<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=http://email.email.llvm.org/c/eJzNWF1v47YS_TXOC2HDluKvhzxsss1tgOwtkC7ax4CSKIs3tOiSVBzvr79nhpIlJdndLlqgDRRbFMnhfJw5M3Jmi9PV50p7kTU7cZReWKd3upbGnEShfW6flVOFkEFUIRz8JP0wSW5x7XSommyW2z0GN0bWu-tGm3Cv6-YFT0z7rb1vlMfNIlksRXaCoKD2h6DrnQgWh2pTCN4kjpAoWNIkub7__MtMfK6UKK0x9kjLoaMUuT2chC1FwJSEliePx6Wz-79BvUmS8hib9qoO0-3mcr5NV-sNSZ1_nMzbz5_hkUmyJnUqWRfTva71Xn-Bl5w6ONuvXs3jlcexegnK1eLZ6kKUk2RjLJm6naTXQ-mPj3CR01kT1OMjVuGqra6hsaLFyVb4IIPOWzlN3UoSLzQ3WbfCBB_xIuBLsRidsv44PI6lRL2TDQ1eS-ED6OqfCWFkpszZUMF_A4uSFa52zXkXHcwGvKNK56mhZpPkUuQUOTH9JRHT0gAv0zzqOsvF1La3ul9uipkxxfh5fAZdhXLOOrr5rwKoscpb86zYh3nQto44yozNn2RRYNqTTbPZjHQeKPagjHqWdRAH6UIHxvv73z6Ju4dJciN2qlZOBkgmSPdw-I49ZW2nlHHSFdNnaRo1reVeeTH99ZWTjHnex0ekG98UqgQ-ROHtI9SXJoJjcjnvIstRTdJ5H1og3J0GIcxcjCqWLWPoBiZ38RY_8IcwiwO4A15MP5LUeGJ7XJDaCGhqRCl9yPOzxh3gtt1KpwJPvgvf1nBdU2rJrwsTTU3eLB4psuSJxdc90at2FgMhenUpsFm0t4fgAtIy8BgnfBgBhw49O_-mdykUQdSxnzPhhu5idsbwpN-x-RzvdxPmdwWta-GVanFW6l1D5G2bAIzKwEAttfNBSLdriORIHYjpnb6aM9Gaozx5Xu_hNlLVQ-8gIhEVPMMgPZNxJxByjpXOKxLDE20qYR1hl91Ah9Q0jB6CGcl2NjTlVyVdXhHrc17ltqBK4KJCtnH5-VxOaoE88XKnxE4_g85ZxDfqASdQ_Jri_P-pPGCI-GX4usyWyzTZrlWZKnVZ5MlisS2Wl8lWFmU6XydqOy9lnm4GcjTtu9aB1MTdg5KFcv2jOJ7lhwNCfL9Zph0fbGCAU-zv2tJ9aw1Xws73oHuniVZvUC1DrJjkGCI6XoiiiDIE4xHKtx7xlT36Lvo4qY2KRdLEhyj3O-U8RUCQplyZK2ebXRV3RKtuxFExtHjXyDLwxheNdsFhRKbEmGVxCfBmVCzlLq6WhwOi6zkRah00txoAfIPaeDAyV5U1tM5mFJhW91oR6NAwKAAs2YNdHTZS0cUQ1ohC7VGLRyCiM1mFCm2Nt-TKg8qxjcu2IUMBohHf3z1gR40CWwdPNksq8qMVrE1nAvkfQJZ9CbkVe0nWlAhsDZRit_Qo1iwjFhiJvqrk-dDv-w_ljTyHJ5eeSI3voVMHferRWlIZ58vvlapF7xUybaBUCxPk2SuOuq3JyNv68fo65j4NQ-c28jmHyStUOghHnNhz6qwjXMAQxlbIQlorzTiuuJHkLyBbnEBnmRqpqAoCBXxp7A7-6TxK0s5U_G9N4WQ7X0zxmayHMbgrezeQ4W8MFjHj46rpJP2JGuFTz7t5pfKntjAECmjokybHd1CExmsK4YcWjQw01zbTzLYHeOOAE4MSt238yQwCIe9s02omXqtLcXqj8rdVGWbr4IQOrSNNgRsqBb4_FBpL8UejYg3pwOrbLB8jhfF93okkea0kStNRo2Lv5RPSHFWPxDQ-IhVdSFS6EG8dMQzhhzIQQRVMgswYhaKcg0NbQtB98jMTUGtJrwJ0FKwY82KGQ598ZFFw5GnMJB0JIRSdfxE7TqsuDTH9BDmFVSOLh5UTvoK_FSsWX63Yg69WU31fzWfiZ3uk3peLyZ_f1xrug5Im8tOA1Dy3F7G69-UcLung1zr6n03te_Ykbu4ePtErbZfKi8ViNaXP9bhyUN2TDRHcdzNWUNsDO-ktOYNscuNBeqbG16Q88hFKKjdKhFnf0y6VlKeIrjcJ-i0i5c0HCapXNaeVH-Hkq2nFJ1WE6tpH4HVF_9_Ow4tVgtit0u5VIHC_gPA0vnX2nf90NlhmRg2a3JrgXLTAHceV2_TW_2f_UQikIQ48vc-TxHDce3FGzN7gyViLZDH6ibqCUmqHcgru5KKOUg8mmYlb_cI_dYR2Nbqz_Okkppx-Su39e-2XU3802ql2blRxbs-sKtFvIC0xb9F-aHo5rXSs5I66d-oziUAHPEzSmFRf4QZcFiKHkMnUhz5ra7gmxO7I-4Z-4rH1THySYE78x66S-s_6WUJQ3dnD_oB1e72rCMN1aXQe-hZ4Z9GvIUjMny72pyT2lMUmVhdKctdE3BXPisztiOg8MTiAXaAZO-FsUB4sIVLCsmGH6rlF_UYPdQvdGpja9stC7_E2yWW23xIlQ1k5cmTbfo3I_0DvjhzqGprfzi6Kq7TYplt5IZtQWXfFgf9y0Thz9cPpd_5Va5msN-uL6mpeJtlGLtN5tszSVZLkyMG0nG_LdJ2Uidpc8GuZv5os0QcmtToKFoH7yfLjxV_XQF8lcyR_stjM08vVPJ2tlullPl-l2XqTr_Nsjpdl9O_azEjOzLrdhbtikUgOj0mjffD9JBCmd2hPWWFoGHQwPKByvKQfG5If_7GHXiSYsqnqUmhG-CBodkDOnfV-epY0Cuy59fcX7IQr9sD_AV0l-F8>52787</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [lld] "error: Never resolved function from blockaddress" when linking bitcode files containing cross-function blockaddress references
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          rickyz
      </td>
    </tr>
