[v2,4/5] add lookup_ptr_list_entry()

Commit Message

Luc Van Oostenryck July 25, 2018, 8:44 p.m. UTC

For liveness analysis, the ptrlists need to be used as sets. IOW,
before adding a new element, it's needed to check if it doesn't
already belong to the list.

This check is currently done, specifically for pseudos,  using the
list walking macros FOR_EACH_PTR/END_FOR_EACH_PTR.

Add a new generic ptrlist function: lookup_ptr_list_entry() which
test if a given pointer already belong to the list.

Signed-off-by: Luc Van Oostenryck <[e-mail]>
---
 linearize.h |  5 +++++
 liveness.c  |  9 ---------
 ptrlist.c   | 21 +++++++++++++++++++++
 ptrlist.h   |  1 +
 4 files changed, 27 insertions(+), 9 deletions(-)

Patch

diff --git a/linearize.h b/linearize.h
index b067b3e84..63a51ff35 100644
--- a/linearize.h
+++ b/linearize.h
@@ -303,6 +303,11 @@  static inline int remove_pseudo(struct pseudo_list **list, pseudo_t pseudo)
 	return delete_ptr_list_entry((struct ptr_list **)list, pseudo, 0) != 0;
 }
 
+static inline int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo)
+{
+	return lookup_ptr_list_entry((struct ptr_list *)list, pseudo);
+}
+
 static inline int bb_terminated(struct basic_block *bb)
 {
 	struct instruction *insn;
diff --git a/liveness.c b/liveness.c
index 4c3339f10..d1968ce4b 100644
--- a/liveness.c
+++ b/liveness.c
@@ -139,15 +139,6 @@  static void track_instruction_usage(struct basic_block *bb, struct instruction *
 	}
 }
 
-int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo)
-{
-	pseudo_t old;
-	FOR_EACH_PTR(list,old) {
-		if (old == pseudo)
-			return 1;
-	} END_FOR_EACH_PTR(old);   
-	return 0;
-}
 
 static int liveness_changed;
 
diff --git a/ptrlist.c b/ptrlist.c
index ae00b5134..3677a347c 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -272,6 +272,27 @@  void **__add_ptr_list_tag(struct ptr_list **listp, void *ptr, unsigned long tag)
 	return __add_ptr_list(listp, ptr);
 }
 
+///
+// test if some entry is already present in a ptrlist
+// @list: the head of the list
+// @entry: the entry to test
+// @return: ``true`` if the entry is already present, ``false`` otherwise.
+bool lookup_ptr_list_entry(const struct ptr_list *head, const void *entry)
+{
+	const struct ptr_list *list = head;
+
+	if (!head)
+		return false;
+	do {
+		int nr = list->nr;
+		int i;
+		for (i = 0; i < nr; i++)
+			if (list->list[i] == entry)
+				return true;
+	} while ((list = list->next) != head);
+	return false;
+}
+
 ///
 // delete an entry from a ptrlist
 // @list: a pointer to the list
diff --git a/ptrlist.h b/ptrlist.h
index 176bb0712..2f0234784 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -33,6 +33,7 @@  void * undo_ptr_list_last(struct ptr_list **head);
 void * delete_ptr_list_last(struct ptr_list **head);
 int delete_ptr_list_entry(struct ptr_list **, void *, int);
 int replace_ptr_list_entry(struct ptr_list **, void *old, void *new, int);
+bool lookup_ptr_list_entry(const struct ptr_list *head, const void *entry);
 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);