[turbofan] Induction variable decrement bound analysis.

src/compiler/typer.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/typer.h"
 
 #include <iomanip>
 
 #include "src/base/flags.h"
 #include "src/bootstrapper.h"
@@ skipping 633 matching lines @@
   // the increment, just return the initial value's type.
   if (!initial_type->IsInhabited() || !increment_type->IsInhabited()) {
     return initial_type;
   }
 
   // Now process the bounds.
   auto res = induction_vars_->induction_variables().find(node->id());
   DCHECK(res != induction_vars_->induction_variables().end());
   InductionVariable* induction_var = res->second;
 
+  InductionVariable::ArithmeticType arithmeticType = induction_var->Type();
+
   double min = -V8_INFINITY;
   double max = V8_INFINITY;

[Jarin, 2016/08/19 13:08:25]

Could not you just say here:

double increment_min;
double increment_max;
if (arithmeticType == InductionVariable::ArithmeticType::kAddition) {
  increment_min = increment_type->Min();
  increment_max = increment_type->Max();
} else {
  DCHECK(arithmeticType ==
         InductionVariable::ArithmeticType::kSubtraction);
  increment_min = -increment_type->Max();
  increment_max = -increment_type->Min();
}

And then just use these below rather than special casing for add/subtract below?

[Franzi, 2016/08/19 18:38:51]

Done.

-  if (increment_type->Min() >= 0) {
+  if ((increment_type->Min() >= 0 &&
+       arithmeticType == InductionVariable::ArithmeticType::kAddition) ||
+      (increment_type->Max() <= 0 &&
+       arithmeticType == InductionVariable::ArithmeticType::kSubtraction)) {
+    // increasing sequence (add positive values, or subtract negative values)
     min = initial_type->Min();
     for (auto bound : induction_var->upper_bounds()) {
       Type* bound_type = TypeOrNone(bound.bound);
       // If the type is not an integer, just skip the bound.
       if (!bound_type->Is(typer_->cache_.kInteger)) continue;
       // If the type is not inhabited, then we can take the initial value.
       if (!bound_type->IsInhabited()) {
         max = initial_type->Max();
         break;
       }
       double bound_max = bound_type->Max();
       if (bound.kind == InductionVariable::kStrict) {
         bound_max -= 1;
       }
-      max = std::min(max, bound_max + increment_type->Max());
+      double bound_max_next_iteration;
+      if (arithmeticType == InductionVariable::ArithmeticType::kAddition) {
+        // find max, i.e., add the largest positive value
+        bound_max_next_iteration = bound_max + increment_type->Max();
+      } else {
+        // find max, i.e., subtract the smallest negative value
+        bound_max_next_iteration = bound_max - increment_type->Min();
+      }
+      max = std::min(max, bound_max_next_iteration);
     }
     // The upper bound must be at least the initial value's upper bound.
     max = std::max(max, initial_type->Max());
-  } else if (increment_type->Max() <= 0) {
+  } else if ((increment_type->Max() <= 0 &&
+              arithmeticType == InductionVariable::ArithmeticType::kAddition) ||
+             (increment_type->Min() >= 0 &&
+              arithmeticType ==
+                  InductionVariable::ArithmeticType::kSubtraction)) {
+    // decreasing sequence (add negative values, or subtract positive values)
     max = initial_type->Max();
     for (auto bound : induction_var->lower_bounds()) {
       Type* bound_type = TypeOrNone(bound.bound);
       // If the type is not an integer, just skip the bound.
       if (!bound_type->Is(typer_->cache_.kInteger)) continue;
       // If the type is not inhabited, then we can take the initial value.
       if (!bound_type->IsInhabited()) {
         min = initial_type->Min();
         break;
       }
       double bound_min = bound_type->Min();
       if (bound.kind == InductionVariable::kStrict) {
         bound_min += 1;
       }
-      min = std::max(min, bound_min + increment_type->Min());
+      double bound_min_next_iteration;
+      if (arithmeticType == InductionVariable::ArithmeticType::kAddition) {
+        // find min, i.e., add the smallest negative value
+        bound_min_next_iteration = bound_min + increment_type->Min();
+      } else {
+        // find min, i.e., subtract the largest positive value
+        bound_min_next_iteration = bound_min - increment_type->Max();
+      }
+      min = std::max(min, bound_min_next_iteration);
     }
     // The lower bound must be at most the initial value's lower bound.
     min = std::min(min, initial_type->Min());
   } else {
     // Shortcut: If the increment can be both positive and negative,
     // the variable can go arbitrarily far, so just return integer.
     return typer_->cache_.kInteger;
   }
   if (FLAG_trace_turbo_loop) {
     OFStream os(stdout);
     os << std::setprecision(10);
     os << "Loop (" << NodeProperties::GetControlInput(node)->id()
-       << ") variable bounds for phi " << node->id() << ": (" << min << ", "
-       << max << ")\n";
+       << ") variable bounds in "
+       << (arithmeticType == InductionVariable::ArithmeticType::kAddition
+               ? "addition"
+               : "subtraction")
+       << " for phi " << node->id() << ": (" << min << ", " << max << ")\n";
   }
   return Type::Range(min, max, typer_->zone());
 }
 
 Type* Typer::Visitor::TypeEffectPhi(Node* node) {
   UNREACHABLE();
   return nullptr;
 }
 
 Type* Typer::Visitor::TypeLoopExit(Node* node) {
@@ skipping 1606 matching lines @@
   }
   if (Type::IsInteger(*value)) {
     return Type::Range(value->Number(), value->Number(), zone());
   }
   return Type::Constant(value, zone());
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8