[InstCombine] Change order of canonicalization of ADD and AND

[foad]

Summary

Canonicalize ((x + C1) & C2) --> ((x & C2) + C1) for suitable constants
C1 and C2, instead of the other way round. This should allow more
constant ADDs to be matched as part of addressing modes for loads and
stores.

[foad]

This patch subsumes D129844.

I'm not sure what sort of testing is required to show that it improves (or at least doesn't degrade) codegen.

llvm/test/Transforms/InstCombine/or.ll

164

This regression is unfortunate but I don't know what to do about it. Perhaps we can just live with it?

[RKSimon]

llvm/test/Transforms/InstCombine/add.ll

727

Update the comment

[foad]

Update test comment

[foad]

Ping!

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1895

C->isNegatedPowerOf2() ?

llvm/test/Transforms/InstCombine/or.ll

158

Please put a TODO note on this test that says this could reduce to t1+2.

[foad]

Address review comments.

[spatel]

LGTM - see inline for one more test upate.

The question of other logic + math combos came up in the previous review. It looks like we don't handle those either way:
https://github.com/llvm/llvm-project/issues/56731

So this patch should be generalized as a next step (although I have no idea if that would uncover other problems).

llvm/test/Transforms/InstCombine/add.ll

771

This is an existing issue, but this test doesn't add any value as-is. We should be testing if %and has an extra use, not %x.

[foad]

Fix multi use test

[foad]

Rebase.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (C->isOne() && Op0->hasOneUse()) {
     const APInt *C3;
     if (match(Op0, m_AShr(m_Shl(m_Value(X), m_APInt(C2)), m_APInt(C3))) &&
         C2 == C3 && *C2 == Ty->getScalarSizeInBits() - 1) {
       Value *NotX = Builder.CreateNot(X);
       return BinaryOperator::CreateAnd(NotX, ConstantInt::get(Ty, 1));
     }
   }
 
-  // If all bits affected by the add are included in a high-bit-mask, do the
-  // add before the mask op:
-  // (X & 0xFF00) + xx00 --> (X + xx00) & 0xFF00
-  if (match(Op0, m_OneUse(m_And(m_Value(X), m_APInt(C2)))) &&
-      C2->isNegative() && C2->isShiftedMask() && *C == (*C & *C2)) {
-    Value *NewAdd = Builder.CreateAdd(X, ConstantInt::get(Ty, *C));
-    return BinaryOperator::CreateAnd(NewAdd, ConstantInt::get(Ty, *C2));
-  }
-
   return nullptr;
 }
 
 // Matches multiplication expression Op * C where C is a constant. Returns the
 // constant value in C and the other operand in Op. Returns true if such a
 // match is found.
 static bool MatchMul(Value *E, Value *&Op, APInt &C) {
   const APInt *AI;

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(Op0, m_Add(m_Value(X), m_APInt(AddC)))) {
       // the constant we are adding has no bits set below that bit, then the
       // add is flipping a single bit. Example:
       // (X + 4) & 4 --> (X & 4) ^ 4
       if (Op0->hasOneUse() && C->isPowerOf2() && (*AddC & (*C - 1)) == 0) {
         assert((*C & *AddC) != 0 && "Expected common bit");
         Value *NewAnd = Builder.CreateAnd(X, Op1);
         return BinaryOperator::CreateXor(NewAnd, Op1);
       }
+
+      // If all bits affected by the add are included in a high-bit-mask, do the
+      // mask op before the add. Example:
+      // (X + 16) & -4 --> (X & -4) + 16
+      if (Op0->hasOneUse() && C->isNegatedPowerOf2() && *AddC == (*AddC & *C)) {
+        Value *NewAnd = Builder.CreateAnd(X, Op1);
+        return BinaryOperator::CreateAdd(NewAnd, ConstantInt::get(Ty, *AddC));
+      }
     }
 
     // ((C1 OP zext(X)) & C2) -> zext((C1 OP X) & C2) if C2 fits in the
     // bitwidth of X and OP behaves well when given trunc(C1) and X.
     auto isNarrowableBinOpcode = [](BinaryOperator *B) {
       switch (B->getOpcode()) {
       case Instruction::Xor:
       case Instruction::Or:

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

if (Pred == ICmpInst::Predicate::ICMP_NE)
     std::swap(X, XBiasedHighBits);
 
   // FIXME: we could support non non-splats here.
 
   const APInt *LowBitMaskCst;
   if (!match(XLowBits, m_And(m_Specific(X), m_APIntAllowUndef(LowBitMaskCst))))
     return nullptr;
 
+  // Match even if the AND and ADD are swapped.
   const APInt *BiasCst, *HighBitMaskCst;
   if (!match(XBiasedHighBits,
              m_And(m_Add(m_Specific(X), m_APIntAllowUndef(BiasCst)),
-                   m_APIntAllowUndef(HighBitMaskCst))))
+                   m_APIntAllowUndef(HighBitMaskCst))) &&
+      !match(XBiasedHighBits,
+             m_Add(m_And(m_Specific(X), m_APIntAllowUndef(HighBitMaskCst)),
+                   m_APIntAllowUndef(BiasCst))))
     return nullptr;
 
   if (!LowBitMaskCst->isMask())
     return nullptr;
 
   APInt InvertedLowBitMaskCst = ~*LowBitMaskCst;
   if (InvertedLowBitMaskCst != *HighBitMaskCst)
     return nullptr;

