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
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 8968a44..b6220fc 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 @@
// 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 @@
// 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 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 @@
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 7ab80cd..cf35409 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -65,11 +65,16 @@
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 @@
* (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<kArenaAllocInductionVarAnalysis> {
InductionInfo(InductionClass ic,
@@ -119,8 +124,9 @@
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 f16da2a..b7262f6 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -234,7 +234,7 @@
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 @@
}
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 f4842f9..5530d26 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -152,7 +152,7 @@
}
} 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 @@
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 @@
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 @@
}
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 8fbc59f..ce8926a 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -125,7 +125,7 @@
/** 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. */