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"
25 #include "analyzer/store.h"
26 #include "analyzer/program-point.h"
32 /* An enum for discriminating between the different concrete subclasses
57 /* svalue and its subclasses.
59 The class hierarchy looks like this (using indentation to show
60 inheritance, and with svalue_kinds shown for the concrete subclasses):
63 region_svalue (SK_REGION): a pointer to a region
64 constant_svalue (SK_CONSTANT): a constant
65 unknown_svalue (SK_UNKNOWN): an unknowable value
66 poisoned_svalue (SK_POISONED): a unusable value (undefined)
67 setjmp_svalue (SK_SETJMP): a setjmp/longjmp buffer
68 initial_svalue (SK_INITIAL): the initial value of a region
69 unaryop_svalue (SK_UNARYOP): unary operation on another svalue
70 binop_svalue (SK_BINOP): binary operation on two svalues
71 sub_svalue (SK_SUB): the result of accessing a subregion
72 repeated_svalue (SK_REPEATED): repeating an svalue to fill a larger region
73 bits_within_svalue (SK_BITS_WITHIN): a range of bits/bytes within a larger
75 unmergeable_svalue (SK_UNMERGEABLE): a value that is so interesting
76 from a control-flow perspective that it can inhibit state-merging
77 placeholder_svalue (SK_PLACEHOLDER): for use in selftests.
78 widening_svalue (SK_WIDENING): a merger of two svalues (possibly
80 compound_svalue (SK_COMPOUND): a mapping of bit-ranges to svalues
81 conjured_svalue (SK_CONJURED): a value arising from a stmt
82 asm_output_svalue (SK_ASM_OUTPUT): an output from a deterministic
84 const_fn_result_svalue (SK_CONST_FN_RESULT): the return value from
85 a function with __attribute((const)) for given inputs. */
87 /* An abstract base class representing a value held by a region of memory. */
94 tree
get_type () const { return m_type
; }
96 virtual enum svalue_kind
get_kind () const = 0;
98 void print (const region_model
&model
,
99 pretty_printer
*pp
) const;
101 virtual void dump_to_pp (pretty_printer
*pp
, bool simple
) const = 0;
102 void dump (bool simple
=true) const;
103 label_text
get_desc (bool simple
=true) const;
105 json::value
*to_json () const;
107 virtual const region_svalue
*
108 dyn_cast_region_svalue () const { return NULL
; }
109 virtual const constant_svalue
*
110 dyn_cast_constant_svalue () const { return NULL
; }
111 virtual const poisoned_svalue
*
112 dyn_cast_poisoned_svalue () const { return NULL
; }
113 virtual const setjmp_svalue
*
114 dyn_cast_setjmp_svalue () const { return NULL
; }
115 virtual const initial_svalue
*
116 dyn_cast_initial_svalue () const { return NULL
; }
117 virtual const unaryop_svalue
*
118 dyn_cast_unaryop_svalue () const { return NULL
; }
119 virtual const binop_svalue
*
120 dyn_cast_binop_svalue () const { return NULL
; }
121 virtual const sub_svalue
*
122 dyn_cast_sub_svalue () const { return NULL
; }
123 virtual const repeated_svalue
*
124 dyn_cast_repeated_svalue () const { return NULL
; }
125 virtual const bits_within_svalue
*
126 dyn_cast_bits_within_svalue () const { return NULL
; }
127 virtual const unmergeable_svalue
*
128 dyn_cast_unmergeable_svalue () const { return NULL
; }
129 virtual const widening_svalue
*
130 dyn_cast_widening_svalue () const { return NULL
; }
131 virtual const compound_svalue
*
132 dyn_cast_compound_svalue () const { return NULL
; }
133 virtual const conjured_svalue
*
134 dyn_cast_conjured_svalue () const { return NULL
; }
135 virtual const asm_output_svalue
*
136 dyn_cast_asm_output_svalue () const { return NULL
; }
137 virtual const const_fn_result_svalue
*
138 dyn_cast_const_fn_result_svalue () const { return NULL
; }
140 tree
maybe_get_constant () const;
141 const region
*maybe_get_region () const;
142 const svalue
*maybe_undo_cast () const;
143 const svalue
*unwrap_any_unmergeable () const;
145 const svalue
*can_merge_p (const svalue
*other
,
146 region_model_manager
*mgr
,
147 model_merger
*merger
) const;
149 const complexity
&get_complexity () const { return m_complexity
; }
151 virtual void accept (visitor
*v
) const = 0;
153 bool live_p (const svalue_set
*live_svalues
,
154 const region_model
*model
) const;
155 virtual bool implicitly_live_p (const svalue_set
*live_svalues
,
156 const region_model
*model
) const;
158 static int cmp_ptr (const svalue
*, const svalue
*);
159 static int cmp_ptr_ptr (const void *, const void *);
161 bool involves_p (const svalue
*other
) const;
164 extract_bit_range (tree type
,
165 const bit_range
&subrange
,
166 region_model_manager
*mgr
) const;
168 virtual const svalue
*
169 maybe_fold_bits_within (tree type
,
170 const bit_range
&subrange
,
171 region_model_manager
*mgr
) const;
173 virtual bool all_zeroes_p () const;
175 /* Can this svalue be involved in constraints and sm-state?
176 Most can, but UNKNOWN and POISONED svalues are singletons
177 per-type and thus it's meaningless for them to "have state". */
178 virtual bool can_have_associated_state_p () const { return true; }
180 const region
*maybe_get_deref_base_region () const;
183 svalue (complexity c
, tree type
)
184 : m_complexity (c
), m_type (type
)
188 complexity m_complexity
;
192 /* Concrete subclass of svalue representing a pointer value that points to
195 class region_svalue
: public svalue
198 /* A support class for uniquifying instances of region_svalue. */
201 key_t (tree type
, const region
*reg
)
202 : m_type (type
), m_reg (reg
)
205 hashval_t
hash () const
207 inchash::hash hstate
;
208 hstate
.add_ptr (m_type
);
209 hstate
.add_ptr (m_reg
);
210 return hstate
.end ();
213 bool operator== (const key_t
&other
) const
215 return (m_type
== other
.m_type
&& m_reg
== other
.m_reg
);
218 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
219 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
220 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
221 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
227 region_svalue (tree type
, const region
*reg
)
228 : svalue (complexity (reg
), type
),
231 gcc_assert (m_reg
!= NULL
);
234 enum svalue_kind
get_kind () const final override
{ return SK_REGION
; }
235 const region_svalue
*
236 dyn_cast_region_svalue () const final override
{ return this; }
238 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
239 void accept (visitor
*v
) const final override
;
240 bool implicitly_live_p (const svalue_set
*,
241 const region_model
*) const final override
;
243 const region
* get_pointee () const { return m_reg
; }
245 static tristate
eval_condition (const region_svalue
*lhs_ptr
,
247 const region_svalue
*rhs_ptr
);
258 is_a_helper
<const region_svalue
*>::test (const svalue
*sval
)
260 return sval
->get_kind () == SK_REGION
;
263 template <> struct default_hash_traits
<region_svalue::key_t
>
264 : public member_function_hash_traits
<region_svalue::key_t
>
266 static const bool empty_zero_p
= false;
271 /* Concrete subclass of svalue representing a specific constant value. */
273 class constant_svalue
: public svalue
276 constant_svalue (tree cst_expr
)
277 : svalue (complexity (1, 1), TREE_TYPE (cst_expr
)), m_cst_expr (cst_expr
)
279 gcc_assert (cst_expr
);
280 gcc_assert (CONSTANT_CLASS_P (cst_expr
));
283 enum svalue_kind
get_kind () const final override
{ return SK_CONSTANT
; }
284 const constant_svalue
*
285 dyn_cast_constant_svalue () const final override
{ return this; }
287 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
288 void accept (visitor
*v
) const final override
;
289 bool implicitly_live_p (const svalue_set
*,
290 const region_model
*) const final override
;
292 tree
get_constant () const { return m_cst_expr
; }
293 static tristate
eval_condition (const constant_svalue
*lhs
,
295 const constant_svalue
*rhs
);
298 maybe_fold_bits_within (tree type
,
299 const bit_range
&subrange
,
300 region_model_manager
*mgr
) const final override
;
302 bool all_zeroes_p () const final override
;
313 is_a_helper
<const constant_svalue
*>::test (const svalue
*sval
)
315 return sval
->get_kind () == SK_CONSTANT
;
320 /* Concrete subclass of svalue representing an unknowable value, the bottom
321 value when thinking of svalues as a lattice.
322 This is a singleton (w.r.t. its manager): there is a single unknown_svalue
323 per type. Self-comparisons of such instances yield "unknown". */
325 class unknown_svalue
: public svalue
328 unknown_svalue (tree type
)
329 : svalue (complexity (1, 1), type
)
332 enum svalue_kind
get_kind () const final override
{ return SK_UNKNOWN
; }
334 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
335 void accept (visitor
*v
) const final override
;
338 maybe_fold_bits_within (tree type
,
339 const bit_range
&subrange
,
340 region_model_manager
*mgr
) const final override
;
342 /* Unknown values are singletons per-type, so can't have state. */
343 bool can_have_associated_state_p () const final override
{ return false; }
346 /* An enum describing a particular kind of "poisoned" value. */
350 /* For use to describe uninitialized memory. */
353 /* For use to describe freed memory. */
356 /* For use on pointers to regions within popped stack frames. */
357 POISON_KIND_POPPED_STACK
360 extern const char *poison_kind_to_str (enum poison_kind
);
362 /* Concrete subclass of svalue representing a value that should not
363 be used (e.g. uninitialized memory, freed memory). */
365 class poisoned_svalue
: public svalue
368 /* A support class for uniquifying instances of poisoned_svalue. */
371 key_t (enum poison_kind kind
, tree type
)
372 : m_kind (kind
), m_type (type
)
375 hashval_t
hash () const
377 inchash::hash hstate
;
378 hstate
.add_int (m_kind
);
379 hstate
.add_ptr (m_type
);
380 return hstate
.end ();
383 bool operator== (const key_t
&other
) const
385 return (m_kind
== other
.m_kind
&& m_type
== other
.m_type
);
388 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
389 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
390 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
391 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
393 enum poison_kind m_kind
;
397 poisoned_svalue (enum poison_kind kind
, tree type
)
398 : svalue (complexity (1, 1), type
), m_kind (kind
) {}
400 enum svalue_kind
get_kind () const final override
{ return SK_POISONED
; }
401 const poisoned_svalue
*
402 dyn_cast_poisoned_svalue () const final override
{ return this; }
404 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
405 void accept (visitor
*v
) const final override
;
408 maybe_fold_bits_within (tree type
,
409 const bit_range
&subrange
,
410 region_model_manager
*mgr
) const final override
;
412 enum poison_kind
get_poison_kind () const { return m_kind
; }
414 /* Poisoned svalues are singletons per-type, so can't have state. */
415 bool can_have_associated_state_p () const final override
{ return false; }
418 enum poison_kind m_kind
;
426 is_a_helper
<const poisoned_svalue
*>::test (const svalue
*sval
)
428 return sval
->get_kind () == SK_POISONED
;
431 template <> struct default_hash_traits
<poisoned_svalue::key_t
>
432 : public member_function_hash_traits
<poisoned_svalue::key_t
>
434 static const bool empty_zero_p
= false;
439 /* A bundle of information recording a setjmp/sigsetjmp call, corresponding
440 roughly to a jmp_buf. */
444 setjmp_record (const exploded_node
*enode
,
445 const gcall
*setjmp_call
)
446 : m_enode (enode
), m_setjmp_call (setjmp_call
)
450 bool operator== (const setjmp_record
&other
) const
452 return (m_enode
== other
.m_enode
453 && m_setjmp_call
== other
.m_setjmp_call
);
456 void add_to_hash (inchash::hash
*hstate
) const
458 hstate
->add_ptr (m_enode
);
459 hstate
->add_ptr (m_setjmp_call
);
462 static int cmp (const setjmp_record
&rec1
, const setjmp_record
&rec2
);
464 const exploded_node
*m_enode
;
465 const gcall
*m_setjmp_call
;
468 /* Concrete subclass of svalue representing buffers for setjmp/sigsetjmp,
469 so that longjmp/siglongjmp can potentially "return" to an entirely
470 different function. */
472 class setjmp_svalue
: public svalue
475 /* A support class for uniquifying instances of poisoned_svalue. */
478 key_t (const setjmp_record
&record
, tree type
)
479 : m_record (record
), m_type (type
)
482 hashval_t
hash () const
484 inchash::hash hstate
;
485 m_record
.add_to_hash (&hstate
);
486 hstate
.add_ptr (m_type
);
487 return hstate
.end ();
490 bool operator== (const key_t
&other
) const
492 return (m_record
== other
.m_record
&& m_type
== other
.m_type
);
495 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
496 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
497 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
498 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
500 setjmp_record m_record
;
504 setjmp_svalue (const setjmp_record
&setjmp_record
,
506 : svalue (complexity (1, 1), type
), m_setjmp_record (setjmp_record
)
509 enum svalue_kind
get_kind () const final override
{ return SK_SETJMP
; }
510 const setjmp_svalue
*
511 dyn_cast_setjmp_svalue () const final override
{ return this; }
513 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
514 void accept (visitor
*v
) const final override
;
516 int get_enode_index () const;
518 const setjmp_record
&get_setjmp_record () const { return m_setjmp_record
; }
521 setjmp_record m_setjmp_record
;
529 is_a_helper
<const setjmp_svalue
*>::test (const svalue
*sval
)
531 return sval
->get_kind () == SK_SETJMP
;
534 template <> struct default_hash_traits
<setjmp_svalue::key_t
>
535 : public member_function_hash_traits
<setjmp_svalue::key_t
>
537 static const bool empty_zero_p
= false;
542 /* Concrete subclass of svalue representing the initial value of a
545 This represents the initial value at the start of the analysis path,
546 as opposed to the first time the region is accessed during the path.
547 Hence as soon as we have a call to an unknown function, all previously
548 unmodelled globals become implicitly "unknown" rathen than "initial". */
550 class initial_svalue
: public svalue
553 initial_svalue (tree type
, const region
*reg
)
554 : svalue (complexity (reg
), type
), m_reg (reg
)
556 gcc_assert (m_reg
!= NULL
);
559 enum svalue_kind
get_kind () const final override
{ return SK_INITIAL
; }
560 const initial_svalue
*
561 dyn_cast_initial_svalue () const final override
{ return this; }
563 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
564 void accept (visitor
*v
) const final override
;
565 bool implicitly_live_p (const svalue_set
*,
566 const region_model
*) const final override
;
568 bool initial_value_of_param_p () const;
570 const region
*get_region () const { return m_reg
; }
581 is_a_helper
<const initial_svalue
*>::test (const svalue
*sval
)
583 return sval
->get_kind () == SK_INITIAL
;
588 /* Concrete subclass of svalue representing a unary operation on
589 another svalues (e.g. a cast). */
591 class unaryop_svalue
: public svalue
594 /* A support class for uniquifying instances of unaryop_svalue. */
597 key_t (tree type
, enum tree_code op
, const svalue
*arg
)
598 : m_type (type
), m_op (op
), m_arg (arg
)
601 hashval_t
hash () const
603 inchash::hash hstate
;
604 hstate
.add_ptr (m_type
);
605 hstate
.add_int (m_op
);
606 hstate
.add_ptr (m_arg
);
607 return hstate
.end ();
610 bool operator== (const key_t
&other
) const
612 return (m_type
== other
.m_type
613 && m_op
== other
.m_op
614 && m_arg
== other
.m_arg
);
617 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
618 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
619 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
620 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
627 unaryop_svalue (tree type
, enum tree_code op
, const svalue
*arg
)
628 : svalue (complexity (arg
), type
), m_op (op
), m_arg (arg
)
630 gcc_assert (arg
->can_have_associated_state_p ());
633 enum svalue_kind
get_kind () const final override
{ return SK_UNARYOP
; }
634 const unaryop_svalue
*
635 dyn_cast_unaryop_svalue () const final override
{ return this; }
637 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
638 void accept (visitor
*v
) const final override
;
639 bool implicitly_live_p (const svalue_set
*,
640 const region_model
*) const final override
;
642 enum tree_code
get_op () const { return m_op
; }
643 const svalue
*get_arg () const { return m_arg
; }
646 maybe_fold_bits_within (tree type
,
647 const bit_range
&subrange
,
648 region_model_manager
*mgr
) const final override
;
660 is_a_helper
<const unaryop_svalue
*>::test (const svalue
*sval
)
662 return sval
->get_kind () == SK_UNARYOP
;
665 template <> struct default_hash_traits
<unaryop_svalue::key_t
>
666 : public member_function_hash_traits
<unaryop_svalue::key_t
>
668 static const bool empty_zero_p
= false;
673 /* Concrete subclass of svalue representing a binary operation of
676 class binop_svalue
: public svalue
679 /* A support class for uniquifying instances of binop_svalue. */
682 key_t (tree type
, enum tree_code op
,
683 const svalue
*arg0
, const svalue
*arg1
)
684 : m_type (type
), m_op (op
), m_arg0 (arg0
), m_arg1 (arg1
)
687 hashval_t
hash () const
689 inchash::hash hstate
;
690 hstate
.add_ptr (m_type
);
691 hstate
.add_int (m_op
);
692 hstate
.add_ptr (m_arg0
);
693 hstate
.add_ptr (m_arg1
);
694 return hstate
.end ();
697 bool operator== (const key_t
&other
) const
699 return (m_type
== other
.m_type
700 && m_op
== other
.m_op
701 && m_arg0
== other
.m_arg0
702 && m_arg1
== other
.m_arg1
);
705 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
706 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
707 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
708 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
712 const svalue
*m_arg0
;
713 const svalue
*m_arg1
;
716 binop_svalue (tree type
, enum tree_code op
,
717 const svalue
*arg0
, const svalue
*arg1
)
718 : svalue (complexity::from_pair (arg0
->get_complexity (),
719 arg1
->get_complexity ()),
721 m_op (op
), m_arg0 (arg0
), m_arg1 (arg1
)
723 gcc_assert (arg0
->can_have_associated_state_p ());
724 gcc_assert (arg1
->can_have_associated_state_p ());
727 enum svalue_kind
get_kind () const final override
{ return SK_BINOP
; }
728 const binop_svalue
*dyn_cast_binop_svalue () const final override
733 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
734 void accept (visitor
*v
) const final override
;
735 bool implicitly_live_p (const svalue_set
*,
736 const region_model
*) const final override
;
738 enum tree_code
get_op () const { return m_op
; }
739 const svalue
*get_arg0 () const { return m_arg0
; }
740 const svalue
*get_arg1 () const { return m_arg1
; }
744 const svalue
*m_arg0
;
745 const svalue
*m_arg1
;
753 is_a_helper
<const binop_svalue
*>::test (const svalue
*sval
)
755 return sval
->get_kind () == SK_BINOP
;
758 template <> struct default_hash_traits
<binop_svalue::key_t
>
759 : public member_function_hash_traits
<binop_svalue::key_t
>
761 static const bool empty_zero_p
= false;
766 /* Concrete subclass of svalue representing the result of accessing a subregion
767 of another svalue (the value of a component/field of a struct, or an element
770 class sub_svalue
: public svalue
773 /* A support class for uniquifying instances of sub_svalue. */
776 key_t (tree type
, const svalue
*parent_svalue
, const region
*subregion
)
777 : m_type (type
), m_parent_svalue (parent_svalue
), m_subregion (subregion
)
780 hashval_t
hash () const
782 inchash::hash hstate
;
783 hstate
.add_ptr (m_type
);
784 hstate
.add_ptr (m_parent_svalue
);
785 hstate
.add_ptr (m_subregion
);
786 return hstate
.end ();
789 bool operator== (const key_t
&other
) const
791 return (m_type
== other
.m_type
792 && m_parent_svalue
== other
.m_parent_svalue
793 && m_subregion
== other
.m_subregion
);
796 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
797 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
798 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
799 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
802 const svalue
*m_parent_svalue
;
803 const region
*m_subregion
;
805 sub_svalue (tree type
, const svalue
*parent_svalue
,
806 const region
*subregion
);
808 enum svalue_kind
get_kind () const final override
{ return SK_SUB
; }
809 const sub_svalue
*dyn_cast_sub_svalue () const final override
814 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
815 void accept (visitor
*v
) const final override
;
816 bool implicitly_live_p (const svalue_set
*,
817 const region_model
*) const final override
;
819 const svalue
*get_parent () const { return m_parent_svalue
; }
820 const region
*get_subregion () const { return m_subregion
; }
823 const svalue
*m_parent_svalue
;
824 const region
*m_subregion
;
832 is_a_helper
<const sub_svalue
*>::test (const svalue
*sval
)
834 return sval
->get_kind () == SK_SUB
;
837 template <> struct default_hash_traits
<sub_svalue::key_t
>
838 : public member_function_hash_traits
<sub_svalue::key_t
>
840 static const bool empty_zero_p
= false;
845 /* Concrete subclass of svalue representing repeating an inner svalue
846 (possibly not a whole number of times) to fill a larger region of
847 type TYPE of size OUTER_SIZE bytes. */
849 class repeated_svalue
: public svalue
852 /* A support class for uniquifying instances of repeated_svalue. */
856 const svalue
*outer_size
,
857 const svalue
*inner_svalue
)
858 : m_type (type
), m_outer_size (outer_size
), m_inner_svalue (inner_svalue
)
861 hashval_t
hash () const
863 inchash::hash hstate
;
864 hstate
.add_ptr (m_type
);
865 hstate
.add_ptr (m_outer_size
);
866 hstate
.add_ptr (m_inner_svalue
);
867 return hstate
.end ();
870 bool operator== (const key_t
&other
) const
872 return (m_type
== other
.m_type
873 && m_outer_size
== other
.m_outer_size
874 && m_inner_svalue
== other
.m_inner_svalue
);
877 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
878 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
879 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
880 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
883 const svalue
*m_outer_size
;
884 const svalue
*m_inner_svalue
;
886 repeated_svalue (tree type
,
887 const svalue
*outer_size
,
888 const svalue
*inner_svalue
);
890 enum svalue_kind
get_kind () const final override
{ return SK_REPEATED
; }
891 const repeated_svalue
*dyn_cast_repeated_svalue () const final override
896 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
897 void accept (visitor
*v
) const final override
;
899 const svalue
*get_outer_size () const { return m_outer_size
; }
900 const svalue
*get_inner_svalue () const { return m_inner_svalue
; }
902 bool all_zeroes_p () const final override
;
905 maybe_fold_bits_within (tree type
,
906 const bit_range
&subrange
,
907 region_model_manager
*mgr
) const final override
;
910 const svalue
*m_outer_size
;
911 const svalue
*m_inner_svalue
;
919 is_a_helper
<const repeated_svalue
*>::test (const svalue
*sval
)
921 return sval
->get_kind () == SK_REPEATED
;
924 template <> struct default_hash_traits
<repeated_svalue::key_t
>
925 : public member_function_hash_traits
<repeated_svalue::key_t
>
927 static const bool empty_zero_p
= false;
932 /* A range of bits/bytes within another svalue
933 e.g. bytes 5-39 of INITIAL_SVALUE(R).
934 These can be generated for prefixes and suffixes when part of a binding
935 is clobbered, so that we don't lose too much information. */
937 class bits_within_svalue
: public svalue
940 /* A support class for uniquifying instances of bits_within_svalue. */
944 const bit_range
&bits
,
945 const svalue
*inner_svalue
)
946 : m_type (type
), m_bits (bits
), m_inner_svalue (inner_svalue
)
949 hashval_t
hash () const
951 inchash::hash hstate
;
952 hstate
.add_ptr (m_type
);
953 hstate
.add_ptr (m_inner_svalue
);
954 return hstate
.end ();
957 bool operator== (const key_t
&other
) const
959 return (m_type
== other
.m_type
960 && m_bits
== other
.m_bits
961 && m_inner_svalue
== other
.m_inner_svalue
);
964 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
965 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
966 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
967 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
971 const svalue
*m_inner_svalue
;
973 bits_within_svalue (tree type
,
974 const bit_range
&bits
,
975 const svalue
*inner_svalue
);
977 enum svalue_kind
get_kind () const final override
{ return SK_BITS_WITHIN
; }
978 const bits_within_svalue
*
979 dyn_cast_bits_within_svalue () const final override
984 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
985 void accept (visitor
*v
) const final override
;
986 bool implicitly_live_p (const svalue_set
*,
987 const region_model
*) const final override
;
989 const bit_range
&get_bits () const { return m_bits
; }
990 const svalue
*get_inner_svalue () const { return m_inner_svalue
; }
993 maybe_fold_bits_within (tree type
,
994 const bit_range
&subrange
,
995 region_model_manager
*mgr
) const final override
;
998 const bit_range m_bits
;
999 const svalue
*m_inner_svalue
;
1007 is_a_helper
<const bits_within_svalue
*>::test (const svalue
*sval
)
1009 return sval
->get_kind () == SK_BITS_WITHIN
;
1012 template <> struct default_hash_traits
<bits_within_svalue::key_t
>
1013 : public member_function_hash_traits
<bits_within_svalue::key_t
>
1015 static const bool empty_zero_p
= false;
1020 /* Concrete subclass of svalue: decorate another svalue,
1021 so that the resulting svalue can be identified as being
1022 "interesting to control flow".
1023 For example, consider the return value from setjmp. We
1024 don't want to merge states in which the result is 0 with
1025 those in which the result is non-zero. By using an
1026 unmergeable_svalue for the result, we can inhibit such merges
1027 and have separate exploded nodes for those states, keeping
1028 the first and second returns from setjmp distinct in the exploded
1031 class unmergeable_svalue
: public svalue
1034 unmergeable_svalue (const svalue
*arg
)
1035 : svalue (complexity (arg
), arg
->get_type ()), m_arg (arg
)
1039 enum svalue_kind
get_kind () const final override
{ return SK_UNMERGEABLE
; }
1040 const unmergeable_svalue
*
1041 dyn_cast_unmergeable_svalue () const final override
{ return this; }
1043 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1044 void accept (visitor
*v
) const final override
;
1045 bool implicitly_live_p (const svalue_set
*,
1046 const region_model
*) const final override
;
1048 const svalue
*get_arg () const { return m_arg
; }
1051 const svalue
*m_arg
;
1059 is_a_helper
<const unmergeable_svalue
*>::test (const svalue
*sval
)
1061 return sval
->get_kind () == SK_UNMERGEABLE
;
1066 /* Concrete subclass of svalue for use in selftests, where
1067 we want a specific but unknown svalue.
1068 Unlike other svalue subclasses these aren't managed by
1069 region_model_manager. */
1071 class placeholder_svalue
: public svalue
1074 placeholder_svalue (tree type
, const char *name
)
1075 : svalue (complexity (1, 1), type
), m_name (name
)
1079 enum svalue_kind
get_kind () const final override
{ return SK_PLACEHOLDER
; }
1081 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1082 void accept (visitor
*v
) const final override
;
1084 const char *get_name () const { return m_name
; }
1095 is_a_helper
<const placeholder_svalue
*>::test (const svalue
*sval
)
1097 return sval
->get_kind () == SK_PLACEHOLDER
;
1102 /* Concrete subclass of svalue representing a "widening" seen when merging
1103 states, widening from a base value to {base value, iter value} and thus
1104 representing a possible fixed point in an iteration from the base to
1105 +ve infinity, or -ve infinity, and thus useful for representing a value
1107 We also need to capture the program_point at which the merger happens,
1108 so that distinguish between different iterators, and thus handle
1109 nested loops. (currently we capture the function_point instead, for
1110 simplicity of hashing). */
1112 class widening_svalue
: public svalue
1115 /* A support class for uniquifying instances of widening_svalue. */
1118 key_t (tree type
, const function_point
&point
,
1119 const svalue
*base_sval
, const svalue
*iter_sval
)
1120 : m_type (type
), m_point (point
),
1121 m_base_sval (base_sval
), m_iter_sval (iter_sval
)
1124 hashval_t
hash () const
1126 inchash::hash hstate
;
1127 hstate
.add_ptr (m_base_sval
);
1128 hstate
.add_ptr (m_iter_sval
);
1129 return hstate
.end ();
1132 bool operator== (const key_t
&other
) const
1134 return (m_type
== other
.m_type
1135 && m_point
== other
.m_point
1136 && m_base_sval
== other
.m_base_sval
1137 && m_iter_sval
== other
.m_iter_sval
);
1140 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
1141 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
1142 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
1143 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
1146 function_point m_point
;
1147 const svalue
*m_base_sval
;
1148 const svalue
*m_iter_sval
;
1158 widening_svalue (tree type
, const function_point
&point
,
1159 const svalue
*base_sval
, const svalue
*iter_sval
)
1160 : svalue (complexity::from_pair (base_sval
->get_complexity (),
1161 iter_sval
->get_complexity ()),
1164 m_base_sval (base_sval
), m_iter_sval (iter_sval
)
1166 gcc_assert (base_sval
->can_have_associated_state_p ());
1167 gcc_assert (iter_sval
->can_have_associated_state_p ());
1170 enum svalue_kind
get_kind () const final override
{ return SK_WIDENING
; }
1171 const widening_svalue
*dyn_cast_widening_svalue () const final override
1176 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1177 void accept (visitor
*v
) const final override
;
1179 const function_point
&get_point () const { return m_point
; }
1180 const svalue
*get_base_svalue () const { return m_base_sval
; }
1181 const svalue
*get_iter_svalue () const { return m_iter_sval
; }
1183 enum direction_t
get_direction () const;
1185 tristate
eval_condition_without_cm (enum tree_code op
,
1186 tree rhs_cst
) const;
1189 function_point m_point
;
1190 const svalue
*m_base_sval
;
1191 const svalue
*m_iter_sval
;
1199 is_a_helper
<const widening_svalue
*>::test (const svalue
*sval
)
1201 return sval
->get_kind () == SK_WIDENING
;
1204 template <> struct default_hash_traits
<widening_svalue::key_t
>
1205 : public member_function_hash_traits
<widening_svalue::key_t
>
1207 static const bool empty_zero_p
= false;
1212 /* Concrete subclass of svalue representing a mapping of bit-ranges
1213 to svalues, analogous to a cluster within the store.
1215 This is for use in places where we want to represent a store-like
1216 mapping, but are required to use an svalue, such as when handling
1217 compound assignments and compound return values.
1219 All keys within the underlying binding_map are required to be concrete,
1222 Instances of this class shouldn't be bound as-is into the store;
1223 instead they should be unpacked. Similarly, they should not be
1226 class compound_svalue
: public svalue
1229 typedef binding_map::iterator_t iterator_t
;
1231 /* A support class for uniquifying instances of compound_svalue.
1232 Note that to avoid copies, keys store pointers to binding_maps,
1233 rather than the maps themselves. */
1236 key_t (tree type
, const binding_map
*map_ptr
)
1237 : m_type (type
), m_map_ptr (map_ptr
)
1240 hashval_t
hash () const
1242 inchash::hash hstate
;
1243 hstate
.add_ptr (m_type
);
1244 //hstate.add_ptr (m_map_ptr); // TODO
1245 return hstate
.end ();
1248 bool operator== (const key_t
&other
) const
1250 return (m_type
== other
.m_type
1251 && *m_map_ptr
== *other
.m_map_ptr
);
1254 void mark_deleted () { m_type
= reinterpret_cast<tree
> (1); }
1255 void mark_empty () { m_type
= reinterpret_cast<tree
> (2); }
1256 bool is_deleted () const { return m_type
== reinterpret_cast<tree
> (1); }
1257 bool is_empty () const { return m_type
== reinterpret_cast<tree
> (2); }
1260 const binding_map
*m_map_ptr
;
1263 compound_svalue (tree type
, const binding_map
&map
);
1265 enum svalue_kind
get_kind () const final override
{ return SK_COMPOUND
; }
1266 const compound_svalue
*dyn_cast_compound_svalue () const final override
1271 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1272 void accept (visitor
*v
) const final override
;
1274 const binding_map
&get_map () const { return m_map
; }
1276 iterator_t
begin () const { return m_map
.begin (); }
1277 iterator_t
end () const { return m_map
.end (); }
1279 struct key_t
make_key () const
1281 return key_t (get_type (), &m_map
);
1285 maybe_fold_bits_within (tree type
,
1286 const bit_range
&subrange
,
1287 region_model_manager
*mgr
) const final override
;
1290 static complexity
calc_complexity (const binding_map
&map
);
1300 is_a_helper
<const compound_svalue
*>::test (const svalue
*sval
)
1302 return sval
->get_kind () == SK_COMPOUND
;
1305 template <> struct default_hash_traits
<compound_svalue::key_t
>
1306 : public member_function_hash_traits
<compound_svalue::key_t
>
1308 static const bool empty_zero_p
= false;
1313 /* A bundle of state for purging information from a program_state about
1314 a conjured_svalue. We pass this whenever calling
1315 get_or_create_conjured_svalue, so that if the program_state already
1316 has information about this conjured_svalue on an execution path, we
1317 can purge that information, to avoid the analyzer confusing the two
1318 values as being the same. */
1320 class conjured_purge
1323 conjured_purge (region_model
*model
, region_model_context
*ctxt
)
1324 : m_model (model
), m_ctxt (ctxt
)
1327 void purge (const conjured_svalue
*sval
) const;
1330 region_model
*m_model
;
1331 region_model_context
*m_ctxt
;
1334 /* A defined value arising from a statement, where we want to identify a
1335 particular unknown value, rather than resorting to the unknown_value
1336 singleton, so that the value can have sm-state.
1338 Comparisons of variables that share the same conjured_svalue are known
1339 to be equal, even if we don't know what the value is.
1341 For example, this is used for the values of regions that may have been
1342 touched when calling an unknown function.
1344 The value captures a region as well as a stmt in order to avoid falsely
1345 aliasing the various values that could arise in one statement. For
1347 unknown_fn (&a, &b);
1348 we want values to clobber a and b with, but we don't want to use the
1349 same value, or it would falsely implicitly assume that a == b. */
1351 class conjured_svalue
: public svalue
1354 /* A support class for uniquifying instances of conjured_svalue. */
1357 key_t (tree type
, const gimple
*stmt
, const region
*id_reg
)
1358 : m_type (type
), m_stmt (stmt
), m_id_reg (id_reg
)
1361 hashval_t
hash () const
1363 inchash::hash hstate
;
1364 hstate
.add_ptr (m_type
);
1365 hstate
.add_ptr (m_stmt
);
1366 hstate
.add_ptr (m_id_reg
);
1367 return hstate
.end ();
1370 bool operator== (const key_t
&other
) const
1372 return (m_type
== other
.m_type
1373 && m_stmt
== other
.m_stmt
1374 && m_id_reg
== other
.m_id_reg
);
1377 /* Use m_stmt to mark empty/deleted, as m_type can be NULL for
1378 legitimate instances. */
1379 void mark_deleted () { m_stmt
= reinterpret_cast<const gimple
*> (1); }
1380 void mark_empty () { m_stmt
= NULL
; }
1381 bool is_deleted () const
1383 return m_stmt
== reinterpret_cast<const gimple
*> (1);
1385 bool is_empty () const { return m_stmt
== NULL
; }
1388 const gimple
*m_stmt
;
1389 const region
*m_id_reg
;
1392 conjured_svalue (tree type
, const gimple
*stmt
, const region
*id_reg
)
1393 : svalue (complexity (id_reg
), type
),
1394 m_stmt (stmt
), m_id_reg (id_reg
)
1396 gcc_assert (m_stmt
!= NULL
);
1399 enum svalue_kind
get_kind () const final override
{ return SK_CONJURED
; }
1400 const conjured_svalue
*dyn_cast_conjured_svalue () const final override
1405 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1406 void accept (visitor
*v
) const final override
;
1408 const gimple
*get_stmt () const { return m_stmt
; }
1409 const region
*get_id_region () const { return m_id_reg
; }
1412 const gimple
*m_stmt
;
1413 const region
*m_id_reg
;
1421 is_a_helper
<const conjured_svalue
*>::test (const svalue
*sval
)
1423 return sval
->get_kind () == SK_CONJURED
;
1426 template <> struct default_hash_traits
<conjured_svalue::key_t
>
1427 : public member_function_hash_traits
<conjured_svalue::key_t
>
1429 static const bool empty_zero_p
= true;
1434 /* An output from a deterministic asm stmt, where we want to identify a
1435 particular unknown value, rather than resorting to the unknown_value
1438 Comparisons of variables that share the same asm_output_svalue are known
1439 to be equal, even if we don't know what the value is. */
1441 class asm_output_svalue
: public svalue
1444 /* Imposing an upper limit and using a (small) array allows key_t
1445 to avoid memory management. */
1446 static const unsigned MAX_INPUTS
= 2;
1448 /* A support class for uniquifying instances of asm_output_svalue. */
1452 const char *asm_string
,
1453 unsigned output_idx
,
1454 const vec
<const svalue
*> &inputs
)
1455 : m_type (type
), m_asm_string (asm_string
), m_output_idx (output_idx
),
1456 m_num_inputs (inputs
.length ())
1458 gcc_assert (inputs
.length () <= MAX_INPUTS
);
1459 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1460 m_input_arr
[i
] = inputs
[i
];
1463 hashval_t
hash () const
1465 inchash::hash hstate
;
1466 hstate
.add_ptr (m_type
);
1467 /* We don't bother hashing m_asm_str. */
1468 hstate
.add_int (m_output_idx
);
1469 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1470 hstate
.add_ptr (m_input_arr
[i
]);
1471 return hstate
.end ();
1474 bool operator== (const key_t
&other
) const
1476 if (!(m_type
== other
.m_type
1477 && 0 == (strcmp (m_asm_string
, other
.m_asm_string
))
1478 && m_output_idx
== other
.m_output_idx
1479 && m_num_inputs
== other
.m_num_inputs
))
1481 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1482 if (m_input_arr
[i
] != other
.m_input_arr
[i
])
1487 /* Use m_asm_string to mark empty/deleted, as m_type can be NULL for
1488 legitimate instances. */
1489 void mark_deleted () { m_asm_string
= reinterpret_cast<const char *> (1); }
1490 void mark_empty () { m_asm_string
= NULL
; }
1491 bool is_deleted () const
1493 return m_asm_string
== reinterpret_cast<const char *> (1);
1495 bool is_empty () const { return m_asm_string
== NULL
; }
1498 const char *m_asm_string
;
1499 unsigned m_output_idx
;
1500 unsigned m_num_inputs
;
1501 const svalue
*m_input_arr
[MAX_INPUTS
];
1504 asm_output_svalue (tree type
,
1505 const char *asm_string
,
1506 unsigned output_idx
,
1507 unsigned num_outputs
,
1508 const vec
<const svalue
*> &inputs
)
1509 : svalue (complexity::from_vec_svalue (inputs
), type
),
1510 m_asm_string (asm_string
),
1511 m_output_idx (output_idx
),
1512 m_num_outputs (num_outputs
),
1513 m_num_inputs (inputs
.length ())
1515 gcc_assert (inputs
.length () <= MAX_INPUTS
);
1516 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1517 m_input_arr
[i
] = inputs
[i
];
1520 enum svalue_kind
get_kind () const final override
{ return SK_ASM_OUTPUT
; }
1521 const asm_output_svalue
*
1522 dyn_cast_asm_output_svalue () const final override
1527 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1528 void accept (visitor
*v
) const final override
;
1530 const char *get_asm_string () const { return m_asm_string
; }
1531 unsigned get_output_idx () const { return m_output_idx
; }
1532 unsigned get_num_outputs () const { return m_num_outputs
; }
1533 unsigned get_num_inputs () const { return m_num_inputs
; }
1534 const svalue
*get_input (unsigned idx
) const { return m_input_arr
[idx
]; }
1537 void dump_input (pretty_printer
*pp
,
1541 unsigned input_idx_to_asm_idx (unsigned input_idx
) const;
1543 const char *m_asm_string
;
1544 unsigned m_output_idx
;
1546 /* We capture this so that we can offset the input indices
1547 to match the %0, %1, %2 in the asm_string when dumping. */
1548 unsigned m_num_outputs
;
1550 unsigned m_num_inputs
;
1551 const svalue
*m_input_arr
[MAX_INPUTS
];
1559 is_a_helper
<const asm_output_svalue
*>::test (const svalue
*sval
)
1561 return sval
->get_kind () == SK_ASM_OUTPUT
;
1564 template <> struct default_hash_traits
<asm_output_svalue::key_t
>
1565 : public member_function_hash_traits
<asm_output_svalue::key_t
>
1567 static const bool empty_zero_p
= true;
1572 /* The return value from a function with __attribute((const)) for given
1573 inputs, provided that we don't have too many inputs, and all of them
1576 Comparisons of variables that share the same const_fn_result_svalue are known
1577 to be equal, even if we don't know what the value is. */
1579 class const_fn_result_svalue
: public svalue
1582 /* Imposing an upper limit and using a (small) array allows key_t
1583 to avoid memory management. */
1584 static const unsigned MAX_INPUTS
= 2;
1586 /* A support class for uniquifying instances of const_fn_result_svalue. */
1591 const vec
<const svalue
*> &inputs
)
1592 : m_type (type
), m_fndecl (fndecl
),
1593 m_num_inputs (inputs
.length ())
1595 gcc_assert (inputs
.length () <= MAX_INPUTS
);
1596 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1597 m_input_arr
[i
] = inputs
[i
];
1600 hashval_t
hash () const
1602 inchash::hash hstate
;
1603 hstate
.add_ptr (m_type
);
1604 hstate
.add_ptr (m_fndecl
);
1605 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1606 hstate
.add_ptr (m_input_arr
[i
]);
1607 return hstate
.end ();
1610 bool operator== (const key_t
&other
) const
1612 if (!(m_type
== other
.m_type
1613 && m_fndecl
== other
.m_fndecl
1614 && m_num_inputs
== other
.m_num_inputs
))
1616 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1617 if (m_input_arr
[i
] != other
.m_input_arr
[i
])
1622 /* Use m_fndecl to mark empty/deleted. */
1623 void mark_deleted () { m_fndecl
= reinterpret_cast<tree
> (1); }
1624 void mark_empty () { m_fndecl
= NULL
; }
1625 bool is_deleted () const
1627 return m_fndecl
== reinterpret_cast<tree
> (1);
1629 bool is_empty () const { return m_fndecl
== NULL
; }
1633 unsigned m_num_inputs
;
1634 const svalue
*m_input_arr
[MAX_INPUTS
];
1637 const_fn_result_svalue (tree type
,
1639 const vec
<const svalue
*> &inputs
)
1640 : svalue (complexity::from_vec_svalue (inputs
), type
),
1642 m_num_inputs (inputs
.length ())
1644 gcc_assert (inputs
.length () <= MAX_INPUTS
);
1645 for (unsigned i
= 0; i
< m_num_inputs
; i
++)
1646 m_input_arr
[i
] = inputs
[i
];
1649 enum svalue_kind
get_kind () const final override
1651 return SK_CONST_FN_RESULT
;
1653 const const_fn_result_svalue
*
1654 dyn_cast_const_fn_result_svalue () const final override
1659 void dump_to_pp (pretty_printer
*pp
, bool simple
) const final override
;
1660 void accept (visitor
*v
) const final override
;
1662 tree
get_fndecl () const { return m_fndecl
; }
1663 unsigned get_num_inputs () const { return m_num_inputs
; }
1664 const svalue
*get_input (unsigned idx
) const { return m_input_arr
[idx
]; }
1667 void dump_input (pretty_printer
*pp
,
1673 unsigned m_num_inputs
;
1674 const svalue
*m_input_arr
[MAX_INPUTS
];
1682 is_a_helper
<const const_fn_result_svalue
*>::test (const svalue
*sval
)
1684 return sval
->get_kind () == SK_CONST_FN_RESULT
;
1687 template <> struct default_hash_traits
<const_fn_result_svalue::key_t
>
1688 : public member_function_hash_traits
<const_fn_result_svalue::key_t
>
1690 static const bool empty_zero_p
= true;
1693 #endif /* GCC_ANALYZER_SVALUE_H */