michael@0: //
michael@0: // Copyright (c) 2012 The ANGLE Project Authors. All rights reserved.
michael@0: // Use of this source code is governed by a BSD-style license that can be
michael@0: // found in the LICENSE file.
michael@0: //
michael@0: 
michael@0: #ifndef COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
michael@0: #define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
michael@0: 
michael@0: #include "compiler/depgraph/DependencyGraph.h"
michael@0: 
michael@0: //
michael@0: // Creates a dependency graph of symbols, function calls, conditions etc. by traversing a
michael@0: // intermediate tree.
michael@0: //
michael@0: class TDependencyGraphBuilder : public TIntermTraverser {
michael@0: public:
michael@0:     static void build(TIntermNode* node, TDependencyGraph* graph);
michael@0: 
michael@0:     virtual void visitSymbol(TIntermSymbol*);
michael@0:     virtual bool visitBinary(Visit visit, TIntermBinary*);
michael@0:     virtual bool visitSelection(Visit visit, TIntermSelection*);
michael@0:     virtual bool visitAggregate(Visit visit, TIntermAggregate*);
michael@0:     virtual bool visitLoop(Visit visit, TIntermLoop*);
michael@0: 
michael@0: private:
michael@0:     typedef std::stack<TGraphSymbol*> TSymbolStack;
michael@0:     typedef std::set<TGraphParentNode*> TParentNodeSet;
michael@0: 
michael@0:     //
michael@0:     // For collecting the dependent nodes of assignments, conditions, etc.
michael@0:     // while traversing the intermediate tree.
michael@0:     //
michael@0:     // This data structure is stack of sets. Each set contains dependency graph parent nodes.
michael@0:     //
michael@0:     class TNodeSetStack {
michael@0:     public:
michael@0:         TNodeSetStack() {};
michael@0:         ~TNodeSetStack() { clear(); }
michael@0: 
michael@0:         // This should only be called after a pushSet.
michael@0:         // Returns NULL if the top set is empty.
michael@0:         TParentNodeSet* getTopSet() const
michael@0:         {
michael@0:             ASSERT(!nodeSets.empty());
michael@0:             TParentNodeSet* topSet = nodeSets.top();
michael@0:             return !topSet->empty() ? topSet : NULL;
michael@0:         }
michael@0: 
michael@0:         void pushSet() { nodeSets.push(new TParentNodeSet()); }
michael@0:         void popSet()
michael@0:         {
michael@0:             ASSERT(!nodeSets.empty());
michael@0:             delete nodeSets.top();
michael@0:             nodeSets.pop();
michael@0:         }
michael@0: 
michael@0:         // Pops the top set and adds its contents to the new top set.
michael@0:         // This should only be called after a pushSet.
michael@0:         // If there is no set below the top set, the top set is just deleted.
michael@0:         void popSetIntoNext()
michael@0:         {
michael@0:             ASSERT(!nodeSets.empty());
michael@0:             TParentNodeSet* oldTopSet = nodeSets.top();
michael@0:             nodeSets.pop();
michael@0: 
michael@0:             if (!nodeSets.empty()) {
michael@0:                 TParentNodeSet* newTopSet = nodeSets.top();
michael@0:                 newTopSet->insert(oldTopSet->begin(), oldTopSet->end());
michael@0:             }
michael@0: 
michael@0:             delete oldTopSet;
michael@0:         }
michael@0: 
michael@0:         // Does nothing if there is no top set.
michael@0:         // This can be called when there is no top set if we are visiting
michael@0:         // symbols that are not under an assignment or condition.
michael@0:         // We don't need to track those symbols.
michael@0:         void insertIntoTopSet(TGraphParentNode* node)
michael@0:         {
michael@0:             if (nodeSets.empty())
michael@0:                 return;
michael@0: 
michael@0:             nodeSets.top()->insert(node);
michael@0:         }
michael@0: 
michael@0:         void clear()
michael@0:         {
michael@0:             while (!nodeSets.empty())
michael@0:                 popSet();
michael@0:         }
michael@0: 
michael@0:     private:
michael@0:         typedef std::stack<TParentNodeSet*> TParentNodeSetStack;
michael@0: 
michael@0:         TParentNodeSetStack nodeSets;
michael@0:     };
michael@0: 
michael@0:     //
michael@0:     // An instance of this class pushes a new node set when instantiated.
michael@0:     // When the instance goes out of scope, it and pops the node set.
michael@0:     //
michael@0:     class TNodeSetMaintainer {
michael@0:     public:
michael@0:         TNodeSetMaintainer(TDependencyGraphBuilder* factory)
michael@0:             : sets(factory->mNodeSets) { sets.pushSet(); }
michael@0:         ~TNodeSetMaintainer() { sets.popSet(); }
michael@0:     protected:
michael@0:         TNodeSetStack& sets;
michael@0:     };
michael@0: 
michael@0:     //
michael@0:     // An instance of this class pushes a new node set when instantiated.
michael@0:     // When the instance goes out of scope, it and pops the top node set and adds its contents to
michael@0:     // the new top node set.
michael@0:     //
michael@0:     class TNodeSetPropagatingMaintainer {
michael@0:     public:
michael@0:         TNodeSetPropagatingMaintainer(TDependencyGraphBuilder* factory)
michael@0:             : sets(factory->mNodeSets) { sets.pushSet(); }
michael@0:         ~TNodeSetPropagatingMaintainer() { sets.popSetIntoNext(); }
michael@0:     protected:
michael@0:         TNodeSetStack& sets;
michael@0:     };
michael@0: 
michael@0:     //
michael@0:     // An instance of this class keeps track of the leftmost symbol while we're exploring an
michael@0:     // assignment.
michael@0:     // It will push the placeholder symbol kLeftSubtree when instantiated under a left subtree,
michael@0:     // and kRightSubtree under a right subtree.
michael@0:     // When it goes out of scope, it will pop the leftmost symbol at the top of the scope.
michael@0:     // During traversal, the TDependencyGraphBuilder will replace kLeftSubtree with a real symbol.
michael@0:     // kRightSubtree will never be replaced by a real symbol because we are tracking the leftmost
michael@0:     // symbol.
michael@0:     //
michael@0:     class TLeftmostSymbolMaintainer {
michael@0:     public:
michael@0:         TLeftmostSymbolMaintainer(TDependencyGraphBuilder* factory, TGraphSymbol& subtree)
michael@0:             : leftmostSymbols(factory->mLeftmostSymbols)
michael@0:         {
michael@0:             needsPlaceholderSymbol = leftmostSymbols.empty() || leftmostSymbols.top() != &subtree;
michael@0:             if (needsPlaceholderSymbol)
michael@0:                 leftmostSymbols.push(&subtree);
michael@0:         }
michael@0: 
michael@0:         ~TLeftmostSymbolMaintainer()
michael@0:         {
michael@0:             if (needsPlaceholderSymbol)
michael@0:                 leftmostSymbols.pop();
michael@0:         }
michael@0: 
michael@0:     protected:
michael@0:         TSymbolStack& leftmostSymbols;
michael@0:         bool needsPlaceholderSymbol;
michael@0:     };
michael@0: 
michael@0:     TDependencyGraphBuilder(TDependencyGraph* graph)
michael@0:         : TIntermTraverser(true, false, false)
michael@0:         , mLeftSubtree(NULL)
michael@0:         , mRightSubtree(NULL)
michael@0:         , mGraph(graph) {}
michael@0:     void build(TIntermNode* intermNode) { intermNode->traverse(this); }
michael@0: 
michael@0:     void connectMultipleNodesToSingleNode(TParentNodeSet* nodes, TGraphNode* node) const;
michael@0: 
michael@0:     void visitAssignment(TIntermBinary*);
michael@0:     void visitLogicalOp(TIntermBinary*);
michael@0:     void visitBinaryChildren(TIntermBinary*);
michael@0:     void visitFunctionDefinition(TIntermAggregate*);
michael@0:     void visitFunctionCall(TIntermAggregate* intermFunctionCall);
michael@0:     void visitAggregateChildren(TIntermAggregate*);
michael@0: 
michael@0:     TGraphSymbol mLeftSubtree;
michael@0:     TGraphSymbol mRightSubtree;
michael@0: 
michael@0:     TDependencyGraph* mGraph;
michael@0:     TNodeSetStack mNodeSets;
michael@0:     TSymbolStack mLeftmostSymbols;
michael@0: };
michael@0: 
michael@0: #endif  // COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H