[Bug tree-optimization/106514] [12/13 Regression] ranger slowness in path query

["cvs-commit at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106514

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:409978d58dafa689c5b3f85013e2786526160f2c

commit r13-1998-g409978d58dafa689c5b3f85013e2786526160f2c
Author: Richard Biener <rguenther@suse.de>
Date:   Mon Aug 8 12:20:04 2022 +0200

    tree-optimization/106514 - add --param max-jump-thread-paths

    The following adds a limit for the exponential greedy search of
    the backwards jump threader.  The idea is to limit the search
    space in a way that the paths considered are the same if the search
    were in BFS order rather than DFS.  In particular it stops considering
    incoming edges into a block if the product of the in-degrees of
    blocks on the path exceeds the specified limit.

    When considering the low stmt copying limit of 7 (or 1 in the size
    optimize case) this means the degenerate case with maximum search
    space is a sequence of conditions with no actual code

      B1
       |\
       | empty
       |/
      B2
       |\
       ...
      Bn
       |\

    GIMPLE_CONDs are costed 2, an equivalent GIMPLE_SWITCH already 4, so
    we reach 7 already with 3 middle conditions (B1 and Bn do not count).
    The search space would be 2^4 == 16 to reach this.  The FSM threads
    historically allowed for a thread length of 10 but is really looking
    for a single multiway branch threaded across the backedge.  I've
    chosen the default of the new parameter to 64 which effectively
    limits the outdegree of the switch statement (the cases reaching the
    backedge) to that number (divided by 2 until I add some special
    pruning for FSM threads due to the loop header indegree).  The
    testcase ssa-dom-thread-7.c requires 56 at the moment (as said,
    some special FSM thread pruning of considered edges would bring
    it down to half of that), but we now get one more threading
    and quite some more in later threadfull.  This testcase seems to
    be difficult to check for expected transforms.

    The new testcases add the degenerate case we currently thread
    (without deciding whether that's a good idea ...) plus one with
    an approripate limit that should prevent the threading.

    This obsoletes the mentioned --param max-fsm-thread-length but
    I am not removing it as part of this patch.  When the search
    space is limited the thread stmt size limit effectively provides
    max-fsm-thread-length.

    The param with its default does not help PR106514 enough to unleash
    path searching with the higher FSM stmt count limit.

            PR tree-optimization/106514
            * params.opt (max-jump-thread-paths): New.
            * doc/invoke.texi (max-jump-thread-paths): Document.
            * tree-ssa-threadbackward.cc (back_threader::find_paths_to_names):
            Honor max-jump-thread-paths, take overall_path argument.
            (back_threader::find_paths): Pass 1 as initial overall_path.

            * gcc.dg/tree-ssa/ssa-thread-16.c: New testcase.
            * gcc.dg/tree-ssa/ssa-thread-17.c: Likewise.
            * gcc.dg/tree-ssa/ssa-dom-thread-7.c: Adjust.