GCC Middle and Back End API Reference
cfgloopmanip.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.






bool remove_path (edge, bool *=NULL, bitmap=NULL)
void place_new_loop (struct function *, class loop *)
void add_loop (class loop *, class loop *)
void scale_loop_frequencies (class loop *, profile_probability)
void scale_loop_profile (class loop *, profile_probability, gcov_type)
edge create_empty_if_region_on_edge (edge, tree)
class loopcreate_empty_loop_on_edge (edge, tree, tree, tree, tree, tree *, tree *, class loop *)
void unloop (class loop *, bool *, bitmap)
void unloop_loops (vec< class loop * > &loops_to_unloop, vec< int > &loops_to_unloop_nunroll, vec< edge > &edges_to_remove, bitmap loop_closed_ssa_invalidated, bool *irred_invalidated)
void copy_loop_info (class loop *loop, class loop *target)
class loopduplicate_loop (class loop *, class loop *, class loop *=NULL)
void duplicate_subloops (class loop *, class loop *)
bool can_duplicate_loop_p (const class loop *loop)
bool duplicate_loop_body_to_header_edge (class loop *, edge, unsigned, sbitmap, edge, vec< edge > *, int)
bool mfb_keep_just (edge)
basic_block create_preheader (class loop *, int)
void create_preheaders (int)
void force_single_succ_latches (void)
class looploop_version (class loop *, void *, basic_block *, profile_probability, profile_probability, profile_probability, profile_probability, bool)
void adjust_loop_info_after_peeling (class loop *loop, int npeel, bool precise)
void scale_dominated_blocks_in_loop (class loop *loop, basic_block bb, profile_count num, profile_count den)
edge update_loop_exit_probability_scale_dom_bbs (class loop *loop, edge exit_edge=NULL, profile_count desired_count=profile_count::uninitialized())
void update_exit_probability_after_unrolling (class loop *loop, edge new_exit)


edge mfb_kj_edge

Macro Definition Documentation


4 /* Update frequencies expecting
a complete peeling. @endverbatim */

Referenced by duplicate_loop_body_to_header_edge(), and try_unroll_loop_completely().


8 /* Profile is flat; do not reduce
count by unroll factor. @endverbatim */

Referenced by duplicate_loop_body_to_header_edge(), tree_transform_and_unroll_loop(), and unroll_loop_constant_iterations().




2 /* Record copy number in the aux
field of newly create BB. @endverbatim */

Referenced by duplicate_loop_body_to_header_edge(), unroll_loop_constant_iterations(), unroll_loop_runtime_iterations(), and unroll_loop_stupid().

Enumeration Type Documentation

◆ anonymous enum

Loop manipulation header.
   Copyright (C) 2014-2024 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

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
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

Function Documentation

◆ add_loop()

◆ adjust_loop_info_after_peeling()

void adjust_loop_info_after_peeling ( class loop * loop,
int npeel,
bool precise )
Update loop estimates after peeling LOOP by NPEEL.
If PRECISE is false only likely exists were duplicated and thus
do not update any estimates that are supposed to be always reliable.   

References loop::any_estimate, loop::any_likely_upper_bound, loop::any_upper_bound, gcc_unreachable, ggc_alloc(), wi::leu_p(), loop::nb_iterations_estimate, loop::nb_iterations_likely_upper_bound, and loop::nb_iterations_upper_bound.

Referenced by try_peel_loop().

◆ can_duplicate_loop_p()

bool can_duplicate_loop_p ( const class loop * loop)
Check whether LOOP's body can be duplicated.   

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

Referenced by can_unroll_loop_p(), decide_unrolling(), and parallelize_loops().

◆ copy_loop_info()

◆ create_empty_if_region_on_edge()

edge create_empty_if_region_on_edge ( edge entry_edge,
tree condition )
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, force_gimple_operand_gsi(), ggc_alloc(), gimple_build_cond_from_tree(), gsi_insert_after(), gsi_last_bb(), GSI_NEW_STMT, make_edge(), NULL, NULL_TREE, set_immediate_dominator(), single_pred_p(), single_succ_edge(), and split_edge().

◆ create_empty_loop_on_edge()

class 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,
class loop * outer )
|    - 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

