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