SkSLCFGGenerator.h 5.8 KB

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