[ValueTracking] Allow min/max detection to see through casts.

[jmolloy]

Summary

This teaches the min/max idiom detector in ValueTracking to see through
casts such as SExt/ZExt/Trunc. SCEV can already do this, so we're bringing
non-SCEV analyses up to the same level.

The returned LHS/RHS will not match the type of the original SelectInst
any more, so a CastOp is returned too to inform the caller how to
convert to the SelectInst's type.

UIToFP/FPToSI are not yet handled - that would require this function to be able to return floating point min/max, which I intend to do in the future.

No in-tree users yet; this will be used by InstCombine in a followup and will be tested there.

[reames]

No obvious problems spotted, but I'd like to see the updated diff after comments applied so that I can be more confident of the change before signing off.

lib/Analysis/ValueTracking.cpp

3211

Missing context here makes it hard to review change. Please upload full diff.

3279

I find it odd that these routines don't already exist. Have you looked at various subclasses of Constant and ConstantExpr?

If they don't already exist, I'd prefer to see them placed as members on Constant or an appropriate class.

3344

This loop usage is a bit confusing. It would probably be clearer to extract out a helper function and call it twice.

[majnemer]

lib/Analysis/ValueTracking.cpp

3279

Right, how is this different from ConstantExpr::getTrunc ?

3290–3292

No need for the extra indentation here, just stick return nullptr at the end of the function.

3295

Likewise, why can't this be ConstantExpr::getSExt

3311

Likewise, why can't this be ConstantExpr::getZExt

3327

It'd be nice if V was const qualified.

3344

Agreed.

[jmolloy]

Hi Philip, David,

Thanks for your review! I've updated the diff. I looked for public versions of those helper functions but couldn't find them - I didn't think to check ConstantExpr! :(

All comments addressed. The only thing I'm not too keen on is the const_cast, I feel like raptors will come and attack me whenever it's used. But without it the "const" goes viral and takes over everything, including the return values "LHS" and "RHS".

James

[majnemer]

In D9748#172701, @jmolloy wrote:

Hi Philip, David,

Thanks for your review! I've updated the diff. I looked for public versions of those helper functions but couldn't find them - I didn't think to check ConstantExpr! :(

All comments addressed. The only thing I'm not too keen on is the const_cast, I feel like raptors will come and attack me whenever it's used. But without it the "const" goes viral and takes over everything, including the return values "LHS" and "RHS".

James

In that case, let's just skip the const.

lib/Analysis/ValueTracking.cpp

3291–3293

Would it be equally correct to phrase this like:

if (ICI->isSigned())
  if (Constant *Trunc = ConstantExpr::getTrunc(Op2, Castee->getType());
    return Trunc;

?

3297–3299

!ICI->isSigned() will return true for NE/EQ. Perhaps:

if (ICI->isUnsigned())
  if (Constant *Trunc = ConstantExpr::getTrunc(Op2, Castee->getType());
    return Trunc;

3302–3304

You may want to wrap the call to getIntegerCast with if (!ICI->isEquality()) so you won't create the cast if the comparison is == or !=.

3328–3332

I think it'd be more clear if you switched those cast<Instruction> over to cast<CastInst>.

[jmolloy]

Hi David,

Those comments make sense. Thanks!

I've changed !isSigned() to isUnsigned(), but instead of checking for !equality everywhere I've just added a quick bailout right at the start.

Cheers,

James

[jmolloy]

.... and now with conflict markers removed ...

[majnemer]

include/llvm/Analysis/ValueTracking.h

294

Please clang-format this.

lib/Analysis/ValueTracking.cpp

3279–3303

TrueVal and FalseVal are not accurate names and the switch/case structure is a little superfluous. Castee->getType() is just Op1->getSrcTy().

I think the following is equivalent:

static Constant *lookThroughCast(ICmpInst *ICI, Value *V1, Value *V2,
                                 Instruction::CastOps *CastOp) {
  auto *CI = dyn_cast<CastInst>(V1);
  auto *C = dyn_cast<Constant>(V2);
  if (!CI || !C)
    return nullptr;

  *CastOp = CI->getOpcode();

  if ((isa<SExtInst>(CI) && ICI->isSigned()) ||
      (isa<ZExtInst>(CI) && ICI->isUnsigned()))
    return ConstantExpr::getTrunc(C, CI->getSrcTy());

  if (isa<TruncInst>(CI))
    return ConstantExpr::getIntegerCast(C, CI->getSrcTy(), ICI->isSigned());

  return nullptr;
}

3321–3322

I don't think this will compile, CI isn't defined.

3330

No need to make this else if.

[jmolloy]

Hi David,

Apologies for the broken code; I have a bunch of patches downstream in my git history and messed up slightly with the rebase.

I've tested this patch in isolation and it compiles and works fine. Thanks for all the suggestions so far, I'm slightly embarrassed that you've essentially rewritten this entire patch for me but your version looks far superior!

Cheers,

James

[majnemer]

LGTM

include/llvm/Analysis/ValueTracking.h

 // computations have.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_VALUETRACKING_H
 #define LLVM_ANALYSIS_VALUETRACKING_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/IR/Instruction.h"
 #include "llvm/Support/DataTypes.h"
 
 namespace llvm {
   class Value;
   class Instruction;
   class APInt;
   class DataLayout;
   class StringRef;
enum SelectPatternFlavor {
     SPF_UMIN,                   // Unsigned minimum
     SPF_SMAX,                   // Signed maximum
     SPF_UMAX,                   // Unsigned maximum
     SPF_ABS,                    // Absolute value
     SPF_NABS                    // Negated absolute value
   };
   /// Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind
   /// and providing the out parameter results if we successfully match.
-  SelectPatternFlavor matchSelectPattern(Value *V, Value *&LHS, Value *&RHS);
+  ///
+  /// If CastOp is not nullptr, also match MIN/MAX idioms where the type does
+  /// not match that of the original select. If this is the case, the cast
+  /// operation (one of Trunc,SExt,Zext) that must be done to transform the
+  /// type of LHS and RHS into the type of V is returned in CastOp.
+  ///
+  /// For example:
+  ///   %1 = icmp slt i32 %a, i32 4
+  ///   %2 = sext i32 %a to i64
+  ///   %3 = select i1 %1, i64 %2, i64 4
+  ///
+  /// -> LHS = %a, RHS = i32 4, *CastOp = Instruction::SExt
+  ///
+  SelectPatternFlavor matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
+                                         Instruction::CastOps *CastOp = nullptr);
 
 } // end namespace llvm
 
 #endif

lib/Analysis/ValueTracking.cpp

if (LHSKnownNonNegative && RHSKnownNonNegative) {
       // Create a simple add instruction, and insert it into the struct.
       return OverflowResult::NeverOverflows;
     }
   }
 
   return OverflowResult::MayOverflow;
 }
 
