Optimize the multiplication of two 32-bit unsigned integers.

runtime/vm/intermediate_language_ia32.cc

Index: runtime/vm/intermediate_language_ia32.cc
===================================================================
--- runtime/vm/intermediate_language_ia32.cc	(revision 38266)
+++ runtime/vm/intermediate_language_ia32.cc	(working copy)
@@ -651,7 +651,7 @@
   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();
@@ -5846,7 +5846,9 @@
   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);
@@ -5857,16 +5859,16 @@
       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:
@@ -5920,6 +5922,24 @@
       }
       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.
+      ASSERT(out_lo == EAX);
+      ASSERT(out_hi == EDX);
+      if (can_overflow()) {
+        __ testl(out_hi, Immediate(0xc0000000));
+        __ j(NOT_ZERO, deopt);

[Vyacheslav Egorov (Google), 2014/07/16 19:51:22]

I am very wary of this kind of optimistic optimizations that have no built-in
mechanism for disabling them. If somebody writes multiplication that from time
to time multiplies smth non uint32-ish then their code will be stuck in the
deoptimization loop. 

We saw example of why such situations are not desirable with Uint32List loads.

Additionally this feels somewhat backwards to me: should not we just ensure that
bigint arithmetic never emits this kind of multiplication? We started UInt32
support precisely for this reason. If it does not hit the code that we are
writing ourselves then maybe we should fix it first.

[regis, 2014/07/16 23:12:42]

Fair enough. I have added a range check, so that this code is only generated if
the inputs are guaranteed to be uint32. In other words, the code does not check
the inputs anymore. However, the code can still deopt if the result is too
large, but I think this is OK and no different than deopt for addition or
subtraction.

The new bigint implementation is not yes complete and critical parts will be
hand coded in assembly. For now, 16-bit positive smis are multiplied and result
in positive mints. In order for these to be handled by unit32 ops, corresponding
mint ops must exist to be replaced. This is why I had to implement this mint
code.

+      }
+      break;
+    }
     default: UNREACHABLE();
   }
   if (FLAG_throw_on_javascript_int_overflow) {
@@ -6193,10 +6213,15 @@
 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;
@@ -6208,22 +6233,28 @@
   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.

[Cutch, 2014/07/16 18:09:48]

Uint32 operations are only used in places where we know we don't care about
overflow.

[regis, 2014/07/16 23:12:42]

I have removed the overflow check.

+      __ j(OVERFLOW, deopt);
+      break;
     default:
       UNREACHABLE();
   }