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

    <tr>
        <th>Summary</th>
        <td>
            [SPIRV] Module analysis stage is not able to complete processing of a really big LLVM source
        </td>
    </tr>

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

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

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

<pre>
    There is an example of a bulky LLVM source: https://github.com/KhronosGroup/SPIRV-LLVM-Translator/blob/main/test/SpecConstants/long-spec-const-composite.ll

Processing of this file to produce SPIR-V output using LLVM SPIR-V backend takes so long that I've never been able to see it actually completes. It can be reproduced, for example, using the following command:
`llc -mtriple=spirv64-unknown-unknown -O0 long-spec-const-composite.ll -o long-spec-const-composite.spvt`

Debugging shows that a problem is within the Module Analysis stage, namely, on a step of collectOtherInstr()/findSameInstrInMS() calls from lib/Target/SPIRV/SPIRVModuleAnalysis.cpp

The reason seems to be O(n^2) complexity of this particular analysis step, related to choice of a data structure behind `MS` field of `struct ModuleAnalysisInfo`. Possible solution is to use, for example, `std::set` to trace instructions with identical operands instead of `findSameInstrInMS()`.

PR: https://github.com/llvm/llvm-project/pull/76047

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyUVMFu4zYQ_Rr6MpAh07bsPfiQburCaIIEmyD3ETWS2FCkwBk6678vKMW7CdBu0YtpiSPyzXtvHjLbzhMd1PY3tb1dYJI-xMPLBU1P7PB8R-eL8OvlsqhDczk89xQJLAN6oO84jI4gtIBQJ_d6gbu7l3vgkKIhtb6BXmRktb5R-qj0sbPSp3ppwqD08c8-Bh_4jxjSqPTx6fH07aXInxfPET07lBCVPtYu1EofB7Re6aMQSy4eyXwNngW9sNJHF3xX8EimMPltYcIwBrZCS-dUeavKm_n3MQZDzNZ3GbP0lqG1jkACjDE0yRBkHMULhCRjEkhT7dTU-0aN5pV8A4KvxMAB8t0gPQqclN6dCTydKUJN5AHr-XAmAiuARhI6d4GMz5EQL-EkYNBDTRDpHUOj9FdoQ7zymx9nINITtMG58JafTBgG9E2md-6xKp0zUAwSbf5sfcujjedqUyT_6sObv65QPJTwK86gCL_Y5_Esqio_EntLdeq6DIr78MYzH5hJrR0N2S5vVnrrpw7uQ5McwY1Hd2HLwILd1KTHgdwl_wseEFhozDqZ4BwZeZCe4smzRKX3Sn9R-tha3zzhQNPbk79_mnfAoHMMbQwDOJvt84yxI7na7LrOQK44lmYcP_b03GdNkIPP-g2chawJHpTee7X9XU8XTUJ-t3L5YagRo1iTHEbAnx3SmNuK5FCoySeZPljzPjoNSu42JiMpEtTUW9-Aqsr7J1WV0FpyTa5UVTlXwWfkJ98GVZVLeAzMNnuOg0tig8_MS4DE9A-emo6b7LO-YcqS5lqJaAisn2-ywc_agW3IizXoIIwU0Tc8FRFeof2LGBnYpxn89h_B4Nz5uhRjDH-RycKNyTmlj7uq3OzmgxbNYd18WX_BBR1Wu3Jd7qr9vlr0h3ajt80e27qmqmn0rsJS11SuTEt7qvf7hT3oUq9XWpcrvd1squVmtVptm_WqNRpXuN6qTUkDWrfMIJYhdgvLnOiQb98vHNbkeApMrT29wbSptM75GQ8T8Dp1rDalsyz88xSx4qaknW24vb3OAn6ahayaD_IjPq5xkefpQ35htmeOk9p2H4N3kaI7_G-Cpyb4neL93wEAAP__xQoM_Q">