</table>

<pre>
    This bug was originally discovered at https://github.com/ClangBuiltLinux/linux/issues/1215 by attempting to build Linux with Clang+LTO. The following is a copy of the analysis from https://github.com/ClangBuiltLinux/linux/issues/1215#issuecomment-984093678:

Here's a hand-minimized repro:
```c
extern void f(long);

__attribute__((noinline)) static void fun(long x) {
  f(x + 1);
}

void repro(void) {
  fun(({
    label:
      (long)&&label;
  }));
}
```

$ clang -O2 -flto -c repro.c -o repro.i
$ ld.lld repro.i
ld.lld: error: Never resolved function from blockaddress (...)

Relevant part of the LLVM IR, generated with:
$ clang -O2 -flto -c repro.c -fno-discard-value-names -S
```llvm
...
define dso_local void @repro() #0 {
entry:
  br label %label

label:                                            ; preds = %entry
  tail call fastcc void @fun()
  ret void
}

define internal fastcc void @fun() unnamed_addr #1 {
entry:
  tail call void @f(i64 add (i64 ptrtoint (i8* blockaddress(@repro, %label) to i64), i64 1)) #3
  ret void
}
...
```

We can see clang figured out that the first argument to `fun()` is always the same, so it inlined the value of the argument (which is the address of `label` in `repro`).

Searching LLVM code for the source of the error message gives
https://github.com/llvm/llvm-project/blob/4b553297ef3ee4dc2119d5429adf3072e90fac38/llvm/lib/Bitcode/Reader/BitcodeReader.cpp#L853
(there is another error with the same string, but building lld with a change to the error message shows that this is the one that triggers). Reading through this code, we see that BitcodeReader lazily reads an LLVM bitcode file. The reader appears to initially return placeholder objects that need to be "materialized" on demand.

The code has some special handling of blockaddress IR constants, as a blockaddress that appears within a function F may reference a basic block from a different function G (as is the case in the IR for the bug repro).

