[InstCombine] Prevent icmp transform that can cause inf loop if part of min/max

[tejohnson]

Summary

I found an infinite loop due to repeatedly canonicalizing a min/max
cmp/select sequence in canonicalizeMinMaxWithConstant due to a
competing transformation on that icmp due to a dominating cmp.

There is already code in the ICmp folder to try to detect and block
ICmp transformations leading to such infinite loops. Prior fixes along
these lines have extracted and moved the offending ICmp transforms below
the check (e.g. r293345 and r315895). Rather than take that approach, I
moved the detection of the possible min/max sequence earlier, and pass a
flag into foldICmpWithDominatingICmp.

Added a test to minmax-fold.ll that will infinitely loop without this
patch. I also added a test (not subject to the min/max) of this
particular ICmp transform to icmp-dom.ll, since it does not appear that
one exists (when I block that transformation completely, nothing
fails!).

Note that I could not figure out how to trigger the infinite loop with
the NE transformation just below the EQ transformation I am guarding.
Which doesn't mean it can't happen, but guarding that one too resulted
in some test case failures (as we blocked some expected
transformations). In general, I'm concerned that this possibility exists
with other ICmp transformations, and that they are being worked around
one by one as they are encountered in the wild, but I don't have
the expertise here to do a broader assessment/fix.

[spatel]

Please check in the test that provides the missing coverage as an NFC preliminary patch.

I agree with all of the comments about the min/max hacks here, and I wish we could untangle this, but it's tough to do without breaking something along the way.

I'd prefer that we IR simplify our way out of this infinite loop instead of looking the other way though. Ie, can we get this in instsimplify using a ConstantRange?
https://rise4fun.com/Alive/dOr

%i2 = icmp sgt i32 %i, 1
%i3 = select i1 %i2, i32 %i, i32 1
%i4 = icmp sgt i32 %i3, 0
=>
%i4 = true

[nikic]

I'd prefer that we IR simplify our way out of this infinite loop instead of looking the other way though. Ie, can we get this in instsimplify using a ConstantRange?

That should be relatively simple to do, we just need to support constant range calculation for min/max flavor selects in computeConstantRange().

[tejohnson]

In D59378#1432514, @nikic wrote:

I'd prefer that we IR simplify our way out of this infinite loop instead of looking the other way though. Ie, can we get this in instsimplify using a ConstantRange?

That should be relatively simple to do, we just need to support constant range calculation for min/max flavor selects in computeConstantRange().

One thing I didn't mention is that this opportunity was exposed only by InstCombine's instruction sinking. I captured the code after sinking to create the test case.

Also, is it reasonable to assume prior passes will transform the code to avoid triggering possible infinite loops in later passes like this? Unless you mean move part of this transformation into InstSimplify and out of InstCombine? If that is a better longer term fix for these issues, it would be good if this one can go in for now to block the infinite loop.

[spatel]

In D59378#1433157, @tejohnson wrote:

In D59378#1432514, @nikic wrote:

I'd prefer that we IR simplify our way out of this infinite loop instead of looking the other way though. Ie, can we get this in instsimplify using a ConstantRange?

That should be relatively simple to do, we just need to support constant range calculation for min/max flavor selects in computeConstantRange().

One thing I didn't mention is that this opportunity was exposed only by InstCombine's instruction sinking. I captured the code after sinking to create the test case.

Also, is it reasonable to assume prior passes will transform the code to avoid triggering possible infinite loops in later passes like this? Unless you mean move part of this transformation into InstSimplify and out of InstCombine?

instsimplify and instcombine have a special relationship: instcombine always calls instsimplify as an analysis on an instruction before trying more general combines (because we can avoid a lot of work if we can kill the instruction first). So that lets us assert that some patterns just don't exist by the time general instcombine is running.

If that is a better longer term fix for these issues, it would be good if this one can go in for now to block the infinite loop.

@nikic - do you have time to work on the instsimplify change? I'm ok if we want to add this patch as an immediate work-around for the hang, but if we need to take that option, let's mark this with a FIXME comment because we know there's a better solution.

[nikic]

@spatel I've created D59506 for the InstSimplify change.

[spatel]

In D59378#1433602, @nikic wrote:

@spatel I've created D59506 for the InstSimplify change.

Thanks! I think we can safely abandon this patch...until we hit the next infinite loop (although that extra regression test in this patch should still be committed).

[tejohnson]

In D59378#1433795, @spatel wrote:

In D59378#1433602, @nikic wrote:

@spatel I've created D59506 for the InstSimplify change.

Thanks! I think we can safely abandon this patch...until we hit the next infinite loop (although that extra regression test in this patch should still be committed).

