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 add_edge(), INVALID_EDGE, fixup_edge_d::is_rflow_valid, fixup_edge_d::rflow, and fixup_edge_d::type.

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.

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.

     This edge is not a valid edge - merely used to hold residual flow.

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

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.

         Fixup BB.

         Deduct flow from normalized reverse edge.

         Fixup edge.

             Treat edges with ignore attribute set as if they don't exist.

                 Non-self edge.

                 Deduct flow from normalized reverse edge.

                 Handle self edges. Self edge is split with a normalization
                 vertex. Here i=j.

     Compute edge probabilities.

References dump_file, fixup_edge_d::flow, HOST_WIDEST_INT_PRINT_DEC, fixup_edge_d::norm_vertex_index, and print_edge().

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.

     Initialize.

     Skip ENTRY.

     Relax.

     No negative cycles exist.

     Detect.

     Augment the cycle with the cycle's minimum residual capacity.

                 cycle[k] -> ... -> cycle[i].

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.

static void create_fixup_graph ( )

static

   Creates a fixup graph FIXUP_GRAPH from the function CFG.

     Vector to hold D(v) = sum_out_edges(v) - sum_in_edges(v).

     Each basic_block will be split into 2 during vertex transformation.

     Count the new SOURCE and EXIT vertices to be added.

     In create_fixup_graph: Each basic block and edge can be split into 3
     edges. Number of balance edges = n_basic_blocks. So after
     create_fixup_graph:
     max_edges = 4 * n_basic_blocks + 3 * n_edges
     Accounting for residual flow edges
     max_edges = 2 * (4 * n_basic_blocks + 3 * n_edges)
     = 8 * n_basic_blocks + 6 * n_edges
     < 8 * n_basic_blocks + 8 * n_edges.

     Initial num of vertices in the fixup graph.

     Fixup graph vertex list.

     Fixup graph edge list.

     Compute constants b, k_pos, k_neg used in the cost function calculation.
     b = sqrt(avg_vertex_weight(cfg)); k_pos = b; k_neg = 50b.

     1. Vertex Transformation: Split each vertex v into two vertices v' and v'',
     connected by an edge e from v' to v''. w(e) = w(v).

       v'->v'': index1->(index1+1).

         Edges with ignore attribute set should be treated like they don't
         exist.

     After vertex transformation.

     Redirect edges are not added for edges with ignore attribute.

     2. Initialize D(v).

     Entry block - vertex indices 0, 1; EXIT block - vertex indices 2, 3.

     3. Add reverse edges: needed to decrease counts during smoothing.

             Skip adding reverse edges for edges with w(e) = 0, as its maximum
             capacity is 0.

     4. Create single source and sink. Connect new source vertex s' to function
     entry block. Connect sink vertex t' to function exit.

     Set supply_value to 1 to avoid zero count function ENTRY.

     Create new exit with EXIT_BLOCK as single pred.

     Connect vertices with unbalanced D(v) to source/sink.

     Skip vertices for ENTRY (0, 1) and EXIT (2,3) blocks, so start with i = 4.
     diff_out_in[v''] will be 0, so skip v'' vertices, hence i += 2.

     Set supply = demand.

     6. Normalize edges: remove anti-parallel edges. Anti-parallel edges are
     created by the vertex transformation step from self-edges in the original
     CFG and by the reverse edges added earlier.

             Add a new fixup edge: new_index->src.

             Edge: r_pfedge->src -> r_pfedge->dest
             ==> r_pfedge->src -> new_index.

     Cleanup.

References add_fixup_edge(), edge_def::count, edge_def::dest, basic_block_def::index, fixup_graph_d::num_vertices, REDIRECT_EDGE, and VERTEX_SPLIT_EDGE.

static void delete_fixup_graph ( )

static

   Cleanup routine to free structures in FIXUP_GRAPH.

static int dequeue ( )

static

   Return the first element in QUEUE_LIST.

static void dump_fixup_edge ( )

static

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

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.

             Distinguish forward edges and backward edges in the residual flow
             network.

static void enqueue ( )

static

   Insert element X into QUEUE_LIST.

References fixup_edge_d::cost, fixup_edge_d::dest, and fixup_edge_d::src.

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 fixup_edge_d::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.

Referenced by 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.

     Initialize flow to 0.

         Determine the amount by which we can increment the flow.

         Now increment the flow. EXIT vertex index is 1.

                 forward edge.

                 backward edge.

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

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.

     Holds the index of predecessor in path.

     Used to hold the minimum cost cycle.

     Used to record the number of iterations of cancel_negative_cycle.

     Vector d[i] holds the minimum cost of path from i to sink.

     Initialize the structures for find_negative_cycle().

     Repeatedly find and cancel negative cost cycles, until
     no more negative cycles exist. This also updates the flow field
     to represent the minimum cost flow so far.

     Cleanup structures.

static void free_augmenting_path ( )

static

   Free the structures in AUGMENTING_PATH.

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.

static void init_queue ( )

static

   Queue routines. Assumes queue will never overflow.

static bool is_empty ( )

static

   Return true if QUEUE_LIST is empty.

References fixup_edge_d::src.

Referenced by gt_ggc_mx(), and vnull::operator vec< T, A, L >().

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.

static double mcf_sqrt ( )

static

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

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.

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

Referenced by adjust_cfg_counts(), and find_max_flow().

gcov_type sum_edge_counts ( )

   Compute the sum of the edge counts in TO_EDGES.

Data Structures

Typedefs

Enumerations

Functions

Typedef Documentation

Enumeration Type Documentation

Function Documentation