1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/angle/src/compiler/depgraph/DependencyGraphBuilder.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,181 @@
1.4 +//
1.5 +// Copyright (c) 2012 The ANGLE Project Authors. All rights reserved.
1.6 +// Use of this source code is governed by a BSD-style license that can be
1.7 +// found in the LICENSE file.
1.8 +//
1.9 +
1.10 +#ifndef COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
1.11 +#define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
1.12 +
1.13 +#include "compiler/depgraph/DependencyGraph.h"
1.14 +
1.15 +//
1.16 +// Creates a dependency graph of symbols, function calls, conditions etc. by traversing a
1.17 +// intermediate tree.
1.18 +//
1.19 +class TDependencyGraphBuilder : public TIntermTraverser {
1.20 +public:
1.21 + static void build(TIntermNode* node, TDependencyGraph* graph);
1.22 +
1.23 + virtual void visitSymbol(TIntermSymbol*);
1.24 + virtual bool visitBinary(Visit visit, TIntermBinary*);
1.25 + virtual bool visitSelection(Visit visit, TIntermSelection*);
1.26 + virtual bool visitAggregate(Visit visit, TIntermAggregate*);
1.27 + virtual bool visitLoop(Visit visit, TIntermLoop*);
1.28 +
1.29 +private:
1.30 + typedef std::stack<TGraphSymbol*> TSymbolStack;
1.31 + typedef std::set<TGraphParentNode*> TParentNodeSet;
1.32 +
1.33 + //
1.34 + // For collecting the dependent nodes of assignments, conditions, etc.
1.35 + // while traversing the intermediate tree.
1.36 + //
1.37 + // This data structure is stack of sets. Each set contains dependency graph parent nodes.
1.38 + //
1.39 + class TNodeSetStack {
1.40 + public:
1.41 + TNodeSetStack() {};
1.42 + ~TNodeSetStack() { clear(); }
1.43 +
1.44 + // This should only be called after a pushSet.
1.45 + // Returns NULL if the top set is empty.
1.46 + TParentNodeSet* getTopSet() const
1.47 + {
1.48 + ASSERT(!nodeSets.empty());
1.49 + TParentNodeSet* topSet = nodeSets.top();
1.50 + return !topSet->empty() ? topSet : NULL;
1.51 + }
1.52 +
1.53 + void pushSet() { nodeSets.push(new TParentNodeSet()); }
1.54 + void popSet()
1.55 + {
1.56 + ASSERT(!nodeSets.empty());
1.57 + delete nodeSets.top();
1.58 + nodeSets.pop();
1.59 + }
1.60 +
1.61 + // Pops the top set and adds its contents to the new top set.
1.62 + // This should only be called after a pushSet.
1.63 + // If there is no set below the top set, the top set is just deleted.
1.64 + void popSetIntoNext()
1.65 + {
1.66 + ASSERT(!nodeSets.empty());
1.67 + TParentNodeSet* oldTopSet = nodeSets.top();
1.68 + nodeSets.pop();
1.69 +
1.70 + if (!nodeSets.empty()) {
1.71 + TParentNodeSet* newTopSet = nodeSets.top();
1.72 + newTopSet->insert(oldTopSet->begin(), oldTopSet->end());
1.73 + }
1.74 +
1.75 + delete oldTopSet;
1.76 + }
1.77 +
1.78 + // Does nothing if there is no top set.
1.79 + // This can be called when there is no top set if we are visiting
1.80 + // symbols that are not under an assignment or condition.
1.81 + // We don't need to track those symbols.
1.82 + void insertIntoTopSet(TGraphParentNode* node)
1.83 + {
1.84 + if (nodeSets.empty())
1.85 + return;
1.86 +
1.87 + nodeSets.top()->insert(node);
1.88 + }
1.89 +
1.90 + void clear()
1.91 + {
1.92 + while (!nodeSets.empty())
1.93 + popSet();
1.94 + }
1.95 +
1.96 + private:
1.97 + typedef std::stack<TParentNodeSet*> TParentNodeSetStack;
1.98 +
1.99 + TParentNodeSetStack nodeSets;
1.100 + };
1.101 +
1.102 + //
1.103 + // An instance of this class pushes a new node set when instantiated.
1.104 + // When the instance goes out of scope, it and pops the node set.
1.105 + //
1.106 + class TNodeSetMaintainer {
1.107 + public:
1.108 + TNodeSetMaintainer(TDependencyGraphBuilder* factory)
1.109 + : sets(factory->mNodeSets) { sets.pushSet(); }
1.110 + ~TNodeSetMaintainer() { sets.popSet(); }
1.111 + protected:
1.112 + TNodeSetStack& sets;
1.113 + };
1.114 +
1.115 + //
1.116 + // An instance of this class pushes a new node set when instantiated.
1.117 + // When the instance goes out of scope, it and pops the top node set and adds its contents to
1.118 + // the new top node set.
1.119 + //
1.120 + class TNodeSetPropagatingMaintainer {
1.121 + public:
1.122 + TNodeSetPropagatingMaintainer(TDependencyGraphBuilder* factory)
1.123 + : sets(factory->mNodeSets) { sets.pushSet(); }
1.124 + ~TNodeSetPropagatingMaintainer() { sets.popSetIntoNext(); }
1.125 + protected:
1.126 + TNodeSetStack& sets;
1.127 + };
1.128 +
1.129 + //
1.130 + // An instance of this class keeps track of the leftmost symbol while we're exploring an
1.131 + // assignment.
1.132 + // It will push the placeholder symbol kLeftSubtree when instantiated under a left subtree,
1.133 + // and kRightSubtree under a right subtree.
1.134 + // When it goes out of scope, it will pop the leftmost symbol at the top of the scope.
1.135 + // During traversal, the TDependencyGraphBuilder will replace kLeftSubtree with a real symbol.
1.136 + // kRightSubtree will never be replaced by a real symbol because we are tracking the leftmost
1.137 + // symbol.
1.138 + //
1.139 + class TLeftmostSymbolMaintainer {
1.140 + public:
1.141 + TLeftmostSymbolMaintainer(TDependencyGraphBuilder* factory, TGraphSymbol& subtree)
1.142 + : leftmostSymbols(factory->mLeftmostSymbols)
1.143 + {
1.144 + needsPlaceholderSymbol = leftmostSymbols.empty() || leftmostSymbols.top() != &subtree;
1.145 + if (needsPlaceholderSymbol)
1.146 + leftmostSymbols.push(&subtree);
1.147 + }
1.148 +
1.149 + ~TLeftmostSymbolMaintainer()
1.150 + {
1.151 + if (needsPlaceholderSymbol)
1.152 + leftmostSymbols.pop();
1.153 + }
1.154 +
1.155 + protected:
1.156 + TSymbolStack& leftmostSymbols;
1.157 + bool needsPlaceholderSymbol;
1.158 + };
1.159 +
1.160 + TDependencyGraphBuilder(TDependencyGraph* graph)
1.161 + : TIntermTraverser(true, false, false)
1.162 + , mLeftSubtree(NULL)
1.163 + , mRightSubtree(NULL)
1.164 + , mGraph(graph) {}
1.165 + void build(TIntermNode* intermNode) { intermNode->traverse(this); }
1.166 +
1.167 + void connectMultipleNodesToSingleNode(TParentNodeSet* nodes, TGraphNode* node) const;
1.168 +
1.169 + void visitAssignment(TIntermBinary*);
1.170 + void visitLogicalOp(TIntermBinary*);
1.171 + void visitBinaryChildren(TIntermBinary*);
1.172 + void visitFunctionDefinition(TIntermAggregate*);
1.173 + void visitFunctionCall(TIntermAggregate* intermFunctionCall);
1.174 + void visitAggregateChildren(TIntermAggregate*);
1.175 +
1.176 + TGraphSymbol mLeftSubtree;
1.177 + TGraphSymbol mRightSubtree;
1.178 +
1.179 + TDependencyGraph* mGraph;
1.180 + TNodeSetStack mNodeSets;
1.181 + TSymbolStack mLeftmostSymbols;
1.182 +};
1.183 +
1.184 +#endif // COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
