OSDN Git Service

* params.def (PARAM_INLINE_UNIT_GROWTH): Set to 30.
[pf3gnuchains/gcc-fork.git] / gcc / tree-cfg.c
index d956d2b..e3e2134 100644 (file)
@@ -1,5 +1,5 @@
 /* Control flow functions for trees.
-   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
+   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
    Free Software Foundation, Inc.
    Contributed by Diego Novillo <dnovillo@redhat.com>
 
@@ -44,9 +44,9 @@ Boston, MA 02110-1301, USA.  */
 #include "except.h"
 #include "cfgloop.h"
 #include "cfglayout.h"
-#include "hashtab.h"
 #include "tree-ssa-propagate.h"
 #include "value-prof.h"
+#include "pointer-set.h"
 
 /* This file contains functions for building the Control Flow Graph (CFG)
    for a function tree.  */
@@ -69,19 +69,7 @@ static const int initial_cfg_capacity = 20;
    more persistent.  The key is getting notification of changes to
    the CFG (particularly edge removal, creation and redirection).  */
 
-struct edge_to_cases_elt
-{
-  /* The edge itself.  Necessary for hashing and equality tests.  */
-  edge e;
-
-  /* The case labels associated with this edge.  We link these up via
-     their TREE_CHAIN field, then we wipe out the TREE_CHAIN fields
-     when we destroy the hash table.  This prevents problems when copying
-     SWITCH_EXPRs.  */
-  tree case_labels;
-};
-
-static htab_t edge_to_cases;
+static struct pointer_map_t *edge_to_cases;
 
 /* CFG statistics.  */
 struct cfg_stats_d
@@ -236,7 +224,7 @@ struct tree_opt_pass pass_build_cfg =
   PROP_cfg,                            /* properties_provided */
   0,                                   /* properties_destroyed */
   0,                                   /* todo_flags_start */
-  TODO_verify_stmts,                   /* todo_flags_finish */
+  TODO_verify_stmts | TODO_cleanup_cfg,        /* todo_flags_finish */
   0                                    /* letter */
 };
 
@@ -578,9 +566,6 @@ make_edges (void)
 
   /* Fold COND_EXPR_COND of each COND_EXPR.  */
   fold_cond_expr_cond ();
-
-  /* Clean up the graph and warn for unreachable code.  */
-  cleanup_tree_cfg ();
 }
 
 
@@ -621,28 +606,6 @@ make_cond_expr_edges (basic_block bb)
     }
 }
 
-/* Hashing routine for EDGE_TO_CASES.  */
-
-static hashval_t
-edge_to_cases_hash (const void *p)
-{
-  edge e = ((struct edge_to_cases_elt *)p)->e;
-
-  /* Hash on the edge itself (which is a pointer).  */
-  return htab_hash_pointer (e);
-}
-
-/* Equality routine for EDGE_TO_CASES, edges are unique, so testing
-   for equality is just a pointer comparison.  */
-
-static int
-edge_to_cases_eq (const void *p1, const void *p2)
-{
-  edge e1 = ((struct edge_to_cases_elt *)p1)->e;
-  edge e2 = ((struct edge_to_cases_elt *)p2)->e;
-
-  return e1 == e2;
-}
 
 /* Called for each element in the hash table (P) as we delete the
    edge to cases hash table.
@@ -651,18 +614,20 @@ edge_to_cases_eq (const void *p1, const void *p2)
    SWITCH_EXPRs and structure sharing rules, then free the hash table
    element.  */
 
-static void
-edge_to_cases_cleanup (void *p)
+static bool
+edge_to_cases_cleanup (void *key ATTRIBUTE_UNUSED, void **value,
+                      void *data ATTRIBUTE_UNUSED)
 {
-  struct edge_to_cases_elt *elt = (struct edge_to_cases_elt *) p;
   tree t, next;
 
-  for (t = elt->case_labels; t; t = next)
+  for (t = (tree) *value; t; t = next)
     {
       next = TREE_CHAIN (t);
       TREE_CHAIN (t) = NULL;
     }
-  free (p);
+
+  *value = NULL;
+  return false;
 }
 
 /* Start recording information mapping edges to case labels.  */
@@ -671,11 +636,7 @@ void
 start_recording_case_labels (void)
 {
   gcc_assert (edge_to_cases == NULL);
-
-  edge_to_cases = htab_create (37,
-                              edge_to_cases_hash,
-                              edge_to_cases_eq,
-                              edge_to_cases_cleanup);
+  edge_to_cases = pointer_map_create ();
 }
 
 /* Return nonzero if we are recording information for case labels.  */
@@ -691,46 +652,11 @@ recording_case_labels_p (void)
 void
 end_recording_case_labels (void)
 {
-  htab_delete (edge_to_cases);
+  pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
+  pointer_map_destroy (edge_to_cases);
   edge_to_cases = NULL;
 }
 
