tree-ssa-loop-unswitch.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "fold-const.h"
#include "tree-cfg.h"
#include "tree-ssa.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
#include "tree-into-ssa.h"
#include "cfgloop.h"
#include "tree-inline.h"
#include "gimple-iterator.h"
#include "cfghooks.h"
#include "tree-ssa-loop-manip.h"
#include "tree-vectorizer.h"
#include "gimple-range.h"
#include "dbgcnt.h"
#include "cfganal.h"
#include "tree-cfgcleanup.h"

Include dependency graph for tree-ssa-loop-unswitch.cc:

Data Structures
struct	unswitch_predicate

Typedefs
typedef vec< std::pair< unswitch_predicate *, bool > >	predicate_vector

Functions
static class loop *	tree_unswitch_loop (class loop *, edge, tree)
static bool	tree_unswitch_single_loop (class loop *, dump_user_location_t, predicate_vector &predicate_path, unsigned loop_size, unsigned &budget, int ignored_edge_flag, bitmap, unswitch_predicate *=NULL, basic_block=NULL)
static void	find_unswitching_predicates_for_bb (basic_block bb, class loop *loop, class loop *&outer_loop, vec< unswitch_predicate * > &candidates, unswitch_predicate *&hottest, basic_block &hottest_bb)
static bool	tree_unswitch_outer_loop (class loop *)
static edge	find_loop_guard (class loop *, vec< gimple * > &)
static bool	empty_bb_without_guard_p (class loop *, basic_block, vec< gimple * > &)
static bool	used_outside_loop_p (class loop *, tree, vec< gimple * > &)
static void	hoist_guard (class loop *, edge)
static bool	check_exit_phi (class loop *)
static tree	get_vop_from_header (class loop *)
static void	clean_up_after_unswitching (int)
static vec< unswitch_predicate * > &	get_predicates_for_bb (basic_block bb)
static void	set_predicates_for_bb (basic_block bb, vec< unswitch_predicate * > predicates)
static unsigned	estimate_loop_insns (class loop *loop)
static unsigned	init_loop_unswitch_info (class loop *&loop, unswitch_predicate *&hottest, basic_block &hottest_bb)
unsigned int	tree_ssa_unswitch_loops (function *fun)
static bool	is_maybe_undefined (const tree name, gimple *stmt, class loop *loop)
static void	merge_last (predicate_vector &predicate_path)
static void	add_predicate_to_path (predicate_vector &predicate_path, unswitch_predicate *predicate, bool true_edge)
static bool	find_range_for_lhs (predicate_vector &predicate_path, tree lhs, int_range_max &range)
static tree	evaluate_control_stmt_using_entry_checks (gimple *stmt, predicate_vector &predicate_path, int ignored_edge_flag, hash_set< edge > *ignored_edges)
static bool	simplify_loop_version (class loop *loop, predicate_vector &predicate_path, int ignored_edge_flag, bitmap handled)
template<typename VisitOp>
static void	evaluate_bbs (class loop *loop, predicate_vector *predicate_path, int ignored_edge_flag, VisitOp visit)
static void	evaluate_loop_insns_for_predicate (class loop *loop, predicate_vector &predicate_path, unswitch_predicate *predicate, int ignored_edge_flag, unsigned *true_size, unsigned *false_size)
gimple_opt_pass *	make_pass_tree_unswitch (gcc::context *ctxt)

Variables
static gimple_ranger *	ranger = NULL
static vec< vec< unswitch_predicate * > > *	bb_predicates

Typedef Documentation

predicate_vector

typedef vec<std::pair<unswitch_predicate *, bool> > predicate_vector

The type represents a predicate path leading to a basic block.   

Function Documentation

add_predicate_to_path()

void add_predicate_to_path ( predicate_vector & predicate_path, unswitch_predicate * predicate, bool true_edge )

static

Add PREDICATE to PREDICATE_PATH on TRUE_EDGE.   

