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