Data Structures
struct	fixup_edge_d
struct	fixup_vertex_d
struct	fixup_graph_d
struct	queue_d
struct	augmenting_path_d

Typedefs
typedef struct fixup_edge_d	fixup_edge_type
typedef fixup_edge_type *	fixup_edge_p
typedef struct fixup_vertex_d	fixup_vertex_type
typedef fixup_vertex_type *	fixup_vertex_p
typedef struct fixup_graph_d	fixup_graph_type
typedef struct queue_d	queue_type
typedef struct augmenting_path_d	augmenting_path_type

Enumerations
enum	edge_type { INVALID_EDGE, VERTEX_SPLIT_EDGE, REDIRECT_EDGE, REVERSE_EDGE, SOURCE_CONNECT_EDGE, SINK_CONNECT_EDGE, BALANCE_EDGE, REDIRECT_NORMALIZED_EDGE, REVERSE_NORMALIZED_EDGE }

Functions
static void	print_basic_block ()
static void	print_edge ()
static void	dump_fixup_edge ()
static void	dump_fixup_graph ()
static double	mcf_ln ()
static double	mcf_sqrt ()
static fixup_edge_p	add_edge ()
static void	add_fixup_edge (fixup_graph_type *fixup_graph, int src, int dest, edge_type type, gcov_type weight, gcov_type cost, gcov_type max_capacity)
static void	add_rfixup_edge (fixup_graph_type *fixup_graph, int src, int dest, gcov_type rflow, gcov_type cost)
static fixup_edge_p	find_fixup_edge ()
static void	delete_fixup_graph ()
static void	create_fixup_graph ()
static void	init_augmenting_path ()
static void	free_augmenting_path ()
static void	init_queue ()
static bool	is_empty ()
static void	enqueue ()
static int	dequeue ()
static bool	cancel_negative_cycle (fixup_graph_type fixup_graph, int pi, gcov_type d, int cycle)
static void	compute_residual_flow ()
static int	find_augmenting_path (fixup_graph_type fixup_graph, augmenting_path_type augmenting_path, int source, int sink)
static gcov_type	find_max_flow ()
static void	adjust_cfg_counts ()
static void	find_minimum_cost_flow ()
gcov_type	sum_edge_counts ()
void	mcf_smooth_cfg ()

Typedef Documentation

typedef struct augmenting_path_d augmenting_path_type

Structure used in the maximal flow routines to find augmenting path.

typedef fixup_edge_type* fixup_edge_p

typedef struct fixup_edge_d fixup_edge_type

Structure to represent an edge in the fixup graph.

typedef struct fixup_graph_d fixup_graph_type

Fixup graph used in the MCF algorithm.

typedef fixup_vertex_type* fixup_vertex_p

typedef struct fixup_vertex_d fixup_vertex_type

Structure to represent a vertex in the fixup graph.

typedef struct queue_d queue_type

Enumeration Type Documentation

enum edge_type

Enumerator:

INVALID_EDGE
VERTEX_SPLIT_EDGE
REDIRECT_EDGE
REVERSE_EDGE
SOURCE_CONNECT_EDGE
SINK_CONNECT_EDGE
BALANCE_EDGE
REDIRECT_NORMALIZED_EDGE
REVERSE_NORMALIZED_EDGE

Function Documentation

static fixup_edge_p add_edge ( )

static

Common code shared between add_fixup_edge and add_rfixup_edge. Adds an edge
   (SRC->DEST) to the edge_list maintained in FIXUP_GRAPH with cost of the edge
   added set to COST.

References fixup_edge_d::cost, fixup_edge_d::dest, dump_file, dump_fixup_edge(), fixup_graph_d::edge_list, fixup_graph_d::num_edges, fixup_edge_d::src, fixup_vertex_d::succ_edges, and fixup_graph_d::vertex_list.

static void add_fixup_edge	(	fixup_graph_type *	fixup_graph,
		int	src,
		int	dest,
		edge_type	type,
		gcov_type	weight,
		gcov_type	cost,
		gcov_type	max_capacity
	)

static

Add a fixup edge (src->dest) with attributes TYPE, WEIGHT, COST and
   MAX_CAPACITY to the edge_list in the fixup graph.

