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