[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

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

31

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

Nondet output? Different evaluation order of args between compilers

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1424

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

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

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombinerImpl::visitAdd(BinaryOperator &I) {
   if (match(&I, m_c_BinOp(m_Or(m_Value(A), m_Value(B)),
                           m_c_And(m_Deferred(A), m_Deferred(B))))) {
     // Replacing operands in-place to preserve nuw/nsw flags.
     replaceOperand(I, 0, A);
     replaceOperand(I, 1, B);
     return &I;
   }
 
+  // Canonicalize ((A & -A) - 1) --> (~A & (A - 1))
+  // Forms all commutable operations, and simplifies ctpop -> cttz folds.
+  if (match(&I,
+            m_Add(m_OneUse(m_c_And(m_Value(A), m_OneUse(m_Neg(m_Deferred(A))))),
+                  m_AllOnes()))) {
+    Constant *AllOnes = ConstantInt::getAllOnesValue(RHS->getType());
+    return BinaryOperator::CreateAnd(Builder.CreateXor(A, AllOnes),
+                                     Builder.CreateAdd(A, AllOnes));
+  }
+
   // TODO(jingyue): Consider willNotOverflowSignedAdd and
   // willNotOverflowUnsignedAdd to reduce the number of invocations of
   // computeKnownBits.
   bool Changed = false;
   if (!I.hasNoSignedWrap() && willNotOverflowSignedAdd(LHS, RHS, I)) {
     Changed = true;
     I.setHasNoSignedWrap(true);
   }

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -passes=instcombine | FileCheck %s
 
 ;
-; TODO: Canonicalize ((X & -X) - 1) --> (~X & (X - 1))
+; Canonicalize ((X & -X) - 1) --> (~X & (X - 1))
 ;
 
 define i32 @dec_mask_neg_i32(i32 %X) {
 ; CHECK-LABEL: @dec_mask_neg_i32(
-; CHECK-NEXT:    [[NEG:%.*]] = sub i32 0, [[X:%.*]]
-; CHECK-NEXT:    [[MASK:%.*]] = and i32 [[NEG]], [[X]]
-; CHECK-NEXT:    [[DEC:%.*]] = add i32 [[MASK]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[X]], -1
+; CHECK-NEXT:    [[DEC:%.*]] = and i32 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i32 [[DEC]]
 ;
   %neg = sub i32 0, %X
   %mask = and i32 %neg, %X
   %dec = add i32 %mask, -1
   ret i32 %dec
 }
 
 define i32 @dec_mask_commute_neg_i32(i32 %A) {
 ; CHECK-LABEL: @dec_mask_commute_neg_i32(
 ; CHECK-NEXT:    [[X:%.*]] = sdiv i32 42, [[A:%.*]]
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[MASK:%.*]] = and i32 [[X]], [[NEG]]
-; CHECK-NEXT:    [[DEC:%.*]] = add i32 [[MASK]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i32 [[X]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[X]], -1
+; CHECK-NEXT:    [[DEC:%.*]] = and i32 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i32 [[DEC]]
 ;
   %X = sdiv i32 42, %A ; thwart complexity-based canonicalization
   %neg = sub i32 0, %X
   %mask = and i32 %X, %neg
   %dec = add i32 %mask, -1
   ret i32 %dec
 }
 
 define i32 @dec_commute_mask_neg_i32(i32 %X) {
 ; CHECK-LABEL: @dec_commute_mask_neg_i32(
-; CHECK-NEXT:    [[NEG:%.*]] = sub i32 0, [[X:%.*]]
-; CHECK-NEXT:    [[MASK:%.*]] = and i32 [[NEG]], [[X]]
-; CHECK-NEXT:    [[DEC:%.*]] = add i32 [[MASK]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[X]], -1
+; CHECK-NEXT:    [[DEC:%.*]] = and i32 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i32 [[DEC]]
 ;
   %neg = sub i32 0, %X
   %mask = and i32 %neg, %X
   %dec = add i32 -1, %mask
   ret i32 %dec
 }
 
;
   %mask = and i32 %neg, %X
   %dec = add i32 %mask, -1
   call void @use(i32 %mask)
   ret i32 %dec
 }
 
 define <2 x i32> @dec_mask_neg_v2i32(<2 x i32> %X) {
 ; CHECK-LABEL: @dec_mask_neg_v2i32(
-; CHECK-NEXT:    [[NEG:%.*]] = sub <2 x i32> zeroinitializer, [[X:%.*]]
-; CHECK-NEXT:    [[MASK:%.*]] = and <2 x i32> [[NEG]], [[X]]
-; CHECK-NEXT:    [[DEC:%.*]] = add <2 x i32> [[MASK]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP1:%.*]] = add <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = xor <2 x i32> [[X]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[DEC:%.*]] = and <2 x i32> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i32> [[DEC]]
 ;
   %neg = sub <2 x i32> zeroinitializer, %X
   %mask = and <2 x i32> %neg, %X
   %dec = add <2 x i32> %mask, <i32 -1, i32 -1>
   ret <2 x i32> %dec
 }
 
 define <2 x i32> @dec_mask_neg_v2i32_undef(<2 x i32> %X) {
 ; CHECK-LABEL: @dec_mask_neg_v2i32_undef(
-; CHECK-NEXT:    [[NEG:%.*]] = sub <2 x i32> zeroinitializer, [[X:%.*]]
-; CHECK-NEXT:    [[MASK:%.*]] = and <2 x i32> [[NEG]], [[X]]
-; CHECK-NEXT:    [[DEC:%.*]] = add <2 x i32> [[MASK]], <i32 -1, i32 undef>
+; CHECK-NEXT:    [[TMP1:%.*]] = add <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = xor <2 x i32> [[X]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[DEC:%.*]] = and <2 x i32> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <2 x i32> [[DEC]]
 ;
   %neg = sub <2 x i32> zeroinitializer, %X
   %mask = and <2 x i32> %neg, %X
   %dec = add <2 x i32> %mask, <i32 -1, i32 undef>
   ret <2 x i32> %dec
 }
 

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
 }