Index: llvm/lib/Transforms/Utils/InlineFunction.cpp
===================================================================
--- llvm/lib/Transforms/Utils/InlineFunction.cpp
+++ llvm/lib/Transforms/Utils/InlineFunction.cpp
@@ -921,14 +921,20 @@
     if (!I)
       continue;
 
+    // Only update scopes when we find them in the map. If they are not, it is
+    // because we already handled that instruction before. This is faster than
+    // tracking which instructions we already updated.
     if (MDNode *M = I->getMetadata(LLVMContext::MD_alias_scope))
-      I->setMetadata(LLVMContext::MD_alias_scope, MDMap[M]);
+      if (MDNode *MNew = MDMap.lookup(M))
+        I->setMetadata(LLVMContext::MD_alias_scope, MNew);
 
     if (MDNode *M = I->getMetadata(LLVMContext::MD_noalias))
-      I->setMetadata(LLVMContext::MD_noalias, MDMap[M]);
+      if (MDNode *MNew = MDMap.lookup(M))
+        I->setMetadata(LLVMContext::MD_noalias, MNew);
 
     if (auto *Decl = dyn_cast<NoAliasScopeDeclInst>(I))
-      Decl->setScopeList(MDMap[Decl->getScopeList()]);
+      if (MDNode *MNew = MDMap.lookup(Decl->getScopeList()))
+        Decl->setScopeList(MNew);
   }
 }
 
Index: llvm/test/Transforms/Inline/noalias3.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/Inline/noalias3.ll
@@ -0,0 +1,35 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature
+; RUN: opt -inline -S < %s | FileCheck %s
+
+define void @caller(i8* %ptr) {
+; CHECK-LABEL: define {{[^@]+}}@caller
+; CHECK-SAME: (i8* [[PTR:%.*]]) {
+; CHECK-NEXT:    [[I_I:%.*]] = load i8, i8* [[PTR]], align 1, !alias.scope !0
+; CHECK-NEXT:    ret void
+;
+  call void @callee(i8* %ptr)
+  ret void
+}
+
+define void @callee(i8* %ptr) {
+; CHECK-LABEL: define {{[^@]+}}@callee
+; CHECK-SAME: (i8* [[PTR:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[I:%.*]] = load i8, i8* [[PTR]], align 1, !alias.scope !3
+; CHECK-NEXT:    br label [[DUMMY:%.*]]
+; CHECK:       dummy:
+; CHECK-NEXT:    [[I_COPY:%.*]] = phi i8 [ [[I]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret void
+;
+entry:
+  %i = load i8, i8* %ptr, !alias.scope !0
+  br label %dummy
+
+dummy:
+  %i.copy = phi i8 [ %i, %entry ]
+  ret void
+}
+
+!0 = !{!1}
+!1 = distinct !{!1, !2}
+!2 = distinct !{!2}