[turbofan] Induction variable decrement bound analysis.

src/compiler/loop-variable-optimizer.cc

 // Copyright 2016 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/loop-variable-optimizer.h"
 
 #include "src/compiler/common-operator.h"
 #include "src/compiler/graph.h"
 #include "src/compiler/node-marker.h"
 #include "src/compiler/node-properties.h"
@@ skipping 170 matching lines @@
         NodeProperties::GetControlInput(constraint->left()) == loop) {
       auto var = induction_vars_.find(constraint->left()->id());
       if (var != induction_vars_.end()) {
         var->second->AddUpperBound(constraint->right(), constraint->kind());
       }
     }
     if (constraint->right()->opcode() == IrOpcode::kPhi &&
         NodeProperties::GetControlInput(constraint->right()) == loop) {
       auto var = induction_vars_.find(constraint->right()->id());
       if (var != induction_vars_.end()) {
-        var->second->AddUpperBound(constraint->left(), constraint->kind());
+        var->second->AddLowerBound(constraint->left(), constraint->kind());

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

Awesome, thanks for the fix! After a bit of thinking, I believe this is a bad
bug. For example, the program below does not terminate.

function f() {
  for (var i = 5; i < 10; i++) {
    if (i < 0) break;
    if (i === 7) return true;
  }
  return false;
}

f();
f();
%OptimizeFunctionOnNextCall(f);
print(f());

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

Done.

       }
     }
   }
 }
 
 void LoopVariableOptimizer::VisitNode(Node* node) {
   switch (node->opcode()) {
     case IrOpcode::kMerge:
       return VisitMerge(node);
     case IrOpcode::kLoop:
@@ skipping 94 matching lines @@
     return var->second;
   }
   return nullptr;
 }
 
 InductionVariable* LoopVariableOptimizer::TryGetInductionVariable(Node* phi) {
   DCHECK_EQ(2, phi->op()->ValueInputCount());
   DCHECK_EQ(IrOpcode::kLoop, NodeProperties::GetControlInput(phi)->opcode());
   Node* initial = phi->InputAt(0);
   Node* arith = phi->InputAt(1);
-  // TODO(jarin) Support subtraction.
-  if (arith->opcode() != IrOpcode::kJSAdd) {
+  InductionVariable::ArithmeticType arithmeticType;
+  if (arith->opcode() == IrOpcode::kJSAdd) {
+    arithmeticType = InductionVariable::ArithmeticType::kAddition;
+  } else if (arith->opcode() == IrOpcode::kJSSubtract) {
+    arithmeticType = InductionVariable::ArithmeticType::kSubtraction;
+  } else {
     return nullptr;
   }
+
   // TODO(jarin) Support both sides.
   if (arith->InputAt(0) != phi) {
     if (arith->InputAt(0)->opcode() != IrOpcode::kJSToNumber ||
         arith->InputAt(0)->InputAt(0) != phi) {
       return nullptr;
     }
   }
   Node* incr = arith->InputAt(1);
-  return new (zone()) InductionVariable(phi, arith, incr, initial, zone());
+  return new (zone())
+      InductionVariable(phi, arith, incr, initial, zone(), arithmeticType);
 }
 
 void LoopVariableOptimizer::DetectInductionVariables(Node* loop) {
   if (loop->op()->ControlInputCount() != 2) return;
   TRACE("Loop variables for loop %i:", loop->id());
   for (Edge edge : loop->use_edges()) {
     if (NodeProperties::IsControlEdge(edge) &&
         edge.from()->opcode() == IrOpcode::kPhi) {
       Node* phi = edge.from();
       InductionVariable* induction_var = TryGetInductionVariable(phi);
@@ skipping 62 matching lines @@
                                         backedge_value, backedge_control);
         induction_var->phi()->ReplaceInput(1, rename);
       }
     }
   }
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8