1/* Classes for modeling the state of memory. 2 Copyright (C) 2019-2020 Free Software Foundation, Inc. 3 Contributed by David Malcolm <dmalcolm@redhat.com>. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it 8under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 3, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, but 13WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21#ifndef GCC_ANALYZER_REGION_MODEL_H 22#define GCC_ANALYZER_REGION_MODEL_H 23 24/* Implementation of the region-based ternary model described in: 25 "A Memory Model for Static Analysis of C Programs" 26 (Zhongxing Xu, Ted Kremenek, and Jian Zhang) 27 http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf */ 28 29/* A tree, extended with stack frame information for locals, so that 30 we can distinguish between different values of locals within a potentially 31 recursive callstack. */ 32// TODO: would this be better as a new tree code? 33 34using namespace ana; 35 36namespace ana { 37 38class path_var 39{ 40public: 41 path_var (tree t, int stack_depth) 42 : m_tree (t), m_stack_depth (stack_depth) 43 { 44 // TODO: ignore stack depth for globals and constants 45 } 46 47 bool operator== (const path_var &other) const 48 { 49 return (m_tree == other.m_tree 50 && m_stack_depth == other.m_stack_depth); 51 } 52 53 void dump (pretty_printer *pp) const; 54 55 tree m_tree; 56 int m_stack_depth; // or -1 for globals? 57}; 58 59} // namespace ana 60 61namespace inchash 62{ 63 extern void add_path_var (path_var pv, hash &hstate); 64} // namespace inchash 65 66 67namespace ana { 68 69/* A region_model is effectively a graph of regions and symbolic values. 70 We store per-model IDs rather than pointers to make it easier to clone 71 and to compare graphs. */ 72 73/* An ID for an svalue within a region_model. Internally, this is an index 74 into a vector of svalue * within the region_model. */ 75 76class svalue_id 77{ 78public: 79 static svalue_id null () { return svalue_id (-1); } 80 81 svalue_id () : m_idx (-1) {} 82 83 bool operator== (const svalue_id &other) const 84 { 85 return m_idx == other.m_idx; 86 } 87 88 bool operator!= (const svalue_id &other) const 89 { 90 return m_idx != other.m_idx; 91 } 92 93 bool null_p () const { return m_idx == -1; } 94 95 static svalue_id from_int (int idx) { return svalue_id (idx); } 96 int as_int () const { return m_idx; } 97 98 void print (pretty_printer *pp) const; 99 void dump_node_name_to_pp (pretty_printer *pp) const; 100 101 void validate (const region_model &model) const; 102 103private: 104 svalue_id (int idx) : m_idx (idx) {} 105 106 int m_idx; 107}; 108 109/* An ID for a region within a region_model. Internally, this is an index 110 into a vector of region * within the region_model. */ 111 112class region_id 113{ 114public: 115 static region_id null () { return region_id (-1); } 116 117 region_id () : m_idx (-1) {} 118 119 bool operator== (const region_id &other) const 120 { 121 return m_idx == other.m_idx; 122 } 123 124 bool operator!= (const region_id &other) const 125 { 126 return m_idx != other.m_idx; 127 } 128 129 bool null_p () const { return m_idx == -1; } 130 131 static region_id from_int (int idx) { return region_id (idx); } 132 int as_int () const { return m_idx; } 133 134 void print (pretty_printer *pp) const; 135 void dump_node_name_to_pp (pretty_printer *pp) const; 136 137 void validate (const region_model &model) const; 138 139private: 140 region_id (int idx) : m_idx (idx) {} 141 142 int m_idx; 143}; 144 145/* A class for renumbering IDs within a region_model, mapping old IDs 146 to new IDs (e.g. when removing one or more elements, thus needing to 147 renumber). */ 148// TODO: could this be useful for equiv_class_ids? 149 150template <typename T> 151class id_map 152{ 153 public: 154 id_map (int num_ids); 155 void put (T src, T dst); 156 T get_dst_for_src (T src) const; 157 T get_src_for_dst (T dst) const; 158 void dump_to_pp (pretty_printer *pp) const; 159 void dump () const; 160 void update (T *) const; 161 162 private: 163 auto_vec<T> m_src_to_dst; 164 auto_vec<T> m_dst_to_src; 165}; 166 167typedef id_map<svalue_id> svalue_id_map; 168typedef id_map<region_id> region_id_map; 169 170/* class id_map. */ 171 172/* id_map's ctor, which populates the map with dummy null values. */ 173 174template <typename T> 175inline id_map<T>::id_map (int num_svalues) 176: m_src_to_dst (num_svalues), 177 m_dst_to_src (num_svalues) 178{ 179 for (int i = 0; i < num_svalues; i++) 180 { 181 m_src_to_dst.quick_push (T::null ()); 182 m_dst_to_src.quick_push (T::null ()); 183 } 184} 185 186/* Record that SRC is to be mapped to DST. */ 187 188template <typename T> 189inline void 190id_map<T>::put (T src, T dst) 191{ 192 m_src_to_dst[src.as_int ()] = dst; 193 m_dst_to_src[dst.as_int ()] = src; 194} 195 196/* Get the new value for SRC within the map. */ 197 198template <typename T> 199inline T 200id_map<T>::get_dst_for_src (T src) const 201{ 202 if (src.null_p ()) 203 return src; 204 return m_src_to_dst[src.as_int ()]; 205} 206 207/* Given DST, a new value, determine which old value will be mapped to it 208 (the inverse of the map). */ 209 210template <typename T> 211inline T 212id_map<T>::get_src_for_dst (T dst) const 213{ 214 if (dst.null_p ()) 215 return dst; 216 return m_dst_to_src[dst.as_int ()]; 217} 218 219/* Dump this id_map to PP. */ 220 221template <typename T> 222inline void 223id_map<T>::dump_to_pp (pretty_printer *pp) const 224{ 225 pp_string (pp, "src to dst: {"); 226 unsigned i; 227 T *dst; 228 FOR_EACH_VEC_ELT (m_src_to_dst, i, dst) 229 { 230 if (i > 0) 231 pp_string (pp, ", "); 232 T src (T::from_int (i)); 233 src.print (pp); 234 pp_string (pp, " -> "); 235 dst->print (pp); 236 } 237 pp_string (pp, "}"); 238 pp_newline (pp); 239 240 pp_string (pp, "dst to src: {"); 241 T *src; 242 FOR_EACH_VEC_ELT (m_dst_to_src, i, src) 243 { 244 if (i > 0) 245 pp_string (pp, ", "); 246 T dst (T::from_int (i)); 247 dst.print (pp); 248 pp_string (pp, " <- "); 249 src->print (pp); 250 } 251 pp_string (pp, "}"); 252 pp_newline (pp); 253} 254 255/* Dump this id_map to stderr. */ 256 257template <typename T> 258DEBUG_FUNCTION inline void 259id_map<T>::dump () const 260{ 261 pretty_printer pp; 262 pp.buffer->stream = stderr; 263 dump_to_pp (&pp); 264 pp_flush (&pp); 265} 266 267/* Update *ID from the old value to its new value in this map. */ 268 269template <typename T> 270inline void 271id_map<T>::update (T *id) const 272{ 273 *id = get_dst_for_src (*id); 274} 275 276/* Variant of the above, which only stores things in one direction. 277 (e.g. for merging, when the number of destination regions is not 278 the same of the src regions, and can grow). */ 279 280template <typename T> 281class one_way_id_map 282{ 283 public: 284 one_way_id_map (int num_ids); 285 void put (T src, T dst); 286 T get_dst_for_src (T src) const; 287 void dump_to_pp (pretty_printer *pp) const; 288 void dump () const; 289 void update (T *) const; 290 291 private: 292 auto_vec<T> m_src_to_dst; 293}; 294 295typedef one_way_id_map<svalue_id> one_way_svalue_id_map; 296typedef one_way_id_map<region_id> one_way_region_id_map; 297 298/* class one_way_id_map. */ 299 300/* one_way_id_map's ctor, which populates the map with dummy null values. */ 301 302template <typename T> 303inline one_way_id_map<T>::one_way_id_map (int num_svalues) 304: m_src_to_dst (num_svalues) 305{ 306 for (int i = 0; i < num_svalues; i++) 307 m_src_to_dst.quick_push (T::null ()); 308} 309 310/* Record that SRC is to be mapped to DST. */ 311 312template <typename T> 313inline void 314one_way_id_map<T>::put (T src, T dst) 315{ 316 m_src_to_dst[src.as_int ()] = dst; 317} 318 319/* Get the new value for SRC within the map. */ 320 321template <typename T> 322inline T 323one_way_id_map<T>::get_dst_for_src (T src) const 324{ 325 if (src.null_p ()) 326 return src; 327 return m_src_to_dst[src.as_int ()]; 328} 329 330/* Dump this map to PP. */ 331 332template <typename T> 333inline void 334one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const 335{ 336 pp_string (pp, "src to dst: {"); 337 unsigned i; 338 T *dst; 339 FOR_EACH_VEC_ELT (m_src_to_dst, i, dst) 340 { 341 if (i > 0) 342 pp_string (pp, ", "); 343 T src (T::from_int (i)); 344 src.print (pp); 345 pp_string (pp, " -> "); 346 dst->print (pp); 347 } 348 pp_string (pp, "}"); 349 pp_newline (pp); 350} 351 352/* Dump this map to stderr. */ 353 354template <typename T> 355DEBUG_FUNCTION inline void 356one_way_id_map<T>::dump () const 357{ 358 pretty_printer pp; 359 pp.buffer->stream = stderr; 360 dump_to_pp (&pp); 361 pp_flush (&pp); 362} 363 364/* Update *ID from the old value to its new value in this map. */ 365 366template <typename T> 367inline void 368one_way_id_map<T>::update (T *id) const 369{ 370 *id = get_dst_for_src (*id); 371} 372 373/* A set of region_ids within a region_model. */ 374 375class region_id_set 376{ 377public: 378 region_id_set (const region_model *model); 379 380 void add_region (region_id rid) 381 { 382 if (!rid.null_p ()) 383 bitmap_set_bit (m_bitmap, rid.as_int ()); 384 } 385 386 bool region_p (region_id rid) const 387 { 388 gcc_assert (!rid.null_p ()); 389 return bitmap_bit_p (const_cast <auto_sbitmap &> (m_bitmap), 390 rid.as_int ()); 391 } 392 393 unsigned int num_regions () 394 { 395 return bitmap_count_bits (m_bitmap); 396 } 397 398private: 399 auto_sbitmap m_bitmap; 400}; 401 402/* A set of svalue_ids within a region_model. */ 403 404class svalue_id_set 405{ 406public: 407 svalue_id_set (); 408 409 void add_svalue (svalue_id sid) 410 { 411 if (!sid.null_p ()) 412 bitmap_set_bit (m_bitmap, sid.as_int ()); 413 } 414 415 bool svalue_p (svalue_id sid) const 416 { 417 gcc_assert (!sid.null_p ()); 418 return bitmap_bit_p (const_cast <auto_bitmap &> (m_bitmap), 419 sid.as_int ()); 420 } 421 422private: 423 auto_bitmap m_bitmap; 424}; 425 426/* Various operations delete information from a region_model. 427 428 This struct tracks how many of each kind of entity were purged (e.g. 429 for selftests, and for debugging). */ 430 431struct purge_stats 432{ 433 purge_stats () 434 : m_num_svalues (0), 435 m_num_regions (0), 436 m_num_equiv_classes (0), 437 m_num_constraints (0), 438 m_num_client_items (0) 439 {} 440 441 int m_num_svalues; 442 int m_num_regions; 443 int m_num_equiv_classes; 444 int m_num_constraints; 445 int m_num_client_items; 446}; 447 448/* An enum for discriminating between the different concrete subclasses 449 of svalue. */ 450 451enum svalue_kind 452{ 453 SK_REGION, 454 SK_CONSTANT, 455 SK_UNKNOWN, 456 SK_POISONED, 457 SK_SETJMP 458}; 459 460/* svalue and its subclasses. 461 462 The class hierarchy looks like this (using indentation to show 463 inheritance, and with svalue_kinds shown for the concrete subclasses): 464 465 svalue 466 region_svalue (SK_REGION) 467 constant_svalue (SK_CONSTANT) 468 unknown_svalue (SK_UNKNOWN) 469 poisoned_svalue (SK_POISONED) 470 setjmp_svalue (SK_SETJMP). */ 471 472/* An abstract base class representing a value held by a region of memory. */ 473 474class svalue 475{ 476public: 477 virtual ~svalue () {} 478 479 bool operator== (const svalue &other) const; 480 bool operator!= (const svalue &other) const { return !(*this == other); } 481 482 virtual svalue *clone () const = 0; 483 484 tree get_type () const { return m_type; } 485 486 virtual enum svalue_kind get_kind () const = 0; 487 488 hashval_t hash () const; 489 490 void print (const region_model &model, 491 svalue_id this_sid, 492 pretty_printer *pp) const; 493 494 virtual void dump_dot_to_pp (const region_model &model, 495 svalue_id this_sid, 496 pretty_printer *pp) const; 497 498 virtual region_svalue *dyn_cast_region_svalue () { return NULL; } 499 virtual constant_svalue *dyn_cast_constant_svalue () { return NULL; } 500 virtual const constant_svalue *dyn_cast_constant_svalue () const 501 { return NULL; } 502 virtual poisoned_svalue *dyn_cast_poisoned_svalue () { return NULL; } 503 virtual unknown_svalue *dyn_cast_unknown_svalue () { return NULL; } 504 virtual setjmp_svalue *dyn_cast_setjmp_svalue () { return NULL; } 505 506 virtual void remap_region_ids (const region_id_map &map); 507 508 virtual void walk_for_canonicalization (canonicalization *c) const; 509 510 virtual svalue_id get_child_sid (region *parent, region *child, 511 region_model &model, 512 region_model_context *ctxt); 513 514 tree maybe_get_constant () const; 515 516 protected: 517 svalue (tree type) : m_type (type) {} 518 519 virtual void add_to_hash (inchash::hash &hstate) const = 0; 520 521 private: 522 virtual void print_details (const region_model &model, 523 svalue_id this_sid, 524 pretty_printer *pp) const = 0; 525 tree m_type; 526}; 527 528/* Concrete subclass of svalue representing a pointer value that points to 529 a known region */ 530 531class region_svalue : public svalue 532{ 533public: 534 region_svalue (tree type, region_id rid) : svalue (type), m_rid (rid) 535 { 536 /* Should we support NULL ptrs here? */ 537 gcc_assert (!rid.null_p ()); 538 } 539 540 bool compare_fields (const region_svalue &other) const; 541 542 svalue *clone () const FINAL OVERRIDE 543 { return new region_svalue (get_type (), m_rid); } 544 545 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_REGION; } 546 547 void dump_dot_to_pp (const region_model &model, 548 svalue_id this_sid, 549 pretty_printer *pp) const 550 FINAL OVERRIDE; 551 552 region_svalue *dyn_cast_region_svalue () FINAL OVERRIDE { return this; } 553 554 region_id get_pointee () const { return m_rid; } 555 556 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE; 557 558 static void merge_values (const region_svalue ®ion_sval_a, 559 const region_svalue ®ion_sval_b, 560 svalue_id *merged_sid, 561 tree type, 562 model_merger *merger); 563 564 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE; 565 566 static tristate eval_condition (region_svalue *lhs_ptr, 567 enum tree_code op, 568 region_svalue *rhs_ptr); 569 570 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE; 571 572 private: 573 void print_details (const region_model &model, 574 svalue_id this_sid, 575 pretty_printer *pp) const 576 FINAL OVERRIDE; 577 578 region_id m_rid; 579}; 580 581} // namespace ana 582 583template <> 584template <> 585inline bool 586is_a_helper <region_svalue *>::test (svalue *sval) 587{ 588 return sval->get_kind () == SK_REGION; 589} 590 591namespace ana { 592 593/* Concrete subclass of svalue representing a specific constant value. */ 594 595class constant_svalue : public svalue 596{ 597public: 598 constant_svalue (tree cst_expr) 599 : svalue (TREE_TYPE (cst_expr)), m_cst_expr (cst_expr) 600 { 601 gcc_assert (cst_expr); 602 gcc_assert (CONSTANT_CLASS_P (cst_expr)); 603 } 604 605 bool compare_fields (const constant_svalue &other) const; 606 607 svalue *clone () const FINAL OVERRIDE 608 { return new constant_svalue (m_cst_expr); } 609 610 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_CONSTANT; } 611 612 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE; 613 614 constant_svalue *dyn_cast_constant_svalue () FINAL OVERRIDE { return this; } 615 const constant_svalue *dyn_cast_constant_svalue () const FINAL OVERRIDE 616 { return this; } 617 618 tree get_constant () const { return m_cst_expr; } 619 620 static void merge_values (const constant_svalue &cst_sval_a, 621 const constant_svalue &cst_sval_b, 622 svalue_id *merged_sid, 623 model_merger *merger); 624 625 static tristate eval_condition (constant_svalue *lhs, 626 enum tree_code op, 627 constant_svalue *rhs); 628 629 svalue_id get_child_sid (region *parent, region *child, 630 region_model &model, 631 region_model_context *ctxt) FINAL OVERRIDE; 632 633 private: 634 void print_details (const region_model &model, 635 svalue_id this_sid, 636 pretty_printer *pp) const 637 FINAL OVERRIDE; 638 639 tree m_cst_expr; 640}; 641 642} // namespace ana 643 644template <> 645template <> 646inline bool 647is_a_helper <constant_svalue *>::test (svalue *sval) 648{ 649 return sval->get_kind () == SK_CONSTANT; 650} 651 652namespace ana { 653 654/* Concrete subclass of svalue representing a unique but unknown value. 655 Comparisons of variables that share the same unknown value are known 656 to be equal, even if we don't know what the value is. */ 657 658class unknown_svalue : public svalue 659{ 660public: 661 unknown_svalue (tree type) 662 : svalue (type) 663 {} 664 665 bool compare_fields (const unknown_svalue &other) const; 666 667 svalue *clone () const FINAL OVERRIDE 668 { return new unknown_svalue (get_type ()); } 669 670 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_UNKNOWN; } 671 672 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE; 673 674 unknown_svalue *dyn_cast_unknown_svalue () FINAL OVERRIDE { return this; } 675 676 private: 677 void print_details (const region_model &model, 678 svalue_id this_sid, 679 pretty_printer *pp) const 680 FINAL OVERRIDE; 681}; 682 683/* An enum describing a particular kind of "poisoned" value. */ 684 685enum poison_kind 686{ 687 /* For use to describe freed memory. */ 688 POISON_KIND_FREED, 689 690 /* For use on pointers to regions within popped stack frames. */ 691 POISON_KIND_POPPED_STACK 692}; 693 694extern const char *poison_kind_to_str (enum poison_kind); 695 696/* Concrete subclass of svalue representing a value that should not 697 be used (e.g. uninitialized memory, freed memory). */ 698 699class poisoned_svalue : public svalue 700{ 701public: 702 poisoned_svalue (enum poison_kind kind, tree type) 703 : svalue (type), m_kind (kind) {} 704 705 bool compare_fields (const poisoned_svalue &other) const; 706 707 svalue *clone () const FINAL OVERRIDE 708 { return new poisoned_svalue (m_kind, get_type ()); } 709 710 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_POISONED; } 711 712 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE; 713 714 poisoned_svalue *dyn_cast_poisoned_svalue () FINAL OVERRIDE { return this; } 715 716 enum poison_kind get_poison_kind () const { return m_kind; } 717 718 private: 719 void print_details (const region_model &model, 720 svalue_id this_sid, 721 pretty_printer *pp) const 722 FINAL OVERRIDE; 723 724 enum poison_kind m_kind; 725}; 726 727} // namespace ana 728 729template <> 730template <> 731inline bool 732is_a_helper <poisoned_svalue *>::test (svalue *sval) 733{ 734 return sval->get_kind () == SK_POISONED; 735} 736 737namespace ana { 738 739/* A bundle of information recording a setjmp/sigsetjmp call, corresponding 740 roughly to a jmp_buf. */ 741 742struct setjmp_record 743{ 744 setjmp_record (const exploded_node *enode, 745 const gcall *setjmp_call) 746 : m_enode (enode), m_setjmp_call (setjmp_call) 747 { 748 } 749 750 bool operator== (const setjmp_record &other) const 751 { 752 return (m_enode == other.m_enode 753 && m_setjmp_call == other.m_setjmp_call); 754 } 755 756 const exploded_node *m_enode; 757 const gcall *m_setjmp_call; 758}; 759 760/* Concrete subclass of svalue representing buffers for setjmp/sigsetjmp, 761 so that longjmp/siglongjmp can potentially "return" to an entirely 762 different function. */ 763 764class setjmp_svalue : public svalue 765{ 766public: 767 setjmp_svalue (const setjmp_record &setjmp_record, 768 tree type) 769 : svalue (type), m_setjmp_record (setjmp_record) 770 {} 771 772 bool compare_fields (const setjmp_svalue &other) const; 773 774 svalue *clone () const FINAL OVERRIDE 775 { return new setjmp_svalue (m_setjmp_record, get_type ()); } 776 777 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_SETJMP; } 778 779 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE; 780 781 setjmp_svalue *dyn_cast_setjmp_svalue () FINAL OVERRIDE { return this; } 782 783 int get_enode_index () const; 784 785 const setjmp_record &get_setjmp_record () const { return m_setjmp_record; } 786 787 private: 788 void print_details (const region_model &model, 789 svalue_id this_sid, 790 pretty_printer *pp) const 791 FINAL OVERRIDE; 792 793 setjmp_record m_setjmp_record; 794}; 795 796/* An enum for discriminating between the different concrete subclasses 797 of region. */ 798 799enum region_kind 800{ 801 RK_PRIMITIVE, 802 RK_STRUCT, 803 RK_UNION, 804 RK_FRAME, 805 RK_GLOBALS, 806 RK_CODE, 807 RK_FUNCTION, 808 RK_ARRAY, 809 RK_STACK, 810 RK_HEAP, 811 RK_ROOT, 812 RK_SYMBOLIC 813}; 814 815extern const char *region_kind_to_str (enum region_kind); 816 817/* Region and its subclasses. 818 819 The class hierarchy looks like this (using indentation to show 820 inheritance, and with region_kinds shown for the concrete subclasses): 821 822 region 823 primitive_region (RK_PRIMITIVE) 824 map_region 825 struct_or_union_region 826 struct_region (RK_STRUCT) 827 union_region (RK_UNION) 828 scope_region 829 frame_region (RK_FRAME) 830 globals_region (RK_GLOBALS) 831 code_region (RK_CODE) 832 function_region (RK_FUNCTION) 833 array_region (RK_ARRAY) 834 stack_region (RK_STACK) 835 heap_region (RK_HEAP) 836 root_region (RK_ROOT) 837 label_region (RK_FUNCTION) 838 symbolic_region (RK_SYMBOLIC). */ 839 840/* Abstract base class representing a chunk of memory. 841 842 Regions form a tree-like hierarchy, with a root region at the base, 843 with memory space regions within it, representing the stack and 844 globals, with frames within the stack, and regions for variables 845 within the frames and the "globals" region. Regions for structs 846 can have subregions for fields. 847 848 A region can optionally have a value, or inherit its value from 849 the first ancestor with a value. For example, the stack region 850 has a "uninitialized" poison value which is inherited by all 851 descendent regions that don't themselves have a value. */ 852 853class region 854{ 855public: 856 virtual ~region () {} 857 858 bool operator== (const region &other) const; 859 bool operator!= (const region &other) const { return !(*this == other); } 860 861 virtual region *clone () const = 0; 862 863 virtual enum region_kind get_kind () const = 0; 864 virtual map_region *dyn_cast_map_region () { return NULL; } 865 virtual array_region *dyn_cast_array_region () { return NULL; } 866 virtual symbolic_region *dyn_cast_symbolic_region () { return NULL; } 867 virtual const symbolic_region *dyn_cast_symbolic_region () const { return NULL; } 868 869 region_id get_parent () const { return m_parent_rid; } 870 region *get_parent_region (const region_model &model) const; 871 872 void set_value (region_model &model, region_id this_rid, svalue_id rhs_sid, 873 region_model_context *ctxt); 874 svalue_id get_value (region_model &model, bool non_null, 875 region_model_context *ctxt); 876 svalue_id get_value_direct () const { return m_sval_id; } 877 878 svalue_id get_inherited_child_sid (region *child, 879 region_model &model, 880 region_model_context *ctxt); 881 882 tree get_type () const { return m_type; } 883 884 hashval_t hash () const; 885 886 void print (const region_model &model, 887 region_id this_rid, 888 pretty_printer *pp) const; 889 890 virtual void dump_dot_to_pp (const region_model &model, 891 region_id this_rid, 892 pretty_printer *pp) const; 893 894 void dump_to_pp (const region_model &model, 895 region_id this_rid, 896 pretty_printer *pp, 897 const char *prefix, 898 bool is_last_child) const; 899 virtual void dump_child_label (const region_model &model, 900 region_id this_rid, 901 region_id child_rid, 902 pretty_printer *pp) const; 903 904 void remap_svalue_ids (const svalue_id_map &map); 905 virtual void remap_region_ids (const region_id_map &map); 906 907 virtual void walk_for_canonicalization (canonicalization *c) const = 0; 908 909 void add_view (region_id view_rid, region_model *model); 910 region_id get_view (tree type, region_model *model) const; 911 region_id get_active_view () const { return m_active_view_rid; } 912 bool is_view_p () const { return m_is_view; } 913 914 virtual void validate (const region_model &model) const; 915 916 bool non_null_p (const region_model &model) const; 917 918 protected: 919 region (region_id parent_rid, svalue_id sval_id, tree type); 920 region (const region &other); 921 922 virtual void add_to_hash (inchash::hash &hstate) const; 923 virtual void print_fields (const region_model &model, 924 region_id this_rid, 925 pretty_printer *pp) const; 926 927 private: 928 void become_active_view (region_model &model, region_id this_rid); 929 void deactivate_any_active_view (region_model &model); 930 void deactivate_view (region_model &model, region_id this_view_rid); 931 932 region_id m_parent_rid; 933 svalue_id m_sval_id; 934 tree m_type; 935 /* Child regions that are "views" (one per type). */ 936 auto_vec<region_id> m_view_rids; 937 938 bool m_is_view; 939 region_id m_active_view_rid; 940}; 941 942} // namespace ana 943 944template <> 945template <> 946inline bool 947is_a_helper <region *>::test (region *) 948{ 949 return true; 950} 951 952namespace ana { 953 954/* Concrete region subclass for storing "primitive" types (integral types, 955 pointers, etc). */ 956 957class primitive_region : public region 958{ 959public: 960 primitive_region (region_id parent_rid, tree type) 961 : region (parent_rid, svalue_id::null (), type) 962 {} 963 964 region *clone () const FINAL OVERRIDE; 965 966 enum region_kind get_kind () const FINAL OVERRIDE { return RK_PRIMITIVE; } 967 968 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE; 969}; 970 971/* A region that has children identified by tree keys. 972 For example a stack frame has subregions per local, and a region 973 for a struct has subregions per field. */ 974 975class map_region : public region 976{ 977public: 978 typedef ordered_hash_map<tree, region_id> map_t; 979 typedef map_t::iterator iterator_t; 980 981 map_region (region_id parent_rid, tree type) 982 : region (parent_rid, svalue_id::null (), type) 983 {} 984 map_region (const map_region &other); 985 986 map_region *dyn_cast_map_region () FINAL OVERRIDE { return this; } 987 988 void dump_dot_to_pp (const region_model &model, 989 region_id this_rid, 990 pretty_printer *pp) const 991 FINAL OVERRIDE; 992 993 void dump_child_label (const region_model &model, 994 region_id this_rid, 995 region_id child_rid, 996 pretty_printer *pp) const 997 FINAL OVERRIDE; 998 999 region_id get_or_create (region_model *model, 1000 region_id this_rid, 1001 tree expr, tree type, 1002 region_model_context *ctxt); 1003 void unbind (tree expr); 1004 region_id *get (tree expr); 1005 1006 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE; 1007 1008 tree get_tree_for_child_region (region_id child_rid) const; 1009 1010 tree get_tree_for_child_region (region *child, 1011 const region_model &model) const; 1012 1013 static bool can_merge_p (const map_region *map_region_a, 1014 const map_region *map_region_b, 1015 map_region *merged_map_region, 1016 region_id merged_rid, 1017 model_merger *merger); 1018 1019 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE; 1020 1021 virtual bool valid_key_p (tree key) const = 0; 1022 1023 svalue_id get_value_by_name (tree identifier, 1024 const region_model &model) const; 1025 1026 iterator_t begin () { return m_map.begin (); } 1027 iterator_t end () { return m_map.end (); } 1028 size_t elements () const { return m_map.elements (); } 1029 1030 protected: 1031 bool compare_fields (const map_region &other) const; 1032 void add_to_hash (inchash::hash &hstate) const OVERRIDE; 1033 void print_fields (const region_model &model, 1034 region_id this_rid, 1035 pretty_printer *pp) const 1036 OVERRIDE; 1037 void validate (const region_model &model) const FINAL OVERRIDE; 1038 1039 private: 1040 /* Mapping from tree to child region. */ 1041 map_t m_map; 1042}; 1043 1044} // namespace ana 1045 1046template <> 1047template <> 1048inline bool 1049is_a_helper <map_region *>::test (region *reg) 1050{ 1051 return (reg->dyn_cast_map_region () != NULL); 1052} 1053 1054namespace ana { 1055 1056/* Abstract subclass representing a region with fields 1057 (either a struct or a union). */ 1058 1059class struct_or_union_region : public map_region 1060{ 1061public: 1062 bool valid_key_p (tree key) const FINAL OVERRIDE; 1063 1064 protected: 1065 struct_or_union_region (region_id parent_rid, tree type) 1066 : map_region (parent_rid, type) 1067 {} 1068 1069 bool compare_fields (const struct_or_union_region &other) const; 1070}; 1071 1072} // namespace ana 1073 1074template <> 1075template <> 1076inline bool 1077is_a_helper <struct_or_union_region *>::test (region *reg) 1078{ 1079 return (reg->get_kind () == RK_STRUCT 1080 || reg->get_kind () == RK_UNION); 1081} 1082 1083namespace ana { 1084 1085/* Concrete region subclass. A map_region representing a struct, using 1086 FIELD_DECLs for its keys. */ 1087 1088class struct_region : public struct_or_union_region 1089{ 1090public: 1091 struct_region (region_id parent_rid, tree type) 1092 : struct_or_union_region (parent_rid, type) 1093 { 1094 gcc_assert (TREE_CODE (type) == RECORD_TYPE); 1095 } 1096 1097 region *clone () const FINAL OVERRIDE; 1098 1099 enum region_kind get_kind () const FINAL OVERRIDE { return RK_STRUCT; } 1100 1101 bool compare_fields (const struct_region &other) const; 1102}; 1103 1104} // namespace ana 1105 1106template <> 1107template <> 1108inline bool 1109is_a_helper <struct_region *>::test (region *reg) 1110{ 1111 return reg->get_kind () == RK_STRUCT; 1112} 1113 1114namespace ana { 1115 1116/* Concrete region subclass. A map_region representing a union, using 1117 FIELD_DECLs for its keys. */ 1118 1119class union_region : public struct_or_union_region 1120{ 1121public: 1122 union_region (region_id parent_rid, tree type) 1123 : struct_or_union_region (parent_rid, type) 1124 { 1125 gcc_assert (TREE_CODE (type) == UNION_TYPE); 1126 } 1127 1128 region *clone () const FINAL OVERRIDE; 1129 1130 enum region_kind get_kind () const FINAL OVERRIDE { return RK_UNION; } 1131 1132 bool compare_fields (const union_region &other) const; 1133}; 1134 1135} // namespace ana 1136 1137template <> 1138template <> 1139inline bool 1140is_a_helper <union_region *>::test (region *reg) 1141{ 1142 return reg->get_kind () == RK_UNION; 1143} 1144 1145namespace ana { 1146 1147/* Abstract map_region subclass for accessing decls, used as a base class 1148 for function frames and for the globals region. */ 1149 1150class scope_region : public map_region 1151{ 1152 public: 1153 1154 protected: 1155 scope_region (region_id parent_rid) 1156 : map_region (parent_rid, NULL_TREE) 1157 {} 1158 1159 scope_region (const scope_region &other) 1160 : map_region (other) 1161 { 1162 } 1163 1164 bool compare_fields (const scope_region &other) const; 1165}; 1166 1167/* Concrete region subclass, representing a function frame on the stack, 1168 to contain the locals. */ 1169 1170class frame_region : public scope_region 1171{ 1172public: 1173 frame_region (region_id parent_rid, function *fun, int depth) 1174 : scope_region (parent_rid), m_fun (fun), m_depth (depth) 1175 {} 1176 1177 frame_region (const frame_region &other) 1178 : scope_region (other), m_fun (other.m_fun), m_depth (other.m_depth) 1179 { 1180 } 1181 1182 /* region vfuncs. */ 1183 region *clone () const FINAL OVERRIDE; 1184 enum region_kind get_kind () const FINAL OVERRIDE { return RK_FRAME; } 1185 void print_fields (const region_model &model, 1186 region_id this_rid, 1187 pretty_printer *pp) const 1188 FINAL OVERRIDE; 1189 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE; 1190 1191 /* map_region vfuncs. */ 1192 bool valid_key_p (tree key) const FINAL OVERRIDE; 1193 1194 /* Accessors. */ 1195 function *get_function () const { return m_fun; } 1196 int get_depth () const { return m_depth; } 1197 1198 bool compare_fields (const frame_region &other) const; 1199 1200 private: 1201 function *m_fun; 1202 int m_depth; 1203}; 1204 1205} // namespace ana 1206 1207template <> 1208template <> 1209inline bool 1210is_a_helper <frame_region *>::test (region *reg) 1211{ 1212 return reg->get_kind () == RK_FRAME; 1213} 1214 1215namespace ana { 1216 1217/* Concrete region subclass, to hold global variables (data and bss). */ 1218 1219class globals_region : public scope_region 1220{ 1221 public: 1222 globals_region (region_id parent_rid) 1223 : scope_region (parent_rid) 1224 {} 1225 1226 globals_region (const globals_region &other) 1227 : scope_region (other) 1228 { 1229 } 1230 1231 /* region vfuncs. */ 1232 region *clone () const FINAL OVERRIDE; 1233 enum region_kind get_kind () const FINAL OVERRIDE { return RK_GLOBALS; } 1234 1235 /* map_region vfuncs. */ 1236 bool valid_key_p (tree key) const FINAL OVERRIDE; 1237 1238 bool compare_fields (const globals_region &other) const; 1239}; 1240 1241} // namespace ana 1242 1243template <> 1244template <> 1245inline bool 1246is_a_helper <globals_region *>::test (region *reg) 1247{ 1248 return reg->get_kind () == RK_GLOBALS; 1249} 1250 1251namespace ana { 1252 1253/* Concrete region subclass. A map_region representing the code, using 1254 FUNCTION_DECLs for its keys. */ 1255 1256class code_region : public map_region 1257{ 1258public: 1259 code_region (region_id parent_rid) 1260 : map_region (parent_rid, NULL_TREE) 1261 {} 1262 code_region (const code_region &other) 1263 : map_region (other) 1264 {} 1265 1266 /* region vfuncs. */ 1267 region *clone () const FINAL OVERRIDE; 1268 enum region_kind get_kind () const FINAL OVERRIDE { return RK_CODE; } 1269 1270 /* map_region vfunc. */ 1271 bool valid_key_p (tree key) const FINAL OVERRIDE; 1272 1273 region_id get_element (region_model *model, 1274 region_id this_rid, 1275 svalue_id index_sid, 1276 region_model_context *ctxt); 1277 1278 bool compare_fields (const code_region &other) const; 1279}; 1280 1281} // namespace ana 1282 1283template <> 1284template <> 1285inline bool 1286is_a_helper <code_region *>::test (region *reg) 1287{ 1288 return reg->get_kind () == RK_CODE; 1289} 1290 1291namespace ana { 1292 1293/* Concrete region subclass. A map_region representing the code for 1294 a particular function, using LABEL_DECLs for its keys. */ 1295 1296class function_region : public map_region 1297{ 1298public: 1299 function_region (region_id parent_rid, tree type) 1300 : map_region (parent_rid, type) 1301 { 1302 gcc_assert (FUNC_OR_METHOD_TYPE_P (type)); 1303 } 1304 function_region (const function_region &other) 1305 : map_region (other) 1306 {} 1307 1308 /* region vfuncs. */ 1309 region *clone () const FINAL OVERRIDE; 1310 enum region_kind get_kind () const FINAL OVERRIDE { return RK_FUNCTION; } 1311 1312 /* map_region vfunc. */ 1313 bool valid_key_p (tree key) const FINAL OVERRIDE; 1314 1315 region_id get_element (region_model *model, 1316 region_id this_rid, 1317 svalue_id index_sid, 1318 region_model_context *ctxt); 1319 1320 bool compare_fields (const function_region &other) const; 1321}; 1322 1323} // namespace ana 1324 1325template <> 1326template <> 1327inline bool 1328is_a_helper <function_region *>::test (region *reg) 1329{ 1330 return reg->get_kind () == RK_FUNCTION; 1331} 1332 1333namespace ana { 1334 1335/* Concrete region subclass representing an array (or an array-like view 1336 of a parent region of memory. 1337 This can't be a map_region as we can't use trees as the keys: there's 1338 no guarantee about the uniqueness of an INTEGER_CST. */ 1339 1340class array_region : public region 1341{ 1342public: 1343#if 0 1344 wide_int m_test; 1345 1346 typedef wide_int key_t; 1347 typedef int_hash <wide_int, -1, -2> hash_t; 1348 typedef ordered_hash_map<hash_t, region_id> map_t; 1349#else 1350 typedef int key_t; 1351 typedef int_hash <int, -1, -2> int_hash_t; 1352 typedef ordered_hash_map<int_hash_t, region_id> map_t; 1353#endif 1354 typedef map_t::iterator iterator_t; 1355 1356 array_region (region_id parent_rid, tree type) 1357 : region (parent_rid, svalue_id::null (), type) 1358 { 1359 gcc_assert (TREE_CODE (type) == ARRAY_TYPE); 1360 } 1361 array_region (const array_region &other); 1362 1363 void dump_dot_to_pp (const region_model &model, 1364 region_id this_rid, 1365 pretty_printer *pp) const 1366 FINAL OVERRIDE; 1367 1368 void dump_child_label (const region_model &model, 1369 region_id this_rid, 1370 region_id child_rid, 1371 pretty_printer *pp) const 1372 FINAL OVERRIDE; 1373 1374 /* region vfuncs. */ 1375 region *clone () const FINAL OVERRIDE; 1376 enum region_kind get_kind () const FINAL OVERRIDE { return RK_ARRAY; } 1377 array_region *dyn_cast_array_region () { return this; } 1378 1379 region_id get_element (region_model *model, 1380 region_id this_rid, 1381 svalue_id index_sid, 1382 region_model_context *ctxt); 1383 1384 bool compare_fields (const array_region &other) const; 1385 1386 static bool can_merge_p (const array_region *array_region_a, 1387 const array_region *array_region_b, 1388 array_region *merged_array_region, 1389 region_id merged_rid, 1390 model_merger *merger); 1391 1392 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE; 1393 1394 iterator_t begin () { return m_map.begin (); } 1395 iterator_t end () { return m_map.end (); } 1396 size_t elements () const { return m_map.elements (); } 1397 1398 region_id get_or_create (region_model *model, 1399 region_id this_rid, 1400 key_t key, tree type, 1401 region_model_context *ctxt); 1402// void unbind (int expr); 1403 region_id *get (key_t key); 1404 1405 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE; 1406 1407 bool get_key_for_child_region (region_id child_rid, 1408 key_t *out) const; 1409 1410#if 0 1411 bool get_key_for_child_region (region *child, 1412 const region_model &model, 1413 key_t *out) const; 1414#endif 1415 1416 void add_to_hash (inchash::hash &hstate) const OVERRIDE; 1417 void print_fields (const region_model &model, 1418 region_id this_rid, 1419 pretty_printer *pp) const 1420 OVERRIDE; 1421 void validate (const region_model &model) const FINAL OVERRIDE; 1422 1423 static key_t key_from_constant (tree cst); 1424 tree constant_from_key (key_t key); 1425 1426 private: 1427 static int key_cmp (const void *, const void *); 1428 1429 /* Mapping from tree to child region. */ 1430 map_t m_map; 1431}; 1432 1433} // namespace ana 1434 1435template <> 1436template <> 1437inline bool 1438is_a_helper <array_region *>::test (region *reg) 1439{ 1440 return reg->get_kind () == RK_ARRAY; 1441} 1442 1443namespace ana { 1444 1445/* Concrete region subclass representing a stack, containing all stack 1446 frames, and implicitly providing a POISON_KIND_UNINIT value to all 1447 child regions by default. */ 1448 1449class stack_region : public region 1450{ 1451public: 1452 stack_region (region_id parent_rid, svalue_id sval_id) 1453 : region (parent_rid, sval_id, NULL_TREE) 1454 {} 1455 1456 stack_region (const stack_region &other); 1457 1458 bool compare_fields (const stack_region &other) const; 1459 1460 region *clone () const FINAL OVERRIDE; 1461 1462 enum region_kind get_kind () const FINAL OVERRIDE { return RK_STACK; } 1463 1464 void dump_child_label (const region_model &model, 1465 region_id this_rid, 1466 region_id child_rid, 1467 pretty_printer *pp) const 1468 FINAL OVERRIDE; 1469 1470 void push_frame (region_id frame_rid); 1471 region_id get_current_frame_id () const; 1472 void pop_frame (region_model *model, region_id result_dst_rid, 1473 bool purge, purge_stats *stats, 1474 region_model_context *ctxt); 1475 1476 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE; 1477 1478 unsigned get_num_frames () const { return m_frame_rids.length (); } 1479 region_id get_frame_rid (unsigned i) const { return m_frame_rids[i]; } 1480 1481 static bool can_merge_p (const stack_region *stack_region_a, 1482 const stack_region *stack_region_b, 1483 model_merger *merger); 1484 1485 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE; 1486 1487 svalue_id get_value_by_name (tree identifier, 1488 const region_model &model) const; 1489 1490 void validate (const region_model &model) const FINAL OVERRIDE; 1491 1492 private: 1493 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE; 1494 void print_fields (const region_model &model, 1495 region_id this_rid, 1496 pretty_printer *pp) const 1497 FINAL OVERRIDE; 1498 1499 auto_vec<region_id> m_frame_rids; 1500}; 1501 1502} // namespace ana 1503 1504template <> 1505template <> 1506inline bool 1507is_a_helper <stack_region *>::test (region *reg) 1508{ 1509 return reg->get_kind () == RK_STACK; 1510} 1511 1512namespace ana { 1513 1514/* Concrete region subclass: a region within which regions can be 1515 dynamically allocated. */ 1516 1517class heap_region : public region 1518{ 1519public: 1520 heap_region (region_id parent_rid, svalue_id sval_id) 1521 : region (parent_rid, sval_id, NULL_TREE) 1522 {} 1523 heap_region (const heap_region &other); 1524 1525 bool compare_fields (const heap_region &other) const; 1526 1527 region *clone () const FINAL OVERRIDE; 1528 1529 enum region_kind get_kind () const FINAL OVERRIDE { return RK_HEAP; } 1530 1531 static bool can_merge_p (const heap_region *heap_a, region_id heap_a_rid, 1532 const heap_region *heap_b, region_id heap_b_rid, 1533 heap_region *merged_heap, region_id merged_heap_rid, 1534 model_merger *merger); 1535 1536 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE; 1537 1538}; 1539 1540} // namespace ana 1541 1542template <> 1543template <> 1544inline bool 1545is_a_helper <heap_region *>::test (region *reg) 1546{ 1547 return reg->get_kind () == RK_HEAP; 1548} 1549 1550namespace ana { 1551 1552/* Concrete region subclass. The root region, containing all regions 1553 (either directly, or as descendents). 1554 Unique within a region_model. */ 1555 1556class root_region : public region 1557{ 1558public: 1559 root_region (); 1560 root_region (const root_region &other); 1561 1562 bool compare_fields (const root_region &other) const; 1563 1564 region *clone () const FINAL OVERRIDE; 1565 1566 enum region_kind get_kind () const FINAL OVERRIDE { return RK_ROOT; } 1567 1568 void dump_child_label (const region_model &model, 1569 region_id this_rid, 1570 region_id child_rid, 1571 pretty_printer *pp) const 1572 FINAL OVERRIDE; 1573 1574 region_id push_frame (region_model *model, function *fun, 1575 vec<svalue_id> *arg_sids, 1576 region_model_context *ctxt); 1577 region_id get_current_frame_id (const region_model &model) const; 1578 void pop_frame (region_model *model, region_id result_dst_rid, 1579 bool purge, purge_stats *stats, 1580 region_model_context *ctxt); 1581 1582 region_id ensure_stack_region (region_model *model); 1583 region_id get_stack_region_id () const { return m_stack_rid; } 1584 stack_region *get_stack_region (const region_model *model) const; 1585 1586 region_id ensure_globals_region (region_model *model); 1587 region_id get_globals_region_id () const { return m_globals_rid; } 1588 globals_region *get_globals_region (const region_model *model) const; 1589 1590 region_id ensure_code_region (region_model *model); 1591 code_region *get_code_region (const region_model *model) const; 1592 1593 region_id ensure_heap_region (region_model *model); 1594 heap_region *get_heap_region (const region_model *model) const; 1595 1596 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE; 1597 1598 static bool can_merge_p (const root_region *root_region_a, 1599 const root_region *root_region_b, 1600 root_region *merged_root_region, 1601 model_merger *merger); 1602 1603 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE; 1604 1605 svalue_id get_value_by_name (tree identifier, 1606 const region_model &model) const; 1607 1608 void validate (const region_model &model) const FINAL OVERRIDE; 1609 1610private: 1611 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE; 1612 void print_fields (const region_model &model, 1613 region_id this_rid, 1614 pretty_printer *pp) const 1615 FINAL OVERRIDE; 1616 1617 region_id m_stack_rid; 1618 region_id m_globals_rid; 1619 region_id m_code_rid; 1620 region_id m_heap_rid; 1621}; 1622 1623} // namespace ana 1624 1625template <> 1626template <> 1627inline bool 1628is_a_helper <root_region *>::test (region *reg) 1629{ 1630 return reg->get_kind () == RK_ROOT; 1631} 1632 1633namespace ana { 1634 1635/* Concrete region subclass: a region to use when dereferencing an unknown 1636 pointer. */ 1637 1638class symbolic_region : public region 1639{ 1640public: 1641 symbolic_region (region_id parent_rid, tree type, bool possibly_null) 1642 : region (parent_rid, svalue_id::null (), type), 1643 m_possibly_null (possibly_null) 1644 {} 1645 symbolic_region (const symbolic_region &other); 1646 1647 const symbolic_region *dyn_cast_symbolic_region () const FINAL OVERRIDE 1648 { return this; } 1649 symbolic_region *dyn_cast_symbolic_region () FINAL OVERRIDE 1650 { return this; } 1651 1652 bool compare_fields (const symbolic_region &other) const; 1653 1654 region *clone () const FINAL OVERRIDE; 1655 1656 enum region_kind get_kind () const FINAL OVERRIDE { return RK_SYMBOLIC; } 1657 1658 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE; 1659 1660 void print_fields (const region_model &model, 1661 region_id this_rid, 1662 pretty_printer *pp) const FINAL OVERRIDE; 1663 1664 bool m_possibly_null; 1665}; 1666 1667/* A region_model encapsulates a representation of the state of memory, with 1668 a tree of regions, along with their associated values. 1669 The representation is graph-like because values can be pointers to 1670 regions. 1671 It also stores a constraint_manager, capturing relationships between 1672 the values. */ 1673 1674class region_model 1675{ 1676 public: 1677 region_model (); 1678 region_model (const region_model &other); 1679 ~region_model (); 1680 1681#if 0//__cplusplus >= 201103 1682 region_model (region_model &&other); 1683#endif 1684 1685 region_model &operator= (const region_model &other); 1686 1687 bool operator== (const region_model &other) const; 1688 bool operator!= (const region_model &other) const 1689 { 1690 return !(*this == other); 1691 } 1692 1693 hashval_t hash () const; 1694 1695 void print (pretty_printer *pp) const; 1696 1697 void print_svalue (svalue_id sid, pretty_printer *pp) const; 1698 1699 void dump_dot_to_pp (pretty_printer *pp) const; 1700 void dump_dot_to_file (FILE *fp) const; 1701 void dump_dot (const char *path) const; 1702 1703 void dump_to_pp (pretty_printer *pp, bool summarize) const; 1704 void dump (FILE *fp, bool summarize) const; 1705 void dump (bool summarize) const; 1706 1707 void debug () const; 1708 1709 void validate () const; 1710 1711 void canonicalize (region_model_context *ctxt); 1712 bool canonicalized_p () const; 1713 1714 void check_for_poison (tree expr, region_model_context *ctxt); 1715 void on_assignment (const gassign *stmt, region_model_context *ctxt); 1716 bool on_call_pre (const gcall *stmt, region_model_context *ctxt); 1717 void on_call_post (const gcall *stmt, 1718 bool unknown_side_effects, 1719 region_model_context *ctxt); 1720 void handle_unrecognized_call (const gcall *call, 1721 region_model_context *ctxt); 1722 void on_return (const greturn *stmt, region_model_context *ctxt); 1723 void on_setjmp (const gcall *stmt, const exploded_node *enode, 1724 region_model_context *ctxt); 1725 void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call, 1726 int setjmp_stack_depth, region_model_context *ctxt); 1727 1728 void update_for_phis (const supernode *snode, 1729 const cfg_superedge *last_cfg_superedge, 1730 region_model_context *ctxt); 1731 1732 void handle_phi (const gphi *phi, 1733 tree lhs, tree rhs, bool is_back_edge, 1734 region_model_context *ctxt); 1735 1736 bool maybe_update_for_edge (const superedge &edge, 1737 const gimple *last_stmt, 1738 region_model_context *ctxt); 1739 1740 region_id get_root_rid () const { return m_root_rid; } 1741 root_region *get_root_region () const; 1742 1743 region_id get_stack_region_id () const; 1744 region_id push_frame (function *fun, vec<svalue_id> *arg_sids, 1745 region_model_context *ctxt); 1746 region_id get_current_frame_id () const; 1747 function * get_current_function () const; 1748 void pop_frame (region_id result_dst_rid, 1749 bool purge, purge_stats *stats, 1750 region_model_context *ctxt); 1751 int get_stack_depth () const; 1752 function *get_function_at_depth (unsigned depth) const; 1753 1754 region_id get_globals_region_id () const; 1755 1756 svalue_id add_svalue (svalue *sval); 1757 void replace_svalue (svalue_id sid, svalue *new_sval); 1758 1759 region_id add_region (region *r); 1760 1761 region_id add_region_for_type (region_id parent_rid, tree type, 1762 region_model_context *ctxt); 1763 1764 svalue *get_svalue (svalue_id sval_id) const; 1765 region *get_region (region_id rid) const; 1766 1767 template <typename Subclass> 1768 Subclass *get_region (region_id rid) const 1769 { 1770 region *result = get_region (rid); 1771 if (result) 1772 gcc_assert (is_a<Subclass *> (result)); 1773 return (Subclass *)result; 1774 } 1775 1776 region_id get_lvalue (path_var pv, region_model_context *ctxt); 1777 region_id get_lvalue (tree expr, region_model_context *ctxt); 1778 svalue_id get_rvalue (path_var pv, region_model_context *ctxt); 1779 svalue_id get_rvalue (tree expr, region_model_context *ctxt); 1780 1781 svalue_id get_or_create_ptr_svalue (tree ptr_type, region_id id); 1782 svalue_id get_or_create_constant_svalue (tree cst_expr); 1783 svalue_id get_svalue_for_fndecl (tree ptr_type, tree fndecl, 1784 region_model_context *ctxt); 1785 svalue_id get_svalue_for_label (tree ptr_type, tree label, 1786 region_model_context *ctxt); 1787 1788 region_id get_region_for_fndecl (tree fndecl, region_model_context *ctxt); 1789 region_id get_region_for_label (tree label, region_model_context *ctxt); 1790 1791 svalue_id maybe_cast (tree type, svalue_id sid, region_model_context *ctxt); 1792 svalue_id maybe_cast_1 (tree type, svalue_id sid); 1793 1794 region_id get_field_region (region_id rid, tree field, 1795 region_model_context *ctxt); 1796 1797 region_id deref_rvalue (svalue_id ptr_sid, region_model_context *ctxt); 1798 region_id deref_rvalue (tree ptr, region_model_context *ctxt); 1799 1800 void set_value (region_id lhs_rid, svalue_id rhs_sid, 1801 region_model_context *ctxt); 1802 void set_value (tree lhs, tree rhs, region_model_context *ctxt); 1803 svalue_id set_to_new_unknown_value (region_id dst_rid, tree type, 1804 region_model_context *ctxt); 1805 1806 void copy_region (region_id dst_rid, region_id src_rid, 1807 region_model_context *ctxt); 1808 1809 tristate eval_condition (svalue_id lhs, 1810 enum tree_code op, 1811 svalue_id rhs) const; 1812 tristate eval_condition_without_cm (svalue_id lhs, 1813 enum tree_code op, 1814 svalue_id rhs) const; 1815 tristate eval_condition (tree lhs, 1816 enum tree_code op, 1817 tree rhs, 1818 region_model_context *ctxt); 1819 bool add_constraint (tree lhs, enum tree_code op, tree rhs, 1820 region_model_context *ctxt); 1821 1822 tree maybe_get_constant (svalue_id sid) const; 1823 1824 region_id add_new_malloc_region (); 1825 1826 tree get_representative_tree (svalue_id sid) const; 1827 path_var get_representative_path_var (region_id rid) const; 1828 void get_path_vars_for_svalue (svalue_id sid, vec<path_var> *out) const; 1829 1830 void purge_unused_svalues (purge_stats *out, 1831 region_model_context *ctxt, 1832 svalue_id_set *known_used_sids = NULL); 1833 void remap_svalue_ids (const svalue_id_map &map); 1834 void remap_region_ids (const region_id_map &map); 1835 1836 void purge_regions (const region_id_set &set, 1837 purge_stats *stats, 1838 logger *logger); 1839 1840 unsigned get_num_svalues () const { return m_svalues.length (); } 1841 unsigned get_num_regions () const { return m_regions.length (); } 1842 1843 /* For selftests. */ 1844 constraint_manager *get_constraints () 1845 { 1846 return m_constraints; 1847 } 1848 1849 void get_descendents (region_id rid, region_id_set *out, 1850 region_id exclude_rid) const; 1851 1852 void delete_region_and_descendents (region_id rid, 1853 enum poison_kind pkind, 1854 purge_stats *stats, 1855 logger *logger); 1856 1857 bool can_merge_with_p (const region_model &other_model, 1858 region_model *out_model, 1859 svalue_id_merger_mapping *out) const; 1860 bool can_merge_with_p (const region_model &other_model, 1861 region_model *out_model) const; 1862 1863 svalue_id get_value_by_name (const char *name) const; 1864 1865 svalue_id convert_byte_offset_to_array_index (tree ptr_type, 1866 svalue_id offset_sid); 1867 1868 region_id get_or_create_mem_ref (tree type, 1869 svalue_id ptr_sid, 1870 svalue_id offset_sid, 1871 region_model_context *ctxt); 1872 region_id get_or_create_pointer_plus_expr (tree type, 1873 svalue_id ptr_sid, 1874 svalue_id offset_sid, 1875 region_model_context *ctxt); 1876 region_id get_or_create_view (region_id raw_rid, tree type, 1877 region_model_context *ctxt); 1878 1879 tree get_fndecl_for_call (const gcall *call, 1880 region_model_context *ctxt); 1881 1882 private: 1883 region_id get_lvalue_1 (path_var pv, region_model_context *ctxt); 1884 svalue_id get_rvalue_1 (path_var pv, region_model_context *ctxt); 1885 1886 void copy_struct_region (region_id dst_rid, struct_region *dst_reg, 1887 struct_region *src_reg, region_model_context *ctxt); 1888 void copy_union_region (region_id dst_rid, union_region *src_reg, 1889 region_model_context *ctxt); 1890 void copy_array_region (region_id dst_rid, array_region *dst_reg, 1891 array_region *src_reg, region_model_context *ctxt); 1892 1893 region_id make_region_for_unexpected_tree_code (region_model_context *ctxt, 1894 tree t, 1895 const dump_location_t &loc); 1896 1897 void add_any_constraints_from_ssa_def_stmt (tree lhs, 1898 enum tree_code op, 1899 tree rhs, 1900 region_model_context *ctxt); 1901 void add_any_constraints_from_gassign (enum tree_code op, 1902 tree rhs, 1903 const gassign *assign, 1904 region_model_context *ctxt); 1905 void add_any_constraints_from_gcall (enum tree_code op, 1906 tree rhs, 1907 const gcall *call, 1908 region_model_context *ctxt); 1909 1910 void update_for_call_superedge (const call_superedge &call_edge, 1911 region_model_context *ctxt); 1912 void update_for_return_superedge (const return_superedge &return_edge, 1913 region_model_context *ctxt); 1914 void update_for_call_summary (const callgraph_superedge &cg_sedge, 1915 region_model_context *ctxt); 1916 bool apply_constraints_for_gcond (const cfg_superedge &edge, 1917 const gcond *cond_stmt, 1918 region_model_context *ctxt); 1919 bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge, 1920 const gswitch *switch_stmt, 1921 region_model_context *ctxt); 1922 1923 void poison_any_pointers_to_bad_regions (const region_id_set &bad_regions, 1924 enum poison_kind pkind); 1925 1926 void dump_summary_of_rep_path_vars (pretty_printer *pp, 1927 auto_vec<path_var> *rep_path_vars, 1928 bool *is_first); 1929 1930 auto_delete_vec<svalue> m_svalues; 1931 auto_delete_vec<region> m_regions; 1932 region_id m_root_rid; 1933 constraint_manager *m_constraints; // TODO: embed, rather than dynalloc? 1934}; 1935 1936/* Some region_model activity could lead to warnings (e.g. attempts to use an 1937 uninitialized value). This abstract base class encapsulates an interface 1938 for the region model to use when emitting such warnings. 1939 1940 It also provides an interface for being notified about svalue_ids being 1941 remapped, and being deleted. 1942 1943 Having this as an abstract base class allows us to support the various 1944 operations needed by program_state in the analyzer within region_model, 1945 whilst keeping them somewhat modularized. */ 1946 1947class region_model_context 1948{ 1949 public: 1950 virtual void warn (pending_diagnostic *d) = 0; 1951 1952 /* Hook for clients that store svalue_id instances, so that they 1953 can remap their IDs when the underlying region_model renumbers 1954 the IDs. */ 1955 virtual void remap_svalue_ids (const svalue_id_map &map) = 0; 1956 1957#if 0 1958 /* Return true if if's OK to purge SID when simplifying state. 1959 Subclasses can return false for values that have sm state, 1960 to avoid generating "leak" false positives. */ 1961 virtual bool can_purge_p (svalue_id sid) = 0; 1962#endif 1963 1964 /* Hook for clients to be notified when a range of SIDs have 1965 been purged, so that they can purge state relating to those 1966 values (and potentially emit warnings about leaks). 1967 All SIDs from FIRST_PURGED_SID numerically upwards are being 1968 purged. 1969 The return values is a count of how many items of data the client 1970 has purged (potentially for use in selftests). 1971 MAP has already been applied to the IDs, but is provided in case 1972 the client needs to figure out the old IDs. */ 1973 virtual int on_svalue_purge (svalue_id first_purged_sid, 1974 const svalue_id_map &map) = 0; 1975 1976 virtual logger *get_logger () = 0; 1977 1978 /* Hook for clients to be notified when CHILD_SID is created 1979 from PARENT_SID, when "inheriting" a value for a region from a 1980 parent region. 1981 This exists so that state machines that inherit state can 1982 propagate the state from parent to child. */ 1983 virtual void on_inherited_svalue (svalue_id parent_sid, 1984 svalue_id child_sid) = 0; 1985 1986 /* Hook for clients to be notified when DST_SID is created 1987 (or reused) as a cast from SRC_SID. 1988 This exists so that state machines can propagate the state 1989 from SRC_SID to DST_SID. */ 1990 virtual void on_cast (svalue_id src_sid, 1991 svalue_id dst_sid) = 0; 1992 1993 /* Hook for clients to be notified when the condition 1994 "LHS OP RHS" is added to the region model. 1995 This exists so that state machines can detect tests on edges, 1996 and use them to trigger sm-state transitions (e.g. transitions due 1997 to ptrs becoming known to be NULL or non-NULL, rather than just 1998 "unchecked") */ 1999 virtual void on_condition (tree lhs, enum tree_code op, tree rhs) = 0; 2000 2001 /* Hooks for clients to be notified when an unknown change happens 2002 to SID (in response to a call to an unknown function). */ 2003 virtual void on_unknown_change (svalue_id sid) = 0; 2004 2005 /* Hooks for clients to be notified when a phi node is handled, 2006 where RHS is the pertinent argument. */ 2007 virtual void on_phi (const gphi *phi, tree rhs) = 0; 2008 2009 /* Hooks for clients to be notified when the region model doesn't 2010 know how to handle the tree code of T at LOC. */ 2011 virtual void on_unexpected_tree_code (tree t, 2012 const dump_location_t &loc) = 0; 2013}; 2014 2015/* A "do nothing" subclass of region_model_context. */ 2016 2017class noop_region_model_context : public region_model_context 2018{ 2019public: 2020 void warn (pending_diagnostic *) OVERRIDE {} 2021 void remap_svalue_ids (const svalue_id_map &) OVERRIDE {} 2022 int on_svalue_purge (svalue_id, const svalue_id_map &) OVERRIDE 2023 { 2024 return 0; 2025 } 2026 logger *get_logger () OVERRIDE { return NULL; } 2027 void on_inherited_svalue (svalue_id parent_sid ATTRIBUTE_UNUSED, 2028 svalue_id child_sid ATTRIBUTE_UNUSED) 2029 OVERRIDE 2030 { 2031 } 2032 void on_cast (svalue_id src_sid ATTRIBUTE_UNUSED, 2033 svalue_id dst_sid ATTRIBUTE_UNUSED) OVERRIDE 2034 { 2035 } 2036 void on_condition (tree lhs ATTRIBUTE_UNUSED, 2037 enum tree_code op ATTRIBUTE_UNUSED, 2038 tree rhs ATTRIBUTE_UNUSED) OVERRIDE 2039 { 2040 } 2041 void on_unknown_change (svalue_id sid ATTRIBUTE_UNUSED) OVERRIDE 2042 { 2043 } 2044 void on_phi (const gphi *phi ATTRIBUTE_UNUSED, 2045 tree rhs ATTRIBUTE_UNUSED) OVERRIDE 2046 { 2047 } 2048 void on_unexpected_tree_code (tree, const dump_location_t &) OVERRIDE {} 2049}; 2050 2051/* A subclass of region_model_context for determining if operations fail 2052 e.g. "can we generate a region for the lvalue of EXPR?". */ 2053 2054class tentative_region_model_context : public noop_region_model_context 2055{ 2056public: 2057 tentative_region_model_context () : m_num_unexpected_codes (0) {} 2058 2059 void on_unexpected_tree_code (tree, const dump_location_t &) 2060 FINAL OVERRIDE 2061 { 2062 m_num_unexpected_codes++; 2063 } 2064 2065 bool had_errors_p () const { return m_num_unexpected_codes > 0; } 2066 2067private: 2068 int m_num_unexpected_codes; 2069}; 2070 2071/* A bundle of data for use when attempting to merge two region_model 2072 instances to make a third. */ 2073 2074struct model_merger 2075{ 2076 model_merger (const region_model *model_a, 2077 const region_model *model_b, 2078 region_model *merged_model, 2079 svalue_id_merger_mapping *sid_mapping) 2080 : m_model_a (model_a), m_model_b (model_b), 2081 m_merged_model (merged_model), 2082 m_map_regions_from_a_to_m (model_a->get_num_regions ()), 2083 m_map_regions_from_b_to_m (model_b->get_num_regions ()), 2084 m_sid_mapping (sid_mapping) 2085 { 2086 gcc_assert (sid_mapping); 2087 } 2088 2089 void dump_to_pp (pretty_printer *pp) const; 2090 void dump (FILE *fp) const; 2091 void dump () const; 2092 2093 template <typename Subclass> 2094 Subclass *get_region_a (region_id rid_a) const 2095 { 2096 return m_model_a->get_region <Subclass> (rid_a); 2097 } 2098 2099 template <typename Subclass> 2100 Subclass *get_region_b (region_id rid_b) const 2101 { 2102 return m_model_b->get_region <Subclass> (rid_b); 2103 } 2104 2105 bool can_merge_values_p (svalue_id sid_a, 2106 svalue_id sid_b, 2107 svalue_id *merged_sid); 2108 2109 void record_regions (region_id a_rid, 2110 region_id b_rid, 2111 region_id merged_rid); 2112 2113 void record_svalues (svalue_id a_sid, 2114 svalue_id b_sid, 2115 svalue_id merged_sid); 2116 2117 const region_model *m_model_a; 2118 const region_model *m_model_b; 2119 region_model *m_merged_model; 2120 2121 one_way_region_id_map m_map_regions_from_a_to_m; 2122 one_way_region_id_map m_map_regions_from_b_to_m; 2123 svalue_id_merger_mapping *m_sid_mapping; 2124}; 2125 2126/* A bundle of data that can be optionally generated during merger of two 2127 region_models that describes how svalue_ids in each of the two inputs 2128 are mapped to svalue_ids in the merged output. 2129 2130 For use when merging sm-states within program_state. */ 2131 2132struct svalue_id_merger_mapping 2133{ 2134 svalue_id_merger_mapping (const region_model &a, 2135 const region_model &b); 2136 2137 void dump_to_pp (pretty_printer *pp) const; 2138 void dump (FILE *fp) const; 2139 void dump () const; 2140 2141 one_way_svalue_id_map m_map_from_a_to_m; 2142 one_way_svalue_id_map m_map_from_b_to_m; 2143}; 2144 2145/* A bundle of data used when canonicalizing a region_model so that the 2146 order of regions and svalues is in a predictable order (thus increasing 2147 the chance of two region_models being equal). 2148 2149 This object is used to keep track of a recursive traversal across the 2150 svalues and regions within the model, made in a deterministic order, 2151 assigning new ids the first time each region or svalue is 2152 encountered. */ 2153 2154struct canonicalization 2155{ 2156 canonicalization (const region_model &model); 2157 void walk_rid (region_id rid); 2158 void walk_sid (svalue_id sid); 2159 2160 void dump_to_pp (pretty_printer *pp) const; 2161 void dump (FILE *fp) const; 2162 void dump () const; 2163 2164 const region_model &m_model; 2165 /* Maps from existing IDs to new IDs. */ 2166 region_id_map m_rid_map; 2167 svalue_id_map m_sid_map; 2168 /* The next IDs to hand out. */ 2169 int m_next_rid_int; 2170 int m_next_sid_int; 2171}; 2172 2173} // namespace ana 2174 2175namespace inchash 2176{ 2177 extern void add (svalue_id sid, hash &hstate); 2178 extern void add (region_id rid, hash &hstate); 2179} // namespace inchash 2180 2181extern void debug (const region_model &rmodel); 2182 2183namespace ana { 2184 2185#if CHECKING_P 2186 2187namespace selftest { 2188 2189using namespace ::selftest; 2190 2191/* An implementation of region_model_context for use in selftests, which 2192 stores any pending_diagnostic instances passed to it. */ 2193 2194class test_region_model_context : public noop_region_model_context 2195{ 2196public: 2197 void warn (pending_diagnostic *d) FINAL OVERRIDE 2198 { 2199 m_diagnostics.safe_push (d); 2200 } 2201 2202 unsigned get_num_diagnostics () const { return m_diagnostics.length (); } 2203 2204 void on_unexpected_tree_code (tree t, const dump_location_t &) 2205 FINAL OVERRIDE 2206 { 2207 internal_error ("unhandled tree code: %qs", 2208 t ? get_tree_code_name (TREE_CODE (t)) : "(null)"); 2209 } 2210 2211private: 2212 /* Implicitly delete any diagnostics in the dtor. */ 2213 auto_delete_vec<pending_diagnostic> m_diagnostics; 2214}; 2215 2216/* Attempt to add the constraint (LHS OP RHS) to MODEL. 2217 Verify that MODEL remains satisfiable. */ 2218 2219#define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \ 2220 SELFTEST_BEGIN_STMT \ 2221 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \ 2222 ASSERT_TRUE (sat); \ 2223 SELFTEST_END_STMT 2224 2225/* Attempt to add the constraint (LHS OP RHS) to MODEL. 2226 Verify that the result is not satisfiable. */ 2227 2228#define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \ 2229 SELFTEST_BEGIN_STMT \ 2230 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \ 2231 ASSERT_FALSE (sat); \ 2232 SELFTEST_END_STMT 2233 2234/* Implementation detail of the ASSERT_CONDITION_* macros. */ 2235 2236void assert_condition (const location &loc, 2237 region_model &model, 2238 tree lhs, tree_code op, tree rhs, 2239 tristate expected); 2240 2241/* Assert that REGION_MODEL evaluates the condition "LHS OP RHS" 2242 as "true". */ 2243 2244#define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \ 2245 SELFTEST_BEGIN_STMT \ 2246 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \ 2247 tristate (tristate::TS_TRUE)); \ 2248 SELFTEST_END_STMT 2249 2250/* Assert that REGION_MODEL evaluates the condition "LHS OP RHS" 2251 as "false". */ 2252 2253#define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \ 2254 SELFTEST_BEGIN_STMT \ 2255 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \ 2256 tristate (tristate::TS_FALSE)); \ 2257 SELFTEST_END_STMT 2258 2259/* Assert that REGION_MODEL evaluates the condition "LHS OP RHS" 2260 as "unknown". */ 2261 2262#define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \ 2263 SELFTEST_BEGIN_STMT \ 2264 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \ 2265 tristate (tristate::TS_UNKNOWN)); \ 2266 SELFTEST_END_STMT 2267 2268} /* end of namespace selftest. */ 2269 2270#endif /* #if CHECKING_P */ 2271 2272} // namespace ana 2273 2274#endif /* GCC_ANALYZER_REGION_MODEL_H */ 2275