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