-/* Record that CASE_LABEL (a CASE_LABEL_EXPR) references edge E.  */
-
-static void
-record_switch_edge (edge e, tree case_label)
-{
-  struct edge_to_cases_elt *elt;
-  void **slot;
-
-  /* Build a hash table element so we can see if E is already
-     in the table.  */
-  elt = XNEW (struct edge_to_cases_elt);
-  elt->e = e;
-  elt->case_labels = case_label;
-
-  slot = htab_find_slot (edge_to_cases, elt, INSERT);
-
-  if (*slot == NULL)
-    {
-      /* E was not in the hash table.  Install E into the hash table.  */
-      *slot = (void *)elt;
-    }
-  else
-    {
-      /* E was already in the hash table.  Free ELT as we do not need it
-        anymore.  */
-      free (elt);
-
-      /* Get the entry stored in the hash table.  */
-      elt = (struct edge_to_cases_elt *) *slot;
-
-      /* Add it to the chain of CASE_LABEL_EXPRs referencing E.  */
-      TREE_CHAIN (case_label) = elt->case_labels;
-      elt->case_labels = case_label;
-    }
-}
-
 /* If we are inside a {start,end}_recording_cases block, then return
    a chain of CASE_LABEL_EXPRs from T which reference E.
 
@@ -739,7 +665,6 @@ record_switch_edge (edge e, tree case_label)
 static tree
 get_cases_for_edge (edge e, tree t)
 {
-  struct edge_to_cases_elt elt, *elt_p;
   void **slot;
   size_t i, n;
   tree vec;
@@ -749,16 +674,9 @@ get_cases_for_edge (edge e, tree t)
   if (!recording_case_labels_p ())
     return NULL;
 
-restart:
-  elt.e = e;
-  elt.case_labels = NULL;
-  slot = htab_find_slot (edge_to_cases, &elt, NO_INSERT);
-
+  slot = pointer_map_contains (edge_to_cases, e);
   if (slot)
-    {
-      elt_p = (struct edge_to_cases_elt *)*slot;
-      return elt_p->case_labels;
-    }
+    return (tree) *slot;
 
   /* If we did not find E in the hash table, then this must be the first
      time we have been queried for information about E & T.  Add all the
@@ -768,11 +686,19 @@ restart:
   n = TREE_VEC_LENGTH (vec);
   for (i = 0; i < n; i++)
     {
-      tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
+      tree elt = TREE_VEC_ELT (vec, i);
+      tree lab = CASE_LABEL (elt);
       basic_block label_bb = label_to_block (lab);
-      record_switch_edge (find_edge (e->src, label_bb), TREE_VEC_ELT (vec, i));
+      edge this_edge = find_edge (e->src, label_bb);
+
+      /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
+        a new chain.  */
+      slot = pointer_map_insert (edge_to_cases, this_edge);
+      TREE_CHAIN (elt) = (tree) *slot;
+      *slot = elt;
     }
-  goto restart;
+
+  return (tree) *pointer_map_contains (edge_to_cases, e);
 }
 
 /* Create the edges for a SWITCH_EXPR starting at block BB.
@@ -1329,11 +1255,13 @@ tree_merge_blocks (basic_block a, basic_block b)
          copy = build2_gimple (GIMPLE_MODIFY_STMT, def, use);
          bsi_insert_after (&bsi, copy, BSI_NEW_STMT);
          SSA_NAME_DEF_STMT (def) = copy;
+          remove_phi_node (phi, NULL, false);
        }
       else
-       replace_uses_by (def, use);
-
-      remove_phi_node (phi, NULL, false);
+        {
+          replace_uses_by (def, use);
+          remove_phi_node (phi, NULL, true);
+        }
     }
 
   /* Ensure that B follows A.  */
@@ -2649,6 +2577,17 @@ disband_implicit_edges (void)
 void
 delete_tree_cfg_annotations (void)
 {
+  basic_block bb;
+  block_stmt_iterator bsi;
+
+  /* Remove annotations from every tree in the function.  */
+  FOR_EACH_BB (bb)
+    for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+      {
+       tree stmt = bsi_stmt (bsi);
+       ggc_free (stmt->base.ann);
+       stmt->base.ann = NULL;
+      }
   label_to_block_map = NULL;
 }
 
@@ -2901,6 +2840,8 @@ bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool update_eh_info)
   int eh_region;
   tree orig_stmt = bsi_stmt (*bsi);
 
+  if (stmt == orig_stmt)
+    return;
   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
   set_bb_for_stmt (stmt, bsi->bb);
 
@@ -2913,11 +2854,11 @@ bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool update_eh_info)
        {
          remove_stmt_from_eh_region (orig_stmt);
          add_stmt_to_eh_region (stmt, eh_region);
-         gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
-          gimple_remove_stmt_histograms (cfun, orig_stmt);
        }
     }
 
