#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "obstack.h"
#include "ggc.h"
#include "hash-table.h"
#include "alloc-pool.h"
#include "tree.h"
#include "basic-block.h"
#include "df.h"
#include "cfgloop.h"
#include "dumpfile.h"
#include "cfg-flags.def"

Include dependency graph for cfg.c:

Data Structures
struct	htab_bb_copy_original_entry
struct	bb_copy_hasher

Macros
#define	RDIV(X, Y) (((X) + (Y) / 2) / (Y))
#define	DEF_EDGE_FLAG(NAME, IDX) #NAME ,
#define	DEF_BASIC_BLOCK_FLAG(NAME, IDX) #NAME ,
#define	MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))

Functions
void	init_flow ()
static void	free_edge ()
void	clear_edges ()
basic_block	alloc_block ()
void	link_block ()
void	unlink_block ()
void	compact_blocks ()
void	expunge_block ()
static void	connect_src ()
static void	connect_dest ()
static void	disconnect_src ()
static void	disconnect_dest ()
edge	unchecked_make_edge ()
edge	cached_make_edge ()
edge	make_edge ()
edge	make_single_succ_edge ()
void	remove_edge_raw ()
void	redirect_edge_succ ()
void	redirect_edge_pred ()
void	clear_bb_flags ()
static void	check_bb_profile ()
void	dump_edge_info ()
DEBUG_FUNCTION void	debug ()
static void	alloc_aux_for_block ()
void	alloc_aux_for_blocks ()
void	clear_aux_for_blocks ()
void	free_aux_for_blocks ()
void	alloc_aux_for_edge ()
void	alloc_aux_for_edges ()
void	clear_aux_for_edges ()
void	free_aux_for_edges ()
DEBUG_FUNCTION void	debug_bb ()
DEBUG_FUNCTION basic_block	debug_bb_n ()
void	dump_bb_info (FILE *outf, basic_block bb, int indent, int flags, bool do_header, bool do_footer)
void	brief_dump_cfg ()
void	update_bb_profile_for_threading (basic_block bb, int edge_frequency, gcov_type count, edge taken_edge)
void	scale_bbs_frequencies_int ()
void	scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num, gcov_type den)
void	initialize_original_copy_tables ()
void	free_original_copy_tables ()
static void	copy_original_table_clear ()
static void	copy_original_table_set (hash_table< bb_copy_hasher > tab, unsigned obj, unsigned val)
void	set_bb_original ()
basic_block	get_bb_original ()
void	set_bb_copy ()
basic_block	get_bb_copy ()
void	set_loop_copy ()
struct loop *	get_loop_copy ()

Variables
static struct obstack	block_aux_obstack
static void *	first_block_aux_obj = 0
static struct obstack	edge_aux_obstack
static void *	first_edge_aux_obj = 0
static hash_table< bb_copy_hasher >	bb_original
static hash_table< bb_copy_hasher >	bb_copy
static hash_table< bb_copy_hasher >	loop_copy
static alloc_pool	original_copy_bb_pool

Macro Definition Documentation

#define DEF_BASIC_BLOCK_FLAG	(	NAME,
		IDX
	)	#NAME ,

#define DEF_EDGE_FLAG	(	NAME,
		IDX
	)	#NAME ,

#define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))

numbers smaller than this value are safe to multiply without getting 64bit overflow.

#define RDIV	(	X,
		Y
	)	(((X) + (Y) / 2) / (Y))

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/. This file contains low level functions to manipulate the CFG and analyze it. All other modules should not transform the data structure directly and use abstraction instead. The file is supposed to be ordered bottom-up and should not contain any code dependent on a particular intermediate language (RTL or trees).

Available functionality:

Initialization/deallocation init_flow, clear_edges
Low level basic block manipulation alloc_block, expunge_block
Edge manipulation make_edge, make_single_succ_edge, cached_make_edge, remove_edge
- Low level edge redirection (without updating instruction chain) redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
Dumping and debugging dump_flow_info, debug_flow_info, dump_edge_info
Allocation of AUX fields for basic blocks alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
clear_bb_flags
Consistency checking verify_flow_info
Dumping and debugging print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n

TODO: Document these "Available functionality" functions in the files that implement them.

Referenced by update_bb_profile_for_threading().

Function Documentation

static void alloc_aux_for_block ( )

static

Allocate a memory block of SIZE as BB->aux. The obstack must be first initialized by alloc_aux_for_blocks.

Verify that aux field is clear.

References basic_block_def::aux, FOR_ALL_BB, and NULL.

