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