GNU Info

(gprof.info)Internals

---

Next: Debugging Prev: File Format Up: Details

---

Enter node , (file) or (file)node

`gprof''s Internal Operation
============================

   Like most programs, `gprof' begins by processing its options.
During this stage, it may building its symspec list
(`sym_ids.c:sym_id_add'), if options are specified which use symspecs.
`gprof' maintains a single linked list of symspecs, which will
eventually get turned into 12 symbol tables, organized into six
include/exclude pairs - one pair each for the flat profile
(INCL_FLAT/EXCL_FLAT), the call graph arcs (INCL_ARCS/EXCL_ARCS),
printing in the call graph (INCL_GRAPH/EXCL_GRAPH), timing propagation
in the call graph (INCL_TIME/EXCL_TIME), the annotated source listing
(INCL_ANNO/EXCL_ANNO), and the execution count listing
(INCL_EXEC/EXCL_EXEC).

   After option processing, `gprof' finishes building the symspec list
by adding all the symspecs in `default_excluded_list' to the exclude
lists EXCL_TIME and EXCL_GRAPH, and if line-by-line profiling is
specified, EXCL_FLAT as well.  These default excludes are not added to
EXCL_ANNO, EXCL_ARCS, and EXCL_EXEC.

   Next, the BFD library is called to open the object file, verify that
it is an object file, and read its symbol table (`core.c:core_init'),
using `bfd_canonicalize_symtab' after mallocing an appropriately sized
array of symbols.  At this point, function mappings are read (if the
`--file-ordering' option has been specified), and the core text space
is read into memory (if the `-c' option was given).

   `gprof''s own symbol table, an array of Sym structures, is now built.
This is done in one of two ways, by one of two routines, depending on
whether line-by-line profiling (`-l' option) has been enabled.  For
normal profiling, the BFD canonical symbol table is scanned.  For
line-by-line profiling, every text space address is examined, and a new
symbol table entry gets created every time the line number changes.  In
either case, two passes are made through the symbol table - one to
count the size of the symbol table required, and the other to actually
read the symbols.  In between the two passes, a single array of type
`Sym' is created of the appropriate length.  Finally,
`symtab.c:symtab_finalize' is called to sort the symbol table and
remove duplicate entries (entries with the same memory address).

   The symbol table must be a contiguous array for two reasons.  First,
the `qsort' library function (which sorts an array) will be used to
sort the symbol table.  Also, the symbol lookup routine
(`symtab.c:sym_lookup'), which finds symbols based on memory address,
uses a binary search algorithm which requires the symbol table to be a
sorted array.  Function symbols are indicated with an `is_func' flag.
Line number symbols have no special flags set.  Additionally, a symbol
can have an `is_static' flag to indicate that it is a local symbol.

   With the symbol table read, the symspecs can now be translated into
Syms (`sym_ids.c:sym_id_parse').  Remember that a single symspec can
match multiple symbols.  An array of symbol tables (`syms') is created,
each entry of which is a symbol table of Syms to be included or
excluded from a particular listing.  The master symbol table and the
symspecs are examined by nested loops, and every symbol that matches a
symspec is inserted into the appropriate syms table.  This is done
twice, once to count the size of each required symbol table, and again
to build the tables, which have been malloced between passes.  From now
on, to determine whether a symbol is on an include or exclude symspec
list, `gprof' simply uses its standard symbol lookup routine on the
appropriate table in the `syms' array.

   Now the profile data file(s) themselves are read
(`gmon_io.c:gmon_out_read'), first by checking for a new-style
`gmon.out' header, then assuming this is an old-style BSD `gmon.out' if
the magic number test failed.

   New-style histogram records are read by `hist.c:hist_read_rec'.  For
the first histogram record, allocate a memory array to hold all the
bins, and read them in.  When multiple profile data files (or files
with multiple histogram records) are read, the starting address, ending
address, number of bins and sampling rate must match between the
various histograms, or a fatal error will result.  If everything
matches, just sum the additional histograms into the existing in-memory
array.

   As each call graph record is read (`call_graph.c:cg_read_rec'), the
parent and child addresses are matched to symbol table entries, and a
call graph arc is created by `cg_arcs.c:arc_add', unless the arc fails
a symspec check against INCL_ARCS/EXCL_ARCS.  As each arc is added, a
linked list is maintained of the parent's child arcs, and of the child's
parent arcs.  Both the child's call count and the arc's call count are
incremented by the record's call count.

   Basic-block records are read (`basic_blocks.c:bb_read_rec'), but
only if line-by-line profiling has been selected.  Each basic-block
address is matched to a corresponding line symbol in the symbol table,
and an entry made in the symbol's bb_addr and bb_calls arrays.  Again,
if multiple basic-block records are present for the same address, the
call counts are cumulative.

   A gmon.sum file is dumped, if requested (`gmon_io.c:gmon_out_write').

   If histograms were present in the data files, assign them to symbols
(`hist.c:hist_assign_samples') by iterating over all the sample bins
and assigning them to symbols.  Since the symbol table is sorted in
order of ascending memory addresses, we can simple follow along in the
symbol table as we make our pass over the sample bins.  This step
includes a symspec check against INCL_FLAT/EXCL_FLAT.  Depending on the
histogram scale factor, a sample bin may span multiple symbols, in
which case a fraction of the sample count is allocated to each symbol,
proportional to the degree of overlap.  This effect is rare for normal
profiling, but overlaps are more common during line-by-line profiling,
and can cause each of two adjacent lines to be credited with half a
hit, for example.

   If call graph data is present, `cg_arcs.c:cg_assemble' is called.
First, if `-c' was specified, a machine-dependent routine (`find_call')
scans through each symbol's machine code, looking for subroutine call
instructions, and adding them to the call graph with a zero call count.
A topological sort is performed by depth-first numbering all the
symbols (`cg_dfn.c:cg_dfn'), so that children are always numbered less
than their parents, then making a array of pointers into the symbol
table and sorting it into numerical order, which is reverse topological
order (children appear before parents).  Cycles are also detected at
this point, all members of which are assigned the same topological
number.  Two passes are now made through this sorted array of symbol
pointers.  The first pass, from end to beginning (parents to children),
computes the fraction of child time to propagate to each parent and a
print flag.  The print flag reflects symspec handling of
INCL_GRAPH/EXCL_GRAPH, with a parent's include or exclude (print or no
print) property being propagated to its children, unless they
themselves explicitly appear in INCL_GRAPH or EXCL_GRAPH.  A second
pass, from beginning to end (children to parents) actually propagates
the timings along the call graph, subject to a check against
INCL_TIME/EXCL_TIME.  With the print flag, fractions, and timings now
stored in the symbol structures, the topological sort array is now
discarded, and a new array of pointers is assembled, this time sorted
by propagated time.

   Finally, print the various outputs the user requested, which is now
fairly straightforward.  The call graph (`cg_print.c:cg_print') and
flat profile (`hist.c:hist_print') are regurgitations of values already
computed.  The annotated source listing
(`basic_blocks.c:print_annotated_source') uses basic-block information,
if present, to label each line of code with call counts, otherwise only
the function call counts are presented.

   The function ordering code is marginally well documented in the
source code itself (`cg_print.c').  Basically, the functions with the
most use and the most parents are placed first, followed by other
functions with the most use, followed by lower use functions, followed
by unused functions at the end.