Integer division when operands and target are integers

[Evan Wallace]

I've been trying to optimize image manipulation and I couldn't get V8 to emit integer division instructions. Does V8 currently emit any integer division instructions? It seems odd that it wouldn't because it does have the capability to emit them (see LDivI). I was going to submit a bug but wanted to check first that this really is the case.

When using typed arrays, division causes lots of conversions to and from doubles. Since V8 does range analysis, it should be possible to emit integer division for at least the case with non-negative dividends and positive divisors when the target location is an integer. I hacked up a quick proof of concept yesterday and got an easy 2x speedup (for converting a premultiplied alpha image to non-premultiplied alpha). This puts V8 at the speed of optimized C code and seems like too good an optimization to pass up. This optimization would also be useful for tools like emscripten.

function undoPremultiplication(image, w, h) {

  for (var y = 0, i = 0; y < h; y++) {

    for (var x = 0; x < w; x++, i += 4) {

      var alpha = image[i + 3];

      if (alpha > 0) {

        image[i + 0] = image[i + 0] * 0xFF / alpha;

        image[i + 1] = image[i + 1] * 0xFF / alpha;

        image[i + 2] = image[i + 2] * 0xFF / alpha;

      }

    }

  }

}

[Vyacheslav Egorov]

Once type-feedback told hydrogen that division happened to produce
double value it does not try to revert it to integer division.

The only exception is (quite fragile) MathFloorOfDiv optimization
performed by HUnaryMathOperation::Canonicalize.

Consider contributing your patch :-)

--
Vyacheslav Egorov

> --
> v8-users mailing list
> v8-u...@googlegroups.com
> http://groups.google.com/group/v8-users

[Daniel Clifford]

As your examples suggests, this could happen frequently in Canvas pixel manipulation. Please do file a bug so we can track it.

Danno

[Evan Wallace]

Oh ok, that makes sense. So V8 generates an integer instruction only if the remainder is always zero. I've submitted this as issue 2258.

I'm more than happy to contribute my patch but I'm new to V8 and my quick hack probably isn't the correct way to do it. It looks like instruction replacement should take place in the canonicalize pass but range information isn't available until range analysis. I did the optimization during range analysis both to make sure the preconditions hold (non-negative dividend and positive divisor) and to make sure the correct range is calculated for subsequent instructions. Would a patch that adds and removes instructions during range analysis be accepted?

[Vyacheslav Egorov]

It does not have to be in Canonicalization pass (not every
optimization that replaces instructions fits into it).

I am not entirely sure that it makes perfect sense to perform such
optimization during range analysis itself though I do see at least one
reason why you would want to do that: our conditional range
propagation does not associate range information with uses, so [alpha
> 0] information becomes lost after range analysis. This can be worked
around by attaching more information to HUseListNode* during range
analysis.

Honestly speaking it's hard to speculate if some patch would be
accepted or not without actually seeing a patch.

--
Vyacheslav Egorov

[Evan Wallace]

Sorry I didn't mean accepted, just wanted to see if I was on the right track! Thank you very much for your help. I'm not sure how important correct range information for the result of the division is, but it seems like the only way to have the range information correctly calculated in this case would be to have the optimization performed during range analysis. I have uploaded my change at https://chromiumcodereview.appspot.com/10825071. I wasn't sure how to test for the optimization itself since I didn't find any other tests that did that, but I did add a test for correctness. Would either of you be willing to review my change?