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: %s\n", (int) j, n.fKind == BasicBlock::Node::kExpression_Kind
72                                                           ? (*n.fExpression)->description().c_str()
73                                                           : n.fStatement->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
85void CFGGenerator::addExpression(CFG& cfg, std::unique_ptr<Expression>* e, bool constantPropagate) {
86    ASSERT(e);
87    switch ((*e)->fKind) {
88        case Expression::kBinary_Kind: {
89            BinaryExpression* b = (BinaryExpression*) e->get();
90            switch (b->fOperator) {
91                case Token::LOGICALAND: // fall through
92                case Token::LOGICALOR: {
93                    // this isn't as precise as it could be -- we don't bother to track that if we
94                    // early exit from a logical and/or, we know which branch of an 'if' we're going
95                    // to hit -- but it won't make much difference in practice.
96                    this->addExpression(cfg, &b->fLeft, constantPropagate);
97                    BlockId start = cfg.fCurrent;
98                    cfg.newBlock();
99                    this->addExpression(cfg, &b->fRight, constantPropagate);
100                    cfg.newBlock();
101                    cfg.addExit(start, cfg.fCurrent);
102                    break;
103                }
104                case Token::EQ: {
105                    this->addExpression(cfg, &b->fRight, constantPropagate);
106                    this->addLValue(cfg, &b->fLeft);
107                    cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
108                        BasicBlock::Node::kExpression_Kind,
109                        constantPropagate,
110                        e,
111                        nullptr
112                    });
113                    break;
114                }
115                default:
116                    this->addExpression(cfg, &b->fLeft, !Token::IsAssignment(b->fOperator));
117                    this->addExpression(cfg, &b->fRight, constantPropagate);
118                    cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
119                        BasicBlock::Node::kExpression_Kind,
120                        constantPropagate,
121                        e,
122                        nullptr
123                    });
124            }
125            break;
126        }
127        case Expression::kConstructor_Kind: {
128            Constructor* c = (Constructor*) e->get();
129            for (auto& arg : c->fArguments) {
130                this->addExpression(cfg, &arg, constantPropagate);
131            }
132            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
133                                                         constantPropagate, e, nullptr });
134            break;
135        }
136        case Expression::kFunctionCall_Kind: {
137            FunctionCall* c = (FunctionCall*) e->get();
138            for (auto& arg : c->fArguments) {
139                this->addExpression(cfg, &arg, constantPropagate);
140            }
141            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
142                                                         constantPropagate, e, nullptr });
143            break;
144        }
145        case Expression::kFieldAccess_Kind:
146            this->addExpression(cfg, &((FieldAccess*) e->get())->fBase, constantPropagate);
147            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
148                                                         constantPropagate, e, nullptr });
149            break;
150        case Expression::kIndex_Kind:
151            this->addExpression(cfg, &((IndexExpression*) e->get())->fBase, constantPropagate);
152            this->addExpression(cfg, &((IndexExpression*) e->get())->fIndex, constantPropagate);
153            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
154                                                         constantPropagate, e, nullptr });
155            break;
156        case Expression::kPrefix_Kind: {
157            PrefixExpression* p = (PrefixExpression*) e->get();
158            this->addExpression(cfg, &p->fOperand, constantPropagate &&
159                                                   p->fOperator != Token::PLUSPLUS &&
160                                                   p->fOperator != Token::MINUSMINUS);
161            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
162                                                         constantPropagate, e, nullptr });
163            break;
164        }
165        case Expression::kPostfix_Kind:
166            this->addExpression(cfg, &((PostfixExpression*) e->get())->fOperand, false);
167            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
168                                                         constantPropagate, e, nullptr });
169            break;
170        case Expression::kSwizzle_Kind:
171            this->addExpression(cfg, &((Swizzle*) e->get())->fBase, constantPropagate);
172            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
173                                                         constantPropagate, e, nullptr });
174            break;
175        case Expression::kBoolLiteral_Kind:  // fall through
176        case Expression::kFloatLiteral_Kind: // fall through
177        case Expression::kIntLiteral_Kind:   // fall through
178        case Expression::kVariableReference_Kind:
179            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
180                                                         constantPropagate, e, nullptr });
181            break;
182        case Expression::kTernary_Kind: {
183            TernaryExpression* t = (TernaryExpression*) e->get();
184            this->addExpression(cfg, &t->fTest, constantPropagate);
185            BlockId start = cfg.fCurrent;
186            cfg.newBlock();
187            this->addExpression(cfg, &t->fIfTrue, constantPropagate);
188            BlockId next = cfg.newBlock();
189            cfg.fCurrent = start;
190            cfg.newBlock();
191            this->addExpression(cfg, &t->fIfFalse, constantPropagate);
192            cfg.addExit(cfg.fCurrent, next);
193            cfg.fCurrent = next;
194            break;
195        }
196        case Expression::kFunctionReference_Kind: // fall through
197        case Expression::kTypeReference_Kind:     // fall through
198        case Expression::kDefined_Kind:
199            ASSERT(false);
200            break;
201    }
202}
203
204// adds expressions that are evaluated as part of resolving an lvalue
205void CFGGenerator::addLValue(CFG& cfg, std::unique_ptr<Expression>* e) {
206    switch ((*e)->fKind) {
207        case Expression::kFieldAccess_Kind:
208            this->addLValue(cfg, &((FieldAccess&) **e).fBase);
209            break;
210        case Expression::kIndex_Kind:
211            this->addLValue(cfg, &((IndexExpression&) **e).fBase);
212            this->addExpression(cfg, &((IndexExpression&) **e).fIndex, true);
213            break;
214        case Expression::kSwizzle_Kind:
215            this->addLValue(cfg, &((Swizzle&) **e).fBase);
216            break;
217        case Expression::kVariableReference_Kind:
218            break;
219        default:
220            // not an lvalue, can't happen
221            ASSERT(false);
222            break;
223    }
224}
225
226void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
227    switch (s->fKind) {
228        case Statement::kBlock_Kind:
229            for (const auto& child : ((const Block*) s)->fStatements) {
230                addStatement(cfg, child.get());
231            }
232            break;
233        case Statement::kIf_Kind: {
234            IfStatement* ifs = (IfStatement*) s;
235            this->addExpression(cfg, &ifs->fTest, true);
236            BlockId start = cfg.fCurrent;
237            cfg.newBlock();
238            this->addStatement(cfg, ifs->fIfTrue.get());
239            BlockId next = cfg.newBlock();
240            if (ifs->fIfFalse) {
241                cfg.fCurrent = start;
242                cfg.newBlock();
243                this->addStatement(cfg, ifs->fIfFalse.get());
244                cfg.addExit(cfg.fCurrent, next);
245                cfg.fCurrent = next;
246            } else {
247                cfg.addExit(start, next);
248            }
249            break;
250        }
251        case Statement::kExpression_Kind: {
252            this->addExpression(cfg, &((ExpressionStatement&) *s).fExpression, true);
253            break;
254        }
255        case Statement::kVarDeclarations_Kind: {
256            VarDeclarationsStatement& decls = ((VarDeclarationsStatement&) *s);
257            for (auto& vd : decls.fDeclaration->fVars) {
258                if (vd.fValue) {
259                    this->addExpression(cfg, &vd.fValue, true);
260                }
261            }
262            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
263                                                         nullptr, s });
264            break;
265        }
266        case Statement::kDiscard_Kind:
267            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
268                                                         nullptr, s });
269            cfg.fCurrent = cfg.newIsolatedBlock();
270            break;
271        case Statement::kReturn_Kind: {
272            ReturnStatement& r = ((ReturnStatement&) *s);
273            if (r.fExpression) {
274                this->addExpression(cfg, &r.fExpression, true);
275            }
276            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
277                                                         nullptr, s });
278            cfg.fCurrent = cfg.newIsolatedBlock();
279            break;
280        }
281        case Statement::kBreak_Kind:
282            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
283                                                         nullptr, s });
284            cfg.addExit(cfg.fCurrent, fLoopExits.top());
285            cfg.fCurrent = cfg.newIsolatedBlock();
286            break;
287        case Statement::kContinue_Kind:
288            cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
289                                                         nullptr, s });
290            cfg.addExit(cfg.fCurrent, fLoopContinues.top());
291            cfg.fCurrent = cfg.newIsolatedBlock();
292            break;
293        case Statement::kWhile_Kind: {
294            WhileStatement* w = (WhileStatement*) s;
295            BlockId loopStart = cfg.newBlock();
296            fLoopContinues.push(loopStart);
297            BlockId loopExit = cfg.newIsolatedBlock();
298            fLoopExits.push(loopExit);
299            this->addExpression(cfg, &w->fTest, true);
300            BlockId test = cfg.fCurrent;
301            cfg.addExit(test, loopExit);
302            cfg.newBlock();
303            this->addStatement(cfg, w->fStatement.get());
304            cfg.addExit(cfg.fCurrent, loopStart);
305            fLoopContinues.pop();
306            fLoopExits.pop();
307            cfg.fCurrent = loopExit;
308            break;
309        }
310        case Statement::kDo_Kind: {
311            DoStatement* d = (DoStatement*) s;
312            BlockId loopStart = cfg.newBlock();
313            fLoopContinues.push(loopStart);
314            BlockId loopExit = cfg.newIsolatedBlock();
315            fLoopExits.push(loopExit);
316            this->addStatement(cfg, d->fStatement.get());
317            this->addExpression(cfg, &d->fTest, true);
318            cfg.addExit(cfg.fCurrent, loopExit);
319            cfg.addExit(cfg.fCurrent, loopStart);
320            fLoopContinues.pop();
321            fLoopExits.pop();
322            cfg.fCurrent = loopExit;
323            break;
324        }
325        case Statement::kFor_Kind: {
326            ForStatement* f = (ForStatement*) s;
327            if (f->fInitializer) {
328                this->addStatement(cfg, f->fInitializer.get());
329            }
330            BlockId loopStart = cfg.newBlock();
331            BlockId next = cfg.newIsolatedBlock();
332            fLoopContinues.push(next);
333            BlockId loopExit = cfg.newIsolatedBlock();
334            fLoopExits.push(loopExit);
335            if (f->fTest) {
336                this->addExpression(cfg, &f->fTest, true);
337                BlockId test = cfg.fCurrent;
338                cfg.addExit(test, loopExit);
339            }
340            cfg.newBlock();
341            this->addStatement(cfg, f->fStatement.get());
342            cfg.addExit(cfg.fCurrent, next);
343            cfg.fCurrent = next;
344            if (f->fNext) {
345                this->addExpression(cfg, &f->fNext, true);
346            }
347            cfg.addExit(cfg.fCurrent, loopStart);
348            fLoopContinues.pop();
349            fLoopExits.pop();
350            cfg.fCurrent = loopExit;
351            break;
352        }
353        case Statement::kSwitch_Kind: {
354            SwitchStatement* ss = (SwitchStatement*) s;
355            this->addExpression(cfg, &ss->fValue, true);
356            BlockId start = cfg.fCurrent;
357            BlockId switchExit = cfg.newIsolatedBlock();
358            fLoopExits.push(switchExit);
359            for (const auto& c : ss->fCases) {
360                cfg.newBlock();
361                cfg.addExit(start, cfg.fCurrent);
362                if (c->fValue) {
363                    // technically this should go in the start block, but it doesn't actually matter
364                    // because it must be constant. Not worth running two loops for.
365                    this->addExpression(cfg, &c->fValue, true);
366                }
367                for (const auto& caseStatement : c->fStatements) {
368                    this->addStatement(cfg, caseStatement.get());
369                }
370            }
371            cfg.addExit(cfg.fCurrent, switchExit);
372            // note that unlike GLSL, our grammar requires the default case to be last
373            if (0 == ss->fCases.size() || ss->fCases[ss->fCases.size() - 1]->fValue) {
374                // switch does not have a default clause, mark that it can skip straight to the end
375                cfg.addExit(start, switchExit);
376            }
377            fLoopExits.pop();
378            cfg.fCurrent = switchExit;
379            break;
380        }
381        default:
382            printf("statement: %s\n", s->description().c_str());
383            ABORT("unsupported statement kind");
384    }
385}
386
387CFG CFGGenerator::getCFG(const FunctionDefinition& f) {
388    CFG result;
389    result.fStart = result.newBlock();
390    result.fCurrent = result.fStart;
391    this->addStatement(result, f.fBody.get());
392    result.newBlock();
393    result.fExit = result.fCurrent;
394    return result;
395}
396
397} // namespace
398