[InstCombine] foldXorOfICmps(): don't give up on non-single-use ICmp's if all users are freely invertible

[lebedev.ri]

Summary

This is rather unconventional..

As the comment there says, we don't have much folds for xor-of-icmps,
we try to turn them into an and-of-icmps, for which we have plenty of folds.
But if the ICmp we need to invert is not single-use - we give up.

As discussed in https://reviews.llvm.org/D65148#1603922,
we may have a non-canonical CLAMP pattern, with bit match and
select-of-threshold that we'll potentially clamp.
As it can be seen in canonicalize-clamp-with-select-of-constant-threshold-pattern.ll,
out of all 8 variations of the pattern, only two are not canonicalized into
the variant with and+icmp instead of bit math.
The reason is because the ICmp we need to invert is not single-use - we give up.

We indeed can't perform this fold at will, the general rule is that
we should not increase instruction count in InstCombine,

But we wouldn't end up increasing instruction count if we can adapt every other
user to the inverted value. This way the not we create will get folded,
and in the end the instruction count did not increase.

For that, of course, we need to look at the users of a Value,
which is again rather unconventional for InstCombine :S

Thus i'm proposing to be a little bit more insistive in foldXorOfICmps().
The alternatives would be to not create that not, but add duplicate code to
manually invert all users; or to add some even less general combine to handle
some more specific pattern[s].

[lebedev.ri]

Rebased, NFC.
Ping.

[lebedev.ri]

Ping.

[spatel]

Sorry for the delay in looking at this. What do the motivating examples look like for codegen? Are we getting the optimal codegen for these clamps, or would we better off trying to create min/max and/or saturating intrinsics?

Make sure I didn't typo this translation, but I think I'm seeing extra instructions for vectors with this transform on x86 and aarch64:

define <4 x i32> @t4_select_cond_xor_v0_vec_before(<4 x i32> %X) {
  %need_to_clamp_positive = icmp sgt <4 x i32> %X, <i32 32767, i32 32767, i32 32767, i32 32767>
  %dont_need_to_clamp_negative = icmp sgt <4 x i32> %X, <i32 -32768, i32 -32768, i32 -32768, i32 -32768>
  %clamp_limit = select <4 x i1> %need_to_clamp_positive, <4 x i32> <i32 32767, i32 32767, i32 32767, i32 32767>, <4 x i32> <i32 -32768, i32 -32768, i32 -32768, i32 -32768>
  %dont_need_to_clamp = xor <4 x i1> %need_to_clamp_positive, %dont_need_to_clamp_negative
  %R = select <4 x i1> %dont_need_to_clamp, <4 x i32> %X, <4 x i32> %clamp_limit
  ret <4 x i32> %R
}

define <4 x i32> @t4_select_cond_xor_v0_vec_after(<4 x i32> %X) {
  %t1 = icmp slt <4 x i32> %X, <i32 32768, i32 32768, i32 32768, i32 32768>
  %t2 = select <4 x i1> %t1, <4 x i32> <i32 -32768, i32 -32768, i32 -32768, i32 -32768>, <4 x i32> <i32 32767, i32 32767, i32 32767, i32 32767>
  %t3 = add <4 x i32> %X, <i32 32767, i32 32767, i32 32767, i32 32767>
  %t4 = icmp ult <4 x i32> %t3, <i32 65535, i32 65535, i32 65535, i32 65535>
  %t5 = select <4 x i1> %t4, <4 x i32> %X, <4 x i32> %t2
  ret <4 x i32> %t5
}

[lebedev.ri]

In D65530#1625321, @spatel wrote:

Sorry for the delay in looking at this. What do the motivating examples look like for codegen? Are we getting the optimal codegen for these clamps, or would we better off trying to create min/max and/or saturating intrinsics?

We most certainly do *NOT* get optimal codegen with these patterns, as noted in https://reviews.llvm.org/D65148#1603922 by @dmgreen.
We need to fold them into traditional clamp pattern, D65765 does just that.

The motivation behind *this* patch is that out of all the variations of this pattern that we can have (see canonicalize-clamp-with-select-of-constant-threshold-pattern.ll),
only this single pattern is not folded into the same form all the other variants are.
So if we don't do this, i will need to redo D65765 to do also handle this non-canonical pattern, and i don't think it would be the correct solution.

...

[lebedev.ri]

In D65530#1625321, @spatel wrote:

Make sure I didn't typo this translation, but I think I'm seeing extra instructions for vectors with this transform on x86 and aarch64:
...

