[PATCH] avoid infinite loop during simplification

[PATCH] avoid infinite loop during simplification

[Luc Van Oostenryck]

Currently, sparse can enter in infinite loops.
The effect can be seen is the normal simplification/CSE
loops but the origin of the problem is not there
(it's some interaction between simplify_loads() and
unreachable code, at least for a good part of them).

On the other hand, on normal code, the number of
simplification/CSE cycle is fairly small: even in big,
complex functions, in 80% of cases only 1 or 2 cycles are
needed. The most extreme I found was 12 cycles and that's
an unique case (on a total of 172000+).

So, avoid to let sparse in infinite loop by stopping
the loop if the number of cycles becomes too high: 16.

Note: this solves all the 77 cases of inifinite loop I found.
Note: of course, this patch doesn't change the fact that
      the generated IR is broken and that the root cause(s)
      must be addressed.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---

The patch is also available in the git repository at:
  git://github.com/lucvoo/sparse.git avoid-infinite-loop--max-cse

 cse.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/cse.c b/cse.c
index 17b3da01a..fa136c370 100644
--- a/cse.c
+++ b/cse.c
@@ -356,13 +356,17 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction
 	return i1;
 }
 
+#define	MAX_CSE_CYCLES	16
 void cleanup_and_cse(struct entrypoint *ep)
 {
+	int max = MAX_CSE_CYCLES;
 	int i;
 
 	simplify_memops(ep);
 repeat:
 	repeat_phase = 0;
+	if (--max == 0)
+		return;
 	clean_up_insns(ep);
 	if (repeat_phase & REPEAT_CFG_CLEANUP)
 		kill_unreachable_bbs(ep);
-- 
2.14.0

Re: [PATCH] avoid infinite loop during simplification

[Christopher Li]

On Sat, Aug 12, 2017 at 8:55 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Currently, sparse can enter in infinite loops.
> The effect can be seen is the normal simplification/CSE
> loops but the origin of the problem is not there
> (it's some interaction between simplify_loads() and
> unreachable code, at least for a good part of them).
>
> On the other hand, on normal code, the number of
> simplification/CSE cycle is fairly small: even in big,
> complex functions, in 80% of cases only 1 or 2 cycles are
> needed. The most extreme I found was 12 cycles and that's
> an unique case (on a total of 172000+).

That make sense.

>
> So, avoid to let sparse in infinite loop by stopping
> the loop if the number of cycles becomes too high: 16.
>
> Note: this solves all the 77 cases of inifinite loop I found.
> Note: of course, this patch doesn't change the fact that
>       the generated IR is broken and that the root cause(s)
>       must be addressed.

Of course. I am more interested in the 77 cases.

Are you considering this in this release?

>
> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> ---
>
> The patch is also available in the git repository at:
>   git://github.com/lucvoo/sparse.git avoid-infinite-loop--max-cse
>
>  cse.c | 4 ++++
>  1 file changed, 4 insertions(+)
>
> diff --git a/cse.c b/cse.c
> index 17b3da01a..fa136c370 100644
> --- a/cse.c
> +++ b/cse.c
> @@ -356,13 +356,17 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction
>         return i1;
>  }
>
> +#define        MAX_CSE_CYCLES  16
>  void cleanup_and_cse(struct entrypoint *ep)
>  {
> +       int max = MAX_CSE_CYCLES;
>         int i;
>
>         simplify_memops(ep);
>  repeat:
>         repeat_phase = 0;
> +       if (--max == 0)
> +               return;


I think we might also want to have the option that if max loop
was reached,  dump the instruction and see what the hell is going
on here. The dumping can be turn off.

Chris

Re: [PATCH] avoid infinite loop during simplification

[Christopher Li]

On Sat, Aug 12, 2017 at 9:55 AM, Christopher Li <sparse@chrisli.org> wrote:
> On Sat, Aug 12, 2017 at 8:55 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> Currently, sparse can enter in infinite loops.
>> The effect can be seen is the normal simplification/CSE
>> loops but the origin of the problem is not there
>> (it's some interaction between simplify_loads() and
>> unreachable code, at least for a good part of them).
>>
>> On the other hand, on normal code, the number of
>> simplification/CSE cycle is fairly small: even in big,
>> complex functions, in 80% of cases only 1 or 2 cycles are
>> needed. The most extreme I found was 12 cycles and that's
>> an unique case (on a total of 172000+).

There is also the other way to do it.
Every time the CFG changed, set a changed flag.
Stop CSE if there is no more change reached.

It should detect the problem that currently we think
there is opportunity to optimize, but turn out there is not.
If we keep repeating this loop, that is a bug, we need
to fix it.

Another way to look at it is, the model should be more
if we are sure there is change can be make, then we
go do the change. Current CSE scanning all instructions
looking for oppertuniity is actually not very optimal.

Chris

Re: [PATCH] avoid infinite loop during simplification

[Luc Van Oostenryck]

On Sat, Aug 12, 2017 at 4:04 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> There is also the other way to do it.
> Every time the CFG changed, set a changed flag.
> Stop CSE if there is no more change reached.

uh no.
It's exactly how it's already working now.
But it's exactly what is the problem when something
silly, caused by an internal bug, change at *each*
cycle and this it's what this patch avoid.

Of course, there is plenty of ways to do the same
or something similar or something which will have
the same result. This patch is just a very simple,
no non-sense way to do it.

-- Luc

Re: [PATCH] avoid infinite loop during simplification

[Christopher Li]

On Sat, Aug 12, 2017 at 10:22 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> uh no.
> It's exactly how it's already working now.
> But it's exactly what is the problem when something
> silly, caused by an internal bug, change at *each*
> cycle and this it's what this patch avoid.

If there is change at each cycle then the change
flag will not help. I haven't seen those dead loop
so I did not know what is the nature of those.
I assume there is also other kind of deadloop
if we think there is some thing can CSE but no
actual change to the CFG.

>
> Of course, there is plenty of ways to do the same
> or something similar or something which will have
> the same result. This patch is just a very simple,
> no non-sense way to do it.
>

Sure. It is simple enough.

Chris

Re: [PATCH] avoid infinite loop during simplification

[Luc Van Oostenryck]

On Sat, Aug 12, 2017 at 3:55 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> Are you considering this in this release?

Yes, I do.
I've another version with a tunable but this one I made for a
quick inclusion in the release.

>
> I think we might also want to have the option that if max loop
> was reached,  dump the instruction and see what the hell is going
> on here. The dumping can be turn off.

That make sense for a dev point of view but the patch is
for the users. Having the dumping done by default make
no sense for them, so this can be done later.

-- Luc

Re: [PATCH] avoid infinite loop during simplification

[Christopher Li]

On Sat, Aug 12, 2017 at 10:17 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Sat, Aug 12, 2017 at 3:55 PM, Christopher Li <sparse@chrisli.org> wrote:
>>
>> Are you considering this in this release?
>
> Yes, I do.
> I've another version with a tunable but this one I made for a
> quick inclusion in the release.


I think we need to draw the line some where.

Now RC5 is out. The merge window is closed.
It is not critical to have it. If  there is serious bug cause
RC6 then we can merge this in as well.

Otherwise I would say hold on to after the release.
We can make a minor 0.5.2 release. We don't have to
pile every thing into one release.

Let's get this 0.5.1 release out.

Chris

Re: [PATCH] avoid infinite loop during simplification

[Luc Van Oostenryck]

On Sat, Aug 12, 2017 at 4:31 PM, Christopher Li <sparse@chrisli.org> wrote:
>
> I think we need to draw the line some where.
>
> Now RC5 is out. The merge window is closed.
> It is not critical to have it.

Certainly.

> If  there is serious bug cause
> RC6 then we can merge this in as well.
>
> Otherwise I would say hold on to after the release.

That's very fine for me.

> Let's get this 0.5.1 release out.

I'm all in favor of that.

-- Luc

Re: [PATCH] avoid infinite loop during simplification

[Christopher Li]

On Sat, Aug 12, 2017 at 8:55 AM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> +       if (--max == 0)
> +               return;

I think actually here need to at least report error very loudly.
The error message should be clear there is likely a internal
bug in sparse. Hopefully the user will report back to the mailing
list.


Otherwise sparse will be silence and masking the bugs.
In that sense, having the dead loop is not that bad compare
to masking a dead loop.

Silently work around the bug will hurt sparse in the long term.

Chris

Re: [PATCH] avoid infinite loop during simplification

[Luc Van Oostenryck]

On Sat, Aug 12, 2017 at 5:26 PM, Christopher Li <sparse@chrisli.org> wrote:
> On Sat, Aug 12, 2017 at 8:55 AM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> +       if (--max == 0)
>> +               return;
>
> I think actually here need to at least report error very loudly.
> The error message should be clear there is likely a internal
> bug in sparse. Hopefully the user will report back to the mailing
> list.
>
>
> Otherwise sparse will be silence and masking the bugs.
> In that sense, having the dead loop is not that bad compare
> to masking a dead loop.
>
> Silently work around the bug will hurt sparse in the long term.

No disagreement here.

-- Luc