PR tree-optimization/109417 - Check if dependency is valid before using in may_recompute_p.

When a statement is first processed, any SSA_NAMEs that are dependencies 
are cached for quick future access.

if we ;later rewrite the statement (say propagate a constant into it), 
its possible the ssa-name in this cache is no longer active.   Normally 
this is not a problem, but the changed to may_recompute_p forgot to take 
that into account, and was checking a dependency from the cache that was 
in the SSA_NAME_FREE_LIST. It thus had no SSA_NAME_DEF_STMT when we were 
expecting one.

This patch simply rejects dependencies from consideration if they are in 
the free list.

Bootstrapping on x86_64-pc-linux-gnu  and presuming no regressio0ns, OK 
for trunk?

Andrew

On 4/5/23 14:10, Andrew MacLeod via Gcc-patches wrote:
> When a statement is first processed, any SSA_NAMEs that are dependencies 
> are cached for quick future access.
> 
> if we ;later rewrite the statement (say propagate a constant into it), 
> its possible the ssa-name in this cache is no longer active.   Normally 
> this is not a problem, but the changed to may_recompute_p forgot to take 
> that into account, and was checking a dependency from the cache that was 
> in the SSA_NAME_FREE_LIST. It thus had no SSA_NAME_DEF_STMT when we were 
> expecting one.
> 
> This patch simply rejects dependencies from consideration if they are in 
> the free list.
> 
> Bootstrapping on x86_64-pc-linux-gnu  and presuming no regressio0ns, OK 
> for trunk?
eek.  So you've got a released name in the cache?  What happens if the 
name gets released, then re-used?  Aren't you going to get bogus results 
in that case?

jeff

On Wed, Apr 05, 2023 at 04:10:25PM -0400, Andrew MacLeod via Gcc-patches wrote:
> When a statement is first processed, any SSA_NAMEs that are dependencies are
> cached for quick future access.
> 
> if we ;later rewrite the statement (say propagate a constant into it), its
> possible the ssa-name in this cache is no longer active.   Normally this is
> not a problem, but the changed to may_recompute_p forgot to take that into
> account, and was checking a dependency from the cache that was in the
> SSA_NAME_FREE_LIST. It thus had no SSA_NAME_DEF_STMT when we were expecting
> one.
> 
> This patch simply rejects dependencies from consideration if they are in the
> free list.
> 
> Bootstrapping on x86_64-pc-linux-gnu  and presuming no regressio0ns, OK for
> trunk?
> 
> Andrew

> commit ecd86e159e8499feb387bc4d99bd37a5fd6a0d68
> Author: Andrew MacLeod <amacleod@redhat.com>
> Date:   Wed Apr 5 15:59:38 2023 -0400
> 
>     Check if dependency is valid before using in may_recompute_p.
>     
>     When the IL is rewritten after a statement has been processed and
>     dependencies cached, its possible that an ssa-name in the dependency
>     cache is no longer in the IL.  Check this before trying to recompute.
>     
>             PR tree-optimization/109417
>             gcc/
>             * gimple-range-gori.cc (gori_compute::may_recompute_p): Check if
>             dependency is in SSA_NAME_FREE_LIST.
>     
>             gcc/testsuite/
>             * gcc.dg/pr109417.c: New.

Ok for trunk (mainly to unbreak the recent regression).
But please be ready to adjust if Richi disagrees next week.

> --- a/gcc/gimple-range-gori.cc
> +++ b/gcc/gimple-range-gori.cc
> @@ -1314,7 +1314,9 @@ gori_compute::may_recompute_p (tree name, basic_block bb, int depth)
>    tree dep2 = depend2 (name);
>  
>    // If the first dependency is not set, there is no recomputation.
> -  if (!dep1)
> +  // Dependencies reflect original IL, not current state.   Check if the
> +  // SSA_NAME is still valid as well.
> +  if (!dep1 || SSA_NAME_IN_FREE_LIST (dep1))
>      return false;
>  
>    // Don't recalculate PHIs or statements with side_effects.

	Jakub

On Wed, Apr 5, 2023 at 11:53 PM Jeff Law via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
>
>
> On 4/5/23 14:10, Andrew MacLeod via Gcc-patches wrote:
> > When a statement is first processed, any SSA_NAMEs that are dependencies
> > are cached for quick future access.
> >
> > if we ;later rewrite the statement (say propagate a constant into it),
> > its possible the ssa-name in this cache is no longer active.   Normally
> > this is not a problem, but the changed to may_recompute_p forgot to take
> > that into account, and was checking a dependency from the cache that was
> > in the SSA_NAME_FREE_LIST. It thus had no SSA_NAME_DEF_STMT when we were
> > expecting one.
> >
> > This patch simply rejects dependencies from consideration if they are in
> > the free list.
> >
> > Bootstrapping on x86_64-pc-linux-gnu  and presuming no regressio0ns, OK
> > for trunk?
> eek.  So you've got a released name in the cache?  What happens if the
> name gets released, then re-used?  Aren't you going to get bogus results
> in that case?

