Data Structures
struct	el
struct	redirection_data
struct	ssa_local_info_t
struct	thread_stats_d

Enumerations
enum	bb_dom_status { DOMST_NONDOMINATING, DOMST_LOOP_BROKEN, DOMST_DOMINATING }

Functions
static void	remove_ctrl_stmt_and_useless_edges ()
static void	create_block_for_threading ()
static struct redirection_data *	lookup_redirection_data ()
static void	copy_phi_args ()
static void	update_destination_phis ()
static void	create_edge_and_update_destination_phis (struct redirection_data *rd, basic_block bb)
void	ssa_fix_duplicate_block_edges (struct redirection_data rd, ssa_local_info_t local_info)
int	ssa_create_duplicates (struct redirection_data *slot, ssa_local_info_t local_info)
int	ssa_fixup_template_block (struct redirection_data *slot, ssa_local_info_t local_info)
int	ssa_redirect_edges (struct redirection_data *slot, ssa_local_info_t local_info)
static bool	redirection_block_p ()
static bool	thread_block ()
static basic_block	thread_single_edge ()
static bool	dbds_continue_enumeration_p ()
static enum bb_dom_status	determine_bb_domination_status ()
static bool	def_split_header_continue_p ()
static bool	thread_through_loop_header ()
static void	mark_threaded_blocks ()
bool	thread_through_all_blocks ()
void	register_jump_thread ()

Variables
static vec< edge >	threaded_edges
struct thread_stats_d	thread_stats
static hash_table < redirection_data >	redirection_data
static basic_block	dbds_ce_stop

Enumeration Type Documentation

enum bb_dom_status

Evaluates the dominance relationship of latch of the LOOP and BB, and
   returns the state.

Enumerator:

DOMST_NONDOMINATING
DOMST_LOOP_BROKEN
DOMST_DOMINATING

Function Documentation

static void copy_phi_args ( )

static

For each PHI in BB, copy the argument associated with SRC_E to TGT_E.

References add_phi_arg(), edge_def::dest_idx, gimple_phi_arg_def(), gimple_phi_arg_location(), gsi_end_p(), gsi_next(), gsi_start_phis(), and gsi_stmt().

Referenced by create_edge_and_update_destination_phis(), ssa_fix_duplicate_block_edges(), and update_destination_phis().

static void create_block_for_threading ( )

static

Create a duplicate of BB.  Record the duplicate block in RD.

References edge_def::aux, basic_block_def::count, redirection_data::dup_block, duplicate_block(), basic_block_def::frequency, and basic_block_def::succs.

Referenced by ssa_create_duplicates(), and thread_single_edge().

static void create_edge_and_update_destination_phis	(	struct redirection_data *	rd,
		basic_block	bb
	)

static

Given a duplicate block and its single destination (both stored
   in RD).  Create an edge between the duplicate and its single
   destination.

   Add an additional argument to any PHI nodes at the single
   destination.

References edge_def::aux, copy_phi_args(), edge_def::count, basic_block_def::count, edge_def::dest, el::e, make_edge(), redirection_data::outgoing_edge, edge_def::probability, and rescan_loop_exit().

Referenced by ssa_fix_duplicate_block_edges(), and thread_single_edge().

static bool dbds_continue_enumeration_p ( )

static

Referenced by determine_bb_domination_status().

static bool def_split_header_continue_p ( )

static

Return true if BB is part of the new pre-header that is created
   when threading the latch to DATA.

References loop_depth(), basic_block_def::loop_father, and loop_outer().

Referenced by thread_through_loop_header().

static enum bb_dom_status determine_bb_domination_status ( )

static

References dbds_continue_enumeration_p(), dfs_enumerate_from(), DOMST_DOMINATING, DOMST_LOOP_BROKEN, DOMST_NONDOMINATING, free(), loop::header, loop::latch, loop::num_nodes, basic_block_def::preds, and edge_def::src.

Referenced by thread_through_loop_header().

static struct redirection_data* lookup_redirection_data ( )

staticread

Given an outgoing edge E lookup and return its entry in our hash table.

   If INSERT is true, then we insert the entry into the hash table if
   it is not already present.  INCOMING_EDGE is added to the list of incoming
   edges associated with E in the hash table.

References redirection_data::dup_block, el::e, hash_table< Descriptor, Allocator >::find_slot(), free(), redirection_data::incoming_edges, redirection_data::intermediate_edge, el::next, and redirection_data::outgoing_edge.

Referenced by thread_block().

static void mark_threaded_blocks ( )

static

