[patch] Fix tree-optimizaation/21430

[Andrew MacLeod <amacleod at redhat dot com>]

This is the patch to resolve the quadratic behaviour of correct_use_link
in certain circumstances. Further reflection of the problem showed that
we don't have to ever check the use links on virtual operands since they
cannot be directly manipulated via the TREE_OPERAND mechanism. They only
exist in the operand cache, so we can be certain they are in the right
list.

This patch provides a much simple routine to make sure virtual operands
have the stmt pointer set as well as belonging to some list. The
original code use to do at least this much work in the best case, and
additional list traversing in other cases. So this should never actually
slow anything down. 

Results for the testcase in this PR are good.  on a 3.0 Ghz P4, the
operands scan time goes from 18.98 seconds to 0.11 seconds.  Similar
results are seen on x86-64, and presumably other targets as well.

cc1-i results are pretty much a wash, although they seem  a hair better
some times.  There are less opportunties for the situation to arise in C
code.

Bootstrapped on i686-pc-linux-gnu and no new test failures. Checked in.

Andrew


2005-09-30  Andrew Macleod  <amacleod@redat.com>

	PR tree-optimization/21430
	* tree-ssa-operands.c (set_virtual_use_link): New. Link new virtual
	use operands, and set stmt pointer if need be.
	(FINALIZE_CORRECT_USE: New. Macro to call appropriate use fixup routine.
	tree-ssa-opfinalize.h (FINALIZE_FUNC): Call FINALIZE_CORRECT_USE if
	present.


Index: tree-ssa-operands.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-operands.c,v
retrieving revision 2.101
diff -c -p -r2.101 tree-ssa-operands.c
*** tree-ssa-operands.c	19 Sep 2005 14:54:24 -0000	2.101
--- tree-ssa-operands.c	26 Sep 2005 20:57:23 -0000
*************** correct_use_link (use_operand_p ptr, tre
*** 511,516 ****
--- 511,534 ----
  }
  
  
+ /* This routine makes sure that PTR is in an immediate use list, and makes
+    sure the stmt pointer is set to the current stmt.  Virtual uses do not need
+    the overhead of correct_use_link since they cannot be directly manipulated
+    like a real use can be.  (They don't exist in the TREE_OPERAND nodes.)  */
+ static inline void
+ set_virtual_use_link (use_operand_p ptr, tree stmt)
+ {
+   /*  Fold_stmt () may have changed the stmt pointers.  */
+   if (ptr->stmt != stmt)
+     ptr->stmt = stmt;
+ 
+   /* If this use isn't in a list, add it to the correct list.  */
+   if (!ptr->prev)
+     link_imm_use (ptr, *(ptr->use));
+ }
+ 
+ 
+ 
  #define FINALIZE_OPBUILD		build_defs
  #define FINALIZE_OPBUILD_BASE(I)	opbuild_elem_real (&build_defs, (I))
  #define FINALIZE_OPBUILD_ELEM(I)	opbuild_elem_real (&build_defs, (I))
*************** finalize_ssa_defs (tree stmt)
*** 553,558 ****
--- 571,577 ----
  #define FINALIZE_ELEM(PTR)	((PTR)->use_ptr.use)
  #define FINALIZE_OPS		USE_OPS
  #define FINALIZE_USE_PTR(PTR)	USE_OP_PTR (PTR)
+ #define FINALIZE_CORRECT_USE	correct_use_link
  #define FINALIZE_BASE(VAR)	VAR
  #define FINALIZE_BASE_TYPE	tree *
  #define FINALIZE_BASE_ZERO	NULL
*************** finalize_ssa_uses (tree stmt)
*** 596,601 ****
--- 615,621 ----
  #define FINALIZE_ELEM(PTR)	MAYDEF_RESULT (PTR)
  #define FINALIZE_OPS		MAYDEF_OPS
  #define FINALIZE_USE_PTR(PTR)	MAYDEF_OP_PTR (PTR)
+ #define FINALIZE_CORRECT_USE	set_virtual_use_link
  #define FINALIZE_BASE_ZERO	0
  #define FINALIZE_BASE(VAR)	((TREE_CODE (VAR) == SSA_NAME)		\
  				? DECL_UID (SSA_NAME_VAR (VAR)) : DECL_UID ((VAR)))
*************** cleanup_v_may_defs (void)
*** 647,652 ****
--- 667,673 ----
  #define FINALIZE_ELEM(PTR)	VUSE_OP (PTR)
  #define FINALIZE_OPS		VUSE_OPS
  #define FINALIZE_USE_PTR(PTR)	VUSE_OP_PTR (PTR)
+ #define FINALIZE_CORRECT_USE	set_virtual_use_link
  #define FINALIZE_BASE_ZERO	0
  #define FINALIZE_BASE(VAR)	((TREE_CODE (VAR) == SSA_NAME)		\
  				? DECL_UID (SSA_NAME_VAR (VAR)) : DECL_UID ((VAR)))
*************** finalize_ssa_vuses (tree stmt)
*** 740,745 ****
--- 761,767 ----
  #define FINALIZE_ELEM(PTR)	MUSTDEF_RESULT (PTR)
  #define FINALIZE_OPS		MUSTDEF_OPS
  #define FINALIZE_USE_PTR(PTR)	MUSTDEF_KILL_PTR (PTR)
+ #define FINALIZE_CORRECT_USE	set_virtual_use_link
  #define FINALIZE_BASE_ZERO	0
  #define FINALIZE_BASE(VAR)	((TREE_CODE (VAR) == SSA_NAME)		\
  				? DECL_UID (SSA_NAME_VAR (VAR)) : DECL_UID ((VAR)))
Index: tree-ssa-opfinalize.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-opfinalize.h,v
retrieving revision 2.3
diff -c -p -r2.3 tree-ssa-opfinalize.h
*** tree-ssa-opfinalize.h	25 Jun 2005 02:01:44 -0000	2.3
--- tree-ssa-opfinalize.h	27 Sep 2005 17:36:55 -0000
*************** FINALIZE_FUNC (tree stmt)
*** 86,93 ****
  	  /* if variables are the same, reuse this node.  */
  	  last->next = old_ops;
  	  last = old_ops;
! #ifdef FINALIZE_USE_PTR
! 	  correct_use_link (FINALIZE_USE_PTR (last), stmt);
  #endif
  	  old_ops = old_ops->next;
  	  new_i = opbuild_next (&FINALIZE_OPBUILD, new_i);
--- 86,93 ----
  	  /* if variables are the same, reuse this node.  */
  	  last->next = old_ops;
  	  last = old_ops;
! #ifdef FINALIZE_CORRECT_USE
! 	  FINALIZE_CORRECT_USE (FINALIZE_USE_PTR (last), stmt);
  #endif
  	  old_ops = old_ops->next;
  	  new_i = opbuild_next (&FINALIZE_OPBUILD, new_i);
*************** FINALIZE_FUNC (tree stmt)
*** 173,175 ****
--- 173,176 ----
  #undef FINALIZE_OPBUILD_ELEM
  #undef FINALIZE_OPBUILD_BASE
  #undef FINALIZE_BASE_ZERO
+ #undef FINALIZE_CORRECT_USE