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 "src/sksl/ir/SkSLExpression.h"
12 #include "src/sksl/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 
NodeBasicBlock::Node29         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 
expressionBasicBlock::Node36         std::unique_ptr<Expression>* expression() const {
37             SkASSERT(fKind == kExpression_Kind);
38             return fExpression;
39         }
40 
setExpressionBasicBlock::Node41         void setExpression(std::unique_ptr<Expression> expr) {
42             SkASSERT(fKind == kExpression_Kind);
43             *fExpression = std::move(expr);
44         }
45 
statementBasicBlock::Node46         std::unique_ptr<Statement>* statement() const {
47             SkASSERT(fKind == kStatement_Kind);
48             return fStatement;
49         }
50 
setStatementBasicBlock::Node51         void setStatement(std::unique_ptr<Statement> stmt) {
52             SkASSERT(fKind == kStatement_Kind);
53             *fStatement = std::move(stmt);
54         }
55 
descriptionBasicBlock::Node56         String description() const {
57             if (fKind == kStatement_Kind) {
58                 return (*fStatement)->description();
59             } else {
60                 SkASSERT(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:
CFGGenerator()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