#include "double-int.h"
#include "bitmap.h"
#include "sbitmap.h"
#include "function.h"

Include dependency graph for cfgloop.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	lpt_decision
struct	nb_iter_bound
struct	loop_exit
struct	loop
struct	loops
struct	rtx_iv
struct	niter_desc
struct	loop_iterator
struct	target_cfgloop

Macros
#define	LOOPS_NORMAL
#define	AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
#define	DLTHE_FLAG_UPDATE_FREQ
#define	DLTHE_RECORD_COPY_NUMBER
#define	DLTHE_FLAG_COMPLETTE_PEEL
#define	FOR_EACH_LOOP(LI, LOOP, FLAGS)
#define	FOR_EACH_LOOP_BREAK(LI)
#define	this_target_cfgloop (&default_target_cfgloop)
#define	target_avail_regs (this_target_cfgloop->x_target_avail_regs)
#define	target_clobbered_regs (this_target_cfgloop->x_target_clobbered_regs)
#define	target_res_regs (this_target_cfgloop->x_target_res_regs)
#define	target_reg_cost (this_target_cfgloop->x_target_reg_cost)
#define	target_spill_cost (this_target_cfgloop->x_target_spill_cost)

Typedefs
typedef struct loop *	loop_p

Enumerations
enum	lpt_dec { LPT_NONE, LPT_PEEL_COMPLETELY, LPT_PEEL_SIMPLE, LPT_UNROLL_CONSTANT, LPT_UNROLL_RUNTIME, LPT_UNROLL_STUPID }
enum	iv_extend_code { IV_SIGN_EXTEND, IV_ZERO_EXTEND, IV_UNKNOWN_EXTEND }
enum	loop_estimation { EST_NOT_COMPUTED, EST_AVAILABLE, EST_LAST }
enum	{ LOOPS_HAVE_PREHEADERS = 1, LOOPS_HAVE_SIMPLE_LATCHES = 2, LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS = 4, LOOPS_HAVE_RECORDED_EXITS = 8, LOOPS_MAY_HAVE_MULTIPLE_LATCHES = 16, LOOP_CLOSED_SSA = 32, LOOPS_NEED_FIXUP = 64, LOOPS_HAVE_FALLTHRU_PREHEADERS = 128 }
enum	{ CP_SIMPLE_PREHEADERS = 1, CP_FALLTHRU_PREHEADERS = 2 }
enum	li_flags { LI_INCLUDE_ROOT = 1, LI_FROM_INNERMOST = 2, LI_ONLY_INNERMOST = 4 }
enum	{ UAP_PEEL = 1, UAP_UNROLL = 2, UAP_UNROLL_ALL = 4 }

