gcc/analyzer/region.cc

   1 /* Regions of memory.
   2    Copyright (C) 2019-2021 Free Software Foundation, Inc.
   3    Contributed by David Malcolm <dmalcolm@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along 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 "diagnostic-core.h"
  26 #include "gimple-pretty-print.h"
  27 #include "function.h"
  28 #include "basic-block.h"
  29 #include "gimple.h"
  30 #include "gimple-iterator.h"
  31 #include "diagnostic-core.h"
  32 #include "graphviz.h"
  33 #include "options.h"
  34 #include "cgraph.h"
  35 #include "tree-dfa.h"
  36 #include "stringpool.h"
  37 #include "convert.h"
  38 #include "target.h"
  39 #include "fold-const.h"
  40 #include "tree-pretty-print.h"
  41 #include "diagnostic-color.h"
  42 #include "diagnostic-metadata.h"
  43 #include "tristate.h"
  44 #include "bitmap.h"
  45 #include "selftest.h"
  46 #include "function.h"
  47 #include "json.h"
  48 #include "analyzer/analyzer.h"
  49 #include "analyzer/analyzer-logging.h"
  50 #include "ordered-hash-map.h"
  51 #include "options.h"
  52 #include "cgraph.h"
  53 #include "cfg.h"
  54 #include "digraph.h"
  55 #include "analyzer/supergraph.h"
  56 #include "sbitmap.h"
  57 #include "analyzer/call-string.h"
  58 #include "analyzer/program-point.h"
  59 #include "analyzer/store.h"
  60 #include "analyzer/region.h"
  61 #include "analyzer/region-model.h"
  62
  63 #if ENABLE_ANALYZER
  64
  65 namespace ana {
  66
  67 /* class region and its various subclasses.  */
  68
  69 /* class region.  */
  70
  71 region::~region ()
  72 {
  73   delete m_cached_offset;
  74 }
  75
  76 /* Compare REG1 and REG2 by id.  */
  77
  78 int
  79 region::cmp_ids (const region *reg1, const region *reg2)
  80 {
  81   return (long)reg1->get_id () - (long)reg2->get_id ();
  82 }
  83
  84 /* Determine the base region for this region: when considering bindings
  85    for this region, the base region is the ancestor which identifies
  86    which cluster they should be partitioned into.
  87    Regions within the same struct/union/array are in the same cluster.
  88    Different decls are in different clusters.  */
  89
  90 const region *
  91 region::get_base_region () const
  92 {
  93   const region *iter = this;
  94   while (iter)
  95     {
  96       switch (iter->get_kind ())
  97         {
  98         case RK_FIELD:
  99         case RK_ELEMENT:
 100         case RK_OFFSET:
 101         case RK_SIZED:
 102           iter = iter->get_parent_region ();
 103           continue;
 104         case RK_CAST:
 105           iter = iter->dyn_cast_cast_region ()->get_original_region ();
 106           continue;
 107         default:
 108           return iter;
 109         }
 110     }
 111   return iter;
 112 }
 113
 114 /* Return true if get_base_region() == this for this region.  */
 115
 116 bool
 117 region::base_region_p () const
 118 {
 119   switch (get_kind ())
 120     {
 121     /* Region kinds representing a descendent of a base region.  */
 122     case RK_FIELD:
 123     case RK_ELEMENT:
 124     case RK_OFFSET:
 125     case RK_SIZED:
 126     case RK_CAST:
 127       return false;
 128
 129     default:
 130       return true;
 131     }
 132 }
 133
 134 /* Return true if this region is ELDER or one of its descendents.  */
 135
 136 bool
 137 region::descendent_of_p (const region *elder) const
 138 {
 139   const region *iter = this;
 140   while (iter)
 141     {
 142       if (iter == elder)
 143         return true;
 144       if (iter->get_kind () == RK_CAST)
 145         iter = iter->dyn_cast_cast_region ()->get_original_region ();
 146       else
 147         iter = iter->get_parent_region ();
 148     }
 149   return false;
 150 }
 151
 152 /* If this region is a frame_region, or a descendent of one, return it.
 153    Otherwise return NULL.  */
 154
 155 const frame_region *
 156 region::maybe_get_frame_region () const
 157 {
 158   const region *iter = this;
 159   while (iter)
 160     {
 161       if (const frame_region *frame_reg = iter->dyn_cast_frame_region ())
 162         return frame_reg;
 163       if (iter->get_kind () == RK_CAST)
 164         iter = iter->dyn_cast_cast_region ()->get_original_region ();
 165       else
 166         iter = iter->get_parent_region ();
 167     }
 168   return NULL;
 169 }
 170
 171 /* If this region is a decl_region, return the decl.
 172    Otherwise return NULL.  */
 173
 174 tree
 175 region::maybe_get_decl () const
 176 {
 177   if (const decl_region *decl_reg = dyn_cast_decl_region ())
 178     return decl_reg->get_decl ();
 179   return NULL_TREE;
 180 }
 181
 182 /* Get the region_offset for this region (calculating it on the
 183    first call and caching it internally).  */
 184
 185 region_offset
 186 region::get_offset () const
 187 {
 188   if(!m_cached_offset)
 189     m_cached_offset = new region_offset (calc_offset ());
 190   return *m_cached_offset;
 191 }
 192
 193 /* Base class implementation of region::get_byte_size vfunc.
 194    If the size of this region (in bytes) is known statically, write it to *OUT
 195    and return true.
 196    Otherwise return false.  */
 197
 198 bool
 199 region::get_byte_size (byte_size_t *out) const
 200 {
 201   tree type = get_type ();
 202
 203   /* Bail out e.g. for heap-allocated regions.  */
 204   if (!type)
 205     return false;
 206
 207   HOST_WIDE_INT bytes = int_size_in_bytes (type);
 208   if (bytes == -1)
 209     return false;
 210   *out = bytes;
 211   return true;
 212 }
 213
 214 /* Base implementation of region::get_byte_size_sval vfunc.  */
 215
 216 const svalue *
 217 region::get_byte_size_sval (region_model_manager *mgr) const
 218 {
 219   tree type = get_type ();
 220
 221   /* Bail out e.g. for heap-allocated regions.  */
 222   if (!type)
 223     return mgr->get_or_create_unknown_svalue (size_type_node);
 224
 225   HOST_WIDE_INT bytes = int_size_in_bytes (type);
 226   if (bytes == -1)
 227     return mgr->get_or_create_unknown_svalue (size_type_node);
 228
 229   tree byte_size = size_in_bytes (type);
 230   if (TREE_TYPE (byte_size) != size_type_node)
 231     byte_size = fold_build1 (NOP_EXPR, size_type_node, byte_size);
 232   return mgr->get_or_create_constant_svalue (byte_size);
 233 }
 234
 235 /* Attempt to get the size of TYPE in bits.
 236    If successful, return true and write the size to *OUT.
 237    Otherwise return false.  */
 238
 239 bool
 240 int_size_in_bits (const_tree type, bit_size_t *out)
 241 {
 242   if (INTEGRAL_TYPE_P (type))
 243     {
 244       *out = TYPE_PRECISION (type);
 245       return true;
 246     }
 247
 248   tree sz = TYPE_SIZE (type);
 249   if (sz && tree_fits_uhwi_p (sz))
 250     {
 251       *out = TREE_INT_CST_LOW (sz);
 252       return true;
 253     }
 254   else
 255     return false;
 256 }
 257
 258 /* If the size of this region (in bits) is known statically, write it to *OUT
 259    and return true.
 260    Otherwise return false.  */
 261
 262 bool
 263 region::get_bit_size (bit_size_t *out) const
 264 {
 265   tree type = get_type ();
 266
 267   /* Bail out e.g. for heap-allocated regions.  */
 268   if (!type)
 269     return false;
 270
 271   return int_size_in_bits (type, out);
 272 }
 273
 274 /* Get the field within RECORD_TYPE at BIT_OFFSET.  */
 275
 276 tree
 277 get_field_at_bit_offset (tree record_type, bit_offset_t bit_offset)
 278 {
 279   gcc_assert (TREE_CODE (record_type) == RECORD_TYPE);
 280   if (bit_offset < 0)
 281     return NULL;
 282
 283   /* Find the first field that has an offset > BIT_OFFSET,
 284      then return the one preceding it.
 285      Skip other trees within the chain, such as FUNCTION_DECLs.  */
 286   tree last_field = NULL_TREE;
 287   for (tree iter = TYPE_FIELDS (record_type); iter != NULL_TREE;
 288        iter = DECL_CHAIN (iter))
 289     {
 290       if (TREE_CODE (iter) == FIELD_DECL)
 291         {
 292           int iter_field_offset = int_bit_position (iter);
 293           if (bit_offset < iter_field_offset)
 294             return last_field;
 295           last_field = iter;
 296         }
 297     }
 298   return last_field;
 299 }
 300
 301 /* Populate *OUT with descendent regions of type TYPE that match
 302    RELATIVE_BIT_OFFSET and SIZE_IN_BITS within this region.  */
 303
 304 void
 305 region::get_subregions_for_binding (region_model_manager *mgr,
 306                                     bit_offset_t relative_bit_offset,
 307                                     bit_size_t size_in_bits,
 308                                     tree type,
 309                                     auto_vec <const region *> *out) const
 310 {
 311   if (get_type () == NULL_TREE || type == NULL_TREE)
 312     return;
 313   if (relative_bit_offset == 0
 314       && types_compatible_p (get_type (), type))
 315     {
 316       out->safe_push (this);
 317       return;
 318     }
 319   switch (TREE_CODE (get_type ()))
 320     {
 321     case ARRAY_TYPE:
 322       {
 323         tree element_type = TREE_TYPE (get_type ());
 324         HOST_WIDE_INT hwi_byte_size = int_size_in_bytes (element_type);
 325         if (hwi_byte_size > 0)
 326           {
 327             HOST_WIDE_INT bits_per_element
 328               = hwi_byte_size << LOG2_BITS_PER_UNIT;
 329             HOST_WIDE_INT element_index
 330               = (relative_bit_offset.to_shwi () / bits_per_element);
 331             tree element_index_cst
 332               = build_int_cst (integer_type_node, element_index);
 333             HOST_WIDE_INT inner_bit_offset
 334               = relative_bit_offset.to_shwi () % bits_per_element;
 335             const region *subregion = mgr->get_element_region
 336               (this, element_type,
 337                mgr->get_or_create_constant_svalue (element_index_cst));
 338             subregion->get_subregions_for_binding (mgr, inner_bit_offset,
 339                                                    size_in_bits, type, out);
 340           }
 341       }
 342       break;
 343     case RECORD_TYPE:
 344       {
 345         /* The bit offset might be *within* one of the fields (such as
 346            with nested structs).
 347            So we want to find the enclosing field, adjust the offset,
 348            and repeat.  */
 349         if (tree field = get_field_at_bit_offset (get_type (),
 350                                                   relative_bit_offset))
 351           {
 352             int field_bit_offset = int_bit_position (field);
 353             const region *subregion = mgr->get_field_region (this, field);
 354             subregion->get_subregions_for_binding
 355               (mgr, relative_bit_offset - field_bit_offset,
 356                size_in_bits, type, out);
 357           }
 358       }
 359       break;
 360     case UNION_TYPE:
 361       {
 362         for (tree field = TYPE_FIELDS (get_type ()); field != NULL_TREE;
 363              field = DECL_CHAIN (field))
 364           {
 365             if (TREE_CODE (field) != FIELD_DECL)
 366               continue;
 367             const region *subregion = mgr->get_field_region (this, field);
 368             subregion->get_subregions_for_binding (mgr,
 369                                                    relative_bit_offset,
 370                                                    size_in_bits,
 371                                                    type,
 372                                                    out);
 373           }
 374       }
 375       break;
 376     default:
 377       /* Do nothing.  */
 378       break;
 379     }
 380 }
 381
 382 /* Walk from this region up to the base region within its cluster, calculating
 383    the offset relative to the base region, either as an offset in bits,
 384    or a symbolic offset.  */
 385
 386 region_offset
 387 region::calc_offset () const
 388 {
 389   const region *iter_region = this;
 390   bit_offset_t accum_bit_offset = 0;
 391
 392   while (iter_region)
 393     {
 394       switch (iter_region->get_kind ())
 395         {
 396         case RK_FIELD:
 397           {
 398             const field_region *field_reg
 399               = (const field_region *)iter_region;
 400             iter_region = iter_region->get_parent_region ();
 401
 402             bit_offset_t rel_bit_offset;
 403             if (!field_reg->get_relative_concrete_offset (&rel_bit_offset))
 404               return region_offset::make_symbolic (iter_region);
 405             accum_bit_offset += rel_bit_offset;
 406           }
 407           continue;
 408
 409         case RK_ELEMENT:
 410           {
 411             const element_region *element_reg
 412               = (const element_region *)iter_region;
 413             iter_region = iter_region->get_parent_region ();
 414
 415             bit_offset_t rel_bit_offset;
 416             if (!element_reg->get_relative_concrete_offset (&rel_bit_offset))
 417               return region_offset::make_symbolic (iter_region);
 418             accum_bit_offset += rel_bit_offset;
 419           }
 420           continue;
 421
 422         case RK_OFFSET:
 423           {
 424             const offset_region *offset_reg
 425               = (const offset_region *)iter_region;
 426             iter_region = iter_region->get_parent_region ();
 427
 428             bit_offset_t rel_bit_offset;
 429             if (!offset_reg->get_relative_concrete_offset (&rel_bit_offset))
 430               return region_offset::make_symbolic (iter_region);
 431             accum_bit_offset += rel_bit_offset;
 432           }
 433           continue;
 434
 435         case RK_SIZED:
 436           iter_region = iter_region->get_parent_region ();
 437           continue;
 438
 439         case RK_CAST:
 440           {
 441             const cast_region *cast_reg
 442               = as_a <const cast_region *> (iter_region);
 443             iter_region = cast_reg->get_original_region ();
 444           }
 445           continue;
 446
 447         default:
 448           return region_offset::make_concrete (iter_region, accum_bit_offset);
 449         }
 450     }
 451   return region_offset::make_concrete (iter_region, accum_bit_offset);
 452 }
 453
 454 /* Base implementation of region::get_relative_concrete_offset vfunc.  */
 455
 456 bool
 457 region::get_relative_concrete_offset (bit_offset_t *) const
 458 {
 459   return false;
 460 }
 461
 462 /* Copy from SRC_REG to DST_REG, using CTXT for any issues that occur.  */
 463
 464 void
 465 region_model::copy_region (const region *dst_reg, const region *src_reg,
 466                            region_model_context *ctxt)
 467 {
 468   gcc_assert (dst_reg);
 469   gcc_assert (src_reg);
 470   if (dst_reg == src_reg)
 471     return;
 472
 473   const svalue *sval = get_store_value (src_reg);
 474   set_value (dst_reg, sval, ctxt);
 475 }
 476
 477 /* Dump a description of this region to stderr.  */
 478
 479 DEBUG_FUNCTION void
 480 region::dump (bool simple) const
 481 {
 482   pretty_printer pp;
 483   pp_format_decoder (&pp) = default_tree_printer;
 484   pp_show_color (&pp) = pp_show_color (global_dc->printer);
 485   pp.buffer->stream = stderr;
 486   dump_to_pp (&pp, simple);
 487   pp_newline (&pp);
 488   pp_flush (&pp);
 489 }
 490
 491 /* Return a new json::string describing the region.  */
 492
 493 json::value *
 494 region::to_json () const
 495 {
 496   label_text desc = get_desc (true);
 497   json::value *reg_js = new json::string (desc.m_buffer);
 498   desc.maybe_free ();
 499   return reg_js;
 500 }
 501
 502 /* Generate a description of this region.  */
 503
 504 DEBUG_FUNCTION label_text
 505 region::get_desc (bool simple) const
 506 {
 507   pretty_printer pp;
 508   pp_format_decoder (&pp) = default_tree_printer;
 509   dump_to_pp (&pp, simple);
 510   return label_text::take (xstrdup (pp_formatted_text (&pp)));
 511 }
 512
 513 /* Base implementation of region::accept vfunc.
 514    Subclass implementations should chain up to this.  */
 515
 516 void
 517 region::accept (visitor *v) const
 518 {
 519   v->visit_region (this);
 520   if (m_parent)
 521     m_parent->accept (v);
 522 }
 523
 524 /* Return true if this is a symbolic region for deferencing an
 525    unknown ptr.
 526    We shouldn't attempt to bind values for this region (but
 527    can unbind values for other regions).  */
 528
 529 bool
 530 region::symbolic_for_unknown_ptr_p () const
 531 {
 532   if (const symbolic_region *sym_reg = dyn_cast_symbolic_region ())
 533     if (sym_reg->get_pointer ()->get_kind () == SK_UNKNOWN)
 534       return true;
 535   return false;
 536 }
 537
 538 /* region's ctor.  */
 539
 540 region::region (complexity c, unsigned id, const region *parent, tree type)
 541 : m_complexity (c), m_id (id), m_parent (parent), m_type (type),
 542   m_cached_offset (NULL)
 543 {
 544   gcc_assert (type == NULL_TREE || TYPE_P (type));
 545 }
 546
 547 /* Comparator for use by vec<const region *>::qsort,
 548    using their IDs to order them.  */
 549
 550 int
 551 region::cmp_ptr_ptr (const void *p1, const void *p2)
 552 {
 553   const region * const *reg1 = (const region * const *)p1;
 554   const region * const *reg2 = (const region * const *)p2;
 555
 556   return cmp_ids (*reg1, *reg2);
 557 }
 558
 559 /* Determine if a pointer to this region must be non-NULL.
 560
 561    Generally, pointers to regions must be non-NULL, but pointers
 562    to symbolic_regions might, in fact, be NULL.
 563
 564    This allows us to simulate functions like malloc and calloc with:
 565    - only one "outcome" from each statement,
 566    - the idea that the pointer is on the heap if non-NULL
 567    - the possibility that the pointer could be NULL
 568    - the idea that successive values returned from malloc are non-equal
 569    - to be able to zero-fill for calloc.  */
 570
 571 bool
 572 region::non_null_p () const
 573 {
 574   switch (get_kind ())
 575     {
 576     default:
 577       return true;
 578     case RK_SYMBOLIC:
 579       /* Are we within a symbolic_region?  If so, it could be NULL, and we
 580          have to fall back on the constraints.  */
 581       return false;
 582     case RK_HEAP_ALLOCATED:
 583       return false;
 584     }
 585 }
 586
 587 /* Comparator for trees to impose a deterministic ordering on
 588    T1 and T2.  */
 589
 590 static int
 591 tree_cmp (const_tree t1, const_tree t2)
 592 {
 593   gcc_assert (t1);
 594   gcc_assert (t2);
 595
 596   /* Test tree codes first.  */
 597   if (TREE_CODE (t1) != TREE_CODE (t2))
 598     return TREE_CODE (t1) - TREE_CODE (t2);
 599
 600   /* From this point on, we know T1 and T2 have the same tree code.  */
 601
 602   if (DECL_P (t1))
 603     {
 604       if (DECL_NAME (t1) && DECL_NAME (t2))
 605         return strcmp (IDENTIFIER_POINTER (DECL_NAME (t1)),
 606                        IDENTIFIER_POINTER (DECL_NAME (t2)));
 607       else
 608         {
 609           if (DECL_NAME (t1))
 610             return -1;
 611           else if (DECL_NAME (t2))
 612             return 1;
 613           else
 614             return DECL_UID (t1) - DECL_UID (t2);
 615         }
 616     }
 617
 618   switch (TREE_CODE (t1))
 619     {
 620     case SSA_NAME:
 621       {
 622         if (SSA_NAME_VAR (t1) && SSA_NAME_VAR (t2))
 623           {
 624             int var_cmp = tree_cmp (SSA_NAME_VAR (t1), SSA_NAME_VAR (t2));
 625             if (var_cmp)
 626               return var_cmp;
 627             return SSA_NAME_VERSION (t1) - SSA_NAME_VERSION (t2);
 628           }
 629         else
 630           {
 631             if (SSA_NAME_VAR (t1))
 632               return -1;
 633             else if (SSA_NAME_VAR (t2))
 634               return 1;
 635             else
 636               return SSA_NAME_VERSION (t1) - SSA_NAME_VERSION (t2);
 637           }
 638       }
 639       break;
 640
 641     case INTEGER_CST:
 642       return tree_int_cst_compare (t1, t2);
 643
 644     case REAL_CST:
 645       {
 646         const real_value *rv1 = TREE_REAL_CST_PTR (t1);
 647         const real_value *rv2 = TREE_REAL_CST_PTR (t2);
 648         if (real_compare (UNORDERED_EXPR, rv1, rv2))
 649           {
 650             /* Impose an arbitrary order on NaNs relative to other NaNs
 651                and to non-NaNs.  */
 652             if (int cmp_isnan = real_isnan (rv1) - real_isnan (rv2))
 653               return cmp_isnan;
 654             if (int cmp_issignaling_nan
 655                   = real_issignaling_nan (rv1) - real_issignaling_nan (rv2))
 656               return cmp_issignaling_nan;
 657             return real_isneg (rv1) - real_isneg (rv2);
 658           }
 659         if (real_compare (LT_EXPR, rv1, rv2))
 660           return -1;
 661         if (real_compare (GT_EXPR, rv1, rv2))
 662           return 1;
 663         return 0;
 664       }
 665
 666     case STRING_CST:
 667       return strcmp (TREE_STRING_POINTER (t1),
 668                      TREE_STRING_POINTER (t2));
 669
 670     default:
 671       gcc_unreachable ();
 672       break;
 673     }
 674
 675   gcc_unreachable ();
 676
 677   return 0;
 678 }
 679
 680 /* qsort comparator for trees to impose a deterministic ordering on
 681    P1 and P2.  */
 682
 683 int
 684 tree_cmp (const void *p1, const void *p2)
 685 {
 686   const_tree t1 = *(const_tree const *)p1;
 687   const_tree t2 = *(const_tree const *)p2;
 688
 689   return tree_cmp (t1, t2);
 690 }
 691
 692 /* class frame_region : public space_region.  */
 693
 694 frame_region::~frame_region ()
 695 {
 696   for (map_t::iterator iter = m_locals.begin ();
 697        iter != m_locals.end ();
 698        ++iter)
 699     delete (*iter).second;
 700 }
 701
 702 void
 703 frame_region::accept (visitor *v) const
 704 {
 705   region::accept (v);
 706   if (m_calling_frame)
 707     m_calling_frame->accept (v);
 708 }
 709
 710 /* Implementation of region::dump_to_pp vfunc for frame_region.  */
 711
 712 void
 713 frame_region::dump_to_pp (pretty_printer *pp, bool simple) const
 714 {
 715   if (simple)
 716     pp_printf (pp, "frame: %qs@%i", function_name (m_fun), get_stack_depth ());
 717   else
 718     pp_printf (pp, "frame_region(%qs, index: %i, depth: %i)",
 719                function_name (m_fun), m_index, get_stack_depth ());
 720 }
 721
 722 const decl_region *
 723 frame_region::get_region_for_local (region_model_manager *mgr,
 724                                     tree expr) const
 725 {
 726   // TODO: could also check that VAR_DECLs are locals
 727   gcc_assert (TREE_CODE (expr) == PARM_DECL
 728               || TREE_CODE (expr) == VAR_DECL
 729               || TREE_CODE (expr) == SSA_NAME
 730               || TREE_CODE (expr) == RESULT_DECL);
 731
 732   /* Ideally we'd use mutable here.  */
 733   map_t &mutable_locals = const_cast <map_t &> (m_locals);
 734
 735   if (decl_region **slot = mutable_locals.get (expr))
 736     return *slot;
 737   decl_region *reg
 738     = new decl_region (mgr->alloc_region_id (), this, expr);
 739   mutable_locals.put (expr, reg);
 740   return reg;
 741 }
 742
 743 /* class globals_region : public space_region.  */
 744
 745 /* Implementation of region::dump_to_pp vfunc for globals_region.  */
 746
 747 void
 748 globals_region::dump_to_pp (pretty_printer *pp, bool simple) const
 749 {
 750   if (simple)
 751     pp_string (pp, "::");
 752   else
 753     pp_string (pp, "globals");
 754 }
 755
 756 /* class code_region : public map_region.  */
 757
 758 /* Implementation of region::dump_to_pp vfunc for code_region.  */
 759
 760 void
 761 code_region::dump_to_pp (pretty_printer *pp, bool simple) const
 762 {
 763   if (simple)
 764     pp_string (pp, "code region");
 765   else
 766     pp_string (pp, "code_region()");
 767 }
 768
 769 /* class function_region : public region.  */
 770
 771 /* Implementation of region::dump_to_pp vfunc for function_region.  */
 772
 773 void
 774 function_region::dump_to_pp (pretty_printer *pp, bool simple) const
 775 {
 776   if (simple)
 777     {
 778       dump_quoted_tree (pp, m_fndecl);
 779     }
 780   else
 781     {
 782       pp_string (pp, "function_region(");
 783       dump_quoted_tree (pp, m_fndecl);
 784       pp_string (pp, ")");
 785     }
 786 }
 787
 788 /* class label_region : public region.  */
 789
 790 /* Implementation of region::dump_to_pp vfunc for label_region.  */
 791
 792 void
 793 label_region::dump_to_pp (pretty_printer *pp, bool simple) const
 794 {
 795   if (simple)
 796     {
 797       dump_quoted_tree (pp, m_label);
 798     }
 799   else
 800     {
 801       pp_string (pp, "label_region(");
 802       dump_quoted_tree (pp, m_label);
 803       pp_string (pp, ")");
 804     }
 805 }
 806
 807 /* class stack_region : public region.  */
 808
 809 /* Implementation of region::dump_to_pp vfunc for stack_region.  */
 810
 811 void
 812 stack_region::dump_to_pp (pretty_printer *pp, bool simple) const
 813 {
 814   if (simple)
 815     pp_string (pp, "stack region");
 816   else
 817     pp_string (pp, "stack_region()");
 818 }
 819
 820 /* class heap_region : public region.  */
 821
 822 /* Implementation of region::dump_to_pp vfunc for heap_region.  */
 823
 824 void
 825 heap_region::dump_to_pp (pretty_printer *pp, bool simple) const
 826 {
 827   if (simple)
 828     pp_string (pp, "heap region");
 829   else
 830     pp_string (pp, "heap_region()");
 831 }
 832
 833 /* class root_region : public region.  */
 834
 835 /* root_region's ctor.  */
 836
 837 root_region::root_region (unsigned id)
 838 : region (complexity (1, 1), id, NULL, NULL_TREE)
 839 {
 840 }
 841
 842 /* Implementation of region::dump_to_pp vfunc for root_region.  */
 843
 844 void
 845 root_region::dump_to_pp (pretty_printer *pp, bool simple) const
 846 {
 847   if (simple)
 848     pp_string (pp, "root region");
 849   else
 850     pp_string (pp, "root_region()");
 851 }
 852
 853 /* class symbolic_region : public map_region.  */
 854
 855 /* symbolic_region's ctor.  */
 856
 857 symbolic_region::symbolic_region (unsigned id, region *parent,
 858                                   const svalue *sval_ptr)
 859 : region (complexity::from_pair (parent, sval_ptr), id, parent,
 860           TREE_TYPE (sval_ptr->get_type ())),
 861   m_sval_ptr (sval_ptr)
 862 {
 863 }
 864
 865 /* Implementation of region::accept vfunc for symbolic_region.  */
 866
 867 void
 868 symbolic_region::accept (visitor *v) const
 869 {
 870   region::accept (v);
 871   m_sval_ptr->accept (v);
 872 }
 873
 874 /* Implementation of region::dump_to_pp vfunc for symbolic_region.  */
 875
 876 void
 877 symbolic_region::dump_to_pp (pretty_printer *pp, bool simple) const
 878 {
 879   if (simple)
 880     {
 881       pp_string (pp, "(*");
 882       m_sval_ptr->dump_to_pp (pp, simple);
 883       pp_string (pp, ")");
 884     }
 885   else
 886     {
 887       pp_string (pp, "symbolic_region(");
 888       get_parent_region ()->dump_to_pp (pp, simple);
 889       pp_string (pp, ", ");
 890       print_quoted_type (pp, get_type ());
 891       pp_string (pp, ", ");
 892       m_sval_ptr->dump_to_pp (pp, simple);
 893       pp_string (pp, ")");
 894     }
 895 }
 896
 897 /* class decl_region : public region.  */
 898
 899 /* Implementation of region::dump_to_pp vfunc for decl_region.  */
 900
 901 void
 902 decl_region::dump_to_pp (pretty_printer *pp, bool simple) const
 903 {
 904   if (simple)
 905     pp_printf (pp, "%E", m_decl);
 906   else
 907     {
 908       pp_string (pp, "decl_region(");
 909       get_parent_region ()->dump_to_pp (pp, simple);
 910       pp_string (pp, ", ");
 911       print_quoted_type (pp, get_type ());
 912       pp_printf (pp, ", %qE)", m_decl);
 913     }
 914 }
 915
 916 /* Get the stack depth for the frame containing this decl, or 0
 917    for a global.  */
 918
 919 int
 920 decl_region::get_stack_depth () const
 921 {
 922   if (get_parent_region () == NULL)
 923     return 0;
 924   if (const frame_region *frame_reg
 925         = get_parent_region ()->dyn_cast_frame_region ())
 926     return frame_reg->get_stack_depth ();
 927   return 0;
 928 }
 929
 930 /* If the underlying decl is in the global constant pool,
 931    return an svalue representing the constant value.
 932    Otherwise return NULL.  */
 933
 934 const svalue *
 935 decl_region::maybe_get_constant_value (region_model_manager *mgr) const
 936 {
 937   if (TREE_CODE (m_decl) == VAR_DECL
 938       && DECL_IN_CONSTANT_POOL (m_decl)
 939       && DECL_INITIAL (m_decl)
 940       && TREE_CODE (DECL_INITIAL (m_decl)) == CONSTRUCTOR)
 941     return get_svalue_for_constructor (DECL_INITIAL (m_decl), mgr);
 942   return NULL;
 943 }
 944
 945 /* Get an svalue for CTOR, a CONSTRUCTOR for this region's decl.  */
 946
 947 const svalue *
 948 decl_region::get_svalue_for_constructor (tree ctor,
 949                                          region_model_manager *mgr) const
 950 {
 951   gcc_assert (!TREE_CLOBBER_P (ctor));
 952
 953   /* Create a binding map, applying ctor to it, using this
 954      decl_region as the base region when building child regions
 955      for offset calculations.  */
 956   binding_map map;
 957   if (!map.apply_ctor_to_region (this, ctor, mgr))
 958     return mgr->get_or_create_unknown_svalue (get_type ());
 959
 960   /* Return a compound svalue for the map we built.  */
 961   return mgr->get_or_create_compound_svalue (get_type (), map);
 962 }
 963
 964 /* For use on decl_regions for global variables.
 965
 966    Get an svalue for the initial value of this region at entry to
 967    "main" (either based on DECL_INITIAL, or implicit initialization to
 968    zero.
 969
 970    Return NULL if there is a problem.  */
 971
 972 const svalue *
 973 decl_region::get_svalue_for_initializer (region_model_manager *mgr) const
 974 {
 975   tree init = DECL_INITIAL (m_decl);
 976   if (!init)
 977     {
 978       /* If we have an "extern" decl then there may be an initializer in
 979          another TU.  */
 980       if (DECL_EXTERNAL (m_decl))
 981         return NULL;
 982
 983       /* Implicit initialization to zero; use a compound_svalue for it.
 984          Doing so requires that we have a concrete binding for this region,
 985          which can fail if we have a region with unknown size
 986          (e.g. "extern const char arr[];").  */
 987       const binding_key *binding
 988         = binding_key::make (mgr->get_store_manager (), this);
 989       if (binding->symbolic_p ())
 990         return NULL;
 991
 992       binding_cluster c (this);
 993       c.zero_fill_region (mgr->get_store_manager (), this);
 994       return mgr->get_or_create_compound_svalue (TREE_TYPE (m_decl),
 995                                                  c.get_map ());
 996     }
 997
 998   /* LTO can write out error_mark_node as the DECL_INITIAL for simple scalar
 999      values (to avoid writing out an extra section).  */
1000   if (init == error_mark_node)
1001     return NULL;
1002
1003   if (TREE_CODE (init) == CONSTRUCTOR)
1004     return get_svalue_for_constructor (init, mgr);
1005
1006   /* Reuse the get_rvalue logic from region_model.  */
1007   region_model m (mgr);
1008   return m.get_rvalue (path_var (init, 0), NULL);
1009 }
1010
1011 /* class field_region : public region.  */
1012
1013 /* Implementation of region::dump_to_pp vfunc for field_region.  */
1014
1015 void
1016 field_region::dump_to_pp (pretty_printer *pp, bool simple) const
1017 {
1018   if (simple)
1019     {
1020       get_parent_region ()->dump_to_pp (pp, simple);
1021       pp_string (pp, ".");
1022       pp_printf (pp, "%E", m_field);
1023     }
1024   else
1025     {
1026       pp_string (pp, "field_region(");
1027       get_parent_region ()->dump_to_pp (pp, simple);
1028       pp_string (pp, ", ");
1029       print_quoted_type (pp, get_type ());
1030       pp_printf (pp, ", %qE)", m_field);
1031     }
1032 }
1033
1034 /* Implementation of region::get_relative_concrete_offset vfunc
1035    for field_region.  */
1036
1037 bool
1038 field_region::get_relative_concrete_offset (bit_offset_t *out) const
1039 {
1040   /* Compare with e.g. gimple-fold.c's
1041      fold_nonarray_ctor_reference.  */
1042   tree byte_offset = DECL_FIELD_OFFSET (m_field);
1043   if (TREE_CODE (byte_offset) != INTEGER_CST)
1044     return false;
1045   tree field_offset = DECL_FIELD_BIT_OFFSET (m_field);
1046   /* Compute bit offset of the field.  */
1047   offset_int bitoffset
1048     = (wi::to_offset (field_offset)
1049        + (wi::to_offset (byte_offset) << LOG2_BITS_PER_UNIT));
1050   *out = bitoffset;
1051   return true;
1052 }
1053
1054 /* class element_region : public region.  */
1055
1056 /* Implementation of region::accept vfunc for element_region.  */
1057
1058 void
1059 element_region::accept (visitor *v) const
1060 {
1061   region::accept (v);
1062   m_index->accept (v);
1063 }
1064
1065 /* Implementation of region::dump_to_pp vfunc for element_region.  */
1066
1067 void
1068 element_region::dump_to_pp (pretty_printer *pp, bool simple) const
1069 {
1070   if (simple)
1071     {
1072       //pp_string (pp, "(");
1073       get_parent_region ()->dump_to_pp (pp, simple);
1074       pp_string (pp, "[");
1075       m_index->dump_to_pp (pp, simple);
1076       pp_string (pp, "]");
1077       //pp_string (pp, ")");
1078     }
1079   else
1080     {
1081       pp_string (pp, "element_region(");
1082       get_parent_region ()->dump_to_pp (pp, simple);
1083       pp_string (pp, ", ");
1084       print_quoted_type (pp, get_type ());
1085       pp_string (pp, ", ");
1086       m_index->dump_to_pp (pp, simple);
1087       pp_printf (pp, ")");
1088     }
1089 }
1090
1091 /* Implementation of region::get_relative_concrete_offset vfunc
1092    for element_region.  */
1093
1094 bool
1095 element_region::get_relative_concrete_offset (bit_offset_t *out) const
1096 {
1097   if (tree idx_cst = m_index->maybe_get_constant ())
1098     {
1099       gcc_assert (TREE_CODE (idx_cst) == INTEGER_CST);
1100
1101       tree elem_type = get_type ();
1102       offset_int element_idx = wi::to_offset (idx_cst);
1103
1104       /* First, use int_size_in_bytes, to reject the case where we
1105          have an incomplete type, or a non-constant value.  */
1106       HOST_WIDE_INT hwi_byte_size = int_size_in_bytes (elem_type);
1107       if (hwi_byte_size > 0)
1108         {
1109           offset_int element_bit_size
1110             = hwi_byte_size << LOG2_BITS_PER_UNIT;
1111           offset_int element_bit_offset
1112             = element_idx * element_bit_size;
1113           *out = element_bit_offset;
1114           return true;
1115         }
1116     }
1117   return false;
1118 }
1119
1120 /* class offset_region : public region.  */
1121
1122 /* Implementation of region::accept vfunc for offset_region.  */
1123
1124 void
1125 offset_region::accept (visitor *v) const
1126 {
1127   region::accept (v);
1128   m_byte_offset->accept (v);
1129 }
1130
1131 /* Implementation of region::dump_to_pp vfunc for offset_region.  */
1132
1133 void
1134 offset_region::dump_to_pp (pretty_printer *pp, bool simple) const
1135 {
1136   if (simple)
1137     {
1138       //pp_string (pp, "(");
1139       get_parent_region ()->dump_to_pp (pp, simple);
1140       pp_string (pp, "+");
1141       m_byte_offset->dump_to_pp (pp, simple);
1142       //pp_string (pp, ")");
1143     }
1144   else
1145     {
1146       pp_string (pp, "offset_region(");
1147       get_parent_region ()->dump_to_pp (pp, simple);
1148       pp_string (pp, ", ");
1149       print_quoted_type (pp, get_type ());
1150       pp_string (pp, ", ");
1151       m_byte_offset->dump_to_pp (pp, simple);
1152       pp_printf (pp, ")");
1153     }
1154 }
1155
1156 /* Implementation of region::get_relative_concrete_offset vfunc
1157    for offset_region.  */
1158
1159 bool
1160 offset_region::get_relative_concrete_offset (bit_offset_t *out) const
1161 {
1162   if (tree byte_offset_cst = m_byte_offset->maybe_get_constant ())
1163     {
1164       gcc_assert (TREE_CODE (byte_offset_cst) == INTEGER_CST);
1165       /* Use a signed value for the byte offset, to handle
1166          negative offsets.  */
1167       HOST_WIDE_INT byte_offset
1168         = wi::to_offset (byte_offset_cst).to_shwi ();
1169       HOST_WIDE_INT bit_offset = byte_offset * BITS_PER_UNIT;
1170       *out = bit_offset;
1171       return true;
1172     }
1173   return false;
1174 }
1175
1176 /* class sized_region : public region.  */
1177
1178 /* Implementation of region::accept vfunc for sized_region.  */
1179
1180 void
1181 sized_region::accept (visitor *v) const
1182 {
1183   region::accept (v);
1184   m_byte_size_sval->accept (v);
1185 }
1186
1187 /* Implementation of region::dump_to_pp vfunc for sized_region.  */
1188
1189 void
1190 sized_region::dump_to_pp (pretty_printer *pp, bool simple) const
1191 {
1192   if (simple)
1193     {
1194       pp_string (pp, "SIZED_REG(");
1195       get_parent_region ()->dump_to_pp (pp, simple);
1196       pp_string (pp, ", ");
1197       m_byte_size_sval->dump_to_pp (pp, simple);
1198       pp_string (pp, ")");
1199     }
1200   else
1201     {
1202       pp_string (pp, "sized_region(");
1203       get_parent_region ()->dump_to_pp (pp, simple);
1204       pp_string (pp, ", ");
1205       m_byte_size_sval->dump_to_pp (pp, simple);
1206       pp_printf (pp, ")");
1207     }
1208 }
1209
1210 /* Implementation of region::get_byte_size vfunc for sized_region.  */
1211
1212 bool
1213 sized_region::get_byte_size (byte_size_t *out) const
1214 {
1215   if (tree cst = m_byte_size_sval->maybe_get_constant ())
1216     {
1217       gcc_assert (TREE_CODE (cst) == INTEGER_CST);
1218       *out = tree_to_uhwi (cst);
1219       return true;
1220     }
1221   return false;
1222 }
1223
1224 /* Implementation of region::get_bit_size vfunc for sized_region.  */
1225
1226 bool
1227 sized_region::get_bit_size (bit_size_t *out) const
1228 {
1229   byte_size_t byte_size;
1230   if (!get_byte_size (&byte_size))
1231     return false;
1232   *out = byte_size * BITS_PER_UNIT;
1233   return true;
1234 }
1235
1236 /* class cast_region : public region.  */
1237
1238 /* Implementation of region::accept vfunc for cast_region.  */
1239
1240 void
1241 cast_region::accept (visitor *v) const
1242 {
1243   region::accept (v);
1244   m_original_region->accept (v);
1245 }
1246
1247 /* Implementation of region::dump_to_pp vfunc for cast_region.  */
1248
1249 void
1250 cast_region::dump_to_pp (pretty_printer *pp, bool simple) const
1251 {
1252   if (simple)
1253     {
1254       pp_string (pp, "CAST_REG(");
1255       print_quoted_type (pp, get_type ());
1256       pp_string (pp, ", ");
1257       m_original_region->dump_to_pp (pp, simple);
1258       pp_string (pp, ")");
1259     }
1260   else
1261     {
1262       pp_string (pp, "cast_region(");
1263       m_original_region->dump_to_pp (pp, simple);
1264       pp_string (pp, ", ");
1265       print_quoted_type (pp, get_type ());
1266       pp_printf (pp, ")");
1267     }
1268 }
1269
1270 /* class heap_allocated_region : public region.  */
1271
1272 /* Implementation of region::dump_to_pp vfunc for heap_allocated_region.  */
1273
1274 void
1275 heap_allocated_region::dump_to_pp (pretty_printer *pp, bool simple) const
1276 {
1277   if (simple)
1278     pp_printf (pp, "HEAP_ALLOCATED_REGION(%i)", get_id ());
1279   else
1280     pp_printf (pp, "heap_allocated_region(%i)", get_id ());
1281 }
1282
1283 /* class alloca_region : public region.  */
1284
1285 /* Implementation of region::dump_to_pp vfunc for alloca_region.  */
1286
1287 void
1288 alloca_region::dump_to_pp (pretty_printer *pp, bool simple) const
1289 {
1290   if (simple)
1291     pp_string (pp, "ALLOCA_REGION");
1292   else
1293     pp_string (pp, "alloca_region()");
1294 }
1295
1296 /* class string_region : public region.  */
1297
1298 /* Implementation of region::dump_to_pp vfunc for string_region.  */
1299
1300 void
1301 string_region::dump_to_pp (pretty_printer *pp, bool simple) const
1302 {
1303   if (simple)
1304     dump_tree (pp, m_string_cst);
1305   else
1306     {
1307       pp_string (pp, "string_region(");
1308       dump_tree (pp, m_string_cst);
1309       if (!flag_dump_noaddr)
1310         {
1311           pp_string (pp, " (");
1312           pp_pointer (pp, m_string_cst);
1313           pp_string (pp, "))");
1314         }
1315     }
1316 }
1317
1318 /* class unknown_region : public region.  */
1319
1320 /* Implementation of region::dump_to_pp vfunc for unknown_region.  */
1321
1322 void
1323 unknown_region::dump_to_pp (pretty_printer *pp, bool /*simple*/) const
1324 {
1325   pp_string (pp, "UNKNOWN_REGION");
1326 }
1327
1328 } // namespace ana
1329
1330 #endif /* #if ENABLE_ANALYZER */