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