[PATCH v3 0/7] fixes for rare issues

[PATCH v3 0/7] fixes for rare issues

[Luc Van Oostenryck]

This series contains some fixes for crashes I found during
some fuzzy-testing, as well as for some infinite loops
that may happen during simplification.

Patch 3 is quite fundamental for all BB simplifications.
I won't bet this is all perfect now but at least the change
make a lot of sense and I'm confident that the situation is
now a lot saner.

It passes all functional tests (regressions test & kernel check),
it should be fine when used on the Wine code too.

Changes since v3:
- change the way kill_unreachable_bbs() is called (patch 1)
- add fix for the infinite simplification loops   (patch 2 & 3)

This series is also available at:
  git://github.com/lucvoo/sparse.git fix-fuzzy-crashes-v3

----------------------------------------------------------------
Luc Van Oostenryck (7):
      fix ptrlist corruption while killing unreachable BBs
      fix infinite simplification loops
      fix BB dependencies on phi-nodes
      fix crash when ep->active is NULL
      fix crash in rewrite_branch()
      fix some crashes in add_dominators()
      fix crash with sym->bb_target == NULL

 cse.c                             |  2 ++
 flow.c                            | 38 ++++++++++++++++++--------------------
 linearize.c                       | 17 +++++++++++------
 memops.c                          |  2 ++
 simplify.c                        |  9 +++++++++
 validation/crash-add-doms.c       | 22 ++++++++++++++++++++++
 validation/crash-bb_target.c      | 10 ++++++++++
 validation/crash-ep-active.c      | 12 ++++++++++++
 validation/crash-ptrlist.c        | 23 +++++++++++++++++++++++
 validation/crash-rewrite-branch.c | 24 ++++++++++++++++++++++++
 validation/crazy02-not-so.c       | 18 ++++++++++++++++++
 validation/infinite-loop02.c      | 11 +++++++++++
 validation/infinite-loop03.c      | 16 ++++++++++++++++
 13 files changed, 178 insertions(+), 26 deletions(-)
 create mode 100644 validation/crash-add-doms.c
 create mode 100644 validation/crash-bb_target.c
 create mode 100644 validation/crash-ep-active.c
 create mode 100644 validation/crash-ptrlist.c
 create mode 100644 validation/crash-rewrite-branch.c
 create mode 100644 validation/infinite-loop02.c
 create mode 100644 validation/infinite-loop03.c

[PATCH v3 1/7] fix ptrlist corruption while killing unreachable BBs

[Luc Van Oostenryck]

In commit (51cfbc90a5 "fix: kill unreachable BBs after killing a child")
kill_unreachable_bbs() was called during simplification in order
to avoid creating fake cycles between phis and issuing bogus
"crazy programmer" warnings.

However, simplification is done via cse.c:clean_up_insns()
which is looping over all BBs while kill_unreachable_bbs()
loops over all BBs *and* can delete some of them which may
corrupt the looping in clean_up_insns().

Fix this by:
1) refuse to emit the "crazy programmer" warning if there
   is a potential dead BB
2) move kill_unreachable_bbs() in the main cleanup loop
   which will avoid nested ep->bbs loop.

Note: this solution is preferable to some others because
      the "crazy programmer" condition happens very rarely.
      It this thus better to delay this check than to call
      kill_unreachable_bbs() preventively.

Note: the reproducer is one with very broken syntax but nothing
      forbid the same situation to happen with a valid program.

Fixes: 51cfbc90a5e1462fcd624a1598ecd985a508a5d6
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 cse.c                       |  2 ++
 flow.c                      |  2 --
 linearize.c                 |  3 ---
 simplify.c                  |  9 +++++++++
 validation/crash-ptrlist.c  | 23 +++++++++++++++++++++++
 validation/crazy02-not-so.c | 18 ++++++++++++++++++
 6 files changed, 52 insertions(+), 5 deletions(-)
 create mode 100644 validation/crash-ptrlist.c

diff --git a/cse.c b/cse.c
index 0d3815c5a..17b3da01a 100644
--- a/cse.c
+++ b/cse.c
@@ -364,6 +364,8 @@ void cleanup_and_cse(struct entrypoint *ep)
 repeat:
 	repeat_phase = 0;
 	clean_up_insns(ep);
