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