summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/angle/src/compiler/depgraph/DependencyGraphBuilder.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/3rdparty/angle/src/compiler/depgraph/DependencyGraphBuilder.h')
-rw-r--r--src/3rdparty/angle/src/compiler/depgraph/DependencyGraphBuilder.h181
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