The Tor Browser / file revision

 //

 // Copyright (c) 2012 The ANGLE Project Authors. All rights reserved.

 // Use of this source code is governed by a BSD-style license that can be

 // found in the LICENSE file.

 //

 #ifndef COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H

 #define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H

 #include "compiler/depgraph/DependencyGraph.h"

 //

 // Creates a dependency graph of symbols, function calls, conditions etc. by traversing a

 // intermediate tree.

 //

 class TDependencyGraphBuilder : public TIntermTraverser {

 public:

     static void build(TIntermNode* node, TDependencyGraph* graph);

     virtual void visitSymbol(TIntermSymbol*);

     virtual bool visitBinary(Visit visit, TIntermBinary*);

     virtual bool visitSelection(Visit visit, TIntermSelection*);

     virtual bool visitAggregate(Visit visit, TIntermAggregate*);

     virtual bool visitLoop(Visit visit, TIntermLoop*);

 private:

     typedef std::stack<TGraphSymbol*> TSymbolStack;

     typedef std::set<TGraphParentNode*> TParentNodeSet;

     //

     // For collecting the dependent nodes of assignments, conditions, etc.

     // while traversing the intermediate tree.

     //

     // This data structure is stack of sets. Each set contains dependency graph parent nodes.

     //

     class TNodeSetStack {

     public:

         TNodeSetStack() {};

         ~TNodeSetStack() { clear(); }

         // This should only be called after a pushSet.

         // Returns NULL if the top set is empty.

         TParentNodeSet* getTopSet() const

         {

             ASSERT(!nodeSets.empty());

             TParentNodeSet* topSet = nodeSets.top();

             return !topSet->empty() ? topSet : NULL;

         }

         void pushSet() { nodeSets.push(new TParentNodeSet()); }

         void popSet()

         {

             ASSERT(!nodeSets.empty());

             delete nodeSets.top();

             nodeSets.pop();

         }

         // Pops the top set and adds its contents to the new top set.

         // This should only be called after a pushSet.

         // If there is no set below the top set, the top set is just deleted.

         void popSetIntoNext()

         {

             ASSERT(!nodeSets.empty());

             TParentNodeSet* oldTopSet = nodeSets.top();

             nodeSets.pop();

             if (!nodeSets.empty()) {

                 TParentNodeSet* newTopSet = nodeSets.top();

                 newTopSet->insert(oldTopSet->begin(), oldTopSet->end());

             }

             delete oldTopSet;

         }

         // Does nothing if there is no top set.

         // This can be called when there is no top set if we are visiting

         // symbols that are not under an assignment or condition.

         // We don't need to track those symbols.

         void insertIntoTopSet(TGraphParentNode* node)

         {

             if (nodeSets.empty())

                 return;

             nodeSets.top()->insert(node);

         }

         void clear()

         {

             while (!nodeSets.empty())

                 popSet();

         }

     private:

         typedef std::stack<TParentNodeSet*> TParentNodeSetStack;

         TParentNodeSetStack nodeSets;

     };

     //

     // An instance of this class pushes a new node set when instantiated.

     // When the instance goes out of scope, it and pops the node set.

     //

     class TNodeSetMaintainer {

     public:

         TNodeSetMaintainer(TDependencyGraphBuilder* factory)

             : sets(factory->mNodeSets) { sets.pushSet(); }

         ~TNodeSetMaintainer() { sets.popSet(); }

     protected:

         TNodeSetStack& sets;

     };

     //

     // An instance of this class pushes a new node set when instantiated.

     // When the instance goes out of scope, it and pops the top node set and adds its contents to

     // the new top node set.

     //

     class TNodeSetPropagatingMaintainer {

     public:

         TNodeSetPropagatingMaintainer(TDependencyGraphBuilder* factory)

             : sets(factory->mNodeSets) { sets.pushSet(); }

         ~TNodeSetPropagatingMaintainer() { sets.popSetIntoNext(); }

     protected:

         TNodeSetStack& sets;

     };

     //

     // An instance of this class keeps track of the leftmost symbol while we're exploring an

     // assignment.

     // It will push the placeholder symbol kLeftSubtree when instantiated under a left subtree,

     // and kRightSubtree under a right subtree.

     // When it goes out of scope, it will pop the leftmost symbol at the top of the scope.

     // During traversal, the TDependencyGraphBuilder will replace kLeftSubtree with a real symbol.

     // kRightSubtree will never be replaced by a real symbol because we are tracking the leftmost

     // symbol.

     //

     class TLeftmostSymbolMaintainer {

     public:

         TLeftmostSymbolMaintainer(TDependencyGraphBuilder* factory, TGraphSymbol& subtree)

             : leftmostSymbols(factory->mLeftmostSymbols)

         {

             needsPlaceholderSymbol = leftmostSymbols.empty() || leftmostSymbols.top() != &subtree;

             if (needsPlaceholderSymbol)

                 leftmostSymbols.push(&subtree);

         }

         ~TLeftmostSymbolMaintainer()

         {

             if (needsPlaceholderSymbol)

                 leftmostSymbols.pop();

         }

     protected:

         TSymbolStack& leftmostSymbols;

         bool needsPlaceholderSymbol;

     };

     TDependencyGraphBuilder(TDependencyGraph* graph)

         : TIntermTraverser(true, false, false)

         , mLeftSubtree(NULL)

         , mRightSubtree(NULL)

         , mGraph(graph) {}

     void build(TIntermNode* intermNode) { intermNode->traverse(this); }

     void connectMultipleNodesToSingleNode(TParentNodeSet* nodes, TGraphNode* node) const;

     void visitAssignment(TIntermBinary*);

     void visitLogicalOp(TIntermBinary*);

     void visitBinaryChildren(TIntermBinary*);

     void visitFunctionDefinition(TIntermAggregate*);

     void visitFunctionCall(TIntermAggregate* intermFunctionCall);

     void visitAggregateChildren(TIntermAggregate*);

     TGraphSymbol mLeftSubtree;

     TGraphSymbol mRightSubtree;

     TDependencyGraph* mGraph;

     TNodeSetStack mNodeSets;

     TSymbolStack mLeftmostSymbols;

 };

 #endif  // COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H