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 57033093 : 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 14047289 : dyn_cast_region_svalue () const { return nullptr; }
116 : virtual const constant_svalue *
117 9462544 : dyn_cast_constant_svalue () const { return nullptr; }
118 : virtual const poisoned_svalue *
119 2071172 : 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 4018216 : dyn_cast_initial_svalue () const { return nullptr; }
124 : virtual const unaryop_svalue *
125 12514357 : dyn_cast_unaryop_svalue () const { return nullptr; }
126 : virtual const binop_svalue *
127 1136582 : dyn_cast_binop_svalue () const { return nullptr; }
128 : virtual const sub_svalue *
129 3693261 : dyn_cast_sub_svalue () const { return nullptr; }
130 : virtual const repeated_svalue *
131 16194 : 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 17294145 : dyn_cast_unmergeable_svalue () const { return nullptr; }
136 : virtual const widening_svalue *
137 495421 : dyn_cast_widening_svalue () const { return nullptr; }
138 : virtual const compound_svalue *
139 13198740 : 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 2406128 : 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 214432 : maybe_get_value_range (value_range &out) const
197 : {
198 214432 : if (maybe_get_value_range_1 (out))
199 : {
200 155021 : gcc_assert (!out.undefined_p ());
201 : return true;
202 : }
203 : return false;
204 : }
205 :
206 : protected:
207 206701 : svalue (complexity c, symbol::id_t id, tree type)
208 92078 : : 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 1011438 : key_t (tree type, const region *reg)
235 1011438 : : m_type (type), m_reg (reg)
236 : {}
237 :
238 5034348 : hashval_t hash () const
239 : {
240 5034348 : inchash::hash hstate;
241 5034348 : hstate.add_ptr (m_type);
242 5034348 : hstate.add_ptr (m_reg);
243 5034348 : return hstate.end ();
244 : }
245 :
246 4816665 : bool operator== (const key_t &other) const
247 : {
248 4816665 : return (m_type == other.m_type && m_reg == other.m_reg);
249 : }
250 :
251 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
252 102391 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
253 5361915 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
254 18396142 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
255 :
256 : tree m_type;
257 : const region *m_reg;
258 : };
259 :
260 26921 : region_svalue (symbol::id_t id, tree type, const region *reg)
261 26921 : : svalue (complexity (reg), id, type),
262 26921 : m_reg (reg)
263 : {
264 26921 : gcc_assert (m_reg != nullptr);
265 26921 : }
266 :
267 13887229 : enum svalue_kind get_kind () const final override { return SK_REGION; }
268 : const region_svalue *
269 2185463 : 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 4037415 : 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 : const region_model &model);
289 :
290 : private:
291 : const region *m_reg;
292 : };
293 :
294 : } // namespace ana
295 :
296 : template <>
297 : template <>
298 : inline bool
299 64084 : is_a_helper <const region_svalue *>::test (const svalue *sval)
300 : {
301 64084 : return sval->get_kind () == SK_REGION;
302 : }
303 :
304 : template <> struct default_hash_traits<region_svalue::key_t>
305 : : public member_function_hash_traits<region_svalue::key_t>
306 : {
307 : static const bool empty_zero_p = false;
308 : };
309 :
310 : namespace ana {
311 :
312 : /* Concrete subclass of svalue representing a specific constant value.
313 : The type will either be the same as that of the underlying tree constant,
314 : or NULL_TREE indicating the constant is intended to be "typeless". */
315 :
316 : class constant_svalue : public svalue
317 : {
318 : public:
319 : /* A support class for uniquifying instances of region_svalue. */
320 : struct key_t
321 : {
322 2629513 : key_t (tree type, tree cst)
323 2629513 : : m_type (type), m_cst (cst)
324 : {}
325 :
326 16374929 : hashval_t hash () const
327 : {
328 16374929 : inchash::hash hstate;
329 16374929 : hstate.add_ptr (m_type);
330 16374929 : hstate.add_ptr (m_cst);
331 16374929 : return hstate.end ();
332 : }
333 :
334 16497018 : bool operator== (const key_t &other) const
335 : {
336 16497018 : return (m_type == other.m_type && m_cst == other.m_cst);
337 : }
338 :
339 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
340 182988 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
341 17183608 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
342 50705726 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
343 :
344 : tree m_type;
345 : tree m_cst;
346 : };
347 :
348 58407 : constant_svalue (symbol::id_t id, tree type, tree cst_expr)
349 58407 : : svalue (complexity (1, 1), id, type),
350 58407 : m_cst_expr (cst_expr)
351 : {
352 58407 : gcc_assert (cst_expr);
353 58407 : gcc_assert (CONSTANT_CLASS_P (cst_expr));
354 58407 : gcc_assert (type == TREE_TYPE (cst_expr) || type == NULL_TREE);
355 58407 : }
356 :
357 37222755 : enum svalue_kind get_kind () const final override { return SK_CONSTANT; }
358 : const constant_svalue *
359 4969446 : dyn_cast_constant_svalue () const final override { return this; }
360 :
361 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
362 :
363 : void
364 : print_dump_widget_label (pretty_printer *pp) const final override;
365 : void
366 : add_dump_widget_children (text_art::tree_widget &w,
367 : const dump_widget_info &dwi) const final override;
368 :
369 : void accept (visitor *v) const final override;
370 : bool implicitly_live_p (const svalue_set *,
371 : const region_model *) const final override;
372 :
373 6461564 : tree get_constant () const { return m_cst_expr; }
374 : static tristate eval_condition (const constant_svalue *lhs,
375 : enum tree_code op,
376 : const constant_svalue *rhs);
377 :
378 : const svalue *
379 : maybe_fold_bits_within (tree type,
380 : const bit_range &subrange,
381 : region_model_manager *mgr) const final override;
382 :
383 : bool all_zeroes_p () const final override;
384 :
385 : bool maybe_get_value_range_1 (value_range &out) const final override;
386 :
387 : private:
388 : tree m_cst_expr;
389 : };
390 :
391 : } // namespace ana
392 :
393 : template <>
394 : template <>
395 : inline bool
396 1955 : is_a_helper <const constant_svalue *>::test (const svalue *sval)
397 : {
398 1955 : return sval->get_kind () == SK_CONSTANT;
399 : }
400 :
401 : template <> struct default_hash_traits<constant_svalue::key_t>
402 : : public member_function_hash_traits<constant_svalue::key_t>
403 : {
404 : static const bool empty_zero_p = false;
405 : };
406 :
407 : namespace ana {
408 :
409 : /* Concrete subclass of svalue representing an unknowable value, the bottom
410 : value when thinking of svalues as a lattice.
411 : This is a singleton (w.r.t. its manager): there is a single unknown_svalue
412 : per type. Self-comparisons of such instances yield "unknown". */
413 :
414 : class unknown_svalue : public svalue
415 : {
416 : public:
417 10681 : unknown_svalue (symbol::id_t id, tree type)
418 10681 : : svalue (complexity (1, 1), id, type)
419 : {}
420 :
421 7778471 : enum svalue_kind get_kind () const final override { return SK_UNKNOWN; }
422 :
423 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
424 :
425 : void
426 : print_dump_widget_label (pretty_printer *pp) const final override;
427 : void
428 : add_dump_widget_children (text_art::tree_widget &w,
429 : const dump_widget_info &dwi) const final override;
430 :
431 : void accept (visitor *v) const final override;
432 :
433 : const svalue *
434 : maybe_fold_bits_within (tree type,
435 : const bit_range &subrange,
436 : region_model_manager *mgr) const final override;
437 :
438 : bool maybe_get_value_range_1 (value_range &out) const final override;
439 :
440 : /* Unknown values are singletons per-type, so can't have state. */
441 102473 : bool can_have_associated_state_p () const final override { return false; }
442 : };
443 :
444 : /* An enum describing a particular kind of "poisoned" value. */
445 :
446 : enum class poison_kind
447 : {
448 : /* For use to describe uninitialized memory. */
449 : uninit,
450 :
451 : /* For use to describe freed memory. */
452 : freed,
453 :
454 : /* For use to describe deleted memory. */
455 : deleted,
456 :
457 : /* For use on pointers to regions within popped stack frames. */
458 : popped_stack
459 : };
460 :
461 : extern const char *poison_kind_to_str (enum poison_kind);
462 :
463 : /* Concrete subclass of svalue representing a value that should not
464 : be used (e.g. uninitialized memory, freed memory). */
465 :
466 : class poisoned_svalue : public svalue
467 : {
468 : public:
469 : /* A support class for uniquifying instances of poisoned_svalue. */
470 : struct key_t
471 : {
472 211337 : key_t (enum poison_kind kind, tree type)
473 211337 : : m_kind (kind), m_type (type)
474 : {}
475 :
476 821376 : hashval_t hash () const
477 : {
478 821376 : inchash::hash hstate;
479 821376 : hstate.add_int (static_cast<int> (m_kind));
480 821376 : hstate.add_ptr (m_type);
481 821376 : return hstate.end ();
482 : }
483 :
484 667962 : bool operator== (const key_t &other) const
485 : {
486 667962 : return (m_kind == other.m_kind && m_type == other.m_type);
487 : }
488 :
489 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
490 53279 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
491 860895 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
492 3629726 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
493 :
494 : enum poison_kind m_kind;
495 : tree m_type;
496 : };
497 :
498 6195 : poisoned_svalue (enum poison_kind kind, symbol::id_t id, tree type)
499 6195 : : svalue (complexity (1, 1), id, type), m_kind (kind) {}
500 :
501 311113 : enum svalue_kind get_kind () const final override { return SK_POISONED; }
502 : const poisoned_svalue *
503 5509 : dyn_cast_poisoned_svalue () const final override { return this; }
504 :
505 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
506 :
507 : void
508 : print_dump_widget_label (pretty_printer *pp) const final override;
509 : void
510 : add_dump_widget_children (text_art::tree_widget &w,
511 : const dump_widget_info &dwi) const final override;
512 :
513 : void accept (visitor *v) const final override;
514 :
515 : const svalue *
516 : maybe_fold_bits_within (tree type,
517 : const bit_range &subrange,
518 : region_model_manager *mgr) const final override;
519 :
520 5525 : enum poison_kind get_poison_kind () const { return m_kind; }
521 :
522 : /* Poisoned svalues are singletons per-type, so can't have state. */
523 8432 : bool can_have_associated_state_p () const final override { return false; }
524 :
525 : private:
526 : enum poison_kind m_kind;
527 : };
528 :
529 : } // namespace ana
530 :
531 : template <>
532 : template <>
533 : inline bool
534 8 : is_a_helper <const poisoned_svalue *>::test (const svalue *sval)
535 : {
536 8 : return sval->get_kind () == SK_POISONED;
537 : }
538 :
539 : template <> struct default_hash_traits<poisoned_svalue::key_t>
540 : : public member_function_hash_traits<poisoned_svalue::key_t>
541 : {
542 : static const bool empty_zero_p = false;
543 : };
544 :
545 : namespace ana {
546 :
547 : /* A bundle of information recording a setjmp/sigsetjmp call, corresponding
548 : roughly to a jmp_buf. */
549 :
550 : struct setjmp_record
551 : {
552 34 : setjmp_record (const exploded_node *enode,
553 : const superedge *sedge,
554 : const gcall &setjmp_call)
555 34 : : m_enode (enode), m_sedge (sedge), m_setjmp_call (&setjmp_call)
556 : {
557 : }
558 :
559 12 : bool operator== (const setjmp_record &other) const
560 : {
561 12 : return (m_enode == other.m_enode
562 0 : && m_sedge == other.m_sedge
563 0 : && m_setjmp_call == other.m_setjmp_call);
564 : }
565 :
566 76 : void add_to_hash (inchash::hash *hstate) const
567 : {
568 76 : hstate->add_ptr (m_enode);
569 76 : hstate->add_ptr (m_sedge);
570 76 : hstate->add_ptr (m_setjmp_call);
571 76 : }
572 :
573 : static int cmp (const setjmp_record &rec1, const setjmp_record &rec2);
574 :
575 : const exploded_node *m_enode;
576 : const superedge *m_sedge;
577 : const gcall *m_setjmp_call;
578 : // non-null, but we can't use a reference since we're putting these in a hash_map
579 : };
580 :
581 : /* Concrete subclass of svalue representing buffers for setjmp/sigsetjmp,
582 : so that longjmp/siglongjmp can potentially "return" to an entirely
583 : different function. */
584 :
585 : class setjmp_svalue : public svalue
586 : {
587 : public:
588 : /* A support class for uniquifying instances of poisoned_svalue. */
589 : struct key_t
590 : {
591 34 : key_t (const setjmp_record &record, tree type)
592 34 : : m_record (record), m_type (type)
593 : {}
594 :
595 76 : hashval_t hash () const
596 : {
597 76 : inchash::hash hstate;
598 76 : m_record.add_to_hash (&hstate);
599 76 : hstate.add_ptr (m_type);
600 76 : return hstate.end ();
601 : }
602 :
603 12 : bool operator== (const key_t &other) const
604 : {
605 12 : return (m_record == other.m_record && m_type == other.m_type);
606 : }
607 :
608 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
609 52442 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
610 80 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
611 105917 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
612 :
613 : setjmp_record m_record;
614 : tree m_type;
615 : };
616 :
617 34 : setjmp_svalue (const setjmp_record &setjmp_record,
618 : symbol::id_t id,
619 : tree type)
620 34 : : svalue (complexity (1, 1), id, type), m_setjmp_record (setjmp_record)
621 : {}
622 :
623 2775 : enum svalue_kind get_kind () const final override { return SK_SETJMP; }
624 : const setjmp_svalue *
625 25 : dyn_cast_setjmp_svalue () const final override { return this; }
626 :
627 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
628 :
629 : void
630 : print_dump_widget_label (pretty_printer *pp) const final override;
631 : void
632 : add_dump_widget_children (text_art::tree_widget &w,
633 : const dump_widget_info &dwi) const final override;
634 :
635 : void accept (visitor *v) const final override;
636 :
637 : int get_enode_index () const;
638 :
639 0 : const setjmp_record &get_setjmp_record () const { return m_setjmp_record; }
640 :
641 : private:
642 : setjmp_record m_setjmp_record;
643 : };
644 :
645 : } // namespace ana
646 :
647 : template <>
648 : template <>
649 : inline bool
650 : is_a_helper <const setjmp_svalue *>::test (const svalue *sval)
651 : {
652 : return sval->get_kind () == SK_SETJMP;
653 : }
654 :
655 : template <> struct default_hash_traits<setjmp_svalue::key_t>
656 : : public member_function_hash_traits<setjmp_svalue::key_t>
657 : {
658 : static const bool empty_zero_p = false;
659 : };
660 :
661 : namespace ana {
662 :
663 : /* Concrete subclass of svalue representing the initial value of a
664 : specific region.
665 :
666 : This represents the initial value at the start of the analysis path,
667 : as opposed to the first time the region is accessed during the path.
668 : Hence as soon as we have a call to an unknown function, all previously
669 : unmodelled globals become implicitly "unknown" rathen than "initial". */
670 :
671 : class initial_svalue : public svalue
672 : {
673 : public:
674 28205 : initial_svalue (symbol::id_t id, tree type, const region *reg)
675 28205 : : svalue (complexity (reg), id, type), m_reg (reg)
676 : {
677 28205 : gcc_assert (m_reg != nullptr);
678 28205 : }
679 :
680 28942580 : enum svalue_kind get_kind () const final override { return SK_INITIAL; }
681 : const initial_svalue *
682 304713 : dyn_cast_initial_svalue () const final override { return this; }
683 :
684 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
685 :
686 : void
687 : print_dump_widget_label (pretty_printer *pp) const final override;
688 : void
689 : add_dump_widget_children (text_art::tree_widget &w,
690 : const dump_widget_info &dwi) const final override;
691 :
692 : void accept (visitor *v) const final override;
693 : bool implicitly_live_p (const svalue_set *,
694 : const region_model *) const final override;
695 :
696 : bool initial_value_of_param_p () const;
697 :
698 6132101 : const region *get_region () const { return m_reg; }
699 :
700 : private:
701 : const region *m_reg;
702 : };
703 :
704 : } // namespace ana
705 :
706 : template <>
707 : template <>
708 : inline bool
709 1709578 : is_a_helper <const initial_svalue *>::test (const svalue *sval)
710 : {
711 1709578 : return sval->get_kind () == SK_INITIAL;
712 : }
713 :
714 : namespace ana {
715 :
716 : /* Concrete subclass of svalue representing a unary operation on
717 : another svalues (e.g. a cast). */
718 :
719 : class unaryop_svalue : public svalue
720 : {
721 : public:
722 : /* A support class for uniquifying instances of unaryop_svalue. */
723 : struct key_t
724 : {
725 121621 : key_t (tree type, enum tree_code op, const svalue *arg)
726 121621 : : m_type (type), m_op (op), m_arg (arg)
727 : {}
728 :
729 774455 : hashval_t hash () const
730 : {
731 774455 : inchash::hash hstate;
732 774455 : hstate.add_ptr (m_type);
733 774455 : hstate.add_int (m_op);
734 774455 : hstate.add_ptr (m_arg);
735 774455 : return hstate.end ();
736 : }
737 :
738 778594 : bool operator== (const key_t &other) const
739 : {
740 778594 : return (m_type == other.m_type
741 318620 : && m_op == other.m_op
742 1094891 : && m_arg == other.m_arg);
743 : }
744 :
745 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
746 66395 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
747 830929 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
748 2600799 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
749 :
750 : tree m_type;
751 : enum tree_code m_op;
752 : const svalue *m_arg;
753 : };
754 :
755 8839 : unaryop_svalue (symbol::id_t id, tree type, enum tree_code op,
756 : const svalue *arg)
757 8839 : : svalue (complexity (arg), id, type), m_op (op), m_arg (arg)
758 : {
759 8839 : gcc_assert (arg->can_have_associated_state_p ());
760 8839 : }
761 :
762 9430999 : enum svalue_kind get_kind () const final override { return SK_UNARYOP; }
763 : const unaryop_svalue *
764 895650 : dyn_cast_unaryop_svalue () const final override { return this; }
765 :
766 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
767 :
768 : void
769 : print_dump_widget_label (pretty_printer *pp) const final override;
770 : void
771 : add_dump_widget_children (text_art::tree_widget &w,
772 : const dump_widget_info &dwi) const final override;
773 :
774 : void accept (visitor *v) const final override;
775 : bool implicitly_live_p (const svalue_set *,
776 : const region_model *) const final override;
777 :
778 2585623 : enum tree_code get_op () const { return m_op; }
779 2791537 : const svalue *get_arg () const { return m_arg; }
780 :
781 : const svalue *
782 : maybe_fold_bits_within (tree type,
783 : const bit_range &subrange,
784 : region_model_manager *mgr) const final override;
785 :
786 : bool maybe_get_value_range_1 (value_range &out) const final override;
787 :
788 : private:
789 : enum tree_code m_op;
790 : const svalue *m_arg;
791 : };
792 :
793 : } // namespace ana
794 :
795 : template <>
796 : template <>
797 : inline bool
798 306726 : is_a_helper <const unaryop_svalue *>::test (const svalue *sval)
799 : {
800 306726 : return sval->get_kind () == SK_UNARYOP;
801 : }
802 :
803 : template <> struct default_hash_traits<unaryop_svalue::key_t>
804 : : public member_function_hash_traits<unaryop_svalue::key_t>
805 : {
806 : static const bool empty_zero_p = false;
807 : };
808 :
809 : namespace ana {
810 :
811 : /* Concrete subclass of svalue representing a binary operation of
812 : two svalues. */
813 :
814 : class binop_svalue : public svalue
815 : {
816 : public:
817 : /* A support class for uniquifying instances of binop_svalue. */
818 : struct key_t
819 : {
820 108139 : key_t (tree type, enum tree_code op,
821 : const svalue *arg0, const svalue *arg1)
822 108139 : : m_type (type), m_op (op), m_arg0 (arg0), m_arg1 (arg1)
823 : {}
824 :
825 717937 : hashval_t hash () const
826 : {
827 717937 : inchash::hash hstate;
828 717937 : hstate.add_ptr (m_type);
829 717937 : hstate.add_int (m_op);
830 717937 : hstate.add_ptr (m_arg0);
831 717937 : hstate.add_ptr (m_arg1);
832 717937 : return hstate.end ();
833 : }
834 :
835 720636 : bool operator== (const key_t &other) const
836 : {
837 720636 : return (m_type == other.m_type
838 326764 : && m_op == other.m_op
839 255226 : && m_arg0 == other.m_arg0
840 858261 : && m_arg1 == other.m_arg1);
841 : }
842 :
843 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
844 102480 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
845 802241 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
846 2676305 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
847 :
848 : tree m_type;
849 : enum tree_code m_op;
850 : const svalue *m_arg0;
851 : const svalue *m_arg1;
852 : };
853 :
854 21017 : binop_svalue (symbol::id_t id, tree type, enum tree_code op,
855 : const svalue *arg0, const svalue *arg1)
856 21017 : : svalue (complexity::from_pair (arg0->get_complexity (),
857 : arg1->get_complexity ()),
858 : id,
859 : type),
860 21017 : m_op (op), m_arg0 (arg0), m_arg1 (arg1)
861 : {
862 21017 : gcc_assert (arg0->can_have_associated_state_p ());
863 21017 : gcc_assert (arg1->can_have_associated_state_p ());
864 21017 : }
865 :
866 20418550 : enum svalue_kind get_kind () const final override { return SK_BINOP; }
867 136813 : const binop_svalue *dyn_cast_binop_svalue () const final override
868 : {
869 136813 : return this;
870 : }
871 :
872 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
873 :
874 : void
875 : print_dump_widget_label (pretty_printer *pp) const final override;
876 : void
877 : add_dump_widget_children (text_art::tree_widget &w,
878 : const dump_widget_info &dwi) const final override;
879 :
880 : void accept (visitor *v) const final override;
881 : bool implicitly_live_p (const svalue_set *,
882 : const region_model *) const final override;
883 :
884 : bool maybe_get_value_range_1 (value_range &out) const final override;
885 :
886 5111396 : enum tree_code get_op () const { return m_op; }
887 3447799 : const svalue *get_arg0 () const { return m_arg0; }
888 2259946 : const svalue *get_arg1 () const { return m_arg1; }
889 :
890 : private:
891 : enum tree_code m_op;
892 : const svalue *m_arg0;
893 : const svalue *m_arg1;
894 : };
895 :
896 : } // namespace ana
897 :
898 : template <>
899 : template <>
900 : inline bool
901 287757 : is_a_helper <const binop_svalue *>::test (const svalue *sval)
902 : {
903 287757 : return sval->get_kind () == SK_BINOP;
904 : }
905 :
906 : template <> struct default_hash_traits<binop_svalue::key_t>
907 : : public member_function_hash_traits<binop_svalue::key_t>
908 : {
909 : static const bool empty_zero_p = false;
910 : };
911 :
912 : namespace ana {
913 :
914 : /* Concrete subclass of svalue representing the result of accessing a subregion
915 : of another svalue (the value of a component/field of a struct, or an element
916 : from an array). */
917 :
918 : class sub_svalue : public svalue
919 : {
920 : public:
921 : /* A support class for uniquifying instances of sub_svalue. */
922 : struct key_t
923 : {
924 16198 : key_t (tree type, const svalue *parent_svalue, const region *subregion)
925 16198 : : m_type (type), m_parent_svalue (parent_svalue), m_subregion (subregion)
926 : {}
927 :
928 105449 : hashval_t hash () const
929 : {
930 105449 : inchash::hash hstate;
931 105449 : hstate.add_ptr (m_type);
932 105449 : hstate.add_ptr (m_parent_svalue);
933 105449 : hstate.add_ptr (m_subregion);
934 105449 : return hstate.end ();
935 : }
936 :
937 102271 : bool operator== (const key_t &other) const
938 : {
939 102271 : return (m_type == other.m_type
940 57197 : && m_parent_svalue == other.m_parent_svalue
941 143549 : && m_subregion == other.m_subregion);
942 : }
943 :
944 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
945 55504 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
946 114340 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
947 461504 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
948 :
949 : tree m_type;
950 : const svalue *m_parent_svalue;
951 : const region *m_subregion;
952 : };
953 : sub_svalue (symbol::id_t id, tree type, const svalue *parent_svalue,
954 : const region *subregion);
955 :
956 1409542 : enum svalue_kind get_kind () const final override { return SK_SUB; }
957 20340 : const sub_svalue *dyn_cast_sub_svalue () const final override
958 : {
959 20340 : return this;
960 : }
961 :
962 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
963 :
964 : void
965 : print_dump_widget_label (pretty_printer *pp) const final override;
966 : void
967 : add_dump_widget_children (text_art::tree_widget &w,
968 : const dump_widget_info &dwi) const final override;
969 :
970 : void accept (visitor *v) const final override;
971 : bool implicitly_live_p (const svalue_set *,
972 : const region_model *) const final override;
973 :
974 1018554 : const svalue *get_parent () const { return m_parent_svalue; }
975 808101 : const region *get_subregion () const { return m_subregion; }
976 :
977 : private:
978 : const svalue *m_parent_svalue;
979 : const region *m_subregion;
980 : };
981 :
982 : } // namespace ana
983 :
984 : template <>
985 : template <>
986 : inline bool
987 0 : is_a_helper <const sub_svalue *>::test (const svalue *sval)
988 : {
989 0 : return sval->get_kind () == SK_SUB;
990 : }
991 :
992 : template <> struct default_hash_traits<sub_svalue::key_t>
993 : : public member_function_hash_traits<sub_svalue::key_t>
994 : {
995 : static const bool empty_zero_p = false;
996 : };
997 :
998 : namespace ana {
999 :
1000 : /* Concrete subclass of svalue representing repeating an inner svalue
1001 : (possibly not a whole number of times) to fill a larger region of
1002 : type TYPE of size OUTER_SIZE bytes. */
1003 :
1004 : class repeated_svalue : public svalue
1005 : {
1006 : public:
1007 : /* A support class for uniquifying instances of repeated_svalue. */
1008 : struct key_t
1009 : {
1010 2016 : key_t (tree type,
1011 : const svalue *outer_size,
1012 : const svalue *inner_svalue)
1013 2016 : : m_type (type), m_outer_size (outer_size), m_inner_svalue (inner_svalue)
1014 : {}
1015 :
1016 9507 : hashval_t hash () const
1017 : {
1018 9507 : inchash::hash hstate;
1019 9507 : hstate.add_ptr (m_type);
1020 9507 : hstate.add_ptr (m_outer_size);
1021 9507 : hstate.add_ptr (m_inner_svalue);
1022 9507 : return hstate.end ();
1023 : }
1024 :
1025 8156 : bool operator== (const key_t &other) const
1026 : {
1027 8156 : return (m_type == other.m_type
1028 8039 : && m_outer_size == other.m_outer_size
1029 9724 : && m_inner_svalue == other.m_inner_svalue);
1030 : }
1031 :
1032 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1033 52938 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
1034 10196 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1035 148138 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
1036 :
1037 : tree m_type;
1038 : const svalue *m_outer_size;
1039 : const svalue *m_inner_svalue;
1040 : };
1041 : repeated_svalue (symbol::id_t id,
1042 : tree type,
1043 : const svalue *outer_size,
1044 : const svalue *inner_svalue);
1045 :
1046 149055 : enum svalue_kind get_kind () const final override { return SK_REPEATED; }
1047 100 : const repeated_svalue *dyn_cast_repeated_svalue () const final override
1048 : {
1049 100 : return this;
1050 : }
1051 :
1052 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1053 :
1054 : void
1055 : print_dump_widget_label (pretty_printer *pp) const final override;
1056 : void
1057 : add_dump_widget_children (text_art::tree_widget &w,
1058 : const dump_widget_info &dwi) const final override;
1059 :
1060 : void accept (visitor *v) const final override;
1061 :
1062 54 : const svalue *get_outer_size () const { return m_outer_size; }
1063 449 : const svalue *get_inner_svalue () const { return m_inner_svalue; }
1064 :
1065 : bool all_zeroes_p () const final override;
1066 :
1067 : const svalue *
1068 : maybe_fold_bits_within (tree type,
1069 : const bit_range &subrange,
1070 : region_model_manager *mgr) const final override;
1071 :
1072 : private:
1073 : const svalue *m_outer_size;
1074 : const svalue *m_inner_svalue;
1075 : };
1076 :
1077 : } // namespace ana
1078 :
1079 : template <>
1080 : template <>
1081 : inline bool
1082 42 : is_a_helper <const repeated_svalue *>::test (const svalue *sval)
1083 : {
1084 42 : return sval->get_kind () == SK_REPEATED;
1085 : }
1086 :
1087 : template <> struct default_hash_traits<repeated_svalue::key_t>
1088 : : public member_function_hash_traits<repeated_svalue::key_t>
1089 : {
1090 : static const bool empty_zero_p = false;
1091 : };
1092 :
1093 : namespace ana {
1094 :
1095 : /* A range of bits/bytes within another svalue
1096 : e.g. bytes 5-39 of INITIAL_SVALUE(R).
1097 : These can be generated for prefixes and suffixes when part of a binding
1098 : is clobbered, so that we don't lose too much information. */
1099 :
1100 : class bits_within_svalue : public svalue
1101 : {
1102 : public:
1103 : /* A support class for uniquifying instances of bits_within_svalue. */
1104 : struct key_t
1105 : {
1106 1511 : key_t (tree type,
1107 : const bit_range &bits,
1108 : const svalue *inner_svalue)
1109 1511 : : m_type (type), m_bits (bits), m_inner_svalue (inner_svalue)
1110 : {}
1111 :
1112 9723 : hashval_t hash () const
1113 : {
1114 9723 : inchash::hash hstate;
1115 9723 : hstate.add_ptr (m_type);
1116 9723 : hstate.add_ptr (m_inner_svalue);
1117 9723 : return hstate.end ();
1118 : }
1119 :
1120 10161 : bool operator== (const key_t &other) const
1121 : {
1122 10161 : return (m_type == other.m_type
1123 8505 : && m_bits == other.m_bits
1124 11539 : && m_inner_svalue == other.m_inner_svalue);
1125 : }
1126 :
1127 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1128 53844 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
1129 15467 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1130 157729 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
1131 :
1132 : tree m_type;
1133 : bit_range m_bits;
1134 : const svalue *m_inner_svalue;
1135 : };
1136 : bits_within_svalue (symbol::id_t id,
1137 : tree type,
1138 : const bit_range &bits,
1139 : const svalue *inner_svalue);
1140 :
1141 180820 : enum svalue_kind get_kind () const final override { return SK_BITS_WITHIN; }
1142 : const bits_within_svalue *
1143 0 : dyn_cast_bits_within_svalue () const final override
1144 : {
1145 0 : return this;
1146 : }
1147 :
1148 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1149 :
1150 : void
1151 : print_dump_widget_label (pretty_printer *pp) const final override;
1152 : void
1153 : add_dump_widget_children (text_art::tree_widget &w,
1154 : const dump_widget_info &dwi) const final override;
1155 :
1156 : void accept (visitor *v) const final override;
1157 : bool implicitly_live_p (const svalue_set *,
1158 : const region_model *) const final override;
1159 :
1160 451 : const bit_range &get_bits () const { return m_bits; }
1161 78 : const svalue *get_inner_svalue () const { return m_inner_svalue; }
1162 :
1163 : const svalue *
1164 : maybe_fold_bits_within (tree type,
1165 : const bit_range &subrange,
1166 : region_model_manager *mgr) const final override;
1167 :
1168 : private:
1169 : const bit_range m_bits;
1170 : const svalue *m_inner_svalue;
1171 : };
1172 :
1173 : } // namespace ana
1174 :
1175 : template <>
1176 : template <>
1177 : inline bool
1178 0 : is_a_helper <const bits_within_svalue *>::test (const svalue *sval)
1179 : {
1180 0 : return sval->get_kind () == SK_BITS_WITHIN;
1181 : }
1182 :
1183 : template <> struct default_hash_traits<bits_within_svalue::key_t>
1184 : : public member_function_hash_traits<bits_within_svalue::key_t>
1185 : {
1186 : static const bool empty_zero_p = false;
1187 : };
1188 :
1189 : namespace ana {
1190 :
1191 : /* Concrete subclass of svalue: decorate another svalue,
1192 : so that the resulting svalue can be identified as being
1193 : "interesting to control flow".
1194 : For example, consider the return value from setjmp. We
1195 : don't want to merge states in which the result is 0 with
1196 : those in which the result is non-zero. By using an
1197 : unmergeable_svalue for the result, we can inhibit such merges
1198 : and have separate exploded nodes for those states, keeping
1199 : the first and second returns from setjmp distinct in the exploded
1200 : graph. */
1201 :
1202 : class unmergeable_svalue : public svalue
1203 : {
1204 : public:
1205 210 : unmergeable_svalue (symbol::id_t id, const svalue *arg)
1206 210 : : svalue (complexity (arg), id, arg->get_type ()), m_arg (arg)
1207 : {
1208 210 : }
1209 :
1210 22648 : enum svalue_kind get_kind () const final override { return SK_UNMERGEABLE; }
1211 : const unmergeable_svalue *
1212 4370 : dyn_cast_unmergeable_svalue () const final override { return this; }
1213 :
1214 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1215 :
1216 : void
1217 : print_dump_widget_label (pretty_printer *pp) const final override;
1218 : void
1219 : add_dump_widget_children (text_art::tree_widget &w,
1220 : const dump_widget_info &dwi) const final override;
1221 :
1222 : void accept (visitor *v) const final override;
1223 : bool implicitly_live_p (const svalue_set *,
1224 : const region_model *) const final override;
1225 :
1226 5264 : const svalue *get_arg () const { return m_arg; }
1227 :
1228 : private:
1229 : const svalue *m_arg;
1230 : };
1231 :
1232 : } // namespace ana
1233 :
1234 : template <>
1235 : template <>
1236 : inline bool
1237 0 : is_a_helper <const unmergeable_svalue *>::test (const svalue *sval)
1238 : {
1239 0 : return sval->get_kind () == SK_UNMERGEABLE;
1240 : }
1241 :
1242 : namespace ana {
1243 :
1244 : /* Concrete subclass of svalue for use in selftests, where
1245 : we want a specific but unknown svalue.
1246 : Unlike other svalue subclasses these aren't managed by
1247 : region_model_manager. */
1248 :
1249 28 : class placeholder_svalue : public svalue
1250 : {
1251 : public:
1252 12449 : placeholder_svalue (symbol::id_t id, tree type, const char *name)
1253 12449 : : svalue (complexity (1, 1), id, type), m_name (name)
1254 : {
1255 : }
1256 :
1257 33898 : enum svalue_kind get_kind () const final override { return SK_PLACEHOLDER; }
1258 :
1259 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1260 :
1261 : void
1262 : print_dump_widget_label (pretty_printer *pp) const final override;
1263 : void
1264 : add_dump_widget_children (text_art::tree_widget &w,
1265 : const dump_widget_info &dwi) const final override;
1266 :
1267 : void accept (visitor *v) const final override;
1268 :
1269 0 : const char *get_name () const { return m_name; }
1270 :
1271 : private:
1272 : const char *m_name;
1273 : };
1274 :
1275 : } // namespace ana
1276 :
1277 : template <>
1278 : template <>
1279 : inline bool
1280 : is_a_helper <const placeholder_svalue *>::test (const svalue *sval)
1281 : {
1282 : return sval->get_kind () == SK_PLACEHOLDER;
1283 : }
1284 :
1285 : namespace ana {
1286 :
1287 : /* Concrete subclass of svalue representing a "widening" seen when merging
1288 : states, widening from a base value to {base value, iter value} and thus
1289 : representing a possible fixed point in an iteration from the base to
1290 : +ve infinity, or -ve infinity, and thus useful for representing a value
1291 : within a loop.
1292 : We also need to capture the program_point at which the merger happens,
1293 : so that distinguish between different iterators, and thus handle
1294 : nested loops. (currently we capture the function_point instead, for
1295 : simplicity of hashing). */
1296 :
1297 : class widening_svalue : public svalue
1298 : {
1299 : public:
1300 : /* A support class for uniquifying instances of widening_svalue. */
1301 : struct key_t
1302 : {
1303 5772 : key_t (tree type, const supernode *snode,
1304 : const svalue *base_sval, const svalue *iter_sval)
1305 5772 : : m_type (type), m_snode (snode),
1306 5772 : m_base_sval (base_sval), m_iter_sval (iter_sval)
1307 : {}
1308 :
1309 35820 : hashval_t hash () const
1310 : {
1311 35820 : inchash::hash hstate;
1312 35820 : hstate.add_ptr (m_base_sval);
1313 35820 : hstate.add_ptr (m_iter_sval);
1314 35820 : return hstate.end ();
1315 : }
1316 :
1317 65594 : bool operator== (const key_t &other) const
1318 : {
1319 65594 : return (m_type == other.m_type
1320 54529 : && m_snode == other.m_snode
1321 4400 : && m_base_sval == other.m_base_sval
1322 69176 : && m_iter_sval == other.m_iter_sval);
1323 : }
1324 :
1325 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1326 54344 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
1327 90881 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1328 356802 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
1329 :
1330 : tree m_type;
1331 : const supernode *m_snode;
1332 : const svalue *m_base_sval;
1333 : const svalue *m_iter_sval;
1334 : };
1335 :
1336 : enum direction_t
1337 : {
1338 : DIR_ASCENDING,
1339 : DIR_DESCENDING,
1340 : DIR_UNKNOWN
1341 : };
1342 :
1343 2361 : widening_svalue (symbol::id_t id, tree type, const supernode *snode,
1344 : const svalue *base_sval, const svalue *iter_sval)
1345 2361 : : svalue (complexity::from_pair (base_sval->get_complexity (),
1346 : iter_sval->get_complexity ()),
1347 : id,
1348 : type),
1349 2361 : m_snode (snode),
1350 2361 : m_base_sval (base_sval), m_iter_sval (iter_sval)
1351 : {
1352 2361 : gcc_assert (base_sval->can_have_associated_state_p ());
1353 2361 : gcc_assert (iter_sval->can_have_associated_state_p ());
1354 2361 : }
1355 :
1356 1065514 : enum svalue_kind get_kind () const final override { return SK_WIDENING; }
1357 18800 : const widening_svalue *dyn_cast_widening_svalue () const final override
1358 : {
1359 18800 : return this;
1360 : }
1361 :
1362 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1363 :
1364 : void
1365 : print_dump_widget_label (pretty_printer *pp) const final override;
1366 : void
1367 : add_dump_widget_children (text_art::tree_widget &w,
1368 : const dump_widget_info &dwi) const final override;
1369 :
1370 : void accept (visitor *v) const final override;
1371 :
1372 3595 : const supernode *get_snode () const { return m_snode; }
1373 14202 : const svalue *get_base_svalue () const { return m_base_sval; }
1374 4813 : const svalue *get_iter_svalue () const { return m_iter_sval; }
1375 :
1376 : enum direction_t get_direction () const;
1377 :
1378 : tristate eval_condition_without_cm (enum tree_code op,
1379 : tree rhs_cst) const;
1380 :
1381 : private:
1382 : const supernode *m_snode;
1383 : const svalue *m_base_sval;
1384 : const svalue *m_iter_sval;
1385 : };
1386 :
1387 : } // namespace ana
1388 :
1389 : template <>
1390 : template <>
1391 : inline bool
1392 454 : is_a_helper <const widening_svalue *>::test (const svalue *sval)
1393 : {
1394 454 : return sval->get_kind () == SK_WIDENING;
1395 : }
1396 :
1397 : template <> struct default_hash_traits<widening_svalue::key_t>
1398 : : public member_function_hash_traits<widening_svalue::key_t>
1399 : {
1400 : static const bool empty_zero_p = false;
1401 : };
1402 :
1403 : namespace ana {
1404 :
1405 : /* Concrete subclass of svalue representing a mapping of bit-ranges
1406 : to svalues, analogous to a cluster within the store, but without
1407 : symbolic keys.
1408 :
1409 : This is for use in places where we want to represent a store-like
1410 : mapping, but are required to use an svalue, such as when handling
1411 : compound assignments and compound return values.
1412 :
1413 : Instances of this class shouldn't be bound as-is into the store;
1414 : instead they should be unpacked. Similarly, they should not be
1415 : nested. */
1416 :
1417 : class compound_svalue : public svalue
1418 : {
1419 : public:
1420 : typedef concrete_binding_map::const_iterator const_iterator_t;
1421 : typedef concrete_binding_map::iterator iterator_t;
1422 :
1423 : /* A support class for uniquifying instances of compound_svalue.
1424 : Note that to avoid copies, keys store pointers to
1425 : concrete_binding_map, rather than the maps themselves. */
1426 : struct key_t
1427 : {
1428 4631 : key_t (tree type, const concrete_binding_map *map_ptr)
1429 3970 : : m_type (type), m_map_ptr (map_ptr)
1430 : {}
1431 :
1432 18404 : hashval_t hash () const
1433 : {
1434 18404 : inchash::hash hstate;
1435 18404 : hstate.add_ptr (m_type);
1436 : //hstate.add_ptr (m_map_ptr); // TODO
1437 18404 : return hstate.end ();
1438 : }
1439 :
1440 21833 : bool operator== (const key_t &other) const
1441 : {
1442 21833 : return (m_type == other.m_type
1443 21833 : && *m_map_ptr == *other.m_map_ptr);
1444 : }
1445 :
1446 : void mark_deleted () { m_type = reinterpret_cast<tree> (1); }
1447 52723 : void mark_empty () { m_type = reinterpret_cast<tree> (2); }
1448 33026 : bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); }
1449 210021 : bool is_empty () const { return m_type == reinterpret_cast<tree> (2); }
1450 :
1451 : tree m_type;
1452 : const concrete_binding_map *m_map_ptr;
1453 : };
1454 :
1455 : compound_svalue (symbol::id_t id, tree type, concrete_binding_map &&map);
1456 : compound_svalue (symbol::id_t id, tree type, const concrete_binding_map &map);
1457 :
1458 6943 : enum svalue_kind get_kind () const final override { return SK_COMPOUND; }
1459 4209 : const compound_svalue *dyn_cast_compound_svalue () const final override
1460 : {
1461 4209 : 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 : const concrete_binding_map &
1475 137 : get_concrete_bindings () const { return m_map; }
1476 :
1477 4400 : const_iterator_t begin () const { return m_map.begin (); }
1478 14563 : const_iterator_t end () const { return m_map.end (); }
1479 661 : iterator_t begin () { return m_map.begin (); }
1480 661 : iterator_t end () { return m_map.end (); }
1481 :
1482 661 : struct key_t make_key () const
1483 : {
1484 661 : return key_t (get_type (), &m_map);
1485 : }
1486 :
1487 : const svalue *
1488 : maybe_fold_bits_within (tree type,
1489 : const bit_range &subrange,
1490 : region_model_manager *mgr) const final override;
1491 :
1492 : private:
1493 : concrete_binding_map m_map;
1494 : };
1495 :
1496 : } // namespace ana
1497 :
1498 : template <>
1499 : template <>
1500 : inline bool
1501 295 : is_a_helper <const compound_svalue *>::test (const svalue *sval)
1502 : {
1503 295 : return sval->get_kind () == SK_COMPOUND;
1504 : }
1505 :
1506 : template <> struct default_hash_traits<compound_svalue::key_t>
1507 : : public member_function_hash_traits<compound_svalue::key_t>
1508 : {
1509 : static const bool empty_zero_p = false;
1510 : };
1511 :
1512 : namespace ana {
1513 :
1514 : /* A bundle of state for purging information from a program_state about
1515 : a conjured_svalue. We pass this whenever calling
1516 : get_or_create_conjured_svalue, so that if the program_state already
1517 : has information about this conjured_svalue on an execution path, we
1518 : can purge that information, to avoid the analyzer confusing the two
1519 : values as being the same. */
1520 :
1521 : class conjured_purge
1522 : {
1523 : public:
1524 42573 : conjured_purge (region_model *model, region_model_context *ctxt)
1525 42425 : : m_model (model), m_ctxt (ctxt)
1526 : {
1527 : }
1528 : void purge (const conjured_svalue *sval) const;
1529 :
1530 : private:
1531 : region_model *m_model;
1532 : region_model_context *m_ctxt;
1533 : };
1534 :
1535 : /* A defined value arising from a statement, where we want to identify a
1536 : particular unknown value, rather than resorting to the unknown_value
1537 : singleton, so that the value can have sm-state.
1538 :
1539 : Comparisons of variables that share the same conjured_svalue are known
1540 : to be equal, even if we don't know what the value is.
1541 :
1542 : For example, this is used for the values of regions that may have been
1543 : touched when calling an unknown function.
1544 :
1545 : The value captures a region as well as a stmt in order to avoid falsely
1546 : aliasing the various values that could arise in one statement. For
1547 : example, after:
1548 : unknown_fn (&a, &b);
1549 : we want values to clobber a and b with, but we don't want to use the
1550 : same value, or it would falsely implicitly assume that a == b. */
1551 :
1552 : class conjured_svalue : public svalue
1553 : {
1554 : public:
1555 : /* A support class for uniquifying instances of conjured_svalue. */
1556 : struct key_t
1557 : {
1558 56892 : key_t (tree type, const gimple *stmt, const region *id_reg, unsigned idx)
1559 56892 : : m_type (type), m_stmt (stmt), m_id_reg (id_reg), m_idx (idx)
1560 : {}
1561 :
1562 498130 : hashval_t hash () const
1563 : {
1564 498130 : inchash::hash hstate;
1565 498130 : hstate.add_ptr (m_type);
1566 498130 : hstate.add_ptr (m_stmt);
1567 498130 : hstate.add_ptr (m_id_reg);
1568 498130 : return hstate.end ();
1569 : }
1570 :
1571 500685 : bool operator== (const key_t &other) const
1572 : {
1573 500685 : return (m_type == other.m_type
1574 219894 : && m_stmt == other.m_stmt
1575 51287 : && m_id_reg == other.m_id_reg
1576 541220 : && m_idx == other.m_idx);
1577 : }
1578 :
1579 : /* Use m_stmt to mark empty/deleted, as m_type can be NULL_TREE for
1580 : legitimate instances. */
1581 : void mark_deleted () { m_stmt = reinterpret_cast<const gimple *> (1); }
1582 0 : void mark_empty () { m_stmt = nullptr; }
1583 597447 : bool is_deleted () const
1584 : {
1585 597447 : return m_stmt == reinterpret_cast<const gimple *> (1);
1586 : }
1587 1972289 : bool is_empty () const { return m_stmt == nullptr; }
1588 :
1589 : tree m_type;
1590 : const gimple *m_stmt;
1591 : const region *m_id_reg;
1592 : unsigned m_idx;
1593 : };
1594 :
1595 26691 : conjured_svalue (symbol::id_t id, tree type, const gimple *stmt,
1596 : const region *id_reg, unsigned idx)
1597 26691 : : svalue (complexity (id_reg), id, type),
1598 26691 : m_stmt (stmt), m_id_reg (id_reg), m_idx (idx)
1599 : {
1600 26691 : gcc_assert (m_stmt != nullptr);
1601 26691 : }
1602 :
1603 21990873 : enum svalue_kind get_kind () const final override { return SK_CONJURED; }
1604 0 : const conjured_svalue *dyn_cast_conjured_svalue () const final override
1605 : {
1606 0 : return this;
1607 : }
1608 :
1609 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1610 :
1611 : void
1612 : print_dump_widget_label (pretty_printer *pp) const final override;
1613 : void
1614 : add_dump_widget_children (text_art::tree_widget &w,
1615 : const dump_widget_info &dwi) const final override;
1616 :
1617 : void accept (visitor *v) const final override;
1618 :
1619 3183157 : const gimple *get_stmt () const { return m_stmt; }
1620 74316 : const region *get_id_region () const { return m_id_reg; }
1621 : bool lhs_value_p () const;
1622 :
1623 : private:
1624 : const gimple *m_stmt;
1625 : const region *m_id_reg;
1626 : unsigned m_idx;
1627 : };
1628 :
1629 : } // namespace ana
1630 :
1631 : template <>
1632 : template <>
1633 : inline bool
1634 : is_a_helper <const conjured_svalue *>::test (const svalue *sval)
1635 : {
1636 : return sval->get_kind () == SK_CONJURED;
1637 : }
1638 :
1639 : template <> struct default_hash_traits<conjured_svalue::key_t>
1640 : : public member_function_hash_traits<conjured_svalue::key_t>
1641 : {
1642 : static const bool empty_zero_p = true;
1643 : };
1644 :
1645 : namespace ana {
1646 :
1647 : /* An output from a deterministic asm stmt, where we want to identify a
1648 : particular unknown value, rather than resorting to the unknown_value
1649 : singleton.
1650 :
1651 : Comparisons of variables that share the same asm_output_svalue are known
1652 : to be equal, even if we don't know what the value is. */
1653 :
1654 : class asm_output_svalue : public svalue
1655 : {
1656 : public:
1657 : /* Imposing an upper limit and using a (small) array allows key_t
1658 : to avoid memory management. */
1659 : static const unsigned MAX_INPUTS = 2;
1660 :
1661 : /* A support class for uniquifying instances of asm_output_svalue. */
1662 : struct key_t
1663 : {
1664 358 : key_t (tree type,
1665 : const char *asm_string,
1666 : unsigned output_idx,
1667 : const vec<const svalue *> &inputs)
1668 358 : : m_type (type), m_asm_string (asm_string), m_output_idx (output_idx),
1669 358 : m_num_inputs (inputs.length ())
1670 : {
1671 358 : gcc_assert (inputs.length () <= MAX_INPUTS);
1672 958 : for (unsigned i = 0; i < m_num_inputs; i++)
1673 600 : m_input_arr[i] = inputs[i];
1674 358 : }
1675 :
1676 1500 : hashval_t hash () const
1677 : {
1678 1500 : inchash::hash hstate;
1679 1500 : hstate.add_ptr (m_type);
1680 : /* We don't bother hashing m_asm_str. */
1681 1500 : hstate.add_int (m_output_idx);
1682 4079 : for (unsigned i = 0; i < m_num_inputs; i++)
1683 2579 : hstate.add_ptr (m_input_arr[i]);
1684 1500 : return hstate.end ();
1685 : }
1686 :
1687 1059 : bool operator== (const key_t &other) const
1688 : {
1689 1059 : if (!(m_type == other.m_type
1690 850 : && 0 == (strcmp (m_asm_string, other.m_asm_string))
1691 755 : && m_output_idx == other.m_output_idx
1692 585 : && m_num_inputs == other.m_num_inputs))
1693 : return false;
1694 1031 : for (unsigned i = 0; i < m_num_inputs; i++)
1695 865 : if (m_input_arr[i] != other.m_input_arr[i])
1696 : return false;
1697 : return true;
1698 : }
1699 :
1700 : /* Use m_asm_string to mark empty/deleted, as m_type can be NULL_TREE for
1701 : legitimate instances. */
1702 : void mark_deleted () { m_asm_string = reinterpret_cast<const char *> (1); }
1703 0 : void mark_empty () { m_asm_string = nullptr; }
1704 1559 : bool is_deleted () const
1705 : {
1706 1559 : return m_asm_string == reinterpret_cast<const char *> (1);
1707 : }
1708 113486 : bool is_empty () const { return m_asm_string == nullptr; }
1709 :
1710 : tree m_type;
1711 : const char *m_asm_string;
1712 : unsigned m_output_idx;
1713 : unsigned m_num_inputs;
1714 : const svalue *m_input_arr[MAX_INPUTS];
1715 : };
1716 :
1717 192 : asm_output_svalue (symbol::id_t id,
1718 : tree type,
1719 : const char *asm_string,
1720 : unsigned output_idx,
1721 : unsigned num_outputs,
1722 : const vec<const svalue *> &inputs)
1723 192 : : svalue (complexity::from_vec_svalue (inputs), id, type),
1724 192 : m_asm_string (asm_string),
1725 192 : m_output_idx (output_idx),
1726 192 : m_num_outputs (num_outputs),
1727 192 : m_num_inputs (inputs.length ())
1728 : {
1729 192 : gcc_assert (inputs.length () <= MAX_INPUTS);
1730 488 : for (unsigned i = 0; i < m_num_inputs; i++)
1731 296 : m_input_arr[i] = inputs[i];
1732 192 : }
1733 :
1734 18478 : enum svalue_kind get_kind () const final override { return SK_ASM_OUTPUT; }
1735 : const asm_output_svalue *
1736 0 : dyn_cast_asm_output_svalue () const final override
1737 : {
1738 0 : return this;
1739 : }
1740 :
1741 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1742 :
1743 : void
1744 : print_dump_widget_label (pretty_printer *pp) const final override;
1745 : void
1746 : add_dump_widget_children (text_art::tree_widget &w,
1747 : const dump_widget_info &dwi) const final override;
1748 :
1749 : void accept (visitor *v) const final override;
1750 :
1751 102 : const char *get_asm_string () const { return m_asm_string; }
1752 154 : unsigned get_output_idx () const { return m_output_idx; }
1753 78 : unsigned get_num_outputs () const { return m_num_outputs; }
1754 312 : unsigned get_num_inputs () const { return m_num_inputs; }
1755 164 : const svalue *get_input (unsigned idx) const { return m_input_arr[idx]; }
1756 :
1757 : private:
1758 : void dump_input (pretty_printer *pp,
1759 : unsigned input_idx,
1760 : const svalue *sval,
1761 : bool simple) const;
1762 : unsigned input_idx_to_asm_idx (unsigned input_idx) const;
1763 :
1764 : const char *m_asm_string;
1765 : unsigned m_output_idx;
1766 :
1767 : /* We capture this so that we can offset the input indices
1768 : to match the %0, %1, %2 in the asm_string when dumping. */
1769 : unsigned m_num_outputs;
1770 :
1771 : unsigned m_num_inputs;
1772 : const svalue *m_input_arr[MAX_INPUTS];
1773 : };
1774 :
1775 : } // namespace ana
1776 :
1777 : template <>
1778 : template <>
1779 : inline bool
1780 8 : is_a_helper <const asm_output_svalue *>::test (const svalue *sval)
1781 : {
1782 8 : return sval->get_kind () == SK_ASM_OUTPUT;
1783 : }
1784 :
1785 : template <> struct default_hash_traits<asm_output_svalue::key_t>
1786 : : public member_function_hash_traits<asm_output_svalue::key_t>
1787 : {
1788 : static const bool empty_zero_p = true;
1789 : };
1790 :
1791 : namespace ana {
1792 :
1793 : /* The return value from a function with __attribute((const)) for given
1794 : inputs, provided that we don't have too many inputs, and all of them
1795 : are deterministic.
1796 :
1797 : Comparisons of variables that share the same const_fn_result_svalue are known
1798 : to be equal, even if we don't know what the value is. */
1799 :
1800 : class const_fn_result_svalue : public svalue
1801 : {
1802 : public:
1803 : /* Imposing an upper limit and using a (small) array allows key_t
1804 : to avoid memory management. */
1805 : static const unsigned MAX_INPUTS = 2;
1806 :
1807 : /* A support class for uniquifying instances of const_fn_result_svalue. */
1808 : struct key_t
1809 : {
1810 955 : key_t (tree type,
1811 : tree fndecl,
1812 : const vec<const svalue *> &inputs)
1813 955 : : m_type (type), m_fndecl (fndecl),
1814 955 : m_num_inputs (inputs.length ())
1815 : {
1816 955 : gcc_assert (inputs.length () <= MAX_INPUTS);
1817 1421 : for (unsigned i = 0; i < m_num_inputs; i++)
1818 466 : m_input_arr[i] = inputs[i];
1819 955 : }
1820 :
1821 3113 : hashval_t hash () const
1822 : {
1823 3113 : inchash::hash hstate;
1824 3113 : hstate.add_ptr (m_type);
1825 3113 : hstate.add_ptr (m_fndecl);
1826 5716 : for (unsigned i = 0; i < m_num_inputs; i++)
1827 2603 : hstate.add_ptr (m_input_arr[i]);
1828 3113 : return hstate.end ();
1829 : }
1830 :
1831 2317 : bool operator== (const key_t &other) const
1832 : {
1833 2317 : if (!(m_type == other.m_type
1834 2170 : && m_fndecl == other.m_fndecl
1835 1534 : && m_num_inputs == other.m_num_inputs))
1836 : return false;
1837 1930 : for (unsigned i = 0; i < m_num_inputs; i++)
1838 1162 : if (m_input_arr[i] != other.m_input_arr[i])
1839 : return false;
1840 : return true;
1841 : }
1842 :
1843 : /* Use m_fndecl to mark empty/deleted. */
1844 : void mark_deleted () { m_fndecl = reinterpret_cast<tree> (1); }
1845 0 : void mark_empty () { m_fndecl = NULL_TREE; }
1846 3299 : bool is_deleted () const
1847 : {
1848 3299 : return m_fndecl == reinterpret_cast<tree> (1);
1849 : }
1850 122865 : bool is_empty () const { return m_fndecl == NULL_TREE; }
1851 :
1852 : tree m_type;
1853 : tree m_fndecl;
1854 : unsigned m_num_inputs;
1855 : const svalue *m_input_arr[MAX_INPUTS];
1856 : };
1857 :
1858 187 : const_fn_result_svalue (symbol::id_t id,
1859 : tree type,
1860 : tree fndecl,
1861 : const vec<const svalue *> &inputs)
1862 187 : : svalue (complexity::from_vec_svalue (inputs), id, type),
1863 187 : m_fndecl (fndecl),
1864 187 : m_num_inputs (inputs.length ())
1865 : {
1866 187 : gcc_assert (inputs.length () <= MAX_INPUTS);
1867 359 : for (unsigned i = 0; i < m_num_inputs; i++)
1868 172 : m_input_arr[i] = inputs[i];
1869 187 : }
1870 :
1871 39184 : enum svalue_kind get_kind () const final override
1872 : {
1873 39184 : return SK_CONST_FN_RESULT;
1874 : }
1875 : const const_fn_result_svalue *
1876 0 : dyn_cast_const_fn_result_svalue () const final override
1877 : {
1878 0 : return this;
1879 : }
1880 :
1881 : void dump_to_pp (pretty_printer *pp, bool simple) const final override;
1882 :
1883 : void
1884 : print_dump_widget_label (pretty_printer *pp) const final override;
1885 : void
1886 : add_dump_widget_children (text_art::tree_widget &w,
1887 : const dump_widget_info &dwi) const final override;
1888 :
1889 : void accept (visitor *v) const final override;
1890 :
1891 146 : tree get_fndecl () const { return m_fndecl; }
1892 258 : unsigned get_num_inputs () const { return m_num_inputs; }
1893 114 : const svalue *get_input (unsigned idx) const { return m_input_arr[idx]; }
1894 :
1895 : private:
1896 : void dump_input (pretty_printer *pp,
1897 : unsigned input_idx,
1898 : const svalue *sval,
1899 : bool simple) const;
1900 :
1901 : tree m_fndecl;
1902 : unsigned m_num_inputs;
1903 : const svalue *m_input_arr[MAX_INPUTS];
1904 : };
1905 :
1906 : } // namespace ana
1907 :
1908 : template <>
1909 : template <>
1910 : inline bool
1911 2 : is_a_helper <const const_fn_result_svalue *>::test (const svalue *sval)
1912 : {
1913 2 : return sval->get_kind () == SK_CONST_FN_RESULT;
1914 : }
1915 :
1916 : template <> struct default_hash_traits<const_fn_result_svalue::key_t>
1917 : : public member_function_hash_traits<const_fn_result_svalue::key_t>
1918 : {
1919 : static const bool empty_zero_p = true;
1920 : };
1921 :
1922 : #endif /* GCC_ANALYZER_SVALUE_H */
|
