OLD | NEW |
(Empty) | |
| 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/SkSLTernaryExpression.h" |
| 24 #include "ir/SkSLVarDeclarationsStatement.h" |
| 25 #include "ir/SkSLWhileStatement.h" |
| 26 |
| 27 namespace SkSL { |
| 28 |
| 29 BlockId CFG::newBlock() { |
| 30 BlockId result = fBlocks.size(); |
| 31 fBlocks.emplace_back(); |
| 32 if (fBlocks.size() > 1) { |
| 33 this->addExit(fCurrent, result); |
| 34 } |
| 35 fCurrent = result; |
| 36 return result; |
| 37 } |
| 38 |
| 39 BlockId CFG::newIsolatedBlock() { |
| 40 BlockId result = fBlocks.size(); |
| 41 fBlocks.emplace_back(); |
| 42 return result; |
| 43 } |
| 44 |
| 45 void CFG::addExit(BlockId from, BlockId to) { |
| 46 if (from == 0 || fBlocks[from].fEntrances.size()) { |
| 47 fBlocks[from].fExits.insert(to); |
| 48 fBlocks[to].fEntrances.insert(from); |
| 49 } |
| 50 } |
| 51 |
| 52 void CFG::dump() { |
| 53 for (size_t i = 0; i < fBlocks.size(); i++) { |
| 54 printf("Block %d\n-------\nBefore: ", (int) i); |
| 55 const char* separator = ""; |
| 56 for (auto iter = fBlocks[i].fBefore.begin(); iter != fBlocks[i].fBefore.
end(); iter++) { |
| 57 printf("%s%s = %s", separator, iter->first->description().c_str(), |
| 58 iter->second ? iter->second->description().c_str() : "<undefi
ned>"); |
| 59 separator = ", "; |
| 60 } |
| 61 printf("\nEntrances: "); |
| 62 separator = ""; |
| 63 for (BlockId b : fBlocks[i].fEntrances) { |
| 64 printf("%s%d", separator, (int) b); |
| 65 separator = ", "; |
| 66 } |
| 67 printf("\n"); |
| 68 for (size_t j = 0; j < fBlocks[i].fNodes.size(); j++) { |
| 69 printf("Node %d: %s\n", (int) j, fBlocks[i].fNodes[j].fNode->descrip
tion().c_str()); |
| 70 } |
| 71 printf("Exits: "); |
| 72 separator = ""; |
| 73 for (BlockId b : fBlocks[i].fExits) { |
| 74 printf("%s%d", separator, (int) b); |
| 75 separator = ", "; |
| 76 } |
| 77 printf("\n\n"); |
| 78 } |
| 79 } |
| 80 |
| 81 void CFGGenerator::addExpression(CFG& cfg, const Expression* e) { |
| 82 switch (e->fKind) { |
| 83 case Expression::kBinary_Kind: { |
| 84 const BinaryExpression* b = (const BinaryExpression*) e; |
| 85 switch (b->fOperator) { |
| 86 case Token::LOGICALAND: // fall through |
| 87 case Token::LOGICALOR: { |
| 88 // this isn't as precise as it could be -- we don't bother t
o track that if we |
| 89 // early exit from a logical and/or, we know which branch of
an 'if' we're going |
| 90 // to hit -- but it won't make much difference in practice. |
| 91 this->addExpression(cfg, b->fLeft.get()); |
| 92 BlockId start = cfg.fCurrent; |
| 93 cfg.newBlock(); |
| 94 this->addExpression(cfg, b->fRight.get()); |
| 95 cfg.newBlock(); |
| 96 cfg.addExit(start, cfg.fCurrent); |
| 97 break; |
| 98 } |
| 99 case Token::EQ: { |
| 100 this->addExpression(cfg, b->fRight.get()); |
| 101 this->addLValue(cfg, b->fLeft.get()); |
| 102 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ |
| 103 BasicBlock::Node::kExpression_Kind, |
| 104 b |
| 105 }); |
| 106 break; |
| 107 } |
| 108 default: |
| 109 this->addExpression(cfg, b->fLeft.get()); |
| 110 this->addExpression(cfg, b->fRight.get()); |
| 111 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ |
| 112 BasicBlock::Node::kExpression_Kind, |
| 113 b |
| 114 }); |
| 115 } |
| 116 break; |
| 117 } |
| 118 case Expression::kConstructor_Kind: { |
| 119 const Constructor* c = (const Constructor*) e; |
| 120 for (const auto& arg : c->fArguments) { |
| 121 this->addExpression(cfg, arg.get()); |
| 122 } |
| 123 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpr
ession_Kind, c }); |
| 124 break; |
| 125 } |
| 126 case Expression::kFunctionCall_Kind: { |
| 127 const FunctionCall* c = (const FunctionCall*) e; |
| 128 for (const auto& arg : c->fArguments) { |
| 129 this->addExpression(cfg, arg.get()); |
| 130 } |
| 131 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpr
ession_Kind, c }); |
| 132 break; |
| 133 } |
| 134 case Expression::kFieldAccess_Kind: |
| 135 this->addExpression(cfg, ((const FieldAccess*) e)->fBase.get()); |
| 136 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpr
ession_Kind, e }); |
| 137 break; |
| 138 case Expression::kIndex_Kind: |
| 139 this->addExpression(cfg, ((const IndexExpression*) e)->fBase.get()); |
| 140 this->addExpression(cfg, ((const IndexExpression*) e)->fIndex.get())
; |
| 141 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpr
ession_Kind, e }); |
| 142 break; |
| 143 case Expression::kPrefix_Kind: |
| 144 this->addExpression(cfg, ((const PrefixExpression*) e)->fOperand.get
()); |
| 145 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpr
ession_Kind, e }); |
| 146 break; |
| 147 case Expression::kPostfix_Kind: |
| 148 this->addExpression(cfg, ((const PostfixExpression*) e)->fOperand.ge
t()); |
| 149 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpr
ession_Kind, e }); |
| 150 break; |
| 151 case Expression::kSwizzle_Kind: |
| 152 this->addExpression(cfg, ((const Swizzle*) e)->fBase.get()); |
| 153 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpr
ession_Kind, e }); |
| 154 break; |
| 155 case Expression::kBoolLiteral_Kind: // fall through |
| 156 case Expression::kFloatLiteral_Kind: // fall through |
| 157 case Expression::kIntLiteral_Kind: // fall through |
| 158 case Expression::kVariableReference_Kind: |
| 159 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kExpr
ession_Kind, e }); |
| 160 break; |
| 161 case Expression::kTernary_Kind: { |
| 162 const TernaryExpression* t = (const TernaryExpression*) e; |
| 163 this->addExpression(cfg, t->fTest.get()); |
| 164 BlockId start = cfg.fCurrent; |
| 165 cfg.newBlock(); |
| 166 this->addExpression(cfg, t->fIfTrue.get()); |
| 167 BlockId next = cfg.newBlock(); |
| 168 cfg.fCurrent = start; |
| 169 cfg.newBlock(); |
| 170 this->addExpression(cfg, t->fIfFalse.get()); |
| 171 cfg.addExit(cfg.fCurrent, next); |
| 172 cfg.fCurrent = next; |
| 173 break; |
| 174 } |
| 175 case Expression::kFunctionReference_Kind: // fall through |
| 176 case Expression::kTypeReference_Kind: // fall through |
| 177 case Expression::kDefined_Kind: |
| 178 ASSERT(false); |
| 179 break; |
| 180 } |
| 181 } |
| 182 |
| 183 // adds expressions that are evaluated as part of resolving an lvalue |
| 184 void CFGGenerator::addLValue(CFG& cfg, const Expression* e) { |
| 185 switch (e->fKind) { |
| 186 case Expression::kFieldAccess_Kind: |
| 187 this->addLValue(cfg, ((const FieldAccess*) e)->fBase.get()); |
| 188 break; |
| 189 case Expression::kIndex_Kind: |
| 190 this->addLValue(cfg, ((const IndexExpression*) e)->fBase.get()); |
| 191 this->addExpression(cfg, ((const IndexExpression*) e)->fIndex.get())
; |
| 192 break; |
| 193 case Expression::kSwizzle_Kind: |
| 194 this->addLValue(cfg, ((const Swizzle*) e)->fBase.get()); |
| 195 break; |
| 196 case Expression::kVariableReference_Kind: |
| 197 break; |
| 198 default: |
| 199 // not an lvalue, can't happen |
| 200 ASSERT(false); |
| 201 break; |
| 202 } |
| 203 } |
| 204 |
| 205 void CFGGenerator::addStatement(CFG& cfg, const Statement* s) { |
| 206 switch (s->fKind) { |
| 207 case Statement::kBlock_Kind: |
| 208 for (const auto& child : ((const Block*) s)->fStatements) { |
| 209 addStatement(cfg, child.get()); |
| 210 } |
| 211 break; |
| 212 case Statement::kIf_Kind: { |
| 213 const IfStatement* ifs = (const IfStatement*) s; |
| 214 this->addExpression(cfg, ifs->fTest.get()); |
| 215 BlockId start = cfg.fCurrent; |
| 216 cfg.newBlock(); |
| 217 this->addStatement(cfg, ifs->fIfTrue.get()); |
| 218 BlockId next = cfg.newBlock(); |
| 219 if (ifs->fIfFalse) { |
| 220 cfg.fCurrent = start; |
| 221 cfg.newBlock(); |
| 222 this->addStatement(cfg, ifs->fIfFalse.get()); |
| 223 cfg.addExit(cfg.fCurrent, next); |
| 224 cfg.fCurrent = next; |
| 225 } else { |
| 226 cfg.addExit(start, next); |
| 227 } |
| 228 break; |
| 229 } |
| 230 case Statement::kExpression_Kind: { |
| 231 this->addExpression(cfg, ((ExpressionStatement&) *s).fExpression.get
()); |
| 232 break; |
| 233 } |
| 234 case Statement::kVarDeclarations_Kind: { |
| 235 const VarDeclarationsStatement& decls = ((VarDeclarationsStatement&)
*s); |
| 236 for (const auto& vd : decls.fDeclaration->fVars) { |
| 237 if (vd.fValue) { |
| 238 this->addExpression(cfg, vd.fValue.get()); |
| 239 } |
| 240 } |
| 241 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStat
ement_Kind, s }); |
| 242 break; |
| 243 } |
| 244 case Statement::kDiscard_Kind: |
| 245 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStat
ement_Kind, s }); |
| 246 cfg.fCurrent = cfg.newIsolatedBlock(); |
| 247 break; |
| 248 case Statement::kReturn_Kind: { |
| 249 const ReturnStatement& r = ((ReturnStatement&) *s); |
| 250 if (r.fExpression) { |
| 251 this->addExpression(cfg, r.fExpression.get()); |
| 252 } |
| 253 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStat
ement_Kind, s }); |
| 254 cfg.fCurrent = cfg.newIsolatedBlock(); |
| 255 break; |
| 256 } |
| 257 case Statement::kBreak_Kind: |
| 258 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStat
ement_Kind, s }); |
| 259 cfg.addExit(cfg.fCurrent, fLoopExits.top()); |
| 260 cfg.fCurrent = cfg.newIsolatedBlock(); |
| 261 break; |
| 262 case Statement::kContinue_Kind: |
| 263 cfg.fBlocks[cfg.fCurrent].fNodes.push_back({ BasicBlock::Node::kStat
ement_Kind, s }); |
| 264 cfg.addExit(cfg.fCurrent, fLoopContinues.top()); |
| 265 cfg.fCurrent = cfg.newIsolatedBlock(); |
| 266 break; |
| 267 case Statement::kWhile_Kind: { |
| 268 const WhileStatement* w = (const WhileStatement*) s; |
| 269 BlockId loopStart = cfg.newBlock(); |
| 270 fLoopContinues.push(loopStart); |
| 271 BlockId loopExit = cfg.newIsolatedBlock(); |
| 272 fLoopExits.push(loopExit); |
| 273 this->addExpression(cfg, w->fTest.get()); |
| 274 BlockId test = cfg.fCurrent; |
| 275 cfg.addExit(test, loopExit); |
| 276 cfg.newBlock(); |
| 277 this->addStatement(cfg, w->fStatement.get()); |
| 278 cfg.addExit(cfg.fCurrent, loopStart); |
| 279 fLoopContinues.pop(); |
| 280 fLoopExits.pop(); |
| 281 cfg.fCurrent = loopExit; |
| 282 break; |
| 283 } |
| 284 case Statement::kDo_Kind: { |
| 285 const DoStatement* d = (const DoStatement*) s; |
| 286 BlockId loopStart = cfg.newBlock(); |
| 287 fLoopContinues.push(loopStart); |
| 288 BlockId loopExit = cfg.newIsolatedBlock(); |
| 289 fLoopExits.push(loopExit); |
| 290 this->addStatement(cfg, d->fStatement.get()); |
| 291 this->addExpression(cfg, d->fTest.get()); |
| 292 cfg.addExit(cfg.fCurrent, loopExit); |
| 293 cfg.addExit(cfg.fCurrent, loopStart); |
| 294 fLoopContinues.pop(); |
| 295 fLoopExits.pop(); |
| 296 cfg.fCurrent = loopExit; |
| 297 break; |
| 298 } |
| 299 case Statement::kFor_Kind: { |
| 300 const ForStatement* f = (const ForStatement*) s; |
| 301 if (f->fInitializer) { |
| 302 this->addStatement(cfg, f->fInitializer.get()); |
| 303 } |
| 304 BlockId loopStart = cfg.newBlock(); |
| 305 BlockId next = cfg.newIsolatedBlock(); |
| 306 fLoopContinues.push(next); |
| 307 BlockId loopExit = cfg.newIsolatedBlock(); |
| 308 fLoopExits.push(loopExit); |
| 309 if (f->fTest) { |
| 310 this->addExpression(cfg, f->fTest.get()); |
| 311 BlockId test = cfg.fCurrent; |
| 312 cfg.addExit(test, loopExit); |
| 313 } |
| 314 cfg.newBlock(); |
| 315 this->addStatement(cfg, f->fStatement.get()); |
| 316 cfg.addExit(cfg.fCurrent, next); |
| 317 cfg.fCurrent = next; |
| 318 if (f->fNext) { |
| 319 this->addExpression(cfg, f->fNext.get()); |
| 320 } |
| 321 cfg.addExit(next, loopStart); |
| 322 fLoopContinues.pop(); |
| 323 fLoopExits.pop(); |
| 324 cfg.fCurrent = loopExit; |
| 325 break; |
| 326 } |
| 327 default: |
| 328 printf("statement: %s\n", s->description().c_str()); |
| 329 ABORT("unsupported statement kind"); |
| 330 } |
| 331 } |
| 332 |
| 333 CFG CFGGenerator::getCFG(const FunctionDefinition& f) { |
| 334 CFG result; |
| 335 result.fStart = result.newBlock(); |
| 336 result.fCurrent = result.fStart; |
| 337 this->addStatement(result, f.fBody.get()); |
| 338 result.newBlock(); |
| 339 result.fExit = result.fCurrent; |
| 340 return result; |
| 341 } |
| 342 |
| 343 } // namespace |
OLD | NEW |