Re: [PATCH] tree-optimization/106593 - fix ICE with backward threading

[Richard Biener <rguenther@suse.de>]

On Fri, 12 Aug 2022, Andrew MacLeod wrote:

> 
> On 8/12/22 07:31, Aldy Hernandez wrote:
> > On Fri, Aug 12, 2022 at 12:59 PM Richard Biener <rguenther@suse.de> wrote:
> >> With the last re-org I failed to make sure to not add SSA names
> >> nor supported by ranger into m_imports which then triggers an
> >> ICE in range_on_path_entry because range_of_expr returns false.  I've
> >> noticed that range_on_path_entry does mightly complicated things
> >> that don't make sense to me and the commentary might just be
> >> out of date.  For the sake of it I replaced it with range_on_entry
> >> and statistics show we thread _more_ jumps with that, so better
> >> not do magic there.
> > Hang on, hang on.  range_on_path_entry was written that way for a
> > reason.  Andrew and I had numerous discussions about this.  For that
> > matter, my first implementation did exactly what you're proposing, but
> > he had reservations about using range_on_entry, which IIRC he thought
> > should be removed from the (public) API because it had a tendency to
> > blow up lookups.
> >
> > Let's wait for Andrew to chime in on this.  If indeed the commentary
> > is out of date, I would much rather use range_on_entry like you
> > propose, but he and I have fought many times about this... over
> > various versions of the path solver :).
> 
> The original issue with range-on-entry is one needed to be very careful with
> it.  If you ask for range-on-entry of something which is not dominated by the
> definition, then the cache filling walk was getting filled all the way back to
> the top of the IL, and that was both a waste of time and memory., and in some
> pathological cases was outrageous.

I think this won't happen with the backthreader sanitizing of m_imports.

I have pushed the change given the comments made later.

Thanks,
Richard.

>  And it was happening more frequently than
> one imagines... even if accidentally.  I think the most frequent accidental
> misuse we saw was calling range on entry for a def within the block, or a PHI
> for the block.
> 
> Its a legitimate issue for used before defined cases, but there isnt much we
> can do about those anyway,
> 
> range_of_expr on any stmt within a block, when the definition comes from
> outside he block causes ranger to trigger its internal range-on-entry "more
> safely", which is why it didn't need to be part of the API... but i admit it
> does cause some conniptions when for instance there is no stmt in the block.
> 
> That said, the improvements since then to the cache to be able to always use
> dominators, and selectively update the cache at strategic locations probably
> removes most issues with it. That plus we're more careful about timing things
> these days to make sure something horrid isn't introduced.  I also notice all
> my internal range_on_entry and _exit routines have evolved and are much
> cleaner than they once were.
> 
> So. now that we are sufficiently mature in this space...  I think we can
> promote range_on_entry and range_on_exit to full public API..  It does seem
> that there is some use practical use for them.
> 
> Andrew
> 
> PS. It might even be worthwhile to add an assert to make sure it isnt being
> called on the def block.. just to avoid that particular stupidty :-)   I'll
> take care of doing this.
> 
> 
> 
> 
> 
> > For now I would return VARYING in range_on_path_entry if range_of_expr
> > returns false.  We shouldn't be ICEing when we can gracefully handle
> > things.  This gcc_unreachable was there to catch implementation issues
> > during development.
> >
> > I would keep your gimple_range_ssa_p check regardless.  No sense doing
> > extra work if we're absolutely sure we won't handle it.
> >
> > Aldy
> >
> >> Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
> >>
> >> Will push if that succeeds.
> >>
> >>          PR tree-optimization/106593
> >>          * tree-ssa-threadbackward.cc (back_threader::find_paths):
> >>          If the imports from the conditional do not satisfy
> >>          gimple_range_ssa_p don't try to thread anything.
> >>          * gimple-range-path.cc (range_on_path_entry): Just
> >>          call range_on_entry.
> >> ---
> >>   gcc/gimple-range-path.cc       | 33 +--------------------------------
> >>   gcc/tree-ssa-threadbackward.cc |  6 +++++-
> >>   2 files changed, 6 insertions(+), 33 deletions(-)
> >>
> >> diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
> >> index b6148eb5bd7..a7d277c31b8 100644
> >> --- a/gcc/gimple-range-path.cc
> >> +++ b/gcc/gimple-range-path.cc
> >> @@ -153,38 +153,7 @@ path_range_query::range_on_path_entry (vrange &r, tree
> >> name)
> >>   {
> >>     gcc_checking_assert (defined_outside_path (name));
> >>     basic_block entry = entry_bb ();
> >> -
> >> -  // Prefer to use range_of_expr if we have a statement to look at,
> >> -  // since it has better caching than range_on_edge.
> >> -  gimple *last = last_stmt (entry);
> >> -  if (last)
> >> -    {
> >> -      if (m_ranger->range_of_expr (r, name, last))
> >> -       return;
> >> -      gcc_unreachable ();
> >> -    }
> > I
> >> -
> >> -  // If we have no statement, look at all the incoming ranges to the
> >> -  // block.  This can happen when we're querying a block with only an
> >> -  // outgoing edge (no statement but the fall through edge), but for
> >> -  // which we can determine a range on entry to the block.
> >> -  Value_Range tmp (TREE_TYPE (name));
> >> -  bool changed = false;
> >> -  r.set_undefined ();
> >> -  for (unsigned i = 0; i < EDGE_COUNT (entry->preds); ++i)
> >> -    {
> >> -      edge e = EDGE_PRED (entry, i);
> >> -      if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
> >> -         && m_ranger->range_on_edge (tmp, e, name))
> >> -       {
> >> -         r.union_ (tmp);
> >> -         changed = true;
> >> -       }
> >> -    }
> >> -
> >> -  // Make sure we don't return UNDEFINED by mistake.
> >> -  if (!changed)
> >> -    r.set_varying (TREE_TYPE (name));
> >> +  m_ranger->range_on_entry (r, entry, name);
> >>   }
> >>
> >>   // Return the range of NAME at the end of the path being analyzed.
> >> diff --git a/gcc/tree-ssa-threadbackward.cc
> >> b/gcc/tree-ssa-threadbackward.cc
> >> index 0a992213dad..669098e4ec3 100644
> >> --- a/gcc/tree-ssa-threadbackward.cc
> >> +++ b/gcc/tree-ssa-threadbackward.cc
> >> @@ -525,7 +525,11 @@ back_threader::find_paths (basic_block bb, tree name)
> >>         bitmap_clear (m_imports);
> >>         ssa_op_iter iter;
> >>         FOR_EACH_SSA_TREE_OPERAND (name, stmt, iter, SSA_OP_USE)
> >> -       bitmap_set_bit (m_imports, SSA_NAME_VERSION (name));
> >> +       {
> >> +         if (!gimple_range_ssa_p (name))
> >> +           return;
> >> +         bitmap_set_bit (m_imports, SSA_NAME_VERSION (name));
> >> +       }
> >>
> >>         // Interesting is the set of imports we still not have see
> >>         // the definition of.  So while imports only grow, the
> >> --
> >> 2.35.3
> >>
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg,
Germany; GF: Ivo Totev, Andrew Myers, Andrew McDonald, Boudien Moerman;
HRB 36809 (AG Nuernberg)