-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
I've been doing some research into improving certain aspects of our
warnings, particularly removing false positives from the warnings which
require dataflow information. I think it's reasonably well known that
many of the false positives occur due to unexecutable edges remaining in
the CFG.
Long term I think we're going to need a more structured approach to path
isolation and I'm still pondering exactly what that might look like.
In the mean time one thing is clear the current jump threading is quite
important for eliminating many of the unexecutable edges in the CFG.
Furthermore, the cases I'm looking at require us capture more of the
secondary effects of jump threading.
Let's consider this CFG (from a routine in cfgexpand.c)
A
/ \
B C
| / \
| D E
| | / \
| | F G
\| |
\|
H
/ \
I J
/ \
L M
| / \
| N O
| | / \
| | P Q
\| |
\|
R
As it turns out some blocks have the same condition (A,I), (C,M), (E,O).
But because of the merge block H, no threading is possible. I've got
patches which let us copy H into B, D & F. That exposes the jump
threads B->L, D->M and F->M. Unfortunately, we need another iteration
of jump threading to then thread D->N and F->O and then another
iteration to thread F->P with the net result looking something like this:
A
/ \
BH'L C
| / \
|DH'N E
| | / \
| |FH'P G
\| |
\|
R
I don't think anyone is going to argue for a return to the iterated DOM
approach we had in the past. Luckily we can often pick up the secondary
effects by looking deeper into the CFG when we do find a threading
opportunity. ie, when we discover D->I->M, go ahead and look at M and
see if we can thread through it to N or O and so-on.
That turns out to be relatively easy and cheap if we restrict the form
of M so that we don't need to create a duplicate of M (which ties back
to our long term need for a more structured approach to path isolation).
The attached patch allows us to capture some of these secondary effects
by looking at the destination of a threadable jump to see if it is yet
another conditional with a statically computable destination.
Bootstrapped and regression tested on x86_64-unknown-linux-gnu. Trivial
testcase included :-) OK for trunk?
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
iQEcBAEBAgAGBQJNjMM7AAoJEBRtltQi2kC7mtAH/2yC58nNaW1ZZP6OQFztNTHo
nyRAIjS7NxT8Sal84cRwfaAgND74VesVUs8EgYY9G7brHWihBWYqZ8gRjRp2VJqA
EM9IIScKgYqM5/2+41Iy2yGY3yMksOpVPX3LZfCHWKW0PIycpmHnLglGUSU33rbr
8EtVbv3PuXn6OnqYqA5onCmLiI4YRapLnF+iNvH3r5DI4EJKPweLPBygye/aDI+F
DCZl9zCKfdrKvvkA81o1+f2CQPC9507w2B1MZBM3uXRJGETrLTNKiyIDyciq2OG+
SR2e72co/zbUTU1HQlpkL5nCEl4xn8fYmZQlaZjp3OypkY86vI5YnStjPKjnc2w=
=z6nn
-----END PGP SIGNATURE-----
* tree-ssa-threadupdate.c (redirect_edges): Call
create_edge_and_update_destination_phis as needed.
(create_edge_and_update_destination_phis): Accept new BB argument.
All callers updated.
(thread_block): Do not update the profile when threading around
intermediate blocks.
(thread_single_edge): Likewise.
(determine_bb_domination_status): If BB is not a successor of the
loop header, return NONDOMINATING.
(register_jump_thread): Note when we register a jump thread around
an intermediate block.
* tree-ssa-threadedge.c (thread_around_empty_block): New function.
(thread_across_edge): Use it.
* gcc.dg/tree-ssa/ssa-dom-thread-3.c: New test.
Index: tree-ssa-threadupdate.c
===================================================================
*** tree-ssa-threadupdate.c (revision 171364)
--- tree-ssa-threadupdate.c (working copy)
*************** lookup_redirection_data (edge e, edge in
*** 304,317 ****
destination. */
static void
! create_edge_and_update_destination_phis (struct redirection_data *rd)
{
! edge e = make_edge (rd->dup_block, rd->outgoing_edge->dest, EDGE_FALLTHRU);
gimple_stmt_iterator gsi;
rescan_loop_exit (e, true, false);
e->probability = REG_BR_PROB_BASE;
! e->count = rd->dup_block->count;
e->aux = rd->outgoing_edge->aux;
/* If there are any PHI nodes at the destination of the outgoing edge
--- 304,318 ----
destination. */
static void
! create_edge_and_update_destination_phis (struct redirection_data *rd,
! basic_block bb)
{
! edge e = make_edge (bb, rd->outgoing_edge->dest, EDGE_FALLTHRU);
gimple_stmt_iterator gsi;
rescan_loop_exit (e, true, false);
e->probability = REG_BR_PROB_BASE;
! e->count = bb->count;
e->aux = rd->outgoing_edge->aux;
/* If there are any PHI nodes at the destination of the outgoing edge
*************** create_duplicates (void **slot, void *da
*** 359,365 ****
/* Go ahead and wire up outgoing edges and update PHIs for the duplicate
block. */
! create_edge_and_update_destination_phis (rd);
}
/* Keep walking the hash table. */
--- 360,366 ----
/* Go ahead and wire up outgoing edges and update PHIs for the duplicate
block. */
! create_edge_and_update_destination_phis (rd, rd->dup_block);
}
/* Keep walking the hash table. */
*************** fixup_template_block (void **slot, void
*** 380,386 ****
and halt the hash table traversal. */
if (rd->dup_block && rd->dup_block == local_info->template_block)
{
! create_edge_and_update_destination_phis (rd);
return 0;
}
--- 381,387 ----
and halt the hash table traversal. */
if (rd->dup_block && rd->dup_block == local_info->template_block)
{
! create_edge_and_update_destination_phis (rd, rd->dup_block);
return 0;
}
*************** redirect_edges (void **slot, void *data)
*** 443,448 ****
--- 444,454 ----
remove_ctrl_stmt_and_useless_edges (local_info->bb,
rd->outgoing_edge->dest);
+ /* If we are threading beyond the immediate successors of
+ the duplicate, then BB will have no edges, create one. */
+ if (EDGE_COUNT (local_info->bb->succs) == 0)
+ create_edge_and_update_destination_phis (rd, local_info->bb);
+
/* Fixup the flags on the single remaining edge. */
single_succ_edge (local_info->bb)->flags
&= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL);
*************** thread_block (basic_block bb, bool noloo
*** 565,572 ****
continue;
}
! update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
! e->count, (edge) e->aux);
/* Insert the outgoing edge into the hash table if it is not
already in the hash table. */
--- 571,579 ----
continue;
}
! if (e->dest == e2->src)
! update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
! e->count, (edge) e->aux);
/* Insert the outgoing edge into the hash table if it is not
already in the hash table. */
*************** thread_single_edge (edge e)
*** 650,661 ****
}
/* Otherwise, we need to create a copy. */
! update_bb_profile_for_threading (bb, EDGE_FREQUENCY (e), e->count, eto);
rd.outgoing_edge = eto;
create_block_for_threading (bb, &rd);
! create_edge_and_update_destination_phis (&rd);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
--- 657,669 ----
}
/* Otherwise, we need to create a copy. */
! if (e->dest == eto->src)
! update_bb_profile_for_threading (bb, EDGE_FREQUENCY (e), e->count, eto);
rd.outgoing_edge = eto;
create_block_for_threading (bb, &rd);
! create_edge_and_update_destination_phis (&rd, rd.dup_block);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
*************** determine_bb_domination_status (struct l
*** 704,710 ****
edge e;
#ifdef ENABLE_CHECKING
! /* This function assumes BB is a successor of LOOP->header. */
{
bool ok = false;
--- 712,720 ----
edge e;
#ifdef ENABLE_CHECKING
! /* This function assumes BB is a successor of LOOP->header.
! If that is not the case return DOMST_NONDOMINATING which
! is always safe. */
{
bool ok = false;
*************** determine_bb_domination_status (struct l
*** 717,723 ****
}
}
! gcc_assert (ok);
}
#endif
--- 727,734 ----
}
}
! if (!ok)
! return DOMST_NONDOMINATING;
}
#endif
*************** register_jump_thread (edge e, edge e2)
*** 1099,1104 ****
--- 1110,1120 ----
if (threaded_edges == NULL)
threaded_edges = VEC_alloc (edge, heap, 10);
+ if (dump_file && (dump_flags & TDF_DETAILS)
+ && e->dest != e2->src)
+ fprintf (dump_file,
+ " Registering jump thread around one or more intermediate
blocks\n");
+
VEC_safe_push (edge, heap, threaded_edges, e);
VEC_safe_push (edge, heap, threaded_edges, e2);
}
Index: tree-ssa-threadedge.c
===================================================================
*** tree-ssa-threadedge.c (revision 171364)
--- tree-ssa-threadedge.c (working copy)
*************** simplify_control_stmt_condition (edge e,
*** 583,588 ****
--- 583,661 ----
return cached_lhs;
}
+ /* TAKEN_EDGE represents the an edge taken as a result of jump threading.
+ See if we can thread around TAKEN_EDGE->dest as well. If so, return
+ the edge out of TAKEN_EDGE->dest that we can statically compute will be
+ traversed.
+
+ We are much more restrictive as to the contents of TAKEN_EDGE->dest
+ as the path isolation code in tree-ssa-threadupdate.c isn't prepared
+ to handle copying intermediate blocks on a threaded path.
+
+ Long term a more consistent and structured approach to path isolation
+ would be a huge help. */
+ static edge
+ thread_around_empty_block (edge taken_edge,
+ gimple dummy_cond,
+ bool handle_dominating_asserts,
+ tree (*simplify) (gimple, gimple),
+ bitmap visited)
+ {
+ basic_block bb = taken_edge->dest;
+ gimple_stmt_iterator gsi;
+ gimple stmt;
+ tree cond;
+
+ /* This block must have a single predecessor (E->dest). */
+ if (!single_pred_p (bb))
+ return NULL;
+
+ /* This block must have more than one successor. */
+ if (single_succ_p (bb))
+ return NULL;
+
+ /* This block can have no PHI nodes. This is overly conservative. */
+ if (!gsi_end_p (gsi_start_phis (bb)))
+ return NULL;
+
+ /* Skip over DEBUG statements at the start of the block. */
+ gsi = gsi_start_bb (bb);
+ while (!gsi_end_p (gsi)
+ && gimple_code (gsi_stmt (gsi)) == GIMPLE_DEBUG)
+ gsi_next (&gsi);
+
+ if (gsi_end_p (gsi))
+ return NULL;
+
+ /* This block can have no statements other than its control altering
+ statement. This is overly conservative. */
+ stmt = gsi_stmt (gsi);
+ if (gimple_code (stmt) != GIMPLE_COND
+ && gimple_code (stmt) != GIMPLE_GOTO
+ && gimple_code (stmt) != GIMPLE_SWITCH)
+ return NULL;
+
+ /* Extract and simplify the condition. */
+ cond = simplify_control_stmt_condition (taken_edge, stmt, dummy_cond,
+ simplify, handle_dominating_asserts);
+
+ /* If the condition can be statically computed and we have not already
+ visited the destination edge, then add the taken edge to our thread
+ path. */
+ if (cond && is_gimple_min_invariant (cond))
+ {
+ edge taken_edge = find_taken_edge (bb, cond);
+
+ if (bitmap_bit_p (visited, taken_edge->dest->index))
+ return NULL;
+ bitmap_set_bit (visited, taken_edge->dest->index);
+ return taken_edge;
+ }
+
+ return NULL;
+ }
+
+
/* We are exiting E->src, see if E->dest ends with a conditional
jump which has a known value when reached via E.
*************** thread_across_edge (gimple dummy_cond,
*** 661,676 ****
tree cond;
/* Extract and simplify the condition. */
! cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify,
handle_dominating_asserts);
if (cond && is_gimple_min_invariant (cond))
{
edge taken_edge = find_taken_edge (e->dest, cond);
basic_block dest = (taken_edge ? taken_edge->dest : NULL);
if (dest == e->dest)
goto fail;
remove_temporary_equivalences (stack);
register_jump_thread (e, taken_edge);
}
--- 734,777 ----
tree cond;
/* Extract and simplify the condition. */
! cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify,
! handle_dominating_asserts);
if (cond && is_gimple_min_invariant (cond))
{
edge taken_edge = find_taken_edge (e->dest, cond);
basic_block dest = (taken_edge ? taken_edge->dest : NULL);
+ bitmap visited;
+ edge e2;
if (dest == e->dest)
goto fail;
+ /* DEST could be null for a computed jump to an absolute
+ address. If DEST is not null, then see if we can thread
+ through it as well, this helps capture secondary effects
+ of threading without having to re-run DOM or VRP. */
+ if (dest)
+ {
+ /* We don't want to thread back to a block we have already
+ visited. This may be overly conservative. */
+ visited = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (visited, dest->index);
+ bitmap_set_bit (visited, e->dest->index);
+ do
+ {
+ e2 = thread_around_empty_block (taken_edge,
+ dummy_cond,
+ handle_dominating_asserts,
+ simplify,
+ visited);
+ if (e2)
+ taken_edge = e2;
+ }
+ while (e2);
+ BITMAP_FREE (visited);
+ }
+
remove_temporary_equivalences (stack);
register_jump_thread (e, taken_edge);
}
Index: testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c (revision 0)
--- testsuite/gcc.dg/tree-ssa/ssa-dom-thread-3.c (revision 0)
***************
*** 0 ****
--- 1,47 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-dom1-details" } */
+ extern void abort (void) __attribute__ ((__noreturn__));
+ union tree_node;
+ typedef union tree_node *tree;
+ enum tree_code
+ {
+ VAR_DECL,
+ SSA_NAME,
+ MAX_TREE_CODES
+ };
+ extern unsigned char tree_contains_struct[MAX_TREE_CODES][64];
+ struct tree_base
+ {
+ enum tree_code code:16;
+ };
+ enum tree_node_structure_enum
+ {
+ TS_DECL_COMMON
+ };
+ struct tree_ssa_name
+ {
+ tree var;
+ };
+ union tree_node
+ {
+ struct tree_base base;
+ struct tree_ssa_name ssa_name;
+ };
+ long
+ expand_one_var (tree var, unsigned char toplevel, unsigned char really_expand)
+ {
+ tree origvar = var;
+ var = var->ssa_name.var;
+ if (((enum tree_code) (origvar)->base.code) == SSA_NAME
+ && !((var->base.code != VAR_DECL)))
+ abort ();
+ if ((var->base.code) != VAR_DECL && ((origvar)->base.code) != SSA_NAME)
+ ;
+ else if (tree_contains_struct[(var->base.code)][(TS_DECL_COMMON)] != 1)
+ abort ();
+ }
+ /* We should thread the jump, through an intermediate block. */
+ /* { dg-final { scan-tree-dump-times "Threaded" 1 "dom1"} } */
+ /* { dg-final { scan-tree-dump-times "one or more intermediate" 1 "dom1"} } */
+ /* { dg-final { cleanup-tree-dump "dom1" } } */
+
