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 ()
void	dump_use ()
void	dump_uses ()
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 ()
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, 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.

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.

     If we insert the increment in any position other than the standard
     ones, we must ensure that it is incremented once per iteration.
     It must not be in an inner nested loop, or one side of an if
     statement.

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.

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.

     For non-original variables, make sure their values are computed in a type
     that does not invoke undefined behavior on overflows (since in general,
     we cannot prove that these induction variables are non-wrapping).

static comp_cost add_costs ( )

static

   Adds costs COST1 and COST2.

static void add_derived_ivs_candidates ( )

static

   Adds candidates based on the uses.

             Just add the ivs based on the value of the iv used here.

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.

     The same, but with initial value zero.  Make such variable important,
     since it is generic enough so that possibly many uses may be based
     on it.

     Third, try removing the constant offset.  Make sure to even
     add a candidate for &a[0] vs. (T *)&a.

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

static void add_old_iv_candidates ( )

static

   Adds candidates bases on the old induction variable IV.

     The same, but with initial value zero.

         Additionally record the possibility of leaving the original iv
         untouched.

Referenced by allow_ip_end_pos_p().

static void add_old_ivs_candidates ( )

static

   Adds candidates based on the old induction variables.

static void add_standard_iv_candidates ( )

static

   Adds standard iv candidates.

     The same for a double-integer type if it is still fast enough.

     The same for a double-integer type if it is still fast enough.

static void adjust_iv_update_pos ( )

static

@verbatim

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;

     Only handle conditional statement for now.

References free_tree_niter_desc(), ivopts_data::niters, pointer_map_destroy(), and pointer_map_traverse().

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.

static struct iv* alloc_iv ( )

staticread

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

References contains_abnormal_ssa_name_p(), determine_biv_step(), expand_simple_operations(), gsi_stmt(), and loop_preheader_edge().

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.

             Round up to the power of two, so that moduling by it is fast.

References cost_pair::cost, and set_src_cost().

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 add_old_iv_candidates(), iv::biv_p, integer_zerop(), version_info::iv, iv::step, and ver_info().

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.

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.

Referenced by get_expr_id().

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.

static bool cheaper_cost_pair ( )

static

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

     In case the costs are the same, prefer the cheaper candidate.

Referenced by iv_ca_set_cp().

static bool compare_aff_trees ( )

static

   Returns true if AFF1 and AFF2 are identical.

static int compare_costs ( )

static

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

Referenced by iv_ca_extend().

static unsigned computation_cost ( )

static

   Determines cost of the computation of EXPR.

     Avoid using hard regs in ways which may be unsupported.

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.

bool contains_abnormal_ssa_name_p ( )

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

         Fallthru.

Referenced by alloc_iv().

static void create_new_iv ( )

static

   Creates a new induction variable corresponding to CAND.

         fall through

         Mark that the iv is preserved.

         Rewrite the increment so that it uses var_before directly.

static void create_new_ivs ( )

static

   Creates new induction variables described in SET.

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.

     If this is a pointer casted to any type, we need to determine
     the base object for the pointer; so handle conversions before
     throwing away non-pointer expressions.

         Pointer addition is done solely using POINTER_PLUS_EXPR.

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

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.

Referenced by alloc_iv().

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.

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.

static void determine_iv_cost ( )

static

   Determines cost of the candidate CAND.

     There are two costs associated with the candidate -- its increment
     and its initialization.  The second is almost negligible for any loop
     that rolls enough, so we take it just very little into account.

     It will be exceptional that the iv register happens to be initialized with
     the proper value at no cost.  In general, there will at least be a regcopy
     or a const set.

     Prefer the original ivs unless we may gain something by replacing it.
     The reason is to make debugging simpler; so this is not relevant for
     artificial ivs created by other optimization passes.

     Prefer not to insert statements into latch unless there are some
     already (so that we do not create unnecessary jumps).

static void determine_iv_costs ( )

static

   Determines costs of computation of the candidates.

Referenced by rewrite_use_compare().

static void determine_set_costs ( )

static

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

References iv_ca::n_invariant_uses.

Referenced by rewrite_use_compare().

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 dump_file, and ivopts_data::speed.

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.

         If we generated the candidate solely for exploiting autoincrement
         opportunities, and it turns out it can't be used, set the cost to
         infinity to make sure we ignore it.

