[PATCH 0/4] fix bitfield initiallizers

[PATCH 0/4] fix bitfield initiallizers

[Luc Van Oostenryck]

The goal of this series is to fix two bugs related
to the initialization of bitfields:
- bad shift & mask
- no implicit zeroing

One notable change is the removal of bit_offset & bit_size
from struct access_data.


This series is available at:
	git://github.com/lucvoo/sparse.git fix-bitfield-init
based on commit:
	14964df5373292af78b29529d4fc7e1a26b67a97 (sparse-next @ 2017-03-31)
up to commit:
	6e778f937073d96934c6240b5d47a76b0d592e27


Luc Van Oostenryck (4):
  add support for a new flag: -fdump-linearize[=only]
  remove bit_size & bit_offset from struct access_data
  add test case for linearize_initializer() of bitfields
  fix implicit zero initializer.

 lib.c                                   |  22 +++++++
 lib.h                                   |   2 +
 linearize.c                             |  36 +++++++----
 sparse.1                                |   7 +++
 validation/linear/bitfield-init-mask.c  |  27 +++++++++
 validation/linear/bitfield-init-zero.c  | 102 ++++++++++++++++++++++++++++++++
 validation/linear/struct-init-full.c    |  28 +++++++++
 validation/linear/struct-init-partial.c |  41 +++++++++++++
 8 files changed, 255 insertions(+), 10 deletions(-)
 create mode 100644 validation/linear/bitfield-init-mask.c
 create mode 100644 validation/linear/bitfield-init-zero.c
 create mode 100644 validation/linear/struct-init-full.c
 create mode 100644 validation/linear/struct-init-partial.c

-- Luc Van Oostenryck

[PATCH 1/4] add support for a new flag: -fdump-linearize[=only]

[Luc Van Oostenryck]

The effect of this flag is to dump the IR just after the
linearization, before any simplification, and to stop
further processing if '=only' is given as argument.

The motivation of this flag is of course for debugging,
to be able to inspect the raw result of the linearization,
undisturbed by an simplification.

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

diff --git a/lib.c b/lib.c
index 272d2c88a..f5e4860a6 100644
--- a/lib.c
+++ b/lib.c
@@ -250,6 +250,8 @@ int Wvla = 1;
 int dbg_entry = 0;
 int dbg_dead = 0;
 
+int fdump_linearize;
+
 int preprocess_only;
 
 static enum { STANDARD_C89,
@@ -645,12 +647,32 @@ static char **handle_switch_ftabstop(char *arg, char **next)
 	return next;
 }
 
+static char **handle_switch_fdump(char *arg, char **next)
+{
+	if (!strncmp(arg, "linearize", 9)) {
+		if (arg[6] == '\0')
+			fdump_linearize = 1;
+		else if (!strcmp(arg+9, "=only"))
+			fdump_linearize = 2;
+		else
+			goto err;
+	}
+
+	/* ignore others flags */
+	return next;
+
+err:
+	die("error: unknown flag \"-fdump-%s\"", arg);
+}
+
 static char **handle_switch_f(char *arg, char **next)
 {
 	arg++;
 
 	if (!strncmp(arg, "tabstop=", 8))
 		return handle_switch_ftabstop(arg+8, next);
+	if (!strncmp(arg, "dump-", 5))
+		return handle_switch_fdump(arg+5, next);
 
 	/* handle switches w/ arguments above, boolean and only boolean below */
 
diff --git a/lib.h b/lib.h
index 134e56040..fb612d154 100644
--- a/lib.h
+++ b/lib.h
@@ -136,6 +136,8 @@ extern int Wvla;
 extern int dbg_entry;
 extern int dbg_dead;
 
+extern int fdump_linearize;
+
 extern int arch_m64;
 
 extern void declare_builtin_functions(void);
diff --git a/linearize.c b/linearize.c
index 2f850fb7e..61c804333 100644
--- a/linearize.c
+++ b/linearize.c
@@ -2171,6 +2171,12 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
 		add_one_insn(ep, insn);
 	}
 
