tree-ssa-loop-ivopts.c File Reference

Data Structures
struct	iv
struct	version_info
struct	comp_cost
struct	cost_pair
struct	iv_use
struct	iv_cand
struct	iv_inv_expr_ent
struct	iv_inv_expr_hasher
struct	ivopts_data
struct	iv_ca
struct	iv_ca_delta
struct	ifs_ivopts_data
struct	address_cost_data_s

Typedefs
typedef struct iv_use *	iv_use_p
typedef struct iv_cand *	iv_cand_p
typedef struct address_cost_data_s *	address_cost_data

Enumerations
enum	use_type { USE_NONLINEAR_EXPR, USE_ADDRESS, USE_COMPARE }
enum	iv_position {   IP_NORMAL, IP_END, IP_BEFORE_USE, IP_AFTER_USE,   IP_ORIGINAL }

Functions
static HOST_WIDE_INT	avg_loop_niter ()
static comp_cost	force_expr_to_var_cost (tree, bool)
static unsigned	n_iv_uses ()
static struct iv_use *	iv_use ()
static unsigned	n_iv_cands ()
static struct iv_cand *	iv_cand ()
edge	single_dom_exit ()
void	dump_iv (FILE *, struct iv *)
void	dump_iv ()
void	dump_use (FILE *, struct iv_use *)
void	dump_use ()
void	dump_uses (FILE *, struct ivopts_data *)
void	dump_uses ()
void	dump_cand (FILE *, struct iv_cand *)
void	dump_cand ()
static struct version_info *	ver_info ()
static struct version_info *	name_info ()
static bool	stmt_after_ip_normal_pos ()
static bool	stmt_after_inc_pos ()
static bool	stmt_after_increment ()
static bool	abnormal_ssa_name_p ()
static bool	idx_contains_abnormal_ssa_name_p (tree base, tree *index, void *data)
bool	contains_abnormal_ssa_name_p ()
static struct tree_niter_desc *	niter_for_exit ()
static struct tree_niter_desc *	niter_for_single_dom_exit ()
static void	tree_ssa_iv_optimize_init ()
static tree	determine_base_object ()
static struct iv *	alloc_iv ()
static void	set_iv ()
static struct iv *	get_iv ()
static tree	determine_biv_step ()
static bool	find_bivs ()
static void	mark_bivs ()
static bool	find_givs_in_stmt_scev ()
static void	find_givs_in_stmt ()
static void	find_givs_in_bb ()
static void	find_givs ()
static bool	find_induction_variables ()
static struct iv_use *	record_use (struct ivopts_data *data, tree *use_p, struct iv *iv, gimple stmt, enum use_type use_type)
static void	record_invariant ()
static struct iv_use *	find_interesting_uses_op ()
static bool	extract_cond_operands (struct ivopts_data *data, gimple stmt, tree **control_var, tree **bound, struct iv **iv_var, struct iv **iv_bound)
static void	find_interesting_uses_cond ()
struct loop *	outermost_invariant_loop_for_expr ()
bool	expr_invariant_in_loop_p ()
bool	stmt_invariant_in_loop_p ()
static bool	idx_find_step ()
static bool	idx_record_use (tree base, tree *idx, void *vdata)
static bool	constant_multiple_of ()
static bool	may_be_unaligned_p ()
bool	may_be_nonaddressable_p ()
static void	find_interesting_uses_address ()
static void	find_invariants_stmt ()
static void	find_interesting_uses_stmt ()
static void	find_interesting_uses_outside ()
static void	find_interesting_uses ()
static tree	strip_offset_1 (tree expr, bool inside_addr, bool top_compref, unsigned HOST_WIDE_INT *offset)
static tree	strip_offset ()
static tree	generic_type_for ()
static tree	find_depends ()
static struct iv_cand *	add_candidate_1 (struct ivopts_data *data, tree base, tree step, bool important, enum iv_position pos, struct iv_use *use, gimple incremented_at)
static bool	allow_ip_end_pos_p ()
static void	add_autoinc_candidates (struct ivopts_data *data, tree base, tree step, bool important, struct iv_use *use)
static void	add_candidate (struct ivopts_data *data, tree base, tree step, bool important, struct iv_use *use)
static void	add_standard_iv_candidates ()
static void	add_old_iv_candidates ()
static void	add_old_ivs_candidates ()
static void	add_iv_value_candidates (struct ivopts_data *data, struct iv *iv, struct iv_use *use)
static void	add_derived_ivs_candidates ()
static void	record_important_candidates ()
static void	alloc_use_cost_map ()
static comp_cost	new_cost ()
static comp_cost	add_costs ()
static comp_cost	sub_costs ()
static int	compare_costs ()
static bool	infinite_cost_p ()
static void	set_use_iv_cost (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand, comp_cost cost, bitmap depends_on, tree value, enum tree_code comp, int inv_expr_id)
static struct cost_pair *	get_use_iv_cost (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
static unsigned	seq_cost ()
static rtx	produce_memory_decl_rtl ()
static tree	prepare_decl_rtl ()
static unsigned	computation_cost ()
static tree	var_at_stmt ()
static tree	determine_common_wider_type ()
static bool	get_computation_aff (struct loop *loop, struct iv_use *use, struct iv_cand *cand, gimple at, struct affine_tree_combination *aff)
static tree	get_use_type ()
static tree	get_computation_at (struct loop *loop, struct iv_use *use, struct iv_cand *cand, gimple at)
static tree	get_computation ()
static unsigned	adjust_setup_cost ()
bool	multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, enum machine_mode mode, addr_space_t as)
static comp_cost	get_address_cost (bool symbol_present, bool var_present, unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio, HOST_WIDE_INT cstep, enum machine_mode mem_mode, addr_space_t as, bool speed, bool stmt_after_inc, bool *may_autoinc)
static bool	get_shiftadd_cost (tree expr, enum machine_mode mode, comp_cost cost0, comp_cost cost1, tree mult, bool speed, comp_cost *cost)
static comp_cost	force_expr_to_var_cost ()
static comp_cost	force_var_cost (struct ivopts_data *data, tree expr, bitmap *depends_on)
static comp_cost	split_address_cost (struct ivopts_data *data, tree addr, bool *symbol_present, bool *var_present, unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
static comp_cost	ptr_difference_cost (struct ivopts_data *data, tree e1, tree e2, bool *symbol_present, bool *var_present, unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
static comp_cost	difference_cost (struct ivopts_data *data, tree e1, tree e2, bool *symbol_present, bool *var_present, unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
static bool	compare_aff_trees ()
static int	get_expr_id ()
static int	get_loop_invariant_expr_id (struct ivopts_data *data, tree ubase, tree cbase, HOST_WIDE_INT ratio, bool address_p)
static comp_cost	get_computation_cost_at (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand, bool address_p, bitmap *depends_on, gimple at, bool *can_autoinc, int *inv_expr_id)
static comp_cost	get_computation_cost (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand, bool address_p, bitmap *depends_on, bool *can_autoinc, int *inv_expr_id)
static bool	determine_use_iv_cost_generic (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
static bool	determine_use_iv_cost_address (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
static void	cand_value_at (struct loop *loop, struct iv_cand *cand, gimple at, tree niter, aff_tree *val)
static tree	iv_period ()
static enum tree_code	iv_elimination_compare ()
static tree	strip_wrap_conserving_type_conversions ()
static bool	expr_equal_p ()
static bool	difference_cannot_overflow_p ()
static bool	iv_elimination_compare_lt (struct ivopts_data *data, struct iv_cand *cand, enum tree_code *comp_p, struct tree_niter_desc *niter)
static bool	may_eliminate_iv (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand, tree *bound, enum tree_code *comp)
static int	parm_decl_cost ()
static bool	determine_use_iv_cost_condition (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
static bool	determine_use_iv_cost (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
static bool	autoinc_possible_for_pair (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
static void	set_autoinc_for_original_candidates ()
static void	find_iv_candidates ()
static void	determine_use_iv_costs ()
static void	determine_iv_cost ()
static void	determine_iv_costs ()
static unsigned	ivopts_global_cost_for_size ()
static void	determine_set_costs ()
static bool	cheaper_cost_pair ()
static struct cost_pair *	iv_ca_cand_for_use ()
static void	iv_ca_recount_cost ()
static void	iv_ca_set_remove_invariants ()
static void	iv_ca_set_no_cp (struct ivopts_data *data, struct iv_ca *ivs, struct iv_use *use)
static void	iv_ca_set_add_invariants ()
static void	iv_ca_set_cp (struct ivopts_data *data, struct iv_ca *ivs, struct iv_use *use, struct cost_pair *cp)
static void	iv_ca_add_use (struct ivopts_data *data, struct iv_ca *ivs, struct iv_use *use, bool important_candidates)
static comp_cost	iv_ca_cost ()
static bool	iv_ca_has_deps ()
static struct iv_ca_delta *	iv_ca_delta_add (struct iv_use *use, struct cost_pair *old_cp, struct cost_pair *new_cp, struct iv_ca_delta *next_change)
static struct iv_ca_delta *	iv_ca_delta_join ()
static struct iv_ca_delta *	iv_ca_delta_reverse ()
static void	iv_ca_delta_commit (struct ivopts_data *data, struct iv_ca *ivs, struct iv_ca_delta *delta, bool forward)
static bool	iv_ca_cand_used_p ()
static unsigned	iv_ca_n_cands ()
static void	iv_ca_delta_free ()
static struct iv_ca *	iv_ca_new ()
static void	iv_ca_free ()
static void	iv_ca_dump ()
static comp_cost	iv_ca_extend (struct ivopts_data *data, struct iv_ca *ivs, struct iv_cand *cand, struct iv_ca_delta **delta, unsigned *n_ivs, bool min_ncand)
static comp_cost	iv_ca_narrow (struct ivopts_data *data, struct iv_ca *ivs, struct iv_cand *cand, struct iv_ca_delta **delta)
static comp_cost	iv_ca_prune (struct ivopts_data *data, struct iv_ca *ivs, struct iv_cand *except_cand, struct iv_ca_delta **delta)
static bool	try_add_cand_for (struct ivopts_data *data, struct iv_ca *ivs, struct iv_use *use, bool originalp)
static struct iv_ca *	get_initial_solution ()
static bool	try_improve_iv_set ()
static struct iv_ca *	find_optimal_iv_set_1 ()
static struct iv_ca *	find_optimal_iv_set ()
static void	create_new_iv ()
static void	create_new_ivs ()
static void	rewrite_use_nonlinear_expr (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
static void	adjust_iv_update_pos ()
static void	rewrite_use_address (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
static void	rewrite_use_compare (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
static void	rewrite_use ()
static void	rewrite_uses ()
static void	remove_unused_ivs ()
static bool	free_tree_niter_desc (const void *key, void **value, void *data)
static void	free_loop_data ()
static void	tree_ssa_iv_optimize_finalize ()
static bool	loop_body_includes_call ()
static bool	tree_ssa_iv_optimize_loop ()
void	tree_ssa_iv_optimize ()

Variables
static const comp_cost	no_cost = {0, 0}
static const comp_cost	infinite_cost = {INFTY, INFTY}
static vec< tree >	decl_rtl_to_reset
static struct ivopts_data *	fd_ivopts_data

---

Typedef Documentation

typedef struct address_cost_data_s * address_cost_data

Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
   If SYMBOL_PRESENT is false, symbol is omitted.  If VAR_PRESENT is false,
   variable is omitted.  Compute the cost for a memory reference that accesses
   a memory location of mode MEM_MODE in address space AS.

   MAY_AUTOINC is set to true if the autoincrement (increasing index by
   size of MEM_MODE / RATIO) is available.  To make this determination, we
   look at the size of the increment to be made, which is given in CSTEP.
   CSTEP may be zero if the step is unknown.
   STMT_AFTER_INC is true iff the statement we're looking at is after the
   increment of the original biv.

   TODO -- there must be some better way.  This all is quite crude.   

typedef struct iv_cand* iv_cand_p

typedef struct iv_use* iv_use_p

The data used by the induction variable optimizations.   

---

Enumeration Type Documentation

enum iv_position

The position where the iv is computed.   

Enumerator:

IP_NORMAL
IP_END
IP_BEFORE_USE
IP_AFTER_USE
IP_ORIGINAL

enum use_type

Types of uses.   

Enumerator:

USE_NONLINEAR_EXPR
USE_ADDRESS
USE_COMPARE

---

Function Documentation

static bool abnormal_ssa_name_p ( )

static

Returns true if EXP is a ssa name that occurs in an abnormal phi node.   

Referenced by idx_contains_abnormal_ssa_name_p().

static void add_autoinc_candidates ( struct ivopts_data *  data, tree  base, tree  step, bool  important, struct iv_use *  use  )

static

If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
   Important field is set to IMPORTANT.   

References add_candidate_1(), CDI_DOMINATORS, cst_and_fits_in_hwi(), ivopts_data::current_loop, dominated_by_p(), gimple_bb(), HOST_WIDE_INT, int_cst_value(), IP_AFTER_USE, IP_BEFORE_USE, loop::latch, basic_block_def::loop_father, iv_use::op_p, iv_use::stmt, and stmt_could_throw_p().

Referenced by add_candidate().

static void add_candidate ( struct ivopts_data *  data, tree  base, tree  step, bool  important, struct iv_use *  use  )

static

Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
   position to POS.  If USE is not NULL, the candidate is set as related to
   it.  The candidate computation is scheduled on all available positions.   

References add_autoinc_candidates(), add_candidate_1(), allow_ip_end_pos_p(), ivopts_data::current_loop, IP_END, ip_end_pos(), IP_NORMAL, ip_normal_pos(), iv_use::type, and USE_ADDRESS.

Referenced by add_iv_value_candidates(), add_old_iv_candidates(), and add_standard_iv_candidates().

static struct iv_cand* add_candidate_1 ( struct ivopts_data *  data, tree  base, tree  step, bool  important, enum iv_position  pos, struct iv_use *  use, gimple  incremented_at  )

staticread

Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
   position to POS.  If USE is not NULL, the candidate is set as related to
   it.  If both BASE and STEP are NULL, we add a pseudocandidate for the
   replacement of the final value of the iv by a direct computation.   

References alloc_iv(), bitmap_set_bit(), create_tmp_var_raw(), dump_cand(), dump_file, dump_flags, fd_ivopts_data, find_depends(), generic_type_for(), iv_use::id, iv_cand::id, iv_cand::important, IP_AFTER_USE, IP_BEFORE_USE, IP_ORIGINAL, iv_cand(), ivopts_data::iv_candidates, n_iv_cands(), operand_equal_p(), iv_use::related_cands, and type().

Referenced by add_autoinc_candidates(), add_candidate(), and add_old_iv_candidates().

static comp_cost add_costs ( )

static

Adds costs COST1 and COST2.   

References comp_cost::complexity, and comp_cost::cost.

Referenced by force_expr_to_var_cost(), get_computation_cost_at(), get_shiftadd_cost(), iv_ca_set_cp(), and replace_uncond_cands_and_profitable_phis().

static void add_derived_ivs_candidates ( )

static

Adds candidates based on the uses.   

References add_iv_value_candidates(), iv_use::iv, iv_use(), n_iv_uses(), iv_use::type, USE_ADDRESS, USE_COMPARE, and USE_NONLINEAR_EXPR.

Referenced by find_iv_candidates().

static void add_iv_value_candidates ( struct ivopts_data *  data, struct iv *  iv, struct iv_use *  use  )

static

Adds candidates based on the value of the induction variable IV and USE.   

References add_candidate(), iv::base, build_int_cst(), HOST_WIDE_INT, offset, iv::step, and strip_offset().

Referenced by add_derived_ivs_candidates().

static void add_old_iv_candidates ( )

static

Adds candidates bases on the old induction variable IV.   

References add_candidate(), add_candidate_1(), iv::base, build_int_cst(), ivopts_data::current_loop, IP_ORIGINAL, loop_latch_edge(), iv::ssa_name, and iv::step.

Referenced by add_old_ivs_candidates().

static void add_old_ivs_candidates ( )

static

Adds candidates based on the old induction variables.   

References add_old_iv_candidates(), iv::biv_p, integer_zerop(), version_info::iv, ivopts_data::relevant, iv::step, and ver_info().

Referenced by find_iv_candidates().

static void add_standard_iv_candidates ( )

static

Adds standard iv candidates.   

References add_candidate(), and build_int_cst().

Referenced by find_iv_candidates().

static void adjust_iv_update_pos ( )

static

Performs a peephole optimization to reorder the iv update statement with
   a mem ref to enable instruction combining in later phases. The mem ref uses
   the iv value before the update, so the reordering transformation requires
   adjustment of the offset. CAND is the selected IV_CAND.

   Example:

   t = MEM_REF (base, iv1, 8, 16);  // base, index, stride, offset
   iv2 = iv1 + 1;

   if (t < val)      (1)
     goto L;
   goto Head;


   directly propagating t over to (1) will introduce overlapping live range
   thus increase register pressure. This peephole transform it into:


   iv2 = iv1 + 1;
   t = MEM_REF (base, iv2, 8, 8);
   if (t < val)
     goto L;
   goto Head;

References dump_file, dump_flags, gimple_assign_lhs(), gimple_bb(), gsi_end_p(), gsi_for_stmt(), gsi_last_nondebug_bb(), gsi_move_before(), gsi_prev_nondebug(), gsi_stmt(), IP_BEFORE_USE, IP_NORMAL, print_gimple_stmt(), and iv_use::stmt.

Referenced by rewrite_use_address().

static unsigned adjust_setup_cost ( )

static

Adjust the cost COST for being in loop setup rather than loop body.
   If we're optimizing for space, the loop setup overhead is constant;
   if we're optimizing for speed, amortize it over the per-iteration cost.   

References avg_loop_niter(), ivopts_data::current_loop, and optimize_loop_for_speed_p().

Referenced by determine_iv_cost(), determine_use_iv_cost_condition(), and get_computation_cost_at().

static struct iv* alloc_iv ( )

staticread

Allocates an induction variable with given initial value BASE and step STEP
   for loop LOOP.   

References iv::base, iv::base_object, iv::biv_p, determine_base_object(), iv::have_use_for, iv::ssa_name, iv::step, and iv::use_id.

Referenced by add_candidate_1(), find_interesting_uses_address(), and set_iv().

static void alloc_use_cost_map ( )

static

Allocates the data structure mapping the (use, candidate) pairs to costs.
   If consider_all_candidates is true, we use a two-dimensional array, otherwise
   we allocate a simple list to every use.   

References bitmap_count_bits(), ceil_log2(), ivopts_data::consider_all_candidates, iv_use::cost_map, iv_use(), n_iv_cands(), n_iv_uses(), iv_use::n_map_members, and iv_use::related_cands.

Referenced by determine_use_iv_costs().

static bool allow_ip_end_pos_p ( )

static

Returns true if incrementing the induction variable at the end of the LOOP
   is allowed.

   The purpose is to avoid splitting latch edge with a biv increment, thus
   creating a jump, possibly confusing other optimization passes and leaving
   less freedom to scheduler.  So we allow IP_END_POS only if IP_NORMAL_POS
   is not available (so we do not have a better alternative), or if the latch
   edge is already nonempty.   

References empty_block_p(), ip_end_pos(), and ip_normal_pos().

Referenced by add_candidate().

static bool autoinc_possible_for_pair ( struct ivopts_data *  data, struct iv_use *  use, struct iv_cand *  cand  )

static

Return true if get_computation_cost indicates that autoincrement is
   a possibility for the pair of USE and CAND, false otherwise.   

References get_computation_cost(), infinite_cost_p(), iv_use::type, and USE_ADDRESS.

Referenced by set_autoinc_for_original_candidates().

static HOST_WIDE_INT avg_loop_niter ( )

inlinestatic

Returns the expected number of loop iterations for LOOP.
   The average trip count is computed from profile data if it
   exists.  

References estimated_stmt_executions_int(), and HOST_WIDE_INT.

Referenced by adjust_setup_cost(), and get_computation_cost_at().

static void cand_value_at ( struct loop *  loop, struct iv_cand *  cand, gimple  at, tree  niter, aff_tree *  val  )

static

Computes value of candidate CAND at position AT in iteration NITER, and
   stores it to VAL.   

References aff_combination_add(), aff_combination_convert(), aff_combination_mult(), iv::base, iv::step, stmt_after_increment(), tree_to_aff_combination(), and type().

Referenced by may_eliminate_iv().

static bool cheaper_cost_pair ( )

static

Returns true if A is a cheaper cost pair than B.   

References cost_pair::cand, compare_costs(), and cost_pair::cost.

Referenced by iv_ca_add_use(), iv_ca_extend(), and iv_ca_narrow().

static bool compare_aff_trees ( )

static

Returns true if AFF1 and AFF2 are identical.   

References aff_comb_elt::coef, affine_tree_combination::elts, affine_tree_combination::n, operand_equal_p(), and aff_comb_elt::val.

Referenced by get_loop_invariant_expr_id().

static int compare_costs ( )

static

Returns a negative number if COST1 < COST2, a positive number if
   COST1 > COST2, and 0 if COST1 = COST2.   

References comp_cost::complexity, and comp_cost::cost.

Referenced by cheaper_cost_pair(), determine_use_iv_cost_condition(), find_optimal_iv_set(), iv_ca_prune(), try_add_cand_for(), and try_improve_iv_set().

static unsigned computation_cost ( )

static

Determines cost of the computation of EXPR.   

References address_cost(), cgraph_get_node(), cost_pair::cost, current_function_decl, default_rtl_profile(), end_sequence(), expand_expr(), EXPAND_NORMAL, get_insns(), NODE_FREQUENCY_NORMAL, prepare_decl_rtl(), seq_cost(), set_src_cost(), and start_sequence().

Referenced by force_expr_to_var_cost(), and get_computation_cost_at().

static bool constant_multiple_of ( )

static

If we can prove that TOP = cst * BOT for some constant cst,
   store cst to MUL and return true.  Otherwise return false.
   The returned value is always sign-extended, regardless of the
   signedness of TOP and BOT.   

References double_int::is_zero(), operand_equal_p(), double_int::sdivmod(), double_int::sext(), and tree_to_double_int().

Referenced by get_computation_aff(), and get_computation_cost_at().

bool contains_abnormal_ssa_name_p

(

)

Returns true if EXPR contains a ssa name that occurs in an
   abnormal phi node.   

References contains_abnormal_ssa_name_p(), for_each_index(), idx_contains_abnormal_ssa_name_p(), is_gimple_min_invariant(), tcc_binary, tcc_comparison, and tcc_unary.

static void create_new_iv ( )

static

Creates a new induction variable corresponding to CAND.   

References create_iv(), ivopts_data::current_loop, find_interesting_uses_op(), gimple_add_tmp_var(), gsi_for_stmt(), gsi_last_bb(), IP_AFTER_USE, IP_BEFORE_USE, IP_END, ip_end_pos(), IP_NORMAL, ip_normal_pos(), IP_ORIGINAL, name_info(), version_info::preserve_biv, iv_use::selected, and unshare_expr().

Referenced by create_new_ivs().

static void create_new_ivs ( )

static

Creates new induction variables described in SET.   

References create_new_iv(), dump_cand(), dump_file, dump_flags, and iv_cand().

Referenced by tree_ssa_iv_optimize_loop().

static tree determine_base_object ( )

static

Returns a memory object to that EXPR points.  In case we are able to
   determine that it does not point to any such object, NULL is returned.   

References get_base_address().

Referenced by alloc_iv().

static tree determine_biv_step ( )

static

Determines the step of a biv defined in PHI.  Returns NULL if PHI does
   not define a simple affine biv with nonzero step.   

References gimple_bb(), integer_zerop(), basic_block_def::loop_father, simple_iv(), affine_iv::step, and virtual_operand_p().

Referenced by find_bivs().

static tree determine_common_wider_type ( )

static

If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the
   same precision that is at least as wide as the precision of TYPE, stores
   BA to A and BB to B, and returns the type of BA.  Otherwise, returns the
   type of A and B.   

Referenced by get_computation_aff().

static void determine_iv_cost ( )

static

Determines cost of the candidate CAND.   

References add_cost(), adjust_setup_cost(), comp_cost::cost, ivopts_data::current_loop, empty_block_p(), force_var_cost(), IP_END, ip_end_pos(), IP_ORIGINAL, and ivopts_data::speed.

Referenced by determine_iv_costs().

static void determine_iv_costs ( )

static

Determines costs of computation of the candidates.   

References determine_iv_cost(), dump_file, dump_flags, iv_cand(), and n_iv_cands().

Referenced by tree_ssa_iv_optimize_loop().

static void determine_set_costs ( )

static

For each size of the induction variable set determine the penalty.   

References ivopts_data::current_loop, dump_file, dump_flags, get_iv(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), version_info::has_nonlin_use, loop::header, version_info::inv_id, ivopts_global_cost_for_size(), ivopts_data::regs_used, ivopts_data::relevant, ivopts_data::speed, ver_info(), and virtual_operand_p().

Referenced by tree_ssa_iv_optimize_loop().

static bool determine_use_iv_cost ( struct ivopts_data *  data, struct iv_use *  use, struct iv_cand *  cand  )

static

Determines cost of basing replacement of USE on CAND.  Returns false
   if USE cannot be based on CAND.   

References determine_use_iv_cost_address(), determine_use_iv_cost_condition(), determine_use_iv_cost_generic(), iv_use::type, USE_ADDRESS, USE_COMPARE, and USE_NONLINEAR_EXPR.

Referenced by determine_use_iv_costs().

static bool determine_use_iv_cost_address ( struct ivopts_data *  data, struct iv_use *  use, struct iv_cand *  cand  )

static

Determines cost of basing replacement of USE on CAND in an address.   

References comp_cost::cost, get_computation_cost(), infinite_cost, infinite_cost_p(), IP_AFTER_USE, IP_BEFORE_USE, and set_use_iv_cost().

Referenced by determine_use_iv_cost().

static bool determine_use_iv_cost_condition ( struct ivopts_data *  data, struct iv_use *  use, struct iv_cand *  cand  )

static

Determines cost of basing replacement of USE on CAND in a condition.   

References adjust_setup_cost(), iv::base, bitmap_clear(), bitmap_count_bits(), tree_niter_desc::bound, comp, compare_costs(), comp_cost::cost, extract_cond_operands(), fd_ivopts_data, find_depends(), force_var_cost(), get_computation_cost(), get_expr_id(), infinite_cost, infinite_cost_p(), integer_zerop(), may_eliminate_iv(), operand_equal_p(), parm_decl_cost(), set_use_iv_cost(), and iv_use::stmt.

Referenced by determine_use_iv_cost().

static bool determine_use_iv_cost_generic ( struct ivopts_data *  data, struct iv_use *  use, struct iv_cand *  cand  )

static

Determines cost of basing replacement of USE on CAND in a generic
   expression.   

References get_computation_cost(), infinite_cost_p(), IP_ORIGINAL, set_use_iv_cost(), and iv_use::stmt.

Referenced by determine_use_iv_cost().

static void determine_use_iv_costs ( )

static

Determines costs of basing the use of the iv on an iv candidate.   

References alloc_use_cost_map(), bitmap_and_compl_into(), bitmap_clear(), bitmap_print(), bitmap_set_bit(), cost_pair::cand, comp_cost::complexity, ivopts_data::consider_all_candidates, comp_cost::cost, cost_pair::cost, iv_use::cost_map, cost_pair::depends_on, determine_use_iv_cost(), dump_file, dump_flags, iv_cand::id, infinite_cost_p(), cost_pair::inv_expr_id, iv_cand(), iv_use(), n_iv_cands(), n_iv_uses(), iv_use::n_map_members, and iv_use::related_cands.

Referenced by tree_ssa_iv_optimize_loop().

static bool difference_cannot_overflow_p ( )

static

Returns true if we can prove that BASE - OFFSET does not overflow.  For now,
   we only detect the situation that BASE = SOMETHING + OFFSET, where the
   calculation is performed in non-wrapping type.

   TODO: More generally, we could test for the situation that
         BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero.
         This would require knowing the sign of OFFSET.

         Also, we only look for the first addition in the computation of BASE.
         More complex analysis would be better, but introducing it just for
         this optimization seems like an overkill.   

References expand_simple_operations(), expr_equal_p(), get_gimple_rhs_class(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), GIMPLE_BINARY_RHS, and nowrap_type_p().

Referenced by iv_elimination_compare_lt().

static comp_cost difference_cost ( struct ivopts_data *  data, tree  e1, tree  e2, bool *  symbol_present, bool *  var_present, unsigned HOST_WIDE_INT *  offset, bitmap *  depends_on  )

static

Estimates cost of expressing difference E1 - E2 as
   var + symbol + offset.  The value of offset is added to OFFSET,
   SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
   part is missing.  DEPENDS_ON is a set of the invariants the computation
   depends on.   

References aff_combination_add(), aff_combination_scale(), aff_combination_to_tree(), comp_cost::cost, force_var_cost(), HOST_WIDE_INT, integer_zerop(), mult_by_coeff_cost(), no_cost, operand_equal_p(), ptr_difference_cost(), signed_type_for(), ivopts_data::speed, strip_offset(), tree_to_aff_combination(), and type().

Referenced by get_computation_cost_at().

void dump_cand	(	FILE *	,
		struct iv_cand *
	)

Dumps information about induction variable candidate CAND to FILE.   

Referenced by add_candidate_1(), and create_new_ivs().

void dump_cand

(

)

References dump_bitmap(), dump_iv(), iv_cand::id, iv_cand::important, IP_AFTER_USE, IP_BEFORE_USE, IP_END, IP_NORMAL, IP_ORIGINAL, and print_generic_expr().

void dump_iv	(	FILE *	,
		struct iv *
	)

Dumps information about the induction variable IV to FILE.   

Referenced by dump_cand(), dump_use(), and find_induction_variables().

void dump_iv

(

)

References iv::base, iv::base_object, iv::biv_p, print_generic_expr(), iv::ssa_name, and iv::step.

void dump_use	(	FILE *	,
		struct iv_use *
	)

Dumps information about the USE to FILE.   

Referenced by dump_uses(), and record_use().

void dump_use

(

)

References dump_bitmap(), dump_iv(), iv_use::id, iv_use::iv, iv_use::op_p, print_generic_expr(), print_gimple_stmt(), iv_use::related_cands, iv_use::stmt, iv_use::type, USE_ADDRESS, USE_COMPARE, and USE_NONLINEAR_EXPR.

void dump_uses	(	FILE *	,
		struct ivopts_data *
	)

Dumps information about the uses to FILE.   

void dump_uses

(

)

References dump_use(), iv_use(), and n_iv_uses().

static bool expr_equal_p ( )

static

Walk the SSA form and check whether E == WHAT.  Fairly simplistic, we
   check for an exact match.   

References get_gimple_rhs_class(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), GIMPLE_BINARY_RHS, GIMPLE_SINGLE_RHS, GIMPLE_UNARY_RHS, operand_equal_p(), and strip_wrap_conserving_type_conversions().

Referenced by difference_cannot_overflow_p().

bool expr_invariant_in_loop_p

(

)

Returns true if expression EXPR is obviously invariant in LOOP,
   i.e. if all its operands are defined outside of the LOOP.  LOOP
   should not be the function body.   

References expr_invariant_in_loop_p(), flow_bb_inside_loop_p(), gimple_bb(), is_gimple_min_invariant(), len, and loop_depth().

static bool extract_cond_operands ( struct ivopts_data *  data, gimple  stmt, tree **  control_var, tree **  bound, struct iv **  iv_var, struct iv **  iv_bound  )

static

Given a condition in statement STMT, checks whether it is a compare
   of an induction variable and an invariant.  If this is the case,
   CONTROL_VAR is set to location of the iv, BOUND to the location of
   the invariant, IV_VAR and IV_BOUND are set to the corresponding
   induction variable descriptions, and true is returned.  If this is not
   the case, CONTROL_VAR and BOUND are set to the arguments of the
   condition and false is returned.   

References get_iv(), gimple_assign_rhs1_ptr(), gimple_assign_rhs2_ptr(), gimple_cond_lhs_ptr(), gimple_cond_rhs_ptr(), integer_zerop(), and iv::step.

Referenced by determine_use_iv_cost_condition(), find_interesting_uses_cond(), and rewrite_use_compare().

static bool find_bivs ( )

static

Finds basic ivs.   

References contains_abnormal_ssa_name_p(), ivopts_data::current_loop, determine_biv_step(), expand_simple_operations(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), loop::header, loop_preheader_edge(), set_iv(), and type().

Referenced by find_induction_variables().

static tree find_depends ( )

static

References bitmap_set_bit(), fd_ivopts_data, version_info::has_nonlin_use, version_info::inv_id, and name_info().

Referenced by add_candidate_1(), determine_use_iv_cost_condition(), force_var_cost(), and split_address_cost().

static void find_givs ( )

static

Finds general ivs.   

References ivopts_data::current_loop, find_givs_in_bb(), free(), get_loop_body_in_dom_order(), and loop::num_nodes.

Referenced by find_induction_variables().

static void find_givs_in_bb ( )

static

Finds general ivs in basic block BB.   

References find_givs_in_stmt(), gsi_end_p(), gsi_next(), gsi_start_bb(), and gsi_stmt().

Referenced by find_givs().

static void find_givs_in_stmt ( )

static

Finds general ivs in statement STMT.   

References affine_iv::base, find_givs_in_stmt_scev(), gimple_assign_lhs(), set_iv(), and affine_iv::step.

Referenced by find_givs_in_bb().

static bool find_givs_in_stmt_scev ( )

static

Checks whether STMT defines a linear induction variable and stores its
   parameters to IV.   

References affine_iv::base, contains_abnormal_ssa_name_p(), ivopts_data::current_loop, expand_simple_operations(), gimple_assign_lhs(), loop_containing_stmt(), simple_iv(), affine_iv::step, and stmt_could_throw_p().

Referenced by find_givs_in_stmt().

static bool find_induction_variables ( )

static

For each ssa name defined in LOOP determines whether it is an induction
   variable and if so, its initial value and step.   

References dump_file, dump_flags, dump_iv(), find_bivs(), find_givs(), integer_zerop(), mark_bivs(), tree_niter_desc::may_be_zero, tree_niter_desc::niter, niter_for_single_dom_exit(), print_generic_expr(), ivopts_data::relevant, and ver_info().

Referenced by tree_ssa_iv_optimize_loop().

static void find_interesting_uses ( )

static

Finds uses of the induction variables that are interesting.   

References ivopts_data::current_loop, edge_def::dest, dump_file, dump_flags, find_interesting_uses_outside(), find_interesting_uses_stmt(), flow_bb_inside_loop_p(), free(), get_loop_body(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), version_info::has_nonlin_use, version_info::inv_id, is_gimple_debug(), version_info::name, loop::num_nodes, print_generic_expr(), ivopts_data::relevant, basic_block_def::succs, and ver_info().

Referenced by tree_ssa_iv_optimize_loop().

static void find_interesting_uses_address ( )

static

Finds addresses in *OP_P inside STMT.   

References alloc_iv(), iv::base, build_pointer_type(), for_each_index(), get_iv(), gimple_has_volatile_ops(), handled_component_p(), idx_find_step(), idx_record_use(), integer_zerop(), ifs_ivopts_data::ivopts_data, may_be_nonaddressable_p(), may_be_unaligned_p(), record_use(), iv::step, ifs_ivopts_data::step, ifs_ivopts_data::stmt, tree_mem_ref_addr(), unshare_expr(), and USE_ADDRESS.

Referenced by find_interesting_uses_stmt().

static void find_interesting_uses_cond ( )

static

Checks whether the condition in STMT is interesting and if so,
   records it.   

References extract_cond_operands(), find_interesting_uses_op(), record_use(), and USE_COMPARE.

Referenced by find_interesting_uses_stmt().

static struct iv_use* find_interesting_uses_op ( )

staticread

Checks whether the use OP is interesting and if so, records it.   

References get_iv(), iv::have_use_for, iv_use::id, integer_zerop(), is_gimple_assign(), iv_use::iv, iv_use(), record_invariant(), record_use(), iv::step, iv_use::type, iv::use_id, and USE_NONLINEAR_EXPR.

Referenced by create_new_iv(), find_interesting_uses_cond(), find_interesting_uses_outside(), find_interesting_uses_stmt(), and idx_record_use().

static void find_interesting_uses_outside ( )

static

Finds interesting uses of induction variables outside of loops
   on loop exit edge EXIT.   

References edge_def::dest, find_interesting_uses_op(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), and virtual_operand_p().

Referenced by find_interesting_uses().

static void find_interesting_uses_stmt ( )

static

Finds interesting uses of induction variables in the statement STMT.   

References ivopts_data::current_loop, find_interesting_uses_address(), find_interesting_uses_cond(), find_interesting_uses_op(), find_invariants_stmt(), get_gimple_rhs_class(), get_iv(), gimple_assign_lhs_ptr(), gimple_assign_rhs1_ptr(), gimple_assign_rhs_code(), GIMPLE_SINGLE_RHS, loop::header, integer_zerop(), is_gimple_assign(), is_gimple_val(), iv::step, and tcc_comparison.

Referenced by find_interesting_uses().

static void find_invariants_stmt ( )

static

Finds and records invariants used in STMT.   

References record_invariant().

Referenced by find_interesting_uses_stmt().

static void find_iv_candidates ( )

static

Finds the candidates for the induction variables.   

References add_derived_ivs_candidates(), add_old_ivs_candidates(), add_standard_iv_candidates(), record_important_candidates(), and set_autoinc_for_original_candidates().

Referenced by tree_ssa_iv_optimize_loop().

static struct iv_ca* find_optimal_iv_set ( )

staticread

References cost_pair::cand, compare_costs(), comp_cost::complexity, comp_cost::cost, dump_file, dump_flags, find_optimal_iv_set_1(), infinite_cost, iv_ca_cand_for_use(), iv_ca_cost(), iv_ca_free(), iv_use(), n_iv_uses(), and iv_use::selected.

Referenced by tree_ssa_iv_optimize_loop().

static struct iv_ca* find_optimal_iv_set_1 ( )

staticread

Attempts to find the optimal set of induction variables.  We do simple
   greedy heuristic -- we try to replace at most one candidate in the selected
   solution and remove the unused ivs while this improves the cost.   

References dump_file, dump_flags, get_initial_solution(), iv_ca_dump(), and try_improve_iv_set().

Referenced by find_optimal_iv_set().

static comp_cost force_expr_to_var_cost ( tree  , bool    )

static

Referenced by force_expr_to_var_cost(), force_var_cost(), and get_shiftadd_cost().

static comp_cost force_expr_to_var_cost ( )

static

Estimates cost of forcing expression EXPR into a variable.   

References add_cost(), add_costs(), address_cost(), build_int_cst(), build_pointer_type(), computation_cost(), comp_cost::cost, create_tmp_var_raw(), cst_and_fits_in_hwi(), dump_file, dump_flags, force_expr_to_var_cost(), get_shiftadd_cost(), int_cst_value(), is_gimple_min_invariant(), is_gimple_val(), mult, mult_by_coeff_cost(), new_cost(), no_cost, and produce_memory_decl_rtl().

static comp_cost force_var_cost ( struct ivopts_data *  data, tree  expr, bitmap *  depends_on  )

static

Estimates cost of forcing EXPR into a variable.  DEPENDS_ON is a set of the
   invariants the computation depends on.   

References fd_ivopts_data, find_depends(), force_expr_to_var_cost(), and ivopts_data::speed.

Referenced by determine_iv_cost(), determine_use_iv_cost_condition(), difference_cost(), get_computation_cost_at(), and ptr_difference_cost().

static void free_loop_data ( )

static

Frees data allocated by the optimization of a single loop.   

References bitmap_clear(), iv_use::cost_map, decl_rtl_to_reset, cost_pair::depends_on, hash_table< Descriptor, Allocator >::empty(), free(), free_tree_niter_desc(), version_info::has_nonlin_use, ivopts_data::important_candidates, ivopts_data::inv_expr_id, ivopts_data::inv_expr_tab, version_info::inv_id, version_info::iv, iv_use::iv, iv_cand(), ivopts_data::iv_candidates, iv_use(), ivopts_data::iv_uses, ivopts_data::max_inv_id, n_iv_cands(), n_iv_uses(), iv_use::n_map_members, ivopts_data::niters, pointer_map_destroy(), pointer_map_traverse(), version_info::preserve_biv, iv_use::related_cands, ivopts_data::relevant, ver_info(), ivopts_data::version_info, and ivopts_data::version_info_size.

Referenced by tree_ssa_iv_optimize_finalize(), and tree_ssa_iv_optimize_loop().

static bool free_tree_niter_desc ( const void *  key, void **  value, void *  data  )

static

Frees memory occupied by struct tree_niter_desc in *VALUE. Callback
   for pointer_map_traverse.   

References free(), and tree_niter_desc::niter.

Referenced by free_loop_data().

static tree generic_type_for ( )

static

Returns variant of TYPE that can be used as base for different uses.
   We return unsigned type with the same precision, which avoids problems
   with overflows.   

References type(), and unsigned_type_for().

Referenced by add_candidate_1().

static comp_cost get_address_cost ( bool  symbol_present, bool  var_present, unsigned HOST_WIDE_INT  offset, HOST_WIDE_INT  ratio, HOST_WIDE_INT  cstep, enum machine_mode  mem_mode, addr_space_t  as, bool  speed, bool  stmt_after_inc, bool *  may_autoinc  )

static

References add_cost(), address_cost(), address_cost_data_s::costs, cse_not_expected, dump_file, dump_flags, end_sequence(), gen_int_mode(), gen_raw_REG(), get_insns(), HOST_BITS_PER_WIDE_INT, HOST_WIDE_INT, HOST_WIDE_INT_PRINT_DEC, address_cost_data_s::max_offset, memory_address_addr_space(), memory_address_addr_space_p(), address_cost_data_s::min_offset, mult_by_coeff_cost(), multiplier_allowed_in_address_p(), new_cost(), offset, seq_cost(), start_sequence(), and targetm.

Referenced by get_computation_cost_at().

static tree get_computation ( )

static

Determines the expression by that USE is expressed from induction variable
   CAND in LOOP.  The computation is unshared.   

References get_computation_at(), and iv_use::stmt.

Referenced by rewrite_use_compare(), and rewrite_use_nonlinear_expr().

static bool get_computation_aff ( struct loop *  loop, struct iv_use *  use, struct iv_cand *  cand, gimple  at, struct affine_tree_combination *  aff  )

static

Determines the expression by that USE is expressed from induction variable
   CAND at statement AT in LOOP.  The expression is stored in a decomposed
   form into AFF.  Returns false if USE cannot be expressed using CAND.   

References aff_combination_add(), aff_combination_convert(), aff_combination_scale(), iv::base, constant_multiple_of(), determine_common_wider_type(), iv_use::iv, iv::step, stmt_after_increment(), tree_to_aff_combination(), unsigned_type_for(), and var_at_stmt().

Referenced by get_computation_at(), and rewrite_use_address().

static tree get_computation_at ( struct loop *  loop, struct iv_use *  use, struct iv_cand *  cand, gimple  at  )

static

Determines the expression by that USE is expressed from induction variable
   CAND at statement AT in LOOP.  The computation is unshared.   

References aff_combination_to_tree(), get_computation_aff(), get_use_type(), and unshare_aff_combination().

Referenced by get_computation(), get_computation_cost_at(), and remove_unused_ivs().

static comp_cost get_computation_cost ( struct ivopts_data *  data, struct iv_use *  use, struct iv_cand *  cand, bool  address_p, bitmap *  depends_on, bool *  can_autoinc, int *  inv_expr_id  )

static

Determines the cost of the computation by that USE is expressed
   from induction variable CAND.  If ADDRESS_P is true, we just need
   to create an address from it, otherwise we want to get it into
   register.  A set of invariants we depend on is stored in
   DEPENDS_ON.  If CAN_AUTOINC is nonnull, use it to record whether
   autoinc addressing is likely.   

References get_computation_cost_at(), and iv_use::stmt.

Referenced by autoinc_possible_for_pair(), determine_use_iv_cost_address(), determine_use_iv_cost_condition(), and determine_use_iv_cost_generic().

static comp_cost get_computation_cost_at ( struct ivopts_data *  data, struct iv_use *  use, struct iv_cand *  cand, bool  address_p, bitmap *  depends_on, gimple  at, bool *  can_autoinc, int *  inv_expr_id  )

static

Determines the cost of the computation by that USE is expressed
   from induction variable CAND.  If ADDRESS_P is true, we just need
   to create an address from it, otherwise we want to get it into
   register.  A set of invariants we depend on is stored in
   DEPENDS_ON.  AT is the statement at that the value is computed.
   If CAN_AUTOINC is nonnull, use it to record whether autoinc
   addressing is likely.   

References add_cost(), add_costs(), adjust_setup_cost(), aff_combination_add(), aff_combination_to_tree(), avg_loop_niter(), iv::base, iv::base_object, bitmap_clear(), build_int_cst(), comp, comp_cost::complexity, computation_cost(), constant_multiple_of(), comp_cost::cost, cst_and_fits_in_hwi(), ivopts_data::current_loop, difference_cost(), double_int::fits_shwi(), force_var_cost(), get_address_cost(), get_computation_at(), get_loop_invariant_expr_id(), HOST_WIDE_INT, infinite_cost, int_cst_value(), iv_use::iv, mult_by_coeff_cost(), multiplier_allowed_in_address_p(), new_cost(), offset, iv_use::op_p, operand_equal_p(), optimize_bb_for_speed_p(), ivopts_data::speed, iv::step, stmt_after_increment(), double_int::to_shwi(), and tree_to_aff_combination().

Referenced by get_computation_cost().

static int get_expr_id ( )

static

Stores EXPR in DATA->inv_expr_tab, and assigns it an inv_expr_id.   

References iv_inv_expr_ent::expr, hash_table< Descriptor, Allocator >::find_slot(), iv_inv_expr_ent::hash, iv_inv_expr_ent::id, ivopts_data::inv_expr_id, ivopts_data::inv_expr_tab, and iterative_hash_expr().

Referenced by determine_use_iv_cost_condition(), and get_loop_invariant_expr_id().

static struct iv_ca* get_initial_solution ( )

staticread

Finds an initial assignment of candidates to uses.   

References iv_ca_free(), iv_ca_new(), n_iv_uses(), and try_add_cand_for().

Referenced by find_optimal_iv_set_1().

static struct iv* get_iv ( )

staticread

Finds induction variable declaration for VAR.   

References build_int_cst(), ivopts_data::current_loop, flow_bb_inside_loop_p(), gimple_bb(), version_info::iv, name_info(), and set_iv().

Referenced by determine_set_costs(), extract_cond_operands(), find_interesting_uses_address(), find_interesting_uses_op(), find_interesting_uses_stmt(), idx_find_step(), and mark_bivs().

static int get_loop_invariant_expr_id ( struct ivopts_data *  data, tree  ubase, tree  cbase, HOST_WIDE_INT  ratio, bool  address_p  )

static

Returns the pseudo expr id if expression UBASE - RATIO * CBASE
   requires a new compiler generated temporary.  Returns -1 otherwise.
   ADDRESS_P is a flag indicating if the expression is for address
   computation.   

References aff_combination_add(), aff_combination_scale(), aff_combination_to_tree(), compare_aff_trees(), iv_inv_expr_ent::expr, double_int::from_shwi(), get_expr_id(), host_integerp(), is_gimple_min_invariant(), operand_equal_p(), and tree_to_aff_combination().

Referenced by get_computation_cost_at().

static bool get_shiftadd_cost ( tree  expr, enum machine_mode  mode, comp_cost  cost0, comp_cost  cost1, tree  mult, bool  speed, comp_cost *  cost  )

static

References add_costs(), exact_log2(), force_expr_to_var_cost(), int_cst_value(), is_gimple_val(), new_cost(), shiftadd_cost(), shiftsub0_cost(), and shiftsub1_cost().

Referenced by force_expr_to_var_cost().

static struct cost_pair* get_use_iv_cost ( struct ivopts_data *  data, struct iv_use *  use, struct iv_cand *  cand  )

staticread

Gets cost of (USE, CANDIDATE) pair.   

References cost_pair::cand, ivopts_data::consider_all_candidates, iv_use::cost_map, iv_cand::id, and iv_use::n_map_members.

Referenced by iv_ca_add_use(), iv_ca_extend(), iv_ca_narrow(), rewrite_use_compare(), and try_add_cand_for().

static tree get_use_type ( )

static

Return the type of USE.   

References iv::base, build_pointer_type(), iv_use::iv, iv_use::op_p, iv_use::type, type(), and USE_ADDRESS.

Referenced by get_computation_at().

static bool idx_contains_abnormal_ssa_name_p ( tree  base, tree *  index, void *  data  )

static

Returns false if BASE or INDEX contains a ssa name that occurs in an
   abnormal phi node.  Callback for for_each_index.   

References abnormal_ssa_name_p().

Referenced by contains_abnormal_ssa_name_p().

static bool idx_find_step ( )

static

References array_ref_element_size(), array_ref_low_bound(), iv::base, component_ref_field_offset(), convert_affine_scev(), ivopts_data::current_loop, expr_invariant_in_loop_p(), get_iv(), integer_zerop(), ifs_ivopts_data::ivopts_data, iv::step, ifs_ivopts_data::step, and ifs_ivopts_data::stmt.

Referenced by find_interesting_uses_address().

static bool idx_record_use ( tree  base, tree *  idx, void *  vdata  )

static

Records use in index IDX.  Callback for for_each_index.  Ivopts data
   object is passed to it in DATA.   

References array_ref_element_size(), array_ref_low_bound(), and find_interesting_uses_op().

Referenced by find_interesting_uses_address().

static bool infinite_cost_p ( )

static

Returns true if COST is infinite.   

References comp_cost::cost.

Referenced by autoinc_possible_for_pair(), determine_use_iv_cost_address(), determine_use_iv_cost_condition(), determine_use_iv_cost_generic(), determine_use_iv_costs(), set_use_iv_cost(), and try_add_cand_for().

static void iv_ca_add_use ( struct ivopts_data *  data, struct iv_ca *  ivs, struct iv_use *  use, bool  important_candidates  )

static

Extend set IVS by expressing USE by some of the candidates in it
   if possible. All important candidates will be considered
   if IMPORTANT_CANDIDATES is true.   

References iv_ca::bad_uses, iv_ca::cands, cheaper_cost_pair(), get_use_iv_cost(), iv_use::id, ivopts_data::important_candidates, iv_ca_set_cp(), iv_cand(), and iv_ca::upto.

Referenced by try_add_cand_for().

static struct cost_pair* iv_ca_cand_for_use ( )

staticread

Returns candidate by that USE is expressed in IVS.   

References iv_ca::cand_for_use, and iv_use::id.

Referenced by find_optimal_iv_set(), iv_ca_delta_commit(), iv_ca_dump(), iv_ca_extend(), iv_ca_narrow(), and try_add_cand_for().

static bool iv_ca_cand_used_p ( )

static

Returns true if CAND is used in IVS.   

References iv_cand::id, and iv_ca::n_cand_uses.

Referenced by try_add_cand_for(), and try_improve_iv_set().

static comp_cost iv_ca_cost ( )

static

Get cost for assignment IVS.   

References iv_ca::bad_uses, iv_ca::cost, and infinite_cost.

Referenced by find_optimal_iv_set(), iv_ca_dump(), iv_ca_extend(), iv_ca_narrow(), iv_ca_prune(), try_add_cand_for(), and try_improve_iv_set().

static struct iv_ca_delta* iv_ca_delta_add ( struct iv_use *  use, struct cost_pair *  old_cp, struct cost_pair *  new_cp, struct iv_ca_delta *  next_change  )

staticread

Creates change of expressing USE by NEW_CP instead of OLD_CP and chains
   it before NEXT_CHANGE.   

References iv_ca_delta::new_cp, iv_ca_delta::next_change, iv_ca_delta::old_cp, and iv_ca_delta::use.

Referenced by iv_ca_extend(), iv_ca_narrow(), and try_add_cand_for().

static void iv_ca_delta_commit ( struct ivopts_data *  data, struct iv_ca *  ivs, struct iv_ca_delta *  delta, bool  forward  )

static

Commit changes in DELTA to IVS.  If FORWARD is false, the changes are
   reverted instead.   

References iv_ca_cand_for_use(), iv_ca_delta_reverse(), iv_ca_set_cp(), iv_ca_delta::new_cp, iv_ca_delta::next_change, iv_ca_delta::old_cp, and iv_ca_delta::use.

Referenced by iv_ca_extend(), iv_ca_narrow(), iv_ca_prune(), try_add_cand_for(), and try_improve_iv_set().

static void iv_ca_delta_free ( )

static

Free the list of changes DELTA.   

References free(), and iv_ca_delta::next_change.

Referenced by iv_ca_narrow(), iv_ca_prune(), try_add_cand_for(), and try_improve_iv_set().

static struct iv_ca_delta* iv_ca_delta_join ( )

staticread

Joins two lists of changes L1 and L2.  Destructive -- old lists
   are rewritten.   

References last, and iv_ca_delta::next_change.

Referenced by iv_ca_prune(), and try_improve_iv_set().

static struct iv_ca_delta* iv_ca_delta_reverse ( )

staticread

Reverse the list of changes DELTA, forming the inverse to it.   

References iv_ca_delta::new_cp, iv_ca_delta::next_change, and iv_ca_delta::old_cp.

Referenced by iv_ca_delta_commit().

static void iv_ca_dump ( )

static

Dumps IVS to FILE.   

References bitmap_print(), cost_pair::cand, iv_ca::cand_cost, iv_ca::cand_use_cost, iv_ca::cands, comp_cost::complexity, comp_cost::cost, cost_pair::cost, iv_ca::cost, iv_use::id, iv_cand::id, iv_ca_cand_for_use(), iv_ca_cost(), iv_use(), ivopts_data::max_inv_id, iv_ca::n_invariant_uses, pref, and iv_ca::upto.

Referenced by find_optimal_iv_set_1().

static comp_cost iv_ca_extend ( struct ivopts_data *  data, struct iv_ca *  ivs, struct iv_cand *  cand, struct iv_ca_delta **  delta, unsigned *  n_ivs, bool  min_ncand  )

static

Try changing candidate in IVS to CAND for each use.  Return cost of the
   new set, and store differences in DELTA.  Number of induction variables
   in the new set is stored to N_IVS. MIN_NCAND is a flag. When it is true
   the function will try to find a solution with mimimal iv candidates.   

References cost_pair::cand, cheaper_cost_pair(), cost_pair::cost, get_use_iv_cost(), iv_ca_cand_for_use(), iv_ca_cost(), iv_ca_delta_add(), iv_ca_delta_commit(), iv_ca_has_deps(), iv_ca_n_cands(), iv_use(), and iv_ca::upto.

Referenced by try_add_cand_for(), and try_improve_iv_set().

static void iv_ca_free ( )

static

Free memory occupied by the set IVS.   

References free().

Referenced by find_optimal_iv_set(), get_initial_solution(), and tree_ssa_iv_optimize_loop().

static bool iv_ca_has_deps ( )

static

Returns true if all dependences of CP are among invariants in IVS.   

References cost_pair::depends_on, and iv_ca::n_invariant_uses.

Referenced by iv_ca_extend(), and iv_ca_narrow().

static unsigned iv_ca_n_cands ( )

static

Returns number of induction variable candidates in the set IVS.   

References iv_ca::n_cands.

Referenced by iv_ca_extend().

static comp_cost iv_ca_narrow ( struct ivopts_data *  data, struct iv_ca *  ivs, struct iv_cand *  cand, struct iv_ca_delta **  delta  )

static

Try narrowing set IVS by removing CAND.  Return the cost of
   the new set and store the differences in DELTA.   

References cost_pair::cand, iv_ca::cands, cheaper_cost_pair(), ivopts_data::consider_all_candidates, get_use_iv_cost(), iv_cand::id, infinite_cost, iv_ca_cand_for_use(), iv_ca_cost(), iv_ca_delta_add(), iv_ca_delta_commit(), iv_ca_delta_free(), iv_ca_has_deps(), iv_cand(), iv_use(), n_iv_uses(), and iv_use::related_cands.

Referenced by iv_ca_prune().

static struct iv_ca* iv_ca_new ( )

staticread

Allocates new iv candidates assignment.   

References iv_ca::bad_uses, iv_ca::cand_cost, iv_ca::cand_for_use, iv_ca::cand_use_cost, iv_ca::cands, iv_ca::cost, ivopts_data::inv_expr_id, ivopts_data::max_inv_id, iv_ca::n_cand_uses, iv_ca::n_cands, iv_ca::n_invariant_uses, n_iv_cands(), n_iv_uses(), iv_ca::n_regs, no_cost, iv_ca::num_used_inv_expr, iv_ca::upto, and iv_ca::used_inv_expr.

Referenced by get_initial_solution().

static comp_cost iv_ca_prune ( struct ivopts_data *  data, struct iv_ca *  ivs, struct iv_cand *  except_cand, struct iv_ca_delta **  delta  )

static

Try optimizing the set of candidates IVS by removing candidates different
   from to EXCEPT_CAND from it.  Return cost of the new set, and store
   differences in DELTA.   

References iv_ca::cands, compare_costs(), iv_ca_cost(), iv_ca_delta_commit(), iv_ca_delta_free(), iv_ca_delta_join(), iv_ca_narrow(), and iv_cand().

Referenced by try_improve_iv_set().

static void iv_ca_recount_cost ( )

static

Computes the cost field of IVS structure.   

References iv_ca::cand_cost, iv_ca::cand_use_cost, comp_cost::cost, cost_pair::cost, iv_ca::cost, ivopts_global_cost_for_size(), iv_ca::n_regs, and iv_ca::num_used_inv_expr.

Referenced by iv_ca_set_cp(), and iv_ca_set_no_cp().

static void iv_ca_set_add_invariants ( )

static

Add invariants in set INVS to set IVS.   

References iv_ca::n_invariant_uses, and iv_ca::n_regs.

Referenced by iv_ca_set_cp().

static void iv_ca_set_cp ( struct ivopts_data *  data, struct iv_ca *  ivs, struct iv_use *  use, struct cost_pair *  cp  )

static

Set cost pair for USE in set IVS to CP.   

References add_costs(), iv_ca::bad_uses, bitmap_set_bit(), cost_pair::cand, iv_ca::cand_cost, iv_ca::cand_for_use, iv_ca::cand_use_cost, iv_ca::cands, cost_pair::cost, cost_pair::depends_on, iv_use::id, iv_cand::id, cost_pair::inv_expr_id, iv_ca_recount_cost(), iv_ca_set_add_invariants(), iv_ca_set_no_cp(), iv_ca::n_cand_uses, iv_ca::n_cands, iv_ca::n_regs, iv_ca::num_used_inv_expr, and iv_ca::used_inv_expr.

Referenced by iv_ca_add_use(), iv_ca_delta_commit(), and try_add_cand_for().

static void iv_ca_set_no_cp ( struct ivopts_data *  data, struct iv_ca *  ivs, struct iv_use *  use  )

static

Set USE not to be expressed by any candidate in IVS.   

References iv_ca::bad_uses, bitmap_clear_bit(), cost_pair::cand, iv_ca::cand_cost, iv_ca::cand_for_use, iv_ca::cand_use_cost, iv_ca::cands, cost_pair::cost, cost_pair::depends_on, iv_use::id, iv_cand::id, cost_pair::inv_expr_id, iv_ca_recount_cost(), iv_ca_set_remove_invariants(), iv_ca::n_cand_uses, iv_ca::n_cands, iv_ca::n_regs, iv_ca::num_used_inv_expr, sub_costs(), and iv_ca::used_inv_expr.

Referenced by iv_ca_set_cp(), and try_add_cand_for().

static void iv_ca_set_remove_invariants ( )

static

Remove invariants in set INVS to set IVS.   

References iv_ca::n_invariant_uses, and iv_ca::n_regs.

Referenced by iv_ca_set_no_cp().

static struct iv_cand* iv_cand ( )

staticread

Ith candidate recorded in DATA.   

References ivopts_data::iv_candidates.

Referenced by add_candidate_1(), create_new_ivs(), determine_iv_costs(), determine_use_iv_costs(), free_loop_data(), iv_ca_add_use(), iv_ca_narrow(), iv_ca_prune(), record_important_candidates(), set_autoinc_for_original_candidates(), try_add_cand_for(), and try_improve_iv_set().

static enum tree_code iv_elimination_compare ( )

static

Returns the comparison operator used when eliminating the iv USE.   

References ivopts_data::current_loop, edge_def::dest, edge_def::flags, flow_bb_inside_loop_p(), gimple_bb(), and iv_use::stmt.

Referenced by may_eliminate_iv().

static bool iv_elimination_compare_lt ( struct ivopts_data *  data, struct iv_cand *  cand, enum tree_code *  comp_p, struct tree_niter_desc *  niter  )

static

Tries to replace loop exit by one formulated in terms of a LT_EXPR
   comparison with CAND.  NITER describes the number of iterations of
   the loops.  If successful, the comparison in COMP_P is altered accordingly.

   We aim to handle the following situation:

   sometype *base, *p;
   int a, b, i;

   i = a;
   p = p_0 = base + a;

   do
     {
       bla (*p);
       p++;
       i++;
     }
   while (i < b);

   Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1.
   We aim to optimize this to

   p = p_0 = base + a;
   do
     {
       bla (*p);
       p++;
     }
   while (p < p_0 - a + b);

   This preserves the correctness, since the pointer arithmetics does not
   overflow.  More precisely:

   1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there is no
      overflow in computing it or the values of p.
   2) if a + 1 > b, then we need to verify that the expression p_0 - a does not
      overflow.  To prove this, we use the fact that p_0 = base + a.   

References aff_combination_add(), aff_combination_scale(), comp, cst_and_fits_in_hwi(), difference_cannot_overflow_p(), HOST_WIDE_INT, int_cst_value(), integer_onep(), invert_tree_comparison(), IP_ORIGINAL, ivopts_data::loop_single_exit_p, tree_niter_desc::may_be_zero, affine_tree_combination::n, tree_niter_desc::niter, nowrap_type_p(), affine_tree_combination::offset, offset, and tree_to_aff_combination().

Referenced by may_eliminate_iv().

static tree iv_period ( )

static

Returns period of induction variable iv.   

References build_low_bits_mask(), num_ending_zeros(), iv::step, tree_low_cst(), type(), and unsigned_type_for().

Referenced by may_eliminate_iv().

static struct iv_use* iv_use ( )

staticread

Ith use recorded in DATA.   

References ivopts_data::iv_uses.

Referenced by add_derived_ivs_candidates(), alloc_use_cost_map(), determine_use_iv_costs(), dump_uses(), find_interesting_uses_op(), find_optimal_iv_set(), free_loop_data(), iv_ca_dump(), iv_ca_extend(), iv_ca_narrow(), record_important_candidates(), remove_unused_ivs(), rewrite_uses(), and set_autoinc_for_original_candidates().

static unsigned ivopts_global_cost_for_size ( )

static

Calculates cost for having SIZE induction variables.   

References ivopts_data::body_includes_call, estimate_reg_pressure_cost(), ivopts_data::regs_used, and ivopts_data::speed.

Referenced by determine_set_costs(), and iv_ca_recount_cost().

static bool loop_body_includes_call ( )

static

Returns true if the loop body BODY includes any function calls.   

References gimple_call_fndecl(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), is_gimple_call(), and is_inexpensive_builtin().

Referenced by tree_ssa_iv_optimize_loop().

static void mark_bivs ( )

static

Marks basic ivs.   

References iv::biv_p, ivopts_data::current_loop, basic_block_def::flags, get_iv(), gimple_bb(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), loop::header, basic_block_def::loop_father, and loop_latch_edge().

Referenced by find_induction_variables().

bool may_be_nonaddressable_p

(

)

Return true if EXPR may be non-addressable.    

References is_gimple_addressable(), is_gimple_reg(), and may_be_nonaddressable_p().

static bool may_be_unaligned_p ( )

static

Returns true if memory reference REF with step STEP may be unaligned.   

References get_inner_reference(), get_object_alignment(), highest_pow2_factor(), and HOST_WIDE_INT.

Referenced by find_interesting_uses_address().

static bool may_eliminate_iv ( struct ivopts_data *  data, struct iv_use *  use, struct iv_cand *  cand, tree *  bound, enum tree_code *  comp  )

static

Check whether it is possible to express the condition in USE by comparison
   of candidate CAND.  If so, store the value compared with to BOUND, and the
   comparison operator to COMP.   

References aff_combination_to_tree(), cand_value_at(), CDI_DOMINATORS, ivopts_data::current_loop, edge_def::dest, dominated_by_p(), expression_expensive_p(), flow_bb_inside_loop_p(), gimple_bb(), integer_zerop(), iv_elimination_compare(), iv_elimination_compare_lt(), iv_period(), last_stmt(), loop::latch, ivopts_data::loop_single_exit_p, tree_niter_desc::max, max_loop_iterations(), tree_niter_desc::may_be_zero, tree_niter_desc::niter, niter_for_exit(), iv_use::stmt, stmt_after_increment(), tree_int_cst_lt(), tree_to_double_int(), and double_int::ugt().

Referenced by determine_use_iv_cost_condition().

bool multiplier_allowed_in_address_p	(	HOST_WIDE_INT	ratio,
		enum machine_mode	mode,
		addr_space_t	as
	)

Returns true if multiplying by RATIO is allowed in an address.  Test the
   validity for a memory reference accessing memory of mode MODE in
   address space AS.   

References bitmap_bit_p(), bitmap_clear(), bitmap_set_bit(), dump_file, dump_flags, gen_int_mode(), gen_raw_REG(), HOST_WIDE_INT, memory_address_addr_space_p(), sbitmap_alloc(), and targetm.

Referenced by get_address_cost(), get_computation_cost_at(), and most_expensive_mult_to_index().

static unsigned n_iv_cands ( )

inlinestatic

Number of candidates recorded in DATA.   

References ivopts_data::iv_candidates.

Referenced by add_candidate_1(), alloc_use_cost_map(), determine_iv_costs(), determine_use_iv_costs(), free_loop_data(), iv_ca_new(), record_important_candidates(), set_autoinc_for_original_candidates(), and try_improve_iv_set().

static unsigned n_iv_uses ( )

inlinestatic

Number of uses recorded in DATA.   

References ivopts_data::iv_uses.

Referenced by add_derived_ivs_candidates(), alloc_use_cost_map(), determine_use_iv_costs(), dump_uses(), find_optimal_iv_set(), free_loop_data(), get_initial_solution(), iv_ca_narrow(), iv_ca_new(), record_important_candidates(), record_use(), remove_unused_ivs(), rewrite_uses(), set_autoinc_for_original_candidates(), and tree_ssa_iv_optimize_loop().

static struct version_info* name_info ( )

staticread

Returns the info for ssa name NAME.   

References ver_info().

Referenced by create_new_iv(), find_depends(), get_iv(), record_invariant(), rewrite_use_nonlinear_expr(), and set_iv().

static comp_cost new_cost ( )

static

Returns description of computation cost of expression whose runtime
   cost is RUNTIME and complexity corresponds to COMPLEXITY.   

References comp_cost::complexity, and comp_cost::cost.

Referenced by attempt_change(), combine_validate_cost(), force_expr_to_var_cost(), get_address_cost(), get_computation_cost_at(), get_shiftadd_cost(), split_address_cost(), and try_replace_in_use().

static struct tree_niter_desc* niter_for_exit ( )

staticread

Returns the structure describing number of iterations determined from
    EXIT of DATA->current_loop, or NULL if something goes wrong.   

References contains_abnormal_ssa_name_p(), ivopts_data::current_loop, tree_niter_desc::niter, ivopts_data::niters, number_of_iterations_exit(), pointer_map_contains(), pointer_map_create(), and pointer_map_insert().

Referenced by may_eliminate_iv(), and niter_for_single_dom_exit().

static struct tree_niter_desc* niter_for_single_dom_exit ( )

staticread

Returns the structure describing number of iterations determined from
   single dominating exit of DATA->current_loop, or NULL if something
   goes wrong.   

References ivopts_data::current_loop, niter_for_exit(), and single_dom_exit().

Referenced by find_induction_variables().

struct loop* outermost_invariant_loop_for_expr ( )

read

Returns the outermost loop EXPR is obviously invariant in
   relative to the loop LOOP, i.e. if all its operands are defined
   outside of the returned loop.  Returns NULL if EXPR is not
   even obviously invariant in LOOP.   

References flow_bb_inside_loop_p(), gimple_bb(), is_gimple_min_invariant(), len, loop_depth(), basic_block_def::loop_father, outermost_invariant_loop_for_expr(), and superloop_at_depth().

static int parm_decl_cost ( )

static

References ivopts_data::body_includes_call, and tree_niter_desc::bound.

Referenced by determine_use_iv_cost_condition().

static tree prepare_decl_rtl ( )

static

Prepares decl_rtl for variables referred in *EXPR_P.  Callback for
   walk_tree.  DATA contains the actual fake register number.   

References decl_rtl_to_reset, gen_raw_REG(), handled_component_p(), and produce_memory_decl_rtl().

Referenced by computation_cost().

static rtx produce_memory_decl_rtl ( )

static

Produce DECL_RTL for object obj so it looks like it is stored in memory.   

References gen_raw_REG(), gen_rtx_MEM(), set_mem_addr_space(), and targetm.

Referenced by force_expr_to_var_cost(), and prepare_decl_rtl().

static comp_cost ptr_difference_cost ( struct ivopts_data *  data, tree  e1, tree  e2, bool *  symbol_present, bool *  var_present, unsigned HOST_WIDE_INT *  offset, bitmap *  depends_on  )

static

Estimates cost of expressing difference of addresses E1 - E2 as
   var + symbol + offset.  The value of offset is added to OFFSET,
   SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
   part is missing.  DEPENDS_ON is a set of the invariants the computation
   depends on.   

References aff_combination_add(), aff_combination_scale(), aff_combination_to_tree(), force_var_cost(), HOST_WIDE_INT, integer_zerop(), no_cost, ptr_difference_const(), signed_type_for(), split_address_cost(), tree_to_aff_combination(), and type().

Referenced by difference_cost().

static void record_important_candidates ( )

static

Record important candidates and add them to related_cands bitmaps
   if needed.   

References bitmap_ior_into(), bitmap_set_bit(), ivopts_data::consider_all_candidates, iv_cand::important, ivopts_data::important_candidates, iv_cand(), iv_use(), n_iv_cands(), n_iv_uses(), and iv_use::related_cands.

Referenced by find_iv_candidates().

static void record_invariant ( )

static

Checks whether OP is a loop-level invariant and if so, records it.
   NONLINEAR_USE is true if the invariant is used in a way we do not
   handle specially.   

References bitmap_set_bit(), ivopts_data::current_loop, flow_bb_inside_loop_p(), gimple_bb(), version_info::has_nonlin_use, version_info::inv_id, ivopts_data::max_inv_id, version_info::name, name_info(), ivopts_data::relevant, and virtual_operand_p().

Referenced by find_interesting_uses_op(), and find_invariants_stmt().

static struct iv_use* record_use ( struct ivopts_data *  data, tree *  use_p, struct iv *  iv, gimple  stmt, enum use_type  use_type  )

staticread

Records a use of type USE_TYPE at *USE_P in STMT whose value is IV.   

References dump_file, dump_flags, dump_use(), iv_use::id, iv_use::iv, ivopts_data::iv_uses, n_iv_uses(), iv_use::op_p, iv_use::related_cands, iv::ssa_name, iv_use::stmt, and iv_use::type.

Referenced by find_interesting_uses_address(), find_interesting_uses_cond(), and find_interesting_uses_op().

static void remove_unused_ivs ( )

static

Removes the ivs that are not used after rewriting.   

References iv::base, bitmap_set_bit(), comp, count, ivopts_data::current_loop, get_computation_at(), gimple_debug_bind_get_value(), gimple_debug_bind_p(), gsi_after_labels(), gsi_for_stmt(), gsi_insert_before(), GSI_SAME_STMT, iv::have_use_for, integer_zerop(), version_info::inv_id, version_info::iv, iv_use::iv, iv_use(), memset(), n_iv_uses(), operand_equal_p(), version_info::preserve_biv, release_defs_bitset(), ivopts_data::relevant, iv_use::selected, iv::ssa_name, iv::step, update_stmt(), and ver_info().

Referenced by tree_ssa_iv_optimize_loop().

static void rewrite_use ( )

static

Rewrites USE using candidate CAND.   

References rewrite_use_address(), rewrite_use_compare(), rewrite_use_nonlinear_expr(), iv_use::stmt, iv_use::type, update_stmt(), USE_ADDRESS, USE_COMPARE, and USE_NONLINEAR_EXPR.

Referenced by rewrite_uses().

static void rewrite_use_address ( struct ivopts_data *  data, struct iv_use *  use, struct iv_cand *  cand  )

static

Rewrites USE (address that is an iv) using candidate CAND.   

References adjust_iv_update_pos(), copy_ref_info(), create_mem_ref(), ivopts_data::current_loop, get_computation_aff(), gsi_for_stmt(), iv_use::op_p, reference_alias_ptr_type(), ivopts_data::speed, iv_use::stmt, unshare_aff_combination(), and var_at_stmt().

Referenced by rewrite_use().

static void rewrite_use_compare ( struct ivopts_data *  data, struct iv_use *  use, struct iv_cand *  cand  )

static

Rewrites USE (the condition such that one of the arguments is an iv) using
   candidate CAND.   

References cost_pair::comp, comp, ivopts_data::current_loop, dump_file, dump_flags, extract_cond_operands(), force_gimple_operand(), force_gimple_operand_gsi(), get_computation(), get_use_iv_cost(), gimple_cond_set_code(), gimple_cond_set_lhs(), gimple_cond_set_rhs(), gsi_for_stmt(), gsi_insert_seq_on_edge_immediate(), GSI_SAME_STMT, loop_preheader_edge(), print_gimple_stmt(), iv_use::stmt, unshare_expr(), cost_pair::value, and var_at_stmt().

Referenced by rewrite_use().

static void rewrite_use_nonlinear_expr ( struct ivopts_data *  data, struct iv_use *  use, struct iv_cand *  cand  )

static

Rewrites USE (definition of iv used in a nonlinear expression)
   using candidate CAND.   

References comp, ivopts_data::current_loop, duplicate_ssa_name_ptr_info(), expr_invariant_in_loop_p(), force_gimple_operand_gsi(), get_computation(), get_gimple_rhs_num_ops(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_assign_set_rhs_from_tree(), gimple_num_ops(), gsi_after_labels(), gsi_for_stmt(), gsi_insert_before(), GSI_SAME_STMT, gsi_stmt(), IP_ORIGINAL, is_gimple_assign(), mark_ptr_info_alignment_unknown(), name_info(), remove_phi_node(), iv_use::stmt, and valid_gimple_rhs_p().

Referenced by rewrite_use().

static void rewrite_uses ( )

static

Rewrite the uses using the selected induction variables.   

References iv_use(), n_iv_uses(), rewrite_use(), and iv_use::selected.

Referenced by tree_ssa_iv_optimize_loop().

static unsigned seq_cost ( )

static

Returns estimate on cost of computing SEQ.   

References cost_pair::cost, and set_src_cost().

Referenced by computation_cost(), and get_address_cost().

static void set_autoinc_for_original_candidates ( )

static

Examine IP_ORIGINAL candidates to see if they are incremented next to a
   use that allows autoincrement, and set their AINC_USE if possible.   

References autoinc_possible_for_pair(), gimple_uid(), IP_ORIGINAL, iv_cand(), iv_use(), n_iv_cands(), n_iv_uses(), and iv_use::stmt.

Referenced by find_iv_candidates().

static void set_iv ( )

static

Sets STEP and BASE for induction variable IV.   

References alloc_iv(), bitmap_set_bit(), version_info::iv, name_info(), ivopts_data::relevant, and iv::ssa_name.

Referenced by find_bivs(), find_givs_in_stmt(), and get_iv().

static void set_use_iv_cost ( struct ivopts_data *  data, struct iv_use *  use, struct iv_cand *  cand, comp_cost  cost, bitmap  depends_on, tree  value, enum tree_code  comp, int  inv_expr_id  )

static

Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
   on invariants DEPENDS_ON and that the value used in expressing it
   is VALUE, and in case of iv elimination the comparison operator is COMP.   

References cost_pair::cand, cost_pair::comp, comp, ivopts_data::consider_all_candidates, cost_pair::cost, iv_use::cost_map, cost_pair::depends_on, iv_cand::id, infinite_cost_p(), cost_pair::inv_expr_id, iv_use::n_map_members, and cost_pair::value.

Referenced by determine_use_iv_cost_address(), determine_use_iv_cost_condition(), and determine_use_iv_cost_generic().

edge single_dom_exit

(

)

The single loop exit if it dominates the latch, NULL otherwise.   

References just_once_each_iteration_p(), single_exit(), and edge_def::src.

static comp_cost split_address_cost ( struct ivopts_data *  data, tree  addr, bool *  symbol_present, bool *  var_present, unsigned HOST_WIDE_INT *  offset, bitmap *  depends_on  )

static

Estimates cost of expressing address ADDR  as var + symbol + offset.  The
   value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set
   to false if the corresponding part is missing.  DEPENDS_ON is a set of the
   invariants the computation depends on.   

References fd_ivopts_data, find_depends(), get_inner_reference(), HOST_WIDE_INT, new_cost(), no_cost, and ivopts_data::speed.

Referenced by ptr_difference_cost().

static bool stmt_after_inc_pos ( )

static

Returns true if STMT if after the place where the original induction
   variable CAND is incremented.  If TRUE_IF_EQUAL is set, we return true
   if the positions are identical.   

References CDI_DOMINATORS, dominated_by_p(), gimple_bb(), and gimple_uid().

Referenced by stmt_after_increment().

static bool stmt_after_increment ( )

static

Returns true if STMT if after the place where the induction variable
   CAND is incremented in LOOP.   

References IP_AFTER_USE, IP_BEFORE_USE, IP_END, IP_NORMAL, IP_ORIGINAL, stmt_after_inc_pos(), and stmt_after_ip_normal_pos().

Referenced by cand_value_at(), get_computation_aff(), get_computation_cost_at(), may_eliminate_iv(), and var_at_stmt().

static bool stmt_after_ip_normal_pos ( )

static

Returns true if STMT is after the place where the IP_NORMAL ivs will be
   emitted in LOOP.   

References gimple_bb(), ip_normal_pos(), last_stmt(), and loop::latch.

Referenced by stmt_after_increment().

bool stmt_invariant_in_loop_p

(

)

Returns true if statement STMT is obviously invariant in LOOP,
   i.e. if all its operands on the RHS are defined outside of the LOOP.
   LOOP should not be the function body.   

References expr_invariant_in_loop_p(), gimple_get_lhs(), gimple_num_ops(), gimple_op(), and loop_depth().

static tree strip_offset ( )

static

Strips constant offsets from EXPR and stores them to OFFSET.   

References strip_offset_1().

Referenced by add_iv_value_candidates(), and difference_cost().

static tree strip_offset_1 ( tree  expr, bool  inside_addr, bool  top_compref, unsigned HOST_WIDE_INT *  offset  )

static

Strips constant offsets from EXPR and stores them to OFFSET.  If INSIDE_ADDR
   is true, assume we are inside an address.  If TOP_COMPREF is true, assume
   we are at the top-level of the processed address.   

References array_ref_element_size(), build_int_cst(), component_ref_field_offset(), copy_node(), cst_and_fits_in_hwi(), HOST_WIDE_INT, int_cst_value(), integer_zerop(), and type().

Referenced by strip_offset().

static tree strip_wrap_conserving_type_conversions ( )

static

References exp(), nowrap_type_p(), and tree_ssa_useless_type_conversion().

Referenced by expr_equal_p().

static comp_cost sub_costs ( )

static

Subtracts costs COST1 and COST2.   

References comp_cost::complexity, and comp_cost::cost.

Referenced by iv_ca_set_no_cp().

void tree_ssa_iv_optimize

(

void

)

Main entry point.  Optimizes induction variables in loops.   

References dump_file, dump_flags, flow_loop_dump(), LI_FROM_INNERMOST, tree_ssa_iv_optimize_finalize(), tree_ssa_iv_optimize_init(), and tree_ssa_iv_optimize_loop().

Referenced by tree_ssa_loop_ivopts().

static void tree_ssa_iv_optimize_finalize ( )

static

Finalizes data structures used by the iv optimization pass.  LOOPS is the
   loop tree.   

References decl_rtl_to_reset, hash_table< Descriptor, Allocator >::dispose(), free(), free_loop_data(), ivopts_data::important_candidates, ivopts_data::inv_expr_tab, ivopts_data::iv_candidates, ivopts_data::iv_uses, ivopts_data::relevant, and ivopts_data::version_info.

Referenced by tree_ssa_iv_optimize().

static void tree_ssa_iv_optimize_init ( )

static

Initializes data structures used by the iv optimization pass, stored
   in DATA.   

References hash_table< Descriptor, Allocator >::create(), decl_rtl_to_reset, ivopts_data::important_candidates, ivopts_data::inv_expr_id, ivopts_data::inv_expr_tab, ivopts_data::iv_candidates, ivopts_data::iv_uses, ivopts_data::max_inv_id, ivopts_data::niters, ivopts_data::relevant, ivopts_data::version_info, and ivopts_data::version_info_size.

Referenced by tree_ssa_iv_optimize().

static bool tree_ssa_iv_optimize_loop ( )

static

Optimizes the LOOP.  Returns true if anything changed.   

References ivopts_data::body_includes_call, changed, create_new_ivs(), ivopts_data::current_loop, edge_def::dest, determine_iv_costs(), determine_set_costs(), determine_use_iv_costs(), dump_file, dump_flags, find_induction_variables(), find_interesting_uses(), find_iv_candidates(), find_optimal_iv_set(), free(), free_loop_data(), get_loop_body(), basic_block_def::index, iv_ca_free(), last_stmt(), loop_body_includes_call(), loop_only_exit_p(), ivopts_data::loop_single_exit_p, n_iv_uses(), ivopts_data::niters, loop::num, loop::num_nodes, optimize_loop_for_speed_p(), print_gimple_stmt(), remove_unused_ivs(), renumber_gimple_stmt_uids_in_blocks(), rewrite_uses(), scev_reset(), single_dom_exit(), ivopts_data::speed, and edge_def::src.

Referenced by tree_ssa_iv_optimize().

static bool try_add_cand_for ( struct ivopts_data *  data, struct iv_ca *  ivs, struct iv_use *  use, bool  originalp  )

static

Tries to extend the sets IVS in the best possible way in order
   to express the USE.  If ORIGINALP is true, prefer candidates from
   the original set of IVs, otherwise favor important candidates not
   based on any memory object.   

References iv_ca::bad_uses, cost_pair::cand, compare_costs(), iv_use::cost_map, get_use_iv_cost(), iv_cand::important, ivopts_data::important_candidates, infinite_cost_p(), IP_ORIGINAL, iv_ca_add_use(), iv_ca_cand_for_use(), iv_ca_cand_used_p(), iv_ca_cost(), iv_ca_delta_add(), iv_ca_delta_commit(), iv_ca_delta_free(), iv_ca_extend(), iv_ca_set_cp(), iv_ca_set_no_cp(), iv_cand(), iv_use::n_map_members, and iv_ca::upto.

Referenced by get_initial_solution().

static bool try_improve_iv_set ( )

static

Tries to improve set of induction variables IVS.   

References compare_costs(), iv_ca_cand_used_p(), iv_ca_cost(), iv_ca_delta_commit(), iv_ca_delta_free(), iv_ca_delta_join(), iv_ca_extend(), iv_ca_prune(), iv_cand(), and n_iv_cands().

Referenced by find_optimal_iv_set_1().

static tree var_at_stmt ( )

static

Returns variable containing the value of candidate CAND at statement AT.   

References stmt_after_increment().

Referenced by get_computation_aff(), rewrite_use_address(), and rewrite_use_compare().

static struct version_info* ver_info ( )

staticread

Returns the info for ssa version VER.   

References ivopts_data::version_info.

Referenced by add_old_ivs_candidates(), determine_set_costs(), find_induction_variables(), find_interesting_uses(), free_loop_data(), name_info(), and remove_unused_ivs().

---

Variable Documentation

vec<tree> decl_rtl_to_reset

static

The list of trees for that the decl_rtl field must be reset is stored
   here.   

Referenced by free_loop_data(), prepare_decl_rtl(), tree_ssa_iv_optimize_finalize(), and tree_ssa_iv_optimize_init().

struct ivopts_data* fd_ivopts_data

static

Records invariants in *EXPR_P.  Callback for walk_tree.  DATA contains
   the bitmap to that we should store it.   

Referenced by add_candidate_1(), determine_use_iv_cost_condition(), find_depends(), force_var_cost(), and split_address_cost().

const comp_cost infinite_cost = {INFTY, INFTY}

static

Referenced by determine_use_iv_cost_address(), determine_use_iv_cost_condition(), find_optimal_iv_set(), get_computation_cost_at(), iv_ca_cost(), and iv_ca_narrow().

const comp_cost no_cost = {0, 0}

static

Referenced by difference_cost(), force_expr_to_var_cost(), iv_ca_new(), ptr_difference_cost(), and split_address_cost().