OSDN Git Service

* misc.c (gnat_types_compatible_p, LANG_HOOKS_TYPES_COMPATIBLE_P):
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-dce.c
index fec54ab..502117c 100644 (file)
@@ -54,6 +54,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "rtl.h"
 #include "tm_p.h"
 #include "hard-reg-set.h"
+#include "obstack.h"
 #include "basic-block.h"
 
 #include "tree.h"
@@ -95,7 +96,14 @@ bitmap *control_dependence_map;
 /* Execute CODE for each edge (given number EDGE_NUMBER within the CODE)
    for which the block with index N is control dependent.  */
 #define EXECUTE_IF_CONTROL_DEPENDENT(N, EDGE_NUMBER, CODE)                   \
-  EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[N], 0, EDGE_NUMBER, CODE)
+  {                                                                          \
+    bitmap_iterator bi;                                                              \
+                                                                             \
+    EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[N], 0, EDGE_NUMBER, bi)  \
+      {                                                                              \
+       CODE;                                                                 \
+      }                                                                              \
+  }
 
 /* Local function prototypes.  */
 static inline void set_control_dependence_map_bit (basic_block, int);
@@ -105,7 +113,7 @@ static void find_control_dependence (struct edge_list *, int);
 static inline basic_block find_pdom (basic_block);
 
 static inline void mark_stmt_necessary (tree, bool);
-static inline void mark_operand_necessary (tree);
+static inline void mark_operand_necessary (tree, bool);
 
 static void mark_stmt_if_obviously_necessary (tree, bool);
 static void find_obviously_necessary_stmts (struct edge_list *);
@@ -227,10 +235,11 @@ mark_stmt_necessary (tree stmt, bool add_to_worklist)
     VARRAY_PUSH_TREE (worklist, stmt);
 }
 
-/* Mark the statement defining operand OP as necessary.  */
+/* Mark the statement defining operand OP as necessary.  PHIONLY is true
+   if we should only mark it necessary if it is a phi node.  */
 
 static inline void
-mark_operand_necessary (tree op)
+mark_operand_necessary (tree op, bool phionly)
 {
   tree stmt;
   int ver;
@@ -246,7 +255,8 @@ mark_operand_necessary (tree op)
   gcc_assert (stmt);
 
   if (NECESSARY (stmt)
-      || IS_EMPTY_STMT (stmt))
+      || IS_EMPTY_STMT (stmt)
+      || (phionly && TREE_CODE (stmt) != PHI_NODE))
     return;
 
   NECESSARY (stmt) = 1;
@@ -316,22 +326,12 @@ mark_stmt_if_obviously_necessary (tree stmt, bool aggressive)
       break;
 
     case GOTO_EXPR:
-      if (! simple_goto_p (stmt))
-       mark_stmt_necessary (stmt, true);
+      gcc_assert (!simple_goto_p (stmt));
+      mark_stmt_necessary (stmt, true);
       return;
 
     case COND_EXPR:
-      if (GOTO_DESTINATION (COND_EXPR_THEN (stmt))
-         == GOTO_DESTINATION (COND_EXPR_ELSE (stmt)))
-       {
-         /* A COND_EXPR is obviously dead if the target labels are the same.
-            We cannot kill the statement at this point, so to prevent the
-            statement from being marked necessary, we replace the condition
-            with a constant.  The stmt is killed later on in cfg_cleanup.  */
-         COND_EXPR_COND (stmt) = integer_zero_node;
-         modify_stmt (stmt);
-         return;
-       }
+      gcc_assert (EDGE_COUNT (bb_for_stmt (stmt)->succs) == 2);
       /* Fall through.  */
 
     case SWITCH_EXPR:
@@ -402,7 +402,7 @@ mark_stmt_if_obviously_necessary (tree stmt, bool aggressive)
         a global variable.  Otherwise, we check if the base variable
         is a global.  */
       lhs = TREE_OPERAND (stmt, 0);
-      if (TREE_CODE_CLASS (TREE_CODE (lhs)) == 'r')
+      if (REFERENCE_CLASS_P (lhs))
        lhs = get_base_address (lhs);
 
       if (lhs == NULL_TREE)
@@ -418,7 +418,7 @@ mark_stmt_if_obviously_necessary (tree stmt, bool aggressive)
          if (is_global_var (lhs))
            mark_stmt_necessary (stmt, true);
        }