When materializing a function with a `blockaddress(Fn, Fn_BB)`, the code needs to separately handle the cases where `Fn` either has or has not yet been materialized. That logic appears here:
https://github.com/llvm/llvm-project/blob/4b553297ef3ee4dc2119d5429adf3072e90fac38/llvm/lib/Bitcode/Reader/BitcodeReader.cpp#L2901-L2927

If `Fn` has been materialized (the `Fn->empty()` check), then the reader creates a BlockAddress referring to the appropriate Function/BasicBlock object. If `Fn` has not been materialized, then the reader creates a placeholder BasicBlock for the BlockAddress and adds `Fn` to a queue of functions to be materialized. When `Fn` is materialized, it will make sure to use the precreated BasicBlock object.

After adding some debug prints, it appears that lld's use of BitcodeReader breaks this lazy blockaddress handling. In the repro case, the linker does materialize `repro` before it attempts to materialize `fun`. However, before it attempts to materialize `fun`, it steals the basic blocks out of `repro`'s Function object here:
https://github.com/llvm/llvm-project/blob/4b553297ef3ee4dc2119d5429adf3072e90fac38/llvm/lib/Linker/IRMover.cpp#L1116-L1117

This causes the `Fn->empty()` check mentioned above to pass when materializing `repro`, which makes the code think that `Fn` has not yet been materialized. That code path enqueues `repro` to be materialized. When that happens, this code:
https://github.com/llvm/llvm-project/blob/4b553297ef3ee4dc2119d5429adf3072e90fac38/llvm/lib/Bitcode/Reader/BitcodeReader.cpp#L162-L163
detects (using `IsMaterializable()` instead of `empty()`) that `repro` has already been materialized, and errors out.

