1 /* Classes for managing a directed graph of <point, state> pairs.
2 Copyright (C) 2019-2022 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
26 /* Concrete implementation of region_model_context, wiring it up to the
27 rest of the analysis engine. */
29 class impl_region_model_context
: public region_model_context
32 impl_region_model_context (exploded_graph
&eg
,
33 exploded_node
*enode_for_diag
,
35 /* TODO: should we be getting the ECs from the
36 old state, rather than the new? */
37 const program_state
*old_state
,
38 program_state
*new_state
,
39 uncertainty_t
*uncertainty
,
40 path_context
*path_ctxt
,
43 stmt_finder
*stmt_finder
= NULL
);
45 impl_region_model_context (program_state
*state
,
46 const extrinsic_state
&ext_state
,
47 uncertainty_t
*uncertainty
,
48 logger
*logger
= NULL
);
50 bool warn (pending_diagnostic
*d
) FINAL OVERRIDE
;
51 void add_note (pending_note
*pn
) FINAL OVERRIDE
;
52 void on_svalue_leak (const svalue
*) OVERRIDE
;
53 void on_liveness_change (const svalue_set
&live_svalues
,
54 const region_model
*model
) FINAL OVERRIDE
;
55 logger
*get_logger () FINAL OVERRIDE
57 return m_logger
.get_logger ();
60 void on_state_leak (const state_machine
&sm
,
62 state_machine::state_t state
);
64 void on_condition (const svalue
*lhs
,
66 const svalue
*rhs
) FINAL OVERRIDE
;
68 void on_unknown_change (const svalue
*sval
, bool is_mutable
) FINAL OVERRIDE
;
70 void on_phi (const gphi
*phi
, tree rhs
) FINAL OVERRIDE
;
72 void on_unexpected_tree_code (tree t
,
73 const dump_location_t
&loc
) FINAL OVERRIDE
;
75 void on_escaped_function (tree fndecl
) FINAL OVERRIDE
;
77 uncertainty_t
*get_uncertainty () FINAL OVERRIDE
;
79 void purge_state_involving (const svalue
*sval
) FINAL OVERRIDE
;
81 void bifurcate (custom_edge_info
*info
) FINAL OVERRIDE
;
82 void terminate_path () FINAL OVERRIDE
;
83 const extrinsic_state
*get_ext_state () const FINAL OVERRIDE
87 bool get_malloc_map (sm_state_map
**out_smap
,
88 const state_machine
**out_sm
,
89 unsigned *out_sm_idx
) FINAL OVERRIDE
;
90 bool get_taint_map (sm_state_map
**out_smap
,
91 const state_machine
**out_sm
,
92 unsigned *out_sm_idx
) FINAL OVERRIDE
;
94 const gimple
*get_stmt () const OVERRIDE
{ return m_stmt
; }
98 exploded_node
*m_enode_for_diag
;
99 const program_state
*m_old_state
;
100 program_state
*m_new_state
;
101 const gimple
*m_stmt
;
102 stmt_finder
*m_stmt_finder
;
103 const extrinsic_state
&m_ext_state
;
104 uncertainty_t
*m_uncertainty
;
105 path_context
*m_path_ctxt
;
108 /* A <program_point, program_state> pair, used internally by
109 exploded_node as its immutable data, and as a key for identifying
110 exploded_nodes we've already seen in the graph. */
112 class point_and_state
115 point_and_state (const program_point
&point
,
116 const program_state
&state
)
119 m_hash (m_point
.hash () ^ m_state
.hash ())
121 /* We shouldn't be building point_and_states and thus exploded_nodes
122 for states that aren't valid. */
123 gcc_assert (state
.m_valid
);
126 hashval_t
hash () const
130 bool operator== (const point_and_state
&other
) const
132 return m_point
== other
.m_point
&& m_state
== other
.m_state
;
135 const program_point
&get_point () const { return m_point
; }
136 const program_state
&get_state () const { return m_state
; }
138 void set_state (const program_state
&state
)
141 m_hash
= m_point
.hash () ^ m_state
.hash ();
144 void validate (const extrinsic_state
&ext_state
) const;
147 program_point m_point
;
148 program_state m_state
;
152 /* A traits class for exploded graphs and their nodes and edges. */
156 typedef exploded_node node_t
;
157 typedef exploded_edge edge_t
;
158 typedef exploded_graph graph_t
;
161 dump_args_t (const exploded_graph
&eg
) : m_eg (eg
) {}
163 bool show_enode_details_p (const exploded_node
&enode
) const;
166 dump_extra_info (const exploded_node
*, pretty_printer
*) const {}
168 const exploded_graph
&m_eg
;
170 typedef exploded_cluster cluster_t
;
173 /* An exploded_node is a unique, immutable <point, state> pair within the
175 Each exploded_node has a unique index within the graph
176 (for ease of debugging). */
178 class exploded_node
: public dnode
<eg_traits
>
181 /* Has this enode had exploded_graph::process_node called on it?
182 This allows us to distinguish enodes that were merged during
183 worklist-handling, and thus never had process_node called on them
184 (in favor of processing the merged node). */
187 /* Node is in the worklist. */
190 /* Node has had exploded_graph::process_node called on it. */
193 /* Node was left unprocessed due to merger; it won't have had
194 exploded_graph::process_node called on it. */
197 /* Node was processed by maybe_process_run_of_before_supernode_enodes. */
200 static const char * status_to_str (enum status s
);
202 exploded_node (const point_and_state
&ps
, int index
);
204 hashval_t
hash () const { return m_ps
.hash (); }
206 const char * get_dot_fillcolor () const;
207 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
)
208 const FINAL OVERRIDE
;
209 void dump_dot_id (pretty_printer
*pp
) const;
211 void dump_to_pp (pretty_printer
*pp
, const extrinsic_state
&ext_state
) const;
212 void dump (FILE *fp
, const extrinsic_state
&ext_state
) const;
213 void dump (const extrinsic_state
&ext_state
) const;
215 void dump_processed_stmts (pretty_printer
*pp
) const;
216 void dump_saved_diagnostics (pretty_printer
*pp
) const;
218 json::object
*to_json (const extrinsic_state
&ext_state
) const;
220 /* The result of on_stmt. */
223 on_stmt_flags () : m_terminate_path (false)
226 static on_stmt_flags
terminate_path ()
228 return on_stmt_flags (true);
231 /* Should we stop analyzing this path (on_stmt may have already
232 added nodes/edges, e.g. when handling longjmp). */
233 bool m_terminate_path
: 1;
236 on_stmt_flags (bool terminate_path
)
237 : m_terminate_path (terminate_path
)
241 on_stmt_flags
on_stmt (exploded_graph
&eg
,
242 const supernode
*snode
,
244 program_state
*state
,
245 uncertainty_t
*uncertainty
,
246 path_context
*path_ctxt
);
247 void on_stmt_pre (exploded_graph
&eg
,
249 program_state
*state
,
250 bool *out_terminate_path
,
251 bool *out_unknown_side_effects
,
252 region_model_context
*ctxt
);
253 void on_stmt_post (const gimple
*stmt
,
254 program_state
*state
,
255 bool unknown_side_effects
,
256 region_model_context
*ctxt
);
258 bool on_edge (exploded_graph
&eg
,
259 const superedge
*succ
,
260 program_point
*next_point
,
261 program_state
*next_state
,
262 uncertainty_t
*uncertainty
);
263 void on_longjmp (exploded_graph
&eg
,
265 program_state
*new_state
,
266 region_model_context
*ctxt
);
268 void detect_leaks (exploded_graph
&eg
);
270 const program_point
&get_point () const { return m_ps
.get_point (); }
271 const supernode
*get_supernode () const
273 return get_point ().get_supernode ();
275 function
*get_function () const
277 return get_point ().get_function ();
279 int get_stack_depth () const
281 return get_point ().get_stack_depth ();
283 const gimple
*get_stmt () const { return get_point ().get_stmt (); }
284 const gimple
*get_processed_stmt (unsigned idx
) const;
286 const program_state
&get_state () const { return m_ps
.get_state (); }
288 const point_and_state
*get_ps_key () const { return &m_ps
; }
289 const program_point
*get_point_key () const { return &m_ps
.get_point (); }
291 void dump_succs_and_preds (FILE *outf
) const;
293 enum status
get_status () const { return m_status
; }
294 void set_status (enum status status
)
296 gcc_assert (m_status
== STATUS_WORKLIST
);
300 void add_diagnostic (const saved_diagnostic
*sd
)
302 m_saved_diagnostics
.safe_push (sd
);
304 unsigned get_num_diagnostics () const
306 return m_saved_diagnostics
.length ();
308 const saved_diagnostic
*get_saved_diagnostic (unsigned idx
) const
310 return m_saved_diagnostics
[idx
];
314 DISABLE_COPY_AND_ASSIGN (exploded_node
);
316 /* The <program_point, program_state> pair. This is const, as it
317 is immutable once the exploded_node has been created. */
318 const point_and_state m_ps
;
320 enum status m_status
;
322 /* The saved_diagnostics at this enode, borrowed from the
323 diagnostic_manager. */
324 auto_vec
<const saved_diagnostic
*> m_saved_diagnostics
;
327 /* The index of this exploded_node. */
330 /* The number of stmts that were processed when process_node was
331 called on this enode. */
332 unsigned m_num_processed_stmts
;
335 /* An edge within the exploded graph.
336 Some exploded_edges have an underlying superedge; others don't. */
338 class exploded_edge
: public dedge
<eg_traits
>
341 exploded_edge (exploded_node
*src
, exploded_node
*dest
,
342 const superedge
*sedge
,
343 custom_edge_info
*custom_info
);
345 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
)
346 const FINAL OVERRIDE
;
347 void dump_dot_label (pretty_printer
*pp
) const;
349 json::object
*to_json () const;
352 const superedge
*const m_sedge
;
354 /* NULL for most edges; will be non-NULL for special cases
355 such as an unwind from a longjmp to a setjmp, or when
356 a signal is delivered to a signal-handler.
358 Owned by this class. */
359 custom_edge_info
*m_custom_info
;
362 DISABLE_COPY_AND_ASSIGN (exploded_edge
);
365 /* Extra data for an exploded_edge that represents dynamic call info ( calls
366 that doesn't have an underlying superedge representing the call ). */
368 class dynamic_call_info_t
: public custom_edge_info
371 dynamic_call_info_t (const gcall
*dynamic_call
,
372 const bool is_returning_call
= false)
373 : m_dynamic_call (dynamic_call
),
374 m_is_returning_call (is_returning_call
)
377 void print (pretty_printer
*pp
) const FINAL OVERRIDE
379 if (m_is_returning_call
)
380 pp_string (pp
, "dynamic_return");
382 pp_string (pp
, "dynamic_call");
385 bool update_model (region_model
*model
,
386 const exploded_edge
*eedge
,
387 region_model_context
*ctxt
) const FINAL OVERRIDE
;
389 void add_events_to_path (checker_path
*emission_path
,
390 const exploded_edge
&eedge
) const FINAL OVERRIDE
;
392 const gcall
*m_dynamic_call
;
393 const bool m_is_returning_call
;
397 /* Extra data for an exploded_edge that represents a rewind from a
398 longjmp to a setjmp (or from a siglongjmp to a sigsetjmp). */
400 class rewind_info_t
: public custom_edge_info
403 rewind_info_t (const setjmp_record
&setjmp_record
,
404 const gcall
*longjmp_call
)
405 : m_setjmp_record (setjmp_record
),
406 m_longjmp_call (longjmp_call
)
409 void print (pretty_printer
*pp
) const FINAL OVERRIDE
411 pp_string (pp
, "rewind");
414 bool update_model (region_model
*model
,
415 const exploded_edge
*eedge
,
416 region_model_context
*ctxt
) const FINAL OVERRIDE
;
418 void add_events_to_path (checker_path
*emission_path
,
419 const exploded_edge
&eedge
) const FINAL OVERRIDE
;
421 const program_point
&get_setjmp_point () const
423 const program_point
&origin_point
= get_enode_origin ()->get_point ();
425 /* "origin_point" ought to be before the call to "setjmp". */
426 gcc_assert (origin_point
.get_kind () == PK_BEFORE_STMT
);
428 /* TODO: assert that it's the final stmt in its supernode. */
433 const gcall
*get_setjmp_call () const
435 return m_setjmp_record
.m_setjmp_call
;
438 const gcall
*get_longjmp_call () const
440 return m_longjmp_call
;
443 const exploded_node
*get_enode_origin () const
445 return m_setjmp_record
.m_enode
;
449 setjmp_record m_setjmp_record
;
450 const gcall
*m_longjmp_call
;
453 /* Statistics about aspects of an exploded_graph. */
457 stats (int num_supernodes
);
458 void log (logger
*logger
) const;
459 void dump (FILE *out
) const;
461 int get_total_enodes () const;
463 int m_num_nodes
[NUM_POINT_KINDS
];
464 int m_node_reuse_count
;
465 int m_node_reuse_after_merge_count
;
466 int m_num_supernodes
;
469 /* Traits class for ensuring uniqueness of point_and_state data within
470 an exploded_graph. */
472 struct eg_hash_map_traits
474 typedef const point_and_state
*key_type
;
475 typedef exploded_node
*value_type
;
476 typedef exploded_node
*compare_type
;
478 static inline hashval_t
hash (const key_type
&k
)
480 gcc_assert (k
!= NULL
);
481 gcc_assert (k
!= reinterpret_cast<key_type
> (1));
484 static inline bool equal_keys (const key_type
&k1
, const key_type
&k2
)
486 gcc_assert (k1
!= NULL
);
487 gcc_assert (k2
!= NULL
);
488 gcc_assert (k1
!= reinterpret_cast<key_type
> (1));
489 gcc_assert (k2
!= reinterpret_cast<key_type
> (1));
493 /* Otherwise they must both be non-NULL. */
496 template <typename T
>
497 static inline void remove (T
&)
499 /* empty; the nodes are handled elsewhere. */
501 template <typename T
>
502 static inline void mark_deleted (T
&entry
)
504 entry
.m_key
= reinterpret_cast<key_type
> (1);
506 template <typename T
>
507 static inline void mark_empty (T
&entry
)
511 template <typename T
>
512 static inline bool is_deleted (const T
&entry
)
514 return entry
.m_key
== reinterpret_cast<key_type
> (1);
516 template <typename T
>
517 static inline bool is_empty (const T
&entry
)
519 return entry
.m_key
== NULL
;
521 static const bool empty_zero_p
= false;
524 /* Per-program_point data for an exploded_graph. */
526 struct per_program_point_data
528 per_program_point_data (const program_point
&key
)
529 : m_key (key
), m_excess_enodes (0)
532 const program_point m_key
;
533 auto_vec
<exploded_node
*> m_enodes
;
534 /* The number of attempts to create an enode for this point
535 after exceeding --param=analyzer-max-enodes-per-program-point. */
539 /* Traits class for storing per-program_point data within
540 an exploded_graph. */
542 struct eg_point_hash_map_traits
544 typedef const program_point
*key_type
;
545 typedef per_program_point_data
*value_type
;
546 typedef per_program_point_data
*compare_type
;
548 static inline hashval_t
hash (const key_type
&k
)
550 gcc_assert (k
!= NULL
);
551 gcc_assert (k
!= reinterpret_cast<key_type
> (1));
554 static inline bool equal_keys (const key_type
&k1
, const key_type
&k2
)
556 gcc_assert (k1
!= NULL
);
557 gcc_assert (k2
!= NULL
);
558 gcc_assert (k1
!= reinterpret_cast<key_type
> (1));
559 gcc_assert (k2
!= reinterpret_cast<key_type
> (1));
563 /* Otherwise they must both be non-NULL. */
566 template <typename T
>
567 static inline void remove (T
&)
569 /* empty; the nodes are handled elsewhere. */
571 template <typename T
>
572 static inline void mark_deleted (T
&entry
)
574 entry
.m_key
= reinterpret_cast<key_type
> (1);
576 template <typename T
>
577 static inline void mark_empty (T
&entry
)
581 template <typename T
>
582 static inline bool is_deleted (const T
&entry
)
584 return entry
.m_key
== reinterpret_cast<key_type
> (1);
586 template <typename T
>
587 static inline bool is_empty (const T
&entry
)
589 return entry
.m_key
== NULL
;
591 static const bool empty_zero_p
= false;
594 /* Data about a particular call_string within an exploded_graph. */
596 struct per_call_string_data
598 per_call_string_data (const call_string
&key
, int num_supernodes
)
599 : m_key (key
), m_stats (num_supernodes
)
602 const call_string m_key
;
606 /* Traits class for storing per-call_string data within
607 an exploded_graph. */
609 struct eg_call_string_hash_map_traits
611 typedef const call_string
*key_type
;
612 typedef per_call_string_data
*value_type
;
613 typedef per_call_string_data
*compare_type
;
615 static inline hashval_t
hash (const key_type
&k
)
617 gcc_assert (k
!= NULL
);
618 gcc_assert (k
!= reinterpret_cast<key_type
> (1));
621 static inline bool equal_keys (const key_type
&k1
, const key_type
&k2
)
623 gcc_assert (k1
!= NULL
);
624 gcc_assert (k2
!= NULL
);
625 gcc_assert (k1
!= reinterpret_cast<key_type
> (1));
626 gcc_assert (k2
!= reinterpret_cast<key_type
> (1));
630 /* Otherwise they must both be non-NULL. */
633 template <typename T
>
634 static inline void remove (T
&)
636 /* empty; the nodes are handled elsewhere. */
638 template <typename T
>
639 static inline void mark_deleted (T
&entry
)
641 entry
.m_key
= reinterpret_cast<key_type
> (1);
643 template <typename T
>
644 static inline void mark_empty (T
&entry
)
648 template <typename T
>
649 static inline bool is_deleted (const T
&entry
)
651 return entry
.m_key
== reinterpret_cast<key_type
> (1);
653 template <typename T
>
654 static inline bool is_empty (const T
&entry
)
656 return entry
.m_key
== NULL
;
658 static const bool empty_zero_p
= false;
661 /* Data about a particular function within an exploded_graph. */
663 struct per_function_data
665 per_function_data () {}
667 void add_call_summary (exploded_node
*node
)
669 m_summaries
.safe_push (node
);
672 auto_vec
<exploded_node
*> m_summaries
;
676 /* The strongly connected components of a supergraph.
677 In particular, this allows us to compute a partial ordering
680 class strongly_connected_components
683 strongly_connected_components (const supergraph
&sg
, logger
*logger
);
685 int get_scc_id (int node_index
) const
687 return m_per_node
[node_index
].m_lowlink
;
692 json::array
*to_json () const;
698 : m_index (-1), m_lowlink (-1), m_on_stack (false)
706 void strong_connect (unsigned index
);
708 const supergraph
&m_sg
;
709 auto_vec
<unsigned> m_stack
;
710 auto_vec
<per_node_data
> m_per_node
;
713 /* The worklist of exploded_node instances that have been added to
714 an exploded_graph, but that haven't yet been processed to find
715 their successors (or warnings).
717 The enodes are stored in a priority queue, ordered by a topological
718 sort of the SCCs in the supergraph, so that enodes for the same
719 program_point should appear at the front of the queue together.
720 This allows for state-merging at CFG join-points, so that
721 sufficiently-similar enodes can be merged into one. */
726 worklist (const exploded_graph
&eg
, const analysis_plan
&plan
);
727 unsigned length () const;
728 exploded_node
*take_next ();
729 exploded_node
*peek_next ();
730 void add_node (exploded_node
*enode
);
731 int get_scc_id (const supernode
&snode
) const
733 return m_scc
.get_scc_id (snode
.m_index
);
736 json::object
*to_json () const;
742 key_t (const worklist
&w
, exploded_node
*enode
)
743 : m_worklist (w
), m_enode (enode
)
746 bool operator< (const key_t
&other
) const
748 return cmp (*this, other
) < 0;
751 bool operator== (const key_t
&other
) const
753 return cmp (*this, other
) == 0;
756 bool operator> (const key_t
&other
) const
758 return !(*this == other
|| *this < other
);
762 static int cmp (const key_t
&ka
, const key_t
&kb
);
764 int get_scc_id (const exploded_node
*enode
) const
766 const supernode
*snode
= enode
->get_supernode ();
769 return m_worklist
.m_scc
.get_scc_id (snode
->m_index
);
772 const worklist
&m_worklist
;
773 exploded_node
*m_enode
;
776 /* The order is important here: m_scc needs to stick around
777 until after m_queue has finished being cleaned up (the dtor
778 calls the ordering fns). */
779 strongly_connected_components m_scc
;
780 const analysis_plan
&m_plan
;
782 /* Priority queue, backed by a fibonacci_heap. */
783 typedef fibonacci_heap
<key_t
, exploded_node
> queue_t
;
787 /* An exploded_graph is a directed graph of unique <point, state> pairs.
788 It also has a worklist of nodes that are waiting for their successors
789 to be added to the graph. */
791 class exploded_graph
: public digraph
<eg_traits
>
794 typedef hash_map
<const call_string
*, per_call_string_data
*,
795 eg_call_string_hash_map_traits
> call_string_data_map_t
;
797 exploded_graph (const supergraph
&sg
, logger
*logger
,
798 const extrinsic_state
&ext_state
,
799 const state_purge_map
*purge_map
,
800 const analysis_plan
&plan
,
804 logger
*get_logger () const { return m_logger
.get_logger (); }
806 const supergraph
&get_supergraph () const { return m_sg
; }
807 const extrinsic_state
&get_ext_state () const { return m_ext_state
; }
808 engine
*get_engine () const { return m_ext_state
.get_engine (); }
809 const state_purge_map
*get_purge_map () const { return m_purge_map
; }
810 const analysis_plan
&get_analysis_plan () const { return m_plan
; }
812 exploded_node
*get_origin () const { return m_origin
; }
814 exploded_node
*add_function_entry (function
*fun
);
816 void build_initial_worklist ();
817 void process_worklist ();
818 bool maybe_process_run_of_before_supernode_enodes (exploded_node
*node
);
819 void process_node (exploded_node
*node
);
821 bool maybe_create_dynamic_call (const gcall
*call
,
824 program_state next_state
,
825 program_point
&next_point
,
826 uncertainty_t
*uncertainty
,
829 exploded_node
*get_or_create_node (const program_point
&point
,
830 const program_state
&state
,
831 exploded_node
*enode_for_diag
);
832 exploded_edge
*add_edge (exploded_node
*src
, exploded_node
*dest
,
833 const superedge
*sedge
,
834 custom_edge_info
*custom
= NULL
);
836 per_program_point_data
*
837 get_or_create_per_program_point_data (const program_point
&);
838 per_program_point_data
*
839 get_per_program_point_data (const program_point
&) const;
841 per_call_string_data
*
842 get_or_create_per_call_string_data (const call_string
&);
845 get_or_create_per_function_data (function
*);
846 per_function_data
*get_per_function_data (function
*) const;
848 void save_diagnostic (const state_machine
&sm
,
849 const exploded_node
*enode
,
850 const supernode
*node
, const gimple
*stmt
,
852 tree var
, state_machine::state_t state
,
853 pending_diagnostic
*d
);
855 diagnostic_manager
&get_diagnostic_manager ()
857 return m_diagnostic_manager
;
859 const diagnostic_manager
&get_diagnostic_manager () const
861 return m_diagnostic_manager
;
864 stats
*get_global_stats () { return &m_global_stats
; }
865 stats
*get_or_create_function_stats (function
*fn
);
866 void log_stats () const;
867 void dump_stats (FILE *) const;
868 void dump_states_for_supernode (FILE *, const supernode
*snode
) const;
869 void dump_exploded_nodes () const;
871 json::object
*to_json () const;
873 exploded_node
*get_node_by_index (int idx
) const;
875 const call_string_data_map_t
*get_per_call_string_data () const
876 { return &m_per_call_string_data
; }
878 int get_scc_id (const supernode
&node
) const
880 return m_worklist
.get_scc_id (node
);
883 void on_escaped_function (tree fndecl
);
886 void print_bar_charts (pretty_printer
*pp
) const;
888 DISABLE_COPY_AND_ASSIGN (exploded_graph
);
890 const supergraph
&m_sg
;
894 /* Map from point/state to exploded node.
895 To avoid duplication we store point_and_state
896 *pointers* as keys, rather than point_and_state, using the
897 instance from within the exploded_node, with a custom hasher. */
898 typedef hash_map
<const point_and_state
*, exploded_node
*,
899 eg_hash_map_traits
> map_t
;
900 map_t m_point_and_state_to_node
;
902 /* Map from program_point to per-program_point data. */
903 typedef hash_map
<const program_point
*, per_program_point_data
*,
904 eg_point_hash_map_traits
> point_map_t
;
905 point_map_t m_per_point_data
;
909 exploded_node
*m_origin
;
911 const extrinsic_state
&m_ext_state
;
913 const state_purge_map
*const m_purge_map
;
915 const analysis_plan
&m_plan
;
917 typedef hash_map
<function
*, per_function_data
*> per_function_data_t
;
918 per_function_data_t m_per_function_data
;
920 diagnostic_manager m_diagnostic_manager
;
923 stats m_global_stats
;
924 typedef ordered_hash_map
<function
*, stats
*> function_stat_map_t
;
925 function_stat_map_t m_per_function_stats
;
926 stats m_functionless_stats
;
928 call_string_data_map_t m_per_call_string_data
;
930 auto_vec
<int> m_PK_AFTER_SUPERNODE_per_snode
;
932 /* Functions with a top-level enode, to make add_function_entry
933 be idempotent, for use in handling callbacks. */
934 hash_set
<function
*> m_functions_with_enodes
;
937 /* A path within an exploded_graph: a sequence of edges. */
942 exploded_path () : m_edges () {}
943 exploded_path (const exploded_path
&other
);
945 unsigned length () const { return m_edges
.length (); }
947 bool find_stmt_backwards (const gimple
*search_stmt
,
950 exploded_node
*get_final_enode () const;
952 void dump_to_pp (pretty_printer
*pp
,
953 const extrinsic_state
*ext_state
) const;
954 void dump (FILE *fp
, const extrinsic_state
*ext_state
) const;
955 void dump (const extrinsic_state
*ext_state
= NULL
) const;
956 void dump_to_file (const char *filename
,
957 const extrinsic_state
&ext_state
) const;
959 bool feasible_p (logger
*logger
, feasibility_problem
**out
,
960 engine
*eng
, const exploded_graph
*eg
) const;
962 auto_vec
<const exploded_edge
*> m_edges
;
965 /* A reason why a particular exploded_path is infeasible. */
967 class feasibility_problem
970 feasibility_problem (unsigned eedge_idx
,
971 const exploded_edge
&eedge
,
972 const gimple
*last_stmt
,
973 rejected_constraint
*rc
)
974 : m_eedge_idx (eedge_idx
), m_eedge (eedge
),
975 m_last_stmt (last_stmt
), m_rc (rc
)
977 ~feasibility_problem () { delete m_rc
; }
979 void dump_to_pp (pretty_printer
*pp
) const;
981 unsigned m_eedge_idx
;
982 const exploded_edge
&m_eedge
;
983 const gimple
*m_last_stmt
;
984 rejected_constraint
*m_rc
;
987 /* A class for capturing the state of a node when checking a path
988 through the exploded_graph for feasibility. */
990 class feasibility_state
993 feasibility_state (region_model_manager
*manager
,
994 const supergraph
&sg
);
995 feasibility_state (const feasibility_state
&other
);
997 bool maybe_update_for_edge (logger
*logger
,
998 const exploded_edge
*eedge
,
999 rejected_constraint
**out_rc
);
1001 const region_model
&get_model () const { return m_model
; }
1002 const auto_sbitmap
&get_snodes_visited () const { return m_snodes_visited
; }
1005 region_model m_model
;
1006 auto_sbitmap m_snodes_visited
;
1009 /* Finding the shortest exploded_path within an exploded_graph. */
1011 typedef shortest_paths
<eg_traits
, exploded_path
> shortest_exploded_paths
;
1013 /* Abstract base class for use when passing NULL as the stmt for
1014 a possible warning, allowing the choice of stmt to be deferred
1015 until after we have an emission path (and know we're emitting a
1021 virtual ~stmt_finder () {}
1022 virtual stmt_finder
*clone () const = 0;
1023 virtual const gimple
*find_stmt (const exploded_path
&epath
) = 0;
1026 // TODO: split the above up?
1030 #endif /* GCC_ANALYZER_EXPLODED_GRAPH_H */