[SCEVExpander] Discount cost of umin(1, x) expressions

[reames]

Summary

umin(1, x) reduces to checking if x != 0 as the expression can only be zero if x == 0. InstCombine has been taught to turn the umin form into the zext of icmp form; this patch adjusts the cost model used for determining if an expression is "high cost" to apply discount the same case.

This is was found while working on a variant of what would eventually become D105216. It has the effect of allowing LFTR more often when we use the ceiling expansion. However, I have not been able to find a way to test it on it's own. I'm tempted to land it without tests, but maybe a reviewer has a better idea?

[reames]

For future self:

• and reduction trick does not hold when A and B are both non-zero, but with different bits set.
• the original umin(a,1) trick still holds, it's the extension to multiple operands which was wrong

[reames]

Rely on instcombine, and remove wrong code.

[efriedma]

Can we write tests for this, now that all the overflow stuff has landed?

[fhahn]

This looks good to me. It would be good to have a test though.

[fhahn]

(Let me try if I can get this to trigger so we can extract a test)

[fhahn]

In D105209#2943276, @fhahn wrote:

(Let me try if I can get this to trigger so we can extract a test)

Hm I couldn't get this triggered on MultiSource/SPEC2006/SPEC2017 with -O3 on X86. Philip, do you have any thoughts if a different combination of flags may make this trigger in C/C++?

[reames]

Abandoning this for now. This came up in an alternate approach to the overflow during BTC computation issue, and I separated it out. It doesn't appear to matter with the current approach, so I'll defer this until it does. I think the patch is correct, it just doesn't have a strong motivation or test right now.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) {
   // In the case of mixed integer and pointer types, cast the
   // final result back to the pointer type.
   if (LHS->getType() != S->getType())
     LHS = InsertNoopCastOfTo(LHS, S->getType());
   return LHS;
 }
 
 Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) {
+  // For the umin(1,X1...Xn) pattern described in the cost modeling, we let
+  // instcombine do the actual transform, relying on the order of SCEV
+  // canonicalization to put the constant in the outermost umin.
   Value *LHS = expand(S->getOperand(S->getNumOperands() - 1));
   Type *Ty = LHS->getType();
   for (int i = S->getNumOperands() - 2; i >= 0; --i) {
     // In the case of mixed integer and pointer types, do the
     // rest of the comparisons as integer.
     Type *OpTy = S->getOperand(i)->getType();
     if (OpTy->isIntegerTy() != Ty->isIntegerTy()) {
       Ty = SE.getEffectiveSCEVType(Ty);
case scAddExpr:
     Cost = ArithCost(Instruction::Add, S->getNumOperands() - 1);
     break;
   case scMulExpr:
     // TODO: this is a very pessimistic cost modelling for Mul,
     // because of Bin Pow algorithm actually used by the expander,
     // see SCEVExpander::visitMulExpr(), ExpandOpBinPowN().
     Cost = ArithCost(Instruction::Mul, S->getNumOperands() - 1);
     break;
+  case scUMinExpr:
+    // For umin(1, x2, ..., xn), the form we generate will be converted by
+    // instcombine to: zext(icmp ne umin(x1..xn), 0).  This saves one select.
+    if (S->getOperand(0)->getType()->isIntegerTy() &&
+        S->getOperand(0)->isOne()) {
+      Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1);
+      if (S->getNumOperands() > 2)
+        Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 2, 0, 2);
+      Cost += CastCost(Instruction::ZExt);
+      break;
+    }
+    LLVM_FALLTHROUGH;
   case scSMaxExpr:
   case scUMaxExpr:
-  case scSMinExpr:
-  case scUMinExpr: {
+  case scSMinExpr: {
     // FIXME: should this ask the cost for Intrinsic's?
     Cost += CmpSelCost(Instruction::ICmp, S->getNumOperands() - 1, 0, 1);
     Cost += CmpSelCost(Instruction::Select, S->getNumOperands() - 1, 0, 2);
     break;
   }
   case scAddRecExpr: {
     // In this polynominal, we may have some zero operands, and we shouldn't
     // really charge for those. So how many non-zero coeffients are there?