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/zone/zone-containers.h"
       9             : 
      10             : namespace v8 {
      11             : namespace internal {
      12             : namespace compiler {
      13             : 
      14             : class CommonOperatorBuilder;
      15             : class Graph;
      16             : class Node;
      17             : 
      18             : class InductionVariable : public ZoneObject {
      19             :  public:
      20             :   Node* phi() const { return phi_; }
      21             :   Node* arith() const { return arith_; }
      22             :   Node* increment() const { return increment_; }
      23             :   Node* init_value() const { return init_value_; }
      24             : 
      25             :   enum ConstraintKind { kStrict, kNonStrict };
      26             :   enum ArithmeticType { kAddition, kSubtraction };
      27             :   struct Bound {
      28       23269 :     Bound(Node* bound, ConstraintKind kind) : bound(bound), kind(kind) {}
      29             : 
      30             :     Node* bound;
      31             :     ConstraintKind kind;
      32             :   };
      33             : 
      34             :   const ZoneVector<Bound>& lower_bounds() { return lower_bounds_; }
      35             :   const ZoneVector<Bound>& upper_bounds() { return upper_bounds_; }
      36             : 
      37             :   ArithmeticType Type() { return arithmeticType_; }
      38             : 
      39             :  private:
      40             :   friend class LoopVariableOptimizer;
      41             : 
      42             :   InductionVariable(Node* phi, Node* arith, Node* increment, Node* init_value,
      43             :                     Zone* zone, ArithmeticType arithmeticType)
      44             :       : phi_(phi),
      45             :         arith_(arith),
      46             :         increment_(increment),
      47             :         init_value_(init_value),
      48             :         lower_bounds_(zone),
      49             :         upper_bounds_(zone),
      50       57512 :         arithmeticType_(arithmeticType) {}
      51             : 
      52             :   void AddUpperBound(Node* bound, ConstraintKind kind);
      53             :   void AddLowerBound(Node* bound, ConstraintKind kind);
      54             : 
      55             :   Node* phi_;
      56             :   Node* arith_;
      57             :   Node* increment_;
      58             :   Node* init_value_;
      59             :   ZoneVector<Bound> lower_bounds_;
      60             :   ZoneVector<Bound> upper_bounds_;
      61             :   ArithmeticType arithmeticType_;
      62             : };
      63             : 
      64             : class LoopVariableOptimizer {
      65             :  public:
      66             :   void Run();
      67             : 
      68             :   LoopVariableOptimizer(Graph* graph, CommonOperatorBuilder* common,
      69             :                         Zone* zone);
      70             : 
      71             :   const ZoneMap<int, InductionVariable*>& induction_variables() {
      72             :     return induction_vars_;
      73             :   }
      74             : 
      75             :   void ChangeToInductionVariablePhis();
      76             :   void ChangeToPhisAndInsertGuards();
      77             : 
      78             :  private:
      79             :   const int kAssumedLoopEntryIndex = 0;
      80             :   const int kFirstBackedge = 1;
      81             : 
      82             :   class Constraint;
      83             :   class VariableLimits;
      84             : 
      85             :   void VisitBackedge(Node* from, Node* loop);
      86             :   void VisitNode(Node* node);
      87             :   void VisitMerge(Node* node);
      88             :   void VisitLoop(Node* node);
      89             :   void VisitIf(Node* node, bool polarity);
      90             :   void VisitStart(Node* node);
      91             :   void VisitLoopExit(Node* node);
      92             :   void VisitOtherControl(Node* node);
      93             : 
      94             :   void AddCmpToLimits(VariableLimits* limits, Node* node,
      95             :                       InductionVariable::ConstraintKind kind, bool polarity);
      96             : 
      97             :   void TakeConditionsFromFirstControl(Node* node);
      98             :   const InductionVariable* FindInductionVariable(Node* node);
      99             :   InductionVariable* TryGetInductionVariable(Node* phi);
     100             :   void DetectInductionVariables(Node* loop);
     101             : 
     102             :   Graph* graph() { return graph_; }
     103             :   CommonOperatorBuilder* common() { return common_; }
     104             :   Zone* zone() { return zone_; }
     105             : 
     106             :   Graph* graph_;
     107             :   CommonOperatorBuilder* common_;
     108             :   Zone* zone_;
     109             :   ZoneVector<const VariableLimits*> limits_;
     110             :   ZoneMap<int, InductionVariable*> induction_vars_;
     111             : };
     112             : 
     113             : }  // namespace compiler
     114             : }  // namespace internal
     115             : }  // namespace v8
     116             : 
     117             : #endif  // V8_COMPILER_LOOP_VARIABLE_OPTIMIZER_H_