GCC Middle and Back End API Reference
mcf.c File Reference

Data Structures

struct  fixup_edge_d
struct  fixup_vertex_d
struct  fixup_graph_d
struct  queue_d
struct  augmenting_path_d


typedef struct fixup_edge_d fixup_edge_type
typedef fixup_edge_typefixup_edge_p
typedef struct fixup_vertex_d fixup_vertex_type
typedef fixup_vertex_typefixup_vertex_p
typedef struct fixup_graph_d fixup_graph_type
typedef struct queue_d queue_type
typedef struct augmenting_path_d augmenting_path_type


enum  edge_type {


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

   Structure used in the maximal flow routines to find augmenting path.  
typedef struct fixup_edge_d fixup_edge_type
   Structure to represent an edge in the fixup graph.  
   Fixup graph used in the MCF algorithm.  
   Structure to represent a vertex in the fixup graph.  
typedef struct queue_d queue_type

Enumeration Type Documentation

enum edge_type

Function Documentation

static fixup_edge_p add_edge ( )
   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 
   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 
   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 ( )
   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 

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.

     Skip ENTRY.  
     No negative cycles exist.  
     Augment the cycle with the cycle's minimum residual capacity.  
                 cycle[k] -> ... -> cycle[i].  
static void compute_residual_flow ( )
   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 ( )
   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
     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
     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.  

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 ( )
   Cleanup routine to free structures in FIXUP_GRAPH.  
static int dequeue ( )
   Return the first element in QUEUE_LIST.  
static void dump_fixup_edge ( )
   Dump out the attributes of a given edge FEDGE in the fixup_graph to a
static void dump_fixup_graph ( )
   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
static void enqueue ( )
   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 
   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 ( )
   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 ( )

Routine to find the maximal flow: Algorithm:

  1. Initialize flow to 0
  2. Find an augmenting path form source to sink.
  3. Send flow equal to the path's residual capacity along the edges of this path.
  4. 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 ( )

Implements the negative cycle canceling algorithm to compute a minimum cost flow. Algorithm:

  1. Find maximal flow.
  2. Form residual network
  3. Repeat: While G contains a negative cost cycle C, reverse the flow on the found cycle by the minimum residual capacity in that cycle.
  4. 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 ( )
   Free the structures in AUGMENTING_PATH.  
static void init_augmenting_path ( )
   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
static void init_queue ( )
   Queue routines. Assumes queue will never overflow.  
static bool is_empty ( )
   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 ( )
   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
static double mcf_sqrt ( )
   sqrt() implementation: based on open source QUAKE3 code (magic sqrt
   implementation) by John Carmack.  Returns sqrt of X.  
static void print_basic_block ( )
   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 ( )
   Print edge S->D for given fixup_graph with n' and n'' format.
   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.