Re: [PATCH 5/7] Add line map statistics to -fmem-report output

[Dodji Seketeli <dodji at redhat dot com>]

> On 07/16/2011 10:37 AM, Dodji Seketeli wrote:
> > +#define ONE_M ONE_K * ONE_K
> 
> Parenthesize this so that users don't need to.

OK.

> 
> > +  macro_maps_used_size =
> > +    LINEMAPS_MACRO_USED (set) * sizeof (struct line_map)
> > +    + macro_maps_locations_size;
> 
> It seems odd to add in the locations size here since it's also printed
> separately.

I wanted macro_maps_used_size to really reflect the total used size
for macro maps, without having to mentally do the addition of its two
components.  But at the same time, I was interested in seeing how much
memory were the locations taking inside the macro map memory.  As I
was suspecting them to take a lot of memory.  It turned out I could
gain much more by optimizing things elsewhere.

> 
> > +  fprintf (stderr, "Total allocated maps size:           %5lu%c\n",
> > +          SCALE (s.total_allocated_map_size),
> > +          STAT_LABEL (s.total_allocated_map_size));
> > +  fprintf (stderr, "Total used maps size:                %5lu%c\n",
> > +          SCALE (s.total_used_map_size),
> > +          STAT_LABEL (s.total_used_map_size));
> > +  fprintf (stderr, "Ordinary map used size:              %5lu%c\n",
> > +          SCALE (s.ordinary_maps_used_size),
> > +          STAT_LABEL (s.ordinary_maps_used_size));
> > +  fprintf (stderr, "Macro maps used size:                %5lu%c\n",
> > +          SCALE (s.macro_maps_used_size),
> > +          STAT_LABEL (s.macro_maps_used_size));
> > +  fprintf (stderr, "Number of ordinary maps allocated:   %5lu%c\n",
> > +          SCALE (s.num_ordinary_maps_allocated),
> > +          STAT_LABEL (s.num_ordinary_maps_allocated));
> > +  fprintf (stderr, "Number of ordinary maps used:        %5lu%c\n",
> > +          SCALE (s.num_ordinary_maps_used),
> > +          STAT_LABEL (s.num_ordinary_maps_used));
> > +  fprintf (stderr, "Number of macro maps used:           %5lu%c\n",
> > +          SCALE (s.num_macro_maps_used),
> > +          STAT_LABEL (s.num_macro_maps_used));
> > +  fprintf (stderr, "Ordinary maps allocated size:        %5lu%c\n",
> > +          SCALE (s.ordinary_maps_allocated_size),
> > +          STAT_LABEL (s.ordinary_maps_allocated_size));
> > +  fprintf (stderr, "Macro maps locations size:           %5lu%c\n",
> > +          SCALE (s.macro_maps_locations_size),
> > +          STAT_LABEL (s.macro_maps_locations_size));
> > +  fprintf (stderr, "Duplicated maps locations size:      %5lu%c\n",
> > +          SCALE (s.duplicated_macro_maps_locations_size),
> > +          STAT_LABEL (s.duplicated_macro_maps_locations_size));
> 
> This seems oddly sorted.

I am not sure what you mean exactly, but in the patch below I tried to
actually sort them this time, as opposed to just adding things as I
needed them, in no particular order.  :-) Please tell me if you prefer
any particular order.

> And why the difference between ordinary and macro maps in terms of
> what is printed?

It's related to the difference of memory layout of ordinary and macro
maps.  I wanted to understand how each component of a macro map
impacts the overall size of taken by the macro maps, and where/how I
could gain by working on the macro map encoding.

For macro maps, the memory is allocated in two parts.  First the array
line_maps::info_macro::maps, and then, for each map, there is memory
allocated for the locations it holds.  Then, because of the way the
mapping encoding is done, there can be times where the two locations
of an entry of a macro map are the same.  This space wasted by this
redundancy is what I tried to quantify with
duplicated_macro_maps_locations_size.  I wanted to quantify the memory
consumed by each of these components to see how much memory I could
save by changing the way the macro maps were organized.  E.g, at one
iteration, I realized that it really was the number of macro maps that
was hurting, independently of how each map were encoded.  So we could
work on reducing that.  Then we realized that we were allocating too
much memory, just for line_maps::info_macro::maps alone.  Hence the
memory allocator patch, etc...

