[tree-ssa] Fix coreutils::csplit miscompilation

[law at redhat dot com]

csplit from GNU coreutils was being mis-compiled by the tree-ssa compiler.

Jump threading has the ability to determine if a statement at the head of
a block is effectively a NOP when the block is reached from a particular
predecessor.  It does this by verifying that the LHS and the simplified
form of the RHS are both SSA_NAMEs which have the same underlying 
variable and the RHS is the current version for that variable.   ie, it
attempts to prove that in normal form such statements will look like
"i = i".

Unfortunately, the code in question was failing to update the current
definition for variables set in PHI nodes and statements we cross at the
start of a basic block.   This can cause the jump threading code to
mistakenly determine that a statement is a NOP leading to incorrect code.

In the specific case of coreutils, we thread across a block containing
an increment of a loop counter.  Thus the loop does not exit and we
get a hang or segfault due to memory allocations occuring within the
loop.  Not good.

This patch adds the two missing register_new_def calls and the code
necessary to unwind those definitions.  At the same time I slightly
simplified register_def_def and its callers to avoid a useless argument
(it can be trivially derived from a different argument).

I have been unable to extract a reasonable testcase for the GCC testsuite.

The fix has been bootstrapped and regression tested on i686-pc-linux-gnu
and also tested to verify that csplit from coreutils functions properly.

	* tree-into-ssa.c (register_new_def): Lose unnecessary VAR argument,
	instead derive VAR from DEF argument.
	(rewrite_initialize_block, rewrite_stmt, rewrite_operand): Corresponding
	changes.
	* tree-ssa-dom.c (register_definitions_for_stmt): Corresponding changes.
	(record_equivalences_from_phis): Likewise.
	(restore_currdefs_to_original_value): New, extracted from ...
	(dom_opt_finalize_block): Use restore_currdefs_to_original_value.
	Restore currdefs after threading across a true edge.
	(thread_across_edge): Register new defintions when we walk through
	a PHI node or real statement.
	* tree-flow.h (register_new_def): Updated.

Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.197
diff -c -p -r1.1.4.197 tree-flow.h
*** tree-flow.h	19 Mar 2004 02:07:25 -0000	1.1.4.197
--- tree-flow.h	23 Mar 2004 22:18:47 -0000
*************** extern bool tree_ssa_useless_type_conver
*** 550,556 ****
  extern bool tree_ssa_useless_type_conversion_1 (tree, tree);
  extern void verify_ssa (void);
  extern void delete_tree_ssa (void);
! extern void register_new_def (tree, tree, varray_type *, varray_type);
  extern void walk_use_def_chains (tree, walk_use_def_chains_fn, void *);
  
  /* In tree-into-ssa.c  */
--- 550,556 ----
  extern bool tree_ssa_useless_type_conversion_1 (tree, tree);
  extern void verify_ssa (void);
  extern void delete_tree_ssa (void);
! extern void register_new_def (tree, varray_type *, varray_type);
  extern void walk_use_def_chains (tree, walk_use_def_chains_fn, void *);
  
  /* In tree-into-ssa.c  */
Index: tree-into-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-into-ssa.c,v
retrieving revision 1.1.2.1
diff -c -p -r1.1.2.1 tree-into-ssa.c
*** tree-into-ssa.c	19 Mar 2004 02:07:25 -0000	1.1.2.1
--- tree-into-ssa.c	23 Mar 2004 22:18:50 -0000
*************** rewrite_initialize_block (struct dom_wal
*** 514,521 ****
      {
        tree result = PHI_RESULT (phi);
  
!       register_new_def (SSA_NAME_VAR (result), result,
! 			&bd->block_defs, currdefs);
      }
  }
  
--- 514,520 ----
      {
        tree result = PHI_RESULT (phi);
  
!       register_new_def (result, &bd->block_defs, currdefs);
      }
  }
  
*************** rewrite_stmt (struct dom_walk_data *walk
*** 780,787 ****
  
        /* FIXME: We shouldn't be registering new defs if the variable
  	 doesn't need to be renamed.  */
!       register_new_def (SSA_NAME_VAR (*def_p), *def_p,
! 			&bd->block_defs, currdefs);
      }
  
    /* Register new virtual definitions made by the statement.  */
--- 779,785 ----
  
        /* FIXME: We shouldn't be registering new defs if the variable
  	 doesn't need to be renamed.  */
!       register_new_def (*def_p, &bd->block_defs, currdefs);
      }
  
    /* Register new virtual definitions made by the statement.  */
