Functions
static void	copy_loops_to (struct loop *, int, struct loop )
static void	loop_redirect_edge (edge, basic_block)
static void	remove_bbs (basic_block *, int)
static bool	rpe_enum_p (const_basic_block, const void *)
static int	find_path (edge, basic_block **)
static void	fix_loop_placements (struct loop , bool )
static bool	fix_bb_placement (basic_block)
static void	fix_bb_placements (basic_block, bool *, bitmap)
static bool	rpe_enum_p ()
static void	remove_bbs ()
static int	find_path ()
static bool	fix_bb_placement ()
static bool	fix_loop_placement ()
bool	remove_path ()
void	place_new_loop ()
void	add_loop ()
void	scale_loop_frequencies ()
void	scale_loop_profile ()
static void	update_dominators_in_loop ()
edge	create_empty_if_region_on_edge ()
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)
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)
void	unloop (struct loop loop, bool irred_invalidated, bitmap loop_closed_ssa_invalidated)
static void	fix_loop_placements ()
void	copy_loop_info ()
struct loop *	duplicate_loop ()
void	duplicate_subloops ()
static void	copy_loops_to ()
static void	loop_redirect_edge ()
bool	can_duplicate_loop_p ()
static void	set_zero_probability ()
bool	duplicate_loop_to_header_edge (struct loop loop, edge e, unsigned int ndupl, sbitmap wont_exit, edge orig, vec< edge > to_remove, int flags)
bool	mfb_keep_just ()
static bool	has_preds_from_loop ()
basic_block	create_preheader ()
void	create_preheaders ()
void	force_single_succ_latches ()
static basic_block	lv_adjust_loop_entry_edge (basic_block first_head, basic_block second_head, edge e, void *cond_expr, unsigned then_prob)
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)

Variables
edge	mfb_kj_edge

Function Documentation

void add_loop ( )

Given LOOP structure with filled header and latch, find the body of the
   corresponding loop and add it to loops tree.  Insert the LOOP as a son of
   outer.

References add_bb_to_loop(), cfun, flow_loop_tree_node_add(), flow_loop_tree_node_remove(), free(), get_loop_body_with_size(), loop::header, basic_block_def::loop_father, loop_outer(), loop::num_nodes, place_new_loop(), remove_bb_from_loops(), and rescan_loop_exit().

bool can_duplicate_loop_p ( )

Check whether LOOP's body can be duplicated.

References can_copy_bbs_p(), free(), get_loop_body(), and loop::num_nodes.

void copy_loop_info ( )

Duplicate loop bounds and other information we store about
   the loop into its duplicate.

References loop::any_estimate, loop::any_upper_bound, loop::estimate_state, loop::nb_iterations_estimate, and loop::nb_iterations_upper_bound.

static void copy_loops_to	(	struct loop **	,
		int	,
		struct loop *
	)

static

@verbatim Loop manipulation code for GNU compiler.

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

Referenced by duplicate_loop_to_header_edge().

static void copy_loops_to ( )

static

Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
   into TARGET loop, placing newly created loops into loop tree.

References duplicate_loop(), and duplicate_subloops().

edge create_empty_if_region_on_edge ( )

Creates an if region as shown above. CONDITION is used to create
   the test for the if.

   |
   |     -------------                 -------------
   |     |  pred_bb  |                 |  pred_bb  |
   |     -------------                 -------------
   |           |                             |
   |           |                             | ENTRY_EDGE
   |           | ENTRY_EDGE                  V
   |           |             ====>     -------------
   |           |                       |  cond_bb  |
   |           |                       | CONDITION |
   |           |                       -------------
   |           V                        /         \
   |     -------------         e_false /           \ e_true
   |     |  succ_bb  |                V             V
   |     -------------         -----------       -----------
   |                           | false_bb |      | true_bb |
   |                           -----------       -----------
   |                                   \           /
   |                                    \         /
   |                                     V       V
   |                                   -------------
   |                                   |  join_bb  |
   |                                   -------------
   |                                         | exit_edge (result)
   |                                         V
   |                                    -----------
   |                                    | succ_bb |
   |                                    -----------
   |

References CDI_DOMINATORS, edge_def::dest, edge_def::flags, force_gimple_operand_gsi(), gimple_build_cond_from_tree(), gsi_insert_after(), gsi_last_bb(), GSI_NEW_STMT, make_edge(), set_immediate_dominator(), single_pred_p(), single_succ_edge(), split_edge(), and edge_def::src.

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.

