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 InductionVariable(Node * phi,Node * effect_phi,Node * arith,Node * increment,Node * init_value,Zone * zone,ArithmeticType arithmeticType)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 induction_variables()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 graph()116 Graph* graph() { return graph_; } common()117 CommonOperatorBuilder* common() { return common_; } zone()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