-SelectPatternFlavor llvm::matchSelectPattern(Value *V,
+static SelectPatternFlavor matchSelectPattern(ICmpInst::Predicate Pred,
+                                              Value *CmpLHS, Value *CmpRHS,
+                                              Value *TrueVal, Value *FalseVal,
                                               Value *&LHS, Value *&RHS) {
-  SelectInst *SI = dyn_cast<SelectInst>(V);
-  if (!SI) return SPF_UNKNOWN;
-
-  ICmpInst *ICI = dyn_cast<ICmpInst>(SI->getCondition());
-  if (!ICI) return SPF_UNKNOWN;
-
-  ICmpInst::Predicate Pred = ICI->getPredicate();
-  Value *CmpLHS = ICI->getOperand(0);
-  Value *CmpRHS = ICI->getOperand(1);
-  Value *TrueVal = SI->getTrueValue();
-  Value *FalseVal = SI->getFalseValue();
-
   LHS = CmpLHS;
   RHS = CmpRHS;
 
   // (icmp X, Y) ? X : Y
   if (TrueVal == CmpLHS && FalseVal == CmpRHS) {
     switch (Pred) {
     default: return SPF_UNKNOWN; // Equality.
     case ICmpInst::ICMP_UGT:
if (const auto *C2 = dyn_cast<ConstantInt>(FalseVal)) {
       }
     }
   }
 
   // TODO: (X > 4) ? X : 5   -->  (X >= 5) ? X : 5  -->  MAX(X, 5)
 
   return SPF_UNKNOWN;
 }
+
+static Constant *lookThroughCast(ICmpInst *CmpI, Value *V1, Value *V2,
+                                 Instruction::CastOps *CastOp) {
+  CastInst *CI = dyn_cast<CastInst>(V1);
+  Constant *C = dyn_cast<Constant>(V2);
+  if (!CI || !C)
+    return nullptr;
+  *CastOp = CI->getOpcode();
+
+  if ((isa<SExtInst>(CI) && CmpI->isSigned()) ||
+      (isa<ZExtInst>(CI) && CmpI->isUnsigned()))
+    return ConstantExpr::getTrunc(C, CI->getSrcTy());
+
+  if (isa<TruncInst>(CI))
+    return ConstantExpr::getIntegerCast(C, CI->getSrcTy(), CmpI->isSigned());
+
+  return nullptr;
+}
+
+SelectPatternFlavor llvm::matchSelectPattern(Value *V,
+                                             Value *&LHS, Value *&RHS,
+                                             Instruction::CastOps *CastOp) {
+  SelectInst *SI = dyn_cast<SelectInst>(V);
+  if (!SI) return SPF_UNKNOWN;
+
+  ICmpInst *CmpI = dyn_cast<ICmpInst>(SI->getCondition());
+  if (!CmpI) return SPF_UNKNOWN;
+
+  ICmpInst::Predicate Pred = CmpI->getPredicate();
+  Value *CmpLHS = CmpI->getOperand(0);
+  Value *CmpRHS = CmpI->getOperand(1);
+  Value *TrueVal = SI->getTrueValue();
+  Value *FalseVal = SI->getFalseValue();
+
+  // Bail out early.
+  if (CmpI->isEquality())
+    return SPF_UNKNOWN;
+
+  // Deal with type mismatches.
+  if (CastOp && CmpLHS->getType() != TrueVal->getType()) {
+    if (Constant *C = lookThroughCast(CmpI, TrueVal, FalseVal, CastOp))
+      return ::matchSelectPattern(Pred, CmpLHS, CmpRHS,
+                                  cast<CastInst>(TrueVal)->getOperand(0), C,
+                                  LHS, RHS);
+    if (Constant *C = lookThroughCast(CmpI, FalseVal, TrueVal, CastOp))
+      return ::matchSelectPattern(Pred, CmpLHS, CmpRHS,
+                                  C, cast<CastInst>(FalseVal)->getOperand(0),
+                                  LHS, RHS);
+  }
+  return ::matchSelectPattern(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal,
+                              LHS, RHS);
+}