1 | /* Classes for managing a directed graph of <point, state> pairs. |
2 | Copyright (C) 2019-2024 Free Software Foundation, Inc. |
3 | Contributed by David Malcolm <dmalcolm@redhat.com>. |
4 | |
5 | This file is part of GCC. |
6 | |
7 | GCC is free software; you can redistribute it and/or modify it |
8 | under the terms of the GNU General Public License as published by |
9 | the Free Software Foundation; either version 3, or (at your option) |
10 | any later version. |
11 | |
12 | GCC is distributed in the hope that it will be useful, but |
13 | WITHOUT ANY WARRANTY; without even the implied warranty of |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
15 | General Public License for more details. |
16 | |
17 | You should have received a copy of the GNU General Public License |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ |
20 | |
21 | #ifndef GCC_ANALYZER_EXPLODED_GRAPH_H |
22 | #define GCC_ANALYZER_EXPLODED_GRAPH_H |
23 | |
24 | #include "alloc-pool.h" |
25 | #include "fibonacci_heap.h" |
26 | #include "supergraph.h" |
27 | #include "sbitmap.h" |
28 | #include "shortest-paths.h" |
29 | #include "analyzer/sm.h" |
30 | #include "analyzer/program-state.h" |
31 | #include "analyzer/diagnostic-manager.h" |
32 | |
33 | namespace ana { |
34 | |
35 | /* Concrete implementation of region_model_context, wiring it up to the |
36 | rest of the analysis engine. */ |
37 | |
38 | class impl_region_model_context : public region_model_context |
39 | { |
40 | public: |
41 | impl_region_model_context (exploded_graph &eg, |
42 | exploded_node *enode_for_diag, |
43 | |
44 | /* TODO: should we be getting the ECs from the |
45 | old state, rather than the new? */ |
46 | const program_state *old_state, |
47 | program_state *new_state, |
48 | uncertainty_t *uncertainty, |
49 | path_context *path_ctxt, |
50 | |
51 | const gimple *stmt, |
52 | stmt_finder *stmt_finder = NULL, |
53 | |
54 | bool *out_could_have_done_work = nullptr); |
55 | |
56 | impl_region_model_context (program_state *state, |
57 | const extrinsic_state &ext_state, |
58 | uncertainty_t *uncertainty, |
59 | logger *logger = NULL); |
60 | |
61 | bool warn (std::unique_ptr<pending_diagnostic> d, |
62 | const stmt_finder *custom_finder = NULL) final override; |
63 | void add_note (std::unique_ptr<pending_note> pn) final override; |
64 | void add_event (std::unique_ptr<checker_event> event) final override; |
65 | void on_svalue_leak (const svalue *) override; |
66 | void on_liveness_change (const svalue_set &live_svalues, |
67 | const region_model *model) final override; |
68 | logger *get_logger () final override |
69 | { |
70 | return m_logger.get_logger (); |
71 | } |
72 | |
73 | void on_state_leak (const state_machine &sm, |
74 | const svalue *sval, |
75 | state_machine::state_t state); |
76 | |
77 | void on_condition (const svalue *lhs, |
78 | enum tree_code op, |
79 | const svalue *rhs) final override; |
80 | |
81 | void on_bounded_ranges (const svalue &sval, |
82 | const bounded_ranges &ranges) final override; |
83 | |
84 | void on_pop_frame (const frame_region *frame_reg) final override; |
85 | |
86 | void on_unknown_change (const svalue *sval, bool is_mutable) final override; |
87 | |
88 | void on_phi (const gphi *phi, tree rhs) final override; |
89 | |
90 | void on_unexpected_tree_code (tree t, |
91 | const dump_location_t &loc) final override; |
92 | |
93 | void on_escaped_function (tree fndecl) final override; |
94 | |
95 | uncertainty_t *get_uncertainty () final override; |
96 | |
97 | void purge_state_involving (const svalue *sval) final override; |
98 | |
99 | void bifurcate (std::unique_ptr<custom_edge_info> info) final override; |
100 | void terminate_path () final override; |
101 | const extrinsic_state *get_ext_state () const final override |
102 | { |
103 | return &m_ext_state; |
104 | } |
105 | bool |
106 | get_state_map_by_name (const char *name, |
107 | sm_state_map **out_smap, |
108 | const state_machine **out_sm, |
109 | unsigned *out_sm_idx, |
110 | std::unique_ptr<sm_context> *out_sm_context) override; |
111 | |
112 | const gimple *get_stmt () const override { return m_stmt; } |
113 | const exploded_graph *get_eg () const override { return m_eg; } |
114 | |
115 | void maybe_did_work () override; |
116 | bool checking_for_infinite_loop_p () const override { return false; } |
117 | void on_unusable_in_infinite_loop () override {} |
118 | |
119 | exploded_graph *m_eg; |
120 | log_user m_logger; |
121 | exploded_node *m_enode_for_diag; |
122 | const program_state *m_old_state; |
123 | program_state *m_new_state; |
124 | const gimple *m_stmt; |
125 | stmt_finder *m_stmt_finder; |
126 | const extrinsic_state &m_ext_state; |
127 | uncertainty_t *m_uncertainty; |
128 | path_context *m_path_ctxt; |
129 | bool *m_out_could_have_done_work; |
130 | }; |
131 | |
132 | /* A <program_point, program_state> pair, used internally by |
133 | exploded_node as its immutable data, and as a key for identifying |
134 | exploded_nodes we've already seen in the graph. */ |
135 | |
136 | class point_and_state |
137 | { |
138 | public: |
139 | point_and_state (const program_point &point, |
140 | const program_state &state) |
141 | : m_point (point), |
142 | m_state (state), |
143 | m_hash (m_point.hash () ^ m_state.hash ()) |
144 | { |
145 | /* We shouldn't be building point_and_states and thus exploded_nodes |
146 | for states that aren't valid. */ |
147 | gcc_assert (state.m_valid); |
148 | } |
149 | |
150 | hashval_t hash () const |
151 | { |
152 | return m_hash; |
153 | } |
154 | bool operator== (const point_and_state &other) const |
155 | { |
156 | return m_point == other.m_point && m_state == other.m_state; |
157 | } |
158 | |
159 | const program_point &get_point () const { return m_point; } |
160 | const program_state &get_state () const { return m_state; } |
161 | |
162 | void set_state (const program_state &state) |
163 | { |
164 | m_state = state; |
165 | m_hash = m_point.hash () ^ m_state.hash (); |
166 | } |
167 | |
168 | void validate (const extrinsic_state &ext_state) const; |
169 | |
170 | private: |
171 | program_point m_point; |
172 | program_state m_state; |
173 | hashval_t m_hash; |
174 | }; |
175 | |
176 | /* A traits class for exploded graphs and their nodes and edges. */ |
177 | |
178 | struct eg_traits |
179 | { |
180 | typedef exploded_node node_t; |
181 | typedef exploded_edge edge_t; |
182 | typedef exploded_graph graph_t; |
183 | struct dump_args_t |
184 | { |
185 | dump_args_t (const exploded_graph &eg) : m_eg (eg) {} |
186 | |
187 | bool show_enode_details_p (const exploded_node &enode) const; |
188 | |
189 | virtual void |
190 | (const exploded_node *, pretty_printer *) const {} |
191 | |
192 | const exploded_graph &m_eg; |
193 | }; |
194 | typedef exploded_cluster cluster_t; |
195 | }; |
196 | |
197 | /* An exploded_node is a unique, immutable <point, state> pair within the |
198 | exploded_graph. |
199 | Each exploded_node has a unique index within the graph |
200 | (for ease of debugging). */ |
201 | |
202 | class exploded_node : public dnode<eg_traits> |
203 | { |
204 | public: |
205 | /* Has this enode had exploded_graph::process_node called on it? |
206 | This allows us to distinguish enodes that were merged during |
207 | worklist-handling, and thus never had process_node called on them |
208 | (in favor of processing the merged node). */ |
209 | enum status |
210 | { |
211 | /* Node is in the worklist. */ |
212 | STATUS_WORKLIST, |
213 | |
214 | /* Node has had exploded_graph::process_node called on it. */ |
215 | STATUS_PROCESSED, |
216 | |
217 | /* Node was left unprocessed due to merger; it won't have had |
218 | exploded_graph::process_node called on it. */ |
219 | STATUS_MERGER, |
220 | |
221 | /* Node was processed by maybe_process_run_of_before_supernode_enodes. */ |
222 | STATUS_BULK_MERGED |
223 | }; |
224 | static const char * status_to_str (enum status s); |
225 | |
226 | exploded_node (const point_and_state &ps, int index); |
227 | |
228 | hashval_t hash () const { return m_ps.hash (); } |
229 | |
230 | const char * get_dot_fillcolor () const; |
231 | void dump_dot (graphviz_out *gv, const dump_args_t &args) |
232 | const final override; |
233 | void dump_dot_id (pretty_printer *pp) const; |
234 | |
235 | void dump_to_pp (pretty_printer *pp, const extrinsic_state &ext_state) const; |
236 | void dump (FILE *fp, const extrinsic_state &ext_state) const; |
237 | void dump (const extrinsic_state &ext_state) const; |
238 | |
239 | void dump_processed_stmts (pretty_printer *pp) const; |
240 | void dump_saved_diagnostics (pretty_printer *pp) const; |
241 | |
242 | json::object *to_json (const extrinsic_state &ext_state) const; |
243 | |
244 | /* The result of on_stmt. */ |
245 | struct on_stmt_flags |
246 | { |
247 | on_stmt_flags () : m_terminate_path (false) |
248 | {} |
249 | |
250 | static on_stmt_flags terminate_path () |
251 | { |
252 | return on_stmt_flags (true); |
253 | } |
254 | |
255 | /* Should we stop analyzing this path (on_stmt may have already |
256 | added nodes/edges, e.g. when handling longjmp). */ |
257 | bool m_terminate_path : 1; |
258 | |
259 | private: |
260 | on_stmt_flags (bool terminate_path) |
261 | : m_terminate_path (terminate_path) |
262 | {} |
263 | }; |
264 | |
265 | on_stmt_flags on_stmt (exploded_graph &eg, |
266 | const supernode *snode, |
267 | const gimple *stmt, |
268 | program_state *state, |
269 | uncertainty_t *uncertainty, |
270 | bool *out_could_have_done_work, |
271 | path_context *path_ctxt); |
272 | void on_stmt_pre (exploded_graph &eg, |
273 | const gimple *stmt, |
274 | program_state *state, |
275 | bool *out_terminate_path, |
276 | bool *out_unknown_side_effects, |
277 | region_model_context *ctxt); |
278 | void on_stmt_post (const gimple *stmt, |
279 | program_state *state, |
280 | bool unknown_side_effects, |
281 | region_model_context *ctxt); |
282 | |
283 | on_stmt_flags replay_call_summaries (exploded_graph &eg, |
284 | const supernode *snode, |
285 | const gcall *call_stmt, |
286 | program_state *state, |
287 | path_context *path_ctxt, |
288 | const function &called_fn, |
289 | per_function_data &called_fn_data, |
290 | region_model_context *ctxt); |
291 | void replay_call_summary (exploded_graph &eg, |
292 | const supernode *snode, |
293 | const gcall *call_stmt, |
294 | program_state *state, |
295 | path_context *path_ctxt, |
296 | const function &called_fn, |
297 | call_summary *summary, |
298 | region_model_context *ctxt); |
299 | |
300 | bool on_edge (exploded_graph &eg, |
301 | const superedge *succ, |
302 | program_point *next_point, |
303 | program_state *next_state, |
304 | uncertainty_t *uncertainty); |
305 | void on_longjmp (exploded_graph &eg, |
306 | const gcall *call, |
307 | program_state *new_state, |
308 | region_model_context *ctxt); |
309 | |
310 | void detect_leaks (exploded_graph &eg); |
311 | |
312 | const program_point &get_point () const { return m_ps.get_point (); } |
313 | const supernode *get_supernode () const |
314 | { |
315 | return get_point ().get_supernode (); |
316 | } |
317 | function *get_function () const |
318 | { |
319 | return get_point ().get_function (); |
320 | } |
321 | int get_stack_depth () const |
322 | { |
323 | return get_point ().get_stack_depth (); |
324 | } |
325 | const gimple *get_stmt () const { return get_point ().get_stmt (); } |
326 | const gimple *get_processed_stmt (unsigned idx) const; |
327 | |
328 | const program_state &get_state () const { return m_ps.get_state (); } |
329 | |
330 | const point_and_state *get_ps_key () const { return &m_ps; } |
331 | const program_point *get_point_key () const { return &m_ps.get_point (); } |
332 | |
333 | void dump_succs_and_preds (FILE *outf) const; |
334 | |
335 | enum status get_status () const { return m_status; } |
336 | void set_status (enum status status) |
337 | { |
338 | gcc_assert (m_status == STATUS_WORKLIST); |
339 | m_status = status; |
340 | } |
341 | |
342 | void add_diagnostic (const saved_diagnostic *sd) |
343 | { |
344 | m_saved_diagnostics.safe_push (obj: sd); |
345 | } |
346 | unsigned get_num_diagnostics () const |
347 | { |
348 | return m_saved_diagnostics.length (); |
349 | } |
350 | const saved_diagnostic *get_saved_diagnostic (unsigned idx) const |
351 | { |
352 | return m_saved_diagnostics[idx]; |
353 | } |
354 | |
355 | private: |
356 | DISABLE_COPY_AND_ASSIGN (exploded_node); |
357 | |
358 | /* The <program_point, program_state> pair. This is const, as it |
359 | is immutable once the exploded_node has been created. */ |
360 | const point_and_state m_ps; |
361 | |
362 | enum status m_status; |
363 | |
364 | /* The saved_diagnostics at this enode, borrowed from the |
365 | diagnostic_manager. */ |
366 | auto_vec <const saved_diagnostic *> m_saved_diagnostics; |
367 | |
368 | public: |
369 | /* The index of this exploded_node. */ |
370 | const int m_index; |
371 | |
372 | /* The number of stmts that were processed when process_node was |
373 | called on this enode. */ |
374 | unsigned m_num_processed_stmts; |
375 | }; |
376 | |
377 | /* An edge within the exploded graph. |
378 | Some exploded_edges have an underlying superedge; others don't. */ |
379 | |
380 | class exploded_edge : public dedge<eg_traits> |
381 | { |
382 | public: |
383 | exploded_edge (exploded_node *src, exploded_node *dest, |
384 | const superedge *sedge, bool could_do_work, |
385 | std::unique_ptr<custom_edge_info> custom_info); |
386 | void dump_dot (graphviz_out *gv, const dump_args_t &args) |
387 | const final override; |
388 | void dump_dot_label (pretty_printer *pp) const; |
389 | |
390 | json::object *to_json () const; |
391 | |
392 | //private: |
393 | const superedge *const m_sedge; |
394 | |
395 | /* NULL for most edges; will be non-NULL for special cases |
396 | such as an unwind from a longjmp to a setjmp, or when |
397 | a signal is delivered to a signal-handler. */ |
398 | std::unique_ptr<custom_edge_info> m_custom_info; |
399 | |
400 | bool could_do_work_p () const { return m_could_do_work_p; } |
401 | |
402 | private: |
403 | DISABLE_COPY_AND_ASSIGN (exploded_edge); |
404 | |
405 | /* For -Wanalyzer-infinite-loop. |
406 | Set to true during processing if any of the activity along |
407 | this edge is "externally-visible work" (and thus ruling this |
408 | out as being part of an infinite loop. |
409 | |
410 | For example, given: |
411 | |
412 | while (1) |
413 | do_something (); |
414 | |
415 | although it is an infinite loop, presumably the point of the |
416 | program is the loop body, and thus reporting this as an infinite |
417 | loop is likely to be unhelpful to the user. */ |
418 | bool m_could_do_work_p; |
419 | }; |
420 | |
421 | /* Extra data for an exploded_edge that represents dynamic call info ( calls |
422 | that doesn't have an underlying superedge representing the call ). */ |
423 | |
424 | class dynamic_call_info_t : public custom_edge_info |
425 | { |
426 | public: |
427 | dynamic_call_info_t (const gcall *dynamic_call, |
428 | const bool is_returning_call = false) |
429 | : m_dynamic_call (dynamic_call), |
430 | m_is_returning_call (is_returning_call) |
431 | {} |
432 | |
433 | void print (pretty_printer *pp) const final override |
434 | { |
435 | if (m_is_returning_call) |
436 | pp_string (pp, "dynamic_return" ); |
437 | else |
438 | pp_string (pp, "dynamic_call" ); |
439 | } |
440 | |
441 | bool update_model (region_model *model, |
442 | const exploded_edge *eedge, |
443 | region_model_context *ctxt) const final override; |
444 | |
445 | void add_events_to_path (checker_path *emission_path, |
446 | const exploded_edge &eedge) const final override; |
447 | private: |
448 | const gcall *m_dynamic_call; |
449 | const bool m_is_returning_call; |
450 | }; |
451 | |
452 | |
453 | /* Extra data for an exploded_edge that represents a rewind from a |
454 | longjmp to a setjmp (or from a siglongjmp to a sigsetjmp). */ |
455 | |
456 | class rewind_info_t : public custom_edge_info |
457 | { |
458 | public: |
459 | rewind_info_t (const setjmp_record &setjmp_record, |
460 | const gcall *longjmp_call) |
461 | : m_setjmp_record (setjmp_record), |
462 | m_longjmp_call (longjmp_call) |
463 | {} |
464 | |
465 | void print (pretty_printer *pp) const final override |
466 | { |
467 | pp_string (pp, "rewind" ); |
468 | } |
469 | |
470 | bool update_model (region_model *model, |
471 | const exploded_edge *eedge, |
472 | region_model_context *ctxt) const final override; |
473 | |
474 | void add_events_to_path (checker_path *emission_path, |
475 | const exploded_edge &eedge) const final override; |
476 | |
477 | const program_point &get_setjmp_point () const |
478 | { |
479 | const program_point &origin_point = get_enode_origin ()->get_point (); |
480 | |
481 | /* "origin_point" ought to be before the call to "setjmp". */ |
482 | gcc_assert (origin_point.get_kind () == PK_BEFORE_STMT); |
483 | |
484 | /* TODO: assert that it's the final stmt in its supernode. */ |
485 | |
486 | return origin_point; |
487 | } |
488 | |
489 | const gcall *get_setjmp_call () const |
490 | { |
491 | return m_setjmp_record.m_setjmp_call; |
492 | } |
493 | |
494 | const gcall *get_longjmp_call () const |
495 | { |
496 | return m_longjmp_call; |
497 | } |
498 | |
499 | const exploded_node *get_enode_origin () const |
500 | { |
501 | return m_setjmp_record.m_enode; |
502 | } |
503 | |
504 | private: |
505 | setjmp_record m_setjmp_record; |
506 | const gcall *m_longjmp_call; |
507 | }; |
508 | |
509 | /* Statistics about aspects of an exploded_graph. */ |
510 | |
511 | struct stats |
512 | { |
513 | stats (int num_supernodes); |
514 | void log (logger *logger) const; |
515 | void dump (FILE *out) const; |
516 | |
517 | int get_total_enodes () const; |
518 | |
519 | int m_num_nodes[NUM_POINT_KINDS]; |
520 | int m_node_reuse_count; |
521 | int m_node_reuse_after_merge_count; |
522 | int m_num_supernodes; |
523 | }; |
524 | |
525 | /* Traits class for ensuring uniqueness of point_and_state data within |
526 | an exploded_graph. */ |
527 | |
528 | struct eg_hash_map_traits |
529 | { |
530 | typedef const point_and_state *key_type; |
531 | typedef exploded_node *value_type; |
532 | typedef exploded_node *compare_type; |
533 | |
534 | static inline hashval_t hash (const key_type &k) |
535 | { |
536 | gcc_assert (k != NULL); |
537 | gcc_assert (k != reinterpret_cast<key_type> (1)); |
538 | return k->hash (); |
539 | } |
540 | static inline bool equal_keys (const key_type &k1, const key_type &k2) |
541 | { |
542 | gcc_assert (k1 != NULL); |
543 | gcc_assert (k2 != NULL); |
544 | gcc_assert (k1 != reinterpret_cast<key_type> (1)); |
545 | gcc_assert (k2 != reinterpret_cast<key_type> (1)); |
546 | if (k1 && k2) |
547 | return *k1 == *k2; |
548 | else |
549 | /* Otherwise they must both be non-NULL. */ |
550 | return k1 == k2; |
551 | } |
552 | template <typename T> |
553 | static inline void remove (T &) |
554 | { |
555 | /* empty; the nodes are handled elsewhere. */ |
556 | } |
557 | template <typename T> |
558 | static inline void mark_deleted (T &entry) |
559 | { |
560 | entry.m_key = reinterpret_cast<key_type> (1); |
561 | } |
562 | template <typename T> |
563 | static inline void mark_empty (T &entry) |
564 | { |
565 | entry.m_key = NULL; |
566 | } |
567 | template <typename T> |
568 | static inline bool is_deleted (const T &entry) |
569 | { |
570 | return entry.m_key == reinterpret_cast<key_type> (1); |
571 | } |
572 | template <typename T> |
573 | static inline bool is_empty (const T &entry) |
574 | { |
575 | return entry.m_key == NULL; |
576 | } |
577 | static const bool empty_zero_p = false; |
578 | }; |
579 | |
580 | /* Per-program_point data for an exploded_graph. */ |
581 | |
582 | struct per_program_point_data |
583 | { |
584 | per_program_point_data (const program_point &key) |
585 | : m_key (key), m_excess_enodes (0) |
586 | {} |
587 | |
588 | const program_point m_key; |
589 | auto_vec<exploded_node *> m_enodes; |
590 | /* The number of attempts to create an enode for this point |
591 | after exceeding --param=analyzer-max-enodes-per-program-point. */ |
592 | int m_excess_enodes; |
593 | }; |
594 | |
595 | /* Traits class for storing per-program_point data within |
596 | an exploded_graph. */ |
597 | |
598 | struct eg_point_hash_map_traits |
599 | { |
600 | typedef const program_point *key_type; |
601 | typedef per_program_point_data *value_type; |
602 | typedef per_program_point_data *compare_type; |
603 | |
604 | static inline hashval_t hash (const key_type &k) |
605 | { |
606 | gcc_assert (k != NULL); |
607 | gcc_assert (k != reinterpret_cast<key_type> (1)); |
608 | return k->hash (); |
609 | } |
610 | static inline bool equal_keys (const key_type &k1, const key_type &k2) |
611 | { |
612 | gcc_assert (k1 != NULL); |
613 | gcc_assert (k2 != NULL); |
614 | gcc_assert (k1 != reinterpret_cast<key_type> (1)); |
615 | gcc_assert (k2 != reinterpret_cast<key_type> (1)); |
616 | if (k1 && k2) |
617 | return *k1 == *k2; |
618 | else |
619 | /* Otherwise they must both be non-NULL. */ |
620 | return k1 == k2; |
621 | } |
622 | template <typename T> |
623 | static inline void remove (T &) |
624 | { |
625 | /* empty; the nodes are handled elsewhere. */ |
626 | } |
627 | template <typename T> |
628 | static inline void mark_deleted (T &entry) |
629 | { |
630 | entry.m_key = reinterpret_cast<key_type> (1); |
631 | } |
632 | template <typename T> |
633 | static inline void mark_empty (T &entry) |
634 | { |
635 | entry.m_key = NULL; |
636 | } |
637 | template <typename T> |
638 | static inline bool is_deleted (const T &entry) |
639 | { |
640 | return entry.m_key == reinterpret_cast<key_type> (1); |
641 | } |
642 | template <typename T> |
643 | static inline bool is_empty (const T &entry) |
644 | { |
645 | return entry.m_key == NULL; |
646 | } |
647 | static const bool empty_zero_p = false; |
648 | }; |
649 | |
650 | /* Data about a particular call_string within an exploded_graph. */ |
651 | |
652 | struct per_call_string_data |
653 | { |
654 | per_call_string_data (const call_string &key, int num_supernodes) |
655 | : m_key (key), m_stats (num_supernodes) |
656 | {} |
657 | |
658 | const call_string &m_key; |
659 | stats m_stats; |
660 | }; |
661 | |
662 | /* Data about a particular function within an exploded_graph. */ |
663 | |
664 | struct per_function_data |
665 | { |
666 | per_function_data () {} |
667 | ~per_function_data (); |
668 | |
669 | void add_call_summary (exploded_node *node); |
670 | |
671 | auto_vec<call_summary *> m_summaries; |
672 | }; |
673 | |
674 | |
675 | /* The strongly connected components of a supergraph. |
676 | In particular, this allows us to compute a partial ordering |
677 | of supernodes. */ |
678 | |
679 | class strongly_connected_components |
680 | { |
681 | public: |
682 | strongly_connected_components (const supergraph &sg, logger *logger); |
683 | |
684 | int get_scc_id (int node_index) const |
685 | { |
686 | return m_per_node[node_index].m_lowlink; |
687 | } |
688 | |
689 | void dump () const; |
690 | |
691 | json::array *to_json () const; |
692 | |
693 | private: |
694 | struct per_node_data |
695 | { |
696 | per_node_data () |
697 | : m_index (-1), m_lowlink (-1), m_on_stack (false) |
698 | {} |
699 | |
700 | int m_index; |
701 | int m_lowlink; |
702 | bool m_on_stack; |
703 | }; |
704 | |
705 | void strong_connect (unsigned index); |
706 | |
707 | const supergraph &m_sg; |
708 | auto_vec<unsigned> m_stack; |
709 | auto_vec<per_node_data> m_per_node; |
710 | }; |
711 | |
712 | /* The worklist of exploded_node instances that have been added to |
713 | an exploded_graph, but that haven't yet been processed to find |
714 | their successors (or warnings). |
715 | |
716 | The enodes are stored in a priority queue, ordered by a topological |
717 | sort of the SCCs in the supergraph, so that enodes for the same |
718 | program_point should appear at the front of the queue together. |
719 | This allows for state-merging at CFG join-points, so that |
720 | sufficiently-similar enodes can be merged into one. */ |
721 | |
722 | class worklist |
723 | { |
724 | public: |
725 | worklist (const exploded_graph &eg, const analysis_plan &plan); |
726 | unsigned length () const; |
727 | exploded_node *take_next (); |
728 | exploded_node *peek_next (); |
729 | void add_node (exploded_node *enode); |
730 | int get_scc_id (const supernode &snode) const |
731 | { |
732 | return m_scc.get_scc_id (node_index: snode.m_index); |
733 | } |
734 | |
735 | json::object *to_json () const; |
736 | |
737 | private: |
738 | class key_t |
739 | { |
740 | public: |
741 | key_t (const worklist &w, exploded_node *enode) |
742 | : m_worklist (w), m_enode (enode) |
743 | {} |
744 | |
745 | bool operator< (const key_t &other) const |
746 | { |
747 | return cmp (ka: *this, kb: other) < 0; |
748 | } |
749 | |
750 | bool operator== (const key_t &other) const |
751 | { |
752 | return cmp (ka: *this, kb: other) == 0; |
753 | } |
754 | |
755 | bool operator> (const key_t &other) const |
756 | { |
757 | return !(*this == other || *this < other); |
758 | } |
759 | |
760 | private: |
761 | static int cmp (const key_t &ka, const key_t &kb); |
762 | |
763 | int get_scc_id (const exploded_node *enode) const |
764 | { |
765 | const supernode *snode = enode->get_supernode (); |
766 | if (snode == NULL) |
767 | return 0; |
768 | return m_worklist.m_scc.get_scc_id (node_index: snode->m_index); |
769 | } |
770 | |
771 | const worklist &m_worklist; |
772 | exploded_node *m_enode; |
773 | }; |
774 | |
775 | /* The order is important here: m_scc needs to stick around |
776 | until after m_queue has finished being cleaned up (the dtor |
777 | calls the ordering fns). */ |
778 | strongly_connected_components m_scc; |
779 | const analysis_plan &m_plan; |
780 | |
781 | /* Priority queue, backed by a fibonacci_heap. */ |
782 | typedef fibonacci_heap<key_t, exploded_node> queue_t; |
783 | queue_t m_queue; |
784 | }; |
785 | |
786 | /* An exploded_graph is a directed graph of unique <point, state> pairs. |
787 | It also has a worklist of nodes that are waiting for their successors |
788 | to be added to the graph. */ |
789 | |
790 | class exploded_graph : public digraph<eg_traits> |
791 | { |
792 | public: |
793 | typedef hash_map <const call_string *, |
794 | per_call_string_data *> call_string_data_map_t; |
795 | |
796 | exploded_graph (const supergraph &sg, logger *logger, |
797 | const extrinsic_state &ext_state, |
798 | const state_purge_map *purge_map, |
799 | const analysis_plan &plan, |
800 | int verbosity); |
801 | ~exploded_graph (); |
802 | |
803 | logger *get_logger () const { return m_logger.get_logger (); } |
804 | |
805 | const supergraph &get_supergraph () const { return m_sg; } |
806 | const extrinsic_state &get_ext_state () const { return m_ext_state; } |
807 | engine *get_engine () const { return m_ext_state.get_engine (); } |
808 | const state_purge_map *get_purge_map () const { return m_purge_map; } |
809 | const analysis_plan &get_analysis_plan () const { return m_plan; } |
810 | |
811 | exploded_node *get_origin () const { return m_origin; } |
812 | |
813 | exploded_node *add_function_entry (const function &fun); |
814 | |
815 | void build_initial_worklist (); |
816 | void process_worklist (); |
817 | bool maybe_process_run_of_before_supernode_enodes (exploded_node *node); |
818 | void process_node (exploded_node *node); |
819 | |
820 | bool maybe_create_dynamic_call (const gcall *call, |
821 | tree fn_decl, |
822 | exploded_node *node, |
823 | program_state next_state, |
824 | program_point &next_point, |
825 | uncertainty_t *uncertainty, |
826 | logger *logger); |
827 | |
828 | exploded_node *get_or_create_node (const program_point &point, |
829 | const program_state &state, |
830 | exploded_node *enode_for_diag); |
831 | exploded_edge *add_edge (exploded_node *src, exploded_node *dest, |
832 | const superedge *sedge, bool could_do_work, |
833 | std::unique_ptr<custom_edge_info> custom = NULL); |
834 | |
835 | per_program_point_data * |
836 | get_or_create_per_program_point_data (const program_point &); |
837 | per_program_point_data * |
838 | get_per_program_point_data (const program_point &) const; |
839 | |
840 | per_call_string_data * |
841 | get_or_create_per_call_string_data (const call_string &); |
842 | |
843 | per_function_data * |
844 | get_or_create_per_function_data (function *); |
845 | per_function_data *get_per_function_data (function *) const; |
846 | |
847 | void save_diagnostic (const state_machine &sm, |
848 | const exploded_node *enode, |
849 | const supernode *node, const gimple *stmt, |
850 | stmt_finder *finder, |
851 | tree var, state_machine::state_t state, |
852 | pending_diagnostic *d); |
853 | |
854 | diagnostic_manager &get_diagnostic_manager () |
855 | { |
856 | return m_diagnostic_manager; |
857 | } |
858 | const diagnostic_manager &get_diagnostic_manager () const |
859 | { |
860 | return m_diagnostic_manager; |
861 | } |
862 | |
863 | stats *get_global_stats () { return &m_global_stats; } |
864 | stats *get_or_create_function_stats (function *fn); |
865 | void log_stats () const; |
866 | void dump_stats (FILE *) const; |
867 | void dump_states_for_supernode (FILE *, const supernode *snode) const; |
868 | void dump_exploded_nodes () const; |
869 | |
870 | json::object *to_json () const; |
871 | |
872 | exploded_node *get_node_by_index (int idx) const; |
873 | |
874 | const call_string_data_map_t *get_per_call_string_data () const |
875 | { return &m_per_call_string_data; } |
876 | |
877 | int get_scc_id (const supernode &node) const |
878 | { |
879 | return m_worklist.get_scc_id (snode: node); |
880 | } |
881 | |
882 | void on_escaped_function (tree fndecl); |
883 | |
884 | /* In infinite-loop.cc */ |
885 | void detect_infinite_loops (); |
886 | |
887 | /* In infinite-recursion.cc */ |
888 | void detect_infinite_recursion (exploded_node *enode); |
889 | exploded_node *find_previous_entry_to (function *top_of_stack_fun, |
890 | exploded_node *enode) const; |
891 | |
892 | private: |
893 | void print_bar_charts (pretty_printer *pp) const; |
894 | |
895 | DISABLE_COPY_AND_ASSIGN (exploded_graph); |
896 | |
897 | const supergraph &m_sg; |
898 | |
899 | log_user m_logger; |
900 | |
901 | /* Map from point/state to exploded node. |
902 | To avoid duplication we store point_and_state |
903 | *pointers* as keys, rather than point_and_state, using the |
904 | instance from within the exploded_node, with a custom hasher. */ |
905 | typedef hash_map <const point_and_state *, exploded_node *, |
906 | eg_hash_map_traits> map_t; |
907 | map_t m_point_and_state_to_node; |
908 | |
909 | /* Map from program_point to per-program_point data. */ |
910 | typedef hash_map <const program_point *, per_program_point_data *, |
911 | eg_point_hash_map_traits> point_map_t; |
912 | point_map_t m_per_point_data; |
913 | |
914 | worklist m_worklist; |
915 | |
916 | exploded_node *m_origin; |
917 | |
918 | const extrinsic_state &m_ext_state; |
919 | |
920 | const state_purge_map *const m_purge_map; |
921 | |
922 | const analysis_plan &m_plan; |
923 | |
924 | typedef hash_map<function *, per_function_data *> per_function_data_t; |
925 | per_function_data_t m_per_function_data; |
926 | |
927 | diagnostic_manager m_diagnostic_manager; |
928 | |
929 | /* Stats. */ |
930 | stats m_global_stats; |
931 | typedef ordered_hash_map<function *, stats *> function_stat_map_t; |
932 | function_stat_map_t m_per_function_stats; |
933 | stats m_functionless_stats; |
934 | |
935 | call_string_data_map_t m_per_call_string_data; |
936 | |
937 | auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode; |
938 | |
939 | /* Functions with a top-level enode, to make add_function_entry |
940 | be idempotent, for use in handling callbacks. */ |
941 | hash_set<function *> m_functions_with_enodes; |
942 | }; |
943 | |
944 | /* A path within an exploded_graph: a sequence of edges. */ |
945 | |
946 | class exploded_path |
947 | { |
948 | public: |
949 | exploded_path () : m_edges () {} |
950 | exploded_path (const exploded_path &other); |
951 | |
952 | unsigned length () const { return m_edges.length (); } |
953 | |
954 | bool find_stmt_backwards (const gimple *search_stmt, |
955 | int *out_idx) const; |
956 | |
957 | exploded_node *get_final_enode () const; |
958 | |
959 | void dump_to_pp (pretty_printer *pp, |
960 | const extrinsic_state *ext_state) const; |
961 | void dump (FILE *fp, const extrinsic_state *ext_state) const; |
962 | void dump (const extrinsic_state *ext_state = NULL) const; |
963 | void dump_to_file (const char *filename, |
964 | const extrinsic_state &ext_state) const; |
965 | |
966 | bool feasible_p (logger *logger, std::unique_ptr<feasibility_problem> *out, |
967 | engine *eng, const exploded_graph *eg) const; |
968 | |
969 | auto_vec<const exploded_edge *> m_edges; |
970 | }; |
971 | |
972 | /* A reason why a particular exploded_path is infeasible. */ |
973 | |
974 | class feasibility_problem |
975 | { |
976 | public: |
977 | feasibility_problem (unsigned eedge_idx, |
978 | const exploded_edge &eedge, |
979 | const gimple *last_stmt, |
980 | std::unique_ptr<rejected_constraint> rc) |
981 | : m_eedge_idx (eedge_idx), m_eedge (eedge), |
982 | m_last_stmt (last_stmt), m_rc (std::move (rc)) |
983 | {} |
984 | |
985 | void dump_to_pp (pretty_printer *pp) const; |
986 | |
987 | unsigned m_eedge_idx; |
988 | const exploded_edge &m_eedge; |
989 | const gimple *m_last_stmt; |
990 | std::unique_ptr<rejected_constraint> m_rc; |
991 | }; |
992 | |
993 | /* A class for capturing the state of a node when checking a path |
994 | through the exploded_graph for feasibility. */ |
995 | |
996 | class feasibility_state |
997 | { |
998 | public: |
999 | feasibility_state (region_model_manager *manager, |
1000 | const supergraph &sg); |
1001 | feasibility_state (const region_model &model, |
1002 | const supergraph &sg); |
1003 | feasibility_state (const feasibility_state &other); |
1004 | |
1005 | feasibility_state &operator= (const feasibility_state &other); |
1006 | |
1007 | bool maybe_update_for_edge (logger *logger, |
1008 | const exploded_edge *eedge, |
1009 | region_model_context *ctxt, |
1010 | std::unique_ptr<rejected_constraint> *out_rc); |
1011 | void update_for_stmt (const gimple *stmt); |
1012 | |
1013 | const region_model &get_model () const { return m_model; } |
1014 | const auto_sbitmap &get_snodes_visited () const { return m_snodes_visited; } |
1015 | |
1016 | void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const; |
1017 | |
1018 | private: |
1019 | region_model m_model; |
1020 | auto_sbitmap m_snodes_visited; |
1021 | }; |
1022 | |
1023 | /* Finding the shortest exploded_path within an exploded_graph. */ |
1024 | |
1025 | typedef shortest_paths<eg_traits, exploded_path> shortest_exploded_paths; |
1026 | |
1027 | /* Abstract base class for use when passing NULL as the stmt for |
1028 | a possible warning, allowing the choice of stmt to be deferred |
1029 | until after we have an emission path (and know we're emitting a |
1030 | warning). */ |
1031 | |
1032 | class stmt_finder |
1033 | { |
1034 | public: |
1035 | virtual ~stmt_finder () {} |
1036 | virtual std::unique_ptr<stmt_finder> clone () const = 0; |
1037 | virtual const gimple *find_stmt (const exploded_path &epath) = 0; |
1038 | }; |
1039 | |
1040 | // TODO: split the above up? |
1041 | |
1042 | } // namespace ana |
1043 | |
1044 | #endif /* GCC_ANALYZER_EXPLODED_GRAPH_H */ |
1045 | |