Optimize the multiplication of two 32-bit unsigned integers.

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 633 matching lines @@
 }
 
 
 Condition TestCidsInstr::EmitComparisonCode(FlowGraphCompiler* compiler,
                                             BranchLabels labels) {
   ASSERT((kind() == Token::kIS) || (kind() == Token::kISNOT));
   Register val_reg = locs()->in(0).reg();
   Register cid_reg = locs()->temp(0).reg();
 
   Label* deopt = CanDeoptimize() ?
-  compiler->AddDeoptStub(deopt_id(), ICData::kDeoptTestCids) : NULL;
+      compiler->AddDeoptStub(deopt_id(), ICData::kDeoptTestCids) : NULL;
 
   const intptr_t true_result = (kind() == Token::kIS) ? 1 : 0;
   const ZoneGrowableArray<intptr_t>& data = cid_results();
   ASSERT(data[0] == kSmiCid);
   bool result = data[1] == true_result;
   __ testl(val_reg, Immediate(kSmiTagMask));
   __ j(ZERO, result ? labels.true_label : labels.false_label);
   __ LoadClassId(cid_reg, val_reg);
   for (intptr_t i = 2; i < data.length(); i += 2) {
     const intptr_t test_cid = data[i];
@@ skipping 5174 matching lines @@
   __ Bind(&done);
 }
 
 
 LocationSummary* BinaryMintOpInstr::MakeLocationSummary(Isolate* isolate,
                                                         bool opt) const {
   const intptr_t kNumInputs = 2;
   switch (op_kind()) {
     case Token::kBIT_AND:
     case Token::kBIT_OR:
-    case Token::kBIT_XOR: {
+    case Token::kBIT_XOR:
+    case Token::kADD:
+    case Token::kSUB: {
       const intptr_t kNumTemps = 0;
       LocationSummary* summary = new(isolate) LocationSummary(
           isolate, kNumInputs, kNumTemps, LocationSummary::kNoCall);
       summary->set_in(0, Location::Pair(Location::RequiresRegister(),
                                         Location::RequiresRegister()));
       summary->set_in(1, Location::Pair(Location::RequiresRegister(),
                                         Location::RequiresRegister()));
       summary->set_out(0, Location::SameAsFirstInput());
       return summary;
     }
-    case Token::kADD:
-    case Token::kSUB: {
+    case Token::kMUL: {
       const intptr_t kNumTemps = 0;
       LocationSummary* summary = new(isolate) LocationSummary(
           isolate, kNumInputs, kNumTemps, LocationSummary::kNoCall);
-      summary->set_in(0, Location::Pair(Location::RequiresRegister(),
-                                        Location::RequiresRegister()));
+      summary->set_in(0, Location::Pair(Location::RegisterLocation(EAX),
+                                        Location::RegisterLocation(EDX)));
       summary->set_in(1, Location::Pair(Location::RequiresRegister(),
                                         Location::RequiresRegister()));
-      summary->set_out(0, Location::SameAsFirstInput());
+      summary->set_out(0, Location::Pair(Location::RegisterLocation(EAX),
+                                         Location::RegisterLocation(EDX)));
       return summary;
     }
     default:
       UNREACHABLE();
       return NULL;
   }
 }
 
 
 void BinaryMintOpInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
@@ skipping 33 matching lines @@
         __ adcl(left_hi, right_hi);
       } else {
         __ subl(left_lo, right_lo);
         __ sbbl(left_hi, right_hi);
       }
       if (can_overflow()) {
         __ j(OVERFLOW, deopt);
       }
       break;
     }
+    case Token::kMUL: {
+      // We only support the multiplication of two positive 32-bit integers
+      // resulting in a positive 64-bit integer fitting in a mint.
+      // We deopt in all other cases.
+      // This guarantees that the multiplication of 16-bit unsigned integers,
+      // as used in bignum arithmetic, will always succeed.
+      __ orl(left_hi, right_hi);
+      __ j(NOT_ZERO, deopt);
+      ASSERT(left_lo == EAX);
+      __ mull(right_lo);  // Result in EDX:EAX.
+      if (can_overflow()) {
+        __ testl(right_hi, Immediate(0xc0000000));
+        __ shrl(right_hi, Immediate(30));

[sra1, 2014/07/16 00:58:27]

Maybe I misunderstand, but...

Why test right_hi? Surely it is zero from the orl/jnz test?
The product is in EDX:EAX which is aliased to left_hi:left_lo and out_hi:out_lo.

Should shrl be removed?
The flags generated by testl flags are killed by shrl, and doesn't shrl kill the
high word of the result?

[regis, 2014/07/16 02:23:22]

Oops, the shrl is left over from a previous version and is redundant here. Yes,
it should be removed.

Also, it should be out_hi, not right_hi. I should have tested with
--unbox_mints=false

out_hi is guaranteed to be EDX and it contains the upper 32-bit of the result.
I've added asserts.

Thanks!

+        __ j(NOT_ZERO, deopt);
+      }
+      break;
+    }
     default: UNREACHABLE();
   }
   if (FLAG_throw_on_javascript_int_overflow) {
     EmitJavascriptIntOverflowCheck(compiler, deopt, left_lo, left_hi);
   }
 }
 
 
 LocationSummary* ShiftMintOpInstr::MakeLocationSummary(Isolate* isolate,
                                                        bool opt) const {
@@ skipping 253 matching lines @@
 
 
 CompileType UnboxUint32Instr::ComputeType() const {
   return CompileType::Int();
 }
 
 
 LocationSummary* BinaryUint32OpInstr::MakeLocationSummary(Isolate* isolate,
                                                           bool opt) const {
   const intptr_t kNumInputs = 2;
-  const intptr_t kNumTemps = 0;
+  const intptr_t kNumTemps = (op_kind() == Token::kMUL) ? 1 : 0;
   LocationSummary* summary = new(isolate) LocationSummary(
       isolate, kNumInputs, kNumTemps, LocationSummary::kNoCall);
-  summary->set_in(0, Location::RequiresRegister());
+  if (op_kind() == Token::kMUL) {
+    summary->set_in(0, Location::RegisterLocation(EAX));
+    summary->set_temp(0, Location::RegisterLocation(EDX));
+  } else {
+    summary->set_in(0, Location::RequiresRegister());
+  }
   summary->set_in(1, Location::RequiresRegister());
   summary->set_out(0, Location::SameAsFirstInput());
   return summary;
 }
 
 
 void BinaryUint32OpInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
   Register left = locs()->in(0).reg();
   Register right = locs()->in(1).reg();
   Register out = locs()->out(0).reg();
   ASSERT(out == left);
+  Label* deopt = CanDeoptimize() ?
+      compiler->AddDeoptStub(deopt_id(), ICData::kDeoptBinaryUint32Op) : NULL;
   switch (op_kind()) {
     case Token::kBIT_AND:
       __ andl(out, right);
-    break;
+      break;
     case Token::kBIT_OR:
       __ orl(out, right);
-    break;
+      break;
     case Token::kBIT_XOR:
       __ xorl(out, right);
-    break;
+      break;
     case Token::kADD:
       __ addl(out, right);
-    break;
+      break;
     case Token::kSUB:
       __ subl(out, right);
-    break;
+      break;
+    case Token::kMUL:
+      __ mull(right);  // Result in EDX:EAX, CF set if EDX != 0.
+      __ j(OVERFLOW, deopt);
+      break;
     default:
       UNREACHABLE();
   }
 }
 
 
 LocationSummary* ShiftUint32OpInstr::MakeLocationSummary(Isolate* isolate,
                                                          bool opt) const {
   const intptr_t kNumInputs = 2;
   const intptr_t kNumTemps = 0;
@@ skipping 594 matching lines @@
   __ movl(EDX, Immediate(kInvalidObjectPointer));
   __ movl(EDX, Immediate(kInvalidObjectPointer));
 #endif
 }
 
 }  // namespace dart
 
 #undef __
 
 #endif  // defined TARGET_ARCH_IA32