Use SAR for positive divident by a power-of two constant divisor.

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 "lib/error.h"
@@ skipping 1933 matching lines @@
   __ cmpl(ESP,
           Address::Absolute(Isolate::Current()->stack_limit_address()));
   __ j(BELOW_EQUAL, slow_path->entry_label());
   __ Bind(slow_path->exit_label());
 }
 
 
 LocationSummary* BinarySmiOpInstr::MakeLocationSummary() const {
   const intptr_t kNumInputs = 2;
   if (op_kind() == Token::kTRUNCDIV) {
-    const intptr_t kNumTemps = 1;
+    const intptr_t kNumTemps = RightIsPowerOfTwoConstant() ? 2 : 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(EAX));
-    summary->set_in(1, Location::WritableRegister());
+    if (kNumTemps == 1) {
+      summary->set_in(1, Location::WritableRegister());
+    } else {
+      ConstantInstr* right_constant = right()->definition()->AsConstant();
+      summary->set_in(1, Location::Constant(right_constant->value()));
+      // Temporary to hold divisor constant.
+      summary->set_temp(1, Location::RegisterLocation(EBX));
+    }
     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::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));
@@ skipping 19 matching lines @@
   }
 }
 
 
 void BinarySmiOpInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
   Register left = locs()->in(0).reg();
   Register result = locs()->out().reg();
   ASSERT(left == result);
   Label* deopt = NULL;
   if (CanDeoptimize()) {
-      deopt  = compiler->AddDeoptStub(deopt_id(),
-                                      kDeoptBinarySmiOp);
+    deopt  = compiler->AddDeoptStub(deopt_id(), kDeoptBinarySmiOp);
   }
 
   if (locs()->in(1).IsConstant()) {
     const Object& constant = locs()->in(1).constant();
     ASSERT(constant.IsSmi());
     const int32_t imm =
         reinterpret_cast<int32_t>(constant.raw());
     switch (op_kind()) {
       case Token::kADD:
         __ addl(left, Immediate(imm));
         if (deopt != NULL) __ j(OVERFLOW, deopt);
         break;
       case Token::kSUB: {
         __ subl(left, Immediate(imm));
         if (deopt != NULL) __ j(OVERFLOW, deopt);
         break;
       }
       case Token::kMUL: {
         // Keep left value tagged and untag right value.
         const intptr_t value = Smi::Cast(constant).Value();
         __ imull(left, Immediate(value));
         if (deopt != NULL) __ j(OVERFLOW, deopt);
         break;
       }
+      case Token::kTRUNCDIV: {
+        Label use_div, done;
+        const intptr_t value = Smi::Cast(constant).Value();
+        ASSERT((value > 0) && Utils::IsPowerOfTwo(value));
+        __ cmpl(left, Immediate(0));

[Florian Schneider, 2013/02/01 11:48:33]

For checking x < 0, this sequence is 1 byte shorter:

__ testl(left, left);
__ j(NEGATIVE, &use_div, Assembler::kNearJump);

+        __ j(LESS, &use_div, Assembler::kNearJump);
+        // Positive division by power of two is an arithmetic left shift.

[Florian Schneider, 2013/02/01 11:48:33]

In the comment s/left/right/.

[srdjan, 2013/02/01 22:57:54]

Done.

+        intptr_t shift_count = Utils::ShiftForPowerOfTwo(value) + kSmiTagSize;
+        __ sarl(left, Immediate(shift_count));
+        __ jmp(&done, Assembler::kNearJump);
+        __ Bind(&use_div);

[Florian Schneider, 2013/02/01 11:48:33]

I think this could be improved for negative numbers: How about compiling it into
something similar to what gcc generates for integer division by a power of two:

result = left >= 0 
           ? left >> log2(right)
           : (left + (right - 1)) >> log2(right);

It can be further generalized to allow negative powers of two.

[Florian Schneider, 2013/02/04 13:04:02]

Yes, my mistake: of course the absolute value of right must be used in this
formula.

+        Register right = locs()->temp(1).reg();
+        ASSERT(left == EAX);
+        ASSERT((right != EDX) && (right != EAX));
+        ASSERT(locs()->temp(0).reg() == EDX);
+        ASSERT(result == EAX);
+        __ movl(right, Immediate(value));
+        __ SmiUntag(left);
+        __ 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

[Florian Schneider, 2013/02/01 11:48:33]

Since the right side is a known constant, you can avoid checking for that corner
case in all cases except when  generating (x ~/ -1).

+        // case we cannot tag the result.
+        __ cmpl(result, Immediate(0x40000000));
+        __ j(EQUAL, deopt);
+        __ Bind(&done);
+        __ SmiTag(result);
+        break;
+      }
       case Token::kBIT_AND: {
         // No overflow check.
         __ andl(left, Immediate(imm));
         break;
       }
       case Token::kBIT_OR: {
         // No overflow check.
         __ orl(left, Immediate(imm));
         break;
       }
@@ skipping 1331 matching lines @@
                          PcDescriptors::kOther,
                          locs());
   __ Drop(2);  // Discard type arguments and receiver.
 }
 
 }  // namespace dart
 
 #undef __
 
 #endif  // defined TARGET_ARCH_IA32