This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[tree-ssa] Further memory usage reductions



As discussed yesterday, the dominator optimizer is generating an amazing
number of temporary tree nodes due to the design of its main hash table.

Consider

if (a > 24)
  {
    ...
  }

When we walk down into the TRUE arm of that if statement, we want to record
the fact that a has a value > 24.  Due to the nature of the our hash table
we actually have to generate a statement as well as an annotation for that
statement.  Yuk.  Worse yet, we have to do it twice (once for the main
expresion, then again for its inverse).  Double yuk.

Revamping this code wasn't terribly difficult.  We keep the main hash
table, but we have two additional new hash tables.  One for expressions
which are known to produce a true result, the other for expressions which
are known to produce a false result.  Thus we avoid generation of all those
useless MODIFY_EXPRs.  Basically it's a specialized form of the 
avail_exprs hash table.


The second way the dominator optimizer wastes memory is for equivalences
created by memory operations.  ie


  *p = whatever


When we encounter a statement like that, we want to record the fact that
"p" has a nonzero value, even though we don't know its precise value.

Previously we had to first generate a conditional such as

  p != 0

Then we had to put it into a statement like this

1 = (p != 0)

[ That way if we tried to lookup p != 0, we'd get the result "1". ]

So we were generating a ton of EQ_EXPR and NE_EXPR nodes along with their
associated MODIFY_EXPRs and statement annotations.  Egad.  And of course,
we had to do the inverse function as well 0 = (p == 0).

We could handle this using the true/false expression table -- but that
would not allow us to kill the useless EQ_EXPR and NE_EXPR nodes.  Having
a separate varray  to indicate if a var has a nonzero value is an easy
way to solve this problem.  It's roughly analogous to how we handle
const_and_copies.


The net result is we save another 20M or something like that for Gerald's
favorite PR.  We get excellent savings in the other files I've examined
as well.  Compile time across the components of cc1 is unchanged.

These changes shouldn't affect code generation at all.  So I was rather
shocked when they did :(  It turns out that there is a bug in my 11-18
change to the dominator optimizer which would allow an expression to stay
in the hash tables after we left the dominator tree.  After fixing that
bug, the code generated before and after the memory improvements is the
same.

I'll note that the dominator optimizer is probably sucking up a lot of
memory in GC'd varrays.  I expect to work on that shortly.

Bootstrapped and regression tested.  Whee.


	* tree-ssa-dom.c (true_exprs, false_exprs): New hash tables.
	(nonzero_vars): New varray.
	(dom_walk_block_data): Add true_exprs, false_exprs and nonzero_vars.
	(get_value_for, set_value_for): Accept additional argument indicating
	which table to use.  Callers updated.
	(tree_ssa_dominator_optimize_1): Initialize and wipe our new hash
	tables and varray appropriately.
	(dom_opt_initialize_block): Initialize new block local varrays for
	true expressions, false expressions and nonzero vars.  Update call
	to record_equivalences_from_incoming_edge.
	(dom_opt_finalize_block): Put equivalences from taken edges
	into the true_exprs and false_exprs hash tables.  Restore global
	state for true_exprs, false_exprs and nonzero_vars  too.
	(record_equivalences_from_incoming_edge): Accept dom_walk structure
	instead of a gazillion varrays.  Pass down block local
	true_exprs, false_exprs and nonzero_vars varrays to various children.
	(optimize_stmt):  Accept block local nonzero_vars argument.  Pass
	new varrays down to record_equivalences_from_stmt.
	(thread_jumps_walk_stmt): Pass new varrays down to 
	record_equivalences_from_stmt.
	(dom_opt_walk_stmt): Pass new varrays down to optimize_stmt.
	(dump_dominator_optimizer_statistics): Dump new hash tables.
	(record_cond_is_true, record_cond_is_false): Record info into
	the true/false hash tables/varrays instead of the main expression
	varrays.  Don't create useless tree nodes.
	(record_var_is_nonzero): New function.
	(record_equivalences_from_stmt): Don't generate useless tree nodes.
	(lookup_avail_expr): Consult nonzero_vars and the true/false
	expression tables as well.
	(get_eq_expr_value): Record local true/false expressions in the
	local true/false varrays rather than the main local expression
	varray.
	(true_false_expr_hash, true_false_expr_eq): New functions.
	

Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.80
diff -c -3 -p -r1.1.2.80 tree-ssa-dom.c
*** tree-ssa-dom.c	19 Nov 2003 20:10:01 -0000	1.1.2.80
--- tree-ssa-dom.c	20 Nov 2003 00:42:08 -0000
*************** static int dump_flags;
*** 52,57 ****
--- 52,63 ----
     global redundancy elimination). */
  static htab_t avail_exprs;
  
+ /* Hash table of expressions known to be either true or false.  This
+    is primarily used to track the results of conditionals as we walk
+    down the dominator tree.  */
+ static htab_t true_exprs;
+ static htab_t false_exprs;
+ 
  /* Table of constant values and copies indexed by SSA name.  When the
     renaming pass finds an assignment of a constant (X_i = C) or a copy
     assignment from another SSA variable (X_i = Y_j), it creates a mapping
*************** static htab_t avail_exprs;
*** 62,67 ****
--- 68,80 ----
     propagation).  */
  static varray_type const_and_copies;
  
+ /* 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;
  
*************** struct dom_walk_block_data
*** 157,166 ****
--- 170,187 ----
       table.  */
    varray_type avail_exprs;
  
+   /* Similarly for expressions known to have a true or false value.  */
+   varray_type true_exprs;
+   varray_type false_exprs;
+ 
    /* Array of dest, src pairs that need to be restored during finalization
       into the global const/copies table during finalization.  */
    varray_type const_and_copies;
  
+   /* Similarly for the nonzero state of variables that needs to be
+      restored during finalization.  */
+   varray_type nonzero_vars;
+ 
    /* Array of statements we need to rescan during finalization for newly
       exposed variables.  */
    varray_type stmts_to_rescan;
*************** struct dom_walk_block_data
*** 172,185 ****
  };
  
  /* Local functions.  */
