[1/5] do not corrupt ptrlist while killing unreachable BBs

Commit Message

Christopher Li July 9, 2017, 9:07 a.m. UTC

On Thu, Jul 6, 2017 at 12:19 PM, Luc Van Oostenryck
<[e-mail]> wrote:
>
> Fix this, by adding a flag to kill_unreachable_bbs(), telling
> if it is safe to delete the BBs or if we can just mark them
> as unreachable (set bb->ep to NULL and unlink any parent and/or
> chilren), in which case the deletion will be done later.
>
> Note: the reproducer is one with very broken syntax but nothing
>       seems to forbid the same situation to happen with a valid
>       program.

I think it is simpler to move the kill not reachable bb to outer
CSE stage. The following patch has been test pass kernel compile
test. Feel free to combine that with your test as one patch.

git branch:

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

Chris

From 5234b1fcb69ade5e69ab3a528b57c8f5cea9b11e Mon Sep 17 00:00:00 2001
From: Christopher Li <[e-mail]>
Date: Sat, 8 Jul 2017 19:34:49 -0700
Subject: [PATCH 1/2] 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 <[e-mail]>
Signed-of-By: Christopher Li <[e-mail]>
---
 cse.c       | 3 +++
 flow.c      | 2 +-
 linearize.c | 3 ---
 3 files changed, 4 insertions(+), 4 deletions(-)

Comments

Luc Van Oostenryck July 9, 2017, 10:26 a.m. UTC | #1

> diff --git a/flow.c b/flow.c
> index c7161d4..5d2f15a 100644
> --- a/flow.c
> +++ b/flow.c
> @@ -841,7 +841,7 @@ void kill_unreachable_bbs(struct entrypoint *ep)
>   } END_FOR_EACH_PTR(bb);
>   PACK_PTR_LIST(&ep->bbs);
> 
> - 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.

And not removing the REPEAT_CFG_CLEANUP is an error IMO.
At the end of the function the CFG *is* clean. If you don't
clear it here, then what is its meaning?

-- Luc
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Christopher Li July 9, 2017, 2:44 p.m. UTC | #2

On Sun, Jul 9, 2017 at 3:26 AM, Luc Van Oostenryck
<[e-mail]> wrote:
>> diff --git a/flow.c b/flow.c
>> index c7161d4..5d2f15a 100644
>> --- a/flow.c
>> +++ b/flow.c
>> @@ -841,7 +841,7 @@ void kill_unreachable_bbs(struct entrypoint *ep)
>>   } END_FOR_EACH_PTR(bb);
>>   PACK_PTR_LIST(&ep->bbs);
>>
>> - 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.
OK. I will update the patch. Basically removing unreachable dead code will
impact the us


> And not removing the REPEAT_CFG_CLEANUP is an error IMO.
> At the end of the function the CFG *is* clean. If you don't
> clear it here, then what is its meaning?
It is an error as concept or it is an error the program will do wrong
things?

I want to turn REPEAT_CFG_CLEANUP usage pattern similar
to REPEAT_SYMBOL_CLEANUP. Take the a look at

if (repeat_phase & REPEAT_SYMBOL_CLEANUP)
simplify_memops(ep);

The simplify_memops does not clear the REPEAT_SYMBOL_CLEANUP
either. It was clear at the very beginning of the cse repeat loop:

repeat:
repeat_phase = 0;

I just want to be consistent with other usage of the similar flags.

It is also a reflection of my review feedback when you submit the
patch back then. One of the comment I give was that I want to
avoid calling "kill unreachable bb" multiple time within one "ep->bbs"
pass. You said there is no simple way to do it. This patch is actually
what I want back then.

I think when you introduce REPEAT_CFG_CLEANUP you have
different usage in mind. I found the flag clean at beginning of the
CSE loop is conceptually clean as well, it is simpler. The flag
is just a request, it can set more than one times. The action is
perform only once at one CSE pass.

Chris
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Luc Van Oostenryck July 9, 2017, 4:11 p.m. UTC | #3

On Sun, Jul 09, 2017 at 07:44:46AM -0700, Christopher Li wrote:
> On Sun, Jul 9, 2017 at 3:26 AM, Luc Van Oostenryck
> <[e-mail]> wrote:
> >> diff --git a/flow.c b/flow.c
> >> index c7161d4..5d2f15a 100644
> >> --- a/flow.c
> >> +++ b/flow.c
> >> @@ -841,7 +841,7 @@ void kill_unreachable_bbs(struct entrypoint *ep)
> >>   } END_FOR_EACH_PTR(bb);
> >>   PACK_PTR_LIST(&ep->bbs);
> >>
> >> - 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.
> OK. I will update the patch. Basically removing unreachable dead code will
> impact the us
> 
> 
> > And not removing the REPEAT_CFG_CLEANUP is an error IMO.
> > At the end of the function the CFG *is* clean. If you don't
> > clear it here, then what is its meaning?
> It is an error as concept or it is an error the program will do wrong
> things?

Concept.
 
> I want to turn REPEAT_CFG_CLEANUP usage pattern similar
> to REPEAT_SYMBOL_CLEANUP.


> I just want to be consistent with other usage of the similar flags.

For the other usage, the clearing of the flag (REPEAT_CSE) was done
just after the CSE was done.

You focus on the placement. I would focus on the meaning.
But it's your choice.

> I think when you introduce REPEAT_CFG_CLEANUP you have
> different usage in mind. I found the flag clean at beginning of the
> CSE loop is conceptually clean as well, it is simpler. The flag
> is just a request, it can set more than one times. The action is
> perform only once at one CSE pass.

This doesn't sound technically convincing to me, not at all.
Does the facts that:
1) it's a request flag
2) it can be set more than once
imply in any sort of way that:
1) the action is to be performed at the CSE pass and only there
2) and thus the only sane place where the flag can be cleared
   is there like the other flags?

By clearing the flag there and not at the end of the function
doing the action, you're more or less forcing the action to be
done there and only there. This may be a good enough reason to
for whishing to enforce that but then tell it, put it in a nice
comment in the code.

This is certainly not "conceptually clean as well" to me.

-- Luc
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch

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..5d2f15a 100644
--- a/flow.c
+++ b/flow.c
@@ -841,7 +841,7 @@  void kill_unreachable_bbs(struct entrypoint *ep)
  } END_FOR_EACH_PTR(bb);
  PACK_PTR_LIST(&ep->bbs);

- repeat_phase &= ~REPEAT_CFG_CLEANUP;
+ repeat_phase |=  REPEAT_CSE ;
 }

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