2007-11-05 H.J. Lu <hongjiu.lu@intel.com>

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

diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c
index a4c764a..17eec74 100644 (file)
--- a/gcc/tree-ssa-propagate.c
+++ b/gcc/tree-ssa-propagate.c
@@ -1,12 +1,12 @@
 /* Generic SSA value propagation engine.
 /* Generic SSA value propagation engine.

-   Copyright (C) 2004, 2005 Free Software Foundation, Inc.
+   Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.

    Contributed by Diego Novillo <dnovillo@redhat.com>
 
    This file is part of GCC.
 
    GCC is free software; you can redistribute it and/or modify it
    under the terms of the GNU General Public License as published by the
    Contributed by Diego Novillo <dnovillo@redhat.com>
 
    This file is part of GCC.
 
    GCC is free software; you can redistribute it and/or modify it
    under the terms of the GNU General Public License as published by the

-   Free Software Foundation; either version 2, or (at your option) any
+   Free Software Foundation; either version 3, or (at your option) any

    later version.
 
    GCC is distributed in the hope that it will be useful, but WITHOUT
    later version.
 
    GCC is distributed in the hope that it will be useful, but WITHOUT


@@ -15,9 +15,8 @@
    for more details.
 
    You should have received a copy of the 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.  */
+   along with GCC; see the file COPYING3.  If not see
+   <http://www.gnu.org/licenses/>.  */

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


@@ -30,7 +29,6 @@
 #include "ggc.h"
 #include "basic-block.h"
 #include "output.h"
 #include "ggc.h"
 #include "basic-block.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"


@@ -131,7 +129,7 @@ static ssa_prop_visit_phi_fn ssa_prop_visit_phi;
 static sbitmap executable_blocks;
 
 /* Array of control flow edges on the worklist.  */
 static sbitmap executable_blocks;
 
 /* Array of control flow edges on the worklist.  */

-static GTY(()) varray_type cfg_blocks = NULL;
+static VEC(basic_block,heap) *cfg_blocks;

 
 static unsigned int cfg_blocks_num = 0;
 static int cfg_blocks_tail;
 
 static unsigned int cfg_blocks_num = 0;
 static int cfg_blocks_tail;


@@ -143,7 +141,7 @@ static sbitmap bb_in_list;
    definition has changed.  SSA edges are def-use edges in the SSA
    web.  For each D-U edge, we store the target statement or PHI node
    U.  */
    definition has changed.  SSA edges are def-use edges in the SSA
    web.  For each D-U edge, we store the target statement or PHI node
    U.  */

-static GTY(()) VEC(tree) *interesting_ssa_edges;
+static GTY(()) VEC(tree,gc) *interesting_ssa_edges;

 
 /* Identical to INTERESTING_SSA_EDGES.  For performance reasons, the
    list of SSA edges is split into two.  One contains all SSA edges
 
 /* Identical to INTERESTING_SSA_EDGES.  For performance reasons, the
    list of SSA edges is split into two.  One contains all SSA edges


@@ -159,7 +157,7 @@ static GTY(()) VEC(tree) *interesting_ssa_edges;
    don't use a separate worklist for VARYING edges, we end up with
    situations where lattice values move from
    UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING.  */
    don't use a separate worklist for VARYING edges, we end up with
    situations where lattice values move from
    UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING.  */

-static GTY(()) VEC(tree) *varying_ssa_edges;
+static GTY(()) VEC(tree,gc) *varying_ssa_edges;

 
 
 /* Return true if the block worklist empty.  */
 
 
 /* Return true if the block worklist empty.  */


@@ -177,6 +175,8 @@ cfg_blocks_empty_p (void)
 static void 
 cfg_blocks_add (basic_block bb)
 {
 static void 
 cfg_blocks_add (basic_block bb)
 {

+  bool head = false;
+

   gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR);
   gcc_assert (!TEST_BIT (bb_in_list, bb->index));
 
   gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR);
   gcc_assert (!TEST_BIT (bb_in_list, bb->index));
 