+	if (fdump_linearize) {
+		if (fdump_linearize == 2)
+			return ep;
+		show_entry(ep);
+	}
+
 	/*
 	 * Do trivial flow simplification - branches to
 	 * branches, kill dead basicblocks etc
diff --git a/sparse.1 b/sparse.1
index 85d6e646b..525d3ded5 100644
--- a/sparse.1
+++ b/sparse.1
@@ -344,6 +344,13 @@ Look for system headers in the multiarch subdirectory \fIdir\fR.
 The \fIdir\fR name would normally take the form of the target's
 normalized GNU triplet. (e.g. i386-linux-gnu).
 .
+.SH DEBUG OPTIONS
+.TP
+.B \-fdump-linearize[=only]
+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.
+.
 .SH OTHER OPTIONS
 .TP
 .B \-ftabstop=WIDTH
-- 
2.12.0

Re: [PATCH 1/4] add support for a new flag: -fdump-linearize[=only]

[Dibyendu Majumdar]

Hi Luc,

On 7 April 2017 at 00:00, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> The effect of this flag is to dump the IR just after the
> linearization, before any simplification, and to stop
> further processing if '=only' is given as argument.
>
> The motivation of this flag is of course for debugging,
> to be able to inspect the raw result of the linearization,
> undisturbed by an simplification.
>

In my view it is better to use the existing -O<n> option to control
whether or not simplifications are done. That way sparse-llvm can be
run with/without simplifications.

Of course there is an issue that what should be the default for this
setting if no option is given by the user. I would suggest that -O0
switches off simplifications, any other value or not specifying -O
switches it on.

Thanks and Regards
Dibyendu

Re: [PATCH 1/4] add support for a new flag: -fdump-linearize[=only]

[Luc Van Oostenryck]

On Fri, Apr 7, 2017 at 2:32 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi Luc,
>
> On 7 April 2017 at 00:00, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> The effect of this flag is to dump the IR just after the
>> linearization, before any simplification, and to stop
>> further processing if '=only' is given as argument.
>>
>> The motivation of this flag is of course for debugging,
>> to be able to inspect the raw result of the linearization,
>> undisturbed by a simplification.
>>
>
> In my view it is better to use the existing -O<n> option to control
> whether or not simplifications are done.

But controlling whether or not simplifications (which one?) are done
is not what this new flag is all about.

-- Luc

[PATCH 2/4] remove bit_size & bit_offset from struct access_data

[Luc Van Oostenryck]

In struct access_data, the fields: 'bit_offset', 'bit_size' and
'alignment' are always the ones corresponding to the 'result_type'
and are thus completely redundant.

Change this by removing these fields and directly using
the info from the 'result_type' field.

Note: the motivation for this change is the realization that the
      initialization of bitfields are buggy because the 'bit_size'
      is never set for initializers. The bug could be solved by
      initializing 'bit_size' & 'bit_offset' but it was much
      simpler (and feel safer) to simply use the values from
      'result_type'.

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

diff --git a/linearize.c b/linearize.c
index 61c804333..e9610932b 100644
--- a/linearize.c
+++ b/linearize.c
@@ -844,8 +844,7 @@ struct access_data {
 	struct symbol *source_type;	// source ctype
 	pseudo_t address;		// pseudo containing address ..
 	pseudo_t origval;		// pseudo for original value ..
-	unsigned int offset, alignment;	// byte offset
-	unsigned int bit_size, bit_offset; // which bits
+	unsigned int offset;		// byte offset
 	struct position pos;
 };
 
@@ -898,9 +897,6 @@ static int linearize_address_gen(struct entrypoint *ep,
 	ad->pos = expr->pos;
 	ad->result_type = ctype;
 	ad->source_type = base_type(ctype);
-	ad->bit_size = ctype->bit_size;
-	ad->alignment = ctype->ctype.alignment;
-	ad->bit_offset = ctype->bit_offset;
 	if (expr->type == EXPR_PREOP && expr->op == '*')
 		return linearize_simple_address(ep, expr->unop, ad);
 
@@ -948,9 +944,11 @@ static pseudo_t linearize_store_gen(struct entrypoint *ep,
 	pseudo_t store = value;
 
 	if (type_size(ad->source_type) != type_size(ad->result_type)) {
+		struct symbol *ctype = ad->result_type;
+		unsigned int shift = ctype->bit_offset;
+		unsigned int size = ctype->bit_size;
 		pseudo_t orig = add_load(ep, ad);
-		int shift = ad->bit_offset;
-		unsigned long long mask = (1ULL << ad->bit_size)-1;
+		unsigned long long mask = (1ULL << size) - 1;
 
 		if (shift) {
 			store = add_binary_op(ep, ad->source_type, OP_SHL, value, value_pseudo(shift));
@@ -997,14 +995,15 @@ static pseudo_t add_symbol_address(struct entrypoint *ep, struct symbol *sym)
 
 static pseudo_t linearize_load_gen(struct entrypoint *ep, struct access_data *ad)
 {
+	struct symbol *ctype = ad->result_type;
 	pseudo_t new = add_load(ep, ad);
 
-	if (ad->bit_offset) {
-		pseudo_t shift = value_pseudo(ad->bit_offset);
+	if (ctype->bit_offset) {
+		pseudo_t shift = value_pseudo(ctype->bit_offset);
 		pseudo_t newval = add_binary_op(ep, ad->source_type, OP_LSR, new, shift);
 		new = newval;
 	}
-	if (ad->bit_size != type_size(ad->source_type))
+	if (ctype->bit_size != type_size(ad->source_type))
 		new = cast_pseudo(ep, new, ad->source_type, ad->result_type);
 	return new;
 }
-- 
2.12.0

[PATCH 3/4] add test case for linearize_initializer() of bitfields

[Luc Van Oostenryck]

In linearize_initializer(), 'ad->bit_size' & 'ad->bit_offset' were
never set, making the correct initialization impossible (a bit_size of
zero being especially bad, resulting in a mask of -1 instead of 0).

This is now fixed since 'bit_size' & 'bit_offset' are taken directly
from 'result_type'.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 validation/linear/bitfield-init-mask.c | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)
 create mode 100644 validation/linear/bitfield-init-mask.c

diff --git a/validation/linear/bitfield-init-mask.c b/validation/linear/bitfield-init-mask.c
new file mode 100644
index 000000000..94afa400c
--- /dev/null
+++ b/validation/linear/bitfield-init-mask.c
@@ -0,0 +1,27 @@
+struct bfu {
+	unsigned int a:11;
+	unsigned int f:9;
+	unsigned int z:3;
+};
+
+struct bfu bfu_init_00_11(int a)
+{
+	struct bfu bfu = { .a = a, };
+	return bfu;
+}
+
+struct bfu bfu_init_20_23(int a)
+{
+	struct bfu bfu = { .z = a, };
+	return bfu;
+}
+
+/*
+ * check-name: bitfield initializer mask
+ * check-command: test-linearize -fdump-linearize=only -Wno-decl $file
+ * check-output-ignore
+ *
+ * check-output-contains: and\\..*fffff800\$
+ * check-output-contains: shl\\..* \\$20
+ * check-output-contains: and\\..*ff8fffff\$
+ */
-- 
2.12.0

