blob: 72c2064d894296c5419e6a678dd88039e4416a87 [file] [log] [blame]
Aart Bikd14c5952015-09-08 15:25:15 -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
Aart Bikd14c5952015-09-08 15:25:15 -070017#include "induction_var_range.h"
18
Aart Bikcd26feb2015-09-23 17:50:50 -070019#include <limits>
20
Vladimir Marko0a516052019-10-14 13:00:44 +000021namespace art {
Aart Bikd14c5952015-09-08 15:25:15 -070022
Aart Bikb3365e02015-09-21 14:45:05 -070023/** Returns true if 64-bit constant fits in 32-bit constant. */
24static bool CanLongValueFitIntoInt(int64_t c) {
Aart Bikcd26feb2015-09-23 17:50:50 -070025 return std::numeric_limits<int32_t>::min() <= c && c <= std::numeric_limits<int32_t>::max();
Aart Bikd14c5952015-09-08 15:25:15 -070026}
27
Aart Bikb3365e02015-09-21 14:45:05 -070028/** Returns true if 32-bit addition can be done safely. */
Aart Bikd14c5952015-09-08 15:25:15 -070029static bool IsSafeAdd(int32_t c1, int32_t c2) {
Aart Bikb3365e02015-09-21 14:45:05 -070030 return CanLongValueFitIntoInt(static_cast<int64_t>(c1) + static_cast<int64_t>(c2));
Aart Bikd14c5952015-09-08 15:25:15 -070031}
32
Aart Bikb3365e02015-09-21 14:45:05 -070033/** Returns true if 32-bit subtraction can be done safely. */
Aart Bikd14c5952015-09-08 15:25:15 -070034static bool IsSafeSub(int32_t c1, int32_t c2) {
Aart Bikb3365e02015-09-21 14:45:05 -070035 return CanLongValueFitIntoInt(static_cast<int64_t>(c1) - static_cast<int64_t>(c2));
Aart Bikd14c5952015-09-08 15:25:15 -070036}
37
Aart Bikb3365e02015-09-21 14:45:05 -070038/** Returns true if 32-bit multiplication can be done safely. */
Aart Bikd14c5952015-09-08 15:25:15 -070039static bool IsSafeMul(int32_t c1, int32_t c2) {
Aart Bikb3365e02015-09-21 14:45:05 -070040 return CanLongValueFitIntoInt(static_cast<int64_t>(c1) * static_cast<int64_t>(c2));
Aart Bikd14c5952015-09-08 15:25:15 -070041}
42
Aart Bikb3365e02015-09-21 14:45:05 -070043/** Returns true if 32-bit division can be done safely. */
Aart Bikd14c5952015-09-08 15:25:15 -070044static bool IsSafeDiv(int32_t c1, int32_t c2) {
Aart Bikb3365e02015-09-21 14:45:05 -070045 return c2 != 0 && CanLongValueFitIntoInt(static_cast<int64_t>(c1) / static_cast<int64_t>(c2));
Aart Bikd14c5952015-09-08 15:25:15 -070046}
47
Aart Bikb603a5c2017-03-06 18:29:39 -080048/** Computes a * b for a,b > 0 (at least until first overflow happens). */
49static int64_t SafeMul(int64_t a, int64_t b, /*out*/ bool* overflow) {
50 if (a > 0 && b > 0 && a > (std::numeric_limits<int64_t>::max() / b)) {
51 *overflow = true;
52 }
53 return a * b;
54}
55
56/** Returns b^e for b,e > 0. Sets overflow if arithmetic wrap-around occurred. */
Aart Bikd3ba6262017-01-30 14:37:12 -080057static int64_t IntPow(int64_t b, int64_t e, /*out*/ bool* overflow) {
Aart Bikb603a5c2017-03-06 18:29:39 -080058 DCHECK_LT(0, b);
59 DCHECK_LT(0, e);
Aart Bikc071a012016-12-01 10:22:31 -080060 int64_t pow = 1;
61 while (e) {
62 if (e & 1) {
Aart Bikb603a5c2017-03-06 18:29:39 -080063 pow = SafeMul(pow, b, overflow);
Aart Bikc071a012016-12-01 10:22:31 -080064 }
65 e >>= 1;
Aart Bikb603a5c2017-03-06 18:29:39 -080066 if (e) {
67 b = SafeMul(b, b, overflow);
68 }
Aart Bikc071a012016-12-01 10:22:31 -080069 }
70 return pow;
71}
72
Aart Bik40fbf742016-10-31 11:02:50 -070073/** Hunts "under the hood" for a suitable instruction at the hint. */
74static bool IsMaxAtHint(
75 HInstruction* instruction, HInstruction* hint, /*out*/HInstruction** suitable) {
Aart Bik1f8d51b2018-02-15 10:42:37 -080076 if (instruction->IsMin()) {
77 // For MIN(x, y), return most suitable x or y as maximum.
78 return IsMaxAtHint(instruction->InputAt(0), hint, suitable) ||
79 IsMaxAtHint(instruction->InputAt(1), hint, suitable);
Aart Bik40fbf742016-10-31 11:02:50 -070080 } else {
81 *suitable = instruction;
Nicolas Geoffraye761bcc2017-01-19 08:59:37 +000082 return HuntForDeclaration(instruction) == hint;
Aart Bik40fbf742016-10-31 11:02:50 -070083 }
Aart Bik40fbf742016-10-31 11:02:50 -070084}
85
86/** Post-analysis simplification of a minimum value that makes the bound more useful to clients. */
87static InductionVarRange::Value SimplifyMin(InductionVarRange::Value v) {
88 if (v.is_known && v.a_constant == 1 && v.b_constant <= 0) {
89 // If a == 1, instruction >= 0 and b <= 0, just return the constant b.
90 // No arithmetic wrap-around can occur.
91 if (IsGEZero(v.instruction)) {
92 return InductionVarRange::Value(v.b_constant);
93 }
Aart Bikb3365e02015-09-21 14:45:05 -070094 }
95 return v;
96}
97
Aart Bik40fbf742016-10-31 11:02:50 -070098/** Post-analysis simplification of a maximum value that makes the bound more useful to clients. */
99static InductionVarRange::Value SimplifyMax(InductionVarRange::Value v, HInstruction* hint) {
100 if (v.is_known && v.a_constant >= 1) {
101 // An upper bound a * (length / a) + b, where a >= 1, can be conservatively rewritten as
102 // length + b because length >= 0 is true.
103 int64_t value;
104 if (v.instruction->IsDiv() &&
105 v.instruction->InputAt(0)->IsArrayLength() &&
Aart Bikf3e61ee2017-04-12 17:09:20 -0700106 IsInt64AndGet(v.instruction->InputAt(1), &value) && v.a_constant == value) {
Aart Bik40fbf742016-10-31 11:02:50 -0700107 return InductionVarRange::Value(v.instruction->InputAt(0), 1, v.b_constant);
108 }
109 // If a == 1, the most suitable one suffices as maximum value.
110 HInstruction* suitable = nullptr;
111 if (v.a_constant == 1 && IsMaxAtHint(v.instruction, hint, &suitable)) {
112 return InductionVarRange::Value(suitable, 1, v.b_constant);
113 }
114 }
115 return v;
116}
117
118/** Tests for a constant value. */
Aart Bik52be7e72016-06-23 11:20:41 -0700119static bool IsConstantValue(InductionVarRange::Value v) {
120 return v.is_known && v.a_constant == 0;
121}
122
123/** Corrects a value for type to account for arithmetic wrap-around in lower precision. */
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100124static InductionVarRange::Value CorrectForType(InductionVarRange::Value v, DataType::Type type) {
Aart Bik0d345cf2016-03-16 10:49:38 -0700125 switch (type) {
Vladimir Markod5d2f2c2017-09-26 12:37:26 +0100126 case DataType::Type::kUint8:
127 case DataType::Type::kInt8:
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100128 case DataType::Type::kUint16:
Vladimir Markod5d2f2c2017-09-26 12:37:26 +0100129 case DataType::Type::kInt16: {
Aart Bik0d345cf2016-03-16 10:49:38 -0700130 // Constants within range only.
131 // TODO: maybe some room for improvement, like allowing widening conversions
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100132 int32_t min = DataType::MinValueOfIntegralType(type);
133 int32_t max = DataType::MaxValueOfIntegralType(type);
Aart Bik52be7e72016-06-23 11:20:41 -0700134 return (IsConstantValue(v) && min <= v.b_constant && v.b_constant <= max)
Aart Bik0d345cf2016-03-16 10:49:38 -0700135 ? v
136 : InductionVarRange::Value();
137 }
138 default:
Aart Bik0d345cf2016-03-16 10:49:38 -0700139 return v;
140 }
141}
142
Aart Bik40fbf742016-10-31 11:02:50 -0700143/** Inserts an instruction. */
Aart Bik389b3db2015-10-28 14:23:40 -0700144static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) {
145 DCHECK(block != nullptr);
146 DCHECK(block->GetLastInstruction() != nullptr) << block->GetBlockId();
Aart Bikaec3cce2015-10-14 17:44:55 -0700147 DCHECK(instruction != nullptr);
Aart Bik389b3db2015-10-28 14:23:40 -0700148 block->InsertInstructionBefore(instruction, block->GetLastInstruction());
Aart Bikaec3cce2015-10-14 17:44:55 -0700149 return instruction;
150}
151
Aart Bik40fbf742016-10-31 11:02:50 -0700152/** Obtains loop's control instruction. */
Aart Bik009cace2016-09-16 10:15:19 -0700153static HInstruction* GetLoopControl(HLoopInformation* loop) {
154 DCHECK(loop != nullptr);
155 return loop->GetHeader()->GetLastInstruction();
156}
157
Aart Bikd14c5952015-09-08 15:25:15 -0700158//
159// Public class methods.
160//
161
162InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis)
Aart Bik52be7e72016-06-23 11:20:41 -0700163 : induction_analysis_(induction_analysis),
164 chase_hint_(nullptr) {
Aart Bikb3365e02015-09-21 14:45:05 -0700165 DCHECK(induction_analysis != nullptr);
Aart Bikd14c5952015-09-08 15:25:15 -0700166}
167
Aart Bik1fc3afb2016-02-02 13:26:16 -0800168bool InductionVarRange::GetInductionRange(HInstruction* context,
Aart Bik389b3db2015-10-28 14:23:40 -0700169 HInstruction* instruction,
Aart Bik52be7e72016-06-23 11:20:41 -0700170 HInstruction* chase_hint,
Aart Bik389b3db2015-10-28 14:23:40 -0700171 /*out*/Value* min_val,
172 /*out*/Value* max_val,
173 /*out*/bool* needs_finite_test) {
Aart Bik52be7e72016-06-23 11:20:41 -0700174 HLoopInformation* loop = nullptr;
175 HInductionVarAnalysis::InductionInfo* info = nullptr;
176 HInductionVarAnalysis::InductionInfo* trip = nullptr;
177 if (!HasInductionInfo(context, instruction, &loop, &info, &trip)) {
178 return false;
Aart Bik97412c922016-02-19 20:14:38 -0800179 }
Aart Bik0d345cf2016-03-16 10:49:38 -0700180 // Type int or lower (this is not too restrictive since intended clients, like
181 // bounds check elimination, will have truncated higher precision induction
182 // at their use point already).
183 switch (info->type) {
Vladimir Markod5d2f2c2017-09-26 12:37:26 +0100184 case DataType::Type::kUint8:
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100185 case DataType::Type::kInt8:
Vladimir Markod5d2f2c2017-09-26 12:37:26 +0100186 case DataType::Type::kUint16:
187 case DataType::Type::kInt16:
188 case DataType::Type::kInt32:
Aart Bik0d345cf2016-03-16 10:49:38 -0700189 break;
190 default:
191 return false;
192 }
Aart Bik97412c922016-02-19 20:14:38 -0800193 // Find range.
Aart Bik52be7e72016-06-23 11:20:41 -0700194 chase_hint_ = chase_hint;
195 bool in_body = context->GetBlock() != loop->GetHeader();
Aart Bik16d3a652016-09-09 10:33:50 -0700196 int64_t stride_value = 0;
Andreas Gampe3db70682018-12-26 15:12:03 -0800197 *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min= */ true));
198 *max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min= */ false), chase_hint);
Aart Bik16d3a652016-09-09 10:33:50 -0700199 *needs_finite_test = NeedsTripCount(info, &stride_value) && IsUnsafeTripCount(trip);
Aart Bik40fbf742016-10-31 11:02:50 -0700200 chase_hint_ = nullptr;
201 // Retry chasing constants for wrap-around (merge sensitive).
202 if (!min_val->is_known && info->induction_class == HInductionVarAnalysis::kWrapAround) {
Andreas Gampe3db70682018-12-26 15:12:03 -0800203 *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min= */ true));
Aart Bik40fbf742016-10-31 11:02:50 -0700204 }
Aart Bik97412c922016-02-19 20:14:38 -0800205 return true;
Aart Bikd14c5952015-09-08 15:25:15 -0700206}
207
Aart Bik16d3a652016-09-09 10:33:50 -0700208bool InductionVarRange::CanGenerateRange(HInstruction* context,
209 HInstruction* instruction,
210 /*out*/bool* needs_finite_test,
211 /*out*/bool* needs_taken_test) {
212 bool is_last_value = false;
213 int64_t stride_value = 0;
Aart Bik9abf8942016-10-14 09:49:42 -0700214 return GenerateRangeOrLastValue(context,
215 instruction,
216 is_last_value,
217 nullptr,
218 nullptr,
219 nullptr,
220 nullptr,
221 nullptr, // nothing generated yet
222 &stride_value,
223 needs_finite_test,
224 needs_taken_test)
Aart Bik16d3a652016-09-09 10:33:50 -0700225 && (stride_value == -1 ||
226 stride_value == 0 ||
Aart Bik40fbf742016-10-31 11:02:50 -0700227 stride_value == 1); // avoid arithmetic wrap-around anomalies.
Aart Bikaec3cce2015-10-14 17:44:55 -0700228}
229
Aart Bik16d3a652016-09-09 10:33:50 -0700230void InductionVarRange::GenerateRange(HInstruction* context,
231 HInstruction* instruction,
232 HGraph* graph,
233 HBasicBlock* block,
234 /*out*/HInstruction** lower,
235 /*out*/HInstruction** upper) {
236 bool is_last_value = false;
Aart Bik009cace2016-09-16 10:15:19 -0700237 int64_t stride_value = 0;
Aart Bik389b3db2015-10-28 14:23:40 -0700238 bool b1, b2; // unused
Aart Bik9abf8942016-10-14 09:49:42 -0700239 if (!GenerateRangeOrLastValue(context,
240 instruction,
241 is_last_value,
242 graph,
243 block,
244 lower,
245 upper,
246 nullptr,
247 &stride_value,
248 &b1,
249 &b2)) {
Aart Bik16d3a652016-09-09 10:33:50 -0700250 LOG(FATAL) << "Failed precondition: CanGenerateRange()";
Aart Bik389b3db2015-10-28 14:23:40 -0700251 }
252}
253
Aart Bik16d3a652016-09-09 10:33:50 -0700254HInstruction* InductionVarRange::GenerateTakenTest(HInstruction* context,
255 HGraph* graph,
256 HBasicBlock* block) {
257 HInstruction* taken_test = nullptr;
258 bool is_last_value = false;
259 int64_t stride_value = 0;
Aart Bik389b3db2015-10-28 14:23:40 -0700260 bool b1, b2; // unused
Aart Bik9abf8942016-10-14 09:49:42 -0700261 if (!GenerateRangeOrLastValue(context,
262 context,
263 is_last_value,
264 graph,
265 block,
266 nullptr,
267 nullptr,
268 &taken_test,
269 &stride_value,
270 &b1,
271 &b2)) {
Aart Bik16d3a652016-09-09 10:33:50 -0700272 LOG(FATAL) << "Failed precondition: CanGenerateRange()";
273 }
274 return taken_test;
275}
276
277bool InductionVarRange::CanGenerateLastValue(HInstruction* instruction) {
278 bool is_last_value = true;
279 int64_t stride_value = 0;
280 bool needs_finite_test = false;
281 bool needs_taken_test = false;
Aart Bik9abf8942016-10-14 09:49:42 -0700282 return GenerateRangeOrLastValue(instruction,
283 instruction,
284 is_last_value,
285 nullptr,
286 nullptr,
287 nullptr,
288 nullptr,
289 nullptr, // nothing generated yet
290 &stride_value,
291 &needs_finite_test,
292 &needs_taken_test)
Aart Bik16d3a652016-09-09 10:33:50 -0700293 && !needs_finite_test && !needs_taken_test;
294}
295
296HInstruction* InductionVarRange::GenerateLastValue(HInstruction* instruction,
297 HGraph* graph,
298 HBasicBlock* block) {
299 HInstruction* last_value = nullptr;
300 bool is_last_value = true;
301 int64_t stride_value = 0;
302 bool b1, b2; // unused
Aart Bik9abf8942016-10-14 09:49:42 -0700303 if (!GenerateRangeOrLastValue(instruction,
304 instruction,
305 is_last_value,
306 graph,
307 block,
308 &last_value,
309 &last_value,
310 nullptr,
311 &stride_value,
312 &b1,
313 &b2)) {
Aart Bik16d3a652016-09-09 10:33:50 -0700314 LOG(FATAL) << "Failed precondition: CanGenerateLastValue()";
315 }
316 return last_value;
317}
318
319void InductionVarRange::Replace(HInstruction* instruction,
320 HInstruction* fetch,
321 HInstruction* replacement) {
322 for (HLoopInformation* lp = instruction->GetBlock()->GetLoopInformation(); // closest enveloping loop
323 lp != nullptr;
324 lp = lp->GetPreHeader()->GetLoopInformation()) {
Aart Bik009cace2016-09-16 10:15:19 -0700325 // Update instruction's information.
Aart Bik16d3a652016-09-09 10:33:50 -0700326 ReplaceInduction(induction_analysis_->LookupInfo(lp, instruction), fetch, replacement);
Aart Bik009cace2016-09-16 10:15:19 -0700327 // Update loop's trip-count information.
328 ReplaceInduction(induction_analysis_->LookupInfo(lp, GetLoopControl(lp)), fetch, replacement);
Aart Bik389b3db2015-10-28 14:23:40 -0700329 }
Aart Bikaec3cce2015-10-14 17:44:55 -0700330}
331
Aart Bik1f8d51b2018-02-15 10:42:37 -0800332bool InductionVarRange::IsFinite(HLoopInformation* loop, /*out*/ int64_t* trip_count) const {
Artem Serov121f2032017-10-23 19:19:06 +0100333 bool is_constant_unused = false;
334 return CheckForFiniteAndConstantProps(loop, &is_constant_unused, trip_count);
335}
336
337bool InductionVarRange::HasKnownTripCount(HLoopInformation* loop,
338 /*out*/ int64_t* trip_count) const {
339 bool is_constant = false;
340 CheckForFiniteAndConstantProps(loop, &is_constant, trip_count);
341 return is_constant;
Aart Bik9abf8942016-10-14 09:49:42 -0700342}
343
Aart Bikfa762962017-04-07 11:33:37 -0700344bool InductionVarRange::IsUnitStride(HInstruction* context,
345 HInstruction* instruction,
Aart Bik37dc4df2017-06-28 14:08:00 -0700346 HGraph* graph,
Aart Bik8e02e3e2017-02-28 14:41:55 -0800347 /*out*/ HInstruction** offset) const {
348 HLoopInformation* loop = nullptr;
349 HInductionVarAnalysis::InductionInfo* info = nullptr;
350 HInductionVarAnalysis::InductionInfo* trip = nullptr;
Aart Bikfa762962017-04-07 11:33:37 -0700351 if (HasInductionInfo(context, instruction, &loop, &info, &trip)) {
Aart Bik8e02e3e2017-02-28 14:41:55 -0800352 if (info->induction_class == HInductionVarAnalysis::kLinear &&
Aart Bik7adb6882017-03-07 13:28:51 -0800353 !HInductionVarAnalysis::IsNarrowingLinear(info)) {
Aart Bik8e02e3e2017-02-28 14:41:55 -0800354 int64_t stride_value = 0;
355 if (IsConstant(info->op_a, kExact, &stride_value) && stride_value == 1) {
356 int64_t off_value = 0;
Aart Bik37dc4df2017-06-28 14:08:00 -0700357 if (IsConstant(info->op_b, kExact, &off_value)) {
358 *offset = graph->GetConstant(info->op_b->type, off_value);
359 } else if (info->op_b->operation == HInductionVarAnalysis::kFetch) {
Aart Bik8e02e3e2017-02-28 14:41:55 -0800360 *offset = info->op_b->fetch;
Aart Bik37dc4df2017-06-28 14:08:00 -0700361 } else {
362 return false;
Aart Bik8e02e3e2017-02-28 14:41:55 -0800363 }
364 return true;
365 }
366 }
367 }
368 return false;
369}
370
371HInstruction* InductionVarRange::GenerateTripCount(HLoopInformation* loop,
372 HGraph* graph,
373 HBasicBlock* block) {
374 HInductionVarAnalysis::InductionInfo *trip =
375 induction_analysis_->LookupInfo(loop, GetLoopControl(loop));
376 if (trip != nullptr && !IsUnsafeTripCount(trip)) {
377 HInstruction* taken_test = nullptr;
378 HInstruction* trip_expr = nullptr;
379 if (IsBodyTripCount(trip)) {
380 if (!GenerateCode(trip->op_b, nullptr, graph, block, &taken_test, false, false)) {
381 return nullptr;
382 }
383 }
384 if (GenerateCode(trip->op_a, nullptr, graph, block, &trip_expr, false, false)) {
385 if (taken_test != nullptr) {
386 HInstruction* zero = graph->GetConstant(trip->type, 0);
Vladimir Markoca6fff82017-10-03 14:49:14 +0100387 ArenaAllocator* allocator = graph->GetAllocator();
388 trip_expr = Insert(block, new (allocator) HSelect(taken_test, trip_expr, zero, kNoDexPc));
Aart Bik8e02e3e2017-02-28 14:41:55 -0800389 }
390 return trip_expr;
391 }
392 }
393 return nullptr;
394}
395
Aart Bikd14c5952015-09-08 15:25:15 -0700396//
397// Private class methods.
398//
399
Artem Serov121f2032017-10-23 19:19:06 +0100400bool InductionVarRange::CheckForFiniteAndConstantProps(HLoopInformation* loop,
401 /*out*/ bool* is_constant,
402 /*out*/ int64_t* trip_count) const {
403 HInductionVarAnalysis::InductionInfo *trip =
404 induction_analysis_->LookupInfo(loop, GetLoopControl(loop));
405 if (trip != nullptr && !IsUnsafeTripCount(trip)) {
406 *is_constant = IsConstant(trip->op_a, kExact, trip_count);
407 return true;
408 }
409 return false;
410}
411
Aart Bik97412c922016-02-19 20:14:38 -0800412bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info,
413 ConstantRequest request,
Aart Bik52be7e72016-06-23 11:20:41 -0700414 /*out*/ int64_t* value) const {
Aart Bik97412c922016-02-19 20:14:38 -0800415 if (info != nullptr) {
416 // A direct 32-bit or 64-bit constant fetch. This immediately satisfies
417 // any of the three requests (kExact, kAtMost, and KAtLeast).
418 if (info->induction_class == HInductionVarAnalysis::kInvariant &&
419 info->operation == HInductionVarAnalysis::kFetch) {
Aart Bikf3e61ee2017-04-12 17:09:20 -0700420 if (IsInt64AndGet(info->fetch, value)) {
Aart Bik97412c922016-02-19 20:14:38 -0800421 return true;
422 }
423 }
Aart Bik40fbf742016-10-31 11:02:50 -0700424 // Try range analysis on the invariant, only accept a proper range
425 // to avoid arithmetic wrap-around anomalies.
Andreas Gampe3db70682018-12-26 15:12:03 -0800426 Value min_val = GetVal(info, nullptr, /* in_body= */ true, /* is_min= */ true);
427 Value max_val = GetVal(info, nullptr, /* in_body= */ true, /* is_min= */ false);
Aart Bik52be7e72016-06-23 11:20:41 -0700428 if (IsConstantValue(min_val) &&
429 IsConstantValue(max_val) && min_val.b_constant <= max_val.b_constant) {
430 if ((request == kExact && min_val.b_constant == max_val.b_constant) || request == kAtMost) {
431 *value = max_val.b_constant;
432 return true;
433 } else if (request == kAtLeast) {
434 *value = min_val.b_constant;
Aart Bik358af832016-02-24 14:17:53 -0800435 return true;
436 }
437 }
Aart Bik97412c922016-02-19 20:14:38 -0800438 }
439 return false;
440}
441
Aart Bik52be7e72016-06-23 11:20:41 -0700442bool InductionVarRange::HasInductionInfo(
443 HInstruction* context,
444 HInstruction* instruction,
445 /*out*/ HLoopInformation** loop,
446 /*out*/ HInductionVarAnalysis::InductionInfo** info,
447 /*out*/ HInductionVarAnalysis::InductionInfo** trip) const {
Aart Bikc071a012016-12-01 10:22:31 -0800448 DCHECK(context != nullptr);
449 DCHECK(context->GetBlock() != nullptr);
Aart Bik009cace2016-09-16 10:15:19 -0700450 HLoopInformation* lp = context->GetBlock()->GetLoopInformation(); // closest enveloping loop
451 if (lp != nullptr) {
452 HInductionVarAnalysis::InductionInfo* i = induction_analysis_->LookupInfo(lp, instruction);
Aart Bik52be7e72016-06-23 11:20:41 -0700453 if (i != nullptr) {
Aart Bik009cace2016-09-16 10:15:19 -0700454 *loop = lp;
Aart Bik52be7e72016-06-23 11:20:41 -0700455 *info = i;
Aart Bik009cace2016-09-16 10:15:19 -0700456 *trip = induction_analysis_->LookupInfo(lp, GetLoopControl(lp));
Aart Bik52be7e72016-06-23 11:20:41 -0700457 return true;
458 }
459 }
460 return false;
461}
462
463bool InductionVarRange::IsWellBehavedTripCount(HInductionVarAnalysis::InductionInfo* trip) const {
464 if (trip != nullptr) {
465 // Both bounds that define a trip-count are well-behaved if they either are not defined
466 // in any loop, or are contained in a proper interval. This allows finding the min/max
467 // of an expression by chasing outward.
468 InductionVarRange range(induction_analysis_);
469 HInductionVarAnalysis::InductionInfo* lower = trip->op_b->op_a;
470 HInductionVarAnalysis::InductionInfo* upper = trip->op_b->op_b;
471 int64_t not_used = 0;
472 return (!HasFetchInLoop(lower) || range.IsConstant(lower, kAtLeast, &not_used)) &&
473 (!HasFetchInLoop(upper) || range.IsConstant(upper, kAtLeast, &not_used));
474 }
475 return true;
476}
477
478bool InductionVarRange::HasFetchInLoop(HInductionVarAnalysis::InductionInfo* info) const {
479 if (info != nullptr) {
480 if (info->induction_class == HInductionVarAnalysis::kInvariant &&
481 info->operation == HInductionVarAnalysis::kFetch) {
482 return info->fetch->GetBlock()->GetLoopInformation() != nullptr;
483 }
484 return HasFetchInLoop(info->op_a) || HasFetchInLoop(info->op_b);
485 }
486 return false;
487}
488
Aart Bik16d3a652016-09-09 10:33:50 -0700489bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info,
490 int64_t* stride_value) const {
Aart Bik389b3db2015-10-28 14:23:40 -0700491 if (info != nullptr) {
492 if (info->induction_class == HInductionVarAnalysis::kLinear) {
Aart Bik16d3a652016-09-09 10:33:50 -0700493 return IsConstant(info->op_a, kExact, stride_value);
Aart Bikdf7822e2016-12-06 10:05:30 -0800494 } else if (info->induction_class == HInductionVarAnalysis::kPolynomial) {
495 return NeedsTripCount(info->op_a, stride_value);
Aart Bik389b3db2015-10-28 14:23:40 -0700496 } else if (info->induction_class == HInductionVarAnalysis::kWrapAround) {
Aart Bik16d3a652016-09-09 10:33:50 -0700497 return NeedsTripCount(info->op_b, stride_value);
Aart Bik389b3db2015-10-28 14:23:40 -0700498 }
Aart Bikd14c5952015-09-08 15:25:15 -0700499 }
Aart Bik389b3db2015-10-28 14:23:40 -0700500 return false;
501}
502
Aart Bik7d57d7f2015-12-09 14:39:48 -0800503bool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const {
Aart Bik389b3db2015-10-28 14:23:40 -0700504 if (trip != nullptr) {
505 if (trip->induction_class == HInductionVarAnalysis::kInvariant) {
506 return trip->operation == HInductionVarAnalysis::kTripCountInBody ||
507 trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe;
508 }
509 }
510 return false;
511}
512
Aart Bik7d57d7f2015-12-09 14:39:48 -0800513bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const {
Aart Bik389b3db2015-10-28 14:23:40 -0700514 if (trip != nullptr) {
515 if (trip->induction_class == HInductionVarAnalysis::kInvariant) {
516 return trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe ||
517 trip->operation == HInductionVarAnalysis::kTripCountInLoopUnsafe;
518 }
519 }
520 return false;
Aart Bikd14c5952015-09-08 15:25:15 -0700521}
522
Aart Bik7d57d7f2015-12-09 14:39:48 -0800523InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::InductionInfo* info,
524 HInductionVarAnalysis::InductionInfo* trip,
525 bool in_body,
526 bool is_min) const {
Aart Bikc071a012016-12-01 10:22:31 -0800527 DCHECK(info != nullptr);
Aart Bikdf7822e2016-12-06 10:05:30 -0800528 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kLinear);
Aart Bik52be7e72016-06-23 11:20:41 -0700529 // Detect common situation where an offset inside the trip-count cancels out during range
Aart Bik7d57d7f2015-12-09 14:39:48 -0800530 // analysis (finding max a * (TC - 1) + OFFSET for a == 1 and TC = UPPER - OFFSET or finding
531 // min a * (TC - 1) + OFFSET for a == -1 and TC = OFFSET - UPPER) to avoid losing information
532 // with intermediate results that only incorporate single instructions.
533 if (trip != nullptr) {
534 HInductionVarAnalysis::InductionInfo* trip_expr = trip->op_a;
Aart Bik52be7e72016-06-23 11:20:41 -0700535 if (trip_expr->type == info->type && trip_expr->operation == HInductionVarAnalysis::kSub) {
Aart Bik97412c922016-02-19 20:14:38 -0800536 int64_t stride_value = 0;
537 if (IsConstant(info->op_a, kExact, &stride_value)) {
Aart Bik7d57d7f2015-12-09 14:39:48 -0800538 if (!is_min && stride_value == 1) {
Aart Bik97412c922016-02-19 20:14:38 -0800539 // Test original trip's negative operand (trip_expr->op_b) against offset of induction.
Aart Bik7d57d7f2015-12-09 14:39:48 -0800540 if (HInductionVarAnalysis::InductionEqual(trip_expr->op_b, info->op_b)) {
541 // Analyze cancelled trip with just the positive operand (trip_expr->op_a).
542 HInductionVarAnalysis::InductionInfo cancelled_trip(
Aart Bik0d345cf2016-03-16 10:49:38 -0700543 trip->induction_class,
544 trip->operation,
545 trip_expr->op_a,
546 trip->op_b,
547 nullptr,
548 trip->type);
Aart Bik7d57d7f2015-12-09 14:39:48 -0800549 return GetVal(&cancelled_trip, trip, in_body, is_min);
550 }
551 } else if (is_min && stride_value == -1) {
Aart Bik97412c922016-02-19 20:14:38 -0800552 // Test original trip's positive operand (trip_expr->op_a) against offset of induction.
Aart Bik7d57d7f2015-12-09 14:39:48 -0800553 if (HInductionVarAnalysis::InductionEqual(trip_expr->op_a, info->op_b)) {
554 // Analyze cancelled trip with just the negative operand (trip_expr->op_b).
555 HInductionVarAnalysis::InductionInfo neg(
556 HInductionVarAnalysis::kInvariant,
557 HInductionVarAnalysis::kNeg,
558 nullptr,
559 trip_expr->op_b,
Aart Bik0d345cf2016-03-16 10:49:38 -0700560 nullptr,
561 trip->type);
Aart Bik7d57d7f2015-12-09 14:39:48 -0800562 HInductionVarAnalysis::InductionInfo cancelled_trip(
Aart Bik0d345cf2016-03-16 10:49:38 -0700563 trip->induction_class, trip->operation, &neg, trip->op_b, nullptr, trip->type);
Aart Bik7d57d7f2015-12-09 14:39:48 -0800564 return SubValue(Value(0), GetVal(&cancelled_trip, trip, in_body, !is_min));
565 }
566 }
567 }
568 }
569 }
570 // General rule of linear induction a * i + b, for normalized 0 <= i < TC.
571 return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min),
572 GetVal(info->op_b, trip, in_body, is_min));
573}
574
Aart Bikdf7822e2016-12-06 10:05:30 -0800575InductionVarRange::Value InductionVarRange::GetPolynomial(HInductionVarAnalysis::InductionInfo* info,
576 HInductionVarAnalysis::InductionInfo* trip,
577 bool in_body,
578 bool is_min) const {
579 DCHECK(info != nullptr);
580 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial);
581 int64_t a = 0;
582 int64_t b = 0;
583 if (IsConstant(info->op_a->op_a, kExact, &a) && CanLongValueFitIntoInt(a) && a >= 0 &&
584 IsConstant(info->op_a->op_b, kExact, &b) && CanLongValueFitIntoInt(b) && b >= 0) {
Aart Bike6bd0272016-12-16 13:57:52 -0800585 // Evaluate bounds on sum_i=0^m-1(a * i + b) + c with a,b >= 0 for
Aart Bikdf7822e2016-12-06 10:05:30 -0800586 // maximum index value m as a * (m * (m-1)) / 2 + b * m + c.
587 Value c = GetVal(info->op_b, trip, in_body, is_min);
588 if (is_min) {
589 return c;
590 } else {
591 Value m = GetVal(trip, trip, in_body, is_min);
592 Value t = DivValue(MulValue(m, SubValue(m, Value(1))), Value(2));
593 Value x = MulValue(Value(a), t);
594 Value y = MulValue(Value(b), m);
595 return AddValue(AddValue(x, y), c);
596 }
597 }
598 return Value();
599}
600
Aart Bikc071a012016-12-01 10:22:31 -0800601InductionVarRange::Value InductionVarRange::GetGeometric(HInductionVarAnalysis::InductionInfo* info,
602 HInductionVarAnalysis::InductionInfo* trip,
603 bool in_body,
604 bool is_min) const {
605 DCHECK(info != nullptr);
Aart Bikdf7822e2016-12-06 10:05:30 -0800606 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric);
Aart Bikc071a012016-12-01 10:22:31 -0800607 int64_t a = 0;
608 int64_t f = 0;
609 if (IsConstant(info->op_a, kExact, &a) &&
610 CanLongValueFitIntoInt(a) &&
Aart Bikf3e61ee2017-04-12 17:09:20 -0700611 IsInt64AndGet(info->fetch, &f) && f >= 1) {
Aart Bikdf7822e2016-12-06 10:05:30 -0800612 // Conservative bounds on a * f^-i + b with f >= 1 can be computed without
613 // trip count. Other forms would require a much more elaborate evaluation.
Aart Bikc071a012016-12-01 10:22:31 -0800614 const bool is_min_a = a >= 0 ? is_min : !is_min;
615 if (info->operation == HInductionVarAnalysis::kDiv) {
Aart Bikdf7822e2016-12-06 10:05:30 -0800616 Value b = GetVal(info->op_b, trip, in_body, is_min);
617 return is_min_a ? b : AddValue(Value(a), b);
Aart Bikc071a012016-12-01 10:22:31 -0800618 }
619 }
620 return Value();
621}
622
Aart Bikd14c5952015-09-08 15:25:15 -0700623InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction,
Aart Bik22af3be2015-09-10 12:50:58 -0700624 HInductionVarAnalysis::InductionInfo* trip,
Aart Bik9401f532015-09-28 16:25:56 -0700625 bool in_body,
Aart Bik7d57d7f2015-12-09 14:39:48 -0800626 bool is_min) const {
Aart Bik40fbf742016-10-31 11:02:50 -0700627 // Special case when chasing constants: single instruction that denotes trip count in the
628 // loop-body is minimal 1 and maximal, with safe trip-count, max int,
629 if (chase_hint_ == nullptr && in_body && trip != nullptr && instruction == trip->op_a->fetch) {
Aart Bik52be7e72016-06-23 11:20:41 -0700630 if (is_min) {
631 return Value(1);
Aart Bikdf7822e2016-12-06 10:05:30 -0800632 } else if (!instruction->IsConstant() && !IsUnsafeTripCount(trip)) {
Aart Bik52be7e72016-06-23 11:20:41 -0700633 return Value(std::numeric_limits<int32_t>::max());
634 }
635 }
Aart Bik40fbf742016-10-31 11:02:50 -0700636 // Unless at a constant or hint, chase the instruction a bit deeper into the HIR tree, so that
637 // it becomes more likely range analysis will compare the same instructions as terminal nodes.
638 int64_t value;
Aart Bikf3e61ee2017-04-12 17:09:20 -0700639 if (IsInt64AndGet(instruction, &value) && CanLongValueFitIntoInt(value)) {
Aart Bik40fbf742016-10-31 11:02:50 -0700640 // Proper constant reveals best information.
641 return Value(static_cast<int32_t>(value));
642 } else if (instruction == chase_hint_) {
643 // At hint, fetch is represented by itself.
644 return Value(instruction, 1, 0);
645 } else if (instruction->IsAdd()) {
646 // Incorporate suitable constants in the chased value.
Aart Bikf3e61ee2017-04-12 17:09:20 -0700647 if (IsInt64AndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) {
Aart Bik97412c922016-02-19 20:14:38 -0800648 return AddValue(Value(static_cast<int32_t>(value)),
649 GetFetch(instruction->InputAt(1), trip, in_body, is_min));
Aart Bikf3e61ee2017-04-12 17:09:20 -0700650 } else if (IsInt64AndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) {
Aart Bik97412c922016-02-19 20:14:38 -0800651 return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min),
652 Value(static_cast<int32_t>(value)));
Aart Bik22af3be2015-09-10 12:50:58 -0700653 }
Aart Bik8e9090b2017-09-08 16:46:50 -0700654 } else if (instruction->IsSub()) {
655 // Incorporate suitable constants in the chased value.
656 if (IsInt64AndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) {
657 return SubValue(Value(static_cast<int32_t>(value)),
658 GetFetch(instruction->InputAt(1), trip, in_body, !is_min));
659 } else if (IsInt64AndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) {
660 return SubValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min),
661 Value(static_cast<int32_t>(value)));
662 }
Aart Bik52be7e72016-06-23 11:20:41 -0700663 } else if (instruction->IsArrayLength()) {
Aart Bik40fbf742016-10-31 11:02:50 -0700664 // Exploit length properties when chasing constants or chase into a new array declaration.
Aart Bik52be7e72016-06-23 11:20:41 -0700665 if (chase_hint_ == nullptr) {
666 return is_min ? Value(0) : Value(std::numeric_limits<int32_t>::max());
667 } else if (instruction->InputAt(0)->IsNewArray()) {
Nicolas Geoffraye761bcc2017-01-19 08:59:37 +0000668 return GetFetch(instruction->InputAt(0)->AsNewArray()->GetLength(), trip, in_body, is_min);
Aart Bik52be7e72016-06-23 11:20:41 -0700669 }
Aart Bik0d345cf2016-03-16 10:49:38 -0700670 } else if (instruction->IsTypeConversion()) {
Aart Bik40fbf742016-10-31 11:02:50 -0700671 // Since analysis is 32-bit (or narrower), chase beyond widening along the path.
Aart Bike6bd0272016-12-16 13:57:52 -0800672 // For example, this discovers the length in: for (long i = 0; i < a.length; i++);
Vladimir Marko0ebe0d82017-09-21 22:50:39 +0100673 if (instruction->AsTypeConversion()->GetInputType() == DataType::Type::kInt32 &&
674 instruction->AsTypeConversion()->GetResultType() == DataType::Type::kInt64) {
Aart Bik0d345cf2016-03-16 10:49:38 -0700675 return GetFetch(instruction->InputAt(0), trip, in_body, is_min);
676 }
Aart Bik52be7e72016-06-23 11:20:41 -0700677 }
678 // Chase an invariant fetch that is defined by an outer loop if the trip-count used
679 // so far is well-behaved in both bounds and the next trip-count is safe.
680 // Example:
681 // for (int i = 0; i <= 100; i++) // safe
682 // for (int j = 0; j <= i; j++) // well-behaved
683 // j is in range [0, i ] (if i is chase hint)
684 // or in range [0, 100] (otherwise)
685 HLoopInformation* next_loop = nullptr;
686 HInductionVarAnalysis::InductionInfo* next_info = nullptr;
687 HInductionVarAnalysis::InductionInfo* next_trip = nullptr;
688 bool next_in_body = true; // inner loop is always in body of outer loop
689 if (HasInductionInfo(instruction, instruction, &next_loop, &next_info, &next_trip) &&
690 IsWellBehavedTripCount(trip) &&
691 !IsUnsafeTripCount(next_trip)) {
692 return GetVal(next_info, next_trip, next_in_body, is_min);
Aart Bikd14c5952015-09-08 15:25:15 -0700693 }
Aart Bik40fbf742016-10-31 11:02:50 -0700694 // Fetch is represented by itself.
Aart Bikd14c5952015-09-08 15:25:15 -0700695 return Value(instruction, 1, 0);
696}
697
Aart Bikcd26feb2015-09-23 17:50:50 -0700698InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::InductionInfo* info,
699 HInductionVarAnalysis::InductionInfo* trip,
Aart Bik9401f532015-09-28 16:25:56 -0700700 bool in_body,
Aart Bik7d57d7f2015-12-09 14:39:48 -0800701 bool is_min) const {
Aart Bikd14c5952015-09-08 15:25:15 -0700702 if (info != nullptr) {
703 switch (info->induction_class) {
704 case HInductionVarAnalysis::kInvariant:
705 // Invariants.
706 switch (info->operation) {
Aart Bikd14c5952015-09-08 15:25:15 -0700707 case HInductionVarAnalysis::kAdd:
Aart Bik9401f532015-09-28 16:25:56 -0700708 return AddValue(GetVal(info->op_a, trip, in_body, is_min),
709 GetVal(info->op_b, trip, in_body, is_min));
Aart Bikcd26feb2015-09-23 17:50:50 -0700710 case HInductionVarAnalysis::kSub: // second reversed!
Aart Bik9401f532015-09-28 16:25:56 -0700711 return SubValue(GetVal(info->op_a, trip, in_body, is_min),
712 GetVal(info->op_b, trip, in_body, !is_min));
Aart Bikcd26feb2015-09-23 17:50:50 -0700713 case HInductionVarAnalysis::kNeg: // second reversed!
714 return SubValue(Value(0),
Aart Bik9401f532015-09-28 16:25:56 -0700715 GetVal(info->op_b, trip, in_body, !is_min));
Aart Bikd14c5952015-09-08 15:25:15 -0700716 case HInductionVarAnalysis::kMul:
Aart Bik9401f532015-09-28 16:25:56 -0700717 return GetMul(info->op_a, info->op_b, trip, in_body, is_min);
Aart Bikd14c5952015-09-08 15:25:15 -0700718 case HInductionVarAnalysis::kDiv:
Aart Bik9401f532015-09-28 16:25:56 -0700719 return GetDiv(info->op_a, info->op_b, trip, in_body, is_min);
Aart Bikdf7822e2016-12-06 10:05:30 -0800720 case HInductionVarAnalysis::kRem:
721 return GetRem(info->op_a, info->op_b);
Aart Bik7dc96932016-10-12 10:01:05 -0700722 case HInductionVarAnalysis::kXor:
723 return GetXor(info->op_a, info->op_b);
Aart Bikd14c5952015-09-08 15:25:15 -0700724 case HInductionVarAnalysis::kFetch:
Aart Bik9401f532015-09-28 16:25:56 -0700725 return GetFetch(info->fetch, trip, in_body, is_min);
726 case HInductionVarAnalysis::kTripCountInLoop:
Aart Bik389b3db2015-10-28 14:23:40 -0700727 case HInductionVarAnalysis::kTripCountInLoopUnsafe:
Aart Bikaec3cce2015-10-14 17:44:55 -0700728 if (!in_body && !is_min) { // one extra!
Aart Bik22f05872015-10-27 15:56:28 -0700729 return GetVal(info->op_a, trip, in_body, is_min);
Aart Bik9401f532015-09-28 16:25:56 -0700730 }
731 FALLTHROUGH_INTENDED;
732 case HInductionVarAnalysis::kTripCountInBody:
Aart Bik389b3db2015-10-28 14:23:40 -0700733 case HInductionVarAnalysis::kTripCountInBodyUnsafe:
Aart Bikaec3cce2015-10-14 17:44:55 -0700734 if (is_min) {
735 return Value(0);
736 } else if (in_body) {
Aart Bik22f05872015-10-27 15:56:28 -0700737 return SubValue(GetVal(info->op_a, trip, in_body, is_min), Value(1));
Aart Bik9401f532015-09-28 16:25:56 -0700738 }
739 break;
740 default:
741 break;
Aart Bikd14c5952015-09-08 15:25:15 -0700742 }
743 break;
Aart Bik52be7e72016-06-23 11:20:41 -0700744 case HInductionVarAnalysis::kLinear:
Aart Bik0d345cf2016-03-16 10:49:38 -0700745 return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type);
Aart Bikc071a012016-12-01 10:22:31 -0800746 case HInductionVarAnalysis::kPolynomial:
Aart Bikdf7822e2016-12-06 10:05:30 -0800747 return GetPolynomial(info, trip, in_body, is_min);
Aart Bikc071a012016-12-01 10:22:31 -0800748 case HInductionVarAnalysis::kGeometric:
749 return GetGeometric(info, trip, in_body, is_min);
Aart Bikd14c5952015-09-08 15:25:15 -0700750 case HInductionVarAnalysis::kWrapAround:
751 case HInductionVarAnalysis::kPeriodic:
Aart Bik9401f532015-09-28 16:25:56 -0700752 return MergeVal(GetVal(info->op_a, trip, in_body, is_min),
753 GetVal(info->op_b, trip, in_body, is_min), is_min);
Aart Bikd14c5952015-09-08 15:25:15 -0700754 }
755 }
Aart Bikb3365e02015-09-21 14:45:05 -0700756 return Value();
Aart Bikd14c5952015-09-08 15:25:15 -0700757}
758
759InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1,
760 HInductionVarAnalysis::InductionInfo* info2,
761 HInductionVarAnalysis::InductionInfo* trip,
Aart Bik9401f532015-09-28 16:25:56 -0700762 bool in_body,
Aart Bik7d57d7f2015-12-09 14:39:48 -0800763 bool is_min) const {
Aart Bik52be7e72016-06-23 11:20:41 -0700764 // Constant times range.
765 int64_t value = 0;
766 if (IsConstant(info1, kExact, &value)) {
767 return MulRangeAndConstant(value, info2, trip, in_body, is_min);
768 } else if (IsConstant(info2, kExact, &value)) {
769 return MulRangeAndConstant(value, info1, trip, in_body, is_min);
770 }
771 // Interval ranges.
Andreas Gampe3db70682018-12-26 15:12:03 -0800772 Value v1_min = GetVal(info1, trip, in_body, /* is_min= */ true);
773 Value v1_max = GetVal(info1, trip, in_body, /* is_min= */ false);
774 Value v2_min = GetVal(info2, trip, in_body, /* is_min= */ true);
775 Value v2_max = GetVal(info2, trip, in_body, /* is_min= */ false);
Aart Bik97412c922016-02-19 20:14:38 -0800776 // Positive range vs. positive or negative range.
777 if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) {
778 if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
779 return is_min ? MulValue(v1_min, v2_min) : MulValue(v1_max, v2_max);
780 } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) {
781 return is_min ? MulValue(v1_max, v2_min) : MulValue(v1_min, v2_max);
Aart Bikd14c5952015-09-08 15:25:15 -0700782 }
Aart Bik97412c922016-02-19 20:14:38 -0800783 }
784 // Negative range vs. positive or negative range.
785 if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) {
786 if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
787 return is_min ? MulValue(v1_min, v2_max) : MulValue(v1_max, v2_min);
788 } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) {
789 return is_min ? MulValue(v1_max, v2_max) : MulValue(v1_min, v2_min);
Aart Bikd14c5952015-09-08 15:25:15 -0700790 }
791 }
Aart Bikb3365e02015-09-21 14:45:05 -0700792 return Value();
Aart Bikd14c5952015-09-08 15:25:15 -0700793}
794
795InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::InductionInfo* info1,
796 HInductionVarAnalysis::InductionInfo* info2,
797 HInductionVarAnalysis::InductionInfo* trip,
Aart Bik9401f532015-09-28 16:25:56 -0700798 bool in_body,
Aart Bik7d57d7f2015-12-09 14:39:48 -0800799 bool is_min) const {
Aart Bik52be7e72016-06-23 11:20:41 -0700800 // Range divided by constant.
801 int64_t value = 0;
802 if (IsConstant(info2, kExact, &value)) {
803 return DivRangeAndConstant(value, info1, trip, in_body, is_min);
804 }
805 // Interval ranges.
Andreas Gampe3db70682018-12-26 15:12:03 -0800806 Value v1_min = GetVal(info1, trip, in_body, /* is_min= */ true);
807 Value v1_max = GetVal(info1, trip, in_body, /* is_min= */ false);
808 Value v2_min = GetVal(info2, trip, in_body, /* is_min= */ true);
809 Value v2_max = GetVal(info2, trip, in_body, /* is_min= */ false);
Aart Bik97412c922016-02-19 20:14:38 -0800810 // Positive range vs. positive or negative range.
811 if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) {
812 if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
813 return is_min ? DivValue(v1_min, v2_max) : DivValue(v1_max, v2_min);
814 } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) {
815 return is_min ? DivValue(v1_max, v2_max) : DivValue(v1_min, v2_min);
Aart Bikd14c5952015-09-08 15:25:15 -0700816 }
Aart Bik97412c922016-02-19 20:14:38 -0800817 }
818 // Negative range vs. positive or negative range.
819 if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) {
820 if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
821 return is_min ? DivValue(v1_min, v2_min) : DivValue(v1_max, v2_max);
822 } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) {
823 return is_min ? DivValue(v1_max, v2_min) : DivValue(v1_min, v2_max);
Aart Bikd14c5952015-09-08 15:25:15 -0700824 }
825 }
Aart Bikb3365e02015-09-21 14:45:05 -0700826 return Value();
Aart Bikd14c5952015-09-08 15:25:15 -0700827}
828
Aart Bikdf7822e2016-12-06 10:05:30 -0800829InductionVarRange::Value InductionVarRange::GetRem(
830 HInductionVarAnalysis::InductionInfo* info1,
831 HInductionVarAnalysis::InductionInfo* info2) const {
832 int64_t v1 = 0;
833 int64_t v2 = 0;
834 // Only accept exact values.
835 if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2) && v2 != 0) {
836 int64_t value = v1 % v2;
837 if (CanLongValueFitIntoInt(value)) {
838 return Value(static_cast<int32_t>(value));
839 }
840 }
841 return Value();
842}
843
Aart Bik7dc96932016-10-12 10:01:05 -0700844InductionVarRange::Value InductionVarRange::GetXor(
845 HInductionVarAnalysis::InductionInfo* info1,
846 HInductionVarAnalysis::InductionInfo* info2) const {
847 int64_t v1 = 0;
848 int64_t v2 = 0;
849 // Only accept exact values.
850 if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2)) {
851 int64_t value = v1 ^ v2;
852 if (CanLongValueFitIntoInt(value)) {
853 return Value(static_cast<int32_t>(value));
854 }
855 }
856 return Value();
857}
858
Aart Bik52be7e72016-06-23 11:20:41 -0700859InductionVarRange::Value InductionVarRange::MulRangeAndConstant(
860 int64_t value,
861 HInductionVarAnalysis::InductionInfo* info,
862 HInductionVarAnalysis::InductionInfo* trip,
863 bool in_body,
864 bool is_min) const {
865 if (CanLongValueFitIntoInt(value)) {
866 Value c(static_cast<int32_t>(value));
867 return MulValue(GetVal(info, trip, in_body, is_min == value >= 0), c);
868 }
869 return Value();
Aart Bik97412c922016-02-19 20:14:38 -0800870}
871
Aart Bik52be7e72016-06-23 11:20:41 -0700872InductionVarRange::Value InductionVarRange::DivRangeAndConstant(
873 int64_t value,
874 HInductionVarAnalysis::InductionInfo* info,
875 HInductionVarAnalysis::InductionInfo* trip,
876 bool in_body,
877 bool is_min) const {
878 if (CanLongValueFitIntoInt(value)) {
879 Value c(static_cast<int32_t>(value));
880 return DivValue(GetVal(info, trip, in_body, is_min == value >= 0), c);
881 }
882 return Value();
Aart Bik9401f532015-09-28 16:25:56 -0700883}
884
Aart Bik7d57d7f2015-12-09 14:39:48 -0800885InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) const {
Aart Bikb3365e02015-09-21 14:45:05 -0700886 if (v1.is_known && v2.is_known && IsSafeAdd(v1.b_constant, v2.b_constant)) {
Aart Bike6bd0272016-12-16 13:57:52 -0800887 int32_t b = v1.b_constant + v2.b_constant;
Aart Bikd14c5952015-09-08 15:25:15 -0700888 if (v1.a_constant == 0) {
889 return Value(v2.instruction, v2.a_constant, b);
890 } else if (v2.a_constant == 0) {
891 return Value(v1.instruction, v1.a_constant, b);
892 } else if (v1.instruction == v2.instruction && IsSafeAdd(v1.a_constant, v2.a_constant)) {
893 return Value(v1.instruction, v1.a_constant + v2.a_constant, b);
894 }
895 }
Aart Bikb3365e02015-09-21 14:45:05 -0700896 return Value();
Aart Bikd14c5952015-09-08 15:25:15 -0700897}
898
Aart Bik7d57d7f2015-12-09 14:39:48 -0800899InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) const {
Aart Bikb3365e02015-09-21 14:45:05 -0700900 if (v1.is_known && v2.is_known && IsSafeSub(v1.b_constant, v2.b_constant)) {
Aart Bike6bd0272016-12-16 13:57:52 -0800901 int32_t b = v1.b_constant - v2.b_constant;
Aart Bikd14c5952015-09-08 15:25:15 -0700902 if (v1.a_constant == 0 && IsSafeSub(0, v2.a_constant)) {
903 return Value(v2.instruction, -v2.a_constant, b);
904 } else if (v2.a_constant == 0) {
905 return Value(v1.instruction, v1.a_constant, b);
906 } else if (v1.instruction == v2.instruction && IsSafeSub(v1.a_constant, v2.a_constant)) {
907 return Value(v1.instruction, v1.a_constant - v2.a_constant, b);
908 }
909 }
Aart Bikb3365e02015-09-21 14:45:05 -0700910 return Value();
Aart Bikd14c5952015-09-08 15:25:15 -0700911}
912
Aart Bik7d57d7f2015-12-09 14:39:48 -0800913InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2) const {
Aart Bikb3365e02015-09-21 14:45:05 -0700914 if (v1.is_known && v2.is_known) {
915 if (v1.a_constant == 0) {
916 if (IsSafeMul(v1.b_constant, v2.a_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) {
917 return Value(v2.instruction, v1.b_constant * v2.a_constant, v1.b_constant * v2.b_constant);
918 }
919 } else if (v2.a_constant == 0) {
920 if (IsSafeMul(v1.a_constant, v2.b_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) {
921 return Value(v1.instruction, v1.a_constant * v2.b_constant, v1.b_constant * v2.b_constant);
922 }
Aart Bikd14c5952015-09-08 15:25:15 -0700923 }
924 }
Aart Bikb3365e02015-09-21 14:45:05 -0700925 return Value();
Aart Bikd14c5952015-09-08 15:25:15 -0700926}
927
Aart Bik7d57d7f2015-12-09 14:39:48 -0800928InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2) const {
Aart Bikb3365e02015-09-21 14:45:05 -0700929 if (v1.is_known && v2.is_known && v1.a_constant == 0 && v2.a_constant == 0) {
Aart Bikd14c5952015-09-08 15:25:15 -0700930 if (IsSafeDiv(v1.b_constant, v2.b_constant)) {
931 return Value(v1.b_constant / v2.b_constant);
932 }
933 }
Aart Bikb3365e02015-09-21 14:45:05 -0700934 return Value();
Aart Bikd14c5952015-09-08 15:25:15 -0700935}
936
Aart Bik7d57d7f2015-12-09 14:39:48 -0800937InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is_min) const {
Aart Bikb3365e02015-09-21 14:45:05 -0700938 if (v1.is_known && v2.is_known) {
939 if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) {
Aart Bikcd26feb2015-09-23 17:50:50 -0700940 return Value(v1.instruction, v1.a_constant,
941 is_min ? std::min(v1.b_constant, v2.b_constant)
942 : std::max(v1.b_constant, v2.b_constant));
Aart Bikb3365e02015-09-21 14:45:05 -0700943 }
Aart Bikd14c5952015-09-08 15:25:15 -0700944 }
Aart Bikb3365e02015-09-21 14:45:05 -0700945 return Value();
Aart Bikd14c5952015-09-08 15:25:15 -0700946}
947
Aart Bik9abf8942016-10-14 09:49:42 -0700948bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context,
949 HInstruction* instruction,
950 bool is_last_value,
951 HGraph* graph,
952 HBasicBlock* block,
953 /*out*/HInstruction** lower,
954 /*out*/HInstruction** upper,
955 /*out*/HInstruction** taken_test,
956 /*out*/int64_t* stride_value,
957 /*out*/bool* needs_finite_test,
958 /*out*/bool* needs_taken_test) const {
Aart Bik52be7e72016-06-23 11:20:41 -0700959 HLoopInformation* loop = nullptr;
960 HInductionVarAnalysis::InductionInfo* info = nullptr;
961 HInductionVarAnalysis::InductionInfo* trip = nullptr;
962 if (!HasInductionInfo(context, instruction, &loop, &info, &trip) || trip == nullptr) {
963 return false; // codegen needs all information, including tripcount
Aart Bik97412c922016-02-19 20:14:38 -0800964 }
965 // Determine what tests are needed. A finite test is needed if the evaluation code uses the
966 // trip-count and the loop maybe unsafe (because in such cases, the index could "overshoot"
967 // the computed range). A taken test is needed for any unknown trip-count, even if evaluation
968 // code does not use the trip-count explicitly (since there could be an implicit relation
969 // between e.g. an invariant subscript and a not-taken condition).
Aart Bik52be7e72016-06-23 11:20:41 -0700970 bool in_body = context->GetBlock() != loop->GetHeader();
Aart Bik16d3a652016-09-09 10:33:50 -0700971 *stride_value = 0;
972 *needs_finite_test = NeedsTripCount(info, stride_value) && IsUnsafeTripCount(trip);
Aart Bik97412c922016-02-19 20:14:38 -0800973 *needs_taken_test = IsBodyTripCount(trip);
Aart Bik16d3a652016-09-09 10:33:50 -0700974 // Handle last value request.
975 if (is_last_value) {
Aart Bikc071a012016-12-01 10:22:31 -0800976 DCHECK(!in_body);
977 switch (info->induction_class) {
978 case HInductionVarAnalysis::kLinear:
979 if (*stride_value > 0) {
980 lower = nullptr;
981 } else {
982 upper = nullptr;
983 }
984 break;
Aart Bikdf7822e2016-12-06 10:05:30 -0800985 case HInductionVarAnalysis::kPolynomial:
986 return GenerateLastValuePolynomial(info, trip, graph, block, lower);
Aart Bikc071a012016-12-01 10:22:31 -0800987 case HInductionVarAnalysis::kGeometric:
988 return GenerateLastValueGeometric(info, trip, graph, block, lower);
Aart Bikdf7822e2016-12-06 10:05:30 -0800989 case HInductionVarAnalysis::kWrapAround:
990 return GenerateLastValueWrapAround(info, trip, graph, block, lower);
Aart Bikc071a012016-12-01 10:22:31 -0800991 case HInductionVarAnalysis::kPeriodic:
992 return GenerateLastValuePeriodic(info, trip, graph, block, lower, needs_taken_test);
993 default:
994 return false;
Aart Bik16d3a652016-09-09 10:33:50 -0700995 }
996 }
Aart Bik97412c922016-02-19 20:14:38 -0800997 // Code generation for taken test: generate the code when requested or otherwise analyze
998 // if code generation is feasible when taken test is needed.
999 if (taken_test != nullptr) {
Andreas Gampe3db70682018-12-26 15:12:03 -08001000 return GenerateCode(trip->op_b, nullptr, graph, block, taken_test, in_body, /* is_min= */ false);
Aart Bik97412c922016-02-19 20:14:38 -08001001 } else if (*needs_taken_test) {
1002 if (!GenerateCode(
Andreas Gampe3db70682018-12-26 15:12:03 -08001003 trip->op_b, nullptr, nullptr, nullptr, nullptr, in_body, /* is_min= */ false)) {
Aart Bik97412c922016-02-19 20:14:38 -08001004 return false;
1005 }
1006 }
1007 // Code generation for lower and upper.
1008 return
1009 // Success on lower if invariant (not set), or code can be generated.
1010 ((info->induction_class == HInductionVarAnalysis::kInvariant) ||
Andreas Gampe3db70682018-12-26 15:12:03 -08001011 GenerateCode(info, trip, graph, block, lower, in_body, /* is_min= */ true)) &&
Aart Bik97412c922016-02-19 20:14:38 -08001012 // And success on upper.
Andreas Gampe3db70682018-12-26 15:12:03 -08001013 GenerateCode(info, trip, graph, block, upper, in_body, /* is_min= */ false);
Aart Bikaec3cce2015-10-14 17:44:55 -07001014}
1015
Aart Bikdf7822e2016-12-06 10:05:30 -08001016bool InductionVarRange::GenerateLastValuePolynomial(HInductionVarAnalysis::InductionInfo* info,
1017 HInductionVarAnalysis::InductionInfo* trip,
1018 HGraph* graph,
1019 HBasicBlock* block,
1020 /*out*/HInstruction** result) const {
1021 DCHECK(info != nullptr);
1022 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial);
1023 // Detect known coefficients and trip count (always taken).
1024 int64_t a = 0;
1025 int64_t b = 0;
1026 int64_t m = 0;
Aart Bikd0a022d2016-12-13 11:22:31 -08001027 if (IsConstant(info->op_a->op_a, kExact, &a) &&
1028 IsConstant(info->op_a->op_b, kExact, &b) &&
Aart Bikdf7822e2016-12-06 10:05:30 -08001029 IsConstant(trip->op_a, kExact, &m) && m >= 1) {
Aart Bikd0a022d2016-12-13 11:22:31 -08001030 // Evaluate bounds on sum_i=0^m-1(a * i + b) + c for known
Aart Bikdf7822e2016-12-06 10:05:30 -08001031 // maximum index value m as a * (m * (m-1)) / 2 + b * m + c.
Aart Bike6bd0272016-12-16 13:57:52 -08001032 HInstruction* c = nullptr;
1033 if (GenerateCode(info->op_b, nullptr, graph, block, graph ? &c : nullptr, false, false)) {
Aart Bikdf7822e2016-12-06 10:05:30 -08001034 if (graph != nullptr) {
Vladimir Marko0ebe0d82017-09-21 22:50:39 +01001035 DataType::Type type = info->type;
Aart Bikdf7822e2016-12-06 10:05:30 -08001036 int64_t sum = a * ((m * (m - 1)) / 2) + b * m;
Vladimir Marko0ebe0d82017-09-21 22:50:39 +01001037 if (type != DataType::Type::kInt64) {
Aart Bike6bd0272016-12-16 13:57:52 -08001038 sum = static_cast<int32_t>(sum); // okay to truncate
1039 }
1040 *result =
Vladimir Markoca6fff82017-10-03 14:49:14 +01001041 Insert(block, new (graph->GetAllocator()) HAdd(type, graph->GetConstant(type, sum), c));
Aart Bikdf7822e2016-12-06 10:05:30 -08001042 }
1043 return true;
1044 }
1045 }
1046 return false;
1047}
1048
Aart Bikc071a012016-12-01 10:22:31 -08001049bool InductionVarRange::GenerateLastValueGeometric(HInductionVarAnalysis::InductionInfo* info,
1050 HInductionVarAnalysis::InductionInfo* trip,
1051 HGraph* graph,
1052 HBasicBlock* block,
1053 /*out*/HInstruction** result) const {
1054 DCHECK(info != nullptr);
Aart Bikdf7822e2016-12-06 10:05:30 -08001055 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric);
Aart Bikc071a012016-12-01 10:22:31 -08001056 // Detect known base and trip count (always taken).
1057 int64_t f = 0;
Aart Bike6bd0272016-12-16 13:57:52 -08001058 int64_t m = 0;
Aart Bikf3e61ee2017-04-12 17:09:20 -07001059 if (IsInt64AndGet(info->fetch, &f) && f >= 1 && IsConstant(trip->op_a, kExact, &m) && m >= 1) {
Aart Bikc071a012016-12-01 10:22:31 -08001060 HInstruction* opa = nullptr;
1061 HInstruction* opb = nullptr;
1062 if (GenerateCode(info->op_a, nullptr, graph, block, &opa, false, false) &&
1063 GenerateCode(info->op_b, nullptr, graph, block, &opb, false, false)) {
Aart Bikc071a012016-12-01 10:22:31 -08001064 if (graph != nullptr) {
Vladimir Marko0ebe0d82017-09-21 22:50:39 +01001065 DataType::Type type = info->type;
Aart Bikd3ba6262017-01-30 14:37:12 -08001066 // Compute f ^ m for known maximum index value m.
1067 bool overflow = false;
1068 int64_t fpow = IntPow(f, m, &overflow);
1069 if (info->operation == HInductionVarAnalysis::kDiv) {
1070 // For division, any overflow truncates to zero.
Vladimir Marko0ebe0d82017-09-21 22:50:39 +01001071 if (overflow || (type != DataType::Type::kInt64 && !CanLongValueFitIntoInt(fpow))) {
Aart Bikd3ba6262017-01-30 14:37:12 -08001072 fpow = 0;
1073 }
Vladimir Marko0ebe0d82017-09-21 22:50:39 +01001074 } else if (type != DataType::Type::kInt64) {
Aart Bikd3ba6262017-01-30 14:37:12 -08001075 // For multiplication, okay to truncate to required precision.
1076 DCHECK(info->operation == HInductionVarAnalysis::kMul);
1077 fpow = static_cast<int32_t>(fpow);
1078 }
1079 // Generate code.
Aart Bike6bd0272016-12-16 13:57:52 -08001080 if (fpow == 0) {
Aart Bikc071a012016-12-01 10:22:31 -08001081 // Special case: repeated mul/div always yields zero.
Aart Bike6bd0272016-12-16 13:57:52 -08001082 *result = graph->GetConstant(type, 0);
Aart Bikc071a012016-12-01 10:22:31 -08001083 } else {
Aart Bike6bd0272016-12-16 13:57:52 -08001084 // Last value: a * f ^ m + b or a * f ^ -m + b.
Aart Bike6bd0272016-12-16 13:57:52 -08001085 HInstruction* e = nullptr;
Vladimir Markoca6fff82017-10-03 14:49:14 +01001086 ArenaAllocator* allocator = graph->GetAllocator();
Aart Bike6bd0272016-12-16 13:57:52 -08001087 if (info->operation == HInductionVarAnalysis::kMul) {
Vladimir Markoca6fff82017-10-03 14:49:14 +01001088 e = new (allocator) HMul(type, opa, graph->GetConstant(type, fpow));
Aart Bike6bd0272016-12-16 13:57:52 -08001089 } else {
Vladimir Markoca6fff82017-10-03 14:49:14 +01001090 e = new (allocator) HDiv(type, opa, graph->GetConstant(type, fpow), kNoDexPc);
Aart Bike6bd0272016-12-16 13:57:52 -08001091 }
Vladimir Markoca6fff82017-10-03 14:49:14 +01001092 *result = Insert(block, new (allocator) HAdd(type, Insert(block, e), opb));
Aart Bikc071a012016-12-01 10:22:31 -08001093 }
1094 }
1095 return true;
1096 }
1097 }
1098 return false;
1099}
1100
Aart Bikdf7822e2016-12-06 10:05:30 -08001101bool InductionVarRange::GenerateLastValueWrapAround(HInductionVarAnalysis::InductionInfo* info,
1102 HInductionVarAnalysis::InductionInfo* trip,
1103 HGraph* graph,
1104 HBasicBlock* block,
1105 /*out*/HInstruction** result) const {
1106 DCHECK(info != nullptr);
1107 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kWrapAround);
1108 // Count depth.
1109 int32_t depth = 0;
1110 for (; info->induction_class == HInductionVarAnalysis::kWrapAround;
1111 info = info->op_b, ++depth) {}
1112 // Handle wrap(x, wrap(.., y)) if trip count reaches an invariant at end.
Aart Bike6bd0272016-12-16 13:57:52 -08001113 // TODO: generalize, but be careful to adjust the terminal.
1114 int64_t m = 0;
Aart Bikdf7822e2016-12-06 10:05:30 -08001115 if (info->induction_class == HInductionVarAnalysis::kInvariant &&
Aart Bike6bd0272016-12-16 13:57:52 -08001116 IsConstant(trip->op_a, kExact, &m) && m >= depth) {
1117 return GenerateCode(info, nullptr, graph, block, result, false, false);
Aart Bikdf7822e2016-12-06 10:05:30 -08001118 }
1119 return false;
1120}
1121
Aart Bik9abf8942016-10-14 09:49:42 -07001122bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info,
1123 HInductionVarAnalysis::InductionInfo* trip,
1124 HGraph* graph,
1125 HBasicBlock* block,
1126 /*out*/HInstruction** result,
1127 /*out*/bool* needs_taken_test) const {
Aart Bikc071a012016-12-01 10:22:31 -08001128 DCHECK(info != nullptr);
Aart Bikdf7822e2016-12-06 10:05:30 -08001129 DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPeriodic);
Aart Bik8523ea12017-06-01 15:45:09 -07001130 // Count period and detect all-invariants.
Aart Bike6bd0272016-12-16 13:57:52 -08001131 int64_t period = 1;
Aart Bik8523ea12017-06-01 15:45:09 -07001132 bool all_invariants = true;
1133 HInductionVarAnalysis::InductionInfo* p = info;
1134 for (; p->induction_class == HInductionVarAnalysis::kPeriodic; p = p->op_b, ++period) {
1135 DCHECK_EQ(p->op_a->induction_class, HInductionVarAnalysis::kInvariant);
1136 if (p->op_a->operation != HInductionVarAnalysis::kFetch) {
1137 all_invariants = false;
1138 }
1139 }
1140 DCHECK_EQ(p->induction_class, HInductionVarAnalysis::kInvariant);
1141 if (p->operation != HInductionVarAnalysis::kFetch) {
1142 all_invariants = false;
1143 }
1144 // Don't rely on FP arithmetic to be precise, unless the full period
1145 // consist of pre-computed expressions only.
Vladimir Marko0ebe0d82017-09-21 22:50:39 +01001146 if (info->type == DataType::Type::kFloat32 || info->type == DataType::Type::kFloat64) {
Aart Bik8523ea12017-06-01 15:45:09 -07001147 if (!all_invariants) {
1148 return false;
1149 }
1150 }
Aart Bike6bd0272016-12-16 13:57:52 -08001151 // Handle any periodic(x, periodic(.., y)) for known maximum index value m.
1152 int64_t m = 0;
1153 if (IsConstant(trip->op_a, kExact, &m) && m >= 1) {
1154 int64_t li = m % period;
1155 for (int64_t i = 0; i < li; info = info->op_b, i++) {}
1156 if (info->induction_class == HInductionVarAnalysis::kPeriodic) {
1157 info = info->op_a;
1158 }
1159 return GenerateCode(info, nullptr, graph, block, result, false, false);
Aart Bik9abf8942016-10-14 09:49:42 -07001160 }
Aart Bike6bd0272016-12-16 13:57:52 -08001161 // Handle periodic(x, y) using even/odd-select on trip count. Enter trip count expression
1162 // directly to obtain the maximum index value t even if taken test is needed.
1163 HInstruction* x = nullptr;
1164 HInstruction* y = nullptr;
1165 HInstruction* t = nullptr;
1166 if (period == 2 &&
1167 GenerateCode(info->op_a, nullptr, graph, block, graph ? &x : nullptr, false, false) &&
1168 GenerateCode(info->op_b, nullptr, graph, block, graph ? &y : nullptr, false, false) &&
1169 GenerateCode(trip->op_a, nullptr, graph, block, graph ? &t : nullptr, false, false)) {
1170 // During actual code generation (graph != nullptr), generate is_even ? x : y.
Aart Bik9abf8942016-10-14 09:49:42 -07001171 if (graph != nullptr) {
Vladimir Marko0ebe0d82017-09-21 22:50:39 +01001172 DataType::Type type = trip->type;
Vladimir Markoca6fff82017-10-03 14:49:14 +01001173 ArenaAllocator* allocator = graph->GetAllocator();
Aart Bike6bd0272016-12-16 13:57:52 -08001174 HInstruction* msk =
Vladimir Markoca6fff82017-10-03 14:49:14 +01001175 Insert(block, new (allocator) HAnd(type, t, graph->GetConstant(type, 1)));
Aart Bike6bd0272016-12-16 13:57:52 -08001176 HInstruction* is_even =
Vladimir Markoca6fff82017-10-03 14:49:14 +01001177 Insert(block, new (allocator) HEqual(msk, graph->GetConstant(type, 0), kNoDexPc));
1178 *result = Insert(block, new (graph->GetAllocator()) HSelect(is_even, x, y, kNoDexPc));
Aart Bik9abf8942016-10-14 09:49:42 -07001179 }
1180 // Guard select with taken test if needed.
1181 if (*needs_taken_test) {
Aart Bike6bd0272016-12-16 13:57:52 -08001182 HInstruction* is_taken = nullptr;
1183 if (GenerateCode(trip->op_b, nullptr, graph, block, graph ? &is_taken : nullptr, false, false)) {
1184 if (graph != nullptr) {
Vladimir Markoca6fff82017-10-03 14:49:14 +01001185 ArenaAllocator* allocator = graph->GetAllocator();
1186 *result = Insert(block, new (allocator) HSelect(is_taken, *result, x, kNoDexPc));
Aart Bike6bd0272016-12-16 13:57:52 -08001187 }
1188 *needs_taken_test = false; // taken care of
1189 } else {
Aart Bik9abf8942016-10-14 09:49:42 -07001190 return false;
Aart Bik9abf8942016-10-14 09:49:42 -07001191 }
Aart Bik9abf8942016-10-14 09:49:42 -07001192 }
1193 return true;
1194 }
1195 return false;
1196}
1197
Aart Bikaec3cce2015-10-14 17:44:55 -07001198bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
1199 HInductionVarAnalysis::InductionInfo* trip,
1200 HGraph* graph, // when set, code is generated
1201 HBasicBlock* block,
1202 /*out*/HInstruction** result,
1203 bool in_body,
Aart Bik7d57d7f2015-12-09 14:39:48 -08001204 bool is_min) const {
Aart Bikaec3cce2015-10-14 17:44:55 -07001205 if (info != nullptr) {
Aart Bik16d3a652016-09-09 10:33:50 -07001206 // If during codegen, the result is not needed (nullptr), simply return success.
1207 if (graph != nullptr && result == nullptr) {
1208 return true;
1209 }
Aart Bik0d345cf2016-03-16 10:49:38 -07001210 // Handle current operation.
Vladimir Marko0ebe0d82017-09-21 22:50:39 +01001211 DataType::Type type = info->type;
Aart Bikaec3cce2015-10-14 17:44:55 -07001212 HInstruction* opa = nullptr;
1213 HInstruction* opb = nullptr;
Aart Bikaec3cce2015-10-14 17:44:55 -07001214 switch (info->induction_class) {
1215 case HInductionVarAnalysis::kInvariant:
Aart Bik8e02e3e2017-02-28 14:41:55 -08001216 // Invariants (note that since invariants only have other invariants as
1217 // sub expressions, viz. no induction, there is no need to adjust is_min).
Aart Bikaec3cce2015-10-14 17:44:55 -07001218 switch (info->operation) {
1219 case HInductionVarAnalysis::kAdd:
Aart Bik8e02e3e2017-02-28 14:41:55 -08001220 case HInductionVarAnalysis::kSub:
1221 case HInductionVarAnalysis::kMul:
1222 case HInductionVarAnalysis::kDiv:
1223 case HInductionVarAnalysis::kRem:
1224 case HInductionVarAnalysis::kXor:
Aart Bik389b3db2015-10-28 14:23:40 -07001225 case HInductionVarAnalysis::kLT:
1226 case HInductionVarAnalysis::kLE:
1227 case HInductionVarAnalysis::kGT:
1228 case HInductionVarAnalysis::kGE:
Aart Bikaec3cce2015-10-14 17:44:55 -07001229 if (GenerateCode(info->op_a, trip, graph, block, &opa, in_body, is_min) &&
1230 GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
1231 if (graph != nullptr) {
Aart Bik389b3db2015-10-28 14:23:40 -07001232 HInstruction* operation = nullptr;
1233 switch (info->operation) {
1234 case HInductionVarAnalysis::kAdd:
Vladimir Markoca6fff82017-10-03 14:49:14 +01001235 operation = new (graph->GetAllocator()) HAdd(type, opa, opb); break;
Aart Bik8e02e3e2017-02-28 14:41:55 -08001236 case HInductionVarAnalysis::kSub:
Vladimir Markoca6fff82017-10-03 14:49:14 +01001237 operation = new (graph->GetAllocator()) HSub(type, opa, opb); break;
Aart Bik8e02e3e2017-02-28 14:41:55 -08001238 case HInductionVarAnalysis::kMul:
Vladimir Markoca6fff82017-10-03 14:49:14 +01001239 operation = new (graph->GetAllocator()) HMul(type, opa, opb, kNoDexPc); break;
Aart Bik8e02e3e2017-02-28 14:41:55 -08001240 case HInductionVarAnalysis::kDiv:
Vladimir Markoca6fff82017-10-03 14:49:14 +01001241 operation = new (graph->GetAllocator()) HDiv(type, opa, opb, kNoDexPc); break;
Aart Bikdf7822e2016-12-06 10:05:30 -08001242 case HInductionVarAnalysis::kRem:
Vladimir Markoca6fff82017-10-03 14:49:14 +01001243 operation = new (graph->GetAllocator()) HRem(type, opa, opb, kNoDexPc); break;
Aart Bik9abf8942016-10-14 09:49:42 -07001244 case HInductionVarAnalysis::kXor:
Vladimir Markoca6fff82017-10-03 14:49:14 +01001245 operation = new (graph->GetAllocator()) HXor(type, opa, opb); break;
Aart Bik389b3db2015-10-28 14:23:40 -07001246 case HInductionVarAnalysis::kLT:
Vladimir Markoca6fff82017-10-03 14:49:14 +01001247 operation = new (graph->GetAllocator()) HLessThan(opa, opb); break;
Aart Bik389b3db2015-10-28 14:23:40 -07001248 case HInductionVarAnalysis::kLE:
Vladimir Markoca6fff82017-10-03 14:49:14 +01001249 operation = new (graph->GetAllocator()) HLessThanOrEqual(opa, opb); break;
Aart Bik389b3db2015-10-28 14:23:40 -07001250 case HInductionVarAnalysis::kGT:
Vladimir Markoca6fff82017-10-03 14:49:14 +01001251 operation = new (graph->GetAllocator()) HGreaterThan(opa, opb); break;
Aart Bik389b3db2015-10-28 14:23:40 -07001252 case HInductionVarAnalysis::kGE:
Vladimir Markoca6fff82017-10-03 14:49:14 +01001253 operation = new (graph->GetAllocator()) HGreaterThanOrEqual(opa, opb); break;
Aart Bik389b3db2015-10-28 14:23:40 -07001254 default:
1255 LOG(FATAL) << "unknown operation";
1256 }
1257 *result = Insert(block, operation);
Aart Bikaec3cce2015-10-14 17:44:55 -07001258 }
1259 return true;
1260 }
1261 break;
Aart Bik8e02e3e2017-02-28 14:41:55 -08001262 case HInductionVarAnalysis::kNeg:
Aart Bikaec3cce2015-10-14 17:44:55 -07001263 if (GenerateCode(info->op_b, trip, graph, block, &opb, in_body, !is_min)) {
1264 if (graph != nullptr) {
Vladimir Markoca6fff82017-10-03 14:49:14 +01001265 *result = Insert(block, new (graph->GetAllocator()) HNeg(type, opb));
Aart Bikaec3cce2015-10-14 17:44:55 -07001266 }
1267 return true;
1268 }
1269 break;
1270 case HInductionVarAnalysis::kFetch:
Aart Bik0d345cf2016-03-16 10:49:38 -07001271 if (graph != nullptr) {
1272 *result = info->fetch; // already in HIR
Aart Bikaec3cce2015-10-14 17:44:55 -07001273 }
Aart Bik0d345cf2016-03-16 10:49:38 -07001274 return true;
Aart Bikaec3cce2015-10-14 17:44:55 -07001275 case HInductionVarAnalysis::kTripCountInLoop:
Aart Bik389b3db2015-10-28 14:23:40 -07001276 case HInductionVarAnalysis::kTripCountInLoopUnsafe:
Aart Bikaec3cce2015-10-14 17:44:55 -07001277 if (!in_body && !is_min) { // one extra!
Aart Bik22f05872015-10-27 15:56:28 -07001278 return GenerateCode(info->op_a, trip, graph, block, result, in_body, is_min);
Aart Bikaec3cce2015-10-14 17:44:55 -07001279 }
1280 FALLTHROUGH_INTENDED;
1281 case HInductionVarAnalysis::kTripCountInBody:
Aart Bik389b3db2015-10-28 14:23:40 -07001282 case HInductionVarAnalysis::kTripCountInBodyUnsafe:
Aart Bikaec3cce2015-10-14 17:44:55 -07001283 if (is_min) {
1284 if (graph != nullptr) {
Aart Bike6bd0272016-12-16 13:57:52 -08001285 *result = graph->GetConstant(type, 0);
Aart Bikaec3cce2015-10-14 17:44:55 -07001286 }
1287 return true;
1288 } else if (in_body) {
Aart Bik22f05872015-10-27 15:56:28 -07001289 if (GenerateCode(info->op_a, trip, graph, block, &opb, in_body, is_min)) {
Aart Bikaec3cce2015-10-14 17:44:55 -07001290 if (graph != nullptr) {
Vladimir Markoca6fff82017-10-03 14:49:14 +01001291 ArenaAllocator* allocator = graph->GetAllocator();
Aart Bike6bd0272016-12-16 13:57:52 -08001292 *result =
Vladimir Markoca6fff82017-10-03 14:49:14 +01001293 Insert(block, new (allocator) HSub(type, opb, graph->GetConstant(type, 1)));
Aart Bikaec3cce2015-10-14 17:44:55 -07001294 }
1295 return true;
1296 }
1297 }
1298 break;
Aart Bik8e02e3e2017-02-28 14:41:55 -08001299 case HInductionVarAnalysis::kNop:
1300 LOG(FATAL) << "unexpected invariant nop";
1301 } // switch invariant operation
Aart Bikaec3cce2015-10-14 17:44:55 -07001302 break;
Aart Bik389b3db2015-10-28 14:23:40 -07001303 case HInductionVarAnalysis::kLinear: {
Aart Bik16d3a652016-09-09 10:33:50 -07001304 // Linear induction a * i + b, for normalized 0 <= i < TC. For ranges, this should
1305 // be restricted to a unit stride to avoid arithmetic wrap-around situations that
1306 // are harder to guard against. For a last value, requesting min/max based on any
Aart Bike6bd0272016-12-16 13:57:52 -08001307 // known stride yields right value. Always avoid any narrowing linear induction or
1308 // any type mismatch between the linear induction and the trip count expression.
1309 // TODO: careful runtime type conversions could generalize this latter restriction.
1310 if (!HInductionVarAnalysis::IsNarrowingLinear(info) && trip->type == type) {
1311 int64_t stride_value = 0;
1312 if (IsConstant(info->op_a, kExact, &stride_value) &&
1313 CanLongValueFitIntoInt(stride_value)) {
1314 const bool is_min_a = stride_value >= 0 ? is_min : !is_min;
1315 if (GenerateCode(trip, trip, graph, block, &opa, in_body, is_min_a) &&
1316 GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
1317 if (graph != nullptr) {
Vladimir Markoca6fff82017-10-03 14:49:14 +01001318 ArenaAllocator* allocator = graph->GetAllocator();
Aart Bike6bd0272016-12-16 13:57:52 -08001319 HInstruction* oper;
1320 if (stride_value == 1) {
Vladimir Markoca6fff82017-10-03 14:49:14 +01001321 oper = new (allocator) HAdd(type, opa, opb);
Aart Bike6bd0272016-12-16 13:57:52 -08001322 } else if (stride_value == -1) {
Vladimir Markoca6fff82017-10-03 14:49:14 +01001323 oper = new (graph->GetAllocator()) HSub(type, opb, opa);
Aart Bike6bd0272016-12-16 13:57:52 -08001324 } else {
1325 HInstruction* mul =
Vladimir Markoca6fff82017-10-03 14:49:14 +01001326 new (allocator) HMul(type, graph->GetConstant(type, stride_value), opa);
1327 oper = new (allocator) HAdd(type, Insert(block, mul), opb);
Aart Bike6bd0272016-12-16 13:57:52 -08001328 }
1329 *result = Insert(block, oper);
Aart Bikaec3cce2015-10-14 17:44:55 -07001330 }
Aart Bike6bd0272016-12-16 13:57:52 -08001331 return true;
Aart Bikaec3cce2015-10-14 17:44:55 -07001332 }
1333 }
1334 }
1335 break;
Aart Bik4a342772015-11-30 10:17:46 -08001336 }
Aart Bikc071a012016-12-01 10:22:31 -08001337 case HInductionVarAnalysis::kPolynomial:
1338 case HInductionVarAnalysis::kGeometric:
1339 break;
Aart Bik4a342772015-11-30 10:17:46 -08001340 case HInductionVarAnalysis::kWrapAround:
1341 case HInductionVarAnalysis::kPeriodic: {
1342 // Wrap-around and periodic inductions are restricted to constants only, so that extreme
1343 // values are easy to test at runtime without complications of arithmetic wrap-around.
1344 Value extreme = GetVal(info, trip, in_body, is_min);
Aart Bik97412c922016-02-19 20:14:38 -08001345 if (IsConstantValue(extreme)) {
Aart Bik4a342772015-11-30 10:17:46 -08001346 if (graph != nullptr) {
Aart Bike6bd0272016-12-16 13:57:52 -08001347 *result = graph->GetConstant(type, extreme.b_constant);
Aart Bik4a342772015-11-30 10:17:46 -08001348 }
1349 return true;
1350 }
1351 break;
1352 }
Aart Bik8e02e3e2017-02-28 14:41:55 -08001353 } // switch induction class
Aart Bikaec3cce2015-10-14 17:44:55 -07001354 }
1355 return false;
1356}
1357
Aart Bik16d3a652016-09-09 10:33:50 -07001358void InductionVarRange::ReplaceInduction(HInductionVarAnalysis::InductionInfo* info,
1359 HInstruction* fetch,
1360 HInstruction* replacement) {
1361 if (info != nullptr) {
1362 if (info->induction_class == HInductionVarAnalysis::kInvariant &&
1363 info->operation == HInductionVarAnalysis::kFetch &&
1364 info->fetch == fetch) {
1365 info->fetch = replacement;
1366 }
1367 ReplaceInduction(info->op_a, fetch, replacement);
1368 ReplaceInduction(info->op_b, fetch, replacement);
1369 }
1370}
1371
Aart Bikd14c5952015-09-08 15:25:15 -07001372} // namespace art