void alloc_aux_for_blocks ( )

Initialize the block_aux_obstack and if SIZE is nonzero, call alloc_aux_for_block for each basic block.

Check whether AUX data are still allocated.

References block_aux_obstack, clear_aux_for_blocks(), gcc_assert, and NULL.

void alloc_aux_for_edge ( )

Allocate a memory edge of SIZE as E->aux. The obstack must be first initialized by alloc_aux_for_edges.

Verify that aux field is clear.

References edge_def::aux, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, FOR_BB_BETWEEN, FOR_EACH_EDGE, NULL, and basic_block_def::succs.

void alloc_aux_for_edges ( )

Initialize the edge_aux_obstack and if SIZE is nonzero, call alloc_aux_for_edge for each basic edge.

Check whether AUX data are still allocated.

References clear_aux_for_edges(), edge_aux_obstack, gcc_assert, and NULL.

basic_block alloc_block ( void )

Allocate memory for basic_block.

References basic_block_def::next_bb, and basic_block_def::prev_bb.

void brief_dump_cfg ( )

Dumps a brief description of cfg to FILE.

edge cached_make_edge ( )

Create an edge connecting SRC and DST with FLAGS optionally using edge cache CACHE. Return the new edge, NULL if already exist.

 Does the requested edge already exist?

     The edge does not exist.  Create one and update the
     cache.

 At this point, we know that the requested edge exists.  Adjust
 flags if necessary.

References find_edge(), and edge_def::flags.

static void check_bb_profile ( )

static

Check the consistency of profile information. We can't do that in verify_flow_info, as the counts may get invalid for incompletely solved graphs, later eliminating of conditionals or roundoff errors. It is still practical to have them reported for debugging of simple testcases.

Warn about inconsistencies in the partitioning that are currently caused by profile insanities created via optimization.

References basic_block_def::count, EDGE_FREQUENCY, FOR_EACH_EDGE, basic_block_def::frequency, and basic_block_def::preds.

void clear_aux_for_blocks ( void )

Clear AUX pointers of all blocks.

References edge_aux_obstack, and gcc_obstack_init.

Referenced by alloc_aux_for_blocks(), and duplicate_computed_gotos().

void clear_aux_for_edges ( void )

Clear AUX pointers of all edges.

References alloca, first, and NULL.

Referenced by alloc_aux_for_edges().

void clear_bb_flags ( void )

Clear all basic block flags that do not have to be preserved.

Referenced by reorder_basic_blocks().

void clear_edges ( void )

Free the memory associated with the edge structures.

References FOR_EACH_EDGE, free_edge(), basic_block_def::preds, basic_block_def::succs, and vec_safe_truncate().

void compact_blocks ( void )

Sequentially order blocks and compact the arrays.

References FOR_EACH_BB, gcc_assert, basic_block_def::index, last_basic_block, n_basic_blocks, NULL, NUM_FIXED_BLOCKS, and SET_BASIC_BLOCK.

Referenced by cleanup_tree_cfg_1().

static void connect_dest ( )

inlinestatic

Connect E to E->dest.

References df_mark_solutions_dirty(), edge_iterator::index, and basic_block_def::succs.

Referenced by disconnect_dest(), and make_single_succ_edge().

static void connect_src ( )

inlinestatic

Connect E to E->src.

Referenced by disconnect_dest().

static void copy_original_table_clear ( )

static

Removes the value associated with OBJ from table TAB.

References copy_original_table_set(), and basic_block_def::index.

static void copy_original_table_set	(	hash_table< bb_copy_hasher >	tab,
		unsigned	obj,
		unsigned	val
	)

static

Sets the value associated with OBJ in table TAB to VAL. Do nothing when data structures are not initialized.

Referenced by copy_original_table_clear().

DEBUG_FUNCTION void debug ( )

FIXME (crowl): Is this desireable?

DEBUG_FUNCTION void debug_bb ( )

DEBUG_FUNCTION basic_block debug_bb_n ( )

static void disconnect_dest ( )

inlinestatic

Disconnect edge E from E->dest.

If we removed an edge in the middle of the edge vector, we need to update dest_idx of the edge that moved into the "hole".

References connect_dest(), connect_src(), edge_def::dest, execute_on_growing_pred(), edge_def::flags, n_edges, and edge_def::src.

Referenced by make_single_succ_edge().

static void disconnect_src ( )

inlinestatic

Disconnect edge E from E->src.

void dump_bb_info	(	FILE *	outf,
		basic_block	bb,
		int	indent,
		int	flags,
		bool	do_header,
		bool	do_footer
	)

