[InstCombine] remove fold: zext(bool) + C -> bool ? C + 1 : C

[spatel]

Summary

This is a small patch with a long backstory.

First, I'm proposing to remove a fold of (zext i1) + C to select of constants.
A pair of sibling folds for this was added at:
https://reviews.llvm.org/rL75531

The commit was made with a request for feedback in case selects might not be the best form. 3 years later, we lost half of the transform with:
https://reviews.llvm.org/rL159230

Sadly, that commit just removed code and didn't bother to canonicalize the other way (from select to ext+add). That left us in a state where logically equivalent code could be present in multiple forms - PR30327:
https://llvm.org/bugs/show_bug.cgi?id=30327

So in addition to removing the remaining piece of r75531, I'm proposing to canonicalize selects to ext+add and filling in whatever folds may be missing as follow-up patches (see the motivating case based on the source code for InstCombine itself in PR30273).

There are a few reasons to prefer ext+add to select:

1. Adds with constants are easier to combine with other adds and subs.
2. We are already canonicalizing selects with {-1,0,1} to extends; doing this for all constants is more consistent.
3. As noted, we already lost half of the original patch, so we're not even consistent about C+1 vs. C-1.
4. The stated reason for killing the C-1 half of the patch was poor codegen. This is not a valid reason by itself to change a canonicalization (just fix the backend). However, as a practical matter, it is 7 years later and we still have not fixed the backend! See the codegen examples for AArch64 and PowerPC here:

https://llvm.org/bugs/show_bug.cgi?id=30327#c2

In order to avoid a regression on the tests in test/Transforms/InstCombine/icmp-div-constant.ll (note that those are phantom diffs), I'm adding a fold that converts icmp (add (zext), -1) to icmp' (sext) in this patch. I'm not sure how to expose this difference independently of removing the select fold.

[majnemer]

I think r159230 was a step in the wrong direction. An add with a zext seems harder to reason about than a select.

[spatel]

In D24480#540517, @majnemer wrote:

I think r159230 was a step in the wrong direction. An add with a zext seems harder to reason about than a select.

This seems similar to the select -> shuffle canonicalization (D24279) to me. I think it's easier to *read* a select in the IR (I was initially in favor of the select in that case), but it's easier to *combine* the alternative (shuffles or adds). Please let me know if you see an example where a select is easier to combine either in IR or the DAG.

Note that I'm starting from the perspective of:
https://llvm.org/bugs/show_bug.cgi?id=30273

Ie, it's going to take more work to untangle these selects to the adds that most (all?) targets would prefer to codegen:

define i32 @selects_are_hard(i1 zeroext %a, i1 zeroext %b, i1 zeroext %c) {
  %. = zext i1 %a to i32
  %inc5 = select i1 %a, i32 2, i32 1
  %ret.1 = select i1 %b, i32 %inc5, i32 %.
  %inc9 = zext i1 %c to i32
  %inc9.ret.1 = add nuw nsw i32 %inc9, %ret.1
  ret i32 %inc9.ret.1
}

define i32 @adds_are_easy(i1 zeroext %a, i1 zeroext %b, i1 zeroext %c) {
  %conv = zext i1 %a to i32
  %conv4 = zext i1 %b to i32
  %add = add nuw nsw i32 %conv4, %conv
  %conv6 = zext i1 %c to i32
  %add7 = add nuw nsw i32 %add, %conv6
  ret i32 %add7
}

[majnemer]

I think IR should be canonicalized with ValueTracking in mind (ComputeKnownBits, etc.)
That SelectionDAG doesn't know how to make selects lower nicely is a problem but it can be localized late in codegen: either in SDAG itself or CGP.

[efriedma]

The general direction seems fine.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1070–1084

I guess we should prefer sext(cmp) over add(zext(cmp), -1), but we prefer add(zext(cmp), N) over add(sext(cmp), N-1) for any other N? That works, but you might want to explain that here.

[arsenm]

In D24480#540557, @majnemer wrote:

I think IR should be canonicalized with ValueTracking in mind (ComputeKnownBits, etc.)
That SelectionDAG doesn't know how to make selects lower nicely is a problem but it can be localized late in codegen: either in SDAG itself or CGP.

+1

[spatel]

