Make cltz and cttz zero undef when the operand cannot be zero in InstCombine

[deadalnix]

Summary

As per title.

[majnemer]

Please split this patch into two changes.

[spatel]

For reference, the ctpop side of this patch is one of the missing folds noted in PR28668:
https://llvm.org/bugs/show_bug.cgi?id=28668

[deadalnix]

Split popcount change in D23139

[spatel]

Just curious, is there a fold or codegen that doesn't work because of the undef?

lib/Transforms/InstCombine/InstCombineCalls.cpp

1403 ↗

(On Diff #66724)

I'm not sure where we draw the line on 'auto', but I think the general preference is to use the actual type (Value *) in cases like this. At the least, this should be 'auto *' according to the coding standards.

1410 ↗

(On Diff #66724)

Use 'Op0' since we have it now.

1416–1417 ↗

(On Diff #66724)

I don't see anything about 'goto' in the coding standard doc, but I was trained to feel nervous anytime I see one. Make this a static helper or lambda instead?

1421–1438 ↗

(On Diff #66724)

How about refactoring this whole case into a helper function since it's nearly identical to the cttz case? That would remove the question about the 'goto' too.

test/Transforms/InstCombine/intrinsics.ll

383 ↗

(On Diff #66724)

You can remove the label to reuce the test and the CHECKs.

[spatel]

test/Transforms/InstCombine/intrinsics.ll

383 ↗

(On Diff #66724)

typo:
"reuce" -> "reduce"

[deadalnix]

@spatel , the undef version lead to much better codegen on X86 at least, because bsf/bsr instruction are undefined when the operand is 0.

[deadalnix]

Address @spatel comments.

[spatel]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1240–1253 ↗

(On Diff #66906)

Can't this function simplify to one line of code?

II->setArgOperand(1, ConstantInt::getTrue(II->getContext()));

Ie, you don't even need to check the current value of the undef operand. If it's already true, setting it again does nothing.

1414–1452 ↗

(On Diff #66906)

I was hoping that you could refactor this whole thing, so there's no code duplication.

On 2nd look, I see that the existing fold is actually in the wrong place. Since we're able to fold to a constant, I think it belongs in InstSimplify. Can you fix that or add a 'FIXME' comment?

I'd still prefer that you refactor this ahead of the functional change. If my first comment about makeCttzCtlzZeroUndef() being one line of code is correct, then it's still just one helper function for this whole thing.

Let me know if I'm not seeing this correctly.

test/Transforms/InstCombine/intrinsics.ll

406 ↗

(On Diff #66906)

Remove unnecessary label.

[deadalnix]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1240–1253 ↗

(On Diff #66906)

No, you want to patch this only once, not every time, or it'll never terminate.

[deadalnix]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1414–1452 ↗

(On Diff #66906)

The bitmask manipulation previous this, while following a similar pattern, are different for cttz and ctlz.

This is NOT constant folding in any way. It is making cttz and/or ctlz undefined for 0 when possible as it lead to better codegen, at least on X86. No the function cannot be simplified to a one liner.

[deadalnix]

Remove entry label.

[spatel]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1414–1452 ↗

(On Diff #66989)

I've drafted what I tried to suggest here as D23223. Let me know if that makes sense.

[deadalnix]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1414–1452 ↗

(On Diff #66989)

I don't think it really makes the code better. There are more branches and names become ambiguous as they can represent 2 things. Also, this is kind of out of the scope of this diff.

[spatel]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1240–1253 ↗

(On Diff #66989)

OK, then:

if (match(II->getArgOperand(1), m_Zero()))
  II->setArgOperand(1, ConstantInt::getTrue(II->getContext()));

[deadalnix]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1240–1253 ↗

(On Diff #66989)

I'd rather match everything that is NOT true, just in case.

[spatel]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1240–1253 ↗

(On Diff #66989)

Sorry - I don't see the difference between the 'm_Zero' version and this?

Note that I checked in the refactoring in rL277883. We have too many LLVM bugs due to code duplication, and this function may continue to grow over time.

[deadalnix]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1240–1253 ↗

(On Diff #66989)

Alright, I'll rebase on top of it.

Not all value are true or false, so matching what is NOT true is not the same as matching false.

[deadalnix]

rebase on top of @spatel changes

[spatel]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1283–1296 ↗

(On Diff #67132)

Sorry for still not seeing it...can you add test case to show the difference?

AFAICT, the undef param of these intrinsics must be an i1 true/false constant?

case Intrinsic::ctlz:  // llvm.ctlz
case Intrinsic::cttz:  // llvm.cttz
  Assert(isa<ConstantInt>(CS.getArgOperand(1)),
         "is_zero_undef argument of bit counting intrinsics must be a "
         "constant int",
         CS);

[deadalnix]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1283–1296 ↗

(On Diff #67132)

I has no idea there was an assertion to make sure of this. I'd still go for the logic "if it is anything but true, make it true" rather than it "if it false, make it true".

[spatel]

I has no idea there was an assertion to make sure of this. I'd still go for the logic "if it is anything but true, make it true" rather than it "if it false, make it true".

I think that's fair - how about this:

if (KnownOne != 0 || isKnownNonZero(Op0, IC.getDataLayout()))
  if (!match(II.getArgOperand(1), m_One()))
    II.setArgOperand(1, ConstantInt::getTrue(II.getContext()));

But I think we need a comment to explain the transform and motivation. Something like

// If the input to cttz/ctlz is known to be non-zero, 
// then change the 'ZeroIsUndef' parameter to 'true'
// because we know the zero behavior can't affect the result.

[deadalnix]

Use match and add comment that explain the transformation.

[majnemer]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1143 ↗

(On Diff #67463)

I'd use IRBuilder's getTrue here.

[deadalnix]

Use getTrue

[spatel]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1141 ↗

(On Diff #67479)

Shouldn't this return the updated instruction to signal to the callers that a change was made? If we do that, then we don't need to explicitly add to the worklist either, right?

[deadalnix]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1141 ↗

(On Diff #67479)

No as we don't want to go though replacing the instruction by itself and we especially don't want to replace false by true in the program.

[spatel]

No as we don't want to go though replacing the instruction by itself and we especially don't want to replace false by true in the program.

I don't understand the 2nd comment. For the first, I'm not suggesting that you replace the instruction by itself.
Looking around InstCombine, the common pattern I see is:

I.setOperand(1, X);
return &I;

This adheres to the 'visit' function comments:

// Visitation implementation - Implement instruction combining for different
// instruction types.  The semantics are as follows:
// Return Value:
//    null        - No change was made
//     I          - Change was made, I is still valid, I may be dead though
//   otherwise    - Change was made, replace I with returned instruction

I think we'd have to change the helper function signature to return an Instruction* for this to work, so I'll defer to @majnemer on whether the code here is an acceptable substitute. I have no further comments for this patch.

[deadalnix]

Return the instruction instead of putting it in the worklist manually.

[spatel]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1473–1475 ↗

(On Diff #67974)

In the case where no change is made, we want to continue on in this function:

if (Instruction *I = foldCttzCtlz(*II, *this))
  return I;
break;

[deadalnix]

Continue if no change is made.

[spatel]

LGTM.

llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp

static Instruction *simplifyMaskedScatter(IntrinsicInst &II, InstCombiner &IC) {
   // If the mask is all zeros, a scatter does nothing.
   auto *ConstMask = dyn_cast<Constant>(II.getArgOperand(3));
   if (ConstMask && ConstMask->isNullValue())
     return IC.eraseInstFromFunction(II);
 
   return nullptr;
 }
 
-static Value *foldCttzCtlz(IntrinsicInst &II, InstCombiner &IC) {
+static Instruction *foldCttzCtlz(IntrinsicInst &II, InstCombiner &IC) {
+  assert((II.getIntrinsicID() == Intrinsic::cttz ||
+          II.getIntrinsicID() == Intrinsic::ctlz) &&
+         "Expected cttz or ctlz intrinsic");
   Value *Op0 = II.getArgOperand(0);
   // FIXME: Try to simplify vectors of integers.
   auto *IT = dyn_cast<IntegerType>(Op0->getType());
   if (!IT)
     return nullptr;
 
   unsigned BitWidth = IT->getBitWidth();
   APInt KnownZero(BitWidth, 0);
   APInt KnownOne(BitWidth, 0);
   IC.computeKnownBits(Op0, KnownZero, KnownOne, 0, &II);
 
   // Create a mask for bits above (ctlz) or below (cttz) the first known one.
   bool IsTZ = II.getIntrinsicID() == Intrinsic::cttz;
   unsigned NumMaskBits = IsTZ ? KnownOne.countTrailingZeros()
                               : KnownOne.countLeadingZeros();
   APInt Mask = IsTZ ? APInt::getLowBitsSet(BitWidth, NumMaskBits)
                     : APInt::getHighBitsSet(BitWidth, NumMaskBits);
 
   // If all bits above (ctlz) or below (cttz) the first known one are known
   // zero, this value is constant.
   // FIXME: This should be in InstSimplify because we're replacing an
   // instruction with a constant.
-  if ((Mask & KnownZero) == Mask)
-    return ConstantInt::get(IT, APInt(BitWidth, NumMaskBits));
+  if ((Mask & KnownZero) == Mask) {
+    auto *C = ConstantInt::get(IT, APInt(BitWidth, NumMaskBits));
+    return IC.replaceInstUsesWith(II, C);
+  }
+
+  // If the input to cttz/ctlz is known to be non-zero,
+  // then change the 'ZeroIsUndef' parameter to 'true'
+  // because we know the zero behavior can't affect the result.
+  if (KnownOne != 0 || isKnownNonZero(Op0, IC.getDataLayout())) {
+    if (!match(II.getArgOperand(1), m_One())) {
+      II.setOperand(1, IC.Builder->getTrue());
+      return &II;
+    }
+  }
 
   return nullptr;
 }
 
 // TODO: If the x86 backend knew how to convert a bool vector mask back to an
 // XMM register mask efficiently, we could transform all x86 masked intrinsics
 // to LLVM masked intrinsics and remove the x86 masked intrinsic defs.
 static Instruction *simplifyX86MaskedLoad(IntrinsicInst &II, InstCombiner &IC) {
if (ConstantInt *Power = dyn_cast<ConstantInt>(II->getArgOperand(1))) {
       if (Power->isAllOnesValue())
         return BinaryOperator::CreateFDiv(ConstantFP::get(CI.getType(), 1.0),
                                           II->getArgOperand(0));
     }
     break;
 
   case Intrinsic::cttz:
   case Intrinsic::ctlz:
-    if (Value *V = foldCttzCtlz(*II, *this))
-      return replaceInstUsesWith(*II, V);
+    if (auto *I = foldCttzCtlz(*II, *this))
+      return I;
     break;
 
   case Intrinsic::uadd_with_overflow:
   case Intrinsic::sadd_with_overflow:
   case Intrinsic::umul_with_overflow:
   case Intrinsic::smul_with_overflow:
     if (isa<Constant>(II->getArgOperand(0)) &&
         !isa<Constant>(II->getArgOperand(1))) {

llvm/trunk/test/Transforms/InstCombine/intrinsics.ll

 ; CHECK-LABEL: @ctlz_undef(
 ; CHECK-NEXT:    ret i32 undef
 ;
   %ctlz = call i32 @llvm.ctlz.i32(i32 0, i1 true)
   ret i32 %ctlz
 
 }
 
+define i32 @ctlz_make_undef(i32 %a) {
+  %or = or i32 %a, 8
+  %ctlz = tail call i32 @llvm.ctlz.i32(i32 %or, i1 false)
+  ret i32 %ctlz
+; CHECK-LABEL: @ctlz_make_undef(
+; CHECK-NEXT: %or = or i32 %a, 8
+; CHECK-NEXT: %ctlz = tail call i32 @llvm.ctlz.i32(i32 %or, i1 true)
+; CHECK-NEXT: ret i32 %ctlz
+}
+
 define i32 @cttz_undef(i32 %Value) nounwind {
 ; CHECK-LABEL: @cttz_undef(
 ; CHECK-NEXT:    ret i32 undef
 ;
   %cttz = call i32 @llvm.cttz.i32(i32 0, i1 true)
   ret i32 %cttz
 
 }
 
+define i32 @cttz_make_undef(i32 %a) {
+  %or = or i32 %a, 8
+  %cttz = tail call i32 @llvm.cttz.i32(i32 %or, i1 false)
+  ret i32 %cttz
+; CHECK-LABEL: @cttz_make_undef(
+; CHECK-NEXT: %or = or i32 %a, 8
+; CHECK-NEXT: %cttz = tail call i32 @llvm.cttz.i32(i32 %or, i1 true)
+; CHECK-NEXT: ret i32 %cttz
+}
+
 define i32 @ctlz_select(i32 %Value) nounwind {
 ; CHECK-LABEL: @ctlz_select(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctlz.i32(i32 %Value, i1 false)
 ; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %tobool = icmp ne i32 %Value, 0
   %ctlz = call i32 @llvm.ctlz.i32(i32 %Value, i1 true)
   %s = select i1 %tobool, i32 %ctlz, i32 32