[PATCH 4/4] fix implicit zero initializer.

[Luc Van Oostenryck]

The C standard requires that, when initializing an aggregate, all
fieds not explicitly initialized shall be implicity zero-initialized
(more exactly "the same as objects that have static storage duration"
[6.7.9.21]).

Until now sparse didn't did this.
Fix this (when an initializer is present and the object not a scalar)
by first storing zeroes in the whole object before doing the
initialization of each fields explicitly initialized.

Note 1: the code simplify nicely when there is a single field that is
        initialized, much less so when there is several ones.
Note 2: this implicit initialization is not needed if all fields are
        explicitly initialized but is done anyway for the moment.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c                             |  11 ++++
 validation/linear/bitfield-init-zero.c  | 102 ++++++++++++++++++++++++++++++++
 validation/linear/struct-init-full.c    |  28 +++++++++
 validation/linear/struct-init-partial.c |  41 +++++++++++++
 4 files changed, 182 insertions(+)
 create mode 100644 validation/linear/bitfield-init-zero.c
 create mode 100644 validation/linear/struct-init-full.c
 create mode 100644 validation/linear/struct-init-partial.c

diff --git a/linearize.c b/linearize.c
index e9610932b..e4cbc8bd4 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1634,6 +1634,17 @@ static pseudo_t linearize_one_symbol(struct entrypoint *ep, struct symbol *sym)
 
 	sym->initialized = 1;
 	ad.address = symbol_pseudo(ep, sym);
