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