<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/138254>138254</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [LLD][AARCH64] Bug with ADRP + LDR transformation when there is a branch to the LDR
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            lld
      </td>
    </tr>

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

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

<pre>
    **Summary:**

The issue is how LLD replaces two ADRP + LDR pairs to the same symbol inconsistently while there is a branch somewhere in the program to one of the LDR that assumes both ADRP will end-up with the same offset in the program.

That following assembly:
```
        adrp    x2, :got:b
 // unrelated instructions
        ldr     x3, [x2, :got_lo12:b]  // note that source register !=dest

       // ... some code and check
       bge .L9
       // ... some more code
        adrp    x2, :got:b
.L9:
 ldr     x2, [x2, :got_lo12:b]
```

Is rewritten in the final executable by LLD into the following:
```
```
        adrp    x2, 0x220000
        // ...
        ldr     x3, [x2, #2944]

       // ... 
       bge .L9
 // ... 
        adrp    x2, 0x419000 <a+1999920>
.L9:
        add     x2, x2, #0x50
```

But now the path that jumps directly to L9 with the value from the first adrp will execute `adrp  x2, 0x220000` followed by `add        x2, x2, #0x50` which ends computing the wrong address.

Note that the hardcoded addresses in this illustration will of course be different in different environments, what matters is that the two adrp now have different offsets ( 0x220000 vs 0x419000).

The actual assembly were I discovered the issue is much more complex and was actually obtained when compiling LLVM source with gcc 9.3.1. More details below in the "Where I saw the bug" section below.

I think LLD should not optimize ADRP + LDR if there is a branch in the program to the LDR. I am not expert enough  in aarch64 assembly to asses the validity of GCC generating a branch to the second LDR.

This was observed with LLD as old as LLD 17 and is still present in the LLVM head I tested (099a0fa3f2cf1a434e20b2fa97b6251088321467) .

**Small full repoducer:**

Reproduce with the attached [repro.tar.gz](https://github.com/user-attachments/files/20011949/repro.tar.gz):
```
tar -xzvf repro.tar.gz
cd repro
bash build_and_run.sh
```

This will print the following output (the exact 4296785 number does not matter, this is an address, what matters is that it should be printed twice, while here 2228305 is printed):
```
expect 4296785 to be printed twice below:
4296785
2228305

Dump of assembler code for function foo:
 0x0000000000210880 <+0>: cmp     x0, #0x0
   0x0000000000210884 <+4>:       b.ge    0x210898 <foo+24>  // b.tcont
   0x0000000000210888 <+8>:       adrp    x2, 0x419000 <a+1999920>
   0x000000000021088c <+12>:      add     x2, x2, #0x50
   0x0000000000210890 <+16>:      add     x0, x2, x1
 0x0000000000210894 <+20>:        b       0x210804 <bar>
   0x0000000000210898 <+24>:      stp     x29, x30, [sp, #-32]!
   0x000000000021089c <+28>:      adrp    x2, 0x220000
   0x00000000002108a0 <+32>:      add     x0, x0, #0x1
 0x00000000002108a4 <+36>:        ldr     x3, [x2, #2944]
   0x00000000002108a8 <+40>:      add     x0, x3, x0
   0x00000000002108ac <+44>:      mov     x29, sp
 0x00000000002108b0 <+48>:        stp     x2, x1, [sp, #16]
   0x00000000002108b4 <+52>:      bl      0x210804 <bar>
   0x00000000002108b8 <+56>:      ldp     x2, x1, [sp, #16]
   0x00000000002108bc <+60>:      ldp     x29, x30, [sp], #32
 0x00000000002108c0 <+64>:        b       0x21088c <foo+12>
```

You can see the bogus assembly from the executable for foo. For the record, `foo` from foo.s is manually modified assembly to get the branch on the second LDR for the following C code:
```
void foo(int64_t i, int64_t j) {
  if (i >=0)
 bar(i+1+(int64_t)&b);
  bar(j+(int64_t)&b);
}
```

** Where I saw the bug: **

This bug causes some LLVM release with assert builds with gcc (at least 9.3.0) + lld to produce a flang that will hit a weird compiler error on some Fortran programs when generation IR for WHERE statements. I am providing some details below for the record, but I do not think it matters here that I provide a full Fortran reproducer that will trigger this bug to cause an ICE in flang.

The bug at hand is breaking the generated code for llvm::DenseMap insertion in flang:

In repro.tar.gz attached above, you will find the assembly code before and after linking the excutable for the instantiation of the template function `void mlir::IRMapping::map<llvm::MutableArrayRef<mlir::BlockArgument>, mlir::ValueRange&, (void*)0>(llvm::MutableArrayRef<mlir::BlockArgument>&&, mlir::ValueRange&)` (a.k.a `_ZN4mlir9IRMapping3mapIN4llvm15MutableArrayRefINS_13BlockArgumentEEERNS_10ValueRangeELPv0EEEvOT_OT0_`) that is declared [here in MLIR source](https://github.com/llvm/llvm-project/blob/10ea5eedb1d13760e4caf0bd983ce7778cff0426/mlir/include/mlir/IR/IRMapping.h#L38) and instantiated [here in flang source](https://github.com/llvm/llvm-project/blob/40edb37bb370541b71657fc308ba26b1ec2deb16/flang/lib/Optimizer/Builder/HLFIRTools.cpp#L884).

Both ADRP + LDR are generated to compute the DenseMap seed using the `llvm::install_fatal_error_handler` function address [here](https://github.com/llvm/llvm-project/blob/85c810060e1a2a90dc4ec184b4c4275db17ef28f/llvm/include/llvm/ADT/Hashing.h#L317).

The bug is then triggered when this exact template instantiation is entered and the map needs to be grown during the insertion (this causes the code path to make the critical jump for this bug). In that case, the value is wrongly inserted into the wrong bucket because the hash used the bogus address. Later searches fail to retrieve the value map to that key because they are using the right hash seed.

The flang bug is very hard to reproduce because one needs to get gcc to do the right inlining and block merging + CSE + register assignment to create that branch on the second LDR. The distance in the text between the template code and  `llvm::install_fatal_error_handler` also needs to be big enough so that LLD keeps ADRP.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJysWdtu4zjSfhrlhmiDomRZusiFncM_Btw9g0xjBv_eBJRUstihSIGk7GSeflGkZNmJs3PYbTTabYmsw1fnMrdW7BXAbbTcRMv7Gz64VpvbH8DVL2AEmJtS12-3EVtHbP3r0HXcvEXJOnyPKP793gIR1g74L2n1kex298RAL3kFlrijJuv7p19IxDZkd_9Eei6MJU4T1wKxvANi37pSSyJUpZUV1oFy8o0cWyEBDxlPmJPScFW1xOoOjuGp8jR6o_eGd0hSKyC68U-RlWu5I9zaoQNLSu3aIMlRSElA1V-GnhyFa2dJdNNYcO8ILyY1uSONllIfhdojWehK6cGg6yij41-6JuMfXpseP19ZxO5IlKz32kXJusQjEXuM2CMZlAHJHdREKOvMUDmhlT2jIWvjP18TT2O5OSf2LHXMPMXlPZlIKu0gKG71YCogBvaIqSERi6PkvgbrgkIji_HeYrHw0JJK10C4qknVQvUynyv3QBa74vOLnTbh9l_DAGl57GYl2Z8o-Q7oiK63lhg4GuEcqMlsjVBcEniFanC8lEDKN--SQo1OdzLiR9t9ZseIFkEo-soYpfT8_YzDpeHwzjuzsYQVaTpqcg3Iq3Bfff9erDQuKKUkSu54xDZxURQFo1HycIH06Wp9unmSjL4u3yMQ0fVmcETpY4gH7mOFO_Jj6HpLamGgwlB1muyKOZQOXA5AGqO70R7GuuAJIfK8ZYBEGQ3u8Q7ZjI4WghpN5499Jm9GMU9ULYazJZXu-sFhdCLfo9EYp3VtwNoxiL-dogNPtNzU6LD1dApscCJhiZBysM5wjMggt25IpQdjgZRAatE0YED5ZDF_AXUQRqsOlLMo5xFZddw5MBaz2Ik1pkWvPYLb8sM5xZCFLIlYfkKFHOzJyBErFnPq5ZUbuDzlI3LE1LgltbCVPoCB2vM7JehuqNopVLtewquP9SO3IyH5RnTpuFBQk2MLyh8TEkHd7X77OmUVb-x9VZFikSziBfmKFGtwXEhLSpD6OIVjxNjvbZDJ8uBI5bCPGCMWfL4Lx0eNtoi-evEBa1s9yBozGtG9E534Ay5LiWiu1IePVWEsBwuyJbzz5OC1B4PW0sO-JXiFc1O1WTrD6LT_v508WtTCvaEP_N_dHdmDAnQN9K-J71TRoNKq9vwmGwnr8dWlBXNAWBE7VBAfyho_8Fu88qYQlliH_tYbsKODeQ0Q_RZ4TbbEgcWiEbGcFgWnDU8aVjUxT5MUGC1Zw4tVmbFlTPM8YXGarSJWkFGgsZZ3XErSDFJirdb1UIF5V9ifoDf-xRza3Dletch6uTH4euG4Wez_wJTG8ta53noimLD2wrVDuah0F7HHwYL5Em6PwfHYCAn4ySiN4yItIvZ4QZIVH_Oz44Z8ef3j0JCLo3Rd1eFJRNclty0pByHrZ67qZzOohW0_ZrZglwC0UO6yMhA9uH5wiDA-h1deOZKyIlvlS6KGrgRDag3We1OIbwz3kDks4WrKKJ8mAeEm_y4hSICRehQVhCvY_HjfZozlCV3ixfHYVWTQpc9kdPoD3RBn4eZ4LKLrkXzA5H7oevTxMQrAhG6g0YY0gwrR2mg9VhP6Sk9_GLqaLz8R2_i6g2eKqvM1ip5y9lg4P1xNx6vp6Wq52ENEC_qK74sc3yNrtmF45lQ1y4WrtHKfkM1HsvmJ7F8vm9foVSM9bElOBD8vpldIFBNIcfaeBJ1JvMbXAC4mlNiMcHnCiPq3JTefil9McLAZZusCHIVnm9CxYbH9qMmXhPngjj8hOSHCPoX4vGF6f51PaCQfAA1ozJ5zFRE-IZLMaP5563VNkAmalF4XJBnFuX57QiGdge30YQbW9tekLyft0_yDPUYveGeNOPtUg3KCYjlDWcq_4R3lBMHyHMt_Ks2ESEY_EPvoauhgnmLCruFUTThl6RW_D0EZckOIyw-5_v_1QCquiAUIDYjeD3au9adW9Wxo8DlP6wV51Ma_M1BpU3s5M4rcsE_Fi3jK5_WOq9BAdboWjcC28qyb2EOoMWO7oNW7dsFzvCxCd2Gc-pDrD1rUPg-zXCiXpc-OCBRs-vIDq3202njTiAarmCAeuXtsHvExOgLLBUIWsc1MCF-zrPQlJtwPJ3_8x1PR6spsFloJcq35S3CoOd8gCIvPScUHbLn8OOn7HQMSuB0bEETTuFDa7dyBRiznjuA557tR6rVnGyJljcBPTQwnjeR-NuAuFP5WOMLJEYSpxzYXDAFjtEHzeCketXGGq6mdtKEnnvo_rcg2GO73nx6eHoh13IHvb8Zmszf6IGq0pad22SA3HzyrHBy27tq3FaERFnPr4IH00m9Hwl4pbOEmMc3UspkzNZ0R-71_MsLsdEAa-5Tt3QN2mB6as6kCj3FH2rEjLQ3wl2mwGrWHeu4OpDx06KfJ-h6Uha-8J0KhtRCiifzoyHS9VRft29xV8lIffP_zpocgeyNUGGBOoeR5ltDgwIHS8caBIVKok3zweh7EfvpR1nHlRDDZuCFy0PWSO5hbmyijPrQ6KUzQZvv0lff9uCpI1h3vo-RuVvZr4LM2hr89QRMld_PVjdTVy9rsB_QHDD52d0b4N5yRn7jaQ8SykPxy5O3DovA5k-X_lFE20vyUXYHJC-Nm8bLgqPbzv76leLo4KZx0vN9-S1GEePmO_fbbr89xcsH34eHhCZ_SmdPD7pcDfXh4OPz8_fnn7_QZEwMrxu7XkhoqyU0YJaZ13tfd9mmcMP90ovDghI8vvdE_oHIReyylLiP2GFPgS4C6jOs4WWUU0oo3tKyLPKlgtVrlVdPQFKF49CCxR6EqOdQwP9g--X9GOBZtxJJdkqMGPiZOHnWpQUgx_wsVUgp1mazKMlnRZRqXqzhbrpoqoXnJWVbGULEayhhVCNHFHqXAiz-PszIqscFc6f_30-5x-_Rda2kXVd-jMnmezpuEzWk7Og3X3JxHOqYMv10JBfQU5RagJoOdQi_K6Oy0HiMpnxvuuHz2efUZE4oE44vnFHbjqDTB-N_Bli-rPKY0oxBzxgtaVylUcZ6WaZWy1bIu4xU0LG9mOrPlxwfr--8IGLftbPh4dbl1wfzoRzlQU36dFiY-zYaJ8ZRiLhMQvlfO3-Bjeut4TxRAbcfJbW_0UZF6MBOyczr1M6mwU7HElz4nhvWcJh1_CUaqjHCi4tKv68ZcGCoA6kK2KsRixS2E4XVa3eFgbLTay7eRrV9QjwuOsFYrh-oFHCkhFJKwTbMtGey4cBpbrHH7RnYcs7QFbqoWLGm4kCirAWcEHOCMOSLhWXFHXuDtnMWbd8rZ24zYty7wRT88M08Iw9FIBzBvftcXOE79wERYK5ihxy4NmwqnsQzPTISSQvl9j6pJiZmPdGD2-AQD5u7XB_95WraH31UwM_rQMcCnxeNn_d-CoOC1QEepTj9uOHhFlN0RQF1WrdOe_m8FHZdWXzhaKfbTHsyOqO929-QFoLc-ISxu6tukLpKC38BtvEqzOM-WNL1pb8skL1clT1hW1hDXNRRNXkOepQ0rU5ZXN-KWUbakS8riOM1ZsgDIl1kG2aopOKQJRCmFjgu5QPkX2uxv_J7yNk5ytkxvJC9BWv_TFGNS1hHDWfTG3PrQL4e9jVIqhXV2JuCEk_7XrN3uHjPJcrNeP939lOHoRzbDPvSNF5kOOyfbaNONy94QxO_3ivMi8WYw8vZv5yevmcXaFJQ73LJ_BwAA__80pWMA">