1 //
2 // Copyright 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/tree_ops/SimplifyLoopConditions.h"
12
13 #include "compiler/translator/StaticType.h"
14 #include "compiler/translator/tree_util/IntermNodePatternMatcher.h"
15 #include "compiler/translator/tree_util/IntermNode_util.h"
16 #include "compiler/translator/tree_util/IntermTraverse.h"
17
18 namespace sh
19 {
20
21 namespace
22 {
23
24 class SimplifyLoopConditionsTraverser : public TLValueTrackingTraverser
25 {
26 public:
27 SimplifyLoopConditionsTraverser(unsigned int conditionsToSimplifyMask,
28 TSymbolTable *symbolTable);
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)48 SimplifyLoopConditionsTraverser::SimplifyLoopConditionsTraverser(
49 unsigned int conditionsToSimplifyMask,
50 TSymbolTable *symbolTable)
51 : TLValueTrackingTraverser(true, false, false, symbolTable),
52 mFoundLoopToChange(false),
53 mInsideLoopInitConditionOrExpression(false),
54 mConditionsToSimplify(conditionsToSimplifyMask)
55 {}
56
57 // If we're inside a loop initialization, condition, or expression, we check for expressions that
58 // should be moved out of the loop condition or expression. If one is found, the loop is
59 // transformed.
60 // If we're not inside loop initialization, condition, or expression, we only need to traverse nodes
61 // that may contain loops.
62
visitUnary(Visit visit,TIntermUnary * node)63 bool SimplifyLoopConditionsTraverser::visitUnary(Visit visit, TIntermUnary *node)
64 {
65 if (!mInsideLoopInitConditionOrExpression)
66 return false;
67
68 if (mFoundLoopToChange)
69 return false; // Already decided to change this loop.
70
71 mFoundLoopToChange = mConditionsToSimplify.match(node);
72 return !mFoundLoopToChange;
73 }
74
visitBinary(Visit visit,TIntermBinary * node)75 bool SimplifyLoopConditionsTraverser::visitBinary(Visit visit, TIntermBinary *node)
76 {
77 if (!mInsideLoopInitConditionOrExpression)
78 return false;
79
80 if (mFoundLoopToChange)
81 return false; // Already decided to change this loop.
82
83 mFoundLoopToChange = mConditionsToSimplify.match(node, getParentNode(), isLValueRequiredHere());
84 return !mFoundLoopToChange;
85 }
86
visitAggregate(Visit visit,TIntermAggregate * node)87 bool SimplifyLoopConditionsTraverser::visitAggregate(Visit visit, TIntermAggregate *node)
88 {
89 if (!mInsideLoopInitConditionOrExpression)
90 return false;
91
92 if (mFoundLoopToChange)
93 return false; // Already decided to change this loop.
94
95 mFoundLoopToChange = mConditionsToSimplify.match(node, getParentNode());
96 return !mFoundLoopToChange;
97 }
98
visitTernary(Visit visit,TIntermTernary * node)99 bool SimplifyLoopConditionsTraverser::visitTernary(Visit visit, TIntermTernary *node)
100 {
101 if (!mInsideLoopInitConditionOrExpression)
102 return false;
103
104 if (mFoundLoopToChange)
105 return false; // Already decided to change this loop.
106
107 mFoundLoopToChange = mConditionsToSimplify.match(node);
108 return !mFoundLoopToChange;
109 }
110
visitDeclaration(Visit visit,TIntermDeclaration * node)111 bool SimplifyLoopConditionsTraverser::visitDeclaration(Visit visit, TIntermDeclaration *node)
112 {
113 if (!mInsideLoopInitConditionOrExpression)
114 return false;
115
116 if (mFoundLoopToChange)
117 return false; // Already decided to change this loop.
118
119 mFoundLoopToChange = mConditionsToSimplify.match(node);
120 return !mFoundLoopToChange;
121 }
122
traverseLoop(TIntermLoop * node)123 void SimplifyLoopConditionsTraverser::traverseLoop(TIntermLoop *node)
124 {
125 // Mark that we're inside a loop condition or expression, and determine if the loop needs to be
126 // transformed.
127
128 ScopedNodeInTraversalPath addToPath(this, node);
129
130 mInsideLoopInitConditionOrExpression = true;
131 mFoundLoopToChange = false;
132
133 if (!mFoundLoopToChange && node->getInit())
134 {
135 node->getInit()->traverse(this);
136 }
137
138 if (!mFoundLoopToChange && node->getCondition())
139 {
140 node->getCondition()->traverse(this);
141 }
142
143 if (!mFoundLoopToChange && node->getExpression())
144 {
145 node->getExpression()->traverse(this);
146 }
147
148 mInsideLoopInitConditionOrExpression = false;
149
150 if (mFoundLoopToChange)
151 {
152 const TType *boolType = StaticType::Get<EbtBool, EbpUndefined, EvqTemporary, 1, 1>();
153 TVariable *conditionVariable = CreateTempVariable(mSymbolTable, boolType);
154
155 // Replace the loop condition with a boolean variable that's updated on each iteration.
156 TLoopType loopType = node->getType();
157 if (loopType == ELoopWhile)
158 {
159 // Transform:
160 // while (expr) { body; }
161 // into
162 // bool s0 = expr;
163 // while (s0) { { body; } s0 = expr; }
164 TIntermDeclaration *tempInitDeclaration =
165 CreateTempInitDeclarationNode(conditionVariable, node->getCondition()->deepCopy());
166 insertStatementInParentBlock(tempInitDeclaration);
167
168 TIntermBlock *newBody = new TIntermBlock();
169 if (node->getBody())
170 {
171 newBody->getSequence()->push_back(node->getBody());
172 }
173 newBody->getSequence()->push_back(
174 CreateTempAssignmentNode(conditionVariable, node->getCondition()->deepCopy()));
175
176 // Can't use queueReplacement to replace old body, since it may have been nullptr.
177 // It's safe to do the replacements in place here - the new body will still be
178 // traversed, but that won't create any problems.
179 node->setBody(newBody);
180 node->setCondition(CreateTempSymbolNode(conditionVariable));
181 }
182 else if (loopType == ELoopDoWhile)
183 {
184 // Transform:
185 // do {
186 // body;
187 // } while (expr);
188 // into
189 // bool s0 = true;
190 // do {
191 // { body; }
192 // s0 = expr;
193 // } while (s0);
194 TIntermDeclaration *tempInitDeclaration =
195 CreateTempInitDeclarationNode(conditionVariable, CreateBoolNode(true));
196 insertStatementInParentBlock(tempInitDeclaration);
197
198 TIntermBlock *newBody = new TIntermBlock();
199 if (node->getBody())
200 {
201 newBody->getSequence()->push_back(node->getBody());
202 }
203 newBody->getSequence()->push_back(
204 CreateTempAssignmentNode(conditionVariable, node->getCondition()->deepCopy()));
205
206 // Can't use queueReplacement to replace old body, since it may have been nullptr.
207 // It's safe to do the replacements in place here - the new body will still be
208 // traversed, but that won't create any problems.
209 node->setBody(newBody);
210 node->setCondition(CreateTempSymbolNode(conditionVariable));
211 }
212 else if (loopType == ELoopFor)
213 {
214 // Move the loop condition inside the loop.
215 // Transform:
216 // for (init; expr; exprB) { body; }
217 // into
218 // {
219 // init;
220 // bool s0 = expr;
221 // while (s0) {
222 // { body; }
223 // exprB;
224 // s0 = expr;
225 // }
226 // }
227 TIntermBlock *loopScope = new TIntermBlock();
228 TIntermSequence *loopScopeSequence = loopScope->getSequence();
229
230 // Insert "init;"
231 if (node->getInit())
232 {
233 loopScopeSequence->push_back(node->getInit());
234 }
235
236 // Insert "bool s0 = expr;" if applicable, "bool s0 = true;" otherwise
237 TIntermTyped *conditionInitializer = nullptr;
238 if (node->getCondition())
239 {
240 conditionInitializer = node->getCondition()->deepCopy();
241 }
242 else
243 {
244 conditionInitializer = CreateBoolNode(true);
245 }
246 loopScopeSequence->push_back(
247 CreateTempInitDeclarationNode(conditionVariable, 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 CreateTempAssignmentNode(conditionVariable, node->getCondition()->deepCopy()));
265 }
266
267 // Create "while(s0) { whileLoopBody }"
268 TIntermLoop *whileLoop =
269 new TIntermLoop(ELoopWhile, nullptr, CreateTempSymbolNode(conditionVariable),
270 nullptr, 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(TCompiler * compiler,TIntermNode * root,unsigned int conditionsToSimplifyMask,TSymbolTable * symbolTable)290 bool SimplifyLoopConditions(TCompiler *compiler,
291 TIntermNode *root,
292 unsigned int conditionsToSimplifyMask,
293 TSymbolTable *symbolTable)
294 {
295 SimplifyLoopConditionsTraverser traverser(conditionsToSimplifyMask, symbolTable);
296 root->traverse(&traverser);
297 return traverser.updateTree(compiler, root);
298 }
299
300 } // namespace sh
301