diff options
| author | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2018-07-05 11:34:57 +0200 |
|---|---|---|
| committer | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2018-07-25 15:17:01 +0200 |
| commit | 16d6357f2172cb78f3455cc0aeb0a64326876654 (patch) | |
| tree | 1deebe0cdeffabc9e64c2563dfb171e10dd220d7 | |
| parent | 979a731fccdad2000a19c59f5f65bfb14e025154 (diff) | |
| download | sparse-dev-16d6357f2172cb78f3455cc0aeb0a64326876654.tar.gz | |
add ptr_list_multiple()
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@gmail.com>
| -rw-r--r-- | linearize.h | 5 | ||||
| -rw-r--r-- | ptrlist.c | 21 | ||||
| -rw-r--r-- | ptrlist.h | 1 | ||||
| -rw-r--r-- | simplify.c | 2 |
4 files changed, 28 insertions, 1 deletions
diff --git a/linearize.h b/linearize.h index de42e718..b067b3e8 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); @@ -56,6 +56,27 @@ bool ptr_list_empty(const struct ptr_list *head) } /// +// 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 @@ -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 *); @@ -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; |