Inline integer modulo operation.

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 2188 matching lines @@
       summary->set_out(Location::SameAsFirstInput());
     } else {
       // Both inputs must be writable because they will be untagged.
       summary->set_in(0, Location::RegisterLocation(EAX));
       summary->set_in(1, Location::WritableRegister());
       summary->set_out(Location::SameAsFirstInput());
       // Will be used for sign extension and division.
       summary->set_temp(0, Location::RegisterLocation(EDX));
     }
     return summary;
+  } else if (op_kind() == Token::kMOD) {
+    const intptr_t kNumTemps = 1;
+    LocationSummary* summary =
+        new LocationSummary(kNumInputs, kNumTemps, LocationSummary::kNoCall);
+    // Both inputs must be writable because they will be untagged.
+    summary->set_in(0, Location::RegisterLocation(EDX));
+    summary->set_in(1, Location::WritableRegister());
+    summary->set_out(Location::SameAsFirstInput());
+    // Will be used for sign extension and division.
+    summary->set_temp(0, Location::RegisterLocation(EAX));
+    return summary;
   } else if (op_kind() == Token::kSHR) {
     const intptr_t kNumTemps = 0;
     LocationSummary* summary =
         new LocationSummary(kNumInputs, kNumTemps, LocationSummary::kNoCall);
     summary->set_in(0, Location::RequiresRegister());
     summary->set_in(1, Location::FixedRegisterOrSmiConstant(right(), ECX));
     summary->set_out(Location::SameAsFirstInput());
     return summary;
   } else if (op_kind() == Token::kSHL) {
     const intptr_t kNumTemps = 0;
@@ skipping 225 matching lines @@
       __ 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);

[sra1, 2013/11/07 00:50:23]

This should be unnecessary in cases where right == 10.
Does range information tell you this?

[srdjan, 2013/11/07 05:26:52]

Yes. I had the code in and have removed it in order to make the Cl simpler. The
cost of a division is so high that I could not measure any benefit by skipping
the tests here and below. I may try more measurements later. Having less
variations makes me more certain that the code is being tested.

[sra1, 2013/11/08 01:40:16]

I see.  The latency of idiv covers everything else in the loop.
Probably the only way left to win is to merge "val ~/ 10" and "val % 10" into a
single idiv.

[srdjan, 2013/11/08 16:02:53]

Yes, preliminary measurement show a big benefit of merging div/mod. That is what
I am (finally) working on next.

+      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;
+      __ cmpl(result, Immediate(0));
+      __ j(GREATER_EQUAL, &done, Assembler::kNearJump);

[sra1, 2013/11/07 00:50:23]

You might be able to test whether this is necessary.
The loop in Smi.toString has the guard "while (val > 0)" and right is the
constant 10 in "val % 10".  Does range information tell you this?

I believe the untagging and re-tagging is unnecessary, at least in the toString
case where both inputs are non-negative.

These comments mostly apply to "val ~/ 10" in the loop too - i.e. it might be
possible to remove three deopt checks and 5 tagging operations from the loop.

[srdjan, 2013/11/07 05:26:52]

Ditto. I have not used the val range, but the range of the right side. Have not
measured any benefits, but may add the appropriate guards later.

+      // 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);
+      __ 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);
       __ sarl(left, right);
       __ SmiTag(left);
       break;
     }
     case Token::kDIV: {
       // Dispatches to 'Double./'.
       // TODO(srdjan): Implement as conversion to double and double division.
       UNREACHABLE();
       break;
     }
-    case Token::kMOD: {
-      // TODO(srdjan): Implement.
-      UNREACHABLE();
-      break;
-    }
     case Token::kOR:
     case Token::kAND: {
       // Flow graph builder has dissected this operation to guarantee correct
       // behavior (short-circuit evaluation).
       UNREACHABLE();
       break;
     }
     default:
       UNREACHABLE();
       break;
@@ skipping 2423 matching lines @@
                          PcDescriptors::kOther,
                          locs());
   __ Drop(2);  // Discard type arguments and receiver.
 }
 
 }  // namespace dart
 
 #undef __
 
 #endif  // defined TARGET_ARCH_IA32