Functions
bool	bb_loop_header_p (basic_block)
void	init_loops_structure (struct function , struct loops , unsigned)
struct loops *	flow_loops_find (struct loops *)
void	disambiguate_loops_with_multiple_latches (void)
void	flow_loops_free (struct loops *)
void	flow_loops_dump (FILE , void()(const struct loop , FILE , int), int)
void	flow_loop_dump (const struct loop , FILE , void()(const struct loop , FILE *, int), int)
struct loop *	alloc_loop (void)
void	flow_loop_free (struct loop *)
int	flow_loop_nodes_find (basic_block, struct loop *)
unsigned	fix_loop_structure (bitmap changed_bbs)
bool	mark_irreducible_loops (void)
void	release_recorded_exits (void)
void	record_loop_exits (void)
void	rescan_loop_exit (edge, bool, bool)
void	flow_loop_tree_node_add (struct loop , struct loop )
void	flow_loop_tree_node_remove (struct loop *)
void	place_new_loop (struct function , struct loop )
void	add_loop (struct loop , struct loop )
bool	flow_loop_nested_p (const struct loop , const struct loop )
bool	flow_bb_inside_loop_p (const struct loop *, const_basic_block)
struct loop *	find_common_loop (struct loop , struct loop )
struct loop *	superloop_at_depth (struct loop *, unsigned)
int	num_loop_insns (const struct loop *)
int	average_num_loop_insns (const struct loop *)
unsigned	get_loop_level (const struct loop *)
bool	loop_exit_edge_p (const struct loop *, const_edge)
bool	loop_exits_to_bb_p (struct loop *, basic_block)
bool	loop_exits_from_bb_p (struct loop *, basic_block)
void	mark_loop_exit_edges (void)
location_t	get_loop_location (struct loop *loop)
basic_block *	get_loop_body (const struct loop *)
unsigned	get_loop_body_with_size (const struct loop , basic_block , unsigned)
basic_block *	get_loop_body_in_dom_order (const struct loop *)
basic_block *	get_loop_body_in_bfs_order (const struct loop *)
basic_block *	get_loop_body_in_custom_order (const struct loop , int()(const void , const void ))
vec< edge >	get_loop_exit_edges (const struct loop *)
edge	single_exit (const struct loop *)
edge	single_likely_exit (struct loop *loop)
unsigned	num_loop_branches (const struct loop *)
edge	loop_preheader_edge (const struct loop *)
edge	loop_latch_edge (const struct loop *)
void	add_bb_to_loop (basic_block, struct loop *)
void	remove_bb_from_loops (basic_block)
void	cancel_loop_tree (struct loop *)
void	delete_loop (struct loop *)
basic_block	create_preheader (struct loop *, int)
void	create_preheaders (int)
void	force_single_succ_latches (void)
void	verify_loop_structure (void)
bool	just_once_each_iteration_p (const struct loop *, const_basic_block)
gcov_type	expected_loop_iterations_unbounded (const struct loop *)
unsigned	expected_loop_iterations (const struct loop *)
rtx	doloop_condition_get (rtx)
bool	can_duplicate_loop_p (const struct loop *loop)
edge	create_empty_if_region_on_edge (edge, tree)
struct loop *	create_empty_loop_on_edge (edge, tree, tree, tree, tree, tree , tree , struct loop *)
struct loop *	duplicate_loop (struct loop , struct loop )
void	copy_loop_info (struct loop loop, struct loop target)
void	duplicate_subloops (struct loop , struct loop )
bool	duplicate_loop_to_header_edge (struct loop , edge, unsigned, sbitmap, edge, vec< edge > , int)
struct loop *	loopify (edge, edge, basic_block, edge, edge, bool, unsigned, unsigned)
struct loop *	loop_version (struct loop , void , basic_block *, unsigned, unsigned, unsigned, bool)
bool	remove_path (edge)
void	unloop (struct loop , bool , bitmap)
void	scale_loop_frequencies (struct loop *, int, int)
void	iv_analysis_loop_init (struct loop *)
bool	iv_analyze (rtx, rtx, struct rtx_iv *)
bool	iv_analyze_result (rtx, rtx, struct rtx_iv *)
bool	iv_analyze_expr (rtx, rtx, enum machine_mode, struct rtx_iv *)
rtx	get_iv_value (struct rtx_iv *, rtx)
bool	biv_p (rtx, rtx)
void	find_simple_exit (struct loop , struct niter_desc )
void	iv_analysis_done (void)
struct niter_desc *	get_simple_loop_desc (struct loop *loop)
void	free_simple_loop_desc (struct loop *loop)
static struct niter_desc *	simple_loop_desc ()
static struct loop *	get_loop ()
static unsigned	loop_depth ()
static struct loop *	loop_outer ()
static bool	loop_has_exit_edges ()
vec< loop_p, va_gc > *	get_loops ()
static unsigned	number_of_loops ()
static bool	loops_state_satisfies_p ()
static void	loops_state_set ()
static void	loops_state_clear ()
static void	fel_next ()
static void	fel_init ()
unsigned	estimate_reg_pressure_cost (unsigned, unsigned, bool, bool)
void	init_set_costs (void)
void	loop_optimizer_init (unsigned)
void	loop_optimizer_finalize (void)
void	unswitch_loops (void)
void	unroll_and_peel_loops (int)
void	doloop_optimize_loops (void)
void	move_loop_invariants (void)
void	scale_loop_profile (struct loop *loop, int scale, gcov_type iteration_bound)
vec< basic_block >	get_loop_hot_path (const struct loop *loop)
static struct loop *	loop_outermost ()
void	record_niter_bound (struct loop *, double_int, bool, bool)
HOST_WIDE_INT	get_estimated_loop_iterations_int (struct loop *)
HOST_WIDE_INT	get_max_loop_iterations_int (struct loop *)
bool	get_estimated_loop_iterations (struct loop loop, double_int nit)
bool	get_max_loop_iterations (struct loop loop, double_int nit)
int	bb_loop_depth (const_basic_block)
static double_int	gcov_type_to_double_int ()

Variables
struct target_cfgloop	default_target_cfgloop

Macro Definition Documentation

#define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)

Referenced by copy_decl_maybe_to_var(), move_unallocated_pseudos(), and split_live_ranges_for_shrink_wrap().

#define DLTHE_FLAG_COMPLETTE_PEEL

Value:

4 /* Update frequencies expecting

a complete peeling. */

#define DLTHE_FLAG_UPDATE_FREQ

Value:

1 /* Update frequencies in

duplicate_loop_to_header_edge. */

Referenced by decide_peel_simple().

#define DLTHE_RECORD_COPY_NUMBER

Value:

2 /* Record copy number in the aux

field of newly create BB. */

Referenced by decide_peel_simple().

#define FOR_EACH_LOOP	(	LI,
		LOOP,
		FLAGS
	)

Value:

for (fel_init (&(LI), &(LOOP), FLAGS); \
       (LOOP); \
       fel_next (&(LI), &(LOOP)))

Referenced by analyze_function(), create_preheader(), gather_chrec_stats(), loop_exit_at_end_p(), mark_ref_stored(), and rewrite_uses().

#define FOR_EACH_LOOP_BREAK ( LI )

Value:

{ \
    (LI).to_visit.release (); \
    break; \
  }

Referenced by analyze_function().

#define LOOPS_NORMAL

Value:

(LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES \

| LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)

#define target_avail_regs (this_target_cfgloop->x_target_avail_regs)

Referenced by determine_use_iv_cost(), and seq_cost().

#define target_clobbered_regs (this_target_cfgloop->x_target_clobbered_regs)

Referenced by determine_use_iv_cost(), and seq_cost().

#define target_reg_cost (this_target_cfgloop->x_target_reg_cost)

Referenced by determine_use_iv_cost(), and init_set_costs().

#define target_res_regs (this_target_cfgloop->x_target_res_regs)

Referenced by seq_cost().

#define target_spill_cost (this_target_cfgloop->x_target_spill_cost)

Referenced by determine_use_iv_cost(), and init_set_costs().

#define this_target_cfgloop (&default_target_cfgloop)

Typedef Documentation

typedef struct loop* loop_p

Enumeration Type Documentation

anonymous enum

Flags for state of loop structure.

Enumerator:

LOOPS_HAVE_PREHEADERS
LOOPS_HAVE_SIMPLE_LATCHES
LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
LOOPS_HAVE_RECORDED_EXITS
LOOPS_MAY_HAVE_MULTIPLE_LATCHES
LOOP_CLOSED_SSA
LOOPS_NEED_FIXUP
LOOPS_HAVE_FALLTHRU_PREHEADERS

anonymous enum

Enumerator:

CP_SIMPLE_PREHEADERS
CP_FALLTHRU_PREHEADERS

anonymous enum

Enumerator:

UAP_PEEL
UAP_UNROLL
UAP_UNROLL_ALL

enum iv_extend_code

The type of extend applied to an IV.

Enumerator:

IV_SIGN_EXTEND
IV_ZERO_EXTEND
IV_UNKNOWN_EXTEND

enum li_flags

Loop iterators. Flags for loop iteration.

Enumerator:

LI_INCLUDE_ROOT
LI_FROM_INNERMOST
LI_ONLY_INNERMOST

enum loop_estimation

An integer estimation of the number of iterations. Estimate_state describes what is the state of the estimation.

Enumerator:

EST_NOT_COMPUTED	Estimate was not computed yet.
EST_AVAILABLE	Estimate is ready.
EST_LAST

enum lpt_dec

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/. Structure to hold decision about unrolling/peeling.

Enumerator:

LPT_NONE
LPT_PEEL_COMPLETELY
LPT_PEEL_SIMPLE
LPT_UNROLL_CONSTANT
LPT_UNROLL_RUNTIME
LPT_UNROLL_STUPID

