Line data Source code
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 23269 : 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 57512 : 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_
|