tweak to immediate uses

[Andrew MacLeod <amacleod at redhat dot com>]

The following patch removes a linear linked list search from
correct_use_link, and replaces it with something that is usually much
shorter.

Due to the fact that we allow direct tree manipulations, whenever we
rebuild an operand list, we have to check to make sure the underlying
tree node wasn't changed (ick), resulting in a use node now being in the
wrong immediate use list.

Previously, we scanned all the way back to the root node in order to be
sure we are in the right list.  Simply checking the previous node in the
list wasn't enough because the previous node may have been a use in the
same stmt, and may also have been changed.

So, now what we do is scan for a previous node in the list whose stmt is
up to date, or the root, whichever comes first.  If we have the same
tree value as that node, then we are in the right list.

Pretty marginal differences most places. User time isnt much difference,
minor drops in total time a few places.

Primarily this became an issue for dnovillos TCB changes.  We end up
with *much* longer use lists, and the time spent in this linear search
was dramatic some times.  

bootstrapped on i686-pc-linux-gnu with no new testsuite regression.

I've checked it in.

Andrew

	* tree-ssa-operands.c (correct_use_link): Remove linear scan.

Index: tree-ssa-operands.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-operands.c,v
retrieving revision 2.73
diff -c -p -r2.73 tree-ssa-operands.c
*** tree-ssa-operands.c	6 Apr 2005 17:05:03 -0000	2.73
--- tree-ssa-operands.c	8 Apr 2005 12:48:59 -0000
*************** finalize_ssa_defs (def_optype *old_ops_p
*** 456,462 ****
     changed what this pointer points to via TREE_OPERANDS (exp, 0) = <...>.
     THe contents are different, but the the pointer is still the same.  This
     routine will check to make sure PTR is in the correct list, and if it isn't
!    put it in the correct list.  */
  
  static inline void
  correct_use_link (ssa_imm_use_t *ptr, tree stmt)
--- 456,463 ----
     changed what this pointer points to via TREE_OPERANDS (exp, 0) = <...>.
     THe contents are different, but the the pointer is still the same.  This
     routine will check to make sure PTR is in the correct list, and if it isn't
!    put it in the correct list.  We cannot simply check the previous node 
!    because all nodes in the same stmt might have be changed.  */
  
  static inline void
  correct_use_link (ssa_imm_use_t *ptr, tree stmt)
*************** correct_use_link (ssa_imm_use_t *ptr, tr
*** 471,480 ****
    prev = ptr->prev;
    if (prev)
      {
!       /* find the root, which has a non-NULL stmt, and a NULL use.  */
!       while (prev->stmt == NULL || prev->use != NULL)
!         prev = prev->prev;
!       root = prev->stmt;
        if (root == *(ptr->use))
  	return;
      }
--- 472,499 ----
    prev = ptr->prev;
    if (prev)
      {
!       bool stmt_mod = true;
!       /* Find the first element which isn't a SAFE iterator, is in a sifferent
! 	 stmt, and is not a a modified stmt,  That node is in the correct list,
! 	 see if we are too.  */
! 
!       while (stmt_mod)
! 	{
! 	  while (prev->stmt == stmt || prev->stmt == NULL)
! 	    prev = prev->prev;
! 	  if (prev->use == NULL)
! 	    stmt_mod = false;
! 	  else
! 	    if ((stmt_mod = stmt_modified_p (prev->stmt)))
! 	      prev = prev->prev;
! 	}
! 
!       /* Get the ssa_name of the list the node is in.  */
!       if (prev->use == NULL)
! 	root = prev->stmt;
!       else
! 	root = *(prev->use);
!       /* If its the right list, simply return.  */
        if (root == *(ptr->use))
  	return;
      }