[InstCombine] Don't break the min/max idiom by mutating compares.

[aemerson]

Summary

This is motivated by the troubles in D143624 where a change in inlining
order resulted in instcombine seeing more code and then breaking the
smin idiom. The problem is that code like this:

%shr = ashr i32 %mul, 15
%cmp4.i = icmp sgt i32 %shr, 32767
%switch.i = icmp ult i1 %cmp4.i, true
%spec.select.i = select i1 %switch.i, i32 %shr, i32 32767

has the %cmp4.i being modified so that the idiom doesn't match. This patch
extends some of the attempts to detect a potential idiom by looking for the
"not" idiom of the %switch.i icmp in between the first cmp and the select.

This however isn't quite enough. After we prevent the first breakage, another
combine mutates the constant operand and condition of %cmp4.i, and unfortunately
that again prevents the idiom-preserving bail out code from working. To
get around this we re-use some of the canonicalization code that undoes that
transform to again prevent breakage.

I don't feel good about any of this.

[nikic]

Yeah, no, this is too much of a hack. At that point it would be better to add a special case to the SPF matcher to handle this case.

[aemerson]

We can prevent the pattern breaking with D149918 instead of this.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/CmpInstAnalysis.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Transforms/InstCombine/InstCombiner.h"
 
 using namespace llvm;
 using namespace PatternMatch;
 
Instruction *InstCombinerImpl::visitICmpInst(ICmpInst &I) {
   // 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())) {
+  if (I.hasOneUse()) {
+    Instruction *User = I.user_back();
+    if (SelectInst *SI = dyn_cast<SelectInst>(User)) {
       Value *A, *B;
       SelectPatternResult SPR = matchSelectPattern(SI, A, B);
       if (SPR.Flavor != SPF_UNKNOWN)
         return nullptr;
-    }
+      // Maybe a canonicalization that happens later will make it
+      // possible to form minmax, don't give up yet.
+      if (canReuseConstantFromSelectInComparison(*SI, I))
+        return nullptr;
+    }
+    // Sometimes we may have an intermediate instruction between the compare
+    // and the use. If this is a form of `not` then look through it.
+    ICmpInst::Predicate P;
+    if (match(User, m_ICmp(P, m_Specific(&I), m_Specific(Builder.getTrue())))) {
+      if (P == CmpInst::Predicate::ICMP_ULT ||
+          P == CmpInst::Predicate::ICMP_UGT)
+        return nullptr;
+    }
+    if (match(User, m_Not(m_Specific(&I))))
+      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

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

private:
 
   // Optimize one of these forms:
   //   and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
   //   or i1 Op, SI  / select i1 Op, i1 true, i1 SI  (if IsAnd = false)
   // into simplier select instruction using isImpliedCondition.
   Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
                                                  bool IsAnd);
 
