1 /*
2 * Copyright 2016 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "SkSLCFGGenerator.h"
9
10 #include "ir/SkSLConstructor.h"
11 #include "ir/SkSLBinaryExpression.h"
12 #include "ir/SkSLDoStatement.h"
13 #include "ir/SkSLExpressionStatement.h"
14 #include "ir/SkSLFieldAccess.h"
15 #include "ir/SkSLForStatement.h"
16 #include "ir/SkSLFunctionCall.h"
17 #include "ir/SkSLIfStatement.h"
18 #include "ir/SkSLIndexExpression.h"
19 #include "ir/SkSLPostfixExpression.h"
20 #include "ir/SkSLPrefixExpression.h"
21 #include "ir/SkSLReturnStatement.h"
22 #include "ir/SkSLSwizzle.h"
23 #include "ir/SkSLSwitchStatement.h"
24 #include "ir/SkSLTernaryExpression.h"
25 #include "ir/SkSLVarDeclarationsStatement.h"
26 #include "ir/SkSLWhileStatement.h"
27
28 namespace SkSL {
29
newBlock()30 BlockId CFG::newBlock() {
31 BlockId result = fBlocks.size();
32 fBlocks.emplace_back();
33 if (fBlocks.size() > 1) {
34 this->addExit(fCurrent, result);
35 }
36 fCurrent = result;
37 return result;
38 }
39
newIsolatedBlock()40 BlockId CFG::newIsolatedBlock() {
41 BlockId result = fBlocks.size();
42 fBlocks.emplace_back();
43 return result;
44 }
45
addExit(BlockId from,BlockId to)46 void CFG::addExit(BlockId from, BlockId to) {
47 if (from == 0 || fBlocks[from].fEntrances.size()) {
48 fBlocks[from].fExits.insert(to);
49 fBlocks[to].fEntrances.insert(from);
50 }
51 }
52
dump()53 void CFG::dump() {
54 for (size_t i = 0; i < fBlocks.size(); i++) {
55 printf("Block %d\n-------\nBefore: ", (int) i);
56 const char* separator = "";
57 for (auto iter = fBlocks[i].fBefore.begin(); iter != fBlocks[i].fBefore.end(); iter++) {
58 printf("%s%s = %s", separator, iter->first->description().c_str(),
59 iter->second ? (*iter->second)->description().c_str() : "<undefined>");
60 separator = ", ";
61 }
62 printf("\nEntrances: ");
63 separator = "";
64 for (BlockId b : fBlocks[i].fEntrances) {
65 printf("%s%d", separator, (int) b);
66 separator = ", ";
67 }
68 printf("\n");
69 for (size_t j = 0; j < fBlocks[i].fNodes.size(); j++) {
70 BasicBlock::Node& n = fBlocks[i].fNodes[j];
71 printf("Node %d (%p): %s\n", (int) j, &n, n.fKind == BasicBlock::Node::kExpression_Kind
72 ? (*n.expression())->description().c_str()
73 : (*n.statement())->description().c_str());
74 }
75 printf("Exits: ");
76 separator = "";
77 for (BlockId b : fBlocks[i].fExits) {
78 printf("%s%d", separator, (int) b);
79 separator = ", ";
80 }
81 printf("\n\n");
82 }
83 }
84
tryRemoveExpressionBefore(std::vector<BasicBlock::Node>::iterator * iter,Expression * e)85 bool BasicBlock::tryRemoveExpressionBefore(std::vector<BasicBlock::Node>::iterator* iter,
86 Expression* e) {
87 if (e->fKind == Expression::kTernary_Kind) {
88 return false;
89 }
90 bool result;
91 if ((*iter)->fKind == BasicBlock::Node::kExpression_Kind) {
92 SkASSERT((*iter)->expression()->get() != e);
93 Expression* old = (*iter)->expression()->get();
94 do {
95 if ((*iter) == fNodes.begin()) {
96 return false;
97 }
98 --(*iter);
99 } while ((*iter)->fKind != BasicBlock::Node::kExpression_Kind ||
100 (*iter)->expression()->get() != e);
101 result = this->tryRemoveExpression(iter);
102 while ((*iter)->fKind != BasicBlock::Node::kExpression_Kind ||
103 (*iter)->expression()->get() != old) {
104 SkASSERT(*iter != fNodes.end());
105 ++(*iter);
106 }
107 } else {
108 Statement* old = (*iter)->statement()->get();
109 do {
110 if ((*iter) == fNodes.begin()) {
111 return false;
112 }
113 --(*iter);
114 } while ((*iter)->fKind != BasicBlock::Node::kExpression_Kind ||
115 (*iter)->expression()->get() != e);
116 result = this->tryRemoveExpression(iter);
117 while ((*iter)->fKind != BasicBlock::Node::kStatement_Kind ||
118 (*iter)->statement()->get() != old) {
119 SkASSERT(*iter != fNodes.end());
120 ++(*iter);
121 }
122 }
123 return result;
124 }
125
tryRemoveLValueBefore(std::vector<BasicBlock::Node>::iterator * iter,Expression * lvalue)126 bool BasicBlock::tryRemoveLValueBefore(std::vector<BasicBlock::Node>::iterator* iter,
127 Expression* lvalue) {
128 switch (lvalue->fKind) {
129 case Expression::kVariableReference_Kind:
130 return true;
131 case Expression::kSwizzle_Kind:
132 return this->tryRemoveLValueBefore(iter, ((Swizzle*) lvalue)->fBase.get());
133 case Expression::kFieldAccess_Kind:
134 return this->tryRemoveLValueBefore(iter, ((FieldAccess*) lvalue)->fBase.get());
135 case Expression::kIndex_Kind:
136 if (!this->tryRemoveLValueBefore(iter, ((IndexExpression*) lvalue)->fBase.get())) {
137 return false;
138 }
139 return this->tryRemoveExpressionBefore(iter, ((IndexExpression*) lvalue)->fIndex.get());
140 case Expression::kTernary_Kind:
141 if (!this->tryRemoveExpressionBefore(iter,
142 ((TernaryExpression*) lvalue)->fTest.get())) {
143 return false;
144 }
145 if (!this->tryRemoveLValueBefore(iter, ((TernaryExpression*) lvalue)->fIfTrue.get())) {
146 return false;
147 }
148 return this->tryRemoveLValueBefore(iter, ((TernaryExpression*) lvalue)->fIfFalse.get());
149 default:
150 ABORT("invalid lvalue: %s\n", lvalue->description().c_str());
151 }
152 }
153
tryRemoveExpression(std::vector<BasicBlock::Node>::iterator * iter)154 bool BasicBlock::tryRemoveExpression(std::vector<BasicBlock::Node>::iterator* iter) {
155 Expression* expr = (*iter)->expression()->get();
156 switch (expr->fKind) {
157 case Expression::kBinary_Kind: {
158 BinaryExpression* b = (BinaryExpression*) expr;
159 if (b->fOperator == Token::EQ) {
160 if (!this->tryRemoveLValueBefore(iter, b->fLeft.get())) {
161 return false;
162 }
163 } else if (!this->tryRemoveExpressionBefore(iter, b->fLeft.get())) {
164 return false;
165 }
166 if (!this->tryRemoveExpressionBefore(iter, b->fRight.get())) {
167 return false;
168 }
169 SkASSERT((*iter)->expression()->get() == expr);
170 *iter = fNodes.erase(*iter);
171 return true;
172 }
173 case Expression::kTernary_Kind: {
174 // ternaries cross basic block boundaries, must regenerate the CFG to remove it
175 return false;
176 }
177 case Expression::kFieldAccess_Kind: {
178 FieldAccess* f = (FieldAccess*) expr;
179 if (!this->tryRemoveExpressionBefore(iter, f->fBase.get())) {
180 return false;
181 }
182 *iter = fNodes.erase(*iter);
183 return true;
184 }
185 case Expression::kSwizzle_Kind: {
186 Swizzle* s = (Swizzle*) expr;
187 if (!this->tryRemoveExpressionBefore(iter, s->fBase.get())) {
188 return false;
189 }
190 *iter = fNodes.erase(*iter);
191 return true;
192 }
193 case Expression::kIndex_Kind: {
194 IndexExpression* idx = (IndexExpression*) expr;
195 if (!this->tryRemoveExpressionBefore(iter, idx->fBase.get())) {
196 return false;
197 }
198 if (!this->tryRemoveExpressionBefore(iter, idx->fIndex.get())) {
199 return false;
200 }
201 *iter = fNodes.erase(*iter);
202 return true;
203 }
204 case Expression::kConstructor_Kind: {
205 Constructor* c = (Constructor*) expr;
206 for (auto& arg : c->fArguments) {
207 if (!this->tryRemoveExpressionBefore(iter, arg.get())) {
208 return false;
209 }
210 SkASSERT((*iter)->expression()->get() == expr);
211 }
212 *iter = fNodes.erase(*iter);
213 return true;
214 }
215 case Expression::kFunctionCall_Kind: {
216 FunctionCall* f = (FunctionCall*) expr;
217 for (auto& arg : f->fArguments) {
218 if (!this->tryRemoveExpressionBefore(iter, arg.get())) {
219 return false;
220 }
221 SkASSERT((*iter)->expression()->get() == expr);
222 }
223 *iter = fNodes.erase(*iter);
224 return true;
225 }
226 case Expression::kPrefix_Kind:
227 if (!this->tryRemoveExpressionBefore(iter,
228 ((PrefixExpression*) expr)->fOperand.get())) {
229 return false;
230 }
231 *iter = fNodes.erase(*iter);
232 return true;
233 case Expression::kPostfix_Kind:
234 if (!this->tryRemoveExpressionBefore(iter,
235 ((PrefixExpression*) expr)->fOperand.get())) {
236 return false;
237 }
238 *iter = fNodes.erase(*iter);
239 return true;
240 case Expression::kBoolLiteral_Kind: // fall through
241 case Expression::kFloatLiteral_Kind: // fall through
242 case Expression::kIntLiteral_Kind: // fall through
243 case Expression::kSetting_Kind: // fall through
244 case Expression::kVariableReference_Kind:
245 *iter = fNodes.erase(*iter);
246 return true;
247 default:
248 ABORT("unhandled expression: %s\n", expr->description().c_str());
249 }
250 }
251
tryInsertExpression(std::vector<BasicBlock::Node>::iterator * iter,std::unique_ptr<Expression> * expr)252 bool BasicBlock::tryInsertExpression(std::vector<BasicBlock::Node>::iterator* iter,
253 std::unique_ptr<Expression>* expr) {
254 switch ((*expr)->fKind) {
255 case Expression::kBinary_Kind: {
256 BinaryExpression* b = (BinaryExpression*) expr->get();
257 if (!this->tryInsertExpression(iter, &b->fRight)) {
258 return false;
259 }
260 ++(*iter);
261 if (!this->tryInsertExpression(iter, &b->fLeft)) {
262 return false;
263 }
264 ++(*iter);
265 BasicBlock::Node node = { BasicBlock::Node::kExpression_Kind, true, expr, nullptr };
266 *iter = fNodes.insert(*iter, node);
267 return true;
268 }
269 case Expression::kBoolLiteral_Kind: // fall through
270 case Expression::kFloatLiteral_Kind: // fall through
271 case Expression::kIntLiteral_Kind: // fall through
272 case Expression::kVariableReference_Kind: {
273 BasicBlock::Node node = { BasicBlock::Node::kExpression_Kind, true, expr, nullptr };
274 *iter = fNodes.insert(*iter, node);
275 return true;
276 }
277 case Expression::kConstructor_Kind: {
278 Constructor* c = (Constructor*) expr->get();
279 for (auto& arg : c->fArguments) {
280 if (!this->tryInsertExpression(iter, &arg)) {
281 return false;
282 }
283 ++(*iter);
284 }
285 BasicBlock::Node node = { BasicBlock::Node::kExpression_Kind, true, expr, nullptr };
286 *iter = fNodes.insert(*iter, node);
287 return true;
288 }
289 default:
290 return false;
291 }
292 }
293
addExpression(CFG & cfg,std::unique_ptr<Expression> * e,bool constantPropagate)294 void CFGGenerator::addExpression(CFG& cfg, std::unique_ptr<Expression>* e, bool constantPropagate) {
295 SkASSERT(e);
296 switch ((*e)->fKind) {
297 case Expression::kBinary_Kind: {
298 BinaryExpression* b = (BinaryExpression*) e->get();
299 switch (b->fOperator) {
300 case Token::LOGICALAND: // fall through
301 case Token::LOGICALOR: {
302 // this isn't as precise as it could be -- we don't bother to track that if we
303 // early exit from a logical and/or, we know which branch of an 'if' we're going
304 // to hit -- but it won't make much difference in practice.
305 this->addExpression(cfg, &b->fLeft, constantPropagate);
306 BlockId start = cfg.fCurrent;
307 cfg.newBlock();
308 this->addExpression(cfg, &b->fRight, constantPropagate);
309 cfg.newBlock();
310 cfg.addExit(start, cfg.fCurrent);
311 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
312 BasicBlock::Node::kExpression_Kind,
313 constantPropagate,
314 e,
315 nullptr
316 });
317 break;
318 }
319 case Token::EQ: {
320 this->addExpression(cfg, &b->fRight, constantPropagate);
321 this->addLValue(cfg, &b->fLeft);
322 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
323 BasicBlock::Node::kExpression_Kind,
324 constantPropagate,
325 e,
326 nullptr
327 });
328 break;
329 }
330 default:
331 this->addExpression(cfg, &b->fLeft, !Compiler::IsAssignment(b->fOperator));
332 this->addExpression(cfg, &b->fRight, constantPropagate);
333 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
334 BasicBlock::Node::kExpression_Kind,
335 constantPropagate,
336 e,
337 nullptr
338 });
339 }
340 break;
341 }
342 case Expression::kConstructor_Kind: {
343 Constructor* c = (Constructor*) e->get();
344 for (auto& arg : c->fArguments) {
345 this->addExpression(cfg, &arg, constantPropagate);
346 }
347 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
348 constantPropagate, e, nullptr });
349 break;
350 }
351 case Expression::kFunctionCall_Kind: {
352 FunctionCall* c = (FunctionCall*) e->get();
353 for (auto& arg : c->fArguments) {
354 this->addExpression(cfg, &arg, constantPropagate);
355 }
356 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
357 constantPropagate, e, nullptr });
358 break;
359 }
360 case Expression::kFieldAccess_Kind:
361 this->addExpression(cfg, &((FieldAccess*) e->get())->fBase, constantPropagate);
362 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
363 constantPropagate, e, nullptr });
364 break;
365 case Expression::kIndex_Kind:
366 this->addExpression(cfg, &((IndexExpression*) e->get())->fBase, constantPropagate);
367 this->addExpression(cfg, &((IndexExpression*) e->get())->fIndex, constantPropagate);
368 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
369 constantPropagate, e, nullptr });
370 break;
371 case Expression::kPrefix_Kind: {
372 PrefixExpression* p = (PrefixExpression*) e->get();
373 this->addExpression(cfg, &p->fOperand, constantPropagate &&
374 p->fOperator != Token::PLUSPLUS &&
375 p->fOperator != Token::MINUSMINUS);
376 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
377 constantPropagate, e, nullptr });
378 break;
379 }
380 case Expression::kPostfix_Kind:
381 this->addExpression(cfg, &((PostfixExpression*) e->get())->fOperand, false);
382 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
383 constantPropagate, e, nullptr });
384 break;
385 case Expression::kSwizzle_Kind:
386 this->addExpression(cfg, &((Swizzle*) e->get())->fBase, constantPropagate);
387 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
388 constantPropagate, e, nullptr });
389 break;
390 case Expression::kAppendStage_Kind: // fall through
391 case Expression::kBoolLiteral_Kind: // fall through
392 case Expression::kFloatLiteral_Kind: // fall through
393 case Expression::kIntLiteral_Kind: // fall through
394 case Expression::kSetting_Kind: // fall through
395 case Expression::kVariableReference_Kind:
396 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
397 constantPropagate, e, nullptr });
398 break;
399 case Expression::kTernary_Kind: {
400 TernaryExpression* t = (TernaryExpression*) e->get();
401 this->addExpression(cfg, &t->fTest, constantPropagate);
402 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
403 constantPropagate, e, nullptr });
404 BlockId start = cfg.fCurrent;
405 cfg.newBlock();
406 this->addExpression(cfg, &t->fIfTrue, constantPropagate);
407 BlockId next = cfg.newBlock();
408 cfg.fCurrent = start;
409 cfg.newBlock();
410 this->addExpression(cfg, &t->fIfFalse, constantPropagate);
411 cfg.addExit(cfg.fCurrent, next);
412 cfg.fCurrent = next;
413 break;
414 }
415 case Expression::kFunctionReference_Kind: // fall through
416 case Expression::kTypeReference_Kind: // fall through
417 case Expression::kDefined_Kind:
418 SkASSERT(false);
419 break;
420 }
421 }
422
423 // adds expressions that are evaluated as part of resolving an lvalue
addLValue(CFG & cfg,std::unique_ptr<Expression> * e)424 void CFGGenerator::addLValue(CFG& cfg, std::unique_ptr<Expression>* e) {
425 switch ((*e)->fKind) {
426 case Expression::kFieldAccess_Kind:
427 this->addLValue(cfg, &((FieldAccess&) **e).fBase);
428 break;
429 case Expression::kIndex_Kind:
430 this->addLValue(cfg, &((IndexExpression&) **e).fBase);
431 this->addExpression(cfg, &((IndexExpression&) **e).fIndex, true);
432 break;
433 case Expression::kSwizzle_Kind:
434 this->addLValue(cfg, &((Swizzle&) **e).fBase);
435 break;
436 case Expression::kVariableReference_Kind:
437 break;
438 case Expression::kTernary_Kind:
439 this->addExpression(cfg, &((TernaryExpression&) **e).fTest, true);
440 // Technically we will of course only evaluate one or the other, but if the test turns
441 // out to be constant, the ternary will get collapsed down to just one branch anyway. So
442 // it should be ok to pretend that we always evaluate both branches here.
443 this->addLValue(cfg, &((TernaryExpression&) **e).fIfTrue);
444 this->addLValue(cfg, &((TernaryExpression&) **e).fIfFalse);
445 break;
446 default:
447 // not an lvalue, can't happen
448 SkASSERT(false);
449 break;
450 }
451 }
452
addStatement(CFG & cfg,std::unique_ptr<Statement> * s)453 void CFGGenerator::addStatement(CFG& cfg, std::unique_ptr<Statement>* s) {
454 switch ((*s)->fKind) {
455 case Statement::kBlock_Kind:
456 for (auto& child : ((Block&) **s).fStatements) {
457 addStatement(cfg, &child);
458 }
459 break;
460 case Statement::kIf_Kind: {
461 IfStatement& ifs = (IfStatement&) **s;
462 this->addExpression(cfg, &ifs.fTest, true);
463 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
464 nullptr, s });
465 BlockId start = cfg.fCurrent;
466 cfg.newBlock();
467 this->addStatement(cfg, &ifs.fIfTrue);
468 BlockId next = cfg.newBlock();
469 if (ifs.fIfFalse) {
470 cfg.fCurrent = start;
471 cfg.newBlock();
472 this->addStatement(cfg, &ifs.fIfFalse);
473 cfg.addExit(cfg.fCurrent, next);
474 cfg.fCurrent = next;
475 } else {
476 cfg.addExit(start, next);
477 }
478 break;
479 }
480 case Statement::kExpression_Kind: {
481 this->addExpression(cfg, &((ExpressionStatement&) **s).fExpression, true);
482 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
483 nullptr, s });
484 break;
485 }
486 case Statement::kVarDeclarations_Kind: {
487 VarDeclarationsStatement& decls = ((VarDeclarationsStatement&) **s);
488 for (auto& stmt : decls.fDeclaration->fVars) {
489 if (stmt->fKind == Statement::kNop_Kind) {
490 continue;
491 }
492 VarDeclaration& vd = (VarDeclaration&) *stmt;
493 if (vd.fValue) {
494 this->addExpression(cfg, &vd.fValue, true);
495 }
496 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind,
497 false, nullptr, &stmt });
498 }
499 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
500 nullptr, s });
501 break;
502 }
503 case Statement::kDiscard_Kind:
504 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
505 nullptr, s });
506 cfg.fCurrent = cfg.newIsolatedBlock();
507 break;
508 case Statement::kReturn_Kind: {
509 ReturnStatement& r = ((ReturnStatement&) **s);
510 if (r.fExpression) {
511 this->addExpression(cfg, &r.fExpression, true);
512 }
513 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
514 nullptr, s });
515 cfg.fCurrent = cfg.newIsolatedBlock();
516 break;
517 }
518 case Statement::kBreak_Kind:
519 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
520 nullptr, s });
521 cfg.addExit(cfg.fCurrent, fLoopExits.top());
522 cfg.fCurrent = cfg.newIsolatedBlock();
523 break;
524 case Statement::kContinue_Kind:
525 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
526 nullptr, s });
527 cfg.addExit(cfg.fCurrent, fLoopContinues.top());
528 cfg.fCurrent = cfg.newIsolatedBlock();
529 break;
530 case Statement::kWhile_Kind: {
531 WhileStatement& w = (WhileStatement&) **s;
532 BlockId loopStart = cfg.newBlock();
533 fLoopContinues.push(loopStart);
534 BlockId loopExit = cfg.newIsolatedBlock();
535 fLoopExits.push(loopExit);
536 this->addExpression(cfg, &w.fTest, true);
537 BlockId test = cfg.fCurrent;
538 cfg.addExit(test, loopExit);
539 cfg.newBlock();
540 this->addStatement(cfg, &w.fStatement);
541 cfg.addExit(cfg.fCurrent, loopStart);
542 fLoopContinues.pop();
543 fLoopExits.pop();
544 cfg.fCurrent = loopExit;
545 break;
546 }
547 case Statement::kDo_Kind: {
548 DoStatement& d = (DoStatement&) **s;
549 BlockId loopStart = cfg.newBlock();
550 fLoopContinues.push(loopStart);
551 BlockId loopExit = cfg.newIsolatedBlock();
552 fLoopExits.push(loopExit);
553 this->addStatement(cfg, &d.fStatement);
554 this->addExpression(cfg, &d.fTest, true);
555 cfg.addExit(cfg.fCurrent, loopExit);
556 cfg.addExit(cfg.fCurrent, loopStart);
557 fLoopContinues.pop();
558 fLoopExits.pop();
559 cfg.fCurrent = loopExit;
560 break;
561 }
562 case Statement::kFor_Kind: {
563 ForStatement& f = (ForStatement&) **s;
564 if (f.fInitializer) {
565 this->addStatement(cfg, &f.fInitializer);
566 }
567 BlockId loopStart = cfg.newBlock();
568 BlockId next = cfg.newIsolatedBlock();
569 fLoopContinues.push(next);
570 BlockId loopExit = cfg.newIsolatedBlock();
571 fLoopExits.push(loopExit);
572 if (f.fTest) {
573 this->addExpression(cfg, &f.fTest, true);
574 // this isn't quite right; we should have an exit from here to the loop exit, and
575 // remove the exit from the loop body to the loop exit. Structuring it like this
576 // forces the optimizer to believe that the loop body is always executed at least
577 // once. While not strictly correct, this avoids incorrect "variable not assigned"
578 // errors on variables which are assigned within the loop. The correct solution to
579 // this is to analyze the loop to see whether or not at least one iteration is
580 // guaranteed to happen, but for the time being we take the easy way out.
581 }
582 cfg.newBlock();
583 this->addStatement(cfg, &f.fStatement);
584 cfg.addExit(cfg.fCurrent, next);
585 cfg.fCurrent = next;
586 if (f.fNext) {
587 this->addExpression(cfg, &f.fNext, true);
588 }
589 cfg.addExit(cfg.fCurrent, loopStart);
590 cfg.addExit(cfg.fCurrent, loopExit);
591 fLoopContinues.pop();
592 fLoopExits.pop();
593 cfg.fCurrent = loopExit;
594 break;
595 }
596 case Statement::kSwitch_Kind: {
597 SwitchStatement& ss = (SwitchStatement&) **s;
598 this->addExpression(cfg, &ss.fValue, true);
599 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
600 nullptr, s });
601 BlockId start = cfg.fCurrent;
602 BlockId switchExit = cfg.newIsolatedBlock();
603 fLoopExits.push(switchExit);
604 for (const auto& c : ss.fCases) {
605 cfg.newBlock();
606 cfg.addExit(start, cfg.fCurrent);
607 if (c->fValue) {
608 // technically this should go in the start block, but it doesn't actually matter
609 // because it must be constant. Not worth running two loops for.
610 this->addExpression(cfg, &c->fValue, true);
611 }
612 for (auto& caseStatement : c->fStatements) {
613 this->addStatement(cfg, &caseStatement);
614 }
615 }
616 cfg.addExit(cfg.fCurrent, switchExit);
617 // note that unlike GLSL, our grammar requires the default case to be last
618 if (0 == ss.fCases.size() || ss.fCases[ss.fCases.size() - 1]->fValue) {
619 // switch does not have a default clause, mark that it can skip straight to the end
620 cfg.addExit(start, switchExit);
621 }
622 fLoopExits.pop();
623 cfg.fCurrent = switchExit;
624 break;
625 }
626 case Statement::kNop_Kind:
627 break;
628 default:
629 printf("statement: %s\n", (*s)->description().c_str());
630 ABORT("unsupported statement kind");
631 }
632 }
633
getCFG(FunctionDefinition & f)634 CFG CFGGenerator::getCFG(FunctionDefinition& f) {
635 CFG result;
636 result.fStart = result.newBlock();
637 result.fCurrent = result.fStart;
638 this->addStatement(result, &f.fBody);
639 result.newBlock();
640 result.fExit = result.fCurrent;
641 return result;
642 }
643
644 } // namespace
645