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