@@ -188,19 +188,37 @@ cfg_blocks_add (basic_block bb)
   else
     {
       cfg_blocks_num++;
   else
     {
       cfg_blocks_num++;

-      if (cfg_blocks_num > VARRAY_SIZE (cfg_blocks))
+      if (cfg_blocks_num > VEC_length (basic_block, cfg_blocks))

        {
        {

-         /* We have to grow the array now.  Adjust to queue to occupy the
-            full space of the original array.  */
-         cfg_blocks_tail = VARRAY_SIZE (cfg_blocks);
+         /* We have to grow the array now.  Adjust to queue to occupy
+            the full space of the original array.  We do not need to
+            initialize the newly allocated portion of the array
+            because we keep track of CFG_BLOCKS_HEAD and
+            CFG_BLOCKS_HEAD.  */
+         cfg_blocks_tail = VEC_length (basic_block, cfg_blocks);

          cfg_blocks_head = 0;
          cfg_blocks_head = 0;

-         VARRAY_GROW (cfg_blocks, 2 * VARRAY_SIZE (cfg_blocks));
+         VEC_safe_grow (basic_block, heap, cfg_blocks, 2 * cfg_blocks_tail);

        }
        }

+      /* Minor optimization: we prefer to see blocks with more
+        predecessors later, because there is more of a chance that
+        the incoming edges will be executable.  */
+      else if (EDGE_COUNT (bb->preds)
+              >= EDGE_COUNT (VEC_index (basic_block, cfg_blocks,
+                                        cfg_blocks_head)->preds))
+       cfg_blocks_tail = ((cfg_blocks_tail + 1)
+                          % VEC_length (basic_block, cfg_blocks));

       else
       else

-       cfg_blocks_tail = (cfg_blocks_tail + 1) % VARRAY_SIZE (cfg_blocks);
+       {
+         if (cfg_blocks_head == 0)
+           cfg_blocks_head = VEC_length (basic_block, cfg_blocks);
+         --cfg_blocks_head;
+         head = true;
+       }

     }
 
     }
 

-  VARRAY_BB (cfg_blocks, cfg_blocks_tail) = bb;
+  VEC_replace (basic_block, cfg_blocks,
+              head ? cfg_blocks_head : cfg_blocks_tail,
+              bb);

   SET_BIT (bb_in_list, bb->index);
 }
 
   SET_BIT (bb_in_list, bb->index);
 }
 


@@ -212,12 +230,13 @@ cfg_blocks_get (void)
 {
   basic_block bb;
 
 {
   basic_block bb;
 

-  bb = VARRAY_BB (cfg_blocks, cfg_blocks_head);
+  bb = VEC_index (basic_block, cfg_blocks, cfg_blocks_head);

 
   gcc_assert (!cfg_blocks_empty_p ());
   gcc_assert (bb);
 
 
   gcc_assert (!cfg_blocks_empty_p ());
   gcc_assert (bb);
 

-  cfg_blocks_head = (cfg_blocks_head + 1) % VARRAY_SIZE (cfg_blocks);
+  cfg_blocks_head = ((cfg_blocks_head + 1)
+                    % VEC_length (basic_block, cfg_blocks));

   --cfg_blocks_num;
   RESET_BIT (bb_in_list, bb->index);
 
   --cfg_blocks_num;
   RESET_BIT (bb_in_list, bb->index);
 


@@ -244,9 +263,9 @@ add_ssa_edge (tree var, bool is_varying)
        {
          STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1;
          if (is_varying)
        {
          STMT_IN_SSA_EDGE_WORKLIST (use_stmt) = 1;
          if (is_varying)

-           VEC_safe_push (tree, varying_ssa_edges, use_stmt);
+           VEC_safe_push (tree, gc, varying_ssa_edges, use_stmt);

          else
          else

-           VEC_safe_push (tree, interesting_ssa_edges, use_stmt);
+           VEC_safe_push (tree, gc, interesting_ssa_edges, use_stmt);

        }
     }
 }
        }
     }
 }


@@ -342,7 +361,7 @@ simulate_stmt (tree stmt)
    SSA edge is added to it in simulate_stmt.  */
 
 static void
    SSA edge is added to it in simulate_stmt.  */
 
 static void

