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