1 /* Classes for managing a directed graph of <point, state> pairs.
2 Copyright (C) 2019-2023 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #ifndef GCC_ANALYZER_EXPLODED_GRAPH_H
22 #define GCC_ANALYZER_EXPLODED_GRAPH_H
24 #include "alloc-pool.h"
25 #include "fibonacci_heap.h"
26 #include "supergraph.h"
28 #include "shortest-paths.h"
29 #include "analyzer/sm.h"
30 #include "analyzer/program-state.h"
31 #include "analyzer/diagnostic-manager.h"
35 /* Concrete implementation of region_model_context, wiring it up to the
36 rest of the analysis engine. */
38 class impl_region_model_context
: public region_model_context
41 impl_region_model_context (exploded_graph
&eg
,
42 exploded_node
*enode_for_diag
,
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
,
52 stmt_finder
*stmt_finder
= NULL
);
54 impl_region_model_context (program_state
*state
,
55 const extrinsic_state
&ext_state
,
56 uncertainty_t
*uncertainty
,
57 logger
*logger
= NULL
);
59 bool warn (std::unique_ptr
<pending_diagnostic
> d
,
60 const stmt_finder
*custom_finder
= NULL
) final override
;
61 void add_note (std::unique_ptr
<pending_note
> pn
) final override
;
62 void add_event (std::unique_ptr
<checker_event
> event
) final override
;
63 void on_svalue_leak (const svalue
*) override
;
64 void on_liveness_change (const svalue_set
&live_svalues
,
65 const region_model
*model
) final override
;
66 logger
*get_logger () final override
68 return m_logger
.get_logger ();
71 void on_state_leak (const state_machine
&sm
,
73 state_machine::state_t state
);
75 void on_condition (const svalue
*lhs
,
77 const svalue
*rhs
) final override
;
79 void on_bounded_ranges (const svalue
&sval
,
80 const bounded_ranges
&ranges
) final override
;
82 void on_pop_frame (const frame_region
*frame_reg
) final override
;
84 void on_unknown_change (const svalue
*sval
, bool is_mutable
) final override
;
86 void on_phi (const gphi
*phi
, tree rhs
) final override
;
88 void on_unexpected_tree_code (tree t
,
89 const dump_location_t
&loc
) final override
;
91 void on_escaped_function (tree fndecl
) final override
;
93 uncertainty_t
*get_uncertainty () final override
;
95 void purge_state_involving (const svalue
*sval
) final override
;
97 void bifurcate (std::unique_ptr
<custom_edge_info
> info
) final override
;
98 void terminate_path () final override
;
99 const extrinsic_state
*get_ext_state () const final override
104 get_state_map_by_name (const char *name
,
105 sm_state_map
**out_smap
,
106 const state_machine
**out_sm
,
107 unsigned *out_sm_idx
,
108 std::unique_ptr
<sm_context
> *out_sm_context
) override
;
110 const gimple
*get_stmt () const override
{ return m_stmt
; }
111 const exploded_graph
*get_eg () const override
{ return m_eg
; }
113 exploded_graph
*m_eg
;
115 exploded_node
*m_enode_for_diag
;
116 const program_state
*m_old_state
;
117 program_state
*m_new_state
;
118 const gimple
*m_stmt
;
119 stmt_finder
*m_stmt_finder
;
120 const extrinsic_state
&m_ext_state
;
121 uncertainty_t
*m_uncertainty
;
122 path_context
*m_path_ctxt
;
125 /* A <program_point, program_state> pair, used internally by
126 exploded_node as its immutable data, and as a key for identifying
127 exploded_nodes we've already seen in the graph. */
129 class point_and_state
132 point_and_state (const program_point
&point
,
133 const program_state
&state
)
136 m_hash (m_point
.hash () ^ m_state
.hash ())
138 /* We shouldn't be building point_and_states and thus exploded_nodes
139 for states that aren't valid. */
140 gcc_assert (state
.m_valid
);
143 hashval_t
hash () const
147 bool operator== (const point_and_state
&other
) const
149 return m_point
== other
.m_point
&& m_state
== other
.m_state
;
152 const program_point
&get_point () const { return m_point
; }
153 const program_state
&get_state () const { return m_state
; }
155 void set_state (const program_state
&state
)
158 m_hash
= m_point
.hash () ^ m_state
.hash ();
161 void validate (const extrinsic_state
&ext_state
) const;
164 program_point m_point
;
165 program_state m_state
;
169 /* A traits class for exploded graphs and their nodes and edges. */
173 typedef exploded_node node_t
;
174 typedef exploded_edge edge_t
;
175 typedef exploded_graph graph_t
;
178 dump_args_t (const exploded_graph
&eg
) : m_eg (eg
) {}
180 bool show_enode_details_p (const exploded_node
&enode
) const;
183 dump_extra_info (const exploded_node
*, pretty_printer
*) const {}
185 const exploded_graph
&m_eg
;
187 typedef exploded_cluster cluster_t
;
190 /* An exploded_node is a unique, immutable <point, state> pair within the
192 Each exploded_node has a unique index within the graph
193 (for ease of debugging). */
195 class exploded_node
: public dnode
<eg_traits
>
198 /* Has this enode had exploded_graph::process_node called on it?
199 This allows us to distinguish enodes that were merged during
200 worklist-handling, and thus never had process_node called on them
201 (in favor of processing the merged node). */
204 /* Node is in the worklist. */
207 /* Node has had exploded_graph::process_node called on it. */
210 /* Node was left unprocessed due to merger; it won't have had
211 exploded_graph::process_node called on it. */
214 /* Node was processed by maybe_process_run_of_before_supernode_enodes. */
217 static const char * status_to_str (enum status s
);
219 exploded_node (const point_and_state
&ps
, int index
);
221 hashval_t
hash () const { return m_ps
.hash (); }
223 const char * get_dot_fillcolor () const;
224 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
)
225 const final override
;
226 void dump_dot_id (pretty_printer
*pp
) const;
228 void dump_to_pp (pretty_printer
*pp
, const extrinsic_state
&ext_state
) const;
229 void dump (FILE *fp
, const extrinsic_state
&ext_state
) const;
230 void dump (const extrinsic_state
&ext_state
) const;
232 void dump_processed_stmts (pretty_printer
*pp
) const;
233 void dump_saved_diagnostics (pretty_printer
*pp
) const;
235 json::object
*to_json (const extrinsic_state
&ext_state
) const;
237 /* The result of on_stmt. */
240 on_stmt_flags () : m_terminate_path (false)
243 static on_stmt_flags
terminate_path ()
245 return on_stmt_flags (true);
248 /* Should we stop analyzing this path (on_stmt may have already
249 added nodes/edges, e.g. when handling longjmp). */
250 bool m_terminate_path
: 1;
253 on_stmt_flags (bool terminate_path
)
254 : m_terminate_path (terminate_path
)
258 on_stmt_flags
on_stmt (exploded_graph
&eg
,
259 const supernode
*snode
,
261 program_state
*state
,
262 uncertainty_t
*uncertainty
,
263 path_context
*path_ctxt
);
264 void on_stmt_pre (exploded_graph
&eg
,
266 program_state
*state
,
267 bool *out_terminate_path
,
268 bool *out_unknown_side_effects
,
269 region_model_context
*ctxt
);
270 void on_stmt_post (const gimple
*stmt
,
271 program_state
*state
,
272 bool unknown_side_effects
,
273 region_model_context
*ctxt
);
275 on_stmt_flags
replay_call_summaries (exploded_graph
&eg
,
276 const supernode
*snode
,
277 const gcall
*call_stmt
,
278 program_state
*state
,
279 path_context
*path_ctxt
,
281 per_function_data
*called_fn_data
,
282 region_model_context
*ctxt
);
283 void replay_call_summary (exploded_graph
&eg
,
284 const supernode
*snode
,
285 const gcall
*call_stmt
,
286 program_state
*state
,
287 path_context
*path_ctxt
,
289 call_summary
*summary
,
290 region_model_context
*ctxt
);
292 bool on_edge (exploded_graph
&eg
,
293 const superedge
*succ
,
294 program_point
*next_point
,
295 program_state
*next_state
,
296 uncertainty_t
*uncertainty
);
297 void on_longjmp (exploded_graph
&eg
,
299 program_state
*new_state
,
300 region_model_context
*ctxt
);
302 void detect_leaks (exploded_graph
&eg
);
304 const program_point
&get_point () const { return m_ps
.get_point (); }
305 const supernode
*get_supernode () const
307 return get_point ().get_supernode ();
309 function
*get_function () const
311 return get_point ().get_function ();
313 int get_stack_depth () const
315 return get_point ().get_stack_depth ();
317 const gimple
*get_stmt () const { return get_point ().get_stmt (); }
318 const gimple
*get_processed_stmt (unsigned idx
) const;
320 const program_state
&get_state () const { return m_ps
.get_state (); }
322 const point_and_state
*get_ps_key () const { return &m_ps
; }
323 const program_point
*get_point_key () const { return &m_ps
.get_point (); }
325 void dump_succs_and_preds (FILE *outf
) const;
327 enum status
get_status () const { return m_status
; }
328 void set_status (enum status status
)
330 gcc_assert (m_status
== STATUS_WORKLIST
);
334 void add_diagnostic (const saved_diagnostic
*sd
)
336 m_saved_diagnostics
.safe_push (sd
);
338 unsigned get_num_diagnostics () const
340 return m_saved_diagnostics
.length ();
342 const saved_diagnostic
*get_saved_diagnostic (unsigned idx
) const
344 return m_saved_diagnostics
[idx
];
348 DISABLE_COPY_AND_ASSIGN (exploded_node
);
350 /* The <program_point, program_state> pair. This is const, as it
351 is immutable once the exploded_node has been created. */
352 const point_and_state m_ps
;
354 enum status m_status
;
356 /* The saved_diagnostics at this enode, borrowed from the
357 diagnostic_manager. */
358 auto_vec
<const saved_diagnostic
*> m_saved_diagnostics
;
361 /* The index of this exploded_node. */
364 /* The number of stmts that were processed when process_node was
365 called on this enode. */
366 unsigned m_num_processed_stmts
;
369 /* An edge within the exploded graph.
370 Some exploded_edges have an underlying superedge; others don't. */
372 class exploded_edge
: public dedge
<eg_traits
>
375 exploded_edge (exploded_node
*src
, exploded_node
*dest
,
376 const superedge
*sedge
,
377 std::unique_ptr
<custom_edge_info
> custom_info
);
378 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
)
379 const final override
;
380 void dump_dot_label (pretty_printer
*pp
) const;
382 json::object
*to_json () const;
385 const superedge
*const m_sedge
;
387 /* NULL for most edges; will be non-NULL for special cases
388 such as an unwind from a longjmp to a setjmp, or when
389 a signal is delivered to a signal-handler. */
390 std::unique_ptr
<custom_edge_info
> m_custom_info
;
393 DISABLE_COPY_AND_ASSIGN (exploded_edge
);
396 /* Extra data for an exploded_edge that represents dynamic call info ( calls
397 that doesn't have an underlying superedge representing the call ). */
399 class dynamic_call_info_t
: public custom_edge_info
402 dynamic_call_info_t (const gcall
*dynamic_call
,
403 const bool is_returning_call
= false)
404 : m_dynamic_call (dynamic_call
),
405 m_is_returning_call (is_returning_call
)
408 void print (pretty_printer
*pp
) const final override
410 if (m_is_returning_call
)
411 pp_string (pp
, "dynamic_return");
413 pp_string (pp
, "dynamic_call");
416 bool update_model (region_model
*model
,
417 const exploded_edge
*eedge
,
418 region_model_context
*ctxt
) const final override
;
420 void add_events_to_path (checker_path
*emission_path
,
421 const exploded_edge
&eedge
) const final override
;
423 const gcall
*m_dynamic_call
;
424 const bool m_is_returning_call
;
428 /* Extra data for an exploded_edge that represents a rewind from a
429 longjmp to a setjmp (or from a siglongjmp to a sigsetjmp). */
431 class rewind_info_t
: public custom_edge_info
434 rewind_info_t (const setjmp_record
&setjmp_record
,
435 const gcall
*longjmp_call
)
436 : m_setjmp_record (setjmp_record
),
437 m_longjmp_call (longjmp_call
)
440 void print (pretty_printer
*pp
) const final override
442 pp_string (pp
, "rewind");
445 bool update_model (region_model
*model
,
446 const exploded_edge
*eedge
,
447 region_model_context
*ctxt
) const final override
;
449 void add_events_to_path (checker_path
*emission_path
,
450 const exploded_edge
&eedge
) const final override
;
452 const program_point
&get_setjmp_point () const
454 const program_point
&origin_point
= get_enode_origin ()->get_point ();
456 /* "origin_point" ought to be before the call to "setjmp". */
457 gcc_assert (origin_point
.get_kind () == PK_BEFORE_STMT
);
459 /* TODO: assert that it's the final stmt in its supernode. */
464 const gcall
*get_setjmp_call () const
466 return m_setjmp_record
.m_setjmp_call
;
469 const gcall
*get_longjmp_call () const
471 return m_longjmp_call
;
474 const exploded_node
*get_enode_origin () const
476 return m_setjmp_record
.m_enode
;
480 setjmp_record m_setjmp_record
;
481 const gcall
*m_longjmp_call
;
484 /* Statistics about aspects of an exploded_graph. */
488 stats (int num_supernodes
);
489 void log (logger
*logger
) const;
490 void dump (FILE *out
) const;
492 int get_total_enodes () const;
494 int m_num_nodes
[NUM_POINT_KINDS
];
495 int m_node_reuse_count
;
496 int m_node_reuse_after_merge_count
;
497 int m_num_supernodes
;
500 /* Traits class for ensuring uniqueness of point_and_state data within
501 an exploded_graph. */
503 struct eg_hash_map_traits
505 typedef const point_and_state
*key_type
;
506 typedef exploded_node
*value_type
;
507 typedef exploded_node
*compare_type
;
509 static inline hashval_t
hash (const key_type
&k
)
511 gcc_assert (k
!= NULL
);
512 gcc_assert (k
!= reinterpret_cast<key_type
> (1));
515 static inline bool equal_keys (const key_type
&k1
, const key_type
&k2
)
517 gcc_assert (k1
!= NULL
);
518 gcc_assert (k2
!= NULL
);
519 gcc_assert (k1
!= reinterpret_cast<key_type
> (1));
520 gcc_assert (k2
!= reinterpret_cast<key_type
> (1));
524 /* Otherwise they must both be non-NULL. */
527 template <typename T
>
528 static inline void remove (T
&)
530 /* empty; the nodes are handled elsewhere. */
532 template <typename T
>
533 static inline void mark_deleted (T
&entry
)
535 entry
.m_key
= reinterpret_cast<key_type
> (1);
537 template <typename T
>
538 static inline void mark_empty (T
&entry
)
542 template <typename T
>
543 static inline bool is_deleted (const T
&entry
)
545 return entry
.m_key
== reinterpret_cast<key_type
> (1);
547 template <typename T
>
548 static inline bool is_empty (const T
&entry
)
550 return entry
.m_key
== NULL
;
552 static const bool empty_zero_p
= false;
555 /* Per-program_point data for an exploded_graph. */
557 struct per_program_point_data
559 per_program_point_data (const program_point
&key
)
560 : m_key (key
), m_excess_enodes (0)
563 const program_point m_key
;
564 auto_vec
<exploded_node
*> m_enodes
;
565 /* The number of attempts to create an enode for this point
566 after exceeding --param=analyzer-max-enodes-per-program-point. */
570 /* Traits class for storing per-program_point data within
571 an exploded_graph. */
573 struct eg_point_hash_map_traits
575 typedef const program_point
*key_type
;
576 typedef per_program_point_data
*value_type
;
577 typedef per_program_point_data
*compare_type
;
579 static inline hashval_t
hash (const key_type
&k
)
581 gcc_assert (k
!= NULL
);
582 gcc_assert (k
!= reinterpret_cast<key_type
> (1));
585 static inline bool equal_keys (const key_type
&k1
, const key_type
&k2
)
587 gcc_assert (k1
!= NULL
);
588 gcc_assert (k2
!= NULL
);
589 gcc_assert (k1
!= reinterpret_cast<key_type
> (1));
590 gcc_assert (k2
!= reinterpret_cast<key_type
> (1));
594 /* Otherwise they must both be non-NULL. */
597 template <typename T
>
598 static inline void remove (T
&)
600 /* empty; the nodes are handled elsewhere. */
602 template <typename T
>
603 static inline void mark_deleted (T
&entry
)
605 entry
.m_key
= reinterpret_cast<key_type
> (1);
607 template <typename T
>
608 static inline void mark_empty (T
&entry
)
612 template <typename T
>
613 static inline bool is_deleted (const T
&entry
)
615 return entry
.m_key
== reinterpret_cast<key_type
> (1);
617 template <typename T
>
618 static inline bool is_empty (const T
&entry
)
620 return entry
.m_key
== NULL
;
622 static const bool empty_zero_p
= false;
625 /* Data about a particular call_string within an exploded_graph. */
627 struct per_call_string_data
629 per_call_string_data (const call_string
&key
, int num_supernodes
)
630 : m_key (key
), m_stats (num_supernodes
)
633 const call_string
&m_key
;
637 /* Data about a particular function within an exploded_graph. */
639 struct per_function_data
641 per_function_data () {}
642 ~per_function_data ();
644 void add_call_summary (exploded_node
*node
);
646 auto_vec
<call_summary
*> m_summaries
;
650 /* The strongly connected components of a supergraph.
651 In particular, this allows us to compute a partial ordering
654 class strongly_connected_components
657 strongly_connected_components (const supergraph
&sg
, logger
*logger
);
659 int get_scc_id (int node_index
) const
661 return m_per_node
[node_index
].m_lowlink
;
666 json::array
*to_json () const;
672 : m_index (-1), m_lowlink (-1), m_on_stack (false)
680 void strong_connect (unsigned index
);
682 const supergraph
&m_sg
;
683 auto_vec
<unsigned> m_stack
;
684 auto_vec
<per_node_data
> m_per_node
;
687 /* The worklist of exploded_node instances that have been added to
688 an exploded_graph, but that haven't yet been processed to find
689 their successors (or warnings).
691 The enodes are stored in a priority queue, ordered by a topological
692 sort of the SCCs in the supergraph, so that enodes for the same
693 program_point should appear at the front of the queue together.
694 This allows for state-merging at CFG join-points, so that
695 sufficiently-similar enodes can be merged into one. */
700 worklist (const exploded_graph
&eg
, const analysis_plan
&plan
);
701 unsigned length () const;
702 exploded_node
*take_next ();
703 exploded_node
*peek_next ();
704 void add_node (exploded_node
*enode
);
705 int get_scc_id (const supernode
&snode
) const
707 return m_scc
.get_scc_id (snode
.m_index
);
710 json::object
*to_json () const;
716 key_t (const worklist
&w
, exploded_node
*enode
)
717 : m_worklist (w
), m_enode (enode
)
720 bool operator< (const key_t
&other
) const
722 return cmp (*this, other
) < 0;
725 bool operator== (const key_t
&other
) const
727 return cmp (*this, other
) == 0;
730 bool operator> (const key_t
&other
) const
732 return !(*this == other
|| *this < other
);
736 static int cmp (const key_t
&ka
, const key_t
&kb
);
738 int get_scc_id (const exploded_node
*enode
) const
740 const supernode
*snode
= enode
->get_supernode ();
743 return m_worklist
.m_scc
.get_scc_id (snode
->m_index
);
746 const worklist
&m_worklist
;
747 exploded_node
*m_enode
;
750 /* The order is important here: m_scc needs to stick around
751 until after m_queue has finished being cleaned up (the dtor
752 calls the ordering fns). */
753 strongly_connected_components m_scc
;
754 const analysis_plan
&m_plan
;
756 /* Priority queue, backed by a fibonacci_heap. */
757 typedef fibonacci_heap
<key_t
, exploded_node
> queue_t
;
761 /* An exploded_graph is a directed graph of unique <point, state> pairs.
762 It also has a worklist of nodes that are waiting for their successors
763 to be added to the graph. */
765 class exploded_graph
: public digraph
<eg_traits
>
768 typedef hash_map
<const call_string
*,
769 per_call_string_data
*> call_string_data_map_t
;
771 exploded_graph (const supergraph
&sg
, logger
*logger
,
772 const extrinsic_state
&ext_state
,
773 const state_purge_map
*purge_map
,
774 const analysis_plan
&plan
,
778 logger
*get_logger () const { return m_logger
.get_logger (); }
780 const supergraph
&get_supergraph () const { return m_sg
; }
781 const extrinsic_state
&get_ext_state () const { return m_ext_state
; }
782 engine
*get_engine () const { return m_ext_state
.get_engine (); }
783 const state_purge_map
*get_purge_map () const { return m_purge_map
; }
784 const analysis_plan
&get_analysis_plan () const { return m_plan
; }
786 exploded_node
*get_origin () const { return m_origin
; }
788 exploded_node
*add_function_entry (function
*fun
);
790 void build_initial_worklist ();
791 void process_worklist ();
792 bool maybe_process_run_of_before_supernode_enodes (exploded_node
*node
);
793 void process_node (exploded_node
*node
);
795 bool maybe_create_dynamic_call (const gcall
*call
,
798 program_state next_state
,
799 program_point
&next_point
,
800 uncertainty_t
*uncertainty
,
803 exploded_node
*get_or_create_node (const program_point
&point
,
804 const program_state
&state
,
805 exploded_node
*enode_for_diag
);
806 exploded_edge
*add_edge (exploded_node
*src
, exploded_node
*dest
,
807 const superedge
*sedge
,
808 std::unique_ptr
<custom_edge_info
> custom
= NULL
);
810 per_program_point_data
*
811 get_or_create_per_program_point_data (const program_point
&);
812 per_program_point_data
*
813 get_per_program_point_data (const program_point
&) const;
815 per_call_string_data
*
816 get_or_create_per_call_string_data (const call_string
&);
819 get_or_create_per_function_data (function
*);
820 per_function_data
*get_per_function_data (function
*) const;
822 void save_diagnostic (const state_machine
&sm
,
823 const exploded_node
*enode
,
824 const supernode
*node
, const gimple
*stmt
,
826 tree var
, state_machine::state_t state
,
827 pending_diagnostic
*d
);
829 diagnostic_manager
&get_diagnostic_manager ()
831 return m_diagnostic_manager
;
833 const diagnostic_manager
&get_diagnostic_manager () const
835 return m_diagnostic_manager
;
838 stats
*get_global_stats () { return &m_global_stats
; }
839 stats
*get_or_create_function_stats (function
*fn
);
840 void log_stats () const;
841 void dump_stats (FILE *) const;
842 void dump_states_for_supernode (FILE *, const supernode
*snode
) const;
843 void dump_exploded_nodes () const;
845 json::object
*to_json () const;
847 exploded_node
*get_node_by_index (int idx
) const;
849 const call_string_data_map_t
*get_per_call_string_data () const
850 { return &m_per_call_string_data
; }
852 int get_scc_id (const supernode
&node
) const
854 return m_worklist
.get_scc_id (node
);
857 void on_escaped_function (tree fndecl
);
859 /* In infinite-recursion.cc */
860 void detect_infinite_recursion (exploded_node
*enode
);
861 exploded_node
*find_previous_entry_to (function
*top_of_stack_fun
,
862 exploded_node
*enode
) const;
865 void print_bar_charts (pretty_printer
*pp
) const;
867 DISABLE_COPY_AND_ASSIGN (exploded_graph
);
869 const supergraph
&m_sg
;
873 /* Map from point/state to exploded node.
874 To avoid duplication we store point_and_state
875 *pointers* as keys, rather than point_and_state, using the
876 instance from within the exploded_node, with a custom hasher. */
877 typedef hash_map
<const point_and_state
*, exploded_node
*,
878 eg_hash_map_traits
> map_t
;
879 map_t m_point_and_state_to_node
;
881 /* Map from program_point to per-program_point data. */
882 typedef hash_map
<const program_point
*, per_program_point_data
*,
883 eg_point_hash_map_traits
> point_map_t
;
884 point_map_t m_per_point_data
;
888 exploded_node
*m_origin
;
890 const extrinsic_state
&m_ext_state
;
892 const state_purge_map
*const m_purge_map
;
894 const analysis_plan
&m_plan
;
896 typedef hash_map
<function
*, per_function_data
*> per_function_data_t
;
897 per_function_data_t m_per_function_data
;
899 diagnostic_manager m_diagnostic_manager
;
902 stats m_global_stats
;
903 typedef ordered_hash_map
<function
*, stats
*> function_stat_map_t
;
904 function_stat_map_t m_per_function_stats
;
905 stats m_functionless_stats
;
907 call_string_data_map_t m_per_call_string_data
;
909 auto_vec
<int> m_PK_AFTER_SUPERNODE_per_snode
;
911 /* Functions with a top-level enode, to make add_function_entry
912 be idempotent, for use in handling callbacks. */
913 hash_set
<function
*> m_functions_with_enodes
;
916 /* A path within an exploded_graph: a sequence of edges. */
921 exploded_path () : m_edges () {}
922 exploded_path (const exploded_path
&other
);
924 unsigned length () const { return m_edges
.length (); }
926 bool find_stmt_backwards (const gimple
*search_stmt
,
929 exploded_node
*get_final_enode () const;
931 void dump_to_pp (pretty_printer
*pp
,
932 const extrinsic_state
*ext_state
) const;
933 void dump (FILE *fp
, const extrinsic_state
*ext_state
) const;
934 void dump (const extrinsic_state
*ext_state
= NULL
) const;
935 void dump_to_file (const char *filename
,
936 const extrinsic_state
&ext_state
) const;
938 bool feasible_p (logger
*logger
, std::unique_ptr
<feasibility_problem
> *out
,
939 engine
*eng
, const exploded_graph
*eg
) const;
941 auto_vec
<const exploded_edge
*> m_edges
;
944 /* A reason why a particular exploded_path is infeasible. */
946 class feasibility_problem
949 feasibility_problem (unsigned eedge_idx
,
950 const exploded_edge
&eedge
,
951 const gimple
*last_stmt
,
952 std::unique_ptr
<rejected_constraint
> rc
)
953 : m_eedge_idx (eedge_idx
), m_eedge (eedge
),
954 m_last_stmt (last_stmt
), m_rc (std::move (rc
))
957 void dump_to_pp (pretty_printer
*pp
) const;
959 unsigned m_eedge_idx
;
960 const exploded_edge
&m_eedge
;
961 const gimple
*m_last_stmt
;
962 std::unique_ptr
<rejected_constraint
> m_rc
;
965 /* A class for capturing the state of a node when checking a path
966 through the exploded_graph for feasibility. */
968 class feasibility_state
971 feasibility_state (region_model_manager
*manager
,
972 const supergraph
&sg
);
973 feasibility_state (const feasibility_state
&other
);
975 bool maybe_update_for_edge (logger
*logger
,
976 const exploded_edge
*eedge
,
977 std::unique_ptr
<rejected_constraint
> *out_rc
);
978 void update_for_stmt (const gimple
*stmt
);
980 const region_model
&get_model () const { return m_model
; }
981 const auto_sbitmap
&get_snodes_visited () const { return m_snodes_visited
; }
983 void dump_to_pp (pretty_printer
*pp
, bool simple
, bool multiline
) const;
986 region_model m_model
;
987 auto_sbitmap m_snodes_visited
;
990 /* Finding the shortest exploded_path within an exploded_graph. */
992 typedef shortest_paths
<eg_traits
, exploded_path
> shortest_exploded_paths
;
994 /* Abstract base class for use when passing NULL as the stmt for
995 a possible warning, allowing the choice of stmt to be deferred
996 until after we have an emission path (and know we're emitting a
1002 virtual ~stmt_finder () {}
1003 virtual std::unique_ptr
<stmt_finder
> clone () const = 0;
1004 virtual const gimple
*find_stmt (const exploded_path
&epath
) = 0;
1007 // TODO: split the above up?
1011 #endif /* GCC_ANALYZER_EXPLODED_GRAPH_H */