Re: Q on redirect_edges

[Jeffrey A Law <law at redhat dot com>]

On Mon, 2005-05-09 at 21:19 -0400, Diego Novillo wrote:
> On Fri, May 06, 2005 at 11:12:20AM -0600, Jeffrey A Law wrote:
> 
> > For a duplicate block the first thing we do after creating the duplicate
> > block is remove the control statement at the end of the block
> > (see create_block_for_threading). 
> > 
> > If we are threading all incoming edges (and thus re-using the existing
> > block rather than creating a duplicate) we arrange to remove the
> > control statement in the original block in redirect_edges.
> > 
> I must be missing something else, because I set a breakpoint in
> both functions for block 3 and it never triggered.  We never try
> to remove the final control stmt from block 3.  I'm not sure what
> to do with this info you gave me.  We are setting something up
> the wrong way in the threader but I get lost in there.
> 
> I managed to reduce the problem to something that also triggers
> with mainline without my patch.  Do you think you'll have some
> time to take a look at it this week?  If not, I'll create a PR
> and see if I can work on it later this week.
[ ... ]
The fundamental problem was some extreme braindamage in the change to
allow jump threading to thread a computed jump.


Fundamentally, threading a computed jump is a good thing as it allows
paths in the CFG to use direct, normal jumps rather than computed jumps.
Something like

  x = phi (&l1, &l2)
  goto *x;

Will get turned into two blocks which look like

  goto l1;

  goto l2;

And the indirect jump will be eliminated as are the abnormal edges.



For reasons I can't comprehend I added code which attempts to thread
at the *destination* of a computed jump.  That is absolutely not safe
as successfully threading at the destination of a computed jump would
require revectoring the computed jump to a new location -- which is
a nontrivial exercise.  Diego's testcase falls into this category.

+ void bar (int k)
+ {
+   void *label = (k) ? &&x : &&y;
+   if (k)
+     goto *label;
+
+ x:
+   if (k)
+     dont_remove ();
+ y:
+   return;
+ }

We were trying to thread through the x: if(k) block when it was reached
via the goto *label.  Threading was successful and we then tried to 
redirect the goto *label statement which (of course) failed.

The proper way to optimize this testcase is to first thread the
goto *label so that it only reaches "x".  Resulting in something
like this:

+ void bar (int k)
+ {
+   void *label = (k) ? &&x : &&y;
+   if (k)
+     goto x;
+
+ x:
+   if (k)
+     dont_remove ();
+ y:
+   return;
+ }

At this point there are no computed gotos or abnormal edges -- and we
can thread the "goto x" so that it bypasses the second test of if (k)
so that the code wold look something like

    if (k)
  x:
      dont_remove ()
  y:
      return;


This patch removes the horribly bogus code which (of course) fixes
Diego's problem and we still are able to fully optimize this test.
Bootstrapped and regression tested on i686-pc-linux-gnu.

Attachment: PPP
Description: Text document