Walk through the registered jump threads and convert them into a
   form convenient for this pass.

   Any block which has incoming edges threaded to outgoing edges
   will have its entry in THREADED_BLOCK set.

   Any threaded edge will have its new outgoing edge stored in the
   original edge's AUX field.

   This form avoids the need to walk all the edges in the CFG to
   discover blocks which need processing and avoids unnecessary
   hash table lookups to map from threaded edge to new target.

References edge_def::aux, bitmap_copy(), bitmap_set_bit(), cfun, edge_def::dest, free(), basic_block_def::index, optimize_function_for_size_p(), basic_block_def::preds, and redirection_block_p().

Referenced by thread_through_all_blocks().

static bool redirection_block_p ( )

static

Return true if this block has no executable statements other than
   a simple ctrl flow instruction.  When the number of outgoing edges
   is one, this is equivalent to a "forwarder" block.

References gimple_nop_p(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), and is_gimple_debug().

Referenced by mark_threaded_blocks(), and thread_through_loop_header().

void register_jump_thread ( )

Register a jump threading opportunity.  We queue up all the jump
   threading opportunities discovered by a pass and update the CFG
   and SSA form all at once.

   E is the edge we can thread, E2 is the new target edge, i.e., we
   are effectively recording that E->dest can be changed to E2->dest
   after fixing the SSA graph.

References edge_def::dest, dump_file, dump_flags, and edge_def::src.

static void remove_ctrl_stmt_and_useless_edges ( )

static

Remove the last statement in block BB if it is a control statement
   Also remove all outgoing edges except the edge which reaches DEST_BB.
   If DEST_BB is NULL, then remove all outgoing edges.

References edge_def::dest, ei_next(), ei_safe_edge(), gsi_end_p(), gsi_last_bb(), gsi_remove(), gsi_stmt(), remove_edge(), and basic_block_def::succs.

Referenced by ssa_fix_duplicate_block_edges(), and thread_single_edge().

int ssa_create_duplicates	(	struct redirection_data **	slot,
		ssa_local_info_t *	local_info
	)

Hash table traversal callback routine to create duplicate blocks.

References ssa_local_info_t::bb, create_block_for_threading(), redirection_data::dup_block, ssa_fix_duplicate_block_edges(), and ssa_local_info_t::template_block.

Referenced by thread_block().

void ssa_fix_duplicate_block_edges	(	struct redirection_data *	rd,
		ssa_local_info_t *	local_info
	)

Wire up the outgoing edges from the duplicate block and
   update any PHIs as needed.

References ssa_local_info_t::bb, copy_phi_args(), create_edge_and_update_destination_phis(), edge_def::dest, redirection_data::dup_block, el::e, find_edge(), redirection_data::incoming_edges, redirect_edge_and_branch(), remove_ctrl_stmt_and_useless_edges(), and update_destination_phis().

Referenced by ssa_create_duplicates(), and ssa_fixup_template_block().

int ssa_fixup_template_block	(	struct redirection_data **	slot,
		ssa_local_info_t *	local_info
	)

inline

We did not create any outgoing edges for the template block during
   block creation.  This hash table traversal callback creates the
   outgoing edge for the template block.

References redirection_data::dup_block, ssa_fix_duplicate_block_edges(), and ssa_local_info_t::template_block.

Referenced by thread_block().

int ssa_redirect_edges	(	struct redirection_data **	slot,
		ssa_local_info_t *	local_info
	)

Hash table traversal callback to redirect each incoming edge
   associated with this hash table element to its new destination.

References edge_def::aux, edge_def::count, basic_block_def::count, edge_def::dest, dump_file, dump_flags, redirection_data::dup_block, el::e, flush_pending_stmts(), free(), basic_block_def::frequency, redirection_data::incoming_edges, basic_block_def::index, ssa_local_info_t::jumps_threaded, el::next, thread_stats_d::num_threaded_edges, redirect_edge_and_branch(), edge_def::src, and thread_stats.

Referenced by thread_block().

static bool thread_block ( )

static

BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
   is reached via one or more specific incoming edges, we know which
   outgoing edge from BB will be traversed.

   We want to redirect those incoming edges to the target of the
   appropriate outgoing edge.  Doing so avoids a conditional branch
   and may expose new optimization opportunities.  Note that we have
   to update dominator tree and SSA graph after such changes.

   The key to keeping the SSA graph update manageable is to duplicate
   the side effects occurring in BB so that those side effects still
   occur on the paths which bypass BB after redirecting edges.

   We accomplish this by creating duplicates of BB and arranging for
   the duplicates to unconditionally pass control to one specific
   successor of BB.  We then revector the incoming edges into BB to
   the appropriate duplicate of BB.

   If NOLOOP_ONLY is true, we only perform the threading as long as it
   does not affect the structure of the loops in a nontrivial way.

