| Issue |
58203
|
| Summary |
Jump threading takes too long when the threading chain is too long
|
| Labels |
slow-compile,
llvm:compiletime,
llvm
|
| Assignees |
UsmanNadeem
|
| Reporter |
UsmanNadeem
|
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
```
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
