[InstCombine] ctlz(x) -> 0 if x is known negative number

[xbolva00]

Summary

----------------------------------------
define i32 @src(i32 %x, i1 %zerodef) {
%0:
  %assume = icmp slt i32 %x, 0
  assume i1 %assume
  %c = ctlz i32 %x, %zerodef
  ret i32 %c
}
=>
define i32 @tgt(i32 %x, i1 %zerodef) {
%0:
  %assume = icmp slt i32 %x, 0
  assume i1 %assume
  ret i32 0
}
Transformation seems to be correct!

Proof: https://alive2.llvm.org/ce/z/rU6o1d
Solves second case in https://bugs.llvm.org/show_bug.cgi?id=50173

[xbolva00]

Generalization.

[RKSimon]

llvm/test/Transforms/InstSimplify/call.ll

1490

please pre-commit the new tests and rebase

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

5412–5413 ↗

(On Diff #342757)

Enhance isKnownNegative to know that ashr of negative constant is still negative? Then we could remove the match here.

[xbolva00]

Rebased.

[xbolva00]

llvm/lib/Analysis/InstructionSimplify.cpp

5412–5413 ↗

(On Diff #342757)

Yeah

5412–5413 ↗

(On Diff #342757)

As followup I think.

[RKSimon]

LGTM

[craig.topper]

What's the advantage of doing this in InstSimplfy when InstCombine can already do it via computeKnownBits? Is ctlz common enough for this to matter for the places that use InstSimplify directly?

[xbolva00]

No strong opinion, but everybody should agree.

I really dont want to go with “instsimplify -> instcombine -> instsimplify” patches.

[craig.topper]

isKnownNegative is just a wrapper around computeKnownBits. So if we are to do this in InstSimplify we might as well take the whole code that was already flagged in InstCombineCalls that can already do this and more.

KnownBits Known = IC.computeKnownBits(Op0, 0, &II);                                                                                                                                                  
                                                                                                                                                                                                     
// Create a mask for bits above (ctlz) or below (cttz) the first known one.                                                                                                                          
unsigned PossibleZeros = IsTZ ? Known.countMaxTrailingZeros()                                                                                                                                        
                              : Known.countMaxLeadingZeros();                                                                                                                                        
unsigned DefiniteZeros = IsTZ ? Known.countMinTrailingZeros()                                                                                                                                        
                              : Known.countMinLeadingZeros();                                                                                                                                        
                                                                                                                                                                                                     
// 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 (PossibleZeros == DefiniteZeros) {                                                                                                                                                                
  auto *C = ConstantInt::get(Op0->getType(), DefiniteZeros);                                                                                                                                         
  return IC.replaceInstUsesWith(II, C);                                                                                                                                                              
}

[xbolva00]

// FIXME: This should be in InstSimplify because we're replacing an ...

Not sure, if we want to then compute known bits in instcombine just for:

if (!Known.One.isNullValue() ||
    isKnownNonZero(Op0, IC.getDataLayout(), 0, &IC.getAssumptionCache(), &II,
                   &IC.getDominatorTree())) {
  if (!match(II.getArgOperand(1), m_One()))
    return IC.replaceOperand(II, 1, IC.Builder.getTrue());
}

For now I think I will move this code to instcombine.

Enhance isKnownNegative to know that ashr of negative constant is still negative? Then we could remove the match here.

In this case, please feel free to enhance computeKnownBits/computeSignBits.

[xbolva00]

Moved to InstCombine.

[craig.topper]

In D101840#2736994, @xbolva00 wrote:

Moved to InstCombine.

Your test already passes before your change. If the Known bits is negative, PossibleZeros and DefiniteZeros will both be 0 which triggers the PossibleZeros == DefiniteZeros case.

[xbolva00]

In D101840#2737160, @craig.topper wrote:

In D101840#2736994, @xbolva00 wrote:

Moved to InstCombine.

Your test already passes before your change. If the Known bits is negative, PossibleZeros and DefiniteZeros will both be 0 which triggers the PossibleZeros == DefiniteZeros case.

ah, yes.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

if (SPF == SPF_ABS || SPF == SPF_NABS)
       return IC.replaceOperand(II, 0, X);
 
     if (match(Op0, m_Intrinsic<Intrinsic::abs>(m_Value(X))))
       return IC.replaceOperand(II, 0, X);
   }
 
   KnownBits Known = IC.computeKnownBits(Op0, 0, &II);
 
+  if (!IsTZ && Known.isNegative()) {
+    // ctlz(x) -> 0 if x is known negative.
+    auto *C = Constant::getNullValue(Op0->getType());
+    return IC.replaceInstUsesWith(II, C);
+  }
+
   // Create a mask for bits above (ctlz) or below (cttz) the first known one.
   unsigned PossibleZeros = IsTZ ? Known.countMaxTrailingZeros()
                                 : Known.countMaxLeadingZeros();
   unsigned DefiniteZeros = IsTZ ? Known.countMinTrailingZeros()
                                 : Known.countMinLeadingZeros();
 
   // If all bits above (ctlz) or below (cttz) the first known one are known
   // zero, this value is constant.

llvm/test/Transforms/InstCombine/ctlz.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -instcombine -S < %s | FileCheck %s
+declare i32 @llvm.ctlz.i32(i32, i1)
+declare void @llvm.assume(i1)
+declare void @use(i32)
+
+define i32 @ctlz_sext_negative_zero_undef(i16 %x) {
+; CHECK-LABEL: @ctlz_sext_negative_zero_undef(
+; CHECK-NEXT:    [[ASSUME:%.*]] = icmp slt i16 [[X:%.*]], 0
+; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUME]])
+; CHECK-NEXT:    ret i32 0
+;
+  %assume = icmp slt i16 %x, 0
+  call void @llvm.assume(i1 %assume)
+  %s = sext i16 %x to i32
+  %c = call i32 @llvm.ctlz.i32(i32 %s, i1 true)
+  ret i32 %c
+}
+
+define i32 @ctlz_negative_zero_undef(i32 %x) {
+; CHECK-LABEL: @ctlz_negative_zero_undef(
+; CHECK-NEXT:    [[ASSUME:%.*]] = icmp slt i32 [[X:%.*]], 0
+; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUME]])
+; CHECK-NEXT:    ret i32 0
+;
+  %assume = icmp slt i32 %x, 0
+  call void @llvm.assume(i1 %assume)
+  %c = call i32 @llvm.ctlz.i32(i32 %x, i1 true)
+  ret i32 %c
+}
+
+define i32 @ctlz_negative_zero_def(i32 %x) {
+; CHECK-LABEL: @ctlz_negative_zero_def(
+; CHECK-NEXT:    [[ASSUME:%.*]] = icmp slt i32 [[X:%.*]], 0
+; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUME]])
+; CHECK-NEXT:    ret i32 0
+;
+  %assume = icmp slt i32 %x, 0
+  call void @llvm.assume(i1 %assume)
+  %c = call i32 @llvm.ctlz.i32(i32 %x, i1 false)
+  ret i32 %c
+}
+
+define i32 @ctlz_sext_negative_zero_def(i16 %x) {
+; CHECK-LABEL: @ctlz_sext_negative_zero_def(
+; CHECK-NEXT:    [[ASSUME:%.*]] = icmp slt i16 [[X:%.*]], 0
+; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUME]])
+; CHECK-NEXT:    ret i32 0
+;
+  %assume = icmp slt i16 %x, 0
+  call void @llvm.assume(i1 %assume)
+  %s = sext i16 %x to i32
+  %c = call i32 @llvm.ctlz.i32(i32 %s, i1 false)
+  ret i32 %c
+}
+
+define i32 @ctlz_sext_negative_zero_undef_extra_use(i16 %x) {
+; CHECK-LABEL: @ctlz_sext_negative_zero_undef_extra_use(
+; CHECK-NEXT:    [[ASSUME:%.*]] = icmp slt i16 [[X:%.*]], 0
+; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUME]])
+; CHECK-NEXT:    [[S:%.*]] = sext i16 [[X]] to i32
+; CHECK-NEXT:    call void @use(i32 [[S]])
+; CHECK-NEXT:    ret i32 0
+;
+  %assume = icmp slt i16 %x, 0
+  call void @llvm.assume(i1 %assume)
+  %s = sext i16 %x to i32
+  call void @use(i32 %s)
+  %c = call i32 @llvm.ctlz.i32(i32 %s, i1 true)
+  ret i32 %c
+}

