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