zenilib: zenilib/jni/external/angle/src/compiler/depgraph/DependencyGraphBuilder.cpp 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.cpp
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 #include "compiler/depgraph/DependencyGraphBuilder.h"
8
9 void TDependencyGraphBuilder::build(TIntermNode* node, TDependencyGraph* graph)
10 {
11 TDependencyGraphBuilder builder(graph);
12 builder.build(node);
13 }
14
15 bool TDependencyGraphBuilder::visitAggregate(Visit visit, TIntermAggregate* intermAggregate)
16 {
17 switch (intermAggregate->getOp()) {
18 case EOpFunction: visitFunctionDefinition(intermAggregate); break;
19 case EOpFunctionCall: visitFunctionCall(intermAggregate); break;
20 default: visitAggregateChildren(intermAggregate); break;
21 }
22
23 return false;
24 }
25
26 void TDependencyGraphBuilder::visitFunctionDefinition(TIntermAggregate* intermAggregate)
27 {
28 // Currently, we do not support user defined functions.
29 if (intermAggregate->getName() != "main(")
30 return;
31
32 visitAggregateChildren(intermAggregate);
33 }
34
35 // Takes an expression like "f(x)" and creates a dependency graph like
36 // "x -> argument 0 -> function call".
37 void TDependencyGraphBuilder::visitFunctionCall(TIntermAggregate* intermFunctionCall)
38 {
39 TGraphFunctionCall* functionCall = mGraph->createFunctionCall(intermFunctionCall);
40
41 // Run through the function call arguments.
42 int argumentNumber = 0;
43 TIntermSequence& intermArguments = intermFunctionCall->getSequence();
44 for (TIntermSequence::const_iterator iter = intermArguments.begin();
45 iter != intermArguments.end();
46 ++iter, ++argumentNumber)
47 {
48 TNodeSetMaintainer nodeSetMaintainer(this);
49
50 TIntermNode* intermArgument = *iter;
51 intermArgument->traverse(this);
52
53 if (TParentNodeSet* argumentNodes = mNodeSets.getTopSet()) {
54 TGraphArgument* argument = mGraph->createArgument(intermFunctionCall, argumentNumber);
55 connectMultipleNodesToSingleNode(argumentNodes, argument);
56 argument->addDependentNode(functionCall);
57 }
58 }
59
60 // Push the leftmost symbol of this function call into the current set of dependent symbols to
61 // represent the result of this function call.
62 // Thus, an expression like "y = f(x)" will yield a dependency graph like
63 // "x -> argument 0 -> function call -> y".
64 // This line essentially passes the function call node back up to an earlier visitAssignment
65 // call, which will create the connection "function call -> y".
66 mNodeSets.insertIntoTopSet(functionCall);
67 }
68
69 void TDependencyGraphBuilder::visitAggregateChildren(TIntermAggregate* intermAggregate)
70 {
71 TIntermSequence& sequence = intermAggregate->getSequence();
72 for(TIntermSequence::const_iterator iter = sequence.begin(); iter != sequence.end(); ++iter)
73 {
74 TIntermNode* intermChild = *iter;
75 intermChild->traverse(this);
76 }
77 }
78
79 void TDependencyGraphBuilder::visitSymbol(TIntermSymbol* intermSymbol)
80 {
81 // Push this symbol into the set of dependent symbols for the current assignment or condition
82 // that we are traversing.
83 TGraphSymbol* symbol = mGraph->getOrCreateSymbol(intermSymbol);
84 mNodeSets.insertIntoTopSet(symbol);
85
86 // If this symbol is the current leftmost symbol under an assignment, replace the previous
87 // leftmost symbol with this symbol.
88 if (!mLeftmostSymbols.empty() && mLeftmostSymbols.top() != &mRightSubtree) {
89 mLeftmostSymbols.pop();
90 mLeftmostSymbols.push(symbol);
91 }
92 }
93
94 bool TDependencyGraphBuilder::visitBinary(Visit visit, TIntermBinary* intermBinary)
95 {
96 TOperator op = intermBinary->getOp();
97 if (op == EOpInitialize || intermBinary->modifiesState())
98 visitAssignment(intermBinary);
99 else if (op == EOpLogicalAnd || op == EOpLogicalOr)
100 visitLogicalOp(intermBinary);
101 else
102 visitBinaryChildren(intermBinary);
103
104 return false;
105 }
106
107 void TDependencyGraphBuilder::visitAssignment(TIntermBinary* intermAssignment)
108 {
109 TIntermTyped* intermLeft = intermAssignment->getLeft();
110 if (!intermLeft)
111 return;
112
113 TGraphSymbol* leftmostSymbol = NULL;
114
115 {
116 TNodeSetMaintainer nodeSetMaintainer(this);
117
118 {
119 TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mLeftSubtree);
120 intermLeft->traverse(this);
121 leftmostSymbol = mLeftmostSymbols.top();
122
123 // After traversing the left subtree of this assignment, we should have found a real
124 // leftmost symbol, and the leftmost symbol should not be a placeholder.
125 ASSERT(leftmostSymbol != &mLeftSubtree);
126 ASSERT(leftmostSymbol != &mRightSubtree);
127 }
128
129 if (TIntermTyped* intermRight = intermAssignment->getRight()) {
130 TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
131 intermRight->traverse(this);
132 }
133
134 if (TParentNodeSet* assignmentNodes = mNodeSets.getTopSet())
135 connectMultipleNodesToSingleNode(assignmentNodes, leftmostSymbol);
136 }
137
138 // Push the leftmost symbol of this assignment into the current set of dependent symbols to
139 // represent the result of this assignment.
140 // An expression like "a = (b = c)" will yield a dependency graph like "c -> b -> a".
141 // This line essentially passes the leftmost symbol of the nested assignment ("b" in this
142 // example) back up to the earlier visitAssignment call for the outer assignment, which will
143 // create the connection "b -> a".
144 mNodeSets.insertIntoTopSet(leftmostSymbol);
145 }
146
147 void TDependencyGraphBuilder::visitLogicalOp(TIntermBinary* intermLogicalOp)
148 {
149 if (TIntermTyped* intermLeft = intermLogicalOp->getLeft()) {
150 TNodeSetPropagatingMaintainer nodeSetMaintainer(this);
151
152 intermLeft->traverse(this);
153 if (TParentNodeSet* leftNodes = mNodeSets.getTopSet()) {
154 TGraphLogicalOp* logicalOp = mGraph->createLogicalOp(intermLogicalOp);
155 connectMultipleNodesToSingleNode(leftNodes, logicalOp);
156 }
157 }
158
159 if (TIntermTyped* intermRight = intermLogicalOp->getRight()) {
160 TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
161 intermRight->traverse(this);
162 }
163 }
164
165 void TDependencyGraphBuilder::visitBinaryChildren(TIntermBinary* intermBinary)
166 {
167 if (TIntermTyped* intermLeft = intermBinary->getLeft())
168 intermLeft->traverse(this);
169
170 if (TIntermTyped* intermRight = intermBinary->getRight()) {
171 TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, mRightSubtree);
172 intermRight->traverse(this);
173 }
174 }
175
176 bool TDependencyGraphBuilder::visitSelection(Visit visit, TIntermSelection* intermSelection)
177 {
178 if (TIntermNode* intermCondition = intermSelection->getCondition()) {
179 TNodeSetMaintainer nodeSetMaintainer(this);
180
181 intermCondition->traverse(this);
182 if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) {
183 TGraphSelection* selection = mGraph->createSelection(intermSelection);
184 connectMultipleNodesToSingleNode(conditionNodes, selection);
185 }
186 }
187
188 if (TIntermNode* intermTrueBlock = intermSelection->getTrueBlock())
189 intermTrueBlock->traverse(this);
190
191 if (TIntermNode* intermFalseBlock = intermSelection->getFalseBlock())
192 intermFalseBlock->traverse(this);
193
194 return false;
195 }
196
197 bool TDependencyGraphBuilder::visitLoop(Visit visit, TIntermLoop* intermLoop)
198 {
199 if (TIntermTyped* intermCondition = intermLoop->getCondition()) {
200 TNodeSetMaintainer nodeSetMaintainer(this);
201
202 intermCondition->traverse(this);
203 if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) {
204 TGraphLoop* loop = mGraph->createLoop(intermLoop);
205 connectMultipleNodesToSingleNode(conditionNodes, loop);
206 }
207 }
208
209 if (TIntermNode* intermBody = intermLoop->getBody())
210 intermBody->traverse(this);
211
212 if (TIntermTyped* intermExpression = intermLoop->getExpression())
213 intermExpression->traverse(this);
214
215 return false;
216 }
217
218
219 void TDependencyGraphBuilder::connectMultipleNodesToSingleNode(TParentNodeSet* nodes,
220 TGraphNode* node) const
221 {
222 for (TParentNodeSet::const_iterator iter = nodes->begin(); iter != nodes->end(); ++iter)
223 {
224 TGraphParentNode* currentNode = *iter;
225 currentNode->addDependentNode(node);
226 }
227 }
TOperator
TOperator
Definition: intermediate.h:29
Visit
Visit
Definition: intermediate.h:524
TIntermOperator::getOp
TOperator getOp() const
Definition: intermediate.h:389
EOpFunctionCall
Definition: intermediate.h:32
TDependencyGraphBuilder::visitLoop
virtual bool visitLoop(Visit visit, TIntermLoop *)
Definition: DependencyGraphBuilder.cpp:197
TIntermAggregate::getSequence
TIntermSequence & getSequence()
Definition: intermediate.h:469
TIntermSelection::getTrueBlock
TIntermNode * getTrueBlock() const
Definition: intermediate.h:514
TIntermLoop::getCondition
TIntermTyped * getCondition()
Definition: intermediate.h:301
EOpLogicalOr
Definition: intermediate.h:82
TIntermBinary::getLeft
TIntermTyped * getLeft() const
Definition: intermediate.h:413
NULL
#define NULL
Definition: ftobjs.h:61
TDependencyGraphBuilder
Definition: DependencyGraphBuilder.h:16
TDependencyGraphBuilder::visitBinary
virtual bool visitBinary(Visit visit, TIntermBinary *)
Definition: DependencyGraphBuilder.cpp:94
EOpInitialize
Definition: intermediate.h:179
TGraphArgument
Definition: DependencyGraph.h:59
TIntermSelection::getFalseBlock
TIntermNode * getFalseBlock() const
Definition: intermediate.h:515
TIntermBinary::getRight
TIntermTyped * getRight() const
Definition: intermediate.h:414
TDependencyGraph::getOrCreateSymbol
TGraphSymbol * getOrCreateSymbol(TIntermSymbol *intermSymbol)
Definition: DependencyGraph.cpp:43
TIntermTyped
Definition: intermediate.h:245
TGraphParentNode::addDependentNode
void addDependentNode(TGraphNode *node)
Definition: DependencyGraph.h:50
TDependencyGraph::createArgument
TGraphArgument * createArgument(TIntermAggregate *intermFunctionCall, int argumentNumber)
Definition: DependencyGraph.cpp:26
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
TGraphSelection
Definition: DependencyGraph.h:98
TIntermSelection
Definition: intermediate.h:503
TGraphSymbol
Definition: DependencyGraph.h:87
ASSERT
#define ASSERT(expression)
Definition: debug.h:36
TGraphLogicalOp
Definition: DependencyGraph.h:120
EOpFunction
Definition: intermediate.h:33
TIntermNode::traverse
virtual void traverse(TIntermTraverser *)=0
TIntermSelection::getCondition
TIntermNode * getCondition() const
Definition: intermediate.h:513
TIntermLoop::getBody
TIntermNode * getBody()
Definition: intermediate.h:303
TGraphLoop
Definition: DependencyGraph.h:109
TIntermAggregate::getName
const TString & getName() const
Definition: intermediate.h:472
TDependencyGraph
Definition: DependencyGraph.h:139
TGraphNode
Definition: DependencyGraph.h:34
TDependencyGraph::createLoop
TGraphLoop * createLoop(TIntermLoop *intermLoop)
Definition: DependencyGraph.cpp:74
DependencyGraphBuilder.h
TGraphFunctionCall
Definition: DependencyGraph.h:75
TIntermSymbol
Definition: intermediate.h:340
TIntermLoop
Definition: intermediate.h:284
EOpLogicalAnd
Definition: intermediate.h:84
TIntermLoop::getExpression
TIntermTyped * getExpression()
Definition: intermediate.h:302
TDependencyGraph::createFunctionCall
TGraphFunctionCall * createFunctionCall(TIntermAggregate *intermFunctionCall)
Definition: DependencyGraph.cpp:34
TVector< TIntermNode * >
TIntermNode
Definition: intermediate.h:206
TDependencyGraph::createSelection
TGraphSelection * createSelection(TIntermSelection *intermSelection)
Definition: DependencyGraph.cpp:67
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
TIntermOperator::modifiesState
bool modifiesState() const
Definition: Intermediate.cpp:750
TDependencyGraph::createLogicalOp
TGraphLogicalOp * createLogicalOp(TIntermBinary *intermLogicalOp)
Definition: DependencyGraph.cpp:81