/* Thread edges through blocks and update the control flow and SSA graphs.
- Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010 Free Software Foundation,
- Inc.
+ Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010, 201
+ Free Software Foundation, Inc.
This file is part of GCC.
its single successor. */
edge outgoing_edge;
+ edge intermediate_edge;
+
/* A list of incoming edges which we want to thread to
OUTGOING_EDGE->dest. */
struct el *incoming_edges;
threading is attached to the AUX field for the incoming edge. Use these
macros to access the underlying structure attached to the AUX field. */
#define THREAD_TARGET(E) ((edge *)(E)->aux)[0]
+#define THREAD_TARGET2(E) ((edge *)(E)->aux)[1]
/* Jump threading statistics. */
}
}
-/* Create a duplicate of BB which only reaches the destination of the edge
- stored in RD. Record the duplicate block in RD. */
+/* Create a duplicate of BB. Record the duplicate block in RD. */
static void
create_block_for_threading (basic_block bb, struct redirection_data *rd)
/* Zero out the profile, since the block is unreachable for now. */
rd->dup_block->frequency = 0;
rd->dup_block->count = 0;
-
- /* The call to duplicate_block will copy everything, including the
- useless COND_EXPR or SWITCH_EXPR at the end of BB. We just remove
- the useless COND_EXPR or SWITCH_EXPR here rather than having a
- specialized block copier. We also remove all outgoing edges
- from the duplicate block. The appropriate edge will be created
- later. */
- remove_ctrl_stmt_and_useless_edges (rd->dup_block, NULL);
}
/* Hashing and equality routines for our hash table. */
{
edge e1 = ((const struct redirection_data *)p1)->outgoing_edge;
edge e2 = ((const struct redirection_data *)p2)->outgoing_edge;
+ edge e3 = ((const struct redirection_data *)p1)->intermediate_edge;
+ edge e4 = ((const struct redirection_data *)p2)->intermediate_edge;
- return e1 == e2;
+ return e1 == e2 && e3 == e4;
}
/* Given an outgoing edge E lookup and return its entry in our hash table.
edges associated with E in the hash table. */
static struct redirection_data *
-lookup_redirection_data (edge e, edge incoming_edge, enum insert_option insert)
+lookup_redirection_data (edge e, enum insert_option insert)
{
void **slot;
struct redirection_data *elt;
/* Build a hash table element so we can see if E is already
in the table. */
elt = XNEW (struct redirection_data);
- elt->outgoing_edge = e;
+ elt->intermediate_edge = THREAD_TARGET2 (e) ? THREAD_TARGET (e) : NULL;
+ elt->outgoing_edge = THREAD_TARGET2 (e) ? THREAD_TARGET2 (e)
+ : THREAD_TARGET (e);
elt->dup_block = NULL;
elt->incoming_edges = NULL;
{
*slot = (void *)elt;
elt->incoming_edges = XNEW (struct el);
- elt->incoming_edges->e = incoming_edge;
+ elt->incoming_edges->e = e;
elt->incoming_edges->next = NULL;
return elt;
}
{
struct el *el = XNEW (struct el);
el->next = elt->incoming_edges;
- el->e = incoming_edge;
+ el->e = e;
elt->incoming_edges = el;
}
}
}
+/* For each PHI in BB, copy the argument associated with SRC_E to TGT_E. */
+
+static void
+copy_phi_args (basic_block bb, edge src_e, edge tgt_e)
+{
+ gimple_stmt_iterator gsi;
+ int src_indx = src_e->dest_idx;
+
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple phi = gsi_stmt (gsi);
+ source_location locus = gimple_phi_arg_location (phi, src_indx);
+ add_phi_arg (phi, gimple_phi_arg_def (phi, src_indx), tgt_e, locus);
+ }
+}
+
+/* We have recently made a copy of ORIG_BB, including its outgoing
+ edges. The copy is NEW_BB. Every PHI node in every direct successor of
+ ORIG_BB has a new argument associated with edge from NEW_BB to the
+ successor. Initialize the PHI argument so that it is equal to the PHI
+ argument associated with the edge from ORIG_BB to the successor. */
+
+static void
+update_destination_phis (basic_block orig_bb, basic_block new_bb)
+{
+ edge_iterator ei;
+ edge e;
+
+ FOR_EACH_EDGE (e, ei, orig_bb->succs)
+ {
+ edge e2 = find_edge (new_bb, e->dest);
+ copy_phi_args (e->dest, e, e2);
+ }
+}
+
/* Given a duplicate block and its single destination (both stored
in RD). Create an edge between the duplicate and its single
destination.
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;
if (rd->outgoing_edge->aux)
{
- e->aux = (edge *) XNEWVEC (edge, 1);
+ e->aux = (edge *) XNEWVEC (edge, 2);
THREAD_TARGET(e) = THREAD_TARGET (rd->outgoing_edge);
+ THREAD_TARGET2(e) = THREAD_TARGET2 (rd->outgoing_edge);
}
else
{
from the duplicate block, then we will need to add a new argument
to them. The argument should have the same value as the argument
associated with the outgoing edge stored in RD. */
- for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple phi = gsi_stmt (gsi);
- source_location locus;
- int indx = rd->outgoing_edge->dest_idx;
+ copy_phi_args (e->dest, rd->outgoing_edge, e);
+}
- locus = gimple_phi_arg_location (phi, indx);
- add_phi_arg (phi, gimple_phi_arg_def (phi, indx), e, locus);
+/* Wire up the outgoing edges from the duplicate block and
+ update any PHIs as needed. */
+static void
+fix_duplicate_block_edges (struct redirection_data *rd,
+ struct local_info *local_info)
+{
+ /* If we were threading through an joiner block, then we want
+ to keep its control statement and redirect an outgoing edge.
+ Else we want to remove the control statement & edges, then create
+ a new outgoing edge. In both cases we may need to update PHIs. */
+ if (THREAD_TARGET2 (rd->incoming_edges->e))
+ {
+ edge victim;
+ edge e2;
+ edge e = rd->incoming_edges->e;
+
+ /* This updates the PHIs at the destination of the duplicate
+ block. */
+ update_destination_phis (local_info->bb, rd->dup_block);
+
+ /* Find the edge from the duplicate block to the block we're
+ threading through. That's the edge we want to redirect. */
+ victim = find_edge (rd->dup_block, THREAD_TARGET (e)->dest);
+ e2 = redirect_edge_and_branch (victim, THREAD_TARGET2 (e)->dest);
+
+ /* If we redirected the edge, then we need to copy PHI arguments
+ at the target. If the edge already existed (e2 != victim case),
+ then the PHIs in the target already have the correct arguments. */
+ if (e2 == victim)
+ copy_phi_args (e2->dest, THREAD_TARGET2 (e), e2);
+ }
+ else
+ {
+ remove_ctrl_stmt_and_useless_edges (rd->dup_block, NULL);
+ create_edge_and_update_destination_phis (rd, rd->dup_block);
}
}
-
/* Hash table traversal callback routine to create duplicate blocks. */
static int
create_block_for_threading (local_info->template_block, rd);
/* Go ahead and wire up outgoing edges and update PHIs for the duplicate
- block. */
- create_edge_and_update_destination_phis (rd, rd->dup_block);
+ block. */
+ fix_duplicate_block_edges (rd, local_info);
}
/* Keep walking the hash table. */
struct redirection_data *rd = (struct redirection_data *) *slot;
struct local_info *local_info = (struct local_info *)data;
- /* If this is the template block, then create its outgoing edges
- and halt the hash table traversal. */
+ /* If this is the template block halt the traversal after updating
+ it appropriately.
+
+ If we were threading through an joiner block, then we want
+ to keep its control statement and redirect an outgoing edge.
+ Else we want to remove the control statement & edges, then create
+ a new outgoing edge. In both cases we may need to update PHIs. */
if (rd->dup_block && rd->dup_block == local_info->template_block)
{
- create_edge_and_update_destination_phis (rd, rd->dup_block);
+ fix_duplicate_block_edges (rd, local_info);
return 0;
}
free (el);
thread_stats.num_threaded_edges++;
+ /* If we are threading through a joiner block, then we have to
+ find the edge we want to redirect and update some PHI nodes. */
+ if (THREAD_TARGET2 (e))
+ {
+ edge e2;
- if (rd->dup_block)
+ /* We want to redirect the incoming edge to the joiner block (E)
+ to instead reach the duplicate of the joiner block. */
+ e2 = redirect_edge_and_branch (e, rd->dup_block);
+ flush_pending_stmts (e2);
+ }
+ else if (rd->dup_block)
{
edge e2;
if (e->aux == NULL)
continue;
- e2 = THREAD_TARGET (e);
+ if (THREAD_TARGET2 (e))
+ e2 = THREAD_TARGET2 (e);
+ else
+ e2 = THREAD_TARGET (e);
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))))
+ && (!loop_exit_edge_p (bb->loop_father, e2)
+ || THREAD_TARGET2 (e))))
continue;
if (e->dest == e2->src)
/* Insert the outgoing edge into the hash table if it is not
already in the hash table. */
- lookup_redirection_data (e2, e, INSERT);
+ lookup_redirection_data (e, INSERT);
}
/* We do not update dominance info. */
rd.outgoing_edge = eto;
create_block_for_threading (bb, &rd);
+ remove_ctrl_stmt_and_useless_edges (rd.dup_block, NULL);
create_edge_and_update_destination_phis (&rd, rd.dup_block);
if (dump_file && (dump_flags & TDF_DETAILS))
if (latch->aux)
{
+ if (THREAD_TARGET2 (latch))
+ goto fail;
tgt_edge = THREAD_TARGET (latch);
tgt_bb = tgt_edge->dest;
}
goto fail;
}
+ if (THREAD_TARGET2 (e))
+ goto fail;
tgt_edge = THREAD_TARGET (e);
atgt_bb = tgt_edge->dest;
if (!tgt_bb)
edge e;
edge_iterator ei;
- for (i = 0; i < VEC_length (edge, threaded_edges); i += 2)
+ for (i = 0; i < VEC_length (edge, threaded_edges); i += 3)
{
edge e = VEC_index (edge, threaded_edges, i);
- edge *x = (edge *) XNEWVEC (edge, 1);
+ edge *x = (edge *) XNEWVEC (edge, 2);
- x[0] = VEC_index (edge, threaded_edges, i + 1);
e->aux = x;
+ THREAD_TARGET (e) = VEC_index (edge, threaded_edges, i + 1);
+ THREAD_TARGET2 (e) = VEC_index (edge, threaded_edges, i + 2);
bitmap_set_bit (tmp, e->dest->index);
}
after fixing the SSA graph. */
void
-register_jump_thread (edge e, edge e2)
+register_jump_thread (edge e, edge e2, edge e3)
{
/* This can occur if we're jumping to a constant address or
or something similar. Just get out now. */
VEC_safe_push (edge, heap, threaded_edges, e);
VEC_safe_push (edge, heap, threaded_edges, e2);
+ VEC_safe_push (edge, heap, threaded_edges, e3);
}
OSDN Git Service
