Index: clang/lib/CodeGen/CodeGenModule.cpp
===================================================================
--- clang/lib/CodeGen/CodeGenModule.cpp
+++ clang/lib/CodeGen/CodeGenModule.cpp
@@ -2855,38 +2855,47 @@
 }
 
 namespace {
-  struct FunctionIsDirectlyRecursive
-      : public ConstStmtVisitor<FunctionIsDirectlyRecursive, bool> {
-    const StringRef Name;
-    const Builtin::Context &BI;
-    FunctionIsDirectlyRecursive(StringRef N, const Builtin::Context &C)
-        : Name(N), BI(C) {}
-
-    bool VisitCallExpr(const CallExpr *E) {
-      const FunctionDecl *FD = E->getDirectCallee();
-      if (!FD)
-        return false;
-      AsmLabelAttr *Attr = FD->getAttr<AsmLabelAttr>();
-      if (Attr && Name == Attr->getLabel())
-        return true;
-      unsigned BuiltinID = FD->getBuiltinID();
-      if (!BuiltinID || !BI.isLibFunction(BuiltinID))
-        return false;
-      StringRef BuiltinName = BI.getName(BuiltinID);
-      if (BuiltinName.startswith("__builtin_") &&
-          Name == BuiltinName.slice(strlen("__builtin_"), StringRef::npos)) {
-        return true;
-      }
+struct FunctionIsDirectlyAlwaysRecursive
+    : public ConstStmtVisitor<FunctionIsDirectlyAlwaysRecursive, bool> {
+  const StringRef Name;
+  const Builtin::Context &BI;
+  FunctionIsDirectlyAlwaysRecursive(StringRef N, const Builtin::Context &C)
+      : Name(N), BI(C) {}
+
+  bool VisitCallExpr(const CallExpr *E) {
+    const FunctionDecl *FD = E->getDirectCallee();
+    if (!FD)
       return false;
-    }
-
-    bool VisitStmt(const Stmt *S) {
-      for (const Stmt *Child : S->children())
-        if (Child && this->Visit(Child))
-          return true;
+    AsmLabelAttr *Attr = FD->getAttr<AsmLabelAttr>();
+    if (Attr && Name == Attr->getLabel())
+      return true;
+    unsigned BuiltinID = FD->getBuiltinID();
+    if (!BuiltinID || !BI.isLibFunction(BuiltinID))
       return false;
+    StringRef BuiltinName = BI.getName(BuiltinID);
+    if (BuiltinName.startswith("__builtin_") &&
+        Name == BuiltinName.slice(strlen("__builtin_"), StringRef::npos)) {
+      return true;
     }
-  };
+    return false;
+  }
+
+  // This is very naive, we should probably use a regular CFG visitor instead.
+  // Basically we check that at least one branch doesn't recurse, to catch the
+  // pattern
+  // if(cond) return special_case(...); else return original_case(...);
+  bool VisitIfStmt(const IfStmt *S) {
+    bool Then = S->getThen() && this->Visit(S->getThen());
+    bool Else = S->getElse() && this->Visit(S->getElse());
+    return Then && Else;
+  }
+
+  bool VisitStmt(const Stmt *S) {
+    return llvm::any_of(S->children(), [this](const Stmt *Child) {
+      return Child && this->Visit(Child);
+    });
+  }
+};
 
   // Make sure we're not referencing non-imported vars or functions.
   struct DLLImportFunctionVisitor
@@ -2952,11 +2961,10 @@
   };
 }
 
-// isTriviallyRecursive - Check if this function calls another
+// isTriviallyAlwaysRecursive - Check if this function always calls another
 // decl that, because of the asm attribute or the other decl being a builtin,
 // ends up pointing to itself.
