[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 #8 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:16b013c9d9b4d950f89821476e791bf18c1295df

commit r13-2020-g16b013c9d9b4d950f89821476e791bf18c1295df
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Aug 9 13:37:26 2022 +0200

    tree-optimization/106514 - revisit m_import compute in backward threading

    This revisits how we compute imports later used for the ranger path
    query during backwards threading.  The compute_imports function
    of the path solver ends up pulling the SSA def chain of regular
    stmts without limit and since it starts with just the gori imports
    of the path exit it misses some interesting names to translate
    during path discovery.  In fact with a still empty path this
    compute_imports function looks like not the correct tool.

    The following instead implements what it does during the path discovery
    and since we add the exit block we seed the initial imports and
    interesting names from just the exit conditional.  When we then
    process interesting names (aka imports we did not yet see the definition
    of) we prune local defs but add their uses in a similar way as
    compute_imports would have done.

    compute_imports also is lacking in its walking of the def chain
    compared to range_def_chain::get_def_chain which for example
    handles &_1->x specially through range_op_handler and
    gimple_range_operand1, so the code copies this.  A fix for
    compute_imports will be done separately, also fixing the unbound
    walk there.

    The patch also properly unwinds m_imports during the path discovery
    backtracking and from a debugging session I have verified the two
    sets evolve as expected now while previously behaving slightly erratic.

    Fortunately the m_imports set now also is shrunken significantly for
    the PR69592 testcase (aka PR106514) so that there's overall speedup
    when increasing --param max-jump-thread-duplication-stmts as
    15 -> 30 -> 60 -> 120 from 1s -> 2s -> 13s -> 27s to with the patch
    1s -> 2s -> 4s -> 8s.

    This runs into a latent issue in X which doesn't seem to expect
    any PHI nodes with a constant argument on an edge inside the path.
    But we now have those as interesting, for example for the ICEing
    g++.dg/torture/pr100925.C which just has sth like

      if (i)
        x = 1;
      else
        x = 5;
      if (x == 1)
        ...

    where we now have the path from if (i) to if (x) and the PHI for x
    in the set of imports to consider for resolving x == 1 which IMHO
    looks exactly like what we want.  The path_range_query::ssa_range_in_phi
    papers over the issue and drops the range to varying instead of
    crashing.  I didn't want to mess with this any further in this patch
    (but I couldn't resist replacing the loop over PHI args with
    PHI_ARG_DEF_FROM_EDGE, so mind the re-indenting).

            PR tree-optimization/106514
            * tree-ssa-threadbackward.cc (back_threader::find_paths_to_names):
            Compute and unwind both m_imports and interesting on the fly during
            path discovery.
            (back_threader::find_paths): Compute the original m_imports
            from just the SSA uses of the exit conditional.  Drop
            handling single_succ_to_potentially_threadable_block.
            * gimple-range-path.cc (path_range_query::ssa_range_in_phi): Handle
            constant PHI arguments without crashing.  Use
PHI_ARG_DEF_FROM_EDGE.

            * gcc.dg/tree-ssa/ssa-thread-19.c: Un-XFAIL.
            * gcc.dg/tree-ssa/ssa-thread-20.c: New testcase.