! static bool optimize_stmt (block_stmt_iterator, varray_type *);
! static inline tree get_value_for (tree);
! static inline void set_value_for (tree, tree);
  static tree lookup_avail_expr (tree, varray_type *, bool);
! static tree get_eq_expr_value (tree, int, varray_type *,
  			       basic_block, varray_type *);
  static hashval_t avail_expr_hash (const void *);
  static int avail_expr_eq (const void *, const void *);
  static void htab_statistics (FILE *, htab_t);
  static void record_cond_is_false (tree, varray_type *);
  static void record_cond_is_true (tree, varray_type *);
--- 193,208 ----
  };
  
  /* Local functions.  */
! static bool optimize_stmt (block_stmt_iterator, varray_type *, varray_type 
*);
! static inline tree get_value_for (tree, varray_type table);
! static inline void set_value_for (tree, tree, varray_type table);
  static tree lookup_avail_expr (tree, varray_type *, bool);
! static tree get_eq_expr_value (tree, int, varray_type *, varray_type *,
  			       basic_block, varray_type *);
  static hashval_t avail_expr_hash (const void *);
  static int avail_expr_eq (const void *, const void *);
+ static hashval_t true_false_expr_hash (const void *);
+ static int true_false_expr_eq (const void *, const void *);
  static void htab_statistics (FILE *, htab_t);
  static void record_cond_is_false (tree, varray_type *);
  static void record_cond_is_true (tree, varray_type *);
*************** static void record_range (tree, basic_bl
*** 194,205 ****
  static bool extract_range_from_cond (tree, tree *, tree *, int *);
  static bool cprop_into_stmt (tree);
  static void record_equivalences_from_phis (basic_block);
! static void record_equivalences_from_incoming_edge (basic_block, tree,
! 						    varray_type *,
! 						    varray_type *,
! 						    varray_type *);
  static bool eliminate_redundant_computations (tree, varray_type *, 
stmt_ann_t);
! static void record_equivalences_from_stmt (tree, varray_type *,
  					   int, stmt_ann_t);
  static void thread_across_edge (edge);
  static void dom_opt_finalize_block (struct dom_walk_data *, basic_block, 
tree);
--- 217,226 ----
  static bool extract_range_from_cond (tree, tree *, tree *, int *);
  static bool cprop_into_stmt (tree);
  static void record_equivalences_from_phis (basic_block);
! static void record_equivalences_from_incoming_edge (struct dom_walk_data *,
! 						    basic_block, tree);
  static bool eliminate_redundant_computations (tree, varray_type *, 
stmt_ann_t);
! static void record_equivalences_from_stmt (tree, varray_type *, varray_type 
*,
  					   int, stmt_ann_t);
  static void thread_across_edge (edge);
  static void dom_opt_finalize_block (struct dom_walk_data *, basic_block, 
tree);
*************** static void thread_jumps_walk_stmts (str
*** 214,235 ****
  /* Return the value associated with variable VAR in TABLE.  */
  
  static inline tree
! get_value_for (tree var)
  {
!   return VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (var));
  }
  
  
  /* Associate VALUE to variable VAR in TABLE.  */
  
  static inline void
! set_value_for (tree var, tree value)
  {
!   VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (var)) = value;
  }
  
- 
- 
  /* Thread jumps in FNDECL based on equivalences created by walking the
     dominator tree.
  
--- 235,254 ----
  /* Return the value associated with variable VAR in TABLE.  */
  
  static inline tree
! get_value_for (tree var, varray_type table)
  {
!   return VARRAY_TREE (table, SSA_NAME_VERSION (var));
  }
  
  
  /* Associate VALUE to variable VAR in TABLE.  */
  
  static inline void
! set_value_for (tree var, tree value, varray_type table)
  {
!   VARRAY_TREE (table, SSA_NAME_VERSION (var)) = value;
  }
  
  /* Thread jumps in FNDECL based on equivalences created by walking the
     dominator tree.
  
*************** tree_ssa_dominator_optimize_1 (tree fnde
*** 321,327 ****
--- 340,351 ----
  
    /* Create our hash tables.  */
    avail_exprs = htab_create (1024, avail_expr_hash, avail_expr_eq, NULL);
+   true_exprs = htab_create (1024, true_false_expr_hash,
+ 			    true_false_expr_eq, NULL);
+   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 (edges_to_redirect, 20, "edges_to_redirect");
    VARRAY_BB_INIT (redirection_targets, 20, "redirection_targets");
    VARRAY_GENERIC_PTR_INIT (vrp_data, highest_ssa_version, "vrp_data");
