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 | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
ptrlist.h | 1 +
3 files changed, 51 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..684aff8c5 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -340,6 +340,55 @@ 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;
+ head = *listp;
+ if (!head) {
+ *listp = src;
+ return;
+ }
+
+ tail = head->prev;
+ idx = tail->nr;
+ do {
+ struct ptr_list *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 *prev = tail;
+ tail = __alloc_ptrlist(0);
+ prev->next = tail;
+ tail->prev = prev;
+ prev->nr = idx;
+ idx = 0;
+ }
+ tail->list[idx++] = ptr;
+ }
+
+ next = cur->next;
+ __free_ptrlist(cur);
+ cur = next;
+ } while (cur != src);
+
+ 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 *);
--
2.18.0
--
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
