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
12namespace v8 {
13namespace internal {
14namespace compiler {
15
16class CommonOperatorBuilder;
17class Graph;
18class Node;
19
20class 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  friend Zone;
45
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
70class LoopVariableOptimizer {
71 public:
72  void Run();
73
74  LoopVariableOptimizer(Graph* graph, CommonOperatorBuilder* common,
75                        Zone* zone);
76
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
117  Graph* graph() { return graph_; }
118  CommonOperatorBuilder* common() { return common_; }
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