[InstCombine] Teach how to fold a select into a cttz/ctlz with the 'is_zero_undef' flag cleared.

[andreadb]

Summary

Hi all,

This patch teaches the Instruction Combiner how to fold a cttz/ctlz followed by a icmp plus select into a single cttz/ctlz with flag 'is_zero_undef' cleared.

Example:

%a = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
%b = icmp ne i32 %x, 0
%c = select i1 %b, i32 %a, i32 32

In this example, the condition value used by the select instruction compares value %x for equality against zero.
Value %x is also used by the call to the llvm intrinsic cttz. So, the select instruction would propagate the sizeof in bits of %x (i.e. 32) if %x is zero.

The entire cttz+icmp+select sequence can be safely folded into:

%c = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)

Added test InstCombine/select-cmp-cttz-ctlz.ll.

Please let me know if ok to submit.

Thanks,
Andrea

[majnemer]

lib/Transforms/InstCombine/InstCombineSelect.cpp

465–468

@llvm.cttz.* and @llvm.ctlz.* both accept vector types as arguments. You may want to switch from m_ConstantInt to m_APInt because it will match against a splatted ConstantVector as well.

You could go even further and use m_SpecificInt(II->getType()->getScalarSizeInBits()) to save you a check later on.

478–483

You could use m_Specific(CmpLHS) instead of m_Value(V) and V != CmpLHS.

492–498

I wonder if it might be nicer to clone II and then fixup the clone.
Something like:

NewI = II->clone();
NewI->setOperand(1, Constant::getNullValue(II->getArgOperand(1)->getType()));

This formulation also has the advantage of working with vector types.

[pete]

Hi Andrea

Is this intended to replace the work in CodeGenPrepare:r225274?

If you match this to a single intrinsic call in instcombine then it would be relatively simple for SimplifyCFG to then speculate it with existing code. Then we can remove the code from CGP?

Thanks,
Pete

[andreadb]

Hi Pete,

In D6891#106740, @pete wrote:

Hi Andrea

Is this intended to replace the work in CodeGenPrepare:r225274?

No, It applies to a different scenario where the cttz/ctlz is always evaluated.

Something like:

unsigned int foo(unsigned int x) {
  unsigned int count = __builtin_ctz(x);
  return x ? count : 32;
}

Where the count trailing zeroes is always evaluated before reaching the conditional statement (which is then converted into a select).

The logic added in CodeGenPrepare would work in a different scenario (see below):

unsigned int bar(unsigned int x) {
  return x ? __builtin_ctz(x) : 32;
}

In this case, the builtin call is not always executed since it is not dominating the control flow (it is in the 'then' part). Depending on the target, it may or may not be beneficial to speculate that builtin call.

If you match this to a single intrinsic call in instcombine then it would be relatively simple for SimplifyCFG to then speculate it with existing code. Then we can remove the code from CGP?

The problem with implementing that logic into SimplifyCFG is that we need to query the target to check if calls to cttz/ctlz are cheap to speculate. Therefore, in code review D6679 it was suggested by the reviewers to move that logic into CodeGenPrepare.

I hope this clears up any misunderstanding.

-Andrea

Thanks,
Pete

[pete]

Hi Andrea

[andreadb]

Hi David,

thanks for the review.
I uploaded a new version of the patch that should address all your comments.

Please let me know what you think.

Thanks again for your time.
-Andrea

[andreadb]

Sorry, I just realized that I uploaded a wrong version of the patch.
This is the correct version of the patch.
Again, sorry for the confusion.

-Andrea

[andreadb]

Ping.

[RKSimon]

Thanks Andrea, I'd prefer David to give the final approval but this patch works fine with my local tests.

[andreadb]

Ping * 2.

[hfinkel]

LGTM.

[andreadb]

Thanks Hal,

Committed revision 227197.

lib/Transforms/InstCombine/InstCombineSelect.cpp

