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