[WIP] 'walk_gimple_seq' backward

Message ID 87blbi1xk8.fsf@dem-tschwing-1.ger.mentorg.com
State New
Headers show
Series
  • [WIP] 'walk_gimple_seq' backward
Related show

Commit Message

Thomas Schwinge March 16, 2021, 11:35 p.m.
Hi!

On 2021-03-17T00:24:55+0100, I wrote:
> Now, walking each function backwards (!), [...]


> I've now got a simple 'callback_op', which for '!is_lhs' looks at

> 'get_base_address ([op])', and if that 'var' is contained in the set of

> current candidates (initialized per containg 'bind's, which we enter

> first, even if walking a 'gimple_seq' backwards), removes that 'var' as a

> candidate for such optimization.  (Plus some "details", of couse.)  This

> seems to work fine, as far as I can tell.  :-)


Is something like the attached "[WIP] 'walk_gimple_seq' backward" OK
conceptually?  (For next development stage 1 and with all the TODOs
resolved, of course.)

The 'backward' flag cannot simply be a argument to 'walk_gimple_seq'
etc.: it needs to also be passed to 'walk_gimple_seq_mod' calls triggered
from inside 'walk_gimple_stmt'.  Hence, I've put it into the state
'struct walk_stmt_info'.


Grüße
 Thomas


-----------------
Mentor Graphics (Deutschland) GmbH, Arnulfstrasse 201, 80634 München Registergericht München HRB 106955, Geschäftsführer: Thomas Heurung, Frank Thürauf

Comments

Martin Sebor via Gcc-patches March 17, 2021, 7:54 a.m. | #1
On Wed, Mar 17, 2021 at 12:35 AM Thomas Schwinge
<thomas@codesourcery.com> wrote:
>

> Hi!

>

> On 2021-03-17T00:24:55+0100, I wrote:

> > Now, walking each function backwards (!), [...]

>

> > I've now got a simple 'callback_op', which for '!is_lhs' looks at

> > 'get_base_address ([op])', and if that 'var' is contained in the set of

> > current candidates (initialized per containg 'bind's, which we enter

> > first, even if walking a 'gimple_seq' backwards), removes that 'var' as a

> > candidate for such optimization.  (Plus some "details", of couse.)  This

> > seems to work fine, as far as I can tell.  :-)

>

> Is something like the attached "[WIP] 'walk_gimple_seq' backward" OK

> conceptually?  (For next development stage 1 and with all the TODOs

> resolved, of course.)

>

> The 'backward' flag cannot simply be a argument to 'walk_gimple_seq'

> etc.: it needs to also be passed to 'walk_gimple_seq_mod' calls triggered

> from inside 'walk_gimple_stmt'.  Hence, I've put it into the state

> 'struct walk_stmt_info'.


Can't you simply walk the sequence backward youself and call
walk_gimple_stmt on each stmt instead?

That said,

       if (!wi->removed_stmt)
-       gsi_next (&gsi);
+       {
+         if (forward)
+           gsi_next (&gsi);
+         else //TODO Correct?
+           gsi_prev (&gsi);
+         //TODO This could do with some unit testing, to make sure
all the corner cases (removing first/last, for example) work
correctly.
+       }

if wi->removed_stmt maps to gsi_remove being called then the backwards
code is incorrect since gsi_remove advances the iterator in the wrong direction.
So you always need gsi_prev () here.

Otherwise sure.

Richard.

>

> Grüße

>  Thomas

>

>

> -----------------

> Mentor Graphics (Deutschland) GmbH, Arnulfstrasse 201, 80634 München Registergericht München HRB 106955, Geschäftsführer: Thomas Heurung, Frank Thürauf
Thomas Schwinge March 18, 2021, 12:41 p.m. | #2
Hi!

On 2021-03-17T08:54:15+0100, Richard Biener <richard.guenther@gmail.com> wrote:
> On Wed, Mar 17, 2021 at 12:35 AM Thomas Schwinge

> <thomas@codesourcery.com> wrote:

>> On 2021-03-17T00:24:55+0100, I wrote:

>> > Now, walking each function backwards (!), [...]

>>

>> > I've now got a simple 'callback_op', which for '!is_lhs' looks at

>> > 'get_base_address ([op])', and if that 'var' is contained in the set of

>> > current candidates (initialized per containg 'bind's, which we enter

>> > first, even if walking a 'gimple_seq' backwards), removes that 'var' as a

>> > candidate for such optimization.  (Plus some "details", of couse.)  This

>> > seems to work fine, as far as I can tell.  :-)

>>

>> Is something like the attached "[WIP] 'walk_gimple_seq' backward" OK

>> conceptually?  (For next development stage 1 and with all the TODOs

>> resolved, of course.)

>>

>> The 'backward' flag cannot simply be a argument to 'walk_gimple_seq'

>> etc.: it needs to also be passed to 'walk_gimple_seq_mod' calls triggered

>> from inside 'walk_gimple_stmt'.  Hence, I've put it into the state

>> 'struct walk_stmt_info'.

>

> Can't you simply walk the sequence backward youself and call

> walk_gimple_stmt on each stmt instead?


