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

src/a64/lithium-codegen-a64.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 2546 matching lines @@
   // the special case below.
   if (info()->IsStub() && (type == Deoptimizer::EAGER)) {
     type = Deoptimizer::LAZY;
   }
 
   Comment(";;; deoptimize: %s", instr->hydrogen()->reason());
   Deoptimize(instr->environment(), &type);
 }
 
 
+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.
+  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) {
-  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));
-
-    // 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);
-    return;
-  }
-
   Register dividend = ToRegister32(instr->left());
   Register divisor = ToRegister32(instr->right());
   Register result = ToRegister32(instr->result());
   HValue* hdiv = instr->hydrogen_value();
 
   // Issue the division first, and then check for any deopt cases whilst the
   // result is computed.
   __ Sdiv(result, dividend, divisor);
 
   if (hdiv->CheckFlag(HInstruction::kAllUsesTruncatingToInt32)) {
@@ skipping 1152 matching lines @@
   __ Fccmp(input, input, NoFlag, eq);
   __ B(&done, eq);
 
   __ Bind(&deopt);
   Deoptimize(instr->environment());
 
   __ Bind(&done);
 }
 
 
-void LCodeGen::DoMathFloorOfDiv(LMathFloorOfDiv* instr) {
+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());
-  Register left = ToRegister32(instr->left());
-  Register right = ToRegister32(instr->right());
-  Register remainder = ToRegister32(instr->temp());
 
   // 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);
 
   __ Bind(&done);
 }
 
 
 void LCodeGen::DoMathLog(LMathLog* instr) {
   ASSERT(instr->IsMarkedAsCall());
   ASSERT(ToDoubleRegister(instr->value()).is(d0));
@@ skipping 168 matching lines @@
     if (op == HMathMinMax::kMathMax) {
       __ Fmax(result, left, right);
     } else {
       ASSERT(op == HMathMinMax::kMathMin);
       __ Fmin(result, left, right);
     }
   }
 }
 
 
+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();
+  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);
+  }
+
+  __ bind(&dividend_is_not_negative);
+  __ And(dividend, dividend, Operand(mask));
+  __ bind(&done);
+}
+
+
 void LCodeGen::DoModI(LModI* instr) {
-  HMod* hmod = instr->hydrogen();
-  HValue* hleft = hmod->left();
-  HValue* hright = hmod->right();
+  Register dividend = ToRegister32(instr->left());
+  Register divisor = ToRegister32(instr->right());
+  Register result = ToRegister32(instr->result());
 
-  Label done;
-  Register result = ToRegister32(instr->result());
-  Register dividend = ToRegister32(instr->left());
-
-  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);
 }
 
 
 void LCodeGen::DoMulConstIS(LMulConstIS* instr) {
   ASSERT(instr->hydrogen()->representation().IsSmiOrInteger32());
   bool is_smi = instr->hydrogen()->representation().IsSmi();
   Register result =
@@ skipping 1595 matching lines @@
   __ Bind(&out_of_object);
   __ Ldr(result, FieldMemOperand(object, JSObject::kPropertiesOffset));
   // Index is equal to negated out of object property index plus 1.
   __ Sub(result, result, Operand::UntagSmiAndScale(index, kPointerSizeLog2));
   __ Ldr(result, FieldMemOperand(result,
                                  FixedArray::kHeaderSize - kPointerSize));
   __ Bind(&done);
 }
 
 } }  // namespace v8::internal