[PATCH 0/2] fix bogus "crazy progammer"

[PATCH 0/2] fix bogus "crazy progammer"

[Luc Van Oostenryck]

The goal of this series is to fix the bogus "crazy progammer"
warnings issued by sparse when running on the git tree.

This "crazy programmer" warning is issued when there is
a circulary dependency between pseudos but in the present
case this circulary dependence was only an consequence of
optimizations applied on a wrong state.

With this bug fixed, there is only a single sparse warnings 
left in the git tree (and it's most probably a bogus one).
Big congrats to them!
For comparison the Linux kernel has more than 1000 errors and
close to 24000 warnings (on an allyesconfig for x86-64),
plenty of bogus ones but also a lot of real ones.

For the adventurous ones, this series is also available at:
  git://github.com/lucvoo/sparse.git fix-eager-ttsbb


Luc Van Oostenryck (2):
  fix OP_PHI usage in try_to_simplify_bb() only when non-bogus
  fix: try_to_simplify_bb eargerness

 flow.c               | 47 ++++++++++++++++++++++++++---------------------
 validation/crazy03.c | 33 +++++++++++++++++++++++++++++++++
 2 files changed, 59 insertions(+), 21 deletions(-)
 create mode 100644 validation/crazy03.c

-- 
2.13.0

[PATCH 1/2] fix OP_PHI usage in try_to_simplify_bb() only when non-bogus

[Luc Van Oostenryck]

Currently, sparse method of conversion to SSA form, doesn't
place phi-nodes at the dominance frontier but often place them
'lower' where the corresponding 'value' is needed.
This, in itself create all sort of problems. One of these
problems is that it is then quite common for an OP_PHI
to contains less 'sources' than it has parents. This is wrong
has phi-nodes represent the 'join' a value can have from each
of the incoming paths/parents.

This situation can't be given a sensible semantic and any
attempt to try some optimization involving the phi-nodes and
their sources are bound to fail.

Temporary workaround this in try_to_simplify_bb() by simply
checking if the number of parents and the number of phi-sources
match and avoid to make this simplification if they don't.

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

diff --git a/flow.c b/flow.c
index e0932edb4..8a9005aa6 100644
--- a/flow.c
+++ b/flow.c
@@ -79,34 +79,6 @@ static int bb_depends_on(struct basic_block *target, struct basic_block *src)
 	return 0;
 }
 
-/*
- * Return 1 if 'pseudo' is needed in some parent of 'bb'.
- * Need liveness info.
- */
-static int needed_phisrc(struct instruction *phi, struct basic_block *curr, unsigned long generation)
-{
-	pseudo_t target = phi->target;
-	struct basic_block *bb;
-
-	curr->generation = generation;
-	FOR_EACH_PTR(curr->children, bb) {
-		if (bb->generation == generation)
-			continue;
-		if (bb == phi->bb)
-			continue;
-		if (pseudo_in_list(bb->defines, target)) {
-			continue;
-		}
-		if (pseudo_in_list(bb->needs, target))
-			return 1;
-		if (needed_phisrc(phi, bb, generation))
-			return 1;
-
-	} END_FOR_EACH_PTR(bb);
-
-	return 0;
-}
-
 /*
  * When we reach here, we have:
  *  - a basic block that ends in a conditional branch and
@@ -122,6 +94,14 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 {
 	int changed = 0;
 	pseudo_t phi;
+	int bogus;
+
+	/*
+	 * This a due to improper dominance tracking during
+	 * simplify_symbol_usage()/conversion to SSA form.
+	 * No sane simplification can be done when we have this.
+	 */
+	bogus = bb_list_size(bb->parents) != pseudo_list_size(first->phi_list);
 
 	FOR_EACH_PTR(first->phi_list, phi) {
 		struct instruction *def = phi->def;
@@ -149,7 +129,7 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 			continue;
 		changed |= rewrite_branch(source, &br->bb_true, bb, target);
 		changed |= rewrite_branch(source, &br->bb_false, bb, target);
-		if (changed && !needed_phisrc(first, source, ++bb_generation))
+		if (changed && !bogus)
 			kill_use(THIS_ADDRESS(phi));
 	} END_FOR_EACH_PTR(phi);
 	return changed;
-- 
2.13.0

[PATCH 2/2] fix: try_to_simplify_bb eargerness

[Luc Van Oostenryck]

