[InstCombine] Canonicalize min/max expressions correctly.

[jmolloy]

Summary

This patch introduces a canonical form for min/max idioms where one operand
is extended or truncated. This often happens when the other operand is a
constant. For example:

%1 = icmp slt i32 %a, i32 0
%2 = sext i32 %a to i64
%3 = select i1 %1, i64 %2, i64 0

Would now be canonicalized into:

%1 = icmp slt i32 %a, i32 0
%2 = select i1 %1, i32 %a, i32 0
%3 = sext i32 %2 to i64

This builds upon a patch posted by David Majenemer
(https://www.marc.info/?l=llvm-commits&m=143008038714141&w=2). That pass
passively stopped instcombine from ruining canonical patterns. This
patch additionally actively makes instcombine canonicalize too.

[majnemer]

lib/Transforms/InstCombine/InstCombineSelect.cpp

1169–1176

This looks the same as getICmpPredicateForMinMax.

1177–1182

I'd expect you to use the IRBuilder to construct each instruction up until the last which I'd expect you'd feed into ReplaceInstUsesWith.

[jmolloy]

Hi David,

Thanks - updated patch attached.

Cheers,

James

[majnemer]

lib/Transforms/InstCombine/InstCombineSelect.cpp

1170

Don't we already have a builder called Builder ?

[jmolloy]

Yes. Yes we do.

Patch updated.

[majnemer]

LGTM

lib/Transforms/InstCombine/InstCombineCompares.cpp

if (Op0 == Op1) {
     case FCmpInst::FCMP_OLE:    // True if ordered and less than or equal
       // Canonicalize these to be 'fcmp ord %X, 0.0'.
       I.setPredicate(FCmpInst::FCMP_ORD);
       I.setOperand(1, Constant::getNullValue(Op0->getType()));
       return &I;
     }
   }
 
+  // Test if the FCmpInst 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.
+  if (I.hasOneUse())
+    if (SelectInst *SI = dyn_cast<SelectInst>(*I.user_begin()))
+      if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) ||
+          (SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1))
+        return nullptr;
+
   // Handle fcmp with constant RHS
   if (Constant *RHSC = dyn_cast<Constant>(Op1)) {
     if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
       switch (LHSI->getOpcode()) {
       case Instruction::FPExt: {
         // fcmp (fpext x), C -> fcmp x, (fptrunc C) if fptrunc is lossless
         FPExtInst *LHSExt = cast<FPExtInst>(LHSI);
         ConstantFP *RHSF = dyn_cast<ConstantFP>(RHSC);

lib/Transforms/InstCombine/InstCombineSelect.cpp

if (Instruction *FI = dyn_cast<Instruction>(FalseVal))
               return RI;
             } else
               return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel);
           }
         }
       }
 
   // See if we can fold the select into one of our operands.
-  if (SI.getType()->isIntegerTy()) {
+  if (SI.getType()->isIntOrIntVectorTy()) {
     if (Instruction *FoldI = FoldSelectIntoOp(SI, TrueVal, FalseVal))
       return FoldI;
 
     Value *LHS, *RHS, *LHS2, *RHS2;
-    SelectPatternFlavor SPF = matchSelectPattern(&SI, LHS, RHS);
+    Instruction::CastOps CastOp;
+    SelectPatternFlavor SPF = matchSelectPattern(&SI, LHS, RHS, &CastOp);
+
+    if (SPF) {
+      // Canonicalize so that type casts are outside select patterns.
+      if (LHS->getType()->getPrimitiveSizeInBits() !=
+          SI.getType()->getPrimitiveSizeInBits()) {
+        CmpInst::Predicate Pred = getICmpPredicateForMinMax(SPF);
+        Value *Cmp = Builder->CreateICmp(Pred, LHS, RHS);
+        Value *NewSI = Builder->CreateCast(CastOp,
+                                           Builder->CreateSelect(Cmp, LHS, RHS),
+                                           SI.getType());
+        return ReplaceInstUsesWith(SI, NewSI);
+      }
 
       // MAX(MAX(a, b), a) -> MAX(a, b)
       // MIN(MIN(a, b), a) -> MIN(a, b)
       // MAX(MIN(a, b), a) -> a
       // MIN(MAX(a, b), a) -> a
-    if (SPF) {
       if (SelectPatternFlavor SPF2 = matchSelectPattern(LHS, LHS2, RHS2))
         if (Instruction *R = FoldSPFofSPF(cast<Instruction>(LHS),SPF2,LHS2,RHS2,
                                           SI, SPF, RHS))
           return R;
       if (SelectPatternFlavor SPF2 = matchSelectPattern(RHS, LHS2, RHS2))
         if (Instruction *R = FoldSPFofSPF(cast<Instruction>(RHS),SPF2,LHS2,RHS2,
                                           SI, SPF, LHS))
           return R;
     }
 

lib/Transforms/InstCombine/InstructionCombining.cpp

if (BitCastInst *BC = dyn_cast<BitCastInst>(&Op)) {
 
       // Verify that either both or neither are vectors.
       if ((SrcTy == nullptr) != (DestTy == nullptr)) return nullptr;
       // If vectors, verify that they have the same number of elements.
       if (SrcTy && SrcTy->getNumElements() != DestTy->getNumElements())
         return nullptr;
     }
 
+    // Test if a CmpInst 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.
+    if (auto *CI = dyn_cast<CmpInst>(SI->getCondition())) {
+      if (CI->hasOneUse()) {
+        Value *Op0 = CI->getOperand(0), *Op1 = CI->getOperand(1);
+        if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) ||
+            (SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1))
+          return nullptr;
+      }
+    }
+
     Value *SelectTrueVal = FoldOperationIntoSelectOperand(Op, TV, this);
     Value *SelectFalseVal = FoldOperationIntoSelectOperand(Op, FV, this);
 
     return SelectInst::Create(SI->getCondition(),
                               SelectTrueVal, SelectFalseVal);
   }
   return nullptr;
 }
 
