This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] "Fix" PR70623
- From: Richard Biener <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 13 Apr 2016 13:28:43 +0200 (CEST)
- Subject: [PATCH] "Fix" PR70623
- Authentication-results: sourceware.org; auth=none
The following happens to fix the testcase in PR70623 while in reality
I was only cleaning up code, adding comments when I figured that
the worklist handling is a) obfuscated and b) visits nodes
unnecessarily. b) may be the reason for this bug as the cruical
difference appears in the second iteration where we have
-ANTIC_OUT[13] := { _9 (0006) }
-ANTIC_IN[13] := { _9 (0006) }
-S[13] := { _9 (0006) }
-ANTIC_OUT[6] := { _9 (0006) }
-[changed] ANTIC_IN[6] := { _9 (0006),
{mem_ref<0B>,addr_expr<&nm>}@.MEM_7(D) (0007) }
-S[6] := { _9 (0006) }
-ANTIC_OUT[14] := { _9 (0006) }
-ANTIC_IN[14] := { _9 (0006) }
-S[14] := { _9 (0006) }
thus ANTIC_IN for 6 changes because we visit it at an unfortunate
point. The change in iteration order with the patch is
@@ -23,18 +23,12 @@
18
20
11
-19
10
-12
-15
7
5
4
16
8
-13
-6
-14
3
21
2
@@ -45,5480 +39,4 @@
12
15
7
-5
... (the patched variant has finished now)
we _do_ visit 6 again, at line 36, so it's cruical we don't pick up
intermittend state from antic iteration 0 and thus skip computing antic in
for 6 during iteration 1.
I'm not 100% sure this isn't really an issue with the iteration order
and constraints on how the DF problem can converge. But at least the
patch also improves compile-time.
Bootstrap and regtest running on x86_64_unknown-linux-gnu.
Richard.
2016-04-13 Richard Biener <rguenther@suse.de>
PR tree-optimization/70623
* tree-ssa-pre.c (changed_blocks): Make global ...
(compute_antic): ... local here. Move and fix worklist
handling here. Do not clear EDGE_DFS_BACK or call mark_dfs_back_edges.
(compute_antic_aux): Add dumping for MAX assumed succs. Remove
worklist handling, dump when ANTIC_IN changed.
(compute_partial_antic_aux): Remove worklist handling.
(init_pre): Do not compute post dominators. Add a comment about
the CFG order chosen.
(fini_pre): Do not free post dominators.
* gcc.dg/torture/pr70623.c: New testcase.
Index: gcc/tree-ssa-pre.c
===================================================================
*** gcc/tree-ssa-pre.c (revision 234894)
--- gcc/tree-ssa-pre.c (working copy)
*************** prune_clobbered_mems (bitmap_set_t set,
*** 2062,2072 ****
static sbitmap has_abnormal_preds;
- /* List of blocks that may have changed during ANTIC computation and
- thus need to be iterated over. */
-
- static sbitmap changed_blocks;
-
/* Compute the ANTIC set for BLOCK.
If succs(BLOCK) > 1 then
--- 2078,2083 ----
*************** compute_antic_aux (basic_block block, bo
*** 2125,2130 ****
--- 2136,2151 ----
first = e->dest;
else if (BB_VISITED (e->dest))
worklist.quick_push (e->dest);
+ else
+ {
+ /* Unvisited successors get their ANTIC_IN replaced by the
+ maximal set to arrive at a maximum ANTIC_IN solution.
+ We can ignore them in the intersection operation and thus
+ need not explicitely represent that maximum solution. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "ANTIC_IN is MAX on %d->%d\n",
+ e->src->index, e->dest->index);
+ }
}
/* Of multiple successors we have to have visited one already
*************** compute_antic_aux (basic_block block, bo
*** 2167,2180 ****
clean (ANTIC_IN (block));
if (!bitmap_set_equal (old, ANTIC_IN (block)))
! {
! changed = true;
! bitmap_set_bit (changed_blocks, block->index);
! FOR_EACH_EDGE (e, ei, block->preds)
! bitmap_set_bit (changed_blocks, e->src->index);
! }
! else
! bitmap_clear_bit (changed_blocks, block->index);
maybe_dump_sets:
if (dump_file && (dump_flags & TDF_DETAILS))
--- 2188,2194 ----
clean (ANTIC_IN (block));
if (!bitmap_set_equal (old, ANTIC_IN (block)))
! changed = true;
maybe_dump_sets:
if (dump_file && (dump_flags & TDF_DETAILS))
*************** compute_antic_aux (basic_block block, bo
*** 2182,2187 ****
--- 2196,2203 ----
if (ANTIC_OUT)
print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
+ if (changed)
+ fprintf (dump_file, "[changed] ");
print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
block->index);
*************** compute_partial_antic_aux (basic_block b
*** 2313,2326 ****
dependent_clean (PA_IN (block), ANTIC_IN (block));
if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
! {
! changed = true;
! bitmap_set_bit (changed_blocks, block->index);
! FOR_EACH_EDGE (e, ei, block->preds)
! bitmap_set_bit (changed_blocks, e->src->index);
! }
! else
! bitmap_clear_bit (changed_blocks, block->index);
maybe_dump_sets:
if (dump_file && (dump_flags & TDF_DETAILS))
--- 2329,2335 ----
dependent_clean (PA_IN (block), ANTIC_IN (block));
if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
! changed = true;
maybe_dump_sets:
if (dump_file && (dump_flags & TDF_DETAILS))
*************** compute_antic (void)
*** 2346,2351 ****
--- 2355,2362 ----
int num_iterations = 0;
basic_block block;
int i;
+ edge_iterator ei;
+ edge e;
/* If any predecessor edges are abnormal, we punt, so antic_in is empty.
We pre-build the map of blocks with incoming abnormal edges here. */
*************** compute_antic (void)
*** 2354,2371 ****
FOR_ALL_BB_FN (block, cfun)
{
- edge_iterator ei;
- edge e;
-
FOR_EACH_EDGE (e, ei, block->preds)
! {
! e->flags &= ~EDGE_DFS_BACK;
! if (e->flags & EDGE_ABNORMAL)
! {
! bitmap_set_bit (has_abnormal_preds, block->index);
! break;
! }
! }
BB_VISITED (block) = 0;
--- 2365,2376 ----
FOR_ALL_BB_FN (block, cfun)
{
FOR_EACH_EDGE (e, ei, block->preds)
! if (e->flags & EDGE_ABNORMAL)
! {
! bitmap_set_bit (has_abnormal_preds, block->index);
! break;
! }
BB_VISITED (block) = 0;
*************** compute_antic (void)
*** 2377,2384 ****
/* At the exit block we anticipate nothing. */
BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun)) = 1;
! changed_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun) + 1);
! bitmap_ones (changed_blocks);
while (changed)
{
if (dump_file && (dump_flags & TDF_DETAILS))
--- 2382,2389 ----
/* At the exit block we anticipate nothing. */
BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun)) = 1;
! sbitmap worklist = sbitmap_alloc (last_basic_block_for_fn (cfun) + 1);
! bitmap_ones (worklist);
while (changed)
{
if (dump_file && (dump_flags & TDF_DETAILS))
*************** compute_antic (void)
*** 2391,2402 ****
changed = false;
for (i = postorder_num - 1; i >= 0; i--)
{
! if (bitmap_bit_p (changed_blocks, postorder[i]))
{
basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
! changed |= compute_antic_aux (block,
! bitmap_bit_p (has_abnormal_preds,
! block->index));
}
}
/* Theoretically possible, but *highly* unlikely. */
--- 2396,2413 ----
changed = false;
for (i = postorder_num - 1; i >= 0; i--)
{
! if (bitmap_bit_p (worklist, postorder[i]))
{
basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
! bitmap_clear_bit (worklist, block->index);
! if (compute_antic_aux (block,
! bitmap_bit_p (has_abnormal_preds,
! block->index)))
! {
! FOR_EACH_EDGE (e, ei, block->preds)
! bitmap_set_bit (worklist, e->src->index);
! changed = true;
! }
}
}
/* Theoretically possible, but *highly* unlikely. */
*************** compute_antic (void)
*** 2408,2415 ****
if (do_partial_partial)
{
! bitmap_ones (changed_blocks);
! mark_dfs_back_edges ();
num_iterations = 0;
changed = true;
while (changed)
--- 2419,2425 ----
if (do_partial_partial)
{
! bitmap_ones (worklist);
num_iterations = 0;
changed = true;
while (changed)
*************** compute_antic (void)
*** 2420,2432 ****
changed = false;
for (i = postorder_num - 1 ; i >= 0; i--)
{
! if (bitmap_bit_p (changed_blocks, postorder[i]))
{
basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
! changed
! |= compute_partial_antic_aux (block,
! bitmap_bit_p (has_abnormal_preds,
! block->index));
}
}
/* Theoretically possible, but *highly* unlikely. */
--- 2430,2447 ----
changed = false;
for (i = postorder_num - 1 ; i >= 0; i--)
{
! if (bitmap_bit_p (worklist, postorder[i]))
{
basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
! bitmap_clear_bit (worklist, block->index);
! if (compute_partial_antic_aux (block,
! bitmap_bit_p (has_abnormal_preds,
! block->index)))
! {
! FOR_EACH_EDGE (e, ei, block->preds)
! bitmap_set_bit (worklist, e->src->index);
! changed = true;
! }
}
}
/* Theoretically possible, but *highly* unlikely. */
*************** compute_antic (void)
*** 2436,2442 ****
num_iterations);
}
sbitmap_free (has_abnormal_preds);
! sbitmap_free (changed_blocks);
}
--- 2451,2457 ----
num_iterations);
}
sbitmap_free (has_abnormal_preds);
! sbitmap_free (worklist);
}
*************** init_pre (void)
*** 4695,4706 ****
connect_infinite_loops_to_exit ();
memset (&pre_stats, 0, sizeof (pre_stats));
postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
postorder_num = inverted_post_order_compute (postorder);
alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets));
- calculate_dominance_info (CDI_POST_DOMINATORS);
calculate_dominance_info (CDI_DOMINATORS);
bitmap_obstack_initialize (&grand_bitmap_obstack);
--- 4748,4761 ----
connect_infinite_loops_to_exit ();
memset (&pre_stats, 0, sizeof (pre_stats));
+ /* For ANTIC computation we need a postorder that also guarantees that
+ a block with a single successor is visited after its successor.
+ RPO on the inverted CFG has this property. */
postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
postorder_num = inverted_post_order_compute (postorder);
alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets));
calculate_dominance_info (CDI_DOMINATORS);
bitmap_obstack_initialize (&grand_bitmap_obstack);
*************** fini_pre ()
*** 4734,4741 ****
name_to_id.release ();
free_aux_for_blocks ();
-
- free_dominance_info (CDI_POST_DOMINATORS);
}
namespace {
--- 4789,4794 ----
Index: gcc/testsuite/gcc.dg/torture/pr70623.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr70623.c (revision 0)
--- gcc/testsuite/gcc.dg/torture/pr70623.c (working copy)
***************
*** 0 ****
--- 1,32 ----
+ /* { dg-do compile } */
+ /* { dg-additional-options "-w" } */
+
+ int nm;
+ int *av;
+
+ void
+ h9(void)
+ {
+ for (;;) {
+ int wk, rc;
+ int **ptr_10 = &av;
+ if (*av != 0) {
+ }
+ u4:
+ wk = 0;
+ for (rc = 0; rc < 3; ++rc) {
+ int bc = (rc ? rc : nm);
+ int ud = bc ? (*av ? 0 : rc) : 1;
+ if (ud != 0) {
+ if (*av != 0)
+ goto u4;
+ for (;;) {
+ }
+ }
+ }
+ while (wk < 3) {
+ av = **ptr_10;
+ ++wk;
+ }
+ }
+ }