+	if (repeat_phase & REPEAT_CFG_CLEANUP)
+		kill_unreachable_bbs(ep);
 	for (i = 0; i < INSN_HASH_SIZE; i++) {
 		struct instruction_list **list = insn_hash_table + i;
 		if (*list) {
diff --git a/flow.c b/flow.c
index c7161d47e..fce8bde21 100644
--- a/flow.c
+++ b/flow.c
@@ -840,8 +840,6 @@ void kill_unreachable_bbs(struct entrypoint *ep)
 		DELETE_CURRENT_PTR(bb);
 	} END_FOR_EACH_PTR(bb);
 	PACK_PTR_LIST(&ep->bbs);
-
-	repeat_phase &= ~REPEAT_CFG_CLEANUP;
 }
 
 static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old, struct basic_block *new)
diff --git a/linearize.c b/linearize.c
index 7313e72d8..a36720779 100644
--- a/linearize.c
+++ b/linearize.c
@@ -671,9 +671,6 @@ void insert_branch(struct basic_block *bb, struct instruction *jmp, struct basic
 		remove_parent(child, bb);
 	} END_FOR_EACH_PTR(child);
 	PACK_PTR_LIST(&bb->children);
-
-	if (repeat_phase & REPEAT_CFG_CLEANUP)
-		kill_unreachable_bbs(bb->ep);
 }
 	
 
diff --git a/simplify.c b/simplify.c
index a141ddd43..03ff9c942 100644
--- a/simplify.c
+++ b/simplify.c
@@ -879,6 +879,15 @@ offset:
 	if (new == orig) {
 		if (new == VOID)
 			return 0;
+		/*
+		 * If some BB have been removed it is possible that this
+		 * memop is in fact part of a dead BB. In this case
+		 * we must not warn since nothing is wrong.
+		 * If not part of a dead BB this will be redone after
+		 * the BBs have been cleaned up.
+		 */
+		if (repeat_phase & REPEAT_CFG_CLEANUP)
+			return 0;
 		new = VOID;
 		warning(insn->pos, "crazy programmer");
 	}
