Binaryen: [Proposal] Optimization for i64/u64 division by constant

[MaxGraey]

Usually VM great optimize division by constant for i32/u32 types replacing it on two operations: wide multiplication and right shift. But for i64/u64 division by constant this tweak not supported unfortunately.

I propose generate some helping routines for that kind of optimization during special opt pass in binaryen. For example if we divide u64 by 10 we can generate special multiplier and shift like in this answer (but this not optimal algorithm) during compile time and replace dividend / 10 to mulh(dividend, mul_inv_precompute) >> shift_precompute

where __mulh__ is:

function umulh64(u: u64, v: u64): u64 {
  var u0 = u & 0xFFFFFFFF;
  var v0 = v & 0xFFFFFFFF;

  var u1 = u >> 32;
  var v1 = v >> 32;

  var l = u0 * v0;
  var t = u1 * v0 + (l >> 32);
  var w = u0 * v1 + (t & 0xFFFFFFFF);

  t >>= 32;
  w >>= 32;

  return u1 * v1 + t + w;
}

In my dirty tests this approach faster 3x-4x times then usual division:
https://webassembly.studio/?f=0c23c6gc34bn

Results for loop 1e8 times:

division by uint64 constant 1e10 (mulh/shift): 240ms
division by uint64 constant 1e10 (normal):     843ms

[kripken]

Interesting, I thought VMs would be doing this kind of thing. I see this on firefox (on a slow machine):

division by uint64 constant 1e10 (mulh/shift): 2268ms
division by uint64 constant 1e10 (normal): 1260ms

which looks like the opposite of your results.

cc @sunfishcode - should VMs or binaryen do this, in your opinion?

[kripken]

(In my opinion it would be great if VMs did it - because it lets us ship smaller wasm binaries.)

[MaxGraey]

Hmm, the best way if this doing by VM of course, especially if machine support mulq/umulh instructions. But current LLVM/VM (jit) in some reason don't do this for u64/i64 and doing this only for u32/i32.

Interesting, I thought VMs would be doing this kind of thing. I see this on firefox

Hmm, interesting. May be you have older cpu architecture than me where multiplication is not so cheap

PS I have Intel x64 Crystal Well family chip

@sunfishcode WDYT? I know crettone optimize this case even for u64/i64 but seems latest Chrome and Firefox don't manage this currently

[sunfishcode]

I don't think there's an exclusively right answer here, but the trends seem to be favoring calling this the VM's job. As @kripken mentions, relying on the VM to do it saves wasm code size. And, it seems most VMs are already doing this for 32-bit, so it's not unreasonable to expect them to eventually do it for 64-bit too.

[jgravelle-google]

May be you have older cpu architecture than me where multiplication is not so cheap

To me this says even more strongly that this is the VM's job. (In theory) the VM can know what CPU the code is running on, and if this optimization makes sense. Even if not all the VMs are implementing this today, we should ship maximally optimizable code for the future. I'd hate to be in a position where the VMs pattern-match on this in order to undo it back into a division on some architectures, for example.

For what it's worth, running the webassembly.studio project in Chrome 67 on my machine gives me:

division by uint64 constant 1e10 (mulh/shift): 279.611328125ms
division by uint64 constant 1e10 (normal): 934.128173828125ms

And Firefox Nightly (62):

division by uint64 constant 1e10 (mulh/shift): 366ms
division by uint64 constant 1e10 (normal): 1094ms

[MaxGraey]

3x+ times speedup for only polyfilled umul so we can definitely expect significant boost when using builtin instructions like mulq or imulh/umulh if arch support it.

Since we are determined that this is in part of VM I'm closing this issue.