145
|
1 /* Classes for modeling the state of memory.
|
|
2 Copyright (C) 2019-2020 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_REGION_MODEL_H
|
|
22 #define GCC_ANALYZER_REGION_MODEL_H
|
|
23
|
|
24 /* Implementation of the region-based ternary model described in:
|
|
25 "A Memory Model for Static Analysis of C Programs"
|
|
26 (Zhongxing Xu, Ted Kremenek, and Jian Zhang)
|
|
27 http://lcs.ios.ac.cn/~xuzb/canalyze/memmodel.pdf */
|
|
28
|
|
29 /* A tree, extended with stack frame information for locals, so that
|
|
30 we can distinguish between different values of locals within a potentially
|
|
31 recursive callstack. */
|
|
32 // TODO: would this be better as a new tree code?
|
|
33
|
|
34 using namespace ana;
|
|
35
|
|
36 namespace ana {
|
|
37
|
|
38 class path_var
|
|
39 {
|
|
40 public:
|
|
41 path_var (tree t, int stack_depth)
|
|
42 : m_tree (t), m_stack_depth (stack_depth)
|
|
43 {
|
|
44 // TODO: ignore stack depth for globals and constants
|
|
45 }
|
|
46
|
|
47 bool operator== (const path_var &other) const
|
|
48 {
|
|
49 return (m_tree == other.m_tree
|
|
50 && m_stack_depth == other.m_stack_depth);
|
|
51 }
|
|
52
|
|
53 void dump (pretty_printer *pp) const;
|
|
54
|
|
55 tree m_tree;
|
|
56 int m_stack_depth; // or -1 for globals?
|
|
57 };
|
|
58
|
|
59 } // namespace ana
|
|
60
|
|
61 namespace inchash
|
|
62 {
|
|
63 extern void add_path_var (path_var pv, hash &hstate);
|
|
64 } // namespace inchash
|
|
65
|
|
66
|
|
67 namespace ana {
|
|
68
|
|
69 /* A region_model is effectively a graph of regions and symbolic values.
|
|
70 We store per-model IDs rather than pointers to make it easier to clone
|
|
71 and to compare graphs. */
|
|
72
|
|
73 /* An ID for an svalue within a region_model. Internally, this is an index
|
|
74 into a vector of svalue * within the region_model. */
|
|
75
|
|
76 class svalue_id
|
|
77 {
|
|
78 public:
|
|
79 static svalue_id null () { return svalue_id (-1); }
|
|
80
|
|
81 svalue_id () : m_idx (-1) {}
|
|
82
|
|
83 bool operator== (const svalue_id &other) const
|
|
84 {
|
|
85 return m_idx == other.m_idx;
|
|
86 }
|
|
87
|
|
88 bool operator!= (const svalue_id &other) const
|
|
89 {
|
|
90 return m_idx != other.m_idx;
|
|
91 }
|
|
92
|
|
93 bool null_p () const { return m_idx == -1; }
|
|
94
|
|
95 static svalue_id from_int (int idx) { return svalue_id (idx); }
|
|
96 int as_int () const { return m_idx; }
|
|
97
|
|
98 void print (pretty_printer *pp) const;
|
|
99 void dump_node_name_to_pp (pretty_printer *pp) const;
|
|
100
|
|
101 void validate (const region_model &model) const;
|
|
102
|
|
103 private:
|
|
104 svalue_id (int idx) : m_idx (idx) {}
|
|
105
|
|
106 int m_idx;
|
|
107 };
|
|
108
|
|
109 /* An ID for a region within a region_model. Internally, this is an index
|
|
110 into a vector of region * within the region_model. */
|
|
111
|
|
112 class region_id
|
|
113 {
|
|
114 public:
|
|
115 static region_id null () { return region_id (-1); }
|
|
116
|
|
117 region_id () : m_idx (-1) {}
|
|
118
|
|
119 bool operator== (const region_id &other) const
|
|
120 {
|
|
121 return m_idx == other.m_idx;
|
|
122 }
|
|
123
|
|
124 bool operator!= (const region_id &other) const
|
|
125 {
|
|
126 return m_idx != other.m_idx;
|
|
127 }
|
|
128
|
|
129 bool null_p () const { return m_idx == -1; }
|
|
130
|
|
131 static region_id from_int (int idx) { return region_id (idx); }
|
|
132 int as_int () const { return m_idx; }
|
|
133
|
|
134 void print (pretty_printer *pp) const;
|
|
135 void dump_node_name_to_pp (pretty_printer *pp) const;
|
|
136
|
|
137 void validate (const region_model &model) const;
|
|
138
|
|
139 private:
|
|
140 region_id (int idx) : m_idx (idx) {}
|
|
141
|
|
142 int m_idx;
|
|
143 };
|
|
144
|
|
145 /* A class for renumbering IDs within a region_model, mapping old IDs
|
|
146 to new IDs (e.g. when removing one or more elements, thus needing to
|
|
147 renumber). */
|
|
148 // TODO: could this be useful for equiv_class_ids?
|
|
149
|
|
150 template <typename T>
|
|
151 class id_map
|
|
152 {
|
|
153 public:
|
|
154 id_map (int num_ids);
|
|
155 void put (T src, T dst);
|
|
156 T get_dst_for_src (T src) const;
|
|
157 T get_src_for_dst (T dst) const;
|
|
158 void dump_to_pp (pretty_printer *pp) const;
|
|
159 void dump () const;
|
|
160 void update (T *) const;
|
|
161
|
|
162 private:
|
|
163 auto_vec<T> m_src_to_dst;
|
|
164 auto_vec<T> m_dst_to_src;
|
|
165 };
|
|
166
|
|
167 typedef id_map<svalue_id> svalue_id_map;
|
|
168 typedef id_map<region_id> region_id_map;
|
|
169
|
|
170 /* class id_map. */
|
|
171
|
|
172 /* id_map's ctor, which populates the map with dummy null values. */
|
|
173
|
|
174 template <typename T>
|
|
175 inline id_map<T>::id_map (int num_svalues)
|
|
176 : m_src_to_dst (num_svalues),
|
|
177 m_dst_to_src (num_svalues)
|
|
178 {
|
|
179 for (int i = 0; i < num_svalues; i++)
|
|
180 {
|
|
181 m_src_to_dst.quick_push (T::null ());
|
|
182 m_dst_to_src.quick_push (T::null ());
|
|
183 }
|
|
184 }
|
|
185
|
|
186 /* Record that SRC is to be mapped to DST. */
|
|
187
|
|
188 template <typename T>
|
|
189 inline void
|
|
190 id_map<T>::put (T src, T dst)
|
|
191 {
|
|
192 m_src_to_dst[src.as_int ()] = dst;
|
|
193 m_dst_to_src[dst.as_int ()] = src;
|
|
194 }
|
|
195
|
|
196 /* Get the new value for SRC within the map. */
|
|
197
|
|
198 template <typename T>
|
|
199 inline T
|
|
200 id_map<T>::get_dst_for_src (T src) const
|
|
201 {
|
|
202 if (src.null_p ())
|
|
203 return src;
|
|
204 return m_src_to_dst[src.as_int ()];
|
|
205 }
|
|
206
|
|
207 /* Given DST, a new value, determine which old value will be mapped to it
|
|
208 (the inverse of the map). */
|
|
209
|
|
210 template <typename T>
|
|
211 inline T
|
|
212 id_map<T>::get_src_for_dst (T dst) const
|
|
213 {
|
|
214 if (dst.null_p ())
|
|
215 return dst;
|
|
216 return m_dst_to_src[dst.as_int ()];
|
|
217 }
|
|
218
|
|
219 /* Dump this id_map to PP. */
|
|
220
|
|
221 template <typename T>
|
|
222 inline void
|
|
223 id_map<T>::dump_to_pp (pretty_printer *pp) const
|
|
224 {
|
|
225 pp_string (pp, "src to dst: {");
|
|
226 unsigned i;
|
|
227 T *dst;
|
|
228 FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
|
|
229 {
|
|
230 if (i > 0)
|
|
231 pp_string (pp, ", ");
|
|
232 T src (T::from_int (i));
|
|
233 src.print (pp);
|
|
234 pp_string (pp, " -> ");
|
|
235 dst->print (pp);
|
|
236 }
|
|
237 pp_string (pp, "}");
|
|
238 pp_newline (pp);
|
|
239
|
|
240 pp_string (pp, "dst to src: {");
|
|
241 T *src;
|
|
242 FOR_EACH_VEC_ELT (m_dst_to_src, i, src)
|
|
243 {
|
|
244 if (i > 0)
|
|
245 pp_string (pp, ", ");
|
|
246 T dst (T::from_int (i));
|
|
247 dst.print (pp);
|
|
248 pp_string (pp, " <- ");
|
|
249 src->print (pp);
|
|
250 }
|
|
251 pp_string (pp, "}");
|
|
252 pp_newline (pp);
|
|
253 }
|
|
254
|
|
255 /* Dump this id_map to stderr. */
|
|
256
|
|
257 template <typename T>
|
|
258 DEBUG_FUNCTION inline void
|
|
259 id_map<T>::dump () const
|
|
260 {
|
|
261 pretty_printer pp;
|
|
262 pp.buffer->stream = stderr;
|
|
263 dump_to_pp (&pp);
|
|
264 pp_flush (&pp);
|
|
265 }
|
|
266
|
|
267 /* Update *ID from the old value to its new value in this map. */
|
|
268
|
|
269 template <typename T>
|
|
270 inline void
|
|
271 id_map<T>::update (T *id) const
|
|
272 {
|
|
273 *id = get_dst_for_src (*id);
|
|
274 }
|
|
275
|
|
276 /* Variant of the above, which only stores things in one direction.
|
|
277 (e.g. for merging, when the number of destination regions is not
|
|
278 the same of the src regions, and can grow). */
|
|
279
|
|
280 template <typename T>
|
|
281 class one_way_id_map
|
|
282 {
|
|
283 public:
|
|
284 one_way_id_map (int num_ids);
|
|
285 void put (T src, T dst);
|
|
286 T get_dst_for_src (T src) const;
|
|
287 void dump_to_pp (pretty_printer *pp) const;
|
|
288 void dump () const;
|
|
289 void update (T *) const;
|
|
290
|
|
291 private:
|
|
292 auto_vec<T> m_src_to_dst;
|
|
293 };
|
|
294
|
|
295 typedef one_way_id_map<svalue_id> one_way_svalue_id_map;
|
|
296 typedef one_way_id_map<region_id> one_way_region_id_map;
|
|
297
|
|
298 /* class one_way_id_map. */
|
|
299
|
|
300 /* one_way_id_map's ctor, which populates the map with dummy null values. */
|
|
301
|
|
302 template <typename T>
|
|
303 inline one_way_id_map<T>::one_way_id_map (int num_svalues)
|
|
304 : m_src_to_dst (num_svalues)
|
|
305 {
|
|
306 for (int i = 0; i < num_svalues; i++)
|
|
307 m_src_to_dst.quick_push (T::null ());
|
|
308 }
|
|
309
|
|
310 /* Record that SRC is to be mapped to DST. */
|
|
311
|
|
312 template <typename T>
|
|
313 inline void
|
|
314 one_way_id_map<T>::put (T src, T dst)
|
|
315 {
|
|
316 m_src_to_dst[src.as_int ()] = dst;
|
|
317 }
|
|
318
|
|
319 /* Get the new value for SRC within the map. */
|
|
320
|
|
321 template <typename T>
|
|
322 inline T
|
|
323 one_way_id_map<T>::get_dst_for_src (T src) const
|
|
324 {
|
|
325 if (src.null_p ())
|
|
326 return src;
|
|
327 return m_src_to_dst[src.as_int ()];
|
|
328 }
|
|
329
|
|
330 /* Dump this map to PP. */
|
|
331
|
|
332 template <typename T>
|
|
333 inline void
|
|
334 one_way_id_map<T>::dump_to_pp (pretty_printer *pp) const
|
|
335 {
|
|
336 pp_string (pp, "src to dst: {");
|
|
337 unsigned i;
|
|
338 T *dst;
|
|
339 FOR_EACH_VEC_ELT (m_src_to_dst, i, dst)
|
|
340 {
|
|
341 if (i > 0)
|
|
342 pp_string (pp, ", ");
|
|
343 T src (T::from_int (i));
|
|
344 src.print (pp);
|
|
345 pp_string (pp, " -> ");
|
|
346 dst->print (pp);
|
|
347 }
|
|
348 pp_string (pp, "}");
|
|
349 pp_newline (pp);
|
|
350 }
|
|
351
|
|
352 /* Dump this map to stderr. */
|
|
353
|
|
354 template <typename T>
|
|
355 DEBUG_FUNCTION inline void
|
|
356 one_way_id_map<T>::dump () const
|
|
357 {
|
|
358 pretty_printer pp;
|
|
359 pp.buffer->stream = stderr;
|
|
360 dump_to_pp (&pp);
|
|
361 pp_flush (&pp);
|
|
362 }
|
|
363
|
|
364 /* Update *ID from the old value to its new value in this map. */
|
|
365
|
|
366 template <typename T>
|
|
367 inline void
|
|
368 one_way_id_map<T>::update (T *id) const
|
|
369 {
|
|
370 *id = get_dst_for_src (*id);
|
|
371 }
|
|
372
|
|
373 /* A set of IDs within a region_model (either svalue_id or region_id). */
|
|
374
|
|
375 template <typename T>
|
|
376 class id_set
|
|
377 {
|
|
378 public:
|
|
379 id_set (const region_model *model);
|
|
380
|
|
381 void add_region (T id)
|
|
382 {
|
|
383 if (!id.null_p ())
|
|
384 bitmap_set_bit (m_bitmap, id.as_int ());
|
|
385 }
|
|
386
|
|
387 bool region_p (T id) const
|
|
388 {
|
|
389 gcc_assert (!id.null_p ());
|
|
390 return bitmap_bit_p (const_cast <auto_sbitmap &> (m_bitmap),
|
|
391 id.as_int ());
|
|
392 }
|
|
393
|
|
394 unsigned int num_regions ()
|
|
395 {
|
|
396 return bitmap_count_bits (m_bitmap);
|
|
397 }
|
|
398
|
|
399 private:
|
|
400 auto_sbitmap m_bitmap;
|
|
401 };
|
|
402
|
|
403 typedef id_set<region_id> region_id_set;
|
|
404
|
|
405 /* Various operations delete information from a region_model.
|
|
406
|
|
407 This struct tracks how many of each kind of entity were purged (e.g.
|
|
408 for selftests, and for debugging). */
|
|
409
|
|
410 struct purge_stats
|
|
411 {
|
|
412 purge_stats ()
|
|
413 : m_num_svalues (0),
|
|
414 m_num_regions (0),
|
|
415 m_num_equiv_classes (0),
|
|
416 m_num_constraints (0),
|
|
417 m_num_client_items (0)
|
|
418 {}
|
|
419
|
|
420 int m_num_svalues;
|
|
421 int m_num_regions;
|
|
422 int m_num_equiv_classes;
|
|
423 int m_num_constraints;
|
|
424 int m_num_client_items;
|
|
425 };
|
|
426
|
|
427 /* An enum for discriminating between the different concrete subclasses
|
|
428 of svalue. */
|
|
429
|
|
430 enum svalue_kind
|
|
431 {
|
|
432 SK_REGION,
|
|
433 SK_CONSTANT,
|
|
434 SK_UNKNOWN,
|
|
435 SK_POISONED,
|
|
436 SK_SETJMP
|
|
437 };
|
|
438
|
|
439 /* svalue and its subclasses.
|
|
440
|
|
441 The class hierarchy looks like this (using indentation to show
|
|
442 inheritance, and with svalue_kinds shown for the concrete subclasses):
|
|
443
|
|
444 svalue
|
|
445 region_svalue (SK_REGION)
|
|
446 constant_svalue (SK_CONSTANT)
|
|
447 unknown_svalue (SK_UNKNOWN)
|
|
448 poisoned_svalue (SK_POISONED)
|
|
449 setjmp_svalue (SK_SETJMP). */
|
|
450
|
|
451 /* An abstract base class representing a value held by a region of memory. */
|
|
452
|
|
453 class svalue
|
|
454 {
|
|
455 public:
|
|
456 virtual ~svalue () {}
|
|
457
|
|
458 bool operator== (const svalue &other) const;
|
|
459 bool operator!= (const svalue &other) const { return !(*this == other); }
|
|
460
|
|
461 virtual svalue *clone () const = 0;
|
|
462
|
|
463 tree get_type () const { return m_type; }
|
|
464
|
|
465 virtual enum svalue_kind get_kind () const = 0;
|
|
466
|
|
467 hashval_t hash () const;
|
|
468
|
|
469 void print (const region_model &model,
|
|
470 svalue_id this_sid,
|
|
471 pretty_printer *pp) const;
|
|
472
|
|
473 virtual void dump_dot_to_pp (const region_model &model,
|
|
474 svalue_id this_sid,
|
|
475 pretty_printer *pp) const;
|
|
476
|
|
477 virtual region_svalue *dyn_cast_region_svalue () { return NULL; }
|
|
478 virtual constant_svalue *dyn_cast_constant_svalue () { return NULL; }
|
|
479 virtual const constant_svalue *dyn_cast_constant_svalue () const
|
|
480 { return NULL; }
|
|
481 virtual poisoned_svalue *dyn_cast_poisoned_svalue () { return NULL; }
|
|
482 virtual unknown_svalue *dyn_cast_unknown_svalue () { return NULL; }
|
|
483 virtual setjmp_svalue *dyn_cast_setjmp_svalue () { return NULL; }
|
|
484
|
|
485 virtual void remap_region_ids (const region_id_map &map);
|
|
486
|
|
487 virtual void walk_for_canonicalization (canonicalization *c) const;
|
|
488
|
|
489 virtual svalue_id get_child_sid (region *parent, region *child,
|
|
490 region_model &model,
|
|
491 region_model_context *ctxt);
|
|
492
|
|
493 tree maybe_get_constant () const;
|
|
494
|
|
495 protected:
|
|
496 svalue (tree type) : m_type (type) {}
|
|
497
|
|
498 virtual void add_to_hash (inchash::hash &hstate) const = 0;
|
|
499
|
|
500 private:
|
|
501 virtual void print_details (const region_model &model,
|
|
502 svalue_id this_sid,
|
|
503 pretty_printer *pp) const = 0;
|
|
504 tree m_type;
|
|
505 };
|
|
506
|
|
507 /* Concrete subclass of svalue representing a pointer value that points to
|
|
508 a known region */
|
|
509
|
|
510 class region_svalue : public svalue
|
|
511 {
|
|
512 public:
|
|
513 region_svalue (tree type, region_id rid) : svalue (type), m_rid (rid)
|
|
514 {
|
|
515 /* Should we support NULL ptrs here? */
|
|
516 gcc_assert (!rid.null_p ());
|
|
517 }
|
|
518
|
|
519 bool compare_fields (const region_svalue &other) const;
|
|
520
|
|
521 svalue *clone () const FINAL OVERRIDE
|
|
522 { return new region_svalue (get_type (), m_rid); }
|
|
523
|
|
524 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_REGION; }
|
|
525
|
|
526 void dump_dot_to_pp (const region_model &model,
|
|
527 svalue_id this_sid,
|
|
528 pretty_printer *pp) const
|
|
529 FINAL OVERRIDE;
|
|
530
|
|
531 region_svalue *dyn_cast_region_svalue () FINAL OVERRIDE { return this; }
|
|
532
|
|
533 region_id get_pointee () const { return m_rid; }
|
|
534
|
|
535 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
|
|
536
|
|
537 static void merge_values (const region_svalue ®ion_sval_a,
|
|
538 const region_svalue ®ion_sval_b,
|
|
539 svalue_id *merged_sid,
|
|
540 tree type,
|
|
541 model_merger *merger);
|
|
542
|
|
543 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
|
|
544
|
|
545 static tristate eval_condition (region_svalue *lhs_ptr,
|
|
546 enum tree_code op,
|
|
547 region_svalue *rhs_ptr);
|
|
548
|
|
549 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
|
|
550
|
|
551 private:
|
|
552 void print_details (const region_model &model,
|
|
553 svalue_id this_sid,
|
|
554 pretty_printer *pp) const
|
|
555 FINAL OVERRIDE;
|
|
556
|
|
557 region_id m_rid;
|
|
558 };
|
|
559
|
|
560 } // namespace ana
|
|
561
|
|
562 template <>
|
|
563 template <>
|
|
564 inline bool
|
|
565 is_a_helper <region_svalue *>::test (svalue *sval)
|
|
566 {
|
|
567 return sval->get_kind () == SK_REGION;
|
|
568 }
|
|
569
|
|
570 namespace ana {
|
|
571
|
|
572 /* Concrete subclass of svalue representing a specific constant value. */
|
|
573
|
|
574 class constant_svalue : public svalue
|
|
575 {
|
|
576 public:
|
|
577 constant_svalue (tree cst_expr)
|
|
578 : svalue (TREE_TYPE (cst_expr)), m_cst_expr (cst_expr)
|
|
579 {
|
|
580 gcc_assert (cst_expr);
|
|
581 gcc_assert (CONSTANT_CLASS_P (cst_expr));
|
|
582 }
|
|
583
|
|
584 bool compare_fields (const constant_svalue &other) const;
|
|
585
|
|
586 svalue *clone () const FINAL OVERRIDE
|
|
587 { return new constant_svalue (m_cst_expr); }
|
|
588
|
|
589 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_CONSTANT; }
|
|
590
|
|
591 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
|
|
592
|
|
593 constant_svalue *dyn_cast_constant_svalue () FINAL OVERRIDE { return this; }
|
|
594 const constant_svalue *dyn_cast_constant_svalue () const FINAL OVERRIDE
|
|
595 { return this; }
|
|
596
|
|
597 tree get_constant () const { return m_cst_expr; }
|
|
598
|
|
599 static void merge_values (const constant_svalue &cst_sval_a,
|
|
600 const constant_svalue &cst_sval_b,
|
|
601 svalue_id *merged_sid,
|
|
602 model_merger *merger);
|
|
603
|
|
604 static tristate eval_condition (constant_svalue *lhs,
|
|
605 enum tree_code op,
|
|
606 constant_svalue *rhs);
|
|
607
|
|
608 svalue_id get_child_sid (region *parent, region *child,
|
|
609 region_model &model,
|
|
610 region_model_context *ctxt) FINAL OVERRIDE;
|
|
611
|
|
612 private:
|
|
613 void print_details (const region_model &model,
|
|
614 svalue_id this_sid,
|
|
615 pretty_printer *pp) const
|
|
616 FINAL OVERRIDE;
|
|
617
|
|
618 tree m_cst_expr;
|
|
619 };
|
|
620
|
|
621 } // namespace ana
|
|
622
|
|
623 template <>
|
|
624 template <>
|
|
625 inline bool
|
|
626 is_a_helper <constant_svalue *>::test (svalue *sval)
|
|
627 {
|
|
628 return sval->get_kind () == SK_CONSTANT;
|
|
629 }
|
|
630
|
|
631 namespace ana {
|
|
632
|
|
633 /* Concrete subclass of svalue representing a unique but unknown value.
|
|
634 Comparisons of variables that share the same unknown value are known
|
|
635 to be equal, even if we don't know what the value is. */
|
|
636
|
|
637 class unknown_svalue : public svalue
|
|
638 {
|
|
639 public:
|
|
640 unknown_svalue (tree type)
|
|
641 : svalue (type)
|
|
642 {}
|
|
643
|
|
644 bool compare_fields (const unknown_svalue &other) const;
|
|
645
|
|
646 svalue *clone () const FINAL OVERRIDE
|
|
647 { return new unknown_svalue (get_type ()); }
|
|
648
|
|
649 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_UNKNOWN; }
|
|
650
|
|
651 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
|
|
652
|
|
653 unknown_svalue *dyn_cast_unknown_svalue () FINAL OVERRIDE { return this; }
|
|
654
|
|
655 private:
|
|
656 void print_details (const region_model &model,
|
|
657 svalue_id this_sid,
|
|
658 pretty_printer *pp) const
|
|
659 FINAL OVERRIDE;
|
|
660 };
|
|
661
|
|
662 /* An enum describing a particular kind of "poisoned" value. */
|
|
663
|
|
664 enum poison_kind
|
|
665 {
|
|
666 /* For use to describe uninitialized memory. */
|
|
667 POISON_KIND_UNINIT,
|
|
668
|
|
669 /* For use to describe freed memory. */
|
|
670 POISON_KIND_FREED,
|
|
671
|
|
672 /* For use on pointers to regions within popped stack frames. */
|
|
673 POISON_KIND_POPPED_STACK
|
|
674 };
|
|
675
|
|
676 extern const char *poison_kind_to_str (enum poison_kind);
|
|
677
|
|
678 /* Concrete subclass of svalue representing a value that should not
|
|
679 be used (e.g. uninitialized memory, freed memory). */
|
|
680
|
|
681 class poisoned_svalue : public svalue
|
|
682 {
|
|
683 public:
|
|
684 poisoned_svalue (enum poison_kind kind, tree type)
|
|
685 : svalue (type), m_kind (kind) {}
|
|
686
|
|
687 bool compare_fields (const poisoned_svalue &other) const;
|
|
688
|
|
689 svalue *clone () const FINAL OVERRIDE
|
|
690 { return new poisoned_svalue (m_kind, get_type ()); }
|
|
691
|
|
692 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_POISONED; }
|
|
693
|
|
694 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
|
|
695
|
|
696 poisoned_svalue *dyn_cast_poisoned_svalue () FINAL OVERRIDE { return this; }
|
|
697
|
|
698 enum poison_kind get_poison_kind () const { return m_kind; }
|
|
699
|
|
700 private:
|
|
701 void print_details (const region_model &model,
|
|
702 svalue_id this_sid,
|
|
703 pretty_printer *pp) const
|
|
704 FINAL OVERRIDE;
|
|
705
|
|
706 enum poison_kind m_kind;
|
|
707 };
|
|
708
|
|
709 } // namespace ana
|
|
710
|
|
711 template <>
|
|
712 template <>
|
|
713 inline bool
|
|
714 is_a_helper <poisoned_svalue *>::test (svalue *sval)
|
|
715 {
|
|
716 return sval->get_kind () == SK_POISONED;
|
|
717 }
|
|
718
|
|
719 namespace ana {
|
|
720
|
|
721 /* A bundle of information recording a setjmp/sigsetjmp call, corresponding
|
|
722 roughly to a jmp_buf. */
|
|
723
|
|
724 struct setjmp_record
|
|
725 {
|
|
726 setjmp_record (const exploded_node *enode,
|
|
727 const gcall *setjmp_call)
|
|
728 : m_enode (enode), m_setjmp_call (setjmp_call)
|
|
729 {
|
|
730 }
|
|
731
|
|
732 bool operator== (const setjmp_record &other) const
|
|
733 {
|
|
734 return (m_enode == other.m_enode
|
|
735 && m_setjmp_call == other.m_setjmp_call);
|
|
736 }
|
|
737
|
|
738 const exploded_node *m_enode;
|
|
739 const gcall *m_setjmp_call;
|
|
740 };
|
|
741
|
|
742 /* Concrete subclass of svalue representing buffers for setjmp/sigsetjmp,
|
|
743 so that longjmp/siglongjmp can potentially "return" to an entirely
|
|
744 different function. */
|
|
745
|
|
746 class setjmp_svalue : public svalue
|
|
747 {
|
|
748 public:
|
|
749 setjmp_svalue (const setjmp_record &setjmp_record,
|
|
750 tree type)
|
|
751 : svalue (type), m_setjmp_record (setjmp_record)
|
|
752 {}
|
|
753
|
|
754 bool compare_fields (const setjmp_svalue &other) const;
|
|
755
|
|
756 svalue *clone () const FINAL OVERRIDE
|
|
757 { return new setjmp_svalue (m_setjmp_record, get_type ()); }
|
|
758
|
|
759 enum svalue_kind get_kind () const FINAL OVERRIDE { return SK_SETJMP; }
|
|
760
|
|
761 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
|
|
762
|
|
763 setjmp_svalue *dyn_cast_setjmp_svalue () FINAL OVERRIDE { return this; }
|
|
764
|
|
765 int get_enode_index () const;
|
|
766
|
|
767 const setjmp_record &get_setjmp_record () const { return m_setjmp_record; }
|
|
768
|
|
769 private:
|
|
770 void print_details (const region_model &model,
|
|
771 svalue_id this_sid,
|
|
772 pretty_printer *pp) const
|
|
773 FINAL OVERRIDE;
|
|
774
|
|
775 setjmp_record m_setjmp_record;
|
|
776 };
|
|
777
|
|
778 /* An enum for discriminating between the different concrete subclasses
|
|
779 of region. */
|
|
780
|
|
781 enum region_kind
|
|
782 {
|
|
783 RK_PRIMITIVE,
|
|
784 RK_STRUCT,
|
|
785 RK_UNION,
|
|
786 RK_FRAME,
|
|
787 RK_GLOBALS,
|
|
788 RK_CODE,
|
|
789 RK_FUNCTION,
|
|
790 RK_ARRAY,
|
|
791 RK_STACK,
|
|
792 RK_HEAP,
|
|
793 RK_ROOT,
|
|
794 RK_SYMBOLIC
|
|
795 };
|
|
796
|
|
797 extern const char *region_kind_to_str (enum region_kind);
|
|
798
|
|
799 /* Region and its subclasses.
|
|
800
|
|
801 The class hierarchy looks like this (using indentation to show
|
|
802 inheritance, and with region_kinds shown for the concrete subclasses):
|
|
803
|
|
804 region
|
|
805 primitive_region (RK_PRIMITIVE)
|
|
806 map_region
|
|
807 struct_or_union_region
|
|
808 struct_region (RK_STRUCT)
|
|
809 union_region (RK_UNION)
|
|
810 scope_region
|
|
811 frame_region (RK_FRAME)
|
|
812 globals_region (RK_GLOBALS)
|
|
813 code_region (RK_CODE)
|
|
814 function_region (RK_FUNCTION)
|
|
815 array_region (RK_ARRAY)
|
|
816 stack_region (RK_STACK)
|
|
817 heap_region (RK_HEAP)
|
|
818 root_region (RK_ROOT)
|
|
819 label_region (RK_FUNCTION)
|
|
820 symbolic_region (RK_SYMBOLIC). */
|
|
821
|
|
822 /* Abstract base class representing a chunk of memory.
|
|
823
|
|
824 Regions form a tree-like hierarchy, with a root region at the base,
|
|
825 with memory space regions within it, representing the stack and
|
|
826 globals, with frames within the stack, and regions for variables
|
|
827 within the frames and the "globals" region. Regions for structs
|
|
828 can have subregions for fields.
|
|
829
|
|
830 A region can optionally have a value, or inherit its value from
|
|
831 the first ancestor with a value. For example, the stack region
|
|
832 has a "uninitialized" poison value which is inherited by all
|
|
833 descendent regions that don't themselves have a value. */
|
|
834
|
|
835 class region
|
|
836 {
|
|
837 public:
|
|
838 virtual ~region () {}
|
|
839
|
|
840 bool operator== (const region &other) const;
|
|
841 bool operator!= (const region &other) const { return !(*this == other); }
|
|
842
|
|
843 virtual region *clone () const = 0;
|
|
844
|
|
845 virtual enum region_kind get_kind () const = 0;
|
|
846 virtual map_region *dyn_cast_map_region () { return NULL; }
|
|
847 virtual const symbolic_region *dyn_cast_symbolic_region () const
|
|
848 { return NULL; }
|
|
849
|
|
850 region_id get_parent () const { return m_parent_rid; }
|
|
851 region *get_parent_region (const region_model &model) const;
|
|
852
|
|
853 void set_value (region_model &model, region_id this_rid, svalue_id rhs_sid,
|
|
854 region_model_context *ctxt);
|
|
855 svalue_id get_value (region_model &model, bool non_null,
|
|
856 region_model_context *ctxt);
|
|
857 svalue_id get_value_direct () const { return m_sval_id; }
|
|
858
|
|
859 svalue_id get_inherited_child_sid (region *child,
|
|
860 region_model &model,
|
|
861 region_model_context *ctxt);
|
|
862
|
|
863 tree get_type () const { return m_type; }
|
|
864
|
|
865 hashval_t hash () const;
|
|
866
|
|
867 void print (const region_model &model,
|
|
868 region_id this_rid,
|
|
869 pretty_printer *pp) const;
|
|
870
|
|
871 virtual void dump_dot_to_pp (const region_model &model,
|
|
872 region_id this_rid,
|
|
873 pretty_printer *pp) const;
|
|
874
|
|
875 void dump_to_pp (const region_model &model,
|
|
876 region_id this_rid,
|
|
877 pretty_printer *pp,
|
|
878 const char *prefix,
|
|
879 bool is_last_child) const;
|
|
880 virtual void dump_child_label (const region_model &model,
|
|
881 region_id this_rid,
|
|
882 region_id child_rid,
|
|
883 pretty_printer *pp) const;
|
|
884
|
|
885 void remap_svalue_ids (const svalue_id_map &map);
|
|
886 virtual void remap_region_ids (const region_id_map &map);
|
|
887
|
|
888 virtual void walk_for_canonicalization (canonicalization *c) const = 0;
|
|
889
|
|
890 void add_view (region_id view_rid, region_model *model);
|
|
891 region_id get_view (tree type, region_model *model) const;
|
|
892 bool is_view_p () const { return m_is_view; }
|
|
893
|
|
894 void validate (const region_model *model) const;
|
|
895
|
|
896 bool non_null_p (const region_model &model) const;
|
|
897
|
|
898 protected:
|
|
899 region (region_id parent_rid, svalue_id sval_id, tree type);
|
|
900 region (const region &other);
|
|
901
|
|
902 virtual void add_to_hash (inchash::hash &hstate) const;
|
|
903 virtual void print_fields (const region_model &model,
|
|
904 region_id this_rid,
|
|
905 pretty_printer *pp) const;
|
|
906
|
|
907 private:
|
|
908 void become_active_view (region_model &model, region_id this_rid);
|
|
909 void deactivate_any_active_view (region_model &model);
|
|
910 void deactivate_view (region_model &model, region_id this_view_rid);
|
|
911
|
|
912 region_id m_parent_rid;
|
|
913 svalue_id m_sval_id;
|
|
914 tree m_type;
|
|
915 /* Child regions that are "views" (one per type). */
|
|
916 auto_vec<region_id> m_view_rids;
|
|
917
|
|
918 bool m_is_view;
|
|
919 region_id m_active_view_rid;
|
|
920 };
|
|
921
|
|
922 } // namespace ana
|
|
923
|
|
924 template <>
|
|
925 template <>
|
|
926 inline bool
|
|
927 is_a_helper <region *>::test (region *)
|
|
928 {
|
|
929 return true;
|
|
930 }
|
|
931
|
|
932 namespace ana {
|
|
933
|
|
934 /* Concrete region subclass for storing "primitive" types (integral types,
|
|
935 pointers, etc). */
|
|
936
|
|
937 class primitive_region : public region
|
|
938 {
|
|
939 public:
|
|
940 primitive_region (region_id parent_rid, tree type)
|
|
941 : region (parent_rid, svalue_id::null (), type)
|
|
942 {}
|
|
943
|
|
944 region *clone () const FINAL OVERRIDE;
|
|
945
|
|
946 enum region_kind get_kind () const FINAL OVERRIDE { return RK_PRIMITIVE; }
|
|
947
|
|
948 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
|
|
949 };
|
|
950
|
|
951 /* A region that has children identified by tree keys.
|
|
952 For example a stack frame has subregions per local, and a region
|
|
953 for a struct has subregions per field. */
|
|
954
|
|
955 class map_region : public region
|
|
956 {
|
|
957 public:
|
|
958 typedef ordered_hash_map<tree, region_id> map_t;
|
|
959 typedef map_t::iterator iterator_t;
|
|
960
|
|
961 map_region (region_id parent_rid, tree type)
|
|
962 : region (parent_rid, svalue_id::null (), type)
|
|
963 {}
|
|
964 map_region (const map_region &other);
|
|
965
|
|
966 map_region *dyn_cast_map_region () FINAL OVERRIDE { return this; }
|
|
967
|
|
968 void dump_dot_to_pp (const region_model &model,
|
|
969 region_id this_rid,
|
|
970 pretty_printer *pp) const
|
|
971 FINAL OVERRIDE;
|
|
972
|
|
973 void dump_child_label (const region_model &model,
|
|
974 region_id this_rid,
|
|
975 region_id child_rid,
|
|
976 pretty_printer *pp) const
|
|
977 FINAL OVERRIDE;
|
|
978
|
|
979 region_id get_or_create (region_model *model,
|
|
980 region_id this_rid,
|
|
981 tree expr, tree type);
|
|
982 void unbind (tree expr);
|
|
983 region_id *get (tree expr);
|
|
984
|
|
985 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
|
|
986
|
|
987 tree get_tree_for_child_region (region_id child_rid) const;
|
|
988
|
|
989 tree get_tree_for_child_region (region *child,
|
|
990 const region_model &model) const;
|
|
991
|
|
992 static bool can_merge_p (const map_region *map_region_a,
|
|
993 const map_region *map_region_b,
|
|
994 map_region *merged_map_region,
|
|
995 region_id merged_rid,
|
|
996 model_merger *merger);
|
|
997
|
|
998 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
|
|
999
|
|
1000 virtual bool valid_key_p (tree key) const = 0;
|
|
1001
|
|
1002 svalue_id get_value_by_name (tree identifier,
|
|
1003 const region_model &model) const;
|
|
1004
|
|
1005 iterator_t begin () { return m_map.begin (); }
|
|
1006 iterator_t end () { return m_map.end (); }
|
|
1007 size_t elements () const { return m_map.elements (); }
|
|
1008
|
|
1009 protected:
|
|
1010 bool compare_fields (const map_region &other) const;
|
|
1011 void add_to_hash (inchash::hash &hstate) const OVERRIDE;
|
|
1012 void print_fields (const region_model &model,
|
|
1013 region_id this_rid,
|
|
1014 pretty_printer *pp) const
|
|
1015 OVERRIDE;
|
|
1016
|
|
1017 private:
|
|
1018 /* Mapping from tree to child region. */
|
|
1019 map_t m_map;
|
|
1020 };
|
|
1021
|
|
1022 } // namespace ana
|
|
1023
|
|
1024 template <>
|
|
1025 template <>
|
|
1026 inline bool
|
|
1027 is_a_helper <map_region *>::test (region *reg)
|
|
1028 {
|
|
1029 return (reg->dyn_cast_map_region () != NULL);
|
|
1030 }
|
|
1031
|
|
1032 namespace ana {
|
|
1033
|
|
1034 /* Abstract subclass representing a region with fields
|
|
1035 (either a struct or a union). */
|
|
1036
|
|
1037 class struct_or_union_region : public map_region
|
|
1038 {
|
|
1039 public:
|
|
1040 bool valid_key_p (tree key) const FINAL OVERRIDE;
|
|
1041
|
|
1042 protected:
|
|
1043 struct_or_union_region (region_id parent_rid, tree type)
|
|
1044 : map_region (parent_rid, type)
|
|
1045 {}
|
|
1046
|
|
1047 bool compare_fields (const struct_or_union_region &other) const;
|
|
1048 };
|
|
1049
|
|
1050 } // namespace ana
|
|
1051
|
|
1052 template <>
|
|
1053 template <>
|
|
1054 inline bool
|
|
1055 is_a_helper <struct_or_union_region *>::test (region *reg)
|
|
1056 {
|
|
1057 return (reg->get_kind () == RK_STRUCT
|
|
1058 || reg->get_kind () == RK_UNION);
|
|
1059 }
|
|
1060
|
|
1061 namespace ana {
|
|
1062
|
|
1063 /* Concrete region subclass. A map_region representing a struct, using
|
|
1064 FIELD_DECLs for its keys. */
|
|
1065
|
|
1066 class struct_region : public struct_or_union_region
|
|
1067 {
|
|
1068 public:
|
|
1069 struct_region (region_id parent_rid, tree type)
|
|
1070 : struct_or_union_region (parent_rid, type)
|
|
1071 {
|
|
1072 gcc_assert (TREE_CODE (type) == RECORD_TYPE);
|
|
1073 }
|
|
1074
|
|
1075 region *clone () const FINAL OVERRIDE;
|
|
1076
|
|
1077 enum region_kind get_kind () const FINAL OVERRIDE { return RK_STRUCT; }
|
|
1078
|
|
1079 bool compare_fields (const struct_region &other) const;
|
|
1080 };
|
|
1081
|
|
1082 } // namespace ana
|
|
1083
|
|
1084 template <>
|
|
1085 template <>
|
|
1086 inline bool
|
|
1087 is_a_helper <struct_region *>::test (region *reg)
|
|
1088 {
|
|
1089 return reg->get_kind () == RK_STRUCT;
|
|
1090 }
|
|
1091
|
|
1092 namespace ana {
|
|
1093
|
|
1094 /* Concrete region subclass. A map_region representing a union, using
|
|
1095 FIELD_DECLs for its keys. */
|
|
1096
|
|
1097 class union_region : public struct_or_union_region
|
|
1098 {
|
|
1099 public:
|
|
1100 union_region (region_id parent_rid, tree type)
|
|
1101 : struct_or_union_region (parent_rid, type)
|
|
1102 {
|
|
1103 gcc_assert (TREE_CODE (type) == UNION_TYPE);
|
|
1104 }
|
|
1105
|
|
1106 region *clone () const FINAL OVERRIDE;
|
|
1107
|
|
1108 enum region_kind get_kind () const FINAL OVERRIDE { return RK_UNION; }
|
|
1109
|
|
1110 bool compare_fields (const union_region &other) const;
|
|
1111 };
|
|
1112
|
|
1113 } // namespace ana
|
|
1114
|
|
1115 template <>
|
|
1116 template <>
|
|
1117 inline bool
|
|
1118 is_a_helper <union_region *>::test (region *reg)
|
|
1119 {
|
|
1120 return reg->get_kind () == RK_UNION;
|
|
1121 }
|
|
1122
|
|
1123 namespace ana {
|
|
1124
|
|
1125 /* Abstract map_region subclass for accessing decls, used as a base class
|
|
1126 for function frames and for the globals region. */
|
|
1127
|
|
1128 class scope_region : public map_region
|
|
1129 {
|
|
1130 public:
|
|
1131
|
|
1132 protected:
|
|
1133 scope_region (region_id parent_rid)
|
|
1134 : map_region (parent_rid, NULL_TREE)
|
|
1135 {}
|
|
1136
|
|
1137 scope_region (const scope_region &other)
|
|
1138 : map_region (other)
|
|
1139 {
|
|
1140 }
|
|
1141
|
|
1142 bool compare_fields (const scope_region &other) const;
|
|
1143 };
|
|
1144
|
|
1145 /* Concrete region subclass, representing a function frame on the stack,
|
|
1146 to contain the locals. */
|
|
1147
|
|
1148 class frame_region : public scope_region
|
|
1149 {
|
|
1150 public:
|
|
1151 frame_region (region_id parent_rid, function *fun, int depth)
|
|
1152 : scope_region (parent_rid), m_fun (fun), m_depth (depth)
|
|
1153 {}
|
|
1154
|
|
1155 frame_region (const frame_region &other)
|
|
1156 : scope_region (other), m_fun (other.m_fun), m_depth (other.m_depth)
|
|
1157 {
|
|
1158 }
|
|
1159
|
|
1160 /* region vfuncs. */
|
|
1161 region *clone () const FINAL OVERRIDE;
|
|
1162 enum region_kind get_kind () const FINAL OVERRIDE { return RK_FRAME; }
|
|
1163 void print_fields (const region_model &model,
|
|
1164 region_id this_rid,
|
|
1165 pretty_printer *pp) const
|
|
1166 FINAL OVERRIDE;
|
|
1167 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
|
|
1168
|
|
1169 /* map_region vfuncs. */
|
|
1170 bool valid_key_p (tree key) const FINAL OVERRIDE;
|
|
1171
|
|
1172 /* Accessors. */
|
|
1173 function *get_function () const { return m_fun; }
|
|
1174 int get_depth () const { return m_depth; }
|
|
1175
|
|
1176 bool compare_fields (const frame_region &other) const;
|
|
1177
|
|
1178 private:
|
|
1179 function *m_fun;
|
|
1180 int m_depth;
|
|
1181 };
|
|
1182
|
|
1183 } // namespace ana
|
|
1184
|
|
1185 template <>
|
|
1186 template <>
|
|
1187 inline bool
|
|
1188 is_a_helper <frame_region *>::test (region *reg)
|
|
1189 {
|
|
1190 return reg->get_kind () == RK_FRAME;
|
|
1191 }
|
|
1192
|
|
1193 namespace ana {
|
|
1194
|
|
1195 /* Concrete region subclass, to hold global variables (data and bss). */
|
|
1196
|
|
1197 class globals_region : public scope_region
|
|
1198 {
|
|
1199 public:
|
|
1200 globals_region (region_id parent_rid)
|
|
1201 : scope_region (parent_rid)
|
|
1202 {}
|
|
1203
|
|
1204 globals_region (const globals_region &other)
|
|
1205 : scope_region (other)
|
|
1206 {
|
|
1207 }
|
|
1208
|
|
1209 /* region vfuncs. */
|
|
1210 region *clone () const FINAL OVERRIDE;
|
|
1211 enum region_kind get_kind () const FINAL OVERRIDE { return RK_GLOBALS; }
|
|
1212
|
|
1213 /* map_region vfuncs. */
|
|
1214 bool valid_key_p (tree key) const FINAL OVERRIDE;
|
|
1215
|
|
1216 bool compare_fields (const globals_region &other) const;
|
|
1217 };
|
|
1218
|
|
1219 } // namespace ana
|
|
1220
|
|
1221 template <>
|
|
1222 template <>
|
|
1223 inline bool
|
|
1224 is_a_helper <globals_region *>::test (region *reg)
|
|
1225 {
|
|
1226 return reg->get_kind () == RK_GLOBALS;
|
|
1227 }
|
|
1228
|
|
1229 namespace ana {
|
|
1230
|
|
1231 /* Concrete region subclass. A map_region representing the code, using
|
|
1232 FUNCTION_DECLs for its keys. */
|
|
1233
|
|
1234 class code_region : public map_region
|
|
1235 {
|
|
1236 public:
|
|
1237 code_region (region_id parent_rid)
|
|
1238 : map_region (parent_rid, NULL_TREE)
|
|
1239 {}
|
|
1240 code_region (const code_region &other)
|
|
1241 : map_region (other)
|
|
1242 {}
|
|
1243
|
|
1244 /* region vfuncs. */
|
|
1245 region *clone () const FINAL OVERRIDE;
|
|
1246 enum region_kind get_kind () const FINAL OVERRIDE { return RK_CODE; }
|
|
1247
|
|
1248 /* map_region vfunc. */
|
|
1249 bool valid_key_p (tree key) const FINAL OVERRIDE;
|
|
1250
|
|
1251 region_id get_element (region_model *model,
|
|
1252 region_id this_rid,
|
|
1253 svalue_id index_sid,
|
|
1254 region_model_context *ctxt);
|
|
1255
|
|
1256 bool compare_fields (const code_region &other) const;
|
|
1257 };
|
|
1258
|
|
1259 } // namespace ana
|
|
1260
|
|
1261 template <>
|
|
1262 template <>
|
|
1263 inline bool
|
|
1264 is_a_helper <code_region *>::test (region *reg)
|
|
1265 {
|
|
1266 return reg->get_kind () == RK_CODE;
|
|
1267 }
|
|
1268
|
|
1269 namespace ana {
|
|
1270
|
|
1271 /* Concrete region subclass. A map_region representing the code for
|
|
1272 a particular function, using LABEL_DECLs for its keys. */
|
|
1273
|
|
1274 class function_region : public map_region
|
|
1275 {
|
|
1276 public:
|
|
1277 function_region (region_id parent_rid, tree type)
|
|
1278 : map_region (parent_rid, type)
|
|
1279 {
|
|
1280 gcc_assert (FUNC_OR_METHOD_TYPE_P (type));
|
|
1281 }
|
|
1282 function_region (const function_region &other)
|
|
1283 : map_region (other)
|
|
1284 {}
|
|
1285
|
|
1286 /* region vfuncs. */
|
|
1287 region *clone () const FINAL OVERRIDE;
|
|
1288 enum region_kind get_kind () const FINAL OVERRIDE { return RK_FUNCTION; }
|
|
1289
|
|
1290 /* map_region vfunc. */
|
|
1291 bool valid_key_p (tree key) const FINAL OVERRIDE;
|
|
1292
|
|
1293 region_id get_element (region_model *model,
|
|
1294 region_id this_rid,
|
|
1295 svalue_id index_sid,
|
|
1296 region_model_context *ctxt);
|
|
1297
|
|
1298 bool compare_fields (const function_region &other) const;
|
|
1299 };
|
|
1300
|
|
1301 } // namespace ana
|
|
1302
|
|
1303 template <>
|
|
1304 template <>
|
|
1305 inline bool
|
|
1306 is_a_helper <function_region *>::test (region *reg)
|
|
1307 {
|
|
1308 return reg->get_kind () == RK_FUNCTION;
|
|
1309 }
|
|
1310
|
|
1311 namespace ana {
|
|
1312
|
|
1313 /* Concrete region subclass representing an array (or an array-like view
|
|
1314 of a parent region of memory.
|
|
1315 This can't be a map_region as we can't use trees as the keys: there's
|
|
1316 no guarantee about the uniqueness of an INTEGER_CST. */
|
|
1317
|
|
1318 class array_region : public region
|
|
1319 {
|
|
1320 public:
|
|
1321 #if 0
|
|
1322 wide_int m_test;
|
|
1323
|
|
1324 typedef wide_int key_t;
|
|
1325 typedef int_hash <wide_int, -1, -2> hash_t;
|
|
1326 typedef ordered_hash_map<hash_t, region_id> map_t;
|
|
1327 #else
|
|
1328 typedef int key_t;
|
|
1329 typedef int_hash <int, -1, -2> int_hash_t;
|
|
1330 typedef ordered_hash_map<int_hash_t, region_id> map_t;
|
|
1331 #endif
|
|
1332 typedef map_t::iterator iterator_t;
|
|
1333
|
|
1334 array_region (region_id parent_rid, tree type)
|
|
1335 : region (parent_rid, svalue_id::null (), type)
|
|
1336 {
|
|
1337 gcc_assert (TREE_CODE (type) == ARRAY_TYPE);
|
|
1338 }
|
|
1339 array_region (const array_region &other);
|
|
1340
|
|
1341 void dump_dot_to_pp (const region_model &model,
|
|
1342 region_id this_rid,
|
|
1343 pretty_printer *pp) const
|
|
1344 FINAL OVERRIDE;
|
|
1345
|
|
1346 void dump_child_label (const region_model &model,
|
|
1347 region_id this_rid,
|
|
1348 region_id child_rid,
|
|
1349 pretty_printer *pp) const
|
|
1350 FINAL OVERRIDE;
|
|
1351
|
|
1352 /* region vfuncs. */
|
|
1353 region *clone () const FINAL OVERRIDE;
|
|
1354 enum region_kind get_kind () const FINAL OVERRIDE { return RK_ARRAY; }
|
|
1355
|
|
1356 region_id get_element (region_model *model,
|
|
1357 region_id this_rid,
|
|
1358 svalue_id index_sid,
|
|
1359 region_model_context *ctxt);
|
|
1360
|
|
1361 bool compare_fields (const array_region &other) const;
|
|
1362
|
|
1363 static bool can_merge_p (const array_region *array_region_a,
|
|
1364 const array_region *array_region_b,
|
|
1365 array_region *merged_array_region,
|
|
1366 region_id merged_rid,
|
|
1367 model_merger *merger);
|
|
1368
|
|
1369 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
|
|
1370
|
|
1371 iterator_t begin () { return m_map.begin (); }
|
|
1372 iterator_t end () { return m_map.end (); }
|
|
1373 size_t elements () const { return m_map.elements (); }
|
|
1374
|
|
1375 region_id get_or_create (region_model *model,
|
|
1376 region_id this_rid,
|
|
1377 key_t key, tree type);
|
|
1378 // void unbind (int expr);
|
|
1379 region_id *get (key_t key);
|
|
1380
|
|
1381 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
|
|
1382
|
|
1383 bool get_key_for_child_region (region_id child_rid,
|
|
1384 key_t *out) const;
|
|
1385
|
|
1386 #if 0
|
|
1387 bool get_key_for_child_region (region *child,
|
|
1388 const region_model &model,
|
|
1389 key_t *out) const;
|
|
1390 #endif
|
|
1391
|
|
1392 void add_to_hash (inchash::hash &hstate) const OVERRIDE;
|
|
1393 void print_fields (const region_model &model,
|
|
1394 region_id this_rid,
|
|
1395 pretty_printer *pp) const
|
|
1396 OVERRIDE;
|
|
1397
|
|
1398 static key_t key_from_constant (tree cst);
|
|
1399
|
|
1400 private:
|
|
1401 static int key_cmp (const void *, const void *);
|
|
1402
|
|
1403 /* Mapping from tree to child region. */
|
|
1404 map_t m_map;
|
|
1405 };
|
|
1406
|
|
1407 } // namespace ana
|
|
1408
|
|
1409 template <>
|
|
1410 template <>
|
|
1411 inline bool
|
|
1412 is_a_helper <array_region *>::test (region *reg)
|
|
1413 {
|
|
1414 return reg->get_kind () == RK_ARRAY;
|
|
1415 }
|
|
1416
|
|
1417 namespace ana {
|
|
1418
|
|
1419 /* Concrete region subclass representing a stack, containing all stack
|
|
1420 frames, and implicitly providing a POISON_KIND_UNINIT value to all
|
|
1421 child regions by default. */
|
|
1422
|
|
1423 class stack_region : public region
|
|
1424 {
|
|
1425 public:
|
|
1426 stack_region (region_id parent_rid, svalue_id sval_id)
|
|
1427 : region (parent_rid, sval_id, NULL_TREE)
|
|
1428 {}
|
|
1429
|
|
1430 stack_region (const stack_region &other);
|
|
1431
|
|
1432 bool compare_fields (const stack_region &other) const;
|
|
1433
|
|
1434 region *clone () const FINAL OVERRIDE;
|
|
1435
|
|
1436 enum region_kind get_kind () const FINAL OVERRIDE { return RK_STACK; }
|
|
1437
|
|
1438 void dump_child_label (const region_model &model,
|
|
1439 region_id this_rid,
|
|
1440 region_id child_rid,
|
|
1441 pretty_printer *pp) const
|
|
1442 FINAL OVERRIDE;
|
|
1443
|
|
1444 void push_frame (region_id frame_rid);
|
|
1445 region_id get_current_frame_id () const;
|
|
1446 svalue_id pop_frame (region_model *model, bool purge, purge_stats *stats,
|
|
1447 region_model_context *ctxt);
|
|
1448
|
|
1449 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
|
|
1450
|
|
1451 unsigned get_num_frames () const { return m_frame_rids.length (); }
|
|
1452 region_id get_frame_rid (unsigned i) const { return m_frame_rids[i]; }
|
|
1453
|
|
1454 static bool can_merge_p (const stack_region *stack_region_a,
|
|
1455 const stack_region *stack_region_b,
|
|
1456 model_merger *merger);
|
|
1457
|
|
1458 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
|
|
1459
|
|
1460 svalue_id get_value_by_name (tree identifier,
|
|
1461 const region_model &model) const;
|
|
1462
|
|
1463 private:
|
|
1464 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
|
|
1465 void print_fields (const region_model &model,
|
|
1466 region_id this_rid,
|
|
1467 pretty_printer *pp) const
|
|
1468 FINAL OVERRIDE;
|
|
1469
|
|
1470 auto_vec<region_id> m_frame_rids;
|
|
1471 };
|
|
1472
|
|
1473 } // namespace ana
|
|
1474
|
|
1475 template <>
|
|
1476 template <>
|
|
1477 inline bool
|
|
1478 is_a_helper <stack_region *>::test (region *reg)
|
|
1479 {
|
|
1480 return reg->get_kind () == RK_STACK;
|
|
1481 }
|
|
1482
|
|
1483 namespace ana {
|
|
1484
|
|
1485 /* Concrete region subclass: a region within which regions can be
|
|
1486 dynamically allocated. */
|
|
1487
|
|
1488 class heap_region : public region
|
|
1489 {
|
|
1490 public:
|
|
1491 heap_region (region_id parent_rid, svalue_id sval_id)
|
|
1492 : region (parent_rid, sval_id, NULL_TREE)
|
|
1493 {}
|
|
1494 heap_region (const heap_region &other);
|
|
1495
|
|
1496 bool compare_fields (const heap_region &other) const;
|
|
1497
|
|
1498 region *clone () const FINAL OVERRIDE;
|
|
1499
|
|
1500 enum region_kind get_kind () const FINAL OVERRIDE { return RK_HEAP; }
|
|
1501
|
|
1502 static bool can_merge_p (const heap_region *heap_a, region_id heap_a_rid,
|
|
1503 const heap_region *heap_b, region_id heap_b_rid,
|
|
1504 heap_region *merged_heap, region_id merged_heap_rid,
|
|
1505 model_merger *merger);
|
|
1506
|
|
1507 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
|
|
1508
|
|
1509 };
|
|
1510
|
|
1511 } // namespace ana
|
|
1512
|
|
1513 template <>
|
|
1514 template <>
|
|
1515 inline bool
|
|
1516 is_a_helper <heap_region *>::test (region *reg)
|
|
1517 {
|
|
1518 return reg->get_kind () == RK_HEAP;
|
|
1519 }
|
|
1520
|
|
1521 namespace ana {
|
|
1522
|
|
1523 /* Concrete region subclass. The root region, containing all regions
|
|
1524 (either directly, or as descendents).
|
|
1525 Unique within a region_model. */
|
|
1526
|
|
1527 class root_region : public region
|
|
1528 {
|
|
1529 public:
|
|
1530 root_region ();
|
|
1531 root_region (const root_region &other);
|
|
1532
|
|
1533 bool compare_fields (const root_region &other) const;
|
|
1534
|
|
1535 region *clone () const FINAL OVERRIDE;
|
|
1536
|
|
1537 enum region_kind get_kind () const FINAL OVERRIDE { return RK_ROOT; }
|
|
1538
|
|
1539 void dump_child_label (const region_model &model,
|
|
1540 region_id this_rid,
|
|
1541 region_id child_rid,
|
|
1542 pretty_printer *pp) const
|
|
1543 FINAL OVERRIDE;
|
|
1544
|
|
1545 region_id push_frame (region_model *model, function *fun,
|
|
1546 vec<svalue_id> *arg_sids,
|
|
1547 region_model_context *ctxt);
|
|
1548 region_id get_current_frame_id (const region_model &model) const;
|
|
1549 svalue_id pop_frame (region_model *model, bool purge, purge_stats *stats,
|
|
1550 region_model_context *ctxt);
|
|
1551
|
|
1552 region_id ensure_stack_region (region_model *model);
|
|
1553 region_id get_stack_region_id () const { return m_stack_rid; }
|
|
1554 stack_region *get_stack_region (const region_model *model) const;
|
|
1555
|
|
1556 region_id ensure_globals_region (region_model *model);
|
|
1557 region_id get_globals_region_id () const { return m_globals_rid; }
|
|
1558 globals_region *get_globals_region (const region_model *model) const;
|
|
1559
|
|
1560 region_id ensure_code_region (region_model *model);
|
|
1561 code_region *get_code_region (const region_model *model) const;
|
|
1562
|
|
1563 region_id ensure_heap_region (region_model *model);
|
|
1564 heap_region *get_heap_region (const region_model *model) const;
|
|
1565
|
|
1566 void remap_region_ids (const region_id_map &map) FINAL OVERRIDE;
|
|
1567
|
|
1568 static bool can_merge_p (const root_region *root_region_a,
|
|
1569 const root_region *root_region_b,
|
|
1570 root_region *merged_root_region,
|
|
1571 model_merger *merger);
|
|
1572
|
|
1573 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
|
|
1574
|
|
1575 svalue_id get_value_by_name (tree identifier,
|
|
1576 const region_model &model) const;
|
|
1577
|
|
1578 private:
|
|
1579 void add_to_hash (inchash::hash &hstate) const FINAL OVERRIDE;
|
|
1580 void print_fields (const region_model &model,
|
|
1581 region_id this_rid,
|
|
1582 pretty_printer *pp) const
|
|
1583 FINAL OVERRIDE;
|
|
1584
|
|
1585 region_id m_stack_rid;
|
|
1586 region_id m_globals_rid;
|
|
1587 region_id m_code_rid;
|
|
1588 region_id m_heap_rid;
|
|
1589 };
|
|
1590
|
|
1591 } // namespace ana
|
|
1592
|
|
1593 template <>
|
|
1594 template <>
|
|
1595 inline bool
|
|
1596 is_a_helper <root_region *>::test (region *reg)
|
|
1597 {
|
|
1598 return reg->get_kind () == RK_ROOT;
|
|
1599 }
|
|
1600
|
|
1601 namespace ana {
|
|
1602
|
|
1603 /* Concrete region subclass: a region to use when dereferencing an unknown
|
|
1604 pointer. */
|
|
1605
|
|
1606 class symbolic_region : public region
|
|
1607 {
|
|
1608 public:
|
|
1609 symbolic_region (region_id parent_rid, tree type, bool possibly_null)
|
|
1610 : region (parent_rid, svalue_id::null (), type),
|
|
1611 m_possibly_null (possibly_null)
|
|
1612 {}
|
|
1613 symbolic_region (const symbolic_region &other);
|
|
1614
|
|
1615 const symbolic_region *dyn_cast_symbolic_region () const FINAL OVERRIDE
|
|
1616 { return this; }
|
|
1617
|
|
1618 bool compare_fields (const symbolic_region &other) const;
|
|
1619
|
|
1620 region *clone () const FINAL OVERRIDE;
|
|
1621
|
|
1622 enum region_kind get_kind () const FINAL OVERRIDE { return RK_SYMBOLIC; }
|
|
1623
|
|
1624 void walk_for_canonicalization (canonicalization *c) const FINAL OVERRIDE;
|
|
1625
|
|
1626 bool m_possibly_null;
|
|
1627 };
|
|
1628
|
|
1629 /* A region_model encapsulates a representation of the state of memory, with
|
|
1630 a tree of regions, along with their associated values.
|
|
1631 The representation is graph-like because values can be pointers to
|
|
1632 regions.
|
|
1633 It also stores a constraint_manager, capturing relationships between
|
|
1634 the values. */
|
|
1635
|
|
1636 class region_model
|
|
1637 {
|
|
1638 public:
|
|
1639 region_model ();
|
|
1640 region_model (const region_model &other);
|
|
1641 ~region_model ();
|
|
1642
|
|
1643 #if 0//__cplusplus >= 201103
|
|
1644 region_model (region_model &&other);
|
|
1645 #endif
|
|
1646
|
|
1647 region_model &operator= (const region_model &other);
|
|
1648
|
|
1649 bool operator== (const region_model &other) const;
|
|
1650 bool operator!= (const region_model &other) const
|
|
1651 {
|
|
1652 return !(*this == other);
|
|
1653 }
|
|
1654
|
|
1655 hashval_t hash () const;
|
|
1656
|
|
1657 void print (pretty_printer *pp) const;
|
|
1658
|
|
1659 void print_svalue (svalue_id sid, pretty_printer *pp) const;
|
|
1660
|
|
1661 void dump_dot_to_pp (pretty_printer *pp) const;
|
|
1662 void dump_dot_to_file (FILE *fp) const;
|
|
1663 void dump_dot (const char *path) const;
|
|
1664
|
|
1665 void dump_to_pp (pretty_printer *pp, bool summarize) const;
|
|
1666 void dump (FILE *fp, bool summarize) const;
|
|
1667 void dump (bool summarize) const;
|
|
1668
|
|
1669 void debug () const;
|
|
1670
|
|
1671 void validate () const;
|
|
1672
|
|
1673 void canonicalize (region_model_context *ctxt);
|
|
1674 bool canonicalized_p () const;
|
|
1675
|
|
1676 void check_for_poison (tree expr, region_model_context *ctxt);
|
|
1677 void on_assignment (const gassign *stmt, region_model_context *ctxt);
|
|
1678 bool on_call_pre (const gcall *stmt, region_model_context *ctxt);
|
|
1679 void on_call_post (const gcall *stmt,
|
|
1680 bool unknown_side_effects,
|
|
1681 region_model_context *ctxt);
|
|
1682 void handle_unrecognized_call (const gcall *call,
|
|
1683 region_model_context *ctxt);
|
|
1684 void on_return (const greturn *stmt, region_model_context *ctxt);
|
|
1685 void on_setjmp (const gcall *stmt, const exploded_node *enode,
|
|
1686 region_model_context *ctxt);
|
|
1687 void on_longjmp (const gcall *longjmp_call, const gcall *setjmp_call,
|
|
1688 int setjmp_stack_depth, region_model_context *ctxt);
|
|
1689
|
|
1690 void update_for_phis (const supernode *snode,
|
|
1691 const cfg_superedge *last_cfg_superedge,
|
|
1692 region_model_context *ctxt);
|
|
1693
|
|
1694 void handle_phi (const gphi *phi,
|
|
1695 tree lhs, tree rhs, bool is_back_edge,
|
|
1696 region_model_context *ctxt);
|
|
1697
|
|
1698 bool maybe_update_for_edge (const superedge &edge,
|
|
1699 const gimple *last_stmt,
|
|
1700 region_model_context *ctxt);
|
|
1701
|
|
1702 region_id get_root_rid () const { return m_root_rid; }
|
|
1703 root_region *get_root_region () const;
|
|
1704
|
|
1705 region_id get_stack_region_id () const;
|
|
1706 region_id push_frame (function *fun, vec<svalue_id> *arg_sids,
|
|
1707 region_model_context *ctxt);
|
|
1708 region_id get_current_frame_id () const;
|
|
1709 function * get_current_function () const;
|
|
1710 svalue_id pop_frame (bool purge, purge_stats *stats,
|
|
1711 region_model_context *ctxt);
|
|
1712 int get_stack_depth () const;
|
|
1713 function *get_function_at_depth (unsigned depth) const;
|
|
1714
|
|
1715 region_id get_globals_region_id () const;
|
|
1716
|
|
1717 svalue_id add_svalue (svalue *sval);
|
|
1718 void replace_svalue (svalue_id sid, svalue *new_sval);
|
|
1719
|
|
1720 region_id add_region (region *r);
|
|
1721
|
|
1722 region_id add_region_for_type (region_id parent_rid, tree type);
|
|
1723
|
|
1724 svalue *get_svalue (svalue_id sval_id) const;
|
|
1725 region *get_region (region_id rid) const;
|
|
1726
|
|
1727 template <typename Subclass>
|
|
1728 Subclass *get_region (region_id rid) const
|
|
1729 {
|
|
1730 region *result = get_region (rid);
|
|
1731 if (result)
|
|
1732 gcc_assert (is_a<Subclass *> (result));
|
|
1733 return (Subclass *)result;
|
|
1734 }
|
|
1735
|
|
1736 region_id get_lvalue (path_var pv, region_model_context *ctxt);
|
|
1737 region_id get_lvalue (tree expr, region_model_context *ctxt);
|
|
1738 svalue_id get_rvalue (path_var pv, region_model_context *ctxt);
|
|
1739 svalue_id get_rvalue (tree expr, region_model_context *ctxt);
|
|
1740
|
|
1741 svalue_id get_or_create_ptr_svalue (tree ptr_type, region_id id);
|
|
1742 svalue_id get_or_create_constant_svalue (tree cst_expr);
|
|
1743 svalue_id get_svalue_for_fndecl (tree ptr_type, tree fndecl);
|
|
1744 svalue_id get_svalue_for_label (tree ptr_type, tree label);
|
|
1745
|
|
1746 region_id get_region_for_fndecl (tree fndecl);
|
|
1747 region_id get_region_for_label (tree label);
|
|
1748
|
|
1749 svalue_id maybe_cast (tree type, svalue_id sid, region_model_context *ctxt);
|
|
1750 svalue_id maybe_cast_1 (tree type, svalue_id sid);
|
|
1751
|
|
1752 region_id get_field_region (region_id rid, tree field);
|
|
1753
|
|
1754 region_id deref_rvalue (svalue_id ptr_sid, region_model_context *ctxt);
|
|
1755 region_id deref_rvalue (tree ptr, region_model_context *ctxt);
|
|
1756
|
|
1757 void set_value (region_id lhs_rid, svalue_id rhs_sid,
|
|
1758 region_model_context *ctxt);
|
|
1759 svalue_id set_to_new_unknown_value (region_id dst_rid, tree type,
|
|
1760 region_model_context *ctxt);
|
|
1761
|
|
1762 tristate eval_condition (svalue_id lhs,
|
|
1763 enum tree_code op,
|
|
1764 svalue_id rhs) const;
|
|
1765 tristate eval_condition_without_cm (svalue_id lhs,
|
|
1766 enum tree_code op,
|
|
1767 svalue_id rhs) const;
|
|
1768 tristate eval_condition (tree lhs,
|
|
1769 enum tree_code op,
|
|
1770 tree rhs,
|
|
1771 region_model_context *ctxt);
|
|
1772 bool add_constraint (tree lhs, enum tree_code op, tree rhs,
|
|
1773 region_model_context *ctxt);
|
|
1774
|
|
1775 tree maybe_get_constant (svalue_id sid) const;
|
|
1776
|
|
1777 region_id add_new_malloc_region ();
|
|
1778
|
|
1779 tree get_representative_tree (svalue_id sid) const;
|
|
1780 path_var get_representative_path_var (region_id rid) const;
|
|
1781 void get_path_vars_for_svalue (svalue_id sid, vec<path_var> *out) const;
|
|
1782
|
|
1783 void purge_unused_svalues (purge_stats *out,
|
|
1784 region_model_context *ctxt,
|
|
1785 svalue_id *known_used_sid = NULL);
|
|
1786 void remap_svalue_ids (const svalue_id_map &map);
|
|
1787 void remap_region_ids (const region_id_map &map);
|
|
1788
|
|
1789 void purge_regions (const region_id_set &set,
|
|
1790 purge_stats *stats,
|
|
1791 logger *logger);
|
|
1792
|
|
1793 unsigned get_num_svalues () const { return m_svalues.length (); }
|
|
1794 unsigned get_num_regions () const { return m_regions.length (); }
|
|
1795
|
|
1796 /* For selftests. */
|
|
1797 constraint_manager *get_constraints ()
|
|
1798 {
|
|
1799 return m_constraints;
|
|
1800 }
|
|
1801
|
|
1802 void get_descendents (region_id rid, region_id_set *out,
|
|
1803 region_id exclude_rid) const;
|
|
1804
|
|
1805 void delete_region_and_descendents (region_id rid,
|
|
1806 enum poison_kind pkind,
|
|
1807 purge_stats *stats,
|
|
1808 logger *logger);
|
|
1809
|
|
1810 bool can_merge_with_p (const region_model &other_model,
|
|
1811 region_model *out_model,
|
|
1812 svalue_id_merger_mapping *out) const;
|
|
1813 bool can_merge_with_p (const region_model &other_model,
|
|
1814 region_model *out_model) const;
|
|
1815
|
|
1816 svalue_id get_value_by_name (const char *name) const;
|
|
1817
|
|
1818 svalue_id convert_byte_offset_to_array_index (tree ptr_type,
|
|
1819 svalue_id offset_sid);
|
|
1820
|
|
1821 region_id get_or_create_mem_ref (tree type,
|
|
1822 svalue_id ptr_sid,
|
|
1823 svalue_id offset_sid,
|
|
1824 region_model_context *ctxt);
|
|
1825 region_id get_or_create_pointer_plus_expr (tree type,
|
|
1826 svalue_id ptr_sid,
|
|
1827 svalue_id offset_sid,
|
|
1828 region_model_context *ctxt);
|
|
1829 region_id get_or_create_view (region_id raw_rid, tree type);
|
|
1830
|
|
1831 tree get_fndecl_for_call (const gcall *call,
|
|
1832 region_model_context *ctxt);
|
|
1833
|
|
1834 private:
|
|
1835 region_id get_lvalue_1 (path_var pv, region_model_context *ctxt);
|
|
1836 svalue_id get_rvalue_1 (path_var pv, region_model_context *ctxt);
|
|
1837
|
|
1838 void add_any_constraints_from_ssa_def_stmt (tree lhs,
|
|
1839 enum tree_code op,
|
|
1840 tree rhs,
|
|
1841 region_model_context *ctxt);
|
|
1842
|
|
1843 void update_for_call_superedge (const call_superedge &call_edge,
|
|
1844 region_model_context *ctxt);
|
|
1845 void update_for_return_superedge (const return_superedge &return_edge,
|
|
1846 region_model_context *ctxt);
|
|
1847 void update_for_call_summary (const callgraph_superedge &cg_sedge,
|
|
1848 region_model_context *ctxt);
|
|
1849 bool apply_constraints_for_gcond (const cfg_superedge &edge,
|
|
1850 const gcond *cond_stmt,
|
|
1851 region_model_context *ctxt);
|
|
1852 bool apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
|
|
1853 const gswitch *switch_stmt,
|
|
1854 region_model_context *ctxt);
|
|
1855
|
|
1856 void poison_any_pointers_to_bad_regions (const region_id_set &bad_regions,
|
|
1857 enum poison_kind pkind);
|
|
1858
|
|
1859 void dump_summary_of_map (pretty_printer *pp, map_region *map_region,
|
|
1860 bool *is_first) const;
|
|
1861
|
|
1862 auto_delete_vec<svalue> m_svalues;
|
|
1863 auto_delete_vec<region> m_regions;
|
|
1864 region_id m_root_rid;
|
|
1865 constraint_manager *m_constraints; // TODO: embed, rather than dynalloc?
|
|
1866 };
|
|
1867
|
|
1868 /* Some region_model activity could lead to warnings (e.g. attempts to use an
|
|
1869 uninitialized value). This abstract base class encapsulates an interface
|
|
1870 for the region model to use when emitting such warnings.
|
|
1871
|
|
1872 It also provides an interface for being notified about svalue_ids being
|
|
1873 remapped, and being deleted.
|
|
1874
|
|
1875 Having this as an abstract base class allows us to support the various
|
|
1876 operations needed by program_state in the analyzer within region_model,
|
|
1877 whilst keeping them somewhat modularized. */
|
|
1878
|
|
1879 class region_model_context
|
|
1880 {
|
|
1881 public:
|
|
1882 virtual void warn (pending_diagnostic *d) = 0;
|
|
1883
|
|
1884 /* Hook for clients that store svalue_id instances, so that they
|
|
1885 can remap their IDs when the underlying region_model renumbers
|
|
1886 the IDs. */
|
|
1887 virtual void remap_svalue_ids (const svalue_id_map &map) = 0;
|
|
1888
|
|
1889 #if 0
|
|
1890 /* Return true if if's OK to purge SID when simplifying state.
|
|
1891 Subclasses can return false for values that have sm state,
|
|
1892 to avoid generating "leak" false positives. */
|
|
1893 virtual bool can_purge_p (svalue_id sid) = 0;
|
|
1894 #endif
|
|
1895
|
|
1896 /* Hook for clients to be notified when a range of SIDs have
|
|
1897 been purged, so that they can purge state relating to those
|
|
1898 values (and potentially emit warnings about leaks).
|
|
1899 All SIDs from FIRST_PURGED_SID numerically upwards are being
|
|
1900 purged.
|
|
1901 The return values is a count of how many items of data the client
|
|
1902 has purged (potentially for use in selftests).
|
|
1903 MAP has already been applied to the IDs, but is provided in case
|
|
1904 the client needs to figure out the old IDs. */
|
|
1905 virtual int on_svalue_purge (svalue_id first_purged_sid,
|
|
1906 const svalue_id_map &map) = 0;
|
|
1907
|
|
1908 virtual logger *get_logger () = 0;
|
|
1909
|
|
1910 /* Hook for clients to be notified when CHILD_SID is created
|
|
1911 from PARENT_SID, when "inheriting" a value for a region from a
|
|
1912 parent region.
|
|
1913 This exists so that state machines that inherit state can
|
|
1914 propagate the state from parent to child. */
|
|
1915 virtual void on_inherited_svalue (svalue_id parent_sid,
|
|
1916 svalue_id child_sid) = 0;
|
|
1917
|
|
1918 /* Hook for clients to be notified when DST_SID is created
|
|
1919 (or reused) as a cast from SRC_SID.
|
|
1920 This exists so that state machines can propagate the state
|
|
1921 from SRC_SID to DST_SID. */
|
|
1922 virtual void on_cast (svalue_id src_sid,
|
|
1923 svalue_id dst_sid) = 0;
|
|
1924
|
|
1925 /* Hook for clients to be notified when the condition
|
|
1926 "LHS OP RHS" is added to the region model.
|
|
1927 This exists so that state machines can detect tests on edges,
|
|
1928 and use them to trigger sm-state transitions (e.g. transitions due
|
|
1929 to ptrs becoming known to be NULL or non-NULL, rather than just
|
|
1930 "unchecked") */
|
|
1931 virtual void on_condition (tree lhs, enum tree_code op, tree rhs) = 0;
|
|
1932
|
|
1933 /* Hooks for clients to be notified when an unknown change happens
|
|
1934 to SID (in response to a call to an unknown function). */
|
|
1935 virtual void on_unknown_change (svalue_id sid) = 0;
|
|
1936
|
|
1937 /* Hooks for clients to be notified when a phi node is handled,
|
|
1938 where RHS is the pertinent argument. */
|
|
1939 virtual void on_phi (const gphi *phi, tree rhs) = 0;
|
|
1940 };
|
|
1941
|
|
1942 /* A bundle of data for use when attempting to merge two region_model
|
|
1943 instances to make a third. */
|
|
1944
|
|
1945 struct model_merger
|
|
1946 {
|
|
1947 model_merger (const region_model *model_a,
|
|
1948 const region_model *model_b,
|
|
1949 region_model *merged_model,
|
|
1950 svalue_id_merger_mapping *sid_mapping)
|
|
1951 : m_model_a (model_a), m_model_b (model_b),
|
|
1952 m_merged_model (merged_model),
|
|
1953 m_map_regions_from_a_to_m (model_a->get_num_regions ()),
|
|
1954 m_map_regions_from_b_to_m (model_b->get_num_regions ()),
|
|
1955 m_sid_mapping (sid_mapping)
|
|
1956 {
|
|
1957 gcc_assert (sid_mapping);
|
|
1958 }
|
|
1959
|
|
1960 void dump_to_pp (pretty_printer *pp) const;
|
|
1961 void dump (FILE *fp) const;
|
|
1962 void dump () const;
|
|
1963
|
|
1964 template <typename Subclass>
|
|
1965 Subclass *get_region_a (region_id rid_a) const
|
|
1966 {
|
|
1967 return m_model_a->get_region <Subclass> (rid_a);
|
|
1968 }
|
|
1969
|
|
1970 template <typename Subclass>
|
|
1971 Subclass *get_region_b (region_id rid_b) const
|
|
1972 {
|
|
1973 return m_model_b->get_region <Subclass> (rid_b);
|
|
1974 }
|
|
1975
|
|
1976 bool can_merge_values_p (svalue_id sid_a,
|
|
1977 svalue_id sid_b,
|
|
1978 svalue_id *merged_sid);
|
|
1979
|
|
1980 void record_regions (region_id a_rid,
|
|
1981 region_id b_rid,
|
|
1982 region_id merged_rid);
|
|
1983
|
|
1984 void record_svalues (svalue_id a_sid,
|
|
1985 svalue_id b_sid,
|
|
1986 svalue_id merged_sid);
|
|
1987
|
|
1988 const region_model *m_model_a;
|
|
1989 const region_model *m_model_b;
|
|
1990 region_model *m_merged_model;
|
|
1991
|
|
1992 one_way_region_id_map m_map_regions_from_a_to_m;
|
|
1993 one_way_region_id_map m_map_regions_from_b_to_m;
|
|
1994 svalue_id_merger_mapping *m_sid_mapping;
|
|
1995 };
|
|
1996
|
|
1997 /* A bundle of data that can be optionally generated during merger of two
|
|
1998 region_models that describes how svalue_ids in each of the two inputs
|
|
1999 are mapped to svalue_ids in the merged output.
|
|
2000
|
|
2001 For use when merging sm-states within program_state. */
|
|
2002
|
|
2003 struct svalue_id_merger_mapping
|
|
2004 {
|
|
2005 svalue_id_merger_mapping (const region_model &a,
|
|
2006 const region_model &b);
|
|
2007
|
|
2008 void dump_to_pp (pretty_printer *pp) const;
|
|
2009 void dump (FILE *fp) const;
|
|
2010 void dump () const;
|
|
2011
|
|
2012 one_way_svalue_id_map m_map_from_a_to_m;
|
|
2013 one_way_svalue_id_map m_map_from_b_to_m;
|
|
2014 };
|
|
2015
|
|
2016 /* A bundle of data used when canonicalizing a region_model so that the
|
|
2017 order of regions and svalues is in a predictable order (thus increasing
|
|
2018 the chance of two region_models being equal).
|
|
2019
|
|
2020 This object is used to keep track of a recursive traversal across the
|
|
2021 svalues and regions within the model, made in a deterministic order,
|
|
2022 assigning new ids the first time each region or svalue is
|
|
2023 encountered. */
|
|
2024
|
|
2025 struct canonicalization
|
|
2026 {
|
|
2027 canonicalization (const region_model &model);
|
|
2028 void walk_rid (region_id rid);
|
|
2029 void walk_sid (svalue_id sid);
|
|
2030
|
|
2031 void dump_to_pp (pretty_printer *pp) const;
|
|
2032 void dump (FILE *fp) const;
|
|
2033 void dump () const;
|
|
2034
|
|
2035 const region_model &m_model;
|
|
2036 /* Maps from existing IDs to new IDs. */
|
|
2037 region_id_map m_rid_map;
|
|
2038 svalue_id_map m_sid_map;
|
|
2039 /* The next IDs to hand out. */
|
|
2040 int m_next_rid_int;
|
|
2041 int m_next_sid_int;
|
|
2042 };
|
|
2043
|
|
2044 } // namespace ana
|
|
2045
|
|
2046 namespace inchash
|
|
2047 {
|
|
2048 extern void add (svalue_id sid, hash &hstate);
|
|
2049 extern void add (region_id rid, hash &hstate);
|
|
2050 } // namespace inchash
|
|
2051
|
|
2052 extern void debug (const region_model &rmodel);
|
|
2053
|
|
2054 namespace ana {
|
|
2055
|
|
2056 #if CHECKING_P
|
|
2057
|
|
2058 namespace selftest {
|
|
2059
|
|
2060 using namespace ::selftest;
|
|
2061
|
|
2062 /* An implementation of region_model_context for use in selftests, which
|
|
2063 stores any pending_diagnostic instances passed to it. */
|
|
2064
|
|
2065 class test_region_model_context : public region_model_context
|
|
2066 {
|
|
2067 public:
|
|
2068 void warn (pending_diagnostic *d) FINAL OVERRIDE
|
|
2069 {
|
|
2070 m_diagnostics.safe_push (d);
|
|
2071 }
|
|
2072
|
|
2073 void remap_svalue_ids (const svalue_id_map &) FINAL OVERRIDE
|
|
2074 {
|
|
2075 /* Empty. */
|
|
2076 }
|
|
2077
|
|
2078 #if 0
|
|
2079 bool can_purge_p (svalue_id) FINAL OVERRIDE
|
|
2080 {
|
|
2081 return true;
|
|
2082 }
|
|
2083 #endif
|
|
2084
|
|
2085 int on_svalue_purge (svalue_id, const svalue_id_map &) FINAL OVERRIDE
|
|
2086 {
|
|
2087 /* Empty. */
|
|
2088 return 0;
|
|
2089 }
|
|
2090
|
|
2091 logger *get_logger () FINAL OVERRIDE { return NULL; }
|
|
2092
|
|
2093 void on_inherited_svalue (svalue_id parent_sid ATTRIBUTE_UNUSED,
|
|
2094 svalue_id child_sid ATTRIBUTE_UNUSED)
|
|
2095 FINAL OVERRIDE
|
|
2096 {
|
|
2097 }
|
|
2098
|
|
2099 void on_cast (svalue_id src_sid ATTRIBUTE_UNUSED,
|
|
2100 svalue_id dst_sid ATTRIBUTE_UNUSED) FINAL OVERRIDE
|
|
2101 {
|
|
2102 }
|
|
2103
|
|
2104 unsigned get_num_diagnostics () const { return m_diagnostics.length (); }
|
|
2105
|
|
2106 void on_condition (tree lhs ATTRIBUTE_UNUSED,
|
|
2107 enum tree_code op ATTRIBUTE_UNUSED,
|
|
2108 tree rhs ATTRIBUTE_UNUSED) FINAL OVERRIDE
|
|
2109 {
|
|
2110 }
|
|
2111
|
|
2112 void on_unknown_change (svalue_id sid ATTRIBUTE_UNUSED) FINAL OVERRIDE
|
|
2113 {
|
|
2114 }
|
|
2115
|
|
2116 void on_phi (const gphi *phi ATTRIBUTE_UNUSED,
|
|
2117 tree rhs ATTRIBUTE_UNUSED) FINAL OVERRIDE
|
|
2118 {
|
|
2119 }
|
|
2120
|
|
2121 private:
|
|
2122 /* Implicitly delete any diagnostics in the dtor. */
|
|
2123 auto_delete_vec<pending_diagnostic> m_diagnostics;
|
|
2124 };
|
|
2125
|
|
2126 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
|
|
2127 Verify that MODEL remains satisfiable. */
|
|
2128
|
|
2129 #define ADD_SAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
|
|
2130 SELFTEST_BEGIN_STMT \
|
|
2131 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
|
|
2132 ASSERT_TRUE (sat); \
|
|
2133 SELFTEST_END_STMT
|
|
2134
|
|
2135 /* Attempt to add the constraint (LHS OP RHS) to MODEL.
|
|
2136 Verify that the result is not satisfiable. */
|
|
2137
|
|
2138 #define ADD_UNSAT_CONSTRAINT(MODEL, LHS, OP, RHS) \
|
|
2139 SELFTEST_BEGIN_STMT \
|
|
2140 bool sat = (MODEL).add_constraint (LHS, OP, RHS, NULL); \
|
|
2141 ASSERT_FALSE (sat); \
|
|
2142 SELFTEST_END_STMT
|
|
2143
|
|
2144 /* Implementation detail of the ASSERT_CONDITION_* macros. */
|
|
2145
|
|
2146 void assert_condition (const location &loc,
|
|
2147 region_model &model,
|
|
2148 tree lhs, tree_code op, tree rhs,
|
|
2149 tristate expected);
|
|
2150
|
|
2151 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
|
|
2152 as "true". */
|
|
2153
|
|
2154 #define ASSERT_CONDITION_TRUE(REGION_MODEL, LHS, OP, RHS) \
|
|
2155 SELFTEST_BEGIN_STMT \
|
|
2156 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
|
|
2157 tristate (tristate::TS_TRUE)); \
|
|
2158 SELFTEST_END_STMT
|
|
2159
|
|
2160 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
|
|
2161 as "false". */
|
|
2162
|
|
2163 #define ASSERT_CONDITION_FALSE(REGION_MODEL, LHS, OP, RHS) \
|
|
2164 SELFTEST_BEGIN_STMT \
|
|
2165 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
|
|
2166 tristate (tristate::TS_FALSE)); \
|
|
2167 SELFTEST_END_STMT
|
|
2168
|
|
2169 /* Assert that REGION_MODEL evaluates the condition "LHS OP RHS"
|
|
2170 as "unknown". */
|
|
2171
|
|
2172 #define ASSERT_CONDITION_UNKNOWN(REGION_MODEL, LHS, OP, RHS) \
|
|
2173 SELFTEST_BEGIN_STMT \
|
|
2174 assert_condition (SELFTEST_LOCATION, REGION_MODEL, LHS, OP, RHS, \
|
|
2175 tristate (tristate::TS_UNKNOWN)); \
|
|
2176 SELFTEST_END_STMT
|
|
2177
|
|
2178 } /* end of namespace selftest. */
|
|
2179
|
|
2180 #endif /* #if CHECKING_P */
|
|
2181
|
|
2182 } // namespace ana
|
|
2183
|
|
2184 #endif /* GCC_ANALYZER_REGION_MODEL_H */
|