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"
39 #include "ordered-hash-map.h"
40 #include "analyzer/analyzer.h"
41 #include "analyzer/analyzer-logging.h"
42 #include "analyzer/sm.h"
43 #include "analyzer/pending-diagnostic.h"
44 #include "analyzer/diagnostic-manager.h"
45 #include "analyzer/call-string.h"
46 #include "analyzer/program-point.h"
47 #include "analyzer/store.h"
48 #include "analyzer/region-model.h"
49 #include "analyzer/constraint-manager.h"
51 #include "basic-block.h"
53 #include "gimple-iterator.h"
56 #include "analyzer/supergraph.h"
57 #include "analyzer/program-state.h"
58 #include "analyzer/exploded-graph.h"
59 #include "analyzer/checker-path.h"
60 #include "analyzer/reachability.h"
66 /* class saved_diagnostic. */
68 /* saved_diagnostic's ctor.
69 Take ownership of D and STMT_FINDER. */
71 saved_diagnostic::saved_diagnostic (const state_machine
*sm
,
72 const exploded_node
*enode
,
73 const supernode
*snode
, const gimple
*stmt
,
74 stmt_finder
*stmt_finder
,
77 state_machine::state_t state
,
78 pending_diagnostic
*d
)
79 : m_sm (sm
), m_enode (enode
), m_snode (snode
), m_stmt (stmt
),
80 /* stmt_finder could be on-stack; we want our own copy that can
82 m_stmt_finder (stmt_finder
? stmt_finder
->clone () : NULL
),
83 m_var (var
), m_sval (sval
), m_state (state
),
84 m_d (d
), m_trailing_eedge (NULL
),
85 m_status (STATUS_NEW
), m_epath_length (0), m_problem (NULL
)
87 gcc_assert (m_stmt
|| m_stmt_finder
);
89 /* We must have an enode in order to be able to look for paths
90 through the exploded_graph to this diagnostic. */
94 /* saved_diagnostic's dtor. */
96 saved_diagnostic::~saved_diagnostic ()
104 saved_diagnostic::operator== (const saved_diagnostic
&other
) const
106 return (m_sm
== other
.m_sm
107 /* We don't compare m_enode. */
108 && m_snode
== other
.m_snode
109 && m_stmt
== other
.m_stmt
110 /* We don't compare m_stmt_finder. */
111 && pending_diagnostic::same_tree_p (m_var
, other
.m_var
)
112 && m_state
== other
.m_state
113 && m_d
->equal_p (*other
.m_d
)
114 && m_trailing_eedge
== other
.m_trailing_eedge
);
117 /* State for building a checker_path from a particular exploded_path.
118 In particular, this precomputes reachability information: the set of
119 source enodes for which a path be found to the diagnostic enode. */
124 path_builder (const exploded_graph
&eg
,
125 const exploded_path
&epath
)
127 m_diag_enode (epath
.get_final_enode ()),
128 m_reachability (eg
, m_diag_enode
)
131 const exploded_node
*get_diag_node () const { return m_diag_enode
; }
133 bool reachable_from_p (const exploded_node
*src_enode
) const
135 return m_reachability
.reachable_from_p (src_enode
);
138 const extrinsic_state
&get_ext_state () const { return m_eg
.get_ext_state (); }
141 typedef reachability
<eg_traits
> enode_reachability
;
143 const exploded_graph
&m_eg
;
145 /* The enode where the diagnostic occurs. */
146 const exploded_node
*m_diag_enode
;
148 /* Precompute all enodes from which the diagnostic is reachable. */
149 enode_reachability m_reachability
;
152 /* class diagnostic_manager. */
154 /* diagnostic_manager's ctor. */
156 diagnostic_manager::diagnostic_manager (logger
*logger
, engine
*eng
,
158 : log_user (logger
), m_eng (eng
), m_verbosity (verbosity
)
162 /* Queue pending_diagnostic D at ENODE for later emission. */
165 diagnostic_manager::add_diagnostic (const state_machine
*sm
,
166 const exploded_node
*enode
,
167 const supernode
*snode
, const gimple
*stmt
,
171 state_machine::state_t state
,
172 pending_diagnostic
*d
)
174 LOG_FUNC (get_logger ());
176 /* We must have an enode in order to be able to look for paths
177 through the exploded_graph to the diagnostic. */
181 = new saved_diagnostic (sm
, enode
, snode
, stmt
, finder
, var
, sval
,
183 m_saved_diagnostics
.safe_push (sd
);
185 log ("adding saved diagnostic %i at SN %i: %qs",
186 m_saved_diagnostics
.length () - 1,
187 snode
->m_index
, d
->get_kind ());
190 /* Queue pending_diagnostic D at ENODE for later emission. */
193 diagnostic_manager::add_diagnostic (const exploded_node
*enode
,
194 const supernode
*snode
, const gimple
*stmt
,
196 pending_diagnostic
*d
)
199 add_diagnostic (NULL
, enode
, snode
, stmt
, finder
, NULL_TREE
, NULL
, 0, d
);
202 /* A class for identifying sets of duplicated pending_diagnostic.
204 We want to find the simplest dedupe_candidate amongst those that share a
210 dedupe_key (const saved_diagnostic
&sd
,
211 const exploded_path
&epath
)
212 : m_sd (sd
), m_stmt (sd
.m_stmt
)
214 /* Support deferring the choice of stmt until after an emission path has
215 been built, using an optional stmt_finder. */
218 gcc_assert (sd
.m_stmt_finder
);
219 m_stmt
= sd
.m_stmt_finder
->find_stmt (epath
);
224 hashval_t
hash () const
226 inchash::hash hstate
;
227 hstate
.add_ptr (m_stmt
);
229 return hstate
.end ();
231 bool operator== (const dedupe_key
&other
) const
233 return (m_sd
== other
.m_sd
234 && m_stmt
== other
.m_stmt
);
237 location_t
get_location () const
239 return m_stmt
->location
;
242 /* A qsort comparator for use by dedupe_winners::emit_best
243 to sort them into location_t order. */
246 comparator (const void *p1
, const void *p2
)
248 const dedupe_key
*pk1
= *(const dedupe_key
* const *)p1
;
249 const dedupe_key
*pk2
= *(const dedupe_key
* const *)p2
;
251 location_t loc1
= pk1
->get_location ();
252 location_t loc2
= pk2
->get_location ();
254 return linemap_compare_locations (line_table
, loc2
, loc1
);
257 const saved_diagnostic
&m_sd
;
258 const gimple
*m_stmt
;
261 /* The value of a slot for a dedupe_key within dedupe_winners:
262 the exploded_path for the best candidate for that key, and the
263 number of duplicates seen so far. */
265 class dedupe_candidate
268 // has the exploded_path
269 dedupe_candidate (const shortest_exploded_paths
&sp
,
270 saved_diagnostic
*sd
)
271 : m_epath (sp
.get_shortest_path (sd
->m_enode
)),
276 unsigned length () const { return m_epath
.length (); }
277 const exploded_path
&get_path () const { return m_epath
; }
279 void add_duplicate () { m_num_dupes
++; }
280 int get_num_dupes () const { return m_num_dupes
; }
283 exploded_path m_epath
;
288 /* Traits for use by dedupe_winners. */
290 class dedupe_hash_map_traits
293 typedef const dedupe_key
*key_type
;
294 typedef dedupe_candidate
*value_type
;
295 typedef dedupe_candidate
*compare_type
;
297 static inline hashval_t
hash (const key_type
&v
)
301 static inline bool equal_keys (const key_type
&k1
, const key_type
&k2
)
305 template <typename T
>
306 static inline void remove (T
&)
310 template <typename T
>
311 static inline void mark_deleted (T
&entry
)
313 entry
.m_key
= reinterpret_cast<key_type
> (1);
315 template <typename T
>
316 static inline void mark_empty (T
&entry
)
320 template <typename T
>
321 static inline bool is_deleted (const T
&entry
)
323 return entry
.m_key
== reinterpret_cast<key_type
> (1);
325 template <typename T
>
326 static inline bool is_empty (const T
&entry
)
328 return entry
.m_key
== NULL
;
330 static const bool empty_zero_p
= true;
333 /* A class for deduplicating diagnostics and finding (and emitting) the
334 best diagnostic within each partition. */
339 dedupe_winners (engine
*eng
) : m_engine (eng
) {}
343 /* Delete all keys and candidates. */
344 for (map_t::iterator iter
= m_map
.begin ();
345 iter
!= m_map
.end ();
348 delete (*iter
).first
;
349 delete (*iter
).second
;
353 /* Determine an exploded_path for SD using SP and, if it's feasible,
354 determine if it's the best seen so far for its dedupe_key.
355 Retain the winner for each dedupe_key, and discard the rest. */
357 void add (logger
*logger
,
358 const shortest_exploded_paths
&sp
,
359 const exploded_graph
*eg
,
360 saved_diagnostic
*sd
)
362 /* Build a dedupe_candidate for SD.
363 This uses SP to build an exploded_path. */
364 dedupe_candidate
*dc
= new dedupe_candidate (sp
, sd
);
366 sd
->set_epath_length (dc
->length ());
368 /* Verify that the epath is feasible.
369 State-merging means that not every path in the epath corresponds
370 to a feasible one w.r.t. states.
371 Here we simply check each duplicate saved_diagnostic's
372 shortest_path, and reject any that aren't feasible.
373 This could introduce false negatives, as there could be longer
374 feasible paths within the egraph. */
376 logger
->log ("considering %qs at EN: %i, SN: %i",
377 sd
->m_d
->get_kind (), sd
->m_enode
->m_index
,
378 sd
->m_snode
->m_index
);
380 feasibility_problem
*p
= NULL
;
381 if (!dc
->get_path ().feasible_p (logger
, &p
, m_engine
, eg
))
384 logger
->log ("rejecting %qs at EN: %i, SN: %i"
385 " due to infeasible path",
386 sd
->m_d
->get_kind (), sd
->m_enode
->m_index
,
387 sd
->m_snode
->m_index
);
388 sd
->set_infeasible (p
);
394 logger
->log ("accepting %qs at EN: %i, SN: %i with feasible path",
395 sd
->m_d
->get_kind (), sd
->m_enode
->m_index
,
396 sd
->m_snode
->m_index
);
400 dedupe_key
*key
= new dedupe_key (*sd
, dc
->get_path ());
401 if (dedupe_candidate
**slot
= m_map
.get (key
))
404 logger
->log ("already have this dedupe_key");
406 (*slot
)->add_duplicate ();
408 if (dc
->length () < (*slot
)->length ())
410 /* We've got a shorter path for the key; replace
411 the current candidate. */
413 logger
->log ("length %i is better than existing length %i;"
414 " taking over this dedupe_key",
415 dc
->length (), (*slot
)->length ());
416 dc
->m_num_dupes
= (*slot
)->get_num_dupes ();
421 /* We haven't beaten the current best candidate;
422 drop the new candidate. */
425 logger
->log ("length %i isn't better than existing length %i;"
426 " dropping this candidate",
427 dc
->length (), (*slot
)->length ());
434 /* This is the first candidate for this key. */
437 logger
->log ("first candidate for this dedupe_key");
441 /* Emit the simplest diagnostic within each set. */
443 void emit_best (diagnostic_manager
*dm
,
444 const exploded_graph
&eg
)
446 LOG_SCOPE (dm
->get_logger ());
448 /* Get keys into a vec for sorting. */
449 auto_vec
<const dedupe_key
*> keys (m_map
.elements ());
450 for (map_t::iterator iter
= m_map
.begin ();
451 iter
!= m_map
.end ();
453 keys
.quick_push ((*iter
).first
);
455 dm
->log ("# keys after de-duplication: %i", keys
.length ());
457 /* Sort into a good emission order. */
458 keys
.qsort (dedupe_key::comparator
);
460 /* Emit the best candidate for each key. */
462 const dedupe_key
*key
;
463 FOR_EACH_VEC_ELT (keys
, i
, key
)
465 dedupe_candidate
**slot
= m_map
.get (key
);
467 const dedupe_candidate
&dc
= **slot
;
469 dm
->emit_saved_diagnostic (eg
, key
->m_sd
,
470 dc
.get_path (), key
->m_stmt
,
471 dc
.get_num_dupes ());
478 /* This maps from each dedupe_key to a current best dedupe_candidate. */
480 typedef hash_map
<const dedupe_key
*, dedupe_candidate
*,
481 dedupe_hash_map_traits
> map_t
;
485 /* Emit all saved diagnostics. */
488 diagnostic_manager::emit_saved_diagnostics (const exploded_graph
&eg
)
490 LOG_SCOPE (get_logger ());
491 auto_timevar
tv (TV_ANALYZER_DIAGNOSTICS
);
492 log ("# saved diagnostics: %i", m_saved_diagnostics
.length ());
496 saved_diagnostic
*sd
;
497 FOR_EACH_VEC_ELT (m_saved_diagnostics
, i
, sd
)
498 log ("[%i] sd: %qs at EN: %i, SN: %i",
499 i
, sd
->m_d
->get_kind (), sd
->m_enode
->m_index
,
500 sd
->m_snode
->m_index
);
503 if (m_saved_diagnostics
.length () == 0)
506 /* Compute the shortest_paths once, sharing it between all diagnostics. */
507 shortest_exploded_paths
sp (eg
, eg
.get_origin ());
509 /* Iterate through all saved diagnostics, adding them to a dedupe_winners
510 instance. This partitions the saved diagnostics by dedupe_key,
511 generating exploded_paths for them, and retaining the best one in each
513 dedupe_winners
best_candidates (eg
.get_engine ());
516 saved_diagnostic
*sd
;
517 FOR_EACH_VEC_ELT (m_saved_diagnostics
, i
, sd
)
518 best_candidates
.add (get_logger (), sp
, &eg
, sd
);
520 /* For each dedupe-key, call emit_saved_diagnostic on the "best"
522 best_candidates
.emit_best (this, eg
);
525 /* Given a saved_diagnostic SD at STMT with feasible path EPATH through EG,
526 create an checker_path of suitable events and use it to call
527 SD's underlying pending_diagnostic "emit" vfunc to emit a diagnostic. */
530 diagnostic_manager::emit_saved_diagnostic (const exploded_graph
&eg
,
531 const saved_diagnostic
&sd
,
532 const exploded_path
&epath
,
536 LOG_SCOPE (get_logger ());
537 log ("sd: %qs at SN: %i", sd
.m_d
->get_kind (), sd
.m_snode
->m_index
);
538 log ("num dupes: %i", num_dupes
);
540 pretty_printer
*pp
= global_dc
->printer
->clone ();
542 /* Precompute all enodes from which the diagnostic is reachable. */
543 path_builder
pb (eg
, epath
);
545 /* This is the diagnostic_path subclass that will be built for
547 checker_path emission_path
;
549 /* Populate emission_path with a full description of EPATH. */
550 build_emission_path (pb
, epath
, &emission_path
);
552 /* Now prune it to just cover the most pertinent events. */
553 prune_path (&emission_path
, sd
.m_sm
, sd
.m_sval
, sd
.m_state
);
555 /* Add a final event to the path, covering the diagnostic itself.
556 We use the final enode from the epath, which might be different from
557 the sd.m_enode, as the dedupe code doesn't care about enodes, just
559 emission_path
.add_final_event (sd
.m_sm
, epath
.get_final_enode (), stmt
,
560 sd
.m_var
, sd
.m_state
);
562 /* The "final" event might not be final; if the saved_diagnostic has a
563 trailing eedge stashed, add any events for it. This is for use
564 in handling longjmp, to show where a longjmp is rewinding to. */
565 if (sd
.m_trailing_eedge
)
566 add_events_for_eedge (pb
, *sd
.m_trailing_eedge
, &emission_path
);
568 emission_path
.prepare_for_emission (sd
.m_d
);
570 gcc_rich_location
rich_loc (get_stmt_location (stmt
, sd
.m_snode
->m_fun
));
571 rich_loc
.set_path (&emission_path
);
573 auto_diagnostic_group d
;
574 auto_cfun
sentinel (sd
.m_snode
->m_fun
);
575 if (sd
.m_d
->emit (&rich_loc
))
577 if (flag_analyzer_show_duplicate_count
&& num_dupes
> 0)
578 inform_n (stmt
->location
, num_dupes
,
579 "%i duplicate", "%i duplicates",
585 /* Emit a "path" of events to EMISSION_PATH describing the exploded path
589 diagnostic_manager::build_emission_path (const path_builder
&pb
,
590 const exploded_path
&epath
,
591 checker_path
*emission_path
) const
593 LOG_SCOPE (get_logger ());
594 for (unsigned i
= 0; i
< epath
.m_edges
.length (); i
++)
596 const exploded_edge
*eedge
= epath
.m_edges
[i
];
597 add_events_for_eedge (pb
, *eedge
, emission_path
);
601 /* Subclass of state_change_visitor that creates state_change_event
604 class state_change_event_creator
: public state_change_visitor
607 state_change_event_creator (const exploded_edge
&eedge
,
608 checker_path
*emission_path
)
610 m_emission_path (emission_path
)
613 bool on_global_state_change (const state_machine
&sm
,
614 state_machine::state_t src_sm_val
,
615 state_machine::state_t dst_sm_val
)
618 const exploded_node
*src_node
= m_eedge
.m_src
;
619 const program_point
&src_point
= src_node
->get_point ();
620 const int src_stack_depth
= src_point
.get_stack_depth ();
621 const exploded_node
*dst_node
= m_eedge
.m_dest
;
622 const gimple
*stmt
= src_point
.get_stmt ();
623 const supernode
*supernode
= src_point
.get_supernode ();
624 const program_state
&dst_state
= dst_node
->get_state ();
626 int stack_depth
= src_stack_depth
;
628 m_emission_path
->add_event (new state_change_event (supernode
,
640 bool on_state_change (const state_machine
&sm
,
641 state_machine::state_t src_sm_val
,
642 state_machine::state_t dst_sm_val
,
644 const svalue
*dst_origin_sval
) FINAL OVERRIDE
646 const exploded_node
*src_node
= m_eedge
.m_src
;
647 const program_point
&src_point
= src_node
->get_point ();
648 const int src_stack_depth
= src_point
.get_stack_depth ();
649 const exploded_node
*dst_node
= m_eedge
.m_dest
;
650 const gimple
*stmt
= src_point
.get_stmt ();
651 const supernode
*supernode
= src_point
.get_supernode ();
652 const program_state
&dst_state
= dst_node
->get_state ();
654 int stack_depth
= src_stack_depth
;
657 && m_eedge
.m_sedge
->m_kind
== SUPEREDGE_CFG_EDGE
)
659 supernode
= src_point
.get_supernode ();
660 stmt
= supernode
->get_last_stmt ();
661 stack_depth
= src_stack_depth
;
664 /* Bulletproofing for state changes at calls/returns;
665 TODO: is there a better way? */
669 m_emission_path
->add_event (new state_change_event (supernode
,
681 const exploded_edge
&m_eedge
;
682 checker_path
*m_emission_path
;
685 /* Compare SRC_STATE and DST_STATE (which use EXT_STATE), and call
686 VISITOR's on_state_change for every sm-state change that occurs
687 to a tree, and on_global_state_change for every global state change
690 This determines the state changes that ought to be reported to
691 the user: a combination of the effects of changes to sm_state_map
692 (which maps svalues to sm-states), and of region_model changes
693 (which map trees to svalues).
695 Bail out early and return true if any call to on_global_state_change
696 or on_state_change returns true, otherwise return false.
698 This is split out to make it easier to experiment with changes to
699 exploded_node granularity (so that we can observe what state changes
700 lead to state_change_events being emitted). */
703 for_each_state_change (const program_state
&src_state
,
704 const program_state
&dst_state
,
705 const extrinsic_state
&ext_state
,
706 state_change_visitor
*visitor
)
708 gcc_assert (src_state
.m_checker_states
.length ()
709 == ext_state
.get_num_checkers ());
710 gcc_assert (dst_state
.m_checker_states
.length ()
711 == ext_state
.get_num_checkers ());
712 for (unsigned i
= 0; i
< ext_state
.get_num_checkers (); i
++)
714 const state_machine
&sm
= ext_state
.get_sm (i
);
715 const sm_state_map
&src_smap
= *src_state
.m_checker_states
[i
];
716 const sm_state_map
&dst_smap
= *dst_state
.m_checker_states
[i
];
718 /* Add events for any global state changes. */
719 if (src_smap
.get_global_state () != dst_smap
.get_global_state ())
720 if (visitor
->on_global_state_change (sm
,
721 src_smap
.get_global_state (),
722 dst_smap
.get_global_state ()))
725 /* Add events for per-svalue state changes. */
726 for (sm_state_map::iterator_t iter
= dst_smap
.begin ();
727 iter
!= dst_smap
.end ();
730 const svalue
*sval
= (*iter
).first
;
731 state_machine::state_t dst_sm_val
= (*iter
).second
.m_state
;
732 state_machine::state_t src_sm_val
733 = src_smap
.get_state (sval
, ext_state
);
734 if (dst_sm_val
!= src_sm_val
)
736 const svalue
*origin_sval
= (*iter
).second
.m_origin
;
737 if (visitor
->on_state_change (sm
, src_sm_val
, dst_sm_val
,
746 /* An sm_context for adding state_change_event on assignments to NULL,
747 where the default state isn't m_start. Storing such state in the
748 sm_state_map would lead to bloat of the exploded_graph, so we want
749 to leave it as a default state, and inject state change events here
750 when we have a diagnostic.
751 Find transitions of constants, for handling on_zero_assignment. */
753 struct null_assignment_sm_context
: public sm_context
755 null_assignment_sm_context (int sm_idx
,
756 const state_machine
&sm
,
757 const program_state
*old_state
,
758 const program_state
*new_state
,
760 const program_point
*point
,
761 checker_path
*emission_path
,
762 const extrinsic_state
&ext_state
)
763 : sm_context (sm_idx
, sm
), m_old_state (old_state
), m_new_state (new_state
),
764 m_stmt (stmt
), m_point (point
), m_emission_path (emission_path
),
765 m_ext_state (ext_state
)
769 tree
get_fndecl_for_call (const gcall */
*call*/
) FINAL OVERRIDE
774 state_machine::state_t
get_state (const gimple
*stmt ATTRIBUTE_UNUSED
,
775 tree var
) FINAL OVERRIDE
777 const svalue
*var_old_sval
778 = m_old_state
->m_region_model
->get_rvalue (var
, NULL
);
779 const sm_state_map
*old_smap
= m_old_state
->m_checker_states
[m_sm_idx
];
781 state_machine::state_t current
782 = old_smap
->get_state (var_old_sval
, m_ext_state
);
787 void set_next_state (const gimple
*stmt
,
789 state_machine::state_t to
,
790 tree origin ATTRIBUTE_UNUSED
) FINAL OVERRIDE
792 state_machine::state_t from
= get_state (stmt
, var
);
793 if (from
!= m_sm
.get_start_state ())
796 const svalue
*var_new_sval
797 = m_new_state
->m_region_model
->get_rvalue (var
, NULL
);
798 const supernode
*supernode
= m_point
->get_supernode ();
799 int stack_depth
= m_point
->get_stack_depth ();
801 m_emission_path
->add_event (new state_change_event (supernode
,
811 void warn (const supernode
*, const gimple
*,
812 tree
, pending_diagnostic
*d
) FINAL OVERRIDE
817 tree
get_diagnostic_tree (tree expr
) FINAL OVERRIDE
822 state_machine::state_t
get_global_state () const FINAL OVERRIDE
827 void set_global_state (state_machine::state_t
) FINAL OVERRIDE
832 void on_custom_transition (custom_transition
*) FINAL OVERRIDE
836 tree
is_zero_assignment (const gimple
*stmt
) FINAL OVERRIDE
838 const gassign
*assign_stmt
= dyn_cast
<const gassign
*> (stmt
);
841 if (const svalue
*sval
842 = m_new_state
->m_region_model
->get_gassign_result (assign_stmt
, NULL
))
843 if (tree cst
= sval
->maybe_get_constant ())
845 return gimple_assign_lhs (assign_stmt
);
849 const program_state
*m_old_state
;
850 const program_state
*m_new_state
;
851 const gimple
*m_stmt
;
852 const program_point
*m_point
;
853 state_change_visitor
*m_visitor
;
854 checker_path
*m_emission_path
;
855 const extrinsic_state
&m_ext_state
;
858 /* Subroutine of diagnostic_manager::build_emission_path.
859 Add any events for EEDGE to EMISSION_PATH. */
862 diagnostic_manager::add_events_for_eedge (const path_builder
&pb
,
863 const exploded_edge
&eedge
,
864 checker_path
*emission_path
) const
866 const exploded_node
*src_node
= eedge
.m_src
;
867 const program_point
&src_point
= src_node
->get_point ();
868 const exploded_node
*dst_node
= eedge
.m_dest
;
869 const program_point
&dst_point
= dst_node
->get_point ();
870 const int dst_stack_depth
= dst_point
.get_stack_depth ();
873 get_logger ()->start_log_line ();
874 pretty_printer
*pp
= get_logger ()->get_printer ();
875 pp_printf (pp
, "EN %i -> EN %i: ",
876 eedge
.m_src
->m_index
,
877 eedge
.m_dest
->m_index
);
878 src_point
.print (pp
, format (false));
879 pp_string (pp
, "-> ");
880 dst_point
.print (pp
, format (false));
881 get_logger ()->end_log_line ();
883 const program_state
&src_state
= src_node
->get_state ();
884 const program_state
&dst_state
= dst_node
->get_state ();
886 /* Add state change events for the states that have changed.
887 We add these before events for superedges, so that if we have a
888 state_change_event due to following an edge, we'll get this sequence
894 | (1) assuming 'ptr' is non-NULL (state_change_event)
895 | (2) following 'false' branch... (start_cfg_edge_event)
897 | do_something (ptr);
900 | (3) ...to here (end_cfg_edge_event). */
901 state_change_event_creator
visitor (eedge
, emission_path
);
902 for_each_state_change (src_state
, dst_state
, pb
.get_ext_state (),
905 /* Allow non-standard edges to add events, e.g. when rewinding from
906 longjmp to a setjmp. */
907 if (eedge
.m_custom_info
)
908 eedge
.m_custom_info
->add_events_to_path (emission_path
, eedge
);
910 /* Add events for superedges, function entries, and for statements. */
911 switch (dst_point
.get_kind ())
915 case PK_BEFORE_SUPERNODE
:
916 if (src_point
.get_kind () == PK_AFTER_SUPERNODE
)
919 add_events_for_superedge (pb
, eedge
, emission_path
);
921 /* Add function entry events. */
922 if (dst_point
.get_supernode ()->entry_p ())
924 emission_path
->add_event
925 (new function_entry_event
926 (dst_point
.get_supernode ()->get_start_location (),
927 dst_point
.get_fndecl (),
933 const gimple
*stmt
= dst_point
.get_stmt ();
934 const gcall
*call
= dyn_cast
<const gcall
*> (stmt
);
935 if (call
&& is_setjmp_call_p (call
))
936 emission_path
->add_event
937 (new setjmp_event (stmt
->location
,
939 dst_point
.get_fndecl (),
943 emission_path
->add_event
944 (new statement_event (stmt
,
945 dst_point
.get_fndecl (),
946 dst_stack_depth
, dst_state
));
948 /* Create state change events for assignment to NULL.
949 Iterate through the stmts in dst_enode, adding state change
951 if (dst_state
.m_region_model
)
953 program_state
iter_state (dst_state
);
954 program_point
iter_point (dst_point
);
957 const gimple
*stmt
= iter_point
.get_stmt ();
958 if (const gassign
*assign
= dyn_cast
<const gassign
*> (stmt
))
960 const extrinsic_state
&ext_state
= pb
.get_ext_state ();
961 program_state
old_state (iter_state
);
962 iter_state
.m_region_model
->on_assignment (assign
, NULL
);
963 for (unsigned i
= 0; i
< ext_state
.get_num_checkers (); i
++)
965 const state_machine
&sm
= ext_state
.get_sm (i
);
966 null_assignment_sm_context
sm_ctxt (i
, sm
,
972 pb
.get_ext_state ());
973 sm
.on_stmt (&sm_ctxt
, dst_point
.get_supernode (), stmt
);
974 // TODO: what about phi nodes?
977 iter_point
.next_stmt ();
978 if (iter_point
.get_kind () == PK_AFTER_SUPERNODE
979 || (dst_node
->m_succs
.length () > 1
981 == dst_node
->m_succs
[0]->m_dest
->get_point ())))
990 /* Return true if EEDGE is a significant edge in the path to the diagnostic
993 Consider all of the sibling out-eedges from the same source enode
995 If there's no path from the destinations of those eedges to the
996 diagnostic enode, then we have to take this eedge and thus it's
999 Conversely if there is a path from the destination of any other sibling
1000 eedge to the diagnostic enode, then this edge is insignificant.
1002 Example 1: redundant if-else:
1010 D is reachable by either B or C, so neither of these edges
1013 Example 2: pertinent if-else:
1018 (C) [NECESSARY CONDITION] | |
1019 (D) [POSSIBLE DIAGNOSTIC] D1 D2
1021 D becomes D1 and D2 in the exploded graph, where the diagnostic occurs
1022 at D2. D2 is only reachable via C, so the A -> C edge is significant.
1024 Example 3: redundant loop:
1026 (A) while (...) +-->A
1032 D is reachable from both B and C, so the A->C edge is not significant. */
1035 diagnostic_manager::significant_edge_p (const path_builder
&pb
,
1036 const exploded_edge
&eedge
) const
1039 exploded_edge
*sibling
;
1040 FOR_EACH_VEC_ELT (eedge
.m_src
->m_succs
, i
, sibling
)
1042 if (sibling
== &eedge
)
1044 if (pb
.reachable_from_p (sibling
->m_dest
))
1047 get_logger ()->log (" edge EN: %i -> EN: %i is insignificant as"
1048 " EN: %i is also reachable via"
1049 " EN: %i -> EN: %i",
1050 eedge
.m_src
->m_index
, eedge
.m_dest
->m_index
,
1051 pb
.get_diag_node ()->m_index
,
1052 sibling
->m_src
->m_index
,
1053 sibling
->m_dest
->m_index
);
1061 /* Subroutine of diagnostic_manager::add_events_for_eedge
1062 where EEDGE has an underlying superedge i.e. a CFG edge,
1063 or an interprocedural call/return.
1064 Add any events for the superedge to EMISSION_PATH. */
1067 diagnostic_manager::add_events_for_superedge (const path_builder
&pb
,
1068 const exploded_edge
&eedge
,
1069 checker_path
*emission_path
)
1072 gcc_assert (eedge
.m_sedge
);
1074 /* Don't add events for insignificant edges at verbosity levels below 3. */
1075 if (m_verbosity
< 3)
1076 if (!significant_edge_p (pb
, eedge
))
1079 const exploded_node
*src_node
= eedge
.m_src
;
1080 const program_point
&src_point
= src_node
->get_point ();
1081 const exploded_node
*dst_node
= eedge
.m_dest
;
1082 const program_point
&dst_point
= dst_node
->get_point ();
1083 const int src_stack_depth
= src_point
.get_stack_depth ();
1084 const int dst_stack_depth
= dst_point
.get_stack_depth ();
1085 const gimple
*last_stmt
= src_point
.get_supernode ()->get_last_stmt ();
1087 switch (eedge
.m_sedge
->m_kind
)
1089 case SUPEREDGE_CFG_EDGE
:
1091 emission_path
->add_event
1092 (new start_cfg_edge_event (eedge
,
1094 ? last_stmt
->location
1095 : UNKNOWN_LOCATION
),
1096 src_point
.get_fndecl (),
1098 emission_path
->add_event
1099 (new end_cfg_edge_event (eedge
,
1100 dst_point
.get_supernode ()->get_start_location (),
1101 dst_point
.get_fndecl (),
1106 case SUPEREDGE_CALL
:
1108 emission_path
->add_event
1109 (new call_event (eedge
,
1111 ? last_stmt
->location
1112 : UNKNOWN_LOCATION
),
1113 src_point
.get_fndecl (),
1118 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
1120 /* TODO: add a subclass for this, or generate events for the
1122 emission_path
->add_event
1123 (new debug_event ((last_stmt
1124 ? last_stmt
->location
1125 : UNKNOWN_LOCATION
),
1126 src_point
.get_fndecl (),
1132 case SUPEREDGE_RETURN
:
1134 const return_superedge
*return_edge
1135 = as_a
<const return_superedge
*> (eedge
.m_sedge
);
1137 const gcall
*call_stmt
= return_edge
->get_call_stmt ();
1138 emission_path
->add_event
1139 (new return_event (eedge
,
1141 ? call_stmt
->location
1142 : UNKNOWN_LOCATION
),
1143 dst_point
.get_fndecl (),
1150 /* Prune PATH, based on the verbosity level, to the most pertinent
1151 events for a diagnostic that involves VAR ending in state STATE
1152 (for state machine SM).
1154 PATH is updated in place, and the redundant checker_events are deleted.
1156 As well as deleting events, call record_critical_state on events in
1157 which state critical to the pending_diagnostic is being handled; see
1158 the comment for diagnostic_manager::prune_for_sm_diagnostic. */
1161 diagnostic_manager::prune_path (checker_path
*path
,
1162 const state_machine
*sm
,
1164 state_machine::state_t state
) const
1166 LOG_FUNC (get_logger ());
1167 path
->maybe_log (get_logger (), "path");
1168 prune_for_sm_diagnostic (path
, sm
, sval
, state
);
1169 prune_interproc_events (path
);
1170 finish_pruning (path
);
1171 path
->maybe_log (get_logger (), "pruned");
1174 /* A cheap test to determine if EXPR can be the expression of interest in
1175 an sm-diagnostic, so that we can reject cases where we have a non-lvalue.
1176 We don't have always have a model when calling this, so we can't use
1177 tentative_region_model_context, so there can be false positives. */
1180 can_be_expr_of_interest_p (tree expr
)
1185 /* Reject constants. */
1186 if (CONSTANT_CLASS_P (expr
))
1189 /* Otherwise assume that it can be an lvalue. */
1193 /* First pass of diagnostic_manager::prune_path: apply verbosity level,
1194 pruning unrelated state change events.
1196 Iterate backwards through PATH, skipping state change events that aren't
1197 VAR but update the pertinent VAR when state-copying occurs.
1199 As well as deleting events, call record_critical_state on events in
1200 which state critical to the pending_diagnostic is being handled, so
1201 that the event's get_desc vfunc can potentially supply a more precise
1202 description of the event to the user.
1204 "calling 'foo' from 'bar'"
1206 "passing possibly-NULL pointer 'ptr' to 'foo' from 'bar' as param 1"
1207 when the diagnostic relates to later dereferencing 'ptr'. */
1210 diagnostic_manager::prune_for_sm_diagnostic (checker_path
*path
,
1211 const state_machine
*sm
,
1213 state_machine::state_t state
) const
1215 int idx
= path
->num_events () - 1;
1216 while (idx
>= 0 && idx
< (signed)path
->num_events ())
1218 checker_event
*base_event
= path
->get_checker_event (idx
);
1225 label_text sval_desc
= sval
->get_desc ();
1226 log ("considering event %i (%s), with sval: %qs, state: %qs",
1227 idx
, event_kind_to_string (base_event
->m_kind
),
1228 sval_desc
.m_buffer
, state
->get_name ());
1231 log ("considering event %i (%s), with global state: %qs",
1232 idx
, event_kind_to_string (base_event
->m_kind
),
1233 state
->get_name ());
1236 log ("considering event %i", idx
);
1239 switch (base_event
->m_kind
)
1245 if (m_verbosity
< 4)
1247 log ("filtering event %i: debug event", idx
);
1248 path
->delete_event (idx
);
1253 /* Don't filter custom events. */
1258 if (m_verbosity
< 4)
1260 log ("filtering event %i: statement event", idx
);
1261 path
->delete_event (idx
);
1266 case EK_FUNCTION_ENTRY
:
1267 if (m_verbosity
< 1)
1269 log ("filtering event %i: function entry", idx
);
1270 path
->delete_event (idx
);
1274 case EK_STATE_CHANGE
:
1276 state_change_event
*state_change
= (state_change_event
*)base_event
;
1277 gcc_assert (state_change
->m_dst_state
.m_region_model
);
1279 if (state_change
->m_sval
== sval
)
1281 if (state_change
->m_origin
)
1285 label_text sval_desc
= sval
->get_desc ();
1286 label_text origin_sval_desc
1287 = state_change
->m_origin
->get_desc ();
1289 " switching var of interest from %qs to %qs",
1290 idx
, sval_desc
.m_buffer
,
1291 origin_sval_desc
.m_buffer
);
1293 sval
= state_change
->m_origin
;
1295 log ("event %i: switching state of interest from %qs to %qs",
1296 idx
, state_change
->m_to
->get_name (),
1297 state_change
->m_from
->get_name ());
1298 state
= state_change
->m_from
;
1300 else if (m_verbosity
< 4)
1304 if (state_change
->m_sval
)
1306 label_text change_sval_desc
1307 = state_change
->m_sval
->get_desc ();
1310 label_text sval_desc
= sval
->get_desc ();
1311 log ("filtering event %i:"
1312 " state change to %qs unrelated to %qs",
1313 idx
, change_sval_desc
.m_buffer
,
1314 sval_desc
.m_buffer
);
1317 log ("filtering event %i: state change to %qs",
1318 idx
, change_sval_desc
.m_buffer
);
1321 log ("filtering event %i: global state change", idx
);
1323 path
->delete_event (idx
);
1328 case EK_START_CFG_EDGE
:
1330 cfg_edge_event
*event
= (cfg_edge_event
*)base_event
;
1332 /* TODO: is this edge significant to var?
1333 See if var can be in other states in the dest, but not
1334 in other states in the src?
1335 Must have multiple sibling edges. */
1337 if (event
->should_filter_p (m_verbosity
))
1339 log ("filtering events %i and %i: CFG edge", idx
, idx
+ 1);
1340 path
->delete_event (idx
);
1341 /* Also delete the corresponding EK_END_CFG_EDGE. */
1342 gcc_assert (path
->get_checker_event (idx
)->m_kind
1343 == EK_END_CFG_EDGE
);
1344 path
->delete_event (idx
);
1349 case EK_END_CFG_EDGE
:
1350 /* These come in pairs with EK_START_CFG_EDGE events and are
1351 filtered when their start event is filtered. */
1356 call_event
*event
= (call_event
*)base_event
;
1357 const callgraph_superedge
& cg_superedge
1358 = event
->get_callgraph_superedge ();
1359 const region_model
*callee_model
1360 = event
->m_eedge
.m_dest
->get_state ().m_region_model
;
1361 tree callee_var
= callee_model
->get_representative_tree (sval
);
1362 /* We could just use caller_model->get_representative_tree (sval);
1363 to get the caller_var, but for now use
1364 map_expr_from_callee_to_caller so as to only record critical
1365 state for parms and the like. */
1368 = cg_superedge
.map_expr_from_callee_to_caller (callee_var
, &expr
);
1373 label_text sval_desc
= sval
->get_desc ();
1375 " recording critical state for %qs at call"
1376 " from %qE in callee to %qE in caller",
1377 idx
, sval_desc
.m_buffer
, callee_var
, caller_var
);
1379 if (expr
.param_p ())
1380 event
->record_critical_state (caller_var
, state
);
1385 case EK_RETURN_EDGE
:
1389 return_event
*event
= (return_event
*)base_event
;
1390 const callgraph_superedge
& cg_superedge
1391 = event
->get_callgraph_superedge ();
1392 const region_model
*caller_model
1393 = event
->m_eedge
.m_dest
->get_state ().m_region_model
;
1394 tree caller_var
= caller_model
->get_representative_tree (sval
);
1397 = cg_superedge
.map_expr_from_caller_to_callee (caller_var
,
1403 label_text sval_desc
= sval
->get_desc ();
1405 " recording critical state for %qs at return"
1406 " from %qE in caller to %qE in callee",
1407 idx
, sval_desc
.m_buffer
, callee_var
, callee_var
);
1409 if (expr
.return_value_p ())
1410 event
->record_critical_state (callee_var
, state
);
1417 /* TODO: only show setjmp_events that matter i.e. those for which
1418 there is a later rewind event using them. */
1419 case EK_REWIND_FROM_LONGJMP
:
1420 case EK_REWIND_TO_SETJMP
:
1424 /* Always show the final "warning" event in the path. */
1431 /* Subroutine of diagnostic_manager::prune_for_sm_diagnostic.
1432 If *EXPR is not suitable to be the expression of interest in
1433 an sm-diagnostic, set *EXPR to NULL and log. */
1436 diagnostic_manager::update_for_unsuitable_sm_exprs (tree
*expr
) const
1439 if (*expr
&& !can_be_expr_of_interest_p (*expr
))
1441 log ("new var %qE is unsuitable; setting var to NULL", *expr
);
1446 /* Second pass of diagnostic_manager::prune_path: remove redundant
1447 interprocedural information.
1450 (1)- calling "f2" from "f1"
1451 (2)--- entry to "f2"
1452 (3)--- calling "f3" from "f2"
1453 (4)----- entry to "f3"
1454 (5)--- returning to "f2" to "f3"
1455 (6)- returning to "f1" to "f2"
1456 with no other intervening events, then none of these events are
1457 likely to be interesting to the user.
1459 Prune [..., call, function-entry, return, ...] triples repeatedly
1460 until nothing has changed. For the example above, this would
1461 remove events (3, 4, 5), and then remove events (1, 2, 6). */
1464 diagnostic_manager::prune_interproc_events (checker_path
*path
) const
1466 bool changed
= false;
1470 int idx
= path
->num_events () - 1;
1473 /* Prune [..., call, function-entry, return, ...] triples. */
1474 if (idx
+ 2 < (signed)path
->num_events ()
1475 && path
->get_checker_event (idx
)->is_call_p ()
1476 && path
->get_checker_event (idx
+ 1)->is_function_entry_p ()
1477 && path
->get_checker_event (idx
+ 2)->is_return_p ())
1482 (path
->get_checker_event (idx
)->get_desc (false));
1483 log ("filtering events %i-%i:"
1484 " irrelevant call/entry/return: %s",
1485 idx
, idx
+ 2, desc
.m_buffer
);
1488 path
->delete_event (idx
+ 2);
1489 path
->delete_event (idx
+ 1);
1490 path
->delete_event (idx
);
1496 /* Prune [..., call, return, ...] pairs
1497 (for -fanalyzer-verbosity=0). */
1498 if (idx
+ 1 < (signed)path
->num_events ()
1499 && path
->get_checker_event (idx
)->is_call_p ()
1500 && path
->get_checker_event (idx
+ 1)->is_return_p ())
1505 (path
->get_checker_event (idx
)->get_desc (false));
1506 log ("filtering events %i-%i:"
1507 " irrelevant call/return: %s",
1508 idx
, idx
+ 1, desc
.m_buffer
);
1511 path
->delete_event (idx
+ 1);
1512 path
->delete_event (idx
);
1525 /* Final pass of diagnostic_manager::prune_path.
1527 If all we're left with is in one function, then filter function entry
1531 diagnostic_manager::finish_pruning (checker_path
*path
) const
1533 if (!path
->interprocedural_p ())
1535 int idx
= path
->num_events () - 1;
1536 while (idx
>= 0 && idx
< (signed)path
->num_events ())
1538 checker_event
*base_event
= path
->get_checker_event (idx
);
1539 if (base_event
->m_kind
== EK_FUNCTION_ENTRY
)
1541 log ("filtering event %i:"
1542 " function entry for purely intraprocedural path", idx
);
1543 path
->delete_event (idx
);
1552 #endif /* #if ENABLE_ANALYZER */