cfgloopanal.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "predict.h"
#include "memmodel.h"
#include "emit-rtl.h"
#include "cfgloop.h"
#include "explow.h"
#include "expr.h"
#include "graphds.h"
#include "sreal.h"
#include "regs.h"
#include "function-abi.h"

Include dependency graph for cfgloopanal.cc:

Macros
#define	LOOP_REPR(LOOP)   ((LOOP)->num + last_basic_block_for_fn (cfun))
#define	BB_REPR(BB)   ((BB)->index + 1)

Functions
bool	just_once_each_iteration_p (const class loop *loop, const_basic_block bb)
bool	mark_irreducible_loops (void)
int	num_loop_insns (const class loop *loop)
int	average_num_loop_insns (const class loop *loop)
profile_count	loop_count_in (const class loop *loop)
bool	expected_loop_iterations_by_profile (const class loop *loop, sreal *ret, bool *reliable)
bool	maybe_flat_loop_profile (const class loop *loop)
gcov_type	expected_loop_iterations_unbounded (const class loop *loop, bool *read_profile_p)
unsigned	expected_loop_iterations (class loop *loop)
unsigned	get_loop_level (const class loop *loop)
void	init_set_costs (void)
unsigned	estimate_reg_pressure_cost (unsigned n_new, unsigned n_old, bool speed, bool call_p)
void	mark_loop_exit_edges (void)
edge	single_likely_exit (class loop *loop, const vec< edge > &exits)
auto_vec< basic_block >	get_loop_hot_path (const class loop *loop)

Variables
struct target_cfgloop	default_target_cfgloop

Macro Definition Documentation

BB_REPR

#define BB_REPR

(

BB

)

((BB)->index + 1)

Referenced by mark_irreducible_loops().

LOOP_REPR

#define LOOP_REPR

(

LOOP

)

((LOOP)->num + last_basic_block_for_fn (cfun))

Marks blocks and edges that are part of non-recognized loops; i.e. we
throw away all latch edges and mark blocks inside any remaining cycle.
Everything is a bit complicated due to fact we do not want to do this
for parts of cycles that only "pass" through some loop -- i.e. for
each cycle, we want to mark blocks that belong directly to innermost
loop containing the whole cycle.

LOOPS is the loop tree.   

Referenced by mark_irreducible_loops().

Function Documentation

average_num_loop_insns()

int average_num_loop_insns

(

const class loop *

loop

)

Counts number of insns executed on average per iteration LOOP.   

References basic_block_def::count, FOR_BB_INSNS, free(), get_loop_body(), ggc_alloc(), loop::header, i, loop::ninsns, NONDEBUG_INSN_P, loop::num_nodes, and profile_count::to_sreal_scale().

Referenced by decide_unrolling().

estimate_reg_pressure_cost()

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

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.   

References cfun, ggc_alloc(), IRA_REGION_ALL, IRA_REGION_MIXED, number_of_loops(), target_avail_regs, target_clobbered_regs, target_reg_cost, target_res_regs, and target_spill_cost.

Referenced by gain_for_invariant().

expected_loop_iterations()

unsigned expected_loop_iterations

(

class loop *

loop

)

Returns expected number of LOOP iterations.  The returned value is bounded
by REG_BR_PROB_BASE.   

References expected_loop_iterations_unbounded(), ggc_alloc(), and REG_BR_PROB_BASE.

Referenced by determine_loop_nest_reuse().

expected_loop_iterations_by_profile()

bool expected_loop_iterations_by_profile	(	const class loop *	loop,
		sreal *	ret,
		bool *	reliable )

