[PATCH] Preserve order in cfun->local_decls vector (PR debug/44901)

[Jakub Jelinek]

Hi!

The recent change of cfun->local_decls representation from linked list
to vector caused -fcompare-debug regressions.  The problem is that
expansion cares about the order of vars in cfun->local_decls (which
determines in which order the vars will be expanded in some cases)
and that some vars are only preserved when -g and not when -g0
(this isn't related to VTA btw, the failures are even with
-m32 -O2 -fcompare-debug -fno-var-tracking).  As the removal
of vars from cfun->local_decls is done using VEC_unordered_remove,
the relative order of vars gets out of sync in between -g and -g0 builds
which leads into -fcompare-debug failures.

Fixed by not doing unordered removals, instead moving the vector a single
element at a time after first spot that needs element removal.
We walk the whole vector anyways, this just adds writing of it.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2010-07-12  Jakub Jelinek  <jakub@redhat.com>

	PR debug/44901
	* vec.h (VEC_block_remove): Fix comment.
	* tree-ssa-live.c (remove_unused_locals): Don't use
	VEC_unordered_remove on local_decls, instead replace a single
	vector element in each iteration if at least one element had
	to be removed and VEC_truncate at the end.
	* omp-low.c (expand_omp_taskreg): Likewise.

--- gcc/vec.h.jj	2010-07-07 14:25:51.000000000 +0200
+++ gcc/vec.h	2010-07-12 16:41:27.000000000 +0200
@@ -424,7 +424,7 @@ along with GCC; see the file COPYING3.  
    void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
 
    Remove LEN elements starting at the IXth.  Ordering is retained.
-   This is an O(1) operation.  */
+   This is an O(N) operation due to memmove.  */
 
 #define VEC_block_remove(T,V,I,L)	\
 	(VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO))
--- gcc/tree-ssa-live.c.jj	2010-07-12 09:25:05.000000000 +0200
+++ gcc/tree-ssa-live.c	2010-07-12 17:03:32.000000000 +0200
@@ -689,7 +689,7 @@ remove_unused_locals (void)
   referenced_var_iterator rvi;
   var_ann_t ann;
   bitmap global_unused_vars = NULL;
-  unsigned ix;
+  unsigned srcidx, dstidx, num;
 
   /* Removing declarations from lexical blocks when not optimizing is
      not only a waste of time, it actually causes differences in stack
@@ -756,8 +756,10 @@ remove_unused_locals (void)
   cfun->has_local_explicit_reg_vars = false;
 
   /* Remove unmarked local vars from local_decls.  */
-  for (ix = 0; VEC_iterate (tree, cfun->local_decls, ix, var); )
+  num = VEC_length (tree, cfun->local_decls);
+  for (srcidx = 0, dstidx = 0; srcidx < num; srcidx++)
     {
+      var = VEC_index (tree, cfun->local_decls, srcidx);
       if (TREE_CODE (var) != FUNCTION_DECL
 	  && (!(ann = var_ann (var))
 	      || !ann->used))
@@ -769,18 +771,19 @@ remove_unused_locals (void)
 	      bitmap_set_bit (global_unused_vars, DECL_UID (var));
 	    }
 	  else
-	    {
-	      VEC_unordered_remove (tree, cfun->local_decls, ix);
-	      continue;
-	    }
+	    continue;
 	}
       else if (TREE_CODE (var) == VAR_DECL
 	       && DECL_HARD_REGISTER (var)
 	       && !is_global_var (var))
 	cfun->has_local_explicit_reg_vars = true;
 
-      ix++;
+      if (srcidx != dstidx)
+	VEC_replace (tree, cfun->local_decls, dstidx, var);
+      dstidx++;
     }
+  if (dstidx != num)
+    VEC_truncate (tree, cfun->local_decls, dstidx);
 
   /* Remove unmarked global vars from local_decls.  */
   if (global_unused_vars != NULL)
@@ -794,13 +797,21 @@ remove_unused_locals (void)
 	    && ann->used)
 	  mark_all_vars_used (&DECL_INITIAL (var), global_unused_vars);
 
-      for (ix = 0; VEC_iterate (tree, cfun->local_decls, ix, var); )
-	if (TREE_CODE (var) == VAR_DECL
-	    && is_global_var (var)
-	    && bitmap_bit_p (global_unused_vars, DECL_UID (var)))
-	  VEC_unordered_remove (tree, cfun->local_decls, ix);
-	else
-	  ix++;
+      num = VEC_length (tree, cfun->local_decls);
+      for (srcidx = 0, dstidx = 0; srcidx < num; srcidx++)
+	{
+	  var = VEC_index (tree, cfun->local_decls, srcidx);
+	  if (TREE_CODE (var) == VAR_DECL
+	      && is_global_var (var)
+	      && bitmap_bit_p (global_unused_vars, DECL_UID (var)))
+	    continue;
+
+	  if (srcidx != dstidx)
+	    VEC_replace (tree, cfun->local_decls, dstidx, var);
+	  dstidx++;
+	}
+      if (dstidx != num)
+	VEC_truncate (tree, cfun->local_decls, dstidx);
       BITMAP_FREE (global_unused_vars);
     }
 
--- gcc/omp-low.c.jj	2010-07-07 14:25:51.000000000 +0200
+++ gcc/omp-low.c	2010-07-12 17:07:25.000000000 +0200
@@ -3378,7 +3378,7 @@ expand_omp_taskreg (struct omp_region *r
     }
   else
     {
-      unsigned ix;
+      unsigned srcidx, dstidx, num;
 
       /* If the parallel region needs data sent from the parent
 	 function, then the very first statement (except possible
@@ -3515,11 +3515,18 @@ expand_omp_taskreg (struct omp_region *r
 	single_succ_edge (new_bb)->flags = EDGE_FALLTHRU;
 
       /* Remove non-local VAR_DECLs from child_cfun->local_decls list.  */
-      for (ix = 0; VEC_iterate (tree, child_cfun->local_decls, ix, t); )
-	if (DECL_CONTEXT (t) != cfun->decl)
-	  ix++;
-	else
-	  VEC_unordered_remove (tree, child_cfun->local_decls, ix);
+      num = VEC_length (tree, child_cfun->local_decls);
+      for (srcidx = 0, dstidx = 0; srcidx < num; srcidx++)
+	{
+	  t = VEC_index (tree, child_cfun->local_decls, srcidx);
+	  if (DECL_CONTEXT (t) == cfun->decl)
+	    continue;
+	  if (srcidx != dstidx)
+	    VEC_replace (tree, child_cfun->local_decls, dstidx, t);
+	  dstidx++;
+	}
+      if (dstidx != num)
+	VEC_truncate (tree, child_cfun->local_decls, dstidx);
 
       /* Inform the callgraph about the new function.  */
       DECL_STRUCT_FUNCTION (child_fn)->curr_properties

	Jakub