In D24480#540557, @majnemer wrote:

I think IR should be canonicalized with ValueTracking in mind (ComputeKnownBits, etc.)

That sounds good, but this raises questions for me:

1. Why is select i8 %bool, i8 2, i8 1 better for ValueTracking than zext i1 %bool to i8; add nuw nsw i8 %z, 1? Is there a fundamental or practical difference in what computeKnownBits can extract from either of those?

2. If select has an advantage and is the canonical form for the case of choosing between constants, then should we remove these existing transforms?
   1. select b, 1, 0 -> zext b to int
   2. select b, -1, 0 -> sext b to int
   3. select b, 0, 1 -> zext !b to int
   4. select b, 0, -1 -> sext !b to int

3. Is the IR for @selects_are_hard in my earlier comment canonical? Ie, is a select with variable operands also preferred over an add: %ret.1 = select i1 %b, i32 %inc5, i32 %. ?

4. Should I send a note to llvm-dev for a wider audience?

[spatel]

Ping.

Patch updated:
Added comment about this case of sext over zext as suggested by Eli.

[efriedma]

LGTM. (If you want to discuss more general questions of when we should prefer select vs. arithmetic, please bring it up on llvmdev.)

[spatel]

In D24480#553185, @efriedma wrote:

LGTM. (If you want to discuss more general questions of when we should prefer select vs. arithmetic, please bring it up on llvmdev.)

Thanks, Eli.
Sure - I'll post the issues raised here on llvm-dev, so we can get more feedback before trying to commit this.

[spatel]

There seems to be consensus that we should canonicalize towards select in IR (ie, as David suggested - rL159230 was a mistake):
http://lists.llvm.org/pipermail/llvm-dev/2016-September/105335.html
...so I will most likely abandon this patch eventually. Leaving as-is for the moment just in case that changes. And maybe we still want to make the add(zext) --> sext transform as an independent change.

[spatel]

Abandoning - see D40612.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
   // FIXME: Use the match above instead of dyn_cast to allow these transforms
   // for splat vectors.
   if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
     // See if SimplifyDemandedBits can simplify this.  This handles stuff like
     // (X & 254)+1 -> (X&254)|1
     if (SimplifyDemandedInstructionBits(I))
       return &I;
 
