| // |
| // Copyright (c) 2012 The ANGLE Project Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| // |
| |
| #ifndef COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H |
| #define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H |
| |
| #include "compiler/depgraph/DependencyGraph.h" |
| |
| // |
| // 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); |
| |
| 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; |
| |
| // |
| // 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. |
| // |
| 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 |
| { |
| ASSERT(!nodeSets.empty()); |
| TParentNodeSet* topSet = nodeSets.top(); |
| return !topSet->empty() ? topSet : NULL; |
| } |
| |
| void pushSet() { nodeSets.push(new TParentNodeSet()); } |
| void popSet() |
| { |
| ASSERT(!nodeSets.empty()); |
| delete nodeSets.top(); |
| nodeSets.pop(); |
| } |
| |
| // Pops the top set and adds its contents to the new top set. |
| // This should only be called after a pushSet. |
| // 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(); |
| |
| if (!nodeSets.empty()) { |
| TParentNodeSet* newTopSet = nodeSets.top(); |
| newTopSet->insert(oldTopSet->begin(), oldTopSet->end()); |
| } |
| |
| delete oldTopSet; |
| } |
| |
| // Does nothing if there is no top set. |
| // 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) |
| { |
| if (nodeSets.empty()) |
| return; |
| |
| nodeSets.top()->insert(node); |
| } |
| |
| void clear() |
| { |
| while (!nodeSets.empty()) |
| popSet(); |
| } |
| |
| private: |
| typedef std::stack<TParentNodeSet*> TParentNodeSetStack; |
| |
| TParentNodeSetStack nodeSets; |
| }; |
| |
| // |
| // 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; |
| }; |
| |
| // |
| // 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. |
| // |
| class TNodeSetPropagatingMaintainer { |
| public: |
| TNodeSetPropagatingMaintainer(TDependencyGraphBuilder* factory) |
| : sets(factory->mNodeSets) { sets.pushSet(); } |
| ~TNodeSetPropagatingMaintainer() { sets.popSetIntoNext(); } |
| protected: |
| TNodeSetStack& sets; |
| }; |
| |
| // |
| // 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) |
| { |
| needsPlaceholderSymbol = leftmostSymbols.empty() || leftmostSymbols.top() != &subtree; |
| if (needsPlaceholderSymbol) |
| leftmostSymbols.push(&subtree); |
| } |
| |
| ~TLeftmostSymbolMaintainer() |
| { |
| if (needsPlaceholderSymbol) |
| leftmostSymbols.pop(); |
| } |
| |
| protected: |
| TSymbolStack& leftmostSymbols; |
| bool needsPlaceholderSymbol; |
| }; |
| |
| 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 visitAssignment(TIntermBinary*); |
| void visitLogicalOp(TIntermBinary*); |
| void visitBinaryChildren(TIntermBinary*); |
| void visitFunctionDefinition(TIntermAggregate*); |
| void visitFunctionCall(TIntermAggregate* intermFunctionCall); |
| void visitAggregateChildren(TIntermAggregate*); |
| |
| TGraphSymbol mLeftSubtree; |
| TGraphSymbol mRightSubtree; |
| |
| TDependencyGraph* mGraph; |
| TNodeSetStack mNodeSets; |
| TSymbolStack mLeftmostSymbols; |
| }; |
| |
| #endif // COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H |