mcf.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "profile.h"
#include "dumpfile.h"

Include dependency graph for mcf.cc:

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

Value:

((k) / mcf_ln ((w) + 2))

Referenced by create_fixup_graph().

E

#define E   2.71828

Referenced by mcf_ln().

K_NEG

#define K_NEG

(

b

)

Value:

(50 * (b))

Referenced by create_fixup_graph().

K_POS

#define K_POS

(

b

)

Value:

((b))

COST FUNCTION.   

Referenced by create_fixup_graph().

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 )

Value:

10 + (1000000 / ((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

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

add_edge()

static fixup_edge_p add_edge ( fixup_graph_type * fixup_graph, int src, int dest, gcov_type cost )

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 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_type::max_capacity, fixup_edge_type::type, type(), and fixup_edge_type::weight.

Referenced by create_fixup_graph().

add_rfixup_edge()

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_type::is_rflow_valid, fixup_edge_type::rflow, and fixup_edge_type::type.

Referenced by compute_residual_flow().

adjust_cfg_counts()

static void adjust_cfg_counts ( fixup_graph_type * fixup_graph )

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 bool cancel_negative_cycle ( fixup_graph_type * fixup_graph, int * pi, gcov_type * d, int * 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 void compute_residual_flow ( fixup_graph_type * fixup_graph )

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 void create_fixup_graph ( fixup_graph_type * 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 void delete_fixup_graph ( fixup_graph_type * 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 int dequeue ( queue_type * queue_list )

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 void dump_fixup_edge ( FILE * file, fixup_graph_type * fixup_graph, fixup_edge_p fedge )

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 void dump_fixup_graph ( FILE * file, fixup_graph_type * fixup_graph, const char * msg )

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 void enqueue ( queue_type * queue_list, int x )

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 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_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 fixup_edge_p find_fixup_edge ( fixup_graph_type * fixup_graph, int src, int dest )

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 gcov_type find_max_flow ( fixup_graph_type * fixup_graph, int source, int sink )

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 void find_minimum_cost_flow ( fixup_graph_type * fixup_graph )

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 void free_augmenting_path ( augmenting_path_type * 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 void init_augmenting_path ( augmenting_path_type * augmenting_path, int graph_size )

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 void init_queue ( queue_type * queue_list )

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 bool is_empty ( queue_type * queue_list )

static

Return true if QUEUE_LIST is empty.   

References queue_type::head, and queue_type::tail.

Referenced by allocate_phi_node(), hash_table< Descriptor, Lazy, Allocator >::clear_slot(), dbg_cnt(), hash_table< Descriptor, Lazy, Allocator >::empty_slow(), evaluate_bbs(), hash_table< Descriptor, Lazy, Allocator >::expand(), find_augmenting_path(), hash_table< Descriptor, Lazy, Allocator >::find_empty_slot_for_expand(), hash_table< Descriptor, Lazy, Allocator >::find_slot_with_hash(), hash_table< Descriptor, Lazy, Allocator >::find_with_hash(), vect_optimize_slp_pass::get_result_with_layout(), predicate::init_from_control_deps(), loc_exp_dep_alloc(), loc_exp_dep_clear(), loc_exp_dep_set(), move_early_exit_stmts(), predicate::simplify_4(), hash_table< Descriptor, Lazy, Allocator >::traverse_noresize(), 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(), vectorize_slp_instance_root_stmt(), hash_table< Descriptor, Lazy, Allocator >::verify(), and hash_table< Descriptor, Lazy, Allocator >::~hash_table().

mcf_ln()

static double mcf_ln ( double x )

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 double mcf_sqrt ( double x )

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 void print_basic_block ( FILE * file, fixup_graph_type * fixup_graph, int n )

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 void print_edge ( FILE * file, fixup_graph_type * fixup_graph, int s, int d )

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

gcov_type sum_edge_counts

(

vec< edge, va_gc > *

to_edges

)

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