On Tue, Jul 24, 2018 at 11:56:01PM +0100, Ramsay Jones wrote:
>
>
> On 24/07/18 21:34, Luc Van Oostenryck wrote:
> > When an instruction can be replaced by a pseudo, the user list of
> > this pseudo and the instruction's target must be merged.
> >
> > Currently this is done by concat_ptr_list() which copy the elements
> > of one list into the other using add_ptr_list(). This incurs quite
> > a bit overhead.
> >
> > Add a new more efficient ptrlist function: copy_ptr_list() which
> > copy the element by block by looping over both list in parallel.
> >
> > This gives a speedup up to 26% on some pathological workloads.
> >
> > Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx>
> > ---
> > flow.c | 2 +-
> > ptrlist.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++
> > ptrlist.h | 1 +
> > 3 files changed, 48 insertions(+), 1 deletion(-)
> >
> > diff --git a/flow.c b/flow.c
> > index f928c2684..9483938fb 100644
> > --- a/flow.c
> > +++ b/flow.c
> > @@ -278,7 +278,7 @@ int simplify_flow(struct entrypoint *ep)
> >
> > static inline void concat_user_list(struct pseudo_user_list *src, struct pseudo_user_list **dst)
> > {
> > - concat_ptr_list((struct ptr_list *)src, (struct ptr_list **)dst);
> > + copy_ptr_list((struct ptr_list **)dst, (struct ptr_list *)src);
> > }
> >
> > void convert_instruction_target(struct instruction *insn, pseudo_t src)
> > diff --git a/ptrlist.c b/ptrlist.c
> > index c7ebf5a3f..234433033 100644
> > --- a/ptrlist.c
> > +++ b/ptrlist.c
> > @@ -340,6 +340,52 @@ void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
> > } END_FOR_EACH_PTR(entry);
> > }
> >
> > +///
> > +// copy the elements of a list at the end of another list.
> > +// @listp: a pointer to the destination list.
> > +// @src: the head of the source list.
> > +void copy_ptr_list(struct ptr_list **listp, struct ptr_list *src)
> > +{
> > + struct ptr_list *head, *tail;
> > + struct ptr_list *cur = src;
> > + int idx;
> > +
> > + if (!src)
> > + return;
> > + if (!(head = *listp))
> > + return (void) (*listp = src);
>
> cute, but I don't like this. I would prefer:
'cute'?
It's horrible! I wonder what I had in mind when I wrote this.
> head = *listp;
> if (!head) {
> *listp = src;
> return;
> }
>
> ... but it's your choice. :-)
Much better, indeed.
> > +
> > + tail = head->prev;
> > + idx = tail->nr;
> > + do {
> > + struct ptr_list *next;
>
> first 'next' (which could be initialised with cur->next).
>
> > + int nr = cur->nr;
> > + int i;
> > + for (i = 0; i < nr;) {
> > + void *ptr = cur->list[i++];
> > + if (!ptr)
> > + continue;
> > + if (idx >= LIST_NODE_NR) {
> > + struct ptr_list *next = __alloc_ptrlist(0);
>
> second 'next', which is actually the 'new_tail' (or if you
> want to be short and cute: 'newt'!)
Yes, bad naming.
> > + tail->next = next;
> > + next->prev = tail;
> > + tail->nr = idx;
> > + idx = 0;
> > + tail = next;
>
> rename all 'next' as above.
>
> > + }
> > + tail->list[idx++] = ptr;
> > + }
> > +
> > + next = cur->next;
>
> possibly remove, see above.
Yes. I prefer it here, but it doesn't really matter.
> > + __free_ptrlist(cur);> + cur = next;
> > + } while (cur != src);
>
> Hmm, hasn't 'src' been freed? (via __free_ptrlist(cur)).
Yes, src has been freed during the first iteration of this loop
but even if already reused it still correctly identifies the end
of the list.
> Maybe free the entire list after the loop, with
> __free_ptr_list(&src)? (or should that use the macro wrapper
> 'free_ptr_list' instead?).
Well, since the goal of this function is to copy lists more
efficiently, I prefer to not loop again to free them.
Thank you once more for the review.
I'll make a new version tomorrow.
-- 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