+  bool canReuseConstantFromSelectInComparison(SelectInst &Sel, ICmpInst &Cmp);
+
 public:
   /// Create and insert the idiom we use to indicate a block is unreachable
   /// without having to rewrite the CFG from within InstCombine.
   void CreateNonTerminatorUnreachable(Instruction *InsertAt) {
     auto &Ctx = InsertAt->getContext();
     new StoreInst(ConstantInt::getTrue(Ctx),
                   PoisonValue::get(Type::getInt1PtrTy(Ctx)),
                   InsertAt);

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

 // If we have
 //  %cmp = icmp [canonical predicate] i32 %x, C0
 //  %r = select i1 %cmp, i32 %y, i32 C1
 // Where C0 != C1 and %x may be different from %y, see if the constant that we
 // will have if we flip the strictness of the predicate (i.e. without changing
 // the result) is identical to the C1 in select. If it matches we can change
 // original comparison to one with swapped predicate, reuse the constant,
 // and swap the hands of select.
+// If IC is null then this will return &Sel if it's possible to do the combine,
+// without actually performing it.
 static Instruction *
 tryToReuseConstantFromSelectInComparison(SelectInst &Sel, ICmpInst &Cmp,
-                                         InstCombinerImpl &IC) {
+                                         InstCombinerImpl *IC) {
   ICmpInst::Predicate Pred;
   Value *X;
   Constant *C0;
   if (!match(&Cmp, m_OneUse(m_ICmp(
                        Pred, m_Value(X),
                        m_CombineAnd(m_AnyIntegralConstant(), m_Constant(C0))))))
     return nullptr;
 
auto FlippedStrictness =
       InstCombiner::getFlippedStrictnessPredicateAndConstant(Pred, C0);
   if (!FlippedStrictness)
     return nullptr;
 
   // If said constant doesn't match either, then there is no hope,
   if (!MatchesSelectValue(FlippedStrictness->second))
     return nullptr;
 
+  if (!IC)
+    return &Sel;
+
   // It matched! Lets insert the new comparison just before select.
-  InstCombiner::BuilderTy::InsertPointGuard Guard(IC.Builder);
-  IC.Builder.SetInsertPoint(&Sel);
+  InstCombiner::BuilderTy::InsertPointGuard Guard(IC->Builder);
+  IC->Builder.SetInsertPoint(&Sel);
 
   Pred = ICmpInst::getSwappedPredicate(Pred); // Yes, swapped.
-  Value *NewCmp = IC.Builder.CreateICmp(Pred, X, FlippedStrictness->second,
+  Value *NewCmp = IC->Builder.CreateICmp(Pred, X, FlippedStrictness->second,
                                          Cmp.getName() + ".inv");
-  IC.replaceOperand(Sel, 0, NewCmp);
+  IC->replaceOperand(Sel, 0, NewCmp);
   Sel.swapValues();
   Sel.swapProfMetadata();
-
   return &Sel;
 }
 
+bool InstCombinerImpl::canReuseConstantFromSelectInComparison(SelectInst &Sel,
+                                                              ICmpInst &Cmp) {
+  return tryToReuseConstantFromSelectInComparison(Sel, Cmp, nullptr);
+}
+
 static Instruction *foldSelectZeroOrOnes(ICmpInst *Cmp, Value *TVal,
                                          Value *FVal,
                                          InstCombiner::BuilderTy &Builder) {
   if (!Cmp->hasOneUse())
     return nullptr;
 
   const APInt *CmpC;
   if (!match(Cmp->getOperand(1), m_APIntAllowUndef(CmpC)))
Instruction *InstCombinerImpl::foldSelectInstWithICmp(SelectInst &SI,
 
   if (Value *V = foldSelectInstWithICmpConst(SI, ICI, Builder))
     return replaceInstUsesWith(SI, V);
 
   if (Value *V = canonicalizeClampLike(SI, *ICI, Builder))
     return replaceInstUsesWith(SI, V);
 
   if (Instruction *NewSel =
-          tryToReuseConstantFromSelectInComparison(SI, *ICI, *this))
+          tryToReuseConstantFromSelectInComparison(SI, *ICI, this))
     return NewSel;
 
   bool Changed = adjustMinMax(SI, *ICI);
 
   if (Value *V = foldSelectICmpAnd(SI, ICI, Builder))
     return replaceInstUsesWith(SI, V);
 
   // NOTE: if we wanted to, this is where to detect integer MIN/MAX

llvm/test/Transforms/InstCombine/prevent-minmax-pattern-break.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt < %s -p instcombine -S | FileCheck %s
+
+; Ensure that we don't break the smin idiom and generate the llvm.smin intrinsic call.
+
+define void @arm_mult_q15(ptr %pSrcA, ptr %pSrcB, ptr noalias %pDst, i32 %blockSize) {
+; CHECK-LABEL: define void @arm_mult_q15
+; CHECK-SAME: (ptr [[PSRCA:%.*]], ptr [[PSRCB:%.*]], ptr noalias [[PDST:%.*]], i32 [[BLOCKSIZE:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
+; CHECK:       while.cond:
+; CHECK-NEXT:    [[PSRCB_ADDR_0:%.*]] = phi ptr [ [[PSRCB]], [[ENTRY:%.*]] ], [ [[INCDEC_PTR1:%.*]], [[WHILE_BODY:%.*]] ]
+; CHECK-NEXT:    [[PDST_ADDR_0:%.*]] = phi ptr [ [[PDST]], [[ENTRY]] ], [ [[INCDEC_PTR4:%.*]], [[WHILE_BODY]] ]
+; CHECK-NEXT:    [[PSRCA_ADDR_0:%.*]] = phi ptr [ [[PSRCA]], [[ENTRY]] ], [ [[INCDEC_PTR:%.*]], [[WHILE_BODY]] ]
+; CHECK-NEXT:    [[BLKCNT_0:%.*]] = phi i32 [ [[BLOCKSIZE]], [[ENTRY]] ], [ [[DEC:%.*]], [[WHILE_BODY]] ]
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[BLKCNT_0]], 0
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[WHILE_END:%.*]], label [[WHILE_BODY]]
+; CHECK:       while.body:
+; CHECK-NEXT:    [[INCDEC_PTR]] = getelementptr inbounds i16, ptr [[PSRCA_ADDR_0]], i64 1
+; CHECK-NEXT:    [[TMP0:%.*]] = load i16, ptr [[PSRCA_ADDR_0]], align 2
+; CHECK-NEXT:    [[CONV:%.*]] = sext i16 [[TMP0]] to i32
+; CHECK-NEXT:    [[INCDEC_PTR1]] = getelementptr inbounds i16, ptr [[PSRCB_ADDR_0]], i64 1
+; CHECK-NEXT:    [[TMP1:%.*]] = load i16, ptr [[PSRCB_ADDR_0]], align 2
+; CHECK-NEXT:    [[CONV2:%.*]] = sext i16 [[TMP1]] to i32
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[CONV]], [[CONV2]]
+; CHECK-NEXT:    [[SHR:%.*]] = ashr i32 [[MUL]], 15
+; CHECK-NEXT:    [[SPEC_SELECT_I:%.*]] = call i32 @llvm.smin.i32(i32 [[SHR]], i32 32767)
+; CHECK-NEXT:    [[CONV3:%.*]] = trunc i32 [[SPEC_SELECT_I]] to i16
+; CHECK-NEXT:    [[INCDEC_PTR4]] = getelementptr inbounds i16, ptr [[PDST_ADDR_0]], i64 1
+; CHECK-NEXT:    store i16 [[CONV3]], ptr [[PDST_ADDR_0]], align 2
+; CHECK-NEXT:    [[DEC]] = add i32 [[BLKCNT_0]], -1
+; CHECK-NEXT:    br label [[WHILE_COND]]
+; CHECK:       while.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.body, %entry
+  %pSrcB.addr.0 = phi ptr [ %pSrcB, %entry ], [ %incdec.ptr1, %while.body ]
+  %pDst.addr.0 = phi ptr [ %pDst, %entry ], [ %incdec.ptr4, %while.body ]
+  %pSrcA.addr.0 = phi ptr [ %pSrcA, %entry ], [ %incdec.ptr, %while.body ]
+  %blkCnt.0 = phi i32 [ %blockSize, %entry ], [ %dec, %while.body ]
+  %cmp.not = icmp eq i32 %blkCnt.0, 0
+  br i1 %cmp.not, label %while.end, label %while.body
+
+while.body:                                       ; preds = %while.cond
+  %incdec.ptr = getelementptr inbounds i16, ptr %pSrcA.addr.0, i32 1
+  %0 = load i16, ptr %pSrcA.addr.0, align 2
+  %conv = sext i16 %0 to i32
+  %incdec.ptr1 = getelementptr inbounds i16, ptr %pSrcB.addr.0, i32 1
+  %1 = load i16, ptr %pSrcB.addr.0, align 2
+  %conv2 = sext i16 %1 to i32
+  %mul = mul nsw i32 %conv, %conv2
+  %shr = ashr i32 %mul, 15
+  %cmp4.i = icmp sgt i32 %shr, 32767
+  %switch.i = icmp ult i1 %cmp4.i, true
+  %spec.select.i = select i1 %switch.i, i32 %shr, i32 32767
+  %conv3 = trunc i32 %spec.select.i to i16
+  %incdec.ptr4 = getelementptr inbounds i16, ptr %pDst.addr.0, i32 1
+  store i16 %conv3, ptr %pDst.addr.0, align 2
+  %dec = add i32 %blkCnt.0, -1
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  ret void
+}
+