Function Documentation

void add_bb_to_loop	(	basic_block	,
		struct loop *
	)

void add_loop	(	struct loop *	,
		struct loop *
	)

Referenced by create_empty_if_region_on_edge().

struct loop* alloc_loop ( void )

read

Allocates and returns new loop structure.

References alloc_loop(), ENTRY_BLOCK_PTR_FOR_FUNCTION, EXIT_BLOCK_PTR_FOR_FUNCTION, loop::header, loops::larray, loop::latch, n_basic_blocks_for_function, loop::num_nodes, loops::tree_root, and vec_alloc().

Referenced by alloc_loop(), create_empty_if_region_on_edge(), and remap_decl_1().

int average_num_loop_insns ( const struct loop * )

int bb_loop_depth ( const_basic_block )

bool bb_loop_header_p ( basic_block )

Loop recognition.

bool biv_p	(	rtx	,
		rtx
	)

Referenced by analyze_insn_to_expand_var().

bool can_duplicate_loop_p ( const struct loop * loop )

Loop manipulation.

void cancel_loop_tree ( struct loop * )

void copy_loop_info	(	struct loop *	loop,
		struct loop *	target
	)

edge create_empty_if_region_on_edge	(	edge	,
		tree
	)

struct loop* create_empty_loop_on_edge	(	edge	entry_edge,
		tree	initial_value,
		tree	stride,
		tree	upper_bound,
		tree	iv,
		tree *	iv_before,
		tree *	iv_after,
		struct loop *	outer
	)

read

create_empty_loop_on_edge | | - pred_bb - —— pred_bb —— | | | | iv0 = initial_value | | -----|----- ---------|----------- | | ______ | entry_edge | | entry_edge / | | | | ====> | -V—V- loop_header ————- | V | | iv_before = phi (iv0, iv_after) | | - succ_bb - | —|—————————– | | | | | | ———– | —V— loop_body ————— | | | iv_after = iv_before + stride | | | | if (iv_before < upper_bound) | | | —|————–————– | | | \ exit_e | | V \ | | - loop_latch - V- succ_bb - | | | | | | | | /————- ———– | \ ___ /

Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME that is used before the increment of IV. IV_BEFORE should be used for adding code to the body that uses the IV. OUTER is the outer loop in which the new loop should be inserted.

Both INITIAL_VALUE and UPPER_BOUND expressions are gimplified and inserted on the loop entry edge. This implies that this function should be used only when the UPPER_BOUND expression is a loop invariant.

 Create header, latch and wire up the loop.

 Set immediate dominator information.

 Initialize a loop structure and put it in a loop hierarchy.

 TODO: Fix frequencies and counts.

 Update dominators.

 Modify edge flags.

 Construct IV code in loop.

 Insert loop exit condition.

basic_block create_preheader	(	struct loop *	,
		int
	)

Referenced by copy_loop_before().

void create_preheaders ( int )

void delete_loop ( struct loop * )

void disambiguate_loops_with_multiple_latches ( void )

Split loops with multiple latch edges.

rtx doloop_condition_get ( rtx )

void doloop_optimize_loops ( void )

struct loop* duplicate_loop	(	struct loop *	,
		struct loop *
	)

read

Referenced by fix_loop_placements().

bool duplicate_loop_to_header_edge	(	struct loop *	,
		edge	,
		unsigned	,
		sbitmap	,
		edge	,
		vec< edge > *	,
		int
	)

Referenced by decide_peel_simple().

void duplicate_subloops	(	struct loop *	,
		struct loop *
	)

Referenced by fix_loop_placements().

unsigned estimate_reg_pressure_cost	(	unsigned	n_new,
		unsigned	n_old,
		bool	speed,
		bool	call_p
	)

Register pressure estimation for induction variable optimizations & loop invariant motion.

