Re: [patch] Prevent DOM from creating overlapping live ranges ofivs

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

On Wed, 2005-02-16 at 23:38 +0100, Zdenek Dvorak wrote:
> Hello,
> 
> if DOM sees the following code:
> 
> while (1)
>   {
>     i_1 = phi(0, i_2);
>     i_2 = i_1 + 1;
> 
>     if (something)
>       break;
> 
>     foo (i_2 + 3);
>   }
> 
> It transforms it to
> 
> while (1)
>   {
>     i_1 = phi(0, i_2);
>     i_2 = i_1 + 1;
> 
>     if (something)
>       break;
> 
>     foo (i_1 + 4);
>   }
> 
> This by itself is a missoptimization, since it does not help anything
> and forces us to use two registers for i instead of one.  But things
> get only worse.
> 
> Loop header copying then creates the following code:
> 
> if (!something)
>   goto somewhere;
> 
> i_1 = 0;
> i_2 = 1;
> while (1)
>   {
>     i_1 = phi (0, i_3);
>     i_2 = phi (1, i_4);
> 
>     foo (i_1 + 4);
> 
>     i_3 = i_2;
>     i_4 = i_3 + 1;
> 
>     if (something)
>       break;
>   }
> 
> This copy propagates to
> 
> if (!something)
>   goto somewhere;
> 
> i_1 = 0;
> i_2 = 1;
> while (1)
>   {
>     i_1 = phi (0, i_2);
>     i_2 = phi (1, i_4);
> 
>     foo (i_1 + 4);
>     i_4 = i_2 + 1;
> 
>     if (something)
>       break;
>   }
> 
> Now we have two induction variables, and worse, i_1 is defined by
> cycling around the loop (i_1 == i_2 from previous iteration), which
> confuses iv analysis.  There is a patch by Sebastian for scev to handle
> this case, but I think the proper fix is to prevent dom from
> creating such monstrosities.
> 
> The patch below detects simple bivs and prevents dom from propagating
> the value of the iv before increment across the increment.
> 
> Bootstrapped & regtested on i686.
> 
> Zdenek
> 
> 	* tree-ssa-dom.c (simple_iv_increment_p): New function.
> 	(simplify_rhs_and_lookup_avail_expr, eliminate_redundant_computations):
> 	Do not propagate value of iv before increment over the increment.
This is fine.  Please go ahead and install.
jeff