[PATCH v3 0/8] fix loading of partially defined bitfield

[PATCH v3 0/8] fix loading of partially defined bitfield

[Luc Van Oostenryck]

The goal of this series is to fix the problems present in sparse
when a bitfield in an uninitialized automatic variable is first
set then read-back.

In this case the bitfield itself is initialized but not the
remaining of the structure/word and sparse was not smart
enough to handle it.

It will also solve most infinite loops that can happen
when processing undefined vars.


Changes since v1:
- use the hack from March to work-around the problem 
  with undefined vars.
- add the missing simplifications to make the
  store-and-load-back of a bitfield almost a no-op
  as it should be.

Change since v2:
- in patch 7, '-1' really meant 'all ones' but only for the
  size of the word, not bigger. Thanks to Linus for noticing it.
- add a note in patch 1 about the infinite loops.


The series is also available in the git repository at:
  git://github.com/lucvoo/sparse.git fix-loading-partialy-defined-bitfields-v3

----------------------------------------------------------------
Luc Van Oostenryck (8):
      Remove single-store shortcut
      new helper: def_opcode()
      reuse nbr_pseudo_users()
      change the masking when loading bitfields
      simplify ((A & M') | B ) & M when M' & M == 0
      transform (A & M) >> S to (A >> S) & (M >> S)
      transform (A << S) >> S into A & (-1 >> S)
      fix: cast of OP_AND only valid if it's an OP_CAST

 flow.c                                 |  39 +-----------
 linearize.c                            |  15 +++--
 linearize.h                            |   5 ++
 simplify.c                             | 109 ++++++++++++++++++++++++++++++---
 unssa.c                                |   5 --
 validation/bitfield-size.c             |   4 +-
 validation/optim/store-load-bitfield.c |  66 ++++++++++++++++++++
 7 files changed, 183 insertions(+), 60 deletions(-)
 create mode 100644 validation/optim/store-load-bitfield.c

[PATCH v3 1/8] Remove single-store shortcut

[Luc Van Oostenryck]

Current sparse code doesn't handle very gracefully
code with undefined pseudos. These can occurs, of
course because the dev has not initialize them,
maybe by error, but they can also occurs when they
are only set (and used) in a single path or even worse,
hen initiializing a bitfield.

The origin of the problem is the single store shortcut
in simplify_one_symbol() which doesn't take in account
the (absence of) dominance when loads exist without
stores.

Fix this by removing this single-store shortcut and leave
all the work for the general case which handle this
situation quite well (and/but set those variables to 0).

Warning: this change impact the performance.

Note: this will also solve most infinite loops that can
      happen when processing undefined vars.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c | 39 ++-------------------------------------
 1 file changed, 2 insertions(+), 37 deletions(-)

diff --git a/flow.c b/flow.c
index 6cac21b24..6b2c879a8 100644
--- a/flow.c
+++ b/flow.c
@@ -650,11 +650,10 @@ void check_access(struct instruction *insn)
 
 static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 {
-	pseudo_t pseudo, src;
+	pseudo_t pseudo;
 	struct pseudo_user *pu;
-	struct instruction *def;
 	unsigned long mod;
-	int all, stores, complex;
+	int all;
 
 	/* Never used as a symbol? */
 	pseudo = sym->pseudo;
@@ -670,17 +669,12 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 	if (mod)
 		goto external_visibility;
 
-	def = NULL;
-	stores = 0;
-	complex = 0;
 	FOR_EACH_PTR(pseudo->users, pu) {
 		/* We know that the symbol-pseudo use is the "src" in the instruction */
 		struct instruction *insn = pu->insn;
 
 		switch (insn->opcode) {
 		case OP_STORE:
-			stores++;
-			def = insn;
 			break;
 		case OP_LOAD:
 			break;
@@ -697,37 +691,8 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 		default:
 			warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident));
 		}
-		complex |= insn->offset;
 	} END_FOR_EACH_PTR(pu);
 
-	if (complex)
-		goto complex_def;
-	if (stores > 1)
-		goto multi_def;
-
-	/*
-	 * Goodie, we have a single store (if even that) in the whole
-	 * thing. Replace all loads with moves from the pseudo,
-	 * replace the store with a def.
-	 */
-	src = VOID;
-	if (def)
-		src = def->target;
-
-	FOR_EACH_PTR(pseudo->users, pu) {
-		struct instruction *insn = pu->insn;
-		if (insn->opcode == OP_LOAD) {
-			check_access(insn);
-			convert_load_instruction(insn, src);
-		}
-	} END_FOR_EACH_PTR(pu);
-
-	/* Turn the store into a no-op */
-	kill_store(def);
-	return;

[PATCH v3 2/8] new helper: def_opcode()

[Luc Van Oostenryck]

Getting the opcode corresponding to the instruction defining
a pseudo if the psedudo has such and instruction (PSEUDO_REG)
is an common operation in the simplification phase.

Use an helper to make the code a bit easier to read.

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

diff --git a/simplify.c b/simplify.c
index 2bc86f53e..d9528de43 100644
--- a/simplify.c
+++ b/simplify.c
@@ -352,6 +352,13 @@ static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 	return REPEAT_CSE;
 }
 
