2 Copyright (C) 2019-2022 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)
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 #ifndef GCC_ANALYZER_SVALUE_H
22 #define GCC_ANALYZER_SVALUE_H
24 #include "analyzer/complexity.h"
30 /* An enum for discriminating between the different concrete subclasses
55 /* svalue and its subclasses.
57 The class hierarchy looks like this (using indentation to show
58 inheritance, and with svalue_kinds shown for the concrete subclasses):
61 region_svalue (SK_REGION): a pointer to a region
62 constant_svalue (SK_CONSTANT): a constant
63 unknown_svalue (SK_UNKNOWN): an unknowable value
64 poisoned_svalue (SK_POISONED): a unusable value (undefined)
65 setjmp_svalue (SK_SETJMP): a setjmp/longjmp buffer
66 initial_svalue (SK_INITIAL): the initial value of a region
67 unaryop_svalue (SK_UNARYOP): unary operation on another svalue
68 binop_svalue (SK_BINOP): binary operation on two svalues
69 sub_svalue (SK_SUB): the result of accessing a subregion
70 repeated_svalue (SK_REPEATED): repeating an svalue to fill a larger region
71 bits_within_svalue (SK_BITS_WITHIN): a range of bits/bytes within a larger
73 unmergeable_svalue (SK_UNMERGEABLE): a value that is so interesting
74 from a control-flow perspective that it can inhibit state-merging
75 placeholder_svalue (SK_PLACEHOLDER): for use in selftests.
76 widening_svalue (SK_WIDENING): a merger of two svalues (possibly
78 compound_svalue (SK_COMPOUND): a mapping of bit-ranges to svalues
79 conjured_svalue (SK_CONJURED): a value arising from a stmt
80 asm_output_svalue (SK_ASM_OUTPUT): an output from a deterministic
82 const_fn_result_svalue (SK_CONST_FN_RESULT): the return value from
83 a function with __attribute((const)) for given inputs. */
85 /* An abstract base class representing a value held by a region of memory. */
92 tree
get_type () const { return m_type
; }
94 virtual enum svalue_kind
get_kind () const = 0;
96 void print (const region_model
&model
,
97 pretty_printer
*pp
) const;
99 virtual void dump_to_pp (pretty_printer
*pp
, bool simple
) const = 0;
100 void dump (bool simple
=true) const;
101 label_text
get_desc (bool simple
=true) const;
103 json::value
*to_json () const;
105 virtual const region_svalue
*
106 dyn_cast_region_svalue () const { return NULL
; }
107 virtual const constant_svalue
*
108 dyn_cast_constant_svalue () const { return NULL
; }
109 virtual const poisoned_svalue
*
110 dyn_cast_poisoned_svalue () const { return NULL
; }
111 virtual const setjmp_svalue
*
112 dyn_cast_setjmp_svalue () const { return NULL
; }
113 virtual const initial_svalue
*
114 dyn_cast_initial_svalue () const { return NULL
; }
115 virtual const unaryop_svalue
*
116 dyn_cast_unaryop_svalue () const { return NULL
; }
117 virtual const binop_svalue
*
118 dyn_cast_binop_svalue () const { return NULL
; }
119 virtual const sub_svalue
*
120 dyn_cast_sub_svalue () const { return NULL
; }
121 virtual const repeated_svalue
*
122 dyn_cast_repeated_svalue () const { return NULL
; }
123 virtual const bits_within_svalue
*
124 dyn_cast_bits_within_svalue () const { return NULL
; }
125 virtual const unmergeable_svalue
*
126 dyn_cast_unmergeable_svalue () const { return NULL
; }
127 virtual const widening_svalue
*
128 dyn_cast_widening_svalue () const { return NULL
; }
129 virtual const compound_svalue
*
130 dyn_cast_compound_svalue () const { return NULL
; }
131 virtual const conjured_svalue
*
132 dyn_cast_conjured_svalue () const { return NULL
; }
133 virtual const asm_output_svalue
*
134 dyn_cast_asm_output_svalue () const { return NULL
; }
135 virtual const const_fn_result_svalue
*
136 dyn_cast_const_fn_result_svalue () const { return NULL
; }
138 tree
maybe_get_constant () const;
139 const region
*maybe_get_region () const;
140 const svalue
*maybe_undo_cast () const;
141 const svalue
*unwrap_any_unmergeable () const;
143 const svalue
*can_merge_p (const svalue
*other
,
144 region_model_manager
*mgr
,
145 model_merger
*merger
) const;
147 const complexity
&get_complexity () const { return m_complexity
; }
149 virtual void accept (visitor
*v
) const = 0;
151 bool live_p (const svalue_set
*live_svalues
,
152 const region_model
*model
) const;
153 virtual bool implicitly_live_p (const svalue_set
*live_svalues
,
154 const region_model
*model
) const;
156 static int cmp_ptr (const svalue
*, const svalue
*);
157 static int cmp_ptr_ptr (const void *, const void *);
159 bool involves_p (const svalue
*other
) const;
162 extract_bit_range (tree type
,
163 const bit_range
&subrange
,
164 region_model_manager
*mgr
) const;
166 virtual const svalue
*
167 maybe_fold_bits_within (tree type
,
168 const bit_range
&subrange
,
169 region_model_manager
*mgr
) const;
171 virtual bool all_zeroes_p () const;
173 /* Can this svalue be involved in constraints and sm-state?
174 Most can, but UNKNOWN and POISONED svalues are singletons
175 per-type and thus it's meaningless for them to "have state". */
176 virtual bool can_have_associated_state_p () const { return true; }
178 const region
*maybe_get_deref_base_region () const;
181 svalue (complexity c
, tree type
)
182 : m_complexity (c
), m_type (type
)
186 complexity m_complexity
;
190 /* Concrete subclass of svalue representing a pointer value that points to
193 class region_svalue
: public svalue
196 /* A support class for uniquifying instances of region_svalue. */
199 key_t (tree type
, const region
*reg
)
200 : m_type (type
), m_reg (reg
)
203 hashval_t
hash () const
205 inchash::hash hstate
;
206 hstate
.add_ptr (m_type
);
207 hstate
.add_ptr (m_reg
);
208 return hstate
.end ();
211 bool operator== (const key_t
&other
) const
213 return (m_type
== other
.m_type
&& m_reg
== other
.m_reg
);
216 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
217 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
218 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
219 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
225 region_svalue (tree type
, const region
*reg
)
226 : svalue (complexity (reg
), type
),
229 gcc_assert (m_reg
!= NULL
);
232 enum svalue_kind
get_kind () const final override
{ return SK_REGION
; }
233 const region_svalue
*
234 dyn_cast_region_svalue () const final override
{ return this; }
236 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
237 void accept (visitor
*v
) const final override
;
238 bool implicitly_live_p (const svalue_set
*,
239 const region_model
*) const final override
;
241 const region
* get_pointee () const { return m_reg
; }
243 static tristate
eval_condition (const region_svalue
*lhs_ptr
,
245 const region_svalue
*rhs_ptr
);
256 is_a_helper
<const region_svalue
*>::test (const svalue
*sval
)
258 return sval
->get_kind () == SK_REGION
;
261 template <> struct default_hash_traits
<region_svalue::key_t
>
262 : public member_function_hash_traits
<region_svalue::key_t
>
264 static const bool empty_zero_p
= false;
269 /* Concrete subclass of svalue representing a specific constant value. */
271 class constant_svalue
: public svalue
274 constant_svalue (tree cst_expr
)
275 : svalue (complexity (1, 1), TREE_TYPE (cst_expr
)), m_cst_expr (cst_expr
)
277 gcc_assert (cst_expr
);
278 gcc_assert (CONSTANT_CLASS_P (cst_expr
));
281 enum svalue_kind
get_kind () const final override
{ return SK_CONSTANT
; }
282 const constant_svalue
*
283 dyn_cast_constant_svalue () const final override
{ return this; }
285 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
286 void accept (visitor
*v
) const final override
;
287 bool implicitly_live_p (const svalue_set
*,
288 const region_model
*) const final override
;
290 tree
get_constant () const { return m_cst_expr
; }
291 static tristate
eval_condition (const constant_svalue
*lhs
,
293 const constant_svalue
*rhs
);
296 maybe_fold_bits_within (tree type
,
297 const bit_range
&subrange
,
298 region_model_manager
*mgr
) const final override
;
300 bool all_zeroes_p () const final override
;
311 is_a_helper
<const constant_svalue
*>::test (const svalue
*sval
)
313 return sval
->get_kind () == SK_CONSTANT
;
318 /* Concrete subclass of svalue representing an unknowable value, the bottom
319 value when thinking of svalues as a lattice.
320 This is a singleton (w.r.t. its manager): there is a single unknown_svalue
321 per type. Self-comparisons of such instances yield "unknown". */
323 class unknown_svalue
: public svalue
326 unknown_svalue (tree type
)
327 : svalue (complexity (1, 1), type
)
330 enum svalue_kind
get_kind () const final override
{ return SK_UNKNOWN
; }
332 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
333 void accept (visitor
*v
) const final override
;
336 maybe_fold_bits_within (tree type
,
337 const bit_range
&subrange
,
338 region_model_manager
*mgr
) const final override
;
340 /* Unknown values are singletons per-type, so can't have state. */
341 bool can_have_associated_state_p () const final override
{ return false; }
344 /* An enum describing a particular kind of "poisoned" value. */
348 /* For use to describe uninitialized memory. */
351 /* For use to describe freed memory. */
354 /* For use on pointers to regions within popped stack frames. */
355 POISON_KIND_POPPED_STACK
358 extern const char *poison_kind_to_str (enum poison_kind
);
360 /* Concrete subclass of svalue representing a value that should not
361 be used (e.g. uninitialized memory, freed memory). */
363 class poisoned_svalue
: public svalue
366 /* A support class for uniquifying instances of poisoned_svalue. */
369 key_t (enum poison_kind kind
, tree type
)
370 : m_kind (kind
), m_type (type
)
373 hashval_t
hash () const
375 inchash::hash hstate
;
376 hstate
.add_int (m_kind
);
377 hstate
.add_ptr (m_type
);
378 return hstate
.end ();
381 bool operator== (const key_t
&other
) const
383 return (m_kind
== other
.m_kind
&& m_type
== other
.m_type
);
386 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
387 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
388 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
389 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
391 enum poison_kind m_kind
;
395 poisoned_svalue (enum poison_kind kind
, tree type
)
396 : svalue (complexity (1, 1), type
), m_kind (kind
) {}
398 enum svalue_kind
get_kind () const final override
{ return SK_POISONED
; }
399 const poisoned_svalue
*
400 dyn_cast_poisoned_svalue () const final override
{ return this; }
402 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
403 void accept (visitor
*v
) const final override
;
406 maybe_fold_bits_within (tree type
,
407 const bit_range
&subrange
,
408 region_model_manager
*mgr
) const final override
;
410 enum poison_kind
get_poison_kind () const { return m_kind
; }
412 /* Poisoned svalues are singletons per-type, so can't have state. */
413 bool can_have_associated_state_p () const final override
{ return false; }
416 enum poison_kind m_kind
;
424 is_a_helper
<const poisoned_svalue
*>::test (const svalue
*sval
)
426 return sval
->get_kind () == SK_POISONED
;
429 template <> struct default_hash_traits
<poisoned_svalue::key_t
>
430 : public member_function_hash_traits
<poisoned_svalue::key_t
>
432 static const bool empty_zero_p
= false;
437 /* A bundle of information recording a setjmp/sigsetjmp call, corresponding
438 roughly to a jmp_buf. */
442 setjmp_record (const exploded_node
*enode
,
443 const gcall
*setjmp_call
)
444 : m_enode (enode
), m_setjmp_call (setjmp_call
)
448 bool operator== (const setjmp_record
&other
) const
450 return (m_enode
== other
.m_enode
451 && m_setjmp_call
== other
.m_setjmp_call
);
454 void add_to_hash (inchash::hash
*hstate
) const
456 hstate
->add_ptr (m_enode
);
457 hstate
->add_ptr (m_setjmp_call
);
460 static int cmp (const setjmp_record
&rec1
, const setjmp_record
&rec2
);
462 const exploded_node
*m_enode
;
463 const gcall
*m_setjmp_call
;
466 /* Concrete subclass of svalue representing buffers for setjmp/sigsetjmp,
467 so that longjmp/siglongjmp can potentially "return" to an entirely
468 different function. */
470 class setjmp_svalue
: public svalue
473 /* A support class for uniquifying instances of poisoned_svalue. */
476 key_t (const setjmp_record
&record
, tree type
)
477 : m_record (record
), m_type (type
)
480 hashval_t
hash () const
482 inchash::hash hstate
;
483 m_record
.add_to_hash (&hstate
);
484 hstate
.add_ptr (m_type
);
485 return hstate
.end ();
488 bool operator== (const key_t
&other
) const
490 return (m_record
== other
.m_record
&& m_type
== other
.m_type
);
493 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
494 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
495 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
496 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
498 setjmp_record m_record
;
502 setjmp_svalue (const setjmp_record
&setjmp_record
,
504 : svalue (complexity (1, 1), type
), m_setjmp_record (setjmp_record
)
507 enum svalue_kind
get_kind () const final override
{ return SK_SETJMP
; }
508 const setjmp_svalue
*
509 dyn_cast_setjmp_svalue () const final override
{ return this; }
511 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
512 void accept (visitor
*v
) const final override
;
514 int get_enode_index () const;
516 const setjmp_record
&get_setjmp_record () const { return m_setjmp_record
; }
519 setjmp_record m_setjmp_record
;
527 is_a_helper
<const setjmp_svalue
*>::test (const svalue
*sval
)
529 return sval
->get_kind () == SK_SETJMP
;
532 template <> struct default_hash_traits
<setjmp_svalue::key_t
>
533 : public member_function_hash_traits
<setjmp_svalue::key_t
>
535 static const bool empty_zero_p
= false;
540 /* Concrete subclass of svalue representing the initial value of a
543 This represents the initial value at the start of the analysis path,
544 as opposed to the first time the region is accessed during the path.
545 Hence as soon as we have a call to an unknown function, all previously
546 unmodelled globals become implicitly "unknown" rathen than "initial". */
548 class initial_svalue
: public svalue
551 initial_svalue (tree type
, const region
*reg
)
552 : svalue (complexity (reg
), type
), m_reg (reg
)
554 gcc_assert (m_reg
!= NULL
);
557 enum svalue_kind
get_kind () const final override
{ return SK_INITIAL
; }
558 const initial_svalue
*
559 dyn_cast_initial_svalue () const final override
{ return this; }
561 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
562 void accept (visitor
*v
) const final override
;
563 bool implicitly_live_p (const svalue_set
*,
564 const region_model
*) const final override
;
566 bool initial_value_of_param_p () const;
568 const region
*get_region () const { return m_reg
; }
579 is_a_helper
<const initial_svalue
*>::test (const svalue
*sval
)
581 return sval
->get_kind () == SK_INITIAL
;
586 /* Concrete subclass of svalue representing a unary operation on
587 another svalues (e.g. a cast). */
589 class unaryop_svalue
: public svalue
592 /* A support class for uniquifying instances of unaryop_svalue. */
595 key_t (tree type
, enum tree_code op
, const svalue
*arg
)
596 : m_type (type
), m_op (op
), m_arg (arg
)
599 hashval_t
hash () const
601 inchash::hash hstate
;
602 hstate
.add_ptr (m_type
);
603 hstate
.add_int (m_op
);
604 hstate
.add_ptr (m_arg
);
605 return hstate
.end ();
608 bool operator== (const key_t
&other
) const
610 return (m_type
== other
.m_type
611 && m_op
== other
.m_op
612 && m_arg
== other
.m_arg
);
615 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
616 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
617 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
618 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
625 unaryop_svalue (tree type
, enum tree_code op
, const svalue
*arg
)
626 : svalue (complexity (arg
), type
), m_op (op
), m_arg (arg
)
628 gcc_assert (arg
->can_have_associated_state_p ());
631 enum svalue_kind
get_kind () const final override
{ return SK_UNARYOP
; }
632 const unaryop_svalue
*
633 dyn_cast_unaryop_svalue () const final override
{ return this; }
635 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
636 void accept (visitor
*v
) const final override
;
637 bool implicitly_live_p (const svalue_set
*,
638 const region_model
*) const final override
;
640 enum tree_code
get_op () const { return m_op
; }
641 const svalue
*get_arg () const { return m_arg
; }
644 maybe_fold_bits_within (tree type
,
645 const bit_range
&subrange
,
646 region_model_manager
*mgr
) const final override
;
658 is_a_helper
<const unaryop_svalue
*>::test (const svalue
*sval
)
660 return sval
->get_kind () == SK_UNARYOP
;
663 template <> struct default_hash_traits
<unaryop_svalue::key_t
>
664 : public member_function_hash_traits
<unaryop_svalue::key_t
>
666 static const bool empty_zero_p
= false;
671 /* Concrete subclass of svalue representing a binary operation of
674 class binop_svalue
: public svalue
677 /* A support class for uniquifying instances of binop_svalue. */
680 key_t (tree type
, enum tree_code op
,
681 const svalue
*arg0
, const svalue
*arg1
)
682 : m_type (type
), m_op (op
), m_arg0 (arg0
), m_arg1 (arg1
)
685 hashval_t
hash () const
687 inchash::hash hstate
;
688 hstate
.add_ptr (m_type
);
689 hstate
.add_int (m_op
);
690 hstate
.add_ptr (m_arg0
);
691 hstate
.add_ptr (m_arg1
);
692 return hstate
.end ();
695 bool operator== (const key_t
&other
) const
697 return (m_type
== other
.m_type
698 && m_op
== other
.m_op
699 && m_arg0
== other
.m_arg0
700 && m_arg1
== other
.m_arg1
);
703 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
704 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
705 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
706 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
710 const svalue
*m_arg0
;
711 const svalue
*m_arg1
;
714 binop_svalue (tree type
, enum tree_code op
,
715 const svalue
*arg0
, const svalue
*arg1
)
716 : svalue (complexity::from_pair (arg0
->get_complexity (),
717 arg1
->get_complexity ()),
719 m_op (op
), m_arg0 (arg0
), m_arg1 (arg1
)
721 gcc_assert (arg0
->can_have_associated_state_p ());
722 gcc_assert (arg1
->can_have_associated_state_p ());
725 enum svalue_kind
get_kind () const final override
{ return SK_BINOP
; }
726 const binop_svalue
*dyn_cast_binop_svalue () const final override
731 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
732 void accept (visitor
*v
) const final override
;
733 bool implicitly_live_p (const svalue_set
*,
734 const region_model
*) const final override
;
736 enum tree_code
get_op () const { return m_op
; }
737 const svalue
*get_arg0 () const { return m_arg0
; }
738 const svalue
*get_arg1 () const { return m_arg1
; }
742 const svalue
*m_arg0
;
743 const svalue
*m_arg1
;
751 is_a_helper
<const binop_svalue
*>::test (const svalue
*sval
)
753 return sval
->get_kind () == SK_BINOP
;
756 template <> struct default_hash_traits
<binop_svalue::key_t
>
757 : public member_function_hash_traits
<binop_svalue::key_t
>
759 static const bool empty_zero_p
= false;
764 /* Concrete subclass of svalue representing the result of accessing a subregion
765 of another svalue (the value of a component/field of a struct, or an element
768 class sub_svalue
: public svalue
771 /* A support class for uniquifying instances of sub_svalue. */
774 key_t (tree type
, const svalue
*parent_svalue
, const region
*subregion
)
775 : m_type (type
), m_parent_svalue (parent_svalue
), m_subregion (subregion
)
778 hashval_t
hash () const
780 inchash::hash hstate
;
781 hstate
.add_ptr (m_type
);
782 hstate
.add_ptr (m_parent_svalue
);
783 hstate
.add_ptr (m_subregion
);
784 return hstate
.end ();
787 bool operator== (const key_t
&other
) const
789 return (m_type
== other
.m_type
790 && m_parent_svalue
== other
.m_parent_svalue
791 && m_subregion
== other
.m_subregion
);
794 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
795 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
796 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
797 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
800 const svalue
*m_parent_svalue
;
801 const region
*m_subregion
;
803 sub_svalue (tree type
, const svalue
*parent_svalue
,
804 const region
*subregion
);
806 enum svalue_kind
get_kind () const final override
{ return SK_SUB
; }
807 const sub_svalue
*dyn_cast_sub_svalue () const final override
812 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
813 void accept (visitor
*v
) const final override
;
814 bool implicitly_live_p (const svalue_set
*,
815 const region_model
*) const final override
;
817 const svalue
*get_parent () const { return m_parent_svalue
; }
818 const region
*get_subregion () const { return m_subregion
; }
821 const svalue
*m_parent_svalue
;
822 const region
*m_subregion
;
830 is_a_helper
<const sub_svalue
*>::test (const svalue
*sval
)
832 return sval
->get_kind () == SK_SUB
;
835 template <> struct default_hash_traits
<sub_svalue::key_t
>
836 : public member_function_hash_traits
<sub_svalue::key_t
>
838 static const bool empty_zero_p
= false;
843 /* Concrete subclass of svalue representing repeating an inner svalue
844 (possibly not a whole number of times) to fill a larger region of
845 type TYPE of size OUTER_SIZE bytes. */
847 class repeated_svalue
: public svalue
850 /* A support class for uniquifying instances of repeated_svalue. */
854 const svalue
*outer_size
,
855 const svalue
*inner_svalue
)
856 : m_type (type
), m_outer_size (outer_size
), m_inner_svalue (inner_svalue
)
859 hashval_t
hash () const
861 inchash::hash hstate
;
862 hstate
.add_ptr (m_type
);
863 hstate
.add_ptr (m_outer_size
);
864 hstate
.add_ptr (m_inner_svalue
);
865 return hstate
.end ();
868 bool operator== (const key_t
&other
) const
870 return (m_type
== other
.m_type
871 && m_outer_size
== other
.m_outer_size
872 && m_inner_svalue
== other
.m_inner_svalue
);
875 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
876 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
877 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
878 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
881 const svalue
*m_outer_size
;
882 const svalue
*m_inner_svalue
;
884 repeated_svalue (tree type
,
885 const svalue
*outer_size
,
886 const svalue
*inner_svalue
);
888 enum svalue_kind
get_kind () const final override
{ return SK_REPEATED
; }
889 const repeated_svalue
*dyn_cast_repeated_svalue () const final override
894 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
895 void accept (visitor
*v
) const final override
;
897 const svalue
*get_outer_size () const { return m_outer_size
; }
898 const svalue
*get_inner_svalue () const { return m_inner_svalue
; }
900 bool all_zeroes_p () const final override
;
903 maybe_fold_bits_within (tree type
,
904 const bit_range
&subrange
,
905 region_model_manager
*mgr
) const final override
;
908 const svalue
*m_outer_size
;
909 const svalue
*m_inner_svalue
;
917 is_a_helper
<const repeated_svalue
*>::test (const svalue
*sval
)
919 return sval
->get_kind () == SK_REPEATED
;
922 template <> struct default_hash_traits
<repeated_svalue::key_t
>
923 : public member_function_hash_traits
<repeated_svalue::key_t
>
925 static const bool empty_zero_p
= false;
930 /* A range of bits/bytes within another svalue
931 e.g. bytes 5-39 of INITIAL_SVALUE(R).
932 These can be generated for prefixes and suffixes when part of a binding
933 is clobbered, so that we don't lose too much information. */
935 class bits_within_svalue
: public svalue
938 /* A support class for uniquifying instances of bits_within_svalue. */
942 const bit_range
&bits
,
943 const svalue
*inner_svalue
)
944 : m_type (type
), m_bits (bits
), m_inner_svalue (inner_svalue
)
947 hashval_t
hash () const
949 inchash::hash hstate
;
950 hstate
.add_ptr (m_type
);
951 hstate
.add_ptr (m_inner_svalue
);
952 return hstate
.end ();
955 bool operator== (const key_t
&other
) const
957 return (m_type
== other
.m_type
958 && m_bits
== other
.m_bits
959 && m_inner_svalue
== other
.m_inner_svalue
);
962 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
963 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
964 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
965 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
969 const svalue
*m_inner_svalue
;
971 bits_within_svalue (tree type
,
972 const bit_range
&bits
,
973 const svalue
*inner_svalue
);
975 enum svalue_kind
get_kind () const final override
{ return SK_BITS_WITHIN
; }
976 const bits_within_svalue
*
977 dyn_cast_bits_within_svalue () const final override
982 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
983 void accept (visitor
*v
) const final override
;
984 bool implicitly_live_p (const svalue_set
*,
985 const region_model
*) const final override
;
987 const bit_range
&get_bits () const { return m_bits
; }
988 const svalue
*get_inner_svalue () const { return m_inner_svalue
; }
991 maybe_fold_bits_within (tree type
,
992 const bit_range
&subrange
,
993 region_model_manager
*mgr
) const final override
;
996 const bit_range m_bits
;
997 const svalue
*m_inner_svalue
;
1005 is_a_helper
<const bits_within_svalue
*>::test (const svalue
*sval
)
1007 return sval
->get_kind () == SK_BITS_WITHIN
;
1010 template <> struct default_hash_traits
<bits_within_svalue::key_t
>
1011 : public member_function_hash_traits
<bits_within_svalue::key_t
>
1013 static const bool empty_zero_p
= false;
1018 /* Concrete subclass of svalue: decorate another svalue,
1019 so that the resulting svalue can be identified as being
1020 "interesting to control flow".
1021 For example, consider the return value from setjmp. We
1022 don't want to merge states in which the result is 0 with
1023 those in which the result is non-zero. By using an
1024 unmergeable_svalue for the result, we can inhibit such merges
1025 and have separate exploded nodes for those states, keeping
1026 the first and second returns from setjmp distinct in the exploded
1029 class unmergeable_svalue
: public svalue
1032 unmergeable_svalue (const svalue
*arg
)
1033 : svalue (complexity (arg
), arg
->get_type ()), m_arg (arg
)
1037 enum svalue_kind
get_kind () const final override
{ return SK_UNMERGEABLE
; }
1038 const unmergeable_svalue
*
1039 dyn_cast_unmergeable_svalue () const final override
{ return this; }
1041 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1042 void accept (visitor
*v
) const final override
;
1043 bool implicitly_live_p (const svalue_set
*,
1044 const region_model
*) const final override
;
1046 const svalue
*get_arg () const { return m_arg
; }
1049 const svalue
*m_arg
;
1057 is_a_helper
<const unmergeable_svalue
*>::test (const svalue
*sval
)
1059 return sval
->get_kind () == SK_UNMERGEABLE
;
1064 /* Concrete subclass of svalue for use in selftests, where
1065 we want a specific but unknown svalue.
1066 Unlike other svalue subclasses these aren't managed by
1067 region_model_manager. */
1069 class placeholder_svalue
: public svalue
1072 placeholder_svalue (tree type
, const char *name
)
1073 : svalue (complexity (1, 1), type
), m_name (name
)
1077 enum svalue_kind
get_kind () const final override
{ return SK_PLACEHOLDER
; }
1079 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1080 void accept (visitor
*v
) const final override
;
1082 const char *get_name () const { return m_name
; }
1093 is_a_helper
<const placeholder_svalue
*>::test (const svalue
*sval
)
1095 return sval
->get_kind () == SK_PLACEHOLDER
;
1100 /* Concrete subclass of svalue representing a "widening" seen when merging
1101 states, widening from a base value to {base value, iter value} and thus
1102 representing a possible fixed point in an iteration from the base to
1103 +ve infinity, or -ve infinity, and thus useful for representing a value
1105 We also need to capture the program_point at which the merger happens,
1106 so that distinguish between different iterators, and thus handle
1107 nested loops. (currently we capture the function_point instead, for
1108 simplicity of hashing). */
1110 class widening_svalue
: public svalue
1113 /* A support class for uniquifying instances of widening_svalue. */
1116 key_t (tree type
, const program_point
&point
,
1117 const svalue
*base_sval
, const svalue
*iter_sval
)
1118 : m_type (type
), m_point (point
.get_function_point ()),
1119 m_base_sval (base_sval
), m_iter_sval (iter_sval
)
1122 hashval_t
hash () const
1124 inchash::hash hstate
;
1125 hstate
.add_ptr (m_base_sval
);
1126 hstate
.add_ptr (m_iter_sval
);
1127 return hstate
.end ();
1130 bool operator== (const key_t
&other
) const
1132 return (m_type
== other
.m_type
1133 && m_point
== other
.m_point
1134 && m_base_sval
== other
.m_base_sval
1135 && m_iter_sval
== other
.m_iter_sval
);
1138 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
1139 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
1140 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
1141 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
1144 function_point m_point
;
1145 const svalue
*m_base_sval
;
1146 const svalue
*m_iter_sval
;
1156 widening_svalue (tree type
, const program_point
&point
,
1157 const svalue
*base_sval
, const svalue
*iter_sval
)
1158 : svalue (complexity::from_pair (base_sval
->get_complexity (),
1159 iter_sval
->get_complexity ()),
1161 m_point (point
.get_function_point ()),
1162 m_base_sval (base_sval
), m_iter_sval (iter_sval
)
1164 gcc_assert (base_sval
->can_have_associated_state_p ());
1165 gcc_assert (iter_sval
->can_have_associated_state_p ());
1168 enum svalue_kind
get_kind () const final override
{ return SK_WIDENING
; }
1169 const widening_svalue
*dyn_cast_widening_svalue () const final override
1174 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1175 void accept (visitor
*v
) const final override
;
1177 const function_point
&get_point () const { return m_point
; }
1178 const svalue
*get_base_svalue () const { return m_base_sval
; }
1179 const svalue
*get_iter_svalue () const { return m_iter_sval
; }
1181 enum direction_t
get_direction () const;
1183 tristate
eval_condition_without_cm (enum tree_code op
,
1184 tree rhs_cst
) const;
1187 function_point m_point
;
1188 const svalue
*m_base_sval
;
1189 const svalue
*m_iter_sval
;
1197 is_a_helper
<const widening_svalue
*>::test (const svalue
*sval
)
1199 return sval
->get_kind () == SK_WIDENING
;
1202 template <> struct default_hash_traits
<widening_svalue::key_t
>
1203 : public member_function_hash_traits
<widening_svalue::key_t
>
1205 static const bool empty_zero_p
= false;
1210 /* Concrete subclass of svalue representing a mapping of bit-ranges
1211 to svalues, analogous to a cluster within the store.
1213 This is for use in places where we want to represent a store-like
1214 mapping, but are required to use an svalue, such as when handling
1215 compound assignments and compound return values.
1217 All keys within the underlying binding_map are required to be concrete,
1220 Instances of this class shouldn't be bound as-is into the store;
1221 instead they should be unpacked. Similarly, they should not be
1224 class compound_svalue
: public svalue
1227 typedef binding_map::iterator_t iterator_t
;
1229 /* A support class for uniquifying instances of compound_svalue.
1230 Note that to avoid copies, keys store pointers to binding_maps,
1231 rather than the maps themselves. */
1234 key_t (tree type
, const binding_map
*map_ptr
)
1235 : m_type (type
), m_map_ptr (map_ptr
)
1238 hashval_t
hash () const
1240 inchash::hash hstate
;
1241 hstate
.add_ptr (m_type
);
1242 //hstate.add_ptr (m_map_ptr); // TODO
1243 return hstate
.end ();
1246 bool operator== (const key_t
&other
) const
1248 return (m_type
== other
.m_type
1249 && *m_map_ptr
== *other
.m_map_ptr
);
1252 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
1253 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
1254 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
1255 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
1258 const binding_map
*m_map_ptr
;
1261 compound_svalue (tree type
, const binding_map
&map
);
1263 enum svalue_kind
get_kind () const final override
{ return SK_COMPOUND
; }
1264 const compound_svalue
*dyn_cast_compound_svalue () const final override
1269 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1270 void accept (visitor
*v
) const final override
;
1272 const binding_map
&get_map () const { return m_map
; }
1274 iterator_t
begin () const { return m_map
.begin (); }
1275 iterator_t
end () const { return m_map
.end (); }
1277 struct key_t
make_key () const
1279 return key_t (get_type (), &m_map
);
1283 maybe_fold_bits_within (tree type
,
1284 const bit_range
&subrange
,
1285 region_model_manager
*mgr
) const final override
;
1288 static complexity
calc_complexity (const binding_map
&map
);
1298 is_a_helper
<const compound_svalue
*>::test (const svalue
*sval
)
1300 return sval
->get_kind () == SK_COMPOUND
;
1303 template <> struct default_hash_traits
<compound_svalue::key_t
>
1304 : public member_function_hash_traits
<compound_svalue::key_t
>
1306 static const bool empty_zero_p
= false;
1311 /* A bundle of state for purging information from a program_state about
1312 a conjured_svalue. We pass this whenever calling
1313 get_or_create_conjured_svalue, so that if the program_state already
1314 has information about this conjured_svalue on an execution path, we
1315 can purge that information, to avoid the analyzer confusing the two
1316 values as being the same. */
1318 class conjured_purge
1321 conjured_purge (region_model
*model
, region_model_context
*ctxt
)
1322 : m_model (model
), m_ctxt (ctxt
)
1325 void purge (const conjured_svalue
*sval
) const;
1328 region_model
*m_model
;
1329 region_model_context
*m_ctxt
;
1332 /* A defined value arising from a statement, where we want to identify a
1333 particular unknown value, rather than resorting to the unknown_value
1334 singleton, so that the value can have sm-state.
1336 Comparisons of variables that share the same conjured_svalue are known
1337 to be equal, even if we don't know what the value is.
1339 For example, this is used for the values of regions that may have been
1340 touched when calling an unknown function.
1342 The value captures a region as well as a stmt in order to avoid falsely
1343 aliasing the various values that could arise in one statement. For
1345 unknown_fn (&a, &b);
1346 we want values to clobber a and b with, but we don't want to use the
1347 same value, or it would falsely implicitly assume that a == b. */
1349 class conjured_svalue
: public svalue
1352 /* A support class for uniquifying instances of conjured_svalue. */
1355 key_t (tree type
, const gimple
*stmt
, const region
*id_reg
)
1356 : m_type (type
), m_stmt (stmt
), m_id_reg (id_reg
)
1359 hashval_t
hash () const
1361 inchash::hash hstate
;
1362 hstate
.add_ptr (m_type
);
1363 hstate
.add_ptr (m_stmt
);
1364 hstate
.add_ptr (m_id_reg
);
1365 return hstate
.end ();
1368 bool operator== (const key_t
&other
) const
1370 return (m_type
== other
.m_type
1371 && m_stmt
== other
.m_stmt
1372 && m_id_reg
== other
.m_id_reg
);
1375 /* Use m_stmt to mark empty/deleted, as m_type can be NULL for
1376 legitimate instances. */
1377 void mark_deleted () { m_stmt
= reinterpret_cast<const gimple
*> (1); }
1378 void mark_empty () { m_stmt
= NULL
; }
1379 bool is_deleted () const
1381 return m_stmt
== reinterpret_cast<const gimple
*> (1);
1383 bool is_empty () const { return m_stmt
== NULL
; }
1386 const gimple
*m_stmt
;
1387 const region
*m_id_reg
;
1390 conjured_svalue (tree type
, const gimple
*stmt
, const region
*id_reg
)
1391 : svalue (complexity (id_reg
), type
),
1392 m_stmt (stmt
), m_id_reg (id_reg
)
1394 gcc_assert (m_stmt
!= NULL
);
1397 enum svalue_kind
get_kind () const final override
{ return SK_CONJURED
; }
1398 const conjured_svalue
*dyn_cast_conjured_svalue () const final override
1403 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1404 void accept (visitor
*v
) const final override
;
1406 const gimple
*get_stmt () const { return m_stmt
; }
1407 const region
*get_id_region () const { return m_id_reg
; }
1410 const gimple
*m_stmt
;
1411 const region
*m_id_reg
;
1419 is_a_helper
<const conjured_svalue
*>::test (const svalue
*sval
)
1421 return sval
->get_kind () == SK_CONJURED
;
1424 template <> struct default_hash_traits
<conjured_svalue::key_t
>
1425 : public member_function_hash_traits
<conjured_svalue::key_t
>
1427 static const bool empty_zero_p
= true;
1432 /* An output from a deterministic asm stmt, where we want to identify a
1433 particular unknown value, rather than resorting to the unknown_value
1436 Comparisons of variables that share the same asm_output_svalue are known
1437 to be equal, even if we don't know what the value is. */
1439 class asm_output_svalue
: public svalue
1442 /* Imposing an upper limit and using a (small) array allows key_t
1443 to avoid memory management. */
1444 static const unsigned MAX_INPUTS
= 2;
1446 /* A support class for uniquifying instances of asm_output_svalue. */
1450 const char *asm_string
,
1451 unsigned output_idx
,
1452 const vec
<const svalue
*> &inputs
)
1453 : m_type (type
), m_asm_string (asm_string
), m_output_idx (output_idx
),
1454 m_num_inputs (inputs
.length ())
1456 gcc_assert (inputs
.length () <= MAX_INPUTS
);
1457 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1458 m_input_arr
[i
] = inputs
[i
];
1461 hashval_t
hash () const
1463 inchash::hash hstate
;
1464 hstate
.add_ptr (m_type
);
1465 /* We don't bother hashing m_asm_str. */
1466 hstate
.add_int (m_output_idx
);
1467 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1468 hstate
.add_ptr (m_input_arr
[i
]);
1469 return hstate
.end ();
1472 bool operator== (const key_t
&other
) const
1474 if (!(m_type
== other
.m_type
1475 && 0 == (strcmp (m_asm_string
, other
.m_asm_string
))
1476 && m_output_idx
== other
.m_output_idx
1477 && m_num_inputs
== other
.m_num_inputs
))
1479 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1480 if (m_input_arr
[i
] != other
.m_input_arr
[i
])
1485 /* Use m_asm_string to mark empty/deleted, as m_type can be NULL for
1486 legitimate instances. */
1487 void mark_deleted () { m_asm_string
= reinterpret_cast<const char *> (1); }
1488 void mark_empty () { m_asm_string
= NULL
; }
1489 bool is_deleted () const
1491 return m_asm_string
== reinterpret_cast<const char *> (1);
1493 bool is_empty () const { return m_asm_string
== NULL
; }
1496 const char *m_asm_string
;
1497 unsigned m_output_idx
;
1498 unsigned m_num_inputs
;
1499 const svalue
*m_input_arr
[MAX_INPUTS
];
1502 asm_output_svalue (tree type
,
1503 const char *asm_string
,
1504 unsigned output_idx
,
1505 unsigned num_outputs
,
1506 const vec
<const svalue
*> &inputs
)
1507 : svalue (complexity::from_vec_svalue (inputs
), type
),
1508 m_asm_string (asm_string
),
1509 m_output_idx (output_idx
),
1510 m_num_outputs (num_outputs
),
1511 m_num_inputs (inputs
.length ())
1513 gcc_assert (inputs
.length () <= MAX_INPUTS
);
1514 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1515 m_input_arr
[i
] = inputs
[i
];
1518 enum svalue_kind
get_kind () const final override
{ return SK_ASM_OUTPUT
; }
1519 const asm_output_svalue
*
1520 dyn_cast_asm_output_svalue () const final override
1525 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1526 void accept (visitor
*v
) const final override
;
1528 const char *get_asm_string () const { return m_asm_string
; }
1529 unsigned get_output_idx () const { return m_output_idx
; }
1530 unsigned get_num_inputs () const { return m_num_inputs
; }
1531 const svalue
*get_input (unsigned idx
) const { return m_input_arr
[idx
]; }
1534 void dump_input (pretty_printer
*pp
,
1538 unsigned input_idx_to_asm_idx (unsigned input_idx
) const;
1540 const char *m_asm_string
;
1541 unsigned m_output_idx
;
1543 /* We capture this so that we can offset the input indices
1544 to match the %0, %1, %2 in the asm_string when dumping. */
1545 unsigned m_num_outputs
;
1547 unsigned m_num_inputs
;
1548 const svalue
*m_input_arr
[MAX_INPUTS
];
1556 is_a_helper
<const asm_output_svalue
*>::test (const svalue
*sval
)
1558 return sval
->get_kind () == SK_ASM_OUTPUT
;
1561 template <> struct default_hash_traits
<asm_output_svalue::key_t
>
1562 : public member_function_hash_traits
<asm_output_svalue::key_t
>
1564 static const bool empty_zero_p
= true;
1569 /* The return value from a function with __attribute((const)) for given
1570 inputs, provided that we don't have too many inputs, and all of them
1573 Comparisons of variables that share the same const_fn_result_svalue are known
1574 to be equal, even if we don't know what the value is. */
1576 class const_fn_result_svalue
: public svalue
1579 /* Imposing an upper limit and using a (small) array allows key_t
1580 to avoid memory management. */
1581 static const unsigned MAX_INPUTS
= 2;
1583 /* A support class for uniquifying instances of const_fn_result_svalue. */
1588 const vec
<const svalue
*> &inputs
)
1589 : m_type (type
), m_fndecl (fndecl
),
1590 m_num_inputs (inputs
.length ())
1592 gcc_assert (inputs
.length () <= MAX_INPUTS
);
1593 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1594 m_input_arr
[i
] = inputs
[i
];
1597 hashval_t
hash () const
1599 inchash::hash hstate
;
1600 hstate
.add_ptr (m_type
);
1601 hstate
.add_ptr (m_fndecl
);
1602 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1603 hstate
.add_ptr (m_input_arr
[i
]);
1604 return hstate
.end ();
1607 bool operator== (const key_t
&other
) const
1609 if (!(m_type
== other
.m_type
1610 && m_fndecl
== other
.m_fndecl
1611 && m_num_inputs
== other
.m_num_inputs
))
1613 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1614 if (m_input_arr
[i
] != other
.m_input_arr
[i
])
1619 /* Use m_fndecl to mark empty/deleted. */
1620 void mark_deleted () { m_fndecl
= reinterpret_cast<tree
> (1); }
1621 void mark_empty () { m_fndecl
= NULL
; }
1622 bool is_deleted () const
1624 return m_fndecl
== reinterpret_cast<tree
> (1);
1626 bool is_empty () const { return m_fndecl
== NULL
; }
1630 unsigned m_num_inputs
;
1631 const svalue
*m_input_arr
[MAX_INPUTS
];
1634 const_fn_result_svalue (tree type
,
1636 const vec
<const svalue
*> &inputs
)
1637 : svalue (complexity::from_vec_svalue (inputs
), type
),
1639 m_num_inputs (inputs
.length ())
1641 gcc_assert (inputs
.length () <= MAX_INPUTS
);
1642 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1643 m_input_arr
[i
] = inputs
[i
];
1646 enum svalue_kind
get_kind () const final override
1648 return SK_CONST_FN_RESULT
;
1650 const const_fn_result_svalue
*
1651 dyn_cast_const_fn_result_svalue () const final override
1656 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1657 void accept (visitor
*v
) const final override
;
1659 tree
get_fndecl () const { return m_fndecl
; }
1660 unsigned get_num_inputs () const { return m_num_inputs
; }
1661 const svalue
*get_input (unsigned idx
) const { return m_input_arr
[idx
]; }
1664 void dump_input (pretty_printer
*pp
,
1670 unsigned m_num_inputs
;
1671 const svalue
*m_input_arr
[MAX_INPUTS
];
1679 is_a_helper
<const const_fn_result_svalue
*>::test (const svalue
*sval
)
1681 return sval
->get_kind () == SK_CONST_FN_RESULT
;
1684 template <> struct default_hash_traits
<const_fn_result_svalue::key_t
>
1685 : public member_function_hash_traits
<const_fn_result_svalue::key_t
>
1687 static const bool empty_zero_p
= true;
1690 #endif /* GCC_ANALYZER_SVALUE_H */