-bool
-CodeGenModule::isTriviallyRecursive(const FunctionDecl *FD) {
+bool CodeGenModule::isTriviallyAlwaysRecursive(const FunctionDecl *FD) {
   StringRef Name;
   if (getCXXABI().getMangleContext().shouldMangleDeclName(FD)) {
     // asm labels are a special kind of mangling we have to support.
@@ -2968,7 +2976,7 @@
     Name = FD->getName();
   }
 
-  FunctionIsDirectlyRecursive Walker(Name, Context.BuiltinInfo);
+  FunctionIsDirectlyAlwaysRecursive Walker(Name, Context.BuiltinInfo);
   const Stmt *Body = FD->getBody();
   return Body ? Walker.Visit(Body) : false;
 }
@@ -3005,7 +3013,7 @@
   // but a function that calls itself through asm label/`__builtin_` trickery is
   // clearly not equivalent to the real implementation.
   // This happens in glibc's btowc and in some configure checks.
-  return !isTriviallyRecursive(F);
+  return !isTriviallyAlwaysRecursive(F);
 }
 
 bool CodeGenModule::shouldOpportunisticallyEmitVTables() {
Index: clang/test/CodeGen/memmove-always-inline-definition-used.c
===================================================================
--- /dev/null
+++ clang/test/CodeGen/memmove-always-inline-definition-used.c
@@ -0,0 +1,26 @@
+// RUN: %clang_cc1 -triple x86_64-unknown-unknown -S -emit-llvm -o - %s | FileCheck %s
+//
+// Verifies that even at O0, the inline definition of memmove has precedence
+// over the builtin
+
+typedef unsigned long size_t;
+
+#define AVAILABLE_EXTERNALLY extern inline __attribute__((always_inline)) \
+__attribute__((gnu_inline))
+
+AVAILABLE_EXTERNALLY void *memmove(void *a, const void *b, size_t c) {
+  if (c == 1 && a != b) {
+    return __builtin_memcpy(a, b, c);
+  } else
+    return __builtin_memmove(a, b, c);
+}
+
+// CHECK-LABEL: define void @foo
+void foo(void *a, const void *b, size_t c) {
+  // Clang should use the inline definition of memmove here.
+  // CHECK: call void @llvm.memcpy
+  // CHECK: call void @llvm.memmove
+  memmove(a, b, c);
+}
+
+// CHECK-NOT: nobuiltin
Index: llvm/include/llvm/Analysis/InlineCost.h
===================================================================
--- llvm/include/llvm/Analysis/InlineCost.h
+++ llvm/include/llvm/Analysis/InlineCost.h
@@ -272,6 +272,8 @@
 
 /// Minimal filter to detect invalid constructs for inlining.
 InlineResult isInlineViable(Function &Callee);
+/// AlwaysInline allows inlining of recursive function
+InlineResult isAlwaysInlineViable(Function &Callee);
 
 // This pass is used to annotate instructions during the inline process for
 // debugging and analysis. The main purpose of the pass is to see and test
Index: llvm/lib/Analysis/InlineCost.cpp
===================================================================
--- llvm/lib/Analysis/InlineCost.cpp
+++ llvm/lib/Analysis/InlineCost.cpp
@@ -2430,7 +2430,7 @@
   return llvm::InlineCost::get(CA.getCost(), CA.getThreshold());
 }
 
-InlineResult llvm::isInlineViable(Function &F) {
+static InlineResult isInlineViableImpl(Function &F, bool RecursiveIsViable) {
   bool ReturnsTwice = F.hasFnAttribute(Attribute::ReturnsTwice);
   for (BasicBlock &BB : F) {
     // Disallow inlining of functions which contain indirect branches.
@@ -2449,8 +2449,8 @@
       if (!Call)
         continue;
 
-      // Disallow recursive calls.
       Function *Callee = Call->getCalledFunction();
+      // Disallow recursive calls.
       if (&F == Callee)
         return InlineResult::failure("recursive call");
 
@@ -2486,6 +2486,14 @@
   return InlineResult::success();
 }
 
+InlineResult llvm::isInlineViable(Function &F) {
+  return isInlineViableImpl(F, false /* disallow recursive call */);
+}
+
+InlineResult llvm::isAlwaysInlineViable(Function &F) {
+  return isInlineViableImpl(F, false /* allow recursive call */);
+}
+
 // APIs to create InlineParams based on command line flags and/or other
 // parameters.
 
Index: llvm/lib/Transforms/IPO/AlwaysInliner.cpp
===================================================================
--- llvm/lib/Transforms/IPO/AlwaysInliner.cpp
+++ llvm/lib/Transforms/IPO/AlwaysInliner.cpp
@@ -189,7 +189,7 @@
   if (!CB.hasFnAttr(Attribute::AlwaysInline))
     return InlineCost::getNever("no alwaysinline attribute");
 
-  auto IsViable = isInlineViable(*Callee);
+  auto IsViable = isAlwaysInlineViable(*Callee);
   if (!IsViable.isSuccess())
     return InlineCost::getNever(IsViable.getFailureReason());