OSDN Git Service

2008-08-20 Richard Guenther <rguenther@suse.de>
authorrguenth <rguenth@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 20 Aug 2008 08:28:17 +0000 (08:28 +0000)
committerrguenth <rguenth@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 20 Aug 2008 08:28:17 +0000 (08:28 +0000)
* tree-vrp.c (found_in_subgraph): Remove.
(live): New global static.
(live_on_edge): New function.
(blocks_visited): Remove.
(register_edge_assert_for_2): Use live_on_edge.
(find_conditional_asserts): Remove code dealing with
found_in_subgraph.  Do not walk the CFG.
(find_switch_asserts): Likewise.
(find_assert_locations_1): Renamed from find_assert_locations.
Move finding assert locations for conditional and switch
statements first.  Update live bitmap.  Do not walk the CFG.
(find_assert_locations): New function.
(insert_range_assertions): Remove entry of CFG walk.
Adjust call to find_assert_locations.
* tree-ssa-pre.c (do_regular_insertion): Ignore critical edges
that only can appear because of fake exit edges but assert we
never try to insert on those.
(fini_pre): Do not remove fake exit edges here...
(execute_pre): ...but here, before committing edge inserts.

* gcc.dg/tree-ssa/pr20701.c: Scan vrp1 dump.
* gcc.dg/tree-ssa/ssa-dom-thread-1.c: Pass -fno-tree-vrp.
* gcc.dg/tree-ssa/ssa-pre-20.c: New testcase.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@139263 138bc75d-0d04-0410-961f-82ee72b054a4

gcc/ChangeLog
gcc/testsuite/ChangeLog
gcc/testsuite/gcc.dg/tree-ssa/pr20701.c
gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-1.c
gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-20.c [new file with mode: 0644]
gcc/tree-ssa-pre.c
gcc/tree-vrp.c

index 529c246..6f207e5 100644 (file)
@@ -1,3 +1,25 @@
+2008-08-20  Richard Guenther  <rguenther@suse.de>
+
+       * tree-vrp.c (found_in_subgraph): Remove.
+       (live): New global static.
+       (live_on_edge): New function.
+       (blocks_visited): Remove.
+       (register_edge_assert_for_2): Use live_on_edge.
+       (find_conditional_asserts): Remove code dealing with
+       found_in_subgraph.  Do not walk the CFG.
+       (find_switch_asserts): Likewise.
+       (find_assert_locations_1): Renamed from find_assert_locations.
+       Move finding assert locations for conditional and switch
+       statements first.  Update live bitmap.  Do not walk the CFG.
+       (find_assert_locations): New function.
+       (insert_range_assertions): Remove entry of CFG walk.
+       Adjust call to find_assert_locations.
+       * tree-ssa-pre.c (do_regular_insertion): Ignore critical edges
+       that only can appear because of fake exit edges but assert we
+       never try to insert on those.
+       (fini_pre): Do not remove fake exit edges here...
+       (execute_pre): ...but here, before committing edge inserts.
+
 2008-08-19  Richard Guenther  <rguenther@suse.de>
 
        * passes.c (init_optimization_passes): Exchange store-ccp
index 8c0322a..791d51b 100644 (file)
@@ -1,3 +1,9 @@
+2008-08-20  Richard Guenther  <rguenther@suse.de>
+
+       * gcc.dg/tree-ssa/pr20701.c: Scan vrp1 dump.
+       * gcc.dg/tree-ssa/ssa-dom-thread-1.c: Pass -fno-tree-vrp.
+       * gcc.dg/tree-ssa/ssa-pre-20.c: New testcase.
+
 2008-08-19  Ulrich Weigand  <Ulrich.Weigand@de.ibm.com>
 
        * gcc.dg/torture/fp-int-convert-float.c: Reenable test on SPU.
index d20b102..3ddf48e 100644 (file)
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp2 -fno-early-inlining" } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fno-early-inlining" } */
 
 typedef struct {
   int code;
@@ -36,6 +36,6 @@ can_combine_p (rtx insn, rtx elt)
 }
 
 /* Target with fno-delete-null-pointer-checks should not fold checks */