+  gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
+  gimple_remove_stmt_histograms (cfun, orig_stmt);
   delink_stmt_imm_use (orig_stmt);
   *bsi_stmt_ptr (*bsi) = stmt;
   mark_stmt_modified (stmt);
@@ -3512,8 +3453,7 @@ tree_node_can_be_shared (tree t)
 static tree
 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
 {
-  htab_t htab = (htab_t) data;
-  void **slot;
+  struct pointer_set_t *visited = (struct pointer_set_t *) data;
 
   if (tree_node_can_be_shared (*tp))
     {
@@ -3521,10 +3461,8 @@ verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
       return NULL;
     }
 
-  slot = htab_find_slot (htab, *tp, INSERT);
-  if (*slot)
-    return (tree) *slot;
-  *slot = *tp;
+  if (pointer_set_insert (visited, *tp))
+    return *tp;
 
   return NULL;
 }
@@ -3559,6 +3497,22 @@ verify_gimple_tuples (tree t)
   return walk_tree (&t, verify_gimple_tuples_1, NULL, NULL) != NULL;
 }
 
+static bool eh_error_found;
+static int
+verify_eh_throw_stmt_node (void **slot, void *data)
+{
+  struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
+  struct pointer_set_t *visited = (struct pointer_set_t *) data;
+
+  if (!pointer_set_contains (visited, node->stmt))
+    {
+      error ("Dead STMT in EH table");
+      debug_generic_stmt (node->stmt);
+      eh_error_found = true;
+    }
+  return 0;
+}
+
 /* Verify the GIMPLE statement chain.  */
 
 void
@@ -3567,11 +3521,12 @@ verify_stmts (void)
   basic_block bb;
   block_stmt_iterator bsi;
   bool err = false;
-  htab_t htab;
+  struct pointer_set_t *visited, *visited_stmts;
   tree addr;
 
   timevar_push (TV_TREE_STMT_VERIFY);
-  htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+  visited = pointer_set_create ();
+  visited_stmts = pointer_set_create ();
 
   FOR_EACH_BB (bb)
     {
@@ -3582,6 +3537,7 @@ verify_stmts (void)
        {
          int phi_num_args = PHI_NUM_ARGS (phi);
 
+         pointer_set_insert (visited_stmts, phi);
          if (bb_for_stmt (phi) != bb)
            {
              error ("bb_for_stmt (phi) is set to a wrong basic block");
@@ -3612,7 +3568,7 @@ verify_stmts (void)
                  err |= true;
                }
 
-             addr = walk_tree (&t, verify_node_sharing, htab, NULL);
+             addr = walk_tree (&t, verify_node_sharing, visited, NULL);
              if (addr)
                {
                  error ("incorrect sharing of tree nodes");
@@ -3627,6 +3583,7 @@ verify_stmts (void)
        {
          tree stmt = bsi_stmt (bsi);
 
+         pointer_set_insert (visited_stmts, stmt);
          err |= verify_gimple_tuples (stmt);
 
          if (bb_for_stmt (stmt) != bb)
@@ -3637,7 +3594,7 @@ verify_stmts (void)
 
          bsi_next (&bsi);
          err |= verify_stmt (stmt, bsi_end_p (bsi));
-         addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
+         addr = walk_tree (&stmt, verify_node_sharing, visited, NULL);
          if (addr)
            {
              error ("incorrect sharing of tree nodes");
@@ -3647,11 +3604,17 @@ verify_stmts (void)
            }
        }
     }
+  eh_error_found = false;
+  if (get_eh_throw_stmt_table (cfun))
+    htab_traverse (get_eh_throw_stmt_table (cfun),
+                  verify_eh_throw_stmt_node,
+                  visited_stmts);
 
-  if (err)
+  if (err | eh_error_found)
     internal_error ("verify_stmts failed");
 
-  htab_delete (htab);
+  pointer_set_destroy (visited);
+  pointer_set_destroy (visited_stmts);
   verify_histograms ();
   timevar_pop (TV_TREE_STMT_VERIFY);
 }
@@ -4186,6 +4149,17 @@ tree_redirect_edge_and_branch (edge e, basic_block dest)
   return e;
 }
 
+/* Returns true if it is possible to remove edge E by redirecting
+   it to the destination of the other edge from E->src.  */
+
+static bool
+tree_can_remove_branch_p (edge e)
+{
+  if (e->flags & EDGE_ABNORMAL)
+    return false;
+
+  return true;
+}
 
 /* Simple wrapper, as we can always redirect fallthru edges.  */
 
@@ -5581,6 +5555,7 @@ struct cfg_hooks tree_cfg_hooks = {
   create_bb,                   /* create_basic_block  */
   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
+  tree_can_remove_branch_p,    /* can_remove_branch_p  */
   remove_bb,                   /* delete_basic_block  */
   tree_split_block,            /* split_block  */
   tree_move_block_after,       /* move_block_after  */