The memory of ordinary macros on the other hand is allocated in a much
simpler linear way.  Just the size of line_maps::info_ordinary::maps
tells the story.

> 
> > +/* Counters defined in libcpp's macro.c.  */
> > +extern unsigned num_expanded_macros_counter;
> > +extern unsigned num_macro_tokens_counter;
> 
> These should be part of struct linemap_stats.

Done, and updated input.c accordingly.

Thanks.

Bootstrapped and tested it on x86_64-unknown-linux-gnu against a tree
based on trunk and containing the previous patches of the set.

This patch adds statistics about line maps' memory consumption and macro
expansion to the output of -fmem-report.  It has been useful in trying
to reduce the memory consumption of the macro maps support.

Tested on x86_64-unknown-linux-gnu against trunk.

gcc/
	* input.c (ONE_K, ONE_M, SCALE, STAT_LABEL, FORMAT_AMOUNT): New
	macros.
	(num_expanded_macros_counter, num_macro_tokens_counter): Declare
	new counters.
	(dump_line_table_statistics): Define new function.
	* input.h (dump_line_table_statistics): Declare new function.
	* toplev.c (dump_memory_report): Call dump_line_table_statistics.

libcpp/
	* line-map.h (struct linemap_stats): Declare new struct.
	(linemap_get_statistics): Declare ...
	* line-map.c (linemap_get_statistics):  ... new function.
	* macro.c (num_expanded_macros_counter, num_macro_tokens_counter):
	Declare new counters.
	(enter_macro_context, replace_args): Update
	num_macro_tokens_counter.
	(cpp_get_token_1): Update num_expanded_macros_counter.
---
 gcc/input.c               |   79 +++++++++++++++++++++++++++++++++++++++++++++
 gcc/input.h               |    2 +
 gcc/toplev.c              |    1 +
 libcpp/include/line-map.h |   20 +++++++++++
 libcpp/line-map.c         |   69 +++++++++++++++++++++++++++++++++++++++
 libcpp/macro.c            |   29 ++++++++++++++--
 6 files changed, 196 insertions(+), 4 deletions(-)

diff --git a/gcc/input.c b/gcc/input.c
index 83344d7..bdd1434 100644
--- a/gcc/input.c
+++ b/gcc/input.c
@@ -46,3 +46,82 @@ expand_location (source_location loc)
 					 LRK_SPELLING_LOCATION);
   return xloc;
 }
