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