[InstCombine] Canonicalize "and, add", "or, add", "xor, add"

[emgullufsen]

Summary

Canonicalize

((x + C1) & C2) --> ((x & C2) + C1)     
((x + C1) ^ C2) --> ((x ^ C2) + C1)     
((x + C1) | C2) --> ((x | C2) + C1)

for suitable constants C1 and C2.

Alive2 proofs: add, or --> or, add
add, xor --> xor, add
add, and --> and, add

[emgullufsen]

Hadn't run clang-format

[emgullufsen]

I wasn't sure whether to subsume D130080 or make this revision a child of that one.

[emgullufsen]

Update on top of new negative multiple use tests in and-xor-or.ll

[emgullufsen]

Updated on top of vector tests

[emgullufsen]

Added clarifying comment in test

[emgullufsen]

clang-format

[emgullufsen]

Needed to run update_test_checks.py against add.ll

[foad]

Looks good overall.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1769

The way you've written it is fine. Just remove the comment.

1774

Can you just fold the ! and >= into < please

1783

This can be llvm_unreachable

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

13–14

These changes are not significant - it's just update_test_checks choosing a different name for its variables. Could you regenerate the checks for this file first and commit that, and then rebase the current patch?

[bcl5980]

We need to keep nsw/nuw for add I think.
And it's better to provider alive proof link also.

llvm/test/Transforms/InstCombine/add.ll

726 ↗

(On Diff #451667)

I think this code want to get better address pattern for load/store. But don't know why we do this before with this comment.
@spatel this test case is commited on dab8515370c7fd43782e72c46333e801454219cc
do you remember the history about the test ?

[hiraditya]

nit: please edit the summary with

// (X + C2) | C
// (X + C2) ^ C
// (X + C2) & C

[spatel]

llvm/test/Transforms/InstCombine/add.ll

726 ↗

(On Diff #451667)

I didn't find any direct reason, but f82c55fa082711f520 inverted the transform and updated the comment. This patch needs to be rebased, so we are not confusing the diffs.

[foad]

In D131142#3743081, @bcl5980 wrote:

We need to keep nsw/nuw for add I think.

Agreed, good point.

[emgullufsen]

Rebase & Address comments

[emgullufsen]

This patch now does not affect integer-round-up-pow2-alignment.ll (since those changes merged via rGf82c55fa082711f520a7359393b483956b69bf08). So, the NFC changes (changes of variable names) that update_test_checks would make don't have to be addressed at this time (I don't think). I did pull those NFC changes to this test out anyway as D132564, but as said I don't think this needs to be messed with just now.

[spatel]

This seems right, but can you verify with Alive2 and add the links to the patch summary.
If I modeled the code correctly, it looks like this for or/xor:
https://alive2.llvm.org/ce/z/BhAeCl
...and needs a small adjustment for 'and'.

[emgullufsen]

In D131142#3752110, @spatel wrote:

This seems right, but can you verify with Alive2 and add the links to the patch summary.
If I modeled the code correctly, it looks like this for or/xor:
https://alive2.llvm.org/ce/z/BhAeCl
...and needs a small adjustment for 'and'.

Oh shoot I had meant to include alive2 proofs - sorry for that (and thank you for or/xor proofs) - will get patch summary updated.

[spatel]

LGTM

[emgullufsen]

Sorry for the failed test - I ran update_test_checks against test/Transforms/InstCombine/freeze.ll,
and the changes I verified using Alive2 https://alive2.llvm.org/ce/z/4ABLcz

[spatel]

To confirm, you just missed updating a test, right?
Still LGTM - the extra test diff is an improvement. :)

[emgullufsen]

In D131142#3752627, @spatel wrote:

To confirm, you just missed updating a test, right?
Still LGTM - the extra test diff is an improvement. :)

Yes I just missed updating a test that I should have noticed, that actually caused bot failure. But freeze.ll seems to be the only one I missed - check-llvm results look good now.

[emgullufsen]

Thanks for reverting @reames - when you have a second maybe you could please have a look over this updated patch?

[reames]

In D131142#3752707, @emgullufsen wrote:

Thanks for reverting @reames - when you have a second maybe you could please have a look over this updated patch?

No need. I reverted because of a broken test, if that's been fixed, your LGTM stands.

[emgullufsen]

In D131142#3752708, @reames wrote:

In D131142#3752707, @emgullufsen wrote:

Thanks for reverting @reames - when you have a second maybe you could please have a look over this updated patch?

No need. I reverted because of a broken test, if that's been fixed, your LGTM stands.