-    // zext(bool) + C -> bool ? C + 1 : C
-    if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS))
-      if (ZI->getSrcTy()->isIntegerTy(1))
-        return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI);
+    // add (zext (icmp Pred X, Y)), -1 --> sext (icmp Pred' X, Y)
+    // In general, we prefer to have zext rather than sext for better
+    // value-tracking potential, but in this case, we get to eliminate an add.
+    Instruction *ZextOp;
+    ICmpInst::Predicate Pred;
+    Value *X, *Y;
+    if (CI->getSExtValue() == -1 && match(LHS, m_ZExt(m_Instruction(ZextOp))) &&
+        match(ZextOp, m_OneUse(m_ICmp(Pred, m_Value(X), m_Value(Y))))) {
+      // We have this pattern: if the compare is true, return 0;
+      //                       if the compare is false, return -1.
+      // Transform it to: if the inverse compare is true, return -1;
+      //                  if the inverse compare is false, return 0.
+      auto *Cmp = Builder->CreateICmp(CmpInst::getInversePredicate(Pred), X, Y);
+      return CastInst::Create(Instruction::SExt, Cmp, I.getType());
+    }
 
     Value *XorLHS = nullptr; ConstantInt *XorRHS = nullptr;
     if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) {
       uint32_t TySizeBits = I.getType()->getScalarSizeInBits();
       const APInt &RHSVal = CI->getValue();
       unsigned ExtendAmt = 0;
       // If we have ADD(XOR(AND(X, 0xFF), 0x80), 0xF..F80), it's a sext.
       // If we have ADD(XOR(AND(X, 0xFF), 0xF..F80), 0x80), it's a sext.

test/Transforms/InstCombine/icmp-div-constant.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; PR30281 - https://llvm.org/bugs/show_bug.cgi?id=30281
 
 ; All of these tests contain foldable division-by-constant instructions, but we
 ; can't assert that those folds have occurred before we process the later icmp.
 
 define i32 @icmp_div(i16 %a, i16 %c) {
 ; CHECK-LABEL: @icmp_div(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i16 %a, 0
 ; CHECK-NEXT:    br i1 [[TOBOOL]], label %then, label %exit
 ; CHECK:       then:
-; CHECK-NEXT:    [[NOT_CMP:%.*]] = icmp eq i16 %c, 0
-; CHECK-NEXT:    [[PHITMP1:%.*]] = sext i1 [[NOT_CMP]] to i32
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i16 %c, 0
+; CHECK-NEXT:    [[PHITMP1:%.*]] = sext i1 [[TMP0]] to i32
 ; CHECK-NEXT:    br label %exit
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ -1, %entry ], [ [[PHITMP1]], %then ]
 ; CHECK-NEXT:    ret i32 [[PHI]]
 ;
 entry:
   %tobool = icmp eq i16 %a, 0
   br i1 %tobool, label %then, label %exit

 }
 
 define i32 @icmp_div3(i16 %a, i16 %c) {
 ; CHECK-LABEL: @icmp_div3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i16 %a, 0
 ; CHECK-NEXT:    br i1 [[TOBOOL]], label %then, label %exit
 ; CHECK:       then:
-; CHECK-NEXT:    [[NOT_CMP:%.*]] = icmp eq i16 %c, 0
-; CHECK-NEXT:    [[PHITMP1:%.*]] = sext i1 [[NOT_CMP]] to i32
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i16 %c, 0
+; CHECK-NEXT:    [[PHITMP1:%.*]] = sext i1 [[TMP0]] to i32
 ; CHECK-NEXT:    br label %exit
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ -1, %entry ], [ [[PHITMP1]], %then ]
 ; CHECK-NEXT:    ret i32 [[PHI]]
 ;
 entry:
   %tobool = icmp eq i16 %a, 0
   br i1 %tobool, label %then, label %exit

test/Transforms/InstCombine/zext-bool-add-sub.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; rdar://11748024
 
 define i32 @a(i1 zeroext %x, i1 zeroext %y) {
 ; CHECK-LABEL: @a(
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 %x to i32
 ; CHECK-NEXT:    [[CONV3_NEG:%.*]] = sext i1 %y to i32
-; CHECK-NEXT:    [[SUB:%.*]] = select i1 %x, i32 2, i32 1
+; CHECK-NEXT:    [[SUB:%.*]] = add nuw nsw i32 [[CONV]], 1
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[SUB]], [[CONV3_NEG]]
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
   %conv = zext i1 %x to i32
   %conv3 = zext i1 %y to i32
   %conv3.neg = sub i32 0, %conv3
   %sub = add i32 %conv, 1
   %add = add i32 %sub, %conv3.neg
;
   %conv3 = zext i1 %b to i32
   %add = add nuw nsw i32 %conv3, %conv
   ret i32 %add
 }
 
 define i32 @PR30273_three_bools(i1 %x, i1 %y, i1 %z) {
 ; CHECK-LABEL: @PR30273_three_bools(
 ; CHECK-NEXT:    [[FROMBOOL:%.*]] = zext i1 %x to i32
-; CHECK-NEXT:    [[ADD1:%.*]] = select i1 %x, i32 2, i32 1
-; CHECK-NEXT:    [[SEL1:%.*]] = select i1 %y, i32 [[ADD1]], i32 [[FROMBOOL]]
+; CHECK-NEXT:    [[ADD1:%.*]] = zext i1 %y to i32
+; CHECK-NEXT:    [[SEL1:%.*]] = add nuw nsw i32 [[FROMBOOL]], [[ADD1]]
 ; CHECK-NEXT:    [[ADD2:%.*]] = zext i1 %z to i32
 ; CHECK-NEXT:    [[SEL2:%.*]] = add nuw nsw i32 [[SEL1]], [[ADD2]]
 ; CHECK-NEXT:    ret i32 [[SEL2]]
 ;
   %frombool = zext i1 %x to i32
   %add1 = add nsw i32 %frombool, 1
   %sel1 = select i1 %y, i32 %add1, i32 %frombool
   %add2 = add nsw i32 %sel1, 1
   %sel2 = select i1 %z, i32 %add2, i32 %sel1
   ret i32 %sel2
 }