*************** tree_ssa_dominator_optimize_1 (tree fnde
*** 389,396 ****
--- 413,423 ----
  
        /* Wipe the hash tables.  */
        htab_empty (avail_exprs);
+       htab_empty (true_exprs);
+       htab_empty (false_exprs);
  
        VARRAY_CLEAR (const_and_copies);
+       VARRAY_CLEAR (nonzero_vars);
  
        /* If some edges were threaded in this iteration, then perform
  	 the required redirections and recompute the dominators.  */
*************** tree_ssa_dominator_optimize_1 (tree fnde
*** 458,465 ****
--- 485,494 ----
  	  sbitmap_zero (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_CLEAR (const_and_copies);
  	  VARRAY_CLEAR (vrp_data);
+ 	  VARRAY_CLEAR (nonzero_vars);
  	}
      }
    while (cfg_altered);
*************** tree_ssa_dominator_optimize_1 (tree fnde
*** 477,482 ****
--- 506,513 ----
      }
  
    htab_delete (avail_exprs);
+   htab_delete (true_exprs);
+   htab_delete (false_exprs);
  
    VARRAY_FREE (edges_to_redirect);
    VARRAY_FREE (redirection_targets);
*************** dom_opt_initialize_block (struct dom_wal
*** 592,613 ****
       block.  */
    bd = ggc_alloc (sizeof (struct dom_walk_block_data));
    VARRAY_TREE_INIT (bd->avail_exprs, 20, "block_avail_exprs");
    VARRAY_TREE_INIT (bd->const_and_copies, 2, "block_const_and_copies");
    VARRAY_TREE_INIT (bd->stmts_to_rescan, 20, "stmts_to_rescan");
    VARRAY_TREE_INIT (bd->vrp_variables, 2, "vrp_variables");
  
    /* Push this block record onto the stack of block records.  */
    VARRAY_PUSH_GENERIC_PTR (walk_data->block_data_stack, bd);
  
!   record_equivalences_from_incoming_edge (bb,
! 					  parent_block_last_stmt,
! 					  &bd->avail_exprs,
! 					  &bd->const_and_copies,
! 					  &bd->vrp_variables);
  
    /* PHI nodes can create equivalences too.  */
    record_equivalences_from_phis (bb);
  }
  /* We have finished processing the dominator children of BB, perform
     any finalization actions in preparation for leaving this node in
     the dominator tree.  */
--- 623,645 ----
       block.  */
    bd = ggc_alloc (sizeof (struct dom_walk_block_data));
    VARRAY_TREE_INIT (bd->avail_exprs, 20, "block_avail_exprs");
+   VARRAY_TREE_INIT (bd->true_exprs, 2, "block_true_exprs");
+   VARRAY_TREE_INIT (bd->false_exprs, 2, "block_false_exprs");
    VARRAY_TREE_INIT (bd->const_and_copies, 2, "block_const_and_copies");
+   VARRAY_TREE_INIT (bd->nonzero_vars, 2, "block_nonzero_vars");
    VARRAY_TREE_INIT (bd->stmts_to_rescan, 20, "stmts_to_rescan");
    VARRAY_TREE_INIT (bd->vrp_variables, 2, "vrp_variables");
  
    /* Push this block record onto the stack of block records.  */
    VARRAY_PUSH_GENERIC_PTR (walk_data->block_data_stack, bd);
  
!   record_equivalences_from_incoming_edge (walk_data, bb,
! 					  parent_block_last_stmt);
  
    /* PHI nodes can create equivalences too.  */
    record_equivalences_from_phis (bb);
  }
