[patch] Add discriminators to DWARF line table

[Cary Coutant <ccoutant at google dot com>]

The attached patch lays some groundwork for the addition of
sample-based profiling, as described in the paper, "Feedback-Directed
Optimizations in GCC with Estimated Edge Profiles from Hardware Event
Sampling," by Ramasamy et al., at last year's GCC summit:

  http://gccsummit.org/2008/gcc-2008-proceedings.pdf

One of the challenges listed in that paper was insufficient source
position information due to code from a single source position being
separated into two or more basic blocks. To address this problem,
we've introduced the concept of a "discriminator," which is simply an
extra column in the DWARF line number table that can be used to
distinguish between instructions in multiple basic blocks that share a
common source position. The proposal to extend the DWARF format can be
found on the DWARF wiki:

  http://wiki.dwarfstd.org/index.php?title=Path_Discriminators

This DWARF extension has been approved for the DWARF-4 specification,
and I've submitted a couple of binutils patches to add the necessary
support to gas, readelf, and objdump:

  http://sourceware.org/ml/binutils/2009-04/msg00308.html
  http://sourceware.org/ml/binutils/2009-04/msg00310.html

This patch adds a discriminator field to the basic block structure,
and assigns discriminators during gimplification. Whenever we add an
edge between two basic blocks where the end of the "from" block and
the entry of the "to" block have the same source position, we assign a
new discriminator to the "to" block. This value gets picked up at the
end of the compilation and added to the .loc directive in the assembly
output. I've added a configure check to make sure that discriminator
support is available in the target assembler.

With optimization, it's possible to lose the assigned discriminator
sometimes -- copy propagation can empty a basic block, allowing DCE to
remove it, only to recreate it when coming out of SSA. I have a plan
to remember the discriminator in the PHI nodes, but I talked with
Diego about it and he suggested leaving it as is until we know how
important it is to fix that. Assigning the discriminators later could
have avoided that problem, but the discriminators need to be assigned
early enough that we can know what discriminators were assigned to the
basic blocks when we're reading the sample-based profiling information
and setting the profile counts in those basic blocks. There are also
some cases where control flow is generated later that I don't yet take
care of (like switch statements), but we'll take care of that when
we're ready to use the profiling information in those cases.

A patch (or series of patches) to add sample-based profiling support
is under development, and should be ready well before the end of stage
1.

-cary


	* basic-block.h (struct basic_block_def): Add discriminator field.
	* dbxout.c (dbxout_source_line): Add new parameter.  Change all
	callers.
	* debug.c (do_nothing_debug_hooks): Add additional entry.
	(debug_nothing_int_charstar_int): New function.
	* debug.h (struct gcc_debug_hooks): Add parameter to source_line
	hook.
	(debug_nothing_int_charstar_int): New declaration.
	* dwarf2out.c (dwarf2out_source_line): Add new parameter.  Write
	discriminator value in .loc directive.
	* final.c (last_discriminator): New variable.
	(discriminator): New variable.
	(final_start_function): Initialize above variables, pass current
	discriminator to debug hook.
	(notice_source_line): Check for discriminator change.
	* gimple-pretty-print.c (dump_bb_header): Print discriminator value.
	* sdbout.c (sdbout_source_line): New parameter.
	* tree-cfg.c (struct locus_discrim_map): New structure type.
	(discriminator_per_locus): New hash table.
	(build_gimple_cfg): Allocate and free discriminator hash table.
	(make_edges): Call assign_discriminator.
	(locus_map_hash): New function.
	(locus_map_eq): New function.
	(next_discriminator_for_locus): New function.
	(assign_discriminator): New function.
	(make_cond_expr_edges): Call assign_discriminator.
	(make_gimple_switch_edges): Likewise.
	(first_non_label_stmt): New function.
	* vmsdbgout.c (vmsdbgout_source_line): Add new parameter.  Change
	all callers.
	* xcoffout.c (xcoffout_source_line): Add new parameter.

	* configure.ac (gcc_cv_as_discriminator): New configury check for
	gas support for discriminator.
	* configure: Regenerate.
	* config.in: Regenerate.

Attachment: gcc-discrim-patch.txt
Description: Text document