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"
30#include "analyzer/program-state.h"
31#include "analyzer/diagnostic-manager.h"
32
33namespace ana {
34
35/* Concrete implementation of region_model_context, wiring it up to the
36 rest of the analysis engine. */
37
38class impl_region_model_context : public region_model_context
39{
40 public:
41 impl_region_model_context (exploded_graph &eg,
42 exploded_node *enode_for_diag,
43
44 /* TODO: should we be getting the ECs from the
45 old state, rather than the new? */
46 const program_state *old_state,
47 program_state *new_state,
48 uncertainty_t *uncertainty,
49 path_context *path_ctxt,
50
51 const gimple *stmt,
52 stmt_finder *stmt_finder = NULL,
53
54 bool *out_could_have_done_work = nullptr);
55
56 impl_region_model_context (program_state *state,
57 const extrinsic_state &ext_state,
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
73 void on_state_leak (const state_machine &sm,
74 const svalue *sval,
75 state_machine::state_t state);
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
90 void on_unexpected_tree_code (tree t,
91 const dump_location_t &loc) final override;
92
93 void on_escaped_function (tree fndecl) final override;
94
95 uncertainty_t *get_uncertainty () final override;
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; }
117 void on_unusable_in_infinite_loop () override {}
118
119 exploded_graph *m_eg;
120 log_user m_logger;
121 exploded_node *m_enode_for_diag;
122 const program_state *m_old_state;
123 program_state *m_new_state;
124 const gimple *m_stmt;
125 stmt_finder *m_stmt_finder;
126 const extrinsic_state &m_ext_state;
127 uncertainty_t *m_uncertainty;
128 path_context *m_path_ctxt;
129 bool *m_out_could_have_done_work;
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
136class point_and_state
137{
138public:
139 point_and_state (const program_point &point,
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
162 void set_state (const program_state &state)
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:
171 program_point m_point;
172 program_state m_state;
173 hashval_t m_hash;
174};
175
176/* A traits class for exploded graphs and their nodes and edges. */
177
178struct eg_traits
179{
180 typedef exploded_node node_t;
181 typedef exploded_edge edge_t;
182 typedef exploded_graph graph_t;
183 struct dump_args_t
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
190 dump_extra_info (const exploded_node *, pretty_printer *) const {}
191
192 const exploded_graph &m_eg;
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). */
209 enum status
210 {
211 /* Node is in the worklist. */
212 STATUS_WORKLIST,
213
214 /* Node has had exploded_graph::process_node called on it. */
215 STATUS_PROCESSED,
216
217 /* Node was left unprocessed due to merger; it won't have had
218 exploded_graph::process_node called on it. */
219 STATUS_MERGER,
220
221 /* Node was processed by maybe_process_run_of_before_supernode_enodes. */
222 STATUS_BULK_MERGED
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
235 void dump_to_pp (pretty_printer *pp, const extrinsic_state &ext_state) const;
236 void dump (FILE *fp, const extrinsic_state &ext_state) const;
237 void dump (const extrinsic_state &ext_state) const;
238
239 void dump_processed_stmts (pretty_printer *pp) const;
240 void dump_saved_diagnostics (pretty_printer *pp) const;
241
242 json::object *to_json (const extrinsic_state &ext_state) const;
243
244 /* The result of on_stmt. */
245 struct on_stmt_flags
246 {
247 on_stmt_flags () : m_terminate_path (false)
248 {}
249
250 static on_stmt_flags terminate_path ()
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). */
257 bool m_terminate_path : 1;
258
259 private:
260 on_stmt_flags (bool terminate_path)
261 : m_terminate_path (terminate_path)
262 {}
263 };
264
265 on_stmt_flags on_stmt (exploded_graph &eg,
266 const supernode *snode,
267 const gimple *stmt,
268 program_state *state,
269 uncertainty_t *uncertainty,
270 bool *out_could_have_done_work,
271 path_context *path_ctxt);
272 void on_stmt_pre (exploded_graph &eg,
273 const gimple *stmt,
274 program_state *state,
275 bool *out_terminate_path,
276 bool *out_unknown_side_effects,
277 region_model_context *ctxt);
278 void on_stmt_post (const gimple *stmt,
279 program_state *state,
280 bool unknown_side_effects,
281 region_model_context *ctxt);
282
283 on_stmt_flags replay_call_summaries (exploded_graph &eg,
284 const supernode *snode,
285 const gcall *call_stmt,
286 program_state *state,
287 path_context *path_ctxt,
288 const function &called_fn,
289 per_function_data &called_fn_data,
290 region_model_context *ctxt);
291 void replay_call_summary (exploded_graph &eg,
292 const supernode *snode,
293 const gcall *call_stmt,
294 program_state *state,
295 path_context *path_ctxt,
296 const function &called_fn,
297 call_summary *summary,
298 region_model_context *ctxt);
299
300 bool on_edge (exploded_graph &eg,
301 const superedge *succ,
302 program_point *next_point,
303 program_state *next_state,
304 uncertainty_t *uncertainty);
305 void on_longjmp (exploded_graph &eg,
306 const gcall *call,
307 program_state *new_state,
308 region_model_context *ctxt);
309
310 void detect_leaks (exploded_graph &eg);
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 }
317 function *get_function () const
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; }
336 void set_status (enum status status)
337 {
338 gcc_assert (m_status == STATUS_WORKLIST);
339 m_status = status;
340 }
341
342 void add_diagnostic (const saved_diagnostic *sd)
343 {
344 m_saved_diagnostics.safe_push (obj: 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:
356 DISABLE_COPY_AND_ASSIGN (exploded_node);
357
358 /* The <program_point, program_state> pair. This is const, as it
359 is immutable once the exploded_node has been created. */
360 const point_and_state m_ps;
361
362 enum status m_status;
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. */
374 unsigned m_num_processed_stmts;
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:
383 exploded_edge (exploded_node *src, exploded_node *dest,
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;
388 void dump_dot_label (pretty_printer *pp) const;
389
390 json::object *to_json () const;
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:
403 DISABLE_COPY_AND_ASSIGN (exploded_edge);
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. */
418 bool m_could_do_work_p;
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
424class dynamic_call_info_t : public custom_edge_info
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 {
435 if (m_is_returning_call)
436 pp_string (pp, "dynamic_return");
437 else
438 pp_string (pp, "dynamic_call");
439 }
440
441 bool update_model (region_model *model,
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:
448 const gcall *m_dynamic_call;
449 const bool m_is_returning_call;
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
456class rewind_info_t : public custom_edge_info
457{
458public:
459 rewind_info_t (const setjmp_record &setjmp_record,
460 const gcall *longjmp_call)
461 : m_setjmp_record (setjmp_record),
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
470 bool update_model (region_model *model,
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
477 const program_point &get_setjmp_point () const
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 {
491 return m_setjmp_record.m_setjmp_call;
492 }
493
494 const gcall *get_longjmp_call () const
495 {
496 return m_longjmp_call;
497 }
498
499 const exploded_node *get_enode_origin () const
500 {
501 return m_setjmp_record.m_enode;
502 }
503
504private:
505 setjmp_record m_setjmp_record;
506 const gcall *m_longjmp_call;
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
519 int m_num_nodes[NUM_POINT_KINDS];
520 int m_node_reuse_count;
521 int m_node_reuse_after_merge_count;
522 int m_num_supernodes;
523};
524
525/* Traits class for ensuring uniqueness of point_and_state data within
526 an exploded_graph. */
527
528struct eg_hash_map_traits
529{
530 typedef const point_and_state *key_type;
531 typedef exploded_node *value_type;
532 typedef exploded_node *compare_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
582struct per_program_point_data
583{
584 per_program_point_data (const program_point &key)
585 : m_key (key), m_excess_enodes (0)
586 {}
587
588 const program_point m_key;
589 auto_vec<exploded_node *> m_enodes;
590 /* The number of attempts to create an enode for this point
591 after exceeding --param=analyzer-max-enodes-per-program-point. */
592 int m_excess_enodes;
593};
594
595/* Traits class for storing per-program_point data within
596 an exploded_graph. */
597
598struct eg_point_hash_map_traits
599{
600 typedef const program_point *key_type;
601 typedef per_program_point_data *value_type;
602 typedef per_program_point_data *compare_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
652struct per_call_string_data
653{
654 per_call_string_data (const call_string &key, int num_supernodes)
655 : m_key (key), m_stats (num_supernodes)
656 {}
657
658 const call_string &m_key;
659 stats m_stats;
660};
661
662/* Data about a particular function within an exploded_graph. */
663
664struct per_function_data
665{
666 per_function_data () {}
667 ~per_function_data ();
668
669 void add_call_summary (exploded_node *node);
670
671 auto_vec<call_summary *> m_summaries;
672};
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
679class strongly_connected_components
680{
681public:
682 strongly_connected_components (const supergraph &sg, logger *logger);
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
691 json::array *to_json () const;
692
693private:
694 struct per_node_data
695 {
696 per_node_data ()
697 : m_index (-1), m_lowlink (-1), m_on_stack (false)
698 {}
699
700 int m_index;
701 int m_lowlink;
702 bool m_on_stack;
703 };
704
705 void strong_connect (unsigned index);
706
707 const supergraph &m_sg;
708 auto_vec<unsigned> m_stack;
709 auto_vec<per_node_data> m_per_node;
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
722class worklist
723{
724public:
725 worklist (const exploded_graph &eg, const analysis_plan &plan);
726 unsigned length () const;
727 exploded_node *take_next ();
728 exploded_node *peek_next ();
729 void add_node (exploded_node *enode);
730 int get_scc_id (const supernode &snode) const
731 {
732 return m_scc.get_scc_id (node_index: snode.m_index);
733 }
734
735 json::object *to_json () const;
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 (ka: *this, kb: other) < 0;
748 }
749
750 bool operator== (const key_t &other) const
751 {
752 return cmp (ka: *this, kb: 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 (node_index: snode->m_index);
769 }
770
771 const worklist &m_worklist;
772 exploded_node *m_enode;
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). */
778 strongly_connected_components m_scc;
779 const analysis_plan &m_plan;
780
781 /* Priority queue, backed by a fibonacci_heap. */
782 typedef fibonacci_heap<key_t, exploded_node> queue_t;
783 queue_t m_queue;
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 *,
794 per_call_string_data *> call_string_data_map_t;
795
796 exploded_graph (const supergraph &sg, logger *logger,
797 const extrinsic_state &ext_state,
798 const state_purge_map *purge_map,
799 const analysis_plan &plan,
800 int verbosity);
801 ~exploded_graph ();
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
813 exploded_node *add_function_entry (const function &fun);
814
815 void build_initial_worklist ();
816 void process_worklist ();
817 bool maybe_process_run_of_before_supernode_enodes (exploded_node *node);
818 void process_node (exploded_node *node);
819
820 bool maybe_create_dynamic_call (const gcall *call,
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
828 exploded_node *get_or_create_node (const program_point &point,
829 const program_state &state,
830 exploded_node *enode_for_diag);
831 exploded_edge *add_edge (exploded_node *src, exploded_node *dest,
832 const superedge *sedge, bool could_do_work,
833 std::unique_ptr<custom_edge_info> custom = NULL);
834
835 per_program_point_data *
836 get_or_create_per_program_point_data (const program_point &);
837 per_program_point_data *
838 get_per_program_point_data (const program_point &) const;
839
840 per_call_string_data *
841 get_or_create_per_call_string_data (const call_string &);
842
843 per_function_data *
844 get_or_create_per_function_data (function *);
845 per_function_data *get_per_function_data (function *) const;
846
847 void save_diagnostic (const state_machine &sm,
848 const exploded_node *enode,
849 const supernode *node, const gimple *stmt,
850 stmt_finder *finder,
851 tree var, state_machine::state_t state,
852 pending_diagnostic *d);
853
854 diagnostic_manager &get_diagnostic_manager ()
855 {
856 return m_diagnostic_manager;
857 }
858 const diagnostic_manager &get_diagnostic_manager () const
859 {
860 return m_diagnostic_manager;
861 }
862
863 stats *get_global_stats () { return &m_global_stats; }
864 stats *get_or_create_function_stats (function *fn);
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
870 json::object *to_json () const;
871
872 exploded_node *get_node_by_index (int idx) const;
873
874 const call_string_data_map_t *get_per_call_string_data () const
875 { return &m_per_call_string_data; }
876
877 int get_scc_id (const supernode &node) const
878 {
879 return m_worklist.get_scc_id (snode: node);
880 }
881
882 void on_escaped_function (tree fndecl);
883
884 /* In infinite-loop.cc */
885 void detect_infinite_loops ();
886
887 /* In infinite-recursion.cc */
888 void detect_infinite_recursion (exploded_node *enode);
889 exploded_node *find_previous_entry_to (function *top_of_stack_fun,
890 exploded_node *enode) const;
891
892private:
893 void print_bar_charts (pretty_printer *pp) const;
894
895 DISABLE_COPY_AND_ASSIGN (exploded_graph);
896
897 const supergraph &m_sg;
898
899 log_user m_logger;
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 *,
906 eg_hash_map_traits> map_t;
907 map_t m_point_and_state_to_node;
908
909 /* Map from program_point to per-program_point data. */
910 typedef hash_map <const program_point *, per_program_point_data *,
911 eg_point_hash_map_traits> point_map_t;
912 point_map_t m_per_point_data;
913
914 worklist m_worklist;
915
916 exploded_node *m_origin;
917
918 const extrinsic_state &m_ext_state;
919
920 const state_purge_map *const m_purge_map;
921
922 const analysis_plan &m_plan;
923
924 typedef hash_map<function *, per_function_data *> per_function_data_t;
925 per_function_data_t m_per_function_data;
926
927 diagnostic_manager m_diagnostic_manager;
928
929 /* Stats. */
930 stats m_global_stats;
931 typedef ordered_hash_map<function *, stats *> function_stat_map_t;
932 function_stat_map_t m_per_function_stats;
933 stats m_functionless_stats;
934
935 call_string_data_map_t m_per_call_string_data;
936
937 auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode;
938
939 /* Functions with a top-level enode, to make add_function_entry
940 be idempotent, for use in handling callbacks. */
941 hash_set<function *> m_functions_with_enodes;
942};
943
944/* A path within an exploded_graph: a sequence of edges. */
945
946class exploded_path
947{
948public:
949 exploded_path () : m_edges () {}
950 exploded_path (const exploded_path &other);
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
957 exploded_node *get_final_enode () const;
958
959 void dump_to_pp (pretty_printer *pp,
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
969 auto_vec<const exploded_edge *> m_edges;
970};
971
972/* A reason why a particular exploded_path is infeasible. */
973
974class feasibility_problem
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;
988 const exploded_edge &m_eedge;
989 const gimple *m_last_stmt;
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
996class feasibility_state
997{
998public:
999 feasibility_state (region_model_manager *manager,
1000 const supergraph &sg);
1001 feasibility_state (const region_model &model,
1002 const supergraph &sg);
1003 feasibility_state (const feasibility_state &other);
1004
1005 feasibility_state &operator= (const feasibility_state &other);
1006
1007 bool maybe_update_for_edge (logger *logger,
1008 const exploded_edge *eedge,
1009 region_model_context *ctxt,
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; }
1014 const auto_sbitmap &get_snodes_visited () const { return m_snodes_visited; }
1015
1016 void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const;
1017
1018private:
1019 region_model m_model;
1020 auto_sbitmap m_snodes_visited;
1021};
1022
1023/* Finding the shortest exploded_path within an exploded_graph. */
1024
1025typedef shortest_paths<eg_traits, exploded_path> shortest_exploded_paths;
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
1032class stmt_finder
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;
1038};
1039
1040// TODO: split the above up?
1041
1042} // namespace ana
1043
1044#endif /* GCC_ANALYZER_EXPLODED_GRAPH_H */
1045

source code of gcc/analyzer/exploded-graph.h