SkSLCFGGenerator.cpp 28 KB

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