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

1 files changed, 111 insertions, 44 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 + ")";