-/* { dg-final { scan-tree-dump-times "Folding predicate.*to 0" 1 "vrp2" { target { ! keeps_null_pointer_checks } } } } */
-/* { dg-final { scan-tree-dump-times "Folding predicate.*to 0" 0 "vrp2" { target {   keeps_null_pointer_checks } } } } */
-/* { dg-final { cleanup-tree-dump "vrp2" } } */
+/* { dg-final { scan-tree-dump-times "Folding predicate.*to 0" 1 "vrp1" { target { ! keeps_null_pointer_checks } } } } */
+/* { dg-final { scan-tree-dump-times "Folding predicate.*to 0" 0 "vrp1" { target {   keeps_null_pointer_checks } } } } */
+/* { dg-final { cleanup-tree-dump "vrp1" } } */
index d89394a..7671e93 100644 (file)
@@ -1,5 +1,5 @@
 /* { dg-do compile } */ 
-/* { dg-options "-O2 -fdump-tree-dom1-details" } */
+/* { dg-options "-O2 -fno-tree-vrp -fdump-tree-dom1-details" } */
 void t(void);
 void q(void);
 void q1(void);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-20.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-20.c
new file mode 100644 (file)
index 0000000..6361b67
--- /dev/null
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-pre-stats" } */
+
+double pcheck;
+
+void foo(int n, int m, int b)
+{
+  int i, j;
+
+  goto bb18;
+
+start:
+  i = 1;
+  do {
+    j = 1;
+    do {
+      double x = pcheck;
+      x = x + 1;
+      pcheck = x;
+      j = j + 1;
+    } while (j != m);
+    i = i + 1;
+  } while (i != n);
+
+bb18:
+  pcheck = 0.0;
+  goto start;
+}
+
+/* We should have inserted two PHI nodes and the one in the i-loop
+   should have 0.0 in the argument coming from the bb18 block.  */
+
+/* { dg-final { scan-tree-dump "New PHIs: 2" "pre" } } */
+/* { dg-final { scan-tree-dump "PHI <.*0\\\.0" "pre" } } */
+/* { dg-final { cleanup-tree-dump "pre" } } */
index cc56782..d2a55ae 100644 (file)
@@ -3160,14 +3160,9 @@ do_regular_insertion (basic_block block, basic_block dom)
            {
              unsigned int vprime;
 
-             /* This can happen in the very weird case
-                that our fake infinite loop edges have caused a
-                critical edge to appear.  */
-             if (EDGE_CRITICAL_P (pred))
-               {
-                 cant_insert = true;
-                 break;
-               }
+             /* We should never run insertion for the exit block
+                and so not come across fake pred edges.  */
+             gcc_assert (!(pred->flags & EDGE_FAKE));
              bprime = pred->src;
              eprime = phi_translate (expr, ANTIC_IN (block), NULL,
                                      bprime, block);
@@ -3299,14 +3294,9 @@ do_partial_partial_insertion (basic_block block, basic_block dom)
              unsigned int vprime;
              pre_expr edoubleprime;
 
-             /* This can happen in the very weird case
-                that our fake infinite loop edges have caused a
-                critical edge to appear.  */
-             if (EDGE_CRITICAL_P (pred))
-               {
-                 cant_insert = true;
-                 break;
-               }
+             /* We should never run insertion for the exit block
+                and so not come across fake pred edges.  */
+             gcc_assert (!(pred->flags & EDGE_FAKE));
              bprime = pred->src;
              eprime = phi_translate (expr, ANTIC_IN (block),
                                      PA_IN (block),
@@ -4117,7 +4107,6 @@ fini_pre (bool do_fre)
   free_alloc_pool (pre_expr_pool);
   htab_delete (phi_translate_table);
   htab_delete (expression_to_id);
-  remove_fake_exit_edges ();
 
   FOR_ALL_BB (bb)
     {
@@ -4203,6 +4192,11 @@ execute_pre (bool do_fre ATTRIBUTE_UNUSED)
   statistics_counter_event (cfun, "New PHIs", pre_stats.phis);
   statistics_counter_event (cfun, "Eliminated", pre_stats.eliminations);
   statistics_counter_event (cfun, "Constified", pre_stats.constified);
+
+  /* Make sure to remove fake edges before committing our inserts.
+     This makes sure we don't end up with extra critical edges that
+     we would need to split.  */
+  remove_fake_exit_edges ();
   gsi_commit_edge_inserts ();
 
   clear_expression_ids ();
index 383beb1..7351912 100644 (file)
@@ -39,9 +39,18 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-chrec.h"
 
 
-/* Set of SSA names found during the dominator traversal of a
-   sub-graph in find_assert_locations.  */
-static sbitmap found_in_subgraph;
+/* Set of SSA names found live during the RPO traversal of the function
+   for still active basic-blocks.  */
+static sbitmap *live;
+
+/* Return true if the SSA name NAME is live on the edge E.  */
+
+static bool
+live_on_edge (edge e, tree name)
+{
+  return (live[e->dest->index]
+         && TEST_BIT (live[e->dest->index], SSA_NAME_VERSION (name)));
+}
 
 /* Local functions.  */
 static int compare_values (tree val1, tree val2);
@@ -91,10 +100,6 @@ static bitmap need_assert_for;
    ASSERT_EXPRs for SSA name N_I should be inserted.  */
 static assert_locus_t *asserts_for;
 
-/* Set of blocks visited in find_assert_locations.  Used to avoid
-   visiting the same block more than once.  */
-static sbitmap blocks_visited;
-
 /* Value range array.  After propagation, VR_VALUE[I] holds the range
    of values that SSA name N_I may take.  */
 static value_range_t **vr_value;
@@ -3910,7 +3915,7 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
 
   /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
      reachable from E.  */
-  if (TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))
+  if (live_on_edge (e, name)
       && !has_single_use (name))
     {
       register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
@@ -3956,7 +3961,7 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
          && (cst2 == NULL_TREE
              || TREE_CODE (cst2) == INTEGER_CST)
          && INTEGRAL_TYPE_P (TREE_TYPE (name3))
-         && TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name3))
+         && live_on_edge (e, name3)
          && !has_single_use (name3))
        {
          tree tmp;
@@ -3985,7 +3990,7 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
          && TREE_CODE (name2) == SSA_NAME
          && TREE_CODE (cst2) == INTEGER_CST
          && INTEGRAL_TYPE_P (TREE_TYPE (name2))
-         && TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name2))
+         && live_on_edge (e, name2)
          && !has_single_use (name2))
        {
          tree tmp;
@@ -4185,8 +4190,6 @@ register_edge_assert_for (tree name, edge e, gimple_stmt_iterator si,
 }
 
 
-static bool find_assert_locations (basic_block bb);
-
 /* Determine whether the outgoing edges of BB should receive an
    ASSERT_EXPR for each of the operands of BB's LAST statement.
    The last statement of BB must be a COND_EXPR.
@@ -4217,35 +4220,6 @@ find_conditional_asserts (basic_block bb, gimple last)
       if (e->dest == bb)
        continue;
 
-      /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
-        Otherwise, when we finish traversing each of the sub-graphs, we
-        won't know whether the variables were found in the sub-graphs or
-        if they had been found in a block upstream from BB. 
-
-        This is actually a bad idea is some cases, particularly jump
-        threading.  Consider a CFG like the following:
-
-                    0
-                   /|
-                  1 |
-                   \|
-                    2
-                   / \
-                  3   4
-
-        Assume that one or more operands in the conditional at the
-        end of block 0 are used in a conditional in block 2, but not
-        anywhere in block 1.  In this case we will not insert any
-        assert statements in block 1, which may cause us to miss
-        opportunities to optimize, particularly for jump threading.  */
-      FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
-       RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
-
-      /* Traverse the strictly dominated sub-graph rooted at E->DEST
-        to determine if any of the operands in the conditional
-        predicate are used.  */
-      need_assert |= find_assert_locations (e->dest);
-
       /* Register the necessary assertions for each operand in the
         conditional predicate.  */
       FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
@@ -4257,11 +4231,6 @@ find_conditional_asserts (basic_block bb, gimple last)
        }
     }
 
