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
28namespace SkSL {
29
30BlockId 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
40BlockId CFG::newIsolatedBlock() {
41    BlockId result = fBlocks.size();
42    fBlocks.emplace_back();
43    return result;
44}
45
46void 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
53void 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
85bool 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
126bool 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
154bool 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
252bool 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
294void 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
423void 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
452void 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
633CFG 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