#include "config.h"#include "system.h"#include "coretypes.h"#include "backend.h"#include "profile.h"#include "dumpfile.h"
Data Structures | |
| struct | fixup_edge_type |
| struct | fixup_vertex_type |
| struct | fixup_graph_type |
| struct | queue_type |
| struct | augmenting_path_type |
Macros | |
| #define | CAP_INFINITY INTTYPE_MAXIMUM (int64_t) |
| #define | K_POS(b) |
| #define | K_NEG(b) |
| #define | COST(k, w) |
| #define | MAX_ITER(n, e) |
| #define | E 2.71828 |
| #define | MAGIC_CONST1 0x1fbcf800 |
| #define | MAGIC_CONST2 0x5f3759df |
Typedefs | |
| typedef fixup_edge_type * | fixup_edge_p |
| typedef fixup_vertex_type * | fixup_vertex_p |
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 (FILE *file, fixup_graph_type *fixup_graph, int n) |
| static void | print_edge (FILE *file, fixup_graph_type *fixup_graph, int s, int d) |
| static void | dump_fixup_edge (FILE *file, fixup_graph_type *fixup_graph, fixup_edge_p fedge) |
| static void | dump_fixup_graph (FILE *file, fixup_graph_type *fixup_graph, const char *msg) |
| static double | mcf_ln (double x) |
| static double | mcf_sqrt (double x) |
| static fixup_edge_p | add_edge (fixup_graph_type *fixup_graph, int src, int dest, gcov_type cost) |
| 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 (fixup_graph_type *fixup_graph, int src, int dest) |
| static void | delete_fixup_graph (fixup_graph_type *fixup_graph) |
| static void | create_fixup_graph (fixup_graph_type *fixup_graph) |
| static void | init_augmenting_path (augmenting_path_type *augmenting_path, int graph_size) |
| static void | free_augmenting_path (augmenting_path_type *augmenting_path) |
| static void | init_queue (queue_type *queue_list) |
| static bool | is_empty (queue_type *queue_list) |
| static void | enqueue (queue_type *queue_list, int x) |
| static int | dequeue (queue_type *queue_list) |
| static bool | cancel_negative_cycle (fixup_graph_type *fixup_graph, int *pi, gcov_type *d, int *cycle) |
| static void | compute_residual_flow (fixup_graph_type *fixup_graph) |
| 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 (fixup_graph_type *fixup_graph, int source, int sink) |
| static void | adjust_cfg_counts (fixup_graph_type *fixup_graph) |
| static void | find_minimum_cost_flow (fixup_graph_type *fixup_graph) |
| gcov_type | sum_edge_counts (vec< edge, va_gc > *to_edges) |
| void | mcf_smooth_cfg (void) |
Macro Definition Documentation
◆ CAP_INFINITY
| #define CAP_INFINITY INTTYPE_MAXIMUM (int64_t) |
Routines to implement minimum-cost maximal flow algorithm used to smooth
basic block and edge frequency counts.
Copyright (C) 2008-2025 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:
1. create_fixup_graph: Create fixup graph by translating function CFG into
a graph that satisfies MCF algorithm requirements.
2. find_max_flow: Find maximal flow.
3. compute_residual_flow: Form residual network.
4. 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.
5. Form the minimal cost flow
f(u,v) = rf(v, u).
6. 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 cancel_negative_cycle(), create_fixup_graph(), dump_fixup_edge(), and find_max_flow().
◆ COST
| #define COST | ( | k, | |
| w ) |
◆ E
| #define E 2.71828 |
Referenced by mcf_ln().
◆ K_NEG
| #define K_NEG | ( | b | ) |
Referenced by create_fixup_graph().
◆ K_POS
| #define K_POS | ( | b | ) |
◆ MAGIC_CONST1
| #define MAGIC_CONST1 0x1fbcf800 |
Referenced by mcf_sqrt().
◆ MAGIC_CONST2
| #define MAGIC_CONST2 0x5f3759df |
Referenced by mcf_sqrt().
◆ MAX_ITER
| #define MAX_ITER | ( | n, | |
| e ) |
Limit the number of iterations for cancel_negative_cycles() to ensure reasonable compile time.
Referenced by find_minimum_cost_flow().
Typedef Documentation
◆ fixup_edge_p
| typedef fixup_edge_type* fixup_edge_p |
◆ fixup_vertex_p
| typedef fixup_vertex_type* fixup_vertex_p |
Enumeration Type Documentation
◆ edge_type
| enum edge_type |
Function Documentation
◆ 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_type::cost, fixup_edge_type::dest, dump_file, dump_fixup_edge(), fixup_graph_type::edge_list, fixup_graph_type::num_edges, fixup_edge_type::src, fixup_vertex_type::succ_edges, and fixup_graph_type::vertex_list.
Referenced by add_fixup_edge(), and add_rfixup_edge().
◆ add_fixup_edge()
|
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_type::max_capacity, fixup_edge_type::type, and fixup_edge_type::weight.
Referenced by create_fixup_graph().
◆ add_rfixup_edge()
|
static |
Add a residual edge (SRC->DEST) with attributes RFLOW and COST to the fixup graph.
References add_edge(), INVALID_EDGE, fixup_edge_type::is_rflow_valid, fixup_edge_type::rflow, and fixup_edge_type::type.
Referenced by compute_residual_flow().
◆ adjust_cfg_counts()
|
static |
Computes the corrected edge and basic block weights using FIXUP_GRAPH after applying the find_minimum_cost_flow() routine.
References bb_gcov_count(), cfun, current_function_name(), dump_file, edge_gcov_count(), EDGE_INFO, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK_PTR_FOR_FN, find_fixup_edge(), fixup_edge_type::flow, FOR_ALL_BB_FN, FOR_BB_BETWEEN, FOR_EACH_BB_FN, FOR_EACH_EDGE, gcc_assert, i, basic_block_def::index, fixup_edge_type::norm_vertex_index, basic_block_def::preds, PRId64, print_edge(), profile_probability::probability_in_gcov_type(), basic_block_def::succs, and sum_edge_counts().
Referenced by mcf_smooth_cfg().
◆ cancel_negative_cycle()
|
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.
References CAP_INFINITY, fixup_edge_type::cost, fixup_edge_type::dest, dump_file, fixup_graph_type::edge_list, ENTRY_BLOCK, find_fixup_edge(), fixup_edge_type::flow, gcc_assert, i, fixup_edge_type::is_rflow_valid, MIN, fixup_graph_type::new_entry_index, fixup_graph_type::num_edges, fixup_graph_type::num_vertices, PRId64, fixup_edge_type::rflow, fixup_edge_type::src, and fixup_edge_type::type.
Referenced by find_minimum_cost_flow().
◆ 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_type::cost, fixup_edge_type::dest, dump_file, fixup_graph_type::edge_list, fixup_edge_type::flow, gcc_assert, i, fixup_edge_type::is_rflow_valid, fixup_edge_type::max_capacity, fixup_graph_type::num_edges, fixup_edge_type::rflow, and fixup_edge_type::src.
Referenced by find_max_flow().
◆ create_fixup_graph()
|
static |
Creates a fixup graph FIXUP_GRAPH from the function CFG.
References add_fixup_edge(), BALANCE_EDGE, bb_gcov_count(), CAP_INFINITY, cfun, COST, fixup_edge_type::cost, fixup_edge_type::dest, dump_file, dump_fixup_edge(), dump_fixup_graph(), edge_gcov_count(), EDGE_INFO, fixup_graph_type::edge_list, ENTRY_BLOCK, ENTRY_BLOCK_PTR_FOR_FN, EXIT_BLOCK, find_fixup_edge(), FOR_BB_BETWEEN, FOR_EACH_EDGE, free(), gcc_assert, i, basic_block_def::index, K_NEG, K_POS, fixup_edge_type::max_capacity, mcf_sqrt(), n_basic_blocks_for_fn, n_edges_for_fn, fixup_graph_type::new_entry_index, fixup_graph_type::new_exit_index, fixup_edge_type::norm_vertex_index, NULL, fixup_graph_type::num_edges, fixup_graph_type::num_vertices, PRId64, REDIRECT_EDGE, REVERSE_EDGE, REVERSE_NORMALIZED_EDGE, SINK_CONNECT_EDGE, SOURCE_CONNECT_EDGE, fixup_edge_type::src, basic_block_def::succs, fixup_edge_type::type, fixup_graph_type::vertex_list, VERTEX_SPLIT_EDGE, and fixup_edge_type::weight.
Referenced by mcf_smooth_cfg().
◆ delete_fixup_graph()
|
static |
Cleanup routine to free structures in FIXUP_GRAPH.
References fixup_graph_type::edge_list, free(), i, fixup_graph_type::num_vertices, fixup_vertex_type::succ_edges, and fixup_graph_type::vertex_list.
Referenced by mcf_smooth_cfg().
◆ dequeue()
|
static |
Return the first element in QUEUE_LIST.
References gcc_assert, queue_type::head, and queue_type::queue.
Referenced by find_augmenting_path().
◆ dump_fixup_edge()
|
static |
Dump out the attributes of a given edge FEDGE in the fixup_graph to a file.
References BALANCE_EDGE, CAP_INFINITY, fixup_edge_type::cost, fixup_edge_type::dest, fixup_edge_type::flow, fixup_edge_type::is_rflow_valid, fixup_edge_type::max_capacity, PRId64, print_edge(), REDIRECT_EDGE, REDIRECT_NORMALIZED_EDGE, REVERSE_EDGE, REVERSE_NORMALIZED_EDGE, fixup_edge_type::rflow, SINK_CONNECT_EDGE, SOURCE_CONNECT_EDGE, fixup_edge_type::src, fixup_edge_type::type, and VERTEX_SPLIT_EDGE.
Referenced by add_edge(), create_fixup_graph(), and dump_fixup_graph().
◆ 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(), gcc_assert, i, fixup_edge_type::is_rflow_valid, msg, fixup_graph_type::new_exit_index, fixup_graph_type::num_edges, fixup_graph_type::num_vertices, fixup_vertex_type::succ_edges, fixup_edge_type::type, and fixup_graph_type::vertex_list.
Referenced by create_fixup_graph(), find_max_flow(), and find_minimum_cost_flow().
◆ enqueue()
|
static |
Insert element X into QUEUE_LIST.
References gcc_assert, queue_type::queue, queue_type::size, and queue_type::tail.
Referenced by find_augmenting_path().
◆ find_augmenting_path()
|
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_type::bb_pred, dequeue(), fixup_edge_type::dest, enqueue(), gcc_assert, i, init_queue(), is_empty(), augmenting_path_type::is_visited, fixup_graph_type::num_vertices, augmenting_path_type::queue_list, fixup_edge_type::rflow, fixup_vertex_type::succ_edges, and fixup_graph_type::vertex_list.
Referenced by find_max_flow().
◆ 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_type::dest, gcc_assert, NULL, fixup_vertex_type::succ_edges, and fixup_graph_type::vertex_list.
Referenced by adjust_cfg_counts(), cancel_negative_cycle(), create_fixup_graph(), and find_max_flow().
◆ find_max_flow()
|
static |
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.
References augmenting_path_type::bb_pred, CAP_INFINITY, compute_residual_flow(), dump_file, dump_fixup_graph(), fixup_graph_type::edge_list, find_augmenting_path(), find_fixup_edge(), fixup_edge_type::flow, free_augmenting_path(), gcc_assert, i, init_augmenting_path(), MIN, fixup_graph_type::num_edges, fixup_graph_type::num_vertices, PRId64, print_basic_block(), fixup_edge_type::rflow, and fixup_edge_type::type.
Referenced by find_minimum_cost_flow().
◆ find_minimum_cost_flow()
|
static |
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.
References cancel_negative_cycle(), dump_file, dump_fixup_graph(), find_max_flow(), free(), gcc_assert, MAX_ITER, fixup_graph_type::new_entry_index, fixup_graph_type::new_exit_index, fixup_graph_type::num_edges, and fixup_graph_type::num_vertices.
Referenced by mcf_smooth_cfg().
◆ free_augmenting_path()
|
static |
Free the structures in AUGMENTING_PATH.
References augmenting_path_type::bb_pred, free(), augmenting_path_type::is_visited, queue_type::queue, and augmenting_path_type::queue_list.
Referenced by find_max_flow().
◆ 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_type::bb_pred, augmenting_path_type::is_visited, queue_type::queue, augmenting_path_type::queue_list, and queue_type::size.
Referenced by find_max_flow().
◆ init_queue()
|
static |
Queue routines. Assumes queue will never overflow.
References gcc_assert, queue_type::head, and queue_type::tail.
Referenced by find_augmenting_path().
◆ is_empty()
|
static |
Return true if QUEUE_LIST is empty.
References queue_type::head, and queue_type::tail.
Referenced by allocate_phi_node(), dbg_cnt(), evaluate_bbs(), find_augmenting_path(), vect_optimize_slp_pass::get_result_with_layout(), loc_exp_dep_alloc(), loc_exp_dep_clear(), loc_exp_dep_set(), move_early_exit_stmts(), tree_loop_unroll_and_jam(), vect_analyze_early_break_dependences(), vect_analyze_loop_2(), vect_bb_vectorization_profitable_p(), vect_cse_slp_nodes(), vect_enhance_data_refs_alignment(), vect_lower_load_permutations(), vect_print_slp_tree(), vect_prologue_cost_for_slp(), vect_schedule_slp(), vect_schedule_slp_node(), vect_slp_analyze_node_operations(), vect_slp_analyze_operations(), vect_slp_tree_uniform_p(), vect_verify_full_masking(), vect_verify_full_masking_avx512(), vect_verify_loop_lens(), vectorizable_phi(), vectorizable_slp_permutation_1(), and vectorize_slp_instance_root_stmt().
◆ mcf_ln()
|
static |
Utility routines.
ln() implementation: approximate calculation. Returns ln of X.
References E, and gcc_assert.
◆ mcf_smooth_cfg()
| 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(), and find_minimum_cost_flow().
Referenced by compute_branch_probabilities().
◆ mcf_sqrt()
|
static |
sqrt() implementation: based on open source QUAKE3 code (magic sqrt implementation) by John Carmack. Returns sqrt of X.
References gcc_assert, MAGIC_CONST1, and MAGIC_CONST2.
Referenced by create_fixup_graph().
◆ 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 ENTRY_BLOCK, EXIT_BLOCK, fixup_graph_type::new_entry_index, and fixup_graph_type::new_exit_index.
Referenced by find_max_flow(), and print_edge().
◆ 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(), vect_optimize_slp_pass::dump(), and dump_fixup_edge().
◆ sum_edge_counts()
Compute the sum of the edge counts in TO_EDGES.
References edge_gcov_count(), EDGE_INFO, and FOR_EACH_EDGE.
Referenced by adjust_cfg_counts(), is_inconsistent(), and set_bb_counts().
