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
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            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
120struct CFG {
121    BlockId fStart;
122    BlockId fExit;
123    std::vector<BasicBlock> fBlocks;
124
125    void dump();
126
127private:
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 */
151class CFGGenerator {
152public:
153    CFGGenerator() {}
154
155    CFG getCFG(FunctionDefinition& f);
156
157private:
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