maxvujovic@gmail.com | 66ebd01 | 2012-05-30 22:18:11 +0000 | [diff] [blame] | 1 | // |
| 2 | // Copyright (c) 2012 The ANGLE Project Authors. All rights reserved. |
| 3 | // Use of this source code is governed by a BSD-style license that can be |
| 4 | // found in the LICENSE file. |
| 5 | // |
| 6 | |
| 7 | #ifndef COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_H |
| 8 | #define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_H |
| 9 | |
Jamie Madill | b1a85f4 | 2014-08-19 15:23:24 -0400 | [diff] [blame] | 10 | #include "compiler/translator/IntermNode.h" |
maxvujovic@gmail.com | 66ebd01 | 2012-05-30 22:18:11 +0000 | [diff] [blame] | 11 | |
| 12 | #include <set> |
| 13 | #include <stack> |
| 14 | |
| 15 | class TGraphNode; |
| 16 | class TGraphParentNode; |
| 17 | class TGraphArgument; |
| 18 | class TGraphFunctionCall; |
| 19 | class TGraphSymbol; |
| 20 | class TGraphSelection; |
| 21 | class TGraphLoop; |
| 22 | class TGraphLogicalOp; |
| 23 | class TDependencyGraphTraverser; |
| 24 | class TDependencyGraphOutput; |
| 25 | |
| 26 | typedef std::set<TGraphNode*> TGraphNodeSet; |
| 27 | typedef std::vector<TGraphNode*> TGraphNodeVector; |
maxvujovic@gmail.com | 77222c9 | 2012-06-04 21:06:05 +0000 | [diff] [blame] | 28 | typedef std::vector<TGraphSymbol*> TGraphSymbolVector; |
maxvujovic@gmail.com | 66ebd01 | 2012-05-30 22:18:11 +0000 | [diff] [blame] | 29 | typedef std::vector<TGraphFunctionCall*> TFunctionCallVector; |
| 30 | |
| 31 | // |
| 32 | // Base class for all dependency graph nodes. |
| 33 | // |
| 34 | class TGraphNode { |
| 35 | public: |
| 36 | TGraphNode(TIntermNode* node) : intermNode(node) {} |
| 37 | virtual ~TGraphNode() {} |
| 38 | virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| 39 | protected: |
| 40 | TIntermNode* intermNode; |
| 41 | }; |
| 42 | |
| 43 | // |
| 44 | // Base class for dependency graph nodes that may have children. |
| 45 | // |
| 46 | class TGraphParentNode : public TGraphNode { |
| 47 | public: |
| 48 | TGraphParentNode(TIntermNode* node) : TGraphNode(node) {} |
| 49 | virtual ~TGraphParentNode() {} |
| 50 | void addDependentNode(TGraphNode* node) { if (node != this) mDependentNodes.insert(node); } |
| 51 | virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| 52 | private: |
| 53 | TGraphNodeSet mDependentNodes; |
| 54 | }; |
| 55 | |
| 56 | // |
| 57 | // Handle function call arguments. |
| 58 | // |
| 59 | class TGraphArgument : public TGraphParentNode { |
| 60 | public: |
| 61 | TGraphArgument(TIntermAggregate* intermFunctionCall, int argumentNumber) |
| 62 | : TGraphParentNode(intermFunctionCall) |
| 63 | , mArgumentNumber(argumentNumber) {} |
| 64 | virtual ~TGraphArgument() {} |
| 65 | const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); } |
| 66 | int getArgumentNumber() const { return mArgumentNumber; } |
| 67 | virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| 68 | private: |
| 69 | int mArgumentNumber; |
| 70 | }; |
| 71 | |
| 72 | // |
| 73 | // Handle function calls. |
| 74 | // |
| 75 | class TGraphFunctionCall : public TGraphParentNode { |
| 76 | public: |
| 77 | TGraphFunctionCall(TIntermAggregate* intermFunctionCall) |
| 78 | : TGraphParentNode(intermFunctionCall) {} |
| 79 | virtual ~TGraphFunctionCall() {} |
| 80 | const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); } |
| 81 | virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| 82 | }; |
| 83 | |
| 84 | // |
| 85 | // Handle symbols. |
| 86 | // |
| 87 | class TGraphSymbol : public TGraphParentNode { |
| 88 | public: |
| 89 | TGraphSymbol(TIntermSymbol* intermSymbol) : TGraphParentNode(intermSymbol) {} |
| 90 | virtual ~TGraphSymbol() {} |
| 91 | const TIntermSymbol* getIntermSymbol() const { return intermNode->getAsSymbolNode(); } |
| 92 | virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| 93 | }; |
| 94 | |
| 95 | // |
| 96 | // Handle if statements and ternary operators. |
| 97 | // |
| 98 | class TGraphSelection : public TGraphNode { |
| 99 | public: |
| 100 | TGraphSelection(TIntermSelection* intermSelection) : TGraphNode(intermSelection) {} |
| 101 | virtual ~TGraphSelection() {} |
| 102 | const TIntermSelection* getIntermSelection() const { return intermNode->getAsSelectionNode(); } |
| 103 | virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| 104 | }; |
| 105 | |
| 106 | // |
| 107 | // Handle for, do-while, and while loops. |
| 108 | // |
| 109 | class TGraphLoop : public TGraphNode { |
| 110 | public: |
| 111 | TGraphLoop(TIntermLoop* intermLoop) : TGraphNode(intermLoop) {} |
| 112 | virtual ~TGraphLoop() {} |
| 113 | const TIntermLoop* getIntermLoop() const { return intermNode->getAsLoopNode(); } |
| 114 | virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| 115 | }; |
| 116 | |
| 117 | // |
| 118 | // Handle logical and, or. |
| 119 | // |
| 120 | class TGraphLogicalOp : public TGraphNode { |
| 121 | public: |
| 122 | TGraphLogicalOp(TIntermBinary* intermLogicalOp) : TGraphNode(intermLogicalOp) {} |
| 123 | virtual ~TGraphLogicalOp() {} |
| 124 | const TIntermBinary* getIntermLogicalOp() const { return intermNode->getAsBinaryNode(); } |
| 125 | const char* getOpString() const; |
| 126 | virtual void traverse(TDependencyGraphTraverser* graphTraverser); |
| 127 | }; |
| 128 | |
| 129 | // |
| 130 | // A dependency graph of symbols, function calls, conditions etc. |
| 131 | // |
| 132 | // This class provides an interface to the entry points of the dependency graph. |
| 133 | // |
| 134 | // Dependency graph nodes should be created by using one of the provided "create..." methods. |
| 135 | // This class (and nobody else) manages the memory of the created nodes. |
| 136 | // Nodes may not be removed after being added, so all created nodes will exist while the |
| 137 | // TDependencyGraph instance exists. |
| 138 | // |
| 139 | class TDependencyGraph { |
| 140 | public: |
| 141 | TDependencyGraph(TIntermNode* intermNode); |
| 142 | ~TDependencyGraph(); |
| 143 | TGraphNodeVector::const_iterator begin() const { return mAllNodes.begin(); } |
| 144 | TGraphNodeVector::const_iterator end() const { return mAllNodes.end(); } |
| 145 | |
maxvujovic@gmail.com | 77222c9 | 2012-06-04 21:06:05 +0000 | [diff] [blame] | 146 | TGraphSymbolVector::const_iterator beginSamplerSymbols() const |
| 147 | { |
| 148 | return mSamplerSymbols.begin(); |
| 149 | } |
| 150 | |
| 151 | TGraphSymbolVector::const_iterator endSamplerSymbols() const |
| 152 | { |
| 153 | return mSamplerSymbols.end(); |
| 154 | } |
| 155 | |
maxvujovic@gmail.com | 66ebd01 | 2012-05-30 22:18:11 +0000 | [diff] [blame] | 156 | TFunctionCallVector::const_iterator beginUserDefinedFunctionCalls() const |
| 157 | { |
| 158 | return mUserDefinedFunctionCalls.begin(); |
| 159 | } |
| 160 | |
| 161 | TFunctionCallVector::const_iterator endUserDefinedFunctionCalls() const |
| 162 | { |
| 163 | return mUserDefinedFunctionCalls.end(); |
| 164 | } |
| 165 | |
maxvujovic@gmail.com | 66ebd01 | 2012-05-30 22:18:11 +0000 | [diff] [blame] | 166 | TGraphArgument* createArgument(TIntermAggregate* intermFunctionCall, int argumentNumber); |
| 167 | TGraphFunctionCall* createFunctionCall(TIntermAggregate* intermFunctionCall); |
maxvujovic@gmail.com | 77222c9 | 2012-06-04 21:06:05 +0000 | [diff] [blame] | 168 | TGraphSymbol* getOrCreateSymbol(TIntermSymbol* intermSymbol); |
maxvujovic@gmail.com | 66ebd01 | 2012-05-30 22:18:11 +0000 | [diff] [blame] | 169 | TGraphSelection* createSelection(TIntermSelection* intermSelection); |
| 170 | TGraphLoop* createLoop(TIntermLoop* intermLoop); |
| 171 | TGraphLogicalOp* createLogicalOp(TIntermBinary* intermLogicalOp); |
| 172 | private: |
| 173 | typedef TMap<int, TGraphSymbol*> TSymbolIdMap; |
| 174 | typedef std::pair<int, TGraphSymbol*> TSymbolIdPair; |
| 175 | |
maxvujovic@gmail.com | 66ebd01 | 2012-05-30 22:18:11 +0000 | [diff] [blame] | 176 | TGraphNodeVector mAllNodes; |
maxvujovic@gmail.com | 77222c9 | 2012-06-04 21:06:05 +0000 | [diff] [blame] | 177 | TGraphSymbolVector mSamplerSymbols; |
| 178 | TFunctionCallVector mUserDefinedFunctionCalls; |
| 179 | TSymbolIdMap mSymbolIdMap; |
maxvujovic@gmail.com | 66ebd01 | 2012-05-30 22:18:11 +0000 | [diff] [blame] | 180 | }; |
| 181 | |
| 182 | // |
| 183 | // For traversing the dependency graph. Users should derive from this, |
| 184 | // put their traversal specific data in it, and then pass it to a |
| 185 | // traverse method. |
| 186 | // |
| 187 | // When using this, just fill in the methods for nodes you want visited. |
| 188 | // |
| 189 | class TDependencyGraphTraverser { |
| 190 | public: |
| 191 | TDependencyGraphTraverser() : mDepth(0) {} |
| 192 | |
| 193 | virtual void visitSymbol(TGraphSymbol* symbol) {}; |
| 194 | virtual void visitArgument(TGraphArgument* selection) {}; |
| 195 | virtual void visitFunctionCall(TGraphFunctionCall* functionCall) {}; |
| 196 | virtual void visitSelection(TGraphSelection* selection) {}; |
| 197 | virtual void visitLoop(TGraphLoop* loop) {}; |
| 198 | virtual void visitLogicalOp(TGraphLogicalOp* logicalOp) {}; |
| 199 | |
| 200 | int getDepth() const { return mDepth; } |
| 201 | void incrementDepth() { ++mDepth; } |
| 202 | void decrementDepth() { --mDepth; } |
| 203 | |
| 204 | void clearVisited() { mVisited.clear(); } |
| 205 | void markVisited(TGraphNode* node) { mVisited.insert(node); } |
| 206 | bool isVisited(TGraphNode* node) const { return mVisited.find(node) != mVisited.end(); } |
| 207 | private: |
| 208 | int mDepth; |
| 209 | TGraphNodeSet mVisited; |
| 210 | }; |
| 211 | |
| 212 | #endif |