+ 
  /* 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_
*** 620,626 ****
--- 652,661 ----
    struct dom_walk_block_data *bd
      = (struct dom_walk_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->
block_data_stack);
    varray_type block_avail_exprs = bd->avail_exprs;
+   varray_type block_true_exprs = bd->true_exprs;
+   varray_type block_false_exprs = bd->false_exprs;
    varray_type block_const_and_copies = bd->const_and_copies;
+   varray_type block_nonzero_vars = bd->nonzero_vars;
    varray_type vrp_variables = bd->vrp_variables;
    varray_type stmts_to_rescan = bd->stmts_to_rescan;
    tree last;
*************** dom_opt_finalize_block (struct dom_walk_
*** 669,682 ****
        if (! dom_children (bb)
  	  || ! bitmap_bit_p (dom_children (bb), true_edge->dest->index))
  	{
! 	  unsigned limit = VARRAY_ACTIVE_SIZE (bd->avail_exprs);
! 	  record_cond_is_true (cond, &bd->avail_exprs);
! 	  record_cond_is_false (inverted, &bd->avail_exprs);
  	  thread_across_edge (true_edge);
! 	  if (limit != VARRAY_ACTIVE_SIZE (bd->avail_exprs))
  	    {
! 	      htab_remove_elt (avail_exprs, VARRAY_TOP_TREE (bd->avail_exprs));
! 	      VARRAY_POP (bd->avail_exprs);
  	    }
  	}
  
--- 704,723 ----
        if (! dom_children (bb)
  	  || ! bitmap_bit_p (dom_children (bb), true_edge->dest->index))
  	{
! 	  unsigned true_limit = VARRAY_ACTIVE_SIZE (bd->true_exprs);
! 	  unsigned false_limit = VARRAY_ACTIVE_SIZE (bd->true_exprs);
! 	  record_cond_is_true (cond, &bd->true_exprs);
! 	  record_cond_is_false (inverted, &bd->false_exprs);
  	  thread_across_edge (true_edge);
! 	  if (true_limit != VARRAY_ACTIVE_SIZE (bd->true_exprs))
  	    {
! 	      htab_remove_elt (true_exprs, VARRAY_TOP_TREE (bd->true_exprs));
! 	      VARRAY_POP (bd->true_exprs);
! 	    }
! 	  if (false_limit != VARRAY_ACTIVE_SIZE (bd->false_exprs))
! 	    {
! 	      htab_remove_elt (false_exprs, VARRAY_TOP_TREE (bd->false_exprs));
! 	      VARRAY_POP (bd->false_exprs);
  	    }
  	}
  
*************** dom_opt_finalize_block (struct dom_walk_
*** 684,702 ****
        if (! dom_children (bb)
  	  || ! bitmap_bit_p (dom_children (bb), false_edge->dest->index))
  	{
! 	  unsigned limit = VARRAY_ACTIVE_SIZE (bd->avail_exprs);
! 	  record_cond_is_false (cond, &bd->avail_exprs);
! 	  record_cond_is_true (inverted, &bd->avail_exprs);
  	  thread_across_edge (false_edge);
! 	  if (limit != VARRAY_ACTIVE_SIZE (bd->avail_exprs))
  	    {
! 	      htab_remove_elt (avail_exprs, VARRAY_TOP_TREE (bd->avail_exprs));
! 	      VARRAY_POP (bd->avail_exprs);
  	    }
  	}
      }
  
    /* Remove all the expressions made available in this block.  */
    while (VARRAY_ACTIVE_SIZE (block_avail_exprs) > 0)
      {
        tree stmt = VARRAY_TOP_TREE (block_avail_exprs);
--- 725,763 ----
        if (! dom_children (bb)
  	  || ! bitmap_bit_p (dom_children (bb), false_edge->dest->index))
  	{
! 	  unsigned true_limit = VARRAY_ACTIVE_SIZE (bd->true_exprs);
! 	  unsigned false_limit = VARRAY_ACTIVE_SIZE (bd->false_exprs);
! 	  record_cond_is_false (cond, &bd->false_exprs);
! 	  record_cond_is_true (inverted, &bd->true_exprs);
  	  thread_across_edge (false_edge);
! 	  if (true_limit != VARRAY_ACTIVE_SIZE (bd->true_exprs))
! 	    {
! 	      htab_remove_elt (true_exprs, VARRAY_TOP_TREE (bd->true_exprs));
! 	      VARRAY_POP (bd->true_exprs);
! 	    }
! 	  if (false_limit != VARRAY_ACTIVE_SIZE (bd->false_exprs))
  	    {
! 	      htab_remove_elt (false_exprs, VARRAY_TOP_TREE (bd->false_exprs));
! 	      VARRAY_POP (bd->false_exprs);
  	    }
  	}
      }
  
    /* Remove all the expressions made available in this block.  */
+   while (VARRAY_ACTIVE_SIZE (block_true_exprs) > 0)
+     {
+       tree cond = VARRAY_TOP_TREE (block_true_exprs);
+       VARRAY_POP (block_true_exprs);
+       htab_remove_elt (true_exprs, cond);
+     }
+ 
+   while (VARRAY_ACTIVE_SIZE (block_false_exprs) > 0)
+     {
+       tree cond = VARRAY_TOP_TREE (block_false_exprs);
+       VARRAY_POP (block_false_exprs);
+       htab_remove_elt (false_exprs, cond);
+     }
+ 
    while (VARRAY_ACTIVE_SIZE (block_avail_exprs) > 0)
      {
        tree stmt = VARRAY_TOP_TREE (block_avail_exprs);
*************** dom_opt_finalize_block (struct dom_walk_
*** 714,720 ****
        dest = VARRAY_TOP_TREE (block_const_and_copies);
        VARRAY_POP (block_const_and_copies);
  
!       set_value_for (dest, prev_value);
      }
  
    /* Remove VRP records associated with this basic block.  They are no
--- 775,794 ----
        dest = VARRAY_TOP_TREE (block_const_and_copies);
        VARRAY_POP (block_const_and_copies);
  
!       set_value_for (dest, prev_value, const_and_copies);
!     }
! 
!   /* Also remove block local expressions which created nonzero values.  */
!   while (VARRAY_ACTIVE_SIZE (block_nonzero_vars) > 0)
!     {
!       tree prev_value, dest;
! 
!       prev_value = VARRAY_TOP_TREE (block_nonzero_vars);
!       VARRAY_POP (block_nonzero_vars);
!       dest = VARRAY_TOP_TREE (block_nonzero_vars);
!       VARRAY_POP (block_nonzero_vars);
! 
!       set_value_for (dest, prev_value, nonzero_vars);
      }
  
    /* Remove VRP records associated with this basic block.  They are no
*************** record_equivalences_from_phis (basic_blo
*** 812,818 ****
  	 a useful equivalence.  */
        if (i == PHI_NUM_ARGS (phi)
  	  && may_propagate_copy (lhs, rhs))
! 	set_value_for (lhs, rhs);
      }
  }
  
--- 886,892 ----
  	 a useful equivalence.  */
        if (i == PHI_NUM_ARGS (phi)
  	  && may_propagate_copy (lhs, rhs))
! 	set_value_for (lhs, rhs, const_and_copies);
      }
  }
  
