11f5207b7SJohn Levon /*
21f5207b7SJohn Levon  * Copyright (C) 2008,2009 Dan Carpenter.
31f5207b7SJohn Levon  *
41f5207b7SJohn Levon  * This program is free software; you can redistribute it and/or
51f5207b7SJohn Levon  * modify it under the terms of the GNU General Public License
61f5207b7SJohn Levon  * as published by the Free Software Foundation; either version 2
71f5207b7SJohn Levon  * of the License, or (at your option) any later version.
81f5207b7SJohn Levon  *
91f5207b7SJohn Levon  * This program is distributed in the hope that it will be useful,
101f5207b7SJohn Levon  * but WITHOUT ANY WARRANTY; without even the implied warranty of
111f5207b7SJohn Levon  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
121f5207b7SJohn Levon  * GNU General Public License for more details.
131f5207b7SJohn Levon  *
141f5207b7SJohn Levon  * You should have received a copy of the GNU General Public License
151f5207b7SJohn Levon  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
161f5207b7SJohn Levon  */
171f5207b7SJohn Levon 
181f5207b7SJohn Levon #include <stdlib.h>
191f5207b7SJohn Levon #include <stdio.h>
201f5207b7SJohn Levon #include "smatch.h"
211f5207b7SJohn Levon #include "smatch_slist.h"
221f5207b7SJohn Levon 
231f5207b7SJohn Levon #undef CHECKORDER
241f5207b7SJohn Levon 
251f5207b7SJohn Levon ALLOCATOR(smatch_state, "smatch state");
261f5207b7SJohn Levon ALLOCATOR(sm_state, "sm state");
271f5207b7SJohn Levon ALLOCATOR(named_stree, "named slist");
281f5207b7SJohn Levon __DO_ALLOCATOR(char, 1, 4, "state names", sname);
291f5207b7SJohn Levon 
301f5207b7SJohn Levon int sm_state_counter;
311f5207b7SJohn Levon 
321f5207b7SJohn Levon static struct stree_stack *all_pools;
331f5207b7SJohn Levon 
show_sm(struct sm_state * sm)341f5207b7SJohn Levon const char *show_sm(struct sm_state *sm)
351f5207b7SJohn Levon {
361f5207b7SJohn Levon 	static char buf[256];
371f5207b7SJohn Levon 	struct sm_state *tmp;
381f5207b7SJohn Levon 	int pos;
391f5207b7SJohn Levon 	int i;
401f5207b7SJohn Levon 
411f5207b7SJohn Levon 	if (!sm)
421f5207b7SJohn Levon 		return "<none>";
431f5207b7SJohn Levon 
44c85f09ccSJohn Levon 	pos = snprintf(buf, sizeof(buf), "[%s] %s = '%s'%s",
45c85f09ccSJohn Levon 		       check_name(sm->owner), sm->name, show_state(sm->state),
46c85f09ccSJohn Levon 		       sm->merged ? " [merged]" : "");
471f5207b7SJohn Levon 	if (pos > sizeof(buf))
481f5207b7SJohn Levon 		goto truncate;
491f5207b7SJohn Levon 
501f5207b7SJohn Levon 	if (ptr_list_size((struct ptr_list *)sm->possible) == 1)
511f5207b7SJohn Levon 		return buf;
521f5207b7SJohn Levon 
531f5207b7SJohn Levon 	pos += snprintf(buf + pos, sizeof(buf) - pos, " (");
541f5207b7SJohn Levon 	if (pos > sizeof(buf))
551f5207b7SJohn Levon 		goto truncate;
561f5207b7SJohn Levon 	i = 0;
571f5207b7SJohn Levon 	FOR_EACH_PTR(sm->possible, tmp) {
581f5207b7SJohn Levon 		if (i++)
591f5207b7SJohn Levon 			pos += snprintf(buf + pos, sizeof(buf) - pos, ", ");
601f5207b7SJohn Levon 		if (pos > sizeof(buf))
611f5207b7SJohn Levon 			goto truncate;
621f5207b7SJohn Levon 		pos += snprintf(buf + pos, sizeof(buf) - pos, "%s",
631f5207b7SJohn Levon 			       show_state(tmp->state));
641f5207b7SJohn Levon 		if (pos > sizeof(buf))
651f5207b7SJohn Levon 			goto truncate;
661f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
671f5207b7SJohn Levon 	snprintf(buf + pos, sizeof(buf) - pos, ")");
681f5207b7SJohn Levon 
691f5207b7SJohn Levon 	return buf;
701f5207b7SJohn Levon 
711f5207b7SJohn Levon truncate:
721f5207b7SJohn Levon 	for (i = 0; i < 3; i++)
731f5207b7SJohn Levon 		buf[sizeof(buf) - 2 - i] = '.';
741f5207b7SJohn Levon 	return buf;
751f5207b7SJohn Levon }
761f5207b7SJohn Levon 
__print_stree(struct stree * stree)771f5207b7SJohn Levon void __print_stree(struct stree *stree)
781f5207b7SJohn Levon {
791f5207b7SJohn Levon 	struct sm_state *sm;
801f5207b7SJohn Levon 
8131ad075eSJohn Levon 	option_debug++;
8231ad075eSJohn Levon 	sm_msg("dumping stree [%ld states]", stree_count(stree));
831f5207b7SJohn Levon 	FOR_EACH_SM(stree, sm) {
8431ad075eSJohn Levon 		sm_printf("%s\n", show_sm(sm));
851f5207b7SJohn Levon 	} END_FOR_EACH_SM(sm);
8631ad075eSJohn Levon 	sm_printf("---\n");
8731ad075eSJohn Levon 	option_debug--;
881f5207b7SJohn Levon }
891f5207b7SJohn Levon 
901f5207b7SJohn Levon /* NULL states go at the end to simplify merge_slist */
cmp_tracker(const struct sm_state * a,const struct sm_state * b)911f5207b7SJohn Levon int cmp_tracker(const struct sm_state *a, const struct sm_state *b)
921f5207b7SJohn Levon {
931f5207b7SJohn Levon 	int ret;
941f5207b7SJohn Levon 
951f5207b7SJohn Levon 	if (a == b)
961f5207b7SJohn Levon 		return 0;
971f5207b7SJohn Levon 	if (!b)
981f5207b7SJohn Levon 		return -1;
991f5207b7SJohn Levon 	if (!a)
1001f5207b7SJohn Levon 		return 1;
1011f5207b7SJohn Levon 
1021f5207b7SJohn Levon 	if (a->owner < b->owner)
103efe51d0cSJohn Levon 		return -1;
104efe51d0cSJohn Levon 	if (a->owner > b->owner)
1051f5207b7SJohn Levon 		return 1;
1061f5207b7SJohn Levon 
1071f5207b7SJohn Levon 	ret = strcmp(a->name, b->name);
1081f5207b7SJohn Levon 	if (ret < 0)
1091f5207b7SJohn Levon 		return -1;
1101f5207b7SJohn Levon 	if (ret > 0)
1111f5207b7SJohn Levon 		return 1;
1121f5207b7SJohn Levon 
1131f5207b7SJohn Levon 	if (!b->sym && a->sym)
1141f5207b7SJohn Levon 		return -1;
1151f5207b7SJohn Levon 	if (!a->sym && b->sym)
1161f5207b7SJohn Levon 		return 1;
1171f5207b7SJohn Levon 	if (a->sym < b->sym)
1181f5207b7SJohn Levon 		return -1;
1191f5207b7SJohn Levon 	if (a->sym > b->sym)
1201f5207b7SJohn Levon 		return 1;
1211f5207b7SJohn Levon 
1221f5207b7SJohn Levon 	return 0;
1231f5207b7SJohn Levon }
1241f5207b7SJohn Levon 
125efe51d0cSJohn Levon int *dynamic_states;
allocate_dynamic_states_array(int num_checks)126efe51d0cSJohn Levon void allocate_dynamic_states_array(int num_checks)
127efe51d0cSJohn Levon {
128efe51d0cSJohn Levon 	dynamic_states = calloc(num_checks + 1, sizeof(int));
129efe51d0cSJohn Levon }
130efe51d0cSJohn Levon 
set_dynamic_states(unsigned short owner)131efe51d0cSJohn Levon void set_dynamic_states(unsigned short owner)
132efe51d0cSJohn Levon {
133efe51d0cSJohn Levon 	dynamic_states[owner] = true;
134efe51d0cSJohn Levon }
135efe51d0cSJohn Levon 
has_dynamic_states(unsigned short owner)136efe51d0cSJohn Levon bool has_dynamic_states(unsigned short owner)
137efe51d0cSJohn Levon {
138efe51d0cSJohn Levon 	if (owner >= num_checks)
139efe51d0cSJohn Levon 		return false;
140efe51d0cSJohn Levon 	return dynamic_states[owner];
141efe51d0cSJohn Levon }
142efe51d0cSJohn Levon 
cmp_possible_sm(const struct sm_state * a,const struct sm_state * b,int preserve)143efe51d0cSJohn Levon static int cmp_possible_sm(const struct sm_state *a, const struct sm_state *b, int preserve)
1441f5207b7SJohn Levon {
1451f5207b7SJohn Levon 	int ret;
1461f5207b7SJohn Levon 
147efe51d0cSJohn Levon 	if (a == b)
148efe51d0cSJohn Levon 		return 0;
1491f5207b7SJohn Levon 
150efe51d0cSJohn Levon 	if (!has_dynamic_states(a->owner)) {
151efe51d0cSJohn Levon 		if (a->state > b->state)
1521f5207b7SJohn Levon 			return -1;
153efe51d0cSJohn Levon 		if (a->state < b->state)
1541f5207b7SJohn Levon 			return 1;
155efe51d0cSJohn Levon 		return 0;
1561f5207b7SJohn Levon 	}
1571f5207b7SJohn Levon 
158efe51d0cSJohn Levon 	if (a->owner == SMATCH_EXTRA) {
159efe51d0cSJohn Levon 		/*
160efe51d0cSJohn Levon 		 * In Smatch extra you can have borrowed implications.
161efe51d0cSJohn Levon 		 *
162efe51d0cSJohn Levon 		 * FIXME: review how borrowed implications work and if they
163efe51d0cSJohn Levon 		 * are the best way.  See also smatch_implied.c.
164efe51d0cSJohn Levon 		 *
165efe51d0cSJohn Levon 		 */
166efe51d0cSJohn Levon 		ret = cmp_tracker(a, b);
167efe51d0cSJohn Levon 		if (ret)
168efe51d0cSJohn Levon 			return ret;
169efe51d0cSJohn Levon 
170efe51d0cSJohn Levon 		/*
171efe51d0cSJohn Levon 		 * We want to preserve leaf states.  They're use to split
172efe51d0cSJohn Levon 		 * returns in smatch_db.c.
173efe51d0cSJohn Levon 		 *
174efe51d0cSJohn Levon 		 */
175efe51d0cSJohn Levon 		if (preserve) {
176efe51d0cSJohn Levon 			if (a->merged && !b->merged)
177efe51d0cSJohn Levon 				return -1;
178efe51d0cSJohn Levon 			if (!a->merged)
179efe51d0cSJohn Levon 				return 1;
180efe51d0cSJohn Levon 		}
181efe51d0cSJohn Levon 	}
182efe51d0cSJohn Levon 	if (!a->state->name || !b->state->name)
183efe51d0cSJohn Levon 		return 0;
184efe51d0cSJohn Levon 
185efe51d0cSJohn Levon 	return strcmp(a->state->name, b->state->name);
1861f5207b7SJohn Levon }
1871f5207b7SJohn Levon 
alloc_sm_state(int owner,const char * name,struct symbol * sym,struct smatch_state * state)1881f5207b7SJohn Levon struct sm_state *alloc_sm_state(int owner, const char *name,
1891f5207b7SJohn Levon 				struct symbol *sym, struct smatch_state *state)
1901f5207b7SJohn Levon {
1911f5207b7SJohn Levon 	struct sm_state *sm_state = __alloc_sm_state(0);
1921f5207b7SJohn Levon 
1931f5207b7SJohn Levon 	sm_state_counter++;
1941f5207b7SJohn Levon 
1951f5207b7SJohn Levon 	sm_state->name = alloc_sname(name);
1961f5207b7SJohn Levon 	sm_state->owner = owner;
1971f5207b7SJohn Levon 	sm_state->sym = sym;
1981f5207b7SJohn Levon 	sm_state->state = state;
1991f5207b7SJohn Levon 	sm_state->line = get_lineno();
2001f5207b7SJohn Levon 	sm_state->merged = 0;
2011f5207b7SJohn Levon 	sm_state->pool = NULL;
2021f5207b7SJohn Levon 	sm_state->left = NULL;
2031f5207b7SJohn Levon 	sm_state->right = NULL;
2041f5207b7SJohn Levon 	sm_state->possible = NULL;
2051f5207b7SJohn Levon 	add_ptr_list(&sm_state->possible, sm_state);
2061f5207b7SJohn Levon 	return sm_state;
2071f5207b7SJohn Levon }
2081f5207b7SJohn Levon 
alloc_state_no_name(int owner,const char * name,struct symbol * sym,struct smatch_state * state)2091f5207b7SJohn Levon static struct sm_state *alloc_state_no_name(int owner, const char *name,
2101f5207b7SJohn Levon 				     struct symbol *sym,
2111f5207b7SJohn Levon 				     struct smatch_state *state)
2121f5207b7SJohn Levon {
2131f5207b7SJohn Levon 	struct sm_state *tmp;
2141f5207b7SJohn Levon 
2151f5207b7SJohn Levon 	tmp = alloc_sm_state(owner, NULL, sym, state);
2161f5207b7SJohn Levon 	tmp->name = name;
2171f5207b7SJohn Levon 	return tmp;
2181f5207b7SJohn Levon }
2191f5207b7SJohn Levon 
too_many_possible(struct sm_state * sm)2201f5207b7SJohn Levon int too_many_possible(struct sm_state *sm)
2211f5207b7SJohn Levon {
2221f5207b7SJohn Levon 	if (ptr_list_size((struct ptr_list *)sm->possible) >= 100)
2231f5207b7SJohn Levon 		return 1;
2241f5207b7SJohn Levon 	return 0;
2251f5207b7SJohn Levon }
2261f5207b7SJohn Levon 
add_possible_sm(struct sm_state * to,struct sm_state * new)2271f5207b7SJohn Levon void add_possible_sm(struct sm_state *to, struct sm_state *new)
2281f5207b7SJohn Levon {
2291f5207b7SJohn Levon 	struct sm_state *tmp;
2301f5207b7SJohn Levon 	int preserve = 1;
231efe51d0cSJohn Levon 	int cmp;
2321f5207b7SJohn Levon 
2331f5207b7SJohn Levon 	if (too_many_possible(to))
2341f5207b7SJohn Levon 		preserve = 0;
2351f5207b7SJohn Levon 
2361f5207b7SJohn Levon 	FOR_EACH_PTR(to->possible, tmp) {
237efe51d0cSJohn Levon 		cmp = cmp_possible_sm(tmp, new, preserve);
238efe51d0cSJohn Levon 		if (cmp < 0)
2391f5207b7SJohn Levon 			continue;
240efe51d0cSJohn Levon 		else if (cmp == 0) {
2411f5207b7SJohn Levon 			return;
2421f5207b7SJohn Levon 		} else {
2431f5207b7SJohn Levon 			INSERT_CURRENT(new, tmp);
2441f5207b7SJohn Levon 			return;
2451f5207b7SJohn Levon 		}
2461f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
2471f5207b7SJohn Levon 	add_ptr_list(&to->possible, new);
2481f5207b7SJohn Levon }
2491f5207b7SJohn Levon 
copy_possibles(struct sm_state * to,struct sm_state * one,struct sm_state * two)250efe51d0cSJohn Levon static void copy_possibles(struct sm_state *to, struct sm_state *one, struct sm_state *two)
2511f5207b7SJohn Levon {
252efe51d0cSJohn Levon 	struct sm_state *large = one;
253efe51d0cSJohn Levon 	struct sm_state *small = two;
2541f5207b7SJohn Levon 	struct sm_state *tmp;
2551f5207b7SJohn Levon 
256efe51d0cSJohn Levon 	/*
257efe51d0cSJohn Levon 	 * We spend a lot of time copying the possible lists.  I've tried to
258efe51d0cSJohn Levon 	 * optimize the process a bit.
259efe51d0cSJohn Levon 	 *
260efe51d0cSJohn Levon 	 */
261efe51d0cSJohn Levon 
262efe51d0cSJohn Levon 	if (ptr_list_size((struct ptr_list *)two->possible) >
263efe51d0cSJohn Levon 	    ptr_list_size((struct ptr_list *)one->possible)) {
264efe51d0cSJohn Levon 		large = two;
265efe51d0cSJohn Levon 		small = one;
266efe51d0cSJohn Levon 	}
267efe51d0cSJohn Levon 
268efe51d0cSJohn Levon 	to->possible = clone_slist(large->possible);
269efe51d0cSJohn Levon 	add_possible_sm(to, to);
270efe51d0cSJohn Levon 	FOR_EACH_PTR(small->possible, tmp) {
2711f5207b7SJohn Levon 		add_possible_sm(to, tmp);
2721f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
2731f5207b7SJohn Levon }
2741f5207b7SJohn Levon 
alloc_sname(const char * str)2751f5207b7SJohn Levon char *alloc_sname(const char *str)
2761f5207b7SJohn Levon {
2771f5207b7SJohn Levon 	char *tmp;
2781f5207b7SJohn Levon 
2791f5207b7SJohn Levon 	if (!str)
2801f5207b7SJohn Levon 		return NULL;
2811f5207b7SJohn Levon 	tmp = __alloc_sname(strlen(str) + 1);
2821f5207b7SJohn Levon 	strcpy(tmp, str);
2831f5207b7SJohn Levon 	return tmp;
2841f5207b7SJohn Levon }
2851f5207b7SJohn Levon 
286efe51d0cSJohn Levon static struct symbol *oom_func;
287efe51d0cSJohn Levon static int oom_limit = 3000000;  /* Start with a 3GB limit */
out_of_memory(void)2881f5207b7SJohn Levon int out_of_memory(void)
2891f5207b7SJohn Levon {
290efe51d0cSJohn Levon 	if (oom_func)
291efe51d0cSJohn Levon 		return 1;
292efe51d0cSJohn Levon 
2931f5207b7SJohn Levon 	/*
2941f5207b7SJohn Levon 	 * I decided to use 50M here based on trial and error.
2951f5207b7SJohn Levon 	 * It works out OK for the kernel and so it should work
2961f5207b7SJohn Levon 	 * for most other projects as well.
2971f5207b7SJohn Levon 	 */
2981f5207b7SJohn Levon 	if (sm_state_counter * sizeof(struct sm_state) >= 100000000)
2991f5207b7SJohn Levon 		return 1;
300efe51d0cSJohn Levon 
301efe51d0cSJohn Levon 	/*
302efe51d0cSJohn Levon 	 * We're reading from statm to figure out how much memory we
303efe51d0cSJohn Levon 	 * are using.  The problem is that at the end of the function
304efe51d0cSJohn Levon 	 * we release the memory, so that it can be re-used but it
305efe51d0cSJohn Levon 	 * stays in cache, it's not released to the OS.  So then if
306efe51d0cSJohn Levon 	 * we allocate memory for different purposes we can easily
307efe51d0cSJohn Levon 	 * hit the 3GB limit on the next function, so that's why I give
308efe51d0cSJohn Levon 	 * the next function an extra 100MB to work with.
309efe51d0cSJohn Levon 	 *
310efe51d0cSJohn Levon 	 */
311efe51d0cSJohn Levon 	if (get_mem_kb() > oom_limit) {
312efe51d0cSJohn Levon 		oom_func = cur_func_sym;
313efe51d0cSJohn Levon 		final_pass++;
314efe51d0cSJohn Levon 		sm_perror("OOM: %luKb sm_state_count = %d", get_mem_kb(), sm_state_counter);
315efe51d0cSJohn Levon 		final_pass--;
316efe51d0cSJohn Levon 		return 1;
317efe51d0cSJohn Levon 	}
318efe51d0cSJohn Levon 
3191f5207b7SJohn Levon 	return 0;
3201f5207b7SJohn Levon }
3211f5207b7SJohn Levon 
low_on_memory(void)3221f5207b7SJohn Levon int low_on_memory(void)
3231f5207b7SJohn Levon {
3241f5207b7SJohn Levon 	if (sm_state_counter * sizeof(struct sm_state) >= 25000000)
3251f5207b7SJohn Levon 		return 1;
3261f5207b7SJohn Levon 	return 0;
3271f5207b7SJohn Levon }
3281f5207b7SJohn Levon 
free_sm_state(struct sm_state * sm)3291f5207b7SJohn Levon static void free_sm_state(struct sm_state *sm)
3301f5207b7SJohn Levon {
3311f5207b7SJohn Levon 	free_slist(&sm->possible);
3321f5207b7SJohn Levon 	/*
3331f5207b7SJohn Levon 	 * fixme.  Free the actual state.
3341f5207b7SJohn Levon 	 * Right now we leave it until the end of the function
3351f5207b7SJohn Levon 	 * because we don't want to double free it.
3361f5207b7SJohn Levon 	 * Use the freelist to not double free things
3371f5207b7SJohn Levon 	 */
3381f5207b7SJohn Levon }
3391f5207b7SJohn Levon 
free_all_sm_states(struct allocation_blob * blob)3401f5207b7SJohn Levon static void free_all_sm_states(struct allocation_blob *blob)
3411f5207b7SJohn Levon {
3421f5207b7SJohn Levon 	unsigned int size = sizeof(struct sm_state);
3431f5207b7SJohn Levon 	unsigned int offset = 0;
3441f5207b7SJohn Levon 
3451f5207b7SJohn Levon 	while (offset < blob->offset) {
3461f5207b7SJohn Levon 		free_sm_state((struct sm_state *)(blob->data + offset));
3471f5207b7SJohn Levon 		offset += size;
3481f5207b7SJohn Levon 	}
3491f5207b7SJohn Levon }
3501f5207b7SJohn Levon 
3511f5207b7SJohn Levon /* At the end of every function we free all the sm_states */
free_every_single_sm_state(void)3521f5207b7SJohn Levon void free_every_single_sm_state(void)
3531f5207b7SJohn Levon {
3541f5207b7SJohn Levon 	struct allocator_struct *desc = &sm_state_allocator;
3551f5207b7SJohn Levon 	struct allocation_blob *blob = desc->blobs;
3561f5207b7SJohn Levon 
3571f5207b7SJohn Levon 	desc->blobs = NULL;
3581f5207b7SJohn Levon 	desc->allocations = 0;
3591f5207b7SJohn Levon 	desc->total_bytes = 0;
3601f5207b7SJohn Levon 	desc->useful_bytes = 0;
3611f5207b7SJohn Levon 	desc->freelist = NULL;
3621f5207b7SJohn Levon 	while (blob) {
3631f5207b7SJohn Levon 		struct allocation_blob *next = blob->next;
3641f5207b7SJohn Levon 		free_all_sm_states(blob);
3651f5207b7SJohn Levon 		blob_free(blob, desc->chunking);
3661f5207b7SJohn Levon 		blob = next;
3671f5207b7SJohn Levon 	}
3681f5207b7SJohn Levon 	clear_sname_alloc();
3691f5207b7SJohn Levon 	clear_smatch_state_alloc();
3701f5207b7SJohn Levon 
3711f5207b7SJohn Levon 	free_stack_and_strees(&all_pools);
3721f5207b7SJohn Levon 	sm_state_counter = 0;
373efe51d0cSJohn Levon 	if (oom_func) {
374efe51d0cSJohn Levon 		oom_limit += 100000;
375efe51d0cSJohn Levon 		oom_func = NULL;
376efe51d0cSJohn Levon 	}
3771f5207b7SJohn Levon }
3781f5207b7SJohn Levon 
get_pool_count(void)3791f5207b7SJohn Levon unsigned long get_pool_count(void)
3801f5207b7SJohn Levon {
3811f5207b7SJohn Levon 	return ptr_list_size((struct ptr_list *)all_pools);
3821f5207b7SJohn Levon }
3831f5207b7SJohn Levon 
clone_sm(struct sm_state * s)3841f5207b7SJohn Levon struct sm_state *clone_sm(struct sm_state *s)
3851f5207b7SJohn Levon {
3861f5207b7SJohn Levon 	struct sm_state *ret;
3871f5207b7SJohn Levon 
3881f5207b7SJohn Levon 	ret = alloc_state_no_name(s->owner, s->name, s->sym, s->state);
3891f5207b7SJohn Levon 	ret->merged = s->merged;
3901f5207b7SJohn Levon 	ret->line = s->line;
3911f5207b7SJohn Levon 	/* clone_sm() doesn't copy the pools.  Each state needs to have
3921f5207b7SJohn Levon 	   only one pool. */
3931f5207b7SJohn Levon 	ret->possible = clone_slist(s->possible);
3941f5207b7SJohn Levon 	ret->left = s->left;
3951f5207b7SJohn Levon 	ret->right = s->right;
3961f5207b7SJohn Levon 	return ret;
3971f5207b7SJohn Levon }
3981f5207b7SJohn Levon 
is_merged(struct sm_state * sm)3991f5207b7SJohn Levon int is_merged(struct sm_state *sm)
4001f5207b7SJohn Levon {
4011f5207b7SJohn Levon 	return sm->merged;
4021f5207b7SJohn Levon }
4031f5207b7SJohn Levon 
is_leaf(struct sm_state * sm)4041f5207b7SJohn Levon int is_leaf(struct sm_state *sm)
4051f5207b7SJohn Levon {
4061f5207b7SJohn Levon 	return !sm->merged;
4071f5207b7SJohn Levon }
4081f5207b7SJohn Levon 
slist_has_state(struct state_list * slist,struct smatch_state * state)4091f5207b7SJohn Levon int slist_has_state(struct state_list *slist, struct smatch_state *state)
4101f5207b7SJohn Levon {
4111f5207b7SJohn Levon 	struct sm_state *tmp;
4121f5207b7SJohn Levon 
4131f5207b7SJohn Levon 	FOR_EACH_PTR(slist, tmp) {
4141f5207b7SJohn Levon 		if (tmp->state == state)
4151f5207b7SJohn Levon 			return 1;
4161f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
4171f5207b7SJohn Levon 	return 0;
4181f5207b7SJohn Levon }
4191f5207b7SJohn Levon 
clone_slist(struct state_list * from_slist)4201f5207b7SJohn Levon struct state_list *clone_slist(struct state_list *from_slist)
4211f5207b7SJohn Levon {
4221f5207b7SJohn Levon 	struct sm_state *sm;
4231f5207b7SJohn Levon 	struct state_list *to_slist = NULL;
4241f5207b7SJohn Levon 
4251f5207b7SJohn Levon 	FOR_EACH_PTR(from_slist, sm) {
4261f5207b7SJohn Levon 		add_ptr_list(&to_slist, sm);
4271f5207b7SJohn Levon 	} END_FOR_EACH_PTR(sm);
4281f5207b7SJohn Levon 	return to_slist;
4291f5207b7SJohn Levon }
4301f5207b7SJohn Levon 
merge_states(int owner,const char * name,struct symbol * sym,struct smatch_state * state1,struct smatch_state * state2)4311f5207b7SJohn Levon static struct smatch_state *merge_states(int owner, const char *name,
4321f5207b7SJohn Levon 					 struct symbol *sym,
4331f5207b7SJohn Levon 					 struct smatch_state *state1,
4341f5207b7SJohn Levon 					 struct smatch_state *state2)
4351f5207b7SJohn Levon {
4361f5207b7SJohn Levon 	struct smatch_state *ret;
4371f5207b7SJohn Levon 
4381f5207b7SJohn Levon 	if (state1 == state2)
4391f5207b7SJohn Levon 		ret = state1;
4401f5207b7SJohn Levon 	else if (__has_merge_function(owner))
4411f5207b7SJohn Levon 		ret = __client_merge_function(owner, state1, state2);
4421f5207b7SJohn Levon 	else if (state1 == &ghost)
4431f5207b7SJohn Levon 		ret = state2;
4441f5207b7SJohn Levon 	else if (state2 == &ghost)
4451f5207b7SJohn Levon 		ret = state1;
4461f5207b7SJohn Levon 	else if (!state1 || !state2)
4471f5207b7SJohn Levon 		ret = &undefined;
4481f5207b7SJohn Levon 	else
4491f5207b7SJohn Levon 		ret = &merged;
4501f5207b7SJohn Levon 	return ret;
4511f5207b7SJohn Levon }
4521f5207b7SJohn Levon 
merge_sm_states(struct sm_state * one,struct sm_state * two)4531f5207b7SJohn Levon struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
4541f5207b7SJohn Levon {
4551f5207b7SJohn Levon 	struct smatch_state *s;
4561f5207b7SJohn Levon 	struct sm_state *result;
4571f5207b7SJohn Levon 	static int warned;
4581f5207b7SJohn Levon 
459*6523a3aaSJohn Levon 	if (one->state->data && !has_dynamic_states(one->owner))
460*6523a3aaSJohn Levon 		sm_msg("dynamic state: %s", show_sm(one));
461*6523a3aaSJohn Levon 
4621f5207b7SJohn Levon 	if (one == two)
4631f5207b7SJohn Levon 		return one;
4641f5207b7SJohn Levon 	if (out_of_memory()) {
4651f5207b7SJohn Levon 		if (!warned)
4661f5207b7SJohn Levon 			sm_warning("Function too hairy.  No more merges.");
4671f5207b7SJohn Levon 		warned = 1;
4681f5207b7SJohn Levon 		return one;
4691f5207b7SJohn Levon 	}
4701f5207b7SJohn Levon 	warned = 0;
4711f5207b7SJohn Levon 	s = merge_states(one->owner, one->name, one->sym, one->state, two->state);
4721f5207b7SJohn Levon 	result = alloc_state_no_name(one->owner, one->name, one->sym, s);
4731f5207b7SJohn Levon 	result->merged = 1;
4741f5207b7SJohn Levon 	result->left = one;
4751f5207b7SJohn Levon 	result->right = two;
476efe51d0cSJohn Levon 
477efe51d0cSJohn Levon 	copy_possibles(result, one, two);
4781f5207b7SJohn Levon 
4791f5207b7SJohn Levon 	/*
4801f5207b7SJohn Levon 	 * The ->line information is used by deref_check where we complain about
4811f5207b7SJohn Levon 	 * checking pointers that have already been dereferenced.  Let's say we
4821f5207b7SJohn Levon 	 * dereference a pointer on both the true and false paths and then merge
4831f5207b7SJohn Levon 	 * the states here.  The result state is &derefed, but the ->line number
4841f5207b7SJohn Levon 	 * is on the line where the pointer is merged not where it was
4851f5207b7SJohn Levon 	 * dereferenced..
4861f5207b7SJohn Levon 	 *
4871f5207b7SJohn Levon 	 * So in that case, let's just pick one dereference and set the ->line
4881f5207b7SJohn Levon 	 * to point at it.
4891f5207b7SJohn Levon 	 *
4901f5207b7SJohn Levon 	 */
4911f5207b7SJohn Levon 
4921f5207b7SJohn Levon 	if (result->state == one->state)
4931f5207b7SJohn Levon 		result->line = one->line;
4941f5207b7SJohn Levon 	if (result->state == two->state)
4951f5207b7SJohn Levon 		result->line = two->line;
4961f5207b7SJohn Levon 
4971f5207b7SJohn Levon 	if (option_debug ||
4981f5207b7SJohn Levon 	    strcmp(check_name(one->owner), option_debug_check) == 0) {
4991f5207b7SJohn Levon 		struct sm_state *tmp;
5001f5207b7SJohn Levon 		int i = 0;
5011f5207b7SJohn Levon 
5021f5207b7SJohn Levon 		printf("%s:%d %s() merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
5031f5207b7SJohn Levon 			get_filename(), get_lineno(), get_function(),
5041f5207b7SJohn Levon 			check_name(one->owner), one->name,
5051f5207b7SJohn Levon 			show_state(one->state), one->line,
5061f5207b7SJohn Levon 			show_state(two->state), two->line,
5071f5207b7SJohn Levon 			show_state(s));
5081f5207b7SJohn Levon 
5091f5207b7SJohn Levon 		FOR_EACH_PTR(result->possible, tmp) {
5101f5207b7SJohn Levon 			if (i++)
5111f5207b7SJohn Levon 				printf(", ");
5121f5207b7SJohn Levon 			printf("%s", show_state(tmp->state));
5131f5207b7SJohn Levon 		} END_FOR_EACH_PTR(tmp);
5141f5207b7SJohn Levon 		printf(")\n");
5151f5207b7SJohn Levon 	}
5161f5207b7SJohn Levon 
5171f5207b7SJohn Levon 	return result;
5181f5207b7SJohn Levon }
5191f5207b7SJohn Levon 
get_sm_state_stree(struct stree * stree,int owner,const char * name,struct symbol * sym)5201f5207b7SJohn Levon struct sm_state *get_sm_state_stree(struct stree *stree, int owner, const char *name,
5211f5207b7SJohn Levon 				struct symbol *sym)
5221f5207b7SJohn Levon {
5231f5207b7SJohn Levon 	struct tracker tracker = {
5241f5207b7SJohn Levon 		.owner = owner,
5251f5207b7SJohn Levon 		.name = (char *)name,
5261f5207b7SJohn Levon 		.sym = sym,
5271f5207b7SJohn Levon 	};
5281f5207b7SJohn Levon 
5291f5207b7SJohn Levon 	if (!name)
5301f5207b7SJohn Levon 		return NULL;
5311f5207b7SJohn Levon 
5321f5207b7SJohn Levon 
5331f5207b7SJohn Levon 	return avl_lookup(stree, (struct sm_state *)&tracker);
5341f5207b7SJohn Levon }
5351f5207b7SJohn Levon 
get_state_stree(struct stree * stree,int owner,const char * name,struct symbol * sym)5361f5207b7SJohn Levon struct smatch_state *get_state_stree(struct stree *stree,
5371f5207b7SJohn Levon 				int owner, const char *name,
5381f5207b7SJohn Levon 				struct symbol *sym)
5391f5207b7SJohn Levon {
5401f5207b7SJohn Levon 	struct sm_state *sm;
5411f5207b7SJohn Levon 
5421f5207b7SJohn Levon 	sm = get_sm_state_stree(stree, owner, name, sym);
5431f5207b7SJohn Levon 	if (sm)
5441f5207b7SJohn Levon 		return sm->state;
5451f5207b7SJohn Levon 	return NULL;
5461f5207b7SJohn Levon }
5471f5207b7SJohn Levon 
5481f5207b7SJohn Levon /* FIXME: this is almost exactly the same as set_sm_state_slist() */
overwrite_sm_state_stree(struct stree ** stree,struct sm_state * new)5491f5207b7SJohn Levon void overwrite_sm_state_stree(struct stree **stree, struct sm_state *new)
5501f5207b7SJohn Levon {
5511f5207b7SJohn Levon 	avl_insert(stree, new);
5521f5207b7SJohn Levon }
5531f5207b7SJohn Levon 
overwrite_sm_state_stree_stack(struct stree_stack ** stack,struct sm_state * sm)5541f5207b7SJohn Levon void overwrite_sm_state_stree_stack(struct stree_stack **stack,
5551f5207b7SJohn Levon 			struct sm_state *sm)
5561f5207b7SJohn Levon {
5571f5207b7SJohn Levon 	struct stree *stree;
5581f5207b7SJohn Levon 
5591f5207b7SJohn Levon 	stree = pop_stree(stack);
5601f5207b7SJohn Levon 	overwrite_sm_state_stree(&stree, sm);
5611f5207b7SJohn Levon 	push_stree(stack, stree);
5621f5207b7SJohn Levon }
5631f5207b7SJohn Levon 
set_state_stree(struct stree ** stree,int owner,const char * name,struct symbol * sym,struct smatch_state * state)5641f5207b7SJohn Levon struct sm_state *set_state_stree(struct stree **stree, int owner, const char *name,
5651f5207b7SJohn Levon 		     struct symbol *sym, struct smatch_state *state)
5661f5207b7SJohn Levon {
5671f5207b7SJohn Levon 	struct sm_state *new = alloc_sm_state(owner, name, sym, state);
5681f5207b7SJohn Levon 
5691f5207b7SJohn Levon 	avl_insert(stree, new);
5701f5207b7SJohn Levon 	return new;
5711f5207b7SJohn Levon }
5721f5207b7SJohn Levon 
set_state_stree_perm(struct stree ** stree,int owner,const char * name,struct symbol * sym,struct smatch_state * state)5731f5207b7SJohn Levon void set_state_stree_perm(struct stree **stree, int owner, const char *name,
5741f5207b7SJohn Levon 		     struct symbol *sym, struct smatch_state *state)
5751f5207b7SJohn Levon {
5761f5207b7SJohn Levon 	struct sm_state *sm;
5771f5207b7SJohn Levon 
5781f5207b7SJohn Levon 	sm = malloc(sizeof(*sm) + strlen(name) + 1);
5791f5207b7SJohn Levon 	memset(sm, 0, sizeof(*sm));
5801f5207b7SJohn Levon 	sm->owner = owner;
5811f5207b7SJohn Levon 	sm->name = (char *)(sm + 1);
5821f5207b7SJohn Levon 	strcpy((char *)sm->name, name);
5831f5207b7SJohn Levon 	sm->sym = sym;
5841f5207b7SJohn Levon 	sm->state = state;
5851f5207b7SJohn Levon 
5861f5207b7SJohn Levon 	overwrite_sm_state_stree(stree, sm);
5871f5207b7SJohn Levon }
5881f5207b7SJohn Levon 
delete_state_stree(struct stree ** stree,int owner,const char * name,struct symbol * sym)5891f5207b7SJohn Levon void delete_state_stree(struct stree **stree, int owner, const char *name,
5901f5207b7SJohn Levon 			struct symbol *sym)
5911f5207b7SJohn Levon {
5921f5207b7SJohn Levon 	struct tracker tracker = {
5931f5207b7SJohn Levon 		.owner = owner,
5941f5207b7SJohn Levon 		.name = (char *)name,
5951f5207b7SJohn Levon 		.sym = sym,
5961f5207b7SJohn Levon 	};
5971f5207b7SJohn Levon 
5981f5207b7SJohn Levon 	avl_remove(stree, (struct sm_state *)&tracker);
5991f5207b7SJohn Levon }
6001f5207b7SJohn Levon 
delete_state_stree_stack(struct stree_stack ** stack,int owner,const char * name,struct symbol * sym)6011f5207b7SJohn Levon void delete_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
6021f5207b7SJohn Levon 			struct symbol *sym)
6031f5207b7SJohn Levon {
6041f5207b7SJohn Levon 	struct stree *stree;
6051f5207b7SJohn Levon 
6061f5207b7SJohn Levon 	stree = pop_stree(stack);
6071f5207b7SJohn Levon 	delete_state_stree(&stree, owner, name, sym);
6081f5207b7SJohn Levon 	push_stree(stack, stree);
6091f5207b7SJohn Levon }
6101f5207b7SJohn Levon 
push_stree(struct stree_stack ** stack,struct stree * stree)6111f5207b7SJohn Levon void push_stree(struct stree_stack **stack, struct stree *stree)
6121f5207b7SJohn Levon {
6131f5207b7SJohn Levon 	add_ptr_list(stack, stree);
6141f5207b7SJohn Levon }
6151f5207b7SJohn Levon 
pop_stree(struct stree_stack ** stack)6161f5207b7SJohn Levon struct stree *pop_stree(struct stree_stack **stack)
6171f5207b7SJohn Levon {
6181f5207b7SJohn Levon 	struct stree *stree;
6191f5207b7SJohn Levon 
6201f5207b7SJohn Levon 	stree = last_ptr_list((struct ptr_list *)*stack);
6211f5207b7SJohn Levon 	delete_ptr_list_last((struct ptr_list **)stack);
6221f5207b7SJohn Levon 	return stree;
6231f5207b7SJohn Levon }
6241f5207b7SJohn Levon 
top_stree(struct stree_stack * stack)6251f5207b7SJohn Levon struct stree *top_stree(struct stree_stack *stack)
6261f5207b7SJohn Levon {
6271f5207b7SJohn Levon 	return last_ptr_list((struct ptr_list *)stack);
6281f5207b7SJohn Levon }
6291f5207b7SJohn Levon 
free_slist(struct state_list ** slist)6301f5207b7SJohn Levon void free_slist(struct state_list **slist)
6311f5207b7SJohn Levon {
6321f5207b7SJohn Levon 	__free_ptr_list((struct ptr_list **)slist);
6331f5207b7SJohn Levon }
6341f5207b7SJohn Levon 
free_stree_stack(struct stree_stack ** stack)6351f5207b7SJohn Levon void free_stree_stack(struct stree_stack **stack)
6361f5207b7SJohn Levon {
6371f5207b7SJohn Levon 	__free_ptr_list((struct ptr_list **)stack);
6381f5207b7SJohn Levon }
6391f5207b7SJohn Levon 
free_stack_and_strees(struct stree_stack ** stree_stack)6401f5207b7SJohn Levon void free_stack_and_strees(struct stree_stack **stree_stack)
6411f5207b7SJohn Levon {
6421f5207b7SJohn Levon 	struct stree *stree;
6431f5207b7SJohn Levon 
6441f5207b7SJohn Levon 	FOR_EACH_PTR(*stree_stack, stree) {
6451f5207b7SJohn Levon 		free_stree(&stree);
6461f5207b7SJohn Levon 	} END_FOR_EACH_PTR(stree);
6471f5207b7SJohn Levon 	free_stree_stack(stree_stack);
6481f5207b7SJohn Levon }
6491f5207b7SJohn Levon 
set_state_stree_stack(struct stree_stack ** stack,int owner,const char * name,struct symbol * sym,struct smatch_state * state)6501f5207b7SJohn Levon struct sm_state *set_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
6511f5207b7SJohn Levon 				struct symbol *sym, struct smatch_state *state)
6521f5207b7SJohn Levon {
6531f5207b7SJohn Levon 	struct stree *stree;
6541f5207b7SJohn Levon 	struct sm_state *sm;
6551f5207b7SJohn Levon 
6561f5207b7SJohn Levon 	stree = pop_stree(stack);
6571f5207b7SJohn Levon 	sm = set_state_stree(&stree, owner, name, sym, state);
6581f5207b7SJohn Levon 	push_stree(stack, stree);
6591f5207b7SJohn Levon 
6601f5207b7SJohn Levon 	return sm;
6611f5207b7SJohn Levon }
6621f5207b7SJohn Levon 
6631f5207b7SJohn Levon /*
6641f5207b7SJohn Levon  * get_sm_state_stack() gets the state for the top slist on the stack.
6651f5207b7SJohn Levon  */
get_sm_state_stree_stack(struct stree_stack * stack,int owner,const char * name,struct symbol * sym)6661f5207b7SJohn Levon struct sm_state *get_sm_state_stree_stack(struct stree_stack *stack,
6671f5207b7SJohn Levon 				int owner, const char *name,
6681f5207b7SJohn Levon 				struct symbol *sym)
6691f5207b7SJohn Levon {
6701f5207b7SJohn Levon 	struct stree *stree;
6711f5207b7SJohn Levon 	struct sm_state *ret;
6721f5207b7SJohn Levon 
6731f5207b7SJohn Levon 	stree = pop_stree(&stack);
6741f5207b7SJohn Levon 	ret = get_sm_state_stree(stree, owner, name, sym);
6751f5207b7SJohn Levon 	push_stree(&stack, stree);
6761f5207b7SJohn Levon 	return ret;
6771f5207b7SJohn Levon }
6781f5207b7SJohn Levon 
get_state_stree_stack(struct stree_stack * stack,int owner,const char * name,struct symbol * sym)6791f5207b7SJohn Levon struct smatch_state *get_state_stree_stack(struct stree_stack *stack,
6801f5207b7SJohn Levon 				int owner, const char *name,
6811f5207b7SJohn Levon 				struct symbol *sym)
6821f5207b7SJohn Levon {
6831f5207b7SJohn Levon 	struct sm_state *sm;
6841f5207b7SJohn Levon 
6851f5207b7SJohn Levon 	sm = get_sm_state_stree_stack(stack, owner, name, sym);
6861f5207b7SJohn Levon 	if (sm)
6871f5207b7SJohn Levon 		return sm->state;
6881f5207b7SJohn Levon 	return NULL;
6891f5207b7SJohn Levon }
6901f5207b7SJohn Levon 
match_states_stree(struct stree ** one,struct stree ** two)6911f5207b7SJohn Levon static void match_states_stree(struct stree **one, struct stree **two)
6921f5207b7SJohn Levon {
6931f5207b7SJohn Levon 	struct smatch_state *tmp_state;
6941f5207b7SJohn Levon 	struct sm_state *sm;
6951f5207b7SJohn Levon 	struct state_list *add_to_one = NULL;
6961f5207b7SJohn Levon 	struct state_list *add_to_two = NULL;
6971f5207b7SJohn Levon 	AvlIter one_iter;
6981f5207b7SJohn Levon 	AvlIter two_iter;
6991f5207b7SJohn Levon 
700c85f09ccSJohn Levon 	__set_cur_stree_readonly();
701c85f09ccSJohn Levon 
7021f5207b7SJohn Levon 	avl_iter_begin(&one_iter, *one, FORWARD);
7031f5207b7SJohn Levon 	avl_iter_begin(&two_iter, *two, FORWARD);
7041f5207b7SJohn Levon 
7051f5207b7SJohn Levon 	for (;;) {
7061f5207b7SJohn Levon 		if (!one_iter.sm && !two_iter.sm)
7071f5207b7SJohn Levon 			break;
7081f5207b7SJohn Levon 		if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
7091f5207b7SJohn Levon 			__set_fake_cur_stree_fast(*two);
710c85f09ccSJohn Levon 			__in_unmatched_hook++;
7111f5207b7SJohn Levon 			tmp_state = __client_unmatched_state_function(one_iter.sm);
712c85f09ccSJohn Levon 			__in_unmatched_hook--;
7131f5207b7SJohn Levon 			__pop_fake_cur_stree_fast();
7141f5207b7SJohn Levon 			sm = alloc_state_no_name(one_iter.sm->owner, one_iter.sm->name,
7151f5207b7SJohn Levon 						  one_iter.sm->sym, tmp_state);
7161f5207b7SJohn Levon 			add_ptr_list(&add_to_two, sm);
7171f5207b7SJohn Levon 			avl_iter_next(&one_iter);
7181f5207b7SJohn Levon 		} else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
7191f5207b7SJohn Levon 			avl_iter_next(&one_iter);
7201f5207b7SJohn Levon 			avl_iter_next(&two_iter);
7211f5207b7SJohn Levon 		} else {
7221f5207b7SJohn Levon 			__set_fake_cur_stree_fast(*one);
723c85f09ccSJohn Levon 			__in_unmatched_hook++;
7241f5207b7SJohn Levon 			tmp_state = __client_unmatched_state_function(two_iter.sm);
725c85f09ccSJohn Levon 			__in_unmatched_hook--;
7261f5207b7SJohn Levon 			__pop_fake_cur_stree_fast();
7271f5207b7SJohn Levon 			sm = alloc_state_no_name(two_iter.sm->owner, two_iter.sm->name,
7281f5207b7SJohn Levon 						  two_iter.sm->sym, tmp_state);
7291f5207b7SJohn Levon 			add_ptr_list(&add_to_one, sm);
7301f5207b7SJohn Levon 			avl_iter_next(&two_iter);
7311f5207b7SJohn Levon 		}
7321f5207b7SJohn Levon 	}
7331f5207b7SJohn Levon 
734c85f09ccSJohn Levon 	__set_cur_stree_writable();
735c85f09ccSJohn Levon 
7361f5207b7SJohn Levon 	FOR_EACH_PTR(add_to_one, sm) {
7371f5207b7SJohn Levon 		avl_insert(one, sm);
7381f5207b7SJohn Levon 	} END_FOR_EACH_PTR(sm);
7391f5207b7SJohn Levon 
7401f5207b7SJohn Levon 	FOR_EACH_PTR(add_to_two, sm) {
7411f5207b7SJohn Levon 		avl_insert(two, sm);
7421f5207b7SJohn Levon 	} END_FOR_EACH_PTR(sm);
7431f5207b7SJohn Levon 
7441f5207b7SJohn Levon 	free_slist(&add_to_one);
7451f5207b7SJohn Levon 	free_slist(&add_to_two);
7461f5207b7SJohn Levon }
7471f5207b7SJohn Levon 
call_pre_merge_hooks(struct stree ** one,struct stree ** two)7481f5207b7SJohn Levon static void call_pre_merge_hooks(struct stree **one, struct stree **two)
7491f5207b7SJohn Levon {
750c85f09ccSJohn Levon 	struct sm_state *sm, *cur;
751c85f09ccSJohn Levon 	struct stree *new;
7521f5207b7SJohn Levon 
753c85f09ccSJohn Levon 	__in_unmatched_hook++;
7541f5207b7SJohn Levon 
755c85f09ccSJohn Levon 	__set_fake_cur_stree_fast(*one);
756c85f09ccSJohn Levon 	__push_fake_cur_stree();
7571f5207b7SJohn Levon 	FOR_EACH_SM(*two, sm) {
758c85f09ccSJohn Levon 		cur = get_sm_state(sm->owner, sm->name, sm->sym);
759c85f09ccSJohn Levon 		if (cur == sm)
7601f5207b7SJohn Levon 			continue;
761c85f09ccSJohn Levon 		call_pre_merge_hook(cur, sm);
7621f5207b7SJohn Levon 	} END_FOR_EACH_SM(sm);
763c85f09ccSJohn Levon 	new = __pop_fake_cur_stree();
764c85f09ccSJohn Levon 	overwrite_stree(new, one);
765c85f09ccSJohn Levon 	free_stree(&new);
766c85f09ccSJohn Levon 	__pop_fake_cur_stree_fast();
7671f5207b7SJohn Levon 
768c85f09ccSJohn Levon 	__set_fake_cur_stree_fast(*two);
769c85f09ccSJohn Levon 	__push_fake_cur_stree();
7701f5207b7SJohn Levon 	FOR_EACH_SM(*one, sm) {
771c85f09ccSJohn Levon 		cur = get_sm_state(sm->owner, sm->name, sm->sym);
772c85f09ccSJohn Levon 		if (cur == sm)
7731f5207b7SJohn Levon 			continue;
774c85f09ccSJohn Levon 		call_pre_merge_hook(cur, sm);
7751f5207b7SJohn Levon 	} END_FOR_EACH_SM(sm);
776c85f09ccSJohn Levon 	new = __pop_fake_cur_stree();
777c85f09ccSJohn Levon 	overwrite_stree(new, two);
778c85f09ccSJohn Levon 	free_stree(&new);
779c85f09ccSJohn Levon 	__pop_fake_cur_stree_fast();
7801f5207b7SJohn Levon 
781c85f09ccSJohn Levon 	__in_unmatched_hook--;
7821f5207b7SJohn Levon }
7831f5207b7SJohn Levon 
clone_pool_havers_stree(struct stree ** stree)7841f5207b7SJohn Levon static void clone_pool_havers_stree(struct stree **stree)
7851f5207b7SJohn Levon {
7861f5207b7SJohn Levon 	struct sm_state *sm, *tmp;
7871f5207b7SJohn Levon 	struct state_list *slist = NULL;
7881f5207b7SJohn Levon 
7891f5207b7SJohn Levon 	FOR_EACH_SM(*stree, sm) {
7901f5207b7SJohn Levon 		if (sm->pool) {
7911f5207b7SJohn Levon 			tmp = clone_sm(sm);
7921f5207b7SJohn Levon 			add_ptr_list(&slist, tmp);
7931f5207b7SJohn Levon 		}
7941f5207b7SJohn Levon 	} END_FOR_EACH_SM(sm);
7951f5207b7SJohn Levon 
7961f5207b7SJohn Levon 	FOR_EACH_PTR(slist, sm) {
7971f5207b7SJohn Levon 		avl_insert(stree, sm);
7981f5207b7SJohn Levon 	} END_FOR_EACH_PTR(sm);
7991f5207b7SJohn Levon 
8001f5207b7SJohn Levon 	free_slist(&slist);
8011f5207b7SJohn Levon }
8021f5207b7SJohn Levon 
8031f5207b7SJohn Levon int __stree_id;
8041f5207b7SJohn Levon 
8051f5207b7SJohn Levon /*
8061f5207b7SJohn Levon  * merge_slist() is called whenever paths merge, such as after
8071f5207b7SJohn Levon  * an if statement.  It takes the two slists and creates one.
8081f5207b7SJohn Levon  */
__merge_stree(struct stree ** to,struct stree * stree,int add_pool)8091f5207b7SJohn Levon static void __merge_stree(struct stree **to, struct stree *stree, int add_pool)
8101f5207b7SJohn Levon {
8111f5207b7SJohn Levon 	struct stree *results = NULL;
8121f5207b7SJohn Levon 	struct stree *implied_one = NULL;
8131f5207b7SJohn Levon 	struct stree *implied_two = NULL;
8141f5207b7SJohn Levon 	AvlIter one_iter;
8151f5207b7SJohn Levon 	AvlIter two_iter;
816efe51d0cSJohn Levon 	struct sm_state *one, *two, *res;
8171f5207b7SJohn Levon 
818