ipa-split.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "cfghooks.h"
#include "alloc-pool.h"
#include "tree-pass.h"
#include "ssa.h"
#include "cgraph.h"
#include "diagnostic.h"
#include "fold-const.h"
#include "cfganal.h"
#include "calls.h"
#include "gimplify.h"
#include "gimple-iterator.h"
#include "gimplify-me.h"
#include "gimple-walk.h"
#include "symbol-summary.h"
#include "sreal.h"
#include "ipa-cp.h"
#include "ipa-prop.h"
#include "tree-cfg.h"
#include "tree-into-ssa.h"
#include "tree-dfa.h"
#include "tree-inline.h"
#include "gimple-pretty-print.h"
#include "ipa-fnsummary.h"
#include "cfgloop.h"
#include "attribs.h"
#include "ipa-strub.h"

Include dependency graph for ipa-split.cc:

Data Structures
class	split_bb_info
class	split_point
class	stack_entry

Functions
static tree	find_retval (basic_block return_bb)
static bool	test_nonssa_use (gimple *, tree t, tree, void *data)
static void	dump_split_point (FILE *file, class split_point *current)
static bool	verify_non_ssa_vars (class split_point *current, bitmap non_ssa_vars, basic_block return_bb)
static void	check_forbidden_calls (gimple *stmt)
static bool	dominated_by_forbidden (basic_block bb)
static bool	split_part_set_ssa_name_p (tree val, class split_point *current, basic_block return_bb)
static void	consider_split (class split_point *current, bitmap non_ssa_vars, basic_block return_bb)
static basic_block	find_return_bb (void)
static bool	mark_nonssa_use (gimple *, tree t, tree, void *data)
static bool	visit_bb (basic_block bb, basic_block return_bb, bitmap set_ssa_names, bitmap used_ssa_names, bitmap non_ssa_vars)
static void	find_split_points (basic_block return_bb, sreal overall_time, int overall_size)
static void	split_function (basic_block return_bb, class split_point *split_point, bool add_tsan_func_exit)
static unsigned int	execute_split_functions (void)
gimple_opt_pass *	make_pass_split_functions (gcc::context *ctxt)
static unsigned int	execute_feedback_split_functions (void)
gimple_opt_pass *	make_pass_feedback_split_functions (gcc::context *ctxt)

Variables
static vec< split_bb_info >	bb_info_vec
class split_point	best_split_point
static bitmap	forbidden_dominators

Function Documentation

check_forbidden_calls()

static void check_forbidden_calls ( gimple * stmt )

static

If STMT is a call, check the callee against a list of forbidden
predicate functions.  If a match is found, look for uses of the
call result in condition statements that compare against zero.
For each such use, find the block targeted by the condition
statement for the nonzero result, and set the bit for this block
in the forbidden dominators bitmap.  The purpose of this is to avoid
selecting a split point where we are likely to lose the chance
to optimize away an unused function call.   

References bitmap_set_bit, extract_true_false_edges_from_block(), FOR_EACH_IMM_USE_FAST, forbidden_dominators, ggc_alloc(), gimple_bb(), gimple_call_builtin_p(), gimple_call_lhs(), gimple_cond_code(), gimple_cond_rhs(), integer_zerop(), TREE_CODE, and USE_STMT.

Referenced by execute_split_functions().

consider_split()

static void consider_split ( class split_point * current, bitmap non_ssa_vars, basic_block return_bb )

static

We found an split_point CURRENT.  NON_SSA_VARS is bitmap of all non ssa
variables used and RETURN_BB is return basic block.
See if we can split function here.   