*************** record_equivalences_from_phis (basic_blo
*** 820,833 ****
     has more than one incoming edge, then no equivalence is created.  */
  
  static void
! record_equivalences_from_incoming_edge (basic_block bb,
! 					tree parent_block_last_stmt,
! 					varray_type *block_avail_exprs_p,
! 					varray_type *block_const_and_copies_p,
! 					varray_type *vrp_variables_p)
  {
    int edge_flags;
    tree eq_expr_value = NULL_TREE;
  
    /* If we have a single predecessor, then extract EDGE_FLAGS from
       our single incoming edge.  Otherwise clear EDGE_FLAGS and
--- 894,907 ----
     has more than one incoming edge, then no equivalence is created.  */
  
  static void
! record_equivalences_from_incoming_edge (struct dom_walk_data *walk_data,
! 					basic_block bb,
! 					tree parent_block_last_stmt)
  {
    int edge_flags;
    tree eq_expr_value = NULL_TREE;
+   struct dom_walk_block_data *bd
+     = (struct dom_walk_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->
block_data_stack);
  
    /* If we have a single predecessor, then extract EDGE_FLAGS from
       our single incoming edge.  Otherwise clear EDGE_FLAGS and
*************** record_equivalences_from_incoming_edge (
*** 862,870 ****
        && (edge_flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
      eq_expr_value = get_eq_expr_value (parent_block_last_stmt,
  				       (edge_flags & EDGE_TRUE_VALUE) != 0,
! 				       block_avail_exprs_p,
  				       bb,
! 				       vrp_variables_p);
    /* Similarly when the parent block ended in a SWITCH_EXPR.  */
    else if (parent_block_last_stmt
  	   && bb->pred->pred_next == NULL
--- 936,945 ----
        && (edge_flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
      eq_expr_value = get_eq_expr_value (parent_block_last_stmt,
  				       (edge_flags & EDGE_TRUE_VALUE) != 0,
! 				       &bd->true_exprs,
! 				       &bd->false_exprs,
  				       bb,
! 				       &bd->vrp_variables);
    /* Similarly when the parent block ended in a SWITCH_EXPR.  */
    else if (parent_block_last_stmt
  	   && bb->pred->pred_next == NULL
*************** record_equivalences_from_incoming_edge (
*** 912,917 ****
--- 987,993 ----
  	}
      }
  
+ 
    /* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
       new value for VAR, so that occurrences of VAR can be replaced with
       VALUE while re-writing the THEN arm of a COND_EXPR.  */
*************** record_equivalences_from_incoming_edge (
*** 919,932 ****
      {
        tree dest = TREE_OPERAND (eq_expr_value, 0);
        tree src = TREE_OPERAND (eq_expr_value, 1);
!       tree prev_value = get_value_for (dest);
  
!       set_value_for (dest, src);
  
        /* Record the destination and its previous value so that we can
  	 reset them as we leave this block.  */
!       VARRAY_PUSH_TREE (*block_const_and_copies_p, dest);
!       VARRAY_PUSH_TREE (*block_const_and_copies_p, prev_value);
      }
  }
  
--- 995,1008 ----
      {
        tree dest = TREE_OPERAND (eq_expr_value, 0);
        tree src = TREE_OPERAND (eq_expr_value, 1);
!       tree prev_value = get_value_for (dest, const_and_copies);
  
!       set_value_for (dest, src, const_and_copies);
  
        /* Record the destination and its previous value so that we can
  	 reset them as we leave this block.  */
!       VARRAY_PUSH_TREE (bd->const_and_copies, dest);
!       VARRAY_PUSH_TREE (bd->const_and_copies, prev_value);
      }
  }
  
*************** dom_opt_walk_stmts (struct dom_walk_data
*** 976,982 ****
  	 because that would change the statement's value number.  If the
  	 statement had been added to AVAIL_EXPRS, we would not be able to
  	 find it again.  */
!       if (optimize_stmt (si, &bd->avail_exprs))
  	VARRAY_PUSH_TREE (bd->stmts_to_rescan, bsi_stmt (si));
      }
  }
--- 1052,1060 ----
  	 because that would change the statement's value number.  If the
  	 statement had been added to AVAIL_EXPRS, we would not be able to
  	 find it again.  */
!       if (optimize_stmt (si,
! 			 &bd->avail_exprs,
! 			 &bd->nonzero_vars))
  	VARRAY_PUSH_TREE (bd->stmts_to_rescan, bsi_stmt (si));
      }
  }
*************** thread_jumps_walk_stmts (struct dom_walk
*** 1057,1064 ****
  	 this statement may still generate other equivalences.  For example,
  	 an aliased store can indicate that a pointer has a nonzero value.  */
        if (TREE_CODE (stmt) == MODIFY_EXPR)
! 	record_equivalences_from_stmt (stmt, &bd->avail_exprs,
! 				       may_optimize_p, stmt_ann (stmt));
      }
  }
  
--- 1135,1145 ----
  	 this statement may still generate other equivalences.  For example,
  	 an aliased store can indicate that a pointer has a nonzero value.  */
        if (TREE_CODE (stmt) == MODIFY_EXPR)
! 	record_equivalences_from_stmt (stmt,
! 				       &bd->avail_exprs,
! 				       &bd->nonzero_vars,
! 				       may_optimize_p,
! 				       stmt_ann (stmt));
      }
  }
  
*************** dump_dominator_optimization_stats (FILE 
*** 1093,1098 ****
--- 1174,1184 ----
    fprintf (file, "    avail_exprs: ");
    htab_statistics (file, avail_exprs);
  
+   fprintf (file, "    true_exprs: ");
+   htab_statistics (file, true_exprs);
+ 
+   fprintf (file, "    false_exprs: ");
+   htab_statistics (file, false_exprs);
    fprintf (file, "\n");
  }
  
