[SimplifyLibCalls] Constant folding for fls, flsl, flsll

[davide]

Summary

This enables constant folding for fls() [FreeBSD specific]. This should be quite straighforward (unless I got the math wrong, which I don't exclude).

Thanks!

[davide]

SimplifyLibCalls needs to know how to translate the pair (DataLayout, C99 type) -> LLVM IR Type in order to make this transformation. Until then, there's no reliable way to know how big a long is and that could cause a wrong constant folding of fls(). I haven't audited all the transformations here, but I wouldn't be surprised if other functions are incorrectly transformed assuming sizes of primitive types.

[davide]

In D14590#623196, @davide wrote:

SimplifyLibCalls needs to know how to translate the pair (DataLayout, C99 type) -> LLVM IR Type in order to make this transformation. Until then, there's no reliable way to know how big a long is and that could cause a wrong constant folding of fls(). I haven't audited all the transformations here, but I wouldn't be surprised if other functions are incorrectly transformed assuming sizes of primitive types.

https://llvm.org/bugs/show_bug.cgi?id=31385

[efriedma]

I'm not sure I follow the issue with long. If we see call i32 @flsl(i32 42) in the IR, "long" must be 32 bits; if we see call i32 @flsl(i64 42) in the IR, "long" must be 64 bits.

[davide]

In D14590#623196, @davide wrote:

SimplifyLibCalls needs to know how to translate the pair (DataLayout, C99 type) -> LLVM IR Type in order to make this transformation. Until then, there's no reliable way to know how big a long is and that could cause a wrong constant folding of fls(). I haven't audited all the transformations here, but I wouldn't be surprised if other functions are incorrectly transformed assuming sizes of primitive types.

https://llvm.org/bugs/show_bug.cgi?id=31385

In D14590#623203, @efriedma wrote:

I'm not sure I follow the issue with long. If we see call i32 @flsl(i32 42) in the IR, "long" must be 32 bits; if we see call i32 @flsl(i64 42) in the IR, "long" must be 64 bits.

You're absolutely right, there's no such problem as we actually have the type. I was under the impression we needed the correspondence with the C type but I was clearly wrong. Well, thanks for catching.
I updated the patch, which also revealed a bug in TargetLibraryInfo while checking the function prototype.
Can you please take a look?

[davide]

1. Fix TargetLibraryInfo prototype checking
2. make the transform correct with flsl() and flsll()
3. Remove now unneeded call to checkIntUnaryReturnAndParam()

[efriedma]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1558

Maybe we should just unconditionally lower fls() to llvm.ctlz()?

[davide]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1558

Hmm, yeah. I decided to do what ffs already does.
Try to constant fold, and if the argument is not a constant, lower to
(x != 0) ? (i32)(sizeInBits(x) - llvm.ctlz()) : 0
Is this what you had in mind, or you wanted to remove the constant folding part completely?

[efriedma]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1551

There isn't much point to keeping this around; the general-case code will constant-fold anyway.

1560

"sizeInBits(x) - llvm.ctlz(x, false)" is equivalent, I think?

[davide]

With llvm.ctlz(x, true) we end up producing slightly smaller code (at least on x86_64 FreeBSD)

i.e.

x != 0 ? (sizeInBits(x) - llvm.ctlz(x, true)) : 0

bsrq    %rdi, %rcx
xorl    $-64, %ecx
addl    $65, %ecx
xorl    %eax, %eax
testq   %rdi, %rdi
cmovnel %ecx, %eax
retq

x != 0 ? (sizeInBits(x) - llvm.ctlz(x, false)) : 0

# BB#0:
        testq   %rdi, %rdi
        je      .LBB0_1
# BB#2:                                 # %cond.false
        bsrq    %rdi, %rax
        xorq    $63, %rax
        jmp     .LBB0_3
.LBB0_1:
        movl    $64, %eax
.LBB0_3:                                # %cond.end
        movl    $64, %ecx
        subl    %eax, %ecx
        xorl    %eax, %eax
        testq   %rdi, %rdi
        cmovnel %ecx, %eax
        retq

sizeInBits(x) - llvm.ctlz(x, false)

# BB#0:
        testq   %rdi, %rdi
        je      .LBB0_1
# BB#2:                                 # %cond.false
        bsrq    %rdi, %rcx
        xorq    $63, %rcx
        jmp     .LBB0_3
.LBB0_1:
        movl    $64, %ecx
.LBB0_3:                                # %cond.end
        movl    $64, %eax
        subl    %ecx, %eax
        retq

Which one do you prefer, 1) or 3) ?

lib/Transforms/Utils/SimplifyLibCalls.cpp

1551

Done.

[efriedma]

That's weird... I would have guessed instcombine would kick in an canonicalize one way or the other. Anyway, the difference between 1 and 3 doesn't really matter.

[davide]

In D14590#624289, @efriedma wrote:

That's weird... I would have guessed instcombine would kick in an canonicalize one way or the other. Anyway, the difference between 1 and 3 doesn't really matter.

I'll go for 3, then.
Slightly related, we seem to produce slightly worse code than gcc-4.2 for ffs(x), see https://godbolt.org/g/CruJtS
I don't think it matters much, but still worth mentioning.

[davide]

Simplified after discussion with Eli

[efriedma]

