[InstCombine][InstSimplify] Teach decomposeBitTestICmp to look through truncate instructions

[craig.topper]

Summary

This patch teaches decomposeBitTestICmp to look through truncate instructions on the input to the compare. If a truncate is found it will now return the pre-truncated Value and appropriately extend the APInt mask.

This allows some code to be removed from InstSimplify that was doing this functionality.

This allows InstCombine's bit test combining code to match a pre-truncate Value with the same Value appear with an 'and' on another icmp. Or it allows us to combine a truncate to i16 and a truncate to i8. This also required removing the type check from the beginning of getMaskedTypeForICmpPair, but I believe that's ok because we still have to find two values from the input to each icmp that are equal before we'll do any transformation. So the type check was really just serving as an early out.

There was one user of decomposeBitTestICmp that didn't want to look through truncates, so I've added a flag to prevent that behavior when necessary.

[craig.topper]

Ping

[spatel]

LGTM.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

302–317 ↗

(On Diff #112722)

These are just cleanups? Could go in as a preliminary NFC.

llvm/trunk/include/llvm/Analysis/CmpInstAnalysis.h

namespace llvm {
   /// Return true if both predicates match sign or if at least one of them is an
   /// equality comparison (which is signless).
   bool PredicatesFoldable(CmpInst::Predicate p1, CmpInst::Predicate p2);
 
   /// Decompose an icmp into the form ((X & Mask) pred 0) if possible. The
   /// returned predicate is either == or !=. Returns false if decomposition
   /// fails.
   bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred,
-                            Value *&X, APInt &Mask);
+                            Value *&X, APInt &Mask,
+                            bool LookThroughTrunc = true);
 
 } // end namespace llvm
 
 #endif

llvm/trunk/lib/Analysis/CmpInstAnalysis.cpp

 bool llvm::PredicatesFoldable(ICmpInst::Predicate p1, ICmpInst::Predicate p2) {
   return (CmpInst::isSigned(p1) == CmpInst::isSigned(p2)) ||
          (CmpInst::isSigned(p1) && ICmpInst::isEquality(p2)) ||
          (CmpInst::isSigned(p2) && ICmpInst::isEquality(p1));
 }
 
 bool llvm::decomposeBitTestICmp(Value *LHS, Value *RHS,
                                 CmpInst::Predicate &Pred,
-                                Value *&X, APInt &Mask) {
+                                Value *&X, APInt &Mask, bool LookThruTrunc) {
+  using namespace PatternMatch;
+
   const APInt *C;
-  if (!match(RHS, PatternMatch::m_APInt(C)))
+  if (!match(RHS, m_APInt(C)))
     return false;
 
   switch (Pred) {
   default:
     return false;
   case ICmpInst::ICMP_SLT:
     // X < 0 is equivalent to (X & SignMask) != 0.
     if (!C->isNullValue())
case ICmpInst::ICMP_UGE:
     // X >=u 2^n is equivalent to (X & ~(2^n-1)) != 0.
     if (!C->isPowerOf2())
       return false;
     Mask = -*C;
     Pred = ICmpInst::ICMP_NE;
     break;
   }
 
+  if (LookThruTrunc && match(LHS, m_Trunc(m_Value(X)))) {
+    Mask = Mask.zext(X->getType()->getScalarSizeInBits());
+  } else {
     X = LHS;
+  }
+
   return true;
 }

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

 static Value *simplifySelectWithFakeICmpEq(Value *CmpLHS, Value *CmpRHS,
                                            ICmpInst::Predicate Pred,
                                            Value *TrueVal, Value *FalseVal) {
   Value *X;
   APInt Mask;
   if (!decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, X, Mask))
     return nullptr;
 
-  unsigned BitWidth = TrueVal->getType()->getScalarSizeInBits();
-  if (!BitWidth)
-    return nullptr;
-
-  Value *ExtX;
-  if (match(X, m_Trunc(m_Value(ExtX))) &&
-      (ExtX == TrueVal || ExtX == FalseVal)) {
-    // icmp slt (trunc X), 0  <--> icmp ne (and X, C), 0
-    // icmp sgt (trunc X), -1 <--> icmp eq (and X, C), 0
-    X = ExtX;
-    Mask = Mask.zext(BitWidth);
-  }
-
   return simplifySelectBitTest(TrueVal, FalseVal, X, &Mask,
                                Pred == ICmpInst::ICMP_EQ);
 }
 
 /// Try to simplify a select instruction when its condition operand is an
 /// integer comparison.
 static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal,
                                          Value *FalseVal, const SimplifyQuery &Q,

