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/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     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         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 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       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_
    134