LGTM with typo fixed.

lib/Transforms/Utils/SimplifyLibCalls.cpp

1550

Typo: fls, not ffs.

[majnemer]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1558

Can't we replace B.getInt32Ty with CI->getType()?

[davide]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1558

Done before committing. Thanks for your comment!

include/llvm/Transforms/Utils/SimplifyLibCalls.h

private:
   Value *optimizeFabs(CallInst *CI, IRBuilder<> &B);
   Value *optimizeFMinFMax(CallInst *CI, IRBuilder<> &B);
   Value *optimizeSqrt(CallInst *CI, IRBuilder<> &B);
   Value *optimizeSinCosPi(CallInst *CI, IRBuilder<> &B);
   Value *optimizeTan(CallInst *CI, IRBuilder<> &B);
 
   // Integer Library Call Optimizations
   Value *optimizeFFS(CallInst *CI, IRBuilder<> &B);
+  Value *optimizeFls(CallInst *CI, IRBuilder<> &B);
   Value *optimizeAbs(CallInst *CI, IRBuilder<> &B);
   Value *optimizeIsDigit(CallInst *CI, IRBuilder<> &B);
   Value *optimizeIsAscii(CallInst *CI, IRBuilder<> &B);
   Value *optimizeToAscii(CallInst *CI, IRBuilder<> &B);
 
   // Formatting and IO Library Call Optimizations
   Value *optimizeErrorReporting(CallInst *CI, IRBuilder<> &B,
                                 int StreamArg = -1);

lib/Transforms/Utils/SimplifyLibCalls.cpp

 
 static bool checkIntUnaryReturnAndParam(Function *Callee) {
   FunctionType *FT = Callee->getFunctionType();
   return FT->getNumParams() == 1 && FT->getReturnType()->isIntegerTy(32) &&
     FT->getParamType(0)->isIntegerTy();
 }
 
 Value *LibCallSimplifier::optimizeFFS(CallInst *CI, IRBuilder<> &B) {
   Function *Callee = CI->getCalledFunction();
   if (!checkIntUnaryReturnAndParam(Callee))
     return nullptr;
   Value *Op = CI->getArgOperand(0);
 
   // Constant fold.
   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
     if (CI->isZero()) // ffs(0) -> 0.
       return B.getInt32(0);
     // ffs(c) -> cttz(c)+1
     return B.getInt32(CI->getValue().countTrailingZeros() + 1);
   }
 
   // ffs(x) -> x != 0 ? (i32)llvm.cttz(x)+1 : 0
   Type *ArgType = Op->getType();
   Value *F =
       Intrinsic::getDeclaration(Callee->getParent(), Intrinsic::cttz, ArgType);
   Value *V = B.CreateCall(F, {Op, B.getTrue()}, "cttz");
   V = B.CreateAdd(V, ConstantInt::get(V->getType(), 1));
   V = B.CreateIntCast(V, B.getInt32Ty(), false);
 
   Value *Cond = B.CreateICmpNE(Op, Constant::getNullValue(ArgType));
   return B.CreateSelect(Cond, V, B.getInt32(0));
 }
 
+Value *LibCallSimplifier::optimizeFls(CallInst *CI, IRBuilder<> &B) {
+  Function *Callee = CI->getCalledFunction();
+  if (!checkIntUnaryReturnAndParam(Callee))
+    return nullptr;
+  Value *Op = CI->getArgOperand(0);
+
+  // Constant fold.
+  if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
+    if (CI->isZero()) // fls(0) -> 0.
+      return B.getInt32(0);
+    // fls(c) -> 32 - ctlz(c)
+    return B.getInt32(32 - CI->getValue().countLeadingZeros());
+  }
+  return nullptr;
+}
+
 Value *LibCallSimplifier::optimizeAbs(CallInst *CI, IRBuilder<> &B) {
   Function *Callee = CI->getCalledFunction();
   FunctionType *FT = Callee->getFunctionType();
   // We require integer(integer) where the types agree.
   if (FT->getNumParams() != 1 || !FT->getReturnType()->isIntegerTy() ||
       FT->getParamType(0) != FT->getReturnType())
     return nullptr;
 

     case LibFunc::sqrtf:
     case LibFunc::sqrt:
     case LibFunc::sqrtl:
       return optimizeSqrt(CI, Builder);
     case LibFunc::ffs:
     case LibFunc::ffsl:
     case LibFunc::ffsll:
       return optimizeFFS(CI, Builder);
+    case LibFunc::fls:
+    case LibFunc::flsl:
+    case LibFunc::flsll:
+      return optimizeFls(CI, Builder);
     case LibFunc::abs:
     case LibFunc::labs:
     case LibFunc::llabs:
       return optimizeAbs(CI, Builder);
     case LibFunc::isdigit:
       return optimizeIsDigit(CI, Builder);
     case LibFunc::isascii:
       return optimizeIsAscii(CI, Builder);

test/Transforms/InstCombine/fls.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target triple = "x86_64-unknown-freebsd11.0"
+
+define i32 @myfls() {
+entry:
+  %call = call i32 @fls(i32 42) #2
+  ret i32 %call
+}
+
+declare i32 @fls(i32)
+
+; CHECK-LABEL: define i32 @myfls(
+; CHECK: ret i32 6
+; CHECK: }