aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
authorLuc Van Oostenryck <luc.vanoostenryck@gmail.com>2018-08-04 22:52:37 +0200
committerLuc Van Oostenryck <luc.vanoostenryck@gmail.com>2018-08-04 22:55:24 +0200
commitc22d39ec3768b210ba5ab6110c5f311980f8fb1a (patch)
tree882ee46f937b58506aca0981294a302d13f8e194
parent8a852bf56850a0135e0e50cbc141fafce910d258 (diff)
parenta4fb469ca61a9262361a252e8211f8ea0f67f1fa (diff)
downloadsparse-dev-c22d39ec3768b210ba5ab6110c5f311980f8fb1a.tar.gz
Merge branch 'list-optims' (early part) into tip
* add optimized version of some list operations Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
Diffstat
-rw-r--r--flow.c2
-rw-r--r--linearize.h17
-rw-r--r--liveness.c9
-rw-r--r--ptrlist.c110
-rw-r--r--ptrlist.h5
-rw-r--r--simplify.c4
6 files changed, 134 insertions, 13 deletions
diff --git a/flow.c b/flow.c
index f928c268..9483938f 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/linearize.h b/linearize.h
index 2bd6185a..1184df98 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;
@@ -333,9 +338,19 @@ static inline int pseudo_user_list_size(struct pseudo_user_list *list)
return ptr_list_size((struct ptr_list *)list);
}
+static inline bool pseudo_user_list_empty(struct pseudo_user_list *list)
+{
+ return ptr_list_empty((struct ptr_list *)list);
+}
+
static inline int has_users(pseudo_t p)
{
- return pseudo_user_list_size(p->users) != 0;
+ 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 int nbr_users(pseudo_t p)
diff --git a/liveness.c b/liveness.c
index 4c3339f1..d1968ce4 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 c7ebf5a3..3677a347 100644
--- a/ptrlist.c
+++ b/ptrlist.c
@@ -37,6 +37,46 @@ int ptr_list_size(struct ptr_list *head)
}
///
+// test if a list is empty
+// @head: the head of the list
+// @return: ``true`` if the list is empty, ``false`` otherwise.
+bool ptr_list_empty(const struct ptr_list *head)
+{
+ const struct ptr_list *list = head;
+
+ if (!head)
+ return true;
+
+ do {
+ if (list->nr - list->rm)
+ return false;
+ } while ((list = list->next) != 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
// @return: the first element of the list or ``NULL`` if the list is empty
@@ -233,6 +273,27 @@ void **__add_ptr_list_tag(struct ptr_list **listp, void *ptr, unsigned long tag)
}
///
+// 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
// @entry: the item to be deleted
@@ -341,6 +402,55 @@ void concat_ptr_list(struct ptr_list *a, struct ptr_list **b)
}
///
+// 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
// Each blocks of the list are freed (but the entries
diff --git a/ptrlist.h b/ptrlist.h
index e97cdda3..2f023478 100644
--- a/ptrlist.h
+++ b/ptrlist.h
@@ -2,6 +2,7 @@
#define PTR_LIST_H
#include <stdlib.h>
+#include <stdbool.h>
/*
* Generic pointer list manipulation code.
@@ -32,10 +33,14 @@ 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);
+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 b28d9375..57e90b9b 100644
--- a/simplify.c
+++ b/simplify.c
@@ -179,7 +179,7 @@ static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_
} END_FOR_EACH_PTR(pu);
assert(count <= 0);
out:
- if (pseudo_user_list_size(*list) == 0)
+ if (pseudo_user_list_empty(*list))
*list = NULL;
return count;
}
@@ -968,7 +968,7 @@ static int simplify_associative_binop(struct instruction *insn)
return 0;
if (!simple_pseudo(def->src2))
return 0;
- if (nbr_users(def->target) != 1)
+ if (multi_users(def->target))
return 0;
switch_pseudo(def, &def->src1, insn, &insn->src2);
return REPEAT_CSE;
generated by cgit 1.2.3-korg (git 2.43.0) at 2026-03-01 19:52:15 +0000