diff options
Diffstat (limited to 'compiler/optimizing/induction_var_range.cc')
| -rw-r--r-- | compiler/optimizing/induction_var_range.cc | 511 |
1 files changed, 333 insertions, 178 deletions
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc index 72c2064d89..ad3d1a9321 100644 --- a/compiler/optimizing/induction_var_range.cc +++ b/compiler/optimizing/induction_var_range.cc @@ -150,11 +150,44 @@ static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) { } /** Obtains loop's control instruction. */ -static HInstruction* GetLoopControl(HLoopInformation* loop) { +static HInstruction* GetLoopControl(const HLoopInformation* loop) { DCHECK(loop != nullptr); return loop->GetHeader()->GetLastInstruction(); } +/** Determines whether the `context` is in the body of the `loop`. */ +static bool IsContextInBody(const HBasicBlock* context, const HLoopInformation* loop) { + DCHECK(loop != nullptr); + // We're currently classifying trip count only for the exit condition from loop header. + // All other blocks in the loop are considered loop body. + return context != loop->GetHeader() && loop->Contains(*context); +} + +/** Determines whether to use the full trip count for given `context`, `loop` and `is_min`. */ +bool UseFullTripCount(const HBasicBlock* context, const HLoopInformation* loop, bool is_min) { + // We're currently classifying trip count only for the exit condition from loop header. + // So, we should call this helper function only if the loop control is an `HIf` with + // one edge leaving the loop. The loop header is the only block that's both inside + // the loop and not in the loop body. + DCHECK(GetLoopControl(loop)->IsIf()); + DCHECK_NE(loop->Contains(*GetLoopControl(loop)->AsIf()->IfTrueSuccessor()), + loop->Contains(*GetLoopControl(loop)->AsIf()->IfFalseSuccessor())); + if (loop->Contains(*context)) { + // Use the full trip count if determining the maximum and context is not in the loop body. + DCHECK_NE(context == loop->GetHeader(), IsContextInBody(context, loop)); + return !is_min && context == loop->GetHeader(); + } else { + // Trip count after the loop is always the maximum (ignoring `is_min`), + // as long as the `context` is dominated by the loop control exit block. + // If there are additional exit edges, the value is unknown on those paths. + HInstruction* loop_control = GetLoopControl(loop); + HBasicBlock* then_block = loop_control->AsIf()->IfTrueSuccessor(); + HBasicBlock* else_block = loop_control->AsIf()->IfFalseSuccessor(); + HBasicBlock* loop_exit_block = loop->Contains(*then_block) ? else_block : then_block; + return loop_exit_block->Dominates(context); + } +} + // // Public class methods. // @@ -165,13 +198,13 @@ InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis) DCHECK(induction_analysis != nullptr); } -bool InductionVarRange::GetInductionRange(HInstruction* context, +bool InductionVarRange::GetInductionRange(const HBasicBlock* context, HInstruction* instruction, HInstruction* chase_hint, /*out*/Value* min_val, /*out*/Value* max_val, /*out*/bool* needs_finite_test) { - HLoopInformation* loop = nullptr; + const HLoopInformation* loop = nullptr; HInductionVarAnalysis::InductionInfo* info = nullptr; HInductionVarAnalysis::InductionInfo* trip = nullptr; if (!HasInductionInfo(context, instruction, &loop, &info, &trip)) { @@ -192,20 +225,20 @@ bool InductionVarRange::GetInductionRange(HInstruction* context, } // Find range. chase_hint_ = chase_hint; - bool in_body = context->GetBlock() != loop->GetHeader(); int64_t stride_value = 0; - *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min= */ true)); - *max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min= */ false), chase_hint); - *needs_finite_test = NeedsTripCount(info, &stride_value) && IsUnsafeTripCount(trip); + *min_val = SimplifyMin(GetVal(context, loop, info, trip, /*is_min=*/ true)); + *max_val = SimplifyMax(GetVal(context, loop, info, trip, /*is_min=*/ false), chase_hint); + *needs_finite_test = + NeedsTripCount(context, loop, info, &stride_value) && IsUnsafeTripCount(trip); chase_hint_ = nullptr; // Retry chasing constants for wrap-around (merge sensitive). if (!min_val->is_known && info->induction_class == HInductionVarAnalysis::kWrapAround) { - *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min= */ true)); + *min_val = SimplifyMin(GetVal(context, loop, info, trip, /*is_min=*/ true)); } return true; } -bool InductionVarRange::CanGenerateRange(HInstruction* context, +bool InductionVarRange::CanGenerateRange(const HBasicBlock* context, HInstruction* instruction, /*out*/bool* needs_finite_test, /*out*/bool* needs_taken_test) { @@ -227,7 +260,7 @@ bool InductionVarRange::CanGenerateRange(HInstruction* context, stride_value == 1); // avoid arithmetic wrap-around anomalies. } -void InductionVarRange::GenerateRange(HInstruction* context, +void InductionVarRange::GenerateRange(const HBasicBlock* context, HInstruction* instruction, HGraph* graph, HBasicBlock* block, @@ -251,15 +284,16 @@ void InductionVarRange::GenerateRange(HInstruction* context, } } -HInstruction* InductionVarRange::GenerateTakenTest(HInstruction* context, +HInstruction* InductionVarRange::GenerateTakenTest(HInstruction* loop_control, HGraph* graph, HBasicBlock* block) { + const HBasicBlock* context = loop_control->GetBlock(); HInstruction* taken_test = nullptr; bool is_last_value = false; int64_t stride_value = 0; bool b1, b2; // unused if (!GenerateRangeOrLastValue(context, - context, + loop_control, is_last_value, graph, block, @@ -275,11 +309,12 @@ HInstruction* InductionVarRange::GenerateTakenTest(HInstruction* context, } bool InductionVarRange::CanGenerateLastValue(HInstruction* instruction) { + const HBasicBlock* context = instruction->GetBlock(); bool is_last_value = true; int64_t stride_value = 0; bool needs_finite_test = false; bool needs_taken_test = false; - return GenerateRangeOrLastValue(instruction, + return GenerateRangeOrLastValue(context, instruction, is_last_value, nullptr, @@ -296,11 +331,12 @@ bool InductionVarRange::CanGenerateLastValue(HInstruction* instruction) { HInstruction* InductionVarRange::GenerateLastValue(HInstruction* instruction, HGraph* graph, HBasicBlock* block) { + const HBasicBlock* context = instruction->GetBlock(); HInstruction* last_value = nullptr; bool is_last_value = true; int64_t stride_value = 0; bool b1, b2; // unused - if (!GenerateRangeOrLastValue(instruction, + if (!GenerateRangeOrLastValue(context, instruction, is_last_value, graph, @@ -329,32 +365,32 @@ void InductionVarRange::Replace(HInstruction* instruction, } } -bool InductionVarRange::IsFinite(HLoopInformation* loop, /*out*/ int64_t* trip_count) const { +bool InductionVarRange::IsFinite(const HLoopInformation* loop, /*out*/ int64_t* trip_count) const { bool is_constant_unused = false; return CheckForFiniteAndConstantProps(loop, &is_constant_unused, trip_count); } -bool InductionVarRange::HasKnownTripCount(HLoopInformation* loop, +bool InductionVarRange::HasKnownTripCount(const HLoopInformation* loop, /*out*/ int64_t* trip_count) const { bool is_constant = false; CheckForFiniteAndConstantProps(loop, &is_constant, trip_count); return is_constant; } -bool InductionVarRange::IsUnitStride(HInstruction* context, +bool InductionVarRange::IsUnitStride(const HBasicBlock* context, HInstruction* instruction, HGraph* graph, /*out*/ HInstruction** offset) const { - HLoopInformation* loop = nullptr; + const HLoopInformation* loop = nullptr; HInductionVarAnalysis::InductionInfo* info = nullptr; HInductionVarAnalysis::InductionInfo* trip = nullptr; if (HasInductionInfo(context, instruction, &loop, &info, &trip)) { if (info->induction_class == HInductionVarAnalysis::kLinear && !HInductionVarAnalysis::IsNarrowingLinear(info)) { int64_t stride_value = 0; - if (IsConstant(info->op_a, kExact, &stride_value) && stride_value == 1) { + if (IsConstant(context, loop, info->op_a, kExact, &stride_value) && stride_value == 1) { int64_t off_value = 0; - if (IsConstant(info->op_b, kExact, &off_value)) { + if (IsConstant(context, loop, info->op_b, kExact, &off_value)) { *offset = graph->GetConstant(info->op_b->type, off_value); } else if (info->op_b->operation == HInductionVarAnalysis::kFetch) { *offset = info->op_b->fetch; @@ -368,20 +404,35 @@ bool InductionVarRange::IsUnitStride(HInstruction* context, return false; } -HInstruction* InductionVarRange::GenerateTripCount(HLoopInformation* loop, +HInstruction* InductionVarRange::GenerateTripCount(const HLoopInformation* loop, HGraph* graph, HBasicBlock* block) { - HInductionVarAnalysis::InductionInfo *trip = - induction_analysis_->LookupInfo(loop, GetLoopControl(loop)); + HInstruction* loop_control = GetLoopControl(loop); + HInductionVarAnalysis::InductionInfo *trip = induction_analysis_->LookupInfo(loop, loop_control); if (trip != nullptr && !IsUnsafeTripCount(trip)) { + const HBasicBlock* context = loop_control->GetBlock(); HInstruction* taken_test = nullptr; HInstruction* trip_expr = nullptr; if (IsBodyTripCount(trip)) { - if (!GenerateCode(trip->op_b, nullptr, graph, block, &taken_test, false, false)) { + if (!GenerateCode(context, + loop, + trip->op_b, + /*trip=*/ nullptr, + graph, + block, + /*is_min=*/ false, + &taken_test)) { return nullptr; } } - if (GenerateCode(trip->op_a, nullptr, graph, block, &trip_expr, false, false)) { + if (GenerateCode(context, + loop, + trip->op_a, + /*trip=*/ nullptr, + graph, + block, + /*is_min=*/ false, + &trip_expr)) { if (taken_test != nullptr) { HInstruction* zero = graph->GetConstant(trip->type, 0); ArenaAllocator* allocator = graph->GetAllocator(); @@ -397,19 +448,22 @@ HInstruction* InductionVarRange::GenerateTripCount(HLoopInformation* loop, // Private class methods. // -bool InductionVarRange::CheckForFiniteAndConstantProps(HLoopInformation* loop, +bool InductionVarRange::CheckForFiniteAndConstantProps(const HLoopInformation* loop, /*out*/ bool* is_constant, /*out*/ int64_t* trip_count) const { - HInductionVarAnalysis::InductionInfo *trip = - induction_analysis_->LookupInfo(loop, GetLoopControl(loop)); + HInstruction* loop_control = GetLoopControl(loop); + HInductionVarAnalysis::InductionInfo *trip = induction_analysis_->LookupInfo(loop, loop_control); if (trip != nullptr && !IsUnsafeTripCount(trip)) { - *is_constant = IsConstant(trip->op_a, kExact, trip_count); + const HBasicBlock* context = loop_control->GetBlock(); + *is_constant = IsConstant(context, loop, trip->op_a, kExact, trip_count); return true; } return false; } -bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info, +bool InductionVarRange::IsConstant(const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* info, ConstantRequest request, /*out*/ int64_t* value) const { if (info != nullptr) { @@ -423,8 +477,8 @@ bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info, } // Try range analysis on the invariant, only accept a proper range // to avoid arithmetic wrap-around anomalies. - Value min_val = GetVal(info, nullptr, /* in_body= */ true, /* is_min= */ true); - Value max_val = GetVal(info, nullptr, /* in_body= */ true, /* is_min= */ false); + Value min_val = GetVal(context, loop, info, /*trip=*/ nullptr, /*is_min=*/ true); + Value max_val = GetVal(context, loop, info, /*trip=*/ nullptr, /*is_min=*/ false); if (IsConstantValue(min_val) && IsConstantValue(max_val) && min_val.b_constant <= max_val.b_constant) { if ((request == kExact && min_val.b_constant == max_val.b_constant) || request == kAtMost) { @@ -440,14 +494,13 @@ bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info, } bool InductionVarRange::HasInductionInfo( - HInstruction* context, + const HBasicBlock* context, HInstruction* instruction, - /*out*/ HLoopInformation** loop, + /*out*/ const HLoopInformation** loop, /*out*/ HInductionVarAnalysis::InductionInfo** info, /*out*/ HInductionVarAnalysis::InductionInfo** trip) const { DCHECK(context != nullptr); - DCHECK(context->GetBlock() != nullptr); - HLoopInformation* lp = context->GetBlock()->GetLoopInformation(); // closest enveloping loop + HLoopInformation* lp = context->GetLoopInformation(); // closest enveloping loop if (lp != nullptr) { HInductionVarAnalysis::InductionInfo* i = induction_analysis_->LookupInfo(lp, instruction); if (i != nullptr) { @@ -460,7 +513,9 @@ bool InductionVarRange::HasInductionInfo( return false; } -bool InductionVarRange::IsWellBehavedTripCount(HInductionVarAnalysis::InductionInfo* trip) const { +bool InductionVarRange::IsWellBehavedTripCount(const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* trip) const { if (trip != nullptr) { // Both bounds that define a trip-count are well-behaved if they either are not defined // in any loop, or are contained in a proper interval. This allows finding the min/max @@ -469,8 +524,9 @@ bool InductionVarRange::IsWellBehavedTripCount(HInductionVarAnalysis::InductionI HInductionVarAnalysis::InductionInfo* lower = trip->op_b->op_a; HInductionVarAnalysis::InductionInfo* upper = trip->op_b->op_b; int64_t not_used = 0; - return (!HasFetchInLoop(lower) || range.IsConstant(lower, kAtLeast, ¬_used)) && - (!HasFetchInLoop(upper) || range.IsConstant(upper, kAtLeast, ¬_used)); + return + (!HasFetchInLoop(lower) || range.IsConstant(context, loop, lower, kAtLeast, ¬_used)) && + (!HasFetchInLoop(upper) || range.IsConstant(context, loop, upper, kAtLeast, ¬_used)); } return true; } @@ -486,15 +542,17 @@ bool InductionVarRange::HasFetchInLoop(HInductionVarAnalysis::InductionInfo* inf return false; } -bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info, +bool InductionVarRange::NeedsTripCount(const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* info, int64_t* stride_value) const { if (info != nullptr) { if (info->induction_class == HInductionVarAnalysis::kLinear) { - return IsConstant(info->op_a, kExact, stride_value); + return IsConstant(context, loop, info->op_a, kExact, stride_value); } else if (info->induction_class == HInductionVarAnalysis::kPolynomial) { - return NeedsTripCount(info->op_a, stride_value); + return NeedsTripCount(context, loop, info->op_a, stride_value); } else if (info->induction_class == HInductionVarAnalysis::kWrapAround) { - return NeedsTripCount(info->op_b, stride_value); + return NeedsTripCount(context, loop, info->op_b, stride_value); } } return false; @@ -520,9 +578,10 @@ bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* return false; } -InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::InductionInfo* info, +InductionVarRange::Value InductionVarRange::GetLinear(const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* trip, - bool in_body, bool is_min) const { DCHECK(info != nullptr); DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kLinear); @@ -534,7 +593,7 @@ InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::Ind HInductionVarAnalysis::InductionInfo* trip_expr = trip->op_a; if (trip_expr->type == info->type && trip_expr->operation == HInductionVarAnalysis::kSub) { int64_t stride_value = 0; - if (IsConstant(info->op_a, kExact, &stride_value)) { + if (IsConstant(context, loop, info->op_a, kExact, &stride_value)) { if (!is_min && stride_value == 1) { // Test original trip's negative operand (trip_expr->op_b) against offset of induction. if (HInductionVarAnalysis::InductionEqual(trip_expr->op_b, info->op_b)) { @@ -546,7 +605,7 @@ InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::Ind trip->op_b, nullptr, trip->type); - return GetVal(&cancelled_trip, trip, in_body, is_min); + return GetVal(context, loop, &cancelled_trip, trip, is_min); } } else if (is_min && stride_value == -1) { // Test original trip's positive operand (trip_expr->op_a) against offset of induction. @@ -561,72 +620,81 @@ InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::Ind trip->type); HInductionVarAnalysis::InductionInfo cancelled_trip( trip->induction_class, trip->operation, &neg, trip->op_b, nullptr, trip->type); - return SubValue(Value(0), GetVal(&cancelled_trip, trip, in_body, !is_min)); + return SubValue(Value(0), GetVal(context, loop, &cancelled_trip, trip, !is_min)); } } } } } // General rule of linear induction a * i + b, for normalized 0 <= i < TC. - return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min), - GetVal(info->op_b, trip, in_body, is_min)); + return AddValue(GetMul(context, loop, info->op_a, trip, trip, is_min), + GetVal(context, loop, info->op_b, trip, is_min)); } -InductionVarRange::Value InductionVarRange::GetPolynomial(HInductionVarAnalysis::InductionInfo* info, - HInductionVarAnalysis::InductionInfo* trip, - bool in_body, - bool is_min) const { +InductionVarRange::Value InductionVarRange::GetPolynomial( + const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* info, + HInductionVarAnalysis::InductionInfo* trip, + bool is_min) const { DCHECK(info != nullptr); DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial); int64_t a = 0; int64_t b = 0; - if (IsConstant(info->op_a->op_a, kExact, &a) && CanLongValueFitIntoInt(a) && a >= 0 && - IsConstant(info->op_a->op_b, kExact, &b) && CanLongValueFitIntoInt(b) && b >= 0) { + if (IsConstant(context, loop, info->op_a->op_a, kExact, &a) && + CanLongValueFitIntoInt(a) && + a >= 0 && + IsConstant(context, loop, info->op_a->op_b, kExact, &b) && + CanLongValueFitIntoInt(b) && + b >= 0) { // Evaluate bounds on sum_i=0^m-1(a * i + b) + c with a,b >= 0 for // maximum index value m as a * (m * (m-1)) / 2 + b * m + c. - Value c = GetVal(info->op_b, trip, in_body, is_min); - if (is_min) { - return c; - } else { - Value m = GetVal(trip, trip, in_body, is_min); - Value t = DivValue(MulValue(m, SubValue(m, Value(1))), Value(2)); - Value x = MulValue(Value(a), t); - Value y = MulValue(Value(b), m); - return AddValue(AddValue(x, y), c); - } + // Do not simply return `c` as minimum because the trip count may be non-zero + // if the `context` is after the `loop` (and therefore ignoring `is_min`). + Value c = GetVal(context, loop, info->op_b, trip, is_min); + Value m = GetVal(context, loop, trip, trip, is_min); + Value t = DivValue(MulValue(m, SubValue(m, Value(1))), Value(2)); + Value x = MulValue(Value(a), t); + Value y = MulValue(Value(b), m); + return AddValue(AddValue(x, y), c); } return Value(); } -InductionVarRange::Value InductionVarRange::GetGeometric(HInductionVarAnalysis::InductionInfo* info, +InductionVarRange::Value InductionVarRange::GetGeometric(const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* trip, - bool in_body, bool is_min) const { DCHECK(info != nullptr); DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric); int64_t a = 0; int64_t f = 0; - if (IsConstant(info->op_a, kExact, &a) && + if (IsConstant(context, loop, info->op_a, kExact, &a) && CanLongValueFitIntoInt(a) && IsInt64AndGet(info->fetch, &f) && f >= 1) { // Conservative bounds on a * f^-i + b with f >= 1 can be computed without // trip count. Other forms would require a much more elaborate evaluation. const bool is_min_a = a >= 0 ? is_min : !is_min; if (info->operation == HInductionVarAnalysis::kDiv) { - Value b = GetVal(info->op_b, trip, in_body, is_min); + Value b = GetVal(context, loop, info->op_b, trip, is_min); return is_min_a ? b : AddValue(Value(a), b); } } return Value(); } -InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, +InductionVarRange::Value InductionVarRange::GetFetch(const HBasicBlock* context, + const HLoopInformation* loop, + HInstruction* instruction, HInductionVarAnalysis::InductionInfo* trip, - bool in_body, bool is_min) const { // Special case when chasing constants: single instruction that denotes trip count in the // loop-body is minimal 1 and maximal, with safe trip-count, max int, - if (chase_hint_ == nullptr && in_body && trip != nullptr && instruction == trip->op_a->fetch) { + if (chase_hint_ == nullptr && + IsContextInBody(context, loop) && + trip != nullptr && + instruction == trip->op_a->fetch) { if (is_min) { return Value(1); } else if (!instruction->IsConstant() && !IsUnsafeTripCount(trip)) { @@ -646,18 +714,18 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, // Incorporate suitable constants in the chased value. if (IsInt64AndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) { return AddValue(Value(static_cast<int32_t>(value)), - GetFetch(instruction->InputAt(1), trip, in_body, is_min)); + GetFetch(context, loop, instruction->InputAt(1), trip, is_min)); } else if (IsInt64AndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) { - return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min), + return AddValue(GetFetch(context, loop, instruction->InputAt(0), trip, is_min), Value(static_cast<int32_t>(value))); } } else if (instruction->IsSub()) { // Incorporate suitable constants in the chased value. if (IsInt64AndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) { return SubValue(Value(static_cast<int32_t>(value)), - GetFetch(instruction->InputAt(1), trip, in_body, !is_min)); + GetFetch(context, loop, instruction->InputAt(1), trip, !is_min)); } else if (IsInt64AndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) { - return SubValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min), + return SubValue(GetFetch(context, loop, instruction->InputAt(0), trip, is_min), Value(static_cast<int32_t>(value))); } } else if (instruction->IsArrayLength()) { @@ -665,39 +733,45 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, if (chase_hint_ == nullptr) { return is_min ? Value(0) : Value(std::numeric_limits<int32_t>::max()); } else if (instruction->InputAt(0)->IsNewArray()) { - return GetFetch(instruction->InputAt(0)->AsNewArray()->GetLength(), trip, in_body, is_min); + return GetFetch( + context, loop, instruction->InputAt(0)->AsNewArray()->GetLength(), trip, is_min); } } else if (instruction->IsTypeConversion()) { // Since analysis is 32-bit (or narrower), chase beyond widening along the path. // For example, this discovers the length in: for (long i = 0; i < a.length; i++); if (instruction->AsTypeConversion()->GetInputType() == DataType::Type::kInt32 && instruction->AsTypeConversion()->GetResultType() == DataType::Type::kInt64) { - return GetFetch(instruction->InputAt(0), trip, in_body, is_min); + return GetFetch(context, loop, instruction->InputAt(0), trip, is_min); } } - // Chase an invariant fetch that is defined by an outer loop if the trip-count used + // Chase an invariant fetch that is defined by another loop if the trip-count used // so far is well-behaved in both bounds and the next trip-count is safe. // Example: // for (int i = 0; i <= 100; i++) // safe // for (int j = 0; j <= i; j++) // well-behaved // j is in range [0, i ] (if i is chase hint) // or in range [0, 100] (otherwise) - HLoopInformation* next_loop = nullptr; + // Example: + // for (i = 0; i < 100; ++i) + // <some-code> + // for (j = 0; j < 10; ++j) + // sum += i; // The `i` is a "fetch" of a loop Phi from the previous loop. + const HLoopInformation* next_loop = nullptr; HInductionVarAnalysis::InductionInfo* next_info = nullptr; HInductionVarAnalysis::InductionInfo* next_trip = nullptr; - bool next_in_body = true; // inner loop is always in body of outer loop - if (HasInductionInfo(instruction, instruction, &next_loop, &next_info, &next_trip) && - IsWellBehavedTripCount(trip) && + if (HasInductionInfo(instruction->GetBlock(), instruction, &next_loop, &next_info, &next_trip) && + IsWellBehavedTripCount(context, next_loop, trip) && !IsUnsafeTripCount(next_trip)) { - return GetVal(next_info, next_trip, next_in_body, is_min); + return GetVal(context, next_loop, next_info, next_trip, is_min); } // Fetch is represented by itself. return Value(instruction, 1, 0); } -InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::InductionInfo* info, +InductionVarRange::Value InductionVarRange::GetVal(const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* trip, - bool in_body, bool is_min) const { if (info != nullptr) { switch (info->induction_class) { @@ -705,36 +779,37 @@ InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::Induct // Invariants. switch (info->operation) { case HInductionVarAnalysis::kAdd: - return AddValue(GetVal(info->op_a, trip, in_body, is_min), - GetVal(info->op_b, trip, in_body, is_min)); + return AddValue(GetVal(context, loop, info->op_a, trip, is_min), + GetVal(context, loop, info->op_b, trip, is_min)); case HInductionVarAnalysis::kSub: // second reversed! - return SubValue(GetVal(info->op_a, trip, in_body, is_min), - GetVal(info->op_b, trip, in_body, !is_min)); + return SubValue(GetVal(context, loop, info->op_a, trip, is_min), + GetVal(context, loop, info->op_b, trip, !is_min)); case HInductionVarAnalysis::kNeg: // second reversed! return SubValue(Value(0), - GetVal(info->op_b, trip, in_body, !is_min)); + GetVal(context, loop, info->op_b, trip, !is_min)); case HInductionVarAnalysis::kMul: - return GetMul(info->op_a, info->op_b, trip, in_body, is_min); + return GetMul(context, loop, info->op_a, info->op_b, trip, is_min); case HInductionVarAnalysis::kDiv: - return GetDiv(info->op_a, info->op_b, trip, in_body, is_min); + return GetDiv(context, loop, info->op_a, info->op_b, trip, is_min); case HInductionVarAnalysis::kRem: - return GetRem(info->op_a, info->op_b); + return GetRem(context, loop, info->op_a, info->op_b); case HInductionVarAnalysis::kXor: - return GetXor(info->op_a, info->op_b); + return GetXor(context, loop, info->op_a, info->op_b); case HInductionVarAnalysis::kFetch: - return GetFetch(info->fetch, trip, in_body, is_min); + return GetFetch(context, loop, info->fetch, trip, is_min); case HInductionVarAnalysis::kTripCountInLoop: case HInductionVarAnalysis::kTripCountInLoopUnsafe: - if (!in_body && !is_min) { // one extra! - return GetVal(info->op_a, trip, in_body, is_min); + if (UseFullTripCount(context, loop, is_min)) { + // Return the full trip count (do not subtract 1 as we do in loop body). + return GetVal(context, loop, info->op_a, trip, /*is_min=*/ false); } FALLTHROUGH_INTENDED; case HInductionVarAnalysis::kTripCountInBody: case HInductionVarAnalysis::kTripCountInBodyUnsafe: if (is_min) { return Value(0); - } else if (in_body) { - return SubValue(GetVal(info->op_a, trip, in_body, is_min), Value(1)); + } else if (IsContextInBody(context, loop)) { + return SubValue(GetVal(context, loop, info->op_a, trip, is_min), Value(1)); } break; default: @@ -742,37 +817,39 @@ InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::Induct } break; case HInductionVarAnalysis::kLinear: - return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type); + return CorrectForType(GetLinear(context, loop, info, trip, is_min), info->type); case HInductionVarAnalysis::kPolynomial: - return GetPolynomial(info, trip, in_body, is_min); + return GetPolynomial(context, loop, info, trip, is_min); case HInductionVarAnalysis::kGeometric: - return GetGeometric(info, trip, in_body, is_min); + return GetGeometric(context, loop, info, trip, is_min); case HInductionVarAnalysis::kWrapAround: case HInductionVarAnalysis::kPeriodic: - return MergeVal(GetVal(info->op_a, trip, in_body, is_min), - GetVal(info->op_b, trip, in_body, is_min), is_min); + return MergeVal(GetVal(context, loop, info->op_a, trip, is_min), + GetVal(context, loop, info->op_b, trip, is_min), + is_min); } } return Value(); } -InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1, +InductionVarRange::Value InductionVarRange::GetMul(const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* info1, HInductionVarAnalysis::InductionInfo* info2, HInductionVarAnalysis::InductionInfo* trip, - bool in_body, bool is_min) const { // Constant times range. int64_t value = 0; - if (IsConstant(info1, kExact, &value)) { - return MulRangeAndConstant(value, info2, trip, in_body, is_min); - } else if (IsConstant(info2, kExact, &value)) { - return MulRangeAndConstant(value, info1, trip, in_body, is_min); + if (IsConstant(context, loop, info1, kExact, &value)) { + return MulRangeAndConstant(context, loop, value, info2, trip, is_min); + } else if (IsConstant(context, loop, info2, kExact, &value)) { + return MulRangeAndConstant(context, loop, value, info1, trip, is_min); } // Interval ranges. - Value v1_min = GetVal(info1, trip, in_body, /* is_min= */ true); - Value v1_max = GetVal(info1, trip, in_body, /* is_min= */ false); - Value v2_min = GetVal(info2, trip, in_body, /* is_min= */ true); - Value v2_max = GetVal(info2, trip, in_body, /* is_min= */ false); + Value v1_min = GetVal(context, loop, info1, trip, /*is_min=*/ true); + Value v1_max = GetVal(context, loop, info1, trip, /*is_min=*/ false); + Value v2_min = GetVal(context, loop, info2, trip, /*is_min=*/ true); + Value v2_max = GetVal(context, loop, info2, trip, /*is_min=*/ false); // Positive range vs. positive or negative range. if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) { if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { @@ -792,21 +869,22 @@ InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::Induct return Value(); } -InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::InductionInfo* info1, +InductionVarRange::Value InductionVarRange::GetDiv(const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* info1, HInductionVarAnalysis::InductionInfo* info2, HInductionVarAnalysis::InductionInfo* trip, - bool in_body, bool is_min) const { // Range divided by constant. int64_t value = 0; - if (IsConstant(info2, kExact, &value)) { - return DivRangeAndConstant(value, info1, trip, in_body, is_min); + if (IsConstant(context, loop, info2, kExact, &value)) { + return DivRangeAndConstant(context, loop, value, info1, trip, is_min); } // Interval ranges. - Value v1_min = GetVal(info1, trip, in_body, /* is_min= */ true); - Value v1_max = GetVal(info1, trip, in_body, /* is_min= */ false); - Value v2_min = GetVal(info2, trip, in_body, /* is_min= */ true); - Value v2_max = GetVal(info2, trip, in_body, /* is_min= */ false); + Value v1_min = GetVal(context, loop, info1, trip, /*is_min=*/ true); + Value v1_max = GetVal(context, loop, info1, trip, /*is_min=*/ false); + Value v2_min = GetVal(context, loop, info2, trip, /*is_min=*/ true); + Value v2_max = GetVal(context, loop, info2, trip, /*is_min=*/ false); // Positive range vs. positive or negative range. if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) { if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { @@ -827,12 +905,16 @@ InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::Induct } InductionVarRange::Value InductionVarRange::GetRem( + const HBasicBlock* context, + const HLoopInformation* loop, HInductionVarAnalysis::InductionInfo* info1, HInductionVarAnalysis::InductionInfo* info2) const { int64_t v1 = 0; int64_t v2 = 0; // Only accept exact values. - if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2) && v2 != 0) { + if (IsConstant(context, loop, info1, kExact, &v1) && + IsConstant(context, loop, info2, kExact, &v2) && + v2 != 0) { int64_t value = v1 % v2; if (CanLongValueFitIntoInt(value)) { return Value(static_cast<int32_t>(value)); @@ -842,12 +924,15 @@ InductionVarRange::Value InductionVarRange::GetRem( } InductionVarRange::Value InductionVarRange::GetXor( + const HBasicBlock* context, + const HLoopInformation* loop, HInductionVarAnalysis::InductionInfo* info1, HInductionVarAnalysis::InductionInfo* info2) const { int64_t v1 = 0; int64_t v2 = 0; // Only accept exact values. - if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2)) { + if (IsConstant(context, loop, info1, kExact, &v1) && + IsConstant(context, loop, info2, kExact, &v2)) { int64_t value = v1 ^ v2; if (CanLongValueFitIntoInt(value)) { return Value(static_cast<int32_t>(value)); @@ -857,27 +942,29 @@ InductionVarRange::Value InductionVarRange::GetXor( } InductionVarRange::Value InductionVarRange::MulRangeAndConstant( + const HBasicBlock* context, + const HLoopInformation* loop, int64_t value, HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* trip, - bool in_body, bool is_min) const { if (CanLongValueFitIntoInt(value)) { Value c(static_cast<int32_t>(value)); - return MulValue(GetVal(info, trip, in_body, is_min == value >= 0), c); + return MulValue(GetVal(context, loop, info, trip, is_min == value >= 0), c); } return Value(); } InductionVarRange::Value InductionVarRange::DivRangeAndConstant( + const HBasicBlock* context, + const HLoopInformation* loop, int64_t value, HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* trip, - bool in_body, bool is_min) const { if (CanLongValueFitIntoInt(value)) { Value c(static_cast<int32_t>(value)); - return DivValue(GetVal(info, trip, in_body, is_min == value >= 0), c); + return DivValue(GetVal(context, loop, info, trip, is_min == value >= 0), c); } return Value(); } @@ -945,7 +1032,7 @@ InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is return Value(); } -bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, +bool InductionVarRange::GenerateRangeOrLastValue(const HBasicBlock* context, HInstruction* instruction, bool is_last_value, HGraph* graph, @@ -956,7 +1043,7 @@ bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, /*out*/int64_t* stride_value, /*out*/bool* needs_finite_test, /*out*/bool* needs_taken_test) const { - HLoopInformation* loop = nullptr; + const HLoopInformation* loop = nullptr; HInductionVarAnalysis::InductionInfo* info = nullptr; HInductionVarAnalysis::InductionInfo* trip = nullptr; if (!HasInductionInfo(context, instruction, &loop, &info, &trip) || trip == nullptr) { @@ -967,13 +1054,12 @@ bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, // the computed range). A taken test is needed for any unknown trip-count, even if evaluation // code does not use the trip-count explicitly (since there could be an implicit relation // between e.g. an invariant subscript and a not-taken condition). - bool in_body = context->GetBlock() != loop->GetHeader(); *stride_value = 0; - *needs_finite_test = NeedsTripCount(info, stride_value) && IsUnsafeTripCount(trip); + *needs_finite_test = NeedsTripCount(context, loop, info, stride_value) && IsUnsafeTripCount(trip); *needs_taken_test = IsBodyTripCount(trip); // Handle last value request. if (is_last_value) { - DCHECK(!in_body); + DCHECK(!IsContextInBody(context, loop)); switch (info->induction_class) { case HInductionVarAnalysis::kLinear: if (*stride_value > 0) { @@ -983,13 +1069,14 @@ bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, } break; case HInductionVarAnalysis::kPolynomial: - return GenerateLastValuePolynomial(info, trip, graph, block, lower); + return GenerateLastValuePolynomial(context, loop, info, trip, graph, block, lower); case HInductionVarAnalysis::kGeometric: - return GenerateLastValueGeometric(info, trip, graph, block, lower); + return GenerateLastValueGeometric(context, loop, info, trip, graph, block, lower); case HInductionVarAnalysis::kWrapAround: - return GenerateLastValueWrapAround(info, trip, graph, block, lower); + return GenerateLastValueWrapAround(context, loop, info, trip, graph, block, lower); case HInductionVarAnalysis::kPeriodic: - return GenerateLastValuePeriodic(info, trip, graph, block, lower, needs_taken_test); + return GenerateLastValuePeriodic( + context, loop, info, trip, graph, block, lower, needs_taken_test); default: return false; } @@ -997,10 +1084,23 @@ bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, // Code generation for taken test: generate the code when requested or otherwise analyze // if code generation is feasible when taken test is needed. if (taken_test != nullptr) { - return GenerateCode(trip->op_b, nullptr, graph, block, taken_test, in_body, /* is_min= */ false); + return GenerateCode(context, + loop, + trip->op_b, + /*trip=*/ nullptr, + graph, + block, + /*is_min=*/ false, + taken_test); } else if (*needs_taken_test) { - if (!GenerateCode( - trip->op_b, nullptr, nullptr, nullptr, nullptr, in_body, /* is_min= */ false)) { + if (!GenerateCode(context, + loop, + trip->op_b, + /*trip=*/ nullptr, + /*graph=*/ nullptr, + /*block=*/ nullptr, + /*is_min=*/ false, + /*result=*/ nullptr)) { return false; } } @@ -1008,12 +1108,14 @@ bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, return // Success on lower if invariant (not set), or code can be generated. ((info->induction_class == HInductionVarAnalysis::kInvariant) || - GenerateCode(info, trip, graph, block, lower, in_body, /* is_min= */ true)) && + GenerateCode(context, loop, info, trip, graph, block, /*is_min=*/ true, lower)) && // And success on upper. - GenerateCode(info, trip, graph, block, upper, in_body, /* is_min= */ false); + GenerateCode(context, loop, info, trip, graph, block, /*is_min=*/ false, upper); } -bool InductionVarRange::GenerateLastValuePolynomial(HInductionVarAnalysis::InductionInfo* info, +bool InductionVarRange::GenerateLastValuePolynomial(const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* trip, HGraph* graph, HBasicBlock* block, @@ -1024,13 +1126,21 @@ bool InductionVarRange::GenerateLastValuePolynomial(HInductionVarAnalysis::Induc int64_t a = 0; int64_t b = 0; int64_t m = 0; - if (IsConstant(info->op_a->op_a, kExact, &a) && - IsConstant(info->op_a->op_b, kExact, &b) && - IsConstant(trip->op_a, kExact, &m) && m >= 1) { + if (IsConstant(context, loop, info->op_a->op_a, kExact, &a) && + IsConstant(context, loop, info->op_a->op_b, kExact, &b) && + IsConstant(context, loop, trip->op_a, kExact, &m) && + m >= 1) { // Evaluate bounds on sum_i=0^m-1(a * i + b) + c for known // maximum index value m as a * (m * (m-1)) / 2 + b * m + c. HInstruction* c = nullptr; - if (GenerateCode(info->op_b, nullptr, graph, block, graph ? &c : nullptr, false, false)) { + if (GenerateCode(context, + loop, + info->op_b, + /*trip=*/ nullptr, + graph, + block, + /*is_min=*/ false, + graph ? &c : nullptr)) { if (graph != nullptr) { DataType::Type type = info->type; int64_t sum = a * ((m * (m - 1)) / 2) + b * m; @@ -1046,7 +1156,9 @@ bool InductionVarRange::GenerateLastValuePolynomial(HInductionVarAnalysis::Induc return false; } -bool InductionVarRange::GenerateLastValueGeometric(HInductionVarAnalysis::InductionInfo* info, +bool InductionVarRange::GenerateLastValueGeometric(const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* trip, HGraph* graph, HBasicBlock* block, @@ -1056,11 +1168,16 @@ bool InductionVarRange::GenerateLastValueGeometric(HInductionVarAnalysis::Induct // Detect known base and trip count (always taken). int64_t f = 0; int64_t m = 0; - if (IsInt64AndGet(info->fetch, &f) && f >= 1 && IsConstant(trip->op_a, kExact, &m) && m >= 1) { + if (IsInt64AndGet(info->fetch, &f) && + f >= 1 && + IsConstant(context, loop, trip->op_a, kExact, &m) && + m >= 1) { HInstruction* opa = nullptr; HInstruction* opb = nullptr; - if (GenerateCode(info->op_a, nullptr, graph, block, &opa, false, false) && - GenerateCode(info->op_b, nullptr, graph, block, &opb, false, false)) { + if (GenerateCode( + context, loop, info->op_a, /*trip=*/ nullptr, graph, block, /*is_min=*/ false, &opa) && + GenerateCode( + context, loop, info->op_b, /*trip=*/ nullptr, graph, block, /*is_min=*/ false, &opb)) { if (graph != nullptr) { DataType::Type type = info->type; // Compute f ^ m for known maximum index value m. @@ -1098,7 +1215,9 @@ bool InductionVarRange::GenerateLastValueGeometric(HInductionVarAnalysis::Induct return false; } -bool InductionVarRange::GenerateLastValueWrapAround(HInductionVarAnalysis::InductionInfo* info, +bool InductionVarRange::GenerateLastValueWrapAround(const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* trip, HGraph* graph, HBasicBlock* block, @@ -1113,13 +1232,17 @@ bool InductionVarRange::GenerateLastValueWrapAround(HInductionVarAnalysis::Induc // TODO: generalize, but be careful to adjust the terminal. int64_t m = 0; if (info->induction_class == HInductionVarAnalysis::kInvariant && - IsConstant(trip->op_a, kExact, &m) && m >= depth) { - return GenerateCode(info, nullptr, graph, block, result, false, false); + IsConstant(context, loop, trip->op_a, kExact, &m) && + m >= depth) { + return GenerateCode( + context, loop, info, /*trip=*/ nullptr, graph, block, /*is_min=*/ false, result); } return false; } -bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info, +bool InductionVarRange::GenerateLastValuePeriodic(const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* trip, HGraph* graph, HBasicBlock* block, @@ -1150,13 +1273,14 @@ bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::Inducti } // Handle any periodic(x, periodic(.., y)) for known maximum index value m. int64_t m = 0; - if (IsConstant(trip->op_a, kExact, &m) && m >= 1) { + if (IsConstant(context, loop, trip->op_a, kExact, &m) && m >= 1) { int64_t li = m % period; for (int64_t i = 0; i < li; info = info->op_b, i++) {} if (info->induction_class == HInductionVarAnalysis::kPeriodic) { info = info->op_a; } - return GenerateCode(info, nullptr, graph, block, result, false, false); + return GenerateCode( + context, loop, info, /*trip=*/ nullptr, graph, block, /*is_min=*/ false, result); } // Handle periodic(x, y) using even/odd-select on trip count. Enter trip count expression // directly to obtain the maximum index value t even if taken test is needed. @@ -1164,9 +1288,30 @@ bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::Inducti HInstruction* y = nullptr; HInstruction* t = nullptr; if (period == 2 && - GenerateCode(info->op_a, nullptr, graph, block, graph ? &x : nullptr, false, false) && - GenerateCode(info->op_b, nullptr, graph, block, graph ? &y : nullptr, false, false) && - GenerateCode(trip->op_a, nullptr, graph, block, graph ? &t : nullptr, false, false)) { + GenerateCode(context, + loop, + info->op_a, + /*trip=*/ nullptr, + graph, + block, + /*is_min=*/ false, + graph ? &x : nullptr) && + GenerateCode(context, + loop, + info->op_b, + /*trip=*/ nullptr, + graph, + block, + /*is_min=*/ false, + graph ? &y : nullptr) && + GenerateCode(context, + loop, + trip->op_a, + /*trip=*/ nullptr, + graph, + block, + /*is_min=*/ false, + graph ? &t : nullptr)) { // During actual code generation (graph != nullptr), generate is_even ? x : y. if (graph != nullptr) { DataType::Type type = trip->type; @@ -1180,7 +1325,14 @@ bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::Inducti // Guard select with taken test if needed. if (*needs_taken_test) { HInstruction* is_taken = nullptr; - if (GenerateCode(trip->op_b, nullptr, graph, block, graph ? &is_taken : nullptr, false, false)) { + if (GenerateCode(context, + loop, + trip->op_b, + /*trip=*/ nullptr, + graph, + block, + /*is_min=*/ false, + graph ? &is_taken : nullptr)) { if (graph != nullptr) { ArenaAllocator* allocator = graph->GetAllocator(); *result = Insert(block, new (allocator) HSelect(is_taken, *result, x, kNoDexPc)); @@ -1195,13 +1347,14 @@ bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::Inducti return false; } -bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, +bool InductionVarRange::GenerateCode(const HBasicBlock* context, + const HLoopInformation* loop, + HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* trip, HGraph* graph, // when set, code is generated HBasicBlock* block, - /*out*/HInstruction** result, - bool in_body, - bool is_min) const { + bool is_min, + /*out*/HInstruction** result) const { if (info != nullptr) { // If during codegen, the result is not needed (nullptr), simply return success. if (graph != nullptr && result == nullptr) { @@ -1226,8 +1379,8 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, case HInductionVarAnalysis::kLE: case HInductionVarAnalysis::kGT: case HInductionVarAnalysis::kGE: - if (GenerateCode(info->op_a, trip, graph, block, &opa, in_body, is_min) && - GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) { + if (GenerateCode(context, loop, info->op_a, trip, graph, block, is_min, &opa) && + GenerateCode(context, loop, info->op_b, trip, graph, block, is_min, &opb)) { if (graph != nullptr) { HInstruction* operation = nullptr; switch (info->operation) { @@ -1260,7 +1413,7 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, } break; case HInductionVarAnalysis::kNeg: - if (GenerateCode(info->op_b, trip, graph, block, &opb, in_body, !is_min)) { + if (GenerateCode(context, loop, info->op_b, trip, graph, block, !is_min, &opb)) { if (graph != nullptr) { *result = Insert(block, new (graph->GetAllocator()) HNeg(type, opb)); } @@ -1274,8 +1427,10 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, return true; case HInductionVarAnalysis::kTripCountInLoop: case HInductionVarAnalysis::kTripCountInLoopUnsafe: - if (!in_body && !is_min) { // one extra! - return GenerateCode(info->op_a, trip, graph, block, result, in_body, is_min); + if (UseFullTripCount(context, loop, is_min)) { + // Generate the full trip count (do not subtract 1 as we do in loop body). + return GenerateCode( + context, loop, info->op_a, trip, graph, block, /*is_min=*/ false, result); } FALLTHROUGH_INTENDED; case HInductionVarAnalysis::kTripCountInBody: @@ -1285,8 +1440,8 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, *result = graph->GetConstant(type, 0); } return true; - } else if (in_body) { - if (GenerateCode(info->op_a, trip, graph, block, &opb, in_body, is_min)) { + } else if (IsContextInBody(context, loop)) { + if (GenerateCode(context, loop, info->op_a, trip, graph, block, is_min, &opb)) { if (graph != nullptr) { ArenaAllocator* allocator = graph->GetAllocator(); *result = @@ -1309,11 +1464,11 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, // TODO: careful runtime type conversions could generalize this latter restriction. if (!HInductionVarAnalysis::IsNarrowingLinear(info) && trip->type == type) { int64_t stride_value = 0; - if (IsConstant(info->op_a, kExact, &stride_value) && + if (IsConstant(context, loop, info->op_a, kExact, &stride_value) && CanLongValueFitIntoInt(stride_value)) { const bool is_min_a = stride_value >= 0 ? is_min : !is_min; - if (GenerateCode(trip, trip, graph, block, &opa, in_body, is_min_a) && - GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) { + if (GenerateCode(context, loop, trip, trip, graph, block, is_min_a, &opa) && + GenerateCode(context, loop, info->op_b, trip, graph, block, is_min, &opb)) { if (graph != nullptr) { ArenaAllocator* allocator = graph->GetAllocator(); HInstruction* oper; @@ -1341,7 +1496,7 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, case HInductionVarAnalysis::kPeriodic: { // Wrap-around and periodic inductions are restricted to constants only, so that extreme // values are easy to test at runtime without complications of arithmetic wrap-around. - Value extreme = GetVal(info, trip, in_body, is_min); + Value extreme = GetVal(context, loop, info, trip, is_min); if (IsConstantValue(extreme)) { if (graph != nullptr) { *result = graph->GetConstant(type, extreme.b_constant); |