Sure, but that is irrelevant. D65765 improves upon both of them:
https://godbolt.org/z/-UIddL

[spatel]

In D65530#1625331, @lebedev.ri wrote:

In D65530#1625321, @spatel wrote:

Make sure I didn't typo this translation, but I think I'm seeing extra instructions for vectors with this transform on x86 and aarch64:
...

Sure, but that is irrelevant. D65765 improves upon both of them:
https://godbolt.org/z/-UIddL

Ok, but I wouldn't call it irrelevant if this patch is viewed/committed independently. For example, if D65765 had to be reverted, we'd probably want to revert this too, so there's no perf regression potential.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2654–2658

'V can be' -> 'V be'

2654–2659

Is there a way to share logic with the existing IsFreeToInvert()? Can we put them next to each other in 1 file, so it's easier to discover that both exist?

2725

it's -> its

2732

inversible -> invertible

[lebedev.ri]

Addressed review notes, thanks for taking a look!

In D65530#1625426, @spatel wrote:

In D65530#1625331, @lebedev.ri wrote:

In D65530#1625321, @spatel wrote:

Make sure I didn't typo this translation, but I think I'm seeing extra instructions for vectors with this transform on x86 and aarch64:
...

Sure, but that is irrelevant. D65765 improves upon both of them:
https://godbolt.org/z/-UIddL

Ok, but I wouldn't call it irrelevant if this patch is viewed/committed independently. For example, if D65765 had to be reverted, we'd probably want to revert this too, so there's no perf regression potential.

Right.
What i meant is, every other variant of the pattern in canonicalize-clamp-with-select-of-constant-threshold-pattern.ll
is already 'folded'/bad, so so this only handles an edge-case, not generally worsens things.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2654–2659

Right, i should have put it next to IsFreeToInvert().

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

176

Use the current formatting: canFreely...
It should be safe to update IsFreeToInvert() too for uniformity.

[lebedev.ri]

In D65530#1626886, @spatel wrote:

LGTM

Thank you for the review!

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if ((match(Op0, m_Or(m_Value(A), m_Value(B))) &&
        match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B))))) ||
       (match(Op0, m_And(m_Value(A), m_Value(B))) &&
        match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B))))))
     return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
 
   return nullptr;
 }
 
-Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS) {
+Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS,
+                                    BinaryOperator &I) {
+  assert(I.getOpcode() == Instruction::Xor && I.getOperand(0) == LHS &&
+         I.getOperand(1) == RHS && "Should be 'xor' with these operands");
+
   if (predicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) {
     if (LHS->getOperand(0) == RHS->getOperand(1) &&
         LHS->getOperand(1) == RHS->getOperand(0))
       LHS->swapOperands();
     if (LHS->getOperand(0) == RHS->getOperand(0) &&
         LHS->getOperand(1) == RHS->getOperand(1)) {
       // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
       Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
       unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS);
Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS,
   //
   // This is based on a truth table definition of xor:
   // X ^ Y --> (X | Y) & !(X & Y)
   if (Value *OrICmp = SimplifyBinOp(Instruction::Or, LHS, RHS, SQ)) {
     // TODO: If OrICmp is true, then the definition of xor simplifies to !(X&Y).
     // TODO: If OrICmp is false, the whole thing is false (InstSimplify?).
     if (Value *AndICmp = SimplifyBinOp(Instruction::And, LHS, RHS, SQ)) {
       // TODO: Independently handle cases where the 'and' side is a constant.
-      if (OrICmp == LHS && AndICmp == RHS && RHS->hasOneUse()) {
-        // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS
-        RHS->setPredicate(RHS->getInversePredicate());
-        return Builder.CreateAnd(LHS, RHS);
+      ICmpInst *X = nullptr, *Y = nullptr;
+      if (OrICmp == LHS && AndICmp == RHS) {
+        // (LHS | RHS) & !(LHS & RHS) --> LHS & !RHS  --> X & !Y
+        X = LHS;
+        Y = RHS;
+      }
+      if (OrICmp == RHS && AndICmp == LHS) {
+        // !(LHS & RHS) & (LHS | RHS) --> !LHS & RHS  --> !Y & X
+        X = RHS;
+        Y = LHS;
+      }
+      if (X && Y && (Y->hasOneUse() || CanFreelyInvertAllUsersOf(Y, &I))) {
+        // Invert the predicate of 'Y', thus inverting its output.
+        Y->setPredicate(Y->getInversePredicate());
+        // So, are there other uses of Y?
+        if (!Y->hasOneUse()) {
+          // We need to adapt other uses of Y though. Get a value that matches
+          // the original value of Y before inversion. While this increases
+          // immediate instruction count, we have just ensured that all the
+          // users are freely-invertible, so that 'not' *will* get folded away.
+          BuilderTy::InsertPointGuard Guard(Builder);
+          // Set insertion point to right after the Y.
+          Builder.SetInsertPoint(Y->getParent(), ++(Y->getIterator()));
+          Value *NotY = Builder.CreateNot(Y, Y->getName() + ".not");
+          // Replace all uses of Y (excluding the one in NotY!) with NotY.
+          Y->replaceUsesWithIf(NotY,
+                               [NotY](Use &U) { return U.getUser() != NotY; });
         }
-      if (OrICmp == RHS && AndICmp == LHS && LHS->hasOneUse()) {
-        // !(LHS & RHS) & (LHS | RHS) --> !LHS & RHS
-        LHS->setPredicate(LHS->getInversePredicate());
+        // All done.
         return Builder.CreateAnd(LHS, RHS);
       }
     }
   }
 
   return nullptr;
 }
 
Instruction *InstCombiner::visitXor(BinaryOperator &I) {
   // (A & ~B) ^ ~A -> ~(A & B)
   // (~B & A) ^ ~A -> ~(A & B)
   if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
       match(Op1, m_Not(m_Specific(A))))
     return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
 
   if (auto *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
     if (auto *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
-      if (Value *V = foldXorOfICmps(LHS, RHS))
+      if (Value *V = foldXorOfICmps(LHS, RHS, I))
         return replaceInstUsesWith(I, V);
 
   if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
     return CastedXor;
 
   // Canonicalize a shifty way to code absolute value to the common pattern.
   // There are 4 potential commuted variants. Move the 'ashr' candidate to Op1.
   // We're relying on the fact that we only do this transform when the shift has

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

 static inline Constant *SubOne(Constant *C) {
   return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
 }
 
 /// Return true if the specified value is free to invert (apply ~ to).
 /// This happens in cases where the ~ can be eliminated.  If WillInvertAllUses
 /// is true, work under the assumption that the caller intends to remove all
 /// uses of V and only keep uses of ~V.
+///
+/// See also: CanFreelyInvertAllUsersOf()
 static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) {
   // ~(~(X)) -> X.
   if (match(V, m_Not(m_Value())))
     return true;
 
   // Constants can be considered to be not'ed values.
   if (match(V, m_AnyIntegralConstant()))
     return true;
static inline bool IsFreeToInvert(Value *V, bool WillInvertAllUses) {
 
   // Selects with invertible operands are freely invertible
   if (match(V, m_Select(m_Value(), m_Not(m_Value()), m_Not(m_Value()))))
     return WillInvertAllUses;
 
   return false;
 }
 
+/// Given i1 V, can every user of V be freely adapted if V is changed to !V ?
+///
+/// See also: IsFreeToInvert()
+static inline bool CanFreelyInvertAllUsersOf(Value *V, Value *IgnoredUser) {
+  // Look at every user of V.
+  for (User *U : V->users()) {
+    if (U == IgnoredUser)
+      continue; // Don't consider this user.
+
+    auto *I = cast<Instruction>(U);
+    switch (I->getOpcode()) {
+    case Instruction::Select:
+    case Instruction::Br:
+      break; // Free to invert by swapping true/false values/destinations.
+    case Instruction::Xor: // Can invert 'xor' if it's a 'not', by ignoring it.
+      if (!match(I, m_Not(m_Value())))
+        return false; // Not a 'not'.
+      break;
+    default:
+      return false; // Don't know, likely not freely invertible.
+    }
+    // So far all users were free to invert...
+  }
+  return true; // Can freely invert all users!
+}
+
 /// Some binary operators require special handling to avoid poison and undefined
 /// behavior. If a constant vector has undef elements, replace those undefs with
 /// identity constants if possible because those are always safe to execute.
 /// If no identity constant exists, replace undef with some other safe constant.
 static inline Constant *getSafeVectorConstantForBinop(
       BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant) {
   assert(In->getType()->isVectorTy() && "Not expecting scalars here");
 
private:
   /// CI1->getSrcTy() to CI2->getDstTy().
   ///
   /// \see CastInst::isEliminableCastPair
   Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
                                             const CastInst *CI2);
 
   Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
   Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &CxtI);
-  Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS);
+  Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &I);
 
   /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
   /// NOTE: Unlike most of instcombine, this returns a Value which should
   /// already be inserted into the function.
   Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd);
 
   Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
                                        bool JoinedByAnd, Instruction &CxtI);

