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:
head = *listp;
if (!head) {
*listp = src;
return;
}
... but it's your choice. :-)
> +
> + 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'!)
> + 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.
> + __free_ptrlist(cur);> + cur = next;
> + } while (cur != src);
Hmm, hasn't 'src' been freed? (via __free_ptrlist(cur)).
Maybe free the entire list after the loop, with
__free_ptr_list(&src)? (or should that use the macro wrapper
'free_ptr_list' instead?).
ATB,
Ramsay Jones
> +
> + tail->nr = idx;
> + head->prev = tail;
> + tail->next = head;
> +}
> +
> ///
> // free a ptrlist
> // @listp: a pointer to the list
> diff --git a/ptrlist.h b/ptrlist.h
> index e97cdda31..46a9baee2 100644
> --- a/ptrlist.h
> +++ b/ptrlist.h
> @@ -35,6 +35,7 @@ int replace_ptr_list_entry(struct ptr_list **, void *old, void *new, int);
> extern void sort_list(struct ptr_list **, int (*)(const void *, const void *));
>
> extern void concat_ptr_list(struct ptr_list *a, struct ptr_list **b);
> +extern void copy_ptr_list(struct ptr_list **h, struct ptr_list *t);
> extern int ptr_list_size(struct ptr_list *);
> extern int linearize_ptr_list(struct ptr_list *, void **, int);
> extern void *first_ptr_list(struct ptr_list *);
>
--
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
