[PATCH v2 0/6] fix bitfield initializers

[PATCH v2 0/6] fix bitfield initializers

[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.

Change since v1:
- fix typo in handle_switch_fdump()
- also remove struct access_data:alignment
- also remove struct access_data:origval

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

Luc Van Oostenryck (6):
  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.
  remove alignment from struct access_data
  remove origval from struct access_data

 lib.c                                   |  23 +++++++
 lib.h                                   |   2 +
 linearize.c                             |  46 +++++++++-----
 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, 260 insertions(+), 16 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

-- 
2.12.0

[PATCH v2 1/6] 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       | 23 +++++++++++++++++++++++
 lib.h       |  2 ++
 linearize.c |  6 ++++++
 sparse.1    |  7 +++++++
 4 files changed, 38 insertions(+)

diff --git a/lib.c b/lib.c
index 272d2c88a..ca8ff2d17 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,33 @@ 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)) {
+		arg += 9;
+		if (*arg == '\0')
+			fdump_linearize = 1;
+		else if (!strcmp(arg, "=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

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

[Luc Van Oostenryck]

In struct access_data, the fields: 'bit_offset', 'bit_size'
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 'bit_size'
      is never set for initializers. The bug could be solved by
      initializing 'bit_size' & 'bit_offset' but it is 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 | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

diff --git a/linearize.c b/linearize.c
index 61c804333..5c273a91d 100644
--- a/linearize.c
+++ b/linearize.c
@@ -845,7 +845,6 @@ struct access_data {
 	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
 	struct position pos;
 };
 
@@ -898,9 +897,7 @@ 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 +945,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 +996,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 v2 3/6] 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 v2 4/6] 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: this patch initialize the *whole* aggregate while the
	standard only requires that existing fields are initialized.
	Thanks to Linus to notice this.
Note 2: this implicit initialization is not needed if all fields are
        explicitly initialized but is done anyway, for the moment.
Note 3: the code simplify nicely when there is a single field that is
        initialized, much less so when there is several ones.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c                             |  15 +++++
 validation/linear/bitfield-init-zero.c  | 102 ++++++++++++++++++++++++++++++++
 validation/linear/struct-init-full.c    |  28 +++++++++
 validation/linear/struct-init-partial.c |  41 +++++++++++++
 4 files changed, 186 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 5c273a91d..f628f5a74 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1635,6 +1635,21 @@ 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]
+		// FIXME: this init the whole aggregate while
+		// only the existing fields need to be initialized.
+		// FIXME: this init the whole aggregate even if
+		// all fields arelater  explicitely initialized.
+		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 v2 4/6] fix implicit zero initializer.

[Christopher Li]

On Sat, Apr 8, 2017 at 2:18 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> diff --git a/linearize.c b/linearize.c
> index 5c273a91d..f628f5a74 100644
> --- a/linearize.c
> +++ b/linearize.c
> @@ -1635,6 +1635,21 @@ 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]
> +               // FIXME: this init the whole aggregate while
> +               // only the existing fields need to be initialized.
> +               // FIXME: this init the whole aggregate even if
> +               // all fields arelater  explicitely initialized.

Some very minor comment. The multi-line comment should be
written in the C type. /* ... */

Chris

[PATCH v2 5/6] remove alignment from struct access_data

[Luc Van Oostenryck]

In struct access_data, the field 'alignment' is always
the one present in 'result_type' and is thus completely
redundant.

Change this by removing this field.
---
 linearize.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/linearize.c b/linearize.c
index f628f5a74..1f93da9ae 100644
--- a/linearize.c
+++ b/linearize.c
@@ -844,7 +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 offset;		// byte offset
 	struct position pos;
 };
 
@@ -897,7 +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->alignment = ctype->ctype.alignment;
 	if (expr->type == EXPR_PREOP && expr->op == '*')
 		return linearize_simple_address(ep, expr->unop, ad);
 
-- 
2.12.0

[PATCH v2 6/6] remove origval from struct access_data

[Luc Van Oostenryck]

In struct access_data, the field 'origval' seems to be a
leftower of some previous version and is set but never really used.

Change this by removing this field.
---
 linearize.c | 6 ------
 1 file changed, 6 deletions(-)

diff --git a/linearize.c b/linearize.c
index 1f93da9ae..af4c40650 100644
--- a/linearize.c
+++ b/linearize.c
@@ -843,7 +843,6 @@ struct access_data {
 	struct symbol *result_type;	// result ctype
 	struct symbol *source_type;	// source ctype
 	pseudo_t address;		// pseudo containing address ..
-	pseudo_t origval;		// pseudo for original value ..
 	unsigned int offset;		// byte offset
 	struct position pos;
 };
@@ -909,13 +908,8 @@ static pseudo_t add_load(struct entrypoint *ep, struct access_data *ad)
 	struct instruction *insn;
 	pseudo_t new;
 
-	new = ad->origval;
-	if (0 && new)
-		return new;