Home | History | Annotate | Download | only in compiler 
      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     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         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_
    118