llvm/test/Transforms/InstCombine/canonicalize-clamp-with-select-of-constant-threshold-pattern.ll

;
   %R = select i1 %need_to_clamp, i32 %clamp_limit, i32 %X
   ret i32 %R
 }
 
 ;-------------------------------------------------------------------------------
 
 define i32 @t4_select_cond_xor_v0(i32 %X) {
 ; CHECK-LABEL: @t4_select_cond_xor_v0(
-; CHECK-NEXT:    [[NEED_TO_CLAMP_POSITIVE:%.*]] = icmp sgt i32 [[X:%.*]], 32767
-; CHECK-NEXT:    [[DONT_NEED_TO_CLAMP_NEGATIVE:%.*]] = icmp sgt i32 [[X]], -32768
-; CHECK-NEXT:    [[CLAMP_LIMIT:%.*]] = select i1 [[NEED_TO_CLAMP_POSITIVE]], i32 32767, i32 -32768
-; CHECK-NEXT:    [[DONT_NEED_TO_CLAMP:%.*]] = xor i1 [[NEED_TO_CLAMP_POSITIVE]], [[DONT_NEED_TO_CLAMP_NEGATIVE]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[DONT_NEED_TO_CLAMP]], i32 [[X]], i32 [[CLAMP_LIMIT]]
+; CHECK-NEXT:    [[NEED_TO_CLAMP_POSITIVE:%.*]] = icmp slt i32 [[X:%.*]], 32768
+; CHECK-NEXT:    [[CLAMP_LIMIT:%.*]] = select i1 [[NEED_TO_CLAMP_POSITIVE]], i32 -32768, i32 32767
+; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], 32767
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[X_OFF]], 65535
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 [[CLAMP_LIMIT]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %need_to_clamp_positive = icmp sgt i32 %X, 32767
   %dont_need_to_clamp_negative = icmp sgt i32 %X, -32768
   %clamp_limit = select i1 %need_to_clamp_positive, i32 32767, i32 -32768
   %dont_need_to_clamp = xor i1 %need_to_clamp_positive, %dont_need_to_clamp_negative
   %R = select i1 %dont_need_to_clamp, i32 %X, i32 %clamp_limit
   ret i32 %R
;
   %clamp_limit = select i1 %dont_need_to_clamp_negative, i32 32767, i32 -32768
   %dont_need_to_clamp = xor i1 %need_to_clamp_positive, %dont_need_to_clamp_negative
   %R = select i1 %dont_need_to_clamp, i32 %X, i32 %clamp_limit
   ret i32 %R
 }
 
 define i32 @t5_select_cond_xor_v2(i32 %X) {
 ; CHECK-LABEL: @t5_select_cond_xor_v2(
-; CHECK-NEXT:    [[DONT_NEED_TO_CLAMP_POSITIVE:%.*]] = icmp slt i32 [[X:%.*]], 32768
-; CHECK-NEXT:    [[NEED_TO_CLAMP_NEGATIVE:%.*]] = icmp slt i32 [[X]], -32767
-; CHECK-NEXT:    [[CLAMP_LIMIT:%.*]] = select i1 [[NEED_TO_CLAMP_NEGATIVE]], i32 -32768, i32 32767
-; CHECK-NEXT:    [[DONT_NEED_TO_CLAMP:%.*]] = xor i1 [[DONT_NEED_TO_CLAMP_POSITIVE]], [[NEED_TO_CLAMP_NEGATIVE]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[DONT_NEED_TO_CLAMP]], i32 [[X]], i32 [[CLAMP_LIMIT]]
+; CHECK-NEXT:    [[NEED_TO_CLAMP_NEGATIVE:%.*]] = icmp sgt i32 [[X:%.*]], -32768
+; CHECK-NEXT:    [[CLAMP_LIMIT:%.*]] = select i1 [[NEED_TO_CLAMP_NEGATIVE]], i32 32767, i32 -32768
+; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], 32767
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[X_OFF]], 65535
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 [[CLAMP_LIMIT]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %dont_need_to_clamp_positive = icmp sle i32 %X, 32767
   %need_to_clamp_negative = icmp sle i32 %X, -32768
   %clamp_limit = select i1 %need_to_clamp_negative, i32 -32768, i32 32767
   %dont_need_to_clamp = xor i1 %dont_need_to_clamp_positive, %need_to_clamp_negative
   %R = select i1 %dont_need_to_clamp, i32 %X, i32 %clamp_limit
   ret i32 %R

llvm/test/Transforms/InstCombine/xor-of-icmps-with-extra-uses.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; These xor-of-icmps could be replaced with and-of-icmps, but %cond0 has extra
 ; uses, so we don't consider it, even though some cases are freely invertible.
 
 ; %cond0 is extra-used in select, which is freely invertible.
 define i1 @v0_select_of_consts(i32 %X, i32* %selected) {
 ; CHECK-LABEL: @v0_select_of_consts(
-; CHECK-NEXT:    [[COND0:%.*]] = icmp sgt i32 [[X:%.*]], 32767
-; CHECK-NEXT:    [[COND1:%.*]] = icmp sgt i32 [[X]], -32768
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[COND0]], i32 32767, i32 -32768
+; CHECK-NEXT:    [[COND0:%.*]] = icmp slt i32 [[X:%.*]], 32768
+; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[COND0]], i32 -32768, i32 32767
 ; CHECK-NEXT:    store i32 [[SELECT]], i32* [[SELECTED:%.*]], align 4
-; CHECK-NEXT:    [[RES:%.*]] = xor i1 [[COND0]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], 32767
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[X_OFF]], 65535
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %cond0 = icmp sgt i32 %X, 32767
   %cond1 = icmp sgt i32 %X, -32768
   %select = select i1 %cond0, i32 32767, i32 -32768
   store i32 %select, i32* %selected
   %res = xor i1 %cond0, %cond1
   ret i1 %res
 }
 define i1 @v1_select_of_var_and_const(i32 %X, i32 %Y, i32* %selected) {
 ; CHECK-LABEL: @v1_select_of_var_and_const(
-; CHECK-NEXT:    [[COND0:%.*]] = icmp sgt i32 [[X:%.*]], 32767
-; CHECK-NEXT:    [[COND1:%.*]] = icmp sgt i32 [[X]], -32768
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[COND0]], i32 [[Y:%.*]], i32 -32768
+; CHECK-NEXT:    [[COND0:%.*]] = icmp slt i32 [[X:%.*]], 32768
+; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[COND0]], i32 -32768, i32 [[Y:%.*]]
 ; CHECK-NEXT:    store i32 [[SELECT]], i32* [[SELECTED:%.*]], align 4
