Print this page
12166 resync smatch to 0.6.1-rc1-il-3
Split |
Close |
Expand all |
Collapse all |
--- old/usr/src/tools/smatch/src/smatch_states.c
+++ new/usr/src/tools/smatch/src/smatch_states.c
1 1 /*
2 2 * Copyright (C) 2006 Dan Carpenter.
3 3 *
4 4 * This program is free software; you can redistribute it and/or
5 5 * modify it under the terms of the GNU General Public License
6 6 * as published by the Free Software Foundation; either version 2
7 7 * of the License, or (at your option) any later version.
8 8 *
9 9 * This program is distributed in the hope that it will be useful,
10 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 12 * GNU General Public License for more details.
13 13 *
14 14 * You should have received a copy of the GNU General Public License
15 15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16 16 */
17 17
18 18 /*
19 19 * You have a lists of states. kernel = locked, foo = NULL, ...
20 20 * When you hit an if {} else {} statement then you swap the list
21 21 * of states for a different list of states. The lists are stored
22 22 * on stacks.
23 23 *
24 24 * At the beginning of this file there are list of the stacks that
25 25 * we use. Each function in this file does something to one of
26 26 * of the stacks.
27 27 *
28 28 * So the smatch_flow.c understands code but it doesn't understand states.
29 29 * smatch_flow calls functions in this file. This file calls functions
30 30 * in smatch_slist.c which just has boring generic plumbing for handling
31 31 * state lists. But really it's this file where all the magic happens.
32 32 */
33 33
34 34 #include <stdlib.h>
35 35 #include <stdio.h>
36 36 #include "smatch.h"
37 37 #include "smatch_slist.h"
38 38 #include "smatch_extra.h"
39 39
40 40 struct smatch_state undefined = { .name = "undefined" };
41 41 struct smatch_state ghost = { .name = "ghost" };
42 42 struct smatch_state merged = { .name = "merged" };
43 43 struct smatch_state true_state = { .name = "true" };
44 44 struct smatch_state false_state = { .name = "false" };
45 45
46 46 static struct stree *cur_stree; /* current states */
47 47 static struct stree *fast_overlay;
48 48
49 49 static struct stree_stack *true_stack; /* states after a t/f branch */
50 50 static struct stree_stack *false_stack;
51 51 static struct stree_stack *pre_cond_stack; /* states before a t/f branch */
52 52
53 53 static struct stree_stack *cond_true_stack; /* states affected by a branch */
54 54 static struct stree_stack *cond_false_stack;
55 55
56 56 static struct stree_stack *fake_cur_stree_stack;
57 57 static int read_only;
58 58
59 59 static struct stree_stack *break_stack;
60 60 static struct stree_stack *fake_break_stack;
61 61 static struct stree_stack *switch_stack;
62 62 static struct range_list_stack *remaining_cases;
63 63 static struct stree_stack *default_stack;
64 64 static struct stree_stack *continue_stack;
65 65
66 66 static struct named_stree_stack *goto_stack;
67 67
68 68 static struct ptr_list *backup;
69 69
70 70 int option_debug;
71 71
72 72 void __print_cur_stree(void)
73 73 {
74 74 __print_stree(cur_stree);
75 75 }
76 76
77 77 int unreachable(void)
78 78 {
79 79 if (!cur_stree)
80 80 return 1;
81 81 return 0;
82 82 }
83 83
84 84 void __set_cur_stree_readonly(void)
85 85 {
86 86 read_only++;
87 87 }
88 88
89 89 void __set_cur_stree_writable(void)
90 90 {
91 91 read_only--;
92 92 }
93 93
94 94 struct sm_state *set_state(int owner, const char *name, struct symbol *sym, struct smatch_state *state)
95 95 {
96 96 struct sm_state *ret;
97 97
98 98 if (!name || !state)
99 99 return NULL;
100 100
101 101 if (read_only)
102 102 sm_perror("cur_stree is read only.");
103 103
104 104 if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
105 105 struct smatch_state *s;
106 106
107 107 s = __get_state(owner, name, sym);
108 108 if (!s)
109 109 sm_msg("%s new [%s] '%s' %s", __func__,
110 110 check_name(owner), name, show_state(state));
111 111 else
112 112 sm_msg("%s change [%s] '%s' %s => %s",
113 113 __func__, check_name(owner), name, show_state(s),
114 114 show_state(state));
115 115 }
116 116
117 117 if (owner != -1 && unreachable())
118 118 return NULL;
119 119
120 120 if (fake_cur_stree_stack)
121 121 set_state_stree_stack(&fake_cur_stree_stack, owner, name, sym, state);
122 122
123 123 ret = set_state_stree(&cur_stree, owner, name, sym, state);
124 124
125 125 return ret;
126 126 }
127 127
128 128 struct sm_state *set_state_expr(int owner, struct expression *expr, struct smatch_state *state)
129 129 {
130 130 char *name;
131 131 struct symbol *sym;
132 132 struct sm_state *ret = NULL;
133 133
134 134 expr = strip_expr(expr);
135 135 name = expr_to_var_sym(expr, &sym);
136 136 if (!name || !sym)
137 137 goto free;
138 138 ret = set_state(owner, name, sym, state);
139 139 free:
140 140 free_string(name);
141 141 return ret;
142 142 }
143 143
144 144 struct stree *__swap_cur_stree(struct stree *stree)
145 145 {
146 146 struct stree *orig = cur_stree;
147 147
148 148 cur_stree = stree;
149 149 return orig;
150 150 }
151 151
152 152 void __push_fake_cur_stree(void)
153 153 {
154 154 push_stree(&fake_cur_stree_stack, NULL);
155 155 __save_pre_cond_states();
156 156 }
157 157
158 158 struct stree *__pop_fake_cur_stree(void)
159 159 {
160 160 if (!fake_cur_stree_stack)
161 161 sm_perror("popping too many fake cur strees.");
162 162 __use_pre_cond_states();
163 163 return pop_stree(&fake_cur_stree_stack);
164 164 }
165 165
166 166 void __free_fake_cur_stree(void)
167 167 {
168 168 struct stree *stree;
169 169
170 170 stree = __pop_fake_cur_stree();
171 171 free_stree(&stree);
172 172 }
173 173
174 174 void __set_fake_cur_stree_fast(struct stree *stree)
175 175 {
176 176 if (fast_overlay) {
177 177 sm_perror("cannot nest fast overlay");
178 178 return;
179 179 }
180 180 fast_overlay = stree;
181 181 set_fast_math_only();
182 182 }
183 183
184 184 void __pop_fake_cur_stree_fast(void)
185 185 {
186 186 fast_overlay = NULL;
187 187 clear_fast_math_only();
188 188 }
189 189
190 190 void __merge_stree_into_cur(struct stree *stree)
191 191 {
192 192 struct sm_state *sm;
193 193 struct sm_state *orig;
194 194 struct sm_state *merged;
195 195
196 196 FOR_EACH_SM(stree, sm) {
197 197 orig = get_sm_state(sm->owner, sm->name, sm->sym);
198 198 if (orig)
199 199 merged = merge_sm_states(orig, sm);
200 200 else
201 201 merged = sm;
202 202 __set_sm(merged);
203 203 } END_FOR_EACH_SM(sm);
204 204 }
205 205
206 206 void __set_sm(struct sm_state *sm)
207 207 {
208 208 if (read_only)
209 209 sm_perror("cur_stree is read only.");
210 210
211 211 if (option_debug ||
212 212 strcmp(check_name(sm->owner), option_debug_check) == 0) {
213 213 struct smatch_state *s;
214 214
215 215 s = __get_state(sm->owner, sm->name, sm->sym);
216 216 if (!s)
217 217 sm_msg("%s new %s", __func__, show_sm(sm));
218 218 else
219 219 sm_msg("%s change %s (was %s)", __func__, show_sm(sm),
220 220 show_state(s));
221 221 }
222 222
223 223 if (unreachable())
224 224 return;
225 225
226 226 if (fake_cur_stree_stack)
227 227 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
228 228
229 229 overwrite_sm_state_stree(&cur_stree, sm);
230 230 }
231 231
232 232 void __set_sm_cur_stree(struct sm_state *sm)
233 233 {
234 234 if (read_only)
235 235 sm_perror("cur_stree is read only.");
236 236
237 237 if (option_debug ||
238 238 strcmp(check_name(sm->owner), option_debug_check) == 0) {
239 239 struct smatch_state *s;
240 240
241 241 s = __get_state(sm->owner, sm->name, sm->sym);
242 242 if (!s)
243 243 sm_msg("%s new %s", __func__, show_sm(sm));
244 244 else
245 245 sm_msg("%s change %s (was %s)",
246 246 __func__, show_sm(sm), show_state(s));
247 247 }
248 248
249 249 if (unreachable())
250 250 return;
251 251
252 252 overwrite_sm_state_stree(&cur_stree, sm);
253 253 }
254 254
255 255 void __set_sm_fake_stree(struct sm_state *sm)
256 256 {
257 257 if (read_only)
258 258 sm_perror("cur_stree is read only.");
259 259
260 260 if (option_debug ||
261 261 strcmp(check_name(sm->owner), option_debug_check) == 0) {
262 262 struct smatch_state *s;
263 263
264 264 s = __get_state(sm->owner, sm->name, sm->sym);
265 265 if (!s)
266 266 sm_msg("%s new %s", __func__, show_sm(sm));
267 267 else
268 268 sm_msg("%s change %s (was %s)",
269 269 __func__, show_sm(sm), show_state(s));
270 270 }
271 271
272 272 if (unreachable())
273 273 return;
274 274
275 275 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
276 276 }
277 277
278 278
279 279 typedef void (get_state_hook)(int owner, const char *name, struct symbol *sym);
280 280 DECLARE_PTR_LIST(fn_list, get_state_hook *);
281 281 static struct fn_list *get_state_hooks;
282 282
283 283 void add_get_state_hook(get_state_hook *fn)
284 284 {
285 285 get_state_hook **p = malloc(sizeof(get_state_hook *));
286 286 *p = fn;
287 287 add_ptr_list(&get_state_hooks, p);
288 288 }
289 289
290 290 static void call_get_state_hooks(int owner, const char *name, struct symbol *sym)
291 291 {
292 292 static int recursion;
293 293 get_state_hook **fn;
294 294
295 295 if (recursion)
296 296 return;
297 297 recursion = 1;
298 298
299 299 FOR_EACH_PTR(get_state_hooks, fn) {
300 300 (*fn)(owner, name, sym);
301 301 } END_FOR_EACH_PTR(fn);
302 302
303 303 recursion = 0;
304 304 }
305 305
306 306 struct smatch_state *__get_state(int owner, const char *name, struct symbol *sym)
307 307 {
308 308 struct sm_state *sm;
309 309
310 310 sm = get_sm_state(owner, name, sym);
311 311 if (!sm)
312 312 return NULL;
313 313 return sm->state;
314 314 }
315 315
316 316 struct smatch_state *get_state(int owner, const char *name, struct symbol *sym)
317 317 {
318 318 call_get_state_hooks(owner, name, sym);
319 319
320 320 return __get_state(owner, name, sym);
321 321 }
322 322
323 323 struct smatch_state *get_state_expr(int owner, struct expression *expr)
324 324 {
325 325 char *name;
326 326 struct symbol *sym;
327 327 struct smatch_state *ret = NULL;
328 328
329 329 expr = strip_expr(expr);
330 330 name = expr_to_var_sym(expr, &sym);
331 331 if (!name || !sym)
332 332 goto free;
333 333 ret = get_state(owner, name, sym);
334 334 free:
335 335 free_string(name);
336 336 return ret;
337 337 }
338 338
339 339 struct state_list *get_possible_states(int owner, const char *name, struct symbol *sym)
340 340 {
341 341 struct sm_state *sms;
342 342
343 343 sms = get_sm_state_stree(cur_stree, owner, name, sym);
344 344 if (sms)
345 345 return sms->possible;
346 346 return NULL;
347 347 }
348 348
349 349 struct state_list *get_possible_states_expr(int owner, struct expression *expr)
350 350 {
351 351 char *name;
352 352 struct symbol *sym;
353 353 struct state_list *ret = NULL;
354 354
355 355 expr = strip_expr(expr);
356 356 name = expr_to_var_sym(expr, &sym);
357 357 if (!name || !sym)
358 358 goto free;
359 359 ret = get_possible_states(owner, name, sym);
360 360 free:
361 361 free_string(name);
362 362 return ret;
363 363 }
364 364
365 365 struct sm_state *get_sm_state(int owner, const char *name, struct symbol *sym)
366 366 {
367 367 struct sm_state *ret;
368 368
369 369 ret = get_sm_state_stree(fast_overlay, owner, name, sym);
370 370 if (ret)
371 371 return ret;
372 372
373 373 return get_sm_state_stree(cur_stree, owner, name, sym);
374 374 }
375 375
376 376 struct sm_state *get_sm_state_expr(int owner, struct expression *expr)
377 377 {
378 378 char *name;
379 379 struct symbol *sym;
380 380 struct sm_state *ret = NULL;
381 381
382 382 expr = strip_expr(expr);
383 383 name = expr_to_var_sym(expr, &sym);
384 384 if (!name || !sym)
385 385 goto free;
386 386 ret = get_sm_state(owner, name, sym);
387 387 free:
388 388 free_string(name);
389 389 return ret;
390 390 }
391 391
392 392 void delete_state(int owner, const char *name, struct symbol *sym)
393 393 {
394 394 delete_state_stree(&cur_stree, owner, name, sym);
395 395 if (cond_true_stack) {
396 396 delete_state_stree_stack(&pre_cond_stack, owner, name, sym);
397 397 delete_state_stree_stack(&cond_true_stack, owner, name, sym);
398 398 delete_state_stree_stack(&cond_false_stack, owner, name, sym);
399 399 }
400 400 }
401 401
402 402 void delete_state_expr(int owner, struct expression *expr)
403 403 {
404 404 char *name;
405 405 struct symbol *sym;
406 406
407 407 expr = strip_expr(expr);
408 408 name = expr_to_var_sym(expr, &sym);
409 409 if (!name || !sym)
410 410 goto free;
411 411 delete_state(owner, name, sym);
412 412 free:
413 413 free_string(name);
414 414 }
415 415
416 416 static void delete_all_states_stree_sym(struct stree **stree, struct symbol *sym)
417 417 {
418 418 struct state_list *slist = NULL;
419 419 struct sm_state *sm;
420 420
421 421 FOR_EACH_SM(*stree, sm) {
422 422 if (sm->sym == sym)
423 423 add_ptr_list(&slist, sm);
424 424 } END_FOR_EACH_SM(sm);
425 425
426 426 FOR_EACH_PTR(slist, sm) {
427 427 delete_state_stree(stree, sm->owner, sm->name, sm->sym);
428 428 } END_FOR_EACH_PTR(sm);
429 429
430 430 free_slist(&slist);
431 431 }
432 432
433 433 static void delete_all_states_stree_stack_sym(struct stree_stack **stack, struct symbol *sym)
434 434 {
435 435 struct stree *stree;
436 436
437 437 if (!*stack)
438 438 return;
439 439
440 440 stree = pop_stree(stack);
441 441 delete_all_states_stree_sym(&stree, sym);
442 442 push_stree(stack, stree);
443 443 }
444 444
445 445 void __delete_all_states_sym(struct symbol *sym)
446 446 {
447 447 delete_all_states_stree_sym(&cur_stree, sym);
448 448
449 449 delete_all_states_stree_stack_sym(&true_stack, sym);
450 450 delete_all_states_stree_stack_sym(&true_stack, sym);
451 451 delete_all_states_stree_stack_sym(&false_stack, sym);
452 452 delete_all_states_stree_stack_sym(&pre_cond_stack, sym);
453 453 delete_all_states_stree_stack_sym(&cond_true_stack, sym);
454 454 delete_all_states_stree_stack_sym(&cond_false_stack, sym);
455 455 delete_all_states_stree_stack_sym(&fake_cur_stree_stack, sym);
456 456 delete_all_states_stree_stack_sym(&break_stack, sym);
457 457 delete_all_states_stree_stack_sym(&fake_break_stack, sym);
458 458 delete_all_states_stree_stack_sym(&switch_stack, sym);
459 459 delete_all_states_stree_stack_sym(&continue_stack, sym);
460 460
461 461 /*
462 462 * deleting from the goto stack is problematic because we don't know
463 463 * if the label is in scope and also we need the value for --two-passes.
464 464 */
465 465 }
466 466
467 467 struct stree *get_all_states_from_stree(int owner, struct stree *source)
468 468 {
469 469 struct stree *ret = NULL;
470 470 struct sm_state *tmp;
471 471
472 472 FOR_EACH_SM(source, tmp) {
473 473 if (tmp->owner == owner)
474 474 avl_insert(&ret, tmp);
475 475 } END_FOR_EACH_SM(tmp);
476 476
477 477 return ret;
478 478 }
479 479
480 480 struct stree *get_all_states_stree(int owner)
481 481 {
482 482 return get_all_states_from_stree(owner, cur_stree);
483 483 }
484 484
485 485 struct stree *__get_cur_stree(void)
486 486 {
487 487 return cur_stree;
488 488 }
489 489
490 490 int is_reachable(void)
491 491 {
492 492 if (cur_stree)
493 493 return 1;
494 494 return 0;
495 495 }
496 496
497 497 void set_true_false_states(int owner, const char *name, struct symbol *sym,
498 498 struct smatch_state *true_state,
499 499 struct smatch_state *false_state)
500 500 {
501 501 if (read_only)
502 502 sm_perror("cur_stree is read only.");
503 503
504 504 if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
505 505 struct smatch_state *tmp;
506 506
507 507 tmp = __get_state(owner, name, sym);
508 508 sm_msg("%s [%s] '%s'. Was %s. Now T:%s F:%s", __func__,
509 509 check_name(owner), name, show_state(tmp),
510 510 show_state(true_state), show_state(false_state));
511 511 }
512 512
513 513 if (unreachable())
514 514 return;
515 515
516 516 if (!cond_false_stack || !cond_true_stack) {
517 517 sm_perror("missing true/false stacks");
518 518 return;
519 519 }
520 520
521 521 if (true_state)
522 522 set_state_stree_stack(&cond_true_stack, owner, name, sym, true_state);
523 523 if (false_state)
524 524 set_state_stree_stack(&cond_false_stack, owner, name, sym, false_state);
525 525 }
526 526
527 527 void set_true_false_states_expr(int owner, struct expression *expr,
528 528 struct smatch_state *true_state,
529 529 struct smatch_state *false_state)
530 530 {
531 531 char *name;
532 532 struct symbol *sym;
533 533
534 534 expr = strip_expr(expr);
535 535 name = expr_to_var_sym(expr, &sym);
536 536 if (!name || !sym)
537 537 goto free;
538 538 set_true_false_states(owner, name, sym, true_state, false_state);
539 539 free:
540 540 free_string(name);
541 541 }
542 542
543 543 void __set_true_false_sm(struct sm_state *true_sm, struct sm_state *false_sm)
544 544 {
545 545 int owner;
546 546 const char *name;
547 547 struct symbol *sym;
548 548
549 549 if (!true_sm && !false_sm)
550 550 return;
551 551
552 552 if (unreachable())
553 553 return;
554 554
555 555 owner = true_sm ? true_sm->owner : false_sm->owner;
556 556 name = true_sm ? true_sm->name : false_sm->name;
557 557 sym = true_sm ? true_sm->sym : false_sm->sym;
558 558 if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
559 559 struct smatch_state *tmp;
560 560
561 561 tmp = __get_state(owner, name, sym);
562 562 sm_msg("%s [%s] '%s'. Was %s. Now T:%s F:%s", __func__,
563 563 check_name(owner), name, show_state(tmp),
564 564 show_state(true_sm ? true_sm->state : NULL),
565 565 show_state(false_sm ? false_sm->state : NULL));
566 566 }
567 567
568 568 if (!cond_false_stack || !cond_true_stack) {
569 569 sm_perror("missing true/false stacks");
570 570 return;
571 571 }
572 572
573 573 if (true_sm)
574 574 overwrite_sm_state_stree_stack(&cond_true_stack, true_sm);
575 575 if (false_sm)
576 576 overwrite_sm_state_stree_stack(&cond_false_stack, false_sm);
577 577 }
578 578
579 579 void nullify_path(void)
580 580 {
581 581 if (fake_cur_stree_stack) {
582 582 __free_fake_cur_stree();
583 583 __push_fake_cur_stree();
584 584 }
585 585 free_stree(&cur_stree);
586 586 }
587 587
588 588 void __match_nullify_path_hook(const char *fn, struct expression *expr,
589 589 void *unused)
590 590 {
591 591 nullify_path();
592 592 }
593 593
594 594 /*
595 595 * At the start of every function we mark the path
596 596 * as unnull. That way there is always at least one state
597 597 * in the cur_stree until nullify_path is called. This
598 598 * is used in merge_slist() for the first null check.
599 599 */
600 600 void __unnullify_path(void)
601 601 {
602 602 if (!cur_stree)
603 603 set_state(-1, "unnull_path", NULL, &true_state);
604 604 }
605 605
606 606 int __path_is_null(void)
607 607 {
608 608 if (cur_stree)
609 609 return 0;
610 610 return 1;
611 611 }
612 612
613 613 static void check_stree_stack_free(struct stree_stack **stack)
614 614 {
615 615 if (*stack) {
616 616 sm_perror("stack not empty");
617 617 free_stack_and_strees(stack);
618 618 }
619 619 }
620 620
621 621 void save_all_states(void)
622 622 {
623 623 __add_ptr_list(&backup, cur_stree);
624 624 cur_stree = NULL;
625 625
626 626 __add_ptr_list(&backup, true_stack);
627 627 true_stack = NULL;
628 628 __add_ptr_list(&backup, false_stack);
629 629 false_stack = NULL;
630 630 __add_ptr_list(&backup, pre_cond_stack);
631 631 pre_cond_stack = NULL;
632 632
633 633 __add_ptr_list(&backup, cond_true_stack);
634 634 cond_true_stack = NULL;
635 635 __add_ptr_list(&backup, cond_false_stack);
636 636 cond_false_stack = NULL;
637 637
638 638 __add_ptr_list(&backup, fake_cur_stree_stack);
639 639 fake_cur_stree_stack = NULL;
640 640
641 641 __add_ptr_list(&backup, break_stack);
642 642 break_stack = NULL;
643 643 __add_ptr_list(&backup, fake_break_stack);
644 644 fake_break_stack = NULL;
645 645
646 646 __add_ptr_list(&backup, switch_stack);
647 647 switch_stack = NULL;
648 648 __add_ptr_list(&backup, remaining_cases);
649 649 remaining_cases = NULL;
650 650 __add_ptr_list(&backup, default_stack);
651 651 default_stack = NULL;
652 652 __add_ptr_list(&backup, continue_stack);
653 653 continue_stack = NULL;
654 654
655 655 __add_ptr_list(&backup, goto_stack);
656 656 goto_stack = NULL;
657 657 }
658 658
659 659 static void *pop_backup(void)
660 660 {
661 661 void *ret;
662 662
663 663 ret = last_ptr_list(backup);
664 664 delete_ptr_list_last(&backup);
665 665 return ret;
666 666 }
667 667
668 668 void restore_all_states(void)
669 669 {
670 670 goto_stack = pop_backup();
671 671
672 672 continue_stack = pop_backup();
673 673 default_stack = pop_backup();
674 674 remaining_cases = pop_backup();
675 675 switch_stack = pop_backup();
676 676 fake_break_stack = pop_backup();
677 677 break_stack = pop_backup();
678 678
679 679 fake_cur_stree_stack = pop_backup();
680 680
681 681 cond_false_stack = pop_backup();
682 682 cond_true_stack = pop_backup();
683 683
684 684 pre_cond_stack = pop_backup();
685 685 false_stack = pop_backup();
686 686 true_stack = pop_backup();
687 687
688 688 cur_stree = pop_backup();
689 689 }
690 690
691 691 void free_goto_stack(void)
692 692 {
693 693 struct named_stree *named_stree;
694 694
695 695 FOR_EACH_PTR(goto_stack, named_stree) {
696 696 free_stree(&named_stree->stree);
697 697 } END_FOR_EACH_PTR(named_stree);
698 698 __free_ptr_list((struct ptr_list **)&goto_stack);
699 699 }
700 700
701 701 void clear_all_states(void)
702 702 {
703 703 nullify_path();
704 704 check_stree_stack_free(&true_stack);
705 705 check_stree_stack_free(&false_stack);
706 706 check_stree_stack_free(&pre_cond_stack);
707 707 check_stree_stack_free(&cond_true_stack);
708 708 check_stree_stack_free(&cond_false_stack);
709 709 check_stree_stack_free(&break_stack);
710 710 check_stree_stack_free(&fake_break_stack);
711 711 check_stree_stack_free(&switch_stack);
712 712 check_stree_stack_free(&continue_stack);
713 713 check_stree_stack_free(&fake_cur_stree_stack);
714 714
715 715 free_goto_stack();
716 716
717 717 free_every_single_sm_state();
718 718 free_tmp_expressions();
719 719 }
720 720
721 721 void __push_cond_stacks(void)
722 722 {
723 723 push_stree(&cond_true_stack, NULL);
724 724 push_stree(&cond_false_stack, NULL);
725 725 __push_fake_cur_stree();
726 726 }
727 727
728 728 void __fold_in_set_states(void)
729 729 {
730 730 struct stree *new_states;
731 731 struct sm_state *sm;
732 732
733 733 new_states = __pop_fake_cur_stree();
734 734 FOR_EACH_SM(new_states, sm) {
735 735 __set_sm(sm);
736 736 __set_true_false_sm(sm, sm);
737 737 } END_FOR_EACH_SM(sm);
738 738 free_stree(&new_states);
739 739 }
740 740
741 741 void __free_set_states(void)
742 742 {
743 743 struct stree *new_states;
744 744
745 745 new_states = __pop_fake_cur_stree();
746 746 free_stree(&new_states);
747 747 }
748 748
749 749 struct stree *__copy_cond_true_states(void)
750 750 {
751 751 struct stree *ret;
752 752
753 753 ret = pop_stree(&cond_true_stack);
754 754 push_stree(&cond_true_stack, clone_stree(ret));
755 755 return ret;
756 756 }
757 757
758 758 struct stree *__copy_cond_false_states(void)
759 759 {
760 760 struct stree *ret;
761 761
762 762 ret = pop_stree(&cond_false_stack);
763 763 push_stree(&cond_false_stack, clone_stree(ret));
764 764 return ret;
765 765 }
766 766
767 767 struct stree *__pop_cond_true_stack(void)
768 768 {
769 769 return pop_stree(&cond_true_stack);
770 770 }
771 771
772 772 struct stree *__pop_cond_false_stack(void)
773 773 {
774 774 return pop_stree(&cond_false_stack);
775 775 }
776 776
777 777 /*
778 778 * This combines the pre cond states with either the true or false states.
779 779 * For example:
780 780 * a = kmalloc() ; if (a !! foo(a)
781 781 * In the pre state a is possibly null. In the true state it is non null.
782 782 * In the false state it is null. Combine the pre and the false to get
783 783 * that when we call 'foo', 'a' is null.
784 784 */
785 785 static void __use_cond_stack(struct stree_stack **stack)
786 786 {
787 787 struct stree *stree;
788 788
789 789 free_stree(&cur_stree);
790 790
791 791 cur_stree = pop_stree(&pre_cond_stack);
792 792 push_stree(&pre_cond_stack, clone_stree(cur_stree));
793 793
794 794 stree = pop_stree(stack);
795 795 overwrite_stree(stree, &cur_stree);
796 796 push_stree(stack, stree);
797 797 }
798 798
799 799 void __use_pre_cond_states(void)
800 800 {
801 801 free_stree(&cur_stree);
802 802 cur_stree = pop_stree(&pre_cond_stack);
803 803 }
804 804
805 805 void __use_cond_true_states(void)
806 806 {
807 807 __use_cond_stack(&cond_true_stack);
808 808 }
809 809
810 810 void __use_cond_false_states(void)
811 811 {
812 812 __use_cond_stack(&cond_false_stack);
813 813 }
814 814
815 815 void __negate_cond_stacks(void)
816 816 {
817 817 struct stree *old_false, *old_true;
818 818
819 819 old_false = pop_stree(&cond_false_stack);
820 820 old_true = pop_stree(&cond_true_stack);
821 821 push_stree(&cond_false_stack, old_true);
822 822 push_stree(&cond_true_stack, old_false);
823 823 }
824 824
825 825 void __and_cond_states(void)
826 826 {
827 827 and_stree_stack(&cond_true_stack);
828 828 or_stree_stack(&pre_cond_stack, cur_stree, &cond_false_stack);
829 829 }
830 830
831 831 void __or_cond_states(void)
832 832 {
833 833 or_stree_stack(&pre_cond_stack, cur_stree, &cond_true_stack);
834 834 and_stree_stack(&cond_false_stack);
835 835 }
836 836
837 837 void __save_pre_cond_states(void)
838 838 {
839 839 push_stree(&pre_cond_stack, clone_stree(cur_stree));
840 840 }
841 841
842 842 void __discard_pre_cond_states(void)
843 843 {
844 844 struct stree *tmp;
845 845
846 846 tmp = pop_stree(&pre_cond_stack);
847 847 free_stree(&tmp);
848 848 }
849 849
850 850 struct stree *__get_true_states(void)
851 851 {
852 852 return clone_stree(top_stree(cond_true_stack));
853 853 }
854 854
855 855 struct stree *__get_false_states(void)
856 856 {
857 857 return clone_stree(top_stree(cond_false_stack));
858 858 }
859 859
860 860 void __use_cond_states(void)
861 861 {
862 862 struct stree *pre, *pre_clone, *true_states, *false_states;
863 863
864 864 pre = pop_stree(&pre_cond_stack);
865 865 pre_clone = clone_stree(pre);
866 866
867 867 true_states = pop_stree(&cond_true_stack);
868 868 overwrite_stree(true_states, &pre);
869 869 free_stree(&true_states);
870 870 /* we use the true states right away */
871 871 free_stree(&cur_stree);
872 872 cur_stree = pre;
873 873
874 874 false_states = pop_stree(&cond_false_stack);
875 875 overwrite_stree(false_states, &pre_clone);
876 876 free_stree(&false_states);
877 877 push_stree(&false_stack, pre_clone);
878 878 }
879 879
880 880 void __push_true_states(void)
881 881 {
882 882 push_stree(&true_stack, clone_stree(cur_stree));
883 883 }
884 884
885 885 void __use_false_states(void)
886 886 {
887 887 free_stree(&cur_stree);
888 888 cur_stree = pop_stree(&false_stack);
889 889 }
890 890
891 891 void __discard_false_states(void)
892 892 {
893 893 struct stree *stree;
894 894
895 895 stree = pop_stree(&false_stack);
896 896 free_stree(&stree);
897 897 }
898 898
899 899 void __merge_false_states(void)
900 900 {
901 901 struct stree *stree;
902 902
903 903 stree = pop_stree(&false_stack);
904 904 merge_stree(&cur_stree, stree);
905 905 free_stree(&stree);
906 906 }
907 907
908 908 /*
909 909 * This function probably seemed common sensical when I wrote it but, oh wow,
910 910 * does it look subtle in retrospect. Say we set a state on one side of the if
911 911 * else path but not on the other, then what we should record in the fake stree
912 912 * is the merged state.
913 913 *
914 914 * This function relies on the fact that the we always set the cur_stree as well
915 915 * and we already have the infrastructure to merge things correctly into the
916 916 * cur_stree.
917 917 *
918 918 * So instead of merging fake strees together which is probably a lot of work,
919 919 * we just use it as a list of set states and look up the actual current values
920 920 * in the cur_stree.
921 921 *
922 922 */
923 923 static void update_stree_with_merged(struct stree **stree)
924 924 {
925 925 struct state_list *slist = NULL;
926 926 struct sm_state *sm, *new;
927 927
928 928 FOR_EACH_SM(*stree, sm) {
929 929 new = get_sm_state(sm->owner, sm->name, sm->sym);
930 930 if (!new) /* This can happen if we go out of scope */
931 931 continue;
932 932 add_ptr_list(&slist, new);
933 933 } END_FOR_EACH_SM(sm);
934 934
935 935 FOR_EACH_PTR(slist, sm) {
936 936 overwrite_sm_state_stree(stree, sm);
937 937 } END_FOR_EACH_PTR(sm);
938 938
939 939 free_slist(&slist);
940 940 }
941 941
942 942 static void update_fake_stree_with_merged(void)
943 943 {
944 944 struct stree *stree;
945 945
946 946 if (!fake_cur_stree_stack)
947 947 return;
948 948 stree = pop_stree(&fake_cur_stree_stack);
949 949 update_stree_with_merged(&stree);
950 950 push_stree(&fake_cur_stree_stack, stree);
951 951 }
952 952
953 953 void __merge_true_states(void)
954 954 {
955 955 struct stree *stree;
956 956
957 957 stree = pop_stree(&true_stack);
958 958 merge_stree(&cur_stree, stree);
959 959 update_fake_stree_with_merged();
960 960 free_stree(&stree);
961 961 }
962 962
963 963 void __push_continues(void)
964 964 {
965 965 push_stree(&continue_stack, NULL);
966 966 }
967 967
968 968 void __discard_continues(void)
969 969 {
970 970 struct stree *stree;
971 971
972 972 stree = pop_stree(&continue_stack);
973 973 free_stree(&stree);
974 974 }
975 975
976 976 void __process_continues(void)
977 977 {
978 978 struct stree *stree;
979 979
980 980 stree = pop_stree(&continue_stack);
981 981 if (!stree)
982 982 stree = clone_stree(cur_stree);
983 983 else
984 984 merge_stree(&stree, cur_stree);
985 985
986 986 push_stree(&continue_stack, stree);
987 987 }
988 988
989 989 void __merge_continues(void)
990 990 {
991 991 struct stree *stree;
992 992
993 993 stree = pop_stree(&continue_stack);
994 994 merge_stree(&cur_stree, stree);
995 995 free_stree(&stree);
996 996 }
997 997
998 998 void __push_breaks(void)
999 999 {
1000 1000 push_stree(&break_stack, NULL);
1001 1001 if (fake_cur_stree_stack)
1002 1002 push_stree(&fake_break_stack, NULL);
1003 1003 }
1004 1004
1005 1005 void __process_breaks(void)
1006 1006 {
1007 1007 struct stree *stree;
1008 1008
1009 1009 stree = pop_stree(&break_stack);
1010 1010 if (!stree)
1011 1011 stree = clone_stree(cur_stree);
1012 1012 else
1013 1013 merge_stree(&stree, cur_stree);
1014 1014 push_stree(&break_stack, stree);
1015 1015
1016 1016 if (!fake_cur_stree_stack)
1017 1017 return;
1018 1018
1019 1019 stree = pop_stree(&fake_break_stack);
1020 1020 if (!stree)
1021 1021 stree = clone_stree(top_stree(fake_cur_stree_stack));
1022 1022 else
1023 1023 merge_stree(&stree, top_stree(fake_cur_stree_stack));
1024 1024 push_stree(&fake_break_stack, stree);
1025 1025 }
1026 1026
1027 1027 int __has_breaks(void)
1028 1028 {
1029 1029 struct stree *stree;
1030 1030 int ret;
1031 1031
1032 1032 stree = pop_stree(&break_stack);
1033 1033 ret = !!stree;
1034 1034 push_stree(&break_stack, stree);
1035 1035 return ret;
1036 1036 }
1037 1037
1038 1038 void __merge_breaks(void)
1039 1039 {
1040 1040 struct stree *stree;
1041 1041 struct sm_state *sm;
1042 1042
1043 1043 stree = pop_stree(&break_stack);
1044 1044 merge_stree(&cur_stree, stree);
1045 1045 free_stree(&stree);
1046 1046
1047 1047 if (!fake_cur_stree_stack)
1048 1048 return;
1049 1049
1050 1050 stree = pop_stree(&fake_break_stack);
1051 1051 update_stree_with_merged(&stree);
1052 1052 FOR_EACH_SM(stree, sm) {
1053 1053 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
1054 1054 } END_FOR_EACH_SM(sm);
1055 1055 free_stree(&stree);
1056 1056 }
1057 1057
1058 1058 void __use_breaks(void)
1059 1059 {
1060 1060 struct stree *stree;
1061 1061 struct sm_state *sm;
1062 1062
1063 1063 free_stree(&cur_stree);
1064 1064 cur_stree = pop_stree(&break_stack);
1065 1065
1066 1066 if (!fake_cur_stree_stack)
1067 1067 return;
1068 1068 stree = pop_stree(&fake_break_stack);
1069 1069 FOR_EACH_SM(stree, sm) {
1070 1070 overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
1071 1071 } END_FOR_EACH_SM(sm);
1072 1072 free_stree(&stree);
1073 1073
1074 1074
1075 1075 }
1076 1076
1077 1077 void __save_switch_states(struct expression *switch_expr)
1078 1078 {
1079 1079 struct range_list *rl;
1080 1080
1081 1081 get_absolute_rl(switch_expr, &rl);
1082 1082
1083 1083 push_rl(&remaining_cases, rl);
1084 1084 push_stree(&switch_stack, clone_stree(cur_stree));
1085 1085 }
1086 1086
1087 1087 int have_remaining_cases(void)
↓ open down ↓ |
1087 lines elided |
↑ open up ↑ |
1088 1088 {
1089 1089 return !!top_rl(remaining_cases);
1090 1090 }
1091 1091
1092 1092 void __merge_switches(struct expression *switch_expr, struct range_list *case_rl)
1093 1093 {
1094 1094 struct stree *stree;
1095 1095 struct stree *implied_stree;
1096 1096
1097 1097 stree = pop_stree(&switch_stack);
1098 + if (!stree) {
1099 + /*
1100 + * If the cur_stree was NULL before the start of the switch
1101 + * statement then we don't want to unnullify it.
1102 + *
1103 + */
1104 + push_stree(&switch_stack, stree);
1105 + return;
1106 + }
1098 1107 implied_stree = __implied_case_stree(switch_expr, case_rl, &remaining_cases, &stree);
1099 1108 merge_stree(&cur_stree, implied_stree);
1100 1109 free_stree(&implied_stree);
1101 1110 push_stree(&switch_stack, stree);
1102 1111 }
1103 1112
1104 1113 void __discard_switches(void)
1105 1114 {
1106 1115 struct stree *stree;
1107 1116
1108 1117 pop_rl(&remaining_cases);
1109 1118 stree = pop_stree(&switch_stack);
1110 1119 free_stree(&stree);
1111 1120 }
1112 1121
1113 1122 void __push_default(void)
1114 1123 {
1115 1124 push_stree(&default_stack, NULL);
1116 1125 }
1117 1126
1118 1127 void __set_default(void)
1119 1128 {
1120 1129 set_state_stree_stack(&default_stack, 0, "has_default", NULL, &true_state);
1121 1130 }
1122 1131
1123 1132 int __pop_default(void)
1124 1133 {
1125 1134 struct stree *stree;
1126 1135
1127 1136 stree = pop_stree(&default_stack);
1128 1137 if (stree) {
1129 1138 free_stree(&stree);
1130 1139 return 1;
1131 1140 }
1132 1141 return 0;
1133 1142 }
1134 1143
1135 1144 static struct named_stree *alloc_named_stree(const char *name, struct symbol *sym, struct stree *stree)
1136 1145 {
1137 1146 struct named_stree *named_stree = __alloc_named_stree(0);
1138 1147
1139 1148 named_stree->name = (char *)name;
1140 1149 named_stree->stree = stree;
1141 1150 named_stree->sym = sym;
1142 1151 return named_stree;
1143 1152 }
1144 1153
1145 1154 void __save_gotos(const char *name, struct symbol *sym)
1146 1155 {
1147 1156 struct stree **stree;
1148 1157 struct stree *clone;
1149 1158
1150 1159 stree = get_named_stree(goto_stack, name, sym);
1151 1160 if (stree) {
1152 1161 merge_stree(stree, cur_stree);
1153 1162 return;
1154 1163 } else {
1155 1164 struct named_stree *named_stree;
1156 1165
1157 1166 clone = clone_stree(cur_stree);
1158 1167 named_stree = alloc_named_stree(name, sym, clone);
1159 1168 add_ptr_list(&goto_stack, named_stree);
1160 1169 }
1161 1170 }
1162 1171
1163 1172 void __merge_gotos(const char *name, struct symbol *sym)
1164 1173 {
1165 1174 struct stree **stree;
1166 1175
1167 1176 stree = get_named_stree(goto_stack, name, sym);
1168 1177 if (stree)
1169 1178 merge_stree(&cur_stree, *stree);
1170 1179 }
↓ open down ↓ |
63 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX