[instcombine, sha] Add Instruction Fold for Masked Merge

[llvmbot]

Bugzilla Link	6773
Version	trunk
OS	Linux
Blocks	llvm/llvm-bugzilla-archive#49930
Reporter	LLVM Bugzilla Contributor
CC	@asl,@d0k,@lattner,@topperc,@efriedma-quic,@LebedevRI,@RKSimon,@sunfishcode,@nlewycky,@rotateright
Fixed by commit(s)	333106

Extended Description

When experimenting with SHA, I was pleased to notice that LLVM will fold the "Maj" function (x & y) ^ (x & z) ^ (y & z) down to ((z ^ y) & x) ^ (y & z).

The "Ch" function, though, doesn't fold. (x & y) | (~x & z) should become ((y ^ z) & x) ^ z, as mentioned on http://graphics.stanford.edu/~seander/bithacks.html#MaskedMerge (as should (x & y) ^ (~x & z), the version used in the SHA standard).

(If you're wondering at the similarity, Maj(x,y,z) is equivalent to Ch(x, y|z, y&z). Using that implementation with the optimized Ch again gives optimal code from LLVM as it knows to fold (y|z)^(y&z) down to y^z.)

LLVM IR from Bitter Melon:

define i32 @Ch(i32 %x, i32 %y, i32 %z) nounwind readnone {
entry:
  %0 = and i32 %y, %x                             ; <i32> [#uses=1]
  %not = xor i32 %x, -1                           ; <i32> [#uses=1]
  %1 = and i32 %z, %not                           ; <i32> [#uses=1]
  %2 = xor i32 %1, %0                             ; <i32> [#uses=1]
  ret i32 %2
}

define i32 @Maj(i32 %x, i32 %y, i32 %z) nounwind readnone {
entry:
  %0 = xor i32 %z, %y                             ; <i32> [#uses=1]
  %1 = and i32 %0, %x                             ; <i32> [#uses=1]
  %2 = and i32 %z, %y                             ; <i32> [#uses=1]
  %3 = xor i32 %1, %2                             ; <i32> [#uses=1]
  ret i32 %3
}

define i32 @Ch2(i32 %x, i32 %y, i32 %z) nounwind readnone {
entry:
  %0 = xor i32 %z, %y                             ; <i32> [#uses=1]
  %1 = and i32 %0, %x                             ; <i32> [#uses=1]
  %2 = xor i32 %1, %z                             ; <i32> [#uses=1]
  ret i32 %2
}

define i32 @Maj2(i32 %x, i32 %y, i32 %z) nounwind readnone {
entry:
  %0 = and i32 %z, %y                             ; <i32> [#uses=1]
  %1 = xor i32 %z, %y                             ; <i32> [#uses=1]
  %2 = and i32 %1, %x                             ; <i32> [#uses=1]
  %3 = xor i32 %2, %0                             ; <i32> [#uses=1]
  ret i32 %3
}

From the following C source:

int Ch(int x, int y, int z) {
   return (x&y) ^ (~x&z);
}
int Maj(int x, int y, int z) {
   return (x&y) ^ (x&z) ^ (y&z);
}

int Ch2(int x, int y, int z) {
   return z ^ ((y ^ z) & x);
}
int Maj2(int x, int y, int z) {
   return Ch2(x, y|z, y&z);
}

[llvmbot]

assigned to @LebedevRI

[d0k]

Thanks for the nice testcase, optimization implemented in r108136.

[d0k]

And reverted in r108141 … I hope to fix this later today.

[lattner]

Thanks for working on this Benjamin!

[lattner]

Benjamin: I haven't tracked down the root issue here, but I strongly suspect that this instcombine is just exposing a bug elsewhere in the compiler. An interesting aspect of this is that (on the clang build) the xform triggers either exclusively or almost so for cases when C/D are constants. I'm seeing tons of stuff like this:

XFORM: %6 = and i8 %5, -2 ; [#uses=1]
XFORM: %4 = and i8 %2, 1 ; [#uses=1]
XFORM: %8 = or i8 %4, %6 ; [#uses=1]

This is because m_Not is matching on constants, which is dubious. This should certainly be turned off for constants, because the and/or sequence is better for most targets. However, it looks like we're missing the inverse transformation:

$ cat t.c
int test1(int A, int B) {
return (A&-8388481)|(B&8388480);
}

int test2(int A, int B) {
return ((A^B)&8388480)^A;
}
$ llvm-gcc t.c -S -o - -O3 -m64 -fomit-frame-pointer -mkernel
..
_test1:
andl $-8388481, %edi
andl $8388480, %esi
leal (%rsi,%rdi), %eax
ret
...
test2:
xorl %edi, %esi
andl $8388480, %esi
movl %esi, %eax
xorl %edi, %eax
ret

We should turn the later into the former in the case of a constant. I will continue investigating the latent bug, many of these are triggering on SRoA-created i128's, i256's etc, we really want to keep these and/or and not turn them into xor. However, I want to find and fix the latent bug.

[efriedma-quic]

This is because m_Not is matching on constants, which is dubious. This should
certainly be turned off for constants, because the and/or sequence is better
for most targets.

Actually, for armv5, we generate better code for the xor form, but I think I'd consider that a deficiency in the backend.

[d0k]

patch v2
The newest version of my patch, doesn't transform constants but catches some cases with flipped operands. I don't know if it's worth to add code to catch all possible cases.

[LebedevRI]

https://godbolt.org/g/KafbjK
https://rise4fun.com/Alive/AOe9

This looks pretty straight forward, so i could take a look.
Any idea if the issues that resulted in the reverts were resolved?

[rotateright]

https://godbolt.org/g/KafbjK
https://rise4fun.com/Alive/AOe9

This looks pretty straight forward, so i could take a look.
Any idea if the issues that resulted in the reverts were resolved?

I don't know the history, but I wonder if it would be better to treat this as 2 problems rather than 2 specific folds as in https://reviews.llvm.org/rL108141 .

First, reduce the final xor (and also 'add') to 'or' when the operands have no common bits set:

Name: xor_to_or
%xy = and i32 %x, %y
%notx = xor i32 %x, -1
%nxz = and i32 %notx, %z
%r = xor i32 %xy, %nxz
=>
%r = or i32 %xy, %nxz

Name: add_to_or
%xy = and i32 %x, %y
%notx = xor i32 %x, -1
%nxz = and i32 %notx, %z
%r = add i32 %xy, %nxz
=>
%r = or i32 %xy, %nxz

https://rise4fun.com/Alive/u6f

Inverted operands to 'and' ops might be worth adding to llvm::haveNoCommonBitsSet().

[rotateright]

Another consideration: does the backend recognize the sequential xor sequence if a target has 'andn' or a bit-select instruction?

Eg, x86 with BMI:
andl %edx, %edi
andnl %esi, %edx, %eax
orl %edi, %eax

The 'not' isn't a separate instruction here, so it should always be better than the alternative (better throughput than sequential xor+and+xor because the 'and' and 'andn' can execute in parallel).

AArch64 has 'bsl':
Bitwise Select. This instruction sets each bit in the destination SIMD&FP register to the corresponding bit from the first source SIMD&FP register when the original destination bit was 1, otherwise from the second source SIMD&FP register.

So I think you have to make sure that the IR optimization doesn't cause a regression for this:

define <4 x i32> @​v(<4 x i32> %x, <4 x i32> %y, <4 x i32> %mask) {
%mx = and <4 x i32> %x, %mask
%notmask = xor <4 x i32> %mask, <i32 -1, i32 -1, i32 -1, i32 -1>
%my = and <4 x i32> %y, %notmask
%r = or <4 x i32> %mx, %my
ret <4 x i32> %r
}

[LebedevRI]

Another consideration: does the backend recognize the sequential xor
sequence if a target has 'andn' or a bit-select instruction?

Eg, x86 with BMI:
andl %edx, %edi
andnl %esi, %edx, %eax
orl %edi, %eax

The 'not' isn't a separate instruction here, so it should always be better
than the alternative (better throughput than sequential xor+and+xor because
the 'and' and 'andn' can execute in parallel).

AArch64 has 'bsl':
Bitwise Select. This instruction sets each bit in the destination SIMD&FP
register to the corresponding bit from the first source SIMD&FP register
when the original destination bit was 1, otherwise from the second source
SIMD&FP register.

So I think you have to make sure that the IR optimization doesn't cause a
regression for this:

define <4 x i32> @​v(<4 x i32> %x, <4 x i32> %y, <4 x i32> %mask) {
%mx = and <4 x i32> %x, %mask
%notmask = xor <4 x i32> %mask, <i32 -1, i32 -1, i32 -1, i32 -1>
%my = and <4 x i32> %y, %notmask
%r = or <4 x i32> %mx, %my
ret <4 x i32> %r
}

So in other words, the backend (what specifically?) should be able to unfold:
https://rise4fun.com/Alive/HqI
https://godbolt.org/g/skwsvY
?

I think that

[LebedevRI]

Eh, meant to post that into llvm/llvm-bugzilla-archive#37104

[rotateright]

This looks pretty straight forward, so i could take a look.

So this actually turns out to be more complicated. I see at least 5 steps:

1. DAGCombiner: allow targets with 'andn' functionality to optimize the xor sequence.
2. DAGCombiner: allow targets with 'bsl' functionality to optimize the xor sequence.
3. InstCombine: with no common bits set, convert 'xor' to 'or' (comment 8).
4. InstCombine: with no common bits set, convert 'add' to 'or' (comment 8).
5. InstCombine: convert masked merge (starting for 'or') to 'xor' sequence (comment 7).

#​1 and #​2 are prerequisites for #​5.
#​3 and #​4 look like generally good IR canonicalizations to me with no potential backend concerns, but others may see it differently.

[efriedma-quic]

We already do add->or and xor->or, IIRC.

[LebedevRI]

We already do add->or and xor->or, IIRC.

Based on the testcase output, no.