static Value *foldSelectICmpAndOr(const SelectInst &SI, Value *TrueVal,
   ICmpInst::Predicate Pred = IC->getPredicate();
   if ((Pred == ICmpInst::ICMP_NE && OrOnFalseVal) ||
       (Pred == ICmpInst::ICMP_EQ && OrOnTrueVal))
     V = Builder->CreateXor(V, *C2);
 
   return Builder->CreateOr(V, Y);
 }
 
+/// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single
+/// call to cttz/ctlz with flag 'is_zero_undef' cleared.
+///
+/// For example, we can fold the following code sequence:
+/// \code
+///   %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
+///   %1 = icmp ne i32 %x, 0
+///   %2 = select i1 %1, i32 %0, i32 32
+/// \code
+/// 
+/// into:
+///   %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
+static Value *foldSelectCttzCtlz(ICmpInst *ICI, Value *TrueVal, Value *FalseVal,
+                                  InstCombiner::BuilderTy *Builder) {
+  ICmpInst::Predicate Pred = ICI->getPredicate();
+  Value *CmpLHS = ICI->getOperand(0);
+  Value *CmpRHS = ICI->getOperand(1);
+
+  // Check if the condition value compares a value for equality against zero.
+  if (!ICI->isEquality() || !match(CmpRHS, m_Zero()))
+    return nullptr;
+
+  Value *Count = FalseVal;
+  Value *ValueOnZero = TrueVal;
+  if (Pred == ICmpInst::ICMP_NE)
+    std::swap(Count, ValueOnZero);
+
+  // Skip zero extend/truncate.
+  Value *V = nullptr;
+  if (match(Count, m_ZExt(m_Value(V))) ||
+      match(Count, m_Trunc(m_Value(V))))
+    Count = V;
+
+  // Check if the value propagated on zero is a constant number equal to the
+  // sizeof in bits of 'Count'.
+  unsigned SizeOfInBits = Count->getType()->getScalarSizeInBits();
+  if (!match(ValueOnZero, m_SpecificInt(SizeOfInBits)))
+    return nullptr;
+
+  // Check that 'Count' is a call to intrinsic cttz/ctlz. Also check that the
+  // input to the cttz/ctlz is used as LHS for the compare instruction.
+  if (match(Count, m_Intrinsic<Intrinsic::cttz>(m_Specific(CmpLHS))) ||
+      match(Count, m_Intrinsic<Intrinsic::ctlz>(m_Specific(CmpLHS)))) {
+    IntrinsicInst *II = cast<IntrinsicInst>(Count);
+    IRBuilder<> Builder(II);
+    if (cast<ConstantInt>(II->getArgOperand(1))->isOne()) {
+      // Explicitly clear the 'undef_on_zero' flag.
+      IntrinsicInst *NewI = cast<IntrinsicInst>(II->clone());
+      Type *Ty = NewI->getArgOperand(1)->getType();
+      NewI->setArgOperand(1, Constant::getNullValue(Ty));
+      Builder.Insert(NewI);
+      Count = NewI;
+    }
+
+    return Builder.CreateZExtOrTrunc(Count, ValueOnZero->getType());
+  }
+
+  return nullptr;
+}
+
 /// visitSelectInstWithICmp - Visit a SelectInst that has an
 /// ICmpInst as its first operand.
 ///
 Instruction *InstCombiner::visitSelectInstWithICmp(SelectInst &SI,
                                                    ICmpInst *ICI) {
   bool Changed = false;
   ICmpInst::Predicate Pred = ICI->getPredicate();
   Value *CmpLHS = ICI->getOperand(0);
if (IsBitTest) {
       if (V)
         return ReplaceInstUsesWith(SI, V);
     }
   }
 
   if (Value *V = foldSelectICmpAndOr(SI, TrueVal, FalseVal, Builder))
     return ReplaceInstUsesWith(SI, V);
 
+  if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder))
+    return ReplaceInstUsesWith(SI, V);
+
   return Changed ? &SI : nullptr;
 }
 
 
 /// CanSelectOperandBeMappingIntoPredBlock - SI is a select whose condition is a
 /// PHI node (but the two may be in different blocks).  See if the true/false
 /// values (V) are live in all of the predecessor blocks of the PHI.  For
 /// example, cases like this cannot be mapped:

