| Message ID | 20170812125525.34044-1-luc.vanoostenryck@gmail.com (mailing list archive) |
|---|---|
| State | Superseded, archived |
| Headers | show |
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 -- 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
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 -- 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
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 -- 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
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 -- 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
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 -- 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
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 -- 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
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 -- 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
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 -- 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
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 -- 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
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);
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(+)