https://gcc.gnu.org/bugzilla/show_bug.cgi?id=116398
--- Comment #23 from Richard Sandiford <rsandifo at gcc dot gnu.org> --- (In reply to Segher Boessenkool from comment #22) > (In reply to Richard Sandiford from comment #18) > > but: the problem in PR101523 was that, after each > > successful 2->2 attempt, distribute_links would search further and further > > for the new next combinable use of the i2 destination. > > And the way it searches is linear in time, yeah. Making that better will > require keeping some extra data structure up to date throughout combine, not > something that will likely be a great success. Or do you see some other > possibility? Nah, I agree. I don't see an easy way of doing that without using different data structures (and possibly not even then). One thing I used in "rtl-ssa" (yeah, bit of a misleading name) was to combine a splay tree with a linked list, so that each node belonged to both the tree and the list. The splay tree allows for sublinear random updates while the linked list means that in-order traversal is still linear and neighbouring accesses are still constant-time. > > So rather than > > adding a LUID-based limit to try_combine, how about just limiting the > > distribute_links to a certain number of instructions when i2 is unchanged? > > That does not sound too bad. Heck, even limiting it *always* could be done! Yeah, I'd wondered about limiting it an all cases too. Definitely seems worth trying. But given that we're in stage 4, maybe it would make sense to apply the limit only to the "newly re-enabled" cases for GCC 15 and consider a universal limit for GCC 16. > > Does this seem like a plausible approach? I'm going to be away for the next > > couple of weeks so wouldn't be able to take it further for a while. > > Do you see time to still post the patch today? I'll be disappearing very soon, so don't have time to do a test run. > If not, I'll pick it up. Thanks, that'd be great.