Cool I see - I didn't think I needed to ask for review from reverting dev from Developer Policy, but just wanted to be sure I guess. Thanks again to you and to @spatel for help with proofs and review. Will be more careful with tests in the future.

[bcl5980]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1787

I still insist we should add the nsw/nuw flags here as this transform is really easy case to pass the flags.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1787

Yes - if we can keep flags, we should do that. @emgullufsen - can you create tests/patch for that?

[emgullufsen]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1787

Sorry to leave this unseen for so long - certainly I am happy to create tests/patch to account for nsw/nuw flags, thanks @bcl5980 & @spatel

[emgullufsen]

In D131142#3743081, @bcl5980 wrote:

We need to keep nsw/nuw for add I think.
And it's better to provider alive proof link also.

Sorry to miss provisioning for carrying through nsw/nuw flags before, I am preparing tests/patch to fix this and will add as reviewer.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

 //===- InstCombineAddSub.cpp ------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
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

 //===- InstCombineAndOrXor.cpp --------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (match(Op1, m_OneUse(m_Not(m_OneUse(
       return BinaryOperator::Create(
           FlippedOpcode, Builder.CreateBinOp(Opcode, B, Builder.CreateNot(C)),
           X);
   }
 
   return nullptr;
 }
 
+// Match
+// (X + C2) | C
+// (X + C2) ^ C
+// (X + C2) & C 
+// and convert to do the bitwise logic first:
+// (X | C) + C2
+// (X ^ C) + C2
+// (X & C) + C2
+//iff bits affected by logic op are lower than last bit affected by math op
+static Instruction *canonicalizeLogicFirst(BinaryOperator &I,
+                                           InstCombiner::BuilderTy &Builder) {
+  Type *Ty = I.getType();
+  Instruction::BinaryOps OpC = I.getOpcode();
+  Value *Op0 = I.getOperand(0);
+  Value *Op1 = I.getOperand(1);
+  Value *X;
+  const APInt *C, *C2;
+
+  if (!(match(Op0, m_OneUse(m_Add(m_Value(X), m_APInt(C2)))) &&
+        match(Op1, m_APInt(C))))
+    return nullptr;
+
+  unsigned Width = Ty->getScalarSizeInBits(); // C2->getBitWidth() instead?
+  unsigned LastOneMath = Width - C2->countTrailingZeros();
+
+  switch (OpC) {
+  case Instruction::And:
+    if (!(C->countLeadingOnes() >= LastOneMath))
+      return nullptr;
+    break;
+  case Instruction::Xor:
+  case Instruction::Or:
+    if (!(C->countLeadingZeros() >= LastOneMath))
+      return nullptr;
+    break;
+  default:
+    return nullptr;
+  }
+
+  Value *NewBinOp = Builder.CreateBinOp(OpC, X, ConstantInt::get(Ty, *C));
+  return BinaryOperator::CreateAdd(NewBinOp, ConstantInt::get(Ty, *C2));
+}
+
 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
 // here. We should standardize that construct where it is needed or choose some
 // other way to ensure that commutated variants of patterns are not missed.
 Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) {
   Type *Ty = I.getType();
 
   if (Value *V = simplifyAndInst(I.getOperand(0), I.getOperand(1),
                                  SQ.getWithInstruction(&I)))
Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) {
   if (sinkNotIntoOtherHandOfAndOrOr(I))
     return &I;
 
   // An and recurrence w/loop invariant step is equivelent to (and start, step)
   PHINode *PN = nullptr;
   Value *Start = nullptr, *Step = nullptr;
   if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
     return replaceInstUsesWith(I, Builder.CreateAnd(Start, Step));
   
+  if (Instruction *Canonicalized = canonicalizeLogicFirst(I, Builder))
+    return Canonicalized;
+  
   return nullptr;
 }
 
 Instruction *InstCombinerImpl::matchBSwapOrBitReverse(Instruction &I,
                                                       bool MatchBSwaps,
                                                       bool MatchBitReversals) {
   SmallVector<Instruction *, 4> Insts;
   if (!recognizeBSwapOrBitReverseIdiom(&I, MatchBSwaps, MatchBitReversals,
if (match(&I, m_c_Or(m_OneUse(m_And(m_Value(A), m_Value(B))),
     // (? | D) | (A & B) -> (? | (A & B)) | D
     // (? | D) | (A & B) -> (? | (A & B)) | D
     if (match(C, m_OneUse(m_c_And(m_Specific(A), m_Value()))) ||
         match(C, m_OneUse(m_c_And(m_Specific(B), m_Value()))))
       return BinaryOperator::CreateOr(
           Builder.CreateOr(C, Builder.CreateAnd(A, B)), D);
   }
 
+  if (Instruction *Canonicalized = canonicalizeLogicFirst(I, Builder))
+    return Canonicalized;
+
   return nullptr;
 }
 
 /// A ^ B can be specified using other logic ops in a variety of patterns. We
 /// can fold these early and efficiently by morphing an existing instruction.
 static Instruction *foldXorToXor(BinaryOperator &I,
                                  InstCombiner::BuilderTy &Builder) {
   assert(I.getOpcode() == Instruction::Xor);
Instruction *InstCombinerImpl::visitXor(BinaryOperator &I) {
   // Just like we do in other places, we completely avoid the fold
   // for constantexprs, at least to avoid endless combine loop.
   if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_CombineAnd(m_Value(X),
                                                     m_Unless(m_ConstantExpr())),
                                        m_ImmConstant(C1))),
                         m_Value(Y))))
     return BinaryOperator::CreateXor(Builder.CreateXor(X, Y), C1);
 
+  if (Instruction *Canonicalized = canonicalizeLogicFirst(I, Builder))
+    return Canonicalized;
+
   return nullptr;
 }

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

 //===- InstCombineSelect.cpp ----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
