libcpp, c, middle-end: Optimize initializers using #embed in C
[official-gcc.git] / gcc / analyzer / region.cc
blob59b09e5c81ce89a16ed10442262e7df5dfd11ee4
1 /* Regions of memory.
2 Copyright (C) 2019-2024 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
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.
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.
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/>. */
21 #include "config.h"
22 #define INCLUDE_MEMORY
23 #define INCLUDE_VECTOR
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tree.h"
27 #include "diagnostic-core.h"
28 #include "gimple-pretty-print.h"
29 #include "function.h"
30 #include "basic-block.h"
31 #include "gimple.h"
32 #include "gimple-iterator.h"
33 #include "diagnostic-core.h"
34 #include "graphviz.h"
35 #include "options.h"
36 #include "cgraph.h"
37 #include "tree-dfa.h"
38 #include "stringpool.h"
39 #include "convert.h"
40 #include "target.h"
41 #include "fold-const.h"
42 #include "tree-pretty-print.h"
43 #include "diagnostic-color.h"
44 #include "bitmap.h"
45 #include "analyzer/analyzer.h"
46 #include "analyzer/analyzer-logging.h"
47 #include "ordered-hash-map.h"
48 #include "options.h"
49 #include "cgraph.h"
50 #include "cfg.h"
51 #include "digraph.h"
52 #include "analyzer/supergraph.h"
53 #include "sbitmap.h"
54 #include "analyzer/call-string.h"
55 #include "analyzer/program-point.h"
56 #include "analyzer/store.h"
57 #include "analyzer/region.h"
58 #include "analyzer/region-model.h"
59 #include "analyzer/sm.h"
60 #include "analyzer/program-state.h"
61 #include "text-art/dump.h"
63 #if ENABLE_ANALYZER
65 namespace ana {
67 region_offset
68 region_offset::make_byte_offset (const region *base_region,
69 const svalue *num_bytes_sval)
71 if (tree num_bytes_cst = num_bytes_sval->maybe_get_constant ())
73 gcc_assert (TREE_CODE (num_bytes_cst) == INTEGER_CST);
74 bit_offset_t num_bits = wi::to_offset (num_bytes_cst) * BITS_PER_UNIT;
75 return make_concrete (base_region, num_bits);
77 else
79 return make_symbolic (base_region, num_bytes_sval);
83 const svalue &
84 region_offset::calc_symbolic_bit_offset (region_model_manager *mgr) const
86 if (symbolic_p ())
88 const svalue *bits_per_byte
89 = mgr->get_or_create_int_cst (NULL_TREE, BITS_PER_UNIT);
90 return *mgr->get_or_create_binop (NULL_TREE, MULT_EXPR,
91 m_sym_offset, bits_per_byte);
93 else
94 return *mgr->get_or_create_int_cst (NULL_TREE, m_offset);
97 const svalue *
98 region_offset::calc_symbolic_byte_offset (region_model_manager *mgr) const
100 if (symbolic_p ())
101 return m_sym_offset;
102 else
104 byte_offset_t concrete_byte_offset;
105 if (get_concrete_byte_offset (&concrete_byte_offset))
106 return mgr->get_or_create_int_cst (size_type_node,
107 concrete_byte_offset);
108 else
109 /* Can't handle bitfields; return UNKNOWN. */
110 return mgr->get_or_create_unknown_svalue (size_type_node);
114 void
115 region_offset::dump_to_pp (pretty_printer *pp, bool simple) const
117 if (symbolic_p ())
119 /* We don't bother showing the base region. */
120 pp_string (pp, "byte ");
121 m_sym_offset->dump_to_pp (pp, simple);
123 else
125 if (m_offset % BITS_PER_UNIT == 0)
127 pp_string (pp, "byte ");
128 pp_wide_int (pp, m_offset / BITS_PER_UNIT, SIGNED);
130 else
132 pp_string (pp, "bit ");
133 pp_wide_int (pp, m_offset, SIGNED);
138 DEBUG_FUNCTION void
139 region_offset::dump (bool simple) const
141 tree_dump_pretty_printer pp (stderr);
142 dump_to_pp (&pp, simple);
143 pp_newline (&pp);
146 /* An svalue that matches the pattern (BASE * FACTOR) + OFFSET
147 where FACTOR or OFFSET could be the identity (represented as NULL). */
149 struct linear_op
151 linear_op (const svalue *base,
152 const svalue *factor,
153 const svalue *offset)
154 : m_base (base), m_factor (factor), m_offset (offset)
158 bool maybe_get_cst_factor (bit_offset_t *out) const
160 if (m_factor == nullptr)
162 *out = 1;
163 return true;
165 if (tree cst_factor = m_factor->maybe_get_constant ())
167 *out = wi::to_offset (cst_factor);
168 return true;
170 return false;
173 bool maybe_get_cst_offset (bit_offset_t *out) const
175 if (m_offset == nullptr)
177 *out = 0;
178 return true;
180 if (tree cst_offset = m_offset->maybe_get_constant ())
182 *out = wi::to_offset (cst_offset);
183 return true;
185 return false;
188 static tristate
189 less (const linear_op &a, const linear_op &b)
191 /* Same base. */
192 if (a.m_base == b.m_base)
194 bit_offset_t a_wi_factor;
195 bit_offset_t b_wi_factor;
196 if (a.maybe_get_cst_factor (&a_wi_factor)
197 && b.maybe_get_cst_factor (&b_wi_factor))
199 if (a_wi_factor != b_wi_factor)
200 return tristate (a_wi_factor < b_wi_factor);
201 else
203 bit_offset_t a_wi_offset;
204 bit_offset_t b_wi_offset;
205 if (a.maybe_get_cst_offset (&a_wi_offset)
206 && b.maybe_get_cst_offset (&b_wi_offset))
207 return tristate (a_wi_offset < b_wi_offset);
211 return tristate::unknown ();
214 static tristate
215 le (const linear_op &a, const linear_op &b)
217 /* Same base. */
218 if (a.m_base == b.m_base)
220 bit_offset_t a_wi_factor;
221 bit_offset_t b_wi_factor;
222 if (a.maybe_get_cst_factor (&a_wi_factor)
223 && b.maybe_get_cst_factor (&b_wi_factor))
225 if (a_wi_factor != b_wi_factor)
226 return tristate (a_wi_factor <= b_wi_factor);
227 else
229 bit_offset_t a_wi_offset;
230 bit_offset_t b_wi_offset;
231 if (a.maybe_get_cst_offset (&a_wi_offset)
232 && b.maybe_get_cst_offset (&b_wi_offset))
233 return tristate (a_wi_offset <= b_wi_offset);
237 return tristate::unknown ();
240 static bool
241 from_svalue (const svalue &sval, linear_op *out)
243 switch (sval.get_kind ())
245 default:
246 break;
247 case SK_BINOP:
249 const binop_svalue &binop_sval ((const binop_svalue &)sval);
250 if (binop_sval.get_op () == MULT_EXPR)
252 *out = linear_op (binop_sval.get_arg0 (),
253 binop_sval.get_arg1 (),
254 NULL);
255 return true;
257 else if (binop_sval.get_op () == PLUS_EXPR)
259 if (binop_sval.get_arg0 ()->get_kind () == SK_BINOP)
261 const binop_svalue &inner_binop_sval
262 ((const binop_svalue &)*binop_sval.get_arg0 ());
263 if (inner_binop_sval.get_op () == MULT_EXPR)
265 *out = linear_op (inner_binop_sval.get_arg0 (),
266 inner_binop_sval.get_arg1 (),
267 binop_sval.get_arg1 ());
268 return true;
272 *out = linear_op (binop_sval.get_arg0 (),
273 NULL,
274 binop_sval.get_arg1 ());
275 return true;
278 break;
280 return false;
283 const svalue *m_base;
284 const svalue *m_factor;
285 const svalue *m_offset;
288 bool
289 operator< (const region_offset &a, const region_offset &b)
291 if (a.symbolic_p ())
293 if (b.symbolic_p ())
295 /* Symbolic vs symbolic. */
296 const svalue &a_sval = *a.get_symbolic_byte_offset ();
297 const svalue &b_sval = *b.get_symbolic_byte_offset ();
299 linear_op op_a (NULL, NULL, NULL);
300 linear_op op_b (NULL, NULL, NULL);
301 if (linear_op::from_svalue (a_sval, &op_a)
302 && linear_op::from_svalue (b_sval, &op_b))
304 tristate ts = linear_op::less (op_a, op_b);
305 if (ts.is_true ())
306 return true;
307 else if (ts.is_false ())
308 return false;
310 /* Use svalue's deterministic order, for now. */
311 return (svalue::cmp_ptr (a.get_symbolic_byte_offset (),
312 b.get_symbolic_byte_offset ())
313 < 0);
315 else
316 /* Symbolic vs concrete: put all symbolic after all concrete. */
317 return false;
319 else
321 if (b.symbolic_p ())
322 /* Concrete vs symbolic: put all concrete before all symbolic. */
323 return true;
324 else
325 /* Concrete vs concrete. */
326 return a.get_bit_offset () < b.get_bit_offset ();
330 bool
331 operator<= (const region_offset &a, const region_offset &b)
333 if (a.symbolic_p ())
335 if (b.symbolic_p ())
337 /* Symbolic vs symbolic. */
338 const svalue &a_sval = *a.get_symbolic_byte_offset ();
339 const svalue &b_sval = *b.get_symbolic_byte_offset ();
341 linear_op op_a (NULL, NULL, NULL);
342 linear_op op_b (NULL, NULL, NULL);
343 if (linear_op::from_svalue (a_sval, &op_a)
344 && linear_op::from_svalue (b_sval, &op_b))
346 tristate ts = linear_op::le (op_a, op_b);
347 if (ts.is_true ())
348 return true;
349 else if (ts.is_false ())
350 return false;
352 /* Use svalue's deterministic order, for now. */
353 return (svalue::cmp_ptr (a.get_symbolic_byte_offset (),
354 b.get_symbolic_byte_offset ())
355 <= 0);
357 else
358 /* Symbolic vs concrete: put all symbolic after all concrete. */
359 return false;
361 else
363 if (b.symbolic_p ())
364 /* Concrete vs symbolic: put all concrete before all symbolic. */
365 return true;
366 else
367 /* Concrete vs concrete. */
368 return a.get_bit_offset () <= b.get_bit_offset ();
372 bool
373 operator> (const region_offset &a, const region_offset &b)
375 return b < a;
378 bool
379 operator>= (const region_offset &a, const region_offset &b)
381 return b <= a;
384 region_offset
385 strip_types (const region_offset &offset, region_model_manager &mgr)
387 if (offset.symbolic_p ())
388 return region_offset::make_symbolic
389 (offset.get_base_region (),
390 strip_types (offset.get_symbolic_byte_offset (),
391 mgr));
392 else
393 return offset;
396 /* class region and its various subclasses. */
398 /* class region. */
400 region::~region ()
402 delete m_cached_offset;
405 /* Determine the base region for this region: when considering bindings
406 for this region, the base region is the ancestor which identifies
407 which cluster they should be partitioned into.
408 Regions within the same struct/union/array are in the same cluster.
409 Different decls are in different clusters. */
411 const region *
412 region::get_base_region () const
414 const region *iter = this;
415 while (iter)
417 switch (iter->get_kind ())
419 case RK_FIELD:
420 case RK_ELEMENT:
421 case RK_OFFSET:
422 case RK_SIZED:
423 case RK_BIT_RANGE:
424 case RK_CAST:
425 iter = iter->get_parent_region ();
426 continue;
427 default:
428 return iter;
431 return iter;
434 /* Return true if get_base_region() == this for this region. */
436 bool
437 region::base_region_p () const
439 switch (get_kind ())
441 /* Region kinds representing a descendent of a base region. */
442 case RK_FIELD:
443 case RK_ELEMENT:
444 case RK_OFFSET:
445 case RK_SIZED:
446 case RK_CAST:
447 case RK_BIT_RANGE:
448 return false;
450 default:
451 return true;
455 /* Return true if this region is ELDER or one of its descendents. */
457 bool
458 region::descendent_of_p (const region *elder) const
460 const region *iter = this;
461 while (iter)
463 if (iter == elder)
464 return true;
465 iter = iter->get_parent_region ();
467 return false;
470 /* If this region is a frame_region, or a descendent of one, return it.
471 Otherwise return NULL. */
473 const frame_region *
474 region::maybe_get_frame_region () const
476 const region *iter = this;
477 while (iter)
479 if (const frame_region *frame_reg = iter->dyn_cast_frame_region ())
480 return frame_reg;
481 iter = iter->get_parent_region ();
483 return NULL;
486 /* Get the memory space of this region. */
488 enum memory_space
489 region::get_memory_space () const
491 const region *iter = this;
492 while (iter)
494 switch (iter->get_kind ())
496 default:
497 break;
498 case RK_GLOBALS:
499 return MEMSPACE_GLOBALS;
500 case RK_CODE:
501 case RK_FUNCTION:
502 case RK_LABEL:
503 return MEMSPACE_CODE;
504 case RK_FRAME:
505 case RK_STACK:
506 case RK_ALLOCA:
507 return MEMSPACE_STACK;
508 case RK_HEAP:
509 case RK_HEAP_ALLOCATED:
510 return MEMSPACE_HEAP;
511 case RK_STRING:
512 return MEMSPACE_READONLY_DATA;
513 case RK_PRIVATE:
514 return MEMSPACE_PRIVATE;
516 iter = iter->get_parent_region ();
518 return MEMSPACE_UNKNOWN;
521 /* Subroutine for use by region_model_manager::get_or_create_initial_value.
522 Return true if this region has an initial_svalue.
523 Return false if attempting to use INIT_VAL(this_region) should give
524 the "UNINITIALIZED" poison value. */
526 bool
527 region::can_have_initial_svalue_p () const
529 const region *base_reg = get_base_region ();
531 /* Check for memory spaces that are uninitialized by default. */
532 enum memory_space mem_space = base_reg->get_memory_space ();
533 switch (mem_space)
535 default:
536 gcc_unreachable ();
537 case MEMSPACE_UNKNOWN:
538 case MEMSPACE_CODE:
539 case MEMSPACE_GLOBALS:
540 case MEMSPACE_READONLY_DATA:
541 case MEMSPACE_PRIVATE:
542 /* Such regions have initial_svalues. */
543 return true;
545 case MEMSPACE_HEAP:
546 /* Heap allocations are uninitialized by default. */
547 return false;
549 case MEMSPACE_STACK:
550 if (tree decl = base_reg->maybe_get_decl ())
552 /* See the assertion in frame_region::get_region_for_local for the
553 tree codes we need to handle here. */
554 switch (TREE_CODE (decl))
556 default:
557 gcc_unreachable ();
559 case PARM_DECL:
560 /* Parameters have initial values. */
561 return true;
563 case VAR_DECL:
564 case RESULT_DECL:
565 /* Function locals don't have initial values. */
566 return false;
568 case SSA_NAME:
570 tree ssa_name = decl;
571 /* SSA names that are the default defn of a PARM_DECL
572 have initial_svalues; other SSA names don't. */
573 if (SSA_NAME_IS_DEFAULT_DEF (ssa_name)
574 && SSA_NAME_VAR (ssa_name)
575 && TREE_CODE (SSA_NAME_VAR (ssa_name)) == PARM_DECL)
576 return true;
577 else
578 return false;
583 /* If we have an on-stack region that isn't associated with a decl
584 or SSA name, then we have VLA/alloca, which is uninitialized. */
585 return false;
589 /* For regions within a global decl, get the svalue for the initial
590 value of this region when the program starts, caching the result. */
592 const svalue *
593 region::get_initial_value_at_main (region_model_manager *mgr) const
595 if (!m_cached_init_sval_at_main)
596 m_cached_init_sval_at_main = calc_initial_value_at_main (mgr);
597 return m_cached_init_sval_at_main;
600 /* Implementation of region::get_initial_value_at_main. */
602 const svalue *
603 region::calc_initial_value_at_main (region_model_manager *mgr) const
605 const decl_region *base_reg = get_base_region ()->dyn_cast_decl_region ();
606 gcc_assert (base_reg);
608 /* Attempt to get the initializer value for base_reg. */
609 if (const svalue *base_reg_init
610 = base_reg->get_svalue_for_initializer (mgr))
612 if (this == base_reg)
613 return base_reg_init;
614 else
616 /* Get the value for REG within base_reg_init. */
617 binding_cluster c (base_reg);
618 c.bind (mgr->get_store_manager (), base_reg, base_reg_init);
619 const svalue *sval
620 = c.get_any_binding (mgr->get_store_manager (), this);
621 if (sval)
623 if (get_type ())
624 sval = mgr->get_or_create_cast (get_type (), sval);
625 return sval;
630 /* Otherwise, return INIT_VAL(REG). */
631 return mgr->get_or_create_initial_value (this);
634 /* If this region is a decl_region, return the decl.
635 Otherwise return NULL. */
637 tree
638 region::maybe_get_decl () const
640 if (const decl_region *decl_reg = dyn_cast_decl_region ())
641 return decl_reg->get_decl ();
642 return NULL_TREE;
645 /* Get the region_offset for this region (calculating it on the
646 first call and caching it internally). */
648 region_offset
649 region::get_offset (region_model_manager *mgr) const
651 if(!m_cached_offset)
652 m_cached_offset = new region_offset (calc_offset (mgr));
653 return *m_cached_offset;
656 /* Get the region_offset for immediately beyond this region. */
658 region_offset
659 region::get_next_offset (region_model_manager *mgr) const
661 region_offset start = get_offset (mgr);
663 bit_size_t bit_size;
664 if (get_bit_size (&bit_size))
666 if (start.concrete_p ())
668 bit_offset_t next_bit_offset = start.get_bit_offset () + bit_size;
669 return region_offset::make_concrete (start.get_base_region (),
670 next_bit_offset);
674 const svalue *start_byte_offset_sval = start.calc_symbolic_byte_offset (mgr);
675 const svalue *byte_size_sval = get_byte_size_sval (mgr);
676 const svalue *sum_sval
677 = mgr->get_or_create_binop (size_type_node,
678 PLUS_EXPR,
679 start_byte_offset_sval,
680 byte_size_sval);
681 return region_offset::make_symbolic (start.get_base_region (),
682 sum_sval);
685 /* Base class implementation of region::get_byte_size vfunc.
686 If the size of this region (in bytes) is known statically, write it to *OUT
687 and return true.
688 Otherwise return false. */
690 bool
691 region::get_byte_size (byte_size_t *out) const
693 tree type = get_type ();
695 /* Bail out e.g. for heap-allocated regions. */
696 if (!type)
697 return false;
699 HOST_WIDE_INT bytes = int_size_in_bytes (type);
700 if (bytes == -1)
701 return false;
702 *out = bytes;
703 return true;
706 /* Base implementation of region::get_byte_size_sval vfunc. */
708 const svalue *
709 region::get_byte_size_sval (region_model_manager *mgr) const
711 tree type = get_type ();
713 /* Bail out e.g. for heap-allocated regions. */
714 if (!type)
715 return mgr->get_or_create_unknown_svalue (size_type_node);
717 HOST_WIDE_INT bytes = int_size_in_bytes (type);
718 if (bytes == -1)
719 return mgr->get_or_create_unknown_svalue (size_type_node);
721 tree byte_size = size_in_bytes (type);
722 if (TREE_TYPE (byte_size) != size_type_node)
723 byte_size = fold_build1 (NOP_EXPR, size_type_node, byte_size);
724 return mgr->get_or_create_constant_svalue (byte_size);
727 /* Attempt to get the size of TYPE in bits.
728 If successful, return true and write the size to *OUT.
729 Otherwise return false. */
731 bool
732 int_size_in_bits (const_tree type, bit_size_t *out)
734 if (INTEGRAL_TYPE_P (type))
736 *out = TYPE_PRECISION (type);
737 return true;
740 tree sz = TYPE_SIZE (type);
741 if (sz
742 && tree_fits_uhwi_p (sz)
743 /* If the size is zero, then we may have a zero-sized
744 array; handle such cases by returning false. */
745 && !integer_zerop (sz))
747 *out = TREE_INT_CST_LOW (sz);
748 return true;
750 else
751 return false;
754 /* Base implementation of region::get_bit_size_sval vfunc. */
756 const svalue *
757 region::get_bit_size_sval (region_model_manager *mgr) const
759 tree type = get_type ();
761 /* Bail out e.g. for heap-allocated regions. */
762 if (!type)
763 return mgr->get_or_create_unknown_svalue (size_type_node);
765 bit_size_t bits;
766 if (!int_size_in_bits (type, &bits))
767 return mgr->get_or_create_unknown_svalue (size_type_node);
769 return mgr->get_or_create_int_cst (size_type_node, bits);
772 /* If the size of this region (in bits) is known statically, write it to *OUT
773 and return true.
774 Otherwise return false. */
776 bool
777 region::get_bit_size (bit_size_t *out) const
779 tree type = get_type ();
781 /* Bail out e.g. for heap-allocated regions. */
782 if (!type)
783 return false;
785 return int_size_in_bits (type, out);
788 /* Get the field within RECORD_TYPE at BIT_OFFSET. */
790 tree
791 get_field_at_bit_offset (tree record_type, bit_offset_t bit_offset)
793 gcc_assert (TREE_CODE (record_type) == RECORD_TYPE);
794 if (bit_offset < 0)
795 return NULL;
797 /* Find the first field that has an offset > BIT_OFFSET,
798 then return the one preceding it.
799 Skip other trees within the chain, such as FUNCTION_DECLs. */
800 tree last_field = NULL_TREE;
801 for (tree iter = TYPE_FIELDS (record_type); iter != NULL_TREE;
802 iter = DECL_CHAIN (iter))
804 if (TREE_CODE (iter) == FIELD_DECL)
806 int iter_field_offset = int_bit_position (iter);
807 if (bit_offset < iter_field_offset)
808 return last_field;
809 last_field = iter;
812 return last_field;
815 /* Populate *OUT with descendent regions of type TYPE that match
816 RELATIVE_BIT_OFFSET and SIZE_IN_BITS within this region. */
818 void
819 region::get_subregions_for_binding (region_model_manager *mgr,
820 bit_offset_t relative_bit_offset,
821 bit_size_t size_in_bits,
822 tree type,
823 auto_vec <const region *> *out) const
825 if (get_type () == NULL_TREE || type == NULL_TREE)
826 return;
827 if (relative_bit_offset == 0
828 && types_compatible_p (get_type (), type))
830 out->safe_push (this);
831 return;
833 switch (TREE_CODE (get_type ()))
835 case ARRAY_TYPE:
837 tree element_type = TREE_TYPE (get_type ());
838 HOST_WIDE_INT hwi_byte_size = int_size_in_bytes (element_type);
839 if (hwi_byte_size > 0)
841 HOST_WIDE_INT bits_per_element
842 = hwi_byte_size << LOG2_BITS_PER_UNIT;
843 HOST_WIDE_INT element_index
844 = (relative_bit_offset.to_shwi () / bits_per_element);
845 tree element_index_cst
846 = build_int_cst (integer_type_node, element_index);
847 HOST_WIDE_INT inner_bit_offset
848 = relative_bit_offset.to_shwi () % bits_per_element;
849 const region *subregion = mgr->get_element_region
850 (this, element_type,
851 mgr->get_or_create_constant_svalue (element_index_cst));
852 subregion->get_subregions_for_binding (mgr, inner_bit_offset,
853 size_in_bits, type, out);
856 break;
857 case RECORD_TYPE:
859 /* The bit offset might be *within* one of the fields (such as
860 with nested structs).
861 So we want to find the enclosing field, adjust the offset,
862 and repeat. */
863 if (tree field = get_field_at_bit_offset (get_type (),
864 relative_bit_offset))
866 int field_bit_offset = int_bit_position (field);
867 const region *subregion = mgr->get_field_region (this, field);
868 subregion->get_subregions_for_binding
869 (mgr, relative_bit_offset - field_bit_offset,
870 size_in_bits, type, out);
873 break;
874 case UNION_TYPE:
876 for (tree field = TYPE_FIELDS (get_type ()); field != NULL_TREE;
877 field = DECL_CHAIN (field))
879 if (TREE_CODE (field) != FIELD_DECL)
880 continue;
881 const region *subregion = mgr->get_field_region (this, field);
882 subregion->get_subregions_for_binding (mgr,
883 relative_bit_offset,
884 size_in_bits,
885 type,
886 out);
889 break;
890 default:
891 /* Do nothing. */
892 break;
896 /* Walk from this region up to the base region within its cluster, calculating
897 the offset relative to the base region, either as an offset in bits,
898 or a symbolic offset. */
900 region_offset
901 region::calc_offset (region_model_manager *mgr) const
903 const region *iter_region = this;
904 bit_offset_t accum_bit_offset = 0;
905 const svalue *accum_byte_sval = NULL;
907 while (iter_region)
909 switch (iter_region->get_kind ())
911 case RK_FIELD:
912 case RK_ELEMENT:
913 case RK_OFFSET:
914 case RK_BIT_RANGE:
915 if (accum_byte_sval)
917 const svalue *sval
918 = iter_region->get_relative_symbolic_offset (mgr);
919 accum_byte_sval
920 = mgr->get_or_create_binop (ptrdiff_type_node, PLUS_EXPR,
921 accum_byte_sval, sval);
922 iter_region = iter_region->get_parent_region ();
924 else
926 bit_offset_t rel_bit_offset;
927 if (iter_region->get_relative_concrete_offset (&rel_bit_offset))
929 accum_bit_offset += rel_bit_offset;
930 iter_region = iter_region->get_parent_region ();
932 else
934 /* If the iter_region is not concrete anymore, convert the
935 accumulated bits to a svalue in bytes and revisit the
936 iter_region collecting the symbolic value. */
937 byte_offset_t byte_offset = accum_bit_offset / BITS_PER_UNIT;
938 tree offset_tree = wide_int_to_tree (ptrdiff_type_node,
939 byte_offset);
940 accum_byte_sval
941 = mgr->get_or_create_constant_svalue (offset_tree);
944 continue;
945 case RK_SIZED:
946 case RK_CAST:
947 iter_region = iter_region->get_parent_region ();
948 continue;
950 default:
951 return accum_byte_sval
952 ? region_offset::make_symbolic (iter_region,
953 accum_byte_sval)
954 : region_offset::make_concrete (iter_region,
955 accum_bit_offset);
959 return accum_byte_sval ? region_offset::make_symbolic (iter_region,
960 accum_byte_sval)
961 : region_offset::make_concrete (iter_region,
962 accum_bit_offset);
965 /* Base implementation of region::get_relative_concrete_offset vfunc. */
967 bool
968 region::get_relative_concrete_offset (bit_offset_t *) const
970 return false;
973 /* Base implementation of region::get_relative_symbolic_offset vfunc. */
975 const svalue *
976 region::get_relative_symbolic_offset (region_model_manager *mgr) const
978 return mgr->get_or_create_unknown_svalue (ptrdiff_type_node);
981 /* Attempt to get the position and size of this region expressed as a
982 concrete range of bytes relative to its parent.
983 If successful, return true and write to *OUT.
984 Otherwise return false. */
986 bool
987 region::get_relative_concrete_byte_range (byte_range *out) const
989 /* We must have a concrete offset relative to the parent. */
990 bit_offset_t rel_bit_offset;
991 if (!get_relative_concrete_offset (&rel_bit_offset))
992 return false;
993 /* ...which must be a whole number of bytes. */
994 if (rel_bit_offset % BITS_PER_UNIT != 0)
995 return false;
996 byte_offset_t start_byte_offset = rel_bit_offset / BITS_PER_UNIT;
998 /* We must have a concrete size, which must be a whole number
999 of bytes. */
1000 byte_size_t num_bytes;
1001 if (!get_byte_size (&num_bytes))
1002 return false;
1004 /* Success. */
1005 *out = byte_range (start_byte_offset, num_bytes);
1006 return true;
1009 /* Dump a description of this region to stderr. */
1011 DEBUG_FUNCTION void
1012 region::dump (bool simple) const
1014 tree_dump_pretty_printer pp (stderr);
1015 dump_to_pp (&pp, simple);
1016 pp_newline (&pp);
1019 /* Dump a tree-like representation of this region and its constituent symbols
1020 to stderr, using global_dc's colorization and theming options.
1022 For example:
1023 . (gdb) call reg->dump()
1024 . (26): ‘int’: decl_region(‘x_10(D)’)
1025 . ╰─ parent: (9): frame_region(‘test_bitmask_2’, index: 0, depth: 1)
1026 . ╰─ parent: (1): stack region
1027 . ╰─ parent: (0): root region
1030 DEBUG_FUNCTION void
1031 region::dump () const
1033 text_art::dump (*this);
1036 /* Return a new json::string describing the region. */
1038 json::value *
1039 region::to_json () const
1041 label_text desc = get_desc (true);
1042 json::value *reg_js = new json::string (desc.get ());
1043 return reg_js;
1046 bool
1047 region::maybe_print_for_user (pretty_printer *pp,
1048 const region_model &) const
1050 switch (get_kind ())
1052 default:
1053 break;
1054 case RK_DECL:
1056 const decl_region *reg = (const decl_region *)this;
1057 tree decl = reg->get_decl ();
1058 if (TREE_CODE (decl) == SSA_NAME)
1059 decl = SSA_NAME_VAR (decl);
1060 print_expr_for_user (pp, decl);
1061 return true;
1065 return false;
1068 /* Use DWI to create a text_art::widget describing this region in
1069 a tree-like form, using PREFIX as a prefix (e.g. for field names). */
1071 std::unique_ptr<text_art::tree_widget>
1072 region::make_dump_widget (const text_art::dump_widget_info &dwi,
1073 const char *prefix) const
1075 pretty_printer pp;
1076 pp_format_decoder (&pp) = default_tree_printer;
1077 pp_show_color (&pp) = true;
1079 if (prefix)
1080 pp_printf (&pp, "%s: ", prefix);
1082 pp_printf (&pp, "(%i): ", get_id ());
1083 if (get_type ())
1084 pp_printf (&pp, "%qT: ", get_type ());
1086 print_dump_widget_label (&pp);
1088 std::unique_ptr<text_art::tree_widget> w
1089 (text_art::tree_widget::make (dwi, &pp));
1091 add_dump_widget_children (*w, dwi);
1093 if (m_parent)
1094 w->add_child (m_parent->make_dump_widget (dwi, "parent"));
1096 return w;
1099 void
1100 region::add_dump_widget_children (text_art::tree_widget &,
1101 const text_art::dump_widget_info &) const
1103 /* By default, add nothing (parent is added in make_dump_widget). */
1106 /* Generate a description of this region. */
1108 DEBUG_FUNCTION label_text
1109 region::get_desc (bool simple) const
1111 pretty_printer pp;
1112 pp_format_decoder (&pp) = default_tree_printer;
1113 dump_to_pp (&pp, simple);
1114 return label_text::take (xstrdup (pp_formatted_text (&pp)));
1117 /* Base implementation of region::accept vfunc.
1118 Subclass implementations should chain up to this. */
1120 void
1121 region::accept (visitor *v) const
1123 v->visit_region (this);
1124 if (m_parent)
1125 m_parent->accept (v);
1128 /* Return true if this is a symbolic region for deferencing an
1129 unknown ptr.
1130 We shouldn't attempt to bind values for this region (but
1131 can unbind values for other regions). */
1133 bool
1134 region::symbolic_for_unknown_ptr_p () const
1136 if (const symbolic_region *sym_reg = dyn_cast_symbolic_region ())
1137 if (sym_reg->get_pointer ()->get_kind () == SK_UNKNOWN)
1138 return true;
1139 return false;
1142 /* Return true if this is a symbolic region. */
1144 bool
1145 region::symbolic_p () const
1147 return get_kind () == RK_SYMBOLIC;
1150 /* Return true if this region is known to be zero bits in size. */
1152 bool
1153 region::empty_p () const
1155 bit_size_t num_bits;
1156 if (get_bit_size (&num_bits))
1157 if (num_bits == 0)
1158 return true;
1159 return false;
1162 /* Return true if this is a region for a decl with name DECL_NAME.
1163 Intended for use when debugging (for assertions and conditional
1164 breakpoints). */
1166 DEBUG_FUNCTION bool
1167 region::is_named_decl_p (const char *decl_name) const
1169 if (tree decl = maybe_get_decl ())
1170 if (DECL_NAME (decl)
1171 && !strcmp (IDENTIFIER_POINTER (DECL_NAME (decl)), decl_name))
1172 return true;
1173 return false;
1176 /* region's ctor. */
1178 region::region (complexity c, symbol::id_t id, const region *parent, tree type)
1179 : symbol (c, id),
1180 m_parent (parent), m_type (type),
1181 m_cached_offset (NULL), m_cached_init_sval_at_main (NULL)
1183 gcc_assert (type == NULL_TREE || TYPE_P (type));
1186 /* Comparator for use by vec<const region *>::qsort,
1187 using their IDs to order them. */
1190 region::cmp_ptr_ptr (const void *p1, const void *p2)
1192 const region * const *reg1 = (const region * const *)p1;
1193 const region * const *reg2 = (const region * const *)p2;
1195 return cmp_ids (*reg1, *reg2);
1198 /* Determine if a pointer to this region must be non-NULL.
1200 Generally, pointers to regions must be non-NULL, but pointers
1201 to symbolic_regions might, in fact, be NULL.
1203 This allows us to simulate functions like malloc and calloc with:
1204 - only one "outcome" from each statement,
1205 - the idea that the pointer is on the heap if non-NULL
1206 - the possibility that the pointer could be NULL
1207 - the idea that successive values returned from malloc are non-equal
1208 - to be able to zero-fill for calloc. */
1210 bool
1211 region::non_null_p () const
1213 switch (get_kind ())
1215 default:
1216 return true;
1217 case RK_SYMBOLIC:
1218 /* Are we within a symbolic_region? If so, it could be NULL, and we
1219 have to fall back on the constraints. */
1220 return false;
1221 case RK_HEAP_ALLOCATED:
1222 return false;
1226 /* Return true iff this region is defined in terms of SVAL. */
1228 bool
1229 region::involves_p (const svalue *sval) const
1231 if (const symbolic_region *symbolic_reg = dyn_cast_symbolic_region ())
1233 if (symbolic_reg->get_pointer ()->involves_p (sval))
1234 return true;
1237 return false;
1240 /* Comparator for trees to impose a deterministic ordering on
1241 T1 and T2. */
1243 static int
1244 tree_cmp (const_tree t1, const_tree t2)
1246 gcc_assert (t1);
1247 gcc_assert (t2);
1249 /* Test tree codes first. */
1250 if (TREE_CODE (t1) != TREE_CODE (t2))
1251 return TREE_CODE (t1) - TREE_CODE (t2);
1253 /* From this point on, we know T1 and T2 have the same tree code. */
1255 if (DECL_P (t1))
1257 if (DECL_NAME (t1) && DECL_NAME (t2))
1258 return strcmp (IDENTIFIER_POINTER (DECL_NAME (t1)),
1259 IDENTIFIER_POINTER (DECL_NAME (t2)));
1260 else
1262 if (DECL_NAME (t1))
1263 return -1;
1264 else if (DECL_NAME (t2))
1265 return 1;
1266 else
1267 return DECL_UID (t1) - DECL_UID (t2);
1271 switch (TREE_CODE (t1))
1273 case SSA_NAME:
1275 if (SSA_NAME_VAR (t1) && SSA_NAME_VAR (t2))
1277 int var_cmp = tree_cmp (SSA_NAME_VAR (t1), SSA_NAME_VAR (t2));
1278 if (var_cmp)
1279 return var_cmp;
1280 return SSA_NAME_VERSION (t1) - SSA_NAME_VERSION (t2);
1282 else
1284 if (SSA_NAME_VAR (t1))
1285 return -1;
1286 else if (SSA_NAME_VAR (t2))
1287 return 1;
1288 else
1289 return SSA_NAME_VERSION (t1) - SSA_NAME_VERSION (t2);
1292 break;
1294 case INTEGER_CST:
1295 return tree_int_cst_compare (t1, t2);
1297 case REAL_CST:
1299 const real_value *rv1 = TREE_REAL_CST_PTR (t1);
1300 const real_value *rv2 = TREE_REAL_CST_PTR (t2);
1301 if (real_compare (UNORDERED_EXPR, rv1, rv2))
1303 /* Impose an arbitrary order on NaNs relative to other NaNs
1304 and to non-NaNs. */
1305 if (int cmp_isnan = real_isnan (rv1) - real_isnan (rv2))
1306 return cmp_isnan;
1307 if (int cmp_issignaling_nan
1308 = real_issignaling_nan (rv1) - real_issignaling_nan (rv2))
1309 return cmp_issignaling_nan;
1310 return real_isneg (rv1) - real_isneg (rv2);
1312 if (real_compare (LT_EXPR, rv1, rv2))
1313 return -1;
1314 if (real_compare (GT_EXPR, rv1, rv2))
1315 return 1;
1316 return 0;
1319 case STRING_CST:
1320 return strcmp (TREE_STRING_POINTER (t1),
1321 TREE_STRING_POINTER (t2));
1323 default:
1324 gcc_unreachable ();
1325 break;
1328 gcc_unreachable ();
1330 return 0;
1333 /* qsort comparator for trees to impose a deterministic ordering on
1334 P1 and P2. */
1337 tree_cmp (const void *p1, const void *p2)
1339 const_tree t1 = *(const_tree const *)p1;
1340 const_tree t2 = *(const_tree const *)p2;
1342 return tree_cmp (t1, t2);
1345 /* class frame_region : public space_region. */
1347 frame_region::~frame_region ()
1349 for (map_t::iterator iter = m_locals.begin ();
1350 iter != m_locals.end ();
1351 ++iter)
1352 delete (*iter).second;
1355 void
1356 frame_region::accept (visitor *v) const
1358 region::accept (v);
1359 if (m_calling_frame)
1360 m_calling_frame->accept (v);
1363 /* Implementation of region::dump_to_pp vfunc for frame_region. */
1365 void
1366 frame_region::dump_to_pp (pretty_printer *pp, bool simple) const
1368 if (simple)
1369 pp_printf (pp, "frame: %qs@%i", function_name (&m_fun), get_stack_depth ());
1370 else
1371 pp_printf (pp, "frame_region(%qs, index: %i, depth: %i)",
1372 function_name (&m_fun), m_index, get_stack_depth ());
1375 void
1376 frame_region::print_dump_widget_label (pretty_printer *pp) const
1378 pp_printf (pp, "frame_region(%qs, index: %i, depth: %i)",
1379 function_name (&m_fun), m_index, get_stack_depth ());
1382 const decl_region *
1383 frame_region::get_region_for_local (region_model_manager *mgr,
1384 tree expr,
1385 const region_model_context *ctxt) const
1387 if (CHECKING_P)
1389 /* Verify that EXPR is a local or SSA name, and that it's for the
1390 correct function for this stack frame. */
1391 gcc_assert (TREE_CODE (expr) == PARM_DECL
1392 || TREE_CODE (expr) == VAR_DECL
1393 || TREE_CODE (expr) == SSA_NAME
1394 || TREE_CODE (expr) == RESULT_DECL);
1395 switch (TREE_CODE (expr))
1397 default:
1398 gcc_unreachable ();
1399 case VAR_DECL:
1400 gcc_assert (!is_global_var (expr));
1401 /* Fall through. */
1402 case PARM_DECL:
1403 case RESULT_DECL:
1404 gcc_assert (DECL_CONTEXT (expr) == m_fun.decl);
1405 break;
1406 case SSA_NAME:
1408 if (tree var = SSA_NAME_VAR (expr))
1410 if (DECL_P (var))
1411 gcc_assert (DECL_CONTEXT (var) == m_fun.decl);
1413 else if (ctxt)
1414 if (const extrinsic_state *ext_state = ctxt->get_ext_state ())
1415 if (const supergraph *sg
1416 = ext_state->get_engine ()->get_supergraph ())
1418 const gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
1419 const supernode *snode
1420 = sg->get_supernode_for_stmt (def_stmt);
1421 gcc_assert (snode->get_function () == &m_fun);
1424 break;
1428 /* Ideally we'd use mutable here. */
1429 map_t &mutable_locals = const_cast <map_t &> (m_locals);
1431 if (decl_region **slot = mutable_locals.get (expr))
1432 return *slot;
1433 decl_region *reg
1434 = new decl_region (mgr->alloc_symbol_id (), this, expr);
1435 mutable_locals.put (expr, reg);
1436 return reg;
1439 /* class globals_region : public space_region. */
1441 /* Implementation of region::dump_to_pp vfunc for globals_region. */
1443 void
1444 globals_region::dump_to_pp (pretty_printer *pp, bool simple) const
1446 if (simple)
1447 pp_string (pp, "::");
1448 else
1449 pp_string (pp, "globals");
1452 void
1453 globals_region::print_dump_widget_label (pretty_printer *pp) const
1455 pp_string (pp, "globals");
1458 /* class code_region : public map_region. */
1460 /* Implementation of region::dump_to_pp vfunc for code_region. */
1462 void
1463 code_region::dump_to_pp (pretty_printer *pp, bool simple) const
1465 if (simple)
1466 pp_string (pp, "code region");
1467 else
1468 pp_string (pp, "code_region()");
1471 void
1472 code_region::print_dump_widget_label (pretty_printer *pp) const
1474 pp_string (pp, "code region");
1477 /* class function_region : public region. */
1479 /* Implementation of region::dump_to_pp vfunc for function_region. */
1481 void
1482 function_region::dump_to_pp (pretty_printer *pp, bool simple) const
1484 if (simple)
1486 dump_quoted_tree (pp, m_fndecl);
1488 else
1490 pp_string (pp, "function_region(");
1491 dump_quoted_tree (pp, m_fndecl);
1492 pp_string (pp, ")");
1496 void
1497 function_region::print_dump_widget_label (pretty_printer *pp) const
1499 pp_string (pp, "function_region(");
1500 dump_quoted_tree (pp, m_fndecl);
1501 pp_string (pp, ")");
1504 /* class label_region : public region. */
1506 /* Implementation of region::dump_to_pp vfunc for label_region. */
1508 void
1509 label_region::dump_to_pp (pretty_printer *pp, bool simple) const
1511 if (simple)
1513 dump_quoted_tree (pp, m_label);
1515 else
1517 pp_string (pp, "label_region(");
1518 dump_quoted_tree (pp, m_label);
1519 pp_string (pp, ")");
1523 void
1524 label_region::print_dump_widget_label (pretty_printer *pp) const
1526 pp_string (pp, "label_region(");
1527 dump_quoted_tree (pp, m_label);
1528 pp_string (pp, ")");
1531 /* class stack_region : public region. */
1533 /* Implementation of region::dump_to_pp vfunc for stack_region. */
1535 void
1536 stack_region::dump_to_pp (pretty_printer *pp, bool simple) const
1538 if (simple)
1539 pp_string (pp, "stack region");
1540 else
1541 pp_string (pp, "stack_region()");
1544 void
1545 stack_region::print_dump_widget_label (pretty_printer *pp) const
1547 pp_string (pp, "stack region");
1550 /* class heap_region : public region. */
1552 /* Implementation of region::dump_to_pp vfunc for heap_region. */
1554 void
1555 heap_region::dump_to_pp (pretty_printer *pp, bool simple) const
1557 if (simple)
1558 pp_string (pp, "heap region");
1559 else
1560 pp_string (pp, "heap_region()");
1563 void
1564 heap_region::print_dump_widget_label (pretty_printer *pp) const
1566 pp_string (pp, "heap_region");
1569 /* class root_region : public region. */
1571 /* root_region's ctor. */
1573 root_region::root_region (symbol::id_t id)
1574 : region (complexity (1, 1), id, NULL, NULL_TREE)
1578 /* Implementation of region::dump_to_pp vfunc for root_region. */
1580 void
1581 root_region::dump_to_pp (pretty_printer *pp, bool simple) const
1583 if (simple)
1584 pp_string (pp, "root region");
1585 else
1586 pp_string (pp, "root_region()");
1589 void
1590 root_region::print_dump_widget_label (pretty_printer *pp) const
1592 pp_string (pp, "root region");
1595 /* class thread_local_region : public space_region. */
1597 void
1598 thread_local_region::dump_to_pp (pretty_printer *pp, bool simple) const
1600 if (simple)
1601 pp_string (pp, "thread_local_region");
1602 else
1603 pp_string (pp, "thread_local_region()");
1606 void
1607 thread_local_region::print_dump_widget_label (pretty_printer *pp) const
1609 pp_string (pp, "thread_local_region");
1612 /* class symbolic_region : public map_region. */
1614 /* symbolic_region's ctor. */
1616 symbolic_region::symbolic_region (symbol::id_t id, region *parent,
1617 const svalue *sval_ptr)
1618 : region (complexity::from_pair (parent, sval_ptr), id, parent,
1619 (sval_ptr->get_type ()
1620 ? TREE_TYPE (sval_ptr->get_type ())
1621 : NULL_TREE)),
1622 m_sval_ptr (sval_ptr)
1626 /* Implementation of region::accept vfunc for symbolic_region. */
1628 void
1629 symbolic_region::accept (visitor *v) const
1631 region::accept (v);
1632 m_sval_ptr->accept (v);
1635 /* Implementation of region::dump_to_pp vfunc for symbolic_region. */
1637 void
1638 symbolic_region::dump_to_pp (pretty_printer *pp, bool simple) const
1640 if (simple)
1642 pp_string (pp, "(*");
1643 m_sval_ptr->dump_to_pp (pp, simple);
1644 pp_string (pp, ")");
1646 else
1648 pp_string (pp, "symbolic_region(");
1649 get_parent_region ()->dump_to_pp (pp, simple);
1650 if (get_type ())
1652 pp_string (pp, ", ");
1653 print_quoted_type (pp, get_type ());
1655 pp_string (pp, ", ");
1656 m_sval_ptr->dump_to_pp (pp, simple);
1657 pp_string (pp, ")");
1661 void
1662 symbolic_region::print_dump_widget_label (pretty_printer *pp) const
1664 pp_string (pp, "symbolic_region: %<*%>");
1667 void
1668 symbolic_region::
1669 add_dump_widget_children (text_art::tree_widget &w,
1670 const text_art::dump_widget_info &dwi) const
1672 w.add_child (m_sval_ptr->make_dump_widget (dwi, "m_sval_ptr"));
1675 /* class decl_region : public region. */
1677 /* Implementation of region::dump_to_pp vfunc for decl_region. */
1679 void
1680 decl_region::dump_to_pp (pretty_printer *pp, bool simple) const
1682 if (simple)
1683 pp_printf (pp, "%E", m_decl);
1684 else
1686 pp_string (pp, "decl_region(");
1687 get_parent_region ()->dump_to_pp (pp, simple);
1688 pp_string (pp, ", ");
1689 print_quoted_type (pp, get_type ());
1690 pp_printf (pp, ", %qE)", m_decl);
1694 void
1695 decl_region::print_dump_widget_label (pretty_printer *pp) const
1697 pp_printf (pp, "decl_region(%qE)", m_decl);
1700 /* Get the stack depth for the frame containing this decl, or 0
1701 for a global. */
1704 decl_region::get_stack_depth () const
1706 if (get_parent_region () == NULL)
1707 return 0;
1708 if (const frame_region *frame_reg
1709 = get_parent_region ()->dyn_cast_frame_region ())
1710 return frame_reg->get_stack_depth ();
1711 return 0;
1714 /* If the underlying decl is in the global constant pool,
1715 return an svalue representing the constant value.
1716 Otherwise return NULL. */
1718 const svalue *
1719 decl_region::maybe_get_constant_value (region_model_manager *mgr) const
1721 if (VAR_P (m_decl)
1722 && DECL_IN_CONSTANT_POOL (m_decl)
1723 && DECL_INITIAL (m_decl)
1724 && TREE_CODE (DECL_INITIAL (m_decl)) == CONSTRUCTOR)
1725 return get_svalue_for_constructor (DECL_INITIAL (m_decl), mgr);
1726 return NULL;
1729 /* Implementation of decl_region::get_svalue_for_constructor
1730 for when the cached value hasn't yet been calculated. */
1732 const svalue *
1733 decl_region::calc_svalue_for_constructor (tree ctor,
1734 region_model_manager *mgr) const
1736 /* Create a binding map, applying ctor to it, using this
1737 decl_region as the base region when building child regions
1738 for offset calculations. */
1739 binding_map map;
1740 if (!map.apply_ctor_to_region (this, ctor, mgr))
1741 return mgr->get_or_create_unknown_svalue (get_type ());
1743 /* Return a compound svalue for the map we built. */
1744 return mgr->get_or_create_compound_svalue (get_type (), map);
1747 /* Get an svalue for CTOR, a CONSTRUCTOR for this region's decl. */
1749 const svalue *
1750 decl_region::get_svalue_for_constructor (tree ctor,
1751 region_model_manager *mgr) const
1753 gcc_assert (!TREE_CLOBBER_P (ctor));
1754 gcc_assert (ctor == DECL_INITIAL (m_decl));
1756 if (!m_ctor_svalue)
1757 m_ctor_svalue = calc_svalue_for_constructor (ctor, mgr);
1759 return m_ctor_svalue;
1762 /* For use on decl_regions for global variables.
1764 Get an svalue for the initial value of this region at entry to
1765 "main" (either based on DECL_INITIAL, or implicit initialization to
1766 zero.
1768 Return NULL if there is a problem. */
1770 const svalue *
1771 decl_region::get_svalue_for_initializer (region_model_manager *mgr) const
1773 tree init = DECL_INITIAL (m_decl);
1774 if (!init)
1776 /* If we have an "extern" decl then there may be an initializer in
1777 another TU. */
1778 if (DECL_EXTERNAL (m_decl))
1779 return NULL;
1781 if (empty_p ())
1782 return NULL;
1784 /* Implicit initialization to zero; use a compound_svalue for it.
1785 Doing so requires that we have a concrete binding for this region,
1786 which can fail if we have a region with unknown size
1787 (e.g. "extern const char arr[];"). */
1788 const binding_key *binding
1789 = binding_key::make (mgr->get_store_manager (), this);
1790 if (binding->symbolic_p ())
1791 return NULL;
1793 /* If we don't care about tracking the content of this region, then
1794 it's unused, and the value doesn't matter. */
1795 if (!tracked_p ())
1796 return NULL;
1798 binding_cluster c (this);
1799 c.zero_fill_region (mgr->get_store_manager (), this);
1800 return mgr->get_or_create_compound_svalue (TREE_TYPE (m_decl),
1801 c.get_map ());
1804 /* LTO can write out error_mark_node as the DECL_INITIAL for simple scalar
1805 values (to avoid writing out an extra section). */
1806 if (init == error_mark_node)
1807 return NULL;
1809 if (TREE_CODE (init) == CONSTRUCTOR)
1810 return get_svalue_for_constructor (init, mgr);
1812 /* Reuse the get_rvalue logic from region_model. */
1813 region_model m (mgr);
1814 return m.get_rvalue (path_var (init, 0), NULL);
1817 /* Subroutine of symnode_requires_tracking_p; return true if REF
1818 might imply that we should be tracking the value of its decl. */
1820 static bool
1821 ipa_ref_requires_tracking (ipa_ref *ref)
1823 /* If we have a load/store/alias of the symbol, then we'll track
1824 the decl's value. */
1825 if (ref->use != IPA_REF_ADDR)
1826 return true;
1828 if (ref->stmt == NULL)
1829 return true;
1831 switch (ref->stmt->code)
1833 default:
1834 return true;
1835 case GIMPLE_CALL:
1837 cgraph_node *caller_cnode = dyn_cast <cgraph_node *> (ref->referring);
1838 if (caller_cnode == NULL)
1839 return true;
1840 cgraph_edge *edge = caller_cnode->get_edge (ref->stmt);
1841 if (!edge)
1842 return true;
1843 if (edge->callee == NULL)
1844 return true; /* e.g. call through function ptr. */
1845 if (edge->callee->definition)
1846 return true;
1847 /* If we get here, then this ref is a pointer passed to
1848 a function we don't have the definition for. */
1849 return false;
1851 break;
1852 case GIMPLE_ASM:
1854 const gasm *asm_stmt = as_a <const gasm *> (ref->stmt);
1855 if (gimple_asm_noutputs (asm_stmt) > 0)
1856 return true;
1857 if (gimple_asm_nclobbers (asm_stmt) > 0)
1858 return true;
1859 /* If we get here, then this ref is the decl being passed
1860 by pointer to asm with no outputs. */
1861 return false;
1863 break;
1867 /* Determine if the decl for SYMNODE should have binding_clusters
1868 in our state objects; return false to optimize away tracking
1869 certain decls in our state objects, as an optimization. */
1871 static bool
1872 symnode_requires_tracking_p (symtab_node *symnode)
1874 gcc_assert (symnode);
1875 if (symnode->externally_visible)
1876 return true;
1877 tree context_fndecl = DECL_CONTEXT (symnode->decl);
1878 if (context_fndecl == NULL)
1879 return true;
1880 if (TREE_CODE (context_fndecl) != FUNCTION_DECL)
1881 return true;
1882 for (auto ref : symnode->ref_list.referring)
1883 if (ipa_ref_requires_tracking (ref))
1884 return true;
1886 /* If we get here, then we don't have uses of this decl that require
1887 tracking; we never read from it or write to it explicitly. */
1888 return false;
1891 /* Subroutine of decl_region ctor: determine whether this decl_region
1892 can have binding_clusters; return false to optimize away tracking
1893 of certain decls in our state objects, as an optimization. */
1895 bool
1896 decl_region::calc_tracked_p (tree decl)
1898 /* Precondition of symtab_node::get. */
1899 if (TREE_CODE (decl) == VAR_DECL
1900 && (TREE_STATIC (decl) || DECL_EXTERNAL (decl) || in_lto_p))
1901 if (symtab_node *symnode = symtab_node::get (decl))
1902 return symnode_requires_tracking_p (symnode);
1903 return true;
1906 /* class field_region : public region. */
1908 /* Implementation of region::dump_to_pp vfunc for field_region. */
1910 void
1911 field_region::dump_to_pp (pretty_printer *pp, bool simple) const
1913 if (simple)
1915 get_parent_region ()->dump_to_pp (pp, simple);
1916 pp_string (pp, ".");
1917 pp_printf (pp, "%E", m_field);
1919 else
1921 pp_string (pp, "field_region(");
1922 get_parent_region ()->dump_to_pp (pp, simple);
1923 pp_string (pp, ", ");
1924 print_quoted_type (pp, get_type ());
1925 pp_printf (pp, ", %qE)", m_field);
1929 void
1930 field_region::print_dump_widget_label (pretty_printer *pp) const
1932 pp_printf (pp, "field_region(%qE)", m_field);
1935 /* Implementation of region::get_relative_concrete_offset vfunc
1936 for field_region. */
1938 bool
1939 field_region::get_relative_concrete_offset (bit_offset_t *out) const
1941 /* Compare with e.g. gimple-fold.cc's
1942 fold_nonarray_ctor_reference. */
1943 tree byte_offset = DECL_FIELD_OFFSET (m_field);
1944 if (TREE_CODE (byte_offset) != INTEGER_CST)
1945 return false;
1946 tree field_offset = DECL_FIELD_BIT_OFFSET (m_field);
1947 /* Compute bit offset of the field. */
1948 offset_int bitoffset
1949 = (wi::to_offset (field_offset)
1950 + (wi::to_offset (byte_offset) << LOG2_BITS_PER_UNIT));
1951 *out = bitoffset;
1952 return true;
1956 /* Implementation of region::get_relative_symbolic_offset vfunc
1957 for field_region.
1958 If known, the returned svalue is equal to the offset converted to bytes and
1959 rounded off. */
1961 const svalue *
1962 field_region::get_relative_symbolic_offset (region_model_manager *mgr) const
1964 bit_offset_t out;
1965 if (get_relative_concrete_offset (&out))
1967 tree cst_tree
1968 = wide_int_to_tree (ptrdiff_type_node, out / BITS_PER_UNIT);
1969 return mgr->get_or_create_constant_svalue (cst_tree);
1971 return mgr->get_or_create_unknown_svalue (ptrdiff_type_node);
1974 /* class element_region : public region. */
1976 /* Implementation of region::accept vfunc for element_region. */
1978 void
1979 element_region::accept (visitor *v) const
1981 region::accept (v);
1982 m_index->accept (v);
1985 /* Implementation of region::dump_to_pp vfunc for element_region. */
1987 void
1988 element_region::dump_to_pp (pretty_printer *pp, bool simple) const
1990 if (simple)
1992 //pp_string (pp, "(");
1993 get_parent_region ()->dump_to_pp (pp, simple);
1994 pp_string (pp, "[");
1995 m_index->dump_to_pp (pp, simple);
1996 pp_string (pp, "]");
1997 //pp_string (pp, ")");
1999 else
2001 pp_string (pp, "element_region(");
2002 get_parent_region ()->dump_to_pp (pp, simple);
2003 pp_string (pp, ", ");
2004 print_quoted_type (pp, get_type ());
2005 pp_string (pp, ", ");
2006 m_index->dump_to_pp (pp, simple);
2007 pp_printf (pp, ")");
2011 void
2012 element_region::print_dump_widget_label (pretty_printer *pp) const
2014 pp_printf (pp, "element_region: %<[]%>");
2017 void
2018 element_region::
2019 add_dump_widget_children (text_art::tree_widget &w,
2020 const text_art::dump_widget_info &dwi) const
2022 w.add_child (m_index->make_dump_widget (dwi, "m_index"));
2025 /* Implementation of region::get_relative_concrete_offset vfunc
2026 for element_region. */
2028 bool
2029 element_region::get_relative_concrete_offset (bit_offset_t *out) const
2031 if (tree idx_cst = m_index->maybe_get_constant ())
2033 gcc_assert (TREE_CODE (idx_cst) == INTEGER_CST);
2035 tree elem_type = get_type ();
2036 offset_int element_idx = wi::to_offset (idx_cst);
2038 /* First, use int_size_in_bytes, to reject the case where we
2039 have an incomplete type, or a non-constant value. */
2040 HOST_WIDE_INT hwi_byte_size = int_size_in_bytes (elem_type);
2041 if (hwi_byte_size > 0)
2043 offset_int element_bit_size
2044 = hwi_byte_size << LOG2_BITS_PER_UNIT;
2045 offset_int element_bit_offset
2046 = element_idx * element_bit_size;
2047 *out = element_bit_offset;
2048 return true;
2051 return false;
2054 /* Implementation of region::get_relative_symbolic_offset vfunc
2055 for element_region. */
2057 const svalue *
2058 element_region::get_relative_symbolic_offset (region_model_manager *mgr) const
2060 tree elem_type = get_type ();
2062 /* First, use int_size_in_bytes, to reject the case where we
2063 have an incomplete type, or a non-constant value. */
2064 HOST_WIDE_INT hwi_byte_size = int_size_in_bytes (elem_type);
2065 if (hwi_byte_size > 0)
2067 tree byte_size_tree = wide_int_to_tree (ptrdiff_type_node,
2068 hwi_byte_size);
2069 const svalue *byte_size_sval
2070 = mgr->get_or_create_constant_svalue (byte_size_tree);
2071 return mgr->get_or_create_binop (NULL_TREE, MULT_EXPR,
2072 m_index, byte_size_sval);
2074 return mgr->get_or_create_unknown_svalue (ptrdiff_type_node);
2077 /* class offset_region : public region. */
2079 /* Implementation of region::accept vfunc for offset_region. */
2081 void
2082 offset_region::accept (visitor *v) const
2084 region::accept (v);
2085 m_byte_offset->accept (v);
2088 /* Implementation of region::dump_to_pp vfunc for offset_region. */
2090 void
2091 offset_region::dump_to_pp (pretty_printer *pp, bool simple) const
2093 if (simple)
2095 //pp_string (pp, "(");
2096 get_parent_region ()->dump_to_pp (pp, simple);
2097 pp_string (pp, "+");
2098 m_byte_offset->dump_to_pp (pp, simple);
2099 //pp_string (pp, ")");
2101 else
2103 pp_string (pp, "offset_region(");
2104 get_parent_region ()->dump_to_pp (pp, simple);
2105 pp_string (pp, ", ");
2106 print_quoted_type (pp, get_type ());
2107 pp_string (pp, ", ");
2108 m_byte_offset->dump_to_pp (pp, simple);
2109 pp_printf (pp, ")");
2113 void
2114 offset_region::print_dump_widget_label (pretty_printer *pp) const
2116 pp_printf (pp, "offset_region");
2119 void
2120 offset_region::
2121 add_dump_widget_children (text_art::tree_widget &w,
2122 const text_art::dump_widget_info &dwi) const
2124 w.add_child (m_byte_offset->make_dump_widget (dwi, "m_byte_offset"));
2127 const svalue *
2128 offset_region::get_bit_offset (region_model_manager *mgr) const
2130 const svalue *bits_per_byte_sval
2131 = mgr->get_or_create_int_cst (NULL_TREE, BITS_PER_UNIT);
2132 return mgr->get_or_create_binop (NULL_TREE, MULT_EXPR,
2133 m_byte_offset, bits_per_byte_sval);
2136 /* Implementation of region::get_relative_concrete_offset vfunc
2137 for offset_region. */
2139 bool
2140 offset_region::get_relative_concrete_offset (bit_offset_t *out) const
2142 if (tree byte_offset_cst = m_byte_offset->maybe_get_constant ())
2144 gcc_assert (TREE_CODE (byte_offset_cst) == INTEGER_CST);
2145 /* Use a signed value for the byte offset, to handle
2146 negative offsets. */
2147 HOST_WIDE_INT byte_offset
2148 = wi::to_offset (byte_offset_cst).to_shwi ();
2149 HOST_WIDE_INT bit_offset = byte_offset * BITS_PER_UNIT;
2150 *out = bit_offset;
2151 return true;
2153 return false;
2156 /* Implementation of region::get_relative_symbolic_offset vfunc
2157 for offset_region. */
2159 const svalue *
2160 offset_region::get_relative_symbolic_offset (region_model_manager *mgr
2161 ATTRIBUTE_UNUSED) const
2163 return get_byte_offset ();
2166 /* class sized_region : public region. */
2168 /* Implementation of region::accept vfunc for sized_region. */
2170 void
2171 sized_region::accept (visitor *v) const
2173 region::accept (v);
2174 m_byte_size_sval->accept (v);
2177 /* Implementation of region::dump_to_pp vfunc for sized_region. */
2179 void
2180 sized_region::dump_to_pp (pretty_printer *pp, bool simple) const
2182 if (simple)
2184 pp_string (pp, "SIZED_REG(");
2185 get_parent_region ()->dump_to_pp (pp, simple);
2186 pp_string (pp, ", ");
2187 m_byte_size_sval->dump_to_pp (pp, simple);
2188 pp_string (pp, ")");
2190 else
2192 pp_string (pp, "sized_region(");
2193 get_parent_region ()->dump_to_pp (pp, simple);
2194 pp_string (pp, ", ");
2195 m_byte_size_sval->dump_to_pp (pp, simple);
2196 pp_printf (pp, ")");
2200 void
2201 sized_region::print_dump_widget_label (pretty_printer *pp) const
2203 pp_printf (pp, "sized_region");
2206 void
2207 sized_region::
2208 add_dump_widget_children (text_art::tree_widget &w,
2209 const text_art::dump_widget_info &dwi) const
2211 w.add_child (m_byte_size_sval->make_dump_widget (dwi, "m_byte_size_sval"));
2214 /* Implementation of region::get_byte_size vfunc for sized_region. */
2216 bool
2217 sized_region::get_byte_size (byte_size_t *out) const
2219 if (tree cst = m_byte_size_sval->maybe_get_constant ())
2221 gcc_assert (TREE_CODE (cst) == INTEGER_CST);
2222 *out = tree_to_uhwi (cst);
2223 return true;
2225 return false;
2228 /* Implementation of region::get_bit_size vfunc for sized_region. */
2230 bool
2231 sized_region::get_bit_size (bit_size_t *out) const
2233 byte_size_t byte_size;
2234 if (!get_byte_size (&byte_size))
2235 return false;
2236 *out = byte_size * BITS_PER_UNIT;
2237 return true;
2240 /* Implementation of region::get_bit_size_sval vfunc for sized_region. */
2242 const svalue *
2243 sized_region::get_bit_size_sval (region_model_manager *mgr) const
2245 const svalue *bits_per_byte_sval
2246 = mgr->get_or_create_int_cst (NULL_TREE, BITS_PER_UNIT);
2247 return mgr->get_or_create_binop (NULL_TREE, MULT_EXPR,
2248 m_byte_size_sval, bits_per_byte_sval);
2251 /* class cast_region : public region. */
2253 /* Implementation of region::dump_to_pp vfunc for cast_region. */
2255 void
2256 cast_region::dump_to_pp (pretty_printer *pp, bool simple) const
2258 if (simple)
2260 pp_string (pp, "CAST_REG(");
2261 print_quoted_type (pp, get_type ());
2262 pp_string (pp, ", ");
2263 get_parent_region ()->dump_to_pp (pp, simple);
2264 pp_string (pp, ")");
2266 else
2268 pp_string (pp, "cast_region(");
2269 get_parent_region ()->dump_to_pp (pp, simple);
2270 pp_string (pp, ", ");
2271 print_quoted_type (pp, get_type ());
2272 pp_printf (pp, ")");
2276 void
2277 cast_region::print_dump_widget_label (pretty_printer *pp) const
2279 pp_printf (pp, "cast_region");
2282 /* Implementation of region::get_relative_concrete_offset vfunc
2283 for cast_region. */
2285 bool
2286 cast_region::get_relative_concrete_offset (bit_offset_t *out) const
2288 *out = (int) 0;
2289 return true;
2292 /* class heap_allocated_region : public region. */
2294 /* Implementation of region::dump_to_pp vfunc for heap_allocated_region. */
2296 void
2297 heap_allocated_region::dump_to_pp (pretty_printer *pp, bool simple) const
2299 if (simple)
2300 pp_printf (pp, "HEAP_ALLOCATED_REGION(%i)", get_id ());
2301 else
2302 pp_printf (pp, "heap_allocated_region(%i)", get_id ());
2305 void
2306 heap_allocated_region::print_dump_widget_label (pretty_printer *pp) const
2308 pp_printf (pp, "heap_allocated_region");
2311 /* class alloca_region : public region. */
2313 /* Implementation of region::dump_to_pp vfunc for alloca_region. */
2315 void
2316 alloca_region::dump_to_pp (pretty_printer *pp, bool simple) const
2318 if (simple)
2319 pp_printf (pp, "ALLOCA_REGION(%i)", get_id ());
2320 else
2321 pp_printf (pp, "alloca_region(%i)", get_id ());
2324 void
2325 alloca_region::print_dump_widget_label (pretty_printer *pp) const
2327 pp_printf (pp, "alloca_region");
2330 /* class string_region : public region. */
2332 /* Implementation of region::dump_to_pp vfunc for string_region. */
2334 void
2335 string_region::dump_to_pp (pretty_printer *pp, bool simple) const
2337 if (simple)
2338 dump_tree (pp, m_string_cst);
2339 else
2341 pp_string (pp, "string_region(");
2342 dump_tree (pp, m_string_cst);
2343 if (!flag_dump_noaddr)
2345 pp_string (pp, " (");
2346 pp_pointer (pp, m_string_cst);
2347 pp_string (pp, "))");
2352 void
2353 string_region::print_dump_widget_label (pretty_printer *pp) const
2355 pp_string (pp, "string_region(");
2356 dump_tree (pp, m_string_cst);
2357 pp_string (pp, ")");
2360 /* class bit_range_region : public region. */
2362 /* Implementation of region::dump_to_pp vfunc for bit_range_region. */
2364 void
2365 bit_range_region::dump_to_pp (pretty_printer *pp, bool simple) const
2367 if (simple)
2369 pp_string (pp, "BIT_RANGE_REG(");
2370 get_parent_region ()->dump_to_pp (pp, simple);
2371 pp_string (pp, ", ");
2372 m_bits.dump_to_pp (pp);
2373 pp_string (pp, ")");
2375 else
2377 pp_string (pp, "bit_range_region(");
2378 get_parent_region ()->dump_to_pp (pp, simple);
2379 pp_string (pp, ", ");
2380 m_bits.dump_to_pp (pp);
2381 pp_printf (pp, ")");
2385 void
2386 bit_range_region::print_dump_widget_label (pretty_printer *pp) const
2388 pp_printf (pp, "bit_range_region(m_bits: ");
2389 m_bits.dump_to_pp (pp);
2390 pp_string (pp, ")");
2393 /* Implementation of region::get_byte_size vfunc for bit_range_region. */
2395 bool
2396 bit_range_region::get_byte_size (byte_size_t *out) const
2398 if (m_bits.m_size_in_bits % BITS_PER_UNIT == 0)
2400 *out = m_bits.m_size_in_bits / BITS_PER_UNIT;
2401 return true;
2403 return false;
2406 /* Implementation of region::get_bit_size vfunc for bit_range_region. */
2408 bool
2409 bit_range_region::get_bit_size (bit_size_t *out) const
2411 *out = m_bits.m_size_in_bits;
2412 return true;
2415 /* Implementation of region::get_byte_size_sval vfunc for bit_range_region. */
2417 const svalue *
2418 bit_range_region::get_byte_size_sval (region_model_manager *mgr) const
2420 if (m_bits.m_size_in_bits % BITS_PER_UNIT != 0)
2421 return mgr->get_or_create_unknown_svalue (size_type_node);
2423 HOST_WIDE_INT num_bytes = m_bits.m_size_in_bits.to_shwi () / BITS_PER_UNIT;
2424 return mgr->get_or_create_int_cst (size_type_node, num_bytes);
2427 /* Implementation of region::get_bit_size_sval vfunc for bit_range_region. */
2429 const svalue *
2430 bit_range_region::get_bit_size_sval (region_model_manager *mgr) const
2432 return mgr->get_or_create_int_cst (size_type_node,
2433 m_bits.m_size_in_bits);
2436 /* Implementation of region::get_relative_concrete_offset vfunc for
2437 bit_range_region. */
2439 bool
2440 bit_range_region::get_relative_concrete_offset (bit_offset_t *out) const
2442 *out = m_bits.get_start_bit_offset ();
2443 return true;
2446 /* Implementation of region::get_relative_symbolic_offset vfunc for
2447 bit_range_region.
2448 The returned svalue is equal to the offset converted to bytes and
2449 rounded off. */
2451 const svalue *
2452 bit_range_region::get_relative_symbolic_offset (region_model_manager *mgr)
2453 const
2455 byte_offset_t start_byte = m_bits.get_start_bit_offset () / BITS_PER_UNIT;
2456 tree start_bit_tree = wide_int_to_tree (ptrdiff_type_node, start_byte);
2457 return mgr->get_or_create_constant_svalue (start_bit_tree);
2460 /* class var_arg_region : public region. */
2462 void
2463 var_arg_region::dump_to_pp (pretty_printer *pp, bool simple) const
2465 if (simple)
2467 pp_string (pp, "VAR_ARG_REG(");
2468 get_parent_region ()->dump_to_pp (pp, simple);
2469 pp_printf (pp, ", arg_idx: %d)", m_idx);
2471 else
2473 pp_string (pp, "var_arg_region(");
2474 get_parent_region ()->dump_to_pp (pp, simple);
2475 pp_printf (pp, ", arg_idx: %d)", m_idx);
2479 void
2480 var_arg_region::print_dump_widget_label (pretty_printer *pp) const
2482 pp_printf (pp, "var_arg_region(arg_idx: %i)", m_idx);
2485 /* Get the frame_region for this var_arg_region. */
2487 const frame_region *
2488 var_arg_region::get_frame_region () const
2490 gcc_assert (get_parent_region ());
2491 return as_a <const frame_region *> (get_parent_region ());
2494 /* class errno_region : public region. */
2496 void
2497 errno_region::dump_to_pp (pretty_printer *pp, bool simple) const
2499 if (simple)
2500 pp_string (pp, "errno_region");
2501 else
2502 pp_string (pp, "errno_region()");
2505 void
2506 errno_region::print_dump_widget_label (pretty_printer *pp) const
2508 pp_printf (pp, "errno_region");
2511 /* class private_region : public region. */
2513 void
2514 private_region::dump_to_pp (pretty_printer *pp, bool simple) const
2516 if (simple)
2517 pp_printf (pp, "PRIVATE_REG(%qs)", m_desc);
2518 else
2519 pp_printf (pp, "private_region(%qs)", m_desc);
2522 void
2523 private_region::print_dump_widget_label (pretty_printer *pp) const
2525 pp_printf (pp, "private_region(%qs)", m_desc);
2528 /* class unknown_region : public region. */
2530 /* Implementation of region::dump_to_pp vfunc for unknown_region. */
2532 void
2533 unknown_region::dump_to_pp (pretty_printer *pp, bool /*simple*/) const
2535 pp_string (pp, "UNKNOWN_REGION");
2538 void
2539 unknown_region::print_dump_widget_label (pretty_printer *pp) const
2541 pp_printf (pp, "unknown_region");
2544 } // namespace ana
2546 #endif /* #if ENABLE_ANALYZER */