https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90316
--- Comment #28 from Richard Biener <rguenth at gcc dot gnu.org> --- Created attachment 46339 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=46339&action=edit untested patch This is another patch. It changes the iteration scheme to RPO order instead of DOM order to not require iteration unless AVAIL_OUT changes on a backedge (which usually should not happen for regular PRE insertions...). Your reduced testcases were all acyclic so this should fix the slowness there.