References add_loop(), alloc_loop(), CDI_DOMINATORS, create_iv(), edge_def::flags, force_gimple_operand(), force_gimple_operand_gsi(), gimple_build_cond(), gimple_cond_lhs(), gimple_cond_set_lhs(), gsi_commit_edge_inserts(), gsi_insert_after(), gsi_insert_seq_on_edge(), gsi_last_bb(), GSI_NEW_STMT, loop::header, loop::latch, loop_preheader_edge(), make_edge(), prob, redirect_edge_succ_nodup(), scale_loop_frequencies(), set_immediate_dominator(), single_exit(), single_pred_edge(), single_succ(), single_succ_edge(), split_block_after_labels(), split_edge(), edge_def::src, and update_dominators_in_loop().

Referenced by graphite_create_new_loop().

basic_block create_preheader ( )

Creates a pre-header for a LOOP.  Returns newly created block.  Unless
   CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
   entry; otherwise we also force preheader block to have only one successor.
   When CP_FALLTHRU_PREHEADERS is set in FLAGS, we force the preheader block
   to be a fallthru predecessor to the loop header and to have only
   predecessors from outside of the loop.
   The function also updates dominators.

References CP_FALLTHRU_PREHEADERS, CP_SIMPLE_PREHEADERS, edge_def::dest, dump_file, edge_def::flags, basic_block_def::flags, has_preds_from_loop(), loop::header, loop::latch, loop_latch_edge(), make_forwarder_block(), mfb_keep_just(), move_block_after(), loop::num, basic_block_def::preds, single_succ_edge(), single_succ_p(), and edge_def::src.

void create_preheaders ( )

Create preheaders for each loop; for meaning of FLAGS see create_preheader.

References create_preheader(), LOOPS_HAVE_PREHEADERS, and loops_state_set().

struct loop* duplicate_loop ( )

read

Copies copy of LOOP as subloop of TARGET loop, placing newly
   created loop into loops structure.

References alloc_loop(), cfun, copy_loop_info(), flow_loop_tree_node_add(), place_new_loop(), and set_loop_copy().

bool duplicate_loop_to_header_edge	(	struct loop *	loop,
		edge	e,
		unsigned int	ndupl,
		sbitmap	wont_exit,
		edge	orig,
		vec< edge > *	to_remove,
		int	flags
	)

Duplicates body of LOOP to given edge E NDUPL times.  Takes care of updating
   loop structure and dominators.  E's destination must be LOOP header for
   this to work, i.e. it must be entry or latch edge of this loop; these are
   unique, as the loops must have preheaders for this function to work
   correctly (in case E is latch, the function unrolls the loop, if E is entry
   edge, it peels the loop).  Store edges created by copying ORIG edge from
   copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
   original LOOP body, the other copies are numbered in order given by control
   flow through them) into TO_REMOVE array.  Returns false if duplication is
   impossible.

References loop::aux, basic_block_def::aux, bitmap_bit_p(), bitmap_set_bit(), can_copy_bbs_p(), CDI_DOMINATORS, combine_probabilities(), copy_bbs(), copy_loops_to(), edge_def::dest, dominated_by_p(), edge_def::flags, basic_block_def::flags, flow_bb_inside_loop_p(), free(), basic_block_def::frequency, get_dominated_by(), get_loop_body_in_dom_order(), loop::header, loop::inner, loop::latch, basic_block_def::loop_father, loop_latch_edge(), memcpy(), nearest_common_dominator(), loop::next, loop::num_nodes, edge_def::probability, redirect_edge_and_branch_force(), scale_bbs_frequencies_int(), set_immediate_dominator(), set_loop_copy(), set_zero_probability(), edge_def::src, and basic_block_def::succs.

void duplicate_subloops ( )

Copies structure of subloops of LOOP into TARGET loop, placing
   newly created loops into loop tree.

References duplicate_loop(), duplicate_subloops(), loop::inner, and loop::next.

static int find_path	(	edge	,
		basic_block **
	)

static

Referenced by remove_path().

static int find_path ( )

static

Find path -- i.e. the basic blocks dominated by edge E and put them
   into array BBS, that will be allocated large enough to contain them.
   E->dest must have exactly one predecessor for this to work (it is
   easy to achieve and we do not put it here because we do not want to
   alter anything by this function).  The number of basic blocks in the
   path is returned.

References edge_def::dest, dfs_enumerate_from(), basic_block_def::preds, and rpe_enum_p().

static bool fix_bb_placement ( basic_block )

static

Referenced by fix_bb_placements().

static bool fix_bb_placement ( )

static

Fix placement of basic block BB inside loop hierarchy --
   Let L be a loop to that BB belongs.  Then every successor of BB must either
     1) belong to some superloop of loop L, or
     2) be a header of loop K such that K->outer is superloop of L
   Returns true if we had to move BB into other loop to enforce this condition,
   false if the placement of BB was already correct (provided that placements
   of its successors are correct).

References add_bb_to_loop(), edge_def::dest, flow_loop_nested_p(), basic_block_def::loop_father, loop_outer(), remove_bb_from_loops(), and basic_block_def::succs.

