-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
This is merely an infrastructure patch in preparation for another
improvement in the jump threading code. It shouldn't affect the code we
generate at all.
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. What we
want to do is make 3 copies of H, each reachable from one predecessor of
the original H.
To do this we need to know the edge into the joiner block so that we
can wire up the copy to the right predecessor. We need the outgoing
edge from the joiner block that is threadable and finally we need the
destination edge.
This is a fairly simple extension to the existing code -- but we're
going to need the ability to store more information in the E->aux field.
Previously E->aux stored the destination edge for a jump thread. This
change allows E->aux to store additional data by changing it from a
single edge pointer to instead point to an array of edges.
FWIW, the patch to make copies of H to enable threading is probably the
limit of what can be done with the current threader. I'm hoping to
start prototyping more generic path isolation code shortly.
Bootstrapped and regression tested on x86_64-unknown-linux-gnu.
OK for trunk?
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
iQEcBAEBAgAGBQJNvuTiAAoJEBRtltQi2kC75OAIAIe77UqINq3jUeKdYMZ/OII1
+x+al4zcsx9YOCw6wdmMjWUS0Z9IcPmuKQIoPXtgq+R1qnADg5OnAiwKKZvdukIc
mhzbp+IBiDezFufv373shlp+hZtPN4QL73TDffWC4F9Eb7mYzADsIuAz2SIRcFVd
HB1UAxiiD8nUA4/uVa8Ree4PA91u8M3OGpC2iwW3eq/sBIzbdCs+TEI2Nps6qDLa
qmjNab/Zunh5OadJgtGB7Uk9pBv/I6zsbHmHCcZjRyOMyg8UXMCJTDjqpgUWJHAg
vIast5ayTI45cwJO69qykqZdrmrNUDpOHf/93HjNMhJvdSqPkB7eHiBvlcy2RdA=
=QsON
-----END PGP SIGNATURE-----
* tree-ssa-threadupdate.c (remove_ctrl_stmt_and_useless_edges): Clear
AUX field of outgoing edges.
(craete_edge_and_update_destination_phis): Handle AUX field being an
array of edges. Free the AUX field before clearning it.
(thread_block, thread_through_loop_header): Likewise.
(thread_single_edge, mark_threaded_blocks): Likewise.
(redirect_edges): Delay clearing the AUX field. Free the AUX field.
(register_jump_thread): Do not attempt to thread to a NULL edge.
Index: tree-ssa-threadupdate.c
===================================================================
*** tree-ssa-threadupdate.c (revision 173168)
--- tree-ssa-threadupdate.c (working copy)
*************** remove_ctrl_stmt_and_useless_edges (basi
*** 200,209 ****
--- 200,215 ----
static void
create_block_for_threading (basic_block bb, struct redirection_data *rd)
{
+ edge_iterator ei;
+ edge e;
+
/* We can use the generic block duplication code and simply remove
the stuff we do not need. */
rd->dup_block = duplicate_block (bb, NULL, NULL);
+ FOR_EACH_EDGE (e, ei, rd->dup_block->succs)
+ e->aux = NULL;
+
/* Zero out the profile, since the block is unreachable for now. */
rd->dup_block->frequency = 0;
rd->dup_block->count = 0;
*************** create_edge_and_update_destination_phis
*** 314,320 ****
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
from the duplicate block, then we will need to add a new argument
--- 320,335 ----
rescan_loop_exit (e, true, false);
e->probability = REG_BR_PROB_BASE;
e->count = bb->count;
!
! if (rd->outgoing_edge->aux)
! {
! e->aux = (edge *) xmalloc (sizeof (edge) * 1);
! ((edge *)e->aux)[0] = ((edge *)rd->outgoing_edge->aux)[0];
! }
! else
! {
! e->aux = NULL;
! }
/* If there are any PHI nodes at the destination of the outgoing edge
from the duplicate block, then we will need to add a new argument
*************** redirect_edges (void **slot, void *data)
*** 406,415 ****
next = el->next;
free (el);
- /* Go ahead and clear E->aux. It's not needed anymore and failure
- to clear it will cause all kinds of unpleasant problems later. */
- e->aux = NULL;
-
thread_stats.num_threaded_edges++;
if (rd->dup_block)
--- 421,426 ----
*************** redirect_edges (void **slot, void *data)
*** 429,434 ****
--- 440,453 ----
gcc_assert (e == e2);
flush_pending_stmts (e2);
}
+
+ /* Go ahead and clear E->aux. It's not needed anymore and failure
+ to clear it will cause all kinds of unpleasant problems later. */
+ free (e->aux);
+ e->aux = NULL;
+
+ thread_stats.num_threaded_edges++;
+
}
/* Indicate that we actually threaded one or more jumps. */
*************** thread_block (basic_block bb, bool noloo
*** 512,518 ****
if (loop->header == bb)
{
e = loop_latch_edge (loop);
! e2 = (edge) e->aux;
if (e2 && loop_exit_edge_p (loop, e2))
{
--- 531,541 ----
if (loop->header == bb)
{
e = loop_latch_edge (loop);
!
! if (e->aux)
! e2 = ((edge *) e->aux)[0];
! else
! e2 = NULL;
if (e2 && loop_exit_edge_p (loop, e2))
{
*************** thread_block (basic_block bb, bool noloo
*** 525,543 ****
efficient lookups. */
FOR_EACH_EDGE (e, ei, bb->preds)
{
! e2 = (edge) e->aux;
if (!e2
/* If NOLOOP_ONLY is true, we only allow threading through the
header of a loop to exit edges. */
|| (noloop_only
&& bb == bb->loop_father->header
! && !loop_exit_edge_p (bb->loop_father, e2)))
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. */
--- 548,569 ----
efficient lookups. */
FOR_EACH_EDGE (e, ei, bb->preds)
{
! if (e->aux == NULL)
! continue;
!
! e2 = ((edge *) e->aux)[0];
if (!e2
/* If NOLOOP_ONLY is true, we only allow threading through the
header of a loop to exit edges. */
|| (noloop_only
&& bb == bb->loop_father->header
! && (!loop_exit_edge_p (bb->loop_father, e2))))
continue;
if (e->dest == e2->src)
update_bb_profile_for_threading (e->dest, EDGE_FREQUENCY (e),
! e->count, ((edge *) e->aux)[0]);
/* Insert the outgoing edge into the hash table if it is not
already in the hash table. */
*************** thread_block (basic_block bb, bool noloo
*** 582,588 ****
return local_info.jumps_threaded;
}
! /* Threads edge E through E->dest to the edge E->aux. Returns the copy
of E->dest created during threading, or E->dest if it was not necessary
to copy it (E is its single predecessor). */
--- 608,614 ----
return local_info.jumps_threaded;
}
! /* Threads edge E through E->dest to the edge E->aux[0]. Returns the copy
of E->dest created during threading, or E->dest if it was not necessary
to copy it (E is its single predecessor). */
*************** static basic_block
*** 590,598 ****
thread_single_edge (edge e)
{
basic_block bb = e->dest;
! edge eto = (edge) e->aux;
struct redirection_data rd;
e->aux = NULL;
thread_stats.num_threaded_edges++;
--- 616,625 ----
thread_single_edge (edge e)
{
basic_block bb = e->dest;
! edge eto = ((edge *) e->aux)[0];
struct redirection_data rd;
+ free (e->aux);
e->aux = NULL;
thread_stats.num_threaded_edges++;
*************** thread_through_loop_header (struct loop
*** 794,800 ****
if (latch->aux)
{
! tgt_edge = (edge) latch->aux;
tgt_bb = tgt_edge->dest;
}
else if (!may_peel_loop_headers
--- 821,827 ----
if (latch->aux)
{
! tgt_edge = ((edge *) latch->aux)[0];
tgt_bb = tgt_edge->dest;
}
else if (!may_peel_loop_headers
*************** thread_through_loop_header (struct loop
*** 817,823 ****
goto fail;
}
! tgt_edge = (edge) e->aux;
atgt_bb = tgt_edge->dest;
if (!tgt_bb)
tgt_bb = atgt_bb;
--- 844,850 ----
goto fail;
}
! tgt_edge = ((edge *) e->aux)[0];
atgt_bb = tgt_edge->dest;
if (!tgt_bb)
tgt_bb = atgt_bb;
*************** thread_through_loop_header (struct loop
*** 883,889 ****
/* Now consider the case entry edges are redirected to the new entry
block. Remember one entry edge, so that we can find the new
! preheader (its destination after threading). */
FOR_EACH_EDGE (e, ei, header->preds)
{
if (e->aux)
--- 910,916 ----
/* Now consider the case entry edges are redirected to the new entry
block. Remember one entry edge, so that we can find the new
! preheader (its destination after threading). */
FOR_EACH_EDGE (e, ei, header->preds)
{
if (e->aux)
*************** fail:
*** 915,920 ****
--- 942,948 ----
/* We failed to thread anything. Cancel the requests. */
FOR_EACH_EDGE (e, ei, header->preds)
{
+ free (e->aux);
e->aux = NULL;
}
return false;
*************** mark_threaded_blocks (bitmap threaded_bl
*** 946,954 ****
for (i = 0; i < VEC_length (edge, threaded_edges); i += 2)
{
edge e = VEC_index (edge, threaded_edges, i);
! edge e2 = VEC_index (edge, threaded_edges, i + 1);
! e->aux = e2;
bitmap_set_bit (tmp, e->dest->index);
}
--- 974,983 ----
for (i = 0; i < VEC_length (edge, threaded_edges); i += 2)
{
edge e = VEC_index (edge, threaded_edges, i);
! edge *x = (edge *)xmalloc (sizeof (edge) * 1);
! x[0] = VEC_index (edge, threaded_edges, i + 1);
! e->aux = x;
bitmap_set_bit (tmp, e->dest->index);
}
*************** mark_threaded_blocks (bitmap threaded_bl
*** 963,969 ****
&& !redirection_block_p (bb))
{
FOR_EACH_EDGE (e, ei, bb->preds)
! e->aux = NULL;
}
else
bitmap_set_bit (threaded_blocks, i);
--- 992,1001 ----
&& !redirection_block_p (bb))
{
FOR_EACH_EDGE (e, ei, bb->preds)
! {
! free (e->aux);
! e->aux = NULL;
! }
}
else
bitmap_set_bit (threaded_blocks, i);
*************** thread_through_all_blocks (bool may_peel
*** 1059,1066 ****
void
register_jump_thread (edge e, edge e2)
{
if (threaded_edges == NULL)
! threaded_edges = VEC_alloc (edge, heap, 10);
if (dump_file && (dump_flags & TDF_DETAILS)
&& e->dest != e2->src)
--- 1091,1103 ----
void
register_jump_thread (edge e, edge e2)
{
+ /* This can occur if we're jumping to a constant address or
+ or something similar. Just get out now. */
+ if (e2 == NULL)
+ return;
+
if (threaded_edges == NULL)
! threaded_edges = VEC_alloc (edge, heap, 15);
if (dump_file && (dump_flags & TDF_DETAILS)
&& e->dest != e2->src)
