blob: 7c74816c26a5b3d32f554f62b207285e990de61b [file] [log] [blame]
Aart Bik30efb4e2015-07-30 12:14:31 -07001/*
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/**
Aart Bike609b7c2015-08-27 13:46:58 -070028 * 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.
Aart Bik30efb4e2015-07-30 12:14:31 -070031 *
Aart Bike609b7c2015-08-27 13:46:58 -070032 * The analysis implementation is based on the paper by M. Gerlek et al.
Aart Bik30efb4e2015-07-30 12:14:31 -070033 * "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
Aart Bik30efb4e2015-07-30 12:14:31 -070040 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 {
Aart Bik30efb4e2015-07-30 12:14:31 -070052 kInvariant,
53 kLinear,
54 kWrapAround,
Aart Bike609b7c2015-08-27 13:46:58 -070055 kPeriodic
Aart Bik30efb4e2015-07-30 12:14:31 -070056 };
57
58 enum InductionOp {
Aart Bik9401f532015-09-28 16:25:56 -070059 // No-operation: a true induction.
60 kNop,
61 // Various invariant operations.
Aart Bik30efb4e2015-07-30 12:14:31 -070062 kAdd,
63 kSub,
64 kNeg,
65 kMul,
66 kDiv,
Aart Bik9401f532015-09-28 16:25:56 -070067 kFetch,
Aart Bik22f05872015-10-27 15:56:28 -070068 // 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
Aart Bik30efb4e2015-07-30 12:14:31 -070078 };
79
80 /**
81 * Defines a detected induction as:
82 * (1) invariant:
83 * operation: a + b, a - b, -b, a * b, a / b
Aart Bike609b7c2015-08-27 13:46:58 -070084 * or:
Aart Bik30efb4e2015-07-30 12:14:31 -070085 * 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)
Aart Bik9401f532015-09-28 16:25:56 -070092 * (5) trip-count:
Aart Bik22f05872015-10-27 15:56:28 -070093 * tc: defined by a, taken-test in b
Aart Bik30efb4e2015-07-30 12:14:31 -070094 */
Vladimir Marko5233f932015-09-29 19:01:15 +010095 struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> {
Aart Bik30efb4e2015-07-30 12:14:31 -070096 InductionInfo(InductionClass ic,
97 InductionOp op,
98 InductionInfo* a,
99 InductionInfo* b,
Aart Bik0d345cf2016-03-16 10:49:38 -0700100 HInstruction* f,
101 Primitive::Type t)
Aart Bik30efb4e2015-07-30 12:14:31 -0700102 : induction_class(ic),
103 operation(op),
104 op_a(a),
105 op_b(b),
Aart Bik0d345cf2016-03-16 10:49:38 -0700106 fetch(f),
107 type(t) {}
Aart Bik30efb4e2015-07-30 12:14:31 -0700108 InductionClass induction_class;
109 InductionOp operation;
110 InductionInfo* op_a;
111 InductionInfo* op_b;
112 HInstruction* fetch;
Aart Bik0d345cf2016-03-16 10:49:38 -0700113 Primitive::Type type; // precision of induction
Aart Bik30efb4e2015-07-30 12:14:31 -0700114 };
115
Aart Bike609b7c2015-08-27 13:46:58 -0700116 bool IsVisitedNode(HInstruction* instruction) const {
117 return map_.find(instruction) != map_.end();
Aart Bik30efb4e2015-07-30 12:14:31 -0700118 }
119
Aart Bik471a2032015-09-04 18:22:11 -0700120 InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
Aart Bike609b7c2015-08-27 13:46:58 -0700121 DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr);
Aart Bik471a2032015-09-04 18:22:11 -0700122 return CreateSimplifiedInvariant(op, a, b);
Aart Bike609b7c2015-08-27 13:46:58 -0700123 }
124
Aart Bik471a2032015-09-04 18:22:11 -0700125 InductionInfo* CreateInvariantFetch(HInstruction* f) {
Aart Bike609b7c2015-08-27 13:46:58 -0700126 DCHECK(f != nullptr);
Aart Bik0d345cf2016-03-16 10:49:38 -0700127 return new (graph_->GetArena())
128 InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType());
Aart Bike609b7c2015-08-27 13:46:58 -0700129 }
130
Aart Bik0d345cf2016-03-16 10:49:38 -0700131 InductionInfo* CreateTripCount(InductionOp op,
132 InductionInfo* a,
133 InductionInfo* b,
134 Primitive::Type type) {
Aart Bik52be7e72016-06-23 11:20:41 -0700135 DCHECK(a != nullptr && b != nullptr);
Aart Bik0d345cf2016-03-16 10:49:38 -0700136 return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, type);
Aart Bik9401f532015-09-28 16:25:56 -0700137 }
138
Aart Bik0d345cf2016-03-16 10:49:38 -0700139 InductionInfo* CreateInduction(InductionClass ic,
140 InductionInfo* a,
141 InductionInfo* b,
142 Primitive::Type type) {
Aart Bike609b7c2015-08-27 13:46:58 -0700143 DCHECK(a != nullptr && b != nullptr);
Aart Bik0d345cf2016-03-16 10:49:38 -0700144 return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr, type);
Aart Bik30efb4e2015-07-30 12:14:31 -0700145 }
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);
Aart Bikf475bee2015-09-16 12:50:25 -0700153 InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
Aart Bik30efb4e2015-07-30 12:14:31 -0700154
155 // Transfer operations.
Aart Bikf475bee2015-09-16 12:50:25 -0700156 InductionInfo* TransferPhi(HLoopInformation* loop, HInstruction* phi, size_t input_index);
Aart Bik30efb4e2015-07-30 12:14:31 -0700157 InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
158 InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
Aart Bikd14c5952015-09-08 15:25:15 -0700159 InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type type);
Aart Bik30efb4e2015-07-30 12:14:31 -0700160 InductionInfo* TransferNeg(InductionInfo* a);
Aart Bik0d345cf2016-03-16 10:49:38 -0700161 InductionInfo* TransferCnv(InductionInfo* a, Primitive::Type from, Primitive::Type to);
Aart Bike609b7c2015-08-27 13:46:58 -0700162
163 // Solvers.
Aart Bikf475bee2015-09-16 12:50:25 -0700164 InductionInfo* SolvePhi(HInstruction* phi, size_t input_index);
165 InductionInfo* SolvePhiAllInputs(HLoopInformation* loop,
166 HInstruction* entry_phi,
167 HInstruction* phi);
Aart Bike609b7c2015-08-27 13:46:58 -0700168 InductionInfo* SolveAddSub(HLoopInformation* loop,
Aart Bikf475bee2015-09-16 12:50:25 -0700169 HInstruction* entry_phi,
Aart Bike609b7c2015-08-27 13:46:58 -0700170 HInstruction* instruction,
171 HInstruction* x,
172 HInstruction* y,
173 InductionOp op,
174 bool is_first_call);
Aart Bik0d345cf2016-03-16 10:49:38 -0700175 InductionInfo* SolveCnv(HTypeConversion* conversion);
Aart Bik30efb4e2015-07-30 12:14:31 -0700176
Aart Bikd14c5952015-09-08 15:25:15 -0700177 // 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,
Aart Bik9401f532015-09-28 16:25:56 -0700185 InductionInfo* lower_expr,
186 InductionInfo* upper_expr,
Aart Bikd14c5952015-09-08 15:25:15 -0700187 InductionInfo* stride,
Aart Bik9401f532015-09-28 16:25:56 -0700188 int64_t stride_value,
Aart Bikd14c5952015-09-08 15:25:15 -0700189 Primitive::Type type,
Aart Bikf475bee2015-09-16 12:50:25 -0700190 IfCondition cmp);
Aart Bik9401f532015-09-28 16:25:56 -0700191 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);
Aart Bik0d345cf2016-03-16 10:49:38 -0700196 bool FitsNarrowerControl(InductionInfo* lower_expr,
197 InductionInfo* upper_expr,
198 int64_t stride_value,
199 Primitive::Type type,
200 IfCondition cmp);
Aart Bikd14c5952015-09-08 15:25:15 -0700201
Aart Bik30efb4e2015-07-30 12:14:31 -0700202 // Assign and lookup.
Aart Bik30efb4e2015-07-30 12:14:31 -0700203 void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
204 InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
Aart Bikd14c5952015-09-08 15:25:15 -0700205 InductionInfo* CreateConstant(int64_t value, Primitive::Type type);
Aart Bik471a2032015-09-04 18:22:11 -0700206 InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
Aart Bik30efb4e2015-07-30 12:14:31 -0700207
Aart Bik7d57d7f2015-12-09 14:39:48 -0800208 // Constants.
Aart Bik97412c922016-02-19 20:14:38 -0800209 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);
Aart Bik7d57d7f2015-12-09 14:39:48 -0800212
Aart Bike609b7c2015-08-27 13:46:58 -0700213 // Helpers.
214 static bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
215 static std::string InductionToString(InductionInfo* info);
Aart Bik30efb4e2015-07-30 12:14:31 -0700216
Aart Bike609b7c2015-08-27 13:46:58 -0700217 // TODO: fine tune the following data structures, only keep relevant data.
218
219 // Temporary book-keeping during the analysis.
Aart Bik30efb4e2015-07-30 12:14:31 -0700220 uint32_t global_depth_;
Aart Bik30efb4e2015-07-30 12:14:31 -0700221 ArenaVector<HInstruction*> stack_;
222 ArenaVector<HInstruction*> scc_;
Aart Bike609b7c2015-08-27 13:46:58 -0700223 ArenaSafeMap<HInstruction*, NodeInfo> map_;
224 ArenaSafeMap<HInstruction*, InductionInfo*> cycle_;
Aart Bik0d345cf2016-03-16 10:49:38 -0700225 Primitive::Type type_;
Aart Bik30efb4e2015-07-30 12:14:31 -0700226
Aart Bike609b7c2015-08-27 13:46:58 -0700227 /**
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_;
Aart Bik30efb4e2015-07-30 12:14:31 -0700232
Aart Bike609b7c2015-08-27 13:46:58 -0700233 friend class InductionVarAnalysisTest;
Aart Bikd14c5952015-09-08 15:25:15 -0700234 friend class InductionVarRange;
235 friend class InductionVarRangeTest;
Aart Bik30efb4e2015-07-30 12:14:31 -0700236
237 DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
238};
239
240} // namespace art
241
242#endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_