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 Node(Kind kind, bool constantPropagation, std::unique_ptr<Expression>* expression, 30 std::unique_ptr<Statement>* statement) 31 : fKind(kind) 32 , fConstantPropagation(constantPropagation) 33 , fExpression(expression) 34 , fStatement(statement) {} 35 36 std::unique_ptr<Expression>* expression() const { 37 ASSERT(fKind == kExpression_Kind); 38 return fExpression; 39 } 40 41 void setExpression(std::unique_ptr<Expression> expr) { 42 ASSERT(fKind == kExpression_Kind); 43 *fExpression = std::move(expr); 44 } 45 46 std::unique_ptr<Statement>* statement() const { 47 ASSERT(fKind == kStatement_Kind); 48 return fStatement; 49 } 50 51 void setStatement(std::unique_ptr<Statement> stmt) { 52 ASSERT(fKind == kStatement_Kind); 53 *fStatement = std::move(stmt); 54 } 55 56 String description() const { 57 if (fKind == kStatement_Kind) { 58 return (*fStatement)->description(); 59 } else { 60 ASSERT(fKind == kExpression_Kind); 61 return (*fExpression)->description(); 62 } 63 } 64 65 Kind fKind; 66 // if false, this node should not be subject to constant propagation. This happens with 67 // compound assignment (i.e. x *= 2), in which the value x is used as an rvalue for 68 // multiplication by 2 and then as an lvalue for assignment purposes. Since there is only 69 // one "x" node, replacing it with a constant would break the assignment and we suppress 70 // it. Down the road, we should handle this more elegantly by substituting a regular 71 // assignment if the target is constant (i.e. x = 1; x *= 2; should become x = 1; x = 1 * 2; 72 // and then collapse down to a simple x = 2;). 73 bool fConstantPropagation; 74 75 private: 76 // we store pointers to the unique_ptrs so that we can replace expressions or statements 77 // during optimization without having to regenerate the entire tree 78 std::unique_ptr<Expression>* fExpression; 79 std::unique_ptr<Statement>* fStatement; 80 }; 81 82 /** 83 * Attempts to remove the expression (and its subexpressions) pointed to by the iterator. If the 84 * expression can be cleanly removed, returns true and updates the iterator to point to the 85 * expression after the deleted expression. Otherwise returns false (and the CFG will need to be 86 * regenerated). 87 */ 88 bool tryRemoveExpression(std::vector<BasicBlock::Node>::iterator* iter); 89 90 /** 91 * Locates and attempts remove an expression occurring before the expression pointed to by iter. 92 * If the expression can be cleanly removed, returns true and resets iter to a valid iterator 93 * pointing to the same expression it did initially. Otherwise returns false (and the CFG will 94 * need to be regenerated). 95 */ 96 bool tryRemoveExpressionBefore(std::vector<BasicBlock::Node>::iterator* iter, Expression* e); 97 98 /** 99 * As tryRemoveExpressionBefore, but for lvalues. As lvalues are at most partially evaluated 100 * (for instance, x[i] = 0 evaluates i but not x) this will only look for the parts of the 101 * lvalue that are actually evaluated. 102 */ 103 bool tryRemoveLValueBefore(std::vector<BasicBlock::Node>::iterator* iter, Expression* lvalue); 104 105 /** 106 * Attempts to inserts a new expression before the node pointed to by iter. If the 107 * expression can be cleanly inserted, returns true and updates the iterator to point to the 108 * newly inserted expression. Otherwise returns false (and the CFG will need to be regenerated). 109 */ 110 bool tryInsertExpression(std::vector<BasicBlock::Node>::iterator* iter, 111 std::unique_ptr<Expression>* expr); 112 113 std::vector<Node> fNodes; 114 std::set<BlockId> fEntrances; 115 std::set<BlockId> fExits; 116 // variable definitions upon entering this basic block (null expression = undefined) 117 DefinitionMap fBefore; 118 }; 119 120 struct CFG { 121 BlockId fStart; 122 BlockId fExit; 123 std::vector<BasicBlock> fBlocks; 124 125 void dump(); 126 127 private: 128 BlockId fCurrent; 129 130 // Adds a new block, adds an exit* from the current block to the new block, then marks the new 131 // block as the current block 132 // *see note in addExit() 133 BlockId newBlock(); 134 135 // Adds a new block, but does not mark it current or add an exit from the current block 136 BlockId newIsolatedBlock(); 137 138 // Adds an exit from the 'from' block to the 'to' block 139 // Note that we skip adding the exit if the 'from' block is itself unreachable; this means that 140 // we don't actually have to trace the tree to see if a particular block is unreachable, we can 141 // just check to see if it has any entrances. This does require a bit of care in the order in 142 // which we set the CFG up. 143 void addExit(BlockId from, BlockId to); 144 145 friend class CFGGenerator; 146 }; 147 148 /** 149 * Converts functions into control flow graphs. 150 */ 151 class CFGGenerator { 152 public: 153 CFGGenerator() {} 154 155 CFG getCFG(FunctionDefinition& f); 156 157 private: 158 void addStatement(CFG& cfg, std::unique_ptr<Statement>* s); 159 160 void addExpression(CFG& cfg, std::unique_ptr<Expression>* e, bool constantPropagate); 161 162 void addLValue(CFG& cfg, std::unique_ptr<Expression>* e); 163 164 std::stack<BlockId> fLoopContinues; 165 std::stack<BlockId> fLoopExits; 166 }; 167 168 } 169 170 #endif 171
