[InstSimplify] Simplify comparison between zext(x) and sext(x)

[nikic]

Summary

This is picking up a loose thread from D69006: We can simplify (zext x) ule (sext x) and (zext x) sge (sext x) to true, with various permutations. Oddly, SCEV knows about this identity, but nothing on the IR level does.

Alive is happy: https://gist.github.com/nikic/7bd5e2ce0dda5ef4c3e712a707f5d0f7

[spatel]

LGTM, but you should adjust at least a couple of the tests to use vector types so we have better coverage.

llvm/lib/Analysis/InstructionSimplify.cpp

if (isa<ZExtInst>(LHS)) {
       if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) {
         if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
           // Compare X and Y.  Note that signed predicates become unsigned.
           if (Value *V = SimplifyICmpInst(ICmpInst::getUnsignedPredicate(Pred),
                                           SrcOp, RI->getOperand(0), Q,
                                           MaxRecurse-1))
             return V;
       }
+      // Fold (zext X) ule (sext X), (zext X) sge (sext X) to true.
+      else if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) {
+        if (SrcOp == RI->getOperand(0)) {
+          if (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_SGE)
+            return ConstantInt::getTrue(ITy);
+          if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_SLT)
+            return ConstantInt::getFalse(ITy);
+        }
+      }
       // Turn icmp (zext X), Cst into a compare of X and Cst if Cst is extended
       // too.  If not, then try to deduce the result of the comparison.
       else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
         // Compute the constant that would happen if we truncated to SrcTy then
         // reextended to DstTy.
         Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
         Constant *RExt = ConstantExpr::getCast(CastInst::ZExt, Trunc, DstTy);
 
