1 /*
2 * Copyright 2016 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "SkSLCFGGenerator.h"
9
10 #include "ir/SkSLConstructor.h"
11 #include "ir/SkSLBinaryExpression.h"
12 #include "ir/SkSLDoStatement.h"
13 #include "ir/SkSLExpressionStatement.h"
14 #include "ir/SkSLFieldAccess.h"
15 #include "ir/SkSLForStatement.h"
16 #include "ir/SkSLFunctionCall.h"
17 #include "ir/SkSLIfStatement.h"
18 #include "ir/SkSLIndexExpression.h"
19 #include "ir/SkSLPostfixExpression.h"
20 #include "ir/SkSLPrefixExpression.h"
21 #include "ir/SkSLReturnStatement.h"
22 #include "ir/SkSLSwizzle.h"
23 #include "ir/SkSLSwitchStatement.h"
24 #include "ir/SkSLTernaryExpression.h"
25 #include "ir/SkSLVarDeclarationsStatement.h"
26 #include "ir/SkSLWhileStatement.h"
27
28 namespace SkSL {
29
newBlock()30 BlockId CFG::newBlock() {
31 BlockId result = fBlocks.size();
32 fBlocks.emplace_back();
33 if (fBlocks.size() > 1) {
34 this->addExit(fCurrent, result);
35 }
36 fCurrent = result;
37 return result;
38 }
39
newIsolatedBlock()40 BlockId CFG::newIsolatedBlock() {
41 BlockId result = fBlocks.size();
42 fBlocks.emplace_back();
43 return result;
44 }
45
addExit(BlockId from,BlockId to)46 void CFG::addExit(BlockId from, BlockId to) {
47 if (from == 0 || fBlocks[from].fEntrances.size()) {
48 fBlocks[from].fExits.insert(to);
49 fBlocks[to].fEntrances.insert(from);
50 }
51 }
52
dump()53 void CFG::dump() {
54 for (size_t i = 0; i < fBlocks.size(); i++) {
55 printf("Block %d\n-------\nBefore: ", (int) i);
56 const char* separator = "";
57 for (auto iter = fBlocks[i].fBefore.begin(); iter != fBlocks[i].fBefore.end(); iter++) {
58 printf("%s%s = %s", separator, iter->first->description().c_str(),
59 *iter->second ? (*iter->second)->description().c_str() : "<undefined>");
60 separator = ", ";
61 }
62 printf("\nEntrances: ");
63 separator = "";
64 for (BlockId b : fBlocks[i].fEntrances) {
65 printf("%s%d", separator, (int) b);
66 separator = ", ";
67 }
68 printf("\n");
69 for (size_t j = 0; j < fBlocks[i].fNodes.size(); j++) {
70 BasicBlock::Node& n = fBlocks[i].fNodes[j];
71 printf("Node %d: %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
addExpression(CFG & cfg,std::unique_ptr<Expression> * e,bool constantPropagate)85 void 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
addLValue(CFG & cfg,std::unique_ptr<Expression> * e)205 void 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
addStatement(CFG & cfg,const Statement * s)226 void 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
getCFG(const FunctionDefinition & f)387 CFG 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