diff options
Diffstat (limited to 'src/3rdparty/angle/src/compiler/depgraph/DependencyGraphBuilder.h')
-rw-r--r-- | src/3rdparty/angle/src/compiler/depgraph/DependencyGraphBuilder.h | 181 |
1 files changed, 181 insertions, 0 deletions
diff --git a/src/3rdparty/angle/src/compiler/depgraph/DependencyGraphBuilder.h b/src/3rdparty/angle/src/compiler/depgraph/DependencyGraphBuilder.h new file mode 100644 index 0000000000..c5f232cb21 --- /dev/null +++ b/src/3rdparty/angle/src/compiler/depgraph/DependencyGraphBuilder.h @@ -0,0 +1,181 @@ +// +// 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 |