diff --git a/bolt/lib/Core/BinaryContext.cpp b/bolt/lib/Core/BinaryContext.cpp
--- a/bolt/lib/Core/BinaryContext.cpp
+++ b/bolt/lib/Core/BinaryContext.cpp
@@ -390,6 +390,12 @@
     // can pull this constant island and emit it as part of this function
     // too.
     auto IslandIter = AddressToConstantIslandMap.lower_bound(Address);
+
+    if (IslandIter != AddressToConstantIslandMap.begin() &&
+        (IslandIter == AddressToConstantIslandMap.end() ||
+         IslandIter->first > Address))
+      --IslandIter;
+
     if (IslandIter != AddressToConstantIslandMap.end()) {
       if (MCSymbol *IslandSym =
               IslandIter->second->getOrCreateProxyIslandAccess(Address, BF)) {
diff --git a/bolt/test/AArch64/ext-island-ref.s b/bolt/test/AArch64/ext-island-ref.s
new file mode 100644
--- /dev/null
+++ b/bolt/test/AArch64/ext-island-ref.s
@@ -0,0 +1,39 @@
+// This test checks that references to the middle of CI from other function
+// are handled properly
+
+// RUN: llvm-mc -filetype=obj -triple aarch64-unknown-unknown %s -o %t.o
+// RUN: %clang %cflags --target=aarch64-unknown-linux %t.o -o %t.exe -Wl,-q
+// RUN: llvm-bolt %t.exe -o %t.bolt -lite=false
+// RUN: llvm-objdump -d -j .text %t.bolt | FileCheck %s
+
+// CHECK: deadbeef
+// CHECK-NEXT: deadbeef
+// CHECK-NEXT: [[#%x,ADDR:]]: deadbeef
+// CHECK-NEXT: deadbeef
+// CHECK: <func>:
+// CHECK-NEXT: ldr	x0, 0x[[#ADDR]]
+// CHECK-NEXT: ret
+
+.type	funcWithIsland, %function
+funcWithIsland:
+    ret
+    .word 0xdeadbeef
+    .word 0xdeadbeef
+    .word 0xdeadbeef
+    .word 0xdeadbeef
+.size   funcWithIsland, .-funcWithIsland
+
+.type	func, %function
+func:
+    ldr x0, funcWithIsland + 12
+    ret
+.size   func, .-func
+
+.global	main
+.type	main, %function
+main:
+    bl funcWithIsland
+    bl func
+    mov     w8, #93
+    svc     #0
+.size   main, .-main