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

    <tr>
        <th>Summary</th>
        <td>
            [MIPS] `MIPSELFObjectWriter::sortRelocs()` makes compilation near-unusably slow for O32
        </td>
    </tr>

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

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

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

<pre>
    Building and running the Zig standard library tests (with LLVM 18.1.8):

```console
❯ time zig4 build -j8 -Dno-lib -Dno-bin -fqemu test-std -Dtest-target-filter=mips64- -Dtest-target-filter=mips64el-
________________________________________________________
Executed in  209.15 secs    fish           external
   usr time   18.17 mins  361.00 micros   18.17 mins
   sys time    1.02 mins   64.00 micros    1.02 mins
❯ time zig4 build -j8 -Dno-lib -Dno-bin -fqemu test-std -Dtest-target-filter=mips- -Dtest-target-filter=mipsel- -Dtest-slow-targets
________________________________________________________
Executed in   66.50 mins    fish           external
   usr time  242.35 mins    5.87 millis  242.35 mins
   sys time    1.06 mins    0.30 millis    1.06 mins
```

As a result of this, we've had to disable MIPS O32 tests for local development and only run them in CI.

Attaching a debugger made it clear that the overwhelming majority of time is spent in `MIPSELFObjectWriter::sortRelocs()`. Specifically (and perhaps unsurprisingly) here:

https://github.com/llvm/llvm-project/blob/ef6760116fa2fa21f78e7a3b499f77e1a3eb7b92/llvm/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp#L468-L476

Some extra context:

```
(gdb) p Relocs.size()
$3 = 1412282
(gdb) p Remainder.size()
$4 = 439999
(gdb) p Sorted.size()
$5 = 1019010
```

We build the standard library tests as one big executable so we end up with a ton of relocations. Due to the size of the resulting LLVM IR, I can't easily post it here. :slightly_frowning_face:
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy0VV9v66gT_TTkZWTL4H_xQx56b26kSq360-1Pe6V9qbAZ23QxeAE3TT_9CpL-3bZSV7tWGxOGA8PJOTPcOTloxA0pv5Fyu-KLH43dcIX3dl61Rhw23xaphNQDcC3ALlqHsR8RfpcDOM-14FaAkq3l9gAenXdA2Hov_QgXF79dAl2nNF0T1pD8jGRbkj1-VtnxrzPaGYWn2R-MNFtytgMvJ4QHORTQhhQguV1DstUmUbI9DlqpIen_xGmJ5ybOC0i2cei5HdAnvVQeLcm3k5xdVSSfh1ElxyRu_uFzRP-4x27xKEBqAJY1KS3BYecAAHrpRnh-8N6j1VwdgQCwOHu8OETeapikdgB5RdMsg0l21rhXsSekO7hHJNA0YyckVMUr5HPsP-f7U7ZRPYWdMvvTGvev8w9VlZbZIxlf4J8VLM3LJ2CZrgPhSkn3KvYR_9UTMkvz7An5IvbGBS-tceaAg0W3KA-mBz9KR9h32CNh9R3CyAV4A0I63iqEy_P_XcNVzk7m640FZTquQOAdKjNPqH10r9HqECwc7DsFdr6fp6-O9Z53Y_Q6CGyXYUALExcI0kOnkFvwI_fR_eYO7X5ENYXlE781VvpDTDZwIB24ORwrNZAqCxn-uNhdtbfY-V9WRhmckfzMGet_ojKdIyyWiCpL4XrGTvay40odQikJqc9oRz47WLRb7Gylk3pQB8IaGNHim8oyej-7MMd2hO0G6celTTszEbZT6u7xlczWhHwI27XKtITtsK_qKqO06jnrOaN9vcaa523RNH1dI-U5tnXbsBf7yID7f9QuYbtLObvw-n6c2aLrTrNvbp9280xYflFU6-SiqKuX2V-bCYMwLYfOaI_3_qPCefrK1oNoAxUzHLlMnXzAE6GnJUUOJN8CLShja_YecOJSC7TvYYuILfKmaZq_Q6-N9Sjew5XHMzPaZDT7RO6_8FRygrA-aCncgdEIrRwAo7-j9J2BPQJqAcsMseVw8EYHHdpABffSaJfCdsHgmLi_fMCjqfBksaDg2KnOfwaXnUPHNWG1B-ROqgPMxvnggKC0FIJqlRxGrw43vTX70A9vet4FEa7EJhdN3vAVbmjN8rqpGM1X46Zoeyo6UYu1oIJR3lKktOtESUUrmj5byQ3LWJGtaRX-yzylmeirruSc5bStmpwUWfiJVBqUlxo7rKRzC25oVpQVWyneonKxjTOmcQ8xShgLXd1uot7bZXCkyJR03j1v46VXsf8Hk5Jy-1W_wsT_QAedmWapIt-gkdtk0UsoTwcI5T0WpaucrRarNl-2Z7xLMNbpsncb9lcAAAD__-B3tqo">