Improve lookThroughCast function.

[ArturGainullin]

Summary

When we have the following case:

%c = cmp iN %x, a
%t = trunc iN %y to iK
%sel = select i1 %c, iK %t, iK b

We could possibly match only min/max pattern after looking through cast.
So it is more profitable if widened b constant will be equal a. That is
why extend b using upper bits from a.

Also description for lookTroughCast function was added.

[ArturGainullin]

Ping.

[spatel]

This reminds me that I haven't revisited D26556...in ~6 months.

If we implement what Eli suggested there (matching the size of a select to a cmp of its condition operand), then we won't need to do this?

[ArturGainullin]

I have checked that patch from D26556 doesn't work for the case described in this review.
D26556 is about folding extension instruction into select.
I.e. in case of the following pattern:

s = select Cond, C1, C2 
sext s

sext operation is eliminated and C1, C2 constants are widened.

Also it perfroms the following folding when we have trunc before select and zext after select:

zext (select Cond, C, (trunc X)) --> select Cond, C', (and X, Mask)
zext (select Cond, (trunc X), C) --> select Cond, (and X, Mask), C'

While patch from this review is intended to cover more cases when we can match min/max pattern and as a result of canonicalization move cast operation out of min/max.
So I think that we still need this.

[ArturGainullin]

I have read more carefully your comment. As far as I understood in D26556 you want to change the process of decision making for function that folds cast operation into select.
According to suggestion from Eli you should try to match the size of a select to a cmp of its condition operand as a final result.
Necessary to mention that this function doesn't make cast folding when select is min/max and it is called only when select is an operand of cast operation.

Current differential revision try to solve this case:

p = cmp i32 x, a
x' = trunc i32 x to i8
select i1 p, i8 x', i8 a'

where select is not an operand of the cast and where we have min/max operation as a result.
So here we try to match min/max pattern with further canonicalization (sinking of trunc). Reverse hoisting will not be performed because foldCastIntoSelect doesn't touch min/max idioms.

[spatel]

In D38536#898338, @ArturGainullin wrote:

I have read more carefully your comment. As far as I understood in D26556 you want to change the process of decision making for function that folds cast operation into select.
According to suggestion from Eli you should try to match the size of a select to a cmp of its condition operand as a final result.

That's right. The patch I was imagining would be something like this:

Index: lib/Transforms/InstCombine/InstCombineSelect.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineSelect.cpp	(revision 315902)
+++ lib/Transforms/InstCombine/InstCombineSelect.cpp	(working copy)
@@ -748,6 +748,22 @@
     }
   }
 
+  // If the select uses a truncated operand of the compare, try to select using the
+  // same value as the compare. This may then be matched as a canonical min/max
+  // op, and it usually produces better codegen for vector types because the
+  // compare result is often used as a mask value for the select.
+  Constant *CmpC, *SelC;
+  if (match(CmpRHS, m_Constant(CmpC)) && match(FalseVal, m_Constant(SelC)) &&
+      match(TrueVal, m_Trunc(m_Specific(CmpLHS)))) {
+    Type *NarrowType = SelC->getType();
+    if (ConstantExpr::getTrunc(CmpC, NarrowType) == SelC) {
+       // select (icmp Pred X, CmpC), (trunc X), SelC -->
+       // trunc (select (icmp Pred X, CmpC), X, CmpC
+      Value *WideSel = Builder.CreateSelect(ICI, CmpLHS, CmpC);
+      return new TruncInst(WideSel, NarrowType);
+    }
+  }
+

