[PATCH 0/5] report allocation stats

[PATCH 0/5] report allocation stats

[Luc Van Oostenryck]

The goal of this series is to add some support to easily
report allocations statistics and thus be able to do
some experiments about allocation.

For example, playing a bit with this showed that most lists
are quite short (can be as short as and avarage of 2.5 elements
on some code) and that decreasing LIST_NODE_NR from 29 to 13
allow to win 5% when using make C=2 on the kernel (when all
source files have already been compile by GCC), which is already
quite interesting..


This series is available at:
	git://github.com/lucvoo/sparse.git alloc-stats
based on commits (a merge):
	263f8ce449097da4caacfac4e00144f626c6e6a7 (pre-llvm-fixes-v6)
	fc981fe285c37ee297e93ef1cc8725caac75f9b3 (fix-bitfield-init-v2
up to commit:
	bdd16ed276569a16b2362adb266048b91e617f32

Luc Van Oostenryck (5):
  add get_<allocator>_stats()
  add show_allocation_stats()
  add helper handle_simple_switch()
  teach sparse how to handle '-fmem-report'
  use -fmem-report to report allocation stats


 Makefile         |  1 +
 allocate.c       |  8 ++++++++
 allocate.h       | 13 ++++++++++++
 lib.c            | 26 ++++++++++++++++++++----
 lib.h            |  2 ++
 sparse-llvm.c    |  1 +
 sparse.1         |  4 ++++
 sparse.c         |  2 ++
 stats.c          | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 test-linearize.c |  2 ++
 test-unssa.c     |  1 +
 11 files changed, 118 insertions(+), 4 deletions(-)
 create mode 100644 stats.c

-- 
2.12.0

[PATCH 1/5] add get_<allocator>_stats()

[Luc Van Oostenryck]

There exists a function to display the stats from each allocator
but:
1) what it displays is a bit long and fixed
2) it doesn't allow to make totals and stuff.

Change this by adding a function that only collect the stats
from each allocator.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 allocate.c |  8 ++++++++
 allocate.h | 12 ++++++++++++
 2 files changed, 20 insertions(+)

diff --git a/allocate.c b/allocate.c
index f597caf16..daa4ac247 100644
--- a/allocate.c
+++ b/allocate.c
@@ -127,6 +127,14 @@ void show_allocations(struct allocator_struct *x)
 		(double) x->useful_bytes / x->allocations);
 }
 
+void get_allocator_stats(struct allocator_struct *x, struct allocator_stats *s)
+{
+	s->name = x->name;
+	s->allocations = x->allocations;
+	s->useful_bytes = x->useful_bytes;
+	s->total_bytes = x->total_bytes;
+}
+
 ALLOCATOR(ident, "identifiers");
 ALLOCATOR(token, "tokens");
 ALLOCATOR(context, "contexts");
diff --git a/allocate.h b/allocate.h
index 9e51ed7da..6e6c3a614 100644
--- a/allocate.h
+++ b/allocate.h
@@ -17,16 +17,24 @@ struct allocator_struct {
 	unsigned int allocations, total_bytes, useful_bytes;
 };
 
+struct allocator_stats {
+	const char *name;
+	unsigned int allocations;
+	unsigned long total_bytes, useful_bytes;
+};
+
 extern void protect_allocations(struct allocator_struct *desc);
 extern void drop_all_allocations(struct allocator_struct *desc);
 extern void *allocate(struct allocator_struct *desc, unsigned int size);
 extern void free_one_entry(struct allocator_struct *desc, void *entry);
 extern void show_allocations(struct allocator_struct *);
+extern void get_allocator_stats(struct allocator_struct *, struct allocator_stats *);
 
 #define __DECLARE_ALLOCATOR(type, x)		\
 	extern type *__alloc_##x(int);		\
 	extern void __free_##x(type *);		\
 	extern void show_##x##_alloc(void);	\
+	extern void get_##x##_stats(struct allocator_stats *);		\
 	extern void clear_##x##_alloc(void);	\
 	extern void protect_##x##_alloc(void);
 #define DECLARE_ALLOCATOR(x) __DECLARE_ALLOCATOR(struct x, x)
