| // |
| // 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_H |
| #define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_H |
| |
| #include "compiler/intermediate.h" |
| |
| #include <set> |
| #include <stack> |
| |
| class TGraphNode; |
| class TGraphParentNode; |
| class TGraphArgument; |
| class TGraphFunctionCall; |
| class TGraphSymbol; |
| class TGraphSelection; |
| class TGraphLoop; |
| class TGraphLogicalOp; |
| class TDependencyGraphTraverser; |
| class TDependencyGraphOutput; |
| |
| typedef std::set<TGraphNode*> TGraphNodeSet; |
| typedef std::vector<TGraphNode*> TGraphNodeVector; |
| typedef std::vector<TGraphSymbol*> TGraphSymbolVector; |
| typedef std::vector<TGraphFunctionCall*> TFunctionCallVector; |
| |
| // |
| // Base class for all dependency graph nodes. |
| // |
| class TGraphNode { |
| public: |
| TGraphNode(TIntermNode* node) : intermNode(node) {} |
| virtual ~TGraphNode() {} |
| virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| protected: |
| TIntermNode* intermNode; |
| }; |
| |
| // |
| // Base class for dependency graph nodes that may have children. |
| // |
| class TGraphParentNode : public TGraphNode { |
| public: |
| TGraphParentNode(TIntermNode* node) : TGraphNode(node) {} |
| virtual ~TGraphParentNode() {} |
| void addDependentNode(TGraphNode* node) { if (node != this) mDependentNodes.insert(node); } |
| virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| private: |
| TGraphNodeSet mDependentNodes; |
| }; |
| |
| // |
| // Handle function call arguments. |
| // |
| class TGraphArgument : public TGraphParentNode { |
| public: |
| TGraphArgument(TIntermAggregate* intermFunctionCall, int argumentNumber) |
| : TGraphParentNode(intermFunctionCall) |
| , mArgumentNumber(argumentNumber) {} |
| virtual ~TGraphArgument() {} |
| const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); } |
| int getArgumentNumber() const { return mArgumentNumber; } |
| virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| private: |
| int mArgumentNumber; |
| }; |
| |
| // |
| // Handle function calls. |
| // |
| class TGraphFunctionCall : public TGraphParentNode { |
| public: |
| TGraphFunctionCall(TIntermAggregate* intermFunctionCall) |
| : TGraphParentNode(intermFunctionCall) {} |
| virtual ~TGraphFunctionCall() {} |
| const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); } |
| virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| }; |
| |
| // |
| // Handle symbols. |
| // |
| class TGraphSymbol : public TGraphParentNode { |
| public: |
| TGraphSymbol(TIntermSymbol* intermSymbol) : TGraphParentNode(intermSymbol) {} |
| virtual ~TGraphSymbol() {} |
| const TIntermSymbol* getIntermSymbol() const { return intermNode->getAsSymbolNode(); } |
| virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| }; |
| |
| // |
| // Handle if statements and ternary operators. |
| // |
| class TGraphSelection : public TGraphNode { |
| public: |
| TGraphSelection(TIntermSelection* intermSelection) : TGraphNode(intermSelection) {} |
| virtual ~TGraphSelection() {} |
| const TIntermSelection* getIntermSelection() const { return intermNode->getAsSelectionNode(); } |
| virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| }; |
| |
| // |
| // Handle for, do-while, and while loops. |
| // |
| class TGraphLoop : public TGraphNode { |
| public: |
| TGraphLoop(TIntermLoop* intermLoop) : TGraphNode(intermLoop) {} |
| virtual ~TGraphLoop() {} |
| const TIntermLoop* getIntermLoop() const { return intermNode->getAsLoopNode(); } |
| virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| }; |
| |
| // |
| // Handle logical and, or. |
| // |
| class TGraphLogicalOp : public TGraphNode { |
| public: |
| TGraphLogicalOp(TIntermBinary* intermLogicalOp) : TGraphNode(intermLogicalOp) {} |
| virtual ~TGraphLogicalOp() {} |
| const TIntermBinary* getIntermLogicalOp() const { return intermNode->getAsBinaryNode(); } |
| const char* getOpString() const; |
| virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| }; |
| |
| // |
| // A dependency graph of symbols, function calls, conditions etc. |
| // |
| // This class provides an interface to the entry points of the dependency graph. |
| // |
| // Dependency graph nodes should be created by using one of the provided "create..." methods. |
| // This class (and nobody else) manages the memory of the created nodes. |
| // Nodes may not be removed after being added, so all created nodes will exist while the |
| // TDependencyGraph instance exists. |
| // |
| class TDependencyGraph { |
| public: |
| TDependencyGraph(TIntermNode* intermNode); |
| ~TDependencyGraph(); |
| TGraphNodeVector::const_iterator begin() const { return mAllNodes.begin(); } |
| TGraphNodeVector::const_iterator end() const { return mAllNodes.end(); } |
| |
| TGraphSymbolVector::const_iterator beginSamplerSymbols() const |
| { |
| return mSamplerSymbols.begin(); |
| } |
| |
| TGraphSymbolVector::const_iterator endSamplerSymbols() const |
| { |
| return mSamplerSymbols.end(); |
| } |
| |
| TFunctionCallVector::const_iterator beginUserDefinedFunctionCalls() const |
| { |
| return mUserDefinedFunctionCalls.begin(); |
| } |
| |
| TFunctionCallVector::const_iterator endUserDefinedFunctionCalls() const |
| { |
| return mUserDefinedFunctionCalls.end(); |
| } |
| |
| TGraphArgument* createArgument(TIntermAggregate* intermFunctionCall, int argumentNumber); |
| TGraphFunctionCall* createFunctionCall(TIntermAggregate* intermFunctionCall); |
| TGraphSymbol* getOrCreateSymbol(TIntermSymbol* intermSymbol); |
| TGraphSelection* createSelection(TIntermSelection* intermSelection); |
| TGraphLoop* createLoop(TIntermLoop* intermLoop); |
| TGraphLogicalOp* createLogicalOp(TIntermBinary* intermLogicalOp); |
| private: |
| typedef TMap<int, TGraphSymbol*> TSymbolIdMap; |
| typedef std::pair<int, TGraphSymbol*> TSymbolIdPair; |
| |
| TGraphNodeVector mAllNodes; |
| TGraphSymbolVector mSamplerSymbols; |
| TFunctionCallVector mUserDefinedFunctionCalls; |
| TSymbolIdMap mSymbolIdMap; |
| }; |
| |
| // |
| // For traversing the dependency graph. Users should derive from this, |
| // put their traversal specific data in it, and then pass it to a |
| // traverse method. |
| // |
| // When using this, just fill in the methods for nodes you want visited. |
| // |
| class TDependencyGraphTraverser { |
| public: |
| TDependencyGraphTraverser() : mDepth(0) {} |
| |
| virtual void visitSymbol(TGraphSymbol* symbol) {}; |
| virtual void visitArgument(TGraphArgument* selection) {}; |
| virtual void visitFunctionCall(TGraphFunctionCall* functionCall) {}; |
| virtual void visitSelection(TGraphSelection* selection) {}; |
| virtual void visitLoop(TGraphLoop* loop) {}; |
| virtual void visitLogicalOp(TGraphLogicalOp* logicalOp) {}; |
| |
| int getDepth() const { return mDepth; } |
| void incrementDepth() { ++mDepth; } |
| void decrementDepth() { --mDepth; } |
| |
| void clearVisited() { mVisited.clear(); } |
| void markVisited(TGraphNode* node) { mVisited.insert(node); } |
| bool isVisited(TGraphNode* node) const { return mVisited.find(node) != mVisited.end(); } |
| private: |
| int mDepth; |
| TGraphNodeSet mVisited; |
| }; |
| |
| #endif |