static void fix_bb_placements	(	basic_block	from,
		bool *	irred_invalidated,
		bitmap	loop_closed_ssa_invalidated
	)

static

Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
   enforce condition condition stated in description of fix_bb_placement. We
   start from basic block FROM that had some of its successors removed, so that
   his placement no longer has to be correct, and iteratively fix placement of
   its predecessors that may change if placement of FROM changed.  Also fix
   placement of subloops of FROM->loop_father, that might also be altered due
   to this change; the condition for them is similar, except that instead of
   successors we consider edges coming out of the loops.

   If the changes may invalidate the information about irreducible regions,
   IRRED_INVALIDATED is set to true.  

   If LOOP_CLOSED_SSA_INVLIDATED is non-zero then all basic blocks with
   changed loop_father are collected there.

References bitmap_bit_p(), bitmap_clear(), bitmap_clear_bit(), bitmap_set_bit(), find_common_loop(), fix_bb_placement(), fix_loop_placement(), edge_def::flags, flow_loop_nested_p(), free(), loop::header, basic_block_def::index, basic_block_def::loop_father, loop_outer(), loop::num_nodes, basic_block_def::preds, queue, sbitmap_alloc(), edge_def::src, and basic_block_def::succs.

Referenced by fix_loop_placements(), remove_path(), and unloop().

static bool fix_loop_placement ( )

static

Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
   of LOOP to that leads at least one exit edge of LOOP, and set it
   as the immediate superloop of LOOP.  Return true if the immediate superloop
   of LOOP changed.

   IRRED_INVALIDATED is set to true if a change in the loop structures might
   invalidate the information about irreducible regions.

References edge_def::dest, loop::exits, find_common_loop(), edge_def::flags, flow_loop_nested_p(), flow_loop_tree_node_add(), flow_loop_tree_node_remove(), get_loop_exit_edges(), basic_block_def::loop_father, loop_outer(), loop::num_nodes, and rescan_loop_exit().

Referenced by fix_bb_placements(), and fix_loop_placements().

static void fix_loop_placements	(	struct loop *	,
		bool *
	)

static

Referenced by remove_path().

static void fix_loop_placements ( )

static

Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
   condition stated in description of fix_loop_placement holds for them.
   It is used in case when we removed some edges coming out of LOOP, which
   may cause the right placement of LOOP inside loop tree to change.

   IRRED_INVALIDATED is set to true if a change in the loop structures might
   invalidate the information about irreducible regions.

References fix_bb_placements(), fix_loop_placement(), loop_outer(), and loop_preheader_edge().

void force_single_succ_latches ( void )

Forces all loop latches to have only single successor.

References find_edge(), loop::header, loop::latch, LOOPS_HAVE_SIMPLE_LATCHES, loops_state_set(), single_succ_p(), and split_edge().

Referenced by apply_loop_flags().

static bool has_preds_from_loop ( )

static

True when a candidate preheader BLOCK has predecessors from LOOP.

References basic_block_def::loop_father, basic_block_def::preds, and edge_def::src.

Referenced by create_preheader().

static void loop_redirect_edge	(	edge	,
		basic_block
	)

static

Referenced by loopify().

static void loop_redirect_edge ( )

static

Redirects edge E to basic block DEST.

References edge_def::dest, and redirect_edge_and_branch_force().

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.

References cfg_hook_duplicate_loop_to_header_edge(), copy_loop_info(), edge_def::dest, extract_cond_bb_edges(), edge_def::flags, basic_block_def::flags, free(), get_bb_copy(), get_loop_body_in_dom_order(), loop::header, loop::latch, loop_preheader_edge(), loopify(), lv_adjust_loop_entry_edge(), lv_flush_pending_stmts(), move_block_after(), loop::num_nodes, single_pred_edge(), single_succ_edge(), and split_edge().

Referenced by gen_parallel_loop(), sms_schedule(), tree_transform_and_unroll_loop(), tree_unswitch_loop(), and vect_loop_versioning().

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.

References add_bb_to_loop(), add_loop(), alloc_loop(), apply_probability(), CDI_DOMINATORS, edge_def::count, basic_block_def::count, edge_def::dest, basic_block_def::frequency, loop::header, loop::latch, basic_block_def::loop_father, loop_outer(), loop_redirect_edge(), edge_def::probability, remove_bb_from_loops(), scale_loop_frequencies(), set_immediate_dominator(), edge_def::src, basic_block_def::succs, and update_dominators_in_loop().

Referenced by loop_version(), and unswitch_loop().

static basic_block lv_adjust_loop_entry_edge	(	basic_block	first_head,
		basic_block	second_head,
		edge	e,
		void *	cond_expr,
		unsigned	then_prob
	)

static