*************** rewrite_stmt (struct dom_walk_data *walk
*** 795,802 ****
  
        /* FIXME: We shouldn't be registering new defs if the variable
  	 doesn't need to be renamed.  */
!       register_new_def (SSA_NAME_VAR (VDEF_RESULT (vdefs, i)), 
! 			VDEF_RESULT (vdefs, i), &bd->block_defs, currdefs);
      }
  }
  
--- 793,799 ----
  
        /* FIXME: We shouldn't be registering new defs if the variable
  	 doesn't need to be renamed.  */
!       register_new_def (VDEF_RESULT (vdefs, i), &bd->block_defs, currdefs);
      }
  }
  
*************** rewrite_operand (tree *op_p)
*** 812,825 ****
  }
  
  
! /* Register DEF to be a new definition for variable VAR and push VAR's
!    current reaching definition into the stack pointed by BLOCK_DEFS_P.
!    IS_REAL_OPERAND is true when DEF is a real definition.  */
  
  void
! register_new_def (tree var, tree def,
! 		  varray_type *block_defs_p, varray_type table)
  {
    tree currdef = get_value_for (var, table);
  
    if (! *block_defs_p)
--- 809,822 ----
  }
  
  
! /* Register DEF (an SSA_NAME) to be a new definition for its underlying
!    variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
!    into the stack pointed by BLOCK_DEFS_P.  */
  
  void
! register_new_def (tree def, varray_type *block_defs_p, varray_type table)
  {
+   tree var = SSA_NAME_VAR (def);
    tree currdef = get_value_for (var, table);
  
    if (! *block_defs_p)
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.149
diff -c -p -r1.1.2.149 tree-ssa-dom.c
*** tree-ssa-dom.c	19 Mar 2004 22:46:30 -0000	1.1.2.149
--- tree-ssa-dom.c	23 Mar 2004 22:18:54 -0000
*************** static void remove_local_expressions_fro
*** 254,259 ****
--- 254,262 ----
  static void restore_vars_to_original_value (varray_type locals,
  					    unsigned limit, 
  					    varray_type table);
+ static void restore_currdefs_to_original_value (varray_type locals,
+ 						unsigned limit,
+ 						varray_type table);
  static void register_definitions_for_stmt (tree, varray_type *);
  static void redirect_edges_and_update_ssa_graph (varray_type);
  
*************** thread_across_edge (struct dom_walk_data
*** 700,705 ****
--- 703,709 ----
        tree src = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, e));
        tree dst = PHI_RESULT (phi);
        record_const_or_copy (dst, src, &bd->const_and_copies);
+       register_new_def (dst, &bd->block_defs, currdefs);
      }
  
    for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
*************** thread_across_edge (struct dom_walk_data
*** 814,819 ****
--- 818,824 ----
  	 the result of this statement is used later we can copy propagate
  	 suitably.  */
        record_const_or_copy (lhs, cached_lhs, &bd->const_and_copies);
+       register_new_def (lhs, &bd->block_defs, currdefs);
      }
  
    /* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
*************** restore_vars_to_original_value (varray_t
*** 1063,1068 ****
--- 1068,1104 ----
      }
  }
  
+ /* Similar to restore_vars_to_original_value, except that it restores 
+    CURRDEFS to its original value.  */
+ static void
+ restore_currdefs_to_original_value (varray_type locals,
+ 				    unsigned limit,
+ 				    varray_type table)
+ {
+   if (!locals)
+     return;
+ 
+   /* Restore CURRDEFS to its original state.  */
+   while (VARRAY_ACTIVE_SIZE (locals) > limit)
+     {
+       tree var;
+       tree saved_def = VARRAY_TOP_TREE (locals);
+       VARRAY_POP (locals);
+  
+       /* If SAVED_DEF is NULL, then the next slot in the stack contains
+ 	 the variable associated with SAVED_DEF.  */
+      if (saved_def == NULL_TREE)
+ 	{
+ 	  var = VARRAY_TOP_TREE (locals);
+ 	  VARRAY_POP (locals);
+ 	}
+       else
+ 	var = SSA_NAME_VAR (saved_def);
+ 
+       set_value_for (var, saved_def, table);
+     }
+ }
+ 
  /* We have finished processing the dominator children of BB, perform
     any finalization actions in preparation for leaving this node in
     the dominator tree.  */
