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