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 "SkSLCompiler.h" 9 10 #include "SkSLCFGGenerator.h" 11 #include "SkSLCPPCodeGenerator.h" 12 #include "SkSLGLSLCodeGenerator.h" 13 #include "SkSLHCodeGenerator.h" 14 #include "SkSLIRGenerator.h" 15 #include "SkSLSPIRVCodeGenerator.h" 16 #include "ir/SkSLExpression.h" 17 #include "ir/SkSLExpressionStatement.h" 18 #include "ir/SkSLIntLiteral.h" 19 #include "ir/SkSLModifiersDeclaration.h" 20 #include "ir/SkSLNop.h" 21 #include "ir/SkSLSymbolTable.h" 22 #include "ir/SkSLTernaryExpression.h" 23 #include "ir/SkSLUnresolvedFunction.h" 24 #include "ir/SkSLVarDeclarations.h" 25 26 #ifdef SK_ENABLE_SPIRV_VALIDATION 27 #include "spirv-tools/libspirv.hpp" 28 #endif 29 30 #define STRINGIFY(x) #x 31 32 // include the built-in shader symbols as static strings 33 34 static const char* SKSL_INCLUDE = 35 #include "sksl.include" 36 ; 37 38 static const char* SKSL_VERT_INCLUDE = 39 #include "sksl_vert.include" 40 ; 41 42 static const char* SKSL_FRAG_INCLUDE = 43 #include "sksl_frag.include" 44 ; 45 46 static const char* SKSL_GEOM_INCLUDE = 47 #include "sksl_geom.include" 48 ; 49 50 static const char* SKSL_FP_INCLUDE = 51 #include "sksl_fp.include" 52 ; 53 54 55 namespace SkSL { 56 57 Compiler::Compiler(Flags flags) 58 : fFlags(flags) 59 , fErrorCount(0) { 60 auto types = std::shared_ptr<SymbolTable>(new SymbolTable(this)); 61 auto symbols = std::shared_ptr<SymbolTable>(new SymbolTable(types, this)); 62 fIRGenerator = new IRGenerator(&fContext, symbols, *this); 63 fTypes = types; 64 #define ADD_TYPE(t) types->addWithoutOwnership(fContext.f ## t ## _Type->fName, \ 65 fContext.f ## t ## _Type.get()) 66 ADD_TYPE(Void); 67 ADD_TYPE(Float); 68 ADD_TYPE(Vec2); 69 ADD_TYPE(Vec3); 70 ADD_TYPE(Vec4); 71 ADD_TYPE(Double); 72 ADD_TYPE(DVec2); 73 ADD_TYPE(DVec3); 74 ADD_TYPE(DVec4); 75 ADD_TYPE(Int); 76 ADD_TYPE(IVec2); 77 ADD_TYPE(IVec3); 78 ADD_TYPE(IVec4); 79 ADD_TYPE(UInt); 80 ADD_TYPE(UVec2); 81 ADD_TYPE(UVec3); 82 ADD_TYPE(UVec4); 83 ADD_TYPE(Bool); 84 ADD_TYPE(BVec2); 85 ADD_TYPE(BVec3); 86 ADD_TYPE(BVec4); 87 ADD_TYPE(Mat2x2); 88 types->addWithoutOwnership(String("mat2x2"), fContext.fMat2x2_Type.get()); 89 ADD_TYPE(Mat2x3); 90 ADD_TYPE(Mat2x4); 91 ADD_TYPE(Mat3x2); 92 ADD_TYPE(Mat3x3); 93 types->addWithoutOwnership(String("mat3x3"), fContext.fMat3x3_Type.get()); 94 ADD_TYPE(Mat3x4); 95 ADD_TYPE(Mat4x2); 96 ADD_TYPE(Mat4x3); 97 ADD_TYPE(Mat4x4); 98 types->addWithoutOwnership(String("mat4x4"), fContext.fMat4x4_Type.get()); 99 ADD_TYPE(GenType); 100 ADD_TYPE(GenDType); 101 ADD_TYPE(GenIType); 102 ADD_TYPE(GenUType); 103 ADD_TYPE(GenBType); 104 ADD_TYPE(Mat); 105 ADD_TYPE(Vec); 106 ADD_TYPE(GVec); 107 ADD_TYPE(GVec2); 108 ADD_TYPE(GVec3); 109 ADD_TYPE(GVec4); 110 ADD_TYPE(DVec); 111 ADD_TYPE(IVec); 112 ADD_TYPE(UVec); 113 ADD_TYPE(BVec); 114 115 ADD_TYPE(Sampler1D); 116 ADD_TYPE(Sampler2D); 117 ADD_TYPE(Sampler3D); 118 ADD_TYPE(SamplerExternalOES); 119 ADD_TYPE(SamplerCube); 120 ADD_TYPE(Sampler2DRect); 121 ADD_TYPE(Sampler1DArray); 122 ADD_TYPE(Sampler2DArray); 123 ADD_TYPE(SamplerCubeArray); 124 ADD_TYPE(SamplerBuffer); 125 ADD_TYPE(Sampler2DMS); 126 ADD_TYPE(Sampler2DMSArray); 127 128 ADD_TYPE(ISampler2D); 129 130 ADD_TYPE(Image2D); 131 ADD_TYPE(IImage2D); 132 133 ADD_TYPE(SubpassInput); 134 ADD_TYPE(SubpassInputMS); 135 136 ADD_TYPE(GSampler1D); 137 ADD_TYPE(GSampler2D); 138 ADD_TYPE(GSampler3D); 139 ADD_TYPE(GSamplerCube); 140 ADD_TYPE(GSampler2DRect); 141 ADD_TYPE(GSampler1DArray); 142 ADD_TYPE(GSampler2DArray); 143 ADD_TYPE(GSamplerCubeArray); 144 ADD_TYPE(GSamplerBuffer); 145 ADD_TYPE(GSampler2DMS); 146 ADD_TYPE(GSampler2DMSArray); 147 148 ADD_TYPE(Sampler1DShadow); 149 ADD_TYPE(Sampler2DShadow); 150 ADD_TYPE(SamplerCubeShadow); 151 ADD_TYPE(Sampler2DRectShadow); 152 ADD_TYPE(Sampler1DArrayShadow); 153 ADD_TYPE(Sampler2DArrayShadow); 154 ADD_TYPE(SamplerCubeArrayShadow); 155 ADD_TYPE(GSampler2DArrayShadow); 156 ADD_TYPE(GSamplerCubeArrayShadow); 157 ADD_TYPE(ColorSpaceXform); 158 159 String skCapsName("sk_Caps"); 160 Variable* skCaps = new Variable(Position(), Modifiers(), skCapsName, 161 *fContext.fSkCaps_Type, Variable::kGlobal_Storage); 162 fIRGenerator->fSymbolTable->add(skCapsName, std::unique_ptr<Symbol>(skCaps)); 163 164 String skArgsName("sk_Args"); 165 Variable* skArgs = new Variable(Position(), Modifiers(), skArgsName, 166 *fContext.fSkArgs_Type, Variable::kGlobal_Storage); 167 fIRGenerator->fSymbolTable->add(skArgsName, std::unique_ptr<Symbol>(skArgs)); 168 169 Modifiers::Flag ignored1; 170 std::vector<std::unique_ptr<ProgramElement>> ignored2; 171 fIRGenerator->convertProgram(String(SKSL_INCLUDE), *fTypes, &ignored1, &ignored2); 172 fIRGenerator->fSymbolTable->markAllFunctionsBuiltin(); 173 ASSERT(!fErrorCount); 174 } 175 176 Compiler::~Compiler() { 177 delete fIRGenerator; 178 } 179 180 // add the definition created by assigning to the lvalue to the definition set 181 void Compiler::addDefinition(const Expression* lvalue, std::unique_ptr<Expression>* expr, 182 DefinitionMap* definitions) { 183 switch (lvalue->fKind) { 184 case Expression::kVariableReference_Kind: { 185 const Variable& var = ((VariableReference*) lvalue)->fVariable; 186 if (var.fStorage == Variable::kLocal_Storage) { 187 (*definitions)[&var] = expr; 188 } 189 break; 190 } 191 case Expression::kSwizzle_Kind: 192 // We consider the variable written to as long as at least some of its components have 193 // been written to. This will lead to some false negatives (we won't catch it if you 194 // write to foo.x and then read foo.y), but being stricter could lead to false positives 195 // (we write to foo.x, and then pass foo to a function which happens to only read foo.x, 196 // but since we pass foo as a whole it is flagged as an error) unless we perform a much 197 // more complicated whole-program analysis. This is probably good enough. 198 this->addDefinition(((Swizzle*) lvalue)->fBase.get(), 199 (std::unique_ptr<Expression>*) &fContext.fDefined_Expression, 200 definitions); 201 break; 202 case Expression::kIndex_Kind: 203 // see comments in Swizzle 204 this->addDefinition(((IndexExpression*) lvalue)->fBase.get(), 205 (std::unique_ptr<Expression>*) &fContext.fDefined_Expression, 206 definitions); 207 break; 208 case Expression::kFieldAccess_Kind: 209 // see comments in Swizzle 210 this->addDefinition(((FieldAccess*) lvalue)->fBase.get(), 211 (std::unique_ptr<Expression>*) &fContext.fDefined_Expression, 212 definitions); 213 break; 214 default: 215 // not an lvalue, can't happen 216 ASSERT(false); 217 } 218 } 219 220 // add local variables defined by this node to the set 221 void Compiler::addDefinitions(const BasicBlock::Node& node, 222 DefinitionMap* definitions) { 223 switch (node.fKind) { 224 case BasicBlock::Node::kExpression_Kind: { 225 ASSERT(node.expression()); 226 const Expression* expr = (Expression*) node.expression()->get(); 227 switch (expr->fKind) { 228 case Expression::kBinary_Kind: { 229 BinaryExpression* b = (BinaryExpression*) expr; 230 if (b->fOperator == Token::EQ) { 231 this->addDefinition(b->fLeft.get(), &b->fRight, definitions); 232 } else if (Token::IsAssignment(b->fOperator)) { 233 this->addDefinition( 234 b->fLeft.get(), 235 (std::unique_ptr<Expression>*) &fContext.fDefined_Expression, 236 definitions); 237 238 } 239 break; 240 } 241 case Expression::kPrefix_Kind: { 242 const PrefixExpression* p = (PrefixExpression*) expr; 243 if (p->fOperator == Token::MINUSMINUS || p->fOperator == Token::PLUSPLUS) { 244 this->addDefinition( 245 p->fOperand.get(), 246 (std::unique_ptr<Expression>*) &fContext.fDefined_Expression, 247 definitions); 248 } 249 break; 250 } 251 case Expression::kPostfix_Kind: { 252 const PostfixExpression* p = (PostfixExpression*) expr; 253 if (p->fOperator == Token::MINUSMINUS || p->fOperator == Token::PLUSPLUS) { 254 this->addDefinition( 255 p->fOperand.get(), 256 (std::unique_ptr<Expression>*) &fContext.fDefined_Expression, 257 definitions); 258 } 259 break; 260 } 261 case Expression::kVariableReference_Kind: { 262 const VariableReference* v = (VariableReference*) expr; 263 if (v->fRefKind != VariableReference::kRead_RefKind) { 264 this->addDefinition( 265 v, 266 (std::unique_ptr<Expression>*) &fContext.fDefined_Expression, 267 definitions); 268 } 269 } 270 default: 271 break; 272 } 273 break; 274 } 275 case BasicBlock::Node::kStatement_Kind: { 276 const Statement* stmt = (Statement*) node.statement()->get(); 277 if (stmt->fKind == Statement::kVarDeclaration_Kind) { 278 VarDeclaration& vd = (VarDeclaration&) *stmt; 279 if (vd.fValue) { 280 (*definitions)[vd.fVar] = &vd.fValue; 281 } 282 } 283 break; 284 } 285 } 286 } 287 288 void Compiler::scanCFG(CFG* cfg, BlockId blockId, std::set<BlockId>* workList) { 289 BasicBlock& block = cfg->fBlocks[blockId]; 290 291 // compute definitions after this block 292 DefinitionMap after = block.fBefore; 293 for (const BasicBlock::Node& n : block.fNodes) { 294 this->addDefinitions(n, &after); 295 } 296 297 // propagate definitions to exits 298 for (BlockId exitId : block.fExits) { 299 BasicBlock& exit = cfg->fBlocks[exitId]; 300 for (const auto& pair : after) { 301 std::unique_ptr<Expression>* e1 = pair.second; 302 auto found = exit.fBefore.find(pair.first); 303 if (found == exit.fBefore.end()) { 304 // exit has no definition for it, just copy it 305 workList->insert(exitId); 306 exit.fBefore[pair.first] = e1; 307 } else { 308 // exit has a (possibly different) value already defined 309 std::unique_ptr<Expression>* e2 = exit.fBefore[pair.first]; 310 if (e1 != e2) { 311 // definition has changed, merge and add exit block to worklist 312 workList->insert(exitId); 313 if (e1 && e2) { 314 exit.fBefore[pair.first] = 315 (std::unique_ptr<Expression>*) &fContext.fDefined_Expression; 316 } else { 317 exit.fBefore[pair.first] = nullptr; 318 } 319 } 320 } 321 } 322 } 323 } 324 325 // returns a map which maps all local variables in the function to null, indicating that their value 326 // is initially unknown 327 static DefinitionMap compute_start_state(const CFG& cfg) { 328 DefinitionMap result; 329 for (const auto& block : cfg.fBlocks) { 330 for (const auto& node : block.fNodes) { 331 if (node.fKind == BasicBlock::Node::kStatement_Kind) { 332 ASSERT(node.statement()); 333 const Statement* s = node.statement()->get(); 334 if (s->fKind == Statement::kVarDeclarations_Kind) { 335 const VarDeclarationsStatement* vd = (const VarDeclarationsStatement*) s; 336 for (const auto& decl : vd->fDeclaration->fVars) { 337 if (decl->fKind == Statement::kVarDeclaration_Kind) { 338 result[((VarDeclaration&) *decl).fVar] = nullptr; 339 } 340 } 341 } 342 } 343 } 344 } 345 return result; 346 } 347 348 /** 349 * Returns true if assigning to this lvalue has no effect. 350 */ 351 static bool is_dead(const Expression& lvalue) { 352 switch (lvalue.fKind) { 353 case Expression::kVariableReference_Kind: 354 return ((VariableReference&) lvalue).fVariable.dead(); 355 case Expression::kSwizzle_Kind: 356 return is_dead(*((Swizzle&) lvalue).fBase); 357 case Expression::kFieldAccess_Kind: 358 return is_dead(*((FieldAccess&) lvalue).fBase); 359 case Expression::kIndex_Kind: { 360 const IndexExpression& idx = (IndexExpression&) lvalue; 361 return is_dead(*idx.fBase) && !idx.fIndex->hasSideEffects(); 362 } 363 default: 364 ABORT("invalid lvalue: %s\n", lvalue.description().c_str()); 365 } 366 } 367 368 /** 369 * Returns true if this is an assignment which can be collapsed down to just the right hand side due 370 * to a dead target and lack of side effects on the left hand side. 371 */ 372 static bool dead_assignment(const BinaryExpression& b) { 373 if (!Token::IsAssignment(b.fOperator)) { 374 return false; 375 } 376 return is_dead(*b.fLeft); 377 } 378 379 void Compiler::computeDataFlow(CFG* cfg) { 380 cfg->fBlocks[cfg->fStart].fBefore = compute_start_state(*cfg); 381 std::set<BlockId> workList; 382 for (BlockId i = 0; i < cfg->fBlocks.size(); i++) { 383 workList.insert(i); 384 } 385 while (workList.size()) { 386 BlockId next = *workList.begin(); 387 workList.erase(workList.begin()); 388 this->scanCFG(cfg, next, &workList); 389 } 390 } 391 392 /** 393 * Attempts to replace the expression pointed to by iter with a new one (in both the CFG and the 394 * IR). If the expression can be cleanly removed, returns true and updates the iterator to point to 395 * the newly-inserted element. Otherwise updates only the IR and returns false (and the CFG will 396 * need to be regenerated). 397 */ 398 bool try_replace_expression(BasicBlock* b, 399 std::vector<BasicBlock::Node>::iterator* iter, 400 std::unique_ptr<Expression>* newExpression) { 401 std::unique_ptr<Expression>* target = (*iter)->expression(); 402 if (!b->tryRemoveExpression(iter)) { 403 *target = std::move(*newExpression); 404 return false; 405 } 406 *target = std::move(*newExpression); 407 return b->tryInsertExpression(iter, target); 408 } 409 410 /** 411 * Returns true if the expression is a constant numeric literal with the specified value, or a 412 * constant vector with all elements equal to the specified value. 413 */ 414 bool is_constant(const Expression& expr, double value) { 415 switch (expr.fKind) { 416 case Expression::kIntLiteral_Kind: 417 return ((IntLiteral&) expr).fValue == value; 418 case Expression::kFloatLiteral_Kind: 419 return ((FloatLiteral&) expr).fValue == value; 420 case Expression::kConstructor_Kind: { 421 Constructor& c = (Constructor&) expr; 422 if (c.fType.kind() == Type::kVector_Kind && c.isConstant()) { 423 for (int i = 0; i < c.fType.columns(); ++i) { 424 if (!is_constant(c.getVecComponent(i), value)) { 425 return false; 426 } 427 } 428 return true; 429 } 430 return false; 431 } 432 default: 433 return false; 434 } 435 } 436 437 /** 438 * Collapses the binary expression pointed to by iter down to just the right side (in both the IR 439 * and CFG structures). 440 */ 441 void delete_left(BasicBlock* b, 442 std::vector<BasicBlock::Node>::iterator* iter, 443 bool* outUpdated, 444 bool* outNeedsRescan) { 445 *outUpdated = true; 446 std::unique_ptr<Expression>* target = (*iter)->expression(); 447 ASSERT((*target)->fKind == Expression::kBinary_Kind); 448 BinaryExpression& bin = (BinaryExpression&) **target; 449 bool result; 450 if (bin.fOperator == Token::EQ) { 451 result = b->tryRemoveLValueBefore(iter, bin.fLeft.get()); 452 } else { 453 result = b->tryRemoveExpressionBefore(iter, bin.fLeft.get()); 454 } 455 *target = std::move(bin.fRight); 456 if (!result) { 457 *outNeedsRescan = true; 458 return; 459 } 460 if (*iter == b->fNodes.begin()) { 461 *outNeedsRescan = true; 462 return; 463 } 464 --(*iter); 465 if ((*iter)->fKind != BasicBlock::Node::kExpression_Kind || 466 (*iter)->expression() != &bin.fRight) { 467 *outNeedsRescan = true; 468 return; 469 } 470 *iter = b->fNodes.erase(*iter); 471 ASSERT((*iter)->expression() == target); 472 } 473 474 /** 475 * Collapses the binary expression pointed to by iter down to just the left side (in both the IR and 476 * CFG structures). 477 */ 478 void delete_right(BasicBlock* b, 479 std::vector<BasicBlock::Node>::iterator* iter, 480 bool* outUpdated, 481 bool* outNeedsRescan) { 482 *outUpdated = true; 483 std::unique_ptr<Expression>* target = (*iter)->expression(); 484 ASSERT((*target)->fKind == Expression::kBinary_Kind); 485 BinaryExpression& bin = (BinaryExpression&) **target; 486 if (!b->tryRemoveExpressionBefore(iter, bin.fRight.get())) { 487 *target = std::move(bin.fLeft); 488 *outNeedsRescan = true; 489 return; 490 } 491 *target = std::move(bin.fLeft); 492 if (*iter == b->fNodes.begin()) { 493 *outNeedsRescan = true; 494 return; 495 } 496 --(*iter); 497 if (((*iter)->fKind != BasicBlock::Node::kExpression_Kind || 498 (*iter)->expression() != &bin.fLeft)) { 499 *outNeedsRescan = true; 500 return; 501 } 502 *iter = b->fNodes.erase(*iter); 503 ASSERT((*iter)->expression() == target); 504 } 505 506 /** 507 * Constructs the specified type using a single argument. 508 */ 509 static std::unique_ptr<Expression> construct(const Type& type, std::unique_ptr<Expression> v) { 510 std::vector<std::unique_ptr<Expression>> args; 511 args.push_back(std::move(v)); 512 auto result = std::unique_ptr<Expression>(new Constructor(Position(), type, std::move(args))); 513 return result; 514 } 515 516 /** 517 * Used in the implementations of vectorize_left and vectorize_right. Given a vector type and an 518 * expression x, deletes the expression pointed to by iter and replaces it with <type>(x). 519 */ 520 static void vectorize(BasicBlock* b, 521 std::vector<BasicBlock::Node>::iterator* iter, 522 const Type& type, 523 std::unique_ptr<Expression>* otherExpression, 524 bool* outUpdated, 525 bool* outNeedsRescan) { 526 ASSERT((*(*iter)->expression())->fKind == Expression::kBinary_Kind); 527 ASSERT(type.kind() == Type::kVector_Kind); 528 ASSERT((*otherExpression)->fType.kind() == Type::kScalar_Kind); 529 *outUpdated = true; 530 std::unique_ptr<Expression>* target = (*iter)->expression(); 531 if (!b->tryRemoveExpression(iter)) { 532 *target = construct(type, std::move(*otherExpression)); 533 *outNeedsRescan = true; 534 } else { 535 *target = construct(type, std::move(*otherExpression)); 536 if (!b->tryInsertExpression(iter, target)) { 537 *outNeedsRescan = true; 538 } 539 } 540 } 541 542 /** 543 * Given a binary expression of the form x <op> vec<n>(y), deletes the right side and vectorizes the 544 * left to yield vec<n>(x). 545 */ 546 static void vectorize_left(BasicBlock* b, 547 std::vector<BasicBlock::Node>::iterator* iter, 548 bool* outUpdated, 549 bool* outNeedsRescan) { 550 BinaryExpression& bin = (BinaryExpression&) **(*iter)->expression(); 551 vectorize(b, iter, bin.fRight->fType, &bin.fLeft, outUpdated, outNeedsRescan); 552 } 553 554 /** 555 * Given a binary expression of the form vec<n>(x) <op> y, deletes the left side and vectorizes the 556 * right to yield vec<n>(y). 557 */ 558 static void vectorize_right(BasicBlock* b, 559 std::vector<BasicBlock::Node>::iterator* iter, 560 bool* outUpdated, 561 bool* outNeedsRescan) { 562 BinaryExpression& bin = (BinaryExpression&) **(*iter)->expression(); 563 vectorize(b, iter, bin.fLeft->fType, &bin.fRight, outUpdated, outNeedsRescan); 564 } 565 566 // Mark that an expression which we were writing to is no longer being written to 567 void clear_write(const Expression& expr) { 568 switch (expr.fKind) { 569 case Expression::kVariableReference_Kind: { 570 ((VariableReference&) expr).setRefKind(VariableReference::kRead_RefKind); 571 break; 572 } 573 case Expression::kFieldAccess_Kind: 574 clear_write(*((FieldAccess&) expr).fBase); 575 break; 576 case Expression::kSwizzle_Kind: 577 clear_write(*((Swizzle&) expr).fBase); 578 break; 579 case Expression::kIndex_Kind: 580 clear_write(*((IndexExpression&) expr).fBase); 581 break; 582 default: 583 ABORT("shouldn't be writing to this kind of expression\n"); 584 break; 585 } 586 } 587 588 void Compiler::simplifyExpression(DefinitionMap& definitions, 589 BasicBlock& b, 590 std::vector<BasicBlock::Node>::iterator* iter, 591 std::unordered_set<const Variable*>* undefinedVariables, 592 bool* outUpdated, 593 bool* outNeedsRescan) { 594 Expression* expr = (*iter)->expression()->get(); 595 ASSERT(expr); 596 if ((*iter)->fConstantPropagation) { 597 std::unique_ptr<Expression> optimized = expr->constantPropagate(*fIRGenerator, definitions); 598 if (optimized) { 599 *outUpdated = true; 600 if (!try_replace_expression(&b, iter, &optimized)) { 601 *outNeedsRescan = true; 602 return; 603 } 604 ASSERT((*iter)->fKind == BasicBlock::Node::kExpression_Kind); 605 expr = (*iter)->expression()->get(); 606 } 607 } 608 switch (expr->fKind) { 609 case Expression::kVariableReference_Kind: { 610 const Variable& var = ((VariableReference*) expr)->fVariable; 611 if (var.fStorage == Variable::kLocal_Storage && !definitions[&var] && 612 (*undefinedVariables).find(&var) == (*undefinedVariables).end()) { 613 (*undefinedVariables).insert(&var); 614 this->error(expr->fPosition, 615 "'" + var.fName + "' has not been assigned"); 616 } 617 break; 618 } 619 case Expression::kTernary_Kind: { 620 TernaryExpression* t = (TernaryExpression*) expr; 621 if (t->fTest->fKind == Expression::kBoolLiteral_Kind) { 622 // ternary has a constant test, replace it with either the true or 623 // false branch 624 if (((BoolLiteral&) *t->fTest).fValue) { 625 (*iter)->setExpression(std::move(t->fIfTrue)); 626 } else { 627 (*iter)->setExpression(std::move(t->fIfFalse)); 628 } 629 *outUpdated = true; 630 *outNeedsRescan = true; 631 } 632 break; 633 } 634 case Expression::kBinary_Kind: { 635 BinaryExpression* bin = (BinaryExpression*) expr; 636 if (dead_assignment(*bin)) { 637 delete_left(&b, iter, outUpdated, outNeedsRescan); 638 break; 639 } 640 // collapse useless expressions like x * 1 or x + 0 641 if (((bin->fLeft->fType.kind() != Type::kScalar_Kind) && 642 (bin->fLeft->fType.kind() != Type::kVector_Kind)) || 643 ((bin->fRight->fType.kind() != Type::kScalar_Kind) && 644 (bin->fRight->fType.kind() != Type::kVector_Kind))) { 645 break; 646 } 647 switch (bin->fOperator) { 648 case Token::STAR: 649 if (is_constant(*bin->fLeft, 1)) { 650 if (bin->fLeft->fType.kind() == Type::kVector_Kind && 651 bin->fRight->fType.kind() == Type::kScalar_Kind) { 652 // vec4(1) * x -> vec4(x) 653 vectorize_right(&b, iter, outUpdated, outNeedsRescan); 654 } else { 655 // 1 * x -> x 656 // 1 * vec4(x) -> vec4(x) 657 // vec4(1) * vec4(x) -> vec4(x) 658 delete_left(&b, iter, outUpdated, outNeedsRescan); 659 } 660 } 661 else if (is_constant(*bin->fLeft, 0)) { 662 if (bin->fLeft->fType.kind() == Type::kScalar_Kind && 663 bin->fRight->fType.kind() == Type::kVector_Kind) { 664 // 0 * vec4(x) -> vec4(0) 665 vectorize_left(&b, iter, outUpdated, outNeedsRescan); 666 } else { 667 // 0 * x -> 0 668 // vec4(0) * x -> vec4(0) 669 // vec4(0) * vec4(x) -> vec4(0) 670 delete_right(&b, iter, outUpdated, outNeedsRescan); 671 } 672 } 673 else if (is_constant(*bin->fRight, 1)) { 674 if (bin->fLeft->fType.kind() == Type::kScalar_Kind && 675 bin->fRight->fType.kind() == Type::kVector_Kind) { 676 // x * vec4(1) -> vec4(x) 677 vectorize_left(&b, iter, outUpdated, outNeedsRescan); 678 } else { 679 // x * 1 -> x 680 // vec4(x) * 1 -> vec4(x) 681 // vec4(x) * vec4(1) -> vec4(x) 682 delete_right(&b, iter, outUpdated, outNeedsRescan); 683 } 684 } 685 else if (is_constant(*bin->fRight, 0)) { 686 if (bin->fLeft->fType.kind() == Type::kVector_Kind && 687 bin->fRight->fType.kind() == Type::kScalar_Kind) { 688 // vec4(x) * 0 -> vec4(0) 689 vectorize_right(&b, iter, outUpdated, outNeedsRescan); 690 } else { 691 // x * 0 -> 0 692 // x * vec4(0) -> vec4(0) 693 // vec4(x) * vec4(0) -> vec4(0) 694 delete_left(&b, iter, outUpdated, outNeedsRescan); 695 } 696 } 697 break; 698 case Token::PLUS: 699 if (is_constant(*bin->fLeft, 0)) { 700 if (bin->fLeft->fType.kind() == Type::kVector_Kind && 701 bin->fRight->fType.kind() == Type::kScalar_Kind) { 702 // vec4(0) + x -> vec4(x) 703 vectorize_right(&b, iter, outUpdated, outNeedsRescan); 704 } else { 705 // 0 + x -> x 706 // 0 + vec4(x) -> vec4(x) 707 // vec4(0) + vec4(x) -> vec4(x) 708 delete_left(&b, iter, outUpdated, outNeedsRescan); 709 } 710 } else if (is_constant(*bin->fRight, 0)) { 711 if (bin->fLeft->fType.kind() == Type::kScalar_Kind && 712 bin->fRight->fType.kind() == Type::kVector_Kind) { 713 // x + vec4(0) -> vec4(x) 714 vectorize_left(&b, iter, outUpdated, outNeedsRescan); 715 } else { 716 // x + 0 -> x 717 // vec4(x) + 0 -> vec4(x) 718 // vec4(x) + vec4(0) -> vec4(x) 719 delete_right(&b, iter, outUpdated, outNeedsRescan); 720 } 721 } 722 break; 723 case Token::MINUS: 724 if (is_constant(*bin->fRight, 0)) { 725 if (bin->fLeft->fType.kind() == Type::kScalar_Kind && 726 bin->fRight->fType.kind() == Type::kVector_Kind) { 727 // x - vec4(0) -> vec4(x) 728 vectorize_left(&b, iter, outUpdated, outNeedsRescan); 729 } else { 730 // x - 0 -> x 731 // vec4(x) - 0 -> vec4(x) 732 // vec4(x) - vec4(0) -> vec4(x) 733 delete_right(&b, iter, outUpdated, outNeedsRescan); 734 } 735 } 736 break; 737 case Token::SLASH: 738 if (is_constant(*bin->fRight, 1)) { 739 if (bin->fLeft->fType.kind() == Type::kScalar_Kind && 740 bin->fRight->fType.kind() == Type::kVector_Kind) { 741 // x / vec4(1) -> vec4(x) 742 vectorize_left(&b, iter, outUpdated, outNeedsRescan); 743 } else { 744 // x / 1 -> x 745 // vec4(x) / 1 -> vec4(x) 746 // vec4(x) / vec4(1) -> vec4(x) 747 delete_right(&b, iter, outUpdated, outNeedsRescan); 748 } 749 } else if (is_constant(*bin->fLeft, 0)) { 750 if (bin->fLeft->fType.kind() == Type::kScalar_Kind && 751 bin->fRight->fType.kind() == Type::kVector_Kind) { 752 // 0 / vec4(x) -> vec4(0) 753 vectorize_left(&b, iter, outUpdated, outNeedsRescan); 754 } else { 755 // 0 / x -> 0 756 // vec4(0) / x -> vec4(0) 757 // vec4(0) / vec4(x) -> vec4(0) 758 delete_right(&b, iter, outUpdated, outNeedsRescan); 759 } 760 } 761 break; 762 case Token::PLUSEQ: 763 if (is_constant(*bin->fRight, 0)) { 764 clear_write(*bin->fLeft); 765 delete_right(&b, iter, outUpdated, outNeedsRescan); 766 } 767 break; 768 case Token::MINUSEQ: 769 if (is_constant(*bin->fRight, 0)) { 770 clear_write(*bin->fLeft); 771 delete_right(&b, iter, outUpdated, outNeedsRescan); 772 } 773 break; 774 case Token::STAREQ: 775 if (is_constant(*bin->fRight, 1)) { 776 clear_write(*bin->fLeft); 777 delete_right(&b, iter, outUpdated, outNeedsRescan); 778 } 779 break; 780 case Token::SLASHEQ: 781 if (is_constant(*bin->fRight, 1)) { 782 clear_write(*bin->fLeft); 783 delete_right(&b, iter, outUpdated, outNeedsRescan); 784 } 785 break; 786 default: 787 break; 788 } 789 } 790 default: 791 break; 792 } 793 } 794 795 // returns true if this statement could potentially execute a break at the current level (we ignore 796 // nested loops and switches, since any breaks inside of them will merely break the loop / switch) 797 static bool contains_break(Statement& s) { 798 switch (s.fKind) { 799 case Statement::kBlock_Kind: 800 for (const auto& sub : ((Block&) s).fStatements) { 801 if (contains_break(*sub)) { 802 return true; 803 } 804 } 805 return false; 806 case Statement::kBreak_Kind: 807 return true; 808 case Statement::kIf_Kind: { 809 const IfStatement& i = (IfStatement&) s; 810 return contains_break(*i.fIfTrue) || (i.fIfFalse && contains_break(*i.fIfFalse)); 811 } 812 default: 813 return false; 814 } 815 } 816 817 // Returns a block containing all of the statements that will be run if the given case matches 818 // (which, owing to the statements being owned by unique_ptrs, means the switch itself will be 819 // broken by this call and must then be discarded). 820 // Returns null (and leaves the switch unmodified) if no such simple reduction is possible, such as 821 // when break statements appear inside conditionals. 822 static std::unique_ptr<Statement> block_for_case(SwitchStatement* s, SwitchCase* c) { 823 bool capturing = false; 824 std::vector<std::unique_ptr<Statement>*> statementPtrs; 825 for (const auto& current : s->fCases) { 826 if (current.get() == c) { 827 capturing = true; 828 } 829 if (capturing) { 830 for (auto& stmt : current->fStatements) { 831 if (stmt->fKind == Statement::kBreak_Kind) { 832 capturing = false; 833 break; 834 } 835 if (contains_break(*stmt)) { 836 return nullptr; 837 } 838 statementPtrs.push_back(&stmt); 839 } 840 if (!capturing) { 841 break; 842 } 843 } 844 } 845 std::vector<std::unique_ptr<Statement>> statements; 846 for (const auto& s : statementPtrs) { 847 statements.push_back(std::move(*s)); 848 } 849 return std::unique_ptr<Statement>(new Block(Position(), std::move(statements), s->fSymbols)); 850 } 851 852 void Compiler::simplifyStatement(DefinitionMap& definitions, 853 BasicBlock& b, 854 std::vector<BasicBlock::Node>::iterator* iter, 855 std::unordered_set<const Variable*>* undefinedVariables, 856 bool* outUpdated, 857 bool* outNeedsRescan) { 858 Statement* stmt = (*iter)->statement()->get(); 859 switch (stmt->fKind) { 860 case Statement::kVarDeclaration_Kind: { 861 const auto& varDecl = (VarDeclaration&) *stmt; 862 if (varDecl.fVar->dead() && 863 (!varDecl.fValue || 864 !varDecl.fValue->hasSideEffects())) { 865 if (varDecl.fValue) { 866 ASSERT((*iter)->statement()->get() == stmt); 867 if (!b.tryRemoveExpressionBefore(iter, varDecl.fValue.get())) { 868 *outNeedsRescan = true; 869 } 870 } 871 (*iter)->setStatement(std::unique_ptr<Statement>(new Nop())); 872 *outUpdated = true; 873 } 874 break; 875 } 876 case Statement::kIf_Kind: { 877 IfStatement& i = (IfStatement&) *stmt; 878 if (i.fTest->fKind == Expression::kBoolLiteral_Kind) { 879 // constant if, collapse down to a single branch 880 if (((BoolLiteral&) *i.fTest).fValue) { 881 ASSERT(i.fIfTrue); 882 (*iter)->setStatement(std::move(i.fIfTrue)); 883 } else { 884 if (i.fIfFalse) { 885 (*iter)->setStatement(std::move(i.fIfFalse)); 886 } else { 887 (*iter)->setStatement(std::unique_ptr<Statement>(new Nop())); 888 } 889 } 890 *outUpdated = true; 891 *outNeedsRescan = true; 892 break; 893 } 894 if (i.fIfFalse && i.fIfFalse->isEmpty()) { 895 // else block doesn't do anything, remove it 896 i.fIfFalse.reset(); 897 *outUpdated = true; 898 *outNeedsRescan = true; 899 } 900 if (!i.fIfFalse && i.fIfTrue->isEmpty()) { 901 // if block doesn't do anything, no else block 902 if (i.fTest->hasSideEffects()) { 903 // test has side effects, keep it 904 (*iter)->setStatement(std::unique_ptr<Statement>( 905 new ExpressionStatement(std::move(i.fTest)))); 906 } else { 907 // no if, no else, no test side effects, kill the whole if 908 // statement 909 (*iter)->setStatement(std::unique_ptr<Statement>(new Nop())); 910 } 911 *outUpdated = true; 912 *outNeedsRescan = true; 913 } 914 break; 915 } 916 case Statement::kSwitch_Kind: { 917 SwitchStatement& s = (SwitchStatement&) *stmt; 918 if (s.fValue->isConstant()) { 919 // switch is constant, replace it with the case that matches 920 bool found = false; 921 SwitchCase* defaultCase = nullptr; 922 for (const auto& c : s.fCases) { 923 if (!c->fValue) { 924 defaultCase = c.get(); 925 continue; 926 } 927 ASSERT(c->fValue->fKind == s.fValue->fKind); 928 found = c->fValue->compareConstant(fContext, *s.fValue); 929 if (found) { 930 std::unique_ptr<Statement> newBlock = block_for_case(&s, c.get()); 931 if (newBlock) { 932 (*iter)->setStatement(std::move(newBlock)); 933 break; 934 } else { 935 if (s.fIsStatic && !(fFlags & kPermitInvalidStaticTests_Flag)) { 936 this->error(s.fPosition, 937 "static switch contains non-static conditional break"); 938 s.fIsStatic = false; 939 } 940 return; // can't simplify 941 } 942 } 943 } 944 if (!found) { 945 // no matching case. use default if it exists, or kill the whole thing 946 if (defaultCase) { 947 std::unique_ptr<Statement> newBlock = block_for_case(&s, defaultCase); 948 if (newBlock) { 949 (*iter)->setStatement(std::move(newBlock)); 950 } else { 951 if (s.fIsStatic && !(fFlags & kPermitInvalidStaticTests_Flag)) { 952 this->error(s.fPosition, 953 "static switch contains non-static conditional break"); 954 s.fIsStatic = false; 955 } 956 return; // can't simplify 957 } 958 } else { 959 (*iter)->setStatement(std::unique_ptr<Statement>(new Nop())); 960 } 961 } 962 *outUpdated = true; 963 *outNeedsRescan = true; 964 } 965 break; 966 } 967 case Statement::kExpression_Kind: { 968 ExpressionStatement& e = (ExpressionStatement&) *stmt; 969 ASSERT((*iter)->statement()->get() == &e); 970 if (!e.fExpression->hasSideEffects()) { 971 // Expression statement with no side effects, kill it 972 if (!b.tryRemoveExpressionBefore(iter, e.fExpression.get())) { 973 *outNeedsRescan = true; 974 } 975 ASSERT((*iter)->statement()->get() == stmt); 976 (*iter)->setStatement(std::unique_ptr<Statement>(new Nop())); 977 *outUpdated = true; 978 } 979 break; 980 } 981 default: 982 break; 983 } 984 } 985 986 void Compiler::scanCFG(FunctionDefinition& f) { 987 CFG cfg = CFGGenerator().getCFG(f); 988 this->computeDataFlow(&cfg); 989 990 // check for unreachable code 991 for (size_t i = 0; i < cfg.fBlocks.size(); i++) { 992 if (i != cfg.fStart && !cfg.fBlocks[i].fEntrances.size() && 993 cfg.fBlocks[i].fNodes.size()) { 994 Position p; 995 switch (cfg.fBlocks[i].fNodes[0].fKind) { 996 case BasicBlock::Node::kStatement_Kind: 997 p = (*cfg.fBlocks[i].fNodes[0].statement())->fPosition; 998 break; 999 case BasicBlock::Node::kExpression_Kind: 1000 p = (*cfg.fBlocks[i].fNodes[0].expression())->fPosition; 1001 break; 1002 } 1003 this->error(p, String("unreachable")); 1004 } 1005 } 1006 if (fErrorCount) { 1007 return; 1008 } 1009 1010 // check for dead code & undefined variables, perform constant propagation 1011 std::unordered_set<const Variable*> undefinedVariables; 1012 bool updated; 1013 bool needsRescan = false; 1014 do { 1015 if (needsRescan) { 1016 cfg = CFGGenerator().getCFG(f); 1017 this->computeDataFlow(&cfg); 1018 needsRescan = false; 1019 } 1020 1021 updated = false; 1022 for (BasicBlock& b : cfg.fBlocks) { 1023 DefinitionMap definitions = b.fBefore; 1024 1025 for (auto iter = b.fNodes.begin(); iter != b.fNodes.end() && !needsRescan; ++iter) { 1026 if (iter->fKind == BasicBlock::Node::kExpression_Kind) { 1027 this->simplifyExpression(definitions, b, &iter, &undefinedVariables, &updated, 1028 &needsRescan); 1029 } else { 1030 this->simplifyStatement(definitions, b, &iter, &undefinedVariables, &updated, 1031 &needsRescan); 1032 } 1033 if (needsRescan) { 1034 break; 1035 } 1036 this->addDefinitions(*iter, &definitions); 1037 } 1038 } 1039 } while (updated); 1040 ASSERT(!needsRescan); 1041 1042 // verify static ifs & switches, clean up dead variable decls 1043 for (BasicBlock& b : cfg.fBlocks) { 1044 DefinitionMap definitions = b.fBefore; 1045 1046 for (auto iter = b.fNodes.begin(); iter != b.fNodes.end() && !needsRescan;) { 1047 if (iter->fKind == BasicBlock::Node::kStatement_Kind) { 1048 const Statement& s = **iter->statement(); 1049 switch (s.fKind) { 1050 case Statement::kIf_Kind: 1051 if (((const IfStatement&) s).fIsStatic && 1052 !(fFlags & kPermitInvalidStaticTests_Flag)) { 1053 this->error(s.fPosition, "static if has non-static test"); 1054 } 1055 ++iter; 1056 break; 1057 case Statement::kSwitch_Kind: 1058 if (((const SwitchStatement&) s).fIsStatic && 1059 !(fFlags & kPermitInvalidStaticTests_Flag)) { 1060 this->error(s.fPosition, "static switch has non-static test"); 1061 } 1062 ++iter; 1063 break; 1064 case Statement::kVarDeclarations_Kind: { 1065 VarDeclarations& decls = *((VarDeclarationsStatement&) s).fDeclaration; 1066 for (auto varIter = decls.fVars.begin(); varIter != decls.fVars.end();) { 1067 if ((*varIter)->fKind == Statement::kNop_Kind) { 1068 varIter = decls.fVars.erase(varIter); 1069 } else { 1070 ++varIter; 1071 } 1072 } 1073 if (!decls.fVars.size()) { 1074 iter = b.fNodes.erase(iter); 1075 } else { 1076 ++iter; 1077 } 1078 break; 1079 } 1080 default: 1081 ++iter; 1082 break; 1083 } 1084 } else { 1085 ++iter; 1086 } 1087 } 1088 } 1089 1090 // check for missing return 1091 if (f.fDeclaration.fReturnType != *fContext.fVoid_Type) { 1092 if (cfg.fBlocks[cfg.fExit].fEntrances.size()) { 1093 this->error(f.fPosition, String("function can exit without returning a value")); 1094 } 1095 } 1096 } 1097 1098 std::unique_ptr<Program> Compiler::convertProgram(Program::Kind kind, String text, 1099 const Program::Settings& settings) { 1100 fErrorText = ""; 1101 fErrorCount = 0; 1102 fIRGenerator->start(&settings); 1103 std::vector<std::unique_ptr<ProgramElement>> elements; 1104 Modifiers::Flag ignored; 1105 switch (kind) { 1106 case Program::kVertex_Kind: 1107 fIRGenerator->convertProgram(String(SKSL_VERT_INCLUDE), *fTypes, &ignored, &elements); 1108 break; 1109 case Program::kFragment_Kind: 1110 fIRGenerator->convertProgram(String(SKSL_FRAG_INCLUDE), *fTypes, &ignored, &elements); 1111 break; 1112 case Program::kGeometry_Kind: 1113 fIRGenerator->convertProgram(String(SKSL_GEOM_INCLUDE), *fTypes, &ignored, &elements); 1114 break; 1115 case Program::kFragmentProcessor_Kind: 1116 fIRGenerator->convertProgram(String(SKSL_FP_INCLUDE), *fTypes, &ignored, &elements); 1117 break; 1118 } 1119 fIRGenerator->fSymbolTable->markAllFunctionsBuiltin(); 1120 Modifiers::Flag defaultPrecision; 1121 fIRGenerator->convertProgram(text, *fTypes, &defaultPrecision, &elements); 1122 if (!fErrorCount) { 1123 for (auto& element : elements) { 1124 if (element->fKind == ProgramElement::kFunction_Kind) { 1125 this->scanCFG((FunctionDefinition&) *element); 1126 } 1127 } 1128 } 1129 auto result = std::unique_ptr<Program>(new Program(kind, settings, defaultPrecision, &fContext, 1130 std::move(elements), 1131 fIRGenerator->fSymbolTable, 1132 fIRGenerator->fInputs)); 1133 fIRGenerator->finish(); 1134 this->writeErrorCount(); 1135 if (fErrorCount) { 1136 return nullptr; 1137 } 1138 return result; 1139 } 1140 1141 bool Compiler::toSPIRV(const Program& program, OutputStream& out) { 1142 #ifdef SK_ENABLE_SPIRV_VALIDATION 1143 StringStream buffer; 1144 SPIRVCodeGenerator cg(&fContext, &program, this, &buffer); 1145 bool result = cg.generateCode(); 1146 if (result) { 1147 spvtools::SpirvTools tools(SPV_ENV_VULKAN_1_0); 1148 const String& data = buffer.str(); 1149 ASSERT(0 == data.size() % 4); 1150 auto dumpmsg = [](spv_message_level_t, const char*, const spv_position_t&, const char* m) { 1151 SkDebugf("SPIR-V validation error: %s\n", m); 1152 }; 1153 tools.SetMessageConsumer(dumpmsg); 1154 // Verify that the SPIR-V we produced is valid. If this assert fails, check the logs prior 1155 // to the failure to see the validation errors. 1156 ASSERT_RESULT(tools.Validate((const uint32_t*) data.c_str(), data.size() / 4)); 1157 out.write(data.c_str(), data.size()); 1158 } 1159 #else 1160 SPIRVCodeGenerator cg(&fContext, &program, this, &out); 1161 bool result = cg.generateCode(); 1162 #endif 1163 this->writeErrorCount(); 1164 return result; 1165 } 1166 1167 bool Compiler::toSPIRV(const Program& program, String* out) { 1168 StringStream buffer; 1169 bool result = this->toSPIRV(program, buffer); 1170 if (result) { 1171 *out = buffer.str(); 1172 } 1173 return result; 1174 } 1175 1176 bool Compiler::toGLSL(const Program& program, OutputStream& out) { 1177 GLSLCodeGenerator cg(&fContext, &program, this, &out); 1178 bool result = cg.generateCode(); 1179 this->writeErrorCount(); 1180 return result; 1181 } 1182 1183 bool Compiler::toGLSL(const Program& program, String* out) { 1184 StringStream buffer; 1185 bool result = this->toGLSL(program, buffer); 1186 if (result) { 1187 *out = buffer.str(); 1188 } 1189 return result; 1190 } 1191 1192 bool Compiler::toCPP(const Program& program, String name, OutputStream& out) { 1193 CPPCodeGenerator cg(&fContext, &program, this, name, &out); 1194 bool result = cg.generateCode(); 1195 this->writeErrorCount(); 1196 return result; 1197 } 1198 1199 bool Compiler::toH(const Program& program, String name, OutputStream& out) { 1200 HCodeGenerator cg(&program, this, name, &out); 1201 bool result = cg.generateCode(); 1202 this->writeErrorCount(); 1203 return result; 1204 } 1205 1206 void Compiler::error(Position position, String msg) { 1207 fErrorCount++; 1208 fErrorText += "error: " + position.description() + ": " + msg.c_str() + "\n"; 1209 } 1210 1211 String Compiler::errorText() { 1212 String result = fErrorText; 1213 return result; 1214 } 1215 1216 void Compiler::writeErrorCount() { 1217 if (fErrorCount) { 1218 fErrorText += to_string(fErrorCount) + " error"; 1219 if (fErrorCount > 1) { 1220 fErrorText += "s"; 1221 } 1222 fErrorText += "\n"; 1223 } 1224 } 1225 1226 } // namespace 1227
