[RFC] Track discriminators by instruction instead of by basic block

[RFC] Track discriminators by instruction instead of by basic block

[Cary Coutant]

[-- Attachment #1: Type: text/plain, Size: 2637 bytes --]

The attached patch reworks discriminator assignment so that it
attaches the discriminator to the source location of each instruction
instead of to the basic block itself. I had hoped not to have to do it
this way, but we've found that we're losing too much discriminator
information when basic blocks get combined and resplit in later
optimization passes, and the loss of accuracy in the sample profiling
is hurting the performance. This approach turned out not to be as hard
as I originally thought it would be: When I need to assign a
discrimator, I allocate a new location_t value larger than any
assigned by libcpp, and keep two vectors that map each new location_t
value to its original libcpp-assigned value and to the discriminator
value itself.

I'm not looking to put this into mainline during Stage 3, since the
problem it solves is only for sample-based profiling, but I would like
to get this reviewed anyway. If it looks generally OK, I'll hold it in
the dwarf4 branch until the next Stage 1.

-cary

        * basic-block.h (struct basic_block_def): Remove discriminator field.
        * cfghooks.c (split_block): Remove discriminator field.
        * cfglayout.c (insn_discriminator): New function.
        * final.c (discriminator): Remove.
        (override_discriminator): New file-scope variable.
        (final_start_function): Remove tracking of discriminator by basic
        block.
        (final_scan_insn): Track discriminator by instruction.
        (notice_source_line): Check for discriminator override. Get
        discriminator from instruction.
        * gimple-pretty-print.c (dump_gimple_stmt): Print discriminator.
        (dump_bb_header): Don't print discriminator.
        * print-rtl.c (print_rtx): Print discriminator.
        * rtl.h (insn_discriminator): New function.
        * tree.h (min_discriminator_location): New global.
        (map_discriminator_location): New function.
        (get_discriminator_from_locus): New function.
        * tree.c (expand_location): Use map_discriminator_location.
        * tree-cfg.c: Include vecprim.h.
        (discriminator_location_locations): New variable.
        (discriminator_location_discriminators): New variable.
        (min_discriminator_location): New variable.
        (location_with_discriminator): New function.
        (has_discriminator): New function.
        (map_discriminator_location): New function.
        (get_discriminator_from_locus): New function.
        (assign_discriminator): Assign discriminators to instructions rather
        than to the basic block.
        * tree-pretty-print.c (dump_location): Print discriminator.

[-- Attachment #2: gcc-discrim-patch-8.txt --]
[-- Type: text/plain, Size: 13565 bytes --]

Index: tree-pretty-print.c
===================================================================
--- tree-pretty-print.c	(revision 154100)
+++ tree-pretty-print.c	(working copy)
@@ -439,6 +439,7 @@ static void
 dump_location (pretty_printer *buffer, location_t loc)
 {
   expanded_location xloc = expand_location (loc);
+  int discriminator = get_discriminator_from_locus (loc);
 
   pp_character (buffer, '[');
   if (xloc.file)
@@ -447,6 +448,11 @@ dump_location (pretty_printer *buffer, l
       pp_string (buffer, " : ");
     }
   pp_decimal_int (buffer, xloc.line);
+  if (discriminator)
+    {
+      pp_string (buffer, " discrim ");
+      pp_decimal_int (buffer, discriminator);
+    }
   pp_string (buffer, "] ");
 }
 
Index: tree.c
===================================================================
--- tree.c	(revision 154100)
+++ tree.c	(working copy)
@@ -3948,6 +3948,13 @@ expanded_location
 expand_location (source_location loc)
 {
   expanded_location xloc;
+
+  /* If LOC describes a location with a discriminator, extract the
+     discriminator and map it to the real location.  */
+  if (min_discriminator_location != UNKNOWN_LOCATION
+      && loc >= min_discriminator_location)
+    loc = map_discriminator_location (loc);
+
   if (loc <= BUILTINS_LOCATION)
     {
       xloc.file = loc == UNKNOWN_LOCATION ? NULL : _("<built-in>");
Index: tree.h
===================================================================
--- tree.h	(revision 154100)
+++ tree.h	(working copy)
@@ -5293,6 +5293,11 @@ struct GTY(()) tree_priority_map {
 #define tree_priority_map_hash tree_map_base_hash
 #define tree_priority_map_marked_p tree_map_base_marked_p
 
+/* In tree-cfg.c.  */
+extern location_t min_discriminator_location;
+extern location_t map_discriminator_location (location_t);
+extern int get_discriminator_from_locus (location_t);
+
 /* In tree-ssa.c */
 
 tree target_for_debug_bind (tree);
Index: final.c
===================================================================
--- final.c	(revision 154100)
+++ final.c	(working copy)
@@ -134,9 +134,6 @@ static int last_linenum;
 /* Last discriminator written to assembly.  */
 static int last_discriminator;
 
-/* Discriminator of current block.  */
-static int discriminator;
-
 /* Highest line number in current block.  */
 static int high_block_linenum;
 
@@ -146,9 +143,10 @@ static int high_function_linenum;
 /* Filename of last NOTE.  */
 static const char *last_filename;
 
-/* Override filename and line number.  */
+/* Override filename, line number, and discriminator.  */
 static const char *override_filename;
 static int override_linenum;
+static int override_discriminator;
 
 /* Whether to force emission of a line note before the next insn.  */
 static bool force_source_line = false;
@@ -1525,7 +1523,7 @@ final_start_function (rtx first ATTRIBUT
 
   last_filename = locator_file (prologue_locator);
   last_linenum = locator_line (prologue_locator);
-  last_discriminator = discriminator = 0;
+  last_discriminator = 0;
 
   high_block_linenum = high_function_linenum = last_linenum;
 
@@ -1864,8 +1862,6 @@ final_scan_insn (rtx insn, FILE *file, i
 	  else
 	    *seen |= SEEN_BB;
 
-          discriminator = NOTE_BASIC_BLOCK (insn)->discriminator;
-
 	  break;
 
 	case NOTE_INSN_EH_REGION_BEG:
@@ -1951,6 +1947,8 @@ final_scan_insn (rtx insn, FILE *file, i
 		{
 		  override_filename = LOCATION_FILE (*locus_ptr);
 		  override_linenum = LOCATION_LINE (*locus_ptr);
+		  override_discriminator =
+		      get_discriminator_from_locus (*locus_ptr);
 		}
 	    }
 	  break;
@@ -1984,11 +1982,14 @@ final_scan_insn (rtx insn, FILE *file, i
 		{
 		  override_filename = LOCATION_FILE (*locus_ptr);
 		  override_linenum = LOCATION_LINE (*locus_ptr);
+		  override_discriminator =
+		      get_discriminator_from_locus (*locus_ptr);
 		}
 	      else
 		{
 		  override_filename = NULL;
 		  override_linenum = 0;
+		  override_discriminator = 0;
 		}
 	    }
 	  break;
@@ -2733,16 +2734,19 @@ notice_source_line (rtx insn, bool *is_s
 {
   const char *filename;
   int linenum;
+  int discriminator;
 
   if (override_filename)
     {
       filename = override_filename;
       linenum = override_linenum;
+      discriminator = override_discriminator;
     }
   else
     {
       filename = insn_file (insn);
       linenum = insn_line (insn);
+      discriminator = insn_discriminator (insn);
     }
 
   if (filename == NULL)
Index: cfghooks.c
===================================================================
--- cfghooks.c	(revision 154100)
+++ cfghooks.c	(working copy)
@@ -437,7 +437,6 @@ split_block (basic_block bb, void *i)
   new_bb->count = bb->count;
   new_bb->frequency = bb->frequency;
   new_bb->loop_depth = bb->loop_depth;
-  new_bb->discriminator = bb->discriminator;
 
   if (dom_info_available_p (CDI_DOMINATORS))
     {
Index: gimple-pretty-print.c
===================================================================
--- gimple-pretty-print.c	(revision 154100)
+++ gimple-pretty-print.c	(working copy)
@@ -1505,7 +1505,9 @@ dump_gimple_stmt (pretty_printer *buffer
 
   if ((flags & TDF_LINENO) && gimple_has_location (gs))
     {
-      expanded_location xloc = expand_location (gimple_location (gs));
+      location_t loc = gimple_location (gs);
+      expanded_location xloc = expand_location (loc);
+      int discriminator = get_discriminator_from_locus (loc);
       pp_character (buffer, '[');
       if (xloc.file)
 	{
@@ -1515,6 +1517,11 @@ dump_gimple_stmt (pretty_printer *buffer
       pp_decimal_int (buffer, xloc.line);
       pp_string (buffer, ":");
       pp_decimal_int (buffer, xloc.column);
+      if (discriminator)
+	{
+	  pp_string (buffer, " discrim ");
+	  pp_decimal_int (buffer, discriminator);
+	}
       pp_string (buffer, "] ");
     }
 
@@ -1716,12 +1723,6 @@ dump_bb_header (pretty_printer *buffer, 
 		pp_decimal_int (buffer, get_lineno (gsi_stmt (gsi)));
 		break;
 	      }
-
-          if (bb->discriminator)
-            {
-              pp_string (buffer, ", discriminator ");
-	      pp_decimal_int (buffer, bb->discriminator);
-            }
 	}
       newline_and_indent (buffer, indent);
 
Index: print-rtl.c
===================================================================
--- print-rtl.c	(revision 154100)
+++ print-rtl.c	(working copy)
@@ -382,7 +382,13 @@ print_rtx (const_rtx in_rtx)
 		redundant with line number information and do not print anything
 		when there is no location information available.  */
 	    if (INSN_LOCATOR (in_rtx) && insn_file (in_rtx))
-	      fprintf(outfile, " %s:%i", insn_file (in_rtx), insn_line (in_rtx));
+	      {
+		int discriminator = insn_discriminator (in_rtx);
+		fprintf (outfile, " %s:%i", insn_file (in_rtx),
+			 insn_line (in_rtx));
+		if (discriminator)
+		  fprintf (outfile, " discrim %d", discriminator);
+	      }
 #endif
 	  }
 	else if (i == 6 && GET_CODE (in_rtx) == ASM_OPERANDS)
Index: cfglayout.c
===================================================================
--- cfglayout.c	(revision 154100)
+++ cfglayout.c	(working copy)
@@ -567,6 +567,16 @@ insn_file (const_rtx insn)
   return locator_file (INSN_LOCATOR (insn));
 }
 
+/* Return discriminator of the statement that produced this insn.  */
+int
+insn_discriminator (const_rtx insn)
+{
+  int loc = INSN_LOCATOR (insn);
+  if (!loc)
+    return 0;
+  return get_discriminator_from_locus (locator_location (loc));
+}
+
 /* Return true if LOC1 and LOC2 locators have the same location and scope.  */
 bool
 locator_eq (int loc1, int loc2)
Index: rtl.h
===================================================================
--- rtl.h	(revision 154100)
+++ rtl.h	(working copy)
@@ -1723,6 +1723,7 @@ extern rtx prev_cc0_setter (rtx);
 /* In cfglayout.c  */
 extern int insn_line (const_rtx);
 extern const char * insn_file (const_rtx);
+extern int insn_discriminator (const_rtx);
 extern location_t locator_location (int);
 extern int locator_line (int);
 extern const char * locator_file (int);
Index: basic-block.h
===================================================================
--- basic-block.h	(revision 154100)
+++ basic-block.h	(working copy)
@@ -249,9 +249,6 @@ struct GTY((chain_next ("%h.next_bb"), c
   /* Expected frequency.  Normalized to be in range 0 to BB_FREQ_MAX.  */
   int frequency;
 
-  /* The discriminator for this block.  */
-  int discriminator;
-
   /* Various flags.  See BB_* below.  */
   int flags;
 };
Index: tree-cfg.c
===================================================================
--- tree-cfg.c	(revision 154100)
+++ tree-cfg.c	(working copy)
@@ -47,6 +47,7 @@ along with GCC; see the file COPYING3.  
 #include "value-prof.h"
 #include "pointer-set.h"
 #include "tree-inline.h"
+#include "vecprim.h"
 
 /* This file contains functions for building the Control Flow Graph (CFG)
    for a function tree.  */
@@ -82,6 +83,12 @@ static struct cfg_stats_d cfg_stats;
 /* Nonzero if we found a computed goto while building basic blocks.  */
 static bool found_computed_goto;
 
+/* Vectors to map a discriminator-enhanced locus to a real locus and
+   discriminator value.  */
+static VEC(int,heap) *discriminator_location_locations = NULL;
+static VEC(int,heap) *discriminator_location_discriminators = NULL;
+location_t min_discriminator_location = UNKNOWN_LOCATION;
+
 /* Hash table to store last discriminator assigned for each locus.  */
 struct locus_discrim_map
 {
@@ -685,6 +692,60 @@ make_edges (void)
   fold_cond_expr_cond ();
 }
 
+/* Associate the DISCRIMINATOR with LOCUS, and return a new locus.
+   We associate discriminators with a locus by allocating location_t
+   values beyond those assigned by libcpp.  Each new value is mapped
+   directly to a real location_t value, and separately to the
+   discriminator.  */
+
+static location_t
+location_with_discriminator (location_t locus, int discriminator)
+{
+  static int next_discriminator_location = 0;
+
+  if (min_discriminator_location == UNKNOWN_LOCATION)
+    {
+      min_discriminator_location = line_table->highest_location + 1;
+      next_discriminator_location = min_discriminator_location;
+    }
+
+  VEC_safe_push (int, heap, discriminator_location_locations, (int) locus);
+  VEC_safe_push (int, heap, discriminator_location_discriminators,
+		 discriminator);
+  return next_discriminator_location++;
+}
+
+/* Return TRUE if LOCUS represents a location with a discriminator.  */
+
+static inline bool
+has_discriminator (location_t locus)
+{
+  return (min_discriminator_location != UNKNOWN_LOCATION
+  	  && locus >= min_discriminator_location);
+}
+
+/* Return the real location_t value for LOCUS.  */
+
+location_t
+map_discriminator_location (location_t locus)
+{
+  if (! has_discriminator (locus))
+    return locus;
+  return (location_t) VEC_index (int, discriminator_location_locations,
+				 locus - min_discriminator_location);
+}
+
+/* Return the discriminator for LOCUS.  */
+
+int
+get_discriminator_from_locus (location_t locus)
+{
+  if (! has_discriminator (locus))
+    return 0;
+  return VEC_index (int, discriminator_location_discriminators,
+		    locus - min_discriminator_location);
+}
+
 /* Trivial hash function for a location_t.  ITEM is a pointer to
    a hash table entry that maps a location_t to a discriminator.  */
 
@@ -755,22 +816,59 @@ same_line_p (location_t locus1, location
           && strcmp (from.file, to.file) == 0);
 }
 
-/* Assign a unique discriminator value to block BB if it begins at the same
-   LOCUS as its predecessor block.  */
+/* Assign a unique discriminator value to instructions in block BB that
+   have the same LOCUS as its predecessor block.  */
 
 static void
 assign_discriminator (location_t locus, basic_block bb)
 {
   gimple first_in_to_bb, last_in_to_bb;
+  int discriminator = 0;
 
-  if (locus == 0 || bb->discriminator != 0)
+  if (locus == UNKNOWN_LOCATION)
     return;
 
+  if (has_discriminator (locus))
+    locus = map_discriminator_location (locus);
+
+  /* Check the locus of the first (non-label) instruction in the block.  */
   first_in_to_bb = first_non_label_stmt (bb);
-  last_in_to_bb = last_stmt (bb);
-  if ((first_in_to_bb && same_line_p (locus, gimple_location (first_in_to_bb)))
-      || (last_in_to_bb && same_line_p (locus, gimple_location (last_in_to_bb))))
-    bb->discriminator = next_discriminator_for_locus (locus);
+  if (first_in_to_bb)
+    {
+      location_t first_locus = gimple_location (first_in_to_bb);
+      if (! has_discriminator (first_locus)
+	  && same_line_p (locus, first_locus))
+	discriminator = next_discriminator_for_locus (locus);
+    }
+
+  /* If the first instruction doesn't trigger a discriminator, check the
+     last instruction of the block.  This catches the case where the
+     increment portion of a for loop is placed at the end of the loop
+     body.  */
+  if (discriminator == 0)
+    {
+      last_in_to_bb = last_stmt (bb);
+      if (last_in_to_bb)
+	{
+	   location_t last_locus = gimple_location (last_in_to_bb);
+	   if (! has_discriminator (last_locus)
+	       && same_line_p (locus, last_locus))
+	     discriminator = next_discriminator_for_locus (locus);
+	}
+    }
+
+  if (discriminator != 0)
+    {
+      location_t new_locus = location_with_discriminator (locus, discriminator);
+      gimple_stmt_iterator gsi;
+
+      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gimple stmt = gsi_stmt (gsi);
+	  if (same_line_p (locus, gimple_location (stmt)))
+	    gimple_set_location (stmt, new_locus);
+	}
+    }
 }
 
 /* Create the edges for a GIMPLE_COND starting at block BB.  */

Re: [RFC] Track discriminators by instruction instead of by basic block

[Richard Guenther]

On Wed, Nov 11, 2009 at 1:39 PM, Cary Coutant <ccoutant@google.com> wrote:
> The attached patch reworks discriminator assignment so that it
> attaches the discriminator to the source location of each instruction
> instead of to the basic block itself. I had hoped not to have to do it
> this way, but we've found that we're losing too much discriminator
> information when basic blocks get combined and resplit in later
> optimization passes, and the loss of accuracy in the sample profiling
> is hurting the performance. This approach turned out not to be as hard
> as I originally thought it would be: When I need to assign a
> discrimator, I allocate a new location_t value larger than any
> assigned by libcpp, and keep two vectors that map each new location_t
> value to its original libcpp-assigned value and to the discriminator
> value itself.
>
> I'm not looking to put this into mainline during Stage 3, since the
> problem it solves is only for sample-based profiling, but I would like
> to get this reviewed anyway. If it looks generally OK, I'll hold it in
> the dwarf4 branch until the next Stage 1.

What's a discriminator?  Why is it worth bloating locations with it?
How much more memory do we need when keeping discriminators
with LTO (which you don't - patches to lto-streamer-{in,out} are missing).

Thanks,
Richard.

> -cary
>
>        * basic-block.h (struct basic_block_def): Remove discriminator field.
>        * cfghooks.c (split_block): Remove discriminator field.
>        * cfglayout.c (insn_discriminator): New function.
>        * final.c (discriminator): Remove.
>        (override_discriminator): New file-scope variable.
>        (final_start_function): Remove tracking of discriminator by basic
>        block.
>        (final_scan_insn): Track discriminator by instruction.
>        (notice_source_line): Check for discriminator override. Get
>        discriminator from instruction.
>        * gimple-pretty-print.c (dump_gimple_stmt): Print discriminator.
>        (dump_bb_header): Don't print discriminator.
>        * print-rtl.c (print_rtx): Print discriminator.
>        * rtl.h (insn_discriminator): New function.
>        * tree.h (min_discriminator_location): New global.
>        (map_discriminator_location): New function.
>        (get_discriminator_from_locus): New function.
>        * tree.c (expand_location): Use map_discriminator_location.
>        * tree-cfg.c: Include vecprim.h.
>        (discriminator_location_locations): New variable.
>        (discriminator_location_discriminators): New variable.
>        (min_discriminator_location): New variable.
>        (location_with_discriminator): New function.
>        (has_discriminator): New function.
>        (map_discriminator_location): New function.
>        (get_discriminator_from_locus): New function.
>        (assign_discriminator): Assign discriminators to instructions rather
>        than to the basic block.
>        * tree-pretty-print.c (dump_location): Print discriminator.
>

Re: [RFC] Track discriminators by instruction instead of by basic block

[Cary Coutant]

> What's a discriminator?  Why is it worth bloating locations with it?

A discriminator is a small integer that helps distinguish instructions
for profiling purposes, when code on two different logical paths
belongs to the same line. This allows sample-based profile information
to be attributed accurately to the appropriate basic blocks during
optimization. This is a new feature of the DWARF-4 line number table;
there's a full writeup on the DWARF wiki:

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

> How much more memory do we need when keeping discriminators
> with LTO (which you don't - patches to lto-streamer-{in,out} are missing).

Not a lot. We assign discriminators for only a small fraction of the
total number of locations in the program, so the number of unique
location_t values doesn't increase significantly. I didn't add
anything to the line_map structure, nor did I do anything at all in
libcpp, so it's not bloating the source_location/location_t data
structures at all. The extra space needed is linear with the number of
discriminators assigned, which is roughly one per for loop or switch
statement, plus an occasional discriminator for conditional
expressions or macro expansions with control flow. (In the old code
that I'm replacing, the extra space was one int per basic block.)

Yes, I do need to deal with this in the lto streamer -- thanks for
pointing that out.

-cary

Re: [RFC] Track discriminators by instruction instead of by basic block

[Cary Coutant]

> How much more memory do we need when keeping discriminators
> with LTO (which you don't - patches to lto-streamer-{in,out} are missing).

I'm thinking of leaving build_cfg the way it is currently (where it
assigns discriminators to basic blocks as necessary), but move the
mechanics of assigning the discriminators to individual instructions
down to the fixup_cfg pass. The earliest we actually use the
discriminators is in tree_profile, so that gets the discriminators
assigned just before we use them, and it means that the assignment
happens after lto-streamer-in, so I don't need to stream out the
per-instruction discriminator information. I'll still need to stream
the per-basic-block discriminator info out in output_cfg(), but that's
fairly easy, and adds only one byte (discriminators are small and
usually 0) per basic block.

Does that sound reasonable?

-cary

Re: [RFC] Track discriminators by instruction instead of by basic block

[Richard Guenther]

On Thu, Nov 12, 2009 at 8:44 PM, Cary Coutant <ccoutant@google.com> wrote:
>> How much more memory do we need when keeping discriminators
>> with LTO (which you don't - patches to lto-streamer-{in,out} are missing).
>
> I'm thinking of leaving build_cfg the way it is currently (where it
> assigns discriminators to basic blocks as necessary), but move the
> mechanics of assigning the discriminators to individual instructions
> down to the fixup_cfg pass. The earliest we actually use the
> discriminators is in tree_profile, so that gets the discriminators
> assigned just before we use them, and it means that the assignment
> happens after lto-streamer-in, so I don't need to stream out the
> per-instruction discriminator information. I'll still need to stream
> the per-basic-block discriminator info out in output_cfg(), but that's
> fairly easy, and adds only one byte (discriminators are small and
> usually 0) per basic block.

I don't think that observation is correct (that tree-profile is after
streaming in).

Richard.

> Does that sound reasonable?
>
> -cary
>

Re: [RFC] Track discriminators by instruction instead of by basic block

[Cary Coutant]

> I don't think that observation is correct (that tree-profile is after
> streaming in).

Yeah, you're right. It doesn't look like it's feasible to delay the
assignment of discriminators to instructions until after the IR is
streamed out. For the moment, I think we can live with losing the
discriminator information on a -flto compilation -- the important
thing is that they will be passed through a non-LTO initial
compilation so that samples from a profiling run can be mapped back to
the correct blocks. The profile-use compilation can use -flto, though,
as the discriminators will survive long enough for the frequency
information to be set correctly.

Nevertheless, I'll work on the fixing this before the next Stage 1
opens, and I'll try to make sure it doesn't bloat the external IR.
(Would one extra byte per instruction be considered excessive?)

Thanks!

-cary