Estimates cost of increased register pressure caused by making N_NEW new registers live around the loop. N_OLD is the number of registers live around the loop. If CALL_P is true, also take into account that call-used registers may be clobbered in the loop body, reducing the number of available registers before we spill.

 If there is a call in the loop body, the call-clobbered registers
 are not available for loop invariants.

 If we have enough registers, we should use them and not restrict
 the transformations unnecessarily.

   If we are close to running out of registers, try to preserve
   them.

   If we run out of registers, it is very expensive to add another
   one.

   IRA regional allocation deals with high register pressure
   better.  So decrease the cost (to do more accurate the cost
   calculation for IRA, we need to know how many registers lives
   through the loop transparently).

unsigned expected_loop_iterations ( const struct loop * )

Referenced by scale_dominated_blocks_in_loop().

gcov_type expected_loop_iterations_unbounded ( const struct loop * )

static void fel_init ( )

inlinestatic

Push the loops to LI->TO_VISIT in postorder.

     Push the loops to LI->TO_VISIT in preorder.

static void fel_next ( )

inlinestatic

struct loop* find_common_loop	(	struct loop *	,
		struct loop *
	)

read

void find_simple_exit	(	struct loop *	,
		struct niter_desc *
	)

Referenced by check_simple_exit().

unsigned fix_loop_structure ( bitmap changed_bbs )

Referenced by unswitch_loops().

bool flow_bb_inside_loop_p	(	const struct loop *	,
		const_basic_block
	)

void flow_loop_dump	(	const struct loop *	loop,
		FILE *	file,
		void()(const struct loop , FILE *, int)	loop_dump_aux,
		int	verbose
	)

Dump the loop information specified by LOOP to the stream FILE using auxiliary dump callback function LOOP_DUMP_AUX if non null.

Referenced by rewrite_uses().

void flow_loop_free ( struct loop * )

bool flow_loop_nested_p	(	const struct loop *	,
		const struct loop *
	)

int flow_loop_nodes_find	(	basic_block	,
		struct loop *
	)

void flow_loop_tree_node_add	(	struct loop *	,
		struct loop *
	)

Loop data structure manipulation/querying.

void flow_loop_tree_node_remove ( struct loop * )

void flow_loops_dump	(	FILE *	file,
		void()(const struct loop , FILE *, int)	loop_dump_aux,
		int	verbose
	)

Dump the loop information about loops to the stream FILE, using auxiliary dump callback function LOOP_DUMP_AUX if non null.

Referenced by analyze_function().

struct loops* flow_loops_find ( struct loops * )

read

void flow_loops_free ( struct loops * )

void force_single_succ_latches ( void )

Forces all loop latches to have only single successor.

void free_simple_loop_desc ( struct loop * loop )

Referenced by decide_peel_simple().

static double_int gcov_type_to_double_int ( )

inlinestatic

Converts VAL to double_int.

If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by the size of type.

bool get_estimated_loop_iterations	(	struct loop *	loop,
		double_int *	nit
	)

HOST_WIDE_INT get_estimated_loop_iterations_int ( struct loop * )

rtx get_iv_value	(	struct rtx_iv *	,
		rtx
	)

static struct loop* get_loop ( )

staticread

Accessors for the loop structures. Returns the loop with index NUM from FNs loop tree.

Referenced by chrec_contains_undetermined(), copy_loops(), move_stmt_r(), and output_eh_regions().

basic_block* get_loop_body ( const struct loop * )

Loops & cfg manipulation.

basic_block* get_loop_body_in_bfs_order ( const struct loop * )

basic_block* get_loop_body_in_custom_order	(	const struct loop *	loop,
		int()(const void , const void *)	bb_comparator
	)

Gets body of a LOOP sorted via provided BB_COMPARATOR.

References loop_exit::e.

basic_block* get_loop_body_in_dom_order ( const struct loop * )

unsigned get_loop_body_with_size	(	const struct loop *	loop,
		basic_block *	body,
		unsigned	max_size
	)

Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs order against direction of edges from latch. Specially, if header != latch, latch is the 1-st block. LOOP cannot be the fake loop tree root, and its size must be at most MAX_SIZE. The blocks in the LOOP body are stored to BODY, and the size of the LOOP is returned.

Referenced by cancel_loop().

vec<edge> get_loop_exit_edges ( const struct loop * )

vec<basic_block> get_loop_hot_path ( const struct loop * loop )

unsigned get_loop_level ( const struct loop * )

location_t get_loop_location ( struct loop * loop )

