1 //
2 // Copyright (c) 2016 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 // SimplifyLoopConditions is an AST traverser that converts loop conditions and loop expressions
7 // to regular statements inside the loop. This way further transformations that generate statements
8 // from loop conditions and loop expressions work correctly.
9 //
10
11 #include "compiler/translator/SimplifyLoopConditions.h"
12
13 #include "compiler/translator/IntermNodePatternMatcher.h"
14 #include "compiler/translator/IntermNode_util.h"
15 #include "compiler/translator/IntermTraverse.h"
16
17 namespace sh
18 {
19
20 namespace
21 {
22
23 class SimplifyLoopConditionsTraverser : public TLValueTrackingTraverser
24 {
25 public:
26 SimplifyLoopConditionsTraverser(unsigned int conditionsToSimplifyMask,
27 TSymbolTable *symbolTable,
28 int shaderVersion);
29
30 void traverseLoop(TIntermLoop *node) override;
31
32 bool visitUnary(Visit visit, TIntermUnary *node) override;
33 bool visitBinary(Visit visit, TIntermBinary *node) override;
34 bool visitAggregate(Visit visit, TIntermAggregate *node) override;
35 bool visitTernary(Visit visit, TIntermTernary *node) override;
36 bool visitDeclaration(Visit visit, TIntermDeclaration *node) override;
37
foundLoopToChange() const38 bool foundLoopToChange() const { return mFoundLoopToChange; }
39
40 protected:
41 // Marked to true once an operation that needs to be hoisted out of a loop expression has been
42 // found.
43 bool mFoundLoopToChange;
44 bool mInsideLoopInitConditionOrExpression;
45 IntermNodePatternMatcher mConditionsToSimplify;
46 };
47
SimplifyLoopConditionsTraverser(unsigned int conditionsToSimplifyMask,TSymbolTable * symbolTable,int shaderVersion)48 SimplifyLoopConditionsTraverser::SimplifyLoopConditionsTraverser(
49 unsigned int conditionsToSimplifyMask,
50 TSymbolTable *symbolTable,
51 int shaderVersion)
52 : TLValueTrackingTraverser(true, false, false, symbolTable, shaderVersion),
53 mFoundLoopToChange(false),
54 mInsideLoopInitConditionOrExpression(false),
55 mConditionsToSimplify(conditionsToSimplifyMask)
56 {
57 }
58
59 // If we're inside a loop initialization, condition, or expression, we check for expressions that
60 // should be moved out of the loop condition or expression. If one is found, the loop is
61 // transformed.
62 // If we're not inside loop initialization, condition, or expression, we only need to traverse nodes
63 // that may contain loops.
64
visitUnary(Visit visit,TIntermUnary * node)65 bool SimplifyLoopConditionsTraverser::visitUnary(Visit visit, TIntermUnary *node)
66 {
67 if (!mInsideLoopInitConditionOrExpression)
68 return false;
69
70 if (mFoundLoopToChange)
71 return false; // Already decided to change this loop.
72
73 mFoundLoopToChange = mConditionsToSimplify.match(node);
74 return !mFoundLoopToChange;
75 }
76
visitBinary(Visit visit,TIntermBinary * node)77 bool SimplifyLoopConditionsTraverser::visitBinary(Visit visit, TIntermBinary *node)
78 {
79 if (!mInsideLoopInitConditionOrExpression)
80 return false;
81
82 if (mFoundLoopToChange)
83 return false; // Already decided to change this loop.
84
85 mFoundLoopToChange = mConditionsToSimplify.match(node, getParentNode(), isLValueRequiredHere());
86 return !mFoundLoopToChange;
87 }
88
visitAggregate(Visit visit,TIntermAggregate * node)89 bool SimplifyLoopConditionsTraverser::visitAggregate(Visit visit, TIntermAggregate *node)
90 {
91 if (!mInsideLoopInitConditionOrExpression)
92 return false;
93
94 if (mFoundLoopToChange)
95 return false; // Already decided to change this loop.
96
97 mFoundLoopToChange = mConditionsToSimplify.match(node, getParentNode());
98 return !mFoundLoopToChange;
99 }
100
visitTernary(Visit visit,TIntermTernary * node)101 bool SimplifyLoopConditionsTraverser::visitTernary(Visit visit, TIntermTernary *node)
102 {
103 if (!mInsideLoopInitConditionOrExpression)
104 return false;
105
106 if (mFoundLoopToChange)
107 return false; // Already decided to change this loop.
108
109 mFoundLoopToChange = mConditionsToSimplify.match(node);
110 return !mFoundLoopToChange;
111 }
112
visitDeclaration(Visit visit,TIntermDeclaration * node)113 bool SimplifyLoopConditionsTraverser::visitDeclaration(Visit visit, TIntermDeclaration *node)
114 {
115 if (!mInsideLoopInitConditionOrExpression)
116 return false;
117
118 if (mFoundLoopToChange)
119 return false; // Already decided to change this loop.
120
121 mFoundLoopToChange = mConditionsToSimplify.match(node);
122 return !mFoundLoopToChange;
123 }
124
traverseLoop(TIntermLoop * node)125 void SimplifyLoopConditionsTraverser::traverseLoop(TIntermLoop *node)
126 {
127 // Mark that we're inside a loop condition or expression, and determine if the loop needs to be
128 // transformed.
129
130 ScopedNodeInTraversalPath addToPath(this, node);
131
132 mInsideLoopInitConditionOrExpression = true;
133 mFoundLoopToChange = false;
134
135 if (!mFoundLoopToChange && node->getInit())
136 {
137 node->getInit()->traverse(this);
138 }
139
140 if (!mFoundLoopToChange && node->getCondition())
141 {
142 node->getCondition()->traverse(this);
143 }
144
145 if (!mFoundLoopToChange && node->getExpression())
146 {
147 node->getExpression()->traverse(this);
148 }
149
150 mInsideLoopInitConditionOrExpression = false;
151
152 if (mFoundLoopToChange)
153 {
154 nextTemporaryId();
155
156 // Replace the loop condition with a boolean variable that's updated on each iteration.
157 TLoopType loopType = node->getType();
158 if (loopType == ELoopWhile)
159 {
160 // Transform:
161 // while (expr) { body; }
162 // into
163 // bool s0 = expr;
164 // while (s0) { { body; } s0 = expr; }
165 TIntermSequence tempInitSeq;
166 tempInitSeq.push_back(createTempInitDeclaration(node->getCondition()->deepCopy()));
167 insertStatementsInParentBlock(tempInitSeq);
168
169 TIntermBlock *newBody = new TIntermBlock();
170 if (node->getBody())
171 {
172 newBody->getSequence()->push_back(node->getBody());
173 }
174 newBody->getSequence()->push_back(
175 createTempAssignment(node->getCondition()->deepCopy()));
176
177 // Can't use queueReplacement to replace old body, since it may have been nullptr.
178 // It's safe to do the replacements in place here - the new body will still be
179 // traversed, but that won't create any problems.
180 node->setBody(newBody);
181 node->setCondition(createTempSymbol(node->getCondition()->getType()));
182 }
183 else if (loopType == ELoopDoWhile)
184 {
185 // Transform:
186 // do {
187 // body;
188 // } while (expr);
189 // into
190 // bool s0 = true;
191 // do {
192 // { body; }
193 // s0 = expr;
194 // } while (s0);
195 TIntermSequence tempInitSeq;
196 tempInitSeq.push_back(createTempInitDeclaration(CreateBoolNode(true)));
197 insertStatementsInParentBlock(tempInitSeq);
198
199 TIntermBlock *newBody = new TIntermBlock();
200 if (node->getBody())
201 {
202 newBody->getSequence()->push_back(node->getBody());
203 }
204 newBody->getSequence()->push_back(
205 createTempAssignment(node->getCondition()->deepCopy()));
206
207 // Can't use queueReplacement to replace old body, since it may have been nullptr.
208 // It's safe to do the replacements in place here - the new body will still be
209 // traversed, but that won't create any problems.
210 node->setBody(newBody);
211 node->setCondition(createTempSymbol(node->getCondition()->getType()));
212 }
213 else if (loopType == ELoopFor)
214 {
215 // Move the loop condition inside the loop.
216 // Transform:
217 // for (init; expr; exprB) { body; }
218 // into
219 // {
220 // init;
221 // bool s0 = expr;
222 // while (s0) {
223 // { body; }
224 // exprB;
225 // s0 = expr;
226 // }
227 // }
228 TIntermBlock *loopScope = new TIntermBlock();
229 TIntermSequence *loopScopeSequence = loopScope->getSequence();
230
231 // Insert "init;"
232 if (node->getInit())
233 {
234 loopScopeSequence->push_back(node->getInit());
235 }
236
237 // Insert "bool s0 = expr;" if applicable, "bool s0 = true;" otherwise
238 TIntermTyped *conditionInitializer = nullptr;
239 if (node->getCondition())
240 {
241 conditionInitializer = node->getCondition()->deepCopy();
242 }
243 else
244 {
245 conditionInitializer = CreateBoolNode(true);
246 }
247 loopScopeSequence->push_back(createTempInitDeclaration(conditionInitializer));
248
249 // Insert "{ body; }" in the while loop
250 TIntermBlock *whileLoopBody = new TIntermBlock();
251 if (node->getBody())
252 {
253 whileLoopBody->getSequence()->push_back(node->getBody());
254 }
255 // Insert "exprB;" in the while loop
256 if (node->getExpression())
257 {
258 whileLoopBody->getSequence()->push_back(node->getExpression());
259 }
260 // Insert "s0 = expr;" in the while loop
261 if (node->getCondition())
262 {
263 whileLoopBody->getSequence()->push_back(
264 createTempAssignment(node->getCondition()->deepCopy()));
265 }
266
267 // Create "while(s0) { whileLoopBody }"
268 TIntermLoop *whileLoop = new TIntermLoop(
269 ELoopWhile, nullptr, createTempSymbol(conditionInitializer->getType()), nullptr,
270 whileLoopBody);
271 loopScope->getSequence()->push_back(whileLoop);
272 queueReplacement(loopScope, OriginalNode::IS_DROPPED);
273
274 // After this the old body node will be traversed and loops inside it may be
275 // transformed. This is fine, since the old body node will still be in the AST after the
276 // transformation that's queued here, and transforming loops inside it doesn't need to
277 // know the exact post-transform path to it.
278 }
279 }
280
281 mFoundLoopToChange = false;
282
283 // We traverse the body of the loop even if the loop is transformed.
284 if (node->getBody())
285 node->getBody()->traverse(this);
286 }
287
288 } // namespace
289
SimplifyLoopConditions(TIntermNode * root,unsigned int conditionsToSimplifyMask,TSymbolTable * symbolTable,int shaderVersion)290 void SimplifyLoopConditions(TIntermNode *root,
291 unsigned int conditionsToSimplifyMask,
292 TSymbolTable *symbolTable,
293 int shaderVersion)
294 {
295 SimplifyLoopConditionsTraverser traverser(conditionsToSimplifyMask, symbolTable, shaderVersion);
296 root->traverse(&traverser);
297 traverser.updateTree();
298 }
299
300 } // namespace sh
301