llvm/trunk/lib/Transforms/InstCombine/InstCombineSelect.cpp

Instruction *InstCombiner::foldSelectInstWithICmp(SelectInst &SI,
   // TODO: Merge this with foldSelectICmpAnd somehow.
   if (CmpLHS->getType()->isIntOrIntVectorTy() &&
       CmpLHS->getType() == TrueVal->getType()) {
     const APInt *C1, *C2;
     if (match(TrueVal, m_APInt(C1)) && match(FalseVal, m_APInt(C2))) {
       ICmpInst::Predicate Pred = ICI->getPredicate();
       Value *X;
       APInt Mask;
-      if (decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, X, Mask)) {
+      if (decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, X, Mask, false)) {
         if (Mask.isSignMask()) {
           assert(X == CmpLHS && "Expected to use the compare input directly");
           assert(ICmpInst::isEquality(Pred) && "Expected equality predicate");
 
           if (Pred == ICmpInst::ICMP_NE)
             std::swap(C1, C2);
 
           // This shift results in either -1 or 0.

llvm/trunk/test/Transforms/InstCombine/bit-checks.ll

;
   %tobool3 = icmp eq i32 %de, %and2
   %and.cond = and i1 %tobool, %tobool3
   %storemerge = select i1 %and.cond, i32 0, i32 1
   ret i32 %storemerge
 }
 
 define i32 @main8(i32 %argc) {
 ; CHECK-LABEL: @main8(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[ARGC:%.*]], 64
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[AND]], 0
-; CHECK-NEXT:    [[TRUNC2:%.*]] = trunc i32 [[ARGC]] to i8
-; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp slt i8 [[TRUNC2]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[TOBOOL]], [[TOBOOL3]]
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[OR_COND]], i32 2, i32 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[ARGC:%.*]], 192
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[TMP2]], i32 1, i32 2
 ; CHECK-NEXT:    ret i32 [[RETVAL_0]]
 ;
   %and = and i32 %argc, 64
   %tobool = icmp ne i32 %and, 0
   %trunc2 = trunc i32 %argc to i8
   %tobool3 = icmp slt i8 %trunc2, 0
   %or.cond = or i1 %tobool, %tobool3
   %retval.0 = select i1 %or.cond, i32 2, i32 1
   ret i32 %retval.0
 }
 
 define i32 @main9(i32 %argc) {
 ; CHECK-LABEL: @main9(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[ARGC:%.*]], 64
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[AND]], 0
-; CHECK-NEXT:    [[TRUNC2:%.*]] = trunc i32 [[ARGC]] to i8
-; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp slt i8 [[TRUNC2]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[TOBOOL]], [[TOBOOL3]]
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[OR_COND]], i32 2, i32 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[ARGC:%.*]], 192
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 192
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[TMP2]], i32 2, i32 1
 ; CHECK-NEXT:    ret i32 [[RETVAL_0]]
 ;
   %and = and i32 %argc, 64
   %tobool = icmp ne i32 %and, 0
   %trunc2 = trunc i32 %argc to i8
   %tobool3 = icmp slt i8 %trunc2, 0
   %or.cond = and i1 %tobool, %tobool3
   %retval.0 = select i1 %or.cond, i32 2, i32 1
   ret i32 %retval.0
 }
 
 define i32 @main10(i32 %argc) {
 ; CHECK-LABEL: @main10(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[ARGC:%.*]], 64
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[TRUNC2:%.*]] = trunc i32 [[ARGC]] to i8
-; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp sgt i8 [[TRUNC2]], -1
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[TOBOOL]], [[TOBOOL3]]
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[OR_COND]], i32 2, i32 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[ARGC:%.*]], 192
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[TMP2]], i32 2, i32 1
 ; CHECK-NEXT:    ret i32 [[RETVAL_0]]
 ;
   %and = and i32 %argc, 64
   %tobool = icmp eq i32 %and, 0
   %trunc2 = trunc i32 %argc to i8
   %tobool3 = icmp sge i8 %trunc2, 0
   %or.cond = and i1 %tobool, %tobool3
   %retval.0 = select i1 %or.cond, i32 2, i32 1
   ret i32 %retval.0
 }
 
 define i32 @main11(i32 %argc) {
 ; CHECK-LABEL: @main11(
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[ARGC:%.*]], 64
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    [[TRUNC2:%.*]] = trunc i32 [[ARGC]] to i8
-; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp sgt i8 [[TRUNC2]], -1
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[TOBOOL]], [[TOBOOL3]]
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[OR_COND]], i32 2, i32 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[ARGC:%.*]], 192
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 192
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[TMP2]], i32 1, i32 2
 ; CHECK-NEXT:    ret i32 [[RETVAL_0]]
 ;
   %and = and i32 %argc, 64
   %tobool = icmp eq i32 %and, 0
   %trunc2 = trunc i32 %argc to i8
   %tobool3 = icmp sge i8 %trunc2, 0
   %or.cond = or i1 %tobool, %tobool3
   %retval.0 = select i1 %or.cond, i32 2, i32 1
   ret i32 %retval.0
 }
 
 define i32 @main12(i32 %argc) {
 ; CHECK-LABEL: @main12(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[ARGC:%.*]] to i16
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp slt i16 [[TRUNC]], 0
-; CHECK-NEXT:    [[TRUNC2:%.*]] = trunc i32 [[ARGC]] to i8
-; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp slt i8 [[TRUNC2]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[TOBOOL]], [[TOBOOL3]]
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[OR_COND]], i32 2, i32 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[ARGC:%.*]], 32896
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[TMP2]], i32 1, i32 2
 ; CHECK-NEXT:    ret i32 [[RETVAL_0]]
 ;
   %trunc = trunc i32 %argc to i16
   %tobool = icmp slt i16 %trunc, 0
   %trunc2 = trunc i32 %argc to i8
   %tobool3 = icmp slt i8 %trunc2, 0
   %or.cond = or i1 %tobool, %tobool3
   %retval.0 = select i1 %or.cond, i32 2, i32 1
   ret i32 %retval.0
 }
 
 define i32 @main13(i32 %argc) {
 ; CHECK-LABEL: @main13(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[ARGC:%.*]] to i16
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp slt i16 [[TRUNC]], 0
-; CHECK-NEXT:    [[TRUNC2:%.*]] = trunc i32 [[ARGC]] to i8
-; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp slt i8 [[TRUNC2]], 0
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[TOBOOL]], [[TOBOOL3]]
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[OR_COND]], i32 2, i32 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[ARGC:%.*]], 32896
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 32896
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[TMP2]], i32 2, i32 1
 ; CHECK-NEXT:    ret i32 [[RETVAL_0]]
 ;
   %trunc = trunc i32 %argc to i16
   %tobool = icmp slt i16 %trunc, 0
   %trunc2 = trunc i32 %argc to i8
   %tobool3 = icmp slt i8 %trunc2, 0
   %or.cond = and i1 %tobool, %tobool3
   %retval.0 = select i1 %or.cond, i32 2, i32 1
   ret i32 %retval.0
 }
 
 define i32 @main14(i32 %argc) {
 ; CHECK-LABEL: @main14(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[ARGC:%.*]] to i16
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp sgt i16 [[TRUNC]], -1
-; CHECK-NEXT:    [[TRUNC2:%.*]] = trunc i32 [[ARGC]] to i8
-; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp sgt i8 [[TRUNC2]], -1
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[TOBOOL]], [[TOBOOL3]]
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[OR_COND]], i32 2, i32 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[ARGC:%.*]], 32896
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[TMP2]], i32 2, i32 1
 ; CHECK-NEXT:    ret i32 [[RETVAL_0]]
 ;
   %trunc = trunc i32 %argc to i16
   %tobool = icmp sge i16 %trunc, 0
   %trunc2 = trunc i32 %argc to i8
   %tobool3 = icmp sge i8 %trunc2, 0
   %or.cond = and i1 %tobool, %tobool3
   %retval.0 = select i1 %or.cond, i32 2, i32 1
   ret i32 %retval.0
 }
 
 define i32 @main15(i32 %argc) {
 ; CHECK-LABEL: @main15(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[ARGC:%.*]] to i16
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp sgt i16 [[TRUNC]], -1
-; CHECK-NEXT:    [[TRUNC2:%.*]] = trunc i32 [[ARGC]] to i8
-; CHECK-NEXT:    [[TOBOOL3:%.*]] = icmp sgt i8 [[TRUNC2]], -1
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[TOBOOL]], [[TOBOOL3]]
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[OR_COND]], i32 2, i32 1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[ARGC:%.*]], 32896
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 32896
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = select i1 [[TMP2]], i32 1, i32 2
 ; CHECK-NEXT:    ret i32 [[RETVAL_0]]
 ;
   %trunc = trunc i32 %argc to i16
   %tobool = icmp sge i16 %trunc, 0
   %trunc2 = trunc i32 %argc to i8
   %tobool3 = icmp sge i8 %trunc2, 0
   %or.cond = or i1 %tobool, %tobool3
   %retval.0 = select i1 %or.cond, i32 2, i32 1
   ret i32 %retval.0
 }