[InstCombine] Apply foldICmpUsingKnownBits to early bailout case

[mkazantsev]

Summary

In the patch rL336172, we've sunk foldICmpUsingKnownBits down the pipeline
because it is expensive and sometimes produces instruction patterns that cannot be
analyzed by other parts of optimizer. However the method from which it is invoked
also contains a early bailout (it looks like it is needed to work around some endless
loop corner cases), in which case we don't do any transforms, including foldICmpUsingKnownBits.

There is a case where it is profitable to do foldICmpUsingKnownBits before the
early bailout. In this patch, we add its invocation to this execution path to help
the attached test.

[spatel]

Bailing out on optimizations is a hack, so I'd prefer not to perpetuate that.

I have no context for this patch other than the one test case shown here. I see 2 potential missing folds that would solve that case (and I suspect that we actually have these folds but they are again guarded by min/max bailout hacks):
https://rise4fun.com/Alive/Pe9U

Name: narrow min/max in instcombine
  %z = zext i16 %x to i32
  %c = icmp ult i32 %z, 255
  %s = select i1 %c, i32 %z, i32 255
  %t = trunc i32 %s to i16
  =>
  %c2 = icmp ult i16 %x, 255
  %t = select i1 %c2, i16 %x, i16 255
  
Name: fold min/max in instsimplify
  %a = and i16 %x, 255
  %z = zext i16 %a to i32
  %c = icmp ult i32 %z, 255
  %s = select i1 %c, i32 %z, i32 255
  =>
  %s = %z

Can we add/fix one of those folds instead of trying to solve this in visitICmpInst()?

[mkazantsev]

The context is following: the patch rL336172 has broken this test, and I was asked to fix it. Basically I just restored the behavior that we used to have before this sinking. I would prefer to not introduce any new transforms to InstCombine without dire need because it is fragile, and I am not familiar with it well enough (in particular, I don't understand ordering of particular transforms in many places). So I've chosen a conservative approach (to restore old behavior).

However if you think that this approach is unacceptable, I can try to introduce a new transform and hope that it will not change behavior of other tests.

[spatel]

In D48930#1152437, @mkazantsev wrote:

The context is following: the patch rL336172 has broken this test, and I was asked to fix it.

I assumed that much. :)
But are there any other examples that were given to you? The solution may depend on how varied the breakage is. If it's just this case, then we can probably get by with a solution that doesn't need value tracking.

[spatel]

Here's a partial fix that I think should be universally good (ie, can't cause regressions for any other analysis/pass and has no obvious compile-time impact):
rL336293

[mkazantsev]

In D48930#1152458, @spatel wrote:

In D48930#1152437, @mkazantsev wrote:

The context is following: the patch rL336172 has broken this test, and I was asked to fix it.

I assumed that much. :)
But are there any other examples that were given to you? The solution may depend on how varied the breakage is. If it's just this case, then we can probably get by with a solution that doesn't need value tracking.

It's the only example I have. @aditya_nandakumar, do you have any more tests where it matters?

[aditya_nandakumar]

In D48930#1152669, @mkazantsev wrote:

In D48930#1152458, @spatel wrote:

In D48930#1152437, @mkazantsev wrote:

The context is following: the patch rL336172 has broken this test, and I was asked to fix it.

I assumed that much. :)
But are there any other examples that were given to you? The solution may depend on how varied the breakage is. If it's just this case, then we can probably get by with a solution that doesn't need value tracking.

It's the only example I have. @aditya_nandakumar, do you have any more tests where it matters?

That was the simplest test case where I observed regression. There were quite a few more - I didn't get a chance to look at them all.

[spatel]

In D48930#1152683, @aditya_nandakumar wrote:

In D48930#1152669, @mkazantsev wrote:

In D48930#1152458, @spatel wrote:

In D48930#1152437, @mkazantsev wrote:

The context is following: the patch rL336172 has broken this test, and I was asked to fix it.

I assumed that much. :)
But are there any other examples that were given to you? The solution may depend on how varied the breakage is. If it's just this case, then we can probably get by with a solution that doesn't need value tracking.

It's the only example I have. @aditya_nandakumar, do you have any more tests where it matters?

That was the simplest test case where I observed regression. There were quite a few more - I didn't get a chance to look at them all.

I'd like to see more examples before trying to fix it. If it's just min/max cases that were broken, that can be a specific patch as I showed in the earlier comment, but if we regressed regular icmp patterns, then we might want to redo rL336172 by taking into account metadata rather than rearranging the folds.

[mkazantsev]

I've reverted the original problematic change by rL336410. I think we need to collect tests that degrade from it to make this change properly.

[lebedev.ri]

Hmm, this appears to be stuck.
I feel like marking it as such just to remove it from my review queue.

lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
   // operands has at least one user besides the compare (the select),
   // which would often largely negate the benefit of folding anyway.
   //
   // Do the same for the other patterns recognized by matchSelectPattern.
   if (I.hasOneUse())
     if (SelectInst *SI = dyn_cast<SelectInst>(I.user_back())) {
       Value *A, *B;
       SelectPatternResult SPR = matchSelectPattern(SI, A, B);
-      if (SPR.Flavor != SPF_UNKNOWN)
+      if (SPR.Flavor != SPF_UNKNOWN) {
+        // This may be expensive in compile-time, and transforms based on known
+        // bits can make further analysis more difficult, so we use it as the
+        // last resort if we cannot do anything better.
+        if (Instruction *Res = foldICmpUsingKnownBits(I))
+          return Res;
         return nullptr;
       }
+    }
 
   // Do this after checking for min/max to prevent infinite looping.
   if (Instruction *Res = foldICmpWithZero(I))
     return Res;
 
   // FIXME: We only do this after checking for min/max to prevent infinite
   // looping caused by a reverse canonicalization of these patterns for min/max.
   // FIXME: The organization of folds is a mess. These would naturally go into

test/Transforms/InstCombine/max_known_bits.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine < %s | FileCheck %s
-; TODO: The entire thing should be folded to and i16 %0, 255.
+; The entire thing should be folded to and i16 %0, 255.
 
 define i16 @foo(i16 )  {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[TMP0:%.*]], 255
-; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[TMP1]] to i32
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i32 [[TMP2]], 255
-; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i32 [[TMP2]], i32 255
-; CHECK-NEXT:    [[TMP5:%.*]] = trunc i32 [[TMP4]] to i16
-; CHECK-NEXT:    [[TMP6:%.*]] = and i16 [[TMP5]], 255
-; CHECK-NEXT:    ret i16 [[TMP6]]
+; CHECK-NEXT:    ret i16 [[TMP1]]
 ;
 entry:
   %1 = and i16 %0, 255
   %2 = zext i16 %1 to i32
   %3 = icmp ult i32 %2, 255
   %4 = select i1 %3, i32 %2, i32 255
   %5 = trunc i32 %4 to i16
   %6 = and i16 %5, 255
   ret i16 %6
 }