[patch] tree-ssa-threadupdate.c: Speed up threadblock.

[Kazu Hirata <kazu at cs dot umass dot edu>]

Hi,

Attached is a patch to speed up threadblock.

threadblock first adds PHI arguments to the basic block that we wish
to redirect an edge to before we actually redirect the edge.  It turns
out that this way of implementation would call phi_arg_from_edge more
than necessary.  Here is why.

1. copy_phis_to_block looks for PHI arguments using an edge that is
   about to be redirected.

2. ssa_redirect_edge, called from redirect_edge_and_branch, stores
   into PENDING_STMT the PHI arguments from the same edge.

Both of these operations use phi_arg_from_edge to locate PHI arguments
on the edge being redirected.

If we call redirect_edge_and_branch first, we can add PHI arguments to
the new edge using PENDING_STMT, which is stuffed by
ssa_redirect_edge.  Note that the running time of phi_arg_from_edge on
edge E is proportional to EDGE_COUNT (E->dest->preds).

Tested on i686-pc-linux-gnu.  OK to apply?

p.s.
As a good side effect of this patch, we create the redirected edge E
*before* we add PHI arguments associated with E.  This makes "O(1) PHI
argument look-up" easier to implement because given E's index in the
corresponding edge vector, we know where we should put the new PHI
arguments in the array of PHI arguments.

Kazu Hirata

2004-10-30  Kazu Hirata  <kazu@cs.umass.edu>

	* tree-ssa-threadupdate.c (copy_phis_to_block): Install PHI
	arguments using PENDING_STMT.
	(thread_block): Call copy_phis_to_block after redirecting an
	edge.

Index: tree-ssa-threadupdate.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-threadupdate.c,v
retrieving revision 2.11
diff -c -d -p -r2.11 tree-ssa-threadupdate.c
*** tree-ssa-threadupdate.c	22 Oct 2004 17:05:10 -0000	2.11
--- tree-ssa-threadupdate.c	30 Oct 2004 02:48:48 -0000
*************** struct redirection_data
*** 95,132 ****
  /* Main data structure to hold information for duplicates of BB.  */
  static varray_type redirection_data;
  
! /* For each PHI node in BB, find or create a PHI node in NEW_BB for the
!    same PHI_RESULT.  Add an argument to the PHI node in NEW_BB which
!    corresponds to the same PHI argument associated with edge E in BB.  */
  
  static void
! copy_phis_to_block (basic_block new_bb, basic_block bb, edge e)
  {
!   tree phi, arg;
  
!   /* Walk over every PHI in BB.  */
!   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
      {
        tree new_phi;
  
        /* First try to find a PHI node in NEW_BB which has the same
           PHI_RESULT as the PHI from BB we are currently processing.  */
!       for (new_phi = phi_nodes (new_bb); new_phi;
  	   new_phi = PHI_CHAIN (new_phi))
! 	if (PHI_RESULT (new_phi) == PHI_RESULT (phi))
  	  break;
  
        /* If we did not find a suitable PHI in NEW_BB, create one.  */
        if (!new_phi)
! 	new_phi = create_phi_node (PHI_RESULT (phi), new_bb);
! 
!       /* Extract the argument corresponding to E from the current PHI
!          node in BB.  */
!       arg = PHI_ARG_DEF_TREE (phi, phi_arg_from_edge (phi, e));
  
        /* Now add that same argument to the new PHI node in block NEW_BB.  */
        add_phi_arg (&new_phi, arg, e);
      }
  }
  
  /* Remove the last statement in block BB if it is a control statement
--- 95,131 ----
  /* Main data structure to hold information for duplicates of BB.  */
  static varray_type redirection_data;
  
! /* Add to the destination of edge E those PHI arguments queued on
!    E.  */
  
  static void
! copy_phis_to_block (edge e)
  {
!   basic_block dest = e->dest;
!   tree var;
  
!   for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var))
      {
+       tree result = TREE_PURPOSE (var);
+       tree arg = TREE_VALUE (var);
        tree new_phi;
  
        /* First try to find a PHI node in NEW_BB which has the same
           PHI_RESULT as the PHI from BB we are currently processing.  */
!       for (new_phi = phi_nodes (dest); new_phi;
  	   new_phi = PHI_CHAIN (new_phi))
! 	if (PHI_RESULT (new_phi) == result)
  	  break;
  
        /* If we did not find a suitable PHI in NEW_BB, create one.  */
        if (!new_phi)
! 	new_phi = create_phi_node (result, dest);
  
        /* Now add that same argument to the new PHI node in block NEW_BB.  */
        add_phi_arg (&new_phi, arg, e);
      }
+ 
+   PENDING_STMT (e) = NULL;
  }
  
  /* Remove the last statement in block BB if it is a control statement
*************** thread_block (basic_block bb)
*** 363,376 ****
  	  if (rd->outgoing_edge == new_dest && rd->dup_block)
  	    {
  	      edge e2;
- 	      copy_phis_to_block (rd->dup_block, bb, e);
  
  	      if (dump_file && (dump_flags & TDF_DETAILS))
  		fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
  			 e->src->index, e->dest->index, rd->dup_block->index);
  
  	      e2 = redirect_edge_and_branch (e, rd->dup_block);
! 	      PENDING_STMT (e2) = NULL;
  
  	      if ((dump_file && (dump_flags & TDF_DETAILS))
  		  && e->src != e2->src)
--- 362,374 ----
  	  if (rd->outgoing_edge == new_dest && rd->dup_block)
  	    {
  	      edge e2;
  
  	      if (dump_file && (dump_flags & TDF_DETAILS))
  		fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
  			 e->src->index, e->dest->index, rd->dup_block->index);
  
  	      e2 = redirect_edge_and_branch (e, rd->dup_block);
! 	      copy_phis_to_block (e2);
  
  	      if ((dump_file && (dump_flags & TDF_DETAILS))
  		  && e->src != e2->src)