<table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Issue</th>
<td>
<a href=https://github.com/llvm/llvm-project/issues/58203>58203</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>
Jump threading takes too long when the threading chain is too long
</td>
</tr>
<tr>
<th>Labels</th>
<td>
slow-compile,
llvm:compiletime,
llvm
</td>
</tr>
<tr>
<th>Assignees</th>
<td>
UsmanNadeem
</td>
</tr>
<tr>
<th>Reporter</th>
<td>
UsmanNadeem
</td>
</tr>
</table>
<pre>
Input file: https://gist.github.com/UsmanNadeem/bfa78d0390d103275792afdd21069d2c
Command: `opt -jump-threading file.ll`
Currently takes more than 80 minutes on my machine.
My attempt to fix it by reversing the iteration order: https://reviews.llvm.org/D135125
Essentially the file I was compiling had many lines of fortran code of this form: `arr(:ncol,:) = 0`. The dimensions of this 2d array in this case are statically known. When compiling with flang-new this is converted into a nested loop with a store. Loop passes convert it into the form it is in the input file above i.e. unrolled with memset/memcpys.
Just before Jump Threading is run we have tens of thousands of branches containing GEP + memsets and memcpys and each
threadable chain is very long as well.
90% of the time was spent in renaming non-local uses of instructions in updateSSA(). Profiling showed that about half that time was spent in `llvm::SSAUpdaterImpl<llvm::SSAUpdater>::BuildBlockList` and the other half in the `SSAUpdater::FindAvailableVals() --> FindExistingPHI()` call.
The issue is that we were accumulating new PHIs as we kept on threading the successors BBs.
`%uglygep.13072` is defined in` ._crit_edge2292` and used in `.lr.ph2291.1 and .lr.ph2669.1`. `._crit_edge2292` gets replicated and a phi node put in its successor `._crit_edge2292.1`.
Next time `._crit_edge2292.1` gets replicated with 1 phi node and one gep, after one more iteration `._crit_edge2292.2` gets replicated with 2 phi nodes and one gep, this goes on until we reach `._crit_edge2292.24` when we have 24 phi nodes that need to be replicated and rewritten.
```
Threading edge from '._crit_edge2292.23.thread' to '._crit_edge2292.25, across block:
._crit_edge2292.24: ; preds = %._crit_edge2292.23.thread, %.lr.ph2291.24
%uglygep.243095600 = phi ptr [ %uglygep.243095576, %._crit_edge2292.23.thread ], [ %uglygep.243095, %.lr.ph2291.24 ]
%uglygep.223093506530599 = phi ptr [ %uglygep.223093484, %._crit_edge2292.23.thread ], [ %uglygep.223093, %.lr.ph2291.24 ]
%uglygep.203091420442505531598 = phi ptr [ %uglygep.203091400, %._crit_edge2292.23.thread ], [ %uglygep.203091, %.lr.ph2291.24 ]
%uglygep.183089342362419443504532597 = phi ptr [ %uglygep.183089324, %._crit_edge2292.23.thread ], [ %uglygep.183089, %.lr.ph2291.24 ]
%uglygep.163087272290341363418444503533596 = phi ptr [ %uglygep.163087256, %._crit_edge2292.23.thread ], [ %uglygep.163087, %.lr.ph2291.24 ]
%uglygep.143085210226271291340364417445502534595 = phi ptr [ %uglygep.143085196, %._crit_edge2292.23.thread ], [ %uglygep.143085, %.lr.ph2291.24 ]
%uglygep.123083156170209227270292339365416446501535594 = phi ptr [ %uglygep.123083144, %._crit_edge2292.23.thread ], [ %uglygep.123083, %.lr.ph2291.24 ]
%uglygep.103081110122155171208228269293338366415447500536593 = phi ptr [ %uglygep.103081100, %._crit_edge2292.23.thread ], [ %uglygep.103081, %.lr.ph2291.24 ]
%uglygep.830797282109123154172207229268294337367414448499537592 = phi ptr [ %uglygep.8307964, %._crit_edge2292.23.thread ], [ %uglygep.83079, %.lr.ph2291.24 ]
%uglygep.6307742507183108124153173206230267295336368413449498538591 = phi ptr [ %uglygep.6307736, %._crit_edge2292.23.thread ], [ %uglygep.63077, %.lr.ph2291.24 ]
%uglygep.43075202641517084107125152174205231266296335369412450497539590 = phi ptr [ %uglygep.4307516, %._crit_edge2292.23.thread ], [ %uglygep.43075, %.lr.ph2291.24 ]
%uglygep.23073610192740526985106126151175204232265297334370411451496540589 = phi ptr [ %uglygep.230734, %._crit_edge2292.23.thread ], [ %uglygep.23073, %.lr.ph2291.24 ]
%uglygep.130722511182839536886105127150176203233264298333371410452495541588 = phi ptr [ %uglygep.130721, %._crit_edge2292.23.thread ], [ %uglygep.13072, %.lr.ph2291.24 ]
%uglygep.3307412172938546787104128149177202234263299332372409453494542587 = phi ptr [ %uglygep.330749, %._crit_edge2292.23.thread ], [ %uglygep.33074, %.lr.ph2291.24 ]
%uglygep.530763037556688103129148178201235262300331373408454493543586 = phi ptr [ %uglygep.5307625, %._crit_edge2292.23.thread ], [ %uglygep.53076, %.lr.ph2291.24 ]
%uglygep.73078566589102130147179200236261301330374407455492544585 = phi ptr [ %uglygep.7307849, %._crit_edge2292.23.thread ], [ %uglygep.73078, %.lr.ph2291.24 ]
%uglygep.9308090101131146180199237260302329375406456491545584 = phi ptr [ %uglygep.9308081, %._crit_edge2292.23.thread ], [ %uglygep.93080, %.lr.ph2291.24 ]
%uglygep.113082132145181198238259303328376405457490546583 = phi ptr [ %uglygep.113082121, %._crit_edge2292.23.thread ], [ %uglygep.113082, %.lr.ph2291.24 ]
%uglygep.133084182197239258304327377404458489547582 = phi ptr [ %uglygep.133084169, %._crit_edge2292.23.thread ], [ %uglygep.133084, %.lr.ph2291.24 ]
%uglygep.153086240257305326378403459488548581 = phi ptr [ %uglygep.153086225, %._crit_edge2292.23.thread ], [ %uglygep.153086, %.lr.ph2291.24 ]
%uglygep.173088306325379402460487549580 = phi ptr [ %uglygep.173088289, %._crit_edge2292.23.thread ], [ %uglygep.173088, %.lr.ph2291.24 ]
%uglygep.193090380401461486550579 = phi ptr [ %uglygep.193090361, %._crit_edge2292.23.thread ], [ %uglygep.193090, %.lr.ph2291.24 ]
%uglygep.213092462485551578 = phi ptr [ %uglygep.213092441, %._crit_edge2292.23.thread ], [ %uglygep.213092, %.lr.ph2291.24 ]
%uglygep.233094552577 = phi ptr [ %uglygep.233094529, %._crit_edge2292.23.thread ], [ %uglygep.233094, %.lr.ph2291.24 ]
%uglygep.253096 = getelementptr i8, ptr %40, i64 800, !dbg !127
br i1 %.not2713, label %._crit_edge2292.25, label %.lr.ph2291.25, !dbg !127
JT: Renaming non-local uses of: %uglygep.243095600 = phi ptr [ %uglygep.243095, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.223093506530599 = phi ptr [ %uglygep.223093, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.203091420442505531598 = phi ptr [ %uglygep.203091, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.183089342362419443504532597 = phi ptr [ %uglygep.183089, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.163087272290341363418444503533596 = phi ptr [ %uglygep.163087, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.143085210226271291340364417445502534595 = phi ptr [ %uglygep.143085, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.123083156170209227270292339365416446501535594 = phi ptr [ %uglygep.123083, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.103081110122155171208228269293338366415447500536593 = phi ptr [ %uglygep.103081, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.830797282109123154172207229268294337367414448499537592 = phi ptr [ %uglygep.83079, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.6307742507183108124153173206230267295336368413449498538591 = phi ptr [ %uglygep.63077, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.43075202641517084107125152174205231266296335369412450497539590 = phi ptr [ %uglygep.43075, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.23073610192740526985106126151175204232265297334370411451496540589 = phi ptr [ %uglygep.23073, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.130722511182839536886105127150176203233264298333371410452495541588 = phi ptr [ %uglygep.13072, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.3307412172938546787104128149177202234263299332372409453494542587 = phi ptr [ %uglygep.33074, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.530763037556688103129148178201235262300331373408454493543586 = phi ptr [ %uglygep.53076, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.73078566589102130147179200236261301330374407455492544585 = phi ptr [ %uglygep.73078, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.9308090101131146180199237260302329375406456491545584 = phi ptr [ %uglygep.93080, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.113082132145181198238259303328376405457490546583 = phi ptr [ %uglygep.113082, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.133084182197239258304327377404458489547582 = phi ptr [ %uglygep.133084, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.153086240257305326378403459488548581 = phi ptr [ %uglygep.153086, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.173088306325379402460487549580 = phi ptr [ %uglygep.173088, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.193090380401461486550579 = phi ptr [ %uglygep.193090, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.213092462485551578 = phi ptr [ %uglygep.213092, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.233094552577 = phi ptr [ %uglygep.233094, %.lr.ph2291.24 ]
JT: Renaming non-local uses of: %uglygep.253096 = getelementptr i8, ptr %40, i64 800, !dbg !127
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy1Wltz2zYW_jXyC8Ya3C8PeoiTdJtO28ls293HDkVCEhuK1PASxf9-PwCyI8cOZ8nQHo8kgjjnfOcOYLBtivvNh_o09GRXVn4l3pBD3586_Fjxn_C_L7t-vS_7w7Bd580RI391x6z-PSu8D0_bXWZsQYWjBaOCG2Ucz3ZFwRnVruD5ir5b0TdvmyOIisB-pWlz6sntP8PxdNsfWp8VZb2P0tdVhbcXiqFtfd1X96TPPvmOHJvWk_6Q1cRScizrocdgU5PjPTlm-aGs_ZokyvT52z3J-t4fIapvwP0LKXuyvSet_-zbLkjsDx5jvs36EnyatvDtc_UxvfTnDsg-H9dNu8fQOyYU4-pa2PuuA9YyqwJcsA3KkA_knHUENjuVVZB3yApAre8JngL2Hdk1bd9Co7wpfHjuD2UXBo8XO2Vtu-IWD3XeVCv-NqJyZCXeEYrXa_InZBXl0dcdVOgeWfCCgDS7J2WdBvKs8xjypOuhbR5xfqqbc70m_z34-grkGZ4muyqr97e1PyfqwKCpYbbeF2AJc2YEGoSnqmlOiSYDb7hoTX4NQ6cMFnkkC6aPdNE20C8OdAkenPAYfiTbNp8xsAafoW6bqoKMyP7oj53vYX38yE_33fra_L8MHXzrdyFEfkFYwS4PYQUp7VCTs4f5wbn3D2Zqhg4BGR-28EF-SHD7rKwD3b_efyQrfneR2xHMJRfR8bdHzCXhKYSzLdDnB1AHkVAabm7ABxFw9lX1BK6jK64SCiCC-2KgdCeEUDAJwj47Bgx1U99WDbxFhi4FTFl3fTvkffQ2pg6nIuv9H3-8CWHC3Zp8bJtdcmR3aM4wHjKmD1aFgQ9ZtUvPz2UimkKEhwATb8Dvr8i4_XA8VSvx9qVXK_E-Dd0NZVXcAeenX1EqwCjaJ6jW4KNNYi-exttrDoH8p7Iu3nzOyipY8D9Z1SVVyO0tJJDw9v0X8IVKH3_-kN4FGSGGnxg1pELZdUP4TFrC52ePiMjyfDgOVdZHmyKowahLjiGfPOpDE8A9BEyA2Q157ruuaTtyd_c01EJ94mrYV_d7f1ozQQ0PcCCz8DvkdUiQMLD-O2_L_m9f7D3njj-YBY4sLvZeV-36dMBLtmbx3WVAa7dmMbvDx3M2-xCOrT9VyOOQgoE0I6dDiXhBGQmpFIIQkx7VeIFTEpF0-t1_ucTEd-Y9kxlTkn0VGjA0tce8E8oUyXZwbxyIVftrkX2B_4s6Rf78kX_3rYBYlvZN6gADKm8VnNmGpHxRhgxCzqHSPRQCLq-4x3CpfUiXBnXkW-u2_gx2KB3PIiH9x0dyVXSCYLJrmyNKiHkGRqxTtOFdkPfSFBWtmLdN15FtSK2QK1eyX1AQHWP8byXuyKn1KHmhfyCIR4C9je-_Bij4X5S8Cn4uBXVKUxoZBmueeoSauns-SRn9wPR7QkH4Ls55if4lRJHgBVQcBEJRrQRVzo1ii1OllXOxRfop2CgImORUSq6oUoIpZ0cRJgJK5yKM9BMQMiuohU240FwyJyUsKZXgypkxnBcyPteSiX4KTg0Cww1mUSGZ0PiwUkpFhRJCOT2KNhGruTGZ6KegRRBbhRUx55obhrlCUqGlZAaQFeVKSOXUKObIgrnZmCP9FMwIbosA1cxQTh2HrfHDcSGc0EoyoNeKMiWUcnIUeWIkZ8dGpJ-CHEFvGWOUcc6UYjA4tZxbrh13QggrtJZMSWkUpQrKODGKP7GbnYOJfgJ-5IJxBngZcpfDBQgTzmmIda4td1III7SRMClql3NKGOX4mAqRo57rgEg9AT-yw5hQ4AzSmkF3VBKUOiM41fAl14YDM1JWW2SulE46q4RVjo3pELmKueEfqSfogGwxigMroCMBABTacMWQxFCNKrgFCzXuNIqN0E5CRxRKZ5Rwyo02xMiZzdUjUk_pOJgvNFLBcSMBW8PU2JgDPPRiQUWUelQlxZ0RQgpDJWNSMemQ41TZ8f4ZmM9unoF4SlaHpTY8wJjlFlZG9Fgohp24YahDRqPXoTjBY9xZZLkwDE6TikssP-BFO9poI3c2N8PjLuD_V0VgPiIGWe0Q9lIba4CUcQuzM2MQdhwdWAvuUK64MFxShyaMRFFIKzvaiSNvN1ORSDxBESyxDDIL9UdpuAOVLvQ2aZmxHNVXIN7gZioEQ8WSyCIUXazNsKiwow068uVqphaReoIWBvMtFEC0o0PDmUwaZhynNKyCdBgQQUkpYR3EkuNQQ9nRdh15zvZDpJ6ggUOHoY4izZlA-mpmkfAuRI5G80GCO7hIUi2VRoQpKGFHW3bkZ-emQ6SektmwMJqd4KHwoNM6y4XFihM2F0h1o1GIpEJU4wtOGm_Widf8VI70k8qSCN0BMtGyBUID3VIKbgRaIA1hIq1TWGnY0QZ94aLnBkyinwIbSWKxxMfSE8GGBb4WiFcalqHSoiZZZUe78YV-do4m-imAAdPCtqiKWO84AJeaSouwdsqONtxEye1s20b6KVARudiVWCppyEVpNZb4yoy20guNnh23kX7KwgCB7mBDDldjjazM-D40zZZz4SX6SesWEXqeQniOtrvLPD7XuYl-CjAE7mV3ufe9r_zR130AVsYQiRDRH6IrSi2Jfdg3sGK7D19Yrzyw3YKKRcF102MZE5dDVbb11YuqqKevr8Cq74h4ckb-Zzgi-vd3z5bTAdK8451x-02XPPUIZ2n5845pFkbxQ0cxS2P58eOWpREtdaSyNK5lj02WRvcaRyMLY3yl44-FUb7iIcfCSF_5KGPp2vvqBxZLp9Trn0ssjPjVjx8WxvuqpwwLY321s4SFcb7KicHSmbX4ucDiqb_c3n9paIvs75cG9YN7-KXhzN6nL93zZuzFF2-7U_bbSwtfbE_9zZ2MG79hqMVhiavdTbERhRMuu-nLvvKbeFHs6t5PvGXYN026txUvi8T7WY8zHm93PUy6Gdpq8-1tyauLkvHaVPq6PbXNPz4PF9jiJaUOP1AXqLg5bKwqAI_Zwmb4lRX5VtHd1u9yVvAc9eUm7vm7DVyx4ryrmvNtuq_n8ZgMwS83tC7j4S7PN-_wpN7dlJvQ3RnFgiosq-w6k1iX5LnabXco_KpYSeqPWVk93ne8aTcR_3bYd3hZlV3_9TLkTdZ15b72_oLtyc3QKDAb-kPTbq5e3ET9N1H5_wHVtKKc">