[InstCombine] Canonicalize ((X & -X) - 1) --> (~X & (X - 1)) (PR51784)

[RKSimon]

Summary

Enables the ctpop((x & -x ) - 1) -> cttz(x, false) fold

Alive2: https://alive2.llvm.org/ce/z/EDk4h7 (((X & -X) - 1) --> (~X & (X - 1)) )

Alive2: https://alive2.llvm.org/ce/z/8Yr3XG (CTPOP -> CTTZ)

Fixes #51126

[RKSimon]

An alternative would be to decide if (~x & (x - 1)) or ((x & -x ) - 1) should be the canonical pattern?

https://alive2.llvm.org/ce/z/WA_cmX

[xbolva00]

In D110488#3022683, @RKSimon wrote:

An alternative would be to decide if (~x & (x - 1)) or ((x & -x ) - 1) should be the canonical pattern?

https://alive2.llvm.org/ce/z/WA_cmX

Yeah I was thinking about some more general pattern too. @spatel?

[spatel]

In D110488#3022686, @xbolva00 wrote:

In D110488#3022683, @RKSimon wrote:

An alternative would be to decide if (~x & (x - 1)) or ((x & -x ) - 1) should be the canonical pattern?

https://alive2.llvm.org/ce/z/WA_cmX

Yeah I was thinking about some more general pattern too. @spatel?

I'd go with the 'not' pattern since that is likely better for known bits - and that's what we were already expecting here.
But if either of the 'and' or 'sub' ops has an extra use, then we can't do the 'not' canonicalization, so we'd want this fold too.

So this patch might be made less important with the 'not' canonicalization, but it could still fire.
I expect this has no detectable compile-time cost and it's a one-line patch, so seems fine to keep it.
But please add tests with extra uses on the preceding ops, so we have motivating (even if they are contrived) regression tests for this patch. That would still show the value of this patch whether we do the other transform or not.

[RKSimon]

Having spoken to @spatel offline, I'm going to add a fold for ((x & -x ) - 1) -> (~x & (x - 1)) as well as the ctpop fold - this will require single/multiuse tests for the inner fold (where it shouldn't fold multiuses) and for the ctpop case (where it should always fold to cttz).

[RKSimon]

Replaced the ctpop fold with a generic ((X & -X) - 1) --> (~X & (X - 1)) canonicalization

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1420 ↗

