Subzero: Strength-reduce mul by certain constants.

Subzero: Strength-reduce mul by certain constants.

These all appear to some degree in spec2k.

This is implemented for i8/i16/i32 types.  It is done as part of core lowering, so in theory all optimization levels could benefit, but it is explicitly disabled for Om1/O0 to keep things simple there.

While clang appears to strength-reduce udiv/urem by a constant power of 2, for some reason it does not always strength-reduce multiplies (given that they appear in the spec2k bitcode).

For multiplies by 3, 5, or 9, we can make use of the lea instruction.  We can do combinations of shift and lea to multiply by other constants, e.g. 100=5*5*4.  If too many operations would be required, just give up and use the mul instruction.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4095
R=jpp@chromium.org, jvoung@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=0933c0cfb8183a662e44a61d8671b20987d12c78

[Jim Stichnoth, 2015-06-09 23:06:58]

stichnot@chromium.org changed reviewers:
+ jpp@chromium.org, jvoung@chromium.org, kschimpf@google.com,
mtrofin@chromium.org

[John, 2015-06-10 17:27:52]

lgtm

If my comment does not make sense, please ignore it... LGTM otherwise.

https://codereview.chromium.org/1146803002/diff/100001/src/IceTargetLoweringX...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/1146803002/diff/100001/src/IceTargetLoweringX...
src/IceTargetLoweringX8632.cpp:1314: if (Src1 <= 0)
Just throwing an idea... would it work to invert Src1 and then _inv(T) at the
end? Then this function would become something like

if (Src1 == 0) {
  _mov(T, Zero);
  _mov(Dest, Zero);
  return true;
}

const bool NegativeSrc1 = Src1 < 0;

if (NegativeSrc1) {
  Src1 = -Src1;
}

uint32_t Count9 = 0;
uint32_t Count5 = 0;
uint32_t Count3 = 0;
uint32_t Count2 = 0;
uint32_t CountOps = NegativeSrc1 ? 1 : 0;

while (Src1 > 1) {
   ...
}

const uint32_t MaxOpsForOptimizedMul = 5;
if (CountOps > MaxOpsForOptimizedMul) {
  return false;
}

_mov(T, Src0);
...
if (NegativeSrc1) {
  _inv(T);
}
_mov(Dest, T);
return true;

[jvoung (off chromium), 2015-06-10 18:12:28]

lgtm too -- would it be good to add a .ll test showing the optimization
triggering? (cross test could still pass without the optimization running)

https://codereview.chromium.org/1146803002/diff/100001/src/IceTargetLoweringX...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/1146803002/diff/100001/src/IceTargetLoweringX...
src/IceTargetLoweringX8632.cpp:1345: const uint32_t MaxOpsForOptimizedMul = 5;
FWIW, some of the agner tables say mul r/i is about 3 microops for 32-bit
(sometimes better for 8-bit, sometimes worse for 64-bit), so 5 might be high?
I'm not sure how many ops LLVM/gcc will go up to.

Anyway, could tune more later.

[John, 2015-06-10 23:47:19]

lgtm

Still LGTM.

https://codereview.chromium.org/1146803002/diff/100001/src/IceTargetLoweringX...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/1146803002/diff/100001/src/IceTargetLoweringX...
src/IceTargetLoweringX8632.cpp:1345: const uint32_t MaxOpsForOptimizedMul = 5;
On 2015/06/10 18:12:27, jvoung wrote:
> FWIW, some of the agner tables say mul r/i is about 3 microops for 32-bit
> (sometimes better for 8-bit, sometimes worse for 64-bit), so 5 might be high?
> I'm not sure how many ops LLVM/gcc will go up to.
> 
> Anyway, could tune more later.

This little command

echo "int v(int i) { return i * 25; }"|gcc -S -O99 -x c - -o-|less

showed me a couple of interesting things. It seems gcc will not go over 2
instructions (and maybe a neg at the end for negative numbers.)

[Jim Stichnoth, 2015-06-12 17:31:47]

https://codereview.chromium.org/1146803002/diff/100001/src/IceTargetLoweringX...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/1146803002/diff/100001/src/IceTargetLoweringX...
src/IceTargetLoweringX8632.cpp:1314: if (Src1 <= 0)
On 2015/06/10 17:27:52, John wrote:
> Just throwing an idea... would it work to invert Src1 and then _inv(T) at the
> end? Then this function would become something like
> 
> if (Src1 == 0) {
>   _mov(T, Zero);
>   _mov(Dest, Zero);
>   return true;
> }
> 
> const bool NegativeSrc1 = Src1 < 0;
> 
> if (NegativeSrc1) {
>   Src1 = -Src1;
> }
> 
> uint32_t Count9 = 0;
> uint32_t Count5 = 0;
> uint32_t Count3 = 0;
> uint32_t Count2 = 0;
> uint32_t CountOps = NegativeSrc1 ? 1 : 0;
> 
> while (Src1 > 1) {
>    ...
> }
> 
> const uint32_t MaxOpsForOptimizedMul = 5;
> if (CountOps > MaxOpsForOptimizedMul) {
>   return false;
> }
> 
> _mov(T, Src0);
> ...
> if (NegativeSrc1) {
>   _inv(T);
> }
> _mov(Dest, T);
> return true;

Done.  Though I suppress that when the constant is MININT.

https://codereview.chromium.org/1146803002/diff/100001/src/IceTargetLoweringX...
src/IceTargetLoweringX8632.cpp:1345: const uint32_t MaxOpsForOptimizedMul = 5;
On 2015/06/10 18:12:27, jvoung wrote:
> FWIW, some of the agner tables say mul r/i is about 3 microops for 32-bit
> (sometimes better for 8-bit, sometimes worse for 64-bit), so 5 might be high?
> I'm not sure how many ops LLVM/gcc will go up to.
> 
> Anyway, could tune more later.

OK.  I reduced the threshold to 3.

[Jim Stichnoth, 2015-06-12 17:41:21]

Committed patchset #8 (id:140001) manually as
0933c0cfb8183a662e44a61d8671b20987d12c78 (presubmit successful).