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

    <tr>
        <th>Summary</th>
        <td>
            SelectionDAG's SimplifySelectOps can take a pathological amount of time
        </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>
    Consider the attached .bc file. This file is quite large (about 4MB uncompressed,
about 300k IR statements, all in one function with very large BBs). As such, it is no surprise that
compiling it may take same time. However, on LLVM master the compile time (`llc A2.bc`)
is excessive (I haven't actually been patient enough to let it finish yet, but
at least three hours). 

The compile time improves dramatically if I disable the SimplifySelectOps load reassociation:
```
diff --git a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index dd7f692ede90..17f96ab2efe5 100644
--- a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -24969,6 +24969,7 @@ bool DAGCombiner::SimplifySelectOps(SDNode *TheSelect, SDValue LHS,
 LLD->getBasePtr().getValueType()))
 return false;
 
+    return false;
 
     // Check that the select condition doesn't reach either load.  If so,
     // folding this will induce a cycle into the DAG.  If not, this is safe to
```

With this patch applied, the whole compilation finishes in about 25s, which seems
reasonable to me for this size IR.

I think there are some low-hanging fruits to improve performance slightly, but the
overall problem here is algorithmic. The
`SDNode::hasPredecessorHelper(LLD, Visited, Worklist))` check that is used to avoid
introducing cycles needs to essentially walk the entire function, which in functions
as large as this is very expensive.

I think there's a couple of options here:
1. Try some sort of different search heuristic. For example, we might do a BFS of successors instead from both points to establish a local topological order. The intuition here is that while in the common case the two nodes are not each other's predecessors, they likely flow into common successors, making that a more fruitful search direction. 
2. We could try maintaining an incremental topological order. The changes that DAGCombine makes are fairly local, which avoids some of the usual worst case behavior in topological maintenance algorithms.
3. We could just put a MaxNodes cutoff into this optimization. This is probably the easiest option, but not particularly satisfying.

I'm of course also working on making the frontend emit something nicer here and maybe have it split the function into a few parts, but it would be good to fix it in both places if possible.

[A2.bc.tar.gz](https://github.com/llvm/llvm-project/files/10451463/A2.bc.tar.gz)

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJykV99v4zgO_mvcF6KB46RJ85CH_rjMFNfZW2wHM8-0TMfayqJPlJNm_voDJafp3O0ecHuAkTaWRJEfv49kUMTuPdG2uLkvbh6vcIwdh-3fyfNVzc1p-8BebEMBYkeAMaLpqIFZbaC1jmbwtbOS_gUr8M_RRgKHYU9QVLdY8xhh-eUeRm-4HwKJUFNUD0X5WJR3eXlRlq_w9BtIxEg9-ShF9QDoHFgP7Ana0Zto2cPRxg4OFE7TDff3UlSbGdwJyGg6PWajuuEZZAxDsEIQO4z5OvXAOuv3uqvHE0R8JRDsCaLtaQaf-UgHCmqHPTw_f_sCPUqcYs_H814NrliVzhm4q2a1KVZlUW3yNVaA3gyJ2EPa9wQdHsgX1ToCmjiicyeoiTwMGC35COR53HcQGRxFda613koHJ4rqSz1OAWAERygRYheIoOMxZADycv78-u-u2n4IfCCBJmCP0ZrkgG3hCRorWOu-juDF9oOz7emFHJn4j0HAMTYQCEXYWNQMFIvpEo03P-lrY9sWrq_3NgIW1c65Q69_bF1Uuwdu6JOGv8uWLfvHu09FtXu8-_TAfW09hZkZBqj_6skJdt_QGzTNul1tKmpoU85m83W7WWFdUUs3MC_L1XKZN19fX_91TycIqvv8_L-OF8uyWJZwXS03q01RPaygqO7PX9YwLdfMDj6c11Qs7v4jaUV1-_L4CzfKPKVCXlAWvTx-QzcSPH9-eRcgPD8_XheLv-0p3qPQrzEor6vNbE8x7f56Gii_mp58LFAcg4cWnVCxuJ_evuMCAP91i65DUe2KagcPHZnXJNLEQkn-gmHf2KT5hkmydgKh6YBs7Cgkbs4AnloQvoTzwW7LrlGpRy1PR5uqSTMaAgRzMlqtfOR05ePdp2zJcwIqnbACgi1B5D8kfP78rvUobR8wmg5wGJxN9S0ZPnbszlpM8pl0TaKVLRe_6iZVu2NnTQdC1Es2rbJjn8XJ0BO0HPJVYn8QPP02--jIky55hZECAQYC4Z7A8fG6Q79XHNow2ihqbKoHMFBoOfToDYE4u--iO03lRg1ly3ygoKV4CFw76iFdYAXQ7TnY2PXWaAugd5Qy-zI7O5RfAzWkxZDDZ3KDFtfb5-dHveebFRszWt85vDorcSLZqgRzoYUVGIUadR0PbJuz3GPgZjQaW0qogCdqUoTaZXy0qc4d0SVcQN-ESzO5oG79-8sJfJSpwaC8syG1HXobyGtd_3P0i2otyjEeB0fALfCQLCfk3uvnfAZfwylnSThE3ahFlIL2AyEMpoOOxmAlKsI7DkBv2A-OkuMEvSYMGgaE-92LnpfRZKCVXhIJG2gD91Bz7GBg6-METsTaaXtBcGzQQeSBHe-1MQCHhkLKqApkzBo8Jz2l49ilXu_PPbFnDwYlN5F4ZPDckCQSeo6QRMsKTUJmuPBBJp2cwNlXcidoHR-zLCezl4h0a4-vWdAYAaFnTaaSuh3dGbHGhlxuzy2xmsF39XJ0DcRwgh6tj2i9GkIP1puQRo4_R8GogGiK_VJ_1ZspyhZtcKeM5YVViaqSM8xtAmeUER0cOUjMiNXU4cFySGh-uD55ST4p811oMnFu8SGk30eJMIyKxxd8-yUBb8bIbXsub1YSAXv7AzMuXyc-q6CxdqesDRRLEieunouApm_AEK0ZHWqIgtFKe7J-_zP_i2rda5BGBxJ1WVjDTOlif0mcJow1sgaotzGBo9LZg7eGQuYZ-kaHs5rS2KTTkAzO5u7wPgmm6BBaOiYP5eyyjXBMyNQEe-ZUNFr7lsZCPynBodEK3MLAIrZ2P4u5uLlPE90sYpjtfxQ3j0V128U4iIo39Za9jd1Yzwz3Hxq_O_TXQ-DfU7fd6TwsRbWbl8ub-XK1KKrdT1bPnfSq2S6azWKDV7Sdr9bL8rasysVVt6VmsTTrdr2qNwabRbmq5ytssFmtb1eEq_bKbquyWpTz-W1VzVfLxWyJbb0pSyqJcN6Wi2JZUo_WzdS1GYf9lRUZabsq54vqymFNTtLQX1WejpAWi6rS3wBhm8Kpx70Uy1ILs1ysRBsdbX8ebNbyB-OjQZ8nbNT22L2zG3sefap4Op5ejcFt_2d8k7cKcIrmXwEAAP__7_4_gA">