References edge_def::aux, ssa_local_info_t::bb, CDI_DOMINATORS, edge_def::count, hash_table< Descriptor, Allocator >::create(), edge_def::dest, hash_table< Descriptor, Allocator >::dispose(), el::e, free_dominance_info(), loop::header, ssa_local_info_t::jumps_threaded, loop::latch, lookup_redirection_data(), loop_exit_edge_p(), basic_block_def::loop_father, loop_latch_edge(), loop_outer(), LOOPS_NEED_FIXUP, loops_state_set(), basic_block_def::preds, set_loop_copy(), edge_def::src, ssa_create_duplicates(), ssa_fixup_template_block(), ssa_redirect_edges(), basic_block_def::succs, ssa_local_info_t::template_block, hash_table< Descriptor, Allocator >::traverse(), and update_bb_profile_for_threading().

Referenced by thread_through_all_blocks(), and thread_through_loop_header().

static basic_block thread_single_edge ( )

static

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).

References edge_def::aux, edge_def::count, basic_block_def::count, create_block_for_threading(), create_edge_and_update_destination_phis(), edge_def::dest, dump_file, dump_flags, redirection_data::dup_block, edge_def::flags, flush_pending_stmts(), free(), basic_block_def::frequency, basic_block_def::index, thread_stats_d::num_threaded_edges, redirection_data::outgoing_edge, redirect_edge_and_branch(), remove_ctrl_stmt_and_useless_edges(), single_pred_p(), single_succ_edge(), edge_def::src, thread_stats, and update_bb_profile_for_threading().

Referenced by thread_through_loop_header().

bool thread_through_all_blocks ( )

Walk through all blocks and thread incoming edges to the appropriate
   outgoing edge for each edge pair recorded in THREADED_EDGES.

   It is the caller's responsibility to fix the dominance information
   and rewrite duplicated SSA_NAMEs back into SSA form.

   If MAY_PEEL_LOOP_HEADERS is false, we avoid threading edges through
   loop headers if it does not simplify the loop.

   Returns true if one or more edges were threaded, false otherwise.

References bitmap_bit_p(), cfun, free_original_copy_tables(), loop::header, basic_block_def::index, initialize_original_copy_tables(), LI_FROM_INNERMOST, LOOPS_NEED_FIXUP, loops_state_set(), mark_threaded_blocks(), memset(), thread_stats_d::num_threaded_edges, basic_block_def::preds, statistics_counter_event(), thread_block(), thread_stats, and thread_through_loop_header().

static bool thread_through_loop_header ( )

static

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.

References add_bb_to_loop(), edge_def::aux, create_preheader(), def_split_header_continue_p(), edge_def::dest, determine_bb_domination_status(), dfs_enumerate_from(), DOMST_LOOP_BROKEN, DOMST_NONDOMINATING, empty_block_p(), free(), loop::header, loop::latch, basic_block_def::loop_father, loop_latch_edge(), loop_outer(), LOOPS_MAY_HAVE_MULTIPLE_LATCHES, LOOPS_NEED_FIXUP, loops_state_set(), make_forwarder_block(), mfb_keep_just(), mfb_kj_edge, loop::num_nodes, basic_block_def::preds, redirection_block_p(), remove_bb_from_loops(), set_loop_copy(), single_succ(), single_succ_edge(), single_succ_p(), split_edge(), edge_def::src, thread_block(), and thread_single_edge().

Referenced by thread_through_all_blocks().

static void update_destination_phis ( )

static

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.

References copy_phi_args(), edge_def::dest, el::e, find_edge(), and basic_block_def::succs.

Referenced by ssa_fix_duplicate_block_edges().

Variable Documentation

basic_block dbds_ce_stop

static

Callback for dfs_enumerate_from.  Returns true if BB is different
   from STOP and DBDS_CE_STOP.

hash_table<redirection_data> redirection_data

static

Main data structure to hold information for duplicates of BB.

struct thread_stats_d thread_stats

Referenced by ssa_redirect_edges(), thread_single_edge(), and thread_through_all_blocks().

vec<edge> threaded_edges

static

Passes which use the jump threading code register jump threading
   opportunities as they are discovered.  We keep the registered
   jump threading opportunities in this vector as edge pairs
   (original_edge, target_edge).

Referenced by try_forward_edges().

Data Structures

Enumerations

Functions

Variables

Enumeration Type Documentation

Function Documentation

Variable Documentation