GCC Middle and Back End API Reference
cfgloop.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "cfghooks.h"
#include "gimple-ssa.h"
#include "diagnostic-core.h"
#include "cfganal.h"
#include "cfgloop.h"
#include "gimple-iterator.h"
#include "dumpfile.h"
#include "tree-ssa.h"
#include "tree-pretty-print.h"
#include "sreal.h"
Include dependency graph for cfgloop.cc:

Macros

#define HEAVY_EDGE_RATIO   8
 
#define HEAVY_EDGE_MIN_SAMPLES   10
 

Functions

static void flow_loops_cfg_dump (FILE *)
 
bool flow_loop_nested_p (const class loop *outer, const class loop *loop)
 
class loopsuperloop_at_depth (class loop *loop, unsigned depth)
 
static vec< edgeget_loop_latch_edges (const class loop *loop)
 
void flow_loop_dump (const class loop *loop, FILE *file, void(*loop_dump_aux)(const class loop *, FILE *, int), int verbose)
 
void flow_loops_dump (FILE *file, void(*loop_dump_aux)(const class loop *, FILE *, int), int verbose)
 
void flow_loop_free (class loop *loop)
 
void flow_loops_free (struct loops *loops)
 
int flow_loop_nodes_find (basic_block header, class loop *loop)
 
static void establish_preds (class loop *loop, class loop *father)
 
void flow_loop_tree_node_add (class loop *father, class loop *loop, class loop *after)
 
void flow_loop_tree_node_remove (class loop *loop)
 
class loopalloc_loop (void)
 
void init_loops_structure (struct function *fn, struct loops *loops, unsigned num_loops)
 
bool bb_loop_header_p (basic_block header)
 
struct loopsflow_loops_find (struct loops *loops)
 
static int sort_sibling_loops_cmp (const void *la_, const void *lb_)
 
void sort_sibling_loops (function *fn)
 
static edge find_subloop_latch_edge_by_profile (vec< edge > latches)
 
static edge find_subloop_latch_edge_by_ivs (class loop *loop, vec< edge > latches)
 
static edge find_subloop_latch_edge (class loop *loop)
 
static bool mfb_redirect_edges_in_set (edge e)
 
static void form_subloop (class loop *loop, edge latch)
 
static void merge_latch_edges (class loop *loop)
 
static void disambiguate_multiple_latches (class loop *loop)
 
void disambiguate_loops_with_multiple_latches (void)
 
bool flow_bb_inside_loop_p (const class loop *loop, const_basic_block bb)
 
static bool glb_enum_p (const_basic_block bb, const void *glb_loop)
 
unsigned get_loop_body_with_size (const class loop *loop, basic_block *body, unsigned max_size)
 
basic_blockget_loop_body (const class loop *loop)
 
static void fill_sons_in_loop (const class loop *loop, basic_block bb, basic_block *tovisit, int *tv)
 
basic_blockget_loop_body_in_dom_order (const class loop *loop)
 
basic_blockget_loop_body_in_custom_order (const class loop *loop, int(*bb_comparator)(const void *, const void *))
 
basic_blockget_loop_body_in_custom_order (const class loop *loop, void *data, int(*bb_comparator)(const void *, const void *, void *))
 
basic_blockget_loop_body_in_bfs_order (const class loop *loop)
 
static struct loop_exitget_exit_descriptions (edge e)
 
void rescan_loop_exit (edge e, bool new_edge, bool removed)
 
void record_loop_exits (void)
 
int dump_recorded_exit (loop_exit **slot, FILE *file)
 
void dump_recorded_exits (FILE *)
 
void release_recorded_exits (function *fn)
 
auto_vec< edgeget_loop_exit_edges (const class loop *loop, basic_block *body)
 
unsigned num_loop_branches (const class loop *loop)
 
void add_bb_to_loop (basic_block bb, class loop *loop)
 
void remove_bb_from_loops (basic_block bb)
 
class loopfind_common_loop (class loop *loop_s, class loop *loop_d)
 
void delete_loop (class loop *loop)
 
static void cancel_loop (class loop *loop)
 
void cancel_loop_tree (class loop *loop)
 
DEBUG_FUNCTION void verify_loop_structure (void)
 
edge loop_latch_edge (const class loop *loop)
 
edge loop_preheader_edge (const class loop *loop)
 
bool loop_exit_edge_p (const class loop *loop, const_edge e)
 
edge single_exit (const class loop *loop)
 
bool loop_exits_to_bb_p (class loop *loop, basic_block bb)
 
bool loop_exits_from_bb_p (class loop *loop, basic_block bb)
 
dump_user_location_t get_loop_location (class loop *loop)
 
void record_niter_bound (class loop *loop, const widest_int &i_bound, bool realistic, bool upper)
 
HOST_WIDE_INT get_estimated_loop_iterations_int (class loop *loop)
 
HOST_WIDE_INT max_stmt_executions_int (class loop *loop)
 
