Optimize the multiplication of two 32-bit unsigned integers.

runtime/vm/intermediate_language_arm.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_ARM.
 #if defined(TARGET_ARCH_ARM)
 
 #include "vm/intermediate_language.h"
 
 #include "vm/cpu.h"
@@ skipping 6112 matching lines @@
         ASSERT(op_kind() == Token::kSUB);
         __ subs(out_lo, left_lo, Operand(right_lo));
         __ sbcs(out_hi, left_hi, Operand(right_hi));
       }
       if (can_overflow()) {
         // Deopt on overflow.
         __ b(deopt, VS);
       }
       break;
     }
-    default:
-      UNREACHABLE();
-    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.
+      if (TargetCPUFeatures::arm_version() == ARMv7) {
+        __ orrs(out_hi, left_hi, Operand(right_hi));
+        __ b(deopt, NE);
+        __ smull(out_lo, out_hi, left_lo, right_lo);

[Vyacheslav Egorov (Google), 2014/07/16 23:51:35]

should not this be umul given that we look at hi? (smul and umul match at lo
part but not on hi).

I feel like this miscomputes result of 0xFFFFFFFF * 0xFFFFFFFF which would be 1
after smul but should not be.

Please write a pure Dart test on this.

[regis, 2014/07/18 02:44:56]

You are right. This should have been an unsigned multiplication as on IA32.

In the next revision, it is back to a signed multiplication. See below.

I agree that tests would be nice, but it is really tricky to target optimized
code. The code could have called deopt and the result is still correct. Any tips
are welcome.

[Vyacheslav Egorov (Google), 2014/07/18 11:15:34]

Well this particular case would not call a deopt right? 0xFFFFFFFF has hi == 0
so the first deopt will not happen. Result of multplication with smull would
have hi == 0 too so the second deopt would not happen either. 

I just wanted to have a regression test for cases that miscomputes. If deopt
happens we are fine :)

+        if (can_overflow()) {
+          __ TestImmediate(out_hi, 0xC0000000);
+          __ b(deopt, NE);
+        }
+      } else {
+        __ b(deopt);
+      }
+      break;
+    }
+    default: UNREACHABLE();
   }
   if (FLAG_throw_on_javascript_int_overflow) {
     EmitJavascriptIntOverflowCheck(compiler, deopt, out_lo, out_hi);
   }
 }
 
 
 LocationSummary* ShiftMintOpInstr::MakeLocationSummary(Isolate* isolate,
                                                        bool opt) const {
   const intptr_t kNumInputs = 2;
@@ skipping 163 matching lines @@
   summary->set_out(0, Location::RequiresRegister());
   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:
       __ and_(out, left, Operand(right));
-    break;
+      break;
     case Token::kBIT_OR:
       __ orr(out, left, Operand(right));
-    break;
+      break;
     case Token::kBIT_XOR:
       __ eor(out, left, Operand(right));
-    break;
+      break;
     case Token::kADD:
       __ add(out, left, Operand(right));
-    break;
+      break;
     case Token::kSUB:
       __ sub(out, left, Operand(right));
-    break;
+      break;
+    case Token::kMUL: {
+      if (TargetCPUFeatures::arm_version() == ARMv7) {
+        __ smull(out, IP, left, right);

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

Have you tested this code path?

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

Yes, I have ran all the tests, including the RSA benchmark with
--unbox_mints=true and false.

I have not tested the path when we do not have ARMv7, however. But I changed
this code not to check for overflow and can use the MUL instruction available on
all supported ARM versions.

+        __ TestImmediate(IP, 0xC0000000);
+        __ b(deopt, NE);
+      } else {
+        __ b(deopt);
+      }
+      break;
+    }
     default:
       UNREACHABLE();
   }
 }
 
 
 LocationSummary* ShiftUint32OpInstr::MakeLocationSummary(Isolate* isolate,
                                                          bool opt) const {
   const intptr_t kNumInputs = 2;
   const intptr_t kNumTemps = 1;
@@ skipping 471 matching lines @@
   compiler->GenerateCall(token_pos(), &label, stub_kind_, locs());
 #if defined(DEBUG)
   __ LoadImmediate(R4, kInvalidObjectPointer);
   __ LoadImmediate(R5, kInvalidObjectPointer);
 #endif
 }
 
 }  // namespace dart
 
 #endif  // defined TARGET_ARCH_ARM