Closed Bug 999764 Opened 8 years ago Closed 8 years ago

Optimize floating-point division into multiplication when safe


(Core :: JavaScript Engine: JIT, enhancement)

Not set





(Reporter: sunfish, Assigned: sankha, Mentored)



(Whiteboard: [lang=c++][good first bug])


(2 files, 5 obsolete files)

Floating-point divisions by constants whose reciprocal can be exactly represented can be implemented by a multiplication by reciprocal rather than by a division. For example, this code:

define f(x) {
  return x / 16.0;

can be implemented by multiplying x by 0.0625, since the reciprocal of 16.0 is exactly representable.

According to Agner, divsd has a latency of 10-20 while mulsd has a latency of 5 (on Haswell; other micro-architectures are similar).

This is less important for OdinMonkey since Emscripten-produced code will already have this optimization applied to it.
Note that this may not be a good idea if the reciprocal is subnormal, because that may end up being slower.
Hi! Any guide to get started? I have no experiences on IonMonkey before.
Take a look at some of the implementations of the foldsTo virtual member function in MIR.cpp. They return a new node which is a suitable replacement for their "this", or "this" itself if they don't have a replacement. For this bug, when an MDiv has a suitable constant operand, we want to create an MMul to replace it.
Attached patch patchv1 (obsolete) — Splinter Review
Attachment #8424485 - Flags: feedback?(sunfish)
Comment on attachment 8424485 [details] [diff] [review]

Review of attachment 8424485 [details] [diff] [review]:

Overall looks good. Just a few comments:

::: js/src/jit/MIR.cpp
@@ +136,5 @@
>      return MConstant::New(alloc, ret);
>  }
> +static MMul *
> +EvaluateExactReciprocal(TempAllocator &alloc, MBinaryInstruction *ins)

Since this function only makes sense for division, the second argument here can be MDiv *.

@@ +153,5 @@
> +    int32_t num = rhs.toInt32();
> +
> +    // check if rhs is a power of two
> +    if (!(num > 0 && !(num & (num - 1))))
> +        return nullptr;

It would be nice to support negative values here too. The Abs in mfbt/MathAlgorithms.h can help generalize this to also accept a negated power of two.
Attachment #8424485 - Flags: feedback?(sunfish) → feedback+
Mentor: sunfish
Whiteboard: [mentor=sunfish][lang=c++][good first bug] → [lang=c++][good first bug]
Attached patch patchv2 (obsolete) — Splinter Review
I addressed the previous comments and ran this through the jit-test suite. There is one failure at asm.js/testBullet.js. Can you help?
Attachment #8424485 - Attachment is obsolete: true
Attachment #8447723 - Flags: feedback?(sunfish)
Comment on attachment 8447723 [details] [diff] [review]

The test is failing because GVN is asserting that the replacement value has the same type as the original value. Regular MMul::New defaults to MIRType_Value, but there's an overload which allows specifying an explicit type.

Thinking about types, you probably also need to add some checks to make sure that this optimization is only done when the types are floating-point.
Attachment #8447723 - Flags: feedback?(sunfish)
Attached patch patch v3 (obsolete) — Splinter Review
Assignee: nobody → sankha93
Attachment #8447723 - Attachment is obsolete: true
Attachment #8448717 - Flags: review?(sunfish)
Comment on attachment 8448717 [details] [diff] [review]
patch v3

Review of attachment 8448717 [details] [diff] [review]:

::: js/src/jit/MIR.cpp
@@ +147,5 @@
> +static MMul *
> +EvaluateExactReciprocal(TempAllocator &alloc, MDiv *ins)
> +{
> +    // we should fold only when it is a floating point operation
> +    if (ins->type() != MIRType_Double || ins->type() != MIRType_Float32)

This check can use the IsFloatingPointType predicate.
Attachment #8448717 - Flags: review?(sunfish) → review+
Attached patch patchv4 (obsolete) — Splinter Review
Attachment #8448717 - Attachment is obsolete: true
Attachment #8450924 - Flags: review+
I just tried a simple testcase:

function f(x) { return x / 4; }

(run with js --ion-eager --ion-offthread-compile=off) and the divide didn't get optimized.

It looks like the rhs.isInt32() check fails because rhs is double even though the actual value is integral. SpiderMonkey does have code for automatically setting the type of a value to int32, but apparently it isn't always used. Also, the power-of-two check is inverted. If I comment out both of these checks, the optimization does complete, though there's a bug.

GVN only adds the instruction that is returned from foldsTo to ins's basic block. Since the optimization also creates a new MConstant, you'll need to add it to ins's basic block manually. You can use insertBefore to insert it right before ins.
Keywords: checkin-needed
Attached patch patch v5 (obsolete) — Splinter Review
Attachment #8450924 - Attachment is obsolete: true
Attachment #8452393 - Flags: review?(sunfish)
This is the iongraph image for the GVN pass when f(3.3) took place. The instruction was folded to a Mul.
I just ran the latest patch through a quick jit-tests run, and asm.js/testFloat32.js failed. Can you investigate?
Blocks: 1036037
Attached patch patch v5Splinter Review
This patch passes all the tests. The previous failure was because the MConstant had the type double while the asm.js tests required float32. I now set the type of MConstant to the type of the original division instruction.
Attachment #8452393 - Attachment is obsolete: true
Attachment #8452393 - Flags: review?(sunfish)
Attachment #8452961 - Flags: review?(sunfish)
Comment on attachment 8452961 [details] [diff] [review]
patch v5

Review of attachment 8452961 [details] [diff] [review]:

Looks good, thanks for patiently seeing this through!
Attachment #8452961 - Flags: review?(sunfish) → review+
Closed: 8 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla33
You need to log in before you can comment on or make changes to this bug.