SkSLCompiler.cpp 63 KB

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