Re: [tree-ssa] DCE compile time repair.

[Diego Novillo <dnovillo at redhat dot com>]

On Fri, 2003-06-13 at 14:15, Andrew MacLeod wrote:
> I analyzed the testfile from the POOMA library which was taking forever
> to compile, and here's the fix.
> 
> When PHI nodes are marked as necessary, we need to make sure that if
> they are fed from a COND_EXPR, that we keep the COND_EXPR alive as well.
> If we delete the COND_EXPR and discover later that the PHI args and
> result don't coalesce, we need to insert copies on the edges, and if the
> COND_EXPR is gone, its impossible to recreate. ie:
> 
>   if (a_3 < 5)
>      a_6 = b_2
>   else
>     a_7 = c_8
> 
>   a_10 = PHI <a_6(2), a_7(3)>
> 
> copy prop turns this into:
> 
>   if (a_3 < 5)
>      ;
>   else
>      ;
>   a_10 = PHI <b_2(2), c_8(3)>
> 
> and dead code thinks the condition is no longer needed.
> 
> Anyway, the fix for that was a bit brute force. Whenever a PHI was
> marked as necessary, it would go look at each arguments source block. If
> the parent of the block ended in a COND_EXPR, then we'd mark the
> COND_EXPR as necessary.
> 
> This was being performed a bit too vigorously, and the more PHI nodes,
> the worse it got.
> 
> I restructured the checking slightly so that it only makes this check
> once per block. The result is that the POOMA library test case now
> compiles faster.
> 
> Before the patch,. DCE took 1678 seconds on my machine. After this
> patch, it takes 3.5 seconds. It was pretty lame before :-)
> 
Excellent!

> *************** process_worklist (void)
> *** 318,323 ****
> --- 318,329 ----
>     basic_block bb;
>     tree i, j;
>     edge e;
> +   sbitmap cond_checked, goto_checked;
> + 
> +   cond_checked = sbitmap_alloc (n_basic_blocks);
> +   goto_checked = sbitmap_alloc (n_basic_blocks);
> +   sbitmap_zero (cond_checked);
> +   sbitmap_zero (goto_checked);
>   
Wouldn't it be better to use a sparse bitmap instead?  They take a lot
less memory than sbitmaps.


Thanks.  Diego.