Implemented trip-count safety information.
As shown in the induction analysis presentation, trip-counts need to
deal with potential taken/not-taken situations (so that trip-count
is either valid in the full loop or just in the loop-body proper)
and potential finite/infinite situations (the latter can still be
analyzed but may need to run-time test later to guard against the
infinite conditions). This CL provides that information.
Change-Id: I0445d8e836b80a3614af217ce3e39d766e77b986
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 9fb4304..a8006a9 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -553,44 +553,33 @@
}
} 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 @@
// 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::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 @@
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 + ")";