[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 ↗

(On Diff #81523)

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

[davide]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1558 ↗

(On Diff #81523)

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 ↗

(On Diff #81637)

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

1560 ↗

(On Diff #81637)

"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 ↗

(On Diff #81637)

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 ↗

(On Diff #81662)

Typo: fls, not ffs.

[majnemer]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1558 ↗

(On Diff #81662)

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

[davide]

lib/Transforms/Utils/SimplifyLibCalls.cpp

1558 ↗

(On Diff #81662)

Done before committing. Thanks for your comment!

llvm/trunk/include/llvm/Transforms/Utils/SimplifyLibCalls.h

private:
   Value *optimizeFMinFMax(CallInst *CI, IRBuilder<> &B);
   Value *optimizeLog(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);

llvm/trunk/lib/Analysis/TargetLibraryInfo.cpp

bool TargetLibraryInfoImpl::isValidProtoForLibFunc(const FunctionType &FTy,
   case LibFunc::powl:
     return (NumParams == 2 && FTy.getReturnType()->isFloatingPointTy() &&
             FTy.getReturnType() == FTy.getParamType(0) &&
             FTy.getReturnType() == FTy.getParamType(1));
 
   case LibFunc::ffs:
   case LibFunc::ffsl:
   case LibFunc::ffsll:
+  case LibFunc::fls:
+  case LibFunc::flsl:
+  case LibFunc::flsll:
     return (NumParams == 1 && FTy.getReturnType()->isIntegerTy(32) &&
             FTy.getParamType(0)->isIntegerTy());
 
   case LibFunc::isdigit:
   case LibFunc::isascii:
   case LibFunc::toascii:
     return (NumParams == 1 && FTy.getReturnType()->isIntegerTy(32) &&
             FTy.getReturnType() == FTy.getParamType(0));
 
-  case LibFunc::fls:
-  case LibFunc::flsl:
-  case LibFunc::flsll:
   case LibFunc::abs:
   case LibFunc::labs:
   case LibFunc::llabs:
     return (NumParams == 1 && FTy.getReturnType()->isIntegerTy() &&
             FTy.getReturnType() == FTy.getParamType(0));
 
   case LibFunc::cxa_atexit:
     return (NumParams == 3 && FTy.getReturnType()->isIntegerTy() &&

llvm/trunk/lib/Transforms/Utils/SimplifyLibCalls.cpp

Value *LibCallSimplifier::optimizeFFS(CallInst *CI, IRBuilder<> &B) {
   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) {
+  // fls(x) -> (i32)(sizeInBits(x) - llvm.ctlz(x, false))
+  Value *Op = CI->getArgOperand(0);
+  Type *ArgType = Op->getType();
+  Value *F = Intrinsic::getDeclaration(CI->getCalledFunction()->getParent(),
+                                       Intrinsic::ctlz, ArgType);
+  Value *V = B.CreateCall(F, {Op, B.getFalse()}, "ctlz");
+  V = B.CreateSub(ConstantInt::get(V->getType(), ArgType->getIntegerBitWidth()),
+                  V);
+  return B.CreateIntCast(V, CI->getType(), false);
+}
+
 Value *LibCallSimplifier::optimizeAbs(CallInst *CI, IRBuilder<> &B) {
   // abs(x) -> x >s -1 ? x : -x
   Value *Op = CI->getArgOperand(0);
   Value *Pos =
       B.CreateICmpSGT(Op, Constant::getAllOnesValue(Op->getType()), "ispos");
   Value *Neg = B.CreateNeg(Op, "neg");
   return B.CreateSelect(Pos, Op, Neg);
 }
if (TLI->getLibFunc(*Callee, Func) && TLI->has(Func)) {
     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);

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

+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+target triple = "x86_64-unknown-freebsd11.0"
+
+
+; CHECK-LABEL: define i32 @myfls(
+; CHECK: ret i32 6
+; CHECK: }
+
+define i32 @myfls() {
+entry:
+  %call = call i32 @fls(i32 42)
+  ret i32 %call
+}
+
+; CHECK-LABEL: define i32 @myflsl(
+; CHECK: ret i32 6
+; CHECK: }
+
+define i32 @myflsl() {
+  %patatino = call i32 @flsl(i64 42)
+  ret i32 %patatino
+}
+
+; CHECK-LABEL: define i32 @myflsll(
+; CHECK: ret i32 6
+; CHECK: }
+
+define i32 @myflsll() {
+  %whatever = call i32 @flsll(i64 42)
+  ret i32 %whatever
+}
+
+; Lower to llvm.ctlz() if the argument is not a constant
+; CHECK-LABEL: define i32 @flsnotconst(
+; CHECK-NEXT:  %ctlz = call i64 @llvm.ctlz.i64(i64 %z, i1 false)
+; CHECK-NEXT:  %1 = sub nsw i64 64, %ctlz
+; CHECK-NEXT:  %2 = trunc i64 %1 to i32
+; CHECK-NEXT:  ret i32 %2
+
+define i32 @flsnotconst(i64 %z) {
+  %goo = call i32 @flsl(i64 %z)
+  ret i32 %goo
+}
+
+declare i32 @fls(i32)
+declare i32 @flsl(i64)
+declare i32 @flsll(i64)