*************** dom_opt_finalize_block (struct dom_walk_
*** 1117,1122 ****
--- 1153,1159 ----
  	  unsigned true_limit;
  	  unsigned false_limit;
  	  unsigned const_and_copies_limit;
+ 	  unsigned currdefs_limit;
  
  	  true_limit
  	    = bd->true_exprs ? VARRAY_ACTIVE_SIZE (bd->true_exprs) : 0;
*************** dom_opt_finalize_block (struct dom_walk_
*** 1125,1130 ****
--- 1162,1169 ----
  	  const_and_copies_limit
  	    = bd->const_and_copies ? VARRAY_ACTIVE_SIZE (bd->const_and_copies)
  				   : 0;
+ 	  currdefs_limit
+ 	    = bd->block_defs ? VARRAY_ACTIVE_SIZE (bd->block_defs) : 0;
  
  	  /* Record any equivalences created by following this edge.  */
  	  if (TREE_CODE_CLASS (cond_code) == '<')
*************** dom_opt_finalize_block (struct dom_walk_
*** 1150,1155 ****
--- 1189,1197 ----
  	  restore_vars_to_original_value (bd->const_and_copies,
  					  const_and_copies_limit,
  					  const_and_copies);
+ 	  restore_currdefs_to_original_value (bd->block_defs,
+ 					      currdefs_limit,
+ 					      currdefs);
  	}
  
        /* Similarly for the ELSE arm.  */
*************** dom_opt_finalize_block (struct dom_walk_
*** 1179,1204 ****
    remove_local_expressions_from_table (bd->avail_exprs, 0, avail_exprs);
    restore_vars_to_original_value (bd->nonzero_vars, 0, nonzero_vars);
    restore_vars_to_original_value (bd->const_and_copies, 0, const_and_copies);
! 
!   /* Restore CURRDEFS to its original state.  */
!   while (bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
!     {
!       tree var;
!       tree saved_def = VARRAY_TOP_TREE (bd->block_defs);
!       VARRAY_POP (bd->block_defs);
!  
!       /* If SAVED_DEF is NULL, then the next slot in the stack contains
! 	 the variable associated with SAVED_DEF.  */
!      if (saved_def == NULL_TREE)
! 	{
! 	  var = VARRAY_TOP_TREE (bd->block_defs);
! 	  VARRAY_POP (bd->block_defs);
! 	}
!       else
! 	var = SSA_NAME_VAR (saved_def);
! 
!       set_value_for (var, saved_def, currdefs);
!     }
  
    /* Remove VRP records associated with this basic block.  They are no
       longer valid.
--- 1221,1227 ----
    remove_local_expressions_from_table (bd->avail_exprs, 0, avail_exprs);
    restore_vars_to_original_value (bd->nonzero_vars, 0, nonzero_vars);
    restore_vars_to_original_value (bd->const_and_copies, 0, const_and_copies);
!   restore_currdefs_to_original_value (bd->block_defs, 0, currdefs);
  
    /* Remove VRP records associated with this basic block.  They are no
       longer valid.
*************** record_equivalences_from_phis (struct do
*** 1299,1306 ****
  	  && may_propagate_copy (lhs, rhs))
  	set_value_for (lhs, rhs, const_and_copies);
  
!       register_new_def (SSA_NAME_VAR (PHI_RESULT (phi)), PHI_RESULT (phi),
! 			&bd->block_defs, currdefs);
      }
  }
  
--- 1322,1328 ----
  	  && may_propagate_copy (lhs, rhs))
  	set_value_for (lhs, rhs, const_and_copies);
  
!       register_new_def (lhs, &bd->block_defs, currdefs);
      }
  }
  
*************** register_definitions_for_stmt (tree stmt
*** 3150,3156 ****
  
        /* FIXME: We shouldn't be registering new defs if the variable
  	 doesn't need to be renamed.  */
!       register_new_def (SSA_NAME_VAR (def), def, block_defs_p, currdefs);
      }
  
    /* Register new virtual definitions made by the statement.  */
--- 3172,3178 ----
  
        /* FIXME: We shouldn't be registering new defs if the variable
  	 doesn't need to be renamed.  */
!       register_new_def (def, block_defs_p, currdefs);
      }
  
    /* Register new virtual definitions made by the statement.  */
*************** register_definitions_for_stmt (tree stmt
*** 3159,3166 ****
      {
        /* FIXME: We shouldn't be registering new defs if the variable
  	 doesn't need to be renamed.  */
!       register_new_def (SSA_NAME_VAR (VDEF_RESULT (vdefs, i)),
! 			VDEF_RESULT (vdefs, i), block_defs_p, currdefs);
      }
  }
  
--- 3181,3187 ----
      {
        /* FIXME: We shouldn't be registering new defs if the variable
  	 doesn't need to be renamed.  */
!       register_new_def (VDEF_RESULT (vdefs, i), block_defs_p, currdefs);
      }
  }