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