-  /* Finally, indicate that we have found the operands in the
-     conditional.  */
-  FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
-    SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
-
   return need_assert;
 }
 
@@ -4358,18 +4327,6 @@ find_switch_asserts (basic_block bb, gimple last)
       /* Find the edge to register the assert expr on.  */
       e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
 
-      /* Remove the SWITCH_EXPR operand from the FOUND_IN_SUBGRAPH bitmap.
-        Otherwise, when we finish traversing each of the sub-graphs, we
-        won't know whether the variables were found in the sub-graphs or
-        if they had been found in a block upstream from BB.  */
-      RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
-
-      /* Traverse the strictly dominated sub-graph rooted at E->DEST
-        to determine if any of the operands in the conditional
-        predicate are used.  */
-      if (e->dest != bb)
-       need_assert |= find_assert_locations (e->dest);
-
       /* Register the necessary assertions for the operand in the
         SWITCH_EXPR.  */
       need_assert |= register_edge_assert_for (op, e, bsi,
@@ -4386,10 +4343,6 @@ find_switch_asserts (basic_block bb, gimple last)
        }
     }
 
-  /* Finally, indicate that we have found the operand in the
-     SWITCH_EXPR.  */
-  SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
-
   return need_assert;
 }
 
@@ -4458,42 +4411,33 @@ find_switch_asserts (basic_block bb, gimple last)
    inserted by process_assert_insertions.  */
 
 static bool
