Index: include/llvm/Transforms/Utils/SimplifyLibCalls.h
===================================================================
--- include/llvm/Transforms/Utils/SimplifyLibCalls.h
+++ include/llvm/Transforms/Utils/SimplifyLibCalls.h
@@ -137,6 +137,7 @@
 
   // 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);
Index: lib/Analysis/TargetLibraryInfo.cpp
===================================================================
--- lib/Analysis/TargetLibraryInfo.cpp
+++ lib/Analysis/TargetLibraryInfo.cpp
@@ -986,6 +986,9 @@
   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());
 
@@ -995,9 +998,6 @@
     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:
Index: lib/Transforms/Utils/SimplifyLibCalls.cpp
===================================================================
--- lib/Transforms/Utils/SimplifyLibCalls.cpp
+++ lib/Transforms/Utils/SimplifyLibCalls.cpp
@@ -1544,6 +1544,32 @@
   return B.CreateSelect(Cond, V, B.getInt32(0));
 }
 
+Value *LibCallSimplifier::optimizeFls(CallInst *CI, IRBuilder<> &B) {
+  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(ty c) -> sizeInBits(ty) - ctlz(c)
+    return B.getInt32(CI->getType()->getBitWidth() -
+                      CI->getValue().countLeadingZeros());
+  }
+
+  // ffs(x) -> x != 0 ? (i32)(sizeInBits(x) - llvm.ctlz(x)) : 0
+  Type *ArgType = Op->getType();
+  Value *F =
+      Intrinsic::getDeclaration(CI->getCalledFunction()->getParent(),
+                                Intrinsic::ctlz, ArgType);
+  Value *V = B.CreateCall(F, {Op, B.getTrue()}, "ctlz");
+  V = B.CreateSub(ConstantInt::get(V->getType(),
+                                   ArgType->getIntegerBitWidth()), V);
+  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::optimizeAbs(CallInst *CI, IRBuilder<> &B) {
   // abs(x) -> x >s -1 ? x : -x
   Value *Op = CI->getArgOperand(0);
@@ -2080,6 +2106,10 @@
     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:
Index: test/Transforms/InstCombine/fls.ll
===================================================================
--- /dev/null
+++ test/Transforms/InstCombine/fls.ll
@@ -0,0 +1,50 @@
+; 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 true)
+; CHECK-NEXT:  %1 = sub nsw i64 64, %ctlz
+; CHECK-NEXT:  %2 = trunc i64 %1 to i32
+; CHECK-NEXT:  %3 = icmp ne i64 %z, 0
+; CHECK-NEXT:  %4 = select i1 %3, i32 %2, i32 0
+; CHECK-NEXT:  ret i32 %4
+
+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)