1 /* Classes for saving, deduplicating, and emitting analyzer diagnostics.
2 Copyright (C) 2019-2023 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 #define INCLUDE_MEMORY
24 #include "coretypes.h"
27 #include "pretty-print.h"
28 #include "gcc-rich-location.h"
29 #include "gimple-pretty-print.h"
31 #include "diagnostic-core.h"
32 #include "diagnostic-event-id.h"
33 #include "diagnostic-path.h"
35 #include "ordered-hash-map.h"
36 #include "analyzer/analyzer.h"
37 #include "analyzer/analyzer-logging.h"
38 #include "analyzer/sm.h"
39 #include "analyzer/pending-diagnostic.h"
40 #include "analyzer/diagnostic-manager.h"
41 #include "analyzer/call-string.h"
42 #include "analyzer/program-point.h"
43 #include "analyzer/store.h"
44 #include "analyzer/region-model.h"
45 #include "analyzer/constraint-manager.h"
47 #include "basic-block.h"
49 #include "gimple-iterator.h"
50 #include "inlining-iterator.h"
53 #include "analyzer/supergraph.h"
54 #include "analyzer/program-state.h"
55 #include "analyzer/exploded-graph.h"
56 #include "analyzer/trimmed-graph.h"
57 #include "analyzer/feasible-graph.h"
58 #include "analyzer/checker-path.h"
59 #include "analyzer/reachability.h"
60 #include "make-unique.h"
61 #include "diagnostic-format-sarif.h"
67 class feasible_worklist
;
69 /* State for finding the shortest feasible exploded_path for a
71 This is shared between all diagnostics, so that we avoid repeating work. */
76 epath_finder (const exploded_graph
&eg
)
80 /* This is shared by all diagnostics, but only needed if
81 !flag_analyzer_feasibility. */
82 if (!flag_analyzer_feasibility
)
83 m_sep
= new shortest_exploded_paths (eg
, eg
.get_origin (),
84 SPS_FROM_GIVEN_ORIGIN
);
87 ~epath_finder () { delete m_sep
; }
89 logger
*get_logger () const { return m_eg
.get_logger (); }
91 std::unique_ptr
<exploded_path
>
92 get_best_epath (const exploded_node
*target_enode
,
93 const gimple
*target_stmt
,
94 const pending_diagnostic
&pd
,
95 const char *desc
, unsigned diag_idx
,
96 std::unique_ptr
<feasibility_problem
> *out_problem
);
99 DISABLE_COPY_AND_ASSIGN(epath_finder
);
101 std::unique_ptr
<exploded_path
>
102 explore_feasible_paths (const exploded_node
*target_enode
,
103 const gimple
*target_stmt
,
104 const pending_diagnostic
&pd
,
105 const char *desc
, unsigned diag_idx
);
107 process_worklist_item (feasible_worklist
*worklist
,
108 const trimmed_graph
&tg
,
110 const exploded_node
*target_enode
,
111 const gimple
*target_stmt
,
112 const pending_diagnostic
&pd
,
114 std::unique_ptr
<exploded_path
> *out_best_path
) const;
115 void dump_trimmed_graph (const exploded_node
*target_enode
,
116 const char *desc
, unsigned diag_idx
,
117 const trimmed_graph
&tg
,
118 const shortest_paths
<eg_traits
, exploded_path
> &sep
);
119 void dump_feasible_graph (const exploded_node
*target_enode
,
120 const char *desc
, unsigned diag_idx
,
121 const feasible_graph
&fg
);
122 void dump_feasible_path (const exploded_node
*target_enode
,
124 const feasible_graph
&fg
,
125 const feasible_node
&fnode
) const;
127 const exploded_graph
&m_eg
;
128 shortest_exploded_paths
*m_sep
;
131 /* class epath_finder. */
133 /* Get the "best" exploded_path for reaching ENODE from the origin,
134 returning ownership of it to the caller.
136 If TARGET_STMT is non-NULL, then check for reaching that stmt
139 Ideally we want to report the shortest feasible path.
140 Return NULL if we could not find a feasible path
141 (when flag_analyzer_feasibility is true).
143 If flag_analyzer_feasibility is false, then simply return the
146 Use DESC and DIAG_IDX when logging.
148 Write any feasibility_problem to *OUT_PROBLEM. */
150 std::unique_ptr
<exploded_path
>
151 epath_finder::get_best_epath (const exploded_node
*enode
,
152 const gimple
*target_stmt
,
153 const pending_diagnostic
&pd
,
154 const char *desc
, unsigned diag_idx
,
155 std::unique_ptr
<feasibility_problem
> *out_problem
)
157 logger
*logger
= get_logger ();
160 unsigned snode_idx
= enode
->get_supernode ()->m_index
;
162 logger
->log ("considering %qs at EN: %i, SN: %i (sd: %i)",
163 desc
, enode
->m_index
, snode_idx
, diag_idx
);
165 /* State-merging means that not every path in the egraph corresponds
166 to a feasible one w.r.t. states.
168 We want to find the shortest feasible path from the origin to ENODE
171 if (flag_analyzer_feasibility
)
173 /* Attempt to find the shortest feasible path using feasible_graph. */
175 logger
->log ("trying to find shortest feasible path");
176 if (std::unique_ptr
<exploded_path
> epath
177 = explore_feasible_paths (enode
, target_stmt
, pd
, desc
, diag_idx
))
180 logger
->log ("accepting %qs at EN: %i, SN: %i (sd: %i)"
181 " with feasible path (length: %i)",
182 desc
, enode
->m_index
, snode_idx
, diag_idx
,
189 logger
->log ("rejecting %qs at EN: %i, SN: %i (sd: %i)"
190 " due to not finding feasible path",
191 desc
, enode
->m_index
, snode_idx
, diag_idx
);
197 /* As a crude approximation to shortest feasible path, simply find
198 the shortest path, and note whether it is feasible.
199 There could be longer feasible paths within the egraph, so this
200 approach would lead to diagnostics being falsely rejected
201 (PR analyzer/96374). */
203 logger
->log ("trying to find shortest path ignoring feasibility");
205 std::unique_ptr
<exploded_path
> epath
206 = make_unique
<exploded_path
> (m_sep
->get_shortest_path (enode
));
207 if (epath
->feasible_p (logger
, out_problem
, m_eg
.get_engine (), &m_eg
))
210 logger
->log ("accepting %qs at EN: %i, SN: %i (sn: %i)"
211 " with feasible path (length: %i)",
212 desc
, enode
->m_index
, snode_idx
, diag_idx
,
218 logger
->log ("accepting %qs at EN: %i, SN: %i (sn: %i) (length: %i)"
219 " despite infeasible path (due to %qs)",
220 desc
, enode
->m_index
, snode_idx
, diag_idx
,
222 "-fno-analyzer-feasibility");
228 /* A class for managing the worklist of feasible_nodes in
229 epath_finder::explore_feasible_paths, prioritizing them
230 so that shorter paths appear earlier in the queue. */
232 class feasible_worklist
235 feasible_worklist (const shortest_paths
<eg_traits
, exploded_path
> &sep
)
236 : m_queue (key_t (*this, NULL
)),
241 feasible_node
*take_next () { return m_queue
.extract_min (); }
243 void add_node (feasible_node
*fnode
)
245 m_queue
.insert (key_t (*this, fnode
), fnode
);
251 key_t (const feasible_worklist
&w
, feasible_node
*fnode
)
252 : m_worklist (w
), m_fnode (fnode
)
255 bool operator< (const key_t
&other
) const
257 return cmp (*this, other
) < 0;
260 bool operator== (const key_t
&other
) const
262 return cmp (*this, other
) == 0;
265 bool operator> (const key_t
&other
) const
267 return !(*this == other
|| *this < other
);
271 static int cmp (const key_t
&ka
, const key_t
&kb
)
273 /* Choose the node for which if the remaining path were feasible,
274 it would be the shortest path (summing the length of the
275 known-feasible path so far with that of the remaining
276 possibly-feasible path). */
277 int ca
= ka
.m_worklist
.get_estimated_cost (ka
.m_fnode
);
278 int cb
= kb
.m_worklist
.get_estimated_cost (kb
.m_fnode
);
282 const feasible_worklist
&m_worklist
;
283 feasible_node
*m_fnode
;
286 /* Get the estimated length of a path involving FNODE from
287 the origin to the target enode.
288 Sum the length of the known-feasible path so far with
289 that of the remaining possibly-feasible path. */
291 int get_estimated_cost (const feasible_node
*fnode
) const
293 unsigned length_so_far
= fnode
->get_path_length ();
294 int shortest_remaining_path
295 = m_sep
.get_shortest_distance (fnode
->get_inner_node ());
297 gcc_assert (shortest_remaining_path
>= 0);
298 /* This should be true since we're only exploring nodes within
299 the trimmed graph (and we anticipate it being much smaller
300 than this, and thus not overflowing the sum). */
301 gcc_assert (shortest_remaining_path
< INT_MAX
);
303 return length_so_far
+ shortest_remaining_path
;
306 /* Priority queue, backed by a fibonacci_heap. */
307 typedef fibonacci_heap
<key_t
, feasible_node
> queue_t
;
309 const shortest_paths
<eg_traits
, exploded_path
> &m_sep
;
312 /* When we're building the exploded graph we want to simplify
313 overly-complicated symbolic values down to "UNKNOWN" to try to avoid
314 state explosions and unbounded chains of exploration.
316 However, when we're building the feasibility graph for a diagnostic
317 (actually a tree), we don't want UNKNOWN values, as conditions on them
318 are also unknown: we don't want to have a contradiction such as a path
319 where (VAL != 0) and then (VAL == 0) along the same path.
321 Hence this is an RAII class for temporarily disabling complexity-checking
322 in the region_model_manager, for use within
323 epath_finder::explore_feasible_paths.
325 We also disable the creation of unknown_svalue instances during feasibility
326 checking, instead creating unique svalues, to avoid paradoxes in paths. */
328 class auto_checking_feasibility
331 auto_checking_feasibility (region_model_manager
*mgr
) : m_mgr (mgr
)
333 m_mgr
->begin_checking_feasibility ();
335 ~auto_checking_feasibility ()
337 m_mgr
->end_checking_feasibility ();
340 region_model_manager
*m_mgr
;
343 /* Attempt to find the shortest feasible path from the origin to
344 TARGET_ENODE by iteratively building a feasible_graph, in which
345 every path to a feasible_node is feasible by construction.
347 If TARGET_STMT is non-NULL, then check for reaching that stmt
350 We effectively explore the tree of feasible paths in order of shortest
351 path until we either find a feasible path to TARGET_ENODE, or hit
355 - Find the shortest path from each node to the TARGET_ENODE (without
356 checking feasibility), so that we can prioritize our worklist.
357 - Construct a trimmed_graph: the subset of nodes/edges that
358 are on a path that eventually reaches TARGET_ENODE. We will only need
359 to consider these when considering the shortest feasible path.
361 Build a feasible_graph, in which every path to a feasible_node
362 is feasible by construction.
363 We use a worklist to flatten the exploration into an iteration.
364 Starting at the origin, find feasible out-edges within the trimmed graph.
365 At each stage, choose the node for which if the remaining path were feasible,
366 it would be the shortest path (summing the length of the known-feasible path
367 so far with that of the remaining possibly-feasible path).
368 This way, the first feasible path we find to TARGET_ENODE is the shortest.
369 We start by trying the shortest possible path, but if that fails,
370 we explore progressively longer paths, eventually trying iterations through
371 loops. The exploration is captured in the feasible_graph, which can be
372 dumped as a .dot file to visualize the exploration. The indices of the
373 feasible_nodes show the order in which they were created.
375 This is something of a brute-force approach, but the trimmed_graph
376 hopefully keeps the complexity manageable.
378 Terminate with failure when the number of infeasible edges exceeds
379 a threshold (--param=analyzer-max-infeasible-edges=).
380 This is guaranteed to eventually lead to terminatation, as
381 we can't keep creating feasible nodes without eventually
382 either reaching an infeasible edge, or reaching the
383 TARGET_ENODE. Specifically, there can't be a cycle of
384 feasible edges that doesn't reach the target_enode without
385 an out-edge that either fails feasibility or gets closer
386 to the TARGET_ENODE: on each iteration we are either:
387 - effectively getting closer to the TARGET_ENODE (which can't
388 continue forever without reaching the target), or
389 - getting monotonically closer to the termination threshold. */
391 std::unique_ptr
<exploded_path
>
392 epath_finder::explore_feasible_paths (const exploded_node
*target_enode
,
393 const gimple
*target_stmt
,
394 const pending_diagnostic
&pd
,
395 const char *desc
, unsigned diag_idx
)
397 logger
*logger
= get_logger ();
400 region_model_manager
*mgr
= m_eg
.get_engine ()->get_model_manager ();
402 /* Determine the shortest path to TARGET_ENODE from each node in
403 the exploded graph. */
404 shortest_paths
<eg_traits
, exploded_path
> sep
405 (m_eg
, target_enode
, SPS_TO_GIVEN_TARGET
);
407 /* Construct a trimmed_graph: the subset of nodes/edges that
408 are on a path that eventually reaches TARGET_ENODE.
409 We only need to consider these when considering the shortest
411 trimmed_graph
tg (m_eg
, target_enode
);
413 if (flag_dump_analyzer_feasibility
)
414 dump_trimmed_graph (target_enode
, desc
, diag_idx
, tg
, sep
);
417 feasible_worklist
worklist (sep
);
419 /* Populate the worklist with the origin node. */
421 feasibility_state
init_state (mgr
, m_eg
.get_supergraph ());
422 feasible_node
*origin
= fg
.add_node (m_eg
.get_origin (), init_state
, 0);
423 worklist
.add_node (origin
);
426 /* Iteratively explore the tree of feasible paths in order of shortest
427 path until we either find a feasible path to TARGET_ENODE, or hit
430 /* Set this if we find a feasible path to TARGET_ENODE. */
431 std::unique_ptr
<exploded_path
> best_path
= NULL
;
434 auto_checking_feasibility
sentinel (mgr
);
436 while (process_worklist_item (&worklist
, tg
, &fg
, target_enode
, target_stmt
,
437 pd
, diag_idx
, &best_path
))
439 /* Empty; the work is done within process_worklist_item. */
445 logger
->log ("tg for sd: %i:", diag_idx
);
446 logger
->inc_indent ();
447 tg
.log_stats (logger
);
448 logger
->dec_indent ();
450 logger
->log ("fg for sd: %i:", diag_idx
);
451 logger
->inc_indent ();
452 fg
.log_stats (logger
);
453 logger
->dec_indent ();
456 /* Dump the feasible_graph. */
457 if (flag_dump_analyzer_feasibility
)
458 dump_feasible_graph (target_enode
, desc
, diag_idx
, fg
);
463 /* Process the next item in WORKLIST, potentially adding new items
464 based on feasible out-edges, and extending FG accordingly.
465 Use TG to ignore out-edges that don't lead to TARGET_ENODE.
466 Return true if the worklist processing should continue.
467 Return false if the processing of the worklist should stop
468 (either due to reaching TARGET_ENODE, or hitting a limit).
469 Write to *OUT_BEST_PATH if stopping due to finding a feasible path
471 Use PD to provide additional restrictions on feasibility of
472 the final path in the feasible_graph before converting to
477 process_worklist_item (feasible_worklist
*worklist
,
478 const trimmed_graph
&tg
,
480 const exploded_node
*target_enode
,
481 const gimple
*target_stmt
,
482 const pending_diagnostic
&pd
,
484 std::unique_ptr
<exploded_path
> *out_best_path
) const
486 logger
*logger
= get_logger ();
488 feasible_node
*fnode
= worklist
->take_next ();
492 logger
->log ("drained worklist for sd: %i"
493 " without finding feasible path",
498 log_scope
s (logger
, "fg worklist item",
499 "considering FN: %i (EN: %i) for sd: %i",
500 fnode
->get_index (), fnode
->get_inner_node ()->m_index
,
503 /* Iterate through all out-edges from this item. */
505 exploded_edge
*succ_eedge
;
506 FOR_EACH_VEC_ELT (fnode
->get_inner_node ()->m_succs
, i
, succ_eedge
)
508 log_scope
s (logger
, "edge", "considering edge: EN:%i -> EN:%i",
509 succ_eedge
->m_src
->m_index
,
510 succ_eedge
->m_dest
->m_index
);
511 /* Reject edges that aren't in the trimmed graph. */
512 if (!tg
.contains_p (succ_eedge
))
515 logger
->log ("rejecting: not in trimmed graph");
519 feasibility_state
succ_state (fnode
->get_state ());
520 std::unique_ptr
<rejected_constraint
> rc
;
521 if (succ_state
.maybe_update_for_edge (logger
, succ_eedge
, nullptr, &rc
))
523 gcc_assert (rc
== NULL
);
524 feasible_node
*succ_fnode
525 = fg
->add_node (succ_eedge
->m_dest
,
527 fnode
->get_path_length () + 1);
529 logger
->log ("accepting as FN: %i", succ_fnode
->get_index ());
530 fg
->add_edge (new feasible_edge (fnode
, succ_fnode
, succ_eedge
));
532 /* Have we reached TARGET_ENODE? */
533 if (succ_fnode
->get_inner_node () == target_enode
)
536 logger
->log ("success: got feasible path to EN: %i (sd: %i)"
538 target_enode
->m_index
, diag_idx
,
539 succ_fnode
->get_path_length ());
540 if (!pd
.check_valid_fpath_p (*succ_fnode
, target_stmt
))
543 logger
->log ("rejecting feasible path due to"
544 " pending_diagnostic");
547 *out_best_path
= fg
->make_epath (succ_fnode
);
548 if (flag_dump_analyzer_feasibility
)
549 dump_feasible_path (target_enode
, diag_idx
, *fg
, *succ_fnode
);
551 /* Success: stop the worklist iteration. */
555 worklist
->add_node (succ_fnode
);
560 logger
->log ("infeasible");
562 fg
->add_feasibility_problem (fnode
,
566 /* Give up if there have been too many infeasible edges. */
567 if (fg
->get_num_infeasible ()
568 > (unsigned)param_analyzer_max_infeasible_edges
)
571 logger
->log ("too many infeasible edges (%i); giving up",
572 fg
->get_num_infeasible ());
578 /* Continue the worklist iteration. */
582 /* Helper class for epath_finder::dump_trimmed_graph
583 to dump extra per-node information.
584 Use SEP to add the length of the shortest path from each
585 node to the target node to each node's dump. */
587 class dump_eg_with_shortest_path
: public eg_traits::dump_args_t
590 dump_eg_with_shortest_path
591 (const exploded_graph
&eg
,
592 const shortest_paths
<eg_traits
, exploded_path
> &sep
)
598 void dump_extra_info (const exploded_node
*enode
,
599 pretty_printer
*pp
) const final override
601 pp_printf (pp
, "sp: %i", m_sep
.get_shortest_path (enode
).length ());
606 const shortest_paths
<eg_traits
, exploded_path
> &m_sep
;
609 /* Dump TG to "BASE_NAME.DESC.DIAG_IDX.to-enN.tg.dot",
610 annotating each node with the length of the shortest path
611 from that node to TARGET_ENODE (using SEP). */
615 dump_trimmed_graph (const exploded_node
*target_enode
,
616 const char *desc
, unsigned diag_idx
,
617 const trimmed_graph
&tg
,
618 const shortest_paths
<eg_traits
, exploded_path
> &sep
)
620 auto_timevar
tv (TV_ANALYZER_DUMP
);
621 dump_eg_with_shortest_path
inner_args (m_eg
, sep
);
622 trimmed_graph::dump_args_t
args (inner_args
);
624 pp_printf (&pp
, "%s.%s.%i.to-en%i.tg.dot",
625 dump_base_name
, desc
, diag_idx
, target_enode
->m_index
);
626 char *filename
= xstrdup (pp_formatted_text (&pp
));
627 tg
.dump_dot (filename
, NULL
, args
);
631 /* Dump FG to "BASE_NAME.DESC.DIAG_IDX.to-enN.fg.dot". */
634 epath_finder::dump_feasible_graph (const exploded_node
*target_enode
,
635 const char *desc
, unsigned diag_idx
,
636 const feasible_graph
&fg
)
638 auto_timevar
tv (TV_ANALYZER_DUMP
);
639 exploded_graph::dump_args_t
inner_args (m_eg
);
640 feasible_graph::dump_args_t
args (inner_args
);
642 pp_printf (&pp
, "%s.%s.%i.to-en%i.fg.dot",
643 dump_base_name
, desc
, diag_idx
, target_enode
->m_index
);
644 char *filename
= xstrdup (pp_formatted_text (&pp
));
645 fg
.dump_dot (filename
, NULL
, args
);
649 /* Dump the path to FNODE to "BASE_NAME.DIAG_IDX.to-enN.fpath.txt". */
652 epath_finder::dump_feasible_path (const exploded_node
*target_enode
,
654 const feasible_graph
&fg
,
655 const feasible_node
&fnode
) const
657 auto_timevar
tv (TV_ANALYZER_DUMP
);
659 pp_printf (&pp
, "%s.%i.to-en%i.fpath.txt",
660 dump_base_name
, diag_idx
, target_enode
->m_index
);
661 char *filename
= xstrdup (pp_formatted_text (&pp
));
662 fg
.dump_feasible_path (fnode
, filename
);
666 /* class saved_diagnostic. */
668 /* saved_diagnostic's ctor. */
670 saved_diagnostic::saved_diagnostic (const state_machine
*sm
,
671 const pending_location
&ploc
,
674 state_machine::state_t state
,
675 std::unique_ptr
<pending_diagnostic
> d
,
677 : m_sm (sm
), m_enode (ploc
.m_enode
), m_snode (ploc
.m_snode
),
678 m_stmt (ploc
.m_stmt
),
679 /* stmt_finder could be on-stack; we want our own copy that can
681 m_stmt_finder (ploc
.m_finder
? ploc
.m_finder
->clone () : NULL
),
683 m_var (var
), m_sval (sval
), m_state (state
),
684 m_d (std::move (d
)), m_trailing_eedge (NULL
),
686 m_best_epath (NULL
), m_problem (NULL
),
689 /* We must have an enode in order to be able to look for paths
690 through the exploded_graph to this diagnostic. */
691 gcc_assert (m_enode
);
695 saved_diagnostic::operator== (const saved_diagnostic
&other
) const
697 if (m_notes
.length () != other
.m_notes
.length ())
699 for (unsigned i
= 0; i
< m_notes
.length (); i
++)
700 if (!m_notes
[i
]->equal_p (*other
.m_notes
[i
]))
702 return (m_sm
== other
.m_sm
703 /* We don't compare m_enode. */
704 && m_snode
== other
.m_snode
705 && m_stmt
== other
.m_stmt
706 /* We don't compare m_stmt_finder. */
707 && m_loc
== other
.m_loc
708 && pending_diagnostic::same_tree_p (m_var
, other
.m_var
)
709 && m_state
== other
.m_state
710 && m_d
->equal_p (*other
.m_d
)
711 && m_trailing_eedge
== other
.m_trailing_eedge
);
714 /* Add PN to this diagnostic, taking ownership of it. */
717 saved_diagnostic::add_note (std::unique_ptr
<pending_note
> pn
)
720 m_notes
.safe_push (pn
.release ());
723 /* Add EVENT to this diagnostic. */
726 saved_diagnostic::add_event (std::unique_ptr
<checker_event
> event
)
729 m_saved_events
.safe_push (event
.release ());
732 /* Return a new json::object of the form
736 "sval": optional str,
737 "state": optional str,
738 "path_length": optional int,
739 "pending_diagnostic": str,
743 saved_diagnostic::to_json () const
745 json::object
*sd_obj
= new json::object ();
748 sd_obj
->set ("sm", new json::string (m_sm
->get_name ()));
749 sd_obj
->set ("enode", new json::integer_number (m_enode
->m_index
));
750 sd_obj
->set ("snode", new json::integer_number (m_snode
->m_index
));
752 sd_obj
->set ("sval", m_sval
->to_json ());
754 sd_obj
->set ("state", m_state
->to_json ());
756 sd_obj
->set ("path_length", new json::integer_number (get_epath_length ()));
757 sd_obj
->set ("pending_diagnostic", new json::string (m_d
->get_kind ()));
758 sd_obj
->set ("idx", new json::integer_number (m_idx
));
760 /* We're not yet JSONifying the following fields:
761 const gimple *m_stmt;
762 stmt_finder *m_stmt_finder;
764 exploded_edge *m_trailing_eedge;
765 enum status m_status;
766 feasibility_problem *m_problem;
767 auto_delete_vec <pending_note> m_notes;
773 /* Dump this to PP in a form suitable for use as an id in .dot output. */
776 saved_diagnostic::dump_dot_id (pretty_printer
*pp
) const
778 pp_printf (pp
, "sd_%i", m_idx
);
781 /* Dump this to PP in a form suitable for use as a node in .dot output. */
784 saved_diagnostic::dump_as_dot_node (pretty_printer
*pp
) const
788 " [shape=none,margin=0,style=filled,fillcolor=\"red\",label=\"");
789 pp_write_text_to_stream (pp
);
792 pp_printf (pp
, "DIAGNOSTIC: %s (sd: %i)\n",
793 m_d
->get_kind (), m_idx
);
796 pp_printf (pp
, "sm: %s", m_sm
->get_name ());
799 pp_printf (pp
, "; state: ");
800 m_state
->dump_to_pp (pp
);
806 pp_string (pp
, "stmt: ");
807 pp_gimple_stmt_1 (pp
, m_stmt
, 0, (dump_flags_t
)0);
811 pp_printf (pp
, "var: %qE\n", m_var
);
814 pp_string (pp
, "sval: ");
815 m_sval
->dump_to_pp (pp
, true);
819 pp_printf (pp
, "path length: %i\n", get_epath_length ());
821 pp_write_text_as_dot_label_to_stream (pp
, /*for_record=*/true);
822 pp_string (pp
, "\"];\n\n");
824 /* Show links to duplicates. */
825 for (auto iter
: m_duplicates
)
828 pp_string (pp
, " -> ");
829 iter
->dump_dot_id (pp
);
830 pp_string (pp
, " [style=\"dotted\" arrowhead=\"none\"];");
835 /* Use PF to find the best exploded_path for this saved_diagnostic,
836 and store it in m_best_epath.
837 If we don't have a specific location in m_loc and m_stmt is still NULL,
838 use m_stmt_finder on the epath to populate m_stmt.
839 Return true if a best path was found. */
842 saved_diagnostic::calc_best_epath (epath_finder
*pf
)
844 logger
*logger
= pf
->get_logger ();
848 m_best_epath
= pf
->get_best_epath (m_enode
, m_stmt
,
849 *m_d
, m_d
->get_kind (), m_idx
,
852 /* Handle failure to find a feasible path. */
853 if (m_best_epath
== NULL
)
856 gcc_assert (m_best_epath
);
857 if (m_loc
== UNKNOWN_LOCATION
)
861 gcc_assert (m_stmt_finder
);
862 m_stmt
= m_stmt_finder
->find_stmt (*m_best_epath
);
871 saved_diagnostic::get_epath_length () const
873 gcc_assert (m_best_epath
);
874 return m_best_epath
->length ();
877 /* Record that OTHER (and its duplicates) are duplicates
878 of this saved_diagnostic. */
881 saved_diagnostic::add_duplicate (saved_diagnostic
*other
)
884 m_duplicates
.reserve (m_duplicates
.length ()
885 + other
->m_duplicates
.length ()
887 m_duplicates
.splice (other
->m_duplicates
);
888 other
->m_duplicates
.truncate (0);
889 m_duplicates
.safe_push (other
);
892 /* Walk up the sedges of each of the two paths.
893 If the two sequences of sedges do not perfectly correspond,
894 then paths are incompatible.
895 If there is at least one sedge that either cannot be paired up
896 or its counterpart is not equal, then the paths are incompatible
897 and this function returns FALSE.
898 Otherwise return TRUE.
913 Both LHS_PATH and RHS_PATH final enodes should be
914 over the same gimple statement. */
917 compatible_epath_p (const exploded_path
*lhs_path
,
918 const exploded_path
*rhs_path
)
920 gcc_assert (lhs_path
);
921 gcc_assert (rhs_path
);
922 gcc_assert (rhs_path
->length () > 0);
923 gcc_assert (rhs_path
->length () > 0);
924 int lhs_eedge_idx
= lhs_path
->length () - 1;
925 int rhs_eedge_idx
= rhs_path
->length () - 1;
926 const exploded_edge
*lhs_eedge
;
927 const exploded_edge
*rhs_eedge
;
929 while (lhs_eedge_idx
>= 0 && rhs_eedge_idx
>= 0)
931 while (lhs_eedge_idx
>= 0)
933 /* Find LHS_PATH's next superedge. */
934 lhs_eedge
= lhs_path
->m_edges
[lhs_eedge_idx
];
935 if (lhs_eedge
->m_sedge
)
940 while (rhs_eedge_idx
>= 0)
942 /* Find RHS_PATH's next superedge. */
943 rhs_eedge
= rhs_path
->m_edges
[rhs_eedge_idx
];
944 if (rhs_eedge
->m_sedge
)
950 if (lhs_eedge
->m_sedge
&& rhs_eedge
->m_sedge
)
952 if (lhs_eedge
->m_sedge
!= rhs_eedge
->m_sedge
)
953 /* Both superedges do not match.
954 Superedges are not dependent on the exploded path, so even
955 different epaths will have similar sedges if they follow
956 the same outcome of a conditional node. */
963 else if (lhs_eedge
->m_sedge
== nullptr && rhs_eedge
->m_sedge
== nullptr)
964 /* Both paths were drained up entirely.
965 No discriminant was found. */
968 /* A superedge was found for only one of the two paths. */
972 /* A superedge was found for only one of the two paths. */
973 if (lhs_eedge_idx
>= 0 || rhs_eedge_idx
>= 0)
976 /* Both paths were drained up entirely.
977 No discriminant was found. */
982 /* Return true if this diagnostic supercedes OTHER, and that OTHER should
983 therefore not be emitted. */
986 saved_diagnostic::supercedes_p (const saved_diagnostic
&other
) const
988 /* They should be at the same stmt. */
989 if (m_stmt
!= other
.m_stmt
)
991 /* return early if OTHER won't be superseded anyway. */
992 if (!m_d
->supercedes_p (*other
.m_d
))
995 /* If the two saved_diagnostics' path are not compatible
996 then they cannot supersede one another. */
997 return compatible_epath_p (m_best_epath
.get (), other
.m_best_epath
.get ());
1000 /* Move any saved checker_events from this saved_diagnostic to
1001 the end of DST_PATH. */
1004 saved_diagnostic::add_any_saved_events (checker_path
&dst_path
)
1006 for (auto &event
: m_saved_events
)
1008 dst_path
.add_event (std::unique_ptr
<checker_event
> (event
));
1013 /* Emit any pending notes owned by this diagnostic. */
1016 saved_diagnostic::emit_any_notes () const
1018 for (auto pn
: m_notes
)
1022 /* For SARIF output, add additional properties to the "result" object
1023 for this diagnostic.
1024 This extra data is intended for use when debugging the analyzer. */
1027 saved_diagnostic::maybe_add_sarif_properties (sarif_object
&result_obj
) const
1029 sarif_property_bag
&props
= result_obj
.get_or_create_properties ();
1030 #define PROPERTY_PREFIX "gcc/analyzer/saved_diagnostic/"
1032 props
.set_string (PROPERTY_PREFIX
"sm", m_sm
->get_name ());
1033 props
.set_integer (PROPERTY_PREFIX
"enode", m_enode
->m_index
);
1034 props
.set_integer (PROPERTY_PREFIX
"snode", m_snode
->m_index
);
1036 props
.set (PROPERTY_PREFIX
"sval", m_sval
->to_json ());
1038 props
.set (PROPERTY_PREFIX
"state", m_state
->to_json ());
1040 props
.set (PROPERTY_PREFIX
"idx", new json::integer_number (m_idx
));
1041 #undef PROPERTY_PREFIX
1043 /* Potentially add pending_diagnostic-specific properties. */
1044 m_d
->maybe_add_sarif_properties (result_obj
);
1047 /* State for building a checker_path from a particular exploded_path.
1048 In particular, this precomputes reachability information: the set of
1049 source enodes for which a path be found to the diagnostic enode. */
1054 path_builder (const exploded_graph
&eg
,
1055 const exploded_path
&epath
,
1056 const feasibility_problem
*problem
,
1057 const saved_diagnostic
&sd
)
1059 m_diag_enode (epath
.get_final_enode ()),
1061 m_reachability (eg
, m_diag_enode
),
1062 m_feasibility_problem (problem
)
1065 const exploded_node
*get_diag_node () const { return m_diag_enode
; }
1067 pending_diagnostic
*get_pending_diagnostic () const
1069 return m_sd
.m_d
.get ();
1072 bool reachable_from_p (const exploded_node
*src_enode
) const
1074 return m_reachability
.reachable_from_p (src_enode
);
1077 const extrinsic_state
&get_ext_state () const { return m_eg
.get_ext_state (); }
1079 const feasibility_problem
*get_feasibility_problem () const
1081 return m_feasibility_problem
;
1084 const state_machine
*get_sm () const { return m_sd
.m_sm
; }
1087 typedef reachability
<eg_traits
> enode_reachability
;
1089 const exploded_graph
&m_eg
;
1091 /* The enode where the diagnostic occurs. */
1092 const exploded_node
*m_diag_enode
;
1094 const saved_diagnostic
&m_sd
;
1096 /* Precompute all enodes from which the diagnostic is reachable. */
1097 enode_reachability m_reachability
;
1099 const feasibility_problem
*m_feasibility_problem
;
1102 /* Determine the emission location for PD at STMT in FUN. */
1105 get_emission_location (const gimple
*stmt
, function
*fun
,
1106 const pending_diagnostic
&pd
)
1108 location_t loc
= get_stmt_location (stmt
, fun
);
1110 /* Allow the pending_diagnostic to fix up the location. */
1111 loc
= pd
.fixup_location (loc
, true);
1116 /* class diagnostic_manager. */
1118 /* diagnostic_manager's ctor. */
1120 diagnostic_manager::diagnostic_manager (logger
*logger
, engine
*eng
,
1122 : log_user (logger
), m_eng (eng
), m_verbosity (verbosity
),
1123 m_num_disabled_diagnostics (0)
1127 /* Queue pending_diagnostic D at ENODE for later emission.
1128 Return true/false signifying if the diagnostic was actually added. */
1131 diagnostic_manager::add_diagnostic (const state_machine
*sm
,
1132 const pending_location
&ploc
,
1135 state_machine::state_t state
,
1136 std::unique_ptr
<pending_diagnostic
> d
)
1138 LOG_FUNC (get_logger ());
1140 /* We must have an enode in order to be able to look for paths
1141 through the exploded_graph to the diagnostic. */
1142 gcc_assert (ploc
.m_enode
);
1144 /* If this warning is ultimately going to be rejected by a -Wno-analyzer-*
1145 flag, reject it now.
1146 We can only do this for diagnostics where we already know the stmt,
1147 and thus can determine the emission location. */
1151 = get_emission_location (ploc
.m_stmt
, ploc
.m_snode
->m_fun
, *d
);
1152 int option
= d
->get_controlling_option ();
1153 if (!warning_enabled_at (loc
, option
))
1156 get_logger ()->log ("rejecting disabled warning %qs",
1158 m_num_disabled_diagnostics
++;
1163 saved_diagnostic
*sd
1164 = new saved_diagnostic (sm
, ploc
, var
, sval
, state
, std::move (d
),
1165 m_saved_diagnostics
.length ());
1166 m_saved_diagnostics
.safe_push (sd
);
1167 ploc
.m_enode
->add_diagnostic (sd
);
1169 log ("adding saved diagnostic %i at SN %i to EN %i: %qs",
1171 ploc
.m_snode
->m_index
, ploc
.m_enode
->m_index
, sd
->m_d
->get_kind ());
1175 /* Queue pending_diagnostic D at ENODE for later emission.
1176 Return true/false signifying if the diagnostic was actually added.
1177 Take ownership of D (or delete it). */
1180 diagnostic_manager::add_diagnostic (const pending_location
&ploc
,
1181 std::unique_ptr
<pending_diagnostic
> d
)
1183 gcc_assert (ploc
.m_enode
);
1184 return add_diagnostic (NULL
, ploc
, NULL_TREE
, NULL
, 0, std::move (d
));
1187 /* Add PN to the most recent saved_diagnostic. */
1190 diagnostic_manager::add_note (std::unique_ptr
<pending_note
> pn
)
1192 LOG_FUNC (get_logger ());
1195 /* Get most recent saved_diagnostic. */
1196 gcc_assert (m_saved_diagnostics
.length () > 0);
1197 saved_diagnostic
*sd
= m_saved_diagnostics
[m_saved_diagnostics
.length () - 1];
1198 sd
->add_note (std::move (pn
));
1201 /* Add EVENT to the most recent saved_diagnostic. */
1204 diagnostic_manager::add_event (std::unique_ptr
<checker_event
> event
)
1206 LOG_FUNC (get_logger ());
1209 /* Get most recent saved_diagnostic. */
1210 gcc_assert (m_saved_diagnostics
.length () > 0);
1211 saved_diagnostic
*sd
= m_saved_diagnostics
[m_saved_diagnostics
.length () - 1];
1212 sd
->add_event (std::move (event
));
1215 /* Return a new json::object of the form
1216 {"diagnostics" : [obj for saved_diagnostic]}. */
1219 diagnostic_manager::to_json () const
1221 json::object
*dm_obj
= new json::object ();
1224 json::array
*sd_arr
= new json::array ();
1226 saved_diagnostic
*sd
;
1227 FOR_EACH_VEC_ELT (m_saved_diagnostics
, i
, sd
)
1228 sd_arr
->append (sd
->to_json ());
1229 dm_obj
->set ("diagnostics", sd_arr
);
1235 /* A class for identifying sets of duplicated pending_diagnostic.
1237 We want to find the simplest saved_diagnostic amongst those that share a
1243 dedupe_key (const saved_diagnostic
&sd
)
1244 : m_sd (sd
), m_stmt (sd
.m_stmt
), m_loc (sd
.m_loc
)
1246 gcc_assert (m_stmt
|| m_loc
!= UNKNOWN_LOCATION
);
1249 hashval_t
hash () const
1251 inchash::hash hstate
;
1252 hstate
.add_ptr (m_stmt
);
1254 return hstate
.end ();
1256 bool operator== (const dedupe_key
&other
) const
1258 return (m_sd
== other
.m_sd
1259 && m_stmt
== other
.m_stmt
1260 && m_loc
== other
.m_loc
);
1263 location_t
get_location () const
1265 if (m_loc
!= UNKNOWN_LOCATION
)
1267 gcc_assert (m_stmt
);
1268 return m_stmt
->location
;
1271 /* A qsort comparator for use by dedupe_winners::emit_best
1272 to sort them into location_t order. */
1275 comparator (const void *p1
, const void *p2
)
1277 const dedupe_key
*pk1
= *(const dedupe_key
* const *)p1
;
1278 const dedupe_key
*pk2
= *(const dedupe_key
* const *)p2
;
1280 location_t loc1
= pk1
->get_location ();
1281 location_t loc2
= pk2
->get_location ();
1283 if (int cmp
= linemap_compare_locations (line_table
, loc2
, loc1
))
1285 if (int cmp
= ((int)pk1
->m_sd
.get_epath_length ()
1286 - (int)pk2
->m_sd
.get_epath_length ()))
1288 if (int cmp
= strcmp (pk1
->m_sd
.m_d
->get_kind (),
1289 pk2
->m_sd
.m_d
->get_kind ()))
1294 const saved_diagnostic
&m_sd
;
1295 const gimple
*m_stmt
;
1299 /* Traits for use by dedupe_winners. */
1301 class dedupe_hash_map_traits
1304 typedef const dedupe_key
*key_type
;
1305 typedef saved_diagnostic
*value_type
;
1306 typedef saved_diagnostic
*compare_type
;
1308 static inline hashval_t
hash (const key_type
&v
)
1312 static inline bool equal_keys (const key_type
&k1
, const key_type
&k2
)
1316 template <typename T
>
1317 static inline void remove (T
&)
1321 template <typename T
>
1322 static inline void mark_deleted (T
&entry
)
1324 entry
.m_key
= reinterpret_cast<key_type
> (1);
1326 template <typename T
>
1327 static inline void mark_empty (T
&entry
)
1331 template <typename T
>
1332 static inline bool is_deleted (const T
&entry
)
1334 return entry
.m_key
== reinterpret_cast<key_type
> (1);
1336 template <typename T
>
1337 static inline bool is_empty (const T
&entry
)
1339 return entry
.m_key
== NULL
;
1341 static const bool empty_zero_p
= true;
1344 /* A class for deduplicating diagnostics and finding (and emitting) the
1345 best saved_diagnostic within each partition. */
1347 class dedupe_winners
1352 /* Delete all keys, but not the saved_diagnostics. */
1353 for (map_t::iterator iter
= m_map
.begin ();
1354 iter
!= m_map
.end ();
1356 delete (*iter
).first
;
1359 /* Determine an exploded_path for SD using PF and, if it's feasible,
1360 determine if SD is the best seen so far for its dedupe_key.
1361 Record the winning SD for each dedupe_key. */
1363 void add (logger
*logger
,
1365 saved_diagnostic
*sd
)
1367 /* Determine best epath for SD. */
1368 if (!sd
->calc_best_epath (pf
))
1371 dedupe_key
*key
= new dedupe_key (*sd
);
1372 if (saved_diagnostic
**slot
= m_map
.get (key
))
1375 logger
->log ("already have this dedupe_key");
1377 saved_diagnostic
*cur_best_sd
= *slot
;
1379 if (sd
->get_epath_length () < cur_best_sd
->get_epath_length ())
1381 /* We've got a shorter path for the key; replace
1382 the current candidate, marking it as a duplicate of SD. */
1384 logger
->log ("length %i is better than existing length %i;"
1385 " taking over this dedupe_key",
1386 sd
->get_epath_length (),
1387 cur_best_sd
->get_epath_length ());
1388 sd
->add_duplicate (cur_best_sd
);
1392 /* We haven't beaten the current best candidate; add SD
1393 as a duplicate of it. */
1396 logger
->log ("length %i isn't better than existing length %i;"
1397 " dropping this candidate",
1398 sd
->get_epath_length (),
1399 cur_best_sd
->get_epath_length ());
1400 cur_best_sd
->add_duplicate (sd
);
1406 /* This is the first candidate for this key. */
1407 m_map
.put (key
, sd
);
1409 logger
->log ("first candidate for this dedupe_key");
1413 /* Handle interactions between the dedupe winners, so that some
1414 diagnostics can supercede others (of different kinds).
1416 We want use-after-free to supercede use-of-unitialized-value,
1417 so that if we have these at the same stmt, we don't emit
1418 a use-of-uninitialized, just the use-after-free. */
1420 void handle_interactions (diagnostic_manager
*dm
)
1422 LOG_SCOPE (dm
->get_logger ());
1423 auto_vec
<const dedupe_key
*> superceded
;
1424 for (auto outer
: m_map
)
1426 const saved_diagnostic
*outer_sd
= outer
.second
;
1427 for (auto inner
: m_map
)
1429 const saved_diagnostic
*inner_sd
= inner
.second
;
1430 if (inner_sd
->supercedes_p (*outer_sd
))
1432 superceded
.safe_push (outer
.first
);
1433 if (dm
->get_logger ())
1434 dm
->log ("sd[%i] \"%s\" superceded by sd[%i] \"%s\"",
1435 outer_sd
->get_index (), outer_sd
->m_d
->get_kind (),
1436 inner_sd
->get_index (), inner_sd
->m_d
->get_kind ());
1441 for (auto iter
: superceded
)
1442 m_map
.remove (iter
);
1445 /* Emit the simplest diagnostic within each set. */
1447 void emit_best (diagnostic_manager
*dm
,
1448 const exploded_graph
&eg
)
1450 LOG_SCOPE (dm
->get_logger ());
1452 /* Get keys into a vec for sorting. */
1453 auto_vec
<const dedupe_key
*> keys (m_map
.elements ());
1454 for (map_t::iterator iter
= m_map
.begin ();
1455 iter
!= m_map
.end ();
1457 keys
.quick_push ((*iter
).first
);
1459 dm
->log ("# keys after de-duplication: %i", keys
.length ());
1461 /* Sort into a good emission order. */
1462 keys
.qsort (dedupe_key::comparator
);
1464 /* Emit the best saved_diagnostics for each key. */
1466 const dedupe_key
*key
;
1467 FOR_EACH_VEC_ELT (keys
, i
, key
)
1469 saved_diagnostic
**slot
= m_map
.get (key
);
1471 saved_diagnostic
*sd
= *slot
;
1472 dm
->emit_saved_diagnostic (eg
, *sd
);
1477 /* This maps from each dedupe_key to a current best saved_diagnostic. */
1479 typedef hash_map
<const dedupe_key
*, saved_diagnostic
*,
1480 dedupe_hash_map_traits
> map_t
;
1484 /* Emit all saved diagnostics. */
1487 diagnostic_manager::emit_saved_diagnostics (const exploded_graph
&eg
)
1489 LOG_SCOPE (get_logger ());
1490 auto_timevar
tv (TV_ANALYZER_DIAGNOSTICS
);
1491 log ("# saved diagnostics: %i", m_saved_diagnostics
.length ());
1492 log ("# disabled diagnostics: %i", m_num_disabled_diagnostics
);
1496 saved_diagnostic
*sd
;
1497 FOR_EACH_VEC_ELT (m_saved_diagnostics
, i
, sd
)
1498 log ("[%i] sd: %qs at EN: %i, SN: %i",
1499 i
, sd
->m_d
->get_kind (), sd
->m_enode
->m_index
,
1500 sd
->m_snode
->m_index
);
1503 if (m_saved_diagnostics
.length () == 0)
1506 /* Compute the shortest_paths once, sharing it between all diagnostics. */
1507 epath_finder
pf (eg
);
1509 /* Iterate through all saved diagnostics, adding them to a dedupe_winners
1510 instance. This partitions the saved diagnostics by dedupe_key,
1511 generating exploded_paths for them, and retaining the best one in each
1513 dedupe_winners best_candidates
;
1516 saved_diagnostic
*sd
;
1517 FOR_EACH_VEC_ELT (m_saved_diagnostics
, i
, sd
)
1518 best_candidates
.add (get_logger (), &pf
, sd
);
1520 best_candidates
.handle_interactions (this);
1522 /* For each dedupe-key, call emit_saved_diagnostic on the "best"
1523 saved_diagnostic. */
1524 best_candidates
.emit_best (this, eg
);
1527 /* Custom subclass of diagnostic_metadata which, for SARIF output,
1528 populates the property bag of the diagnostic's "result" object
1529 with information from the saved_diagnostic and the
1530 pending_diagnostic. */
1532 class pending_diagnostic_metadata
: public diagnostic_metadata
1535 pending_diagnostic_metadata (const saved_diagnostic
&sd
)
1541 maybe_add_sarif_properties (sarif_object
&result_obj
) const override
1543 m_sd
.maybe_add_sarif_properties (result_obj
);
1547 const saved_diagnostic
&m_sd
;
1550 /* Given a saved_diagnostic SD with m_best_epath through EG,
1551 create an checker_path of suitable events and use it to call
1552 SD's underlying pending_diagnostic "emit" vfunc to emit a diagnostic. */
1555 diagnostic_manager::emit_saved_diagnostic (const exploded_graph
&eg
,
1556 saved_diagnostic
&sd
)
1558 LOG_SCOPE (get_logger ());
1559 log ("sd[%i]: %qs at SN: %i",
1560 sd
.get_index (), sd
.m_d
->get_kind (), sd
.m_snode
->m_index
);
1561 log ("num dupes: %i", sd
.get_num_dupes ());
1563 pretty_printer
*pp
= global_dc
->printer
->clone ();
1565 const exploded_path
*epath
= sd
.get_best_epath ();
1568 /* Precompute all enodes from which the diagnostic is reachable. */
1569 path_builder
pb (eg
, *epath
, sd
.get_feasibility_problem (), sd
);
1571 /* This is the diagnostic_path subclass that will be built for
1573 checker_path
emission_path (get_logger ());
1575 /* Populate emission_path with a full description of EPATH. */
1576 build_emission_path (pb
, *epath
, &emission_path
);
1578 /* Now prune it to just cover the most pertinent events. */
1579 prune_path (&emission_path
, sd
.m_sm
, sd
.m_sval
, sd
.m_state
);
1581 /* Add any saved events to the path, giving contextual information
1582 about what the analyzer was simulating as the diagnostic was
1583 generated. These don't get pruned, as they are probably pertinent. */
1584 sd
.add_any_saved_events (emission_path
);
1586 /* Add a final event to the path, covering the diagnostic itself.
1587 We use the final enode from the epath, which might be different from
1588 the sd.m_enode, as the dedupe code doesn't care about enodes, just
1590 sd
.m_d
->add_final_event (sd
.m_sm
, epath
->get_final_enode (), sd
.m_stmt
,
1591 sd
.m_var
, sd
.m_state
, &emission_path
);
1593 /* The "final" event might not be final; if the saved_diagnostic has a
1594 trailing eedge stashed, add any events for it. This is for use
1595 in handling longjmp, to show where a longjmp is rewinding to. */
1596 if (sd
.m_trailing_eedge
)
1597 add_events_for_eedge (pb
, *sd
.m_trailing_eedge
, &emission_path
, NULL
);
1599 emission_path
.inject_any_inlined_call_events (get_logger ());
1601 emission_path
.prepare_for_emission (sd
.m_d
.get ());
1603 location_t loc
= sd
.m_loc
;
1604 if (loc
== UNKNOWN_LOCATION
)
1605 loc
= get_emission_location (sd
.m_stmt
, sd
.m_snode
->m_fun
, *sd
.m_d
);
1607 /* Allow the pending_diagnostic to fix up the locations of events. */
1608 emission_path
.fixup_locations (sd
.m_d
.get ());
1610 gcc_rich_location
rich_loc (loc
);
1611 rich_loc
.set_path (&emission_path
);
1613 auto_diagnostic_group d
;
1614 auto_cfun
sentinel (sd
.m_snode
->m_fun
);
1615 pending_diagnostic_metadata
m (sd
);
1616 diagnostic_emission_context
diag_ctxt (sd
, rich_loc
, m
, get_logger ());
1617 if (sd
.m_d
->emit (diag_ctxt
))
1619 sd
.emit_any_notes ();
1621 unsigned num_dupes
= sd
.get_num_dupes ();
1622 if (flag_analyzer_show_duplicate_count
&& num_dupes
> 0)
1623 inform_n (loc
, num_dupes
,
1624 "%i duplicate", "%i duplicates",
1626 if (flag_dump_analyzer_exploded_paths
)
1628 auto_timevar
tv (TV_ANALYZER_DUMP
);
1630 pp_printf (&pp
, "%s.%i.%s.epath.txt",
1631 dump_base_name
, sd
.get_index (), sd
.m_d
->get_kind ());
1632 char *filename
= xstrdup (pp_formatted_text (&pp
));
1633 epath
->dump_to_file (filename
, eg
.get_ext_state ());
1634 inform (loc
, "exploded path written to %qs", filename
);
1641 /* Emit a "path" of events to EMISSION_PATH describing the exploded path
1645 diagnostic_manager::build_emission_path (const path_builder
&pb
,
1646 const exploded_path
&epath
,
1647 checker_path
*emission_path
) const
1649 LOG_SCOPE (get_logger ());
1651 interesting_t interest
;
1652 pb
.get_pending_diagnostic ()->mark_interesting_stuff (&interest
);
1654 /* Add region creation events for any globals of interest, at the
1655 beginning of the path. */
1657 for (auto reg
: interest
.m_region_creation
)
1658 switch (reg
->get_memory_space ())
1663 case MEMSPACE_GLOBALS
:
1664 case MEMSPACE_READONLY_DATA
:
1666 const region
*base_reg
= reg
->get_base_region ();
1667 if (tree decl
= base_reg
->maybe_get_decl ())
1669 && DECL_SOURCE_LOCATION (decl
) != UNKNOWN_LOCATION
)
1671 emission_path
->add_region_creation_events
1672 (pb
.get_pending_diagnostic (),
1674 event_loc_info (DECL_SOURCE_LOCATION (decl
),
1683 /* Walk EPATH, adding events as appropriate. */
1684 for (unsigned i
= 0; i
< epath
.m_edges
.length (); i
++)
1686 const exploded_edge
*eedge
= epath
.m_edges
[i
];
1687 add_events_for_eedge (pb
, *eedge
, emission_path
, &interest
);
1689 add_event_on_final_node (pb
, epath
.get_final_enode (),
1690 emission_path
, &interest
);
1693 /* Emit a region_creation_event when requested on the last statement in
1696 If a region_creation_event should be emitted on the last statement of the
1697 path, we need to peek to the successors to get whether the final enode
1702 diagnostic_manager::add_event_on_final_node (const path_builder
&pb
,
1703 const exploded_node
*final_enode
,
1704 checker_path
*emission_path
,
1705 interesting_t
*interest
) const
1707 const program_point
&src_point
= final_enode
->get_point ();
1708 const int src_stack_depth
= src_point
.get_stack_depth ();
1709 const program_state
&src_state
= final_enode
->get_state ();
1710 const region_model
*src_model
= src_state
.m_region_model
;
1714 FOR_EACH_VEC_ELT (final_enode
->m_succs
, j
, e
)
1716 exploded_node
*dst
= e
->m_dest
;
1717 const program_state
&dst_state
= dst
->get_state ();
1718 const region_model
*dst_model
= dst_state
.m_region_model
;
1719 if (src_model
->get_dynamic_extents ()
1720 != dst_model
->get_dynamic_extents ())
1724 bool emitted
= false;
1725 FOR_EACH_VEC_ELT (interest
->m_region_creation
, i
, reg
)
1727 const region
*base_reg
= reg
->get_base_region ();
1728 const svalue
*old_extents
1729 = src_model
->get_dynamic_extents (base_reg
);
1730 const svalue
*new_extents
1731 = dst_model
->get_dynamic_extents (base_reg
);
1732 if (old_extents
== NULL
&& new_extents
!= NULL
)
1733 switch (base_reg
->get_kind ())
1737 case RK_HEAP_ALLOCATED
:
1739 emission_path
->add_region_creation_events
1740 (pb
.get_pending_diagnostic (),
1743 event_loc_info (src_point
.get_location (),
1744 src_point
.get_fndecl (),
1757 /* Subclass of state_change_visitor that creates state_change_event
1760 class state_change_event_creator
: public state_change_visitor
1763 state_change_event_creator (const path_builder
&pb
,
1764 const exploded_edge
&eedge
,
1765 checker_path
*emission_path
)
1768 m_emission_path (emission_path
)
1771 bool on_global_state_change (const state_machine
&sm
,
1772 state_machine::state_t src_sm_val
,
1773 state_machine::state_t dst_sm_val
)
1776 if (&sm
!= m_pb
.get_sm ())
1778 const exploded_node
*src_node
= m_eedge
.m_src
;
1779 const program_point
&src_point
= src_node
->get_point ();
1780 const int src_stack_depth
= src_point
.get_stack_depth ();
1781 const exploded_node
*dst_node
= m_eedge
.m_dest
;
1782 const gimple
*stmt
= src_point
.get_stmt ();
1783 const supernode
*supernode
= src_point
.get_supernode ();
1784 const program_state
&dst_state
= dst_node
->get_state ();
1786 int stack_depth
= src_stack_depth
;
1788 m_emission_path
->add_event
1789 (make_unique
<state_change_event
> (supernode
,
1802 bool on_state_change (const state_machine
&sm
,
1803 state_machine::state_t src_sm_val
,
1804 state_machine::state_t dst_sm_val
,
1806 const svalue
*dst_origin_sval
) final override
1808 if (&sm
!= m_pb
.get_sm ())
1810 const exploded_node
*src_node
= m_eedge
.m_src
;
1811 const program_point
&src_point
= src_node
->get_point ();
1812 const int src_stack_depth
= src_point
.get_stack_depth ();
1813 const exploded_node
*dst_node
= m_eedge
.m_dest
;
1814 const gimple
*stmt
= src_point
.get_stmt ();
1815 const supernode
*supernode
= src_point
.get_supernode ();
1816 const program_state
&dst_state
= dst_node
->get_state ();
1818 int stack_depth
= src_stack_depth
;
1821 && m_eedge
.m_sedge
->m_kind
== SUPEREDGE_CFG_EDGE
)
1823 supernode
= src_point
.get_supernode ();
1824 stmt
= supernode
->get_last_stmt ();
1825 stack_depth
= src_stack_depth
;
1828 /* Bulletproofing for state changes at calls/returns;
1829 TODO: is there a better way? */
1833 m_emission_path
->add_event
1834 (make_unique
<state_change_event
> (supernode
,
1847 const path_builder
&m_pb
;
1848 const exploded_edge
&m_eedge
;
1849 checker_path
*m_emission_path
;
1852 /* Compare SRC_STATE and DST_STATE (which use EXT_STATE), and call
1853 VISITOR's on_state_change for every sm-state change that occurs
1854 to a tree, and on_global_state_change for every global state change
1857 This determines the state changes that ought to be reported to
1858 the user: a combination of the effects of changes to sm_state_map
1859 (which maps svalues to sm-states), and of region_model changes
1860 (which map trees to svalues).
1862 Bail out early and return true if any call to on_global_state_change
1863 or on_state_change returns true, otherwise return false.
1865 This is split out to make it easier to experiment with changes to
1866 exploded_node granularity (so that we can observe what state changes
1867 lead to state_change_events being emitted). */
1870 for_each_state_change (const program_state
&src_state
,
1871 const program_state
&dst_state
,
1872 const extrinsic_state
&ext_state
,
1873 state_change_visitor
*visitor
)
1875 gcc_assert (src_state
.m_checker_states
.length ()
1876 == ext_state
.get_num_checkers ());
1877 gcc_assert (dst_state
.m_checker_states
.length ()
1878 == ext_state
.get_num_checkers ());
1879 for (unsigned i
= 0; i
< ext_state
.get_num_checkers (); i
++)
1881 const state_machine
&sm
= ext_state
.get_sm (i
);
1882 const sm_state_map
&src_smap
= *src_state
.m_checker_states
[i
];
1883 const sm_state_map
&dst_smap
= *dst_state
.m_checker_states
[i
];
1885 /* Add events for any global state changes. */
1886 if (src_smap
.get_global_state () != dst_smap
.get_global_state ())
1887 if (visitor
->on_global_state_change (sm
,
1888 src_smap
.get_global_state (),
1889 dst_smap
.get_global_state ()))
1892 /* Add events for per-svalue state changes. */
1893 for (sm_state_map::iterator_t iter
= dst_smap
.begin ();
1894 iter
!= dst_smap
.end ();
1897 const svalue
*sval
= (*iter
).first
;
1898 state_machine::state_t dst_sm_val
= (*iter
).second
.m_state
;
1899 state_machine::state_t src_sm_val
1900 = src_smap
.get_state (sval
, ext_state
);
1901 if (dst_sm_val
!= src_sm_val
)
1903 const svalue
*origin_sval
= (*iter
).second
.m_origin
;
1904 if (visitor
->on_state_change (sm
, src_sm_val
, dst_sm_val
,
1913 /* An sm_context for adding state_change_event on assignments to NULL,
1914 where the default state isn't m_start. Storing such state in the
1915 sm_state_map would lead to bloat of the exploded_graph, so we want
1916 to leave it as a default state, and inject state change events here
1917 when we have a diagnostic.
1918 Find transitions of constants, for handling on_zero_assignment. */
1920 struct null_assignment_sm_context
: public sm_context
1922 null_assignment_sm_context (int sm_idx
,
1923 const state_machine
&sm
,
1924 const program_state
*old_state
,
1925 const program_state
*new_state
,
1927 const program_point
*point
,
1928 checker_path
*emission_path
,
1929 const extrinsic_state
&ext_state
)
1930 : sm_context (sm_idx
, sm
), m_old_state (old_state
), m_new_state (new_state
),
1931 m_stmt (stmt
), m_point (point
), m_emission_path (emission_path
),
1932 m_ext_state (ext_state
)
1936 tree
get_fndecl_for_call (const gcall */
*call*/
) final override
1941 state_machine::state_t
get_state (const gimple
*stmt ATTRIBUTE_UNUSED
,
1942 tree var
) final override
1944 const svalue
*var_old_sval
1945 = m_old_state
->m_region_model
->get_rvalue (var
, NULL
);
1946 const sm_state_map
*old_smap
= m_old_state
->m_checker_states
[m_sm_idx
];
1948 state_machine::state_t current
1949 = old_smap
->get_state (var_old_sval
, m_ext_state
);
1954 state_machine::state_t
get_state (const gimple
*stmt ATTRIBUTE_UNUSED
,
1955 const svalue
*sval
) final override
1957 const sm_state_map
*old_smap
= m_old_state
->m_checker_states
[m_sm_idx
];
1958 state_machine::state_t current
= old_smap
->get_state (sval
, m_ext_state
);
1962 void set_next_state (const gimple
*stmt
,
1964 state_machine::state_t to
,
1965 tree origin ATTRIBUTE_UNUSED
) final override
1967 state_machine::state_t from
= get_state (stmt
, var
);
1968 if (from
!= m_sm
.get_start_state ())
1970 if (!is_transition_to_null (to
))
1973 const svalue
*var_new_sval
1974 = m_new_state
->m_region_model
->get_rvalue (var
, NULL
);
1976 const supernode
*supernode
= m_point
->get_supernode ();
1977 int stack_depth
= m_point
->get_stack_depth ();
1979 m_emission_path
->add_event
1980 (make_unique
<state_change_event
> (supernode
,
1991 void set_next_state (const gimple
*stmt
,
1993 state_machine::state_t to
,
1994 tree origin ATTRIBUTE_UNUSED
) final override
1996 state_machine::state_t from
= get_state (stmt
, sval
);
1997 if (from
!= m_sm
.get_start_state ())
1999 if (!is_transition_to_null (to
))
2002 const supernode
*supernode
= m_point
->get_supernode ();
2003 int stack_depth
= m_point
->get_stack_depth ();
2005 m_emission_path
->add_event
2006 (make_unique
<state_change_event
> (supernode
,
2017 void warn (const supernode
*, const gimple
*,
2018 tree
, std::unique_ptr
<pending_diagnostic
>) final override
2021 void warn (const supernode
*, const gimple
*,
2022 const svalue
*, std::unique_ptr
<pending_diagnostic
>) final override
2026 tree
get_diagnostic_tree (tree expr
) final override
2031 tree
get_diagnostic_tree (const svalue
*sval
) final override
2033 return m_new_state
->m_region_model
->get_representative_tree (sval
);
2036 state_machine::state_t
get_global_state () const final override
2041 void set_global_state (state_machine::state_t
) final override
2046 void clear_all_per_svalue_state () final override
2051 void on_custom_transition (custom_transition
*) final override
2055 tree
is_zero_assignment (const gimple
*stmt
) final override
2057 const gassign
*assign_stmt
= dyn_cast
<const gassign
*> (stmt
);
2060 if (const svalue
*sval
2061 = m_new_state
->m_region_model
->get_gassign_result (assign_stmt
, NULL
))
2062 if (tree cst
= sval
->maybe_get_constant ())
2064 return gimple_assign_lhs (assign_stmt
);
2068 const program_state
*get_old_program_state () const final override
2072 const program_state
*get_new_program_state () const final override
2077 /* We only care about transitions to the "null" state
2078 within sm-malloc. Special-case this. */
2079 static bool is_transition_to_null (state_machine::state_t s
)
2081 return !strcmp (s
->get_name (), "null");
2084 const program_state
*m_old_state
;
2085 const program_state
*m_new_state
;
2086 const gimple
*m_stmt
;
2087 const program_point
*m_point
;
2088 checker_path
*m_emission_path
;
2089 const extrinsic_state
&m_ext_state
;
2092 /* Subroutine of diagnostic_manager::build_emission_path.
2093 Add any events for EEDGE to EMISSION_PATH. */
2096 diagnostic_manager::add_events_for_eedge (const path_builder
&pb
,
2097 const exploded_edge
&eedge
,
2098 checker_path
*emission_path
,
2099 interesting_t
*interest
) const
2101 const exploded_node
*src_node
= eedge
.m_src
;
2102 const program_point
&src_point
= src_node
->get_point ();
2103 const int src_stack_depth
= src_point
.get_stack_depth ();
2104 const exploded_node
*dst_node
= eedge
.m_dest
;
2105 const program_point
&dst_point
= dst_node
->get_point ();
2106 const int dst_stack_depth
= dst_point
.get_stack_depth ();
2109 get_logger ()->start_log_line ();
2110 pretty_printer
*pp
= get_logger ()->get_printer ();
2111 pp_printf (pp
, "EN %i -> EN %i: ",
2112 eedge
.m_src
->m_index
,
2113 eedge
.m_dest
->m_index
);
2114 src_point
.print (pp
, format (false));
2115 pp_string (pp
, "-> ");
2116 dst_point
.print (pp
, format (false));
2117 get_logger ()->end_log_line ();
2119 const program_state
&src_state
= src_node
->get_state ();
2120 const program_state
&dst_state
= dst_node
->get_state ();
2122 /* Add state change events for the states that have changed.
2123 We add these before events for superedges, so that if we have a
2124 state_change_event due to following an edge, we'll get this sequence
2130 | (1) assuming 'ptr' is non-NULL (state_change_event)
2131 | (2) following 'false' branch... (start_cfg_edge_event)
2133 | do_something (ptr);
2134 | ~~~~~~~~~~~~~^~~~~
2136 | (3) ...to here (end_cfg_edge_event). */
2137 state_change_event_creator
visitor (pb
, eedge
, emission_path
);
2138 for_each_state_change (src_state
, dst_state
, pb
.get_ext_state (),
2141 /* Allow non-standard edges to add events, e.g. when rewinding from
2142 longjmp to a setjmp. */
2143 if (eedge
.m_custom_info
)
2144 eedge
.m_custom_info
->add_events_to_path (emission_path
, eedge
);
2146 /* Add events for superedges, function entries, and for statements. */
2147 switch (dst_point
.get_kind ())
2151 case PK_BEFORE_SUPERNODE
:
2152 if (src_point
.get_kind () == PK_AFTER_SUPERNODE
)
2155 add_events_for_superedge (pb
, eedge
, emission_path
);
2157 /* Add function entry events. */
2158 if (dst_point
.get_supernode ()->entry_p ())
2160 pb
.get_pending_diagnostic ()->add_function_entry_event
2161 (eedge
, emission_path
);
2162 /* Create region_creation_events for on-stack regions within
2168 FOR_EACH_VEC_ELT (interest
->m_region_creation
, i
, reg
)
2169 if (const frame_region
*frame
= reg
->maybe_get_frame_region ())
2170 if (frame
->get_fndecl () == dst_point
.get_fndecl ())
2172 const region
*base_reg
= reg
->get_base_region ();
2173 if (tree decl
= base_reg
->maybe_get_decl ())
2175 && DECL_SOURCE_LOCATION (decl
) != UNKNOWN_LOCATION
)
2177 emission_path
->add_region_creation_events
2178 (pb
.get_pending_diagnostic (),
2179 reg
, dst_state
.m_region_model
,
2180 event_loc_info (DECL_SOURCE_LOCATION (decl
),
2181 dst_point
.get_fndecl (),
2189 case PK_BEFORE_STMT
:
2191 const gimple
*stmt
= dst_point
.get_stmt ();
2192 const gcall
*call
= dyn_cast
<const gcall
*> (stmt
);
2193 if (call
&& is_setjmp_call_p (call
))
2194 emission_path
->add_event
2195 (make_unique
<setjmp_event
> (event_loc_info (stmt
->location
,
2196 dst_point
.get_fndecl (),
2201 emission_path
->add_event
2202 (make_unique
<statement_event
> (stmt
,
2203 dst_point
.get_fndecl (),
2204 dst_stack_depth
, dst_state
));
2206 /* Create state change events for assignment to NULL.
2207 Iterate through the stmts in dst_enode, adding state change
2209 if (dst_state
.m_region_model
)
2211 log_scope
s (get_logger (), "processing run of stmts");
2212 program_state
iter_state (dst_state
);
2213 program_point
iter_point (dst_point
);
2216 const gimple
*stmt
= iter_point
.get_stmt ();
2217 if (const gassign
*assign
= dyn_cast
<const gassign
*> (stmt
))
2219 const extrinsic_state
&ext_state
= pb
.get_ext_state ();
2220 program_state
old_state (iter_state
);
2221 iter_state
.m_region_model
->on_assignment (assign
, NULL
);
2222 for (unsigned i
= 0; i
< ext_state
.get_num_checkers (); i
++)
2224 const state_machine
&sm
= ext_state
.get_sm (i
);
2225 null_assignment_sm_context
sm_ctxt (i
, sm
,
2231 pb
.get_ext_state ());
2232 sm
.on_stmt (&sm_ctxt
, dst_point
.get_supernode (), stmt
);
2233 // TODO: what about phi nodes?
2236 iter_point
.next_stmt ();
2237 if (iter_point
.get_kind () == PK_AFTER_SUPERNODE
2238 || (dst_node
->m_succs
.length () > 1
2240 == dst_node
->m_succs
[0]->m_dest
->get_point ())))
2249 /* Look for changes in dynamic extents, which will identify
2250 the creation of heap-based regions and alloca regions. */
2253 const region_model
*src_model
= src_state
.m_region_model
;
2254 const region_model
*dst_model
= dst_state
.m_region_model
;
2255 if (src_model
->get_dynamic_extents ()
2256 != dst_model
->get_dynamic_extents ())
2260 FOR_EACH_VEC_ELT (interest
->m_region_creation
, i
, reg
)
2262 const region
*base_reg
= reg
->get_base_region ();
2263 const svalue
*old_extents
2264 = src_model
->get_dynamic_extents (base_reg
);
2265 const svalue
*new_extents
2266 = dst_model
->get_dynamic_extents (base_reg
);
2267 if (old_extents
== NULL
&& new_extents
!= NULL
)
2268 switch (base_reg
->get_kind ())
2272 case RK_HEAP_ALLOCATED
:
2274 emission_path
->add_region_creation_events
2275 (pb
.get_pending_diagnostic (),
2277 event_loc_info (src_point
.get_location (),
2278 src_point
.get_fndecl (),
2287 if (pb
.get_feasibility_problem ()
2288 && &pb
.get_feasibility_problem ()->m_eedge
== &eedge
)
2291 pp_format_decoder (&pp
) = default_tree_printer
;
2293 "this path would have been rejected as infeasible"
2295 pb
.get_feasibility_problem ()->dump_to_pp (&pp
);
2296 emission_path
->add_event
2297 (make_unique
<precanned_custom_event
>
2298 (event_loc_info (dst_point
.get_location (),
2299 dst_point
.get_fndecl (),
2301 pp_formatted_text (&pp
)));
2305 /* Return true if EEDGE is a significant edge in the path to the diagnostic
2308 Consider all of the sibling out-eedges from the same source enode
2310 If there's no path from the destinations of those eedges to the
2311 diagnostic enode, then we have to take this eedge and thus it's
2314 Conversely if there is a path from the destination of any other sibling
2315 eedge to the diagnostic enode, then this edge is insignificant.
2317 Example 1: redundant if-else:
2325 D is reachable by either B or C, so neither of these edges
2328 Example 2: pertinent if-else:
2333 (C) [NECESSARY CONDITION] | |
2334 (D) [POSSIBLE DIAGNOSTIC] D1 D2
2336 D becomes D1 and D2 in the exploded graph, where the diagnostic occurs
2337 at D2. D2 is only reachable via C, so the A -> C edge is significant.
2339 Example 3: redundant loop:
2341 (A) while (...) +-->A
2347 D is reachable from both B and C, so the A->C edge is not significant. */
2350 diagnostic_manager::significant_edge_p (const path_builder
&pb
,
2351 const exploded_edge
&eedge
) const
2354 exploded_edge
*sibling
;
2355 FOR_EACH_VEC_ELT (eedge
.m_src
->m_succs
, i
, sibling
)
2357 if (sibling
== &eedge
)
2359 if (pb
.reachable_from_p (sibling
->m_dest
))
2362 get_logger ()->log (" edge EN: %i -> EN: %i is insignificant as"
2363 " EN: %i is also reachable via"
2364 " EN: %i -> EN: %i",
2365 eedge
.m_src
->m_index
, eedge
.m_dest
->m_index
,
2366 pb
.get_diag_node ()->m_index
,
2367 sibling
->m_src
->m_index
,
2368 sibling
->m_dest
->m_index
);
2376 /* Subroutine of diagnostic_manager::add_events_for_eedge
2377 where EEDGE has an underlying superedge i.e. a CFG edge,
2378 or an interprocedural call/return.
2379 Add any events for the superedge to EMISSION_PATH. */
2382 diagnostic_manager::add_events_for_superedge (const path_builder
&pb
,
2383 const exploded_edge
&eedge
,
2384 checker_path
*emission_path
)
2387 gcc_assert (eedge
.m_sedge
);
2389 /* Give diagnostics an opportunity to override this function. */
2390 pending_diagnostic
*pd
= pb
.get_pending_diagnostic ();
2391 if (pd
->maybe_add_custom_events_for_superedge (eedge
, emission_path
))
2394 /* Don't add events for insignificant edges at verbosity levels below 3. */
2395 if (m_verbosity
< 3)
2396 if (!significant_edge_p (pb
, eedge
))
2399 const exploded_node
*src_node
= eedge
.m_src
;
2400 const program_point
&src_point
= src_node
->get_point ();
2401 const exploded_node
*dst_node
= eedge
.m_dest
;
2402 const program_point
&dst_point
= dst_node
->get_point ();
2403 const int src_stack_depth
= src_point
.get_stack_depth ();
2404 const int dst_stack_depth
= dst_point
.get_stack_depth ();
2405 const gimple
*last_stmt
= src_point
.get_supernode ()->get_last_stmt ();
2407 switch (eedge
.m_sedge
->m_kind
)
2409 case SUPEREDGE_CFG_EDGE
:
2411 emission_path
->add_event
2412 (make_unique
<start_cfg_edge_event
>
2414 event_loc_info (last_stmt
? last_stmt
->location
: UNKNOWN_LOCATION
,
2415 src_point
.get_fndecl (),
2417 emission_path
->add_event
2418 (make_unique
<end_cfg_edge_event
>
2420 event_loc_info (dst_point
.get_supernode ()->get_start_location (),
2421 dst_point
.get_fndecl (),
2426 case SUPEREDGE_CALL
:
2427 pd
->add_call_event (eedge
, emission_path
);
2430 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
2432 /* TODO: add a subclass for this, or generate events for the
2434 emission_path
->add_event
2435 (make_unique
<debug_event
> (event_loc_info (last_stmt
2436 ? last_stmt
->location
2438 src_point
.get_fndecl (),
2444 case SUPEREDGE_RETURN
:
2446 const return_superedge
*return_edge
2447 = as_a
<const return_superedge
*> (eedge
.m_sedge
);
2449 const gcall
*call_stmt
= return_edge
->get_call_stmt ();
2450 emission_path
->add_event
2451 (make_unique
<return_event
> (eedge
,
2452 event_loc_info (call_stmt
2453 ? call_stmt
->location
2455 dst_point
.get_fndecl (),
2462 /* Prune PATH, based on the verbosity level, to the most pertinent
2463 events for a diagnostic that involves VAR ending in state STATE
2464 (for state machine SM).
2466 PATH is updated in place, and the redundant checker_events are deleted.
2468 As well as deleting events, call record_critical_state on events in
2469 which state critical to the pending_diagnostic is being handled; see
2470 the comment for diagnostic_manager::prune_for_sm_diagnostic. */
2473 diagnostic_manager::prune_path (checker_path
*path
,
2474 const state_machine
*sm
,
2476 state_machine::state_t state
) const
2478 LOG_FUNC (get_logger ());
2479 path
->maybe_log (get_logger (), "path");
2480 prune_for_sm_diagnostic (path
, sm
, sval
, state
);
2481 prune_interproc_events (path
);
2482 if (! flag_analyzer_show_events_in_system_headers
)
2483 prune_system_headers (path
);
2484 consolidate_conditions (path
);
2485 finish_pruning (path
);
2486 path
->maybe_log (get_logger (), "pruned");
2489 /* A cheap test to determine if EXPR can be the expression of interest in
2490 an sm-diagnostic, so that we can reject cases where we have a non-lvalue.
2491 We don't have always have a model when calling this, so we can't use
2492 tentative_region_model_context, so there can be false positives. */
2495 can_be_expr_of_interest_p (tree expr
)
2500 /* Reject constants. */
2501 if (CONSTANT_CLASS_P (expr
))
2504 /* Otherwise assume that it can be an lvalue. */
2508 /* First pass of diagnostic_manager::prune_path: apply verbosity level,
2509 pruning unrelated state change events.
2511 Iterate backwards through PATH, skipping state change events that aren't
2512 VAR but update the pertinent VAR when state-copying occurs.
2514 As well as deleting events, call record_critical_state on events in
2515 which state critical to the pending_diagnostic is being handled, so
2516 that the event's get_desc vfunc can potentially supply a more precise
2517 description of the event to the user.
2519 "calling 'foo' from 'bar'"
2521 "passing possibly-NULL pointer 'ptr' to 'foo' from 'bar' as param 1"
2522 when the diagnostic relates to later dereferencing 'ptr'. */
2525 diagnostic_manager::prune_for_sm_diagnostic (checker_path
*path
,
2526 const state_machine
*sm
,
2528 state_machine::state_t state
) const
2530 int idx
= path
->num_events () - 1;
2531 while (idx
>= 0 && idx
< (signed)path
->num_events ())
2533 checker_event
*base_event
= path
->get_checker_event (idx
);
2540 label_text sval_desc
= sval
->get_desc ();
2541 log ("considering event %i (%s), with sval: %qs, state: %qs",
2542 idx
, event_kind_to_string (base_event
->m_kind
),
2543 sval_desc
.get (), state
->get_name ());
2546 log ("considering event %i (%s), with global state: %qs",
2547 idx
, event_kind_to_string (base_event
->m_kind
),
2548 state
->get_name ());
2551 log ("considering event %i", idx
);
2554 switch (base_event
->m_kind
)
2560 if (m_verbosity
< 4)
2562 log ("filtering event %i: debug event", idx
);
2563 path
->delete_event (idx
);
2568 /* Don't filter custom events. */
2573 if (m_verbosity
< 4)
2575 log ("filtering event %i: statement event", idx
);
2576 path
->delete_event (idx
);
2581 case EK_REGION_CREATION
:
2582 /* Don't filter these. */
2585 case EK_FUNCTION_ENTRY
:
2586 if (m_verbosity
< 1)
2588 log ("filtering event %i: function entry", idx
);
2589 path
->delete_event (idx
);
2593 case EK_STATE_CHANGE
:
2595 state_change_event
*state_change
= (state_change_event
*)base_event
;
2596 gcc_assert (state_change
->m_dst_state
.m_region_model
);
2598 if (state_change
->m_sval
== sval
)
2600 if (state_change
->m_origin
)
2604 label_text sval_desc
= sval
->get_desc ();
2605 label_text origin_sval_desc
2606 = state_change
->m_origin
->get_desc ();
2608 " switching var of interest from %qs to %qs",
2609 idx
, sval_desc
.get (),
2610 origin_sval_desc
.get ());
2612 sval
= state_change
->m_origin
;
2614 log ("event %i: switching state of interest from %qs to %qs",
2615 idx
, state_change
->m_to
->get_name (),
2616 state_change
->m_from
->get_name ());
2617 state
= state_change
->m_from
;
2619 else if (m_verbosity
< 4)
2623 if (state_change
->m_sval
)
2625 label_text change_sval_desc
2626 = state_change
->m_sval
->get_desc ();
2629 label_text sval_desc
= sval
->get_desc ();
2630 log ("filtering event %i:"
2631 " state change to %qs unrelated to %qs",
2632 idx
, change_sval_desc
.get (),
2636 log ("filtering event %i: state change to %qs",
2637 idx
, change_sval_desc
.get ());
2640 log ("filtering event %i: global state change", idx
);
2642 path
->delete_event (idx
);
2647 case EK_START_CFG_EDGE
:
2649 cfg_edge_event
*event
= (cfg_edge_event
*)base_event
;
2651 /* TODO: is this edge significant to var?
2652 See if var can be in other states in the dest, but not
2653 in other states in the src?
2654 Must have multiple sibling edges. */
2656 if (event
->should_filter_p (m_verbosity
))
2658 log ("filtering events %i and %i: CFG edge", idx
, idx
+ 1);
2659 path
->delete_event (idx
);
2660 /* Also delete the corresponding EK_END_CFG_EDGE. */
2661 gcc_assert (path
->get_checker_event (idx
)->m_kind
2662 == EK_END_CFG_EDGE
);
2663 path
->delete_event (idx
);
2668 case EK_END_CFG_EDGE
:
2669 /* These come in pairs with EK_START_CFG_EDGE events and are
2670 filtered when their start event is filtered. */
2675 call_event
*event
= (call_event
*)base_event
;
2676 const region_model
*callee_model
2677 = event
->m_eedge
.m_dest
->get_state ().m_region_model
;
2678 const region_model
*caller_model
2679 = event
->m_eedge
.m_src
->get_state ().m_region_model
;
2680 tree callee_var
= callee_model
->get_representative_tree (sval
);
2686 const callgraph_superedge
& cg_superedge
2687 = event
->get_callgraph_superedge ();
2688 if (cg_superedge
.m_cedge
)
2690 = cg_superedge
.map_expr_from_callee_to_caller (callee_var
,
2693 caller_var
= caller_model
->get_representative_tree (sval
);
2696 caller_var
= caller_model
->get_representative_tree (sval
);
2702 label_text sval_desc
= sval
->get_desc ();
2704 " recording critical state for %qs at call"
2705 " from %qE in callee to %qE in caller",
2706 idx
, sval_desc
.get (), callee_var
, caller_var
);
2708 if (expr
.param_p ())
2709 event
->record_critical_state (caller_var
, state
);
2714 case EK_RETURN_EDGE
:
2718 return_event
*event
= (return_event
*)base_event
;
2719 const region_model
*caller_model
2720 = event
->m_eedge
.m_dest
->get_state ().m_region_model
;
2721 tree caller_var
= caller_model
->get_representative_tree (sval
);
2722 const region_model
*callee_model
2723 = event
->m_eedge
.m_src
->get_state ().m_region_model
;
2729 const callgraph_superedge
& cg_superedge
2730 = event
->get_callgraph_superedge ();
2731 if (cg_superedge
.m_cedge
)
2733 = cg_superedge
.map_expr_from_caller_to_callee (caller_var
,
2736 callee_var
= callee_model
->get_representative_tree (sval
);
2739 callee_var
= callee_model
->get_representative_tree (sval
);
2745 label_text sval_desc
= sval
->get_desc ();
2747 " recording critical state for %qs at return"
2748 " from %qE in caller to %qE in callee",
2749 idx
, sval_desc
.get (), callee_var
, callee_var
);
2751 if (expr
.return_value_p ())
2752 event
->record_critical_state (callee_var
, state
);
2758 case EK_INLINED_CALL
:
2759 /* We don't expect to see these yet, as they're added later.
2760 We'd want to keep them around. */
2764 /* TODO: only show setjmp_events that matter i.e. those for which
2765 there is a later rewind event using them. */
2766 case EK_REWIND_FROM_LONGJMP
:
2767 case EK_REWIND_TO_SETJMP
:
2771 /* Always show the final "warning" event in the path. */
2778 /* Subroutine of diagnostic_manager::prune_for_sm_diagnostic.
2779 If *EXPR is not suitable to be the expression of interest in
2780 an sm-diagnostic, set *EXPR to NULL and log. */
2783 diagnostic_manager::update_for_unsuitable_sm_exprs (tree
*expr
) const
2786 if (*expr
&& !can_be_expr_of_interest_p (*expr
))
2788 log ("new var %qE is unsuitable; setting var to NULL", *expr
);
2793 /* Second pass of diagnostic_manager::prune_path: remove redundant
2794 interprocedural information.
2797 (1)- calling "f2" from "f1"
2798 (2)--- entry to "f2"
2799 (3)--- calling "f3" from "f2"
2800 (4)----- entry to "f3"
2801 (5)--- returning to "f2" to "f3"
2802 (6)- returning to "f1" to "f2"
2803 with no other intervening events, then none of these events are
2804 likely to be interesting to the user.
2806 Prune [..., call, function-entry, return, ...] triples repeatedly
2807 until nothing has changed. For the example above, this would
2808 remove events (3, 4, 5), and then remove events (1, 2, 6). */
2811 diagnostic_manager::prune_interproc_events (checker_path
*path
) const
2813 bool changed
= false;
2817 int idx
= (signed)path
->num_events () - 1;
2820 /* Prune [..., call, function-entry, return, ...] triples. */
2821 if (idx
+ 2 < (signed)path
->num_events ()
2822 && path
->get_checker_event (idx
)->is_call_p ()
2823 && path
->get_checker_event (idx
+ 1)->is_function_entry_p ()
2824 && path
->get_checker_event (idx
+ 2)->is_return_p ())
2829 (path
->get_checker_event (idx
)->get_desc (false));
2830 log ("filtering events %i-%i:"
2831 " irrelevant call/entry/return: %s",
2832 idx
, idx
+ 2, desc
.get ());
2834 path
->delete_event (idx
+ 2);
2835 path
->delete_event (idx
+ 1);
2836 path
->delete_event (idx
);
2842 /* Prune [..., call, return, ...] pairs
2843 (for -fanalyzer-verbosity=0). */
2844 if (idx
+ 1 < (signed)path
->num_events ()
2845 && path
->get_checker_event (idx
)->is_call_p ()
2846 && path
->get_checker_event (idx
+ 1)->is_return_p ())
2851 (path
->get_checker_event (idx
)->get_desc (false));
2852 log ("filtering events %i-%i:"
2853 " irrelevant call/return: %s",
2854 idx
, idx
+ 1, desc
.get ());
2856 path
->delete_event (idx
+ 1);
2857 path
->delete_event (idx
);
2870 /* Remove everything within [call point, IDX]. For consistency,
2871 IDX should represent the return event of the frame to delete,
2872 or if there is none it should be the last event of the frame.
2873 After this function, IDX designates the event prior to calling
2877 prune_frame (checker_path
*path
, int &idx
)
2879 gcc_assert (idx
>= 0);
2881 if (path
->get_checker_event (idx
)->is_return_p ())
2885 if (path
->get_checker_event (idx
)->is_call_p ())
2887 else if (path
->get_checker_event (idx
)->is_return_p ())
2890 path
->delete_event (idx
--);
2891 } while (idx
>= 0 && nesting
!= 0);
2894 /* This function is called when fanalyzer-show-events-in-system-headers
2895 is disabled and will prune the diagnostic of all events within a
2896 system header, only keeping the entry and exit events to the header.
2897 This should be called after diagnostic_manager::prune_interproc_events
2898 so that sucessive events [system header call, system header return]
2899 are preserved thereafter.
2901 Given a diagnostics path diving into a system header in the form
2905 system header entry,
2906 events within system headers...,
2907 system header return,
2911 then transforms it into
2915 system header return,
2920 diagnostic_manager::prune_system_headers (checker_path
*path
) const
2922 int idx
= (signed)path
->num_events () - 1;
2925 const checker_event
*event
= path
->get_checker_event (idx
);
2926 /* Prune everything between
2927 [..., system entry, (...), system return, ...]. */
2928 if (event
->is_return_p ()
2929 && in_system_header_at (event
->get_location ()))
2932 prune_frame (path
, idx
);
2936 log ("filtering system headers events %i-%i:",
2939 // Delete function entry within system headers.
2942 event
= path
->get_checker_event (idx
);
2943 if (event
->is_function_entry_p ()
2944 && in_system_header_at (event
->get_location ()))
2948 label_text
desc (event
->get_desc (false));
2949 log ("filtering event %i:"
2950 "system header entry event: %s",
2954 path
->delete_event (idx
);
2963 /* Return true iff event IDX within PATH is on the same line as REF_EXP_LOC. */
2966 same_line_as_p (const expanded_location
&ref_exp_loc
,
2967 checker_path
*path
, unsigned idx
)
2969 const checker_event
*ev
= path
->get_checker_event (idx
);
2970 expanded_location idx_exp_loc
= expand_location (ev
->get_location ());
2971 gcc_assert (ref_exp_loc
.file
);
2972 if (idx_exp_loc
.file
== NULL
)
2974 if (strcmp (ref_exp_loc
.file
, idx_exp_loc
.file
))
2976 return ref_exp_loc
.line
== idx_exp_loc
.line
;
2979 /* This path-readability optimization reduces the verbosity of compound
2980 conditional statements (without needing to reconstruct the AST, which
2981 has already been lost).
2983 For example, it converts:
2985 | 61 | if (cp[0] != '\0' && cp[0] != '#')
2986 | | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2988 | | | | (6) ...to here
2989 | | | (7) following ‘true’ branch...
2990 | | (5) following ‘true’ branch...
2992 | 63 | alias = cp++;
2999 | 61 | if (cp[0] != '\0' && cp[0] != '#')
3002 | | (5) following ‘true’ branch...
3004 | 63 | alias = cp++;
3009 by combining events 5-8 into new events 5-6.
3011 Find runs of consecutive (start_cfg_edge_event, end_cfg_edge_event) pairs
3012 in which all events apart from the final end_cfg_edge_event are on the same
3013 line, and for which either all the CFG edges are TRUE edges, or all are
3016 Consolidate each such run into a
3017 (start_consolidated_cfg_edges_event, end_consolidated_cfg_edges_event)
3021 diagnostic_manager::consolidate_conditions (checker_path
*path
) const
3023 /* Don't simplify edges if we're debugging them. */
3024 if (flag_analyzer_verbose_edges
)
3027 for (int start_idx
= 0;
3028 start_idx
< (signed)path
->num_events () - 1;
3031 if (path
->cfg_edge_pair_at_p (start_idx
))
3033 const checker_event
*old_start_ev
3034 = path
->get_checker_event (start_idx
);
3035 expanded_location start_exp_loc
3036 = expand_location (old_start_ev
->get_location ());
3037 if (start_exp_loc
.file
== NULL
)
3039 if (!same_line_as_p (start_exp_loc
, path
, start_idx
+ 1))
3042 /* Are we looking for a run of all TRUE edges, or all FALSE edges? */
3043 gcc_assert (old_start_ev
->m_kind
== EK_START_CFG_EDGE
);
3044 const start_cfg_edge_event
*old_start_cfg_ev
3045 = (const start_cfg_edge_event
*)old_start_ev
;
3046 const cfg_superedge
& first_cfg_sedge
3047 = old_start_cfg_ev
->get_cfg_superedge ();
3049 if (first_cfg_sedge
.true_value_p ())
3051 else if (first_cfg_sedge
.false_value_p ())
3056 /* Find a run of CFG start/end event pairs from
3057 [start_idx, next_idx)
3058 where all apart from the final event are on the same line,
3059 and all are either TRUE or FALSE edges, matching the initial. */
3060 int next_idx
= start_idx
+ 2;
3061 while (path
->cfg_edge_pair_at_p (next_idx
)
3062 && same_line_as_p (start_exp_loc
, path
, next_idx
))
3064 const checker_event
*iter_ev
3065 = path
->get_checker_event (next_idx
);
3066 gcc_assert (iter_ev
->m_kind
== EK_START_CFG_EDGE
);
3067 const start_cfg_edge_event
*iter_cfg_ev
3068 = (const start_cfg_edge_event
*)iter_ev
;
3069 const cfg_superedge
& iter_cfg_sedge
3070 = iter_cfg_ev
->get_cfg_superedge ();
3073 if (!iter_cfg_sedge
.true_value_p ())
3078 if (!iter_cfg_sedge
.false_value_p ())
3084 /* If we have more than one pair in the run, consolidate. */
3085 if (next_idx
> start_idx
+ 2)
3087 const checker_event
*old_end_ev
3088 = path
->get_checker_event (next_idx
- 1);
3089 log ("consolidating CFG edge events %i-%i into %i-%i",
3090 start_idx
, next_idx
- 1, start_idx
, start_idx
+1);
3091 start_consolidated_cfg_edges_event
*new_start_ev
3092 = new start_consolidated_cfg_edges_event
3093 (event_loc_info (old_start_ev
->get_location (),
3094 old_start_ev
->get_fndecl (),
3095 old_start_ev
->get_stack_depth ()),
3097 checker_event
*new_end_ev
3098 = new end_consolidated_cfg_edges_event
3099 (event_loc_info (old_end_ev
->get_location (),
3100 old_end_ev
->get_fndecl (),
3101 old_end_ev
->get_stack_depth ()));
3102 path
->replace_event (start_idx
, new_start_ev
);
3103 path
->replace_event (start_idx
+ 1, new_end_ev
);
3104 path
->delete_events (start_idx
+ 2, next_idx
- (start_idx
+ 2));
3110 /* Final pass of diagnostic_manager::prune_path.
3112 If all we're left with is in one function, then filter function entry
3116 diagnostic_manager::finish_pruning (checker_path
*path
) const
3118 if (!path
->interprocedural_p ())
3120 int idx
= path
->num_events () - 1;
3121 while (idx
>= 0 && idx
< (signed)path
->num_events ())
3123 checker_event
*base_event
= path
->get_checker_event (idx
);
3124 if (base_event
->m_kind
== EK_FUNCTION_ENTRY
)
3126 log ("filtering event %i:"
3127 " function entry for purely intraprocedural path", idx
);
3128 path
->delete_event (idx
);
3137 #endif /* #if ENABLE_ANALYZER */