-process_ssa_edge_worklist (VEC(tree) **worklist)
+process_ssa_edge_worklist (VEC(tree,gc) **worklist)

 {
   /* Drain the entire worklist.  */
   while (VEC_length (tree, *worklist) > 0)
 {
   /* Drain the entire worklist.  */
   while (VEC_length (tree, *worklist) > 0)


@@ -462,8 +481,8 @@ ssa_prop_init (void)
   size_t i;
 
   /* Worklists of SSA edges.  */
   size_t i;
 
   /* Worklists of SSA edges.  */

-  interesting_ssa_edges = VEC_alloc (tree, 20);
-  varying_ssa_edges = VEC_alloc (tree, 20);
+  interesting_ssa_edges = VEC_alloc (tree, gc, 20);
+  varying_ssa_edges = VEC_alloc (tree, gc, 20);

 
   executable_blocks = sbitmap_alloc (last_basic_block);
   sbitmap_zero (executable_blocks);
 
   executable_blocks = sbitmap_alloc (last_basic_block);
   sbitmap_zero (executable_blocks);


@@ -474,7 +493,8 @@ ssa_prop_init (void)
   if (dump_file && (dump_flags & TDF_DETAILS))
     dump_immediate_uses (dump_file);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     dump_immediate_uses (dump_file);
 

-  VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks");
+  cfg_blocks = VEC_alloc (basic_block, heap, 20);
+  VEC_safe_grow (basic_block, heap, cfg_blocks, 20);

 
   /* Initialize the values for every SSA_NAME.  */
   for (i = 1; i < num_ssa_names; i++)
 
   /* Initialize the values for every SSA_NAME.  */
   for (i = 1; i < num_ssa_names; i++)


@@ -506,8 +526,9 @@ ssa_prop_init (void)
 static void
 ssa_prop_fini (void)
 {
 static void
 ssa_prop_fini (void)
 {

-  VEC_free (tree, interesting_ssa_edges);
-  VEC_free (tree, varying_ssa_edges);
+  VEC_free (tree, gc, interesting_ssa_edges);
+  VEC_free (tree, gc, varying_ssa_edges);
+  VEC_free (basic_block, heap, cfg_blocks);

   cfg_blocks = NULL;
   sbitmap_free (bb_in_list);
   sbitmap_free (executable_blocks);
   cfg_blocks = NULL;
   sbitmap_free (bb_in_list);
   sbitmap_free (executable_blocks);


@@ -525,12 +546,12 @@ get_rhs (tree stmt)
     {
     case RETURN_EXPR:
       stmt = TREE_OPERAND (stmt, 0);
     {
     case RETURN_EXPR:
       stmt = TREE_OPERAND (stmt, 0);

-      if (!stmt || TREE_CODE (stmt) != MODIFY_EXPR)
+      if (!stmt || TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)

        return stmt;
       /* FALLTHRU */
 
        return stmt;
       /* FALLTHRU */
 

-    case MODIFY_EXPR:
-      stmt = TREE_OPERAND (stmt, 1);
+    case GIMPLE_MODIFY_STMT:
+      stmt = GENERIC_TREE_OPERAND (stmt, 1);

       if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
        return TREE_OPERAND (stmt, 0);
       else
       if (TREE_CODE (stmt) == WITH_SIZE_EXPR)
        return TREE_OPERAND (stmt, 0);
       else


@@ -551,54 +572,155 @@ get_rhs (tree stmt)
 }
 
 
 }
 
 

-/* Set the main expression of *STMT_P to EXPR.  If EXPR is not a valid
-   GIMPLE expression no changes are done and the function returns
-   false.  */
+/* Return true if EXPR is a valid GIMPLE expression.  */

 
 bool
 
 bool

-set_rhs (tree *stmt_p, tree expr)
+valid_gimple_expression_p (tree expr)

 {
 {

-  tree stmt = *stmt_p, op;

   enum tree_code code = TREE_CODE (expr);
   enum tree_code code = TREE_CODE (expr);

-  stmt_ann_t ann;
-  tree var;
-  ssa_op_iter iter;

 
 

-  /* Verify the constant folded result is valid gimple.  */
-  if (TREE_CODE_CLASS (code) == tcc_binary)
+  switch (TREE_CODE_CLASS (code))

     {
     {

+    case tcc_declaration:
+      if (!is_gimple_variable (expr))
+       return false;
+      break;
+
+    case tcc_constant:
+      break;
+
+    case tcc_binary:
+    case tcc_comparison:

       if (!is_gimple_val (TREE_OPERAND (expr, 0))
          || !is_gimple_val (TREE_OPERAND (expr, 1)))
        return false;
       if (!is_gimple_val (TREE_OPERAND (expr, 0))
          || !is_gimple_val (TREE_OPERAND (expr, 1)))
        return false;

-    }
-  else if (TREE_CODE_CLASS (code) == tcc_unary)
-    {
+      break;
+
+    case tcc_unary:

       if (!is_gimple_val (TREE_OPERAND (expr, 0)))
        return false;
       if (!is_gimple_val (TREE_OPERAND (expr, 0)))
        return false;

+      break;
+
+    case tcc_expression:
+      switch (code)
+       {
+       case ADDR_EXPR:
+         {
+           tree t = TREE_OPERAND (expr, 0);
+           while (handled_component_p (t))
+             {
+               /* ??? More checks needed, see the GIMPLE verifier.  */
+               if ((TREE_CODE (t) == ARRAY_REF
+                    || TREE_CODE (t) == ARRAY_RANGE_REF)
+                   && !is_gimple_val (TREE_OPERAND (t, 1)))
+                 return false;
+               t = TREE_OPERAND (t, 0);
+             }
+           if (!is_gimple_id (t))
+             return false;
+           break;
+         }
+
+       case TRUTH_NOT_EXPR:
+         if (!is_gimple_val (TREE_OPERAND (expr, 0)))
+           return false;
+         break;
+
+       case TRUTH_AND_EXPR:
+       case TRUTH_XOR_EXPR:
+       case TRUTH_OR_EXPR:
+         if (!is_gimple_val (TREE_OPERAND (expr, 0))
+             || !is_gimple_val (TREE_OPERAND (expr, 1)))
+           return false;
+         break;
+
+       case EXC_PTR_EXPR:
+       case FILTER_EXPR:
+         break;
+
+       default:
+         return false;
+       }
+      break;
+
+    case tcc_vl_exp:
+      switch (code)
+       {
+       case CALL_EXPR:
+         break;
+       default:
+         return false;
+       }
+      break;
+
+    case tcc_exceptional:
+      switch (code)
+       {
+       case SSA_NAME:
+         break;
+
+       default:
+         return false;
+       }
+      break;
+
+    default:
+      return false;

     }
     }

-  else if (code == COMPOUND_EXPR)
+
+  return true;
+}
+
+
+/* Set the main expression of *STMT_P to EXPR.  If EXPR is not a valid
+   GIMPLE expression no changes are done and the function returns
+   false.  */
+
+bool
+set_rhs (tree *stmt_p, tree expr)
+{
+  tree stmt = *stmt_p, op;
+  stmt_ann_t ann;
+  tree var;
+  ssa_op_iter iter;
+
+  if (!valid_gimple_expression_p (expr))

     return false;
 
     return false;
 

+  if (EXPR_HAS_LOCATION (stmt)
+      && (EXPR_P (expr)
+         || GIMPLE_STMT_P (expr))
+      && ! EXPR_HAS_LOCATION (expr)
+      && TREE_SIDE_EFFECTS (expr)
+      && TREE_CODE (expr) != LABEL_EXPR)
+    SET_EXPR_LOCATION (expr, EXPR_LOCATION (stmt));
+

   switch (TREE_CODE (stmt))
     {
     case RETURN_EXPR:
       op = TREE_OPERAND (stmt, 0);
   switch (TREE_CODE (stmt))
     {
     case RETURN_EXPR:
       op = TREE_OPERAND (stmt, 0);

-      if (TREE_CODE (op) != MODIFY_EXPR)
+      if (TREE_CODE (op) != GIMPLE_MODIFY_STMT)

        {
        {

-         TREE_OPERAND (stmt, 0) = expr;
+         GIMPLE_STMT_OPERAND (stmt, 0) = expr;

          break;
        }
       stmt = op;
       /* FALLTHRU */
 
          break;
        }
       stmt = op;
       /* FALLTHRU */
 

-    case MODIFY_EXPR:
-      op = TREE_OPERAND (stmt, 1);
+    case GIMPLE_MODIFY_STMT:
+      op = GIMPLE_STMT_OPERAND (stmt, 1);

       if (TREE_CODE (op) == WITH_SIZE_EXPR)
       if (TREE_CODE (op) == WITH_SIZE_EXPR)

-       stmt = op;
-      TREE_OPERAND (stmt, 1) = expr;
+       {
+         stmt = op;
+          TREE_OPERAND (stmt, 1) = expr;
+       }
+      else
+        GIMPLE_STMT_OPERAND (stmt, 1) = expr;

       break;
 
     case COND_EXPR:
       break;
 
     case COND_EXPR:

+      if (!is_gimple_condexpr (expr))
+        return false;

       COND_EXPR_COND (stmt) = expr;
       break;
     case SWITCH_EXPR:
       COND_EXPR_COND (stmt) = expr;
       break;
     case SWITCH_EXPR:


@@ -616,9 +738,10 @@ set_rhs (tree *stmt_p, tree expr)
         effects, then replace *STMT_P with an empty statement.  */
       ann = stmt_ann (stmt);
       *stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt ();
         effects, then replace *STMT_P with an empty statement.  */
       ann = stmt_ann (stmt);
       *stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt ();

-      (*stmt_p)->common.ann = (tree_ann_t) ann;
+      (*stmt_p)->base.ann = (tree_ann_t) ann;

 
 

-      if (TREE_SIDE_EFFECTS (expr))
+      if (gimple_in_ssa_p (cfun)
+         && TREE_SIDE_EFFECTS (expr))

        {
          /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
             replacement.  */
        {
          /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
             replacement.  */


@@ -628,6 +751,7 @@ set_rhs (tree *stmt_p, tree expr)
                SSA_NAME_DEF_STMT (var) = *stmt_p;
            }
        }
                SSA_NAME_DEF_STMT (var) = *stmt_p;
            }
        }

+      stmt->base.ann = NULL;

       break;
     }
 
       break;
     }
 


@@ -673,17 +797,19 @@ ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt,
 }
 
 
 }
 
 

-/* Return the first V_MAY_DEF or V_MUST_DEF operand for STMT.  */
+/* Return the first VDEF operand for STMT.  */

 
 tree
 first_vdef (tree stmt)
 {
 
 tree
 first_vdef (tree stmt)
 {

-  if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0)
-    return V_MAY_DEF_RESULT (STMT_V_MAY_DEF_OPS (stmt), 0);
-  else if (NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
-    return V_MUST_DEF_RESULT (STMT_V_MUST_DEF_OPS (stmt), 0);
-  else
-    gcc_unreachable ();
+  ssa_op_iter iter;
+  tree op;
+
+  /* Simply return the first operand we arrive at.  */
+  FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
+    return (op);
+
+  gcc_unreachable ();

 }
 
 
 }
 
 


@@ -697,19 +823,18 @@ stmt_makes_single_load (tree stmt)
 {
   tree rhs;
 
 {
   tree rhs;
 

-  if (TREE_CODE (stmt) != MODIFY_EXPR)
+  if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)

     return false;
 
     return false;
 

-  if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0
-      && NUM_VUSES (STMT_VUSE_OPS (stmt)) == 0)
+  if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF|SSA_OP_VUSE))

     return false;
 
     return false;
 