llvm/test/Transforms/InstSimplify/call.ll

 ; CHECK-LABEL: @ctlz_ashr_sign_bit_vec(
 ; CHECK-NEXT:    ret <3 x i33> zeroinitializer
 ;
   %s = ashr <3 x i33> <i33 4294967296, i33 undef, i33 4294967296>, %x
   %r = call <3 x i33> @llvm.ctlz.v3i33(<3 x i33> %s, i1 true)
   ret <3 x i33> %r
 }
 
-define i32 @ctlz_sext_negative_zero_undef(i16 %x) {
-; CHECK-LABEL: @ctlz_sext_negative_zero_undef(
-; CHECK-NEXT:    [[ASSUME:%.*]] = icmp slt i16 [[X:%.*]], 0
-; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUME]])
-; CHECK-NEXT:    [[S:%.*]] = sext i16 [[X]] to i32
-; CHECK-NEXT:    [[C:%.*]] = call i32 @llvm.ctlz.i32(i32 [[S]], i1 true)
-; CHECK-NEXT:    ret i32 [[C]]
-;
-  %assume = icmp slt i16 %x, 0
-  call void @llvm.assume(i1 %assume)
-  %s = sext i16 %x to i32
-  %c = call i32 @llvm.ctlz.i32(i32 %s, i1 true)
-  ret i32 %c
-}
-
-define i32 @ctlz_negative_zero_undef(i32 %x) {
-; CHECK-LABEL: @ctlz_negative_zero_undef(
-; CHECK-NEXT:    [[ASSUME:%.*]] = icmp slt i32 [[X:%.*]], 0
-; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUME]])
-; CHECK-NEXT:    [[C:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X]], i1 true)
-; CHECK-NEXT:    ret i32 [[C]]
-;
-  %assume = icmp slt i32 %x, 0
-  call void @llvm.assume(i1 %assume)
-  %c = call i32 @llvm.ctlz.i32(i32 %x, i1 true)
-  ret i32 %c
-}
-
-define i32 @ctlz_negative_zero_def(i32 %x) {
-; CHECK-LABEL: @ctlz_negative_zero_def(
-; CHECK-NEXT:    [[ASSUME:%.*]] = icmp slt i32 [[X:%.*]], 0
-; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUME]])
-; CHECK-NEXT:    [[C:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X]], i1 false)
-; CHECK-NEXT:    ret i32 [[C]]
-;
-  %assume = icmp slt i32 %x, 0
-  call void @llvm.assume(i1 %assume)
-  %c = call i32 @llvm.ctlz.i32(i32 %x, i1 false)
-  ret i32 %c
-}
-
-define i32 @ctlz_sext_negative_zero_def(i16 %x) {
-; CHECK-LABEL: @ctlz_sext_negative_zero_def(
-; CHECK-NEXT:    [[ASSUME:%.*]] = icmp slt i16 [[X:%.*]], 0
-; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUME]])
-; CHECK-NEXT:    [[S:%.*]] = sext i16 [[X]] to i32
-; CHECK-NEXT:    [[C:%.*]] = call i32 @llvm.ctlz.i32(i32 [[S]], i1 false)
-; CHECK-NEXT:    ret i32 [[C]]
-;
-  %assume = icmp slt i16 %x, 0
-  call void @llvm.assume(i1 %assume)
-  %s = sext i16 %x to i32
-  %c = call i32 @llvm.ctlz.i32(i32 %s, i1 false)
-  ret i32 %c
-}
-
-declare void @use(i32)
-define i32 @ctlz_sext_negative_zero_undef_extra_use(i16 %x) {
-; CHECK-LABEL: @ctlz_sext_negative_zero_undef_extra_use(
-; CHECK-NEXT:    [[ASSUME:%.*]] = icmp slt i16 [[X:%.*]], 0
-; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUME]])
-; CHECK-NEXT:    [[S:%.*]] = sext i16 [[X]] to i32
-; CHECK-NEXT:    call void @use(i32 [[S]])
-; CHECK-NEXT:    [[C:%.*]] = call i32 @llvm.ctlz.i32(i32 [[S]], i1 true)
-; CHECK-NEXT:    ret i32 [[C]]
-;
-  %assume = icmp slt i16 %x, 0
-  call void @llvm.assume(i1 %assume)
-  %s = sext i16 %x to i32
-  call void @use(i32 %s)
-  %c = call i32 @llvm.ctlz.i32(i32 %s, i1 true)
-  ret i32 %c
-}
-
 attributes #0 = { nobuiltin readnone }