2005-12-02 Richard Guenther <rguenther@suse.de>

[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-dom.c

diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index ebb0aa3..1c7bcbe 100644 (file)
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -16,8 +16,8 @@ GNU General Public License for more details.
 
 You should have received a copy of the GNU General Public License
 along with GCC; see the file COPYING.  If not, write to
 
 You should have received a copy of the GNU General Public License
 along with GCC; see the file COPYING.  If not, write to

-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA.  */
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA.  */

 
 #include "config.h"
 #include "system.h"
 
 #include "config.h"
 #include "system.h"


@@ -31,7 +31,6 @@ Boston, MA 02111-1307, USA.  */
 #include "basic-block.h"
 #include "cfgloop.h"
 #include "output.h"
 #include "basic-block.h"
 #include "cfgloop.h"
 #include "output.h"

-#include "errors.h"

 #include "expr.h"
 #include "function.h"
 #include "diagnostic.h"
 #include "expr.h"
 #include "function.h"
 #include "diagnostic.h"


@@ -43,6 +42,7 @@ Boston, MA 02111-1307, USA.  */
 #include "tree-pass.h"
 #include "tree-ssa-propagate.h"
 #include "langhooks.h"
 #include "tree-pass.h"
 #include "tree-ssa-propagate.h"
 #include "langhooks.h"

+#include "params.h"

 
 /* This file implements optimizations on the dominator tree.  */
 
 
 /* This file implements optimizations on the dominator tree.  */
 


@@ -94,20 +94,7 @@ static htab_t avail_exprs;
    (null).  When we finish processing the block, we pop off entries and
    remove the expressions from the global hash table until we hit the
    marker.  */
    (null).  When we finish processing the block, we pop off entries and
    remove the expressions from the global hash table until we hit the
    marker.  */

-static VEC(tree_on_heap) *avail_exprs_stack;
-
-/* Stack of trees used to restore the global currdefs to its original
-   state after completing optimization of a block and its dominator children.
-
-   An SSA_NAME indicates that the current definition of the underlying
-   variable should be set to the given SSA_NAME.
-
-   A _DECL node indicates that the underlying variable has no current
-   definition.
-
-   A NULL node is used to mark the last node associated with the
-   current block.  */
-static VEC(tree_on_heap) *block_defs_stack;
+static VEC(tree,heap) *avail_exprs_stack;

 
 /* Stack of statements we need to rescan during finalization for newly
    exposed variables.
 
 /* Stack of statements we need to rescan during finalization for newly
    exposed variables.


@@ -116,7 +103,7 @@ static VEC(tree_on_heap) *block_defs_stack;
    expressions are removed from AVAIL_EXPRS.  Else we may change the
    hash code for an expression and be unable to find/remove it from
    AVAIL_EXPRS.  */
    expressions are removed from AVAIL_EXPRS.  Else we may change the
    hash code for an expression and be unable to find/remove it from
    AVAIL_EXPRS.  */

-static VEC(tree_on_heap) *stmts_to_rescan;
+static VEC(tree,heap) *stmts_to_rescan;

 
 /* Structure for entries in the expression hash table.
 
 
 /* Structure for entries in the expression hash table.
 


@@ -137,8 +124,8 @@ struct expr_hash_elt
   /* The expression (rhs) we want to record.  */
   tree rhs;
 
   /* The expression (rhs) we want to record.  */
   tree rhs;
 

-  /* The annotation if this element corresponds to a statement.  */
-  stmt_ann_t ann;
+  /* The stmt pointer if this element corresponds to a statement.  */
+  tree stmt;

 
   /* The hash value for RHS/ann.  */
   hashval_t hash;
 
   /* The hash value for RHS/ann.  */
   hashval_t hash;


@@ -148,18 +135,22 @@ struct expr_hash_elt
 
    A NULL entry is used to mark the end of pairs which need to be
    restored during finalization of this block.  */
 
    A NULL entry is used to mark the end of pairs which need to be
    restored during finalization of this block.  */

-static VEC(tree_on_heap) *const_and_copies_stack;
+static VEC(tree,heap) *const_and_copies_stack;

 
 /* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
    know their exact value.  */
 static bitmap nonzero_vars;
 
 
 /* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
    know their exact value.  */
 static bitmap nonzero_vars;
 

+/* Bitmap of blocks that are scheduled to be threaded through.  This
+   is used to communicate with thread_through_blocks.  */
+static bitmap threaded_blocks;
+

 /* Stack of SSA_NAMEs which need their NONZERO_VARS property cleared
    when the current block is finalized. 
 
    A NULL entry is used to mark the end of names needing their 
    entry in NONZERO_VARS cleared during finalization of this block.  */
 /* Stack of SSA_NAMEs which need their NONZERO_VARS property cleared
    when the current block is finalized. 
 
    A NULL entry is used to mark the end of names needing their 
    entry in NONZERO_VARS cleared during finalization of this block.  */

-static VEC(tree_on_heap) *nonzero_vars_stack;
+static VEC(tree,heap) *nonzero_vars_stack;

 
 /* Track whether or not we have changed the control flow graph.  */
 static bool cfg_altered;
 
 /* Track whether or not we have changed the control flow graph.  */
 static bool cfg_altered;


@@ -174,6 +165,9 @@ struct opt_stats_d
   long num_stmts;
   long num_exprs_considered;
   long num_re;
   long num_stmts;
   long num_exprs_considered;
   long num_re;

+  long num_const_prop;
+  long num_copy_prop;
+  long num_iterations;

 };
 
 static struct opt_stats_d opt_stats;
 };
 
 static struct opt_stats_d opt_stats;


@@ -235,12 +229,17 @@ struct vrp_element
    with useful information is very low.  */
 static htab_t vrp_data;
 
    with useful information is very low.  */
 static htab_t vrp_data;
 

+typedef struct vrp_element *vrp_element_p;
+
+DEF_VEC_P(vrp_element_p);
+DEF_VEC_ALLOC_P(vrp_element_p,heap);
+

 /* An entry in the VRP_DATA hash table.  We record the variable and a
    varray of VRP_ELEMENT records associated with that variable.  */
 struct vrp_hash_elt
 {
   tree var;
 /* An entry in the VRP_DATA hash table.  We record the variable and a
    varray of VRP_ELEMENT records associated with that variable.  */
 struct vrp_hash_elt
 {
   tree var;

-  varray_type records;
+  VEC(vrp_element_p,heap) *records;

 };
 
 /* Array of variables which have their values constrained by operations
 };
 
 /* Array of variables which have their values constrained by operations


@@ -252,7 +251,7 @@ struct vrp_hash_elt
    list to determine which variables need their VRP data updated.
 
    A NULL entry marks the end of the SSA_NAMEs associated with this block.  */
    list to determine which variables need their VRP data updated.
 
    A NULL entry marks the end of the SSA_NAMEs associated with this block.  */

-static VEC(tree_on_heap) *vrp_variables_stack;
+static VEC(tree,heap) *vrp_variables_stack;

 
 struct eq_expr_value
 {
 
 struct eq_expr_value
 {


@@ -275,8 +274,7 @@ static void record_cond (tree, tree);
 static void record_const_or_copy (tree, tree);
 static void record_equality (tree, tree);
 static tree update_rhs_and_lookup_avail_expr (tree, tree, bool);
 static void record_const_or_copy (tree, tree);
 static void record_equality (tree, tree);
 static tree update_rhs_and_lookup_avail_expr (tree, tree, bool);

-static tree simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *,
-                                               tree, int);
+static tree simplify_rhs_and_lookup_avail_expr (tree, int);

 static tree simplify_cond_and_lookup_avail_expr (tree, stmt_ann_t, int);
 static tree simplify_switch_and_lookup_avail_expr (tree, int);
 static tree find_equivalent_equality_comparison (tree);
 static tree simplify_cond_and_lookup_avail_expr (tree, stmt_ann_t, int);
 static tree simplify_switch_and_lookup_avail_expr (tree, int);
 static tree find_equivalent_equality_comparison (tree);


@@ -284,8 +282,7 @@ static void record_range (tree, basic_block);
 static bool extract_range_from_cond (tree, tree *, tree *, int *);
 static void record_equivalences_from_phis (basic_block);
 static void record_equivalences_from_incoming_edge (basic_block);
 static bool extract_range_from_cond (tree, tree *, tree *, int *);
 static void record_equivalences_from_phis (basic_block);
 static void record_equivalences_from_incoming_edge (basic_block);

-static bool eliminate_redundant_computations (struct dom_walk_data *,
-                                             tree, stmt_ann_t);
+static bool eliminate_redundant_computations (tree, stmt_ann_t);

 static void record_equivalences_from_stmt (tree, int, stmt_ann_t);
 static void thread_across_edge (struct dom_walk_data *, edge);
 static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);
 static void record_equivalences_from_stmt (tree, int, stmt_ann_t);
 static void thread_across_edge (struct dom_walk_data *, edge);
 static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);


@@ -293,12 +290,11 @@ static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);
 static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block);
 static void remove_local_expressions_from_table (void);
 static void restore_vars_to_original_value (void);
 static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block);
 static void remove_local_expressions_from_table (void);
 static void restore_vars_to_original_value (void);

-static void restore_currdefs_to_original_value (void);
-static void register_definitions_for_stmt (tree);

 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
 static void restore_nonzero_vars_to_original_value (void);
 static inline bool unsafe_associative_fp_binop (tree);
 
 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
 static void restore_nonzero_vars_to_original_value (void);
 static inline bool unsafe_associative_fp_binop (tree);
 

+

 /* Local version of fold that doesn't introduce cruft.  */
 
 static tree
 /* Local version of fold that doesn't introduce cruft.  */
 
 static tree


@@ -358,6 +354,18 @@ free_all_edge_infos (void)
     }
 }
 
     }
 }
 

+/* Free an instance of vrp_hash_elt.  */
+
+static void
+vrp_free (void *data)
+{
+  struct vrp_hash_elt *elt = data;
+  struct VEC(vrp_element_p,heap) **vrp_elt = &elt->records;
+
+  VEC_free (vrp_element_p, heap, *vrp_elt);
+  free (elt);
+}
+

 /* Jump threading, redundancy elimination and const/copy propagation. 
 
    This pass may expose new symbols that need to be renamed into SSA.  For
 /* Jump threading, redundancy elimination and const/copy propagation. 
 
    This pass may expose new symbols that need to be renamed into SSA.  For


@@ -373,19 +381,17 @@ tree_ssa_dominator_optimize (void)
 
   memset (&opt_stats, 0, sizeof (opt_stats));
 
 
   memset (&opt_stats, 0, sizeof (opt_stats));
 

-  for (i = 0; i < num_referenced_vars; i++)
-    var_ann (referenced_var (i))->current_def = NULL;
-

   /* Create our hash tables.  */
   avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);
   /* Create our hash tables.  */
   avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);

-  vrp_data = htab_create (ceil_log2 (num_ssa_names), vrp_hash, vrp_eq, free);
-  avail_exprs_stack = VEC_alloc (tree_on_heap, 20);
-  block_defs_stack = VEC_alloc (tree_on_heap, 20);
-  const_and_copies_stack = VEC_alloc (tree_on_heap, 20);
-  nonzero_vars_stack = VEC_alloc (tree_on_heap, 20);
-  vrp_variables_stack = VEC_alloc (tree_on_heap, 20);
-  stmts_to_rescan = VEC_alloc (tree_on_heap, 20);
+  vrp_data = htab_create (ceil_log2 (num_ssa_names), vrp_hash, vrp_eq,
+                         vrp_free);
+  avail_exprs_stack = VEC_alloc (tree, heap, 20);
+  const_and_copies_stack = VEC_alloc (tree, heap, 20);
+  nonzero_vars_stack = VEC_alloc (tree, heap, 20);
+  vrp_variables_stack = VEC_alloc (tree, heap, 20);
+  stmts_to_rescan = VEC_alloc (tree, heap, 20);

   nonzero_vars = BITMAP_ALLOC (NULL);
   nonzero_vars = BITMAP_ALLOC (NULL);

+  threaded_blocks = BITMAP_ALLOC (NULL);

   need_eh_cleanup = BITMAP_ALLOC (NULL);
 
   /* Setup callbacks for the generic dominator tree walker.  */
   need_eh_cleanup = BITMAP_ALLOC (NULL);
 
   /* Setup callbacks for the generic dominator tree walker.  */


@@ -403,6 +409,7 @@ tree_ssa_dominator_optimize (void)
      structure.  */
   walk_data.global_data = NULL;
   walk_data.block_local_data_size = 0;
      structure.  */
   walk_data.global_data = NULL;
   walk_data.block_local_data_size = 0;

+  walk_data.interesting_blocks = NULL;

 
   /* Now initialize the dominator walker.  */
   init_walk_dominator_tree (&walk_data);
 
   /* Now initialize the dominator walker.  */
   init_walk_dominator_tree (&walk_data);


@@ -419,6 +426,7 @@ tree_ssa_dominator_optimize (void)
   /* Clean up the CFG so that any forwarder blocks created by loop
      canonicalization are removed.  */
   cleanup_tree_cfg ();
   /* Clean up the CFG so that any forwarder blocks created by loop
      canonicalization are removed.  */
   cleanup_tree_cfg ();

+  calculate_dominance_info (CDI_DOMINATORS);

 
   /* If we prove certain blocks are unreachable, then we want to
      repeat the dominator optimization process as PHI nodes may
 
   /* If we prove certain blocks are unreachable, then we want to
      repeat the dominator optimization process as PHI nodes may


@@ -437,32 +445,29 @@ tree_ssa_dominator_optimize (void)
       /* Recursively walk the dominator tree optimizing statements.  */
       walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 
       /* Recursively walk the dominator tree optimizing statements.  */
       walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 

+      {
+       block_stmt_iterator bsi;
+       basic_block bb;
+       FOR_EACH_BB (bb)
+         {
+           for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+             {
+               update_stmt_if_modified (bsi_stmt (bsi));
+             }
+         }
+      }
+

       /* If we exposed any new variables, go ahead and put them into
         SSA form now, before we handle jump threading.  This simplifies
         interactions between rewriting of _DECL nodes into SSA form
         and rewriting SSA_NAME nodes into SSA form after block
         duplication and CFG manipulation.  */
       /* If we exposed any new variables, go ahead and put them into
         SSA form now, before we handle jump threading.  This simplifies
         interactions between rewriting of _DECL nodes into SSA form
         and rewriting SSA_NAME nodes into SSA form after block
         duplication and CFG manipulation.  */

-      if (!bitmap_empty_p (vars_to_rename))
-       {
-         rewrite_into_ssa (false);
-         bitmap_clear (vars_to_rename);
-       }
+      update_ssa (TODO_update_ssa);

 
       free_all_edge_infos ();
 
 
       free_all_edge_infos ();
 

-  {
-    block_stmt_iterator bsi;
-    basic_block bb;
-    FOR_EACH_BB (bb)
-      {
-       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
-         {
-           update_stmt_if_modified (bsi_stmt (bsi));
-         }
-      }
-  }

       /* Thread jumps, creating duplicate blocks as needed.  */
       /* Thread jumps, creating duplicate blocks as needed.  */

-      cfg_altered |= thread_through_all_blocks ();
+      cfg_altered |= thread_through_all_blocks (threaded_blocks);

 
       /* Removal of statements may make some EH edges dead.  Purge
         such edges from the CFG as needed.  */
 
       /* Removal of statements may make some EH edges dead.  Purge
         such edges from the CFG as needed.  */


@@ -475,7 +480,11 @@ tree_ssa_dominator_optimize (void)
       if (cfg_altered)
         free_dominance_info (CDI_DOMINATORS);
 
       if (cfg_altered)
         free_dominance_info (CDI_DOMINATORS);
 

-      cfg_altered |= cleanup_tree_cfg ();
+      /* Only iterate if we threaded jumps AND the CFG cleanup did
+        something interesting.  Other cases generate far fewer
+        optimization opportunities and thus are not worth another
+        full DOM iteration.  */
+      cfg_altered &= cleanup_tree_cfg ();

 
       if (rediscover_loops_after_threading)
        {
 
       if (rediscover_loops_after_threading)
        {


@@ -493,21 +502,19 @@ tree_ssa_dominator_optimize (void)
 
       calculate_dominance_info (CDI_DOMINATORS);
 
 
       calculate_dominance_info (CDI_DOMINATORS);
 

-      rewrite_ssa_into_ssa ();
+      update_ssa (TODO_update_ssa);

 
       /* Reinitialize the various tables.  */
       bitmap_clear (nonzero_vars);
 
       /* Reinitialize the various tables.  */
       bitmap_clear (nonzero_vars);

+      bitmap_clear (threaded_blocks);

       htab_empty (avail_exprs);
       htab_empty (vrp_data);
 
       htab_empty (avail_exprs);
       htab_empty (vrp_data);
 

-      for (i = 0; i < num_referenced_vars; i++)
-       var_ann (referenced_var (i))->current_def = NULL;
-

       /* Finally, remove everything except invariants in SSA_NAME_VALUE.
 
         This must be done before we iterate as we might have a
         reference to an SSA_NAME which was removed by the call to
       /* Finally, remove everything except invariants in SSA_NAME_VALUE.
 
         This must be done before we iterate as we might have a
         reference to an SSA_NAME which was removed by the call to

-        rewrite_ssa_into_ssa.
+        update_ssa.

 
         Long term we will be able to let everything in SSA_NAME_VALUE
         persist.  However, for now, we know this is the safe thing to do.  */
 
         Long term we will be able to let everything in SSA_NAME_VALUE
         persist.  However, for now, we know this is the safe thing to do.  */


@@ -523,6 +530,8 @@ tree_ssa_dominator_optimize (void)
          if (value && !is_gimple_min_invariant (value))
            SSA_NAME_VALUE (name) = NULL;
        }
          if (value && !is_gimple_min_invariant (value))
            SSA_NAME_VALUE (name) = NULL;
        }

+
+      opt_stats.num_iterations++;

     }
   while (optimize > 1 && cfg_altered);
 
     }
   while (optimize > 1 && cfg_altered);
 


@@ -543,14 +552,14 @@ tree_ssa_dominator_optimize (void)
 
   /* Free nonzero_vars.  */
   BITMAP_FREE (nonzero_vars);
 
   /* Free nonzero_vars.  */
   BITMAP_FREE (nonzero_vars);

+  BITMAP_FREE (threaded_blocks);

   BITMAP_FREE (need_eh_cleanup);
   
   BITMAP_FREE (need_eh_cleanup);
   

-  VEC_free (tree_on_heap, block_defs_stack);
-  VEC_free (tree_on_heap, avail_exprs_stack);
-  VEC_free (tree_on_heap, const_and_copies_stack);
-  VEC_free (tree_on_heap, nonzero_vars_stack);
-  VEC_free (tree_on_heap, vrp_variables_stack);
-  VEC_free (tree_on_heap, stmts_to_rescan);
+  VEC_free (tree, heap, avail_exprs_stack);
+  VEC_free (tree, heap, const_and_copies_stack);
+  VEC_free (tree, heap, nonzero_vars_stack);
+  VEC_free (tree, heap, vrp_variables_stack);
+  VEC_free (tree, heap, stmts_to_rescan);

 }
 
 static bool
 }
 
 static bool


@@ -572,14 +581,27 @@ struct tree_opt_pass pass_dominator =
   0,                                   /* properties_provided */
   0,                                   /* properties_destroyed */
   0,                                   /* todo_flags_start */
   0,                                   /* properties_provided */
   0,                                   /* properties_destroyed */
   0,                                   /* todo_flags_start */

-  TODO_dump_func | TODO_rename_vars
+  TODO_dump_func
+    | TODO_update_ssa

     | TODO_verify_ssa,                 /* todo_flags_finish */
   0                                    /* letter */
 };
 
 
     | TODO_verify_ssa,                 /* todo_flags_finish */
   0                                    /* letter */
 };
 
 

-/* We are exiting BB, see if the target block begins with a conditional
-   jump which has a known value when reached via BB.  */
+/* We are exiting E->src, see if E->dest ends with a conditional
+   jump which has a known value when reached via E. 
+
+   Special care is necessary if E is a back edge in the CFG as we
+   will have already recorded equivalences for E->dest into our
+   various tables, including the result of the conditional at
+   the end of E->dest.  Threading opportunities are severely
+   limited in that case to avoid short-circuiting the loop
+   incorrectly.
+
+   Note it is quite common for the first block inside a loop to
+   end with a conditional which is either always true or always
+   false when reached via the loop backedge.  Thus we do not want
+   to blindly disable threading across a loop backedge.  */

 
 static void
 thread_across_edge (struct dom_walk_data *walk_data, edge e)
 
 static void
 thread_across_edge (struct dom_walk_data *walk_data, edge e)


@@ -587,16 +609,46 @@ thread_across_edge (struct dom_walk_data *walk_data, edge e)
   block_stmt_iterator bsi;
   tree stmt = NULL;
   tree phi;
   block_stmt_iterator bsi;
   tree stmt = NULL;
   tree phi;

+  int stmt_count = 0;
+  int max_stmt_count;
+
+
+  /* If E->dest does not end with a conditional, then there is
+     nothing to do.  */
+  bsi = bsi_last (e->dest);
+  if (bsi_end_p (bsi)
+      || ! bsi_stmt (bsi)
+      || (TREE_CODE (bsi_stmt (bsi)) != COND_EXPR
+         && TREE_CODE (bsi_stmt (bsi)) != GOTO_EXPR
+         && TREE_CODE (bsi_stmt (bsi)) != SWITCH_EXPR))
+    return;

 
 

-  /* Each PHI creates a temporary equivalence, record them.  */
+  /* The basic idea here is to use whatever knowledge we have
+     from our dominator walk to simplify statements in E->dest,
+     with the ultimate goal being to simplify the conditional
+     at the end of E->dest.
+
+     Note that we must undo any changes we make to the underlying
+     statements as the simplifications we are making are control
+     flow sensitive (ie, the simplifications are valid when we 
+     traverse E, but may not be valid on other paths to E->dest.  */
+     
+  /* Each PHI creates a temporary equivalence, record them.  Again
+     these are context sensitive equivalences and will be removed
+     by our caller.  */

   for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
     {
       tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
       tree dst = PHI_RESULT (phi);
 
   for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
     {
       tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
       tree dst = PHI_RESULT (phi);
 

+      /* Do not include virtual PHIs in our statement count as
+        they never generate code.  */
+      if (is_gimple_reg (dst))
+       stmt_count++;
+

       /* If the desired argument is not the same as this PHI's result 
       /* If the desired argument is not the same as this PHI's result 

-        and it is set by a PHI in this block, then we can not thread
-        through this block.  */
+        and it is set by a PHI in E->dest, then we can not thread
+        through E->dest.  */

       if (src != dst
          && TREE_CODE (src) == SSA_NAME
          && TREE_CODE (SSA_NAME_DEF_STMT (src)) == PHI_NODE
       if (src != dst
          && TREE_CODE (src) == SSA_NAME
          && TREE_CODE (SSA_NAME_DEF_STMT (src)) == PHI_NODE


@@ -604,12 +656,27 @@ thread_across_edge (struct dom_walk_data *walk_data, edge e)
        return;
 
       record_const_or_copy (dst, src);
        return;
 
       record_const_or_copy (dst, src);

-      register_new_def (dst, &block_defs_stack);

     }
 
     }
 

+  /* Try to simplify each statement in E->dest, ultimately leading to
+     a simplification of the COND_EXPR at the end of E->dest.
+
+     We might consider marking just those statements which ultimately
+     feed the COND_EXPR.  It's not clear if the overhead of bookkeeping
+     would be recovered by trying to simplify fewer statements.
+
+     If we are able to simplify a statement into the form
+     SSA_NAME = (SSA_NAME | gimple invariant), then we can record
+     a context sensitive equivalency which may help us simplify
+     later statements in E->dest. 
+
+     Failure to simplify into the form above merely means that the
+     statement provides no equivalences to help simplify later
+     statements.  This does not prevent threading through E->dest.  */
+  max_stmt_count = PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS);

   for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
     {
   for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
     {

-      tree lhs, cached_lhs;
+      tree cached_lhs = NULL;

 
       stmt = bsi_stmt (bsi);
 
 
       stmt = bsi_stmt (bsi);
 


@@ -617,117 +684,115 @@ thread_across_edge (struct dom_walk_data *walk_data, edge e)
       if (IS_EMPTY_STMT (stmt) || TREE_CODE (stmt) == LABEL_EXPR)
        continue;
 
       if (IS_EMPTY_STMT (stmt) || TREE_CODE (stmt) == LABEL_EXPR)
        continue;
 

+      /* If duplicating this block is going to cause too much code
+        expansion, then do not thread through this block.  */
+      stmt_count++;
+      if (stmt_count > max_stmt_count)
+       return;
+
+      /* Safely handle threading across loop backedges.  This is
+        over conservative, but still allows us to capture the
+        majority of the cases where we can thread across a loop
+        backedge.  */
+      if ((e->flags & EDGE_DFS_BACK) != 0
+         && TREE_CODE (stmt) != COND_EXPR
+         && TREE_CODE (stmt) != SWITCH_EXPR)
+       return;
+
+      /* If the statement has volatile operands, then we assume we
+        can not thread through this block.  This is overly
+        conservative in some ways.  */
+      if (TREE_CODE (stmt) == ASM_EXPR && ASM_VOLATILE_P (stmt))
+       return;
+

       /* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new
       /* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new

-        value, then stop our search here.  Ideally when we stop a
-        search we stop on a COND_EXPR or SWITCH_EXPR.  */
+        value, then do not try to simplify this statement as it will
+        not simplify in any way that is helpful for jump threading.  */

       if (TREE_CODE (stmt) != MODIFY_EXPR
          || TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
       if (TREE_CODE (stmt) != MODIFY_EXPR
          || TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)

-       break;
+       continue;

 
       /* At this point we have a statement which assigns an RHS to an
 
       /* At this point we have a statement which assigns an RHS to an

-        SSA_VAR on the LHS.  We want to prove that the RHS is already
-        available and that its value is held in the current definition
-        of the LHS -- meaning that this assignment is a NOP when
-        reached via edge E.  */
+        SSA_VAR on the LHS.  We want to try and simplify this statement
+        to expose more context sensitive equivalences which in turn may
+        allow us to simplify the condition at the end of the loop.  */

       if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
        cached_lhs = TREE_OPERAND (stmt, 1);
       else
       if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
        cached_lhs = TREE_OPERAND (stmt, 1);
       else

-       cached_lhs = lookup_avail_expr (stmt, false);
-
-      lhs = TREE_OPERAND (stmt, 0);
-
-      /* This can happen if we thread around to the start of a loop.  */
-      if (lhs == cached_lhs)
-       break;
-
-      /* If we did not find RHS in the hash table, then try again after
-        temporarily const/copy propagating the operands.  */
-      if (!cached_lhs)

        {
          /* Copy the operands.  */
        {
          /* Copy the operands.  */

-         stmt_ann_t ann = stmt_ann (stmt);
-         use_optype uses = USE_OPS (ann);
-         vuse_optype vuses = VUSE_OPS (ann);
-         tree *uses_copy = xmalloc (NUM_USES (uses) * sizeof (tree));
-         tree *vuses_copy = xmalloc (NUM_VUSES (vuses) * sizeof (tree));
-         unsigned int i;
+         tree *copy, pre_fold_expr;
+         ssa_op_iter iter;
+         use_operand_p use_p;
+         unsigned int num, i = 0;
+
+         num = NUM_SSA_OPERANDS (stmt, (SSA_OP_USE | SSA_OP_VUSE));
+         copy = xcalloc (num, sizeof (tree));

 
 

-         /* Make a copy of the uses into USES_COPY, then cprop into
-            the use operands.  */
-         for (i = 0; i < NUM_USES (uses); i++)
+         /* Make a copy of the uses & vuses into USES_COPY, then cprop into
+            the operands.  */
+         FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)

            {
              tree tmp = NULL;
            {
              tree tmp = NULL;

+             tree use = USE_FROM_PTR (use_p);

 
 

-             uses_copy[i] = USE_OP (uses, i);
-             if (TREE_CODE (USE_OP (uses, i)) == SSA_NAME)
-               tmp = SSA_NAME_VALUE (USE_OP (uses, i));
+             copy[i++] = use;
+             if (TREE_CODE (use) == SSA_NAME)
+               tmp = SSA_NAME_VALUE (use);

              if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
              if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)

-               SET_USE_OP (uses, i, tmp);
+               SET_USE (use_p, tmp);

            }
 
            }
 

-         /* Similarly for virtual uses.  */
-         for (i = 0; i < NUM_VUSES (vuses); i++)
+         /* Try to fold/lookup the new expression.  Inserting the
+            expression into the hash table is unlikely to help
+            Sadly, we have to handle conditional assignments specially
+            here, because fold expects all the operands of an expression
+            to be folded before the expression itself is folded, but we
+            can't just substitute the folded condition here.  */
+         if (TREE_CODE (TREE_OPERAND (stmt, 1)) == COND_EXPR)

            {
            {

-             tree tmp = NULL;
-
-             vuses_copy[i] = VUSE_OP (vuses, i);
-             if (TREE_CODE (VUSE_OP (vuses, i)) == SSA_NAME)
-               tmp = SSA_NAME_VALUE (VUSE_OP (vuses, i));
-             if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
-               SET_VUSE_OP (vuses, i, tmp);
+             tree cond = COND_EXPR_COND (TREE_OPERAND (stmt, 1));
+             cond = fold (cond);
+             if (cond == boolean_true_node)
+               pre_fold_expr = COND_EXPR_THEN (TREE_OPERAND (stmt, 1));
+             else if (cond == boolean_false_node)
+               pre_fold_expr = COND_EXPR_ELSE (TREE_OPERAND (stmt, 1));
+             else
+               pre_fold_expr = TREE_OPERAND (stmt, 1);

            }
            }

+         else
+           pre_fold_expr = TREE_OPERAND (stmt, 1);

 
 

-         /* Try to lookup the new expression.  */
-         cached_lhs = lookup_avail_expr (stmt, false);
+         if (pre_fold_expr)
+           {
+             cached_lhs = fold (pre_fold_expr);
+             if (TREE_CODE (cached_lhs) != SSA_NAME
+                 && !is_gimple_min_invariant (cached_lhs))
+               cached_lhs = lookup_avail_expr (stmt, false);
+           }

 
          /* Restore the statement's original uses/defs.  */
 
          /* Restore the statement's original uses/defs.  */

-         for (i = 0; i < NUM_USES (uses); i++)
-           SET_USE_OP (uses, i, uses_copy[i]);
-
-         for (i = 0; i < NUM_VUSES (vuses); i++)
-           SET_VUSE_OP (vuses, i, vuses_copy[i]);
+         i = 0;
+         FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
+           SET_USE (use_p, copy[i++]);

 
 

-         free (uses_copy);
-         free (vuses_copy);
-
-         /* If we still did not find the expression in the hash table,
-            then we can not ignore this statement.  */
-         if (! cached_lhs)
-           break;
+         free (copy);

        }
 
        }
 

-      /* If the expression in the hash table was not assigned to an
-        SSA_NAME, then we can not ignore this statement.  */
-      if (TREE_CODE (cached_lhs) != SSA_NAME)
-       break;
-
-      /* If we have different underlying variables, then we can not
-        ignore this statement.  */
-      if (SSA_NAME_VAR (cached_lhs) != SSA_NAME_VAR (lhs))
-       break;
-
-      /* If CACHED_LHS does not represent the current value of the underlying
-        variable in CACHED_LHS/LHS, then we can not ignore this statement.  */
-      if (var_ann (SSA_NAME_VAR (lhs))->current_def != cached_lhs)
-       break;
-
-      /* If we got here, then we can ignore this statement and continue
-        walking through the statements in the block looking for a threadable
-        COND_EXPR.
-
-        We want to record an equivalence lhs = cache_lhs so that if
-        the result of this statement is used later we can copy propagate
-        suitably.  */
-      record_const_or_copy (lhs, cached_lhs);
-      register_new_def (lhs, &block_defs_stack);
+      /* Record the context sensitive equivalence if we were able
+        to simplify this statement.  */
+      if (cached_lhs
+         && (TREE_CODE (cached_lhs) == SSA_NAME
+             || is_gimple_min_invariant (cached_lhs)))
+       record_const_or_copy (TREE_OPERAND (stmt, 0), cached_lhs);

     }
 
     }
 

-  /* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
-     arm will be taken.  */
+  /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
+     will be taken.  */

   if (stmt
       && (TREE_CODE (stmt) == COND_EXPR
   if (stmt
       && (TREE_CODE (stmt) == COND_EXPR

-         || TREE_CODE (stmt) == SWITCH_EXPR
-         || TREE_CODE (stmt) == GOTO_EXPR))
+         || TREE_CODE (stmt) == GOTO_EXPR
+         || TREE_CODE (stmt) == SWITCH_EXPR))

     {
       tree cond, cached_lhs;
 
     {
       tree cond, cached_lhs;
 


@@ -769,9 +834,9 @@ thread_across_edge (struct dom_walk_data *walk_data, edge e)
          dummy_cond = walk_data->global_data;
          if (! dummy_cond)
            {
          dummy_cond = walk_data->global_data;
          if (! dummy_cond)
            {

-             dummy_cond = build (cond_code, boolean_type_node, op0, op1);
-             dummy_cond = build (COND_EXPR, void_type_node,
-                                 dummy_cond, NULL, NULL);
+             dummy_cond = build2 (cond_code, boolean_type_node, op0, op1);
+             dummy_cond = build3 (COND_EXPR, void_type_node,
+                                  dummy_cond, NULL_TREE, NULL_TREE);

              walk_data->global_data = dummy_cond;
            }
          else
              walk_data->global_data = dummy_cond;
            }
          else


@@ -801,7 +866,7 @@ thread_across_edge (struct dom_walk_data *walk_data, edge e)
          cached_lhs = cond;
          cached_lhs = SSA_NAME_VALUE (cached_lhs);
          if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
          cached_lhs = cond;
          cached_lhs = SSA_NAME_VALUE (cached_lhs);
          if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))

-           cached_lhs = 0;
+           cached_lhs = NULL;

        }
       else
        cached_lhs = lookup_avail_expr (stmt, false);
        }
       else
        cached_lhs = lookup_avail_expr (stmt, false);


@@ -822,14 +887,12 @@ thread_across_edge (struct dom_walk_data *walk_data, edge e)
            {
              struct edge_info *edge_info;
 
            {
              struct edge_info *edge_info;
 

-             update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
-                                              e->count, taken_edge);

              if (e->aux)
                edge_info = e->aux;
              else
                edge_info = allocate_edge_info (e);
              edge_info->redirection_target = taken_edge;
              if (e->aux)
                edge_info = e->aux;
              else
                edge_info = allocate_edge_info (e);
              edge_info->redirection_target = taken_edge;

-             bb_ann (e->dest)->incoming_edge_threaded = true;
+             bitmap_set_bit (threaded_blocks, e->dest->index);

            }
        }
     }
            }
        }
     }


@@ -849,11 +912,10 @@ dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
 
   /* Push a marker on the stacks of local information so that we know how
      far to unwind when we finalize this block.  */
 
   /* Push a marker on the stacks of local information so that we know how
      far to unwind when we finalize this block.  */

-  VEC_safe_push (tree_on_heap, avail_exprs_stack, NULL_TREE);
-  VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
-  VEC_safe_push (tree_on_heap, const_and_copies_stack, NULL_TREE);
-  VEC_safe_push (tree_on_heap, nonzero_vars_stack, NULL_TREE);
-  VEC_safe_push (tree_on_heap, vrp_variables_stack, NULL_TREE);
+  VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE);
+  VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
+  VEC_safe_push (tree, heap, nonzero_vars_stack, NULL_TREE);
+  VEC_safe_push (tree, heap, vrp_variables_stack, NULL_TREE);

 
   record_equivalences_from_incoming_edge (bb);
 
 
   record_equivalences_from_incoming_edge (bb);
 


@@ -862,7 +924,7 @@ dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
 }
 
 /* Given an expression EXPR (a relational expression or a statement), 
 }
 
 /* Given an expression EXPR (a relational expression or a statement), 

-   initialize the hash table element pointed by by ELEMENT.  */
+   initialize the hash table element pointed to by ELEMENT.  */

 
 static void
 initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)
 
 static void
 initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)


@@ -874,27 +936,32 @@ initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)
      we want to record the expression the statement evaluates.  */
   if (COMPARISON_CLASS_P (expr) || TREE_CODE (expr) == TRUTH_NOT_EXPR)
     {
      we want to record the expression the statement evaluates.  */
   if (COMPARISON_CLASS_P (expr) || TREE_CODE (expr) == TRUTH_NOT_EXPR)
     {

-      element->ann = NULL;
+      element->stmt = NULL;

       element->rhs = expr;
     }
   else if (TREE_CODE (expr) == COND_EXPR)
     {
       element->rhs = expr;
     }
   else if (TREE_CODE (expr) == COND_EXPR)
     {

-      element->ann = stmt_ann (expr);
+      element->stmt = expr;

       element->rhs = COND_EXPR_COND (expr);
     }
   else if (TREE_CODE (expr) == SWITCH_EXPR)
     {
       element->rhs = COND_EXPR_COND (expr);
     }
   else if (TREE_CODE (expr) == SWITCH_EXPR)
     {

-      element->ann = stmt_ann (expr);
+      element->stmt = expr;

       element->rhs = SWITCH_COND (expr);
     }
   else if (TREE_CODE (expr) == RETURN_EXPR && TREE_OPERAND (expr, 0))
     {
       element->rhs = SWITCH_COND (expr);
     }
   else if (TREE_CODE (expr) == RETURN_EXPR && TREE_OPERAND (expr, 0))
     {

-      element->ann = stmt_ann (expr);
+      element->stmt = expr;

       element->rhs = TREE_OPERAND (TREE_OPERAND (expr, 0), 1);
     }
       element->rhs = TREE_OPERAND (TREE_OPERAND (expr, 0), 1);
     }

+  else if (TREE_CODE (expr) == GOTO_EXPR)
+    {
+      element->stmt = expr;
+      element->rhs = GOTO_DESTINATION (expr);
+    }

   else
     {
   else
     {

-      element->ann = stmt_ann (expr);
+      element->stmt = expr;

       element->rhs = TREE_OPERAND (expr, 1);
     }
 
       element->rhs = TREE_OPERAND (expr, 1);
     }
 


@@ -909,10 +976,10 @@ static void
 remove_local_expressions_from_table (void)
 {
   /* Remove all the expressions made available in this block.  */
 remove_local_expressions_from_table (void)
 {
   /* Remove all the expressions made available in this block.  */

-  while (VEC_length (tree_on_heap, avail_exprs_stack) > 0)
+  while (VEC_length (tree, avail_exprs_stack) > 0)

     {
       struct expr_hash_elt element;
     {
       struct expr_hash_elt element;

-      tree expr = VEC_pop (tree_on_heap, avail_exprs_stack);
+      tree expr = VEC_pop (tree, avail_exprs_stack);

 
       if (expr == NULL_TREE)
        break;
 
       if (expr == NULL_TREE)
        break;


@@ -928,9 +995,9 @@ remove_local_expressions_from_table (void)
 static void
 restore_nonzero_vars_to_original_value (void)
 {
 static void
 restore_nonzero_vars_to_original_value (void)
 {

-  while (VEC_length (tree_on_heap, nonzero_vars_stack) > 0)
+  while (VEC_length (tree, nonzero_vars_stack) > 0)

     {
     {

-      tree name = VEC_pop (tree_on_heap, nonzero_vars_stack);
+      tree name = VEC_pop (tree, nonzero_vars_stack);

 
       if (name == NULL)
        break;
 
       if (name == NULL)
        break;


@@ -946,53 +1013,20 @@ restore_nonzero_vars_to_original_value (void)
 static void
 restore_vars_to_original_value (void)
 {
 static void
 restore_vars_to_original_value (void)
 {

-  while (VEC_length (tree_on_heap, const_and_copies_stack) > 0)
+  while (VEC_length (tree, const_and_copies_stack) > 0)

     {
       tree prev_value, dest;
 
     {
       tree prev_value, dest;
 

-      dest = VEC_pop (tree_on_heap, const_and_copies_stack);
+      dest = VEC_pop (tree, const_and_copies_stack);

 
       if (dest == NULL)
        break;
 
 
       if (dest == NULL)
        break;
 

-      prev_value = VEC_pop (tree_on_heap, const_and_copies_stack);
+      prev_value = VEC_pop (tree, const_and_copies_stack);

       SSA_NAME_VALUE (dest) =  prev_value;
     }
 }
 
       SSA_NAME_VALUE (dest) =  prev_value;
     }
 }
 

-/* Similar to restore_vars_to_original_value, except that it restores 
-   CURRDEFS to its original value.  */
-static void
-restore_currdefs_to_original_value (void)
-{
-  /* Restore CURRDEFS to its original state.  */
-  while (VEC_length (tree_on_heap, block_defs_stack) > 0)
-    {
-      tree tmp = VEC_pop (tree_on_heap, block_defs_stack);
-      tree saved_def, var;
-
-      if (tmp == NULL_TREE)
-       break;
-
-      /* If we recorded an SSA_NAME, then make the SSA_NAME the current
-        definition of its underlying variable.  If we recorded anything
-        else, it must have been an _DECL node and its current reaching
-        definition must have been NULL.  */
-      if (TREE_CODE (tmp) == SSA_NAME)
-       {
-         saved_def = tmp;
-         var = SSA_NAME_VAR (saved_def);
-       }
-      else
-       {
-         saved_def = NULL;
-         var = tmp;
-       }
-                                                                                
-      var_ann (var)->current_def = saved_def;
-    }
-}
-

 /* We have finished processing the dominator children of BB, perform
    any finalization actions in preparation for leaving this node in
    the dominator tree.  */
 /* We have finished processing the dominator children of BB, perform
    any finalization actions in preparation for leaving this node in
    the dominator tree.  */


@@ -1002,31 +1036,19 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
 {
   tree last;
 
 {
   tree last;
 

-  /* If we are at a leaf node in the dominator tree, see if we can thread
-     the edge from BB through its successor.
-
-     Do this before we remove entries from our equivalence tables.  */
+  /* If we have an outgoing edge to a block with multiple incoming and
+     outgoing edges, then we may be able to thread the edge.  ie, we
+     may be able to statically determine which of the outgoing edges
+     will be traversed when the incoming edge from BB is traversed.  */

   if (single_succ_p (bb)
       && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
   if (single_succ_p (bb)
       && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0

-      && (get_immediate_dominator (CDI_DOMINATORS, single_succ (bb)) != bb
-         || phi_nodes (single_succ (bb))))
+      && !single_pred_p (single_succ (bb))
+      && !single_succ_p (single_succ (bb)))

        
     {
       thread_across_edge (walk_data, single_succ_edge (bb));
     }
   else if ((last = last_stmt (bb))
        
     {
       thread_across_edge (walk_data, single_succ_edge (bb));
     }
   else if ((last = last_stmt (bb))

-          && TREE_CODE (last) == GOTO_EXPR
-          && TREE_CODE (TREE_OPERAND (last, 0)) == SSA_NAME)
-    {
-      edge_iterator ei;
-      edge e;
-
-      FOR_EACH_EDGE (e, ei, bb->succs)
-       {
-         thread_across_edge (walk_data, e);
-       }
-    }
-  else if ((last = last_stmt (bb))

           && TREE_CODE (last) == COND_EXPR
           && (COMPARISON_CLASS_P (COND_EXPR_COND (last))
               || TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)
           && TREE_CODE (last) == COND_EXPR
           && (COMPARISON_CLASS_P (COND_EXPR_COND (last))
               || TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)


@@ -1038,10 +1060,9 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
 
       extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
 
 
       extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
 

-      /* If the THEN arm is the end of a dominator tree or has PHI nodes,
-        then try to thread through its edge.  */
-      if (get_immediate_dominator (CDI_DOMINATORS, true_edge->dest) != bb
-         || phi_nodes (true_edge->dest))
+      /* Only try to thread the edge if it reaches a target block with
+        more than one predecessor and more than one successor.  */
+      if (!single_pred_p (true_edge->dest) && !single_succ_p (true_edge->dest))

        {
          struct edge_info *edge_info;
          unsigned int i;
        {
          struct edge_info *edge_info;
          unsigned int i;


@@ -1049,9 +1070,8 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
          /* Push a marker onto the available expression stack so that we
             unwind any expressions related to the TRUE arm before processing
             the false arm below.  */
          /* Push a marker onto the available expression stack so that we
             unwind any expressions related to the TRUE arm before processing
             the false arm below.  */

-         VEC_safe_push (tree_on_heap, avail_exprs_stack, NULL_TREE);
-         VEC_safe_push (tree_on_heap, block_defs_stack, NULL_TREE);
-         VEC_safe_push (tree_on_heap, const_and_copies_stack, NULL_TREE);
+         VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE);
+         VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);

 
          edge_info = true_edge->aux;
 
 
          edge_info = true_edge->aux;
 


@@ -1063,15 +1083,8 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
              tree lhs = edge_info->lhs;
              tree rhs = edge_info->rhs;
 
              tree lhs = edge_info->lhs;
              tree rhs = edge_info->rhs;
 

-             /* If we have a simple NAME = VALUE equivalency record it.
-                Until the jump threading selection code improves, only
-                do this if both the name and value are SSA_NAMEs with
-                the same underlying variable to avoid missing threading
-                opportunities.  */
-             if (lhs
-                 && TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME
-                 && TREE_CODE (edge_info->rhs) == SSA_NAME
-                 && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs))
+             /* If we have a simple NAME = VALUE equivalency record it.  */
+             if (lhs && TREE_CODE (lhs) == SSA_NAME)

                record_const_or_copy (lhs, rhs);
 
              /* If we have 0 = COND or 1 = COND equivalences, record them
                record_const_or_copy (lhs, rhs);
 
              /* If we have 0 = COND or 1 = COND equivalences, record them


@@ -1093,12 +1106,10 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
             we threaded this edge.  */
          remove_local_expressions_from_table ();
          restore_vars_to_original_value ();
             we threaded this edge.  */
          remove_local_expressions_from_table ();
          restore_vars_to_original_value ();

-         restore_currdefs_to_original_value ();

        }
 
       /* Similarly for the ELSE arm.  */
        }
 
       /* Similarly for the ELSE arm.  */

-      if (get_immediate_dominator (CDI_DOMINATORS, false_edge->dest) != bb
-         || phi_nodes (false_edge->dest))
+      if (!single_pred_p (false_edge->dest) && !single_succ_p (false_edge->dest))

        {
          struct edge_info *edge_info;
          unsigned int i;
        {
          struct edge_info *edge_info;
          unsigned int i;


@@ -1113,13 +1124,8 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
              tree lhs = edge_info->lhs;
              tree rhs = edge_info->rhs;
 
              tree lhs = edge_info->lhs;
              tree rhs = edge_info->rhs;
 

-             /* If we have a simple NAME = VALUE equivalency record it.
-                Until the jump threading selection code improves, only
-                do this if both the name and value are SSA_NAMEs with
-                the same underlying variable to avoid missing threading
-                opportunities.  */
-             if (lhs
-                 && TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)
+             /* If we have a simple NAME = VALUE equivalency record it.  */
+             if (lhs && TREE_CODE (lhs) == SSA_NAME)

                record_const_or_copy (lhs, rhs);
 
              /* If we have 0 = COND or 1 = COND equivalences, record them
                record_const_or_copy (lhs, rhs);
 
              /* If we have 0 = COND or 1 = COND equivalences, record them


@@ -1145,7 +1151,6 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
   remove_local_expressions_from_table ();
   restore_nonzero_vars_to_original_value ();
   restore_vars_to_original_value ();
   remove_local_expressions_from_table ();
   restore_nonzero_vars_to_original_value ();
   restore_vars_to_original_value ();

-  restore_currdefs_to_original_value ();

 
   /* Remove VRP records associated with this basic block.  They are no
      longer valid.
 
   /* Remove VRP records associated with this basic block.  They are no
      longer valid.


@@ -1153,9 +1158,9 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
      To be efficient, we note which variables have had their values
      constrained in this block.  So walk over each variable in the
      VRP_VARIABLEs array.  */
      To be efficient, we note which variables have had their values
      constrained in this block.  So walk over each variable in the
      VRP_VARIABLEs array.  */

-  while (VEC_length (tree_on_heap, vrp_variables_stack) > 0)
+  while (VEC_length (tree, vrp_variables_stack) > 0)

     {
     {

-      tree var = VEC_pop (tree_on_heap, vrp_variables_stack);
+      tree var = VEC_pop (tree, vrp_variables_stack);

       struct vrp_hash_elt vrp_hash_elt, *vrp_hash_elt_p;
       void **slot;
 
       struct vrp_hash_elt vrp_hash_elt, *vrp_hash_elt_p;
       void **slot;
 


@@ -1164,7 +1169,7 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
         the array backwards popping off records associated with our
         block.  Once we hit a record not associated with our block
         we are done.  */
         the array backwards popping off records associated with our
         block.  Once we hit a record not associated with our block
         we are done.  */

-      varray_type var_vrp_records;
+      VEC(vrp_element_p,heap) **var_vrp_records;

 
       if (var == NULL)
        break;
 
       if (var == NULL)
        break;


@@ -1175,32 +1180,32 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
       slot = htab_find_slot (vrp_data, &vrp_hash_elt, NO_INSERT);
 
       vrp_hash_elt_p = (struct vrp_hash_elt *) *slot;
       slot = htab_find_slot (vrp_data, &vrp_hash_elt, NO_INSERT);
 
       vrp_hash_elt_p = (struct vrp_hash_elt *) *slot;

-      var_vrp_records = vrp_hash_elt_p->records;
+      var_vrp_records = &vrp_hash_elt_p->records;

 
 

-      while (VARRAY_ACTIVE_SIZE (var_vrp_records) > 0)
+      while (VEC_length (vrp_element_p, *var_vrp_records) > 0)

        {
          struct vrp_element *element
        {
          struct vrp_element *element

-           = (struct vrp_element *)VARRAY_TOP_GENERIC_PTR (var_vrp_records);
+           = VEC_last (vrp_element_p, *var_vrp_records);

 
          if (element->bb != bb)
            break;
   
 
          if (element->bb != bb)
            break;
   

-         VARRAY_POP (var_vrp_records);
+         VEC_pop (vrp_element_p, *var_vrp_records);

        }
     }
 
   /* If we queued any statements to rescan in this block, then
      go ahead and rescan them now.  */
        }
     }
 
   /* If we queued any statements to rescan in this block, then
      go ahead and rescan them now.  */

-  while (VEC_length (tree_on_heap, stmts_to_rescan) > 0)
+  while (VEC_length (tree, stmts_to_rescan) > 0)

     {
     {

-      tree stmt = VEC_last (tree_on_heap, stmts_to_rescan);
+      tree stmt = VEC_last (tree, stmts_to_rescan);

       basic_block stmt_bb = bb_for_stmt (stmt);
 
       if (stmt_bb != bb)
        break;
 
       basic_block stmt_bb = bb_for_stmt (stmt);
 
       if (stmt_bb != bb)
        break;
 

-      VEC_pop (tree_on_heap, stmts_to_rescan);
-      mark_new_vars_to_rename (stmt, vars_to_rename);
+      VEC_pop (tree, stmts_to_rescan);
+      mark_new_vars_to_rename (stmt);

     }
 }
 
     }
 }
 


@@ -1271,8 +1276,6 @@ record_equivalences_from_phis (basic_block bb)
 
       if (i == PHI_NUM_ARGS (phi))
        bitmap_set_bit (nonzero_vars, SSA_NAME_VERSION (PHI_RESULT (phi)));
 
       if (i == PHI_NUM_ARGS (phi))
        bitmap_set_bit (nonzero_vars, SSA_NAME_VERSION (PHI_RESULT (phi)));

-
-      register_new_def (lhs, &block_defs_stack);

     }
 }
 
     }
 }
 


@@ -1386,6 +1389,13 @@ dump_dominator_optimization_stats (FILE *file)
   fprintf (file, "    Redundant expressions eliminated:         %6ld (%.0f%%)\n",
           opt_stats.num_re, PERCENT (opt_stats.num_re,
                                      n_exprs));
   fprintf (file, "    Redundant expressions eliminated:         %6ld (%.0f%%)\n",
           opt_stats.num_re, PERCENT (opt_stats.num_re,
                                      n_exprs));

+  fprintf (file, "    Constants propagated:                     %6ld\n",
+          opt_stats.num_const_prop);
+  fprintf (file, "    Copies propagated:                        %6ld\n",
+          opt_stats.num_copy_prop);
+
+  fprintf (file, "\nTotal number of DOM iterations:             %6ld\n",
+          opt_stats.num_iterations);

 
   fprintf (file, "\nHash table statistics:\n");
 
 
   fprintf (file, "\nHash table statistics:\n");
 


@@ -1431,7 +1441,7 @@ record_var_is_nonzero (tree var)
 
   /* Record this SSA_NAME so that we can reset the global table
      when we leave this block.  */
 
   /* Record this SSA_NAME so that we can reset the global table
      when we leave this block.  */

-  VEC_safe_push (tree_on_heap, nonzero_vars_stack, var);
+  VEC_safe_push (tree, heap, nonzero_vars_stack, var);

 }
 
 /* Enter a statement into the true/false expression hash table indicating
 }
 
 /* Enter a statement into the true/false expression hash table indicating


@@ -1450,7 +1460,7 @@ record_cond (tree cond, tree value)
   if (*slot == NULL)
     {
       *slot = (void *) element;
   if (*slot == NULL)
     {
       *slot = (void *) element;

-      VEC_safe_push (tree_on_heap, avail_exprs_stack, cond);
+      VEC_safe_push (tree, heap, avail_exprs_stack, cond);

     }
   else
     free (element);
     }
   else
     free (element);


@@ -1589,8 +1599,9 @@ record_const_or_copy_1 (tree x, tree y, tree prev_x)
 {
   SSA_NAME_VALUE (x) = y;
 
 {
   SSA_NAME_VALUE (x) = y;
 

-  VEC_safe_push (tree_on_heap, const_and_copies_stack, prev_x);
-  VEC_safe_push (tree_on_heap, const_and_copies_stack, x);
+  VEC_reserve (tree, heap, const_and_copies_stack, 2);
+  VEC_quick_push (tree, const_and_copies_stack, prev_x);
+  VEC_quick_push (tree, const_and_copies_stack, x);

 }
 
 
 }
 
 


@@ -1600,7 +1611,7 @@ record_const_or_copy_1 (tree x, tree y, tree prev_x)
    will be relatively correct, and as more passes are taught to keep loop info
    up to date, the result will become more and more accurate.  */
 
    will be relatively correct, and as more passes are taught to keep loop info
    up to date, the result will become more and more accurate.  */
 

-static int
+int

 loop_depth_of_name (tree x)
 {
   tree defstmt;
 loop_depth_of_name (tree x)
 {
   tree defstmt;


@@ -1743,8 +1754,7 @@ simple_iv_increment_p (tree stmt)
    the hash table and return the result.  Otherwise return NULL.  */
 
 static tree
    the hash table and return the result.  Otherwise return NULL.  */
 
 static tree

-simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *walk_data,
-                                   tree stmt, int insert)
+simplify_rhs_and_lookup_avail_expr (tree stmt, int insert)

 {
   tree rhs = TREE_OPERAND (stmt, 1);
   enum tree_code rhs_code = TREE_CODE (rhs);
 {
   tree rhs = TREE_OPERAND (stmt, 1);
   enum tree_code rhs_code = TREE_CODE (rhs);


@@ -1784,6 +1794,7 @@ simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *walk_data,
      assignment.  Add minus to this, as we handle it specially below.  */
   if ((associative_tree_code (rhs_code) || rhs_code == MINUS_EXPR)
       && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
      assignment.  Add minus to this, as we handle it specially below.  */
   if ((associative_tree_code (rhs_code) || rhs_code == MINUS_EXPR)
       && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME

+      && num_imm_uses (TREE_OPERAND (rhs, 0)) == 1

       && is_gimple_min_invariant (TREE_OPERAND (rhs, 1)))
     {
       tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
       && is_gimple_min_invariant (TREE_OPERAND (rhs, 1)))
     {
       tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));


@@ -1840,17 +1851,17 @@ simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *walk_data,
                  if (rhs_def_code != rhs_code)
                    {
                      if (rhs_def_code == MINUS_EXPR)
                  if (rhs_def_code != rhs_code)
                    {
                      if (rhs_def_code == MINUS_EXPR)

-                       t = build (MINUS_EXPR, type, outer_const, def_stmt_op1);
+                       t = build2 (MINUS_EXPR, type, outer_const, def_stmt_op1);

                      else
                      else

-                       t = build (MINUS_EXPR, type, def_stmt_op1, outer_const);
+                       t = build2 (MINUS_EXPR, type, def_stmt_op1, outer_const);

                      rhs_code = PLUS_EXPR;
                    }
                  else if (rhs_def_code == MINUS_EXPR)
                      rhs_code = PLUS_EXPR;
                    }
                  else if (rhs_def_code == MINUS_EXPR)

-                   t = build (PLUS_EXPR, type, def_stmt_op1, outer_const);
+                   t = build2 (PLUS_EXPR, type, def_stmt_op1, outer_const);

                  else
                  else

-                   t = build (rhs_def_code, type, def_stmt_op1, outer_const);
+                   t = build2 (rhs_def_code, type, def_stmt_op1, outer_const);

                  t = local_fold (t);
                  t = local_fold (t);

-                 t = build (rhs_code, type, def_stmt_op0, t);
+                 t = build2 (rhs_code, type, def_stmt_op0, t);

                  t = local_fold (t);
 
                  /* If the result is a suitable looking gimple expression,
                  t = local_fold (t);
 
                  /* If the result is a suitable looking gimple expression,


@@ -1868,127 +1879,6 @@ simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *walk_data,
  dont_fold_assoc:;
     }
 
  dont_fold_assoc:;
     }
 

-  /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
-     and BIT_AND_EXPR respectively if the first operand is greater
-     than zero and the second operand is an exact power of two.  */
-  if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
-      && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
-      && integer_pow2p (TREE_OPERAND (rhs, 1)))
-    {
-      tree val;
-      tree op = TREE_OPERAND (rhs, 0);
-
-      if (TYPE_UNSIGNED (TREE_TYPE (op)))
-       {
-         val = integer_one_node;
-       }
-      else
-       {
-         tree dummy_cond = walk_data->global_data;
-
-         if (! dummy_cond)
-           {
-             dummy_cond = build (GT_EXPR, boolean_type_node,
-                                 op, integer_zero_node);
-             dummy_cond = build (COND_EXPR, void_type_node,
-                                 dummy_cond, NULL, NULL);
-             walk_data->global_data = dummy_cond;
-           }
-          else
-           {
-             TREE_SET_CODE (COND_EXPR_COND (dummy_cond), GT_EXPR);
-             TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op;
-             TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1)
-               = integer_zero_node;
-           }
-         val = simplify_cond_and_lookup_avail_expr (dummy_cond, NULL, false);
-       }
-
-      if (val && integer_onep (val))
-       {
-         tree t;
-         tree op0 = TREE_OPERAND (rhs, 0);
-         tree op1 = TREE_OPERAND (rhs, 1);
-
-         if (rhs_code == TRUNC_DIV_EXPR)
-           t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0,
-                      build_int_cst (NULL_TREE, tree_log2 (op1)));
-         else
-           t = build (BIT_AND_EXPR, TREE_TYPE (op0), op0,
-                      local_fold (build (MINUS_EXPR, TREE_TYPE (op1),
-                                         op1, integer_one_node)));
-
-         result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
-       }
-    }
-
-  /* Transform ABS (X) into X or -X as appropriate.  */
-  if (rhs_code == ABS_EXPR
-      && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
-    {
-      tree val;
-      tree op = TREE_OPERAND (rhs, 0);
-      tree type = TREE_TYPE (op);
-
-      if (TYPE_UNSIGNED (type))
-       {
-         val = integer_zero_node;
-       }
-      else
-       {
-         tree dummy_cond = walk_data->global_data;
-
-         if (! dummy_cond)
-           {
-             dummy_cond = build (LE_EXPR, boolean_type_node,
-                                 op, integer_zero_node);
-             dummy_cond = build (COND_EXPR, void_type_node,
-                                 dummy_cond, NULL, NULL);
-             walk_data->global_data = dummy_cond;
-           }
-         else
-           {
-             TREE_SET_CODE (COND_EXPR_COND (dummy_cond), LE_EXPR);
-             TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op;
-             TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1)
-               = build_int_cst (type, 0);
-           }
-         val = simplify_cond_and_lookup_avail_expr (dummy_cond, NULL, false);
-
-         if (!val)
-           {
-             TREE_SET_CODE (COND_EXPR_COND (dummy_cond), GE_EXPR);
-             TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op;
-             TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1)
-               = build_int_cst (type, 0);
-
-             val = simplify_cond_and_lookup_avail_expr (dummy_cond,
-                                                        NULL, false);
-
-             if (val)
-               {
-                 if (integer_zerop (val))
-                   val = integer_one_node;
-                 else if (integer_onep (val))
-                   val = integer_zero_node;
-               }
-           }
-       }
-
-      if (val
-         && (integer_onep (val) || integer_zerop (val)))
-       {
-         tree t;
-
-         if (integer_onep (val))
-           t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
-         else
-           t = op;
-
-         result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
-       }
-    }
-

   /* Optimize *"foo" into 'f'.  This is done here rather than
      in fold to avoid problems with stuff like &*"foo".  */
   if (TREE_CODE (rhs) == INDIRECT_REF || TREE_CODE (rhs) == ARRAY_REF)
   /* Optimize *"foo" into 'f'.  This is done here rather than
      in fold to avoid problems with stuff like &*"foo".  */
   if (TREE_CODE (rhs) == INDIRECT_REF || TREE_CODE (rhs) == ARRAY_REF)


@@ -2034,6 +1924,18 @@ find_equivalent_equality_comparison (tree cond)
     {
       tree def_rhs = TREE_OPERAND (def_stmt, 1);
 
     {
       tree def_rhs = TREE_OPERAND (def_stmt, 1);
 

+
+      /* If either operand to the comparison is a pointer to
+        a function, then we can not apply this optimization
+        as some targets require function pointers to be
+        canonicalized and in this case this optimization would
+        eliminate a necessary canonicalization.  */
+      if ((POINTER_TYPE_P (TREE_TYPE (op0))
+          && TREE_CODE (TREE_TYPE (TREE_TYPE (op0))) == FUNCTION_TYPE)
+         || (POINTER_TYPE_P (TREE_TYPE (op1))
+             && TREE_CODE (TREE_TYPE (TREE_TYPE (op1))) == FUNCTION_TYPE))
+       return NULL;
+             

       /* Now make sure the RHS of the MODIFY_EXPR is a typecast.  */
       if ((TREE_CODE (def_rhs) == NOP_EXPR
           || TREE_CODE (def_rhs) == CONVERT_EXPR)
       /* Now make sure the RHS of the MODIFY_EXPR is a typecast.  */
       if ((TREE_CODE (def_rhs) == NOP_EXPR
           || TREE_CODE (def_rhs) == CONVERT_EXPR)


@@ -2047,6 +1949,16 @@ find_equivalent_equality_comparison (tree cond)
              > TYPE_PRECISION (TREE_TYPE (def_rhs)))
            return NULL;
 
              > TYPE_PRECISION (TREE_TYPE (def_rhs)))
            return NULL;
 

+         /* If the inner type of the conversion is a pointer to
+            a function, then we can not apply this optimization
+            as some targets require function pointers to be
+            canonicalized.  This optimization would result in
+            canonicalization of the pointer when it was not originally
+            needed/intended.  */
+         if (POINTER_TYPE_P (def_rhs_inner_type)
+             && TREE_CODE (TREE_TYPE (def_rhs_inner_type)) == FUNCTION_TYPE)
+           return NULL;
+

          /* What we want to prove is that if we convert OP1 to
             the type of the object inside the NOP_EXPR that the
             result is still equivalent to SRC. 
          /* What we want to prove is that if we convert OP1 to
             the type of the object inside the NOP_EXPR that the
             result is still equivalent to SRC. 


@@ -2057,8 +1969,8 @@ find_equivalent_equality_comparison (tree cond)
          new = build1 (TREE_CODE (def_rhs), def_rhs_inner_type, op1);
          new = local_fold (new);
          if (is_gimple_val (new) && tree_int_cst_equal (new, op1))
          new = build1 (TREE_CODE (def_rhs), def_rhs_inner_type, op1);
          new = local_fold (new);
          if (is_gimple_val (new) && tree_int_cst_equal (new, op1))

-           return build (TREE_CODE (cond), TREE_TYPE (cond),
-                         def_rhs_inner, new);
+           return build2 (TREE_CODE (cond), TREE_TYPE (cond),
+                          def_rhs_inner, new);

        }
     }
   return NULL;
        }
     }
   return NULL;


@@ -2086,7 +1998,7 @@ simplify_cond_and_lookup_avail_expr (tree stmt,
          int limit;
          tree low, high, cond_low, cond_high;
          int lowequal, highequal, swapped, no_overlap, subset, cond_inverted;
          int limit;
          tree low, high, cond_low, cond_high;
          int lowequal, highequal, swapped, no_overlap, subset, cond_inverted;

-         varray_type vrp_records;
+         VEC(vrp_element_p,heap) **vrp_records;

          struct vrp_element *element;
          struct vrp_hash_elt vrp_hash_elt, *vrp_hash_elt_p;
          void **slot;
          struct vrp_element *element;
          struct vrp_hash_elt vrp_hash_elt, *vrp_hash_elt_p;
          void **slot;


@@ -2139,11 +2051,9 @@ simplify_cond_and_lookup_avail_expr (tree stmt,
            return NULL;
 
          vrp_hash_elt_p = (struct vrp_hash_elt *) *slot;
            return NULL;
 
          vrp_hash_elt_p = (struct vrp_hash_elt *) *slot;

-         vrp_records = vrp_hash_elt_p->records;
-         if (vrp_records == NULL)
-           return NULL;
+         vrp_records = &vrp_hash_elt_p->records;

 
 

-         limit = VARRAY_ACTIVE_SIZE (vrp_records);
+         limit = VEC_length (vrp_element_p, *vrp_records);

 
          /* If we have no value range records for this variable, or we are
             unable to extract a range for this condition, then there is
 
          /* If we have no value range records for this variable, or we are
             unable to extract a range for this condition, then there is


@@ -2175,8 +2085,7 @@ simplify_cond_and_lookup_avail_expr (tree stmt,
             conditional into the current range. 
 
             These properties also help us avoid unnecessary work.  */
             conditional into the current range. 
 
             These properties also help us avoid unnecessary work.  */

-          element
-            = (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records, limit - 1);
+          element = VEC_last (vrp_element_p, *vrp_records);

 
          if (element->high && element->low)
            {
 
          if (element->high && element->low)
            {


@@ -2215,8 +2124,7 @@ simplify_cond_and_lookup_avail_expr (tree stmt,
                {
                  /* Get the high/low value from the previous element.  */
                  struct vrp_element *prev
                {
                  /* Get the high/low value from the previous element.  */
                  struct vrp_element *prev

-                   = (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records,
-                                                               limit - 2);
+                   = VEC_index (vrp_element_p, *vrp_records, limit - 2);

                  low = prev->low;
                  high = prev->high;
 
                  low = prev->low;
                  high = prev->high;
 


@@ -2229,9 +2137,9 @@ simplify_cond_and_lookup_avail_expr (tree stmt,
                     Similarly the high value for the merged range is the
                     minimum of the previous high value and the high value of
                     this record.  */
                     Similarly the high value for the merged range is the
                     minimum of the previous high value and the high value of
                     this record.  */

-                 low = (tree_int_cst_compare (low, tmp_low) == 1
+                 low = (low && tree_int_cst_compare (low, tmp_low) == 1

                         ? low : tmp_low);
                         ? low : tmp_low);

-                 high = (tree_int_cst_compare (high, tmp_high) == -1
+                 high = (high && tree_int_cst_compare (high, tmp_high) == -1

                          ? high : tmp_high);
                }
 
                          ? high : tmp_high);
                }
 


@@ -2424,12 +2332,11 @@ cprop_into_successor_phis (basic_block bb, bitmap nonzero_vars)
             ORIG_P with its value in our constant/copy table.  */
          new = SSA_NAME_VALUE (orig);
          if (new
             ORIG_P with its value in our constant/copy table.  */
          new = SSA_NAME_VALUE (orig);
          if (new

+             && new != orig

              && (TREE_CODE (new) == SSA_NAME
                  || is_gimple_min_invariant (new))
              && may_propagate_copy (orig, new))
              && (TREE_CODE (new) == SSA_NAME
                  || is_gimple_min_invariant (new))
              && may_propagate_copy (orig, new))

-           {
-             propagate_value (orig_p, new);
-           }
+           propagate_value (orig_p, new);

        }
     }
 }
        }
     }
 }


@@ -2455,7 +2362,7 @@ record_edge_info (basic_block bb)
            {
              tree labels = SWITCH_LABELS (stmt);
              int i, n_labels = TREE_VEC_LENGTH (labels);
            {
              tree labels = SWITCH_LABELS (stmt);
              int i, n_labels = TREE_VEC_LENGTH (labels);

-             tree *info = xcalloc (n_basic_blocks, sizeof (tree));
+             tree *info = xcalloc (last_basic_block, sizeof (tree));

              edge e;
              edge_iterator ei;
 
              edge e;
              edge_iterator ei;
 


@@ -2624,7 +2531,6 @@ static void
 propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
                             basic_block bb)
 {
 propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
                             basic_block bb)
 {

-  

   record_edge_info (bb);
   cprop_into_successor_phis (bb, nonzero_vars);
 }
   record_edge_info (bb);
   cprop_into_successor_phis (bb, nonzero_vars);
 }


@@ -2636,14 +2542,13 @@ propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
    table.  */
 
 static bool
    table.  */
 
 static bool

-eliminate_redundant_computations (struct dom_walk_data *walk_data,
-                                 tree stmt, stmt_ann_t ann)
+eliminate_redundant_computations (tree stmt, stmt_ann_t ann)

 {
 {

-  v_may_def_optype v_may_defs = V_MAY_DEF_OPS (ann);

   tree *expr_p, def = NULL_TREE;
   bool insert = true;
   tree cached_lhs;
   bool retval = false;
   tree *expr_p, def = NULL_TREE;
   bool insert = true;
   tree cached_lhs;
   bool retval = false;

+  bool modify_expr_p = false;

 
   if (TREE_CODE (stmt) == MODIFY_EXPR)
     def = TREE_OPERAND (stmt, 0);
 
   if (TREE_CODE (stmt) == MODIFY_EXPR)
     def = TREE_OPERAND (stmt, 0);


@@ -2654,7 +2559,7 @@ eliminate_redundant_computations (struct dom_walk_data *walk_data,
       || ! def
       || TREE_CODE (def) != SSA_NAME
       || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
       || ! def
       || TREE_CODE (def) != SSA_NAME
       || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)

-      || NUM_V_MAY_DEFS (v_may_defs) != 0
+      || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF)

       /* Do not record equivalences for increments of ivs.  This would create
         overlapping live ranges for a very questionable gain.  */
       || simple_iv_increment_p (stmt))
       /* Do not record equivalences for increments of ivs.  This would create
         overlapping live ranges for a very questionable gain.  */
       || simple_iv_increment_p (stmt))


@@ -2667,7 +2572,7 @@ eliminate_redundant_computations (struct dom_walk_data *walk_data,
      then try to simplify the RHS and lookup the new RHS in the
      hash table.  */
   if (! cached_lhs && TREE_CODE (stmt) == MODIFY_EXPR)
      then try to simplify the RHS and lookup the new RHS in the
      hash table.  */
   if (! cached_lhs && TREE_CODE (stmt) == MODIFY_EXPR)

-    cached_lhs = simplify_rhs_and_lookup_avail_expr (walk_data, stmt, insert);
+    cached_lhs = simplify_rhs_and_lookup_avail_expr (stmt, insert);

   /* Similarly if this is a COND_EXPR and we did not find its
      expression in the hash table, simplify the condition and
      try again.  */
   /* Similarly if this is a COND_EXPR and we did not find its
      expression in the hash table, simplify the condition and
      try again.  */


@@ -2685,9 +2590,15 @@ eliminate_redundant_computations (struct dom_walk_data *walk_data,
   else if (TREE_CODE (stmt) == SWITCH_EXPR)
     expr_p = &SWITCH_COND (stmt);
   else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0))
   else if (TREE_CODE (stmt) == SWITCH_EXPR)
     expr_p = &SWITCH_COND (stmt);
   else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0))

-    expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
+    {
+      expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
+      modify_expr_p = true;
+    }

   else
   else

-    expr_p = &TREE_OPERAND (stmt, 1);
+    {
+      expr_p = &TREE_OPERAND (stmt, 1);
+      modify_expr_p = true;
+    }

 
   /* It is safe to ignore types here since we have already done
      type checking in the hashing and equality routines.  In fact
 
   /* It is safe to ignore types here since we have already done
      type checking in the hashing and equality routines.  In fact


@@ -2695,7 +2606,10 @@ eliminate_redundant_computations (struct dom_walk_data *walk_data,
      propagation.  Also, make sure that it is safe to propagate
      CACHED_LHS into *EXPR_P.  */
   if (cached_lhs
      propagation.  Also, make sure that it is safe to propagate
      CACHED_LHS into *EXPR_P.  */
   if (cached_lhs

-      && (TREE_CODE (cached_lhs) != SSA_NAME
+      && ((TREE_CODE (cached_lhs) != SSA_NAME
+          && (modify_expr_p
+              || tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p),
+                                                     TREE_TYPE (cached_lhs))))

          || may_propagate_copy (*expr_p, cached_lhs)))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
          || may_propagate_copy (*expr_p, cached_lhs)))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))


@@ -2718,6 +2632,11 @@ eliminate_redundant_computations (struct dom_walk_data *walk_data,
          || (POINTER_TYPE_P (TREE_TYPE (*expr_p))
              && is_gimple_min_invariant (cached_lhs)))
        retval = true;
          || (POINTER_TYPE_P (TREE_TYPE (*expr_p))
              && is_gimple_min_invariant (cached_lhs)))
        retval = true;

+      
+      if (modify_expr_p
+         && !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p),
+                                                 TREE_TYPE (cached_lhs)))
+       cached_lhs = fold_convert (TREE_TYPE (*expr_p), cached_lhs);

 
       propagate_tree_value (expr_p, cached_lhs);
       mark_stmt_modified (stmt);
 
       propagate_tree_value (expr_p, cached_lhs);
       mark_stmt_modified (stmt);


@@ -2756,24 +2675,7 @@ record_equivalences_from_stmt (tree stmt,
              || is_gimple_min_invariant (rhs)))
        SSA_NAME_VALUE (lhs) = rhs;
 
              || is_gimple_min_invariant (rhs)))
        SSA_NAME_VALUE (lhs) = rhs;
 

-      /* alloca never returns zero and the address of a non-weak symbol
-        is never zero.  NOP_EXPRs and CONVERT_EXPRs can be completely
-        stripped as they do not affect this equivalence.  */
-      while (TREE_CODE (rhs) == NOP_EXPR
-            || TREE_CODE (rhs) == CONVERT_EXPR)
-        rhs = TREE_OPERAND (rhs, 0);
-
-      if (alloca_call_p (rhs)
-          || (TREE_CODE (rhs) == ADDR_EXPR
-             && DECL_P (TREE_OPERAND (rhs, 0))
-             && ! DECL_WEAK (TREE_OPERAND (rhs, 0))))
-       record_var_is_nonzero (lhs);
-
-      /* 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)))
+      if (tree_expr_nonzero_p (rhs))

        record_var_is_nonzero (lhs);
     }
 
        record_var_is_nonzero (lhs);
     }
 


@@ -2850,9 +2752,9 @@ record_equivalences_from_stmt (tree stmt,
       if (rhs)
        {
          /* Build a new statement with the RHS and LHS exchanged.  */
       if (rhs)
        {
          /* Build a new statement with the RHS and LHS exchanged.  */

-         new = build (MODIFY_EXPR, TREE_TYPE (stmt), rhs, lhs);
+         new = build2 (MODIFY_EXPR, TREE_TYPE (stmt), rhs, lhs);

 
 

-         create_ssa_artficial_load_stmt (&(ann->operands), new);
+         create_ssa_artficial_load_stmt (new, stmt);

 
          /* Finally enter the statement into the available expression
             table.  */
 
          /* Finally enter the statement into the available expression
             table.  */


@@ -2875,7 +2777,7 @@ cprop_operand (tree stmt, use_operand_p op_p)
      copy of some other variable, use the value or copy stored in
      CONST_AND_COPIES.  */
   val = SSA_NAME_VALUE (op);
      copy of some other variable, use the value or copy stored in
      CONST_AND_COPIES.  */
   val = SSA_NAME_VALUE (op);

-  if (val && TREE_CODE (val) != VALUE_HANDLE)
+  if (val && val != op && TREE_CODE (val) != VALUE_HANDLE)

     {
       tree op_type, val_type;
 
     {
       tree op_type, val_type;
 


@@ -2885,8 +2787,9 @@ cprop_operand (tree stmt, use_operand_p op_p)
         statement.  Also only allow the new value to be an SSA_NAME
         for propagation into virtual operands.  */
       if (!is_gimple_reg (op)
         statement.  Also only allow the new value to be an SSA_NAME
         for propagation into virtual operands.  */
       if (!is_gimple_reg (op)

-         && (get_virtual_var (val) != get_virtual_var (op)
-             || TREE_CODE (val) != SSA_NAME))
+         && (TREE_CODE (val) != SSA_NAME
+             || is_gimple_reg (val)
+             || get_virtual_var (val) != get_virtual_var (op)))

        return false;
 
       /* Do not replace hard register operands in asm statements.  */
        return false;
 
       /* Do not replace hard register operands in asm statements.  */


@@ -2952,6 +2855,11 @@ cprop_operand (tree stmt, use_operand_p op_p)
              && is_gimple_min_invariant (val)))
        may_have_exposed_new_symbols = true;
 
              && is_gimple_min_invariant (val)))
        may_have_exposed_new_symbols = true;
 

+      if (TREE_CODE (val) != SSA_NAME)
+       opt_stats.num_const_prop++;
+      else
+       opt_stats.num_copy_prop++;
+

       propagate_value (op_p, val);
 
       /* And note that we modified this statement.  This is now
       propagate_value (op_p, val);
 
       /* And note that we modified this statement.  This is now


@@ -2974,7 +2882,6 @@ cprop_into_stmt (tree stmt)
   bool may_have_exposed_new_symbols = false;
   use_operand_p op_p;
   ssa_op_iter iter;
   bool may_have_exposed_new_symbols = false;
   use_operand_p op_p;
   ssa_op_iter iter;

-  tree rhs;

 
   FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
     {
 
   FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
     {


@@ -2982,18 +2889,11 @@ cprop_into_stmt (tree stmt)
        may_have_exposed_new_symbols |= cprop_operand (stmt, op_p);
     }
 
        may_have_exposed_new_symbols |= cprop_operand (stmt, op_p);
     }
 

-  if (may_have_exposed_new_symbols)
-    {
-      rhs = get_rhs (stmt);
-      if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
-       recompute_tree_invarant_for_addr_expr (rhs);
-    }
-

   return may_have_exposed_new_symbols;
 }
 
 
   return may_have_exposed_new_symbols;
 }
 
 

-/* Optimize the statement pointed by iterator SI.
+/* Optimize the statement pointed to by iterator SI.

    
    We try to perform some simplistic global redundancy elimination and
    constant propagation:
    
    We try to perform some simplistic global redundancy elimination and
    constant propagation:


@@ -3009,15 +2909,15 @@ cprop_into_stmt (tree stmt)
       the variable in the LHS in the CONST_AND_COPIES table.  */
 
 static void
       the variable in the LHS in the CONST_AND_COPIES table.  */
 
 static void

-optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
-              block_stmt_iterator si)
+optimize_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+              basic_block bb, block_stmt_iterator si)

 {
   stmt_ann_t ann;
 {
   stmt_ann_t ann;

-  tree stmt;
+  tree stmt, old_stmt;

   bool may_optimize_p;
   bool may_have_exposed_new_symbols = false;
 
   bool may_optimize_p;
   bool may_have_exposed_new_symbols = false;
 

-  stmt = bsi_stmt (si);
+  old_stmt = stmt = bsi_stmt (si);

 
   update_stmt_if_modified (stmt);
   ann = stmt_ann (stmt);
 
   update_stmt_if_modified (stmt);
   ann = stmt_ann (stmt);


@@ -3037,6 +2937,8 @@ optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
      fold its RHS before checking for redundant computations.  */
   if (ann->modified)
     {
      fold its RHS before checking for redundant computations.  */
   if (ann->modified)
     {

+      tree rhs;
+

       /* Try to fold the statement making sure that STMT is kept
         up to date.  */
       if (fold_stmt (bsi_stmt_ptr (si)))
       /* Try to fold the statement making sure that STMT is kept
         up to date.  */
       if (fold_stmt (bsi_stmt_ptr (si)))


@@ -3051,6 +2953,10 @@ optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
            }
        }
 
            }
        }
 

+      rhs = get_rhs (stmt);
+      if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
+       recompute_tree_invarant_for_addr_expr (rhs);
+

       /* Constant/copy propagation above may change the set of 
         virtual operands associated with this statement.  Folding
         may remove the need for some virtual operands.
       /* Constant/copy propagation above may change the set of 
         virtual operands associated with this statement.  Folding
         may remove the need for some virtual operands.


@@ -3074,7 +2980,7 @@ optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
 
   if (may_optimize_p)
     may_have_exposed_new_symbols
 
   if (may_optimize_p)
     may_have_exposed_new_symbols

-      |= eliminate_redundant_computations (walk_data, stmt, ann);
+      |= eliminate_redundant_computations (stmt, ann);

 
   /* Record any additional equivalences created by this statement.  */
   if (TREE_CODE (stmt) == MODIFY_EXPR)
 
   /* Record any additional equivalences created by this statement.  */
   if (TREE_CODE (stmt) == MODIFY_EXPR)


@@ -3082,8 +2988,6 @@ optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
                                   may_optimize_p,
                                   ann);
 
                                   may_optimize_p,
                                   ann);
 

-  register_definitions_for_stmt (stmt);
-

   /* If STMT is a COND_EXPR and it was modified, then we may know
      where it goes.  If that is the case, then mark the CFG as altered.
 
   /* If STMT is a COND_EXPR and it was modified, then we may know
      where it goes.  If that is the case, then mark the CFG as altered.
 


@@ -3124,7 +3028,7 @@ optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
 
       /* If we simplified a statement in such a way as to be shown that it
         cannot trap, update the eh information and the cfg to match.  */
 
       /* If we simplified a statement in such a way as to be shown that it
         cannot trap, update the eh information and the cfg to match.  */

-      if (maybe_clean_eh_stmt (stmt))
+      if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))

        {
          bitmap_set_bit (need_eh_cleanup, bb->index);
          if (dump_file && (dump_flags & TDF_DETAILS))
        {
          bitmap_set_bit (need_eh_cleanup, bb->index);
          if (dump_file && (dump_flags & TDF_DETAILS))


@@ -3133,7 +3037,7 @@ optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
     }
 
   if (may_have_exposed_new_symbols)
     }
 
   if (may_have_exposed_new_symbols)

-    VEC_safe_push (tree_on_heap, stmts_to_rescan, bsi_stmt (si));
+    VEC_safe_push (tree, heap, stmts_to_rescan, bsi_stmt (si));

 }
 
 /* Replace the RHS of STMT with NEW_RHS.  If RHS can be found in the
 }
 
 /* Replace the RHS of STMT with NEW_RHS.  If RHS can be found in the


@@ -3185,7 +3089,7 @@ update_rhs_and_lookup_avail_expr (tree stmt, tree new_rhs, bool insert)
      we found a copy of this statement in the second hash table lookup
      we want _no_ copies of this statement in BLOCK_AVAIL_EXPRs.  */
   if (insert)
      we found a copy of this statement in the second hash table lookup
      we want _no_ copies of this statement in BLOCK_AVAIL_EXPRs.  */
   if (insert)

-    VEC_pop (tree_on_heap, avail_exprs_stack);
+    VEC_pop (tree, avail_exprs_stack);

 
   /* And make sure we record the fact that we modified this
      statement.  */
 
   /* And make sure we record the fact that we modified this
      statement.  */


@@ -3199,7 +3103,7 @@ update_rhs_and_lookup_avail_expr (tree stmt, tree new_rhs, bool insert)
    NULL_TREE.
 
    Also, when an expression is first inserted in the AVAIL_EXPRS table, it
    NULL_TREE.
 
    Also, when an expression is first inserted in the AVAIL_EXPRS table, it

-   is also added to the stack pointed by BLOCK_AVAIL_EXPRS_P, so that they
+   is also added to the stack pointed to by BLOCK_AVAIL_EXPRS_P, so that they

    can be removed when we finish processing this block and its children.
 
    NOTE: This function assumes that STMT is a MODIFY_EXPR node that
    can be removed when we finish processing this block and its children.
 
    NOTE: This function assumes that STMT is a MODIFY_EXPR node that


@@ -3241,11 +3145,8 @@ lookup_avail_expr (tree stmt, bool insert)
        {
          tree t = element->rhs;
          free (element);
        {
          tree t = element->rhs;
          free (element);

-
-         if (TREE_CODE (t) == EQ_EXPR)
-           return boolean_false_node;
-         else
-           return boolean_true_node;
+         return constant_boolean_node (TREE_CODE (t) != EQ_EXPR,
+                                       TREE_TYPE (t));

        }
     }
 
        }
     }
 


@@ -3261,7 +3162,7 @@ lookup_avail_expr (tree stmt, bool insert)
   if (*slot == NULL)
     {
       *slot = (void *) element;
   if (*slot == NULL)
     {
       *slot = (void *) element;

-      VEC_safe_push (tree_on_heap, avail_exprs_stack,
+      VEC_safe_push (tree, heap, avail_exprs_stack,

                     stmt ? stmt : element->rhs);
       return NULL_TREE;
     }
                     stmt ? stmt : element->rhs);
       return NULL_TREE;
     }


@@ -3302,10 +3203,7 @@ extract_range_from_cond (tree cond, tree *hi_p, tree *lo_p, int *inverted_p)
      record ranges for enumerations.  Presumably this is due to
      the fact that they're rarely used directly.  They are typically
      cast into an integer type and used that way.  */
      record ranges for enumerations.  Presumably this is due to
      the fact that they're rarely used directly.  They are typically
      cast into an integer type and used that way.  */

-  if (TREE_CODE (type) != INTEGER_TYPE
-      /* We don't know how to deal with types with variable bounds.  */
-      || TREE_CODE (TYPE_MIN_VALUE (type)) != INTEGER_CST
-      || TREE_CODE (TYPE_MAX_VALUE (type)) != INTEGER_CST)
+  if (TREE_CODE (type) != INTEGER_TYPE)

     return 0;
 
   switch (TREE_CODE (cond))
     return 0;
 
   switch (TREE_CODE (cond))


@@ -3322,12 +3220,19 @@ extract_range_from_cond (tree cond, tree *hi_p, tree *lo_p, int *inverted_p)
 
     case GE_EXPR:
       low = op1;
 
     case GE_EXPR:
       low = op1;

+
+      /* Get the highest value of the type.  If not a constant, use that
+        of its base type, if it has one.  */

       high = TYPE_MAX_VALUE (type);
       high = TYPE_MAX_VALUE (type);

+      if (TREE_CODE (high) != INTEGER_CST && TREE_TYPE (type))
+       high = TYPE_MAX_VALUE (TREE_TYPE (type));

       inverted = 0;
       break;
 
     case GT_EXPR:
       high = TYPE_MAX_VALUE (type);
       inverted = 0;
       break;
 
     case GT_EXPR:
       high = TYPE_MAX_VALUE (type);

+      if (TREE_CODE (high) != INTEGER_CST && TREE_TYPE (type))
+       high = TYPE_MAX_VALUE (TREE_TYPE (type));

       if (!tree_int_cst_lt (op1, high))
        return 0;
       low = int_const_binop (PLUS_EXPR, op1, integer_one_node, 1);
       if (!tree_int_cst_lt (op1, high))
        return 0;
       low = int_const_binop (PLUS_EXPR, op1, integer_one_node, 1);


@@ -3337,11 +3242,15 @@ extract_range_from_cond (tree cond, tree *hi_p, tree *lo_p, int *inverted_p)
     case LE_EXPR:
       high = op1;
       low = TYPE_MIN_VALUE (type);
     case LE_EXPR:
       high = op1;
       low = TYPE_MIN_VALUE (type);

+      if (TREE_CODE (low) != INTEGER_CST && TREE_TYPE (type))
+       low = TYPE_MIN_VALUE (TREE_TYPE (type));

       inverted = 0;
       break;
 
     case LT_EXPR:
       low = TYPE_MIN_VALUE (type);
       inverted = 0;
       break;
 
     case LT_EXPR:
       low = TYPE_MIN_VALUE (type);

+      if (TREE_CODE (low) != INTEGER_CST && TREE_TYPE (type))
+       low = TYPE_MIN_VALUE (TREE_TYPE (type));

       if (!tree_int_cst_lt (low, op1))
        return 0;
       high = int_const_binop (MINUS_EXPR, op1, integer_one_node, 1);
       if (!tree_int_cst_lt (low, op1))
        return 0;
       high = int_const_binop (MINUS_EXPR, op1, integer_one_node, 1);


@@ -3374,7 +3283,7 @@ record_range (tree cond, basic_block bb)
     {
       struct vrp_hash_elt *vrp_hash_elt;
       struct vrp_element *element;
     {
       struct vrp_hash_elt *vrp_hash_elt;
       struct vrp_element *element;

-      varray_type *vrp_records_p;
+      VEC(vrp_element_p,heap) **vrp_records_p;

       void **slot;
 
 
       void **slot;
 
 


@@ -3386,7 +3295,7 @@ record_range (tree cond, basic_block bb)
       if (*slot == NULL)
        *slot = (void *) vrp_hash_elt;
       else
       if (*slot == NULL)
        *slot = (void *) vrp_hash_elt;
       else

-       free (vrp_hash_elt);
+       vrp_free (vrp_hash_elt);

 
       vrp_hash_elt = (struct vrp_hash_elt *) *slot;
       vrp_records_p = &vrp_hash_elt->records;
 
       vrp_hash_elt = (struct vrp_hash_elt *) *slot;
       vrp_records_p = &vrp_hash_elt->records;


@@ -3397,11 +3306,8 @@ record_range (tree cond, basic_block bb)
       element->cond = cond;
       element->bb = bb;
 
       element->cond = cond;
       element->bb = bb;
 

-      if (*vrp_records_p == NULL)
-       VARRAY_GENERIC_PTR_INIT (*vrp_records_p, 2, "vrp records");
-      
-      VARRAY_PUSH_GENERIC_PTR (*vrp_records_p, element);
-      VEC_safe_push (tree_on_heap, vrp_variables_stack, TREE_OPERAND (cond, 0));
+      VEC_safe_push (vrp_element_p, heap, *vrp_records_p, element);
+      VEC_safe_push (tree, heap, vrp_variables_stack, TREE_OPERAND (cond, 0));

     }
 }
 
     }
 }
 


@@ -3435,11 +3341,11 @@ vrp_eq (const void *p1, const void *p2)
 static hashval_t
 avail_expr_hash (const void *p)
 {
 static hashval_t
 avail_expr_hash (const void *p)
 {

-  stmt_ann_t ann = ((struct expr_hash_elt *)p)->ann;
+  tree stmt = ((struct expr_hash_elt *)p)->stmt;

   tree rhs = ((struct expr_hash_elt *)p)->rhs;
   tree rhs = ((struct expr_hash_elt *)p)->rhs;

+  tree vuse;
+  ssa_op_iter iter;

   hashval_t val = 0;
   hashval_t val = 0;

-  size_t i;
-  vuse_optype vuses;

 
   /* iterative_hash_expr knows how to deal with any expression and
      deals with commutative operators as well, so just use it instead
 
   /* iterative_hash_expr knows how to deal with any expression and
      deals with commutative operators as well, so just use it instead


@@ -3449,16 +3355,15 @@ avail_expr_hash (const void *p)
   /* If the hash table entry is not associated with a statement, then we
      can just hash the expression and not worry about virtual operands
      and such.  */
   /* If the hash table entry is not associated with a statement, then we
      can just hash the expression and not worry about virtual operands
      and such.  */

-  if (!ann)
+  if (!stmt || !stmt_ann (stmt))

     return val;
 
   /* Add the SSA version numbers of every vuse operand.  This is important
      because compound variables like arrays are not renamed in the
      operands.  Rather, the rename is done on the virtual variable
      representing all the elements of the array.  */
     return val;
 
   /* Add the SSA version numbers of every vuse operand.  This is important
      because compound variables like arrays are not renamed in the
      operands.  Rather, the rename is done on the virtual variable
      representing all the elements of the array.  */

-  vuses = VUSE_OPS (ann);
-  for (i = 0; i < NUM_VUSES (vuses); i++)
-    val = iterative_hash_expr (VUSE_OP (vuses, i), val);
+  FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
+    val = iterative_hash_expr (vuse, val);

 
   return val;
 }
 
   return val;
 }


@@ -3472,13 +3377,13 @@ real_avail_expr_hash (const void *p)
 static int
 avail_expr_eq (const void *p1, const void *p2)
 {
 static int
 avail_expr_eq (const void *p1, const void *p2)
 {

-  stmt_ann_t ann1 = ((struct expr_hash_elt *)p1)->ann;
+  tree stmt1 = ((struct expr_hash_elt *)p1)->stmt;

   tree rhs1 = ((struct expr_hash_elt *)p1)->rhs;
   tree rhs1 = ((struct expr_hash_elt *)p1)->rhs;

-  stmt_ann_t ann2 = ((struct expr_hash_elt *)p2)->ann;
+  tree stmt2 = ((struct expr_hash_elt *)p2)->stmt;

   tree rhs2 = ((struct expr_hash_elt *)p2)->rhs;
 
   /* If they are the same physical expression, return true.  */
   tree rhs2 = ((struct expr_hash_elt *)p2)->rhs;
 
   /* If they are the same physical expression, return true.  */

-  if (rhs1 == rhs2 && ann1 == ann2)
+  if (rhs1 == rhs2 && stmt1 == stmt2)

     return true;
 
   /* If their codes are not equal, then quit now.  */
     return true;
 
   /* If their codes are not equal, then quit now.  */


@@ -3491,57 +3396,11 @@ avail_expr_eq (const void *p1, const void *p2)
        || lang_hooks.types_compatible_p (TREE_TYPE (rhs1), TREE_TYPE (rhs2)))
       && operand_equal_p (rhs1, rhs2, OEP_PURE_SAME))
     {
        || lang_hooks.types_compatible_p (TREE_TYPE (rhs1), TREE_TYPE (rhs2)))
       && operand_equal_p (rhs1, rhs2, OEP_PURE_SAME))
     {

-      vuse_optype ops1 = NULL;
-      vuse_optype ops2 = NULL;
-      size_t num_ops1 = 0;
-      size_t num_ops2 = 0;
-      size_t i;
-
-      if (ann1)
-       {
-         ops1 = VUSE_OPS (ann1);
-         num_ops1 = NUM_VUSES (ops1);
-       }
-
-      if (ann2)
-       {
-         ops2 = VUSE_OPS (ann2);
-         num_ops2 = NUM_VUSES (ops2);
-       }
-
-      /* If the number of virtual uses is different, then we consider
-        them not equal.  */
-      if (num_ops1 != num_ops2)
-       return false;
-
-      for (i = 0; i < num_ops1; i++)
-       if (VUSE_OP (ops1, i) != VUSE_OP (ops2, i))
-         return false;
-
-      gcc_assert (((struct expr_hash_elt *)p1)->hash
+      bool ret = compare_ssa_operands_equal (stmt1, stmt2, SSA_OP_VUSE);
+      gcc_assert (!ret || ((struct expr_hash_elt *)p1)->hash

                  == ((struct expr_hash_elt *)p2)->hash);
                  == ((struct expr_hash_elt *)p2)->hash);

-      return true;
+      return ret;

     }
 
   return false;
 }
     }
 
   return false;
 }

-
-/* Given STMT and a pointer to the block local definitions BLOCK_DEFS_P,
-   register register all objects set by this statement into BLOCK_DEFS_P
-   and CURRDEFS.  */
-
-static void
-register_definitions_for_stmt (tree stmt)
-{
-  tree def;
-  ssa_op_iter iter;
-
-  FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
-    {
-
-      /* FIXME: We shouldn't be registering new defs if the variable
-        doesn't need to be renamed.  */
-      register_new_def (def, &block_defs_stack);
-    }
-}
-