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