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

Cary Coutant ccoutant@google.com
Wed Nov 11 20:00:00 GMT 2009


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.
-------------- next part --------------
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.  */


More information about the Gcc-patches mailing list