-      else if (TREE_CODE (lhs) == INDIRECT_REF)
+      else if (INDIRECT_REF_P (lhs))
        {
          tree ptr = TREE_OPERAND (lhs, 0);
          struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
@@ -495,7 +495,8 @@ find_obviously_necessary_stmts (struct edge_list *el)
         and we currently do not have a means to recognize the finite ones.  */
       FOR_EACH_BB (bb)
        {
-         for (e = bb->succ; e; e = e->succ_next)
+         edge_iterator ei;
+         FOR_EACH_EDGE (e, ei, bb->succs)
            if (e->flags & EDGE_DFS_BACK)
              mark_control_dependent_edges_necessary (e->dest, el);
        }
@@ -508,7 +509,7 @@ find_obviously_necessary_stmts (struct edge_list *el)
 static void
 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
 {
-  int edge_number;
+  unsigned edge_number;
 
   gcc_assert (bb != EXIT_BLOCK_PTR);
 
@@ -584,7 +585,7 @@ propagate_necessity (struct edge_list *el)
             {
              tree arg = PHI_ARG_DEF (i, k);
              if (TREE_CODE (arg) == SSA_NAME)
-               mark_operand_necessary (arg);
+               mark_operand_necessary (arg, false);
            }
 
          if (aggressive)
@@ -616,11 +617,79 @@ propagate_necessity (struct edge_list *el)
             links).  */
 
          FOR_EACH_SSA_TREE_OPERAND (use, i, iter, SSA_OP_ALL_USES)
-           mark_operand_necessary (use);
+           mark_operand_necessary (use, false);
+       }
+    }
+}
+
+
+/* Propagate necessity around virtual phi nodes used in kill operands.
+   The reason this isn't done during propagate_necessity is because we don't
+   want to keep phis around that are just there for must-defs, unless we
+   absolutely have to.  After we've rewritten the reaching definitions to be
+   correct in the previous part of the fixup routine, we can simply propagate
+   around the information about which of these virtual phi nodes are really
+   used, and set the NECESSARY flag accordingly.
+   Note that we do the minimum here to ensure that we keep alive the phis that
+   are actually used in the corrected SSA form.  In particular, some of these
+   phis may now have all of the same operand, and will be deleted by some
+   other pass.  */
+
+static void
+mark_really_necessary_kill_operand_phis (void)
+{
+  basic_block bb;
+  int i;
+
+  /* Seed the worklist with the new virtual phi arguments and virtual
+     uses */
+  FOR_EACH_BB (bb)
+    {
+      block_stmt_iterator bsi;
+      tree phi;
+      
+      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+       {
+         if (!is_gimple_reg (PHI_RESULT (phi)) && NECESSARY (phi))
+           {
+             for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+               mark_operand_necessary (PHI_ARG_DEF (phi, i), true);
+           }
+       }
+      
+      for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
+       {
+         tree stmt = bsi_stmt (bsi);
+       
+         if (NECESSARY (stmt))
+           {
+             use_operand_p use_p;
+             ssa_op_iter iter;
+             FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
+                                       SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
+               {
+                 tree use = USE_FROM_PTR (use_p);
+                 mark_operand_necessary (use, true);
+               }
+           }
        }
     }
+  
+  /* Mark all virtual phis still in use as necessary, and all of their
+     arguments that are phis as necessary.  */
+  while (VARRAY_ACTIVE_SIZE (worklist) > 0)
+    {
+      tree use = VARRAY_TOP_TREE (worklist);
+      VARRAY_POP (worklist);
+      
+      for (i = 0; i < PHI_NUM_ARGS (use); i++)
+       mark_operand_necessary (PHI_ARG_DEF (use, i), true);
+    }
 }
+
+
 \f
+
 /* Eliminate unnecessary statements. Any instruction not marked as necessary
    contributes nothing to the program, and can be deleted.  */
 
@@ -632,7 +701,7 @@ eliminate_unnecessary_stmts (void)
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "\nEliminating unnecessary statements:\n");
-
+  
   clear_special_calls ();
   FOR_EACH_BB (bb)
     {
@@ -642,23 +711,23 @@ eliminate_unnecessary_stmts (void)
       /* Remove dead statements.  */
       for (i = bsi_start (bb); ! bsi_end_p (i) ; )
        {
-         tree t = bsi_stmt (i);
-
-         stats.total++;
-
-         /* If `i' is not necessary then remove it.  */
-         if (! NECESSARY (t))
-           remove_dead_stmt (&i, bb);
-         else
-           {
-             tree call = get_call_expr_in (t);
-             if (call)
-               notice_special_calls (call);
-             bsi_next (&i);
-           }
+         tree t = bsi_stmt (i);
+
+         stats.total++;
+
+         /* If `i' is not necessary then remove it.  */
+         if (! NECESSARY (t))
+           remove_dead_stmt (&i, bb);
+         else
+           {
+             tree call = get_call_expr_in (t);
+             if (call)
+               notice_special_calls (call);
+             bsi_next (&i);
+           }
        }
     }
