[tree-ssa] Reduce tree-ssa-dom memory consumption

[law at redhat dot com]

The dominator optimizer notes when certain SSA_NAMEs are known to have a
nonzero value, even if we don't know the SSA_NAME's exact value.

Right now we treat nonzero vars much like the const_and_copies table;
namely it's a virtual array of tree nodes indexed by SSA_NAME representing
their known value.  To unwind the table to a previous state we keep a block
local varray of SSA_NAME, prev_value pairs.  We add a new pair every time we
determine an SSA_NAME has the nonzero property.

That is rather wasteful for tracking the nonzero property of an SSA_NAME.

First, the property really ought to be carried around in a bitmap rather
than a VARRAY since all we need to know is whether or not the SSA_NAME has
the nonzero property or not.

Second, unlike most other properties of SSA_NAMEs, certain _references_ to
the SSA_NAME can create the nonzero property (dereferencing it as a 
pointer).  So we might record an SSA_NAME as having a nonzero value more
than once in a dominator tree, which creates a lot of redundant entries
in the block local varray we use to unwind the state of the global table.
Fixing record_var_is_nonzero to do nothing if we already recorded the
variable as having a nonzero value avoids this sillyness.

Third, when unwinding we now know the value to unwind to will always be
zero, thus we do not need to record pairs in the block local varrays.
Instead we just record the SSA_NAME since the old value is implicitly
known to be zero.


Fixing all those things reduces the total amount of GC allocated memory
by a little over 5M for Gerald's testcase (~1%).  Nothing huge, but hey,
I'll take it.  It also gives a small compile-time performance improvement
as well.  Less than a percent, but again, I'll take it.


Bootstrapped and regression tested on i686-pc-linux-gnu.

	* tree-ssa-dom.c (nonzero_vars): Turn it into a bitmap.
	(tree_ssa_dominator_optimize): Update initialization, clearing and
	freeing of nonzero_vars.
	(restore_nonzero_vars_to_original_value): New function.
	(dom_opt_finalize_block): Use it.
	(record_var_is_nonzero): Only record the variable into the block
	local nonzero vars array if it did not already have a nonzero property.
	(lookup_avail_expr): Lookup the nonzero property of an SSA_NAME with
	a bitmap test.
	
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.150
diff -c -p -r1.1.2.150 tree-ssa-dom.c
*** tree-ssa-dom.c	23 Mar 2004 23:21:07 -0000	1.1.2.150
--- tree-ssa-dom.c	9 Apr 2004 05:25:04 -0000
*************** static varray_type const_and_copies;
*** 73,84 ****
     reaching SSA_NAME node.  */
  static varray_type currdefs;
  
! /* Table of constant values indexed by SSA_NAME.  If the stored value for a
!    particular SSA_NAME is integer_one_node, then that particular SSA_NAME
!    is known to have a nonzero value (even if we do not know its precise
!    value).  Any other value indicates nothing is known about the zero/nonzero
!    status of the given SSA_NAME.  */
! static varray_type nonzero_vars;
  
  /* Track whether or not we have changed the control flow graph.  */
  static bool cfg_altered;
--- 73,81 ----
     reaching SSA_NAME node.  */
  static varray_type currdefs;
  
! /* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
!    know their exact value.  */
! static bitmap nonzero_vars;
  
  /* Track whether or not we have changed the control flow graph.  */
  static bool cfg_altered;
*************** tree_ssa_dominator_optimize (void)
*** 555,561 ****
    false_exprs = htab_create (1024, true_false_expr_hash,
  			     true_false_expr_eq, NULL);
    VARRAY_TREE_INIT (const_and_copies, highest_ssa_version, "const_and_copies");
!   VARRAY_TREE_INIT (nonzero_vars, highest_ssa_version, "nonzero_vars");
    VARRAY_EDGE_INIT (redirection_edges, 20, "redirection_edges");
    VARRAY_GENERIC_PTR_INIT (vrp_data, highest_ssa_version, "vrp_data");
    VARRAY_TREE_INIT (currdefs, num_referenced_vars, "currdefs");
--- 552,558 ----
    false_exprs = htab_create (1024, true_false_expr_hash,
  			     true_false_expr_eq, NULL);
    VARRAY_TREE_INIT (const_and_copies, highest_ssa_version, "const_and_copies");
!   nonzero_vars = BITMAP_XMALLOC ();
    VARRAY_EDGE_INIT (redirection_edges, 20, "redirection_edges");
    VARRAY_GENERIC_PTR_INIT (vrp_data, highest_ssa_version, "vrp_data");
    VARRAY_TREE_INIT (currdefs, num_referenced_vars, "currdefs");
*************** tree_ssa_dominator_optimize (void)
*** 606,612 ****
        htab_empty (false_exprs);
  
        VARRAY_CLEAR (const_and_copies);
!       VARRAY_CLEAR (nonzero_vars);
  
        if (VARRAY_ACTIVE_SIZE (redirection_edges) > 0)
  	redirect_edges_and_update_ssa_graph (redirection_edges);
--- 603,609 ----
        htab_empty (false_exprs);
  
        VARRAY_CLEAR (const_and_copies);
!       bitmap_clear (nonzero_vars);
  
        if (VARRAY_ACTIVE_SIZE (redirection_edges) > 0)
  	redirect_edges_and_update_ssa_graph (redirection_edges);
*************** tree_ssa_dominator_optimize (void)
*** 633,643 ****
  	  bitmap_clear (vars_to_rename);
  	  VARRAY_GROW (const_and_copies, highest_ssa_version);
  	  VARRAY_GROW (vrp_data, highest_ssa_version);
