[PATCH v2 3/5] add ptr_list_multiple()

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

 



When doing IR simplification, to know if an instruction can be
destructively modified, it's needed to know if the pseudo it defines
is used by a single instruction or not. Currently this is done using
ptr_list_size() which needs to walk the whole list.

This walk is relatively costly when the list is long but knowing
if the list contains more than 1 element can often be answered
more cheaply since an answer can be returned as soon as it's
known that the list contains at least 2 elements.

Add the helpers ptr_list_multiple() and multi_users().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@xxxxxxxxx>
---
 linearize.h |  5 +++++
 ptrlist.c   | 21 +++++++++++++++++++++
 ptrlist.h   |  1 +
 simplify.c  |  2 +-
 4 files changed, 28 insertions(+), 1 deletion(-)

diff --git a/linearize.h b/linearize.h
index de42e718d..b067b3e84 100644
--- a/linearize.h
+++ b/linearize.h
@@ -343,6 +343,11 @@ static inline int has_users(pseudo_t p)
 	return !pseudo_user_list_empty(p->users);
 }
 
+static inline bool multi_users(pseudo_t p)
+{
+	return ptr_list_multiple((struct ptr_list *)(p->users));
+}
+
 static inline struct pseudo_user *alloc_pseudo_user(struct instruction *insn, pseudo_t *pp)
 {
 	struct pseudo_user *user = __alloc_pseudo_user(0);
diff --git a/ptrlist.c b/ptrlist.c
index 356785dfc..ae00b5134 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -55,6 +55,27 @@ bool ptr_list_empty(const struct ptr_list *head)
 	return true;
 }
 
+///
+// test is a list contains more than one element
+// @head: the head of the list
+// @return: ``true`` if the list has more than 1 element, ``false`` otherwise.
+bool ptr_list_multiple(const struct ptr_list *head)
+{
+	const struct ptr_list *list = head;
+	int nr = 0;
+
+	if (!head)
+		return false;
+
+	do {
+		nr += list->nr - list->rm;
+		if (nr > 1)
+			return true;
+	} while ((list = list->next) != head);
+
+	return false;
+}
+
 ///
 // get the first element of a ptrlist
 // @head: the head of the list
diff --git a/ptrlist.h b/ptrlist.h
index f145bc5f1..176bb0712 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -39,6 +39,7 @@ 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 bool ptr_list_empty(const struct ptr_list *head);
+extern bool ptr_list_multiple(const struct ptr_list *head);
 extern int linearize_ptr_list(struct ptr_list *, void **, int);
 extern void *first_ptr_list(struct ptr_list *);
 extern void *last_ptr_list(struct ptr_list *);
diff --git a/simplify.c b/simplify.c
index 4dc24a505..65f29de0a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -824,7 +824,7 @@ static int simplify_associative_binop(struct instruction *insn)
 		return 0;
 	if (!simple_pseudo(def->src2))
 		return 0;
-	if (pseudo_user_list_size(def->target->users) != 1)
+	if (multi_users(def->target))
 		return 0;
 	switch_pseudo(def, &def->src1, insn, &insn->src2);
 	return REPEAT_CSE;
-- 
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