*************** htab_statistics (FILE *file, htab_t htab
*** 1117,1144 ****
  	   htab_collisions (htab));
  }
  
  /* Enter a statement into the available expression hash table indicating
     that the condition COND is true.  */
  
  static void
! record_cond_is_true (tree cond, varray_type *block_avail_exprs_p)
  {
!   tree stmt;
  
!   stmt = build (MODIFY_EXPR, boolean_type_node, integer_one_node, cond);
!   lookup_avail_expr (stmt, block_avail_exprs_p, true);
  }
  
  /* Enter a statement into the available expression hash table indicating
     that the condition COND is false.  */
  
  static void
! record_cond_is_false (tree cond, varray_type *block_avail_exprs_p)
  {
!   tree stmt;
  
!   stmt = build (MODIFY_EXPR, boolean_type_node, integer_zero_node, cond);
!   lookup_avail_expr (stmt, block_avail_exprs_p, true);
  }
  
  /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
--- 1203,1254 ----
  	   htab_collisions (htab));
  }
  
+ /* 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.  */
+   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
     that the condition COND is true.  */
  
  static void
! record_cond_is_true (tree cond, varray_type *block_true_exprs_p)
  {
!   void **slot;
  
!   slot = htab_find_slot (true_exprs, cond, true);
! 
!   if (*slot == NULL)
!     {
!       *slot = (void *) cond;
!       VARRAY_PUSH_TREE (*block_true_exprs_p, cond);
!     }
  }
  
  /* Enter a statement into the available expression hash table indicating
     that the condition COND is false.  */
  
  static void
! record_cond_is_false (tree cond, varray_type *block_false_exprs_p)
  {
!   void **slot;
!   slot = htab_find_slot (false_exprs, cond, true);
  
!   if (*slot == NULL)
!     {
!       *slot = (void *) cond;
!       VARRAY_PUSH_TREE (*block_false_exprs_p, cond);
!     }
  }
  
  /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
*************** cprop_into_stmt (tree stmt)
*** 1655,1661 ****
  	   copy of some other variable, use the value or copy stored in
  	   CONST_AND_COPIES.  */
  	opt_stats.num_exprs_considered++;
