https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114855
--- Comment #28 from Richard Biener <rguenth at gcc dot gnu.org> ---
Just to clarify what the "handcuffs" in the backwards threader do and what
they don't. There is no limit on the number of cond/switch stmts (thus
basic-blocks) we consider as the exit of paths, but for each such exit
there is a limit on the number of paths we consider to it
(param_max_jump_thread_paths) and by that a limit on how many times
we instantiate a path_range_query and call range_of_stmt on that paths
exit statement (cond/switch).
So the number of path_range_query instantiations and range_of_stmt calls
should be linear in the number of basic-blocks with a constant factor
(param_max_jump_thread_paths).
At least that was the intent - placing a counter in
back_threader::find_taken_edge_{switch,cond} should be able to prove that
in case you'd have a testcase you can easily grow/shrink while preserving
its "pattern".
My observation was that instantiation of path_range_query and the
range_of_stmt call does work that is not on the order of the path size
but also scales at least linear with the size of the function - for the
CFG/stmt pattern of the testcase at hand at least. The identified
unlimited dominator walk has this property but might not be the main
time-sink in the end.