foldRoundUpIntegerWithPow2Alignment(SelectInst &SI,
 
   const APInt *LowBitMaskCst;
   if (!match(XLowBits, m_And(m_Specific(X), m_APIntAllowUndef(LowBitMaskCst))))
     return nullptr;
 
   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/and-xor-or.ll

;
   %t6 = and i32 %t4, %t5
   %t7 = icmp ne i32 %t6, 0
   ret i1 %t7
 }
 
 define i32 @canonicalize_logic_first_or_0(i32 %x) {
 ; CHECK-LABEL: define {{[^@]+}}@canonicalize_logic_first_or_0
 ; CHECK-SAME: (i32 [[X:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = add i32 [[X]], 112
-; CHECK-NEXT:    [[R:%.*]] = or i32 [[A]], 15
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[X]], 15
+; CHECK-NEXT:    [[R:%.*]] = add i32 [[TMP1]], 112
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = add i32 %x, 112 ; 01110000
   %r = or i32 %a, 15   ; 00001111
   ret i32 %r
 }
 
 define i32 @canonicalize_logic_first_negative_or_0(i32 %x) {
 ; CHECK-LABEL: define {{[^@]+}}@canonicalize_logic_first_negative_or_0
 ; CHECK-SAME: (i32 [[X:%.*]]) {
 ; CHECK-NEXT:    [[A:%.*]] = add i32 [[X]], 112
 ; CHECK-NEXT:    [[R:%.*]] = or i32 [[A]], 16
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = add i32 %x, 112 ; 01110000
   %r = or i32 %a, 16   ; 00010000
   ret i32 %r
 }
 
 define i8 @canonicalize_logic_first_and_0(i8 %x) {
 ; CHECK-LABEL: define {{[^@]+}}@canonicalize_logic_first_and_0
 ; CHECK-SAME: (i8 [[X:%.*]]) {
-; CHECK-NEXT:    [[B:%.*]] = add i8 [[X]], 48
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[B]], -10
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], -10
+; CHECK-NEXT:    [[R:%.*]] = add i8 [[TMP1]], 48
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %b = add i8 %x, 48    ;  00110000
   %r = and i8 %b, -10   ;  11110110
   ret i8 %r
 }
 
 define i8 @canonicalize_logic_first_negative_and_0(i8 %x) {
 ; CHECK-LABEL: define {{[^@]+}}@canonicalize_logic_first_negative_and_0
 ; CHECK-SAME: (i8 [[X:%.*]]) {
 ; CHECK-NEXT:    [[B:%.*]] = add i8 [[X]], 48
 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[B]], -26
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %b = add i8 %x, 48    ;  00110000
   %r = and i8 %b, -26   ;  11100110
   ret i8 %r
 }
 
 define i8 @canonicalize_logic_first_xor_0(i8 %x) {
 ; CHECK-LABEL: define {{[^@]+}}@canonicalize_logic_first_xor_0
 ; CHECK-SAME: (i8 [[X:%.*]]) {
-; CHECK-NEXT:    [[A:%.*]] = add i8 [[X]], 96
-; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], 31
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[X]], 31
+; CHECK-NEXT:    [[R:%.*]] = add i8 [[TMP1]], 96
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %a = add i8 %x, 96  ; 01100000
   %r = xor i8 %a, 31  ; 00011111
   ret i8 %r
 }
 
 define i8 @canonicalize_logic_first_negative_xor_0(i8 %x) {

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare void @use.i8(i8)
 declare void @use.v2i4(<2 x i4>)
 declare void @use.i1(i1)
 
 declare void @llvm.assume(i1)
 
 ; Basic pattern
 define i8 @t0(i8 %x) {
 ; CHECK-LABEL: @t0(
-; CHECK-NEXT:    [[X_BIASED1:%.*]] = add i8 [[X:%.*]], 15
-; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = and i8 [[X_BIASED1]], -16
+; CHECK-NEXT:    [[X_BIASED:%.*]] = add i8 [[X:%.*]], 15
+; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = and i8 [[X_BIASED]], -16
 ; 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
   %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
   ret i8 %x.roundedup
 }
 
 ; Another alignment is fine
 define i8 @t1(i8 %x) {
 ; CHECK-LABEL: @t1(
-; CHECK-NEXT:    [[X_BIASED1:%.*]] = add i8 [[X:%.*]], 31
-; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = and i8 [[X_BIASED1]], -32
+; CHECK-NEXT:    [[X_BIASED:%.*]] = add i8 [[X:%.*]], 31
+; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = and i8 [[X_BIASED]], -32
 ; 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, 32
   %x.biased.highbits = and i8 %x.biased, -32
   %x.roundedup = select i1 %x.lowbits.are.zero, i8 %x, i8 %x.biased.highbits
   ret i8 %x.roundedup

 }
 
 ; select is commutative
 define i8 @t3_commutative(i8 %x) {
 ; CHECK-LABEL: @t3_commutative(
 ; CHECK-NEXT:    [[X_LOWBITS:%.*]] = and i8 [[X:%.*]], 15
 ; CHECK-NEXT:    [[X_LOWBITS_ARE_NOT_ZERO:%.*]] = icmp ne i8 [[X_LOWBITS]], 0
 ; CHECK-NEXT:    call void @use.i1(i1 [[X_LOWBITS_ARE_NOT_ZERO]])
-; CHECK-NEXT:    [[X_BIASED1:%.*]] = add i8 [[X]], 15
-; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = and i8 [[X_BIASED1]], -16
+; CHECK-NEXT:    [[X_BIASED:%.*]] = add i8 [[X]], 15
+; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = and i8 [[X_BIASED]], -16
 ; CHECK-NEXT:    ret i8 [[X_ROUNDEDUP]]
 ;
   %x.lowbits = and i8 %x, 15
   %x.lowbits.are.not.zero = icmp ne i8 %x.lowbits, 0
   call void @use.i1(i1 %x.lowbits.are.not.zero)
   %x.biased = add i8 %x, 16
   %x.biased.highbits = and i8 %x.biased, -16
   %x.roundedup = select i1 %x.lowbits.are.not.zero, i8 %x.biased.highbits, i8 %x
   ret i8 %x.roundedup
 }
 
 ; Basic splat vector test
 define <2 x i8> @t4_splat(<2 x i8> %x) {
 ; CHECK-LABEL: @t4_splat(
-; CHECK-NEXT:    [[X_BIASED1:%.*]] = add <2 x i8> [[X:%.*]], <i8 15, i8 15>
-; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = and <2 x i8> [[X_BIASED1]], <i8 -16, i8 -16>
+; CHECK-NEXT:    [[X_BIASED:%.*]] = add <2 x i8> [[X:%.*]], <i8 15, i8 15>
+; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = and <2 x i8> [[X_BIASED]], <i8 -16, i8 -16>
 ; CHECK-NEXT:    ret <2 x i8> [[X_ROUNDEDUP]]
 ;
   %x.lowbits = and <2 x i8> %x, <i8 15, i8 15>
   %x.lowbits.are.zero = icmp eq <2 x i8> %x.lowbits, <i8 0, i8 0>
   %x.biased = add <2 x i8> %x, <i8 16, i8 16>
   %x.biased.highbits = and <2 x i8> %x.biased, <i8 -16, i8 -16>
   %x.roundedup = select <2 x i1> %x.lowbits.are.zero, <2 x i8> %x, <2 x i8> %x.biased.highbits
   ret <2 x i8> %x.roundedup
;
   %x.lowbits.are.zero = icmp eq <2 x i8> %x.lowbits, <i8 0, i8 0>
   %x.biased = add <2 x i8> %x, <i8 16, i8 undef>
   %x.biased.highbits = and <2 x i8> %x.biased, <i8 -16, i8 -16>
   %x.roundedup = select <2 x i1> %x.lowbits.are.zero, <2 x i8> %x, <2 x i8> %x.biased.highbits
   ret <2 x i8> %x.roundedup
 }
 define <2 x i8> @t5_splat_undef_0b0100(<2 x i8> %x) {
 ; CHECK-LABEL: @t5_splat_undef_0b0100(
-; CHECK-NEXT:    [[X_BIASED1:%.*]] = add <2 x i8> [[X:%.*]], <i8 15, i8 15>
-; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = and <2 x i8> [[X_BIASED1]], <i8 -16, i8 -16>
+; CHECK-NEXT:    [[X_BIASED:%.*]] = add <2 x i8> [[X:%.*]], <i8 15, i8 15>
+; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = and <2 x i8> [[X_BIASED]], <i8 -16, i8 -16>
 ; CHECK-NEXT:    ret <2 x i8> [[X_ROUNDEDUP]]
 ;
   %x.lowbits = and <2 x i8> %x, <i8 15, i8 15>
   %x.lowbits.are.zero = icmp eq <2 x i8> %x.lowbits, <i8 0, i8 undef>
   %x.biased = add <2 x i8> %x, <i8 16, i8 16>
   %x.biased.highbits = and <2 x i8> %x.biased, <i8 -16, i8 -16>
   %x.roundedup = select <2 x i1> %x.lowbits.are.zero, <2 x i8> %x, <2 x i8> %x.biased.highbits
   ret <2 x i8> %x.roundedup
 }
 define <2 x i8> @t5_splat_undef_0b1000(<2 x i8> %x) {
 ; CHECK-LABEL: @t5_splat_undef_0b1000(
-; CHECK-NEXT:    [[X_BIASED1:%.*]] = add <2 x i8> [[X:%.*]], <i8 15, i8 15>
-; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = and <2 x i8> [[X_BIASED1]], <i8 -16, i8 -16>
+; CHECK-NEXT:    [[X_BIASED:%.*]] = add <2 x i8> [[X:%.*]], <i8 15, i8 15>
+; CHECK-NEXT:    [[X_ROUNDEDUP:%.*]] = and <2 x i8> [[X_BIASED]], <i8 -16, i8 -16>
 ; CHECK-NEXT:    ret <2 x i8> [[X_ROUNDEDUP]]
 ;
   %x.lowbits = and <2 x i8> %x, <i8 15, i8 undef>
   %x.lowbits.are.zero = icmp eq <2 x i8> %x.lowbits, <i8 0, i8 0>
   %x.biased = add <2 x i8> %x, <i8 16, i8 16>
   %x.biased.highbits = and <2 x i8> %x.biased, <i8 -16, i8 -16>
   %x.roundedup = select <2 x i1> %x.lowbits.are.zero, <2 x i8> %x, <2 x i8> %x.biased.highbits
   ret <2 x i8> %x.roundedup
;
   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
 }
 
;
   %a1 = add i8 %x, 4
   %a2 = and i8 %x, 7
   %r = sub i8 %a1, %a2
   ret i8 %r
 }
 
 define <2 x i8> @sub_mask_lowbits_splat_extra_use(<2 x i8> %x, <2 x i8>* %p) {
 ; CHECK-LABEL: @sub_mask_lowbits_splat_extra_use(
-; CHECK-NEXT:    [[A1:%.*]] = add <2 x i8> [[X:%.*]], <i8 -64, i8 -64>
-; CHECK-NEXT:    [[A2:%.*]] = and <2 x i8> [[X]], <i8 10, i8 10>
+; CHECK-NEXT:    [[A2:%.*]] = and <2 x i8> [[X:%.*]], <i8 10, i8 10>
 ; CHECK-NEXT:    store <2 x i8> [[A2]], <2 x i8>* [[P:%.*]], align 2
-; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[A1]], <i8 -11, i8 -11>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X]], <i8 -11, i8 -11>
+; CHECK-NEXT:    [[R:%.*]] = add <2 x i8> [[TMP1]], <i8 -64, i8 -64>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %a1 = add <2 x i8> %x, <i8 192, i8 192> ; 0xc0
   %a2 = and <2 x i8> %x, <i8 10, i8 10>   ; 0x0a
   store <2 x i8> %a2, <2 x i8>* %p
   %r = sub <2 x i8> %a1, %a2
   ret <2 x i8> %r
 }