[PATCH] V2 move kill_unreachable_bbs to outer cse stage Was Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[PATCH] V2 move kill_unreachable_bbs to outer cse stage Was Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

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 pass the
full kernel check as well. It is likely due to I have an unclean tree of the
ptr ref count stuff.

Patch refreshed.
https://git.kernel.org/pub/scm/devel/sparse/sparse.git/log/?h=sparse-next-20170709

Thanks

Chris

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(-)

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);

Re: [PATCH] V2 move kill_unreachable_bbs to outer cse stage Was Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

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

Re: [PATCH] V2 move kill_unreachable_bbs to outer cse stage Was Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

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

Re: [PATCH] V2 move kill_unreachable_bbs to outer cse stage Was Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

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

Re: [PATCH] V2 move kill_unreachable_bbs to outer cse stage Was Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

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

Re: [PATCH] V2 move kill_unreachable_bbs to outer cse stage Was Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

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 

Re: [PATCH] V2 move kill_unreachable_bbs to outer cse stage Was Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

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.

Re: [PATCH] V2 move kill_unreachable_bbs to outer cse stage Was Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

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

Re: [PATCH] V2 move kill_unreachable_bbs to outer cse stage Was Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Luc Van Oostenryck]

> 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

Re: [PATCH] V2 move kill_unreachable_bbs to outer cse stage Was Re: [PATCH 1/5] do not corrupt ptrlist while killing unreachable BBs

[Christopher Li]

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