Return true if BB profile can be used to determine the expected number of
iterations (that is number of executions of latch edge(s) for each
entry of the loop.  If this is the case initialize RET with the number
of iterations.

RELIABLE is set if profile indiates that the returned value should be
realistic estimate.  (This is the case if we read profile and did not
messed it up yet and not the case of guessed profiles.)

This function uses only CFG profile.  We track more reliable info in
loop_info structure and for loop optimization heuristics more relevant
is get_estimated_loop_iterations API.   

References basic_block_def::count, dump_file, dump_flags, ggc_alloc(), loop::header, loop_count_in(), loop::num, and TDF_DETAILS.

Referenced by branch_prob(), estimate_numbers_of_iterations(), expected_loop_iterations_unbounded(), get_estimated_loop_iterations(), maybe_flat_loop_profile(), print_loop_info(), and scale_loop_profile().

expected_loop_iterations_unbounded()

gcov_type expected_loop_iterations_unbounded	(	const class loop *	loop,
		bool *	read_profile_p )

Returns expected number of iterations of LOOP, according to
measured or guessed profile.

This functions attempts to return "sane" value even if profile
information is not good enough to derive osmething.   

References expected_loop_iterations_by_profile(), get_max_loop_iterations_int(), and ggc_alloc().

Referenced by expected_loop_iterations().

get_loop_hot_path()

auto_vec< basic_block > get_loop_hot_path

(

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 BITMAP_ALLOC, bitmap_bit_p, BITMAP_FREE, bitmap_set_bit, FOR_EACH_EDGE, ggc_alloc(), loop::header, basic_block_def::index, loop_exit_edge_p(), NULL, path, basic_block_def::succs, and visited.

Referenced by tree_estimate_loop_size().

get_loop_level()

unsigned get_loop_level

(

const class loop *

loop

)

Returns the maximum level of nesting of subloops of LOOP.   

References get_loop_level(), ggc_alloc(), and loop::inner.

Referenced by doloop_optimize(), and get_loop_level().

init_set_costs()

void init_set_costs

(

void

)

Initialize the constants for computing set costs.   

References crtl, default_function_abi, default_rtl_profile(), emit_move_insn(), end_sequence(), fixed_regs, gen_raw_REG(), gen_rtx_MEM(), get_insns(), ggc_alloc(), i, LAST_VIRTUAL_REGISTER, reg_class_contents, seq_cost(), start_sequence(), target_avail_regs, target_clobbered_regs, target_reg_cost, target_res_regs, target_spill_cost, TEST_HARD_REG_BIT, and validize_mem().

Referenced by backend_init_target().

just_once_each_iteration_p()

bool just_once_each_iteration_p	(	const class loop *	loop,
		const_basic_block	bb )

Checks whether BB is executed exactly once in each LOOP iteration.   

References CDI_DOMINATORS, dominated_by_p(), basic_block_def::flags, ggc_alloc(), loop::latch, and basic_block_def::loop_father.

Referenced by canonicalize_loop_induction_variables(), find_loop_guard(), find_loop_niter_by_eval(), iv_get_reaching_def(), latch_dominating_def(), single_dom_exit(), pcom_worker::suitable_component_p(), and update_loop_exit_probability_scale_dom_bbs().

loop_count_in()

profile_count loop_count_in

(

const class loop *

loop

)

Compute how many times loop is entered.   

References flow_bb_inside_loop_p(), FOR_EACH_EDGE, gcc_checking_assert, ggc_alloc(), loop::header, loop::latch, LOOPS_MAY_HAVE_MULTIPLE_LATCHES, loops_state_satisfies_p(), basic_block_def::preds, and profile_count::zero().

Referenced by expected_loop_iterations_by_profile(), print_loop_info(), scale_loop_profile(), and update_loop_exit_probability_scale_dom_bbs().

mark_irreducible_loops()

bool mark_irreducible_loops

(

void

)

References add_edge(), BB_REPR, CDI_DOMINATORS, cfun, current_loops, graph_edge::data, graph_edge::dest, dominated_by_p(), ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, find_common_loop(), flow_bb_inside_loop_p(), FOR_BB_BETWEEN, FOR_EACH_EDGE, free_graph(), g, gcc_assert, ggc_alloc(), graphds_scc(), i, last_basic_block_for_fn, loop_depth(), LOOP_REPR, LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS, loops_state_set(), new_graph(), NULL, loop::num, number_of_loops(), and graph_edge::src.

Referenced by apply_loop_flags(), canonicalize_induction_variables(), find_obviously_necessary_stmts(), finite_function_p(), remove_path(), tree_unroll_loops_completely(), and verify_loop_structure().

mark_loop_exit_edges()

void mark_loop_exit_edges

(

void

)

Sets EDGE_LOOP_EXIT flag for all loop exits.   

References cfun, FOR_EACH_BB_FN, FOR_EACH_EDGE, ggc_alloc(), loop_exit_edge_p(), basic_block_def::loop_father, loop_outer(), number_of_loops(), and basic_block_def::succs.

Referenced by if_convert().

maybe_flat_loop_profile()

bool maybe_flat_loop_profile

(

const class loop *

loop

)

Return true if loop CFG profile may be unrealistically flat.
This is a common case, since average loops iterate only about 5 times.
In the case we do not have profile feedback or do not know real number of
iterations during profile estimation, we are likely going to predict it with
similar low iteration count.  For static loop profiles we also artificially
cap profile of loops with known large iteration count so they do not appear
significantly more hot than other loops with unknown iteration counts.

For loop optimization heuristics we ignore CFG profile and instead
use get_estimated_loop_iterations API which returns estimate
only when it is realistic.  For unknown counts some optimizations,
like vectorizer or unroller make guess that iteration count will
be large.  In this case we need to avoid scaling down the profile
after the loop transform.   

References loop::any_estimate, loop::any_likely_upper_bound, loop::any_upper_bound, dump_file, dump_flags, expected_loop_iterations_by_profile(), wi::geu_p(), ggc_alloc(), wi::gtu_p(), wi::ltu_p(), loop::nb_iterations_estimate, loop::nb_iterations_likely_upper_bound, loop::nb_iterations_upper_bound, loop::num, TDF_DETAILS, and generic_wide_int< storage >::to_shwi().

Referenced by print_loop_info(), tree_transform_and_unroll_loop(), unroll_loop_constant_iterations(), and vect_transform_loop().

num_loop_insns()

int num_loop_insns

(

const class loop *

loop

)

Counts number of insns inside LOOP.   

References FOR_BB_INSNS, free(), get_loop_body(), i, loop::ninsns, NONDEBUG_INSN_P, and loop::num_nodes.

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

single_likely_exit()

edge single_likely_exit	(	class loop *	loop,
		const vec< edge > &	exits )

Return exit edge if loop has only one exit that is likely
to be executed on runtime (i.e. it is not EH or leading
to noreturn call.   

References cfun, loop::exits, FOR_EACH_VEC_ELT, ggc_alloc(), i, NULL, probably_never_executed_edge_p(), single_exit(), and profile_probability::very_unlikely().

Referenced by canonicalize_loop_induction_variables(), estimate_numbers_of_iterations(), and loop_exit_for_scaling().

Variable Documentation

default_target_cfgloop

struct target_cfgloop default_target_cfgloop

Natural loop analysis code for GNU compiler.
   Copyright (C) 2002-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/>.