We never re-use SSA names from within the pass releasing it.  But if
the ranger cache
persists across passes this could be a problem.  See
flush_ssaname_freelist which
for example resets the SCEV hash table which otherwise would have the
same issue.

IIRC ranger never outlives a pass so the patch should be OK.

_But_ I wonder how ranger gets at the tree SSA name in the first place - usually
caches are indexed by SSA_NAME_VERSION (because that's cheaper and
better than a pointer to the tree) and ssa_name (ver) will return NULL
for released
SSA names.  So range_def_chain::rdc could be just

  struct rdc {
   int ssa1;           // First direct dependency
   int ssa2;           // Second direct dependency
   bitmap bm;           // All dependencies
   bitmap m_import;
  };

and ::depend1 return ssa_name (m_def_chain[v].ssa1) and everything would
work automatically (and save 8 bytes of storage).

Richard.

> jeff

On 4/11/23 05:21, Richard Biener via Gcc-patches wrote:
> On Wed, Apr 5, 2023 at 11:53 PM Jeff Law via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>>
>>
>> On 4/5/23 14:10, Andrew MacLeod via Gcc-patches wrote:
>>> When a statement is first processed, any SSA_NAMEs that are dependencies
>>> are cached for quick future access.
>>>
>>> if we ;later rewrite the statement (say propagate a constant into it),
>>> its possible the ssa-name in this cache is no longer active.   Normally
>>> this is not a problem, but the changed to may_recompute_p forgot to take
>>> that into account, and was checking a dependency from the cache that was
>>> in the SSA_NAME_FREE_LIST. It thus had no SSA_NAME_DEF_STMT when we were
>>> expecting one.
>>>
>>> This patch simply rejects dependencies from consideration if they are in
>>> the free list.
>>>
>>> Bootstrapping on x86_64-pc-linux-gnu  and presuming no regressio0ns, OK
>>> for trunk?
>> eek.  So you've got a released name in the cache?  What happens if the
>> name gets released, then re-used?  Aren't you going to get bogus results
>> in that case?

Its not a real cache..  its merely a statement shortcut in dependency 
analysis to avoid re-parsing statements every time we look at them for 
dependency analysis

It is not suppose to be used for anything other than dependency 
checking.   ie, if an SSA_NAME changes, we can check if it matches 
either of the 2 "cached" names on this DEF, and if so, we know this name 
is stale.  we are never actually suppose to use the dependency cached 
values to drive anything, merely respond to the question if either 
matches a given name.   So it doesnt matter if the name here has been freed


> We never re-use SSA names from within the pass releasing it.  But if
> the ranger cache
> persists across passes this could be a problem.  See


This particular valueswould never persist beyond a current pass.. its 
just the dependency chains and they would get rebuilt every time because 
the IL has changed.


> flush_ssaname_freelist which
> for example resets the SCEV hash table which otherwise would have the
> same issue.
>
> IIRC ranger never outlives a pass so the patch should be OK.
>
> _But_ I wonder how ranger gets at the tree SSA name in the first place - usually
> caches are indexed by SSA_NAME_VERSION (because that's cheaper and


Its stored when we process a statement the first time when building 
dependency chains.  All comparisons down the road for 
staleness/dependency chain existence are against a pointer.. but we 
could simple change it to be an "unsigned int",  we'd then just have to 
compare again SSA_NAME_VERSION(name) instead..


> better than a pointer to the tree) and ssa_name (ver) will return NULL
> for released
> SSA names.  So range_def_chain::rdc could be just
>
>    struct rdc {
>     int ssa1;           // First direct dependency
>     int ssa2;           // Second direct dependency
>     bitmap bm;           // All dependencies
>     bitmap m_import;
>    };
>
> and ::depend1 return ssa_name (m_def_chain[v].ssa1) and everything woul
if the ssa-name is no longer in existence, does ssa_name (x) it return 
NULL?
> work automatically (and save 8 bytes of storage).
>
> Richard.

>> jeff

