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

source code of gcc/analyzer/svalue.h