instcombine: Migrate ffs* optimizations

This patch migrates the ffs* optimizations from the simplify-libcalls
pass into the instcombine library call simplifier.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@168571 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 46 insertions, 0 deletions

diff --git a/lib/Transforms/Utils/SimplifyLibCalls.cpp b/lib/Transforms/Utils/SimplifyLibCalls.cpp
index cceec66..dd623dc 100644
--- a/lib/Transforms/Utils/SimplifyLibCalls.cpp
+++ b/lib/Transforms/Utils/SimplifyLibCalls.cpp
@@ -20,6 +20,7 @@
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Function.h"
 #include "llvm/IRBuilder.h"
+#include "llvm/Intrinsics.h"
 #include "llvm/Module.h"
 #include "llvm/LLVMContext.h"
 #include "llvm/Target/TargetLibraryInfo.h"
@@ -1212,6 +1213,43 @@ struct Exp2Opt : public UnsafeFPLibCallOptimization {
   }
 };
 
+//===----------------------------------------------------------------------===//
+// Integer Library Call Optimizations
+//===----------------------------------------------------------------------===//
+
+struct FFSOpt : public LibCallOptimization {
+  virtual Value *callOptimizer(Function *Callee, CallInst *CI, IRBuilder<> &B) {
+    FunctionType *FT = Callee->getFunctionType();
+    // Just make sure this has 2 arguments of the same FP type, which match the
+    // result type.
+    if (FT->getNumParams() != 1 ||
+        !FT->getReturnType()->isIntegerTy(32) ||
+        !FT->getParamType(0)->isIntegerTy())
+      return 0;
+
+    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.CreateCall2(F, Op, B.getFalse(), "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));
+  }
+};
+
 } // End anonymous namespace.
 
 namespace llvm {
@@ -1258,6 +1296,9 @@ class LibCallSimplifierImpl {
   UnaryDoubleFPOpt UnaryDoubleFP, UnsafeUnaryDoubleFP;
   CosOpt Cos; PowOpt Pow; Exp2Opt Exp2;
 
+  // Integer library call optimizations.
+  FFSOpt FFS;
+
   void initOptimizations();
   void addOpt(LibFunc::Func F, LibCallOptimization* Opt);
   void addOpt(LibFunc::Func F1, LibFunc::Func F2, LibCallOptimization* Opt);
@@ -1367,6 +1408,11 @@ void LibCallSimplifierImpl::initOptimizations() {
   Optimizations["llvm.exp2.f80"] = &Exp2;
   Optimizations["llvm.exp2.f64"] = &Exp2;
   Optimizations["llvm.exp2.f32"] = &Exp2;
+
+  // Integer library call optimizations.
+  addOpt(LibFunc::ffs, &FFS);
+  addOpt(LibFunc::ffsl, &FFS);
+  addOpt(LibFunc::ffsll, &FFS);
 }
 
 Value *LibCallSimplifierImpl::optimizeCall(CallInst *CI) {