diff options
Diffstat (limited to 'src/3rdparty/angle/src/compiler/translator/depgraph')
-rw-r--r-- | src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.cpp | 164 | ||||
-rw-r--r-- | src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.h | 194 |
2 files changed, 202 insertions, 156 deletions
diff --git a/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.cpp b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.cpp index d5f2cba5fc..1aeb822d51 100644 --- a/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.cpp +++ b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.cpp @@ -6,24 +6,32 @@ #include "compiler/translator/depgraph/DependencyGraphBuilder.h" -void TDependencyGraphBuilder::build(TIntermNode* node, TDependencyGraph* graph) +void TDependencyGraphBuilder::build(TIntermNode *node, TDependencyGraph *graph) { TDependencyGraphBuilder builder(graph); builder.build(node); } -bool TDependencyGraphBuilder::visitAggregate(Visit visit, TIntermAggregate* intermAggregate) +bool TDependencyGraphBuilder::visitAggregate( + Visit visit, TIntermAggregate *intermAggregate) { - switch (intermAggregate->getOp()) { - case EOpFunction: visitFunctionDefinition(intermAggregate); break; - case EOpFunctionCall: visitFunctionCall(intermAggregate); break; - default: visitAggregateChildren(intermAggregate); break; + switch (intermAggregate->getOp()) + { + case EOpFunction: + visitFunctionDefinition(intermAggregate); + break; + case EOpFunctionCall: + visitFunctionCall(intermAggregate); + break; + default: + visitAggregateChildren(intermAggregate); + break; } - return false; } -void TDependencyGraphBuilder::visitFunctionDefinition(TIntermAggregate* intermAggregate) +void TDependencyGraphBuilder::visitFunctionDefinition( + TIntermAggregate *intermAggregate) { // Currently, we do not support user defined functions. if (intermAggregate->getName() != "main(") @@ -34,64 +42,71 @@ void TDependencyGraphBuilder::visitFunctionDefinition(TIntermAggregate* intermAg // Takes an expression like "f(x)" and creates a dependency graph like // "x -> argument 0 -> function call". -void TDependencyGraphBuilder::visitFunctionCall(TIntermAggregate* intermFunctionCall) +void TDependencyGraphBuilder::visitFunctionCall( + TIntermAggregate *intermFunctionCall) { - TGraphFunctionCall* functionCall = mGraph->createFunctionCall(intermFunctionCall); + TGraphFunctionCall *functionCall = + mGraph->createFunctionCall(intermFunctionCall); // Run through the function call arguments. int argumentNumber = 0; - TIntermSequence& intermArguments = intermFunctionCall->getSequence(); - for (TIntermSequence::const_iterator iter = intermArguments.begin(); - iter != intermArguments.end(); + TIntermSequence *intermArguments = intermFunctionCall->getSequence(); + for (TIntermSequence::const_iterator iter = intermArguments->begin(); + iter != intermArguments->end(); ++iter, ++argumentNumber) { TNodeSetMaintainer nodeSetMaintainer(this); - TIntermNode* intermArgument = *iter; + TIntermNode *intermArgument = *iter; intermArgument->traverse(this); - if (TParentNodeSet* argumentNodes = mNodeSets.getTopSet()) { - TGraphArgument* argument = mGraph->createArgument(intermFunctionCall, argumentNumber); + if (TParentNodeSet *argumentNodes = mNodeSets.getTopSet()) + { + TGraphArgument *argument = mGraph->createArgument( + intermFunctionCall, argumentNumber); connectMultipleNodesToSingleNode(argumentNodes, argument); argument->addDependentNode(functionCall); } } - // Push the leftmost symbol of this function call into the current set of dependent symbols to - // represent the result of this function call. + // Push the leftmost symbol of this function call into the current set of + // dependent symbols to represent the result of this function call. // Thus, an expression like "y = f(x)" will yield a dependency graph like // "x -> argument 0 -> function call -> y". - // This line essentially passes the function call node back up to an earlier visitAssignment - // call, which will create the connection "function call -> y". + // This line essentially passes the function call node back up to an earlier + // visitAssignment call, which will create the connection "function call -> y". mNodeSets.insertIntoTopSet(functionCall); } -void TDependencyGraphBuilder::visitAggregateChildren(TIntermAggregate* intermAggregate) +void TDependencyGraphBuilder::visitAggregateChildren( + TIntermAggregate *intermAggregate) { - TIntermSequence& sequence = intermAggregate->getSequence(); - for(TIntermSequence::const_iterator iter = sequence.begin(); iter != sequence.end(); ++iter) + TIntermSequence *sequence = intermAggregate->getSequence(); + for (TIntermSequence::const_iterator iter = sequence->begin(); + iter != sequence->end(); ++iter) { - TIntermNode* intermChild = *iter; + TIntermNode *intermChild = *iter; intermChild->traverse(this); } } -void TDependencyGraphBuilder::visitSymbol(TIntermSymbol* intermSymbol) +void TDependencyGraphBuilder::visitSymbol(TIntermSymbol *intermSymbol) { - // Push this symbol into the set of dependent symbols for the current assignment or condition - // that we are traversing. - TGraphSymbol* symbol = mGraph->getOrCreateSymbol(intermSymbol); + // Push this symbol into the set of dependent symbols for the current + // assignment or condition that we are traversing. + TGraphSymbol *symbol = mGraph->getOrCreateSymbol(intermSymbol); mNodeSets.insertIntoTopSet(symbol); - // If this symbol is the current leftmost symbol under an assignment, replace the previous - // leftmost symbol with this symbol. - if (!mLeftmostSymbols.empty() && mLeftmostSymbols.top() != &mRightSubtree) { + // If this symbol is the current leftmost symbol under an assignment, replace + // the previous leftmost symbol with this symbol. + if (!mLeftmostSymbols.empty() && mLeftmostSymbols.top() != &mRightSubtree) + { mLeftmostSymbols.pop(); mLeftmostSymbols.push(symbol); } } -bool TDependencyGraphBuilder::visitBinary(Visit visit, TIntermBinary* intermBinary) +bool TDependencyGraphBuilder::visitBinary(Visit visit, TIntermBinary *intermBinary) { TOperator op = intermBinary->getOp(); if (op == EOpInitialize || intermBinary->isAssignment()) @@ -104,13 +119,13 @@ bool TDependencyGraphBuilder::visitBinary(Visit visit, TIntermBinary* intermBina return false; } -void TDependencyGraphBuilder::visitAssignment(TIntermBinary* intermAssignment) +void TDependencyGraphBuilder::visitAssignment(TIntermBinary *intermAssignment) { - TIntermTyped* intermLeft = intermAssignment->getLeft(); + TIntermTyped *intermLeft = intermAssignment->getLeft(); if (!intermLeft) return; - TGraphSymbol* leftmostSymbol = NULL; + TGraphSymbol *leftmostSymbol = NULL; { TNodeSetMaintainer nodeSetMaintainer(this); @@ -120,88 +135,100 @@ void TDependencyGraphBuilder::visitAssignment(TIntermBinary* intermAssignment) intermLeft->traverse(this); leftmostSymbol = mLeftmostSymbols.top(); - // After traversing the left subtree of this assignment, we should have found a real - // leftmost symbol, and the leftmost symbol should not be a placeholder. + // After traversing the left subtree of this assignment, we should + // have found a real leftmost symbol, and the leftmost symbol should + // not be a placeholder. ASSERT(leftmostSymbol != &mLeftSubtree); ASSERT(leftmostSymbol != &mRightSubtree); } - if (TIntermTyped* intermRight = intermAssignment->getRight()) { + if (TIntermTyped *intermRight = intermAssignment->getRight()) + { TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree); intermRight->traverse(this); } - if (TParentNodeSet* assignmentNodes = mNodeSets.getTopSet()) + if (TParentNodeSet *assignmentNodes = mNodeSets.getTopSet()) connectMultipleNodesToSingleNode(assignmentNodes, leftmostSymbol); } - // Push the leftmost symbol of this assignment into the current set of dependent symbols to - // represent the result of this assignment. - // An expression like "a = (b = c)" will yield a dependency graph like "c -> b -> a". - // This line essentially passes the leftmost symbol of the nested assignment ("b" in this - // example) back up to the earlier visitAssignment call for the outer assignment, which will - // create the connection "b -> a". + // Push the leftmost symbol of this assignment into the current set of dependent + // symbols to represent the result of this assignment. + // An expression like "a = (b = c)" will yield a dependency graph like + // "c -> b -> a". + // This line essentially passes the leftmost symbol of the nested assignment + // ("b" in this example) back up to the earlier visitAssignment call for the + // outer assignment, which will create the connection "b -> a". mNodeSets.insertIntoTopSet(leftmostSymbol); } -void TDependencyGraphBuilder::visitLogicalOp(TIntermBinary* intermLogicalOp) +void TDependencyGraphBuilder::visitLogicalOp(TIntermBinary *intermLogicalOp) { - if (TIntermTyped* intermLeft = intermLogicalOp->getLeft()) { + if (TIntermTyped *intermLeft = intermLogicalOp->getLeft()) + { TNodeSetPropagatingMaintainer nodeSetMaintainer(this); intermLeft->traverse(this); - if (TParentNodeSet* leftNodes = mNodeSets.getTopSet()) { - TGraphLogicalOp* logicalOp = mGraph->createLogicalOp(intermLogicalOp); + if (TParentNodeSet *leftNodes = mNodeSets.getTopSet()) + { + TGraphLogicalOp *logicalOp = mGraph->createLogicalOp(intermLogicalOp); connectMultipleNodesToSingleNode(leftNodes, logicalOp); } } - if (TIntermTyped* intermRight = intermLogicalOp->getRight()) { + if (TIntermTyped *intermRight = intermLogicalOp->getRight()) + { TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree); intermRight->traverse(this); } } -void TDependencyGraphBuilder::visitBinaryChildren(TIntermBinary* intermBinary) +void TDependencyGraphBuilder::visitBinaryChildren(TIntermBinary *intermBinary) { - if (TIntermTyped* intermLeft = intermBinary->getLeft()) + if (TIntermTyped *intermLeft = intermBinary->getLeft()) intermLeft->traverse(this); - if (TIntermTyped* intermRight = intermBinary->getRight()) { + if (TIntermTyped *intermRight = intermBinary->getRight()) + { TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree); intermRight->traverse(this); } } -bool TDependencyGraphBuilder::visitSelection(Visit visit, TIntermSelection* intermSelection) +bool TDependencyGraphBuilder::visitSelection( + Visit visit, TIntermSelection *intermSelection) { - if (TIntermNode* intermCondition = intermSelection->getCondition()) { + if (TIntermNode *intermCondition = intermSelection->getCondition()) + { TNodeSetMaintainer nodeSetMaintainer(this); intermCondition->traverse(this); - if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) { - TGraphSelection* selection = mGraph->createSelection(intermSelection); + if (TParentNodeSet *conditionNodes = mNodeSets.getTopSet()) + { + TGraphSelection *selection = mGraph->createSelection(intermSelection); connectMultipleNodesToSingleNode(conditionNodes, selection); } } - if (TIntermNode* intermTrueBlock = intermSelection->getTrueBlock()) + if (TIntermNode *intermTrueBlock = intermSelection->getTrueBlock()) intermTrueBlock->traverse(this); - if (TIntermNode* intermFalseBlock = intermSelection->getFalseBlock()) + if (TIntermNode *intermFalseBlock = intermSelection->getFalseBlock()) intermFalseBlock->traverse(this); return false; } -bool TDependencyGraphBuilder::visitLoop(Visit visit, TIntermLoop* intermLoop) +bool TDependencyGraphBuilder::visitLoop(Visit visit, TIntermLoop *intermLoop) { - if (TIntermTyped* intermCondition = intermLoop->getCondition()) { + if (TIntermTyped *intermCondition = intermLoop->getCondition()) + { TNodeSetMaintainer nodeSetMaintainer(this); intermCondition->traverse(this); - if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) { - TGraphLoop* loop = mGraph->createLoop(intermLoop); + if (TParentNodeSet *conditionNodes = mNodeSets.getTopSet()) + { + TGraphLoop *loop = mGraph->createLoop(intermLoop); connectMultipleNodesToSingleNode(conditionNodes, loop); } } @@ -209,19 +236,20 @@ bool TDependencyGraphBuilder::visitLoop(Visit visit, TIntermLoop* intermLoop) if (TIntermNode* intermBody = intermLoop->getBody()) intermBody->traverse(this); - if (TIntermTyped* intermExpression = intermLoop->getExpression()) + if (TIntermTyped *intermExpression = intermLoop->getExpression()) intermExpression->traverse(this); return false; } -void TDependencyGraphBuilder::connectMultipleNodesToSingleNode(TParentNodeSet* nodes, - TGraphNode* node) const +void TDependencyGraphBuilder::connectMultipleNodesToSingleNode( + TParentNodeSet *nodes, TGraphNode *node) const { - for (TParentNodeSet::const_iterator iter = nodes->begin(); iter != nodes->end(); ++iter) + for (TParentNodeSet::const_iterator iter = nodes->begin(); + iter != nodes->end(); ++iter) { - TGraphParentNode* currentNode = *iter; + TGraphParentNode *currentNode = *iter; currentNode->addDependentNode(node); } } diff --git a/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.h b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.h index 3e928fb77e..b76f075e68 100644 --- a/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.h +++ b/src/3rdparty/angle/src/compiler/translator/depgraph/DependencyGraphBuilder.h @@ -4,55 +4,58 @@ // found in the LICENSE file. // -#ifndef COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H -#define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H +#ifndef COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H +#define COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H #include "compiler/translator/depgraph/DependencyGraph.h" // -// Creates a dependency graph of symbols, function calls, conditions etc. by traversing a -// intermediate tree. +// Creates a dependency graph of symbols, function calls, conditions etc. by +// traversing a intermediate tree. // -class TDependencyGraphBuilder : public TIntermTraverser { -public: - static void build(TIntermNode* node, TDependencyGraph* graph); +class TDependencyGraphBuilder : public TIntermTraverser +{ + public: + static void build(TIntermNode *node, TDependencyGraph *graph); - virtual void visitSymbol(TIntermSymbol*); - virtual bool visitBinary(Visit visit, TIntermBinary*); - virtual bool visitSelection(Visit visit, TIntermSelection*); - virtual bool visitAggregate(Visit visit, TIntermAggregate*); - virtual bool visitLoop(Visit visit, TIntermLoop*); + virtual void visitSymbol(TIntermSymbol *); + virtual bool visitBinary(Visit visit, TIntermBinary *); + virtual bool visitSelection(Visit visit, TIntermSelection *); + virtual bool visitAggregate(Visit visit, TIntermAggregate *); + virtual bool visitLoop(Visit visit, TIntermLoop *); -private: - typedef std::stack<TGraphSymbol*> TSymbolStack; - typedef std::set<TGraphParentNode*> TParentNodeSet; + private: + typedef std::stack<TGraphSymbol *> TSymbolStack; + typedef std::set<TGraphParentNode *> TParentNodeSet; // // For collecting the dependent nodes of assignments, conditions, etc. // while traversing the intermediate tree. // - // This data structure is stack of sets. Each set contains dependency graph parent nodes. + // This data structure is stack of sets. Each set contains dependency graph + // parent nodes. // - class TNodeSetStack { - public: + class TNodeSetStack + { + public: TNodeSetStack() {}; ~TNodeSetStack() { clear(); } // This should only be called after a pushSet. // Returns NULL if the top set is empty. - TParentNodeSet* getTopSet() const + TParentNodeSet *getTopSet() const { - ASSERT(!nodeSets.empty()); - TParentNodeSet* topSet = nodeSets.top(); + ASSERT(!mNodeSets.empty()); + TParentNodeSet *topSet = mNodeSets.top(); return !topSet->empty() ? topSet : NULL; } - void pushSet() { nodeSets.push(new TParentNodeSet()); } + void pushSet() { mNodeSets.push(new TParentNodeSet()); } void popSet() { - ASSERT(!nodeSets.empty()); - delete nodeSets.top(); - nodeSets.pop(); + ASSERT(!mNodeSets.empty()); + delete mNodeSets.top(); + mNodeSets.pop(); } // Pops the top set and adds its contents to the new top set. @@ -60,12 +63,13 @@ private: // If there is no set below the top set, the top set is just deleted. void popSetIntoNext() { - ASSERT(!nodeSets.empty()); - TParentNodeSet* oldTopSet = nodeSets.top(); - nodeSets.pop(); + ASSERT(!mNodeSets.empty()); + TParentNodeSet *oldTopSet = mNodeSets.top(); + mNodeSets.pop(); - if (!nodeSets.empty()) { - TParentNodeSet* newTopSet = nodeSets.top(); + if (!mNodeSets.empty()) + { + TParentNodeSet *newTopSet = mNodeSets.top(); newTopSet->insert(oldTopSet->begin(), oldTopSet->end()); } @@ -76,106 +80,120 @@ private: // This can be called when there is no top set if we are visiting // symbols that are not under an assignment or condition. // We don't need to track those symbols. - void insertIntoTopSet(TGraphParentNode* node) + void insertIntoTopSet(TGraphParentNode *node) { - if (nodeSets.empty()) + if (mNodeSets.empty()) return; - nodeSets.top()->insert(node); + mNodeSets.top()->insert(node); } void clear() { - while (!nodeSets.empty()) + while (!mNodeSets.empty()) popSet(); } - private: - typedef std::stack<TParentNodeSet*> TParentNodeSetStack; + private: + typedef std::stack<TParentNodeSet *> TParentNodeSetStack; - TParentNodeSetStack nodeSets; + TParentNodeSetStack mNodeSets; }; // // An instance of this class pushes a new node set when instantiated. // When the instance goes out of scope, it and pops the node set. // - class TNodeSetMaintainer { - public: - TNodeSetMaintainer(TDependencyGraphBuilder* factory) - : sets(factory->mNodeSets) { sets.pushSet(); } - ~TNodeSetMaintainer() { sets.popSet(); } - protected: - TNodeSetStack& sets; + class TNodeSetMaintainer + { + public: + TNodeSetMaintainer(TDependencyGraphBuilder *factory) + : mSets(factory->mNodeSets) + { + mSets.pushSet(); + } + ~TNodeSetMaintainer() { mSets.popSet(); } + protected: + TNodeSetStack &mSets; }; // // An instance of this class pushes a new node set when instantiated. - // When the instance goes out of scope, it and pops the top node set and adds its contents to - // the new top node set. + // When the instance goes out of scope, it and pops the top node set and adds + // its contents to the new top node set. // - class TNodeSetPropagatingMaintainer { - public: - TNodeSetPropagatingMaintainer(TDependencyGraphBuilder* factory) - : sets(factory->mNodeSets) { sets.pushSet(); } - ~TNodeSetPropagatingMaintainer() { sets.popSetIntoNext(); } - protected: - TNodeSetStack& sets; + class TNodeSetPropagatingMaintainer + { + public: + TNodeSetPropagatingMaintainer(TDependencyGraphBuilder *factory) + : mSets(factory->mNodeSets) + { + mSets.pushSet(); + } + ~TNodeSetPropagatingMaintainer() { mSets.popSetIntoNext(); } + protected: + TNodeSetStack &mSets; }; // - // An instance of this class keeps track of the leftmost symbol while we're exploring an - // assignment. - // It will push the placeholder symbol kLeftSubtree when instantiated under a left subtree, - // and kRightSubtree under a right subtree. - // When it goes out of scope, it will pop the leftmost symbol at the top of the scope. - // During traversal, the TDependencyGraphBuilder will replace kLeftSubtree with a real symbol. - // kRightSubtree will never be replaced by a real symbol because we are tracking the leftmost - // symbol. + // An instance of this class keeps track of the leftmost symbol while we're + // exploring an assignment. + // It will push the placeholder symbol kLeftSubtree when instantiated under a + // left subtree, and kRightSubtree under a right subtree. + // When it goes out of scope, it will pop the leftmost symbol at the top of the + // scope. + // During traversal, the TDependencyGraphBuilder will replace kLeftSubtree with + // a real symbol. + // kRightSubtree will never be replaced by a real symbol because we are tracking + // the leftmost symbol. // - class TLeftmostSymbolMaintainer { - public: - TLeftmostSymbolMaintainer(TDependencyGraphBuilder* factory, TGraphSymbol& subtree) - : leftmostSymbols(factory->mLeftmostSymbols) + class TLeftmostSymbolMaintainer + { + public: + TLeftmostSymbolMaintainer( + TDependencyGraphBuilder *factory, TGraphSymbol &subtree) + : mLeftmostSymbols(factory->mLeftmostSymbols) { - needsPlaceholderSymbol = leftmostSymbols.empty() || leftmostSymbols.top() != &subtree; - if (needsPlaceholderSymbol) - leftmostSymbols.push(&subtree); + mNeedsPlaceholderSymbol = + mLeftmostSymbols.empty() || mLeftmostSymbols.top() != &subtree; + if (mNeedsPlaceholderSymbol) + mLeftmostSymbols.push(&subtree); } ~TLeftmostSymbolMaintainer() { - if (needsPlaceholderSymbol) - leftmostSymbols.pop(); + if (mNeedsPlaceholderSymbol) + mLeftmostSymbols.pop(); } - protected: - TSymbolStack& leftmostSymbols; - bool needsPlaceholderSymbol; + protected: + TSymbolStack& mLeftmostSymbols; + bool mNeedsPlaceholderSymbol; }; - TDependencyGraphBuilder(TDependencyGraph* graph) - : TIntermTraverser(true, false, false) - , mLeftSubtree(NULL) - , mRightSubtree(NULL) - , mGraph(graph) {} - void build(TIntermNode* intermNode) { intermNode->traverse(this); } + TDependencyGraphBuilder(TDependencyGraph *graph) + : TIntermTraverser(true, false, false), + mLeftSubtree(NULL), + mRightSubtree(NULL), + mGraph(graph) {} + void build(TIntermNode *intermNode) { intermNode->traverse(this); } - void connectMultipleNodesToSingleNode(TParentNodeSet* nodes, TGraphNode* node) const; + void connectMultipleNodesToSingleNode( + TParentNodeSet *nodes, TGraphNode *node) const; - void visitAssignment(TIntermBinary*); - void visitLogicalOp(TIntermBinary*); - void visitBinaryChildren(TIntermBinary*); - void visitFunctionDefinition(TIntermAggregate*); - void visitFunctionCall(TIntermAggregate* intermFunctionCall); - void visitAggregateChildren(TIntermAggregate*); + void visitAssignment(TIntermBinary *); + void visitLogicalOp(TIntermBinary *); + void visitBinaryChildren(TIntermBinary *); + void visitFunctionDefinition(TIntermAggregate *); + void visitFunctionCall(TIntermAggregate *intermFunctionCall); + void visitAggregateChildren(TIntermAggregate *); TGraphSymbol mLeftSubtree; TGraphSymbol mRightSubtree; - TDependencyGraph* mGraph; + TDependencyGraph *mGraph; TNodeSetStack mNodeSets; TSymbolStack mLeftmostSymbols; }; -#endif // COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H +#endif // COMPILER_TRANSLATOR_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H |