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_BUILDER_H
      8 #define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
      9 
     10 #include "compiler/depgraph/DependencyGraph.h"
     11 
     12 //
     13 // Creates a dependency graph of symbols, function calls, conditions etc. by traversing a
     14 // intermediate tree.
     15 //
     16 class TDependencyGraphBuilder : public TIntermTraverser {
     17 public:
     18     static void build(TIntermNode* node, TDependencyGraph* graph);
     19 
     20     virtual void visitSymbol(TIntermSymbol*);
     21     virtual bool visitBinary(Visit visit, TIntermBinary*);
     22     virtual bool visitSelection(Visit visit, TIntermSelection*);
     23     virtual bool visitAggregate(Visit visit, TIntermAggregate*);
     24     virtual bool visitLoop(Visit visit, TIntermLoop*);
     25 
     26 private:
     27     typedef std::stack<TGraphSymbol*> TSymbolStack;
     28     typedef std::set<TGraphParentNode*> TParentNodeSet;
     29 
     30     //
     31     // For collecting the dependent nodes of assignments, conditions, etc.
     32     // while traversing the intermediate tree.
     33     //
     34     // This data structure is stack of sets. Each set contains dependency graph parent nodes.
     35     //
     36     class TNodeSetStack {
     37     public:
     38         TNodeSetStack() {};
     39         ~TNodeSetStack() { clear(); }
     40 
     41         // This should only be called after a pushSet.
     42         // Returns NULL if the top set is empty.
     43         TParentNodeSet* getTopSet() const
     44         {
     45             ASSERT(!nodeSets.empty());
     46             TParentNodeSet* topSet = nodeSets.top();
     47             return !topSet->empty() ? topSet : NULL;
     48         }
     49 
     50         void pushSet() { nodeSets.push(new TParentNodeSet()); }
     51         void popSet()
     52         {
     53             ASSERT(!nodeSets.empty());
     54             delete nodeSets.top();
     55             nodeSets.pop();
     56         }
     57 
     58         // Pops the top set and adds its contents to the new top set.
     59         // This should only be called after a pushSet.
     60         // If there is no set below the top set, the top set is just deleted.
     61         void popSetIntoNext()
     62         {
     63             ASSERT(!nodeSets.empty());
     64             TParentNodeSet* oldTopSet = nodeSets.top();
     65             nodeSets.pop();
     66 
     67             if (!nodeSets.empty()) {
     68                 TParentNodeSet* newTopSet = nodeSets.top();
     69                 newTopSet->insert(oldTopSet->begin(), oldTopSet->end());
     70             }
     71 
     72             delete oldTopSet;
     73         }
     74 
     75         // Does nothing if there is no top set.
     76         // This can be called when there is no top set if we are visiting
     77         // symbols that are not under an assignment or condition.
     78         // We don't need to track those symbols.
     79         void insertIntoTopSet(TGraphParentNode* node)
     80         {
     81             if (nodeSets.empty())
     82                 return;
     83 
     84             nodeSets.top()->insert(node);
     85         }
     86 
     87         void clear()
     88         {
     89             while (!nodeSets.empty())
     90                 popSet();
     91         }
     92 
     93     private:
     94         typedef std::stack<TParentNodeSet*> TParentNodeSetStack;
     95 
     96         TParentNodeSetStack nodeSets;
     97     };
     98 
     99     //
    100     // An instance of this class pushes a new node set when instantiated.
    101     // When the instance goes out of scope, it and pops the node set.
    102     //
    103     class TNodeSetMaintainer {
    104     public:
    105         TNodeSetMaintainer(TDependencyGraphBuilder* factory)
    106             : sets(factory->mNodeSets) { sets.pushSet(); }
    107         ~TNodeSetMaintainer() { sets.popSet(); }
    108     protected:
    109         TNodeSetStack& sets;
    110     };
    111 
    112     //
    113     // An instance of this class pushes a new node set when instantiated.
    114     // When the instance goes out of scope, it and pops the top node set and adds its contents to
    115     // the new top node set.
    116     //
    117     class TNodeSetPropagatingMaintainer {
    118     public:
    119         TNodeSetPropagatingMaintainer(TDependencyGraphBuilder* factory)
    120             : sets(factory->mNodeSets) { sets.pushSet(); }
    121         ~TNodeSetPropagatingMaintainer() { sets.popSetIntoNext(); }
    122     protected:
    123         TNodeSetStack& sets;
    124     };
    125 
    126     //
    127     // An instance of this class keeps track of the leftmost symbol while we're exploring an
    128     // assignment.
    129     // It will push the placeholder symbol kLeftSubtree when instantiated under a left subtree,
    130     // and kRightSubtree under a right subtree.
    131     // When it goes out of scope, it will pop the leftmost symbol at the top of the scope.
    132     // During traversal, the TDependencyGraphBuilder will replace kLeftSubtree with a real symbol.
    133     // kRightSubtree will never be replaced by a real symbol because we are tracking the leftmost
    134     // symbol.
    135     //
    136     class TLeftmostSymbolMaintainer {
    137     public:
    138         TLeftmostSymbolMaintainer(TDependencyGraphBuilder* factory, TGraphSymbol& subtree)
    139             : leftmostSymbols(factory->mLeftmostSymbols)
    140         {
    141             needsPlaceholderSymbol = leftmostSymbols.empty() || leftmostSymbols.top() != &subtree;
    142             if (needsPlaceholderSymbol)
    143                 leftmostSymbols.push(&subtree);
    144         }
    145 
    146         ~TLeftmostSymbolMaintainer()
    147         {
    148             if (needsPlaceholderSymbol)
    149                 leftmostSymbols.pop();
    150         }
    151 
    152     protected:
    153         TSymbolStack& leftmostSymbols;
    154         bool needsPlaceholderSymbol;
    155     };
    156 
    157     TDependencyGraphBuilder(TDependencyGraph* graph)
    158         : TIntermTraverser(true, false, false)
    159         , mLeftSubtree(NULL)
    160         , mRightSubtree(NULL)
    161         , mGraph(graph) {}
    162     void build(TIntermNode* intermNode) { intermNode->traverse(this); }
    163 
    164     void connectMultipleNodesToSingleNode(TParentNodeSet* nodes, TGraphNode* node) const;
    165 
    166     void visitAssignment(TIntermBinary*);
    167     void visitLogicalOp(TIntermBinary*);
    168     void visitBinaryChildren(TIntermBinary*);
    169     void visitFunctionDefinition(TIntermAggregate*);
    170     void visitFunctionCall(TIntermAggregate* intermFunctionCall);
    171     void visitAggregateChildren(TIntermAggregate*);
    172 
    173     TGraphSymbol mLeftSubtree;
    174     TGraphSymbol mRightSubtree;
    175 
    176     TDependencyGraph* mGraph;
    177     TNodeSetStack mNodeSets;
    178     TSymbolStack mLeftmostSymbols;
    179 };
    180 
    181 #endif  // COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
    182