References best_split_point, BITMAP_ALLOC, bitmap_bit_p, bitmap_copy(), bitmap_count_bits(), bitmap_empty_p(), BITMAP_FREE, eni_weights::call_cost, cfun, count, split_point::count, current_function_decl, DECL_ARGUMENTS, DECL_BY_REFERENCE, DECL_CHAIN, DECL_DECLARED_INLINE_P, DECL_ONE_ONLY, DECL_RESULT, DECL_UID, dominated_by_forbidden(), profile_count::dump(), dump_file, dump_flags, dump_split_point(), eni_size_weights, split_point::entry_bb, ENTRY_BLOCK_PTR_FOR_FN, estimate_move_cost(), EXIT_BLOCK_PTR_FOR_FN, find_retval(), FOR_EACH_EDGE, forbidden_dominators, ggc_alloc(), gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_num_args(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), split_point::header_size, i, is_gimple_min_invariant(), is_gimple_reg(), NULL, gphi_iterator::phi(), basic_block_def::preds, PROFILE_READ, profile_status_for_fn, split_point::split_bbs, split_point::split_part_set_retval, split_part_set_ssa_name_p(), split_point::split_size, ssa_default_def(), SSA_NAME_DEF_STMT, SSA_NAME_VAR, SSA_NAME_VERSION, split_point::ssa_names_to_pass, TDF_DETAILS, TREE_CODE, TREE_TYPE, VAR_P, verify_non_ssa_vars(), virtual_operand_p(), VOID_TYPE_P, and profile_count::zero().

Referenced by find_split_points().

dominated_by_forbidden()

static bool dominated_by_forbidden ( basic_block bb )

static

If BB is dominated by any block in the forbidden dominators set,
return TRUE; else FALSE.   

References BASIC_BLOCK_FOR_FN, CDI_DOMINATORS, cfun, dominated_by_p(), EXECUTE_IF_SET_IN_BITMAP, forbidden_dominators, and ggc_alloc().

Referenced by consider_split().

dump_split_point()

static void dump_split_point ( FILE * file, class split_point * current )

static

Dump split point CURRENT.   

References dump_bitmap(), split_point::entry_bb, ggc_alloc(), split_point::header_size, split_point::header_time, basic_block_def::index, split_point::split_bbs, split_point::split_size, split_point::split_time, split_point::ssa_names_to_pass, and sreal::to_double().

Referenced by consider_split(), and split_function().

execute_feedback_split_functions()

static unsigned int execute_feedback_split_functions ( void )

static

Execute function splitting pass.   

References execute_split_functions(), ggc_alloc(), and TODO_rebuild_cgraph_edges.

execute_split_functions()

static unsigned int execute_split_functions ( void )

static

Execute function splitting pass.   

References symtab_node::address_taken, bb_info_vec, best_split_point, BITMAP_ALLOC, BITMAP_FREE, calculate_dominance_info(), cgraph_node::callers, CDI_DOMINATORS, cfun, check_forbidden_calls(), basic_block_def::count, count, current_function_decl, symtab_node::decl, DECL_ATTRIBUTES, DECL_DECLARED_INLINE_P, DECL_DISREGARD_INLINE_LIMITS, DECL_NAME, DECL_STRUCT_FUNCTION, dump_file, dump_flags, ECF_MALLOC, ECF_NORETURN, ECF_RETURNS_TWICE, eni_size_weights, eni_time_weights, ENTRY_BLOCK_PTR_FOR_FN, estimate_num_insns(), symtab_node::externally_visible, find_edge(), find_return_bb(), find_split_points(), flags_from_decl_or_type(), FOR_EACH_BB_FN, forbidden_dominators, cgraph_node::frequency, cgraph_node::get(), ggc_alloc(), gimple_call_internal_p(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), symtab_node::has_aliases_p(), basic_block_def::index, ipa_fn_summaries, last_basic_block_for_fn, cgraph_node::local, lookup_attribute(), MAIN_NAME_P, mark_dfs_back_edges(), cgraph_edge::next_caller, NODE_FREQUENCY_UNLIKELY_EXECUTED, NULL, overall_size, print_gimple_stmt(), PROFILE_READ, profile_status_for_fn, SANITIZE_THREAD, split_point::split_bbs, split_function(), split_point::ssa_names_to_pass, strub_splittable_p(), TDF_DETAILS, sreal::to_double(), profile_count::to_sreal_scale(), todo, TODO_cleanup_cfg, TODO_update_ssa, and tree_versionable_function_p().