Thanks. I will commit the extra regression test independently. Before we abandon this, let me make sure the other patch fixes my original infinite loop, which as I mentioned was exposed by the instruction sinking done during InstCombine. I'll take a look when I'm back in the office tomorrow.

[tejohnson]

Committed icmp test in r356463.

Also tried my original reproducer with the InstSimplify patch D59506, and thankfully that does fix it. Abandoning this one.

lib/Transforms/InstCombine/InstCombineCompares.cpp

if (Pred == ICmpInst::ICMP_UGT && match(Op1, m_ConstantInt(CI)) &&
       match(Op0, m_Add(m_Add(m_Value(A), m_Value(B)), m_ConstantInt(CI2))))
     if (Instruction *Res = processUGT_ADDCST_ADD(Cmp, A, B, CI2, CI, *this))
       return Res;
 
   return nullptr;
 }
 
 /// Canonicalize icmp instructions based on dominating conditions.
-Instruction *InstCombiner::foldICmpWithDominatingICmp(ICmpInst &Cmp) {
+Instruction *InstCombiner::foldICmpWithDominatingICmp(ICmpInst &Cmp,
+                                                      bool CmpUsedInMinMax) {
   // This is a cheap/incomplete check for dominance - just match a single
   // predecessor with a conditional branch.
   BasicBlock *CmpBB = Cmp.getParent();
   BasicBlock *DomBB = CmpBB->getSinglePredecessor();
   if (!DomBB)
     return nullptr;
 
   Value *DomCond;
if (match(DomCond, m_ICmp(DomPred, m_Specific(X), m_APInt(DomC))) &&
     // pessimizes codegen by generating branch on zero instruction instead
     // of a test and branch. So we avoid canonicalizing in such situations
     // because test and branch instruction has better branch displacement
     // than compare and branch instruction.
     bool UnusedBit;
     bool IsSignBit = isSignBitCheck(Pred, *C, UnusedBit);
     if (Cmp.isEquality() || (IsSignBit && hasBranchUse(Cmp)))
       return nullptr;
-
+    // This next case can cause an infinite loop if we end up decanonicalizing a
+    // min/max sequence involving a select.
+    if (!CmpUsedInMinMax)
       if (const APInt *EqC = Intersection.getSingleElement())
         return new ICmpInst(ICmpInst::ICMP_EQ, X, Builder.getInt(*EqC));
     if (const APInt *NeC = Difference.getSingleElement())
       return new ICmpInst(ICmpInst::ICMP_NE, X, Builder.getInt(*NeC));
   }
 
   return nullptr;
 }
 
 /// Fold icmp (trunc X, Y), C.
Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
   /// before binary operators.
   if (Op0Cplxity < Op1Cplxity ||
       (Op0Cplxity == Op1Cplxity && swapMayExposeCSEOpportunities(Op0, Op1))) {
     I.swapOperands();
     std::swap(Op0, Op1);
     Changed = true;
   }
 
+  // Test if the ICmpInst instruction is used exclusively by a select as
+  // part of a minimum or maximum operation. If so, refrain from doing
+  // any other folding. This helps out other analyses which understand
+  // non-obfuscated minimum and maximum idioms, such as ScalarEvolution
+  // and CodeGen. And in this case, at least one of the comparison
+  // 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.
+  bool CmpUsedInMinMax = false;
+  if (I.hasOneUse())
+    if (SelectInst *SI = dyn_cast<SelectInst>(I.user_back())) {
+      Value *A, *B;
+      SelectPatternResult SPR = matchSelectPattern(SI, A, B);
+      CmpUsedInMinMax = SPR.Flavor != SPF_UNKNOWN;
+    }
+
   if (Value *V = SimplifyICmpInst(I.getPredicate(), Op0, Op1,
                                   SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 
   // Comparing -val or val with non-zero is the same as just comparing val
   // ie, abs(val) != 0 -> val != 0
   if (I.getPredicate() == ICmpInst::ICMP_NE && match(Op1, m_Zero())) {
     Value *Cond, *SelectTrue, *SelectFalse;
if (Instruction *Res = canonicalizeICmpBool(I, Builder))
       return Res;
 
   if (ICmpInst *NewICmp = canonicalizeCmpWithConstant(I))
     return NewICmp;
 
   if (Instruction *Res = foldICmpWithConstant(I))
     return Res;
 
-  if (Instruction *Res = foldICmpWithDominatingICmp(I))
+  if (Instruction *Res = foldICmpWithDominatingICmp(I, CmpUsedInMinMax))
     return Res;
 
   if (Instruction *Res = foldICmpUsingKnownBits(I))
     return Res;
 
-  // Test if the ICmpInst instruction is used exclusively by a select as
-  // part of a minimum or maximum operation. If so, refrain from doing
-  // any other folding. This helps out other analyses which understand
-  // non-obfuscated minimum and maximum idioms, such as ScalarEvolution
-  // and CodeGen. And in this case, at least one of the comparison
-  // 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)
-        return nullptr;
-    }
+  if (CmpUsedInMinMax)
 
   // 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

lib/Transforms/InstCombine/InstCombineInternal.h

Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP,
                                             ConstantInt *AndCst = nullptr);
   Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
                                     Constant *RHSC);
   Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
                                   ICmpInst::Predicate Pred);
   Instruction *foldICmpWithCastAndCast(ICmpInst &ICI);
 
   Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
