blob: ce086a55190edb9012b5d403ea0271951f8865ec [file]
/* SSA Jump Threading
Copyright (C) 2005-2026 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.
GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "predict.h"
#include "tree.h"
#include "gimple.h"
#include "fold-const.h"
#include "cfgloop.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "tree-ssa-threadupdate.h"
#include "tree-ssa-loop.h"
#include "cfganal.h"
#include "tree-pass.h"
#include "gimple-ssa.h"
#include "tree-phinodes.h"
#include "tree-inline.h"
#include "tree-vectorizer.h"
#include "value-range.h"
#include "gimple-range.h"
#include "tree-ssa-threadedge.h"
#include "gimple-range-path.h"
#include "tree-ssa-threadbackward.h"
#include "ssa.h"
#include "tree-cfgcleanup.h"
#include "tree-pretty-print.h"
#include "cfghooks.h"
#include "dbgcnt.h"
// Class to abstract the profitability code for the backwards threader.
class back_threader_profitability
{
public:
back_threader_profitability (bool speed_p, gimple *stmt);
void push_bb (const vec<basic_block> &);
void pop_bb ();
bool possibly_profitable_path_p (const vec<basic_block> &, bool *);
bool profitable_path_p (const vec<basic_block> &,
edge taken, bool *irreducible_loop);
private:
int account_bb (basic_block, bool);
// Number of insns on the path, less the branch we get to remove.
int net_insns () const { return m_stats.n_insns - m_exit_jump_benefit; }
const bool m_speed_p;
int m_exit_jump_benefit;
bool m_threaded_multiway_branch;
// The loop the path starts in, i.e. m_path[0]->loop_father.
class loop *m_loop;
// The following are accumulated by push_bb as the path grows and
// restored by pop_bb as it shrinks.
struct path_stats
{
int n_insns;
bool threaded_through_latch;
bool multiway_branch_in_path;
bool contains_hot_bb;
bool unprofitable_bb;
};
path_stats m_stats;
// One entry per push. These are the stats as they stood before that push,
// and the insns of the block. Basically the entry pushed for m_path[i]
// accounts m_path[i - 1].
struct unwind_state
{
path_stats stats;
int bb_insns;
};
auto_vec<unwind_state, 20> m_unwind;
};
back_threader_profitability::back_threader_profitability (bool speed_p,
gimple *last)
: m_speed_p (speed_p)
{
m_threaded_multiway_branch = (gimple_code (last) == GIMPLE_SWITCH
|| gimple_code (last) == GIMPLE_GOTO);
// The forward threader has estimate_threading_killed_stmts, in
// particular it estimates further DCE from eliminating the exit
// control stmt.
m_exit_jump_benefit = estimate_num_insns (last, &eni_size_weights);
m_loop = NULL;
m_stats = path_stats ();
}
/* Account for BB in the cumulative stats for the path being threaded.
CHECK_MULTIWAY is true for all blocks except the block whose branch
we are going to eliminate. Return the number of insns in BB, which
PUSH_BB records so the dump can print a per-block count. */
int
back_threader_profitability::account_bb (basic_block bb, bool check_multiway)
{
int n_insns = 0;
if (!m_stats.contains_hot_bb && m_speed_p)
m_stats.contains_hot_bb |= optimize_bb_for_speed_p (bb);
for (gimple_stmt_iterator gsi = gsi_after_labels (bb);
!gsi_end_p (gsi);
gsi_next_nondebug (&gsi))
{
/* Do not allow OpenACC loop markers and __builtin_constant_p on
threading paths. The latter is disallowed, because an
expression might be constant on two threading paths, and
become non-constant (i.e.: phi) when they merge. */
gimple *stmt = gsi_stmt (gsi);
if (gimple_call_internal_p (stmt, IFN_UNIQUE)
|| gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
{
m_stats.unprofitable_bb = true;
return n_insns;
}
/* Do not count empty statements and labels. */
if (gimple_code (stmt) != GIMPLE_NOP
&& !is_gimple_debug (stmt))
n_insns += estimate_num_insns (stmt, &eni_size_weights);
}
/* We do not look at the block with the threaded branch in this loop.
So if any block with a last statement that is a GIMPLE_SWITCH or
GIMPLE_GOTO is seen, then we have a multiway branch on our path. */
if (check_multiway)
{
gimple *last = *gsi_last_bb (bb);
if (last
&& (gimple_code (last) == GIMPLE_SWITCH
|| gimple_code (last) == GIMPLE_GOTO))
m_stats.multiway_branch_in_path = true;
}
return n_insns;
}
/* Update the stats after a block has been appended to PATH. */
void
back_threader_profitability::push_bb (const vec<basic_block> &path)
{
unwind_state state = { m_stats, /*bb_insns=*/0 };
unsigned n = path.length ();
if (n == 1)
m_loop = path[0]->loop_father;
else
{
/* Appending a block makes the previous entry block part of the copied
path, so that's where to account for now. */
unsigned copied = n - 2;
bool check_multiway = copied > 0;
state.bb_insns = account_bb (path[copied], check_multiway);
m_stats.n_insns += state.bb_insns;
}
m_unwind.safe_push (state);
/* Note if we thread through the latch, we will want to include the
last entry in the array when determining if we thread through the
loop latch. */
if (m_loop->latch == path[n - 1])
m_stats.threaded_through_latch = true;
}
void
back_threader_profitability::pop_bb ()
{
m_stats = m_unwind.pop ().stats;
}
// Used to differentiate unreachable edges, so we may stop the search
// in a the given direction.
const edge back_threader::UNREACHABLE_EDGE = (edge) -1;
back_threader::back_threader (function *fun, unsigned flags, bool first)
: m_visited_flag (fun), m_first (first)
{
if (flags & BT_SPEED)
loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
else
loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
m_fun = fun;
m_flags = flags;
m_last_stmt = NULL;
// The path solver needs EDGE_DFS_BACK in resolving mode.
if (flags & BT_RESOLVE)
mark_dfs_back_edges ();
m_ranger = new gimple_ranger;
m_solver = NULL;
}
back_threader::~back_threader ()
{
delete m_ranger;
loop_optimizer_finalize ();
}
// A wrapper for the various debug counters for the threading passes.
// Returns TRUE if it's OK to register the current threading
// candidate.
bool
back_threader::debug_counter ()
{
// The ethread pass is mostly harmless ;-).
if ((m_flags & BT_SPEED) == 0)
return true;
if (m_flags & BT_RESOLVE)
{
if (m_first && !dbg_cnt (back_threadfull1))
return false;
if (!m_first && !dbg_cnt (back_threadfull2))
return false;
}
else
{
if (m_first && !dbg_cnt (back_thread1))
return false;
if (!m_first && !dbg_cnt (back_thread2))
return false;
}
return true;
}
static void
dump_path (FILE *dump_file, const vec<basic_block> &path)
{
for (unsigned i = path.length (); i > 0; --i)
{
basic_block bb = path[i - 1];
fprintf (dump_file, "%d", bb->index);
if (i > 1)
fprintf (dump_file, "->");
}
}
// Dump details of an attempt to register a path.
void
back_threader::maybe_register_path_dump (edge taken)
{
if (m_path.is_empty ())
return;
fprintf (dump_file, "path: ");
dump_path (dump_file, m_path);
fprintf (dump_file, "->");
if (taken == UNREACHABLE_EDGE)
fprintf (dump_file, "xx REJECTED (unreachable)\n");
else if (taken)
fprintf (dump_file, "%d SUCCESS\n", taken->dest->index);
else
fprintf (dump_file, "xx REJECTED\n");
}
// If an outgoing edge can be determined out of the current path,
// register it for jump threading and return the taken edge.
//
// Return NULL if it is unprofitable to thread this path, or the
// outgoing edge is unknown. Return UNREACHABLE_EDGE if the path is
// unreachable.
edge
back_threader::maybe_register_path (back_threader_profitability &profit)
{
edge taken_edge = find_taken_edge (m_path);
if (taken_edge && taken_edge != UNREACHABLE_EDGE)
{
bool irreducible = false;
if (profit.profitable_path_p (m_path, taken_edge, &irreducible)
&& debug_counter ()
&& m_registry.register_path (m_path, taken_edge))
{
if (irreducible)
vect_free_loop_info_assumptions (m_path[0]->loop_father);
}
else
taken_edge = NULL;
}
if (dump_file && (dump_flags & TDF_DETAILS))
maybe_register_path_dump (taken_edge);
return taken_edge;
}
// Return the known taken edge out of a path. If the path can be
// determined to be unreachable, return UNREACHABLE_EDGE. If no
// outgoing edge can be calculated, return NULL.
edge
back_threader::find_taken_edge (const vec<basic_block> &path)
{
gcc_checking_assert (path.length () > 1);
switch (gimple_code (m_last_stmt))
{
case GIMPLE_COND:
return find_taken_edge_cond (path, as_a<gcond *> (m_last_stmt));
case GIMPLE_SWITCH:
return find_taken_edge_switch (path, as_a<gswitch *> (m_last_stmt));
case GIMPLE_GOTO:
return find_taken_edge_goto (path, as_a<ggoto *> (m_last_stmt));
default:
return NULL;
}
}
// Same as find_taken_edge, but for paths ending in a computed goto.
edge
back_threader::find_taken_edge_goto (const vec<basic_block> &path,
ggoto *stmt)
{
tree dest = gimple_goto_dest (stmt);
if (TREE_CODE (dest) == SSA_NAME)
{
prange r;
m_solver->reset_path (path, m_imports);
if (!m_solver->range_of_expr (r, dest, stmt))
return NULL;
if (r.undefined_p ())
return UNREACHABLE_EDGE;
dest = r.addr_known ();
if (!dest)
return NULL;
}
// For a destination that did not resolve to a label,
// ::find_taken_edge at most returns the block's single successor,
// the only place it could go.
return ::find_taken_edge (gimple_bb (stmt), dest);
}
// Same as find_taken_edge, but for paths ending in a switch.
edge
back_threader::find_taken_edge_switch (const vec<basic_block> &path,
gswitch *sw)
{
tree name = gimple_switch_index (sw);
int_range_max r;
m_solver->reset_path (path, m_imports);
m_solver->range_of_expr (r, name, sw);
if (r.undefined_p ())
return UNREACHABLE_EDGE;
if (r.varying_p ())
return NULL;
tree label = find_case_label_range (sw, &r);
if (!label)
return NULL;
return find_edge (gimple_bb (sw), label_to_block (cfun, CASE_LABEL (label)));
}
// Same as find_taken_edge, but for paths ending in a GIMPLE_COND.
edge
back_threader::find_taken_edge_cond (const vec<basic_block> &path,
gcond *cond)
{
int_range_max r;
m_solver->reset_path (path, m_imports);
m_solver->range_of_stmt (r, cond);
if (m_solver->unreachable_path_p ())
return UNREACHABLE_EDGE;
int_range<2> true_range = range_true ();
int_range<2> false_range = range_false ();
if (r == true_range || r == false_range)
{
edge e_true, e_false;
basic_block bb = gimple_bb (cond);
extract_true_false_edges_from_block (bb, &e_true, &e_false);
return r == true_range ? e_true : e_false;
}
return NULL;
}
// Find jump threading paths to any of the SSA names in the
// INTERESTING bitmap, and register any such paths.
//
// BB is the current path being processed.
//
// OVERALL_PATHS is the search space up to this block
void
back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
unsigned overall_paths,
back_threader_profitability &profit)
{
if (bb->flags & m_visited_flag)
return;
bb->flags |= m_visited_flag;
m_path.safe_push (bb);
profit.push_bb (m_path);
// Try to resolve the path without looking back. Avoid resolving paths
// we know are large but are not (yet) recognized as Finite State Machine.
// ??? Ideally we'd explore the cheapest path to the loop backedge here,
// avoiding the exponential greedy search and only start that from there.
// Precomputing a path-size-to-immediate-dominator-of-successor for each
// edge might help here. Alternatively copying divergent control flow
// on the way to the backedge could be worthwhile.
bool large_non_fsm;
edge e;
if (m_path.length () > 1
&& (!profit.possibly_profitable_path_p (m_path, &large_non_fsm)
|| (!large_non_fsm
&& maybe_register_path (profit))))
;
// The backwards thread copier cannot copy blocks that do not belong
// to the same loop, so when the new source of the path entry no
// longer belongs to it we don't need to search further.
else if (m_path[0]->loop_father != bb->loop_father
&& (!(e = loop_exits_from_bb_p (m_path[0]->loop_father,
m_path[0]))
|| e->dest->loop_father != bb->loop_father))
;
// Continue looking for ways to extend the path but limit the
// search space along a branch
else if ((overall_paths = overall_paths * EDGE_COUNT (bb->preds))
<= (unsigned)param_max_jump_thread_paths)
{
// For further greedy searching we want to remove interesting
// names defined in BB but add ones on the PHI edges for the
// respective edges and adding imports from those stmts.
// We do this by starting with all names
// not defined in BB as interesting, collecting a list of
// interesting PHIs in BB on the fly. Then we iterate over
// predecessor edges, adding interesting PHI edge defs to
// the set of interesting names to consider when processing it.
auto_bitmap new_interesting;
auto_vec<int, 16> new_imports;
auto_vec<gphi *, 4> interesting_phis;
bitmap_iterator bi;
unsigned i;
auto_vec<tree, 16> worklist;
// Add NAME to the list of imports.
auto add_import = [&] (tree name)
{
if (bitmap_set_bit (m_imports, SSA_NAME_VERSION (name)))
{
new_imports.safe_push (SSA_NAME_VERSION (name));
worklist.safe_push (name);
}
};
EXECUTE_IF_SET_IN_BITMAP (interesting, 0, i, bi)
{
tree name = ssa_name (i);
gimple *def_stmt = SSA_NAME_DEF_STMT (name);
/* Imports remain interesting. */
if (gimple_bb (def_stmt) != bb)
{
bitmap_set_bit (new_interesting, i);
continue;
}
worklist.quick_push (name);
while (!worklist.is_empty ())
{
tree name = worklist.pop ();
gimple *def_stmt = SSA_NAME_DEF_STMT (name);
/* Newly discovered imports are interesting. */
if (gimple_bb (def_stmt) != bb)
{
bitmap_set_bit (new_interesting, SSA_NAME_VERSION (name));
continue;
}
/* Local PHIs participate in renaming below. */
if (gphi *phi = dyn_cast<gphi *> (def_stmt))
interesting_phis.safe_push (phi);
/* For other local defs process their uses, amending
imports on the way. */
else
{
tree ssa[3];
unsigned lim = gimple_range_ssa_names (ssa, 3, def_stmt);
for (unsigned j = 0; j < lim; ++j)
if (ssa[j])
add_import (ssa[j]);
}
}
}
if (!bitmap_empty_p (new_interesting)
|| !interesting_phis.is_empty ())
{
auto_vec<int, 4> unwind (interesting_phis.length ());
auto_vec<int, 4> imports_unwind (interesting_phis.length ());
edge_iterator iter;
edge e;
FOR_EACH_EDGE (e, iter, bb->preds)
{
if (e->flags & EDGE_ABNORMAL
|| e->src->index == ENTRY_BLOCK)
continue;
for (gphi *phi : interesting_phis)
{
tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
if (TREE_CODE (def) == SSA_NAME)
{
int ver = SSA_NAME_VERSION (def);
if (bitmap_set_bit (new_interesting, ver))
{
if (bitmap_set_bit (m_imports, ver))
imports_unwind.quick_push (ver);
unwind.quick_push (ver);
}
}
}
find_paths_to_names (e->src, new_interesting, overall_paths,
profit);
// Restore new_interesting.
for (int def : unwind)
bitmap_clear_bit (new_interesting, def);
unwind.truncate (0);
// Restore and m_imports.
for (int def : imports_unwind)
bitmap_clear_bit (m_imports, def);
imports_unwind.truncate (0);
}
}
/* m_imports tracks all interesting names on the path, so when
backtracking we have to restore it. */
for (int j : new_imports)
bitmap_clear_bit (m_imports, j);
}
else if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " FAIL: Search space limit %d reached.\n",
param_max_jump_thread_paths);
// Reset things to their original state.
profit.pop_bb ();
m_path.pop ();
bb->flags &= ~m_visited_flag;
}
// Search backwards from BB looking for paths where the final
// conditional maybe threaded to a successor block. Record such paths
// for jump threading.
void
back_threader::maybe_thread_block (basic_block bb)
{
if (EDGE_COUNT (bb->succs) <= 1)
return;
gimple *stmt = *gsi_last_bb (bb);
if (!stmt)
return;
enum gimple_code code = gimple_code (stmt);
if (code != GIMPLE_SWITCH
&& code != GIMPLE_COND
&& code != GIMPLE_GOTO)
return;
m_last_stmt = stmt;
m_path.truncate (0);
// We compute imports of the path during discovery starting
// just with names used in the conditional.
bitmap_clear (m_imports);
ssa_op_iter iter;
tree name;
FOR_EACH_SSA_TREE_OPERAND (name, stmt, iter, SSA_OP_USE)
{
if (!gimple_range_ssa_p (name))
return;
bitmap_set_bit (m_imports, SSA_NAME_VERSION (name));
}
// Interesting is the set of imports we still not have see
// the definition of. So while imports only grow, the
// set of interesting defs dwindles and once empty we can
// stop searching.
auto_bitmap interesting;
bitmap_copy (interesting, m_imports);
back_threader_profitability profit (m_flags & BT_SPEED, stmt);
find_paths_to_names (bb, interesting, 1, profit);
}
DEBUG_FUNCTION void
debug (const vec <basic_block> &path)
{
dump_path (stderr, path);
fputc ('\n', stderr);
}
void
back_threader::dump (FILE *out)
{
fprintf (out, "\nCandidates for pre-computation:\n");
fprintf (out, "===================================\n");
bitmap_iterator bi;
unsigned i;
EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
{
tree name = ssa_name (i);
print_generic_expr (out, name, TDF_NONE);
fprintf (out, "\n");
}
}
void
back_threader::debug ()
{
dump (stderr);
}
/* Examine jump threading path PATH and return TRUE if it is possibly
profitable to thread it, otherwise return FALSE. If this function
returns TRUE profitable_path_p might not be satisfied but when
the path is extended it might be. In particular indicate in
*LARGE_NON_FSM whether the thread is too large for a non-FSM thread
but would be OK if we extend the path to cover the loop backedge.
?? It seems we should be able to loosen some of the restrictions in
this function after loop optimizations have run. */
bool
back_threader_profitability::possibly_profitable_path_p
(const vec<basic_block> &m_path,
bool *large_non_fsm)
{
gcc_checking_assert (!m_path.is_empty ());
/* We can an empty path here (excluding the DEF block) when the
statement that makes a conditional generate a compile-time
constant result is in the same block as the conditional.
That's not really a jump threading opportunity, but instead is
simple cprop & simplification. We could handle it here if we
wanted by wiring up all the incoming edges. If we run this
early in IPA, that might be worth doing. For now we just
reject that case. */
if (m_path.length () <= 1)
return false;
loop_p loop = m_loop;
if (m_stats.unprofitable_bb)
return false;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Checking profitability of path (backwards): ");
for (unsigned j = 0; j < m_path.length (); j++)
{
fprintf (dump_file, " bb:%i", m_path[j]->index);
/* The last block on the path is not copied, so it has no
count of its own. */
if (j + 1 < m_path.length ())
fprintf (dump_file, " (%i insns)", m_unwind[j + 1].bb_insns);
if (loop->latch == m_path[j])
fprintf (dump_file, " (latch)");
}
fprintf (dump_file, "\n Control statement insns: %i\n"
" Overall: %i insns\n",
m_exit_jump_benefit, net_insns ());
}
/* Threading is profitable if the path duplicated is hot but also
in a case we separate cold path from hot path and permit optimization
of the hot path later. Be on the aggressive side here. In some testcases,
as in PR 78407 this leads to noticeable improvements. */
if (m_speed_p)
{
if (net_insns () >= param_max_fsm_thread_path_insns)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " FAIL: Jump-thread path not considered: "
"the number of instructions on the path "
"exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
return false;
}
edge entry = find_edge (m_path[m_path.length () - 1],
m_path[m_path.length () - 2]);
if (probably_never_executed_edge_p (cfun, entry))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " FAIL: Jump-thread path not considered: "
"path entry is probably never executed.\n");
return false;
}
}
else if (net_insns () > 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " FAIL: Jump-thread path not considered: "
"duplication of %i insns is needed and optimizing for size.\n",
net_insns ());
return false;
}
/* The generic copier used by the backthreader does not re-use an
existing threading path to reduce code duplication. So for that
case, drastically reduce the number of statements we are allowed
to copy. We don't know yet whether we will thread through the latch
so we have to be permissive and continue threading, but indicate
to the caller the thread, if final, wouldn't be profitable. */
if ((!m_threaded_multiway_branch
|| !loop->latch
|| loop->latch->index == EXIT_BLOCK)
&& (net_insns () * param_fsm_scale_path_stmts
>= param_max_jump_thread_duplication_stmts))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
" FAIL: Did not thread around loop and would copy too "
"many statements.\n");
return false;
}
*large_non_fsm = (!(m_stats.threaded_through_latch
&& m_threaded_multiway_branch)
&& (net_insns () * param_fsm_scale_path_stmts
>= param_max_jump_thread_duplication_stmts));
if (dump_file && (dump_flags & TDF_DETAILS))
fputc ('\n', dump_file);
return true;
}
/* Examine jump threading path PATH and return TRUE if it is profitable to
thread it, otherwise return FALSE.
The taken edge out of the path is TAKEN_EDGE.
CREATES_IRREDUCIBLE_LOOP is set to TRUE if threading this path
would create an irreducible loop.
?? It seems we should be able to loosen some of the restrictions in
this function after loop optimizations have run. */
bool
back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
edge taken_edge,
bool *creates_irreducible_loop)
{
// We can assume that possibly_profitable_path_p holds here
loop_p loop = m_path[0]->loop_father;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Checking profitability of path (backwards): ");
/* If this path threaded 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. */
*creates_irreducible_loop = false;
if (m_stats.threaded_through_latch
&& loop == taken_edge->dest->loop_father
&& (determine_bb_domination_status (loop, taken_edge->dest)
== DOMST_NONDOMINATING))
*creates_irreducible_loop = true;
/* Threading is profitable if the path duplicated is hot but also
in a case we separate cold path from hot path and permit optimization
of the hot path later. Be on the aggressive side here. In some testcases,
as in PR 78407 this leads to noticeable improvements. */
if (m_speed_p
&& (optimize_edge_for_speed_p (taken_edge) || m_stats.contains_hot_bb))
{
if (probably_never_executed_edge_p (cfun, taken_edge))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " FAIL: Jump-thread path not considered: "
"path leads to probably never executed edge.\n");
return false;
}
}
else if (net_insns () > 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " FAIL: Jump-thread path not considered: "
"duplication of %i insns is needed and optimizing for size.\n",
net_insns ());
return false;
}
/* We avoid creating irreducible inner loops unless we thread through
a multiway branch, in which case we have deemed it worth losing
other loop optimizations later.
We also consider it worth creating an irreducible inner loop after
loop optimizations if the number of copied statement is low. */
if (!m_threaded_multiway_branch
&& *creates_irreducible_loop
&& (!(cfun->curr_properties & PROP_loop_opts_done)
|| (net_insns () * param_fsm_scale_path_stmts
>= param_max_jump_thread_duplication_stmts)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
" FAIL: Would create irreducible loop early without "
"threading multiway branch.\n");
/* We compute creates_irreducible_loop only late. */
return false;
}
/* The generic copier used by the backthreader does not re-use an
existing threading path to reduce code duplication. So for that
case, drastically reduce the number of statements we are allowed
to copy. */
if (!(m_stats.threaded_through_latch && m_threaded_multiway_branch)
&& (net_insns () * param_fsm_scale_path_stmts
>= param_max_jump_thread_duplication_stmts))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
" FAIL: Did not thread around loop and would copy too "
"many statements.\n");
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 (!m_threaded_multiway_branch && m_stats.multiway_branch_in_path)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
" FAIL: Thread through multiway branch without threading "
"a multiway branch.\n");
return false;
}
/* Threading through an empty latch would cause code to be added to
the latch. This could alter the loop form sufficiently to cause
loop optimizations to fail. Disable these threads until after
loop optimizations have run. */
if ((m_stats.threaded_through_latch || taken_edge->dest == loop->latch)
&& !(cfun->curr_properties & PROP_loop_opts_done)
&& empty_block_p (loop->latch))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
" FAIL: Thread through latch before loop opts would create "
"non-empty latch\n");
return false;
}
if (dump_file && (dump_flags & TDF_DETAILS))
fputc ('\n', dump_file);
return true;
}
/* The current path PATH is a vector of blocks forming a jump threading
path in reverse order. TAKEN_EDGE is the edge taken from path[0].
Convert the current path into the form used by register_jump_thread and
register it.
Return TRUE if successful or FALSE otherwise. */
bool
back_threader_registry::register_path (const vec<basic_block> &m_path,
edge taken_edge)
{
vec<jump_thread_edge *> *jump_thread_path = allocate_thread_path ();
// The generic copier ignores the edge type. We can build the
// thread edges with any type.
for (unsigned int j = 0; j + 1 < m_path.length (); j++)
{
basic_block bb1 = m_path[m_path.length () - j - 1];
basic_block bb2 = m_path[m_path.length () - j - 2];
edge e = find_edge (bb1, bb2);
gcc_assert (e);
push_edge (jump_thread_path, e, EDGE_COPY_SRC_BLOCK);
}
push_edge (jump_thread_path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
return register_jump_thread (jump_thread_path);
}
// Return a new path solver for the search.
path_range_query *
back_threader::make_solver (gimple_ranger &ranger)
{
return new path_range_query (ranger, m_flags & BT_RESOLVE);
}
// Find the paths to thread in the current function.
void
back_threader::search ()
{
m_solver = make_solver (*m_ranger);
basic_block bb;
FOR_EACH_BB_FN (bb, m_fun)
if (EDGE_COUNT (bb->succs) > 1)
maybe_thread_block (bb);
// The solver lives as long as the search: the IL changes after it.
delete m_solver;
m_solver = NULL;
}
// Thread the paths found. Return TODO_flags.
unsigned int
back_threader::apply ()
{
bool changed = m_registry.thread_through_all_blocks (true);
if (m_flags & BT_SPEED)
return changed ? TODO_cleanup_cfg : 0;
return false;
}
// Thread all suitable paths in the current function.
//
// Return TODO_flags.
unsigned int
back_threader::thread_blocks ()
{
search ();
return apply ();
}
namespace {
const pass_data pass_data_early_thread_jumps =
{
GIMPLE_PASS,
"ethread",
OPTGROUP_NONE,
TV_TREE_SSA_THREAD_JUMPS,
( PROP_cfg | PROP_ssa ),
0,
0,
0,
( TODO_cleanup_cfg | TODO_update_ssa ),
};
const pass_data pass_data_thread_jumps =
{
GIMPLE_PASS,
"thread",
OPTGROUP_NONE,
TV_TREE_SSA_THREAD_JUMPS,
( PROP_cfg | PROP_ssa ),
0,
0,
0,
TODO_update_ssa,
};
const pass_data pass_data_thread_jumps_full =
{
GIMPLE_PASS,
"threadfull",
OPTGROUP_NONE,
TV_TREE_SSA_THREAD_JUMPS,
( PROP_cfg | PROP_ssa ),
0,
0,
0,
TODO_update_ssa,
};
// Early jump threading pass optimizing for size.
class pass_early_thread_jumps : public gimple_opt_pass
{
public:
pass_early_thread_jumps (gcc::context *ctxt)
: gimple_opt_pass (pass_data_early_thread_jumps, ctxt)
{}
opt_pass * clone () override
{
return new pass_early_thread_jumps (m_ctxt);
}
void set_pass_param (unsigned int, bool param) override
{
m_first = param;
}
bool gate (function *) override
{
return flag_thread_jumps;
}
unsigned int execute (function *fun) override
{
back_threader threader (fun, BT_NONE, m_first);
return threader.thread_blocks ();
}
private:
bool m_first;
};
// Jump threading pass without resolving of unknown SSAs.
class pass_thread_jumps : public gimple_opt_pass
{
public:
pass_thread_jumps (gcc::context *ctxt)
: gimple_opt_pass (pass_data_thread_jumps, ctxt)
{}
opt_pass * clone (void) override
{
return new pass_thread_jumps (m_ctxt);
}
void set_pass_param (unsigned int, bool param) override
{
m_first = param;
}
bool gate (function *) override
{
return flag_thread_jumps && flag_expensive_optimizations;
}
unsigned int execute (function *fun) override
{
back_threader threader (fun, BT_SPEED, m_first);
return threader.thread_blocks ();
}
private:
bool m_first;
};
// Jump threading pass that fully resolves unknown SSAs.
class pass_thread_jumps_full : public gimple_opt_pass
{
public:
pass_thread_jumps_full (gcc::context *ctxt)
: gimple_opt_pass (pass_data_thread_jumps_full, ctxt)
{}
opt_pass * clone (void) override
{
return new pass_thread_jumps_full (m_ctxt);
}
void set_pass_param (unsigned int, bool param) override
{
m_first = param;
}
bool gate (function *) override
{
return flag_thread_jumps && flag_expensive_optimizations;
}
unsigned int execute (function *fun) override
{
back_threader threader (fun, BT_SPEED | BT_RESOLVE, m_first);
return threader.thread_blocks ();
}
private:
bool m_first;
};
} // namespace {
gimple_opt_pass *
make_pass_thread_jumps (gcc::context *ctxt)
{
return new pass_thread_jumps (ctxt);
}
gimple_opt_pass *
make_pass_thread_jumps_full (gcc::context *ctxt)
{
return new pass_thread_jumps_full (ctxt);
}
gimple_opt_pass *
make_pass_early_thread_jumps (gcc::context *ctxt)
{
return new pass_early_thread_jumps (ctxt);
}