Line data    Source code

       1             : // Copyright 2016 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #ifndef V8_COMPILER_LOOP_VARIABLE_OPTIMIZER_H_
       6             : #define V8_COMPILER_LOOP_VARIABLE_OPTIMIZER_H_
       7             : 
       8             : #include "src/compiler/functional-list.h"
       9             : #include "src/compiler/node-aux-data.h"
      10             : #include "src/zone/zone-containers.h"
      11             : 
      12             : namespace v8 {
      13             : namespace internal {
      14             : namespace compiler {
      15             : 
      16             : class CommonOperatorBuilder;
      17             : class Graph;
      18             : class Node;
      19             : 
      20             : class InductionVariable : public ZoneObject {
      21             :  public:
      22             :   Node* phi() const { return phi_; }
      23             :   Node* effect_phi() const { return effect_phi_; }
      24             :   Node* arith() const { return arith_; }
      25             :   Node* increment() const { return increment_; }
      26             :   Node* init_value() const { return init_value_; }
      27             : 
      28             :   enum ConstraintKind { kStrict, kNonStrict };
      29             :   enum ArithmeticType { kAddition, kSubtraction };
      30             :   struct Bound {
      31       12321 :     Bound(Node* bound, ConstraintKind kind) : bound(bound), kind(kind) {}
      32             : 
      33             :     Node* bound;
      34             :     ConstraintKind kind;
      35             :   };
      36             : 
      37             :   const ZoneVector<Bound>& lower_bounds() { return lower_bounds_; }
      38             :   const ZoneVector<Bound>& upper_bounds() { return upper_bounds_; }
      39             : 
      40             :   ArithmeticType Type() { return arithmeticType_; }
      41             : 
      42             :  private:
      43             :   friend class LoopVariableOptimizer;
      44             : 
      45             :   InductionVariable(Node* phi, Node* effect_phi, Node* arith, Node* increment,
      46             :                     Node* init_value, Zone* zone, ArithmeticType arithmeticType)
      47             :       : phi_(phi),
      48             :         effect_phi_(effect_phi),
      49             :         arith_(arith),
      50             :         increment_(increment),
      51             :         init_value_(init_value),
      52             :         lower_bounds_(zone),
      53             :         upper_bounds_(zone),
      54       35568 :         arithmeticType_(arithmeticType) {}
      55             : 
      56             :   void AddUpperBound(Node* bound, ConstraintKind kind);
      57             :   void AddLowerBound(Node* bound, ConstraintKind kind);
      58             : 
      59             :   Node* phi_;
      60             :   Node* effect_phi_;
      61             :   Node* arith_;
      62             :   Node* increment_;
      63             :   Node* init_value_;
      64             :   ZoneVector<Bound> lower_bounds_;
      65             :   ZoneVector<Bound> upper_bounds_;
      66             :   ArithmeticType arithmeticType_;
      67             : };
      68             : 
      69      463899 : class LoopVariableOptimizer {
      70             :  public:
      71             :   void Run();
      72             : 
      73             :   LoopVariableOptimizer(Graph* graph, CommonOperatorBuilder* common,
      74             :                         Zone* zone);
      75             : 
      76             :   const ZoneMap<int, InductionVariable*>& induction_variables() {
      77             :     return induction_vars_;
      78             :   }
      79             : 
      80             :   void ChangeToInductionVariablePhis();
      81             :   void ChangeToPhisAndInsertGuards();
      82             : 
      83             :  private:
      84             :   const int kAssumedLoopEntryIndex = 0;
      85             :   const int kFirstBackedge = 1;
      86             : 
      87             :   struct Constraint {
      88             :     Node* left;
      89             :     InductionVariable::ConstraintKind kind;
      90             :     Node* right;
      91             : 
      92             :     bool operator!=(const Constraint& other) const {
      93           0 :       return left != other.left || kind != other.kind || right != other.right;
      94             :     }
      95             :   };
      96             : 
      97             :   using VariableLimits = FunctionalList<Constraint>;
      98             : 
      99             :   void VisitBackedge(Node* from, Node* loop);
     100             :   void VisitNode(Node* node);
     101             :   void VisitMerge(Node* node);
     102             :   void VisitLoop(Node* node);
     103             :   void VisitIf(Node* node, bool polarity);
     104             :   void VisitStart(Node* node);
     105             :   void VisitLoopExit(Node* node);
     106             :   void VisitOtherControl(Node* node);
     107             : 
     108             :   void AddCmpToLimits(VariableLimits* limits, Node* node,
     109             :                       InductionVariable::ConstraintKind kind, bool polarity);
     110             : 
     111             :   void TakeConditionsFromFirstControl(Node* node);
     112             :   const InductionVariable* FindInductionVariable(Node* node);
     113             :   InductionVariable* TryGetInductionVariable(Node* phi);
     114             :   void DetectInductionVariables(Node* loop);
     115             : 
     116             :   Graph* graph() { return graph_; }
     117             :   CommonOperatorBuilder* common() { return common_; }
     118             :   Zone* zone() { return zone_; }
     119             : 
     120             :   Graph* graph_;
     121             :   CommonOperatorBuilder* common_;
     122             :   Zone* zone_;
     123             :   NodeAuxData<VariableLimits> limits_;
     124             :   NodeAuxData<bool> reduced_;
     125             : 
     126             :   ZoneMap<int, InductionVariable*> induction_vars_;
     127             : };
     128             : 
     129             : }  // namespace compiler
     130             : }  // namespace internal
     131             : }  // namespace v8
     132             : 
     133             : #endif  // V8_COMPILER_LOOP_VARIABLE_OPTIMIZER_H_