1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/angle/src/compiler/depgraph/DependencyGraph.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,212 @@
1.4 +//
1.5 +// Copyright (c) 2012 The ANGLE Project Authors. All rights reserved.
1.6 +// Use of this source code is governed by a BSD-style license that can be
1.7 +// found in the LICENSE file.
1.8 +//
1.9 +
1.10 +#ifndef COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_H
1.11 +#define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_H
1.12 +
1.13 +#include "compiler/intermediate.h"
1.14 +
1.15 +#include <set>
1.16 +#include <stack>
1.17 +
1.18 +class TGraphNode;
1.19 +class TGraphParentNode;
1.20 +class TGraphArgument;
1.21 +class TGraphFunctionCall;
1.22 +class TGraphSymbol;
1.23 +class TGraphSelection;
1.24 +class TGraphLoop;
1.25 +class TGraphLogicalOp;
1.26 +class TDependencyGraphTraverser;
1.27 +class TDependencyGraphOutput;
1.28 +
1.29 +typedef std::set<TGraphNode*> TGraphNodeSet;
1.30 +typedef std::vector<TGraphNode*> TGraphNodeVector;
1.31 +typedef std::vector<TGraphSymbol*> TGraphSymbolVector;
1.32 +typedef std::vector<TGraphFunctionCall*> TFunctionCallVector;
1.33 +
1.34 +//
1.35 +// Base class for all dependency graph nodes.
1.36 +//
1.37 +class TGraphNode {
1.38 +public:
1.39 + TGraphNode(TIntermNode* node) : intermNode(node) {}
1.40 + virtual ~TGraphNode() {}
1.41 + virtual void traverse(TDependencyGraphTraverser* graphTraverser);
1.42 +protected:
1.43 + TIntermNode* intermNode;
1.44 +};
1.45 +
1.46 +//
1.47 +// Base class for dependency graph nodes that may have children.
1.48 +//
1.49 +class TGraphParentNode : public TGraphNode {
1.50 +public:
1.51 + TGraphParentNode(TIntermNode* node) : TGraphNode(node) {}
1.52 + virtual ~TGraphParentNode() {}
1.53 + void addDependentNode(TGraphNode* node) { if (node != this) mDependentNodes.insert(node); }
1.54 + virtual void traverse(TDependencyGraphTraverser* graphTraverser);
1.55 +private:
1.56 + TGraphNodeSet mDependentNodes;
1.57 +};
1.58 +
1.59 +//
1.60 +// Handle function call arguments.
1.61 +//
1.62 +class TGraphArgument : public TGraphParentNode {
1.63 +public:
1.64 + TGraphArgument(TIntermAggregate* intermFunctionCall, int argumentNumber)
1.65 + : TGraphParentNode(intermFunctionCall)
1.66 + , mArgumentNumber(argumentNumber) {}
1.67 + virtual ~TGraphArgument() {}
1.68 + const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); }
1.69 + int getArgumentNumber() const { return mArgumentNumber; }
1.70 + virtual void traverse(TDependencyGraphTraverser* graphTraverser);
1.71 +private:
1.72 + int mArgumentNumber;
1.73 +};
1.74 +
1.75 +//
1.76 +// Handle function calls.
1.77 +//
1.78 +class TGraphFunctionCall : public TGraphParentNode {
1.79 +public:
1.80 + TGraphFunctionCall(TIntermAggregate* intermFunctionCall)
1.81 + : TGraphParentNode(intermFunctionCall) {}
1.82 + virtual ~TGraphFunctionCall() {}
1.83 + const TIntermAggregate* getIntermFunctionCall() const { return intermNode->getAsAggregate(); }
1.84 + virtual void traverse(TDependencyGraphTraverser* graphTraverser);
1.85 +};
1.86 +
1.87 +//
1.88 +// Handle symbols.
1.89 +//
1.90 +class TGraphSymbol : public TGraphParentNode {
1.91 +public:
1.92 + TGraphSymbol(TIntermSymbol* intermSymbol) : TGraphParentNode(intermSymbol) {}
1.93 + virtual ~TGraphSymbol() {}
1.94 + const TIntermSymbol* getIntermSymbol() const { return intermNode->getAsSymbolNode(); }
1.95 + virtual void traverse(TDependencyGraphTraverser* graphTraverser);
1.96 +};
1.97 +
1.98 +//
1.99 +// Handle if statements and ternary operators.
1.100 +//
1.101 +class TGraphSelection : public TGraphNode {
1.102 +public:
1.103 + TGraphSelection(TIntermSelection* intermSelection) : TGraphNode(intermSelection) {}
1.104 + virtual ~TGraphSelection() {}
1.105 + const TIntermSelection* getIntermSelection() const { return intermNode->getAsSelectionNode(); }
1.106 + virtual void traverse(TDependencyGraphTraverser* graphTraverser);
1.107 +};
1.108 +
1.109 +//
1.110 +// Handle for, do-while, and while loops.
1.111 +//
1.112 +class TGraphLoop : public TGraphNode {
1.113 +public:
1.114 + TGraphLoop(TIntermLoop* intermLoop) : TGraphNode(intermLoop) {}
1.115 + virtual ~TGraphLoop() {}
1.116 + const TIntermLoop* getIntermLoop() const { return intermNode->getAsLoopNode(); }
1.117 + virtual void traverse(TDependencyGraphTraverser* graphTraverser);
1.118 +};
1.119 +
1.120 +//
1.121 +// Handle logical and, or.
1.122 +//
1.123 +class TGraphLogicalOp : public TGraphNode {
1.124 +public:
1.125 + TGraphLogicalOp(TIntermBinary* intermLogicalOp) : TGraphNode(intermLogicalOp) {}
1.126 + virtual ~TGraphLogicalOp() {}
1.127 + const TIntermBinary* getIntermLogicalOp() const { return intermNode->getAsBinaryNode(); }
1.128 + const char* getOpString() const;
1.129 + virtual void traverse(TDependencyGraphTraverser* graphTraverser);
1.130 +};
1.131 +
1.132 +//
1.133 +// A dependency graph of symbols, function calls, conditions etc.
1.134 +//
1.135 +// This class provides an interface to the entry points of the dependency graph.
1.136 +//
1.137 +// Dependency graph nodes should be created by using one of the provided "create..." methods.
1.138 +// This class (and nobody else) manages the memory of the created nodes.
1.139 +// Nodes may not be removed after being added, so all created nodes will exist while the
1.140 +// TDependencyGraph instance exists.
1.141 +//
1.142 +class TDependencyGraph {
1.143 +public:
1.144 + TDependencyGraph(TIntermNode* intermNode);
1.145 + ~TDependencyGraph();
1.146 + TGraphNodeVector::const_iterator begin() const { return mAllNodes.begin(); }
1.147 + TGraphNodeVector::const_iterator end() const { return mAllNodes.end(); }
1.148 +
1.149 + TGraphSymbolVector::const_iterator beginSamplerSymbols() const
1.150 + {
1.151 + return mSamplerSymbols.begin();
1.152 + }
1.153 +
1.154 + TGraphSymbolVector::const_iterator endSamplerSymbols() const
1.155 + {
1.156 + return mSamplerSymbols.end();
1.157 + }
1.158 +
1.159 + TFunctionCallVector::const_iterator beginUserDefinedFunctionCalls() const
1.160 + {
1.161 + return mUserDefinedFunctionCalls.begin();
1.162 + }
1.163 +
1.164 + TFunctionCallVector::const_iterator endUserDefinedFunctionCalls() const
1.165 + {
1.166 + return mUserDefinedFunctionCalls.end();
1.167 + }
1.168 +
1.169 + TGraphArgument* createArgument(TIntermAggregate* intermFunctionCall, int argumentNumber);
1.170 + TGraphFunctionCall* createFunctionCall(TIntermAggregate* intermFunctionCall);
1.171 + TGraphSymbol* getOrCreateSymbol(TIntermSymbol* intermSymbol);
1.172 + TGraphSelection* createSelection(TIntermSelection* intermSelection);
1.173 + TGraphLoop* createLoop(TIntermLoop* intermLoop);
1.174 + TGraphLogicalOp* createLogicalOp(TIntermBinary* intermLogicalOp);
1.175 +private:
1.176 + typedef TMap<int, TGraphSymbol*> TSymbolIdMap;
1.177 + typedef std::pair<int, TGraphSymbol*> TSymbolIdPair;
1.178 +
1.179 + TGraphNodeVector mAllNodes;
1.180 + TGraphSymbolVector mSamplerSymbols;
1.181 + TFunctionCallVector mUserDefinedFunctionCalls;
1.182 + TSymbolIdMap mSymbolIdMap;
1.183 +};
1.184 +
1.185 +//
1.186 +// For traversing the dependency graph. Users should derive from this,
1.187 +// put their traversal specific data in it, and then pass it to a
1.188 +// traverse method.
1.189 +//
1.190 +// When using this, just fill in the methods for nodes you want visited.
1.191 +//
1.192 +class TDependencyGraphTraverser {
1.193 +public:
1.194 + TDependencyGraphTraverser() : mDepth(0) {}
1.195 +
1.196 + virtual void visitSymbol(TGraphSymbol* symbol) {};
1.197 + virtual void visitArgument(TGraphArgument* selection) {};
1.198 + virtual void visitFunctionCall(TGraphFunctionCall* functionCall) {};
1.199 + virtual void visitSelection(TGraphSelection* selection) {};
1.200 + virtual void visitLoop(TGraphLoop* loop) {};
1.201 + virtual void visitLogicalOp(TGraphLogicalOp* logicalOp) {};
1.202 +
1.203 + int getDepth() const { return mDepth; }
1.204 + void incrementDepth() { ++mDepth; }
1.205 + void decrementDepth() { --mDepth; }
1.206 +
1.207 + void clearVisited() { mVisited.clear(); }
1.208 + void markVisited(TGraphNode* node) { mVisited.insert(node); }
1.209 + bool isVisited(TGraphNode* node) const { return mVisited.find(node) != mVisited.end(); }
1.210 +private:
1.211 + int mDepth;
1.212 + TGraphNodeSet mVisited;
1.213 +};
1.214 +
1.215 +#endif
