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