Mercurial > hg > CbC > CbC_gcc
comparison gcc/analyzer/exploded-graph.h @ 145:1830386684a0
gcc-9.2.0
author | anatofuz |
---|---|
date | Thu, 13 Feb 2020 11:34:05 +0900 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
131:84e7813d76e9 | 145:1830386684a0 |
---|---|
1 /* Classes for managing a directed graph of <point, state> pairs. | |
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_EXPLODED_GRAPH_H | |
22 #define GCC_ANALYZER_EXPLODED_GRAPH_H | |
23 | |
24 namespace ana { | |
25 | |
26 /* Concrete implementation of region_model_context, wiring it up to the | |
27 rest of the analysis engine. */ | |
28 | |
29 class impl_region_model_context : public region_model_context | |
30 { | |
31 public: | |
32 impl_region_model_context (exploded_graph &eg, | |
33 const exploded_node *enode_for_diag, | |
34 | |
35 /* TODO: should we be getting the ECs from the | |
36 old state, rather than the new? */ | |
37 const program_state *old_state, | |
38 program_state *new_state, | |
39 state_change *change, | |
40 | |
41 const gimple *stmt, | |
42 stmt_finder *stmt_finder = NULL); | |
43 | |
44 impl_region_model_context (program_state *state, | |
45 state_change *change, | |
46 const extrinsic_state &ext_state); | |
47 | |
48 void warn (pending_diagnostic *d) FINAL OVERRIDE; | |
49 | |
50 void remap_svalue_ids (const svalue_id_map &map) FINAL OVERRIDE; | |
51 | |
52 int on_svalue_purge (svalue_id first_unused_sid, | |
53 const svalue_id_map &map) FINAL OVERRIDE; | |
54 | |
55 logger *get_logger () FINAL OVERRIDE | |
56 { | |
57 return m_logger.get_logger (); | |
58 } | |
59 | |
60 void on_state_leak (const state_machine &sm, | |
61 int sm_idx, | |
62 svalue_id sid, | |
63 svalue_id first_unused_sid, | |
64 const svalue_id_map &map, | |
65 state_machine::state_t state); | |
66 | |
67 void on_inherited_svalue (svalue_id parent_sid, | |
68 svalue_id child_sid) FINAL OVERRIDE; | |
69 | |
70 void on_cast (svalue_id src_sid, | |
71 svalue_id dst_sid) FINAL OVERRIDE; | |
72 | |
73 void on_condition (tree lhs, enum tree_code op, tree rhs) FINAL OVERRIDE; | |
74 | |
75 void on_unknown_change (svalue_id sid ATTRIBUTE_UNUSED) FINAL OVERRIDE; | |
76 | |
77 void on_phi (const gphi *phi, tree rhs) FINAL OVERRIDE; | |
78 | |
79 exploded_graph *m_eg; | |
80 log_user m_logger; | |
81 const exploded_node *m_enode_for_diag; | |
82 const program_state *m_old_state; | |
83 program_state *m_new_state; | |
84 state_change *m_change; | |
85 const gimple *m_stmt; | |
86 stmt_finder *m_stmt_finder; | |
87 const extrinsic_state &m_ext_state; | |
88 }; | |
89 | |
90 /* A <program_point, program_state> pair, used internally by | |
91 exploded_node as its immutable data, and as a key for identifying | |
92 exploded_nodes we've already seen in the graph. */ | |
93 | |
94 class point_and_state | |
95 { | |
96 public: | |
97 point_and_state (const program_point &point, | |
98 const program_state &state) | |
99 : m_point (point), | |
100 m_state (state), | |
101 m_hash (m_point.hash () ^ m_state.hash ()) | |
102 { | |
103 } | |
104 | |
105 hashval_t hash () const | |
106 { | |
107 return m_hash; | |
108 } | |
109 bool operator== (const point_and_state &other) const | |
110 { | |
111 return m_point == other.m_point && m_state == other.m_state; | |
112 } | |
113 | |
114 const program_point &get_point () const { return m_point; } | |
115 const program_state &get_state () const { return m_state; } | |
116 | |
117 void set_state (const program_state &state) | |
118 { | |
119 m_state = state; | |
120 m_hash = m_point.hash () ^ m_state.hash (); | |
121 } | |
122 | |
123 void validate (const extrinsic_state &ext_state) const; | |
124 | |
125 private: | |
126 program_point m_point; | |
127 program_state m_state; | |
128 hashval_t m_hash; | |
129 }; | |
130 | |
131 /* A traits class for exploded graphs and their nodes and edges. */ | |
132 | |
133 struct eg_traits | |
134 { | |
135 typedef exploded_node node_t; | |
136 typedef exploded_edge edge_t; | |
137 typedef exploded_graph graph_t; | |
138 struct dump_args_t | |
139 { | |
140 dump_args_t (const exploded_graph &eg) : m_eg (eg) {} | |
141 const exploded_graph &m_eg; | |
142 }; | |
143 typedef exploded_cluster cluster_t; | |
144 }; | |
145 | |
146 /* An exploded_node is a unique, immutable <point, state> pair within the | |
147 exploded_graph. | |
148 Each exploded_node has a unique index within the graph | |
149 (for ease of debugging). */ | |
150 | |
151 class exploded_node : public dnode<eg_traits> | |
152 { | |
153 public: | |
154 /* Has this enode had exploded_graph::process_node called on it? | |
155 This allows us to distinguish enodes that were merged during | |
156 worklist-handling, and thus never had process_node called on them | |
157 (in favor of processing the merged node). */ | |
158 enum status | |
159 { | |
160 /* Node is in the worklist. */ | |
161 STATUS_WORKLIST, | |
162 | |
163 /* Node has had exploded_graph::process_node called on it. */ | |
164 STATUS_PROCESSED, | |
165 | |
166 /* Node was left unprocessed due to merger; it won't have had | |
167 exploded_graph::process_node called on it. */ | |
168 STATUS_MERGER | |
169 }; | |
170 | |
171 exploded_node (point_and_state ps, | |
172 int index) | |
173 : m_ps (ps), m_status (STATUS_WORKLIST), m_index (index) | |
174 { | |
175 gcc_checking_assert (ps.get_state ().m_region_model->canonicalized_p ()); | |
176 } | |
177 | |
178 hashval_t hash () const { return m_ps.hash (); } | |
179 | |
180 void dump_dot (graphviz_out *gv, const dump_args_t &args) | |
181 const FINAL OVERRIDE; | |
182 void dump_dot_id (pretty_printer *pp) const; | |
183 | |
184 void dump_to_pp (pretty_printer *pp, const extrinsic_state &ext_state) const; | |
185 void dump (FILE *fp, const extrinsic_state &ext_state) const; | |
186 void dump (const extrinsic_state &ext_state) const; | |
187 | |
188 /* The result of on_stmt. */ | |
189 struct on_stmt_flags | |
190 { | |
191 on_stmt_flags (bool sm_changes) | |
192 : m_sm_changes (sm_changes), | |
193 m_terminate_path (false) | |
194 {} | |
195 | |
196 static on_stmt_flags terminate_path () | |
197 { | |
198 return on_stmt_flags (true, true); | |
199 } | |
200 | |
201 static on_stmt_flags state_change (bool any_sm_changes) | |
202 { | |
203 return on_stmt_flags (any_sm_changes, false); | |
204 } | |
205 | |
206 /* Did any sm-changes occur handling the stmt. */ | |
207 bool m_sm_changes : 1; | |
208 | |
209 /* Should we stop analyzing this path (on_stmt may have already | |
210 added nodes/edges, e.g. when handling longjmp). */ | |
211 bool m_terminate_path : 1; | |
212 | |
213 private: | |
214 on_stmt_flags (bool sm_changes, | |
215 bool terminate_path) | |
216 : m_sm_changes (sm_changes), | |
217 m_terminate_path (terminate_path) | |
218 {} | |
219 }; | |
220 | |
221 on_stmt_flags on_stmt (exploded_graph &eg, | |
222 const supernode *snode, | |
223 const gimple *stmt, | |
224 program_state *state, | |
225 state_change *change) const; | |
226 bool on_edge (exploded_graph &eg, | |
227 const superedge *succ, | |
228 program_point *next_point, | |
229 program_state *next_state, | |
230 state_change *change) const; | |
231 void on_longjmp (exploded_graph &eg, | |
232 const gcall *call, | |
233 program_state *new_state, | |
234 region_model_context *ctxt) const; | |
235 | |
236 void detect_leaks (exploded_graph &eg) const; | |
237 | |
238 const program_point &get_point () const { return m_ps.get_point (); } | |
239 const supernode *get_supernode () const | |
240 { | |
241 return get_point ().get_supernode (); | |
242 } | |
243 function *get_function () const | |
244 { | |
245 return get_point ().get_function (); | |
246 } | |
247 int get_stack_depth () const | |
248 { | |
249 return get_point ().get_stack_depth (); | |
250 } | |
251 const gimple *get_stmt () const { return get_point ().get_stmt (); } | |
252 | |
253 const program_state &get_state () const { return m_ps.get_state (); } | |
254 | |
255 const point_and_state *get_ps_key () const { return &m_ps; } | |
256 const program_point *get_point_key () const { return &m_ps.get_point (); } | |
257 | |
258 void dump_succs_and_preds (FILE *outf) const; | |
259 | |
260 enum status get_status () const { return m_status; } | |
261 void set_status (enum status status) | |
262 { | |
263 gcc_assert (m_status == STATUS_WORKLIST); | |
264 m_status = status; | |
265 } | |
266 | |
267 private: | |
268 DISABLE_COPY_AND_ASSIGN (exploded_node); | |
269 | |
270 const char * get_dot_fillcolor () const; | |
271 | |
272 /* The <program_point, program_state> pair. This is const, as it | |
273 is immutable once the exploded_node has been created. */ | |
274 const point_and_state m_ps; | |
275 | |
276 enum status m_status; | |
277 | |
278 public: | |
279 /* The index of this exploded_node. */ | |
280 const int m_index; | |
281 }; | |
282 | |
283 /* An edge within the exploded graph. | |
284 Some exploded_edges have an underlying superedge; others don't. */ | |
285 | |
286 class exploded_edge : public dedge<eg_traits> | |
287 { | |
288 public: | |
289 /* Abstract base class for associating custom data with an | |
290 exploded_edge, for handling non-standard edges such as | |
291 rewinding from a longjmp, signal handlers, etc. */ | |
292 class custom_info_t | |
293 { | |
294 public: | |
295 virtual ~custom_info_t () {} | |
296 | |
297 /* Hook for making .dot label more readable . */ | |
298 virtual void print (pretty_printer *pp) = 0; | |
299 | |
300 /* Hook for updating MODEL within exploded_path::feasible_p. */ | |
301 virtual void update_model (region_model *model, | |
302 const exploded_edge &eedge) = 0; | |
303 | |
304 virtual void add_events_to_path (checker_path *emission_path, | |
305 const exploded_edge &eedge) = 0; | |
306 }; | |
307 | |
308 exploded_edge (exploded_node *src, exploded_node *dest, | |
309 const extrinsic_state &ext_state, | |
310 const superedge *sedge, | |
311 const state_change &change, | |
312 custom_info_t *custom_info); | |
313 ~exploded_edge (); | |
314 void dump_dot (graphviz_out *gv, const dump_args_t &args) | |
315 const FINAL OVERRIDE; | |
316 | |
317 //private: | |
318 const superedge *const m_sedge; | |
319 | |
320 const state_change m_change; | |
321 | |
322 /* NULL for most edges; will be non-NULL for special cases | |
323 such as an unwind from a longjmp to a setjmp, or when | |
324 a signal is delivered to a signal-handler. | |
325 | |
326 Owned by this class. */ | |
327 custom_info_t *m_custom_info; | |
328 | |
329 private: | |
330 DISABLE_COPY_AND_ASSIGN (exploded_edge); | |
331 }; | |
332 | |
333 /* Extra data for an exploded_edge that represents a rewind from a | |
334 longjmp to a setjmp (or from a siglongjmp to a sigsetjmp). */ | |
335 | |
336 class rewind_info_t : public exploded_edge::custom_info_t | |
337 { | |
338 public: | |
339 rewind_info_t (const setjmp_record &setjmp_record, | |
340 const gcall *longjmp_call) | |
341 : m_setjmp_record (setjmp_record), | |
342 m_longjmp_call (longjmp_call) | |
343 {} | |
344 | |
345 void print (pretty_printer *pp) FINAL OVERRIDE | |
346 { | |
347 pp_string (pp, "rewind"); | |
348 } | |
349 | |
350 void update_model (region_model *model, | |
351 const exploded_edge &eedge) FINAL OVERRIDE; | |
352 | |
353 void add_events_to_path (checker_path *emission_path, | |
354 const exploded_edge &eedge) FINAL OVERRIDE; | |
355 | |
356 const program_point &get_setjmp_point () const | |
357 { | |
358 const program_point &origin_point = get_enode_origin ()->get_point (); | |
359 | |
360 /* "origin_point" ought to be before the call to "setjmp". */ | |
361 gcc_assert (origin_point.get_kind () == PK_BEFORE_STMT); | |
362 | |
363 /* TODO: assert that it's the final stmt in its supernode. */ | |
364 | |
365 return origin_point; | |
366 } | |
367 | |
368 const gcall *get_setjmp_call () const | |
369 { | |
370 return m_setjmp_record.m_setjmp_call; | |
371 } | |
372 | |
373 const gcall *get_longjmp_call () const | |
374 { | |
375 return m_longjmp_call; | |
376 } | |
377 | |
378 const exploded_node *get_enode_origin () const | |
379 { | |
380 return m_setjmp_record.m_enode; | |
381 } | |
382 | |
383 private: | |
384 setjmp_record m_setjmp_record; | |
385 const gcall *m_longjmp_call; | |
386 }; | |
387 | |
388 /* Statistics about aspects of an exploded_graph. */ | |
389 | |
390 struct stats | |
391 { | |
392 stats (int num_supernodes); | |
393 void log (logger *logger) const; | |
394 void dump (FILE *out) const; | |
395 | |
396 int m_num_nodes[NUM_POINT_KINDS]; | |
397 int m_node_reuse_count; | |
398 int m_node_reuse_after_merge_count; | |
399 int m_num_supernodes; | |
400 }; | |
401 | |
402 /* Traits class for ensuring uniqueness of point_and_state data within | |
403 an exploded_graph. */ | |
404 | |
405 struct eg_hash_map_traits | |
406 { | |
407 typedef const point_and_state *key_type; | |
408 typedef exploded_node *value_type; | |
409 typedef exploded_node *compare_type; | |
410 | |
411 static inline hashval_t hash (const key_type &k) | |
412 { | |
413 gcc_assert (k != NULL); | |
414 gcc_assert (k != reinterpret_cast<key_type> (1)); | |
415 return k->hash (); | |
416 } | |
417 static inline bool equal_keys (const key_type &k1, const key_type &k2) | |
418 { | |
419 gcc_assert (k1 != NULL); | |
420 gcc_assert (k2 != NULL); | |
421 gcc_assert (k1 != reinterpret_cast<key_type> (1)); | |
422 gcc_assert (k2 != reinterpret_cast<key_type> (1)); | |
423 if (k1 && k2) | |
424 return *k1 == *k2; | |
425 else | |
426 /* Otherwise they must both be non-NULL. */ | |
427 return k1 == k2; | |
428 } | |
429 template <typename T> | |
430 static inline void remove (T &) | |
431 { | |
432 /* empty; the nodes are handled elsewhere. */ | |
433 } | |
434 template <typename T> | |
435 static inline void mark_deleted (T &entry) | |
436 { | |
437 entry.m_key = reinterpret_cast<key_type> (1); | |
438 } | |
439 template <typename T> | |
440 static inline void mark_empty (T &entry) | |
441 { | |
442 entry.m_key = NULL; | |
443 } | |
444 template <typename T> | |
445 static inline bool is_deleted (const T &entry) | |
446 { | |
447 return entry.m_key == reinterpret_cast<key_type> (1); | |
448 } | |
449 template <typename T> | |
450 static inline bool is_empty (const T &entry) | |
451 { | |
452 return entry.m_key == NULL; | |
453 } | |
454 static const bool empty_zero_p = false; | |
455 }; | |
456 | |
457 /* Per-program_point data for an exploded_graph. */ | |
458 | |
459 struct per_program_point_data | |
460 { | |
461 per_program_point_data (const program_point &key) | |
462 : m_key (key) | |
463 {} | |
464 | |
465 const program_point m_key; | |
466 auto_vec<exploded_node *> m_enodes; | |
467 }; | |
468 | |
469 /* Traits class for storing per-program_point data within | |
470 an exploded_graph. */ | |
471 | |
472 struct eg_point_hash_map_traits | |
473 { | |
474 typedef const program_point *key_type; | |
475 typedef per_program_point_data *value_type; | |
476 typedef per_program_point_data *compare_type; | |
477 | |
478 static inline hashval_t hash (const key_type &k) | |
479 { | |
480 gcc_assert (k != NULL); | |
481 gcc_assert (k != reinterpret_cast<key_type> (1)); | |
482 return k->hash (); | |
483 } | |
484 static inline bool equal_keys (const key_type &k1, const key_type &k2) | |
485 { | |
486 gcc_assert (k1 != NULL); | |
487 gcc_assert (k2 != NULL); | |
488 gcc_assert (k1 != reinterpret_cast<key_type> (1)); | |
489 gcc_assert (k2 != reinterpret_cast<key_type> (1)); | |
490 if (k1 && k2) | |
491 return *k1 == *k2; | |
492 else | |
493 /* Otherwise they must both be non-NULL. */ | |
494 return k1 == k2; | |
495 } | |
496 template <typename T> | |
497 static inline void remove (T &) | |
498 { | |
499 /* empty; the nodes are handled elsewhere. */ | |
500 } | |
501 template <typename T> | |
502 static inline void mark_deleted (T &entry) | |
503 { | |
504 entry.m_key = reinterpret_cast<key_type> (1); | |
505 } | |
506 template <typename T> | |
507 static inline void mark_empty (T &entry) | |
508 { | |
509 entry.m_key = NULL; | |
510 } | |
511 template <typename T> | |
512 static inline bool is_deleted (const T &entry) | |
513 { | |
514 return entry.m_key == reinterpret_cast<key_type> (1); | |
515 } | |
516 template <typename T> | |
517 static inline bool is_empty (const T &entry) | |
518 { | |
519 return entry.m_key == NULL; | |
520 } | |
521 static const bool empty_zero_p = false; | |
522 }; | |
523 | |
524 /* Data about a particular call_string within an exploded_graph. */ | |
525 | |
526 struct per_call_string_data | |
527 { | |
528 per_call_string_data (const call_string &key, int num_supernodes) | |
529 : m_key (key), m_stats (num_supernodes) | |
530 {} | |
531 | |
532 const call_string m_key; | |
533 stats m_stats; | |
534 }; | |
535 | |
536 /* Traits class for storing per-call_string data within | |
537 an exploded_graph. */ | |
538 | |
539 struct eg_call_string_hash_map_traits | |
540 { | |
541 typedef const call_string *key_type; | |
542 typedef per_call_string_data *value_type; | |
543 typedef per_call_string_data *compare_type; | |
544 | |
545 static inline hashval_t hash (const key_type &k) | |
546 { | |
547 gcc_assert (k != NULL); | |
548 gcc_assert (k != reinterpret_cast<key_type> (1)); | |
549 return k->hash (); | |
550 } | |
551 static inline bool equal_keys (const key_type &k1, const key_type &k2) | |
552 { | |
553 gcc_assert (k1 != NULL); | |
554 gcc_assert (k2 != NULL); | |
555 gcc_assert (k1 != reinterpret_cast<key_type> (1)); | |
556 gcc_assert (k2 != reinterpret_cast<key_type> (1)); | |
557 if (k1 && k2) | |
558 return *k1 == *k2; | |
559 else | |
560 /* Otherwise they must both be non-NULL. */ | |
561 return k1 == k2; | |
562 } | |
563 template <typename T> | |
564 static inline void remove (T &) | |
565 { | |
566 /* empty; the nodes are handled elsewhere. */ | |
567 } | |
568 template <typename T> | |
569 static inline void mark_deleted (T &entry) | |
570 { | |
571 entry.m_key = reinterpret_cast<key_type> (1); | |
572 } | |
573 template <typename T> | |
574 static inline void mark_empty (T &entry) | |
575 { | |
576 entry.m_key = NULL; | |
577 } | |
578 template <typename T> | |
579 static inline bool is_deleted (const T &entry) | |
580 { | |
581 return entry.m_key == reinterpret_cast<key_type> (1); | |
582 } | |
583 template <typename T> | |
584 static inline bool is_empty (const T &entry) | |
585 { | |
586 return entry.m_key == NULL; | |
587 } | |
588 static const bool empty_zero_p = false; | |
589 }; | |
590 | |
591 /* Data about a particular function within an exploded_graph. */ | |
592 | |
593 struct per_function_data | |
594 { | |
595 per_function_data () {} | |
596 | |
597 void add_call_summary (exploded_node *node) | |
598 { | |
599 m_summaries.safe_push (node); | |
600 } | |
601 | |
602 auto_vec<exploded_node *> m_summaries; | |
603 }; | |
604 | |
605 | |
606 /* The strongly connected components of a supergraph. | |
607 In particular, this allows us to compute a partial ordering | |
608 of supernodes. */ | |
609 | |
610 class strongly_connected_components | |
611 { | |
612 public: | |
613 strongly_connected_components (const supergraph &sg, logger *logger); | |
614 | |
615 int get_scc_id (int node_index) const | |
616 { | |
617 return m_per_node[node_index].m_lowlink; | |
618 } | |
619 | |
620 void dump () const; | |
621 | |
622 private: | |
623 struct per_node_data | |
624 { | |
625 per_node_data () | |
626 : m_index (-1), m_lowlink (-1), m_on_stack (false) | |
627 {} | |
628 | |
629 int m_index; | |
630 int m_lowlink; | |
631 bool m_on_stack; | |
632 }; | |
633 | |
634 void strong_connect (unsigned index); | |
635 | |
636 const supergraph &m_sg; | |
637 auto_vec<unsigned> m_stack; | |
638 auto_vec<per_node_data> m_per_node; | |
639 }; | |
640 | |
641 /* The worklist of exploded_node instances that have been added to | |
642 an exploded_graph, but that haven't yet been processed to find | |
643 their successors (or warnings). | |
644 | |
645 The enodes are stored in a priority queue, ordered by a topological | |
646 sort of the SCCs in the supergraph, so that enodes for the same | |
647 program_point should appear at the front of the queue together. | |
648 This allows for state-merging at CFG join-points, so that | |
649 sufficiently-similar enodes can be merged into one. */ | |
650 | |
651 class worklist | |
652 { | |
653 public: | |
654 worklist (const exploded_graph &eg, const analysis_plan &plan); | |
655 unsigned length () const; | |
656 exploded_node *take_next (); | |
657 exploded_node *peek_next (); | |
658 void add_node (exploded_node *enode); | |
659 | |
660 private: | |
661 class key_t | |
662 { | |
663 public: | |
664 key_t (const worklist &w, exploded_node *enode) | |
665 : m_worklist (w), m_enode (enode) | |
666 {} | |
667 | |
668 bool operator< (const key_t &other) const | |
669 { | |
670 return cmp (*this, other) < 0; | |
671 } | |
672 | |
673 bool operator== (const key_t &other) const | |
674 { | |
675 return cmp (*this, other) == 0; | |
676 } | |
677 | |
678 bool operator> (const key_t &other) const | |
679 { | |
680 return !(*this == other || *this < other); | |
681 } | |
682 | |
683 private: | |
684 static int cmp (const key_t &ka, const key_t &kb); | |
685 | |
686 int get_scc_id (const exploded_node *enode) const | |
687 { | |
688 const supernode *snode = enode->get_supernode (); | |
689 if (snode == NULL) | |
690 return 0; | |
691 return m_worklist.m_scc.get_scc_id (snode->m_index); | |
692 } | |
693 | |
694 const worklist &m_worklist; | |
695 exploded_node *m_enode; | |
696 }; | |
697 | |
698 /* The order is important here: m_scc needs to stick around | |
699 until after m_queue has finished being cleaned up (the dtor | |
700 calls the ordering fns). */ | |
701 const exploded_graph &m_eg; | |
702 strongly_connected_components m_scc; | |
703 const analysis_plan &m_plan; | |
704 | |
705 /* Priority queue, backed by a fibonacci_heap. */ | |
706 typedef fibonacci_heap<key_t, exploded_node> queue_t; | |
707 queue_t m_queue; | |
708 }; | |
709 | |
710 /* An exploded_graph is a directed graph of unique <point, state> pairs. | |
711 It also has a worklist of nodes that are waiting for their successors | |
712 to be added to the graph. */ | |
713 | |
714 class exploded_graph : public digraph<eg_traits> | |
715 { | |
716 public: | |
717 typedef hash_map <const call_string *, per_call_string_data *, | |
718 eg_call_string_hash_map_traits> call_string_data_map_t; | |
719 | |
720 exploded_graph (const supergraph &sg, logger *logger, | |
721 const extrinsic_state &ext_state, | |
722 const state_purge_map *purge_map, | |
723 const analysis_plan &plan, | |
724 int verbosity); | |
725 ~exploded_graph (); | |
726 | |
727 logger *get_logger () const { return m_logger.get_logger (); } | |
728 | |
729 const supergraph &get_supergraph () const { return m_sg; } | |
730 const extrinsic_state &get_ext_state () const { return m_ext_state; } | |
731 const state_purge_map *get_purge_map () const { return m_purge_map; } | |
732 const analysis_plan &get_analysis_plan () const { return m_plan; } | |
733 | |
734 exploded_node *get_origin () const { return m_origin; } | |
735 | |
736 exploded_node *add_function_entry (function *fun); | |
737 | |
738 void build_initial_worklist (); | |
739 void process_worklist (); | |
740 void process_node (exploded_node *node); | |
741 | |
742 exploded_node *get_or_create_node (const program_point &point, | |
743 const program_state &state, | |
744 state_change *change); | |
745 exploded_edge *add_edge (exploded_node *src, exploded_node *dest, | |
746 const superedge *sedge, | |
747 const state_change &change, | |
748 exploded_edge::custom_info_t *custom = NULL); | |
749 | |
750 per_program_point_data * | |
751 get_or_create_per_program_point_data (const program_point &); | |
752 | |
753 per_call_string_data * | |
754 get_or_create_per_call_string_data (const call_string &); | |
755 | |
756 per_function_data * | |
757 get_or_create_per_function_data (function *); | |
758 per_function_data *get_per_function_data (function *) const; | |
759 | |
760 void save_diagnostic (const state_machine &sm, | |
761 const exploded_node *enode, | |
762 const supernode *node, const gimple *stmt, | |
763 stmt_finder *finder, | |
764 tree var, state_machine::state_t state, | |
765 pending_diagnostic *d); | |
766 | |
767 diagnostic_manager &get_diagnostic_manager () | |
768 { | |
769 return m_diagnostic_manager; | |
770 } | |
771 | |
772 stats *get_global_stats () { return &m_global_stats; } | |
773 stats *get_or_create_function_stats (function *fn); | |
774 void log_stats () const; | |
775 void dump_stats (FILE *) const; | |
776 void dump_states_for_supernode (FILE *, const supernode *snode) const; | |
777 void dump_exploded_nodes () const; | |
778 | |
779 const call_string_data_map_t *get_per_call_string_data () const | |
780 { return &m_per_call_string_data; } | |
781 | |
782 private: | |
783 DISABLE_COPY_AND_ASSIGN (exploded_graph); | |
784 | |
785 const supergraph &m_sg; | |
786 | |
787 log_user m_logger; | |
788 | |
789 /* Map from point/state to exploded node. | |
790 To avoid duplication we store point_and_state | |
791 *pointers* as keys, rather than point_and_state, using the | |
792 instance from within the exploded_node, with a custom hasher. */ | |
793 typedef hash_map <const point_and_state *, exploded_node *, | |
794 eg_hash_map_traits> map_t; | |
795 map_t m_point_and_state_to_node; | |
796 | |
797 /* Map from program_point to per-program_point data. */ | |
798 typedef hash_map <const program_point *, per_program_point_data *, | |
799 eg_point_hash_map_traits> point_map_t; | |
800 point_map_t m_per_point_data; | |
801 | |
802 worklist m_worklist; | |
803 | |
804 exploded_node *m_origin; | |
805 | |
806 const extrinsic_state &m_ext_state; | |
807 | |
808 const state_purge_map *const m_purge_map; | |
809 | |
810 const analysis_plan &m_plan; | |
811 | |
812 typedef hash_map<function *, per_function_data *> per_function_data_t; | |
813 per_function_data_t m_per_function_data; | |
814 | |
815 diagnostic_manager m_diagnostic_manager; | |
816 | |
817 /* Stats. */ | |
818 stats m_global_stats; | |
819 typedef ordered_hash_map<function *, stats *> function_stat_map_t; | |
820 function_stat_map_t m_per_function_stats; | |
821 stats m_functionless_stats; | |
822 | |
823 call_string_data_map_t m_per_call_string_data; | |
824 | |
825 auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode; | |
826 }; | |
827 | |
828 /* A path within an exploded_graph: a sequence of edges. */ | |
829 | |
830 class exploded_path | |
831 { | |
832 public: | |
833 exploded_path () : m_edges () {} | |
834 exploded_path (const exploded_path &other); | |
835 exploded_path & operator= (const exploded_path &other); | |
836 | |
837 unsigned length () const { return m_edges.length (); } | |
838 | |
839 bool find_stmt_backwards (const gimple *search_stmt, | |
840 int *out_idx) const; | |
841 | |
842 exploded_node *get_final_enode () const; | |
843 | |
844 void dump_to_pp (pretty_printer *pp) const; | |
845 void dump (FILE *fp) const; | |
846 void dump () const; | |
847 | |
848 bool feasible_p (logger *logger) const; | |
849 | |
850 auto_vec<const exploded_edge *> m_edges; | |
851 }; | |
852 | |
853 /* Finding the shortest exploded_path within an exploded_graph. */ | |
854 | |
855 typedef shortest_paths<eg_traits, exploded_path> shortest_exploded_paths; | |
856 | |
857 /* Abstract base class for use when passing NULL as the stmt for | |
858 a possible warning, allowing the choice of stmt to be deferred | |
859 until after we have an emission path (and know we're emitting a | |
860 warning). */ | |
861 | |
862 class stmt_finder | |
863 { | |
864 public: | |
865 virtual ~stmt_finder () {} | |
866 virtual stmt_finder *clone () const = 0; | |
867 virtual const gimple *find_stmt (const exploded_path &epath) = 0; | |
868 }; | |
869 | |
870 // TODO: split the above up? | |
871 | |
872 } // namespace ana | |
873 | |
874 #endif /* GCC_ANALYZER_EXPLODED_GRAPH_H */ |