[InstCombine] replace fold of an icmp pattern that should never happen with an assert

[spatel]

Summary

While removing a scalar shackle from an icmp fold, I noticed that I couldn't find any tests to trigger this code path.

The 'and' shrinking transform should be handled by InstCombiner::foldCastedBitwiseLogic() or eliminated with InstSimplify. The icmp narrowing is part of InstCombiner::foldICmpWithCastAndCast().

[efriedma]

Are you absolutely sure we can't trigger the assertion? I don't think there's any guarantee instcombine will visit the "and" before the "icmp".

[spatel]

In D24031#530611, @efriedma wrote:

Are you absolutely sure we can't trigger the assertion? I don't think there's any guarantee instcombine will visit the "and" before the "icmp".

Hmm...that would kill my (possibly wrong) mental model of InstCombine as a top-down / greedy machine. Is the comment in AddReachableCodeToWorklist() enough?

// Once we've found all of the instructions to add to instcombine's worklist,
// add them in reverse order.  This way instcombine will visit from the top
// of the function down.

If that's not a valid assumption or if there's some other way that the worklist order doesn't match the instruction order, then I agree we can't assert here.

In that case, I think it should still be valid to remove the block of code (but don't add the assert). The regression test verifies that we get the end result that we want.

[efriedma]

The initial worklist visits from the top down, but that isn't a general guarantee that every operand of an instruction will be completely combined before you visit that instruction. For example, suppose the zext has a second use. If that use is proven dead and erased between the visit to the "and" and the visit to the "icmp", you can trigger the assertion. (Or something along those lines; I haven't actually gone through and proved that particular example works the way I described it.)

[spatel]

In D24031#530868, @efriedma wrote:

The initial worklist visits from the top down, but that isn't a general guarantee that every operand of an instruction will be completely combined before you visit that instruction. For example, suppose the zext has a second use. If that use is proven dead and erased between the visit to the "and" and the visit to the "icmp", you can trigger the assertion. (Or something along those lines; I haven't actually gone through and proved that particular example works the way I described it.)

OK, I'm sufficiently scared that there is a possibility. :)
Do you think it's better to leave the fold in place? Or remove it but not add the assert?

[efriedma]

There isn't any reason to duplicate the combine; instcombine will get to it eventually because it iterates over the function. I would say just remove the combine and don't add an assertion.

[spatel]

Patch updated:
Remove the redundant fold, but don't assert that the base transform has already occurred; we can't be certain about the order.

[efriedma]

LGTM.

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

if (Cmp.isEquality() || (!C2->isNegative() && C1->isNonNegative())) {
       Value *NewAnd = Builder->CreateAnd(
           Cast->getOperand(0), ConstantExpr::getZExt(C2, Cast->getSrcTy()));
       NewAnd->takeName(And);
       return new ICmpInst(Cmp.getPredicate(), NewAnd,
                           ConstantExpr::getZExt(RHS, Cast->getSrcTy()));
     }
   }
 
-  // If the LHS is an AND of a zext, and we have an equality compare, we can
-  // shrink the and/compare to the smaller type, eliminating the cast.
-  if (ZExtInst *Cast = dyn_cast<ZExtInst>(And->getOperand(0))) {
-    IntegerType *Ty = cast<IntegerType>(Cast->getSrcTy());
-    // Make sure we don't compare the upper bits, SimplifyDemandedBits
-    // should fold the icmp to true/false in that case.
-    if (Cmp.isEquality() && C1->getActiveBits() <= Ty->getBitWidth()) {
-      Value *NewAnd = Builder->CreateAnd(Cast->getOperand(0),
-                                         ConstantExpr::getTrunc(C2, Ty));
-      NewAnd->takeName(And);
-      return new ICmpInst(Cmp.getPredicate(), NewAnd,
-                          ConstantExpr::getTrunc(RHS, Ty));
-    }
-  }
-
   if (Instruction *I = foldICmpAndShift(Cmp, And, C1))
     return I;
 
   // (icmp pred (and (or (lshr A, B), A), 1), 0) -->
   //    (icmp pred (and A, (or (shl 1, B), 1), 0))
   //
   // iff pred isn't signed
   {

llvm/trunk/test/Transforms/InstCombine/cast.ll

 ; CHECK-NEXT:    ret <2 x i1> [[D]]
 ;
   %B = trunc <2 x i64> %A to <2 x i32>
   %C = and <2 x i32> %B, <i32 42, i32 42>
   %D = icmp eq <2 x i32> %C, <i32 10, i32 10>
   ret <2 x i1> %D
 }
 
+; Verify that the 'and' was narrowed, the zext was eliminated, and the compare was narrowed
+; even for vectors. Earlier folds should ensure that the icmp(and(zext)) pattern never occurs.
+
+define <2 x i1> @test32vec(<2 x i8> %A) {
+; CHECK-LABEL: @test32vec(
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> %A, <i8 42, i8 42>
+; CHECK-NEXT:    [[D:%.*]] = icmp eq <2 x i8> [[TMP1]], <i8 10, i8 10>
+; CHECK-NEXT:    ret <2 x i1> [[D]]
+;
+  %B = zext <2 x i8> %A to <2 x i16>
+  %C = and <2 x i16> %B, <i16 42, i16 42>
+  %D = icmp eq <2 x i16> %C, <i16 10, i16 10>
+  ret <2 x i1> %D
+}
+
 define i32 @test33(i32 %c1) {
 ; CHECK-LABEL: @test33(
 ; CHECK-NEXT:    ret i32 %c1
 ;
   %x = bitcast i32 %c1 to float           ; <float> [#uses=1]
   %y = bitcast float %x to i32            ; <i32> [#uses=1]
   ret i32 %y
 }