This looks like a fairly old bug in lld. Fixing it looks tricky - it seems that BitcodeReader requires that materialized Functions aren't modified while there are still functions that will be materialized later, and lld violates that assumption. Maintaining this invariant seems like it might conflict with the goal of lazy reading. Maybe one idea is to maintain some reverse dependency information in bitcode files. Then materializing a function F could trigger immediate materialization of all functions with a blockaddress pointing into F.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzNWF1v2zgW_TXOC2HDlvz5kIcmnewESHeATjHzGFASZXFDix6SiuP--j33UrKkJG23wAIzhRtLInk_zz33ypktztdfKu1F1uzFSXphnd7rWhpzFoX2uX1WThVCBlGFcPST9MMkucNnr0PVZLPcHnBza2S9v2m0CQ-6bl7wxLTf2vtGeVwsksVKZGcICupwDLrei2ChVJtC8CFxgkTBkibJzcOX32biS6VEaY2xJ9oOG6XI7fEsbCkCliSsPHs8Lp09_B_MmyQp3-PQQdVhutsu57t0vdmS1PnHybz9-ysiMkk2ZE4l62J60LU-6K-IklNHZ_vd63n85PFevQTlavFsdSHKSbI1llzdTdKbofTHR4TI6awJ6vERu_Cpra5hsaLNyU74IIPOWzlN3UoSL7Q22bTCBKt4EYilWIy0bD4O1bGUaHeypZvXUlgBffpnQhiZKXNxVPC_gUfJGp92z-UUKWYH3jGli9TQskmyFDllTkx_S8S0NMDLNI-2znIxte2l7rebYmZMMX4en8FWoZyzji7-rQBq7PLWPCuOYR60rSOOMmPzJ1kUWPbk02w2I5sHhn1WRj3LOoijdKED48PDH5_E_edJciv2qlZOBkgmSPdw-IE_ZW2nVHHSFdNnaRo1reVBeTH9_VWQjHk-xEdkG18UqgQ-ROHtI8yXJoJjspx3meWsJum8Ty0Q7s6DFGYuZhXbVjF1A5e7fIuf-Ic0iyO4A1FMP5LUqLFVF6Q2ApYaUUof8vxicQe4XbfTqcCL78K3dVzXVFry28JEU1M0i0fKLEVi8e1I9KZdxECIXi8FDov28hhcQFkGvoeGDyPgkNJL8G_7kMIQZB3nuRJu6SpWZ0xP-gOfL_l-t2D-VLC6Fl6pFmel3jdE3rYJwKgMDNRSOx-EdPuGSI7MgZg-6Os5E605ybPn_R5hI1M97A4iElHBKwzSCxl3AiHnVOm8IjG80JYS9hF2OQykpKbbGCG4kexmQ1d-V9LlFbE-11VuC-oELhpkG5df9HJRC9SJl3sl9voZdM4ivtMPuIDi1xT6_6PygFvkL8PXMlut0mS3UWWq1LLIk8ViV6yWyU4WZTrfJGo3L2WebgdyNJ270YHMxNVnJQvl-kfxfpYfj0jxw3aVdnywhQNOcbxrS9etN9wJu9iD7p0mWr1FtwyxY1JgiOh4I5oi2hCcRyrfRsRX9uS77ENTmxWLookP0e73ynnKgCBLuTNXzjb7Kp6IXt2Kk2Jo8amRZ-CNrxrjgsMduRJzlsUtwJtRsZW7uFsej8iu50KoddA8agDwDXrj0chcVdbQPptRYlrba0Wgw8CgALDkAHZ1OEhNF7fwRhTqgF48AhHpZBMqjDXeUiiPKscxbtuGHAWIRnx__xknajTYOnjyWVKTH-1gazoXKP4AsuxbyJ04SPKmRGJroBSnpUezZhmxwUjMVSWvh_7cv6hu5CU9ufREanwNmzro04zWksq4Xv6sVC36qJBrA6NamKDOXnHUXU1O3tWPNzex9uk2dGGjmHOavEKng3DkiSOnLjYiBAxhHIUslLXSjOOKB0n-ArLFGXSWqZGJqiBQIJbG7hGfLqIk7ULF_9QSTnbzxRR_k80wB_dlHwZy_I3DIlZ83DWdpL_QIHzueTevVP7UNoZACQ190eT4DorQeEMp_NCikYHm2mGa2faIaByhMShx1-af3CAQ8sm2rGbitbmUpzcmf9-UYbUONHRoHVkK3FAr8L1SWCzFX42KPaQDq2-rfIwUxvflJIrktZFoTSeNjn2QTyhzdD0S0_iIVEwh0ehCvA3EMIUfykAEVTAJMmMUimoOAW0JQffFz0xAoyW9CpAqeDHmxQxKn3xkUXDkecwkHQkhFV18kTsuq64MsfwEOYVVI4-HnROxQrwVGxZfrTiCr3ZTf1_PZ-JXe6LZl5vJ_36uddwHJU3kpwGpeR4vYnfv2zlC0sGvDfTfW9oPHElc3H_-RK-0XSkvFov1lP5uxp2D-p5siOB-WLGCxh74SW_JGWRTGI_SMzW-JuVRjNBSeVAizPqedqmlPEV0vSnQ7xEpHz5KUL2quaz8CCffLCvWVBGqax-B1zX9fzoPL9YJcrdOu1eBwPMC0tP4Ntj3_tPFYZkZNRhya4Jz0QJ3nFce09v4X-JHKZCGOPD8Pk8Sw_HsxRUxe4MnYy2KxegnmgpKqR3aKbiTmzpaPZhkJu70C__UEdrdmM7yp7OYcvkpdfDvjV9O_dVop9q1Uce5u7CqxLyBssS6xfih6eW00rGTO5reac4kAh3wMEljUn2FG3BZiBxCLtMc-qyt4Z4QpyPvG_qJx9Yz8UmCOfE_TpU0f9bPEoLqzh-OB7w76H1FGK5Lo_PQj8B7i3kNSWL-dHE-JbHnLA6xulCSpybirqgrMrcjovPE4AB2gWHsDN2gPHhCpIRtwwnV84j6nRnqDrY1cLWdl4U-4G2S22x_JEqGsXIUyHb8GpH_kd4dOdU1LL-bXRXXabFLd_Iq6GDU9WR1Q61lRS_Oyc__cEFDMdMPdRBSM_KVwtwlJXfW--lF0sjIyxjrrxpnrn-aBi6_rq2SzXZzVV2ny0zK-Wq7yFZJvtoV2XqeFIvNIt8sVmq7XF7x66En7-FBrU6CReAakbjS18kcFJIstvN0uZ6ns_UqXebzdZpttvkmz-Z45cZbgDYzsmNm3f7KXbNJKDGPRaN98P0icKr3GHJZHeTLJlTWXXPJfb1izdds-X8B-Nbi2g">