References add_loop(), alloc_loop(), CDI_DOMINATORS, create_iv(), profile_probability::even(), force_gimple_operand(), force_gimple_operand_gsi(), gcc_assert, ggc_alloc(), 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(), NULL, NULL_TREE, 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(), and update_dominators_in_loop().

◆ create_preheader()

basic_block create_preheader ( class loop * loop,
int flags )
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 BB_END, cfun, CP_FALLTHRU_PREHEADERS, CP_SIMPLE_PREHEADERS, dump_file, EDGE_COMPLEX, EDGE_PRED, ENTRY_BLOCK_PTR_FOR_FN, basic_block_def::flags, FOR_EACH_EDGE, gcc_assert, ggc_alloc(), has_preds_from_loop(), loop::header, JUMP_P, loop::latch, loop_latch_edge(), make_forwarder_block(), mfb_keep_just(), mfb_kj_edge, move_block_after(), NULL, loop::num, basic_block_def::preds, single_succ_edge(), single_succ_p(), and split_edge().

Referenced by create_preheaders(), generate_loops_for_partition(), and fwd_jt_path_registry::thread_through_loop_header().

◆ create_preheaders()

void create_preheaders ( int flags)
Create preheaders for each loop; for meaning of FLAGS see create_preheader.   

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

Referenced by apply_loop_flags(), and tree_estimate_probability().

◆ duplicate_loop()

class loop * duplicate_loop ( class loop * loop,
class loop * target,
class loop * after )
Copies copy of LOOP as subloop of TARGET loop, placing newly
created loop into loops structure.  If AFTER is non-null
the new loop is added at AFTER->next, otherwise in front of TARGETs
sibling list.   

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

Referenced by copy_loops_to(), duplicate_subloops(), gimple_duplicate_sese_tail(), and slpeel_tree_duplicate_loop_to_edge_cfg().

◆ duplicate_loop_body_to_header_edge()

bool duplicate_loop_body_to_header_edge ( class loop * ,
edge ,
unsigned ,
sbitmap ,
edge ,
vec< edge > * ,
int  )

◆ duplicate_subloops()

void duplicate_subloops ( class loop * loop,
class loop * target )
Copies structure of subloops of LOOP into TARGET loop, placing
newly created loops into loop tree at the end of TARGETs sibling
list in the original order.   

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

Referenced by copy_loops_to(), duplicate_subloops(), gimple_duplicate_sese_tail(), and slpeel_tree_duplicate_loop_to_edge_cfg().

◆ force_single_succ_latches()

void force_single_succ_latches ( void )
Forces all loop latches to have only single successor.   

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

Referenced by apply_loop_flags().

◆ loop_version()

class loop * loop_version ( class loop * loop,
void * cond_expr,
basic_block * condition_bb,
profile_probability then_prob,
profile_probability else_prob,
profile_probability then_scale,
profile_probability else_scale,
bool place_after )
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). COND_EXPR
may be a run time test for things that were not resolved by static
analysis (overlapping ranges (anti-aliasing), alignment, etc.).

If non-NULL, CONDITION_BB is set to the basic block containing the

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 add_bb_to_loop(), add_loop(), alloc_loop(), cfg_hook_duplicate_loop_body_to_header_edge(), copy_loop_info(), free(), get_bb_copy(), get_loop_body_in_dom_order(), ggc_alloc(), loop::header, i, loop::latch, loop_outer(), loop_preheader_edge(), loop_redirect_edge(), lv_adjust_loop_entry_edge(), lv_flush_pending_stmts(), move_block_after(), NULL, remove_bb_from_loops(), scale_loop_frequencies(), set_loop_copy(), single_pred_edge(), single_succ_edge(), split_edge(), and update_dominators_in_loop().

Referenced by do_split_loop_on_cond(), gen_parallel_loop(), split_loop(), tree_transform_and_unroll_loop(), tree_unswitch_loop(), vect_loop_versioning(), version_loop_by_alias_check(), and version_loop_for_if_conversion().

◆ mfb_keep_just()

bool mfb_keep_just ( edge e)

◆ place_new_loop()