That's what I'd intended to convey with the paragraph above -- I can't do
what you suggested: 'walk_gimple_stmt' will recursively call
'walk_gimple_seq_mod' ("If STMT can have statements inside
(e.g. GIMPLE_BIND), walk them.") -- and I need all these to be walked
backwards, too.  (..., and don't want to re-produce that whole
'walk_gimple_stmt' logic -- but could factor that logic out of
'walk_gimple_stmt', if that's cleaner than the 'backward' flag?)


> That said,

>

>        if (!wi->removed_stmt)

> -       gsi_next (&gsi);

> +       {

> +         if (forward)

> +           gsi_next (&gsi);

> +         else //TODO Correct?

> +           gsi_prev (&gsi);

> +         //TODO This could do with some unit testing, to make sure

> all the corner cases (removing first/last, for example) work

> correctly.

> +       }

>

> if wi->removed_stmt maps to gsi_remove being called then the backwards

> code is incorrect since gsi_remove advances the iterator in the wrong direction.

> So you always need gsi_prev () here.


Thanks, we shall look into that.


> Otherwise sure.


OK, we shall prepare something for next development stage 1.


Grüße
 Thomas
-----------------
Mentor Graphics (Deutschland) GmbH, Arnulfstrasse 201, 80634 München Registergericht München HRB 106955, Geschäftsführer: Thomas Heurung, Frank Thürauf

Patch

From 48036d65cea6bb47c7d4eca3b4fea77e058f29e3 Mon Sep 17 00:00:00 2001
From: Thomas Schwinge <thomas@codesourcery.com>
Date: Mon, 15 Mar 2021 17:31:00 +0100
Subject: [PATCH] [WIP] 'walk_gimple_seq' backward

This seems to work -- for the one case where I'm using it...
---
 gcc/doc/gimple.texi |  2 ++
 gcc/gimple-walk.c   | 15 ++++++++++++---
 gcc/gimple-walk.h   |  4 ++++
 3 files changed, 18 insertions(+), 3 deletions(-)

diff --git a/gcc/doc/gimple.texi b/gcc/doc/gimple.texi
index 5e0fc2e0dc5..51fe0f2d715 100644
--- a/gcc/doc/gimple.texi
+++ b/gcc/doc/gimple.texi
@@ -2778,4 +2778,6 @@  calling @code{walk_gimple_stmt} on each one.  @code{WI} is as in
 @code{walk_gimple_stmt}.  If @code{walk_gimple_stmt} returns non-@code{NULL}, the walk
 is stopped and the value returned.  Otherwise, all the statements
 are walked and @code{NULL_TREE} returned.
+
+TODO update for forward vs. backward.
 @end deftypefn
diff --git a/gcc/gimple-walk.c b/gcc/gimple-walk.c
index 9a761f32578..dfc2f0b4dbc 100644
--- a/gcc/gimple-walk.c
+++ b/gcc/gimple-walk.c
@@ -32,6 +32,8 @@  along with GCC; see the file COPYING3.  If not see
 /* Walk all the statements in the sequence *PSEQ calling walk_gimple_stmt
    on each one.  WI is as in walk_gimple_stmt.
 
+   TODO update for forward vs. backward.
+
    If walk_gimple_stmt returns non-NULL, the walk is stopped, and the
    value is stored in WI->CALLBACK_RESULT.  Also, the statement that
    produced the value is returned if this statement has not been
@@ -44,9 +46,10 @@  gimple *
 walk_gimple_seq_mod (gimple_seq *pseq, walk_stmt_fn callback_stmt,
 		     walk_tree_fn callback_op, struct walk_stmt_info *wi)
 {
-  gimple_stmt_iterator gsi;
+  bool forward = !(wi && wi->backward);
 
-  for (gsi = gsi_start (*pseq); !gsi_end_p (gsi); )
+  gimple_stmt_iterator gsi = forward ? gsi_start (*pseq) : gsi_last (*pseq);
+  for (; !gsi_end_p (gsi); )
     {
       tree ret = walk_gimple_stmt (&gsi, callback_stmt, callback_op, wi);
       if (ret)
@@ -60,7 +63,13 @@  walk_gimple_seq_mod (gimple_seq *pseq, walk_stmt_fn callback_stmt,
 	}
 
       if (!wi->removed_stmt)
-	gsi_next (&gsi);
+	{
+	  if (forward)
+	    gsi_next (&gsi);
+	  else //TODO Correct?
+	    gsi_prev (&gsi);
+	  //TODO This could do with some unit testing, to make sure all the corner cases (removing first/last, for example) work correctly.
+	}
     }
 
   if (wi)
diff --git a/gcc/gimple-walk.h b/gcc/gimple-walk.h
index bdc7351f190..9590c63ba18 100644
--- a/gcc/gimple-walk.h
+++ b/gcc/gimple-walk.h
@@ -71,6 +71,10 @@  struct walk_stmt_info
 
   /* True if we've removed the statement that was processed.  */
   BOOL_BITFIELD removed_stmt : 1;
+
+  /*TODO */
+  //TODO Only applicable for 'walk_gimple_seq'.
+  BOOL_BITFIELD backward : 1;
 };
 
 /* Callback for walk_gimple_stmt.  Called for every statement found
-- 
2.17.1