Dumps cfg related information about basic block BB to OUTF. If HEADER is true, dump things that appear before the instructions contained in BB. If FOOTER is true, dump things that appear after. Flags are the TDF_* masks as documented in dumpfile.h. NB: With TDF_DETAILS, it is assumed that cfun is available, so that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE.

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

This file defines flags that may appear on basic blocks or on edges. Source files define DEF_BASIC_BLOCK_FLAG or DEF_EDGE_FLAG appropriately before including this file.

Masks for basic_block.flags.

The format of this file is: DEF_BASIC_BLOCK_FLAG(NAME, IDX). NAME is the name of the basic block flag. A flag BB_::NAME will be created and the name is used in dump_edge_info. IDX is a sequence number that is used to determine the value of the flag, which is 1 << IDX).

BB_HOT_PARTITION and BB_COLD_PARTITION should be preserved throughout the compilation, so they are never cleared.

All other flags may be cleared by clear_bb_flags(). It is generally a bad idea to rely on any flags being up-to-date.

Only set on blocks that have just been created by create_bb.

Set by find_unreachable_blocks. Do not rely on this being set in any pass.

Set for blocks in an irreducible loop by loop analysis.

Set on blocks that may actually not be single-entry single-exit block.

Set on basic blocks that the scheduler should not touch. This is used by SMS to prevent other schedulers from messing with the loop schedule.

Set on blocks that should be put in a hot section.

Set on blocks that should be put in a cold section.

Set on block that was duplicated.

Set if the label at the top of this block is the target of a non-local goto.

Set on blocks that are in RTL format.

Set on blocks that are forwarder blocks. Only used in cfgcleanup.c.

Set on blocks that cannot be threaded through. Only used in cfgcleanup.c.

Set on blocks that were modified in some way. This bit is set in df_set_bb_dirty, but not cleared by df_analyze, so it can be used to test whether a block has been modified prior to a df_analyze call.

A general visited flag for passes to use.

Set on blocks that are in a transaction. This is calculated on demand, and is available after calling compute_transaction_bits().

Masks for edge.flags.

The format of this file is: DEF_EDGE_FLAG(NAME, IDX, STRING). NAME is the name of the edge flag. A flag EDGE_::NAME will be created and the name is used in dump_edge_info. IDX is a sequence number that is used to determine the value of the flag, which is 1 << IDX).

'Straight line' flow. In GIMPLE and in cfglayout mode, all normal edges are fallthru edges. In cfgrtl mode, this flag really means that control flow falls through to the next basic block in the line.

Strange flow, like a computed jump or exception handling. Usually this means that the edge cannot be split.

Edge out of a basic block that ends with a CALL_INSN with abnormal exit, like an exception or a non-local goto. ABNORMAL_CALL edges also have ABNORMAL set. This flag is only used for the RTL CFG.

Exception edge. Exception handling edges represent possible control transfers from a trapping instruction to an exception handler. EH edges also have ABNORMAL set for the RTL CFG.

Never merge blocks via this edge. This is used for exception handling, to prevent merging away edges to the post-landing-pad basic block. This flag is only used for the RTL CFG.

Not a real edge. This is used to connect parts of the CFG that do not halt, such as infinite loops and noreturn functions, to the EXIT_BLOCK, so that traversing of the reverse CFG is possible.

A back edge, marked in a depth-first search of the CFG. Back edges are hints that this edge may be part of a loop in the CFG.

Edge in a part of the CFG that is an irreducible loop.

Edge taken when controlling predicate is nonzero. This is only used for the GIMPLE CFG.

Edge taken when controlling predicate is zero. This is only used for the GIMPLE CFG.

Edge is executable. This is only used in GIMPLE SSA-CCP and VRP. This is only used for the GIMPLE CFG.

Edge crosses between hot and cold sections, when we do partitioning. This flag is only used for the RTL CFG.

Edge from a sibcall CALL_INSN to exit. SIBCALL edges also have ABNORMAL set. This flag is only used for the RTL CFG.

Candidate for straight line flow. Only used in bb-reorder.c. This flag is only used for the RTL CFG.

Exit of a loop. This is only used in ifcvt.c. This flag is only used for the RTL CFG.

Uninstrumented edge out of a GIMPLE_TRANSACTION statement.

Abort (over) edge out of a GIMPLE_TRANSACTION statement.

void dump_edge_info ( )

 ENTRY_BLOCK_PTR/EXIT_BLOCK_PTR depend on cfun.
 Compare against ENTRY_BLOCK/EXIT_BLOCK to avoid that dependency.