+static inline int def_opcode(pseudo_t p)
+{
+	if (p->type != PSEUDO_REG)
+		return -1;
+	return p->def->opcode;
+}
+
 static unsigned int value_size(long long value)
 {
 	value >>= 8;
@@ -376,9 +383,9 @@ static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
 {
 	unsigned int size = insn->size;
 
-	if (pseudo->type == PSEUDO_REG) {
+	if (def_opcode(pseudo) == OP_CAST) {
 		struct instruction *src = pseudo->def;
-		if (src && src->opcode == OP_CAST && src->orig_type) {
+		if (src->orig_type) {
 			unsigned int orig_size = src->orig_type->bit_size;
 			if (orig_size < size)
 				size = orig_size;
@@ -786,13 +793,11 @@ static int simplify_associative_binop(struct instruction *insn)
 
 	if (!simple_pseudo(insn->src2))
 		return 0;
-	if (pseudo->type != PSEUDO_REG)
+	if (def_opcode(pseudo) != insn->opcode)
 		return 0;
 	def = pseudo->def;
 	if (def == insn)
 		return 0;
-	if (def->opcode != insn->opcode)
-		return 0;
 	if (!simple_pseudo(def->src2))
 		return 0;
 	if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
@@ -957,9 +962,9 @@ static int simplify_cast(struct instruction *insn)
 	}
 
 	/* A cast of a "and" might be a no-op.. */
-	if (src->type == PSEUDO_REG) {
+	if (def_opcode(src) == OP_AND) {
 		struct instruction *def = src->def;
-		if (def->opcode == OP_AND && def->size >= size) {
+		if (def->size >= size) {
 			pseudo_t val = def->src2;
 			if (val->type == PSEUDO_VAL) {
 				unsigned long long value = val->value;
-- 
2.13.2

[PATCH v3 3/8] reuse nbr_pseudo_users()

[Luc Van Oostenryck]

This small helper was used in unssa.c but is helpfull elsewhere too.

Change it to an inline function and move it to one of the header.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.h | 5 +++++
 simplify.c  | 2 +-
 unssa.c     | 5 -----
 3 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/linearize.h b/linearize.h
index bac82d7ff..7f2e976e7 100644
--- a/linearize.h
+++ b/linearize.h
@@ -301,6 +301,11 @@ static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, ps
 	return user;
 }
 
+static inline int nbr_pseudo_users(pseudo_t p)
+{
+	return ptr_list_size((struct ptr_list *)p->users);
+}
+
 static inline void use_pseudo(struct instruction *insn, pseudo_t p, pseudo_t *pp)
 {
 	*pp = p;
diff --git a/simplify.c b/simplify.c
index d9528de43..8b63bcaff 100644
--- a/simplify.c
+++ b/simplify.c
@@ -800,7 +800,7 @@ static int simplify_associative_binop(struct instruction *insn)
 		return 0;
 	if (!simple_pseudo(def->src2))
 		return 0;
-	if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
+	if (nbr_pseudo_users(def->target) != 1)
 		return 0;
 	switch_pseudo(def, &def->src1, insn, &insn->src2);
 	return REPEAT_CSE;
diff --git a/unssa.c b/unssa.c
index e7c9154d5..736474b90 100644
--- a/unssa.c
+++ b/unssa.c
@@ -34,11 +34,6 @@
 #include <assert.h>
 
 
-static inline int nbr_pseudo_users(pseudo_t p)
-{
-	return ptr_list_size((struct ptr_list *)p->users);
-}

[PATCH v3 4/8] change the masking when loading bitfields

[Luc Van Oostenryck]

To make some simplification easier, change the way the masking
is done when loading bitfields.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c                | 15 +++++++++------
 validation/bitfield-size.c |  6 ++++--
 2 files changed, 13 insertions(+), 8 deletions(-)

diff --git a/linearize.c b/linearize.c
index ba76397ea..f833fd8d9 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1000,14 +1000,17 @@ 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);
+	unsigned int off = ctype->bit_offset;
+	unsigned int siz = ctype->bit_size;
 
-	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 (siz != type_size(ad->source_type)) {
+		pseudo_t mask = value_pseudo(((1ULL << siz) - 1) << off);
+		new = add_binary_op(ep, ad->source_type, OP_AND, new, mask);
+	}
+	if (off) {
+		pseudo_t shift = value_pseudo(off);
+		new = add_binary_op(ep, ad->source_type, OP_LSR, new, shift);
 	}
-	if (ctype->bit_size != type_size(ad->source_type))
-		new = cast_pseudo(ep, new, ad->source_type, ad->result_type);
 	return new;
 }
 
diff --git a/validation/bitfield-size.c b/validation/bitfield-size.c
index ce78ecf21..c8c94bb15 100644
--- a/validation/bitfield-size.c
+++ b/validation/bitfield-size.c
@@ -35,7 +35,9 @@ unsigned int get_pbfi_b(struct bfi *bf) { return bf->b; }
  * check-command: test-linearize -Wno-decl $file
  * check-output-ignore
  *
- * check-output-pattern-24-times: cast\\.
- * check-output-pattern-12-times: cast\\.4
+ * check-output-excludes: cast\\.4
+ * check-output-pattern-6-times: cast\\.
  * check-output-pattern-6-times: lsr\\..*\\$6
+ * check-output-pattern-6-times: and\\..*\\$15
+ * check-output-pattern-6-times: and\\..*\\$960
  */
-- 
2.13.2

[PATCH v3 5/8] simplify ((A & M') | B ) & M when M' & M == 0

[Luc Van Oostenryck]

This is specially usefull when A is in fact undefined.

Reported-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                             | 42 +++++++++++++++++++++-
 validation/optim/store-load-bitfield.c | 66 ++++++++++++++++++++++++++++++++++
 2 files changed, 107 insertions(+), 1 deletion(-)
 create mode 100644 validation/optim/store-load-bitfield.c

diff --git a/simplify.c b/simplify.c
index 8b63bcaff..9893613da 100644
--- a/simplify.c
+++ b/simplify.c
@@ -502,6 +502,46 @@ static int simplify_seteq_setne(struct instruction *insn, long long value)
 	}
 }
 
+static int simplify_and_or_mask(struct instruction *insn, pseudo_t and, pseudo_t other, unsigned long long mask)
+{
+	struct instruction *def = and->def;
+	pseudo_t old;
+
+	if (!constant(def->src2))
+		return 0;
+	if (def->src2->value & mask)
+		return 0;
+	old = insn->src1;
+	use_pseudo(insn, other, &insn->src1);
+	remove_usage(old, &insn->src1);
+	return REPEAT_CSE;
+}
+
+static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
+{
+	struct instruction *left;
+	pseudo_t src1, src2;
+
+	switch (def_opcode(insn->src1)) {
+	case OP_OR:
+		// Let's handle ((A & M') | B ) & M
+		// or           (B | (A & M')) & M
+		// when M' & M == 0
+		left = insn->src1->def;
+		src1 = left->src1;
+		src2 = left->src2;
+		if (def_opcode(src1) == OP_AND)
+			return simplify_and_or_mask(insn, src1, src2, mask);
+		if (def_opcode(src2) == OP_AND)
+			return simplify_and_or_mask(insn, src2, src1, mask);
+		break;
+
+	default:
+		break;
+	}
+	return 0;
+}
+
 static int simplify_constant_rightside(struct instruction *insn)
 {
 	long long value = insn->src2->value;
@@ -546,7 +586,7 @@ static int simplify_constant_rightside(struct instruction *insn)
 	case OP_AND:
 		if (!value)
 			return replace_with_pseudo(insn, insn->src2);
-		return 0;
+		return simplify_constant_mask(insn, value);
 
 	case OP_SET_NE:
 	case OP_SET_EQ:
diff --git a/validation/optim/store-load-bitfield.c b/validation/optim/store-load-bitfield.c
new file mode 100644
index 000000000..b74022602
--- /dev/null
+++ b/validation/optim/store-load-bitfield.c
@@ -0,0 +1,66 @@
+int ufoo(int a)
+{
+	struct u {
+		unsigned int :2;
+		unsigned int a:3;
+	} bf;
+
+	bf.a = a;
+	return bf.a;
+}
+
+int sfoo(int a)
+{
+	struct s {
+		signed int :2;
+		signed int a:3;
+	} bf;
+
+	bf.a = a;
+	return bf.a;
+}
+
+int xfoo(int a)
+{
+	struct x {
+		int :2;
+		int a:3;	// unsigned !
+	} bf;
+
+	bf.a = a;
+	return bf.a;
+}
+
+
+/*
+ * check-name: optim store/load bitfields
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+ufoo:
+.L0:
+	<entry-point>
+	scast.3     %r2 <- (32) %arg1
+	and.32      %r9 <- %r2, $7
+	ret.32      %r9
+
+
+sfoo:
+.L2:
+	<entry-point>
+	scast.3     %r13 <- (32) %arg1
+	and.32      %r20 <- %r13, $7
+	scast.32    %r21 <- (3) %r20
+	ret.32      %r21
+
+
+xfoo:
+.L4:
+	<entry-point>
+	scast.3     %r24 <- (32) %arg1
+	and.32      %r31 <- %r24, $7
+	ret.32      %r31
+
+
+ * check-output-end
+ */
-- 
2.13.2

[PATCH v3 6/8] transform (A & M) >> S to (A >> S) & (M >> S)

[Luc Van Oostenryck]

This is especially usefull when simplifying code
accessing bitfields.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                 | 29 ++++++++++++++++++++++++++++-
 validation/bitfield-size.c |  4 +---
 2 files changed, 29 insertions(+), 4 deletions(-)

diff --git a/simplify.c b/simplify.c
index 9893613da..f1a898700 100644
--- a/simplify.c
+++ b/simplify.c
@@ -412,6 +412,32 @@ static int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long val
 	return 0;
 }
 
+static int simplify_lsr(struct instruction *insn, pseudo_t pseudo, long long value)
+{
+	struct instruction *def;
+	unsigned long long mask;
+
+	if (!value)
+		return replace_with_pseudo(insn, pseudo);
+	switch (def_opcode(insn->src1)) {
+	case OP_AND:
+		// replace (A & M) >> S
+		// by      (A >> S) & (M >> S)
+		def = insn->src1->def;
+		if (!constant(def->src2))
+			break;
+		if (nbr_pseudo_users(insn->src1) > 1)
+			break;
+		mask = def->src2->value;
+		def->opcode = OP_LSR;
+		def->src2 = value_pseudo(value);
+		insn->opcode = OP_AND;
+		insn->src2 = value_pseudo(mask >> value);
+		return REPEAT_CSE;
+	}
+	return 0;
+}
+
 static int simplify_mul_div(struct instruction *insn, long long value)
 {
 	unsigned long long sbit = 1ULL << (insn->size - 1);
@@ -562,13 +588,14 @@ static int simplify_constant_rightside(struct instruction *insn)
 	case OP_ADD:
 	case OP_OR: case OP_XOR:
 	case OP_SHL:
-	case OP_LSR:
 	case_neutral_zero:
 		if (!value)
 			return replace_with_pseudo(insn, insn->src1);
 		return 0;
 	case OP_ASR:
 		return simplify_asr(insn, insn->src1, value);
+	case OP_LSR:
+		return simplify_lsr(insn, insn->src1, value);
 
 	case OP_MODU: case OP_MODS:
 		if (value == 1)
diff --git a/validation/bitfield-size.c b/validation/bitfield-size.c
index c8c94bb15..34400479a 100644
--- a/validation/bitfield-size.c
+++ b/validation/bitfield-size.c
@@ -36,8 +36,6 @@ unsigned int get_pbfi_b(struct bfi *bf) { return bf->b; }
  * check-output-ignore
  *
  * check-output-excludes: cast\\.4
- * check-output-pattern-6-times: cast\\.
  * check-output-pattern-6-times: lsr\\..*\\$6
- * check-output-pattern-6-times: and\\..*\\$15
- * check-output-pattern-6-times: and\\..*\\$960
+ * check-output-pattern-12-times: and\\..*\\$15
  */
-- 
2.13.2

[PATCH v3 7/8] transform (A << S) >> S into A & (-1 >> S)

[Luc Van Oostenryck]

More exactly, transform it into:
	A & (Mask(size) >> S)
which is equivalent to:
	A & Mask(size - S)
where Mask(X) is ((1 << X) - 1)

This transformation is especially usefull when simplifying code
accessing bitfields or for other masking manipulations.

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

diff --git a/simplify.c b/simplify.c
index f1a898700..23cdd19ae 100644
--- a/simplify.c
+++ b/simplify.c
@@ -416,6 +416,8 @@ static int simplify_lsr(struct instruction *insn, pseudo_t pseudo, long long val
 {
 	struct instruction *def;
 	unsigned long long mask;
+	unsigned int width;
+	pseudo_t old;
 
 	if (!value)
 		return replace_with_pseudo(insn, pseudo);
@@ -434,6 +436,21 @@ static int simplify_lsr(struct instruction *insn, pseudo_t pseudo, long long val
 		insn->opcode = OP_AND;
 		insn->src2 = value_pseudo(mask >> value);
 		return REPEAT_CSE;
+	case OP_SHL:
+		// replace (A << S) >> S
+		// by      A & (Mask(size) >> S)
+		def = insn->src1->def;
+		if (!constant(def->src2))
+			break;
+		if (def->src2->value != value)
+			break;
+		width = insn->size - value;
+		insn->src2 = value_pseudo((1ULL << width) - 1);
+		insn->opcode = OP_AND;
+		old = insn->src1;
+		use_pseudo(insn, def->src1, &insn->src1);
+		remove_usage(old, &insn->src1);
+		return REPEAT_CSE;
 	}
 	return 0;
 }
-- 
2.13.2

[PATCH v3 8/8] fix: cast of OP_AND only valid if it's an OP_CAST

[Luc Van Oostenryck]

A cast of an OP_AND can be simplified away if the mask
already 'cover' the value.
However this cannot be done if the cast is in fact
a sign-extension.

Fix this by adding the appropriate check of OP_CAST vs. OP_SCAST

Fixes: caeaf72d34d1e91aaea7340241232d1d877907b7
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 23cdd19ae..daf91d82b 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1046,7 +1046,7 @@ static int simplify_cast(struct instruction *insn)
 	}
 
 	/* A cast of a "and" might be a no-op.. */
-	if (def_opcode(src) == OP_AND) {
+	if (insn->opcode == OP_CAST && def_opcode(src) == OP_AND) {
 		struct instruction *def = src->def;
 		if (def->size >= size) {
 			pseudo_t val = def->src2;
-- 
2.13.2

Re: [PATCH v3 0/8] fix loading of partially defined bitfield

[Christopher Li]

On Tue, Aug 8, 2017 at 7:06 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> The goal of this series is to fix the problems present in sparse
> when a bitfield in an uninitialized automatic variable is first
> set then read-back.

Haven't have a chance to take a look tonight.

Will get back to you tomorrow.

Chris

[PATCH v4 0/9] fix loading of partially defined bitfield

[Luc Van Oostenryck]

The goal of this series is to fix the problems present in sparse
when a bitfield in an uninitialized automatic variable is first
set then read-back.

In this case the bitfield itself is initialized but not the
remaining of the structure/word and sparse was not smart
enough to handle it.

It will also avoid internal infinite loops occuring when
processing undefined vars present during the SSA construction.


Changes since v1:
- use the hack from March to work-around the problem
  with undefined vars.
- add the missing simplifications to make the
  store-and-load-back of a bitfield almost a no-op
  as it should be.

Change since v2:
- in patch 7, '-1' really meant 'all ones' but only for the
  size of the word, not bigger. Thanks to Linus for noticing it.
- add a note in patch 1 about the infinite loops.

Change since v3:
- add timeout support in the testsuite
- add a testcase for infinite loop
- improve some commit messages

----------------------------------------------------------------

The series is also available in the git repository at:

  git://github.com/lucvoo/sparse.git fix-loading-partialy-defined-bitfields-v4


Luc Van Oostenryck (9):
      testsuite: add support for commands with timeout
      Remove single-store shortcut
      new helper: def_opcode()
      reuse nbr_pseudo_users()
      change the masking when loading bitfields
      simplify ((A & M') | B ) & M when M' & M == 0
      transform (A & M) >> S to (A >> S) & (M >> S)
      transform (A << S) >> S into A & (-1 >> S)
      fix: cast of OP_AND only valid if it's an OP_CAST

 Documentation/test-suite               |   4 ++
 flow.c                                 |  39 +-----------
 linearize.c                            |  15 +++--
 linearize.h                            |   5 ++
 simplify.c                             | 109 ++++++++++++++++++++++++++++++---
 unssa.c                                |   5 --
 validation/bitfield-size.c             |   4 +-
 validation/infinite-loop0.c            |  11 ++++
 validation/optim/store-load-bitfield.c |  66 ++++++++++++++++++++
 validation/test-suite                  |   7 +++
 10 files changed, 205 insertions(+), 60 deletions(-)
 create mode 100644 validation/infinite-loop0.c
 create mode 100644 validation/optim/store-load-bitfield.c

[PATCH v4 1/9] testsuite: add support for commands with timeout

[Luc Van Oostenryck]

Tests taking a huge or infinite amout of time is
a problem for the testsuite. Furthermore, it's most
often the sign of a problem somewhere.

Fix this by adding some support to use an optional
timeout for each testcase command.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 Documentation/test-suite    |  4 ++++
 validation/infinite-loop0.c | 12 ++++++++++++
 validation/test-suite       |  7 +++++++
 3 files changed, 23 insertions(+)
 create mode 100644 validation/infinite-loop0.c

diff --git a/Documentation/test-suite b/Documentation/test-suite
index 2e786bbf3..a288c81a5 100644
--- a/Documentation/test-suite
+++ b/Documentation/test-suite
@@ -25,6 +25,10 @@ check-command: (optional)
 check-exit-value: (optional)
 	The expected exit value of check-command. It defaults to 0.
 
+check-timeout: (optional)
+	The maximum expected duration of check-command, in seconds.
+	It defaults to 1.
+
 check-output-start / check-output-end (optional)
 	The expected output (stdout and stderr) of check-command lies between
 	those two tags. It defaults to no output.
diff --git a/validation/infinite-loop0.c b/validation/infinite-loop0.c
new file mode 100644
index 000000000..a28492307
--- /dev/null
+++ b/validation/infinite-loop0.c
@@ -0,0 +1,12 @@
+void foo(void)
+{
+        int a = a || 0;
+        if (a) ;
+}
+
+/*
+ * check-name: internal infinite loop (0)
+ * check-command: sparse -Wno-decl $file
+ * check-timeout:
+ * check-known-to-fail
+ */
diff --git a/validation/test-suite b/validation/test-suite
index 3056fce90..cf151a361 100755
--- a/validation/test-suite
+++ b/validation/test-suite
@@ -39,6 +39,7 @@ get_tag_value()
 	check_name=""
 	check_command="$default_cmd"
 	check_exit_value=0
+	check_timeout=0
 	check_known_to_fail=0
 	check_error_ignore=0
 	check_output_ignore=0
@@ -56,6 +57,8 @@ get_tag_value()
 		check-name:)		check_name="$val" ;;
 		check-command:)		check_command="$val" ;;
 		check-exit-value:)	check_exit_value="$val" ;;
+		check-timeout:)		[ -z "$val" ] && val=1
+					check_timeout="$val" ;;
 		check-known-to-fail)	check_known_to_fail=1 ;;
 		check-error-ignore)	check_error_ignore=1 ;;
 		check-output-ignore)	check_output_ignore=1 ;;
@@ -211,6 +214,10 @@ do_test()
 	expected_exit_value=$check_exit_value
 	verbose "Expecting exit value: $expected_exit_value"
 
+	# do we want a timeout?
+	if [ $check_timeout -ne 0 ]; then
+		cmd="timeout -k 1s $check_timeout $cmd"
+	fi
 
 	# grab the actual output & exit value
 	$cmd 1> $file.output.got 2> $file.error.got
-- 
2.14.0

[PATCH v4 2/9] Remove single-store shortcut

[Luc Van Oostenryck]

Current sparse code doesn't handle very gracefully
code with undefined pseudos. These can occurs, of
course because the dev has not initialize them,
maybe by error, but they can also occurs when they
are only set (and used) in a single path or even worse,
hen initiializing a bitfield.

The origin of the problem is the single store shortcut
in simplify_one_symbol() which doesn't take in account
the (absence of) dominance when loads exist without
stores.

Fix this by removing this single-store shortcut and leave
all the work for the general case which handle this
situation quite well (and/but set those variables to 0).

Warning: this change impact the performance.

Note: this patch will also avoid internal infinite loops
      occuring when processing undefined vars present
      during the SSA construction.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                      | 39 ++-------------------------------------
 validation/infinite-loop0.c |  1 -
 2 files changed, 2 insertions(+), 38 deletions(-)

diff --git a/flow.c b/flow.c
index c7161d47e..5a3d55f76 100644
--- a/flow.c
+++ b/flow.c
@@ -650,11 +650,10 @@ void check_access(struct instruction *insn)
 
 static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 {
-	pseudo_t pseudo, src;
+	pseudo_t pseudo;
 	struct pseudo_user *pu;
-	struct instruction *def;
 	unsigned long mod;
-	int all, stores, complex;
+	int all;
 
 	/* Never used as a symbol? */
 	pseudo = sym->pseudo;
@@ -670,17 +669,12 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 	if (mod)
 		goto external_visibility;
 
-	def = NULL;
-	stores = 0;
-	complex = 0;
 	FOR_EACH_PTR(pseudo->users, pu) {
 		/* We know that the symbol-pseudo use is the "src" in the instruction */
 		struct instruction *insn = pu->insn;
 
 		switch (insn->opcode) {
 		case OP_STORE:
-			stores++;
-			def = insn;
 			break;
 		case OP_LOAD:
 			break;
@@ -697,37 +691,8 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
 		default:
 			warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident));
 		}
-		complex |= insn->offset;
 	} END_FOR_EACH_PTR(pu);
 
-	if (complex)
-		goto complex_def;
-	if (stores > 1)
-		goto multi_def;
-
-	/*
-	 * Goodie, we have a single store (if even that) in the whole
-	 * thing. Replace all loads with moves from the pseudo,
-	 * replace the store with a def.
-	 */
-	src = VOID;
-	if (def)
-		src = def->target;
-
-	FOR_EACH_PTR(pseudo->users, pu) {
-		struct instruction *insn = pu->insn;
-		if (insn->opcode == OP_LOAD) {
-			check_access(insn);
-			convert_load_instruction(insn, src);
-		}
-	} END_FOR_EACH_PTR(pu);
-
-	/* Turn the store into a no-op */
-	kill_store(def);
-	return;

Re: [PATCH v4 2/9] Remove single-store shortcut

[Dibyendu Majumdar]

Hi Luc,

This this change independent of the rest of changes in the series -
i.e. can I just apply this change?

Regards
Dibyendu

On 9 August 2017 at 20:37, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Current sparse code doesn't handle very gracefully
> code with undefined pseudos. These can occurs, of
> course because the dev has not initialize them,
> maybe by error, but they can also occurs when they
> are only set (and used) in a single path or even worse,
> hen initiializing a bitfield.
>
> The origin of the problem is the single store shortcut
> in simplify_one_symbol() which doesn't take in account
> the (absence of) dominance when loads exist without
> stores.
>
> Fix this by removing this single-store shortcut and leave
> all the work for the general case which handle this
> situation quite well (and/but set those variables to 0).
>
> Warning: this change impact the performance.
>
> Note: this patch will also avoid internal infinite loops
>       occuring when processing undefined vars present
>       during the SSA construction.
>
> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> ---
>  flow.c                      | 39 ++-------------------------------------
>  validation/infinite-loop0.c |  1 -
>  2 files changed, 2 insertions(+), 38 deletions(-)
>
> diff --git a/flow.c b/flow.c
> index c7161d47e..5a3d55f76 100644
> --- a/flow.c
> +++ b/flow.c
> @@ -650,11 +650,10 @@ void check_access(struct instruction *insn)
>
>  static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
>  {
> -       pseudo_t pseudo, src;
> +       pseudo_t pseudo;
>         struct pseudo_user *pu;
> -       struct instruction *def;
>         unsigned long mod;
> -       int all, stores, complex;
> +       int all;
>
>         /* Never used as a symbol? */
>         pseudo = sym->pseudo;
> @@ -670,17 +669,12 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
>         if (mod)
>                 goto external_visibility;
>
> -       def = NULL;
> -       stores = 0;
> -       complex = 0;
>         FOR_EACH_PTR(pseudo->users, pu) {
>                 /* We know that the symbol-pseudo use is the "src" in the instruction */
>                 struct instruction *insn = pu->insn;
>
>                 switch (insn->opcode) {
>                 case OP_STORE:
> -                       stores++;
> -                       def = insn;
>                         break;
>                 case OP_LOAD:
>                         break;
> @@ -697,37 +691,8 @@ static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
>                 default:
>                         warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident));
>                 }
> -               complex |= insn->offset;
>         } END_FOR_EACH_PTR(pu);
>
> -       if (complex)
> -               goto complex_def;
> -       if (stores > 1)
> -               goto multi_def;
> -
> -       /*
> -        * Goodie, we have a single store (if even that) in the whole
> -        * thing. Replace all loads with moves from the pseudo,
> -        * replace the store with a def.
> -        */
> -       src = VOID;
> -       if (def)
> -               src = def->target;
> -
> -       FOR_EACH_PTR(pseudo->users, pu) {
> -               struct instruction *insn = pu->insn;
> -               if (insn->opcode == OP_LOAD) {
> -                       check_access(insn);
> -                       convert_load_instruction(insn, src);
> -               }
> -       } END_FOR_EACH_PTR(pu);
> -
> -       /* Turn the store into a no-op */
> -       kill_store(def);
> -       return;
> -
> -multi_def:
> -complex_def:
>  external_visibility:
>         all = 1;
>         FOR_EACH_PTR_REVERSE(pseudo->users, pu) {
> diff --git a/validation/infinite-loop0.c b/validation/infinite-loop0.c
> index a28492307..0e3e3805c 100644
> --- a/validation/infinite-loop0.c
> +++ b/validation/infinite-loop0.c
> @@ -8,5 +8,4 @@ void foo(void)
>   * check-name: internal infinite loop (0)
>   * check-command: sparse -Wno-decl $file
>   * check-timeout:
> - * check-known-to-fail
>   */
> --
> 2.14.0
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v4 2/9] Remove single-store shortcut

[Luc Van Oostenryck]

On Wed, Aug 9, 2017 at 9:47 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
> Hi Luc,
>
> This this change independent of the rest of changes in the series -
> i.e. can I just apply this change?

Absolutely.

-- Luc

Re: [PATCH v4 2/9] Remove single-store shortcut

[Dibyendu Majumdar]

Hi Luc,

On 9 August 2017 at 21:02, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Wed, Aug 9, 2017 at 9:47 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>> Hi Luc,
>>
>> This this change independent of the rest of changes in the series -
>> i.e. can I just apply this change?
>
> Absolutely.
>

Thank you. I am trying out this change as I am hoping it will help
avoid the incorrect simplifications we saw in some cases. So far my
findings are:

It solves the bit field access issue: i.e. this test works
(https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/set1/onebit.c).

But it doesn't help with the issue with pseudos defined in one branch
of the code (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug.c).

Is there another fix / patch that you made to overcome above issue or
would you expect both issues to be fixed by this change?

I will run my test cases with this change and report if anything breaks.

Regards
Dibyendu

Re: [PATCH v4 2/9] Remove single-store shortcut

[Luc Van Oostenryck]

On Thu, Aug 10, 2017 at 12:23 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> Thank you. I am trying out this change as I am hoping it will help
> avoid the incorrect simplifications we saw in some cases. So far my
> findings are:
>
> It solves the bit field access issue: i.e. this test works
> (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/set1/onebit.c).

Yes, it's the one I used for the patches.

> But it doesn't help with the issue with pseudos defined in one branch
> of the code (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug.c).
>
> Is there another fix / patch that you made to overcome above issue or
> would you expect both issues to be fixed by this change?

I don't know exactly what you have as problem with this other test.
I quickly looked at the output of test-linearize and I saw no problem
with self-defined pseudos. The phi-nodes are very wrong though but that's
another problem.

You may try the new SSA construction at :
   https://github.com/lucvoo/sparse/tree/sssa
It will help a lot.

But in both case, I saw that sparse-llvm crashes
(which is normal as none of the LLVM fixes are applied here).

In the coming days, I'll do a branch that aggregates all the good stuff.

But until then, can you explain exactly what is wrong with this second test?

> I will run my test cases with this change and report if anything breaks.

Thanks.
Testing in other environments, with other goals, is very useful.

-- Luc

Re: [PATCH v4 2/9] Remove single-store shortcut

[Dibyendu Majumdar]

Hi Luc,

On 10 August 2017 at 00:15, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Thu, Aug 10, 2017 at 12:23 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>
>> Thank you. I am trying out this change as I am hoping it will help
>> avoid the incorrect simplifications we saw in some cases. So far my
>> findings are:
>>
>
>> But it doesn't help with the issue with pseudos defined in one branch
>> of the code (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug.c).
>>
>> Is there another fix / patch that you made to overcome above issue or
>> would you expect both issues to be fixed by this change?
>
> I don't know exactly what you have as problem with this other test.
> I quickly looked at the output of test-linearize and I saw no problem
> with self-defined pseudos. The phi-nodes are very wrong though but that's
> another problem.
>

Yes I suppose that is what it is. LLVM complains that 'instruction
does not dominate all uses'.
The unsimplified IR works fine
(https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug.lin).
The simplified IR has an issue
(https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug_O1.lin).

> You may try the new SSA construction at :
>    https://github.com/lucvoo/sparse/tree/sssa
> It will help a lot.
>

Is that a standalone change I can apply?

> But in both case, I saw that sparse-llvm crashes
> (which is normal as none of the LLVM fixes are applied here).
>
> In the coming days, I'll do a branch that aggregates all the good stuff.
>

I think that this is a very good idea. Since the official sparse repo
is so behind - it will be good if you maintain a branch in your repo
that has all the things that you have tested thoroughly and are happy
with - this can be the "next sparse version" for testing. I would
suggest aggregating only changes that you are 100% confident about. It
will allow me (and others like me) to test the changes and report back
if any issues are found.

> But until then, can you explain exactly what is wrong with this second test?
>
>> I will run my test cases with this change and report if anything breaks.
>
> Thanks.
> Testing in other environments, with other goals, is very useful.
>

So far I haven't found any breaks which is good. I will continue
testing tomorrow.

Regards
Dibyendu

Re: [PATCH v4 2/9] Remove single-store shortcut

[Luc Van Oostenryck]

On Thu, Aug 10, 2017 at 1:32 AM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> Yes I suppose that is what it is. LLVM complains that 'instruction
> does not dominate all uses'.
> The unsimplified IR works fine
> (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug.lin).
> The simplified IR has an issue
> (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug_O1.lin).

Yes, I saw now. It's hopeless.
It's a problem with the SSA construction (happen between linearization
and simplification), basically, it puts the phi-nodes where there is a load
but it's often too late, they need to be put where paths join.

>> You may try the new SSA construction at :
>>    https://github.com/lucvoo/sparse/tree/sssa
>> It will help a lot.
>>
>
> Is that a standalone change I can apply?

Arf ... in a sense yes but it's really a 40 patches series
(but most changes are isolated, maybe not too much work for you
I don't know).

> I think that this is a very good idea. Since the official sparse repo
> is so behind - it will be good if you maintain a branch in your repo
> that has all the things that you have tested thoroughly and are happy
> with - this can be the "next sparse version" for testing. I would
> suggest aggregating only changes that you are 100% confident about. It
> will allow me (and others like me) to test the changes and report back
> if any issues are found.

It's the idea.
Only that the 100% confident will be "confident that it won't break but
improve situations I know about".

Regards,
-- Luc

Re: [PATCH v4 2/9] Remove single-store shortcut

[Dibyendu Majumdar]

Hi Luc,

On 10 August 2017 at 00:51, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Thu, Aug 10, 2017 at 1:32 AM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>
>> Yes I suppose that is what it is. LLVM complains that 'instruction
>> does not dominate all uses'.
>> The unsimplified IR works fine
>> (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug.lin).
>> The simplified IR has an issue
>> (https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/bugs/simplifybug_O1.lin).
>
> Yes, I saw now. It's hopeless.
> It's a problem with the SSA construction (happen between linearization
> and simplification), basically, it puts the phi-nodes where there is a load
> but it's often too late, they need to be put where paths join.
>
>>> You may try the new SSA construction at :
>>>    https://github.com/lucvoo/sparse/tree/sssa
>>> It will help a lot.
>>>
>>
>> Is that a standalone change I can apply?
>
> Arf ... in a sense yes but it's really a 40 patches series
> (but most changes are isolated, maybe not too much work for you
> I don't know).
>

I am merging the current changes in RC5 to my repository. When that is
done, I would like to try out your new SSA construction approach.
Please let me know if this is complete (i.e. functional). I had a look
at the branch above, but not all commits appeared to be related to the
SSA construction, so any pointer to the list of changes I should pick
would be very helpful.

I can test the new approach in my repository and report back.

Regards
Dibyendu

Re: [PATCH v4 2/9] Remove single-store shortcut

[Luc Van Oostenryck]

On Sat, Aug 12, 2017 at 8:51 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> ..., I would like to try out your new SSA construction approach.
> Please let me know if this is complete (i.e. functional).

It's more than simply functional, it seems to work pretty well:
- it passes the testsuite
- it doesn't crash while using it on the kernel or any of my tests
  (I have plenty of tests I can't upstream or doesn't make sense
  to be upstreamed)
- the generated code handle correctly the placement of phi-nodes
- the generated code handle correctly undefined vars/pseudos
- it's a bit faster than the current sparse and use less memory

But:
- it needs more testing
- code needs some polish here & there
- it's not a panacea for all current issues.

In my opinion, it's a HUGE step forward.

> I had a look
> at the branch above, but not all commits appeared to be related to the
> SSA construction, so any pointer to the list of changes I should pick
> would be very helpful.

True, the first commits are some small improvement, bug fixes or
even optimization fixes I need for testing during development.

Currently, I'm busy to aggregate the others changes, the LLVM ones
and friends. There are a few merge conflicts to solve but not much.
The next step will be to make the SSA more usable.

-- Luc

Re: [PATCH v4 2/9] Remove single-store shortcut

[Dibyendu Majumdar]

Hi Luc,

On 12 August 2017 at 20:28, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Sat, Aug 12, 2017 at 8:51 PM, Dibyendu Majumdar
> <mobile@majumdar.org.uk> wrote:
>>
>> ..., I would like to try out your new SSA construction approach.
>> Please let me know if this is complete (i.e. functional).
>
> It's more than simply functional, it seems to work pretty well:
> - it passes the testsuite
> - it doesn't crash while using it on the kernel or any of my tests
>   (I have plenty of tests I can't upstream or doesn't make sense
>   to be upstreamed)
> - the generated code handle correctly the placement of phi-nodes
> - the generated code handle correctly undefined vars/pseudos
> - it's a bit faster than the current sparse and use less memory
>
> But:
> - it needs more testing
> - code needs some polish here & there
> - it's not a panacea for all current issues.
>
> In my opinion, it's a HUGE step forward.
>

That sounds very good.

>> I had a look
>> at the branch above, but not all commits appeared to be related to the
>> SSA construction, so any pointer to the list of changes I should pick
>> would be very helpful.
>
> True, the first commits are some small improvement, bug fixes or
> even optimization fixes I need for testing during development.
>
> Currently, I'm busy to aggregate the others changes, the LLVM ones
> and friends. There are a few merge conflicts to solve but not much.
> The next step will be to make the SSA more usable.
>

Okay please let me know when you are ready for me to try and
incorporate this work. I will be finished merging the RC5 changes in
the next few days.

Regards
Dibyendu

Re: [PATCH v4 2/9] Remove single-store shortcut

[Luc Van Oostenryck]

On Sat, Aug 12, 2017 at 9:55 PM, Dibyendu Majumdar
<mobile@majumdar.org.uk> wrote:
>
> Okay please let me know when you are ready for me to try and
> incorporate this work. I will be finished merging the RC5 changes in
> the next few days.

I guess it will be done in a few days too.

-- Luc

[PATCH v4 3/9] new helper: def_opcode()

[Luc Van Oostenryck]

Getting the opcode corresponding to the instruction defining
a pseudo if the psedudo has such and instruction (PSEUDO_REG)
is an common operation in the simplification phase.

Use an helper to make the code a bit easier to read.

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

diff --git a/simplify.c b/simplify.c
index a141ddd43..1576a665a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -351,6 +351,13 @@ static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 	return REPEAT_CSE;
 }
 
+static inline int def_opcode(pseudo_t p)
+{
+	if (p->type != PSEUDO_REG)
+		return -1;
+	return p->def->opcode;
+}
+
 static unsigned int value_size(long long value)
 {
 	value >>= 8;
@@ -375,9 +382,9 @@ static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
 {
 	unsigned int size = insn->size;
 
-	if (pseudo->type == PSEUDO_REG) {
+	if (def_opcode(pseudo) == OP_CAST) {
 		struct instruction *src = pseudo->def;
-		if (src && src->opcode == OP_CAST && src->orig_type) {
+		if (src->orig_type) {
 			unsigned int orig_size = src->orig_type->bit_size;
 			if (orig_size < size)
 				size = orig_size;
@@ -785,13 +792,11 @@ static int simplify_associative_binop(struct instruction *insn)
 
 	if (!simple_pseudo(insn->src2))
 		return 0;
-	if (pseudo->type != PSEUDO_REG)
+	if (def_opcode(pseudo) != insn->opcode)
 		return 0;
 	def = pseudo->def;
 	if (def == insn)
 		return 0;
-	if (def->opcode != insn->opcode)
-		return 0;
 	if (!simple_pseudo(def->src2))
 		return 0;
 	if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
@@ -947,9 +952,9 @@ static int simplify_cast(struct instruction *insn)
 	}
 
 	/* A cast of a "and" might be a no-op.. */
-	if (src->type == PSEUDO_REG) {
+	if (def_opcode(src) == OP_AND) {
 		struct instruction *def = src->def;
-		if (def->opcode == OP_AND && def->size >= size) {
+		if (def->size >= size) {
 			pseudo_t val = def->src2;
 			if (val->type == PSEUDO_VAL) {
 				unsigned long long value = val->value;
-- 
2.14.0

[PATCH v4 4/9] reuse nbr_pseudo_users()

[Luc Van Oostenryck]

This small helper was used in unssa.c but is helpfull elsewhere too.

Change it to an inline function and move it to one of the header.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.h | 5 +++++
 simplify.c  | 2 +-
 unssa.c     | 5 -----
 3 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/linearize.h b/linearize.h
index bac82d7ff..7f2e976e7 100644
--- a/linearize.h
+++ b/linearize.h
@@ -301,6 +301,11 @@ static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, ps
 	return user;
 }
 
+static inline int nbr_pseudo_users(pseudo_t p)
+{
+	return ptr_list_size((struct ptr_list *)p->users);
+}
+
 static inline void use_pseudo(struct instruction *insn, pseudo_t p, pseudo_t *pp)
 {
 	*pp = p;
diff --git a/simplify.c b/simplify.c
index 1576a665a..30961cf39 100644
--- a/simplify.c
+++ b/simplify.c
@@ -799,7 +799,7 @@ static int simplify_associative_binop(struct instruction *insn)
 		return 0;
 	if (!simple_pseudo(def->src2))
 		return 0;
-	if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
+	if (nbr_pseudo_users(def->target) != 1)
 		return 0;
 	switch_pseudo(def, &def->src1, insn, &insn->src2);
 	return REPEAT_CSE;
diff --git a/unssa.c b/unssa.c
index e7c9154d5..736474b90 100644
--- a/unssa.c
+++ b/unssa.c
@@ -34,11 +34,6 @@
 #include <assert.h>
 
 
-static inline int nbr_pseudo_users(pseudo_t p)
-{
-	return ptr_list_size((struct ptr_list *)p->users);
-}

[PATCH v4 5/9] change the masking when loading bitfields

[Luc Van Oostenryck]

To make some simplification easier, change the way the masking
is done when loading bitfields.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c                | 15 +++++++++------
 validation/bitfield-size.c |  6 ++++--
 2 files changed, 13 insertions(+), 8 deletions(-)

diff --git a/linearize.c b/linearize.c
index 7313e72d8..45301f954 100644
--- a/linearize.c
+++ b/linearize.c
@@ -995,14 +995,17 @@ 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);
+	unsigned int off = ctype->bit_offset;
+	unsigned int siz = ctype->bit_size;
 
-	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 (siz != type_size(ad->source_type)) {
+		pseudo_t mask = value_pseudo(((1ULL << siz) - 1) << off);
+		new = add_binary_op(ep, ad->source_type, OP_AND, new, mask);
+	}
+	if (off) {
+		pseudo_t shift = value_pseudo(off);
+		new = add_binary_op(ep, ad->source_type, OP_LSR, new, shift);
 	}
-	if (ctype->bit_size != type_size(ad->source_type))
-		new = cast_pseudo(ep, new, ad->source_type, ad->result_type);
 	return new;
 }
 
diff --git a/validation/bitfield-size.c b/validation/bitfield-size.c
index ce78ecf21..c8c94bb15 100644
--- a/validation/bitfield-size.c
+++ b/validation/bitfield-size.c
@@ -35,7 +35,9 @@ unsigned int get_pbfi_b(struct bfi *bf) { return bf->b; }
  * check-command: test-linearize -Wno-decl $file
  * check-output-ignore
  *
- * check-output-pattern-24-times: cast\\.
- * check-output-pattern-12-times: cast\\.4
+ * check-output-excludes: cast\\.4
+ * check-output-pattern-6-times: cast\\.
  * check-output-pattern-6-times: lsr\\..*\\$6
+ * check-output-pattern-6-times: and\\..*\\$15
+ * check-output-pattern-6-times: and\\..*\\$960
  */
-- 
2.14.0

[PATCH v4 6/9] simplify ((A & M') | B ) & M when M' & M == 0

[Luc Van Oostenryck]

This is specially usefull when A is in fact undefined.

Reported-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                             | 42 +++++++++++++++++++++-
 validation/optim/store-load-bitfield.c | 66 ++++++++++++++++++++++++++++++++++
 2 files changed, 107 insertions(+), 1 deletion(-)
 create mode 100644 validation/optim/store-load-bitfield.c

diff --git a/simplify.c b/simplify.c
index 30961cf39..40d4f0068 100644
--- a/simplify.c
+++ b/simplify.c
@@ -501,6 +501,46 @@ static int simplify_seteq_setne(struct instruction *insn, long long value)
 	}
 }
 
+static int simplify_and_or_mask(struct instruction *insn, pseudo_t and, pseudo_t other, unsigned long long mask)
+{
+	struct instruction *def = and->def;
+	pseudo_t old;
+
+	if (!constant(def->src2))
+		return 0;
+	if (def->src2->value & mask)
+		return 0;
+	old = insn->src1;
+	use_pseudo(insn, other, &insn->src1);
+	remove_usage(old, &insn->src1);
+	return REPEAT_CSE;
+}
+
+static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
+{
+	struct instruction *left;
+	pseudo_t src1, src2;
+
+	switch (def_opcode(insn->src1)) {
+	case OP_OR:
+		// Let's handle ((A & M') | B ) & M
+		// or           (B | (A & M')) & M
+		// when M' & M == 0
+		left = insn->src1->def;
+		src1 = left->src1;
+		src2 = left->src2;
+		if (def_opcode(src1) == OP_AND)
+			return simplify_and_or_mask(insn, src1, src2, mask);
+		if (def_opcode(src2) == OP_AND)
+			return simplify_and_or_mask(insn, src2, src1, mask);
+		break;
+
+	default:
+		break;
+	}
+	return 0;
+}
+
 static int simplify_constant_rightside(struct instruction *insn)
 {
 	long long value = insn->src2->value;
@@ -545,7 +585,7 @@ static int simplify_constant_rightside(struct instruction *insn)
 	case OP_AND:
 		if (!value)
 			return replace_with_pseudo(insn, insn->src2);
-		return 0;
+		return simplify_constant_mask(insn, value);
 
 	case OP_SET_NE:
 	case OP_SET_EQ:
diff --git a/validation/optim/store-load-bitfield.c b/validation/optim/store-load-bitfield.c
new file mode 100644
index 000000000..b74022602
--- /dev/null
+++ b/validation/optim/store-load-bitfield.c
@@ -0,0 +1,66 @@
+int ufoo(int a)
+{
+	struct u {
+		unsigned int :2;
+		unsigned int a:3;
+	} bf;
+
+	bf.a = a;
+	return bf.a;
+}
+
+int sfoo(int a)
+{
+	struct s {
+		signed int :2;
+		signed int a:3;
+	} bf;
+
+	bf.a = a;
+	return bf.a;
+}
+
+int xfoo(int a)
+{
+	struct x {
+		int :2;
+		int a:3;	// unsigned !
+	} bf;
+
+	bf.a = a;
+	return bf.a;
+}
+
+
+/*
+ * check-name: optim store/load bitfields
+ * check-command: test-linearize -Wno-decl $file
+ *
+ * check-output-start
+ufoo:
+.L0:
+	<entry-point>
+	scast.3     %r2 <- (32) %arg1
+	and.32      %r9 <- %r2, $7
+	ret.32      %r9
+
+
+sfoo:
+.L2:
+	<entry-point>
+	scast.3     %r13 <- (32) %arg1
+	and.32      %r20 <- %r13, $7
+	scast.32    %r21 <- (3) %r20
+	ret.32      %r21
+
+
+xfoo:
+.L4:
+	<entry-point>
+	scast.3     %r24 <- (32) %arg1
+	and.32      %r31 <- %r24, $7
+	ret.32      %r31
+
+
+ * check-output-end
+ */
-- 
2.14.0

[PATCH v4 7/9] transform (A & M) >> S to (A >> S) & (M >> S)

[Luc Van Oostenryck]

This is especially usefull when simplifying code
accessing bitfields.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                 | 29 ++++++++++++++++++++++++++++-
 validation/bitfield-size.c |  4 +---
 2 files changed, 29 insertions(+), 4 deletions(-)

diff --git a/simplify.c b/simplify.c
index 40d4f0068..e8bf1c171 100644
--- a/simplify.c
+++ b/simplify.c
@@ -411,6 +411,32 @@ static int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long val
 	return 0;
 }
 
+static int simplify_lsr(struct instruction *insn, pseudo_t pseudo, long long value)
+{
+	struct instruction *def;
+	unsigned long long mask;
+
+	if (!value)
+		return replace_with_pseudo(insn, pseudo);
+	switch (def_opcode(insn->src1)) {
+	case OP_AND:
+		// replace (A & M) >> S
+		// by      (A >> S) & (M >> S)
+		def = insn->src1->def;
+		if (!constant(def->src2))
+			break;
+		if (nbr_pseudo_users(insn->src1) > 1)
+			break;
+		mask = def->src2->value;
+		def->opcode = OP_LSR;
+		def->src2 = value_pseudo(value);
+		insn->opcode = OP_AND;
+		insn->src2 = value_pseudo(mask >> value);
+		return REPEAT_CSE;
+	}
+	return 0;
+}
+
 static int simplify_mul_div(struct instruction *insn, long long value)
 {
 	unsigned long long sbit = 1ULL << (insn->size - 1);
@@ -561,13 +587,14 @@ static int simplify_constant_rightside(struct instruction *insn)
 	case OP_ADD:
 	case OP_OR: case OP_XOR:
 	case OP_SHL:
-	case OP_LSR:
 	case_neutral_zero:
 		if (!value)
 			return replace_with_pseudo(insn, insn->src1);
 		return 0;
 	case OP_ASR:
 		return simplify_asr(insn, insn->src1, value);
+	case OP_LSR:
+		return simplify_lsr(insn, insn->src1, value);
 
 	case OP_MODU: case OP_MODS:
 		if (value == 1)
diff --git a/validation/bitfield-size.c b/validation/bitfield-size.c
index c8c94bb15..34400479a 100644
--- a/validation/bitfield-size.c
+++ b/validation/bitfield-size.c
@@ -36,8 +36,6 @@ unsigned int get_pbfi_b(struct bfi *bf) { return bf->b; }
  * check-output-ignore
  *
  * check-output-excludes: cast\\.4
- * check-output-pattern-6-times: cast\\.
  * check-output-pattern-6-times: lsr\\..*\\$6
- * check-output-pattern-6-times: and\\..*\\$15
- * check-output-pattern-6-times: and\\..*\\$960
+ * check-output-pattern-12-times: and\\..*\\$15
  */
-- 
2.14.0

Re: [PATCH v4 7/9] transform (A & M) >> S to (A >> S) & (M >> S)

[Christopher Li]

On Wed, Aug 9, 2017 at 3:38 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> This is especially usefull when simplifying code
> accessing bitfields.
>
> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> ---
>  simplify.c                 | 29 ++++++++++++++++++++++++++++-
>  validation/bitfield-size.c |  4 +---
>  2 files changed, 29 insertions(+), 4 deletions(-)
>
> diff --git a/simplify.c b/simplify.c
> index 40d4f0068..e8bf1c171 100644
> --- a/simplify.c
> +++ b/simplify.c
> @@ -411,6 +411,32 @@ static int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long val
>         return 0;
>  }
>
> +static int simplify_lsr(struct instruction *insn, pseudo_t pseudo, long long value)
> +{
> +       struct instruction *def;
> +       unsigned long long mask;
> +
> +       if (!value)
> +               return replace_with_pseudo(insn, pseudo);
> +       switch (def_opcode(insn->src1)) {
> +       case OP_AND:
> +               // replace (A & M) >> S
> +               // by      (A >> S) & (M >> S)

A little bit suggestion base on my previous reading and question ask on
this. When I first read the comment without reading the code, then I would
wondering why (A>>S) & (M>>S) is simpler. The following code actually
explain the constant mask very well. So the comment best understand if
the code was read. Adding some comment on M is constant will help a
lot in the comment.

Not a reason to object the patch of course. Just suggestions.

Chris

Re: [PATCH v4 7/9] transform (A & M) >> S to (A >> S) & (M >> S)

[Luc Van Oostenryck]

On Thu, Aug 10, 2017 at 3:16 AM, Christopher Li <sparse@chrisli.org> wrote:

>> +               // replace (A & M) >> S
>> +               // by      (A >> S) & (M >> S)
>
> A little bit suggestion base on my previous reading and question ask on
> this. When I first read the comment without reading the code, then I would
> wondering why (A>>S) & (M>>S) is simpler. The following code actually
> explain the constant mask very well. So the comment best understand if
> the code was read. Adding some comment on M is constant will help a
> lot in the comment.

Yes.
In fact, these patches still need to have a proper commit message.
I've added a not for now.

--Luc

[PATCH v4 8/9] transform (A << S) >> S into A & (-1 >> S)

[Luc Van Oostenryck]

More exactly, transform it into:
	A & (Mask(size) >> S)
which is equivalent to:
	A & Mask(size - S)
where Mask(X) is ((1 << X) - 1)

This transformation is especially usefull when simplifying code
accessing bitfields or for other masking manipulations.

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

diff --git a/simplify.c b/simplify.c
index e8bf1c171..370d4cb81 100644
--- a/simplify.c
+++ b/simplify.c
@@ -415,6 +415,8 @@ static int simplify_lsr(struct instruction *insn, pseudo_t pseudo, long long val
 {
 	struct instruction *def;
 	unsigned long long mask;
+	unsigned int width;
+	pseudo_t old;
 
 	if (!value)
 		return replace_with_pseudo(insn, pseudo);
@@ -433,6 +435,21 @@ static int simplify_lsr(struct instruction *insn, pseudo_t pseudo, long long val
 		insn->opcode = OP_AND;
 		insn->src2 = value_pseudo(mask >> value);
 		return REPEAT_CSE;
+	case OP_SHL:
+		// replace (A << S) >> S
+		// by      A & (Mask(size) >> S)
+		def = insn->src1->def;
+		if (!constant(def->src2))
+			break;
+		if (def->src2->value != value)
+			break;
+		width = insn->size - value;
+		insn->src2 = value_pseudo((1ULL << width) - 1);
+		insn->opcode = OP_AND;
+		old = insn->src1;
+		use_pseudo(insn, def->src1, &insn->src1);
+		remove_usage(old, &insn->src1);
+		return REPEAT_CSE;
 	}
 	return 0;
 }
-- 
2.14.0

[PATCH v4 9/9] fix: cast of OP_AND only valid if it's an OP_CAST

[Luc Van Oostenryck]

A cast of an OP_AND can be simplified away if the mask
already 'cover' the value.
However this cannot be done if the cast is in fact
a sign-extension.

Fix this by adding the appropriate check of OP_CAST vs. OP_SCAST

Fixes: caeaf72d34d1e91aaea7340241232d1d877907b7
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/simplify.c b/simplify.c
index 370d4cb81..dc4fd457b 100644
--- a/simplify.c
+++ b/simplify.c
@@ -1036,7 +1036,7 @@ static int simplify_cast(struct instruction *insn)
 	}
 
 	/* A cast of a "and" might be a no-op.. */
-	if (def_opcode(src) == OP_AND) {
+	if (insn->opcode == OP_CAST && def_opcode(src) == OP_AND) {
 		struct instruction *def = src->def;
 		if (def->size >= size) {
 			pseudo_t val = def->src2;
-- 
2.14.0