- 	  VARRAY_GROW (nonzero_vars, highest_ssa_version);
  	  VARRAY_GROW (currdefs, num_referenced_vars);
  	  VARRAY_CLEAR (const_and_copies);
  	  VARRAY_CLEAR (vrp_data);
! 	  VARRAY_CLEAR (nonzero_vars);
  	  VARRAY_CLEAR (currdefs);
  	}
      }
--- 630,639 ----
  	  bitmap_clear (vars_to_rename);
  	  VARRAY_GROW (const_and_copies, highest_ssa_version);
  	  VARRAY_GROW (vrp_data, highest_ssa_version);
  	  VARRAY_GROW (currdefs, num_referenced_vars);
  	  VARRAY_CLEAR (const_and_copies);
  	  VARRAY_CLEAR (vrp_data);
! 	  bitmap_clear (nonzero_vars);
  	  VARRAY_CLEAR (currdefs);
  	}
      }
*************** tree_ssa_dominator_optimize (void)
*** 657,662 ****
--- 653,660 ----
    VARRAY_CLEAR (redirection_edges);
    VARRAY_CLEAR (currdefs);
  
+   BITMAP_XFREE (nonzero_vars);
+ 
    /* And finalize the dominator walker.  */
    fini_walk_dominator_tree (&walk_data);
  }
*************** remove_local_expressions_from_table (var
*** 1044,1049 ****
--- 1042,1066 ----
      }
  }
  
+ /* Use the SSA_NAMES in LOCALS to restore TABLE to its original
+    state, stopping when there are LIMIT entires left in LOCALs.  */
+ 
+ static void
+ restore_nonzero_vars_to_original_value (varray_type locals,
+ 					unsigned limit,
+ 					bitmap table)
+ {
+   if (!locals)
+     return;
+ 
+   while (VARRAY_ACTIVE_SIZE (locals) > limit)
+     {
+       tree name = VARRAY_TOP_TREE (locals);
+       VARRAY_POP (locals);
+       bitmap_clear_bit (table, SSA_NAME_VERSION (name));
+     }
+ }
+ 
  /* Use the source/dest pairs in LOCALS to restore TABLE to its original
     state, stopping when there are LIMIT entires left in LOCALs.  */
  
*************** dom_opt_finalize_block (struct dom_walk_
*** 1219,1225 ****
    remove_local_expressions_from_table (bd->true_exprs, 0, true_exprs);
    remove_local_expressions_from_table (bd->false_exprs, 0, false_exprs);
    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);
  
--- 1236,1242 ----
    remove_local_expressions_from_table (bd->true_exprs, 0, true_exprs);
    remove_local_expressions_from_table (bd->false_exprs, 0, false_exprs);
    remove_local_expressions_from_table (bd->avail_exprs, 0, avail_exprs);
!   restore_nonzero_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);
  
*************** htab_statistics (FILE *file, htab_t htab
*** 1497,1516 ****
  }
  
  /* Record the fact that VAR has a nonzero value, though we may not know
!    its exact value.  */
  static void
  record_var_is_nonzero (tree var, varray_type *block_nonzero_vars_p)
  {
!   tree prev_value = get_value_for (var, nonzero_vars);
  
!   set_value_for (var, integer_one_node, nonzero_vars);
  
!   /* Record the destination and its previous value so that we can
!      reset them as we leave this block.  */
    if (! *block_nonzero_vars_p)
      VARRAY_TREE_INIT (*block_nonzero_vars_p, 2, "block_nonzero_vars");
    VARRAY_PUSH_TREE (*block_nonzero_vars_p, var);
-   VARRAY_PUSH_TREE (*block_nonzero_vars_p, prev_value);
  }
  
  /* Enter a statement into the available expression hash table indicating
--- 1514,1538 ----
  }
  
  /* Record the fact that VAR has a nonzero value, though we may not know
!    its exact value.  Note that if VAR is already known to have a nonzero
!    value, then we do nothing.  */
! 
  static void
  record_var_is_nonzero (tree var, varray_type *block_nonzero_vars_p)
  {
!   int indx = SSA_NAME_VERSION (var);
! 
!   if (bitmap_bit_p (nonzero_vars, indx))
!     return;
  
!   /* Mark it in the global table.  */
!   bitmap_set_bit (nonzero_vars, indx);
  
!   /* Record this SSA_NAME so that we can reset the global table
!      when we leave this block.  */
    if (! *block_nonzero_vars_p)
      VARRAY_TREE_INIT (*block_nonzero_vars_p, 2, "block_nonzero_vars");
    VARRAY_PUSH_TREE (*block_nonzero_vars_p, var);
  }
  
  /* Enter a statement into the available expression hash table indicating
*************** lookup_avail_expr (tree stmt, varray_typ
*** 2710,2718 ****
        && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
        && integer_zerop (TREE_OPERAND (rhs, 1)))
      {
!       tree nonzero = get_value_for (TREE_OPERAND (rhs, 0), nonzero_vars);
  
!       if (nonzero && integer_onep (nonzero))
  	{
  	  if (TREE_CODE (rhs) == EQ_EXPR)
  	    return boolean_false_node;
--- 2732,2740 ----
        && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
        && integer_zerop (TREE_OPERAND (rhs, 1)))
      {
!       int indx = SSA_NAME_VERSION (TREE_OPERAND (rhs, 0));
  
!       if (bitmap_bit_p (nonzero_vars, indx))
  	{
  	  if (TREE_CODE (rhs) == EQ_EXPR)
  	    return boolean_false_node;