re PR tree-optimization/34683 (SSA rewriting in the loop unroller causes quadratic behavior)

2008-01-08  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/34683
	* tree-ssa-operands.c (operand_build_cmp): Export.
	* tree-ssa-operands.h (operand_build_cmp): Declare.
	* tree-vn.c (vuses_compare): Remove.
	(sort_vuses): Use operand_build_cmp.
	(sort_vuses_heap): Likewise.
	* tree-ssa-sccvn.c (vuses_to_vec): Use VEC_reserve, not VEC_alloc
	to re-use old VEC if available.  Do not sort already sorted VUSEs.
	(vdefs_to_vec): Do not sort already sorted VDEFs.

From-SVN: r131400

5 files changed, 18 insertions, 23 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 26d9093..3bf8fb1 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,15 @@
+2008-01-08  Richard Guenther  <rguenther@suse.de>
+
+	PR tree-optimization/34683
+	* tree-ssa-operands.c (operand_build_cmp): Export.
+	* tree-ssa-operands.h (operand_build_cmp): Declare.
+	* tree-vn.c (vuses_compare): Remove.
+	(sort_vuses): Use operand_build_cmp.
+	(sort_vuses_heap): Likewise.
+	* tree-ssa-sccvn.c (vuses_to_vec): Use VEC_reserve, not VEC_alloc
+	to re-use old VEC if available.  Do not sort already sorted VUSEs.
+	(vdefs_to_vec): Do not sort already sorted VDEFs.
+
 2008-01-08  Jakub Jelinek  <jakub@redhat.com>
 
 	PR middle-end/34694
diff --git a/gcc/tree-ssa-operands.c b/gcc/tree-ssa-operands.c
index 116877d..ceb18ba 100644
--- a/gcc/tree-ssa-operands.c
+++ b/gcc/tree-ssa-operands.c
@@ -210,7 +210,7 @@ get_name_decl (const_tree t)
 
 /* Comparison function for qsort used in operand_build_sort_virtual.  */
 
-static int
+int
 operand_build_cmp (const void *p, const void *q)
 {
   const_tree const e1 = *((const_tree const *)p);
diff --git a/gcc/tree-ssa-operands.h b/gcc/tree-ssa-operands.h
index f48245f..ba9793d 100644
--- a/gcc/tree-ssa-operands.h
+++ b/gcc/tree-ssa-operands.h
@@ -210,6 +210,7 @@ extern void free_stmt_operands (tree);
 extern bool verify_imm_links (FILE *f, tree var);
 
 extern void copy_virtual_operands (tree, tree);
+extern int operand_build_cmp (const void *, const void *);
 extern void create_ssa_artificial_load_stmt (tree, tree, bool);
 
 extern void dump_immediate_uses (FILE *file);
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 035c811..e1d4af1 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -389,13 +389,11 @@ vuses_to_vec (tree stmt, VEC (tree, gc) **result)
   if (!stmt)
     return;
 
-  *result = VEC_alloc (tree, gc, num_ssa_operands (stmt, SSA_OP_VIRTUAL_USES));
+  VEC_reserve_exact (tree, gc, *result,
+		     num_ssa_operands (stmt, SSA_OP_VIRTUAL_USES));
 
   FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES)
     VEC_quick_push (tree, *result, vuse);
-
-  if (VEC_length (tree, *result) > 1)
-    sort_vuses (*result);
 }
 
 
@@ -427,9 +425,6 @@ vdefs_to_vec (tree stmt, VEC (tree, gc) **result)
 
   FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, iter, SSA_OP_VIRTUAL_DEFS)
     VEC_quick_push (tree, *result, vdef);
-
-  if (VEC_length (tree, *result) > 1)
-    sort_vuses (*result);
 }
 
 /* Copy the names of vdef results in STMT into a vector, and return
diff --git a/gcc/tree-vn.c b/gcc/tree-vn.c
index a23d7be..0c5061f 100644
--- a/gcc/tree-vn.c
+++ b/gcc/tree-vn.c
@@ -107,19 +107,6 @@ set_value_handle (tree e, tree v)
     gcc_assert (is_gimple_min_invariant (e));
 }
 
-/* A comparison function for use in qsort to compare vuses.  Simply
-   subtracts version numbers.  */
-
-static int
-vuses_compare (const void *pa, const void *pb)
-{
-  const tree vusea = *((const tree *)pa);
-  const tree vuseb = *((const tree *)pb);
-  int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
-
-  return sn;
-}
-
 /* Print out the "Created value <x> for <Y>" statement to the
    dump_file.
    This is factored because both versions of lookup use it, and it
@@ -161,7 +148,7 @@ sort_vuses (VEC (tree,gc) *vuses)
     qsort (VEC_address (tree, vuses),
 	   VEC_length (tree, vuses),
 	   sizeof (tree),
-	   vuses_compare);
+	   operand_build_cmp);
 }
 
 /* Sort the VUSE array so that we can do equality comparisons
@@ -174,7 +161,7 @@ sort_vuses_heap (VEC (tree,heap) *vuses)
     qsort (VEC_address (tree, vuses),
 	   VEC_length (tree, vuses),
 	   sizeof (tree),
-	   vuses_compare);
+	   operand_build_cmp);
 }
 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
    EXPR to the value set for value VAL.  */