xref: /illumos-gate/usr/src/tools/smatch/src/smatch_implied.c (revision 6523a3aa7f325d64841382707603be7a86e68147)
1 /*
2  * Copyright (C) 2008 Dan Carpenter.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16  *
17  * Copyright 2019 Joyent, Inc.
18  */
19 
20 /*
21  * Imagine we have this code:
22  * foo = 1;
23  * if (bar)
24  *         foo = 99;
25  * else
26  *         frob();
27  *                   //  <-- point #1
28  * if (foo == 99)    //  <-- point #2
29  *         bar->baz; //  <-- point #3
30  *
31  *
32  * At point #3 bar is non null and can be dereferenced.
33  *
34  * It's smatch_implied.c which sets bar to non null at point #2.
35  *
36  * At point #1 merge_slist() stores the list of states from both
37  * the true and false paths.  On the true path foo == 99 and on
38  * the false path foo == 1.  merge_slist() sets their pool
39  * list to show the other states which were there when foo == 99.
40  *
41  * When it comes to the if (foo == 99) the smatch implied hook
42  * looks for all the pools where foo was not 99.  It makes a list
43  * of those.
44  *
45  * Then for bar (and all the other states) it says, ok bar is a
46  * merged state that came from these previous states.  We'll
47  * chop out all the states where it came from a pool where
48  * foo != 99 and merge it all back together.
49  *
50  * That is the implied state of bar.
51  *
52  * merge_slist() sets up ->pool.  An sm_state only has one ->pool and
53  *    that is the pool where it was first set.  The my pool gets set when
54  *    code paths merge.  States that have been set since the last merge do
55  *    not have a ->pool.
56  * merge_sm_state() sets ->left and ->right.  (These are the states which were
57  *    merged to form the current state.)
58  * a pool:  a pool is an slist that has been merged with another slist.
59  */
60 
61 #include <time.h>
62 #include "smatch.h"
63 #include "smatch_slist.h"
64 #include "smatch_extra.h"
65 
66 char *implied_debug_msg;
67 
68 bool implications_off;
69 
70 #define implied_debug 0
71 #define DIMPLIED(msg...) do { if (implied_debug) printf(msg); } while (0)
72 
debug_implied(void)73 bool debug_implied(void)
74 {
75 	if (option_debug)
76 		return true;
77 	return implied_debug;
78 }
79 
80 /*
81  * tmp_range_list():
82  * It messes things up to free range list allocations.  This helper fuction
83  * lets us reuse memory instead of doing new allocations.
84  */
tmp_range_list(struct symbol * type,long long num)85 static struct range_list *tmp_range_list(struct symbol *type, long long num)
86 {
87 	static struct range_list *my_list = NULL;
88 	static struct data_range *my_range;
89 
90 	__free_ptr_list((struct ptr_list **)&my_list);
91 	my_range = alloc_range(ll_to_sval(num), ll_to_sval(num));
92 	add_ptr_list(&my_list, my_range);
93 	return my_list;
94 }
95 
show_comparison(int op)96 static const char *show_comparison(int op)
97 {
98 	if (op == PARAM_LIMIT)
99 		return "<lim>";
100 	return show_special(op);
101 }
102 
print_debug_tf(struct sm_state * sm,int istrue,int isfalse)103 static void print_debug_tf(struct sm_state *sm, int istrue, int isfalse)
104 {
105 	if (!implied_debug && !option_debug)
106 		return;
107 
108 	if (istrue && isfalse) {
109 		printf("%s: %d: does not exist.\n", show_sm(sm), sm->line);
110 	} else if (istrue) {
111 		printf("'%s = %s' from %d is true. %s[stree %d]\n", sm->name, show_state(sm->state),
112 			sm->line, sm->merged ? "[merged]" : "[leaf]",
113 			get_stree_id(sm->pool));
114 	} else if (isfalse) {
115 		printf("'%s = %s' from %d is false. %s[stree %d]\n", sm->name, show_state(sm->state),
116 			sm->line,
117 			sm->merged ? "[merged]" : "[leaf]",
118 			get_stree_id(sm->pool));
119 	} else {
120 		printf("'%s = %s' from %d could be true or false. %s[stree %d]\n", sm->name,
121 			show_state(sm->state), sm->line,
122 			sm->merged ? "[merged]" : "[leaf]",
123 			get_stree_id(sm->pool));
124 	}
125 }
126 
split_comparison_helper(struct range_list * left_orig,int op,struct range_list * right_orig,struct range_list ** left_true_rl,struct range_list ** left_false_rl)127 void split_comparison_helper(struct range_list *left_orig, int op, struct range_list *right_orig,
128 		struct range_list **left_true_rl, struct range_list **left_false_rl)
129 {
130 	if (op == PARAM_LIMIT) {
131 		*left_true_rl = rl_intersection(left_orig, right_orig);
132 		*left_false_rl = rl_filter(left_orig, right_orig);
133 		return;
134 	}
135 
136 	split_comparison_rl(left_orig, op, right_orig, left_true_rl, left_false_rl, NULL, NULL);
137 }
138 
create_fake_history(struct sm_state * sm,int comparison,struct range_list * rl)139 static int create_fake_history(struct sm_state *sm, int comparison, struct range_list *rl)
140 {
141 	struct range_list *orig_rl;
142 	struct range_list *true_rl, *false_rl;
143 	struct stree *true_stree, *false_stree;
144 	struct sm_state *true_sm, *false_sm;
145 	sval_t sval;
146 
147 	if (is_merged(sm) || sm->left || sm->right)
148 		return 0;
149 	if (!rl_to_sval(rl, &sval))
150 		return 0;
151 	if (!estate_rl(sm->state))
152 		return 0;
153 
154 	orig_rl = cast_rl(rl_type(rl), estate_rl(sm->state));
155 	split_comparison_helper(orig_rl, comparison, rl, &true_rl, &false_rl);
156 
157 	true_rl = rl_truncate_cast(estate_type(sm->state), true_rl);
158 	false_rl = rl_truncate_cast(estate_type(sm->state), false_rl);
159 	if (is_whole_rl(true_rl) || is_whole_rl(false_rl) ||
160 	    !true_rl || !false_rl ||
161 	    rl_equiv(orig_rl, true_rl) || rl_equiv(orig_rl, false_rl) ||
162 	    rl_equiv(estate_rl(sm->state), true_rl) || rl_equiv(estate_rl(sm->state), false_rl))
163 		return 0;
164 
165 	if (rl_intersection(true_rl, false_rl)) {
166 		/*
167 		 * Normally these won't intersect, but one exception is when
168 		 * we're dealing with mtags.  We have a long list of mtags and
169 		 * then negate the list.  Now it's over the limit for mtag list
170 		 * length and we squash it down to 4096-ptr_max.  So then it's
171 		 * possible for the true and false rl to overlap.
172 		 */
173 		return 0;
174 	}
175 
176 	if (implied_debug)
177 		sm_msg("fake_history: %s vs %s.  %s %s %s. --> T: %s F: %s",
178 		       sm->name, show_rl(rl), sm->state->name, show_comparison(comparison), show_rl(rl),
179 		       show_rl(true_rl), show_rl(false_rl));
180 
181 	true_sm = clone_sm(sm);
182 	false_sm = clone_sm(sm);
183 
184 	true_sm->state = clone_partial_estate(sm->state, true_rl);
185 	free_slist(&true_sm->possible);
186 	add_possible_sm(true_sm, true_sm);
187 	false_sm->state = clone_partial_estate(sm->state, false_rl);
188 	free_slist(&false_sm->possible);
189 	add_possible_sm(false_sm, false_sm);
190 
191 	true_stree = clone_stree(sm->pool);
192 	false_stree = clone_stree(sm->pool);
193 
194 	overwrite_sm_state_stree(&true_stree, true_sm);
195 	overwrite_sm_state_stree(&false_stree, false_sm);
196 
197 	true_sm->pool = true_stree;
198 	false_sm->pool = false_stree;
199 
200 	sm->merged = 1;
201 	sm->left = true_sm;
202 	sm->right = false_sm;
203 
204 	return 1;
205 }
206 
207 /*
208  * add_pool() adds a slist to *pools. If the slist has already been
209  * added earlier then it doesn't get added a second time.
210  */
add_pool(struct state_list ** pools,struct sm_state * new)211 void add_pool(struct state_list **pools, struct sm_state *new)
212 {
213 	struct sm_state *tmp;
214 
215 	FOR_EACH_PTR(*pools, tmp) {
216 		if (tmp->pool < new->pool)
217 			continue;
218 		else if (tmp->pool == new->pool) {
219 			return;
220 		} else {
221 			INSERT_CURRENT(new, tmp);
222 			return;
223 		}
224 	} END_FOR_EACH_PTR(tmp);
225 	add_ptr_list(pools, new);
226 }
227 
pool_in_pools(struct stree * pool,const struct state_list * slist)228 static int pool_in_pools(struct stree *pool,
229 			 const struct state_list *slist)
230 {
231 	struct sm_state *tmp;
232 
233 	FOR_EACH_PTR(slist, tmp) {
234 		if (!tmp->pool)
235 			continue;
236 		if (tmp->pool == pool)
237 			return 1;
238 	} END_FOR_EACH_PTR(tmp);
239 	return 0;
240 }
241 
remove_pool(struct state_list ** pools,struct stree * remove)242 static int remove_pool(struct state_list **pools, struct stree *remove)
243 {
244 	struct sm_state *tmp;
245 	int ret = 0;
246 
247 	FOR_EACH_PTR(*pools, tmp) {
248 		if (tmp->pool == remove) {
249 			DELETE_CURRENT_PTR(tmp);
250 			ret = 1;
251 		}
252 	} END_FOR_EACH_PTR(tmp);
253 
254 	return ret;
255 }
256 
possibly_true_helper(struct range_list * var_rl,int comparison,struct range_list * rl)257 static bool possibly_true_helper(struct range_list *var_rl, int comparison, struct range_list *rl)
258 {
259 	if (comparison == PARAM_LIMIT) {
260 		struct range_list *intersect;
261 
262 		intersect = rl_intersection(var_rl, rl);
263 		if (intersect)
264 			return true;
265 		return false;
266 	}
267 	return possibly_true_rl(var_rl, comparison, rl);
268 }
269 
possibly_false_helper(struct range_list * var_rl,int comparison,struct range_list * rl)270 static bool possibly_false_helper(struct range_list *var_rl, int comparison, struct range_list *rl)
271 {
272 	if (comparison == PARAM_LIMIT) {
273 		struct range_list *intersect;
274 
275 		intersect = rl_intersection(var_rl, rl);
276 		if (!rl_equiv(var_rl, intersect))
277 			return true;
278 		return false;
279 	}
280 	return possibly_false_rl(var_rl, comparison, rl);
281 }
282 
283 /*
284  * If 'foo' == 99 add it that pool to the true pools.  If it's false, add it to
285  * the false pools.  If we're not sure, then we don't add it to either.
286  */
do_compare(struct sm_state * sm,int comparison,struct range_list * rl,struct state_list ** true_stack,struct state_list ** maybe_stack,struct state_list ** false_stack,int * mixed,struct sm_state * gate_sm)287 static void do_compare(struct sm_state *sm, int comparison, struct range_list *rl,
288 			struct state_list **true_stack,
289 			struct state_list **maybe_stack,
290 			struct state_list **false_stack,
291 			int *mixed, struct sm_state *gate_sm)
292 {
293 	int istrue;
294 	int isfalse;
295 	struct range_list *var_rl;
296 
297 	if (!sm->pool)
298 		return;
299 
300 	var_rl = cast_rl(rl_type(rl), estate_rl(sm->state));
301 
302 	istrue = !possibly_false_helper(var_rl, comparison, rl);
303 	isfalse = !possibly_true_helper(var_rl, comparison, rl);
304 
305 	print_debug_tf(sm, istrue, isfalse);
306 
307 	/* give up if we have borrowed implications (smatch_equiv.c) */
308 	if (sm->sym != gate_sm->sym ||
309 	    strcmp(sm->name, gate_sm->name) != 0) {
310 		if (mixed)
311 			*mixed = 1;
312 	}
313 
314 	if (mixed && !*mixed && !is_merged(sm) && !istrue && !isfalse) {
315 		if (!create_fake_history(sm, comparison, rl))
316 			*mixed = 1;
317 	}
318 
319 	if (istrue)
320 		add_pool(true_stack, sm);
321 	else if (isfalse)
322 		add_pool(false_stack, sm);
323 	else
324 		add_pool(maybe_stack, sm);
325 }
326 
is_checked(struct state_list * checked,struct sm_state * sm)327 static int is_checked(struct state_list *checked, struct sm_state *sm)
328 {
329 	struct sm_state *tmp;
330 
331 	FOR_EACH_PTR(checked, tmp) {
332 		if (tmp == sm)
333 			return 1;
334 	} END_FOR_EACH_PTR(tmp);
335 	return 0;
336 }
337 
338 /*
339  * separate_pools():
340  * Example code:  if (foo == 99) {
341  *
342  * Say 'foo' is a merged state that has many possible values.  It is the combination
343  * of merges.  separate_pools() iterates through the pools recursively and calls
344  * do_compare() for each time 'foo' was set.
345  */
__separate_pools(struct sm_state * sm,int comparison,struct range_list * rl,struct state_list ** true_stack,struct state_list ** maybe_stack,struct state_list ** false_stack,struct state_list ** checked,int * mixed,struct sm_state * gate_sm,struct timeval * start_time)346 static void __separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
347 			struct state_list **true_stack,
348 			struct state_list **maybe_stack,
349 			struct state_list **false_stack,
350 			struct state_list **checked, int *mixed, struct sm_state *gate_sm,
351 			struct timeval *start_time)
352 {
353 	int free_checked = 0;
354 	struct state_list *checked_states = NULL;
355 	struct timeval now, diff;
356 
357 	if (!sm)
358 		return;
359 
360 	gettimeofday(&now, NULL);
361 	timersub(&now, start_time, &diff);
362 	if (diff.tv_sec >= 1) {
363 		if (implied_debug) {
364 			sm_msg("debug: %s: implications taking too long.  (%s %s %s)",
365 			       __func__, sm->state->name, show_comparison(comparison), show_rl(rl));
366 		}
367 		if (mixed)
368 			*mixed = 1;
369 	}
370 
371 	if (checked == NULL) {
372 		checked = &checked_states;
373 		free_checked = 1;
374 	}
375 	if (is_checked(*checked, sm))
376 		return;
377 	add_ptr_list(checked, sm);
378 
379 	do_compare(sm, comparison, rl, true_stack, maybe_stack, false_stack, mixed, gate_sm);
380 
381 	__separate_pools(sm->left, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
382 	__separate_pools(sm->right, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
383 	if (free_checked)
384 		free_slist(checked);
385 }
386 
separate_pools(struct sm_state * sm,int comparison,struct range_list * rl,struct state_list ** true_stack,struct state_list ** false_stack,struct state_list ** checked,int * mixed)387 static void separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
388 			struct state_list **true_stack,
389 			struct state_list **false_stack,
390 			struct state_list **checked, int *mixed)
391 {
392 	struct state_list *maybe_stack = NULL;
393 	struct sm_state *tmp;
394 	struct timeval start_time;
395 
396 
397 	gettimeofday(&start_time, NULL);
398 	__separate_pools(sm, comparison, rl, true_stack, &maybe_stack, false_stack, checked, mixed, sm, &start_time);
399 
400 	if (implied_debug) {
401 		struct sm_state *sm;
402 
403 		FOR_EACH_PTR(*true_stack, sm) {
404 			sm_msg("TRUE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
405 		} END_FOR_EACH_PTR(sm);
406 
407 		FOR_EACH_PTR(maybe_stack, sm) {
408 			sm_msg("MAYBE %s %s[stree %d]",
409 			       show_sm(sm), sm->merged ? "(merged) ": "", get_stree_id(sm->pool));
410 		} END_FOR_EACH_PTR(sm);
411 
412 		FOR_EACH_PTR(*false_stack, sm) {
413 			sm_msg("FALSE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
414 		} END_FOR_EACH_PTR(sm);
415 	}
416 	/* if it's a maybe then remove it */
417 	FOR_EACH_PTR(maybe_stack, tmp) {
418 		remove_pool(false_stack, tmp->pool);
419 		remove_pool(true_stack, tmp->pool);
420 	} END_FOR_EACH_PTR(tmp);
421 
422 	/* if it's both true and false remove it from both */
423 	FOR_EACH_PTR(*true_stack, tmp) {
424 		if (remove_pool(false_stack, tmp->pool))
425 			DELETE_CURRENT_PTR(tmp);
426 	} END_FOR_EACH_PTR(tmp);
427 }
428 
sm_in_keep_leafs(struct sm_state * sm,const struct state_list * keep_gates)429 static int sm_in_keep_leafs(struct sm_state *sm, const struct state_list *keep_gates)
430 {
431 	struct sm_state *tmp, *old;
432 
433 	FOR_EACH_PTR(keep_gates, tmp) {
434 		if (is_merged(tmp))
435 			continue;
436 		old = get_sm_state_stree(tmp->pool, sm->owner, sm->name, sm->sym);
437 		if (!old)
438 			continue;
439 		if (old == sm)
440 			return 1;
441 	} END_FOR_EACH_PTR(tmp);
442 	return 0;
443 }
444 
going_too_slow(void)445 static int going_too_slow(void)
446 {
447 	static void *printed;
448 
449 	if (out_of_memory()) {
450 		implications_off = true;
451 		return 1;
452 	}
453 
454 	if (!option_timeout || time_parsing_function() < option_timeout) {
455 		implications_off = false;
456 		return 0;
457 	}
458 
459 	if (!__inline_fn && printed != cur_func_sym) {
460 		if (!is_skipped_function())
461 			sm_perror("turning off implications after %d seconds", option_timeout);
462 		printed = cur_func_sym;
463 	}
464 	implications_off = true;
465 	return 1;
466 }
467 
sm_state_info(struct sm_state * sm)468 static char *sm_state_info(struct sm_state *sm)
469 {
470 	static char buf[512];
471 	int n = 0;
472 
473 	n += snprintf(buf + n, sizeof(buf) - n, "[stree %d line %d] ",
474 		      get_stree_id(sm->pool),  sm->line);
475 	if (n >= sizeof(buf))
476 		return buf;
477 	n += snprintf(buf + n, sizeof(buf) - n, "%s ", show_sm(sm));
478 	if (n >= sizeof(buf))
479 		return buf;
480 	n += snprintf(buf + n, sizeof(buf) - n, "left = %s [stree %d] ",
481 		      sm->left ? sm->left->state->name : "<none>",
482 		      sm->left ? get_stree_id(sm->left->pool) : -1);
483 	if (n >= sizeof(buf))
484 		return buf;
485 	n += snprintf(buf + n, sizeof(buf) - n, "right = %s [stree %d]",
486 		      sm->right ? sm->right->state->name : "<none>",
487 		      sm->right ? get_stree_id(sm->right->pool) : -1);
488 	return buf;
489 }
490 
491 /*
492  * NOTE: If a state is in both the keep stack and the remove stack then that is
493  * a bug.  Only add states which are definitely true or definitely false.  If
494  * you have a leaf state that could be both true and false, then create a fake
495  * split history where one side is true and one side is false.  Otherwise, if
496  * you can't do that, then don't add it to either list.
497  */
498 #define RECURSE_LIMIT 300
filter_pools(struct sm_state * sm,const struct state_list * remove_stack,const struct state_list * keep_stack,int * modified,int * recurse_cnt,struct timeval * start,int * skip,int * bail)499 struct sm_state *filter_pools(struct sm_state *sm,
500 			      const struct state_list *remove_stack,
501 			      const struct state_list *keep_stack,
502 			      int *modified, int *recurse_cnt,
503 			      struct timeval *start, int *skip, int *bail)
504 {
505 	struct sm_state *ret = NULL;
506 	struct sm_state *left;
507 	struct sm_state *right;
508 	int removed = 0;
509 	struct timeval now, diff;
510 
511 	if (!sm)
512 		return NULL;
513 	if (*bail)
514 		return NULL;
515 	gettimeofday(&now, NULL);
516 	timersub(&now, start, &diff);
517 	if (diff.tv_sec >= 3) {
518 		DIMPLIED("%s: implications taking too long: %s\n", __func__, sm_state_info(sm));
519 		*bail = 1;
520 		return NULL;
521 	}
522 	if ((*recurse_cnt)++ > RECURSE_LIMIT) {
523 		DIMPLIED("%s: recursed too far:  %s\n", __func__, sm_state_info(sm));
524 		*skip = 1;
525 		return NULL;
526 	}
527 
528 	if (pool_in_pools(sm->pool, remove_stack)) {
529 		DIMPLIED("%s: remove: %s\n", __func__, sm_state_info(sm));
530 		*modified = 1;
531 		return NULL;
532 	}
533 
534 	if (!is_merged(sm) || pool_in_pools(sm->pool, keep_stack) || sm_in_keep_leafs(sm, keep_stack)) {
535 		DIMPLIED("%s: keep %s (%s, %s, %s): %s\n", __func__, sm->state->name,
536 			is_merged(sm) ? "merged" : "not merged",
537 			pool_in_pools(sm->pool, keep_stack) ? "not in keep pools" : "in keep pools",
538 			sm_in_keep_leafs(sm, keep_stack) ? "reachable keep leaf" : "no keep leaf",
539 			sm_state_info(sm));
540 		return sm;
541 	}
542 
543 	left = filter_pools(sm->left, remove_stack, keep_stack, &removed, recurse_cnt, start, skip, bail);
544 	right = filter_pools(sm->right, remove_stack, keep_stack, &removed, recurse_cnt, start, skip, bail);
545 	if (*bail || *skip)
546 		return NULL;
547 	if (!removed) {
548 		DIMPLIED("%s: kept all: %s\n", __func__, sm_state_info(sm));
549 		return sm;
550 	}
551 	*modified = 1;
552 	if (!left && !right) {
553 		DIMPLIED("%s: removed all: %s\n", __func__, sm_state_info(sm));
554 		return NULL;
555 	}
556 
557 	if (!left) {
558 		ret = clone_sm(right);
559 		ret->merged = 1;
560 		ret->right = right;
561 		ret->left = NULL;
562 	} else if (!right) {
563 		ret = clone_sm(left);
564 		ret->merged = 1;
565 		ret->left = left;
566 		ret->right = NULL;
567 	} else {
568 		if (left->sym != sm->sym || strcmp(left->name, sm->name) != 0) {
569 			left = clone_sm(left);
570 			left->sym = sm->sym;
571 			left->name = sm->name;
572 		}
573 		if (right->sym != sm->sym || strcmp(right->name, sm->name) != 0) {
574 			right = clone_sm(right);
575 			right->sym = sm->sym;
576 			right->name = sm->name;
577 		}
578 		ret = merge_sm_states(left, right);
579 	}
580 
581 	ret->pool = sm->pool;
582 
583 	DIMPLIED("%s: partial: %s\n", __func__, sm_state_info(sm));
584 	return ret;
585 }
586 
filter_stack(struct sm_state * gate_sm,struct stree * pre_stree,const struct state_list * remove_stack,const struct state_list * keep_stack)587 static struct stree *filter_stack(struct sm_state *gate_sm,
588 				  struct stree *pre_stree,
589 				  const struct state_list *remove_stack,
590 				  const struct state_list *keep_stack)
591 {
592 	struct stree *ret = NULL;
593 	struct sm_state *tmp;
594 	struct sm_state *filtered_sm;
595 	int modified;
596 	int recurse_cnt;
597 	struct timeval start;
598 	int skip;
599 	int bail = 0;
600 
601 	if (!remove_stack)
602 		return NULL;
603 
604 	gettimeofday(&start, NULL);
605 	FOR_EACH_SM(pre_stree, tmp) {
606 		if (!tmp->merged || sm_in_keep_leafs(tmp, keep_stack))
607 			continue;
608 		modified = 0;
609 		recurse_cnt = 0;
610 		skip = 0;
611 		filtered_sm = filter_pools(tmp, remove_stack, keep_stack, &modified, &recurse_cnt, &start, &skip, &bail);
612 		if (going_too_slow())
613 			return NULL;
614 		if (bail)
615 			return ret;  /* Return the implications we figured out before time ran out. */
616 
617 
618 		if (skip || !filtered_sm || !modified)
619 			continue;
620 		/* the assignments here are for borrowed implications */
621 		filtered_sm->name = tmp->name;
622 		filtered_sm->sym = tmp->sym;
623 		avl_insert(&ret, filtered_sm);
624 	} END_FOR_EACH_SM(tmp);
625 	return ret;
626 }
627 
separate_and_filter(struct sm_state * sm,int comparison,struct range_list * rl,struct stree * pre_stree,struct stree ** true_states,struct stree ** false_states,int * mixed)628 static void separate_and_filter(struct sm_state *sm, int comparison, struct range_list *rl,
629 		struct stree *pre_stree,
630 		struct stree **true_states,
631 		struct stree **false_states,
632 		int *mixed)
633 {
634 	struct state_list *true_stack = NULL;
635 	struct state_list *false_stack = NULL;
636 	struct timeval time_before;
637 	struct timeval time_after;
638 	int sec;
639 
640 	gettimeofday(&time_before, NULL);
641 
642 	DIMPLIED("checking implications: (%s (%s) %s %s)\n",
643 		 sm->name, sm->state->name, show_comparison(comparison), show_rl(rl));
644 
645 	if (!is_merged(sm)) {
646 		DIMPLIED("%d '%s' from line %d is not merged.\n", get_lineno(), sm->name, sm->line);
647 		return;
648 	}
649 
650 	separate_pools(sm, comparison, rl, &true_stack, &false_stack, NULL, mixed);
651 
652 	DIMPLIED("filtering true stack.\n");
653 	*true_states = filter_stack(sm, pre_stree, false_stack, true_stack);
654 	DIMPLIED("filtering false stack.\n");
655 	*false_states = filter_stack(sm, pre_stree, true_stack, false_stack);
656 	free_slist(&true_stack);
657 	free_slist(&false_stack);
658 
659 	gettimeofday(&time_after, NULL);
660 	sec = time_after.tv_sec - time_before.tv_sec;
661 	if (option_timeout && sec > option_timeout) {
662 		sm_perror("Function too hairy.  Ignoring implications after %d seconds.", sec);
663 	}
664 }
665 
get_last_expr(struct statement * stmt)666 static struct expression *get_last_expr(struct statement *stmt)
667 {
668 	struct statement *last;
669 
670 	last = last_ptr_list((struct ptr_list *)stmt->stmts);
671 	if (last->type == STMT_EXPRESSION)
672 		return last->expression;
673 
674 	if (last->type == STMT_LABEL) {
675 		if (last->label_statement &&
676 		    last->label_statement->type == STMT_EXPRESSION)
677 			return last->label_statement->expression;
678 	}
679 
680 	return NULL;
681 }
682 
get_left_most_expr(struct expression * expr)683 static struct expression *get_left_most_expr(struct expression *expr)
684 {
685 	struct statement *compound;
686 
687 	compound = get_expression_statement(expr);
688 	if (compound)
689 		return get_last_expr(compound);
690 
691 	expr = strip_parens(expr);
692 	if (expr->type == EXPR_ASSIGNMENT)
693 		return get_left_most_expr(expr->left);
694 	return expr;
695 }
696 
is_merged_expr(struct expression * expr)697 static int is_merged_expr(struct expression  *expr)
698 {
699 	struct sm_state *sm;
700 	sval_t dummy;
701 
702 	if (get_value(expr, &dummy))
703 		return 0;
704 	sm = get_sm_state_expr(SMATCH_EXTRA, expr);
705 	if (!sm)
706 		return 0;
707 	if (is_merged(sm))
708 		return 1;
709 	return 0;
710 }
711 
delete_gate_sm_equiv(struct stree ** stree,const char * name,struct symbol * sym)712 static void delete_gate_sm_equiv(struct stree **stree, const char *name, struct symbol *sym)
713 {
714 	struct smatch_state *state;
715 	struct relation *rel;
716 
717 	state = get_state(SMATCH_EXTRA, name, sym);
718 	if (!state)
719 		return;
720 	FOR_EACH_PTR(estate_related(state), rel) {
721 		delete_state_stree(stree, SMATCH_EXTRA, rel->name, rel->sym);
722 	} END_FOR_EACH_PTR(rel);
723 }
724 
delete_gate_sm(struct stree ** stree,const char * name,struct symbol * sym)725 static void delete_gate_sm(struct stree **stree, const char *name, struct symbol *sym)
726 {
727 	delete_state_stree(stree, SMATCH_EXTRA, name, sym);
728 }
729 
handle_comparison(struct expression * expr,struct stree ** implied_true,struct stree ** implied_false)730 static int handle_comparison(struct expression *expr,
731 			      struct stree **implied_true,
732 			      struct stree **implied_false)
733 {
734 	struct sm_state *sm = NULL;
735 	struct range_list *rl = NULL;
736 	struct expression *left;
737 	struct expression *right;
738 	struct symbol *type;
739 	int comparison = expr->op;
740 	int mixed = 0;
741 
742 	left = get_left_most_expr(expr->left);
743 	right = get_left_most_expr(expr->right);
744 
745 	if (is_merged_expr(left)) {
746 		sm = get_sm_state_expr(SMATCH_EXTRA, left);
747 		get_implied_rl(right, &rl);
748 	} else if (is_merged_expr(right)) {
749 		sm = get_sm_state_expr(SMATCH_EXTRA, right);
750 		get_implied_rl(left, &rl);
751 		comparison = flip_comparison(comparison);
752 	}
753 
754 	if (!rl || !sm)
755 		return 0;
756 
757 	type = get_type(expr);
758 	if (!type)
759 		return 0;
760 	if (type_positive_bits(rl_type(rl)) > type_positive_bits(type))
761 		type = rl_type(rl);
762 	if (type_positive_bits(type) < 31)
763 		type = &int_ctype;
764 	rl = cast_rl(type, rl);
765 
766 	separate_and_filter(sm, comparison, rl, __get_cur_stree(), implied_true, implied_false, &mixed);
767 
768 	delete_gate_sm_equiv(implied_true, sm->name, sm->sym);
769 	delete_gate_sm_equiv(implied_false, sm->name, sm->sym);
770 	if (mixed) {
771 		delete_gate_sm(implied_true, sm->name, sm->sym);
772 		delete_gate_sm(implied_false, sm->name, sm->sym);
773 	}
774 
775 	return 1;
776 }
777 
handle_zero_comparison(struct expression * expr,struct stree ** implied_true,struct stree ** implied_false)778 static int handle_zero_comparison(struct expression *expr,
779 				struct stree **implied_true,
780 				struct stree **implied_false)
781 {
782 	struct symbol *sym;
783 	char *name;
784 	struct sm_state *sm;
785 	int mixed = 0;
786 	int ret = 0;
787 
788 	if (expr->type == EXPR_POSTOP)
789 		expr = strip_expr(expr->unop);
790 
791 	if (expr->type == EXPR_ASSIGNMENT) {
792 		/* most of the time ->pools will be empty here because we
793 		   just set the state, but if have assigned a conditional
794 		   function there are implications. */
795 		expr = expr->left;
796 	}
797 
798 	name = expr_to_var_sym(expr, &sym);
799 	if (!name || !sym)
800 		goto free;
801 	sm = get_sm_state(SMATCH_EXTRA, name, sym);
802 	if (!sm || !sm->merged)
803 		goto free;
804 
805 	separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(estate_type(sm->state), 0), __get_cur_stree(), implied_true, implied_false, &mixed);
806 	delete_gate_sm_equiv(implied_true, sm->name, sm->sym);
807 	delete_gate_sm_equiv(implied_false, sm->name, sm->sym);
808 	if (mixed) {
809 		delete_gate_sm(implied_true, sm->name, sm->sym);
810 		delete_gate_sm(implied_false, sm->name, sm->sym);
811 	}
812 
813 	ret = 1;
814 free:
815 	free_string(name);
816 	return ret;
817 }
818 
handled_by_comparison_hook(struct expression * expr,struct stree ** implied_true,struct stree ** implied_false)819 static int handled_by_comparison_hook(struct expression *expr,
820 				      struct stree **implied_true,
821 				      struct stree **implied_false)
822 {
823 	struct sm_state *sm, *true_sm, *false_sm;
824 	struct state_list *true_stack = NULL;
825 	struct state_list *false_stack = NULL;
826 	struct stree *pre_stree;
827 
828 	sm = comparison_implication_hook(expr, &true_stack, &false_stack);
829 	if (!sm)
830 		return 0;
831 
832 	pre_stree = clone_stree(__get_cur_stree());
833 
834 	*implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
835 	*implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
836 
837 	true_sm = get_sm_state_stree(*implied_true, sm->owner, sm->name, sm->sym);
838 	false_sm = get_sm_state_stree(*implied_false, sm->owner, sm->name, sm->sym);
839 	if (true_sm && strcmp(true_sm->state->name, "unknown") == 0)
840 		delete_state_stree(implied_true, sm->owner, sm->name, sm->sym);
841 	if (false_sm && strcmp(false_sm->state->name, "unknown") == 0)
842 		delete_state_stree(implied_false, sm->owner, sm->name, sm->sym);
843 
844 	free_stree(&pre_stree);
845 	free_slist(&true_stack);
846 	free_slist(&false_stack);
847 
848 	return 1;
849 }
850 
handled_by_extra_states(struct expression * expr,struct stree ** implied_true,struct stree ** implied_false)851 static int handled_by_extra_states(struct expression *expr,
852 				   struct stree **implied_true,
853 				   struct stree **implied_false)
854 {
855 	sval_t sval;
856 
857 	/* If the expression is known then it has no implications.  */
858 	if (get_implied_value(expr, &sval))
859 		return true;
860 
861 	if (expr->type == EXPR_COMPARE)
862 		return handle_comparison(expr, implied_true, implied_false);
863 	else
864 		return handle_zero_comparison(expr, implied_true, implied_false);
865 }
866 
handled_by_parsed_conditions(struct expression * expr,struct stree ** implied_true,struct stree ** implied_false)867 static int handled_by_parsed_conditions(struct expression *expr,
868 					struct stree **implied_true,
869 					struct stree **implied_false)
870 {
871 	struct state_list *true_stack = NULL;
872 	struct state_list *false_stack = NULL;
873 	struct stree *pre_stree;
874 	struct sm_state *sm;
875 
876 	sm = parsed_condition_implication_hook(expr, &true_stack, &false_stack);
877 	if (!sm)
878 		return 0;
879 
880 	pre_stree = clone_stree(__get_cur_stree());
881 
882 	*implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
883 	*implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
884 
885 	free_stree(&pre_stree);
886 	free_slist(&true_stack);
887 	free_slist(&false_stack);
888 
889 	return 1;
890 }
891 
handled_by_stored_conditions(struct expression * expr,struct stree ** implied_true,struct stree ** implied_false)892 static int handled_by_stored_conditions(struct expression *expr,
893 					struct stree **implied_true,
894 					struct stree **implied_false)
895 {
896 	struct state_list *true_stack = NULL;
897 	struct state_list *false_stack = NULL;
898 	struct stree *pre_stree;
899 	struct sm_state *sm;
900 
901 	sm = stored_condition_implication_hook(expr, &true_stack, &false_stack);
902 	if (!sm)
903 		return 0;
904 
905 	pre_stree = clone_stree(__get_cur_stree());
906 
907 	*implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
908 	*implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
909 
910 	free_stree(&pre_stree);
911 	free_slist(&true_stack);
912 	free_slist(&false_stack);
913 
914 	return 1;
915 }
916 
917 static struct stree *saved_implied_true;
918 static struct stree *saved_implied_false;
919 static struct stree *extra_saved_implied_true;
920 static struct stree *extra_saved_implied_false;
921 
separate_implication_states(struct stree ** implied_true,struct stree ** implied_false,int owner)922 static void separate_implication_states(struct stree **implied_true,
923 					 struct stree **implied_false,
924 					 int owner)
925 {
926 	struct sm_state *sm;
927 
928 	/* We process these states later to preserve the implications. */
929 	FOR_EACH_SM(*implied_true, sm) {
930 		if (sm->owner == owner)
931 			overwrite_sm_state_stree(&extra_saved_implied_true, sm);
932 	} END_FOR_EACH_SM(sm);
933 	FOR_EACH_SM(extra_saved_implied_true, sm) {
934 		delete_state_stree(implied_true, sm->owner, sm->name, sm->sym);
935 	} END_FOR_EACH_SM(sm);
936 
937 	FOR_EACH_SM(*implied_false, sm) {
938 		if (sm->owner == owner)
939 			overwrite_sm_state_stree(&extra_saved_implied_false, sm);
940 	} END_FOR_EACH_SM(sm);
941 	FOR_EACH_SM(extra_saved_implied_false, sm) {
942 		delete_state_stree(implied_false, sm->owner, sm->name, sm->sym);
943 	} END_FOR_EACH_SM(sm);
944 }
945 
get_tf_states(struct expression * expr,struct stree ** implied_true,struct stree ** implied_false)946 static void get_tf_states(struct expression *expr,
947 			  struct stree **implied_true,
948 			  struct stree **implied_false)
949 {
950 	if (handled_by_parsed_conditions(expr, implied_true, implied_false))
951 		return;
952 
953 	if (handled_by_comparison_hook(expr, implied_true, implied_false)) {
954 		separate_implication_states(implied_true, implied_false, comparison_id);
955 		return;
956 	}
957 
958 	if (handled_by_extra_states(expr, implied_true, implied_false)) {
959 		separate_implication_states(implied_true, implied_false, SMATCH_EXTRA);
960 		return;
961 	}
962 
963 	if (handled_by_stored_conditions(expr, implied_true, implied_false))
964 		return;
965 }
966 
save_implications_hook(struct expression * expr)967 static void save_implications_hook(struct expression *expr)
968 {
969 	if (going_too_slow())
970 		return;
971 	get_tf_states(expr, &saved_implied_true, &saved_implied_false);
972 }
973 
set_implied_states(struct expression * expr)974 static void set_implied_states(struct expression *expr)
975 {
976 	struct sm_state *sm;
977 
978 	if (implied_debug &&
979 	    (expr || saved_implied_true || saved_implied_false)) {
980 		char *name;
981 
982 		name = expr_to_str(expr);
983 		printf("These are the implied states for the true path: (%s)\n", name);
984 		__print_stree(saved_implied_true);
985 		printf("These are the implied states for the false path: (%s)\n", name);
986 		__print_stree(saved_implied_false);
987 		free_string(name);
988 	}
989 
990 	FOR_EACH_SM(saved_implied_true, sm) {
991 		__set_true_false_sm(sm, NULL);
992 	} END_FOR_EACH_SM(sm);
993 	free_stree(&saved_implied_true);
994 
995 	FOR_EACH_SM(saved_implied_false, sm) {
996 		__set_true_false_sm(NULL, sm);
997 	} END_FOR_EACH_SM(sm);
998 	free_stree(&saved_implied_false);
999 }
1000 
set_extra_implied_states(struct expression * expr)1001 static void set_extra_implied_states(struct expression *expr)
1002 {
1003 	saved_implied_true = extra_saved_implied_true;
1004 	saved_implied_false = extra_saved_implied_false;
1005 	extra_saved_implied_true = NULL;
1006 	extra_saved_implied_false = NULL;
1007 	set_implied_states(NULL);
1008 }
1009 
param_limit_implications(struct expression * expr,int param,char * key,char * value,struct stree ** implied)1010 void param_limit_implications(struct expression *expr, int param, char *key, char *value, struct stree **implied)
1011 {
1012 	struct expression *orig_expr, *arg;
1013 	struct symbol *compare_type;
1014 	char *name;
1015 	struct symbol *sym;
1016 	struct sm_state *sm;
1017 	struct sm_state *tmp;
1018 	struct stree *implied_true = NULL;
1019 	struct stree *implied_false = NULL;
1020 	struct range_list *orig, *limit;
1021 	char *left_name = NULL;
1022 	struct symbol *left_sym = NULL;
1023 	int mixed = 0;
1024 
1025 	if (time_parsing_function() > 40)
1026 		return;
1027 
1028 	orig_expr = expr;
1029 	while (expr->type == EXPR_ASSIGNMENT)
1030 		expr = strip_expr(expr->right);
1031 	if (expr->type != EXPR_CALL)
1032 		return;
1033 
1034 	arg = get_argument_from_call_expr(expr->args, param);
1035 	if (!arg)
1036 		return;
1037 
1038 	arg = strip_parens(arg);
1039 	while (arg->type == EXPR_ASSIGNMENT && arg->op == '=')
1040 		arg = strip_parens(arg->left);
1041 
1042 	name = get_variable_from_key(arg, key, &sym);
1043 	if (!name || !sym)
1044 		goto free;
1045 
1046 	sm = get_sm_state(SMATCH_EXTRA, name, sym);
1047 	if (!sm || !sm->merged)
1048 		goto free;
1049 
1050 	if (strcmp(key, "$") == 0)
1051 		compare_type = get_arg_type(expr->fn, param);
1052 	else
1053 		compare_type = get_member_type_from_key(arg, key);
1054 
1055 	orig = estate_rl(sm->state);
1056 	orig = cast_rl(compare_type, orig);
1057 
1058 	call_results_to_rl(expr, compare_type, value, &limit);
1059 
1060 	separate_and_filter(sm, PARAM_LIMIT, limit, __get_cur_stree(), &implied_true, &implied_false, &mixed);
1061 
1062 	if (orig_expr->type == EXPR_ASSIGNMENT)
1063 		left_name = expr_to_var_sym(orig_expr->left, &left_sym);
1064 
1065 	FOR_EACH_SM(implied_true, tmp) {
1066 		/*
1067 		 * What we're trying to do here is preserve the sm state so that
1068 		 * smatch extra doesn't create a new sm state when it parses the
1069 		 * PARAM_LIMIT.
1070 		 */
1071 		if (!mixed && tmp->sym == sym &&
1072 		    strcmp(tmp->name, name) == 0 &&
1073 		    (!left_name || strcmp(left_name, name) != 0)) {
1074 			overwrite_sm_state_stree(implied, tmp);
1075 			continue;
1076 		}
1077 
1078 		// TODO why can't this just be __set_sm()?
1079 		__set_sm_fake_stree(tmp);
1080 	} END_FOR_EACH_SM(tmp);
1081 
1082 	free_stree(&implied_true);
1083 	free_stree(&implied_false);
1084 free:
1085 	free_string(name);
1086 }
1087 
__implied_case_stree(struct expression * switch_expr,struct range_list * rl,struct range_list_stack ** remaining_cases,struct stree ** raw_stree)1088 struct stree *__implied_case_stree(struct expression *switch_expr,
1089 				   struct range_list *rl,
1090 				   struct range_list_stack **remaining_cases,
1091 				   struct stree **raw_stree)
1092 {
1093 	char *name;
1094 	struct symbol *sym;
1095 	struct var_sym_list *vsl;
1096 	struct sm_state *sm;
1097 	struct stree *true_states = NULL;
1098 	struct stree *false_states = NULL;
1099 	struct stree *extra_states;
1100 	struct stree *ret = clone_stree(*raw_stree);
1101 
1102 	name = expr_to_chunk_sym_vsl(switch_expr, &sym, &vsl);
1103 
1104 	if (rl)
1105 		filter_top_rl(remaining_cases, rl);
1106 	else
1107 		rl = clone_rl(top_rl(*remaining_cases));
1108 
1109 	if (name) {
1110 		sm = get_sm_state_stree(*raw_stree, SMATCH_EXTRA, name, sym);
1111 		if (sm)
1112 			separate_and_filter(sm, SPECIAL_EQUAL, rl, *raw_stree, &true_states, &false_states, NULL);
1113 	}
1114 
1115 	__push_fake_cur_stree();
1116 	__unnullify_path();
1117 	if (name)
1118 		set_extra_nomod_vsl(name, sym, vsl, NULL, alloc_estate_rl(rl));
1119 	__pass_case_to_client(switch_expr, rl);
1120 	extra_states = __pop_fake_cur_stree();
1121 	overwrite_stree(extra_states, &true_states);
1122 	overwrite_stree(true_states, &ret);
1123 	free_stree(&extra_states);
1124 	free_stree(&true_states);
1125 	free_stree(&false_states);
1126 
1127 	free_string(name);
1128 	return ret;
1129 }
1130 
match_end_func(struct symbol * sym)1131 static void match_end_func(struct symbol *sym)
1132 {
1133 	if (__inline_fn)
1134 		return;
1135 	implied_debug_msg = NULL;
1136 }
1137 
get_tf_stacks_from_pool(struct sm_state * gate_sm,struct sm_state * pool_sm,struct state_list ** true_stack,struct state_list ** false_stack)1138 static void get_tf_stacks_from_pool(struct sm_state *gate_sm,
1139 				    struct sm_state *pool_sm,
1140 				    struct state_list **true_stack,
1141 				    struct state_list **false_stack)
1142 {
1143 	struct sm_state *tmp;
1144 	int possibly_true = 0;
1145 
1146 	if (!gate_sm)
1147 		return;
1148 
1149 	if (strcmp(gate_sm->state->name, pool_sm->state->name) == 0) {
1150 		add_ptr_list(true_stack, pool_sm);
1151 		return;
1152 	}
1153 
1154 	FOR_EACH_PTR(gate_sm->possible, tmp) {
1155 		if (strcmp(tmp->state->name, pool_sm->state->name) == 0) {
1156 			possibly_true = 1;
1157 			break;
1158 		}
1159 	} END_FOR_EACH_PTR(tmp);
1160 
1161 	if (!possibly_true) {
1162 		add_ptr_list(false_stack, gate_sm);
1163 		return;
1164 	}
1165 
1166 	get_tf_stacks_from_pool(gate_sm->left, pool_sm, true_stack, false_stack);
1167 	get_tf_stacks_from_pool(gate_sm->right, pool_sm, true_stack, false_stack);
1168 }
1169 
1170 /*
1171  * The situation is we have a SMATCH_EXTRA state and we want to break it into
1172  * each of the ->possible states and find the implications of each.  The caller
1173  * has to use __push_fake_cur_stree() to preserve the correct states so they
1174  * can be restored later.
1175  */
overwrite_states_using_pool(struct sm_state * gate_sm,struct sm_state * pool_sm)1176 void overwrite_states_using_pool(struct sm_state *gate_sm, struct sm_state *pool_sm)
1177 {
1178 	struct state_list *true_stack = NULL;
1179 	struct state_list *false_stack = NULL;
1180 	struct stree *pre_stree;
1181 	struct stree *implied_true;
1182 	struct sm_state *tmp;
1183 
1184 	if (!pool_sm->pool)
1185 		return;
1186 
1187 	get_tf_stacks_from_pool(gate_sm, pool_sm, &true_stack, &false_stack);
1188 
1189 	pre_stree = clone_stree(__get_cur_stree());
1190 
1191 	implied_true = filter_stack(gate_sm, pre_stree, false_stack, true_stack);
1192 
1193 	free_stree(&pre_stree);
1194 	free_slist(&true_stack);
1195 	free_slist(&false_stack);
1196 
1197 	FOR_EACH_SM(implied_true, tmp) {
1198 		set_state(tmp->owner, tmp->name, tmp->sym, tmp->state);
1199 	} END_FOR_EACH_SM(tmp);
1200 
1201 	free_stree(&implied_true);
1202 }
1203 
assume(struct expression * expr)1204 int assume(struct expression *expr)
1205 {
1206 	int orig_final_pass = final_pass;
1207 
1208 	in_fake_env++;
1209 	final_pass = 0;
1210 	__push_fake_cur_stree();
1211 	__split_whole_condition(expr);
1212 	final_pass = orig_final_pass;
1213 	in_fake_env--;
1214 
1215 	return 1;
1216 }
1217 
end_assume(void)1218 void end_assume(void)
1219 {
1220 	__discard_false_states();
1221 	__free_fake_cur_stree();
1222 }
1223 
impossible_assumption(struct expression * left,int op,sval_t sval)1224 int impossible_assumption(struct expression *left, int op, sval_t sval)
1225 {
1226 	struct expression *value;
1227 	struct expression *comparison;
1228 	int ret;
1229 
1230 	value = value_expr(sval.value);
1231 	comparison = compare_expression(left, op, value);
1232 
1233 	if (!assume(comparison))
1234 		return 0;
1235 	ret = is_impossible_path();
1236 	end_assume();
1237 
1238 	return ret;
1239 }
1240 
1241 void __extra_match_condition(struct expression *expr);
1242 void __comparison_match_condition(struct expression *expr);
1243 void __stored_condition(struct expression *expr);
register_implications(int id)1244 void register_implications(int id)
1245 {
1246 	add_hook(&save_implications_hook, CONDITION_HOOK);
1247 	add_hook(&set_implied_states, CONDITION_HOOK);
1248 	add_hook(&__extra_match_condition, CONDITION_HOOK);
1249 	add_hook(&__comparison_match_condition, CONDITION_HOOK);
1250 	add_hook(&set_extra_implied_states, CONDITION_HOOK);
1251 	add_hook(&__stored_condition, CONDITION_HOOK);
1252 	add_hook(&match_end_func, END_FUNC_HOOK);
1253 }
1254