! 	val = get_value_for (*op_p);
  	if (val)
  	  {
  	    /* Do not change the base variable in the virtual operand
--- 1765,1771 ----
  	   copy of some other variable, use the value or copy stored in
  	   CONST_AND_COPIES.  */
  	opt_stats.num_exprs_considered++;
! 	val = get_value_for (*op_p, const_and_copies);
  	if (val)
  	  {
  	    /* Do not change the base variable in the virtual operand
*************** cprop_into_phis (struct dom_walk_data *w
*** 1789,1795 ****
  
  	  /* If we have *ORIG_P in our constant/copy table, then replace
  	     ORIG_P with its value in our constant/copy table.  */
! 	  new = get_value_for (*orig_p);
  	  if (new
  	      && (TREE_CODE (new) == SSA_NAME || is_gimple_min_invariant (new))
  	      && may_propagate_copy (*orig_p, new))
--- 1899,1905 ----
  
  	  /* If we have *ORIG_P in our constant/copy table, then replace
  	     ORIG_P with its value in our constant/copy table.  */
! 	  new = get_value_for (*orig_p, const_and_copies);
  	  if (new
  	      && (TREE_CODE (new) == SSA_NAME || is_gimple_min_invariant (new))
  	      && may_propagate_copy (*orig_p, new))
*************** eliminate_redundant_computations (tree s
*** 1828,1835 ****
      insert = false;
  
    /* Check if the expression has been computed before.  */
!   cached_lhs = lookup_avail_expr (stmt, block_avail_exprs_p,
! 				  insert);
  
    /* If this is an assignment and the RHS was not in the hash table,
       then try to simplify the RHS and lookup the new RHS in the
--- 1938,1944 ----
      insert = false;
  
    /* Check if the expression has been computed before.  */
!   cached_lhs = lookup_avail_expr (stmt, block_avail_exprs_p, insert);
  
    /* If this is an assignment and the RHS was not in the hash table,
       then try to simplify the RHS and lookup the new RHS in the
*************** eliminate_redundant_computations (tree s
*** 1905,1910 ****
--- 2014,2020 ----
  static void
  record_equivalences_from_stmt (tree stmt,
  			       varray_type *block_avail_exprs_p,
+ 			       varray_type *block_nonzero_vars_p,
  			       int may_optimize_p,
  			       stmt_ann_t ann)
  {
*************** record_equivalences_from_stmt (tree stmt
*** 1925,1931 ****
        if (may_optimize_p
  	  && (TREE_CODE (rhs) == SSA_NAME
  	      || is_gimple_min_invariant (rhs)))
! 	set_value_for (lhs, rhs);
  
        /* alloca never returns zero and the address of a non-weak symbol
  	 is never zero.  NOP_EXPRs can be completely stripped as they
--- 2035,2041 ----
        if (may_optimize_p
  	  && (TREE_CODE (rhs) == SSA_NAME
  	      || is_gimple_min_invariant (rhs)))
! 	set_value_for (lhs, rhs, const_and_copies);
  
        /* alloca never returns zero and the address of a non-weak symbol
  	 is never zero.  NOP_EXPRs can be completely stripped as they
*************** record_equivalences_from_stmt (tree stmt
*** 1937,1968 ****
            || (TREE_CODE (rhs) == ADDR_EXPR
  	      && DECL_P (TREE_OPERAND (rhs, 0))
  	      && ! DECL_WEAK (TREE_OPERAND (rhs, 0))))
! 	{
! 	  tree cond;
! 
! 	  cond = build (EQ_EXPR, boolean_type_node, lhs, null_pointer_node);
! 	  record_cond_is_false (cond, block_avail_exprs_p);
! 
! 	  cond = build (NE_EXPR, boolean_type_node, lhs, null_pointer_node);
! 	  record_cond_is_true (cond, block_avail_exprs_p);
! 	}
  
        /* IOR of any value with a nonzero value will result in a nonzero
  	 value.  Even if we do not know the exact result recording that
  	 the result is nonzero is worth the effort.  */
        if (TREE_CODE (rhs) == BIT_IOR_EXPR
  	  && integer_nonzerop (TREE_OPERAND (rhs, 1)))
! 	{
! 	  tree cond;
! 
! 	  cond = build (EQ_EXPR, boolean_type_node, lhs,
! 			convert (TREE_TYPE (lhs), integer_zero_node));
! 	  record_cond_is_false (cond, block_avail_exprs_p);
! 
! 	  cond = build (NE_EXPR, boolean_type_node, lhs,
! 			convert (TREE_TYPE (lhs), integer_zero_node));
! 	  record_cond_is_true (cond, block_avail_exprs_p);
! 	}
      }
  
    /* Look at both sides for pointer dereferences.  If we find one, then
--- 2047,2060 ----
            || (TREE_CODE (rhs) == ADDR_EXPR
  	      && DECL_P (TREE_OPERAND (rhs, 0))
  	      && ! DECL_WEAK (TREE_OPERAND (rhs, 0))))
! 	record_var_is_nonzero (lhs, block_nonzero_vars_p);
  
        /* IOR of any value with a nonzero value will result in a nonzero
  	 value.  Even if we do not know the exact result recording that
  	 the result is nonzero is worth the effort.  */
        if (TREE_CODE (rhs) == BIT_IOR_EXPR
  	  && integer_nonzerop (TREE_OPERAND (rhs, 1)))
! 	record_var_is_nonzero (lhs, block_nonzero_vars_p);
      }
  
    /* Look at both sides for pointer dereferences.  If we find one, then
*************** record_equivalences_from_stmt (tree stmt
*** 1980,1997 ****
        if (TREE_CODE (t) == INDIRECT_REF)
          {
  	  tree op = TREE_OPERAND (t, 0);
- 	  tree cond;
  
  	  /* If the pointer is a SSA variable, then enter new
  	     equivalences into the hash table.  */
  	  if (TREE_CODE (op) == SSA_NAME)
! 	    {
! 	      cond = build (EQ_EXPR, boolean_type_node, op, null_pointer_node);
! 	      record_cond_is_false (cond, block_avail_exprs_p);
! 
! 	      cond = build (NE_EXPR, boolean_type_node, op, null_pointer_node);
! 	      record_cond_is_true (cond, block_avail_exprs_p);
! 	    }
  	}
      }
  
--- 2072,2082 ----
        if (TREE_CODE (t) == INDIRECT_REF)
          {
  	  tree op = TREE_OPERAND (t, 0);
  
  	  /* If the pointer is a SSA variable, then enter new
  	     equivalences into the hash table.  */
  	  if (TREE_CODE (op) == SSA_NAME)
! 	    record_var_is_nonzero (op, block_nonzero_vars_p);
  	}
      }
  
*************** record_equivalences_from_stmt (tree stmt
*** 2068,2074 ****
        the variable in the LHS in the CONST_AND_COPIES table.  */
  
  static bool
! optimize_stmt (block_stmt_iterator si, varray_type *block_avail_exprs_p)
  {
    stmt_ann_t ann;
    tree stmt;
--- 2153,2161 ----
        the variable in the LHS in the CONST_AND_COPIES table.  */
  
  static bool
! optimize_stmt (block_stmt_iterator si,
! 	       varray_type *block_avail_exprs_p,
! 	       varray_type *block_nonzero_vars_p)
  {
    stmt_ann_t ann;
    tree stmt;
*************** optimize_stmt (block_stmt_iterator si, v
*** 2133,2140 ****
  
    /* Record any additional equivalences created by this statement.  */
    if (TREE_CODE (stmt) == MODIFY_EXPR)
!     record_equivalences_from_stmt (stmt, block_avail_exprs_p,
! 				   may_optimize_p, ann);
  
    /* If STMT is a COND_EXPR and it was modified, then we may know
       where it goes.  In which case we can remove some edges, simplify
--- 2220,2230 ----
  
    /* Record any additional equivalences created by this statement.  */
    if (TREE_CODE (stmt) == MODIFY_EXPR)
!     record_equivalences_from_stmt (stmt,
! 				   block_avail_exprs_p,
! 				   block_nonzero_vars_p,
! 				   may_optimize_p,
! 				   ann);
  
    /* If STMT is a COND_EXPR and it was modified, then we may know
       where it goes.  In which case we can remove some edges, simplify
*************** lookup_avail_expr (tree stmt, varray_typ
*** 2248,2253 ****
--- 2338,2371 ----
        || is_gimple_min_invariant (rhs))
      return NULL_TREE;
  
+   /* If this is an equality test against zero, see if we have recorded a
+      nonzero value for the variable in question.  */
+   if ((TREE_CODE (rhs) == EQ_EXPR
+        || TREE_CODE  (rhs) == NE_EXPR)
+       && 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;
+ 	  else
+ 	    return boolean_true_node;
+ 	}
+     }
+ 
+   /* See if we have this expression as a true/false value.  */
+   slot = htab_find_slot (true_exprs, rhs, NO_INSERT);
+   if (slot)
+     return boolean_true_node;
+ 
+   slot = htab_find_slot (false_exprs, rhs, NO_INSERT);
+   if (slot)
+     return boolean_false_node;
+ 
+   /* Finaly try to find the expression in the main expression hash table.  */
    slot = htab_find_slot (avail_exprs, stmt, (insert ? INSERT : NO_INSERT));
    if (slot == NULL)
      return NULL_TREE;
*************** lookup_avail_expr (tree stmt, varray_typ
*** 2267,2273 ****
       use the value from the const_and_copies table.  */
    if (TREE_CODE (lhs) == SSA_NAME)
      {
!       temp = get_value_for (lhs);
        if (temp)
  	lhs = temp;
      }
--- 2385,2391 ----
       use the value from the const_and_copies table.  */
    if (TREE_CODE (lhs) == SSA_NAME)
      {
!       temp = get_value_for (lhs, const_and_copies);
        if (temp)
  	lhs = temp;
      }
*************** record_range (tree cond, basic_block bb,
*** 2393,2400 ****
     get back a constant indicating if the condition is true.  */
  
  static tree
! get_eq_expr_value (tree if_stmt, int true_arm, varray_type 
*block_avail_exprs_p,
! 		   basic_block bb, varray_type *vrp_variables_p)
  {
    tree cond, value;
  
--- 2511,2522 ----
     get back a constant indicating if the condition is true.  */
  
  static tree
! get_eq_expr_value (tree if_stmt,
! 		   int true_arm,
! 		   varray_type *block_true_exprs_p,
! 		   varray_type *block_false_exprs_p,
! 		   basic_block bb,
! 		   varray_type *vrp_variables_p)
  {
    tree cond, value;
  
*************** get_eq_expr_value (tree if_stmt, int tru
*** 2429,2436 ****
  	     condition into the hash table.  */
  	  if (true_arm)
  	    {
! 	      record_cond_is_true (cond, block_avail_exprs_p);
! 	      record_cond_is_false (inverted, block_avail_exprs_p);
  
  	      if (TREE_CONSTANT (op1))
  		record_range (cond, bb, vrp_variables_p);
--- 2551,2558 ----
  	     condition into the hash table.  */
  	  if (true_arm)
  	    {
! 	      record_cond_is_true (cond, block_true_exprs_p);
! 	      record_cond_is_false (inverted, block_false_exprs_p);
  
  	      if (TREE_CONSTANT (op1))
  		record_range (cond, bb, vrp_variables_p);
*************** get_eq_expr_value (tree if_stmt, int tru
*** 2443,2450 ****
  	  else
  	    {
  
! 	      record_cond_is_true (inverted, block_avail_exprs_p);
! 	      record_cond_is_false (cond, block_avail_exprs_p);
  
  	      if (TREE_CONSTANT (op1))
  		record_range (inverted, bb, vrp_variables_p);
--- 2565,2572 ----
  	  else
  	    {
  
! 	      record_cond_is_true (inverted, block_true_exprs_p);
! 	      record_cond_is_false (cond, block_false_exprs_p);
  
  	      if (TREE_CONSTANT (op1))
  		record_range (inverted, bb, vrp_variables_p);
*************** get_eq_expr_value (tree if_stmt, int tru
*** 2460,2465 ****
--- 2582,2624 ----
    return value;
  }
  
+ /* Hashing for expressions which are going to be entered into the true/false
+    hash tables.  */
+ 
+ static hashval_t
+ true_false_expr_hash (const void *p)
+ {
+   tree rhs = (tree) p;
+   return iterative_hash_expr (rhs, 0);
+ }
+ 
+ /* Given two expressions from the true/false hash tables, return nonzero
+    if they are equivalent.  */
+ 
+ static int
+ true_false_expr_eq (const void *p1, const void *p2)
+ {
+   tree rhs1 = (tree)p1;
+   tree rhs2 = (tree)p2;
+ 
+   /* If they are the same physical statement, return true.  */
+   if (rhs1 == rhs2)
+     return true;
+ 
+   if (TREE_CODE (rhs1) == TREE_CODE (rhs2)
+       && (TREE_TYPE (rhs1) == TREE_TYPE (rhs2)
+ 	  || (TYPE_MAIN_VARIANT (TREE_TYPE (rhs1))
+ 	      == TYPE_MAIN_VARIANT (TREE_TYPE (rhs2))))
+       && operand_equal_p (rhs1, rhs2, 0))
+     {
+ #ifdef ENABLE_CHECKING
+ 	  if (true_false_expr_hash (rhs1) != true_false_expr_hash (rhs2))
+ 	    abort ();
+ #endif
+ 	  return true;
+     }
+   return false;
+ }
  
  /* Hashing and equality functions for AVAIL_EXPRS.  The table stores
     MODIFY_EXPR statements.  We compute a value number for expressions using






Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]