Line data Source code
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 :
30 0 : BlockId CFG::newBlock() {
31 0 : BlockId result = fBlocks.size();
32 0 : fBlocks.emplace_back();
33 0 : if (fBlocks.size() > 1) {
34 0 : this->addExit(fCurrent, result);
35 : }
36 0 : fCurrent = result;
37 0 : return result;
38 : }
39 :
40 0 : BlockId CFG::newIsolatedBlock() {
41 0 : BlockId result = fBlocks.size();
42 0 : fBlocks.emplace_back();
43 0 : return result;
44 : }
45 :
46 0 : void CFG::addExit(BlockId from, BlockId to) {
47 0 : if (from == 0 || fBlocks[from].fEntrances.size()) {
48 0 : fBlocks[from].fExits.insert(to);
49 0 : fBlocks[to].fEntrances.insert(from);
50 : }
51 0 : }
52 :
53 0 : void CFG::dump() {
54 0 : for (size_t i = 0; i < fBlocks.size(); i++) {
55 0 : printf("Block %d\n-------\nBefore: ", (int) i);
56 0 : const char* separator = "";
57 0 : for (auto iter = fBlocks[i].fBefore.begin(); iter != fBlocks[i].fBefore.end(); iter++) {
58 0 : printf("%s%s = %s", separator, iter->first->description().c_str(),
59 0 : *iter->second ? (*iter->second)->description().c_str() : "<undefined>");
60 0 : separator = ", ";
61 : }
62 0 : printf("\nEntrances: ");
63 0 : separator = "";
64 0 : for (BlockId b : fBlocks[i].fEntrances) {
65 0 : printf("%s%d", separator, (int) b);
66 0 : separator = ", ";
67 : }
68 0 : printf("\n");
69 0 : for (size_t j = 0; j < fBlocks[i].fNodes.size(); j++) {
70 0 : BasicBlock::Node& n = fBlocks[i].fNodes[j];
71 0 : printf("Node %d: %s\n", (int) j, n.fKind == BasicBlock::Node::kExpression_Kind
72 0 : ? (*n.fExpression)->description().c_str()
73 0 : : n.fStatement->description().c_str());
74 : }
75 0 : printf("Exits: ");
76 0 : separator = "";
77 0 : for (BlockId b : fBlocks[i].fExits) {
78 0 : printf("%s%d", separator, (int) b);
79 0 : separator = ", ";
80 : }
81 0 : printf("\n\n");
82 : }
83 0 : }
84 :
85 0 : void CFGGenerator::addExpression(CFG& cfg, std::unique_ptr<Expression>* e, bool constantPropagate) {
86 0 : ASSERT(e);
87 0 : switch ((*e)->fKind) {
88 : case Expression::kBinary_Kind: {
89 0 : BinaryExpression* b = (BinaryExpression*) e->get();
90 0 : 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 0 : this->addExpression(cfg, &b->fLeft, constantPropagate);
97 0 : BlockId start = cfg.fCurrent;
98 0 : cfg.newBlock();
99 0 : this->addExpression(cfg, &b->fRight, constantPropagate);
100 0 : cfg.newBlock();
101 0 : cfg.addExit(start, cfg.fCurrent);
102 0 : break;
103 : }
104 : case Token::EQ: {
105 0 : this->addExpression(cfg, &b->fRight, constantPropagate);
106 0 : this->addLValue(cfg, &b->fLeft);
107 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
108 : BasicBlock::Node::kExpression_Kind,
109 : constantPropagate,
110 : e,
111 : nullptr
112 0 : });
113 0 : break;
114 : }
115 : default:
116 0 : this->addExpression(cfg, &b->fLeft, !Token::IsAssignment(b->fOperator));
117 0 : this->addExpression(cfg, &b->fRight, constantPropagate);
118 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({
119 : BasicBlock::Node::kExpression_Kind,
120 : constantPropagate,
121 : e,
122 : nullptr
123 0 : });
124 : }
125 0 : break;
126 : }
127 : case Expression::kConstructor_Kind: {
128 0 : Constructor* c = (Constructor*) e->get();
129 0 : for (auto& arg : c->fArguments) {
130 0 : this->addExpression(cfg, &arg, constantPropagate);
131 : }
132 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
133 0 : constantPropagate, e, nullptr });
134 0 : break;
135 : }
136 : case Expression::kFunctionCall_Kind: {
137 0 : FunctionCall* c = (FunctionCall*) e->get();
138 0 : for (auto& arg : c->fArguments) {
139 0 : this->addExpression(cfg, &arg, constantPropagate);
140 : }
141 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
142 0 : constantPropagate, e, nullptr });
143 0 : break;
144 : }
145 : case Expression::kFieldAccess_Kind:
146 0 : this->addExpression(cfg, &((FieldAccess*) e->get())->fBase, constantPropagate);
147 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
148 0 : constantPropagate, e, nullptr });
149 0 : break;
150 : case Expression::kIndex_Kind:
151 0 : this->addExpression(cfg, &((IndexExpression*) e->get())->fBase, constantPropagate);
152 0 : this->addExpression(cfg, &((IndexExpression*) e->get())->fIndex, constantPropagate);
153 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
154 0 : constantPropagate, e, nullptr });
155 0 : break;
156 : case Expression::kPrefix_Kind: {
157 0 : PrefixExpression* p = (PrefixExpression*) e->get();
158 0 : this->addExpression(cfg, &p->fOperand, constantPropagate &&
159 0 : p->fOperator != Token::PLUSPLUS &&
160 0 : p->fOperator != Token::MINUSMINUS);
161 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
162 0 : constantPropagate, e, nullptr });
163 0 : break;
164 : }
165 : case Expression::kPostfix_Kind:
166 0 : this->addExpression(cfg, &((PostfixExpression*) e->get())->fOperand, false);
167 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
168 0 : constantPropagate, e, nullptr });
169 0 : break;
170 : case Expression::kSwizzle_Kind:
171 0 : this->addExpression(cfg, &((Swizzle*) e->get())->fBase, constantPropagate);
172 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
173 0 : constantPropagate, e, nullptr });
174 0 : 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 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpression_Kind,
180 0 : constantPropagate, e, nullptr });
181 0 : break;
182 : case Expression::kTernary_Kind: {
183 0 : TernaryExpression* t = (TernaryExpression*) e->get();
184 0 : this->addExpression(cfg, &t->fTest, constantPropagate);
185 0 : BlockId start = cfg.fCurrent;
186 0 : cfg.newBlock();
187 0 : this->addExpression(cfg, &t->fIfTrue, constantPropagate);
188 0 : BlockId next = cfg.newBlock();
189 0 : cfg.fCurrent = start;
190 0 : cfg.newBlock();
191 0 : this->addExpression(cfg, &t->fIfFalse, constantPropagate);
192 0 : cfg.addExit(cfg.fCurrent, next);
193 0 : cfg.fCurrent = next;
194 0 : break;
195 : }
196 : case Expression::kFunctionReference_Kind: // fall through
197 : case Expression::kTypeReference_Kind: // fall through
198 : case Expression::kDefined_Kind:
199 0 : ASSERT(false);
200 0 : break;
201 : }
202 0 : }
203 :
204 : // adds expressions that are evaluated as part of resolving an lvalue
205 0 : void CFGGenerator::addLValue(CFG& cfg, std::unique_ptr<Expression>* e) {
206 0 : switch ((*e)->fKind) {
207 : case Expression::kFieldAccess_Kind:
208 0 : this->addLValue(cfg, &((FieldAccess&) **e).fBase);
209 0 : break;
210 : case Expression::kIndex_Kind:
211 0 : this->addLValue(cfg, &((IndexExpression&) **e).fBase);
212 0 : this->addExpression(cfg, &((IndexExpression&) **e).fIndex, true);
213 0 : break;
214 : case Expression::kSwizzle_Kind:
215 0 : this->addLValue(cfg, &((Swizzle&) **e).fBase);
216 0 : break;
217 : case Expression::kVariableReference_Kind:
218 0 : break;
219 : default:
220 : // not an lvalue, can't happen
221 0 : ASSERT(false);
222 0 : break;
223 : }
224 0 : }
225 :
226 0 : void CFGGenerator::addStatement(CFG& cfg, const Statement* s) {
227 0 : switch (s->fKind) {
228 : case Statement::kBlock_Kind:
229 0 : for (const auto& child : ((const Block*) s)->fStatements) {
230 0 : addStatement(cfg, child.get());
231 : }
232 0 : break;
233 : case Statement::kIf_Kind: {
234 0 : IfStatement* ifs = (IfStatement*) s;
235 0 : this->addExpression(cfg, &ifs->fTest, true);
236 0 : BlockId start = cfg.fCurrent;
237 0 : cfg.newBlock();
238 0 : this->addStatement(cfg, ifs->fIfTrue.get());
239 0 : BlockId next = cfg.newBlock();
240 0 : if (ifs->fIfFalse) {
241 0 : cfg.fCurrent = start;
242 0 : cfg.newBlock();
243 0 : this->addStatement(cfg, ifs->fIfFalse.get());
244 0 : cfg.addExit(cfg.fCurrent, next);
245 0 : cfg.fCurrent = next;
246 : } else {
247 0 : cfg.addExit(start, next);
248 : }
249 0 : break;
250 : }
251 : case Statement::kExpression_Kind: {
252 0 : this->addExpression(cfg, &((ExpressionStatement&) *s).fExpression, true);
253 0 : break;
254 : }
255 : case Statement::kVarDeclarations_Kind: {
256 0 : VarDeclarationsStatement& decls = ((VarDeclarationsStatement&) *s);
257 0 : for (auto& vd : decls.fDeclaration->fVars) {
258 0 : if (vd.fValue) {
259 0 : this->addExpression(cfg, &vd.fValue, true);
260 : }
261 : }
262 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
263 0 : nullptr, s });
264 0 : break;
265 : }
266 : case Statement::kDiscard_Kind:
267 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
268 0 : nullptr, s });
269 0 : cfg.fCurrent = cfg.newIsolatedBlock();
270 0 : break;
271 : case Statement::kReturn_Kind: {
272 0 : ReturnStatement& r = ((ReturnStatement&) *s);
273 0 : if (r.fExpression) {
274 0 : this->addExpression(cfg, &r.fExpression, true);
275 : }
276 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
277 0 : nullptr, s });
278 0 : cfg.fCurrent = cfg.newIsolatedBlock();
279 0 : break;
280 : }
281 : case Statement::kBreak_Kind:
282 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
283 0 : nullptr, s });
284 0 : cfg.addExit(cfg.fCurrent, fLoopExits.top());
285 0 : cfg.fCurrent = cfg.newIsolatedBlock();
286 0 : break;
287 : case Statement::kContinue_Kind:
288 0 : cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStatement_Kind, false,
289 0 : nullptr, s });
290 0 : cfg.addExit(cfg.fCurrent, fLoopContinues.top());
291 0 : cfg.fCurrent = cfg.newIsolatedBlock();
292 0 : break;
293 : case Statement::kWhile_Kind: {
294 0 : WhileStatement* w = (WhileStatement*) s;
295 0 : BlockId loopStart = cfg.newBlock();
296 0 : fLoopContinues.push(loopStart);
297 0 : BlockId loopExit = cfg.newIsolatedBlock();
298 0 : fLoopExits.push(loopExit);
299 0 : this->addExpression(cfg, &w->fTest, true);
300 0 : BlockId test = cfg.fCurrent;
301 0 : cfg.addExit(test, loopExit);
302 0 : cfg.newBlock();
303 0 : this->addStatement(cfg, w->fStatement.get());
304 0 : cfg.addExit(cfg.fCurrent, loopStart);
305 0 : fLoopContinues.pop();
306 0 : fLoopExits.pop();
307 0 : cfg.fCurrent = loopExit;
308 0 : break;
309 : }
310 : case Statement::kDo_Kind: {
311 0 : DoStatement* d = (DoStatement*) s;
312 0 : BlockId loopStart = cfg.newBlock();
313 0 : fLoopContinues.push(loopStart);
314 0 : BlockId loopExit = cfg.newIsolatedBlock();
315 0 : fLoopExits.push(loopExit);
316 0 : this->addStatement(cfg, d->fStatement.get());
317 0 : this->addExpression(cfg, &d->fTest, true);
318 0 : cfg.addExit(cfg.fCurrent, loopExit);
319 0 : cfg.addExit(cfg.fCurrent, loopStart);
320 0 : fLoopContinues.pop();
321 0 : fLoopExits.pop();
322 0 : cfg.fCurrent = loopExit;
323 0 : break;
324 : }
325 : case Statement::kFor_Kind: {
326 0 : ForStatement* f = (ForStatement*) s;
327 0 : if (f->fInitializer) {
328 0 : this->addStatement(cfg, f->fInitializer.get());
329 : }
330 0 : BlockId loopStart = cfg.newBlock();
331 0 : BlockId next = cfg.newIsolatedBlock();
332 0 : fLoopContinues.push(next);
333 0 : BlockId loopExit = cfg.newIsolatedBlock();
334 0 : fLoopExits.push(loopExit);
335 0 : if (f->fTest) {
336 0 : this->addExpression(cfg, &f->fTest, true);
337 0 : BlockId test = cfg.fCurrent;
338 0 : cfg.addExit(test, loopExit);
339 : }
340 0 : cfg.newBlock();
341 0 : this->addStatement(cfg, f->fStatement.get());
342 0 : cfg.addExit(cfg.fCurrent, next);
343 0 : cfg.fCurrent = next;
344 0 : if (f->fNext) {
345 0 : this->addExpression(cfg, &f->fNext, true);
346 : }
347 0 : cfg.addExit(cfg.fCurrent, loopStart);
348 0 : fLoopContinues.pop();
349 0 : fLoopExits.pop();
350 0 : cfg.fCurrent = loopExit;
351 0 : break;
352 : }
353 : case Statement::kSwitch_Kind: {
354 0 : SwitchStatement* ss = (SwitchStatement*) s;
355 0 : this->addExpression(cfg, &ss->fValue, true);
356 0 : BlockId start = cfg.fCurrent;
357 0 : BlockId switchExit = cfg.newIsolatedBlock();
358 0 : fLoopExits.push(switchExit);
359 0 : for (const auto& c : ss->fCases) {
360 0 : cfg.newBlock();
361 0 : cfg.addExit(start, cfg.fCurrent);
362 0 : 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 0 : this->addExpression(cfg, &c->fValue, true);
366 : }
367 0 : for (const auto& caseStatement : c->fStatements) {
368 0 : this->addStatement(cfg, caseStatement.get());
369 : }
370 : }
371 0 : cfg.addExit(cfg.fCurrent, switchExit);
372 : // note that unlike GLSL, our grammar requires the default case to be last
373 0 : 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 0 : cfg.addExit(start, switchExit);
376 : }
377 0 : fLoopExits.pop();
378 0 : cfg.fCurrent = switchExit;
379 0 : break;
380 : }
381 : default:
382 0 : printf("statement: %s\n", s->description().c_str());
383 0 : ABORT("unsupported statement kind");
384 : }
385 0 : }
386 :
387 0 : CFG CFGGenerator::getCFG(const FunctionDefinition& f) {
388 0 : CFG result;
389 0 : result.fStart = result.newBlock();
390 0 : result.fCurrent = result.fStart;
391 0 : this->addStatement(result, f.fBody.get());
392 0 : result.newBlock();
393 0 : result.fExit = result.fCurrent;
394 0 : return result;
395 : }
396 :
397 : } // namespace
|
