Index: llvm/lib/Bitcode/Reader/BitcodeReader.cpp
===================================================================
--- llvm/lib/Bitcode/Reader/BitcodeReader.cpp
+++ llvm/lib/Bitcode/Reader/BitcodeReader.cpp
@@ -3092,7 +3092,7 @@
                          InlineAsm::AsmDialect(AsmDialect), CanThrow);
       break;
     }
-    case bitc::CST_CODE_BLOCKADDRESS:{
+    case bitc::CST_CODE_BLOCKADDRESS: {
       if (Record.size() < 3)
         return error("Invalid blockaddress record");
       unsigned FnTyID = Record[0];
Index: llvm/lib/Bitcode/Writer/BitcodeWriter.cpp
===================================================================
--- llvm/lib/Bitcode/Writer/BitcodeWriter.cpp
+++ llvm/lib/Bitcode/Writer/BitcodeWriter.cpp
@@ -74,6 +74,7 @@
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
+#include <deque>
 #include <iterator>
 #include <map>
 #include <memory>
@@ -3401,11 +3402,28 @@
     }
 
     if (BlockAddress *BA = BlockAddress::lookup(&BB)) {
-      for (User *U : BA->users()) {
-        if (auto *I = dyn_cast<Instruction>(U)) {
-          Function *P = I->getParent()->getParent();
-          if (P != &F)
-            BlockAddressUsers.insert(P);
+      std::deque<Value *> BlockAddressUsersQueue;
+      SmallPtrSet<Value *, 16> BlockAddressUsersVisited;
+
+      BlockAddressUsersQueue.push_back(BA);
+      BlockAddressUsersVisited.insert(BA);
+
+      while (!BlockAddressUsersQueue.empty()) {
+        Value *V = BlockAddressUsersQueue.front();
+        BlockAddressUsersQueue.pop_front();
+
+        for (User *U : V->users()) {
+          if ((isa<ConstantAggregate>(U) || isa<ConstantExpr>(U)) &&
+              !BlockAddressUsersVisited.contains(U)) {
+            BlockAddressUsersQueue.push_back(U);
+            BlockAddressUsersVisited.insert(U);
+          }
+
+          if (auto *I = dyn_cast<Instruction>(U)) {
+            Function *P = I->getParent()->getParent();
+            if (P != &F)
+              BlockAddressUsers.insert(P);
+          }
         }
       }
     }
Index: llvm/test/Bitcode/blockaddress-aggregate-users.ll
===================================================================
--- /dev/null
+++ llvm/test/Bitcode/blockaddress-aggregate-users.ll
@@ -0,0 +1,40 @@
+; RUN: llvm-as %s -o %t.bc
+; RUN: llvm-bcanalyzer -dump %t.bc | FileCheck %s
+; RUN: llvm-dis %t.bc
+
+; There's a curious case where blockaddress constants may refer to functions
+; outside of the function they're used in. There's a special bitcode function
+; code, FUNC_CODE_BLOCKADDR_USERS, used to signify that this is the case.
+
+; The intent of this test is two-fold:
+; 1. Ensure we produce BLOCKADDR_USERS bitcode function code on the first fn,
+;    @repro, since @fun and @fun2 both refer to @repro via blockaddress
+;    constants.
+; 2. Ensure we can round-trip serializing+desearlizing such case.
+
+; CHECK: <FUNCTION_BLOCK
+; CHECK: <BLOCKADDR_USERS op0=2 op1=1
+; CHECK: <FUNCTION_BLOCK
+; CHECK: <FUNCTION_BLOCK
+
+%struct.ptrs = type { i8*, i8* }
+
+define void @repro() {
+  br label %label
+
+label:
+  call void @fun()
+  ret void
+}
+
+define void @fun() noinline {
+  call void @f(%struct.ptrs { i8* blockaddress(@repro, %label), i8* blockaddress(@repro, %label) })
+  ret void
+}
+
+define void @fun2() noinline {
+  call void @f(%struct.ptrs { i8* blockaddress(@repro, %label), i8* blockaddress(@repro, %label) })
+  ret void
+}
+
+declare void @f(%struct.ptrs)
Index: llvm/test/Bitcode/blockaddress-expr-users.ll
===================================================================
--- /dev/null
+++ llvm/test/Bitcode/blockaddress-expr-users.ll
@@ -0,0 +1,38 @@
+; RUN: llvm-as %s -o %t.bc
+; RUN: llvm-bcanalyzer -dump %t.bc | FileCheck %s
+; RUN: llvm-dis %t.bc
+
+; There's a curious case where blockaddress constants may refer to functions
+; outside of the function they're used in. There's a special bitcode function
+; code, FUNC_CODE_BLOCKADDR_USERS, used to signify that this is the case.
+
+; The intent of this test is two-fold:
+; 1. Ensure we produce BLOCKADDR_USERS bitcode function code on the first fn,
+;    @repro, since @fun and @fun2 both refer to @repro via blockaddress
+;    constants.
+; 2. Ensure we can round-trip serializing+desearlizing such case.
+
+; CHECK: <FUNCTION_BLOCK
+; CHECK: <BLOCKADDR_USERS op0=2 op1=1
+; CHECK: <FUNCTION_BLOCK
+; CHECK: <FUNCTION_BLOCK
+
+define void @repro() {
+  br label %label
+
+label:
+  call void @fun()
+  ret void
+}
+
+define void @fun() noinline {
+  call void @f(i64 ptrtoint (i8* blockaddress(@repro, %label) to i64))
+  ret void
+}
+
+define void @fun2() noinline {
+  call void @f(i64 ptrtoint (i8* blockaddress(@repro, %label) to i64))
+  ret void
+}
+
+declare void @f(i64)
Index: llvm/test/Bitcode/blockaddress-globalvalue-users.ll
===================================================================
--- /dev/null
+++ llvm/test/Bitcode/blockaddress-globalvalue-users.ll
@@ -0,0 +1,38 @@
+; RUN: llvm-as %s -o %t.bc
+; RUN: llvm-bcanalyzer -dump %t.bc | FileCheck %s
+; RUN: llvm-dis %t.bc
+
+; There's a curious case where blockaddress constants may refer to functions
+; outside of the function they're used in. There's a special bitcode function
+; code, FUNC_CODE_BLOCKADDR_USERS, used to signify that this is the case.
+
+; The intent of this test is two-fold:
+; 1. Ensure we do not produce BLOCKADDR_USERS bitcode function code on the first
+;    fn, @repro, by accident, when @fun and @fun2 use a global value, @foo,
+;    which is initialized to @repro's blockaddress constants.
+; 2. Ensure we can round-trip serializing+desearlizing such case.
+
+; CHECK: <FUNCTION_BLOCK
+; CHECK-NOT: <BLOCKADDR_USERS
+
+@foo = global i8* blockaddress(@repro, %label)
+
+define void @repro() {
+  br label %label
+
+label:
+  call void @fun()
+  ret void
+}
+
+define void @fun() noinline {
+  call void @f(i8** @foo)
+  ret void
+}
+
+define void @fun2() noinline {
+  call void @f(i8** @foo)
+  ret void
+}
+
+declare void @f(i8**)
\ No newline at end of file
Index: llvm/test/Bitcode/blockaddress-nested-users.ll
===================================================================
--- /dev/null
+++ llvm/test/Bitcode/blockaddress-nested-users.ll
@@ -0,0 +1,38 @@
+; RUN: llvm-as %s -o %t.bc
+; RUN: llvm-bcanalyzer -dump %t.bc | FileCheck %s
+; RUN: llvm-dis %t.bc
+
+; There's a curious case where blockaddress constants may refer to functions
+; outside of the function they're used in. There's a special bitcode function
+; code, FUNC_CODE_BLOCKADDR_USERS, used to signify that this is the case.
+
+; The intent of this test is two-fold:
+; 1. Ensure we produce BLOCKADDR_USERS bitcode function code on the first fn,
+;    @repro, since @fun and @fun2 both refer to @repro via blockaddress
+;    constants.
+; 2. Ensure we can round-trip serializing+desearlizing such case.
+
+; CHECK: <FUNCTION_BLOCK
+; CHECK: <BLOCKADDR_USERS op0=2 op1=1
+; CHECK: <FUNCTION_BLOCK
+; CHECK: <FUNCTION_BLOCK
+
+define void @repro() {
+  br label %label
+
+label:
+  call void @fun()
+  ret void
+}
+
+define void @fun() noinline {
+  call void @f(i64 add (i64 ptrtoint (i8* blockaddress(@repro, %label) to i64), i64 1))
+  ret void
+}
+
+define void @fun2() noinline {
+  call void @f(i64 add (i64 ptrtoint (i8* blockaddress(@repro, %label) to i64), i64 2))
+  ret void
+}
+
+declare void @f(i64)