llvm/test/Transforms/InstCombine/add.ll

 ; CHECK-NEXT:    ret i8 [[C]]
 ;
   %B = add i8 %A, 64
   %C = and i8 %B, 12
   ret i8 %C
 }
 
 ; If all bits affected by the add are included
-; in the mask, do the add before the mask op.
+; in the mask, do the mask op before the add.
 
 define i8 @masked_add(i8 %x) {
 ; CHECK-LABEL: @masked_add(
-; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], 96
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[TMP1]], -16
+; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], -16
+; CHECK-NEXT:    [[R:%.*]] = add i8 [[AND]], 96
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %and = and i8 %x, 240 ; 0xf0
   %r = add i8 %and, 96  ; 0x60
   ret i8 %r
 }
 
 define <2 x i8> @masked_add_splat(<2 x i8> %x) {
 ; CHECK-LABEL: @masked_add_splat(
-; CHECK-NEXT:    [[TMP1:%.*]] = add <2 x i8> [[X:%.*]], <i8 64, i8 64>
-; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[TMP1]], <i8 -64, i8 -64>
+; CHECK-NEXT:    [[AND:%.*]] = and <2 x i8> [[X:%.*]], <i8 -64, i8 -64>
+; CHECK-NEXT:    [[R:%.*]] = add <2 x i8> [[AND]], <i8 64, i8 64>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %and = and <2 x i8> %x, <i8 192, i8 192> ; 0xc0
   %r = add <2 x i8> %and, <i8 64, i8 64>  ; 0x40
   ret <2 x i8> %r
 }
 
 define i8 @not_masked_add(i8 %x) {
 ; CHECK-LABEL: @not_masked_add(
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], 112
 ; CHECK-NEXT:    [[R:%.*]] = add nuw i8 [[AND]], 96
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %and = and i8 %x, 112 ; 0x70
   %r = add i8 %and, 96  ; 0x60
   ret i8 %r
 }
 
 define i8 @masked_add_multi_use(i8 %x) {
 ; CHECK-LABEL: @masked_add_multi_use(
-; CHECK-NEXT:    [[TMP:%.*]] = add i8 [[X:%.*]], 96
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[TMP:%.*]], -16
-; CHECK-NEXT:    call void @use(i8 [[X]])
+; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], -16
+; CHECK-NEXT:    [[R:%.*]] = add i8 [[AND]], 96
+; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %and = and i8 %x, -16 ; 0xf0
   %r = add i8 %and, 96  ; 0x60
