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

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

[Andrew MacLeod]

[-- Attachment #1: Type: text/plain, Size: 679 bytes --]

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

[-- Attachment #2: 417.diff --]
[-- Type: text/x-patch, Size: 1919 bytes --]

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.

diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index 5f4313b27dd..6e2f9533038 100644
--- 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.
diff --git a/gcc/testsuite/gcc.dg/pr109417.c b/gcc/testsuite/gcc.dg/pr109417.c
new file mode 100644
index 00000000000..15711dbbafe
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr109417.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-options "-O3" } */
+
+int printf(const char *, ...);
+int c, d, *e, f[1][2], g;
+int main() {
+  int h = 0, *a = &h, **b[1] = {&a};
+  while (e)
+    while (g) {
+    L:
+      for (h = 0; h < 2; h++) {
+        while (d)
+          for (*e = 0; *e < 1;)
+            printf("0");
+        while (c)
+          ;
+        f[g][h] = 0;
+      }
+    }
+  if (h)
+    goto L;
+  return 0;
+}
+

Re: [PATCH] PR tree-optimization/109417 - Check if dependency is valid before using in may_recompute_p.

[Jeff Law]

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

Re: [PATCH] PR tree-optimization/109417 - Check if dependency is valid before using in may_recompute_p.

[Richard Biener]

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

Re: [PATCH] PR tree-optimization/109417 - Check if dependency is valid before using in may_recompute_p.

[Andrew MacLeod]

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

Re: [PATCH] PR tree-optimization/109417 - Check if dependency is valid before using in may_recompute_p.

[Richard Biener]

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
>

Re: [PATCH] PR tree-optimization/109417 - Check if dependency is valid before using in may_recompute_p.

[Jeff Law]

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

[COMMITTED 1/5] PR tree-optimization/109417 - Don't save ssa-name pointer in dependency cache.

[Andrew MacLeod]

[-- Attachment #1: Type: text/plain, Size: 1803 bytes --]


On 4/25/23 22:34, Jeff Law wrote:
>
>
> 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
>
well, no worries.  taken care of thusly for the future. Its a hair 
slower, but nothing outrageous

Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed.

Andrew





[-- Attachment #2: 0001-Don-t-save-ssa-name-pointer-in-dependency-cache.patch --]
[-- Type: text/x-patch, Size: 3805 bytes --]

From a530eb642032da7ad4d30de51131421631055f72 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Tue, 25 Apr 2023 15:33:52 -0400
Subject: [PATCH 1/5] Don't save ssa-name pointer in dependency cache.

If the direct dependence fields point directly to an ssa-name,
its possible that an optimization frees an ssa-name, and the value
pointed to may now be in the free list.   Simply maintain the ssa
version number instead.

	PR tree-optimization/109417
	* gimple-range-gori.cc (range_def_chain::register_dependency):
	Save the ssa version number, not the pointer.
	(gori_compute::may_recompute_p): No need to check if a dependency
	is in the free list.
	* gimple-range-gori.h (class range_def_chain): Change ssa1 and ssa2
	fields to be unsigned int instead of trees.
	(ange_def_chain::depend1): Adjust.
	(ange_def_chain::depend2): Adjust.
	* gimple-range.h: Include "ssa.h" to inline ssa_name().
---
 gcc/gimple-range-gori.cc |  8 ++++----
 gcc/gimple-range-gori.h  | 14 ++++++++++----
 gcc/gimple-range.h       |  1 +
 3 files changed, 15 insertions(+), 8 deletions(-)

diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index d77e1f51ac2..5bba77c7b7b 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -182,9 +182,9 @@ range_def_chain::register_dependency (tree name, tree dep, basic_block bb)
 
   // Set the direct dependency cache entries.
   if (!src.ssa1)
-    src.ssa1 = dep;
-  else if (!src.ssa2 && src.ssa1 != dep)
-    src.ssa2 = dep;
+    src.ssa1 = SSA_NAME_VERSION (dep);
+  else if (!src.ssa2 && src.ssa1 != SSA_NAME_VERSION (dep))
+    src.ssa2 = SSA_NAME_VERSION (dep);
 
   // Don't calculate imports or export/dep chains if BB is not provided.
   // This is usually the case for when the temporal cache wants the direct
@@ -1316,7 +1316,7 @@ gori_compute::may_recompute_p (tree name, basic_block bb, int depth)
   // If the first dependency is not set, there is no recomputation.
   // 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))
+  if (!dep1)
     return false;
 
   // Don't recalculate PHIs or statements with side_effects.
diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h
index 3ea4b45595b..526edc24b53 100644
--- a/gcc/gimple-range-gori.h
+++ b/gcc/gimple-range-gori.h
@@ -46,8 +46,8 @@ protected:
   bitmap_obstack m_bitmaps;
 private:
   struct rdc {
-   tree ssa1;		// First direct dependency
-   tree ssa2;		// Second direct dependency
+   unsigned int ssa1;		// First direct dependency
+   unsigned int ssa2;		// Second direct dependency
    bitmap bm;		// All dependencies
    bitmap m_import;
   };
@@ -66,7 +66,10 @@ range_def_chain::depend1 (tree name) const
   unsigned v = SSA_NAME_VERSION (name);
   if (v >= m_def_chain.length ())
     return NULL_TREE;
-  return m_def_chain[v].ssa1;
+  unsigned v1 = m_def_chain[v].ssa1;
+  if (!v1)
+    return NULL_TREE;
+  return ssa_name (v1);
 }
 
 // Return the second direct dependency for NAME, if there is one.
@@ -77,7 +80,10 @@ range_def_chain::depend2 (tree name) const
   unsigned v = SSA_NAME_VERSION (name);
   if (v >= m_def_chain.length ())
     return NULL_TREE;
-  return m_def_chain[v].ssa2;
+  unsigned v2 = m_def_chain[v].ssa2;
+  if (!v2)
+    return NULL_TREE;
+  return ssa_name (v2);
 }
 
 // GORI_MAP is used to accumulate what SSA names in a block can
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index 7ed4d3870b8..b8ddca59d2d 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -22,6 +22,7 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_GIMPLE_RANGE_H
 #define GCC_GIMPLE_RANGE_H
 
+#include "ssa.h"
 #include "range.h"
 #include "value-query.h"
 #include "gimple-range-op.h"
-- 
2.39.2

Re: [PATCH] PR tree-optimization/109417 - Check if dependency is valid before using in may_recompute_p.

[Jakub Jelinek]

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