Use range information to omit checks in TRUNCDIV/MOD operations.

runtime/vm/intermediate_language_ia32.cc

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/globals.h"  // Needed here to get TARGET_ARCH_IA32.
 #if defined(TARGET_ARCH_IA32)
 
 #include "vm/intermediate_language.h"
 
 #include "vm/dart_entry.h"
@@ skipping 2402 matching lines @@
         break;
       }
       default:
         UNREACHABLE();
     }
     return;
   }  // if locs()->in(1).IsStackSlot.
 
   // if locs()->in(1).IsRegister.
   Register right = locs()->in(1).reg();
+  Range* right_range = this->right()->definition()->range();
   switch (op_kind()) {
     case Token::kADD: {
       __ addl(left, right);
       if (deopt != NULL) __ j(OVERFLOW, deopt);
       break;
     }
     case Token::kSUB: {
       __ subl(left, right);
       if (deopt != NULL) __ j(OVERFLOW, deopt);
       break;
@@ skipping 13 matching lines @@
       // No overflow check.
       __ orl(left, right);
       break;
     }
     case Token::kBIT_XOR: {
       // No overflow check.
       __ xorl(left, right);
       break;
     }
     case Token::kTRUNCDIV: {
-      // Handle divide by zero in runtime.
-      __ testl(right, right);
-      __ j(ZERO, deopt);
+      if ((right_range == NULL) || right_range->IsWithin(0, 0)) {

[Florian Schneider, 2013/11/22 15:17:11]

Please also make sure that there is test coverage of all the cases. What if
right_range is [-5, 5]?
In this case you need a check, but [-5, 5]->IsWithin(0, 0) would return false
and the check would be omitted.

[srdjan, 2013/11/22 22:08:17]

Added test coverage, added Range::Overlaps function.

+        // Handle divide by zero in runtime.
+        __ testl(right, right);
+        __ j(ZERO, deopt);
+      }
       ASSERT(left == EAX);
       ASSERT((right != EDX) && (right != EAX));
       ASSERT(locs()->temp(0).reg() == EDX);
       ASSERT(result == EAX);
       __ SmiUntag(left);
       __ SmiUntag(right);
       __ cdq();  // Sign extend EAX -> EDX:EAX.
       __ idivl(right);  //  EAX: quotient, EDX: remainder.
       // Check the corner case of dividing the 'MIN_SMI' with -1, in which
       // case we cannot tag the result.
       __ cmpl(result, Immediate(0x40000000));
       __ j(EQUAL, deopt);
       __ SmiTag(result);
       break;
     }
     case Token::kMOD: {
-      // Handle divide by zero in runtime.
-      __ testl(right, right);
-      __ j(ZERO, deopt);
+      if ((right_range == NULL) || right_range->IsWithin(0, 0)) {
+        // Handle divide by zero in runtime.
+        __ testl(right, right);
+        __ j(ZERO, deopt);
+      }

[Florian Schneider, 2013/11/22 15:17:11]

In the case that the instruction can't deoptimize because of div-by-zero
anymore, you should return false for CanDeoptimize() to avoid having unnessesary
environment uses.

[srdjan, 2013/11/22 22:08:17]

Changed BinarySmiOperation::CanDeoptimize.

       ASSERT(left == EDX);
       ASSERT((right != EDX) && (right != EAX));
       ASSERT(locs()->temp(0).reg() == EAX);
       ASSERT(result == EDX);
       __ SmiUntag(left);
       __ SmiUntag(right);
       __ movl(EAX, EDX);
       __ cdq();  // Sign extend EAX -> EDX:EAX.
       __ idivl(right);  //  EAX: quotient, EDX: remainder.
       //  res = left % right;
       //  if (res < 0) {
       //    if (right < 0) {
       //      res = res - right;
       //    } else {
       //      res = res + right;
       //    }
       //  }
-      Label subtract, done;
+      Label done;
       __ cmpl(result, Immediate(0));
       __ j(GREATER_EQUAL, &done, Assembler::kNearJump);
       // Result is negative, adjust it.
-      __ cmpl(right, Immediate(0));
-      __ j(LESS, &subtract, Assembler::kNearJump);
-      __ addl(result, right);
-      __ jmp(&done, Assembler::kNearJump);
-      __ Bind(&subtract);
-      __ subl(result, right);
+      if ((right_range == NULL) || right_range->IsWithin(-1, 1)) {
+        Label subtract;
+        __ cmpl(right, Immediate(0));
+        __ j(LESS, &subtract, Assembler::kNearJump);
+        __ addl(result, right);
+        __ jmp(&done, Assembler::kNearJump);
+        __ Bind(&subtract);
+        __ subl(result, right);
+      } else if (right_range->IsWithin(0, RangeBoundary::kPlusInfinity)) {
+        // Right is positive.
+        __ addl(result, right);
+      } else {
+        // Right is negative.
+        __ subl(result, right);
+      }
       __ Bind(&done);
       __ SmiTag(result);
       break;
     }
     case Token::kSHR: {
       if (CanDeoptimize()) {
         __ cmpl(right, Immediate(0));
         __ j(LESS, deopt);
       }
       __ SmiUntag(right);
       // sarl operation masks the count to 5 bits.
       const intptr_t kCountLimit = 0x1F;
-      Range* right_range = this->right()->definition()->range();
       if ((right_range == NULL) ||
           !right_range->IsWithin(RangeBoundary::kMinusInfinity, kCountLimit)) {
         __ cmpl(right, Immediate(kCountLimit));
         Label count_ok;
         __ j(LESS, &count_ok, Assembler::kNearJump);
         __ movl(right, Immediate(kCountLimit));
         __ Bind(&count_ok);
       }
       ASSERT(right == ECX);  // Count must be in ECX
       __ SmiUntag(left);
@@ skipping 1472 matching lines @@
 void MergedMathInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
   Label* deopt = NULL;
   if (CanDeoptimize()) {
     deopt  = compiler->AddDeoptStub(deopt_id(), kDeoptBinarySmiOp);
   }
 
   if (kind() == MergedMathInstr::kTruncDivMod) {
     Register left = locs()->in(0).reg();
     Register right = locs()->in(1).reg();
     Register result = locs()->out().reg();
-    // Handle divide by zero in runtime.
-    __ testl(right, right);
-    __ j(ZERO, deopt);
+    Range* right_range = InputAt(1)->definition()->range();
+    if ((right_range == NULL) || right_range->IsWithin(0, 0)) {
+      // Handle divide by zero in runtime.
+      __ testl(right, right);
+      __ j(ZERO, deopt);
+    }
     ASSERT(left == EAX);
     ASSERT((right != EDX) && (right != EAX));
     ASSERT(locs()->temp(0).reg() == EDX);
     ASSERT((result != EDX) && (result != EAX));
     __ SmiUntag(left);
     __ SmiUntag(right);
     __ cdq();  // Sign extend EAX -> EDX:EAX.
     __ idivl(right);  //  EAX: quotient, EDX: remainder.
     // Check the corner case of dividing the 'MIN_SMI' with -1, in which
     // case we cannot tag the result.
     // TODO(srdjan): We could store instead untagged intermediate results in a
     // typed array, but then the load indexed instructions would need to be
     // able to deoptimize.
     __ cmpl(EAX, Immediate(0x40000000));
     __ j(EQUAL, deopt);
     // Modulo result (EDX) correction:
     //  res = left % right;
     //  if (res < 0) {
     //    if (right < 0) {
     //      res = res - right;
     //    } else {
     //      res = res + right;
     //    }
     //  }
-    Label subtract, done;
+    Label done;
     __ cmpl(EDX, Immediate(0));
     __ j(GREATER_EQUAL, &done, Assembler::kNearJump);
     // Result is negative, adjust it.
-    __ cmpl(right, Immediate(0));
-    __ j(LESS, &subtract, Assembler::kNearJump);
-    __ addl(EDX, right);
-    __ jmp(&done, Assembler::kNearJump);
-    __ Bind(&subtract);
-    __ subl(EDX, right);
+    if ((right_range == NULL) || right_range->IsWithin(-1, 1)) {
+      Label subtract;
+      __ cmpl(right, Immediate(0));
+      __ j(LESS, &subtract, Assembler::kNearJump);
+      __ addl(EDX, right);
+      __ jmp(&done, Assembler::kNearJump);
+      __ Bind(&subtract);
+      __ subl(EDX, right);
+    } else if (right_range->IsWithin(0, RangeBoundary::kPlusInfinity)) {
+      // Right is positive.
+      __ addl(EDX, right);
+    } else {
+      // Right is negative.
+      __ subl(EDX, right);
+    }
     __ Bind(&done);
 
     __ LoadObject(result, Array::ZoneHandle(Array::New(2, Heap::kOld)));
     const intptr_t index_scale = FlowGraphCompiler::ElementSizeFor(kArrayCid);
     Address trunc_div_address(
         FlowGraphCompiler::ElementAddressForIntIndex(kArrayCid,
                                                      index_scale,
                                                      result,
                                                      0));
     Address mod_address(
@@ skipping 910 matching lines @@
                          PcDescriptors::kOther,
                          locs());
   __ Drop(2);  // Discard type arguments and receiver.
 }
 
 }  // namespace dart
 
 #undef __
 
 #endif  // defined TARGET_ARCH_IA32