[InstCombine] Update predicate when canonicalizing comparisons in canonicalizeClampLike.

[rickyz]

Summary

canonicalizeClampLike canonicalizes the ule/ugt comparisons to ult/uge,
respectively. However, it does not update the variable holding the
comparison predicate type after doing this. Later code fails to handle
the non-canonical predicate type (specifically, the swap of
ThresholdLowIncl and ThresholdHighExcl when Pred0 has been canonicalized
from ugt to uge). This leads to the miscompile reported in PR53252. Fix
this by updating the comparison predicate after canonicalizing.

Fixes https://github.com/llvm/llvm-project/issues/53252.

[rickyz]

Add assert on predicate type.

[lebedev.ri]

Tests/alive2 only cover the ICMP_UGT case, but not the 3 other affected.

[rickyz]

Rebase.

[rickyz]

I added test coverage of the other cases in D119689 (the parent to this revision).

fwiw, I also verified the fixed transformation with a SAT solver: https://gist.github.com/rickyz/dd9e7c5b73ccf176a80752adf5a0b3f6 (note: doesn't fully model LLVM semantics). It would be cool if these transformations were implemented in some sort of DSL that allowed automatically generating checkers! It looks like bugs like this one are already being found by alive2 + some fuzzing though.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

1381

Why set this if it is never used below here?

llvm/test/Transforms/InstCombine/canonicalize-clamp-like-pattern-between-negative-and-positive-thresholds.ll

214–215

I don't think this variation adds real coverage for the fix. 'uge' will be canonicalized to 'ugt' before we reach the buggy code, so it's the same as the previous test.

Do we need to swap the select operands to exercise the predicate cases further? It's not clear to me from just looking at the code or the existing tests how to hit the bug.

[rickyz]

Rebase/respond to comment.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

1381

This isn't used, but I did it to signal that from this point forward, the predicate has been canonicalized to SLT. I see this as defense in depth against future bugs like this one (kind of like how some C programmers like to set pointer variables to NULL after freeing them). I can see how this could mislead a reader to believe that the variable is used afterwards though.

I'll remove it, since it seems like there's some preference against this.

llvm/test/Transforms/InstCombine/canonicalize-clamp-like-pattern-between-negative-and-positive-thresholds.ll

214–215

Ah, I misinterpreted the comment as asking for tests of different predicates regardless of whether they hit the switch cases in this code (i.e. to provide coverage should canonicalization change at some point). Thinking about this more, I think I also lean towards deleting these tests.

I don't know of a good way to exercise the UGE and ULE cases in the switch on Pred0 - like you mentioned, comparisons against a constant are canonicalized to strict comparisons in canonicalizeCmpWithConstant. The only cases I can think of where this canonicalization will not happen are tautological boundary cases like icmp ule i32 %x, -1 and icmp uge i32 %x, 0 which will instead be simplified to true before we get to canonicalizing the select.

[spatel]

@lebedev.ri mentioned that there may be 4 different patterns to test, but I'm not seeing how that happens. Suggestions?
It seems like we should be able to swap the select operands to make Pred0 become "ule", but then what other conditions are needed to trigger the bug?

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

1381

I'm not opposed to the change, but if you add it, then there should be an assert below. That way, it is clear why we did the update.

[fhahn]

Reverse ping. It would be great to squash this miscompile-bug.

[RKSimon]

@rickyz Are you still looking at this, otherwise would you mind if somebody commandeered the patches to get the bug fixed soon please?

[rickyz]

Apologies for my long-delayed response!

It seems that I was confused in my previous comments about the difficulty of exercising the non-strict equality cases - swapping the select arguments works as expected. D119689 should now contain negative tests for each possible value of Pred0. The two non-strict equality tests pass even without this change, since the bug is only triggered when Pred0 = UGT.

(edit: corrected the last sentence from ULT to UGT)

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

1381

Good idea, done.

[rickyz]

Rebase, add assert on Pred1.

[RKSimon]

llvm/test/Transforms/InstCombine/canonicalize-clamp-like-pattern-between-negative-and-positive-thresholds.ll

189

Remove the FIXME (but please keep the reference to PR53252)

[rickyz]

Remove FIXME comment from incorrect merge.

[rickyz]

Update commit message to clarify conditions for the bug.

Forgot to pass --verbatim last time, sorry for the noise!

[RKSimon]

@spatel Any comments?

[spatel]

I didn't step through to see why the ult/uge variant doesn't trigger the bug, but there's a test now, so LGTM.

[rickyz]

In D119690#3474998, @spatel wrote:

I didn't step through to see why the ult/uge variant doesn't trigger the bug, but there's a test now, so LGTM.

Thanks! If it helps, here is an attempt to explain why the bug is only triggered by UGT:

Pred0 = UGT

Pred0 is canonicalized to UGE here: https://github.com/llvm/llvm-project/blob/5805cfb90127195a9e8aa09716e989f286d0e22b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp#L1307-L1316. Before this change, Pred0 would still equal UGT.

https://github.com/llvm/llvm-project/blob/5805cfb90127195a9e8aa09716e989f286d0e22b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp#L1389-L1390 is supposed to flip the thresholds when the (post-canonicalization) Pred0 is UGE.

The bug does not occur for any other values of Pred0 because:
UGE is canonicalized to UGE, and correctly flips the thresholds
ULT is canonicalized to ULT, which does not require flipping the thresholds
ULE is canonicalized to ULT, which does not require flipping the thresholds

Thanks for the review - I am not an LLVM committer, so can you please land this and D119689? Thanks!

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