-find_assert_locations (basic_block bb)
+find_assert_locations_1 (basic_block bb, sbitmap live)
 {
   gimple_stmt_iterator si;
   gimple last;
   gimple phi;
   bool need_assert;
-  basic_block son;
-
-  if (TEST_BIT (blocks_visited, bb->index))
-    return false;
-
-  SET_BIT (blocks_visited, bb->index);
 
   need_assert = false;
+  last = last_stmt (bb);
 
-  /* Traverse all PHI nodes in BB marking used operands.  */
-  for (si = gsi_start_phis (bb); !gsi_end_p(si); gsi_next (&si))
-    {
-      use_operand_p arg_p;
-      ssa_op_iter i;
-      phi = gsi_stmt (si);
+  /* If BB's last statement is a conditional statement involving integer
+     operands, determine if we need to add ASSERT_EXPRs.  */
+  if (last
+      && gimple_code (last) == GIMPLE_COND
+      && !fp_predicate (last)
+      && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
+    need_assert |= find_conditional_asserts (bb, last);
 
-      FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
-       {
-         tree arg = USE_FROM_PTR (arg_p);
-         if (TREE_CODE (arg) == SSA_NAME)
-           {
-             gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
-             SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
-           }
-       }
-    }
+  /* If BB's last statement is a switch statement involving integer
+     operands, determine if we need to add ASSERT_EXPRs.  */
+  if (last
+      && gimple_code (last) == GIMPLE_SWITCH
+      && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
+    need_assert |= find_switch_asserts (bb, last);
 
   /* Traverse all the statements in BB marking used names and looking
      for statements that may infer assertions for their used operands.  */
-  last = NULL;
   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
     {
       gimple stmt;
@@ -4508,12 +4452,8 @@ find_assert_locations (basic_block bb)
          tree value;
          enum tree_code comp_code;
 
-         /* Mark OP in bitmap FOUND_IN_SUBGRAPH.  If STMT is inside
-            the sub-graph of a conditional block, when we return from
-            this recursive walk, our parent will use the
-            FOUND_IN_SUBGRAPH bitset to determine if one of the
-            operands it was looking for was present in the sub-graph.  */
-         SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
+         /* Mark OP in our live bitmap.  */
+         SET_BIT (live, SSA_NAME_VERSION (op));
 
          /* If OP is used in such a way that we can infer a value
             range for it, and we don't find a previous assertion for
@@ -4564,34 +4504,113 @@ find_assert_locations (basic_block bb)
                }
            }
        }
-
-      /* Remember the last statement of the block.  */
-      last = stmt;
     }
 
-  /* If BB's last statement is a conditional expression
-     involving integer operands, recurse into each of the sub-graphs
-     rooted at BB to determine if we need to add ASSERT_EXPRs.  */
-  if (last
-      && gimple_code (last) == GIMPLE_COND
-      && !fp_predicate (last)
-      && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
-    need_assert |= find_conditional_asserts (bb, last);
-
-  if (last
-      && gimple_code (last) == GIMPLE_SWITCH
-      && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
-    need_assert |= find_switch_asserts (bb, last);
+  /* Traverse all PHI nodes in BB marking used operands.  */
+  for (si = gsi_start_phis (bb); !gsi_end_p(si); gsi_next (&si))
+    {
+      use_operand_p arg_p;
+      ssa_op_iter i;
+      phi = gsi_stmt (si);
 
-  /* Recurse into the dominator children of BB.  */
-  for (son = first_dom_son (CDI_DOMINATORS, bb);
-       son;
-       son = next_dom_son (CDI_DOMINATORS, son))
-    need_assert |= find_assert_locations (son);
+      FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
+       {
+         tree arg = USE_FROM_PTR (arg_p);
+         if (TREE_CODE (arg) == SSA_NAME)
+           SET_BIT (live, SSA_NAME_VERSION (arg));
+       }
+    }
 
   return need_assert;
 }
 
+/* Do an RPO walk over the function computing SSA name liveness
+   on-the-fly and deciding on assert expressions to insert.
+   Returns true if there are assert expressions to be inserted.  */
+
+static bool
+find_assert_locations (void)
+{
+  int *rpo = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
+  int *bb_rpo = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
+  int *last_rpo = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
+  int rpo_cnt, i;
+  bool need_asserts;
+
+  live = XCNEWVEC (sbitmap, last_basic_block + NUM_FIXED_BLOCKS);
+  rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
+  for (i = 0; i < rpo_cnt; ++i)
+    bb_rpo[rpo[i]] = i;
+
+  need_asserts = false;
+  for (i = rpo_cnt-1; i >= 0; --i)
+    {
+      basic_block bb = BASIC_BLOCK (rpo[i]);
+      edge e;
+      edge_iterator ei;
+
+      if (!live[rpo[i]])
+       {
+         live[rpo[i]] = sbitmap_alloc (num_ssa_names);
+         sbitmap_zero (live[rpo[i]]);
+       }
+
+      /* Process BB and update the live information with uses in
+         this block.  */
+      need_asserts |= find_assert_locations_1 (bb, live[rpo[i]]);
+
+      /* Merge liveness into the predecessor blocks and free it.  */
+      if (!sbitmap_empty_p (live[rpo[i]]))
+       {
+         int pred_rpo = i;
+         FOR_EACH_EDGE (e, ei, bb->preds)
+           {
+             int pred = e->src->index;
+             if (e->flags & EDGE_DFS_BACK)
+               continue;
+
+             if (!live[pred])
+               {
+                 live[pred] = sbitmap_alloc (num_ssa_names);
+                 sbitmap_zero (live[pred]);
+               }
+             sbitmap_a_or_b (live[pred], live[pred], live[rpo[i]]);
+
+             if (bb_rpo[pred] < pred_rpo)
+               pred_rpo = bb_rpo[pred];
+           }
+
+         /* Record the RPO number of the last visited block that needs
+            live information from this block.  */
+         last_rpo[rpo[i]] = pred_rpo;
+       }
+      else
+       {
+         sbitmap_free (live[rpo[i]]);
+         live[rpo[i]] = NULL;
+       }
+
+      /* We can free all successors live bitmaps if all their
+         predecessors have been visited already.  */
+      FOR_EACH_EDGE (e, ei, bb->succs)
+       if (last_rpo[e->dest->index] == i
+           && live[e->dest->index])
+         {
+           sbitmap_free (live[e->dest->index]);
+           live[e->dest->index] = NULL;
+         }
+    }
+
+  XDELETEVEC (rpo);
+  XDELETEVEC (bb_rpo);
+  XDELETEVEC (last_rpo);
+  for (i = 0; i < last_basic_block + NUM_FIXED_BLOCKS; ++i)
+    if (live[i])
+      sbitmap_free (live[i]);
+  XDELETEVEC (live);
+
+  return need_asserts;
+}
 
 /* Create an ASSERT_EXPR for NAME and insert it in the location
    indicated by LOC.  Return true if we made any edge insertions.  */
@@ -4718,27 +4737,12 @@ process_assert_insertions (void)
 static void
 insert_range_assertions (void)
 {
-  edge e;
-  edge_iterator ei;
-  bool update_ssa_p;
-  
-  found_in_subgraph = sbitmap_alloc (num_ssa_names);
-  sbitmap_zero (found_in_subgraph);
-
-  blocks_visited = sbitmap_alloc (last_basic_block);
-  sbitmap_zero (blocks_visited);
-
   need_assert_for = BITMAP_ALLOC (NULL);
   asserts_for = XCNEWVEC (assert_locus_t, num_ssa_names);
 
   calculate_dominance_info (CDI_DOMINATORS);
 
-  update_ssa_p = false;
-  FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
-    if (find_assert_locations (e->dest))
-      update_ssa_p = true;
-
-  if (update_ssa_p)
+  if (find_assert_locations ())
     {
       process_assert_insertions ();
       update_ssa (TODO_update_ssa_no_phi);
@@ -4750,7 +4754,6 @@ insert_range_assertions (void)
       dump_function_to_file (current_function_decl, dump_file, dump_flags);
     }
 
-  sbitmap_free (found_in_subgraph);
   free (asserts_for);
   BITMAP_FREE (need_assert_for);
 }
@@ -5019,8 +5022,6 @@ remove_range_assertions (void)
        else
          gsi_next (&si);
       }
-
-  sbitmap_free (blocks_visited);
 }