-  Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp);
+  Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp, bool CmpUsedInMinMax);
   Instruction *foldICmpWithConstant(ICmpInst &Cmp);
   Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
   Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
   Instruction *foldICmpBinOp(ICmpInst &Cmp);
   Instruction *foldICmpEquality(ICmpInst &Cmp);
   Instruction *foldICmpWithZero(ICmpInst &Cmp);
 
   Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,

test/Transforms/InstCombine/icmp-dom.ll

 
 if.then3:
   br label %return
 
 return:
   ret void
 }
 
+define void @trueblock_cmp_eq(i32 %a, i32 %b) {
+; CHECK-LABEL: @trueblock_cmp_eq(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[A:%.*]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_END:%.*]], label [[RETURN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A]], 1
+; CHECK-NEXT:    br i1 [[CMP1]], label [[IF_THEN3:%.*]], label [[RETURN]]
+; CHECK:       if.then3:
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cmp = icmp sgt i32 %a, 0
+  br i1 %cmp, label %if.end, label %return
+
+if.end:
+  %cmp1 = icmp slt i32 %a, 2
+  br i1 %cmp1, label %if.then3, label %return
+
+if.then3:
+  br label %return
+
+return:
+  ret void
+}
+
 define i1 @trueblock_cmp_is_false(i32 %x, i32 %y) {
 ; CHECK-LABEL: @trueblock_cmp_is_false(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       t:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       f:

test/Transforms/InstCombine/minmax-fold.ll

 ;
   %cmp1 = icmp sgt i32 %i, -255
   %sel1 = select i1 %cmp1, i32 %i, i32 -255
   %cmp2 = icmp slt i32 %i, 0
   %res = select i1 %cmp2, i32 %sel1, i32 0
   ret i32 %res
 }
 
+; Check that there is no infinite loop because of reverse cmp transformation:
+; (icmp slt smax(PositiveA, B) 2) -> (icmp eq B 1)
+define i32 @clamp_check_for_no_infinite_loop3(i32 %i) {
+; CHECK-LABEL: @clamp_check_for_no_infinite_loop3(
+; CHECK-NEXT:    [[I2:%.*]] = icmp sgt i32 [[I:%.*]], 1
+; CHECK-NEXT:    [[I3:%.*]] = select i1 [[I2]], i32 [[I]], i32 1
+; CHECK-NEXT:    [[I4:%.*]] = icmp sgt i32 [[I3]], 0
+; CHECK-NEXT:    br i1 [[I4]], label [[TRUELABEL:%.*]], label [[FALSELABEL:%.*]]
+; CHECK:       truelabel:
+; CHECK-NEXT:    [[I5:%.*]] = icmp slt i32 [[I3]], 2
+; CHECK-NEXT:    [[I6:%.*]] = select i1 [[I5]], i32 [[I3]], i32 2
+; CHECK-NEXT:    [[I7:%.*]] = shl nuw nsw i32 [[I6]], 2
+; CHECK-NEXT:    ret i32 [[I7]]
+; CHECK:       falselabel:
+; CHECK-NEXT:    ret i32 0
+;
+
+  %i2 = icmp sgt i32 %i, 1
+  %i3 = select i1 %i2, i32 %i, i32 1
+  %i4 = icmp sgt i32 %i3, 0
+  br i1 %i4, label %truelabel, label %falselabel
+
+truelabel: ; %i<=1, %i3>0
+  %i5 = icmp slt i32 %i3, 2
+  %i6 = select i1 %i5, i32 %i3, i32 2
+  %i7 = shl nuw nsw i32 %i6, 2
+  ret i32 %i7
+
+falselabel:
+  ret i32 0
+}
+
 ; The next 3 min tests should canonicalize to the same form...and not infinite loop.
 
 define double @PR31751_umin1(i32 %x) {
 ; CHECK-LABEL: @PR31751_umin1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[X:%.*]], 2147483647
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 2147483647
 ; CHECK-NEXT:    [[CONV:%.*]] = sitofp i32 [[SEL]] to double
 ; CHECK-NEXT:    ret double [[CONV]]