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

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

[Richard Biener]

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.

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 ();
-    }
-
-  // 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

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

[Aldy Hernandez]

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 :).

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
>

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

[Richard Biener]

On Fri, 12 Aug 2022, 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 :).
> 
> 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.

OK, I'll push just the gimple_range_ssa_p then since that resolves
the PR on its own.  I was first misled about the gcc_unreachable
and my brain hurt understanding this function ... (also as to
why using range_of_expr on a _random_ stmt would be OK).

That said, nothing seems to be (publicly) using range_on_entry,
so if it shouldn't be used (but it's used privately!) then
make it private.

Thanks,
Richard.

> 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)

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

[Aldy Hernandez]

On Fri, Aug 12, 2022 at 1:36 PM Richard Biener <rguenther@suse.de> wrote:
>
> On Fri, 12 Aug 2022, 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 :).
> >
> > 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.
>
> OK, I'll push just the gimple_range_ssa_p then since that resolves
> the PR on its own.  I was first misled about the gcc_unreachable
> and my brain hurt understanding this function ... (also as to
> why using range_of_expr on a _random_ stmt would be OK).

Calling range_of_expr on a random stmt, is not OK, and is bound to
lead to subtle issues.  As I mentioned earlier, and both in the
comments for class path_range_query and
path_range_query::internal_range_of_expr, all we really support is
querying range_of_stmt and range_of_expr as it would appear at the end
of the path.

Internally to the path solver, if it uses range_of_expr and the SSA is
defined out side the path, we'll ignore the statement altogether and
return the range on entry to the path.  So yeah... feeding random
statements is not good.  It's meant to be used to query ranges of SSA
names at the end of the path.

Hmmm, perhaps I should rewrite
path_range_query::internal_range_of_expr() to explicitly ignore the
STMT, or even put some asserts if it's being used nonsensibly.

Aldy

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

[Andrew MacLeod]

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.  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
>>

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

[Andrew MacLeod]

On 8/12/22 09:38, 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.  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.
>
>
Actually, as I look at it, perhaps better to leave things as they are.. 
ie, not promote it to a part of the range_query API.. that appears 
fraught with derived issues in other places.

Continue to leave it in rangers public API and anyone using a ranger can 
use it. I will add the assert to make sure its not abused in the common 
way of the past.

And yes, this will dramatically simplify the path_entry routine :-)

Andrew

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

[Aldy Hernandez]

In that case Richi, go right ahead with your original patch. I for one am
happy we can use range_on_entry, which always seemed cleaner.

Aldy

On Fri, Aug 12, 2022, 16:07 Andrew MacLeod <amacleod@redhat.com> wrote:

>
> On 8/12/22 09:38, 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.  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.
> >
> >
> Actually, as I look at it, perhaps better to leave things as they are..
> ie, not promote it to a part of the range_query API.. that appears
> fraught with derived issues in other places.
>
> Continue to leave it in rangers public API and anyone using a ranger can
> use it. I will add the assert to make sure its not abused in the common
> way of the past.
>
> And yes, this will dramatically simplify the path_entry routine :-)
>
> Andrew
>
>

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

[Richard Biener]

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)