On Thu, Aug 10, 2017 at 08:27:22PM -0400, Chris Li wrote:
> On Thu, Aug 10, 2017 at 7:28 PM, Luc Van Oostenryck
> <luc.vanoostenryck@xxxxxxxxx> wrote:
> >> It is pretty complicate, but do able if we really want to do it.
> >
> > Yes, it's pretty complicated. Too complicate for something that should
> > be very very simple: just add an element to a list.
>
> It is also a dare. I don't think there is much simpler way to do insert
> while looping properly in ptrlist. I welcome any one to give it a try.
> Report back if you have super clever way to do it. To define properly,
> the ptrlist looping while modify should behave as if it is a traditional
> double link list. New item add to before the current position,
> it will not show up in the loop. Insert after the current position, it will
> show up in the loop. That is for the normal direction looping.
>
> >
> > I think that sequences are only needed for instructions: bb->insns.
> > All other current use just need a 'set'.
> >
> > == For instructions ==
> > * delete is already safe (insns are just marked as ->bb = NULL)
> > * insert-at-front is only used to add death notes and this shouldn't
> > be a problem for nested ptrlist walking.
> > * concat is only used when packing BB and should be a problem
> > * add-at-end is used during linearization and some BB simplifications
> > and shouldn't be a problem either
> >
> > == For sets ==
> > * 'delete' should be done by marking the element as deleted if there
> > is a possiblity of nested ptrlist walking
> > * if 'add' is only done at the end, I don't see well how we can have
> > a problem, even with backward walking.
> > * even if somehow safe, 'add' or 'delete' operations should never be
> > done in inner ptrlist walking because the outer will become meaningless
> > if the set change (*any kind of change*) while iterating on the set
> > In other words, what would mean "do this on all elements of the set"
> > if elements are added or removed from the set while iterating on them?
> > [It may be that is some specific cases, it is meaningful but in general
> > it's not].
>
> I think that is exactly the problem with set. When you have looping
> and modify (insert for example), it is very hard to define consistent
> behavior. Should the new inserted element shows in the loop or
> not?
Yes, but again, if we see things strictly from the mathematical
point-of-view, it's not that it is hard to define behaviour, it's
simply that things are *always* inconsistent.
If you write your outer loop in mathematical language as:
for all x in <this set>: ...
things become clearer as the set is modified while the operations
are done/the properties are checked/...
*Probably* we want to have something like:
X' = { x in X ! .... } U ...
for the inner loop and thinsg are in fact OK there but for
the outer loop things are simply and plainly wrong.
> The double link list is very consistent. Consistent is good.
Double linked list is an implementation detail. It is easier to
maintain *local consistency* at the structure level. *But* ...
if this list is used the represent a set then the problem above
remains, it's not a question of implementation.
> ...
> If the compiler get different result run to run, that is bad.
It's not because a set has no ordering that the implementation
*must* create indeterminism (from run to run) when giving an order
to its elements, using an order when accessing its elements.
It just means that we can choose the order.
And yes, it's really much better if sparse can give exactly the
same behaviour from run to run, in other words: reproducible results.
It currently doesn't (for reasons I haven't yet understood) and
it is *very* annoying when comparing results between versions
at instruction level as I very often do.
-- Luc
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
