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 ASSERT((*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 ASSERT(*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 ASSERT(*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 ASSERT((*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 ASSERT((*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 ASSERT((*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 ASSERT(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::kBoolLiteral_Kind: // fall through
391 case Expression::kFloatLiteral_Kind: // fall through
392 case Expression::kIntLiteral_Kind: // fall through
393 case Expression::kSetting_Kind: // fall through
394 case Expression::kVariableReference_Kind:
395 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
396 constantPropagate, e, nullptr });
397 break;
398 case Expression::kTernary_Kind: {
399 TernaryExpression* t = (TernaryExpression*) e->get();
400 this->addExpression(cfg, &t->fTest, constantPropagate);
401 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
402 constantPropagate, e, nullptr });
403 BlockId start = cfg.fCurrent;
404 cfg.newBlock();
405 this->addExpression(cfg, &t->fIfTrue, constantPropagate);
406 BlockId next = cfg.newBlock();
407 cfg.fCurrent = start;
408 cfg.newBlock();
409 this->addExpression(cfg, &t->fIfFalse, constantPropagate);
410 cfg.addExit(cfg.fCurrent, next);
411 cfg.fCurrent = next;
412 break;
413 }
414 case Expression::kFunctionReference_Kind: // fall through
415 case Expression::kTypeReference_Kind: // fall through
416 case Expression::kDefined_Kind:
417 ASSERT(false);
418 break;
419 }
420 }
421
422 // adds expressions that are evaluated as part of resolving an lvalue
addLValue(CFG & cfg,std::unique_ptr<Expression> * e)423 void CFGGenerator::addLValue(CFG& cfg, std::unique_ptr<Expression>* e) {
424 switch ((*e)->fKind) {
425 case Expression::kFieldAccess_Kind:
426 this->addLValue(cfg, &((FieldAccess&) **e).fBase);
427 break;
428 case Expression::kIndex_Kind:
429 this->addLValue(cfg, &((IndexExpression&) **e).fBase);
430 this->addExpression(cfg, &((IndexExpression&) **e).fIndex, true);
431 break;
432 case Expression::kSwizzle_Kind:
433 this->addLValue(cfg, &((Swizzle&) **e).fBase);
434 break;
435 case Expression::kVariableReference_Kind:
436 break;
437 case Expression::kTernary_Kind:
438 this->addExpression(cfg, &((TernaryExpression&) **e).fTest, true);
439 // Technically we will of course only evaluate one or the other, but if the test turns
440 // out to be constant, the ternary will get collapsed down to just one branch anyway. So
441 // it should be ok to pretend that we always evaluate both branches here.
442 this->addLValue(cfg, &((TernaryExpression&) **e).fIfTrue);
443 this->addLValue(cfg, &((TernaryExpression&) **e).fIfFalse);
444 break;
445 default:
446 // not an lvalue, can't happen
447 ASSERT(false);
448 break;
449 }
450 }
451
addStatement(CFG & cfg,std::unique_ptr<Statement> * s)452 void CFGGenerator::addStatement(CFG& cfg, std::unique_ptr<Statement>* s) {
453 switch ((*s)->fKind) {
454 case Statement::kBlock_Kind:
455 for (auto& child : ((Block&) **s).fStatements) {
456 addStatement(cfg, &child);
457 }
458 break;
459 case Statement::kIf_Kind: {
460 IfStatement& ifs = (IfStatement&) **s;
461 this->addExpression(cfg, &ifs.fTest, true);
462 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
463 nullptr, s });
464 BlockId start = cfg.fCurrent;
465 cfg.newBlock();
466 this->addStatement(cfg, &ifs.fIfTrue);
467 BlockId next = cfg.newBlock();
468 if (ifs.fIfFalse) {
469 cfg.fCurrent = start;
470 cfg.newBlock();
471 this->addStatement(cfg, &ifs.fIfFalse);
472 cfg.addExit(cfg.fCurrent, next);
473 cfg.fCurrent = next;
474 } else {
475 cfg.addExit(start, next);
476 }
477 break;
478 }
479 case Statement::kExpression_Kind: {
480 this->addExpression(cfg, &((ExpressionStatement&) **s).fExpression, true);
481 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
482 nullptr, s });
483 break;
484 }
485 case Statement::kVarDeclarations_Kind: {
486 VarDeclarationsStatement& decls = ((VarDeclarationsStatement&) **s);
487 for (auto& stmt : decls.fDeclaration->fVars) {
488 if (stmt->fKind == Statement::kNop_Kind) {
489 continue;
490 }
491 VarDeclaration& vd = (VarDeclaration&) *stmt;
492 if (vd.fValue) {
493 this->addExpression(cfg, &vd.fValue, true);
494 }
495 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind,
496 false, nullptr, &stmt });
497 }
498 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
499 nullptr, s });
500 break;
501 }
502 case Statement::kDiscard_Kind:
503 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
504 nullptr, s });
505 cfg.fCurrent = cfg.newIsolatedBlock();
506 break;
507 case Statement::kReturn_Kind: {
508 ReturnStatement& r = ((ReturnStatement&) **s);
509 if (r.fExpression) {
510 this->addExpression(cfg, &r.fExpression, true);
511 }
512 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
513 nullptr, s });
514 cfg.fCurrent = cfg.newIsolatedBlock();
515 break;
516 }
517 case Statement::kBreak_Kind:
518 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
519 nullptr, s });
520 cfg.addExit(cfg.fCurrent, fLoopExits.top());
521 cfg.fCurrent = cfg.newIsolatedBlock();
522 break;
523 case Statement::kContinue_Kind:
524 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
525 nullptr, s });
526 cfg.addExit(cfg.fCurrent, fLoopContinues.top());
527 cfg.fCurrent = cfg.newIsolatedBlock();
528 break;
529 case Statement::kWhile_Kind: {
530 WhileStatement& w = (WhileStatement&) **s;
531 BlockId loopStart = cfg.newBlock();
532 fLoopContinues.push(loopStart);
533 BlockId loopExit = cfg.newIsolatedBlock();
534 fLoopExits.push(loopExit);
535 this->addExpression(cfg, &w.fTest, true);
536 BlockId test = cfg.fCurrent;
537 cfg.addExit(test, loopExit);
538 cfg.newBlock();
539 this->addStatement(cfg, &w.fStatement);
540 cfg.addExit(cfg.fCurrent, loopStart);
541 fLoopContinues.pop();
542 fLoopExits.pop();
543 cfg.fCurrent = loopExit;
544 break;
545 }
546 case Statement::kDo_Kind: {
547 DoStatement& d = (DoStatement&) **s;
548 BlockId loopStart = cfg.newBlock();
549 fLoopContinues.push(loopStart);
550 BlockId loopExit = cfg.newIsolatedBlock();
551 fLoopExits.push(loopExit);
552 this->addStatement(cfg, &d.fStatement);
553 this->addExpression(cfg, &d.fTest, true);
554 cfg.addExit(cfg.fCurrent, loopExit);
555 cfg.addExit(cfg.fCurrent, loopStart);
556 fLoopContinues.pop();
557 fLoopExits.pop();
558 cfg.fCurrent = loopExit;
559 break;
560 }
561 case Statement::kFor_Kind: {
562 ForStatement& f = (ForStatement&) **s;
563 if (f.fInitializer) {
564 this->addStatement(cfg, &f.fInitializer);
565 }
566 BlockId loopStart = cfg.newBlock();
567 BlockId next = cfg.newIsolatedBlock();
568 fLoopContinues.push(next);
569 BlockId loopExit = cfg.newIsolatedBlock();
570 fLoopExits.push(loopExit);
571 if (f.fTest) {
572 this->addExpression(cfg, &f.fTest, true);
573 // this isn't quite right; we should have an exit from here to the loop exit, and
574 // remove the exit from the loop body to the loop exit. Structuring it like this
575 // forces the optimizer to believe that the loop body is always executed at least
576 // once. While not strictly correct, this avoids incorrect "variable not assigned"
577 // errors on variables which are assigned within the loop. The correct solution to
578 // this is to analyze the loop to see whether or not at least one iteration is
579 // guaranteed to happen, but for the time being we take the easy way out.
580 }
581 cfg.newBlock();
582 this->addStatement(cfg, &f.fStatement);
583 cfg.addExit(cfg.fCurrent, next);
584 cfg.fCurrent = next;
585 if (f.fNext) {
586 this->addExpression(cfg, &f.fNext, true);
587 }
588 cfg.addExit(cfg.fCurrent, loopStart);
589 cfg.addExit(cfg.fCurrent, loopExit);
590 fLoopContinues.pop();
591 fLoopExits.pop();
592 cfg.fCurrent = loopExit;
593 break;
594 }
595 case Statement::kSwitch_Kind: {
596 SwitchStatement& ss = (SwitchStatement&) **s;
597 this->addExpression(cfg, &ss.fValue, true);
598 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
599 nullptr, s });
600 BlockId start = cfg.fCurrent;
601 BlockId switchExit = cfg.newIsolatedBlock();
602 fLoopExits.push(switchExit);
603 for (const auto& c : ss.fCases) {
604 cfg.newBlock();
605 cfg.addExit(start, cfg.fCurrent);
606 if (c->fValue) {
607 // technically this should go in the start block, but it doesn't actually matter
608 // because it must be constant. Not worth running two loops for.
609 this->addExpression(cfg, &c->fValue, true);
610 }
611 for (auto& caseStatement : c->fStatements) {
612 this->addStatement(cfg, &caseStatement);
613 }
614 }
615 cfg.addExit(cfg.fCurrent, switchExit);
616 // note that unlike GLSL, our grammar requires the default case to be last
617 if (0 == ss.fCases.size() || ss.fCases[ss.fCases.size() - 1]->fValue) {
618 // switch does not have a default clause, mark that it can skip straight to the end
619 cfg.addExit(start, switchExit);
620 }
621 fLoopExits.pop();
622 cfg.fCurrent = switchExit;
623 break;
624 }
625 case Statement::kNop_Kind:
626 break;
627 default:
628 printf("statement: %s\n", (*s)->description().c_str());
629 ABORT("unsupported statement kind");
630 }
631 }
632
getCFG(FunctionDefinition & f)633 CFG CFGGenerator::getCFG(FunctionDefinition& f) {
634 CFG result;
635 result.fStart = result.newBlock();
636 result.fCurrent = result.fStart;
637 this->addStatement(result, &f.fBody);
638 result.newBlock();
639 result.fExit = result.fCurrent;
640 return result;
641 }
642
643 } // namespace
644