• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 "src/sksl/SkSLCompiler.h"
9 
10 #include "src/sksl/SkSLByteCodeGenerator.h"
11 #include "src/sksl/SkSLCFGGenerator.h"
12 #include "src/sksl/SkSLCPPCodeGenerator.h"
13 #include "src/sksl/SkSLGLSLCodeGenerator.h"
14 #include "src/sksl/SkSLHCodeGenerator.h"
15 #include "src/sksl/SkSLIRGenerator.h"
16 #include "src/sksl/SkSLMetalCodeGenerator.h"
17 #include "src/sksl/SkSLPipelineStageCodeGenerator.h"
18 #include "src/sksl/SkSLSPIRVCodeGenerator.h"
19 #include "src/sksl/ir/SkSLEnum.h"
20 #include "src/sksl/ir/SkSLExpression.h"
21 #include "src/sksl/ir/SkSLExpressionStatement.h"
22 #include "src/sksl/ir/SkSLFunctionCall.h"
23 #include "src/sksl/ir/SkSLIntLiteral.h"
24 #include "src/sksl/ir/SkSLModifiersDeclaration.h"
25 #include "src/sksl/ir/SkSLNop.h"
26 #include "src/sksl/ir/SkSLSymbolTable.h"
27 #include "src/sksl/ir/SkSLTernaryExpression.h"
28 #include "src/sksl/ir/SkSLUnresolvedFunction.h"
29 #include "src/sksl/ir/SkSLVarDeclarations.h"
30 
31 #ifdef SK_ENABLE_SPIRV_VALIDATION
32 #include "spirv-tools/libspirv.hpp"
33 #endif
34 
35 // include the built-in shader symbols as static strings
36 
37 #define STRINGIFY(x) #x
38 
39 static const char* SKSL_GPU_INCLUDE =
40 #include "sksl_gpu.inc"
41 ;
42 
43 static const char* SKSL_INTERP_INCLUDE =
44 #include "sksl_interp.inc"
45 ;
46 
47 static const char* SKSL_VERT_INCLUDE =
48 #include "sksl_vert.inc"
49 ;
50 
51 static const char* SKSL_FRAG_INCLUDE =
52 #include "sksl_frag.inc"
53 ;
54 
55 static const char* SKSL_GEOM_INCLUDE =
56 #include "sksl_geom.inc"
57 ;
58 
59 static const char* SKSL_FP_INCLUDE =
60 #include "sksl_enums.inc"
61 #include "sksl_fp.inc"
62 ;
63 
64 static const char* SKSL_PIPELINE_INCLUDE =
65 #include "sksl_pipeline.inc"
66 ;
67 
68 namespace SkSL {
69 
Compiler(Flags flags)70 Compiler::Compiler(Flags flags)
71 : fFlags(flags)
72 , fContext(new Context())
73 , fErrorCount(0) {
74     auto types = std::shared_ptr<SymbolTable>(new SymbolTable(this));
75     auto symbols = std::shared_ptr<SymbolTable>(new SymbolTable(types, this));
76     fIRGenerator = new IRGenerator(fContext.get(), symbols, *this);
77     fTypes = types;
78     #define ADD_TYPE(t) types->addWithoutOwnership(fContext->f ## t ## _Type->fName, \
79                                                    fContext->f ## t ## _Type.get())
80     ADD_TYPE(Void);
81     ADD_TYPE(Float);
82     ADD_TYPE(Float2);
83     ADD_TYPE(Float3);
84     ADD_TYPE(Float4);
85     ADD_TYPE(Half);
86     ADD_TYPE(Half2);
87     ADD_TYPE(Half3);
88     ADD_TYPE(Half4);
89     ADD_TYPE(Double);
90     ADD_TYPE(Double2);
91     ADD_TYPE(Double3);
92     ADD_TYPE(Double4);
93     ADD_TYPE(Int);
94     ADD_TYPE(Int2);
95     ADD_TYPE(Int3);
96     ADD_TYPE(Int4);
97     ADD_TYPE(UInt);
98     ADD_TYPE(UInt2);
99     ADD_TYPE(UInt3);
100     ADD_TYPE(UInt4);
101     ADD_TYPE(Short);
102     ADD_TYPE(Short2);
103     ADD_TYPE(Short3);
104     ADD_TYPE(Short4);
105     ADD_TYPE(UShort);
106     ADD_TYPE(UShort2);
107     ADD_TYPE(UShort3);
108     ADD_TYPE(UShort4);
109     ADD_TYPE(Byte);
110     ADD_TYPE(Byte2);
111     ADD_TYPE(Byte3);
112     ADD_TYPE(Byte4);
113     ADD_TYPE(UByte);
114     ADD_TYPE(UByte2);
115     ADD_TYPE(UByte3);
116     ADD_TYPE(UByte4);
117     ADD_TYPE(Bool);
118     ADD_TYPE(Bool2);
119     ADD_TYPE(Bool3);
120     ADD_TYPE(Bool4);
121     ADD_TYPE(Float2x2);
122     ADD_TYPE(Float2x3);
123     ADD_TYPE(Float2x4);
124     ADD_TYPE(Float3x2);
125     ADD_TYPE(Float3x3);
126     ADD_TYPE(Float3x4);
127     ADD_TYPE(Float4x2);
128     ADD_TYPE(Float4x3);
129     ADD_TYPE(Float4x4);
130     ADD_TYPE(Half2x2);
131     ADD_TYPE(Half2x3);
132     ADD_TYPE(Half2x4);
133     ADD_TYPE(Half3x2);
134     ADD_TYPE(Half3x3);
135     ADD_TYPE(Half3x4);
136     ADD_TYPE(Half4x2);
137     ADD_TYPE(Half4x3);
138     ADD_TYPE(Half4x4);
139     ADD_TYPE(Double2x2);
140     ADD_TYPE(Double2x3);
141     ADD_TYPE(Double2x4);
142     ADD_TYPE(Double3x2);
143     ADD_TYPE(Double3x3);
144     ADD_TYPE(Double3x4);
145     ADD_TYPE(Double4x2);
146     ADD_TYPE(Double4x3);
147     ADD_TYPE(Double4x4);
148     ADD_TYPE(GenType);
149     ADD_TYPE(GenHType);
150     ADD_TYPE(GenDType);
151     ADD_TYPE(GenIType);
152     ADD_TYPE(GenUType);
153     ADD_TYPE(GenBType);
154     ADD_TYPE(Mat);
155     ADD_TYPE(Vec);
156     ADD_TYPE(GVec);
157     ADD_TYPE(GVec2);
158     ADD_TYPE(GVec3);
159     ADD_TYPE(GVec4);
160     ADD_TYPE(HVec);
161     ADD_TYPE(DVec);
162     ADD_TYPE(IVec);
163     ADD_TYPE(UVec);
164     ADD_TYPE(SVec);
165     ADD_TYPE(USVec);
166     ADD_TYPE(ByteVec);
167     ADD_TYPE(UByteVec);
168     ADD_TYPE(BVec);
169 
170     ADD_TYPE(Sampler1D);
171     ADD_TYPE(Sampler2D);
172     ADD_TYPE(Sampler3D);
173     ADD_TYPE(SamplerExternalOES);
174     ADD_TYPE(SamplerCube);
175     ADD_TYPE(Sampler2DRect);
176     ADD_TYPE(Sampler1DArray);
177     ADD_TYPE(Sampler2DArray);
178     ADD_TYPE(SamplerCubeArray);
179     ADD_TYPE(SamplerBuffer);
180     ADD_TYPE(Sampler2DMS);
181     ADD_TYPE(Sampler2DMSArray);
182 
183     ADD_TYPE(ISampler2D);
184 
185     ADD_TYPE(Image2D);
186     ADD_TYPE(IImage2D);
187 
188     ADD_TYPE(SubpassInput);
189     ADD_TYPE(SubpassInputMS);
190 
191     ADD_TYPE(GSampler1D);
192     ADD_TYPE(GSampler2D);
193     ADD_TYPE(GSampler3D);
194     ADD_TYPE(GSamplerCube);
195     ADD_TYPE(GSampler2DRect);
196     ADD_TYPE(GSampler1DArray);
197     ADD_TYPE(GSampler2DArray);
198     ADD_TYPE(GSamplerCubeArray);
199     ADD_TYPE(GSamplerBuffer);
200     ADD_TYPE(GSampler2DMS);
201     ADD_TYPE(GSampler2DMSArray);
202 
203     ADD_TYPE(Sampler1DShadow);
204     ADD_TYPE(Sampler2DShadow);
205     ADD_TYPE(SamplerCubeShadow);
206     ADD_TYPE(Sampler2DRectShadow);
207     ADD_TYPE(Sampler1DArrayShadow);
208     ADD_TYPE(Sampler2DArrayShadow);
209     ADD_TYPE(SamplerCubeArrayShadow);
210     ADD_TYPE(GSampler2DArrayShadow);
211     ADD_TYPE(GSamplerCubeArrayShadow);
212     ADD_TYPE(FragmentProcessor);
213     ADD_TYPE(SkRasterPipeline);
214     ADD_TYPE(Sampler);
215     ADD_TYPE(Texture2D);
216 
217     StringFragment skCapsName("sk_Caps");
218     Variable* skCaps = new Variable(-1, Modifiers(), skCapsName,
219                                     *fContext->fSkCaps_Type, Variable::kGlobal_Storage);
220     fIRGenerator->fSymbolTable->add(skCapsName, std::unique_ptr<Symbol>(skCaps));
221 
222     StringFragment skArgsName("sk_Args");
223     Variable* skArgs = new Variable(-1, Modifiers(), skArgsName,
224                                     *fContext->fSkArgs_Type, Variable::kGlobal_Storage);
225     fIRGenerator->fSymbolTable->add(skArgsName, std::unique_ptr<Symbol>(skArgs));
226 
227     std::vector<std::unique_ptr<ProgramElement>> ignored;
228     this->processIncludeFile(Program::kFragment_Kind, SKSL_GPU_INCLUDE, strlen(SKSL_GPU_INCLUDE),
229                              symbols, &ignored, &fGpuSymbolTable);
230     this->processIncludeFile(Program::kVertex_Kind, SKSL_VERT_INCLUDE, strlen(SKSL_VERT_INCLUDE),
231                              fGpuSymbolTable, &fVertexInclude, &fVertexSymbolTable);
232     this->processIncludeFile(Program::kFragment_Kind, SKSL_FRAG_INCLUDE, strlen(SKSL_FRAG_INCLUDE),
233                              fGpuSymbolTable, &fFragmentInclude, &fFragmentSymbolTable);
234     this->processIncludeFile(Program::kGeometry_Kind, SKSL_GEOM_INCLUDE, strlen(SKSL_GEOM_INCLUDE),
235                              fGpuSymbolTable, &fGeometryInclude, &fGeometrySymbolTable);
236     this->processIncludeFile(Program::kPipelineStage_Kind, SKSL_PIPELINE_INCLUDE,
237                              strlen(SKSL_PIPELINE_INCLUDE), fGpuSymbolTable, &fPipelineInclude,
238                              &fPipelineSymbolTable);
239     this->processIncludeFile(Program::kGeneric_Kind, SKSL_INTERP_INCLUDE,
240                              strlen(SKSL_INTERP_INCLUDE), symbols, &fInterpreterInclude,
241                              &fInterpreterSymbolTable);
242 }
243 
~Compiler()244 Compiler::~Compiler() {
245     delete fIRGenerator;
246 }
247 
processIncludeFile(Program::Kind kind,const char * src,size_t length,std::shared_ptr<SymbolTable> base,std::vector<std::unique_ptr<ProgramElement>> * outElements,std::shared_ptr<SymbolTable> * outSymbolTable)248 void Compiler::processIncludeFile(Program::Kind kind, const char* src, size_t length,
249                                   std::shared_ptr<SymbolTable> base,
250                                   std::vector<std::unique_ptr<ProgramElement>>* outElements,
251                                   std::shared_ptr<SymbolTable>* outSymbolTable) {
252     fIRGenerator->fSymbolTable = std::move(base);
253     Program::Settings settings;
254     fIRGenerator->start(&settings, nullptr);
255     fIRGenerator->convertProgram(kind, src, length, *fTypes, outElements);
256     if (this->fErrorCount) {
257         printf("Unexpected errors: %s\n", this->fErrorText.c_str());
258     }
259     SkASSERT(!fErrorCount);
260     fIRGenerator->fSymbolTable->markAllFunctionsBuiltin();
261     *outSymbolTable = fIRGenerator->fSymbolTable;
262 }
263 
264 // add the definition created by assigning to the lvalue to the definition set
addDefinition(const Expression * lvalue,std::unique_ptr<Expression> * expr,DefinitionMap * definitions)265 void Compiler::addDefinition(const Expression* lvalue, std::unique_ptr<Expression>* expr,
266                              DefinitionMap* definitions) {
267     switch (lvalue->fKind) {
268         case Expression::kVariableReference_Kind: {
269             const Variable& var = ((VariableReference*) lvalue)->fVariable;
270             if (var.fStorage == Variable::kLocal_Storage) {
271                 (*definitions)[&var] = expr;
272             }
273             break;
274         }
275         case Expression::kSwizzle_Kind:
276             // We consider the variable written to as long as at least some of its components have
277             // been written to. This will lead to some false negatives (we won't catch it if you
278             // write to foo.x and then read foo.y), but being stricter could lead to false positives
279             // (we write to foo.x, and then pass foo to a function which happens to only read foo.x,
280             // but since we pass foo as a whole it is flagged as an error) unless we perform a much
281             // more complicated whole-program analysis. This is probably good enough.
282             this->addDefinition(((Swizzle*) lvalue)->fBase.get(),
283                                 (std::unique_ptr<Expression>*) &fContext->fDefined_Expression,
284                                 definitions);
285             break;
286         case Expression::kIndex_Kind:
287             // see comments in Swizzle
288             this->addDefinition(((IndexExpression*) lvalue)->fBase.get(),
289                                 (std::unique_ptr<Expression>*) &fContext->fDefined_Expression,
290                                 definitions);
291             break;
292         case Expression::kFieldAccess_Kind:
293             // see comments in Swizzle
294             this->addDefinition(((FieldAccess*) lvalue)->fBase.get(),
295                                 (std::unique_ptr<Expression>*) &fContext->fDefined_Expression,
296                                 definitions);
297             break;
298         case Expression::kTernary_Kind:
299             // To simplify analysis, we just pretend that we write to both sides of the ternary.
300             // This allows for false positives (meaning we fail to detect that a variable might not
301             // have been assigned), but is preferable to false negatives.
302             this->addDefinition(((TernaryExpression*) lvalue)->fIfTrue.get(),
303                                 (std::unique_ptr<Expression>*) &fContext->fDefined_Expression,
304                                 definitions);
305             this->addDefinition(((TernaryExpression*) lvalue)->fIfFalse.get(),
306                                 (std::unique_ptr<Expression>*) &fContext->fDefined_Expression,
307                                 definitions);
308             break;
309         case Expression::kExternalValue_Kind:
310             break;
311         default:
312             // not an lvalue, can't happen
313             SkASSERT(false);
314     }
315 }
316 
317 // add local variables defined by this node to the set
addDefinitions(const BasicBlock::Node & node,DefinitionMap * definitions)318 void Compiler::addDefinitions(const BasicBlock::Node& node,
319                               DefinitionMap* definitions) {
320     switch (node.fKind) {
321         case BasicBlock::Node::kExpression_Kind: {
322             SkASSERT(node.expression());
323             const Expression* expr = (Expression*) node.expression()->get();
324             switch (expr->fKind) {
325                 case Expression::kBinary_Kind: {
326                     BinaryExpression* b = (BinaryExpression*) expr;
327                     if (b->fOperator == Token::EQ) {
328                         this->addDefinition(b->fLeft.get(), &b->fRight, definitions);
329                     } else if (Compiler::IsAssignment(b->fOperator)) {
330                         this->addDefinition(
331                                       b->fLeft.get(),
332                                       (std::unique_ptr<Expression>*) &fContext->fDefined_Expression,
333                                       definitions);
334 
335                     }
336                     break;
337                 }
338                 case Expression::kFunctionCall_Kind: {
339                     const FunctionCall& c = (const FunctionCall&) *expr;
340                     for (size_t i = 0; i < c.fFunction.fParameters.size(); ++i) {
341                         if (c.fFunction.fParameters[i]->fModifiers.fFlags & Modifiers::kOut_Flag) {
342                             this->addDefinition(
343                                       c.fArguments[i].get(),
344                                       (std::unique_ptr<Expression>*) &fContext->fDefined_Expression,
345                                       definitions);
346                         }
347                     }
348                     break;
349                 }
350                 case Expression::kPrefix_Kind: {
351                     const PrefixExpression* p = (PrefixExpression*) expr;
352                     if (p->fOperator == Token::MINUSMINUS || p->fOperator == Token::PLUSPLUS) {
353                         this->addDefinition(
354                                       p->fOperand.get(),
355                                       (std::unique_ptr<Expression>*) &fContext->fDefined_Expression,
356                                       definitions);
357                     }
358                     break;
359                 }
360                 case Expression::kPostfix_Kind: {
361                     const PostfixExpression* p = (PostfixExpression*) expr;
362                     if (p->fOperator == Token::MINUSMINUS || p->fOperator == Token::PLUSPLUS) {
363                         this->addDefinition(
364                                       p->fOperand.get(),
365                                       (std::unique_ptr<Expression>*) &fContext->fDefined_Expression,
366                                       definitions);
367                     }
368                     break;
369                 }
370                 case Expression::kVariableReference_Kind: {
371                     const VariableReference* v = (VariableReference*) expr;
372                     if (v->fRefKind != VariableReference::kRead_RefKind) {
373                         this->addDefinition(
374                                       v,
375                                       (std::unique_ptr<Expression>*) &fContext->fDefined_Expression,
376                                       definitions);
377                     }
378                 }
379                 default:
380                     break;
381             }
382             break;
383         }
384         case BasicBlock::Node::kStatement_Kind: {
385             const Statement* stmt = (Statement*) node.statement()->get();
386             if (stmt->fKind == Statement::kVarDeclaration_Kind) {
387                 VarDeclaration& vd = (VarDeclaration&) *stmt;
388                 if (vd.fValue) {
389                     (*definitions)[vd.fVar] = &vd.fValue;
390                 }
391             }
392             break;
393         }
394     }
395 }
396 
scanCFG(CFG * cfg,BlockId blockId,std::set<BlockId> * workList)397 void Compiler::scanCFG(CFG* cfg, BlockId blockId, std::set<BlockId>* workList) {
398     BasicBlock& block = cfg->fBlocks[blockId];
399 
400     // compute definitions after this block
401     DefinitionMap after = block.fBefore;
402     for (const BasicBlock::Node& n : block.fNodes) {
403         this->addDefinitions(n, &after);
404     }
405 
406     // propagate definitions to exits
407     for (BlockId exitId : block.fExits) {
408         if (exitId == blockId) {
409             continue;
410         }
411         BasicBlock& exit = cfg->fBlocks[exitId];
412         for (const auto& pair : after) {
413             std::unique_ptr<Expression>* e1 = pair.second;
414             auto found = exit.fBefore.find(pair.first);
415             if (found == exit.fBefore.end()) {
416                 // exit has no definition for it, just copy it
417                 workList->insert(exitId);
418                 exit.fBefore[pair.first] = e1;
419             } else {
420                 // exit has a (possibly different) value already defined
421                 std::unique_ptr<Expression>* e2 = exit.fBefore[pair.first];
422                 if (e1 != e2) {
423                     // definition has changed, merge and add exit block to worklist
424                     workList->insert(exitId);
425                     if (e1 && e2) {
426                         exit.fBefore[pair.first] =
427                                       (std::unique_ptr<Expression>*) &fContext->fDefined_Expression;
428                     } else {
429                         exit.fBefore[pair.first] = nullptr;
430                     }
431                 }
432             }
433         }
434     }
435 }
436 
437 // returns a map which maps all local variables in the function to null, indicating that their value
438 // is initially unknown
compute_start_state(const CFG & cfg)439 static DefinitionMap compute_start_state(const CFG& cfg) {
440     DefinitionMap result;
441     for (const auto& block : cfg.fBlocks) {
442         for (const auto& node : block.fNodes) {
443             if (node.fKind == BasicBlock::Node::kStatement_Kind) {
444                 SkASSERT(node.statement());
445                 const Statement* s = node.statement()->get();
446                 if (s->fKind == Statement::kVarDeclarations_Kind) {
447                     const VarDeclarationsStatement* vd = (const VarDeclarationsStatement*) s;
448                     for (const auto& decl : vd->fDeclaration->fVars) {
449                         if (decl->fKind == Statement::kVarDeclaration_Kind) {
450                             result[((VarDeclaration&) *decl).fVar] = nullptr;
451                         }
452                     }
453                 }
454             }
455         }
456     }
457     return result;
458 }
459 
460 /**
461  * Returns true if assigning to this lvalue has no effect.
462  */
is_dead(const Expression & lvalue)463 static bool is_dead(const Expression& lvalue) {
464     switch (lvalue.fKind) {
465         case Expression::kVariableReference_Kind:
466             return ((VariableReference&) lvalue).fVariable.dead();
467         case Expression::kSwizzle_Kind:
468             return is_dead(*((Swizzle&) lvalue).fBase);
469         case Expression::kFieldAccess_Kind:
470             return is_dead(*((FieldAccess&) lvalue).fBase);
471         case Expression::kIndex_Kind: {
472             const IndexExpression& idx = (IndexExpression&) lvalue;
473             return is_dead(*idx.fBase) && !idx.fIndex->hasSideEffects();
474         }
475         case Expression::kTernary_Kind: {
476             const TernaryExpression& t = (TernaryExpression&) lvalue;
477             return !t.fTest->hasSideEffects() && is_dead(*t.fIfTrue) && is_dead(*t.fIfFalse);
478         }
479         case Expression::kExternalValue_Kind:
480             return false;
481         default:
482             ABORT("invalid lvalue: %s\n", lvalue.description().c_str());
483     }
484 }
485 
486 /**
487  * Returns true if this is an assignment which can be collapsed down to just the right hand side due
488  * to a dead target and lack of side effects on the left hand side.
489  */
dead_assignment(const BinaryExpression & b)490 static bool dead_assignment(const BinaryExpression& b) {
491     if (!Compiler::IsAssignment(b.fOperator)) {
492         return false;
493     }
494     return is_dead(*b.fLeft);
495 }
496 
computeDataFlow(CFG * cfg)497 void Compiler::computeDataFlow(CFG* cfg) {
498     cfg->fBlocks[cfg->fStart].fBefore = compute_start_state(*cfg);
499     std::set<BlockId> workList;
500     for (BlockId i = 0; i < cfg->fBlocks.size(); i++) {
501         workList.insert(i);
502     }
503     while (workList.size()) {
504         BlockId next = *workList.begin();
505         workList.erase(workList.begin());
506         this->scanCFG(cfg, next, &workList);
507     }
508 }
509 
510 /**
511  * Attempts to replace the expression pointed to by iter with a new one (in both the CFG and the
512  * IR). If the expression can be cleanly removed, returns true and updates the iterator to point to
513  * the newly-inserted element. Otherwise updates only the IR and returns false (and the CFG will
514  * need to be regenerated).
515  */
try_replace_expression(BasicBlock * b,std::vector<BasicBlock::Node>::iterator * iter,std::unique_ptr<Expression> * newExpression)516 bool try_replace_expression(BasicBlock* b,
517                             std::vector<BasicBlock::Node>::iterator* iter,
518                             std::unique_ptr<Expression>* newExpression) {
519     std::unique_ptr<Expression>* target = (*iter)->expression();
520     if (!b->tryRemoveExpression(iter)) {
521         *target = std::move(*newExpression);
522         return false;
523     }
524     *target = std::move(*newExpression);
525     return b->tryInsertExpression(iter, target);
526 }
527 
528 /**
529  * Returns true if the expression is a constant numeric literal with the specified value, or a
530  * constant vector with all elements equal to the specified value.
531  */
is_constant(const Expression & expr,double value)532 bool is_constant(const Expression& expr, double value) {
533     switch (expr.fKind) {
534         case Expression::kIntLiteral_Kind:
535             return ((IntLiteral&) expr).fValue == value;
536         case Expression::kFloatLiteral_Kind:
537             return ((FloatLiteral&) expr).fValue == value;
538         case Expression::kConstructor_Kind: {
539             Constructor& c = (Constructor&) expr;
540             bool isFloat = c.fType.columns() > 1 ? c.fType.componentType().isFloat()
541                                                  : c.fType.isFloat();
542             if (c.fType.kind() == Type::kVector_Kind && c.isConstant()) {
543                 for (int i = 0; i < c.fType.columns(); ++i) {
544                     if (isFloat) {
545                         if (c.getFVecComponent(i) != value) {
546                             return false;
547                         }
548                     } else if (c.getIVecComponent(i) != value) {
549                         return false;
550                     }
551                 }
552                 return true;
553             }
554             return false;
555         }
556         default:
557             return false;
558     }
559 }
560 
561 /**
562  * Collapses the binary expression pointed to by iter down to just the right side (in both the IR
563  * and CFG structures).
564  */
delete_left(BasicBlock * b,std::vector<BasicBlock::Node>::iterator * iter,bool * outUpdated,bool * outNeedsRescan)565 void delete_left(BasicBlock* b,
566                  std::vector<BasicBlock::Node>::iterator* iter,
567                  bool* outUpdated,
568                  bool* outNeedsRescan) {
569     *outUpdated = true;
570     std::unique_ptr<Expression>* target = (*iter)->expression();
571     SkASSERT((*target)->fKind == Expression::kBinary_Kind);
572     BinaryExpression& bin = (BinaryExpression&) **target;
573     SkASSERT(!bin.fLeft->hasSideEffects());
574     bool result;
575     if (bin.fOperator == Token::EQ) {
576         result = b->tryRemoveLValueBefore(iter, bin.fLeft.get());
577     } else {
578         result = b->tryRemoveExpressionBefore(iter, bin.fLeft.get());
579     }
580     *target = std::move(bin.fRight);
581     if (!result) {
582         *outNeedsRescan = true;
583         return;
584     }
585     if (*iter == b->fNodes.begin()) {
586         *outNeedsRescan = true;
587         return;
588     }
589     --(*iter);
590     if ((*iter)->fKind != BasicBlock::Node::kExpression_Kind ||
591         (*iter)->expression() != &bin.fRight) {
592         *outNeedsRescan = true;
593         return;
594     }
595     *iter = b->fNodes.erase(*iter);
596     SkASSERT((*iter)->expression() == target);
597 }
598 
599 /**
600  * Collapses the binary expression pointed to by iter down to just the left side (in both the IR and
601  * CFG structures).
602  */
delete_right(BasicBlock * b,std::vector<BasicBlock::Node>::iterator * iter,bool * outUpdated,bool * outNeedsRescan)603 void delete_right(BasicBlock* b,
604                   std::vector<BasicBlock::Node>::iterator* iter,
605                   bool* outUpdated,
606                   bool* outNeedsRescan) {
607     *outUpdated = true;
608     std::unique_ptr<Expression>* target = (*iter)->expression();
609     SkASSERT((*target)->fKind == Expression::kBinary_Kind);
610     BinaryExpression& bin = (BinaryExpression&) **target;
611     SkASSERT(!bin.fRight->hasSideEffects());
612     if (!b->tryRemoveExpressionBefore(iter, bin.fRight.get())) {
613         *target = std::move(bin.fLeft);
614         *outNeedsRescan = true;
615         return;
616     }
617     *target = std::move(bin.fLeft);
618     if (*iter == b->fNodes.begin()) {
619         *outNeedsRescan = true;
620         return;
621     }
622     --(*iter);
623     if (((*iter)->fKind != BasicBlock::Node::kExpression_Kind ||
624         (*iter)->expression() != &bin.fLeft)) {
625         *outNeedsRescan = true;
626         return;
627     }
628     *iter = b->fNodes.erase(*iter);
629     SkASSERT((*iter)->expression() == target);
630 }
631 
632 /**
633  * Constructs the specified type using a single argument.
634  */
construct(const Type & type,std::unique_ptr<Expression> v)635 static std::unique_ptr<Expression> construct(const Type& type, std::unique_ptr<Expression> v) {
636     std::vector<std::unique_ptr<Expression>> args;
637     args.push_back(std::move(v));
638     auto result = std::unique_ptr<Expression>(new Constructor(-1, type, std::move(args)));
639     return result;
640 }
641 
642 /**
643  * Used in the implementations of vectorize_left and vectorize_right. Given a vector type and an
644  * expression x, deletes the expression pointed to by iter and replaces it with <type>(x).
645  */
vectorize(BasicBlock * b,std::vector<BasicBlock::Node>::iterator * iter,const Type & type,std::unique_ptr<Expression> * otherExpression,bool * outUpdated,bool * outNeedsRescan)646 static void vectorize(BasicBlock* b,
647                       std::vector<BasicBlock::Node>::iterator* iter,
648                       const Type& type,
649                       std::unique_ptr<Expression>* otherExpression,
650                       bool* outUpdated,
651                       bool* outNeedsRescan) {
652     SkASSERT((*(*iter)->expression())->fKind == Expression::kBinary_Kind);
653     SkASSERT(type.kind() == Type::kVector_Kind);
654     SkASSERT((*otherExpression)->fType.kind() == Type::kScalar_Kind);
655     *outUpdated = true;
656     std::unique_ptr<Expression>* target = (*iter)->expression();
657     if (!b->tryRemoveExpression(iter)) {
658         *target = construct(type, std::move(*otherExpression));
659         *outNeedsRescan = true;
660     } else {
661         *target = construct(type, std::move(*otherExpression));
662         if (!b->tryInsertExpression(iter, target)) {
663             *outNeedsRescan = true;
664         }
665     }
666 }
667 
668 /**
669  * Given a binary expression of the form x <op> vec<n>(y), deletes the right side and vectorizes the
670  * left to yield vec<n>(x).
671  */
vectorize_left(BasicBlock * b,std::vector<BasicBlock::Node>::iterator * iter,bool * outUpdated,bool * outNeedsRescan)672 static void vectorize_left(BasicBlock* b,
673                            std::vector<BasicBlock::Node>::iterator* iter,
674                            bool* outUpdated,
675                            bool* outNeedsRescan) {
676     BinaryExpression& bin = (BinaryExpression&) **(*iter)->expression();
677     vectorize(b, iter, bin.fRight->fType, &bin.fLeft, outUpdated, outNeedsRescan);
678 }
679 
680 /**
681  * Given a binary expression of the form vec<n>(x) <op> y, deletes the left side and vectorizes the
682  * right to yield vec<n>(y).
683  */
vectorize_right(BasicBlock * b,std::vector<BasicBlock::Node>::iterator * iter,bool * outUpdated,bool * outNeedsRescan)684 static void vectorize_right(BasicBlock* b,
685                             std::vector<BasicBlock::Node>::iterator* iter,
686                             bool* outUpdated,
687                             bool* outNeedsRescan) {
688     BinaryExpression& bin = (BinaryExpression&) **(*iter)->expression();
689     vectorize(b, iter, bin.fLeft->fType, &bin.fRight, outUpdated, outNeedsRescan);
690 }
691 
692 // Mark that an expression which we were writing to is no longer being written to
clear_write(const Expression & expr)693 void clear_write(const Expression& expr) {
694     switch (expr.fKind) {
695         case Expression::kVariableReference_Kind: {
696             ((VariableReference&) expr).setRefKind(VariableReference::kRead_RefKind);
697             break;
698         }
699         case Expression::kFieldAccess_Kind:
700             clear_write(*((FieldAccess&) expr).fBase);
701             break;
702         case Expression::kSwizzle_Kind:
703             clear_write(*((Swizzle&) expr).fBase);
704             break;
705         case Expression::kIndex_Kind:
706             clear_write(*((IndexExpression&) expr).fBase);
707             break;
708         default:
709             ABORT("shouldn't be writing to this kind of expression\n");
710             break;
711     }
712 }
713 
simplifyExpression(DefinitionMap & definitions,BasicBlock & b,std::vector<BasicBlock::Node>::iterator * iter,std::unordered_set<const Variable * > * undefinedVariables,bool * outUpdated,bool * outNeedsRescan)714 void Compiler::simplifyExpression(DefinitionMap& definitions,
715                                   BasicBlock& b,
716                                   std::vector<BasicBlock::Node>::iterator* iter,
717                                   std::unordered_set<const Variable*>* undefinedVariables,
718                                   bool* outUpdated,
719                                   bool* outNeedsRescan) {
720     Expression* expr = (*iter)->expression()->get();
721     SkASSERT(expr);
722     if ((*iter)->fConstantPropagation) {
723         std::unique_ptr<Expression> optimized = expr->constantPropagate(*fIRGenerator, definitions);
724         if (optimized) {
725             *outUpdated = true;
726             if (!try_replace_expression(&b, iter, &optimized)) {
727                 *outNeedsRescan = true;
728                 return;
729             }
730             SkASSERT((*iter)->fKind == BasicBlock::Node::kExpression_Kind);
731             expr = (*iter)->expression()->get();
732         }
733     }
734     switch (expr->fKind) {
735         case Expression::kVariableReference_Kind: {
736             const VariableReference& ref = (VariableReference&) *expr;
737             const Variable& var = ref.fVariable;
738             if (ref.refKind() != VariableReference::kWrite_RefKind &&
739                 ref.refKind() != VariableReference::kPointer_RefKind &&
740                 var.fStorage == Variable::kLocal_Storage && !definitions[&var] &&
741                 (*undefinedVariables).find(&var) == (*undefinedVariables).end()) {
742                 (*undefinedVariables).insert(&var);
743                 this->error(expr->fOffset,
744                             "'" + var.fName + "' has not been assigned");
745             }
746             break;
747         }
748         case Expression::kTernary_Kind: {
749             TernaryExpression* t = (TernaryExpression*) expr;
750             if (t->fTest->fKind == Expression::kBoolLiteral_Kind) {
751                 // ternary has a constant test, replace it with either the true or
752                 // false branch
753                 if (((BoolLiteral&) *t->fTest).fValue) {
754                     (*iter)->setExpression(std::move(t->fIfTrue));
755                 } else {
756                     (*iter)->setExpression(std::move(t->fIfFalse));
757                 }
758                 *outUpdated = true;
759                 *outNeedsRescan = true;
760             }
761             break;
762         }
763         case Expression::kBinary_Kind: {
764             BinaryExpression* bin = (BinaryExpression*) expr;
765             if (dead_assignment(*bin)) {
766                 delete_left(&b, iter, outUpdated, outNeedsRescan);
767                 break;
768             }
769             // collapse useless expressions like x * 1 or x + 0
770             if (((bin->fLeft->fType.kind()  != Type::kScalar_Kind) &&
771                  (bin->fLeft->fType.kind()  != Type::kVector_Kind)) ||
772                 ((bin->fRight->fType.kind() != Type::kScalar_Kind) &&
773                  (bin->fRight->fType.kind() != Type::kVector_Kind))) {
774                 break;
775             }
776             switch (bin->fOperator) {
777                 case Token::STAR:
778                     if (is_constant(*bin->fLeft, 1)) {
779                         if (bin->fLeft->fType.kind() == Type::kVector_Kind &&
780                             bin->fRight->fType.kind() == Type::kScalar_Kind) {
781                             // float4(1) * x -> float4(x)
782                             vectorize_right(&b, iter, outUpdated, outNeedsRescan);
783                         } else {
784                             // 1 * x -> x
785                             // 1 * float4(x) -> float4(x)
786                             // float4(1) * float4(x) -> float4(x)
787                             delete_left(&b, iter, outUpdated, outNeedsRescan);
788                         }
789                     }
790                     else if (is_constant(*bin->fLeft, 0)) {
791                         if (bin->fLeft->fType.kind() == Type::kScalar_Kind &&
792                             bin->fRight->fType.kind() == Type::kVector_Kind &&
793                             !bin->fRight->hasSideEffects()) {
794                             // 0 * float4(x) -> float4(0)
795                             vectorize_left(&b, iter, outUpdated, outNeedsRescan);
796                         } else {
797                             // 0 * x -> 0
798                             // float4(0) * x -> float4(0)
799                             // float4(0) * float4(x) -> float4(0)
800                             if (!bin->fRight->hasSideEffects()) {
801                                 delete_right(&b, iter, outUpdated, outNeedsRescan);
802                             }
803                         }
804                     }
805                     else if (is_constant(*bin->fRight, 1)) {
806                         if (bin->fLeft->fType.kind() == Type::kScalar_Kind &&
807                             bin->fRight->fType.kind() == Type::kVector_Kind) {
808                             // x * float4(1) -> float4(x)
809                             vectorize_left(&b, iter, outUpdated, outNeedsRescan);
810                         } else {
811                             // x * 1 -> x
812                             // float4(x) * 1 -> float4(x)
813                             // float4(x) * float4(1) -> float4(x)
814                             delete_right(&b, iter, outUpdated, outNeedsRescan);
815                         }
816                     }
817                     else if (is_constant(*bin->fRight, 0)) {
818                         if (bin->fLeft->fType.kind() == Type::kVector_Kind &&
819                             bin->fRight->fType.kind() == Type::kScalar_Kind &&
820                             !bin->fLeft->hasSideEffects()) {
821                             // float4(x) * 0 -> float4(0)
822                             vectorize_right(&b, iter, outUpdated, outNeedsRescan);
823                         } else {
824                             // x * 0 -> 0
825                             // x * float4(0) -> float4(0)
826                             // float4(x) * float4(0) -> float4(0)
827                             if (!bin->fLeft->hasSideEffects()) {
828                                 delete_left(&b, iter, outUpdated, outNeedsRescan);
829                             }
830                         }
831                     }
832                     break;
833                 case Token::PLUS:
834                     if (is_constant(*bin->fLeft, 0)) {
835                         if (bin->fLeft->fType.kind() == Type::kVector_Kind &&
836                             bin->fRight->fType.kind() == Type::kScalar_Kind) {
837                             // float4(0) + x -> float4(x)
838                             vectorize_right(&b, iter, outUpdated, outNeedsRescan);
839                         } else {
840                             // 0 + x -> x
841                             // 0 + float4(x) -> float4(x)
842                             // float4(0) + float4(x) -> float4(x)
843                             delete_left(&b, iter, outUpdated, outNeedsRescan);
844                         }
845                     } else if (is_constant(*bin->fRight, 0)) {
846                         if (bin->fLeft->fType.kind() == Type::kScalar_Kind &&
847                             bin->fRight->fType.kind() == Type::kVector_Kind) {
848                             // x + float4(0) -> float4(x)
849                             vectorize_left(&b, iter, outUpdated, outNeedsRescan);
850                         } else {
851                             // x + 0 -> x
852                             // float4(x) + 0 -> float4(x)
853                             // float4(x) + float4(0) -> float4(x)
854                             delete_right(&b, iter, outUpdated, outNeedsRescan);
855                         }
856                     }
857                     break;
858                 case Token::MINUS:
859                     if (is_constant(*bin->fRight, 0)) {
860                         if (bin->fLeft->fType.kind() == Type::kScalar_Kind &&
861                             bin->fRight->fType.kind() == Type::kVector_Kind) {
862                             // x - float4(0) -> float4(x)
863                             vectorize_left(&b, iter, outUpdated, outNeedsRescan);
864                         } else {
865                             // x - 0 -> x
866                             // float4(x) - 0 -> float4(x)
867                             // float4(x) - float4(0) -> float4(x)
868                             delete_right(&b, iter, outUpdated, outNeedsRescan);
869                         }
870                     }
871                     break;
872                 case Token::SLASH:
873                     if (is_constant(*bin->fRight, 1)) {
874                         if (bin->fLeft->fType.kind() == Type::kScalar_Kind &&
875                             bin->fRight->fType.kind() == Type::kVector_Kind) {
876                             // x / float4(1) -> float4(x)
877                             vectorize_left(&b, iter, outUpdated, outNeedsRescan);
878                         } else {
879                             // x / 1 -> x
880                             // float4(x) / 1 -> float4(x)
881                             // float4(x) / float4(1) -> float4(x)
882                             delete_right(&b, iter, outUpdated, outNeedsRescan);
883                         }
884                     } else if (is_constant(*bin->fLeft, 0)) {
885                         if (bin->fLeft->fType.kind() == Type::kScalar_Kind &&
886                             bin->fRight->fType.kind() == Type::kVector_Kind &&
887                             !bin->fRight->hasSideEffects()) {
888                             // 0 / float4(x) -> float4(0)
889                             vectorize_left(&b, iter, outUpdated, outNeedsRescan);
890                         } else {
891                             // 0 / x -> 0
892                             // float4(0) / x -> float4(0)
893                             // float4(0) / float4(x) -> float4(0)
894                             if (!bin->fRight->hasSideEffects()) {
895                                 delete_right(&b, iter, outUpdated, outNeedsRescan);
896                             }
897                         }
898                     }
899                     break;
900                 case Token::PLUSEQ:
901                     if (is_constant(*bin->fRight, 0)) {
902                         clear_write(*bin->fLeft);
903                         delete_right(&b, iter, outUpdated, outNeedsRescan);
904                     }
905                     break;
906                 case Token::MINUSEQ:
907                     if (is_constant(*bin->fRight, 0)) {
908                         clear_write(*bin->fLeft);
909                         delete_right(&b, iter, outUpdated, outNeedsRescan);
910                     }
911                     break;
912                 case Token::STAREQ:
913                     if (is_constant(*bin->fRight, 1)) {
914                         clear_write(*bin->fLeft);
915                         delete_right(&b, iter, outUpdated, outNeedsRescan);
916                     }
917                     break;
918                 case Token::SLASHEQ:
919                     if (is_constant(*bin->fRight, 1)) {
920                         clear_write(*bin->fLeft);
921                         delete_right(&b, iter, outUpdated, outNeedsRescan);
922                     }
923                     break;
924                 default:
925                     break;
926             }
927         }
928         default:
929             break;
930     }
931 }
932 
933 // returns true if this statement could potentially execute a break at the current level (we ignore
934 // nested loops and switches, since any breaks inside of them will merely break the loop / switch)
contains_conditional_break(Statement & s,bool inConditional)935 static bool contains_conditional_break(Statement& s, bool inConditional) {
936     switch (s.fKind) {
937         case Statement::kBlock_Kind:
938             for (const auto& sub : ((Block&) s).fStatements) {
939                 if (contains_conditional_break(*sub, inConditional)) {
940                     return true;
941                 }
942             }
943             return false;
944         case Statement::kBreak_Kind:
945             return inConditional;
946         case Statement::kIf_Kind: {
947             const IfStatement& i = (IfStatement&) s;
948             return contains_conditional_break(*i.fIfTrue, true) ||
949                    (i.fIfFalse && contains_conditional_break(*i.fIfFalse, true));
950         }
951         default:
952             return false;
953     }
954 }
955 
956 // returns true if this statement definitely executes a break at the current level (we ignore
957 // nested loops and switches, since any breaks inside of them will merely break the loop / switch)
contains_unconditional_break(Statement & s)958 static bool contains_unconditional_break(Statement& s) {
959     switch (s.fKind) {
960         case Statement::kBlock_Kind:
961             for (const auto& sub : ((Block&) s).fStatements) {
962                 if (contains_unconditional_break(*sub)) {
963                     return true;
964                 }
965             }
966             return false;
967         case Statement::kBreak_Kind:
968             return true;
969         default:
970             return false;
971     }
972 }
973 
974 // Returns a block containing all of the statements that will be run if the given case matches
975 // (which, owing to the statements being owned by unique_ptrs, means the switch itself will be
976 // broken by this call and must then be discarded).
977 // Returns null (and leaves the switch unmodified) if no such simple reduction is possible, such as
978 // when break statements appear inside conditionals.
block_for_case(SwitchStatement * s,SwitchCase * c)979 static std::unique_ptr<Statement> block_for_case(SwitchStatement* s, SwitchCase* c) {
980     bool capturing = false;
981     std::vector<std::unique_ptr<Statement>*> statementPtrs;
982     for (const auto& current : s->fCases) {
983         if (current.get() == c) {
984             capturing = true;
985         }
986         if (capturing) {
987             for (auto& stmt : current->fStatements) {
988                 if (contains_conditional_break(*stmt, s->fKind == Statement::kIf_Kind)) {
989                     return nullptr;
990                 }
991                 if (contains_unconditional_break(*stmt)) {
992                     capturing = false;
993                     break;
994                 }
995                 statementPtrs.push_back(&stmt);
996             }
997             if (!capturing) {
998                 break;
999             }
1000         }
1001     }
1002     std::vector<std::unique_ptr<Statement>> statements;
1003     for (const auto& s : statementPtrs) {
1004         statements.push_back(std::move(*s));
1005     }
1006     return std::unique_ptr<Statement>(new Block(-1, std::move(statements), s->fSymbols));
1007 }
1008 
simplifyStatement(DefinitionMap & definitions,BasicBlock & b,std::vector<BasicBlock::Node>::iterator * iter,std::unordered_set<const Variable * > * undefinedVariables,bool * outUpdated,bool * outNeedsRescan)1009 void Compiler::simplifyStatement(DefinitionMap& definitions,
1010                                  BasicBlock& b,
1011                                  std::vector<BasicBlock::Node>::iterator* iter,
1012                                  std::unordered_set<const Variable*>* undefinedVariables,
1013                                  bool* outUpdated,
1014                                  bool* outNeedsRescan) {
1015     Statement* stmt = (*iter)->statement()->get();
1016     switch (stmt->fKind) {
1017         case Statement::kVarDeclaration_Kind: {
1018             const auto& varDecl = (VarDeclaration&) *stmt;
1019             if (varDecl.fVar->dead() &&
1020                 (!varDecl.fValue ||
1021                  !varDecl.fValue->hasSideEffects())) {
1022                 if (varDecl.fValue) {
1023                     SkASSERT((*iter)->statement()->get() == stmt);
1024                     if (!b.tryRemoveExpressionBefore(iter, varDecl.fValue.get())) {
1025                         *outNeedsRescan = true;
1026                     }
1027                 }
1028                 (*iter)->setStatement(std::unique_ptr<Statement>(new Nop()));
1029                 *outUpdated = true;
1030             }
1031             break;
1032         }
1033         case Statement::kIf_Kind: {
1034             IfStatement& i = (IfStatement&) *stmt;
1035             if (i.fTest->fKind == Expression::kBoolLiteral_Kind) {
1036                 // constant if, collapse down to a single branch
1037                 if (((BoolLiteral&) *i.fTest).fValue) {
1038                     SkASSERT(i.fIfTrue);
1039                     (*iter)->setStatement(std::move(i.fIfTrue));
1040                 } else {
1041                     if (i.fIfFalse) {
1042                         (*iter)->setStatement(std::move(i.fIfFalse));
1043                     } else {
1044                         (*iter)->setStatement(std::unique_ptr<Statement>(new Nop()));
1045                     }
1046                 }
1047                 *outUpdated = true;
1048                 *outNeedsRescan = true;
1049                 break;
1050             }
1051             if (i.fIfFalse && i.fIfFalse->isEmpty()) {
1052                 // else block doesn't do anything, remove it
1053                 i.fIfFalse.reset();
1054                 *outUpdated = true;
1055                 *outNeedsRescan = true;
1056             }
1057             if (!i.fIfFalse && i.fIfTrue->isEmpty()) {
1058                 // if block doesn't do anything, no else block
1059                 if (i.fTest->hasSideEffects()) {
1060                     // test has side effects, keep it
1061                     (*iter)->setStatement(std::unique_ptr<Statement>(
1062                                                       new ExpressionStatement(std::move(i.fTest))));
1063                 } else {
1064                     // no if, no else, no test side effects, kill the whole if
1065                     // statement
1066                     (*iter)->setStatement(std::unique_ptr<Statement>(new Nop()));
1067                 }
1068                 *outUpdated = true;
1069                 *outNeedsRescan = true;
1070             }
1071             break;
1072         }
1073         case Statement::kSwitch_Kind: {
1074             SwitchStatement& s = (SwitchStatement&) *stmt;
1075             if (s.fValue->isConstant()) {
1076                 // switch is constant, replace it with the case that matches
1077                 bool found = false;
1078                 SwitchCase* defaultCase = nullptr;
1079                 for (const auto& c : s.fCases) {
1080                     if (!c->fValue) {
1081                         defaultCase = c.get();
1082                         continue;
1083                     }
1084                     SkASSERT(c->fValue->fKind == s.fValue->fKind);
1085                     found = c->fValue->compareConstant(*fContext, *s.fValue);
1086                     if (found) {
1087                         std::unique_ptr<Statement> newBlock = block_for_case(&s, c.get());
1088                         if (newBlock) {
1089                             (*iter)->setStatement(std::move(newBlock));
1090                             break;
1091                         } else {
1092                             if (s.fIsStatic && !(fFlags & kPermitInvalidStaticTests_Flag)) {
1093                                 this->error(s.fOffset,
1094                                             "static switch contains non-static conditional break");
1095                                 s.fIsStatic = false;
1096                             }
1097                             return; // can't simplify
1098                         }
1099                     }
1100                 }
1101                 if (!found) {
1102                     // no matching case. use default if it exists, or kill the whole thing
1103                     if (defaultCase) {
1104                         std::unique_ptr<Statement> newBlock = block_for_case(&s, defaultCase);
1105                         if (newBlock) {
1106                             (*iter)->setStatement(std::move(newBlock));
1107                         } else {
1108                             if (s.fIsStatic && !(fFlags & kPermitInvalidStaticTests_Flag)) {
1109                                 this->error(s.fOffset,
1110                                             "static switch contains non-static conditional break");
1111                                 s.fIsStatic = false;
1112                             }
1113                             return; // can't simplify
1114                         }
1115                     } else {
1116                         (*iter)->setStatement(std::unique_ptr<Statement>(new Nop()));
1117                     }
1118                 }
1119                 *outUpdated = true;
1120                 *outNeedsRescan = true;
1121             }
1122             break;
1123         }
1124         case Statement::kExpression_Kind: {
1125             ExpressionStatement& e = (ExpressionStatement&) *stmt;
1126             SkASSERT((*iter)->statement()->get() == &e);
1127             if (!e.fExpression->hasSideEffects()) {
1128                 // Expression statement with no side effects, kill it
1129                 if (!b.tryRemoveExpressionBefore(iter, e.fExpression.get())) {
1130                     *outNeedsRescan = true;
1131                 }
1132                 SkASSERT((*iter)->statement()->get() == stmt);
1133                 (*iter)->setStatement(std::unique_ptr<Statement>(new Nop()));
1134                 *outUpdated = true;
1135             }
1136             break;
1137         }
1138         default:
1139             break;
1140     }
1141 }
1142 
scanCFG(FunctionDefinition & f)1143 void Compiler::scanCFG(FunctionDefinition& f) {
1144     CFG cfg = CFGGenerator().getCFG(f);
1145     this->computeDataFlow(&cfg);
1146 
1147     // check for unreachable code
1148     for (size_t i = 0; i < cfg.fBlocks.size(); i++) {
1149         if (i != cfg.fStart && !cfg.fBlocks[i].fEntrances.size() &&
1150             cfg.fBlocks[i].fNodes.size()) {
1151             int offset;
1152             switch (cfg.fBlocks[i].fNodes[0].fKind) {
1153                 case BasicBlock::Node::kStatement_Kind:
1154                     offset = (*cfg.fBlocks[i].fNodes[0].statement())->fOffset;
1155                     break;
1156                 case BasicBlock::Node::kExpression_Kind:
1157                     offset = (*cfg.fBlocks[i].fNodes[0].expression())->fOffset;
1158                     break;
1159             }
1160             this->error(offset, String("unreachable"));
1161         }
1162     }
1163     if (fErrorCount) {
1164         return;
1165     }
1166 
1167     // check for dead code & undefined variables, perform constant propagation
1168     std::unordered_set<const Variable*> undefinedVariables;
1169     bool updated;
1170     bool needsRescan = false;
1171     do {
1172         if (needsRescan) {
1173             cfg = CFGGenerator().getCFG(f);
1174             this->computeDataFlow(&cfg);
1175             needsRescan = false;
1176         }
1177 
1178         updated = false;
1179         for (BasicBlock& b : cfg.fBlocks) {
1180             DefinitionMap definitions = b.fBefore;
1181 
1182             for (auto iter = b.fNodes.begin(); iter != b.fNodes.end() && !needsRescan; ++iter) {
1183                 if (iter->fKind == BasicBlock::Node::kExpression_Kind) {
1184                     this->simplifyExpression(definitions, b, &iter, &undefinedVariables, &updated,
1185                                              &needsRescan);
1186                 } else {
1187                     this->simplifyStatement(definitions, b, &iter, &undefinedVariables, &updated,
1188                                              &needsRescan);
1189                 }
1190                 if (needsRescan) {
1191                     break;
1192                 }
1193                 this->addDefinitions(*iter, &definitions);
1194             }
1195         }
1196     } while (updated);
1197     SkASSERT(!needsRescan);
1198 
1199     // verify static ifs & switches, clean up dead variable decls
1200     for (BasicBlock& b : cfg.fBlocks) {
1201         DefinitionMap definitions = b.fBefore;
1202 
1203         for (auto iter = b.fNodes.begin(); iter != b.fNodes.end() && !needsRescan;) {
1204             if (iter->fKind == BasicBlock::Node::kStatement_Kind) {
1205                 const Statement& s = **iter->statement();
1206                 switch (s.fKind) {
1207                     case Statement::kIf_Kind:
1208                         if (((const IfStatement&) s).fIsStatic &&
1209                             !(fFlags & kPermitInvalidStaticTests_Flag)) {
1210                             this->error(s.fOffset, "static if has non-static test");
1211                         }
1212                         ++iter;
1213                         break;
1214                     case Statement::kSwitch_Kind:
1215                         if (((const SwitchStatement&) s).fIsStatic &&
1216                              !(fFlags & kPermitInvalidStaticTests_Flag)) {
1217                             this->error(s.fOffset, "static switch has non-static test");
1218                         }
1219                         ++iter;
1220                         break;
1221                     case Statement::kVarDeclarations_Kind: {
1222                         VarDeclarations& decls = *((VarDeclarationsStatement&) s).fDeclaration;
1223                         for (auto varIter = decls.fVars.begin(); varIter != decls.fVars.end();) {
1224                             if ((*varIter)->fKind == Statement::kNop_Kind) {
1225                                 varIter = decls.fVars.erase(varIter);
1226                             } else {
1227                                 ++varIter;
1228                             }
1229                         }
1230                         if (!decls.fVars.size()) {
1231                             iter = b.fNodes.erase(iter);
1232                         } else {
1233                             ++iter;
1234                         }
1235                         break;
1236                     }
1237                     default:
1238                         ++iter;
1239                         break;
1240                 }
1241             } else {
1242                 ++iter;
1243             }
1244         }
1245     }
1246 
1247     // check for missing return
1248     if (f.fDeclaration.fReturnType != *fContext->fVoid_Type) {
1249         if (cfg.fBlocks[cfg.fExit].fEntrances.size()) {
1250             this->error(f.fOffset, String("function can exit without returning a value"));
1251         }
1252     }
1253 }
1254 
registerExternalValue(ExternalValue * value)1255 void Compiler::registerExternalValue(ExternalValue* value) {
1256     fIRGenerator->fRootSymbolTable->addWithoutOwnership(value->fName, value);
1257 }
1258 
takeOwnership(std::unique_ptr<Symbol> symbol)1259 Symbol* Compiler::takeOwnership(std::unique_ptr<Symbol> symbol) {
1260     return fIRGenerator->fRootSymbolTable->takeOwnership(std::move(symbol));
1261 }
1262 
convertProgram(Program::Kind kind,String text,const Program::Settings & settings)1263 std::unique_ptr<Program> Compiler::convertProgram(Program::Kind kind, String text,
1264                                                   const Program::Settings& settings) {
1265     fErrorText = "";
1266     fErrorCount = 0;
1267     std::vector<std::unique_ptr<ProgramElement>>* inherited;
1268     std::vector<std::unique_ptr<ProgramElement>> elements;
1269     switch (kind) {
1270         case Program::kVertex_Kind:
1271             inherited = &fVertexInclude;
1272             fIRGenerator->fSymbolTable = fVertexSymbolTable;
1273             fIRGenerator->start(&settings, inherited);
1274             break;
1275         case Program::kFragment_Kind:
1276             inherited = &fFragmentInclude;
1277             fIRGenerator->fSymbolTable = fFragmentSymbolTable;
1278             fIRGenerator->start(&settings, inherited);
1279             break;
1280         case Program::kGeometry_Kind:
1281             inherited = &fGeometryInclude;
1282             fIRGenerator->fSymbolTable = fGeometrySymbolTable;
1283             fIRGenerator->start(&settings, inherited);
1284             break;
1285         case Program::kFragmentProcessor_Kind:
1286             inherited = nullptr;
1287             fIRGenerator->fSymbolTable = fGpuSymbolTable;
1288             fIRGenerator->start(&settings, nullptr);
1289             fIRGenerator->convertProgram(kind, SKSL_FP_INCLUDE, strlen(SKSL_FP_INCLUDE), *fTypes,
1290                                          &elements);
1291             fIRGenerator->fSymbolTable->markAllFunctionsBuiltin();
1292             break;
1293         case Program::kPipelineStage_Kind:
1294             inherited = &fPipelineInclude;
1295             fIRGenerator->fSymbolTable = fPipelineSymbolTable;
1296             fIRGenerator->start(&settings, inherited);
1297             break;
1298         case Program::kGeneric_Kind:
1299             inherited = &fInterpreterInclude;
1300             fIRGenerator->fSymbolTable = fInterpreterSymbolTable;
1301             fIRGenerator->start(&settings, inherited);
1302             break;
1303     }
1304     for (auto& element : elements) {
1305         if (element->fKind == ProgramElement::kEnum_Kind) {
1306             ((Enum&) *element).fBuiltin = true;
1307         }
1308     }
1309     std::unique_ptr<String> textPtr(new String(std::move(text)));
1310     fSource = textPtr.get();
1311     fIRGenerator->convertProgram(kind, textPtr->c_str(), textPtr->size(), *fTypes, &elements);
1312     auto result = std::unique_ptr<Program>(new Program(kind,
1313                                                        std::move(textPtr),
1314                                                        settings,
1315                                                        fContext,
1316                                                        inherited,
1317                                                        std::move(elements),
1318                                                        fIRGenerator->fSymbolTable,
1319                                                        fIRGenerator->fInputs));
1320     if (fErrorCount) {
1321         return nullptr;
1322     }
1323     return result;
1324 }
1325 
optimize(Program & program)1326 bool Compiler::optimize(Program& program) {
1327     SkASSERT(!fErrorCount);
1328     if (!program.fIsOptimized) {
1329         program.fIsOptimized = true;
1330         fIRGenerator->fKind = program.fKind;
1331         fIRGenerator->fSettings = &program.fSettings;
1332         for (auto& element : program) {
1333             if (element.fKind == ProgramElement::kFunction_Kind) {
1334                 this->scanCFG((FunctionDefinition&) element);
1335             }
1336         }
1337         if (program.fKind != Program::kFragmentProcessor_Kind) {
1338             for (auto iter = program.fElements.begin(); iter != program.fElements.end();) {
1339                 if ((*iter)->fKind == ProgramElement::kVar_Kind) {
1340                     VarDeclarations& vars = (VarDeclarations&) **iter;
1341                     for (auto varIter = vars.fVars.begin(); varIter != vars.fVars.end();) {
1342                         const Variable& var = *((VarDeclaration&) **varIter).fVar;
1343                         if (var.dead()) {
1344                             varIter = vars.fVars.erase(varIter);
1345                         } else {
1346                             ++varIter;
1347                         }
1348                     }
1349                     if (vars.fVars.size() == 0) {
1350                         iter = program.fElements.erase(iter);
1351                         continue;
1352                     }
1353                 }
1354                 ++iter;
1355             }
1356         }
1357     }
1358     return fErrorCount == 0;
1359 }
1360 
specialize(Program & program,const std::unordered_map<SkSL::String,SkSL::Program::Settings::Value> & inputs)1361 std::unique_ptr<Program> Compiler::specialize(
1362                    Program& program,
1363                    const std::unordered_map<SkSL::String, SkSL::Program::Settings::Value>& inputs) {
1364     std::vector<std::unique_ptr<ProgramElement>> elements;
1365     for (const auto& e : program) {
1366         elements.push_back(e.clone());
1367     }
1368     Program::Settings settings;
1369     settings.fCaps = program.fSettings.fCaps;
1370     for (auto iter = inputs.begin(); iter != inputs.end(); ++iter) {
1371         settings.fArgs.insert(*iter);
1372     }
1373     std::unique_ptr<Program> result(new Program(program.fKind,
1374                                                 nullptr,
1375                                                 settings,
1376                                                 program.fContext,
1377                                                 program.fInheritedElements,
1378                                                 std::move(elements),
1379                                                 program.fSymbols,
1380                                                 program.fInputs));
1381     return result;
1382 }
1383 
1384 #if defined(SKSL_STANDALONE) || SK_SUPPORT_GPU
1385 
toSPIRV(Program & program,OutputStream & out)1386 bool Compiler::toSPIRV(Program& program, OutputStream& out) {
1387     if (!this->optimize(program)) {
1388         return false;
1389     }
1390 #ifdef SK_ENABLE_SPIRV_VALIDATION
1391     StringStream buffer;
1392     fSource = program.fSource.get();
1393     SPIRVCodeGenerator cg(fContext.get(), &program, this, &buffer);
1394     bool result = cg.generateCode();
1395     fSource = nullptr;
1396     if (result) {
1397         spvtools::SpirvTools tools(SPV_ENV_VULKAN_1_0);
1398         const String& data = buffer.str();
1399         SkASSERT(0 == data.size() % 4);
1400         auto dumpmsg = [](spv_message_level_t, const char*, const spv_position_t&, const char* m) {
1401             SkDebugf("SPIR-V validation error: %s\n", m);
1402         };
1403         tools.SetMessageConsumer(dumpmsg);
1404         // Verify that the SPIR-V we produced is valid. If this SkASSERT fails, check the logs prior
1405         // to the failure to see the validation errors.
1406         SkAssertResult(tools.Validate((const uint32_t*) data.c_str(), data.size() / 4));
1407         out.write(data.c_str(), data.size());
1408     }
1409 #else
1410     fSource = program.fSource.get();
1411     SPIRVCodeGenerator cg(fContext.get(), &program, this, &out);
1412     bool result = cg.generateCode();
1413     fSource = nullptr;
1414 #endif
1415     return result;
1416 }
1417 
toSPIRV(Program & program,String * out)1418 bool Compiler::toSPIRV(Program& program, String* out) {
1419     StringStream buffer;
1420     bool result = this->toSPIRV(program, buffer);
1421     if (result) {
1422         *out = buffer.str();
1423     }
1424     return result;
1425 }
1426 
toGLSL(Program & program,OutputStream & out)1427 bool Compiler::toGLSL(Program& program, OutputStream& out) {
1428     if (!this->optimize(program)) {
1429         return false;
1430     }
1431     fSource = program.fSource.get();
1432     GLSLCodeGenerator cg(fContext.get(), &program, this, &out);
1433     bool result = cg.generateCode();
1434     fSource = nullptr;
1435     return result;
1436 }
1437 
toGLSL(Program & program,String * out)1438 bool Compiler::toGLSL(Program& program, String* out) {
1439     StringStream buffer;
1440     bool result = this->toGLSL(program, buffer);
1441     if (result) {
1442         *out = buffer.str();
1443     }
1444     return result;
1445 }
1446 
toMetal(Program & program,OutputStream & out)1447 bool Compiler::toMetal(Program& program, OutputStream& out) {
1448     if (!this->optimize(program)) {
1449         return false;
1450     }
1451     MetalCodeGenerator cg(fContext.get(), &program, this, &out);
1452     bool result = cg.generateCode();
1453     return result;
1454 }
1455 
toMetal(Program & program,String * out)1456 bool Compiler::toMetal(Program& program, String* out) {
1457     if (!this->optimize(program)) {
1458         return false;
1459     }
1460     StringStream buffer;
1461     bool result = this->toMetal(program, buffer);
1462     if (result) {
1463         *out = buffer.str();
1464     }
1465     return result;
1466 }
1467 
toCPP(Program & program,String name,OutputStream & out)1468 bool Compiler::toCPP(Program& program, String name, OutputStream& out) {
1469     if (!this->optimize(program)) {
1470         return false;
1471     }
1472     fSource = program.fSource.get();
1473     CPPCodeGenerator cg(fContext.get(), &program, this, name, &out);
1474     bool result = cg.generateCode();
1475     fSource = nullptr;
1476     return result;
1477 }
1478 
toH(Program & program,String name,OutputStream & out)1479 bool Compiler::toH(Program& program, String name, OutputStream& out) {
1480     if (!this->optimize(program)) {
1481         return false;
1482     }
1483     fSource = program.fSource.get();
1484     HCodeGenerator cg(fContext.get(), &program, this, name, &out);
1485     bool result = cg.generateCode();
1486     fSource = nullptr;
1487     return result;
1488 }
1489 
toPipelineStage(const Program & program,String * out,std::vector<FormatArg> * outFormatArgs)1490 bool Compiler::toPipelineStage(const Program& program, String* out,
1491                                std::vector<FormatArg>* outFormatArgs) {
1492     SkASSERT(program.fIsOptimized);
1493     fSource = program.fSource.get();
1494     StringStream buffer;
1495     PipelineStageCodeGenerator cg(fContext.get(), &program, this, &buffer, outFormatArgs);
1496     bool result = cg.generateCode();
1497     fSource = nullptr;
1498     if (result) {
1499         *out = buffer.str();
1500     }
1501     return result;
1502 }
1503 
1504 #endif
1505 
toByteCode(Program & program)1506 std::unique_ptr<ByteCode> Compiler::toByteCode(Program& program) {
1507 #if defined(SK_ENABLE_SKSL_INTERPRETER)
1508     if (!this->optimize(program)) {
1509         return nullptr;
1510     }
1511     std::unique_ptr<ByteCode> result(new ByteCode());
1512     ByteCodeGenerator cg(fContext.get(), &program, this, result.get());
1513     if (cg.generateCode()) {
1514         return result;
1515     }
1516 #else
1517     ABORT("ByteCode interpreter not enabled");
1518 #endif
1519     return nullptr;
1520 }
1521 
OperatorName(Token::Kind kind)1522 const char* Compiler::OperatorName(Token::Kind kind) {
1523     switch (kind) {
1524         case Token::PLUS:         return "+";
1525         case Token::MINUS:        return "-";
1526         case Token::STAR:         return "*";
1527         case Token::SLASH:        return "/";
1528         case Token::PERCENT:      return "%";
1529         case Token::SHL:          return "<<";
1530         case Token::SHR:          return ">>";
1531         case Token::LOGICALNOT:   return "!";
1532         case Token::LOGICALAND:   return "&&";
1533         case Token::LOGICALOR:    return "||";
1534         case Token::LOGICALXOR:   return "^^";
1535         case Token::BITWISENOT:   return "~";
1536         case Token::BITWISEAND:   return "&";
1537         case Token::BITWISEOR:    return "|";
1538         case Token::BITWISEXOR:   return "^";
1539         case Token::EQ:           return "=";
1540         case Token::EQEQ:         return "==";
1541         case Token::NEQ:          return "!=";
1542         case Token::LT:           return "<";
1543         case Token::GT:           return ">";
1544         case Token::LTEQ:         return "<=";
1545         case Token::GTEQ:         return ">=";
1546         case Token::PLUSEQ:       return "+=";
1547         case Token::MINUSEQ:      return "-=";
1548         case Token::STAREQ:       return "*=";
1549         case Token::SLASHEQ:      return "/=";
1550         case Token::PERCENTEQ:    return "%=";
1551         case Token::SHLEQ:        return "<<=";
1552         case Token::SHREQ:        return ">>=";
1553         case Token::LOGICALANDEQ: return "&&=";
1554         case Token::LOGICALOREQ:  return "||=";
1555         case Token::LOGICALXOREQ: return "^^=";
1556         case Token::BITWISEANDEQ: return "&=";
1557         case Token::BITWISEOREQ:  return "|=";
1558         case Token::BITWISEXOREQ: return "^=";
1559         case Token::PLUSPLUS:     return "++";
1560         case Token::MINUSMINUS:   return "--";
1561         case Token::COMMA:        return ",";
1562         default:
1563             ABORT("unsupported operator: %d\n", kind);
1564     }
1565 }
1566 
1567 
IsAssignment(Token::Kind op)1568 bool Compiler::IsAssignment(Token::Kind op) {
1569     switch (op) {
1570         case Token::EQ:           // fall through
1571         case Token::PLUSEQ:       // fall through
1572         case Token::MINUSEQ:      // fall through
1573         case Token::STAREQ:       // fall through
1574         case Token::SLASHEQ:      // fall through
1575         case Token::PERCENTEQ:    // fall through
1576         case Token::SHLEQ:        // fall through
1577         case Token::SHREQ:        // fall through
1578         case Token::BITWISEOREQ:  // fall through
1579         case Token::BITWISEXOREQ: // fall through
1580         case Token::BITWISEANDEQ: // fall through
1581         case Token::LOGICALOREQ:  // fall through
1582         case Token::LOGICALXOREQ: // fall through
1583         case Token::LOGICALANDEQ:
1584             return true;
1585         default:
1586             return false;
1587     }
1588 }
1589 
position(int offset)1590 Position Compiler::position(int offset) {
1591     SkASSERT(fSource);
1592     int line = 1;
1593     int column = 1;
1594     for (int i = 0; i < offset; i++) {
1595         if ((*fSource)[i] == '\n') {
1596             ++line;
1597             column = 1;
1598         }
1599         else {
1600             ++column;
1601         }
1602     }
1603     return Position(line, column);
1604 }
1605 
error(int offset,String msg)1606 void Compiler::error(int offset, String msg) {
1607     fErrorCount++;
1608     Position pos = this->position(offset);
1609     fErrorText += "error: " + to_string(pos.fLine) + ": " + msg.c_str() + "\n";
1610 }
1611 
errorText()1612 String Compiler::errorText() {
1613     this->writeErrorCount();
1614     fErrorCount = 0;
1615     String result = fErrorText;
1616     return result;
1617 }
1618 
writeErrorCount()1619 void Compiler::writeErrorCount() {
1620     if (fErrorCount) {
1621         fErrorText += to_string(fErrorCount) + " error";
1622         if (fErrorCount > 1) {
1623             fErrorText += "s";
1624         }
1625         fErrorText += "\n";
1626     }
1627 }
1628 
1629 } // namespace
1630