test/Transforms/InstCombine/intrinsics.ll

 
 define i32 @ctlz_select(i32 %Value) nounwind {
   %tobool = icmp ne i32 %Value, 0
   %ctlz = call i32 @llvm.ctlz.i32(i32 %Value, i1 true)
   %s = select i1 %tobool, i32 %ctlz, i32 32
   ret i32 %s
 
 ; CHECK-LABEL: @ctlz_select(
-; CHECK: select i1 %tobool, i32 %ctlz, i32 32
+; CHECK-NEXT: call i32 @llvm.ctlz.i32(i32 %Value, i1 false)
+; CHECK-NEXT: ret i32
 }
 
 define i32 @cttz_select(i32 %Value) nounwind {
   %tobool = icmp ne i32 %Value, 0
   %cttz = call i32 @llvm.cttz.i32(i32 %Value, i1 true)
   %s = select i1 %tobool, i32 %cttz, i32 32
   ret i32 %s
 
 ; CHECK-LABEL: @cttz_select(
-; CHECK: select i1 %tobool, i32 %cttz, i32 32
+; CHECK-NEXT: call i32 @llvm.cttz.i32(i32 %Value, i1 false)
+; CHECK-NEXT: ret i32
 }

test/Transforms/InstCombine/select-cmp-cttz-ctlz.ll

+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+; This test is to verify that the instruction combiner is able to fold
+; a cttz/ctlz followed by a icmp + select into a single cttz/ctlz with
+; the 'is_zero_undef' flag cleared.
+
+define i16 @test1(i16 %x) {
+; CHECK-LABEL: @test1(
+; CHECK: [[VAR:%[a-zA-Z0-9]+]] = tail call i16 @llvm.ctlz.i16(i16 %x, i1 false)
+; CHECK-NEXT: ret i16 [[VAR]]
+entry:
+  %0 = tail call i16 @llvm.ctlz.i16(i16 %x, i1 true)
+  %tobool = icmp ne i16 %x, 0
+  %cond = select i1 %tobool, i16 %0, i16 16
+  ret i16 %cond
+}
+
+define i32 @test2(i32 %x) {
+; CHECK-LABEL: @test2(
+; CHECK: [[VAR:%[a-zA-Z0-9]+]] = tail call i32 @llvm.ctlz.i32(i32 %x, i1 false)
+; CHECK-NEXT: ret i32 [[VAR]]
+entry:
+  %0 = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
+  %tobool = icmp ne i32 %x, 0
+  %cond = select i1 %tobool, i32 %0, i32 32
+  ret i32 %cond
+}
+
+define i64 @test3(i64 %x) {
+; CHECK-LABEL: @test3(
+; CHECK: [[VAR:%[a-zA-Z0-9]+]] = tail call i64 @llvm.ctlz.i64(i64 %x, i1 false)
+; CHECK-NEXT: ret i64 [[VAR]]
+entry:
+  %0 = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
+  %tobool = icmp ne i64 %x, 0
+  %cond = select i1 %tobool, i64 %0, i64 64
+  ret i64 %cond
+}
+
+define i16 @test4(i16 %x) {
+; CHECK-LABEL: @test4(
+; CHECK: [[VAR:%[a-zA-Z0-9]+]] = tail call i16 @llvm.ctlz.i16(i16 %x, i1 false)
+; CHECK-NEXT: ret i16 [[VAR]]
+entry:
+  %0 = tail call i16 @llvm.ctlz.i16(i16 %x, i1 true)
+  %tobool = icmp eq i16 %x, 0
+  %cond = select i1 %tobool, i16 16, i16 %0
+  ret i16 %cond
+}
+
+define i32 @test5(i32 %x) {
+; CHECK-LABEL: @test5(
+; CHECK: [[VAR:%[a-zA-Z0-9]+]] = tail call i32 @llvm.ctlz.i32(i32 %x, i1 false)
+; CHECK-NEXT: ret i32 [[VAR]]
+entry:
+  %0 = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
+  %tobool = icmp eq i32 %x, 0
+  %cond = select i1 %tobool, i32 32, i32 %0
+  ret i32 %cond
+}
+
+define i64 @test6(i64 %x) {
+; CHECK-LABEL: @test6(
+; CHECK: [[VAR:%[a-zA-Z0-9]+]] = tail call i64 @llvm.ctlz.i64(i64 %x, i1 false)
+; CHECK-NEXT: ret i64 [[VAR]]
+entry:
+  %0 = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
+  %tobool = icmp eq i64 %x, 0
+  %cond = select i1 %tobool, i64 64, i64 %0
+  ret i64 %cond
+}
+
+define i16 @test1b(i16 %x) {
+; CHECK-LABEL: @test1b(
+; CHECK: [[VAR:%[a-zA-Z0-9]+]] = tail call i16 @llvm.cttz.i16(i16 %x, i1 false)
+; CHECK-NEXT: ret i16 [[VAR]]
+entry:
+  %0 = tail call i16 @llvm.cttz.i16(i16 %x, i1 true)
+  %tobool = icmp ne i16 %x, 0
+  %cond = select i1 %tobool, i16 %0, i16 16
+  ret i16 %cond
+}
+
+define i32 @test2b(i32 %x) {
+; CHECK-LABEL: @test2b(
+; CHECK: [[VAR:%[a-zA-Z0-9]+]] = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
+; CHECK-NEXT: ret i32 [[VAR]]
+entry:
+  %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
+  %tobool = icmp ne i32 %x, 0
+  %cond = select i1 %tobool, i32 %0, i32 32
+  ret i32 %cond
+}
+
+define i64 @test3b(i64 %x) {
+; CHECK-LABEL: @test3b(
+; CHECK: [[VAR:%[a-zA-Z0-9]+]] = tail call i64 @llvm.cttz.i64(i64 %x, i1 false)
+; CHECK-NEXT: ret i64 [[VAR]]
+entry:
+  %0 = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
+  %tobool = icmp ne i64 %x, 0
+  %cond = select i1 %tobool, i64 %0, i64 64
+  ret i64 %cond
+}
+
+define i16 @test4b(i16 %x) {
+; CHECK-LABEL: @test4b(
+; CHECK: [[VAR:%[a-zA-Z0-9]+]] = tail call i16 @llvm.cttz.i16(i16 %x, i1 false)
+; CHECK-NEXT: ret i16 [[VAR]]
+entry:
+  %0 = tail call i16 @llvm.cttz.i16(i16 %x, i1 true)
+  %tobool = icmp eq i16 %x, 0
+  %cond = select i1 %tobool, i16 16, i16 %0
+  ret i16 %cond
+}
+
+define i32 @test5b(i32 %x) {
+; CHECK-LABEL: @test5b(
+; CHECK: [[VAR:%[a-zA-Z0-9]+]] = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
+; CHECK-NEXT: ret i32 [[VAR]]
+entry:
+  %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
+  %tobool = icmp eq i32 %x, 0
+  %cond = select i1 %tobool, i32 32, i32 %0
+  ret i32 %cond
+}
+
+define i64 @test6b(i64 %x) {
+; CHECK-LABEL: @test6b(
+; CHECK: [[VAR:%[a-zA-Z0-9]+]] = tail call i64 @llvm.cttz.i64(i64 %x, i1 false)
+; CHECK-NEXT: ret i64 [[VAR]]
+entry:
+  %0 = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
+  %tobool = icmp eq i64 %x, 0
+  %cond = select i1 %tobool, i64 64, i64 %0
+  ret i64 %cond
+}
+
+define i32 @test1c(i16 %x) {
+; CHECK-LABEL: @test1c(
+; CHECK: [[VAR1:%[a-zA-Z0-9]+]] = tail call i16 @llvm.cttz.i16(i16 %x, i1 false)
+; CHECK-NEXT: [[VAR2:%[a-zA-Z0-9]+]] = zext i16 [[VAR1]] to i32
+; CHECK-NEXT: ret i32 [[VAR2]]
+entry:
+  %0 = tail call i16 @llvm.cttz.i16(i16 %x, i1 true)
+  %cast2 = zext i16 %0 to i32
+  %tobool = icmp ne i16 %x, 0
+  %cond = select i1 %tobool, i32 %cast2, i32 16
+  ret i32 %cond
+}
+
+define i64 @test2c(i16 %x) {
+; CHECK-LABEL: @test2c(
+; CHECK: [[VAR1:%[a-zA-Z0-9]+]] = tail call i16 @llvm.cttz.i16(i16 %x, i1 false)
+; CHECK-NEXT: [[VAR2:%[a-zA-Z0-9]+]] = zext i16 [[VAR1]] to i64
+; CHECK-NEXT: ret i64 [[VAR2]]
+entry:
+  %0 = tail call i16 @llvm.cttz.i16(i16 %x, i1 true)
+  %conv = zext i16 %0 to i64
+  %tobool = icmp ne i16 %x, 0
+  %cond = select i1 %tobool, i64 %conv, i64 16
+  ret i64 %cond
+}
+
+define i64 @test3c(i32 %x) {
+; CHECK-LABEL: @test3c(
+; CHECK: [[VAR1:%[a-zA-Z0-9]+]] = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
+; CHECK-NEXT: [[VAR2:%[a-zA-Z0-9]+]] = zext i32 [[VAR1]] to i64
+; CHECK-NEXT: ret i64 [[VAR2]]
+entry:
+  %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
+  %conv = zext i32 %0 to i64
+  %tobool = icmp ne i32 %x, 0
+  %cond = select i1 %tobool, i64 %conv, i64 32
+  ret i64 %cond
+}
+
+define i32 @test4c(i16 %x) {
+; CHECK-LABEL: @test4c(
+; CHECK: [[VAR1:%[a-zA-Z0-9]+]] = tail call i16 @llvm.ctlz.i16(i16 %x, i1 false)
+; CHECK-NEXT: [[VAR2:%[a-zA-Z0-9]+]] = zext i16 [[VAR1]] to i32
+; CHECK-NEXT: ret i32 [[VAR2]]
+entry:
+  %0 = tail call i16 @llvm.ctlz.i16(i16 %x, i1 true)
+  %cast = zext i16 %0 to i32
+  %tobool = icmp ne i16 %x, 0
+  %cond = select i1 %tobool, i32 %cast, i32 16
+  ret i32 %cond
+}
+
+define i64 @test5c(i16 %x) {
+; CHECK-LABEL: @test5c(
+; CHECK: [[VAR1:%[a-zA-Z0-9]+]] = tail call i16 @llvm.ctlz.i16(i16 %x, i1 false)
+; CHECK-NEXT: [[VAR2:%[a-zA-Z0-9]+]] = zext i16 [[VAR1]] to i64
+; CHECK-NEXT: ret i64 [[VAR2]]
+entry:
+  %0 = tail call i16 @llvm.ctlz.i16(i16 %x, i1 true)
+  %cast = zext i16 %0 to i64
+  %tobool = icmp ne i16 %x, 0
+  %cond = select i1 %tobool, i64 %cast, i64 16
+  ret i64 %cond
+}
+
+define i64 @test6c(i32 %x) {
+; CHECK-LABEL: @test6c(
+; CHECK: [[VAR1:%[a-zA-Z0-9]+]] = tail call i32 @llvm.ctlz.i32(i32 %x, i1 false)
+; CHECK-NEXT: [[VAR2:%[a-zA-Z0-9]+]] = zext i32 [[VAR1]] to i64
+; CHECK-NEXT: ret i64 [[VAR2]]
+entry:
+  %0 = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
+  %cast = zext i32 %0 to i64
+  %tobool = icmp ne i32 %x, 0
+  %cond = select i1 %tobool, i64 %cast, i64 32
+  ret i64 %cond
+}
+
+define i16 @test1d(i64 %x) {
+; CHECK-LABEL: @test1d(
+; CHECK: [[VAR1:%[a-zA-Z0-9]+]] = tail call i64 @llvm.cttz.i64(i64 %x, i1 false)
+; CHECK-NEXT: [[VAR2:%[a-zA-Z0-9]+]] = trunc i64 [[VAR1]] to i16
+; CHECK-NEXT: ret i16 [[VAR2]]
+entry:
+  %0 = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
+  %conv = trunc i64 %0 to i16
+  %tobool = icmp ne i64 %x, 0
+  %cond = select i1 %tobool, i16 %conv, i16 64
+  ret i16 %cond
+}
+
+define i32 @test2d(i64 %x) {
+; CHECK-LABEL: @test2d(
+; CHECK: [[VAR1:%[a-zA-Z0-9]+]] = tail call i64 @llvm.cttz.i64(i64 %x, i1 false)
+; CHECK-NEXT: [[VAR2:%[a-zA-Z0-9]+]] = trunc i64 [[VAR1]] to i32
+; CHECK-NEXT: ret i32 [[VAR2]]
+entry:
+  %0 = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
+  %cast = trunc i64 %0 to i32
+  %tobool = icmp ne i64 %x, 0
+  %cond = select i1 %tobool, i32 %cast, i32 64
+  ret i32 %cond
+}
+
+define i16 @test3d(i32 %x) {
+; CHECK-LABEL: @test3d(
+; CHECK: [[VAR1:%[a-zA-Z0-9]+]] = tail call i32 @llvm.cttz.i32(i32 %x, i1 false)
+; CHECK-NEXT: [[VAR2:%[a-zA-Z0-9]+]] = trunc i32 [[VAR1]] to i16
+; CHECK-NEXT: ret i16 [[VAR2]]
+entry:
+  %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
+  %cast = trunc i32 %0 to i16
+  %tobool = icmp ne i32 %x, 0
+  %cond = select i1 %tobool, i16 %cast, i16 32
+  ret i16 %cond
+}
+
+define i16 @test4d(i64 %x) {
+; CHECK-LABEL: @test4d(
+; CHECK: [[VAR1:%[a-zA-Z0-9]+]] = tail call i64 @llvm.ctlz.i64(i64 %x, i1 false)
+; CHECK-NEXT: [[VAR2:%[a-zA-Z0-9]+]] = trunc i64 [[VAR1]] to i16
+; CHECK-NEXT: ret i16 [[VAR2]]
+entry:
+  %0 = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
+  %cast = trunc i64 %0 to i16
+  %tobool = icmp ne i64 %x, 0
+  %cond = select i1 %tobool, i16 %cast, i16 64
+  ret i16 %cond
+}
+
+define i32 @test5d(i64 %x) {
+; CHECK-LABEL: @test5d(
+; CHECK: [[VAR1:%[a-zA-Z0-9]+]] = tail call i64 @llvm.ctlz.i64(i64 %x, i1 false)
+; CHECK-NEXT: [[VAR2:%[a-zA-Z0-9]+]] = trunc i64 [[VAR1]] to i32
+; CHECK-NEXT: ret i32 [[VAR2]]
+entry:
+  %0 = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
+  %cast = trunc i64 %0 to i32
+  %tobool = icmp ne i64 %x, 0
+  %cond = select i1 %tobool, i32 %cast, i32 64
+  ret i32 %cond
+}
+
+define i16 @test6d(i32 %x) {
+; CHECK-LABEL: @test6d(
+; CHECK: [[VAR1:%[a-zA-Z0-9]+]] = tail call i32 @llvm.ctlz.i32(i32 %x, i1 false)
+; CHECK-NEXT: [[VAR2:%[a-zA-Z0-9]+]] = trunc i32 [[VAR1]] to i16
+; CHECK-NEXT: ret i16 [[VAR2]]
+entry:
+  %0 = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
+  %cast = trunc i32 %0 to i16
+  %tobool = icmp ne i32 %x, 0
+  %cond = select i1 %tobool, i16 %cast, i16 32
+  ret i16 %cond
+}
+
+declare i16 @llvm.ctlz.i16(i16, i1)
+declare i32 @llvm.ctlz.i32(i32, i1)
+declare i64 @llvm.ctlz.i64(i64, i1)
+declare i16 @llvm.cttz.i16(i16, i1)
+declare i32 @llvm.cttz.i32(i32, i1)
+declare i64 @llvm.cttz.i64(i64, i1)