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 #include "induction_var_range.h"
18 
19 #include <limits>
20 
21 namespace art {
22 
23 /** Returns true if 64-bit constant fits in 32-bit constant. */
CanLongValueFitIntoInt(int64_t c)24 static bool CanLongValueFitIntoInt(int64_t c) {
25   return std::numeric_limits<int32_t>::min() <= c && c <= std::numeric_limits<int32_t>::max();
26 }
27 
28 /** Returns true if 32-bit addition can be done safely. */
IsSafeAdd(int32_t c1,int32_t c2)29 static bool IsSafeAdd(int32_t c1, int32_t c2) {
30   return CanLongValueFitIntoInt(static_cast<int64_t>(c1) + static_cast<int64_t>(c2));
31 }
32 
33 /** Returns true if 32-bit subtraction can be done safely. */
IsSafeSub(int32_t c1,int32_t c2)34 static bool IsSafeSub(int32_t c1, int32_t c2) {
35   return CanLongValueFitIntoInt(static_cast<int64_t>(c1) - static_cast<int64_t>(c2));
36 }
37 
38 /** Returns true if 32-bit multiplication can be done safely. */
IsSafeMul(int32_t c1,int32_t c2)39 static bool IsSafeMul(int32_t c1, int32_t c2) {
40   return CanLongValueFitIntoInt(static_cast<int64_t>(c1) * static_cast<int64_t>(c2));
41 }
42 
43 /** Returns true if 32-bit division can be done safely. */
IsSafeDiv(int32_t c1,int32_t c2)44 static bool IsSafeDiv(int32_t c1, int32_t c2) {
45   return c2 != 0 && CanLongValueFitIntoInt(static_cast<int64_t>(c1) / static_cast<int64_t>(c2));
46 }
47 
48 /** Computes a * b for a,b > 0 (at least until first overflow happens). */
SafeMul(int64_t a,int64_t b,bool * overflow)49 static 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. */
IntPow(int64_t b,int64_t e,bool * overflow)57 static int64_t IntPow(int64_t b, int64_t e, /*out*/ bool* overflow) {
58   DCHECK_LT(0, b);
59   DCHECK_LT(0, e);
60   int64_t pow = 1;
61   while (e) {
62     if (e & 1) {
63       pow = SafeMul(pow, b, overflow);
64     }
65     e >>= 1;
66     if (e) {
67       b = SafeMul(b, b, overflow);
68     }
69   }
70   return pow;
71 }
72 
73 /**
74  * Detects an instruction that is >= 0. As long as the value is carried by
75  * a single instruction, arithmetic wrap-around cannot occur.
76  */
IsGEZero(HInstruction * instruction)77 static bool IsGEZero(HInstruction* instruction) {
78   DCHECK(instruction != nullptr);
79   if (instruction->IsArrayLength()) {
80     return true;
81   } else if (instruction->IsMin()) {
82     // Instruction MIN(>=0, >=0) is >= 0.
83     return IsGEZero(instruction->InputAt(0)) &&
84            IsGEZero(instruction->InputAt(1));
85   } else if (instruction->IsAbs()) {
86     // Instruction ABS(>=0) is >= 0.
87     // NOTE: ABS(minint) = minint prevents assuming
88     //       >= 0 without looking at the argument.
89     return IsGEZero(instruction->InputAt(0));
90   }
91   int64_t value = -1;
92   return IsInt64AndGet(instruction, &value) && value >= 0;
93 }
94 
95 /** Hunts "under the hood" for a suitable instruction at the hint. */
IsMaxAtHint(HInstruction * instruction,HInstruction * hint,HInstruction ** suitable)96 static bool IsMaxAtHint(
97     HInstruction* instruction, HInstruction* hint, /*out*/HInstruction** suitable) {
98   if (instruction->IsMin()) {
99     // For MIN(x, y), return most suitable x or y as maximum.
100     return IsMaxAtHint(instruction->InputAt(0), hint, suitable) ||
101            IsMaxAtHint(instruction->InputAt(1), hint, suitable);
102   } else {
103     *suitable = instruction;
104     return HuntForDeclaration(instruction) == hint;
105   }
106 }
107 
108 /** Post-analysis simplification of a minimum value that makes the bound more useful to clients. */
SimplifyMin(InductionVarRange::Value v)109 static InductionVarRange::Value SimplifyMin(InductionVarRange::Value v) {
110   if (v.is_known && v.a_constant == 1 && v.b_constant <= 0) {
111     // If a == 1,  instruction >= 0 and b <= 0, just return the constant b.
112     // No arithmetic wrap-around can occur.
113     if (IsGEZero(v.instruction)) {
114       return InductionVarRange::Value(v.b_constant);
115     }
116   }
117   return v;
118 }
119 
120 /** Post-analysis simplification of a maximum value that makes the bound more useful to clients. */
SimplifyMax(InductionVarRange::Value v,HInstruction * hint)121 static InductionVarRange::Value SimplifyMax(InductionVarRange::Value v, HInstruction* hint) {
122   if (v.is_known && v.a_constant >= 1) {
123     // An upper bound a * (length / a) + b, where a >= 1, can be conservatively rewritten as
124     // length + b because length >= 0 is true.
125     int64_t value;
126     if (v.instruction->IsDiv() &&
127         v.instruction->InputAt(0)->IsArrayLength() &&
128         IsInt64AndGet(v.instruction->InputAt(1), &value) && v.a_constant == value) {
129       return InductionVarRange::Value(v.instruction->InputAt(0), 1, v.b_constant);
130     }
131     // If a == 1, the most suitable one suffices as maximum value.
132     HInstruction* suitable = nullptr;
133     if (v.a_constant == 1 && IsMaxAtHint(v.instruction, hint, &suitable)) {
134       return InductionVarRange::Value(suitable, 1, v.b_constant);
135     }
136   }
137   return v;
138 }
139 
140 /** Tests for a constant value. */
IsConstantValue(InductionVarRange::Value v)141 static bool IsConstantValue(InductionVarRange::Value v) {
142   return v.is_known && v.a_constant == 0;
143 }
144 
145 /** Corrects a value for type to account for arithmetic wrap-around in lower precision. */
CorrectForType(InductionVarRange::Value v,DataType::Type type)146 static InductionVarRange::Value CorrectForType(InductionVarRange::Value v, DataType::Type type) {
147   switch (type) {
148     case DataType::Type::kUint8:
149     case DataType::Type::kInt8:
150     case DataType::Type::kUint16:
151     case DataType::Type::kInt16: {
152       // Constants within range only.
153       // TODO: maybe some room for improvement, like allowing widening conversions
154       int32_t min = DataType::MinValueOfIntegralType(type);
155       int32_t max = DataType::MaxValueOfIntegralType(type);
156       return (IsConstantValue(v) && min <= v.b_constant && v.b_constant <= max)
157           ? v
158           : InductionVarRange::Value();
159     }
160     default:
161       return v;
162   }
163 }
164 
165 /** Inserts an instruction. */
Insert(HBasicBlock * block,HInstruction * instruction)166 static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) {
167   DCHECK(block != nullptr);
168   DCHECK(block->GetLastInstruction() != nullptr) << block->GetBlockId();
169   DCHECK(instruction != nullptr);
170   block->InsertInstructionBefore(instruction, block->GetLastInstruction());
171   return instruction;
172 }
173 
174 /** Obtains loop's control instruction. */
GetLoopControl(HLoopInformation * loop)175 static HInstruction* GetLoopControl(HLoopInformation* loop) {
176   DCHECK(loop != nullptr);
177   return loop->GetHeader()->GetLastInstruction();
178 }
179 
180 //
181 // Public class methods.
182 //
183 
InductionVarRange(HInductionVarAnalysis * induction_analysis)184 InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis)
185     : induction_analysis_(induction_analysis),
186       chase_hint_(nullptr) {
187   DCHECK(induction_analysis != nullptr);
188 }
189 
GetInductionRange(HInstruction * context,HInstruction * instruction,HInstruction * chase_hint,Value * min_val,Value * max_val,bool * needs_finite_test)190 bool InductionVarRange::GetInductionRange(HInstruction* context,
191                                           HInstruction* instruction,
192                                           HInstruction* chase_hint,
193                                           /*out*/Value* min_val,
194                                           /*out*/Value* max_val,
195                                           /*out*/bool* needs_finite_test) {
196   HLoopInformation* loop = nullptr;
197   HInductionVarAnalysis::InductionInfo* info = nullptr;
198   HInductionVarAnalysis::InductionInfo* trip = nullptr;
199   if (!HasInductionInfo(context, instruction, &loop, &info, &trip)) {
200     return false;
201   }
202   // Type int or lower (this is not too restrictive since intended clients, like
203   // bounds check elimination, will have truncated higher precision induction
204   // at their use point already).
205   switch (info->type) {
206     case DataType::Type::kUint8:
207     case DataType::Type::kInt8:
208     case DataType::Type::kUint16:
209     case DataType::Type::kInt16:
210     case DataType::Type::kInt32:
211       break;
212     default:
213       return false;
214   }
215   // Find range.
216   chase_hint_ = chase_hint;
217   bool in_body = context->GetBlock() != loop->GetHeader();
218   int64_t stride_value = 0;
219   *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min= */ true));
220   *max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min= */ false), chase_hint);
221   *needs_finite_test = NeedsTripCount(info, &stride_value) && IsUnsafeTripCount(trip);
222   chase_hint_ = nullptr;
223   // Retry chasing constants for wrap-around (merge sensitive).
224   if (!min_val->is_known && info->induction_class == HInductionVarAnalysis::kWrapAround) {
225     *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min= */ true));
226   }
227   return true;
228 }
229 
CanGenerateRange(HInstruction * context,HInstruction * instruction,bool * needs_finite_test,bool * needs_taken_test)230 bool InductionVarRange::CanGenerateRange(HInstruction* context,
231                                          HInstruction* instruction,
232                                          /*out*/bool* needs_finite_test,
233                                          /*out*/bool* needs_taken_test) {
234   bool is_last_value = false;
235   int64_t stride_value = 0;
236   return GenerateRangeOrLastValue(context,
237                                   instruction,
238                                   is_last_value,
239                                   nullptr,
240                                   nullptr,
241                                   nullptr,
242                                   nullptr,
243                                   nullptr,  // nothing generated yet
244                                   &stride_value,
245                                   needs_finite_test,
246                                   needs_taken_test)
247       && (stride_value == -1 ||
248           stride_value == 0 ||
249           stride_value == 1);  // avoid arithmetic wrap-around anomalies.
250 }
251 
GenerateRange(HInstruction * context,HInstruction * instruction,HGraph * graph,HBasicBlock * block,HInstruction ** lower,HInstruction ** upper)252 void InductionVarRange::GenerateRange(HInstruction* context,
253                                       HInstruction* instruction,
254                                       HGraph* graph,
255                                       HBasicBlock* block,
256                                       /*out*/HInstruction** lower,
257                                       /*out*/HInstruction** upper) {
258   bool is_last_value = false;
259   int64_t stride_value = 0;
260   bool b1, b2;  // unused
261   if (!GenerateRangeOrLastValue(context,
262                                 instruction,
263                                 is_last_value,
264                                 graph,
265                                 block,
266                                 lower,
267                                 upper,
268                                 nullptr,
269                                 &stride_value,
270                                 &b1,
271                                 &b2)) {
272     LOG(FATAL) << "Failed precondition: CanGenerateRange()";
273   }
274 }
275 
GenerateTakenTest(HInstruction * context,HGraph * graph,HBasicBlock * block)276 HInstruction* InductionVarRange::GenerateTakenTest(HInstruction* context,
277                                                    HGraph* graph,
278                                                    HBasicBlock* block) {
279   HInstruction* taken_test = nullptr;
280   bool is_last_value = false;
281   int64_t stride_value = 0;
282   bool b1, b2;  // unused
283   if (!GenerateRangeOrLastValue(context,
284                                 context,
285                                 is_last_value,
286                                 graph,
287                                 block,
288                                 nullptr,
289                                 nullptr,
290                                 &taken_test,
291                                 &stride_value,
292                                 &b1,
293                                 &b2)) {
294     LOG(FATAL) << "Failed precondition: CanGenerateRange()";
295   }
296   return taken_test;
297 }
298 
CanGenerateLastValue(HInstruction * instruction)299 bool InductionVarRange::CanGenerateLastValue(HInstruction* instruction) {
300   bool is_last_value = true;
301   int64_t stride_value = 0;
302   bool needs_finite_test = false;
303   bool needs_taken_test = false;
304   return GenerateRangeOrLastValue(instruction,
305                                   instruction,
306                                   is_last_value,
307                                   nullptr,
308                                   nullptr,
309                                   nullptr,
310                                   nullptr,
311                                   nullptr,  // nothing generated yet
312                                   &stride_value,
313                                   &needs_finite_test,
314                                   &needs_taken_test)
315       && !needs_finite_test && !needs_taken_test;
316 }
317 
GenerateLastValue(HInstruction * instruction,HGraph * graph,HBasicBlock * block)318 HInstruction* InductionVarRange::GenerateLastValue(HInstruction* instruction,
319                                                    HGraph* graph,
320                                                    HBasicBlock* block) {
321   HInstruction* last_value = nullptr;
322   bool is_last_value = true;
323   int64_t stride_value = 0;
324   bool b1, b2;  // unused
325   if (!GenerateRangeOrLastValue(instruction,
326                                 instruction,
327                                 is_last_value,
328                                 graph,
329                                 block,
330                                 &last_value,
331                                 &last_value,
332                                 nullptr,
333                                 &stride_value,
334                                 &b1,
335                                 &b2)) {
336     LOG(FATAL) << "Failed precondition: CanGenerateLastValue()";
337   }
338   return last_value;
339 }
340 
Replace(HInstruction * instruction,HInstruction * fetch,HInstruction * replacement)341 void InductionVarRange::Replace(HInstruction* instruction,
342                                 HInstruction* fetch,
343                                 HInstruction* replacement) {
344   for (HLoopInformation* lp = instruction->GetBlock()->GetLoopInformation();  // closest enveloping loop
345        lp != nullptr;
346        lp = lp->GetPreHeader()->GetLoopInformation()) {
347     // Update instruction's information.
348     ReplaceInduction(induction_analysis_->LookupInfo(lp, instruction), fetch, replacement);
349     // Update loop's trip-count information.
350     ReplaceInduction(induction_analysis_->LookupInfo(lp, GetLoopControl(lp)), fetch, replacement);
351   }
352 }
353 
IsFinite(HLoopInformation * loop,int64_t * trip_count) const354 bool InductionVarRange::IsFinite(HLoopInformation* loop, /*out*/ int64_t* trip_count) const {
355   bool is_constant_unused = false;
356   return CheckForFiniteAndConstantProps(loop, &is_constant_unused, trip_count);
357 }
358 
HasKnownTripCount(HLoopInformation * loop,int64_t * trip_count) const359 bool InductionVarRange::HasKnownTripCount(HLoopInformation* loop,
360                                           /*out*/ int64_t* trip_count) const {
361   bool is_constant = false;
362   CheckForFiniteAndConstantProps(loop, &is_constant, trip_count);
363   return is_constant;
364 }
365 
IsUnitStride(HInstruction * context,HInstruction * instruction,HGraph * graph,HInstruction ** offset) const366 bool InductionVarRange::IsUnitStride(HInstruction* context,
367                                      HInstruction* instruction,
368                                      HGraph* graph,
369                                      /*out*/ HInstruction** offset) const {
370   HLoopInformation* loop = nullptr;
371   HInductionVarAnalysis::InductionInfo* info = nullptr;
372   HInductionVarAnalysis::InductionInfo* trip = nullptr;
373   if (HasInductionInfo(context, instruction, &loop, &info, &trip)) {
374     if (info->induction_class == HInductionVarAnalysis::kLinear &&
375         !HInductionVarAnalysis::IsNarrowingLinear(info)) {
376       int64_t stride_value = 0;
377       if (IsConstant(info->op_a, kExact, &stride_value) && stride_value == 1) {
378         int64_t off_value = 0;
379         if (IsConstant(info->op_b, kExact, &off_value)) {
380           *offset = graph->GetConstant(info->op_b->type, off_value);
381         } else if (info->op_b->operation == HInductionVarAnalysis::kFetch) {
382           *offset = info->op_b->fetch;
383         } else {
384           return false;
385         }
386         return true;
387       }
388     }
389   }
390   return false;
391 }
392 
GenerateTripCount(HLoopInformation * loop,HGraph * graph,HBasicBlock * block)393 HInstruction* InductionVarRange::GenerateTripCount(HLoopInformation* loop,
394                                                    HGraph* graph,
395                                                    HBasicBlock* block) {
396   HInductionVarAnalysis::InductionInfo *trip =
397       induction_analysis_->LookupInfo(loop, GetLoopControl(loop));
398   if (trip != nullptr && !IsUnsafeTripCount(trip)) {
399     HInstruction* taken_test = nullptr;
400     HInstruction* trip_expr = nullptr;
401     if (IsBodyTripCount(trip)) {
402       if (!GenerateCode(trip->op_b, nullptr, graph, block, &taken_test, false, false)) {
403         return nullptr;
404       }
405     }
406     if (GenerateCode(trip->op_a, nullptr, graph, block, &trip_expr, false, false)) {
407       if (taken_test != nullptr) {
408         HInstruction* zero = graph->GetConstant(trip->type, 0);
409         ArenaAllocator* allocator = graph->GetAllocator();
410         trip_expr = Insert(block, new (allocator) HSelect(taken_test, trip_expr, zero, kNoDexPc));
411       }
412       return trip_expr;
413     }
414   }
415   return nullptr;
416 }
417 
418 //
419 // Private class methods.
420 //
421 
CheckForFiniteAndConstantProps(HLoopInformation * loop,bool * is_constant,int64_t * trip_count) const422 bool InductionVarRange::CheckForFiniteAndConstantProps(HLoopInformation* loop,
423                                                        /*out*/ bool* is_constant,
424                                                        /*out*/ int64_t* trip_count) const {
425   HInductionVarAnalysis::InductionInfo *trip =
426       induction_analysis_->LookupInfo(loop, GetLoopControl(loop));
427   if (trip != nullptr && !IsUnsafeTripCount(trip)) {
428     *is_constant = IsConstant(trip->op_a, kExact, trip_count);
429     return true;
430   }
431   return false;
432 }
433 
IsConstant(HInductionVarAnalysis::InductionInfo * info,ConstantRequest request,int64_t * value) const434 bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info,
435                                    ConstantRequest request,
436                                    /*out*/ int64_t* value) const {
437   if (info != nullptr) {
438     // A direct 32-bit or 64-bit constant fetch. This immediately satisfies
439     // any of the three requests (kExact, kAtMost, and KAtLeast).
440     if (info->induction_class == HInductionVarAnalysis::kInvariant &&
441         info->operation == HInductionVarAnalysis::kFetch) {
442       if (IsInt64AndGet(info->fetch, value)) {
443         return true;
444       }
445     }
446     // Try range analysis on the invariant, only accept a proper range
447     // to avoid arithmetic wrap-around anomalies.
448     Value min_val = GetVal(info, nullptr, /* in_body= */ true, /* is_min= */ true);
449     Value max_val = GetVal(info, nullptr, /* in_body= */ true, /* is_min= */ false);
450     if (IsConstantValue(min_val) &&
451         IsConstantValue(max_val) && min_val.b_constant <= max_val.b_constant) {
452       if ((request == kExact && min_val.b_constant == max_val.b_constant) || request == kAtMost) {
453         *value = max_val.b_constant;
454         return true;
455       } else if (request == kAtLeast) {
456         *value = min_val.b_constant;
457         return true;
458       }
459     }
460   }
461   return false;
462 }
463 
HasInductionInfo(HInstruction * context,HInstruction * instruction,HLoopInformation ** loop,HInductionVarAnalysis::InductionInfo ** info,HInductionVarAnalysis::InductionInfo ** trip) const464 bool InductionVarRange::HasInductionInfo(
465     HInstruction* context,
466     HInstruction* instruction,
467     /*out*/ HLoopInformation** loop,
468     /*out*/ HInductionVarAnalysis::InductionInfo** info,
469     /*out*/ HInductionVarAnalysis::InductionInfo** trip) const {
470   DCHECK(context != nullptr);
471   DCHECK(context->GetBlock() != nullptr);
472   HLoopInformation* lp = context->GetBlock()->GetLoopInformation();  // closest enveloping loop
473   if (lp != nullptr) {
474     HInductionVarAnalysis::InductionInfo* i = induction_analysis_->LookupInfo(lp, instruction);
475     if (i != nullptr) {
476       *loop = lp;
477       *info = i;
478       *trip = induction_analysis_->LookupInfo(lp, GetLoopControl(lp));
479       return true;
480     }
481   }
482   return false;
483 }
484 
IsWellBehavedTripCount(HInductionVarAnalysis::InductionInfo * trip) const485 bool InductionVarRange::IsWellBehavedTripCount(HInductionVarAnalysis::InductionInfo* trip) const {
486   if (trip != nullptr) {
487     // Both bounds that define a trip-count are well-behaved if they either are not defined
488     // in any loop, or are contained in a proper interval. This allows finding the min/max
489     // of an expression by chasing outward.
490     InductionVarRange range(induction_analysis_);
491     HInductionVarAnalysis::InductionInfo* lower = trip->op_b->op_a;
492     HInductionVarAnalysis::InductionInfo* upper = trip->op_b->op_b;
493     int64_t not_used = 0;
494     return (!HasFetchInLoop(lower) || range.IsConstant(lower, kAtLeast, &not_used)) &&
495            (!HasFetchInLoop(upper) || range.IsConstant(upper, kAtLeast, &not_used));
496   }
497   return true;
498 }
499 
HasFetchInLoop(HInductionVarAnalysis::InductionInfo * info) const500 bool InductionVarRange::HasFetchInLoop(HInductionVarAnalysis::InductionInfo* info) const {
501   if (info != nullptr) {
502     if (info->induction_class == HInductionVarAnalysis::kInvariant &&
503         info->operation == HInductionVarAnalysis::kFetch) {
504       return info->fetch->GetBlock()->GetLoopInformation() != nullptr;
505     }
506     return HasFetchInLoop(info->op_a) || HasFetchInLoop(info->op_b);
507   }
508   return false;
509 }
510 
NeedsTripCount(HInductionVarAnalysis::InductionInfo * info,int64_t * stride_value) const511 bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info,
512                                        int64_t* stride_value) const {
513   if (info != nullptr) {
514     if (info->induction_class == HInductionVarAnalysis::kLinear) {
515       return IsConstant(info->op_a, kExact, stride_value);
516     } else if (info->induction_class == HInductionVarAnalysis::kPolynomial) {
517       return NeedsTripCount(info->op_a, stride_value);
518     } else if (info->induction_class == HInductionVarAnalysis::kWrapAround) {
519       return NeedsTripCount(info->op_b, stride_value);
520     }
521   }
522   return false;
523 }
524 
IsBodyTripCount(HInductionVarAnalysis::InductionInfo * trip) const525 bool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const {
526   if (trip != nullptr) {
527     if (trip->induction_class == HInductionVarAnalysis::kInvariant) {
528       return trip->operation == HInductionVarAnalysis::kTripCountInBody ||
529              trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe;
530     }
531   }
532   return false;
533 }
534 
IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo * trip) const535 bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const {
536   if (trip != nullptr) {
537     if (trip->induction_class == HInductionVarAnalysis::kInvariant) {
538       return trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe ||
539              trip->operation == HInductionVarAnalysis::kTripCountInLoopUnsafe;
540     }
541   }
542   return false;
543 }
544 
GetLinear(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip,bool in_body,bool is_min) const545 InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::InductionInfo* info,
546                                                       HInductionVarAnalysis::InductionInfo* trip,
547                                                       bool in_body,
548                                                       bool is_min) const {
549   DCHECK(info != nullptr);
550   DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kLinear);
551   // Detect common situation where an offset inside the trip-count cancels out during range
552   // analysis (finding max a * (TC - 1) + OFFSET for a == 1 and TC = UPPER - OFFSET or finding
553   // min a * (TC - 1) + OFFSET for a == -1 and TC = OFFSET - UPPER) to avoid losing information
554   // with intermediate results that only incorporate single instructions.
555   if (trip != nullptr) {
556     HInductionVarAnalysis::InductionInfo* trip_expr = trip->op_a;
557     if (trip_expr->type == info->type && trip_expr->operation == HInductionVarAnalysis::kSub) {
558       int64_t stride_value = 0;
559       if (IsConstant(info->op_a, kExact, &stride_value)) {
560         if (!is_min && stride_value == 1) {
561           // Test original trip's negative operand (trip_expr->op_b) against offset of induction.
562           if (HInductionVarAnalysis::InductionEqual(trip_expr->op_b, info->op_b)) {
563             // Analyze cancelled trip with just the positive operand (trip_expr->op_a).
564             HInductionVarAnalysis::InductionInfo cancelled_trip(
565                 trip->induction_class,
566                 trip->operation,
567                 trip_expr->op_a,
568                 trip->op_b,
569                 nullptr,
570                 trip->type);
571             return GetVal(&cancelled_trip, trip, in_body, is_min);
572           }
573         } else if (is_min && stride_value == -1) {
574           // Test original trip's positive operand (trip_expr->op_a) against offset of induction.
575           if (HInductionVarAnalysis::InductionEqual(trip_expr->op_a, info->op_b)) {
576             // Analyze cancelled trip with just the negative operand (trip_expr->op_b).
577             HInductionVarAnalysis::InductionInfo neg(
578                 HInductionVarAnalysis::kInvariant,
579                 HInductionVarAnalysis::kNeg,
580                 nullptr,
581                 trip_expr->op_b,
582                 nullptr,
583                 trip->type);
584             HInductionVarAnalysis::InductionInfo cancelled_trip(
585                 trip->induction_class, trip->operation, &neg, trip->op_b, nullptr, trip->type);
586             return SubValue(Value(0), GetVal(&cancelled_trip, trip, in_body, !is_min));
587           }
588         }
589       }
590     }
591   }
592   // General rule of linear induction a * i + b, for normalized 0 <= i < TC.
593   return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min),
594                   GetVal(info->op_b, trip, in_body, is_min));
595 }
596 
GetPolynomial(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip,bool in_body,bool is_min) const597 InductionVarRange::Value InductionVarRange::GetPolynomial(HInductionVarAnalysis::InductionInfo* info,
598                                                           HInductionVarAnalysis::InductionInfo* trip,
599                                                           bool in_body,
600                                                           bool is_min) const {
601   DCHECK(info != nullptr);
602   DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial);
603   int64_t a = 0;
604   int64_t b = 0;
605   if (IsConstant(info->op_a->op_a, kExact, &a) && CanLongValueFitIntoInt(a) && a >= 0 &&
606       IsConstant(info->op_a->op_b, kExact, &b) && CanLongValueFitIntoInt(b) && b >= 0) {
607     // Evaluate bounds on sum_i=0^m-1(a * i + b) + c with a,b >= 0 for
608     // maximum index value m as a * (m * (m-1)) / 2 + b * m + c.
609     Value c = GetVal(info->op_b, trip, in_body, is_min);
610     if (is_min) {
611       return c;
612     } else {
613       Value m = GetVal(trip, trip, in_body, is_min);
614       Value t = DivValue(MulValue(m, SubValue(m, Value(1))), Value(2));
615       Value x = MulValue(Value(a), t);
616       Value y = MulValue(Value(b), m);
617       return AddValue(AddValue(x, y), c);
618     }
619   }
620   return Value();
621 }
622 
GetGeometric(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip,bool in_body,bool is_min) const623 InductionVarRange::Value InductionVarRange::GetGeometric(HInductionVarAnalysis::InductionInfo* info,
624                                                          HInductionVarAnalysis::InductionInfo* trip,
625                                                          bool in_body,
626                                                          bool is_min) const {
627   DCHECK(info != nullptr);
628   DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric);
629   int64_t a = 0;
630   int64_t f = 0;
631   if (IsConstant(info->op_a, kExact, &a) &&
632       CanLongValueFitIntoInt(a) &&
633       IsInt64AndGet(info->fetch, &f) && f >= 1) {
634     // Conservative bounds on a * f^-i + b with f >= 1 can be computed without
635     // trip count. Other forms would require a much more elaborate evaluation.
636     const bool is_min_a = a >= 0 ? is_min : !is_min;
637     if (info->operation == HInductionVarAnalysis::kDiv) {
638       Value b = GetVal(info->op_b, trip, in_body, is_min);
639       return is_min_a ? b : AddValue(Value(a), b);
640     }
641   }
642   return Value();
643 }
644 
GetFetch(HInstruction * instruction,HInductionVarAnalysis::InductionInfo * trip,bool in_body,bool is_min) const645 InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction,
646                                                      HInductionVarAnalysis::InductionInfo* trip,
647                                                      bool in_body,
648                                                      bool is_min) const {
649   // Special case when chasing constants: single instruction that denotes trip count in the
650   // loop-body is minimal 1 and maximal, with safe trip-count, max int,
651   if (chase_hint_ == nullptr && in_body && trip != nullptr && instruction == trip->op_a->fetch) {
652     if (is_min) {
653       return Value(1);
654     } else if (!instruction->IsConstant() && !IsUnsafeTripCount(trip)) {
655       return Value(std::numeric_limits<int32_t>::max());
656     }
657   }
658   // Unless at a constant or hint, chase the instruction a bit deeper into the HIR tree, so that
659   // it becomes more likely range analysis will compare the same instructions as terminal nodes.
660   int64_t value;
661   if (IsInt64AndGet(instruction, &value) && CanLongValueFitIntoInt(value)) {
662     // Proper constant reveals best information.
663     return Value(static_cast<int32_t>(value));
664   } else if (instruction == chase_hint_) {
665     // At hint, fetch is represented by itself.
666     return Value(instruction, 1, 0);
667   } else if (instruction->IsAdd()) {
668     // Incorporate suitable constants in the chased value.
669     if (IsInt64AndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) {
670       return AddValue(Value(static_cast<int32_t>(value)),
671                       GetFetch(instruction->InputAt(1), trip, in_body, is_min));
672     } else if (IsInt64AndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) {
673       return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min),
674                       Value(static_cast<int32_t>(value)));
675     }
676   } else if (instruction->IsSub()) {
677     // Incorporate suitable constants in the chased value.
678     if (IsInt64AndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) {
679       return SubValue(Value(static_cast<int32_t>(value)),
680                       GetFetch(instruction->InputAt(1), trip, in_body, !is_min));
681     } else if (IsInt64AndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) {
682       return SubValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min),
683                       Value(static_cast<int32_t>(value)));
684     }
685   } else if (instruction->IsArrayLength()) {
686     // Exploit length properties when chasing constants or chase into a new array declaration.
687     if (chase_hint_ == nullptr) {
688       return is_min ? Value(0) : Value(std::numeric_limits<int32_t>::max());
689     } else if (instruction->InputAt(0)->IsNewArray()) {
690       return GetFetch(instruction->InputAt(0)->AsNewArray()->GetLength(), trip, in_body, is_min);
691     }
692   } else if (instruction->IsTypeConversion()) {
693     // Since analysis is 32-bit (or narrower), chase beyond widening along the path.
694     // For example, this discovers the length in: for (long i = 0; i < a.length; i++);
695     if (instruction->AsTypeConversion()->GetInputType() == DataType::Type::kInt32 &&
696         instruction->AsTypeConversion()->GetResultType() == DataType::Type::kInt64) {
697       return GetFetch(instruction->InputAt(0), trip, in_body, is_min);
698     }
699   }
700   // Chase an invariant fetch that is defined by an outer loop if the trip-count used
701   // so far is well-behaved in both bounds and the next trip-count is safe.
702   // Example:
703   //   for (int i = 0; i <= 100; i++)  // safe
704   //     for (int j = 0; j <= i; j++)  // well-behaved
705   //       j is in range [0, i  ] (if i is chase hint)
706   //         or in range [0, 100] (otherwise)
707   HLoopInformation* next_loop = nullptr;
708   HInductionVarAnalysis::InductionInfo* next_info = nullptr;
709   HInductionVarAnalysis::InductionInfo* next_trip = nullptr;
710   bool next_in_body = true;  // inner loop is always in body of outer loop
711   if (HasInductionInfo(instruction, instruction, &next_loop, &next_info, &next_trip) &&
712       IsWellBehavedTripCount(trip) &&
713       !IsUnsafeTripCount(next_trip)) {
714     return GetVal(next_info, next_trip, next_in_body, is_min);
715   }
716   // Fetch is represented by itself.
717   return Value(instruction, 1, 0);
718 }
719 
GetVal(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip,bool in_body,bool is_min) const720 InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::InductionInfo* info,
721                                                    HInductionVarAnalysis::InductionInfo* trip,
722                                                    bool in_body,
723                                                    bool is_min) const {
724   if (info != nullptr) {
725     switch (info->induction_class) {
726       case HInductionVarAnalysis::kInvariant:
727         // Invariants.
728         switch (info->operation) {
729           case HInductionVarAnalysis::kAdd:
730             return AddValue(GetVal(info->op_a, trip, in_body, is_min),
731                             GetVal(info->op_b, trip, in_body, is_min));
732           case HInductionVarAnalysis::kSub:  // second reversed!
733             return SubValue(GetVal(info->op_a, trip, in_body, is_min),
734                             GetVal(info->op_b, trip, in_body, !is_min));
735           case HInductionVarAnalysis::kNeg:  // second reversed!
736             return SubValue(Value(0),
737                             GetVal(info->op_b, trip, in_body, !is_min));
738           case HInductionVarAnalysis::kMul:
739             return GetMul(info->op_a, info->op_b, trip, in_body, is_min);
740           case HInductionVarAnalysis::kDiv:
741             return GetDiv(info->op_a, info->op_b, trip, in_body, is_min);
742           case HInductionVarAnalysis::kRem:
743             return GetRem(info->op_a, info->op_b);
744           case HInductionVarAnalysis::kXor:
745             return GetXor(info->op_a, info->op_b);
746           case HInductionVarAnalysis::kFetch:
747             return GetFetch(info->fetch, trip, in_body, is_min);
748           case HInductionVarAnalysis::kTripCountInLoop:
749           case HInductionVarAnalysis::kTripCountInLoopUnsafe:
750             if (!in_body && !is_min) {  // one extra!
751               return GetVal(info->op_a, trip, in_body, is_min);
752             }
753             FALLTHROUGH_INTENDED;
754           case HInductionVarAnalysis::kTripCountInBody:
755           case HInductionVarAnalysis::kTripCountInBodyUnsafe:
756             if (is_min) {
757               return Value(0);
758             } else if (in_body) {
759               return SubValue(GetVal(info->op_a, trip, in_body, is_min), Value(1));
760             }
761             break;
762           default:
763             break;
764         }
765         break;
766       case HInductionVarAnalysis::kLinear:
767         return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type);
768       case HInductionVarAnalysis::kPolynomial:
769         return GetPolynomial(info, trip, in_body, is_min);
770       case HInductionVarAnalysis::kGeometric:
771         return GetGeometric(info, trip, in_body, is_min);
772       case HInductionVarAnalysis::kWrapAround:
773       case HInductionVarAnalysis::kPeriodic:
774         return MergeVal(GetVal(info->op_a, trip, in_body, is_min),
775                         GetVal(info->op_b, trip, in_body, is_min), is_min);
776     }
777   }
778   return Value();
779 }
780 
GetMul(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2,HInductionVarAnalysis::InductionInfo * trip,bool in_body,bool is_min) const781 InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1,
782                                                    HInductionVarAnalysis::InductionInfo* info2,
783                                                    HInductionVarAnalysis::InductionInfo* trip,
784                                                    bool in_body,
785                                                    bool is_min) const {
786   // Constant times range.
787   int64_t value = 0;
788   if (IsConstant(info1, kExact, &value)) {
789     return MulRangeAndConstant(value, info2, trip, in_body, is_min);
790   } else if (IsConstant(info2, kExact, &value)) {
791     return MulRangeAndConstant(value, info1, trip, in_body, is_min);
792   }
793   // Interval ranges.
794   Value v1_min = GetVal(info1, trip, in_body, /* is_min= */ true);
795   Value v1_max = GetVal(info1, trip, in_body, /* is_min= */ false);
796   Value v2_min = GetVal(info2, trip, in_body, /* is_min= */ true);
797   Value v2_max = GetVal(info2, trip, in_body, /* is_min= */ false);
798   // Positive range vs. positive or negative range.
799   if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) {
800     if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
801       return is_min ? MulValue(v1_min, v2_min) : MulValue(v1_max, v2_max);
802     } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) {
803       return is_min ? MulValue(v1_max, v2_min) : MulValue(v1_min, v2_max);
804     }
805   }
806   // Negative range vs. positive or negative range.
807   if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) {
808     if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
809       return is_min ? MulValue(v1_min, v2_max) : MulValue(v1_max, v2_min);
810     } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) {
811       return is_min ? MulValue(v1_max, v2_max) : MulValue(v1_min, v2_min);
812     }
813   }
814   return Value();
815 }
816 
GetDiv(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2,HInductionVarAnalysis::InductionInfo * trip,bool in_body,bool is_min) const817 InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::InductionInfo* info1,
818                                                    HInductionVarAnalysis::InductionInfo* info2,
819                                                    HInductionVarAnalysis::InductionInfo* trip,
820                                                    bool in_body,
821                                                    bool is_min) const {
822   // Range divided by constant.
823   int64_t value = 0;
824   if (IsConstant(info2, kExact, &value)) {
825     return DivRangeAndConstant(value, info1, trip, in_body, is_min);
826   }
827   // Interval ranges.
828   Value v1_min = GetVal(info1, trip, in_body, /* is_min= */ true);
829   Value v1_max = GetVal(info1, trip, in_body, /* is_min= */ false);
830   Value v2_min = GetVal(info2, trip, in_body, /* is_min= */ true);
831   Value v2_max = GetVal(info2, trip, in_body, /* is_min= */ false);
832   // Positive range vs. positive or negative range.
833   if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) {
834     if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
835       return is_min ? DivValue(v1_min, v2_max) : DivValue(v1_max, v2_min);
836     } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) {
837       return is_min ? DivValue(v1_max, v2_max) : DivValue(v1_min, v2_min);
838     }
839   }
840   // Negative range vs. positive or negative range.
841   if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) {
842     if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
843       return is_min ? DivValue(v1_min, v2_min) : DivValue(v1_max, v2_max);
844     } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) {
845       return is_min ? DivValue(v1_max, v2_min) : DivValue(v1_min, v2_max);
846     }
847   }
848   return Value();
849 }
850 
GetRem(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2) const851 InductionVarRange::Value InductionVarRange::GetRem(
852     HInductionVarAnalysis::InductionInfo* info1,
853     HInductionVarAnalysis::InductionInfo* info2) const {
854   int64_t v1 = 0;
855   int64_t v2 = 0;
856   // Only accept exact values.
857   if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2) && v2 != 0) {
858     int64_t value = v1 % v2;
859     if (CanLongValueFitIntoInt(value)) {
860       return Value(static_cast<int32_t>(value));
861     }
862   }
863   return Value();
864 }
865 
GetXor(HInductionVarAnalysis::InductionInfo * info1,HInductionVarAnalysis::InductionInfo * info2) const866 InductionVarRange::Value InductionVarRange::GetXor(
867     HInductionVarAnalysis::InductionInfo* info1,
868     HInductionVarAnalysis::InductionInfo* info2) const {
869   int64_t v1 = 0;
870   int64_t v2 = 0;
871   // Only accept exact values.
872   if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2)) {
873     int64_t value = v1 ^ v2;
874     if (CanLongValueFitIntoInt(value)) {
875       return Value(static_cast<int32_t>(value));
876     }
877   }
878   return Value();
879 }
880 
MulRangeAndConstant(int64_t value,HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip,bool in_body,bool is_min) const881 InductionVarRange::Value InductionVarRange::MulRangeAndConstant(
882     int64_t value,
883     HInductionVarAnalysis::InductionInfo* info,
884     HInductionVarAnalysis::InductionInfo* trip,
885     bool in_body,
886     bool is_min) const {
887   if (CanLongValueFitIntoInt(value)) {
888     Value c(static_cast<int32_t>(value));
889     return MulValue(GetVal(info, trip, in_body, is_min == value >= 0), c);
890   }
891   return Value();
892 }
893 
DivRangeAndConstant(int64_t value,HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip,bool in_body,bool is_min) const894 InductionVarRange::Value InductionVarRange::DivRangeAndConstant(
895     int64_t value,
896     HInductionVarAnalysis::InductionInfo* info,
897     HInductionVarAnalysis::InductionInfo* trip,
898     bool in_body,
899     bool is_min) const {
900   if (CanLongValueFitIntoInt(value)) {
901     Value c(static_cast<int32_t>(value));
902     return DivValue(GetVal(info, trip, in_body, is_min == value >= 0), c);
903   }
904   return Value();
905 }
906 
AddValue(Value v1,Value v2) const907 InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) const {
908   if (v1.is_known && v2.is_known && IsSafeAdd(v1.b_constant, v2.b_constant)) {
909     int32_t b = v1.b_constant + v2.b_constant;
910     if (v1.a_constant == 0) {
911       return Value(v2.instruction, v2.a_constant, b);
912     } else if (v2.a_constant == 0) {
913       return Value(v1.instruction, v1.a_constant, b);
914     } else if (v1.instruction == v2.instruction && IsSafeAdd(v1.a_constant, v2.a_constant)) {
915       return Value(v1.instruction, v1.a_constant + v2.a_constant, b);
916     }
917   }
918   return Value();
919 }
920 
SubValue(Value v1,Value v2) const921 InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2) const {
922   if (v1.is_known && v2.is_known && IsSafeSub(v1.b_constant, v2.b_constant)) {
923     int32_t b = v1.b_constant - v2.b_constant;
924     if (v1.a_constant == 0 && IsSafeSub(0, v2.a_constant)) {
925       return Value(v2.instruction, -v2.a_constant, b);
926     } else if (v2.a_constant == 0) {
927       return Value(v1.instruction, v1.a_constant, b);
928     } else if (v1.instruction == v2.instruction && IsSafeSub(v1.a_constant, v2.a_constant)) {
929       return Value(v1.instruction, v1.a_constant - v2.a_constant, b);
930     }
931   }
932   return Value();
933 }
934 
MulValue(Value v1,Value v2) const935 InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2) const {
936   if (v1.is_known && v2.is_known) {
937     if (v1.a_constant == 0) {
938       if (IsSafeMul(v1.b_constant, v2.a_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) {
939         return Value(v2.instruction, v1.b_constant * v2.a_constant, v1.b_constant * v2.b_constant);
940       }
941     } else if (v2.a_constant == 0) {
942       if (IsSafeMul(v1.a_constant, v2.b_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) {
943         return Value(v1.instruction, v1.a_constant * v2.b_constant, v1.b_constant * v2.b_constant);
944       }
945     }
946   }
947   return Value();
948 }
949 
DivValue(Value v1,Value v2) const950 InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2) const {
951   if (v1.is_known && v2.is_known && v1.a_constant == 0 && v2.a_constant == 0) {
952     if (IsSafeDiv(v1.b_constant, v2.b_constant)) {
953       return Value(v1.b_constant / v2.b_constant);
954     }
955   }
956   return Value();
957 }
958 
MergeVal(Value v1,Value v2,bool is_min) const959 InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is_min) const {
960   if (v1.is_known && v2.is_known) {
961     if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) {
962       return Value(v1.instruction, v1.a_constant,
963                    is_min ? std::min(v1.b_constant, v2.b_constant)
964                           : std::max(v1.b_constant, v2.b_constant));
965     }
966   }
967   return Value();
968 }
969 
GenerateRangeOrLastValue(HInstruction * context,HInstruction * instruction,bool is_last_value,HGraph * graph,HBasicBlock * block,HInstruction ** lower,HInstruction ** upper,HInstruction ** taken_test,int64_t * stride_value,bool * needs_finite_test,bool * needs_taken_test) const970 bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context,
971                                                  HInstruction* instruction,
972                                                  bool is_last_value,
973                                                  HGraph* graph,
974                                                  HBasicBlock* block,
975                                                  /*out*/HInstruction** lower,
976                                                  /*out*/HInstruction** upper,
977                                                  /*out*/HInstruction** taken_test,
978                                                  /*out*/int64_t* stride_value,
979                                                  /*out*/bool* needs_finite_test,
980                                                  /*out*/bool* needs_taken_test) const {
981   HLoopInformation* loop = nullptr;
982   HInductionVarAnalysis::InductionInfo* info = nullptr;
983   HInductionVarAnalysis::InductionInfo* trip = nullptr;
984   if (!HasInductionInfo(context, instruction, &loop, &info, &trip) || trip == nullptr) {
985     return false;  // codegen needs all information, including tripcount
986   }
987   // Determine what tests are needed. A finite test is needed if the evaluation code uses the
988   // trip-count and the loop maybe unsafe (because in such cases, the index could "overshoot"
989   // the computed range). A taken test is needed for any unknown trip-count, even if evaluation
990   // code does not use the trip-count explicitly (since there could be an implicit relation
991   // between e.g. an invariant subscript and a not-taken condition).
992   bool in_body = context->GetBlock() != loop->GetHeader();
993   *stride_value = 0;
994   *needs_finite_test = NeedsTripCount(info, stride_value) && IsUnsafeTripCount(trip);
995   *needs_taken_test = IsBodyTripCount(trip);
996   // Handle last value request.
997   if (is_last_value) {
998     DCHECK(!in_body);
999     switch (info->induction_class) {
1000       case HInductionVarAnalysis::kLinear:
1001         if (*stride_value > 0) {
1002           lower = nullptr;
1003         } else {
1004           upper = nullptr;
1005         }
1006         break;
1007       case HInductionVarAnalysis::kPolynomial:
1008         return GenerateLastValuePolynomial(info, trip, graph, block, lower);
1009       case HInductionVarAnalysis::kGeometric:
1010         return GenerateLastValueGeometric(info, trip, graph, block, lower);
1011       case HInductionVarAnalysis::kWrapAround:
1012         return GenerateLastValueWrapAround(info, trip, graph, block, lower);
1013       case HInductionVarAnalysis::kPeriodic:
1014         return GenerateLastValuePeriodic(info, trip, graph, block, lower, needs_taken_test);
1015       default:
1016         return false;
1017     }
1018   }
1019   // Code generation for taken test: generate the code when requested or otherwise analyze
1020   // if code generation is feasible when taken test is needed.
1021   if (taken_test != nullptr) {
1022     return GenerateCode(trip->op_b, nullptr, graph, block, taken_test, in_body, /* is_min= */ false);
1023   } else if (*needs_taken_test) {
1024     if (!GenerateCode(
1025         trip->op_b, nullptr, nullptr, nullptr, nullptr, in_body, /* is_min= */ false)) {
1026       return false;
1027     }
1028   }
1029   // Code generation for lower and upper.
1030   return
1031       // Success on lower if invariant (not set), or code can be generated.
1032       ((info->induction_class == HInductionVarAnalysis::kInvariant) ||
1033           GenerateCode(info, trip, graph, block, lower, in_body, /* is_min= */ true)) &&
1034       // And success on upper.
1035       GenerateCode(info, trip, graph, block, upper, in_body, /* is_min= */ false);
1036 }
1037 
GenerateLastValuePolynomial(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip,HGraph * graph,HBasicBlock * block,HInstruction ** result) const1038 bool InductionVarRange::GenerateLastValuePolynomial(HInductionVarAnalysis::InductionInfo* info,
1039                                                     HInductionVarAnalysis::InductionInfo* trip,
1040                                                     HGraph* graph,
1041                                                     HBasicBlock* block,
1042                                                     /*out*/HInstruction** result) const {
1043   DCHECK(info != nullptr);
1044   DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial);
1045   // Detect known coefficients and trip count (always taken).
1046   int64_t a = 0;
1047   int64_t b = 0;
1048   int64_t m = 0;
1049   if (IsConstant(info->op_a->op_a, kExact, &a) &&
1050       IsConstant(info->op_a->op_b, kExact, &b) &&
1051       IsConstant(trip->op_a, kExact, &m) && m >= 1) {
1052     // Evaluate bounds on sum_i=0^m-1(a * i + b) + c for known
1053     // maximum index value m as a * (m * (m-1)) / 2 + b * m + c.
1054     HInstruction* c = nullptr;
1055     if (GenerateCode(info->op_b, nullptr, graph, block, graph ? &c : nullptr, false, false)) {
1056       if (graph != nullptr) {
1057         DataType::Type type = info->type;
1058         int64_t sum = a * ((m * (m - 1)) / 2) + b * m;
1059         if (type != DataType::Type::kInt64) {
1060           sum = static_cast<int32_t>(sum);  // okay to truncate
1061         }
1062         *result =
1063             Insert(block, new (graph->GetAllocator()) HAdd(type, graph->GetConstant(type, sum), c));
1064       }
1065       return true;
1066     }
1067   }
1068   return false;
1069 }
1070 
GenerateLastValueGeometric(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip,HGraph * graph,HBasicBlock * block,HInstruction ** result) const1071 bool InductionVarRange::GenerateLastValueGeometric(HInductionVarAnalysis::InductionInfo* info,
1072                                                    HInductionVarAnalysis::InductionInfo* trip,
1073                                                    HGraph* graph,
1074                                                    HBasicBlock* block,
1075                                                    /*out*/HInstruction** result) const {
1076   DCHECK(info != nullptr);
1077   DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric);
1078   // Detect known base and trip count (always taken).
1079   int64_t f = 0;
1080   int64_t m = 0;
1081   if (IsInt64AndGet(info->fetch, &f) && f >= 1 && IsConstant(trip->op_a, kExact, &m) && m >= 1) {
1082     HInstruction* opa = nullptr;
1083     HInstruction* opb = nullptr;
1084     if (GenerateCode(info->op_a, nullptr, graph, block, &opa, false, false) &&
1085         GenerateCode(info->op_b, nullptr, graph, block, &opb, false, false)) {
1086       if (graph != nullptr) {
1087         DataType::Type type = info->type;
1088         // Compute f ^ m for known maximum index value m.
1089         bool overflow = false;
1090         int64_t fpow = IntPow(f, m, &overflow);
1091         if (info->operation == HInductionVarAnalysis::kDiv) {
1092           // For division, any overflow truncates to zero.
1093           if (overflow || (type != DataType::Type::kInt64 && !CanLongValueFitIntoInt(fpow))) {
1094             fpow = 0;
1095           }
1096         } else if (type != DataType::Type::kInt64) {
1097           // For multiplication, okay to truncate to required precision.
1098           DCHECK(info->operation == HInductionVarAnalysis::kMul);
1099           fpow = static_cast<int32_t>(fpow);
1100         }
1101         // Generate code.
1102         if (fpow == 0) {
1103           // Special case: repeated mul/div always yields zero.
1104           *result = graph->GetConstant(type, 0);
1105         } else {
1106           // Last value: a * f ^ m + b or a * f ^ -m + b.
1107           HInstruction* e = nullptr;
1108           ArenaAllocator* allocator = graph->GetAllocator();
1109           if (info->operation == HInductionVarAnalysis::kMul) {
1110             e = new (allocator) HMul(type, opa, graph->GetConstant(type, fpow));
1111           } else {
1112             e = new (allocator) HDiv(type, opa, graph->GetConstant(type, fpow), kNoDexPc);
1113           }
1114           *result = Insert(block, new (allocator) HAdd(type, Insert(block, e), opb));
1115         }
1116       }
1117       return true;
1118     }
1119   }
1120   return false;
1121 }
1122 
GenerateLastValueWrapAround(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip,HGraph * graph,HBasicBlock * block,HInstruction ** result) const1123 bool InductionVarRange::GenerateLastValueWrapAround(HInductionVarAnalysis::InductionInfo* info,
1124                                                     HInductionVarAnalysis::InductionInfo* trip,
1125                                                     HGraph* graph,
1126                                                     HBasicBlock* block,
1127                                                     /*out*/HInstruction** result) const {
1128   DCHECK(info != nullptr);
1129   DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kWrapAround);
1130   // Count depth.
1131   int32_t depth = 0;
1132   for (; info->induction_class == HInductionVarAnalysis::kWrapAround;
1133        info = info->op_b, ++depth) {}
1134   // Handle wrap(x, wrap(.., y)) if trip count reaches an invariant at end.
1135   // TODO: generalize, but be careful to adjust the terminal.
1136   int64_t m = 0;
1137   if (info->induction_class == HInductionVarAnalysis::kInvariant &&
1138       IsConstant(trip->op_a, kExact, &m) && m >= depth) {
1139     return GenerateCode(info, nullptr, graph, block, result, false, false);
1140   }
1141   return false;
1142 }
1143 
GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip,HGraph * graph,HBasicBlock * block,HInstruction ** result,bool * needs_taken_test) const1144 bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info,
1145                                                   HInductionVarAnalysis::InductionInfo* trip,
1146                                                   HGraph* graph,
1147                                                   HBasicBlock* block,
1148                                                   /*out*/HInstruction** result,
1149                                                   /*out*/bool* needs_taken_test) const {
1150   DCHECK(info != nullptr);
1151   DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPeriodic);
1152   // Count period and detect all-invariants.
1153   int64_t period = 1;
1154   bool all_invariants = true;
1155   HInductionVarAnalysis::InductionInfo* p = info;
1156   for (; p->induction_class == HInductionVarAnalysis::kPeriodic; p = p->op_b, ++period) {
1157     DCHECK_EQ(p->op_a->induction_class, HInductionVarAnalysis::kInvariant);
1158     if (p->op_a->operation != HInductionVarAnalysis::kFetch) {
1159       all_invariants = false;
1160     }
1161   }
1162   DCHECK_EQ(p->induction_class, HInductionVarAnalysis::kInvariant);
1163   if (p->operation != HInductionVarAnalysis::kFetch) {
1164     all_invariants = false;
1165   }
1166   // Don't rely on FP arithmetic to be precise, unless the full period
1167   // consist of pre-computed expressions only.
1168   if (info->type == DataType::Type::kFloat32 || info->type == DataType::Type::kFloat64) {
1169     if (!all_invariants) {
1170       return false;
1171     }
1172   }
1173   // Handle any periodic(x, periodic(.., y)) for known maximum index value m.
1174   int64_t m = 0;
1175   if (IsConstant(trip->op_a, kExact, &m) && m >= 1) {
1176     int64_t li = m % period;
1177     for (int64_t i = 0; i < li; info = info->op_b, i++) {}
1178     if (info->induction_class == HInductionVarAnalysis::kPeriodic) {
1179       info = info->op_a;
1180     }
1181     return GenerateCode(info, nullptr, graph, block, result, false, false);
1182   }
1183   // Handle periodic(x, y) using even/odd-select on trip count. Enter trip count expression
1184   // directly to obtain the maximum index value t even if taken test is needed.
1185   HInstruction* x = nullptr;
1186   HInstruction* y = nullptr;
1187   HInstruction* t = nullptr;
1188   if (period == 2 &&
1189       GenerateCode(info->op_a, nullptr, graph, block, graph ? &x : nullptr, false, false) &&
1190       GenerateCode(info->op_b, nullptr, graph, block, graph ? &y : nullptr, false, false) &&
1191       GenerateCode(trip->op_a, nullptr, graph, block, graph ? &t : nullptr, false, false)) {
1192     // During actual code generation (graph != nullptr), generate is_even ? x : y.
1193     if (graph != nullptr) {
1194       DataType::Type type = trip->type;
1195       ArenaAllocator* allocator = graph->GetAllocator();
1196       HInstruction* msk =
1197           Insert(block, new (allocator) HAnd(type, t, graph->GetConstant(type, 1)));
1198       HInstruction* is_even =
1199           Insert(block, new (allocator) HEqual(msk, graph->GetConstant(type, 0), kNoDexPc));
1200       *result = Insert(block, new (graph->GetAllocator()) HSelect(is_even, x, y, kNoDexPc));
1201     }
1202     // Guard select with taken test if needed.
1203     if (*needs_taken_test) {
1204       HInstruction* is_taken = nullptr;
1205       if (GenerateCode(trip->op_b, nullptr, graph, block, graph ? &is_taken : nullptr, false, false)) {
1206         if (graph != nullptr) {
1207           ArenaAllocator* allocator = graph->GetAllocator();
1208           *result = Insert(block, new (allocator) HSelect(is_taken, *result, x, kNoDexPc));
1209         }
1210         *needs_taken_test = false;  // taken care of
1211       } else {
1212         return false;
1213       }
1214     }
1215     return true;
1216   }
1217   return false;
1218 }
1219 
GenerateCode(HInductionVarAnalysis::InductionInfo * info,HInductionVarAnalysis::InductionInfo * trip,HGraph * graph,HBasicBlock * block,HInstruction ** result,bool in_body,bool is_min) const1220 bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
1221                                      HInductionVarAnalysis::InductionInfo* trip,
1222                                      HGraph* graph,  // when set, code is generated
1223                                      HBasicBlock* block,
1224                                      /*out*/HInstruction** result,
1225                                      bool in_body,
1226                                      bool is_min) const {
1227   if (info != nullptr) {
1228     // If during codegen, the result is not needed (nullptr), simply return success.
1229     if (graph != nullptr && result == nullptr) {
1230       return true;
1231     }
1232     // Handle current operation.
1233     DataType::Type type = info->type;
1234     HInstruction* opa = nullptr;
1235     HInstruction* opb = nullptr;
1236     switch (info->induction_class) {
1237       case HInductionVarAnalysis::kInvariant:
1238         // Invariants (note that since invariants only have other invariants as
1239         // sub expressions, viz. no induction, there is no need to adjust is_min).
1240         switch (info->operation) {
1241           case HInductionVarAnalysis::kAdd:
1242           case HInductionVarAnalysis::kSub:
1243           case HInductionVarAnalysis::kMul:
1244           case HInductionVarAnalysis::kDiv:
1245           case HInductionVarAnalysis::kRem:
1246           case HInductionVarAnalysis::kXor:
1247           case HInductionVarAnalysis::kLT:
1248           case HInductionVarAnalysis::kLE:
1249           case HInductionVarAnalysis::kGT:
1250           case HInductionVarAnalysis::kGE:
1251             if (GenerateCode(info->op_a, trip, graph, block, &opa, in_body, is_min) &&
1252                 GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
1253               if (graph != nullptr) {
1254                 HInstruction* operation = nullptr;
1255                 switch (info->operation) {
1256                   case HInductionVarAnalysis::kAdd:
1257                     operation = new (graph->GetAllocator()) HAdd(type, opa, opb); break;
1258                   case HInductionVarAnalysis::kSub:
1259                     operation = new (graph->GetAllocator()) HSub(type, opa, opb); break;
1260                   case HInductionVarAnalysis::kMul:
1261                     operation = new (graph->GetAllocator()) HMul(type, opa, opb, kNoDexPc); break;
1262                   case HInductionVarAnalysis::kDiv:
1263                     operation = new (graph->GetAllocator()) HDiv(type, opa, opb, kNoDexPc); break;
1264                   case HInductionVarAnalysis::kRem:
1265                     operation = new (graph->GetAllocator()) HRem(type, opa, opb, kNoDexPc); break;
1266                   case HInductionVarAnalysis::kXor:
1267                     operation = new (graph->GetAllocator()) HXor(type, opa, opb); break;
1268                   case HInductionVarAnalysis::kLT:
1269                     operation = new (graph->GetAllocator()) HLessThan(opa, opb); break;
1270                   case HInductionVarAnalysis::kLE:
1271                     operation = new (graph->GetAllocator()) HLessThanOrEqual(opa, opb); break;
1272                   case HInductionVarAnalysis::kGT:
1273                     operation = new (graph->GetAllocator()) HGreaterThan(opa, opb); break;
1274                   case HInductionVarAnalysis::kGE:
1275                     operation = new (graph->GetAllocator()) HGreaterThanOrEqual(opa, opb); break;
1276                   default:
1277                     LOG(FATAL) << "unknown operation";
1278                 }
1279                 *result = Insert(block, operation);
1280               }
1281               return true;
1282             }
1283             break;
1284           case HInductionVarAnalysis::kNeg:
1285             if (GenerateCode(info->op_b, trip, graph, block, &opb, in_body, !is_min)) {
1286               if (graph != nullptr) {
1287                 *result = Insert(block, new (graph->GetAllocator()) HNeg(type, opb));
1288               }
1289               return true;
1290             }
1291             break;
1292           case HInductionVarAnalysis::kFetch:
1293             if (graph != nullptr) {
1294               *result = info->fetch;  // already in HIR
1295             }
1296             return true;
1297           case HInductionVarAnalysis::kTripCountInLoop:
1298           case HInductionVarAnalysis::kTripCountInLoopUnsafe:
1299             if (!in_body && !is_min) {  // one extra!
1300               return GenerateCode(info->op_a, trip, graph, block, result, in_body, is_min);
1301             }
1302             FALLTHROUGH_INTENDED;
1303           case HInductionVarAnalysis::kTripCountInBody:
1304           case HInductionVarAnalysis::kTripCountInBodyUnsafe:
1305             if (is_min) {
1306               if (graph != nullptr) {
1307                 *result = graph->GetConstant(type, 0);
1308               }
1309               return true;
1310             } else if (in_body) {
1311               if (GenerateCode(info->op_a, trip, graph, block, &opb, in_body, is_min)) {
1312                 if (graph != nullptr) {
1313                   ArenaAllocator* allocator = graph->GetAllocator();
1314                   *result =
1315                       Insert(block, new (allocator) HSub(type, opb, graph->GetConstant(type, 1)));
1316                 }
1317                 return true;
1318               }
1319             }
1320             break;
1321           case HInductionVarAnalysis::kNop:
1322             LOG(FATAL) << "unexpected invariant nop";
1323         }  // switch invariant operation
1324         break;
1325       case HInductionVarAnalysis::kLinear: {
1326         // Linear induction a * i + b, for normalized 0 <= i < TC. For ranges, this should
1327         // be restricted to a unit stride to avoid arithmetic wrap-around situations that
1328         // are harder to guard against. For a last value, requesting min/max based on any
1329         // known stride yields right value. Always avoid any narrowing linear induction or
1330         // any type mismatch between the linear induction and the trip count expression.
1331         // TODO: careful runtime type conversions could generalize this latter restriction.
1332         if (!HInductionVarAnalysis::IsNarrowingLinear(info) && trip->type == type) {
1333           int64_t stride_value = 0;
1334           if (IsConstant(info->op_a, kExact, &stride_value) &&
1335               CanLongValueFitIntoInt(stride_value)) {
1336             const bool is_min_a = stride_value >= 0 ? is_min : !is_min;
1337             if (GenerateCode(trip,       trip, graph, block, &opa, in_body, is_min_a) &&
1338                 GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
1339               if (graph != nullptr) {
1340                 ArenaAllocator* allocator = graph->GetAllocator();
1341                 HInstruction* oper;
1342                 if (stride_value == 1) {
1343                   oper = new (allocator) HAdd(type, opa, opb);
1344                 } else if (stride_value == -1) {
1345                   oper = new (graph->GetAllocator()) HSub(type, opb, opa);
1346                 } else {
1347                   HInstruction* mul =
1348                       new (allocator) HMul(type, graph->GetConstant(type, stride_value), opa);
1349                   oper = new (allocator) HAdd(type, Insert(block, mul), opb);
1350                 }
1351                 *result = Insert(block, oper);
1352               }
1353               return true;
1354             }
1355           }
1356         }
1357         break;
1358       }
1359       case HInductionVarAnalysis::kPolynomial:
1360       case HInductionVarAnalysis::kGeometric:
1361         break;
1362       case HInductionVarAnalysis::kWrapAround:
1363       case HInductionVarAnalysis::kPeriodic: {
1364         // Wrap-around and periodic inductions are restricted to constants only, so that extreme
1365         // values are easy to test at runtime without complications of arithmetic wrap-around.
1366         Value extreme = GetVal(info, trip, in_body, is_min);
1367         if (IsConstantValue(extreme)) {
1368           if (graph != nullptr) {
1369             *result = graph->GetConstant(type, extreme.b_constant);
1370           }
1371           return true;
1372         }
1373         break;
1374       }
1375     }  // switch induction class
1376   }
1377   return false;
1378 }
1379 
ReplaceInduction(HInductionVarAnalysis::InductionInfo * info,HInstruction * fetch,HInstruction * replacement)1380 void InductionVarRange::ReplaceInduction(HInductionVarAnalysis::InductionInfo* info,
1381                                          HInstruction* fetch,
1382                                          HInstruction* replacement) {
1383   if (info != nullptr) {
1384     if (info->induction_class == HInductionVarAnalysis::kInvariant &&
1385         info->operation == HInductionVarAnalysis::kFetch &&
1386         info->fetch == fetch) {
1387       info->fetch = replacement;
1388     }
1389     ReplaceInduction(info->op_a, fetch, replacement);
1390     ReplaceInduction(info->op_b, fetch, replacement);
1391   }
1392 }
1393 
1394 }  // namespace art
1395