public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* Fix a tcb crash and a potential bug on mainline
@ 2004-10-18 21:09 Steven Bosscher
  2004-10-18 22:06 ` Andrew MacLeod
                   ` (2 more replies)
  0 siblings, 3 replies; 28+ messages in thread
From: Steven Bosscher @ 2004-10-18 21:09 UTC (permalink / raw)
  To: gcc-patches; +Cc: dnovillo, amacleod

Hi,


So here is an interesting tree CFG cleanup bug seen on the t-c-branch,
but it may well be that it also exists on mainline (haven't tried it).

Consider this function,

extern void abort (void) __attribute__ ((__noreturn__));
extern void foo (const char *s);

int
bar (const char **mangled)
{
  const char *c;
  int type_quals;

  switch (**mangled)
    {
    case 'C':
      type_quals = 1;
      break;
    case 'u':
      type_quals = 4;
      break;
    default:
      abort ();
    }

  switch (type_quals)
    {
    case 6:
      c = "volatile __restrict";
      break;
    case 4:
      c = "const volatile __restrict";
      break;
    default:
      abort ();
    }
  if (c != ((void *)0))
    foo (c);
}

After some constant propagating and jump threading, we eventually find
out that only the path with "case 4" matters and we end up with the two
following basic blocks:

;; basic block 2, loop depth 0, count 0
;; prev block 1, next block 3
;; pred:       0 [33.3%]  (exec)
;; succ:       3 [33.3%]  4 [33.3%]  7 [33.3%]  (exec)
# type_quals_8 = PHI <4(0)>;
<L3>:;
switch (4)
  {
    case 4: goto <L11>;
    case 6: goto <L7>;
    default : goto <L6>;
  }

;; basic block 4, loop depth 0, count 0
;; prev block 3, next block 5
;; pred:       2 [33.3%]
;; succ:       6 [10.0%]  (false) 5 [90.0%]  (true)
# c_13 = PHI <&"volatile __restrict"[0](2)>;
<L7>:;
if (c_13 != 0B) goto <L8>; else goto <L9>;

Then we try to do cleanup_tree_cfg() which calls cleanup_control_flow()
which iterates over all basic blocks with FOR_EACH_BB.
When we find that we'll always go to <L11> from block 2, we replace the
switch with an unconditional jump and block 4 becomes unreachable. We
remove the edge from block 2 to block 4, and we remove the matching PHI
arguments with remove_phi_arg_num().

Now it gets interesting.  remove_phi_arg_num() removes the PHI defining
c_13, and then releases the PHI_RESULT, so c_13 ends up on the SSA free
list, even though it is still used in the COND_EXPR in block 4.

Later on cleanup_control_flow() tries to do its thing on basic block 4.
It tries to fold "(c_13 != 0B)", but c_13 is on the free list, so it
does not have a TREE_TYPE, so fold crashes.

I think the root cause of this bug is that c_13 is put on the free list,
and I think its SSA_NAME_DEF_STMT should be set to the empty statement,
because remove_phi_arg_num() cannot know if there are any immediate
uses of it still left.  I don't know if making that change could have
some unforseen effects, so I decided to re-hide the the bug by just not
looking at unreachable blocks in cleanup_control_flow().  I've tried to
convince myself that this can not happen in other situations, but I'm
not sure.  This may be something Andrew may want to look into as part
of his immediate uses work??

This fix is completely untested at the moment, but it's quite obvious
and it fixes the ICE I was seeing.  Still, I am a bit surprised that we
have not been in trouble over this bug before - perhaps we should still
fix the remove_phi_arg_num() issue instead of papering it over this way?

Gr.
Steven


Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.55.2.5
diff -c -3 -p -r2.55.2.5 tree-cfg.c
*** tree-cfg.c  13 Oct 2004 16:04:10 -0000      2.55.2.5
--- tree-cfg.c  18 Oct 2004 21:00:37 -0000
*************** cleanup_control_flow (void)
*** 1853,1858 ****
--- 1852,1863 ----
  
    FOR_EACH_BB (bb)
      {
+       /* We can have unreachable blocks here if we run before
+        delete_unreachable_blocks or if a block visited before
+        this one had an edge to bb that we removed.  */
+       if (EDGE_COUNT (bb->preds) == 0)
+       continue;
+
        bsi = bsi_last (bb);
  
        if (bsi_end_p (bsi))

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-18 21:09 Fix a tcb crash and a potential bug on mainline Steven Bosscher
@ 2004-10-18 22:06 ` Andrew MacLeod
  2004-10-18 22:18 ` Andrew Pinski
  2004-10-19 20:58 ` Jeffrey A Law
  2 siblings, 0 replies; 28+ messages in thread
From: Andrew MacLeod @ 2004-10-18 22:06 UTC (permalink / raw)
  To: Steven Bosscher; +Cc: gcc-patches, Diego Novillo

On Mon, 2004-10-18 at 17:03, Steven Bosscher wrote:
> Hi,

> I think the root cause of this bug is that c_13 is put on the free list,
> and I think its SSA_NAME_DEF_STMT should be set to the empty statement,
> because remove_phi_arg_num() cannot know if there are any immediate
> uses of it still left.  I don't know if making that change could have
> some unforseen effects, so I decided to re-hide the the bug by just not
> looking at unreachable blocks in cleanup_control_flow().  I've tried to
> convince myself that this can not happen in other situations, but I'm
> not sure.  This may be something Andrew may want to look into as part
> of his immediate uses work??

well, someone can look into it, perhaps me onm my branch  :-). It will
certainly be trivial to tell if there are any uses of c_13, and simply
change all of them to the value in the arguement for the phi, or turn
the PHI into a copy.

the other thing you could do is simply emit the PHI as a copy at the
start of the block instead of deleting it, and DCE will remove it if
there arent any uses.  I actually thought this is what we did when we
had a PHI left with only one incoming edge. We use to do that didnt we?
Its defiend as a copy, so how can anyone delete it without knowing about
its uses?

either that, or I read this note too quickly :-)

Andrew



^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-18 21:09 Fix a tcb crash and a potential bug on mainline Steven Bosscher
  2004-10-18 22:06 ` Andrew MacLeod
@ 2004-10-18 22:18 ` Andrew Pinski
  2004-10-19 20:58 ` Jeffrey A Law
  2 siblings, 0 replies; 28+ messages in thread
From: Andrew Pinski @ 2004-10-18 22:18 UTC (permalink / raw)
  To: Steven Bosscher; +Cc: dnovillo, gcc-patches, amacleod


On Oct 18, 2004, at 5:03 PM, Steven Bosscher wrote:

> Hi,
>
>
> So here is an interesting tree CFG cleanup bug seen on the t-c-branch,
> but it may well be that it also exists on mainline (haven't tried it).

It does show up on the mainline via PR 17757 and the fortran test
emptyif.f90 and I tested this patch and it fixes the testcase in there
also.

Thanks,
Andrew Pinski

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-18 21:09 Fix a tcb crash and a potential bug on mainline Steven Bosscher
  2004-10-18 22:06 ` Andrew MacLeod
  2004-10-18 22:18 ` Andrew Pinski
@ 2004-10-19 20:58 ` Jeffrey A Law
  2004-10-19 21:29   ` Steven Bosscher
  2 siblings, 1 reply; 28+ messages in thread
From: Jeffrey A Law @ 2004-10-19 20:58 UTC (permalink / raw)
  To: Steven Bosscher; +Cc: gcc-patches, dnovillo, amacleod

On Mon, 2004-10-18 at 15:03, Steven Bosscher wrote:

> Later on cleanup_control_flow() tries to do its thing on basic block 4.
> It tries to fold "(c_13 != 0B)", but c_13 is on the free list, so it
> does not have a TREE_TYPE, so fold crashes.
Hmm.  I wonder if this is the same bug Andrew Pinski was trying to
fix by not clearing TREE_TYPE.  Your description matches a lot of
the tidbits Andrew mentioned.


> 
> I think the root cause of this bug is that c_13 is put on the free list,
> and I think its SSA_NAME_DEF_STMT should be set to the empty statement,
> because remove_phi_arg_num() cannot know if there are any immediate
> uses of it still left. 
???  Putting c_13 on the free list is the right thing to do.  I'm not
sure why you think setting SSA_NAME_DEF_STMT to NULL is particularly
interesting though.  Whether or not the name has any uses left in the
IL isn't something we use to determine whether or not to set
SSA_NAME_DEF_STMT to any particular value IIRC. 


>  I don't know if making that change could have
> some unforseen effects, so I decided to re-hide the the bug by just not
> looking at unreachable blocks in cleanup_control_flow().
I'm not sure this is sufficient to hide the bug well enough though.


>   I've tried to
> convince myself that this can not happen in other situations, but I'm
> not sure.
Well, any code that deletes edges from the CFG, then later looks at
statements without first calling delete_unreachable_blocks is
suspect.  But I'm not sure if we've even solved this problem
within the context of cleanup_tree_cfg.

Let's say we have a PHI in block A.  Assume the result is used in 
block B.  Assume block A will become unreachable.

While block B must also be unreachable (block B is dominated by
block A), we won't necessarily have removed all its incoming edges.

Thus when we process block B we can still end up touching a statement
which references a released SSA_NAME.  Ugh...

>   This may be something Andrew may want to look into as part
> of his immediate uses work??
It's something we've pondered and talked about a little.  Basically
with the immediate use work we would know where all the uses are
and we could probably arrange to delete those uses.

The trick is whether or not we can do that without introducing the
kinds of problems we had with delete_insn in the past which tried
to do similar stuff.

> 
> This fix is completely untested at the moment, but it's quite obvious
> and it fixes the ICE I was seeing.  Still, I am a bit surprised that we
> have not been in trouble over this bug before - perhaps we should still
> fix the remove_phi_arg_num() issue instead of papering it over this way?
I'm not sure what you mean by fix remove_phi_arg_num except to compute
the immediate uses of the result and delete those statements, which
in turn can cause other statements to get deleted.  Basically it turns
into immediate use based DCE.  Roughly the same thing we'd end up
doing if we tried to do integrated dead code removal using
immediate uses.

Alternately we could split up cleanup_control_expr_graph into two
phases.  The first identifies all the COND_EXPRs and SWITCH_EXPRs
which need updating, but does not do any edge removal.   Once we
have done our full IL scan, we go back to the nodes where we know
which outgoing edge will be taken and proceed to remove the 
COND_EXPR/SWITCH_EXPR and the untaken edges.

jeff

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-19 20:58 ` Jeffrey A Law
@ 2004-10-19 21:29   ` Steven Bosscher
  2004-10-19 22:08     ` Jeffrey A Law
  0 siblings, 1 reply; 28+ messages in thread
From: Steven Bosscher @ 2004-10-19 21:29 UTC (permalink / raw)
  To: law; +Cc: gcc-patches, dnovillo, amacleod

On Tuesday 19 October 2004 22:48, Jeffrey A Law wrote:
> On Mon, 2004-10-18 at 15:03, Steven Bosscher wrote:
> > Later on cleanup_control_flow() tries to do its thing on basic block 4.
> > It tries to fold "(c_13 != 0B)", but c_13 is on the free list, so it
> > does not have a TREE_TYPE, so fold crashes.
>
> Hmm.  I wonder if this is the same bug Andrew Pinski was trying to
> fix by not clearing TREE_TYPE.  Your description matches a lot of
> the tidbits Andrew mentioned.

Yes, it is.


> > I think the root cause of this bug is that c_13 is put on the free list,
> > and I think its SSA_NAME_DEF_STMT should be set to the empty statement,
> > because remove_phi_arg_num() cannot know if there are any immediate
> > uses of it still left.
>
> ???  Putting c_13 on the free list is the right thing to do.

I believe it is not.  It is *wrong* to put an SSA_NAME on the free list
unless you're absolutely positively sure that the thing is not used
anywhere in the code.

The free list is for SSA names that are available for recycling.  An
SSA_NAME that still appears in the code, even if it is in unreachable
code, is *not* elligible for recycling until that unreachable code is
actually removed.

I really don't understand how you can think this is the right thing to
do, it's the most broken idea I've seen in a long time.


>  I'm not
> sure why you think setting SSA_NAME_DEF_STMT to NULL is particularly
> interesting though.  Whether or not the name has any uses left in the
> IL isn't something we use to determine whether or not to set
> SSA_NAME_DEF_STMT to any particular value IIRC.

Not usually.  But this case is special.  Normally we don't just throw
away a statement, we first update the code or we delete entire blocks
of code.  In this particular case we're only deleting a PHI node and
we don't know if the block we're deleting the PHI from is unreachable
(we could, but it's not the business of remove_phi_arg_num() to remove
unreachable blocks).  So conceptually the PHI_RESULT of the deleted
PHI becomes undefined.  But it is not dead until all its uses are also
removed.  We express "undefined-ness" by setting the SSA_NAME_DEF_STMT
to the empty statement.


> >  I don't know if making that change could have
> > some unforseen effects, so I decided to re-hide the the bug by just not
> > looking at unreachable blocks in cleanup_control_flow().
>
> I'm not sure this is sufficient to hide the bug well enough though.

Me neither.  But I am fairly sure that making the PHI_RESULT undefined,
instead of putting it on the free list, will not just hide but actually
*fix* it.

I would have posted a patch to do that if I had had more time and was
less unsure about unexpected effects of such a change.  I might still
give it a try.


> >   This may be something Andrew may want to look into as part
> > of his immediate uses work??
>
> It's something we've pondered and talked about a little.  Basically
> with the immediate use work we would know where all the uses are
> and we could probably arrange to delete those uses.

How would you delete those uses?  You don't know if those statements
are dead, so you really can't do that.

What I mean with this is that perhaps we should not put the SSA_NAME on
the free list if there still are immediate uses.  On Andrew's branch
that is very easy to do, if we decide to fix the bug this way.


> > This fix is completely untested at the moment, but it's quite obvious
> > and it fixes the ICE I was seeing.  Still, I am a bit surprised that we
> > have not been in trouble over this bug before - perhaps we should still
> > fix the remove_phi_arg_num() issue instead of papering it over this way?
>
> I'm not sure what you mean by fix remove_phi_arg_num

I mean to fix it by making it set the SSA_NAME_DEF_STMT of PHIs that
it is deleting to the empty statement...


> except to compute
> the immediate uses of the result and delete those statements, which
> in turn can cause other statements to get deleted.  Basically it turns
> into immediate use based DCE.  Roughly the same thing we'd end up
> doing if we tried to do integrated dead code removal using
> immediate uses.

...and this is what I don't mean and don't want.

(Not for the CFG cleanup anyway.  Perhaps doing immediate uses based DCE
is a good idea for the mythical "fast DCE".  LLVM used this algorithm
last time I looked.  I don't know which is faster in practice, classic
DCE like we have now, or immediate uses based DCE.  Something we can try
on Andrews branch.  </OT>)


> Alternately we could split up cleanup_control_expr_graph into two
> phases.  The first identifies all the COND_EXPRs and SWITCH_EXPRs
> which need updating, but does not do any edge removal.   Once we
> have done our full IL scan, we go back to the nodes where we know
> which outgoing edge will be taken and proceed to remove the
> COND_EXPR/SWITCH_EXPR and the untaken edges.

Talk about killing a bug with a sledge hammer :-)

Take a step back, and consider what is really happening:
Conceptually, after removing the PHI node, the PHI_RESULT c_13 simply
becomes an SSA_NAME without a defining statement.  The obviously correct
way to handle this is by treating it just like we treat any other SSA
name without defining statement: Setting SSA_NAME_DEF_STMT to the empty
statement.  The whole infrastructure already knows how to deal with such
SSA_NAMEs, so except a change in remove_phi_arg_num() it would probably 
not need any changes anywhere else.  At least that's what I hope, because
I'm going to try this approach now...

Gr.
Steven


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-19 21:29   ` Steven Bosscher
@ 2004-10-19 22:08     ` Jeffrey A Law
  2004-10-19 22:27       ` Daniel Berlin
  2004-10-19 22:36       ` Steven Bosscher
  0 siblings, 2 replies; 28+ messages in thread
From: Jeffrey A Law @ 2004-10-19 22:08 UTC (permalink / raw)
  To: Steven Bosscher; +Cc: gcc-patches, dnovillo, amacleod

On Tue, 2004-10-19 at 15:28, Steven Bosscher wrote:
> On Tuesday 19 October 2004 22:48, Jeffrey A Law wrote:
> > On Mon, 2004-10-18 at 15:03, Steven Bosscher wrote:
> > > Later on cleanup_control_flow() tries to do its thing on basic block 4.
> > > It tries to fold "(c_13 != 0B)", but c_13 is on the free list, so it
> > > does not have a TREE_TYPE, so fold crashes.
> >
> > Hmm.  I wonder if this is the same bug Andrew Pinski was trying to
> > fix by not clearing TREE_TYPE.  Your description matches a lot of
> > the tidbits Andrew mentioned.
> 
> Yes, it is.
> 
> 
> > > I think the root cause of this bug is that c_13 is put on the free list,
> > > and I think its SSA_NAME_DEF_STMT should be set to the empty statement,
> > > because remove_phi_arg_num() cannot know if there are any immediate
> > > uses of it still left.
> >
> > ???  Putting c_13 on the free list is the right thing to do.
> 
> I believe it is not.  It is *wrong* to put an SSA_NAME on the free list
> unless you're absolutely positively sure that the thing is not used
> anywhere in the code.
Have you read the code to manage the free list?  This is normal and
common precisely because we do not have immediate use information
to allow us to find and remove all references.

> >  I'm not
> > sure why you think setting SSA_NAME_DEF_STMT to NULL is particularly
> > interesting though.  Whether or not the name has any uses left in the
> > IL isn't something we use to determine whether or not to set
> > SSA_NAME_DEF_STMT to any particular value IIRC.
> 
> Not usually.  But this case is special.  Normally we don't just throw
> away a statement, we first update the code or we delete entire blocks
> of code.  In this particular case we're only deleting a PHI node and
> we don't know if the block we're deleting the PHI from is unreachable
> (we could, but it's not the business of remove_phi_arg_num() to remove
> unreachable blocks).  So conceptually the PHI_RESULT of the deleted
> PHI becomes undefined.  But it is not dead until all its uses are also
> removed.  We express "undefined-ness" by setting the SSA_NAME_DEF_STMT
> to the empty statement.
Err, if we remove the last argument to a PHI node then by definition
the block containing the PHI is unreachable as it has no incoming
edges.

There is no such thing as an "undefined" PHI node.


> 
> > >   This may be something Andrew may want to look into as part
> > > of his immediate uses work??
> >
> > It's something we've pondered and talked about a little.  Basically
> > with the immediate use work we would know where all the uses are
> > and we could probably arrange to delete those uses.
> 
> How would you delete those uses?  You don't know if those statements
> are dead, so you really can't do that.
If they are using the result of a deleted PHI or some other deleted
statement, then those statements must also be dead.  It's one of
the nice SSA properties.


> What I mean with this is that perhaps we should not put the SSA_NAME on
> the free list if there still are immediate uses.  On Andrew's branch
> that is very easy to do, if we decide to fix the bug this way.
No, you would delete all the immediate uses.

> I mean to fix it by making it set the SSA_NAME_DEF_STMT of PHIs that
> it is deleting to the empty statement...
No.  That is wrong.

Jeff

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-19 22:08     ` Jeffrey A Law
@ 2004-10-19 22:27       ` Daniel Berlin
  2004-10-19 22:35         ` Jeffrey A Law
  2004-10-19 22:36       ` Steven Bosscher
  1 sibling, 1 reply; 28+ messages in thread
From: Daniel Berlin @ 2004-10-19 22:27 UTC (permalink / raw)
  To: law; +Cc: dnovillo, gcc-patches, amacleod, Steven Bosscher

>
>>
>>>>   This may be something Andrew may want to look into as part
>>>> of his immediate uses work??
>>>
>>> It's something we've pondered and talked about a little.  Basically
>>> with the immediate use work we would know where all the uses are
>>> and we could probably arrange to delete those uses.
>>
>> How would you delete those uses?  You don't know if those statements
>> are dead, so you really can't do that.
> If they are using the result of a deleted PHI or some other deleted
> statement, then those statements must also be dead.  It's one of
> the nice SSA properties.
>

Only if your pass performs *all* insertions and updates to statements 
before performing *any* removals of statements.
I believe some passes don't do this right now.
Otherwise, in the intermediate step, we would think some statements are 
dead when they are only dead because we haven't fixed them up yet :)
--Dan

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-19 22:27       ` Daniel Berlin
@ 2004-10-19 22:35         ` Jeffrey A Law
  2004-10-19 23:08           ` Daniel Berlin
  0 siblings, 1 reply; 28+ messages in thread
From: Jeffrey A Law @ 2004-10-19 22:35 UTC (permalink / raw)
  To: Daniel Berlin; +Cc: dnovillo, gcc-patches, amacleod, Steven Bosscher

On Tue, 2004-10-19 at 16:23, Daniel Berlin wrote:

> Only if your pass performs *all* insertions and updates to statements 
> before performing *any* removals of statements.
True.  However, I believe that is the case for most of our optimizers
right now.

> I believe some passes don't do this right now.
PRE and jump threading being the obvious exceptions.

> Otherwise, in the intermediate step, we would think some statements are 
> dead when they are only dead because we haven't fixed them up yet :)
Right -- which is one of my big concerns with integrated dead
code elimination schemes.  This kind of problem bit us with
delete_insn as well.

jeff

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-19 22:08     ` Jeffrey A Law
  2004-10-19 22:27       ` Daniel Berlin
@ 2004-10-19 22:36       ` Steven Bosscher
  2004-10-19 22:41         ` Diego Novillo
  2004-10-19 23:16         ` Jeffrey A Law
  1 sibling, 2 replies; 28+ messages in thread
From: Steven Bosscher @ 2004-10-19 22:36 UTC (permalink / raw)
  To: law; +Cc: gcc-patches, dnovillo, amacleod

On Wednesday 20 October 2004 00:05, Jeffrey A Law wrote:
> > Not usually.  But this case is special.  Normally we don't just throw
> > away a statement, we first update the code or we delete entire blocks
> > of code.  In this particular case we're only deleting a PHI node and
> > we don't know if the block we're deleting the PHI from is unreachable
> > (we could, but it's not the business of remove_phi_arg_num() to remove
> > unreachable blocks).  So conceptually the PHI_RESULT of the deleted
> > PHI becomes undefined.  But it is not dead until all its uses are also
> > removed.  We express "undefined-ness" by setting the SSA_NAME_DEF_STMT
> > to the empty statement.
>
> Err, if we remove the last argument to a PHI node then by definition
> the block containing the PHI is unreachable as it has no incoming
> edges.
>
> There is no such thing as an "undefined" PHI node.

I didn't say we do.  I said we may have an undefined PHI result,
i.e. and SSA_NAME without a definition.

There is such a thing as an "undefined" SSA name.

But you're right, when the last PHI argument disappears, the block
for that PHI must be dead.  Only, what I was arguing for is that it
is not up to remove_phi_arg_num() to decide on that.  If we need to
do that for the SSA names free list, I think that is unfortunate.


> If they are using the result of a deleted PHI or some other deleted
> statement, then those statements must also be dead.  It's one of
> the nice SSA properties.

But you end up doing far more than just removing a PHI argument when
you start deleting the statements using the result of the deleted PHI.


> > What I mean with this is that perhaps we should not put the SSA_NAME on
> > the free list if there still are immediate uses.  On Andrew's branch
> > that is very easy to do, if we decide to fix the bug this way.
>
> No, you would delete all the immediate uses.

So you want to turn remove_phi_arg_num() into an ad-hoc DCE.  It would
work, no doubt.  But just removing a PHI argument does not need to be
so complicated.


> > I mean to fix it by making it set the SSA_NAME_DEF_STMT of PHIs that
> > it is deleting to the empty statement...
>
> No.  That is wrong.

I believe your approach is not right and mine is simpler, but, whatever.

In any case, the original patch is still useful in itself, and it
happens to fix the crash at least for now.  Updated version that I've
bootstrapped and tested on i686-suse-linux-gnu is below.
It fixes emptyif.f90.  Compile time is unchanged.  OK for mainline?

Gr.
Steven

	* tree-cfg.c (cleanup_control_flow): Don't try to cleanup
	statements in unreachable blocks.  Remove all outgoing edges
	of such blocks.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.83
diff -c -3 -p -r2.83 tree-cfg.c
*** tree-cfg.c	19 Oct 2004 15:38:25 -0000	2.83
--- tree-cfg.c	19 Oct 2004 19:10:28 -0000
*************** cleanup_control_flow (void)
*** 1864,1869 ****
--- 1864,1882 ----
  
    FOR_EACH_BB (bb)
      {
+       /* We can have unreachable blocks here if we run before
+ 	 delete_unreachable_blocks or if a block visited before
+ 	 this one had an edge to bb that we removed.
+ 
+ 	 Remove all outdoing edges to perhaps make BB's successors
+ 	 unreachable too.  Then move on to the next block.  */
+       if (EDGE_COUNT (bb->preds) == 0)
+ 	{
+ 	  while (EDGE_COUNT (bb->succs) > 0)
+ 	    ssa_remove_edge (EDGE_SUCC (bb, 0));
+ 	  continue;
+ 	}
+ 
        bsi = bsi_last (bb);
  
        if (bsi_end_p (bsi))

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-19 22:36       ` Steven Bosscher
@ 2004-10-19 22:41         ` Diego Novillo
  2004-10-19 23:16         ` Jeffrey A Law
  1 sibling, 0 replies; 28+ messages in thread
From: Diego Novillo @ 2004-10-19 22:41 UTC (permalink / raw)
  To: Steven Bosscher; +Cc: Jeff Law, gcc-patches, Andrew Macleod

On Tue, 2004-10-19 at 18:36, Steven Bosscher wrote:

> 	* tree-cfg.c (cleanup_control_flow): Don't try to cleanup
> 	statements in unreachable blocks.  Remove all outgoing edges
> 	of such blocks.
> 
This makes sense to me, but I'll defer to Jeff for final approval.  I
haven't followed this thread in too much detail.


> +       /* We can have unreachable blocks here if we run before
> + 	 delete_unreachable_blocks or if a block visited before
> + 	 this one had an edge to bb that we removed.
> + 
s/bb/BB/

> + 	 Remove all outdoing edges to perhaps make BB's successors
>
s/perhaps/attempt to/ ?


Diego.

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-19 22:35         ` Jeffrey A Law
@ 2004-10-19 23:08           ` Daniel Berlin
  2004-10-19 23:14             ` Daniel Berlin
  0 siblings, 1 reply; 28+ messages in thread
From: Daniel Berlin @ 2004-10-19 23:08 UTC (permalink / raw)
  To: law
  Cc: Andrew MacLeod, Diego Novillo, GCC Patches, Steven Bosscher,
	Kenneth Zadeck


On Oct 19, 2004, at 6:30 PM, Jeffrey A Law wrote:

> On Tue, 2004-10-19 at 16:23, Daniel Berlin wrote:
>
>> Only if your pass performs *all* insertions and updates to statements
>> before performing *any* removals of statements.
> True.  However, I believe that is the case for most of our optimizers
> right now.

Except for things that just want t

>
>> I believe some passes don't do this right now.
> PRE and jump threading being the obvious exceptions.
PRE actually does all insertions before it does any 
eliminations/replacements these days, instead of mixing them together 
like it used to.


>
>> Otherwise, in the intermediate step, we would think some statements 
>> are
>> dead when they are only dead because we haven't fixed them up yet :)
> Right -- which is one of my big concerns with integrated dead
> code elimination schemes.  This kind of problem bit us with
> delete_insn as well.

I would seriously suggest we not go down the route of integrating DCE 
into immediate use replacement, of course.
Among other things, it is incredibly surprising that removing a use 
would magically make other statements disappear, unless you had 
explicitly called some DCE pass.

>
> jeff
>

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-19 23:08           ` Daniel Berlin
@ 2004-10-19 23:14             ` Daniel Berlin
  2004-10-21  2:33               ` Jeffrey A Law
  0 siblings, 1 reply; 28+ messages in thread
From: Daniel Berlin @ 2004-10-19 23:14 UTC (permalink / raw)
  To: Daniel Berlin
  Cc: Andrew MacLeod, law, Diego Novillo, GCC Patches, Steven Bosscher,
	Kenneth Zadeck


On Oct 19, 2004, at 7:08 PM, Daniel Berlin wrote:

>
> On Oct 19, 2004, at 6:30 PM, Jeffrey A Law wrote:
>
>> On Tue, 2004-10-19 at 16:23, Daniel Berlin wrote:
>>
>>> Only if your pass performs *all* insertions and updates to statements
>>> before performing *any* removals of statements.
>> True.  However, I believe that is the case for most of our optimizers
>> right now.
>
> Except for things that just want t
Sigh.
Hit send too early by accident.

Except for things that just want to do replacements without worrying 
about what happens to the resulting statements.
Trying to keep our ir in a "minimal form" so to speak (where there are 
never dead statements) doesn't seem like the best idea, however.

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-19 22:36       ` Steven Bosscher
  2004-10-19 22:41         ` Diego Novillo
@ 2004-10-19 23:16         ` Jeffrey A Law
  2004-10-20 13:17           ` Andrew MacLeod
  1 sibling, 1 reply; 28+ messages in thread
From: Jeffrey A Law @ 2004-10-19 23:16 UTC (permalink / raw)
  To: Steven Bosscher; +Cc: gcc-patches, dnovillo, amacleod

On Tue, 2004-10-19 at 16:36, Steven Bosscher wrote:

> > Err, if we remove the last argument to a PHI node then by definition
> > the block containing the PHI is unreachable as it has no incoming
> > edges.
> >
> > There is no such thing as an "undefined" PHI node.
> 
> I didn't say we do.  I said we may have an undefined PHI result,
> i.e. and SSA_NAME without a definition.
OK.  And that is something that is, unfortunately, normal in our
implementation.  If I look at the SSA_NAME manager that's by far
its largest wart.


>  If we need to
> do that for the SSA names free list, I think that is unfortunate.
We do it for both the SSA_NAME and PHI_NODE manager as we want to
recycle both PHI_NODE and the SSA_NAME in its result.

> > If they are using the result of a deleted PHI or some other deleted
> > statement, then those statements must also be dead.  It's one of
> > the nice SSA properties.
> 
> But you end up doing far more than just removing a PHI argument when
> you start deleting the statements using the result of the deleted PHI.
Right.  So given the constraints you can:

  1. Not release SSA_NAMEs and PHI_NODEs.  That's bloody expensive,
     less so now than before because we don't churn things nearly
     as much in the jump threading code, but it's still expensive in
     terms of memory consumption.

  2. When we release an SSA_NAME and PHI_NODE go and find all uses
     of the SSA_NAME and release them too.  This is effectively an
     iterative DCE process.

  3. Allow releasing of SSA_NAMEs which are still referenced in the
     IL and force passes to work around the issues we're seeing now.

     3a. I think your most recent patch masks the problem well enough.
         However, I think mine is a better approach because it's
         more bullet-proof.    I'm going to ponder both a little
         more.

         Regardless of which we choose I think we need a comment
         indicating that we need the delete_unreachable_blocks
         phase to run immediately after cleanup_control_flow to
         avoid the introduction of similar problems in the future.

If you've got something more creative, then I'm all ears.


> > > What I mean with this is that perhaps we should not put the SSA_NAME on
> > > the free list if there still are immediate uses.  On Andrew's branch
> > > that is very easy to do, if we decide to fix the bug this way.
> >
> > No, you would delete all the immediate uses.
> 
> So you want to turn remove_phi_arg_num() into an ad-hoc DCE.  It would
> work, no doubt.  But just removing a PHI argument does not need to be
> so complicated.
See above.  


> I believe your approach is not right and mine is simpler, but, whatever.
I think mine is conceptually simpler as it identifies that we have
two distinct actions here.  The first is to identify what can be
optimized, the second is to actually optimize those sites.

Those two actions ought to be independent of each other, with the
exception of the first action providing a list of optimizable
locations to the second action.

Your approach continues to run both actions in parallel and thus has
to deal with "hidden" dependencies between the two actions.  Such
as the need to avoid looking at statements which reference an
SSA_NAME from a PHI_NODE which was deleted earlier.  You're actually
doing a poor man's unreachable code elimination -- you remove edges
from the CFG and ignore blocks which have become unreachable as a
result.


> In any case, the original patch is still useful in itself, and it
> happens to fix the crash at least for now.  Updated version that I've
> bootstrapped and tested on i686-suse-linux-gnu is below.
> It fixes emptyif.f90.  Compile time is unchanged.  OK for mainline?
Still pondering...

jeff


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-19 23:16         ` Jeffrey A Law
@ 2004-10-20 13:17           ` Andrew MacLeod
  2004-10-20 13:32             ` Steven Bosscher
  2004-10-22 19:10             ` Jeffrey A Law
  0 siblings, 2 replies; 28+ messages in thread
From: Andrew MacLeod @ 2004-10-20 13:17 UTC (permalink / raw)
  To: Jeff Law; +Cc: Steven Bosscher, gcc-patches, Diego Novillo

On Tue, 2004-10-19 at 19:13, Jeffrey A Law wrote:
> On Tue, 2004-10-19 at 16:36, Steven Bosscher wrote:
> 
> > > Err, if we remove the last argument to a PHI node then by definition
> > > the block containing the PHI is unreachable as it has no incoming
> > > edges.
> > >
> > > There is no such thing as an "undefined" PHI node.
> > 
> > I didn't say we do.  I said we may have an undefined PHI result,
> > i.e. and SSA_NAME without a definition.
> OK.  And that is something that is, unfortunately, normal in our
> implementation.  If I look at the SSA_NAME manager that's by far
> its largest wart.
> 

If I understand the problem properly, the fundamental problem here is
that a block becomes unreachable by removing all the incoming edges. PHI
arguments for those edges are removed as the edge is removed. When the
last edge is removed, the PHI node has no more arguments, and thus gets
deleted.  None of the code in the dead block is removed until later when
delete_unreachable_blocks is called. Meanwhile, we end up pawing through
one or more stmts in the dead block which contains uses of the PHI
result.

I have a couple of questions.

1 - Why does cleanup_control_flow() ever look at a stmts inside an
unreachable block? Its seems rather, umm, unnecessary, for starters. Why
not just call delete_unreachable_blocks() as the *first* thing in
cfg_cleanup(). It doesn't look like its an expensive call... 

2 - The issue may also exist outside cleanup_control_flow, so why does
remove_phi_arg_num have to remove the PHI node when is removes the last
argument. Why not allow the PHI node to exist with no arguments. It'll
get removed and free'd if the block remains unreachable. Maybe someone
will add another edge back in at some point during the optimization,
then there are PHI nodes ready to take the arguments.  I presume right
now we make sure we add new edges before deleting old ones when
redirecting things (to avoid deleting the PHI).  This might cause the
PHI node to be resized larger without really needing it. (ie, if you are
replacing two edges with one different one, and you add the one before
delete the other two, you've resized the PHI node to 3.)
 

> 
>   2. When we release an SSA_NAME and PHI_NODE go and find all uses
>      of the SSA_NAME and release them too.  This is effectively an
>      iterative DCE process.

I am not very fond of this one :-)  Especially since they are going to
be dealt with en-mass when you delete the block anyway.

Andrew

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-20 13:17           ` Andrew MacLeod
@ 2004-10-20 13:32             ` Steven Bosscher
  2004-10-20 13:47               ` Andrew MacLeod
  2004-10-22 19:15               ` Jeffrey A Law
  2004-10-22 19:10             ` Jeffrey A Law
  1 sibling, 2 replies; 28+ messages in thread
From: Steven Bosscher @ 2004-10-20 13:32 UTC (permalink / raw)
  To: Andrew MacLeod, Jeff Law; +Cc: gcc-patches, Diego Novillo

On Wednesday 20 October 2004 15:14, Andrew MacLeod wrote:
> If I understand the problem properly, the fundamental problem here is
> that a block becomes unreachable by removing all the incoming edges. PHI
> arguments for those edges are removed as the edge is removed. When the
> last edge is removed, the PHI node has no more arguments, and thus gets
> deleted.  None of the code in the dead block is removed until later when
> delete_unreachable_blocks is called. Meanwhile, we end up pawing through
> one or more stmts in the dead block which contains uses of the PHI
> result.

Correct.


> I have a couple of questions.
>
> 1 - Why does cleanup_control_flow() ever look at a stmts inside an
> unreachable block? Its seems rather, umm, unnecessary, for starters. Why
> not just call delete_unreachable_blocks() as the *first* thing in
> cfg_cleanup(). It doesn't look like its an expensive call...

Well, it wouldn't help because the block is made unreachable by 
cleanup_control_flow().

What happens is that cleanup_control_flow() uses FOR_EACH_BB which
walks BBs from index 0 to last_basic_block, so it sees BB 2 before
BB 4.  In the test case, cleaning up control flow out of BB 2 makes
BB 4 unreachable.  So calling delete_unreachable_blocks() before
cleanup_control_flow() would not help in this case.
Hence my patch to make cleanup_control_flow() ignore unreachable BBs.


> 2 - The issue may also exist outside cleanup_control_flow, so why does
> remove_phi_arg_num have to remove the PHI node when is removes the last
> argument.

That is what I believe to be the problem.  Jeff thinks this is "the
right thing" to do.


> Why not allow the PHI node to exist with no arguments.

That would work too, I guess.


> >   2. When we release an SSA_NAME and PHI_NODE go and find all uses
> >      of the SSA_NAME and release them too.  This is effectively an
> >      iterative DCE process.
>
> I am not very fond of this one :-)  Especially since they are going to
> be dealt with en-mass when you delete the block anyway.

Exactly my feeling about this.

Gr.
Steven


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-20 13:32             ` Steven Bosscher
@ 2004-10-20 13:47               ` Andrew MacLeod
  2004-10-20 14:30                 ` Steven Bosscher
  2004-10-22 19:15               ` Jeffrey A Law
  1 sibling, 1 reply; 28+ messages in thread
From: Andrew MacLeod @ 2004-10-20 13:47 UTC (permalink / raw)
  To: Steven Bosscher; +Cc: Jeff Law, gcc-patches, Diego Novillo

On Wed, 2004-10-20 at 09:27, Steven Bosscher wrote:

> >
> > 1 - Why does cleanup_control_flow() ever look at a stmts inside an
> > unreachable block? Its seems rather, umm, unnecessary, for starters. Why
> > not just call delete_unreachable_blocks() as the *first* thing in
> > cfg_cleanup(). It doesn't look like its an expensive call...
> 
> Well, it wouldn't help because the block is made unreachable by 
> cleanup_control_flow().
> 
> What happens is that cleanup_control_flow() uses FOR_EACH_BB which
> walks BBs from index 0 to last_basic_block, so it sees BB 2 before
> BB 4.  In the test case, cleaning up control flow out of BB 2 makes
> BB 4 unreachable.  So calling delete_unreachable_blocks() before
> cleanup_control_flow() would not help in this case.
> Hence my patch to make cleanup_control_flow() ignore unreachable BBs.
> 

Why doesnt cleanup_control_flow actually follow the flow from entry to
exit instead of FOR_EACH_BB?  Does it have to do something in blocks
that are unreachable?  Or is it just an attempt to avoid using a visited
bitmap?

> 
> > 2 - The issue may also exist outside cleanup_control_flow, so why does
> > remove_phi_arg_num have to remove the PHI node when is removes the last
> > argument.
> 
> That is what I believe to be the problem.  Jeff thinks this is "the
> right thing" to do.

I think he believes the right thing to do is to put the PHI_RESULT on
the free list when the PHI node is deleted.  Thats different than the
issue of having remove_phi_arg_num remove the PHI node.  But that just
my interpretation, I don't presume to actually say what he believes.

I just know I don't think remove_phi_arg_num() ought to delete the PHI
node when the last argument is removed...

Andrew

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-20 13:47               ` Andrew MacLeod
@ 2004-10-20 14:30                 ` Steven Bosscher
  2004-10-20 16:53                   ` Andrew MacLeod
  0 siblings, 1 reply; 28+ messages in thread
From: Steven Bosscher @ 2004-10-20 14:30 UTC (permalink / raw)
  To: Andrew MacLeod; +Cc: Jeff Law, gcc-patches, Diego Novillo

On Wednesday 20 October 2004 15:41, Andrew MacLeod wrote:
> Why doesnt cleanup_control_flow actually follow the flow from entry to
> exit instead of FOR_EACH_BB?

I'm asking myself that each time I see FOR_{EACH,ALL}_BB.

>  Does it have to do something in blocks
> that are unreachable?

No.

>  Or is it just an attempt to avoid using a visited
> bitmap?

And a stack for backtracking.

I've been thinking for some time now about implementing FOR_EACH_BB_DFS
(and perhaps other visiting orders) using some iterator.  You think that
would be a good idea?

Gr.
Steven

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-20 14:30                 ` Steven Bosscher
@ 2004-10-20 16:53                   ` Andrew MacLeod
  2004-10-20 17:33                     ` Daniel Berlin
  0 siblings, 1 reply; 28+ messages in thread
From: Andrew MacLeod @ 2004-10-20 16:53 UTC (permalink / raw)
  To: Steven Bosscher; +Cc: Jeff Law, gcc-patches, Diego Novillo

On Wed, 2004-10-20 at 09:59, Steven Bosscher wrote: 
> On Wednesday 20 October 2004 15:41, Andrew MacLeod wrote:
> > Why doesnt cleanup_control_flow actually follow the flow from entry to
> > exit instead of FOR_EACH_BB?
> 
> I'm asking myself that each time I see FOR_{EACH,ALL}_BB.
> 
> >  Does it have to do something in blocks
> > that are unreachable?
> 
> No.
> 
> >  Or is it just an attempt to avoid using a visited
> > bitmap?
> 
> And a stack for backtracking.

yeah, I guess, but still, thats not so bad.  


> I've been thinking for some time now about implementing FOR_EACH_BB_DFS
> (and perhaps other visiting orders) using some iterator.  You think that
> would be a good idea?

Wasnt Dan mumbling something a while ago about an iterator to visit in
dominator order too?

I suspect there are uses for such things. I also suspect its done by
hand in more than a few places too.  I also thought we had something
once upon a time that followed the edges ike that, but I could be
mistaken.

I've never looked at all the FOR_*_BB loops to see how useful it would
be.

Andrew

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-20 16:53                   ` Andrew MacLeod
@ 2004-10-20 17:33                     ` Daniel Berlin
  0 siblings, 0 replies; 28+ messages in thread
From: Daniel Berlin @ 2004-10-20 17:33 UTC (permalink / raw)
  To: Andrew MacLeod; +Cc: Jeff Law, gcc-patches, Steven Bosscher, Diego Novillo

>
>> I've been thinking for some time now about implementing 
>> FOR_EACH_BB_DFS
>> (and perhaps other visiting orders) using some iterator.  You think 
>> that
>> would be a good idea?
>
> Wasnt Dan mumbling something a while ago about an iterator to visit in
> dominator order too?
>

Yes.
The dominator walker is a little too much overkill for a lot of things 
:)

However, if you are going to write a dominator visitor without it, you 
are just better off making it recurse.

IE

do_whatever_to_bb (basic_block bb)
{
	basic_block son;
	for (son = first_son (CDI_DOMINATORS, bb);
		son;
		son = next_son (CDI_DOMINATORS, son);
	do_whatever_to_bb (son);
}
This is why i never made an iterator, because it was cleaner to just do 
things block by block in the cases i was doing, then it was to have one 
function that was dealing with all blocks using a stack.

> I suspect there are uses for such things. I also suspect its done by
> hand in more than a few places too.  I also thought we had something
> once upon a time that followed the edges ike that, but I could be
> mistaken.
>
> I've never looked at all the FOR_*_BB loops to see how useful it would
> be.
>
> Andrew
>

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-19 23:14             ` Daniel Berlin
@ 2004-10-21  2:33               ` Jeffrey A Law
  0 siblings, 0 replies; 28+ messages in thread
From: Jeffrey A Law @ 2004-10-21  2:33 UTC (permalink / raw)
  To: Daniel Berlin
  Cc: Andrew MacLeod, Diego Novillo, GCC Patches, Steven Bosscher,
	Kenneth Zadeck

On Tue, 2004-10-19 at 17:13, Daniel Berlin wrote:
> On Oct 19, 2004, at 7:08 PM, Daniel Berlin wrote:
> 
> >
> > On Oct 19, 2004, at 6:30 PM, Jeffrey A Law wrote:
> >
> >> On Tue, 2004-10-19 at 16:23, Daniel Berlin wrote:
> >>
> >>> Only if your pass performs *all* insertions and updates to statements
> >>> before performing *any* removals of statements.
> >> True.  However, I believe that is the case for most of our optimizers
> >> right now.
> >
> > Except for things that just want t
> Sigh.
> Hit send too early by accident.
> 
> Except for things that just want to do replacements without worrying 
> about what happens to the resulting statements.
Right.

> Trying to keep our ir in a "minimal form" so to speak (where there are 
> never dead statements) doesn't seem like the best idea, however.
I can see arguments from both directions.  Certainly my experience
with trying to do this in RTL was, err, bad.  I can't express how
happy I was when Jan killed that code.

However, I can see how not having dead statements in the IL would
make somethings easier.

What would be good would be to get to a point where we no
longer need the SSA_NAME and PHI_NODE managers which would avoid
at least one class of problems with the current approach of leaving
dead code in the IL until DCE comes along to clean it up.

jeff

err, good.   :-)  

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-20 13:17           ` Andrew MacLeod
  2004-10-20 13:32             ` Steven Bosscher
@ 2004-10-22 19:10             ` Jeffrey A Law
  1 sibling, 0 replies; 28+ messages in thread
From: Jeffrey A Law @ 2004-10-22 19:10 UTC (permalink / raw)
  To: Andrew MacLeod; +Cc: Steven Bosscher, gcc-patches, Diego Novillo

On Wed, 2004-10-20 at 07:14, Andrew MacLeod wrote:
> On Tue, 2004-10-19 at 19:13, Jeffrey A Law wrote:
> > On Tue, 2004-10-19 at 16:36, Steven Bosscher wrote:
> > 
> > > > Err, if we remove the last argument to a PHI node then by definition
> > > > the block containing the PHI is unreachable as it has no incoming
> > > > edges.
> > > >
> > > > There is no such thing as an "undefined" PHI node.
> > > 
> > > I didn't say we do.  I said we may have an undefined PHI result,
> > > i.e. and SSA_NAME without a definition.
> > OK.  And that is something that is, unfortunately, normal in our
> > implementation.  If I look at the SSA_NAME manager that's by far
> > its largest wart.
> > 
> 
> If I understand the problem properly, the fundamental problem here is
> that a block becomes unreachable by removing all the incoming edges. PHI
> arguments for those edges are removed as the edge is removed. When the
> last edge is removed, the PHI node has no more arguments, and thus gets
> deleted.  None of the code in the dead block is removed until later when
> delete_unreachable_blocks is called. Meanwhile, we end up pawing through
> one or more stmts in the dead block which contains uses of the PHI
> result.
> 
> I have a couple of questions.
> 
> 1 - Why does cleanup_control_flow() ever look at a stmts inside an
> unreachable block? Its seems rather, umm, unnecessary, for starters. Why
> not just call delete_unreachable_blocks() as the *first* thing in
> cfg_cleanup(). It doesn't look like its an expensive call... 
That doesn't help solve this problem.  The unreachable blocks are
created by cleanup_control_flow itself.  So calling
delete_unreachable_blocks before or after cleanup_control_flow
doesn't solve the problem.


> 2 - The issue may also exist outside cleanup_control_flow, so why does
> remove_phi_arg_num have to remove the PHI node when is removes the last
> argument. Why not allow the PHI node to exist with no arguments. It'll
> get removed and free'd if the block remains unreachable.
An excellent question and suggestion.  It may actually be the best
proposed solution.

I think we would all agree that a PHI with no arguments can only occur
in an unreachable block.  Can someone verify that we release PHI nodes
when we remove unreachable blocks?  I suspect we don't right now
because we rely upon generic code to identify and remove unreachable
blocks.  IIRC that does doesn't know about PHIs at all.



>  Maybe someone
> will add another edge back in at some point during the optimization,
> then there are PHI nodes ready to take the arguments.  I presume right
> now we make sure we add new edges before deleting old ones when
> redirecting things (to avoid deleting the PHI).
I'm not aware of any code that does this.  But your solution certainly
avoids this kind of problem in the future.  It's certainly the case
that we've had code elsewhere in the compiler which would temporarily
bump up a counter to avoid having objects disappear.  This was
pretty common with labels in the RTL optimizers.
 
Jeff

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-20 13:32             ` Steven Bosscher
  2004-10-20 13:47               ` Andrew MacLeod
@ 2004-10-22 19:15               ` Jeffrey A Law
  2004-10-22 19:33                 ` Steven Bosscher
  1 sibling, 1 reply; 28+ messages in thread
From: Jeffrey A Law @ 2004-10-22 19:15 UTC (permalink / raw)
  To: Steven Bosscher; +Cc: Andrew MacLeod, gcc-patches, Diego Novillo

On Wed, 2004-10-20 at 07:27, Steven Bosscher wrote:

> 
> > 2 - The issue may also exist outside cleanup_control_flow, so why does
> > remove_phi_arg_num have to remove the PHI node when is removes the last
> > argument.
> 
> That is what I believe to be the problem.  Jeff thinks this is "the
> right thing" to do.
What I think is right is to ensure that we release the dead PHIs
and their associated PHI_RESULTs.  What Andrew made clearer in
his message is that we would get a chance to collect them when
we remove unreachable blocks since the only time we can have a
PHI with no args is when we have unreachable blocks.

I'm pretty sure we don't release PHIs and SSA_NAMEs in that code,
but it shouldn't be terribly hard to add it in a way that is
safe (since the unreachable block removal code is used by both
trees and rtl).



> 
> 
> > Why not allow the PHI node to exist with no arguments.
> 
> That would work too, I guess.
And I like that a lot better than removing the PHI and leaving
in references to the result.



^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-22 19:15               ` Jeffrey A Law
@ 2004-10-22 19:33                 ` Steven Bosscher
  2004-10-22 19:37                   ` Jeffrey A Law
  0 siblings, 1 reply; 28+ messages in thread
From: Steven Bosscher @ 2004-10-22 19:33 UTC (permalink / raw)
  To: law; +Cc: Andrew MacLeod, gcc-patches, Diego Novillo

On Friday 22 October 2004 21:12, Jeffrey A Law wrote:
> I'm pretty sure we don't release PHIs and SSA_NAMEs in that code,
> but it shouldn't be terribly hard to add it in a way that is
> safe (since the unreachable block removal code is used by both
> trees and rtl).

It's cfg-hookized via delete_basic_block (remove_bb in tree-cfg.c),
so it's probably enough to teach remove_bb about this.

> > > Why not allow the PHI node to exist with no arguments.
> >
> > That would work too, I guess.
>
> And I like that a lot better than removing the PHI and leaving
> in references to the result.

Yup.

Gr.
Steven

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-22 19:33                 ` Steven Bosscher
@ 2004-10-22 19:37                   ` Jeffrey A Law
  2004-10-22 19:40                     ` Steven Bosscher
  0 siblings, 1 reply; 28+ messages in thread
From: Jeffrey A Law @ 2004-10-22 19:37 UTC (permalink / raw)
  To: Steven Bosscher; +Cc: Andrew MacLeod, gcc-patches, Diego Novillo

On Fri, 2004-10-22 at 13:16, Steven Bosscher wrote:
> On Friday 22 October 2004 21:12, Jeffrey A Law wrote:
> > I'm pretty sure we don't release PHIs and SSA_NAMEs in that code,
> > but it shouldn't be terribly hard to add it in a way that is
> > safe (since the unreachable block removal code is used by both
> > trees and rtl).
> 
> It's cfg-hookized via delete_basic_block (remove_bb in tree-cfg.c),
> so it's probably enough to teach remove_bb about this.
Can you give this a try?  I don't think I'll get to it today and
I'd like to get this issue resolved.

jeff


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-22 19:37                   ` Jeffrey A Law
@ 2004-10-22 19:40                     ` Steven Bosscher
  2004-10-22 21:08                       ` Jeffrey A Law
  0 siblings, 1 reply; 28+ messages in thread
From: Steven Bosscher @ 2004-10-22 19:40 UTC (permalink / raw)
  To: law; +Cc: Andrew MacLeod, gcc-patches, Diego Novillo

On Friday 22 October 2004 21:27, Jeffrey A Law wrote:
> On Fri, 2004-10-22 at 13:16, Steven Bosscher wrote:
> > On Friday 22 October 2004 21:12, Jeffrey A Law wrote:
> > > I'm pretty sure we don't release PHIs and SSA_NAMEs in that code,
> > > but it shouldn't be terribly hard to add it in a way that is
> > > safe (since the unreachable block removal code is used by both
> > > trees and rtl).
> >
> > It's cfg-hookized via delete_basic_block (remove_bb in tree-cfg.c),
> > so it's probably enough to teach remove_bb about this.
>
> Can you give this a try?  I don't think I'll get to it today and
> I'd like to get this issue resolved.
>

OK, so here we go:

1) delete_unreachable_blocks calls delete_basic_block.
2) delete_basic_block calls remove_bb
3) remove_bb calls remove_phi_nodes_and_edges_for_unreachable_block
4) remove_phi_nodes_and_edges_for_unreachable_block calls remove_phi_node
5) remove_phi_node calls release_phi_node and release_ssa_name
6) -release_phi_node puts the PHIs in the freelist.
   -release_ssa_name puts the SSA_NAMEs in the freelist

So it should already work.

I'll see if I can verify that it indeed actually happens.

Gr.
Steven


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-22 19:40                     ` Steven Bosscher
@ 2004-10-22 21:08                       ` Jeffrey A Law
  2004-10-24 21:20                         ` Steven Bosscher
  0 siblings, 1 reply; 28+ messages in thread
From: Jeffrey A Law @ 2004-10-22 21:08 UTC (permalink / raw)
  To: Steven Bosscher; +Cc: Andrew MacLeod, gcc-patches, Diego Novillo

On Fri, 2004-10-22 at 13:33, Steven Bosscher wrote:
> On Friday 22 October 2004 21:27, Jeffrey A Law wrote:
> > On Fri, 2004-10-22 at 13:16, Steven Bosscher wrote:
> > > On Friday 22 October 2004 21:12, Jeffrey A Law wrote:
> > > > I'm pretty sure we don't release PHIs and SSA_NAMEs in that code,
> > > > but it shouldn't be terribly hard to add it in a way that is
> > > > safe (since the unreachable block removal code is used by both
> > > > trees and rtl).
> > >
> > > It's cfg-hookized via delete_basic_block (remove_bb in tree-cfg.c),
> > > so it's probably enough to teach remove_bb about this.
> >
> > Can you give this a try?  I don't think I'll get to it today and
> > I'd like to get this issue resolved.
> >
> 
> OK, so here we go:
> 
> 1) delete_unreachable_blocks calls delete_basic_block.
> 2) delete_basic_block calls remove_bb
> 3) remove_bb calls remove_phi_nodes_and_edges_for_unreachable_block
> 4) remove_phi_nodes_and_edges_for_unreachable_block calls remove_phi_node
> 5) remove_phi_node calls release_phi_node and release_ssa_name
> 6) -release_phi_node puts the PHIs in the freelist.
>    -release_ssa_name puts the SSA_NAMEs in the freelist
> 
> So it should already work.
> 
> I'll see if I can verify that it indeed actually happens.
Cool.  Let me know how it goes.

jeff


^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-22 21:08                       ` Jeffrey A Law
@ 2004-10-24 21:20                         ` Steven Bosscher
  2004-10-27 16:27                           ` Jeffrey A Law
  0 siblings, 1 reply; 28+ messages in thread
From: Steven Bosscher @ 2004-10-24 21:20 UTC (permalink / raw)
  To: law; +Cc: Andrew MacLeod, gcc-patches, Diego Novillo

On Friday 22 October 2004 21:50, Jeffrey A Law wrote:
> Cool.  Let me know how it goes.

Bootstrapped and tested on i686-suse-linux-gnu, and I
verified with GDB that the PHI is still removed at least
for emptyif.f90.

Gr.
Steven

	* tree-phinodes.c (remove_phi_arg_num): Don't remove PHIs
	without any PHI arguments left.  Make sure the argument that
	we're supposed to remove exists at all.

Index: tree-phinodes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-phinodes.c,v
retrieving revision 2.9
diff -c -3 -p -r2.9 tree-phinodes.c
*** tree-phinodes.c	29 Sep 2004 21:23:35 -0000	2.9
--- tree-phinodes.c	24 Oct 2004 19:54:36 -0000
*************** remove_phi_arg_num (tree phi, int i)
*** 407,412 ****
--- 407,414 ----
  {
    int num_elem = PHI_NUM_ARGS (phi);
  
+   gcc_assert (i < num_elem);
+ 
    /* If we are not at the last element, switch the last element
       with the element we want to delete.  */
    if (i != num_elem - 1)
*************** remove_phi_arg_num (tree phi, int i)
*** 421,431 ****
    PHI_ARG_EDGE (phi, num_elem - 1) = NULL;
    PHI_ARG_NONZERO (phi, num_elem - 1) = false;
    PHI_NUM_ARGS (phi)--;
- 
-   /* If we removed the last PHI argument, then go ahead and
-      remove the PHI node.  */
-   if (PHI_NUM_ARGS (phi) == 0)
-     remove_phi_node (phi, NULL, bb_for_stmt (phi));
  }
  
  /* Remove PHI node PHI from basic block BB.  If PREV is non-NULL, it is
--- 423,428 ----

^ permalink raw reply	[flat|nested] 28+ messages in thread

* Re: Fix a tcb crash and a potential bug on mainline
  2004-10-24 21:20                         ` Steven Bosscher
@ 2004-10-27 16:27                           ` Jeffrey A Law
  0 siblings, 0 replies; 28+ messages in thread
From: Jeffrey A Law @ 2004-10-27 16:27 UTC (permalink / raw)
  To: Steven Bosscher; +Cc: Andrew MacLeod, gcc-patches, Diego Novillo

On Sun, 2004-10-24 at 21:59 +0200, Steven Bosscher wrote:
> On Friday 22 October 2004 21:50, Jeffrey A Law wrote:
> > Cool.  Let me know how it goes.
> 
> Bootstrapped and tested on i686-suse-linux-gnu, and I
> verified with GDB that the PHI is still removed at least
> for emptyif.f90.
> 
> Gr.
> Steven
> 
> 	* tree-phinodes.c (remove_phi_arg_num): Don't remove PHIs
> 	without any PHI arguments left.  Make sure the argument that
> 	we're supposed to remove exists at all.
Looks good to me.  Thanks for your patience.

jeff


^ permalink raw reply	[flat|nested] 28+ messages in thread

end of thread, other threads:[~2004-10-27 16:22 UTC | newest]

Thread overview: 28+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-10-18 21:09 Fix a tcb crash and a potential bug on mainline Steven Bosscher
2004-10-18 22:06 ` Andrew MacLeod
2004-10-18 22:18 ` Andrew Pinski
2004-10-19 20:58 ` Jeffrey A Law
2004-10-19 21:29   ` Steven Bosscher
2004-10-19 22:08     ` Jeffrey A Law
2004-10-19 22:27       ` Daniel Berlin
2004-10-19 22:35         ` Jeffrey A Law
2004-10-19 23:08           ` Daniel Berlin
2004-10-19 23:14             ` Daniel Berlin
2004-10-21  2:33               ` Jeffrey A Law
2004-10-19 22:36       ` Steven Bosscher
2004-10-19 22:41         ` Diego Novillo
2004-10-19 23:16         ` Jeffrey A Law
2004-10-20 13:17           ` Andrew MacLeod
2004-10-20 13:32             ` Steven Bosscher
2004-10-20 13:47               ` Andrew MacLeod
2004-10-20 14:30                 ` Steven Bosscher
2004-10-20 16:53                   ` Andrew MacLeod
2004-10-20 17:33                     ` Daniel Berlin
2004-10-22 19:15               ` Jeffrey A Law
2004-10-22 19:33                 ` Steven Bosscher
2004-10-22 19:37                   ` Jeffrey A Law
2004-10-22 19:40                     ` Steven Bosscher
2004-10-22 21:08                       ` Jeffrey A Law
2004-10-24 21:20                         ` Steven Bosscher
2004-10-27 16:27                           ` Jeffrey A Law
2004-10-22 19:10             ` Jeffrey A Law

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).