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