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.
+      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) {
     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.

[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();
   }
 }
 
 
 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