cfgloop.h File Reference

Go to the source code of 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

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
struct target_cfgloop *	this_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

   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(), loop::header, loops::larray, loop::latch, memset(), 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

)

   This is the main entry point.  Process all loops using doloop_optimize.  

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 emit_move_insn(), end_sequence(), get_insns(), seq_cost(), and start_sequence().

void iv_analysis_done

(

void

)

   Free the data for an induction variable analysis.  

References function_invariant_p().

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 all_non_dominated_preds_marked_p(), follow_ssa_with_commutative_ops(), memref_referenced_p(), phi_contains_arg(), 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(), loop_canon_p(), 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(), loop_canon_p(), 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(), graphite_can_represent_expr(), loop_in_sese_p(), optimize_loop_for_size_p(), print_graphite_scop_statistics(), 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_pbb_via_hash(), find_uses_to_rename(), loop_canon_p(), make_pass_tree_loop_init(), make_pass_vectorize(), mark_ref_stored(), move_allocno_live_ranges(), move_stmt_eh_region_tree_nr(), output_eh_regions(), print_graphite_statistics(), 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, loop::exits, flow_bb_inside_loop_p(), free(), 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, and fix_loop_structure().

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

@verbatim 

Natural loop analysis code for GNU compiler. Copyright (C) 2002-2013 Free Software Foundation, Inc.

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/.

struct target_cfgloop* this_target_cfgloop