Consistenly handle power-of-2 divisors in division-like operations

src/a64/lithium-codegen-a64.cc

Index: src/a64/lithium-codegen-a64.cc
diff --git a/src/a64/lithium-codegen-a64.cc b/src/a64/lithium-codegen-a64.cc
index 3e87944b17192e85538b8c835cdf04310c049b2b..e35aa2eb63e97a57a43477f5428b6e60c3ec4538 100644
--- a/src/a64/lithium-codegen-a64.cc
+++ b/src/a64/lithium-codegen-a64.cc
@@ -2564,50 +2564,53 @@ void LCodeGen::DoDeoptimize(LDeoptimize* instr) {
 }
 
 
-void LCodeGen::DoDivI(LDivI* instr) {
-  if (!instr->is_flooring() && instr->hydrogen()->RightIsPowerOf2()) {
-    HDiv* hdiv = instr->hydrogen();
-    Register dividend = ToRegister32(instr->left());
-    int32_t divisor = hdiv->right()->GetInteger32Constant();
-    Register result = ToRegister32(instr->result());
-    ASSERT(!result.is(dividend));
+void LCodeGen::DoDivByPowerOf2I(LDivByPowerOf2I* instr) {
+  Register dividend = ToRegister32(instr->dividend());
+  int32_t divisor = instr->divisor();
+  Register result = ToRegister32(instr->result());
+  ASSERT(divisor == kMinInt || (divisor != 0 && IsPowerOf2(Abs(divisor))));
+  ASSERT(!result.is(dividend));
 
-    // Check for (0 / -x) that will produce negative zero.
-    if (hdiv->left()->RangeCanInclude(0) && divisor < 0 &&
-        hdiv->CheckFlag(HValue::kBailoutOnMinusZero)) {
-      __ Cmp(dividend, 0);
-      DeoptimizeIf(eq, instr->environment());
-    }
-    // Check for (kMinInt / -1).
-    if (hdiv->left()->RangeCanInclude(kMinInt) && divisor == -1 &&
-        hdiv->CheckFlag(HValue::kCanOverflow)) {
-      __ Cmp(dividend, kMinInt);
-      DeoptimizeIf(eq, instr->environment());
-    }
-    // Deoptimize if remainder will not be 0.
-    if (!hdiv->CheckFlag(HInstruction::kAllUsesTruncatingToInt32) &&
-        Abs(divisor) != 1) {
-      __ Tst(dividend, Abs(divisor) - 1);
-      DeoptimizeIf(ne, instr->environment());
-    }
-    if (divisor == -1) {  // Nice shortcut, not needed for correctness.
-      __ Neg(result, dividend);
-      return;
-    }
-    int32_t shift = WhichPowerOf2(Abs(divisor));
-    if (shift == 0) {
-      __ Mov(result, dividend);
-    } else if (shift == 1) {
-      __ Add(result, dividend, Operand(dividend, LSR, 31));
-    } else {
-      __ Mov(result, Operand(dividend, ASR, 31));
-      __ Add(result, dividend, Operand(result, LSR, 32 - shift));
-    }
-    if (shift > 0) __ Mov(result, Operand(result, ASR, shift));
-    if (divisor < 0) __ Neg(result, result);
+  // Check for (0 / -x) that will produce negative zero.
+  HDiv* hdiv = instr->hydrogen();
+  if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero) &&
+      hdiv->left()->RangeCanInclude(0) && divisor < 0) {
+    __ Cmp(dividend, 0);
+    DeoptimizeIf(eq, instr->environment());
+  }
+  // Check for (kMinInt / -1).
+  if (hdiv->CheckFlag(HValue::kCanOverflow) &&
+      hdiv->left()->RangeCanInclude(kMinInt) && divisor == -1) {
+    __ Cmp(dividend, kMinInt);
+    DeoptimizeIf(eq, instr->environment());
+  }
+  // Deoptimize if remainder will not be 0.
+  if (!hdiv->CheckFlag(HInstruction::kAllUsesTruncatingToInt32) &&
+      divisor != 1 && divisor != -1) {
+    int32_t mask = divisor < 0 ? -(divisor + 1) : (divisor - 1);
+    __ Tst(dividend, mask);
+    DeoptimizeIf(ne, instr->environment());
+  }
+
+  if (divisor == -1) {  // Nice shortcut, not needed for correctness.
+    __ Neg(result, dividend);
     return;
   }
+  int32_t shift = WhichPowerOf2Abs(divisor);
+  if (shift == 0) {
+    __ Mov(result, dividend);
+  } else if (shift == 1) {
+    __ Add(result, dividend, Operand(dividend, LSR, 31));
+  } else {
+    __ Mov(result, Operand(dividend, ASR, 31));
+    __ Add(result, dividend, Operand(result, LSR, 32 - shift));
+  }
+  if (shift > 0) __ Mov(result, Operand(result, ASR, shift));
+  if (divisor < 0) __ Neg(result, result);
+}
 
