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
