| // |
| // 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_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. |
| // |
| 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(!mNodeSets.empty()); |
| TParentNodeSet *topSet = mNodeSets.top(); |
| return !topSet->empty() ? topSet : NULL; |
| } |
| |
| void pushSet() { mNodeSets.push(new TParentNodeSet()); } |
| void popSet() |
| { |
| ASSERT(!mNodeSets.empty()); |
| delete mNodeSets.top(); |
| mNodeSets.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(!mNodeSets.empty()); |
| TParentNodeSet *oldTopSet = mNodeSets.top(); |
| mNodeSets.pop(); |
| |
| if (!mNodeSets.empty()) |
| { |
| TParentNodeSet *newTopSet = mNodeSets.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 (mNodeSets.empty()) |
| return; |
| |
| mNodeSets.top()->insert(node); |
| } |
| |
| void clear() |
| { |
| while (!mNodeSets.empty()) |
| popSet(); |
| } |
| |
| private: |
| typedef std::stack<TParentNodeSet *> TParentNodeSetStack; |
| |
| 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) |
| : 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. |
| // |
| 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. |
| // |
| class TLeftmostSymbolMaintainer |
| { |
| public: |
| TLeftmostSymbolMaintainer( |
| TDependencyGraphBuilder *factory, TGraphSymbol &subtree) |
| : mLeftmostSymbols(factory->mLeftmostSymbols) |
| { |
| mNeedsPlaceholderSymbol = |
| mLeftmostSymbols.empty() || mLeftmostSymbols.top() != &subtree; |
| if (mNeedsPlaceholderSymbol) |
| mLeftmostSymbols.push(&subtree); |
| } |
| |
| ~TLeftmostSymbolMaintainer() |
| { |
| if (mNeedsPlaceholderSymbol) |
| mLeftmostSymbols.pop(); |
| } |
| |
| 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); } |
| |
| 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_TRANSLATOR_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H |