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

src/ia32/lithium-codegen-ia32.cc

 // Copyright 2012 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 1350 matching lines @@
       UNREACHABLE();
   }
 }
 
 
 void LCodeGen::DoUnknownOSRValue(LUnknownOSRValue* instr) {
   GenerateOsrPrologue();
 }
 
 
+void LCodeGen::DoModByPowerOf2I(LModByPowerOf2I* instr) {
+  Register dividend = ToRegister(instr->dividend());
+  int32_t divisor = instr->divisor();
+  ASSERT(dividend.is(ToRegister(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()) {
+    __ test(dividend, dividend);
+    __ j(not_sign, &dividend_is_not_negative, Label::kNear);
+    // Note that this is correct even for kMinInt operands.
+    __ neg(dividend);
+    __ and_(dividend, mask);
+    __ neg(dividend);
+    if (hmod->CheckFlag(HValue::kBailoutOnMinusZero)) {
+      DeoptimizeIf(zero, instr->environment());
+    }
+    __ jmp(&done, Label::kNear);
+  }
+
+  __ bind(&dividend_is_not_negative);
+  __ and_(dividend, mask);
+  __ bind(&done);
+}
+
+
 void LCodeGen::DoModI(LModI* instr) {
   HMod* hmod = instr->hydrogen();
   HValue* left = hmod->left();
   HValue* right = hmod->right();
-  if (hmod->RightIsPowerOf2()) {
-    // TODO(svenpanne) We should really do the strength reduction on the
-    // Hydrogen level.
-    Register left_reg = ToRegister(instr->left());
-    ASSERT(left_reg.is(ToRegister(instr->result())));
-
-    // Note: The code below even works when right contains kMinInt.
-    int32_t divisor = Abs(right->GetInteger32Constant());
-
-    Label left_is_not_negative, done;
-    if (left->CanBeNegative()) {
-      __ test(left_reg, Operand(left_reg));
-      __ j(not_sign, &left_is_not_negative, Label::kNear);
-      __ neg(left_reg);
-      __ and_(left_reg, divisor - 1);
-      __ neg(left_reg);
-      if (hmod->CheckFlag(HValue::kBailoutOnMinusZero)) {
-        DeoptimizeIf(zero, instr->environment());
-      }
+
+  Register left_reg = ToRegister(instr->left());
+  ASSERT(left_reg.is(eax));
+  Register right_reg = ToRegister(instr->right());
+  ASSERT(!right_reg.is(eax));
+  ASSERT(!right_reg.is(edx));
+  Register result_reg = ToRegister(instr->result());
+  ASSERT(result_reg.is(edx));
+
+  Label done;
+  // Check for x % 0, idiv would signal a divide error. We have to
+  // deopt in this case because we can't return a NaN.
+  if (right->CanBeZero()) {
+    __ test(right_reg, Operand(right_reg));
+    DeoptimizeIf(zero, instr->environment());
+  }
+
+  // Check for kMinInt % -1, idiv would signal a divide error. We
+  // have to deopt if we care about -0, because we can't return that.
+  if (left->RangeCanInclude(kMinInt) && right->RangeCanInclude(-1)) {
+    Label no_overflow_possible;
+    __ cmp(left_reg, kMinInt);
+    __ j(not_equal, &no_overflow_possible, Label::kNear);
+    __ cmp(right_reg, -1);
+    if (hmod->CheckFlag(HValue::kBailoutOnMinusZero)) {
+      DeoptimizeIf(equal, instr->environment());
+    } else {
+      __ j(not_equal, &no_overflow_possible, Label::kNear);
+      __ Set(result_reg, Immediate(0));
       __ jmp(&done, Label::kNear);
     }
-
-    __ bind(&left_is_not_negative);
-    __ and_(left_reg, divisor - 1);
-    __ bind(&done);
-  } else {
-    Register left_reg = ToRegister(instr->left());
-    ASSERT(left_reg.is(eax));
-    Register right_reg = ToRegister(instr->right());
-    ASSERT(!right_reg.is(eax));
-    ASSERT(!right_reg.is(edx));
-    Register result_reg = ToRegister(instr->result());
-    ASSERT(result_reg.is(edx));
-
-    Label done;
-    // Check for x % 0, idiv would signal a divide error. We have to
-    // deopt in this case because we can't return a NaN.
-    if (right->CanBeZero()) {
-      __ test(right_reg, Operand(right_reg));
-      DeoptimizeIf(zero, instr->environment());
-    }
-
-    // Check for kMinInt % -1, idiv would signal a divide error. We
-    // have to deopt if we care about -0, because we can't return that.
-    if (left->RangeCanInclude(kMinInt) && right->RangeCanInclude(-1)) {
-      Label no_overflow_possible;
-      __ cmp(left_reg, kMinInt);
-      __ j(not_equal, &no_overflow_possible, Label::kNear);
-      __ cmp(right_reg, -1);
-      if (hmod->CheckFlag(HValue::kBailoutOnMinusZero)) {
-        DeoptimizeIf(equal, instr->environment());
-      } else {
-        __ j(not_equal, &no_overflow_possible, Label::kNear);
-        __ Set(result_reg, Immediate(0));
-        __ jmp(&done, Label::kNear);
-      }
-      __ bind(&no_overflow_possible);
-    }
-
-    // Sign extend dividend in eax into edx:eax.
-    __ cdq();
-
-    // If we care about -0, test if the dividend is <0 and the result is 0.
-    if (left->CanBeNegative() &&
-        hmod->CanBeZero() &&
-        hmod->CheckFlag(HValue::kBailoutOnMinusZero)) {
-      Label positive_left;
-      __ test(left_reg, Operand(left_reg));
-      __ j(not_sign, &positive_left, Label::kNear);
-      __ idiv(right_reg);
-      __ test(result_reg, Operand(result_reg));
-      DeoptimizeIf(zero, instr->environment());
-      __ jmp(&done, Label::kNear);
-      __ bind(&positive_left);
-    }
+    __ bind(&no_overflow_possible);
+  }
+
+  // Sign extend dividend in eax into edx:eax.
+  __ cdq();
+
+  // If we care about -0, test if the dividend is <0 and the result is 0.
+  if (left->CanBeNegative() &&
+      hmod->CanBeZero() &&
+      hmod->CheckFlag(HValue::kBailoutOnMinusZero)) {
+    Label positive_left;
+    __ test(left_reg, Operand(left_reg));
+    __ j(not_sign, &positive_left, Label::kNear);
     __ idiv(right_reg);
-    __ bind(&done);
-  }
+    __ test(result_reg, Operand(result_reg));
+    DeoptimizeIf(zero, instr->environment());
+    __ jmp(&done, Label::kNear);
+    __ bind(&positive_left);
+  }
+  __ idiv(right_reg);
+  __ bind(&done);
+}
+
+
+void LCodeGen::DoDivByPowerOf2I(LDivByPowerOf2I* instr) {
+  Register dividend = ToRegister(instr->dividend());
+  int32_t divisor = instr->divisor();
+  Register result = ToRegister(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) {
+    __ test(dividend, dividend);
+    DeoptimizeIf(zero, instr->environment());
+  }
+  // Check for (kMinInt / -1).
+  if (hdiv->CheckFlag(HValue::kCanOverflow) &&
+      hdiv->left()->RangeCanInclude(kMinInt) && divisor == -1) {
+    __ cmp(dividend, kMinInt);
+    DeoptimizeIf(zero, 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);
+    __ test(dividend, Immediate(mask));
+    DeoptimizeIf(not_zero, instr->environment());
+  }
+  __ Move(result, dividend);
+  int32_t shift = WhichPowerOf2Abs(divisor);
+  if (shift > 0) {
+    // The arithmetic shift is always OK, the 'if' is an optimization only.
+    if (shift > 1) __ sar(result, 31);
+    __ shr(result, 32 - shift);
+    __ add(result, dividend);
+    __ sar(result, shift);
+  }
+  if (divisor < 0) __ neg(result);
 }
 
 
 void LCodeGen::DoDivI(LDivI* instr) {
-  if (!instr->is_flooring() && instr->hydrogen()->RightIsPowerOf2()) {
-    Register dividend = ToRegister(instr->left());
-    HDiv* hdiv = instr->hydrogen();
-    int32_t divisor = hdiv->right()->GetInteger32Constant();
-    Register result = ToRegister(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)) {
-      __ test(dividend, Operand(dividend));
-      DeoptimizeIf(zero, instr->environment());
-    }
-    // Check for (kMinInt / -1).
-    if (hdiv->left()->RangeCanInclude(kMinInt) && divisor == -1 &&
-        hdiv->CheckFlag(HValue::kCanOverflow)) {
-      __ cmp(dividend, kMinInt);
-      DeoptimizeIf(zero, instr->environment());
-    }
-    // Deoptimize if remainder will not be 0.
-    if (!hdiv->CheckFlag(HInstruction::kAllUsesTruncatingToInt32) &&
-        Abs(divisor) != 1) {
-        __ test(dividend, Immediate(Abs(divisor) - 1));
-        DeoptimizeIf(not_zero, instr->environment());
-    }
-    __ Move(result, dividend);
-    int32_t shift = WhichPowerOf2(Abs(divisor));
-    if (shift > 0) {
-      // The arithmetic shift is always OK, the 'if' is an optimization only.
-      if (shift > 1) __ sar(result, 31);
-      __ shr(result, 32 - shift);
-      __ add(result, dividend);
-      __ sar(result, shift);
-    }
-    if (divisor < 0) __ neg(result);
-    return;
-  }
-
-  LOperand* right = instr->right();
-  ASSERT(ToRegister(instr->result()).is(eax));
-  ASSERT(ToRegister(instr->left()).is(eax));
-  ASSERT(!ToRegister(instr->right()).is(eax));
-  ASSERT(!ToRegister(instr->right()).is(edx));
-
-  Register left_reg = eax;
+  Register dividend = ToRegister(instr->left());
+  Register divisor = ToRegister(instr->right());
+  Register remainder = ToRegister(instr->temp());
+  Register result = ToRegister(instr->result());
+  ASSERT(dividend.is(eax));
+  ASSERT(remainder.is(edx));
+  ASSERT(result.is(eax));
+  ASSERT(!divisor.is(eax));
+  ASSERT(!divisor.is(edx));
 
   // Check for x / 0.
-  Register right_reg = ToRegister(right);
-  if (instr->hydrogen_value()->CheckFlag(HValue::kCanBeDivByZero)) {
-    __ test(right_reg, ToOperand(right));
+  HBinaryOperation* hdiv = instr->hydrogen();
+  if (hdiv->CheckFlag(HValue::kCanBeDivByZero)) {
+    __ test(divisor, divisor);
     DeoptimizeIf(zero, instr->environment());
   }
 
   // Check for (0 / -x) that will produce negative zero.
-  if (instr->hydrogen_value()->CheckFlag(HValue::kBailoutOnMinusZero)) {
-    Label left_not_zero;
-    __ test(left_reg, Operand(left_reg));
-    __ j(not_zero, &left_not_zero, Label::kNear);
-    __ test(right_reg, ToOperand(right));
+  if (hdiv->CheckFlag(HValue::kBailoutOnMinusZero)) {
+    Label dividend_not_zero;
+    __ test(dividend, dividend);
+    __ j(not_zero, &dividend_not_zero, Label::kNear);
+    __ test(divisor, divisor);
     DeoptimizeIf(sign, instr->environment());
-    __ bind(&left_not_zero);
+    __ bind(&dividend_not_zero);
   }
 
   // Check for (kMinInt / -1).
-  if (instr->hydrogen_value()->CheckFlag(HValue::kCanOverflow)) {
-    Label left_not_min_int;
-    __ cmp(left_reg, kMinInt);
-    __ j(not_zero, &left_not_min_int, Label::kNear);
-    __ cmp(right_reg, -1);
-    DeoptimizeIf(zero, instr->environment());
-    __ bind(&left_not_min_int);
-  }
-
-  // Sign extend to edx.
+  if (hdiv->CheckFlag(HValue::kCanOverflow)) {
+    Label dividend_not_min_int;
+    __ cmp(dividend, kMinInt);
+    __ j(not_zero, &dividend_not_min_int, Label::kNear);
+    __ cmp(divisor, -1);
+    DeoptimizeIf(zero, instr->environment());
+    __ bind(&dividend_not_min_int);
+  }
+
+  // Sign extend to edx (= remainder).
   __ cdq();
-  __ idiv(right_reg);
+  __ idiv(divisor);
 
   if (instr->is_flooring()) {
     Label done;
-    __ test(edx, edx);
+    __ test(remainder, remainder);
     __ j(zero, &done, Label::kNear);
-    __ xor_(edx, right_reg);
-    __ sar(edx, 31);
-    __ add(eax, edx);
+    __ xor_(remainder, divisor);
+    __ sar(remainder, 31);
+    __ add(result, remainder);
     __ bind(&done);
   } else if (!instr->hydrogen()->CheckFlag(
       HInstruction::kAllUsesTruncatingToInt32)) {
     // Deoptimize if remainder is not 0.
-    __ test(edx, Operand(edx));
+    __ test(remainder, remainder);
     DeoptimizeIf(not_zero, instr->environment());
   }
 }
 
 
-void LCodeGen::DoMathFloorOfDiv(LMathFloorOfDiv* instr) {
-  ASSERT(instr->right()->IsConstantOperand());
-
-  Register dividend = ToRegister(instr->left());
-  int32_t divisor = ToInteger32(LConstantOperand::cast(instr->right()));
-  Register result = ToRegister(instr->result());
-
-  switch (divisor) {
-  case 0:
+void LCodeGen::DoFlooringDivByPowerOf2I(LFlooringDivByPowerOf2I* instr) {
+  Register dividend = ToRegister(instr->dividend());
+  int32_t divisor = instr->divisor();
+  ASSERT(dividend.is(ToRegister(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) {
+    __ sar(dividend, shift);
+    return;
+  }
+
+  // If the divisor is negative, we have to negate and handle edge cases.
+  Label not_kmin_int, done;
+  __ neg(dividend);
+  if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
+    DeoptimizeIf(zero, instr->environment());
+  }
+  if (instr->hydrogen()->left()->RangeCanInclude(kMinInt)) {
+    // Note that we could emit branch-free code, but that would need one more
+    // register.
+    __ j(no_overflow, &not_kmin_int, Label::kNear);
+    if (divisor == -1) {
+      DeoptimizeIf(no_condition, instr->environment());
+    } else {
+      __ mov(dividend, Immediate(kMinInt / divisor));
+      __ jmp(&done, Label::kNear);
+    }
+  }
+  __ bind(&not_kmin_int);
+  __ sar(dividend, shift);
+  __ bind(&done);
+}
+
+
+void LCodeGen::DoFlooringDivByConstI(LFlooringDivByConstI* instr) {
+  Register dividend = ToRegister(instr->dividend());
+  int32_t divisor = instr->divisor();
+  Register scratch = ToRegister(instr->temp());
+  ASSERT(ToRegister(instr->dividend()).is(eax));
+  ASSERT(ToRegister(instr->result()).is(edx));
+
+  if (divisor == 0) {
     DeoptimizeIf(no_condition, instr->environment());
     return;
-
-  case 1:
-    __ Move(result, dividend);
-    return;
-
-  case -1:
-    __ Move(result, dividend);
-    __ neg(result);
-    if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
-      DeoptimizeIf(zero, instr->environment());
-    }
-    if (instr->hydrogen()->CheckFlag(HValue::kCanOverflow)) {
-      DeoptimizeIf(overflow, instr->environment());
-    }
-    return;
-  }
-
+  }
+
+  // Find b which: 2^b < divisor_abs < 2^(b+1).
   uint32_t divisor_abs = abs(divisor);
-  if (IsPowerOf2(divisor_abs)) {
-    int32_t power = WhichPowerOf2(divisor_abs);
-    if (divisor < 0) {
-      // Input[dividend] is clobbered.
-      // The sequence is tedious because neg(dividend) might overflow.
-      __ mov(result, dividend);
-      __ sar(dividend, 31);
-      __ neg(result);
-      if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
-        DeoptimizeIf(zero, instr->environment());
-      }
-      __ shl(dividend, 32 - power);
-      __ sar(result, power);
-      __ not_(dividend);
-      // Clear result.sign if dividend.sign is set.
-      __ and_(result, dividend);
-    } else {
-      __ Move(result, dividend);
-      __ sar(result, power);
-    }
+  unsigned b = 31 - CompilerIntrinsics::CountLeadingZeros(divisor_abs);
+  unsigned shift = 32 + b;  // Precision +1bit (effectively).
+  double multiplier_f =
+      static_cast<double>(static_cast<uint64_t>(1) << shift) / divisor_abs;
+  int64_t multiplier;
+  if (multiplier_f - std::floor(multiplier_f) < 0.5) {
+    multiplier = static_cast<int64_t>(std::floor(multiplier_f));
   } else {
-    ASSERT(ToRegister(instr->left()).is(eax));
-    ASSERT(ToRegister(instr->result()).is(edx));
-    Register scratch = ToRegister(instr->temp());
-
-    // Find b which: 2^b < divisor_abs < 2^(b+1).
-    unsigned b = 31 - CompilerIntrinsics::CountLeadingZeros(divisor_abs);
-    unsigned shift = 32 + b;  // Precision +1bit (effectively).
-    double multiplier_f =
-        static_cast<double>(static_cast<uint64_t>(1) << shift) / divisor_abs;
-    int64_t multiplier;
-    if (multiplier_f - std::floor(multiplier_f) < 0.5) {
-        multiplier = static_cast<int64_t>(std::floor(multiplier_f));
-    } else {
-        multiplier = static_cast<int64_t>(std::floor(multiplier_f)) + 1;
-    }
-    // The multiplier is a uint32.
-    ASSERT(multiplier > 0 &&
-           multiplier < (static_cast<int64_t>(1) << 32));
-    __ mov(scratch, dividend);
-    if (divisor < 0 &&
-        instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
-      __ test(dividend, dividend);
-      DeoptimizeIf(zero, instr->environment());
-    }
-    __ mov(edx, static_cast<int32_t>(multiplier));
-    __ imul(edx);
-    if (static_cast<int32_t>(multiplier) < 0) {
-      __ add(edx, scratch);
-    }
-    Register reg_lo = eax;
-    Register reg_byte_scratch = scratch;
-    if (!reg_byte_scratch.is_byte_register()) {
-        __ xchg(reg_lo, reg_byte_scratch);
-        reg_lo = scratch;
-        reg_byte_scratch = eax;
-    }
-    if (divisor < 0) {
-      __ xor_(reg_byte_scratch, reg_byte_scratch);
-      __ cmp(reg_lo, 0x40000000);
-      __ setcc(above, reg_byte_scratch);
-      __ neg(edx);
-      __ sub(edx, reg_byte_scratch);
-    } else {
-      __ xor_(reg_byte_scratch, reg_byte_scratch);
-      __ cmp(reg_lo, 0xC0000000);
-      __ setcc(above_equal, reg_byte_scratch);
-      __ add(edx, reg_byte_scratch);
-    }
-    __ sar(edx, shift - 32);
-  }
-}
-
-
+    multiplier = static_cast<int64_t>(std::floor(multiplier_f)) + 1;
+  }
+  // The multiplier is a uint32.
+  ASSERT(multiplier > 0 &&
+         multiplier < (static_cast<int64_t>(1) << 32));
+  __ mov(scratch, dividend);
+  if (divisor < 0 &&
+      instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
+    __ test(dividend, dividend);
+    DeoptimizeIf(zero, instr->environment());
+  }
+  __ mov(edx, static_cast<int32_t>(multiplier));
+  __ imul(edx);
+  if (static_cast<int32_t>(multiplier) < 0) {
+    __ add(edx, scratch);
+  }
+  Register reg_lo = eax;
+  Register reg_byte_scratch = scratch;
+  if (!reg_byte_scratch.is_byte_register()) {
+    __ xchg(reg_lo, reg_byte_scratch);
+    reg_lo = scratch;
+    reg_byte_scratch = eax;
+  }
+  if (divisor < 0) {
+    __ xor_(reg_byte_scratch, reg_byte_scratch);
+    __ cmp(reg_lo, 0x40000000);
+    __ setcc(above, reg_byte_scratch);
+    __ neg(edx);
+    __ sub(edx, reg_byte_scratch);
+  } else {
+    __ xor_(reg_byte_scratch, reg_byte_scratch);
+    __ cmp(reg_lo, 0xC0000000);
+    __ setcc(above_equal, reg_byte_scratch);
+    __ add(edx, reg_byte_scratch);
+  }
+  __ sar(edx, shift - 32);
+}
+
+
 void LCodeGen::DoMulI(LMulI* instr) {
   Register left = ToRegister(instr->left());
   LOperand* right = instr->right();
 
   if (instr->hydrogen()->CheckFlag(HValue::kBailoutOnMinusZero)) {
     __ mov(ToRegister(instr->temp()), left);
   }
 
   if (right->IsConstantOperand()) {
     // Try strength reductions on the multiplication.
@@ skipping 4619 matching lines @@
                               FixedArray::kHeaderSize - kPointerSize));
   __ bind(&done);
 }
 
 
 #undef __
 
 } }  // namespace v8::internal
 
 #endif  // V8_TARGET_ARCH_IA32