-
 /// FoldOpIntoPhi - Given a binary operator, cast instruction, or select which
 /// has a PHI node as operand #0, see if we can fold the instruction into the
 /// PHI (which is only possible if all operands to the PHI are constants).
 ///
 Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I) {
   PHINode *PN = cast<PHINode>(I.getOperand(0));
   unsigned NumPHIValues = PN->getNumIncomingValues();
   if (NumPHIValues == 0)

test/Transforms/InstCombine/minmax-fold.ll

+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+; CHECK-LABEL: @t1
+; CHECK-NEXT: icmp
+; CHECK-NEXT: select
+; CHECK-NEXT: sext
+define i64 @t1(i32 %a) {
+  ; This is the canonical form for a type-changing min/max.
+  %1 = icmp slt i32 %a, 5
+  %2 = select i1 %1, i32 %a, i32 5
+  %3 = sext i32 %2 to i64
+  ret i64 %3
+}
+
+; CHECK-LABEL: @t2
+; CHECK-NEXT: icmp
+; CHECK-NEXT: select
+; CHECK-NEXT: sext
+define i64 @t2(i32 %a) {
+  ; Check this is converted into canonical form, as above.
+  %1 = icmp slt i32 %a, 5
+  %2 = sext i32 %a to i64
+  %3 = select i1 %1, i64 %2, i64 5
+  ret i64 %3
+}
+
+; CHECK-LABEL: @t3
+; CHECK-NEXT: icmp
+; CHECK-NEXT: select
+; CHECK-NEXT: zext
+define i64 @t3(i32 %a) {
+  ; Same as @t2, with flipped operands and zext instead of sext.
+  %1 = icmp ult i32 %a, 5
+  %2 = zext i32 %a to i64
+  %3 = select i1 %1, i64 5, i64 %2
+  ret i64 %3
+}
+
+; CHECK-LABEL: @t4
+; CHECK-NEXT: icmp
+; CHECK-NEXT: select
+; CHECK-NEXT: trunc
+define i32 @t4(i64 %a) {
+  ; Same again, with trunc.
+  %1 = icmp slt i64 %a, 5
+  %2 = trunc i64 %a to i32
+  %3 = select i1 %1, i32 %2, i32 5
+  ret i32 %3
+}
+
+; CHECK-LABEL: @t5
+; CHECK-NEXT: icmp
+; CHECK-NEXT: zext
+; CHECK-NEXT: select
+define i64 @t5(i32 %a) {
+  ; Same as @t3, but with mismatched signedness between icmp and zext.
+  ; InstCombine should leave this alone.
+  %1 = icmp slt i32 %a, 5
+  %2 = zext i32 %a to i64
+  %3 = select i1 %1, i64 5, i64 %2
+  ret i64 %3
+}
+
+; CHECK-LABEL: @t6
+; CHECK-NEXT: icmp
+; CHECK-NEXT: select
+; CHECK-NEXT: sitofp
+define float @t6(i32 %a) {
+  %1 = icmp slt i32 %a, 0
+  %2 = select i1 %1, i32 %a, i32 0
+  %3 = sitofp i32 %2 to float
+  ret float %3
+}