diff options
-rw-r--r-- | compiler/optimizing/induction_var_analysis.cc | 155 | ||||
-rw-r--r-- | compiler/optimizing/induction_var_analysis.h | 28 | ||||
-rw-r--r-- | compiler/optimizing/induction_var_analysis_test.cc | 8 | ||||
-rw-r--r-- | compiler/optimizing/induction_var_range.cc | 124 | ||||
-rw-r--r-- | compiler/optimizing/induction_var_range.h | 9 | ||||
-rw-r--r-- | compiler/optimizing/induction_var_range_test.cc | 22 | ||||
-rw-r--r-- | test/530-checker-loops/src/Main.java | 102 |
7 files changed, 316 insertions, 132 deletions
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc index 9fb4304450..a8006a9fa3 100644 --- a/compiler/optimizing/induction_var_analysis.cc +++ b/compiler/optimizing/induction_var_analysis.cc @@ -553,44 +553,33 @@ void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, } } else if (a->induction_class == kLinear && b->induction_class == kInvariant) { // 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* lo_val = a->op_b; - InductionInfo* hi_val = b; - // Analyze stride (may be compound). - InductionVarRange::Value v1 = InductionVarRange::GetVal(stride, nullptr, /* is_min */ true); - InductionVarRange::Value v2 = InductionVarRange::GetVal(stride, nullptr, /* is_min */ false); - if (v1.a_constant != 0 || v2.a_constant != 0 || v1.b_constant != v2.b_constant) { + int64_t stride_value = 0; + if (!IsIntAndGet(stride, &stride_value)) { return; } - // Rewrite safe condition i != U with unit stride into i < U or i > U - // (unit stride guarantees that the end condition is always reached). - const int32_t stride_value = v1.b_constant; - int64_t lo_value = 0; - int64_t hi_value = 0; - if (cmp == kCondNE && IsIntAndGet(lo_val, &lo_value) && IsIntAndGet(hi_val, &hi_value)) { - if ((stride_value == +1 && lo_value < hi_value) || - (stride_value == -1 && lo_value > hi_value)) { - cmp = stride_value > 0 ? kCondLT : kCondGT; - } + // Rewrite condition i != U into i < U or i > U if end condition is reached exactly. + if (cmp == kCondNE && ((stride_value == +1 && IsTaken(lower_expr, upper_expr, kCondLT)) || + (stride_value == -1 && IsTaken(lower_expr, upper_expr, kCondGT)))) { + cmp = stride_value > 0 ? kCondLT : kCondGT; } // Normalize a linear loop control with a nonzero stride: // stride > 0, either i < U or i <= U // stride < 0, either i > U or i >= U - // - // TODO: construct conditions for constant/symbolic safety of trip-count - // if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) || (stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) { - VisitTripCount(loop, lo_val, hi_val, stride, stride_value, type, cmp); + VisitTripCount(loop, lower_expr, upper_expr, stride, stride_value, type, cmp); } } } void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, - InductionInfo* lo_val, - InductionInfo* hi_val, + InductionInfo* lower_expr, + InductionInfo* upper_expr, InductionInfo* stride, - int32_t stride_value, + int64_t stride_value, Primitive::Type type, IfCondition cmp) { // Any loop of the general form: @@ -604,30 +593,95 @@ void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, // for (n = 0; n < TC; n++) // where TC = (U + S - L) / S // .. L + S * n .. // - // NOTE: The TC (trip-count) expression is only valid when safe. Otherwise TC is 0 - // (or possibly infinite). Also, the expression assumes the loop does not have - // early-exits. Otherwise, TC is an upper bound. + // taking the following into consideration: // - bool cancels = (cmp == kCondLT || cmp == kCondGT) && std::abs(stride_value) == 1; + // (1) Using the same precision, the TC (trip-count) expression should be interpreted as + // an unsigned entity, for example, as in the following loop that uses the full range: + // for (int i = INT_MIN; i < INT_MAX; i++) // TC = UINT_MAX + // (2) The TC is only valid if the loop is taken, otherwise TC = 0, as in: + // for (int i = 12; i < U; i++) // TC = 0 when U >= 12 + // If this cannot be determined at compile-time, the TC is only valid within the + // loop-body proper, not the loop-header unless enforced with an explicit condition. + // (3) The TC is only valid if the loop is finite, otherwise TC has no value, as in: + // for (int i = 0; i <= U; i++) // TC = Inf when U = INT_MAX + // If this cannot be determined at compile-time, the TC is only valid when enforced + // with an explicit condition. + // (4) For loops which early-exits, the TC forms an upper bound, as in: + // for (int i = 0; i < 10 && ....; i++) // TC <= 10 + const bool is_taken = IsTaken(lower_expr, upper_expr, cmp); + const bool is_finite = IsFinite(upper_expr, stride_value, type, cmp); + const bool cancels = (cmp == kCondLT || cmp == kCondGT) && std::abs(stride_value) == 1; if (!cancels) { // Convert exclusive integral inequality into inclusive integral inequality, // viz. condition i < U is i <= U - 1 and condition i > U is i >= U + 1. if (cmp == kCondLT) { - hi_val = CreateInvariantOp(kSub, hi_val, CreateConstant(1, type)); + upper_expr = CreateInvariantOp(kSub, upper_expr, CreateConstant(1, type)); } else if (cmp == kCondGT) { - hi_val = CreateInvariantOp(kAdd, hi_val, CreateConstant(1, type)); + upper_expr = CreateInvariantOp(kAdd, upper_expr, CreateConstant(1, type)); } // Compensate for stride. - hi_val = CreateInvariantOp(kAdd, hi_val, stride); + upper_expr = CreateInvariantOp(kAdd, upper_expr, stride); } - + InductionInfo* trip_count + = CreateInvariantOp(kDiv, CreateInvariantOp(kSub, upper_expr, lower_expr), stride); // Assign the trip-count expression to the loop control. Clients that use the information - // should be aware that the expression is only valid in the loop-body proper (when symbolically - // safe), and not yet in the loop-header (unless constant safe). If the loop has any early exits, - // the trip-count forms a conservative upper bound on the number of loop iterations. - InductionInfo* trip_count = - CreateInvariantOp(kDiv, CreateInvariantOp(kSub, hi_val, lo_val), stride); - AssignInfo(loop, loop->GetHeader()->GetLastInstruction(), trip_count); + // should be aware that the expression is only valid under the conditions listed above. + InductionOp tcKind = kTripCountInBodyUnsafe; + if (is_taken && is_finite) { + tcKind = kTripCountInLoop; + } else if (is_finite) { + tcKind = kTripCountInBody; + } else if (is_taken) { + tcKind = kTripCountInLoopUnsafe; + } + AssignInfo(loop, loop->GetHeader()->GetLastInstruction(), CreateTripCount(tcKind, trip_count)); +} + +bool HInductionVarAnalysis::IsTaken(InductionInfo* lower_expr, + InductionInfo* upper_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; + case kCondEQ: + case kCondNE: LOG(FATAL) << "CONDITION UNREACHABLE"; + } + } + return false; // not certain, may be untaken +} + +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(); + // 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)); + case kCondLE: + return (IsIntAndGet(upper_expr, &value) && value <= (max - stride_value)); + case kCondGT: + return stride_value == -1 || + (IsIntAndGet(upper_expr, &value) && value >= (min - stride_value - 1)); + case kCondGE: + return (IsIntAndGet(upper_expr, &value) && value >= (min - stride_value)); + case kCondEQ: + case kCondNE: LOG(FATAL) << "CONDITION UNREACHABLE"; + } + return false; // not certain, may be infinite } void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop, @@ -744,13 +798,22 @@ bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1, } bool HInductionVarAnalysis::IsIntAndGet(InductionInfo* info, int64_t* value) { - if (info != nullptr && info->induction_class == kInvariant && 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(); + 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. + int32_t range_value; + if (InductionVarRange::GetConstant(info, &range_value)) { + *value = range_value; return true; } } @@ -778,6 +841,10 @@ std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) { inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName(); } break; + case kTripCountInLoop: inv += "TC-loop:"; break; + case kTripCountInBody: inv += "TC-body:"; break; + case kTripCountInLoopUnsafe: inv += "TC-loop-unsafe:"; break; + case kTripCountInBodyUnsafe: inv += "TC-body-unsafe:"; break; } inv += InductionToString(info->op_b); return inv + ")"; diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h index 190a0db65c..9669bcc528 100644 --- a/compiler/optimizing/induction_var_analysis.h +++ b/compiler/optimizing/induction_var_analysis.h @@ -56,13 +56,20 @@ class HInductionVarAnalysis : public HOptimization { }; enum InductionOp { - kNop, // no-operation: a true induction + // No-operation: a true induction. + kNop, + // Various invariant operations. kAdd, kSub, kNeg, kMul, kDiv, - kFetch + kFetch, + // Trip counts (valid in full loop or only body proper; unsafe implies loop may be infinite). + kTripCountInLoop, + kTripCountInBody, + kTripCountInLoopUnsafe, + kTripCountInBodyUnsafe }; /** @@ -77,6 +84,8 @@ class HInductionVarAnalysis : public HOptimization { * nop: a, then defined by b * (4) periodic * nop: a, then defined by b (repeated when exhausted) + * (5) trip-count: + * tc: defined by b */ struct InductionInfo : public ArenaObject<kArenaAllocMisc> { InductionInfo(InductionClass ic, @@ -110,6 +119,10 @@ class HInductionVarAnalysis : public HOptimization { return new (graph_->GetArena()) InductionInfo(kInvariant, kFetch, nullptr, nullptr, f); } + InductionInfo* CreateTripCount(InductionOp op, InductionInfo* b) { + return new (graph_->GetArena()) InductionInfo(kInvariant, op, nullptr, b, nullptr); + } + InductionInfo* CreateInduction(InductionClass ic, InductionInfo* a, InductionInfo* b) { DCHECK(a != nullptr && b != nullptr); return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr); @@ -151,12 +164,17 @@ class HInductionVarAnalysis : public HOptimization { Primitive::Type type, IfCondition cmp); void VisitTripCount(HLoopInformation* loop, - InductionInfo* lo_val, - InductionInfo* hi_val, + InductionInfo* lower_expr, + InductionInfo* upper_expr, InductionInfo* stride, - int32_t stride_value, + int64_t stride_value, Primitive::Type type, IfCondition cmp); + bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp); + bool IsFinite(InductionInfo* upper_expr, + int64_t stride_value, + Primitive::Type type, + IfCondition cmp); // Assign and lookup. void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info); diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc index e519e77f60..20492e7152 100644 --- a/compiler/optimizing/induction_var_analysis_test.cc +++ b/compiler/optimizing/induction_var_analysis_test.cc @@ -234,7 +234,8 @@ TEST_F(InductionVarAnalysisTest, FindBasicInduction) { EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[0], 0).c_str()); // Trip-count. - EXPECT_STREQ("(100)", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); + EXPECT_STREQ("(TC-loop:(100))", + GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); } TEST_F(InductionVarAnalysisTest, FindDerivedInduction) { @@ -543,8 +544,10 @@ TEST_F(InductionVarAnalysisTest, FindRange) { InductionVarRange range(iva_); InductionVarRange::Value v_min = range.GetMinInduction(store, store->InputAt(1)); InductionVarRange::Value v_max = range.GetMaxInduction(store, store->InputAt(1)); + ASSERT_TRUE(v_min.is_known); EXPECT_EQ(0, v_min.a_constant); EXPECT_EQ(1, v_min.b_constant); + ASSERT_TRUE(v_max.is_known); EXPECT_EQ(0, v_max.a_constant); EXPECT_EQ(199, v_max.b_constant); } @@ -579,7 +582,8 @@ TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) { } EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[d], d).c_str()); // Trip-count. - EXPECT_STREQ("(100)", GetInductionInfo(loop_header_[d]->GetLastInstruction(), d).c_str()); + EXPECT_STREQ("(TC-loop:(100))", + GetInductionInfo(loop_header_[d]->GetLastInstruction(), d).c_str()); } } diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc index 119a80b6f4..db12819060 100644 --- a/compiler/optimizing/induction_var_range.cc +++ b/compiler/optimizing/induction_var_range.cc @@ -86,51 +86,36 @@ InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis) InductionVarRange::Value InductionVarRange::GetMinInduction(HInstruction* context, HInstruction* instruction) { - HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); - if (loop != nullptr) { - return GetVal(induction_analysis_->LookupInfo(loop, instruction), - GetTripCount(loop, context), /* is_min */ true); - } - return Value(); + return GetInduction(context, instruction, /* is_min */ true); } InductionVarRange::Value InductionVarRange::GetMaxInduction(HInstruction* context, HInstruction* instruction) { - HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); - if (loop != nullptr) { - return SimplifyMax( - GetVal(induction_analysis_->LookupInfo(loop, instruction), - GetTripCount(loop, context), /* is_min */ false)); - } - return Value(); + return SimplifyMax(GetInduction(context, instruction, /* is_min */ false)); } // // Private class methods. // -HInductionVarAnalysis::InductionInfo* InductionVarRange::GetTripCount(HLoopInformation* loop, - HInstruction* context) { - // The trip-count expression is only valid when the top-test is taken at least once, - // that means, when the analyzed context appears outside the loop header itself. - // Early-exit loops are okay, since in those cases, the trip-count is conservative. - // - // TODO: deal with runtime safety issues on TCs - // - if (context->GetBlock() != loop->GetHeader()) { - HInductionVarAnalysis::InductionInfo* trip = - induction_analysis_->LookupInfo(loop, loop->GetHeader()->GetLastInstruction()); - if (trip != nullptr) { - // Wrap the trip-count representation in its own unusual NOP node, so that range analysis - // is able to determine the [0, TC - 1] interval without having to construct constants. - return induction_analysis_->CreateInvariantOp(HInductionVarAnalysis::kNop, trip, trip); - } +InductionVarRange::Value InductionVarRange::GetInduction(HInstruction* context, + HInstruction* instruction, + bool is_min) { + HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop + if (loop != nullptr) { + HBasicBlock* header = loop->GetHeader(); + bool in_body = context->GetBlock() != header; + return GetVal(induction_analysis_->LookupInfo(loop, instruction), + induction_analysis_->LookupInfo(loop, header->GetLastInstruction()), + in_body, + is_min); } - return nullptr; + return Value(); } InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, HInductionVarAnalysis::InductionInfo* trip, + bool in_body, bool is_min) { // 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. @@ -139,13 +124,13 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, return Value(value); } else if (instruction->IsAdd()) { if (IsIntAndGet(instruction->InputAt(0), &value)) { - return AddValue(Value(value), GetFetch(instruction->InputAt(1), trip, is_min)); + 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, is_min), Value(value)); + return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min), Value(value)); } } else if (is_min) { - // Special case for finding minimum: minimum of trip-count is 1. - if (trip != nullptr && instruction == trip->op_b->fetch) { + // Special case for finding minimum: minimum of trip-count in loop-body is 1. + if (trip != nullptr && in_body && instruction == trip->op_b->fetch) { return Value(1); } } @@ -154,42 +139,53 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* trip, + bool in_body, bool is_min) { if (info != nullptr) { switch (info->induction_class) { case HInductionVarAnalysis::kInvariant: // Invariants. switch (info->operation) { - case HInductionVarAnalysis::kNop: // normalized: 0 or TC-1 - DCHECK_EQ(info->op_a, info->op_b); - return is_min ? Value(0) - : SubValue(GetVal(info->op_b, trip, is_min), Value(1)); case HInductionVarAnalysis::kAdd: - return AddValue(GetVal(info->op_a, trip, is_min), - GetVal(info->op_b, trip, is_min)); + return AddValue(GetVal(info->op_a, trip, in_body, is_min), + GetVal(info->op_b, trip, in_body, is_min)); case HInductionVarAnalysis::kSub: // second reversed! - return SubValue(GetVal(info->op_a, trip, is_min), - GetVal(info->op_b, trip, !is_min)); + return SubValue(GetVal(info->op_a, trip, in_body, is_min), + GetVal(info->op_b, trip, in_body, !is_min)); case HInductionVarAnalysis::kNeg: // second reversed! return SubValue(Value(0), - GetVal(info->op_b, trip, !is_min)); + GetVal(info->op_b, trip, in_body, !is_min)); case HInductionVarAnalysis::kMul: - return GetMul(info->op_a, info->op_b, trip, is_min); + return GetMul(info->op_a, info->op_b, trip, in_body, is_min); case HInductionVarAnalysis::kDiv: - return GetDiv(info->op_a, info->op_b, trip, is_min); + return GetDiv(info->op_a, info->op_b, trip, in_body, is_min); case HInductionVarAnalysis::kFetch: - return GetFetch(info->fetch, trip, is_min); + return GetFetch(info->fetch, trip, in_body, is_min); + case HInductionVarAnalysis::kTripCountInLoop: + if (!in_body) { + return is_min ? Value(0) + : GetVal(info->op_b, trip, in_body, is_min); // one extra! + } + FALLTHROUGH_INTENDED; + case HInductionVarAnalysis::kTripCountInBody: + if (in_body) { + return is_min ? Value(0) + : SubValue(GetVal(info->op_b, trip, in_body, is_min), Value(1)); + } + break; + default: + break; } break; case HInductionVarAnalysis::kLinear: // Linear induction a * i + b, for normalized 0 <= i < TC. - return AddValue(GetMul(info->op_a, trip, trip, is_min), - GetVal(info->op_b, trip, is_min)); + return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min), + GetVal(info->op_b, trip, in_body, is_min)); case HInductionVarAnalysis::kWrapAround: case HInductionVarAnalysis::kPeriodic: // Merge values in the wrap-around/periodic. - return MergeVal(GetVal(info->op_a, trip, is_min), - GetVal(info->op_b, trip, is_min), is_min); + return MergeVal(GetVal(info->op_a, trip, in_body, is_min), + GetVal(info->op_b, trip, in_body, is_min), is_min); } } return Value(); @@ -198,11 +194,12 @@ InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::Induct InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1, HInductionVarAnalysis::InductionInfo* info2, HInductionVarAnalysis::InductionInfo* trip, + bool in_body, bool is_min) { - Value v1_min = GetVal(info1, trip, /* is_min */ true); - Value v1_max = GetVal(info1, trip, /* is_min */ false); - Value v2_min = GetVal(info2, trip, /* is_min */ true); - Value v2_max = GetVal(info2, trip, /* is_min */ false); + 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); 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) { @@ -228,11 +225,12 @@ InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::Induct InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::InductionInfo* info1, HInductionVarAnalysis::InductionInfo* info2, HInductionVarAnalysis::InductionInfo* trip, + bool in_body, bool is_min) { - Value v1_min = GetVal(info1, trip, /* is_min */ true); - Value v1_max = GetVal(info1, trip, /* is_min */ false); - Value v2_min = GetVal(info2, trip, /* is_min */ true); - Value v2_max = GetVal(info2, trip, /* is_min */ false); + 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); 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) { @@ -255,6 +253,16 @@ InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::Induct return Value(); } +bool InductionVarRange::GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t *value) { + Value v_min = GetVal(info, nullptr, false, /* is_min */ true); + Value v_max = GetVal(info, nullptr, false, /* is_min */ false); + if (v_min.a_constant == 0 && v_max.a_constant == 0 && v_min.b_constant == v_max.b_constant) { + *value = v_min.b_constant; + return true; + } + return false; +} + InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) { if (v1.is_known && v2.is_known && IsSafeAdd(v1.b_constant, v2.b_constant)) { const int32_t b = v1.b_constant + v2.b_constant; diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h index 8280c8bedc..dbdd2eedac 100644 --- a/compiler/optimizing/induction_var_range.h +++ b/compiler/optimizing/induction_var_range.h @@ -73,24 +73,29 @@ class InductionVarRange { // Private helper methods. // - HInductionVarAnalysis::InductionInfo* GetTripCount(HLoopInformation* loop, HInstruction* context); + Value GetInduction(HInstruction* context, HInstruction* instruction, bool is_min); static Value GetFetch(HInstruction* instruction, HInductionVarAnalysis::InductionInfo* trip, + bool in_body, bool is_min); - static Value GetVal(HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* trip, + bool in_body, bool is_min); static Value GetMul(HInductionVarAnalysis::InductionInfo* info1, HInductionVarAnalysis::InductionInfo* info2, HInductionVarAnalysis::InductionInfo* trip, + bool in_body, bool is_min); static Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, HInductionVarAnalysis::InductionInfo* info2, HInductionVarAnalysis::InductionInfo* trip, + bool in_body, bool is_min); + static bool GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t *value); + static Value AddValue(Value v1, Value v2); static Value SubValue(Value v1, Value v2); static Value MulValue(Value v1, Value v2); diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc index 5d9a075aef..4497a884d9 100644 --- a/compiler/optimizing/induction_var_range_test.cc +++ b/compiler/optimizing/induction_var_range_test.cc @@ -85,8 +85,7 @@ class InductionVarRangeTest : public testing::Test { /** Constructs a trip-count. */ HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc) { - HInductionVarAnalysis::InductionInfo* trip = CreateConst(tc); - return CreateInvariant('@', trip, trip); + return iva_->CreateTripCount(HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc)); } /** Constructs a linear a * i + b induction. */ @@ -112,24 +111,28 @@ class InductionVarRangeTest : public testing::Test { Value GetMin(HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* induc) { - return InductionVarRange::GetVal(info, induc, /* is_min */ true); + return InductionVarRange::GetVal(info, induc, /* in_body */ true, /* is_min */ true); } Value GetMax(HInductionVarAnalysis::InductionInfo* info, HInductionVarAnalysis::InductionInfo* induc) { - return InductionVarRange::GetVal(info, induc, /* is_min */ false); + return InductionVarRange::GetVal(info, induc, /* in_body */ true, /* is_min */ false); } Value GetMul(HInductionVarAnalysis::InductionInfo* info1, HInductionVarAnalysis::InductionInfo* info2, bool is_min) { - return InductionVarRange::GetMul(info1, info2, nullptr, is_min); + return InductionVarRange::GetMul(info1, info2, nullptr, /* in_body */ true, is_min); } Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, HInductionVarAnalysis::InductionInfo* info2, bool is_min) { - return InductionVarRange::GetDiv(info1, info2, nullptr, is_min); + return InductionVarRange::GetDiv(info1, info2, nullptr, /* in_body */ true, is_min); + } + + bool GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t* value) { + return InductionVarRange::GetConstant(info, value); } Value AddValue(Value v1, Value v2) { return InductionVarRange::AddValue(v1, v2); } @@ -279,6 +282,13 @@ TEST_F(InductionVarRangeTest, GetDivMax) { ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), false)); } +TEST_F(InductionVarRangeTest, GetConstant) { + int32_t value; + ASSERT_TRUE(GetConstant(CreateConst(12345), &value)); + EXPECT_EQ(12345, value); + EXPECT_FALSE(GetConstant(CreateRange(1, 2), &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))); diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java index 1c5b5d65b9..58c92f1ea4 100644 --- a/test/530-checker-loops/src/Main.java +++ b/test/530-checker-loops/src/Main.java @@ -22,7 +22,7 @@ public class Main { static int sResult; // - // Various sequence variables where bound checks can be removed from loop. + // Various sequence variables used in bound checks. // /// CHECK-START: int Main.linear(int[]) BCE (before) @@ -262,11 +262,11 @@ public class Main { return result; } - /// CHECK-START: int Main.linearForNE() BCE (before) + /// CHECK-START: int Main.linearForNEUp() BCE (before) /// CHECK-DAG: BoundsCheck - /// CHECK-START: int Main.linearForNE() BCE (after) + /// CHECK-START: int Main.linearForNEUp() BCE (after) /// CHECK-NOT: BoundsCheck - private static int linearForNE() { + private static int linearForNEUp() { int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int result = 0; for (int i = 0; i != 10; i++) { @@ -275,21 +275,47 @@ public class Main { return result; } - /// CHECK-START: int Main.linearDoWhile() BCE (before) + /// CHECK-START: int Main.linearForNEDown() BCE (before) /// CHECK-DAG: BoundsCheck - /// CHECK-START: int Main.linearDoWhile() BCE (after) + /// CHECK-START: int Main.linearForNEDown() BCE (after) + /// CHECK-NOT: BoundsCheck + private static int linearForNEDown() { + int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; + int result = 0; + for (int i = 9; i != -1; i--) { + result += x[i]; + } + return result; + } + + /// CHECK-START: int Main.linearDoWhileUp() BCE (before) /// CHECK-DAG: BoundsCheck - private static int linearDoWhile() { + /// CHECK-START: int Main.linearDoWhileUp() BCE (after) + /// CHECK-NOT: BoundsCheck + private static int linearDoWhileUp() { int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int result = 0; int i = 0; - // TODO: make this work do { result += x[i++]; } while (i < 10); return result; } + /// CHECK-START: int Main.linearDoWhileDown() BCE (before) + /// CHECK-DAG: BoundsCheck + /// CHECK-START: int Main.linearDoWhileDown() BCE (after) + /// CHECK-NOT: BoundsCheck + private static int linearDoWhileDown() { + int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; + int result = 0; + int i = 9; + do { + result += x[i--]; + } while (0 <= i); + return result; + } + /// CHECK-START: int Main.linearShort() BCE (before) /// CHECK-DAG: BoundsCheck /// CHECK-START: int Main.linearShort() BCE (after) @@ -471,23 +497,50 @@ public class Main { return result; } - // - // Cases that actually go out of bounds. These test cases - // ensure the exceptions are thrown at the right places. - // - + /// CHECK-START: void Main.lowerOOB(int[]) BCE (before) + /// CHECK-DAG: BoundsCheck + /// CHECK-START: void Main.lowerOOB(int[]) BCE (after) + /// CHECK-DAG: BoundsCheck private static void lowerOOB(int[] x) { for (int i = -1; i < x.length; i++) { sResult += x[i]; } } + /// CHECK-START: void Main.upperOOB(int[]) BCE (before) + /// CHECK-DAG: BoundsCheck + /// CHECK-START: void Main.upperOOB(int[]) BCE (after) + /// CHECK-DAG: BoundsCheck private static void upperOOB(int[] x) { for (int i = 0; i <= x.length; i++) { sResult += x[i]; } } + /// CHECK-START: void Main.doWhileUpOOB() BCE (before) + /// CHECK-DAG: BoundsCheck + /// CHECK-START: void Main.doWhileUpOOB() BCE (after) + /// CHECK-DAG: BoundsCheck + private static void doWhileUpOOB() { + int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; + int i = 0; + do { + sResult += x[i++]; + } while (i <= x.length); + } + + /// CHECK-START: void Main.doWhileDownOOB() BCE (before) + /// CHECK-DAG: BoundsCheck + /// CHECK-START: void Main.doWhileDownOOB() BCE (after) + /// CHECK-DAG: BoundsCheck + private static void doWhileDownOOB() { + int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; + int i = x.length - 1; + do { + sResult += x[i--]; + } while (-1 <= i); + } + // // Verifier. // @@ -550,8 +603,10 @@ public class Main { expectEquals(66, linearWithVeryLargeNegativeStride()); // Special forms. - expectEquals(55, linearForNE()); - expectEquals(55, linearDoWhile()); + expectEquals(55, linearForNEUp()); + expectEquals(55, linearForNEDown()); + expectEquals(55, linearDoWhileUp()); + expectEquals(55, linearDoWhileDown()); expectEquals(55, linearShort()); // Periodic adds (1, 3), one at the time. @@ -618,6 +673,23 @@ public class Main { } expectEquals(1055, sResult); + // Do while up goes OOB. + sResult = 0; + try { + doWhileUpOOB(); + } catch (ArrayIndexOutOfBoundsException e) { + sResult += 1000; + } + expectEquals(1055, sResult); + + // Do while down goes OOB. + sResult = 0; + try { + doWhileDownOOB(); + } catch (ArrayIndexOutOfBoundsException e) { + sResult += 1000; + } + expectEquals(1055, sResult); } private static void expectEquals(int expected, int result) { |