From a73583631cc4d7de86945b0ee713d19c067b1bb3 Mon Sep 17 00:00:00 2001
From: Dan Carpenter <dan.carpenter@oracle.com>
Date: Mon, 15 May 2017 14:41:51 +0300
Subject: [PATCH] links, var_sym: allocate fewer states

When we merge link states we end up allocating new smatch_states when we
don't need to.

The link states a list of variables we need to modify.  When we merge them
then we just combine both lists.  If one list is empty, then we don't need
to allocate a new state, we can just re-use the state we already had.  If
the lists are the same then we again don't need to allocate a new state
but can just re-use one of the earlier states.

There was some infrastructure needed to make this work.  First store the
states in sorted order so it's easier to compare two of them.  Then add a
var_sym_lists_equiv() to see if they are the same.

Signed-off-by: Dan Carpenter <dan.carpenter@oracle.com>
---
 smatch.h         |  1 +
 smatch_links.c   |  8 ++++++
 smatch_var_sym.c | 74 +++++++++++++++++++++++++++++++++++++++++++++++++++++---
 3 files changed, 80 insertions(+), 3 deletions(-)

diff --git a/smatch.h b/smatch.h
index 0febeb4b..9cd15601 100644
--- a/smatch.h
+++ b/smatch.h
@@ -390,6 +390,7 @@ int in_var_sym_list(struct var_sym_list *list, const char *var, struct symbol *s
 struct var_sym_list *clone_var_sym_list(struct var_sym_list *from_vsl);
 void merge_var_sym_list(struct var_sym_list **dest, struct var_sym_list *src);
 struct var_sym_list *combine_var_sym_lists(struct var_sym_list *one, struct var_sym_list *two);
+int var_sym_lists_equiv(struct var_sym_list *one, struct var_sym_list *two);
 void free_var_sym_list(struct var_sym_list **list);
 void free_var_syms_and_list(struct var_sym_list **list);
 
diff --git a/smatch_links.c b/smatch_links.c
index 76e2b3e9..517fecc7 100644
--- a/smatch_links.c
+++ b/smatch_links.c
@@ -51,6 +51,14 @@ struct smatch_state *merge_link_states(struct smatch_state *s1, struct smatch_st
 {
 	struct var_sym_list *new_links;
 
+	if (s1 == &undefined)
+		return s2;
+	if (s2 == &undefined)
+		return s1;
+
+	if (var_sym_lists_equiv(s1->data, s2->data))
+		return s1;
+
 	new_links = clone_var_sym_list(s1->data);
 	merge_var_sym_list(&new_links, s2->data);
 
diff --git a/smatch_var_sym.c b/smatch_var_sym.c
index 3e5f3a20..ff345988 100644
--- a/smatch_var_sym.c
+++ b/smatch_var_sym.c
@@ -63,14 +63,54 @@ struct var_sym_list *expr_to_vsl(struct expression *expr)
 	return ret;
 }
 
+int cmp_var_sym(const struct var_sym *a, const struct var_sym *b)
+{
+	int ret;
+
+	if (a == b)
+		return 0;
+	if (!b)
+		return -1;
+	if (!a)
+		return 1;
+
+	ret = strcmp(a->var, b->var);
+	if (ret < 0)
+		return -1;
+	if (ret > 0)
+		return 1;
+
+	if (!b->sym && a->sym)
+		return -1;
+	if (!a->sym && b->sym)
+		return 1;
+	if (a->sym < b->sym)
+		return -1;
+	if (a->sym > b->sym)
+		return 1;
+
+	return 0;
+}
+
 void add_var_sym(struct var_sym_list **list, const char *var, struct symbol *sym)
 {
-	struct var_sym *tmp;
+	struct var_sym *tmp, *new;
 
 	if (in_var_sym_list(*list, var, sym))
 		return;
-	tmp = alloc_var_sym(var, sym);
-	add_ptr_list(list, tmp);
+	new = alloc_var_sym(var, sym);
+
+	FOR_EACH_PTR(*list, tmp) {
+		if (cmp_var_sym(tmp, new) < 0)
+			continue;
+		else if (cmp_var_sym(tmp, new) == 0) {
+			return;
+		} else {
+			INSERT_CURRENT(new, tmp);
+			return;
+		}
+	} END_FOR_EACH_PTR(tmp);
+	add_ptr_list(list, new);
 }
 
 void add_var_sym_expr(struct var_sym_list **list, struct expression *expr)
@@ -146,6 +186,34 @@ struct var_sym_list *combine_var_sym_lists(struct var_sym_list *one, struct var_
 	return to_vsl;
 }
 
+int var_sym_lists_equiv(struct var_sym_list *one, struct var_sym_list *two)
+{
+	struct var_sym *one_tmp, *two_tmp;
+
+	if (one == two)
+		return 1;
+
+	if (ptr_list_size((struct ptr_list *)one) != ptr_list_size((struct ptr_list *)two))
+		return 0;
+
+	PREPARE_PTR_LIST(one, one_tmp);
+	PREPARE_PTR_LIST(two, two_tmp);
+	for (;;) {
+		if (!one_tmp && !two_tmp)
+			return 1;
+		if (one_tmp->sym != two_tmp->sym)
+			return 0;
+		if (strcmp(one_tmp->var, two_tmp->var) != 0)
+			return 0;
+		NEXT_PTR_LIST(one_tmp);
+		NEXT_PTR_LIST(two_tmp);
+	}
+	FINISH_PTR_LIST(two_tmp);
+	FINISH_PTR_LIST(one_tmp);
+
+	return 1;
+}
+
 void free_var_sym_list(struct var_sym_list **list)
 {
 	__free_ptr_list((struct ptr_list **)list);
-- 
2.11.4.GIT