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