The simplification done by try_to_simplify_bb() (essentially
trying to bypass a basic block containing a conditional branch
if the branch is controlled by an OP_PHI when the corresponding
OP_PHISRC is a constant) can only be done if some conditions
are met:
1) The basic block doesn't have some side effects (in which case
   it must not be bypassed). Checked by bb_has_side_effects().
2) There may be some pseudos defined in the basic block but no
   basic blocks may depend on them. Checked by bb_depends_on().

The second condition is efficiently checked using liveness
information. However, there is no liveness information done
for OP_PHI/OP_PHISRC. So if the basic block contains some
other OP_PHI than the controlling one, there will surely be
some other BB depending on it but this will not be reflected
in the liveness info and bb_depends_on() can then wrongly
report that no dependencies exist.

Fix this by adding an extra check, verifiying that no other
OP_PHI are defined in the BB and avoiding the simplification
otherwise.

Reported-by: Ramsay Jones <ramsay@ramsayjones.plus.com>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c               | 25 +++++++++++++++++++++++++
 validation/crazy03.c | 33 +++++++++++++++++++++++++++++++++
 2 files changed, 58 insertions(+)
 create mode 100644 validation/crazy03.c

diff --git a/flow.c b/flow.c
index 8a9005aa6..23145d6e7 100644
--- a/flow.c
+++ b/flow.c
@@ -79,6 +79,29 @@ static int bb_depends_on(struct basic_block *target, struct basic_block *src)
 	return 0;
 }
 
+/*
+ * 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.
+ */
+static int bb_defines_phi(struct basic_block *bb, struct instruction *def)
+{
+	struct instruction *insn;
+	FOR_EACH_PTR(bb->insns, insn) {
+		switch (insn->opcode) {
+		case OP_PHI:
+			if (def && insn != def)
+				return 1;
+			continue;
+		}
+	} END_FOR_EACH_PTR(insn);
+	return 0;
+}
+
 /*
  * When we reach here, we have:
  *  - a basic block that ends in a conditional branch and
@@ -127,6 +150,8 @@ 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))
+			continue;
 		changed |= rewrite_branch(source, &br->bb_true, bb, target);
 		changed |= rewrite_branch(source, &br->bb_false, bb, target);
 		if (changed && !bogus)
diff --git a/validation/crazy03.c b/validation/crazy03.c
new file mode 100644
index 000000000..042033790
--- /dev/null
+++ b/validation/crazy03.c
@@ -0,0 +1,33 @@
+extern char a;
+extern int b;
+extern char *c, *d;
+extern void e(void);
+extern void f(char *);
+
+int g(int h);
+int g(int h)
+{
+	if (h > 1)
+		e();
+	if (h > 1)
+		return 0;
+	for (;;) {
+		if (a) {
+			while (c) ;
+			b = 0;
+		} else {
+			c = (void*)0;
+			b = 1;
+		}
+		if (b) {
+			f(c);
+			continue;
+		}
+		d = c;
+		while (*c++) ;
+	}
+}
+
+/*
+ * check-name: crazy03.c
+ */
-- 
2.13.0

Re: [PATCH 0/2] fix bogus "crazy progammer"

[Ramsay Jones]

On 16/06/17 20:18, Luc Van Oostenryck wrote:
> The goal of this series is to fix the bogus "crazy progammer"
> warnings issued by sparse when running on the git tree.
> 
> This "crazy programmer" warning is issued when there is
> a circulary dependency between pseudos but in the present
> case this circulary dependence was only an consequence of
> optimizations applied on a wrong state.

Thank you for posting this (I had just started looking at this
again tonight). I have just fetched it and done a very quick test
and this works for me! Thanks!

[You probably noticed that I counted "grep 'inline.*skip_prefix' |
wc -l", thereby counting the number of inlined calls twice! once for
'begin_inline' and once for 'end_inline'! Ahem ;-)]

