diff options
| -rw-r--r-- | compiler/optimizing/induction_var_analysis.cc | 98 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_analysis.h | 4 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_range.cc | 359 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_range.h | 25 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_range_test.cc | 101 | ||||
| -rw-r--r-- | test/530-checker-loops/src/Main.java | 230 |
6 files changed, 586 insertions, 231 deletions
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc index 37f2d79536..a1e1cde9df 100644 --- a/compiler/optimizing/induction_var_analysis.cc +++ b/compiler/optimizing/induction_var_analysis.cc @@ -379,7 +379,7 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferShl(Inducti Primitive::Type type) { // Transfer over a shift left: treat shift by restricted constant as equivalent multiplication. int64_t value = -1; - if (a != nullptr && IsIntAndGet(b, &value)) { + if (a != nullptr && IsExact(b, &value)) { // Obtain the constant needed for the multiplication. This yields an existing instruction // if the constants is already there. Otherwise, this has a side effect on the HIR. // The restriction on the shift factor avoids generating a negative constant @@ -546,9 +546,10 @@ void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, // Analyze condition with induction at left-hand-side (e.g. i < U). InductionInfo* lower_expr = a->op_b; InductionInfo* upper_expr = b; - InductionInfo* stride = a->op_a; + InductionInfo* stride_expr = a->op_a; + // Constant stride? int64_t stride_value = 0; - if (!IsIntAndGet(stride, &stride_value)) { + if (!IsExact(stride_expr, &stride_value)) { return; } // Rewrite condition i != U into i < U or i > U if end condition is reached exactly. @@ -561,7 +562,7 @@ void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, // stride < 0, either i > U or i >= U if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) || (stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) { - VisitTripCount(loop, lower_expr, upper_expr, stride, stride_value, type, cmp); + VisitTripCount(loop, lower_expr, upper_expr, stride_expr, stride_value, type, cmp); } } } @@ -569,7 +570,7 @@ void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, InductionInfo* lower_expr, InductionInfo* upper_expr, - InductionInfo* stride, + InductionInfo* stride_expr, int64_t stride_value, Primitive::Type type, IfCondition cmp) { @@ -612,9 +613,10 @@ void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, trip_count = CreateInvariantOp(kAdd, trip_count, CreateConstant(1, type)); } // Compensate for stride. - trip_count = CreateInvariantOp(kAdd, trip_count, stride); + trip_count = CreateInvariantOp(kAdd, trip_count, stride_expr); } - trip_count = CreateInvariantOp(kDiv, CreateInvariantOp(kSub, trip_count, lower_expr), stride); + trip_count = CreateInvariantOp( + kDiv, CreateInvariantOp(kSub, trip_count, lower_expr), stride_expr); // Assign the trip-count expression to the loop control. Clients that use the information // should be aware that the expression is only valid under the conditions listed above. InductionOp tcKind = kTripCountInBodyUnsafe; // needs both tests @@ -644,14 +646,25 @@ bool HInductionVarAnalysis::IsTaken(InductionInfo* lower_expr, IfCondition cmp) { int64_t lower_value; int64_t upper_value; - if (IsIntAndGet(lower_expr, &lower_value) && IsIntAndGet(upper_expr, &upper_value)) { - switch (cmp) { - case kCondLT: return lower_value < upper_value; - case kCondLE: return lower_value <= upper_value; - case kCondGT: return lower_value > upper_value; - case kCondGE: return lower_value >= upper_value; - default: LOG(FATAL) << "CONDITION UNREACHABLE"; - } + switch (cmp) { + case kCondLT: + return IsAtMost(lower_expr, &lower_value) + && IsAtLeast(upper_expr, &upper_value) + && lower_value < upper_value; + case kCondLE: + return IsAtMost(lower_expr, &lower_value) + && IsAtLeast(upper_expr, &upper_value) + && lower_value <= upper_value; + case kCondGT: + return IsAtLeast(lower_expr, &lower_value) + && IsAtMost(upper_expr, &upper_value) + && lower_value > upper_value; + case kCondGE: + return IsAtLeast(lower_expr, &lower_value) + && IsAtMost(upper_expr, &upper_value) + && lower_value >= upper_value; + default: + LOG(FATAL) << "CONDITION UNREACHABLE"; } return false; // not certain, may be untaken } @@ -660,25 +673,23 @@ bool HInductionVarAnalysis::IsFinite(InductionInfo* upper_expr, int64_t stride_value, Primitive::Type type, IfCondition cmp) { - const int64_t min = type == Primitive::kPrimInt - ? std::numeric_limits<int32_t>::min() - : std::numeric_limits<int64_t>::min(); - const int64_t max = type == Primitive::kPrimInt - ? std::numeric_limits<int32_t>::max() - : std::numeric_limits<int64_t>::max(); + const int64_t min = type == Primitive::kPrimInt ? std::numeric_limits<int32_t>::min() + : std::numeric_limits<int64_t>::min(); + const int64_t max = type == Primitive::kPrimInt ? std::numeric_limits<int32_t>::max() + : std::numeric_limits<int64_t>::max(); // Some rules under which it is certain at compile-time that the loop is finite. int64_t value; switch (cmp) { case kCondLT: return stride_value == 1 || - (IsIntAndGet(upper_expr, &value) && value <= (max - stride_value + 1)); + (IsAtMost(upper_expr, &value) && value <= (max - stride_value + 1)); case kCondLE: - return (IsIntAndGet(upper_expr, &value) && value <= (max - stride_value)); + return (IsAtMost(upper_expr, &value) && value <= (max - stride_value)); case kCondGT: return stride_value == -1 || - (IsIntAndGet(upper_expr, &value) && value >= (min - stride_value - 1)); + (IsAtLeast(upper_expr, &value) && value >= (min - stride_value - 1)); case kCondGE: - return (IsIntAndGet(upper_expr, &value) && value >= (min - stride_value)); + return (IsAtLeast(upper_expr, &value) && value >= (min - stride_value)); default: LOG(FATAL) << "CONDITION UNREACHABLE"; } @@ -733,7 +744,7 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv // More exhaustive simplifications are done by later phases once induction nodes are // translated back into HIR code (e.g. by loop optimizations or BCE). int64_t value = -1; - if (IsIntAndGet(a, &value)) { + if (IsExact(a, &value)) { if (value == 0) { // Simplify 0 + b = b, 0 * b = 0. if (op == kAdd) { @@ -750,7 +761,7 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv } } } - if (IsIntAndGet(b, &value)) { + if (IsExact(b, &value)) { if (value == 0) { // Simplify a + 0 = a, a - 0 = a, a * 0 = 0, -0 = 0. if (op == kAdd || op == kSub) { @@ -784,29 +795,16 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr); } -bool HInductionVarAnalysis::IsIntAndGet(InductionInfo* info, int64_t* value) { - if (info != nullptr && info->induction_class == kInvariant) { - // A direct constant fetch. - if (info->operation == kFetch) { - DCHECK(info->fetch); - if (info->fetch->IsIntConstant()) { - *value = info->fetch->AsIntConstant()->GetValue(); - return true; - } else if (info->fetch->IsLongConstant()) { - *value = info->fetch->AsLongConstant()->GetValue(); - return true; - } - } - // Use range analysis to resolve compound values. - InductionVarRange range(this); - int32_t min_val = 0; - int32_t max_val = 0; - if (range.IsConstantRange(info, &min_val, &max_val) && min_val == max_val) { - *value = min_val; - return true; - } - } - return false; +bool HInductionVarAnalysis::IsExact(InductionInfo* info, int64_t* value) { + return InductionVarRange(this).IsConstant(info, InductionVarRange::kExact, value); +} + +bool HInductionVarAnalysis::IsAtMost(InductionInfo* info, int64_t* value) { + return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtMost, value); +} + +bool HInductionVarAnalysis::IsAtLeast(InductionInfo* info, int64_t* value) { + return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtLeast, value); } bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1, diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h index 84d5d82568..94d2646aec 100644 --- a/compiler/optimizing/induction_var_analysis.h +++ b/compiler/optimizing/induction_var_analysis.h @@ -189,7 +189,9 @@ class HInductionVarAnalysis : public HOptimization { InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b); // Constants. - bool IsIntAndGet(InductionInfo* info, int64_t* value); + bool IsExact(InductionInfo* info, /*out*/ int64_t* value); + bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value); + bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value); // Helpers. static bool InductionEqual(InductionInfo* info1, InductionInfo* info2); diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc index 9566c29adf..b162696a42 100644 --- a/compiler/optimizing/induction_var_range.cc +++ b/compiler/optimizing/induction_var_range.cc @@ -45,17 +45,14 @@ static bool IsSafeDiv(int32_t c1, int32_t c2) { return c2 != 0 && CanLongValueFitIntoInt(static_cast<int64_t>(c1) / static_cast<int64_t>(c2)); } -/** Returns true for 32/64-bit integral constant. */ -static bool IsIntAndGet(HInstruction* instruction, int32_t* value) { +/** Returns true for 32/64-bit constant instruction. */ +static bool IsIntAndGet(HInstruction* instruction, int64_t* value) { if (instruction->IsIntConstant()) { *value = instruction->AsIntConstant()->GetValue(); return true; } else if (instruction->IsLongConstant()) { - const int64_t c = instruction->AsLongConstant()->GetValue(); - if (CanLongValueFitIntoInt(c)) { - *value = static_cast<int32_t>(c); - return true; - } + *value = instruction->AsLongConstant()->GetValue(); + return true; } return false; } @@ -65,8 +62,9 @@ static bool IsIntAndGet(HInstruction* instruction, int32_t* value) { * because length >= 0 is true. This makes it more likely the bound is useful to clients. */ static InductionVarRange::Value SimplifyMax(InductionVarRange::Value v) { - int32_t value; - if (v.a_constant > 1 && + int64_t value; + if (v.is_known && + v.a_constant > 1 && v.instruction->IsDiv() && v.instruction->InputAt(0)->IsArrayLength() && IsIntAndGet(v.instruction->InputAt(1), &value) && v.a_constant == value) { @@ -75,6 +73,16 @@ static InductionVarRange::Value SimplifyMax(InductionVarRange::Value v) { return v; } +/** Helper method to test for a constant value. */ +static bool IsConstantValue(InductionVarRange::Value v) { + return v.is_known && v.a_constant == 0; +} + +/** Helper method to test for same constant value. */ +static bool IsSameConstantValue(InductionVarRange::Value v1, InductionVarRange::Value v2) { + return IsConstantValue(v1) && IsConstantValue(v2) && v1.b_constant == v2.b_constant; +} + /** Helper method to insert an instruction. */ static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) { DCHECK(block != nullptr); @@ -99,29 +107,45 @@ bool InductionVarRange::GetInductionRange(HInstruction* context, /*out*/Value* max_val, /*out*/bool* needs_finite_test) { HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop - if (loop != nullptr) { - // Set up loop information. - HBasicBlock* header = loop->GetHeader(); - bool in_body = context->GetBlock() != header; - HInductionVarAnalysis::InductionInfo* info = - induction_analysis_->LookupInfo(loop, instruction); - HInductionVarAnalysis::InductionInfo* trip = - induction_analysis_->LookupInfo(loop, header->GetLastInstruction()); - // Find range. - *min_val = GetVal(info, trip, in_body, /* is_min */ true); - *max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min */ false)); - *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip); - return true; + if (loop == nullptr) { + return false; // no loop + } + HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, instruction); + if (info == nullptr) { + return false; // no induction information } - return false; // Nothing known + // Set up loop information. + HBasicBlock* header = loop->GetHeader(); + bool in_body = context->GetBlock() != header; + HInductionVarAnalysis::InductionInfo* trip = + induction_analysis_->LookupInfo(loop, header->GetLastInstruction()); + // Find range. + *min_val = GetVal(info, trip, in_body, /* is_min */ true); + *max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min */ false)); + *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip); + return true; } -bool InductionVarRange::RefineOuter(/*in-out*/Value* min_val, /*in-out*/Value* max_val) const { - Value v1 = RefineOuter(*min_val, /* is_min */ true); - Value v2 = RefineOuter(*max_val, /* is_min */ false); - if (v1.instruction != min_val->instruction || v2.instruction != max_val->instruction) { - *min_val = v1; - *max_val = v2; +bool InductionVarRange::RefineOuter(/*in-out*/ Value* min_val, + /*in-out*/ Value* max_val) const { + Value v1_min = RefineOuter(*min_val, /* is_min */ true); + Value v2_max = RefineOuter(*max_val, /* is_min */ false); + // The refined range is safe if both sides refine the same instruction. Otherwise, since two + // different ranges are combined, the new refined range is safe to pass back to the client if + // the extremes of the computed ranges ensure no arithmetic wrap-around anomalies occur. + if (min_val->instruction != max_val->instruction) { + Value v1_max = RefineOuter(*min_val, /* is_min */ false); + Value v2_min = RefineOuter(*max_val, /* is_min */ true); + if (!IsConstantValue(v1_max) || + !IsConstantValue(v2_min) || + v1_max.b_constant > v2_min.b_constant) { + return false; + } + } + // Did something change? + if (v1_min.instruction != min_val->instruction || v2_max.instruction != max_val->instruction) { + *min_val = v1_min; + *max_val = v2_max; return true; } return false; @@ -164,6 +188,38 @@ void InductionVarRange::GenerateTakenTest(HInstruction* context, // Private class methods. // +bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info, + ConstantRequest request, + /*out*/ int64_t *value) const { + if (info != nullptr) { + // A direct 32-bit or 64-bit constant fetch. This immediately satisfies + // any of the three requests (kExact, kAtMost, and KAtLeast). + if (info->induction_class == HInductionVarAnalysis::kInvariant && + info->operation == HInductionVarAnalysis::kFetch) { + if (IsIntAndGet(info->fetch, value)) { + return true; + } + } + // Try range analysis while traversing outward on loops. + bool in_body = true; // no known trip count + Value v_min = GetVal(info, nullptr, in_body, /* is_min */ true); + Value v_max = GetVal(info, nullptr, in_body, /* is_min */ false); + do { + // Make sure *both* extremes are known to avoid arithmetic wrap-around anomalies. + if (IsConstantValue(v_min) && IsConstantValue(v_max) && v_min.b_constant <= v_max.b_constant) { + if ((request == kExact && v_min.b_constant == v_max.b_constant) || request == kAtMost) { + *value = v_max.b_constant; + return true; + } else if (request == kAtLeast) { + *value = v_min.b_constant; + return true; + } + } + } while (RefineOuter(&v_min, &v_max)); + } + return false; +} + bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const { if (info != nullptr) { if (info->induction_class == HInductionVarAnalysis::kLinear) { @@ -206,12 +262,10 @@ InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::Ind if (trip != nullptr) { HInductionVarAnalysis::InductionInfo* trip_expr = trip->op_a; if (trip_expr->operation == HInductionVarAnalysis::kSub) { - int32_t min_value = 0; - int32_t stride_value = 0; - if (IsConstantRange(info->op_a, &min_value, &stride_value) && min_value == stride_value) { + int64_t stride_value = 0; + if (IsConstant(info->op_a, kExact, &stride_value)) { if (!is_min && stride_value == 1) { - // Test original trip's negative operand (trip_expr->op_b) against - // the offset of the linear induction. + // Test original trip's negative operand (trip_expr->op_b) against offset of induction. if (HInductionVarAnalysis::InductionEqual(trip_expr->op_b, info->op_b)) { // Analyze cancelled trip with just the positive operand (trip_expr->op_a). HInductionVarAnalysis::InductionInfo cancelled_trip( @@ -219,8 +273,7 @@ InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::Ind return GetVal(&cancelled_trip, trip, in_body, is_min); } } else if (is_min && stride_value == -1) { - // Test original trip's positive operand (trip_expr->op_a) against - // the offset of the linear induction. + // Test original trip's positive operand (trip_expr->op_a) against offset of induction. if (HInductionVarAnalysis::InductionEqual(trip_expr->op_a, info->op_b)) { // Analyze cancelled trip with just the negative operand (trip_expr->op_b). HInductionVarAnalysis::InductionInfo neg( @@ -248,14 +301,16 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, bool is_min) const { // Detect constants and chase the fetch a bit deeper into the HIR tree, so that it becomes // more likely range analysis will compare the same instructions as terminal nodes. - int32_t value; - if (IsIntAndGet(instruction, &value)) { - return Value(value); + int64_t value; + if (IsIntAndGet(instruction, &value) && CanLongValueFitIntoInt(value)) { + return Value(static_cast<int32_t>(value)); } else if (instruction->IsAdd()) { - if (IsIntAndGet(instruction->InputAt(0), &value)) { - return AddValue(Value(value), GetFetch(instruction->InputAt(1), trip, in_body, is_min)); - } else if (IsIntAndGet(instruction->InputAt(1), &value)) { - return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min), Value(value)); + if (IsIntAndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) { + return AddValue(Value(static_cast<int32_t>(value)), + GetFetch(instruction->InputAt(1), trip, in_body, is_min)); + } else if (IsIntAndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) { + return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min), + Value(static_cast<int32_t>(value))); } } else if (instruction->IsArrayLength() && instruction->InputAt(0)->IsNewArray()) { return GetFetch(instruction->InputAt(0)->InputAt(0), trip, in_body, is_min); @@ -331,29 +386,30 @@ InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::Induct 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); - // Try to refine certain failure. - if (v1_min.a_constant && v1_max.a_constant) { - v1_min = RefineOuter(v1_min, /* is_min */ true); - v1_max = RefineOuter(v1_max, /* is_min */ false); - } - // Positive or negative range? - if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant >= 0) { - // Positive range vs. positive or negative range. - if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) { - return is_min ? MulValue(v1_min, v2_min) - : MulValue(v1_max, v2_max); - } else if (v2_max.is_known && v2_max.a_constant == 0 && v2_max.b_constant <= 0) { - return is_min ? MulValue(v1_max, v2_min) - : MulValue(v1_min, v2_max); + // Try to refine first operand. + if (!IsConstantValue(v1_min) && !IsConstantValue(v1_max)) { + RefineOuter(&v1_min, &v1_max); + } + // Constant times range. + if (IsSameConstantValue(v1_min, v1_max)) { + return MulRangeAndConstant(v2_min, v2_max, v1_min, is_min); + } else if (IsSameConstantValue(v2_min, v2_max)) { + return MulRangeAndConstant(v1_min, v1_max, v2_min, is_min); + } + // 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) { + return is_min ? MulValue(v1_min, v2_min) : MulValue(v1_max, v2_max); + } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { + return is_min ? MulValue(v1_max, v2_min) : MulValue(v1_min, v2_max); } - } else if (v1_max.is_known && v1_max.a_constant == 0 && v1_max.b_constant <= 0) { - // Negative range vs. positive or negative range. - if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) { - return is_min ? MulValue(v1_min, v2_max) - : MulValue(v1_max, v2_min); - } else if (v2_max.is_known && v2_max.a_constant == 0 && v2_max.b_constant <= 0) { - return is_min ? MulValue(v1_max, v2_max) - : MulValue(v1_min, v2_min); + } + // Negative range vs. positive or negative range. + if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) { + if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { + return is_min ? MulValue(v1_min, v2_max) : MulValue(v1_max, v2_min); + } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { + return is_min ? MulValue(v1_max, v2_max) : MulValue(v1_min, v2_min); } } return Value(); @@ -368,43 +424,41 @@ InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::Induct 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); - // Positive or negative range? - if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant >= 0) { - // Positive range vs. positive or negative range. - if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) { - return is_min ? DivValue(v1_min, v2_max) - : DivValue(v1_max, v2_min); - } else if (v2_max.is_known && v2_max.a_constant == 0 && v2_max.b_constant <= 0) { - return is_min ? DivValue(v1_max, v2_max) - : DivValue(v1_min, v2_min); + // Range divided by constant. + if (IsSameConstantValue(v2_min, v2_max)) { + return DivRangeAndConstant(v1_min, v1_max, v2_min, is_min); + } + // 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) { + return is_min ? DivValue(v1_min, v2_max) : DivValue(v1_max, v2_min); + } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { + return is_min ? DivValue(v1_max, v2_max) : DivValue(v1_min, v2_min); } - } else if (v1_max.is_known && v1_max.a_constant == 0 && v1_max.b_constant <= 0) { - // Negative range vs. positive or negative range. - if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) { - return is_min ? DivValue(v1_min, v2_min) - : DivValue(v1_max, v2_max); - } else if (v2_max.is_known && v2_max.a_constant == 0 && v2_max.b_constant <= 0) { - return is_min ? DivValue(v1_max, v2_min) - : DivValue(v1_min, v2_max); + } + // Negative range vs. positive or negative range. + if (IsConstantValue(v1_max) && v1_max.b_constant <= 0) { + if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) { + return is_min ? DivValue(v1_min, v2_min) : DivValue(v1_max, v2_max); + } else if (IsConstantValue(v2_max) && v2_max.b_constant <= 0) { + return is_min ? DivValue(v1_max, v2_min) : DivValue(v1_min, v2_max); } } return Value(); } -bool InductionVarRange::IsConstantRange(HInductionVarAnalysis::InductionInfo* info, - int32_t *min_value, - int32_t *max_value) const { - bool in_body = true; // no known trip count - Value v_min = GetVal(info, nullptr, in_body, /* is_min */ true); - Value v_max = GetVal(info, nullptr, in_body, /* is_min */ false); - do { - if (v_min.is_known && v_min.a_constant == 0 && v_max.is_known && v_max.a_constant == 0) { - *min_value = v_min.b_constant; - *max_value = v_max.b_constant; - return true; - } - } while (RefineOuter(&v_min, &v_max)); - return false; +InductionVarRange::Value InductionVarRange::MulRangeAndConstant(Value v_min, + Value v_max, + Value c, + bool is_min) const { + return is_min == (c.b_constant >= 0) ? MulValue(v_min, c) : MulValue(v_max, c); +} + +InductionVarRange::Value InductionVarRange::DivRangeAndConstant(Value v_min, + Value v_max, + Value c, + bool is_min) const { + return is_min == (c.b_constant >= 0) ? DivValue(v_min, c) : DivValue(v_max, c); } InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) const { @@ -471,22 +525,25 @@ InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is } InductionVarRange::Value InductionVarRange::RefineOuter(Value v, bool is_min) const { - if (v.instruction != nullptr) { - HLoopInformation* loop = - v.instruction->GetBlock()->GetLoopInformation(); // closest enveloping loop - if (loop != nullptr) { - // Set up loop information. - bool in_body = true; // use is always in body of outer loop - HInductionVarAnalysis::InductionInfo* info = - induction_analysis_->LookupInfo(loop, v.instruction); - HInductionVarAnalysis::InductionInfo* trip = - induction_analysis_->LookupInfo(loop, loop->GetHeader()->GetLastInstruction()); - // Try to refine "a x instruction + b" with outer loop range information on instruction. - return AddValue(MulValue(Value(v.a_constant), GetVal(info, trip, in_body, is_min)), - Value(v.b_constant)); - } + if (v.instruction == nullptr) { + return v; // nothing to refine } - return v; + HLoopInformation* loop = + v.instruction->GetBlock()->GetLoopInformation(); // closest enveloping loop + if (loop == nullptr) { + return v; // no loop + } + HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, v.instruction); + if (info == nullptr) { + return v; // no induction information + } + // Set up loop information. + HBasicBlock* header = loop->GetHeader(); + bool in_body = true; // inner always in more outer + HInductionVarAnalysis::InductionInfo* trip = + induction_analysis_->LookupInfo(loop, header->GetLastInstruction()); + // Try to refine "a x instruction + b" with outer loop range information on instruction. + return AddValue(MulValue(Value(v.a_constant), GetVal(info, trip, in_body, is_min)), Value(v.b_constant)); } bool InductionVarRange::GenerateCode(HInstruction* context, @@ -499,44 +556,45 @@ bool InductionVarRange::GenerateCode(HInstruction* context, /*out*/bool* needs_finite_test, /*out*/bool* needs_taken_test) const { HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop - if (loop != nullptr) { - // Set up loop information. - HBasicBlock* header = loop->GetHeader(); - bool in_body = context->GetBlock() != header; - HInductionVarAnalysis::InductionInfo* info = - induction_analysis_->LookupInfo(loop, instruction); - if (info == nullptr) { - return false; // nothing to analyze - } - HInductionVarAnalysis::InductionInfo* trip = - induction_analysis_->LookupInfo(loop, header->GetLastInstruction()); - // Determine what tests are needed. A finite test is needed if the evaluation code uses the - // trip-count and the loop maybe unsafe (because in such cases, the index could "overshoot" - // 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). - *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip); - *needs_taken_test = IsBodyTripCount(trip); - // 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); - } else if (*needs_taken_test) { - if (!GenerateCode( - trip->op_b, nullptr, nullptr, nullptr, nullptr, in_body, /* is_min */ false)) { - return false; - } + if (loop == nullptr) { + return false; // no loop + } + HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, instruction); + if (info == nullptr) { + return false; // no induction information + } + // Set up loop information. + HBasicBlock* header = loop->GetHeader(); + bool in_body = context->GetBlock() != header; + HInductionVarAnalysis::InductionInfo* trip = + induction_analysis_->LookupInfo(loop, header->GetLastInstruction()); + if (trip == nullptr) { + return false; // codegen relies on trip count + } + // Determine what tests are needed. A finite test is needed if the evaluation code uses the + // trip-count and the loop maybe unsafe (because in such cases, the index could "overshoot" + // 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). + *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip); + *needs_taken_test = IsBodyTripCount(trip); + // 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); + } else if (*needs_taken_test) { + if (!GenerateCode( + trip->op_b, nullptr, nullptr, nullptr, nullptr, in_body, /* is_min */ false)) { + return false; } - // Code generation for lower and upper. - 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)) && - // And success on upper. - GenerateCode(info, trip, graph, block, upper, in_body, /* is_min */ false); } - return false; + // Code generation for lower and upper. + 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)) && + // And success on upper. + GenerateCode(info, trip, graph, block, upper, in_body, /* is_min */ false); } bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, @@ -639,9 +697,8 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, case HInductionVarAnalysis::kLinear: { // Linear induction a * i + b, for normalized 0 <= i < TC. Restrict to unit stride only // to avoid arithmetic wrap-around situations that are hard to guard against. - int32_t min_value = 0; - int32_t stride_value = 0; - if (IsConstantRange(info->op_a, &min_value, &stride_value) && min_value == stride_value) { + int64_t stride_value = 0; + if (IsConstant(info->op_a, kExact, &stride_value)) { if (stride_value == 1 || stride_value == -1) { const bool is_min_a = stride_value == 1 ? is_min : !is_min; if (GenerateCode(trip, trip, graph, block, &opa, in_body, is_min_a) && @@ -666,7 +723,7 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, // 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); - if (extreme.is_known && extreme.a_constant == 0) { + if (IsConstantValue(extreme)) { if (graph != nullptr) { *result = graph->GetIntConstant(extreme.b_constant); } diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h index 3cb7b4bfd5..0af41560ff 100644 --- a/compiler/optimizing/induction_var_range.h +++ b/compiler/optimizing/induction_var_range.h @@ -69,7 +69,8 @@ class InductionVarRange { /*out*/ bool* needs_finite_test); /** Refines the values with induction of next outer loop. Returns true on change. */ - bool RefineOuter(/*in-out*/Value* min_val, /*in-out*/Value* max_val) const; + bool RefineOuter(/*in-out*/ Value* min_val, + /*in-out*/ Value* max_val) const; /** * Returns true if range analysis is able to generate code for the lower and upper @@ -116,6 +117,23 @@ class InductionVarRange { /*out*/ HInstruction** taken_test); private: + /* + * Enum used in IsConstant() request. + */ + enum ConstantRequest { + kExact, + kAtMost, + kAtLeast + }; + + /** + * Returns true if exact or upper/lower bound on the given induction + * information is known as a 64-bit constant, which is returned in value. + */ + bool IsConstant(HInductionVarAnalysis::InductionInfo* info, + ConstantRequest request, + /*out*/ int64_t *value) const; + bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const; bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const; bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const; @@ -143,9 +161,8 @@ class InductionVarRange { bool in_body, bool is_min) const; - bool IsConstantRange(HInductionVarAnalysis::InductionInfo* info, - int32_t *min_value, - int32_t *max_value) const; + Value MulRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const; + Value DivRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const; Value AddValue(Value v1, Value v2) const; Value SubValue(Value v1, Value v2) const; diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc index 55a654e301..c5c33bd9bc 100644 --- a/compiler/optimizing/induction_var_range_test.cc +++ b/compiler/optimizing/induction_var_range_test.cc @@ -215,10 +215,16 @@ class InductionVarRangeTest : public CommonCompilerTest { return range_.GetDiv(info1, info2, nullptr, /* in_body */ true, is_min); } - bool IsConstantRange(HInductionVarAnalysis::InductionInfo* info, - int32_t* min_value, - int32_t* max_value) { - return range_.IsConstantRange(info, min_value, max_value); + bool IsExact(HInductionVarAnalysis::InductionInfo* info, int64_t* value) { + return range_.IsConstant(info, InductionVarRange::kExact, value); + } + + bool IsAtMost(HInductionVarAnalysis::InductionInfo* info, int64_t* value) { + return range_.IsConstant(info, InductionVarRange::kAtMost, value); + } + + bool IsAtLeast(HInductionVarAnalysis::InductionInfo* info, int64_t* value) { + return range_.IsConstant(info, InductionVarRange::kAtLeast, value); } Value AddValue(Value v1, Value v2) { return range_.AddValue(v1, v2); } @@ -249,6 +255,34 @@ class InductionVarRangeTest : public CommonCompilerTest { // Tests on private methods. // +TEST_F(InductionVarRangeTest, IsConstant) { + int64_t value; + // Constant. + EXPECT_TRUE(IsExact(CreateConst(12345), &value)); + EXPECT_EQ(12345, value); + EXPECT_TRUE(IsAtMost(CreateConst(12345), &value)); + EXPECT_EQ(12345, value); + EXPECT_TRUE(IsAtLeast(CreateConst(12345), &value)); + EXPECT_EQ(12345, value); + // Constant trivial range. + EXPECT_TRUE(IsExact(CreateRange(111, 111), &value)); + EXPECT_EQ(111, value); + EXPECT_TRUE(IsAtMost(CreateRange(111, 111), &value)); + EXPECT_EQ(111, value); + EXPECT_TRUE(IsAtLeast(CreateRange(111, 111), &value)); + EXPECT_EQ(111, value); + // Constant non-trivial range. + EXPECT_FALSE(IsExact(CreateRange(11, 22), &value)); + EXPECT_TRUE(IsAtMost(CreateRange(11, 22), &value)); + EXPECT_EQ(22, value); + EXPECT_TRUE(IsAtLeast(CreateRange(11, 22), &value)); + EXPECT_EQ(11, value); + // Symbolic. + EXPECT_FALSE(IsExact(CreateFetch(x_), &value)); + EXPECT_FALSE(IsAtMost(CreateFetch(x_), &value)); + EXPECT_FALSE(IsAtLeast(CreateFetch(x_), &value)); +} + TEST_F(InductionVarRangeTest, TripCountProperties) { EXPECT_FALSE(NeedsTripCount(nullptr)); EXPECT_FALSE(NeedsTripCount(CreateConst(1))); @@ -367,6 +401,10 @@ TEST_F(InductionVarRangeTest, GetMinMaxPeriodic) { } TEST_F(InductionVarRangeTest, GetMulMin) { + ExpectEqual(Value(-14), GetMul(CreateConst(2), CreateRange(-7, 8), true)); + ExpectEqual(Value(-16), GetMul(CreateConst(-2), CreateRange(-7, 8), true)); + ExpectEqual(Value(-14), GetMul(CreateRange(-7, 8), CreateConst(2), true)); + ExpectEqual(Value(-16), GetMul(CreateRange(-7, 8), CreateConst(-2), true)); ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), true)); ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), true)); ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), true)); @@ -379,6 +417,10 @@ TEST_F(InductionVarRangeTest, GetMulMin) { } TEST_F(InductionVarRangeTest, GetMulMax) { + ExpectEqual(Value(16), GetMul(CreateConst(2), CreateRange(-7, 8), false)); + ExpectEqual(Value(14), GetMul(CreateConst(-2), CreateRange(-7, 8), false)); + ExpectEqual(Value(16), GetMul(CreateRange(-7, 8), CreateConst(2), false)); + ExpectEqual(Value(14), GetMul(CreateRange(-7, 8), CreateConst(-2), false)); ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), false)); ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), false)); ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), false)); @@ -391,6 +433,8 @@ TEST_F(InductionVarRangeTest, GetMulMax) { } TEST_F(InductionVarRangeTest, GetDivMin) { + ExpectEqual(Value(-5), GetDiv(CreateRange(-10, 20), CreateConst(2), true)); + ExpectEqual(Value(-10), GetDiv(CreateRange(-10, 20), CreateConst(-2), true)); ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), true)); ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), true)); ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), true)); @@ -403,6 +447,8 @@ TEST_F(InductionVarRangeTest, GetDivMin) { } TEST_F(InductionVarRangeTest, GetDivMax) { + ExpectEqual(Value(10), GetDiv(CreateRange(-10, 20), CreateConst(2), false)); + ExpectEqual(Value(5), GetDiv(CreateRange(-10, 20), CreateConst(-2), false)); ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), false)); ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), false)); ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), false)); @@ -414,18 +460,6 @@ TEST_F(InductionVarRangeTest, GetDivMax) { ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), false)); } -TEST_F(InductionVarRangeTest, IsConstantRange) { - int32_t min_value; - int32_t max_value; - ASSERT_TRUE(IsConstantRange(CreateConst(12345), &min_value, &max_value)); - EXPECT_EQ(12345, min_value); - EXPECT_EQ(12345, max_value); - ASSERT_TRUE(IsConstantRange(CreateRange(1, 2), &min_value, &max_value)); - EXPECT_EQ(1, min_value); - EXPECT_EQ(2, max_value); - EXPECT_FALSE(IsConstantRange(CreateFetch(x_), &min_value, &max_value)); -} - TEST_F(InductionVarRangeTest, AddValue) { ExpectEqual(Value(110), AddValue(Value(10), Value(100))); ExpectEqual(Value(-5), AddValue(Value(x_, 1, -4), Value(x_, -1, -1))); @@ -459,6 +493,24 @@ TEST_F(InductionVarRangeTest, MulValue) { ExpectEqual(Value(), MulValue(Value(90000), Value(-90000))); // unsafe } +TEST_F(InductionVarRangeTest, MulValueSpecial) { + const int32_t min_value = std::numeric_limits<int32_t>::min(); + const int32_t max_value = std::numeric_limits<int32_t>::max(); + + // Unsafe. + ExpectEqual(Value(), MulValue(Value(min_value), Value(min_value))); + ExpectEqual(Value(), MulValue(Value(min_value), Value(-1))); + ExpectEqual(Value(), MulValue(Value(min_value), Value(max_value))); + ExpectEqual(Value(), MulValue(Value(max_value), Value(max_value))); + + // Safe. + ExpectEqual(Value(min_value), MulValue(Value(min_value), Value(1))); + ExpectEqual(Value(max_value), MulValue(Value(max_value), Value(1))); + ExpectEqual(Value(-max_value), MulValue(Value(max_value), Value(-1))); + ExpectEqual(Value(-1), MulValue(Value(1), Value(-1))); + ExpectEqual(Value(1), MulValue(Value(-1), Value(-1))); +} + TEST_F(InductionVarRangeTest, DivValue) { ExpectEqual(Value(25), DivValue(Value(100), Value(4))); ExpectEqual(Value(), DivValue(Value(x_, 1, -4), Value(x_, 1, -1))); @@ -468,6 +520,23 @@ TEST_F(InductionVarRangeTest, DivValue) { ExpectEqual(Value(), DivValue(Value(1), Value(0))); // unsafe } +TEST_F(InductionVarRangeTest, DivValueSpecial) { + const int32_t min_value = std::numeric_limits<int32_t>::min(); + const int32_t max_value = std::numeric_limits<int32_t>::max(); + + // Unsafe. + ExpectEqual(Value(), DivValue(Value(min_value), Value(-1))); + + // Safe. + ExpectEqual(Value(1), DivValue(Value(min_value), Value(min_value))); + ExpectEqual(Value(1), DivValue(Value(max_value), Value(max_value))); + ExpectEqual(Value(min_value), DivValue(Value(min_value), Value(1))); + ExpectEqual(Value(max_value), DivValue(Value(max_value), Value(1))); + ExpectEqual(Value(-max_value), DivValue(Value(max_value), Value(-1))); + ExpectEqual(Value(-1), DivValue(Value(1), Value(-1))); + ExpectEqual(Value(1), DivValue(Value(-1), Value(-1))); +} + TEST_F(InductionVarRangeTest, MinValue) { ExpectEqual(Value(10), MinValue(Value(10), Value(100))); ExpectEqual(Value(x_, 1, -4), MinValue(Value(x_, 1, -4), Value(x_, 1, -1))); diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java index deff279f77..9f344dda11 100644 --- a/test/530-checker-loops/src/Main.java +++ b/test/530-checker-loops/src/Main.java @@ -471,7 +471,7 @@ public class Main { // /// CHECK-START: void Main.linearTriangularOnTwoArrayLengths(int) BCE (after) /// CHECK-NOT: BoundsCheck - /// CHECK-NOT: Deoptimize + // TODO: also CHECK-NOT: Deoptimize, see b/27151190 private static void linearTriangularOnTwoArrayLengths(int n) { int[] a = new int[n]; for (int i = 0; i < a.length; i++) { @@ -513,7 +513,7 @@ public class Main { // /// CHECK-START: void Main.linearTriangularOnParameter(int) BCE (after) /// CHECK-NOT: BoundsCheck - /// CHECK-NOT: Deoptimize + // TODO: also CHECK-NOT: Deoptimize, see b/27151190 private static void linearTriangularOnParameter(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) { @@ -528,22 +528,22 @@ public class Main { } } - /// CHECK-START: void Main.linearTriangularVariations(int) BCE (before) + /// CHECK-START: void Main.linearTriangularVariationsInnerStrict(int) BCE (before) /// CHECK-DAG: BoundsCheck /// CHECK-DAG: BoundsCheck /// CHECK-DAG: BoundsCheck /// CHECK-DAG: BoundsCheck // - /// CHECK-START: void Main.linearTriangularVariations(int) BCE (after) + /// CHECK-START: void Main.linearTriangularVariationsInnerStrict(int) BCE (after) /// CHECK-NOT: BoundsCheck - /// CHECK-NOT: Deoptimize - private static void linearTriangularVariations(int n) { + // TODO: also CHECK-NOT: Deoptimize, see b/27151190 + private static void linearTriangularVariationsInnerStrict(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { a[j] += 1; } - for (int j = i - 1; j >= 0; j--) { + for (int j = i - 1; j > -1; j--) { a[j] += 1; } for (int j = i; j < n; j++) { @@ -556,6 +556,34 @@ public class Main { verifyTriangular(a); } + /// CHECK-START: void Main.linearTriangularVariationsInnerNonStrict(int) BCE (before) + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: BoundsCheck + /// CHECK-DAG: BoundsCheck + // + /// CHECK-START: void Main.linearTriangularVariationsInnerNonStrict(int) BCE (after) + /// CHECK-NOT: BoundsCheck + // TODO: also CHECK-NOT: Deoptimize, see b/27151190 + private static void linearTriangularVariationsInnerNonStrict(int n) { + int[] a = new int[n]; + for (int i = 0; i < n; i++) { + for (int j = 0; j <= i - 1; j++) { + a[j] += 1; + } + for (int j = i - 1; j >= 0; j--) { + a[j] += 1; + } + for (int j = i; j <= n - 1; j++) { + a[j] += 1; + } + for (int j = n - 1; j >= i; j--) { + a[j] += 1; + } + } + verifyTriangular(a); + } + // Verifier for triangular loops. private static void verifyTriangular(int[] a, int[] b, int m, int n) { expectEquals(n, a.length); @@ -583,7 +611,7 @@ public class Main { // /// CHECK-START: void Main.bubble(int[]) BCE (after) /// CHECK-NOT: BoundsCheck - /// CHECK-NOT: Deoptimize + // TODO: also CHECK-NOT: Deoptimize, see b/27151190 private static void bubble(int[] a) { for (int i = a.length; --i >= 0;) { for (int j = 0; j < i; j++) { @@ -853,6 +881,104 @@ public class Main { } while (-1 <= i); } + /// CHECK-START: void Main.hiddenOOB1(int) BCE (before) + /// CHECK-DAG: BoundsCheck + // + /// CHECK-START: void Main.hiddenOOB1(int) BCE (after) + /// CHECK-DAG: Deoptimize + // + /// CHECK-START: void Main.hiddenOOB1(int) BCE (after) + /// CHECK-NOT: BoundsCheck + private static void hiddenOOB1(int lo) { + int[] a = { 1 } ; + for (int i = lo; i <= 10; i++) { + // Dangerous loop where careless static range analysis would yield strict upper bound + // on index j of 5. When, for instance, lo and thus i = -2147483648, the upper bound + // becomes really positive due to arithmetic wrap-around, causing OOB. + // Dynamic BCE is feasible though, since it checks the range. + for (int j = 4; j < i - 5; j++) { + sResult += a[j - 4]; + } + } + } + + /// CHECK-START: void Main.hiddenOOB2(int) BCE (before) + /// CHECK-DAG: BoundsCheck + // + /// CHECK-START: void Main.hiddenOOB2(int) BCE (after) + /// CHECK-DAG: Deoptimize + // + /// CHECK-START: void Main.hiddenOOB2(int) BCE (after) + /// CHECK-NOT: BoundsCheck + private static void hiddenOOB2(int hi) { + int[] a = { 1 } ; + for (int i = 0; i < hi; i++) { + // Dangerous loop where careless static range analysis would yield strict lower bound + // on index j of 5. When, for instance, lo and thus i = 2147483647, the upper bound + // becomes really negative due to arithmetic wrap-around, causing OOB. + // Dynamic BCE is feasible though, since it checks the range. + for (int j = 6; j > i + 5; j--) { + sResult += a[j - 6]; + } + } + } + + /// CHECK-START: void Main.hiddenInfiniteOOB() BCE (before) + /// CHECK-DAG: BoundsCheck + // + /// CHECK-START: void Main.hiddenInfiniteOOB() BCE (after) + /// CHECK-DAG: BoundsCheck + // + /// CHECK-START: void Main.hiddenInfiniteOOB() BCE (after) + /// CHECK-NOT: Deoptimize + private static void hiddenInfiniteOOB() { + int[] a = { 11 } ; + for (int i = -1; i <= 0; i++) { + // Dangerous loop where careless static range analysis would yield a safe upper bound + // of -3. In reality, due to arithmetic wrap-around (when i = -1, j <= 2147483647; + // whereas when i = 0, j <= -3), this is an infinite loop that goes OOB. + for (int j = -3; j <= 2147483646 * i - 3; j++) { + sResult += a[j + 3]; + } + } + } + + /// CHECK-START: void Main.hiddenFiniteOOB() BCE (before) + /// CHECK-DAG: BoundsCheck + // + /// CHECK-START: void Main.hiddenFiniteOOB() BCE (after) + /// CHECK-DAG: Deoptimize + // + /// CHECK-START: void Main.hiddenFiniteOOB() BCE (after) + /// CHECK-NOT: BoundsCheck + private static void hiddenFiniteOOB() { + int[] a = { 111 } ; + for (int i = -1; i <= 0; i++) { + // Dangerous loop similar as above where the loop is now finite, but the + // loop still goes out of bounds for i = -1 due to the large upper bound. + // Dynamic BCE is feasible though, since it checks the range. + for (int j = -4; j < 2147483646 * i - 3; j++) { + sResult += a[j + 4]; + } + } + } + + /// CHECK-START: int[] Main.add() BCE (before) + /// CHECK-DAG: BoundsCheck + // + /// CHECK-START: int[] Main.add() BCE (after) + /// CHECK-NOT: BoundsCheck + /// CHECK-NOT: Deoptimize + private static int[] add() { + int[] a = new int[10]; + for (int i = 0; i <= 3; i++) { + for (int j = 0; j <= 6; j++) { + a[i + j] += 1; + } + } + return a; + } + /// CHECK-START: int[] Main.multiply1() BCE (before) /// CHECK-DAG: BoundsCheck // @@ -1053,6 +1179,37 @@ public class Main { return result; } + /// CHECK-START: int Main.dynamicBCEConstantRange(int[]) BCE (before) + /// CHECK-DAG: BoundsCheck loop:<<InnerLoop:B\d+>> + /// CHECK-DAG: ArrayGet loop:<<InnerLoop>> + /// CHECK-DAG: If loop:<<InnerLoop>> + /// CHECK-DAG: If loop:<<OuterLoop:B\d+>> + /// CHECK-EVAL: "<<InnerLoop>>" != "<<OuterLoop>>" + // + /// CHECK-START: int Main.dynamicBCEConstantRange(int[]) BCE (after) + /// CHECK-DAG: ArrayGet loop:<<InnerLoop:B\d+>> + /// CHECK-DAG: Deoptimize loop:<<OuterLoop:B\d+>> + /// CHECK-EVAL: "<<InnerLoop>>" != "<<OuterLoop>>" + // + /// CHECK-START: int Main.dynamicBCEConstantRange(int[]) BCE (after) + /// CHECK-NOT: BoundsCheck + // + // No additional top tests were introduced. + /// CHECK-START: int Main.dynamicBCEConstantRange(int[]) BCE (after) + /// CHECK-DAG: If + /// CHECK-DAG: If + /// CHECK-NOT: If + static int dynamicBCEConstantRange(int[] x) { + int result = 0; + for (int i = 2; i <= 6; i++) { + // Range analysis sees that innermost loop is finite and always taken. + for (int j = i - 2; j <= i + 2; j++) { + result += x[j]; + } + } + return result; + } + /// CHECK-START: int Main.dynamicBCEAndConstantIndices(int[], int[][], int, int) BCE (before) /// CHECK-DAG: {{l\d+}} ArrayGet loop:<<Loop:B\d+>> /// CHECK-DAG: {{l\d+}} ArrayGet loop:<<Loop>> @@ -1239,7 +1396,8 @@ public class Main { linearTriangularOnTwoArrayLengths(10); linearTriangularOnOneArrayLength(10); linearTriangularOnParameter(10); - linearTriangularVariations(10); + linearTriangularVariationsInnerStrict(10); + linearTriangularVariationsInnerNonStrict(10); // Sorting. int[] sort = { 5, 4, 1, 9, 10, 2, 7, 6, 3, 8 }; @@ -1330,6 +1488,59 @@ public class Main { } expectEquals(1055, sResult); + // Hidden OOB. + sResult = 0; + try { + hiddenOOB1(10); // no OOB + } catch (ArrayIndexOutOfBoundsException e) { + sResult += 1000; + } + expectEquals(1, sResult); + sResult = 0; + try { + hiddenOOB1(-2147483648); // OOB + } catch (ArrayIndexOutOfBoundsException e) { + sResult += 1000; + } + expectEquals(1001, sResult); + sResult = 0; + try { + hiddenOOB2(1); // no OOB + } catch (ArrayIndexOutOfBoundsException e) { + sResult += 1000; + } + expectEquals(1, sResult); + sResult = 0; + try { + hiddenOOB2(2147483647); // OOB + } catch (ArrayIndexOutOfBoundsException e) { + sResult += 1000; + } + expectEquals(1002, sResult); + sResult = 0; + try { + hiddenInfiniteOOB(); + } catch (ArrayIndexOutOfBoundsException e) { + sResult += 1000; + } + expectEquals(1011, sResult); + sResult = 0; + try { + hiddenFiniteOOB(); + } catch (ArrayIndexOutOfBoundsException e) { + sResult += 1000; + } + expectEquals(1111, sResult); + + // Addition. + { + int[] e1 ={ 1, 2, 3, 4, 4, 4, 4, 3, 2, 1 }; + int[] a1 = add(); + for (int i = 0; i < 10; i++) { + expectEquals(a1[i], e1[i]); + } + } + // Multiplication. { int[] e1 = { 7, 1, 2, 2, 1, 0, 2, 0, 0, 1 }; @@ -1388,6 +1599,7 @@ public class Main { expectEquals(55, dynamicBCEPossiblyInfiniteLoop(x, 0, 9)); expectEquals(55, noDynamicBCEPossiblyInfiniteLoop(x, 0, 9)); expectEquals(55, noDynamicBCEMixedInductionTypes(x, 0, 10)); + expectEquals(125, dynamicBCEConstantRange(x)); // Dynamic BCE combined with constant indices. int[][] a; |