if (isa<SExtInst>(LHS)) {
       // same type.
       if (SExtInst *RI = dyn_cast<SExtInst>(RHS)) {
         if (MaxRecurse && SrcTy == RI->getOperand(0)->getType())
           // Compare X and Y.  Note that the predicate does not change.
           if (Value *V = SimplifyICmpInst(Pred, SrcOp, RI->getOperand(0),
                                           Q, MaxRecurse-1))
             return V;
       }
+      // Fold (sext X) uge (zext X), (sext X) sle (zext X) to true.
+      else if (ZExtInst *RI = dyn_cast<ZExtInst>(RHS)) {
+        if (SrcOp == RI->getOperand(0)) {
+          if (Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_SLE)
+            return ConstantInt::getTrue(ITy);
+          if (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_SGT)
+            return ConstantInt::getFalse(ITy);
+        }
+      }
       // Turn icmp (sext X), Cst into a compare of X and Cst if Cst is extended
       // too.  If not, then try to deduce the result of the comparison.
       else if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
         // Compute the constant that would happen if we truncated to SrcTy then
         // reextended to DstTy.
         Constant *Trunc = ConstantExpr::getTrunc(CI, SrcTy);
         Constant *RExt = ConstantExpr::getCast(CastInst::SExt, Trunc, DstTy);
 

llvm/test/Transforms/InstSimplify/cmp_ext.ll

;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp uge i64 %zext, %sext
   ret i1 %cmp
 }
 
 define i1 @zext_ugt_sext(i32 %x) {
 ; CHECK-LABEL: @zext_ugt_sext(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[X:%.*]] to i64
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X]] to i64
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i64 [[ZEXT]], [[SEXT]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp ugt i64 %zext, %sext
   ret i1 %cmp
 }
 
 define i1 @zext_ult_sext(i32 %x) {
 ; CHECK-LABEL: @zext_ult_sext(
 ; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[X:%.*]] to i64
 ; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X]] to i64
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[ZEXT]], [[SEXT]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp ult i64 %zext, %sext
   ret i1 %cmp
 }
 
 define i1 @zext_ule_sext(i32 %x) {
 ; CHECK-LABEL: @zext_ule_sext(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[X:%.*]] to i64
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X]] to i64
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i64 [[ZEXT]], [[SEXT]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp ule i64 %zext, %sext
   ret i1 %cmp
 }
 
 define i1 @zext_sge_sext(i32 %x) {
 ; CHECK-LABEL: @zext_sge_sext(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[X:%.*]] to i64
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X]] to i64
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i64 [[ZEXT]], [[SEXT]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp sge i64 %zext, %sext
   ret i1 %cmp
 }
 
 define i1 @zext_sgt_sext(i32 %x) {
 ; CHECK-LABEL: @zext_sgt_sext(
 ; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[X:%.*]] to i64
 ; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X]] to i64
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[ZEXT]], [[SEXT]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp sgt i64 %zext, %sext
   ret i1 %cmp
 }
 
 define i1 @zext_slt_sext(i32 %x) {
 ; CHECK-LABEL: @zext_slt_sext(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[X:%.*]] to i64
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X]] to i64
-; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[ZEXT]], [[SEXT]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp slt i64 %zext, %sext
   ret i1 %cmp
 }
 
 define i1 @zext_sle_sext(i32 %x) {
 ; CHECK-LABEL: @zext_sle_sext(
 ; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[X:%.*]] to i64
 ; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X]] to i64
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i64 [[ZEXT]], [[SEXT]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp sle i64 %zext, %sext
   ret i1 %cmp
 }
 
 define i1 @sext_uge_zext(i32 %x) {
 ; CHECK-LABEL: @sext_uge_zext(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[X:%.*]] to i64
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X]] to i64
-; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i64 [[SEXT]], [[ZEXT]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp uge i64 %sext, %zext
   ret i1 %cmp
 }
 
 define i1 @sext_ugt_zext(i32 %x) {
 ; CHECK-LABEL: @sext_ugt_zext(
 ; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[X:%.*]] to i64
 ; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X]] to i64
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i64 [[SEXT]], [[ZEXT]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp ugt i64 %sext, %zext
   ret i1 %cmp
 }
 
 define i1 @sext_ult_zext(i32 %x) {
 ; CHECK-LABEL: @sext_ult_zext(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[X:%.*]] to i64
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X]] to i64
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[SEXT]], [[ZEXT]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp ult i64 %sext, %zext
   ret i1 %cmp
 }
 
 define i1 @sext_ule_zext(i32 %x) {
;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp sge i64 %sext, %zext
   ret i1 %cmp
 }
 
 define i1 @sext_sgt_zext(i32 %x) {
 ; CHECK-LABEL: @sext_sgt_zext(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[X:%.*]] to i64
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X]] to i64
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i64 [[SEXT]], [[ZEXT]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp sgt i64 %sext, %zext
   ret i1 %cmp
 }
 
 define i1 @sext_slt_zext(i32 %x) {
 ; CHECK-LABEL: @sext_slt_zext(
 ; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[X:%.*]] to i64
 ; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X]] to i64
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[SEXT]], [[ZEXT]]
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp slt i64 %sext, %zext
   ret i1 %cmp
 }
 
 define i1 @sext_sle_zext(i32 %x) {
 ; CHECK-LABEL: @sext_sle_zext(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext i32 [[X:%.*]] to i64
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext i32 [[X]] to i64
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i64 [[SEXT]], [[ZEXT]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 true
 ;
   %sext = sext i32 %x to i64
   %zext = zext i32 %x to i64
   %cmp = icmp sle i64 %sext, %zext
   ret i1 %cmp
 }
 
 define <4 x i1> @zext_ugt_sext_vec(<4 x i32> %x) {
 ; CHECK-LABEL: @zext_ugt_sext_vec(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext <4 x i32> [[X:%.*]] to <4 x i64>
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext <4 x i32> [[X]] to <4 x i64>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt <4 x i64> [[ZEXT]], [[SEXT]]
-; CHECK-NEXT:    ret <4 x i1> [[CMP]]
+; CHECK-NEXT:    ret <4 x i1> zeroinitializer
 ;
   %sext = sext <4 x i32> %x to <4 x i64>
   %zext = zext <4 x i32> %x to <4 x i64>
   %cmp = icmp ugt <4 x i64> %zext, %sext
   ret <4 x i1> %cmp
 }
 
 define <4 x i1> @sext_ult_zext_vec(<4 x i32> %x) {
 ; CHECK-LABEL: @sext_ult_zext_vec(
-; CHECK-NEXT:    [[SEXT:%.*]] = sext <4 x i32> [[X:%.*]] to <4 x i64>
-; CHECK-NEXT:    [[ZEXT:%.*]] = zext <4 x i32> [[X]] to <4 x i64>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult <4 x i64> [[SEXT]], [[ZEXT]]
-; CHECK-NEXT:    ret <4 x i1> [[CMP]]
+; CHECK-NEXT:    ret <4 x i1> zeroinitializer
 ;
   %sext = sext <4 x i32> %x to <4 x i64>
   %zext = zext <4 x i32> %x to <4 x i64>
   %cmp = icmp ult <4 x i64> %sext, %zext
   ret <4 x i1> %cmp
 }
 
 define i1 @zext_ugt_sext_different_operand(i32 %x, i32 %y) {