From 22f058726d35dd8f40b3763649e61740b3d22535 Mon Sep 17 00:00:00 2001 From: Aart Bik Date: Tue, 27 Oct 2015 15:56:28 -0700 Subject: [PATCH] Generate taken-test during trip-count analysis. Rationale: for loops that may not be taken, this taken-test can be used by clients of the induction variable analysis to ensure trip-count evaluation is valid. Change-Id: Ia64749e2389b7224e69d6a49bb604b1964c11068 --- compiler/optimizing/induction_var_analysis.cc | 69 +++++++++++++--------- compiler/optimizing/induction_var_analysis.h | 22 ++++--- compiler/optimizing/induction_var_analysis_test.cc | 4 +- compiler/optimizing/induction_var_range.cc | 10 ++-- compiler/optimizing/induction_var_range_test.cc | 2 +- 5 files changed, 64 insertions(+), 43 deletions(-) diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc index 8968a44da..b6220fc13 100644 --- a/compiler/optimizing/induction_var_analysis.cc +++ b/compiler/optimizing/induction_var_analysis.cc @@ -20,14 +20,14 @@ namespace art { /** - * Returns true if instruction is invariant within the given loop. + * Returns true if instruction is invariant within the given loop + * (instruction is not defined in same or more inner loop). */ static bool IsLoopInvariant(HLoopInformation* loop, HInstruction* instruction) { HLoopInformation* other_loop = instruction->GetBlock()->GetLoopInformation(); - if (other_loop != loop) { - // If instruction does not occur in same loop, it is invariant - // if it appears in an outer loop (including no loop at all). - return other_loop == nullptr || loop->IsIn(*other_loop); + if (other_loop != loop && (other_loop == nullptr || !other_loop->IsIn(*loop))) { + DCHECK(instruction->GetBlock()->Dominates(loop->GetHeader())); + return true; } return false; } @@ -601,15 +601,16 @@ void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, // 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 + // 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. + // loop-body proper, not the loop-header unless enforced with an explicit taken-test. // (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. + // with an explicit finite-test. // (4) For loops which early-exits, the TC forms an upper bound, as in: // for (int i = 0; i < 10 && ....; i++) // TC <= 10 + InductionInfo* trip_count = upper_expr; 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; @@ -617,26 +618,36 @@ void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, // 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) { - upper_expr = CreateInvariantOp(kSub, upper_expr, CreateConstant(1, type)); + trip_count = CreateInvariantOp(kSub, trip_count, CreateConstant(1, type)); } else if (cmp == kCondGT) { - upper_expr = CreateInvariantOp(kAdd, upper_expr, CreateConstant(1, type)); + trip_count = CreateInvariantOp(kAdd, trip_count, CreateConstant(1, type)); } // Compensate for stride. - upper_expr = CreateInvariantOp(kAdd, upper_expr, stride); + trip_count = CreateInvariantOp(kAdd, trip_count, stride); } - InductionInfo* trip_count - = CreateInvariantOp(kDiv, CreateInvariantOp(kSub, upper_expr, lower_expr), stride); + trip_count = CreateInvariantOp(kDiv, CreateInvariantOp(kSub, trip_count, 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 under the conditions listed above. - InductionOp tcKind = kTripCountInBodyUnsafe; + InductionOp tcKind = kTripCountInBodyUnsafe; // needs both tests if (is_taken && is_finite) { - tcKind = kTripCountInLoop; + tcKind = kTripCountInLoop; // needs neither test } else if (is_finite) { - tcKind = kTripCountInBody; + tcKind = kTripCountInBody; // needs taken-test } else if (is_taken) { - tcKind = kTripCountInLoopUnsafe; + tcKind = kTripCountInLoopUnsafe; // needs finite-test } - AssignInfo(loop, loop->GetHeader()->GetLastInstruction(), CreateTripCount(tcKind, trip_count)); + InductionOp op = kNop; + switch (cmp) { + case kCondLT: op = kLT; break; + case kCondLE: op = kLE; break; + case kCondGT: op = kGT; break; + case kCondGE: op = kGE; break; + default: LOG(FATAL) << "CONDITION UNREACHABLE"; + } + InductionInfo* taken_test = CreateInvariantOp(op, lower_expr, upper_expr); + AssignInfo(loop, + loop->GetHeader()->GetLastInstruction(), + CreateTripCount(tcKind, trip_count, taken_test)); } bool HInductionVarAnalysis::IsTaken(InductionInfo* lower_expr, @@ -829,12 +840,16 @@ std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) { std::string inv = "("; inv += InductionToString(info->op_a); switch (info->operation) { - case kNop: inv += " @ "; break; - case kAdd: inv += " + "; break; + case kNop: inv += " @ "; break; + case kAdd: inv += " + "; break; case kSub: - case kNeg: inv += " - "; break; - case kMul: inv += " * "; break; - case kDiv: inv += " / "; break; + case kNeg: inv += " - "; break; + case kMul: inv += " * "; break; + case kDiv: inv += " / "; break; + case kLT: inv += " < "; break; + case kLE: inv += " <= "; break; + case kGT: inv += " > "; break; + case kGE: inv += " >= "; break; case kFetch: DCHECK(info->fetch); if (IsIntAndGet(info, &value)) { @@ -843,10 +858,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; + 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 7ab80cd67..cf354093f 100644 --- a/compiler/optimizing/induction_var_analysis.h +++ b/compiler/optimizing/induction_var_analysis.h @@ -65,11 +65,16 @@ class HInductionVarAnalysis : public HOptimization { kMul, kDiv, kFetch, - // Trip counts (valid in full loop or only body proper; unsafe implies loop may be infinite). - kTripCountInLoop, - kTripCountInBody, - kTripCountInLoopUnsafe, - kTripCountInBodyUnsafe + // Trip-counts. + kTripCountInLoop, // valid in full loop; loop is finite + kTripCountInBody, // valid in body only; loop is finite + kTripCountInLoopUnsafe, // valid in full loop; loop may be infinite + kTripCountInBodyUnsafe, // valid in body only; loop may be infinite + // Comparisons for trip-count tests. + kLT, + kLE, + kGT, + kGE }; /** @@ -85,7 +90,7 @@ class HInductionVarAnalysis : public HOptimization { * (4) periodic * nop: a, then defined by b (repeated when exhausted) * (5) trip-count: - * tc: defined by b + * tc: defined by a, taken-test in b */ struct InductionInfo : public ArenaObject { InductionInfo(InductionClass ic, @@ -119,8 +124,9 @@ 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* CreateTripCount(InductionOp op, InductionInfo* a, InductionInfo* b) { + DCHECK(a != nullptr); + return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr); } InductionInfo* CreateInduction(InductionClass ic, InductionInfo* a, InductionInfo* b) { diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc index f16da2a3f..b7262f6b2 100644 --- a/compiler/optimizing/induction_var_analysis_test.cc +++ b/compiler/optimizing/induction_var_analysis_test.cc @@ -234,7 +234,7 @@ TEST_F(InductionVarAnalysisTest, FindBasicInduction) { EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[0], 0).c_str()); // Trip-count. - EXPECT_STREQ("(TC-loop:(100))", + EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); } @@ -552,7 +552,7 @@ TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) { } EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[d], d).c_str()); // Trip-count. - EXPECT_STREQ("(TC-loop:(100))", + EXPECT_STREQ("((100) (TC-loop) ((0) < (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 f4842f969..5530d261d 100644 --- a/compiler/optimizing/induction_var_range.cc +++ b/compiler/optimizing/induction_var_range.cc @@ -152,7 +152,7 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, } } else if (is_min) { // Special case for finding minimum: minimum of trip-count in loop-body is 1. - if (trip != nullptr && in_body && instruction == trip->op_b->fetch) { + if (trip != nullptr && in_body && instruction == trip->op_a->fetch) { return Value(1); } } @@ -185,14 +185,14 @@ InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::Induct return GetFetch(info->fetch, trip, in_body, is_min); case HInductionVarAnalysis::kTripCountInLoop: if (!in_body && !is_min) { // one extra! - return GetVal(info->op_b, trip, in_body, is_min); + return GetVal(info->op_a, trip, in_body, is_min); } FALLTHROUGH_INTENDED; case HInductionVarAnalysis::kTripCountInBody: if (is_min) { return Value(0); } else if (in_body) { - return SubValue(GetVal(info->op_b, trip, in_body, is_min), Value(1)); + return SubValue(GetVal(info->op_a, trip, in_body, is_min), Value(1)); } break; default: @@ -428,7 +428,7 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, return true; case HInductionVarAnalysis::kTripCountInLoop: if (!in_body && !is_min) { // one extra! - return GenerateCode(info->op_b, trip, graph, block, result, in_body, is_min); + return GenerateCode(info->op_a, trip, graph, block, result, in_body, is_min); } FALLTHROUGH_INTENDED; case HInductionVarAnalysis::kTripCountInBody: @@ -438,7 +438,7 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, } return true; } else if (in_body) { - if (GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) { + if (GenerateCode(info->op_a, trip, graph, block, &opb, in_body, is_min)) { if (graph != nullptr) { *result = Insert(block, new (graph->GetArena()) diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc index 8fbc59fb4..ce8926ad7 100644 --- a/compiler/optimizing/induction_var_range_test.cc +++ b/compiler/optimizing/induction_var_range_test.cc @@ -125,7 +125,7 @@ class InductionVarRangeTest : public testing::Test { /** Constructs a trip-count. */ HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc) { - return iva_->CreateTripCount(HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc)); + return iva_->CreateTripCount(HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc), nullptr); } /** Constructs a linear a * i + b induction. */ -- 2.11.0