+
+#define ONE_K 1024
+#define ONE_M (ONE_K * ONE_K)
+
+/* Display a number as an integer multiple of either:
+   - 1024, if said integer is >= to 10 K (in base 2)
+   - 1024 * 1024, if said integer is >= 10 M in (base 2)
+ */
+#define SCALE(x) ((unsigned long) ((x) < 10 * ONE_K \
+		  ? (x) \
+		  : ((x) < 10 * ONE_M \
+		     ? (x) / ONE_K \
+		     : (x) / (ONE_M))))
+
+/* For a given integer, display either:
+   - the character 'k', if the number is higher than 10 K (in base 2)
+     but strictly lower than 10 M (in base 2)
+   - the character 'M' if the number is higher than 10 M (in base2)
+   - the charcter ' ' if the number is strictly lower  than 10 K  */
+#define STAT_LABEL(x) ((x) < 10 * ONE_K ? ' ' : ((x) < 10 * ONE_M ? 'k' : 'M'))
+
+/* Display an integer amount as multiple of 1K or 1M (in base 2Ã).
+   Display the correct unit (either k, M, or ' ') after the amout, as
+   well.  */
+#define FORMAT_AMOUNT(size) SCALE (size), STAT_LABEL (size)
+
+/* Dump statistics to stderr about the memory usage of the line_table
+   set of line maps.  This also displays some statistics about macro
+   expansion.  */
+
+void
+dump_line_table_statistics (void)
+{
+  struct linemap_stats s;
+
+  memset (&s, 0, sizeof (s));
+
+  linemap_get_statistics (line_table, &s);
+
+  fprintf (stderr, "Number of expanded macros:                     %5lu\n",
+           s.num_expanded_macros);
+  if (s.num_expanded_macros != 0)
+    fprintf (stderr, "Average number of tokens per macro expansion:  %5lu\n",
+             s.num_macro_tokens / s.num_expanded_macros);
+  fprintf (stderr,
+           "\nLine Table allocations during the "
+           "compilation process\n");
+  fprintf (stderr, "Number of ordinary maps used:        %5lu%c\n",
+           SCALE (s.num_ordinary_maps_used),
+           STAT_LABEL (s.num_ordinary_maps_used));
+  fprintf (stderr, "Ordinary map used size:              %5lu%c\n",
+           SCALE (s.ordinary_maps_used_size),
+           STAT_LABEL (s.ordinary_maps_used_size));
+  fprintf (stderr, "Number of ordinary maps allocated:   %5lu%c\n",
+           SCALE (s.num_ordinary_maps_allocated),
+           STAT_LABEL (s.num_ordinary_maps_allocated));
+  fprintf (stderr, "Ordinary maps allocated size:        %5lu%c\n",
+           SCALE (s.ordinary_maps_allocated_size),
+           STAT_LABEL (s.ordinary_maps_allocated_size));
+  fprintf (stderr, "Number of macro maps used:           %5lu%c\n",
+           SCALE (s.num_macro_maps_used),
+           STAT_LABEL (s.num_macro_maps_used));
+  fprintf (stderr, "Macro maps used size:                %5lu%c\n",
+           SCALE (s.macro_maps_used_size),
+           STAT_LABEL (s.macro_maps_used_size));
+  fprintf (stderr, "Macro maps locations size:           %5lu%c\n",
+           SCALE (s.macro_maps_locations_size),
+           STAT_LABEL (s.macro_maps_locations_size));
+  fprintf (stderr, "Duplicated maps locations size:      %5lu%c\n",
+           SCALE (s.duplicated_macro_maps_locations_size),
+           STAT_LABEL (s.duplicated_macro_maps_locations_size));
+  fprintf (stderr, "Total allocated maps size:           %5lu%c\n",
+           SCALE (s.total_allocated_map_size),
+           STAT_LABEL (s.total_allocated_map_size));
+  fprintf (stderr, "Total used maps size:                %5lu%c\n",
+           SCALE (s.total_used_map_size),
+           STAT_LABEL (s.total_used_map_size));
+  fprintf (stderr, "\n");
+}
diff --git a/gcc/input.h b/gcc/input.h
index 9fc55f3..f2f3513 100644
--- a/gcc/input.h
+++ b/gcc/input.h
@@ -55,4 +55,6 @@ extern location_t input_location;
   ((linemap_location_in_system_header_p (line_table, LOC)))
 #define in_system_header (in_system_header_at (input_location))
 
+void dump_line_table_statistics (void);
+
 #endif
