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 55801883 : 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 13904996 : dyn_cast_region_svalue () const { return nullptr; }
116 : virtual const constant_svalue *
117 9476060 : dyn_cast_constant_svalue () const { return nullptr; }
118 : virtual const poisoned_svalue *
119 1986536 : 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 3946553 : dyn_cast_initial_svalue () const { return nullptr; }
124 : virtual const unaryop_svalue *
125 12291092 : dyn_cast_unaryop_svalue () const { return nullptr; }
126 : virtual const binop_svalue *
127 1100864 : dyn_cast_binop_svalue () const { return nullptr; }
128 : virtual const sub_svalue *
129 3640963 : dyn_cast_sub_svalue () const { return nullptr; }
130 : virtual const repeated_svalue *
131 15894 : 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 17093240 : dyn_cast_unmergeable_svalue () const { return nullptr; }
136 : virtual const widening_svalue *
137 478966 : dyn_cast_widening_svalue () const { return nullptr; }
138 : virtual const compound_svalue *
139 13013410 : 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 2316146 : 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 198528 : maybe_get_value_range (value_range &out) const
197 : {
198 198528 : if (maybe_get_value_range_1 (out))
199 : {
200 145104 : gcc_assert (!out.undefined_p ());
201 : return true;
202 : }
203 : return false;
204 : }
205 :
206 : protected:
207 198107 : svalue (complexity c, symbol::id_t id, tree type)
208 88676 : : 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 962698 : key_t (tree type, const region *reg)
235 962698 : : m_type (type), m_reg (reg)
236 : {}
237 :
238 4986371 : hashval_t hash () const
239 : {
240 4986371 : inchash::hash hstate;
241 4986371 : hstate.add_ptr (m_type);
242 4986371 : hstate.add_ptr (m_reg);
243 4986371 : return hstate.end ();
244 : }
245 :
246 4786490 : bool operator== (const key_t &other) const
247 : {
248 4786490 : return (m_type == other.m_type && m_reg == other.m_reg);
249 : }
250 :
251 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
252 95983 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
253 5397436 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
254 17893495 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
255 :
256 : tree m_type;
257 : const region *m_reg;
258 : };
259 :
260 25168 : region_svalue (symbol::id_t id, tree type, const region *reg)
261 25168 : : svalue (complexity (reg), id, type),
262 25168 : m_reg (reg)
263 : {
264 25168 : gcc_assert (m_reg != nullptr);
265 25168 : }
266 :
267 12039423 : enum svalue_kind get_kind () const final override { return SK_REGION; }
268 : const region_svalue *
269 2040327 : 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 3878149 : 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 58346 : is_a_helper <const region_svalue *>::test (const svalue *sval)
299 : {
300 58346 : 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 2510142 : key_t (tree type, tree cst)
322 2510142 : : m_type (type), m_cst (cst)
323 : {}
324 :
325 15440732 : hashval_t hash () const
326 : {
327 15440732 : inchash::hash hstate;
328 15440732 : hstate.add_ptr (m_type);
329 15440732 : hstate.add_ptr (m_cst);
330 15440732 : return hstate.end ();
331 : }
332 :
333 15576225 : bool operator== (const key_t &other) const
334 : {
335 15576225 : return (m_type == other.m_type && m_cst == other.m_cst);
336 : }
337 :
338 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
339 174634 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
340 16240802 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
341 48270706 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
342 :
343 : tree m_type;
344 : tree m_cst;
345 : };
346 :
347 55891 : constant_svalue (symbol::id_t id, tree type, tree cst_expr)
348 55891 : : svalue (complexity (1, 1), id, type),
349 55891 : m_cst_expr (cst_expr)
350 : {
351 55891 : gcc_assert (cst_expr);
352 55891 : gcc_assert (CONSTANT_CLASS_P (cst_expr));
353 55891 : gcc_assert (type == TREE_TYPE (cst_expr) || type == NULL_TREE);
354 55891 : }
355 :
356 33353580 : enum svalue_kind get_kind () const final override { return SK_CONSTANT; }
357 : const constant_svalue *
358 4841066 : 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 6320424 : 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 1646 : is_a_helper <const constant_svalue *>::test (const svalue *sval)
396 : {
397 1646 : 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 10217 : unknown_svalue (symbol::id_t id, tree type)
417 10217 : : svalue (complexity (1, 1), id, type)
418 : {}
419 :
420 4167625 : 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 97941 : 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 198516 : key_t (enum poison_kind kind, tree type)
472 198516 : : m_kind (kind), m_type (type)
473 : {}
474 :
475 765629 : hashval_t hash () const
476 : {
477 765629 : inchash::hash hstate;
478 765629 : hstate.add_int (static_cast<int> (m_kind));
479 765629 : hstate.add_ptr (m_type);
480 765629 : return hstate.end ();
481 : }
482 :
483 610654 : bool operator== (const key_t &other) const
484 : {
485 610654 : return (m_kind == other.m_kind && m_type == other.m_type);
486 : }
487 :
488 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
489 51801 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
490 791969 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
491 3386886 : 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 5913 : poisoned_svalue (enum poison_kind kind, symbol::id_t id, tree type)
498 5913 : : svalue (complexity (1, 1), id, type), m_kind (kind) {}
499 :
500 244502 : enum svalue_kind get_kind () const final override { return SK_POISONED; }
501 : const poisoned_svalue *
502 5352 : 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 5368 : enum poison_kind get_poison_kind () const { return m_kind; }
520 :
521 : /* Poisoned svalues are singletons per-type, so can't have state. */
522 8225 : 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 12 : bool operator== (const setjmp_record &other) const
559 : {
560 12 : 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 78 : void add_to_hash (inchash::hash *hstate) const
566 : {
567 78 : hstate->add_ptr (m_enode);
568 78 : hstate->add_ptr (m_sedge);
569 78 : hstate->add_ptr (m_setjmp_call);
570 78 : }
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 78 : hashval_t hash () const
595 : {
596 78 : inchash::hash hstate;
597 78 : m_record.add_to_hash (&hstate);
598 78 : hstate.add_ptr (m_type);
599 78 : return hstate.end ();
600 : }
601 :
602 12 : bool operator== (const key_t &other) const
603 : {
604 12 : return (m_record == other.m_record && m_type == other.m_type);
605 : }
606 :
607 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
608 51181 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
609 80 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
610 103393 : 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 879 : 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 26750 : initial_svalue (symbol::id_t id, tree type, const region *reg)
674 26750 : : svalue (complexity (reg), id, type), m_reg (reg)
675 : {
676 26750 : gcc_assert (m_reg != nullptr);
677 26750 : }
678 :
679 27434968 : enum svalue_kind get_kind () const final override { return SK_INITIAL; }
680 : const initial_svalue *
681 292298 : 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 6044070 : 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 1651730 : is_a_helper <const initial_svalue *>::test (const svalue *sval)
709 : {
710 1651730 : 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 115746 : key_t (tree type, enum tree_code op, const svalue *arg)
725 115746 : : m_type (type), m_op (op), m_arg (arg)
726 : {}
727 :
728 740715 : hashval_t hash () const
729 : {
730 740715 : inchash::hash hstate;
731 740715 : hstate.add_ptr (m_type);
732 740715 : hstate.add_int (m_op);
733 740715 : hstate.add_ptr (m_arg);
734 740715 : return hstate.end ();
735 : }
736 :
737 748700 : bool operator== (const key_t &other) const
738 : {
739 748700 : return (m_type == other.m_type
740 311255 : && m_op == other.m_op
741 1057859 : && m_arg == other.m_arg);
742 : }
743 :
744 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
745 64827 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
746 799512 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
747 2490676 : 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 8322 : unaryop_svalue (symbol::id_t id, tree type, enum tree_code op,
755 : const svalue *arg)
756 8322 : : svalue (complexity (arg), id, type), m_op (op), m_arg (arg)
757 : {
758 8322 : gcc_assert (arg->can_have_associated_state_p ());
759 8322 : }
760 :
761 8443929 : enum svalue_kind get_kind () const final override { return SK_UNARYOP; }
762 : const unaryop_svalue *
763 910546 : 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 2614721 : enum tree_code get_op () const { return m_op; }
778 2799840 : 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 288102 : is_a_helper <const unaryop_svalue *>::test (const svalue *sval)
798 : {
799 288102 : 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 103917 : key_t (tree type, enum tree_code op,
820 : const svalue *arg0, const svalue *arg1)
821 103917 : : m_type (type), m_op (op), m_arg0 (arg0), m_arg1 (arg1)
822 : {}
823 :
824 701442 : hashval_t hash () const
825 : {
826 701442 : inchash::hash hstate;
827 701442 : hstate.add_ptr (m_type);
828 701442 : hstate.add_int (m_op);
829 701442 : hstate.add_ptr (m_arg0);
830 701442 : hstate.add_ptr (m_arg1);
831 701442 : return hstate.end ();
832 : }
833 :
834 702073 : bool operator== (const key_t &other) const
835 : {
836 702073 : return (m_type == other.m_type
837 316220 : && m_op == other.m_op
838 243091 : && m_arg0 == other.m_arg0
839 828875 : && m_arg1 == other.m_arg1);
840 : }
841 :
842 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
843 99830 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
844 781256 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
845 2585821 : 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 20347 : binop_svalue (symbol::id_t id, tree type, enum tree_code op,
854 : const svalue *arg0, const svalue *arg1)
855 20347 : : svalue (complexity::from_pair (arg0->get_complexity (),
856 : arg1->get_complexity ()),
857 : id,
858 : type),
859 20347 : m_op (op), m_arg0 (arg0), m_arg1 (arg1)
860 : {
861 20347 : gcc_assert (arg0->can_have_associated_state_p ());
862 20347 : gcc_assert (arg1->can_have_associated_state_p ());
863 20347 : }
864 :
865 17649294 : enum svalue_kind get_kind () const final override { return SK_BINOP; }
866 129972 : const binop_svalue *dyn_cast_binop_svalue () const final override
867 : {
868 129972 : 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 5140729 : enum tree_code get_op () const { return m_op; }
886 3430904 : const svalue *get_arg0 () const { return m_arg0; }
887 2243631 : 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 280261 : is_a_helper <const binop_svalue *>::test (const svalue *sval)
901 : {
902 280261 : 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 15898 : key_t (tree type, const svalue *parent_svalue, const region *subregion)
924 15898 : : m_type (type), m_parent_svalue (parent_svalue), m_subregion (subregion)
925 : {}
926 :
927 108775 : hashval_t hash () const
928 : {
929 108775 : inchash::hash hstate;
930 108775 : hstate.add_ptr (m_type);
931 108775 : hstate.add_ptr (m_parent_svalue);
932 108775 : hstate.add_ptr (m_subregion);
933 108775 : return hstate.end ();
934 : }
935 :
936 105324 : bool operator== (const key_t &other) const
937 : {
938 105324 : return (m_type == other.m_type
939 61204 : && m_parent_svalue == other.m_parent_svalue
940 150239 : && m_subregion == other.m_subregion);
941 : }
942 :
943 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
944 54212 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
945 117409 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
946 457617 : 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 1361218 : enum svalue_kind get_kind () const final override { return SK_SUB; }
956 18363 : const sub_svalue *dyn_cast_sub_svalue () const final override
957 : {
958 18363 : 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 1016445 : 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 1713 : key_t (tree type,
1010 : const svalue *outer_size,
1011 : const svalue *inner_svalue)
1012 1713 : : m_type (type), m_outer_size (outer_size), m_inner_svalue (inner_svalue)
1013 : {}
1014 :
1015 7570 : hashval_t hash () const
1016 : {
1017 7570 : inchash::hash hstate;
1018 7570 : hstate.add_ptr (m_type);
1019 7570 : hstate.add_ptr (m_outer_size);
1020 7570 : hstate.add_ptr (m_inner_svalue);
1021 7570 : return hstate.end ();
1022 : }
1023 :
1024 6340 : bool operator== (const key_t &other) const
1025 : {
1026 6340 : return (m_type == other.m_type
1027 6205 : && m_outer_size == other.m_outer_size
1028 7599 : && m_inner_svalue == other.m_inner_svalue);
1029 : }
1030 :
1031 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1032 51677 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
1033 8162 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1034 139849 : 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 65335 : 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 50 : const svalue *get_outer_size () const { return m_outer_size; }
1062 447 : 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 38 : is_a_helper <const repeated_svalue *>::test (const svalue *sval)
1082 : {
1083 38 : 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 1434 : key_t (tree type,
1106 : const bit_range &bits,
1107 : const svalue *inner_svalue)
1108 1434 : : m_type (type), m_bits (bits), m_inner_svalue (inner_svalue)
1109 : {}
1110 :
1111 10311 : hashval_t hash () const
1112 : {
1113 10311 : inchash::hash hstate;
1114 10311 : hstate.add_ptr (m_type);
1115 10311 : hstate.add_ptr (m_inner_svalue);
1116 10311 : return hstate.end ();
1117 : }
1118 :
1119 10852 : bool operator== (const key_t &other) const
1120 : {
1121 10852 : return (m_type == other.m_type
1122 8918 : && m_bits == other.m_bits
1123 12289 : && m_inner_svalue == other.m_inner_svalue);
1124 : }
1125 :
1126 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1127 52583 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
1128 15959 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1129 154693 : 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 74541 : 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 459 : const bit_range &get_bits () const { return m_bits; }
1160 73 : 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 204 : unmergeable_svalue (symbol::id_t id, const svalue *arg)
1205 204 : : svalue (complexity (arg), id, arg->get_type ()), m_arg (arg)
1206 : {
1207 204 : }
1208 :
1209 12784 : enum svalue_kind get_kind () const final override { return SK_UNMERGEABLE; }
1210 : const unmergeable_svalue *
1211 4269 : 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 5149 : 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 12395 : placeholder_svalue (symbol::id_t id, tree type, const char *name)
1252 12395 : : svalue (complexity (1, 1), id, type), m_name (name)
1253 : {
1254 : }
1255 :
1256 33049 : 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 5809 : key_t (tree type, const supernode *snode,
1303 : const svalue *base_sval, const svalue *iter_sval)
1304 5809 : : m_type (type), m_snode (snode),
1305 5809 : m_base_sval (base_sval), m_iter_sval (iter_sval)
1306 : {}
1307 :
1308 33389 : hashval_t hash () const
1309 : {
1310 33389 : inchash::hash hstate;
1311 33389 : hstate.add_ptr (m_base_sval);
1312 33389 : hstate.add_ptr (m_iter_sval);
1313 33389 : return hstate.end ();
1314 : }
1315 :
1316 65248 : bool operator== (const key_t &other) const
1317 : {
1318 65248 : return (m_type == other.m_type
1319 54744 : && m_snode == other.m_snode
1320 4469 : && m_base_sval == other.m_base_sval
1321 68903 : && m_iter_sval == other.m_iter_sval);
1322 : }
1323 :
1324 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1325 53114 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
1326 88627 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1327 352706 : 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 2361 : widening_svalue (symbol::id_t id, tree type, const supernode *snode,
1343 : const svalue *base_sval, const svalue *iter_sval)
1344 2361 : : svalue (complexity::from_pair (base_sval->get_complexity (),
1345 : iter_sval->get_complexity ()),
1346 : id,
1347 : type),
1348 2361 : m_snode (snode),
1349 2361 : m_base_sval (base_sval), m_iter_sval (iter_sval)
1350 : {
1351 2361 : gcc_assert (base_sval->can_have_associated_state_p ());
1352 2361 : gcc_assert (iter_sval->can_have_associated_state_p ());
1353 2361 : }
1354 :
1355 896007 : enum svalue_kind get_kind () const final override { return SK_WIDENING; }
1356 18996 : const widening_svalue *dyn_cast_widening_svalue () const final override
1357 : {
1358 18996 : 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 3594 : const supernode *get_snode () const { return m_snode; }
1372 14285 : const svalue *get_base_svalue () const { return m_base_sval; }
1373 4965 : 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.
1406 :
1407 : This is for use in places where we want to represent a store-like
1408 : mapping, but are required to use an svalue, such as when handling
1409 : compound assignments and compound return values.
1410 :
1411 : All keys within the underlying binding_map are required to be concrete,
1412 : not symbolic.
1413 :
1414 : Instances of this class shouldn't be bound as-is into the store;
1415 : instead they should be unpacked. Similarly, they should not be
1416 : nested. */
1417 :
1418 : class compound_svalue : public svalue
1419 : {
1420 : public:
1421 : typedef binding_map::const_iterator_t const_iterator_t;
1422 : typedef binding_map::iterator_t iterator_t;
1423 :
1424 : /* A support class for uniquifying instances of compound_svalue.
1425 : Note that to avoid copies, keys store pointers to binding_maps,
1426 : rather than the maps themselves. */
1427 : struct key_t
1428 : {
1429 4356 : key_t (tree type, const binding_map *map_ptr)
1430 3745 : : m_type (type), m_map_ptr (map_ptr)
1431 : {}
1432 :
1433 18811 : hashval_t hash () const
1434 : {
1435 18811 : inchash::hash hstate;
1436 18811 : hstate.add_ptr (m_type);
1437 : //hstate.add_ptr (m_map_ptr); // TODO
1438 18811 : return hstate.end ();
1439 : }
1440 :
1441 22299 : bool operator== (const key_t &other) const
1442 : {
1443 22299 : return (m_type == other.m_type
1444 22299 : && *m_map_ptr == *other.m_map_ptr);
1445 : }
1446 :
1447 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1448 51462 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
1449 33305 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1450 204250 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
1451 :
1452 : tree m_type;
1453 : const binding_map *m_map_ptr;
1454 : };
1455 :
1456 : compound_svalue (symbol::id_t id, tree type, const binding_map &map);
1457 :
1458 6903 : enum svalue_kind get_kind () const final override { return SK_COMPOUND; }
1459 3991 : const compound_svalue *dyn_cast_compound_svalue () const final override
1460 : {
1461 3991 : return this;
1462 : }
1463 :
1464 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1465 :
1466 : void
1467 : print_dump_widget_label (pretty_printer *pp) const final override;
1468 : void
1469 : add_dump_widget_children (text_art::tree_widget &w,
1470 : const dump_widget_info &dwi) const final override;
1471 :
1472 : void accept (visitor *v) const final override;
1473 :
1474 95 : const binding_map &get_map () const { return m_map; }
1475 :
1476 4169 : const_iterator_t begin () const { return m_map.begin (); }
1477 14248 : const_iterator_t end () const { return m_map.end (); }
1478 611 : iterator_t begin () { return m_map.begin (); }
1479 611 : iterator_t end () { return m_map.end (); }
1480 :
1481 611 : struct key_t make_key () const
1482 : {
1483 611 : 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 : static complexity calc_complexity (const binding_map &map);
1493 :
1494 : binding_map m_map;
1495 : };
1496 :
1497 : } // namespace ana
1498 :
1499 : template <>
1500 : template <>
1501 : inline bool
1502 282 : is_a_helper <const compound_svalue *>::test (const svalue *sval)
1503 : {
1504 282 : return sval->get_kind () == SK_COMPOUND;
1505 : }
1506 :
1507 : template <> struct default_hash_traits<compound_svalue::key_t>
1508 : : public member_function_hash_traits<compound_svalue::key_t>
1509 : {
1510 : static const bool empty_zero_p = false;
1511 : };
1512 :
1513 : namespace ana {
1514 :
1515 : /* A bundle of state for purging information from a program_state about
1516 : a conjured_svalue. We pass this whenever calling
1517 : get_or_create_conjured_svalue, so that if the program_state already
1518 : has information about this conjured_svalue on an execution path, we
1519 : can purge that information, to avoid the analyzer confusing the two
1520 : values as being the same. */
1521 :
1522 : class conjured_purge
1523 : {
1524 : public:
1525 38932 : conjured_purge (region_model *model, region_model_context *ctxt)
1526 38784 : : m_model (model), m_ctxt (ctxt)
1527 : {
1528 : }
1529 : void purge (const conjured_svalue *sval) const;
1530 :
1531 : private:
1532 : region_model *m_model;
1533 : region_model_context *m_ctxt;
1534 : };
1535 :
1536 : /* A defined value arising from a statement, where we want to identify a
1537 : particular unknown value, rather than resorting to the unknown_value
1538 : singleton, so that the value can have sm-state.
1539 :
1540 : Comparisons of variables that share the same conjured_svalue are known
1541 : to be equal, even if we don't know what the value is.
1542 :
1543 : For example, this is used for the values of regions that may have been
1544 : touched when calling an unknown function.
1545 :
1546 : The value captures a region as well as a stmt in order to avoid falsely
1547 : aliasing the various values that could arise in one statement. For
1548 : example, after:
1549 : unknown_fn (&a, &b);
1550 : we want values to clobber a and b with, but we don't want to use the
1551 : same value, or it would falsely implicitly assume that a == b. */
1552 :
1553 : class conjured_svalue : public svalue
1554 : {
1555 : public:
1556 : /* A support class for uniquifying instances of conjured_svalue. */
1557 : struct key_t
1558 : {
1559 52685 : key_t (tree type, const gimple *stmt, const region *id_reg, unsigned idx)
1560 52685 : : m_type (type), m_stmt (stmt), m_id_reg (id_reg), m_idx (idx)
1561 : {}
1562 :
1563 470049 : hashval_t hash () const
1564 : {
1565 470049 : inchash::hash hstate;
1566 470049 : hstate.add_ptr (m_type);
1567 470049 : hstate.add_ptr (m_stmt);
1568 470049 : hstate.add_ptr (m_id_reg);
1569 470049 : return hstate.end ();
1570 : }
1571 :
1572 472911 : bool operator== (const key_t &other) const
1573 : {
1574 472911 : return (m_type == other.m_type
1575 209677 : && m_stmt == other.m_stmt
1576 47153 : && m_id_reg == other.m_id_reg
1577 509783 : && m_idx == other.m_idx);
1578 : }
1579 :
1580 : /* Use m_stmt to mark empty/deleted, as m_type can be NULL_TREE for
1581 : legitimate instances. */
1582 : void mark_deleted () { m_stmt = reinterpret_cast<const gimple *> (1); }
1583 0 : void mark_empty () { m_stmt = nullptr; }
1584 565308 : bool is_deleted () const
1585 : {
1586 565308 : return m_stmt == reinterpret_cast<const gimple *> (1);
1587 : }
1588 1866469 : bool is_empty () const { return m_stmt == nullptr; }
1589 :
1590 : tree m_type;
1591 : const gimple *m_stmt;
1592 : const region *m_id_reg;
1593 : unsigned m_idx;
1594 : };
1595 :
1596 25900 : conjured_svalue (symbol::id_t id, tree type, const gimple *stmt,
1597 : const region *id_reg, unsigned idx)
1598 25900 : : svalue (complexity (id_reg), id, type),
1599 25900 : m_stmt (stmt), m_id_reg (id_reg), m_idx (idx)
1600 : {
1601 25900 : gcc_assert (m_stmt != nullptr);
1602 25900 : }
1603 :
1604 19550716 : enum svalue_kind get_kind () const final override { return SK_CONJURED; }
1605 0 : const conjured_svalue *dyn_cast_conjured_svalue () const final override
1606 : {
1607 0 : return this;
1608 : }
1609 :
1610 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1611 :
1612 : void
1613 : print_dump_widget_label (pretty_printer *pp) const final override;
1614 : void
1615 : add_dump_widget_children (text_art::tree_widget &w,
1616 : const dump_widget_info &dwi) const final override;
1617 :
1618 : void accept (visitor *v) const final override;
1619 :
1620 3183169 : const gimple *get_stmt () const { return m_stmt; }
1621 74336 : const region *get_id_region () const { return m_id_reg; }
1622 : bool lhs_value_p () const;
1623 :
1624 : private:
1625 : const gimple *m_stmt;
1626 : const region *m_id_reg;
1627 : unsigned m_idx;
1628 : };
1629 :
1630 : } // namespace ana
1631 :
1632 : template <>
1633 : template <>
1634 : inline bool
1635 : is_a_helper <const conjured_svalue *>::test (const svalue *sval)
1636 : {
1637 : return sval->get_kind () == SK_CONJURED;
1638 : }
1639 :
1640 : template <> struct default_hash_traits<conjured_svalue::key_t>
1641 : : public member_function_hash_traits<conjured_svalue::key_t>
1642 : {
1643 : static const bool empty_zero_p = true;
1644 : };
1645 :
1646 : namespace ana {
1647 :
1648 : /* An output from a deterministic asm stmt, where we want to identify a
1649 : particular unknown value, rather than resorting to the unknown_value
1650 : singleton.
1651 :
1652 : Comparisons of variables that share the same asm_output_svalue are known
1653 : to be equal, even if we don't know what the value is. */
1654 :
1655 : class asm_output_svalue : public svalue
1656 : {
1657 : public:
1658 : /* Imposing an upper limit and using a (small) array allows key_t
1659 : to avoid memory management. */
1660 : static const unsigned MAX_INPUTS = 2;
1661 :
1662 : /* A support class for uniquifying instances of asm_output_svalue. */
1663 : struct key_t
1664 : {
1665 358 : key_t (tree type,
1666 : const char *asm_string,
1667 : unsigned output_idx,
1668 : const vec<const svalue *> &inputs)
1669 358 : : m_type (type), m_asm_string (asm_string), m_output_idx (output_idx),
1670 358 : m_num_inputs (inputs.length ())
1671 : {
1672 358 : gcc_assert (inputs.length () <= MAX_INPUTS);
1673 958 : for (unsigned i = 0; i < m_num_inputs; i++)
1674 600 : m_input_arr[i] = inputs[i];
1675 358 : }
1676 :
1677 1528 : hashval_t hash () const
1678 : {
1679 1528 : inchash::hash hstate;
1680 1528 : hstate.add_ptr (m_type);
1681 : /* We don't bother hashing m_asm_str. */
1682 1528 : hstate.add_int (m_output_idx);
1683 4172 : for (unsigned i = 0; i < m_num_inputs; i++)
1684 2644 : hstate.add_ptr (m_input_arr[i]);
1685 1528 : return hstate.end ();
1686 : }
1687 :
1688 1085 : bool operator== (const key_t &other) const
1689 : {
1690 1085 : if (!(m_type == other.m_type
1691 849 : && 0 == (strcmp (m_asm_string, other.m_asm_string))
1692 748 : && m_output_idx == other.m_output_idx
1693 602 : && m_num_inputs == other.m_num_inputs))
1694 : return false;
1695 1074 : for (unsigned i = 0; i < m_num_inputs; i++)
1696 908 : if (m_input_arr[i] != other.m_input_arr[i])
1697 : return false;
1698 : return true;
1699 : }
1700 :
1701 : /* Use m_asm_string to mark empty/deleted, as m_type can be NULL_TREE for
1702 : legitimate instances. */
1703 : void mark_deleted () { m_asm_string = reinterpret_cast<const char *> (1); }
1704 0 : void mark_empty () { m_asm_string = nullptr; }
1705 1586 : bool is_deleted () const
1706 : {
1707 1586 : return m_asm_string == reinterpret_cast<const char *> (1);
1708 : }
1709 110990 : bool is_empty () const { return m_asm_string == nullptr; }
1710 :
1711 : tree m_type;
1712 : const char *m_asm_string;
1713 : unsigned m_output_idx;
1714 : unsigned m_num_inputs;
1715 : const svalue *m_input_arr[MAX_INPUTS];
1716 : };
1717 :
1718 192 : asm_output_svalue (symbol::id_t id,
1719 : tree type,
1720 : const char *asm_string,
1721 : unsigned output_idx,
1722 : unsigned num_outputs,
1723 : const vec<const svalue *> &inputs)
1724 192 : : svalue (complexity::from_vec_svalue (inputs), id, type),
1725 192 : m_asm_string (asm_string),
1726 192 : m_output_idx (output_idx),
1727 192 : m_num_outputs (num_outputs),
1728 192 : m_num_inputs (inputs.length ())
1729 : {
1730 192 : gcc_assert (inputs.length () <= MAX_INPUTS);
1731 488 : for (unsigned i = 0; i < m_num_inputs; i++)
1732 296 : m_input_arr[i] = inputs[i];
1733 192 : }
1734 :
1735 9612 : enum svalue_kind get_kind () const final override { return SK_ASM_OUTPUT; }
1736 : const asm_output_svalue *
1737 0 : dyn_cast_asm_output_svalue () const final override
1738 : {
1739 0 : return this;
1740 : }
1741 :
1742 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1743 :
1744 : void
1745 : print_dump_widget_label (pretty_printer *pp) const final override;
1746 : void
1747 : add_dump_widget_children (text_art::tree_widget &w,
1748 : const dump_widget_info &dwi) const final override;
1749 :
1750 : void accept (visitor *v) const final override;
1751 :
1752 102 : const char *get_asm_string () const { return m_asm_string; }
1753 154 : unsigned get_output_idx () const { return m_output_idx; }
1754 78 : unsigned get_num_outputs () const { return m_num_outputs; }
1755 312 : unsigned get_num_inputs () const { return m_num_inputs; }
1756 164 : const svalue *get_input (unsigned idx) const { return m_input_arr[idx]; }
1757 :
1758 : private:
1759 : void dump_input (pretty_printer *pp,
1760 : unsigned input_idx,
1761 : const svalue *sval,
1762 : bool simple) const;
1763 : unsigned input_idx_to_asm_idx (unsigned input_idx) const;
1764 :
1765 : const char *m_asm_string;
1766 : unsigned m_output_idx;
1767 :
1768 : /* We capture this so that we can offset the input indices
1769 : to match the %0, %1, %2 in the asm_string when dumping. */
1770 : unsigned m_num_outputs;
1771 :
1772 : unsigned m_num_inputs;
1773 : const svalue *m_input_arr[MAX_INPUTS];
1774 : };
1775 :
1776 : } // namespace ana
1777 :
1778 : template <>
1779 : template <>
1780 : inline bool
1781 8 : is_a_helper <const asm_output_svalue *>::test (const svalue *sval)
1782 : {
1783 8 : return sval->get_kind () == SK_ASM_OUTPUT;
1784 : }
1785 :
1786 : template <> struct default_hash_traits<asm_output_svalue::key_t>
1787 : : public member_function_hash_traits<asm_output_svalue::key_t>
1788 : {
1789 : static const bool empty_zero_p = true;
1790 : };
1791 :
1792 : namespace ana {
1793 :
1794 : /* The return value from a function with __attribute((const)) for given
1795 : inputs, provided that we don't have too many inputs, and all of them
1796 : are deterministic.
1797 :
1798 : Comparisons of variables that share the same const_fn_result_svalue are known
1799 : to be equal, even if we don't know what the value is. */
1800 :
1801 : class const_fn_result_svalue : public svalue
1802 : {
1803 : public:
1804 : /* Imposing an upper limit and using a (small) array allows key_t
1805 : to avoid memory management. */
1806 : static const unsigned MAX_INPUTS = 2;
1807 :
1808 : /* A support class for uniquifying instances of const_fn_result_svalue. */
1809 : struct key_t
1810 : {
1811 891 : key_t (tree type,
1812 : tree fndecl,
1813 : const vec<const svalue *> &inputs)
1814 891 : : m_type (type), m_fndecl (fndecl),
1815 891 : m_num_inputs (inputs.length ())
1816 : {
1817 891 : gcc_assert (inputs.length () <= MAX_INPUTS);
1818 1355 : for (unsigned i = 0; i < m_num_inputs; i++)
1819 464 : m_input_arr[i] = inputs[i];
1820 891 : }
1821 :
1822 3178 : hashval_t hash () const
1823 : {
1824 3178 : inchash::hash hstate;
1825 3178 : hstate.add_ptr (m_type);
1826 3178 : hstate.add_ptr (m_fndecl);
1827 5909 : for (unsigned i = 0; i < m_num_inputs; i++)
1828 2731 : hstate.add_ptr (m_input_arr[i]);
1829 3178 : return hstate.end ();
1830 : }
1831 :
1832 2466 : bool operator== (const key_t &other) const
1833 : {
1834 2466 : if (!(m_type == other.m_type
1835 2288 : && m_fndecl == other.m_fndecl
1836 1590 : && m_num_inputs == other.m_num_inputs))
1837 : return false;
1838 1975 : for (unsigned i = 0; i < m_num_inputs; i++)
1839 1271 : if (m_input_arr[i] != other.m_input_arr[i])
1840 : return false;
1841 : return true;
1842 : }
1843 :
1844 : /* Use m_fndecl to mark empty/deleted. */
1845 : void mark_deleted () { m_fndecl = reinterpret_cast<tree> (1); }
1846 0 : void mark_empty () { m_fndecl = NULL_TREE; }
1847 3414 : bool is_deleted () const
1848 : {
1849 3414 : return m_fndecl == reinterpret_cast<tree> (1);
1850 : }
1851 119740 : bool is_empty () const { return m_fndecl == NULL_TREE; }
1852 :
1853 : tree m_type;
1854 : tree m_fndecl;
1855 : unsigned m_num_inputs;
1856 : const svalue *m_input_arr[MAX_INPUTS];
1857 : };
1858 :
1859 187 : const_fn_result_svalue (symbol::id_t id,
1860 : tree type,
1861 : tree fndecl,
1862 : const vec<const svalue *> &inputs)
1863 187 : : svalue (complexity::from_vec_svalue (inputs), id, type),
1864 187 : m_fndecl (fndecl),
1865 187 : m_num_inputs (inputs.length ())
1866 : {
1867 187 : gcc_assert (inputs.length () <= MAX_INPUTS);
1868 359 : for (unsigned i = 0; i < m_num_inputs; i++)
1869 172 : m_input_arr[i] = inputs[i];
1870 187 : }
1871 :
1872 28525 : enum svalue_kind get_kind () const final override
1873 : {
1874 28525 : return SK_CONST_FN_RESULT;
1875 : }
1876 : const const_fn_result_svalue *
1877 0 : dyn_cast_const_fn_result_svalue () const final override
1878 : {
1879 0 : return this;
1880 : }
1881 :
1882 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1883 :
1884 : void
1885 : print_dump_widget_label (pretty_printer *pp) const final override;
1886 : void
1887 : add_dump_widget_children (text_art::tree_widget &w,
1888 : const dump_widget_info &dwi) const final override;
1889 :
1890 : void accept (visitor *v) const final override;
1891 :
1892 146 : tree get_fndecl () const { return m_fndecl; }
1893 258 : unsigned get_num_inputs () const { return m_num_inputs; }
1894 114 : const svalue *get_input (unsigned idx) const { return m_input_arr[idx]; }
1895 :
1896 : private:
1897 : void dump_input (pretty_printer *pp,
1898 : unsigned input_idx,
1899 : const svalue *sval,
1900 : bool simple) const;
1901 :
1902 : tree m_fndecl;
1903 : unsigned m_num_inputs;
1904 : const svalue *m_input_arr[MAX_INPUTS];
1905 : };
1906 :
1907 : } // namespace ana
1908 :
1909 : template <>
1910 : template <>
1911 : inline bool
1912 2 : is_a_helper <const const_fn_result_svalue *>::test (const svalue *sval)
1913 : {
1914 2 : return sval->get_kind () == SK_CONST_FN_RESULT;
1915 : }
1916 :
1917 : template <> struct default_hash_traits<const_fn_result_svalue::key_t>
1918 : : public member_function_hash_traits<const_fn_result_svalue::key_t>
1919 : {
1920 : static const bool empty_zero_p = true;
1921 : };
1922 :
1923 : #endif /* GCC_ANALYZER_SVALUE_H */
|