HOST_WIDE_INT likely_max_stmt_executions_int (class loop *loop)
 
bool get_estimated_loop_iterations (class loop *loop, widest_int *nit)
 
bool get_max_loop_iterations (const class loop *loop, widest_int *nit)
 
HOST_WIDE_INT get_max_loop_iterations_int (const class loop *loop)
 
bool get_likely_max_loop_iterations (class loop *loop, widest_int *nit)
 
HOST_WIDE_INT get_likely_max_loop_iterations_int (class loop *loop)
 
int bb_loop_depth (const_basic_block bb)
 
void mark_loop_for_removal (loop_p loop)
 

Variables

static int * sort_sibling_loops_cmp_rpo
 
static hash_set< edge > * mfb_reis_set
 

Macro Definition Documentation

◆ HEAVY_EDGE_MIN_SAMPLES

#define HEAVY_EDGE_MIN_SAMPLES   10
Minimum number of samples for that we apply
find_subloop_latch_edge_by_profile heuristics.   

Referenced by find_subloop_latch_edge_by_profile().

◆ HEAVY_EDGE_RATIO

#define HEAVY_EDGE_RATIO   8
Ratio of frequencies of edges so that one of more latch edges is
considered to belong to inner loop with same header.   

Referenced by find_subloop_latch_edge_by_profile().

Function Documentation

◆ add_bb_to_loop()

◆ alloc_loop()

◆ bb_loop_depth()

◆ bb_loop_header_p()

◆ cancel_loop()

static void cancel_loop ( class loop * loop)
static
Cancels the LOOP; it must be innermost one.   

References delete_loop(), free(), gcc_assert, get_loop_body(), i, loop::inner, loop_outer(), and loop::num_nodes.

Referenced by cancel_loop_tree().

◆ cancel_loop_tree()

void cancel_loop_tree ( class loop * loop)
Cancels LOOP and all its subloops.   

References cancel_loop(), cancel_loop_tree(), and loop::inner.

Referenced by cancel_loop_tree(), destroy_loop(), and remove_path().

◆ delete_loop()

void delete_loop ( class loop * loop)
Removes LOOP from structures and frees its data.   

References current_loops, flow_loop_free(), flow_loop_tree_node_remove(), NULL, and loop::num.

Referenced by cancel_loop(), fuse_loops(), and unloop().

◆ disambiguate_loops_with_multiple_latches()

void disambiguate_loops_with_multiple_latches ( void )
Split loops with multiple latch edges.   

References cfun, disambiguate_multiple_latches(), and loop::latch.

Referenced by apply_loop_flags().

◆ disambiguate_multiple_latches()

static void disambiguate_multiple_latches ( class loop * loop)
static
LOOP may have several latch edges.  Transform it into (possibly several)
loops with single latch edge.   

References cfun, dump_file, ENTRY_BLOCK_PTR_FOR_FN, find_edge(), find_subloop_latch_edge(), form_subloop(), ggc_alloc(), loop::header, merge_latch_edges(), loop::num, and split_edge().

Referenced by disambiguate_loops_with_multiple_latches().

◆ dump_recorded_exit()

int dump_recorded_exit ( loop_exit ** slot,
FILE * file )
Dumps information about the exit in *SLOT to FILE.
Callback for htab_traverse.   

References loop_exit::e, ggc_alloc(), loop_exit::next_e, and NULL.

Referenced by dump_recorded_exits().

◆ dump_recorded_exits()

void dump_recorded_exits ( FILE * file)
extern
Dumps the recorded exits of loops to FILE.   

References current_loops, dump_recorded_exit(), and ggc_alloc().

◆ establish_preds()

static void establish_preds ( class loop * loop,
class loop * father )
static
Records the vector of superloops of the loop LOOP, whose immediate
superloop is FATHER.   

References establish_preds(), FOR_EACH_VEC_SAFE_ELT, ggc_alloc(), i, loop::inner, loop_depth(), loop::superloops, and vec_alloc().

Referenced by establish_preds(), and flow_loop_tree_node_add().

◆ fill_sons_in_loop()

static void fill_sons_in_loop ( const class loop * loop,
basic_block bb,
basic_block * tovisit,
int * tv )
static
Fills dominance descendants inside LOOP of the basic block BB into
array TOVISIT from index *TV.   

References CDI_DOMINATORS, dominated_by_p(), fill_sons_in_loop(), first_dom_son(), flow_bb_inside_loop_p(), ggc_alloc(), loop::latch, next_dom_son(), and NULL.

Referenced by fill_sons_in_loop(), and get_loop_body_in_dom_order().

◆ find_common_loop()

◆ find_subloop_latch_edge()

static edge find_subloop_latch_edge ( class loop * loop)
static
If we can determine that one of the several latch edges of LOOP behaves
as a latch edge of a separate subloop, returns this edge.  Otherwise
returns NULL.   