vec<loop_p, va_gc>* get_loops ( )

inline

Returns the list of loops in FN.

Referenced by move_allocno_live_ranges(), and move_stmt_eh_region_tree_nr().

bool get_max_loop_iterations	(	struct loop *	loop,
		double_int *	nit
	)

HOST_WIDE_INT get_max_loop_iterations_int ( struct loop * )

struct niter_desc* get_simple_loop_desc ( struct loop * loop )

read

Referenced by decide_peel_simple(), and split_edge_and_insert().

void init_loops_structure	(	struct function *	fn,
		struct loops *	loops,
		unsigned	num_loops
	)

Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops (including the root of the loop tree).

Dummy loop containing whole function.

void init_set_costs ( void )

Initialize the constants for computing set costs.

Set up the costs for using extra registers:

1) If not many free registers remain, we should prefer having an additional move to decreasing the number of available registers. (TARGET_REG_COST). 2) If no registers are available, we need to spill, which may require storing the old value to memory and loading it back (TARGET_SPILL_COST).

References crtl, emit_move_insn(), end_sequence(), get_insns(), seq_cost(), start_sequence(), target_reg_cost, and target_spill_cost.

void iv_analysis_done ( void )

Free the data for an induction variable analysis.

References function_invariant_p(), GET_CODE, HARD_REGISTER_P, REG_P, and XEXP.

void iv_analysis_loop_init ( struct loop * )

Referenced by check_simple_exit().

bool iv_analyze	(	rtx	,
		rtx	,
		struct rtx_iv *
	)

bool iv_analyze_expr	(	rtx	,
		rtx	,
		enum	machine_mode,
		struct rtx_iv *
	)

bool iv_analyze_result	(	rtx	,
		rtx	,
		struct rtx_iv *
	)

Referenced by analyze_insn_to_expand_var().

bool just_once_each_iteration_p	(	const struct loop *	,
		const_basic_block
	)

Loop analysis.

Referenced by loop_niter_by_eval().

static unsigned loop_depth ( )

inlinestatic

Returns the number of superloops of LOOP.

Referenced by memref_referenced_p(), and set_ifsese_condition().

bool loop_exit_edge_p	(	const struct loop *	,
		const_edge
	)

bool loop_exits_from_bb_p	(	struct loop *	,
		basic_block
	)

bool loop_exits_to_bb_p	(	struct loop *	,
		basic_block
	)

static bool loop_has_exit_edges ( )

inlinestatic

Returns true if LOOP has at least one exit edge.

edge loop_latch_edge ( const struct loop * )

void loop_optimizer_finalize ( void )

Finalize loop structures.

If we should preserve loop structure, do not free it but clear flags that advanced properties are there as we are not preserving that in full.

 Clean up.

References LOOP_CLOSED_SSA, LOOPS_HAVE_FALLTHRU_PREHEADERS, loops_state_clear(), and loops_state_set().

Referenced by analyze_function(), and move_unallocated_pseudos().

void loop_optimizer_init ( unsigned )

Loop optimizer initialization.

Referenced by analyze_function(), copy_decl_maybe_to_var(), free_all_edge_infos(), move_unallocated_pseudos(), and split_live_ranges_for_shrink_wrap().

static struct loop* loop_outer ( )

staticread

Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost loop.

Referenced by add_loop_to_tree(), add_subscript_strides(), analyze_scalar_evolution(), fix_bb_placement(), get_loops_exits(), loop_in_sese_p(), optimize_loop_for_size_p(), and setup_loop_tree_level().

static struct loop* loop_outermost ( )

staticread

Returns the outermost loop of the loop nest that contains LOOP.

edge loop_preheader_edge ( const struct loop * )

struct loop* loop_version	(	struct loop *	loop,
		void *	cond_expr,
		basic_block *	condition_bb,
		unsigned	then_prob,
		unsigned	then_scale,
		unsigned	else_scale,
		bool	place_after
	)

read

Main entry point for Loop Versioning transformation.

This transformation given a condition and a loop, creates -if (condition) { loop_copy1 } else { loop_copy2 }, where loop_copy1 is the loop transformed in one way, and loop_copy2 is the loop transformed in another way (or unchanged). 'condition' may be a run time test for things that were not resolved by static analysis (overlapping ranges (anti-aliasing), alignment, etc.).

