/* Compile this one with gcc. */
/* Copyright (C) 2009. Free Software Foundation, Inc.
Contributed by Xinliang David Li (davidxl@google.com) and
Raksit Ashok (raksit@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.
Under Section 7 of GPL version 3, you are granted additional
permissions described in the GCC Runtime Library Exception, version
3.1, as published by the Free Software Foundation.
You should have received a copy of the GNU General Public License and
a copy of the GCC Runtime Library Exception along with this program;
see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
. */
#include "tconfig.h"
#include "tsystem.h"
#include "coretypes.h"
#include "tm.h"
#if defined(inhibit_libc)
#define IN_LIBGCOV (-1)
#else
#undef NULL /* Avoid errors if stdio.h and our stddef.h mismatch. */
#include
#include
#define IN_LIBGCOV 1
#if defined(L_gcov)
#define GCOV_LINKAGE /* nothing */
#endif
#endif
#include "gcov-io.h"
struct dyn_pointer_set;
#define XNEWVEC(type,ne) (type *)malloc(sizeof(type) * (ne))
#define XNEW(type) (type *)malloc(sizeof(type))
#define XDELETEVEC(p) free(p)
#define XDELETE(p) free(p)
struct dyn_cgraph_node
{
struct dyn_cgraph_edge *callees;
struct dyn_cgraph_edge *callers;
struct dyn_pointer_set *imported_modules;
gcov_type guid;
gcov_type sum_in_count;
gcov_unsigned_t visited;
};
struct dyn_cgraph_edge
{
struct dyn_cgraph_node *caller;
struct dyn_cgraph_node *callee;
struct dyn_cgraph_edge *next_caller;
struct dyn_cgraph_edge *next_callee;
gcov_type count;
};
struct dyn_module_info
{
struct dyn_pointer_set *imported_modules;
gcov_unsigned_t max_func_ident;
};
struct dyn_cgraph
{
struct dyn_pointer_set **call_graph_nodes;
struct gcov_info **modules;
/* supplement module information */
struct dyn_module_info *sup_modules;
const struct gcov_fn_info ***functions;
unsigned num_modules;
unsigned num_nodes_executed;
};
struct dyn_pointer_set
{
size_t log_slots;
size_t n_slots; /* n_slots = 2^log_slots */
size_t n_elements;
void **slots;
unsigned (*get_key) (const void *);
};
#if defined(inhibit_libc)
__gcov_build_callgraph (void) {}
#else
void __gcov_compute_module_groups (void) ATTRIBUTE_HIDDEN;
void __gcov_finalize_dyn_callgraph (void) ATTRIBUTE_HIDDEN;
static void gcov_dump_callgraph (gcov_type);
static void gcov_dump_cgraph_node_short (struct dyn_cgraph_node *node);
static void gcov_dump_cgraph_node (struct dyn_cgraph_node *node,
unsigned m, unsigned f);
static void
gcov_dump_cgraph_node_dot (struct dyn_cgraph_node *node,
unsigned m, unsigned f,
gcov_type cutoff_count);
static void
pointer_set_destroy (struct dyn_pointer_set *pset);
static void **
pointer_set_find_or_insert (struct dyn_pointer_set *pset, unsigned key);
static struct dyn_pointer_set *
pointer_set_create (unsigned (*get_key) (const void *));
static struct dyn_cgraph the_dyn_call_graph;
static int total_zero_count = 0;
static int total_insane_count = 0;
static void
init_dyn_cgraph_node (struct dyn_cgraph_node *node, gcov_type guid)
{
node->callees = 0;
node->callers = 0;
node->imported_modules = 0;
node->guid = guid;
node->visited = 0;
}
/* Return (module_id - 1). FUNC_GUID is the global unique id. */
static inline gcov_unsigned_t
get_module_idx_from_func_glob_uid (gcov_type func_guid)
{
return EXTRACT_MODULE_ID_FROM_GLOBAL_ID (func_guid) - 1;
}
/* Return (module_id - 1) for MODULE_INFO. */
static inline gcov_unsigned_t
get_module_idx (const struct gcov_info *module_info)
{
return module_info->mod_info->ident - 1;
}
/* Return intra-module function id given function global unique id
FUNC_GUID. */
static inline gcov_unsigned_t
get_intra_module_func_id (gcov_type func_guid)
{
return EXTRACT_FUNC_ID_FROM_GLOBAL_ID (func_guid);
}
/* Return the pointer to the dynamic call graph node for FUNC_GUID. */
static inline struct dyn_cgraph_node *
get_cgraph_node (gcov_type func_guid)
{
gcov_unsigned_t mod_id, func_id;
mod_id = get_module_idx_from_func_glob_uid (func_guid);
/* This is to workaround: calls in __static_initialization_and_destruction
should not be instrumented as the module id context for the callees have
not setup yet -- this leads to mod_id == (unsigned) (0 - 1). Multithreaded
programs may also produce insane func_guid in the profile counter. */
if (mod_id >= the_dyn_call_graph.num_modules)
return 0;
func_id = get_intra_module_func_id (func_guid);
if (func_id > the_dyn_call_graph.sup_modules[mod_id].max_func_ident)
return 0;
return *(pointer_set_find_or_insert
(the_dyn_call_graph.call_graph_nodes[mod_id], func_id));
}
/* Return the gcov_info pointer for module with id MODULE_ID. */
static inline struct gcov_info *
get_module_info (gcov_unsigned_t module_id)
{
return the_dyn_call_graph.modules[module_id];
}
struct gcov_info *__gcov_list ATTRIBUTE_HIDDEN;
static inline unsigned
cgraph_node_get_key (const void *p)
{
return get_intra_module_func_id (((const struct dyn_cgraph_node *) p)->guid);
}
/* Initialize dynamic call graph. */
static void
init_dyn_call_graph (void)
{
unsigned num_modules = 0;
struct gcov_info *gi_ptr;
the_dyn_call_graph.call_graph_nodes = 0;
the_dyn_call_graph.modules = 0;
the_dyn_call_graph.functions = 0;
the_dyn_call_graph.num_nodes_executed = 0;
gi_ptr = __gcov_list;
for (; gi_ptr; gi_ptr = gi_ptr->next)
num_modules++;
the_dyn_call_graph.num_modules = num_modules;
the_dyn_call_graph.modules
= XNEWVEC (struct gcov_info *, num_modules);
the_dyn_call_graph.sup_modules
= XNEWVEC (struct dyn_module_info, num_modules);
memset (the_dyn_call_graph.sup_modules, 0,
num_modules * sizeof (struct dyn_module_info));
the_dyn_call_graph.functions
= XNEWVEC (const struct gcov_fn_info **, num_modules);
the_dyn_call_graph.call_graph_nodes
= XNEWVEC (struct dyn_pointer_set *, num_modules);
gi_ptr = __gcov_list;
for (; gi_ptr; gi_ptr = gi_ptr->next)
{
unsigned c_ix = 0, t_ix, j, mod_id, fi_stride, max_func_ident = 0;
struct dyn_cgraph_node *node;
mod_id = get_module_idx (gi_ptr);
the_dyn_call_graph.modules[mod_id] = gi_ptr;
the_dyn_call_graph.functions[mod_id]
= XNEWVEC (const struct gcov_fn_info *, gi_ptr->n_functions);
for (t_ix = 0; t_ix < GCOV_COUNTERS; t_ix++)
if ((1 << t_ix) & gi_ptr->ctr_mask)
c_ix++;
fi_stride = offsetof (struct gcov_fn_info, n_ctrs) + c_ix * sizeof (unsigned);
if (__alignof__ (struct gcov_fn_info) > sizeof (unsigned))
{
fi_stride += __alignof__ (struct gcov_fn_info) - 1;
fi_stride &= ~(__alignof__ (struct gcov_fn_info) - 1);
}
for (j = 0; j < gi_ptr->n_functions; j++)
{
const struct gcov_fn_info *fi_ptr = (const struct gcov_fn_info *)
((const char *) gi_ptr->functions + j * fi_stride);
the_dyn_call_graph.functions[mod_id][j] = fi_ptr;
if (fi_ptr->ident > max_func_ident)
max_func_ident = fi_ptr->ident;
}
the_dyn_call_graph.call_graph_nodes[mod_id]
= pointer_set_create (cgraph_node_get_key);
the_dyn_call_graph.sup_modules[mod_id].max_func_ident = max_func_ident;
for (j = 0; j < gi_ptr->n_functions; j++)
{
const struct gcov_fn_info *fi_ptr
= the_dyn_call_graph.functions[mod_id][j];
*(pointer_set_find_or_insert
(the_dyn_call_graph.call_graph_nodes[mod_id], fi_ptr->ident))
= node = XNEW (struct dyn_cgraph_node);
the_dyn_call_graph.call_graph_nodes[mod_id]->n_elements++;
init_dyn_cgraph_node (node, GEN_FUNC_GLOBAL_ID (gi_ptr->mod_info->ident,
fi_ptr->ident));
}
}
}
/* Free up memory allocated for dynamic call graph. */
void
__gcov_finalize_dyn_callgraph (void)
{
unsigned i;
struct gcov_info *gi_ptr;
for (i = 0; i < the_dyn_call_graph.num_modules; i++)
{
gi_ptr = the_dyn_call_graph.modules[i];
const struct gcov_fn_info *fi_ptr;
unsigned f_ix;
for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++)
{
struct dyn_cgraph_node *node;
struct dyn_cgraph_edge *callees, *next_callee;
fi_ptr = the_dyn_call_graph.functions[i][f_ix];
node = *(pointer_set_find_or_insert
(the_dyn_call_graph.call_graph_nodes[i], fi_ptr->ident));
gcc_assert (node);
callees = node->callees;
if (!callees)
continue;
while (callees != 0)
{
next_callee = callees->next_callee;
XDELETE (callees);
callees = next_callee;
}
if (node->imported_modules)
pointer_set_destroy (node->imported_modules);
}
if (the_dyn_call_graph.call_graph_nodes[i])
pointer_set_destroy (the_dyn_call_graph.call_graph_nodes[i]);
if (the_dyn_call_graph.functions[i])
XDELETEVEC (the_dyn_call_graph.functions[i]);
/* Now delete sup modules */
if (the_dyn_call_graph.sup_modules[i].imported_modules)
pointer_set_destroy (the_dyn_call_graph.sup_modules[i].imported_modules);
}
XDELETEVEC (the_dyn_call_graph.call_graph_nodes);
XDELETEVEC (the_dyn_call_graph.functions);
XDELETEVEC (the_dyn_call_graph.sup_modules);
XDELETEVEC (the_dyn_call_graph.modules);
}
/* Add outgoing edge OUT_EDGE for caller node CALLER. */
static void
gcov_add_out_edge (struct dyn_cgraph_node *caller,
struct dyn_cgraph_edge *out_edge)
{
if (!caller->callees)
caller->callees = out_edge;
else
{
out_edge->next_callee = caller->callees;
caller->callees = out_edge;
}
}
/* Add incoming edge IN_EDGE for callee node CALLEE. */
static void
gcov_add_in_edge (struct dyn_cgraph_node *callee,
struct dyn_cgraph_edge *in_edge)
{
if (!callee->callers)
callee->callers = in_edge;
else
{
in_edge->next_caller = callee->callers;
callee->callers = in_edge;
}
}
/* Add a call graph edge between caller CALLER and callee CALLEE.
The edge count is COUNT. */
static void
gcov_add_cgraph_edge (struct dyn_cgraph_node *caller,
struct dyn_cgraph_node *callee,
gcov_type count)
{
struct dyn_cgraph_edge *new_edge = XNEW (struct dyn_cgraph_edge);
new_edge->caller = caller;
new_edge->callee = callee;
new_edge->count = count;
new_edge->next_caller = 0;
new_edge->next_callee = 0;
gcov_add_out_edge (caller, new_edge);
gcov_add_in_edge (callee, new_edge);
}
/* Add call graph edges from direct calls for caller CALLER. DIR_CALL_COUNTERS
is the array of call counters. N_COUNTS is the number of counters. */
static void
gcov_build_callgraph_dc_fn (struct dyn_cgraph_node *caller,
gcov_type *dir_call_counters,
unsigned n_counts)
{
unsigned i;
for (i = 0; i < n_counts; i += 2)
{
struct dyn_cgraph_node *callee;
gcov_type count;
gcov_type callee_guid = dir_call_counters[i];
count = dir_call_counters[i + 1];
if (count == 0)
{
total_zero_count++;
continue;
}
callee = get_cgraph_node (callee_guid);
if (!callee)
{
total_insane_count++;
continue;
}
gcov_add_cgraph_edge (caller, callee, count);
}
}
/* Add call graph edges from indirect calls for caller CALLER. ICALL_COUNTERS
is the array of icall counters. N_COUNTS is the number of counters. */
static void
gcov_build_callgraph_ic_fn (struct dyn_cgraph_node *caller,
gcov_type *icall_counters,
unsigned n_counts)
{
unsigned i, j;
for (i = 0; i < n_counts; i += GCOV_ICALL_TOPN_NCOUNTS)
{
gcov_type *value_array = &icall_counters[i + 1];
for (j = 0; j < GCOV_ICALL_TOPN_NCOUNTS - 1; j += 2)
{
struct dyn_cgraph_node *callee;
gcov_type count;
gcov_type callee_guid = value_array[j];
count = value_array[j + 1];
/* Do not update zero count edge count
* as it means there is no target in this entry. */
if (count == 0)
continue;
callee = get_cgraph_node (callee_guid);
if (!callee)
{
total_insane_count++;
continue;
}
gcov_add_cgraph_edge (caller, callee, count);
}
}
}
/* Build the dynamic call graph. */
static void
gcov_build_callgraph (void)
{
struct gcov_info *gi_ptr;
unsigned t_ix, m_ix;
init_dyn_call_graph ();
for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++)
{
const struct gcov_fn_info *fi_ptr;
unsigned c_ix, f_ix, n_counts, dp_cix = 0, ip_cix = 0;
gcov_type *dcall_profile_values, *icall_profile_values;
gcov_type *arcs_values = 0; unsigned arcs_cix;
gi_ptr = the_dyn_call_graph.modules[m_ix];
dcall_profile_values = 0;
icall_profile_values = 0;
c_ix = 0;
for (t_ix = 0; t_ix < GCOV_COUNTERS; t_ix++)
if ((1 << t_ix) & gi_ptr->ctr_mask)
{
if (t_ix == GCOV_COUNTER_DIRECT_CALL)
{
dcall_profile_values = gi_ptr->counts[c_ix].values;
dp_cix = c_ix;
}
if (t_ix == GCOV_COUNTER_ICALL_TOPNV)
{
icall_profile_values = gi_ptr->counts[c_ix].values;
ip_cix = c_ix;
}
if (t_ix == GCOV_COUNTER_ARCS)
{
arcs_values = gi_ptr->counts[c_ix].values;
arcs_cix = c_ix;
}
c_ix++;
}
if (dcall_profile_values == 0 && icall_profile_values == 0)
continue;
for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++)
{
struct dyn_cgraph_node *caller;
fi_ptr = the_dyn_call_graph.functions[m_ix][f_ix];
caller = *(pointer_set_find_or_insert
(the_dyn_call_graph.call_graph_nodes[m_ix],
fi_ptr->ident));
gcc_assert (caller);
if (dcall_profile_values)
{
unsigned offset;
n_counts = fi_ptr->n_ctrs[dp_cix];
offset = fi_ptr->dc_offset;
gcov_build_callgraph_dc_fn (caller,
dcall_profile_values + offset,
n_counts);
}
if (icall_profile_values)
{
n_counts = fi_ptr->n_ctrs[ip_cix];
gcov_build_callgraph_ic_fn (caller, icall_profile_values, n_counts);
icall_profile_values += n_counts;
}
if (arcs_values && 0)
{
gcov_type total_arc_count = 0;
unsigned arc;
n_counts = fi_ptr->n_ctrs[arcs_cix];
for (arc = 0; arc < n_counts; arc++)
total_arc_count += arcs_values[arc];
if (total_arc_count != 0)
the_dyn_call_graph.num_nodes_executed++;
arcs_values += n_counts;
}
}
}
}
static inline size_t
hash1 (unsigned p, unsigned long max, unsigned long logmax)
{
const unsigned long long A = 0x9e3779b97f4a7c16ull;
const unsigned long long shift = 64 - logmax;
return ((A * (unsigned long) p) >> shift) & (max - 1);
}
/* Allocate an empty imported-modules set. */
static struct dyn_pointer_set *
pointer_set_create (unsigned (*get_key) (const void *))
{
struct dyn_pointer_set *result = XNEW (struct dyn_pointer_set);
result->n_elements = 0;
result->log_slots = 8;
result->n_slots = (size_t) 1 << result->log_slots;
result->slots = XNEWVEC (void *, result->n_slots);
memset (result->slots, 0, sizeof (void *) * result->n_slots);
result->get_key = get_key;
return result;
}
/* Reclaim all memory associated with PSET. */
static void
pointer_set_destroy (struct dyn_pointer_set *pset)
{
size_t i;
for (i = 0; i < pset->n_slots; i++)
if (pset->slots[i])
XDELETE (pset->slots[i]);
XDELETEVEC (pset->slots);
XDELETE (pset);
}
/* Subroutine of pointer_set_find_or_insert. Return the insertion slot for KEY
into an empty element of SLOTS, an array of length N_SLOTS. */
static inline size_t
insert_aux (unsigned key, void **slots,
size_t n_slots, size_t log_slots,
unsigned (*get_key) (const void *))
{
size_t n = hash1 (key, n_slots, log_slots);
while (1)
{
if (slots[n] == 0 || get_key (slots[n]) == key)
return n;
else
{
++n;
if (n == n_slots)
n = 0;
}
}
}
/* Find slot for KEY. KEY must be nonnull. */
static void **
pointer_set_find_or_insert (struct dyn_pointer_set *pset, unsigned key)
{
size_t n;
/* For simplicity, expand the set even if KEY is already there. This can be
superfluous but can happen at most once. */
if (pset->n_elements > pset->n_slots / 4)
{
size_t new_log_slots = pset->log_slots + 1;
size_t new_n_slots = pset->n_slots * 2;
void **new_slots = XNEWVEC (void *, new_n_slots);
memset (new_slots, 0, sizeof (void *) * new_n_slots);
size_t i;
for (i = 0; i < pset->n_slots; ++i)
{
void *value = pset->slots[i];
if (!value)
continue;
n = insert_aux (pset->get_key (value), new_slots, new_n_slots,
new_log_slots, pset->get_key);
new_slots[n] = value;
}
XDELETEVEC (pset->slots);
pset->n_slots = new_n_slots;
pset->log_slots = new_log_slots;
pset->slots = new_slots;
}
n = insert_aux (key, pset->slots, pset->n_slots, pset->log_slots,
pset->get_key);
return &pset->slots[n];
}
/* Pass each pointer in PSET to the function in FN, together with the fixed
parameters DATA1, DATA2, DATA3. If FN returns false, the iteration stops. */
static void
pointer_set_traverse (const struct dyn_pointer_set *pset,
int (*fn) (const void *, void *, void *, void *),
void *data1, void *data2, void *data3)
{
size_t i;
for (i = 0; i < pset->n_slots; ++i)
if (pset->slots[i] && !fn (pset->slots[i], data1, data2, data3))
break;
}
static int
imp_mod_set_insert (struct dyn_pointer_set *p, const struct gcov_info *imp_mod,
double wt)
{
struct dyn_imp_mod **m = (struct dyn_imp_mod **)
pointer_set_find_or_insert (p, imp_mod->mod_info->ident);
if (*m)
{
(*m)->weight += wt;
return 1;
}
else
{
*m = XNEW (struct dyn_imp_mod);
(*m)->imp_mod = imp_mod;
(*m)->weight = wt;
p->n_elements++;
return 0;
}
}
/* Callback function to propagate import module (VALUE) from callee to
caller's imported-module-set (DATA1).
The weight is scaled by the scaling-factor (DATA2) before propagation,
and accumulated into DATA3. */
static int
gcov_propagate_imp_modules (const void *value, void *data1, void *data2,
void *data3)
{
const struct dyn_imp_mod *m = (const struct dyn_imp_mod *) value;
struct dyn_pointer_set *receiving_set = (struct dyn_pointer_set *) data1;
double *scale = (double *) data2;
double *sum = (double *) data3;
double wt = m->weight;
if (scale)
wt *= *scale;
if (sum)
(*sum) += wt;
imp_mod_set_insert (receiving_set, m->imp_mod, wt);
return 1;
}
static int
sort_by_count (const void *pa, const void *pb)
{
const struct dyn_cgraph_edge *edge_a = *(struct dyn_cgraph_edge * const *)pa;
const struct dyn_cgraph_edge *edge_b = *(struct dyn_cgraph_edge * const *)pb;
/* This can overvlow. */
/* return edge_b->count - edge_a->count; */
if (edge_b->count > edge_a->count)
return 1;
else if (edge_b->count == edge_a->count)
return 0;
else
return -1;
}
/* Compute the hot callgraph edge threhold. */
static gcov_type
gcov_compute_cutoff_count (void)
{
unsigned m_ix, capacity, i;
unsigned num_edges = 0;
gcov_type cutoff_count;
double total, cum, cum_cutoff;
struct dyn_cgraph_edge **edges;
struct gcov_info *gi_ptr;
char *cutoff_str;
char *num_perc_str;
unsigned cutoff_perc;
unsigned num_perc;
int do_dump;
capacity = 100;
/* allocate an edge array */
edges = XNEWVEC (struct dyn_cgraph_edge*, capacity);
/* First count the number of edges. */
for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++)
{
const struct gcov_fn_info *fi_ptr;
unsigned f_ix;
gi_ptr = the_dyn_call_graph.modules[m_ix];
for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++)
{
struct dyn_cgraph_node *node;
struct dyn_cgraph_edge *callees;
fi_ptr = the_dyn_call_graph.functions[m_ix][f_ix];
node = *(pointer_set_find_or_insert
(the_dyn_call_graph.call_graph_nodes[m_ix], fi_ptr->ident));
gcc_assert (node);
callees = node->callees;
while (callees != 0)
{
num_edges++;
if (num_edges < capacity)
edges[num_edges - 1] = callees;
else
{
capacity = capacity + (capacity >> 1);
edges = (struct dyn_cgraph_edge **)realloc (edges, sizeof (void*) * capacity);
edges[num_edges - 1] = callees;
}
callees = callees->next_callee;
}
}
}
/* Now sort */
qsort (edges, num_edges, sizeof (void *), sort_by_count);
#define CUM_CUTOFF_PERCENT 80
#define MIN_NUM_EDGE_PERCENT 0
cutoff_str = getenv ("GCOV_DYN_CGRAPH_CUTOFF");
if (cutoff_str && strlen (cutoff_str))
{
if ((num_perc_str = strchr (cutoff_str, ':')))
{
*num_perc_str = '\0';
num_perc_str++;
}
cutoff_perc = atoi (cutoff_str);
if (num_perc_str)
num_perc = atoi (num_perc_str);
else
num_perc = MIN_NUM_EDGE_PERCENT;
}
else
{
cutoff_perc = CUM_CUTOFF_PERCENT;
num_perc = MIN_NUM_EDGE_PERCENT;
}
total = 0;
cum = 0;
for (i = 0; i < num_edges; i++)
total += edges[i]->count;
cum_cutoff = (total * cutoff_perc)/100;
do_dump = (getenv ("GCOV_DYN_CGRAPH_DUMP") != 0);
for (i = 0; i < num_edges; i++)
{
cum += edges[i]->count;
if (do_dump)
fprintf (stderr, "// edge[%d] count = %.0f [%llx --> %llx]\n",
i, (double) edges[i]->count,
(long long) edges[i]->caller->guid,
(long long) edges[i]->callee->guid);
if (cum >= cum_cutoff && (i * 100 >= num_edges * num_perc))
{
cutoff_count = edges[i]->count;
break;
}
}
if (do_dump)
fprintf (stderr, "// total = %.0f cum = %.0f cum/total = %.0f%%"
" cutoff_count = %lld [total edges: %d hot edges: %d perc: %d%%]\n"
" total_zero_count_edges = %d total_insane_count_edgess = %d\n"
" total_nodes_executed = %d\n",
total, cum, (cum * 100)/total, (long long) cutoff_count,
num_edges, i, (i * 100)/num_edges, total_zero_count,
total_insane_count, the_dyn_call_graph.num_nodes_executed);
XDELETEVEC (edges);
return cutoff_count;
}
static inline unsigned
imp_mod_get_key (const void *p)
{
return ((const struct dyn_imp_mod *) p)->imp_mod->mod_info->ident;
}
/* Return the imported module set for NODE. */
static struct dyn_pointer_set *
gcov_get_imp_module_set (struct dyn_cgraph_node *node)
{
if (!node->imported_modules)
node->imported_modules = pointer_set_create (imp_mod_get_key);
return node->imported_modules;
}
/* Return the imported module set for MODULE MI. */
static struct dyn_pointer_set *
gcov_get_module_imp_module_set (struct dyn_module_info *mi)
{
if (!mi->imported_modules)
mi->imported_modules = pointer_set_create (imp_mod_get_key);
return mi->imported_modules;
}
/* Callback function to mark if a module needs to be exported. */
static int
gcov_mark_export_modules (const void *value,
void *data1 ATTRIBUTE_UNUSED,
void *data2 ATTRIBUTE_UNUSED,
void *data3 ATTRIBUTE_UNUSED)
{
const struct gcov_info *module_info
= ((const struct dyn_imp_mod *) value)->imp_mod;
module_info->mod_info->is_exported = 1;
return 1;
}
struct gcov_import_mod_array
{
const struct dyn_imp_mod **imported_modules;
struct gcov_info *importing_module;
unsigned len;
};
/* Callback function to compute pointer set size. */
static int
gcov_compute_mset_size (const void *value ATTRIBUTE_UNUSED,
void *data1,
void *data2 ATTRIBUTE_UNUSED,
void *data3 ATTRIBUTE_UNUSED)
{
unsigned *len = (unsigned *) data1;
(*len)++;
return 1;
}
/* Callback function to collect imported modules. */
static int
gcov_collect_imported_modules (const void *value,
void *data1,
void *data2 ATTRIBUTE_UNUSED,
void *data3 ATTRIBUTE_UNUSED)
{
struct gcov_import_mod_array *out_array;
const struct dyn_imp_mod *m
= (const struct dyn_imp_mod *) value;
out_array = (struct gcov_import_mod_array *) data1;
if (m->imp_mod != out_array->importing_module)
out_array->imported_modules[out_array->len++] = m;
return 1;
}
/* Comparator for sorting imported modules using weights. */
static int
sort_by_module_wt (const void *pa, const void *pb)
{
const struct dyn_imp_mod *m_a = *((const struct dyn_imp_mod * const *) pa);
const struct dyn_imp_mod *m_b = *((const struct dyn_imp_mod * const *) pb);
/* We want to sort in descending order of weights. */
if (m_a->weight < m_b->weight)
return +1;
if (m_a->weight > m_b->weight)
return -1;
return get_module_idx (m_a->imp_mod) - get_module_idx (m_b->imp_mod);
}
/* Return a dynamic array of imported modules that is sorted for
the importing module MOD_INFO. The length of the array is returned
in *LEN. */
const struct dyn_imp_mod **
gcov_get_sorted_import_module_array (struct gcov_info *mod_info,
unsigned *len)
{
unsigned mod_id;
struct dyn_module_info *sup_mod_info;
unsigned array_len = 0;
struct gcov_import_mod_array imp_array;
mod_id = get_module_idx (mod_info);
sup_mod_info = &the_dyn_call_graph.sup_modules[mod_id];
if (sup_mod_info->imported_modules == 0)
return 0;
pointer_set_traverse (sup_mod_info->imported_modules,
gcov_compute_mset_size, &array_len, 0, 0);
imp_array.imported_modules = XNEWVEC (const struct dyn_imp_mod *, array_len);
imp_array.len = 0;
imp_array.importing_module = mod_info;
pointer_set_traverse (sup_mod_info->imported_modules,
gcov_collect_imported_modules, &imp_array, 0, 0);
*len = imp_array.len;
qsort (imp_array.imported_modules, imp_array.len,
sizeof (void *), sort_by_module_wt);
return imp_array.imported_modules;
}
/* Compute modules that are needed for NODE (for cross module inlining).
CUTTOFF_COUNT is the call graph edge count cutoff value.
IMPORT_SCALE is the scaling-factor (percent) by which to scale the
weights of imported modules of a callee before propagating them to
the caller, if the callee and caller are in different modules.
Each imported module is assigned a weight that corresponds to the
expected benefit due to cross-module inlining. When the imported modules
are written out, they are sorted with highest weight first.
The following example illustrates how the weight is computed:
Suppose we are processing call-graph node A. It calls function B 50 times,
which calls function C 1000 times, and function E 800 times. Lets say B has
another in-edge from function D, with edge-count of 50. Say all the
functions are in separate modules (modules a, b, c, d, e, respectively):
D
|
| 50
|
50 v 1000
A --------> B ----------> C
|
| 800
|
v
E
Nodes are processed in depth-first order, so when processing A, we first
process B. For node B, we are going to add module c to the imported-module
set, with weight 1000 (edge-count), and module e with weight 800.
Coming back to A, we are going to add the imported-module-set of B to A,
after doing some scaling.
The first scaling factor comes from the fact that A calls B 50 times, but B
has in-edge-count total of 100. So this scaling factor is 50/100 = 0.5
The second scaling factor is that since B is in a different module than A,
we want to slightly downgrade imported modules of B, before adding to the
imported-modules set of A. This scaling factor has a default value of 50%
(can be set via env variable GCOV_DYN_IMPORT_SCALE).
So we end up adding modules c and e to the imported-set of A, with weights
0.5*0.5*1000=250 and 0.5*0.5*800=200, respectively.
Next, we have to add module b itself to A. The weight is computed as the
edge-count plus the sum of scaled-weights of all modules in the
imported-module set of B, i.e., 50 + 250 + 200 = 500.
In computing the weight of module b, we add the sum of scaled-weights of
imported modules of b, because it doesn't make sense to import c, e in
module a, until module b is imported. */
static void
gcov_process_cgraph_node (struct dyn_cgraph_node *node,
gcov_type cutoff_count,
unsigned import_scale)
{
unsigned mod_id;
struct dyn_cgraph_edge *callees;
struct dyn_cgraph_edge *callers;
node->visited = 1;
node->sum_in_count = 0;
callers = node->callers;
while (callers)
{
node->sum_in_count += callers->count;
callers = callers->next_caller;
}
callees = node->callees;
mod_id = get_module_idx_from_func_glob_uid (node->guid);
while (callees)
{
if (!callees->callee->visited)
gcov_process_cgraph_node (callees->callee,
cutoff_count,
import_scale);
callees = callees->next_callee;
}
callees = node->callees;
while (callees)
{
if (callees->count >= cutoff_count)
{
unsigned callee_mod_id;
struct dyn_pointer_set *imp_modules
= gcov_get_imp_module_set (node);
callee_mod_id
= get_module_idx_from_func_glob_uid (callees->callee->guid);
double callee_mod_wt = (double) callees->count;
if (callees->callee->imported_modules)
{
double scale = ((double) callees->count) /
((double) callees->callee->sum_in_count);
/* Reduce weight if callee is in different module. */
if (mod_id != callee_mod_id)
scale = (scale * import_scale) / 100.0;
pointer_set_traverse (callees->callee->imported_modules,
gcov_propagate_imp_modules,
imp_modules, &scale, &callee_mod_wt);
}
if (mod_id != callee_mod_id)
{
struct gcov_info *callee_mod_info
= get_module_info (callee_mod_id);
imp_mod_set_insert (imp_modules, callee_mod_info, callee_mod_wt);
}
}
callees = callees->next_callee;
}
}
/* Compute module grouping using CUTOFF_COUNT as the hot edge
threshold. */
#define DEFAULT_IMPORT_SCALE 100
static void
gcov_compute_module_groups (gcov_type cutoff_count)
{
unsigned m_ix;
struct gcov_info *gi_ptr;
const char *import_scale_str;
unsigned import_scale = DEFAULT_IMPORT_SCALE;
import_scale_str = getenv ("GCOV_DYN_IMPORT_SCALE");
if (import_scale_str && strlen (import_scale_str))
import_scale = atoi (import_scale_str);
for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++)
{
const struct gcov_fn_info *fi_ptr;
unsigned f_ix;
gi_ptr = the_dyn_call_graph.modules[m_ix];
for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++)
{
struct dyn_cgraph_node *node;
fi_ptr = the_dyn_call_graph.functions[m_ix][f_ix];
node = *(pointer_set_find_or_insert
(the_dyn_call_graph.call_graph_nodes[m_ix], fi_ptr->ident));
gcc_assert (node);
if (node->visited)
continue;
gcov_process_cgraph_node (node, cutoff_count, import_scale);
}
}
for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++)
{
const struct gcov_fn_info *fi_ptr;
unsigned f_ix;
gi_ptr = the_dyn_call_graph.modules[m_ix];
for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++)
{
struct dyn_cgraph_node *node;
unsigned mod_id;
struct dyn_pointer_set *imp_modules;
fi_ptr = the_dyn_call_graph.functions[m_ix][f_ix];
node = *(pointer_set_find_or_insert
(the_dyn_call_graph.call_graph_nodes[m_ix], fi_ptr->ident));
gcc_assert (node);
if (!node->imported_modules)
continue;
mod_id = get_module_idx_from_func_glob_uid (node->guid);
gcc_assert (mod_id == m_ix);
imp_modules
= gcov_get_module_imp_module_set (
&the_dyn_call_graph.sup_modules[mod_id]);
pointer_set_traverse (node->imported_modules,
gcov_propagate_imp_modules,
imp_modules, 0, 0);
}
}
/* Now compute the export attribute */
for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++)
{
struct dyn_module_info *mi
= &the_dyn_call_graph.sup_modules[m_ix];
if (mi->imported_modules)
pointer_set_traverse (mi->imported_modules,
gcov_mark_export_modules, 0, 0, 0);
}
}
/* For each module, compute at random, the group of imported modules,
that is of size at most MAX_GROUP_SIZE. */
static void
gcov_compute_random_module_groups (unsigned max_group_size)
{
unsigned m_ix;
if (max_group_size > the_dyn_call_graph.num_modules)
max_group_size = the_dyn_call_graph.num_modules;
for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++)
{
struct dyn_pointer_set *imp_modules =
gcov_get_module_imp_module_set (&the_dyn_call_graph.sup_modules[m_ix]);
int cur_group_size = random () % max_group_size;
int i = 0;
while (i < cur_group_size)
{
struct gcov_info *imp_mod_info;
unsigned mod_id = random () % the_dyn_call_graph.num_modules;
if (mod_id == m_ix)
continue;
imp_mod_info = get_module_info (mod_id);
if (!imp_mod_set_insert (imp_modules, imp_mod_info, 1.0))
i++;
}
}
/* Now compute the export attribute */
for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++)
{
struct dyn_module_info *mi
= &the_dyn_call_graph.sup_modules[m_ix];
if (mi->imported_modules)
pointer_set_traverse (mi->imported_modules,
gcov_mark_export_modules, 0, 0, 0);
}
}
/* Write out MOD_INFO into the gcda file. IS_PRIMARY is a flag
indicating if the module is the primary module in the group. */
static void
gcov_write_module_info (const struct gcov_info *mod_info,
unsigned is_primary)
{
gcov_unsigned_t len = 0, filename_len = 0, src_filename_len = 0, i, j;
gcov_unsigned_t num_strings;
gcov_unsigned_t *aligned_fname;
struct gcov_module_info *module_info = mod_info->mod_info;
filename_len = (strlen (module_info->da_filename) +
sizeof (gcov_unsigned_t)) / sizeof (gcov_unsigned_t);
src_filename_len = (strlen (module_info->source_filename) +
sizeof (gcov_unsigned_t)) / sizeof (gcov_unsigned_t);
len = filename_len + src_filename_len;
len += 2; /* each name string is led by a length. */
num_strings = module_info->num_quote_paths + module_info->num_bracket_paths +
module_info->num_cpp_defines + module_info->num_cpp_includes +
module_info->num_cl_args;
for (i = 0; i < num_strings; i++)
{
gcov_unsigned_t string_len
= (strlen (module_info->string_array[i]) + sizeof (gcov_unsigned_t))
/ sizeof (gcov_unsigned_t);
len += string_len;
len += 1; /* Each string is lead by a length. */
}
len += 9; /* 9 more fields */
gcov_write_tag_length (GCOV_TAG_MODULE_INFO, len);
gcov_write_unsigned (module_info->ident);
gcov_write_unsigned (is_primary);
gcov_write_unsigned (module_info->is_exported);
gcov_write_unsigned (module_info->lang);
gcov_write_unsigned (module_info->num_quote_paths);
gcov_write_unsigned (module_info->num_bracket_paths);
gcov_write_unsigned (module_info->num_cpp_defines);
gcov_write_unsigned (module_info->num_cpp_includes);
gcov_write_unsigned (module_info->num_cl_args);
/* Now write the filenames */
aligned_fname = (gcov_unsigned_t *) alloca ((filename_len + src_filename_len + 2) *
sizeof (gcov_unsigned_t));
memset (aligned_fname, 0,
(filename_len + src_filename_len + 2) * sizeof (gcov_unsigned_t));
aligned_fname[0] = filename_len;
strcpy ((char*) (aligned_fname + 1), module_info->da_filename);
aligned_fname[filename_len + 1] = src_filename_len;
strcpy ((char*) (aligned_fname + filename_len + 2), module_info->source_filename);
for (i = 0; i < (filename_len + src_filename_len + 2); i++)
gcov_write_unsigned (aligned_fname[i]);
/* Now write the string array. */
for (j = 0; j < num_strings; j++)
{
gcov_unsigned_t *aligned_string;
gcov_unsigned_t string_len =
(strlen (module_info->string_array[j]) + sizeof (gcov_unsigned_t)) /
sizeof (gcov_unsigned_t);
aligned_string = (gcov_unsigned_t *)
alloca ((string_len + 1) * sizeof (gcov_unsigned_t));
memset (aligned_string, 0, (string_len + 1) * sizeof (gcov_unsigned_t));
aligned_string[0] = string_len;
strcpy ((char*) (aligned_string + 1), module_info->string_array[j]);
for (i = 0; i < (string_len + 1); i++)
gcov_write_unsigned (aligned_string[i]);
}
}
/* Write out MOD_INFO and its imported modules into gcda file. */
void
gcov_write_module_infos (struct gcov_info *mod_info)
{
unsigned mod_id, imp_len = 0;
const struct dyn_imp_mod **imp_mods;
mod_id = get_module_idx (mod_info);
gcov_write_module_info (mod_info, 1);
imp_mods = gcov_get_sorted_import_module_array (mod_info, &imp_len);
if (imp_mods)
{
unsigned i;
for (i = 0; i < imp_len; i++)
{
const struct gcov_info *imp_mod = imp_mods[i]->imp_mod;
gcov_write_module_info (imp_mod, 0);
}
free (imp_mods);
}
}
/* Compute module groups needed for L-IPO compilation. */
void
__gcov_compute_module_groups (void)
{
gcov_type cut_off_count;
char *seed = getenv ("LIPO_RANDOM_GROUPING");
char *max_group_size = seed ? strchr (seed, ':') : 0;
if (seed && max_group_size)
{
*max_group_size = '\0';
max_group_size++;
srandom (atoi (seed));
init_dyn_call_graph ();
gcov_compute_random_module_groups (atoi (max_group_size));
return;
}
/* First compute dynamic call graph. */
gcov_build_callgraph ();
cut_off_count = gcov_compute_cutoff_count ();
gcov_compute_module_groups (cut_off_count);
gcov_dump_callgraph (cut_off_count);
}
/* Dumper function for NODE. */
static void
gcov_dump_cgraph_node_short (struct dyn_cgraph_node *node)
{
unsigned mod_id, func_id;
struct gcov_info *mod_info;
mod_id = get_module_idx_from_func_glob_uid (node->guid);
func_id = get_intra_module_func_id (node->guid);
mod_info = the_dyn_call_graph.modules[mod_id];
fprintf (stderr, "NODE(%llx) module(%s) func(%u)",
(long long)node->guid,
mod_info->mod_info->source_filename, func_id);
}
/* Dumper function for NODE. M is the module id and F is the function id. */
static void
gcov_dump_cgraph_node (struct dyn_cgraph_node *node, unsigned m, unsigned f)
{
unsigned mod_id, func_id;
struct gcov_info *mod_info;
struct dyn_cgraph_edge *callers;
struct dyn_cgraph_edge *callees;
mod_id = get_module_idx_from_func_glob_uid (node->guid);
func_id = get_intra_module_func_id (node->guid);
gcc_assert (mod_id == m && func_id == f);
mod_info = the_dyn_call_graph.modules[mod_id];
fprintf (stderr, "NODE(%llx) module(%s) func(%x)\n",
(long long) node->guid,
mod_info->mod_info->source_filename, f);
/* Now dump callers. */
callers = node->callers;
fprintf (stderr, "\t[CALLERS]\n");
while (callers != 0)
{
fprintf (stderr,"\t\t[count=%ld] ", (long) callers->count);
gcov_dump_cgraph_node_short (callers->caller);
fprintf (stderr,"\n");
callers = callers->next_caller;
}
callees = node->callees;
fprintf (stderr, "\t[CALLEES]\n");
while (callees != 0)
{
fprintf (stderr,"\t\t[count=%ld] ", (long) callees->count);
gcov_dump_cgraph_node_short (callees->callee);
fprintf (stderr,"\n");
callees = callees->next_callee;
}
}
/* Dumper function for NODE. M is the module id and F is the function id. */
static void
gcov_dump_cgraph_node_dot (struct dyn_cgraph_node *node,
unsigned m, unsigned f,
gcov_type cutoff_count)
{
unsigned mod_id, func_id, imp_len = 0, i;
struct gcov_info *mod_info;
const struct dyn_imp_mod **imp_mods;
struct dyn_cgraph_edge *callees;
mod_id = get_module_idx_from_func_glob_uid (node->guid);
func_id = get_intra_module_func_id (node->guid);
gcc_assert (mod_id == m && func_id == f);
mod_info = the_dyn_call_graph.modules[mod_id];
fprintf (stderr, "NODE_%llx[label=\"MODULE\\n(%s)\\n FUNC(%x)\\n",
(long long) node->guid, mod_info->mod_info->source_filename, f);
imp_mods = gcov_get_sorted_import_module_array (mod_info, &imp_len);
fprintf (stderr, "IMPORTS:\\n");
if (imp_mods)
{
for (i = 0; i < imp_len; i++)
fprintf (stderr, "%s\\n", imp_mods[i]->imp_mod->mod_info->source_filename);
fprintf (stderr, "\"]\n");
free (imp_mods);
}
else
fprintf (stderr, "\"]\n");
callees = node->callees;
while (callees != 0)
{
if (callees->count >= cutoff_count)
fprintf (stderr, "NODE_%llx -> NODE_%llx[label=%lld color=red]\n",
(long long) node->guid, (long long) callees->callee->guid,
(long long) callees->count);
else
fprintf (stderr, "NODE_%llx -> NODE_%llx[label=%lld color=blue]\n",
(long long) node->guid, (long long) callees->callee->guid,
(long long) callees->count);
callees = callees->next_callee;
}
}
/* Dump dynamic call graph. CUTOFF_COUNT is the computed hot edge threshold. */
static void
gcov_dump_callgraph (gcov_type cutoff_count)
{
struct gcov_info *gi_ptr;
unsigned m_ix;
const char *dyn_cgraph_dump = 0;
dyn_cgraph_dump = getenv ("GCOV_DYN_CGRAPH_DUMP");
if (!dyn_cgraph_dump || !strlen (dyn_cgraph_dump))
return;
fprintf (stderr,"digraph dyn_call_graph {\n");
fprintf (stderr,"node[shape=box]\nsize=\"11,8.5\"\n");
for (m_ix = 0; m_ix < the_dyn_call_graph.num_modules; m_ix++)
{
const struct gcov_fn_info *fi_ptr;
unsigned f_ix;
gi_ptr = the_dyn_call_graph.modules[m_ix];
for (f_ix = 0; f_ix < gi_ptr->n_functions; f_ix++)
{
struct dyn_cgraph_node *node;
fi_ptr = the_dyn_call_graph.functions[m_ix][f_ix];
node = *(pointer_set_find_or_insert
(the_dyn_call_graph.call_graph_nodes[m_ix], fi_ptr->ident));
gcc_assert (node);
/* skip dead functions */
if (!node->callees && !node->callers)
continue;
if (dyn_cgraph_dump[0] == '1')
gcov_dump_cgraph_node (node, m_ix, fi_ptr->ident);
else
gcov_dump_cgraph_node_dot (node, m_ix, fi_ptr->ident,
cutoff_count);
}
}
fprintf (stderr,"}\n");
}
#endif