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

    <tr>
        <th>Summary</th>
        <td>
            [SelectionDAG] Large compile time regression
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            backend:X86
      </td>
    </tr>

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

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

<pre>
    The patch D118943 results in over an hour long compile times for large global constructors (3db39e74792d774c9d413710d690daf31b1d0d0c).  This is a regression in LLVM 15, the compile time pre LLVM 15 (and without the patch) was approximately 10 seconds.

In the case of the reproducer (linked below), D118943 results in extremely large `TokenFactors` being generated and frequently modified which results in all their operands being recursively added back to the worklist. The `TokenFactor`s are large enough that this behaviour results in an extremely large regression in compile time. We've created the reproducer from production code in which we originally observed the regression.

The flag `-combiner-tokenfactor-inline-limit` set to under 17 prevents the compile time regression from occurring.

Reproducer: https://gist.githubusercontent.com/omern1/283b4f0612e5b0cdb25c7d5c288c915a/raw/c3d9913f417023a64ca835e2dc7c6d4346b15536/repro.ll
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJx0lEuT4zQQxz-NculKSg_Ljg85DEyFomq5wBRwlaW2LUaWQktOdr49JWd2mezCJY9K1P37PyyTs58i4onpH5h-3pm1zIlOaUGKYjck93Z6mREuptgZnoU49o0CwryGksFHSFckMBHmtBKEFCewabn4gFD8ghnGRBAMTQhTSIMJYFPMhVZbEmVg8qjcoHrsmq6Xrusa27tGqE5w1_bcmVGJQTjuuGWyPwC8zD6Dz2CAcCLM2adYMT59-v0XEJrJH6HM-MAAF8Ivv9eFJjq4-TKntWz_3aQx2cPNZDCXC6XPfjEFwxsIDhltii4fGH9m_On--nO8LzEZIY3bZ8ILJbdapLoi-PiKDgYM6cZkX6n-wzr8XAiXuuduEGv5S3rFeDabOazlMKCPE0wYkUxBB5V9JPx7xVjCGyzJ-dGjg9vs7fxxtgmhcnmCdEEy0eX3WYR2peyvda1xrlIa-wolbTJuiV6Dz-UANfRHINbyDIbwnRZjWqcZymyqjb7On83V1xp85Phe5mNwH5M6wB_IZHdFsISb3m-sHSktcP9W6nmbHNYhd_k3hER-8tGE8AZpyEjXrzO-7HwIsoocg5mq0r1Ny-Aj0r5UzeOmee9j8BH3wS--1EAylurVGh0SiK5264qx5O9b90Hmhp2sXYl8nB4Ifv0qjqknmEu5ZKaemDwzeZ5qEJMv8zqsGcmmWDCWg00Lk-f7A8rkWR7V0Iy8FRL1wK0bpLad01Yej7YX2jB5JnNj8myV63uhxkZ0XCrTNtYclUbpbGdb16imHYTWqq0HKtUhhJ07Kder3uzwJNpOdq0Qrd7Np87odhhki93glDC6GRrVCydGbUfVKLHzJ8ml4oIrobVs9MG6TovmqJEb1x7bhjUcF-PDIYTrckg07XzOK550f-R8F8yAIW93kpS1oBgdU09_HlsmZb2m6FTP7Yd1yqzhtbL530nFl7BdaL9hwK0pz08_Mf0Mn7YC_k9Mu5XC6dsEqvnvjtfx72_7C6W_0BYmzxt1ZvK8gf8TAAD__7ChxlI">