-}
+ }
 \f
 /* Remove dead PHI nodes from block BB.  */
 
@@ -703,6 +772,9 @@ static void
 remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
 {
   tree t = bsi_stmt (*i);
+  def_operand_p def_p;
+
+  ssa_op_iter iter;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -722,7 +794,6 @@ remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
   if (is_ctrl_stmt (t))
     {
       basic_block post_dom_bb;
-      edge e;
       /* The post dominance info has to be up-to-date.  */
       gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK);
       /* Get the immediate post dominator of bb.  */
@@ -737,34 +808,37 @@ remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
        }
 
       /* Redirect the first edge out of BB to reach POST_DOM_BB.  */
-      redirect_edge_and_branch (bb->succ, post_dom_bb);
-      PENDING_STMT (bb->succ) = NULL;
-      bb->succ->probability = REG_BR_PROB_BASE;
-      bb->succ->count = bb->count;
+      redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
+      PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
+      EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
+      EDGE_SUCC (bb, 0)->count = bb->count;
 
       /* The edge is no longer associated with a conditional, so it does
         not have TRUE/FALSE flags.  */
-      bb->succ->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
+      EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 
       /* If the edge reaches any block other than the exit, then it is a
         fallthru edge; if it reaches the exit, then it is not a fallthru
         edge.  */
       if (post_dom_bb != EXIT_BLOCK_PTR)
-       bb->succ->flags |= EDGE_FALLTHRU;
+       EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
       else
-       bb->succ->flags &= ~EDGE_FALLTHRU;
+       EDGE_SUCC (bb, 0)->flags &= ~EDGE_FALLTHRU;
 
       /* Remove the remaining the outgoing edges.  */
-      for (e = bb->succ->succ_next; e != NULL;)
-       {
-         edge tmp = e;
-         e = e->succ_next;
-         remove_edge (tmp);
-       }
+      while (EDGE_COUNT (bb->succs) != 1)
+        remove_edge (EDGE_SUCC (bb, 1));
     }
-
-  bsi_remove (i);
-  release_defs (t);
+  
+  FOR_EACH_SSA_DEF_OPERAND (def_p, t, iter, 
+                           SSA_OP_VIRTUAL_DEFS | SSA_OP_VIRTUAL_KILLS)
+    {
+      tree def = DEF_FROM_PTR (def_p);
+      bitmap_set_bit (vars_to_rename,
+                     var_ann (SSA_NAME_VAR (def))->uid);
+    }
+  bsi_remove (i);  
+  release_defs (t); 
 }
 \f
 /* Print out removed statement statistics.  */
@@ -872,19 +946,15 @@ perform_tree_ssa_dce (bool aggressive)
 
   propagate_necessity (el);
 
+  mark_really_necessary_kill_operand_phis ();
   eliminate_unnecessary_stmts ();
 
   if (aggressive)
     free_dominance_info (CDI_POST_DOMINATORS);
 
-  cleanup_tree_cfg ();
-
   /* Debugging dumps.  */
   if (dump_file)
-    {
-      dump_function_to_file (current_function_decl, dump_file, dump_flags);
-      print_stats ();
-    }
+    print_stats ();
 
   tree_dce_done (aggressive);
 
@@ -923,7 +993,7 @@ struct tree_opt_pass pass_dce =
   0,                                   /* properties_provided */
   0,                                   /* properties_destroyed */
   0,                                   /* todo_flags_start */
-  TODO_ggc_collect | TODO_verify_ssa,  /* todo_flags_finish */
+  TODO_dump_func | TODO_fix_def_def_chains | TODO_cleanup_cfg | TODO_ggc_collect | TODO_verify_ssa,    /* todo_flags_finish */
   0                                    /* letter */
 };
 
@@ -940,7 +1010,7 @@ struct tree_opt_pass pass_cd_dce =
   0,                                   /* properties_provided */
   0,                                   /* properties_destroyed */
   0,                                   /* todo_flags_start */
-  TODO_ggc_collect | TODO_verify_ssa | TODO_verify_flow,
+  TODO_dump_func | TODO_fix_def_def_chains | TODO_cleanup_cfg | TODO_ggc_collect | TODO_verify_ssa | TODO_verify_flow,
                                        /* todo_flags_finish */
   0                                    /* letter */
 };