References current_ir_type(), find_subloop_latch_edge_by_ivs(), find_subloop_latch_edge_by_profile(), get_loop_latch_edges(), ggc_alloc(), IR_GIMPLE, loop::latch, and NULL.

Referenced by disambiguate_multiple_latches().

◆ find_subloop_latch_edge_by_ivs()

static edge find_subloop_latch_edge_by_ivs ( class loop * loop,
vec< edge > latches )
static
Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
on the structure of induction variables.  Returns this edge, or NULL if we
do not find any.

We are quite conservative, and look just for an obvious simple innermost
loop (which is the case where we would lose the most performance by not
disambiguating the loop).  More precisely, we look for the following
situation: The source of the chosen latch edge dominates sources of all
the other latch edges.  Additionally, the header does not contain a phi node
such that the argument from the chosen edge is equal to the argument from
another edge.   

References CDI_DOMINATORS, dominated_by_p(), dump_file, flow_bb_inside_loop_p(), FOR_EACH_VEC_ELT, ggc_alloc(), gimple_bb(), gsi_end_p(), gsi_next(), gsi_start_phis(), loop::header, i, basic_block_def::index, loop::latch, NULL, gphi_iterator::phi(), PHI_ARG_DEF_FROM_EDGE, SSA_NAME_DEF_STMT, and TREE_CODE.

Referenced by find_subloop_latch_edge().

◆ find_subloop_latch_edge_by_profile()

static edge find_subloop_latch_edge_by_profile ( vec< edge > latches)
static
If the profile info is available, finds an edge in LATCHES that much more
frequent than the remaining edges.  Returns such an edge, or NULL if we do
not find one.

We do not use guessed profile here, only the measured one.  The guessed
profile is usually too flat and unreliable for this (and it is mostly based
on the loop structure of the program, so it does not make much sense to
derive the loop structure from it).   

References dump_file, FOR_EACH_VEC_ELT, ggc_alloc(), HEAVY_EDGE_MIN_SAMPLES, HEAVY_EDGE_RATIO, i, NULL, and profile_count::zero().

Referenced by find_subloop_latch_edge().

◆ flow_bb_inside_loop_p()

bool flow_bb_inside_loop_p ( const class loop * loop,
const_basic_block bb )
Return nonzero if basic block BB belongs to LOOP.   

References cfun, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, flow_loop_nested_p(), ggc_alloc(), and basic_block_def::loop_father.

Referenced by add_exit_phi(), add_to_dst_predicate_list(), add_to_predicate_list(), analyze_evolution_in_loop(), loop_cand::analyze_iloop_reduction_var(), analyze_initial_condition(), loop_cand::analyze_oloop_reduction_var(), analyze_scalar_evolution_1(), base_names_in_chain_on(), bb_in_loop_p(), can_move_invariant_reg(), chain_of_csts_start(), check_exit_phi(), check_loop_closed_ssa_def(), check_reduction_path(), classify_builtin_st(), compute_access_stride(), compute_added_num_insns(), create_rdg_cd_edges(), duplicate_loop_body_to_header_edge(), rpo_elim::eliminate_avail(), eliminate_dom_walker::eliminate_stmt(), evaluate_bbs(), expr_invariant_in_loop_p(), fill_always_executed_in_1(), fill_sons_in_loop(), final_range_test_p(), find_exits(), find_interesting_uses(), find_inv_vars_cb(), find_loop_guard(), find_simple_exit(), find_subloop_latch_edge_by_ivs(), find_unswitching_predicates_for_bb(), find_uses_to_rename_use(), find_vdef_in_loop(), flow_loops_find(), scev_dfs::follow_ssa_edge_inner_loop_phi(), for_all_locs_in_loop(), get_cond_invariant_branch(), get_control_equiv_head_block(), get_iv(), get_loop_body_in_bfs_order(), get_loop_exit_edges(), hoist_defs_of_uses(), hoist_guard(), init_loop_unswitch_info(), inner_loop_header_p(), insert_into_preds_of_block(), ip_normal_pos(), is_cond_scalar_reduction(), is_inv_store_elimination_chain(), is_reassociable_op(), iv_elimination_compare(), loop_combined_static_and_iv_p(), loop_count_in(), loop_exit_edge_p(), loop_invariant_op_p(), loop_inverted_rev_post_order_compute(), loop_iter_phi_semi_invariant_p(), loop_rev_post_order_compute(), loop_static_op_p(), mark_irreducible_loops(), may_eliminate_iv(), tree_loop_interchange::move_code_to_inner_loop(), outermost_invariant_loop_for_expr(), parloops_is_simple_reduction(), parloops_is_slp_reduction(), predict_loops(), predict_paths_for_bb(), record_invariant(), rename_variables_in_bb(), rescan_loop_exit(), scale_dominated_blocks_in_loop(), should_duplicate_loop_header_p(), single_use_in_loop(), slpeel_tree_duplicate_loop_to_edge_cfg(), ssa_name_has_uses_outside_loop_p(), ssa_semi_invariant_p(), tree_unswitch_loop(), try_create_reduction_list(), unroll_jam_possible_p(), unroll_loop_runtime_iterations(), used_outside_loop_p(), vect_create_epilog_for_reduction(), vect_do_peeling(), vect_is_simple_iv_evolution(), vect_is_simple_reduction(), vect_loop_dist_alias_call(), vect_loop_kill_debug_uses(), vect_loop_versioning(), vect_phi_first_order_recurrence_p(), vect_stmt_relevant_p(), vectorizable_early_exit(), vectorizable_induction(), vectorizable_live_operation(), and verify_loop_structure().

