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-2026 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"
33
34namespace ana {
35
36/* Concrete implementation of region_model_context, wiring it up to the
37 rest of the analysis engine. */
38
40{
41 public:
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
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;
66 logger *get_logger () final override
67 {
68 return m_logger.get_logger ();
69 }
70
72 const svalue *sval,
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
85 bool is_mutable) final override;
86
87 void on_phi (const gphi *phi, tree rhs) final override;
88
90 const dump_location_t &loc) final override;
91
92 void on_escaped_function (tree fndecl) final override;
93
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 const extrinsic_state *get_ext_state () const final override
101 {
102 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 const gimple *get_stmt () const override { return m_stmt; }
112 const exploded_graph *get_eg () const override { return m_eg; }
113
114 const program_state *get_state () const override { return m_new_state; }
115
116 void maybe_did_work () override;
117 bool checking_for_infinite_loop_p () const override { return false; }
119
122
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
140{
141public:
143 const program_state &state)
144 : m_point (point),
145 m_state (state),
146 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 gcc_assert (state.m_valid);
151 }
152
153 point_and_state (const point_and_state &other) = default;
154
157 m_state (std::move (other.m_state)),
159 {
160 }
161
162 hashval_t hash () const
163 {
164 return m_hash;
165 }
166 bool operator== (const point_and_state &other) const
167 {
168 return m_point == other.m_point && m_state == other.m_state;
169 }
170
171 const program_point &get_point () const { return m_point; }
172 const program_state &get_state () const { return m_state; }
173
175 {
176 m_state = state;
177 m_hash = m_point.hash () ^ m_state.hash ();
178 }
179
181 {
182 m_state = std::move (state);
183 m_hash = m_point.hash () ^ m_state.hash ();
184 }
185
186 void validate (const extrinsic_state &ext_state) const;
187
188private:
191 hashval_t m_hash;
192};
193
194/* A traits class for exploded graphs and their nodes and edges. */
195
197{
202 {
203 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
209
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
220class 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. */
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);
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>
260
261 void dump () const;
263 void dump_to_logger (logger &log) const;
264
267
268 std::unique_ptr<json::object> to_json (const extrinsic_state &ext_state) const;
269
271 const gcall &call,
272 program_state *new_state,
275 const gcall &call,
276 const program_point &after_throw_point,
277 program_state *new_state,
278 bool is_rethrow,
280
282
283 const program_point &get_point () const { return m_ps.get_point (); }
284 const supernode *get_supernode () const
285 {
286 return get_point ().get_supernode ();
287 }
288 location_t get_location () const
289 {
290 return get_point ().get_location ();
291 }
293 {
294 return get_point ().get_function ();
295 }
296 int get_stack_depth () const
297 {
298 return get_point ().get_stack_depth ();
299 }
300
301 const program_state &get_state () const { return m_ps.get_state (); }
302
303 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 enum status get_status () const { return m_status; }
309 void set_status (enum status s)
310 {
312 m_status = s;
313 }
314
316 {
317 m_saved_diagnostics.safe_push (sd);
318 }
319 unsigned get_num_diagnostics () const
320 {
321 return m_saved_diagnostics.length ();
322 }
323 const saved_diagnostic *get_saved_diagnostic (unsigned idx) const
324 {
325 return m_saved_diagnostics[idx];
326 }
327
328private:
330
331 /* The <program_point, program_state> pair. This is const, as it
332 is immutable once the exploded_node has been created. */
334
336
337 /* The saved_diagnostics at this enode, borrowed from the
338 diagnostic_manager. */
339 auto_vec <const saved_diagnostic *> m_saved_diagnostics;
340
341public:
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
349class exploded_edge : public dedge<eg_traits>
350{
351 public:
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;
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 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
374private:
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. */
391};
392
393/* Extra data for an exploded_edge that represents an interprocedural
394 call. */
395
397{
398public:
400 function &callee_fun)
401 : m_op (op),
402 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
411 const exploded_edge *eedge,
412 region_model_context *ctxt) const final override;
413
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,
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
428private:
431};
432
433/* Extra data for an exploded_edge that represents an interprocedural
434 return. */
435
437{
438public:
439 interprocedural_return (const gcall &call_stmt)
440 : 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
449 const exploded_edge *eedge,
450 region_model_context *ctxt) const final override;
451
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,
459 const state_transition *state_trans) const final override;
460
461 bool
462 try_to_rewind_data_flow (rewind_context &) const final override;
463
464private:
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,
492 const state_transition *state_trans) const final override;
493
496 {
497 return get_enode_origin ()->get_point ();
498 }
499
502 {
503 const program_point &origin_point = get_enode_origin ()->get_point ();
505 origin_point.get_call_string ());
506 }
507
508 const gcall &get_setjmp_call () const
509 {
511 }
512
513 const gcall &get_longjmp_call () const
514 {
515 return m_longjmp_call;
516 }
517
519 {
521 }
522
523private:
526};
527
528/* Statistics about aspects of an exploded_graph. */
529
530struct 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
542};
543
544/* Traits class for ensuring uniqueness of point_and_state data within
545 an exploded_graph. */
546
548{
549 typedef const point_and_state *key_type;
552
553 static inline hashval_t hash (const key_type &k)
554 {
555 gcc_assert (k != nullptr);
556 gcc_assert (k != reinterpret_cast<key_type> (1));
557 return k->hash ();
558 }
559 static inline bool equal_keys (const key_type &k1, const key_type &k2)
560 {
561 gcc_assert (k1 != nullptr);
562 gcc_assert (k2 != nullptr);
563 gcc_assert (k1 != reinterpret_cast<key_type> (1));
564 gcc_assert (k2 != reinterpret_cast<key_type> (1));
565 if (k1 && k2)
566 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 static inline void mark_empty (T &entry)
583 {
584 entry.m_key = nullptr;
585 }
586 template <typename T>
587 static inline bool is_deleted (const T &entry)
588 {
589 return entry.m_key == reinterpret_cast<key_type> (1);
590 }
591 template <typename T>
592 static inline bool is_empty (const T &entry)
593 {
594 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
602{
604 : m_key (key), m_excess_enodes (0)
605 {}
606
609 /* The number of attempts to create an enode for this point
610 after exceeding --param=analyzer-max-enodes-per-program-point. */
612};
613
614/* Traits class for storing per-program_point data within
615 an exploded_graph. */
616
618{
619 typedef const program_point *key_type;
622
623 static inline hashval_t hash (const key_type &k)
624 {
625 gcc_assert (k != nullptr);
626 gcc_assert (k != reinterpret_cast<key_type> (1));
627 return k->hash ();
628 }
629 static inline bool equal_keys (const key_type &k1, const key_type &k2)
630 {
631 gcc_assert (k1 != nullptr);
632 gcc_assert (k2 != nullptr);
633 gcc_assert (k1 != reinterpret_cast<key_type> (1));
634 gcc_assert (k2 != reinterpret_cast<key_type> (1));
635 if (k1 && k2)
636 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 static inline void mark_empty (T &entry)
653 {
654 entry.m_key = nullptr;
655 }
656 template <typename T>
657 static inline bool is_deleted (const T &entry)
658 {
659 return entry.m_key == reinterpret_cast<key_type> (1);
660 }
661 template <typename T>
662 static inline bool is_empty (const T &entry)
663 {
664 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
672{
673 per_call_string_data (const call_string &key, int num_supernodes)
674 : m_key (key), m_stats (num_supernodes)
675 {}
676
679};
680
681/* Data about a particular function within an exploded_graph. */
682
692
693/* The strongly connected components of a supergraph.
694 In particular, this allows us to compute a partial ordering
695 of supernodes. */
696
698{
699public:
701
702 int get_scc_id (int node_index) const
703 {
704 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
711private:
713 {
715 : m_id (-1), m_lowlink (-1), m_on_stack (false)
716 {}
717
718 int m_id;
721 };
722
723 void strong_connect (unsigned index, logger *logger);
724
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
741{
742public:
743 worklist (const exploded_graph &eg, const analysis_plan &plan);
744 unsigned length () const;
747 void add_node (exploded_node *enode);
748 int get_scc_id (const supernode &snode) const
749 {
750 return m_scc.get_scc_id (snode.m_id);
751 }
752
753 std::unique_ptr<json::object> to_json () const;
754
755private:
756 class key_t
757 {
758 public:
759 key_t (const worklist &w, exploded_node *enode)
760 : m_worklist (w), m_enode (enode)
761 {}
762
763 bool operator< (const key_t &other) const
764 {
765 return cmp (*this, other) < 0;
766 }
767
768 bool operator== (const key_t &other) const
769 {
770 return cmp (*this, other) == 0;
771 }
772
773 bool operator> (const key_t &other) const
774 {
775 return !(*this == other || *this < other);
776 }
777
778 private:
779 static int cmp (const key_t &ka, const key_t &kb);
780
781 int get_scc_id (const exploded_node *enode) const
782 {
783 const supernode *snode = enode->get_supernode ();
784 if (snode == nullptr)
785 return 0;
786 return m_worklist.m_scc.get_scc_id (snode->m_id);
787 }
788
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). */
798
799 /* Priority queue, backed by a fibonacci_heap. */
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
808class exploded_graph : public digraph<eg_traits>
809{
810public:
811 typedef hash_map <const call_string *,
813
816 const state_purge_map *purge_map,
817 const analysis_plan &plan,
818 int verbosity);
820
821 logger *get_logger () const { return m_logger.get_logger (); }
822
823 const supergraph &get_supergraph () const { return m_sg; }
824 const extrinsic_state &get_ext_state () const { return m_ext_state; }
825 engine *get_engine () const { return m_ext_state.get_engine (); }
826 const state_purge_map *get_purge_map () const { return m_purge_map; }
827 const analysis_plan &get_analysis_plan () const { return m_plan; }
828
829 exploded_node *get_origin () const { return m_origin; }
830
832
837
839 const program_state &state,
840 exploded_node *enode_for_diag,
841 bool add_to_worklist = true);
843 const superedge *sedge, bool could_do_work,
844 std::unique_ptr<custom_edge_info> custom = nullptr);
845
850
853
857
859 const exploded_node *enode,
860 const supernode *node, const gimple *stmt,
863
869 {
871 }
872
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
882
885
886 int get_scc_id (const supernode &node) const
887 {
888 return m_worklist.get_scc_id (node);
889 }
890
892
894 const gimple *stmt,
896
897 /* In infinite-loop.cc */
898 void detect_infinite_loops ();
899
900 /* In infinite-recursion.cc */
903 exploded_node *enode) const;
904
905 std::unique_ptr<diagnostics::digraphs::digraph>
907
908 const worklist &
909 get_worklist () const { return m_worklist; }
910
911private:
913
915
917
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 *,
927
928 /* Map from program_point to per-program_point data. */
932
934
936
938
940
942
945
947
948 /* Stats. */
953
955
956 /* Functions with a top-level enode, to make add_function_entry
957 be idempotent, for use in handling callbacks. */
959};
960
961/* A reason why a particular exploded_path is infeasible. */
962
964{
965public:
966 feasibility_problem (unsigned eedge_idx,
967 const exploded_edge &eedge,
968 std::unique_ptr<rejected_constraint> rc)
969 : m_eedge_idx (eedge_idx), m_eedge (eedge),
970 m_rc (std::move (rc))
971 {}
972
973 std::unique_ptr<text_art::tree_widget>
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;
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
992{
993public:
995 const supergraph &sg);
997 const supergraph &sg);
999
1001
1003 const exploded_edge *eedge,
1005 std::unique_ptr<rejected_constraint> *out_rc);
1006
1008 const region_model &get_model () const { return m_model; }
1011
1012 std::unique_ptr<text_art::tree_widget>
1014
1015 void dump_to_pp (pretty_printer *pp) const;
1016
1017private:
1020};
1021
1022// TODO: split the above up?
1023
1024} // namespace ana
1025
1026#endif /* GCC_ANALYZER_EXPLODED_GRAPH_H */
Definition analysis-plan.h:35
Definition ops.h:433
Definition call-string.h:44
Definition checker-path.h:32
Definition common.h:421
Definition diagnostic-manager.h:161
Definition region-model.h:1412
Definition exploded-graph.h:350
std::unique_ptr< json::object > to_json() const
const operation * maybe_get_op() const
void dump_dot_label(pretty_printer *pp) const
bool m_could_do_work_p
Definition exploded-graph.h:390
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:367
void dump_dot(graphviz_out *gv, const dump_args_t &args) const final override
bool could_do_work_p() const
Definition exploded-graph.h:369
DISABLE_COPY_AND_ASSIGN(exploded_edge)
const gimple * maybe_get_stmt() const
const superedge *const m_sedge
Definition exploded-graph.h:362
Definition exploded-graph.h:809
hash_map< const point_and_state *, exploded_node *, eg_hash_map_traits > map_t
Definition exploded-graph.h:925
void log_stats() const
stats * get_global_stats()
Definition exploded-graph.h:873
const call_string_data_map_t * get_per_call_string_data() const
Definition exploded-graph.h:883
const state_purge_map * get_purge_map() const
Definition exploded-graph.h:826
const extrinsic_state & m_ext_state
Definition exploded-graph.h:937
void detect_infinite_recursion(exploded_node *enode)
Definition infinite-recursion.cc:625
std::unique_ptr< diagnostics::digraphs::digraph > make_diagnostics_digraph() const
call_string_data_map_t m_per_call_string_data
Definition exploded-graph.h:954
stats m_functionless_stats
Definition exploded-graph.h:952
exploded_node * find_previous_entry_to(function *top_of_stack_fun, exploded_node *enode) const
Definition infinite-recursion.cc:333
function_stat_map_t m_per_function_stats
Definition exploded-graph.h:951
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:555
void process_node(exploded_node *node)
engine * get_engine() const
Definition exploded-graph.h:825
point_map_t m_per_point_data
Definition exploded-graph.h:931
diagnostic_manager & get_diagnostic_manager()
Definition exploded-graph.h:864
exploded_node * add_function_entry(const function &fun)
const worklist & get_worklist() const
Definition exploded-graph.h:909
per_function_data * get_per_function_data(function *) const
log_user m_logger
Definition exploded-graph.h:918
bool maybe_process_run_of_enodes(exploded_node *node)
const supergraph & get_supergraph() const
Definition exploded-graph.h:823
const analysis_plan & get_analysis_plan() const
Definition exploded-graph.h:827
map_t m_point_and_state_to_node
Definition exploded-graph.h:926
const supergraph & m_sg
Definition exploded-graph.h:916
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:946
hash_map< function *, per_function_data * > per_function_data_t
Definition exploded-graph.h:943
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:868
per_program_point_data * get_per_program_point_data(const program_point &) const
logger * get_logger() const
Definition exploded-graph.h:821
exploded_node * m_origin
Definition exploded-graph.h:935
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:812
hash_set< function * > m_functions_with_enodes
Definition exploded-graph.h:958
stats * get_or_create_function_stats(function *fn)
void print_bar_charts(pretty_printer *pp) const
stats m_global_stats
Definition exploded-graph.h:949
ordered_hash_map< function *, stats * > function_stat_map_t
Definition exploded-graph.h:950
const extrinsic_state & get_ext_state() const
Definition exploded-graph.h:824
worklist m_worklist
Definition exploded-graph.h:933
void dump_stats(FILE *) const
int get_scc_id(const supernode &node) const
Definition exploded-graph.h:886
hash_map< const program_point *, per_program_point_data *, eg_point_hash_map_traits > point_map_t
Definition exploded-graph.h:930
std::unique_ptr< json::object > to_json() const
void save_diagnostic(const state_machine &sm, const exploded_node *enode, const supernode *node, const gimple *stmt, tree var, state_machine::state_t state, pending_diagnostic *d)
const state_purge_map *const m_purge_map
Definition exploded-graph.h:939
const analysis_plan & m_plan
Definition exploded-graph.h:941
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:944
exploded_node * get_origin() const
Definition exploded-graph.h:829
exploded_node * get_node_by_index(int idx) const
DISABLE_COPY_AND_ASSIGN(exploded_graph)
Definition exploded-graph.h:221
DISABLE_COPY_AND_ASSIGN(exploded_node)
const point_and_state * get_ps_key() const
Definition exploded-graph.h:303
status
Definition exploded-graph.h:228
@ worklist
Definition exploded-graph.h:230
function * get_function() const
Definition exploded-graph.h:292
location_t get_location() const
Definition exploded-graph.h:288
void dump_to_logger(logger &log) const
unsigned get_num_diagnostics() const
Definition exploded-graph.h:319
void dump_saved_diagnostics(pretty_printer *pp) const
void dump_dot(graphviz_out *gv, const dump_args_t &args) const final override
void on_throw(exploded_graph &eg, const gcall &call, const program_point &after_throw_point, program_state *new_state, bool is_rethrow, region_model_context *ctxt)
std::unique_ptr< json::object > to_json(const extrinsic_state &ext_state) const
void add_diagnostic(const saved_diagnostic *sd)
Definition exploded-graph.h:315
void dump_processed_stmts(pretty_printer *pp) const
const point_and_state m_ps
Definition exploded-graph.h:333
void dump() const
const char * get_dot_fillcolor() const
void dump_dot_id(pretty_printer *pp) const
const program_state & get_state() const
Definition exploded-graph.h:301
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:343
const program_point * get_point_key() const
Definition exploded-graph.h:304
enum status get_status() const
Definition exploded-graph.h:308
void set_status(enum status s)
Definition exploded-graph.h:309
int get_stack_depth() const
Definition exploded-graph.h:296
void on_longjmp(exploded_graph &eg, const gcall &call, program_state *new_state, region_model_context *ctxt)
exploded_node(const point_and_state &ps, int index)
const program_point & get_point() const
Definition exploded-graph.h:283
exploded_node(point_and_state &&ps, int index)
auto_vec< const saved_diagnostic * > m_saved_diagnostics
Definition exploded-graph.h:339
const supernode * get_supernode() const
Definition exploded-graph.h:284
void detect_leaks(exploded_graph &eg)
std::unique_ptr< text_art::tree_widget > make_dump_widget(symbolic::node_dump_state &nds) const
hashval_t hash() const
Definition exploded-graph.h:251
void dump_to_pp(pretty_printer *) const
enum status m_status
Definition exploded-graph.h:335
const saved_diagnostic * get_saved_diagnostic(unsigned idx) const
Definition exploded-graph.h:323
Definition program-state.h:34
engine * get_engine() const
Definition program-state.h:77
feasibility_problem(unsigned eedge_idx, const exploded_edge &eedge, std::unique_ptr< rejected_constraint > rc)
Definition exploded-graph.h:966
const exploded_edge & m_eedge
Definition exploded-graph.h:984
void dump_to_logger(logger &log) const
void dump_to_pp(pretty_printer *pp) const
unsigned m_eedge_idx
Definition exploded-graph.h:983
std::unique_ptr< json::object > to_json() const
std::unique_ptr< rejected_constraint > m_rc
Definition exploded-graph.h:985
std::unique_ptr< text_art::tree_widget > make_dump_widget(symbolic::node_dump_state &nds) const
std::unique_ptr< text_art::tree_widget > make_dump_widget(symbolic::node_dump_state &nds) const
bool maybe_update_for_edge(logger *logger, const exploded_edge *eedge, region_model_context *ctxt, std::unique_ptr< rejected_constraint > *out_rc)
auto_sbitmap & get_snodes_visited()
Definition exploded-graph.h:1009
void dump_to_pp(pretty_printer *pp) const
feasibility_state(const region_model &model, const supergraph &sg)
auto_sbitmap m_snodes_visited
Definition exploded-graph.h:1019
feasibility_state(region_model_manager *manager, const supergraph &sg)
region_model & get_model()
Definition exploded-graph.h:1007
feasibility_state(const feasibility_state &other)
region_model m_model
Definition exploded-graph.h:1018
const region_model & get_model() const
Definition exploded-graph.h:1008
feasibility_state & operator=(const feasibility_state &other)
const auto_sbitmap & get_snodes_visited() const
Definition exploded-graph.h:1010
Definition region.h:323
void on_condition(const svalue *lhs, enum tree_code op, const svalue *rhs) final override
void terminate_path() final override
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=nullptr, bool *out_could_have_done_work=nullptr)
exploded_graph * m_eg
Definition exploded-graph.h:123
const extrinsic_state & m_ext_state
Definition exploded-graph.h:129
logger * get_logger() final override
Definition exploded-graph.h:66
void on_svalue_leak(const svalue *) override
void on_pop_frame(const frame_region *frame_reg) final override
void add_note(std::unique_ptr< pending_note > pn) final override
bool * m_out_could_have_done_work
Definition exploded-graph.h:132
bool warn_at(std::unique_ptr< pending_diagnostic > d, pending_location &&ploc) final override
void on_state_leak(const state_machine &sm, const svalue *sval, state_machine::state_t state)
void on_liveness_change(symbolic::liveness_context &) final override
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
pending_location get_pending_location_for_diag() const override
program_state * m_new_state
Definition exploded-graph.h:127
log_user m_logger
Definition exploded-graph.h:124
void on_unknown_change(const symbolic::value_node &val, bool is_mutable) final override
const program_state * m_old_state
Definition exploded-graph.h:126
void on_unusable_in_infinite_loop() override
Definition exploded-graph.h:118
const program_state * get_state() const override
Definition exploded-graph.h:114
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
path_context * m_path_ctxt
Definition exploded-graph.h:131
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:128
uncertainty_t * m_uncertainty
Definition exploded-graph.h:130
const gimple * get_stmt() const override
Definition exploded-graph.h:111
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:117
const extrinsic_state * get_ext_state() const final override
Definition exploded-graph.h:100
const exploded_graph * get_eg() const override
Definition exploded-graph.h:112
void purge_state_involving(const symbolic::node &node) final override
exploded_node * m_enode_for_diag
Definition exploded-graph.h:125
interprocedural_call(const call_and_return_op &op, function &callee_fun)
Definition exploded-graph.h:399
void get_dot_attrs(const char *&out_style, const char *&out_color) const final override
bool update_model(region_model *model, const exploded_edge *eedge, region_model_context *ctxt) const final override
const gcall & get_gcall() const
void add_events_to_path(checker_path *emission_path, const exploded_edge &eedge, pending_diagnostic &pd, const state_transition *state_trans) const final override
const call_and_return_op & m_op
Definition exploded-graph.h:429
bool update_state(program_state *state, const exploded_edge *eedge, region_model_context *ctxt) const final override
bool try_to_rewind_data_flow(rewind_context &) const final override
function & m_callee_fun
Definition exploded-graph.h:430
void print(pretty_printer *pp) const final override
const gcall & m_call_stmt
Definition exploded-graph.h:465
void print(pretty_printer *pp) const final override
bool try_to_rewind_data_flow(rewind_context &) const final override
interprocedural_return(const gcall &call_stmt)
Definition exploded-graph.h:439
bool update_model(region_model *model, const exploded_edge *eedge, region_model_context *ctxt) const final override
bool update_state(program_state *state, const exploded_edge *eedge, region_model_context *ctxt) const final override
void get_dot_attrs(const char *&out_style, const char *&out_color) const final override
void add_events_to_path(checker_path *emission_path, const exploded_edge &eedge, pending_diagnostic &pd, const state_transition *state_trans) const final override
Definition analyzer-logging.h:200
logger * get_logger() const
Definition analyzer-logging.h:205
Definition analyzer-logging.h:36
Definition ops.h:113
Definition common.h:471
Definition pending-diagnostic.h:258
Definition exploded-graph.h:140
hashval_t m_hash
Definition exploded-graph.h:191
bool operator==(const point_and_state &other) const
Definition exploded-graph.h:166
void validate(const extrinsic_state &ext_state) const
const program_state & get_state() const
Definition exploded-graph.h:172
void set_state(program_state &&state)
Definition exploded-graph.h:180
program_state m_state
Definition exploded-graph.h:190
program_point m_point
Definition exploded-graph.h:189
point_and_state(const program_point &point, const program_state &state)
Definition exploded-graph.h:142
point_and_state(point_and_state &&other)
Definition exploded-graph.h:155
const program_point & get_point() const
Definition exploded-graph.h:171
hashval_t hash() const
Definition exploded-graph.h:162
void set_state(const program_state &state)
Definition exploded-graph.h:174
point_and_state(const point_and_state &other)=default
Definition program-point.h:54
location_t get_location() const
Definition program-point.h:102
function * get_function() const
Definition program-point.h:92
program_point(const supernode *snode, const call_string &call_string)
Definition program-point.h:56
const supernode * get_supernode() const
Definition program-point.h:86
int get_stack_depth() const
Definition program-point.h:111
const call_string & get_call_string() const
Definition program-point.h:90
hashval_t hash() const
Definition program-state.h:239
hashval_t hash() const
Definition region-model.h:840
Definition region-model-manager.h:36
Definition region-model.h:289
setjmp_record m_setjmp_record
Definition exploded-graph.h:524
program_point get_point_before_setjmp() const
Definition exploded-graph.h:495
bool update_model(region_model *model, const exploded_edge *eedge, region_model_context *ctxt) const final override
void add_events_to_path(checker_path *emission_path, const exploded_edge &eedge, pending_diagnostic &pd, const state_transition *state_trans) const final override
const gcall & get_setjmp_call() const
Definition exploded-graph.h:508
void print(pretty_printer *pp) const final override
Definition exploded-graph.h:480
const exploded_node * get_enode_origin() const
Definition exploded-graph.h:518
const gcall & m_longjmp_call
Definition exploded-graph.h:525
program_point get_point_after_setjmp() const
Definition exploded-graph.h:501
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:513
Definition diagnostic-manager.h:79
Definition program-state.h:98
Definition sm.h:43
const state_machine::state * state_t
Definition sm.h:63
Definition state-purge.h:31
Definition state-transition.h:31
Definition exploded-graph.h:698
void strong_connect(unsigned index, logger *logger)
int get_scc_id(int node_index) const
Definition exploded-graph.h:702
auto_vec< per_node_data > m_per_node
Definition exploded-graph.h:727
const supergraph & m_sg
Definition exploded-graph.h:725
strongly_connected_components(const supergraph &sg, logger *logger)
auto_vec< unsigned > m_stack
Definition exploded-graph.h:726
std::unique_ptr< json::array > to_json() const
Definition supergraph.h:284
Definition supergraph.h:105
Definition supergraph.h:227
int m_id
Definition supergraph.h:271
Definition svalue.h:82
Definition liveness-context.h:33
Definition symbolic-nodes.h:468
Definition store.h:357
bool operator<(const key_t &other) const
Definition exploded-graph.h:763
const worklist & m_worklist
Definition exploded-graph.h:789
bool operator==(const key_t &other) const
Definition exploded-graph.h:768
exploded_node * m_enode
Definition exploded-graph.h:790
bool operator>(const key_t &other) const
Definition exploded-graph.h:773
static int cmp(const key_t &ka, const key_t &kb)
int get_scc_id(const exploded_node *enode) const
Definition exploded-graph.h:781
key_t(const worklist &w, exploded_node *enode)
Definition exploded-graph.h:759
Definition exploded-graph.h:741
std::unique_ptr< json::object > to_json() const
void add_node(exploded_node *enode)
strongly_connected_components m_scc
Definition exploded-graph.h:796
worklist(const exploded_graph &eg, const analysis_plan &plan)
queue_t m_queue
Definition exploded-graph.h:801
exploded_node * take_next()
fibonacci_heap< key_t, exploded_node > queue_t
Definition exploded-graph.h:800
exploded_node * peek_next()
const analysis_plan & m_plan
Definition exploded-graph.h:797
int get_scc_id(const supernode &snode) const
Definition exploded-graph.h:748
unsigned length() const
Definition sbitmap.h:303
Definition vec.h:1667
node_t * m_dest
Definition digraph.h:112
dedge(node_t *src, node_t *dest)
Definition digraph.h:93
eg_traits::dump_args_t dump_args_t
Definition digraph.h:91
digraph()
Definition digraph.h:128
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:388
Definition hash-map.h:40
Definition hash-set.h:37
Definition ordered-hash-map.h:35
Definition pretty-print.h:241
union tree_node * tree
Definition coretypes.h:97
void final(rtx_insn *first, FILE *file, int optimize_p)
Definition final.cc:2004
double log(double)
tree_code
Definition genmatch.cc:1011
Definition common.h:74
Definition access-diagram.h:30
@ other
Definition common.h:535
Definition custom-sarif-properties/state-graphs.h:33
void pp_string(pretty_printer *pp, const char *str)
Definition pretty-print.cc:2765
Definition constraint-manager.h:123
Definition exploded-graph.h:548
static bool equal_keys(const key_type &k1, const key_type &k2)
Definition exploded-graph.h:559
static void mark_empty(T &entry)
Definition exploded-graph.h:582
static void mark_deleted(T &entry)
Definition exploded-graph.h:577
static bool is_deleted(const T &entry)
Definition exploded-graph.h:587
static const bool empty_zero_p
Definition exploded-graph.h:596
exploded_node * compare_type
Definition exploded-graph.h:551
const point_and_state * key_type
Definition exploded-graph.h:549
exploded_node * value_type
Definition exploded-graph.h:550
static void remove(T &)
Definition exploded-graph.h:572
static hashval_t hash(const key_type &k)
Definition exploded-graph.h:553
static bool is_empty(const T &entry)
Definition exploded-graph.h:592
Definition exploded-graph.h:618
static bool is_deleted(const T &entry)
Definition exploded-graph.h:657
static const bool empty_zero_p
Definition exploded-graph.h:666
static void mark_empty(T &entry)
Definition exploded-graph.h:652
static hashval_t hash(const key_type &k)
Definition exploded-graph.h:623
const program_point * key_type
Definition exploded-graph.h:619
per_program_point_data * value_type
Definition exploded-graph.h:620
per_program_point_data * compare_type
Definition exploded-graph.h:621
static void mark_deleted(T &entry)
Definition exploded-graph.h:647
static bool is_empty(const T &entry)
Definition exploded-graph.h:662
static bool equal_keys(const key_type &k1, const key_type &k2)
Definition exploded-graph.h:629
static void remove(T &)
Definition exploded-graph.h:642
bool show_enode_details_p(const exploded_node &enode) const
const exploded_graph & m_eg
Definition exploded-graph.h:210
virtual void dump_extra_info(const exploded_node *, pretty_printer *) const
Definition exploded-graph.h:208
dump_args_t(const exploded_graph &eg)
Definition exploded-graph.h:203
Definition exploded-graph.h:197
exploded_graph graph_t
Definition exploded-graph.h:200
exploded_edge edge_t
Definition exploded-graph.h:199
exploded_node node_t
Definition exploded-graph.h:198
exploded_cluster cluster_t
Definition exploded-graph.h:212
Definition diagnostic-manager.h:35
Definition exploded-graph.h:672
stats m_stats
Definition exploded-graph.h:678
const call_string & m_key
Definition exploded-graph.h:677
per_call_string_data(const call_string &key, int num_supernodes)
Definition exploded-graph.h:673
Definition exploded-graph.h:684
per_function_data()
Definition exploded-graph.h:685
auto_vec< call_summary * > m_summaries
Definition exploded-graph.h:690
void add_call_summary(exploded_node *node)
Definition exploded-graph.h:602
const program_point m_key
Definition exploded-graph.h:607
int m_excess_enodes
Definition exploded-graph.h:611
per_program_point_data(const program_point &key)
Definition exploded-graph.h:603
auto_vec< exploded_node * > m_enodes
Definition exploded-graph.h:608
Definition ops.h:78
Definition svalue.h:496
const exploded_node * m_enode
Definition svalue.h:513
const gcall * m_setjmp_call
Definition svalue.h:515
const superedge * m_sedge
Definition svalue.h:514
Definition exploded-graph.h:531
void log(logger *logger) const
void dump(FILE *out) const
int m_num_nodes
Definition exploded-graph.h:538
int m_num_supernodes
Definition exploded-graph.h:541
int m_node_reuse_after_merge_count
Definition exploded-graph.h:540
stats(int num_supernodes)
int get_total_enodes() const
int m_node_reuse_count
Definition exploded-graph.h:539
per_node_data()
Definition exploded-graph.h:714
bool m_on_stack
Definition exploded-graph.h:720
int m_id
Definition exploded-graph.h:718
int m_lowlink
Definition exploded-graph.h:719
Definition symbolic-nodes.h:276
Definition function.h:249
Definition gimple.h:356
Definition gimple.h:225
Definition gimple.h:465
Definition ira-emit.cc:158
Definition gengtype.h:377
Definition genautomata.cc:669
#define gcc_assert(EXPR)
Definition system.h:772
#define false
Definition system.h:846