diff --git a/gcc/toplev.c b/gcc/toplev.c
index 5f63b69..2f90261 100644
--- a/gcc/toplev.c
+++ b/gcc/toplev.c
@@ -1788,6 +1788,7 @@ target_reinit (void)
 void
 dump_memory_report (bool final)
 {
+  dump_line_table_statistics ();
   ggc_print_statistics ();
   stringpool_statistics ();
   dump_tree_statistics ();
diff --git a/libcpp/include/line-map.h b/libcpp/include/line-map.h
index 81fe6c9..3989c89 100644
--- a/libcpp/include/line-map.h
+++ b/libcpp/include/line-map.h
@@ -800,6 +800,26 @@ expanded_location linemap_expand_location_full (struct line_maps *,
 						source_location loc,
 						enum location_resolution_kind lrk);
 
+struct linemap_stats
+{
+  size_t num_ordinary_maps_allocated;
+  size_t num_ordinary_maps_used;
+  size_t ordinary_maps_allocated_size;
+  size_t ordinary_maps_used_size;
+  size_t num_expanded_macros;
+  size_t num_macro_tokens;
+  size_t num_macro_maps_used;
+  size_t macro_maps_used_size;
+  size_t macro_maps_locations_size;
+  size_t duplicated_macro_maps_locations_size;
+  size_t total_allocated_map_size;
+  size_t total_used_map_size;
+};
+
+/* Compute and return statistics about the memory consumption of some
+   parts of the line table SET.  */
+void linemap_get_statistics (struct line_maps *, struct linemap_stats *);
+
 /* Dump debugging information about source location LOC into the file
    stream STREAM. SET is the line map set LOC comes from.  */
 void linemap_dump_location (struct line_maps *, source_location, FILE *);
diff --git a/libcpp/line-map.c b/libcpp/line-map.c
index fbd88da..09dffcb 100644
--- a/libcpp/line-map.c
+++ b/libcpp/line-map.c
@@ -30,6 +30,11 @@ static const struct line_map * linemap_ordinary_map_lookup (struct line_maps *,
 							    source_location);
 static const struct line_map* linemap_macro_map_lookup (struct line_maps *,
 							source_location);
+
+/* Counters defined in macro.c.  */
+extern unsigned num_expanded_macros_counter;
+extern unsigned num_macro_tokens_counter;
+
 /* Initialize a line map set.  */
 
 void
@@ -993,3 +998,67 @@ linemap_dump_location (struct line_maps *set,
   fprintf (stream, "{P:%s;F:%s;L:%d;C:%d;S:%d;M:%p;E:%d,LOC:%d}",
 	   path, from, l, c, s, (void*)map, e, loc);
 }
+
+void
+linemap_get_statistics (struct line_maps *set,
+			struct linemap_stats *s)
+{
+  size_t ordinary_maps_allocated_size, ordinary_maps_used_size,
+    macro_maps_allocated_size, macro_maps_used_size,
+    macro_maps_locations_size = 0, duplicated_macro_maps_locations_size = 0,
+    total_allocated_map_size, total_used_map_size;
+  struct line_map *cur_map;
+
+  ordinary_maps_allocated_size =
+    LINEMAPS_ORDINARY_ALLOCATED (set) * sizeof (struct line_map);
+
+  ordinary_maps_used_size =
+    LINEMAPS_ORDINARY_USED (set) * sizeof (struct line_map);
+
+  macro_maps_allocated_size =
+    LINEMAPS_MACRO_ALLOCATED (set) * sizeof (struct line_map);
+
+  for (cur_map = LINEMAPS_MACRO_MAPS (set);
+       cur_map && cur_map <= LINEMAPS_LAST_MACRO_MAP (set);
+       ++cur_map)
+    {
+      unsigned i;
+
+      linemap_assert (linemap_macro_expansion_map_p (cur_map));
+
+      macro_maps_locations_size +=
+	2 * MACRO_MAP_NUM_MACRO_TOKENS (cur_map) * sizeof (source_location);
+
+      for (i = 0; i < 2 * MACRO_MAP_NUM_MACRO_TOKENS (cur_map); i+=2)
+	{
+	  if (MACRO_MAP_LOCATIONS (cur_map)[i] ==
+	      MACRO_MAP_LOCATIONS (cur_map)[i + 1])
+	    duplicated_macro_maps_locations_size +=
+	      sizeof (source_location);
+	}
+    }
+
+  macro_maps_used_size =
+    LINEMAPS_MACRO_USED (set) * sizeof (struct line_map)
+    + macro_maps_locations_size;
+
+  total_used_map_size = ordinary_maps_used_size + macro_maps_used_size;
+
+  total_allocated_map_size =
+    ordinary_maps_allocated_size + macro_maps_allocated_size +
+    macro_maps_locations_size;
+
+  s->num_ordinary_maps_allocated = LINEMAPS_ORDINARY_ALLOCATED (set);
+  s->num_ordinary_maps_used = LINEMAPS_ORDINARY_USED (set);
+  s->ordinary_maps_allocated_size = ordinary_maps_allocated_size;
+  s->ordinary_maps_used_size = ordinary_maps_used_size;
+  s->num_expanded_macros = num_expanded_macros_counter;
+  s->num_macro_tokens = num_macro_tokens_counter;
+  s->num_macro_maps_used = LINEMAPS_MACRO_USED (set);
+  s->macro_maps_used_size = macro_maps_used_size;
+  s->macro_maps_locations_size = macro_maps_locations_size;
+  s->duplicated_macro_maps_locations_size =
+    duplicated_macro_maps_locations_size;
+  s->total_allocated_map_size = total_allocated_map_size;
+  s->total_used_map_size = total_used_map_size;
+}
diff --git a/libcpp/macro.c b/libcpp/macro.c
index 0544eb1..1d35018 100644
--- a/libcpp/macro.c
+++ b/libcpp/macro.c
@@ -173,6 +173,13 @@ static void consume_next_token_from_context (cpp_reader *pfile,
 					     source_location *);
 static const cpp_token* cpp_get_token_1 (cpp_reader *, source_location *);
 
+/* Statistical counter tracking the number of macros that got
+   expanded.  */
+unsigned num_expanded_macros_counter = 0;
+/* Statistical counter tracking the total number tokens resulting
+   from macro expansion.  */
+unsigned num_macro_tokens_counter = 0;
+
 /* Emits a warning if NODE is a macro defined in the main file that
    has not been used.  */
 int
@@ -1084,10 +1091,15 @@ enter_macro_context (cpp_reader *pfile, cpp_hashnode *node,
 					    (const cpp_token **)
 					    macro_tokens->base,
 					    count);
+	      num_macro_tokens_counter += count;
 	    }
 	  else