-  rhs = TREE_OPERAND (stmt, 1);
+  rhs = GIMPLE_STMT_OPERAND (stmt, 1);

   STRIP_NOPS (rhs);
 
   return (!TREE_THIS_VOLATILE (rhs)
          && (DECL_P (rhs)
   STRIP_NOPS (rhs);
 
   return (!TREE_THIS_VOLATILE (rhs)
          && (DECL_P (rhs)

-             || TREE_CODE_CLASS (TREE_CODE (rhs)) == tcc_reference));
+             || REFERENCE_CLASS_P (rhs)));

 }
 
 
 }
 
 


@@ -723,19 +848,18 @@ stmt_makes_single_store (tree stmt)
 {
   tree lhs;
 
 {
   tree lhs;
 

-  if (TREE_CODE (stmt) != MODIFY_EXPR)
+  if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)

     return false;
 
     return false;
 

-  if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0
-      && NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) == 0)
+  if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))

     return false;
 
     return false;
 

-  lhs = TREE_OPERAND (stmt, 0);
+  lhs = GIMPLE_STMT_OPERAND (stmt, 0);

   STRIP_NOPS (lhs);
 
   return (!TREE_THIS_VOLATILE (lhs)
           && (DECL_P (lhs)
   STRIP_NOPS (lhs);
 
   return (!TREE_THIS_VOLATILE (lhs)
           && (DECL_P (lhs)

-             || TREE_CODE_CLASS (TREE_CODE (lhs)) == tcc_reference));
+             || REFERENCE_CLASS_P (lhs)));

 }
 
 
 }
 
 