References comp, HOST_WIDE_INT, IP_ORIGINAL, ivopts_data::loop_single_exit_p, tree_niter_desc::niter, nowrap_type_p(), and offset.

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.

     Only consider real candidates.

     Try iv elimination.

         If we replace a loop condition 'i < n' with 'p < base + n',
         depends_on_elim will have 'base' and 'n' set, which implies
         that both 'base' and 'n' will be live during the loop.  More likely,
         'base + n' will be loop invariant, resulting in only one live value
         during the loop.  So in that case we clear depends_on_elim and set
        elim_inv_expr_id instead.

         The bound is a loop invariant, so it will be only computed
         once.

     Try expressing the original giv.  If it is compared with an invariant,
     note that we cannot get rid of it.

     When the condition is a comparison of the candidate IV against
     zero, prefer this IV.

     TODO: The constant that we're subtracting from the cost should
     be target-dependent.  This information should be added to the
     target costs for each backend.

     Count the cost of the original bound as well.

     Choose the better approach, preferring the eliminated IV.

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.

     The simple case first -- if we need to express value of the preserved
     original biv, the cost is 0.  This also prevents us from counting the
     cost of increment twice -- once at this use and once in the cost of
     the candidate.

static void determine_use_iv_costs ( )

static

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

             Remove the candidates for that the cost is infinite from
             the list of related candidates.

Referenced by rewrite_use_compare().

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.

     TODO: deeper inspection may be necessary to prove the equality.

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.

Referenced by get_expr_id().

void dump_cand ( )

   Dumps information about induction variable candidate CAND to FILE.

References ver_info().

void dump_iv ( )

   Dumps information about the induction variable IV to FILE.

void dump_use ( )

   Dumps information about the USE to FILE.

References dump_bitmap().

void dump_uses ( )

   Dumps information about the uses to FILE.

static bool expr_equal_p ( )

static

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

         Fallthru.

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.

Referenced by outermost_invariant_loop_for_expr().

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.

     The objects returned when COND has constant operands.

     Exactly one of the compared values must be an iv, and the other one must
     be an invariant.

         Control variable may be on the other side.

static bool find_bivs ( )

static

   Finds basic ivs.

static tree find_depends ( )

static

Referenced by get_shiftadd_cost().

static void find_givs ( )

static

   Finds general ivs.

static void find_givs_in_bb ( )

static

   Finds general ivs in basic block BB.

References gimple_bb(), and virtual_operand_p().

static void find_givs_in_stmt ( )

static

   Finds general ivs in statement STMT.

static bool find_givs_in_stmt_scev ( )

static

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

     If STMT could throw, then do not consider STMT as defining a GIV.  
     While this will suppress optimizations, we can not safely delete this
     GIV and associated statements, even if it appears it is not used.

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

static void find_interesting_uses ( )

static

   Finds uses of the induction variables that are interesting.

Referenced by rewrite_use_compare().

static void find_interesting_uses_address ( )

static

   Finds addresses in *OP_P inside STMT.

     Do not play with volatile memory references.  A bit too conservative,
     perhaps, but safe.

     Ignore bitfields for now.  Not really something terribly complicated
     to handle.  TODO.

         Check that the base expression is addressable.  This needs
         to be done after substituting bases of IVs into it.

         Moreover, on strict alignment platforms, check that it is
         sufficiently aligned.

         Substituting bases of IVs into the base expression might
         have caused folding opportunities.

static void find_interesting_uses_cond ( )

static

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

static struct iv_use* find_interesting_uses_op ( )

staticread

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

static void find_interesting_uses_outside ( )

static

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

static void find_interesting_uses_stmt ( )

static

   Finds interesting uses of induction variables in the statement STMT.

             If the statement defines an induction variable, the uses are not
             interesting by themselves.

         TODO -- we should also handle address uses of type

         memory = call (whatever);

         and

         call (memory).

References dump_file, version_info::has_nonlin_use, version_info::inv_id, version_info::name, print_generic_expr(), and ver_info().

static void find_invariants_stmt ( )

static

   Finds and records invariants used in STMT.

