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