This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[tree-ssa] Semi-latent jump threading bug


I ran into this with some pending changes to improve the jump threader, but
had been worried that the same underlying problem could show its ugly head
even without the more aggressive jump threading code.  Gerald managed to
trip it which confirmed my suspicions (which at some level is good since
I don't have to totally decipher my notes from before the holidays :-)

Basically we can "lose" certain assignments if the partial out-of-ssa
translation we perform after jump threading needs to insert a statement
on the edge we are redirecting to eliminate a PHI node.

Consider the following CFG


      1
     /|
    2 |
   /| | 
  3 | |
   \|/
    4
   / \
  5   6

Let's assume there are PHI nodes in block #4 and that to eliminate that
PHI node we are going to have to insert copies due to overlapping lifetimes
in the arguments.  [ In the actual testcase blocks #6 & #5 loop back to
block #1 which makes it easier to create overlapping lifetimes. ]

Let's also assume we want to thread 2->4 so that it reaches 6 and 3->4 so
that it reaches 5.

Elimination of the PHI nodes will create something like this:

      1
     / \
    2   8
   / \  |
  3   9 |
   \  | |
    \ |/
      4
     / \
    5   6



Ie, we split the edge from 2->4 and the edge from 1->4 and we insert some
statements in the newly created blocks (block 9 and block 8 respectively).

Then we perform our edge redirections.  We wanted to redirect 2->4 so that
it reaches 6 and 3->4 so that it reaches 5.  For the sake of simplicity let's
redirect 3->4 so that it reaches 5 first.


      1
     / \
    2   8
   / \  |
  3   9 |
  |   | |
  |   |/
  |   4
   \ / \
    5   6

So far so good.  Now for the redirection of edge 2->4 to block 6.

The edge from 2->4 was split, what we have now is two edges 2->9 and 9->4.
Our saved edge pointer points to the 2->9 edge.  If we redirect the 2->9 edge 
to block 6, then we bypass any statements in block #9 that were created to
remove the PHIs in block #4.  That is bad, very very bad.

What we need to do is redirect the edge 9->4 so that it reaches 6.

Luckily it's pretty simple to bulletproof the code to deal with this
case.  Given an edge we want to redirect E, if E->dest does not end with
a COND_EXPR or SWITCH_EXPR, then the edge must have been split and we want
to redirect E->dest->succ to reach a new target rather than E to reach a new
target.

Bootstrapped and regression tested i686-pc-linux-gnu.

	* tree-ssa-dom.c (tree_ssa_dominator_optimize): Correctly handle
	the case where an edge we wish to redirect is split by the out of SSA
	code.

Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.102
diff -c -3 -p -r1.1.2.102 tree-ssa-dom.c
*** tree-ssa-dom.c	19 Dec 2003 07:01:36 -0000	1.1.2.102
--- tree-ssa-dom.c	5 Jan 2004 22:10:44 -0000
*************** tree_ssa_dominator_optimize (tree fndecl
*** 427,432 ****
--- 427,463 ----
  	  if (bitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_vars_out_of_ssa (vars_to_rename);
  
+ 	  /* The out of SSA translation above may split the edge from
+ 	     E->src to E->dest.  This could potentially cause us to lose
+ 	     an assignment leading to invalid warnings about uninitialized
+ 	     variables or incorrect code.
+ 
+ 	     Luckily, we can detect this by looking at the last statement
+ 	     in E->dest.  If it is not a COND_EXPR or SWITCH_EXPR, then
+ 	     the edge was split and instead of E, we want E->dest->succ.  */
+ 	  for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
+ 	    {
+ 	      edge e = VARRAY_EDGE (redirection_edges, i);
+ 	      tree last = last_stmt (e->dest);
+ 
+ 	      if (last
+ 		  && TREE_CODE (last) != COND_EXPR
+ 		  && TREE_CODE (last) != SWITCH_EXPR)
+ 		{
+ 		  e = e->dest->succ;
+ 
+ #ifdef ENABLE_CHECKING
+ 		  /* There should only be a single successor if the
+ 		     original edge was split.  */
+ 		  if (e->succ_next)
+ 		    abort ();
+ #endif
+ 		  /* Replace the edge in REDIRECTION_EDGES for the
+ 		     loop below.  */
+ 		  VARRAY_EDGE (redirection_edges, i) = e;
+ 		}
+ 	    }
+ 
  	  /* Now redirect the edges.  */
  	  for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
  	    {










 


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]