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 #ifndef SKSL_CFGGENERATOR 9 #define SKSL_CFGGENERATOR 10 11 #include "ir/SkSLExpression.h" 12 #include "ir/SkSLFunctionDefinition.h" 13 14 #include <set> 15 #include <stack> 16 17 namespace SkSL { 18 19 // index of a block within CFG.fBlocks 20 typedef size_t BlockId; 21 22 struct BasicBlock { 23 struct Node { 24 enum Kind { 25 kStatement_Kind, 26 kExpression_Kind 27 }; 28 29 Kind fKind; 30 // if false, this node should not be subject to constant propagation. This happens with 31 // compound assignment (i.e. x *= 2), in which the value x is used as an rvalue for 32 // multiplication by 2 and then as an lvalue for assignment purposes. Since there is only 33 // one "x" node, replacing it with a constant would break the assignment and we suppress 34 // it. Down the road, we should handle this more elegantly by substituting a regular 35 // assignment if the target is constant (i.e. x = 1; x *= 2; should become x = 1; x = 1 * 2; 36 // and then collapse down to a simple x = 2;). 37 bool fConstantPropagation; 38 std::unique_ptr<Expression>* fExpression; 39 const Statement* fStatement; 40 }; 41 42 std::vector<Node> fNodes; 43 std::set<BlockId> fEntrances; 44 std::set<BlockId> fExits; 45 // variable definitions upon entering this basic block (null expression = undefined) 46 DefinitionMap fBefore; 47 }; 48 49 struct CFG { 50 BlockId fStart; 51 BlockId fExit; 52 std::vector<BasicBlock> fBlocks; 53 54 void dump(); 55 56 private: 57 BlockId fCurrent; 58 59 // Adds a new block, adds an exit* from the current block to the new block, then marks the new 60 // block as the current block 61 // *see note in addExit() 62 BlockId newBlock(); 63 64 // Adds a new block, but does not mark it current or add an exit from the current block 65 BlockId newIsolatedBlock(); 66 67 // Adds an exit from the 'from' block to the 'to' block 68 // Note that we skip adding the exit if the 'from' block is itself unreachable; this means that 69 // we don't actually have to trace the tree to see if a particular block is unreachable, we can 70 // just check to see if it has any entrances. This does require a bit of care in the order in 71 // which we set the CFG up. 72 void addExit(BlockId from, BlockId to); 73 74 friend class CFGGenerator; 75 }; 76 77 /** 78 * Converts functions into control flow graphs. 79 */ 80 class CFGGenerator { 81 public: CFGGenerator()82 CFGGenerator() {} 83 84 CFG getCFG(const FunctionDefinition& f); 85 86 private: 87 void addStatement(CFG& cfg, const Statement* s); 88 89 void addExpression(CFG& cfg, std::unique_ptr<Expression>* e, bool constantPropagate); 90 91 void addLValue(CFG& cfg, std::unique_ptr<Expression>* e); 92 93 std::stack<BlockId> fLoopContinues; 94 std::stack<BlockId> fLoopExits; 95 }; 96 97 } 98 99 #endif 100