static void find_iv_candidates ( )

static

   Finds the candidates for the induction variables.

     Add commonly used ivs.

     Add old induction variables.

     Add induction variables derived from uses.

     Record the important candidates.

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

static struct iv_ca* find_optimal_iv_set ( )

staticread

     Determine the cost based on a strategy that starts with original IVs,
     and try again using a strategy that prefers candidates not based
     on any IVs.

     Choose the one with the best cost.

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.

     Get the initial solution.

static comp_cost force_expr_to_var_cost	(	tree	,
		bool
	)

static

Referenced by get_shiftadd_cost().

static comp_cost force_expr_to_var_cost ( )

static

   Estimates cost of forcing expression EXPR into a variable.

         Just an arbitrary value, FIXME.

     Bound the cost by target_spill_cost.  The parts of complicated
     computations often are either loop invariant or at least can
     be shared between several iv uses, so letting this grow without
     limits would not give reasonable results.

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.

static void free_loop_data ( )

static

   Frees data allocated by the optimization of a single loop.

Referenced by rewrite_use_address().

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.

Referenced by adjust_iv_update_pos().

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.

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

         Compute the cost of various addressing modes.

                 ??? We can run into trouble with some backends by presenting
                 it with symbols which haven't been properly passed through
                 targetm.encode_section_info.  By setting the local bit, we
                 enhance the probability of things working.

             To avoid splitting addressing modes, pretend that no cse will
             follow.

         On some targets, it is quite expensive to load symbol to a register,
         which makes addresses that contain symbols look much more expensive.
         However, the symbol will have to be loaded in any case before the
         loop (and quite likely we have it in register already), so it does not
         make much sense to penalize them too heavily.  So make some final
         tweaks for the SYMBOL_PRESENT modes:

         If VAR_PRESENT is false, and the mode obtained by changing symbol to
         var is cheaper, use this mode with small penalty.
         If VAR_PRESENT is true, try whether the mode with
         SYMBOL_PRESENT = false is cheaper even with cost of addition, and
         if this is the case, use it.

References address_cost_data_s::costs, and dump_file.

static tree get_computation ( )

static

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

References memory_address_addr_space_p().

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.

         We do not have a precision to express the values of use.

     If the conversion is not noop, perform it.

     In case both UBASE and CBASE are shortened to UUTYPE from some common
     type, we achieve better folding by computing their difference in this
     wider type, and cast the result to UUTYPE.  We do not need to worry about
     overflows, as all the arithmetics will in the end be performed in UUTYPE
     anyway.

     use = ubase - ratio * cbase + ratio * var.

     We need to shift the value if we are after the increment.

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.

Referenced by rewrite_use_nonlinear_expr().

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.