(On Diff #455168)

The -1 constant should always be canonicalized to operand 1 (RHS), so this doesn't really need to match m_c_Add. You could match each of LHS and RHS instead.

[spatel]

llvm/test/Transforms/InstCombine/add-mask-neg.ll

29 ↗

(On Diff #455168)

This test gets canonicalized by complexity, so it's not testing the pattern that was intended. Needs another instruction to thwart that transform.

[RKSimon]

Use m_Add instead of m_c_Add as it'll canonicalise to RHS constant anyway

[RKSimon]

rebase

[spatel]

LGTM

[RKSimon]

cheers

[thakis]

This breaks check-llvm on non-win afaict: http://45.33.8.238/linux/84811/step_12.txt

Please take a look and revert for now if it takes a while to fix.

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1424 ↗

(On Diff #455205)

Nondet output? Different evaluation order of args between compilers

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1424 ↗

(On Diff #455205)

Good catch - yeah, use local variables to ensure that the xor and add are inserted in a fixed order.

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1424 ↗

(On Diff #455205)

yup - I've reverted and have a fix testing on wsl2 now

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

if (Op0->hasOneUse() &&
     Function *F =
         Intrinsic::getDeclaration(II.getModule(), Intrinsic::cttz, Ty);
     auto *Cttz = IC.Builder.CreateCall(F, {X, IC.Builder.getFalse()});
     auto *Bw = ConstantInt::get(Ty, APInt(BitWidth, BitWidth));
     return IC.replaceInstUsesWith(II, IC.Builder.CreateSub(Bw, Cttz));
   }
 
   // ctpop(~x & (x - 1)) -> cttz(x, false)
+  // ctpop((x & -x ) - 1) -> cttz(x, false)
   if (match(Op0,
-            m_c_And(m_Not(m_Value(X)), m_Add(m_Deferred(X), m_AllOnes())))) {
+            m_c_And(m_Not(m_Value(X)), m_Add(m_Deferred(X), m_AllOnes()))) ||
+      match(Op0,
+            m_Add(m_c_And(m_Value(X), m_Neg(m_Deferred(X))), m_AllOnes()))) {
     Function *F =
         Intrinsic::getDeclaration(II.getModule(), Intrinsic::cttz, Ty);
     return CallInst::Create(F, {X, IC.Builder.getFalse()});
   }
 
   // Zext doesn't change the number of set bits, so narrow:
   // ctpop (zext X) --> zext (ctpop X)
   if (match(Op0, m_OneUse(m_ZExt(m_Value(X))))) {

llvm/test/Transforms/InstCombine/ctpop-cttz.ll

;
   %6 = add i32 %5, %4
   ret i32 %6
 }
 
 ; PR51784
 ; __builtin_popcount((i & -i) - 1) -> __builtin_cttz(i, false)
 define i32 @ctpop3(i32 %0) {
 ; CHECK-LABEL: @ctpop3(
-; CHECK-NEXT:    [[TMP2:%.*]] = sub i32 0, [[TMP0:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], [[TMP0]]
-; CHECK-NEXT:    [[TMP4:%.*]] = add i32 [[TMP3]], -1
-; CHECK-NEXT:    [[TMP5:%.*]] = tail call i32 @llvm.ctpop.i32(i32 [[TMP4]]), !range [[RNG0]]
-; CHECK-NEXT:    ret i32 [[TMP5]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.cttz.i32(i32 [[TMP0:%.*]], i1 false), !range [[RNG0]]
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %2 = sub i32 0, %0
   %3 = and i32 %2, %0
   %4 = add i32 %3, -1
   %5 = tail call i32 @llvm.ctpop.i32(i32 %4)
   ret i32 %5
 }
 
 define <2 x i32> @ctpop3v(<2 x i32> %0) {
 ; CHECK-LABEL: @ctpop3v(
-; CHECK-NEXT:    [[TMP2:%.*]] = sub <2 x i32> zeroinitializer, [[TMP0:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = and <2 x i32> [[TMP2]], [[TMP0]]
-; CHECK-NEXT:    [[TMP4:%.*]] = add <2 x i32> [[TMP3]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[TMP5:%.*]] = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[TMP4]])
-; CHECK-NEXT:    ret <2 x i32> [[TMP5]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i32> @llvm.cttz.v2i32(<2 x i32> [[TMP0:%.*]], i1 false)
+; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
 ;
   %2 = sub <2 x i32> zeroinitializer, %0
   %3 = and <2 x i32> %2, %0
   %4 = add <2 x i32> %3, <i32 -1, i32 -1>
   %5 = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %4)
   ret <2 x i32> %5
 }
 
 define <2 x i32> @ctpop3v_undef(<2 x i32> %0) {
 ; CHECK-LABEL: @ctpop3v_undef(
-; CHECK-NEXT:    [[TMP2:%.*]] = sub <2 x i32> zeroinitializer, [[TMP0:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = and <2 x i32> [[TMP2]], [[TMP0]]
-; CHECK-NEXT:    [[TMP4:%.*]] = add <2 x i32> [[TMP3]], <i32 -1, i32 undef>
-; CHECK-NEXT:    [[TMP5:%.*]] = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> [[TMP4]])
-; CHECK-NEXT:    ret <2 x i32> [[TMP5]]
+; CHECK-NEXT:    [[TMP2:%.*]] = call <2 x i32> @llvm.cttz.v2i32(<2 x i32> [[TMP0:%.*]], i1 false)
+; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
 ;
   %2 = sub <2 x i32> zeroinitializer, %0
   %3 = and <2 x i32> %2, %0
   %4 = add <2 x i32> %3, <i32 -1, i32 undef>
   %5 = tail call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %4)
   ret <2 x i32> %5
 }