diff --git a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
--- a/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
+++ b/llvm/lib/Transforms/IPO/ArgumentPromotion.cpp
@@ -150,6 +150,13 @@
   return IRB.CreateBitCast(Ptr, ResElemTy->getPointerTo(AddrSpace));
 }
 
+static void appendUsers(SmallVectorImpl<Value *> &Destination,
+                        SmallPtrSetImpl<Value *> &Visited, Value *V) {
+  for (User *U : V->users())
+    if (Visited.insert(U).second)
+      Destination.push_back(U);
+}
+
 /// DoPromotion - This method actually performs the promotion of the specified
 /// arguments, and returns the new function.  At this point, we know that it's
 /// safe to do so.
@@ -395,13 +402,14 @@
     // instructions (with possible casts and GEPs in between).
 
     SmallVector<Value *, 16> Worklist;
+    SmallPtrSet<Value *, 16> Visited;
     SmallVector<Instruction *, 16> DeadInsts;
-    append_range(Worklist, Arg.users());
+    appendUsers(Worklist, Visited, &Arg);
     while (!Worklist.empty()) {
       Value *V = Worklist.pop_back_val();
       if (isa<BitCastInst>(V) || isa<GetElementPtrInst>(V)) {
         DeadInsts.push_back(cast<Instruction>(V));
-        append_range(Worklist, V->users());
+        appendUsers(Worklist, Visited, V);
         continue;
       }
 
@@ -568,23 +576,18 @@
   SmallVector<Value *, 16> Worklist;
   SmallPtrSet<Value *, 16> Visited;
   SmallVector<LoadInst *, 16> Loads;
-  auto AppendUsers = [&](Value *V) {
-    for (User *U : V->users())
-      if (Visited.insert(U).second)
-        Worklist.push_back(U);
-  };
-  AppendUsers(Arg);
+  appendUsers(Worklist, Visited, Arg);
   while (!Worklist.empty()) {
     Value *V = Worklist.pop_back_val();
     if (isa<BitCastInst>(V)) {
-      AppendUsers(V);
+      appendUsers(Worklist, Visited, V);
       continue;
     }
 
     if (auto *GEP = dyn_cast<GetElementPtrInst>(V)) {
       if (!GEP->hasAllConstantIndices())
         return false;
-      AppendUsers(V);
+      appendUsers(Worklist, Visited, V);
       continue;
     }
 
@@ -715,12 +718,12 @@
 
   // Scan through the uses recursively to make sure the pointer is always used
   // sanely.
-  SmallVector<Value *, 16> WorkList(Arg->users());
-  while (!WorkList.empty()) {
-    Value *V = WorkList.pop_back_val();
+  SmallVector<Value *, 16> Worklist(Arg->users());
+  while (!Worklist.empty()) {
+    Value *V = Worklist.pop_back_val();
     if (isa<GetElementPtrInst>(V) || isa<PHINode>(V)) {
       if (PtrValues.insert(V).second)
-        llvm::append_range(WorkList, V->users());
+        append_range(Worklist, V->users());
     } else if (StoreInst *Store = dyn_cast<StoreInst>(V)) {
       Stores.push_back(Store);
     } else if (!isa<LoadInst>(V)) {
diff --git a/llvm/test/Transforms/ArgumentPromotion/diamond-graph-no-promotion.ll b/llvm/test/Transforms/ArgumentPromotion/diamond-graph-no-promotion.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/ArgumentPromotion/diamond-graph-no-promotion.ll
@@ -0,0 +1,22 @@
+; REQUIRES: asserts
+
+; RUN: opt -passes=argpromotion -debug-only=argpromotion -disable-output %s 2>&1 | FileCheck %s
+
+define internal i32 @diamond_callee(i32* noundef readonly %0, i32* noundef readonly %1) {
+; CHECK: ArgPromotion of i32* [[ARG0:%.*]] failed: unknown user   {{%.+}} = icmp
+; CHECK: ArgPromotion of i32* [[ARG1:%.*]] failed: unknown user   {{%.+}} = icmp
+  %3 = bitcast i32* %0 to float*
+  %4 = bitcast i32* %1 to float*
+  %5 = icmp ugt float* %3, %4
+  %6 = select i1 %5, float* %3, float* %4
+  %7 = load float, float* %6
+  %8 = fptosi float %7 to i32
+  ret i32 %8
+}
+
+define i32 @diamond_caller(i32* nocapture noundef readonly %0) {
+  %2 = getelementptr inbounds i32, i32* %0, i64 0
+  %3 = getelementptr inbounds i32, i32* %0, i64 1
+  %4 = call i32 @diamond_callee(i32* noundef %2, i32* noundef %3)
+  ret i32 %4
+}
diff --git a/llvm/test/Transforms/ArgumentPromotion/phi-loop-no-arg-promotion.ll b/llvm/test/Transforms/ArgumentPromotion/phi-loop-no-arg-promotion.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/ArgumentPromotion/phi-loop-no-arg-promotion.ll
@@ -0,0 +1,36 @@
+; REQUIRES: asserts
+
+; RUN: opt -passes=argpromotion -S -o - %s | FileCheck %s
+; RUN: opt -passes=argpromotion -debug-only=argpromotion -disable-output %s 2>&1 | FileCheck %s --check-prefix=WARN
+
+define internal i32* @callee(i32* noundef %0, i32* noundef %1) {
+; CHECK-LABEL: define {{[^@]+}}@callee
+; CHECK-SAME: (i32* noundef [[P_0_PTR:%.*]]) {
+; CHECK-NEXT:   br label %[[BGN:.*]]
+; CHECK:        [[BGN]]:
+; CHECK-NEXT:   [[PHI_VAL:%.*]] = phi i32* [ [[PHI_VAL]], %[[BGN]] ], [ [[P_0_PTR]], {{%.+}} ]
+; CHECK-NEXT:   br label %[[BGN]]
+; CHECK:        [[END:.*]]:
+; CHECK-NEXT:   ret i32* [[PHI_VAL]]
+
+; WARN: ArgPromotion of i32* [[P_1_PTR:%.*]] failed: unknown user   {{%.+}} = phi i32*
+2:
+  br label %3
+3:
+  %4 = phi i32* [ %4, %3 ], [ %1, %2 ]
+  br label %3
+
+  ret i32* %4
+}
+
+define i32* @caller(i32* noundef %0) {
+; CHECK-LABEL: define {{[^@]+}}@caller
+; CHECK-SAME: (i32* noundef [[ARG:%.*]]) {
+; CHECK: [[P_1_PTR:%.*]] = getelementptr inbounds i32, i32* [[ARG]], i64 1
+; CHECK-NEXT: [[RET:%.+]] = call i32* @callee(i32* noundef [[P_1_PTR]])
+; CHECK-NEXT:  ret i32* [[RET]]
+  %2 = getelementptr inbounds i32, i32* %0, i64 0
+  %3 = getelementptr inbounds i32, i32* %0, i64 1
+  %4 = call i32* @callee(i32* noundef %2, i32* noundef %3)
+  ret i32* %4
+}