References add_edge(), fixup_edge_d::max_capacity, fixup_edge_d::type, type(), and fixup_edge_d::weight.

Referenced by create_fixup_graph().

static void add_rfixup_edge	(	fixup_graph_type *	fixup_graph,
		int	src,
		int	dest,
		gcov_type	rflow,
		gcov_type	cost
	)

static

Add a residual edge (SRC->DEST) with attributes RFLOW and COST
   to the fixup graph.

References add_edge(), INVALID_EDGE, fixup_edge_d::is_rflow_valid, fixup_edge_d::rflow, and fixup_edge_d::type.

Referenced by compute_residual_flow().

static void adjust_cfg_counts ( )

static

Computes the corrected edge and basic block weights using FIXUP_GRAPH
   after applying the find_minimum_cost_flow() routine.

References edge_def::count, basic_block_def::count, current_function_name(), edge_def::dest, dump_file, find_fixup_edge(), edge_def::flags, fixup_edge_d::flow, HOST_WIDEST_INT_PRINT_DEC, basic_block_def::index, fixup_edge_d::norm_vertex_index, basic_block_def::preds, print_edge(), edge_def::probability, basic_block_def::succs, and sum_edge_counts().

Referenced by mcf_smooth_cfg().

static bool cancel_negative_cycle	(	fixup_graph_type *	fixup_graph,
		int *	pi,
		gcov_type *	d,
		int *	cycle
	)

static

@verbatim Finds a negative cycle in the residual network using

the Bellman-Ford algorithm. The flow on the found cycle is reversed by the minimum residual capacity of that cycle. ENTRY and EXIT vertices are not considered.

Parameters: FIXUP_GRAPH - Residual graph (input/output) The following are allocated/freed by the caller: PI - Vector to hold predecessors in path (pi = pred index) D - D[I] holds minimum cost of path from i to sink CYCLE - Vector to hold the minimum cost cycle

Return: true if a negative cycle was found, false otherwise.

References fixup_edge_d::cost, fixup_edge_d::dest, dump_file, fixup_graph_d::edge_list, find_fixup_edge(), fixup_edge_d::flow, HOST_WIDEST_INT_PRINT_DEC, fixup_edge_d::is_rflow_valid, fixup_graph_d::new_entry_index, fixup_graph_d::num_edges, fixup_graph_d::num_vertices, fixup_edge_d::rflow, fixup_edge_d::src, and fixup_edge_d::type.

Referenced by find_minimum_cost_flow().

static void compute_residual_flow ( )

static

Computes the residual flow for FIXUP_GRAPH by setting the rflow field of
   the edges. ENTRY and EXIT vertices should not be considered.

References add_rfixup_edge(), fixup_edge_d::cost, fixup_edge_d::dest, dump_file, fixup_graph_d::edge_list, fixup_edge_d::flow, fixup_edge_d::is_rflow_valid, fixup_edge_d::max_capacity, fixup_graph_d::num_edges, fixup_edge_d::rflow, and fixup_edge_d::src.

Referenced by find_max_flow().

static void create_fixup_graph ( )

static

Creates a fixup graph FIXUP_GRAPH from the function CFG.

References add_fixup_edge(), BALANCE_EDGE, fixup_edge_d::cost, edge_def::count, basic_block_def::count, edge_def::dest, fixup_edge_d::dest, dump_file, dump_fixup_edge(), dump_fixup_graph(), fixup_graph_d::edge_list, find_fixup_edge(), free(), HOST_WIDEST_INT_PRINT_DEC, basic_block_def::index, fixup_edge_d::max_capacity, mcf_sqrt(), fixup_graph_d::new_entry_index, fixup_graph_d::new_exit_index, fixup_edge_d::norm_vertex_index, fixup_graph_d::num_edges, fixup_graph_d::num_vertices, REDIRECT_EDGE, REVERSE_EDGE, REVERSE_NORMALIZED_EDGE, SINK_CONNECT_EDGE, SOURCE_CONNECT_EDGE, fixup_edge_d::src, basic_block_def::succs, fixup_edge_d::type, fixup_graph_d::vertex_list, VERTEX_SPLIT_EDGE, and fixup_edge_d::weight.