@@ -768,6 +892,7 @@ struct prop_stats_d
 {
   long num_const_prop;
   long num_copy_prop;
 {
   long num_const_prop;
   long num_copy_prop;

+  long num_pred_folded;

 };
 
 static struct prop_stats_d prop_stats;
 };
 
 static struct prop_stats_d prop_stats;


@@ -829,7 +954,7 @@ replace_uses_in (tree stmt, bool *replaced_addresses_p,
       GIMPLE register, then we are making a copy/constant propagation
       from a memory store.  For instance,
 
       GIMPLE register, then we are making a copy/constant propagation
       from a memory store.  For instance,
 

-       # a_3 = V_MAY_DEF <a_2>
+       # a_3 = VDEF <a_2>

        a.b = x_1;
        ...
        # VUSE <a_3>
        a.b = x_1;
        ...
        # VUSE <a_3>


@@ -840,8 +965,8 @@ replace_uses_in (tree stmt, bool *replaced_addresses_p,
       the VUSE(s) that we are replacing.  Otherwise, we may do the
       wrong replacement:
 
       the VUSE(s) that we are replacing.  Otherwise, we may do the
       wrong replacement:
 

-       # a_3 = V_MAY_DEF <a_2>
-       # b_5 = V_MAY_DEF <b_4>
+       # a_3 = VDEF <a_2>
+       # b_5 = VDEF <b_4>

        *p = 10;
        ...
        # VUSE <b_5>
        *p = 10;
        ...
        # VUSE <b_5>


@@ -861,10 +986,10 @@ replace_uses_in (tree stmt, bool *replaced_addresses_p,
       stored in different locations:
 
                if (...)
       stored in different locations:
 
                if (...)

-                 # a_3 = V_MAY_DEF <a_2>
+                 # a_3 = VDEF <a_2>

                  a.b = 3;
                else
                  a.b = 3;
                else

-                 # a_4 = V_MAY_DEF <a_2>
+                 # a_4 = VDEF <a_2>

                  a.c = 3;
                # a_5 = PHI <a_3, a_4>
 
                  a.c = 3;
                # a_5 = PHI <a_3, a_4>
 


@@ -891,7 +1016,7 @@ replace_vuses_in (tree stmt, bool *replaced_addresses_p,
         see if we are trying to propagate a constant or a GIMPLE
         register (case #1 above).  */
       prop_value_t *val = get_value_loaded_by (stmt, prop_value);
         see if we are trying to propagate a constant or a GIMPLE
         register (case #1 above).  */
       prop_value_t *val = get_value_loaded_by (stmt, prop_value);

-      tree rhs = TREE_OPERAND (stmt, 1);
+      tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);

 
       if (val
          && val->value
 
       if (val
          && val->value


@@ -903,7 +1028,7 @@ replace_vuses_in (tree stmt, bool *replaced_addresses_p,
          /* If we are replacing a constant address, inform our
             caller.  */
          if (TREE_CODE (val->value) != SSA_NAME
          /* If we are replacing a constant address, inform our
             caller.  */
          if (TREE_CODE (val->value) != SSA_NAME

-             && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1)))
+             && POINTER_TYPE_P (TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 1)))

              && replaced_addresses_p)
            *replaced_addresses_p = true;
 
              && replaced_addresses_p)
            *replaced_addresses_p = true;
 


@@ -913,7 +1038,7 @@ replace_vuses_in (tree stmt, bool *replaced_addresses_p,
             stores between DEF_STMT and STMT, we only need to check
             that the RHS of STMT is the same as the memory reference
             propagated together with the value.  */
             stores between DEF_STMT and STMT, we only need to check
             that the RHS of STMT is the same as the memory reference
             propagated together with the value.  */

-         TREE_OPERAND (stmt, 1) = val->value;
+         GIMPLE_STMT_OPERAND (stmt, 1) = val->value;

 
          if (TREE_CODE (val->value) != SSA_NAME)
            prop_stats.num_const_prop++;
 
          if (TREE_CODE (val->value) != SSA_NAME)
            prop_stats.num_const_prop++;


@@ -959,6 +1084,11 @@ static void
 replace_phi_args_in (tree phi, prop_value_t *prop_value)
 {
   int i;
 replace_phi_args_in (tree phi, prop_value_t *prop_value)
 {
   int i;

+  bool replaced = false;
+  tree prev_phi = NULL;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    prev_phi = unshare_expr (phi);

 
   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
     {
 
   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
     {


@@ -976,6 +1106,7 @@ replace_phi_args_in (tree phi, prop_value_t *prop_value)
                prop_stats.num_copy_prop++;
 
              propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
                prop_stats.num_copy_prop++;
 
              propagate_value (PHI_ARG_DEF_PTR (phi, i), val);

+             replaced = true;

 
              /* If we propagated a copy and this argument flows
                 through an abnormal edge, update the replacement
 
              /* If we propagated a copy and this argument flows
                 through an abnormal edge, update the replacement


@@ -986,19 +1117,89 @@ replace_phi_args_in (tree phi, prop_value_t *prop_value)
            }
        }
     }
            }
        }
     }

+  
+  if (replaced && dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Folded PHI node: ");
+      print_generic_stmt (dump_file, prev_phi, TDF_SLIM);
+      fprintf (dump_file, "           into: ");
+      print_generic_stmt (dump_file, phi, TDF_SLIM);
+      fprintf (dump_file, "\n");
+    }

 }
 
 
 }
 
 

-/* Perform final substitution and folding of propagated values.  */
+/* If STMT has a predicate whose value can be computed using the value
+   range information computed by VRP, compute its value and return true.
+   Otherwise, return false.  */

 
 

-void
-substitute_and_fold (prop_value_t *prop_value)
+static bool
+fold_predicate_in (tree stmt)
+{
+  tree *pred_p = NULL;
+  bool modify_stmt_p = false;
+  tree val;
+
+  if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
+      && COMPARISON_CLASS_P (GIMPLE_STMT_OPERAND (stmt, 1)))
+    {
+      modify_stmt_p = true;
+      pred_p = &GIMPLE_STMT_OPERAND (stmt, 1);
+    }
+  else if (TREE_CODE (stmt) == COND_EXPR)
+    pred_p = &COND_EXPR_COND (stmt);
+  else
+    return false;
+
+  val = vrp_evaluate_conditional (*pred_p, stmt);
+  if (val)
+    {
+      if (modify_stmt_p)
+        val = fold_convert (TREE_TYPE (*pred_p), val);
+      
+      if (dump_file)
+       {
+         fprintf (dump_file, "Folding predicate ");
+         print_generic_expr (dump_file, *pred_p, 0);
+         fprintf (dump_file, " to ");
+         print_generic_expr (dump_file, val, 0);
+         fprintf (dump_file, "\n");
+       }
+
+      prop_stats.num_pred_folded++;
+      *pred_p = val;
+      return true;
+    }
+
+  return false;
+}
+
+
+/* Perform final substitution and folding of propagated values.
+
+   PROP_VALUE[I] contains the single value that should be substituted
+   at every use of SSA name N_I.  If PROP_VALUE is NULL, no values are
+   substituted.
+
+   If USE_RANGES_P is true, statements that contain predicate
+   expressions are evaluated with a call to vrp_evaluate_conditional.
+   This will only give meaningful results when called from tree-vrp.c
+   (the information used by vrp_evaluate_conditional is built by the
+   VRP pass).  
+
+   Return TRUE when something changed.  */
+
+bool
+substitute_and_fold (prop_value_t *prop_value, bool use_ranges_p)

 {
   basic_block bb;
 {
   basic_block bb;

+  bool something_changed = false;
+
+  if (prop_value == NULL && !use_ranges_p)
+    return false;

 
   if (dump_file && (dump_flags & TDF_DETAILS))
 
   if (dump_file && (dump_flags & TDF_DETAILS))

-    fprintf (dump_file,
-            "\nSubstituing values and folding statements\n\n");
+    fprintf (dump_file, "\nSubstituing values and folding statements\n\n");

 
   memset (&prop_stats, 0, sizeof (prop_stats));
 
 
   memset (&prop_stats, 0, sizeof (prop_stats));
 


@@ -1008,64 +1209,98 @@ substitute_and_fold (prop_value_t *prop_value)
       block_stmt_iterator i;
       tree phi;
 
       block_stmt_iterator i;
       tree phi;
 

-      /* Propagate our known values into PHI nodes.  */
-      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
-       {
-         if (dump_file && (dump_flags & TDF_DETAILS))
-           {
-             fprintf (dump_file, "Replaced ");
-             print_generic_stmt (dump_file, phi, TDF_SLIM);
-           }
-
+      /* Propagate known values into PHI nodes.  */
+      if (prop_value)
+       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))

          replace_phi_args_in (phi, prop_value);
 
          replace_phi_args_in (phi, prop_value);
 

-         if (dump_file && (dump_flags & TDF_DETAILS))
-           {
-             fprintf (dump_file, " with ");
-             print_generic_stmt (dump_file, phi, TDF_SLIM);
-             fprintf (dump_file, "\n");
-           }
-       }
-

       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
        {
           bool replaced_address, did_replace;
       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
        {
           bool replaced_address, did_replace;

+         tree prev_stmt = NULL;

          tree stmt = bsi_stmt (i);
 
          tree stmt = bsi_stmt (i);
 

-         get_stmt_operands (stmt);
+         /* Ignore ASSERT_EXPRs.  They are used by VRP to generate
+            range information for names and they are discarded
+            afterwards.  */
+         if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
+             && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ASSERT_EXPR)
+           continue;
+
+         /* Record the state of the statement before replacements.  */
+         push_stmt_changes (bsi_stmt_ptr (i));

 
          /* Replace the statement with its folded version and mark it
             folded.  */
 
          /* Replace the statement with its folded version and mark it
             folded.  */

+         did_replace = false;
+         replaced_address = false;

          if (dump_file && (dump_flags & TDF_DETAILS))
          if (dump_file && (dump_flags & TDF_DETAILS))

+           prev_stmt = unshare_expr (stmt);
+
+         /* If we have range information, see if we can fold
+            predicate expressions.  */
+         if (use_ranges_p)
+           did_replace = fold_predicate_in (stmt);
+
+         if (prop_value)

            {
            {

-             fprintf (dump_file, "Replaced ");
-             print_generic_stmt (dump_file, stmt, TDF_SLIM);
+             /* Only replace real uses if we couldn't fold the
+                statement using value range information (value range
+                information is not collected on virtuals, so we only
+                need to check this for real uses).  */
+             if (!did_replace)
+               did_replace |= replace_uses_in (stmt, &replaced_address,
+                                               prop_value);
+
+             did_replace |= replace_vuses_in (stmt, &replaced_address,
+                                              prop_value);

            }
 
            }
 

-         replaced_address = false;
-         did_replace = replace_uses_in (stmt, &replaced_address, prop_value);
-         did_replace |= replace_vuses_in (stmt, &replaced_address, prop_value);
+         /* If we made a replacement, fold and cleanup the statement.  */

          if (did_replace)
            {
          if (did_replace)
            {

-             fold_stmt (bsi_stmt_ptr (i));
-             stmt = bsi_stmt(i);
+             tree old_stmt = stmt;
+             tree rhs;

 
 

-             /* If we folded a builtin function, we'll likely
-                need to rename VDEFs.  */
-             mark_new_vars_to_rename (stmt);
+             fold_stmt (bsi_stmt_ptr (i));
+             stmt = bsi_stmt (i);

 
               /* If we cleaned up EH information from the statement,
                  remove EH edges.  */
 
               /* If we cleaned up EH information from the statement,
                  remove EH edges.  */

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

                tree_purge_dead_eh_edges (bb);
                tree_purge_dead_eh_edges (bb);

-           }

 
 

-         if (dump_file && (dump_flags & TDF_DETAILS))
+             rhs = get_rhs (stmt);
+             if (TREE_CODE (rhs) == ADDR_EXPR)
+               recompute_tree_invariant_for_addr_expr (rhs);
+
+             if (dump_file && (dump_flags & TDF_DETAILS))
+               {
+                 fprintf (dump_file, "Folded statement: ");
+                 print_generic_stmt (dump_file, prev_stmt, TDF_SLIM);
+                 fprintf (dump_file, "            into: ");
+                 print_generic_stmt (dump_file, stmt, TDF_SLIM);
+                 fprintf (dump_file, "\n");
+               }
+
+             /* Determine what needs to be done to update the SSA form.  */
+             pop_stmt_changes (bsi_stmt_ptr (i));
+             something_changed = true;
+           }
+         else

            {
            {

-             fprintf (dump_file, " with ");
-             print_generic_stmt (dump_file, stmt, TDF_SLIM);
-             fprintf (dump_file, "\n");
+             /* The statement was not modified, discard the change buffer.  */
+             discard_stmt_changes (bsi_stmt_ptr (i));

            }
            }

+
+         /* Some statements may be simplified using ranges.  For
+            example, division may be replaced by shifts, modulo
+            replaced with bitwise and, etc.   Do this after 
+            substituting constants, folding, etc so that we're
+            presented with a fully propagated, canonicalized
+            statement.  */
+         if (use_ranges_p)
+           simplify_stmt_using_ranges (stmt);

        }
     }
 
        }
     }
 


@@ -1075,6 +1310,10 @@ substitute_and_fold (prop_value_t *prop_value)
               prop_stats.num_const_prop);
       fprintf (dump_file, "Copies propagated:    %6ld\n",
               prop_stats.num_copy_prop);
               prop_stats.num_const_prop);
       fprintf (dump_file, "Copies propagated:    %6ld\n",
               prop_stats.num_copy_prop);

+      fprintf (dump_file, "Predicates folded:    %6ld\n",
+              prop_stats.num_pred_folded);

     }
     }

+  return something_changed;

 }
 }

+

 #include "gt-tree-ssa-propagate.h"
 #include "gt-tree-ssa-propagate.h"