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

    <tr>
        <th>Summary</th>
        <td>
            [bugpoint] Very slow function attribute reduction if many functions are left
        </td>
    </tr>

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

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

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

<pre>
    In the function attribute reduction step, bugpoint iterates over all functions in the module and then tries to reduce the list of function attributes:

https://github.com/llvm/llvm-project/blob/main/llvm/tools/bugpoint/CrashDebugger.cpp#L1228-L1243

However, this behavior can cause problems if the number of functions left in the module is very large, as the complexity is `O(n*log(m))` where `n` is the number of functions in the module and `m` is the number of attributes on each function. Everything else in bugpoint generally has `O(log(n))` complexity. In my particular example, there is a global array that references 30k functions, so bugpoint keeps declarations around for all of them and never finishes.

I think a better algorithm here would be to build a list of `(function, attribute)` pairs and do the reduction on that instead for `O(log(n*m))` complexity.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyVVE1vnDAQ_TVwGQWxsGyWA4c0adWolXrrfQwDuDE2sk02--87NsmyStNKRXzYHnv83ptnhOnOzaMGPxL0i269NBrQeyvF4gksdcs65jzNSXEPYhlmI7UH6cmiJwfmmSygUpf1DuSacDLdoghQd6HLY1byfG_WtBTnKOk8mP6DzV1S3iX5Q5K_vkfv5zhWfOF7kH5cRNaaiTtKPb99bmZrflHruSuUEfyZUOptjjdGuRB85cHNe4tufCAeGchm7cw8y--7ojje8HtfXmP4ak7EdIMQfpQOBI34LI2FFjU_iyPg_YWiiUXoI0G9TIIFuqLoQFHv34nEyTjxGRTagUJ-dDHMBGdFL9Kfw5TkkP9IiiPzuVNm4BZTqsN9yOE0kqUwQ4eedH_d_c_q8ILpw0VbMYBLQ9iOlzwZfA6AWQY9AClmznkv7hhIsz2UOsOIF9grZL1B3shlwCaczjCj9bJdWAWgFwzRVetAjdEhDFxUVIDW4pnH0bOZeo7qljGW-dPGMyx0ZoP0RDQ76Kjl5LgqgdYsTL83q4FNrNgUJdGhztBLLd1ILrs2wWOovX5iMIK8j-YfjGU_ThBxnsyiOo4Fp4tFchsvNmfWLMEbxljnN4lfNZlRWhchdCZWYzuDRq-MpebTiCvu99LeTR_Km3ZN2dVljamXXlGTVJ8uJ6B6gJ_Bek6Z079_AmzpCfX5ykvIfIOb08Wq5r9PqHRuoXAaq_2hLNKxOR7q211VY1dVh9t91TLgtqpb6kus6UBFqlCw1wL8pCg0nSCm4DazSGVT5EWRl2XOV1HWmShFK47trupv610rKNnnxL8DlQUcmbFDapsIibVwHAxVclsQnZODpqhWyI-LH41tvpE2ady3ibh_A96vycU">