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