This function is called from loop_version.  It splits the entry edge
   of the loop we want to version, adds the versioning condition, and
   adjust the edges to the two versions of the loop appropriately.
   e is an incoming edge. Returns the basic block containing the
   condition.

   --- edge e ---- > [second_head]

   Split it and insert new conditional expression and adjust edges.

    --- edge e ---> [cond expr] ---> [first_head]
                        |
                        +---------> [second_head]

  THEN_PROB is the probability of then branch of the condition.

References apply_probability(), CDI_DOMINATORS, edge_def::count, current_ir_type(), edge_def::dest, IR_GIMPLE, lv_add_condition_to_bb(), lv_adjust_loop_header_phi(), make_edge(), edge_def::probability, set_immediate_dominator(), single_succ_edge(), and split_edge().

Referenced by loop_version().

bool mfb_keep_just ( )

References mfb_kj_edge.

void place_new_loop ( )

Creates place for a new LOOP in loops structure of FN.

References loops_for_fn(), loop::num, number_of_loops(), and vec_safe_push().

static void remove_bbs	(	basic_block *	,
		int
	)

static

Referenced by remove_path().

static void remove_bbs ( )

static

Remove basic blocks BBS.  NBBS is the number of the basic blocks.

References delete_basic_block().

bool remove_path ( )

Removes path beginning at edge E, i.e. remove basic blocks dominated by E
   and update loop structures and dominators.  Return true if we were able
   to remove the path, false otherwise (and nothing is affected then).

References bitmap_bit_p(), bitmap_clear(), bitmap_set_bit(), can_remove_branch_p(), cancel_loop_tree(), CDI_DOMINATORS, edge_def::dest, dominated_by_p(), find_path(), first_dom_son(), fix_bb_placements(), fix_loop_placements(), edge_def::flags, free(), get_immediate_dominator(), basic_block_def::index, iterate_fix_dominators(), loop::latch, basic_block_def::loop_father, loop_outer(), LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS, loops_state_satisfies_p(), mark_irreducible_loops(), next_dom_son(), remove_bbs(), remove_branch(), sbitmap_alloc(), single_pred_edge(), single_pred_p(), split_edge(), edge_def::src, basic_block_def::succs, and unloop().

static bool rpe_enum_p	(	const_basic_block	,
		const void *
	)

static

Referenced by find_path().

static bool rpe_enum_p ( )

static

Checks whether basic block BB is dominated by DATA.

References CDI_DOMINATORS, and dominated_by_p().

void scale_loop_frequencies ( )

Multiply all frequencies in LOOP by NUM/DEN.

References free(), get_loop_body(), loop::num_nodes, and scale_bbs_frequencies_int().

void scale_loop_profile ( )

Multiply all frequencies in LOOP by SCALE/REG_BR_PROB_BASE.
   If ITERATION_BOUND is non-zero, scale even further if loop is predicted
   to iterate too many times.

References apply_probability(), edge_def::count, basic_block_def::count, dump_file, dump_flags, expected_loop_iterations_unbounded(), edge_def::flags, basic_block_def::frequency, loop::header, inverse_probability(), loop::latch, loop::num, basic_block_def::preds, edge_def::probability, scale_loop_frequencies(), single_exit(), edge_def::src, and basic_block_def::succs.

static void set_zero_probability ( )

static

Sets probability and count of edge E to zero.  The probability and count
   is redistributed evenly to the remaining edges coming from E->src.

References edge_def::count, last, prob, edge_def::probability, edge_def::src, and basic_block_def::succs.

Referenced by duplicate_loop_to_header_edge().

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.

References add_bb_to_loop(), delete_loop(), fix_bb_placements(), flow_loop_tree_node_add(), flow_loop_tree_node_remove(), free(), get_loop_body(), loop::inner, loop::latch, loop_outer(), loop_preheader_edge(), loop::num_nodes, remove_bb_from_loops(), remove_edge(), and single_succ_edge().

Referenced by remove_path(), and unloop_loops().

static void update_dominators_in_loop ( )

static

Recompute dominance information for basic blocks outside LOOP.

References bitmap_bit_p(), bitmap_clear(), bitmap_set_bit(), CDI_DOMINATORS, first_dom_son(), free(), get_loop_body(), basic_block_def::index, iterate_fix_dominators(), next_dom_son(), loop::num_nodes, sbitmap_alloc(), and vNULL.

Referenced by create_empty_loop_on_edge(), and loopify().

Variable Documentation

edge mfb_kj_edge

A callback for make_forwarder block, to redirect all edges except for
   MFB_KJ_EDGE to the entry part.  E is the edge for that we should decide
   whether to redirect it.

Referenced by mfb_keep_just(), and thread_through_loop_header().

Functions

Variables

Function Documentation

Variable Documentation