> With this bug fixed, there is only a single sparse warnings 
> left in the git tree (and it's most probably a bogus one).

Hmm, which one is that? (I'm not counting the 'memset byte count'
warning!) The only other warnings I am aware of are on the 'pu'
branch (expected), or if you build with the NO_REGEX build variable
set. (which I don't on Linux, but I do on cygwin).

This is another long-standing error that I have been meaning to
fix at some point (but it has been on my TODO list for many a
year, so ...). It looks like so:

    SP compat/regex/regex.c
compat/regex/regex_internal.c:926:1: error: symbol 're_string_context_at' redeclared with different type (originally declared at compat/regex/regex_internal.h:434) - different modifiers

(ie the 'pure' attribute is in a different place in the declaration
and definition of the function).

I will do some more testing later (cygwin, 32bit linux etc.) and let
you know if I find anything else.

Thanks again.

ATB,
Ramsay Jones

Re: [PATCH 0/2] fix bogus "crazy progammer"

[Luc Van Oostenryck]

On Fri, Jun 16, 2017 at 09:10:57PM +0100, Ramsay Jones wrote:
> 
> 
> On 16/06/17 20:18, Luc Van Oostenryck wrote:
> > The goal of this series is to fix the bogus "crazy progammer"
> > warnings issued by sparse when running on the git tree.
> > 
> > This "crazy programmer" warning is issued when there is
> > a circulary dependency between pseudos but in the present
> > case this circulary dependence was only an consequence of
> > optimizations applied on a wrong state.
> 
> Thank you for posting this (I had just started looking at this
> again tonight). I have just fetched it and done a very quick test
> and this works for me! Thanks!
> 
> [You probably noticed that I counted "grep 'inline.*skip_prefix' |
> wc -l", thereby counting the number of inlined calls twice! once for
> 'begin_inline' and once for 'end_inline'! Ahem ;-)]

Hehe, I confess that once I saw 'crazy programmer', I directly went
to try to reproduce it (which was simple given you bug report)
because I had already struggled on it some time ago. And then I
tried to reduce it (which took me some time!) before trying to
understand what was happening.

> > With this bug fixed, there is only a single sparse warnings 
> > left in the git tree (and it's most probably a bogus one).
> 
> Hmm, which one is that? (I'm not counting the 'memset byte count'
> warning!) The only other warnings I am aware of are on the 'pu'
> branch (expected), or if you build with the NO_REGEX build variable
> set. (which I don't on Linux, but I do on cygwin).

I think I had left with the default options and it was the master
branch. And, indeed I don't count the 'memset byte count' anymore.
I meant the same as you here:

> This is another long-standing error that I have been meaning to
> fix at some point (but it has been on my TODO list for many a
> year, so ...). It looks like so:
> 
>     SP compat/regex/regex.c
> compat/regex/regex_internal.c:926:1: error: symbol 're_string_context_at' redeclared with different type (originally declared at compat/regex/regex_internal.h:434) - different modifiers
> 
> (ie the 'pure' attribute is in a different place in the declaration
> and definition of the function).

Ah yes, indeed. The syntax for attributes is a bit ... well ...
and dependening on the place the attribute will be 'attached'
either to the function itself or to the return type (or something
close to this).

> I will do some more testing later (cygwin, 32bit linux etc.) and let
> you know if I find anything else.

Yes, please. It's very much appreciated.

-- Luc Van Oostenryck

Re: [PATCH 0/2] fix bogus "crazy progammer"

[Ramsay Jones]

On 17/06/17 04:44, Luc Van Oostenryck wrote:
> On Fri, Jun 16, 2017 at 09:10:57PM +0100, Ramsay Jones wrote:
>> On 16/06/17 20:18, Luc Van Oostenryck wrote:
>> I will do some more testing later (cygwin, 32bit linux etc.) and let
>> you know if I find anything else.
> 
> Yes, please. It's very much appreciated.

Tested on Linux (64-bit and 32-bit) and cygwin (64-bit) with no
additional issues found. Thanks!

ATB,
Ramsay Jones

Re: [PATCH 0/2] fix bogus "crazy progammer"

[Luc Van Oostenryck]

On Sat, Jun 17, 2017 at 10:20:44PM +0100, Ramsay Jones wrote:
> 
> 
> On 17/06/17 04:44, Luc Van Oostenryck wrote:
> > On Fri, Jun 16, 2017 at 09:10:57PM +0100, Ramsay Jones wrote:
> >> On 16/06/17 20:18, Luc Van Oostenryck wrote:
> >> I will do some more testing later (cygwin, 32bit linux etc.) and let
> >> you know if I find anything else.
> > 
> > Yes, please. It's very much appreciated.
> 
> Tested on Linux (64-bit and 32-bit) and cygwin (64-bit) with no
> additional issues found. Thanks!

Thank you very much!

For info, I also tested on some other platform, just for the fun
and only running the testsuite. The results are:
* sparse's makefile totally depends on gmake
* freebsd: OK
* openbsd: build failed because the two available compilers
	didn't liked __builtin_bswap{16,32,64}()
	It should be easy to workaround.
* netbsd:  I had problem to install git. I didn't spend more time.
* OSX:	   OK

Re: [PATCH 0/2] fix bogus "crazy progammer"

[Christopher Li]

On Sat, Jun 17, 2017 at 11:43 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> For info, I also tested on some other platform, just for the fun
> and only running the testsuite. The results are:

Great you have got this issue fix.

I assume you want this fix merge for the -rc2 as well, right?

Chris

Re: [PATCH 0/2] fix bogus "crazy progammer"

[Luc Van Oostenryck]

On Sun, Jun 18, 2017 at 12:24:17AM -0700, Christopher Li wrote:
> On Sat, Jun 17, 2017 at 11:43 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > For info, I also tested on some other platform, just for the fun
> > and only running the testsuite. The results are:
> 
> Great you have got this issue fix.
> 
> I assume you want this fix merge for the -rc2 as well, right?

Yes, sure.
I would like to let it 'soak' a little bit more but I don't see
well how it could be more tested.
I may try the kernel on some non-x86 archs but it won't be for
today or tomorrow.

I have also a patch series for the root cause of the 1st patch:
the misplacement of phi-nodes. This series solve all sort of
problems but it's not the kind of changes for this release:
it's radical changes to some pretty fundamental things and it's
diffstat is: "16 files changed, 679 insertions(+), 476 deletions(-)"
excluding all the changes in the testcases. This will need to
wait for after the release and it's not yet ready anyway, not
even close to.

For the release, I also want the other fix I posted this week,
the one titled "fix: add missing examine in evaluate_dereference()"
which is much more straight-forward.


I'll send another pull request in the next few days.

-- Luc

Re: [PATCH 0/2] fix bogus "crazy progammer"

[Christopher Li]

On Sun, Jun 18, 2017 at 1:11 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Yes, sure.
> I would like to let it 'soak' a little bit more but I don't see
> well how it could be more tested.

Understand. Do you want it on sparse-next while have it soaking?


> I may try the kernel on some non-x86 archs but it won't be for
> today or tomorrow.
>
> I have also a patch series for the root cause of the 1st patch:
> the misplacement of phi-nodes. This series solve all sort of
> problems but it's not the kind of changes for this release:
> it's radical changes to some pretty fundamental things and it's
> diffstat is: "16 files changed, 679 insertions(+), 476 deletions(-)"
> excluding all the changes in the testcases. This will need to
> wait for after the release and it's not yet ready anyway, not
> even close to.

Thanks I was wondering how complicate is the proper fix like.
That is good to know.

>
> For the release, I also want the other fix I posted this week,
> the one titled "fix: add missing examine in evaluate_dereference()"
> which is much more straight-forward.

I have pull your "for-chris" branch into sparse-next.

Chris

Re: [PATCH 0/2] fix bogus "crazy progammer"

[Luc Van Oostenryck]

On Tue, Jun 20, 2017 at 11:09:18AM -0700, Christopher Li wrote:
> On Sun, Jun 18, 2017 at 1:11 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> > Yes, sure.
> > I would like to let it 'soak' a little bit more but I don't see
> > well how it could be more tested.
> 
> Understand. Do you want it on sparse-next while have it soaking?

IIRC, one of the two patches need a small changes.

I'll send you a pull request with the others few fixes.
But I have first some cleanup to do and some retesting.

> > I may try the kernel on some non-x86 archs but it won't be for
> > today or tomorrow.

There was some issues on ARM64.
I also made two changes for freebsd & openbsd that were broken.

> > I have also a patch series for the root cause of the 1st patch:
> > the misplacement of phi-nodes. This series solve all sort of
> > problems but it's not the kind of changes for this release:
> > it's radical changes to some pretty fundamental things and it's
> > diffstat is: "16 files changed, 679 insertions(+), 476 deletions(-)"
> > excluding all the changes in the testcases. This will need to
> > wait for after the release and it's not yet ready anyway, not
> > even close to.
> 
> Thanks I was wondering how complicate is the proper fix like.
> That is good to know.

Yes it's definitively not release material but I've fixed a blocking
issue, so I'll post the series soon. But for the moment, I focus
on the release.

> >
> > For the release, I also want the other fix I posted this week,
> > the one titled "fix: add missing examine in evaluate_dereference()"
> > which is much more straight-forward.
> 
> I have pull your "for-chris" branch into sparse-next.

Yes, I saw. Thanks. 

-- Luc