1 /* Classes for saving, deduplicating, and emitting analyzer diagnostics.
2 Copyright (C) 2019-2020 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/>. */
23 #include "coretypes.h"
25 #include "pretty-print.h"
26 #include "gcc-rich-location.h"
27 #include "gimple-pretty-print.h"
29 #include "diagnostic-core.h"
30 #include "diagnostic-event-id.h"
31 #include "diagnostic-path.h"
32 #include "alloc-pool.h"
33 #include "fibonacci_heap.h"
34 #include "shortest-paths.h"
38 #include "ordered-hash-map.h"
39 #include "analyzer/analyzer.h"
40 #include "analyzer/analyzer-logging.h"
41 #include "analyzer/sm.h"
42 #include "analyzer/pending-diagnostic.h"
43 #include "analyzer/diagnostic-manager.h"
44 #include "analyzer/region-model.h"
45 #include "analyzer/constraint-manager.h"
47 #include "basic-block.h"
49 #include "gimple-iterator.h"
52 #include "analyzer/supergraph.h"
53 #include "analyzer/call-string.h"
54 #include "analyzer/program-point.h"
55 #include "analyzer/program-state.h"
56 #include "analyzer/exploded-graph.h"
57 #include "analyzer/checker-path.h"
58 #include "analyzer/reachability.h"
64 /* class saved_diagnostic. */
66 /* saved_diagnostic's ctor.
67 Take ownership of D and STMT_FINDER. */
69 saved_diagnostic::saved_diagnostic (const state_machine
*sm
,
70 const exploded_node
*enode
,
71 const supernode
*snode
, const gimple
*stmt
,
72 stmt_finder
*stmt_finder
,
73 tree var
, state_machine::state_t state
,
74 pending_diagnostic
*d
)
75 : m_sm (sm
), m_enode (enode
), m_snode (snode
), m_stmt (stmt
),
76 /* stmt_finder could be on-stack; we want our own copy that can
78 m_stmt_finder (stmt_finder
? stmt_finder
->clone () : NULL
),
79 m_var (var
), m_state (state
),
80 m_d (d
), m_trailing_eedge (NULL
)
82 gcc_assert (m_stmt
|| m_stmt_finder
);
84 /* We must have an enode in order to be able to look for paths
85 through the exploded_graph to this diagnostic. */
89 /* saved_diagnostic's dtor. */
91 saved_diagnostic::~saved_diagnostic ()
98 saved_diagnostic::operator== (const saved_diagnostic
&other
) const
100 return (m_sm
== other
.m_sm
101 /* We don't compare m_enode. */
102 && m_snode
== other
.m_snode
103 && m_stmt
== other
.m_stmt
104 /* We don't compare m_stmt_finder. */
105 && pending_diagnostic::same_tree_p (m_var
, other
.m_var
)
106 && m_state
== other
.m_state
107 && m_d
->equal_p (*other
.m_d
)
108 && m_trailing_eedge
== other
.m_trailing_eedge
);
111 /* State for building a checker_path from a particular exploded_path.
112 In particular, this precomputes reachability information: the set of
113 source enodes for which a a path be found to the diagnostic enode. */
118 path_builder (const exploded_graph
&eg
,
119 const exploded_path
&epath
)
121 m_diag_enode (epath
.get_final_enode ()),
122 m_reachability (eg
, m_diag_enode
)
125 const exploded_node
*get_diag_node () const { return m_diag_enode
; }
127 bool reachable_from_p (const exploded_node
*src_enode
) const
129 return m_reachability
.reachable_from_p (src_enode
);
132 const extrinsic_state
&get_ext_state () const { return m_eg
.get_ext_state (); }
135 typedef reachability
<eg_traits
> enode_reachability
;
137 const exploded_graph
&m_eg
;
139 /* The enode where the diagnostic occurs. */
140 const exploded_node
*m_diag_enode
;
142 /* Precompute all enodes from which the diagnostic is reachable. */
143 enode_reachability m_reachability
;
146 /* class diagnostic_manager. */
148 /* diagnostic_manager's ctor. */
150 diagnostic_manager::diagnostic_manager (logger
*logger
, int verbosity
)
151 : log_user (logger
), m_verbosity (verbosity
)
155 /* Queue pending_diagnostic D at ENODE for later emission. */
158 diagnostic_manager::add_diagnostic (const state_machine
*sm
,
159 const exploded_node
*enode
,
160 const supernode
*snode
, const gimple
*stmt
,
162 tree var
, state_machine::state_t state
,
163 pending_diagnostic
*d
)
165 LOG_FUNC (get_logger ());
167 /* We must have an enode in order to be able to look for paths
168 through the exploded_graph to the diagnostic. */
172 = new saved_diagnostic (sm
, enode
, snode
, stmt
, finder
, var
, state
, d
);
173 m_saved_diagnostics
.safe_push (sd
);
175 log ("adding saved diagnostic %i at SN %i: %qs",
176 m_saved_diagnostics
.length () - 1,
177 snode
->m_index
, d
->get_kind ());
180 /* Queue pending_diagnostic D at ENODE for later emission. */
183 diagnostic_manager::add_diagnostic (const exploded_node
*enode
,
184 const supernode
*snode
, const gimple
*stmt
,
186 pending_diagnostic
*d
)
189 add_diagnostic (NULL
, enode
, snode
, stmt
, finder
, NULL_TREE
, 0, d
);
192 /* A class for identifying sets of duplicated pending_diagnostic.
194 We want to find the simplest dedupe_candidate amongst those that share a
200 dedupe_key (const saved_diagnostic
&sd
,
201 const exploded_path
&epath
)
202 : m_sd (sd
), m_stmt (sd
.m_stmt
)
204 /* Support deferring the choice of stmt until after an emission path has
205 been built, using an optional stmt_finder. */
208 gcc_assert (sd
.m_stmt_finder
);
209 m_stmt
= sd
.m_stmt_finder
->find_stmt (epath
);
214 hashval_t
hash () const
216 inchash::hash hstate
;
217 hstate
.add_ptr (m_stmt
);
219 return hstate
.end ();
221 bool operator== (const dedupe_key
&other
) const
223 return (m_sd
== other
.m_sd
224 && m_stmt
== other
.m_stmt
);
227 location_t
get_location () const
229 return m_stmt
->location
;
232 /* A qsort comparator for use by dedupe_winners::emit_best
233 to sort them into location_t order. */
236 comparator (const void *p1
, const void *p2
)
238 const dedupe_key
*pk1
= *(const dedupe_key
* const *)p1
;
239 const dedupe_key
*pk2
= *(const dedupe_key
* const *)p2
;
241 location_t loc1
= pk1
->get_location ();
242 location_t loc2
= pk2
->get_location ();
244 return linemap_compare_locations (line_table
, loc2
, loc1
);
247 const saved_diagnostic
&m_sd
;
248 const gimple
*m_stmt
;
251 /* The value of a slot for a dedupe_key within dedupe_winners:
252 the exploded_path for the best candidate for that key, and the
253 number of duplicates seen so far. */
255 class dedupe_candidate
258 // has the exploded_path
259 dedupe_candidate (const shortest_exploded_paths
&sp
,
260 const saved_diagnostic
&sd
)
261 : m_epath (sp
.get_shortest_path (sd
.m_enode
)),
266 unsigned length () const { return m_epath
.length (); }
267 const exploded_path
&get_path () const { return m_epath
; }
269 void add_duplicate () { m_num_dupes
++; }
270 int get_num_dupes () const { return m_num_dupes
; }
273 exploded_path m_epath
;
278 /* Traits for use by dedupe_winners. */
280 class dedupe_hash_map_traits
283 typedef const dedupe_key
*key_type
;
284 typedef dedupe_candidate
*value_type
;
285 typedef dedupe_candidate
*compare_type
;
287 static inline hashval_t
hash (const key_type
&v
)
291 static inline bool equal_keys (const key_type
&k1
, const key_type
&k2
)
295 template <typename T
>
296 static inline void remove (T
&)
300 template <typename T
>
301 static inline void mark_deleted (T
&entry
)
303 entry
.m_key
= reinterpret_cast<key_type
> (1);
305 template <typename T
>
306 static inline void mark_empty (T
&entry
)
310 template <typename T
>
311 static inline bool is_deleted (const T
&entry
)
313 return entry
.m_key
== reinterpret_cast<key_type
> (1);
315 template <typename T
>
316 static inline bool is_empty (const T
&entry
)
318 return entry
.m_key
== NULL
;
320 static const bool empty_zero_p
= true;
323 /* A class for deduplicating diagnostics and finding (and emitting) the
324 best diagnostic within each partition. */
331 /* Delete all keys and candidates. */
332 for (map_t::iterator iter
= m_map
.begin ();
333 iter
!= m_map
.end ();
336 delete (*iter
).first
;
337 delete (*iter
).second
;
341 /* Determine an exploded_path for SD using SP and, if it's feasible,
342 determine if it's the best seen so far for its dedupe_key.
343 Retain the winner for each dedupe_key, and discard the rest. */
345 void add (logger
*logger
,
346 const shortest_exploded_paths
&sp
,
347 const saved_diagnostic
&sd
)
349 /* Build a dedupe_candidate for SD.
350 This uses SP to build an exploded_path. */
351 dedupe_candidate
*dc
= new dedupe_candidate (sp
, sd
);
353 /* Verify that the epath is feasible.
354 State-merging means that not every path in the epath corresponds
355 to a feasible one w.r.t. states.
356 Here we simply check each duplicate saved_diagnostic's
357 shortest_path, and reject any that aren't feasible.
358 This could introduce false negatives, as there could be longer
359 feasible paths within the egraph. */
361 logger
->log ("considering %qs at SN: %i",
362 sd
.m_d
->get_kind (), sd
.m_snode
->m_index
);
363 if (!dc
->get_path ().feasible_p (logger
))
366 logger
->log ("rejecting %qs at SN: %i"
367 " due to infeasible path",
368 sd
.m_d
->get_kind (), sd
.m_snode
->m_index
);
374 logger
->log ("accepting %qs at SN: %i with feasible path",
375 sd
.m_d
->get_kind (), sd
.m_snode
->m_index
);
377 dedupe_key
*key
= new dedupe_key (sd
, dc
->get_path ());
378 if (dedupe_candidate
**slot
= m_map
.get (key
))
381 logger
->log ("already have this dedupe_key");
383 (*slot
)->add_duplicate ();
385 if (dc
->length () < (*slot
)->length ())
387 /* We've got a shorter path for the key; replace
388 the current candidate. */
390 logger
->log ("length %i is better than existing length %i;"
391 " taking over this dedupe_key",
392 dc
->length (), (*slot
)->length ());
393 dc
->m_num_dupes
= (*slot
)->get_num_dupes ();
398 /* We haven't beaten the current best candidate;
399 drop the new candidate. */
402 logger
->log ("length %i isn't better than existing length %i;"
403 " dropping this candidate",
404 dc
->length (), (*slot
)->length ());
411 /* This is the first candidate for this key. */
414 logger
->log ("first candidate for this dedupe_key");
418 /* Emit the simplest diagnostic within each set. */
420 void emit_best (diagnostic_manager
*dm
,
421 const exploded_graph
&eg
)
423 LOG_SCOPE (dm
->get_logger ());
425 /* Get keys into a vec for sorting. */
426 auto_vec
<const dedupe_key
*> keys (m_map
.elements ());
427 for (map_t::iterator iter
= m_map
.begin ();
428 iter
!= m_map
.end ();
430 keys
.quick_push ((*iter
).first
);
432 dm
->log ("# keys after de-duplication: %i", keys
.length ());
434 /* Sort into a good emission order. */
435 keys
.qsort (dedupe_key::comparator
);
437 /* Emit the best candidate for each key. */
439 const dedupe_key
*key
;
440 FOR_EACH_VEC_ELT (keys
, i
, key
)
442 dedupe_candidate
**slot
= m_map
.get (key
);
444 const dedupe_candidate
&dc
= **slot
;
446 dm
->emit_saved_diagnostic (eg
, key
->m_sd
,
447 dc
.get_path (), key
->m_stmt
,
448 dc
.get_num_dupes ());
454 /* This maps from each dedupe_key to a current best dedupe_candidate. */
456 typedef hash_map
<const dedupe_key
*, dedupe_candidate
*,
457 dedupe_hash_map_traits
> map_t
;
461 /* Emit all saved diagnostics. */
464 diagnostic_manager::emit_saved_diagnostics (const exploded_graph
&eg
)
466 LOG_SCOPE (get_logger ());
467 auto_timevar
tv (TV_ANALYZER_DIAGNOSTICS
);
468 log ("# saved diagnostics: %i", m_saved_diagnostics
.length ());
470 if (m_saved_diagnostics
.length () == 0)
473 /* Compute the shortest_paths once, sharing it between all diagnostics. */
474 shortest_exploded_paths
sp (eg
, eg
.get_origin ());
476 /* Iterate through all saved diagnostics, adding them to a dedupe_winners
477 instance. This partitions the saved diagnostics by dedupe_key,
478 generating exploded_paths for them, and retaining the best one in each
480 dedupe_winners best_candidates
;
483 saved_diagnostic
*sd
;
484 FOR_EACH_VEC_ELT (m_saved_diagnostics
, i
, sd
)
485 best_candidates
.add (get_logger (), sp
, *sd
);
487 /* For each dedupe-key, call emit_saved_diagnostic on the "best"
489 best_candidates
.emit_best (this, eg
);
492 /* Given a saved_diagnostic SD at STMT with feasible path EPATH through EG,
493 create an checker_path of suitable events and use it to call
494 SD's underlying pending_diagnostic "emit" vfunc to emit a diagnostic. */
497 diagnostic_manager::emit_saved_diagnostic (const exploded_graph
&eg
,
498 const saved_diagnostic
&sd
,
499 const exploded_path
&epath
,
503 LOG_SCOPE (get_logger ());
504 log ("sd: %qs at SN: %i", sd
.m_d
->get_kind (), sd
.m_snode
->m_index
);
505 log ("num dupes: %i", num_dupes
);
507 pretty_printer
*pp
= global_dc
->printer
->clone ();
509 /* Precompute all enodes from which the diagnostic is reachable. */
510 path_builder
pb (eg
, epath
);
512 /* This is the diagnostic_path subclass that will be built for
514 checker_path emission_path
;
516 /* Populate emission_path with a full description of EPATH. */
517 build_emission_path (pb
, epath
, &emission_path
);
519 /* Now prune it to just cover the most pertinent events. */
520 prune_path (&emission_path
, sd
.m_sm
, sd
.m_var
, sd
.m_state
);
522 /* Add a final event to the path, covering the diagnostic itself.
523 We use the final enode from the epath, which might be different from
524 the sd.m_enode, as the dedupe code doesn't care about enodes, just
526 emission_path
.add_final_event (sd
.m_sm
, epath
.get_final_enode (), stmt
,
527 sd
.m_var
, sd
.m_state
);
529 /* The "final" event might not be final; if the saved_diagnostic has a
530 trailing eedge stashed, add any events for it. This is for use
531 in handling longjmp, to show where a longjmp is rewinding to. */
532 if (sd
.m_trailing_eedge
)
533 add_events_for_eedge (pb
, *sd
.m_trailing_eedge
, &emission_path
);
535 emission_path
.prepare_for_emission (sd
.m_d
);
537 gcc_rich_location
rich_loc (stmt
->location
);
538 rich_loc
.set_path (&emission_path
);
540 auto_diagnostic_group d
;
541 auto_cfun
sentinel (sd
.m_snode
->m_fun
);
542 if (sd
.m_d
->emit (&rich_loc
))
544 if (flag_analyzer_show_duplicate_count
&& num_dupes
> 0)
545 inform_n (stmt
->location
, num_dupes
,
546 "%i duplicate", "%i duplicates",
552 /* Given a state change to DST_REP, determine a tree that gives the origin
553 of that state at STMT, using DST_STATE's region model, so that state
554 changes based on assignments can be tracked back to their origins.
556 For example, if we have
558 (S1) _1 = malloc (64);
561 then at stmt S2 we can get the origin of EXPR's state as being _1,
562 and thus track the allocation back to S1. */
565 get_any_origin (const gimple
*stmt
,
567 const program_state
&dst_state
)
572 gcc_assert (dst_rep
);
574 if (const gassign
*assign
= dyn_cast
<const gassign
*> (stmt
))
576 tree lhs
= gimple_assign_lhs (assign
);
577 /* Use region IDs to compare lhs with DST_REP. */
578 if (dst_state
.m_region_model
->get_lvalue (lhs
, NULL
)
579 == dst_state
.m_region_model
->get_lvalue (dst_rep
, NULL
))
581 tree rhs1
= gimple_assign_rhs1 (assign
);
582 enum tree_code op
= gimple_assign_rhs_code (assign
);
586 //gcc_unreachable (); // TODO
597 /* Emit a "path" of events to EMISSION_PATH describing the exploded path
601 diagnostic_manager::build_emission_path (const path_builder
&pb
,
602 const exploded_path
&epath
,
603 checker_path
*emission_path
) const
605 LOG_SCOPE (get_logger ());
606 for (unsigned i
= 0; i
< epath
.m_edges
.length (); i
++)
608 const exploded_edge
*eedge
= epath
.m_edges
[i
];
609 add_events_for_eedge (pb
, *eedge
, emission_path
);
613 /* Subclass of state_change_visitor that creates state_change_event
616 class state_change_event_creator
: public state_change_visitor
619 state_change_event_creator (const exploded_edge
&eedge
,
620 checker_path
*emission_path
)
622 m_emission_path (emission_path
)
625 bool on_global_state_change (const state_machine
&sm
,
626 state_machine::state_t src_sm_val
,
627 state_machine::state_t dst_sm_val
)
630 const exploded_node
*src_node
= m_eedge
.m_src
;
631 const program_point
&src_point
= src_node
->get_point ();
632 const int src_stack_depth
= src_point
.get_stack_depth ();
633 const exploded_node
*dst_node
= m_eedge
.m_dest
;
634 const gimple
*stmt
= src_point
.get_stmt ();
635 const supernode
*supernode
= src_point
.get_supernode ();
636 const program_state
&dst_state
= dst_node
->get_state ();
638 int stack_depth
= src_stack_depth
;
640 m_emission_path
->add_event (new state_change_event (supernode
,
652 bool on_state_change (const state_machine
&sm
,
653 state_machine::state_t src_sm_val
,
654 state_machine::state_t dst_sm_val
,
656 svalue_id dst_origin_sid
) FINAL OVERRIDE
658 const exploded_node
*src_node
= m_eedge
.m_src
;
659 const program_point
&src_point
= src_node
->get_point ();
660 const int src_stack_depth
= src_point
.get_stack_depth ();
661 const exploded_node
*dst_node
= m_eedge
.m_dest
;
662 const gimple
*stmt
= src_point
.get_stmt ();
663 const supernode
*supernode
= src_point
.get_supernode ();
664 const program_state
&dst_state
= dst_node
->get_state ();
666 int stack_depth
= src_stack_depth
;
669 && m_eedge
.m_sedge
->m_kind
== SUPEREDGE_CFG_EDGE
)
671 supernode
= src_point
.get_supernode ();
672 stmt
= supernode
->get_last_stmt ();
673 stack_depth
= src_stack_depth
;
676 /* Bulletproofing for state changes at calls/returns;
677 TODO: is there a better way? */
682 = dst_state
.get_representative_tree (dst_origin_sid
);
684 if (origin_rep
== NULL_TREE
)
685 origin_rep
= get_any_origin (stmt
, dst_rep
, dst_state
);
686 m_emission_path
->add_event (new state_change_event (supernode
,
698 const exploded_edge
&m_eedge
;
699 checker_path
*m_emission_path
;
702 /* Compare SRC_STATE and DST_STATE (which use EXT_STATE), and call
703 VISITOR's on_state_change for every sm-state change that occurs
704 to a tree, and on_global_state_change for every global state change
707 This determines the state changes that ought to be reported to
708 the user: a combination of the effects of changes to sm_state_map
709 (which maps svalues to sm-states), and of region_model changes
710 (which map trees to svalues).
712 Bail out early and return true if any call to on_global_state_change
713 or on_state_change returns true, otherwise return false.
715 This is split out to make it easier to experiment with changes to
716 exploded_node granularity (so that we can observe what state changes
717 lead to state_change_events being emitted). */
720 for_each_state_change (const program_state
&src_state
,
721 const program_state
&dst_state
,
722 const extrinsic_state
&ext_state
,
723 state_change_visitor
*visitor
)
725 gcc_assert (src_state
.m_checker_states
.length ()
726 == ext_state
.get_num_checkers ());
727 gcc_assert (dst_state
.m_checker_states
.length ()
728 == ext_state
.get_num_checkers ());
729 for (unsigned i
= 0; i
< ext_state
.get_num_checkers (); i
++)
731 const state_machine
&sm
= ext_state
.get_sm (i
);
732 const sm_state_map
&src_smap
= *src_state
.m_checker_states
[i
];
733 const sm_state_map
&dst_smap
= *dst_state
.m_checker_states
[i
];
735 /* Add events for any global state changes. */
736 if (src_smap
.get_global_state () != dst_smap
.get_global_state ())
737 if (visitor
->on_global_state_change (sm
,
738 src_smap
.get_global_state (),
739 dst_smap
.get_global_state ()))
742 /* Add events for per-svalue state changes. */
743 for (sm_state_map::iterator_t iter
= dst_smap
.begin ();
744 iter
!= dst_smap
.end ();
747 /* Ideally we'd directly compare the SM state between src state
748 and dst state, but there's no guarantee that the IDs can
749 be meaningfully compared. */
750 svalue_id dst_sid
= (*iter
).first
;
751 state_machine::state_t dst_sm_val
= (*iter
).second
.m_state
;
753 auto_vec
<path_var
> dst_pvs
;
754 dst_state
.m_region_model
->get_path_vars_for_svalue (dst_sid
,
759 FOR_EACH_VEC_ELT (dst_pvs
, j
, dst_pv
)
761 tree dst_rep
= dst_pv
->m_tree
;
762 gcc_assert (dst_rep
);
763 if (dst_pv
->m_stack_depth
764 >= src_state
.m_region_model
->get_stack_depth ())
767 = src_state
.m_region_model
->get_rvalue (*dst_pv
, NULL
);
768 if (src_sid
.null_p ())
770 state_machine::state_t src_sm_val
= src_smap
.get_state (src_sid
);
771 if (dst_sm_val
!= src_sm_val
)
773 svalue_id dst_origin_sid
= (*iter
).second
.m_origin
;
774 if (visitor
->on_state_change (sm
, src_sm_val
, dst_sm_val
,
775 dst_rep
, dst_origin_sid
))
784 /* Subroutine of diagnostic_manager::build_emission_path.
785 Add any events for EEDGE to EMISSION_PATH. */
788 diagnostic_manager::add_events_for_eedge (const path_builder
&pb
,
789 const exploded_edge
&eedge
,
790 checker_path
*emission_path
) const
792 const exploded_node
*src_node
= eedge
.m_src
;
793 const program_point
&src_point
= src_node
->get_point ();
794 const exploded_node
*dst_node
= eedge
.m_dest
;
795 const program_point
&dst_point
= dst_node
->get_point ();
796 const int dst_stack_depth
= dst_point
.get_stack_depth ();
799 get_logger ()->start_log_line ();
800 pretty_printer
*pp
= get_logger ()->get_printer ();
801 pp_printf (pp
, "EN %i -> EN %i: ",
802 eedge
.m_src
->m_index
,
803 eedge
.m_dest
->m_index
);
804 src_point
.print (pp
, format (false));
805 pp_string (pp
, "-> ");
806 dst_point
.print (pp
, format (false));
807 get_logger ()->end_log_line ();
809 const program_state
&src_state
= src_node
->get_state ();
810 const program_state
&dst_state
= dst_node
->get_state ();
812 /* Add state change events for the states that have changed.
813 We add these before events for superedges, so that if we have a
814 state_change_event due to following an edge, we'll get this sequence
820 | (1) assuming 'ptr' is non-NULL (state_change_event)
821 | (2) following 'false' branch... (start_cfg_edge_event)
823 | do_something (ptr);
826 | (3) ...to here (end_cfg_edge_event). */
827 state_change_event_creator
visitor (eedge
, emission_path
);
828 for_each_state_change (src_state
, dst_state
, pb
.get_ext_state (),
831 /* Allow non-standard edges to add events, e.g. when rewinding from
832 longjmp to a setjmp. */
833 if (eedge
.m_custom_info
)
834 eedge
.m_custom_info
->add_events_to_path (emission_path
, eedge
);
836 /* Add events for superedges, function entries, and for statements. */
837 switch (dst_point
.get_kind ())
841 case PK_BEFORE_SUPERNODE
:
842 if (src_point
.get_kind () == PK_AFTER_SUPERNODE
)
845 add_events_for_superedge (pb
, eedge
, emission_path
);
847 /* Add function entry events. */
848 if (dst_point
.get_supernode ()->entry_p ())
850 emission_path
->add_event
851 (new function_entry_event
852 (dst_point
.get_supernode ()->get_start_location (),
853 dst_point
.get_fndecl (),
859 const gimple
*stmt
= dst_point
.get_stmt ();
860 const gcall
*call
= dyn_cast
<const gcall
*> (stmt
);
861 if (call
&& is_setjmp_call_p (call
))
862 emission_path
->add_event
863 (new setjmp_event (stmt
->location
,
865 dst_point
.get_fndecl (),
869 emission_path
->add_event
870 (new statement_event (stmt
,
871 dst_point
.get_fndecl (),
872 dst_stack_depth
, dst_state
));
878 /* Return true if EEDGE is a significant edge in the path to the diagnostic
881 Consider all of the sibling out-eedges from the same source enode
883 If there's no path from the destinations of those eedges to the
884 diagnostic enode, then we have to take this eedge and thus it's
887 Conversely if there is a path from the destination of any other sibling
888 eedge to the diagnostic enode, then this edge is insignificant.
890 Example 1: redundant if-else:
898 D is reachable by either B or C, so neither of these edges
901 Example 2: pertinent if-else:
906 (C) [NECESSARY CONDITION] | |
907 (D) [POSSIBLE DIAGNOSTIC] D1 D2
909 D becomes D1 and D2 in the exploded graph, where the diagnostic occurs
910 at D2. D2 is only reachable via C, so the A -> C edge is significant.
912 Example 3: redundant loop:
914 (A) while (...) +-->A
920 D is reachable from both B and C, so the A->C edge is not significant. */
923 diagnostic_manager::significant_edge_p (const path_builder
&pb
,
924 const exploded_edge
&eedge
) const
927 exploded_edge
*sibling
;
928 FOR_EACH_VEC_ELT (eedge
.m_src
->m_succs
, i
, sibling
)
930 if (sibling
== &eedge
)
932 if (pb
.reachable_from_p (sibling
->m_dest
))
935 get_logger ()->log (" edge EN: %i -> EN: %i is insignificant as"
936 " EN: %i is also reachable via"
938 eedge
.m_src
->m_index
, eedge
.m_dest
->m_index
,
939 pb
.get_diag_node ()->m_index
,
940 sibling
->m_src
->m_index
,
941 sibling
->m_dest
->m_index
);
949 /* Subroutine of diagnostic_manager::add_events_for_eedge
950 where EEDGE has an underlying superedge i.e. a CFG edge,
951 or an interprocedural call/return.
952 Add any events for the superedge to EMISSION_PATH. */
955 diagnostic_manager::add_events_for_superedge (const path_builder
&pb
,
956 const exploded_edge
&eedge
,
957 checker_path
*emission_path
)
960 gcc_assert (eedge
.m_sedge
);
962 /* Don't add events for insignificant edges at verbosity levels below 3. */
964 if (!significant_edge_p (pb
, eedge
))
967 const exploded_node
*src_node
= eedge
.m_src
;
968 const program_point
&src_point
= src_node
->get_point ();
969 const exploded_node
*dst_node
= eedge
.m_dest
;
970 const program_point
&dst_point
= dst_node
->get_point ();
971 const int src_stack_depth
= src_point
.get_stack_depth ();
972 const int dst_stack_depth
= dst_point
.get_stack_depth ();
973 const gimple
*last_stmt
= src_point
.get_supernode ()->get_last_stmt ();
975 switch (eedge
.m_sedge
->m_kind
)
977 case SUPEREDGE_CFG_EDGE
:
979 emission_path
->add_event
980 (new start_cfg_edge_event (eedge
,
982 ? last_stmt
->location
984 src_point
.get_fndecl (),
986 emission_path
->add_event
987 (new end_cfg_edge_event (eedge
,
988 dst_point
.get_supernode ()->get_start_location (),
989 dst_point
.get_fndecl (),
996 emission_path
->add_event
997 (new call_event (eedge
,
999 ? last_stmt
->location
1000 : UNKNOWN_LOCATION
),
1001 src_point
.get_fndecl (),
1006 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
1008 /* TODO: add a subclass for this, or generate events for the
1010 emission_path
->add_event
1011 (new debug_event ((last_stmt
1012 ? last_stmt
->location
1013 : UNKNOWN_LOCATION
),
1014 src_point
.get_fndecl (),
1020 case SUPEREDGE_RETURN
:
1022 const return_superedge
*return_edge
1023 = as_a
<const return_superedge
*> (eedge
.m_sedge
);
1025 const gcall
*call_stmt
= return_edge
->get_call_stmt ();
1026 emission_path
->add_event
1027 (new return_event (eedge
,
1029 ? call_stmt
->location
1030 : UNKNOWN_LOCATION
),
1031 dst_point
.get_fndecl (),
1038 /* Prune PATH, based on the verbosity level, to the most pertinent
1039 events for a diagnostic that involves VAR ending in state STATE
1040 (for state machine SM).
1042 PATH is updated in place, and the redundant checker_events are deleted.
1044 As well as deleting events, call record_critical_state on events in
1045 which state critical to the pending_diagnostic is being handled; see
1046 the comment for diagnostic_manager::prune_for_sm_diagnostic. */
1049 diagnostic_manager::prune_path (checker_path
*path
,
1050 const state_machine
*sm
,
1052 state_machine::state_t state
) const
1054 LOG_FUNC (get_logger ());
1055 path
->maybe_log (get_logger (), "path");
1056 prune_for_sm_diagnostic (path
, sm
, var
, state
);
1057 prune_interproc_events (path
);
1058 finish_pruning (path
);
1059 path
->maybe_log (get_logger (), "pruned");
1062 /* First pass of diagnostic_manager::prune_path: apply verbosity level,
1063 pruning unrelated state change events.
1065 Iterate backwards through PATH, skipping state change events that aren't
1066 VAR but update the pertinent VAR when state-copying occurs.
1068 As well as deleting events, call record_critical_state on events in
1069 which state critical to the pending_diagnostic is being handled, so
1070 that the event's get_desc vfunc can potentially supply a more precise
1071 description of the event to the user.
1073 "calling 'foo' from 'bar'"
1075 "passing possibly-NULL pointer 'ptr' to 'foo' from 'bar' as param 1"
1076 when the diagnostic relates to later dereferencing 'ptr'. */
1079 diagnostic_manager::prune_for_sm_diagnostic (checker_path
*path
,
1080 const state_machine
*sm
,
1082 state_machine::state_t state
) const
1084 /* If we have a constant (such as NULL), assume its state is also
1085 constant, so as not to attempt to get its lvalue whilst tracking the
1086 origin of the state. */
1087 if (var
&& CONSTANT_CLASS_P (var
))
1090 int idx
= path
->num_events () - 1;
1091 while (idx
>= 0 && idx
< (signed)path
->num_events ())
1093 checker_event
*base_event
= path
->get_checker_event (idx
);
1099 log ("considering event %i, with var: %qE, state: %qs",
1100 idx
, var
, sm
->get_state_name (state
));
1102 log ("considering event %i, with global state: %qs",
1103 idx
, sm
->get_state_name (state
));
1106 log ("considering event %i", idx
);
1108 gcc_assert (var
== NULL
|| !CONSTANT_CLASS_P (var
));
1109 switch (base_event
->m_kind
)
1115 if (m_verbosity
< 4)
1117 log ("filtering event %i: debug event", idx
);
1118 path
->delete_event (idx
);
1123 /* Don't filter custom events. */
1128 /* If this stmt is the origin of "var", update var. */
1131 statement_event
*stmt_event
= (statement_event
*)base_event
;
1132 tree new_var
= get_any_origin (stmt_event
->m_stmt
, var
,
1133 stmt_event
->m_dst_state
);
1136 log ("event %i: switching var of interest from %qE to %qE",
1141 if (m_verbosity
< 4)
1143 log ("filtering event %i: statement event", idx
);
1144 path
->delete_event (idx
);
1149 case EK_FUNCTION_ENTRY
:
1150 if (m_verbosity
< 1)
1152 log ("filtering event %i: function entry", idx
);
1153 path
->delete_event (idx
);
1157 case EK_STATE_CHANGE
:
1159 state_change_event
*state_change
= (state_change_event
*)base_event
;
1160 if (state_change
->get_lvalue (state_change
->m_var
)
1161 == state_change
->get_lvalue (var
))
1163 if (state_change
->m_origin
)
1165 log ("event %i: switching var of interest from %qE to %qE",
1166 idx
, var
, state_change
->m_origin
);
1167 var
= state_change
->m_origin
;
1168 if (var
&& CONSTANT_CLASS_P (var
))
1170 log ("new var is a constant; setting var to NULL");
1174 log ("event %i: switching state of interest from %qs to %qs",
1175 idx
, sm
->get_state_name (state_change
->m_to
),
1176 sm
->get_state_name (state_change
->m_from
));
1177 state
= state_change
->m_from
;
1179 else if (m_verbosity
< 4)
1182 log ("filtering event %i:"
1183 " state change to %qE unrelated to %qE",
1184 idx
, state_change
->m_var
, var
);
1186 log ("filtering event %i: state change to %qE",
1187 idx
, state_change
->m_var
);
1188 path
->delete_event (idx
);
1193 case EK_START_CFG_EDGE
:
1195 cfg_edge_event
*event
= (cfg_edge_event
*)base_event
;
1196 const cfg_superedge
& cfg_superedge
1197 = event
->get_cfg_superedge ();
1198 const supernode
*dest
= event
->m_sedge
->m_dest
;
1199 /* Do we have an SSA_NAME defined via a phi node in
1200 the dest CFG node? */
1201 if (var
&& TREE_CODE (var
) == SSA_NAME
)
1202 if (SSA_NAME_DEF_STMT (var
)->bb
== dest
->m_bb
)
1205 = dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (var
)))
1207 /* Update var based on its phi node. */
1209 var
= cfg_superedge
.get_phi_arg (phi
);
1210 log ("updating from %qE to %qE based on phi node",
1215 pp_gimple_stmt_1 (&pp
, phi
, 0, (dump_flags_t
)0);
1216 log (" phi: %s", pp_formatted_text (&pp
));
1218 /* If we've chosen a bad exploded_path, then the
1219 phi arg might be a constant. Fail gracefully for
1221 if (CONSTANT_CLASS_P (var
))
1223 log ("new var is a constant (bad path?);"
1224 " setting var to NULL");
1230 /* TODO: is this edge significant to var?
1231 See if var can be in other states in the dest, but not
1232 in other states in the src?
1233 Must have multiple sibling edges. */
1235 if (event
->should_filter_p (m_verbosity
))
1237 log ("filtering event %i: CFG edge", idx
);
1238 path
->delete_event (idx
);
1239 /* Also delete the corresponding EK_END_CFG_EDGE. */
1240 gcc_assert (path
->get_checker_event (idx
)->m_kind
1241 == EK_END_CFG_EDGE
);
1242 path
->delete_event (idx
);
1247 case EK_END_CFG_EDGE
:
1248 /* These come in pairs with EK_START_CFG_EDGE events and are
1249 filtered when their start event is filtered. */
1254 call_event
*event
= (call_event
*)base_event
;
1255 const callgraph_superedge
& cg_superedge
1256 = event
->get_callgraph_superedge ();
1259 = cg_superedge
.map_expr_from_callee_to_caller (var
, &expr
);
1263 " switching var of interest"
1264 " from %qE in callee to %qE in caller",
1265 idx
, var
, caller_var
);
1267 if (expr
.param_p ())
1268 event
->record_critical_state (var
, state
);
1269 if (var
&& CONSTANT_CLASS_P (var
))
1271 log ("new var is a constant; setting var to NULL");
1278 case EK_RETURN_EDGE
:
1279 // TODO: potentially update var/state based on return value,
1284 return_event
*event
= (return_event
*)base_event
;
1285 const callgraph_superedge
& cg_superedge
1286 = event
->get_callgraph_superedge ();
1289 = cg_superedge
.map_expr_from_caller_to_callee (var
, &expr
);
1293 " switching var of interest"
1294 " from %qE in caller to %qE in callee",
1295 idx
, var
, callee_var
);
1297 if (expr
.return_value_p ())
1298 event
->record_critical_state (var
, state
);
1299 if (var
&& CONSTANT_CLASS_P (var
))
1301 log ("new var is a constant; setting var to NULL");
1310 /* TODO: only show setjmp_events that matter i.e. those for which
1311 there is a later rewind event using them. */
1312 case EK_REWIND_FROM_LONGJMP
:
1313 case EK_REWIND_TO_SETJMP
:
1317 /* Always show the final "warning" event in the path. */
1324 /* Second pass of diagnostic_manager::prune_path: remove redundant
1325 interprocedural information.
1328 (1)- calling "f2" from "f1"
1329 (2)--- entry to "f2"
1330 (3)--- calling "f3" from "f2"
1331 (4)----- entry to "f3"
1332 (5)--- returning to "f2" to "f3"
1333 (6)- returning to "f1" to "f2"
1334 with no other intervening events, then none of these events are
1335 likely to be interesting to the user.
1337 Prune [..., call, function-entry, return, ...] triples repeatedly
1338 until nothing has changed. For the example above, this would
1339 remove events (3, 4, 5), and then remove events (1, 2, 6). */
1342 diagnostic_manager::prune_interproc_events (checker_path
*path
) const
1344 bool changed
= false;
1348 int idx
= path
->num_events () - 1;
1351 /* Prune [..., call, function-entry, return, ...] triples. */
1352 if (idx
+ 2 < (signed)path
->num_events ()
1353 && path
->get_checker_event (idx
)->is_call_p ()
1354 && path
->get_checker_event (idx
+ 1)->is_function_entry_p ()
1355 && path
->get_checker_event (idx
+ 2)->is_return_p ())
1360 (path
->get_checker_event (idx
)->get_desc (false));
1361 log ("filtering events %i-%i:"
1362 " irrelevant call/entry/return: %s",
1363 idx
, idx
+ 2, desc
.m_buffer
);
1366 path
->delete_event (idx
+ 2);
1367 path
->delete_event (idx
+ 1);
1368 path
->delete_event (idx
);
1374 /* Prune [..., call, return, ...] pairs
1375 (for -fanalyzer-verbosity=0). */
1376 if (idx
+ 1 < (signed)path
->num_events ()
1377 && path
->get_checker_event (idx
)->is_call_p ()
1378 && path
->get_checker_event (idx
+ 1)->is_return_p ())
1383 (path
->get_checker_event (idx
)->get_desc (false));
1384 log ("filtering events %i-%i:"
1385 " irrelevant call/return: %s",
1386 idx
, idx
+ 1, desc
.m_buffer
);
1389 path
->delete_event (idx
+ 1);
1390 path
->delete_event (idx
);
1403 /* Final pass of diagnostic_manager::prune_path.
1405 If all we're left with is in one function, then filter function entry
1409 diagnostic_manager::finish_pruning (checker_path
*path
) const
1411 if (!path
->interprocedural_p ())
1413 int idx
= path
->num_events () - 1;
1414 while (idx
>= 0 && idx
< (signed)path
->num_events ())
1416 checker_event
*base_event
= path
->get_checker_event (idx
);
1417 if (base_event
->m_kind
== EK_FUNCTION_ENTRY
)
1419 log ("filtering event %i:"
1420 " function entry for purely intraprocedural path", idx
);
1421 path
->delete_event (idx
);
1430 #endif /* #if ENABLE_ANALYZER */