Referenced by mcf_smooth_cfg().

static void delete_fixup_graph ( )

static

Cleanup routine to free structures in FIXUP_GRAPH.

References fixup_graph_d::edge_list, free(), fixup_graph_d::num_vertices, fixup_vertex_d::succ_edges, and fixup_graph_d::vertex_list.

Referenced by mcf_smooth_cfg().

static int dequeue ( )

static

Return the first element in QUEUE_LIST.

References queue_d::head, and queue_d::queue.

Referenced by find_augmenting_path().

static void dump_fixup_edge ( )

static

Dump out the attributes of a given edge FEDGE in the fixup_graph to a
   file.

References BALANCE_EDGE, fixup_edge_d::cost, fixup_edge_d::dest, fixup_edge_d::flow, HOST_WIDEST_INT_PRINT_DEC, fixup_edge_d::is_rflow_valid, fixup_edge_d::max_capacity, print_edge(), REDIRECT_EDGE, REDIRECT_NORMALIZED_EDGE, REVERSE_EDGE, REVERSE_NORMALIZED_EDGE, fixup_edge_d::rflow, SINK_CONNECT_EDGE, SOURCE_CONNECT_EDGE, fixup_edge_d::src, fixup_edge_d::type, and VERTEX_SPLIT_EDGE.

Referenced by add_edge(), create_fixup_graph(), and dump_fixup_graph().

static void dump_fixup_graph ( )

static

Print out the edges and vertices of the given FIXUP_GRAPH, into the dump
   file. The input string MSG is printed out as a heading.

References current_function_name(), dump_fixup_edge(), fixup_edge_d::is_rflow_valid, fixup_graph_d::new_exit_index, fixup_graph_d::num_edges, fixup_graph_d::num_vertices, fixup_vertex_d::succ_edges, fixup_edge_d::type, and fixup_graph_d::vertex_list.

Referenced by create_fixup_graph(), find_max_flow(), and find_minimum_cost_flow().

static void enqueue ( )

static

Insert element X into QUEUE_LIST.

References queue_d::queue, queue_d::size, and queue_d::tail.

Referenced by find_augmenting_path().

static int find_augmenting_path	(	fixup_graph_type *	fixup_graph,
		augmenting_path_type *	augmenting_path,
		int	source,
		int	sink
	)

static

Uses Edmonds-Karp algorithm - BFS to find augmenting path from SOURCE to
   SINK. The fields in the edge vector in the FIXUP_GRAPH are not modified by
   this routine. The vector bb_pred in the AUGMENTING_PATH structure is updated
   to reflect the path found.
   Returns: 0 if no augmenting path is found, 1 otherwise.

References augmenting_path_d::bb_pred, dequeue(), fixup_edge_d::dest, enqueue(), init_queue(), is_empty(), augmenting_path_d::is_visited, fixup_graph_d::num_vertices, augmenting_path_d::queue_list, fixup_edge_d::rflow, fixup_vertex_d::succ_edges, and fixup_graph_d::vertex_list.

Referenced by find_max_flow().

static fixup_edge_p find_fixup_edge ( )

static

Return the pointer to fixup edge SRC->DEST or NULL if edge does not
   exist in the FIXUP_GRAPH.

References fixup_edge_d::dest, fixup_vertex_d::succ_edges, and fixup_graph_d::vertex_list.

Referenced by adjust_cfg_counts(), cancel_negative_cycle(), create_fixup_graph(), and find_max_flow().

static gcov_type find_max_flow ( )

static

@verbatim Routine to find the maximal flow:

Algorithm:

Initialize flow to 0
Find an augmenting path form source to sink.
Send flow equal to the path's residual capacity along the edges of this path.
Repeat steps 2 and 3 until no new augmenting path is found.

Parameters: SOURCE: index of source vertex (input) SINK: index of sink vertex (input) FIXUP_GRAPH: adjacency matrix representing the graph. The flow of the edges will be set to have a valid maximal flow by this routine. (input) Return: Maximum flow possible.

References augmenting_path_d::bb_pred, compute_residual_flow(), dump_file, dump_fixup_graph(), fixup_graph_d::edge_list, find_augmenting_path(), find_fixup_edge(), fixup_edge_d::flow, free_augmenting_path(), HOST_WIDEST_INT_PRINT_DEC, init_augmenting_path(), fixup_graph_d::num_edges, fixup_graph_d::num_vertices, print_basic_block(), fixup_edge_d::rflow, and fixup_edge_d::type.

Referenced by find_minimum_cost_flow().

static void find_minimum_cost_flow ( )

static

@verbatim Implements the negative cycle canceling algorithm to compute a minimum cost

flow. Algorithm:

Find maximal flow.
Form residual network
Repeat: While G contains a negative cost cycle C, reverse the flow on the found cycle by the minimum residual capacity in that cycle.
Form the minimal cost flow f(u,v) = rf(v, u) Input: FIXUP_GRAPH - Initial fixup graph. The flow field is modified to represent the minimum cost flow.

References cancel_negative_cycle(), dump_file, dump_fixup_graph(), find_max_flow(), free(), fixup_graph_d::new_entry_index, fixup_graph_d::new_exit_index, fixup_graph_d::num_edges, and fixup_graph_d::num_vertices.

Referenced by mcf_smooth_cfg().

static void free_augmenting_path ( )

static

Free the structures in AUGMENTING_PATH.

References augmenting_path_d::bb_pred, free(), augmenting_path_d::is_visited, queue_d::queue, and augmenting_path_d::queue_list.

Referenced by find_max_flow().

static void init_augmenting_path ( )

static

Allocates space for the structures in AUGMENTING_PATH.  The space needed is
   proportional to the number of nodes in the graph, which is given by
   GRAPH_SIZE.

References augmenting_path_d::bb_pred, augmenting_path_d::is_visited, queue_d::queue, augmenting_path_d::queue_list, and queue_d::size.

Referenced by find_max_flow().

static void init_queue ( )

static

Queue routines. Assumes queue will never overflow.

References queue_d::head, and queue_d::tail.

Referenced by find_augmenting_path().

static bool is_empty ( )

static

Return true if QUEUE_LIST is empty.

References queue_d::head, and queue_d::tail.

Referenced by add_conditions_to_domain(), allocate_phi_node(), find_augmenting_path(), loc_exp_dep_alloc(), loc_exp_dep_clear(), and loc_exp_dep_set().

static double mcf_ln ( )

static

Utility routines.

ln() implementation: approximate calculation. Returns ln of X.

void mcf_smooth_cfg ( void )

Main routine. Smoothes the initial assigned basic block and edge counts using
   a minimum cost flow algorithm, to ensure that the flow consistency rule is
   obeyed: sum of outgoing edges = sum of incoming edges for each basic
   block.

References adjust_cfg_counts(), create_fixup_graph(), delete_fixup_graph(), find_minimum_cost_flow(), and memset().

Referenced by compute_branch_probabilities().

static double mcf_sqrt ( )

static

sqrt() implementation: based on open source QUAKE3 code (magic sqrt
   implementation) by John Carmack.  Returns sqrt of X.

Referenced by create_fixup_graph().

static void print_basic_block ( )

static

Function definitions.

Dump routines to aid debugging.

Print basic block with index N for FIXUP_GRAPH in n' and n'' format.

References fixup_graph_d::new_entry_index, and fixup_graph_d::new_exit_index.

Referenced by find_max_flow(), and print_edge().

static void print_edge ( )

static

Print edge S->D for given fixup_graph with n' and n'' format.
   PARAMETERS:
   S is the index of the source vertex of the edge (input) and
   D is the index of the destination vertex of the edge (input) for the given
   fixup_graph (input).

References print_basic_block().

Referenced by adjust_cfg_counts(), and dump_fixup_edge().

gcov_type sum_edge_counts ( )

Compute the sum of the edge counts in TO_EDGES.

References edge_def::count.

Referenced by adjust_cfg_counts(), is_inconsistent(), and set_bb_counts().

Data Structures

Typedefs

Enumerations

Functions

Typedef Documentation

Enumeration Type Documentation

Function Documentation