...but I suppose treating this as another special-case min/max is fine too. However, the tests you have are both not minimized (we don't need a clamp pattern) and not complete. Please try this case too:

define <2 x i8> @min_through_cast_vec(<2 x i32> %x) {
  %cmp = icmp slt <2 x i32> %x, <i32 510, i32 511>
  %max_trunc = trunc <2 x i32> %x to <2 x i8>
  %res = select <2 x i1> %cmp, <2 x i8> %max_trunc, <2 x i8> <i8 254, i8 255>
  ret <2 x i8> %res
}

Once you determine that the compare is against a constant, I don't think you need to recreate that constant - just use that constant:

if (match(CmpI->getOperand(1), m_Constant(CmpConst)))
  CastedTo = CmpConst;

[ArturGainullin]

Minimized test cases and added new ones.

[ArturGainullin]

For using constant from cmp instruction (instead of recreation) we will need to check that truncated constant is equal to lower bits of cmp constant.
That is why I decided just to recreate constant which looks like more general solution.

[spatel]

In D38536#899151, @ArturGainullin wrote:

For using constant from cmp instruction (instead of recreation) we will need to check that truncated constant is equal to lower bits of cmp constant.
That is why I decided just to recreate constant which looks like more general solution.

That is already done?

// Make sure the cast doesn't lose any information.
  Constant *CastedBack =
      ConstantExpr::getCast(*CastOp, CastedTo, C->getType(), true);
  if (CastedBack != C)
    return nullptr;

That's why I suggested the non-splat vector test - it should be transformed too, right?

[ArturGainullin]

Fixed according to comments.

[ArturGainullin]

Oh, yes, it is clear for me now. Thanks! I have fixed according to your recommendation.

[ArturGainullin]

Improved comment.

[spatel]

LGTM - see inline notes for a couple of changes to the code comments.

lib/Analysis/ValueTracking.cpp

4312 ↗

(On Diff #119265)

typo: initial - you could just remove that word, and the comment would be better.

4350–4355 ↗

(On Diff #119265)

It's more typical to use 'C' for constant values in code and comments in LLVM, so I'd change this comment text and formula to match the code:

%cond = cmp iN %x, CmpConst
%tr = trunc iN %x to iK
%narrowsel = select i1 %cond, iK %t, iK C
-->
%cond = cmp iN %x, CmpConst
%widesel = select i1 %cond, iN %x, iN CmpConst
%tr = trunc iN %widesel to iK

llvm/trunk/lib/Analysis/ValueTracking.cpp

static SelectPatternResult matchSelectPattern(CmpInst::Predicate Pred,
   if (NaNBehavior != SPNB_RETURNS_ANY ||
       (!FMF.noSignedZeros() && !isKnownNonZero(CmpLHS) &&
        !isKnownNonZero(CmpRHS)))
     return {SPF_UNKNOWN, SPNB_NA, false};
 
   return matchFastFloatClamp(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, LHS, RHS);
 }
 
+/// Helps to match a select pattern in case of a type mismatch.
+///
+/// The function processes the case when type of true and false values of a
+/// select instruction differs from type of the cmp instruction operands because
+/// of a cast instructon. The function checks if it is legal to move the cast
+/// operation after "select". If yes, it returns the new second value of
+/// "select" (with the assumption that cast is moved):
+/// 1. As operand of cast instruction when both values of "select" are same cast
+/// instructions.
+/// 2. As restored constant (by applying reverse cast operation) when the first
+/// value of the "select" is a cast operation and the second value is a
+/// constant.
+/// NOTE: We return only the new second value because the first value could be
+/// accessed as operand of cast instruction.
 static Value *lookThroughCast(CmpInst *CmpI, Value *V1, Value *V2,
                               Instruction::CastOps *CastOp) {
   auto *Cast1 = dyn_cast<CastInst>(V1);
   if (!Cast1)
     return nullptr;
 
   *CastOp = Cast1->getOpcode();
   Type *SrcTy = Cast1->getSrcTy();
case Instruction::ZExt:
     if (CmpI->isUnsigned())
       CastedTo = ConstantExpr::getTrunc(C, SrcTy);
     break;
   case Instruction::SExt:
     if (CmpI->isSigned())
       CastedTo = ConstantExpr::getTrunc(C, SrcTy, true);
     break;
   case Instruction::Trunc:
+    Constant *CmpConst;
+    if (match(CmpI->getOperand(1), m_Constant(CmpConst))) {
+      // Here we have the following case:
+      //
+      //   %cond = cmp iN %x, CmpConst
+      //   %tr = trunc iN %x to iK
+      //   %narrowsel = select i1 %cond, iK %t, iK C
+      //
+      // We can always move trunc after select operation:
+      //
+      //   %cond = cmp iN %x, CmpConst
+      //   %widesel = select i1 %cond, iN %x, iN CmpConst
+      //   %tr = trunc iN %widesel to iK
+      //
+      // Note that C could be extended in any way because we don't care about
+      // upper bits after truncation. It can't be abs pattern, because it would
+      // look like:
+      //
+      //   select i1 %cond, x, -x.
+      //
+      // So only min/max pattern could be matched. Such match requires widened C
+      // == CmpConst. That is why set widened C = CmpConst, condition trunc
+      // CmpConst == C is checked below.
+      CastedTo = CmpConst;
+    } else {
       CastedTo = ConstantExpr::getIntegerCast(C, SrcTy, CmpI->isSigned());
+    }
     break;
   case Instruction::FPTrunc:
     CastedTo = ConstantExpr::getFPExtend(C, SrcTy, true);
     break;
   case Instruction::FPExt:
     CastedTo = ConstantExpr::getFPTrunc(C, SrcTy, true);
     break;
   case Instruction::FPToUI:

llvm/trunk/test/Transforms/InstCombine/minmax-fold.ll

 ; CHECK-NEXT:    ret <8 x float> [[SEL]]
 ;
   %bcx = bitcast <8 x float> %x to <8 x i32>
   %bcy = bitcast <8 x float> %y to <8 x i32>
   %cmp = icmp slt <8 x i32> %bcx, %bcy
   %sel = select <8 x i1> %cmp, <8 x float> %x, <8 x float> %y
   ret <8 x float> %sel
 }
+
+; Check that we look through cast and recognize min idiom.
+define zeroext i8 @look_through_cast1(i32 %x) {
+; CHECK-LABEL: @look_through_cast1(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X:%.*]], 511
+; CHECK-NEXT:    [[RES1:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 511
+; CHECK-NEXT:    [[TMP2:%.*]] = trunc i32 [[RES1]] to i8
+; CHECK-NEXT:    ret i8 [[TMP2]]
+;
+  %cmp1 = icmp slt i32 %x, 511
+  %x_trunc = trunc i32 %x to i8
+  %res = select i1 %cmp1, i8 %x_trunc, i8 255
+  ret i8 %res
+}
+
+; Check that we look through cast but min is not recognized.
+define zeroext i8 @look_through_cast2(i32 %x) {
+; CHECK-LABEL: @look_through_cast2(
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[X:%.*]], 510
+; CHECK-NEXT:    [[X_TRUNC:%.*]] = trunc i32 [[X]] to i8
+; CHECK-NEXT:    [[RES:%.*]] = select i1 [[CMP1]], i8 [[X_TRUNC]], i8 -1
+; CHECK-NEXT:    ret i8 [[RES]]
+;
+  %cmp1 = icmp slt i32 %x, 510
+  %x_trunc = trunc i32 %x to i8
+  %res = select i1 %cmp1, i8 %x_trunc, i8 255
+  ret i8 %res
+}
+
+define <2 x i8> @min_through_cast_vec1(<2 x i32> %x) {
+; CHECK-LABEL: @min_through_cast_vec1(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <2 x i32> [[X:%.*]], <i32 510, i32 511>
+; CHECK-NEXT:    [[RES1:%.*]] = select <2 x i1> [[TMP1]], <2 x i32> [[X]], <2 x i32> <i32 510, i32 511>
+; CHECK-NEXT:    [[TMP2:%.*]] = trunc <2 x i32> [[RES1]] to <2 x i8>
+; CHECK-NEXT:    ret <2 x i8> [[TMP2]]
+;
+  %cmp = icmp slt <2 x i32> %x, <i32 510, i32 511>
+  %x_trunc = trunc <2 x i32> %x to <2 x i8>
+  %res = select <2 x i1> %cmp, <2 x i8> %x_trunc, <2 x i8> <i8 254, i8 255>
+  ret <2 x i8> %res
+}
+
+define <2 x i8> @min_through_cast_vec2(<2 x i32> %x) {
+; CHECK-LABEL: @min_through_cast_vec2(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <2 x i32> [[X:%.*]], <i32 511, i32 511>
+; CHECK-NEXT:    [[RES1:%.*]] = select <2 x i1> [[TMP1]], <2 x i32> [[X]], <2 x i32> <i32 511, i32 511>
+; CHECK-NEXT:    [[TMP2:%.*]] = trunc <2 x i32> [[RES1]] to <2 x i8>
+; CHECK-NEXT:    ret <2 x i8> [[TMP2]]
+;
+  %cmp = icmp slt <2 x i32> %x, <i32 511, i32 511>
+  %x_trunc = trunc <2 x i32> %x to <2 x i8>
+  %res = select <2 x i1> %cmp, <2 x i8> %x_trunc, <2 x i8> <i8 255, i8 255>
+  ret <2 x i8> %res
+}