+
+void LCodeGen::DoDivI(LDivI* instr) {
   Register dividend = ToRegister32(instr->left());
   Register divisor = ToRegister32(instr->right());
   Register result = ToRegister32(instr->result());
@@ -3780,44 +3783,81 @@ void LCodeGen::DoMathFloor(LMathFloor* instr) {
 }
 
 
-void LCodeGen::DoMathFloorOfDiv(LMathFloorOfDiv* instr) {
-  Register result = ToRegister32(instr->result());
-  Register left = ToRegister32(instr->left());
-  Register right = ToRegister32(instr->right());
+void LCodeGen::DoFlooringDivByPowerOf2I(LFlooringDivByPowerOf2I* instr) {
+  Register dividend = ToRegister32(instr->dividend());
+  int32_t divisor = instr->divisor();
+  ASSERT(dividend.is(ToRegister32(instr->result())));
+
+  // If the divisor is positive, things are easy: There can be no deopts and we
+  // can simply do an arithmetic right shift.
+  if (divisor == 1) return;
+  int32_t shift = WhichPowerOf2Abs(divisor);
+  if (divisor > 1) {
+    __ Mov(dividend, Operand(dividend, ASR, shift));
+    return;
+  }
+
+  // If the divisor is negative, we have to negate and handle edge cases.
+  Label not_kmin_int, done;
+  __ Negs(dividend, dividend);
+  if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
+    DeoptimizeIf(eq, instr->environment());
+  }
+  if (instr->hydrogen()->left()->RangeCanInclude(kMinInt)) {
+    // Note that we could emit branch-free code, but that would need one more
+    // register.
+    __ B(vc, &not_kmin_int);
+    if (divisor == -1) {
+      Deoptimize(instr->environment());
+    } else {
+      __ Mov(dividend, kMinInt / divisor);
+      __ B(&done);
+    }
+  }
+  __ bind(&not_kmin_int);
+  __ Mov(dividend, Operand(dividend, ASR, shift));
+  __ bind(&done);
+}
+
+
+void LCodeGen::DoFlooringDivI(LFlooringDivI* instr) {
+  Register dividend = ToRegister32(instr->dividend());
+  Register divisor = ToRegister32(instr->divisor());
   Register remainder = ToRegister32(instr->temp());
+  Register result = ToRegister32(instr->result());
 
   // This can't cause an exception on ARM, so we can speculatively
   // execute it already now.
-  __ Sdiv(result, left, right);
+  __ Sdiv(result, dividend, divisor);
 
   // Check for x / 0.
-  DeoptimizeIfZero(right, instr->environment());
+  DeoptimizeIfZero(divisor, instr->environment());
 
   // Check for (kMinInt / -1).
   if (instr->hydrogen()->CheckFlag(HValue::kCanOverflow)) {
-    // The V flag will be set iff left == kMinInt.
-    __ Cmp(left, 1);
-    __ Ccmp(right, -1, NoFlag, vs);
+    // The V flag will be set iff dividend == kMinInt.
+    __ Cmp(dividend, 1);
+    __ Ccmp(divisor, -1, NoFlag, vs);
     DeoptimizeIf(eq, instr->environment());
   }
 
   // Check for (0 / -x) that will produce negative zero.
   if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
-    __ Cmp(right, 0);
-    __ Ccmp(left, 0, ZFlag, mi);
-    // "right" can't be null because the code would have already been
-    // deoptimized. The Z flag is set only if (right < 0) and (left == 0).
+    __ Cmp(divisor, 0);
+    __ Ccmp(dividend, 0, ZFlag, mi);
+    // "divisor" can't be null because the code would have already been
+    // deoptimized. The Z flag is set only if (divisor < 0) and (dividend == 0).
     // In this case we need to deoptimize to produce a -0.
     DeoptimizeIf(eq, instr->environment());
   }
 
   Label done;
   // If both operands have the same sign then we are done.
-  __ Eor(remainder, left, right);
+  __ Eor(remainder, dividend, divisor);
   __ Tbz(remainder, kWSignBit, &done);
 
   // Check if the result needs to be corrected.
-  __ Msub(remainder, result, right, left);
+  __ Msub(remainder, result, divisor, dividend);
   __ Cbz(remainder, &done);
   __ Sub(result, result, 1);
 
@@ -4006,58 +4046,64 @@ void LCodeGen::DoMathMinMax(LMathMinMax* instr) {
 }
 
 
-void LCodeGen::DoModI(LModI* instr) {
+void LCodeGen::DoModByPowerOf2I(LModByPowerOf2I* instr) {
+  Register dividend = ToRegister32(instr->dividend());
+  int32_t divisor = instr->divisor();
+  ASSERT(dividend.is(ToRegister32(instr->result())));
+
+  // Theoretically, a variation of the branch-free code for integer division by
+  // a power of 2 (calculating the remainder via an additional multiplication
+  // (which gets simplified to an 'and') and subtraction) should be faster, and
+  // this is exactly what GCC and clang emit. Nevertheless, benchmarks seem to
+  // indicate that positive dividends are heavily favored, so the branching
+  // version performs better.
   HMod* hmod = instr->hydrogen();
-  HValue* hleft = hmod->left();
-  HValue* hright = hmod->right();
+  int32_t mask = divisor < 0 ? -(divisor + 1) : (divisor - 1);
+  Label dividend_is_not_negative, done;
+  if (hmod->left()->CanBeNegative()) {
+    __ Cmp(dividend, 0);
+    __ B(pl, &dividend_is_not_negative);
+    // Note that this is correct even for kMinInt operands.
+    __ Neg(dividend, dividend);
+    __ And(dividend, dividend, Operand(mask));
+    __ Neg(dividend, dividend);
+    if (hmod->CheckFlag(HValue::kBailoutOnMinusZero)) {
+      DeoptimizeIf(eq, instr->environment());
+    }
+    __ B(&done);
+  }
 
-  Label done;
-  Register result = ToRegister32(instr->result());
+  __ bind(&dividend_is_not_negative);
+  __ And(dividend, dividend, Operand(mask));
+  __ bind(&done);
+}
+
+
+void LCodeGen::DoModI(LModI* instr) {
   Register dividend = ToRegister32(instr->left());
+  Register divisor = ToRegister32(instr->right());
+  Register result = ToRegister32(instr->result());
 
-  bool need_minus_zero_check = (hmod->CheckFlag(HValue::kBailoutOnMinusZero) &&
-                                hleft->CanBeNegative() && hmod->CanBeZero());
-
-  if (hmod->RightIsPowerOf2()) {
-    // Note: The code below even works when right contains kMinInt.
-    int32_t divisor = Abs(hright->GetInteger32Constant());
-
-    if (hleft->CanBeNegative()) {
-      __ Cmp(dividend, 0);
-      __ Cneg(result, dividend, mi);
-      __ And(result, result, divisor - 1);
-      __ Cneg(result, result, mi);
-      if (need_minus_zero_check) {
-        __ Cbnz(result, &done);
-        // The result is 0. Deoptimize if the dividend was negative.
-        DeoptimizeIf(mi, instr->environment());
-      }
+  Label deopt, done;
+  // modulo = dividend - quotient * divisor
+  __ Sdiv(result, dividend, divisor);
+  if (instr->hydrogen()->right()->CanBeZero()) {
+    // Combine the deoptimization sites.
+    Label ok;
+    __ Cbnz(divisor, &ok);
+    __ Bind(&deopt);
+    Deoptimize(instr->environment());
+    __ Bind(&ok);
+  }
+  __ Msub(result, result, divisor, dividend);
+  if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero) &&
+      instr->hydrogen()->left()->CanBeNegative() &&
+      instr->hydrogen()->CanBeZero()) {
+    __ Cbnz(result, &done);
+    if (deopt.is_bound()) {  // TODO(all) This is a hack, remove this...
+      __ Tbnz(dividend, kWSignBit, &deopt);
     } else {
-      __ And(result, dividend, divisor - 1);
-    }
-
-  } else {
-    Label deopt;
-    Register divisor = ToRegister32(instr->right());
-    // Compute:
-    //   modulo = dividend - quotient * divisor
-    __ Sdiv(result, dividend, divisor);
-    if (hright->CanBeZero()) {
-      // Combine the deoptimization sites.
-      Label ok;
-      __ Cbnz(divisor, &ok);
-      __ Bind(&deopt);
-      Deoptimize(instr->environment());
-      __ Bind(&ok);
-    }
-    __ Msub(result, result, divisor, dividend);
-    if (need_minus_zero_check) {
-      __ Cbnz(result, &done);
-      if (deopt.is_bound()) {
-        __ Tbnz(dividend, kWSignBit, &deopt);
-      } else {
-        DeoptimizeIfNegative(dividend, instr->environment());
-      }
+      DeoptimizeIfNegative(dividend, instr->environment());
     }
   }
   __ Bind(&done);