-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On 03/26/11 11:43, Richard Guenther wrote:
>
>> Looks good to me apart from not using gsi_start_nondebug_bb in
>> thread_around_empty_block.
Ah. I wasn't aware of gsi_start_nondebug_bb. I updated the patch to
use it, ran another bootstrap and regression test.
Attached is the final patch that's being installed onto the trunk.
Thanks,
Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
iQEcBAEBAgAGBQJNkNSJAAoJEBRtltQi2kC73DcIALH8k+/SXMcZy7tYcVrTs6Bq
YR5kyIIMIMjf2G+pEas0WVEP99XoJLbxUHITQFNZtdnhvl62BV23BiVyWVS0KRqB
oUdxdcQhV8x1F6JKKt9oHQ1eVd1ktNTrVGYnWnx24f97x8VYpaKG4fLAsPW221Sy
qBgm4iaY5/nnI8w7fuoruPSUXvMGQVN2g24HcQ/nQ3FPJvmeyZswRajWjylj9Zgg
wZXvmrG4GeOpOIZTD2KwlA1e3f8S1kzIKabOdz/Wgz3jfybI1tE/msSd6m4ID9FE
2m+lQ+AwT40xqcet0M3AB667JVw87Q01Gm+hAmK8qrgIZrhjpMZuHE2wCC6hDjg=
=KKSc
-----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 171620)
--- 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: 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" } } */
+
Index: tree-ssa-threadedge.c
===================================================================
*** tree-ssa-threadedge.c (revision 171620)
--- tree-ssa-threadedge.c (working copy)
*************** simplify_control_stmt_condition (edge e,
*** 583,588 ****
--- 583,658 ----
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_nondebug_bb (bb);
+
+ 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);
}
--- 731,774 ----
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);
}
