1/*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
18#define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
19
20#include <string>
21
22#include "nodes.h"
23#include "optimization.h"
24
25namespace art {
26
27/**
28 * Induction variable analysis. This class does not have a direct public API.
29 * Instead, the results of induction variable analysis can be queried through
30 * friend classes, such as InductionVarRange.
31 *
32 * The analysis implementation is based on the paper by M. Gerlek et al.
33 * "Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form"
34 * (ACM Transactions on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995).
35 */
36class HInductionVarAnalysis : public HOptimization {
37 public:
38  explicit HInductionVarAnalysis(HGraph* graph);
39
40  void Run() OVERRIDE;
41
42 private:
43  static constexpr const char* kInductionPassName = "induction_var_analysis";
44
45  struct NodeInfo {
46    explicit NodeInfo(uint32_t d) : depth(d), done(false) {}
47    uint32_t depth;
48    bool done;
49  };
50
51  enum InductionClass {
52    kInvariant,
53    kLinear,
54    kWrapAround,
55    kPeriodic
56  };
57
58  enum InductionOp {
59    // No-operation: a true induction.
60    kNop,
61    // Various invariant operations.
62    kAdd,
63    kSub,
64    kNeg,
65    kMul,
66    kDiv,
67    kFetch,
68    // Trip-counts.
69    kTripCountInLoop,        // valid in full loop; loop is finite
70    kTripCountInBody,        // valid in body only; loop is finite
71    kTripCountInLoopUnsafe,  // valid in full loop; loop may be infinite
72    kTripCountInBodyUnsafe,  // valid in body only; loop may be infinite
73    // Comparisons for trip-count tests.
74    kLT,
75    kLE,
76    kGT,
77    kGE
78  };
79
80  /**
81   * Defines a detected induction as:
82   *   (1) invariant:
83   *         operation: a + b, a - b, -b, a * b, a / b
84   *       or:
85   *         fetch: fetch from HIR
86   *   (2) linear:
87   *         nop: a * i + b
88   *   (3) wrap-around
89   *         nop: a, then defined by b
90   *   (4) periodic
91   *         nop: a, then defined by b (repeated when exhausted)
92   *   (5) trip-count:
93   *         tc: defined by a, taken-test in b
94   */
95  struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> {
96    InductionInfo(InductionClass ic,
97                  InductionOp op,
98                  InductionInfo* a,
99                  InductionInfo* b,
100                  HInstruction* f,
101                  Primitive::Type t)
102        : induction_class(ic),
103          operation(op),
104          op_a(a),
105          op_b(b),
106          fetch(f),
107          type(t) {}
108    InductionClass induction_class;
109    InductionOp operation;
110    InductionInfo* op_a;
111    InductionInfo* op_b;
112    HInstruction* fetch;
113    Primitive::Type type;  // precision of induction
114  };
115
116  bool IsVisitedNode(HInstruction* instruction) const {
117    return map_.find(instruction) != map_.end();
118  }
119
120  InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
121    DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr);
122    return CreateSimplifiedInvariant(op, a, b);
123  }
124
125  InductionInfo* CreateInvariantFetch(HInstruction* f) {
126    DCHECK(f != nullptr);
127    return new (graph_->GetArena())
128        InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType());
129  }
130
131  InductionInfo* CreateTripCount(InductionOp op,
132                                 InductionInfo* a,
133                                 InductionInfo* b,
134                                 Primitive::Type type) {
135    DCHECK(a != nullptr);
136    return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, type);
137  }
138
139  InductionInfo* CreateInduction(InductionClass ic,
140                                 InductionInfo* a,
141                                 InductionInfo* b,
142                                 Primitive::Type type) {
143    DCHECK(a != nullptr && b != nullptr);
144    return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr, type);
145  }
146
147  // Methods for analysis.
148  void VisitLoop(HLoopInformation* loop);
149  void VisitNode(HLoopInformation* loop, HInstruction* instruction);
150  uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction);
151  void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
152  void ClassifyNonTrivial(HLoopInformation* loop);
153  InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
154
155  // Transfer operations.
156  InductionInfo* TransferPhi(HLoopInformation* loop, HInstruction* phi, size_t input_index);
157  InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
158  InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
159  InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type type);
160  InductionInfo* TransferNeg(InductionInfo* a);
161  InductionInfo* TransferCnv(InductionInfo* a, Primitive::Type from, Primitive::Type to);
162
163  // Solvers.
164  InductionInfo* SolvePhi(HInstruction* phi, size_t input_index);
165  InductionInfo* SolvePhiAllInputs(HLoopInformation* loop,
166                                   HInstruction* entry_phi,
167                                   HInstruction* phi);
168  InductionInfo* SolveAddSub(HLoopInformation* loop,
169                             HInstruction* entry_phi,
170                             HInstruction* instruction,
171                             HInstruction* x,
172                             HInstruction* y,
173                             InductionOp op,
174                             bool is_first_call);
175  InductionInfo* SolveCnv(HTypeConversion* conversion);
176
177  // Trip count information.
178  void VisitControl(HLoopInformation* loop);
179  void VisitCondition(HLoopInformation* loop,
180                      InductionInfo* a,
181                      InductionInfo* b,
182                      Primitive::Type type,
183                      IfCondition cmp);
184  void VisitTripCount(HLoopInformation* loop,
185                      InductionInfo* lower_expr,
186                      InductionInfo* upper_expr,
187                      InductionInfo* stride,
188                      int64_t stride_value,
189                      Primitive::Type type,
190                      IfCondition cmp);
191  bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp);
192  bool IsFinite(InductionInfo* upper_expr,
193                int64_t stride_value,
194                Primitive::Type type,
195                IfCondition cmp);
196  bool FitsNarrowerControl(InductionInfo* lower_expr,
197                           InductionInfo* upper_expr,
198                           int64_t stride_value,
199                           Primitive::Type type,
200                           IfCondition cmp);
201
202  // Assign and lookup.
203  void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
204  InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
205  InductionInfo* CreateConstant(int64_t value, Primitive::Type type);
206  InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
207
208  // Constants.
209  bool IsExact(InductionInfo* info, /*out*/ int64_t* value);
210  bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value);
211  bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value);
212
213  // Helpers.
214  static bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
215  static std::string InductionToString(InductionInfo* info);
216
217  // TODO: fine tune the following data structures, only keep relevant data.
218
219  // Temporary book-keeping during the analysis.
220  uint32_t global_depth_;
221  ArenaVector<HInstruction*> stack_;
222  ArenaVector<HInstruction*> scc_;
223  ArenaSafeMap<HInstruction*, NodeInfo> map_;
224  ArenaSafeMap<HInstruction*, InductionInfo*> cycle_;
225  Primitive::Type type_;
226
227  /**
228   * Maintains the results of the analysis as a mapping from loops to a mapping from instructions
229   * to the induction information for that instruction in that loop.
230   */
231  ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
232
233  friend class InductionVarAnalysisTest;
234  friend class InductionVarRange;
235  friend class InductionVarRangeTest;
236
237  DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
238};
239
240}  // namespace art
241
242#endif  // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
243