THEN_PROB is the probability of the then edge of the if. THEN_SCALE is the ratio by that the frequencies in the original loop should be scaled. ELSE_SCALE is the ratio by that the frequencies in the new loop should be scaled.

If PLACE_AFTER is true, we place the new loop after LOOP in the instruction stream, otherwise it is placed before LOOP.

 Record entry and latch edges for the loop

 Note down head of loop as first_head.

 Duplicate loop.

 After duplication entry edge now points to new loop head block.
 Note down new head as second_head.

 Split loop entry edge and insert new block with cond expr.

 loopify redirected latch_edge. Update its PENDING_STMTS.

 loopify redirected condition_bb's succ edge. Update its PENDING_STMTS.

 Adjust irreducible flag.

 At this point condition_bb is loop preheader with two successors,
 first_head and second_head.   Make sure that loop preheader has only
 one successor.

Referenced by scale_dominated_blocks_in_loop(), and vect_create_cond_for_alias_checks().

struct loop* loopify	(	edge	latch_edge,
		edge	header_edge,
		basic_block	switch_bb,
		edge	true_edge,
		edge	false_edge,
		bool	redirect_all_edges,
		unsigned	true_scale,
		unsigned	false_scale
	)

read

Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting latch to header and update loop tree and dominators accordingly. Everything between them plus LATCH_EDGE destination must be dominated by HEADER_EDGE destination, and back-reachable from LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB, FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE. Returns the newly created loop. Frequencies and counts in the new loop are scaled by FALSE_SCALE and in the old one by TRUE_SCALE.

 Redirect edges.

 During loop versioning, one of the switch_bb edge is already properly
 set. Do not redirect it again unless redirect_all_edges is true.

     Update dominators.

 Compute new loop.

 Add switch_bb to appropriate loop.

 Fix frequencies.

static void loops_state_clear ( )

inlinestatic

Clears FLAGS from the loops state.

Referenced by loop_optimizer_finalize().

static bool loops_state_satisfies_p ( )

inlinestatic

Returns true if state of the loops satisfies all properties described by FLAGS.

Referenced by record_loop_exits(), and standard_iv_increment_position().

static void loops_state_set ( )

inlinestatic

Sets FLAGS to the loops state.

Referenced by apply_loop_flags(), cleanup_tree_cfg_1(), copy_loops(), create_preheader(), find_uses_to_rename(), loop_optimizer_finalize(), move_block_after(), predict_edge(), and redirection_block_p().

bool mark_irreducible_loops ( void )

 Reset the flags.

 Create the edge lists.

       Ignore edges to exit.

       Ignore latch edges.

       Edges inside a single loop should be left where they are.  Edges
       to subloop headers should lead to representative of the subloop,
       but from the same place.

       Edges exiting loops should lead from representative
       of the son of nearest common ancestor of the loops in that
       act lays.

 Find the strongly connected components.

 Mark the irreducible loops.

       edge E in graph G is irreducible if it connects two vertices in the
       same scc.

       All edges should lead from a component with higher number to the
       one with lower one.

Referenced by analyze_function().

void mark_loop_exit_edges ( void )

Sets EDGE_LOOP_EXIT flag for all loop exits.

void move_loop_invariants ( void )

Move the invariants out of the loops.

 Process the loops, innermost first.

     move_single_loop_invariants for very large loops
     is time consuming and might need a lot of memory.

   There is no sense to keep this info because it was most
   probably outdated by subsequent passes.

unsigned num_loop_branches ( const struct loop * )

int num_loop_insns ( const struct loop * )

Referenced by loop_exit_at_end_p().

static unsigned number_of_loops ( )

inlinestatic

Returns the number of loops in FN (including the removed ones and the fake loop that forms the root of the loop tree).

Referenced by find_uses_to_rename(), make_pass_tree_loop_init(), make_pass_vectorize(), mark_ref_stored(), move_allocno_live_ranges(), move_stmt_eh_region_tree_nr(), output_eh_regions(), and remove_unnecessary_allocnos().

void place_new_loop	(	struct function *	,
		struct loop *
	)

