/* Thread edges through blocks and update the control flow and SSA graphs.
- Copyright (C) 2004-2015 Free Software Foundation, Inc.
+ Copyright (C) 2004-2016 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "alias.h"
#include "backend.h"
-#include "cfghooks.h"
#include "tree.h"
#include "gimple.h"
-#include "hard-reg-set.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
#include "ssa.h"
-#include "options.h"
#include "fold-const.h"
-#include "flags.h"
#include "cfganal.h"
-#include "internal-fn.h"
#include "gimple-iterator.h"
#include "tree-ssa.h"
#include "tree-ssa-threadupdate.h"
-#include "dumpfile.h"
#include "cfgloop.h"
#include "dbgcnt.h"
#include "tree-cfg.h"
-#include "tree-pass.h"
/* Given a block B, update the CFG and SSA graph to reflect redirecting
one or more in-edges to B to instead reach the destination of an
return true;
}
+/* Rather than search all the edges in jump thread paths each time
+ DOM is able to simply if control statement, we build a hash table
+ with the deleted edges. We only care about the address of the edge,
+ not its contents. */
+struct removed_edges : nofree_ptr_hash<edge_def>
+{
+ static hashval_t hash (edge e) { return htab_hash_pointer (e); }
+ static bool equal (edge e1, edge e2) { return e1 == e2; }
+};
+
+static hash_table<removed_edges> *removed_edges;
+
/* Data structure of information to pass to hash table traversal routines. */
struct ssa_local_info_t
{
Also remove all outgoing edges except the edge which reaches DEST_BB.
If DEST_BB is NULL, then remove all outgoing edges. */
-static void
+void
remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb)
{
gimple_stmt_iterator gsi;
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
if (e->dest != dest_bb)
- remove_edge (e);
+ {
+ free_dom_edge_info (e);
+ remove_edge (e);
+ }
else
ei_next (&ei);
}
+
+ /* If the remaining edge is a loop exit, there must have
+ a removed edge that was not a loop exit.
+
+ In that case BB and possibly other blocks were previously
+ in the loop, but are now outside the loop. Thus, we need
+ to update the loop structures. */
+ if (single_succ_p (bb)
+ && loop_outer (bb->loop_father)
+ && loop_exit_edge_p (bb->loop_father, single_succ_edge (bb)))
+ loops_state_set (LOOPS_NEED_FIXUP);
}
/* Create a duplicate of BB. Record the duplicate block in an array
fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
e->src->index, e->dest->index, rd->dup_blocks[0]->index);
- /* If we redirect a loop latch edge cancel its loop. */
- if (e->src == e->src->loop_father->latch)
- mark_loop_for_removal (e->src->loop_father);
-
/* Redirect the incoming edge (possibly to the joiner block) to the
appropriate duplicate block. */
e2 = redirect_edge_and_branch (e, rd->dup_blocks[0]);
return retval;
}
-
-/* Threads edge E through E->dest to the edge THREAD_TARGET (E). 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
-thread_single_edge (edge e)
-{
- basic_block bb = e->dest;
- struct redirection_data rd;
- vec<jump_thread_edge *> *path = THREAD_PATH (e);
- edge eto = (*path)[1]->e;
-
- delete_jump_thread_path (path);
- e->aux = NULL;
-
- thread_stats.num_threaded_edges++;
-
- if (single_pred_p (bb))
- {
- /* If BB has just a single predecessor, we should only remove the
- control statements at its end, and successors except for ETO. */
- remove_ctrl_stmt_and_useless_edges (bb, eto->dest);
-
- /* And fixup the flags on the single remaining edge. */
- eto->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL);
- eto->flags |= EDGE_FALLTHRU;
-
- return bb;
- }
-
- /* Otherwise, we need to create a copy. */
- if (e->dest == eto->src)
- update_bb_profile_for_threading (bb, EDGE_FREQUENCY (e), e->count, eto);
-
- vec<jump_thread_edge *> *npath = new vec<jump_thread_edge *> ();
- jump_thread_edge *x = new jump_thread_edge (e, EDGE_START_JUMP_THREAD);
- npath->safe_push (x);
-
- x = new jump_thread_edge (eto, EDGE_COPY_SRC_BLOCK);
- npath->safe_push (x);
- rd.path = npath;
-
- create_block_for_threading (bb, &rd, 0, NULL);
- remove_ctrl_stmt_and_useless_edges (rd.dup_blocks[0], NULL);
- create_edge_and_update_destination_phis (&rd, rd.dup_blocks[0], 0);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " Threaded jump %d --> %d to %d\n",
- e->src->index, e->dest->index, rd.dup_blocks[0]->index);
-
- rd.dup_blocks[0]->count = e->count;
- rd.dup_blocks[0]->frequency = EDGE_FREQUENCY (e);
- single_succ_edge (rd.dup_blocks[0])->count = e->count;
- redirect_edge_and_branch (e, rd.dup_blocks[0]);
- flush_pending_stmts (e);
-
- delete_jump_thread_path (npath);
- return rd.dup_blocks[0];
-}
-
/* Callback for dfs_enumerate_from. Returns true if BB is different
from STOP and DBDS_CE_STOP. */
return (bb_reachable ? DOMST_DOMINATING : DOMST_LOOP_BROKEN);
}
-/* Return true if BB is part of the new pre-header that is created
- when threading the latch to DATA. */
-
-static bool
-def_split_header_continue_p (const_basic_block bb, const void *data)
-{
- const_basic_block new_header = (const_basic_block) data;
- const struct loop *l;
-
- if (bb == new_header
- || loop_depth (bb->loop_father) < loop_depth (new_header->loop_father))
- return false;
- for (l = bb->loop_father; l; l = loop_outer (l))
- if (l == new_header->loop_father)
- return true;
- return false;
-}
-
/* Thread jumps through the header of LOOP. Returns true if cfg changes.
If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges
to the inside of the loop. */
if (single_succ_p (header))
goto fail;
- /* If we threaded the latch using a joiner block, we cancel the
- threading opportunity out of an abundance of caution. However,
- still allow threading from outside to inside the loop. */
- if (latch->aux)
- {
- vec<jump_thread_edge *> *path = THREAD_PATH (latch);
- if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
- {
- delete_jump_thread_path (path);
- latch->aux = NULL;
- }
- }
-
- if (latch->aux)
- {
- vec<jump_thread_edge *> *path = THREAD_PATH (latch);
- tgt_edge = (*path)[1]->e;
- tgt_bb = tgt_edge->dest;
- }
- else if (!may_peel_loop_headers
- && !redirection_block_p (loop->header))
+ if (!may_peel_loop_headers && !redirection_block_p (loop->header))
goto fail;
else
{
tgt_bb = split_edge (tgt_edge);
}
- if (latch->aux)
- {
- basic_block *bblocks;
- unsigned nblocks, i;
-
- /* First handle the case latch edge is redirected. We are copying
- the loop header but not creating a multiple entry loop. Make the
- cfg manipulation code aware of that fact. */
- set_loop_copy (loop, loop);
- loop->latch = thread_single_edge (latch);
- set_loop_copy (loop, NULL);
- gcc_assert (single_succ (loop->latch) == tgt_bb);
- loop->header = tgt_bb;
-
- /* Remove the new pre-header blocks from our loop. */
- bblocks = XCNEWVEC (basic_block, loop->num_nodes);
- nblocks = dfs_enumerate_from (header, 0, def_split_header_continue_p,
- bblocks, loop->num_nodes, tgt_bb);
- for (i = 0; i < nblocks; i++)
- if (bblocks[i]->loop_father == loop)
- {
- remove_bb_from_loops (bblocks[i]);
- add_bb_to_loop (bblocks[i], loop_outer (loop));
- }
- free (bblocks);
-
- /* If the new header has multiple latches mark it so. */
- FOR_EACH_EDGE (e, ei, loop->header->preds)
- if (e->src->loop_father == loop
- && e->src != loop->latch)
- {
- loop->latch = NULL;
- loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
- }
-
- /* Cancel remaining threading requests that would make the
- loop a multiple entry loop. */
- FOR_EACH_EDGE (e, ei, header->preds)
- {
- edge e2;
-
- if (e->aux == NULL)
- continue;
-
- vec<jump_thread_edge *> *path = THREAD_PATH (e);
- e2 = path->last ()->e;
-
- if (e->src->loop_father != e2->dest->loop_father
- && e2->dest != loop->header)
- {
- delete_jump_thread_path (path);
- e->aux = NULL;
- }
- }
+ basic_block new_preheader;
- /* Thread the remaining edges through the former header. */
- thread_block (header, false);
- }
- else
+ /* 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)
{
- basic_block new_preheader;
-
- /* 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)
- break;
- }
-
- /* The duplicate of the header is the new preheader of the loop. Ensure
- that it is placed correctly in the loop hierarchy. */
- set_loop_copy (loop, loop_outer (loop));
-
- thread_block (header, false);
- set_loop_copy (loop, NULL);
- new_preheader = e->dest;
-
- /* Create the new latch block. This is always necessary, as the latch
- must have only a single successor, but the original header had at
- least two successors. */
- loop->latch = NULL;
- mfb_kj_edge = single_succ_edge (new_preheader);
- loop->header = mfb_kj_edge->dest;
- latch = make_forwarder_block (tgt_bb, mfb_keep_just, NULL);
- loop->header = latch->dest;
- loop->latch = latch->src;
+ if (e->aux)
+ break;
}
+ /* The duplicate of the header is the new preheader of the loop. Ensure
+ that it is placed correctly in the loop hierarchy. */
+ set_loop_copy (loop, loop_outer (loop));
+
+ thread_block (header, false);
+ set_loop_copy (loop, NULL);
+ new_preheader = e->dest;
+
+ /* Create the new latch block. This is always necessary, as the latch
+ must have only a single successor, but the original header had at
+ least two successors. */
+ loop->latch = NULL;
+ mfb_kj_edge = single_succ_edge (new_preheader);
+ loop->header = mfb_kj_edge->dest;
+ latch = make_forwarder_block (tgt_bb, mfb_keep_just, NULL);
+ loop->header = latch->dest;
+ loop->latch = latch->src;
return true;
fail:
}
-/* Return TRUE if BB ends with a switch statement or a computed goto.
- Otherwise return false. */
-static bool
-bb_ends_with_multiway_branch (basic_block bb ATTRIBUTE_UNUSED)
-{
- gimple *stmt = last_stmt (bb);
- if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
- return true;
- if (stmt && gimple_code (stmt) == GIMPLE_GOTO
- && TREE_CODE (gimple_goto_dest (stmt)) == SSA_NAME)
- return true;
- return false;
-}
-
/* Verify that the REGION is a valid jump thread. A jump thread is a special
case of SEME Single Entry Multiple Exits region in which all nodes in the
REGION have exactly one incoming edge. The only exception is the first block
scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
}
-#ifdef ENABLE_CHECKING
- verify_jump_thread (region_copy, n_region);
-#endif
+ if (flag_checking)
+ verify_jump_thread (region_copy, n_region);
/* Remove the last branch in the jump thread path. */
remove_ctrl_stmt_and_useless_edges (region_copy[n_region - 1], exit->dest);
valid_jump_thread_path (vec<jump_thread_edge *> *path)
{
unsigned len = path->length ();
+ bool threaded_multiway_branch = false;
+ bool multiway_branch_in_path = false;
+ bool threaded_through_latch = false;
- /* Check that the path is connected. */
+ /* Check that the path is connected and see if there's a multi-way
+ branch on the path and whether or not a multi-way branch
+ is threaded. */
for (unsigned int j = 0; j < len - 1; j++)
- if ((*path)[j]->e->dest != (*path)[j+1]->e->src)
+ {
+ edge e = (*path)[j]->e;
+ struct loop *loop = e->dest->loop_father;
+
+ if (e->dest != (*path)[j+1]->e->src)
+ return false;
+
+ /* If we're threading through the loop latch back into the
+ same loop and the destination does not dominate the loop
+ latch, then this thread would create an irreducible loop. */
+ if (loop->latch
+ && loop_latch_edge (loop) == e
+ && loop == path->last()->e->dest->loop_father
+ && (determine_bb_domination_status (loop, path->last ()->e->dest)
+ == DOMST_NONDOMINATING))
+ threaded_through_latch = true;
+
+ gimple *last = last_stmt (e->dest);
+ if (j == len - 2)
+ threaded_multiway_branch
+ |= (last && gimple_code (last) == GIMPLE_SWITCH);
+ else
+ multiway_branch_in_path
+ |= (last && gimple_code (last) == GIMPLE_SWITCH);
+ }
+
+ /* If we are trying to thread through the loop latch to a block in the
+ loop that does not dominate the loop latch, then that will create an
+ irreducible loop. We avoid that unless the jump thread has a multi-way
+ branch, in which case we have deemed it worth losing other
+ loop optimizations later if we can eliminate the multi-way branch. */
+ if (!threaded_multiway_branch && threaded_through_latch)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file,
+ "Thread through latch without threading a multiway "
+ "branch.\n");
+ dump_jump_thread_path (dump_file, *path, false);
+ }
return false;
+ }
+
+ /* When there is a multi-way branch on the path, then threading can
+ explode the CFG due to duplicating the edges for that multi-way
+ branch. So like above, only allow a multi-way branch on the path
+ if we actually thread a multi-way branch. */
+ if (!threaded_multiway_branch && multiway_branch_in_path)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file,
+ "Thread through multiway branch without threading "
+ "a multiway branch.\n");
+ dump_jump_thread_path (dump_file, *path, false);
+ }
+ return false;
+ }
return true;
}
+/* Remove any queued jump threads that include edge E.
+
+ We don't actually remove them here, just record the edges into ax
+ hash table. That way we can do the search once per iteration of
+ DOM/VRP rather than for every case where DOM optimizes away a COND_EXPR. */
+
+void
+remove_jump_threads_including (edge_def *e)
+{
+ if (!paths.exists ())
+ return;
+
+ if (!removed_edges)
+ removed_edges = new hash_table<struct removed_edges> (17);
+
+ edge *slot = removed_edges->find_slot (e, INSERT);
+ *slot = e;
+}
+
/* Walk through all blocks and thread incoming edges to the appropriate
outgoing edge for each edge pair recorded in THREADED_EDGES.
struct loop *loop;
if (!paths.exists ())
- return false;
+ {
+ retval = false;
+ goto out;
+ }
threaded_blocks = BITMAP_ALLOC (NULL);
memset (&thread_stats, 0, sizeof (thread_stats));
+ /* Remove any paths that referenced removed edges. */
+ if (removed_edges)
+ for (i = 0; i < paths.length (); )
+ {
+ unsigned int j;
+ vec<jump_thread_edge *> *path = paths[i];
+
+ for (j = 0; j < path->length (); j++)
+ {
+ edge e = (*path)[j]->e;
+ if (removed_edges->find_slot (e, NO_INSERT))
+ break;
+ }
+
+ if (j != path->length ())
+ {
+ delete_jump_thread_path (path);
+ paths.unordered_remove (i);
+ continue;
+ }
+ i++;
+ }
+
/* Jump-thread all FSM threads before other jump-threads. */
for (i = 0; i < paths.length ();)
{
/* Do not jump-thread twice from the same block. */
if (bitmap_bit_p (threaded_blocks, entry->src->index)
- /* Verify that the jump thread path is still valid: a
- previous jump-thread may have changed the CFG, and
- invalidated the current path. */
+ /* 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. */
free_dominance_info (CDI_DOMINATORS);
bitmap_set_bit (threaded_blocks, entry->src->index);
retval = true;
+ thread_stats.num_threaded_edges++;
}
delete_jump_thread_path (path);
paths.unordered_remove (i);
+ free (region);
}
/* Remove from PATHS all the jump-threads starting with an edge already
e->aux = NULL;
ei_next (&ei);
}
- else if (bb_ends_with_multiway_branch (path->last ()->e->src))
- {
- /* The code to thread through loop headers may have
- split a block with jump threads attached to it.
-
- We can identify this with a disjoint jump threading
- path. If found, just remove it. */
- for (unsigned int i = 0; i < path->length () - 1; i++)
- if ((*path)[i]->e->dest != (*path)[i + 1]->e->src)
- {
- delete_jump_thread_path (path);
- e->aux = NULL;
- ei_next (&ei);
- break;
- }
-
- /* Our path is still valid, thread it. */
- if (e->aux)
- {
- if (thread_block ((*path)[0]->e->dest, false))
- e->aux = NULL;
- else
- {
- delete_jump_thread_path (path);
- e->aux = NULL;
- ei_next (&ei);
- }
- }
- }
- else
+ else
{
delete_jump_thread_path (path);
e->aux = NULL;
if (retval)
loops_state_set (LOOPS_NEED_FIXUP);
+ out:
+ delete removed_edges;
+ removed_edges = NULL;
return retval;
}
/* First make sure there are no NULL outgoing edges on the jump threading
path. That can happen for jumping to a constant address. */
for (unsigned int i = 0; i < path->length (); i++)
- if ((*path)[i]->e == NULL)
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file,
- "Found NULL edge in jump threading path. Cancelling jump thread:\n");
- dump_jump_thread_path (dump_file, *path, false);
- }
+ {
+ if ((*path)[i]->e == NULL)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file,
+ "Found NULL edge in jump threading path. Cancelling jump thread:\n");
+ dump_jump_thread_path (dump_file, *path, false);
+ }
- delete_jump_thread_path (path);
- return;
- }
+ delete_jump_thread_path (path);
+ return;
+ }
+
+ /* Only the FSM threader is allowed to thread across
+ backedges in the CFG. */
+ if (flag_checking
+ && (*path)[0]->type != EDGE_FSM_THREAD)
+ gcc_assert (((*path)[i]->e->flags & EDGE_DFS_BACK) == 0);
+ }
if (dump_file && (dump_flags & TDF_DETAILS))
dump_jump_thread_path (dump_file, *path, true);
projects / gcc.git / blobdiff