diff --git a/llvm/lib/Transforms/IPO/AlwaysInliner.cpp b/llvm/lib/Transforms/IPO/AlwaysInliner.cpp
--- a/llvm/lib/Transforms/IPO/AlwaysInliner.cpp
+++ b/llvm/lib/Transforms/IPO/AlwaysInliner.cpp
@@ -108,8 +108,10 @@
   // Delete the non-comdat ones from the module and also from our vector.
   auto NonComdatBegin = partition(
       InlinedFunctions, [&](Function *F) { return F->hasComdat(); });
-  for (Function *F : make_range(NonComdatBegin, InlinedFunctions.end()))
+  for (Function *F : make_range(NonComdatBegin, InlinedFunctions.end())) {
     M.getFunctionList().erase(F);
+    Changed = true;
+  }
   InlinedFunctions.erase(NonComdatBegin, InlinedFunctions.end());
 
   if (!InlinedFunctions.empty()) {
@@ -117,8 +119,10 @@
     // are not actually dead.
     filterDeadComdatFunctions(M, InlinedFunctions);
     // The remaining functions are actually dead.
-    for (Function *F : InlinedFunctions)
+    for (Function *F : InlinedFunctions) {
       M.getFunctionList().erase(F);
+      Changed = true;
+    }
   }
 
   return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
diff --git a/llvm/test/Transforms/Inline/always-inline-invalidate.ll b/llvm/test/Transforms/Inline/always-inline-invalidate.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/Inline/always-inline-invalidate.ll
@@ -0,0 +1,8 @@
+; RUN: opt -passes='require<no-op-module>,always-inline' -disable-output < %s 2>&1 -debug-pass-manager | FileCheck %s
+
+; CHECK: Invalidating {{.*}} NoOpModuleAnalysis
+; CHECK-NOT: @f
+
+define internal void @f() alwaysinline {
+  unreachable
+}