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 "gimplify.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 "tree-pretty-print.h"
#include "gimple-range.h"
#include "dbgcnt.h"
#include "cfganal.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	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()

static 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 merge_last().

Referenced by evaluate_loop_insns_for_predicate(), and tree_unswitch_single_loop().

check_exit_phi()

static 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, 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 tree_unswitch_outer_loop().

clean_up_after_unswitching()

static 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, 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 tree_ssa_unswitch_loops().

empty_bb_without_guard_p()

static 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(), 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 find_loop_guard().

evaluate_bbs()

template<typename VisitOp >

static 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_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(), is_empty(), last, loop::num_nodes, safe_dyn_cast(), basic_block_def::succs, visit, and worklist.

Referenced by evaluate_loop_insns_for_predicate(), and tree_unswitch_single_loop().

evaluate_control_stmt_using_entry_checks()

static 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, dyn_cast(), gimple_outgoing_range::edge_range_p(), find_edge(), find_range_for_lhs(), 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, irange::intersect(), label_to_block(), last_predicate, NULL, NULL_TREE, operand_equal_p(), r, ranger, irange::supports_p(), TREE_CODE, TREE_CONSTANT, TREE_OPERAND, TREE_TYPE, and irange::zero_p().

Referenced by evaluate_bbs(), and simplify_loop_version().

evaluate_loop_insns_for_predicate()

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 )

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(), and evaluate_bbs().

Referenced by tree_unswitch_single_loop().

find_loop_guard()

static 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_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(), header, 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 tree_unswitch_outer_loop().

find_range_for_lhs()

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

static

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

Referenced by evaluate_control_stmt_using_entry_checks().

find_unswitching_predicates_for_bb()

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

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, candidates, CASE_HIGH, CASE_LABEL, CASE_LOW, cfun, cmp1(), unswitch_predicate::count, EDGE_COUNT, EDGE_SUCC, find_edge(), 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(), last, 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, and TREE_TYPE.

Referenced by init_loop_unswitch_info().

get_predicates_for_bb()

static vec< unswitch_predicate * > & get_predicates_for_bb ( basic_block bb )

static

Return vector of predicates that belong to a basic block.   

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

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

get_vop_from_header()

static tree get_vop_from_header ( class loop * loop )

static

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

References 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 hoist_guard().

hoist_guard()

static 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_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(), 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(), UNKNOWN_LOCATION, update_stmt(), and virtual_operand_p().

Referenced by tree_unswitch_outer_loop().

init_loop_unswitch_info()

static 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, candidates, eni_size_weights, estimate_num_insns(), 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, loop::inner, insns, last, last_nondebug_stmt(), loop_outer(), loop::next, NULL, loop::num, loop::num_nodes, and set_predicates_for_bb().

Referenced by tree_ssa_unswitch_loops().

is_maybe_undefined()

static 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, and ssa_name_maybe_undef_p().

Referenced by find_unswitching_predicates_for_bb().

make_pass_tree_unswitch()

gimple_opt_pass * make_pass_tree_unswitch

(

gcc::context *

ctxt

)

merge_last()

static 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, last_predicate, and operand_equal_p().

Referenced by add_predicate_to_path().

set_predicates_for_bb()

static 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(), and last_nondebug_stmt().

Referenced by init_loop_unswitch_info().

simplify_loop_version()

static 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, changed, 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, and update_stmt().

Referenced by 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, clean_up_after_unswitching(), 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(), mark_ssa_maybe_undefs(), MSG_NOTE, NULL, optimize_loop_for_size_p(), unswitch_predicate::predicates, ranger, TODO_cleanup_cfg, tree_unswitch_outer_loop(), and tree_unswitch_single_loop().

tree_unswitch_loop()

static 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, and unshare_expr().

Referenced by tree_unswitch_single_loop().

tree_unswitch_outer_loop()

static bool tree_unswitch_outer_loop ( class loop * loop )

static

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

References changed, 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(), and update_stmt().

Referenced by tree_ssa_unswitch_loops().

tree_unswitch_single_loop()

static 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, changed, 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()

static 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(), and USE_STMT.

Referenced by empty_bb_without_guard_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 debug_seed_ranger(), dom_opt_dom_walker::dom_opt_dom_walker(), dump_ranger(), dump_ranger(), evaluate_control_stmt_using_entry_checks(), execute_ranger_vrp(), get_range_query(), loop_static_stmt_p(), path_range_query::path_range_query(), path_range_query::path_range_query(), should_duplicate_loop_header_p(), static_loop_exit(), tree_ssa_unswitch_loops(), and vect_recog_divmod_pattern().