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