static Value *canonicalizeClampLike(SelectInst &Sel0, ICmpInst &Cmp0,
   case ICmpInst::Predicate::ICMP_UGT:
     // We want to canonicalize it to 'ult' or 'uge', so we'll need to increment
     // C0, which again means it must not have any all-ones elements.
     if (!match(C0,
                m_SpecificInt_ICMP(
                    ICmpInst::Predicate::ICMP_NE,
                    APInt::getAllOnes(C0->getType()->getScalarSizeInBits()))))
       return nullptr; // Can't do, have all-ones element[s].
+    Pred0 = ICmpInst::getFlippedStrictnessPredicate(Pred0);
     C0 = InstCombiner::AddOne(C0);
     break;
   default:
     return nullptr; // Unknown predicate.
   }
 
   // Now that we've canonicalized the ICmp, we know the X we expect;
   // the select in other hand should be one-use.
if (!match(C2,
                                   APInt::getSignedMaxValue(
                                       C2->getType()->getScalarSizeInBits()))))
       return nullptr; // Can't do, have signed max element[s].
     C2 = InstCombiner::AddOne(C2);
     LLVM_FALLTHROUGH;
   case ICmpInst::Predicate::ICMP_SGE:
     // Also non-canonical, but here we don't need to change C2,
     // so we don't have any restrictions on C2, so we can just handle it.
+    Pred1 = ICmpInst::Predicate::ICMP_SLT;
     std::swap(ReplacementLow, ReplacementHigh);
     break;
   default:
     return nullptr; // Unknown predicate.
   }
+  assert(Pred1 == ICmpInst::Predicate::ICMP_SLT &&
+         "Unexpected predicate type.");
 
   // The thresholds of this clamp-like pattern.
   auto *ThresholdLowIncl = ConstantExpr::getNeg(C1);
   auto *ThresholdHighExcl = ConstantExpr::getSub(C0, C1);
+
+  assert((Pred0 == ICmpInst::Predicate::ICMP_ULT ||
+          Pred0 == ICmpInst::Predicate::ICMP_UGE) &&
+         "Unexpected predicate type.");
   if (Pred0 == ICmpInst::Predicate::ICMP_UGE)
     std::swap(ThresholdLowIncl, ThresholdHighExcl);
 
   // The fold has a precondition 1: C2 s>= ThresholdLow
   auto *Precond1 = ConstantExpr::getICmp(ICmpInst::Predicate::ICMP_SGE, C2,
                                          ThresholdLowIncl);
   if (!match(Precond1, m_One()))
     return nullptr;

llvm/test/Transforms/InstCombine/canonicalize-clamp-like-pattern-between-negative-and-positive-thresholds.ll

;
   %t0 = icmp slt i32 %x, -17
   %t1 = select i1 %t0, i32 %replacement_low, i32 %replacement_high
   %t2 = add i32 %x, 16
   %t3 = icmp ult i32 %t2, 144
   %r = select i1 %t3, i32 %x, i32 %t1
   ret i32 %r
 }
 
-; FIXME: This is incorrect, see PR53252.
+; Regression test for PR53252.
 define i32 @n10_ugt_slt(i32 %x, i32 %replacement_low, i32 %replacement_high) {
 ; CHECK-LABEL: @n10_ugt_slt(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[X]], 128
-; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP1]], i32 [[REPLACEMENT_LOW:%.*]], i32 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[TMP2]], i32 [[REPLACEMENT_HIGH:%.*]], i32 [[TMP3]]
+; CHECK-NEXT:    [[T0:%.*]] = icmp slt i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[T1:%.*]] = select i1 [[T0]], i32 [[REPLACEMENT_LOW:%.*]], i32 [[REPLACEMENT_HIGH:%.*]]
+; CHECK-NEXT:    [[T2:%.*]] = icmp ugt i32 [[X]], 128
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[T2]], i32 [[X]], i32 [[T1]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %t0 = icmp slt i32 %x, 0
   %t1 = select i1 %t0, i32 %replacement_low, i32 %replacement_high
   %t2 = icmp ugt i32 %x, 128
   %r = select i1 %t2, i32 %x, i32 %t1
   ret i32 %r
 }
 
 define i32 @n11_uge_slt(i32 %x, i32 %replacement_low, i32 %replacement_high) {
 ; CHECK-LABEL: @n11_uge_slt(
 ; CHECK-NEXT:    [[T0:%.*]] = icmp slt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[T1:%.*]] = select i1 [[T0]], i32 [[REPLACEMENT_LOW:%.*]], i32 [[REPLACEMENT_HIGH:%.*]]
 ; CHECK-NEXT:    [[T2:%.*]] = icmp ult i32 [[X]], 129
 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[T2]], i32 [[T1]], i32 [[X]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %t0 = icmp slt i32 %x, 0
   %t1 = select i1 %t0, i32 %replacement_low, i32 %replacement_high
   %t2 = icmp ult i32 %x, 129
   %r = select i1 %t2, i32 %t1, i32 %x
   ret i32 %r
 }
 
 define i32 @n12_ule_slt(i32 %x, i32 %replacement_low, i32 %replacement_high) {
 ; CHECK-LABEL: @n12_ule_slt(
 ; CHECK-NEXT:    [[T0:%.*]] = icmp slt i32 [[X:%.*]], -1
 ; CHECK-NEXT:    [[T1:%.*]] = select i1 [[T0]], i32 [[REPLACEMENT_LOW:%.*]], i32 [[REPLACEMENT_HIGH:%.*]]