void record_loop_exits ( void )

For each loop, record list of exit edges, and start maintaining these lists.

References edge_def::dest, loop_exit::e, EXIT_BLOCK_PTR, loop::exits, flow_bb_inside_loop_p(), FOR_EACH_EDGE, gcc_assert, get_loop_body(), loop::latch, LOOPS_HAVE_RECORDED_EXITS, loops_state_satisfies_p(), loop_exit::next, loop::num_nodes, and vNULL.

void record_niter_bound	(	struct loop *	loop,
		double_int	i_bound,
		bool	realistic,
		bool	upper
	)

Records that every statement in LOOP is executed I_BOUND times. REALISTIC is true if I_BOUND is expected to be close to the real number of iterations. UPPER is true if we are sure the loop iterates at most I_BOUND times.

Update the bounds only when there is no previous estimation, or when the current estimation is smaller.

 If an upper bound is smaller than the realistic estimate of the
 number of iterations, use the upper bound instead.

Referenced by vect_update_ivs_after_vectorizer().

void release_recorded_exits ( void )

Releases lists of loop exits.

References rescan_loop_exit().

void remove_bb_from_loops ( basic_block )

bool remove_path ( edge )

void rescan_loop_exit	(	edge	,
		bool	,
		bool
	)

void scale_loop_frequencies	(	struct loop *	,
		int	,
		int
	)

Referenced by create_empty_if_region_on_edge().

void scale_loop_profile	(	struct loop *	loop,
		int	scale,
		gcov_type	iteration_bound
	)

static struct niter_desc* simple_loop_desc ( )

staticread

Referenced by check_simple_exit(), and find_simple_exit().

edge single_exit ( const struct loop * )

edge single_likely_exit ( struct loop * loop )

struct loop* superloop_at_depth	(	struct loop *	,
		unsigned
	)

read

void unloop	(	struct loop *	loop,
		bool *	irred_invalidated,
		bitmap	loop_closed_ssa_invalidated
	)

Remove the latch edge of a LOOP and update loops to indicate that the LOOP was removed. After this function, original loop latch will have no successor, which caller is expected to fix somehow.

If this may cause the information about irreducible regions to become invalid, IRRED_INVALIDATED is set to true.

LOOP_CLOSED_SSA_INVALIDATED, if non-NULL, is a bitmap where we store basic blocks that had non-trivial update on their loop_father.

 This is relatively straightforward.  The dominators are unchanged, as
 loop header dominates loop latch, so the only thing we have to care of
 is the placement of loops and basic blocks inside the loop tree.  We
 move them all to the loop->outer, and then let fix_bb_placements do
 its work.

 Remove the loop and free its data.

 We do not pass IRRED_INVALIDATED to fix_bb_placements here, as even if
 there is an irreducible region inside the cancelled loop, the flags will
 be still correct.

void unroll_and_peel_loops ( int )

void unswitch_loops ( void )

Optimization passes.

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

Go through inner loops (only original ones).

 If we unswitched any loop discover new loops that are eventually
 exposed by making irreducible regions reducible.

References calculate_dominance_info(), CDI_DOMINATORS, fix_loop_structure(), and NULL.

void verify_loop_structure ( void )

Checks that information about loops is correct – sizes of loops are all right – results of get_loop_body really belong to the loop – loop header have just single entry edge and single latch edge – loop latches have only single successor that is header of their loop – irreducible loops are correctly marked – the cached loop depth and loop father of each bb is correct

 We need up-to-date dominators, compute or verify them.

 Check the headers.

 Check the recorded loop father and sizes of loops.

         Ignore this block if it is in an inner loop.

 Check headers and latches.

 Check irreducible loops.

     Record old info.

     Recount it.

     Compare.

 Check the recorded loop exits.

         Check that the list forms a cycle, and all elements except
         for the head are nonnull.

                  When a loop exit is also an entry edge which
                  can happen when avoiding CFG manipulations
                  then the last loop exited is the outer loop
                  of the loop entered.

Variable Documentation

struct target_cfgloop default_target_cfgloop

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/.

Data Structures

Macros

Typedefs

Enumerations

Functions

Variables

Macro Definition Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation