OSDN Git Service

* g++.dg/crash38.C: moved into proper directory...
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-dom.c
index 278d27a..b37df77 100644 (file)
@@ -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
-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"
@@ -31,7 +31,6 @@ Boston, MA 02111-1307, USA.  */
 #include "basic-block.h"
 #include "cfgloop.h"
 #include "output.h"
-#include "errors.h"
 #include "expr.h"
 #include "function.h"
 #include "diagnostic.h"
@@ -141,6 +140,10 @@ static VEC(tree,heap) *const_and_copies_stack;
    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. 
 
@@ -163,6 +166,7 @@ struct opt_stats_d
   long num_re;
   long num_const_prop;
   long num_copy_prop;
+  long num_iterations;
 };
 
 static struct opt_stats_d opt_stats;
@@ -224,12 +228,17 @@ struct vrp_element
    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;
-  varray_type records;
+  VEC(vrp_element_p,heap) *records;
 };
 
 /* Array of variables which have their values constrained by operations
@@ -264,8 +273,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 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);
@@ -273,8 +281,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 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);
@@ -346,6 +353,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
@@ -363,13 +382,15 @@ tree_ssa_dominator_optimize (void)
 
   /* 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);
+  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);
+  threaded_blocks = BITMAP_ALLOC (NULL);
   need_eh_cleanup = BITMAP_ALLOC (NULL);
 
   /* Setup callbacks for the generic dominator tree walker.  */
@@ -423,15 +444,6 @@ tree_ssa_dominator_optimize (void)
       /* Recursively walk the dominator tree optimizing statements.  */
       walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 
-      /* 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.  */
-      update_ssa (TODO_update_ssa);
-
-      free_all_edge_infos ();
-
       {
        block_stmt_iterator bsi;
        basic_block bb;
@@ -444,8 +456,17 @@ tree_ssa_dominator_optimize (void)
          }
       }
 
+      /* 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.  */
+      update_ssa (TODO_update_ssa);
+
+      free_all_edge_infos ();
+
       /* 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.  */
@@ -458,7 +479,11 @@ tree_ssa_dominator_optimize (void)
       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)
        {
@@ -480,6 +505,7 @@ tree_ssa_dominator_optimize (void)
 
       /* Reinitialize the various tables.  */
       bitmap_clear (nonzero_vars);
+      bitmap_clear (threaded_blocks);
       htab_empty (avail_exprs);
       htab_empty (vrp_data);
 
@@ -503,6 +529,8 @@ tree_ssa_dominator_optimize (void)
          if (value && !is_gimple_min_invariant (value))
            SSA_NAME_VALUE (name) = NULL;
        }
+
+      opt_stats.num_iterations++;
     }
   while (optimize > 1 && cfg_altered);
 
@@ -523,6 +551,7 @@ tree_ssa_dominator_optimize (void)
 
   /* Free nonzero_vars.  */
   BITMAP_FREE (nonzero_vars);
+  BITMAP_FREE (threaded_blocks);
   BITMAP_FREE (need_eh_cleanup);
   
   VEC_free (tree, heap, avail_exprs_stack);
@@ -637,7 +666,7 @@ thread_across_edge (struct dom_walk_data *walk_data, edge e)
      statements.  This does not prevent threading through E->dest.  */
   for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
     {
-      tree cached_lhs;
+      tree cached_lhs = NULL;
 
       stmt = bsi_stmt (bsi);
 
@@ -676,7 +705,7 @@ thread_across_edge (struct dom_walk_data *walk_data, edge e)
       else
        {
          /* Copy the operands.  */
-         tree *copy;
+         tree *copy, pre_fold_expr;
          ssa_op_iter iter;
          use_operand_p use_p;
          unsigned int num, i = 0;
@@ -700,12 +729,31 @@ thread_across_edge (struct dom_walk_data *walk_data, edge e)
 
          /* Try to fold/lookup the new expression.  Inserting the
             expression into the hash table is unlikely to help
-            simplify anything later, so just query the hashtable.  */
-         cached_lhs = fold (TREE_OPERAND (stmt, 1));
-         if (TREE_CODE (cached_lhs) != SSA_NAME
-             && !is_gimple_min_invariant (cached_lhs))
-           cached_lhs = lookup_avail_expr (stmt, false);
+            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 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);
 
+         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.  */
          i = 0;
@@ -823,14 +871,12 @@ thread_across_edge (struct dom_walk_data *walk_data, edge e)
            {
              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;
-             bb_ann (e->dest)->incoming_edge_threaded = true;
+             bitmap_set_bit (threaded_blocks, e->dest->index);
            }
        }
     }
@@ -862,7 +908,7 @@ dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
 }
 
 /* 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)
@@ -974,14 +1020,14 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
 {
   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
-      && (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));
@@ -998,10 +1044,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);
 
-      /* 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;
@@ -1048,8 +1093,7 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
        }
 
       /* 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;
@@ -1109,7 +1153,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.  */
-      varray_type var_vrp_records;
+      VEC(vrp_element_p,heap) **var_vrp_records;
 
       if (var == NULL)
        break;
@@ -1120,17 +1164,17 @@ 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;
-      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 *)VARRAY_TOP_GENERIC_PTR (var_vrp_records);
+           = VEC_last (vrp_element_p, *var_vrp_records);
 
          if (element->bb != bb)
            break;
   
-         VARRAY_POP (var_vrp_records);
+         VEC_pop (vrp_element_p, *var_vrp_records);
        }
     }
 
@@ -1334,6 +1378,9 @@ dump_dominator_optimization_stats (FILE *file)
   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, "    avail_exprs: ");
@@ -1691,8 +1738,7 @@ simple_iv_increment_p (tree stmt)
    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);
@@ -1816,127 +1862,6 @@ simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *walk_data,
  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)
@@ -1982,6 +1907,18 @@ find_equivalent_equality_comparison (tree cond)
     {
       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)
@@ -1995,6 +1932,16 @@ find_equivalent_equality_comparison (tree cond)
              > 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. 
@@ -2034,7 +1981,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;
-         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;
@@ -2087,11 +2034,9 @@ simplify_cond_and_lookup_avail_expr (tree stmt,
            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
@@ -2123,8 +2068,7 @@ simplify_cond_and_lookup_avail_expr (tree stmt,
             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)
            {
@@ -2163,8 +2107,7 @@ simplify_cond_and_lookup_avail_expr (tree stmt,
                {
                  /* 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;
 
@@ -2402,7 +2345,7 @@ record_edge_info (basic_block bb)
            {
              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;
 
@@ -2582,13 +2525,13 @@ propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
    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)
 {
   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);
@@ -2612,7 +2555,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)
-    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.  */
@@ -2630,9 +2573,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))
-    expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
+    {
+      expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
+      modify_expr_p = true;
+    }
   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
@@ -2640,7 +2589,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
-      && (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))
@@ -2663,6 +2615,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;
+      
+      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);
@@ -2701,7 +2658,7 @@ record_equivalences_from_stmt (tree stmt,
              || is_gimple_min_invariant (rhs)))
        SSA_NAME_VALUE (lhs) = rhs;
 
-      if (expr_computes_nonzero (rhs))
+      if (tree_expr_nonzero_p (rhs))
        record_var_is_nonzero (lhs);
     }
 
@@ -2919,7 +2876,7 @@ cprop_into_stmt (tree stmt)
 }
 
 
-/* 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:
@@ -2935,8 +2892,8 @@ cprop_into_stmt (tree stmt)
       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;
   tree stmt, old_stmt;
@@ -3006,7 +2963,7 @@ optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
 
   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)
@@ -3129,7 +3086,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
-   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
@@ -3171,11 +3128,8 @@ lookup_avail_expr (tree stmt, bool insert)
        {
          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));
        }
     }
 
@@ -3304,7 +3258,7 @@ record_range (tree cond, basic_block bb)
     {
       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;
 
 
@@ -3316,7 +3270,7 @@ record_range (tree cond, basic_block bb)
       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;
@@ -3327,10 +3281,7 @@ record_range (tree cond, basic_block 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 (vrp_element_p, heap, *vrp_records_p, element);
       VEC_safe_push (tree, heap, vrp_variables_stack, TREE_OPERAND (cond, 0));
     }
 }