-; CHECK-NEXT:    [[RES:%.*]] = xor i1 [[COND0]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], 32767
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[X_OFF]], 65535
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %cond0 = icmp sgt i32 %X, 32767
   %cond1 = icmp sgt i32 %X, -32768
   %select = select i1 %cond0, i32 %Y, i32 -32768
   store i32 %select, i32* %selected
   %res = xor i1 %cond0, %cond1
   ret i1 %res
 }
 define i1 @v2_select_of_const_and_var(i32 %X, i32 %Y, i32* %selected) {
 ; CHECK-LABEL: @v2_select_of_const_and_var(
-; CHECK-NEXT:    [[COND0:%.*]] = icmp sgt i32 [[X:%.*]], 32767
-; CHECK-NEXT:    [[COND1:%.*]] = icmp sgt i32 [[X]], -32768
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[COND0]], i32 32767, i32 [[Y:%.*]]
+; CHECK-NEXT:    [[COND0:%.*]] = icmp slt i32 [[X:%.*]], 32768
+; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[COND0]], i32 [[Y:%.*]], i32 32767
 ; CHECK-NEXT:    store i32 [[SELECT]], i32* [[SELECTED:%.*]], align 4
-; CHECK-NEXT:    [[RES:%.*]] = xor i1 [[COND0]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], 32767
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[X_OFF]], 65535
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %cond0 = icmp sgt i32 %X, 32767
   %cond1 = icmp sgt i32 %X, -32768
   %select = select i1 %cond0, i32 32767, i32 %Y
   store i32 %select, i32* %selected
   %res = xor i1 %cond0, %cond1
   ret i1 %res
 }
 
 ; Branch is also freely invertible
 define i1 @v3_branch(i32 %X, i32* %dst0, i32* %dst1) {
 ; CHECK-LABEL: @v3_branch(
 ; CHECK-NEXT:  begin:
-; CHECK-NEXT:    [[COND0:%.*]] = icmp sgt i32 [[X:%.*]], 32767
-; CHECK-NEXT:    [[COND1:%.*]] = icmp sgt i32 [[X]], -32768
-; CHECK-NEXT:    br i1 [[COND0]], label [[BB0:%.*]], label [[BB1:%.*]]
+; CHECK-NEXT:    [[COND0:%.*]] = icmp slt i32 [[X:%.*]], 32768
+; CHECK-NEXT:    br i1 [[COND0]], label [[BB1:%.*]], label [[BB0:%.*]]
 ; CHECK:       bb0:
 ; CHECK-NEXT:    store i32 0, i32* [[DST0:%.*]], align 4
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    store i32 0, i32* [[DST1:%.*]], align 4
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[RES:%.*]] = xor i1 [[COND0]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], 32767
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X_OFF]], 65535
+; CHECK-NEXT:    ret i1 [[TMP0]]
 ;
 begin:
   %cond0 = icmp sgt i32 %X, 32767
   %cond1 = icmp sgt i32 %X, -32768
   br i1 %cond0, label %bb0, label %bb1
 bb0:
   store i32 0, i32* %dst0
   br label %end
 bb1:
   store i32 0, i32* %dst1
   br label %end
 end:
   %res = xor i1 %cond0, %cond1
   ret i1 %res
 }
 
 ; Can invert 'not'.
 define i1 @v4_not_store(i32 %X, i1* %not_cond) {
 ; CHECK-LABEL: @v4_not_store(
-; CHECK-NEXT:    [[COND0:%.*]] = icmp sgt i32 [[X:%.*]], 32767
-; CHECK-NEXT:    [[NOT_COND0:%.*]] = xor i1 [[COND0]], true
-; CHECK-NEXT:    store i1 [[NOT_COND0]], i1* [[NOT_COND:%.*]], align 1
-; CHECK-NEXT:    [[COND1:%.*]] = icmp sgt i32 [[X]], -32768
-; CHECK-NEXT:    [[RES:%.*]] = xor i1 [[COND0]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    [[COND0:%.*]] = icmp slt i32 [[X:%.*]], 32768
+; CHECK-NEXT:    store i1 [[COND0]], i1* [[NOT_COND:%.*]], align 1
+; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], 32767
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[X_OFF]], 65535
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %cond0 = icmp sgt i32 %X, 32767
   %not_cond0 = xor i1 %cond0, -1
   store i1 %not_cond0, i1* %not_cond
   %cond1 = icmp sgt i32 %X, -32768
   %select = select i1 %cond0, i32 32767, i32 -32768
   %res = xor i1 %cond0, %cond1
   ret i1 %res
 }
 
 ; All extra uses are invertible.
 define i1 @v5_select_and_not(i32 %X, i32 %Y, i32* %selected, i1* %not_cond) {
 ; CHECK-LABEL: @v5_select_and_not(
-; CHECK-NEXT:    [[COND0:%.*]] = icmp sgt i32 [[X:%.*]], 32767
-; CHECK-NEXT:    [[COND1:%.*]] = icmp sgt i32 [[X]], -32768
-; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[COND0]], i32 32767, i32 [[Y:%.*]]
-; CHECK-NEXT:    [[NOT_COND0:%.*]] = xor i1 [[COND0]], true
-; CHECK-NEXT:    store i1 [[NOT_COND0]], i1* [[NOT_COND:%.*]], align 1
+; CHECK-NEXT:    [[COND0:%.*]] = icmp slt i32 [[X:%.*]], 32768
+; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[COND0]], i32 [[Y:%.*]], i32 32767
+; CHECK-NEXT:    store i1 [[COND0]], i1* [[NOT_COND:%.*]], align 1
 ; CHECK-NEXT:    store i32 [[SELECT]], i32* [[SELECTED:%.*]], align 4
-; CHECK-NEXT:    [[RES:%.*]] = xor i1 [[COND0]], [[COND1]]
-; CHECK-NEXT:    ret i1 [[RES]]
+; CHECK-NEXT:    [[X_OFF:%.*]] = add i32 [[X]], 32767
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[X_OFF]], 65535
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %cond0 = icmp sgt i32 %X, 32767
   %cond1 = icmp sgt i32 %X, -32768
   %select = select i1 %cond0, i32 32767, i32 %Y
   %not_cond0 = xor i1 %cond0, -1
   store i1 %not_cond0, i1* %not_cond
   store i32 %select, i32* %selected
   %res = xor i1 %cond0, %cond1