Referenced by execute_feedback_split_functions().

find_return_bb()

static basic_block find_return_bb ( void )

static

Return basic block containing RETURN statement.  We allow basic blocks
of the form:
<retval> = tmp_var;
return <retval>
but return_bb cannot be more complex than this (except for
-fsanitize=thread we allow TSAN_FUNC_EXIT () internal call in there).
If nothing is found, return the exit block.

When there are multiple RETURN statement, chose one with return value,
since that one is more likely shared by multiple code paths.

Return BB is special, because for function splitting it is the only
basic block that is duplicated in between header and split part of the
function.

TODO: We might support multiple return blocks.   

References auto_var_in_fn_p(), cfun, current_function_decl, EXIT_BLOCK_PTR_FOR_FN, ggc_alloc(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_single_p(), gimple_call_internal_p(), gimple_clobber_p(), gimple_return_retval(), gsi_end_p(), gsi_last_bb(), gsi_prev(), gsi_stmt(), is_gimple_debug(), is_gimple_min_invariant(), NULL_TREE, SANITIZE_THREAD, single_pred_edge(), and single_pred_p().

Referenced by execute_split_functions().

find_retval()

static tree find_retval ( basic_block return_bb )

static

Given return basic block RETURN_BB, see where return value is really
stored.   

References ggc_alloc(), gimple_assign_rhs1(), gimple_clobber_p(), gimple_return_retval(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), and NULL.

Referenced by consider_split(), and split_function().

find_split_points()

static void find_split_points ( basic_block return_bb, sreal overall_time, int overall_size )

static

Find all articulations and call consider_split on them.
OVERALL_TIME and OVERALL_SIZE is time and size of the function.

We perform basic algorithm for finding an articulation in a graph
created from CFG by considering it to be an unoriented graph.

The articulation is discovered via DFS walk. We collect earliest
basic block on stack that is reachable via backward edge.  Articulation
is any basic block such that there is no backward edge bypassing it.
To reduce stack usage we maintain heap allocated stack in STACK vector.
AUX pointer of BB is set to index it appears in the stack or -1 once
it is visited and popped off the stack.

The algorithm finds articulation after visiting the whole component
reachable by it.  This makes it convenient to collect information about
the component used by consider_split.   

References basic_block_def::aux, stack_entry::bb, bb_info_vec, stack_entry::bbs_visited, BITMAP_ALLOC, bitmap_and_compl(), BITMAP_FREE, bitmap_ior_into(), bitmap_set_bit, stack_entry::can_split, cfun, consider_split(), dump_file, dump_flags, stack_entry::earliest, EDGE_COUNT, stack_entry::edge_num, EDGE_PRED, EDGE_SUCC, split_point::entry_bb, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, FOR_EACH_BB_FN, ggc_alloc(), split_point::header_size, split_point::header_time, basic_block_def::index, INT_MAX, stack_entry::non_ssa_vars, NULL, overall_size, stack_entry::overall_size, stack_entry::overall_time, basic_block_def::preds, stack_entry::set_ssa_names, split_point::split_bbs, split_point::split_size, split_point::split_time, split_point::ssa_names_to_pass, basic_block_def::succs, TDF_DETAILS, stack_entry::used_ssa_names, visit_bb(), and vNULL.

Referenced by execute_split_functions().

make_pass_feedback_split_functions()

gimple_opt_pass * make_pass_feedback_split_functions

(

gcc::context *

ctxt

)

References ggc_alloc().

make_pass_split_functions()

gimple_opt_pass * make_pass_split_functions

(

gcc::context *

ctxt

)

References ggc_alloc().

mark_nonssa_use()

static bool mark_nonssa_use ( gimple * , tree t, tree , void * data )

static

Callback for walk_stmt_load_store_addr_ops.  If T is non-SSA automatic
variable, mark it as used in bitmap passed via DATA.
Return true when access to T prevents splitting the function.   

References auto_var_in_fn_p(), bitmap_bit_p, bitmap_set_bit, current_function_decl, DECL_BY_REFERENCE, DECL_RESULT, DECL_UID, dump_file, dump_flags, FORCED_LABEL, get_base_address(), ggc_alloc(), INDIRECT_REF_P, is_gimple_reg(), SSA_NAME_VAR, TDF_DETAILS, TREE_CODE, TREE_OPERAND, and VAR_P.

Referenced by visit_bb().

split_function()

static void split_function ( basic_block return_bb, class split_point * split_point, bool add_tsan_func_exit )

static

Split function at SPLIT_POINT.   

References add_bb_to_loop(), add_phi_arg(), symtab_node::add_to_same_comdat_group(), aggregate_value_p(), BITMAP_ALLOC, bitmap_bit_p, bitmap_empty_p(), BITMAP_FREE, bitmap_set_bit, build_simple_mem_ref, CDI_DOMINATORS, CDI_POST_DOMINATORS, cfun, compute_fn_summary(), copy_ssa_name(), split_point::count, create_basic_block(), create_tmp_reg(), current_function_decl, current_loops, symtab_node::decl, DECL_ARG_TYPE, DECL_ARGUMENTS, DECL_BY_REFERENCE, DECL_CHAIN, decl_debug_args_lookup(), DECL_INITIAL, DECL_NO_INLINE_WARNING_P, DECL_ORIGIN, DECL_RESULT, dump_file, dump_flags, dump_function_to_file(), dump_split_point(), split_point::entry_bb, EXIT_BLOCK_PTR_FOR_FN, find_retval(), fndecl_built_in_p(), fold_convert, FOR_EACH_EDGE, FOR_EACH_SSA_TREE_OPERAND, FOR_EACH_SSA_USE_OPERAND, FOR_EACH_VEC_ELT, force_gimple_operand_gsi(), free_dominance_info(), g, cgraph_node::get(), get_or_create_ssa_default_def(), ggc_alloc(), gimple_assign_lhs(), gimple_assign_set_rhs1(), gimple_bb(), gimple_build_assign(), gimple_build_call_internal(), gimple_build_call_vec(), gimple_build_debug_bind(), gimple_build_return(), gimple_call_set_lhs(), gimple_call_set_return_slot_opt(), gimple_clobber_p(), gimple_debug_bind_reset_value(), gimple_phi_result(), gimple_return_set_retval(), gimple_set_block(), gimple_set_vuse(), gimple_vdef(), gimple_vuse(), GSI_CONTINUE_LINKING, gsi_end_p(), gsi_insert_after(), gsi_last_bb(), GSI_NEW_STMT, gsi_next(), gsi_remove(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), i, basic_block_def::index, IPA_PARAM_OP_COPY, is_gimple_debug(), is_gimple_reg(), is_gimple_reg_type(), is_gimple_val(), make_single_succ_edge(), make_ssa_name(), mark_virtual_phi_result_for_renaming(), MAY_HAVE_DEBUG_BIND_STMTS, NOT_BUILT_IN, NULL, NULL_TREE, gphi_iterator::phi(), cgraph_edge::rebuild_edges(), redirect_edge_and_branch(), remove_edge(), remove_phi_node(), set_decl_built_in_function(), SET_USE, split_point::split_bbs, split_block(), cgraph_node::split_part, split_point::split_part_set_retval, ssa_default_def(), SSA_NAME_DEF_STMT, SSA_NAME_VERSION, split_point::ssa_names_to_pass, SSA_OP_USE, cgraph_node::tp_first_run, TREE_CODE, TREE_THIS_VOLATILE, TREE_TYPE, UNKNOWN_LOCATION, unshare_expr(), update_stmt(), USE_FROM_PTR, useless_type_conversion_p(), vec_safe_length(), vec_safe_push(), virtual_operand_p(), vNULL, VOID_TYPE_P, and profile_count::zero().

Referenced by execute_split_functions().

split_part_set_ssa_name_p()

static bool split_part_set_ssa_name_p ( tree val, class split_point * current, basic_block return_bb )

static

For give split point CURRENT and return block RETURN_BB return 1
if ssa name VAL is set by split part and 0 otherwise.   

References bitmap_bit_p, ggc_alloc(), gimple_bb(), split_point::split_bbs, SSA_NAME_DEF_STMT, SSA_NAME_IS_DEFAULT_DEF, and TREE_CODE.

Referenced by consider_split().

test_nonssa_use()

static bool test_nonssa_use ( gimple * , tree t, tree , void * data )

static

Callback for walk_stmt_load_store_addr_ops.  If T is non-SSA automatic
variable, check it if it is present in bitmap passed via DATA.   

References auto_var_in_fn_p(), bitmap_bit_p, current_function_decl, DECL_BY_REFERENCE, DECL_RESULT, DECL_UID, FORCED_LABEL, get_base_address(), ggc_alloc(), INDIRECT_REF_P, is_gimple_reg(), SSA_NAME_VAR, TREE_CODE, TREE_OPERAND, and VAR_P.

Referenced by verify_non_ssa_vars().

verify_non_ssa_vars()

static bool verify_non_ssa_vars ( class split_point * current, bitmap non_ssa_vars, basic_block return_bb )

static

Look for all BBs in header that might lead to the split part and verify
that they are not defining any non-SSA var used by the split part.
Parameters are the same as for consider_split.   

References BITMAP_ALLOC, bitmap_bit_p, BITMAP_FREE, bitmap_set_bit, cfun, split_point::entry_bb, ENTRY_BLOCK_PTR_FOR_FN, FOR_EACH_BB_FN, FOR_EACH_EDGE, gcc_checking_assert, ggc_alloc(), gimple_label_label(), gimple_phi_arg_def(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), basic_block_def::index, is_gimple_debug(), NULL, NULL_TREE, basic_block_def::preds, split_point::split_bbs, basic_block_def::succs, test_nonssa_use(), TREE_CODE, virtual_operand_p(), vNULL, walk_stmt_load_store_addr_ops(), and worklist.

Referenced by consider_split().

visit_bb()

static bool visit_bb ( basic_block bb, basic_block return_bb, bitmap set_ssa_names, bitmap used_ssa_names, bitmap non_ssa_vars )

static

Compute local properties of basic block BB we collect when looking for
split points.  We look for ssa defs and store them in SET_SSA_NAMES,
for ssa uses and store them in USED_SSA_NAMES and for any non-SSA automatic
vars stored in NON_SSA_VARS.

When BB has edge to RETURN_BB, collect uses in RETURN_BB too.  

Return false when BB contains something that prevents it from being put into
split function.   

References bitmap_set_bit, BUILT_IN_NORMAL, DECL_ATTRIBUTES, DECL_FUNCTION_CODE(), dump_file, dump_flags, fndecl_built_in_p(), FOR_EACH_EDGE, FOR_EACH_SSA_TREE_OPERAND, ggc_alloc(), gimple_call_fndecl(), gimple_clobber_p(), gimple_phi_arg_def(), gimple_phi_num_args(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), i, is_gimple_debug(), lookup_attribute(), mark_nonssa_use(), SSA_NAME_VERSION, SSA_OP_DEF, SSA_OP_USE, basic_block_def::succs, TDF_DETAILS, TREE_CODE, virtual_operand_p(), and walk_stmt_load_store_addr_ops().

Referenced by find_split_points().

Variable Documentation

bb_info_vec

vec<split_bb_info> bb_info_vec

static

Referenced by execute_split_functions(), and find_split_points().

best_split_point

class split_point best_split_point

Best split point found.   

Referenced by consider_split(), and execute_split_functions().

forbidden_dominators

bitmap forbidden_dominators

static

Set of basic blocks that are not allowed to dominate a split point.   

Referenced by check_forbidden_calls(), consider_split(), dominated_by_forbidden(), and execute_split_functions().