+
+	if (sym->initializer && !is_scalar_type(sym)) {
+		// default zero initialization [6.7.9.21]
+		struct expression *expr = sym->initializer;
+		ad.pos = expr->pos;
+		ad.result_type = sym;
+		ad.source_type = base_type(sym);
+		ad.address = symbol_pseudo(ep, sym);
+		linearize_store_gen(ep, value_pseudo(0), &ad);
+	}
+
 	value = linearize_initializer(ep, sym->initializer, &ad);
 	finish_address_gen(ep, &ad);
 	return value;
diff --git a/validation/linear/bitfield-init-zero.c b/validation/linear/bitfield-init-zero.c
new file mode 100644
index 000000000..39a64345e
--- /dev/null
+++ b/validation/linear/bitfield-init-zero.c
@@ -0,0 +1,102 @@
+struct bfu {
+	unsigned int a:11;
+	unsigned int f:9;
+	unsigned int  :2;
+	unsigned int z:3;
+};
+
+struct bfu bfuu_init(unsigned int a)
+{
+	struct bfu bf = { .f = a, };
+	return bf;
+}
+
+struct bfu bfus_init(int a)
+{
+	struct bfu bf = { .f = a, };
+	return bf;
+}
+
+unsigned int bfu_get0(void)
+{
+	struct bfu bf = { };
+	return bf.f;
+}
+
+
+struct bfs {
+	signed int a:11;
+	signed int f:9;
+	signed int  :2;
+	signed int z:3;
+};
+
+struct bfs bfsu_init(unsigned int a)
+{
+	struct bfs bf = { .f = a, };
+	return bf;
+}
+
+struct bfs bfss_init(int a)
+{
+	struct bfs bf = { .f = a, };
+	return bf;
+}
+
+int bfs_get0(void)
+{
+	struct bfs bf = { };
+	return bf.f;
+}
+
+/*
+ * check-name: bitfield implicit init zero
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+bfuu_init:
+.L0:
+	<entry-point>
+	cast.9      %r2 <- (32) %arg1
+	shl.32      %r4 <- %r2, $11
+	ret.32      %r4
+
+
+bfus_init:
+.L2:
+	<entry-point>
+	scast.9     %r10 <- (32) %arg1
+	shl.32      %r12 <- %r10, $11
+	ret.32      %r12
+
+
+bfu_get0:
+.L4:
+	<entry-point>
+	ret.32      $0
+
+
+bfsu_init:
+.L6:
+	<entry-point>
+	cast.9      %r23 <- (32) %arg1
+	shl.32      %r25 <- %r23, $11
+	ret.32      %r25
+
+
+bfss_init:
+.L8:
+	<entry-point>
+	scast.9     %r31 <- (32) %arg1
+	shl.32      %r33 <- %r31, $11
+	ret.32      %r33
+
+
+bfs_get0:
+.L10:
+	<entry-point>
+	ret.32      $0
+
+
+ * check-output-end
+ */
diff --git a/validation/linear/struct-init-full.c b/validation/linear/struct-init-full.c
new file mode 100644
index 000000000..f1b03db71
--- /dev/null
+++ b/validation/linear/struct-init-full.c
@@ -0,0 +1,28 @@
+struct s {
+	int a, b, c;
+};
+
+struct s s_init_all(int a)
+{
+	struct s s = { .a = a, .b = 42, .c = 123, };
+	return s;
+}
+
+/*
+ * check-name: struct implicit init zero not needed
+ * check-command: test-linearize -Wno-decl $file
+ * check-known-to-fail
+ *
+ * check-output-start
+s_init_all:
+.L4:
+	<entry-point>
+	store.32    %arg1 -> 0[s]
+	store.32    $42 -> 4[s]
+	store.32    $123 -> 8[s]
+	load.96     %r8 <- 0[s]
+	ret.96      %r8
+
+
+ * check-output-end
+ */
diff --git a/validation/linear/struct-init-partial.c b/validation/linear/struct-init-partial.c
new file mode 100644
index 000000000..1f5078bfa
--- /dev/null
+++ b/validation/linear/struct-init-partial.c
@@ -0,0 +1,41 @@
+struct s {
+	int a, b, c;
+};
+
+struct s s_init_first(int a)
+{
+	struct s s = { .a = a, };
+	return s;
+}
+
+struct s s_init_third(int a)
+{
+	struct s s = { .c = a, };
+	return s;
+}
+
+/*
+ * check-name: struct implicit init zero needed
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+s_init_first:
+.L0:
+	<entry-point>
+	store.96    $0 -> 0[s]
+	store.32    %arg1 -> 0[s]
+	load.96     %r2 <- 0[s]
+	ret.96      %r2
+
+
+s_init_third:
+.L2:
+	<entry-point>
+	store.96    $0 -> 0[s]
+	store.32    %arg1 -> 8[s]
+	load.96     %r5 <- 0[s]
+	ret.96      %r5
+
+
+ * check-output-end
+ */
-- 
2.12.0