diff --git a/validation/crash-ptrlist.c b/validation/crash-ptrlist.c
new file mode 100644
index 000000000..8e9b5cb5f
--- /dev/null
+++ b/validation/crash-ptrlist.c
@@ -0,0 +1,23 @@
+a;
+char b;
+c() {
+  while () {
+    int *d;
+    while () {
+      char *e = &b;
+      if (a ?: (*d = f || *0) || g) {
+        if
+          ;
+      } else {
+        int h = 0;
+        if (j) {
+          char **i = &e;
+          if (0 ? 0 : 0 ?: (**i = 1 || 0 && 0))             h ?: (*e = i && &h
+
+/*
+ * check-name: crash ptrlist
+ * check-command: test-linearize $file
+ *
+ * check-error-ignore
+ * check-output-ignore
+ */
diff --git a/validation/crazy02-not-so.c b/validation/crazy02-not-so.c
index fe7133587..19ee25299 100644
--- a/validation/crazy02-not-so.c
+++ b/validation/crazy02-not-so.c
@@ -16,6 +16,24 @@ int foo(int *ptr, int i)
 	return 1;
 }
 
+int bar(int *ptr, int i)
+{
+	int *p;
+
+	switch (i - i) {		// will be optimized to 0
+	case 0:
+		return 0;
+	case 1:				// will be optimized away
+					// p is uninitialized
+		do {			// will be an unreachable loop
+			*p++ = 123;
+		} while (--i);
+		break;
+	}
+
+	return 1;
+}
+
 /*
  * check-name: crazy02-not-so.c
  * check-command: sparse -Wno-decl $file
-- 
2.13.2

[PATCH v3 2/7] fix infinite simplification loops

[Luc Van Oostenryck]

Each time a parent is removed from a BB there is
the possibility that the BB become unreachable.
This in turn can create cycles of dead BBs which
can the create inifinite loops during the
simplification process.

Fix this by setting the flag REPEAT_CFG_CLEANUP when
a branch is rewritten, this will in turn trigger
a call to kill_unreachable_bbs() which will break
these loops.

Reported-by: Michael Stefaniuc <mstefani@mykolab.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                       |  3 ++-
 validation/infinite-loop02.c | 11 +++++++++++
 validation/infinite-loop03.c | 16 ++++++++++++++++
 3 files changed, 29 insertions(+), 1 deletion(-)
 create mode 100644 validation/infinite-loop02.c
 create mode 100644 validation/infinite-loop03.c

diff --git a/flow.c b/flow.c
index fce8bde21..536bf257f 100644
--- a/flow.c
+++ b/flow.c
@@ -34,7 +34,8 @@ static int rewrite_branch(struct basic_block *bb,
 		return 0;
 
 	/* We might find new if-conversions or non-dominating CSEs */
-	repeat_phase |= REPEAT_CSE;
+	/* we may also create new dead cycles */
+	repeat_phase |= REPEAT_CSE | REPEAT_CFG_CLEANUP;
 	*ptr = new;
 	replace_bb_in_list(&bb->children, old, new, 1);
 	remove_bb_from_list(&old->parents, bb, 1);
diff --git a/validation/infinite-loop02.c b/validation/infinite-loop02.c
new file mode 100644
index 000000000..7d0761d87
--- /dev/null
+++ b/validation/infinite-loop02.c
@@ -0,0 +1,11 @@
+void foo(void)
+{
+	int a = 1;
+	while ((a = !a))
+		;
+}
+
+/*
+ * check-name: infinite loop 02
+ * check-command: sparse -Wno-decl $file
+ */
diff --git a/validation/infinite-loop03.c b/validation/infinite-loop03.c
new file mode 100644
index 000000000..ac8a9519d
--- /dev/null
+++ b/validation/infinite-loop03.c
@@ -0,0 +1,16 @@
+static void foo(int *buf)
+{
+	int a = 1;
+	int *b;
+	do {
+		if (a)
+			b = buf;
+		if (a)
+			*buf = 0;
+	} while (!(a = !a));
+}
+
+/*
+ * check-name: infinite loop 03
+ * check-command: sparse -Wno-decl $file
+ */
-- 
2.13.2

[PATCH v3 3/7] fix BB dependencies on phi-nodes

[Luc Van Oostenryck]

Simplification of BBs (via try_to_siplify_bb() or
simplify_branch_branch()) can only be done under
some conditions:
- the removed/bypassed BB is free of side-effects
- the removed/bypassed BB doesn't define some pseudos
  needed later.
This last check is efficiently done by bb_depends_on()
using liveness info. However, there is no liveness
done on OP_PHI thus the dependencies involving OP_PHI
are missing, resulting in illegal simplifications.

Fix this by explicitly adding the missing dependencies.

Supersedes: 852801f8b966407544326cd1c485f9bc7681a2e6
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c | 31 +++++++++++++++----------------
 1 file changed, 15 insertions(+), 16 deletions(-)

diff --git a/flow.c b/flow.c
index 536bf257f..23fa7c21b 100644
--- a/flow.c
+++ b/flow.c
@@ -81,26 +81,23 @@ static int bb_depends_on(struct basic_block *target, struct basic_block *src)
 }
 
 /*
- * This is only to be used by try_to_simplify_bb().
- * It really should be handled by bb_depends_on(), only
- * that there is no liveness done on OP_PHI/OP_PHISRC.
- * So we consider for now that if there is an OP_PHI
- * then some block in fact depends on this one.
- * The OP_PHI controling the conditional branch of this bb
- * is excluded since the branch will be removed.
+ * This really should be handled by bb_depends_on()
+ * which efficiently check the dependence using the
+ * defines - needs liveness info. Problem is that
+ * there is no liveness done on OP_PHI & OP_PHISRC.
+ *
+ * This function add the missing dependency checks.
  */
-static int bb_defines_phi(struct basic_block *bb, struct instruction *def)
+static int bb_depends_on_phi(struct basic_block *target, struct basic_block *src)
 {
 	struct instruction *insn;
-	FOR_EACH_PTR(bb->insns, insn) {
-		switch (insn->opcode) {
-		case OP_PHI:
-			if (def && insn != def)
-				return 1;
+	FOR_EACH_PTR(src->insns, insn) {
+		if (!insn->bb)
 			continue;
-		default:
+		if (insn->opcode != OP_PHI)
 			continue;
-		}
+		if (pseudo_in_list(target->needs, insn->target))
+			return 1;
 	} END_FOR_EACH_PTR(insn);
 	return 0;
 }
@@ -153,7 +150,7 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 		target = true ? second->bb_true : second->bb_false;
 		if (bb_depends_on(target, bb))
 			continue;
-		if (bb_defines_phi(bb, first))
+		if (bb_depends_on_phi(target, bb))
 			continue;
 		changed |= rewrite_branch(source, &br->bb_true, bb, target);
 		changed |= rewrite_branch(source, &br->bb_false, bb, target);
@@ -224,6 +221,8 @@ static int simplify_branch_branch(struct basic_block *bb, struct instruction *br
 		goto try_to_rewrite_target;
 	if (bb_depends_on(final, target))
 		goto try_to_rewrite_target;
+	if (bb_depends_on_phi(final, target))
+		return 0;
 	return rewrite_branch(bb, target_p, target, final);
 
 try_to_rewrite_target:
-- 
2.13.2

[PATCH v3 4/7] fix crash when ep->active is NULL

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c                  |  9 +++++++--
 validation/crash-ep-active.c | 12 ++++++++++++
 2 files changed, 19 insertions(+), 2 deletions(-)
 create mode 100644 validation/crash-ep-active.c

diff --git a/linearize.c b/linearize.c
index a36720779..12209492b 100644
--- a/linearize.c
+++ b/linearize.c
@@ -820,10 +820,15 @@ static pseudo_t argument_pseudo(struct entrypoint *ep, int nr)
 
 pseudo_t alloc_phi(struct basic_block *source, pseudo_t pseudo, int size)
 {
-	struct instruction *insn = alloc_instruction(OP_PHISOURCE, size);
-	pseudo_t phi = __alloc_pseudo(0);
+	struct instruction *insn;
+	pseudo_t phi;
 	static int nr = 0;
 
+	if (!source)
+		return VOID;
+
+	insn = alloc_instruction(OP_PHISOURCE, size);
+	phi = __alloc_pseudo(0);
 	phi->type = PSEUDO_PHI;
 	phi->nr = ++nr;
 	phi->def = insn;
diff --git a/validation/crash-ep-active.c b/validation/crash-ep-active.c
new file mode 100644
index 000000000..6945f320b
--- /dev/null
+++ b/validation/crash-ep-active.c
@@ -0,0 +1,12 @@
+int a(int b)
+{
+        return 0( && b;
+}
+
+/*
+ * check-name: crash ep->active
+ * check-command: test-linearize $file
+ *
+ * check-error-ignore
+ * check-output-ignore
+ */
-- 
2.13.2

[PATCH v3 5/7] fix crash in rewrite_branch()

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                            |  2 +-
 validation/crash-rewrite-branch.c | 24 ++++++++++++++++++++++++
 2 files changed, 25 insertions(+), 1 deletion(-)
 create mode 100644 validation/crash-rewrite-branch.c

diff --git a/flow.c b/flow.c
index 23fa7c21b..6cac21b24 100644
--- a/flow.c
+++ b/flow.c
@@ -30,7 +30,7 @@ static int rewrite_branch(struct basic_block *bb,
 	struct basic_block *old,
 	struct basic_block *new)
 {
-	if (*ptr != old || new == old)
+	if (*ptr != old || new == old || !bb->ep)
 		return 0;
 
 	/* We might find new if-conversions or non-dominating CSEs */
diff --git a/validation/crash-rewrite-branch.c b/validation/crash-rewrite-branch.c
new file mode 100644
index 000000000..eb310df1c
--- /dev/null
+++ b/validation/crash-rewrite-branch.c
@@ -0,0 +1,24 @@
+void a(int c, int e)
+{
+	for(;                   b; c ;
+
+	if (()) {
+		unsigned short d = e;
+		if (())
+			while ()
+				;
+		&d;
+	}
+
+	if (()) {
+		int f = &f;
+	}
+}
+
+/*
+ * check-name: crash rewrite_branch
+ * check-command: test-linearize $file
+ *
+ * check-error-ignore
+ * check-output-ignore
+ */
-- 
2.13.2

[PATCH v3 6/7] fix some crashes in add_dominators()

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 memops.c                    |  2 ++
 validation/crash-add-doms.c | 22 ++++++++++++++++++++++
 2 files changed, 24 insertions(+)
 create mode 100644 validation/crash-add-doms.c

diff --git a/memops.c b/memops.c
index 5efdd6f2d..aeacdf566 100644
--- a/memops.c
+++ b/memops.c
@@ -29,6 +29,8 @@ static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
 
 		FOR_EACH_PTR_REVERSE(parent->insns, one) {
 			int dominance;
+			if (!one->bb)
+				continue;
 			if (one == insn)
 				goto no_dominance;
 			dominance = dominates(pseudo, insn, one, local);
diff --git a/validation/crash-add-doms.c b/validation/crash-add-doms.c
new file mode 100644
index 000000000..54ad93e84
--- /dev/null
+++ b/validation/crash-add-doms.c
@@ -0,0 +1,22 @@
+char a;
+int b;
+void c(void)
+{
+	if (0) {
+		char *d;
+		for (;;)
+			for (;;)
+e:
+				*d *= (a && 0) ^ b && *d;
+	}
+	goto e;
+}
+
+
+/*
+ * check-name: crash add-doms
+ * check-command: test-linearize $file
+ *
+ * check-error-ignore
+ * check-output-ignore
+ */
-- 
2.13.2

[PATCH v3 7/7] fix crash with sym->bb_target == NULL

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 linearize.c                  |  5 ++++-
 validation/crash-bb_target.c | 10 ++++++++++
 2 files changed, 14 insertions(+), 1 deletion(-)
 create mode 100644 validation/crash-bb_target.c

diff --git a/linearize.c b/linearize.c
index 12209492b..ba76397ea 100644
--- a/linearize.c
+++ b/linearize.c
@@ -334,6 +334,7 @@ const char *show_instruction(struct instruction *insn)
 		
 	case OP_SETVAL: {
 		struct expression *expr = insn->val;
+		struct symbol *sym;
 		buf += sprintf(buf, "%s <- ", show_pseudo(insn->target));
 
 		if (!expr) {
@@ -355,7 +356,9 @@ const char *show_instruction(struct instruction *insn)
 			buf += sprintf(buf, "%s", show_ident(expr->symbol->ident));
 			break;
 		case EXPR_LABEL:
-			buf += sprintf(buf, ".L%u", expr->symbol->bb_target->nr);
+			sym = expr->symbol;
+			if (sym->bb_target)
+				buf += sprintf(buf, ".L%u", sym->bb_target->nr);
 			break;
 		default:
 			buf += sprintf(buf, "SETVAL EXPR TYPE %d", expr->type);
diff --git a/validation/crash-bb_target.c b/validation/crash-bb_target.c
new file mode 100644
index 000000000..bc5a3d354
--- /dev/null
+++ b/validation/crash-bb_target.c
@@ -0,0 +1,10 @@
+a() {
+  &&b
+
+/*
+ * check-name: crash bb_target
+ * check-command: test-linearize $file
+ *
+ * check-error-ignore
+ * check-output-ignore
+ */
-- 
2.13.2

Re: [PATCH v3 0/7] fixes for rare issues

[Christopher Li]

On Mon, Jul 31, 2017 at 4:36 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> This series contains some fixes for crashes I found during
> some fuzzy-testing, as well as for some infinite loops
> that may happen during simplification.

Thank you so much for the patch.

I have to ask, is it for review (for now) or request to pull to
sparse-next (drop the previous version in sparse-next)?

Chris

Re: [PATCH v3 1/7] fix ptrlist corruption while killing unreachable BBs

[Christopher Li]

On Mon, Jul 31, 2017 at 4:36 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> Fix this by:
> 1) refuse to emit the "crazy programmer" warning if there
>    is a potential dead BB
> 2) move kill_unreachable_bbs() in the main cleanup loop
>    which will avoid nested ep->bbs loop.

Great!

>
> Note: this solution is preferable to some others because
>       the "crazy programmer" condition happens very rarely.
>       It this thus better to delay this check than to call
>       kill_unreachable_bbs() preventively.
>
> Note: the reproducer is one with very broken syntax but nothing
>       forbid the same situation to happen with a valid program.
>
> Fixes: 51cfbc90a5e1462fcd624a1598ecd985a508a5d6
> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> ---
>  cse.c                       |  2 ++
>  flow.c                      |  2 --
>  linearize.c                 |  3 ---
>  simplify.c                  |  9 +++++++++
>  validation/crash-ptrlist.c  | 23 +++++++++++++++++++++++
>  validation/crazy02-not-so.c | 18 ++++++++++++++++++
>  6 files changed, 52 insertions(+), 5 deletions(-)
>  create mode 100644 validation/crash-ptrlist.c
>
> diff --git a/cse.c b/cse.c
> index 0d3815c5a..17b3da01a 100644
> --- a/cse.c
> +++ b/cse.c
> @@ -364,6 +364,8 @@ void cleanup_and_cse(struct entrypoint *ep)
>  repeat:
>         repeat_phase = 0;
>         clean_up_insns(ep);
> +       if (repeat_phase & REPEAT_CFG_CLEANUP)
> +               kill_unreachable_bbs(ep);
>         for (i = 0; i < INSN_HASH_SIZE; i++) {

Interesting.  So my reading is that, this is similar to the other
alternative patch
we discuss with different that:
1. move up kill_unreachable_bbs(ep) right after clean_up_insns(ep)

> +               /*
> +                * If some BB have been removed it is possible that this
> +                * memop is in fact part of a dead BB. In this case
> +                * we must not warn since nothing is wrong.
> +                * If not part of a dead BB this will be redone after
> +                * the BBs have been cleaned up.
> +                */
> +               if (repeat_phase & REPEAT_CFG_CLEANUP)
> +                       return 0;

2. Avoid issue "crazy programmer" if we still have dead code to clean up.

That sound very reasonable and I feel that is better than the previous version
which eager to kill bbs. That is great.

I really appreciate the change.

Chris

Re: [PATCH v3 0/7] fixes for rare issues

[Luc Van Oostenryck]

On Mon, Jul 31, 2017 at 11:01 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Mon, Jul 31, 2017 at 4:36 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> This series contains some fixes for crashes I found during
>> some fuzzy-testing, as well as for some infinite loops
>> that may happen during simplification.
>
> Thank you so much for the patch.
>
> I have to ask, is it for review (for now) or request to pull to
> sparse-next (drop the previous version in sparse-next)?

It's for review & test as one patch is really changed and two
are new and while small induce big changes.

-- Luc

Re: [PATCH v3 1/7] fix ptrlist corruption while killing unreachable BBs

[Luc Van Oostenryck]

On Mon, Jul 31, 2017 at 11:41 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Mon, Jul 31, 2017 at 4:36 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>>
>> Fix this by:
>> 1) refuse to emit the "crazy programmer" warning if there
>>    is a potential dead BB
>> 2) move kill_unreachable_bbs() in the main cleanup loop
>>    which will avoid nested ep->bbs loop.
>
> Great!

> Interesting.  So my reading is that, this is similar to the other
> alternative patch
> we discuss with different that:
> 1. move up kill_unreachable_bbs(ep) right after clean_up_insns(ep)
> 2. Avoid issue "crazy programmer" if we still have dead code to clean up.
>
> That sound very reasonable and I feel that is better than the previous version
> which eager to kill bbs. That is great.

Yes.
I just hope there isn't some other condition to would force again to
have to do the kill_unreachable_bbs() sooner.

> I really appreciate the change.

I thought you would.
The second difference is fundamental for correctness.
For the first, difference, I placed it between cleanup & CSE
because cleanup can create opportunities for dead BBs while
CSE doesn't and it's useless to do CSE on dead BBs.
So, it would be a small perf improvement.

Having some kill_unreachable_bbs() in the main loop was also
needed for the infinite loop problem (this in itself already stopped
the infinite loop with the wine code but the generated code was
very very wrong thus the need for the bb_depends_on() patch
which I think now fixes the root cause there).

I'll launch some stress testing tomorrow.

-- Luc

Re: [PATCH v3 0/7] fixes for rare issues

[Luc Van Oostenryck]

On Mon, Jul 31, 2017 at 11:54 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Mon, Jul 31, 2017 at 11:01 PM, Christopher Li <sparse@chrisli.org> wrote:
>> On Mon, Jul 31, 2017 at 4:36 PM, Luc Van Oostenryck
>> <luc.vanoostenryck@gmail.com> wrote:
>>> This series contains some fixes for crashes I found during
>>> some fuzzy-testing, as well as for some infinite loops
>>> that may happen during simplification.
>>
>> Thank you so much for the patch.
>>
>> I have to ask, is it for review (for now) or request to pull to
>> sparse-next (drop the previous version in sparse-next)?
>
> It's for review & test as one patch is really changed and two
> are new and while small induce big changes.

One of the thing I haven't tested is the performance.
Several things here can make things slower:
- REPEAT_CFG_CLEANUP is now set after every call to rewrite_branch()
  (and will then trigger at some point a call to kill_unreachable_bbs())
- kill_unreachable_bbs() set REPEAT_CSE is a BB have been deleted
  (which may trigger another CSE cycle possibly not present before)
- the bb_depends_on() change add some code with looping through
  the BB's instructions, nothing really heavy but still some more code
  to run
All these are needed though.

-- Luc

Re: [PATCH v3 0/7] fixes for rare issues

[Luc Van Oostenryck]

On Tue, Aug 1, 2017 at 12:34 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Mon, Jul 31, 2017 at 11:54 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> On Mon, Jul 31, 2017 at 11:01 PM, Christopher Li <sparse@chrisli.org> wrote:
>>> On Mon, Jul 31, 2017 at 4:36 PM, Luc Van Oostenryck
>>> <luc.vanoostenryck@gmail.com> wrote:
>>>> This series contains some fixes for crashes I found during
>>>> some fuzzy-testing, as well as for some infinite loops
>>>> that may happen during simplification.
>>>
>>> Thank you so much for the patch.
>>>
>>> I have to ask, is it for review (for now) or request to pull to
>>> sparse-next (drop the previous version in sparse-next)?
>>
>> It's for review & test as one patch is really changed and two
>> are new and while small induce big changes.
>
> One of the thing I haven't tested is the performance.
> Several things here can make things slower:
> - REPEAT_CFG_CLEANUP is now set after every call to rewrite_branch()
>   (and will then trigger at some point a call to kill_unreachable_bbs())
> - kill_unreachable_bbs() set REPEAT_CSE is a BB have been deleted
>   (which may trigger another CSE cycle possibly not present before)
> - the bb_depends_on() change add some code with looping through
>   the BB's instructions, nothing really heavy but still some more code
>   to run
> All these are needed though.

And indeed I see that some tests that took me 38s now take 48s.
I'll look tomorrow for the real cause and see what can be done there.

-- Luc

Re: [PATCH v3 0/7] fixes for rare issues

[Luc Van Oostenryck]

On Tue, Aug 1, 2017 at 12:42 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:

>> One of the thing I haven't tested is the performance.
>> Several things here can make things slower:
>> - REPEAT_CFG_CLEANUP is now set after every call to rewrite_branch()
>>   (and will then trigger at some point a call to kill_unreachable_bbs())
>> - kill_unreachable_bbs() set REPEAT_CSE is a BB have been deleted
>>   (which may trigger another CSE cycle possibly not present before)
>> - the bb_depends_on() change add some code with looping through
>>   the BB's instructions, nothing really heavy but still some more code
>>   to run
>> All these are needed though.
>
> And indeed I see that some tests that took me 38s now take 48s.
> I'll look tomorrow for the real cause and see what can be done there.

OK. That was a false alert, I was still running with debug on.

-- Luc

Re: [PATCH v3 0/7] fixes for rare issues

[Christopher Li]

On Tue, Aug 1, 2017 at 4:46 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> OK. That was a false alert, I was still running with debug on.

My sparse full kernel test shows that:

With -rc4:
1145.61user 517.15system 2:36.62elapsed 1061%CPU (0avgtext+0avgdata
235532maxresident)k
0inputs+12744outputs (0major+126771950minor)pagefaults 0swaps

With fix-fuzzy-crashes-v3:
1128.17user 514.33system 2:34.92elapsed 1060%CPU (0avgtext+0avgdata
235556maxresident)k
0inputs+12744outputs (0major+126769380minor)pagefaults 0swaps

It seems about the same or slightly faster. Obviously only one run of each here.
I have another run before that to warm up the machine, that run also
shows V3 is slightly faster.
But not enough run to say for sure. It is within the variance of run to run.

The warning output is exactly the same, no changes.

Chris

Re: [PATCH v3 0/7] fixes for rare issues

[Luc Van Oostenryck]

On Tue, Aug 1, 2017 at 11:49 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Tue, Aug 1, 2017 at 4:46 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>>
>> OK. That was a false alert, I was still running with debug on.
>
> My sparse full kernel test shows that:
>
> With -rc4:
> 1145.61user 517.15system 2:36.62elapsed 1061%CPU (0avgtext+0avgdata
> 235532maxresident)k
> 0inputs+12744outputs (0major+126771950minor)pagefaults 0swaps
>
> With fix-fuzzy-crashes-v3:
> 1128.17user 514.33system 2:34.92elapsed 1060%CPU (0avgtext+0avgdata
> 235556maxresident)k
> 0inputs+12744outputs (0major+126769380minor)pagefaults 0swaps
>
> It seems about the same or slightly faster. Obviously only one run of each here.
> I have another run before that to warm up the machine, that run also
> shows V3 is slightly faster.
> But not enough run to say for sure. It is within the variance of run to run.

Yes, it's what I really have too.

-- Luc