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