-  call void @use(i8 %x) ; extra use
+  call void @use(i8 %and) ; extra use
   ret i8 %r
 }
 
 define i32 @test35(i32 %a) {
 ; CHECK-LABEL: @test35(
 ; CHECK-NEXT:    ret i32 -1
 ;
   %tmpnot = xor i32 %a, -1

llvm/test/Transforms/InstCombine/integer-round-up-pow2-alignment.ll

;
   ret <2 x i8> %x.roundedup
 }
 
 ; The X are different
 define i8 @n9_wrong_x0(i8 %x.0, i8 %x.1) {
 ; CHECK-LABEL: @n9_wrong_x0(
 ; CHECK-NEXT:    [[X_LOWBITS:%.*]] = and i8 [[X_0:%.*]], 15
 ; CHECK-NEXT:    [[X_LOWBITS_ARE_ZERO:%.*]] = icmp eq i8 [[X_LOWBITS]], 0
-; CHECK-NEXT:    [[X_BIASED:%.*]] = add i8 [[X_0]], 16
-; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = and i8 [[X_BIASED]], -16
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X_0]], -16
+; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = add i8 [[TMP1]], 16
 ; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = select i1 [[X_LOWBITS_ARE_ZERO]], i8 [[X_1:%.*]], i8 [[X_BIASED_HIGHBITS]]
 ; CHECK-NEXT:    ret i8 [[X_ROUNDEDUP]]
 ;
   %x.lowbits = and i8 %x.0, 15
   %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 0
   %x.biased = add i8 %x.0, 16
   %x.biased.highbits = and i8 %x.biased, -16
   %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x.1, i8 %x.biased.highbits
   ret i8 %x.roundedup
 }
 define i8 @n9_wrong_x1(i8 %x.0, i8 %x.1) {
 ; CHECK-LABEL: @n9_wrong_x1(
 ; CHECK-NEXT:    [[X_LOWBITS:%.*]] = and i8 [[X_0:%.*]], 15
 ; CHECK-NEXT:    [[X_LOWBITS_ARE_ZERO:%.*]] = icmp eq i8 [[X_LOWBITS]], 0
-; CHECK-NEXT:    [[X_BIASED:%.*]] = add i8 [[X_1:%.*]], 16
-; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = and i8 [[X_BIASED]], -16
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X_1:%.*]], -16
+; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = add i8 [[TMP1]], 16
 ; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = select i1 [[X_LOWBITS_ARE_ZERO]], i8 [[X_0]], i8 [[X_BIASED_HIGHBITS]]
 ; CHECK-NEXT:    ret i8 [[X_ROUNDEDUP]]
 ;
   %x.lowbits = and i8 %x.0, 15
   %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 0
   %x.biased = add i8 %x.1, 16
   %x.biased.highbits = and i8 %x.biased, -16
   %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x.0, i8 %x.biased.highbits
   ret i8 %x.roundedup
 }
 define i8 @n9_wrong_x2(i8 %x.0, i8 %x.1) {
 ; CHECK-LABEL: @n9_wrong_x2(
 ; CHECK-NEXT:    [[X_LOWBITS:%.*]] = and i8 [[X_1:%.*]], 15
 ; CHECK-NEXT:    [[X_LOWBITS_ARE_ZERO:%.*]] = icmp eq i8 [[X_LOWBITS]], 0
-; CHECK-NEXT:    [[X_BIASED:%.*]] = add i8 [[X_0:%.*]], 16
-; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = and i8 [[X_BIASED]], -16
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X_0:%.*]], -16
+; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = add i8 [[TMP1]], 16
 ; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = select i1 [[X_LOWBITS_ARE_ZERO]], i8 [[X_0]], i8 [[X_BIASED_HIGHBITS]]
 ; CHECK-NEXT:    ret i8 [[X_ROUNDEDUP]]
 ;
   %x.lowbits = and i8 %x.1, 15
   %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 0
   %x.biased = add i8 %x.0, 16
   %x.biased.highbits = and i8 %x.biased, -16
   %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x.0, i8 %x.biased.highbits
   ret i8 %x.roundedup
 }
 
 ; Wrong low-bit mask
 define i8 @n10_wrong_low_bit_mask(i8 %x) {
 ; CHECK-LABEL: @n10_wrong_low_bit_mask(
 ; CHECK-NEXT:    [[X_LOWBITS:%.*]] = and i8 [[X:%.*]], 31
 ; CHECK-NEXT:    [[X_LOWBITS_ARE_ZERO:%.*]] = icmp eq i8 [[X_LOWBITS]], 0
-; CHECK-NEXT:    [[X_BIASED:%.*]] = add i8 [[X]], 16
-; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = and i8 [[X_BIASED]], -16
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], -16
+; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = add i8 [[TMP1]], 16
 ; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = select i1 [[X_LOWBITS_ARE_ZERO]], i8 [[X]], i8 [[X_BIASED_HIGHBITS]]
 ; CHECK-NEXT:    ret i8 [[X_ROUNDEDUP]]
 ;
   %x.lowbits = and i8 %x, 31
   %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 0
   %x.biased = add i8 %x, 16
   %x.biased.highbits = and i8 %x.biased, -16
   %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
;
   ret i8 %x.roundedup
 }
 
 ; Wrong bias
 define i8 @n12_wrong_bias(i8 %x) {
 ; CHECK-LABEL: @n12_wrong_bias(
 ; CHECK-NEXT:    [[X_LOWBITS:%.*]] = and i8 [[X:%.*]], 15
 ; CHECK-NEXT:    [[X_LOWBITS_ARE_ZERO:%.*]] = icmp eq i8 [[X_LOWBITS]], 0
-; CHECK-NEXT:    [[X_BIASED:%.*]] = add i8 [[X]], 32
-; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = and i8 [[X_BIASED]], -16
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], -16
+; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = add i8 [[TMP1]], 32
 ; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = select i1 [[X_LOWBITS_ARE_ZERO]], i8 [[X]], i8 [[X_BIASED_HIGHBITS]]
 ; CHECK-NEXT:    ret i8 [[X_ROUNDEDUP]]
 ;
   %x.lowbits = and i8 %x, 15
   %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 0
   %x.biased = add i8 %x, 32
   %x.biased.highbits = and i8 %x.biased, -16
   %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
;
   ret i8 %x.roundedup
 }
 
 ; Comparison is not with zero
 define i8 @n14_wrong_comparison_constant(i8 %x) {
 ; CHECK-LABEL: @n14_wrong_comparison_constant(
 ; CHECK-NEXT:    [[X_LOWBITS:%.*]] = and i8 [[X:%.*]], 15
 ; CHECK-NEXT:    [[X_LOWBITS_ARE_ZERO:%.*]] = icmp eq i8 [[X_LOWBITS]], 1
-; CHECK-NEXT:    [[X_BIASED:%.*]] = add i8 [[X]], 16
-; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = and i8 [[X_BIASED]], -16
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], -16
+; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = add i8 [[TMP1]], 16
 ; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = select i1 [[X_LOWBITS_ARE_ZERO]], i8 [[X]], i8 [[X_BIASED_HIGHBITS]]
 ; CHECK-NEXT:    ret i8 [[X_ROUNDEDUP]]
 ;
   %x.lowbits = and i8 %x, 15
   %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 1
   %x.biased = add i8 %x, 16
   %x.biased.highbits = and i8 %x.biased, -16
   %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
   ret i8 %x.roundedup
 }
 
 ; Wrong comparison
 define i8 @n15_wrong_comparison_predicate_and_constant(i8 %x) {
 ; CHECK-LABEL: @n15_wrong_comparison_predicate_and_constant(
 ; CHECK-NEXT:    [[X_LOWBITS:%.*]] = and i8 [[X:%.*]], 14
 ; CHECK-NEXT:    [[X_LOWBITS_ARE_ZERO:%.*]] = icmp eq i8 [[X_LOWBITS]], 0
-; CHECK-NEXT:    [[X_BIASED:%.*]] = add i8 [[X]], 16
-; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = and i8 [[X_BIASED]], -16
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], -16
+; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = add i8 [[TMP1]], 16
 ; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = select i1 [[X_LOWBITS_ARE_ZERO]], i8 [[X]], i8 [[X_BIASED_HIGHBITS]]
 ; CHECK-NEXT:    ret i8 [[X_ROUNDEDUP]]
 ;
   %x.lowbits = and i8 %x, 15
   %x.lowbits.are.zero = icmp ult i8 %x.lowbits, 2
   %x.biased = add i8 %x, 16
   %x.biased.highbits = and i8 %x.biased, -16
   %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
   ret i8 %x.roundedup
 }
 
 ; %x.biased.highbits must not have other uses
 define i8 @n16_oneuse(i8 %x) {
 ; CHECK-LABEL: @n16_oneuse(
 ; CHECK-NEXT:    [[X_LOWBITS:%.*]] = and i8 [[X:%.*]], 15
 ; CHECK-NEXT:    [[X_LOWBITS_ARE_ZERO:%.*]] = icmp eq i8 [[X_LOWBITS]], 0
-; CHECK-NEXT:    [[X_BIASED:%.*]] = add i8 [[X]], 16
-; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = and i8 [[X_BIASED]], -16
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], -16
+; CHECK-NEXT:    [[X_BIASED_HIGHBITS:%.*]] = add i8 [[TMP1]], 16
 ; CHECK-NEXT:    call void @use.i8(i8 [[X_BIASED_HIGHBITS]])
 ; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = select i1 [[X_LOWBITS_ARE_ZERO]], i8 [[X]], i8 [[X_BIASED_HIGHBITS]]
 ; CHECK-NEXT:    ret i8 [[X_ROUNDEDUP]]
 ;
   %x.lowbits = and i8 %x, 15
   %x.lowbits.are.zero = icmp eq i8 %x.lowbits, 0
   %x.biased = add i8 %x, 16
   %x.biased.highbits = and i8 %x.biased, -16

llvm/test/Transforms/InstCombine/or.ll

 ; CHECK-LABEL: @test20(
 ; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
   %y = and i32 %x, 123
   %z = or i32 %y, %x
   ret i32 %z
 }
 
+; TODO: This should combine to t1 + 2.
 define i32 @test21(i32 %t1) {
 ; CHECK-LABEL: @test21(
-; CHECK-NEXT:    [[T1_MASK1:%.*]] = add i32 [[T1:%.*]], 2
-; CHECK-NEXT:    ret i32 [[T1_MASK1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[T1:%.*]], -2
+; CHECK-NEXT:    [[T3:%.*]] = add i32 [[TMP1]], 2
+; CHECK-NEXT:    [[T5:%.*]] = and i32 [[T1]], 1
+; CHECK-NEXT:    [[T6:%.*]] = or i32 [[T5]], [[T3]]
+; CHECK-NEXT:    ret i32 [[T6]]
 ;
   %t1.mask1 = add i32 %t1, 2
   %t3 = and i32 %t1.mask1, -2
   %t5 = and i32 %t1, 1
   ;; add tmp.1, 2
   %t6 = or i32 %t5, %t3
   ret i32 %t6
 }

llvm/test/Transforms/InstCombine/sub.ll

;
   %a = add i8 %s1, %y
   call void @use8(i8 %a)
   %s2 = sub i8 %a, %z
   ret i8 %s2
 }
 
 define i8 @sub_mask_lowbits(i8 %x) {
 ; CHECK-LABEL: @sub_mask_lowbits(
-; CHECK-NEXT:    [[A1:%.*]] = add i8 [[X:%.*]], -108
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[A1]], -4
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], -4
+; CHECK-NEXT:    [[R:%.*]] = add i8 [[TMP1]], -108
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %a1 = add i8 %x, 148 ; 0x94
   %a2 = and i8 %x, 3
   %r = sub i8 %a1, %a2
   ret i8 %r
 }