#include "config.h"#include "system.h"#include "coretypes.h"#include "basic-block.h"#include "gcov-io.h"#include "profile.h"#include "dumpfile.h"
Data Structures | |
| struct | fixup_edge_d |
| struct | fixup_vertex_d |
| struct | fixup_graph_d |
| struct | queue_d |
| struct | augmenting_path_d |
Macros | |
| #define | CAP_INFINITY INTTYPE_MAXIMUM (HOST_WIDEST_INT) |
| #define | K_POS(b) ((b)) |
| #define | K_NEG(b) (50 * (b)) |
| #define | COST(k, w) ((k) / mcf_ln ((w) + 2)) |
| #define | MAX_ITER(n, e) 10 + (1000000 / ((n) * (e))) |
| #define | E 2.71828 |
| #define | MAGIC_CONST1 0x1fbcf800 |
| #define | MAGIC_CONST2 0x5f3759df |
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 () |
Macro Definition Documentation
| #define CAP_INFINITY INTTYPE_MAXIMUM (HOST_WIDEST_INT) |
Routines to implement minimum-cost maximal flow algorithm used to smooth basic block and edge frequency counts. Copyright (C) 2008-2013 Free Software Foundation, Inc. Contributed by Paul Yuan (yingbo.com@gmail.com) and Vinodha Ramasamy (vinodha@google.com).
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/. References: [1] "Feedback-directed Optimizations in GCC with Estimated Edge Profiles from Hardware Event Sampling", Vinodha Ramasamy, Paul Yuan, Dehao Chen, and Robert Hundt; GCC Summit 2008. [2] "Complementing Missing and Inaccurate Profiling Using a Minimum Cost Circulation Algorithm", Roy Levin, Ilan Newman and Gadi Haber; HiPEAC '08.
Algorithm to smooth basic block and edge counts:
- create_fixup_graph: Create fixup graph by translating function CFG into a graph that satisfies MCF algorithm requirements.
- find_max_flow: Find maximal flow.
- compute_residual_flow: Form residual network.
- Repeat: cancel_negative_cycle: 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).
- adjust_cfg_counts: Update initial edge weights with corrected weights. delta(u.v) = f(u,v) -f(v,u). w*(u,v) = w(u,v) + delta(u,v). CAP_INFINITY: Constant to represent infinite capacity.
Referenced by create_fixup_graph(), and init_queue().
| #define COST | ( | k, | |
| w | |||
| ) | ((k) / mcf_ln ((w) + 2)) |
Referenced by create_fixup_graph().
| #define E 2.71828 |
| #define K_NEG | ( | b | ) | (50 * (b)) |
| #define K_POS | ( | b | ) | ((b)) |
COST FUNCTION.
| #define MAGIC_CONST1 0x1fbcf800 |
Referenced by mcf_ln().
| #define MAGIC_CONST2 0x5f3759df |
Referenced by mcf_ln().
| #define MAX_ITER | ( | n, | |
| e | |||
| ) | 10 + (1000000 / ((n) * (e))) |
Limit the number of iterations for cancel_negative_cycles() to ensure reasonable compile time.
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 |
Function Documentation
|
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 |
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 |
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, fixup_graph_d::num_vertices, fixup_vertex_d::succ_edges, and fixup_graph_d::vertex_list.
|
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 |
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 |
Computes the residual flow for FIXUP_GRAPH by setting the rflow field of the edges. ENTRY and EXIT vertices should not be considered.
|
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(), CAP_INFINITY, COST, edge_def::count, edge_def::dest, EDGE_INFO, FOR_EACH_EDGE, basic_block_def::index, fixup_graph_d::num_vertices, REDIRECT_EDGE, and VERTEX_SPLIT_EDGE.
|
static |
Cleanup routine to free structures in FIXUP_GRAPH.
|
static |
Return the first element in QUEUE_LIST.
|
static |
Dump out the attributes of a given edge FEDGE in the fixup_graph to a file.
|
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 |
Insert element X into QUEUE_LIST.
References fixup_edge_d::cost, fixup_edge_d::dest, and fixup_edge_d::src.
|
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 |
Return the pointer to fixup edge SRC->DEST or NULL if edge does not exist in the FIXUP_GRAPH.
References NULL.
Referenced by find_max_flow().
|
static |
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, EDGE_INFO, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, find_fixup_edge(), fixup_edge_d::flow, FOR_BB_BETWEEN, FOR_EACH_EDGE, gcc_assert, HOST_WIDEST_INT_PRINT_DEC, basic_block_def::index, fixup_edge_d::norm_vertex_index, print_edge(), and basic_block_def::succs.
|
static |
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 |
Free the structures in 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 |
Queue routines. Assumes queue will never overflow.
References CAP_INFINITY.
|
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 |
Utility routines. ln() implementation: approximate calculation. Returns ln of X.
References MAGIC_CONST1, and MAGIC_CONST2.
| 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 |
sqrt() implementation: based on open source QUAKE3 code (magic sqrt implementation) by John Carmack. Returns sqrt of X.
|
static |
Function definitions. Dump routines to aid debugging. Print basic block with index N for FIXUP_GRAPH in n' and n'' format.
|
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.
