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: {
-      const intptr_t kNumTemps = 0;
+    case Token::kBIT_XOR:
+    case Token::kADD:
+    case Token::kSUB:
+    case Token::kMUL: {
+      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::Pair(Location::RequiresRegister(),
-                                        Location::RequiresRegister()));
+      summary->set_in(0, (op_kind() == Token::kMUL)
+          ? Location::Pair(Location::RegisterLocation(EAX),
+                           Location::RegisterLocation(EDX))
+          : 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: {
-      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());
+      if (kNumTemps > 0) {
+        summary->set_temp(0, Location::RequiresRegister());
+      }
       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;
     }
-    default: UNREACHABLE();
+    case Token::kMUL: {
+      // The product of two signed 32-bit integers fits in a signed 64-bit
+      // result without causing overflow.
+      // We deopt on larger inputs.
+      Register temp = locs()->temp(0).reg();

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

Please add TODO here and in another place use range analysis to remove this
check whenever possible

[regis, 2014/07/18 17:59:43]

Done.

+      __ movl(temp, left_lo);
+      __ sarl(temp, Immediate(31));
+      __ cmpl(temp, left_hi);
+      __ j(NOT_EQUAL, deopt);
+      __ movl(temp, right_lo);
+      __ sarl(temp, Immediate(31));
+      __ cmpl(temp, right_hi);
+      __ j(NOT_EQUAL, deopt);
+      ASSERT(left_lo == EAX);
+      __ imull(right_lo);  // Result in EDX:EAX.
+      ASSERT(out_lo == EAX);
+      ASSERT(out_hi == EDX);
+      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 {
   const intptr_t kNumInputs = 2;
@@ skipping 172 matching lines @@
           __ Bind(&large_shift);
           // No need to subtract 32 from CL, only 5 bits used by shll.
           __ movl(left_hi, left_lo);  // Shift by 32.
           __ xorl(left_lo, left_lo);  // Zero left_lo.
           __ shll(left_hi, ECX);  // Shift count: CL % 32.
         }
         break;
       }
       default:
         UNREACHABLE();
-        break;
     }
     __ Bind(&done);
   }
   if (FLAG_throw_on_javascript_int_overflow) {
     EmitJavascriptIntOverflowCheck(compiler, deopt, left_lo, left_hi);
   }
 }
 
 
 LocationSummary* UnaryMintOpInstr::MakeLocationSummary(Isolate* isolate,
@@ skipping 58 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);
   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.
+      ASSERT(out == EAX);
+      ASSERT(locs()->temp(0).reg() == EDX);
+      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