/* Thread edges through blocks and update the control flow and SSA graphs.
- Copyright (C) 2004-2018 Free Software Foundation, Inc.
+ Copyright (C) 2004-2019 Free Software Foundation, Inc.
This file is part of GCC.
and sharing a template for that block is considerably more difficult. */
basic_block template_block;
+ /* If we append debug stmts to the template block after creating it,
+ this iterator won't be the last one in the block, and further
+ copies of the template block shouldn't get debug stmts after
+ it. */
+ gimple_stmt_iterator template_last_to_copy;
+
/* Blocks duplicated for the thread. */
bitmap duplicate_blocks;
rd->dup_blocks[count] = duplicate_block (bb, NULL, NULL);
FOR_EACH_EDGE (e, ei, rd->dup_blocks[count]->succs)
- e->aux = NULL;
+ {
+ e->aux = NULL;
+
+ /* If we duplicate a block with an outgoing edge marked as
+ EDGE_IGNORE, we must clear EDGE_IGNORE so that it doesn't
+ leak out of the current pass.
+
+ It would be better to simplify switch statements and remove
+ the edges before we get here, but the sequencing is nontrivial. */
+ e->flags &= ~EDGE_IGNORE;
+ }
/* Zero out the profile, since the block is unreachable for now. */
rd->dup_blocks[count]->count = profile_count::uninitialized ();
gphi *src_phi = gsi.phi ();
gphi *dest_phi = gsi2.phi ();
tree val = gimple_phi_arg_def (src_phi, src_idx);
- source_location locus = gimple_phi_arg_location (src_phi, src_idx);
+ location_t locus = gimple_phi_arg_location (src_phi, src_idx);
SET_PHI_ARG_DEF (dest_phi, tgt_idx, val);
gimple_phi_arg_set_location (dest_phi, tgt_idx, locus);
static tree
get_value_locus_in_path (tree def, vec<jump_thread_edge *> *path,
- basic_block bb, int idx, source_location *locus)
+ basic_block bb, int idx, location_t *locus)
{
tree arg;
gphi *def_phi;
{
gphi *phi = gsi.phi ();
tree def = gimple_phi_arg_def (phi, src_indx);
- source_location locus = gimple_phi_arg_location (phi, src_indx);
+ location_t locus = gimple_phi_arg_location (phi, src_indx);
if (TREE_CODE (def) == SSA_NAME
&& !virtual_operand_p (gimple_phi_result (phi)))
create_block_for_threading ((*path)[1]->e->src, rd, 0,
&local_info->duplicate_blocks);
local_info->template_block = rd->dup_blocks[0];
+ local_info->template_last_to_copy
+ = gsi_last_bb (local_info->template_block);
/* We do not create any outgoing edges for the template. We will
take care of that in a later traversal. That way we do not
}
else
{
+ gimple_seq seq = NULL;
+ if (gsi_stmt (local_info->template_last_to_copy)
+ != gsi_stmt (gsi_last_bb (local_info->template_block)))
+ {
+ if (gsi_end_p (local_info->template_last_to_copy))
+ {
+ seq = bb_seq (local_info->template_block);
+ set_bb_seq (local_info->template_block, NULL);
+ }
+ else
+ seq = gsi_split_seq_after (local_info->template_last_to_copy);
+ }
create_block_for_threading (local_info->template_block, rd, 0,
&local_info->duplicate_blocks);
+ if (seq)
+ {
+ if (gsi_end_p (local_info->template_last_to_copy))
+ set_bb_seq (local_info->template_block, seq);
+ else
+ gsi_insert_seq_after (&local_info->template_last_to_copy,
+ seq, GSI_SAME_STMT);
+ }
/* Go ahead and wire up outgoing edges and update PHIs for the duplicate
block. */
ssa_fix_duplicate_block_edges (rd, local_info);
}
+ if (MAY_HAVE_DEBUG_STMTS)
+ {
+ /* Copy debug stmts from each NO_COPY src block to the block
+ that would have been its predecessor, if we can append to it
+ (we can't add stmts after a block-ending stmt), or prepending
+ to the duplicate of the successor, if there is one. If
+ there's no duplicate successor, we'll mostly drop the blocks
+ on the floor; propagate_threaded_block_debug_into, called
+ elsewhere, will consolidate and preserve the effects of the
+ binds, but none of the markers. */
+ gimple_stmt_iterator copy_to = gsi_last_bb (rd->dup_blocks[0]);
+ if (!gsi_end_p (copy_to))
+ {
+ if (stmt_ends_bb_p (gsi_stmt (copy_to)))
+ {
+ if (rd->dup_blocks[1])
+ copy_to = gsi_after_labels (rd->dup_blocks[1]);
+ else
+ copy_to = gsi_none ();
+ }
+ else
+ gsi_next (©_to);
+ }
+ for (unsigned int i = 2, j = 0; i < path->length (); i++)
+ if ((*path)[i]->type == EDGE_NO_COPY_SRC_BLOCK
+ && gsi_bb (copy_to))
+ {
+ for (gimple_stmt_iterator gsi = gsi_start_bb ((*path)[i]->e->src);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ if (!is_gimple_debug (gsi_stmt (gsi)))
+ continue;
+ gimple *stmt = gsi_stmt (gsi);
+ gimple *copy = gimple_copy (stmt);
+ gsi_insert_before (©_to, copy, GSI_SAME_STMT);
+ }
+ }
+ else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK
+ || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
+ {
+ j++;
+ gcc_assert (j < 2);
+ copy_to = gsi_last_bb (rd->dup_blocks[j]);
+ if (!gsi_end_p (copy_to))
+ {
+ if (stmt_ends_bb_p (gsi_stmt (copy_to)))
+ copy_to = gsi_none ();
+ else
+ gsi_next (©_to);
+ }
+ }
+ }
+
/* Keep walking the hash table. */
return 1;
}
{
vec<jump_thread_edge *> *path = paths[i];
- if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
+ if (path->length () > 1
+ && (*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
{
edge e = (*path)[0]->e;
e->aux = (void *)path;
{
vec<jump_thread_edge *> *path = paths[i];
- if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
+ if (path->length () > 1
+ && (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
{
/* Attach the path to the starting edge if none is yet recorded. */
if ((*path)[0]->e->aux == NULL)
vec<jump_thread_edge *> *path = paths[i];
edge e = (*path)[0]->e;
- if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && e->aux == path)
+ if (path->length () > 1
+ && (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && e->aux == path)
{
unsigned int j;
for (j = 1; j < path->length (); j++)
return false;
}
+DEBUG_FUNCTION void
+debug_path (FILE *dump_file, int pathno)
+{
+ vec<jump_thread_edge *> *p = paths[pathno];
+ fprintf (dump_file, "path: ");
+ for (unsigned i = 0; i < p->length (); ++i)
+ fprintf (dump_file, "%d -> %d, ",
+ (*p)[i]->e->src->index, (*p)[i]->e->dest->index);
+ fprintf (dump_file, "\n");
+}
+
+DEBUG_FUNCTION void
+debug_all_paths ()
+{
+ for (unsigned i = 0; i < paths.length (); ++i)
+ debug_path (stderr, i);
+}
+
+/* Rewire a jump_thread_edge so that the source block is now a
+ threaded source block.
+
+ PATH_NUM is an index into the global path table PATHS.
+ EDGE_NUM is the jump thread edge number into said path.
+
+ Returns TRUE if we were able to successfully rewire the edge. */
+
+static bool
+rewire_first_differing_edge (unsigned path_num, unsigned edge_num)
+{
+ vec<jump_thread_edge *> *path = paths[path_num];
+ edge &e = (*path)[edge_num]->e;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "rewiring edge candidate: %d -> %d\n",
+ e->src->index, e->dest->index);
+ basic_block src_copy = get_bb_copy (e->src);
+ if (src_copy == NULL)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "ignoring candidate: there is no src COPY\n");
+ return false;
+ }
+ edge new_edge = find_edge (src_copy, e->dest);
+ /* If the previously threaded paths created a flow graph where we
+ can no longer figure out where to go, give up. */
+ if (new_edge == NULL)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "ignoring candidate: we lost our way\n");
+ return false;
+ }
+ e = new_edge;
+ return true;
+}
+
+/* After an FSM path has been jump threaded, adjust the remaining FSM
+ paths that are subsets of this path, so these paths can be safely
+ threaded within the context of the new threaded path.
+
+ For example, suppose we have just threaded:
+
+ 5 -> 6 -> 7 -> 8 -> 12 => 5 -> 6' -> 7' -> 8' -> 12'
+
+ And we have an upcoming threading candidate:
+ 5 -> 6 -> 7 -> 8 -> 15 -> 20
+
+ This function adjusts the upcoming path into:
+ 8' -> 15 -> 20
+
+ CURR_PATH_NUM is an index into the global paths table. It
+ specifies the path that was just threaded. */
+
+static void
+adjust_paths_after_duplication (unsigned curr_path_num)
+{
+ vec<jump_thread_edge *> *curr_path = paths[curr_path_num];
+ gcc_assert ((*curr_path)[0]->type == EDGE_FSM_THREAD);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "just threaded: ");
+ debug_path (dump_file, curr_path_num);
+ }
+
+ /* Iterate through all the other paths and adjust them. */
+ for (unsigned cand_path_num = 0; cand_path_num < paths.length (); )
+ {
+ if (cand_path_num == curr_path_num)
+ {
+ ++cand_path_num;
+ continue;
+ }
+ /* Make sure the candidate to adjust starts with the same path
+ as the recently threaded path and is an FSM thread. */
+ vec<jump_thread_edge *> *cand_path = paths[cand_path_num];
+ if ((*cand_path)[0]->type != EDGE_FSM_THREAD
+ || (*cand_path)[0]->e != (*curr_path)[0]->e)
+ {
+ ++cand_path_num;
+ continue;
+ }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "adjusting candidate: ");
+ debug_path (dump_file, cand_path_num);
+ }
+
+ /* Chop off from the candidate path any prefix it shares with
+ the recently threaded path. */
+ unsigned minlength = MIN (curr_path->length (), cand_path->length ());
+ unsigned j;
+ for (j = 0; j < minlength; ++j)
+ {
+ edge cand_edge = (*cand_path)[j]->e;
+ edge curr_edge = (*curr_path)[j]->e;
+
+ /* Once the prefix no longer matches, adjust the first
+ non-matching edge to point from an adjusted edge to
+ wherever it was going. */
+ if (cand_edge != curr_edge)
+ {
+ gcc_assert (cand_edge->src == curr_edge->src);
+ if (!rewire_first_differing_edge (cand_path_num, j))
+ goto remove_candidate_from_list;
+ break;
+ }
+ }
+ if (j == minlength)
+ {
+ /* If we consumed the max subgraph we could look at, and
+ still didn't find any different edges, it's the
+ last edge after MINLENGTH. */
+ if (cand_path->length () > minlength)
+ {
+ if (!rewire_first_differing_edge (cand_path_num, j))
+ goto remove_candidate_from_list;
+ }
+ else if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "adjusting first edge after MINLENGTH.\n");
+ }
+ if (j > 0)
+ {
+ /* If we are removing everything, delete the entire candidate. */
+ if (j == cand_path->length ())
+ {
+ remove_candidate_from_list:
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "adjusted candidate: [EMPTY]\n");
+ delete_jump_thread_path (cand_path);
+ paths.unordered_remove (cand_path_num);
+ continue;
+ }
+ /* Otherwise, just remove the redundant sub-path. */
+ cand_path->block_remove (0, j);
+ }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "adjusted candidate: ");
+ debug_path (dump_file, cand_path_num);
+ }
+ ++cand_path_num;
+ }
+}
+
/* Duplicates a jump-thread path of N_REGION basic blocks.
The ENTRY edge is redirected to the duplicate of the region.
and create a single fallthru edge pointing to the same destination as the
EXIT edge.
+ CURRENT_PATH_NO is an index into the global paths[] table
+ specifying the jump-thread path.
+
Returns false if it is unable to copy the region, true otherwise. */
static bool
duplicate_thread_path (edge entry, edge exit, basic_block *region,
- unsigned n_region)
+ unsigned n_region, unsigned current_path_no)
{
unsigned i;
struct loop *loop = entry->dest->loop_father;
if (!can_copy_bbs_p (region, n_region))
return false;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\nabout to thread: ");
+ debug_path (dump_file, current_path_no);
+ }
+
/* Some sanity checking. Note that we do not check for all possible
missuses of the functions. I.e. if you ask to copy something weird,
it will work, but the state of structures probably will not be
free (region_copy);
+ adjust_paths_after_duplication (current_path_no);
+
free_original_copy_tables ();
return true;
}
unsigned int i;
struct loop *loop;
auto_bitmap threaded_blocks;
+ hash_set<edge> visited_starting_edges;
if (!paths.exists ())
{
continue;
}
- /* Do not jump-thread twice from the same block. */
- if (bitmap_bit_p (threaded_blocks, entry->src->index)
- /* We may not want to realize this jump thread path
- for various reasons. So check it first. */
+ /* Do not jump-thread twice from the same starting edge.
+
+ Previously we only checked that we weren't threading twice
+ from the same BB, but that was too restrictive. Imagine a
+ path that starts from GIMPLE_COND(x_123 == 0,...), where both
+ edges out of this conditional yield paths that can be
+ threaded (for example, both lead to an x_123==0 or x_123!=0
+ conditional further down the line. */
+ if (visited_starting_edges.contains (entry)
+ /* We may not want to realize this jump thread path for
+ various reasons. So check it first. */
|| !valid_jump_thread_path (path))
{
/* Remove invalid FSM jump-thread paths. */
for (unsigned int j = 0; j < len - 1; j++)
region[j] = (*path)[j]->e->dest;
- if (duplicate_thread_path (entry, exit, region, len - 1))
+ if (duplicate_thread_path (entry, exit, region, len - 1, i))
{
/* We do not update dominance info. */
free_dominance_info (CDI_DOMINATORS);
- bitmap_set_bit (threaded_blocks, entry->src->index);
+ visited_starting_edges.add (entry);
retval = true;
thread_stats.num_threaded_edges++;
}
edge entry = (*path)[0]->e;
/* Do not jump-thread twice from the same block. */
- if (bitmap_bit_p (threaded_blocks, entry->src->index))
+ if (visited_starting_edges.contains (entry))
{
delete_jump_thread_path (path);
paths.unordered_remove (i);
i++;
}
- bitmap_clear (threaded_blocks);
-
mark_threaded_blocks (threaded_blocks);
initialize_original_copy_tables ();
Consider if we have two jump threading paths A and B. If the
target edge of A is the starting edge of B and we thread path A
first, then we create an additional incoming edge into B->dest that
- we can not discover as a jump threading path on this iteration.
+ we cannot discover as a jump threading path on this iteration.
If we instead thread B first, then the edge into B->dest will have
already been redirected before we process path A and path A will
projects / thirdparty / gcc.git / blobdiff