zenilib: zenilib/jni/external/angle/src/compiler/depgraph/DependencyGraphBuilder.h Source File

zenilib 0.5.3.0

- Main Page
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
DependencyGraphBuilder.h
Go to the documentation of this file.
1 //
2 // Copyright (c) 2012 The ANGLE Project Authors. All rights reserved.
3 // Use of this source code is governed by a BSD-style license that can be
4 // found in the LICENSE file.
5 //
6
7 #ifndef COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
8 #define COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
9
10 #include "compiler/depgraph/DependencyGraph.h"
11
12 //
13 // Creates a dependency graph of symbols, function calls, conditions etc. by traversing a
14 // intermediate tree.
15 //
16 class TDependencyGraphBuilder : public TIntermTraverser {
17 public:
18 static void build(TIntermNode* node, TDependencyGraph* graph);
19
20 virtual void visitSymbol(TIntermSymbol*);
21 virtual bool visitBinary(Visit visit, TIntermBinary*);
22 virtual bool visitSelection(Visit visit, TIntermSelection*);
23 virtual bool visitAggregate(Visit visit, TIntermAggregate*);
24 virtual bool visitLoop(Visit visit, TIntermLoop*);
25
26 private:
27 typedef std::stack<TGraphSymbol*> TSymbolStack;
28 typedef std::set<TGraphParentNode*> TParentNodeSet;
29
30 //
31 // For collecting the dependent nodes of assignments, conditions, etc.
32 // while traversing the intermediate tree.
33 //
34 // This data structure is stack of sets. Each set contains dependency graph parent nodes.
35 //
36 class TNodeSetStack {
37 public:
38 TNodeSetStack() {};
39 ~TNodeSetStack() { clear(); }
40
41 // This should only be called after a pushSet.
42 // Returns NULL if the top set is empty.
43 TParentNodeSet* getTopSet() const
44 {
45 ASSERT(!nodeSets.empty());
46 TParentNodeSet* topSet = nodeSets.top();
47 return !topSet->empty() ? topSet : NULL;
48 }
49
50 void pushSet() { nodeSets.push(new TParentNodeSet()); }
51 void popSet()
52 {
53 ASSERT(!nodeSets.empty());
54 delete nodeSets.top();
55 nodeSets.pop();
56 }
57
58 // Pops the top set and adds its contents to the new top set.
59 // This should only be called after a pushSet.
60 // If there is no set below the top set, the top set is just deleted.
61 void popSetIntoNext()
62 {
63 ASSERT(!nodeSets.empty());
64 TParentNodeSet* oldTopSet = nodeSets.top();
65 nodeSets.pop();
66
67 if (!nodeSets.empty()) {
68 TParentNodeSet* newTopSet = nodeSets.top();
69 newTopSet->insert(oldTopSet->begin(), oldTopSet->end());
70 }
71
72 delete oldTopSet;
73 }
74
75 // Does nothing if there is no top set.
76 // This can be called when there is no top set if we are visiting
77 // symbols that are not under an assignment or condition.
78 // We don't need to track those symbols.
79 void insertIntoTopSet(TGraphParentNode* node)
80 {
81 if (nodeSets.empty())
82 return;
83
84 nodeSets.top()->insert(node);
85 }
86
87 void clear()
88 {
89 while (!nodeSets.empty())
90 popSet();
91 }
92
93 private:
94 typedef std::stack<TParentNodeSet*> TParentNodeSetStack;
95
96 TParentNodeSetStack nodeSets;
97 };
98
99 //
100 // An instance of this class pushes a new node set when instantiated.
101 // When the instance goes out of scope, it and pops the node set.
102 //
103 class TNodeSetMaintainer {
104 public:
105 TNodeSetMaintainer(TDependencyGraphBuilder* factory)
106 : sets(factory->mNodeSets) { sets.pushSet(); }
107 ~TNodeSetMaintainer() { sets.popSet(); }
108 protected:
109 TNodeSetStack& sets;
110 };
111
112 //
113 // An instance of this class pushes a new node set when instantiated.
114 // When the instance goes out of scope, it and pops the top node set and adds its contents to
115 // the new top node set.
116 //
117 class TNodeSetPropagatingMaintainer {
118 public:
119 TNodeSetPropagatingMaintainer(TDependencyGraphBuilder* factory)
120 : sets(factory->mNodeSets) { sets.pushSet(); }
121 ~TNodeSetPropagatingMaintainer() { sets.popSetIntoNext(); }
122 protected:
123 TNodeSetStack& sets;
124 };
125
126 //
127 // An instance of this class keeps track of the leftmost symbol while we're exploring an
128 // assignment.
129 // It will push the placeholder symbol kLeftSubtree when instantiated under a left subtree,
130 // and kRightSubtree under a right subtree.
131 // When it goes out of scope, it will pop the leftmost symbol at the top of the scope.
132 // During traversal, the TDependencyGraphBuilder will replace kLeftSubtree with a real symbol.
133 // kRightSubtree will never be replaced by a real symbol because we are tracking the leftmost
134 // symbol.
135 //
136 class TLeftmostSymbolMaintainer {
137 public:
138 TLeftmostSymbolMaintainer(TDependencyGraphBuilder* factory, TGraphSymbol& subtree)
139 : leftmostSymbols(factory->mLeftmostSymbols)
140 {
141 needsPlaceholderSymbol = leftmostSymbols.empty() || leftmostSymbols.top() != &subtree;
142 if (needsPlaceholderSymbol)
143 leftmostSymbols.push(&subtree);
144 }
145
146 ~TLeftmostSymbolMaintainer()
147 {
148 if (needsPlaceholderSymbol)
149 leftmostSymbols.pop();
150 }
151
152 protected:
153 TSymbolStack& leftmostSymbols;
154 bool needsPlaceholderSymbol;
155 };
156
157 TDependencyGraphBuilder(TDependencyGraph* graph)
158 : TIntermTraverser(true, false, false)
159 , mLeftSubtree(NULL)
160 , mRightSubtree(NULL)
161 , mGraph(graph) {}
162 void build(TIntermNode* intermNode) { intermNode->traverse(this); }
163
164 void connectMultipleNodesToSingleNode(TParentNodeSet* nodes, TGraphNode* node) const;
165
166 void visitAssignment(TIntermBinary*);
167 void visitLogicalOp(TIntermBinary*);
168 void visitBinaryChildren(TIntermBinary*);
169 void visitFunctionDefinition(TIntermAggregate*);
170 void visitFunctionCall(TIntermAggregate* intermFunctionCall);
171 void visitAggregateChildren(TIntermAggregate*);
172
173 TGraphSymbol mLeftSubtree;
174 TGraphSymbol mRightSubtree;
175
176 TDependencyGraph* mGraph;
177 TNodeSetStack mNodeSets;
178 TSymbolStack mLeftmostSymbols;
179 };
180
181 #endif // COMPILER_DEPGRAPH_DEPENDENCY_GRAPH_BUILDER_H
Visit
Visit
Definition: intermediate.h:524
TDependencyGraphBuilder::visitLoop
virtual bool visitLoop(Visit visit, TIntermLoop *)
Definition: DependencyGraphBuilder.cpp:197
NULL
#define NULL
Definition: ftobjs.h:61
TDependencyGraphBuilder
Definition: DependencyGraphBuilder.h:16
TDependencyGraphBuilder::visitBinary
virtual bool visitBinary(Visit visit, TIntermBinary *)
Definition: DependencyGraphBuilder.cpp:94
TIntermTraverser::TIntermTraverser
TIntermTraverser(bool preVisit=true, bool inVisit=false, bool postVisit=false, bool rightToLeft=false)
Definition: intermediate.h:543
TDependencyGraphBuilder::visitAggregate
virtual bool visitAggregate(Visit visit, TIntermAggregate *)
Definition: DependencyGraphBuilder.cpp:15
TGraphParentNode
Definition: DependencyGraph.h:46
TIntermAggregate
Definition: intermediate.h:460
TIntermBinary
Definition: intermediate.h:404
TIntermSelection
Definition: intermediate.h:503
TGraphSymbol
Definition: DependencyGraph.h:87
DependencyGraph.h
ASSERT
#define ASSERT(expression)
Definition: debug.h:36
TIntermNode::traverse
virtual void traverse(TIntermTraverser *)=0
TDependencyGraph
Definition: DependencyGraph.h:139
TIntermTraverser
Definition: intermediate.h:539
TGraphNode
Definition: DependencyGraph.h:34
TIntermSymbol
Definition: intermediate.h:340
TIntermLoop
Definition: intermediate.h:284
TIntermNode
Definition: intermediate.h:206
TDependencyGraphBuilder::build
static void build(TIntermNode *node, TDependencyGraph *graph)
Definition: DependencyGraphBuilder.cpp:9
TDependencyGraphBuilder::visitSymbol
virtual void visitSymbol(TIntermSymbol *)
Definition: DependencyGraphBuilder.cpp:79
TDependencyGraphBuilder::visitSelection
virtual bool visitSelection(Visit visit, TIntermSelection *)
Definition: DependencyGraphBuilder.cpp:176