void place_new_loop ( struct function * fn,
class loop * 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().

Referenced by add_loop(), copy_loops(), duplicate_loop(), and input_cfg().

◆ remove_path()

◆ scale_dominated_blocks_in_loop()

void scale_dominated_blocks_in_loop ( class loop * loop,
basic_block bb,
profile_count num,
profile_count den )

◆ scale_loop_frequencies()

◆ scale_loop_profile()

void scale_loop_profile ( class loop * loop,
profile_probability p,
gcov_type iteration_bound )
Scale profile in LOOP by P.
If ITERATION_BOUND is not -1, scale even further if loop is predicted
to iterate too many times.
Before caling this function, preheader block profile should be already
scaled to final count.  This is necessary because loop iterations are
determined by comparing header edge count to latch ege count and thus
they need to be scaled synchronously.   

References profile_probability::always(), basic_block_def::count, profile_probability::dump(), dump_file, dump_flags, expected_loop_iterations_by_profile(), ggc_alloc(), loop::header, loop_count_in(), loop_exit_for_scaling(), loop::num, scale_loop_frequencies(), TDF_DETAILS, sreal::to_double(), profile_count::uninitialized(), and update_loop_exit_probability_scale_dom_bbs().

Referenced by scale_profile_for_vect_loop(), tree_transform_and_unroll_loop(), try_unroll_loop_completely(), and vect_do_peeling().

◆ unloop()

void unloop ( class 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(), ggc_alloc(), i, 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().

◆ unloop_loops()

void unloop_loops ( vec< class loop * > & loops_to_unloop,
vec< int > & loops_to_unloop_nunroll,
vec< edge > & edges_to_remove,
bitmap loop_closed_ssa_invalidated,
bool * irred_invalidated )
Cancel all fully unrolled loops by putting __builtin_unreachable
on the latch edge.  
We do it after all unrolling since unlooping moves basic blocks
across loop boundaries trashing loop closed SSA form as well
as SCEV info needed to be intact during unrolling. 

IRRED_INVALIDATED is used to bookkeep if information about
irreducible regions may become invalid as a result
of the transformation.  
LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
when we need to go into loop closed SSA form.   

References add_bb_to_loop(), BASIC_BLOCK_FOR_FN, CDI_DOMINATORS, cfun, create_basic_block(), current_loops, edges_to_remove, FOR_EACH_VEC_ELT, gcc_assert, ggc_alloc(), gimple_build_builtin_unreachable(), gsi_insert_after(), GSI_NEW_STMT, gsi_start_bb(), i, loop::latch, loop_latch_edge(), loops_to_unloop, loops_to_unloop_nunroll, make_edge(), profile_probability::never(), NULL, remove_exits_and_undefined_stmts(), remove_path(), set_immediate_dominator(), unloop(), and profile_count::zero().

Referenced by canonicalize_induction_variables(), and tree_unroll_loops_completely().

◆ update_exit_probability_after_unrolling()

void update_exit_probability_after_unrolling ( class loop * loop,
edge new_exit )

◆ update_loop_exit_probability_scale_dom_bbs()

edge update_loop_exit_probability_scale_dom_bbs ( class loop * loop,
edge exit_edge,
profile_count desired_count )
Assume that loop's entry count and profile up to a given EXIT_EDGE is
consistent. Update exit probability so loop exists with PROFILE_COUNT
and rescale profile of basic blocks inside loop dominated by EXIT_EDGE->src.

This is useful after number of iteraitons of loop has changed.
If EXIT_EDGE is NULL, the function will try to identify suitable exit.
If DESIRED_COUNT is NULL, loop entry count will be used.
In consistent profile usually loop exists as many times as it is entred.

Return updated exit if successfull and NULL otherwise.  

References cfun, basic_block_def::count, dump_file, dump_flags, FOR_EACH_EDGE, ggc_alloc(), just_once_each_iteration_p(), loop::latch, loop_count_in(), loop_exit_edge_p(), loop_exit_for_scaling(), NULL, loop::num, scale_dominated_blocks_in_loop(), set_edge_probability_and_rescale_others(), single_pred_p(), and TDF_DETAILS.

Referenced by scale_loop_profile(), split_loop(), tree_transform_and_unroll_loop(), and unroll_loop_constant_iterations().

Variable Documentation

◆ mfb_kj_edge

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 create_preheader(), mfb_keep_just(), and fwd_jt_path_registry::thread_through_loop_header().