@@ -48,6 +56,10 @@ extern void show_allocations(struct allocator_struct *);
 	{							\
 		show_allocations(&x##_allocator);		\
 	}							\
+	void get_##x##_stats(struct allocator_stats *s)		\
+	{							\
+		get_allocator_stats(&x##_allocator, s);		\
+	}							\
 	void clear_##x##_alloc(void)				\
 	{							\
 		drop_all_allocations(&x##_allocator);		\
-- 
2.12.0

[PATCH 2/5] add show_allocation_stats()

[Luc Van Oostenryck]

There exist some function to display the stats from each allocator
(show_<allocator>_alloc()) but these functions need to be
called one by one and deosn't allow to make some totals.

Chnage this by adding show_allocation_stats() which display
(in a more consise way) the stats from every allocator, together
with the totals.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Makefile   |  1 +
 allocate.h |  1 +
 stats.c    | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 58 insertions(+)
 create mode 100644 stats.c

diff --git a/Makefile b/Makefile
index 3ac100744..7ba2dbd82 100644
--- a/Makefile
+++ b/Makefile
@@ -107,6 +107,7 @@ LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \
 	  char.o sort.o allocate.o compat-$(OS).o ptrlist.o \
 	  builtin.o \
 	  opcode.o \
+	  stats.o \
 	  flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o dissect.o
 
 LIB_FILE= libsparse.a
diff --git a/allocate.h b/allocate.h
index 6e6c3a614..64bb6dd64 100644
--- a/allocate.h
+++ b/allocate.h
@@ -29,6 +29,7 @@ extern void *allocate(struct allocator_struct *desc, unsigned int size);
 extern void free_one_entry(struct allocator_struct *desc, void *entry);
 extern void show_allocations(struct allocator_struct *);
 extern void get_allocator_stats(struct allocator_struct *, struct allocator_stats *);
+extern void show_allocation_stats(void);
 
 #define __DECLARE_ALLOCATOR(type, x)		\
 	extern type *__alloc_##x(int);		\
diff --git a/stats.c b/stats.c
new file mode 100644
index 000000000..5f2685733
--- /dev/null
+++ b/stats.c
@@ -0,0 +1,56 @@
+#include <stdio.h>
+#include "allocate.h"
+#include "linearize.h"
+#include "storage.h"
+
+__DECLARE_ALLOCATOR(struct ptr_list, ptrlist);
+
+
+typedef void (*get_t)(struct allocator_stats*);
+
+static void show_stats(get_t get, struct allocator_stats * tot)
+{
+	struct allocator_stats x;
+
+	if (get)
+		get(&x);
+	else
+		x = *tot;
+	fprintf(stderr, "%16s: %8d, %10ld, %10ld, %6.2f%%, %8.2f\n",
+		x.name, x.allocations, x.useful_bytes, x.total_bytes,
+		100 * (double) x.useful_bytes / (x.total_bytes ? : 1),
+		(double) x.useful_bytes / (x.allocations ? : 1));
+
+	tot->allocations += x.allocations;
+	tot->useful_bytes += x.useful_bytes;
+	tot->total_bytes += x.total_bytes;
+}
+
+void show_allocation_stats(void)
+{
+	struct allocator_stats tot = { .name = "total", };
+
+	fprintf(stderr, "%16s: %8s, %10s, %10s, %7s, %8s\n", "allocator", "allocs",
+		"bytes", "total", "%usage", "average");
+	show_stats(get_token_stats, &tot);
+	show_stats(get_ident_stats, &tot);
+	show_stats(get_symbol_stats, &tot);
+	show_stats(get_expression_stats, &tot);
+	show_stats(get_statement_stats, &tot);
+	show_stats(get_scope_stats, &tot);
+	show_stats(get_basic_block_stats, &tot);
+	show_stats(get_instruction_stats, &tot);
+	show_stats(get_pseudo_stats, &tot);
+	show_stats(get_pseudo_user_stats, &tot);
+	show_stats(get_ptrlist_stats, &tot);
+	show_stats(get_multijmp_stats, &tot);
+	show_stats(get_asm_rules_stats, &tot);
+	show_stats(get_asm_constraint_stats, &tot);
+	show_stats(get_context_stats, &tot);
+	show_stats(get_string_stats, &tot);
+	show_stats(get_bytes_stats, &tot);
+	//show_stats(get_storage_stats, &tot);
+	//show_stats(get_storage_hash_stats, &tot);
+
+	show_stats(NULL, &tot);
+}
-- 
2.12.0

[PATCH 3/5] add helper handle_simple_switch()

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 lib.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/lib.c b/lib.c
index 8c9c36bd5..1d21a2fb7 100644
--- a/lib.c
+++ b/lib.c
@@ -454,6 +454,25 @@ static void handle_arch_finalize(void)
 }
 
 
+static int handle_simple_switch(const char *arg, const char *name, int *flag)
+{
+	int val = 1;
+
+	// Prefixe "no-" mean to turn flag off.
+	if (strncmp(arg, "no-", 3) == 0) {
+		arg += 3;
+		val = 0;
+	}
+
+	if (strcmp(arg, name) == 0) {
+		*flag = val;
+		return 1;
+	}
+
+	// not handled
+	return 0;
+}
+
 static char **handle_switch_o(char *arg, char **next)
 {
 	if (!strcmp (arg, "o")) {       // "-o foo"
-- 
2.12.0

Re: [PATCH 3/5] add helper handle_simple_switch()

[Christopher Li]

I have some very minor comment.

On Wed, Apr 12, 2017 at 1:37 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> ---
>  lib.c | 19 +++++++++++++++++++
>  1 file changed, 19 insertions(+)
>
> diff --git a/lib.c b/lib.c
> index 8c9c36bd5..1d21a2fb7 100644
> --- a/lib.c
> +++ b/lib.c
> @@ -454,6 +454,25 @@ static void handle_arch_finalize(void)
>  }
>
>
> +static int handle_simple_switch(const char *arg, const char *name, int *flag)
> +{
> +       int val = 1;
> +
> +       // Prefixe "no-" mean to turn flag off.
> +       if (strncmp(arg, "no-", 3) == 0) {

You don't need to compare to zero. This can be written as:
 if (!strncmp(arg, "no-", 3)) {

That is how most of the strcmp done in sparse.

> +       if (strcmp(arg, name) == 0) {
> +               *flag = val;
> +               return 1;
> +       }

Same here.

Chris

Re: [PATCH 3/5] add helper handle_simple_switch()

[Luc Van Oostenryck]

On Thu, Jun 1, 2017 at 8:15 AM, Christopher Li <sparse@chrisli.org> wrote:
> I have some very minor comment.
>
>> +static int handle_simple_switch(const char *arg, const char *name, int *flag)
>> +{
>> +       int val = 1;
>> +
>> +       // Prefixe "no-" mean to turn flag off.
>> +       if (strncmp(arg, "no-", 3) == 0) {
>
> You don't need to compare to zero. This can be written as:
>  if (!strncmp(arg, "no-", 3)) {
>
> That is how most of the strcmp done in sparse.

I'm not sure exactly what you want me to do in this case.
Is it just a comment for things to avoid in the future or would you
like me to change it
before it is integrated?

Of course, I know that it is not needed to compare it against zero,
I do it purposely because when I use "if (!x) " it means to me something like
"x is invalid" or "x is not true" and my mental model of string
compare never match
with "is invalid" or "is not true", so I use the "if (x == 0)" idioms
to be very clear
that for strcmp() a return value of 0 means "the two strings are equal".

But I don't mind, I can change it if you prefer.
What annoys me is that this code have been posted more than 7 weeks ago,
is now part of the pull request I sent 2 weeks ago and by now I have 35 topic
branches that depend on this code and I certainly would prefer to do more
usefull things than handling these nits and rewrite all my history.

-- Luc

[PATCH 4/5] teach sparse how to handle '-fmem-report'

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 lib.c | 7 +++----
 lib.h | 1 +
 2 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/lib.c b/lib.c
index 1d21a2fb7..f316d120e 100644
--- a/lib.c
+++ b/lib.c
@@ -251,6 +251,7 @@ int dbg_entry = 0;
 int dbg_dead = 0;
 
 int fdump_linearize;
+int fmem_report = 0;
 
 int preprocess_only;
 
@@ -695,11 +696,9 @@ static char **handle_switch_f(char *arg, char **next)
 		return handle_switch_fdump(arg+5, next);
 
 	/* handle switches w/ arguments above, boolean and only boolean below */
+	if (handle_simple_switch(arg, "mem-report", &fmem_report))
+		return next;
 
-	if (!strncmp(arg, "no-", 3)) {
-		arg += 3;
-	}
-	/* handle switch here.. */
 	return next;
 }
 
diff --git a/lib.h b/lib.h
index fb612d154..14cb68af0 100644
--- a/lib.h
+++ b/lib.h
@@ -137,6 +137,7 @@ extern int dbg_entry;
 extern int dbg_dead;
 
 extern int fdump_linearize;
+extern int fmem_report;
 
 extern int arch_m64;
 
-- 
2.12.0

[PATCH 5/5] use -fmem-report to report allocation stats

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 lib.h            | 1 +
 sparse-llvm.c    | 1 +
 sparse.1         | 4 ++++
 sparse.c         | 2 ++
 stats.c          | 6 ++++++
 test-linearize.c | 2 ++
 test-unssa.c     | 1 +
 7 files changed, 17 insertions(+)

diff --git a/lib.h b/lib.h
index 14cb68af0..a0066dc57 100644
--- a/lib.h
+++ b/lib.h
@@ -147,6 +147,7 @@ extern struct symbol_list *sparse_initialize(int argc, char **argv, struct strin
 extern struct symbol_list *__sparse(char *filename);
 extern struct symbol_list *sparse_keep_tokens(char *filename);
 extern struct symbol_list *sparse(char *filename);
+extern void report_stats(void);
 
 static inline int symbol_list_size(struct symbol_list *list)
 {
diff --git a/sparse-llvm.c b/sparse-llvm.c
index ecc4f032f..6319c0ae9 100644
--- a/sparse-llvm.c
+++ b/sparse-llvm.c
@@ -1166,5 +1166,6 @@ int main(int argc, char **argv)
 
 	LLVMDisposeModule(module);
 
+	report_stats();
 	return 0;
 }
diff --git a/sparse.1 b/sparse.1
index 525d3ded5..d8e53ce38 100644
--- a/sparse.1
+++ b/sparse.1
@@ -351,6 +351,10 @@ Dump the IR code of a function directly after its linearization,
 before any simplifications is made. If the argument \fB=only\fR is
 also given no further processing is done on the function.
 .
+.TP
+.B \-fmem-report
+Report some statistics about memory allocation used by the tool.
+.
 .SH OTHER OPTIONS
 .TP
 .B \-ftabstop=WIDTH
diff --git a/sparse.c b/sparse.c
index 6b3324cfc..02ab97743 100644
--- a/sparse.c
+++ b/sparse.c
@@ -302,5 +302,7 @@ int main(int argc, char **argv)
 	FOR_EACH_PTR_NOTAG(filelist, file) {
 		check_symbols(sparse(file));
 	} END_FOR_EACH_PTR_NOTAG(file);
+
+	report_stats();
 	return 0;
 }
diff --git a/stats.c b/stats.c
index 5f2685733..cda18fcae 100644
--- a/stats.c
+++ b/stats.c
@@ -54,3 +54,9 @@ void show_allocation_stats(void)
 
 	show_stats(NULL, &tot);
 }
+
+void report_stats(void)
+{
+	if (fmem_report)
+		show_allocation_stats();
+}
diff --git a/test-linearize.c b/test-linearize.c
index dd2eaecab..fe0673bef 100644
--- a/test-linearize.c
+++ b/test-linearize.c
@@ -61,5 +61,7 @@ int main(int argc, char **argv)
 	FOR_EACH_PTR_NOTAG(filelist, file) {
 		clean_up_symbols(sparse(file));
 	} END_FOR_EACH_PTR_NOTAG(file);
+
+	report_stats();
 	return 0;
 }
diff --git a/test-unssa.c b/test-unssa.c
index f7a5c3a18..240d99601 100644
--- a/test-unssa.c
+++ b/test-unssa.c
@@ -82,5 +82,6 @@ int main(int argc, char **argv)
 		compile(sparse(file));
 	} END_FOR_EACH_PTR_NOTAG(file);
 
+	report_stats();
 	return 0;
 }
-- 
2.12.0