| /* |
| * 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 "include/private/SkTArray.h" |
| #include "src/sksl/ir/SkSLExpression.h" |
| #include "src/sksl/ir/SkSLFunctionDefinition.h" |
| |
| #include <stack> |
| |
| namespace SkSL { |
| |
| class ProgramUsage; |
| |
| // index of a block within CFG.fBlocks |
| typedef size_t BlockId; |
| |
| // Conceptually, this is part of BasicBlock, but structs inside structs can't be forward-declared; |
| // this name can be used in places where forward declaration is required. |
| class BasicBlockNode { |
| public: |
| BasicBlockNode(std::unique_ptr<Statement>* statement) |
| : fConstantPropagation(false) |
| , fExpression(nullptr) |
| , fStatement(statement) {} |
| |
| BasicBlockNode(std::unique_ptr<Expression>* expression, bool constantPropagation) |
| : fConstantPropagation(constantPropagation) |
| , fExpression(expression) |
| , fStatement(nullptr) {} |
| |
| bool isExpression() const { |
| return fExpression != nullptr; |
| } |
| |
| std::unique_ptr<Expression>* expression() const { |
| SkASSERT(!this->isStatement()); |
| return fExpression; |
| } |
| |
| // See comment below on setStatement. Assumption is that 'expr' is a strict subset of the |
| // existing expression. |
| void setExpression(std::unique_ptr<Expression> expr, ProgramUsage* usage); |
| |
| bool isStatement() const { |
| return fStatement != nullptr; |
| } |
| |
| std::unique_ptr<Statement>* statement() const { |
| SkASSERT(!this->isExpression()); |
| return fStatement; |
| } |
| |
| // Replaces the pointed-to statement with 'stmt'. The assumption is that 'stmt' is a strict |
| // subset of the existing statement, or a Nop. For example: just the True or False of an if, |
| // or a single Case from a Switch. To maintain usage's bookkeeping, we remove references in |
| // this node's pointed-to statement. By the time this is called, there is no path from our |
| // statement to 'stmt', because it's been moved to the argument. |
| // If stmt is Nop, returns the previous statement, otherwise nullptr. |
| std::unique_ptr<Statement> setStatement(std::unique_ptr<Statement> stmt, |
| ProgramUsage* usage); |
| |
| #ifdef SK_DEBUG |
| String description() const { |
| SkASSERT(fStatement || fExpression); |
| if (fStatement) { |
| return *fStatement ? (*fStatement)->description() : "(null statement)"; |
| } else if (fExpression) { |
| return *fExpression ? (*fExpression)->description() : "(null expression)"; |
| } else { |
| return "(nothing)"; |
| } |
| } |
| #endif |
| |
| // 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; |
| }; |
| |
| struct BasicBlock { |
| using Node = BasicBlockNode; |
| |
| static Node MakeStatement(std::unique_ptr<Statement>* stmt) { |
| return Node{stmt}; |
| } |
| |
| static Node MakeExpression(std::unique_ptr<Expression>* expr, bool constantPropagation) { |
| return Node{expr, constantPropagation}; |
| } |
| |
| /** |
| * 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); |
| |
| #ifdef SK_DEBUG |
| void dump() const; |
| #endif |
| |
| std::vector<Node> fNodes; |
| bool fIsReachable = false; |
| bool fAllowUnreachable = false; |
| using ExitArray = SkSTArray<4, BlockId>; |
| ExitArray fExits; |
| // variable definitions upon entering this basic block (null expression = undefined) |
| DefinitionMap fBefore; |
| }; |
| |
| struct CFG { |
| BlockId fStart; |
| BlockId fExit; |
| std::vector<BasicBlock> fBlocks; |
| |
| #ifdef SK_DEBUG |
| void dump() const; |
| #endif |
| |
| 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); |
| |
| // Convenience method to return the CFG's current block. |
| BasicBlock& currentBlock() { return fBlocks[fCurrent]; } |
| |
| 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; |
| }; |
| |
| } // namespace SkSL |
| |
| #endif |