ethannicholas | 22f939e | 2016-10-13 13:25:34 -0700 | [diff] [blame] | 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 | */ |
Ethan Nicholas | 0df1b04 | 2017-03-31 13:56:23 -0400 | [diff] [blame] | 7 | |
ethannicholas | 22f939e | 2016-10-13 13:25:34 -0700 | [diff] [blame] | 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 | |
Ethan Nicholas | cb67096 | 2017-04-20 19:31:52 -0400 | [diff] [blame] | 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 { |
Ethan Nicholas | d9d33c3 | 2018-06-12 11:05:59 -0400 | [diff] [blame] | 37 | SkASSERT(fKind == kExpression_Kind); |
Ethan Nicholas | cb67096 | 2017-04-20 19:31:52 -0400 | [diff] [blame] | 38 | return fExpression; |
| 39 | } |
| 40 | |
| 41 | void setExpression(std::unique_ptr<Expression> expr) { |
Ethan Nicholas | d9d33c3 | 2018-06-12 11:05:59 -0400 | [diff] [blame] | 42 | SkASSERT(fKind == kExpression_Kind); |
Ethan Nicholas | cb67096 | 2017-04-20 19:31:52 -0400 | [diff] [blame] | 43 | *fExpression = std::move(expr); |
| 44 | } |
| 45 | |
| 46 | std::unique_ptr<Statement>* statement() const { |
Ethan Nicholas | d9d33c3 | 2018-06-12 11:05:59 -0400 | [diff] [blame] | 47 | SkASSERT(fKind == kStatement_Kind); |
Ethan Nicholas | cb67096 | 2017-04-20 19:31:52 -0400 | [diff] [blame] | 48 | return fStatement; |
| 49 | } |
| 50 | |
| 51 | void setStatement(std::unique_ptr<Statement> stmt) { |
Ethan Nicholas | d9d33c3 | 2018-06-12 11:05:59 -0400 | [diff] [blame] | 52 | SkASSERT(fKind == kStatement_Kind); |
Ethan Nicholas | cb67096 | 2017-04-20 19:31:52 -0400 | [diff] [blame] | 53 | *fStatement = std::move(stmt); |
| 54 | } |
| 55 | |
| 56 | String description() const { |
| 57 | if (fKind == kStatement_Kind) { |
| 58 | return (*fStatement)->description(); |
| 59 | } else { |
Ethan Nicholas | d9d33c3 | 2018-06-12 11:05:59 -0400 | [diff] [blame] | 60 | SkASSERT(fKind == kExpression_Kind); |
Ethan Nicholas | cb67096 | 2017-04-20 19:31:52 -0400 | [diff] [blame] | 61 | return (*fExpression)->description(); |
| 62 | } |
| 63 | } |
| 64 | |
ethannicholas | 22f939e | 2016-10-13 13:25:34 -0700 | [diff] [blame] | 65 | Kind fKind; |
Ethan Nicholas | 86a4340 | 2017-01-19 13:32:00 -0500 | [diff] [blame] | 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; |
Ethan Nicholas | cb67096 | 2017-04-20 19:31:52 -0400 | [diff] [blame] | 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 |
Ethan Nicholas | 86a4340 | 2017-01-19 13:32:00 -0500 | [diff] [blame] | 78 | std::unique_ptr<Expression>* fExpression; |
Ethan Nicholas | cb67096 | 2017-04-20 19:31:52 -0400 | [diff] [blame] | 79 | std::unique_ptr<Statement>* fStatement; |
ethannicholas | 22f939e | 2016-10-13 13:25:34 -0700 | [diff] [blame] | 80 | }; |
Ethan Nicholas | 86a4340 | 2017-01-19 13:32:00 -0500 | [diff] [blame] | 81 | |
Ethan Nicholas | cb67096 | 2017-04-20 19:31:52 -0400 | [diff] [blame] | 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 | |
ethannicholas | 22f939e | 2016-10-13 13:25:34 -0700 | [diff] [blame] | 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) |
Ethan Nicholas | 86a4340 | 2017-01-19 13:32:00 -0500 | [diff] [blame] | 117 | DefinitionMap fBefore; |
ethannicholas | 22f939e | 2016-10-13 13:25:34 -0700 | [diff] [blame] | 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 | |
Ethan Nicholas | cb67096 | 2017-04-20 19:31:52 -0400 | [diff] [blame] | 155 | CFG getCFG(FunctionDefinition& f); |
ethannicholas | 22f939e | 2016-10-13 13:25:34 -0700 | [diff] [blame] | 156 | |
| 157 | private: |
Ethan Nicholas | cb67096 | 2017-04-20 19:31:52 -0400 | [diff] [blame] | 158 | void addStatement(CFG& cfg, std::unique_ptr<Statement>* s); |
ethannicholas | 22f939e | 2016-10-13 13:25:34 -0700 | [diff] [blame] | 159 | |
Ethan Nicholas | 86a4340 | 2017-01-19 13:32:00 -0500 | [diff] [blame] | 160 | void addExpression(CFG& cfg, std::unique_ptr<Expression>* e, bool constantPropagate); |
ethannicholas | 22f939e | 2016-10-13 13:25:34 -0700 | [diff] [blame] | 161 | |
Ethan Nicholas | 86a4340 | 2017-01-19 13:32:00 -0500 | [diff] [blame] | 162 | void addLValue(CFG& cfg, std::unique_ptr<Expression>* e); |
ethannicholas | 22f939e | 2016-10-13 13:25:34 -0700 | [diff] [blame] | 163 | |
| 164 | std::stack<BlockId> fLoopContinues; |
| 165 | std::stack<BlockId> fLoopExits; |
| 166 | }; |
| 167 | |
| 168 | } |
| 169 | |
| 170 | #endif |