[PATCH v2 1/5] add copy_ptr_list()

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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



[Index of Archives]     [Newbies FAQ]     [LKML]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Trinity Fuzzer Tool]

  Powered by Linux