-	    _cpp_push_token_context (pfile, node, macro->exp.tokens,
-				     macro_real_token_count (macro));
+	    {
+	      unsigned tokens_count = macro_real_token_count (macro);
+	      _cpp_push_token_context (pfile, node, macro->exp.tokens,
+				       tokens_count);
+	      num_macro_tokens_counter += tokens_count;
+	    }
 	}
 
       if (pragma_buff)
@@ -1097,13 +1109,18 @@ enter_macro_context (cpp_reader *pfile, cpp_hashnode *node,
 				     padding_token (pfile, result), 1);
 	  do
 	    {
+	      unsigned tokens_count;
 	      _cpp_buff *tail = pragma_buff->next;
 	      pragma_buff->next = NULL;
+	      tokens_count = ((const cpp_token **) BUFF_FRONT (pragma_buff)
+			      - (const cpp_token **) pragma_buff->base);
 	      push_ptoken_context (pfile, NULL, pragma_buff,
 				   (const cpp_token **) pragma_buff->base,
-				   ((const cpp_token **) BUFF_FRONT (pragma_buff)
-				    - (const cpp_token **) pragma_buff->base));
+				   tokens_count);
 	      pragma_buff = tail;
+	      if (!CPP_OPTION (pfile, track_macro_expansion))
+		num_macro_tokens_counter += tokens_count;
+
 	    }
 	  while (pragma_buff != NULL);
 	  return 2;
@@ -1702,6 +1719,8 @@ replace_args (cpp_reader *pfile, cpp_hashnode *node, cpp_macro *macro,
   else
     push_ptoken_context (pfile, node, buff, first,
 			 tokens_buff_count (buff));
+
+  num_macro_tokens_counter += tokens_buff_count (buff);
 }
 
 /* Return a special padding token, with padding inherited from SOURCE.  */
@@ -2246,6 +2265,8 @@ cpp_get_token_1 (cpp_reader *pfile, source_location *location)
 	}
       else
 	{
+	  if (pfile->context->macro)
+	    ++num_expanded_macros_counter;
 	  _cpp_pop_context (pfile);
 	  if (pfile->state.in_directive)
 	    continue;
-- 
		Dodji