References add_predicate_to_path(), and merge_last().

Referenced by add_predicate_to_path(), evaluate_loop_insns_for_predicate(), and tree_unswitch_single_loop().

check_exit_phi()

bool check_exit_phi ( class loop * loop )

static

Return true if phi argument for exit edge can be used
for edge around loop.   

References CDI_DOMINATORS, check_exit_phi(), dominated_by_p(), flow_bb_inside_loop_p(), gimple_bb(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), basic_block_def::loop_father, loop_preheader_edge(), PHI_ARG_DEF_FROM_EDGE, single_exit(), SSA_NAME_DEF_STMT, TREE_CODE, and virtual_operand_p().

Referenced by check_exit_phi(), and tree_unswitch_outer_loop().

clean_up_after_unswitching()

void clean_up_after_unswitching ( int ignored_edge_flag )

static

Remove all dead cases from switches that are unswitched.   

References CASE_LABEL, CDI_DOMINATORS, cfun, clean_up_after_unswitching(), CONSTANT_CLASS_P, find_edge(), FOR_EACH_BB_FN, FOR_EACH_EDGE, free_dominance_info(), gimple_bb(), gimple_switch_default_label(), gimple_switch_index(), gimple_switch_label(), gimple_switch_num_labels(), gimple_switch_set_label(), gimple_switch_set_num_labels(), gsi_last_bb(), i, label_to_block(), NULL, remove_edge(), safe_dyn_cast(), and basic_block_def::succs.

Referenced by clean_up_after_unswitching(), and tree_ssa_unswitch_loops().

empty_bb_without_guard_p()

bool empty_bb_without_guard_p ( class loop * loop, basic_block bb, vec< gimple * > & dbg_to_reset )

static

Returns true if
1) no statement in BB has side effects
2) assuming that edge GUARD is always taken, all definitions in BB
   are noy used outside of the loop.
KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
PROCESSED is a set of ssa names for that we already tested whether they
are invariant or not.  Uses in debug stmts outside of the loop are
pushed to DBG_TO_RESET.   

References CDI_DOMINATORS, dominated_by_p(), empty_bb_without_guard_p(), FOR_EACH_SSA_TREE_OPERAND, gimple_has_side_effects(), gimple_vdef(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), is_gimple_debug(), PHI_RESULT, single_exit(), SSA_OP_DEF, used_outside_loop_p(), and virtual_operand_p().

Referenced by empty_bb_without_guard_p(), and find_loop_guard().

estimate_loop_insns()

unsigned estimate_loop_insns ( class loop * loop )

static

Estimate number of instructions in LOOP using eni_size_weights.   

References eni_size_weights, estimate_loop_insns(), estimate_num_insns(), free(), get_loop_body(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), i, and loop::num_nodes.

Referenced by estimate_loop_insns(), and init_loop_unswitch_info().

evaluate_bbs()

template<typename VisitOp>

void evaluate_bbs ( class loop * loop, predicate_vector * predicate_path, int ignored_edge_flag, VisitOp visit )

static

Evaluate reachable blocks in LOOP and call VISIT on them, aborting the
DFS walk if VISIT returns true.  When PREDICATE_PATH is specified then
take into account that when computing reachability, otherwise just
look at the simplified state and IGNORED_EDGE_FLAG.   

References cfun, hash_set< KeyId, Lazy, Traits >::contains(), evaluate_bbs(), evaluate_control_stmt_using_entry_checks(), basic_block_def::flags, flow_bb_inside_loop_p(), FOR_EACH_EDGE, get_predicates_for_bb(), gimple_cond_false_p(), gimple_cond_true_p(), gsi_last_bb(), loop::header, integer_nonzerop(), loop::num_nodes, safe_dyn_cast(), basic_block_def::succs, and visit.

Referenced by evaluate_bbs(), evaluate_loop_insns_for_predicate(), and tree_unswitch_single_loop().

