PR middle-end 42906 (empty loops not removed when leaved via critical edge with PHI node attached)

[Martin Jambor]

Hi,

I don't usually do this but at least the big comment really needs some
attention.

On Sat, Mar 27, 2010 at 06:37:34PM +0100, Jan Hubicka wrote:
> 
> Index: tree-ssa-dce.c
> ===================================================================

...

> --- tree-ssa-dce.c	(revision 157705)
> +++ tree-ssa-dce.c	(working copy)
> @@ -679,17 +687,85 @@ propagate_necessity (struct edge_list *e
>  		mark_operand_necessary (arg);
>  	    }
>  
> +	  /* For PHI operands it matters from where the control flow arrives
> +	     to the BB.  Consider the following example:

Shouldn't this rather be "where the control flow arrives from?"  It
always has to arrive to the beginning of a BB.

> +
> +	     a=exp1;
> +	     b=exp2;
> +	     if (test)
> +		;
> +	     else
> +		;
> +	     c=PHI(a,b)
> +
> +	     We need to mark control dependence of the empty basic blocks, since they
> +	     contains computation of PHI operands.

they contain (no s at the end)

> +
> +	     Doing so is too restrictive in the case the predecestor 

predecessor

>								     block is in
> +	     the loop.  

I assume you meant in _a_ loop.  If not then I don't understand the
sentence.  I would even turn this into "...in a loop in which the BB
with the PHI node is not."  In fact, this is the thing that made me
write this whole email (and run spellchecker and stuff :-)

Replacing "in the case" with a simple "if" would also be nice.
			
>			In this case the control dependence of predecestor 
									   
predecessor

>									   block
> +	     also contains the block determining number of iterations of the block
> +	     that would prevent removing of empty loops in this case.

removing empty loops (the preposition of doesn't sound right, or you
could write removal of empty loops)

> +
> +	     This scenario can be avoided by splitting critical edges.
> +	     To save the critical edge splitting pass we identify how the control
> +	     dependence would look like if the edge was split.
> +
> +	     Consider the modified CFG created from current CFG by splitting
> +	     edge B->C.  In the postdominance tree of modified CFG, C' is
> +	     always child of C.  There are two cases how chlids 
	
children
							
>								of C' can look
> +	     like:
> +
> +		1) C' is leaf
> +
> +		   In this case the only basic block C' is control dependent on is B.
> +
> +		2) C' has single child that is B

_a_ single child

> +
> +		   In this case control dependence of C' is same as control
> +		   dependence of B in original CFG except for block B itself.
> +		   (since C' postdominate B in modified CFG)
> +
> +	     Now how to decide what case 

which case
					 
>					 happens?  There are two basic options:
> +
> +		a) C postdominate B.  

postdominates
				      
>				      Then C immediately postdominate 
								      
likewise

>								      B and
> +		   case 2 happens iff there is no other way from B to C except
> +		   the edge B->C.
> +
> +		   There is other way from B to C iff there is succesor 
									
_a_ succes_s_or

>									of B that
> +		   is not postdominated by B.  Testing this condition is somewhat
> +		   expensive, because we need to iterate all succesors 

successor
								       
>								       of B.
> +		   We are safe to assume that this does not happen: we will mark B
> +		   as needed when processing the other path from B to C that is
> +		   conrol 

control
			  
>			  dependent on B and marking control dependencies of B
> +		   itself is harmless because they will be processed anyway after
> +		   processing control statement in B.
> +
> +		b) C does not postdominate B.  Always case 1 happens since there is
> +		   path from C to exit that does not go through B and thus also C'.  */

Thanks,

Martin