◆ flow_loop_dump()

void flow_loop_dump ( const class loop * loop,
FILE * file,
void(*)(const class 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.   

References FOR_EACH_VEC_ELT, free(), get_loop_body(), get_loop_latch_edges(), ggc_alloc(), loop::header, i, basic_block_def::index, loop::latch, loop_depth(), loop_outer(), loop::num, loop::num_nodes, print_loop_info(), and verbose.

Referenced by analyze_and_mark_doloop_use(), flow_loops_dump(), and tree_ssa_iv_optimize().

◆ flow_loop_free()

void flow_loop_free ( class loop * loop)

◆ flow_loop_nested_p()

◆ flow_loop_nodes_find()

int flow_loop_nodes_find ( basic_block header,
class loop * loop )
Find the nodes contained within the LOOP with header HEADER.
Return the number of nodes within the loop.   

References CDI_DOMINATORS, dominated_by_p(), loop_exit::e, FOR_EACH_EDGE, ggc_alloc(), loop::header, basic_block_def::loop_father, basic_block_def::preds, and vNULL.

Referenced by flow_loops_find().

◆ flow_loop_tree_node_add()

void flow_loop_tree_node_add ( class loop * father,
class loop * loop,
class loop * after )
Add LOOP to the loop hierarchy tree where FATHER is father of the
added loop.  If LOOP has some children, take care of that their
pred field will be initialized correctly.  If AFTER is non-null
then it's expected it's a pointer into FATHERs inner sibling
list and LOOP is added behind AFTER, otherwise it's added in front
of FATHERs siblings.   

References establish_preds(), ggc_alloc(), loop::inner, and loop::next.

Referenced by add_loop(), copy_loops(), duplicate_loop(), fix_loop_placement(), fix_loop_structure(), flow_loops_find(), input_cfg(), merge_loop_tree(), move_sese_region_to_fn(), and unloop().

◆ flow_loop_tree_node_remove()

void flow_loop_tree_node_remove ( class loop * loop)

◆ flow_loops_cfg_dump()

static void flow_loops_cfg_dump ( FILE * file)
static
Natural loop discovery code for GNU compiler.
   Copyright (C) 2000-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
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/>.   
Dump loop related CFG information.   

References cfun, FOR_EACH_BB_FN, FOR_EACH_EDGE, ggc_alloc(), basic_block_def::index, and basic_block_def::succs.

Referenced by flow_loops_dump().

◆ flow_loops_dump()

void flow_loops_dump ( FILE * file,
void(*)(const class 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.   

References cfun, current_loops, flow_loop_dump(), flow_loops_cfg_dump(), ggc_alloc(), LI_INCLUDE_ROOT, number_of_loops(), and verbose.

Referenced by analyze_function_body(), compute_alignments(), finite_function_p(), loop_optimizer_init(), and report_predictor_hitrates().

◆ flow_loops_find()

struct loops * flow_loops_find ( struct loops * loops)
Find all the natural loops in the function and save in LOOPS structure and
recalculate loop_father information in basic block structures.
If LOOPS is non-NULL then the loop structures for already recorded loops
will be re-used and their number will not change.  We assume that no
stale loops exist in LOOPS.
When LOOPS is NULL it is allocated and re-built from scratch.
Return the built LOOPS structure.   

References alloc_loop(), b, BASIC_BLOCK_FOR_FN, bb_loop_header_p(), calculate_dominance_info(), CDI_DOMINATORS, cfun, dump_file, dump_flags, loops::exits, flow_bb_inside_loop_p(), flow_loop_nodes_find(), flow_loop_tree_node_add(), flow_loop_tree_node_remove(), FOR_EACH_EDGE, free(), gcc_assert, ggc_alloc(), loop::header, i, basic_block_def::index, init_loops_structure(), loops::larray, loop::latch, basic_block_def::loop_father, n_basic_blocks_for_fn, NULL, loop::num, NUM_FIXED_BLOCKS, loop::num_nodes, pre_and_rev_post_order_compute(), basic_block_def::preds, TDF_DETAILS, loops::tree_root, and vec_safe_push().

Referenced by fix_loop_structure(), input_cfg(), and loop_optimizer_init().

◆ flow_loops_free()

void flow_loops_free ( struct loops * loops)
Free all the memory allocated for LOOPS.   

References flow_loop_free(), FOR_EACH_VEC_SAFE_ELT, i, loops::larray, and vec_free().

Referenced by loop_optimizer_finalize().

◆ form_subloop()

◆ get_estimated_loop_iterations()

bool get_estimated_loop_iterations ( class loop * loop,
widest_int * nit )
Sets NIT to the estimated number of executions of the latch of the
LOOP.  If we have no reliable estimate, the function returns false, otherwise
returns true.   

References loop::any_estimate, expected_loop_iterations_by_profile(), ggc_alloc(), loop::nb_iterations_estimate, and SIGNED.

Referenced by decide_unroll_constant_iterations(), decide_unroll_runtime_iterations(), decide_unroll_stupid(), estimated_loop_iterations(), and get_estimated_loop_iterations_int().

◆ get_estimated_loop_iterations_int()

HOST_WIDE_INT get_estimated_loop_iterations_int ( class loop * loop)
Similar to get_estimated_loop_iterations, but returns the estimate only
if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
on the number of iterations of LOOP could not be derived, returns -1.   

References wi::fits_shwi_p(), get_estimated_loop_iterations(), and ggc_alloc().

Referenced by doloop_optimize(), find_simple_exit(), and generic_predict_doloop_p().

◆ get_exit_descriptions()

static struct loop_exit * get_exit_descriptions ( edge e)
static
Returns the list of records for E as an exit of a loop.   

References current_loops, loop_exit::e, and ggc_alloc().

Referenced by verify_loop_structure().

◆ get_likely_max_loop_iterations()

bool get_likely_max_loop_iterations ( class loop * loop,
widest_int * nit )
Sets NIT to an upper bound for the maximum number of executions of the
latch of the LOOP.  If we have no reliable estimate, the function returns
false, otherwise returns true.   

References loop::any_likely_upper_bound, ggc_alloc(), loop::nb_iterations_likely_upper_bound, and SIGNED.

Referenced by decide_unroll_constant_iterations(), decide_unroll_runtime_iterations(), decide_unroll_stupid(), get_likely_max_loop_iterations_int(), and likely_max_loop_iterations().

◆ get_likely_max_loop_iterations_int()

HOST_WIDE_INT get_likely_max_loop_iterations_int ( class loop * loop)
Similar to get_max_loop_iterations, but returns the estimate only
if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
on the number of iterations of LOOP could not be derived, returns -1.   

References wi::fits_shwi_p(), get_likely_max_loop_iterations(), and ggc_alloc().

Referenced by doloop_optimize(), find_simple_exit(), generic_predict_doloop_p(), likely_max_stmt_executions_int(), parallelize_loops(), and scale_profile_for_vect_loop().

◆ get_loop_body()

basic_block * get_loop_body ( const class loop * loop)
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.   

References cfun, EXIT_BLOCK_PTR_FOR_FN, FOR_EACH_BB_FN, gcc_assert, get_loop_body_with_size(), ggc_alloc(), loop::header, loop::latch, n_basic_blocks_for_fn, and loop::num_nodes.

Referenced by analyze_function_body(), analyze_insns_in_loop(), average_num_loop_insns(), can_duplicate_loop_p(), cancel_loop(), determine_reduction_stmt(), doloop_valid_p(), draw_cfg_nodes_for_loop(), estimate_loops_at_level(), estimate_numbers_of_iterations(), find_loop_guard(), find_simple_exit(), fix_bb_placements(), fix_loop_bb_probability(), flow_loop_dump(), get_loop_body_in_custom_order(), get_loop_body_in_custom_order(), get_loop_exit_edges(), hoist_guard(), ifcvt_split_critical_edges(), init_loop_unswitch_info(), loop_has_phi_with_address_arg(), loop_nest_has_data_refs(), num_loop_branches(), num_loop_insns(), number_of_iterations_exit_assumptions(), optimize_mask_stores(), predict_loops(), referenced_in_one_insn_in_loop_p(), reset_debug_uses_in_loop(), scale_loop_frequencies(), set_uid_loop_bbs(), simplify_loop_version(), split_loop(), split_loop_on_cond(), tree_estimate_loop_size(), tree_num_loop_insns(), tree_ssa_iv_optimize_loop(), tree_unswitch_single_loop(), unloop(), unroll_loop_runtime_iterations(), update_dominators_in_loop(), update_epilogue_loop_vinfo(), vect_analyze_loop_form(), vect_do_peeling(), and verify_loop_closed_ssa().

◆ get_loop_body_in_bfs_order()

◆ get_loop_body_in_custom_order() [1/2]

basic_block * get_loop_body_in_custom_order ( const class loop * loop,
int(*)(const void *, const void *) bb_comparator )
Gets body of a LOOP sorted via provided BB_COMPARATOR.   

References get_loop_body(), ggc_alloc(), loop::num_nodes, and qsort.

Referenced by loop_distribution::stmts_from_loop().

◆ get_loop_body_in_custom_order() [2/2]

basic_block * get_loop_body_in_custom_order ( const class loop * loop,
void * data,
int(*)(const void *, const void *, void *) bb_comparator )
Same as above, but use gcc_sort_r instead of qsort.   

References gcc_sort_r(), get_loop_body(), ggc_alloc(), and loop::num_nodes.

◆ get_loop_body_in_dom_order()

◆ get_loop_body_with_size()

unsigned get_loop_body_with_size ( const class 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.   

References dfs_enumerate_from(), glb_enum_p(), and loop::header.

Referenced by add_loop(), get_loop_body(), merge_loop_tree(), slpeel_can_duplicate_loop_p(), slpeel_tree_duplicate_loop_to_edge_cfg(), unroll_jam_possible_p(), and verify_loop_structure().

◆ get_loop_exit_edges()

◆ get_loop_latch_edges()

static vec< edge > get_loop_latch_edges ( const class loop * loop)
static

◆ get_loop_location()

◆ get_max_loop_iterations()

bool get_max_loop_iterations ( const class loop * loop,
widest_int * nit )
Sets NIT to an upper bound for the maximum number of executions of the
latch of the LOOP.  If we have no reliable estimate, the function returns
false, otherwise returns true.   

References loop::any_upper_bound, ggc_alloc(), loop::nb_iterations_upper_bound, and SIGNED.

Referenced by doloop_modify(), doloop_optimize(), doloop_simplify_count(), get_max_loop_iterations_int(), iv_can_overflow_p(), loop_niters_no_overflow(), and max_loop_iterations().

◆ get_max_loop_iterations_int()

HOST_WIDE_INT get_max_loop_iterations_int ( const class loop * loop)
Similar to get_max_loop_iterations, but returns the estimate only
if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
on the number of iterations of LOOP could not be derived, returns -1.   

References wi::fits_shwi_p(), get_max_loop_iterations(), and ggc_alloc().

Referenced by expected_loop_iterations_unbounded(), find_simple_exit(), max_stmt_executions_int(), and pcom_worker::tree_predictive_commoning_loop().

◆ glb_enum_p()

static bool glb_enum_p ( const_basic_block bb,
const void * glb_loop )
static
Enumeration predicate for get_loop_body_with_size.   

References CDI_DOMINATORS, dominated_by_p(), ggc_alloc(), and loop::header.

Referenced by get_loop_body_with_size().

◆ init_loops_structure()

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

References alloc_loop(), ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, ggc_alloc(), loop::header, loops::larray, loop::latch, n_basic_blocks_for_fn, loop::num_nodes, loops::tree_root, and vec_alloc().

Referenced by flow_loops_find(), init_lowered_empty_function(), input_cfg(), and move_sese_region_to_fn().

◆ likely_max_stmt_executions_int()

HOST_WIDE_INT likely_max_stmt_executions_int ( class loop * loop)
Returns an likely upper bound on the number of executions of statements
in the LOOP.  For statements before the loop exit, this exceeds
the number of execution of the latch by one.   

References get_likely_max_loop_iterations_int(), and ggc_alloc().

Referenced by avg_loop_niter(), vector_costs::compare_inside_loop_cost(), loop_prefetch_arrays(), vect_analyze_loop_costing(), and vect_need_peeling_or_partial_vectors_p().

◆ loop_exit_edge_p()

◆ loop_exits_from_bb_p()

bool loop_exits_from_bb_p ( class loop * loop,
basic_block bb )

◆ loop_exits_to_bb_p()

bool loop_exits_to_bb_p ( class loop * loop,
basic_block bb )
Returns true when BB has an incoming edge exiting LOOP.   

References loop_exit::e, FOR_EACH_EDGE, loop_exit_edge_p(), and basic_block_def::preds.

◆ loop_latch_edge()

edge loop_latch_edge ( const class loop * loop)
Returns latch edge of LOOP.   

References find_edge(), loop::header, and loop::latch.

Referenced by add_iv_candidate_for_biv(), analyze_and_compute_bitop_with_inv_effect(), analyze_and_compute_bitwise_induction_effect(), loop_cand::analyze_iloop_reduction_var(), loop_cand::analyze_oloop_reduction_var(), connect_loop_phis(), constant_after_peeling(), create_iv(), create_parallel_loop(), create_preheader(), discover_iteration_bound_by_body_walk(), do_split_loop_on_cond(), duplicate_loop_body_to_header_edge(), easy_exit_values(), eliminate_temp_copies(), estimate_loops_at_level(), pcom_worker::find_looparound_phi(), find_vdef_in_loop(), fuse_loops(), get_base_for(), ifcvt_local_dce(), initialize_root_vars(), initialize_root_vars_lm(), initialize_root_vars_store_elim_2(), is_cond_scalar_reduction(), loop_iter_phi_semi_invariant_p(), loop_niter_by_eval(), mark_bivs(), maybe_lower_iteration_bound(), maybe_set_vectorized_backedge_value(), number_of_iterations_cltz(), number_of_iterations_cltz_complement(), number_of_iterations_popcount(), parloops_is_simple_reduction(), process_use(), slpeel_tree_duplicate_loop_to_edge_cfg(), split_loop(), fwd_jt_path_registry::thread_through_loop_header(), tree_transform_and_unroll_loop(), unloop_loops(), unroll_loop_constant_iterations(), unroll_loop_runtime_iterations(), unroll_loop_stupid(), vect_build_slp_instance(), vect_build_slp_tree_2(), vect_create_epilog_for_reduction(), vect_is_nonlinear_iv_evolution(), vect_is_simple_reduction(), vect_phi_first_order_recurrence_p(), vect_set_loop_control(), vectorizable_induction(), vectorizable_load(), vectorizable_nonlinear_induction(), vectorizable_recurr(), vectorizable_reduction(), and vectorizable_simd_clone_call().

◆ loop_preheader_edge()

edge loop_preheader_edge ( const class loop * loop)
Returns preheader edge of LOOP.   

References cfun, loop_exit::e, ENTRY_BLOCK_PTR_FOR_FN, FOR_EACH_EDGE, gcc_assert, loop::header, loop::latch, loop_outer(), LOOPS_HAVE_PREHEADERS, LOOPS_MAY_HAVE_MULTIPLE_LATCHES, loops_state_satisfies_p(), basic_block_def::preds, and single_succ_edge().

Referenced by add_preheader_seq(), analyze_and_compute_bitop_with_inv_effect(), analyze_and_compute_bitwise_induction_effect(), loop_cand::analyze_carried_vars(), analyze_function_body(), loop_cand::analyze_iloop_reduction_var(), loop_cand::analyze_induction_var(), analyze_insns_in_loop(), loop_cand::analyze_oloop_reduction_var(), bb_colder_than_loop_preheader(), block_before_loop(), build_region(), canonicalize_loop_ivs(), check_exit_phi(), compute_access_stride(), connect_loop_phis(), connect_loops(), constant_after_peeling(), copy_loop_before(), create_empty_loop_on_edge(), create_iv(), create_parallel_loop(), cse_and_gimplify_to_preheader(), destroy_loop(), determine_exit_conditions(), determine_loop_nest_reuse(), determine_value_range(), do_split_loop_on_cond(), doloop_modify(), execute_sm(), execute_sm_exit(), fill_coldest_and_hotter_out_loop(), find_bivs(), find_data_references_in_stmt(), find_invariants_bb(), pcom_worker::find_looparound_phi(), find_reduc_addr(), fix_loop_placements(), gen_parallel_loop(), generate_memcpy_builtin(), generate_memset_builtin(), generate_reduction_builtin_1(), get_base_for(), get_range_query(), get_vop_from_header(), hoist_defs_of_uses(), hoist_guard(), hoist_memory_references(), ifcvt_can_hoist(), initialize_data_dependence_relation(), initialize_reductions(), initialize_root_vars(), initialize_root_vars_lm(), initialize_root_vars_store_elim_2(), insert_init_seqs(), vec_info::insert_seq_on_entry(), instantiate_parameters(), tree_loop_interchange::interchange_loops(), loop_niter_by_eval(), loop_rev_post_order_compute(), loop_version(), move_computations_worker(), move_invariant_reg(), number_of_iterations_cltz(), number_of_iterations_cltz_complement(), number_of_iterations_popcount(), parallelize_loops(), predict_loops(), pcom_worker::prepare_initializers_chain(), resolve_mixers(), rewrite_use_compare(), scale_profile_for_vect_loop(), simplify_using_initial_values(), slpeel_can_duplicate_loop_p(), slpeel_tree_duplicate_loop_to_edge_cfg(), slpeel_update_phi_nodes_for_guard1(), split_loop(), stmt_semi_invariant_p_1(), transform_to_exit_first_loop_alt(), tree_if_conversion(), tree_loop_unroll_and_jam(), tree_transform_and_unroll_loop(), tree_unroll_loops_completely(), try_peel_loop(), try_transform_to_exit_first_loop_alt(), try_unroll_loop_completely(), unloop(), unroll_loop_constant_iterations(), unroll_loop_runtime_iterations(), vect_analyze_loop_form(), vect_build_loop_niters(), vect_build_slp_tree_2(), vect_create_data_ref_ptr(), vect_create_epilog_for_reduction(), vect_do_peeling(), vect_emit_reduction_init_stmts(), vect_enhance_data_refs_alignment(), vect_gen_vector_loop_niters(), vect_get_external_def_edge(), vect_get_gather_scatter_ops(), vect_is_nonlinear_iv_evolution(), vect_loop_dist_alias_call(), vect_loop_vectorized_call(), vect_loop_versioning(), vect_phi_initial_value(), vect_prepare_for_masked_peels(), vect_set_loop_condition_normal(), vect_set_loop_control(), vect_setup_realignment(), vect_transform_cycle_phi(), vect_transform_loop(), vect_update_ivs_after_vectorizer(), vectorizable_induction(), vectorizable_load(), vectorizable_nonlinear_induction(), vectorizable_recurr(), and vectorizable_simd_clone_call().

◆ mark_loop_for_removal()

◆ max_stmt_executions_int()

HOST_WIDE_INT max_stmt_executions_int ( class loop * loop)
Returns an upper bound on the number of executions of statements
in the LOOP.  For statements before the loop exit, this exceeds
the number of execution of the latch by one.   

References get_max_loop_iterations_int(), and ggc_alloc().

Referenced by analyze_siv_subscript_cst_affine(), analyze_subscript_affine_affine(), compute_overlap_steps_for_affine_1_2(), and vect_known_niters_smaller_than_vf().

◆ merge_latch_edges()

static void merge_latch_edges ( class loop * loop)
static

◆ mfb_redirect_edges_in_set()

static bool mfb_redirect_edges_in_set ( edge e)
static

◆ num_loop_branches()

unsigned num_loop_branches ( const class loop * loop)
Counts the number of conditional branches inside LOOP.   

References cfun, EDGE_COUNT, EXIT_BLOCK_PTR_FOR_FN, free(), gcc_assert, get_loop_body(), i, loop::latch, and loop::num_nodes.

Referenced by decide_unroll_stupid().

◆ record_loop_exits()

◆ record_niter_bound()

void record_niter_bound ( class loop * loop,
const widest_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.   

References loop::any_estimate, loop::any_likely_upper_bound, loop::any_upper_bound, ggc_alloc(), wi::ltu_p(), wi::min_precision(), loop::nb_iterations_estimate, loop::nb_iterations_likely_upper_bound, loop::nb_iterations_upper_bound, and SIGNED.

Referenced by branch_prob(), canonicalize_loop_induction_variables(), discover_iteration_bound_by_body_walk(), estimate_numbers_of_iterations(), iv_number_of_iterations(), maybe_lower_iteration_bound(), record_estimate(), and vect_do_peeling().

◆ release_recorded_exits()

◆ remove_bb_from_loops()

◆ rescan_loop_exit()

◆ single_exit()

◆ sort_sibling_loops()

◆ sort_sibling_loops_cmp()

static int sort_sibling_loops_cmp ( const void * la_,
const void * lb_ )
static

◆ superloop_at_depth()

◆ verify_loop_structure()

DEBUG_FUNCTION void verify_loop_structure ( void )
Disable warnings about missing quoting in GCC diagnostics for
the verification errors.  Their format strings don't follow GCC
diagnostic conventions and the calls are ultimately followed by
a deliberate ICE triggered by a failed assertion.   
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

References bb_loop_header_p(), bitmap_bit_p, bitmap_clear(), bitmap_set_bit, calculate_dominance_info(), CDI_DOMINATORS, cfun, current_loops, dom_info_available_p(), dominated_by_p(), loop_exit::e, EDGE_COUNT, ENTRY_BLOCK_PTR_FOR_FN, error(), EXIT_BLOCK_PTR_FOR_FN, loop::exits, find_edge(), find_released_ssa_name(), basic_block_def::flags, flow_bb_inside_loop_p(), FOR_EACH_BB_FN, FOR_EACH_EDGE, free(), free_dominance_info(), gcc_assert, get_exit_descriptions(), get_loop_body_with_size(), ggc_alloc(), loop::header, i, basic_block_def::index, last_basic_block_for_fn, loop::latch, LI_FROM_INNERMOST, basic_block_def::loop_father, loop_outer(), LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS, LOOPS_HAVE_PREHEADERS, LOOPS_HAVE_RECORDED_EXITS, LOOPS_HAVE_SIMPLE_LATCHES, LOOPS_NEED_FIXUP, loops_state_satisfies_p(), mark_irreducible_loops(), n_basic_blocks_for_fn, loop::nb_iterations, loop_exit::next, loop_exit::next_e, NULL, loop::num, loop::num_nodes, number_of_loops(), basic_block_def::preds, single_succ(), single_succ_p(), basic_block_def::succs, verify_dominators(), visited, and walk_tree.

Referenced by checking_verify_loop_structure(), execute_function_todo(), expand_omp_target(), and expand_omp_taskreg().

Variable Documentation

◆ mfb_reis_set

hash_set<edge>* mfb_reis_set
static
Callback for make_forwarder_block.  Returns true if the edge E is marked
in the set MFB_REIS_SET.   

Referenced by form_subloop(), merge_latch_edges(), and mfb_redirect_edges_in_set().

◆ sort_sibling_loops_cmp_rpo

int* sort_sibling_loops_cmp_rpo
static
qsort helper for sort_sibling_loops.   

Referenced by sort_sibling_loops(), and sort_sibling_loops_cmp().