evaluate_control_stmt_using_entry_checks()

tree evaluate_control_stmt_using_entry_checks ( gimple * stmt, predicate_vector & predicate_path, int ignored_edge_flag, hash_set< edge > * ignored_edges )

static

Simplifies STMT using the predicate we unswitched on which is the last
in PREDICATE_PATH.  For switch statements add newly unreachable edges
to IGNORED_EDGES (but do not set IGNORED_EDGE_FLAG on them).   

References hash_set< KeyId, Lazy, Traits >::add(), boolean_false_node, boolean_true_node, CASE_LABEL, CASE_LOW, cfun, unswitch_predicate::condition, dyn_cast(), gimple_outgoing_range::edge_range_p(), evaluate_control_stmt_using_entry_checks(), find_edge(), find_range_for_lhs(), fold_range(), get_global_range_query(), gimple_bb(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_switch_index(), gimple_switch_label(), gimple_switch_num_labels(), range_query::gori(), i, label_to_block(), unswitch_predicate::lhs, NULL, NULL_TREE, operand_equal_p(), r, ranger, irange::supports_p(), TREE_CODE, TREE_CONSTANT, TREE_OPERAND, and TREE_TYPE.

Referenced by evaluate_bbs(), evaluate_control_stmt_using_entry_checks(), and simplify_loop_version().

evaluate_loop_insns_for_predicate()

void evaluate_loop_insns_for_predicate ( class loop * loop, predicate_vector & predicate_path, unswitch_predicate * predicate, int ignored_edge_flag, unsigned * true_size, unsigned * false_size )

static

Evaluate how many instruction will we have if we unswitch LOOP (with BBS)
based on PREDICATE predicate (using PREDICATE_PATH).  Store the
result in TRUE_SIZE and FALSE_SIZE.   

References add_predicate_to_path(), evaluate_bbs(), and evaluate_loop_insns_for_predicate().

Referenced by evaluate_loop_insns_for_predicate(), and tree_unswitch_single_loop().

find_loop_guard()

edge find_loop_guard ( class loop * loop, vec< gimple * > & dbg_to_reset )

static

Checks if the body of the LOOP is within an invariant guard.  If this
is the case, returns the edge that jumps over the real body of the loop,
otherwise returns NULL.   

References CDI_DOMINATORS, dominated_by_p(), dump_enabled_p(), dump_printf_loc(), empty_bb_without_guard_p(), end(), extract_true_false_edges_from_block(), find_loop_guard(), find_loop_location(), basic_block_def::flags, flow_bb_inside_loop_p(), FOR_EACH_SSA_TREE_OPERAND, free(), get_loop_body(), gimple_bb(), gimple_cond_false_p(), gimple_cond_true_p(), gsi_last_bb(), loop::header, i, basic_block_def::index, loop::inner, just_once_each_iteration_p(), loop::latch, basic_block_def::loop_father, MSG_MISSED_OPTIMIZATION, MSG_NOTE, loop::next, NULL, loop::num, loop::num_nodes, safe_dyn_cast(), single_succ(), single_succ_p(), SSA_NAME_DEF_STMT, and SSA_OP_USE.

Referenced by find_loop_guard(), and tree_unswitch_outer_loop().

find_range_for_lhs()

bool find_range_for_lhs ( predicate_vector & predicate_path, tree lhs, int_range_max & range )

static

References find_range_for_lhs(), i, operand_equal_p(), and vrange::undefined_p().

Referenced by evaluate_control_stmt_using_entry_checks(), and find_range_for_lhs().

find_unswitching_predicates_for_bb()

void find_unswitching_predicates_for_bb ( basic_block bb, class loop * loop, class loop *& outer_loop, vec< unswitch_predicate * > & candidates, unswitch_predicate *& hottest, basic_block & hottest_bb )

static

Checks whether we can unswitch LOOP on condition at end of BB -- one of its
basic blocks (for what it means see comments below).
All candidates all filled to the provided vector CANDIDATES.
OUTER_LOOP is updated to the innermost loop all found candidates are
invariant in.   

References boolean_type_node, CASE_HIGH, CASE_LABEL, CASE_LOW, cfun, unswitch_predicate::count, EDGE_COUNT, EDGE_SUCC, find_edge(), find_unswitching_predicates_for_bb(), flow_bb_inside_loop_p(), fold_build2, fold_convert, FOR_EACH_EDGE, FOR_EACH_SSA_TREE_OPERAND, gimple_bb(), gimple_cond_false_p(), gimple_cond_lhs(), gimple_cond_true_p(), gimple_range_ssa_p(), gimple_switch_index(), gimple_switch_label(), gimple_switch_num_labels(), gsi_last_bb(), i, is_maybe_undefined(), label_to_block(), loop_depth(), NULL, NULL_TREE, safe_dyn_cast(), irange::set(), SSA_NAME_DEF_STMT, SSA_OP_USE, superloop_at_depth(), wi::to_wide(), TREE_CODE, TREE_TYPE, and unswitch_predicate::unswitch_predicate().

Referenced by find_unswitching_predicates_for_bb(), and init_loop_unswitch_info().

get_predicates_for_bb()

vec< unswitch_predicate * > & get_predicates_for_bb ( basic_block bb )

static

Return vector of predicates that belong to a basic block.   

References bb_predicates, get_predicates_for_bb(), gimple_uid(), last_nondebug_stmt(), and NULL.

Referenced by evaluate_bbs(), get_predicates_for_bb(), simplify_loop_version(), and tree_unswitch_single_loop().

get_vop_from_header()

tree get_vop_from_header ( class loop * loop )

static

Return argument for loop preheader edge in header virtual phi if any.   

References get_vop_from_header(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), loop::header, loop_preheader_edge(), NULL_TREE, PHI_ARG_DEF_FROM_EDGE, and virtual_operand_p().

Referenced by get_vop_from_header(), and hoist_guard().

hoist_guard()

void hoist_guard ( class loop * loop, edge guard )

static

Move the check of GUARD outside of LOOP.   

References add_phi_arg(), profile_probability::always(), as_a(), CDI_DOMINATORS, basic_block_def::count, dominated_by_p(), dump_enabled_p(), dump_file, dump_flags, dump_printf_loc(), extract_true_false_edges_from_block(), find_loop_location(), flow_bb_inside_loop_p(), free(), gcc_assert, get_immediate_dominator(), get_loop_body(), get_vop_from_header(), gimple_build_cond(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_make_false(), gimple_cond_make_true(), gimple_cond_rhs(), gimple_phi_result(), gsi_end_p(), gsi_insert_after(), gsi_last_bb(), GSI_NEW_STMT, gsi_next(), gsi_start_phis(), gsi_stmt(), hoist_guard(), i, basic_block_def::index, last_nondebug_stmt(), loop_preheader_edge(), make_edge(), MSG_NOTE, MSG_OPTIMIZED_LOCATIONS, profile_probability::never(), profile_count::nonzero_p(), NULL_TREE, loop::num_nodes, PHI_ARG_DEF_FROM_EDGE, scale_bbs_frequencies(), set_immediate_dominator(), single_exit(), split_block(), TDF_DETAILS, UNKNOWN_LOCATION, update_stmt(), and virtual_operand_p().

Referenced by hoist_guard(), and tree_unswitch_outer_loop().

init_loop_unswitch_info()

unsigned init_loop_unswitch_info ( class loop *& loop, unswitch_predicate *& hottest, basic_block & hottest_bb )

static

Initialize LOOP information reused during the unswitching pass.
Return total number of instructions in the loop.  Adjusts LOOP to
the outermost loop all candidates are invariant in.   

References basic_block_def::aux, dump_enabled_p(), dump_printf_loc(), eni_size_weights, estimate_loop_insns(), estimate_num_insns(), find_loop_location(), find_unswitching_predicates_for_bb(), flow_bb_inside_loop_p(), free(), get_loop_body(), gimple_set_uid(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), i, init_loop_unswitch_info(), loop::inner, last_nondebug_stmt(), loop_outer(), MSG_NOTE, loop::next, NULL, loop::num, loop::num_nodes, and set_predicates_for_bb().

Referenced by init_loop_unswitch_info(), and tree_ssa_unswitch_loops().

is_maybe_undefined()

bool is_maybe_undefined ( const tree name, gimple * stmt, class loop * loop )

static

Return TRUE if an SSA_NAME maybe undefined and is therefore
unsuitable for unswitching.  STMT is the statement we are
considering for unswitching and LOOP is the loop it appears in.   

References gimple_bb(), loop::header, is_maybe_undefined(), and ssa_name_maybe_undef_p().

Referenced by find_unswitching_predicates_for_bb(), and is_maybe_undefined().

make_pass_tree_unswitch()

gimple_opt_pass * make_pass_tree_unswitch

(

gcc::context *

ctxt

)

References make_pass_tree_unswitch().

Referenced by make_pass_early_tree_profile(), and make_pass_tree_unswitch().

merge_last()

void merge_last ( predicate_vector & predicate_path )

static

Merge ranges for the last item of PREDICATE_PATH with a predicate
that shared the same LHS.   

References i, irange::intersect(), unswitch_predicate::lhs, merge_last(), unswitch_predicate::merged_false_range, unswitch_predicate::merged_true_range, and operand_equal_p().

Referenced by add_predicate_to_path(), and merge_last().

set_predicates_for_bb()

void set_predicates_for_bb ( basic_block bb, vec< unswitch_predicate * > predicates )

static

Save predicates that belong to a basic block.   

References bb_predicates, gimple_set_uid(), last_nondebug_stmt(), and set_predicates_for_bb().

Referenced by init_loop_unswitch_info(), and set_predicates_for_bb().

simplify_loop_version()

bool simplify_loop_version ( class loop * loop, predicate_vector & predicate_path, int ignored_edge_flag, bitmap handled )

static

Simplify LOOP based on PREDICATE_PATH where dead edges are properly
marked.   

References bitmap_set_bit, boolean_false_node, boolean_true_node, hash_set< KeyId, Lazy, Traits >::contains(), dyn_cast(), EDGE_SUCC, evaluate_control_stmt_using_entry_checks(), FOR_EACH_EDGE, free(), gcc_assert, get_loop_body(), get_predicates_for_bb(), gimple_cond_set_condition_from_tree(), gimple_switch_set_index(), gsi_last_bb(), i, integer_nonzerop(), loop::num, loop::num_nodes, simplify_loop_version(), and update_stmt().

Referenced by simplify_loop_version(), and tree_unswitch_single_loop().

tree_ssa_unswitch_loops()

unsigned int tree_ssa_unswitch_loops

(

function *

fun

)

Main entry point.  Perform loop unswitching on all suitable loops.   

References bb_predicates, cfun, clean_up_after_unswitching(), cleanup_tree_cfg(), clear_aux_for_blocks(), disable_ranger(), dump_enabled_p(), dump_printf_loc(), enable_ranger(), estimated_loop_iterations_int(), find_loop_location(), init_loop_unswitch_info(), loop::inner, LI_FROM_INNERMOST, LI_ONLY_INNERMOST, likely_max_loop_iterations_int(), loop_invariant_motion_in_fun(), mark_ssa_maybe_undefs(), MSG_NOTE, NULL, optimize_loop_for_size_p(), unswitch_predicate::predicates, ranger, tree_ssa_unswitch_loops(), tree_unswitch_outer_loop(), and tree_unswitch_single_loop().

Referenced by tree_ssa_unswitch_loops().

tree_unswitch_loop()

class loop * tree_unswitch_loop ( class loop * loop, edge edge_true, tree cond )

static

Unswitch a LOOP w.r. to given EDGE_TRUE.  We only support unswitching of
innermost loops.  COND is the condition determining which loop is entered;
the new loop is entered if COND is true.  Returns NULL if impossible, new
loop otherwise.   

References EDGE_COUNT, flow_bb_inside_loop_p(), gcc_assert, profile_probability::invert(), loop_version(), NULL, tree_unswitch_loop(), and unshare_expr().

Referenced by tree_unswitch_loop(), and tree_unswitch_single_loop().

tree_unswitch_outer_loop()

bool tree_unswitch_outer_loop ( class loop * loop )

static

Unswitch outer loops by hoisting invariant guard on
inner loop without code duplication.   

References check_exit_phi(), dump_enabled_p(), dump_printf_loc(), estimated_loop_iterations_int(), find_loop_guard(), find_loop_location(), gcc_assert, gimple_debug_bind_reset_value(), hoist_guard(), loop::inner, likely_max_loop_iterations_int(), MSG_MISSED_OPTIMIZATION, loop::next, single_exit(), tree_unswitch_outer_loop(), and update_stmt().

Referenced by tree_ssa_unswitch_loops(), and tree_unswitch_outer_loop().

tree_unswitch_single_loop()

bool tree_unswitch_single_loop ( class loop * loop, dump_user_location_t loc, predicate_vector & predicate_path, unsigned loop_size, unsigned & budget, int ignored_edge_flag, bitmap handled, unswitch_predicate * hottest, basic_block hottest_bb )

static

Unswitch single LOOP.  PREDICATE_PATH contains so far used predicates
for unswitching.  BUDGET is number of instruction for which we can increase
the loop and is updated when unswitching occurs.  If HOTTEST is not
NULL then pick this candidate as the one to unswitch on.   

References add_predicate_to_path(), basic_block_def::aux, loop::aux, BITMAP_ALLOC, bitmap_bit_p, bitmap_copy(), BITMAP_FREE, bitmap_set_bit, dbg_cnt(), dump_enabled_p(), dump_printf_loc(), EDGE_SUCC, evaluate_bbs(), evaluate_loop_insns_for_predicate(), free(), free_original_copy_tables(), get_bb_original(), get_loop_body(), get_predicates_for_bb(), i, initialize_original_copy_tables(), loop::inner, MSG_NOTE, MSG_OPTIMIZED_LOCATIONS, NULL, loop::num, loop::num_nodes, simplify_loop_version(), TODO_update_ssa_no_phi, tree_unswitch_loop(), tree_unswitch_single_loop(), and update_ssa().

Referenced by tree_ssa_unswitch_loops(), and tree_unswitch_single_loop().

used_outside_loop_p()

bool used_outside_loop_p ( class loop * loop, tree name, vec< gimple * > & dbg_to_reset )

static

Return true if NAME is used outside of LOOP.  Pushes debug stmts that
have such uses to DBG_TO_RESET but do not consider such uses.   

References flow_bb_inside_loop_p(), FOR_EACH_IMM_USE_FAST, gimple_bb(), is_gimple_debug(), USE_STMT, and used_outside_loop_p().

Referenced by empty_bb_without_guard_p(), and used_outside_loop_p().

Variable Documentation

bb_predicates

vec<vec<unswitch_predicate *> >* bb_predicates

static

Cache storage for unswitch_predicate belonging to a basic block.   

Referenced by get_predicates_for_bb(), set_predicates_for_bb(), and tree_ssa_unswitch_loops().

ranger

gimple_ranger* ranger = NULL

static

Ranger instance used in the pass.   

Referenced by evaluate_control_stmt_using_entry_checks(), and tree_ssa_unswitch_loops().