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
@@ -564,26 +564,19 @@
 
   // Now look at all loads of the argument. Remember the load instructions
   // for the aliasing check below.
-  SmallVector<Value *, 16> Worklist;
-  SmallPtrSet<Value *, 16> Visited;
+  SmallVector<Value *, 16> Worklist(Arg->users());
   SmallVector<LoadInst *, 16> Loads;
-  auto AppendUsers = [&](Value *V) {
-    for (User *U : V->users())
-      if (Visited.insert(U).second)
-        Worklist.push_back(U);
-  };
-  AppendUsers(Arg);
   while (!Worklist.empty()) {
     Value *V = Worklist.pop_back_val();
     if (isa<BitCastInst>(V)) {
-      AppendUsers(V);
+      append_range(Worklist, V->users());
       continue;
     }
 
     if (auto *GEP = dyn_cast<GetElementPtrInst>(V)) {
       if (!GEP->hasAllConstantIndices())
         return false;
-      AppendUsers(V);
+      append_range(Worklist, V->users());
       continue;
     }
 
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,28 @@
+; 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
+}
+
+!llvm.module.flags = !{!0, !1, !2}
+
+!0 = !{i32 1, !"wchar_size", i32 2}
+!1 = !{i32 7, !"PIC Level", i32 2}
+!2 = !{i32 7, !"uwtable", i32 1}
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,42 @@
+; 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
+}
+
+!llvm.module.flags = !{!0, !1, !2}
+
+!0 = !{i32 1, !"wchar_size", i32 2}
+!1 = !{i32 7, !"PIC Level", i32 2}
+!2 = !{i32 7, !"uwtable", i32 1}