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 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 40 BlockId CFG::newIsolatedBlock() { 41 BlockId result = fBlocks.size(); 42 fBlocks.emplace_back(); 43 return result; 44 } 45 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 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 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 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 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 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 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 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 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 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