Re: [PATCH 4/4] fix implicit zero initializer.

[Linus Torvalds]

On Thu, Apr 6, 2017 at 4:00 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> The C standard requires that, when initializing an aggregate, all
> fieds not explicitly initialized shall be implicity zero-initialized

Note the "all fields".

Which is not the same as "the whole aggregate" which is what you do.
The parts that don't have fields at all are undefined.

I think your patch is fine, and you might as well clear the whole
backing store, but I think strictly speaking you're initializing more
than what the standard says.

                Linus

Re: [PATCH 4/4] fix implicit zero initializer.

[Luc Van Oostenryck]

On Thu, Apr 06, 2017 at 04:39:53PM -0700, Linus Torvalds wrote:
> On Thu, Apr 6, 2017 at 4:00 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > The C standard requires that, when initializing an aggregate, all
> > fieds not explicitly initialized shall be implicity zero-initialized
> 
> Note the "all fields".
> 
> Which is not the same as "the whole aggregate" which is what you do.
> The parts that don't have fields at all are undefined.

Yes indeed. I didn't really think about this little subtility.

> I think your patch is fine, and you might as well clear the whole
> backing store, but I think strictly speaking you're initializing more
> than what the standard says.

Yes, absolutely.
For the moment it's quite crude but generate correct code
(unless we want to track the undefined values).
It should be smarter, though, because of these holes but also
because what I hinted in the note:
for the moment, 'struct { int a, b, c, } s = { 1, 2, 3, };'
will generate something like:
	store.96	$0 -> 0[s]
	store.32	$1 -> 0[s]
	store.32	$2 -> 4[s]
	store.32	$3 -> 8[s]
which is a bit sad.

-- Luc