Line data    Source code

       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             : 
      17             : namespace SkSL {
      18             : 
      19             : // index of a block within CFG.fBlocks
      20             : typedef size_t BlockId;
      21             : 
      22           0 : struct BasicBlock {
      23             :     struct Node {
      24             :         enum Kind {
      25             :             kStatement_Kind,
      26             :             kExpression_Kind
      27             :         };
      28             : 
      29             :         Kind fKind;
      30             :         // if false, this node should not be subject to constant propagation. This happens with
      31             :         // compound assignment (i.e. x *= 2), in which the value x is used as an rvalue for
      32             :         // multiplication by 2 and then as an lvalue for assignment purposes. Since there is only
      33             :         // one "x" node, replacing it with a constant would break the assignment and we suppress
      34             :         // it. Down the road, we should handle this more elegantly by substituting a regular
      35             :         // assignment if the target is constant (i.e. x = 1; x *= 2; should become x = 1; x = 1 * 2;
      36             :         // and then collapse down to a simple x = 2;).
      37             :         bool fConstantPropagation;
      38             :         std::unique_ptr<Expression>* fExpression;
      39             :         const Statement* fStatement;
      40             :     };
      41             : 
      42             :     std::vector<Node> fNodes;
      43             :     std::set<BlockId> fEntrances;
      44             :     std::set<BlockId> fExits;
      45             :     // variable definitions upon entering this basic block (null expression = undefined)
      46             :     DefinitionMap fBefore;
      47             : };
      48             : 
      49           0 : struct CFG {
      50             :     BlockId fStart;
      51             :     BlockId fExit;
      52             :     std::vector<BasicBlock> fBlocks;
      53             : 
      54             :     void dump();
      55             : 
      56             : private:
      57             :     BlockId fCurrent;
      58             : 
      59             :     // Adds a new block, adds an exit* from the current block to the new block, then marks the new
      60             :     // block as the current block
      61             :     // *see note in addExit()
      62             :     BlockId newBlock();
      63             : 
      64             :     // Adds a new block, but does not mark it current or add an exit from the current block
      65             :     BlockId newIsolatedBlock();
      66             : 
      67             :     // Adds an exit from the 'from' block to the 'to' block
      68             :     // Note that we skip adding the exit if the 'from' block is itself unreachable; this means that
      69             :     // we don't actually have to trace the tree to see if a particular block is unreachable, we can
      70             :     // just check to see if it has any entrances. This does require a bit of care in the order in
      71             :     // which we set the CFG up.
      72             :     void addExit(BlockId from, BlockId to);
      73             : 
      74             :     friend class CFGGenerator;
      75             : };
      76             : 
      77             : /**
      78             :  * Converts functions into control flow graphs.
      79             :  */
      80           0 : class CFGGenerator {
      81             : public:
      82           0 :     CFGGenerator() {}
      83             : 
      84             :     CFG getCFG(const FunctionDefinition& f);
      85             : 
      86             : private:
      87             :     void addStatement(CFG& cfg, const Statement* s);
      88             : 
      89             :     void addExpression(CFG& cfg, std::unique_ptr<Expression>* e, bool constantPropagate);
      90             : 
      91             :     void addLValue(CFG& cfg, std::unique_ptr<Expression>* e);
      92             : 
      93             :     std::stack<BlockId> fLoopContinues;
      94             :     std::stack<BlockId> fLoopExits;
      95             : };
      96             : 
      97             : }
      98             : 
      99             : #endif