[tree-ssa] running DCE before DOM1

[Steven Bosscher]

Hi,

While experimenting with the test case for Bug 13629, I noticed that doing DCE 
before DOM1 can significantly clean up the code at seemingly no extra 
compilation time cost.  I tried this on Gerald's test case, which gave me no 
measurable compiler slowdown, but I also had cc1plus dump the trees after 
dom1.  The size difference for the DOM1 dump is large (i.e. the new DCE pass 
cleans up a lot of dead code early):

8361.ii.t17.dom1 17172805 bytes without DCE before DOM1.
8361.ii.t18.dom1 20171686 bytes with the patch.

Removed 77255 of 430148 statements (17%)
Removed 23942 of 127790 PHI nodes (18%)

I also timed the files >800k from Diego's cc1-i files and got a very small 
speedup (2s on 8m20, all files, for all three runs I did, both with and 
without the patch).  The stats from the (new) .dom1 dump look like this (the 
numbers are file totals):

c-common.i.t17.dce1:
Removed 3599 of 57383 statements (6%)
Removed 1054 of 3619 PHI nodes (29%)

c-decl.i.t17.dce1
Removed 4314 of 73604 statements (5%)
Removed 2375 of 18797 PHI nodes (12%)

com.i.t17.dce1
Removed 5064 of 94861 statements (5%)
Removed 3155 of 18303 PHI nodes (17%)

fold-const.i.t17.dce1
Removed 12427 of 168384 statements (7%)
Removed 3136 of 11565 PHI nodes (27%)

i386.i.t17.dce1
Removed 6250 of 116381 statements (5%)
Removed 5426 of 19128 PHI nodes (28%)

insn-attrtab.i.t17.dce1
Removed 6428 of 332253 statements (1%)
Removed 3572 of 43945 PHI nodes (8%)

insn-emit.i.t17.dce1
Removed 2223 of 64029 statements (3%)
Removed 265 of 1327 PHI nodes (19%)

insn-recog.i.t17.dce1
Removed 12440 of 327481 statements (3%)
Removed 409 of 16115 PHI nodes (2%)

pt.i.t17.dce1
Removed 11579 of 155746 statements (7%)
Removed 2864 of 15340 PHI nodes (18%)

Finally, it also fixes the problem for Bug 13629, which is about using dead 
expressions for CSE, making the dead code only partially dead:

int *data; 
void partial_dead (int i, int j) 
{ 
  int k = i * j; 
  if (i & j) 
    data[0] = i * j; 
}

--> without the patch:
partial_dead: 
        movl    4(%esp), %edx   # i 
        movl    8(%esp), %eax   # j 
        movl    %edx, %ecx      # k = i 
        imull   %eax, %ecx      # k = i * j 
        testl   %eax, %edx      # if (j & i) 
        je      .L1             #   goto <L1> 
        movl    data, %eax 
        movl    %ecx, (%eax)    # *data = k 
.L1: 
        ret 

--> with the patch applied:
partial_dead: 
        movl    4(%esp), %edx   # i 
        movl    8(%esp), %eax   # j 
        testl   %eax, %edx      # if (j & i) 
        je      .L1             # goto <L1> 
        imull   %eax, %edx      # k = i * j 
        movl    data, %eax 
        movl    %edx, (%eax)    # *data = k 
.L1: 
        ret 

The effect of all this on the resulting object files seems to be negligible.  
The full unidiff for 8361.s with and without the patch is only 51 lines long 
and is mostly about replacing uses of %edi with %esi for some obscure reason, 
and exactly one movl less with the patch applied :-)

I don't know if running DCE so early can have a negative impact on other 
passes.  Thoughts?

Gr.
Steven

	* tree-optimize.c (init_tree_optimization_passes): Run DCE
	before the first dominator optimization pass.

Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.109
diff -c -3 -p -r1.1.4.109 tree-optimize.c
*** tree-optimize.c	15 Jan 2004 06:43:19 -0000	1.1.4.109
--- tree-optimize.c	15 Jan 2004 23:58:23 -0000
*************** init_tree_optimization_passes (void)
*** 279,286 ****
    NEXT_PASS (pass_referenced_vars);
    NEXT_PASS (pass_build_pta);
    NEXT_PASS (pass_build_ssa);
-   NEXT_PASS (pass_dominator);
    NEXT_PASS (pass_dce);
    NEXT_PASS (pass_may_alias);
    NEXT_PASS (pass_del_pta);
    NEXT_PASS (pass_profile);
--- 279,287 ----
    NEXT_PASS (pass_referenced_vars);
    NEXT_PASS (pass_build_pta);
    NEXT_PASS (pass_build_ssa);
    NEXT_PASS (pass_dce);
+   NEXT_PASS (pass_dominator);
+   NEXT_PASS (DUP_PASS (pass_dce));
    NEXT_PASS (pass_may_alias);
    NEXT_PASS (pass_del_pta);
    NEXT_PASS (pass_profile);