SkSLCFGGenerator.cpp revision ccf59917d3fe7aaf59de714acfbd0596503f324f 
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        default:
141            ABORT("invalid lvalue: %s\n", lvalue->description().c_str());
142    }
143}
144
145bool BasicBlock::tryRemoveExpression(std::vector<BasicBlock::Node>::iterator* iter) {
146    Expression* expr = (*iter)->expression()->get();
147    switch (expr->fKind) {
148        case Expression::kBinary_Kind: {
149            BinaryExpression* b = (BinaryExpression*) expr;
150            if (b->fOperator == Token::EQ) {
151                if (!this->tryRemoveLValueBefore(iter, b->fLeft.get())) {
152                    return false;
153                }
154            } else if (!this->tryRemoveExpressionBefore(iter, b->fLeft.get())) {
155                return false;
156            }
157            if (!this->tryRemoveExpressionBefore(iter, b->fRight.get())) {
158                return false;
159            }
160            ASSERT((*iter)->expression()->get() == expr);
161            *iter = fNodes.erase(*iter);
162            return true;
163        }
164        case Expression::kTernary_Kind: {
165            // ternaries cross basic block boundaries, must regenerate the CFG to remove it
166            return false;
167        }
168        case Expression::kFieldAccess_Kind: {
169            FieldAccess* f = (FieldAccess*) expr;
170            if (!this->tryRemoveExpressionBefore(iter, f->fBase.get())) {
171                return false;
172            }
173            *iter = fNodes.erase(*iter);
174            return true;
175        }
176        case Expression::kSwizzle_Kind: {
177            Swizzle* s = (Swizzle*) expr;
178            if (!this->tryRemoveExpressionBefore(iter, s->fBase.get())) {
179                return false;
180            }
181            *iter = fNodes.erase(*iter);
182            return true;
183        }
184        case Expression::kIndex_Kind: {
185            IndexExpression* idx = (IndexExpression*) expr;
186            if (!this->tryRemoveExpressionBefore(iter, idx->fBase.get())) {
187                return false;
188            }
189            if (!this->tryRemoveExpressionBefore(iter, idx->fIndex.get())) {
190                return false;
191            }
192            *iter = fNodes.erase(*iter);
193            return true;
194        }
195        case Expression::kConstructor_Kind: {
196            Constructor* c = (Constructor*) expr;
197            for (auto& arg : c->fArguments) {
198                if (!this->tryRemoveExpressionBefore(iter, arg.get())) {
199                    return false;
200                }
201                ASSERT((*iter)->expression()->get() == expr);
202            }
203            *iter = fNodes.erase(*iter);
204            return true;
205        }
206        case Expression::kFunctionCall_Kind: {
207            FunctionCall* f = (FunctionCall*) expr;
208            for (auto& arg : f->fArguments) {
209                if (!this->tryRemoveExpressionBefore(iter, arg.get())) {
210                    return false;
211                }
212                ASSERT((*iter)->expression()->get() == expr);
213            }
214            *iter = fNodes.erase(*iter);
215            return true;
216        }
217        case Expression::kPrefix_Kind:
218            if (!this->tryRemoveExpressionBefore(iter,
219                                                 ((PrefixExpression*) expr)->fOperand.get())) {
220                return false;
221            }
222            *iter = fNodes.erase(*iter);
223            return true;
224        case Expression::kPostfix_Kind:
225            if (!this->tryRemoveExpressionBefore(iter,
226                                                 ((PrefixExpression*) expr)->fOperand.get())) {
227                return false;
228            }
229            *iter = fNodes.erase(*iter);
230            return true;
231        case Expression::kBoolLiteral_Kind:  // fall through
232        case Expression::kFloatLiteral_Kind: // fall through
233        case Expression::kIntLiteral_Kind:   // fall through
234        case Expression::kSetting_Kind:      // fall through
235        case Expression::kVariableReference_Kind:
236            *iter = fNodes.erase(*iter);
237            return true;
238        default:
239            ABORT("unhandled expression: %s\n", expr->description().c_str());
240    }
241}
242
243bool 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
285void CFGGenerator::addExpression(CFG& cfg, std::unique_ptr<Expression>* e, bool constantPropagate) {
286    ASSERT(e);
287    switch ((*e)->fKind) {
288        case Expression::kBinary_Kind: {
289            BinaryExpression* b = (BinaryExpression*) e->get();
290            switch (b->fOperator) {
291                case Token::LOGICALAND: // fall through
292                case Token::LOGICALOR: {
293                    // this isn't as precise as it could be -- we don't bother to track that if we
294                    // early exit from a logical and/or, we know which branch of an 'if' we're going
295                    // to hit -- but it won't make much difference in practice.
296                    this->addExpression(cfg, &b->fLeft, constantPropagate);
297                    BlockId start = cfg.fCurrent;
298                    cfg.newBlock();
299                    this->addExpression(cfg, &b->fRight, constantPropagate);
300                    cfg.newBlock();
301                    cfg.addExit(start, cfg.fCurrent);
302                    cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
303                        BasicBlock::Node::kExpression_Kind,
304                        constantPropagate,
305                        e,
306                        nullptr
307                    });
308                    break;
309                }
310                case Token::EQ: {
311                    this->addExpression(cfg, &b->fRight, constantPropagate);
312                    this->addLValue(cfg, &b->fLeft);
313                    cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
314                        BasicBlock::Node::kExpression_Kind,
315                        constantPropagate,
316                        e,
317                        nullptr
318                    });
319                    break;
320                }
321                default:
322                    this->addExpression(cfg, &b->fLeft, !Token::IsAssignment(b->fOperator));
323                    this->addExpression(cfg, &b->fRight, constantPropagate);
324                    cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
325                        BasicBlock::Node::kExpression_Kind,
326                        constantPropagate,
327                        e,
328                        nullptr
329                    });
330            }
331            break;
332        }
333        case Expression::kConstructor_Kind: {
334            Constructor* c = (Constructor*) e->get();
335            for (auto& arg : c->fArguments) {
336                this->addExpression(cfg, &arg, constantPropagate);
337            }
338            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
339                                                         constantPropagate, e, nullptr });
340            break;
341        }
342        case Expression::kFunctionCall_Kind: {
343            FunctionCall* c = (FunctionCall*) 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::kFieldAccess_Kind:
352            this->addExpression(cfg, &((FieldAccess*) e->get())->fBase, constantPropagate);
353            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
354                                                         constantPropagate, e, nullptr });
355            break;
356        case Expression::kIndex_Kind:
357            this->addExpression(cfg, &((IndexExpression*) e->get())->fBase, constantPropagate);
358            this->addExpression(cfg, &((IndexExpression*) e->get())->fIndex, constantPropagate);
359            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
360                                                         constantPropagate, e, nullptr });
361            break;
362        case Expression::kPrefix_Kind: {
363            PrefixExpression* p = (PrefixExpression*) e->get();
364            this->addExpression(cfg, &p->fOperand, constantPropagate &&
365                                                   p->fOperator != Token::PLUSPLUS &&
366                                                   p->fOperator != Token::MINUSMINUS);
367            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
368                                                         constantPropagate, e, nullptr });
369            break;
370        }
371        case Expression::kPostfix_Kind:
372            this->addExpression(cfg, &((PostfixExpression*) e->get())->fOperand, false);
373            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
374                                                         constantPropagate, e, nullptr });
375            break;
376        case Expression::kSwizzle_Kind:
377            this->addExpression(cfg, &((Swizzle*) e->get())->fBase, constantPropagate);
378            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
379                                                         constantPropagate, e, nullptr });
380            break;
381        case Expression::kBoolLiteral_Kind:  // fall through
382        case Expression::kFloatLiteral_Kind: // fall through
383        case Expression::kIntLiteral_Kind:   // fall through
384        case Expression::kSetting_Kind:      // fall through
385        case Expression::kVariableReference_Kind:
386            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
387                                                         constantPropagate, e, nullptr });
388            break;
389        case Expression::kTernary_Kind: {
390            TernaryExpression* t = (TernaryExpression*) e->get();
391            this->addExpression(cfg, &t->fTest, constantPropagate);
392            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
393                                                         constantPropagate, e, nullptr });
394            BlockId start = cfg.fCurrent;
395            cfg.newBlock();
396            this->addExpression(cfg, &t->fIfTrue, constantPropagate);
397            BlockId next = cfg.newBlock();
398            cfg.fCurrent = start;
399            cfg.newBlock();
400            this->addExpression(cfg, &t->fIfFalse, constantPropagate);
401            cfg.addExit(cfg.fCurrent, next);
402            cfg.fCurrent = next;
403            break;
404        }
405        case Expression::kFunctionReference_Kind: // fall through
406        case Expression::kTypeReference_Kind:     // fall through
407        case Expression::kDefined_Kind:
408            ASSERT(false);
409            break;
410    }
411}
412
413// adds expressions that are evaluated as part of resolving an lvalue
414void CFGGenerator::addLValue(CFG& cfg, std::unique_ptr<Expression>* e) {
415    switch ((*e)->fKind) {
416        case Expression::kFieldAccess_Kind:
417            this->addLValue(cfg, &((FieldAccess&) **e).fBase);
418            break;
419        case Expression::kIndex_Kind:
420            this->addLValue(cfg, &((IndexExpression&) **e).fBase);
421            this->addExpression(cfg, &((IndexExpression&) **e).fIndex, true);
422            break;
423        case Expression::kSwizzle_Kind:
424            this->addLValue(cfg, &((Swizzle&) **e).fBase);
425            break;
426        case Expression::kVariableReference_Kind:
427            break;
428        default:
429            // not an lvalue, can't happen
430            ASSERT(false);
431            break;
432    }
433}
434
435void CFGGenerator::addStatement(CFG& cfg, std::unique_ptr<Statement>* s) {
436    switch ((*s)->fKind) {
437        case Statement::kBlock_Kind:
438            for (auto& child : ((Block&) **s).fStatements) {
439                addStatement(cfg, &child);
440            }
441            break;
442        case Statement::kIf_Kind: {
443            IfStatement& ifs = (IfStatement&) **s;
444            this->addExpression(cfg, &ifs.fTest, true);
445            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
446                                                         nullptr, s });
447            BlockId start = cfg.fCurrent;
448            cfg.newBlock();
449            this->addStatement(cfg, &ifs.fIfTrue);
450            BlockId next = cfg.newBlock();
451            if (ifs.fIfFalse) {
452                cfg.fCurrent = start;
453                cfg.newBlock();
454                this->addStatement(cfg, &ifs.fIfFalse);
455                cfg.addExit(cfg.fCurrent, next);
456                cfg.fCurrent = next;
457            } else {
458                cfg.addExit(start, next);
459            }
460            break;
461        }
462        case Statement::kExpression_Kind: {
463            this->addExpression(cfg, &((ExpressionStatement&) **s).fExpression, true);
464            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
465                                                         nullptr, s });
466            break;
467        }
468        case Statement::kVarDeclarations_Kind: {
469            VarDeclarationsStatement& decls = ((VarDeclarationsStatement&) **s);
470            for (auto& stmt : decls.fDeclaration->fVars) {
471                if (stmt->fKind == Statement::kNop_Kind) {
472                    continue;
473                }
474                VarDeclaration& vd = (VarDeclaration&) *stmt;
475                if (vd.fValue) {
476                    this->addExpression(cfg, &vd.fValue, true);
477                }
478                cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind,
479                                                             false, nullptr, &stmt });
480            }
481            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
482                                                         nullptr, s });
483            break;
484        }
485        case Statement::kDiscard_Kind:
486            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
487                                                         nullptr, s });
488            cfg.fCurrent = cfg.newIsolatedBlock();
489            break;
490        case Statement::kReturn_Kind: {
491            ReturnStatement& r = ((ReturnStatement&) **s);
492            if (r.fExpression) {
493                this->addExpression(cfg, &r.fExpression, true);
494            }
495            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
496                                                         nullptr, s });
497            cfg.fCurrent = cfg.newIsolatedBlock();
498            break;
499        }
500        case Statement::kBreak_Kind:
501            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
502                                                         nullptr, s });
503            cfg.addExit(cfg.fCurrent, fLoopExits.top());
504            cfg.fCurrent = cfg.newIsolatedBlock();
505            break;
506        case Statement::kContinue_Kind:
507            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
508                                                         nullptr, s });
509            cfg.addExit(cfg.fCurrent, fLoopContinues.top());
510            cfg.fCurrent = cfg.newIsolatedBlock();
511            break;
512        case Statement::kWhile_Kind: {
513            WhileStatement& w = (WhileStatement&) **s;
514            BlockId loopStart = cfg.newBlock();
515            fLoopContinues.push(loopStart);
516            BlockId loopExit = cfg.newIsolatedBlock();
517            fLoopExits.push(loopExit);
518            this->addExpression(cfg, &w.fTest, true);
519            BlockId test = cfg.fCurrent;
520            cfg.addExit(test, loopExit);
521            cfg.newBlock();
522            this->addStatement(cfg, &w.fStatement);
523            cfg.addExit(cfg.fCurrent, loopStart);
524            fLoopContinues.pop();
525            fLoopExits.pop();
526            cfg.fCurrent = loopExit;
527            break;
528        }
529        case Statement::kDo_Kind: {
530            DoStatement& d = (DoStatement&) **s;
531            BlockId loopStart = cfg.newBlock();
532            fLoopContinues.push(loopStart);
533            BlockId loopExit = cfg.newIsolatedBlock();
534            fLoopExits.push(loopExit);
535            this->addStatement(cfg, &d.fStatement);
536            this->addExpression(cfg, &d.fTest, true);
537            cfg.addExit(cfg.fCurrent, loopExit);
538            cfg.addExit(cfg.fCurrent, loopStart);
539            fLoopContinues.pop();
540            fLoopExits.pop();
541            cfg.fCurrent = loopExit;
542            break;
543        }
544        case Statement::kFor_Kind: {
545            ForStatement& f = (ForStatement&) **s;
546            if (f.fInitializer) {
547                this->addStatement(cfg, &f.fInitializer);
548            }
549            BlockId loopStart = cfg.newBlock();
550            BlockId next = cfg.newIsolatedBlock();
551            fLoopContinues.push(next);
552            BlockId loopExit = cfg.newIsolatedBlock();
553            fLoopExits.push(loopExit);
554            if (f.fTest) {
555                this->addExpression(cfg, &f.fTest, true);
556                // this isn't quite right; we should have an exit from here to the loop exit, and
557                // remove the exit from the loop body to the loop exit. Structuring it like this
558                // forces the optimizer to believe that the loop body is always executed at least
559                // once. While not strictly correct, this avoids incorrect "variable not assigned"
560                // errors on variables which are assigned within the loop. The correct solution to
561                // this is to analyze the loop to see whether or not at least one iteration is
562                // guaranteed to happen, but for the time being we take the easy way out.
563            }
564            cfg.newBlock();
565            this->addStatement(cfg, &f.fStatement);
566            cfg.addExit(cfg.fCurrent, next);
567            cfg.fCurrent = next;
568            if (f.fNext) {
569                this->addExpression(cfg, &f.fNext, true);
570            }
571            cfg.addExit(cfg.fCurrent, loopStart);
572            cfg.addExit(cfg.fCurrent, loopExit);
573            fLoopContinues.pop();
574            fLoopExits.pop();
575            cfg.fCurrent = loopExit;
576            break;
577        }
578        case Statement::kSwitch_Kind: {
579            SwitchStatement& ss = (SwitchStatement&) **s;
580            this->addExpression(cfg, &ss.fValue, true);
581            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
582                                                         nullptr, s });
583            BlockId start = cfg.fCurrent;
584            BlockId switchExit = cfg.newIsolatedBlock();
585            fLoopExits.push(switchExit);
586            for (const auto& c : ss.fCases) {
587                cfg.newBlock();
588                cfg.addExit(start, cfg.fCurrent);
589                if (c->fValue) {
590                    // technically this should go in the start block, but it doesn't actually matter
591                    // because it must be constant. Not worth running two loops for.
592                    this->addExpression(cfg, &c->fValue, true);
593                }
594                for (auto& caseStatement : c->fStatements) {
595                    this->addStatement(cfg, &caseStatement);
596                }
597            }
598            cfg.addExit(cfg.fCurrent, switchExit);
599            // note that unlike GLSL, our grammar requires the default case to be last
600            if (0 == ss.fCases.size() || ss.fCases[ss.fCases.size() - 1]->fValue) {
601                // switch does not have a default clause, mark that it can skip straight to the end
602                cfg.addExit(start, switchExit);
603            }
604            fLoopExits.pop();
605            cfg.fCurrent = switchExit;
606            break;
607        }
608        case Statement::kNop_Kind:
609            break;
610        default:
611            printf("statement: %s\n", (*s)->description().c_str());
612            ABORT("unsupported statement kind");
613    }
614}
615
616CFG CFGGenerator::getCFG(FunctionDefinition& f) {
617    CFG result;
618    result.fStart = result.newBlock();
619    result.fCurrent = result.fStart;
620    this->addStatement(result, &f.fBody);
621    result.newBlock();
622    result.fExit = result.fCurrent;
623    return result;
624}
625
626} // namespace
627