Home | History | Annotate | Download | only in depgraph
      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 
     10 #include "compiler/intermediate.h"
     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;
     28 typedef std::vector<TGraphSymbol*> TGraphSymbolVector;
     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 
    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 
    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 
    166     TGraphArgument* createArgument(TIntermAggregate* intermFunctionCall, int argumentNumber);
    167     TGraphFunctionCall* createFunctionCall(TIntermAggregate* intermFunctionCall);
    168     TGraphSymbol* getOrCreateSymbol(TIntermSymbol* intermSymbol);
    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 
    176     TGraphNodeVector mAllNodes;
    177     TGraphSymbolVector mSamplerSymbols;
    178     TFunctionCallVector mUserDefinedFunctionCalls;
    179     TSymbolIdMap mSymbolIdMap;
    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
    213