On Mon, Apr 24, 2023 at 3:51 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
>
> On 4/11/23 05:21, Richard Biener via Gcc-patches wrote:
> > On Wed, Apr 5, 2023 at 11:53 PM Jeff Law via Gcc-patches
> > <gcc-patches@gcc.gnu.org> wrote:
> >>
> >>
> >> On 4/5/23 14:10, Andrew MacLeod via Gcc-patches wrote:
> >>> When a statement is first processed, any SSA_NAMEs that are dependencies
> >>> are cached for quick future access.
> >>>
> >>> if we ;later rewrite the statement (say propagate a constant into it),
> >>> its possible the ssa-name in this cache is no longer active.   Normally
> >>> this is not a problem, but the changed to may_recompute_p forgot to take
> >>> that into account, and was checking a dependency from the cache that was
> >>> in the SSA_NAME_FREE_LIST. It thus had no SSA_NAME_DEF_STMT when we were
> >>> expecting one.
> >>>
> >>> This patch simply rejects dependencies from consideration if they are in
> >>> the free list.
> >>>
> >>> Bootstrapping on x86_64-pc-linux-gnu  and presuming no regressio0ns, OK
> >>> for trunk?
> >> eek.  So you've got a released name in the cache?  What happens if the
> >> name gets released, then re-used?  Aren't you going to get bogus results
> >> in that case?
>
> Its not a real cache..  its merely a statement shortcut in dependency
> analysis to avoid re-parsing statements every time we look at them for
> dependency analysis
>
> It is not suppose to be used for anything other than dependency
> checking.   ie, if an SSA_NAME changes, we can check if it matches
> either of the 2 "cached" names on this DEF, and if so, we know this name
> is stale.  we are never actually suppose to use the dependency cached
> values to drive anything, merely respond to the question if either
> matches a given name.   So it doesnt matter if the name here has been freed
>
>
> > We never re-use SSA names from within the pass releasing it.  But if
> > the ranger cache
> > persists across passes this could be a problem.  See
>
>
> This particular valueswould never persist beyond a current pass.. its
> just the dependency chains and they would get rebuilt every time because
> the IL has changed.
>
>
> > flush_ssaname_freelist which
> > for example resets the SCEV hash table which otherwise would have the
> > same issue.
> >
> > IIRC ranger never outlives a pass so the patch should be OK.
> >
> > _But_ I wonder how ranger gets at the tree SSA name in the first place - usually
> > caches are indexed by SSA_NAME_VERSION (because that's cheaper and
>
>
> Its stored when we process a statement the first time when building
> dependency chains.  All comparisons down the road for
> staleness/dependency chain existence are against a pointer.. but we
> could simple change it to be an "unsigned int",  we'd then just have to
> compare again SSA_NAME_VERSION(name) instead..
>
>
> > better than a pointer to the tree) and ssa_name (ver) will return NULL
> > for released
> > SSA names.  So range_def_chain::rdc could be just
> >
> >    struct rdc {
> >     int ssa1;           // First direct dependency
> >     int ssa2;           // Second direct dependency
> >     bitmap bm;           // All dependencies
> >     bitmap m_import;
> >    };
> >
> > and ::depend1 return ssa_name (m_def_chain[v].ssa1) and everything woul
> if the ssa-name is no longer in existence, does ssa_name (x) it return
> NULL?

Yes.

> > work automatically (and save 8 bytes of storage).
> >
> > Richard.
>
> >> jeff
>

On 4/24/23 07:51, Andrew MacLeod wrote:

> 
> Its not a real cache..  its merely a statement shortcut in dependency 
> analysis to avoid re-parsing statements every time we look at them for 
> dependency analysis
> 
> It is not suppose to be used for anything other than dependency 
> checking.   ie, if an SSA_NAME changes, we can check if it matches 
> either of the 2 "cached" names on this DEF, and if so, we know this name 
> is stale.  we are never actually suppose to use the dependency cached 
> values to drive anything, merely respond to the question if either 
> matches a given name.   So it doesnt matter if the name here has been freed
OK.  I'll take your word for it.  Note that a free'd SSA_NAME may have 
an empty TREE_TYPE or an unexpected TREE_CHAIN field IIRC.  So you have 
to be a bit careful if you're going to allow them.

> 
> 
>> We never re-use SSA names from within the pass releasing it.  But if
>> the ranger cache
>> persists across passes this could be a problem.  See
> 
> 
> This particular valueswould never persist beyond a current pass.. its 
> just the dependency chains and they would get rebuilt every time because 
> the IL has changed.
Good.  THat would limit the concerns significantly.  I don't think we 
recycle names within a pass anymore (we used to within DOM due to the 
way threading worked eons ago, but we no longer take things out of SSA 
form to handle the CFG/SSA graph updates.  One could even argue we don't 
need to maintain the freelist and recycle names anymore.

Jeff