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 | virtual ~svalue () {} |
93 | |
94 | tree get_type () const { return m_type; } |
95 | |
96 | virtual enum svalue_kind get_kind () const = 0; |
97 | |
98 | void print (const region_model &model, |
99 | pretty_printer *pp) const; |
100 | |
101 | virtual void dump_to_pp (pretty_printer *pp, bool simple) const = 0; |
102 | void dump (bool simple=true) const; |
103 | label_text get_desc (bool simple=true) const; |
104 | |
105 | json::value *to_json () const; |
106 | |
107 | virtual const region_svalue * |
108 | dyn_cast_region_svalue () const { return NULL; } |
109 | virtual const constant_svalue * |
110 | dyn_cast_constant_svalue () const { return NULL; } |
111 | virtual const poisoned_svalue * |
112 | dyn_cast_poisoned_svalue () const { return NULL; } |
113 | virtual const setjmp_svalue * |
114 | dyn_cast_setjmp_svalue () const { return NULL; } |
115 | virtual const initial_svalue * |
116 | dyn_cast_initial_svalue () const { return NULL; } |
117 | virtual const unaryop_svalue * |
118 | dyn_cast_unaryop_svalue () const { return NULL; } |
119 | virtual const binop_svalue * |
120 | dyn_cast_binop_svalue () const { return NULL; } |
121 | virtual const sub_svalue * |
122 | dyn_cast_sub_svalue () const { return NULL; } |
123 | virtual const repeated_svalue * |
124 | dyn_cast_repeated_svalue () const { return NULL; } |
125 | virtual const bits_within_svalue * |
126 | dyn_cast_bits_within_svalue () const { return NULL; } |
127 | virtual const unmergeable_svalue * |
128 | dyn_cast_unmergeable_svalue () const { return NULL; } |
129 | virtual const widening_svalue * |
130 | dyn_cast_widening_svalue () const { return NULL; } |
131 | virtual const compound_svalue * |
132 | dyn_cast_compound_svalue () const { return NULL; } |
133 | virtual const conjured_svalue * |
134 | dyn_cast_conjured_svalue () const { return NULL; } |
135 | virtual const asm_output_svalue * |
136 | dyn_cast_asm_output_svalue () const { return NULL; } |
137 | virtual const const_fn_result_svalue * |
138 | dyn_cast_const_fn_result_svalue () const { return NULL; } |
139 | |
140 | tree maybe_get_constant () const; |
141 | const region *maybe_get_region () const; |
142 | const svalue *maybe_undo_cast () const; |
143 | const svalue *unwrap_any_unmergeable () const; |
144 | |
145 | const svalue *can_merge_p (const svalue *other, |
146 | region_model_manager *mgr, |
147 | model_merger *merger) const; |
148 | |
149 | virtual void accept (visitor *v) const = 0; |
150 | |
151 | bool live_p (const svalue_set *live_svalues, |
152 | const region_model *model) const; |
153 | virtual bool implicitly_live_p (const svalue_set *live_svalues, |
154 | const region_model *model) const; |
155 | |
156 | static int cmp_ptr (const svalue *, const svalue *); |
157 | static int cmp_ptr_ptr (const void *, const void *); |
158 | |
159 | bool involves_p (const svalue *other) const; |
160 | |
161 | const svalue * |
162 | (tree type, |
163 | const bit_range &subrange, |
164 | region_model_manager *mgr) const; |
165 | |
166 | virtual const svalue * |
167 | maybe_fold_bits_within (tree type, |
168 | const bit_range &subrange, |
169 | region_model_manager *mgr) const; |
170 | |
171 | virtual bool all_zeroes_p () const; |
172 | |
173 | /* Can this svalue be involved in constraints and sm-state? |
174 | Most can, but UNKNOWN and POISONED svalues are singletons |
175 | per-type and thus it's meaningless for them to "have state". */ |
176 | virtual bool can_have_associated_state_p () const { return true; } |
177 | |
178 | const region *maybe_get_deref_base_region () const; |
179 | |
180 | bool maybe_print_for_user (pretty_printer *pp, |
181 | const region_model &model, |
182 | const svalue *outer_sval = nullptr) const; |
183 | |
184 | protected: |
185 | svalue (complexity c, symbol::id_t id, tree type) |
186 | : symbol (c, id), m_type (type) |
187 | {} |
188 | |
189 | private: |
190 | tree m_type; |
191 | }; |
192 | |
193 | /* Concrete subclass of svalue representing a pointer value that points to |
194 | a known region */ |
195 | |
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 | key_t (tree type, const region *reg) |
203 | : m_type (type), m_reg (reg) |
204 | {} |
205 | |
206 | hashval_t hash () const |
207 | { |
208 | inchash::hash hstate; |
209 | hstate.add_ptr (ptr: m_type); |
210 | hstate.add_ptr (ptr: m_reg); |
211 | return hstate.end (); |
212 | } |
213 | |
214 | bool operator== (const key_t &other) const |
215 | { |
216 | return (m_type == other.m_type && m_reg == other.m_reg); |
217 | } |
218 | |
219 | void mark_deleted () { m_type = reinterpret_cast<tree> (1); } |
220 | void mark_empty () { m_type = reinterpret_cast<tree> (2); } |
221 | bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } |
222 | bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } |
223 | |
224 | tree m_type; |
225 | const region *m_reg; |
226 | }; |
227 | |
228 | region_svalue (symbol::id_t id, tree type, const region *reg) |
229 | : svalue (complexity (reg), id, type), |
230 | m_reg (reg) |
231 | { |
232 | gcc_assert (m_reg != NULL); |
233 | } |
234 | |
235 | enum svalue_kind get_kind () const final override { return SK_REGION; } |
236 | const region_svalue * |
237 | dyn_cast_region_svalue () const final override { return this; } |
238 | |
239 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
240 | void accept (visitor *v) const final override; |
241 | bool implicitly_live_p (const svalue_set *, |
242 | const region_model *) const final override; |
243 | |
244 | const region * get_pointee () const { return m_reg; } |
245 | |
246 | static tristate eval_condition (const region_svalue *lhs_ptr, |
247 | enum tree_code op, |
248 | const region_svalue *rhs_ptr); |
249 | |
250 | private: |
251 | const region *m_reg; |
252 | }; |
253 | |
254 | } // namespace ana |
255 | |
256 | template <> |
257 | template <> |
258 | inline bool |
259 | is_a_helper <const region_svalue *>::test (const svalue *sval) |
260 | { |
261 | 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 | key_t (tree type, tree cst) |
283 | : m_type (type), m_cst (cst) |
284 | {} |
285 | |
286 | hashval_t hash () const |
287 | { |
288 | inchash::hash hstate; |
289 | hstate.add_ptr (ptr: m_type); |
290 | hstate.add_ptr (ptr: m_cst); |
291 | return hstate.end (); |
292 | } |
293 | |
294 | bool operator== (const key_t &other) const |
295 | { |
296 | return (m_type == other.m_type && m_cst == other.m_cst); |
297 | } |
298 | |
299 | void mark_deleted () { m_type = reinterpret_cast<tree> (1); } |
300 | void mark_empty () { m_type = reinterpret_cast<tree> (2); } |
301 | bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } |
302 | bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } |
303 | |
304 | tree m_type; |
305 | tree m_cst; |
306 | }; |
307 | |
308 | constant_svalue (symbol::id_t id, tree type, tree cst_expr) |
309 | : svalue (complexity (1, 1), id, type), |
310 | m_cst_expr (cst_expr) |
311 | { |
312 | gcc_assert (cst_expr); |
313 | gcc_assert (CONSTANT_CLASS_P (cst_expr)); |
314 | gcc_assert (type == TREE_TYPE (cst_expr) || type == NULL_TREE); |
315 | } |
316 | |
317 | enum svalue_kind get_kind () const final override { return SK_CONSTANT; } |
318 | const constant_svalue * |
319 | dyn_cast_constant_svalue () const final override { return this; } |
320 | |
321 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
322 | void accept (visitor *v) const final override; |
323 | bool implicitly_live_p (const svalue_set *, |
324 | const region_model *) const final override; |
325 | |
326 | tree get_constant () const { return m_cst_expr; } |
327 | static tristate eval_condition (const constant_svalue *lhs, |
328 | enum tree_code op, |
329 | const constant_svalue *rhs); |
330 | |
331 | const svalue * |
332 | maybe_fold_bits_within (tree type, |
333 | const bit_range &subrange, |
334 | region_model_manager *mgr) const final override; |
335 | |
336 | bool all_zeroes_p () const final override; |
337 | |
338 | private: |
339 | tree m_cst_expr; |
340 | }; |
341 | |
342 | } // namespace ana |
343 | |
344 | template <> |
345 | template <> |
346 | inline bool |
347 | is_a_helper <const constant_svalue *>::test (const svalue *sval) |
348 | { |
349 | 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 | unknown_svalue (symbol::id_t id, tree type) |
369 | : svalue (complexity (1, 1), id, type) |
370 | {} |
371 | |
372 | enum svalue_kind get_kind () const final override { return SK_UNKNOWN; } |
373 | |
374 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
375 | void accept (visitor *v) const final override; |
376 | |
377 | const svalue * |
378 | maybe_fold_bits_within (tree type, |
379 | const bit_range &subrange, |
380 | region_model_manager *mgr) const final override; |
381 | |
382 | /* Unknown values are singletons per-type, so can't have state. */ |
383 | bool can_have_associated_state_p () const final override { return false; } |
384 | }; |
385 | |
386 | /* An enum describing a particular kind of "poisoned" value. */ |
387 | |
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 | key_t (enum poison_kind kind, tree type) |
415 | : m_kind (kind), m_type (type) |
416 | {} |
417 | |
418 | hashval_t hash () const |
419 | { |
420 | inchash::hash hstate; |
421 | hstate.add_int (v: m_kind); |
422 | hstate.add_ptr (ptr: m_type); |
423 | return hstate.end (); |
424 | } |
425 | |
426 | bool operator== (const key_t &other) const |
427 | { |
428 | return (m_kind == other.m_kind && m_type == other.m_type); |
429 | } |
430 | |
431 | void mark_deleted () { m_type = reinterpret_cast<tree> (1); } |
432 | void mark_empty () { m_type = reinterpret_cast<tree> (2); } |
433 | bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } |
434 | bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } |
435 | |
436 | enum poison_kind m_kind; |
437 | tree m_type; |
438 | }; |
439 | |
440 | poisoned_svalue (enum poison_kind kind, symbol::id_t id, tree type) |
441 | : svalue (complexity (1, 1), id, type), m_kind (kind) {} |
442 | |
443 | enum svalue_kind get_kind () const final override { return SK_POISONED; } |
444 | const poisoned_svalue * |
445 | dyn_cast_poisoned_svalue () const final override { return this; } |
446 | |
447 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
448 | void accept (visitor *v) const final override; |
449 | |
450 | const svalue * |
451 | maybe_fold_bits_within (tree type, |
452 | const bit_range &subrange, |
453 | region_model_manager *mgr) const final override; |
454 | |
455 | enum poison_kind get_poison_kind () const { return m_kind; } |
456 | |
457 | /* Poisoned svalues are singletons per-type, so can't have state. */ |
458 | bool can_have_associated_state_p () const final override { return false; } |
459 | |
460 | private: |
461 | enum poison_kind m_kind; |
462 | }; |
463 | |
464 | } // namespace ana |
465 | |
466 | template <> |
467 | template <> |
468 | inline bool |
469 | is_a_helper <const poisoned_svalue *>::test (const svalue *sval) |
470 | { |
471 | 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 | setjmp_record (const exploded_node *enode, |
488 | const gcall *setjmp_call) |
489 | : m_enode (enode), m_setjmp_call (setjmp_call) |
490 | { |
491 | } |
492 | |
493 | bool operator== (const setjmp_record &other) const |
494 | { |
495 | return (m_enode == other.m_enode |
496 | && m_setjmp_call == other.m_setjmp_call); |
497 | } |
498 | |
499 | void add_to_hash (inchash::hash *hstate) const |
500 | { |
501 | hstate->add_ptr (ptr: m_enode); |
502 | hstate->add_ptr (ptr: m_setjmp_call); |
503 | } |
504 | |
505 | static int cmp (const setjmp_record &rec1, const setjmp_record &rec2); |
506 | |
507 | const exploded_node *m_enode; |
508 | const gcall *m_setjmp_call; |
509 | }; |
510 | |
511 | /* Concrete subclass of svalue representing buffers for setjmp/sigsetjmp, |
512 | so that longjmp/siglongjmp can potentially "return" to an entirely |
513 | different function. */ |
514 | |
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 | key_t (const setjmp_record &record, tree type) |
522 | : m_record (record), m_type (type) |
523 | {} |
524 | |
525 | hashval_t hash () const |
526 | { |
527 | inchash::hash hstate; |
528 | m_record.add_to_hash (hstate: &hstate); |
529 | hstate.add_ptr (ptr: m_type); |
530 | return hstate.end (); |
531 | } |
532 | |
533 | bool operator== (const key_t &other) const |
534 | { |
535 | return (m_record == other.m_record && m_type == other.m_type); |
536 | } |
537 | |
538 | void mark_deleted () { m_type = reinterpret_cast<tree> (1); } |
539 | void mark_empty () { m_type = reinterpret_cast<tree> (2); } |
540 | bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } |
541 | bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } |
542 | |
543 | setjmp_record m_record; |
544 | tree m_type; |
545 | }; |
546 | |
547 | setjmp_svalue (const setjmp_record &setjmp_record, |
548 | symbol::id_t id, |
549 | tree type) |
550 | : svalue (complexity (1, 1), id, type), m_setjmp_record (setjmp_record) |
551 | {} |
552 | |
553 | enum svalue_kind get_kind () const final override { return SK_SETJMP; } |
554 | const setjmp_svalue * |
555 | dyn_cast_setjmp_svalue () const final override { return this; } |
556 | |
557 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
558 | void accept (visitor *v) const final override; |
559 | |
560 | int get_enode_index () const; |
561 | |
562 | const setjmp_record &get_setjmp_record () const { return m_setjmp_record; } |
563 | |
564 | private: |
565 | setjmp_record m_setjmp_record; |
566 | }; |
567 | |
568 | } // namespace ana |
569 | |
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 | initial_svalue (symbol::id_t id, tree type, const region *reg) |
598 | : svalue (complexity (reg), id, type), m_reg (reg) |
599 | { |
600 | gcc_assert (m_reg != NULL); |
601 | } |
602 | |
603 | enum svalue_kind get_kind () const final override { return SK_INITIAL; } |
604 | const initial_svalue * |
605 | dyn_cast_initial_svalue () const final override { return this; } |
606 | |
607 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
608 | void accept (visitor *v) const final override; |
609 | bool implicitly_live_p (const svalue_set *, |
610 | const region_model *) const final override; |
611 | |
612 | bool initial_value_of_param_p () const; |
613 | |
614 | const region *get_region () const { return m_reg; } |
615 | |
616 | private: |
617 | const region *m_reg; |
618 | }; |
619 | |
620 | } // namespace ana |
621 | |
622 | template <> |
623 | template <> |
624 | inline bool |
625 | is_a_helper <const initial_svalue *>::test (const svalue *sval) |
626 | { |
627 | 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 | key_t (tree type, enum tree_code op, const svalue *arg) |
642 | : m_type (type), m_op (op), m_arg (arg) |
643 | {} |
644 | |
645 | hashval_t hash () const |
646 | { |
647 | inchash::hash hstate; |
648 | hstate.add_ptr (ptr: m_type); |
649 | hstate.add_int (v: m_op); |
650 | hstate.add_ptr (ptr: m_arg); |
651 | return hstate.end (); |
652 | } |
653 | |
654 | bool operator== (const key_t &other) const |
655 | { |
656 | return (m_type == other.m_type |
657 | && m_op == other.m_op |
658 | && m_arg == other.m_arg); |
659 | } |
660 | |
661 | void mark_deleted () { m_type = reinterpret_cast<tree> (1); } |
662 | void mark_empty () { m_type = reinterpret_cast<tree> (2); } |
663 | bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } |
664 | bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } |
665 | |
666 | tree m_type; |
667 | enum tree_code m_op; |
668 | const svalue *m_arg; |
669 | }; |
670 | |
671 | unaryop_svalue (symbol::id_t id, tree type, enum tree_code op, |
672 | const svalue *arg) |
673 | : svalue (complexity (arg), id, type), m_op (op), m_arg (arg) |
674 | { |
675 | gcc_assert (arg->can_have_associated_state_p ()); |
676 | } |
677 | |
678 | enum svalue_kind get_kind () const final override { return SK_UNARYOP; } |
679 | const unaryop_svalue * |
680 | dyn_cast_unaryop_svalue () const final override { return this; } |
681 | |
682 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
683 | void accept (visitor *v) const final override; |
684 | bool implicitly_live_p (const svalue_set *, |
685 | const region_model *) const final override; |
686 | |
687 | enum tree_code get_op () const { return m_op; } |
688 | const svalue *get_arg () const { return m_arg; } |
689 | |
690 | const svalue * |
691 | maybe_fold_bits_within (tree type, |
692 | const bit_range &subrange, |
693 | region_model_manager *mgr) const final override; |
694 | |
695 | private: |
696 | enum tree_code m_op; |
697 | const svalue *m_arg; |
698 | }; |
699 | |
700 | } // namespace ana |
701 | |
702 | template <> |
703 | template <> |
704 | inline bool |
705 | is_a_helper <const unaryop_svalue *>::test (const svalue *sval) |
706 | { |
707 | 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 | key_t (tree type, enum tree_code op, |
728 | const svalue *arg0, const svalue *arg1) |
729 | : m_type (type), m_op (op), m_arg0 (arg0), m_arg1 (arg1) |
730 | {} |
731 | |
732 | hashval_t hash () const |
733 | { |
734 | inchash::hash hstate; |
735 | hstate.add_ptr (ptr: m_type); |
736 | hstate.add_int (v: m_op); |
737 | hstate.add_ptr (ptr: m_arg0); |
738 | hstate.add_ptr (ptr: m_arg1); |
739 | return hstate.end (); |
740 | } |
741 | |
742 | bool operator== (const key_t &other) const |
743 | { |
744 | return (m_type == other.m_type |
745 | && m_op == other.m_op |
746 | && m_arg0 == other.m_arg0 |
747 | && m_arg1 == other.m_arg1); |
748 | } |
749 | |
750 | void mark_deleted () { m_type = reinterpret_cast<tree> (1); } |
751 | void mark_empty () { m_type = reinterpret_cast<tree> (2); } |
752 | bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } |
753 | bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } |
754 | |
755 | tree m_type; |
756 | enum tree_code m_op; |
757 | const svalue *m_arg0; |
758 | const svalue *m_arg1; |
759 | }; |
760 | |
761 | binop_svalue (symbol::id_t id, tree type, enum tree_code op, |
762 | const svalue *arg0, const svalue *arg1) |
763 | : svalue (complexity::from_pair (c1: arg0->get_complexity (), |
764 | c: arg1->get_complexity ()), |
765 | id, |
766 | type), |
767 | m_op (op), m_arg0 (arg0), m_arg1 (arg1) |
768 | { |
769 | gcc_assert (arg0->can_have_associated_state_p ()); |
770 | gcc_assert (arg1->can_have_associated_state_p ()); |
771 | } |
772 | |
773 | enum svalue_kind get_kind () const final override { return SK_BINOP; } |
774 | const binop_svalue *dyn_cast_binop_svalue () const final override |
775 | { |
776 | return this; |
777 | } |
778 | |
779 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
780 | void accept (visitor *v) const final override; |
781 | bool implicitly_live_p (const svalue_set *, |
782 | const region_model *) const final override; |
783 | |
784 | enum tree_code get_op () const { return m_op; } |
785 | const svalue *get_arg0 () const { return m_arg0; } |
786 | const svalue *get_arg1 () const { return m_arg1; } |
787 | |
788 | private: |
789 | enum tree_code m_op; |
790 | const svalue *m_arg0; |
791 | const svalue *m_arg1; |
792 | }; |
793 | |
794 | } // namespace ana |
795 | |
796 | template <> |
797 | template <> |
798 | inline bool |
799 | is_a_helper <const binop_svalue *>::test (const svalue *sval) |
800 | { |
801 | 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 | key_t (tree type, const svalue *parent_svalue, const region *subregion) |
823 | : m_type (type), m_parent_svalue (parent_svalue), m_subregion (subregion) |
824 | {} |
825 | |
826 | hashval_t hash () const |
827 | { |
828 | inchash::hash hstate; |
829 | hstate.add_ptr (ptr: m_type); |
830 | hstate.add_ptr (ptr: m_parent_svalue); |
831 | hstate.add_ptr (ptr: m_subregion); |
832 | return hstate.end (); |
833 | } |
834 | |
835 | bool operator== (const key_t &other) const |
836 | { |
837 | return (m_type == other.m_type |
838 | && m_parent_svalue == other.m_parent_svalue |
839 | && m_subregion == other.m_subregion); |
840 | } |
841 | |
842 | void mark_deleted () { m_type = reinterpret_cast<tree> (1); } |
843 | void mark_empty () { m_type = reinterpret_cast<tree> (2); } |
844 | bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } |
845 | bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } |
846 | |
847 | tree m_type; |
848 | const svalue *m_parent_svalue; |
849 | const region *m_subregion; |
850 | }; |
851 | sub_svalue (symbol::id_t id, tree type, const svalue *parent_svalue, |
852 | const region *subregion); |
853 | |
854 | enum svalue_kind get_kind () const final override { return SK_SUB; } |
855 | const sub_svalue *dyn_cast_sub_svalue () const final override |
856 | { |
857 | return this; |
858 | } |
859 | |
860 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
861 | void accept (visitor *v) const final override; |
862 | bool implicitly_live_p (const svalue_set *, |
863 | const region_model *) const final override; |
864 | |
865 | const svalue *get_parent () const { return m_parent_svalue; } |
866 | const region *get_subregion () const { return m_subregion; } |
867 | |
868 | private: |
869 | const svalue *m_parent_svalue; |
870 | const region *m_subregion; |
871 | }; |
872 | |
873 | } // namespace ana |
874 | |
875 | template <> |
876 | template <> |
877 | inline bool |
878 | is_a_helper <const sub_svalue *>::test (const svalue *sval) |
879 | { |
880 | 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 | key_t (tree type, |
902 | const svalue *outer_size, |
903 | const svalue *inner_svalue) |
904 | : m_type (type), m_outer_size (outer_size), m_inner_svalue (inner_svalue) |
905 | {} |
906 | |
907 | hashval_t hash () const |
908 | { |
909 | inchash::hash hstate; |
910 | hstate.add_ptr (ptr: m_type); |
911 | hstate.add_ptr (ptr: m_outer_size); |
912 | hstate.add_ptr (ptr: m_inner_svalue); |
913 | return hstate.end (); |
914 | } |
915 | |
916 | bool operator== (const key_t &other) const |
917 | { |
918 | return (m_type == other.m_type |
919 | && m_outer_size == other.m_outer_size |
920 | && m_inner_svalue == other.m_inner_svalue); |
921 | } |
922 | |
923 | void mark_deleted () { m_type = reinterpret_cast<tree> (1); } |
924 | void mark_empty () { m_type = reinterpret_cast<tree> (2); } |
925 | bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } |
926 | bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } |
927 | |
928 | tree m_type; |
929 | const svalue *m_outer_size; |
930 | const svalue *m_inner_svalue; |
931 | }; |
932 | repeated_svalue (symbol::id_t id, |
933 | tree type, |
934 | const svalue *outer_size, |
935 | const svalue *inner_svalue); |
936 | |
937 | enum svalue_kind get_kind () const final override { return SK_REPEATED; } |
938 | const repeated_svalue *dyn_cast_repeated_svalue () const final override |
939 | { |
940 | return this; |
941 | } |
942 | |
943 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
944 | void accept (visitor *v) const final override; |
945 | |
946 | const svalue *get_outer_size () const { return m_outer_size; } |
947 | const svalue *get_inner_svalue () const { return m_inner_svalue; } |
948 | |
949 | bool all_zeroes_p () const final override; |
950 | |
951 | const svalue * |
952 | maybe_fold_bits_within (tree type, |
953 | const bit_range &subrange, |
954 | region_model_manager *mgr) const final override; |
955 | |
956 | private: |
957 | const svalue *m_outer_size; |
958 | const svalue *m_inner_svalue; |
959 | }; |
960 | |
961 | } // namespace ana |
962 | |
963 | template <> |
964 | template <> |
965 | inline bool |
966 | is_a_helper <const repeated_svalue *>::test (const svalue *sval) |
967 | { |
968 | 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 | key_t (tree type, |
991 | const bit_range &bits, |
992 | const svalue *inner_svalue) |
993 | : m_type (type), m_bits (bits), m_inner_svalue (inner_svalue) |
994 | {} |
995 | |
996 | hashval_t hash () const |
997 | { |
998 | inchash::hash hstate; |
999 | hstate.add_ptr (ptr: m_type); |
1000 | hstate.add_ptr (ptr: m_inner_svalue); |
1001 | return hstate.end (); |
1002 | } |
1003 | |
1004 | bool operator== (const key_t &other) const |
1005 | { |
1006 | return (m_type == other.m_type |
1007 | && m_bits == other.m_bits |
1008 | && m_inner_svalue == other.m_inner_svalue); |
1009 | } |
1010 | |
1011 | void mark_deleted () { m_type = reinterpret_cast<tree> (1); } |
1012 | void mark_empty () { m_type = reinterpret_cast<tree> (2); } |
1013 | bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } |
1014 | bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } |
1015 | |
1016 | tree m_type; |
1017 | bit_range m_bits; |
1018 | const svalue *m_inner_svalue; |
1019 | }; |
1020 | bits_within_svalue (symbol::id_t id, |
1021 | tree type, |
1022 | const bit_range &bits, |
1023 | const svalue *inner_svalue); |
1024 | |
1025 | enum svalue_kind get_kind () const final override { return SK_BITS_WITHIN; } |
1026 | const bits_within_svalue * |
1027 | dyn_cast_bits_within_svalue () const final override |
1028 | { |
1029 | return this; |
1030 | } |
1031 | |
1032 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
1033 | void accept (visitor *v) const final override; |
1034 | bool implicitly_live_p (const svalue_set *, |
1035 | const region_model *) const final override; |
1036 | |
1037 | const bit_range &get_bits () const { return m_bits; } |
1038 | const svalue *get_inner_svalue () const { return m_inner_svalue; } |
1039 | |
1040 | const svalue * |
1041 | maybe_fold_bits_within (tree type, |
1042 | const bit_range &subrange, |
1043 | region_model_manager *mgr) const final override; |
1044 | |
1045 | private: |
1046 | const bit_range m_bits; |
1047 | const svalue *m_inner_svalue; |
1048 | }; |
1049 | |
1050 | } // namespace ana |
1051 | |
1052 | template <> |
1053 | template <> |
1054 | inline bool |
1055 | is_a_helper <const bits_within_svalue *>::test (const svalue *sval) |
1056 | { |
1057 | 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 | unmergeable_svalue (symbol::id_t id, const svalue *arg) |
1083 | : svalue (complexity (arg), id, arg->get_type ()), m_arg (arg) |
1084 | { |
1085 | } |
1086 | |
1087 | enum svalue_kind get_kind () const final override { return SK_UNMERGEABLE; } |
1088 | const unmergeable_svalue * |
1089 | dyn_cast_unmergeable_svalue () const final override { return this; } |
1090 | |
1091 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
1092 | void accept (visitor *v) const final override; |
1093 | bool implicitly_live_p (const svalue_set *, |
1094 | const region_model *) const final override; |
1095 | |
1096 | const svalue *get_arg () const { return m_arg; } |
1097 | |
1098 | private: |
1099 | const svalue *m_arg; |
1100 | }; |
1101 | |
1102 | } // namespace ana |
1103 | |
1104 | template <> |
1105 | template <> |
1106 | inline bool |
1107 | is_a_helper <const unmergeable_svalue *>::test (const svalue *sval) |
1108 | { |
1109 | 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 | class placeholder_svalue : public svalue |
1120 | { |
1121 | public: |
1122 | placeholder_svalue (symbol::id_t id, tree type, const char *name) |
1123 | : svalue (complexity (1, 1), id, type), m_name (name) |
1124 | { |
1125 | } |
1126 | |
1127 | enum svalue_kind get_kind () const final override { return SK_PLACEHOLDER; } |
1128 | |
1129 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
1130 | void accept (visitor *v) const final override; |
1131 | |
1132 | const char *get_name () const { return m_name; } |
1133 | |
1134 | private: |
1135 | const char *m_name; |
1136 | }; |
1137 | |
1138 | } // namespace ana |
1139 | |
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 | key_t (tree type, const function_point &point, |
1167 | const svalue *base_sval, const svalue *iter_sval) |
1168 | : m_type (type), m_point (point), |
1169 | m_base_sval (base_sval), m_iter_sval (iter_sval) |
1170 | {} |
1171 | |
1172 | hashval_t hash () const |
1173 | { |
1174 | inchash::hash hstate; |
1175 | hstate.add_ptr (ptr: m_base_sval); |
1176 | hstate.add_ptr (ptr: m_iter_sval); |
1177 | return hstate.end (); |
1178 | } |
1179 | |
1180 | bool operator== (const key_t &other) const |
1181 | { |
1182 | return (m_type == other.m_type |
1183 | && m_point == other.m_point |
1184 | && m_base_sval == other.m_base_sval |
1185 | && m_iter_sval == other.m_iter_sval); |
1186 | } |
1187 | |
1188 | void mark_deleted () { m_type = reinterpret_cast<tree> (1); } |
1189 | void mark_empty () { m_type = reinterpret_cast<tree> (2); } |
1190 | bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } |
1191 | bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } |
1192 | |
1193 | tree m_type; |
1194 | function_point m_point; |
1195 | const svalue *m_base_sval; |
1196 | const svalue *m_iter_sval; |
1197 | }; |
1198 | |
1199 | enum direction_t |
1200 | { |
1201 | DIR_ASCENDING, |
1202 | DIR_DESCENDING, |
1203 | DIR_UNKNOWN |
1204 | }; |
1205 | |
1206 | widening_svalue (symbol::id_t id, tree type, const function_point &point, |
1207 | const svalue *base_sval, const svalue *iter_sval) |
1208 | : svalue (complexity::from_pair (c1: base_sval->get_complexity (), |
1209 | c: iter_sval->get_complexity ()), |
1210 | id, |
1211 | type), |
1212 | m_point (point), |
1213 | m_base_sval (base_sval), m_iter_sval (iter_sval) |
1214 | { |
1215 | gcc_assert (base_sval->can_have_associated_state_p ()); |
1216 | gcc_assert (iter_sval->can_have_associated_state_p ()); |
1217 | } |
1218 | |
1219 | enum svalue_kind get_kind () const final override { return SK_WIDENING; } |
1220 | const widening_svalue *dyn_cast_widening_svalue () const final override |
1221 | { |
1222 | return this; |
1223 | } |
1224 | |
1225 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
1226 | void accept (visitor *v) const final override; |
1227 | |
1228 | const function_point &get_point () const { return m_point; } |
1229 | const svalue *get_base_svalue () const { return m_base_sval; } |
1230 | const svalue *get_iter_svalue () const { return m_iter_sval; } |
1231 | |
1232 | enum direction_t get_direction () const; |
1233 | |
1234 | tristate eval_condition_without_cm (enum tree_code op, |
1235 | tree rhs_cst) const; |
1236 | |
1237 | private: |
1238 | function_point m_point; |
1239 | const svalue *m_base_sval; |
1240 | const svalue *m_iter_sval; |
1241 | }; |
1242 | |
1243 | } // namespace ana |
1244 | |
1245 | template <> |
1246 | template <> |
1247 | inline bool |
1248 | is_a_helper <const widening_svalue *>::test (const svalue *sval) |
1249 | { |
1250 | 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 | key_t (tree type, const binding_map *map_ptr) |
1286 | : m_type (type), m_map_ptr (map_ptr) |
1287 | {} |
1288 | |
1289 | hashval_t hash () const |
1290 | { |
1291 | inchash::hash hstate; |
1292 | hstate.add_ptr (ptr: m_type); |
1293 | //hstate.add_ptr (m_map_ptr); // TODO |
1294 | return hstate.end (); |
1295 | } |
1296 | |
1297 | bool operator== (const key_t &other) const |
1298 | { |
1299 | return (m_type == other.m_type |
1300 | && *m_map_ptr == *other.m_map_ptr); |
1301 | } |
1302 | |
1303 | void mark_deleted () { m_type = reinterpret_cast<tree> (1); } |
1304 | void mark_empty () { m_type = reinterpret_cast<tree> (2); } |
1305 | bool is_deleted () const { return m_type == reinterpret_cast<tree> (1); } |
1306 | bool is_empty () const { return m_type == reinterpret_cast<tree> (2); } |
1307 | |
1308 | tree m_type; |
1309 | const binding_map *m_map_ptr; |
1310 | }; |
1311 | |
1312 | compound_svalue (symbol::id_t id, tree type, const binding_map &map); |
1313 | |
1314 | enum svalue_kind get_kind () const final override { return SK_COMPOUND; } |
1315 | const compound_svalue *dyn_cast_compound_svalue () const final override |
1316 | { |
1317 | return this; |
1318 | } |
1319 | |
1320 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
1321 | void accept (visitor *v) const final override; |
1322 | |
1323 | const binding_map &get_map () const { return m_map; } |
1324 | |
1325 | iterator_t begin () const { return m_map.begin (); } |
1326 | iterator_t end () const { return m_map.end (); } |
1327 | |
1328 | struct key_t make_key () const |
1329 | { |
1330 | return key_t (get_type (), &m_map); |
1331 | } |
1332 | |
1333 | const svalue * |
1334 | maybe_fold_bits_within (tree type, |
1335 | const bit_range &subrange, |
1336 | region_model_manager *mgr) const final override; |
1337 | |
1338 | private: |
1339 | static complexity calc_complexity (const binding_map &map); |
1340 | |
1341 | binding_map m_map; |
1342 | }; |
1343 | |
1344 | } // namespace ana |
1345 | |
1346 | template <> |
1347 | template <> |
1348 | inline bool |
1349 | is_a_helper <const compound_svalue *>::test (const svalue *sval) |
1350 | { |
1351 | 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 | conjured_purge (region_model *model, region_model_context *ctxt) |
1373 | : m_model (model), m_ctxt (ctxt) |
1374 | { |
1375 | } |
1376 | void purge (const conjured_svalue *sval) const; |
1377 | |
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 | key_t (tree type, const gimple *stmt, const region *id_reg, unsigned idx) |
1407 | : m_type (type), m_stmt (stmt), m_id_reg (id_reg), m_idx (idx) |
1408 | {} |
1409 | |
1410 | hashval_t hash () const |
1411 | { |
1412 | inchash::hash hstate; |
1413 | hstate.add_ptr (ptr: m_type); |
1414 | hstate.add_ptr (ptr: m_stmt); |
1415 | hstate.add_ptr (ptr: m_id_reg); |
1416 | return hstate.end (); |
1417 | } |
1418 | |
1419 | bool operator== (const key_t &other) const |
1420 | { |
1421 | return (m_type == other.m_type |
1422 | && m_stmt == other.m_stmt |
1423 | && m_id_reg == other.m_id_reg |
1424 | && m_idx == other.m_idx); |
1425 | } |
1426 | |
1427 | /* Use m_stmt to mark empty/deleted, as m_type can be NULL for |
1428 | legitimate instances. */ |
1429 | void mark_deleted () { m_stmt = reinterpret_cast<const gimple *> (1); } |
1430 | void mark_empty () { m_stmt = NULL; } |
1431 | bool is_deleted () const |
1432 | { |
1433 | return m_stmt == reinterpret_cast<const gimple *> (1); |
1434 | } |
1435 | bool is_empty () const { return m_stmt == NULL; } |
1436 | |
1437 | tree m_type; |
1438 | const gimple *m_stmt; |
1439 | const region *m_id_reg; |
1440 | unsigned m_idx; |
1441 | }; |
1442 | |
1443 | conjured_svalue (symbol::id_t id, tree type, const gimple *stmt, |
1444 | const region *id_reg, unsigned idx) |
1445 | : svalue (complexity (id_reg), id, type), |
1446 | m_stmt (stmt), m_id_reg (id_reg), m_idx (idx) |
1447 | { |
1448 | gcc_assert (m_stmt != NULL); |
1449 | } |
1450 | |
1451 | enum svalue_kind get_kind () const final override { return SK_CONJURED; } |
1452 | const conjured_svalue *dyn_cast_conjured_svalue () const final override |
1453 | { |
1454 | return this; |
1455 | } |
1456 | |
1457 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
1458 | void accept (visitor *v) const final override; |
1459 | |
1460 | const gimple *get_stmt () const { return m_stmt; } |
1461 | const region *get_id_region () const { return m_id_reg; } |
1462 | bool lhs_value_p () const; |
1463 | |
1464 | private: |
1465 | const gimple *m_stmt; |
1466 | const region *m_id_reg; |
1467 | unsigned m_idx; |
1468 | }; |
1469 | |
1470 | } // namespace ana |
1471 | |
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 | key_t (tree type, |
1506 | const char *asm_string, |
1507 | unsigned output_idx, |
1508 | const vec<const svalue *> &inputs) |
1509 | : m_type (type), m_asm_string (asm_string), m_output_idx (output_idx), |
1510 | m_num_inputs (inputs.length ()) |
1511 | { |
1512 | gcc_assert (inputs.length () <= MAX_INPUTS); |
1513 | for (unsigned i = 0; i < m_num_inputs; i++) |
1514 | m_input_arr[i] = inputs[i]; |
1515 | } |
1516 | |
1517 | hashval_t hash () const |
1518 | { |
1519 | inchash::hash hstate; |
1520 | hstate.add_ptr (ptr: m_type); |
1521 | /* We don't bother hashing m_asm_str. */ |
1522 | hstate.add_int (v: m_output_idx); |
1523 | for (unsigned i = 0; i < m_num_inputs; i++) |
1524 | hstate.add_ptr (ptr: m_input_arr[i]); |
1525 | return hstate.end (); |
1526 | } |
1527 | |
1528 | bool operator== (const key_t &other) const |
1529 | { |
1530 | if (!(m_type == other.m_type |
1531 | && 0 == (strcmp (s1: m_asm_string, s2: other.m_asm_string)) |
1532 | && m_output_idx == other.m_output_idx |
1533 | && m_num_inputs == other.m_num_inputs)) |
1534 | return false; |
1535 | for (unsigned i = 0; i < m_num_inputs; i++) |
1536 | if (m_input_arr[i] != other.m_input_arr[i]) |
1537 | return false; |
1538 | return true; |
1539 | } |
1540 | |
1541 | /* Use m_asm_string to mark empty/deleted, as m_type can be NULL for |
1542 | legitimate instances. */ |
1543 | void mark_deleted () { m_asm_string = reinterpret_cast<const char *> (1); } |
1544 | void mark_empty () { m_asm_string = NULL; } |
1545 | bool is_deleted () const |
1546 | { |
1547 | return m_asm_string == reinterpret_cast<const char *> (1); |
1548 | } |
1549 | bool is_empty () const { return m_asm_string == NULL; } |
1550 | |
1551 | tree m_type; |
1552 | const char *m_asm_string; |
1553 | unsigned m_output_idx; |
1554 | unsigned m_num_inputs; |
1555 | const svalue *m_input_arr[MAX_INPUTS]; |
1556 | }; |
1557 | |
1558 | asm_output_svalue (symbol::id_t id, |
1559 | tree type, |
1560 | const char *asm_string, |
1561 | unsigned output_idx, |
1562 | unsigned num_outputs, |
1563 | const vec<const svalue *> &inputs) |
1564 | : svalue (complexity::from_vec_svalue (vec: inputs), id, type), |
1565 | m_asm_string (asm_string), |
1566 | m_output_idx (output_idx), |
1567 | m_num_outputs (num_outputs), |
1568 | m_num_inputs (inputs.length ()) |
1569 | { |
1570 | gcc_assert (inputs.length () <= MAX_INPUTS); |
1571 | for (unsigned i = 0; i < m_num_inputs; i++) |
1572 | m_input_arr[i] = inputs[i]; |
1573 | } |
1574 | |
1575 | enum svalue_kind get_kind () const final override { return SK_ASM_OUTPUT; } |
1576 | const asm_output_svalue * |
1577 | dyn_cast_asm_output_svalue () const final override |
1578 | { |
1579 | return this; |
1580 | } |
1581 | |
1582 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
1583 | void accept (visitor *v) const final override; |
1584 | |
1585 | const char *get_asm_string () const { return m_asm_string; } |
1586 | unsigned get_output_idx () const { return m_output_idx; } |
1587 | unsigned get_num_outputs () const { return m_num_outputs; } |
1588 | unsigned get_num_inputs () const { return m_num_inputs; } |
1589 | const svalue *get_input (unsigned idx) const { return m_input_arr[idx]; } |
1590 | |
1591 | private: |
1592 | void dump_input (pretty_printer *pp, |
1593 | unsigned input_idx, |
1594 | const svalue *sval, |
1595 | bool simple) const; |
1596 | unsigned input_idx_to_asm_idx (unsigned input_idx) const; |
1597 | |
1598 | const char *m_asm_string; |
1599 | unsigned m_output_idx; |
1600 | |
1601 | /* We capture this so that we can offset the input indices |
1602 | to match the %0, %1, %2 in the asm_string when dumping. */ |
1603 | unsigned m_num_outputs; |
1604 | |
1605 | unsigned m_num_inputs; |
1606 | const svalue *m_input_arr[MAX_INPUTS]; |
1607 | }; |
1608 | |
1609 | } // namespace ana |
1610 | |
1611 | template <> |
1612 | template <> |
1613 | inline bool |
1614 | is_a_helper <const asm_output_svalue *>::test (const svalue *sval) |
1615 | { |
1616 | 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 | key_t (tree type, |
1645 | tree fndecl, |
1646 | const vec<const svalue *> &inputs) |
1647 | : m_type (type), m_fndecl (fndecl), |
1648 | m_num_inputs (inputs.length ()) |
1649 | { |
1650 | gcc_assert (inputs.length () <= MAX_INPUTS); |
1651 | for (unsigned i = 0; i < m_num_inputs; i++) |
1652 | m_input_arr[i] = inputs[i]; |
1653 | } |
1654 | |
1655 | hashval_t hash () const |
1656 | { |
1657 | inchash::hash hstate; |
1658 | hstate.add_ptr (ptr: m_type); |
1659 | hstate.add_ptr (ptr: m_fndecl); |
1660 | for (unsigned i = 0; i < m_num_inputs; i++) |
1661 | hstate.add_ptr (ptr: m_input_arr[i]); |
1662 | return hstate.end (); |
1663 | } |
1664 | |
1665 | bool operator== (const key_t &other) const |
1666 | { |
1667 | if (!(m_type == other.m_type |
1668 | && m_fndecl == other.m_fndecl |
1669 | && m_num_inputs == other.m_num_inputs)) |
1670 | return false; |
1671 | for (unsigned i = 0; i < m_num_inputs; i++) |
1672 | if (m_input_arr[i] != other.m_input_arr[i]) |
1673 | return false; |
1674 | return true; |
1675 | } |
1676 | |
1677 | /* Use m_fndecl to mark empty/deleted. */ |
1678 | void mark_deleted () { m_fndecl = reinterpret_cast<tree> (1); } |
1679 | void mark_empty () { m_fndecl = NULL; } |
1680 | bool is_deleted () const |
1681 | { |
1682 | return m_fndecl == reinterpret_cast<tree> (1); |
1683 | } |
1684 | bool is_empty () const { return m_fndecl == NULL; } |
1685 | |
1686 | tree m_type; |
1687 | tree m_fndecl; |
1688 | unsigned m_num_inputs; |
1689 | const svalue *m_input_arr[MAX_INPUTS]; |
1690 | }; |
1691 | |
1692 | const_fn_result_svalue (symbol::id_t id, |
1693 | tree type, |
1694 | tree fndecl, |
1695 | const vec<const svalue *> &inputs) |
1696 | : svalue (complexity::from_vec_svalue (vec: inputs), id, type), |
1697 | m_fndecl (fndecl), |
1698 | m_num_inputs (inputs.length ()) |
1699 | { |
1700 | gcc_assert (inputs.length () <= MAX_INPUTS); |
1701 | for (unsigned i = 0; i < m_num_inputs; i++) |
1702 | m_input_arr[i] = inputs[i]; |
1703 | } |
1704 | |
1705 | enum svalue_kind get_kind () const final override |
1706 | { |
1707 | return SK_CONST_FN_RESULT; |
1708 | } |
1709 | const const_fn_result_svalue * |
1710 | dyn_cast_const_fn_result_svalue () const final override |
1711 | { |
1712 | return this; |
1713 | } |
1714 | |
1715 | void dump_to_pp (pretty_printer *pp, bool simple) const final override; |
1716 | void accept (visitor *v) const final override; |
1717 | |
1718 | tree get_fndecl () const { return m_fndecl; } |
1719 | unsigned get_num_inputs () const { return m_num_inputs; } |
1720 | const svalue *get_input (unsigned idx) const { return m_input_arr[idx]; } |
1721 | |
1722 | private: |
1723 | void dump_input (pretty_printer *pp, |
1724 | unsigned input_idx, |
1725 | const svalue *sval, |
1726 | bool simple) const; |
1727 | |
1728 | tree m_fndecl; |
1729 | unsigned m_num_inputs; |
1730 | const svalue *m_input_arr[MAX_INPUTS]; |
1731 | }; |
1732 | |
1733 | } // namespace ana |
1734 | |
1735 | template <> |
1736 | template <> |
1737 | inline bool |
1738 | is_a_helper <const const_fn_result_svalue *>::test (const svalue *sval) |
1739 | { |
1740 | 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 */ |
1750 | |