1/* Classes for modeling the state of memory. 2 Copyright (C) 2019-2022 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#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tree.h" 25#include "function.h" 26#include "basic-block.h" 27#include "gimple.h" 28#include "gimple-iterator.h" 29#include "diagnostic-core.h" 30#include "graphviz.h" 31#include "options.h" 32#include "cgraph.h" 33#include "tree-dfa.h" 34#include "stringpool.h" 35#include "convert.h" 36#include "target.h" 37#include "fold-const.h" 38#include "tree-pretty-print.h" 39#include "diagnostic-color.h" 40#include "diagnostic-metadata.h" 41#include "tristate.h" 42#include "bitmap.h" 43#include "selftest.h" 44#include "function.h" 45#include "json.h" 46#include "analyzer/analyzer.h" 47#include "analyzer/analyzer-logging.h" 48#include "ordered-hash-map.h" 49#include "options.h" 50#include "cgraph.h" 51#include "cfg.h" 52#include "digraph.h" 53#include "analyzer/supergraph.h" 54#include "sbitmap.h" 55#include "analyzer/call-string.h" 56#include "analyzer/program-point.h" 57#include "analyzer/store.h" 58#include "analyzer/region-model.h" 59#include "analyzer/constraint-manager.h" 60#include "diagnostic-event-id.h" 61#include "analyzer/sm.h" 62#include "diagnostic-event-id.h" 63#include "analyzer/sm.h" 64#include "analyzer/pending-diagnostic.h" 65#include "analyzer/region-model-reachability.h" 66#include "analyzer/analyzer-selftests.h" 67#include "analyzer/program-state.h" 68#include "stor-layout.h" 69#include "attribs.h" 70#include "tree-object-size.h" 71#include "gimple-ssa.h" 72#include "tree-phinodes.h" 73#include "tree-ssa-operands.h" 74#include "ssa-iterators.h" 75#include "calls.h" 76 77#if ENABLE_ANALYZER 78 79namespace ana { 80 81/* Dump T to PP in language-independent form, for debugging/logging/dumping 82 purposes. */ 83 84void 85dump_tree (pretty_printer *pp, tree t) 86{ 87 dump_generic_node (pp, t, 0, TDF_SLIM, 0); 88} 89 90/* Dump T to PP in language-independent form in quotes, for 91 debugging/logging/dumping purposes. */ 92 93void 94dump_quoted_tree (pretty_printer *pp, tree t) 95{ 96 pp_begin_quote (pp, pp_show_color (pp)); 97 dump_tree (pp, t); 98 pp_end_quote (pp, pp_show_color (pp)); 99} 100 101/* Equivalent to pp_printf (pp, "%qT", t), to avoid nesting pp_printf 102 calls within other pp_printf calls. 103 104 default_tree_printer handles 'T' and some other codes by calling 105 dump_generic_node (pp, t, 0, TDF_SLIM, 0); 106 dump_generic_node calls pp_printf in various places, leading to 107 garbled output. 108 109 Ideally pp_printf could be made to be reentrant, but in the meantime 110 this function provides a workaround. */ 111 112void 113print_quoted_type (pretty_printer *pp, tree t) 114{ 115 pp_begin_quote (pp, pp_show_color (pp)); 116 dump_generic_node (pp, t, 0, TDF_SLIM, 0); 117 pp_end_quote (pp, pp_show_color (pp)); 118} 119 120/* class region_to_value_map. */ 121 122/* Assignment operator for region_to_value_map. */ 123 124region_to_value_map & 125region_to_value_map::operator= (const region_to_value_map &other) 126{ 127 m_hash_map.empty (); 128 for (auto iter : other.m_hash_map) 129 { 130 const region *reg = iter.first; 131 const svalue *sval = iter.second; 132 m_hash_map.put (reg, sval); 133 } 134 return *this; 135} 136 137/* Equality operator for region_to_value_map. */ 138 139bool 140region_to_value_map::operator== (const region_to_value_map &other) const 141{ 142 if (m_hash_map.elements () != other.m_hash_map.elements ()) 143 return false; 144 145 for (auto iter : *this) 146 { 147 const region *reg = iter.first; 148 const svalue *sval = iter.second; 149 const svalue * const *other_slot = other.get (reg); 150 if (other_slot == NULL) 151 return false; 152 if (sval != *other_slot) 153 return false; 154 } 155 156 return true; 157} 158 159/* Dump this object to PP. */ 160 161void 162region_to_value_map::dump_to_pp (pretty_printer *pp, bool simple, 163 bool multiline) const 164{ 165 auto_vec<const region *> regs; 166 for (iterator iter = begin (); iter != end (); ++iter) 167 regs.safe_push ((*iter).first); 168 regs.qsort (region::cmp_ptr_ptr); 169 if (multiline) 170 pp_newline (pp); 171 else 172 pp_string (pp, " {"); 173 unsigned i; 174 const region *reg; 175 FOR_EACH_VEC_ELT (regs, i, reg) 176 { 177 if (multiline) 178 pp_string (pp, " "); 179 else if (i > 0) 180 pp_string (pp, ", "); 181 reg->dump_to_pp (pp, simple); 182 pp_string (pp, ": "); 183 const svalue *sval = *get (reg); 184 sval->dump_to_pp (pp, true); 185 if (multiline) 186 pp_newline (pp); 187 } 188 if (!multiline) 189 pp_string (pp, "}"); 190} 191 192/* Dump this object to stderr. */ 193 194DEBUG_FUNCTION void 195region_to_value_map::dump (bool simple) const 196{ 197 pretty_printer pp; 198 pp_format_decoder (&pp) = default_tree_printer; 199 pp_show_color (&pp) = pp_show_color (global_dc->printer); 200 pp.buffer->stream = stderr; 201 dump_to_pp (&pp, simple, true); 202 pp_newline (&pp); 203 pp_flush (&pp); 204} 205 206 207/* Attempt to merge THIS with OTHER, writing the result 208 to OUT. 209 210 For now, write (region, value) mappings that are in common between THIS 211 and OTHER to OUT, effectively taking the intersection, rather than 212 rejecting differences. */ 213 214bool 215region_to_value_map::can_merge_with_p (const region_to_value_map &other, 216 region_to_value_map *out) const 217{ 218 for (auto iter : *this) 219 { 220 const region *iter_reg = iter.first; 221 const svalue *iter_sval = iter.second; 222 const svalue * const * other_slot = other.get (iter_reg); 223 if (other_slot) 224 if (iter_sval == *other_slot) 225 out->put (iter_reg, iter_sval); 226 } 227 return true; 228} 229 230/* Purge any state involving SVAL. */ 231 232void 233region_to_value_map::purge_state_involving (const svalue *sval) 234{ 235 auto_vec<const region *> to_purge; 236 for (auto iter : *this) 237 { 238 const region *iter_reg = iter.first; 239 const svalue *iter_sval = iter.second; 240 if (iter_reg->involves_p (sval) || iter_sval->involves_p (sval)) 241 to_purge.safe_push (iter_reg); 242 } 243 for (auto iter : to_purge) 244 m_hash_map.remove (iter); 245} 246 247/* class region_model. */ 248 249/* Ctor for region_model: construct an "empty" model. */ 250 251region_model::region_model (region_model_manager *mgr) 252: m_mgr (mgr), m_store (), m_current_frame (NULL), 253 m_dynamic_extents () 254{ 255 m_constraints = new constraint_manager (mgr); 256} 257 258/* region_model's copy ctor. */ 259 260region_model::region_model (const region_model &other) 261: m_mgr (other.m_mgr), m_store (other.m_store), 262 m_constraints (new constraint_manager (*other.m_constraints)), 263 m_current_frame (other.m_current_frame), 264 m_dynamic_extents (other.m_dynamic_extents) 265{ 266} 267 268/* region_model's dtor. */ 269 270region_model::~region_model () 271{ 272 delete m_constraints; 273} 274 275/* region_model's assignment operator. */ 276 277region_model & 278region_model::operator= (const region_model &other) 279{ 280 /* m_mgr is const. */ 281 gcc_assert (m_mgr == other.m_mgr); 282 283 m_store = other.m_store; 284 285 delete m_constraints; 286 m_constraints = new constraint_manager (*other.m_constraints); 287 288 m_current_frame = other.m_current_frame; 289 290 m_dynamic_extents = other.m_dynamic_extents; 291 292 return *this; 293} 294 295/* Equality operator for region_model. 296 297 Amongst other things this directly compares the stores and the constraint 298 managers, so for this to be meaningful both this and OTHER should 299 have been canonicalized. */ 300 301bool 302region_model::operator== (const region_model &other) const 303{ 304 /* We can only compare instances that use the same manager. */ 305 gcc_assert (m_mgr == other.m_mgr); 306 307 if (m_store != other.m_store) 308 return false; 309 310 if (*m_constraints != *other.m_constraints) 311 return false; 312 313 if (m_current_frame != other.m_current_frame) 314 return false; 315 316 if (m_dynamic_extents != other.m_dynamic_extents) 317 return false; 318 319 gcc_checking_assert (hash () == other.hash ()); 320 321 return true; 322} 323 324/* Generate a hash value for this region_model. */ 325 326hashval_t 327region_model::hash () const 328{ 329 hashval_t result = m_store.hash (); 330 result ^= m_constraints->hash (); 331 return result; 332} 333 334/* Dump a representation of this model to PP, showing the 335 stack, the store, and any constraints. 336 Use SIMPLE to control how svalues and regions are printed. */ 337 338void 339region_model::dump_to_pp (pretty_printer *pp, bool simple, 340 bool multiline) const 341{ 342 /* Dump stack. */ 343 pp_printf (pp, "stack depth: %i", get_stack_depth ()); 344 if (multiline) 345 pp_newline (pp); 346 else 347 pp_string (pp, " {"); 348 for (const frame_region *iter_frame = m_current_frame; iter_frame; 349 iter_frame = iter_frame->get_calling_frame ()) 350 { 351 if (multiline) 352 pp_string (pp, " "); 353 else if (iter_frame != m_current_frame) 354 pp_string (pp, ", "); 355 pp_printf (pp, "frame (index %i): ", iter_frame->get_index ()); 356 iter_frame->dump_to_pp (pp, simple); 357 if (multiline) 358 pp_newline (pp); 359 } 360 if (!multiline) 361 pp_string (pp, "}"); 362 363 /* Dump store. */ 364 if (!multiline) 365 pp_string (pp, ", {"); 366 m_store.dump_to_pp (pp, simple, multiline, 367 m_mgr->get_store_manager ()); 368 if (!multiline) 369 pp_string (pp, "}"); 370 371 /* Dump constraints. */ 372 pp_string (pp, "constraint_manager:"); 373 if (multiline) 374 pp_newline (pp); 375 else 376 pp_string (pp, " {"); 377 m_constraints->dump_to_pp (pp, multiline); 378 if (!multiline) 379 pp_string (pp, "}"); 380 381 /* Dump sizes of dynamic regions, if any are known. */ 382 if (!m_dynamic_extents.is_empty ()) 383 { 384 pp_string (pp, "dynamic_extents:"); 385 m_dynamic_extents.dump_to_pp (pp, simple, multiline); 386 } 387} 388 389/* Dump a representation of this model to FILE. */ 390 391void 392region_model::dump (FILE *fp, bool simple, bool multiline) const 393{ 394 pretty_printer pp; 395 pp_format_decoder (&pp) = default_tree_printer; 396 pp_show_color (&pp) = pp_show_color (global_dc->printer); 397 pp.buffer->stream = fp; 398 dump_to_pp (&pp, simple, multiline); 399 pp_newline (&pp); 400 pp_flush (&pp); 401} 402 403/* Dump a multiline representation of this model to stderr. */ 404 405DEBUG_FUNCTION void 406region_model::dump (bool simple) const 407{ 408 dump (stderr, simple, true); 409} 410 411/* Dump a multiline representation of this model to stderr. */ 412 413DEBUG_FUNCTION void 414region_model::debug () const 415{ 416 dump (true); 417} 418 419/* Assert that this object is valid. */ 420 421void 422region_model::validate () const 423{ 424 m_store.validate (); 425} 426 427/* Canonicalize the store and constraints, to maximize the chance of 428 equality between region_model instances. */ 429 430void 431region_model::canonicalize () 432{ 433 m_store.canonicalize (m_mgr->get_store_manager ()); 434 m_constraints->canonicalize (); 435} 436 437/* Return true if this region_model is in canonical form. */ 438 439bool 440region_model::canonicalized_p () const 441{ 442 region_model copy (*this); 443 copy.canonicalize (); 444 return *this == copy; 445} 446 447/* See the comment for store::loop_replay_fixup. */ 448 449void 450region_model::loop_replay_fixup (const region_model *dst_state) 451{ 452 m_store.loop_replay_fixup (dst_state->get_store (), m_mgr); 453} 454 455/* A subclass of pending_diagnostic for complaining about uses of 456 poisoned values. */ 457 458class poisoned_value_diagnostic 459: public pending_diagnostic_subclass<poisoned_value_diagnostic> 460{ 461public: 462 poisoned_value_diagnostic (tree expr, enum poison_kind pkind, 463 const region *src_region) 464 : m_expr (expr), m_pkind (pkind), 465 m_src_region (src_region) 466 {} 467 468 const char *get_kind () const FINAL OVERRIDE { return "poisoned_value_diagnostic"; } 469 470 bool use_of_uninit_p () const FINAL OVERRIDE 471 { 472 return m_pkind == POISON_KIND_UNINIT; 473 } 474 475 bool operator== (const poisoned_value_diagnostic &other) const 476 { 477 return (m_expr == other.m_expr 478 && m_pkind == other.m_pkind 479 && m_src_region == other.m_src_region); 480 } 481 482 int get_controlling_option () const FINAL OVERRIDE 483 { 484 switch (m_pkind) 485 { 486 default: 487 gcc_unreachable (); 488 case POISON_KIND_UNINIT: 489 return OPT_Wanalyzer_use_of_uninitialized_value; 490 case POISON_KIND_FREED: 491 return OPT_Wanalyzer_use_after_free; 492 case POISON_KIND_POPPED_STACK: 493 return OPT_Wanalyzer_use_of_pointer_in_stale_stack_frame; 494 } 495 } 496 497 bool emit (rich_location *rich_loc) FINAL OVERRIDE 498 { 499 switch (m_pkind) 500 { 501 default: 502 gcc_unreachable (); 503 case POISON_KIND_UNINIT: 504 { 505 diagnostic_metadata m; 506 m.add_cwe (457); /* "CWE-457: Use of Uninitialized Variable". */ 507 return warning_meta (rich_loc, m, get_controlling_option (), 508 "use of uninitialized value %qE", 509 m_expr); 510 } 511 break; 512 case POISON_KIND_FREED: 513 { 514 diagnostic_metadata m; 515 m.add_cwe (416); /* "CWE-416: Use After Free". */ 516 return warning_meta (rich_loc, m, get_controlling_option (), 517 "use after %<free%> of %qE", 518 m_expr); 519 } 520 break; 521 case POISON_KIND_POPPED_STACK: 522 { 523 /* TODO: which CWE? */ 524 return warning_at 525 (rich_loc, get_controlling_option (), 526 "dereferencing pointer %qE to within stale stack frame", 527 m_expr); 528 } 529 break; 530 } 531 } 532 533 label_text describe_final_event (const evdesc::final_event &ev) FINAL OVERRIDE 534 { 535 switch (m_pkind) 536 { 537 default: 538 gcc_unreachable (); 539 case POISON_KIND_UNINIT: 540 return ev.formatted_print ("use of uninitialized value %qE here", 541 m_expr); 542 case POISON_KIND_FREED: 543 return ev.formatted_print ("use after %<free%> of %qE here", 544 m_expr); 545 case POISON_KIND_POPPED_STACK: 546 return ev.formatted_print 547 ("dereferencing pointer %qE to within stale stack frame", 548 m_expr); 549 } 550 } 551 552 void mark_interesting_stuff (interesting_t *interest) FINAL OVERRIDE 553 { 554 if (m_src_region) 555 interest->add_region_creation (m_src_region); 556 } 557 558private: 559 tree m_expr; 560 enum poison_kind m_pkind; 561 const region *m_src_region; 562}; 563 564/* A subclass of pending_diagnostic for complaining about shifts 565 by negative counts. */ 566 567class shift_count_negative_diagnostic 568: public pending_diagnostic_subclass<shift_count_negative_diagnostic> 569{ 570public: 571 shift_count_negative_diagnostic (const gassign *assign, tree count_cst) 572 : m_assign (assign), m_count_cst (count_cst) 573 {} 574 575 const char *get_kind () const FINAL OVERRIDE 576 { 577 return "shift_count_negative_diagnostic"; 578 } 579 580 bool operator== (const shift_count_negative_diagnostic &other) const 581 { 582 return (m_assign == other.m_assign 583 && same_tree_p (m_count_cst, other.m_count_cst)); 584 } 585 586 int get_controlling_option () const FINAL OVERRIDE 587 { 588 return OPT_Wanalyzer_shift_count_negative; 589 } 590 591 bool emit (rich_location *rich_loc) FINAL OVERRIDE 592 { 593 return warning_at (rich_loc, get_controlling_option (), 594 "shift by negative count (%qE)", m_count_cst); 595 } 596 597 label_text describe_final_event (const evdesc::final_event &ev) FINAL OVERRIDE 598 { 599 return ev.formatted_print ("shift by negative amount here (%qE)", m_count_cst); 600 } 601 602private: 603 const gassign *m_assign; 604 tree m_count_cst; 605}; 606 607/* A subclass of pending_diagnostic for complaining about shifts 608 by counts >= the width of the operand type. */ 609 610class shift_count_overflow_diagnostic 611: public pending_diagnostic_subclass<shift_count_overflow_diagnostic> 612{ 613public: 614 shift_count_overflow_diagnostic (const gassign *assign, 615 int operand_precision, 616 tree count_cst) 617 : m_assign (assign), m_operand_precision (operand_precision), 618 m_count_cst (count_cst) 619 {} 620 621 const char *get_kind () const FINAL OVERRIDE 622 { 623 return "shift_count_overflow_diagnostic"; 624 } 625 626 bool operator== (const shift_count_overflow_diagnostic &other) const 627 { 628 return (m_assign == other.m_assign 629 && m_operand_precision == other.m_operand_precision 630 && same_tree_p (m_count_cst, other.m_count_cst)); 631 } 632 633 int get_controlling_option () const FINAL OVERRIDE 634 { 635 return OPT_Wanalyzer_shift_count_overflow; 636 } 637 638 bool emit (rich_location *rich_loc) FINAL OVERRIDE 639 { 640 return warning_at (rich_loc, get_controlling_option (), 641 "shift by count (%qE) >= precision of type (%qi)", 642 m_count_cst, m_operand_precision); 643 } 644 645 label_text describe_final_event (const evdesc::final_event &ev) FINAL OVERRIDE 646 { 647 return ev.formatted_print ("shift by count %qE here", m_count_cst); 648 } 649 650private: 651 const gassign *m_assign; 652 int m_operand_precision; 653 tree m_count_cst; 654}; 655 656/* If ASSIGN is a stmt that can be modelled via 657 set_value (lhs_reg, SVALUE, CTXT) 658 for some SVALUE, get the SVALUE. 659 Otherwise return NULL. */ 660 661const svalue * 662region_model::get_gassign_result (const gassign *assign, 663 region_model_context *ctxt) 664{ 665 tree lhs = gimple_assign_lhs (assign); 666 tree rhs1 = gimple_assign_rhs1 (assign); 667 enum tree_code op = gimple_assign_rhs_code (assign); 668 switch (op) 669 { 670 default: 671 return NULL; 672 673 case POINTER_PLUS_EXPR: 674 { 675 /* e.g. "_1 = a_10(D) + 12;" */ 676 tree ptr = rhs1; 677 tree offset = gimple_assign_rhs2 (assign); 678 679 const svalue *ptr_sval = get_rvalue (ptr, ctxt); 680 const svalue *offset_sval = get_rvalue (offset, ctxt); 681 /* Quoting tree.def, "the second operand [of a POINTER_PLUS_EXPR] 682 is an integer of type sizetype". */ 683 offset_sval = m_mgr->get_or_create_cast (size_type_node, offset_sval); 684 685 const svalue *sval_binop 686 = m_mgr->get_or_create_binop (TREE_TYPE (lhs), op, 687 ptr_sval, offset_sval); 688 return sval_binop; 689 } 690 break; 691 692 case POINTER_DIFF_EXPR: 693 { 694 /* e.g. "_1 = p_2(D) - q_3(D);". */ 695 tree rhs2 = gimple_assign_rhs2 (assign); 696 const svalue *rhs1_sval = get_rvalue (rhs1, ctxt); 697 const svalue *rhs2_sval = get_rvalue (rhs2, ctxt); 698 699 // TODO: perhaps fold to zero if they're known to be equal? 700 701 const svalue *sval_binop 702 = m_mgr->get_or_create_binop (TREE_TYPE (lhs), op, 703 rhs1_sval, rhs2_sval); 704 return sval_binop; 705 } 706 break; 707 708 /* Assignments of the form 709 set_value (lvalue (LHS), rvalue (EXPR)) 710 for various EXPR. 711 We already have the lvalue for the LHS above, as "lhs_reg". */ 712 case ADDR_EXPR: /* LHS = &RHS; */ 713 case BIT_FIELD_REF: 714 case COMPONENT_REF: /* LHS = op0.op1; */ 715 case MEM_REF: 716 case REAL_CST: 717 case COMPLEX_CST: 718 case VECTOR_CST: 719 case INTEGER_CST: 720 case ARRAY_REF: 721 case SSA_NAME: /* LHS = VAR; */ 722 case VAR_DECL: /* LHS = VAR; */ 723 case PARM_DECL:/* LHS = VAR; */ 724 case REALPART_EXPR: 725 case IMAGPART_EXPR: 726 return get_rvalue (rhs1, ctxt); 727 728 case ABS_EXPR: 729 case ABSU_EXPR: 730 case CONJ_EXPR: 731 case BIT_NOT_EXPR: 732 case FIX_TRUNC_EXPR: 733 case FLOAT_EXPR: 734 case NEGATE_EXPR: 735 case NOP_EXPR: 736 case VIEW_CONVERT_EXPR: 737 { 738 /* Unary ops. */ 739 const svalue *rhs_sval = get_rvalue (rhs1, ctxt); 740 const svalue *sval_unaryop 741 = m_mgr->get_or_create_unaryop (TREE_TYPE (lhs), op, rhs_sval); 742 return sval_unaryop; 743 } 744 745 case EQ_EXPR: 746 case GE_EXPR: 747 case LE_EXPR: 748 case NE_EXPR: 749 case GT_EXPR: 750 case LT_EXPR: 751 case UNORDERED_EXPR: 752 case ORDERED_EXPR: 753 { 754 tree rhs2 = gimple_assign_rhs2 (assign); 755 756 const svalue *rhs1_sval = get_rvalue (rhs1, ctxt); 757 const svalue *rhs2_sval = get_rvalue (rhs2, ctxt); 758 759 if (TREE_TYPE (lhs) == boolean_type_node) 760 { 761 /* Consider constraints between svalues. */ 762 tristate t = eval_condition (rhs1_sval, op, rhs2_sval); 763 if (t.is_known ()) 764 return m_mgr->get_or_create_constant_svalue 765 (t.is_true () ? boolean_true_node : boolean_false_node); 766 } 767 768 /* Otherwise, generate a symbolic binary op. */ 769 const svalue *sval_binop 770 = m_mgr->get_or_create_binop (TREE_TYPE (lhs), op, 771 rhs1_sval, rhs2_sval); 772 return sval_binop; 773 } 774 break; 775 776 case PLUS_EXPR: 777 case MINUS_EXPR: 778 case MULT_EXPR: 779 case MULT_HIGHPART_EXPR: 780 case TRUNC_DIV_EXPR: 781 case CEIL_DIV_EXPR: 782 case FLOOR_DIV_EXPR: 783 case ROUND_DIV_EXPR: 784 case TRUNC_MOD_EXPR: 785 case CEIL_MOD_EXPR: 786 case FLOOR_MOD_EXPR: 787 case ROUND_MOD_EXPR: 788 case RDIV_EXPR: 789 case EXACT_DIV_EXPR: 790 case LSHIFT_EXPR: 791 case RSHIFT_EXPR: 792 case LROTATE_EXPR: 793 case RROTATE_EXPR: 794 case BIT_IOR_EXPR: 795 case BIT_XOR_EXPR: 796 case BIT_AND_EXPR: 797 case MIN_EXPR: 798 case MAX_EXPR: 799 case COMPLEX_EXPR: 800 { 801 /* Binary ops. */ 802 tree rhs2 = gimple_assign_rhs2 (assign); 803 804 const svalue *rhs1_sval = get_rvalue (rhs1, ctxt); 805 const svalue *rhs2_sval = get_rvalue (rhs2, ctxt); 806 807 if (ctxt && (op == LSHIFT_EXPR || op == RSHIFT_EXPR)) 808 { 809 /* "INT34-C. Do not shift an expression by a negative number of bits 810 or by greater than or equal to the number of bits that exist in 811 the operand." */ 812 if (const tree rhs2_cst = rhs2_sval->maybe_get_constant ()) 813 if (TREE_CODE (rhs2_cst) == INTEGER_CST) 814 { 815 if (tree_int_cst_sgn (rhs2_cst) < 0) 816 ctxt->warn (new shift_count_negative_diagnostic 817 (assign, rhs2_cst)); 818 else if (compare_tree_int (rhs2_cst, 819 TYPE_PRECISION (TREE_TYPE (rhs1))) 820 >= 0) 821 ctxt->warn (new shift_count_overflow_diagnostic 822 (assign, TYPE_PRECISION (TREE_TYPE (rhs1)), 823 rhs2_cst)); 824 } 825 } 826 827 const svalue *sval_binop 828 = m_mgr->get_or_create_binop (TREE_TYPE (lhs), op, 829 rhs1_sval, rhs2_sval); 830 return sval_binop; 831 } 832 833 /* Vector expressions. In theory we could implement these elementwise, 834 but for now, simply return unknown values. */ 835 case VEC_DUPLICATE_EXPR: 836 case VEC_SERIES_EXPR: 837 case VEC_COND_EXPR: 838 case VEC_PERM_EXPR: 839 case VEC_WIDEN_MULT_HI_EXPR: 840 case VEC_WIDEN_MULT_LO_EXPR: 841 case VEC_WIDEN_MULT_EVEN_EXPR: 842 case VEC_WIDEN_MULT_ODD_EXPR: 843 case VEC_UNPACK_HI_EXPR: 844 case VEC_UNPACK_LO_EXPR: 845 case VEC_UNPACK_FLOAT_HI_EXPR: 846 case VEC_UNPACK_FLOAT_LO_EXPR: 847 case VEC_UNPACK_FIX_TRUNC_HI_EXPR: 848 case VEC_UNPACK_FIX_TRUNC_LO_EXPR: 849 case VEC_PACK_TRUNC_EXPR: 850 case VEC_PACK_SAT_EXPR: 851 case VEC_PACK_FIX_TRUNC_EXPR: 852 case VEC_PACK_FLOAT_EXPR: 853 case VEC_WIDEN_LSHIFT_HI_EXPR: 854 case VEC_WIDEN_LSHIFT_LO_EXPR: 855 return m_mgr->get_or_create_unknown_svalue (TREE_TYPE (lhs)); 856 } 857} 858 859/* Workaround for discarding certain false positives from 860 -Wanalyzer-use-of-uninitialized-value 861 of the form: 862 ((A OR-IF B) OR-IF C) 863 and: 864 ((A AND-IF B) AND-IF C) 865 where evaluating B is redundant, but could involve simple accesses of 866 uninitialized locals. 867 868 When optimization is turned on the FE can immediately fold compound 869 conditionals. Specifically, c_parser_condition parses this condition: 870 ((A OR-IF B) OR-IF C) 871 and calls c_fully_fold on the condition. 872 Within c_fully_fold, fold_truth_andor is called, which bails when 873 optimization is off, but if any optimization is turned on can convert the 874 ((A OR-IF B) OR-IF C) 875 into: 876 ((A OR B) OR_IF C) 877 for sufficiently simple B 878 i.e. the inner OR-IF becomes an OR. 879 At gimplification time the inner OR becomes BIT_IOR_EXPR (in gimplify_expr), 880 giving this for the inner condition: 881 tmp = A | B; 882 if (tmp) 883 thus effectively synthesizing a redundant access of B when optimization 884 is turned on, when compared to: 885 if (A) goto L1; else goto L4; 886 L1: if (B) goto L2; else goto L4; 887 L2: if (C) goto L3; else goto L4; 888 for the unoptimized case. 889 890 Return true if CTXT appears to be handling such a short-circuitable stmt, 891 such as the def-stmt for B for the: 892 tmp = A | B; 893 case above, for the case where A is true and thus B would have been 894 short-circuited without optimization, using MODEL for the value of A. */ 895 896static bool 897within_short_circuited_stmt_p (const region_model *model, 898 const gassign *assign_stmt) 899{ 900 /* We must have an assignment to a temporary of _Bool type. */ 901 tree lhs = gimple_assign_lhs (assign_stmt); 902 if (TREE_TYPE (lhs) != boolean_type_node) 903 return false; 904 if (TREE_CODE (lhs) != SSA_NAME) 905 return false; 906 if (SSA_NAME_VAR (lhs) != NULL_TREE) 907 return false; 908 909 /* The temporary bool must be used exactly once: as the second arg of 910 a BIT_IOR_EXPR or BIT_AND_EXPR. */ 911 use_operand_p use_op; 912 gimple *use_stmt; 913 if (!single_imm_use (lhs, &use_op, &use_stmt)) 914 return false; 915 const gassign *use_assign = dyn_cast <const gassign *> (use_stmt); 916 if (!use_assign) 917 return false; 918 enum tree_code op = gimple_assign_rhs_code (use_assign); 919 if (!(op == BIT_IOR_EXPR ||op == BIT_AND_EXPR)) 920 return false; 921 if (!(gimple_assign_rhs1 (use_assign) != lhs 922 && gimple_assign_rhs2 (use_assign) == lhs)) 923 return false; 924 925 /* The first arg of the bitwise stmt must have a known value in MODEL 926 that implies that the value of the second arg doesn't matter, i.e. 927 1 for bitwise or, 0 for bitwise and. */ 928 tree other_arg = gimple_assign_rhs1 (use_assign); 929 /* Use a NULL ctxt here to avoid generating warnings. */ 930 const svalue *other_arg_sval = model->get_rvalue (other_arg, NULL); 931 tree other_arg_cst = other_arg_sval->maybe_get_constant (); 932 if (!other_arg_cst) 933 return false; 934 switch (op) 935 { 936 default: 937 gcc_unreachable (); 938 case BIT_IOR_EXPR: 939 if (zerop (other_arg_cst)) 940 return false; 941 break; 942 case BIT_AND_EXPR: 943 if (!zerop (other_arg_cst)) 944 return false; 945 break; 946 } 947 948 /* All tests passed. We appear to be in a stmt that generates a boolean 949 temporary with a value that won't matter. */ 950 return true; 951} 952 953/* Workaround for discarding certain false positives from 954 -Wanalyzer-use-of-uninitialized-value 955 seen with -ftrivial-auto-var-init=. 956 957 -ftrivial-auto-var-init= will generate calls to IFN_DEFERRED_INIT. 958 959 If the address of the var is taken, gimplification will give us 960 something like: 961 962 _1 = .DEFERRED_INIT (4, 2, &"len"[0]); 963 len = _1; 964 965 The result of DEFERRED_INIT will be an uninit value; we don't 966 want to emit a false positive for "len = _1;" 967 968 Return true if ASSIGN_STMT is such a stmt. */ 969 970static bool 971due_to_ifn_deferred_init_p (const gassign *assign_stmt) 972 973{ 974 /* We must have an assignment to a decl from an SSA name that's the 975 result of a IFN_DEFERRED_INIT call. */ 976 if (gimple_assign_rhs_code (assign_stmt) != SSA_NAME) 977 return false; 978 tree lhs = gimple_assign_lhs (assign_stmt); 979 if (TREE_CODE (lhs) != VAR_DECL) 980 return false; 981 tree rhs = gimple_assign_rhs1 (assign_stmt); 982 if (TREE_CODE (rhs) != SSA_NAME) 983 return false; 984 const gimple *def_stmt = SSA_NAME_DEF_STMT (rhs); 985 const gcall *call = dyn_cast <const gcall *> (def_stmt); 986 if (!call) 987 return false; 988 if (gimple_call_internal_p (call) 989 && gimple_call_internal_fn (call) == IFN_DEFERRED_INIT) 990 return true; 991 return false; 992} 993 994/* Check for SVAL being poisoned, adding a warning to CTXT. 995 Return SVAL, or, if a warning is added, another value, to avoid 996 repeatedly complaining about the same poisoned value in followup code. */ 997 998const svalue * 999region_model::check_for_poison (const svalue *sval, 1000 tree expr, 1001 region_model_context *ctxt) const 1002{ 1003 if (!ctxt) 1004 return sval; 1005 1006 if (const poisoned_svalue *poisoned_sval = sval->dyn_cast_poisoned_svalue ()) 1007 { 1008 enum poison_kind pkind = poisoned_sval->get_poison_kind (); 1009 1010 /* Ignore uninitialized uses of empty types; there's nothing 1011 to initialize. */ 1012 if (pkind == POISON_KIND_UNINIT 1013 && sval->get_type () 1014 && is_empty_type (sval->get_type ())) 1015 return sval; 1016 1017 if (pkind == POISON_KIND_UNINIT) 1018 if (const gimple *curr_stmt = ctxt->get_stmt ()) 1019 if (const gassign *assign_stmt 1020 = dyn_cast <const gassign *> (curr_stmt)) 1021 { 1022 /* Special case to avoid certain false positives. */ 1023 if (within_short_circuited_stmt_p (this, assign_stmt)) 1024 return sval; 1025 1026 /* Special case to avoid false positive on 1027 -ftrivial-auto-var-init=. */ 1028 if (due_to_ifn_deferred_init_p (assign_stmt)) 1029 return sval; 1030 } 1031 1032 /* If we have an SSA name for a temporary, we don't want to print 1033 '<unknown>'. 1034 Poisoned values are shared by type, and so we can't reconstruct 1035 the tree other than via the def stmts, using 1036 fixup_tree_for_diagnostic. */ 1037 tree diag_arg = fixup_tree_for_diagnostic (expr); 1038 const region *src_region = NULL; 1039 if (pkind == POISON_KIND_UNINIT) 1040 src_region = get_region_for_poisoned_expr (expr); 1041 if (ctxt->warn (new poisoned_value_diagnostic (diag_arg, pkind, 1042 src_region))) 1043 { 1044 /* We only want to report use of a poisoned value at the first 1045 place it gets used; return an unknown value to avoid generating 1046 a chain of followup warnings. */ 1047 sval = m_mgr->get_or_create_unknown_svalue (sval->get_type ()); 1048 } 1049 1050 return sval; 1051 } 1052 1053 return sval; 1054} 1055 1056/* Attempt to get a region for describing EXPR, the source of region of 1057 a poisoned_svalue for use in a poisoned_value_diagnostic. 1058 Return NULL if there is no good region to use. */ 1059 1060const region * 1061region_model::get_region_for_poisoned_expr (tree expr) const 1062{ 1063 if (TREE_CODE (expr) == SSA_NAME) 1064 { 1065 tree decl = SSA_NAME_VAR (expr); 1066 if (decl && DECL_P (decl)) 1067 expr = decl; 1068 else 1069 return NULL; 1070 } 1071 return get_lvalue (expr, NULL); 1072} 1073 1074/* Update this model for the ASSIGN stmt, using CTXT to report any 1075 diagnostics. */ 1076 1077void 1078region_model::on_assignment (const gassign *assign, region_model_context *ctxt) 1079{ 1080 tree lhs = gimple_assign_lhs (assign); 1081 tree rhs1 = gimple_assign_rhs1 (assign); 1082 1083 const region *lhs_reg = get_lvalue (lhs, ctxt); 1084 1085 /* Most assignments are handled by: 1086 set_value (lhs_reg, SVALUE, CTXT) 1087 for some SVALUE. */ 1088 if (const svalue *sval = get_gassign_result (assign, ctxt)) 1089 { 1090 tree expr = get_diagnostic_tree_for_gassign (assign); 1091 check_for_poison (sval, expr, ctxt); 1092 set_value (lhs_reg, sval, ctxt); 1093 return; 1094 } 1095 1096 enum tree_code op = gimple_assign_rhs_code (assign); 1097 switch (op) 1098 { 1099 default: 1100 { 1101 if (0) 1102 sorry_at (assign->location, "unhandled assignment op: %qs", 1103 get_tree_code_name (op)); 1104 const svalue *unknown_sval 1105 = m_mgr->get_or_create_unknown_svalue (TREE_TYPE (lhs)); 1106 set_value (lhs_reg, unknown_sval, ctxt); 1107 } 1108 break; 1109 1110 case CONSTRUCTOR: 1111 { 1112 if (TREE_CLOBBER_P (rhs1)) 1113 { 1114 /* e.g. "x ={v} {CLOBBER};" */ 1115 clobber_region (lhs_reg); 1116 } 1117 else 1118 { 1119 /* Any CONSTRUCTOR that survives to this point is either 1120 just a zero-init of everything, or a vector. */ 1121 if (!CONSTRUCTOR_NO_CLEARING (rhs1)) 1122 zero_fill_region (lhs_reg); 1123 unsigned ix; 1124 tree index; 1125 tree val; 1126 FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (rhs1), ix, index, val) 1127 { 1128 gcc_assert (TREE_CODE (TREE_TYPE (rhs1)) == VECTOR_TYPE); 1129 if (!index) 1130 index = build_int_cst (integer_type_node, ix); 1131 gcc_assert (TREE_CODE (index) == INTEGER_CST); 1132 const svalue *index_sval 1133 = m_mgr->get_or_create_constant_svalue (index); 1134 gcc_assert (index_sval); 1135 const region *sub_reg 1136 = m_mgr->get_element_region (lhs_reg, 1137 TREE_TYPE (val), 1138 index_sval); 1139 const svalue *val_sval = get_rvalue (val, ctxt); 1140 set_value (sub_reg, val_sval, ctxt); 1141 } 1142 } 1143 } 1144 break; 1145 1146 case STRING_CST: 1147 { 1148 /* e.g. "struct s2 x = {{'A', 'B', 'C', 'D'}};". */ 1149 const svalue *rhs_sval = get_rvalue (rhs1, ctxt); 1150 m_store.set_value (m_mgr->get_store_manager(), lhs_reg, rhs_sval, 1151 ctxt ? ctxt->get_uncertainty () : NULL); 1152 } 1153 break; 1154 } 1155} 1156 1157/* A pending_diagnostic subclass for implementing "__analyzer_dump_path". */ 1158 1159class dump_path_diagnostic 1160 : public pending_diagnostic_subclass<dump_path_diagnostic> 1161{ 1162public: 1163 int get_controlling_option () const FINAL OVERRIDE 1164 { 1165 return 0; 1166 } 1167 1168 bool emit (rich_location *richloc) FINAL OVERRIDE 1169 { 1170 inform (richloc, "path"); 1171 return true; 1172 } 1173 1174 const char *get_kind () const FINAL OVERRIDE { return "dump_path_diagnostic"; } 1175 1176 bool operator== (const dump_path_diagnostic &) const 1177 { 1178 return true; 1179 } 1180}; 1181 1182/* Handle the pre-sm-state part of STMT, modifying this object in-place. 1183 Write true to *OUT_TERMINATE_PATH if the path should be terminated. 1184 Write true to *OUT_UNKNOWN_SIDE_EFFECTS if the stmt has unknown 1185 side effects. */ 1186 1187void 1188region_model::on_stmt_pre (const gimple *stmt, 1189 bool *out_terminate_path, 1190 bool *out_unknown_side_effects, 1191 region_model_context *ctxt) 1192{ 1193 switch (gimple_code (stmt)) 1194 { 1195 default: 1196 /* No-op for now. */ 1197 break; 1198 1199 case GIMPLE_ASSIGN: 1200 { 1201 const gassign *assign = as_a <const gassign *> (stmt); 1202 on_assignment (assign, ctxt); 1203 } 1204 break; 1205 1206 case GIMPLE_ASM: 1207 { 1208 const gasm *asm_stmt = as_a <const gasm *> (stmt); 1209 on_asm_stmt (asm_stmt, ctxt); 1210 } 1211 break; 1212 1213 case GIMPLE_CALL: 1214 { 1215 /* Track whether we have a gcall to a function that's not recognized by 1216 anything, for which we don't have a function body, or for which we 1217 don't know the fndecl. */ 1218 const gcall *call = as_a <const gcall *> (stmt); 1219 1220 /* Debugging/test support. */ 1221 if (is_special_named_call_p (call, "__analyzer_describe", 2)) 1222 impl_call_analyzer_describe (call, ctxt); 1223 else if (is_special_named_call_p (call, "__analyzer_dump_capacity", 1)) 1224 impl_call_analyzer_dump_capacity (call, ctxt); 1225 else if (is_special_named_call_p (call, "__analyzer_dump_escaped", 0)) 1226 impl_call_analyzer_dump_escaped (call); 1227 else if (is_special_named_call_p (call, "__analyzer_dump_path", 0)) 1228 { 1229 /* Handle the builtin "__analyzer_dump_path" by queuing a 1230 diagnostic at this exploded_node. */ 1231 ctxt->warn (new dump_path_diagnostic ()); 1232 } 1233 else if (is_special_named_call_p (call, "__analyzer_dump_region_model", 1234 0)) 1235 { 1236 /* Handle the builtin "__analyzer_dump_region_model" by dumping 1237 the region model's state to stderr. */ 1238 dump (false); 1239 } 1240 else if (is_special_named_call_p (call, "__analyzer_eval", 1)) 1241 impl_call_analyzer_eval (call, ctxt); 1242 else if (is_special_named_call_p (call, "__analyzer_break", 0)) 1243 { 1244 /* Handle the builtin "__analyzer_break" by triggering a 1245 breakpoint. */ 1246 /* TODO: is there a good cross-platform way to do this? */ 1247 raise (SIGINT); 1248 } 1249 else if (is_special_named_call_p (call, 1250 "__analyzer_dump_exploded_nodes", 1251 1)) 1252 { 1253 /* This is handled elsewhere. */ 1254 } 1255 else 1256 *out_unknown_side_effects = on_call_pre (call, ctxt, 1257 out_terminate_path); 1258 } 1259 break; 1260 1261 case GIMPLE_RETURN: 1262 { 1263 const greturn *return_ = as_a <const greturn *> (stmt); 1264 on_return (return_, ctxt); 1265 } 1266 break; 1267 } 1268} 1269 1270/* Ensure that all arguments at the call described by CD are checked 1271 for poisoned values, by calling get_rvalue on each argument. */ 1272 1273void 1274region_model::check_call_args (const call_details &cd) const 1275{ 1276 for (unsigned arg_idx = 0; arg_idx < cd.num_args (); arg_idx++) 1277 cd.get_arg_svalue (arg_idx); 1278} 1279 1280/* Return true if CD is known to be a call to a function with 1281 __attribute__((const)). */ 1282 1283static bool 1284const_fn_p (const call_details &cd) 1285{ 1286 tree fndecl = cd.get_fndecl_for_call (); 1287 if (!fndecl) 1288 return false; 1289 gcc_assert (DECL_P (fndecl)); 1290 return TREE_READONLY (fndecl); 1291} 1292 1293/* If this CD is known to be a call to a function with 1294 __attribute__((const)), attempt to get a const_fn_result_svalue 1295 based on the arguments, or return NULL otherwise. */ 1296 1297static const svalue * 1298maybe_get_const_fn_result (const call_details &cd) 1299{ 1300 if (!const_fn_p (cd)) 1301 return NULL; 1302 1303 unsigned num_args = cd.num_args (); 1304 if (num_args > const_fn_result_svalue::MAX_INPUTS) 1305 /* Too many arguments. */ 1306 return NULL; 1307 1308 auto_vec<const svalue *> inputs (num_args); 1309 for (unsigned arg_idx = 0; arg_idx < num_args; arg_idx++) 1310 { 1311 const svalue *arg_sval = cd.get_arg_svalue (arg_idx); 1312 if (!arg_sval->can_have_associated_state_p ()) 1313 return NULL; 1314 inputs.quick_push (arg_sval); 1315 } 1316 1317 region_model_manager *mgr = cd.get_manager (); 1318 const svalue *sval 1319 = mgr->get_or_create_const_fn_result_svalue (cd.get_lhs_type (), 1320 cd.get_fndecl_for_call (), 1321 inputs); 1322 return sval; 1323} 1324 1325/* Update this model for the CALL stmt, using CTXT to report any 1326 diagnostics - the first half. 1327 1328 Updates to the region_model that should be made *before* sm-states 1329 are updated are done here; other updates to the region_model are done 1330 in region_model::on_call_post. 1331 1332 Return true if the function call has unknown side effects (it wasn't 1333 recognized and we don't have a body for it, or are unable to tell which 1334 fndecl it is). 1335 1336 Write true to *OUT_TERMINATE_PATH if this execution path should be 1337 terminated (e.g. the function call terminates the process). */ 1338 1339bool 1340region_model::on_call_pre (const gcall *call, region_model_context *ctxt, 1341 bool *out_terminate_path) 1342{ 1343 call_details cd (call, this, ctxt); 1344 1345 bool unknown_side_effects = false; 1346 1347 /* Special-case for IFN_DEFERRED_INIT. 1348 We want to report uninitialized variables with -fanalyzer (treating 1349 -ftrivial-auto-var-init= as purely a mitigation feature). 1350 Handle IFN_DEFERRED_INIT by treating it as no-op: don't touch the 1351 lhs of the call, so that it is still uninitialized from the point of 1352 view of the analyzer. */ 1353 if (gimple_call_internal_p (call) 1354 && gimple_call_internal_fn (call) == IFN_DEFERRED_INIT) 1355 return false; 1356 1357 /* Get svalues for all of the arguments at the callsite, to ensure that we 1358 complain about any uninitialized arguments. This might lead to 1359 duplicates if any of the handling below also looks up the svalues, 1360 but the deduplication code should deal with that. */ 1361 if (ctxt) 1362 check_call_args (cd); 1363 1364 /* Some of the cases below update the lhs of the call based on the 1365 return value, but not all. Provide a default value, which may 1366 get overwritten below. */ 1367 if (tree lhs = gimple_call_lhs (call)) 1368 { 1369 const region *lhs_region = get_lvalue (lhs, ctxt); 1370 const svalue *sval = maybe_get_const_fn_result (cd); 1371 if (!sval) 1372 { 1373 /* For the common case of functions without __attribute__((const)), 1374 use a conjured value, and purge any prior state involving that 1375 value (in case this is in a loop). */ 1376 sval = m_mgr->get_or_create_conjured_svalue (TREE_TYPE (lhs), call, 1377 lhs_region, 1378 conjured_purge (this, 1379 ctxt)); 1380 } 1381 set_value (lhs_region, sval, ctxt); 1382 } 1383 1384 if (gimple_call_internal_p (call)) 1385 { 1386 switch (gimple_call_internal_fn (call)) 1387 { 1388 default: 1389 break; 1390 case IFN_BUILTIN_EXPECT: 1391 impl_call_builtin_expect (cd); 1392 return false; 1393 case IFN_UBSAN_BOUNDS: 1394 return false; 1395 } 1396 } 1397 1398 if (tree callee_fndecl = get_fndecl_for_call (call, ctxt)) 1399 { 1400 /* The various impl_call_* member functions are implemented 1401 in region-model-impl-calls.cc. 1402 Having them split out into separate functions makes it easier 1403 to put breakpoints on the handling of specific functions. */ 1404 int callee_fndecl_flags = flags_from_decl_or_type (callee_fndecl); 1405 1406 if (fndecl_built_in_p (callee_fndecl, BUILT_IN_NORMAL) 1407 && gimple_builtin_call_types_compatible_p (call, callee_fndecl)) 1408 switch (DECL_UNCHECKED_FUNCTION_CODE (callee_fndecl)) 1409 { 1410 default: 1411 if (!(callee_fndecl_flags & (ECF_CONST | ECF_PURE))) 1412 unknown_side_effects = true; 1413 break; 1414 case BUILT_IN_ALLOCA: 1415 case BUILT_IN_ALLOCA_WITH_ALIGN: 1416 impl_call_alloca (cd); 1417 return false; 1418 case BUILT_IN_CALLOC: 1419 impl_call_calloc (cd); 1420 return false; 1421 case BUILT_IN_EXPECT: 1422 case BUILT_IN_EXPECT_WITH_PROBABILITY: 1423 impl_call_builtin_expect (cd); 1424 return false; 1425 case BUILT_IN_FREE: 1426 /* Handle in "on_call_post". */ 1427 break; 1428 case BUILT_IN_MALLOC: 1429 impl_call_malloc (cd); 1430 return false; 1431 case BUILT_IN_MEMCPY: 1432 case BUILT_IN_MEMCPY_CHK: 1433 impl_call_memcpy (cd); 1434 return false; 1435 case BUILT_IN_MEMSET: 1436 case BUILT_IN_MEMSET_CHK: 1437 impl_call_memset (cd); 1438 return false; 1439 break; 1440 case BUILT_IN_REALLOC: 1441 return false; 1442 case BUILT_IN_STRCHR: 1443 impl_call_strchr (cd); 1444 return false; 1445 case BUILT_IN_STRCPY: 1446 case BUILT_IN_STRCPY_CHK: 1447 impl_call_strcpy (cd); 1448 return false; 1449 case BUILT_IN_STRLEN: 1450 impl_call_strlen (cd); 1451 return false; 1452 1453 case BUILT_IN_STACK_SAVE: 1454 case BUILT_IN_STACK_RESTORE: 1455 return false; 1456 1457 /* Stdio builtins. */ 1458 case BUILT_IN_FPRINTF: 1459 case BUILT_IN_FPRINTF_UNLOCKED: 1460 case BUILT_IN_PUTC: 1461 case BUILT_IN_PUTC_UNLOCKED: 1462 case BUILT_IN_FPUTC: 1463 case BUILT_IN_FPUTC_UNLOCKED: 1464 case BUILT_IN_FPUTS: 1465 case BUILT_IN_FPUTS_UNLOCKED: 1466 case BUILT_IN_FWRITE: 1467 case BUILT_IN_FWRITE_UNLOCKED: 1468 case BUILT_IN_PRINTF: 1469 case BUILT_IN_PRINTF_UNLOCKED: 1470 case BUILT_IN_PUTCHAR: 1471 case BUILT_IN_PUTCHAR_UNLOCKED: 1472 case BUILT_IN_PUTS: 1473 case BUILT_IN_PUTS_UNLOCKED: 1474 case BUILT_IN_VFPRINTF: 1475 case BUILT_IN_VPRINTF: 1476 /* These stdio builtins have external effects that are out 1477 of scope for the analyzer: we only want to model the effects 1478 on the return value. */ 1479 break; 1480 } 1481 else if (is_named_call_p (callee_fndecl, "malloc", call, 1)) 1482 { 1483 impl_call_malloc (cd); 1484 return false; 1485 } 1486 else if (is_named_call_p (callee_fndecl, "calloc", call, 2)) 1487 { 1488 impl_call_calloc (cd); 1489 return false; 1490 } 1491 else if (is_named_call_p (callee_fndecl, "alloca", call, 1)) 1492 { 1493 impl_call_alloca (cd); 1494 return false; 1495 } 1496 else if (is_named_call_p (callee_fndecl, "realloc", call, 2)) 1497 { 1498 impl_call_realloc (cd); 1499 return false; 1500 } 1501 else if (is_named_call_p (callee_fndecl, "error")) 1502 { 1503 if (impl_call_error (cd, 3, out_terminate_path)) 1504 return false; 1505 else 1506 unknown_side_effects = true; 1507 } 1508 else if (is_named_call_p (callee_fndecl, "error_at_line")) 1509 { 1510 if (impl_call_error (cd, 5, out_terminate_path)) 1511 return false; 1512 else 1513 unknown_side_effects = true; 1514 } 1515 else if (is_named_call_p (callee_fndecl, "fgets", call, 3) 1516 || is_named_call_p (callee_fndecl, "fgets_unlocked", call, 3)) 1517 { 1518 impl_call_fgets (cd); 1519 return false; 1520 } 1521 else if (is_named_call_p (callee_fndecl, "fread", call, 4)) 1522 { 1523 impl_call_fread (cd); 1524 return false; 1525 } 1526 else if (is_named_call_p (callee_fndecl, "getchar", call, 0)) 1527 { 1528 /* No side-effects (tracking stream state is out-of-scope 1529 for the analyzer). */ 1530 } 1531 else if (is_named_call_p (callee_fndecl, "memset", call, 3) 1532 && POINTER_TYPE_P (cd.get_arg_type (0))) 1533 { 1534 impl_call_memset (cd); 1535 return false; 1536 } 1537 else if (is_named_call_p (callee_fndecl, "strchr", call, 2) 1538 && POINTER_TYPE_P (cd.get_arg_type (0))) 1539 { 1540 impl_call_strchr (cd); 1541 return false; 1542 } 1543 else if (is_named_call_p (callee_fndecl, "strlen", call, 1) 1544 && POINTER_TYPE_P (cd.get_arg_type (0))) 1545 { 1546 impl_call_strlen (cd); 1547 return false; 1548 } 1549 else if (is_named_call_p (callee_fndecl, "operator new", call, 1)) 1550 { 1551 impl_call_operator_new (cd); 1552 return false; 1553 } 1554 else if (is_named_call_p (callee_fndecl, "operator new []", call, 1)) 1555 { 1556 impl_call_operator_new (cd); 1557 return false; 1558 } 1559 else if (is_named_call_p (callee_fndecl, "operator delete", call, 1) 1560 || is_named_call_p (callee_fndecl, "operator delete", call, 2) 1561 || is_named_call_p (callee_fndecl, "operator delete []", call, 1)) 1562 { 1563 /* Handle in "on_call_post". */ 1564 } 1565 else if (!fndecl_has_gimple_body_p (callee_fndecl) 1566 && (!(callee_fndecl_flags & (ECF_CONST | ECF_PURE))) 1567 && !fndecl_built_in_p (callee_fndecl)) 1568 unknown_side_effects = true; 1569 } 1570 else 1571 unknown_side_effects = true; 1572 1573 return unknown_side_effects; 1574} 1575 1576/* Update this model for the CALL stmt, using CTXT to report any 1577 diagnostics - the second half. 1578 1579 Updates to the region_model that should be made *after* sm-states 1580 are updated are done here; other updates to the region_model are done 1581 in region_model::on_call_pre. 1582 1583 If UNKNOWN_SIDE_EFFECTS is true, also call handle_unrecognized_call 1584 to purge state. */ 1585 1586void 1587region_model::on_call_post (const gcall *call, 1588 bool unknown_side_effects, 1589 region_model_context *ctxt) 1590{ 1591 if (tree callee_fndecl = get_fndecl_for_call (call, ctxt)) 1592 { 1593 call_details cd (call, this, ctxt); 1594 if (is_named_call_p (callee_fndecl, "free", call, 1)) 1595 { 1596 impl_call_free (cd); 1597 return; 1598 } 1599 if (is_named_call_p (callee_fndecl, "operator delete", call, 1) 1600 || is_named_call_p (callee_fndecl, "operator delete", call, 2) 1601 || is_named_call_p (callee_fndecl, "operator delete []", call, 1)) 1602 { 1603 impl_call_operator_delete (cd); 1604 return; 1605 } 1606 /* Was this fndecl referenced by 1607 __attribute__((malloc(FOO)))? */ 1608 if (lookup_attribute ("*dealloc", DECL_ATTRIBUTES (callee_fndecl))) 1609 { 1610 impl_deallocation_call (cd); 1611 return; 1612 } 1613 if (fndecl_built_in_p (callee_fndecl, BUILT_IN_NORMAL) 1614 && gimple_builtin_call_types_compatible_p (call, callee_fndecl)) 1615 switch (DECL_UNCHECKED_FUNCTION_CODE (callee_fndecl)) 1616 { 1617 default: 1618 break; 1619 case BUILT_IN_REALLOC: 1620 impl_call_realloc (cd); 1621 return; 1622 } 1623 } 1624 1625 if (unknown_side_effects) 1626 handle_unrecognized_call (call, ctxt); 1627} 1628 1629/* Purge state involving SVAL from this region_model, using CTXT 1630 (if non-NULL) to purge other state in a program_state. 1631 1632 For example, if we're at the def-stmt of an SSA name, then we need to 1633 purge any state for svalues that involve that SSA name. This avoids 1634 false positives in loops, since a symbolic value referring to the 1635 SSA name will be referring to the previous value of that SSA name. 1636 1637 For example, in: 1638 while ((e = hashmap_iter_next(&iter))) { 1639 struct oid2strbuf *e_strbuf = (struct oid2strbuf *)e; 1640 free (e_strbuf->value); 1641 } 1642 at the def-stmt of e_8: 1643 e_8 = hashmap_iter_next (&iter); 1644 we should purge the "freed" state of: 1645 INIT_VAL(CAST_REG(���struct oid2strbuf���, (*INIT_VAL(e_8))).value) 1646 which is the "e_strbuf->value" value from the previous iteration, 1647 or we will erroneously report a double-free - the "e_8" within it 1648 refers to the previous value. */ 1649 1650void 1651region_model::purge_state_involving (const svalue *sval, 1652 region_model_context *ctxt) 1653{ 1654 if (!sval->can_have_associated_state_p ()) 1655 return; 1656 m_store.purge_state_involving (sval, m_mgr); 1657 m_constraints->purge_state_involving (sval); 1658 m_dynamic_extents.purge_state_involving (sval); 1659 if (ctxt) 1660 ctxt->purge_state_involving (sval); 1661} 1662 1663/* A pending_note subclass for adding a note about an 1664 __attribute__((access, ...)) to a diagnostic. */ 1665 1666class reason_attr_access : public pending_note_subclass<reason_attr_access> 1667{ 1668public: 1669 reason_attr_access (tree callee_fndecl, const attr_access &access) 1670 : m_callee_fndecl (callee_fndecl), 1671 m_ptr_argno (access.ptrarg), 1672 m_access_str (TREE_STRING_POINTER (access.to_external_string ())) 1673 { 1674 } 1675 1676 const char *get_kind () const FINAL OVERRIDE { return "reason_attr_access"; } 1677 1678 void emit () const 1679 { 1680 inform (DECL_SOURCE_LOCATION (m_callee_fndecl), 1681 "parameter %i of %qD marked with attribute %qs", 1682 m_ptr_argno + 1, m_callee_fndecl, m_access_str); 1683 } 1684 1685 bool operator== (const reason_attr_access &other) const 1686 { 1687 return (m_callee_fndecl == other.m_callee_fndecl 1688 && m_ptr_argno == other.m_ptr_argno 1689 && !strcmp (m_access_str, other.m_access_str)); 1690 } 1691 1692private: 1693 tree m_callee_fndecl; 1694 unsigned m_ptr_argno; 1695 const char *m_access_str; 1696}; 1697 1698/* Check CALL a call to external function CALLEE_FNDECL based on 1699 any __attribute__ ((access, ....) on the latter, complaining to 1700 CTXT about any issues. 1701 1702 Currently we merely call check_region_for_write on any regions 1703 pointed to by arguments marked with a "write_only" or "read_write" 1704 attribute. */ 1705 1706void 1707region_model:: 1708check_external_function_for_access_attr (const gcall *call, 1709 tree callee_fndecl, 1710 region_model_context *ctxt) const 1711{ 1712 gcc_assert (call); 1713 gcc_assert (callee_fndecl); 1714 gcc_assert (ctxt); 1715 1716 tree fntype = TREE_TYPE (callee_fndecl); 1717 if (!fntype) 1718 return; 1719 1720 if (!TYPE_ATTRIBUTES (fntype)) 1721 return; 1722 1723 /* Initialize a map of attribute access specifications for arguments 1724 to the function call. */ 1725 rdwr_map rdwr_idx; 1726 init_attr_rdwr_indices (&rdwr_idx, TYPE_ATTRIBUTES (fntype)); 1727 1728 unsigned argno = 0; 1729 1730 for (tree iter = TYPE_ARG_TYPES (fntype); iter; 1731 iter = TREE_CHAIN (iter), ++argno) 1732 { 1733 const attr_access* access = rdwr_idx.get (argno); 1734 if (!access) 1735 continue; 1736 1737 /* Ignore any duplicate entry in the map for the size argument. */ 1738 if (access->ptrarg != argno) 1739 continue; 1740 1741 if (access->mode == access_write_only 1742 || access->mode == access_read_write) 1743 { 1744 /* Subclass of decorated_region_model_context that 1745 adds a note about the attr access to any saved diagnostics. */ 1746 class annotating_ctxt : public note_adding_context 1747 { 1748 public: 1749 annotating_ctxt (tree callee_fndecl, 1750 const attr_access &access, 1751 region_model_context *ctxt) 1752 : note_adding_context (ctxt), 1753 m_callee_fndecl (callee_fndecl), 1754 m_access (access) 1755 { 1756 } 1757 pending_note *make_note () FINAL OVERRIDE 1758 { 1759 return new reason_attr_access (m_callee_fndecl, m_access); 1760 } 1761 private: 1762 tree m_callee_fndecl; 1763 const attr_access &m_access; 1764 }; 1765 1766 /* Use this ctxt below so that any diagnostics get the 1767 note added to them. */ 1768 annotating_ctxt my_ctxt (callee_fndecl, *access, ctxt); 1769 1770 tree ptr_tree = gimple_call_arg (call, access->ptrarg); 1771 const svalue *ptr_sval = get_rvalue (ptr_tree, &my_ctxt); 1772 const region *reg = deref_rvalue (ptr_sval, ptr_tree, &my_ctxt); 1773 check_region_for_write (reg, &my_ctxt); 1774 /* We don't use the size arg for now. */ 1775 } 1776 } 1777} 1778 1779/* Handle a call CALL to a function with unknown behavior. 1780 1781 Traverse the regions in this model, determining what regions are 1782 reachable from pointer arguments to CALL and from global variables, 1783 recursively. 1784 1785 Set all reachable regions to new unknown values and purge sm-state 1786 from their values, and from values that point to them. */ 1787 1788void 1789region_model::handle_unrecognized_call (const gcall *call, 1790 region_model_context *ctxt) 1791{ 1792 tree fndecl = get_fndecl_for_call (call, ctxt); 1793 1794 if (fndecl && ctxt) 1795 check_external_function_for_access_attr (call, fndecl, ctxt); 1796 1797 reachable_regions reachable_regs (this); 1798 1799 /* Determine the reachable regions and their mutability. */ 1800 { 1801 /* Add globals and regions that already escaped in previous 1802 unknown calls. */ 1803 m_store.for_each_cluster (reachable_regions::init_cluster_cb, 1804 &reachable_regs); 1805 1806 /* Params that are pointers. */ 1807 tree iter_param_types = NULL_TREE; 1808 if (fndecl) 1809 iter_param_types = TYPE_ARG_TYPES (TREE_TYPE (fndecl)); 1810 for (unsigned arg_idx = 0; arg_idx < gimple_call_num_args (call); arg_idx++) 1811 { 1812 /* Track expected param type, where available. */ 1813 tree param_type = NULL_TREE; 1814 if (iter_param_types) 1815 { 1816 param_type = TREE_VALUE (iter_param_types); 1817 gcc_assert (param_type); 1818 iter_param_types = TREE_CHAIN (iter_param_types); 1819 } 1820 1821 tree parm = gimple_call_arg (call, arg_idx); 1822 const svalue *parm_sval = get_rvalue (parm, ctxt); 1823 reachable_regs.handle_parm (parm_sval, param_type); 1824 } 1825 } 1826 1827 uncertainty_t *uncertainty = ctxt ? ctxt->get_uncertainty () : NULL; 1828 1829 /* Purge sm-state for the svalues that were reachable, 1830 both in non-mutable and mutable form. */ 1831 for (svalue_set::iterator iter 1832 = reachable_regs.begin_reachable_svals (); 1833 iter != reachable_regs.end_reachable_svals (); ++iter) 1834 { 1835 const svalue *sval = (*iter); 1836 if (ctxt) 1837 ctxt->on_unknown_change (sval, false); 1838 } 1839 for (svalue_set::iterator iter 1840 = reachable_regs.begin_mutable_svals (); 1841 iter != reachable_regs.end_mutable_svals (); ++iter) 1842 { 1843 const svalue *sval = (*iter); 1844 if (ctxt) 1845 ctxt->on_unknown_change (sval, true); 1846 if (uncertainty) 1847 uncertainty->on_mutable_sval_at_unknown_call (sval); 1848 } 1849 1850 /* Mark any clusters that have escaped. */ 1851 reachable_regs.mark_escaped_clusters (ctxt); 1852 1853 /* Update bindings for all clusters that have escaped, whether above, 1854 or previously. */ 1855 m_store.on_unknown_fncall (call, m_mgr->get_store_manager (), 1856 conjured_purge (this, ctxt)); 1857 1858 /* Purge dynamic extents from any regions that have escaped mutably: 1859 realloc could have been called on them. */ 1860 for (hash_set<const region *>::iterator 1861 iter = reachable_regs.begin_mutable_base_regs (); 1862 iter != reachable_regs.end_mutable_base_regs (); 1863 ++iter) 1864 { 1865 const region *base_reg = (*iter); 1866 unset_dynamic_extents (base_reg); 1867 } 1868} 1869 1870/* Traverse the regions in this model, determining what regions are 1871 reachable from the store and populating *OUT. 1872 1873 If EXTRA_SVAL is non-NULL, treat it as an additional "root" 1874 for reachability (for handling return values from functions when 1875 analyzing return of the only function on the stack). 1876 1877 If UNCERTAINTY is non-NULL, treat any svalues that were recorded 1878 within it as being maybe-bound as additional "roots" for reachability. 1879 1880 Find svalues that haven't leaked. */ 1881 1882void 1883region_model::get_reachable_svalues (svalue_set *out, 1884 const svalue *extra_sval, 1885 const uncertainty_t *uncertainty) 1886{ 1887 reachable_regions reachable_regs (this); 1888 1889 /* Add globals and regions that already escaped in previous 1890 unknown calls. */ 1891 m_store.for_each_cluster (reachable_regions::init_cluster_cb, 1892 &reachable_regs); 1893 1894 if (extra_sval) 1895 reachable_regs.handle_sval (extra_sval); 1896 1897 if (uncertainty) 1898 for (uncertainty_t::iterator iter 1899 = uncertainty->begin_maybe_bound_svals (); 1900 iter != uncertainty->end_maybe_bound_svals (); ++iter) 1901 reachable_regs.handle_sval (*iter); 1902 1903 /* Get regions for locals that have explicitly bound values. */ 1904 for (store::cluster_map_t::iterator iter = m_store.begin (); 1905 iter != m_store.end (); ++iter) 1906 { 1907 const region *base_reg = (*iter).first; 1908 if (const region *parent = base_reg->get_parent_region ()) 1909 if (parent->get_kind () == RK_FRAME) 1910 reachable_regs.add (base_reg, false); 1911 } 1912 1913 /* Populate *OUT based on the values that were reachable. */ 1914 for (svalue_set::iterator iter 1915 = reachable_regs.begin_reachable_svals (); 1916 iter != reachable_regs.end_reachable_svals (); ++iter) 1917 out->add (*iter); 1918} 1919 1920/* Update this model for the RETURN_STMT, using CTXT to report any 1921 diagnostics. */ 1922 1923void 1924region_model::on_return (const greturn *return_stmt, region_model_context *ctxt) 1925{ 1926 tree callee = get_current_function ()->decl; 1927 tree lhs = DECL_RESULT (callee); 1928 tree rhs = gimple_return_retval (return_stmt); 1929 1930 if (lhs && rhs) 1931 { 1932 const svalue *sval = get_rvalue (rhs, ctxt); 1933 const region *ret_reg = get_lvalue (lhs, ctxt); 1934 set_value (ret_reg, sval, ctxt); 1935 } 1936} 1937 1938/* Update this model for a call and return of setjmp/sigsetjmp at CALL within 1939 ENODE, using CTXT to report any diagnostics. 1940 1941 This is for the initial direct invocation of setjmp/sigsetjmp (which returns 1942 0), as opposed to any second return due to longjmp/sigsetjmp. */ 1943 1944void 1945region_model::on_setjmp (const gcall *call, const exploded_node *enode, 1946 region_model_context *ctxt) 1947{ 1948 const svalue *buf_ptr = get_rvalue (gimple_call_arg (call, 0), ctxt); 1949 const region *buf_reg = deref_rvalue (buf_ptr, gimple_call_arg (call, 0), 1950 ctxt); 1951 1952 /* Create a setjmp_svalue for this call and store it in BUF_REG's 1953 region. */ 1954 if (buf_reg) 1955 { 1956 setjmp_record r (enode, call); 1957 const svalue *sval 1958 = m_mgr->get_or_create_setjmp_svalue (r, buf_reg->get_type ()); 1959 set_value (buf_reg, sval, ctxt); 1960 } 1961 1962 /* Direct calls to setjmp return 0. */ 1963 if (tree lhs = gimple_call_lhs (call)) 1964 { 1965 const svalue *new_sval 1966 = m_mgr->get_or_create_int_cst (TREE_TYPE (lhs), 0); 1967 const region *lhs_reg = get_lvalue (lhs, ctxt); 1968 set_value (lhs_reg, new_sval, ctxt); 1969 } 1970} 1971 1972/* Update this region_model for rewinding from a "longjmp" at LONGJMP_CALL 1973 to a "setjmp" at SETJMP_CALL where the final stack depth should be 1974 SETJMP_STACK_DEPTH. Pop any stack frames. Leak detection is *not* 1975 done, and should be done by the caller. */ 1976 1977void 1978region_model::on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call, 1979 int setjmp_stack_depth, region_model_context *ctxt) 1980{ 1981 /* Evaluate the val, using the frame of the "longjmp". */ 1982 tree fake_retval = gimple_call_arg (longjmp_call, 1); 1983 const svalue *fake_retval_sval = get_rvalue (fake_retval, ctxt); 1984 1985 /* Pop any frames until we reach the stack depth of the function where 1986 setjmp was called. */ 1987 gcc_assert (get_stack_depth () >= setjmp_stack_depth); 1988 while (get_stack_depth () > setjmp_stack_depth) 1989 pop_frame (NULL, NULL, ctxt, false); 1990 1991 gcc_assert (get_stack_depth () == setjmp_stack_depth); 1992 1993 /* Assign to LHS of "setjmp" in new_state. */ 1994 if (tree lhs = gimple_call_lhs (setjmp_call)) 1995 { 1996 /* Passing 0 as the val to longjmp leads to setjmp returning 1. */ 1997 const svalue *zero_sval 1998 = m_mgr->get_or_create_int_cst (TREE_TYPE (fake_retval), 0); 1999 tristate eq_zero = eval_condition (fake_retval_sval, EQ_EXPR, zero_sval); 2000 /* If we have 0, use 1. */ 2001 if (eq_zero.is_true ()) 2002 { 2003 const svalue *one_sval 2004 = m_mgr->get_or_create_int_cst (TREE_TYPE (fake_retval), 1); 2005 fake_retval_sval = one_sval; 2006 } 2007 else 2008 { 2009 /* Otherwise note that the value is nonzero. */ 2010 m_constraints->add_constraint (fake_retval_sval, NE_EXPR, zero_sval); 2011 } 2012 2013 /* Decorate the return value from setjmp as being unmergeable, 2014 so that we don't attempt to merge states with it as zero 2015 with states in which it's nonzero, leading to a clean distinction 2016 in the exploded_graph betweeen the first return and the second 2017 return. */ 2018 fake_retval_sval = m_mgr->get_or_create_unmergeable (fake_retval_sval); 2019 2020 const region *lhs_reg = get_lvalue (lhs, ctxt); 2021 set_value (lhs_reg, fake_retval_sval, ctxt); 2022 } 2023} 2024 2025/* Update this region_model for a phi stmt of the form 2026 LHS = PHI <...RHS...>. 2027 where RHS is for the appropriate edge. 2028 Get state from OLD_STATE so that all of the phi stmts for a basic block 2029 are effectively handled simultaneously. */ 2030 2031void 2032region_model::handle_phi (const gphi *phi, 2033 tree lhs, tree rhs, 2034 const region_model &old_state, 2035 region_model_context *ctxt) 2036{ 2037 /* For now, don't bother tracking the .MEM SSA names. */ 2038 if (tree var = SSA_NAME_VAR (lhs)) 2039 if (TREE_CODE (var) == VAR_DECL) 2040 if (VAR_DECL_IS_VIRTUAL_OPERAND (var)) 2041 return; 2042 2043 const svalue *src_sval = old_state.get_rvalue (rhs, ctxt); 2044 const region *dst_reg = old_state.get_lvalue (lhs, ctxt); 2045 2046 set_value (dst_reg, src_sval, ctxt); 2047 2048 if (ctxt) 2049 ctxt->on_phi (phi, rhs); 2050} 2051 2052/* Implementation of region_model::get_lvalue; the latter adds type-checking. 2053 2054 Get the id of the region for PV within this region_model, 2055 emitting any diagnostics to CTXT. */ 2056 2057const region * 2058region_model::get_lvalue_1 (path_var pv, region_model_context *ctxt) const 2059{ 2060 tree expr = pv.m_tree; 2061 2062 gcc_assert (expr); 2063 2064 switch (TREE_CODE (expr)) 2065 { 2066 default: 2067 return m_mgr->get_region_for_unexpected_tree_code (ctxt, expr, 2068 dump_location_t ()); 2069 2070 case ARRAY_REF: 2071 { 2072 tree array = TREE_OPERAND (expr, 0); 2073 tree index = TREE_OPERAND (expr, 1); 2074 2075 const region *array_reg = get_lvalue (array, ctxt); 2076 const svalue *index_sval = get_rvalue (index, ctxt); 2077 return m_mgr->get_element_region (array_reg, 2078 TREE_TYPE (TREE_TYPE (array)), 2079 index_sval); 2080 } 2081 break; 2082 2083 case BIT_FIELD_REF: 2084 { 2085 tree inner_expr = TREE_OPERAND (expr, 0); 2086 const region *inner_reg = get_lvalue (inner_expr, ctxt); 2087 tree num_bits = TREE_OPERAND (expr, 1); 2088 tree first_bit_offset = TREE_OPERAND (expr, 2); 2089 gcc_assert (TREE_CODE (num_bits) == INTEGER_CST); 2090 gcc_assert (TREE_CODE (first_bit_offset) == INTEGER_CST); 2091 bit_range bits (TREE_INT_CST_LOW (first_bit_offset), 2092 TREE_INT_CST_LOW (num_bits)); 2093 return m_mgr->get_bit_range (inner_reg, TREE_TYPE (expr), bits); 2094 } 2095 break; 2096 2097 case MEM_REF: 2098 { 2099 tree ptr = TREE_OPERAND (expr, 0); 2100 tree offset = TREE_OPERAND (expr, 1); 2101 const svalue *ptr_sval = get_rvalue (ptr, ctxt); 2102 const svalue *offset_sval = get_rvalue (offset, ctxt); 2103 const region *star_ptr = deref_rvalue (ptr_sval, ptr, ctxt); 2104 return m_mgr->get_offset_region (star_ptr, 2105 TREE_TYPE (expr), 2106 offset_sval); 2107 } 2108 break; 2109 2110 case FUNCTION_DECL: 2111 return m_mgr->get_region_for_fndecl (expr); 2112 2113 case LABEL_DECL: 2114 return m_mgr->get_region_for_label (expr); 2115 2116 case VAR_DECL: 2117 /* Handle globals. */ 2118 if (is_global_var (expr)) 2119 return m_mgr->get_region_for_global (expr); 2120 2121 /* Fall through. */ 2122 2123 case SSA_NAME: 2124 case PARM_DECL: 2125 case RESULT_DECL: 2126 { 2127 gcc_assert (TREE_CODE (expr) == SSA_NAME 2128 || TREE_CODE (expr) == PARM_DECL 2129 || TREE_CODE (expr) == VAR_DECL 2130 || TREE_CODE (expr) == RESULT_DECL); 2131 2132 int stack_index = pv.m_stack_depth; 2133 const frame_region *frame = get_frame_at_index (stack_index); 2134 gcc_assert (frame); 2135 return frame->get_region_for_local (m_mgr, expr, ctxt); 2136 } 2137 2138 case COMPONENT_REF: 2139 { 2140 /* obj.field */ 2141 tree obj = TREE_OPERAND (expr, 0); 2142 tree field = TREE_OPERAND (expr, 1); 2143 const region *obj_reg = get_lvalue (obj, ctxt); 2144 return m_mgr->get_field_region (obj_reg, field); 2145 } 2146 break; 2147 2148 case STRING_CST: 2149 return m_mgr->get_region_for_string (expr); 2150 } 2151} 2152 2153/* Assert that SRC_TYPE can be converted to DST_TYPE as a no-op. */ 2154 2155static void 2156assert_compat_types (tree src_type, tree dst_type) 2157{ 2158 if (src_type && dst_type && !VOID_TYPE_P (dst_type)) 2159 { 2160#if CHECKING_P 2161 if (!(useless_type_conversion_p (src_type, dst_type))) 2162 internal_error ("incompatible types: %qT and %qT", src_type, dst_type); 2163#endif 2164 } 2165} 2166 2167/* Return true if SRC_TYPE can be converted to DST_TYPE as a no-op. */ 2168 2169bool 2170compat_types_p (tree src_type, tree dst_type) 2171{ 2172 if (src_type && dst_type && !VOID_TYPE_P (dst_type)) 2173 if (!(useless_type_conversion_p (src_type, dst_type))) 2174 return false; 2175 return true; 2176} 2177 2178/* Get the region for PV within this region_model, 2179 emitting any diagnostics to CTXT. */ 2180 2181const region * 2182region_model::get_lvalue (path_var pv, region_model_context *ctxt) const 2183{ 2184 if (pv.m_tree == NULL_TREE) 2185 return NULL; 2186 2187 const region *result_reg = get_lvalue_1 (pv, ctxt); 2188 assert_compat_types (result_reg->get_type (), TREE_TYPE (pv.m_tree)); 2189 return result_reg; 2190} 2191 2192/* Get the region for EXPR within this region_model (assuming the most 2193 recent stack frame if it's a local). */ 2194 2195const region * 2196region_model::get_lvalue (tree expr, region_model_context *ctxt) const 2197{ 2198 return get_lvalue (path_var (expr, get_stack_depth () - 1), ctxt); 2199} 2200 2201/* Implementation of region_model::get_rvalue; the latter adds type-checking. 2202 2203 Get the value of PV within this region_model, 2204 emitting any diagnostics to CTXT. */ 2205 2206const svalue * 2207region_model::get_rvalue_1 (path_var pv, region_model_context *ctxt) const 2208{ 2209 gcc_assert (pv.m_tree); 2210 2211 switch (TREE_CODE (pv.m_tree)) 2212 { 2213 default: 2214 return m_mgr->get_or_create_unknown_svalue (TREE_TYPE (pv.m_tree)); 2215 2216 case ADDR_EXPR: 2217 { 2218 /* "&EXPR". */ 2219 tree expr = pv.m_tree; 2220 tree op0 = TREE_OPERAND (expr, 0); 2221 const region *expr_reg = get_lvalue (op0, ctxt); 2222 return m_mgr->get_ptr_svalue (TREE_TYPE (expr), expr_reg); 2223 } 2224 break; 2225 2226 case BIT_FIELD_REF: 2227 { 2228 tree expr = pv.m_tree; 2229 tree op0 = TREE_OPERAND (expr, 0); 2230 const region *reg = get_lvalue (op0, ctxt); 2231 tree num_bits = TREE_OPERAND (expr, 1); 2232 tree first_bit_offset = TREE_OPERAND (expr, 2); 2233 gcc_assert (TREE_CODE (num_bits) == INTEGER_CST); 2234 gcc_assert (TREE_CODE (first_bit_offset) == INTEGER_CST); 2235 bit_range bits (TREE_INT_CST_LOW (first_bit_offset), 2236 TREE_INT_CST_LOW (num_bits)); 2237 return get_rvalue_for_bits (TREE_TYPE (expr), reg, bits, ctxt); 2238 } 2239 2240 case VAR_DECL: 2241 if (DECL_HARD_REGISTER (pv.m_tree)) 2242 { 2243 /* If it has a hard register, it doesn't have a memory region 2244 and can't be referred to as an lvalue. */ 2245 return m_mgr->get_or_create_unknown_svalue (TREE_TYPE (pv.m_tree)); 2246 } 2247 /* Fall through. */ 2248 case PARM_DECL: 2249 case SSA_NAME: 2250 case RESULT_DECL: 2251 case ARRAY_REF: 2252 { 2253 const region *reg = get_lvalue (pv, ctxt); 2254 return get_store_value (reg, ctxt); 2255 } 2256 2257 case REALPART_EXPR: 2258 case IMAGPART_EXPR: 2259 case VIEW_CONVERT_EXPR: 2260 { 2261 tree expr = pv.m_tree; 2262 tree arg = TREE_OPERAND (expr, 0); 2263 const svalue *arg_sval = get_rvalue (arg, ctxt); 2264 const svalue *sval_unaryop 2265 = m_mgr->get_or_create_unaryop (TREE_TYPE (expr), TREE_CODE (expr), 2266 arg_sval); 2267 return sval_unaryop; 2268 }; 2269 2270 case INTEGER_CST: 2271 case REAL_CST: 2272 case COMPLEX_CST: 2273 case VECTOR_CST: 2274 case STRING_CST: 2275 return m_mgr->get_or_create_constant_svalue (pv.m_tree); 2276 2277 case POINTER_PLUS_EXPR: 2278 { 2279 tree expr = pv.m_tree; 2280 tree ptr = TREE_OPERAND (expr, 0); 2281 tree offset = TREE_OPERAND (expr, 1); 2282 const svalue *ptr_sval = get_rvalue (ptr, ctxt); 2283 const svalue *offset_sval = get_rvalue (offset, ctxt); 2284 const svalue *sval_binop 2285 = m_mgr->get_or_create_binop (TREE_TYPE (expr), POINTER_PLUS_EXPR, 2286 ptr_sval, offset_sval); 2287 return sval_binop; 2288 } 2289 2290 /* Binary ops. */ 2291 case PLUS_EXPR: 2292 case MULT_EXPR: 2293 { 2294 tree expr = pv.m_tree; 2295 tree arg0 = TREE_OPERAND (expr, 0); 2296 tree arg1 = TREE_OPERAND (expr, 1); 2297 const svalue *arg0_sval = get_rvalue (arg0, ctxt); 2298 const svalue *arg1_sval = get_rvalue (arg1, ctxt); 2299 const svalue *sval_binop 2300 = m_mgr->get_or_create_binop (TREE_TYPE (expr), TREE_CODE (expr), 2301 arg0_sval, arg1_sval); 2302 return sval_binop; 2303 } 2304 2305 case COMPONENT_REF: 2306 case MEM_REF: 2307 { 2308 const region *ref_reg = get_lvalue (pv, ctxt); 2309 return get_store_value (ref_reg, ctxt); 2310 } 2311 case OBJ_TYPE_REF: 2312 { 2313 tree expr = OBJ_TYPE_REF_EXPR (pv.m_tree); 2314 return get_rvalue (expr, ctxt); 2315 } 2316 } 2317} 2318 2319/* Get the value of PV within this region_model, 2320 emitting any diagnostics to CTXT. */ 2321 2322const svalue * 2323region_model::get_rvalue (path_var pv, region_model_context *ctxt) const 2324{ 2325 if (pv.m_tree == NULL_TREE) 2326 return NULL; 2327 2328 const svalue *result_sval = get_rvalue_1 (pv, ctxt); 2329 2330 assert_compat_types (result_sval->get_type (), TREE_TYPE (pv.m_tree)); 2331 2332 result_sval = check_for_poison (result_sval, pv.m_tree, ctxt); 2333 2334 return result_sval; 2335} 2336 2337/* Get the value of EXPR within this region_model (assuming the most 2338 recent stack frame if it's a local). */ 2339 2340const svalue * 2341region_model::get_rvalue (tree expr, region_model_context *ctxt) const 2342{ 2343 return get_rvalue (path_var (expr, get_stack_depth () - 1), ctxt); 2344} 2345 2346/* Return true if this model is on a path with "main" as the entrypoint 2347 (as opposed to one in which we're merely analyzing a subset of the 2348 path through the code). */ 2349 2350bool 2351region_model::called_from_main_p () const 2352{ 2353 if (!m_current_frame) 2354 return false; 2355 /* Determine if the oldest stack frame in this model is for "main". */ 2356 const frame_region *frame0 = get_frame_at_index (0); 2357 gcc_assert (frame0); 2358 return id_equal (DECL_NAME (frame0->get_function ()->decl), "main"); 2359} 2360 2361/* Subroutine of region_model::get_store_value for when REG is (or is within) 2362 a global variable that hasn't been touched since the start of this path 2363 (or was implicitly touched due to a call to an unknown function). */ 2364 2365const svalue * 2366region_model::get_initial_value_for_global (const region *reg) const 2367{ 2368 /* Get the decl that REG is for (or is within). */ 2369 const decl_region *base_reg 2370 = reg->get_base_region ()->dyn_cast_decl_region (); 2371 gcc_assert (base_reg); 2372 tree decl = base_reg->get_decl (); 2373 2374 /* Special-case: to avoid having to explicitly update all previously 2375 untracked globals when calling an unknown fn, they implicitly have 2376 an unknown value if an unknown call has occurred, unless this is 2377 static to-this-TU and hasn't escaped. Globals that have escaped 2378 are explicitly tracked, so we shouldn't hit this case for them. */ 2379 if (m_store.called_unknown_fn_p () 2380 && TREE_PUBLIC (decl) 2381 && !TREE_READONLY (decl)) 2382 return m_mgr->get_or_create_unknown_svalue (reg->get_type ()); 2383 2384 /* If we are on a path from the entrypoint from "main" and we have a 2385 global decl defined in this TU that hasn't been touched yet, then 2386 the initial value of REG can be taken from the initialization value 2387 of the decl. */ 2388 if (called_from_main_p () || TREE_READONLY (decl)) 2389 { 2390 /* Attempt to get the initializer value for base_reg. */ 2391 if (const svalue *base_reg_init 2392 = base_reg->get_svalue_for_initializer (m_mgr)) 2393 { 2394 if (reg == base_reg) 2395 return base_reg_init; 2396 else 2397 { 2398 /* Get the value for REG within base_reg_init. */ 2399 binding_cluster c (base_reg); 2400 c.bind (m_mgr->get_store_manager (), base_reg, base_reg_init); 2401 const svalue *sval 2402 = c.get_any_binding (m_mgr->get_store_manager (), reg); 2403 if (sval) 2404 { 2405 if (reg->get_type ()) 2406 sval = m_mgr->get_or_create_cast (reg->get_type (), 2407 sval); 2408 return sval; 2409 } 2410 } 2411 } 2412 } 2413 2414 /* Otherwise, return INIT_VAL(REG). */ 2415 return m_mgr->get_or_create_initial_value (reg); 2416} 2417 2418/* Get a value for REG, looking it up in the store, or otherwise falling 2419 back to "initial" or "unknown" values. 2420 Use CTXT to report any warnings associated with reading from REG. */ 2421 2422const svalue * 2423region_model::get_store_value (const region *reg, 2424 region_model_context *ctxt) const 2425{ 2426 check_region_for_read (reg, ctxt); 2427 2428 /* Special-case: handle var_decls in the constant pool. */ 2429 if (const decl_region *decl_reg = reg->dyn_cast_decl_region ()) 2430 if (const svalue *sval = decl_reg->maybe_get_constant_value (m_mgr)) 2431 return sval; 2432 2433 const svalue *sval 2434 = m_store.get_any_binding (m_mgr->get_store_manager (), reg); 2435 if (sval) 2436 { 2437 if (reg->get_type ()) 2438 sval = m_mgr->get_or_create_cast (reg->get_type (), sval); 2439 return sval; 2440 } 2441 2442 /* Special-case: read at a constant index within a STRING_CST. */ 2443 if (const offset_region *offset_reg = reg->dyn_cast_offset_region ()) 2444 if (tree byte_offset_cst 2445 = offset_reg->get_byte_offset ()->maybe_get_constant ()) 2446 if (const string_region *str_reg 2447 = reg->get_parent_region ()->dyn_cast_string_region ()) 2448 { 2449 tree string_cst = str_reg->get_string_cst (); 2450 if (const svalue *char_sval 2451 = m_mgr->maybe_get_char_from_string_cst (string_cst, 2452 byte_offset_cst)) 2453 return m_mgr->get_or_create_cast (reg->get_type (), char_sval); 2454 } 2455 2456 /* Special-case: read the initial char of a STRING_CST. */ 2457 if (const cast_region *cast_reg = reg->dyn_cast_cast_region ()) 2458 if (const string_region *str_reg 2459 = cast_reg->get_original_region ()->dyn_cast_string_region ()) 2460 { 2461 tree string_cst = str_reg->get_string_cst (); 2462 tree byte_offset_cst = build_int_cst (integer_type_node, 0); 2463 if (const svalue *char_sval 2464 = m_mgr->maybe_get_char_from_string_cst (string_cst, 2465 byte_offset_cst)) 2466 return m_mgr->get_or_create_cast (reg->get_type (), char_sval); 2467 } 2468 2469 /* Otherwise we implicitly have the initial value of the region 2470 (if the cluster had been touched, binding_cluster::get_any_binding, 2471 would have returned UNKNOWN, and we would already have returned 2472 that above). */ 2473 2474 /* Handle globals. */ 2475 if (reg->get_base_region ()->get_parent_region ()->get_kind () 2476 == RK_GLOBALS) 2477 return get_initial_value_for_global (reg); 2478 2479 return m_mgr->get_or_create_initial_value (reg); 2480} 2481 2482/* Return false if REG does not exist, true if it may do. 2483 This is for detecting regions within the stack that don't exist anymore 2484 after frames are popped. */ 2485 2486bool 2487region_model::region_exists_p (const region *reg) const 2488{ 2489 /* If within a stack frame, check that the stack frame is live. */ 2490 if (const frame_region *enclosing_frame = reg->maybe_get_frame_region ()) 2491 { 2492 /* Check that the current frame is the enclosing frame, or is called 2493 by it. */ 2494 for (const frame_region *iter_frame = get_current_frame (); iter_frame; 2495 iter_frame = iter_frame->get_calling_frame ()) 2496 if (iter_frame == enclosing_frame) 2497 return true; 2498 return false; 2499 } 2500 2501 return true; 2502} 2503 2504/* Get a region for referencing PTR_SVAL, creating a region if need be, and 2505 potentially generating warnings via CTXT. 2506 PTR_SVAL must be of pointer type. 2507 PTR_TREE if non-NULL can be used when emitting diagnostics. */ 2508 2509const region * 2510region_model::deref_rvalue (const svalue *ptr_sval, tree ptr_tree, 2511 region_model_context *ctxt) const 2512{ 2513 gcc_assert (ptr_sval); 2514 gcc_assert (POINTER_TYPE_P (ptr_sval->get_type ())); 2515 2516 /* If we're dereferencing PTR_SVAL, assume that it is non-NULL; add this 2517 as a constraint. This suppresses false positives from 2518 -Wanalyzer-null-dereference for the case where we later have an 2519 if (PTR_SVAL) that would occur if we considered the false branch 2520 and transitioned the malloc state machine from start->null. */ 2521 tree null_ptr_cst = build_int_cst (ptr_sval->get_type (), 0); 2522 const svalue *null_ptr = m_mgr->get_or_create_constant_svalue (null_ptr_cst); 2523 m_constraints->add_constraint (ptr_sval, NE_EXPR, null_ptr); 2524 2525 switch (ptr_sval->get_kind ()) 2526 { 2527 default: 2528 break; 2529 2530 case SK_REGION: 2531 { 2532 const region_svalue *region_sval 2533 = as_a <const region_svalue *> (ptr_sval); 2534 return region_sval->get_pointee (); 2535 } 2536 2537 case SK_BINOP: 2538 { 2539 const binop_svalue *binop_sval 2540 = as_a <const binop_svalue *> (ptr_sval); 2541 switch (binop_sval->get_op ()) 2542 { 2543 case POINTER_PLUS_EXPR: 2544 { 2545 /* If we have a symbolic value expressing pointer arithmentic, 2546 try to convert it to a suitable region. */ 2547 const region *parent_region 2548 = deref_rvalue (binop_sval->get_arg0 (), NULL_TREE, ctxt); 2549 const svalue *offset = binop_sval->get_arg1 (); 2550 tree type= TREE_TYPE (ptr_sval->get_type ()); 2551 return m_mgr->get_offset_region (parent_region, type, offset); 2552 } 2553 default: 2554 break; 2555 } 2556 } 2557 break; 2558 2559 case SK_POISONED: 2560 { 2561 if (ctxt) 2562 { 2563 tree ptr = get_representative_tree (ptr_sval); 2564 /* If we can't get a representative tree for PTR_SVAL 2565 (e.g. if it hasn't been bound into the store), then 2566 fall back on PTR_TREE, if non-NULL. */ 2567 if (!ptr) 2568 ptr = ptr_tree; 2569 if (ptr) 2570 { 2571 const poisoned_svalue *poisoned_sval 2572 = as_a <const poisoned_svalue *> (ptr_sval); 2573 enum poison_kind pkind = poisoned_sval->get_poison_kind (); 2574 ctxt->warn (new poisoned_value_diagnostic (ptr, pkind, NULL)); 2575 } 2576 } 2577 } 2578 break; 2579 } 2580 2581 return m_mgr->get_symbolic_region (ptr_sval); 2582} 2583 2584/* Attempt to get BITS within any value of REG, as TYPE. 2585 In particular, extract values from compound_svalues for the case 2586 where there's a concrete binding at BITS. 2587 Return an unknown svalue if we can't handle the given case. 2588 Use CTXT to report any warnings associated with reading from REG. */ 2589 2590const svalue * 2591region_model::get_rvalue_for_bits (tree type, 2592 const region *reg, 2593 const bit_range &bits, 2594 region_model_context *ctxt) const 2595{ 2596 const svalue *sval = get_store_value (reg, ctxt); 2597 return m_mgr->get_or_create_bits_within (type, bits, sval); 2598} 2599 2600/* A subclass of pending_diagnostic for complaining about writes to 2601 constant regions of memory. */ 2602 2603class write_to_const_diagnostic 2604: public pending_diagnostic_subclass<write_to_const_diagnostic> 2605{ 2606public: 2607 write_to_const_diagnostic (const region *reg, tree decl) 2608 : m_reg (reg), m_decl (decl) 2609 {} 2610 2611 const char *get_kind () const FINAL OVERRIDE 2612 { 2613 return "write_to_const_diagnostic"; 2614 } 2615 2616 bool operator== (const write_to_const_diagnostic &other) const 2617 { 2618 return (m_reg == other.m_reg 2619 && m_decl == other.m_decl); 2620 } 2621 2622 int get_controlling_option () const FINAL OVERRIDE 2623 { 2624 return OPT_Wanalyzer_write_to_const; 2625 } 2626 2627 bool emit (rich_location *rich_loc) FINAL OVERRIDE 2628 { 2629 auto_diagnostic_group d; 2630 bool warned; 2631 switch (m_reg->get_kind ()) 2632 { 2633 default: 2634 warned = warning_at (rich_loc, get_controlling_option (), 2635 "write to %<const%> object %qE", m_decl); 2636 break; 2637 case RK_FUNCTION: 2638 warned = warning_at (rich_loc, get_controlling_option (), 2639 "write to function %qE", m_decl); 2640 break; 2641 case RK_LABEL: 2642 warned = warning_at (rich_loc, get_controlling_option (), 2643 "write to label %qE", m_decl); 2644 break; 2645 } 2646 if (warned) 2647 inform (DECL_SOURCE_LOCATION (m_decl), "declared here"); 2648 return warned; 2649 } 2650 2651 label_text describe_final_event (const evdesc::final_event &ev) FINAL OVERRIDE 2652 { 2653 switch (m_reg->get_kind ()) 2654 { 2655 default: 2656 return ev.formatted_print ("write to %<const%> object %qE here", m_decl); 2657 case RK_FUNCTION: 2658 return ev.formatted_print ("write to function %qE here", m_decl); 2659 case RK_LABEL: 2660 return ev.formatted_print ("write to label %qE here", m_decl); 2661 } 2662 } 2663 2664private: 2665 const region *m_reg; 2666 tree m_decl; 2667}; 2668 2669/* A subclass of pending_diagnostic for complaining about writes to 2670 string literals. */ 2671 2672class write_to_string_literal_diagnostic 2673: public pending_diagnostic_subclass<write_to_string_literal_diagnostic> 2674{ 2675public: 2676 write_to_string_literal_diagnostic (const region *reg) 2677 : m_reg (reg) 2678 {} 2679 2680 const char *get_kind () const FINAL OVERRIDE 2681 { 2682 return "write_to_string_literal_diagnostic"; 2683 } 2684 2685 bool operator== (const write_to_string_literal_diagnostic &other) const 2686 { 2687 return m_reg == other.m_reg; 2688 } 2689 2690 int get_controlling_option () const FINAL OVERRIDE 2691 { 2692 return OPT_Wanalyzer_write_to_string_literal; 2693 } 2694 2695 bool emit (rich_location *rich_loc) FINAL OVERRIDE 2696 { 2697 return warning_at (rich_loc, get_controlling_option (), 2698 "write to string literal"); 2699 /* Ideally we would show the location of the STRING_CST as well, 2700 but it is not available at this point. */ 2701 } 2702 2703 label_text describe_final_event (const evdesc::final_event &ev) FINAL OVERRIDE 2704 { 2705 return ev.formatted_print ("write to string literal here"); 2706 } 2707 2708private: 2709 const region *m_reg; 2710}; 2711 2712/* Use CTXT to warn If DEST_REG is a region that shouldn't be written to. */ 2713 2714void 2715region_model::check_for_writable_region (const region* dest_reg, 2716 region_model_context *ctxt) const 2717{ 2718 /* Fail gracefully if CTXT is NULL. */ 2719 if (!ctxt) 2720 return; 2721 2722 const region *base_reg = dest_reg->get_base_region (); 2723 switch (base_reg->get_kind ()) 2724 { 2725 default: 2726 break; 2727 case RK_FUNCTION: 2728 { 2729 const function_region *func_reg = as_a <const function_region *> (base_reg); 2730 tree fndecl = func_reg->get_fndecl (); 2731 ctxt->warn (new write_to_const_diagnostic (func_reg, fndecl)); 2732 } 2733 break; 2734 case RK_LABEL: 2735 { 2736 const label_region *label_reg = as_a <const label_region *> (base_reg); 2737 tree label = label_reg->get_label (); 2738 ctxt->warn (new write_to_const_diagnostic (label_reg, label)); 2739 } 2740 break; 2741 case RK_DECL: 2742 { 2743 const decl_region *decl_reg = as_a <const decl_region *> (base_reg); 2744 tree decl = decl_reg->get_decl (); 2745 /* Warn about writes to const globals. 2746 Don't warn for writes to const locals, and params in particular, 2747 since we would warn in push_frame when setting them up (e.g the 2748 "this" param is "T* const"). */ 2749 if (TREE_READONLY (decl) 2750 && is_global_var (decl)) 2751 ctxt->warn (new write_to_const_diagnostic (dest_reg, decl)); 2752 } 2753 break; 2754 case RK_STRING: 2755 ctxt->warn (new write_to_string_literal_diagnostic (dest_reg)); 2756 break; 2757 } 2758} 2759 2760/* Get the capacity of REG in bytes. */ 2761 2762const svalue * 2763region_model::get_capacity (const region *reg) const 2764{ 2765 switch (reg->get_kind ()) 2766 { 2767 default: 2768 break; 2769 case RK_DECL: 2770 { 2771 const decl_region *decl_reg = as_a <const decl_region *> (reg); 2772 tree decl = decl_reg->get_decl (); 2773 if (TREE_CODE (decl) == SSA_NAME) 2774 { 2775 tree type = TREE_TYPE (decl); 2776 tree size = TYPE_SIZE (type); 2777 return get_rvalue (size, NULL); 2778 } 2779 else 2780 { 2781 tree size = decl_init_size (decl, false); 2782 if (size) 2783 return get_rvalue (size, NULL); 2784 } 2785 } 2786 break; 2787 case RK_SIZED: 2788 /* Look through sized regions to get at the capacity 2789 of the underlying regions. */ 2790 return get_capacity (reg->get_parent_region ()); 2791 } 2792 2793 if (const svalue *recorded = get_dynamic_extents (reg)) 2794 return recorded; 2795 2796 return m_mgr->get_or_create_unknown_svalue (sizetype); 2797} 2798 2799/* If CTXT is non-NULL, use it to warn about any problems accessing REG, 2800 using DIR to determine if this access is a read or write. */ 2801 2802void 2803region_model::check_region_access (const region *reg, 2804 enum access_direction dir, 2805 region_model_context *ctxt) const 2806{ 2807 /* Fail gracefully if CTXT is NULL. */ 2808 if (!ctxt) 2809 return; 2810 2811 check_region_for_taint (reg, dir, ctxt); 2812 2813 switch (dir) 2814 { 2815 default: 2816 gcc_unreachable (); 2817 case DIR_READ: 2818 /* Currently a no-op. */ 2819 break; 2820 case DIR_WRITE: 2821 check_for_writable_region (reg, ctxt); 2822 break; 2823 } 2824} 2825 2826/* If CTXT is non-NULL, use it to warn about any problems writing to REG. */ 2827 2828void 2829region_model::check_region_for_write (const region *dest_reg, 2830 region_model_context *ctxt) const 2831{ 2832 check_region_access (dest_reg, DIR_WRITE, ctxt); 2833} 2834 2835/* If CTXT is non-NULL, use it to warn about any problems reading from REG. */ 2836 2837void 2838region_model::check_region_for_read (const region *src_reg, 2839 region_model_context *ctxt) const 2840{ 2841 check_region_access (src_reg, DIR_READ, ctxt); 2842} 2843 2844/* Set the value of the region given by LHS_REG to the value given 2845 by RHS_SVAL. 2846 Use CTXT to report any warnings associated with writing to LHS_REG. */ 2847 2848void 2849region_model::set_value (const region *lhs_reg, const svalue *rhs_sval, 2850 region_model_context *ctxt) 2851{ 2852 gcc_assert (lhs_reg); 2853 gcc_assert (rhs_sval); 2854 2855 check_region_for_write (lhs_reg, ctxt); 2856 2857 m_store.set_value (m_mgr->get_store_manager(), lhs_reg, rhs_sval, 2858 ctxt ? ctxt->get_uncertainty () : NULL); 2859} 2860 2861/* Set the value of the region given by LHS to the value given by RHS. */ 2862 2863void 2864region_model::set_value (tree lhs, tree rhs, region_model_context *ctxt) 2865{ 2866 const region *lhs_reg = get_lvalue (lhs, ctxt); 2867 const svalue *rhs_sval = get_rvalue (rhs, ctxt); 2868 gcc_assert (lhs_reg); 2869 gcc_assert (rhs_sval); 2870 set_value (lhs_reg, rhs_sval, ctxt); 2871} 2872 2873/* Remove all bindings overlapping REG within the store. */ 2874 2875void 2876region_model::clobber_region (const region *reg) 2877{ 2878 m_store.clobber_region (m_mgr->get_store_manager(), reg); 2879} 2880 2881/* Remove any bindings for REG within the store. */ 2882 2883void 2884region_model::purge_region (const region *reg) 2885{ 2886 m_store.purge_region (m_mgr->get_store_manager(), reg); 2887} 2888 2889/* Fill REG with SVAL. */ 2890 2891void 2892region_model::fill_region (const region *reg, const svalue *sval) 2893{ 2894 m_store.fill_region (m_mgr->get_store_manager(), reg, sval); 2895} 2896 2897/* Zero-fill REG. */ 2898 2899void 2900region_model::zero_fill_region (const region *reg) 2901{ 2902 m_store.zero_fill_region (m_mgr->get_store_manager(), reg); 2903} 2904 2905/* Mark REG as having unknown content. */ 2906 2907void 2908region_model::mark_region_as_unknown (const region *reg, 2909 uncertainty_t *uncertainty) 2910{ 2911 m_store.mark_region_as_unknown (m_mgr->get_store_manager(), reg, 2912 uncertainty); 2913} 2914 2915/* Determine what is known about the condition "LHS_SVAL OP RHS_SVAL" within 2916 this model. */ 2917 2918tristate 2919region_model::eval_condition (const svalue *lhs, 2920 enum tree_code op, 2921 const svalue *rhs) const 2922{ 2923 /* For now, make no attempt to capture constraints on floating-point 2924 values. */ 2925 if ((lhs->get_type () && FLOAT_TYPE_P (lhs->get_type ())) 2926 || (rhs->get_type () && FLOAT_TYPE_P (rhs->get_type ()))) 2927 return tristate::unknown (); 2928 2929 tristate ts = eval_condition_without_cm (lhs, op, rhs); 2930 if (ts.is_known ()) 2931 return ts; 2932 2933 /* Otherwise, try constraints. */ 2934 return m_constraints->eval_condition (lhs, op, rhs); 2935} 2936 2937/* Determine what is known about the condition "LHS_SVAL OP RHS_SVAL" within 2938 this model, without resorting to the constraint_manager. 2939 2940 This is exposed so that impl_region_model_context::on_state_leak can 2941 check for equality part-way through region_model::purge_unused_svalues 2942 without risking creating new ECs. */ 2943 2944tristate 2945region_model::eval_condition_without_cm (const svalue *lhs, 2946 enum tree_code op, 2947 const svalue *rhs) const 2948{ 2949 gcc_assert (lhs); 2950 gcc_assert (rhs); 2951 2952 /* See what we know based on the values. */ 2953 2954 /* For now, make no attempt to capture constraints on floating-point 2955 values. */ 2956 if ((lhs->get_type () && FLOAT_TYPE_P (lhs->get_type ())) 2957 || (rhs->get_type () && FLOAT_TYPE_P (rhs->get_type ()))) 2958 return tristate::unknown (); 2959 2960 /* Unwrap any unmergeable values. */ 2961 lhs = lhs->unwrap_any_unmergeable (); 2962 rhs = rhs->unwrap_any_unmergeable (); 2963 2964 if (lhs == rhs) 2965 { 2966 /* If we have the same svalue, then we have equality 2967 (apart from NaN-handling). 2968 TODO: should this definitely be the case for poisoned values? */ 2969 /* Poisoned and unknown values are "unknowable". */ 2970 if (lhs->get_kind () == SK_POISONED 2971 || lhs->get_kind () == SK_UNKNOWN) 2972 return tristate::TS_UNKNOWN; 2973 2974 switch (op) 2975 { 2976 case EQ_EXPR: 2977 case GE_EXPR: 2978 case LE_EXPR: 2979 return tristate::TS_TRUE; 2980 2981 case NE_EXPR: 2982 case GT_EXPR: 2983 case LT_EXPR: 2984 return tristate::TS_FALSE; 2985 2986 default: 2987 /* For other ops, use the logic below. */ 2988 break; 2989 } 2990 } 2991 2992 /* If we have a pair of region_svalues, compare them. */ 2993 if (const region_svalue *lhs_ptr = lhs->dyn_cast_region_svalue ()) 2994 if (const region_svalue *rhs_ptr = rhs->dyn_cast_region_svalue ()) 2995 { 2996 tristate res = region_svalue::eval_condition (lhs_ptr, op, rhs_ptr); 2997 if (res.is_known ()) 2998 return res; 2999 /* Otherwise, only known through constraints. */ 3000 } 3001 3002 if (const constant_svalue *cst_lhs = lhs->dyn_cast_constant_svalue ()) 3003 { 3004 /* If we have a pair of constants, compare them. */ 3005 if (const constant_svalue *cst_rhs = rhs->dyn_cast_constant_svalue ()) 3006 return constant_svalue::eval_condition (cst_lhs, op, cst_rhs); 3007 else 3008 { 3009 /* When we have one constant, put it on the RHS. */ 3010 std::swap (lhs, rhs); 3011 op = swap_tree_comparison (op); 3012 } 3013 } 3014 gcc_assert (lhs->get_kind () != SK_CONSTANT); 3015 3016 /* Handle comparison against zero. */ 3017 if (const constant_svalue *cst_rhs = rhs->dyn_cast_constant_svalue ()) 3018 if (zerop (cst_rhs->get_constant ())) 3019 { 3020 if (const region_svalue *ptr = lhs->dyn_cast_region_svalue ()) 3021 { 3022 /* A region_svalue is a non-NULL pointer, except in certain 3023 special cases (see the comment for region::non_null_p). */ 3024 const region *pointee = ptr->get_pointee (); 3025 if (pointee->non_null_p ()) 3026 { 3027 switch (op) 3028 { 3029 default: 3030 gcc_unreachable (); 3031 3032 case EQ_EXPR: 3033 case GE_EXPR: 3034 case LE_EXPR: 3035 return tristate::TS_FALSE; 3036 3037 case NE_EXPR: 3038 case GT_EXPR: 3039 case LT_EXPR: 3040 return tristate::TS_TRUE; 3041 } 3042 } 3043 } 3044 else if (const binop_svalue *binop = lhs->dyn_cast_binop_svalue ()) 3045 { 3046 /* Treat offsets from a non-NULL pointer as being non-NULL. This 3047 isn't strictly true, in that eventually ptr++ will wrap 3048 around and be NULL, but it won't occur in practise and thus 3049 can be used to suppress effectively false positives that we 3050 shouldn't warn for. */ 3051 if (binop->get_op () == POINTER_PLUS_EXPR) 3052 { 3053 tristate lhs_ts 3054 = eval_condition_without_cm (binop->get_arg0 (), 3055 op, rhs); 3056 if (lhs_ts.is_known ()) 3057 return lhs_ts; 3058 } 3059 } 3060 else if (const unaryop_svalue *unaryop 3061 = lhs->dyn_cast_unaryop_svalue ()) 3062 { 3063 if (unaryop->get_op () == NEGATE_EXPR) 3064 { 3065 /* e.g. "-X <= 0" is equivalent to X >= 0". */ 3066 tristate lhs_ts = eval_condition (unaryop->get_arg (), 3067 swap_tree_comparison (op), 3068 rhs); 3069 if (lhs_ts.is_known ()) 3070 return lhs_ts; 3071 } 3072 } 3073 } 3074 3075 /* Handle rejection of equality for comparisons of the initial values of 3076 "external" values (such as params) with the address of locals. */ 3077 if (const initial_svalue *init_lhs = lhs->dyn_cast_initial_svalue ()) 3078 if (const region_svalue *rhs_ptr = rhs->dyn_cast_region_svalue ()) 3079 { 3080 tristate res = compare_initial_and_pointer (init_lhs, rhs_ptr); 3081 if (res.is_known ()) 3082 return res; 3083 } 3084 if (const initial_svalue *init_rhs = rhs->dyn_cast_initial_svalue ()) 3085 if (const region_svalue *lhs_ptr = lhs->dyn_cast_region_svalue ()) 3086 { 3087 tristate res = compare_initial_and_pointer (init_rhs, lhs_ptr); 3088 if (res.is_known ()) 3089 return res; 3090 } 3091 3092 if (const widening_svalue *widen_lhs = lhs->dyn_cast_widening_svalue ()) 3093 if (tree rhs_cst = rhs->maybe_get_constant ()) 3094 { 3095 tristate res = widen_lhs->eval_condition_without_cm (op, rhs_cst); 3096 if (res.is_known ()) 3097 return res; 3098 } 3099 3100 return tristate::TS_UNKNOWN; 3101} 3102 3103/* Subroutine of region_model::eval_condition_without_cm, for rejecting 3104 equality of INIT_VAL(PARM) with &LOCAL. */ 3105 3106tristate 3107region_model::compare_initial_and_pointer (const initial_svalue *init, 3108 const region_svalue *ptr) const 3109{ 3110 const region *pointee = ptr->get_pointee (); 3111 3112 /* If we have a pointer to something within a stack frame, it can't be the 3113 initial value of a param. */ 3114 if (pointee->maybe_get_frame_region ()) 3115 if (init->initial_value_of_param_p ()) 3116 return tristate::TS_FALSE; 3117 3118 return tristate::TS_UNKNOWN; 3119} 3120 3121/* Handle various constraints of the form: 3122 LHS: ((bool)INNER_LHS INNER_OP INNER_RHS)) 3123 OP : == or != 3124 RHS: zero 3125 and (with a cast): 3126 LHS: CAST([long]int, ((bool)INNER_LHS INNER_OP INNER_RHS)) 3127 OP : == or != 3128 RHS: zero 3129 by adding constraints for INNER_LHS INNEROP INNER_RHS. 3130 3131 Return true if this function can fully handle the constraint; if 3132 so, add the implied constraint(s) and write true to *OUT if they 3133 are consistent with existing constraints, or write false to *OUT 3134 if they contradicts existing constraints. 3135 3136 Return false for cases that this function doeesn't know how to handle. 3137 3138 For example, if we're checking a stored conditional, we'll have 3139 something like: 3140 LHS: CAST(long int, (&HEAP_ALLOCATED_REGION(8)!=(int *)0B)) 3141 OP : NE_EXPR 3142 RHS: zero 3143 which this function can turn into an add_constraint of: 3144 (&HEAP_ALLOCATED_REGION(8) != (int *)0B) 3145 3146 Similarly, optimized && and || conditionals lead to e.g. 3147 if (p && q) 3148 becoming gimple like this: 3149 _1 = p_6 == 0B; 3150 _2 = q_8 == 0B 3151 _3 = _1 | _2 3152 On the "_3 is false" branch we can have constraints of the form: 3153 ((&HEAP_ALLOCATED_REGION(8)!=(int *)0B) 3154 | (&HEAP_ALLOCATED_REGION(10)!=(int *)0B)) 3155 == 0 3156 which implies that both _1 and _2 are false, 3157 which this function can turn into a pair of add_constraints of 3158 (&HEAP_ALLOCATED_REGION(8)!=(int *)0B) 3159 and: 3160 (&HEAP_ALLOCATED_REGION(10)!=(int *)0B). */ 3161 3162bool 3163region_model::add_constraints_from_binop (const svalue *outer_lhs, 3164 enum tree_code outer_op, 3165 const svalue *outer_rhs, 3166 bool *out, 3167 region_model_context *ctxt) 3168{ 3169 while (const svalue *cast = outer_lhs->maybe_undo_cast ()) 3170 outer_lhs = cast; 3171 const binop_svalue *binop_sval = outer_lhs->dyn_cast_binop_svalue (); 3172 if (!binop_sval) 3173 return false; 3174 if (!outer_rhs->all_zeroes_p ()) 3175 return false; 3176 3177 const svalue *inner_lhs = binop_sval->get_arg0 (); 3178 enum tree_code inner_op = binop_sval->get_op (); 3179 const svalue *inner_rhs = binop_sval->get_arg1 (); 3180 3181 if (outer_op != NE_EXPR && outer_op != EQ_EXPR) 3182 return false; 3183 3184 /* We have either 3185 - "OUTER_LHS != false" (i.e. OUTER is true), or 3186 - "OUTER_LHS == false" (i.e. OUTER is false). */ 3187 bool is_true = outer_op == NE_EXPR; 3188 3189 switch (inner_op) 3190 { 3191 default: 3192 return false; 3193 3194 case EQ_EXPR: 3195 case NE_EXPR: 3196 { 3197 /* ...and "(inner_lhs OP inner_rhs) == 0" 3198 then (inner_lhs OP inner_rhs) must have the same 3199 logical value as LHS. */ 3200 if (!is_true) 3201 inner_op = invert_tree_comparison (inner_op, false /* honor_nans */); 3202 *out = add_constraint (inner_lhs, inner_op, inner_rhs, ctxt); 3203 return true; 3204 } 3205 break; 3206 3207 case BIT_AND_EXPR: 3208 if (is_true) 3209 { 3210 /* ...and "(inner_lhs & inner_rhs) != 0" 3211 then both inner_lhs and inner_rhs must be true. */ 3212 const svalue *false_sval 3213 = m_mgr->get_or_create_constant_svalue (boolean_false_node); 3214 bool sat1 = add_constraint (inner_lhs, NE_EXPR, false_sval, ctxt); 3215 bool sat2 = add_constraint (inner_rhs, NE_EXPR, false_sval, ctxt); 3216 *out = sat1 && sat2; 3217 return true; 3218 } 3219 return false; 3220 3221 case BIT_IOR_EXPR: 3222 if (!is_true) 3223 { 3224 /* ...and "(inner_lhs | inner_rhs) == 0" 3225 i.e. "(inner_lhs | inner_rhs)" is false 3226 then both inner_lhs and inner_rhs must be false. */ 3227 const svalue *false_sval 3228 = m_mgr->get_or_create_constant_svalue (boolean_false_node); 3229 bool sat1 = add_constraint (inner_lhs, EQ_EXPR, false_sval, ctxt); 3230 bool sat2 = add_constraint (inner_rhs, EQ_EXPR, false_sval, ctxt); 3231 *out = sat1 && sat2; 3232 return true; 3233 } 3234 return false; 3235 } 3236} 3237 3238/* Attempt to add the constraint "LHS OP RHS" to this region_model. 3239 If it is consistent with existing constraints, add it, and return true. 3240 Return false if it contradicts existing constraints. 3241 Use CTXT for reporting any diagnostics associated with the accesses. */ 3242 3243bool 3244region_model::add_constraint (tree lhs, enum tree_code op, tree rhs, 3245 region_model_context *ctxt) 3246{ 3247 /* For now, make no attempt to capture constraints on floating-point 3248 values. */ 3249 if (FLOAT_TYPE_P (TREE_TYPE (lhs)) || FLOAT_TYPE_P (TREE_TYPE (rhs))) 3250 return true; 3251 3252 const svalue *lhs_sval = get_rvalue (lhs, ctxt); 3253 const svalue *rhs_sval = get_rvalue (rhs, ctxt); 3254 3255 return add_constraint (lhs_sval, op, rhs_sval, ctxt); 3256} 3257 3258/* Attempt to add the constraint "LHS OP RHS" to this region_model. 3259 If it is consistent with existing constraints, add it, and return true. 3260 Return false if it contradicts existing constraints. 3261 Use CTXT for reporting any diagnostics associated with the accesses. */ 3262 3263bool 3264region_model::add_constraint (const svalue *lhs, 3265 enum tree_code op, 3266 const svalue *rhs, 3267 region_model_context *ctxt) 3268{ 3269 tristate t_cond = eval_condition (lhs, op, rhs); 3270 3271 /* If we already have the condition, do nothing. */ 3272 if (t_cond.is_true ()) 3273 return true; 3274 3275 /* Reject a constraint that would contradict existing knowledge, as 3276 unsatisfiable. */ 3277 if (t_cond.is_false ()) 3278 return false; 3279 3280 bool out; 3281 if (add_constraints_from_binop (lhs, op, rhs, &out, ctxt)) 3282 return out; 3283 3284 /* Attempt to store the constraint. */ 3285 if (!m_constraints->add_constraint (lhs, op, rhs)) 3286 return false; 3287 3288 /* Notify the context, if any. This exists so that the state machines 3289 in a program_state can be notified about the condition, and so can 3290 set sm-state for e.g. unchecked->checked, both for cfg-edges, and 3291 when synthesizing constraints as above. */ 3292 if (ctxt) 3293 ctxt->on_condition (lhs, op, rhs); 3294 3295 /* If we have ®ION == NULL, then drop dynamic extents for REGION (for 3296 the case where REGION is heap-allocated and thus could be NULL). */ 3297 if (tree rhs_cst = rhs->maybe_get_constant ()) 3298 if (op == EQ_EXPR && zerop (rhs_cst)) 3299 if (const region_svalue *region_sval = lhs->dyn_cast_region_svalue ()) 3300 unset_dynamic_extents (region_sval->get_pointee ()); 3301 3302 return true; 3303} 3304 3305/* As above, but when returning false, if OUT is non-NULL, write a 3306 new rejected_constraint to *OUT. */ 3307 3308bool 3309region_model::add_constraint (tree lhs, enum tree_code op, tree rhs, 3310 region_model_context *ctxt, 3311 rejected_constraint **out) 3312{ 3313 bool sat = add_constraint (lhs, op, rhs, ctxt); 3314 if (!sat && out) 3315 *out = new rejected_op_constraint (*this, lhs, op, rhs); 3316 return sat; 3317} 3318 3319/* Determine what is known about the condition "LHS OP RHS" within 3320 this model. 3321 Use CTXT for reporting any diagnostics associated with the accesses. */ 3322 3323tristate 3324region_model::eval_condition (tree lhs, 3325 enum tree_code op, 3326 tree rhs, 3327 region_model_context *ctxt) 3328{ 3329 /* For now, make no attempt to model constraints on floating-point 3330 values. */ 3331 if (FLOAT_TYPE_P (TREE_TYPE (lhs)) || FLOAT_TYPE_P (TREE_TYPE (rhs))) 3332 return tristate::unknown (); 3333 3334 return eval_condition (get_rvalue (lhs, ctxt), op, get_rvalue (rhs, ctxt)); 3335} 3336 3337/* Implementation of region_model::get_representative_path_var. 3338 Attempt to return a path_var that represents SVAL, or return NULL_TREE. 3339 Use VISITED to prevent infinite mutual recursion with the overload for 3340 regions. */ 3341 3342path_var 3343region_model::get_representative_path_var_1 (const svalue *sval, 3344 svalue_set *visited) const 3345{ 3346 gcc_assert (sval); 3347 3348 /* Prevent infinite recursion. */ 3349 if (visited->contains (sval)) 3350 return path_var (NULL_TREE, 0); 3351 visited->add (sval); 3352 3353 /* Handle casts by recursion into get_representative_path_var. */ 3354 if (const svalue *cast_sval = sval->maybe_undo_cast ()) 3355 { 3356 path_var result = get_representative_path_var (cast_sval, visited); 3357 tree orig_type = sval->get_type (); 3358 /* If necessary, wrap the result in a cast. */ 3359 if (result.m_tree && orig_type) 3360 result.m_tree = build1 (NOP_EXPR, orig_type, result.m_tree); 3361 return result; 3362 } 3363 3364 auto_vec<path_var> pvs; 3365 m_store.get_representative_path_vars (this, visited, sval, &pvs); 3366 3367 if (tree cst = sval->maybe_get_constant ()) 3368 pvs.safe_push (path_var (cst, 0)); 3369 3370 /* Handle string literals and various other pointers. */ 3371 if (const region_svalue *ptr_sval = sval->dyn_cast_region_svalue ()) 3372 { 3373 const region *reg = ptr_sval->get_pointee (); 3374 if (path_var pv = get_representative_path_var (reg, visited)) 3375 return path_var (build1 (ADDR_EXPR, 3376 sval->get_type (), 3377 pv.m_tree), 3378 pv.m_stack_depth); 3379 } 3380 3381 /* If we have a sub_svalue, look for ways to represent the parent. */ 3382 if (const sub_svalue *sub_sval = sval->dyn_cast_sub_svalue ()) 3383 { 3384 const svalue *parent_sval = sub_sval->get_parent (); 3385 const region *subreg = sub_sval->get_subregion (); 3386 if (path_var parent_pv 3387 = get_representative_path_var (parent_sval, visited)) 3388 if (const field_region *field_reg = subreg->dyn_cast_field_region ()) 3389 return path_var (build3 (COMPONENT_REF, 3390 sval->get_type (), 3391 parent_pv.m_tree, 3392 field_reg->get_field (), 3393 NULL_TREE), 3394 parent_pv.m_stack_depth); 3395 } 3396 3397 /* Handle binops. */ 3398 if (const binop_svalue *binop_sval = sval->dyn_cast_binop_svalue ()) 3399 if (path_var lhs_pv 3400 = get_representative_path_var (binop_sval->get_arg0 (), visited)) 3401 if (path_var rhs_pv 3402 = get_representative_path_var (binop_sval->get_arg1 (), visited)) 3403 return path_var (build2 (binop_sval->get_op (), 3404 sval->get_type (), 3405 lhs_pv.m_tree, rhs_pv.m_tree), 3406 lhs_pv.m_stack_depth); 3407 3408 if (pvs.length () < 1) 3409 return path_var (NULL_TREE, 0); 3410 3411 pvs.qsort (readability_comparator); 3412 return pvs[0]; 3413} 3414 3415/* Attempt to return a path_var that represents SVAL, or return NULL_TREE. 3416 Use VISITED to prevent infinite mutual recursion with the overload for 3417 regions 3418 3419 This function defers to get_representative_path_var_1 to do the work; 3420 it adds verification that get_representative_path_var_1 returned a tree 3421 of the correct type. */ 3422 3423path_var 3424region_model::get_representative_path_var (const svalue *sval, 3425 svalue_set *visited) const 3426{ 3427 if (sval == NULL) 3428 return path_var (NULL_TREE, 0); 3429 3430 tree orig_type = sval->get_type (); 3431 3432 path_var result = get_representative_path_var_1 (sval, visited); 3433 3434 /* Verify that the result has the same type as SVAL, if any. */ 3435 if (result.m_tree && orig_type) 3436 gcc_assert (TREE_TYPE (result.m_tree) == orig_type); 3437 3438 return result; 3439} 3440 3441/* Attempt to return a tree that represents SVAL, or return NULL_TREE. 3442 3443 Strip off any top-level cast, to avoid messages like 3444 double-free of '(void *)ptr' 3445 from analyzer diagnostics. */ 3446 3447tree 3448region_model::get_representative_tree (const svalue *sval) const 3449{ 3450 svalue_set visited; 3451 tree expr = get_representative_path_var (sval, &visited).m_tree; 3452 3453 /* Strip off any top-level cast. */ 3454 if (expr && TREE_CODE (expr) == NOP_EXPR) 3455 expr = TREE_OPERAND (expr, 0); 3456 3457 return fixup_tree_for_diagnostic (expr); 3458} 3459 3460/* Implementation of region_model::get_representative_path_var. 3461 3462 Attempt to return a path_var that represents REG, or return 3463 the NULL path_var. 3464 For example, a region for a field of a local would be a path_var 3465 wrapping a COMPONENT_REF. 3466 Use VISITED to prevent infinite mutual recursion with the overload for 3467 svalues. */ 3468 3469path_var 3470region_model::get_representative_path_var_1 (const region *reg, 3471 svalue_set *visited) const 3472{ 3473 switch (reg->get_kind ()) 3474 { 3475 default: 3476 gcc_unreachable (); 3477 3478 case RK_FRAME: 3479 case RK_GLOBALS: 3480 case RK_CODE: 3481 case RK_HEAP: 3482 case RK_STACK: 3483 case RK_ROOT: 3484 /* Regions that represent memory spaces are not expressible as trees. */ 3485 return path_var (NULL_TREE, 0); 3486 3487 case RK_FUNCTION: 3488 { 3489 const function_region *function_reg 3490 = as_a <const function_region *> (reg); 3491 return path_var (function_reg->get_fndecl (), 0); 3492 } 3493 case RK_LABEL: 3494 { 3495 const label_region *label_reg = as_a <const label_region *> (reg); 3496 return path_var (label_reg->get_label (), 0); 3497 } 3498 3499 case RK_SYMBOLIC: 3500 { 3501 const symbolic_region *symbolic_reg 3502 = as_a <const symbolic_region *> (reg); 3503 const svalue *pointer = symbolic_reg->get_pointer (); 3504 path_var pointer_pv = get_representative_path_var (pointer, visited); 3505 if (!pointer_pv) 3506 return path_var (NULL_TREE, 0); 3507 tree offset = build_int_cst (pointer->get_type (), 0); 3508 return path_var (build2 (MEM_REF, 3509 reg->get_type (), 3510 pointer_pv.m_tree, 3511 offset), 3512 pointer_pv.m_stack_depth); 3513 } 3514 case RK_DECL: 3515 { 3516 const decl_region *decl_reg = as_a <const decl_region *> (reg); 3517 return path_var (decl_reg->get_decl (), decl_reg->get_stack_depth ()); 3518 } 3519 case RK_FIELD: 3520 { 3521 const field_region *field_reg = as_a <const field_region *> (reg); 3522 path_var parent_pv 3523 = get_representative_path_var (reg->get_parent_region (), visited); 3524 if (!parent_pv) 3525 return path_var (NULL_TREE, 0); 3526 return path_var (build3 (COMPONENT_REF, 3527 reg->get_type (), 3528 parent_pv.m_tree, 3529 field_reg->get_field (), 3530 NULL_TREE), 3531 parent_pv.m_stack_depth); 3532 } 3533 3534 case RK_ELEMENT: 3535 { 3536 const element_region *element_reg 3537 = as_a <const element_region *> (reg); 3538 path_var parent_pv 3539 = get_representative_path_var (reg->get_parent_region (), visited); 3540 if (!parent_pv) 3541 return path_var (NULL_TREE, 0); 3542 path_var index_pv 3543 = get_representative_path_var (element_reg->get_index (), visited); 3544 if (!index_pv) 3545 return path_var (NULL_TREE, 0); 3546 return path_var (build4 (ARRAY_REF, 3547 reg->get_type (), 3548 parent_pv.m_tree, index_pv.m_tree, 3549 NULL_TREE, NULL_TREE), 3550 parent_pv.m_stack_depth); 3551 } 3552 3553 case RK_OFFSET: 3554 { 3555 const offset_region *offset_reg 3556 = as_a <const offset_region *> (reg); 3557 path_var parent_pv 3558 = get_representative_path_var (reg->get_parent_region (), visited); 3559 if (!parent_pv) 3560 return path_var (NULL_TREE, 0); 3561 path_var offset_pv 3562 = get_representative_path_var (offset_reg->get_byte_offset (), 3563 visited); 3564 if (!offset_pv || TREE_CODE (offset_pv.m_tree) != INTEGER_CST) 3565 return path_var (NULL_TREE, 0); 3566 tree addr_parent = build1 (ADDR_EXPR, 3567 build_pointer_type (reg->get_type ()), 3568 parent_pv.m_tree); 3569 return path_var (build2 (MEM_REF, 3570 reg->get_type (), 3571 addr_parent, offset_pv.m_tree), 3572 parent_pv.m_stack_depth); 3573 } 3574 3575 case RK_SIZED: 3576 return path_var (NULL_TREE, 0); 3577 3578 case RK_CAST: 3579 { 3580 path_var parent_pv 3581 = get_representative_path_var (reg->get_parent_region (), visited); 3582 if (!parent_pv) 3583 return path_var (NULL_TREE, 0); 3584 return path_var (build1 (NOP_EXPR, 3585 reg->get_type (), 3586 parent_pv.m_tree), 3587 parent_pv.m_stack_depth); 3588 } 3589 3590 case RK_HEAP_ALLOCATED: 3591 case RK_ALLOCA: 3592 /* No good way to express heap-allocated/alloca regions as trees. */ 3593 return path_var (NULL_TREE, 0); 3594 3595 case RK_STRING: 3596 { 3597 const string_region *string_reg = as_a <const string_region *> (reg); 3598 return path_var (string_reg->get_string_cst (), 0); 3599 } 3600 3601 case RK_UNKNOWN: 3602 return path_var (NULL_TREE, 0); 3603 } 3604} 3605 3606/* Attempt to return a path_var that represents REG, or return 3607 the NULL path_var. 3608 For example, a region for a field of a local would be a path_var 3609 wrapping a COMPONENT_REF. 3610 Use VISITED to prevent infinite mutual recursion with the overload for 3611 svalues. 3612 3613 This function defers to get_representative_path_var_1 to do the work; 3614 it adds verification that get_representative_path_var_1 returned a tree 3615 of the correct type. */ 3616 3617path_var 3618region_model::get_representative_path_var (const region *reg, 3619 svalue_set *visited) const 3620{ 3621 path_var result = get_representative_path_var_1 (reg, visited); 3622 3623 /* Verify that the result has the same type as REG, if any. */ 3624 if (result.m_tree && reg->get_type ()) 3625 gcc_assert (TREE_TYPE (result.m_tree) == reg->get_type ()); 3626 3627 return result; 3628} 3629 3630/* Update this model for any phis in SNODE, assuming we came from 3631 LAST_CFG_SUPEREDGE. */ 3632 3633void 3634region_model::update_for_phis (const supernode *snode, 3635 const cfg_superedge *last_cfg_superedge, 3636 region_model_context *ctxt) 3637{ 3638 gcc_assert (last_cfg_superedge); 3639 3640 /* Copy this state and pass it to handle_phi so that all of the phi stmts 3641 are effectively handled simultaneously. */ 3642 const region_model old_state (*this); 3643 3644 for (gphi_iterator gpi = const_cast<supernode *>(snode)->start_phis (); 3645 !gsi_end_p (gpi); gsi_next (&gpi)) 3646 { 3647 gphi *phi = gpi.phi (); 3648 3649 tree src = last_cfg_superedge->get_phi_arg (phi); 3650 tree lhs = gimple_phi_result (phi); 3651 3652 /* Update next_state based on phi and old_state. */ 3653 handle_phi (phi, lhs, src, old_state, ctxt); 3654 } 3655} 3656 3657/* Attempt to update this model for taking EDGE (where the last statement 3658 was LAST_STMT), returning true if the edge can be taken, false 3659 otherwise. 3660 When returning false, if OUT is non-NULL, write a new rejected_constraint 3661 to it. 3662 3663 For CFG superedges where LAST_STMT is a conditional or a switch 3664 statement, attempt to add the relevant conditions for EDGE to this 3665 model, returning true if they are feasible, or false if they are 3666 impossible. 3667 3668 For call superedges, push frame information and store arguments 3669 into parameters. 3670 3671 For return superedges, pop frame information and store return 3672 values into any lhs. 3673 3674 Rejection of call/return superedges happens elsewhere, in 3675 program_point::on_edge (i.e. based on program point, rather 3676 than program state). */ 3677 3678bool 3679region_model::maybe_update_for_edge (const superedge &edge, 3680 const gimple *last_stmt, 3681 region_model_context *ctxt, 3682 rejected_constraint **out) 3683{ 3684 /* Handle frame updates for interprocedural edges. */ 3685 switch (edge.m_kind) 3686 { 3687 default: 3688 break; 3689 3690 case SUPEREDGE_CALL: 3691 { 3692 const call_superedge *call_edge = as_a <const call_superedge *> (&edge); 3693 update_for_call_superedge (*call_edge, ctxt); 3694 } 3695 break; 3696 3697 case SUPEREDGE_RETURN: 3698 { 3699 const return_superedge *return_edge 3700 = as_a <const return_superedge *> (&edge); 3701 update_for_return_superedge (*return_edge, ctxt); 3702 } 3703 break; 3704 3705 case SUPEREDGE_INTRAPROCEDURAL_CALL: 3706 { 3707 const callgraph_superedge *cg_sedge 3708 = as_a <const callgraph_superedge *> (&edge); 3709 update_for_call_summary (*cg_sedge, ctxt); 3710 } 3711 break; 3712 } 3713 3714 if (last_stmt == NULL) 3715 return true; 3716 3717 /* Apply any constraints for conditionals/switch statements. */ 3718 3719 if (const gcond *cond_stmt = dyn_cast <const gcond *> (last_stmt)) 3720 { 3721 const cfg_superedge *cfg_sedge = as_a <const cfg_superedge *> (&edge); 3722 return apply_constraints_for_gcond (*cfg_sedge, cond_stmt, ctxt, out); 3723 } 3724 3725 if (const gswitch *switch_stmt = dyn_cast <const gswitch *> (last_stmt)) 3726 { 3727 const switch_cfg_superedge *switch_sedge 3728 = as_a <const switch_cfg_superedge *> (&edge); 3729 return apply_constraints_for_gswitch (*switch_sedge, switch_stmt, 3730 ctxt, out); 3731 } 3732 3733 /* Apply any constraints due to an exception being thrown. */ 3734 if (const cfg_superedge *cfg_sedge = dyn_cast <const cfg_superedge *> (&edge)) 3735 if (cfg_sedge->get_flags () & EDGE_EH) 3736 return apply_constraints_for_exception (last_stmt, ctxt, out); 3737 3738 return true; 3739} 3740 3741/* Push a new frame_region on to the stack region. 3742 Populate the frame_region with child regions for the function call's 3743 parameters, using values from the arguments at the callsite in the 3744 caller's frame. */ 3745 3746void 3747region_model::update_for_gcall (const gcall *call_stmt, 3748 region_model_context *ctxt, 3749 function *callee) 3750{ 3751 /* Build a vec of argument svalues, using the current top 3752 frame for resolving tree expressions. */ 3753 auto_vec<const svalue *> arg_svals (gimple_call_num_args (call_stmt)); 3754 3755 for (unsigned i = 0; i < gimple_call_num_args (call_stmt); i++) 3756 { 3757 tree arg = gimple_call_arg (call_stmt, i); 3758 arg_svals.quick_push (get_rvalue (arg, ctxt)); 3759 } 3760 3761 if(!callee) 3762 { 3763 /* Get the function * from the gcall. */ 3764 tree fn_decl = get_fndecl_for_call (call_stmt,ctxt); 3765 callee = DECL_STRUCT_FUNCTION (fn_decl); 3766 } 3767 3768 push_frame (callee, &arg_svals, ctxt); 3769} 3770 3771/* Pop the top-most frame_region from the stack, and copy the return 3772 region's values (if any) into the region for the lvalue of the LHS of 3773 the call (if any). */ 3774 3775void 3776region_model::update_for_return_gcall (const gcall *call_stmt, 3777 region_model_context *ctxt) 3778{ 3779 /* Get the lvalue for the result of the call, passing it to pop_frame, 3780 so that pop_frame can determine the region with respect to the 3781 *caller* frame. */ 3782 tree lhs = gimple_call_lhs (call_stmt); 3783 pop_frame (lhs, NULL, ctxt); 3784} 3785 3786/* Extract calling information from the superedge and update the model for the 3787 call */ 3788 3789void 3790region_model::update_for_call_superedge (const call_superedge &call_edge, 3791 region_model_context *ctxt) 3792{ 3793 const gcall *call_stmt = call_edge.get_call_stmt (); 3794 update_for_gcall (call_stmt, ctxt, call_edge.get_callee_function ()); 3795} 3796 3797/* Extract calling information from the return superedge and update the model 3798 for the returning call */ 3799 3800void 3801region_model::update_for_return_superedge (const return_superedge &return_edge, 3802 region_model_context *ctxt) 3803{ 3804 const gcall *call_stmt = return_edge.get_call_stmt (); 3805 update_for_return_gcall (call_stmt, ctxt); 3806} 3807 3808/* Update this region_model with a summary of the effect of calling 3809 and returning from CG_SEDGE. 3810 3811 TODO: Currently this is extremely simplistic: we merely set the 3812 return value to "unknown". A proper implementation would e.g. update 3813 sm-state, and presumably be reworked to support multiple outcomes. */ 3814 3815void 3816region_model::update_for_call_summary (const callgraph_superedge &cg_sedge, 3817 region_model_context *ctxt) 3818{ 3819 /* For now, set any return value to "unknown". */ 3820 const gcall *call_stmt = cg_sedge.get_call_stmt (); 3821 tree lhs = gimple_call_lhs (call_stmt); 3822 if (lhs) 3823 mark_region_as_unknown (get_lvalue (lhs, ctxt), 3824 ctxt ? ctxt->get_uncertainty () : NULL); 3825 3826 // TODO: actually implement some kind of summary here 3827} 3828 3829/* Given a true or false edge guarded by conditional statement COND_STMT, 3830 determine appropriate constraints for the edge to be taken. 3831 3832 If they are feasible, add the constraints and return true. 3833 3834 Return false if the constraints contradict existing knowledge 3835 (and so the edge should not be taken). 3836 When returning false, if OUT is non-NULL, write a new rejected_constraint 3837 to it. */ 3838 3839bool 3840region_model::apply_constraints_for_gcond (const cfg_superedge &sedge, 3841 const gcond *cond_stmt, 3842 region_model_context *ctxt, 3843 rejected_constraint **out) 3844{ 3845 ::edge cfg_edge = sedge.get_cfg_edge (); 3846 gcc_assert (cfg_edge != NULL); 3847 gcc_assert (cfg_edge->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)); 3848 3849 enum tree_code op = gimple_cond_code (cond_stmt); 3850 tree lhs = gimple_cond_lhs (cond_stmt); 3851 tree rhs = gimple_cond_rhs (cond_stmt); 3852 if (cfg_edge->flags & EDGE_FALSE_VALUE) 3853 op = invert_tree_comparison (op, false /* honor_nans */); 3854 return add_constraint (lhs, op, rhs, ctxt, out); 3855} 3856 3857/* Given an EDGE guarded by SWITCH_STMT, determine appropriate constraints 3858 for the edge to be taken. 3859 3860 If they are feasible, add the constraints and return true. 3861 3862 Return false if the constraints contradict existing knowledge 3863 (and so the edge should not be taken). 3864 When returning false, if OUT is non-NULL, write a new rejected_constraint 3865 to it. */ 3866 3867bool 3868region_model::apply_constraints_for_gswitch (const switch_cfg_superedge &edge, 3869 const gswitch *switch_stmt, 3870 region_model_context *ctxt, 3871 rejected_constraint **out) 3872{ 3873 bounded_ranges_manager *ranges_mgr = get_range_manager (); 3874 const bounded_ranges *all_cases_ranges 3875 = ranges_mgr->get_or_create_ranges_for_switch (&edge, switch_stmt); 3876 tree index = gimple_switch_index (switch_stmt); 3877 const svalue *index_sval = get_rvalue (index, ctxt); 3878 bool sat = m_constraints->add_bounded_ranges (index_sval, all_cases_ranges); 3879 if (!sat && out) 3880 *out = new rejected_ranges_constraint (*this, index, all_cases_ranges); 3881 return sat; 3882} 3883 3884/* Apply any constraints due to an exception being thrown at LAST_STMT. 3885 3886 If they are feasible, add the constraints and return true. 3887 3888 Return false if the constraints contradict existing knowledge 3889 (and so the edge should not be taken). 3890 When returning false, if OUT is non-NULL, write a new rejected_constraint 3891 to it. */ 3892 3893bool 3894region_model::apply_constraints_for_exception (const gimple *last_stmt, 3895 region_model_context *ctxt, 3896 rejected_constraint **out) 3897{ 3898 gcc_assert (last_stmt); 3899 if (const gcall *call = dyn_cast <const gcall *> (last_stmt)) 3900 if (tree callee_fndecl = get_fndecl_for_call (call, ctxt)) 3901 if (is_named_call_p (callee_fndecl, "operator new", call, 1) 3902 || is_named_call_p (callee_fndecl, "operator new []", call, 1)) 3903 { 3904 /* We have an exception thrown from operator new. 3905 Add a constraint that the result was NULL, to avoid a false 3906 leak report due to the result being lost when following 3907 the EH edge. */ 3908 if (tree lhs = gimple_call_lhs (call)) 3909 return add_constraint (lhs, EQ_EXPR, null_pointer_node, ctxt, out); 3910 return true; 3911 } 3912 return true; 3913} 3914 3915/* For use with push_frame when handling a top-level call within the analysis. 3916 PARAM has a defined but unknown initial value. 3917 Anything it points to has escaped, since the calling context "knows" 3918 the pointer, and thus calls to unknown functions could read/write into 3919 the region. 3920 If NONNULL is true, then assume that PARAM must be non-NULL. */ 3921 3922void 3923region_model::on_top_level_param (tree param, 3924 bool nonnull, 3925 region_model_context *ctxt) 3926{ 3927 if (POINTER_TYPE_P (TREE_TYPE (param))) 3928 { 3929 const region *param_reg = get_lvalue (param, ctxt); 3930 const svalue *init_ptr_sval 3931 = m_mgr->get_or_create_initial_value (param_reg); 3932 const region *pointee_reg = m_mgr->get_symbolic_region (init_ptr_sval); 3933 m_store.mark_as_escaped (pointee_reg); 3934 if (nonnull) 3935 { 3936 const svalue *null_ptr_sval 3937 = m_mgr->get_or_create_null_ptr (TREE_TYPE (param)); 3938 add_constraint (init_ptr_sval, NE_EXPR, null_ptr_sval, ctxt); 3939 } 3940 } 3941} 3942 3943/* Update this region_model to reflect pushing a frame onto the stack 3944 for a call to FUN. 3945 3946 If ARG_SVALS is non-NULL, use it to populate the parameters 3947 in the new frame. 3948 Otherwise, the params have their initial_svalues. 3949 3950 Return the frame_region for the new frame. */ 3951 3952const region * 3953region_model::push_frame (function *fun, const vec<const svalue *> *arg_svals, 3954 region_model_context *ctxt) 3955{ 3956 m_current_frame = m_mgr->get_frame_region (m_current_frame, fun); 3957 if (arg_svals) 3958 { 3959 /* Arguments supplied from a caller frame. */ 3960 tree fndecl = fun->decl; 3961 unsigned idx = 0; 3962 for (tree iter_parm = DECL_ARGUMENTS (fndecl); iter_parm; 3963 iter_parm = DECL_CHAIN (iter_parm), ++idx) 3964 { 3965 /* If there's a mismatching declaration, the call stmt might 3966 not have enough args. Handle this case by leaving the 3967 rest of the params as uninitialized. */ 3968 if (idx >= arg_svals->length ()) 3969 break; 3970 tree parm_lval = iter_parm; 3971 if (tree parm_default_ssa = ssa_default_def (fun, iter_parm)) 3972 parm_lval = parm_default_ssa; 3973 const region *parm_reg = get_lvalue (parm_lval, ctxt); 3974 const svalue *arg_sval = (*arg_svals)[idx]; 3975 set_value (parm_reg, arg_sval, ctxt); 3976 } 3977 } 3978 else 3979 { 3980 /* Otherwise we have a top-level call within the analysis. The params 3981 have defined but unknown initial values. 3982 Anything they point to has escaped. */ 3983 tree fndecl = fun->decl; 3984 3985 /* Handle "__attribute__((nonnull))". */ 3986 tree fntype = TREE_TYPE (fndecl); 3987 bitmap nonnull_args = get_nonnull_args (fntype); 3988 3989 unsigned parm_idx = 0; 3990 for (tree iter_parm = DECL_ARGUMENTS (fndecl); iter_parm; 3991 iter_parm = DECL_CHAIN (iter_parm)) 3992 { 3993 bool non_null = (nonnull_args 3994 ? (bitmap_empty_p (nonnull_args) 3995 || bitmap_bit_p (nonnull_args, parm_idx)) 3996 : false); 3997 if (tree parm_default_ssa = ssa_default_def (fun, iter_parm)) 3998 on_top_level_param (parm_default_ssa, non_null, ctxt); 3999 else 4000 on_top_level_param (iter_parm, non_null, ctxt); 4001 parm_idx++; 4002 } 4003 4004 BITMAP_FREE (nonnull_args); 4005 } 4006 4007 return m_current_frame; 4008} 4009 4010/* Get the function of the top-most frame in this region_model's stack. 4011 There must be such a frame. */ 4012 4013function * 4014region_model::get_current_function () const 4015{ 4016 const frame_region *frame = get_current_frame (); 4017 gcc_assert (frame); 4018 return frame->get_function (); 4019} 4020 4021/* Pop the topmost frame_region from this region_model's stack; 4022 4023 If RESULT_LVALUE is non-null, copy any return value from the frame 4024 into the corresponding region (evaluated with respect to the *caller* 4025 frame, rather than the called frame). 4026 If OUT_RESULT is non-null, copy any return value from the frame 4027 into *OUT_RESULT. 4028 4029 If EVAL_RETURN_SVALUE is false, then don't evaluate the return value. 4030 This is for use when unwinding frames e.g. due to longjmp, to suppress 4031 erroneously reporting uninitialized return values. 4032 4033 Purge the frame region and all its descendent regions. 4034 Convert any pointers that point into such regions into 4035 POISON_KIND_POPPED_STACK svalues. */ 4036 4037void 4038region_model::pop_frame (tree result_lvalue, 4039 const svalue **out_result, 4040 region_model_context *ctxt, 4041 bool eval_return_svalue) 4042{ 4043 gcc_assert (m_current_frame); 4044 4045 /* Evaluate the result, within the callee frame. */ 4046 const frame_region *frame_reg = m_current_frame; 4047 tree fndecl = m_current_frame->get_function ()->decl; 4048 tree result = DECL_RESULT (fndecl); 4049 const svalue *retval = NULL; 4050 if (result 4051 && TREE_TYPE (result) != void_type_node 4052 && eval_return_svalue) 4053 { 4054 retval = get_rvalue (result, ctxt); 4055 if (out_result) 4056 *out_result = retval; 4057 } 4058 4059 /* Pop the frame. */ 4060 m_current_frame = m_current_frame->get_calling_frame (); 4061 4062 if (result_lvalue && retval) 4063 { 4064 gcc_assert (eval_return_svalue); 4065 4066 /* Compute result_dst_reg using RESULT_LVALUE *after* popping 4067 the frame, but before poisoning pointers into the old frame. */ 4068 const region *result_dst_reg = get_lvalue (result_lvalue, ctxt); 4069 set_value (result_dst_reg, retval, ctxt); 4070 } 4071 4072 unbind_region_and_descendents (frame_reg,POISON_KIND_POPPED_STACK); 4073} 4074 4075/* Get the number of frames in this region_model's stack. */ 4076 4077int 4078region_model::get_stack_depth () const 4079{ 4080 const frame_region *frame = get_current_frame (); 4081 if (frame) 4082 return frame->get_stack_depth (); 4083 else 4084 return 0; 4085} 4086 4087/* Get the frame_region with the given index within the stack. 4088 The frame_region must exist. */ 4089 4090const frame_region * 4091region_model::get_frame_at_index (int index) const 4092{ 4093 const frame_region *frame = get_current_frame (); 4094 gcc_assert (frame); 4095 gcc_assert (index >= 0); 4096 gcc_assert (index <= frame->get_index ()); 4097 while (index != frame->get_index ()) 4098 { 4099 frame = frame->get_calling_frame (); 4100 gcc_assert (frame); 4101 } 4102 return frame; 4103} 4104 4105/* Unbind svalues for any regions in REG and below. 4106 Find any pointers to such regions; convert them to 4107 poisoned values of kind PKIND. 4108 Also purge any dynamic extents. */ 4109 4110void 4111region_model::unbind_region_and_descendents (const region *reg, 4112 enum poison_kind pkind) 4113{ 4114 /* Gather a set of base regions to be unbound. */ 4115 hash_set<const region *> base_regs; 4116 for (store::cluster_map_t::iterator iter = m_store.begin (); 4117 iter != m_store.end (); ++iter) 4118 { 4119 const region *iter_base_reg = (*iter).first; 4120 if (iter_base_reg->descendent_of_p (reg)) 4121 base_regs.add (iter_base_reg); 4122 } 4123 for (hash_set<const region *>::iterator iter = base_regs.begin (); 4124 iter != base_regs.end (); ++iter) 4125 m_store.purge_cluster (*iter); 4126 4127 /* Find any pointers to REG or its descendents; convert to poisoned. */ 4128 poison_any_pointers_to_descendents (reg, pkind); 4129 4130 /* Purge dynamic extents of any base regions in REG and below 4131 (e.g. VLAs and alloca stack regions). */ 4132 for (auto iter : m_dynamic_extents) 4133 { 4134 const region *iter_reg = iter.first; 4135 if (iter_reg->descendent_of_p (reg)) 4136 unset_dynamic_extents (iter_reg); 4137 } 4138} 4139 4140/* Implementation of BindingVisitor. 4141 Update the bound svalues for regions below REG to use poisoned 4142 values instead. */ 4143 4144struct bad_pointer_finder 4145{ 4146 bad_pointer_finder (const region *reg, enum poison_kind pkind, 4147 region_model_manager *mgr) 4148 : m_reg (reg), m_pkind (pkind), m_mgr (mgr), m_count (0) 4149 {} 4150 4151 void on_binding (const binding_key *, const svalue *&sval) 4152 { 4153 if (const region_svalue *ptr_sval = sval->dyn_cast_region_svalue ()) 4154 { 4155 const region *ptr_dst = ptr_sval->get_pointee (); 4156 /* Poison ptrs to descendents of REG, but not to REG itself, 4157 otherwise double-free detection doesn't work (since sm-state 4158 for "free" is stored on the original ptr svalue). */ 4159 if (ptr_dst->descendent_of_p (m_reg) 4160 && ptr_dst != m_reg) 4161 { 4162 sval = m_mgr->get_or_create_poisoned_svalue (m_pkind, 4163 sval->get_type ()); 4164 ++m_count; 4165 } 4166 } 4167 } 4168 4169 const region *m_reg; 4170 enum poison_kind m_pkind; 4171 region_model_manager *const m_mgr; 4172 int m_count; 4173}; 4174 4175/* Find any pointers to REG or its descendents; convert them to 4176 poisoned values of kind PKIND. 4177 Return the number of pointers that were poisoned. */ 4178 4179int 4180region_model::poison_any_pointers_to_descendents (const region *reg, 4181 enum poison_kind pkind) 4182{ 4183 bad_pointer_finder bv (reg, pkind, m_mgr); 4184 m_store.for_each_binding (bv); 4185 return bv.m_count; 4186} 4187 4188/* Attempt to merge THIS with OTHER_MODEL, writing the result 4189 to OUT_MODEL. Use POINT to distinguish values created as a 4190 result of merging. */ 4191 4192bool 4193region_model::can_merge_with_p (const region_model &other_model, 4194 const program_point &point, 4195 region_model *out_model, 4196 const extrinsic_state *ext_state, 4197 const program_state *state_a, 4198 const program_state *state_b) const 4199{ 4200 gcc_assert (out_model); 4201 gcc_assert (m_mgr == other_model.m_mgr); 4202 gcc_assert (m_mgr == out_model->m_mgr); 4203 4204 if (m_current_frame != other_model.m_current_frame) 4205 return false; 4206 out_model->m_current_frame = m_current_frame; 4207 4208 model_merger m (this, &other_model, point, out_model, 4209 ext_state, state_a, state_b); 4210 4211 if (!store::can_merge_p (&m_store, &other_model.m_store, 4212 &out_model->m_store, m_mgr->get_store_manager (), 4213 &m)) 4214 return false; 4215 4216 if (!m_dynamic_extents.can_merge_with_p (other_model.m_dynamic_extents, 4217 &out_model->m_dynamic_extents)) 4218 return false; 4219 4220 /* Merge constraints. */ 4221 constraint_manager::merge (*m_constraints, 4222 *other_model.m_constraints, 4223 out_model->m_constraints); 4224 4225 return true; 4226} 4227 4228/* Attempt to get the fndecl used at CALL, if known, or NULL_TREE 4229 otherwise. */ 4230 4231tree 4232region_model::get_fndecl_for_call (const gcall *call, 4233 region_model_context *ctxt) 4234{ 4235 tree fn_ptr = gimple_call_fn (call); 4236 if (fn_ptr == NULL_TREE) 4237 return NULL_TREE; 4238 const svalue *fn_ptr_sval = get_rvalue (fn_ptr, ctxt); 4239 if (const region_svalue *fn_ptr_ptr 4240 = fn_ptr_sval->dyn_cast_region_svalue ()) 4241 { 4242 const region *reg = fn_ptr_ptr->get_pointee (); 4243 if (const function_region *fn_reg = reg->dyn_cast_function_region ()) 4244 { 4245 tree fn_decl = fn_reg->get_fndecl (); 4246 cgraph_node *node = cgraph_node::get (fn_decl); 4247 if (!node) 4248 return NULL_TREE; 4249 const cgraph_node *ultimate_node = node->ultimate_alias_target (); 4250 if (ultimate_node) 4251 return ultimate_node->decl; 4252 } 4253 } 4254 4255 return NULL_TREE; 4256} 4257 4258/* Would be much simpler to use a lambda here, if it were supported. */ 4259 4260struct append_regions_cb_data 4261{ 4262 const region_model *model; 4263 auto_vec<const decl_region *> *out; 4264}; 4265 4266/* Populate *OUT with all decl_regions in the current 4267 frame that have clusters within the store. */ 4268 4269void 4270region_model:: 4271get_regions_for_current_frame (auto_vec<const decl_region *> *out) const 4272{ 4273 append_regions_cb_data data; 4274 data.model = this; 4275 data.out = out; 4276 m_store.for_each_cluster (append_regions_cb, &data); 4277} 4278 4279/* Implementation detail of get_regions_for_current_frame. */ 4280 4281void 4282region_model::append_regions_cb (const region *base_reg, 4283 append_regions_cb_data *cb_data) 4284{ 4285 if (base_reg->get_parent_region () != cb_data->model->m_current_frame) 4286 return; 4287 if (const decl_region *decl_reg = base_reg->dyn_cast_decl_region ()) 4288 cb_data->out->safe_push (decl_reg); 4289} 4290 4291/* Return a new region describing a heap-allocated block of memory. 4292 Use CTXT to complain about tainted sizes. */ 4293 4294const region * 4295region_model::create_region_for_heap_alloc (const svalue *size_in_bytes, 4296 region_model_context *ctxt) 4297{ 4298 const region *reg = m_mgr->create_region_for_heap_alloc (); 4299 if (compat_types_p (size_in_bytes->get_type (), size_type_node)) 4300 set_dynamic_extents (reg, size_in_bytes, ctxt); 4301 return reg; 4302} 4303 4304/* Return a new region describing a block of memory allocated within the 4305 current frame. 4306 Use CTXT to complain about tainted sizes. */ 4307 4308const region * 4309region_model::create_region_for_alloca (const svalue *size_in_bytes, 4310 region_model_context *ctxt) 4311{ 4312 const region *reg = m_mgr->create_region_for_alloca (m_current_frame); 4313 if (compat_types_p (size_in_bytes->get_type (), size_type_node)) 4314 set_dynamic_extents (reg, size_in_bytes, ctxt); 4315 return reg; 4316} 4317 4318/* Record that the size of REG is SIZE_IN_BYTES. 4319 Use CTXT to complain about tainted sizes. */ 4320 4321void 4322region_model::set_dynamic_extents (const region *reg, 4323 const svalue *size_in_bytes, 4324 region_model_context *ctxt) 4325{ 4326 assert_compat_types (size_in_bytes->get_type (), size_type_node); 4327 if (ctxt) 4328 check_dynamic_size_for_taint (reg->get_memory_space (), size_in_bytes, 4329 ctxt); 4330 m_dynamic_extents.put (reg, size_in_bytes); 4331} 4332 4333/* Get the recording of REG in bytes, or NULL if no dynamic size was 4334 recorded. */ 4335 4336const svalue * 4337region_model::get_dynamic_extents (const region *reg) const 4338{ 4339 if (const svalue * const *slot = m_dynamic_extents.get (reg)) 4340 return *slot; 4341 return NULL; 4342} 4343 4344/* Unset any recorded dynamic size of REG. */ 4345 4346void 4347region_model::unset_dynamic_extents (const region *reg) 4348{ 4349 m_dynamic_extents.remove (reg); 4350} 4351 4352/* class noop_region_model_context : public region_model_context. */ 4353 4354void 4355noop_region_model_context::add_note (pending_note *pn) 4356{ 4357 delete pn; 4358} 4359 4360void 4361noop_region_model_context::bifurcate (custom_edge_info *info) 4362{ 4363 delete info; 4364} 4365 4366void 4367noop_region_model_context::terminate_path () 4368{ 4369} 4370 4371/* struct model_merger. */ 4372 4373/* Dump a multiline representation of this merger to PP. */ 4374 4375void 4376model_merger::dump_to_pp (pretty_printer *pp, bool simple) const 4377{ 4378 pp_string (pp, "model A:"); 4379 pp_newline (pp); 4380 m_model_a->dump_to_pp (pp, simple, true); 4381 pp_newline (pp); 4382 4383 pp_string (pp, "model B:"); 4384 pp_newline (pp); 4385 m_model_b->dump_to_pp (pp, simple, true); 4386 pp_newline (pp); 4387 4388 pp_string (pp, "merged model:"); 4389 pp_newline (pp); 4390 m_merged_model->dump_to_pp (pp, simple, true); 4391 pp_newline (pp); 4392} 4393 4394/* Dump a multiline representation of this merger to FILE. */ 4395 4396void 4397model_merger::dump (FILE *fp, bool simple) const 4398{ 4399 pretty_printer pp; 4400 pp_format_decoder (&pp) = default_tree_printer; 4401 pp_show_color (&pp) = pp_show_color (global_dc->printer); 4402 pp.buffer->stream = fp; 4403 dump_to_pp (&pp, simple); 4404 pp_flush (&pp); 4405} 4406 4407/* Dump a multiline representation of this merger to stderr. */ 4408 4409DEBUG_FUNCTION void 4410model_merger::dump (bool simple) const 4411{ 4412 dump (stderr, simple); 4413} 4414 4415/* Return true if it's OK to merge SVAL with other svalues. */ 4416 4417bool 4418model_merger::mergeable_svalue_p (const svalue *sval) const 4419{ 4420 if (m_ext_state) 4421 { 4422 /* Reject merging svalues that have non-purgable sm-state, 4423 to avoid falsely reporting memory leaks by merging them 4424 with something else. For example, given a local var "p", 4425 reject the merger of a: 4426 store_a mapping "p" to a malloc-ed ptr 4427 with: 4428 store_b mapping "p" to a NULL ptr. */ 4429 if (m_state_a) 4430 if (!m_state_a->can_purge_p (*m_ext_state, sval)) 4431 return false; 4432 if (m_state_b) 4433 if (!m_state_b->can_purge_p (*m_ext_state, sval)) 4434 return false; 4435 } 4436 return true; 4437} 4438 4439} // namespace ana 4440 4441/* Dump RMODEL fully to stderr (i.e. without summarization). */ 4442 4443DEBUG_FUNCTION void 4444debug (const region_model &rmodel) 4445{ 4446 rmodel.dump (false); 4447} 4448 4449/* class rejected_op_constraint : public rejected_constraint. */ 4450 4451void 4452rejected_op_constraint::dump_to_pp (pretty_printer *pp) const 4453{ 4454 region_model m (m_model); 4455 const svalue *lhs_sval = m.get_rvalue (m_lhs, NULL); 4456 const svalue *rhs_sval = m.get_rvalue (m_rhs, NULL); 4457 lhs_sval->dump_to_pp (pp, true); 4458 pp_printf (pp, " %s ", op_symbol_code (m_op)); 4459 rhs_sval->dump_to_pp (pp, true); 4460} 4461 4462/* class rejected_ranges_constraint : public rejected_constraint. */ 4463 4464void 4465rejected_ranges_constraint::dump_to_pp (pretty_printer *pp) const 4466{ 4467 region_model m (m_model); 4468 const svalue *sval = m.get_rvalue (m_expr, NULL); 4469 sval->dump_to_pp (pp, true); 4470 pp_string (pp, " in "); 4471 m_ranges->dump_to_pp (pp, true); 4472} 4473 4474/* class engine. */ 4475 4476/* engine's ctor. */ 4477 4478engine::engine (const supergraph *sg, logger *logger) 4479: m_sg (sg), m_mgr (logger) 4480{ 4481} 4482 4483/* Dump the managed objects by class to LOGGER, and the per-class totals. */ 4484 4485void 4486engine::log_stats (logger *logger) const 4487{ 4488 m_mgr.log_stats (logger, true); 4489} 4490 4491namespace ana { 4492 4493#if CHECKING_P 4494 4495namespace selftest { 4496 4497/* Build a constant tree of the given type from STR. */ 4498 4499static tree 4500build_real_cst_from_string (tree type, const char *str) 4501{ 4502 REAL_VALUE_TYPE real; 4503 real_from_string (&real, str); 4504 return build_real (type, real); 4505} 4506 4507/* Append various "interesting" constants to OUT (e.g. NaN). */ 4508 4509static void 4510append_interesting_constants (auto_vec<tree> *out) 4511{ 4512 out->safe_push (build_int_cst (integer_type_node, 0)); 4513 out->safe_push (build_int_cst (integer_type_node, 42)); 4514 out->safe_push (build_int_cst (unsigned_type_node, 0)); 4515 out->safe_push (build_int_cst (unsigned_type_node, 42)); 4516 out->safe_push (build_real_cst_from_string (float_type_node, "QNaN")); 4517 out->safe_push (build_real_cst_from_string (float_type_node, "-QNaN")); 4518 out->safe_push (build_real_cst_from_string (float_type_node, "SNaN")); 4519 out->safe_push (build_real_cst_from_string (float_type_node, "-SNaN")); 4520 out->safe_push (build_real_cst_from_string (float_type_node, "0.0")); 4521 out->safe_push (build_real_cst_from_string (float_type_node, "-0.0")); 4522 out->safe_push (build_real_cst_from_string (float_type_node, "Inf")); 4523 out->safe_push (build_real_cst_from_string (float_type_node, "-Inf")); 4524} 4525 4526/* Verify that tree_cmp is a well-behaved comparator for qsort, even 4527 if the underlying constants aren't comparable. */ 4528 4529static void 4530test_tree_cmp_on_constants () 4531{ 4532 auto_vec<tree> csts; 4533 append_interesting_constants (&csts); 4534 4535 /* Try sorting every triple. */ 4536 const unsigned num = csts.length (); 4537 for (unsigned i = 0; i < num; i++) 4538 for (unsigned j = 0; j < num; j++) 4539 for (unsigned k = 0; k < num; k++) 4540 { 4541 auto_vec<tree> v (3); 4542 v.quick_push (csts[i]); 4543 v.quick_push (csts[j]); 4544 v.quick_push (csts[k]); 4545 v.qsort (tree_cmp); 4546 } 4547} 4548 4549/* Implementation detail of the ASSERT_CONDITION_* macros. */ 4550 4551void 4552assert_condition (const location &loc, 4553 region_model &model, 4554 const svalue *lhs, tree_code op, const svalue *rhs, 4555 tristate expected) 4556{ 4557 tristate actual = model.eval_condition (lhs, op, rhs); 4558 ASSERT_EQ_AT (loc, actual, expected); 4559} 4560 4561/* Implementation detail of the ASSERT_CONDITION_* macros. */ 4562 4563void 4564assert_condition (const location &loc, 4565 region_model &model, 4566 tree lhs, tree_code op, tree rhs, 4567 tristate expected) 4568{ 4569 tristate actual = model.eval_condition (lhs, op, rhs, NULL); 4570 ASSERT_EQ_AT (loc, actual, expected); 4571} 4572 4573/* Implementation detail of ASSERT_DUMP_TREE_EQ. */ 4574 4575static void 4576assert_dump_tree_eq (const location &loc, tree t, const char *expected) 4577{ 4578 auto_fix_quotes sentinel; 4579 pretty_printer pp; 4580 pp_format_decoder (&pp) = default_tree_printer; 4581 dump_tree (&pp, t); 4582 ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected); 4583} 4584 4585/* Assert that dump_tree (T) is EXPECTED. */ 4586 4587#define ASSERT_DUMP_TREE_EQ(T, EXPECTED) \ 4588 SELFTEST_BEGIN_STMT \ 4589 assert_dump_tree_eq ((SELFTEST_LOCATION), (T), (EXPECTED)); \ 4590 SELFTEST_END_STMT 4591 4592/* Implementation detail of ASSERT_DUMP_EQ. */ 4593 4594static void 4595assert_dump_eq (const location &loc, 4596 const region_model &model, 4597 bool summarize, 4598 const char *expected) 4599{ 4600 auto_fix_quotes sentinel; 4601 pretty_printer pp; 4602 pp_format_decoder (&pp) = default_tree_printer; 4603 4604 model.dump_to_pp (&pp, summarize, true); 4605 ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected); 4606} 4607 4608/* Assert that MODEL.dump_to_pp (SUMMARIZE) is EXPECTED. */ 4609 4610#define ASSERT_DUMP_EQ(MODEL, SUMMARIZE, EXPECTED) \ 4611 SELFTEST_BEGIN_STMT \ 4612 assert_dump_eq ((SELFTEST_LOCATION), (MODEL), (SUMMARIZE), (EXPECTED)); \ 4613 SELFTEST_END_STMT 4614 4615/* Smoketest for region_model::dump_to_pp. */ 4616 4617static void 4618test_dump () 4619{ 4620 region_model_manager mgr; 4621 region_model model (&mgr); 4622 4623 ASSERT_DUMP_EQ (model, false, 4624 "stack depth: 0\n" 4625 "m_called_unknown_fn: FALSE\n" 4626 "constraint_manager:\n" 4627 " equiv classes:\n" 4628 " constraints:\n"); 4629 ASSERT_DUMP_EQ (model, true, 4630 "stack depth: 0\n" 4631 "m_called_unknown_fn: FALSE\n" 4632 "constraint_manager:\n" 4633 " equiv classes:\n" 4634 " constraints:\n"); 4635} 4636 4637/* Helper function for selftests. Create a struct or union type named NAME, 4638 with the fields given by the FIELD_DECLS in FIELDS. 4639 If IS_STRUCT is true create a RECORD_TYPE (aka a struct), otherwise 4640 create a UNION_TYPE. */ 4641 4642static tree 4643make_test_compound_type (const char *name, bool is_struct, 4644 const auto_vec<tree> *fields) 4645{ 4646 tree t = make_node (is_struct ? RECORD_TYPE : UNION_TYPE); 4647 TYPE_NAME (t) = get_identifier (name); 4648 TYPE_SIZE (t) = 0; 4649 4650 tree fieldlist = NULL; 4651 int i; 4652 tree field; 4653 FOR_EACH_VEC_ELT (*fields, i, field) 4654 { 4655 gcc_assert (TREE_CODE (field) == FIELD_DECL); 4656 DECL_CONTEXT (field) = t; 4657 fieldlist = chainon (field, fieldlist); 4658 } 4659 fieldlist = nreverse (fieldlist); 4660 TYPE_FIELDS (t) = fieldlist; 4661 4662 layout_type (t); 4663 return t; 4664} 4665 4666/* Selftest fixture for creating the type "struct coord {int x; int y; };". */ 4667 4668struct coord_test 4669{ 4670 coord_test () 4671 { 4672 auto_vec<tree> fields; 4673 m_x_field = build_decl (UNKNOWN_LOCATION, FIELD_DECL, 4674 get_identifier ("x"), integer_type_node); 4675 fields.safe_push (m_x_field); 4676 m_y_field = build_decl (UNKNOWN_LOCATION, FIELD_DECL, 4677 get_identifier ("y"), integer_type_node); 4678 fields.safe_push (m_y_field); 4679 m_coord_type = make_test_compound_type ("coord", true, &fields); 4680 } 4681 4682 tree m_x_field; 4683 tree m_y_field; 4684 tree m_coord_type; 4685}; 4686 4687/* Verify usage of a struct. */ 4688 4689static void 4690test_struct () 4691{ 4692 coord_test ct; 4693 4694 tree c = build_global_decl ("c", ct.m_coord_type); 4695 tree c_x = build3 (COMPONENT_REF, TREE_TYPE (ct.m_x_field), 4696 c, ct.m_x_field, NULL_TREE); 4697 tree c_y = build3 (COMPONENT_REF, TREE_TYPE (ct.m_y_field), 4698 c, ct.m_y_field, NULL_TREE); 4699 4700 tree int_17 = build_int_cst (integer_type_node, 17); 4701 tree int_m3 = build_int_cst (integer_type_node, -3); 4702 4703 region_model_manager mgr; 4704 region_model model (&mgr); 4705 model.set_value (c_x, int_17, NULL); 4706 model.set_value (c_y, int_m3, NULL); 4707 4708 /* Verify get_offset for "c.x". */ 4709 { 4710 const region *c_x_reg = model.get_lvalue (c_x, NULL); 4711 region_offset offset = c_x_reg->get_offset (); 4712 ASSERT_EQ (offset.get_base_region (), model.get_lvalue (c, NULL)); 4713 ASSERT_EQ (offset.get_bit_offset (), 0); 4714 } 4715 4716 /* Verify get_offset for "c.y". */ 4717 { 4718 const region *c_y_reg = model.get_lvalue (c_y, NULL); 4719 region_offset offset = c_y_reg->get_offset (); 4720 ASSERT_EQ (offset.get_base_region (), model.get_lvalue (c, NULL)); 4721 ASSERT_EQ (offset.get_bit_offset (), INT_TYPE_SIZE); 4722 } 4723} 4724 4725/* Verify usage of an array element. */ 4726 4727static void 4728test_array_1 () 4729{ 4730 tree tlen = size_int (10); 4731 tree arr_type = build_array_type (char_type_node, build_index_type (tlen)); 4732 4733 tree a = build_global_decl ("a", arr_type); 4734 4735 region_model_manager mgr; 4736 region_model model (&mgr); 4737 tree int_0 = build_int_cst (integer_type_node, 0); 4738 tree a_0 = build4 (ARRAY_REF, char_type_node, 4739 a, int_0, NULL_TREE, NULL_TREE); 4740 tree char_A = build_int_cst (char_type_node, 'A'); 4741 model.set_value (a_0, char_A, NULL); 4742} 4743 4744/* Verify that region_model::get_representative_tree works as expected. */ 4745 4746static void 4747test_get_representative_tree () 4748{ 4749 region_model_manager mgr; 4750 4751 /* STRING_CST. */ 4752 { 4753 tree string_cst = build_string (4, "foo"); 4754 region_model m (&mgr); 4755 const svalue *str_sval = m.get_rvalue (string_cst, NULL); 4756 tree rep = m.get_representative_tree (str_sval); 4757 ASSERT_EQ (rep, string_cst); 4758 } 4759 4760 /* String literal. */ 4761 { 4762 tree string_cst_ptr = build_string_literal (4, "foo"); 4763 region_model m (&mgr); 4764 const svalue *str_sval = m.get_rvalue (string_cst_ptr, NULL); 4765 tree rep = m.get_representative_tree (str_sval); 4766 ASSERT_DUMP_TREE_EQ (rep, "&\"foo\"[0]"); 4767 } 4768 4769 /* Value of an element within an array. */ 4770 { 4771 tree tlen = size_int (10); 4772 tree arr_type = build_array_type (char_type_node, build_index_type (tlen)); 4773 tree a = build_global_decl ("a", arr_type); 4774 placeholder_svalue test_sval (char_type_node, "test value"); 4775 4776 /* Value of a[3]. */ 4777 { 4778 test_region_model_context ctxt; 4779 region_model model (&mgr); 4780 tree int_3 = build_int_cst (integer_type_node, 3); 4781 tree a_3 = build4 (ARRAY_REF, char_type_node, 4782 a, int_3, NULL_TREE, NULL_TREE); 4783 const region *a_3_reg = model.get_lvalue (a_3, &ctxt); 4784 model.set_value (a_3_reg, &test_sval, &ctxt); 4785 tree rep = model.get_representative_tree (&test_sval); 4786 ASSERT_DUMP_TREE_EQ (rep, "a[3]"); 4787 } 4788 4789 /* Value of a[0]. */ 4790 { 4791 test_region_model_context ctxt; 4792 region_model model (&mgr); 4793 tree idx = build_int_cst (integer_type_node, 0); 4794 tree a_0 = build4 (ARRAY_REF, char_type_node, 4795 a, idx, NULL_TREE, NULL_TREE); 4796 const region *a_0_reg = model.get_lvalue (a_0, &ctxt); 4797 model.set_value (a_0_reg, &test_sval, &ctxt); 4798 tree rep = model.get_representative_tree (&test_sval); 4799 ASSERT_DUMP_TREE_EQ (rep, "a[0]"); 4800 } 4801 } 4802 4803 /* Value of a field within a struct. */ 4804 { 4805 coord_test ct; 4806 4807 tree c = build_global_decl ("c", ct.m_coord_type); 4808 tree c_x = build3 (COMPONENT_REF, TREE_TYPE (ct.m_x_field), 4809 c, ct.m_x_field, NULL_TREE); 4810 tree c_y = build3 (COMPONENT_REF, TREE_TYPE (ct.m_y_field), 4811 c, ct.m_y_field, NULL_TREE); 4812 4813 test_region_model_context ctxt; 4814 4815 /* Value of initial field. */ 4816 { 4817 region_model m (&mgr); 4818 const region *c_x_reg = m.get_lvalue (c_x, &ctxt); 4819 placeholder_svalue test_sval_x (integer_type_node, "test x val"); 4820 m.set_value (c_x_reg, &test_sval_x, &ctxt); 4821 tree rep = m.get_representative_tree (&test_sval_x); 4822 ASSERT_DUMP_TREE_EQ (rep, "c.x"); 4823 } 4824 4825 /* Value of non-initial field. */ 4826 { 4827 region_model m (&mgr); 4828 const region *c_y_reg = m.get_lvalue (c_y, &ctxt); 4829 placeholder_svalue test_sval_y (integer_type_node, "test y val"); 4830 m.set_value (c_y_reg, &test_sval_y, &ctxt); 4831 tree rep = m.get_representative_tree (&test_sval_y); 4832 ASSERT_DUMP_TREE_EQ (rep, "c.y"); 4833 } 4834 } 4835} 4836 4837/* Verify that calling region_model::get_rvalue repeatedly on the same 4838 tree constant retrieves the same svalue *. */ 4839 4840static void 4841test_unique_constants () 4842{ 4843 tree int_0 = build_int_cst (integer_type_node, 0); 4844 tree int_42 = build_int_cst (integer_type_node, 42); 4845 4846 test_region_model_context ctxt; 4847 region_model_manager mgr; 4848 region_model model (&mgr); 4849 ASSERT_EQ (model.get_rvalue (int_0, &ctxt), model.get_rvalue (int_0, &ctxt)); 4850 ASSERT_EQ (model.get_rvalue (int_42, &ctxt), 4851 model.get_rvalue (int_42, &ctxt)); 4852 ASSERT_NE (model.get_rvalue (int_0, &ctxt), model.get_rvalue (int_42, &ctxt)); 4853 ASSERT_EQ (ctxt.get_num_diagnostics (), 0); 4854 4855 /* A "(const int)42" will be a different tree from "(int)42)"... */ 4856 tree const_int_type_node 4857 = build_qualified_type (integer_type_node, TYPE_QUAL_CONST); 4858 tree const_int_42 = build_int_cst (const_int_type_node, 42); 4859 ASSERT_NE (int_42, const_int_42); 4860 /* It should have a different const_svalue. */ 4861 const svalue *int_42_sval = model.get_rvalue (int_42, &ctxt); 4862 const svalue *const_int_42_sval = model.get_rvalue (const_int_42, &ctxt); 4863 ASSERT_NE (int_42_sval, const_int_42_sval); 4864 /* But they should compare as equal. */ 4865 ASSERT_CONDITION_TRUE (model, int_42_sval, EQ_EXPR, const_int_42_sval); 4866 ASSERT_CONDITION_FALSE (model, int_42_sval, NE_EXPR, const_int_42_sval); 4867} 4868 4869/* Verify that each type gets its own singleton unknown_svalue within a 4870 region_model_manager, and that NULL_TREE gets its own singleton. */ 4871 4872static void 4873test_unique_unknowns () 4874{ 4875 region_model_manager mgr; 4876 const svalue *unknown_int 4877 = mgr.get_or_create_unknown_svalue (integer_type_node); 4878 /* Repeated calls with the same type should get the same "unknown" 4879 svalue. */ 4880 const svalue *unknown_int_2 4881 = mgr.get_or_create_unknown_svalue (integer_type_node); 4882 ASSERT_EQ (unknown_int, unknown_int_2); 4883 4884 /* Different types (or the NULL type) should have different 4885 unknown_svalues. */ 4886 const svalue *unknown_NULL_type = mgr.get_or_create_unknown_svalue (NULL); 4887 ASSERT_NE (unknown_NULL_type, unknown_int); 4888 4889 /* Repeated calls with NULL for the type should get the same "unknown" 4890 svalue. */ 4891 const svalue *unknown_NULL_type_2 = mgr.get_or_create_unknown_svalue (NULL); 4892 ASSERT_EQ (unknown_NULL_type, unknown_NULL_type_2); 4893} 4894 4895/* Verify that initial_svalue are handled as expected. */ 4896 4897static void 4898test_initial_svalue_folding () 4899{ 4900 region_model_manager mgr; 4901 tree x = build_global_decl ("x", integer_type_node); 4902 tree y = build_global_decl ("y", integer_type_node); 4903 4904 test_region_model_context ctxt; 4905 region_model model (&mgr); 4906 const svalue *x_init = model.get_rvalue (x, &ctxt); 4907 const svalue *y_init = model.get_rvalue (y, &ctxt); 4908 ASSERT_NE (x_init, y_init); 4909 const region *x_reg = model.get_lvalue (x, &ctxt); 4910 ASSERT_EQ (x_init, mgr.get_or_create_initial_value (x_reg)); 4911 4912} 4913 4914/* Verify that unary ops are folded as expected. */ 4915 4916static void 4917test_unaryop_svalue_folding () 4918{ 4919 region_model_manager mgr; 4920 tree x = build_global_decl ("x", integer_type_node); 4921 tree y = build_global_decl ("y", integer_type_node); 4922 4923 test_region_model_context ctxt; 4924 region_model model (&mgr); 4925 const svalue *x_init = model.get_rvalue (x, &ctxt); 4926 const svalue *y_init = model.get_rvalue (y, &ctxt); 4927 const region *x_reg = model.get_lvalue (x, &ctxt); 4928 ASSERT_EQ (x_init, mgr.get_or_create_initial_value (x_reg)); 4929 4930 /* "(int)x" -> "x". */ 4931 ASSERT_EQ (x_init, mgr.get_or_create_cast (integer_type_node, x_init)); 4932 4933 /* "(void *)x" -> something other than "x". */ 4934 ASSERT_NE (x_init, mgr.get_or_create_cast (ptr_type_node, x_init)); 4935 4936 /* "!(x == y)" -> "x != y". */ 4937 ASSERT_EQ (mgr.get_or_create_unaryop 4938 (boolean_type_node, TRUTH_NOT_EXPR, 4939 mgr.get_or_create_binop (boolean_type_node, EQ_EXPR, 4940 x_init, y_init)), 4941 mgr.get_or_create_binop (boolean_type_node, NE_EXPR, 4942 x_init, y_init)); 4943 /* "!(x > y)" -> "x <= y". */ 4944 ASSERT_EQ (mgr.get_or_create_unaryop 4945 (boolean_type_node, TRUTH_NOT_EXPR, 4946 mgr.get_or_create_binop (boolean_type_node, GT_EXPR, 4947 x_init, y_init)), 4948 mgr.get_or_create_binop (boolean_type_node, LE_EXPR, 4949 x_init, y_init)); 4950} 4951 4952/* Verify that binops on constant svalues are folded. */ 4953 4954static void 4955test_binop_svalue_folding () 4956{ 4957#define NUM_CSTS 10 4958 tree cst_int[NUM_CSTS]; 4959 region_model_manager mgr; 4960 const svalue *cst_sval[NUM_CSTS]; 4961 for (int i = 0; i < NUM_CSTS; i++) 4962 { 4963 cst_int[i] = build_int_cst (integer_type_node, i); 4964 cst_sval[i] = mgr.get_or_create_constant_svalue (cst_int[i]); 4965 ASSERT_EQ (cst_sval[i]->get_kind (), SK_CONSTANT); 4966 ASSERT_EQ (cst_sval[i]->maybe_get_constant (), cst_int[i]); 4967 } 4968 4969 for (int i = 0; i < NUM_CSTS; i++) 4970 for (int j = 0; j < NUM_CSTS; j++) 4971 { 4972 if (i != j) 4973 ASSERT_NE (cst_sval[i], cst_sval[j]); 4974 if (i + j < NUM_CSTS) 4975 { 4976 const svalue *sum 4977 = mgr.get_or_create_binop (integer_type_node, PLUS_EXPR, 4978 cst_sval[i], cst_sval[j]); 4979 ASSERT_EQ (sum, cst_sval[i + j]); 4980 } 4981 if (i - j >= 0) 4982 { 4983 const svalue *difference 4984 = mgr.get_or_create_binop (integer_type_node, MINUS_EXPR, 4985 cst_sval[i], cst_sval[j]); 4986 ASSERT_EQ (difference, cst_sval[i - j]); 4987 } 4988 if (i * j < NUM_CSTS) 4989 { 4990 const svalue *product 4991 = mgr.get_or_create_binop (integer_type_node, MULT_EXPR, 4992 cst_sval[i], cst_sval[j]); 4993 ASSERT_EQ (product, cst_sval[i * j]); 4994 } 4995 const svalue *eq = mgr.get_or_create_binop (integer_type_node, EQ_EXPR, 4996 cst_sval[i], cst_sval[j]); 4997 ASSERT_EQ (eq, i == j ? cst_sval[1] : cst_sval [0]); 4998 const svalue *neq = mgr.get_or_create_binop (integer_type_node, NE_EXPR, 4999 cst_sval[i], cst_sval[j]); 5000 ASSERT_EQ (neq, i != j ? cst_sval[1] : cst_sval [0]); 5001 // etc 5002 } 5003 5004 tree x = build_global_decl ("x", integer_type_node); 5005 5006 test_region_model_context ctxt; 5007 region_model model (&mgr); 5008 const svalue *x_init = model.get_rvalue (x, &ctxt); 5009 5010 /* PLUS_EXPR folding. */ 5011 const svalue *x_init_plus_zero 5012 = mgr.get_or_create_binop (integer_type_node, PLUS_EXPR, 5013 x_init, cst_sval[0]); 5014 ASSERT_EQ (x_init_plus_zero, x_init); 5015 const svalue *zero_plus_x_init 5016 = mgr.get_or_create_binop (integer_type_node, PLUS_EXPR, 5017 cst_sval[0], x_init); 5018 ASSERT_EQ (zero_plus_x_init, x_init); 5019 5020 /* MULT_EXPR folding. */ 5021 const svalue *x_init_times_zero 5022 = mgr.get_or_create_binop (integer_type_node, MULT_EXPR, 5023 x_init, cst_sval[0]); 5024 ASSERT_EQ (x_init_times_zero, cst_sval[0]); 5025 const svalue *zero_times_x_init 5026 = mgr.get_or_create_binop (integer_type_node, MULT_EXPR, 5027 cst_sval[0], x_init); 5028 ASSERT_EQ (zero_times_x_init, cst_sval[0]); 5029 5030 const svalue *x_init_times_one 5031 = mgr.get_or_create_binop (integer_type_node, MULT_EXPR, 5032 x_init, cst_sval[1]); 5033 ASSERT_EQ (x_init_times_one, x_init); 5034 const svalue *one_times_x_init 5035 = mgr.get_or_create_binop (integer_type_node, MULT_EXPR, 5036 cst_sval[1], x_init); 5037 ASSERT_EQ (one_times_x_init, x_init); 5038 5039 // etc 5040 // TODO: do we want to use the match-and-simplify DSL for this? 5041 5042 /* Verify that binops put any constants on the RHS. */ 5043 const svalue *four_times_x_init 5044 = mgr.get_or_create_binop (integer_type_node, MULT_EXPR, 5045 cst_sval[4], x_init); 5046 const svalue *x_init_times_four 5047 = mgr.get_or_create_binop (integer_type_node, MULT_EXPR, 5048 x_init, cst_sval[4]); 5049 ASSERT_EQ (four_times_x_init, x_init_times_four); 5050 const binop_svalue *binop = four_times_x_init->dyn_cast_binop_svalue (); 5051 ASSERT_EQ (binop->get_op (), MULT_EXPR); 5052 ASSERT_EQ (binop->get_arg0 (), x_init); 5053 ASSERT_EQ (binop->get_arg1 (), cst_sval[4]); 5054 5055 /* Verify that ((x + 1) + 1) == (x + 2). */ 5056 const svalue *x_init_plus_one 5057 = mgr.get_or_create_binop (integer_type_node, PLUS_EXPR, 5058 x_init, cst_sval[1]); 5059 const svalue *x_init_plus_two 5060 = mgr.get_or_create_binop (integer_type_node, PLUS_EXPR, 5061 x_init, cst_sval[2]); 5062 const svalue *x_init_plus_one_plus_one 5063 = mgr.get_or_create_binop (integer_type_node, PLUS_EXPR, 5064 x_init_plus_one, cst_sval[1]); 5065 ASSERT_EQ (x_init_plus_one_plus_one, x_init_plus_two); 5066 5067 /* Verify various binops on booleans. */ 5068 { 5069 const svalue *sval_true = mgr.get_or_create_int_cst (boolean_type_node, 1); 5070 const svalue *sval_false = mgr.get_or_create_int_cst (boolean_type_node, 0); 5071 const svalue *sval_unknown 5072 = mgr.get_or_create_unknown_svalue (boolean_type_node); 5073 const placeholder_svalue sval_placeholder (boolean_type_node, "v"); 5074 for (auto op : {BIT_IOR_EXPR, TRUTH_OR_EXPR}) 5075 { 5076 ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op, 5077 sval_true, sval_unknown), 5078 sval_true); 5079 ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op, 5080 sval_false, sval_unknown), 5081 sval_unknown); 5082 ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op, 5083 sval_false, &sval_placeholder), 5084 &sval_placeholder); 5085 } 5086 for (auto op : {BIT_AND_EXPR, TRUTH_AND_EXPR}) 5087 { 5088 ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op, 5089 sval_false, sval_unknown), 5090 sval_false); 5091 ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op, 5092 sval_true, sval_unknown), 5093 sval_unknown); 5094 ASSERT_EQ (mgr.get_or_create_binop (boolean_type_node, op, 5095 sval_true, &sval_placeholder), 5096 &sval_placeholder); 5097 } 5098 } 5099} 5100 5101/* Verify that sub_svalues are folded as expected. */ 5102 5103static void 5104test_sub_svalue_folding () 5105{ 5106 coord_test ct; 5107 tree c = build_global_decl ("c", ct.m_coord_type); 5108 tree c_x = build3 (COMPONENT_REF, TREE_TYPE (ct.m_x_field), 5109 c, ct.m_x_field, NULL_TREE); 5110 5111 region_model_manager mgr; 5112 region_model model (&mgr); 5113 test_region_model_context ctxt; 5114 const region *c_x_reg = model.get_lvalue (c_x, &ctxt); 5115 5116 /* Verify that sub_svalue of "unknown" simply 5117 yields an unknown. */ 5118 5119 const svalue *unknown = mgr.get_or_create_unknown_svalue (ct.m_coord_type); 5120 const svalue *sub = mgr.get_or_create_sub_svalue (TREE_TYPE (ct.m_x_field), 5121 unknown, c_x_reg); 5122 ASSERT_EQ (sub->get_kind (), SK_UNKNOWN); 5123 ASSERT_EQ (sub->get_type (), TREE_TYPE (ct.m_x_field)); 5124} 5125 5126/* Test that region::descendent_of_p works as expected. */ 5127 5128static void 5129test_descendent_of_p () 5130{ 5131 region_model_manager mgr; 5132 const region *stack = mgr.get_stack_region (); 5133 const region *heap = mgr.get_heap_region (); 5134 const region *code = mgr.get_code_region (); 5135 const region *globals = mgr.get_globals_region (); 5136 5137 /* descendent_of_p should return true when used on the region itself. */ 5138 ASSERT_TRUE (stack->descendent_of_p (stack)); 5139 ASSERT_FALSE (stack->descendent_of_p (heap)); 5140 ASSERT_FALSE (stack->descendent_of_p (code)); 5141 ASSERT_FALSE (stack->descendent_of_p (globals)); 5142 5143 tree x = build_global_decl ("x", integer_type_node); 5144 const region *x_reg = mgr.get_region_for_global (x); 5145 ASSERT_TRUE (x_reg->descendent_of_p (globals)); 5146 5147 /* A cast_region should be a descendent of the original region. */ 5148 const region *cast_reg = mgr.get_cast_region (x_reg, ptr_type_node); 5149 ASSERT_TRUE (cast_reg->descendent_of_p (x_reg)); 5150} 5151 5152/* Verify that bit_range_region works as expected. */ 5153 5154static void 5155test_bit_range_regions () 5156{ 5157 tree x = build_global_decl ("x", integer_type_node); 5158 region_model_manager mgr; 5159 const region *x_reg = mgr.get_region_for_global (x); 5160 const region *byte0 5161 = mgr.get_bit_range (x_reg, char_type_node, bit_range (0, 8)); 5162 const region *byte1 5163 = mgr.get_bit_range (x_reg, char_type_node, bit_range (8, 8)); 5164 ASSERT_TRUE (byte0->descendent_of_p (x_reg)); 5165 ASSERT_TRUE (byte1->descendent_of_p (x_reg)); 5166 ASSERT_NE (byte0, byte1); 5167} 5168 5169/* Verify that simple assignments work as expected. */ 5170 5171static void 5172test_assignment () 5173{ 5174 tree int_0 = build_int_cst (integer_type_node, 0); 5175 tree x = build_global_decl ("x", integer_type_node); 5176 tree y = build_global_decl ("y", integer_type_node); 5177 5178 /* "x == 0", then use of y, then "y = 0;". */ 5179 region_model_manager mgr; 5180 region_model model (&mgr); 5181 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0); 5182 ASSERT_CONDITION_UNKNOWN (model, y, EQ_EXPR, int_0); 5183 model.set_value (model.get_lvalue (y, NULL), 5184 model.get_rvalue (int_0, NULL), 5185 NULL); 5186 ASSERT_CONDITION_TRUE (model, y, EQ_EXPR, int_0); 5187 ASSERT_CONDITION_TRUE (model, y, EQ_EXPR, x); 5188} 5189 5190/* Verify that compound assignments work as expected. */ 5191 5192static void 5193test_compound_assignment () 5194{ 5195 coord_test ct; 5196 5197 tree c = build_global_decl ("c", ct.m_coord_type); 5198 tree c_x = build3 (COMPONENT_REF, TREE_TYPE (ct.m_x_field), 5199 c, ct.m_x_field, NULL_TREE); 5200 tree c_y = build3 (COMPONENT_REF, TREE_TYPE (ct.m_y_field), 5201 c, ct.m_y_field, NULL_TREE); 5202 tree d = build_global_decl ("d", ct.m_coord_type); 5203 tree d_x = build3 (COMPONENT_REF, TREE_TYPE (ct.m_x_field), 5204 d, ct.m_x_field, NULL_TREE); 5205 tree d_y = build3 (COMPONENT_REF, TREE_TYPE (ct.m_y_field), 5206 d, ct.m_y_field, NULL_TREE); 5207 5208 tree int_17 = build_int_cst (integer_type_node, 17); 5209 tree int_m3 = build_int_cst (integer_type_node, -3); 5210 5211 region_model_manager mgr; 5212 region_model model (&mgr); 5213 model.set_value (c_x, int_17, NULL); 5214 model.set_value (c_y, int_m3, NULL); 5215 5216 /* Copy c to d. */ 5217 const svalue *sval = model.get_rvalue (c, NULL); 5218 model.set_value (model.get_lvalue (d, NULL), sval, NULL); 5219 5220 /* Check that the fields have the same svalues. */ 5221 ASSERT_EQ (model.get_rvalue (c_x, NULL), model.get_rvalue (d_x, NULL)); 5222 ASSERT_EQ (model.get_rvalue (c_y, NULL), model.get_rvalue (d_y, NULL)); 5223} 5224 5225/* Verify the details of pushing and popping stack frames. */ 5226 5227static void 5228test_stack_frames () 5229{ 5230 tree int_42 = build_int_cst (integer_type_node, 42); 5231 tree int_10 = build_int_cst (integer_type_node, 10); 5232 tree int_5 = build_int_cst (integer_type_node, 5); 5233 tree int_0 = build_int_cst (integer_type_node, 0); 5234 5235 auto_vec <tree> param_types; 5236 tree parent_fndecl = make_fndecl (integer_type_node, 5237 "parent_fn", 5238 param_types); 5239 allocate_struct_function (parent_fndecl, true); 5240 5241 tree child_fndecl = make_fndecl (integer_type_node, 5242 "child_fn", 5243 param_types); 5244 allocate_struct_function (child_fndecl, true); 5245 5246 /* "a" and "b" in the parent frame. */ 5247 tree a = build_decl (UNKNOWN_LOCATION, PARM_DECL, 5248 get_identifier ("a"), 5249 integer_type_node); 5250 DECL_CONTEXT (a) = parent_fndecl; 5251 tree b = build_decl (UNKNOWN_LOCATION, PARM_DECL, 5252 get_identifier ("b"), 5253 integer_type_node); 5254 DECL_CONTEXT (b) = parent_fndecl; 5255 /* "x" and "y" in a child frame. */ 5256 tree x = build_decl (UNKNOWN_LOCATION, PARM_DECL, 5257 get_identifier ("x"), 5258 integer_type_node); 5259 DECL_CONTEXT (x) = child_fndecl; 5260 tree y = build_decl (UNKNOWN_LOCATION, PARM_DECL, 5261 get_identifier ("y"), 5262 integer_type_node); 5263 DECL_CONTEXT (y) = child_fndecl; 5264 5265 /* "p" global. */ 5266 tree p = build_global_decl ("p", ptr_type_node); 5267 5268 /* "q" global. */ 5269 tree q = build_global_decl ("q", ptr_type_node); 5270 5271 region_model_manager mgr; 5272 test_region_model_context ctxt; 5273 region_model model (&mgr); 5274 5275 /* Push stack frame for "parent_fn". */ 5276 const region *parent_frame_reg 5277 = model.push_frame (DECL_STRUCT_FUNCTION (parent_fndecl), 5278 NULL, &ctxt); 5279 ASSERT_EQ (model.get_current_frame (), parent_frame_reg); 5280 ASSERT_TRUE (model.region_exists_p (parent_frame_reg)); 5281 const region *a_in_parent_reg = model.get_lvalue (a, &ctxt); 5282 model.set_value (a_in_parent_reg, 5283 model.get_rvalue (int_42, &ctxt), 5284 &ctxt); 5285 ASSERT_EQ (a_in_parent_reg->maybe_get_frame_region (), parent_frame_reg); 5286 5287 model.add_constraint (b, LT_EXPR, int_10, &ctxt); 5288 ASSERT_EQ (model.eval_condition (b, LT_EXPR, int_10, &ctxt), 5289 tristate (tristate::TS_TRUE)); 5290 5291 /* Push stack frame for "child_fn". */ 5292 const region *child_frame_reg 5293 = model.push_frame (DECL_STRUCT_FUNCTION (child_fndecl), NULL, &ctxt); 5294 ASSERT_EQ (model.get_current_frame (), child_frame_reg); 5295 ASSERT_TRUE (model.region_exists_p (child_frame_reg)); 5296 const region *x_in_child_reg = model.get_lvalue (x, &ctxt); 5297 model.set_value (x_in_child_reg, 5298 model.get_rvalue (int_0, &ctxt), 5299 &ctxt); 5300 ASSERT_EQ (x_in_child_reg->maybe_get_frame_region (), child_frame_reg); 5301 5302 model.add_constraint (y, NE_EXPR, int_5, &ctxt); 5303 ASSERT_EQ (model.eval_condition (y, NE_EXPR, int_5, &ctxt), 5304 tristate (tristate::TS_TRUE)); 5305 5306 /* Point a global pointer at a local in the child frame: p = &x. */ 5307 const region *p_in_globals_reg = model.get_lvalue (p, &ctxt); 5308 model.set_value (p_in_globals_reg, 5309 mgr.get_ptr_svalue (ptr_type_node, x_in_child_reg), 5310 &ctxt); 5311 ASSERT_EQ (p_in_globals_reg->maybe_get_frame_region (), NULL); 5312 5313 /* Point another global pointer at p: q = &p. */ 5314 const region *q_in_globals_reg = model.get_lvalue (q, &ctxt); 5315 model.set_value (q_in_globals_reg, 5316 mgr.get_ptr_svalue (ptr_type_node, p_in_globals_reg), 5317 &ctxt); 5318 5319 /* Test region::descendent_of_p. */ 5320 ASSERT_TRUE (child_frame_reg->descendent_of_p (child_frame_reg)); 5321 ASSERT_TRUE (x_in_child_reg->descendent_of_p (child_frame_reg)); 5322 ASSERT_FALSE (a_in_parent_reg->descendent_of_p (child_frame_reg)); 5323 5324 /* Pop the "child_fn" frame from the stack. */ 5325 model.pop_frame (NULL, NULL, &ctxt); 5326 ASSERT_FALSE (model.region_exists_p (child_frame_reg)); 5327 ASSERT_TRUE (model.region_exists_p (parent_frame_reg)); 5328 5329 /* Verify that p (which was pointing at the local "x" in the popped 5330 frame) has been poisoned. */ 5331 const svalue *new_p_sval = model.get_rvalue (p, NULL); 5332 ASSERT_EQ (new_p_sval->get_kind (), SK_POISONED); 5333 ASSERT_EQ (new_p_sval->dyn_cast_poisoned_svalue ()->get_poison_kind (), 5334 POISON_KIND_POPPED_STACK); 5335 5336 /* Verify that q still points to p, in spite of the region 5337 renumbering. */ 5338 const svalue *new_q_sval = model.get_rvalue (q, &ctxt); 5339 ASSERT_EQ (new_q_sval->get_kind (), SK_REGION); 5340 ASSERT_EQ (new_q_sval->maybe_get_region (), 5341 model.get_lvalue (p, &ctxt)); 5342 5343 /* Verify that top of stack has been updated. */ 5344 ASSERT_EQ (model.get_current_frame (), parent_frame_reg); 5345 5346 /* Verify locals in parent frame. */ 5347 /* Verify "a" still has its value. */ 5348 const svalue *new_a_sval = model.get_rvalue (a, &ctxt); 5349 ASSERT_EQ (new_a_sval->get_kind (), SK_CONSTANT); 5350 ASSERT_EQ (new_a_sval->dyn_cast_constant_svalue ()->get_constant (), 5351 int_42); 5352 /* Verify "b" still has its constraint. */ 5353 ASSERT_EQ (model.eval_condition (b, LT_EXPR, int_10, &ctxt), 5354 tristate (tristate::TS_TRUE)); 5355} 5356 5357/* Verify that get_representative_path_var works as expected, that 5358 we can map from regions to parms and back within a recursive call 5359 stack. */ 5360 5361static void 5362test_get_representative_path_var () 5363{ 5364 auto_vec <tree> param_types; 5365 tree fndecl = make_fndecl (integer_type_node, 5366 "factorial", 5367 param_types); 5368 allocate_struct_function (fndecl, true); 5369 5370 /* Parm "n". */ 5371 tree n = build_decl (UNKNOWN_LOCATION, PARM_DECL, 5372 get_identifier ("n"), 5373 integer_type_node); 5374 DECL_CONTEXT (n) = fndecl; 5375 5376 region_model_manager mgr; 5377 test_region_model_context ctxt; 5378 region_model model (&mgr); 5379 5380 /* Push 5 stack frames for "factorial", each with a param */ 5381 auto_vec<const region *> parm_regs; 5382 auto_vec<const svalue *> parm_svals; 5383 for (int depth = 0; depth < 5; depth++) 5384 { 5385 const region *frame_n_reg 5386 = model.push_frame (DECL_STRUCT_FUNCTION (fndecl), NULL, &ctxt); 5387 const region *parm_n_reg = model.get_lvalue (path_var (n, depth), &ctxt); 5388 parm_regs.safe_push (parm_n_reg); 5389 5390 ASSERT_EQ (parm_n_reg->get_parent_region (), frame_n_reg); 5391 const svalue *sval_n = mgr.get_or_create_initial_value (parm_n_reg); 5392 parm_svals.safe_push (sval_n); 5393 } 5394 5395 /* Verify that we can recognize that the regions are the parms, 5396 at every depth. */ 5397 for (int depth = 0; depth < 5; depth++) 5398 { 5399 { 5400 svalue_set visited; 5401 ASSERT_EQ (model.get_representative_path_var (parm_regs[depth], 5402 &visited), 5403 path_var (n, depth + 1)); 5404 } 5405 /* ...and that we can lookup lvalues for locals for all frames, 5406 not just the top. */ 5407 ASSERT_EQ (model.get_lvalue (path_var (n, depth), NULL), 5408 parm_regs[depth]); 5409 /* ...and that we can locate the svalues. */ 5410 { 5411 svalue_set visited; 5412 ASSERT_EQ (model.get_representative_path_var (parm_svals[depth], 5413 &visited), 5414 path_var (n, depth + 1)); 5415 } 5416 } 5417} 5418 5419/* Ensure that region_model::operator== works as expected. */ 5420 5421static void 5422test_equality_1 () 5423{ 5424 tree int_42 = build_int_cst (integer_type_node, 42); 5425 tree int_17 = build_int_cst (integer_type_node, 17); 5426 5427/* Verify that "empty" region_model instances are equal to each other. */ 5428 region_model_manager mgr; 5429 region_model model0 (&mgr); 5430 region_model model1 (&mgr); 5431 ASSERT_EQ (model0, model1); 5432 5433 /* Verify that setting state in model1 makes the models non-equal. */ 5434 tree x = build_global_decl ("x", integer_type_node); 5435 model0.set_value (x, int_42, NULL); 5436 ASSERT_EQ (model0.get_rvalue (x, NULL)->maybe_get_constant (), int_42); 5437 ASSERT_NE (model0, model1); 5438 5439 /* Verify the copy-ctor. */ 5440 region_model model2 (model0); 5441 ASSERT_EQ (model0, model2); 5442 ASSERT_EQ (model2.get_rvalue (x, NULL)->maybe_get_constant (), int_42); 5443 ASSERT_NE (model1, model2); 5444 5445 /* Verify that models obtained from copy-ctor are independently editable 5446 w/o affecting the original model. */ 5447 model2.set_value (x, int_17, NULL); 5448 ASSERT_NE (model0, model2); 5449 ASSERT_EQ (model2.get_rvalue (x, NULL)->maybe_get_constant (), int_17); 5450 ASSERT_EQ (model0.get_rvalue (x, NULL)->maybe_get_constant (), int_42); 5451} 5452 5453/* Verify that region models for 5454 x = 42; y = 113; 5455 and 5456 y = 113; x = 42; 5457 are equal. */ 5458 5459static void 5460test_canonicalization_2 () 5461{ 5462 tree int_42 = build_int_cst (integer_type_node, 42); 5463 tree int_113 = build_int_cst (integer_type_node, 113); 5464 tree x = build_global_decl ("x", integer_type_node); 5465 tree y = build_global_decl ("y", integer_type_node); 5466 5467 region_model_manager mgr; 5468 region_model model0 (&mgr); 5469 model0.set_value (model0.get_lvalue (x, NULL), 5470 model0.get_rvalue (int_42, NULL), 5471 NULL); 5472 model0.set_value (model0.get_lvalue (y, NULL), 5473 model0.get_rvalue (int_113, NULL), 5474 NULL); 5475 5476 region_model model1 (&mgr); 5477 model1.set_value (model1.get_lvalue (y, NULL), 5478 model1.get_rvalue (int_113, NULL), 5479 NULL); 5480 model1.set_value (model1.get_lvalue (x, NULL), 5481 model1.get_rvalue (int_42, NULL), 5482 NULL); 5483 5484 ASSERT_EQ (model0, model1); 5485} 5486 5487/* Verify that constraints for 5488 x > 3 && y > 42 5489 and 5490 y > 42 && x > 3 5491 are equal after canonicalization. */ 5492 5493static void 5494test_canonicalization_3 () 5495{ 5496 tree int_3 = build_int_cst (integer_type_node, 3); 5497 tree int_42 = build_int_cst (integer_type_node, 42); 5498 tree x = build_global_decl ("x", integer_type_node); 5499 tree y = build_global_decl ("y", integer_type_node); 5500 5501 region_model_manager mgr; 5502 region_model model0 (&mgr); 5503 model0.add_constraint (x, GT_EXPR, int_3, NULL); 5504 model0.add_constraint (y, GT_EXPR, int_42, NULL); 5505 5506 region_model model1 (&mgr); 5507 model1.add_constraint (y, GT_EXPR, int_42, NULL); 5508 model1.add_constraint (x, GT_EXPR, int_3, NULL); 5509 5510 model0.canonicalize (); 5511 model1.canonicalize (); 5512 ASSERT_EQ (model0, model1); 5513} 5514 5515/* Verify that we can canonicalize a model containing NaN and other real 5516 constants. */ 5517 5518static void 5519test_canonicalization_4 () 5520{ 5521 auto_vec<tree> csts; 5522 append_interesting_constants (&csts); 5523 5524 region_model_manager mgr; 5525 region_model model (&mgr); 5526 5527 for (tree cst : csts) 5528 model.get_rvalue (cst, NULL); 5529 5530 model.canonicalize (); 5531} 5532 5533/* Assert that if we have two region_model instances 5534 with values VAL_A and VAL_B for EXPR that they are 5535 mergable. Write the merged model to *OUT_MERGED_MODEL, 5536 and the merged svalue ptr to *OUT_MERGED_SVALUE. 5537 If VAL_A or VAL_B are NULL_TREE, don't populate EXPR 5538 for that region_model. */ 5539 5540static void 5541assert_region_models_merge (tree expr, tree val_a, tree val_b, 5542 region_model *out_merged_model, 5543 const svalue **out_merged_svalue) 5544{ 5545 program_point point (program_point::origin ()); 5546 test_region_model_context ctxt; 5547 region_model_manager *mgr = out_merged_model->get_manager (); 5548 region_model model0 (mgr); 5549 region_model model1 (mgr); 5550 if (val_a) 5551 model0.set_value (model0.get_lvalue (expr, &ctxt), 5552 model0.get_rvalue (val_a, &ctxt), 5553 &ctxt); 5554 if (val_b) 5555 model1.set_value (model1.get_lvalue (expr, &ctxt), 5556 model1.get_rvalue (val_b, &ctxt), 5557 &ctxt); 5558 5559 /* They should be mergeable. */ 5560 ASSERT_TRUE (model0.can_merge_with_p (model1, point, out_merged_model)); 5561 *out_merged_svalue = out_merged_model->get_rvalue (expr, &ctxt); 5562} 5563 5564/* Verify that we can merge region_model instances. */ 5565 5566static void 5567test_state_merging () 5568{ 5569 tree int_42 = build_int_cst (integer_type_node, 42); 5570 tree int_113 = build_int_cst (integer_type_node, 113); 5571 tree x = build_global_decl ("x", integer_type_node); 5572 tree y = build_global_decl ("y", integer_type_node); 5573 tree z = build_global_decl ("z", integer_type_node); 5574 tree p = build_global_decl ("p", ptr_type_node); 5575 5576 tree addr_of_y = build1 (ADDR_EXPR, ptr_type_node, y); 5577 tree addr_of_z = build1 (ADDR_EXPR, ptr_type_node, z); 5578 5579 auto_vec <tree> param_types; 5580 tree test_fndecl = make_fndecl (integer_type_node, "test_fn", param_types); 5581 allocate_struct_function (test_fndecl, true); 5582 5583 /* Param "a". */ 5584 tree a = build_decl (UNKNOWN_LOCATION, PARM_DECL, 5585 get_identifier ("a"), 5586 integer_type_node); 5587 DECL_CONTEXT (a) = test_fndecl; 5588 tree addr_of_a = build1 (ADDR_EXPR, ptr_type_node, a); 5589 5590 /* Param "q", a pointer. */ 5591 tree q = build_decl (UNKNOWN_LOCATION, PARM_DECL, 5592 get_identifier ("q"), 5593 ptr_type_node); 5594 DECL_CONTEXT (q) = test_fndecl; 5595 5596 program_point point (program_point::origin ()); 5597 region_model_manager mgr; 5598 5599 { 5600 region_model model0 (&mgr); 5601 region_model model1 (&mgr); 5602 region_model merged (&mgr); 5603 /* Verify empty models can be merged. */ 5604 ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged)); 5605 ASSERT_EQ (model0, merged); 5606 } 5607 5608 /* Verify that we can merge two contradictory constraints on the 5609 value for a global. */ 5610 /* TODO: verify that the merged model doesn't have a value for 5611 the global */ 5612 { 5613 region_model model0 (&mgr); 5614 region_model model1 (&mgr); 5615 region_model merged (&mgr); 5616 test_region_model_context ctxt; 5617 model0.add_constraint (x, EQ_EXPR, int_42, &ctxt); 5618 model1.add_constraint (x, EQ_EXPR, int_113, &ctxt); 5619 ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged)); 5620 ASSERT_NE (model0, merged); 5621 ASSERT_NE (model1, merged); 5622 } 5623 5624 /* Verify handling of a PARM_DECL. */ 5625 { 5626 test_region_model_context ctxt; 5627 region_model model0 (&mgr); 5628 region_model model1 (&mgr); 5629 ASSERT_EQ (model0.get_stack_depth (), 0); 5630 model0.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, &ctxt); 5631 ASSERT_EQ (model0.get_stack_depth (), 1); 5632 model1.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, &ctxt); 5633 5634 placeholder_svalue test_sval (integer_type_node, "test sval"); 5635 model0.set_value (model0.get_lvalue (a, &ctxt), &test_sval, &ctxt); 5636 model1.set_value (model1.get_lvalue (a, &ctxt), &test_sval, &ctxt); 5637 ASSERT_EQ (model0, model1); 5638 5639 /* They should be mergeable, and the result should be the same. */ 5640 region_model merged (&mgr); 5641 ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged)); 5642 ASSERT_EQ (model0, merged); 5643 /* In particular, "a" should have the placeholder value. */ 5644 ASSERT_EQ (merged.get_rvalue (a, &ctxt), &test_sval); 5645 } 5646 5647 /* Verify handling of a global. */ 5648 { 5649 test_region_model_context ctxt; 5650 region_model model0 (&mgr); 5651 region_model model1 (&mgr); 5652 5653 placeholder_svalue test_sval (integer_type_node, "test sval"); 5654 model0.set_value (model0.get_lvalue (x, &ctxt), &test_sval, &ctxt); 5655 model1.set_value (model1.get_lvalue (x, &ctxt), &test_sval, &ctxt); 5656 ASSERT_EQ (model0, model1); 5657 5658 /* They should be mergeable, and the result should be the same. */ 5659 region_model merged (&mgr); 5660 ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged)); 5661 ASSERT_EQ (model0, merged); 5662 /* In particular, "x" should have the placeholder value. */ 5663 ASSERT_EQ (merged.get_rvalue (x, &ctxt), &test_sval); 5664 } 5665 5666 /* Use global-handling to verify various combinations of values. */ 5667 5668 /* Two equal constant values. */ 5669 { 5670 region_model merged (&mgr); 5671 const svalue *merged_x_sval; 5672 assert_region_models_merge (x, int_42, int_42, &merged, &merged_x_sval); 5673 5674 /* In particular, there should be a constant value for "x". */ 5675 ASSERT_EQ (merged_x_sval->get_kind (), SK_CONSTANT); 5676 ASSERT_EQ (merged_x_sval->dyn_cast_constant_svalue ()->get_constant (), 5677 int_42); 5678 } 5679 5680 /* Two non-equal constant values. */ 5681 { 5682 region_model merged (&mgr); 5683 const svalue *merged_x_sval; 5684 assert_region_models_merge (x, int_42, int_113, &merged, &merged_x_sval); 5685 5686 /* In particular, there should be a "widening" value for "x". */ 5687 ASSERT_EQ (merged_x_sval->get_kind (), SK_WIDENING); 5688 } 5689 5690 /* Initial and constant. */ 5691 { 5692 region_model merged (&mgr); 5693 const svalue *merged_x_sval; 5694 assert_region_models_merge (x, NULL_TREE, int_113, &merged, &merged_x_sval); 5695 5696 /* In particular, there should be an unknown value for "x". */ 5697 ASSERT_EQ (merged_x_sval->get_kind (), SK_UNKNOWN); 5698 } 5699 5700 /* Constant and initial. */ 5701 { 5702 region_model merged (&mgr); 5703 const svalue *merged_x_sval; 5704 assert_region_models_merge (x, int_42, NULL_TREE, &merged, &merged_x_sval); 5705 5706 /* In particular, there should be an unknown value for "x". */ 5707 ASSERT_EQ (merged_x_sval->get_kind (), SK_UNKNOWN); 5708 } 5709 5710 /* Unknown and constant. */ 5711 // TODO 5712 5713 /* Pointers: NULL and NULL. */ 5714 // TODO 5715 5716 /* Pointers: NULL and non-NULL. */ 5717 // TODO 5718 5719 /* Pointers: non-NULL and non-NULL: ptr to a local. */ 5720 { 5721 region_model model0 (&mgr); 5722 model0.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, NULL); 5723 model0.set_value (model0.get_lvalue (p, NULL), 5724 model0.get_rvalue (addr_of_a, NULL), NULL); 5725 5726 region_model model1 (model0); 5727 ASSERT_EQ (model0, model1); 5728 5729 /* They should be mergeable, and the result should be the same. */ 5730 region_model merged (&mgr); 5731 ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged)); 5732 ASSERT_EQ (model0, merged); 5733 } 5734 5735 /* Pointers: non-NULL and non-NULL: ptr to a global. */ 5736 { 5737 region_model merged (&mgr); 5738 /* p == &y in both input models. */ 5739 const svalue *merged_p_sval; 5740 assert_region_models_merge (p, addr_of_y, addr_of_y, &merged, 5741 &merged_p_sval); 5742 5743 /* We should get p == &y in the merged model. */ 5744 ASSERT_EQ (merged_p_sval->get_kind (), SK_REGION); 5745 const region_svalue *merged_p_ptr 5746 = merged_p_sval->dyn_cast_region_svalue (); 5747 const region *merged_p_star_reg = merged_p_ptr->get_pointee (); 5748 ASSERT_EQ (merged_p_star_reg, merged.get_lvalue (y, NULL)); 5749 } 5750 5751 /* Pointers: non-NULL ptrs to different globals: should be unknown. */ 5752 { 5753 region_model merged (&mgr); 5754 /* x == &y vs x == &z in the input models; these are actually casts 5755 of the ptrs to "int". */ 5756 const svalue *merged_x_sval; 5757 // TODO: 5758 assert_region_models_merge (x, addr_of_y, addr_of_z, &merged, 5759 &merged_x_sval); 5760 5761 /* We should get x == unknown in the merged model. */ 5762 ASSERT_EQ (merged_x_sval->get_kind (), SK_UNKNOWN); 5763 } 5764 5765 /* Pointers: non-NULL and non-NULL: ptr to a heap region. */ 5766 { 5767 test_region_model_context ctxt; 5768 region_model model0 (&mgr); 5769 tree size = build_int_cst (size_type_node, 1024); 5770 const svalue *size_sval = mgr.get_or_create_constant_svalue (size); 5771 const region *new_reg 5772 = model0.create_region_for_heap_alloc (size_sval, &ctxt); 5773 const svalue *ptr_sval = mgr.get_ptr_svalue (ptr_type_node, new_reg); 5774 model0.set_value (model0.get_lvalue (p, &ctxt), 5775 ptr_sval, &ctxt); 5776 5777 region_model model1 (model0); 5778 5779 ASSERT_EQ (model0, model1); 5780 5781 region_model merged (&mgr); 5782 ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged)); 5783 5784 /* The merged model ought to be identical. */ 5785 ASSERT_EQ (model0, merged); 5786 } 5787 5788 /* Two regions sharing the same placeholder svalue should continue sharing 5789 it after self-merger. */ 5790 { 5791 test_region_model_context ctxt; 5792 region_model model0 (&mgr); 5793 placeholder_svalue placeholder_sval (integer_type_node, "test"); 5794 model0.set_value (model0.get_lvalue (x, &ctxt), 5795 &placeholder_sval, &ctxt); 5796 model0.set_value (model0.get_lvalue (y, &ctxt), &placeholder_sval, &ctxt); 5797 region_model model1 (model0); 5798 5799 /* They should be mergeable, and the result should be the same. */ 5800 region_model merged (&mgr); 5801 ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged)); 5802 ASSERT_EQ (model0, merged); 5803 5804 /* In particular, we should have x == y. */ 5805 ASSERT_EQ (merged.eval_condition (x, EQ_EXPR, y, &ctxt), 5806 tristate (tristate::TS_TRUE)); 5807 } 5808 5809 { 5810 region_model model0 (&mgr); 5811 region_model model1 (&mgr); 5812 test_region_model_context ctxt; 5813 model0.add_constraint (x, EQ_EXPR, int_42, &ctxt); 5814 model1.add_constraint (x, NE_EXPR, int_42, &ctxt); 5815 region_model merged (&mgr); 5816 ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged)); 5817 } 5818 5819 { 5820 region_model model0 (&mgr); 5821 region_model model1 (&mgr); 5822 test_region_model_context ctxt; 5823 model0.add_constraint (x, EQ_EXPR, int_42, &ctxt); 5824 model1.add_constraint (x, NE_EXPR, int_42, &ctxt); 5825 model1.add_constraint (x, EQ_EXPR, int_113, &ctxt); 5826 region_model merged (&mgr); 5827 ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged)); 5828 } 5829 5830 // TODO: what can't we merge? need at least one such test 5831 5832 /* TODO: various things 5833 - heap regions 5834 - value merging: 5835 - every combination, but in particular 5836 - pairs of regions 5837 */ 5838 5839 /* Views. */ 5840 { 5841 test_region_model_context ctxt; 5842 region_model model0 (&mgr); 5843 5844 const region *x_reg = model0.get_lvalue (x, &ctxt); 5845 const region *x_as_ptr = mgr.get_cast_region (x_reg, ptr_type_node); 5846 model0.set_value (x_as_ptr, model0.get_rvalue (addr_of_y, &ctxt), &ctxt); 5847 5848 region_model model1 (model0); 5849 ASSERT_EQ (model1, model0); 5850 5851 /* They should be mergeable, and the result should be the same. */ 5852 region_model merged (&mgr); 5853 ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged)); 5854 } 5855 5856 /* Verify that we can merge a model in which a local in an older stack 5857 frame points to a local in a more recent stack frame. */ 5858 { 5859 region_model model0 (&mgr); 5860 model0.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, NULL); 5861 const region *q_in_first_frame = model0.get_lvalue (q, NULL); 5862 5863 /* Push a second frame. */ 5864 const region *reg_2nd_frame 5865 = model0.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, NULL); 5866 5867 /* Have a pointer in the older frame point to a local in the 5868 more recent frame. */ 5869 const svalue *sval_ptr = model0.get_rvalue (addr_of_a, NULL); 5870 model0.set_value (q_in_first_frame, sval_ptr, NULL); 5871 5872 /* Verify that it's pointing at the newer frame. */ 5873 const region *reg_pointee = sval_ptr->maybe_get_region (); 5874 ASSERT_EQ (reg_pointee->get_parent_region (), reg_2nd_frame); 5875 5876 model0.canonicalize (); 5877 5878 region_model model1 (model0); 5879 ASSERT_EQ (model0, model1); 5880 5881 /* They should be mergeable, and the result should be the same 5882 (after canonicalization, at least). */ 5883 region_model merged (&mgr); 5884 ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged)); 5885 merged.canonicalize (); 5886 ASSERT_EQ (model0, merged); 5887 } 5888 5889 /* Verify that we can merge a model in which a local points to a global. */ 5890 { 5891 region_model model0 (&mgr); 5892 model0.push_frame (DECL_STRUCT_FUNCTION (test_fndecl), NULL, NULL); 5893 model0.set_value (model0.get_lvalue (q, NULL), 5894 model0.get_rvalue (addr_of_y, NULL), NULL); 5895 5896 region_model model1 (model0); 5897 ASSERT_EQ (model0, model1); 5898 5899 /* They should be mergeable, and the result should be the same 5900 (after canonicalization, at least). */ 5901 region_model merged (&mgr); 5902 ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged)); 5903 ASSERT_EQ (model0, merged); 5904 } 5905} 5906 5907/* Verify that constraints are correctly merged when merging region_model 5908 instances. */ 5909 5910static void 5911test_constraint_merging () 5912{ 5913 tree int_0 = build_int_cst (integer_type_node, 0); 5914 tree int_5 = build_int_cst (integer_type_node, 5); 5915 tree x = build_global_decl ("x", integer_type_node); 5916 tree y = build_global_decl ("y", integer_type_node); 5917 tree z = build_global_decl ("z", integer_type_node); 5918 tree n = build_global_decl ("n", integer_type_node); 5919 5920 region_model_manager mgr; 5921 test_region_model_context ctxt; 5922 5923 /* model0: 0 <= (x == y) < n. */ 5924 region_model model0 (&mgr); 5925 model0.add_constraint (x, EQ_EXPR, y, &ctxt); 5926 model0.add_constraint (x, GE_EXPR, int_0, NULL); 5927 model0.add_constraint (x, LT_EXPR, n, NULL); 5928 5929 /* model1: z != 5 && (0 <= x < n). */ 5930 region_model model1 (&mgr); 5931 model1.add_constraint (z, NE_EXPR, int_5, NULL); 5932 model1.add_constraint (x, GE_EXPR, int_0, NULL); 5933 model1.add_constraint (x, LT_EXPR, n, NULL); 5934 5935 /* They should be mergeable; the merged constraints should 5936 be: (0 <= x < n). */ 5937 program_point point (program_point::origin ()); 5938 region_model merged (&mgr); 5939 ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged)); 5940 5941 ASSERT_EQ (merged.eval_condition (x, GE_EXPR, int_0, &ctxt), 5942 tristate (tristate::TS_TRUE)); 5943 ASSERT_EQ (merged.eval_condition (x, LT_EXPR, n, &ctxt), 5944 tristate (tristate::TS_TRUE)); 5945 5946 ASSERT_EQ (merged.eval_condition (z, NE_EXPR, int_5, &ctxt), 5947 tristate (tristate::TS_UNKNOWN)); 5948 ASSERT_EQ (merged.eval_condition (x, LT_EXPR, y, &ctxt), 5949 tristate (tristate::TS_UNKNOWN)); 5950} 5951 5952/* Verify that widening_svalue::eval_condition_without_cm works as 5953 expected. */ 5954 5955static void 5956test_widening_constraints () 5957{ 5958 program_point point (program_point::origin ()); 5959 tree int_0 = build_int_cst (integer_type_node, 0); 5960 tree int_m1 = build_int_cst (integer_type_node, -1); 5961 tree int_1 = build_int_cst (integer_type_node, 1); 5962 tree int_256 = build_int_cst (integer_type_node, 256); 5963 region_model_manager mgr; 5964 test_region_model_context ctxt; 5965 const svalue *int_0_sval = mgr.get_or_create_constant_svalue (int_0); 5966 const svalue *int_1_sval = mgr.get_or_create_constant_svalue (int_1); 5967 const svalue *w_zero_then_one_sval 5968 = mgr.get_or_create_widening_svalue (integer_type_node, point, 5969 int_0_sval, int_1_sval); 5970 const widening_svalue *w_zero_then_one 5971 = w_zero_then_one_sval->dyn_cast_widening_svalue (); 5972 ASSERT_EQ (w_zero_then_one->get_direction (), 5973 widening_svalue::DIR_ASCENDING); 5974 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (LT_EXPR, int_m1), 5975 tristate::TS_FALSE); 5976 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (LT_EXPR, int_0), 5977 tristate::TS_FALSE); 5978 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (LT_EXPR, int_1), 5979 tristate::TS_UNKNOWN); 5980 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (LT_EXPR, int_256), 5981 tristate::TS_UNKNOWN); 5982 5983 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (LE_EXPR, int_m1), 5984 tristate::TS_FALSE); 5985 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (LE_EXPR, int_0), 5986 tristate::TS_UNKNOWN); 5987 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (LE_EXPR, int_1), 5988 tristate::TS_UNKNOWN); 5989 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (LE_EXPR, int_256), 5990 tristate::TS_UNKNOWN); 5991 5992 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (GT_EXPR, int_m1), 5993 tristate::TS_TRUE); 5994 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (GT_EXPR, int_0), 5995 tristate::TS_UNKNOWN); 5996 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (GT_EXPR, int_1), 5997 tristate::TS_UNKNOWN); 5998 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (GT_EXPR, int_256), 5999 tristate::TS_UNKNOWN); 6000 6001 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (GE_EXPR, int_m1), 6002 tristate::TS_TRUE); 6003 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (GE_EXPR, int_0), 6004 tristate::TS_TRUE); 6005 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (GE_EXPR, int_1), 6006 tristate::TS_UNKNOWN); 6007 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (GE_EXPR, int_256), 6008 tristate::TS_UNKNOWN); 6009 6010 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (EQ_EXPR, int_m1), 6011 tristate::TS_FALSE); 6012 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (EQ_EXPR, int_0), 6013 tristate::TS_UNKNOWN); 6014 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (EQ_EXPR, int_1), 6015 tristate::TS_UNKNOWN); 6016 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (EQ_EXPR, int_256), 6017 tristate::TS_UNKNOWN); 6018 6019 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (NE_EXPR, int_m1), 6020 tristate::TS_TRUE); 6021 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (NE_EXPR, int_0), 6022 tristate::TS_UNKNOWN); 6023 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (NE_EXPR, int_1), 6024 tristate::TS_UNKNOWN); 6025 ASSERT_EQ (w_zero_then_one->eval_condition_without_cm (NE_EXPR, int_256), 6026 tristate::TS_UNKNOWN); 6027} 6028 6029/* Verify merging constraints for states simulating successive iterations 6030 of a loop. 6031 Simulate: 6032 for (i = 0; i < 256; i++) 6033 [...body...] 6034 i.e. this gimple:. 6035 i_15 = 0; 6036 goto <bb 4>; 6037 6038 <bb 4> : 6039 i_11 = PHI <i_15(2), i_23(3)> 6040 if (i_11 <= 255) 6041 goto <bb 3>; 6042 else 6043 goto [AFTER LOOP] 6044 6045 <bb 3> : 6046 [LOOP BODY] 6047 i_23 = i_11 + 1; 6048 6049 and thus these ops (and resultant states): 6050 i_11 = PHI() 6051 {i_11: 0} 6052 add_constraint (i_11 <= 255) [for the true edge] 6053 {i_11: 0} [constraint was a no-op] 6054 i_23 = i_11 + 1; 6055 {i_22: 1} 6056 i_11 = PHI() 6057 {i_11: WIDENED (at phi, 0, 1)} 6058 add_constraint (i_11 <= 255) [for the true edge] 6059 {i_11: WIDENED (at phi, 0, 1); WIDENED <= 255} 6060 i_23 = i_11 + 1; 6061 {i_23: (WIDENED (at phi, 0, 1) + 1); WIDENED <= 255} 6062 i_11 = PHI(); merge with state at phi above 6063 {i_11: WIDENED (at phi, 0, 1); WIDENED <= 256} 6064 [changing meaning of "WIDENED" here] 6065 if (i_11 <= 255) 6066 T: {i_11: WIDENED (at phi, 0, 1); WIDENED <= 255}; cache hit 6067 F: {i_11: 256} 6068 */ 6069 6070static void 6071test_iteration_1 () 6072{ 6073 program_point point (program_point::origin ()); 6074 6075 tree int_0 = build_int_cst (integer_type_node, 0); 6076 tree int_1 = build_int_cst (integer_type_node, 1); 6077 tree int_256 = build_int_cst (integer_type_node, 256); 6078 tree int_257 = build_int_cst (integer_type_node, 257); 6079 tree i = build_global_decl ("i", integer_type_node); 6080 6081 region_model_manager mgr; 6082 test_region_model_context ctxt; 6083 6084 /* model0: i: 0. */ 6085 region_model model0 (&mgr); 6086 model0.set_value (i, int_0, &ctxt); 6087 6088 /* model1: i: 1. */ 6089 region_model model1 (&mgr); 6090 model1.set_value (i, int_1, &ctxt); 6091 6092 /* Should merge "i" to a widened value. */ 6093 region_model model2 (&mgr); 6094 ASSERT_TRUE (model1.can_merge_with_p (model0, point, &model2)); 6095 const svalue *merged_i = model2.get_rvalue (i, &ctxt); 6096 ASSERT_EQ (merged_i->get_kind (), SK_WIDENING); 6097 const widening_svalue *w = merged_i->dyn_cast_widening_svalue (); 6098 ASSERT_EQ (w->get_direction (), widening_svalue::DIR_ASCENDING); 6099 6100 /* Add constraint: i < 256 */ 6101 model2.add_constraint (i, LT_EXPR, int_256, &ctxt); 6102 ASSERT_EQ (model2.eval_condition (i, LT_EXPR, int_256, &ctxt), 6103 tristate (tristate::TS_TRUE)); 6104 ASSERT_EQ (model2.eval_condition (i, GE_EXPR, int_0, &ctxt), 6105 tristate (tristate::TS_TRUE)); 6106 6107 /* Try merging with the initial state. */ 6108 region_model model3 (&mgr); 6109 ASSERT_TRUE (model2.can_merge_with_p (model0, point, &model3)); 6110 /* Merging the merged value with the initial value should be idempotent, 6111 so that the analysis converges. */ 6112 ASSERT_EQ (model3.get_rvalue (i, &ctxt), merged_i); 6113 /* Merger of 0 and a widening value with constraint < CST 6114 should retain the constraint, even though it was implicit 6115 for the 0 case. */ 6116 ASSERT_EQ (model3.eval_condition (i, LT_EXPR, int_256, &ctxt), 6117 tristate (tristate::TS_TRUE)); 6118 /* ...and we should have equality: the analysis should have converged. */ 6119 ASSERT_EQ (model3, model2); 6120 6121 /* "i_23 = i_11 + 1;" */ 6122 region_model model4 (model3); 6123 ASSERT_EQ (model4, model2); 6124 model4.set_value (i, build2 (PLUS_EXPR, integer_type_node, i, int_1), &ctxt); 6125 const svalue *plus_one = model4.get_rvalue (i, &ctxt); 6126 ASSERT_EQ (plus_one->get_kind (), SK_BINOP); 6127 6128 /* Try merging with the "i: 1" state. */ 6129 region_model model5 (&mgr); 6130 ASSERT_TRUE (model4.can_merge_with_p (model1, point, &model5)); 6131 ASSERT_EQ (model5.get_rvalue (i, &ctxt), plus_one); 6132 ASSERT_EQ (model5, model4); 6133 6134 /* "i_11 = PHI();" merge with state at phi above. 6135 For i, we should have a merger of WIDENING with WIDENING + 1, 6136 and this should be WIDENING again. */ 6137 region_model model6 (&mgr); 6138 ASSERT_TRUE (model5.can_merge_with_p (model2, point, &model6)); 6139 const svalue *merged_widening = model6.get_rvalue (i, &ctxt); 6140 ASSERT_EQ (merged_widening->get_kind (), SK_WIDENING); 6141 6142 ASSERT_CONDITION_TRUE (model6, i, LT_EXPR, int_257); 6143} 6144 6145/* Verify that if we mark a pointer to a malloc-ed region as non-NULL, 6146 all cast pointers to that region are also known to be non-NULL. */ 6147 6148static void 6149test_malloc_constraints () 6150{ 6151 region_model_manager mgr; 6152 region_model model (&mgr); 6153 tree p = build_global_decl ("p", ptr_type_node); 6154 tree char_star = build_pointer_type (char_type_node); 6155 tree q = build_global_decl ("q", char_star); 6156 tree null_ptr = build_int_cst (ptr_type_node, 0); 6157 6158 const svalue *size_in_bytes 6159 = mgr.get_or_create_unknown_svalue (size_type_node); 6160 const region *reg = model.create_region_for_heap_alloc (size_in_bytes, NULL); 6161 const svalue *sval = mgr.get_ptr_svalue (ptr_type_node, reg); 6162 model.set_value (model.get_lvalue (p, NULL), sval, NULL); 6163 model.set_value (q, p, NULL); 6164 6165 ASSERT_CONDITION_UNKNOWN (model, p, NE_EXPR, null_ptr); 6166 ASSERT_CONDITION_UNKNOWN (model, p, EQ_EXPR, null_ptr); 6167 ASSERT_CONDITION_UNKNOWN (model, q, NE_EXPR, null_ptr); 6168 ASSERT_CONDITION_UNKNOWN (model, q, EQ_EXPR, null_ptr); 6169 6170 model.add_constraint (p, NE_EXPR, null_ptr, NULL); 6171 6172 ASSERT_CONDITION_TRUE (model, p, NE_EXPR, null_ptr); 6173 ASSERT_CONDITION_FALSE (model, p, EQ_EXPR, null_ptr); 6174 ASSERT_CONDITION_TRUE (model, q, NE_EXPR, null_ptr); 6175 ASSERT_CONDITION_FALSE (model, q, EQ_EXPR, null_ptr); 6176} 6177 6178/* Smoketest of getting and setting the value of a variable. */ 6179 6180static void 6181test_var () 6182{ 6183 /* "int i;" */ 6184 tree i = build_global_decl ("i", integer_type_node); 6185 6186 tree int_17 = build_int_cst (integer_type_node, 17); 6187 tree int_m3 = build_int_cst (integer_type_node, -3); 6188 6189 region_model_manager mgr; 6190 region_model model (&mgr); 6191 6192 const region *i_reg = model.get_lvalue (i, NULL); 6193 ASSERT_EQ (i_reg->get_kind (), RK_DECL); 6194 6195 /* Reading "i" should give a symbolic "initial value". */ 6196 const svalue *sval_init = model.get_rvalue (i, NULL); 6197 ASSERT_EQ (sval_init->get_kind (), SK_INITIAL); 6198 ASSERT_EQ (sval_init->dyn_cast_initial_svalue ()->get_region (), i_reg); 6199 /* ..and doing it again should give the same "initial value". */ 6200 ASSERT_EQ (model.get_rvalue (i, NULL), sval_init); 6201 6202 /* "i = 17;". */ 6203 model.set_value (i, int_17, NULL); 6204 ASSERT_EQ (model.get_rvalue (i, NULL), 6205 model.get_rvalue (int_17, NULL)); 6206 6207 /* "i = -3;". */ 6208 model.set_value (i, int_m3, NULL); 6209 ASSERT_EQ (model.get_rvalue (i, NULL), 6210 model.get_rvalue (int_m3, NULL)); 6211 6212 /* Verify get_offset for "i". */ 6213 { 6214 region_offset offset = i_reg->get_offset (); 6215 ASSERT_EQ (offset.get_base_region (), i_reg); 6216 ASSERT_EQ (offset.get_bit_offset (), 0); 6217 } 6218} 6219 6220static void 6221test_array_2 () 6222{ 6223 /* "int arr[10];" */ 6224 tree tlen = size_int (10); 6225 tree arr_type 6226 = build_array_type (integer_type_node, build_index_type (tlen)); 6227 tree arr = build_global_decl ("arr", arr_type); 6228 6229 /* "int i;" */ 6230 tree i = build_global_decl ("i", integer_type_node); 6231 6232 tree int_0 = build_int_cst (integer_type_node, 0); 6233 tree int_1 = build_int_cst (integer_type_node, 1); 6234 6235 tree arr_0 = build4 (ARRAY_REF, integer_type_node, 6236 arr, int_0, NULL_TREE, NULL_TREE); 6237 tree arr_1 = build4 (ARRAY_REF, integer_type_node, 6238 arr, int_1, NULL_TREE, NULL_TREE); 6239 tree arr_i = build4 (ARRAY_REF, integer_type_node, 6240 arr, i, NULL_TREE, NULL_TREE); 6241 6242 tree int_17 = build_int_cst (integer_type_node, 17); 6243 tree int_42 = build_int_cst (integer_type_node, 42); 6244 tree int_m3 = build_int_cst (integer_type_node, -3); 6245 6246 region_model_manager mgr; 6247 region_model model (&mgr); 6248 /* "arr[0] = 17;". */ 6249 model.set_value (arr_0, int_17, NULL); 6250 /* "arr[1] = -3;". */ 6251 model.set_value (arr_1, int_m3, NULL); 6252 6253 ASSERT_EQ (model.get_rvalue (arr_0, NULL), model.get_rvalue (int_17, NULL)); 6254 ASSERT_EQ (model.get_rvalue (arr_1, NULL), model.get_rvalue (int_m3, NULL)); 6255 6256 /* Overwrite a pre-existing binding: "arr[1] = 42;". */ 6257 model.set_value (arr_1, int_42, NULL); 6258 ASSERT_EQ (model.get_rvalue (arr_1, NULL), model.get_rvalue (int_42, NULL)); 6259 6260 /* Verify get_offset for "arr[0]". */ 6261 { 6262 const region *arr_0_reg = model.get_lvalue (arr_0, NULL); 6263 region_offset offset = arr_0_reg->get_offset (); 6264 ASSERT_EQ (offset.get_base_region (), model.get_lvalue (arr, NULL)); 6265 ASSERT_EQ (offset.get_bit_offset (), 0); 6266 } 6267 6268 /* Verify get_offset for "arr[1]". */ 6269 { 6270 const region *arr_1_reg = model.get_lvalue (arr_1, NULL); 6271 region_offset offset = arr_1_reg->get_offset (); 6272 ASSERT_EQ (offset.get_base_region (), model.get_lvalue (arr, NULL)); 6273 ASSERT_EQ (offset.get_bit_offset (), INT_TYPE_SIZE); 6274 } 6275 6276 /* "arr[i] = i;" - this should remove the earlier bindings. */ 6277 model.set_value (arr_i, i, NULL); 6278 ASSERT_EQ (model.get_rvalue (arr_i, NULL), model.get_rvalue (i, NULL)); 6279 ASSERT_EQ (model.get_rvalue (arr_0, NULL)->get_kind (), SK_UNKNOWN); 6280 6281 /* "arr[0] = 17;" - this should remove the arr[i] binding. */ 6282 model.set_value (arr_0, int_17, NULL); 6283 ASSERT_EQ (model.get_rvalue (arr_0, NULL), model.get_rvalue (int_17, NULL)); 6284 ASSERT_EQ (model.get_rvalue (arr_i, NULL)->get_kind (), SK_UNKNOWN); 6285} 6286 6287/* Smoketest of dereferencing a pointer via MEM_REF. */ 6288 6289static void 6290test_mem_ref () 6291{ 6292 /* 6293 x = 17; 6294 p = &x; 6295 *p; 6296 */ 6297 tree x = build_global_decl ("x", integer_type_node); 6298 tree int_star = build_pointer_type (integer_type_node); 6299 tree p = build_global_decl ("p", int_star); 6300 6301 tree int_17 = build_int_cst (integer_type_node, 17); 6302 tree addr_of_x = build1 (ADDR_EXPR, int_star, x); 6303 tree offset_0 = build_int_cst (integer_type_node, 0); 6304 tree star_p = build2 (MEM_REF, integer_type_node, p, offset_0); 6305 6306 region_model_manager mgr; 6307 region_model model (&mgr); 6308 6309 /* "x = 17;". */ 6310 model.set_value (x, int_17, NULL); 6311 6312 /* "p = &x;". */ 6313 model.set_value (p, addr_of_x, NULL); 6314 6315 const svalue *sval = model.get_rvalue (star_p, NULL); 6316 ASSERT_EQ (sval->maybe_get_constant (), int_17); 6317} 6318 6319/* Test for a POINTER_PLUS_EXPR followed by a MEM_REF. 6320 Analogous to this code: 6321 void test_6 (int a[10]) 6322 { 6323 __analyzer_eval (a[3] == 42); [should be UNKNOWN] 6324 a[3] = 42; 6325 __analyzer_eval (a[3] == 42); [should be TRUE] 6326 } 6327 from data-model-1.c, which looks like this at the gimple level: 6328 # __analyzer_eval (a[3] == 42); [should be UNKNOWN] 6329 int *_1 = a_10(D) + 12; # POINTER_PLUS_EXPR 6330 int _2 = *_1; # MEM_REF 6331 _Bool _3 = _2 == 42; 6332 int _4 = (int) _3; 6333 __analyzer_eval (_4); 6334 6335 # a[3] = 42; 6336 int *_5 = a_10(D) + 12; # POINTER_PLUS_EXPR 6337 *_5 = 42; # MEM_REF 6338 6339 # __analyzer_eval (a[3] == 42); [should be TRUE] 6340 int *_6 = a_10(D) + 12; # POINTER_PLUS_EXPR 6341 int _7 = *_6; # MEM_REF 6342 _Bool _8 = _7 == 42; 6343 int _9 = (int) _8; 6344 __analyzer_eval (_9); */ 6345 6346static void 6347test_POINTER_PLUS_EXPR_then_MEM_REF () 6348{ 6349 tree int_star = build_pointer_type (integer_type_node); 6350 tree a = build_global_decl ("a", int_star); 6351 tree offset_12 = build_int_cst (size_type_node, 12); 6352 tree pointer_plus_expr = build2 (POINTER_PLUS_EXPR, int_star, a, offset_12); 6353 tree offset_0 = build_int_cst (integer_type_node, 0); 6354 tree mem_ref = build2 (MEM_REF, integer_type_node, 6355 pointer_plus_expr, offset_0); 6356 region_model_manager mgr; 6357 region_model m (&mgr); 6358 6359 tree int_42 = build_int_cst (integer_type_node, 42); 6360 m.set_value (mem_ref, int_42, NULL); 6361 ASSERT_EQ (m.get_rvalue (mem_ref, NULL)->maybe_get_constant (), int_42); 6362} 6363 6364/* Verify that malloc works. */ 6365 6366static void 6367test_malloc () 6368{ 6369 tree int_star = build_pointer_type (integer_type_node); 6370 tree p = build_global_decl ("p", int_star); 6371 tree n = build_global_decl ("n", integer_type_node); 6372 tree n_times_4 = build2 (MULT_EXPR, size_type_node, 6373 n, build_int_cst (size_type_node, 4)); 6374 6375 region_model_manager mgr; 6376 test_region_model_context ctxt; 6377 region_model model (&mgr); 6378 6379 /* "p = malloc (n * 4);". */ 6380 const svalue *size_sval = model.get_rvalue (n_times_4, &ctxt); 6381 const region *reg = model.create_region_for_heap_alloc (size_sval, &ctxt); 6382 const svalue *ptr = mgr.get_ptr_svalue (int_star, reg); 6383 model.set_value (model.get_lvalue (p, &ctxt), ptr, &ctxt); 6384 ASSERT_EQ (model.get_capacity (reg), size_sval); 6385} 6386 6387/* Verify that alloca works. */ 6388 6389static void 6390test_alloca () 6391{ 6392 auto_vec <tree> param_types; 6393 tree fndecl = make_fndecl (integer_type_node, 6394 "test_fn", 6395 param_types); 6396 allocate_struct_function (fndecl, true); 6397 6398 6399 tree int_star = build_pointer_type (integer_type_node); 6400 tree p = build_global_decl ("p", int_star); 6401 tree n = build_global_decl ("n", integer_type_node); 6402 tree n_times_4 = build2 (MULT_EXPR, size_type_node, 6403 n, build_int_cst (size_type_node, 4)); 6404 6405 region_model_manager mgr; 6406 test_region_model_context ctxt; 6407 region_model model (&mgr); 6408 6409 /* Push stack frame. */ 6410 const region *frame_reg 6411 = model.push_frame (DECL_STRUCT_FUNCTION (fndecl), 6412 NULL, &ctxt); 6413 /* "p = alloca (n * 4);". */ 6414 const svalue *size_sval = model.get_rvalue (n_times_4, &ctxt); 6415 const region *reg = model.create_region_for_alloca (size_sval, &ctxt); 6416 ASSERT_EQ (reg->get_parent_region (), frame_reg); 6417 const svalue *ptr = mgr.get_ptr_svalue (int_star, reg); 6418 model.set_value (model.get_lvalue (p, &ctxt), ptr, &ctxt); 6419 ASSERT_EQ (model.get_capacity (reg), size_sval); 6420 6421 /* Verify that the pointers to the alloca region are replaced by 6422 poisoned values when the frame is popped. */ 6423 model.pop_frame (NULL, NULL, &ctxt); 6424 ASSERT_EQ (model.get_rvalue (p, NULL)->get_kind (), SK_POISONED); 6425} 6426 6427/* Verify that svalue::involves_p works. */ 6428 6429static void 6430test_involves_p () 6431{ 6432 region_model_manager mgr; 6433 tree int_star = build_pointer_type (integer_type_node); 6434 tree p = build_global_decl ("p", int_star); 6435 tree q = build_global_decl ("q", int_star); 6436 6437 test_region_model_context ctxt; 6438 region_model model (&mgr); 6439 const svalue *p_init = model.get_rvalue (p, &ctxt); 6440 const svalue *q_init = model.get_rvalue (q, &ctxt); 6441 6442 ASSERT_TRUE (p_init->involves_p (p_init)); 6443 ASSERT_FALSE (p_init->involves_p (q_init)); 6444 6445 const region *star_p_reg = mgr.get_symbolic_region (p_init); 6446 const region *star_q_reg = mgr.get_symbolic_region (q_init); 6447 6448 const svalue *init_star_p = mgr.get_or_create_initial_value (star_p_reg); 6449 const svalue *init_star_q = mgr.get_or_create_initial_value (star_q_reg); 6450 6451 ASSERT_TRUE (init_star_p->involves_p (p_init)); 6452 ASSERT_FALSE (p_init->involves_p (init_star_p)); 6453 ASSERT_FALSE (init_star_p->involves_p (q_init)); 6454 ASSERT_TRUE (init_star_q->involves_p (q_init)); 6455 ASSERT_FALSE (init_star_q->involves_p (p_init)); 6456} 6457 6458/* Run all of the selftests within this file. */ 6459 6460void 6461analyzer_region_model_cc_tests () 6462{ 6463 test_tree_cmp_on_constants (); 6464 test_dump (); 6465 test_struct (); 6466 test_array_1 (); 6467 test_get_representative_tree (); 6468 test_unique_constants (); 6469 test_unique_unknowns (); 6470 test_initial_svalue_folding (); 6471 test_unaryop_svalue_folding (); 6472 test_binop_svalue_folding (); 6473 test_sub_svalue_folding (); 6474 test_descendent_of_p (); 6475 test_bit_range_regions (); 6476 test_assignment (); 6477 test_compound_assignment (); 6478 test_stack_frames (); 6479 test_get_representative_path_var (); 6480 test_equality_1 (); 6481 test_canonicalization_2 (); 6482 test_canonicalization_3 (); 6483 test_canonicalization_4 (); 6484 test_state_merging (); 6485 test_constraint_merging (); 6486 test_widening_constraints (); 6487 test_iteration_1 (); 6488 test_malloc_constraints (); 6489 test_var (); 6490 test_array_2 (); 6491 test_mem_ref (); 6492 test_POINTER_PLUS_EXPR_then_MEM_REF (); 6493 test_malloc (); 6494 test_alloca (); 6495 test_involves_p (); 6496} 6497 6498} // namespace selftest 6499 6500#endif /* CHECKING_P */ 6501 6502} // namespace ana 6503 6504#endif /* #if ENABLE_ANALYZER */ 6505