[tree-ssa] Speeding up dom & cprop

[law at redhat dot com]

Andrew's favorite testcase (interpret.cc from libjava) was still spending
way too much time copy propagating into PHI nodes.  In fact, 15% of the
total compilation time is spent trying to copy propagate into PHI nodes
in one way or another.

The hell of the situation is that for interpret.cc (and code of a similar
nature), that time is wasted doing useless work.

For the dominator optimizer we're trying to copy propagate into the
PHI alternative associated with a specific edge.  If that edge is an
abnormal edge, then the copy propagation will never succeed as we block
such propagations.  Fixing that cuts the time in the dominator optimizer
by 90%.

tree-ssa-copyprop has a similar lameness, though its structure is somewhat
different.  In the case of tree-ssa-copyprop we are trying to propagate
into every alternative of a particular phi all at once.  I this case we
can check the result of the PHI.  If the result occurs in an abnormal
PHI, then we know the copy propagation can never be successful.  Fixing
that basically brings the time in the copy propagator down to zero.

In combination those two changes zap 15% off the compilation time for
interpret.cc without sacrificing optimization.

	* tree-ssa-dom.c (cprop_into_phis): Avoid doing useless work if the
	edge we care about is abnormal.
	* tree-ssa-copyprop (cprop_phi): Avoid doing useless work if the
	destination of the PHI node occurs in an abnormal PHI.


Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.59
diff -c -3 -p -r1.1.2.59 tree-ssa-dom.c
*** tree-ssa-dom.c	14 Oct 2003 21:52:56 -0000	1.1.2.59
--- tree-ssa-dom.c	15 Oct 2003 04:53:14 -0000
*************** cprop_into_phis (basic_block bb, varray_
*** 1490,1495 ****
--- 1490,1500 ----
        int phi_num_args;
        int hint;
  
+       /* If this is an abnormal edge, then we do not want to copy propagate
+ 	 into the PHI alternative associated with this edge.  */
+       if (e->flags & EDGE_ABNORMAL)
+ 	continue;
+ 
        phi = phi_nodes (e->dest);
        if (! phi)
  	continue;
Index: tree-ssa-copyprop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-copyprop.c,v
retrieving revision 1.1.2.17
diff -c -3 -p -r1.1.2.17 tree-ssa-copyprop.c
*** tree-ssa-copyprop.c	13 Oct 2003 15:36:00 -0000	1.1.2.17
--- tree-ssa-copyprop.c	15 Oct 2003 04:53:14 -0000
*************** copyprop_phi (tree phi)
*** 156,161 ****
--- 156,167 ----
        fprintf (dump_file, "\n");
      }
  
+   /* If the result is a abnormal PHI, then there's no sense in trying
+      to copy propagate into its arguments since every attempt will
+      fail.  */
+   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)))
+     return;
+ 
    for (i = 0; i < PHI_NUM_ARGS (phi); i++)
      {
        tree arg = PHI_ARG_DEF (phi, i);