| Message ID | CANeU7QkCcx1d29megDn9bQ0g7rw04=ujsWCe_bN1Kc1NW_-NZw@mail.gmail.com (mailing list archive) |
|---|---|
| State | Rejected, archived |
| Headers | show |
On Sun, Jul 09, 2017 at 09:07:06AM -0700, Christopher Li wrote: > On Sun, Jul 9, 2017 at 3:26 AM, Luc Van Oostenryck > <luc.vanoostenryck@gmail.com> wrote: > >> > >> - repeat_phase &= ~REPEAT_CFG_CLEANUP; > >> + repeat_phase |= REPEAT_CSE ; > > > > It would be good to add a comment for why the '|= REPEAT_CSE' is needed here. > > > > You are right. > > Actually I just find out that is not needed. I was having impression that I > need that to pass one of the test-suit. It seems fine without. It could have made a difference in the test suite because killing unreachable code can create new simplification opportunities. > It pass the > full kernel check as well. What do you mean exactly by 'pass full kernel check'? That you get exactly the same warnings with & without the patch? > From 484a3a27d95b4bf3be9ac4b9bcf1aca1abe3ac19 Mon Sep 17 00:00:00 2001 > From: Christopher Li <sparse@chrisli.org> > Date: Sat, 8 Jul 2017 19:34:49 -0700 > Subject: [PATCH] move kill_unreachable_bbs to outer cse stage > > The current way of kill_unreach_bbs in insert_branch() > cause delete entry in ptrlist that the upper level > caller is looping on. I know what you're talking about but otherwise, I really can't parse this sentence. Anyway, I think that this bug merit a much better commit message. It would also be nice to know why the patch that came with the bug report have been discarded without a single comment. -- 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 Sun, Jul 9, 2017 at 9:52 AM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > > It could have made a difference in the test suite because killing > unreachable code can create new simplification opportunities. Yes. As far as I can tell, when the kill instruction get invoked, it should have cause the REPEAT_CSE. "Kill unreachable bb" shouldn't need to set CSE flag. > What do you mean exactly by 'pass full kernel check'? That you get > exactly the same warnings with & without the patch? Yes, that is what I usually do to give sparse some workload other than the test-suite. > >> From 484a3a27d95b4bf3be9ac4b9bcf1aca1abe3ac19 Mon Sep 17 00:00:00 2001 >> From: Christopher Li <sparse@chrisli.org> >> Date: Sat, 8 Jul 2017 19:34:49 -0700 >> Subject: [PATCH] move kill_unreachable_bbs to outer cse stage >> >> The current way of kill_unreach_bbs in insert_branch() >> cause delete entry in ptrlist that the upper level >> caller is looping on. > > I know what you're talking about but otherwise, I really can't parse > this sentence. > > Anyway, I think that this bug merit a much better commit message. > Of course. Can you take my patch and merge it with your validation test? Do what you see fit. I think it'd better commit together, and get a better commit message. I was overwhelming by the ptr ref counting. I need some thing in my branch to stop die on those ep->bbs. > It would also be nice to know why the patch that came with the bug > report have been discarded without a single comment. Sorry I haven't been more specific. I think the original patch is a bit too complicated. Also just as I suspected, there is more than the bb list get affected. If possible, I think we should try to avoid get into nested loop delete in the first place rather than make the nested loop delete work. 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 Sun, Jul 09, 2017 at 05:19:27PM -0700, Christopher Li wrote: > On Sun, Jul 9, 2017 at 9:52 AM, Luc Van Oostenryck > <luc.vanoostenryck@gmail.com> wrote: > > > > It could have made a difference in the test suite because killing > > unreachable code can create new simplification opportunities. > > Yes. As far as I can tell, when the kill instruction get invoked, it should > have cause the REPEAT_CSE. "Kill unreachable bb" shouldn't need > to set CSE flag. > > > What do you mean exactly by 'pass full kernel check'? That you get > > exactly the same warnings with & without the patch? > > Yes, that is what I usually do to give sparse some workload other > than the test-suite. OK. > > It would also be nice to know why the patch that came with the bug > > report have been discarded without a single comment. > > Sorry I haven't been more specific. I think the original patch is a bit > too complicated. Also just as I suspected, there is more than the bb > list get affected. If possible, I think we should try to avoid get into nested > loop delete in the first place rather than make the nested loop delete > work. I can hardly qualify my patch as 'complicated' but well ... This patch have been done with two goals in mind: 1) solve the problem with the deleted BB 2) do not change anything at the simplification since interaction between differents parts there can have bad effects (it's to fix a problem there that the kill_unreachable_bbs() had been added). Your patch, take care of point 1) but not 2) and effectively change when the BBs are removed and this change the interaction between insert_branch() and some others parts. I have given a run of some of my tests I run here and there is indeed some changes. Most of these changes are obviously correct. Some are not obvious at all and would need to be investigated. Some look scary (and of course would need to be investigated too). In short, I can't guarantee that the "crazy programmer" problem won't come back or that a similar one haven't been created. > Also just as I suspected, there is more than the bb > list get affected. Sure, but this have nothing to do with the choice of patches here since your pacth also just tak ecare of the deleted BBs from the inner kill_unreachable_bbs(). > If possible, I think we should try to avoid get into nested > loop delete in the first place rather than make the nested loop delete > work. This seems an obvious and easy way to avoid problems but this won't something that will be sustainable. It would put a huge constraint on what can be done and what can't done, which is why, of course, I earlier suggested to instead change the way elements are 'deleted' (like instructions are already never removed from their list but just marked as deleted). -- 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 Mon, Jul 10, 2017 at 12:05 AM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: >> > It would also be nice to know why the patch that came with the bug >> > report have been discarded without a single comment. >> >> Sorry I haven't been more specific. I think the original patch is a bit >> too complicated. Also just as I suspected, there is more than the bb >> list get affected. If possible, I think we should try to avoid get into nested >> loop delete in the first place rather than make the nested loop delete >> work. > > I can hardly qualify my patch as 'complicated' but well ... > This patch have been done with two goals in mind: > 1) solve the problem with the deleted BB > 2) do not change anything at the simplification since interaction > between differents parts there can have bad effects (it's to fix > a problem there that the kill_unreachable_bbs() had been added). > > Your patch, take care of point 1) but not 2) and effectively > change when the BBs are removed and this change the interaction > between insert_branch() and some others parts. You are right. I will never consider 2) as my goal. Simply because if the compiler has to depend on certain order of optimization (delete dead BB vs memops, CSE) and it can't figure out the order by itself. Then I consider a bug in the compiler. > I have given a run of some of my tests I run here and there > is indeed some changes. > Most of these changes are obviously correct. > Some are not obvious at all and would need to be investigated. > Some look scary (and of course would need to be investigated too). Great to have you looking at those. That is why I want to get your insight on this. > In short, I can't guarantee that the "crazy programmer" problem > won't come back or that a similar one haven't been created. Nobody can.That "crazy programmer" fix is not even a complete fix. We will need to work on it any way. > Sure, but this have nothing to do with the choice of patches here > since your pacth also just tak ecare of the deleted BBs from the > inner kill_unreachable_bbs(). It does in my thinking process. If there is other list involved, then we need to look for other solutions for those. That other solution might work on the BB list as well. There for, I don't want to invest too much into this temporary change, especially the API change of kill unreachable BB. >> If possible, I think we should try to avoid get into nested >> loop delete in the first place rather than make the nested loop delete >> work. > > This seems an obvious and easy way to avoid problems but this won't > something that will be sustainable. It would put a huge constraint > on what can be done and what can't done, which is why, of course, I would not rule out that possibility so quickly without consider it. For example, we can design the optimization process using work queue to defer certain things do be done outside of the loop. There are many different things we can do to solve the problem. If nested loop deleted can be avoided, that is likely cheaper and less complicate. > I earlier suggested to instead change the way elements are 'deleted' > (like instructions are already never removed from their list but > just marked as deleted). That looks simple but it has hidden complications as well. The issue is that we need to find out which list need this kind of special treatment. Who is the outer loop. If the same function can be both call as the outer loop and inner loop then it is complicate to decide when it should do the finalize. There is also the price to pay for walking the list twice which does not exist if nested loop can be avoided. 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 Mon, Jul 10, 2017 at 06:21:22AM -0700, Christopher Li wrote: > On Mon, Jul 10, 2017 at 12:05 AM, Luc Van Oostenryck > <luc.vanoostenryck@gmail.com> wrote: > >> > It would also be nice to know why the patch that came with the bug > >> > report have been discarded without a single comment. > >> > >> Sorry I haven't been more specific. I think the original patch is a bit > >> too complicated. Also just as I suspected, there is more than the bb > >> list get affected. If possible, I think we should try to avoid get into nested > >> loop delete in the first place rather than make the nested loop delete > >> work. > > > > I can hardly qualify my patch as 'complicated' but well ... > > This patch have been done with two goals in mind: > > 1) solve the problem with the deleted BB > > 2) do not change anything at the simplification since interaction > > between differents parts there can have bad effects (it's to fix > > a problem there that the kill_unreachable_bbs() had been added). > > > > Your patch, take care of point 1) but not 2) and effectively > > change when the BBs are removed and this change the interaction > > between insert_branch() and some others parts. > > You are right. I will never consider 2) as my goal. Simply because > if the compiler has to depend on certain order of optimization (delete > dead BB vs memops, CSE) and it can't figure out the order by itself. > Then I consider a bug in the compiler. You may qualify this as a bug but in the real world it's totally normal to have interactions between optimization passes (yes, this means that the result will depend on the order of the passes). This is especially true when it concern dead code elimination. Any decent compiler book will tell you a bit more about this. But well, you're the maintainer, it's your responsability to make the good choices for the project. -- Luc Van Oostenryck -- 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 Tue, Jul 11, 2017 at 2:26 AM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: >> >> You are right. I will never consider 2) as my goal. Simply because >> if the compiler has to depend on certain order of optimization (delete >> dead BB vs memops, CSE) and it can't figure out the order by itself. >> Then I consider a bug in the compiler. > > You may qualify this as a bug but in the real world it's totally > normal to have interactions between optimization passes (yes, this > means that the result will depend on the order of the passes). > This is especially true when it concern dead code elimination. > > Any decent compiler book will tell you a bit more about this. OK. Apparently I haven't read any decent compiler books yet, that is why I am not a good maintainer. My sentence have two parts. You only read the first part about the ordering. The second part you seem missing is that, if the order make a difference, *and* the compiler can't to figure out a the (optimal) order by itself, that is a bug. It is just command sense. If I re-order my C source file with some goto and moving code blocks around. The C compiler should generate pretty much the same optimal code in the end. If your investigation of comparing two approach to compile the same source code, your patch generate better result. Then we need to look at it. That might be reason to use your patch. Maybe there is some other simple way to modify my patch to generate as good a result as well. Do you have any example you believe my simpler approach will generate worse code then your not so complicate approach? > But well, you're the maintainer, it's your responsability to > make the good choices for the project. Of course. I try really hard to make the right choice. I can only make decision base on the information I have in hand. So far you haven't conclude your investigation that the simpler approach will generate worse code. You said it is different, different can be better or be worse. If it turn out to be different but equivalent, then why not just use the simpler approach? If it is not, then let's look at why this pack blocks earlier will make code better. Make some adjustment in the code, possible remove dead block earlier like your patch suggested. Chris PS, Any decent compiler book you want to recommend? I want to see it. -- 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 Mon, Jul 10, 2017 at 12:05 AM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote:> > I have given a run of some of my tests I run here and there > is indeed some changes. > Most of these changes are obviously correct. > Some are not obvious at all and would need to be investigated. > Some look scary (and of course would need to be investigated too). Haven't heard from you for a while. Can you post some of your scary part of the generated code change? I can take a look as well. I hope we can solve that with finding missing optimization opportunity. e.g. Adding CSE flag some where. Any way, now both nest loop related bug has some patch for review. I will make a RC5 soon. I would love to get more of your feed back, especially the ep->bbs one. If any adjustment needs to make, now it is the time. Thanks 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
> From 484a3a27d95b4bf3be9ac4b9bcf1aca1abe3ac19 Mon Sep 17 00:00:00 2001 > From: Christopher Li <sparse@chrisli.org> > Date: Sat, 8 Jul 2017 19:34:49 -0700 > Subject: [PATCH] move kill_unreachable_bbs to outer cse stage > > The current way of kill_unreach_bbs in insert_branch() > cause delete entry in ptrlist that the upper level > caller is looping on. > > Move it outside to the cse stage avoid that problem. > > Reported-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> > Signed-of-By: Christopher Li <sparse@chrisli.org> > --- > cse.c | 3 +++ > flow.c | 2 -- > linearize.c | 3 --- > 3 files changed, 3 insertions(+), 5 deletions(-) The original patch had a testcase for the regressions testsuite. Is there a reasons why there it has been dropped here? The original patch had a reference to the patch it fixed, which is quite helpful to understand the exact situation. Is there a reason why it has been dropped 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
On Wed, Jul 19, 2017 at 4:48 PM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > > The original patch had a testcase for the regressions testsuite. > Is there a reasons why there it has been dropped here? > > The original patch had a reference to the patch it fixed, > which is quite helpful to understand the exact situation. > Is there a reason why it has been dropped here? Nope, I was hoping your can merge the patch with your test case and resubmit as a combine patch. I haven't heard from you so far so that is what I have. It feel wrong for me to take your test case and submit as mine. Again I consider my change just an alternative incremental change build on top of yours. If you want to improve the commit message or comment on the source, I am all for it. I am glad to see that. I haven't push my change to master for that reason. On the other hand, I can't hold the release for ever. 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
diff --git a/cse.c b/cse.c index 0d3815c..af9863f 100644 --- a/cse.c +++ b/cse.c @@ -387,6 +387,9 @@ repeat: } } + if (repeat_phase & REPEAT_CFG_CLEANUP) + kill_unreachable_bbs(ep); + if (repeat_phase & REPEAT_SYMBOL_CLEANUP) simplify_memops(ep); diff --git a/flow.c b/flow.c index c7161d4..fce8bde 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 7313e72..a367207 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); }