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: phi()20 Node* phi() const { return phi_; } arith()21 Node* arith() const { return arith_; } increment()22 Node* increment() const { return increment_; } init_value()23 Node* init_value() const { return init_value_; } 24 25 enum ConstraintKind { kStrict, kNonStrict }; 26 enum ArithmeticType { kAddition, kSubtraction }; 27 struct Bound { BoundBound28 Bound(Node* bound, ConstraintKind kind) : bound(bound), kind(kind) {} 29 30 Node* bound; 31 ConstraintKind kind; 32 }; 33 lower_bounds()34 const ZoneVector<Bound>& lower_bounds() { return lower_bounds_; } upper_bounds()35 const ZoneVector<Bound>& upper_bounds() { return upper_bounds_; } 36 Type()37 ArithmeticType Type() { return arithmeticType_; } 38 39 private: 40 friend class LoopVariableOptimizer; 41 InductionVariable(Node * phi,Node * arith,Node * increment,Node * init_value,Zone * zone,ArithmeticType arithmeticType)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 induction_variables()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 graph()102 Graph* graph() { return graph_; } common()103 CommonOperatorBuilder* common() { return common_; } zone()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