Referenced by may_eliminate_iv().

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.

     Only consider real candidates.

         We do not have a precision to express the values of use.

         Do not try to express address of an object with computation based
         on address of a different object.  This may cause problems in rtl
         level alias analysis (that does not expect this to be happening,
         as this is illegal in C), and would be unlikely to be useful
         anyway.

         TODO -- add direct handling of this case.

     CSTEPI is removed from the offset in case statement is after the
     increment.  If the step is not constant, we use zero instead.
     This is a bit imprecise (there is the extra addition), but
     redundancy elimination is likely to transform the code so that
     it uses value of the variable before increment anyway,
     so it is not that much unrealistic.

     use = ubase + ratio * (var - cbase).  If either cbase is a constant
     or ratio == 1, it is better to handle this like

     ubase - ratio * cbase + ratio * var

     (also holds in the case ratio == -1, TODO.

         Check to see if any adjustment is needed.

         Clear depends on.

     If we are after the increment, the value of the candidate is higher by
     one iteration.

     Now the computation is in shape symbol + var1 + const + ratio * var2.
     (symbol/var1/const parts may be omitted).  If we are looking for an
     address, find the cost of addressing this.

     Otherwise estimate the costs for computing the expression.

     Symbol + offset should be compile-time computable so consider that they
      are added once to the variable, if present.

     Having offset does not affect runtime cost in case it is added to
     symbol, but it increases complexity.

       Just get the expression, expand it and measure the cost.

References iv_use::stmt.

static int get_expr_id ( )

static

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

References avg_loop_niter(), build_int_cst(), comp_cost::cost, ivopts_data::current_loop, difference_cost(), and int_cst_value().

static struct iv_ca* get_initial_solution ( )

staticread

   Finds an initial assignment of candidates to uses.

static struct iv* get_iv ( )

staticread

   Finds induction variable declaration for VAR.

References ivopts_data::current_loop, 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().

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.

     Strips the constant part.

     Strips the constant part.

         Now do more complex comparison

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

    Calculate the SPEED or size cost of shiftadd EXPR in MODE.  MULT is the
    the EXPR operand holding the shift.  COST0 and COST1 are the costs for
    calculating the operands of EXPR.  Returns true if successful, and returns
    the cost in COST.

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

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.

     n_map_members is a power of two, so this computes modulo.

References stmt_after_increment().

Referenced by iv_ca_add_use(), and iv_ca_set_cp().

static tree get_use_type ( )

static

   Return the type of USE.

         The base_type may be a void pointer.  Create a pointer type based on
         the mem_ref instead.

References dump_file, HOST_WIDE_INT_PRINT_DEC, address_cost_data_s::max_offset, and address_cost_data_s::min_offset.

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 ivopts_data::niters, and pointer_map_create().

static bool idx_find_step ( )

static

     If base is a component ref, require that the offset of the reference
     be invariant.

     If base is array, first check whether we will be able to move the
     reference out of the loop (in order to take its address in strength
     reduction).  In order for this to work we need both lower bound
     and step to be loop invariants.

         Moreover, for a range, the size needs to be invariant as well.

     XXX  We produce for a base of *D42 with iv->base being &x[0]
          *&x[0], which is not folded and does not trigger the
          ARRAY_REF path below.

         We only handle addresses whose step is an integer constant.

       The step for pointer arithmetics already is 1 byte.

         The index might wrap.

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.

static bool infinite_cost_p ( )

static

   Returns true if COST is infinite.

Referenced by may_eliminate_iv().

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 cost_pair::cand, iv_ca::cands, ivopts_data::consider_all_candidates, get_use_iv_cost(), iv_cand::id, iv_ca_cand_for_use(), iv_ca_has_deps(), iv_cand(), iv_use(), and n_iv_uses().

Referenced by iv_ca_delta_commit().

static struct cost_pair* iv_ca_cand_for_use ( )

staticread

   Returns candidate by that USE is expressed in IVS.

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

static bool iv_ca_cand_used_p ( )

static

   Returns true if CAND is used in IVS.

Referenced by iv_ca_extend().

static comp_cost iv_ca_cost ( )

static

   Get cost for assignment IVS.

     This was a conditional expression but it triggered a bug in
     Sun C 5.5.

Referenced by iv_ca_delta_commit(), iv_ca_extend(), and iv_ca_set_cp().

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.

Referenced by iv_ca_set_cp().

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::bad_uses, iv_ca_add_use(), iv_ca_cand_for_use(), iv_ca_cost(), and iv_ca::upto.

Referenced by iv_ca_extend(), and iv_ca_set_cp().

static void iv_ca_delta_free ( )

static

   Free the list of changes DELTA.

Referenced by iv_ca_dump(), iv_ca_extend(), and iv_ca_new().

static struct iv_ca_delta* iv_ca_delta_join ( )

staticread

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

Referenced by iv_ca_extend().

static struct iv_ca_delta* iv_ca_delta_reverse ( )

staticread

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

static void iv_ca_dump ( )

static

   Dumps IVS to FILE.

References iv_ca_delta_free().

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 compare_costs(), iv_ca_cand_used_p(), iv_ca_cost(), iv_ca_delta_commit(), iv_ca_delta_free(), iv_ca_delta_join(), iv_ca_prune(), iv_cand(), and n_iv_cands().

static void iv_ca_free ( )

static

   Free memory occupied by the set IVS.

static bool iv_ca_has_deps ( )

static

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

Referenced by iv_ca_add_use(), and iv_ca_set_cp().

static unsigned iv_ca_n_cands ( )

static

   Returns number of induction variable candidates in the set IVS.

References IP_ORIGINAL, and iv_cand().

Referenced by iv_ca_set_cp().

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.

static struct iv_ca* iv_ca_new ( )

staticread

   Allocates new iv candidates assignment.

References iv_ca_delta_free().

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.

     Recurse to possibly remove other unnecessary ivs.

Referenced by iv_ca_extend().

static void iv_ca_recount_cost ( )

static

   Computes the cost field of IVS structure.

static void iv_ca_set_add_invariants ( )

static

   Add invariants in set INVS to set IVS.

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.

             Do not count the pseudocandidates.

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.

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.

         Do not count the pseudocandidates.

static void iv_ca_set_remove_invariants ( )

static

   Remove invariants in set INVS to set IVS.

References free(), and iv_ca_delta::next_change.

static struct iv_cand* iv_cand ( )

staticread

   Ith candidate recorded in DATA.

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

static enum tree_code iv_elimination_compare ( )

static

   Returns the comparison operator used when eliminating the iv USE.

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.

     We need to know that the candidate induction variable does not overflow.
     While more complex analysis may be used to prove this, for now just
     check that the variable appears in the original program and that it
     is computed in a type that guarantees no overflows.

     Make sure that the loop iterates till the loop bound is hit, as otherwise
     the calculation of the BOUND could overflow, making the comparison
     invalid.

     We need to be able to decide whether candidate is increasing or decreasing
     in order to choose the right comparison operator.

     Check that the number of iterations matches the expected pattern:
     a + 1 > b ? 0 : b - a - 1.

         Handle a + 1 > b.

         Handle b < a + 1.

     Expected number of iterations is B - A - 1.  Check that it matches
     the actual number, i.e., that B - A - NITER = 1.

     Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
     overflow.

     Determine the new comparison operator.

static tree iv_period ( )

static

   Returns period of induction variable iv.

     Period of the iv is lcm (step, type_range)/step -1,
     i.e., N*type_range/step - 1. Since type range is power
     of two, N == (step >> num_of_ending_zeros_binary (step),
     so the final result is

       (type_range >> num_of_ending_zeros_binary (step)) - 1

static struct iv_use* iv_use ( )

staticread

   Ith use recorded in DATA.

Referenced by find_induction_variables(), iv_ca_add_use(), iv_ca_set_cp(), and rewrite_use_nonlinear_expr().

static unsigned ivopts_global_cost_for_size ( )

static

   Calculates cost for having SIZE induction variables.

     We add size to the cost, so that we prefer eliminating ivs
     if possible.

References cost_pair::depends_on.

Referenced by find_iv_candidates().

static bool loop_body_includes_call ( )

static

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

Referenced by rewrite_use_compare().

static void mark_bivs ( )

static

   Marks basic ivs.

         If the increment is in the subloop, ignore it.

bool may_be_nonaddressable_p ( )

   Return true if EXPR may be non-addressable.

         TARGET_MEM_REFs are translated directly to valid MEMs on the
         target, thus they are always addressable.

         This kind of view-conversions may wrap non-addressable objects
         and make them look addressable.  After some processing the
         non-addressability may be uncovered again, causing ADDR_EXPRs
         of inappropriate objects to be built.

         ... fall through ...

static bool may_be_unaligned_p ( )

static

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

     TARGET_MEM_REFs are translated directly to valid MEMs on the target,
     thus they are not misaligned.

     The test below is basically copy of what expr.c:normal_inner_ref
     does to check whether the object must be loaded by parts when
     STRICT_ALIGNMENT is true.

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.

     For now works only for exits that dominate the loop latch.
     TODO: extend to other conditions inside loop body.

     Determine whether we can use the variable to test the exit condition.
     This is the case iff the period of the induction variable is greater
     than the number of iterations for which the exit condition is true.

     If the number of iterations is constant, compare against it directly.

         See cand_value_at.

     If not, and if this is the only possible exit of the loop, see whether
     we can get a conservative estimate on the number of iterations of the
     entire loop and compare against that instead.

             See if we can take advantage of inferred loop bound information.

                 The loop bound is already adjusted by adding 1.

     It is unlikely that computing the number of iterations using division
     would be more profitable than keeping the original induction variable.

     Sometimes, it is possible to handle the situation that the number of
     iterations may be zero unless additional assumtions by using <
     instead of != in the exit condition.

     TODO: we could also calculate the value MAY_BE_ZERO ? 0 : NITER and
           base the exit condition on it.  However, that is often too
           expensive.

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

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.

static unsigned n_iv_cands ( )

inlinestatic

   Number of candidates recorded in DATA.

References iv::base_object, and print_generic_expr().

Referenced by iv_ca_extend().

static unsigned n_iv_uses ( )

inlinestatic

   Number of uses recorded in DATA.

References iv::base, print_generic_expr(), and iv::step.

Referenced by iv_ca_add_use(), and rewrite_use_nonlinear_expr().

static struct version_info* name_info ( )

staticread

   Returns the info for ssa name NAME.

Referenced by determine_base_object().

static comp_cost new_cost ( )

static

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

References targetm.

Referenced by do_SUBST_MODE(), insert_move_insn_before(), and reload_combine_closest_single_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.

         Try to determine number of iterations.  We cannot safely work with ssa
         names that appear in phi nodes on abnormal edges, so that we do not
         create overlapping life ranges for them (PR 27283).

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 iv::base, iv::base_object, iv::biv_p, determine_base_object(), iv::have_use_for, iv::ssa_name, iv::step, and iv::use_id.

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 array_ref_element_size(), array_ref_low_bound(), and expr_invariant_in_loop_p().

static int parm_decl_cost ( )

static

    Calculates the cost of BOUND, if it is a PARM_DECL.  A PARM_DECL must
    be copied, if is is used in the loop body and DATA->body_includes_call.

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.

         Defer handling of anonymous SSA_NAMEs to the expander.

static rtx produce_memory_decl_rtl ( )

static

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

Referenced by sub_costs().

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.

static void record_important_candidates ( )

static

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

         We will not need "related_cands" bitmaps in this case,
         so release them to decrease peak memory consumption.

         Add important candidates to the related_cands bitmaps.

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.

Referenced by 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
	)

staticread

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

     To avoid showing ssa name in the dumps, if it was not reset by the
     caller.

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

Referenced by find_induction_variables().

static void remove_unused_ivs ( )

static

   Removes the ivs that are not used after rewriting.

     Figure out an order in which to release SSA DEFs so that we don't
     release something that we'd have to propagate into a debug stmt
     afterwards.

                     We just want to determine whether to do nothing
                     (count == 0), to substitute the computed
                     expression into a single use of the SSA DEF by
                     itself (count == 1), or to use a debug temp
                     because the SSA DEF is used multiple times or as
                     part of a larger expression (count > 1).

static void rewrite_use ( )

static

   Rewrites USE using candidate CAND.

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.

     To avoid undefined overflow problems, all IV candidates use unsigned
     integer types.  The drawback is that this makes it impossible for
     create_mem_ref to distinguish an IV that is based on a memory object
     from one that represents simply an offset.

     To work around this problem, we pass a hint to create_mem_ref that
     indicates which variable (if any) in aff is an IV based on a memory
     object.  Note that we only consider the candidate.  If this is not
     based on an object, the base of the reference is in some subexpression
     of the use -- but these will use pointer types, so they are recognized
     by the create_mem_ref heuristics anyway.

References decl_rtl_to_reset, free(), and free_loop_data().

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.

     The induction variable elimination failed; just express the original
     giv.

References ivopts_data::body_includes_call, changed, 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(), free(), get_loop_body(), basic_block_def::index, last_stmt(), loop_body_includes_call(), loop_only_exit_p(), ivopts_data::loop_single_exit_p, ivopts_data::niters, loop::num, loop::num_nodes, optimize_loop_for_speed_p(), print_gimple_stmt(), renumber_gimple_stmt_uids_in_blocks(), single_dom_exit(), ivopts_data::speed, and edge_def::src.

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.

     An important special case -- if we are asked to express value of
     the original iv by itself, just exit; there is no need to
     introduce a new computation (that might also need casting the
     variable to unsigned and back).

         Check whether we may leave the computation unchanged.
         This is the case only if it does not rely on other
         computations in the loop -- otherwise, the computation
         we rely upon may be removed in remove_unused_ivs,
         thus leading to ICE.

         If we should keep the biv, do not replace it.

             We can't allow re-allocating the stmt as it might be pointed
             to still.

             As this isn't a plain copy we have to reset alignment
             information.

References iv::base, bitmap_set_bit(), 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, version_info::iv, iv_use::iv, iv_use(), memset(), n_iv_uses(), operand_equal_p(), iv_use::selected, iv::ssa_name, iv::step, and update_stmt().

static void rewrite_uses ( )

static

   Rewrite the uses using the selected induction variables.

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

static unsigned seq_cost ( )

static

   Returns estimate on cost of computing SEQ.

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.

static void set_iv ( )

static

   Sets STEP and BASE for induction variable IV.

Referenced by determine_base_object().

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.

     n_map_members is a power of two, so this computes modulo.

edge single_dom_exit ( )

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

References USE_ADDRESS, USE_COMPARE, and USE_NONLINEAR_EXPR.

Referenced by build_new_reduction(), create_loop_fn(), insn_to_prefetch_ratio_too_small_p(), loop_has_vector_phi_nodes(), and rewrite_use_compare().

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.

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.

static bool stmt_after_increment ( )

static

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

Referenced by get_use_iv_cost().

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.

static tree strip_offset ( )

static

   Strips constant offsets from EXPR and stores them to OFFSET.

static tree strip_offset_1	(	tree	expr,
		bool	inside_addr,
		bool	top_compref,
		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.

             Strip the component reference completely.

               Strip the component reference completely.

         ???  Offset operand?

     Default handling of expressions for that we want to recurse into
     the first operand.

     Inside address, we might strip the top level component references,
     thus changing type of the expression.  Handling of ADDR_EXPR
     will fix that.

static tree strip_wrap_conserving_type_conversions ( )

static

References ivopts_data::current_loop.

static comp_cost sub_costs ( )

static

   Subtracts costs COST1 and COST2.

References handled_component_p(), and produce_memory_decl_rtl().

void tree_ssa_iv_optimize ( void )

   Main entry point.  Optimizes induction variables in loops.

     Optimize the loops starting with the innermost ones.

static void tree_ssa_iv_optimize_finalize ( )

static

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

Referenced by rewrite_uses().

static void tree_ssa_iv_optimize_init ( )

static

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

Referenced by rewrite_uses().

static bool tree_ssa_iv_optimize_loop ( )

static

   Optimizes the LOOP.  Returns true if anything changed.

     For each ssa name determines whether it behaves as an induction variable
     in some loop.

     Finds interesting uses (item 1).

     Finds candidates for the induction variables (item 2).

     Calculates the costs (item 3, part 1).

     Find the optimal set of induction variables (item 3, part 2).

     Create the new induction variables (item 4, part 1).

     Rewrite the uses (item 4, part 2).

     Remove the ivs that are unused after rewriting.

     We have changed the structure of induction variables; it might happen
     that definitions in the scev database refer to some of them that were
     eliminated.

Referenced by rewrite_uses().

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.

     If ORIGINALP is true, try to find the original IV for the use.  Otherwise
     first try important candidates not based on any memory object.  Only if
     this fails, try the specific ones.  Rationale -- in loops with many
     variables the best choice often is to use just one generic biv.  If we
     added here many ivs specific to the uses, the optimization algorithm later
     would be likely to get stuck in a local minimum, thus causing us to create
     too many ivs.  The approach from few ivs to more seems more likely to be
     successful -- starting from few ivs, replacing an expensive use by a
     specific iv should always be a win.

             Already tried this.

static bool try_improve_iv_set ( )

static

   Tries to improve set of induction variables IVS.

     Try extending the set of induction variables by one.

         If we successfully added the candidate and the set is small enough,
         try optimizing it by removing other candidates.

         Try removing the candidates from the set instead.

         Nothing more we can do.

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

static tree var_at_stmt ( )

static

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

static struct version_info* ver_info ( )

staticread

   Returns the info for ssa version VER.

Referenced by allow_ip_end_pos_p(), dump_cand(), and find_interesting_uses_stmt().

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

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.

const comp_cost infinite_cost = {INFTY, INFTY}

static

const comp_cost no_cost = {0, 0}

static

Data Structures

Typedefs

Enumerations

Functions

Variables

Typedef Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation