Line data Source code
1 : /* Symbolic values.
2 : Copyright (C) 2019-2026 Free Software Foundation, Inc.
3 : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it
8 : under the terms of the GNU General Public License as published by
9 : the Free Software Foundation; either version 3, or (at your option)
10 : any later version.
11 :
12 : GCC is distributed in the hope that it will be useful, but
13 : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : General Public License for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #ifndef GCC_ANALYZER_SVALUE_H
22 : #define GCC_ANALYZER_SVALUE_H
23 :
24 : #include "analyzer/symbol.h"
25 : #include "analyzer/store.h"
26 : #include "analyzer/program-point.h"
27 : #include "text-art/widget.h"
28 :
29 : using namespace ana;
30 : using text_art::dump_widget_info;
31 :
32 : namespace ana {
33 :
34 : /* An enum for discriminating between the different concrete subclasses
35 : of svalue. */
36 :
37 : enum svalue_kind
38 : {
39 : SK_REGION,
40 : SK_CONSTANT,
41 : SK_UNKNOWN,
42 : SK_POISONED,
43 : SK_SETJMP,
44 : SK_INITIAL,
45 : SK_UNARYOP,
46 : SK_BINOP,
47 : SK_SUB,
48 : SK_REPEATED,
49 : SK_BITS_WITHIN,
50 : SK_UNMERGEABLE,
51 : SK_PLACEHOLDER,
52 : SK_WIDENING,
53 : SK_COMPOUND,
54 : SK_CONJURED,
55 : SK_ASM_OUTPUT,
56 : SK_CONST_FN_RESULT
57 : };
58 :
59 : /* svalue and its subclasses.
60 :
61 : The class hierarchy looks like this (using indentation to show
62 : inheritance, and with svalue_kinds shown for the concrete subclasses):
63 :
64 : svalue
65 : region_svalue (SK_REGION): a pointer to a region
66 : constant_svalue (SK_CONSTANT): a constant
67 : unknown_svalue (SK_UNKNOWN): an unknowable value
68 : poisoned_svalue (SK_POISONED): a unusable value (undefined)
69 : setjmp_svalue (SK_SETJMP): a setjmp/longjmp buffer
70 : initial_svalue (SK_INITIAL): the initial value of a region
71 : unaryop_svalue (SK_UNARYOP): unary operation on another svalue
72 : binop_svalue (SK_BINOP): binary operation on two svalues
73 : sub_svalue (SK_SUB): the result of accessing a subregion
74 : repeated_svalue (SK_REPEATED): repeating an svalue to fill a larger region
75 : bits_within_svalue (SK_BITS_WITHIN): a range of bits/bytes within a larger
76 : svalue
77 : unmergeable_svalue (SK_UNMERGEABLE): a value that is so interesting
78 : from a control-flow perspective that it can inhibit state-merging
79 : placeholder_svalue (SK_PLACEHOLDER): for use in selftests.
80 : widening_svalue (SK_WIDENING): a merger of two svalues (possibly
81 : in an iteration).
82 : compound_svalue (SK_COMPOUND): a mapping of bit-ranges to svalues
83 : conjured_svalue (SK_CONJURED): a value arising from a stmt
84 : asm_output_svalue (SK_ASM_OUTPUT): an output from a deterministic
85 : asm stmt.
86 : const_fn_result_svalue (SK_CONST_FN_RESULT): the return value from
87 : a function with __attribute((const)) for given inputs. */
88 :
89 : /* An abstract base class representing a value held by a region of memory. */
90 :
91 : class svalue : public symbol
92 : {
93 : public:
94 28 : virtual ~svalue () {}
95 :
96 55920981 : tree get_type () const { return m_type; }
97 :
98 : virtual enum svalue_kind get_kind () const = 0;
99 :
100 : void print (const region_model &model,
101 : pretty_printer *pp) const;
102 :
103 : virtual void dump_to_pp (pretty_printer *pp, bool simple) const = 0;
104 : void dump () const;
105 : void dump (bool simple) const;
106 : label_text get_desc (bool simple=true) const;
107 :
108 : std::unique_ptr<json::value> to_json () const;
109 :
110 : std::unique_ptr<text_art::tree_widget>
111 : make_dump_widget (const dump_widget_info &dwi,
112 : const char *prefix = nullptr) const;
113 :
114 : virtual const region_svalue *
115 14099899 : dyn_cast_region_svalue () const { return nullptr; }
116 : virtual const constant_svalue *
117 9605882 : dyn_cast_constant_svalue () const { return nullptr; }
118 : virtual const poisoned_svalue *
119 2000608 : dyn_cast_poisoned_svalue () const { return nullptr; }
120 : virtual const setjmp_svalue *
121 38 : dyn_cast_setjmp_svalue () const { return nullptr; }
122 : virtual const initial_svalue *
123 3932023 : dyn_cast_initial_svalue () const { return nullptr; }
124 : virtual const unaryop_svalue *
125 12479885 : dyn_cast_unaryop_svalue () const { return nullptr; }
126 : virtual const binop_svalue *
127 1103493 : dyn_cast_binop_svalue () const { return nullptr; }
128 : virtual const sub_svalue *
129 3615598 : dyn_cast_sub_svalue () const { return nullptr; }
130 : virtual const repeated_svalue *
131 16181 : dyn_cast_repeated_svalue () const { return nullptr; }
132 : virtual const bits_within_svalue *
133 0 : dyn_cast_bits_within_svalue () const { return nullptr; }
134 : virtual const unmergeable_svalue *
135 17268561 : dyn_cast_unmergeable_svalue () const { return nullptr; }
136 : virtual const widening_svalue *
137 479943 : dyn_cast_widening_svalue () const { return nullptr; }
138 : virtual const compound_svalue *
139 13245498 : dyn_cast_compound_svalue () const { return nullptr; }
140 : virtual const conjured_svalue *
141 0 : dyn_cast_conjured_svalue () const { return nullptr; }
142 : virtual const asm_output_svalue *
143 0 : dyn_cast_asm_output_svalue () const { return nullptr; }
144 : virtual const const_fn_result_svalue *
145 0 : dyn_cast_const_fn_result_svalue () const { return nullptr; }
146 :
147 : tree maybe_get_constant () const;
148 : const region *maybe_get_region () const;
149 : const svalue *maybe_undo_cast () const;
150 : const svalue *unwrap_any_unmergeable () const;
151 :
152 : const svalue *can_merge_p (const svalue *other,
153 : region_model_manager *mgr,
154 : model_merger *merger) const;
155 :
156 : virtual void accept (visitor *v) const = 0;
157 :
158 : bool live_p (const svalue_set *live_svalues,
159 : const region_model *model) const;
160 : virtual bool implicitly_live_p (const svalue_set *live_svalues,
161 : const region_model *model) const;
162 :
163 : static int cmp_ptr (const svalue *, const svalue *);
164 : static int cmp_ptr_ptr (const void *, const void *);
165 :
166 : bool involves_p (const svalue *other) const;
167 :
168 : const svalue *
169 : extract_bit_range (tree type,
170 : const bit_range &subrange,
171 : region_model_manager *mgr) const;
172 :
173 : virtual const svalue *
174 : maybe_fold_bits_within (tree type,
175 : const bit_range &subrange,
176 : region_model_manager *mgr) const;
177 :
178 : virtual bool all_zeroes_p () const;
179 :
180 : /* Can this svalue be involved in constraints and sm-state?
181 : Most can, but UNKNOWN and POISONED svalues are singletons
182 : per-type and thus it's meaningless for them to "have state". */
183 2386130 : virtual bool can_have_associated_state_p () const { return true; }
184 :
185 : const region *maybe_get_deref_base_region () const;
186 :
187 : bool maybe_print_for_user (pretty_printer *pp,
188 : const region_model &model,
189 : const svalue *outer_sval = nullptr) const;
190 :
191 : tree maybe_get_type_from_typeinfo () const;
192 :
193 : /* If we can get a value_range for this svalue, write it to OUT
194 : and return true. Otherwise return false. */
195 : bool
196 208486 : maybe_get_value_range (value_range &out) const
197 : {
198 208486 : if (maybe_get_value_range_1 (out))
199 : {
200 152867 : gcc_assert (!out.undefined_p ());
201 : return true;
202 : }
203 : return false;
204 : }
205 :
206 : protected:
207 200427 : svalue (complexity c, symbol::id_t id, tree type)
208 89707 : : symbol (c, id), m_type (type)
209 : {}
210 :
211 : void print_svalue_node_label (pretty_printer *pp) const;
212 :
213 : private:
214 : virtual void
215 : print_dump_widget_label (pretty_printer *pp) const = 0;
216 : virtual void
217 : add_dump_widget_children (text_art::tree_widget &,
218 : const dump_widget_info &dwi) const = 0;
219 : virtual bool
220 : maybe_get_value_range_1 (value_range &out) const;
221 :
222 : tree m_type;
223 : };
224 :
225 : /* Concrete subclass of svalue representing a pointer value that points to
226 : a known region */
227 :
228 : class region_svalue : public svalue
229 : {
230 : public:
231 : /* A support class for uniquifying instances of region_svalue. */
232 : struct key_t
233 : {
234 986748 : key_t (tree type, const region *reg)
235 986748 : : m_type (type), m_reg (reg)
236 : {}
237 :
238 5031010 : hashval_t hash () const
239 : {
240 5031010 : inchash::hash hstate;
241 5031010 : hstate.add_ptr (m_type);
242 5031010 : hstate.add_ptr (m_reg);
243 5031010 : return hstate.end ();
244 : }
245 :
246 4762718 : bool operator== (const key_t &other) const
247 : {
248 4762718 : return (m_type == other.m_type && m_reg == other.m_reg);
249 : }
250 :
251 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
252 97872 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
253 5380201 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
254 18112471 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
255 :
256 : tree m_type;
257 : const region *m_reg;
258 : };
259 :
260 25586 : region_svalue (symbol::id_t id, tree type, const region *reg)
261 25586 : : svalue (complexity (reg), id, type),
262 25586 : m_reg (reg)
263 : {
264 25586 : gcc_assert (m_reg != nullptr);
265 25586 : }
266 :
267 13316129 : enum svalue_kind get_kind () const final override { return SK_REGION; }
268 : const region_svalue *
269 2070106 : dyn_cast_region_svalue () const final override { return this; }
270 :
271 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
272 :
273 : void
274 : print_dump_widget_label (pretty_printer *pp) const final override;
275 : void
276 : add_dump_widget_children (text_art::tree_widget &w,
277 : const dump_widget_info &dwi) const final override;
278 :
279 : void accept (visitor *v) const final override;
280 : bool implicitly_live_p (const svalue_set *,
281 : const region_model *) const final override;
282 :
283 3906163 : const region * get_pointee () const { return m_reg; }
284 :
285 : static tristate eval_condition (const region_svalue *lhs_ptr,
286 : enum tree_code op,
287 : const region_svalue *rhs_ptr);
288 :
289 : private:
290 : const region *m_reg;
291 : };
292 :
293 : } // namespace ana
294 :
295 : template <>
296 : template <>
297 : inline bool
298 61839 : is_a_helper <const region_svalue *>::test (const svalue *sval)
299 : {
300 61839 : return sval->get_kind () == SK_REGION;
301 : }
302 :
303 : template <> struct default_hash_traits<region_svalue::key_t>
304 : : public member_function_hash_traits<region_svalue::key_t>
305 : {
306 : static const bool empty_zero_p = false;
307 : };
308 :
309 : namespace ana {
310 :
311 : /* Concrete subclass of svalue representing a specific constant value.
312 : The type will either be the same as that of the underlying tree constant,
313 : or NULL_TREE indicating the constant is intended to be "typeless". */
314 :
315 : class constant_svalue : public svalue
316 : {
317 : public:
318 : /* A support class for uniquifying instances of region_svalue. */
319 : struct key_t
320 : {
321 2551197 : key_t (tree type, tree cst)
322 2551197 : : m_type (type), m_cst (cst)
323 : {}
324 :
325 16066883 : hashval_t hash () const
326 : {
327 16066883 : inchash::hash hstate;
328 16066883 : hstate.add_ptr (m_type);
329 16066883 : hstate.add_ptr (m_cst);
330 16066883 : return hstate.end ();
331 : }
332 :
333 16218433 : bool operator== (const key_t &other) const
334 : {
335 16218433 : return (m_type == other.m_type && m_cst == other.m_cst);
336 : }
337 :
338 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
339 177010 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
340 16900920 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
341 49472983 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
342 :
343 : tree m_type;
344 : tree m_cst;
345 : };
346 :
347 56675 : constant_svalue (symbol::id_t id, tree type, tree cst_expr)
348 56675 : : svalue (complexity (1, 1), id, type),
349 56675 : m_cst_expr (cst_expr)
350 : {
351 56675 : gcc_assert (cst_expr);
352 56675 : gcc_assert (CONSTANT_CLASS_P (cst_expr));
353 56675 : gcc_assert (type == TREE_TYPE (cst_expr) || type == NULL_TREE);
354 56675 : }
355 :
356 36464498 : enum svalue_kind get_kind () const final override { return SK_CONSTANT; }
357 : const constant_svalue *
358 4837520 : dyn_cast_constant_svalue () const final override { return this; }
359 :
360 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
361 :
362 : void
363 : print_dump_widget_label (pretty_printer *pp) const final override;
364 : void
365 : add_dump_widget_children (text_art::tree_widget &w,
366 : const dump_widget_info &dwi) const final override;
367 :
368 : void accept (visitor *v) const final override;
369 : bool implicitly_live_p (const svalue_set *,
370 : const region_model *) const final override;
371 :
372 6316018 : tree get_constant () const { return m_cst_expr; }
373 : static tristate eval_condition (const constant_svalue *lhs,
374 : enum tree_code op,
375 : const constant_svalue *rhs);
376 :
377 : const svalue *
378 : maybe_fold_bits_within (tree type,
379 : const bit_range &subrange,
380 : region_model_manager *mgr) const final override;
381 :
382 : bool all_zeroes_p () const final override;
383 :
384 : bool maybe_get_value_range_1 (value_range &out) const final override;
385 :
386 : private:
387 : tree m_cst_expr;
388 : };
389 :
390 : } // namespace ana
391 :
392 : template <>
393 : template <>
394 : inline bool
395 1834 : is_a_helper <const constant_svalue *>::test (const svalue *sval)
396 : {
397 1834 : return sval->get_kind () == SK_CONSTANT;
398 : }
399 :
400 : template <> struct default_hash_traits<constant_svalue::key_t>
401 : : public member_function_hash_traits<constant_svalue::key_t>
402 : {
403 : static const bool empty_zero_p = false;
404 : };
405 :
406 : namespace ana {
407 :
408 : /* Concrete subclass of svalue representing an unknowable value, the bottom
409 : value when thinking of svalues as a lattice.
410 : This is a singleton (w.r.t. its manager): there is a single unknown_svalue
411 : per type. Self-comparisons of such instances yield "unknown". */
412 :
413 : class unknown_svalue : public svalue
414 : {
415 : public:
416 10349 : unknown_svalue (symbol::id_t id, tree type)
417 10349 : : svalue (complexity (1, 1), id, type)
418 : {}
419 :
420 7635079 : enum svalue_kind get_kind () const final override { return SK_UNKNOWN; }
421 :
422 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
423 :
424 : void
425 : print_dump_widget_label (pretty_printer *pp) const final override;
426 : void
427 : add_dump_widget_children (text_art::tree_widget &w,
428 : const dump_widget_info &dwi) const final override;
429 :
430 : void accept (visitor *v) const final override;
431 :
432 : const svalue *
433 : maybe_fold_bits_within (tree type,
434 : const bit_range &subrange,
435 : region_model_manager *mgr) const final override;
436 :
437 : bool maybe_get_value_range_1 (value_range &out) const final override;
438 :
439 : /* Unknown values are singletons per-type, so can't have state. */
440 99087 : bool can_have_associated_state_p () const final override { return false; }
441 : };
442 :
443 : /* An enum describing a particular kind of "poisoned" value. */
444 :
445 : enum class poison_kind
446 : {
447 : /* For use to describe uninitialized memory. */
448 : uninit,
449 :
450 : /* For use to describe freed memory. */
451 : freed,
452 :
453 : /* For use to describe deleted memory. */
454 : deleted,
455 :
456 : /* For use on pointers to regions within popped stack frames. */
457 : popped_stack
458 : };
459 :
460 : extern const char *poison_kind_to_str (enum poison_kind);
461 :
462 : /* Concrete subclass of svalue representing a value that should not
463 : be used (e.g. uninitialized memory, freed memory). */
464 :
465 : class poisoned_svalue : public svalue
466 : {
467 : public:
468 : /* A support class for uniquifying instances of poisoned_svalue. */
469 : struct key_t
470 : {
471 201398 : key_t (enum poison_kind kind, tree type)
472 201398 : : m_kind (kind), m_type (type)
473 : {}
474 :
475 790592 : hashval_t hash () const
476 : {
477 790592 : inchash::hash hstate;
478 790592 : hstate.add_int (static_cast<int> (m_kind));
479 790592 : hstate.add_ptr (m_type);
480 790592 : return hstate.end ();
481 : }
482 :
483 633747 : bool operator== (const key_t &other) const
484 : {
485 633747 : return (m_kind == other.m_kind && m_type == other.m_type);
486 : }
487 :
488 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
489 52492 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
490 823543 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
491 3461910 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
492 :
493 : enum poison_kind m_kind;
494 : tree m_type;
495 : };
496 :
497 5976 : poisoned_svalue (enum poison_kind kind, symbol::id_t id, tree type)
498 5976 : : svalue (complexity (1, 1), id, type), m_kind (kind) {}
499 :
500 269368 : enum svalue_kind get_kind () const final override { return SK_POISONED; }
501 : const poisoned_svalue *
502 5396 : dyn_cast_poisoned_svalue () const final override { return this; }
503 :
504 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
505 :
506 : void
507 : print_dump_widget_label (pretty_printer *pp) const final override;
508 : void
509 : add_dump_widget_children (text_art::tree_widget &w,
510 : const dump_widget_info &dwi) const final override;
511 :
512 : void accept (visitor *v) const final override;
513 :
514 : const svalue *
515 : maybe_fold_bits_within (tree type,
516 : const bit_range &subrange,
517 : region_model_manager *mgr) const final override;
518 :
519 5412 : enum poison_kind get_poison_kind () const { return m_kind; }
520 :
521 : /* Poisoned svalues are singletons per-type, so can't have state. */
522 8395 : bool can_have_associated_state_p () const final override { return false; }
523 :
524 : private:
525 : enum poison_kind m_kind;
526 : };
527 :
528 : } // namespace ana
529 :
530 : template <>
531 : template <>
532 : inline bool
533 8 : is_a_helper <const poisoned_svalue *>::test (const svalue *sval)
534 : {
535 8 : return sval->get_kind () == SK_POISONED;
536 : }
537 :
538 : template <> struct default_hash_traits<poisoned_svalue::key_t>
539 : : public member_function_hash_traits<poisoned_svalue::key_t>
540 : {
541 : static const bool empty_zero_p = false;
542 : };
543 :
544 : namespace ana {
545 :
546 : /* A bundle of information recording a setjmp/sigsetjmp call, corresponding
547 : roughly to a jmp_buf. */
548 :
549 : struct setjmp_record
550 : {
551 34 : setjmp_record (const exploded_node *enode,
552 : const superedge *sedge,
553 : const gcall &setjmp_call)
554 34 : : m_enode (enode), m_sedge (sedge), m_setjmp_call (&setjmp_call)
555 : {
556 : }
557 :
558 18 : bool operator== (const setjmp_record &other) const
559 : {
560 18 : return (m_enode == other.m_enode
561 0 : && m_sedge == other.m_sedge
562 0 : && m_setjmp_call == other.m_setjmp_call);
563 : }
564 :
565 84 : void add_to_hash (inchash::hash *hstate) const
566 : {
567 84 : hstate->add_ptr (m_enode);
568 84 : hstate->add_ptr (m_sedge);
569 84 : hstate->add_ptr (m_setjmp_call);
570 84 : }
571 :
572 : static int cmp (const setjmp_record &rec1, const setjmp_record &rec2);
573 :
574 : const exploded_node *m_enode;
575 : const superedge *m_sedge;
576 : const gcall *m_setjmp_call;
577 : // non-null, but we can't use a reference since we're putting these in a hash_map
578 : };
579 :
580 : /* Concrete subclass of svalue representing buffers for setjmp/sigsetjmp,
581 : so that longjmp/siglongjmp can potentially "return" to an entirely
582 : different function. */
583 :
584 : class setjmp_svalue : public svalue
585 : {
586 : public:
587 : /* A support class for uniquifying instances of poisoned_svalue. */
588 : struct key_t
589 : {
590 34 : key_t (const setjmp_record &record, tree type)
591 34 : : m_record (record), m_type (type)
592 : {}
593 :
594 84 : hashval_t hash () const
595 : {
596 84 : inchash::hash hstate;
597 84 : m_record.add_to_hash (&hstate);
598 84 : hstate.add_ptr (m_type);
599 84 : return hstate.end ();
600 : }
601 :
602 18 : bool operator== (const key_t &other) const
603 : {
604 18 : return (m_record == other.m_record && m_type == other.m_type);
605 : }
606 :
607 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
608 51779 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
609 86 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
610 104595 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
611 :
612 : setjmp_record m_record;
613 : tree m_type;
614 : };
615 :
616 34 : setjmp_svalue (const setjmp_record &setjmp_record,
617 : symbol::id_t id,
618 : tree type)
619 34 : : svalue (complexity (1, 1), id, type), m_setjmp_record (setjmp_record)
620 : {}
621 :
622 2775 : enum svalue_kind get_kind () const final override { return SK_SETJMP; }
623 : const setjmp_svalue *
624 25 : dyn_cast_setjmp_svalue () const final override { return this; }
625 :
626 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
627 :
628 : void
629 : print_dump_widget_label (pretty_printer *pp) const final override;
630 : void
631 : add_dump_widget_children (text_art::tree_widget &w,
632 : const dump_widget_info &dwi) const final override;
633 :
634 : void accept (visitor *v) const final override;
635 :
636 : int get_enode_index () const;
637 :
638 0 : const setjmp_record &get_setjmp_record () const { return m_setjmp_record; }
639 :
640 : private:
641 : setjmp_record m_setjmp_record;
642 : };
643 :
644 : } // namespace ana
645 :
646 : template <>
647 : template <>
648 : inline bool
649 : is_a_helper <const setjmp_svalue *>::test (const svalue *sval)
650 : {
651 : return sval->get_kind () == SK_SETJMP;
652 : }
653 :
654 : template <> struct default_hash_traits<setjmp_svalue::key_t>
655 : : public member_function_hash_traits<setjmp_svalue::key_t>
656 : {
657 : static const bool empty_zero_p = false;
658 : };
659 :
660 : namespace ana {
661 :
662 : /* Concrete subclass of svalue representing the initial value of a
663 : specific region.
664 :
665 : This represents the initial value at the start of the analysis path,
666 : as opposed to the first time the region is accessed during the path.
667 : Hence as soon as we have a call to an unknown function, all previously
668 : unmodelled globals become implicitly "unknown" rathen than "initial". */
669 :
670 : class initial_svalue : public svalue
671 : {
672 : public:
673 26998 : initial_svalue (symbol::id_t id, tree type, const region *reg)
674 26998 : : svalue (complexity (reg), id, type), m_reg (reg)
675 : {
676 26998 : gcc_assert (m_reg != nullptr);
677 26998 : }
678 :
679 28248125 : enum svalue_kind get_kind () const final override { return SK_INITIAL; }
680 : const initial_svalue *
681 294289 : dyn_cast_initial_svalue () const final override { return this; }
682 :
683 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
684 :
685 : void
686 : print_dump_widget_label (pretty_printer *pp) const final override;
687 : void
688 : add_dump_widget_children (text_art::tree_widget &w,
689 : const dump_widget_info &dwi) const final override;
690 :
691 : void accept (visitor *v) const final override;
692 : bool implicitly_live_p (const svalue_set *,
693 : const region_model *) const final override;
694 :
695 : bool initial_value_of_param_p () const;
696 :
697 6051837 : const region *get_region () const { return m_reg; }
698 :
699 : private:
700 : const region *m_reg;
701 : };
702 :
703 : } // namespace ana
704 :
705 : template <>
706 : template <>
707 : inline bool
708 1653557 : is_a_helper <const initial_svalue *>::test (const svalue *sval)
709 : {
710 1653557 : return sval->get_kind () == SK_INITIAL;
711 : }
712 :
713 : namespace ana {
714 :
715 : /* Concrete subclass of svalue representing a unary operation on
716 : another svalues (e.g. a cast). */
717 :
718 : class unaryop_svalue : public svalue
719 : {
720 : public:
721 : /* A support class for uniquifying instances of unaryop_svalue. */
722 : struct key_t
723 : {
724 118585 : key_t (tree type, enum tree_code op, const svalue *arg)
725 118585 : : m_type (type), m_op (op), m_arg (arg)
726 : {}
727 :
728 693960 : hashval_t hash () const
729 : {
730 693960 : inchash::hash hstate;
731 693960 : hstate.add_ptr (m_type);
732 693960 : hstate.add_int (m_op);
733 693960 : hstate.add_ptr (m_arg);
734 693960 : return hstate.end ();
735 : }
736 :
737 697597 : bool operator== (const key_t &other) const
738 : {
739 697597 : return (m_type == other.m_type
740 290139 : && m_op == other.m_op
741 985655 : && m_arg == other.m_arg);
742 : }
743 :
744 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
745 65394 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
746 746378 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
747 2467992 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
748 :
749 : tree m_type;
750 : enum tree_code m_op;
751 : const svalue *m_arg;
752 : };
753 :
754 8438 : unaryop_svalue (symbol::id_t id, tree type, enum tree_code op,
755 : const svalue *arg)
756 8438 : : svalue (complexity (arg), id, type), m_op (op), m_arg (arg)
757 : {
758 8438 : gcc_assert (arg->can_have_associated_state_p ());
759 8438 : }
760 :
761 9391577 : enum svalue_kind get_kind () const final override { return SK_UNARYOP; }
762 : const unaryop_svalue *
763 945964 : dyn_cast_unaryop_svalue () const final override { return this; }
764 :
765 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
766 :
767 : void
768 : print_dump_widget_label (pretty_printer *pp) const final override;
769 : void
770 : add_dump_widget_children (text_art::tree_widget &w,
771 : const dump_widget_info &dwi) const final override;
772 :
773 : void accept (visitor *v) const final override;
774 : bool implicitly_live_p (const svalue_set *,
775 : const region_model *) const final override;
776 :
777 2685086 : enum tree_code get_op () const { return m_op; }
778 2836656 : const svalue *get_arg () const { return m_arg; }
779 :
780 : const svalue *
781 : maybe_fold_bits_within (tree type,
782 : const bit_range &subrange,
783 : region_model_manager *mgr) const final override;
784 :
785 : bool maybe_get_value_range_1 (value_range &out) const final override;
786 :
787 : private:
788 : enum tree_code m_op;
789 : const svalue *m_arg;
790 : };
791 :
792 : } // namespace ana
793 :
794 : template <>
795 : template <>
796 : inline bool
797 298340 : is_a_helper <const unaryop_svalue *>::test (const svalue *sval)
798 : {
799 298340 : return sval->get_kind () == SK_UNARYOP;
800 : }
801 :
802 : template <> struct default_hash_traits<unaryop_svalue::key_t>
803 : : public member_function_hash_traits<unaryop_svalue::key_t>
804 : {
805 : static const bool empty_zero_p = false;
806 : };
807 :
808 : namespace ana {
809 :
810 : /* Concrete subclass of svalue representing a binary operation of
811 : two svalues. */
812 :
813 : class binop_svalue : public svalue
814 : {
815 : public:
816 : /* A support class for uniquifying instances of binop_svalue. */
817 : struct key_t
818 : {
819 106873 : key_t (tree type, enum tree_code op,
820 : const svalue *arg0, const svalue *arg1)
821 106873 : : m_type (type), m_op (op), m_arg0 (arg0), m_arg1 (arg1)
822 : {}
823 :
824 754011 : hashval_t hash () const
825 : {
826 754011 : inchash::hash hstate;
827 754011 : hstate.add_ptr (m_type);
828 754011 : hstate.add_int (m_op);
829 754011 : hstate.add_ptr (m_arg0);
830 754011 : hstate.add_ptr (m_arg1);
831 754011 : return hstate.end ();
832 : }
833 :
834 758956 : bool operator== (const key_t &other) const
835 : {
836 758956 : return (m_type == other.m_type
837 329127 : && m_op == other.m_op
838 250345 : && m_arg0 == other.m_arg0
839 885379 : && m_arg1 == other.m_arg1);
840 : }
841 :
842 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
843 100428 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
844 840212 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
845 2689400 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
846 :
847 : tree m_type;
848 : enum tree_code m_op;
849 : const svalue *m_arg0;
850 : const svalue *m_arg1;
851 : };
852 :
853 20459 : binop_svalue (symbol::id_t id, tree type, enum tree_code op,
854 : const svalue *arg0, const svalue *arg1)
855 20459 : : svalue (complexity::from_pair (arg0->get_complexity (),
856 : arg1->get_complexity ()),
857 : id,
858 : type),
859 20459 : m_op (op), m_arg0 (arg0), m_arg1 (arg1)
860 : {
861 20459 : gcc_assert (arg0->can_have_associated_state_p ());
862 20459 : gcc_assert (arg1->can_have_associated_state_p ());
863 20459 : }
864 :
865 20487158 : enum svalue_kind get_kind () const final override { return SK_BINOP; }
866 136443 : const binop_svalue *dyn_cast_binop_svalue () const final override
867 : {
868 136443 : return this;
869 : }
870 :
871 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
872 :
873 : void
874 : print_dump_widget_label (pretty_printer *pp) const final override;
875 : void
876 : add_dump_widget_children (text_art::tree_widget &w,
877 : const dump_widget_info &dwi) const final override;
878 :
879 : void accept (visitor *v) const final override;
880 : bool implicitly_live_p (const svalue_set *,
881 : const region_model *) const final override;
882 :
883 : bool maybe_get_value_range_1 (value_range &out) const final override;
884 :
885 5245961 : enum tree_code get_op () const { return m_op; }
886 3441545 : const svalue *get_arg0 () const { return m_arg0; }
887 2250207 : const svalue *get_arg1 () const { return m_arg1; }
888 :
889 : private:
890 : enum tree_code m_op;
891 : const svalue *m_arg0;
892 : const svalue *m_arg1;
893 : };
894 :
895 : } // namespace ana
896 :
897 : template <>
898 : template <>
899 : inline bool
900 286521 : is_a_helper <const binop_svalue *>::test (const svalue *sval)
901 : {
902 286521 : return sval->get_kind () == SK_BINOP;
903 : }
904 :
905 : template <> struct default_hash_traits<binop_svalue::key_t>
906 : : public member_function_hash_traits<binop_svalue::key_t>
907 : {
908 : static const bool empty_zero_p = false;
909 : };
910 :
911 : namespace ana {
912 :
913 : /* Concrete subclass of svalue representing the result of accessing a subregion
914 : of another svalue (the value of a component/field of a struct, or an element
915 : from an array). */
916 :
917 : class sub_svalue : public svalue
918 : {
919 : public:
920 : /* A support class for uniquifying instances of sub_svalue. */
921 : struct key_t
922 : {
923 16185 : key_t (tree type, const svalue *parent_svalue, const region *subregion)
924 16185 : : m_type (type), m_parent_svalue (parent_svalue), m_subregion (subregion)
925 : {}
926 :
927 99341 : hashval_t hash () const
928 : {
929 99341 : inchash::hash hstate;
930 99341 : hstate.add_ptr (m_type);
931 99341 : hstate.add_ptr (m_parent_svalue);
932 99341 : hstate.add_ptr (m_subregion);
933 99341 : return hstate.end ();
934 : }
935 :
936 97434 : bool operator== (const key_t &other) const
937 : {
938 97434 : return (m_type == other.m_type
939 55041 : && m_parent_svalue == other.m_parent_svalue
940 136593 : && m_subregion == other.m_subregion);
941 : }
942 :
943 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
944 54810 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
945 109186 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
946 455245 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
947 :
948 : tree m_type;
949 : const svalue *m_parent_svalue;
950 : const region *m_subregion;
951 : };
952 : sub_svalue (symbol::id_t id, tree type, const svalue *parent_svalue,
953 : const region *subregion);
954 :
955 1410153 : enum svalue_kind get_kind () const final override { return SK_SUB; }
956 20667 : const sub_svalue *dyn_cast_sub_svalue () const final override
957 : {
958 20667 : return this;
959 : }
960 :
961 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
962 :
963 : void
964 : print_dump_widget_label (pretty_printer *pp) const final override;
965 : void
966 : add_dump_widget_children (text_art::tree_widget &w,
967 : const dump_widget_info &dwi) const final override;
968 :
969 : void accept (visitor *v) const final override;
970 : bool implicitly_live_p (const svalue_set *,
971 : const region_model *) const final override;
972 :
973 1018881 : const svalue *get_parent () const { return m_parent_svalue; }
974 808101 : const region *get_subregion () const { return m_subregion; }
975 :
976 : private:
977 : const svalue *m_parent_svalue;
978 : const region *m_subregion;
979 : };
980 :
981 : } // namespace ana
982 :
983 : template <>
984 : template <>
985 : inline bool
986 0 : is_a_helper <const sub_svalue *>::test (const svalue *sval)
987 : {
988 0 : return sval->get_kind () == SK_SUB;
989 : }
990 :
991 : template <> struct default_hash_traits<sub_svalue::key_t>
992 : : public member_function_hash_traits<sub_svalue::key_t>
993 : {
994 : static const bool empty_zero_p = false;
995 : };
996 :
997 : namespace ana {
998 :
999 : /* Concrete subclass of svalue representing repeating an inner svalue
1000 : (possibly not a whole number of times) to fill a larger region of
1001 : type TYPE of size OUTER_SIZE bytes. */
1002 :
1003 : class repeated_svalue : public svalue
1004 : {
1005 : public:
1006 : /* A support class for uniquifying instances of repeated_svalue. */
1007 : struct key_t
1008 : {
1009 2016 : key_t (tree type,
1010 : const svalue *outer_size,
1011 : const svalue *inner_svalue)
1012 2016 : : m_type (type), m_outer_size (outer_size), m_inner_svalue (inner_svalue)
1013 : {}
1014 :
1015 10006 : hashval_t hash () const
1016 : {
1017 10006 : inchash::hash hstate;
1018 10006 : hstate.add_ptr (m_type);
1019 10006 : hstate.add_ptr (m_outer_size);
1020 10006 : hstate.add_ptr (m_inner_svalue);
1021 10006 : return hstate.end ();
1022 : }
1023 :
1024 8609 : bool operator== (const key_t &other) const
1025 : {
1026 8609 : return (m_type == other.m_type
1027 8481 : && m_outer_size == other.m_outer_size
1028 10168 : && m_inner_svalue == other.m_inner_svalue);
1029 : }
1030 :
1031 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1032 52275 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
1033 10655 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1034 147231 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
1035 :
1036 : tree m_type;
1037 : const svalue *m_outer_size;
1038 : const svalue *m_inner_svalue;
1039 : };
1040 : repeated_svalue (symbol::id_t id,
1041 : tree type,
1042 : const svalue *outer_size,
1043 : const svalue *inner_svalue);
1044 :
1045 149133 : enum svalue_kind get_kind () const final override { return SK_REPEATED; }
1046 100 : const repeated_svalue *dyn_cast_repeated_svalue () const final override
1047 : {
1048 100 : return this;
1049 : }
1050 :
1051 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1052 :
1053 : void
1054 : print_dump_widget_label (pretty_printer *pp) const final override;
1055 : void
1056 : add_dump_widget_children (text_art::tree_widget &w,
1057 : const dump_widget_info &dwi) const final override;
1058 :
1059 : void accept (visitor *v) const final override;
1060 :
1061 54 : const svalue *get_outer_size () const { return m_outer_size; }
1062 457 : const svalue *get_inner_svalue () const { return m_inner_svalue; }
1063 :
1064 : bool all_zeroes_p () const final override;
1065 :
1066 : const svalue *
1067 : maybe_fold_bits_within (tree type,
1068 : const bit_range &subrange,
1069 : region_model_manager *mgr) const final override;
1070 :
1071 : private:
1072 : const svalue *m_outer_size;
1073 : const svalue *m_inner_svalue;
1074 : };
1075 :
1076 : } // namespace ana
1077 :
1078 : template <>
1079 : template <>
1080 : inline bool
1081 42 : is_a_helper <const repeated_svalue *>::test (const svalue *sval)
1082 : {
1083 42 : return sval->get_kind () == SK_REPEATED;
1084 : }
1085 :
1086 : template <> struct default_hash_traits<repeated_svalue::key_t>
1087 : : public member_function_hash_traits<repeated_svalue::key_t>
1088 : {
1089 : static const bool empty_zero_p = false;
1090 : };
1091 :
1092 : namespace ana {
1093 :
1094 : /* A range of bits/bytes within another svalue
1095 : e.g. bytes 5-39 of INITIAL_SVALUE(R).
1096 : These can be generated for prefixes and suffixes when part of a binding
1097 : is clobbered, so that we don't lose too much information. */
1098 :
1099 : class bits_within_svalue : public svalue
1100 : {
1101 : public:
1102 : /* A support class for uniquifying instances of bits_within_svalue. */
1103 : struct key_t
1104 : {
1105 1506 : key_t (tree type,
1106 : const bit_range &bits,
1107 : const svalue *inner_svalue)
1108 1506 : : m_type (type), m_bits (bits), m_inner_svalue (inner_svalue)
1109 : {}
1110 :
1111 9940 : hashval_t hash () const
1112 : {
1113 9940 : inchash::hash hstate;
1114 9940 : hstate.add_ptr (m_type);
1115 9940 : hstate.add_ptr (m_inner_svalue);
1116 9940 : return hstate.end ();
1117 : }
1118 :
1119 10495 : bool operator== (const key_t &other) const
1120 : {
1121 10495 : return (m_type == other.m_type
1122 8669 : && m_bits == other.m_bits
1123 11887 : && m_inner_svalue == other.m_inner_svalue);
1124 : }
1125 :
1126 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1127 53181 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
1128 15903 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1129 156886 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
1130 :
1131 : tree m_type;
1132 : bit_range m_bits;
1133 : const svalue *m_inner_svalue;
1134 : };
1135 : bits_within_svalue (symbol::id_t id,
1136 : tree type,
1137 : const bit_range &bits,
1138 : const svalue *inner_svalue);
1139 :
1140 183553 : enum svalue_kind get_kind () const final override { return SK_BITS_WITHIN; }
1141 : const bits_within_svalue *
1142 0 : dyn_cast_bits_within_svalue () const final override
1143 : {
1144 0 : return this;
1145 : }
1146 :
1147 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1148 :
1149 : void
1150 : print_dump_widget_label (pretty_printer *pp) const final override;
1151 : void
1152 : add_dump_widget_children (text_art::tree_widget &w,
1153 : const dump_widget_info &dwi) const final override;
1154 :
1155 : void accept (visitor *v) const final override;
1156 : bool implicitly_live_p (const svalue_set *,
1157 : const region_model *) const final override;
1158 :
1159 456 : const bit_range &get_bits () const { return m_bits; }
1160 81 : const svalue *get_inner_svalue () const { return m_inner_svalue; }
1161 :
1162 : const svalue *
1163 : maybe_fold_bits_within (tree type,
1164 : const bit_range &subrange,
1165 : region_model_manager *mgr) const final override;
1166 :
1167 : private:
1168 : const bit_range m_bits;
1169 : const svalue *m_inner_svalue;
1170 : };
1171 :
1172 : } // namespace ana
1173 :
1174 : template <>
1175 : template <>
1176 : inline bool
1177 0 : is_a_helper <const bits_within_svalue *>::test (const svalue *sval)
1178 : {
1179 0 : return sval->get_kind () == SK_BITS_WITHIN;
1180 : }
1181 :
1182 : template <> struct default_hash_traits<bits_within_svalue::key_t>
1183 : : public member_function_hash_traits<bits_within_svalue::key_t>
1184 : {
1185 : static const bool empty_zero_p = false;
1186 : };
1187 :
1188 : namespace ana {
1189 :
1190 : /* Concrete subclass of svalue: decorate another svalue,
1191 : so that the resulting svalue can be identified as being
1192 : "interesting to control flow".
1193 : For example, consider the return value from setjmp. We
1194 : don't want to merge states in which the result is 0 with
1195 : those in which the result is non-zero. By using an
1196 : unmergeable_svalue for the result, we can inhibit such merges
1197 : and have separate exploded nodes for those states, keeping
1198 : the first and second returns from setjmp distinct in the exploded
1199 : graph. */
1200 :
1201 : class unmergeable_svalue : public svalue
1202 : {
1203 : public:
1204 210 : unmergeable_svalue (symbol::id_t id, const svalue *arg)
1205 210 : : svalue (complexity (arg), id, arg->get_type ()), m_arg (arg)
1206 : {
1207 210 : }
1208 :
1209 22591 : enum svalue_kind get_kind () const final override { return SK_UNMERGEABLE; }
1210 : const unmergeable_svalue *
1211 4370 : dyn_cast_unmergeable_svalue () const final override { return this; }
1212 :
1213 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1214 :
1215 : void
1216 : print_dump_widget_label (pretty_printer *pp) const final override;
1217 : void
1218 : add_dump_widget_children (text_art::tree_widget &w,
1219 : const dump_widget_info &dwi) const final override;
1220 :
1221 : void accept (visitor *v) const final override;
1222 : bool implicitly_live_p (const svalue_set *,
1223 : const region_model *) const final override;
1224 :
1225 5264 : const svalue *get_arg () const { return m_arg; }
1226 :
1227 : private:
1228 : const svalue *m_arg;
1229 : };
1230 :
1231 : } // namespace ana
1232 :
1233 : template <>
1234 : template <>
1235 : inline bool
1236 0 : is_a_helper <const unmergeable_svalue *>::test (const svalue *sval)
1237 : {
1238 0 : return sval->get_kind () == SK_UNMERGEABLE;
1239 : }
1240 :
1241 : namespace ana {
1242 :
1243 : /* Concrete subclass of svalue for use in selftests, where
1244 : we want a specific but unknown svalue.
1245 : Unlike other svalue subclasses these aren't managed by
1246 : region_model_manager. */
1247 :
1248 28 : class placeholder_svalue : public svalue
1249 : {
1250 : public:
1251 12455 : placeholder_svalue (symbol::id_t id, tree type, const char *name)
1252 12455 : : svalue (complexity (1, 1), id, type), m_name (name)
1253 : {
1254 : }
1255 :
1256 33887 : enum svalue_kind get_kind () const final override { return SK_PLACEHOLDER; }
1257 :
1258 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1259 :
1260 : void
1261 : print_dump_widget_label (pretty_printer *pp) const final override;
1262 : void
1263 : add_dump_widget_children (text_art::tree_widget &w,
1264 : const dump_widget_info &dwi) const final override;
1265 :
1266 : void accept (visitor *v) const final override;
1267 :
1268 0 : const char *get_name () const { return m_name; }
1269 :
1270 : private:
1271 : const char *m_name;
1272 : };
1273 :
1274 : } // namespace ana
1275 :
1276 : template <>
1277 : template <>
1278 : inline bool
1279 : is_a_helper <const placeholder_svalue *>::test (const svalue *sval)
1280 : {
1281 : return sval->get_kind () == SK_PLACEHOLDER;
1282 : }
1283 :
1284 : namespace ana {
1285 :
1286 : /* Concrete subclass of svalue representing a "widening" seen when merging
1287 : states, widening from a base value to {base value, iter value} and thus
1288 : representing a possible fixed point in an iteration from the base to
1289 : +ve infinity, or -ve infinity, and thus useful for representing a value
1290 : within a loop.
1291 : We also need to capture the program_point at which the merger happens,
1292 : so that distinguish between different iterators, and thus handle
1293 : nested loops. (currently we capture the function_point instead, for
1294 : simplicity of hashing). */
1295 :
1296 : class widening_svalue : public svalue
1297 : {
1298 : public:
1299 : /* A support class for uniquifying instances of widening_svalue. */
1300 : struct key_t
1301 : {
1302 5761 : key_t (tree type, const supernode *snode,
1303 : const svalue *base_sval, const svalue *iter_sval)
1304 5761 : : m_type (type), m_snode (snode),
1305 5761 : m_base_sval (base_sval), m_iter_sval (iter_sval)
1306 : {}
1307 :
1308 35276 : hashval_t hash () const
1309 : {
1310 35276 : inchash::hash hstate;
1311 35276 : hstate.add_ptr (m_base_sval);
1312 35276 : hstate.add_ptr (m_iter_sval);
1313 35276 : return hstate.end ();
1314 : }
1315 :
1316 71139 : bool operator== (const key_t &other) const
1317 : {
1318 71139 : return (m_type == other.m_type
1319 59939 : && m_snode == other.m_snode
1320 4607 : && m_base_sval == other.m_base_sval
1321 74753 : && m_iter_sval == other.m_iter_sval);
1322 : }
1323 :
1324 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1325 53681 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
1326 96447 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1327 366936 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
1328 :
1329 : tree m_type;
1330 : const supernode *m_snode;
1331 : const svalue *m_base_sval;
1332 : const svalue *m_iter_sval;
1333 : };
1334 :
1335 : enum direction_t
1336 : {
1337 : DIR_ASCENDING,
1338 : DIR_DESCENDING,
1339 : DIR_UNKNOWN
1340 : };
1341 :
1342 2355 : widening_svalue (symbol::id_t id, tree type, const supernode *snode,
1343 : const svalue *base_sval, const svalue *iter_sval)
1344 2355 : : svalue (complexity::from_pair (base_sval->get_complexity (),
1345 : iter_sval->get_complexity ()),
1346 : id,
1347 : type),
1348 2355 : m_snode (snode),
1349 2355 : m_base_sval (base_sval), m_iter_sval (iter_sval)
1350 : {
1351 2355 : gcc_assert (base_sval->can_have_associated_state_p ());
1352 2355 : gcc_assert (iter_sval->can_have_associated_state_p ());
1353 2355 : }
1354 :
1355 1071880 : enum svalue_kind get_kind () const final override { return SK_WIDENING; }
1356 19000 : const widening_svalue *dyn_cast_widening_svalue () const final override
1357 : {
1358 19000 : return this;
1359 : }
1360 :
1361 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1362 :
1363 : void
1364 : print_dump_widget_label (pretty_printer *pp) const final override;
1365 : void
1366 : add_dump_widget_children (text_art::tree_widget &w,
1367 : const dump_widget_info &dwi) const final override;
1368 :
1369 : void accept (visitor *v) const final override;
1370 :
1371 3593 : const supernode *get_snode () const { return m_snode; }
1372 14294 : const svalue *get_base_svalue () const { return m_base_sval; }
1373 4969 : const svalue *get_iter_svalue () const { return m_iter_sval; }
1374 :
1375 : enum direction_t get_direction () const;
1376 :
1377 : tristate eval_condition_without_cm (enum tree_code op,
1378 : tree rhs_cst) const;
1379 :
1380 : private:
1381 : const supernode *m_snode;
1382 : const svalue *m_base_sval;
1383 : const svalue *m_iter_sval;
1384 : };
1385 :
1386 : } // namespace ana
1387 :
1388 : template <>
1389 : template <>
1390 : inline bool
1391 454 : is_a_helper <const widening_svalue *>::test (const svalue *sval)
1392 : {
1393 454 : return sval->get_kind () == SK_WIDENING;
1394 : }
1395 :
1396 : template <> struct default_hash_traits<widening_svalue::key_t>
1397 : : public member_function_hash_traits<widening_svalue::key_t>
1398 : {
1399 : static const bool empty_zero_p = false;
1400 : };
1401 :
1402 : namespace ana {
1403 :
1404 : /* Concrete subclass of svalue representing a mapping of bit-ranges
1405 : to svalues, analogous to a cluster within the store, but without
1406 : symbolic keys.
1407 :
1408 : This is for use in places where we want to represent a store-like
1409 : mapping, but are required to use an svalue, such as when handling
1410 : compound assignments and compound return values.
1411 :
1412 : Instances of this class shouldn't be bound as-is into the store;
1413 : instead they should be unpacked. Similarly, they should not be
1414 : nested. */
1415 :
1416 : class compound_svalue : public svalue
1417 : {
1418 : public:
1419 : typedef concrete_binding_map::const_iterator const_iterator_t;
1420 : typedef concrete_binding_map::iterator iterator_t;
1421 :
1422 : /* A support class for uniquifying instances of compound_svalue.
1423 : Note that to avoid copies, keys store pointers to
1424 : concrete_binding_map, rather than the maps themselves. */
1425 : struct key_t
1426 : {
1427 4389 : key_t (tree type, const concrete_binding_map *map_ptr)
1428 3777 : : m_type (type), m_map_ptr (map_ptr)
1429 : {}
1430 :
1431 16098 : hashval_t hash () const
1432 : {
1433 16098 : inchash::hash hstate;
1434 16098 : hstate.add_ptr (m_type);
1435 : //hstate.add_ptr (m_map_ptr); // TODO
1436 16098 : return hstate.end ();
1437 : }
1438 :
1439 21046 : bool operator== (const key_t &other) const
1440 : {
1441 21046 : return (m_type == other.m_type
1442 21046 : && *m_map_ptr == *other.m_map_ptr);
1443 : }
1444 :
1445 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1446 52060 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
1447 30259 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1448 202465 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
1449 :
1450 : tree m_type;
1451 : const concrete_binding_map *m_map_ptr;
1452 : };
1453 :
1454 : compound_svalue (symbol::id_t id, tree type, concrete_binding_map &&map);
1455 : compound_svalue (symbol::id_t id, tree type, const concrete_binding_map &map);
1456 :
1457 6929 : enum svalue_kind get_kind () const final override { return SK_COMPOUND; }
1458 4027 : const compound_svalue *dyn_cast_compound_svalue () const final override
1459 : {
1460 4027 : return this;
1461 : }
1462 :
1463 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1464 :
1465 : void
1466 : print_dump_widget_label (pretty_printer *pp) const final override;
1467 : void
1468 : add_dump_widget_children (text_art::tree_widget &w,
1469 : const dump_widget_info &dwi) const final override;
1470 :
1471 : void accept (visitor *v) const final override;
1472 :
1473 : const concrete_binding_map &
1474 137 : get_concrete_bindings () const { return m_map; }
1475 :
1476 4216 : const_iterator_t begin () const { return m_map.begin (); }
1477 14335 : const_iterator_t end () const { return m_map.end (); }
1478 612 : iterator_t begin () { return m_map.begin (); }
1479 612 : iterator_t end () { return m_map.end (); }
1480 :
1481 612 : struct key_t make_key () const
1482 : {
1483 612 : return key_t (get_type (), &m_map);
1484 : }
1485 :
1486 : const svalue *
1487 : maybe_fold_bits_within (tree type,
1488 : const bit_range &subrange,
1489 : region_model_manager *mgr) const final override;
1490 :
1491 : private:
1492 : concrete_binding_map m_map;
1493 : };
1494 :
1495 : } // namespace ana
1496 :
1497 : template <>
1498 : template <>
1499 : inline bool
1500 293 : is_a_helper <const compound_svalue *>::test (const svalue *sval)
1501 : {
1502 293 : return sval->get_kind () == SK_COMPOUND;
1503 : }
1504 :
1505 : template <> struct default_hash_traits<compound_svalue::key_t>
1506 : : public member_function_hash_traits<compound_svalue::key_t>
1507 : {
1508 : static const bool empty_zero_p = false;
1509 : };
1510 :
1511 : namespace ana {
1512 :
1513 : /* A bundle of state for purging information from a program_state about
1514 : a conjured_svalue. We pass this whenever calling
1515 : get_or_create_conjured_svalue, so that if the program_state already
1516 : has information about this conjured_svalue on an execution path, we
1517 : can purge that information, to avoid the analyzer confusing the two
1518 : values as being the same. */
1519 :
1520 : class conjured_purge
1521 : {
1522 : public:
1523 42358 : conjured_purge (region_model *model, region_model_context *ctxt)
1524 42210 : : m_model (model), m_ctxt (ctxt)
1525 : {
1526 : }
1527 : void purge (const conjured_svalue *sval) const;
1528 :
1529 : private:
1530 : region_model *m_model;
1531 : region_model_context *m_ctxt;
1532 : };
1533 :
1534 : /* A defined value arising from a statement, where we want to identify a
1535 : particular unknown value, rather than resorting to the unknown_value
1536 : singleton, so that the value can have sm-state.
1537 :
1538 : Comparisons of variables that share the same conjured_svalue are known
1539 : to be equal, even if we don't know what the value is.
1540 :
1541 : For example, this is used for the values of regions that may have been
1542 : touched when calling an unknown function.
1543 :
1544 : The value captures a region as well as a stmt in order to avoid falsely
1545 : aliasing the various values that could arise in one statement. For
1546 : example, after:
1547 : unknown_fn (&a, &b);
1548 : we want values to clobber a and b with, but we don't want to use the
1549 : same value, or it would falsely implicitly assume that a == b. */
1550 :
1551 : class conjured_svalue : public svalue
1552 : {
1553 : public:
1554 : /* A support class for uniquifying instances of conjured_svalue. */
1555 : struct key_t
1556 : {
1557 56293 : key_t (tree type, const gimple *stmt, const region *id_reg, unsigned idx)
1558 56293 : : m_type (type), m_stmt (stmt), m_id_reg (id_reg), m_idx (idx)
1559 : {}
1560 :
1561 482298 : hashval_t hash () const
1562 : {
1563 482298 : inchash::hash hstate;
1564 482298 : hstate.add_ptr (m_type);
1565 482298 : hstate.add_ptr (m_stmt);
1566 482298 : hstate.add_ptr (m_id_reg);
1567 482298 : return hstate.end ();
1568 : }
1569 :
1570 484029 : bool operator== (const key_t &other) const
1571 : {
1572 484029 : return (m_type == other.m_type
1573 210649 : && m_stmt == other.m_stmt
1574 50261 : && m_id_reg == other.m_id_reg
1575 524200 : && m_idx == other.m_idx);
1576 : }
1577 :
1578 : /* Use m_stmt to mark empty/deleted, as m_type can be NULL_TREE for
1579 : legitimate instances. */
1580 : void mark_deleted () { m_stmt = reinterpret_cast<const gimple *> (1); }
1581 0 : void mark_empty () { m_stmt = nullptr; }
1582 579415 : bool is_deleted () const
1583 : {
1584 579415 : return m_stmt == reinterpret_cast<const gimple *> (1);
1585 : }
1586 1936553 : bool is_empty () const { return m_stmt == nullptr; }
1587 :
1588 : tree m_type;
1589 : const gimple *m_stmt;
1590 : const region *m_id_reg;
1591 : unsigned m_idx;
1592 : };
1593 :
1594 26295 : conjured_svalue (symbol::id_t id, tree type, const gimple *stmt,
1595 : const region *id_reg, unsigned idx)
1596 26295 : : svalue (complexity (id_reg), id, type),
1597 26295 : m_stmt (stmt), m_id_reg (id_reg), m_idx (idx)
1598 : {
1599 26295 : gcc_assert (m_stmt != nullptr);
1600 26295 : }
1601 :
1602 21778729 : enum svalue_kind get_kind () const final override { return SK_CONJURED; }
1603 0 : const conjured_svalue *dyn_cast_conjured_svalue () const final override
1604 : {
1605 0 : return this;
1606 : }
1607 :
1608 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1609 :
1610 : void
1611 : print_dump_widget_label (pretty_printer *pp) const final override;
1612 : void
1613 : add_dump_widget_children (text_art::tree_widget &w,
1614 : const dump_widget_info &dwi) const final override;
1615 :
1616 : void accept (visitor *v) const final override;
1617 :
1618 3183195 : const gimple *get_stmt () const { return m_stmt; }
1619 74396 : const region *get_id_region () const { return m_id_reg; }
1620 : bool lhs_value_p () const;
1621 :
1622 : private:
1623 : const gimple *m_stmt;
1624 : const region *m_id_reg;
1625 : unsigned m_idx;
1626 : };
1627 :
1628 : } // namespace ana
1629 :
1630 : template <>
1631 : template <>
1632 : inline bool
1633 : is_a_helper <const conjured_svalue *>::test (const svalue *sval)
1634 : {
1635 : return sval->get_kind () == SK_CONJURED;
1636 : }
1637 :
1638 : template <> struct default_hash_traits<conjured_svalue::key_t>
1639 : : public member_function_hash_traits<conjured_svalue::key_t>
1640 : {
1641 : static const bool empty_zero_p = true;
1642 : };
1643 :
1644 : namespace ana {
1645 :
1646 : /* An output from a deterministic asm stmt, where we want to identify a
1647 : particular unknown value, rather than resorting to the unknown_value
1648 : singleton.
1649 :
1650 : Comparisons of variables that share the same asm_output_svalue are known
1651 : to be equal, even if we don't know what the value is. */
1652 :
1653 : class asm_output_svalue : public svalue
1654 : {
1655 : public:
1656 : /* Imposing an upper limit and using a (small) array allows key_t
1657 : to avoid memory management. */
1658 : static const unsigned MAX_INPUTS = 2;
1659 :
1660 : /* A support class for uniquifying instances of asm_output_svalue. */
1661 : struct key_t
1662 : {
1663 358 : key_t (tree type,
1664 : const char *asm_string,
1665 : unsigned output_idx,
1666 : const vec<const svalue *> &inputs)
1667 358 : : m_type (type), m_asm_string (asm_string), m_output_idx (output_idx),
1668 358 : m_num_inputs (inputs.length ())
1669 : {
1670 358 : gcc_assert (inputs.length () <= MAX_INPUTS);
1671 958 : for (unsigned i = 0; i < m_num_inputs; i++)
1672 600 : m_input_arr[i] = inputs[i];
1673 358 : }
1674 :
1675 1594 : hashval_t hash () const
1676 : {
1677 1594 : inchash::hash hstate;
1678 1594 : hstate.add_ptr (m_type);
1679 : /* We don't bother hashing m_asm_str. */
1680 1594 : hstate.add_int (m_output_idx);
1681 4381 : for (unsigned i = 0; i < m_num_inputs; i++)
1682 2787 : hstate.add_ptr (m_input_arr[i]);
1683 1594 : return hstate.end ();
1684 : }
1685 :
1686 1210 : bool operator== (const key_t &other) const
1687 : {
1688 1210 : if (!(m_type == other.m_type
1689 933 : && 0 == (strcmp (m_asm_string, other.m_asm_string))
1690 827 : && m_output_idx == other.m_output_idx
1691 651 : && m_num_inputs == other.m_num_inputs))
1692 : return false;
1693 1148 : for (unsigned i = 0; i < m_num_inputs; i++)
1694 982 : if (m_input_arr[i] != other.m_input_arr[i])
1695 : return false;
1696 : return true;
1697 : }
1698 :
1699 : /* Use m_asm_string to mark empty/deleted, as m_type can be NULL_TREE for
1700 : legitimate instances. */
1701 : void mark_deleted () { m_asm_string = reinterpret_cast<const char *> (1); }
1702 0 : void mark_empty () { m_asm_string = nullptr; }
1703 1731 : bool is_deleted () const
1704 : {
1705 1731 : return m_asm_string == reinterpret_cast<const char *> (1);
1706 : }
1707 112410 : bool is_empty () const { return m_asm_string == nullptr; }
1708 :
1709 : tree m_type;
1710 : const char *m_asm_string;
1711 : unsigned m_output_idx;
1712 : unsigned m_num_inputs;
1713 : const svalue *m_input_arr[MAX_INPUTS];
1714 : };
1715 :
1716 192 : asm_output_svalue (symbol::id_t id,
1717 : tree type,
1718 : const char *asm_string,
1719 : unsigned output_idx,
1720 : unsigned num_outputs,
1721 : const vec<const svalue *> &inputs)
1722 192 : : svalue (complexity::from_vec_svalue (inputs), id, type),
1723 192 : m_asm_string (asm_string),
1724 192 : m_output_idx (output_idx),
1725 192 : m_num_outputs (num_outputs),
1726 192 : m_num_inputs (inputs.length ())
1727 : {
1728 192 : gcc_assert (inputs.length () <= MAX_INPUTS);
1729 488 : for (unsigned i = 0; i < m_num_inputs; i++)
1730 296 : m_input_arr[i] = inputs[i];
1731 192 : }
1732 :
1733 18490 : enum svalue_kind get_kind () const final override { return SK_ASM_OUTPUT; }
1734 : const asm_output_svalue *
1735 0 : dyn_cast_asm_output_svalue () const final override
1736 : {
1737 0 : return this;
1738 : }
1739 :
1740 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1741 :
1742 : void
1743 : print_dump_widget_label (pretty_printer *pp) const final override;
1744 : void
1745 : add_dump_widget_children (text_art::tree_widget &w,
1746 : const dump_widget_info &dwi) const final override;
1747 :
1748 : void accept (visitor *v) const final override;
1749 :
1750 102 : const char *get_asm_string () const { return m_asm_string; }
1751 154 : unsigned get_output_idx () const { return m_output_idx; }
1752 78 : unsigned get_num_outputs () const { return m_num_outputs; }
1753 312 : unsigned get_num_inputs () const { return m_num_inputs; }
1754 164 : const svalue *get_input (unsigned idx) const { return m_input_arr[idx]; }
1755 :
1756 : private:
1757 : void dump_input (pretty_printer *pp,
1758 : unsigned input_idx,
1759 : const svalue *sval,
1760 : bool simple) const;
1761 : unsigned input_idx_to_asm_idx (unsigned input_idx) const;
1762 :
1763 : const char *m_asm_string;
1764 : unsigned m_output_idx;
1765 :
1766 : /* We capture this so that we can offset the input indices
1767 : to match the %0, %1, %2 in the asm_string when dumping. */
1768 : unsigned m_num_outputs;
1769 :
1770 : unsigned m_num_inputs;
1771 : const svalue *m_input_arr[MAX_INPUTS];
1772 : };
1773 :
1774 : } // namespace ana
1775 :
1776 : template <>
1777 : template <>
1778 : inline bool
1779 8 : is_a_helper <const asm_output_svalue *>::test (const svalue *sval)
1780 : {
1781 8 : return sval->get_kind () == SK_ASM_OUTPUT;
1782 : }
1783 :
1784 : template <> struct default_hash_traits<asm_output_svalue::key_t>
1785 : : public member_function_hash_traits<asm_output_svalue::key_t>
1786 : {
1787 : static const bool empty_zero_p = true;
1788 : };
1789 :
1790 : namespace ana {
1791 :
1792 : /* The return value from a function with __attribute((const)) for given
1793 : inputs, provided that we don't have too many inputs, and all of them
1794 : are deterministic.
1795 :
1796 : Comparisons of variables that share the same const_fn_result_svalue are known
1797 : to be equal, even if we don't know what the value is. */
1798 :
1799 : class const_fn_result_svalue : public svalue
1800 : {
1801 : public:
1802 : /* Imposing an upper limit and using a (small) array allows key_t
1803 : to avoid memory management. */
1804 : static const unsigned MAX_INPUTS = 2;
1805 :
1806 : /* A support class for uniquifying instances of const_fn_result_svalue. */
1807 : struct key_t
1808 : {
1809 955 : key_t (tree type,
1810 : tree fndecl,
1811 : const vec<const svalue *> &inputs)
1812 955 : : m_type (type), m_fndecl (fndecl),
1813 955 : m_num_inputs (inputs.length ())
1814 : {
1815 955 : gcc_assert (inputs.length () <= MAX_INPUTS);
1816 1421 : for (unsigned i = 0; i < m_num_inputs; i++)
1817 466 : m_input_arr[i] = inputs[i];
1818 955 : }
1819 :
1820 3118 : hashval_t hash () const
1821 : {
1822 3118 : inchash::hash hstate;
1823 3118 : hstate.add_ptr (m_type);
1824 3118 : hstate.add_ptr (m_fndecl);
1825 5603 : for (unsigned i = 0; i < m_num_inputs; i++)
1826 2485 : hstate.add_ptr (m_input_arr[i]);
1827 3118 : return hstate.end ();
1828 : }
1829 :
1830 2304 : bool operator== (const key_t &other) const
1831 : {
1832 2304 : if (!(m_type == other.m_type
1833 2190 : && m_fndecl == other.m_fndecl
1834 1594 : && m_num_inputs == other.m_num_inputs))
1835 : return false;
1836 1974 : for (unsigned i = 0; i < m_num_inputs; i++)
1837 1206 : if (m_input_arr[i] != other.m_input_arr[i])
1838 : return false;
1839 : return true;
1840 : }
1841 :
1842 : /* Use m_fndecl to mark empty/deleted. */
1843 : void mark_deleted () { m_fndecl = reinterpret_cast<tree> (1); }
1844 0 : void mark_empty () { m_fndecl = NULL_TREE; }
1845 3330 : bool is_deleted () const
1846 : {
1847 3330 : return m_fndecl == reinterpret_cast<tree> (1);
1848 : }
1849 121596 : bool is_empty () const { return m_fndecl == NULL_TREE; }
1850 :
1851 : tree m_type;
1852 : tree m_fndecl;
1853 : unsigned m_num_inputs;
1854 : const svalue *m_input_arr[MAX_INPUTS];
1855 : };
1856 :
1857 187 : const_fn_result_svalue (symbol::id_t id,
1858 : tree type,
1859 : tree fndecl,
1860 : const vec<const svalue *> &inputs)
1861 187 : : svalue (complexity::from_vec_svalue (inputs), id, type),
1862 187 : m_fndecl (fndecl),
1863 187 : m_num_inputs (inputs.length ())
1864 : {
1865 187 : gcc_assert (inputs.length () <= MAX_INPUTS);
1866 359 : for (unsigned i = 0; i < m_num_inputs; i++)
1867 172 : m_input_arr[i] = inputs[i];
1868 187 : }
1869 :
1870 39072 : enum svalue_kind get_kind () const final override
1871 : {
1872 39072 : return SK_CONST_FN_RESULT;
1873 : }
1874 : const const_fn_result_svalue *
1875 0 : dyn_cast_const_fn_result_svalue () const final override
1876 : {
1877 0 : return this;
1878 : }
1879 :
1880 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1881 :
1882 : void
1883 : print_dump_widget_label (pretty_printer *pp) const final override;
1884 : void
1885 : add_dump_widget_children (text_art::tree_widget &w,
1886 : const dump_widget_info &dwi) const final override;
1887 :
1888 : void accept (visitor *v) const final override;
1889 :
1890 146 : tree get_fndecl () const { return m_fndecl; }
1891 258 : unsigned get_num_inputs () const { return m_num_inputs; }
1892 114 : const svalue *get_input (unsigned idx) const { return m_input_arr[idx]; }
1893 :
1894 : private:
1895 : void dump_input (pretty_printer *pp,
1896 : unsigned input_idx,
1897 : const svalue *sval,
1898 : bool simple) const;
1899 :
1900 : tree m_fndecl;
1901 : unsigned m_num_inputs;
1902 : const svalue *m_input_arr[MAX_INPUTS];
1903 : };
1904 :
1905 : } // namespace ana
1906 :
1907 : template <>
1908 : template <>
1909 : inline bool
1910 2 : is_a_helper <const const_fn_result_svalue *>::test (const svalue *sval)
1911 : {
1912 2 : return sval->get_kind () == SK_CONST_FN_RESULT;
1913 : }
1914 :
1915 : template <> struct default_hash_traits<const_fn_result_svalue::key_t>
1916 : : public member_function_hash_traits<const_fn_result_svalue::key_t>
1917 : {
1918 : static const bool empty_zero_p = true;
1919 : };
1920 :
1921 : #endif /* GCC_ANALYZER_SVALUE_H */
|
