Line data Source code
1 : /* Classes for saving, deduplicating, and emitting analyzer diagnostics.
2 : Copyright (C) 2019-2026 Free Software Foundation, Inc.
3 : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it
8 : under the terms of the GNU General Public License as published by
9 : the Free Software Foundation; either version 3, or (at your option)
10 : any later version.
11 :
12 : GCC is distributed in the hope that it will be useful, but
13 : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : General Public License for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "analyzer/common.h"
22 :
23 : #include "cfg.h"
24 : #include "gimple-pretty-print.h"
25 : #include "gimple-iterator.h"
26 : #include "inlining-iterator.h"
27 : #include "cgraph.h"
28 : #include "digraph.h"
29 : #include "gcc-rich-location.h"
30 : #include "diagnostics/sarif-sink.h"
31 :
32 : #include "analyzer/analyzer-logging.h"
33 : #include "analyzer/sm.h"
34 : #include "analyzer/pending-diagnostic.h"
35 : #include "analyzer/diagnostic-manager.h"
36 : #include "analyzer/call-string.h"
37 : #include "analyzer/program-point.h"
38 : #include "analyzer/store.h"
39 : #include "analyzer/region-model.h"
40 : #include "analyzer/constraint-manager.h"
41 : #include "analyzer/supergraph.h"
42 : #include "analyzer/program-state.h"
43 : #include "analyzer/exploded-graph.h"
44 : #include "analyzer/exploded-path.h"
45 : #include "analyzer/trimmed-graph.h"
46 : #include "analyzer/feasible-graph.h"
47 : #include "analyzer/checker-path.h"
48 : #include "analyzer/reachability.h"
49 :
50 : #if ENABLE_ANALYZER
51 :
52 : namespace ana {
53 :
54 : class feasible_worklist;
55 :
56 : // struct pending_location
57 :
58 755 : pending_location::pending_location ()
59 755 : : m_enode (nullptr),
60 755 : m_event_loc_info (UNKNOWN_LOCATION, NULL_TREE, 0)
61 : {
62 755 : }
63 :
64 7073 : pending_location::pending_location (exploded_node *enode)
65 7073 : : m_enode (enode),
66 7073 : m_event_loc_info (enode)
67 : {
68 7073 : }
69 :
70 3915 : pending_location::pending_location (exploded_node *enode,
71 : location_t loc)
72 3915 : : m_enode (enode),
73 3915 : m_event_loc_info (enode)
74 : {
75 3915 : m_event_loc_info.m_loc = loc;
76 3915 : }
77 :
78 : std::unique_ptr<json::object>
79 38 : pending_location::to_json () const
80 : {
81 38 : auto ploc_obj = std::make_unique<json::object> ();
82 :
83 38 : if (m_enode)
84 38 : ploc_obj->set_integer ("enode", m_enode->m_index);
85 : // TODO: also store m_event_loc_info
86 38 : return ploc_obj;
87 : }
88 :
89 : /* State for finding the shortest feasible exploded_path for a
90 : saved_diagnostic.
91 : This is shared between all diagnostics, so that we avoid repeating work. */
92 :
93 : class epath_finder
94 : {
95 : public:
96 1650 : epath_finder (const exploded_graph &eg)
97 1650 : : m_eg (eg),
98 1650 : m_sep (nullptr)
99 : {
100 : /* This is shared by all diagnostics, but only needed if
101 : !flag_analyzer_feasibility. */
102 1650 : if (!flag_analyzer_feasibility)
103 4 : m_sep = new shortest_exploded_paths (eg, eg.get_origin (),
104 4 : SPS_FROM_GIVEN_ORIGIN);
105 1650 : }
106 :
107 1654 : ~epath_finder () { delete m_sep; }
108 :
109 129594 : logger *get_logger () const { return m_eg.get_logger (); }
110 :
111 : std::unique_ptr<exploded_path>
112 : get_best_epath (const exploded_node *target_enode,
113 : const pending_diagnostic &pd,
114 : const char *desc, unsigned diag_idx,
115 : std::unique_ptr<feasibility_problem> *out_problem);
116 :
117 : private:
118 : DISABLE_COPY_AND_ASSIGN(epath_finder);
119 :
120 : std::unique_ptr<exploded_path>
121 : explore_feasible_paths (const exploded_node *target_enode,
122 : const pending_diagnostic &pd,
123 : const char *desc, unsigned diag_idx);
124 : bool
125 : process_worklist_item (feasible_worklist *worklist,
126 : const trimmed_graph &tg,
127 : feasible_graph *fg,
128 : const exploded_node *target_enode,
129 : const pending_diagnostic &pd,
130 : unsigned diag_idx,
131 : std::unique_ptr<exploded_path> *out_best_path) const;
132 : void dump_trimmed_graph (const exploded_node *target_enode,
133 : const char *desc, unsigned diag_idx,
134 : const trimmed_graph &tg,
135 : const shortest_paths<eg_traits, exploded_path> &sep);
136 : void dump_feasible_graph (const exploded_node *target_enode,
137 : const char *desc, unsigned diag_idx,
138 : const feasible_graph &fg);
139 : void dump_feasible_path (const exploded_node *target_enode,
140 : unsigned diag_idx,
141 : const feasible_graph &fg,
142 : const feasible_node &fnode) const;
143 :
144 : const exploded_graph &m_eg;
145 : shortest_exploded_paths *m_sep;
146 : };
147 :
148 : /* class epath_finder. */
149 :
150 : /* Get the "best" exploded_path for reaching TARGET_ENODE from the origin,
151 : returning ownership of it to the caller.
152 :
153 : Ideally we want to report the shortest feasible path.
154 : Return nullptr if we could not find a feasible path
155 : (when flag_analyzer_feasibility is true).
156 :
157 : If flag_analyzer_feasibility is false, then simply return the
158 : shortest path.
159 :
160 : Use DESC and DIAG_IDX when logging.
161 :
162 : Write any feasibility_problem to *OUT_PROBLEM. */
163 :
164 : std::unique_ptr<exploded_path>
165 6671 : epath_finder::get_best_epath (const exploded_node *target_enode,
166 : const pending_diagnostic &pd,
167 : const char *desc, unsigned diag_idx,
168 : std::unique_ptr<feasibility_problem> *out_problem)
169 : {
170 6671 : logger *logger = get_logger ();
171 6671 : LOG_SCOPE (logger);
172 :
173 6671 : unsigned snode_id = target_enode->get_supernode ()->m_id;
174 6671 : if (logger)
175 2 : logger->log ("considering %qs at EN: %i, SN: %i (sd: %i)",
176 2 : desc, target_enode->m_index, snode_id, diag_idx);
177 :
178 : /* State-merging means that not every path in the egraph corresponds
179 : to a feasible one w.r.t. states.
180 :
181 : We want to find the shortest feasible path from the origin to ENODE
182 : in the egraph. */
183 :
184 6671 : if (flag_analyzer_feasibility)
185 : {
186 : /* Attempt to find the shortest feasible path using feasible_graph. */
187 6667 : if (logger)
188 2 : logger->log ("trying to find shortest feasible path");
189 6667 : if (std::unique_ptr<exploded_path> epath
190 6667 : = explore_feasible_paths (target_enode, pd, desc, diag_idx))
191 : {
192 6447 : if (logger)
193 2 : logger->log ("accepting %qs at EN: %i, SN: %i (sd: %i)"
194 : " with feasible path (length: %i)",
195 2 : desc, target_enode->m_index, snode_id, diag_idx,
196 : epath->length ());
197 6447 : return epath;
198 : }
199 : else
200 : {
201 220 : if (logger)
202 0 : logger->log ("rejecting %qs at EN: %i, SN: %i (sd: %i)"
203 : " due to not finding feasible path",
204 0 : desc, target_enode->m_index, snode_id, diag_idx);
205 220 : return nullptr;
206 6667 : }
207 : }
208 : else
209 : {
210 : /* As a crude approximation to shortest feasible path, simply find
211 : the shortest path, and note whether it is feasible.
212 : There could be longer feasible paths within the egraph, so this
213 : approach would lead to diagnostics being falsely rejected
214 : (PR analyzer/96374). */
215 4 : if (logger)
216 0 : logger->log ("trying to find shortest path ignoring feasibility");
217 4 : gcc_assert (m_sep);
218 4 : auto epath
219 : = std::make_unique<exploded_path>
220 4 : (m_sep->get_shortest_path (target_enode));
221 4 : if (epath->feasible_p (logger, out_problem, m_eg.get_engine (), &m_eg))
222 : {
223 0 : if (logger)
224 0 : logger->log ("accepting %qs at EN: %i, SN: %i (sn: %i)"
225 : " with feasible path (length: %i)",
226 0 : desc, target_enode->m_index, snode_id, diag_idx,
227 : epath->length ());
228 : }
229 : else
230 : {
231 4 : if (logger)
232 0 : logger->log ("accepting %qs at EN: %i, SN: %i (sn: %i) (length: %i)"
233 : " despite infeasible path (due to %qs)",
234 0 : desc, target_enode->m_index, snode_id, diag_idx,
235 : epath->length (),
236 : "-fno-analyzer-feasibility");
237 : }
238 4 : return epath;
239 4 : }
240 6671 : }
241 :
242 : /* A class for managing the worklist of feasible_nodes in
243 : epath_finder::explore_feasible_paths, prioritizing them
244 : so that shorter paths appear earlier in the queue. */
245 :
246 13334 : class feasible_worklist
247 : {
248 : public:
249 6667 : feasible_worklist (const shortest_paths<eg_traits, exploded_path> &sep)
250 13334 : : m_queue (key_t (*this, nullptr)),
251 6667 : m_sep (sep)
252 : {
253 6667 : }
254 :
255 109585 : feasible_node *take_next () { return m_queue.extract_min (); }
256 :
257 111660 : void add_node (feasible_node *fnode)
258 : {
259 223320 : m_queue.insert (key_t (*this, fnode), fnode);
260 : }
261 :
262 : private:
263 : struct key_t
264 : {
265 118327 : key_t (const feasible_worklist &w, feasible_node *fnode)
266 6667 : : m_worklist (w), m_fnode (fnode)
267 : {}
268 :
269 60736 : bool operator< (const key_t &other) const
270 : {
271 60736 : return cmp (*this, other) < 0;
272 : }
273 :
274 14262 : bool operator== (const key_t &other) const
275 : {
276 14262 : return cmp (*this, other) == 0;
277 : }
278 :
279 14262 : bool operator> (const key_t &other) const
280 : {
281 14262 : return !(*this == other || *this < other);
282 : }
283 :
284 : private:
285 74998 : static int cmp (const key_t &ka, const key_t &kb)
286 : {
287 : /* Choose the node for which if the remaining path were feasible,
288 : it would be the shortest path (summing the length of the
289 : known-feasible path so far with that of the remaining
290 : possibly-feasible path). */
291 74998 : int ca = ka.m_worklist.get_estimated_cost (ka.m_fnode);
292 74998 : int cb = kb.m_worklist.get_estimated_cost (kb.m_fnode);
293 74998 : return ca - cb;
294 : }
295 :
296 : const feasible_worklist &m_worklist;
297 : feasible_node *m_fnode;
298 : };
299 :
300 : /* Get the estimated length of a path involving FNODE from
301 : the origin to the target enode.
302 : Sum the length of the known-feasible path so far with
303 : that of the remaining possibly-feasible path. */
304 :
305 149996 : int get_estimated_cost (const feasible_node *fnode) const
306 : {
307 149996 : unsigned length_so_far = fnode->get_path_length ();
308 149996 : int shortest_remaining_path
309 149996 : = m_sep.get_shortest_distance (fnode->get_inner_node ());
310 :
311 149996 : gcc_assert (shortest_remaining_path >= 0);
312 : /* This should be true since we're only exploring nodes within
313 : the trimmed graph (and we anticipate it being much smaller
314 : than this, and thus not overflowing the sum). */
315 149996 : gcc_assert (shortest_remaining_path < INT_MAX);
316 :
317 149996 : return length_so_far + shortest_remaining_path;
318 : }
319 :
320 : /* Priority queue, backed by a fibonacci_heap. */
321 : typedef fibonacci_heap<key_t, feasible_node> queue_t;
322 : queue_t m_queue;
323 : const shortest_paths<eg_traits, exploded_path> &m_sep;
324 : };
325 :
326 : /* When we're building the exploded graph we want to simplify
327 : overly-complicated symbolic values down to "UNKNOWN" to try to avoid
328 : state explosions and unbounded chains of exploration.
329 :
330 : However, when we're building the feasibility graph for a diagnostic
331 : (actually a tree), we don't want UNKNOWN values, as conditions on them
332 : are also unknown: we don't want to have a contradiction such as a path
333 : where (VAL != 0) and then (VAL == 0) along the same path.
334 :
335 : Hence this is an RAII class for temporarily disabling complexity-checking
336 : in the region_model_manager, for use within
337 : epath_finder::explore_feasible_paths.
338 :
339 : We also disable the creation of unknown_svalue instances during feasibility
340 : checking, instead creating unique svalues, to avoid paradoxes in paths. */
341 :
342 : class auto_checking_feasibility
343 : {
344 : public:
345 6667 : auto_checking_feasibility (region_model_manager *mgr) : m_mgr (mgr)
346 : {
347 6667 : m_mgr->begin_checking_feasibility ();
348 : }
349 6667 : ~auto_checking_feasibility ()
350 : {
351 6667 : m_mgr->end_checking_feasibility ();
352 : }
353 : private:
354 : region_model_manager *m_mgr;
355 : };
356 :
357 : /* Attempt to find the shortest feasible path from the origin to
358 : TARGET_ENODE by iteratively building a feasible_graph, in which
359 : every path to a feasible_node is feasible by construction.
360 :
361 : We effectively explore the tree of feasible paths in order of shortest
362 : path until we either find a feasible path to TARGET_ENODE, or hit
363 : a limit and give up.
364 :
365 : Preliminaries:
366 : - Find the shortest path from each node to the TARGET_ENODE (without
367 : checking feasibility), so that we can prioritize our worklist.
368 : - Construct a trimmed_graph: the subset of nodes/edges that
369 : are on a path that eventually reaches TARGET_ENODE. We will only need
370 : to consider these when considering the shortest feasible path.
371 :
372 : Build a feasible_graph, in which every path to a feasible_node
373 : is feasible by construction.
374 : We use a worklist to flatten the exploration into an iteration.
375 : Starting at the origin, find feasible out-edges within the trimmed graph.
376 : At each stage, choose the node for which if the remaining path were feasible,
377 : it would be the shortest path (summing the length of the known-feasible path
378 : so far with that of the remaining possibly-feasible path).
379 : This way, the first feasible path we find to TARGET_ENODE is the shortest.
380 : We start by trying the shortest possible path, but if that fails,
381 : we explore progressively longer paths, eventually trying iterations through
382 : loops. The exploration is captured in the feasible_graph, which can be
383 : dumped as a .dot file to visualize the exploration. The indices of the
384 : feasible_nodes show the order in which they were created.
385 :
386 : This is something of a brute-force approach, but the trimmed_graph
387 : hopefully keeps the complexity manageable.
388 :
389 : Terminate with failure when the number of infeasible edges exceeds
390 : a threshold (--param=analyzer-max-infeasible-edges=).
391 : This is guaranteed to eventually lead to terminatation, as
392 : we can't keep creating feasible nodes without eventually
393 : either reaching an infeasible edge, or reaching the
394 : TARGET_ENODE. Specifically, there can't be a cycle of
395 : feasible edges that doesn't reach the target_enode without
396 : an out-edge that either fails feasibility or gets closer
397 : to the TARGET_ENODE: on each iteration we are either:
398 : - effectively getting closer to the TARGET_ENODE (which can't
399 : continue forever without reaching the target), or
400 : - getting monotonically closer to the termination threshold. */
401 :
402 : std::unique_ptr<exploded_path>
403 6667 : epath_finder::explore_feasible_paths (const exploded_node *target_enode,
404 : const pending_diagnostic &pd,
405 : const char *desc, unsigned diag_idx)
406 : {
407 6667 : logger *logger = get_logger ();
408 6667 : LOG_SCOPE (logger);
409 :
410 6667 : region_model_manager *mgr = m_eg.get_engine ()->get_model_manager ();
411 :
412 : /* Determine the shortest path to TARGET_ENODE from each node in
413 : the exploded graph. */
414 6667 : shortest_paths<eg_traits, exploded_path> sep
415 6667 : (m_eg, target_enode, SPS_TO_GIVEN_TARGET);
416 :
417 : /* Construct a trimmed_graph: the subset of nodes/edges that
418 : are on a path that eventually reaches TARGET_ENODE.
419 : We only need to consider these when considering the shortest
420 : feasible path. */
421 6667 : trimmed_graph tg (m_eg, target_enode);
422 :
423 6667 : if (flag_dump_analyzer_feasibility)
424 4 : dump_trimmed_graph (target_enode, desc, diag_idx, tg, sep);
425 :
426 6667 : feasible_graph fg;
427 6667 : feasible_worklist worklist (sep);
428 :
429 : /* Populate the worklist with the origin node. */
430 6667 : {
431 6667 : feasibility_state init_state (mgr, m_eg.get_supergraph ());
432 6667 : feasible_node *origin = fg.add_node (m_eg.get_origin (), init_state, 0);
433 6667 : worklist.add_node (origin);
434 6667 : }
435 :
436 : /* Iteratively explore the tree of feasible paths in order of shortest
437 : path until we either find a feasible path to TARGET_ENODE, or hit
438 : a limit. */
439 :
440 : /* Set this if we find a feasible path to TARGET_ENODE. */
441 6667 : std::unique_ptr<exploded_path> best_path = nullptr;
442 :
443 6667 : {
444 6667 : auto_checking_feasibility sentinel (mgr);
445 :
446 109585 : while (process_worklist_item (&worklist, tg, &fg, target_enode,
447 : pd, diag_idx, &best_path))
448 : {
449 : /* Empty; the work is done within process_worklist_item. */
450 : }
451 6667 : }
452 :
453 6667 : if (logger)
454 : {
455 2 : logger->log ("tg for sd: %i:", diag_idx);
456 2 : logger->inc_indent ();
457 2 : tg.log_stats (logger);
458 2 : logger->dec_indent ();
459 :
460 2 : logger->log ("fg for sd: %i:", diag_idx);
461 2 : logger->inc_indent ();
462 2 : fg.log_stats (logger);
463 2 : logger->dec_indent ();
464 : }
465 :
466 : /* Dump the feasible_graph. */
467 6667 : if (flag_dump_analyzer_feasibility)
468 4 : dump_feasible_graph (target_enode, desc, diag_idx, fg);
469 :
470 6667 : return best_path;
471 13334 : }
472 :
473 : /* Process the next item in WORKLIST, potentially adding new items
474 : based on feasible out-edges, and extending FG accordingly.
475 : Use TG to ignore out-edges that don't lead to TARGET_ENODE.
476 : Return true if the worklist processing should continue.
477 : Return false if the processing of the worklist should stop
478 : (either due to reaching TARGET_ENODE, or hitting a limit).
479 : Write to *OUT_BEST_PATH if stopping due to finding a feasible path
480 : to TARGET_ENODE.
481 : Use PD to provide additional restrictions on feasibility of
482 : the final path in the feasible_graph before converting to
483 : an exploded_path. */
484 :
485 : bool
486 109585 : epath_finder::
487 : process_worklist_item (feasible_worklist *worklist,
488 : const trimmed_graph &tg,
489 : feasible_graph *fg,
490 : const exploded_node *target_enode,
491 : const pending_diagnostic &pd,
492 : unsigned diag_idx,
493 : std::unique_ptr<exploded_path> *out_best_path) const
494 : {
495 109585 : logger *logger = get_logger ();
496 :
497 109585 : feasible_node *fnode = worklist->take_next ();
498 109585 : if (!fnode)
499 : {
500 38 : if (logger)
501 0 : logger->log ("drained worklist for sd: %i"
502 : " without finding feasible path",
503 : diag_idx);
504 : return false;
505 : }
506 :
507 109547 : log_scope s (logger, "fg worklist item",
508 : "considering FN: %i (EN: %i) for sd: %i",
509 109547 : fnode->get_index (), fnode->get_inner_node ()->m_index,
510 109547 : diag_idx);
511 :
512 : /* Iterate through all out-edges from this item. */
513 109547 : unsigned i;
514 109547 : exploded_edge *succ_eedge;
515 380485 : FOR_EACH_VEC_ELT (fnode->get_inner_node ()->m_succs, i, succ_eedge)
516 : {
517 168020 : log_scope s (logger, "edge", "considering edge: EN:%i -> EN:%i",
518 168020 : succ_eedge->m_src->m_index,
519 168020 : succ_eedge->m_dest->m_index);
520 : /* Reject edges that aren't in the trimmed graph. */
521 168020 : if (!tg.contains_p (succ_eedge))
522 : {
523 54899 : if (logger)
524 1 : logger->log ("rejecting: not in trimmed graph");
525 54899 : continue;
526 : }
527 :
528 113121 : feasibility_state succ_state (fnode->get_state ());
529 113121 : std::unique_ptr<rejected_constraint> rc;
530 113121 : if (succ_state.maybe_update_for_edge (logger, succ_eedge, nullptr, &rc))
531 : {
532 111501 : gcc_assert (rc == nullptr);
533 111501 : feasible_node *succ_fnode
534 111501 : = fg->add_node (succ_eedge->m_dest,
535 : succ_state,
536 111501 : fnode->get_path_length () + 1);
537 111501 : if (logger)
538 14 : logger->log ("accepting as FN: %i", succ_fnode->get_index ());
539 111501 : fg->add_edge (new feasible_edge (fnode, succ_fnode, succ_eedge));
540 :
541 : /* Have we reached TARGET_ENODE? */
542 111501 : if (succ_fnode->get_inner_node () == target_enode)
543 : {
544 6508 : if (logger)
545 2 : logger->log ("success: got feasible path to EN: %i (sd: %i)"
546 : " (length: %i)",
547 2 : target_enode->m_index, diag_idx,
548 : succ_fnode->get_path_length ());
549 6508 : if (!pd.check_valid_fpath_p (*succ_fnode))
550 : {
551 61 : if (logger)
552 0 : logger->log ("rejecting feasible path due to"
553 : " pending_diagnostic");
554 : return false;
555 : }
556 6447 : *out_best_path = fg->make_epath (succ_fnode);
557 6447 : if (flag_dump_analyzer_feasibility)
558 4 : dump_feasible_path (target_enode, diag_idx, *fg, *succ_fnode);
559 :
560 : /* Success: stop the worklist iteration. */
561 : return false;
562 : }
563 : else
564 104993 : worklist->add_node (succ_fnode);
565 : }
566 : else
567 : {
568 1620 : if (logger)
569 0 : logger->log ("infeasible");
570 1620 : gcc_assert (rc);
571 1620 : fg->add_feasibility_problem (fnode,
572 : succ_eedge,
573 : std::move (rc));
574 :
575 : /* Give up if there have been too many infeasible edges. */
576 1620 : if (fg->get_num_infeasible ()
577 1620 : > (unsigned)param_analyzer_max_infeasible_edges)
578 : {
579 121 : if (logger)
580 0 : logger->log ("too many infeasible edges (%i); giving up",
581 : fg->get_num_infeasible ());
582 : return false;
583 : }
584 : }
585 168020 : }
586 :
587 : /* Continue the worklist iteration. */
588 : return true;
589 109547 : }
590 :
591 : /* Helper class for epath_finder::dump_trimmed_graph
592 : to dump extra per-node information.
593 : Use SEP to add the length of the shortest path from each
594 : node to the target node to each node's dump. */
595 :
596 : class dump_eg_with_shortest_path : public eg_traits::dump_args_t
597 : {
598 : public:
599 4 : dump_eg_with_shortest_path
600 : (const exploded_graph &eg,
601 : const shortest_paths<eg_traits, exploded_path> &sep)
602 : : dump_args_t (eg),
603 4 : m_sep (sep)
604 : {
605 : }
606 :
607 74 : void dump_extra_info (const exploded_node *enode,
608 : pretty_printer *pp) const final override
609 : {
610 74 : pp_printf (pp, "sp: %i", m_sep.get_shortest_path (enode).length ());
611 74 : pp_newline (pp);
612 74 : }
613 :
614 : private:
615 : const shortest_paths<eg_traits, exploded_path> &m_sep;
616 : };
617 :
618 : /* Dump TG to "BASE_NAME.DESC.DIAG_IDX.to-enN.tg.dot",
619 : annotating each node with the length of the shortest path
620 : from that node to TARGET_ENODE (using SEP). */
621 :
622 : void
623 4 : epath_finder::
624 : dump_trimmed_graph (const exploded_node *target_enode,
625 : const char *desc, unsigned diag_idx,
626 : const trimmed_graph &tg,
627 : const shortest_paths<eg_traits, exploded_path> &sep)
628 : {
629 4 : auto_timevar tv (TV_ANALYZER_DUMP);
630 4 : dump_eg_with_shortest_path inner_args (m_eg, sep);
631 4 : trimmed_graph::dump_args_t args (inner_args);
632 4 : pretty_printer pp;
633 4 : pp_printf (&pp, "%s.%s.%i.to-en%i.tg.dot",
634 4 : dump_base_name, desc, diag_idx, target_enode->m_index);
635 4 : char *filename = xstrdup (pp_formatted_text (&pp));
636 4 : tg.dump_dot (filename, nullptr, args);
637 4 : free (filename);
638 4 : }
639 :
640 : /* Dump FG to "BASE_NAME.DESC.DIAG_IDX.to-enN.fg.dot". */
641 :
642 : void
643 4 : epath_finder::dump_feasible_graph (const exploded_node *target_enode,
644 : const char *desc, unsigned diag_idx,
645 : const feasible_graph &fg)
646 : {
647 4 : auto_timevar tv (TV_ANALYZER_DUMP);
648 4 : exploded_graph::dump_args_t inner_args (m_eg);
649 4 : feasible_graph::dump_args_t args (inner_args);
650 4 : pretty_printer pp;
651 4 : pp_printf (&pp, "%s.%s.%i.to-en%i.fg.dot",
652 4 : dump_base_name, desc, diag_idx, target_enode->m_index);
653 4 : char *filename = xstrdup (pp_formatted_text (&pp));
654 4 : fg.dump_dot (filename, nullptr, args);
655 4 : free (filename);
656 4 : }
657 :
658 : /* Dump the path to FNODE to "BASE_NAME.DIAG_IDX.to-enN.fpath.txt". */
659 :
660 : void
661 4 : epath_finder::dump_feasible_path (const exploded_node *target_enode,
662 : unsigned diag_idx,
663 : const feasible_graph &fg,
664 : const feasible_node &fnode) const
665 : {
666 4 : auto_timevar tv (TV_ANALYZER_DUMP);
667 4 : pretty_printer pp;
668 4 : pp_printf (&pp, "%s.%i.to-en%i.fpath.txt",
669 4 : dump_base_name, diag_idx, target_enode->m_index);
670 4 : char *filename = xstrdup (pp_formatted_text (&pp));
671 4 : fg.dump_feasible_path (fnode, filename);
672 4 : free (filename);
673 4 : }
674 :
675 : /* class saved_diagnostic. */
676 :
677 : /* saved_diagnostic's ctor. */
678 :
679 6671 : saved_diagnostic::saved_diagnostic (const state_machine *sm,
680 : pending_location &&ploc,
681 : tree var,
682 : const svalue *sval,
683 : state_machine::state_t state,
684 : std::unique_ptr<pending_diagnostic> d,
685 : unsigned idx)
686 6671 : : m_sm (sm),
687 6671 : m_ploc (std::move (ploc)),
688 6671 : m_var (var), m_sval (sval), m_state (state),
689 6671 : m_d (std::move (d)), m_trailing_eedge (nullptr),
690 6671 : m_idx (idx),
691 6671 : m_best_epath (nullptr), m_problem (nullptr),
692 6671 : m_notes ()
693 : {
694 : /* We must have an enode in order to be able to look for paths
695 : through the exploded_graph to this diagnostic. */
696 6671 : gcc_assert (m_ploc.m_enode);
697 6671 : }
698 :
699 : const supernode *
700 159218 : saved_diagnostic::get_supernode () const
701 : {
702 159218 : return m_ploc.m_enode->get_supernode ();
703 : }
704 :
705 : bool
706 53108 : saved_diagnostic::operator== (const saved_diagnostic &other) const
707 : {
708 55548 : if (m_notes.length () != other.m_notes.length ())
709 : return false;
710 52698 : for (unsigned i = 0; i < m_notes.length (); i++)
711 892 : if (!m_notes[i]->equal_p (*other.m_notes[i]))
712 : return false;
713 :
714 : // Don't deduplicate dump_path_diagnostic instances
715 51806 : if (!strcmp (m_d->get_kind (), "dump_path_diagnostic"))
716 1560 : return this == &other;
717 :
718 50246 : return (m_sm == other.m_sm
719 : /* We don't compare m_enode. */
720 43666 : && get_supernode () == other.get_supernode ()
721 9188 : && (m_ploc.m_event_loc_info.m_loc
722 9188 : == other.m_ploc.m_event_loc_info.m_loc)
723 7161 : && pending_diagnostic::same_tree_p (m_var, other.m_var)
724 6507 : && m_state == other.m_state
725 6463 : && m_d->equal_p (*other.m_d)
726 56437 : && m_trailing_eedge == other.m_trailing_eedge);
727 : }
728 :
729 : /* Add PN to this diagnostic, taking ownership of it. */
730 :
731 : void
732 214 : saved_diagnostic::add_note (std::unique_ptr<pending_note> pn)
733 : {
734 214 : gcc_assert (pn);
735 214 : m_notes.safe_push (pn.release ());
736 214 : }
737 :
738 : /* Add EVENT to this diagnostic. */
739 :
740 : void
741 179 : saved_diagnostic::add_event (std::unique_ptr<checker_event> event)
742 : {
743 179 : gcc_assert (event);
744 179 : m_saved_events.safe_push (event.release ());
745 179 : }
746 :
747 : /* Return a new json::object of the form
748 : {"sm": optional str,
749 : "ploc": {},
750 : "sval": optional str,
751 : "state": optional str,
752 : "path_length": optional int,
753 : "pending_diagnostic": str,
754 : "idx": int}. */
755 :
756 : std::unique_ptr<json::object>
757 1 : saved_diagnostic::to_json () const
758 : {
759 1 : auto sd_obj = std::make_unique<json::object> ();
760 :
761 1 : if (m_sm)
762 1 : sd_obj->set_string ("sm", m_sm->get_name ());
763 1 : sd_obj->set ("ploc", m_ploc.to_json ());
764 1 : if (m_sval)
765 1 : sd_obj->set ("sval", m_sval->to_json ());
766 1 : if (m_state)
767 1 : sd_obj->set ("state", m_state->to_json ());
768 1 : if (m_best_epath)
769 1 : sd_obj->set_integer ("path_length", get_epath_length ());
770 1 : sd_obj->set<json::object> ("pending_diagnostic", m_d->to_json ());
771 1 : sd_obj->set_integer ("idx", m_idx);
772 1 : if (m_problem)
773 0 : sd_obj->set<json::object> ("feasibility_problem", m_problem->to_json ());
774 1 : if (!m_duplicates.is_empty ())
775 : {
776 0 : auto arr = std::make_unique<json::array> ();
777 :
778 0 : for (auto &dup : m_duplicates)
779 0 : arr->append (std::make_unique <json::integer_number> (dup->m_idx));
780 :
781 0 : sd_obj->set<json::array> ("duplicates", std::move (arr));
782 0 : }
783 :
784 1 : return sd_obj;
785 : }
786 :
787 : /* Dump this to PP in a form suitable for use as an id in .dot output. */
788 :
789 : void
790 16 : saved_diagnostic::dump_dot_id (pretty_printer *pp) const
791 : {
792 16 : pp_printf (pp, "sd_%i", m_idx);
793 16 : }
794 :
795 : /* Dump this to PP in a form suitable for use as a node in .dot output. */
796 :
797 : void
798 8 : saved_diagnostic::dump_as_dot_node (pretty_printer *pp) const
799 : {
800 8 : dump_dot_id (pp);
801 8 : pp_printf (pp,
802 : " [shape=none,margin=0,style=filled,fillcolor=\"red\",label=\"");
803 8 : pp_write_text_to_stream (pp);
804 :
805 : /* Node label. */
806 8 : pp_printf (pp, "DIAGNOSTIC: %s (sd: %i)\n",
807 8 : m_d->get_kind (), m_idx);
808 8 : if (m_sm)
809 : {
810 8 : pp_printf (pp, "sm: %s", m_sm->get_name ());
811 8 : if (m_state)
812 : {
813 8 : pp_printf (pp, "; state: ");
814 8 : m_state->dump_to_pp (pp);
815 : }
816 8 : pp_newline (pp);
817 : }
818 8 : if (m_var)
819 8 : pp_printf (pp, "var: %qE\n", m_var);
820 8 : if (m_sval)
821 : {
822 8 : pp_string (pp, "sval: ");
823 8 : m_sval->symbolic::node::dump_to_pp (pp);
824 8 : pp_newline (pp);
825 : }
826 8 : if (m_best_epath)
827 0 : pp_printf (pp, "path length: %i\n", get_epath_length ());
828 :
829 8 : pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
830 8 : pp_string (pp, "\"];\n\n");
831 :
832 : /* Show links to duplicates. */
833 8 : for (auto iter : m_duplicates)
834 : {
835 0 : dump_dot_id (pp);
836 0 : pp_string (pp, " -> ");
837 0 : iter->dump_dot_id (pp);
838 0 : pp_string (pp, " [style=\"dotted\" arrowhead=\"none\"];");
839 0 : pp_newline (pp);
840 : }
841 8 : }
842 :
843 : /* Use PF to find the best exploded_path for this saved_diagnostic, if any,
844 : and store it in m_best_epath.
845 : Return true if a best path was found. */
846 :
847 : bool
848 6671 : saved_diagnostic::calc_best_epath (epath_finder *pf)
849 : {
850 6671 : logger *logger = pf->get_logger ();
851 6671 : LOG_SCOPE (logger);
852 6671 : m_problem = nullptr;
853 :
854 6671 : m_best_epath = pf->get_best_epath (m_ploc.m_enode,
855 6671 : *m_d, m_d->get_kind (), m_idx,
856 6671 : &m_problem);
857 :
858 : /* Handle failure to find a feasible path. */
859 6671 : if (m_best_epath == nullptr)
860 220 : return false;
861 :
862 : gcc_assert (m_best_epath);
863 :
864 : return true;
865 6671 : }
866 :
867 : unsigned
868 6607 : saved_diagnostic::get_epath_length () const
869 : {
870 6607 : gcc_assert (m_best_epath);
871 6607 : return m_best_epath->length ();
872 : }
873 :
874 : /* Record that OTHER (and its duplicates) are duplicates
875 : of this saved_diagnostic. */
876 :
877 : void
878 1999 : saved_diagnostic::add_duplicate (saved_diagnostic *other)
879 : {
880 1999 : gcc_assert (other);
881 1999 : m_duplicates.reserve (m_duplicates.length ()
882 2096 : + other->m_duplicates.length ()
883 : + 1);
884 1999 : m_duplicates.splice (other->m_duplicates);
885 1999 : other->m_duplicates.truncate (0);
886 1999 : m_duplicates.safe_push (other);
887 1999 : }
888 :
889 : /* Walk up the sedges of each of the two paths.
890 : If the two sequences of sedges do not perfectly correspond,
891 : then paths are incompatible.
892 : If there is at least one sedge that either cannot be paired up
893 : or its counterpart is not equal, then the paths are incompatible
894 : and this function returns FALSE.
895 : Otherwise return TRUE.
896 :
897 : Incompatible paths:
898 :
899 : <cond Y>
900 : / \
901 : / \
902 : true false
903 : | |
904 : ... ...
905 : | |
906 : ... stmt x
907 : |
908 : stmt x
909 :
910 : Both LHS_PATH and RHS_PATH final enodes should be
911 : over the same gimple statement. */
912 :
913 : static bool
914 98 : compatible_epath_p (const exploded_path *lhs_path,
915 : const exploded_path *rhs_path)
916 : {
917 98 : gcc_assert (lhs_path);
918 98 : gcc_assert (rhs_path);
919 98 : gcc_assert (rhs_path->length () > 0);
920 98 : gcc_assert (rhs_path->length () > 0);
921 98 : int lhs_eedge_idx = lhs_path->length () - 1;
922 98 : int rhs_eedge_idx = rhs_path->length () - 1;
923 98 : const exploded_edge *lhs_eedge;
924 98 : const exploded_edge *rhs_eedge;
925 :
926 2209 : while (lhs_eedge_idx >= 0 && rhs_eedge_idx >= 0)
927 : {
928 2406 : while (lhs_eedge_idx >= 0)
929 : {
930 : /* Find LHS_PATH's next superedge. */
931 2340 : lhs_eedge = lhs_path->m_elements[lhs_eedge_idx].m_eedge;
932 2340 : if (lhs_eedge->m_sedge)
933 : break;
934 : else
935 197 : lhs_eedge_idx--;
936 : }
937 2406 : while (rhs_eedge_idx >= 0)
938 : {
939 : /* Find RHS_PATH's next superedge. */
940 2340 : rhs_eedge = rhs_path->m_elements[rhs_eedge_idx].m_eedge;
941 2340 : if (rhs_eedge->m_sedge)
942 : break;
943 : else
944 197 : rhs_eedge_idx--;
945 : }
946 :
947 2209 : if (lhs_eedge->m_sedge && rhs_eedge->m_sedge)
948 : {
949 2143 : if (lhs_eedge->m_sedge != rhs_eedge->m_sedge)
950 : /* Both superedges do not match.
951 : Superedges are not dependent on the exploded path, so even
952 : different epaths will have similar sedges if they follow
953 : the same outcome of a conditional node. */
954 : return false;
955 :
956 2111 : lhs_eedge_idx--;
957 2111 : rhs_eedge_idx--;
958 2111 : continue;
959 : }
960 66 : else if (lhs_eedge->m_sedge == nullptr && rhs_eedge->m_sedge == nullptr)
961 : /* Both paths were drained up entirely.
962 : No discriminant was found. */
963 66 : return true;
964 :
965 : /* A superedge was found for only one of the two paths. */
966 : return false;
967 : }
968 :
969 : /* A superedge was found for only one of the two paths. */
970 0 : if (lhs_eedge_idx >= 0 || rhs_eedge_idx >= 0)
971 0 : return false;
972 :
973 : /* Both paths were drained up entirely.
974 : No discriminant was found. */
975 : return true;
976 : }
977 :
978 :
979 : /* Return true if this diagnostic supercedes OTHER, and that OTHER should
980 : therefore not be emitted. */
981 :
982 : bool
983 31555 : saved_diagnostic::supercedes_p (const saved_diagnostic &other) const
984 : {
985 31555 : if (get_supernode () != other.get_supernode ())
986 : return false;
987 :
988 : /* return early if OTHER won't be superseded anyway. */
989 6298 : if (!m_d->supercedes_p (*other.m_d))
990 : return false;
991 :
992 : /* If the two saved_diagnostics' path are not compatible
993 : then they cannot supersede one another. */
994 98 : return compatible_epath_p (m_best_epath.get (), other.m_best_epath.get ());
995 : }
996 :
997 : /* Move any saved checker_events from this saved_diagnostic to
998 : the end of DST_PATH. */
999 :
1000 : void
1001 4386 : saved_diagnostic::add_any_saved_events (checker_path &dst_path)
1002 : {
1003 4887 : for (auto &event : m_saved_events)
1004 : {
1005 167 : dst_path.add_event (std::unique_ptr<checker_event> (event));
1006 167 : event = nullptr;
1007 : }
1008 4386 : }
1009 :
1010 : /* Emit any pending notes owned by this diagnostic. */
1011 :
1012 : void
1013 4327 : saved_diagnostic::emit_any_notes () const
1014 : {
1015 4905 : for (auto pn : m_notes)
1016 198 : pn->emit ();
1017 4327 : }
1018 :
1019 : /* For SARIF output, add additional properties to the "result" object
1020 : for this diagnostic.
1021 : This extra data is intended for use when debugging the analyzer. */
1022 :
1023 : void
1024 37 : saved_diagnostic::
1025 : maybe_add_sarif_properties (diagnostics::sarif_object &result_obj) const
1026 : {
1027 37 : auto &props = result_obj.get_or_create_properties ();
1028 : #define PROPERTY_PREFIX "gcc/analyzer/saved_diagnostic/"
1029 37 : if (m_sm)
1030 17 : props.set_string (PROPERTY_PREFIX "sm", m_sm->get_name ());
1031 37 : props.set (PROPERTY_PREFIX "ploc", m_ploc.to_json ());
1032 37 : if (m_var)
1033 17 : props.set (PROPERTY_PREFIX "var", tree_to_json (m_var));
1034 37 : if (m_sval)
1035 17 : props.set (PROPERTY_PREFIX "sval", m_sval->to_json ());
1036 37 : if (m_state)
1037 17 : props.set (PROPERTY_PREFIX "state", m_state->to_json ());
1038 : // TODO: m_best_epath
1039 37 : props.set_integer (PROPERTY_PREFIX "idx", m_idx);
1040 37 : if (m_duplicates.length () > 0)
1041 : {
1042 4 : auto duplicates_arr = std::make_unique<json::array> ();
1043 16 : for (auto iter : m_duplicates)
1044 : {
1045 4 : auto sd_obj = std::make_unique<diagnostics::sarif_object> ();
1046 4 : iter->maybe_add_sarif_properties (*sd_obj);
1047 4 : duplicates_arr->append (std::move (sd_obj));
1048 4 : }
1049 4 : props.set<json::array> (PROPERTY_PREFIX "duplicates",
1050 : std::move (duplicates_arr));
1051 4 : }
1052 : #undef PROPERTY_PREFIX
1053 :
1054 : #define PROPERTY_PREFIX "gcc/analyzer/pending_diagnostic/"
1055 37 : props.set_string (PROPERTY_PREFIX "kind", m_d->get_kind ());
1056 : #undef PROPERTY_PREFIX
1057 :
1058 : /* Potentially add pending_diagnostic-specific properties. */
1059 37 : m_d->maybe_add_sarif_properties (result_obj);
1060 37 : }
1061 :
1062 : /* State for building a checker_path from a particular exploded_path.
1063 : In particular, this precomputes reachability information: the set of
1064 : source enodes for which a path be found to the diagnostic enode. */
1065 :
1066 4386 : class path_builder
1067 : {
1068 : public:
1069 4386 : path_builder (const exploded_graph &eg,
1070 : const exploded_path &epath,
1071 : const feasibility_problem *problem,
1072 : const saved_diagnostic &sd)
1073 4386 : : m_eg (eg),
1074 4386 : m_diag_enode (epath.get_final_enode ()),
1075 4386 : m_sd (sd),
1076 4386 : m_reachability (eg, m_diag_enode),
1077 4386 : m_feasibility_problem (problem)
1078 4386 : {}
1079 :
1080 0 : const exploded_node *get_diag_node () const { return m_diag_enode; }
1081 :
1082 59852 : pending_diagnostic *get_pending_diagnostic () const
1083 : {
1084 255 : return m_sd.m_d.get ();
1085 : }
1086 :
1087 33992 : bool reachable_from_p (const exploded_node *src_enode) const
1088 : {
1089 67984 : return m_reachability.reachable_from_p (src_enode);
1090 : }
1091 :
1092 88054 : const extrinsic_state &get_ext_state () const { return m_eg.get_ext_state (); }
1093 :
1094 42347 : const feasibility_problem *get_feasibility_problem () const
1095 : {
1096 42347 : return m_feasibility_problem;
1097 : }
1098 :
1099 5104 : const state_machine *get_sm () const { return m_sd.m_sm; }
1100 :
1101 : const supergraph &
1102 44025 : get_supergraph () const { return m_eg.get_supergraph (); }
1103 :
1104 : private:
1105 : typedef reachability<eg_traits> enode_reachability;
1106 :
1107 : const exploded_graph &m_eg;
1108 :
1109 : /* The enode where the diagnostic occurs. */
1110 : const exploded_node *m_diag_enode;
1111 :
1112 : const saved_diagnostic &m_sd;
1113 :
1114 : /* Precompute all enodes from which the diagnostic is reachable. */
1115 : enode_reachability m_reachability;
1116 :
1117 : const feasibility_problem *m_feasibility_problem;
1118 : };
1119 :
1120 : /* class diagnostic_manager. */
1121 :
1122 : /* diagnostic_manager's ctor. */
1123 :
1124 3573 : diagnostic_manager::diagnostic_manager (logger *logger, engine *eng,
1125 : int verbosity)
1126 3573 : : log_user (logger), m_eng (eng), m_verbosity (verbosity),
1127 3573 : m_num_disabled_diagnostics (0)
1128 : {
1129 3573 : }
1130 :
1131 : /* Queue pending_diagnostic D at ENODE for later emission.
1132 : Return true/false signifying if the diagnostic was actually added. */
1133 :
1134 : bool
1135 10822 : diagnostic_manager::add_diagnostic (const state_machine *sm,
1136 : pending_location &&ploc,
1137 : tree var,
1138 : const svalue *sval,
1139 : state_machine::state_t state,
1140 : std::unique_ptr<pending_diagnostic> d)
1141 : {
1142 10822 : LOG_FUNC (get_logger ());
1143 :
1144 : /* We must have an enode in order to be able to look for paths
1145 : through the exploded_graph to the diagnostic. */
1146 10822 : gcc_assert (ploc.m_enode);
1147 :
1148 : /* If this warning is ultimately going to be rejected by a -Wno-analyzer-*
1149 : flag, reject it now. */
1150 10822 : {
1151 10822 : location_t loc = ploc.m_event_loc_info.m_loc;
1152 10822 : loc = d->fixup_location (loc, true);
1153 10822 : int option = d->get_controlling_option ();
1154 10822 : if (!warning_enabled_at (loc, option))
1155 : {
1156 4151 : if (get_logger ())
1157 0 : get_logger ()->log ("rejecting disabled warning %qs",
1158 0 : d->get_kind ());
1159 4151 : m_num_disabled_diagnostics++;
1160 4151 : return false;
1161 : }
1162 : }
1163 :
1164 6671 : saved_diagnostic *sd
1165 : = new saved_diagnostic (sm,
1166 : std::move (ploc),
1167 : var,
1168 : sval,
1169 : state,
1170 : std::move (d),
1171 11692 : m_saved_diagnostics.length ());
1172 6671 : m_saved_diagnostics.safe_push (sd);
1173 6671 : sd->m_ploc.m_enode->add_diagnostic (sd);
1174 6671 : if (get_logger ())
1175 4 : log ("adding saved diagnostic %i at SN %i to EN %i: %qs",
1176 : sd->get_index (),
1177 2 : sd->get_supernode ()->m_id,
1178 2 : sd->m_ploc.m_enode->m_index,
1179 2 : sd->m_d->get_kind ());
1180 : return true;
1181 10822 : }
1182 :
1183 : /* Queue pending_diagnostic D at ENODE for later emission.
1184 : Return true/false signifying if the diagnostic was actually added.
1185 : Take ownership of D (or delete it). */
1186 :
1187 : bool
1188 3945 : diagnostic_manager::add_diagnostic (pending_location &&ploc,
1189 : std::unique_ptr<pending_diagnostic> d)
1190 : {
1191 3945 : gcc_assert (ploc.m_enode);
1192 3945 : return add_diagnostic (nullptr, std::move (ploc),
1193 3945 : NULL_TREE, nullptr, 0, std::move (d));
1194 : }
1195 :
1196 : /* Add PN to the most recent saved_diagnostic. */
1197 :
1198 : void
1199 214 : diagnostic_manager::add_note (std::unique_ptr<pending_note> pn)
1200 : {
1201 214 : LOG_FUNC (get_logger ());
1202 214 : gcc_assert (pn);
1203 :
1204 : /* Get most recent saved_diagnostic. */
1205 214 : gcc_assert (m_saved_diagnostics.length () > 0);
1206 214 : saved_diagnostic *sd = m_saved_diagnostics[m_saved_diagnostics.length () - 1];
1207 214 : sd->add_note (std::move (pn));
1208 214 : }
1209 :
1210 : /* Add EVENT to the most recent saved_diagnostic. */
1211 :
1212 : void
1213 179 : diagnostic_manager::add_event (std::unique_ptr<checker_event> event)
1214 : {
1215 179 : LOG_FUNC (get_logger ());
1216 179 : gcc_assert (event);
1217 :
1218 : /* Get most recent saved_diagnostic. */
1219 179 : gcc_assert (m_saved_diagnostics.length () > 0);
1220 179 : saved_diagnostic *sd = m_saved_diagnostics[m_saved_diagnostics.length () - 1];
1221 179 : sd->add_event (std::move (event));
1222 179 : }
1223 :
1224 : /* Return a new json::object of the form
1225 : {"diagnostics" : [obj for saved_diagnostic]}. */
1226 :
1227 : std::unique_ptr<json::object>
1228 1 : diagnostic_manager::to_json () const
1229 : {
1230 1 : auto dm_obj = std::make_unique<json::object> ();
1231 :
1232 1 : {
1233 1 : auto sd_arr = std::make_unique<json::array> ();
1234 1 : int i;
1235 1 : saved_diagnostic *sd;
1236 3 : FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
1237 1 : sd_arr->append (sd->to_json ());
1238 1 : dm_obj->set ("diagnostics", std::move (sd_arr));
1239 1 : }
1240 :
1241 1 : return dm_obj;
1242 : }
1243 :
1244 : /* A class for identifying sets of duplicated pending_diagnostic.
1245 :
1246 : We want to find the simplest saved_diagnostic amongst those that share a
1247 : dedupe_key. */
1248 :
1249 : class dedupe_key
1250 : {
1251 : public:
1252 6451 : dedupe_key (const saved_diagnostic &sd)
1253 6451 : : m_sd (sd),
1254 6451 : m_loc (sd.m_ploc.m_event_loc_info.m_loc)
1255 : {
1256 : }
1257 :
1258 68389 : hashval_t hash () const
1259 : {
1260 68389 : inchash::hash hstate;
1261 : // TODO: m_sd
1262 68389 : return hstate.end ();
1263 : }
1264 53108 : bool operator== (const dedupe_key &other) const
1265 : {
1266 53108 : return (m_sd == other.m_sd
1267 53108 : && m_loc == other.m_loc);
1268 : }
1269 :
1270 33322 : location_t get_location () const { return m_loc; }
1271 :
1272 : /* A qsort comparator for use by dedupe_winners::emit_best
1273 : to sort them into location_t order. */
1274 :
1275 : static int
1276 33322 : comparator (const void *p1, const void *p2)
1277 : {
1278 33322 : const dedupe_key *pk1 = *(const dedupe_key * const *)p1;
1279 33322 : const dedupe_key *pk2 = *(const dedupe_key * const *)p2;
1280 :
1281 33322 : location_t loc1 = pk1->get_location ();
1282 33322 : location_t loc2 = pk2->get_location ();
1283 :
1284 33322 : if (int cmp = linemap_compare_locations (line_table, loc2, loc1))
1285 : return cmp;
1286 1302 : if (int cmp = ((int)pk1->m_sd.get_epath_length ()
1287 1302 : - (int)pk2->m_sd.get_epath_length ()))
1288 : return cmp;
1289 882 : if (int cmp = strcmp (pk1->m_sd.m_d->get_kind (),
1290 882 : pk2->m_sd.m_d->get_kind ()))
1291 : return cmp;
1292 : return 0;
1293 : }
1294 :
1295 : const saved_diagnostic &m_sd;
1296 : location_t m_loc;
1297 : };
1298 :
1299 : /* Traits for use by dedupe_winners. */
1300 :
1301 : class dedupe_hash_map_traits
1302 : {
1303 : public:
1304 : typedef const dedupe_key *key_type;
1305 : typedef saved_diagnostic *value_type;
1306 : typedef saved_diagnostic *compare_type;
1307 :
1308 68389 : static inline hashval_t hash (const key_type &v)
1309 : {
1310 68389 : return v->hash ();
1311 : }
1312 53108 : static inline bool equal_keys (const key_type &k1, const key_type &k2)
1313 : {
1314 53108 : return *k1 == *k2;
1315 : }
1316 : template <typename T>
1317 : static inline void remove (T &)
1318 : {
1319 : // TODO
1320 : }
1321 : template <typename T>
1322 66 : static inline void mark_deleted (T &entry)
1323 : {
1324 66 : entry.m_key = reinterpret_cast<key_type> (1);
1325 : }
1326 : template <typename T>
1327 0 : static inline void mark_empty (T &entry)
1328 : {
1329 0 : entry.m_key = nullptr;
1330 : }
1331 : template <typename T>
1332 159640 : static inline bool is_deleted (const T &entry)
1333 : {
1334 159640 : return entry.m_key == reinterpret_cast<key_type> (1);
1335 : }
1336 : template <typename T>
1337 571986 : static inline bool is_empty (const T &entry)
1338 : {
1339 571986 : return entry.m_key == nullptr;
1340 : }
1341 : static const bool empty_zero_p = true;
1342 : };
1343 :
1344 : /* A class for deduplicating diagnostics and finding (and emitting) the
1345 : best saved_diagnostic within each partition. */
1346 :
1347 : class dedupe_winners
1348 : {
1349 : public:
1350 1650 : ~dedupe_winners ()
1351 : {
1352 : /* Delete all keys, but not the saved_diagnostics. */
1353 6036 : for (map_t::iterator iter = m_map.begin ();
1354 6036 : iter != m_map.end ();
1355 4386 : ++iter)
1356 4386 : delete (*iter).first;
1357 1650 : }
1358 :
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. */
1362 :
1363 6671 : void add (logger *logger,
1364 : epath_finder *pf,
1365 : saved_diagnostic *sd)
1366 : {
1367 : /* Determine best epath for SD. */
1368 6671 : if (!sd->calc_best_epath (pf))
1369 220 : return;
1370 :
1371 6451 : const exploded_path *epath = sd->get_best_epath ();
1372 6451 : gcc_assert (epath);
1373 :
1374 : /* Now we have an exploded path, use it for pending_locations that are
1375 : affected by such things, and for deduplication. */
1376 6451 : if (sd->m_ploc.m_fixer_for_epath)
1377 1070 : sd->m_ploc.m_fixer_for_epath->fixup_for_epath (*epath, sd->m_ploc);
1378 :
1379 6451 : dedupe_key *key = new dedupe_key (*sd);
1380 6451 : if (saved_diagnostic **slot = m_map.get (key))
1381 : {
1382 1999 : if (logger)
1383 0 : logger->log ("already have this dedupe_key");
1384 :
1385 1999 : saved_diagnostic *cur_best_sd = *slot;
1386 :
1387 1999 : if (sd->get_epath_length () < cur_best_sd->get_epath_length ())
1388 : {
1389 : /* We've got a shorter path for the key; replace
1390 : the current candidate, marking it as a duplicate of SD. */
1391 144 : if (logger)
1392 0 : logger->log ("length %i is better than existing length %i;"
1393 : " taking over this dedupe_key",
1394 : sd->get_epath_length (),
1395 : cur_best_sd->get_epath_length ());
1396 144 : sd->add_duplicate (cur_best_sd);
1397 144 : *slot = sd;
1398 : }
1399 : else
1400 : /* We haven't beaten the current best candidate; add SD
1401 : as a duplicate of it. */
1402 : {
1403 1855 : if (logger)
1404 0 : logger->log ("length %i isn't better than existing length %i;"
1405 : " dropping this candidate",
1406 : sd->get_epath_length (),
1407 : cur_best_sd->get_epath_length ());
1408 1855 : cur_best_sd->add_duplicate (sd);
1409 : }
1410 1999 : delete key;
1411 : }
1412 : else
1413 : {
1414 : /* This is the first candidate for this key. */
1415 4452 : m_map.put (key, sd);
1416 4452 : if (logger)
1417 2 : logger->log ("first candidate for this dedupe_key");
1418 : }
1419 : }
1420 :
1421 : /* Handle interactions between the dedupe winners, so that some
1422 : diagnostics can supercede others (of different kinds).
1423 :
1424 : We want use-after-free to supercede use-of-uninitialized-value,
1425 : so that if we have these at the same stmt, we don't emit
1426 : a use-of-uninitialized, just the use-after-free. */
1427 :
1428 1650 : void handle_interactions (diagnostic_manager *dm)
1429 : {
1430 1650 : LOG_SCOPE (dm->get_logger ());
1431 1650 : auto_vec<const dedupe_key *> superceded;
1432 6102 : for (auto outer : m_map)
1433 : {
1434 4452 : const saved_diagnostic *outer_sd = outer.second;
1435 40393 : for (auto inner : m_map)
1436 : {
1437 31555 : const saved_diagnostic *inner_sd = inner.second;
1438 31555 : if (inner_sd->supercedes_p (*outer_sd))
1439 : {
1440 66 : superceded.safe_push (outer.first);
1441 66 : if (dm->get_logger ())
1442 0 : dm->log ("sd[%i] \"%s\" superceded by sd[%i] \"%s\"",
1443 0 : outer_sd->get_index (), outer_sd->m_d->get_kind (),
1444 0 : inner_sd->get_index (), inner_sd->m_d->get_kind ());
1445 : break;
1446 : }
1447 : }
1448 : }
1449 1826 : for (auto iter : superceded)
1450 66 : m_map.remove (iter);
1451 1650 : }
1452 :
1453 : /* Emit the simplest diagnostic within each set. */
1454 :
1455 1650 : void emit_best (diagnostic_manager *dm,
1456 : const exploded_graph &eg)
1457 : {
1458 1650 : LOG_SCOPE (dm->get_logger ());
1459 :
1460 : /* Get keys into a vec for sorting. */
1461 1650 : auto_vec<const dedupe_key *> keys (m_map.elements ());
1462 1650 : for (map_t::iterator iter = m_map.begin ();
1463 6036 : iter != m_map.end ();
1464 4386 : ++iter)
1465 4386 : keys.quick_push ((*iter).first);
1466 :
1467 3252 : dm->log ("# keys after de-duplication: %i", keys.length ());
1468 :
1469 : /* Sort into a good emission order. */
1470 1650 : keys.qsort (dedupe_key::comparator);
1471 :
1472 : /* Emit the best saved_diagnostics for each key. */
1473 1650 : int i;
1474 1650 : const dedupe_key *key;
1475 7638 : FOR_EACH_VEC_ELT (keys, i, key)
1476 : {
1477 4386 : saved_diagnostic **slot = m_map.get (key);
1478 4386 : gcc_assert (*slot);
1479 4386 : saved_diagnostic *sd = *slot;
1480 4386 : dm->emit_saved_diagnostic (eg, *sd);
1481 : }
1482 1650 : }
1483 :
1484 : private:
1485 : /* This maps from each dedupe_key to a current best saved_diagnostic. */
1486 :
1487 : typedef hash_map<const dedupe_key *, saved_diagnostic *,
1488 : dedupe_hash_map_traits> map_t;
1489 : map_t m_map;
1490 : };
1491 :
1492 : /* Emit all saved diagnostics. */
1493 :
1494 : void
1495 3573 : diagnostic_manager::emit_saved_diagnostics (const exploded_graph &eg)
1496 : {
1497 3573 : LOG_SCOPE (get_logger ());
1498 3573 : auto_timevar tv (TV_ANALYZER_DIAGNOSTICS);
1499 5223 : log ("# saved diagnostics: %i", m_saved_diagnostics.length ());
1500 3573 : log ("# disabled diagnostics: %i", m_num_disabled_diagnostics);
1501 3573 : if (get_logger ())
1502 : {
1503 : unsigned i;
1504 : saved_diagnostic *sd;
1505 7 : FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
1506 2 : log ("[%i] sd: %qs at EN: %i, SN: %i",
1507 2 : i, sd->m_d->get_kind (), sd->m_ploc.m_enode->m_index,
1508 2 : sd->get_supernode ()->m_id);
1509 : }
1510 :
1511 3573 : if (m_saved_diagnostics.length () == 0)
1512 1923 : return;
1513 :
1514 : /* Compute the shortest_paths once, sharing it between all diagnostics. */
1515 1650 : epath_finder pf (eg);
1516 :
1517 : /* Iterate through all saved diagnostics, adding them to a dedupe_winners
1518 : instance. This partitions the saved diagnostics by dedupe_key,
1519 : generating exploded_paths for them, and retaining the best one in each
1520 : partition. */
1521 1650 : dedupe_winners best_candidates;
1522 :
1523 1650 : int i;
1524 1650 : saved_diagnostic *sd;
1525 9971 : FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
1526 6671 : best_candidates.add (get_logger (), &pf, sd);
1527 :
1528 1650 : best_candidates.handle_interactions (this);
1529 :
1530 : /* For each dedupe-key, call emit_saved_diagnostic on the "best"
1531 : saved_diagnostic. */
1532 1650 : best_candidates.emit_best (this, eg);
1533 3573 : }
1534 :
1535 : /* Custom subclass of diagnostics::metadata which, for SARIF output,
1536 : populates the property bag of the diagnostic's "result" object
1537 : with information from the saved_diagnostic and the
1538 : pending_diagnostic. */
1539 :
1540 4386 : class pending_diagnostic_metadata : public diagnostics::metadata
1541 : {
1542 : public:
1543 4386 : pending_diagnostic_metadata (const saved_diagnostic &sd)
1544 4386 : : m_sd (sd)
1545 : {
1546 : }
1547 :
1548 : void
1549 33 : maybe_add_sarif_properties (diagnostics::sarif_object &result_obj)
1550 : const override
1551 : {
1552 33 : m_sd.maybe_add_sarif_properties (result_obj);
1553 33 : }
1554 :
1555 : private:
1556 : const saved_diagnostic &m_sd;
1557 : };
1558 :
1559 : /* Given a saved_diagnostic SD with m_best_epath through EG,
1560 : create an checker_path of suitable events and use it to call
1561 : SD's underlying pending_diagnostic "emit" vfunc to emit a diagnostic. */
1562 :
1563 : void
1564 4386 : diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg,
1565 : saved_diagnostic &sd)
1566 : {
1567 4386 : LOG_SCOPE (get_logger ());
1568 4386 : log ("sd[%i]: %qs at SN: %i",
1569 4386 : sd.get_index (), sd.m_d->get_kind (), sd.get_supernode ()->m_id);
1570 5739 : log ("num dupes: %i", sd.get_num_dupes ());
1571 :
1572 4386 : exploded_path *epath = sd.get_best_epath ();
1573 4386 : gcc_assert (epath);
1574 :
1575 4386 : epath->maybe_log (get_logger (), "best epath");
1576 :
1577 : /* Precompute all enodes from which the diagnostic is reachable. */
1578 4386 : path_builder pb (eg, *epath, sd.get_feasibility_problem (), sd);
1579 :
1580 : /* Annotate EPATH with information specific to the diagnostic, such
1581 : as pertinent data flow events. */
1582 4386 : annotate_exploded_path (pb, *epath);
1583 4386 : epath->maybe_log (get_logger (), "best epath with annotations");
1584 :
1585 : /* This is the diagnostics::paths::path instance that will be built for
1586 : the diagnostic. */
1587 4386 : checker_path emission_path (get_logical_location_manager (),
1588 : eg.get_ext_state (),
1589 4386 : get_logger ());
1590 :
1591 : /* Populate emission_path with a full description of EPATH. */
1592 4386 : build_emission_path (pb, *epath, &emission_path);
1593 :
1594 : /* Now prune it to just cover the most pertinent events. */
1595 4386 : prune_path (&emission_path, sd.m_sm, sd.m_sval, sd.m_state);
1596 :
1597 : /* Add any saved events to the path, giving contextual information
1598 : about what the analyzer was simulating as the diagnostic was
1599 : generated. These don't get pruned, as they are probably pertinent. */
1600 4386 : sd.add_any_saved_events (emission_path);
1601 :
1602 : /* Add a final event to the path, covering the diagnostic itself. */
1603 4386 : {
1604 4386 : const exploded_node *const enode = epath->get_final_enode ();
1605 4386 : sd.m_d->add_final_event (sd.m_sm, enode, sd.m_ploc.m_event_loc_info,
1606 : sd.m_var, sd.m_state, &emission_path);
1607 : }
1608 :
1609 : /* The "final" event might not be final; if the saved_diagnostic has a
1610 : trailing eedge stashed, add any events for it. This is for use
1611 : in handling longjmp, to show where a longjmp is rewinding to. */
1612 4386 : if (sd.m_trailing_eedge)
1613 4 : add_events_for_eedge (pb, *sd.m_trailing_eedge, &emission_path, nullptr,
1614 : nullptr);
1615 :
1616 4386 : emission_path.inject_any_inlined_call_events (get_logger ());
1617 :
1618 4386 : emission_path.prepare_for_emission (sd.m_d.get ());
1619 :
1620 4386 : location_t loc = sd.m_ploc.m_event_loc_info.m_loc;
1621 4386 : loc = sd.m_d->fixup_location (loc, true);
1622 :
1623 : /* Allow the pending_diagnostic to fix up the locations of events. */
1624 4386 : emission_path.fixup_locations (sd.m_d.get ());
1625 :
1626 4386 : gcc_rich_location rich_loc (loc);
1627 4386 : rich_loc.set_path (&emission_path);
1628 :
1629 4386 : auto_diagnostic_group d;
1630 4386 : auto_cfun sentinel (sd.get_supernode ()->m_fun);
1631 4386 : pending_diagnostic_metadata m (sd);
1632 4386 : diagnostic_emission_context diag_ctxt (sd, rich_loc, m, get_logger ());
1633 4386 : if (sd.m_d->emit (diag_ctxt))
1634 : {
1635 4327 : sd.emit_any_notes ();
1636 :
1637 4327 : unsigned num_dupes = sd.get_num_dupes ();
1638 4327 : if (flag_analyzer_show_duplicate_count && num_dupes > 0)
1639 4 : inform_n (loc, num_dupes,
1640 : "%i duplicate", "%i duplicates",
1641 : num_dupes);
1642 4327 : if (flag_dump_analyzer_exploded_paths)
1643 : {
1644 0 : auto_timevar tv (TV_ANALYZER_DUMP);
1645 0 : pretty_printer pp;
1646 0 : pp_printf (&pp, "%s.%i.%s.epath.txt",
1647 0 : dump_base_name, sd.get_index (), sd.m_d->get_kind ());
1648 0 : char *filename = xstrdup (pp_formatted_text (&pp));
1649 0 : epath->dump_to_file (filename, eg.get_ext_state ());
1650 0 : inform (loc, "exploded path written to %qs", filename);
1651 0 : free (filename);
1652 0 : }
1653 : }
1654 4386 : }
1655 :
1656 : const diagnostics::logical_locations::manager &
1657 4386 : diagnostic_manager::get_logical_location_manager () const
1658 : {
1659 4386 : gcc_assert (global_dc);
1660 4386 : auto mgr = global_dc->get_logical_location_manager ();
1661 4386 : gcc_assert (mgr);
1662 4386 : return *mgr;
1663 : }
1664 :
1665 : /* Dump C to this logger, indenting each line by the current
1666 : indentation level. */
1667 :
1668 : void
1669 2575 : logger::log_canvas (const text_art::canvas &c)
1670 : {
1671 2575 : std::string per_line_prefix (m_indent_level, ' ');
1672 2575 : c.print_to_pp (get_printer (), per_line_prefix.c_str ());
1673 2575 : pp_flush (get_printer ());
1674 2575 : }
1675 :
1676 : /* Dump OBJ to LOGGER, using OBJ's make_dump_widget member function. */
1677 :
1678 : template <typename T>
1679 : void
1680 26095 : dump_to_logger (const T &obj,
1681 : logger *logger,
1682 : const char *label)
1683 : {
1684 26095 : if (!logger)
1685 26095 : return;
1686 34 : text_art::theme *theme = global_dc->get_diagram_theme ();
1687 34 : if (!theme)
1688 : return;
1689 :
1690 0 : logger->log ("%s:", label);
1691 0 : logger->inc_indent ();
1692 :
1693 0 : text_art::style_manager sm;
1694 0 : text_art::style tree_style (text_art::get_style_from_color_cap_name ("note"));
1695 :
1696 0 : text_art::style::id_t tree_style_id (sm.get_or_create_id (tree_style));
1697 :
1698 0 : symbolic::node_dump_state nds (sm, *theme, tree_style_id, true, true);
1699 0 : if (auto w = obj.make_dump_widget (nds))
1700 : {
1701 0 : text_art::canvas c (w->to_canvas (nds.m_sm));
1702 0 : logger->log_canvas (c);
1703 0 : }
1704 :
1705 0 : logger->dec_indent ();
1706 0 : }
1707 :
1708 : static void
1709 26095 : log_region_model (logger *logger,
1710 : const char *label,
1711 : const region_model &model)
1712 : {
1713 13 : dump_to_logger<region_model> (model, logger, label);
1714 0 : }
1715 :
1716 38217 : class epath_rewind_context : public rewind_context
1717 : {
1718 : public:
1719 38217 : epath_rewind_context (logger *logger,
1720 : diagnostic_state input_state,
1721 : state_transition *&last_state_transition,
1722 : exploded_path::element_t &epath_element,
1723 : const region_model &src_model,
1724 : const region_model &dst_model)
1725 : : rewind_context (logger, input_state),
1726 38217 : m_last_state_transition (last_state_transition),
1727 38217 : m_epath_element (epath_element),
1728 38217 : m_src_model (src_model),
1729 38217 : m_dst_model (dst_model)
1730 : {
1731 38217 : }
1732 :
1733 : const region_model &
1734 1077 : get_src_region_model () const final override
1735 : {
1736 1077 : return m_src_model;
1737 : }
1738 :
1739 : const region_model &
1740 2746 : get_dst_region_model () const final override
1741 : {
1742 2746 : return m_dst_model;
1743 : }
1744 :
1745 : bool
1746 10954 : could_be_affected_by_write_p (tree lhs) final override
1747 : {
1748 10954 : if (!m_input.m_region_holding_value)
1749 : return false;
1750 :
1751 426 : if (TREE_CODE (lhs) == SSA_NAME)
1752 372 : if (tree decl = m_input.m_region_holding_value->maybe_get_decl ())
1753 197 : return decl == lhs;
1754 :
1755 : return true;
1756 : }
1757 :
1758 : void
1759 79 : add_state_transition (std::unique_ptr<state_transition> st) final override
1760 : {
1761 79 : gcc_assert (st.get ());
1762 79 : if (m_logger)
1763 : {
1764 0 : m_logger->start_log_line ();
1765 0 : m_logger->log_partial ("adding state transition: ");
1766 0 : st->dump_to_pp (m_logger->get_printer ());
1767 0 : m_logger->end_log_line ();
1768 : }
1769 :
1770 : /* Chain up the state_transition instances, so that each state transition
1771 : has a pointer to the one that occurred before it (but was created after
1772 : it, since we are rewinding the epath). */
1773 79 : if (m_last_state_transition)
1774 32 : m_last_state_transition->m_prev_state_transition = st.get ();
1775 79 : m_last_state_transition = st.get ();
1776 :
1777 79 : m_epath_element.m_state_transition = std::move (st);
1778 79 : }
1779 :
1780 : private:
1781 : state_transition *&m_last_state_transition;
1782 : exploded_path::element_t &m_epath_element;
1783 : const region_model &m_src_model;
1784 : const region_model &m_dst_model;
1785 : };
1786 :
1787 : /* Return a region_model for the state after any operation/custom_edge_info
1788 : on EEDGE, but without state purging or state merging. Use SRC_MODEL as
1789 : the source state.
1790 :
1791 : We do this to make it easier to rewind state transitions in
1792 : diagnostic_manager::annotate_exploded_path. */
1793 :
1794 : static region_model
1795 44025 : make_raw_dst_region_model (logger *logger,
1796 : const exploded_edge *eedge,
1797 : const region_model &src_model,
1798 : const supergraph &sg)
1799 : {
1800 44025 : LOG_SCOPE (logger);
1801 :
1802 : /* Update cfun and input_location in case of an ICE: make it easier to
1803 : track down which source construct we're failing to handle. */
1804 83664 : auto_cfun sentinel (eedge->m_src->get_function ());
1805 44025 : input_location = eedge->m_src->get_location ();
1806 :
1807 44025 : region_model_context *const ctxt = nullptr;
1808 :
1809 44025 : if (logger)
1810 : {
1811 13 : log_region_model (logger, "src_model", src_model);
1812 13 : log_region_model (logger, "dst_model",
1813 13 : *eedge->m_dest->get_state ().m_region_model);
1814 : }
1815 :
1816 44025 : if (eedge->m_custom_info)
1817 : {
1818 2891 : if (logger)
1819 : {
1820 0 : logger->start_log_line ();
1821 0 : eedge->m_custom_info->print (logger->get_printer ());
1822 0 : logger->end_log_line ();
1823 : }
1824 2891 : region_model new_model (src_model);
1825 2891 : eedge->m_custom_info->update_model (&new_model, eedge, ctxt);
1826 2891 : if (logger)
1827 0 : log_region_model (logger, "new model after custom_info", new_model);
1828 : return new_model;
1829 : }
1830 : else
1831 : {
1832 41134 : const superedge *sedge = eedge->m_sedge;
1833 41134 : if (sedge)
1834 : {
1835 36471 : if (logger)
1836 : {
1837 11 : label_text desc (sedge->get_description (false));
1838 11 : logger->log (" sedge: SN:%i -> SN:%i %s",
1839 11 : sedge->m_src->m_id,
1840 11 : sedge->m_dest->m_id,
1841 : desc.get ());
1842 11 : }
1843 :
1844 36471 : if (auto op = sedge->get_op ())
1845 : {
1846 26067 : if (logger)
1847 : {
1848 6 : logger->start_log_line ();
1849 6 : op->print_as_edge_label (logger->get_printer (), false);
1850 6 : logger->end_log_line ();
1851 : }
1852 26067 : feasibility_state fs (src_model, sg);
1853 26067 : op->execute_for_feasibility (*eedge,
1854 : fs,
1855 : ctxt,
1856 : nullptr);
1857 26067 : log_region_model (logger, "after operation, fs model",
1858 26067 : fs.get_model ());
1859 26067 : return fs.get_model ();
1860 26067 : }
1861 : else
1862 : {
1863 10404 : if (logger)
1864 5 : logger->log ("null operation, using src_model");
1865 10404 : return src_model;
1866 : }
1867 : }
1868 : else
1869 : {
1870 : /* Special-case the initial eedge from the origin node to the
1871 : initial function by pushing a frame for it. */
1872 4663 : if (eedge->m_src->m_index == 0)
1873 : {
1874 4273 : function *fun = eedge->m_dest->get_function ();
1875 4273 : gcc_assert (fun);
1876 4273 : region_model new_model (src_model);
1877 4273 : new_model.push_frame (*fun, nullptr, nullptr, ctxt);
1878 4273 : if (logger)
1879 : {
1880 2 : logger->log (" pushing frame for %qD", fun->decl);
1881 2 : log_region_model (logger, "new model", new_model);
1882 : }
1883 4273 : return new_model;
1884 4273 : }
1885 : }
1886 : }
1887 :
1888 390 : return src_model;
1889 44025 : }
1890 :
1891 : /* Populate the elements of EPATH with diagnostic_state and state_transition
1892 : information pertinent to the pending diagnostic. */
1893 :
1894 : void
1895 4386 : diagnostic_manager::annotate_exploded_path (const path_builder &pb,
1896 : exploded_path &epath) const
1897 : {
1898 4386 : auto logger = get_logger ();
1899 4386 : LOG_SCOPE (logger);
1900 :
1901 : // TODO: consolidate this with build_emission_path?
1902 4386 : interesting_t interest;
1903 4386 : pb.get_pending_diagnostic ()->mark_interesting_stuff (&interest);
1904 :
1905 4386 : gcc_assert (epath.m_elements.size () > 0);
1906 :
1907 4386 : diagnostic_state curr_state;
1908 4386 : state_transition *last_state_transition = nullptr;
1909 :
1910 4386 : if (interest.m_read_regions.size () > 0)
1911 601 : curr_state = interest.m_read_regions[0];
1912 :
1913 : /* Walk EPATH forwards, generating region_model instances for the elements
1914 : of EPATH without state purging or merging, so that we can reliably
1915 : rewind state. */
1916 4386 : std::vector<region_model> src_models;
1917 4386 : std::vector<region_model> dst_models;
1918 48411 : for (int idx = 0; idx < epath.m_elements.size (); ++idx)
1919 : {
1920 44025 : auto eedge = epath.m_elements[idx].m_eedge;
1921 44025 : if (logger)
1922 13 : logger->log ("edge[%i]: considering EN %i -> EN %i",
1923 : idx,
1924 13 : eedge->m_src->m_index,
1925 13 : eedge->m_dest->m_index);
1926 44025 : region_model src_model (pb.get_ext_state ().get_node_manager ());
1927 44025 : if (idx > 0)
1928 39639 : src_model = dst_models[idx - 1];
1929 44025 : src_models.push_back (src_model);
1930 44025 : dst_models.push_back
1931 44025 : (make_raw_dst_region_model (logger,
1932 : eedge,
1933 : src_model,
1934 : pb.get_supergraph ()));
1935 44025 : }
1936 :
1937 : /* Walk EPATH backwards, using the region_models we just built,
1938 : propagating annotation information backwards. */
1939 41972 : for (int idx = epath.m_elements.size () - 1; idx >= 0; --idx)
1940 : {
1941 38217 : exploded_path::element_t &iter_element = epath.m_elements[idx];
1942 38217 : if (logger)
1943 : {
1944 11 : logger->log ("edge[%i]: considering rewinding EN %i -> EN %i",
1945 : idx,
1946 11 : iter_element.m_eedge->m_src->m_index,
1947 11 : iter_element.m_eedge->m_dest->m_index);
1948 11 : logger->start_log_line ();
1949 11 : logger->log_partial ("curr_state: ");
1950 11 : curr_state.dump_to_pp (logger->get_printer ());
1951 11 : logger->end_log_line ();
1952 : }
1953 38217 : iter_element.m_state_at_dst = curr_state;
1954 38217 : const exploded_edge *eedge = iter_element.m_eedge;
1955 38217 : gcc_assert (eedge);
1956 :
1957 38217 : epath_rewind_context ctxt (logger, curr_state,
1958 : last_state_transition, iter_element,
1959 38217 : src_models[idx], dst_models[idx]);
1960 38217 : if (eedge->m_custom_info)
1961 : {
1962 2586 : if (logger)
1963 : {
1964 0 : logger->start_log_line ();
1965 0 : logger->log_partial ("custom_edge_info: ");
1966 0 : eedge->m_custom_info->print (logger->get_printer ());
1967 0 : logger->end_log_line ();
1968 : }
1969 2586 : if (!eedge->m_custom_info->try_to_rewind_data_flow (ctxt))
1970 : {
1971 516 : if (logger)
1972 0 : logger->log ("could not rewind custom info");
1973 : return;
1974 : }
1975 : }
1976 35631 : else if (const operation *op = eedge->maybe_get_op ())
1977 : {
1978 22122 : if (logger)
1979 : {
1980 6 : logger->start_log_line ();
1981 6 : logger->log_partial ("op: ");
1982 6 : op->print_as_edge_label (logger->get_printer (), false);
1983 6 : logger->end_log_line ();
1984 : }
1985 22122 : if (!op->try_to_rewind_data_flow (ctxt))
1986 : {
1987 115 : if (logger)
1988 1 : logger->log ("could not rewind op");
1989 : return;
1990 : }
1991 : }
1992 :
1993 37586 : iter_element.m_state_at_src = ctxt.m_output;
1994 37586 : curr_state = ctxt.m_output;
1995 37586 : if (logger)
1996 : {
1997 10 : logger->log ("rewound");
1998 10 : logger->start_log_line ();
1999 10 : logger->log_partial ("curr_state: ");
2000 10 : curr_state.dump_to_pp (logger->get_printer ());
2001 10 : logger->end_log_line ();
2002 : }
2003 37586 : }
2004 8772 : }
2005 :
2006 : /* Emit a "path" of events to EMISSION_PATH describing the exploded path
2007 : EPATH within EG. */
2008 :
2009 : void
2010 4386 : diagnostic_manager::build_emission_path (const path_builder &pb,
2011 : const exploded_path &epath,
2012 : checker_path *emission_path) const
2013 : {
2014 4386 : LOG_SCOPE (get_logger ());
2015 :
2016 4386 : interesting_t interest;
2017 4386 : pb.get_pending_diagnostic ()->mark_interesting_stuff (&interest);
2018 :
2019 : /* Add region creation events for any globals of interest, at the
2020 : beginning of the path. */
2021 4386 : {
2022 8539 : for (auto reg : interest.m_region_creation)
2023 1403 : switch (reg->get_memory_space ())
2024 : {
2025 1138 : default:
2026 1138 : continue;
2027 265 : case MEMSPACE_CODE:
2028 265 : case MEMSPACE_GLOBALS:
2029 265 : case MEMSPACE_READONLY_DATA:
2030 265 : {
2031 265 : const region *base_reg = reg->get_base_region ();
2032 265 : if (tree decl = base_reg->maybe_get_decl ())
2033 255 : if (DECL_P (decl)
2034 255 : && useful_location_p (DECL_SOURCE_LOCATION (decl)))
2035 : {
2036 255 : emission_path->add_region_creation_events
2037 255 : (pb.get_pending_diagnostic (),
2038 : reg, nullptr,
2039 255 : event_loc_info (DECL_SOURCE_LOCATION (decl),
2040 : NULL_TREE,
2041 255 : 0),
2042 255 : m_verbosity > 3);
2043 : }
2044 : }
2045 1138 : }
2046 : }
2047 :
2048 : /* Walk EPATH, adding events as appropriate. */
2049 48411 : for (unsigned i = 0; i < epath.m_elements.size (); ++i)
2050 : {
2051 44025 : const exploded_edge *eedge = epath.m_elements[i].m_eedge;
2052 44025 : gcc_assert (eedge);
2053 44025 : add_events_for_eedge (pb, *eedge, emission_path, &interest,
2054 44025 : epath.m_elements[i].m_state_transition.get ());
2055 : }
2056 4386 : add_event_on_final_node (pb, epath.get_final_enode (),
2057 : emission_path, &interest);
2058 4386 : }
2059 :
2060 : /* Emit a region_creation_event when requested on the last statement in
2061 : the path.
2062 :
2063 : If a region_creation_event should be emitted on the last statement of the
2064 : path, we need to peek to the successors to get whether the final enode
2065 : created a region.
2066 : */
2067 :
2068 : void
2069 4386 : diagnostic_manager::add_event_on_final_node (const path_builder &pb,
2070 : const exploded_node *final_enode,
2071 : checker_path *emission_path,
2072 : interesting_t *interest) const
2073 : {
2074 4386 : const program_point &src_point = final_enode->get_point ();
2075 4386 : const int src_stack_depth = src_point.get_stack_depth ();
2076 4386 : const program_state &src_state = final_enode->get_state ();
2077 4386 : const region_model *src_model = src_state.m_region_model;
2078 :
2079 4386 : unsigned j;
2080 4386 : exploded_edge *e;
2081 7863 : FOR_EACH_VEC_ELT (final_enode->m_succs, j, e)
2082 : {
2083 3554 : exploded_node *dst = e->m_dest;
2084 3554 : const program_state &dst_state = dst->get_state ();
2085 3554 : const region_model *dst_model = dst_state.m_region_model;
2086 3554 : if (src_model->get_dynamic_extents ()
2087 3554 : != dst_model->get_dynamic_extents ())
2088 : {
2089 : unsigned i;
2090 : const region *reg;
2091 : bool emitted = false;
2092 423 : FOR_EACH_VEC_ELT (interest->m_region_creation, i, reg)
2093 : {
2094 93 : const region *base_reg = reg->get_base_region ();
2095 93 : const svalue *old_extents
2096 93 : = src_model->get_dynamic_extents (base_reg);
2097 93 : const svalue *new_extents
2098 93 : = dst_model->get_dynamic_extents (base_reg);
2099 93 : if (old_extents == nullptr && new_extents != nullptr)
2100 81 : switch (base_reg->get_kind ())
2101 : {
2102 : default:
2103 : break;
2104 77 : case RK_HEAP_ALLOCATED:
2105 77 : case RK_ALLOCA:
2106 77 : emission_path->add_region_creation_events
2107 154 : (pb.get_pending_diagnostic (),
2108 : reg,
2109 : dst_model,
2110 77 : event_loc_info (src_point.get_location (),
2111 : src_point.get_fndecl (),
2112 154 : src_stack_depth),
2113 : false);
2114 77 : emitted = true;
2115 77 : break;
2116 : }
2117 : }
2118 330 : if (emitted)
2119 : break;
2120 : }
2121 : }
2122 4386 : }
2123 :
2124 : /* Subclass of state_change_visitor that creates state_change_event
2125 : instances. */
2126 :
2127 44029 : class state_change_event_creator : public state_change_visitor
2128 : {
2129 : public:
2130 44029 : state_change_event_creator (const path_builder &pb,
2131 : const exploded_edge &eedge,
2132 : checker_path *emission_path)
2133 44029 : : m_pb (pb),
2134 44029 : m_eedge (eedge),
2135 44029 : m_emission_path (emission_path)
2136 : {}
2137 :
2138 120 : bool on_global_state_change (const state_machine &sm,
2139 : state_machine::state_t src_sm_val,
2140 : state_machine::state_t dst_sm_val)
2141 : final override
2142 : {
2143 120 : if (&sm != m_pb.get_sm ())
2144 : return false;
2145 56 : const exploded_node *src_node = m_eedge.m_src;
2146 56 : const exploded_node *dst_node = m_eedge.m_dest;
2147 56 : const gimple *stmt = m_eedge.maybe_get_stmt ();
2148 56 : const program_state &dst_state = dst_node->get_state ();
2149 :
2150 56 : m_emission_path->add_event
2151 56 : (std::make_unique<state_change_event> (m_eedge.m_src,
2152 : stmt,
2153 : sm,
2154 112 : nullptr,
2155 : src_sm_val,
2156 : dst_sm_val,
2157 56 : nullptr,
2158 : dst_state,
2159 : src_node));
2160 56 : return false;
2161 : }
2162 :
2163 4984 : bool on_state_change (const state_machine &sm,
2164 : state_machine::state_t src_sm_val,
2165 : state_machine::state_t dst_sm_val,
2166 : const svalue *sval,
2167 : const svalue *dst_origin_sval) final override
2168 : {
2169 4984 : if (&sm != m_pb.get_sm ())
2170 : return false;
2171 :
2172 3964 : const exploded_node *src_node = m_eedge.m_src;
2173 3964 : const exploded_node *dst_node = m_eedge.m_dest;
2174 3964 : const gimple *stmt = m_eedge.maybe_get_stmt ();
2175 3964 : const program_state &dst_state = dst_node->get_state ();
2176 :
2177 3964 : m_emission_path->add_event
2178 3964 : (std::make_unique<state_change_event> (m_eedge.m_src,
2179 : stmt,
2180 : sm,
2181 : sval,
2182 : src_sm_val,
2183 : dst_sm_val,
2184 : dst_origin_sval,
2185 : dst_state,
2186 : src_node));
2187 3964 : return false;
2188 : }
2189 :
2190 : const path_builder &m_pb;
2191 : const exploded_edge &m_eedge;
2192 : checker_path *m_emission_path;
2193 : };
2194 :
2195 : /* Compare SRC_STATE and DST_STATE (which use EXT_STATE), and call
2196 : VISITOR's on_state_change for every sm-state change that occurs
2197 : to a tree, and on_global_state_change for every global state change
2198 : that occurs.
2199 :
2200 : This determines the state changes that ought to be reported to
2201 : the user: a combination of the effects of changes to sm_state_map
2202 : (which maps svalues to sm-states), and of region_model changes
2203 : (which map trees to svalues).
2204 :
2205 : Bail out early and return true if any call to on_global_state_change
2206 : or on_state_change returns true, otherwise return false.
2207 :
2208 : This is split out to make it easier to experiment with changes to
2209 : exploded_node granularity (so that we can observe what state changes
2210 : lead to state_change_events being emitted). */
2211 :
2212 : bool
2213 44029 : for_each_state_change (const program_state &src_state,
2214 : const program_state &dst_state,
2215 : const extrinsic_state &ext_state,
2216 : state_change_visitor *visitor)
2217 : {
2218 88058 : gcc_assert (src_state.m_checker_states.length ()
2219 : == ext_state.get_num_checkers ());
2220 88058 : gcc_assert (dst_state.m_checker_states.length ()
2221 : == ext_state.get_num_checkers ());
2222 350700 : for (unsigned i = 0; i < ext_state.get_num_checkers (); i++)
2223 : {
2224 306671 : const state_machine &sm = ext_state.get_sm (i);
2225 306671 : const sm_state_map &src_smap = *src_state.m_checker_states[i];
2226 306671 : const sm_state_map &dst_smap = *dst_state.m_checker_states[i];
2227 :
2228 : /* Add events for any global state changes. */
2229 306671 : if (src_smap.get_global_state () != dst_smap.get_global_state ())
2230 120 : if (visitor->on_global_state_change (sm,
2231 : src_smap.get_global_state (),
2232 : dst_smap.get_global_state ()))
2233 : return true;
2234 :
2235 : /* Add events for per-svalue state changes. */
2236 352431 : for (sm_state_map::iterator_t iter = dst_smap.begin ();
2237 659102 : iter != dst_smap.end ();
2238 45760 : ++iter)
2239 : {
2240 45760 : const svalue *sval = (*iter).first;
2241 45760 : state_machine::state_t dst_sm_val = (*iter).second.m_state;
2242 45760 : state_machine::state_t src_sm_val
2243 45760 : = src_smap.get_state (sval, ext_state);
2244 45760 : if (dst_sm_val != src_sm_val)
2245 : {
2246 4984 : const svalue *origin_sval = (*iter).second.m_origin;
2247 4984 : if (visitor->on_state_change (sm, src_sm_val, dst_sm_val,
2248 : sval, origin_sval))
2249 0 : return true;
2250 : }
2251 : }
2252 : }
2253 : return false;
2254 : }
2255 :
2256 : /* Subroutine of diagnostic_manager::build_emission_path.
2257 : Add any events for EEDGE to EMISSION_PATH. */
2258 :
2259 : void
2260 44029 : diagnostic_manager::add_events_for_eedge (const path_builder &pb,
2261 : const exploded_edge &eedge,
2262 : checker_path *emission_path,
2263 : interesting_t *interest,
2264 : const state_transition *state_trans) const
2265 : {
2266 44029 : const exploded_node *src_node = eedge.m_src;
2267 44029 : const program_point &src_point = src_node->get_point ();
2268 44029 : const int src_stack_depth = src_point.get_stack_depth ();
2269 44029 : const exploded_node *dst_node = eedge.m_dest;
2270 44029 : const program_point &dst_point = dst_node->get_point ();
2271 44029 : const int dst_stack_depth = dst_point.get_stack_depth ();
2272 44029 : if (get_logger ())
2273 : {
2274 13 : get_logger ()->start_log_line ();
2275 13 : pretty_printer *pp = get_logger ()->get_printer ();
2276 13 : pp_printf (pp, "EN %i -> EN %i: ",
2277 13 : eedge.m_src->m_index,
2278 13 : eedge.m_dest->m_index);
2279 13 : src_point.print (pp, format (false));
2280 13 : pp_string (pp, "-> ");
2281 13 : dst_point.print (pp, format (false));
2282 13 : if (state_trans)
2283 : {
2284 0 : pp_string (pp, " {");
2285 0 : state_trans->dump_to_pp (pp);
2286 0 : pp_string (pp, "}");
2287 : }
2288 13 : get_logger ()->end_log_line ();
2289 : }
2290 44029 : const program_state &src_state = src_node->get_state ();
2291 44029 : const program_state &dst_state = dst_node->get_state ();
2292 :
2293 44029 : bool created_event_for_state_trans = false;
2294 :
2295 : /* Add state change events for the states that have changed.
2296 : We add these before events for superedges, so that if we have a
2297 : state_change_event due to following an edge, we'll get this sequence
2298 : of events:
2299 :
2300 : | if (!ptr)
2301 : | ~
2302 : | |
2303 : | (1) assuming 'ptr' is non-NULL (state_change_event)
2304 : | (2) following 'false' branch... (start_cfg_edge_event)
2305 : ...
2306 : | do_something (ptr);
2307 : | ~~~~~~~~~~~~~^~~~~
2308 : | |
2309 : | (3) ...to here (end_cfg_edge_event). */
2310 44029 : state_change_event_creator visitor (pb, eedge, emission_path);
2311 44029 : for_each_state_change (src_state, dst_state, pb.get_ext_state (),
2312 : &visitor);
2313 :
2314 : /* Give diagnostics an opportunity to inject extra events, or
2315 : to override the rest of this function. */
2316 44029 : pending_diagnostic *pd = pb.get_pending_diagnostic ();
2317 44029 : if (pd->maybe_add_custom_events_for_eedge (eedge, emission_path))
2318 : return;
2319 :
2320 : /* Allow non-standard edges to add events, e.g. when rewinding from
2321 : longjmp to a setjmp. */
2322 43052 : if (eedge.m_custom_info)
2323 : {
2324 2889 : eedge.m_custom_info->add_events_to_path (emission_path, eedge, *pd,
2325 : state_trans);
2326 2889 : created_event_for_state_trans = true;
2327 : }
2328 :
2329 : /* Don't add events for insignificant edges at verbosity levels below 3. */
2330 43052 : if (m_verbosity < 3)
2331 42827 : if (!significant_edge_p (pb, eedge) && !state_trans)
2332 : return;
2333 :
2334 : /* Add events for operations. */
2335 42343 : if (eedge.m_sedge)
2336 36435 : if (auto op = eedge.m_sedge->get_op ())
2337 26339 : op->add_any_events_for_eedge (eedge, *emission_path);
2338 :
2339 : /* Add events for function entry. */
2340 42343 : if (dst_point.get_supernode ()->entry_p ())
2341 : {
2342 5703 : pb.get_pending_diagnostic ()->add_function_entry_event
2343 5703 : (eedge, emission_path,
2344 5703 : (state_trans
2345 23 : ? state_trans->dyn_cast_state_transition_at_call ()
2346 : : nullptr));
2347 5703 : created_event_for_state_trans = true;
2348 : /* Create region_creation_events for on-stack regions within
2349 : this frame. */
2350 5703 : if (interest)
2351 : {
2352 : unsigned i;
2353 : const region *reg;
2354 7256 : FOR_EACH_VEC_ELT (interest->m_region_creation, i, reg)
2355 1553 : if (const frame_region *frame = reg->maybe_get_frame_region ())
2356 1964 : if (frame->get_fndecl () == dst_point.get_fndecl ())
2357 : {
2358 862 : const region *base_reg = reg->get_base_region ();
2359 862 : if (tree decl = base_reg->maybe_get_decl ())
2360 761 : if (DECL_P (decl)
2361 761 : && useful_location_p (DECL_SOURCE_LOCATION (decl)))
2362 : {
2363 757 : emission_path->add_region_creation_events
2364 1514 : (pb.get_pending_diagnostic (),
2365 757 : reg, dst_state.m_region_model,
2366 757 : event_loc_info (DECL_SOURCE_LOCATION (decl),
2367 : dst_point.get_fndecl (),
2368 757 : dst_stack_depth),
2369 757 : m_verbosity > 3);
2370 : }
2371 : }
2372 : }
2373 : }
2374 :
2375 : /* Look for changes in dynamic extents, which will identify
2376 : the creation of heap-based regions and alloca regions. */
2377 42343 : if (interest)
2378 : {
2379 42339 : const region_model *src_model = src_state.m_region_model;
2380 42339 : const region_model *dst_model = dst_state.m_region_model;
2381 42339 : if (src_model->get_dynamic_extents ()
2382 42339 : != dst_model->get_dynamic_extents ())
2383 : {
2384 : unsigned i;
2385 : const region *reg;
2386 2813 : FOR_EACH_VEC_ELT (interest->m_region_creation, i, reg)
2387 : {
2388 437 : const region *base_reg = reg->get_base_region ();
2389 437 : const svalue *old_extents
2390 437 : = src_model->get_dynamic_extents (base_reg);
2391 437 : const svalue *new_extents
2392 437 : = dst_model->get_dynamic_extents (base_reg);
2393 437 : if (old_extents == nullptr && new_extents != nullptr)
2394 295 : switch (base_reg->get_kind ())
2395 : {
2396 : default:
2397 : break;
2398 259 : case RK_HEAP_ALLOCATED:
2399 259 : case RK_ALLOCA:
2400 259 : emission_path->add_region_creation_events
2401 259 : (pb.get_pending_diagnostic (),
2402 : reg, dst_model,
2403 259 : event_loc_info (src_point.get_location (),
2404 : src_point.get_fndecl (),
2405 518 : src_stack_depth),
2406 259 : m_verbosity > 3);
2407 259 : break;
2408 : }
2409 : }
2410 : }
2411 : }
2412 :
2413 : /* If we have a state transition and haven't yet created an
2414 : event that describes it, do so now. */
2415 42343 : if (state_trans && !created_event_for_state_trans)
2416 44 : emission_path->add_event
2417 44 : (std::make_unique<state_transition_event>
2418 44 : (eedge.m_src->get_point (),
2419 : state_trans));
2420 :
2421 42343 : if (pb.get_feasibility_problem ()
2422 42343 : && &pb.get_feasibility_problem ()->m_eedge == &eedge)
2423 : {
2424 4 : pretty_printer pp;
2425 4 : pp_format_decoder (&pp) = default_tree_printer;
2426 4 : pp_string (&pp,
2427 : "this path would have been rejected as infeasible"
2428 : " at this edge: ");
2429 4 : pb.get_feasibility_problem ()->dump_to_pp (&pp);
2430 4 : emission_path->add_event
2431 4 : (std::make_unique<precanned_custom_event>
2432 4 : (event_loc_info (dst_point.get_location (),
2433 : dst_point.get_fndecl (),
2434 8 : dst_stack_depth),
2435 4 : pp_formatted_text (&pp)));
2436 4 : }
2437 44029 : }
2438 :
2439 : /* Return true if EEDGE is a significant edge in the path to the diagnostic
2440 : for PB.
2441 :
2442 : Consider all of the sibling out-eedges from the same source enode
2443 : as EEDGE.
2444 : If there's no path from the destinations of those eedges to the
2445 : diagnostic enode, then we have to take this eedge and thus it's
2446 : significant.
2447 :
2448 : Conversely if there is a path from the destination of any other sibling
2449 : eedge to the diagnostic enode, then this edge is insignificant.
2450 :
2451 : Example 1: redundant if-else:
2452 :
2453 : (A) if (...) A
2454 : (B) ... / \
2455 : else B C
2456 : (C) ... \ /
2457 : (D) [DIAGNOSTIC] D
2458 :
2459 : D is reachable by either B or C, so neither of these edges
2460 : are significant.
2461 :
2462 : Example 2: pertinent if-else:
2463 :
2464 : (A) if (...) A
2465 : (B) ... / \
2466 : else B C
2467 : (C) [NECESSARY CONDITION] | |
2468 : (D) [POSSIBLE DIAGNOSTIC] D1 D2
2469 :
2470 : D becomes D1 and D2 in the exploded graph, where the diagnostic occurs
2471 : at D2. D2 is only reachable via C, so the A -> C edge is significant.
2472 :
2473 : Example 3: redundant loop:
2474 :
2475 : (A) while (...) +-->A
2476 : (B) ... | / \
2477 : (C) ... +-B C
2478 : (D) [DIAGNOSTIC] |
2479 : D
2480 :
2481 : D is reachable from both B and C, so the A->C edge is not significant. */
2482 :
2483 : bool
2484 42827 : diagnostic_manager::significant_edge_p (const path_builder &pb,
2485 : const exploded_edge &eedge) const
2486 : {
2487 42827 : int i;
2488 42827 : exploded_edge *sibling;
2489 118543 : FOR_EACH_VEC_ELT (eedge.m_src->m_succs, i, sibling)
2490 : {
2491 76425 : if (sibling == &eedge)
2492 42433 : continue;
2493 33992 : if (pb.reachable_from_p (sibling->m_dest))
2494 : {
2495 709 : if (get_logger ())
2496 0 : get_logger ()->log (" edge EN: %i -> EN: %i is insignificant as"
2497 : " EN: %i is also reachable via"
2498 : " EN: %i -> EN: %i",
2499 0 : eedge.m_src->m_index, eedge.m_dest->m_index,
2500 0 : pb.get_diag_node ()->m_index,
2501 0 : sibling->m_src->m_index,
2502 : sibling->m_dest->m_index);
2503 : return false;
2504 : }
2505 : }
2506 :
2507 : return true;
2508 : }
2509 :
2510 : /* Prune PATH, based on the verbosity level, to the most pertinent
2511 : events for a diagnostic that involves VAR ending in state STATE
2512 : (for state machine SM).
2513 :
2514 : PATH is updated in place, and the redundant checker_events are deleted.
2515 :
2516 : As well as deleting events, call record_critical_state on events in
2517 : which state critical to the pending_diagnostic is being handled; see
2518 : the comment for diagnostic_manager::prune_for_sm_diagnostic. */
2519 :
2520 : void
2521 4386 : diagnostic_manager::prune_path (checker_path *path,
2522 : const state_machine *sm,
2523 : const svalue *sval,
2524 : state_machine::state_t state) const
2525 : {
2526 4386 : LOG_FUNC (get_logger ());
2527 4386 : path->maybe_log (get_logger (), "path");
2528 4386 : prune_for_sm_diagnostic (path, sm, sval, state);
2529 4386 : prune_interproc_events (path);
2530 4386 : if (! flag_analyzer_show_events_in_system_headers)
2531 4384 : prune_system_headers (path);
2532 4386 : consolidate_conditions (path);
2533 4386 : consolidate_unwind_events (path);
2534 4386 : finish_pruning (path);
2535 4386 : path->maybe_log (get_logger (), "pruned");
2536 4386 : }
2537 :
2538 : /* A cheap test to determine if EXPR can be the expression of interest in
2539 : an sm-diagnostic, so that we can reject cases where we have a non-lvalue.
2540 : We don't have always have a model when calling this, so we can't use
2541 : tentative_region_model_context, so there can be false positives. */
2542 :
2543 : static bool
2544 0 : can_be_expr_of_interest_p (tree expr)
2545 : {
2546 0 : if (!expr)
2547 : return false;
2548 :
2549 : /* Reject constants. */
2550 0 : if (CONSTANT_CLASS_P (expr))
2551 0 : return false;
2552 :
2553 : /* Otherwise assume that it can be an lvalue. */
2554 : return true;
2555 : }
2556 :
2557 : /* First pass of diagnostic_manager::prune_path: apply verbosity level,
2558 : pruning unrelated state change events.
2559 :
2560 : Iterate backwards through PATH, skipping state change events that aren't
2561 : VAR but update the pertinent VAR when state-copying occurs.
2562 :
2563 : As well as deleting events, call record_critical_state on events in
2564 : which state critical to the pending_diagnostic is being handled, so
2565 : that the event's get_desc vfunc can potentially supply a more precise
2566 : description of the event to the user.
2567 : e.g. improving
2568 : "calling 'foo' from 'bar'"
2569 : to
2570 : "passing possibly-NULL pointer 'ptr' to 'foo' from 'bar' as param 1"
2571 : when the diagnostic relates to later dereferencing 'ptr'. */
2572 :
2573 : void
2574 4386 : diagnostic_manager::prune_for_sm_diagnostic (checker_path *path,
2575 : const state_machine *sm,
2576 : const svalue *uncanonicalized_sval,
2577 : state_machine::state_t state) const
2578 : {
2579 4386 : auto &ext_state = path->get_ext_state ();
2580 4386 : const svalue *canonicalized_sval
2581 4386 : = sm_state_map::canonicalize_svalue (uncanonicalized_sval, ext_state);
2582 :
2583 4386 : int idx = path->num_events () - 1;
2584 70210 : while (idx >= 0 && idx < (signed)path->num_events ())
2585 : {
2586 32912 : checker_event *base_event = path->get_checker_event (idx);
2587 32912 : if (get_logger ())
2588 : {
2589 6 : if (sm)
2590 : {
2591 0 : if (uncanonicalized_sval)
2592 : {
2593 0 : label_text sval_desc = uncanonicalized_sval->get_desc ();
2594 0 : log ("considering event %i (%s), with sval: %qs, state: %qs",
2595 : idx, event_kind_to_string (base_event->get_kind ()),
2596 : sval_desc.get (), state->get_name ());
2597 0 : }
2598 : else
2599 0 : log ("considering event %i (%s), with global state: %qs",
2600 : idx, event_kind_to_string (base_event->get_kind ()),
2601 : state->get_name ());
2602 : }
2603 : else
2604 6 : log ("considering event %i", idx);
2605 : }
2606 :
2607 32912 : switch (base_event->get_kind ())
2608 : {
2609 0 : default:
2610 0 : gcc_unreachable ();
2611 :
2612 0 : case event_kind::debug:
2613 0 : if (m_verbosity < 4)
2614 : {
2615 0 : log ("filtering event %i: debug event", idx);
2616 0 : path->delete_event (idx);
2617 : }
2618 : break;
2619 :
2620 : case event_kind::custom:
2621 : /* Don't filter custom events. */
2622 : break;
2623 :
2624 12854 : case event_kind::stmt:
2625 12854 : {
2626 12854 : if (m_verbosity < 4)
2627 : {
2628 12854 : log ("filtering event %i: statement event", idx);
2629 12854 : path->delete_event (idx);
2630 : }
2631 : }
2632 : break;
2633 :
2634 : case event_kind::region_creation:
2635 : /* Don't filter these. */
2636 : break;
2637 :
2638 44 : case event_kind::state_transition:
2639 : /* Prune these if they have an empty description. */
2640 44 : {
2641 44 : tree_dump_pretty_printer pp (nullptr);
2642 44 : base_event->print_desc (pp);
2643 44 : if (strlen (pp_formatted_text (&pp)) == 0)
2644 : {
2645 0 : log (("filtering event %i:"
2646 : " state_transition_event with empty description"),
2647 : idx);
2648 0 : path->delete_event (idx);
2649 : }
2650 44 : }
2651 44 : break;
2652 :
2653 5703 : case event_kind::function_entry:
2654 5703 : if (m_verbosity < 1)
2655 : {
2656 33 : log ("filtering event %i: function entry", idx);
2657 33 : path->delete_event (idx);
2658 : }
2659 : break;
2660 :
2661 4483 : case event_kind::state_change:
2662 4483 : {
2663 4483 : state_change_event *state_change = (state_change_event *)base_event;
2664 4483 : gcc_assert (state_change->m_dst_state.m_region_model);
2665 :
2666 4483 : if (canonicalized_sval
2667 4483 : == sm_state_map::canonicalize_svalue (state_change->m_sval,
2668 : ext_state))
2669 : {
2670 2450 : if (state_change->m_origin)
2671 : {
2672 0 : if (get_logger ())
2673 : {
2674 0 : label_text sval_desc = uncanonicalized_sval->get_desc ();
2675 0 : label_text origin_sval_desc
2676 0 : = state_change->m_origin->get_desc ();
2677 0 : log ("event %i:"
2678 : " switching var of interest from %qs to %qs",
2679 : idx, sval_desc.get (),
2680 : origin_sval_desc.get ());
2681 0 : }
2682 0 : uncanonicalized_sval = state_change->m_origin;
2683 0 : canonicalized_sval
2684 0 : = sm_state_map::canonicalize_svalue (uncanonicalized_sval,
2685 : ext_state);
2686 :
2687 : }
2688 2450 : log ("event %i: switching state of interest from %qs to %qs",
2689 2450 : idx, state_change->m_to->get_name (),
2690 2450 : state_change->m_from->get_name ());
2691 2450 : state = state_change->m_from;
2692 : }
2693 2033 : else if (m_verbosity < 4)
2694 : {
2695 2033 : if (get_logger ())
2696 : {
2697 0 : if (state_change->m_sval)
2698 : {
2699 0 : label_text change_sval_desc
2700 0 : = state_change->m_sval->get_desc ();
2701 0 : if (uncanonicalized_sval)
2702 : {
2703 0 : label_text sval_desc = uncanonicalized_sval->get_desc ();
2704 0 : log ("filtering event %i:"
2705 : " state change to %qs unrelated to %qs",
2706 : idx, change_sval_desc.get (),
2707 : sval_desc.get ());
2708 0 : }
2709 : else
2710 0 : log ("filtering event %i: state change to %qs",
2711 : idx, change_sval_desc.get ());
2712 0 : }
2713 : else
2714 0 : log ("filtering event %i: global state change", idx);
2715 : }
2716 2033 : path->delete_event (idx);
2717 : }
2718 : }
2719 : break;
2720 :
2721 2599 : case event_kind::start_cfg_edge:
2722 2599 : {
2723 2599 : cfg_edge_event *event = (cfg_edge_event *)base_event;
2724 :
2725 : /* TODO: is this edge significant to var?
2726 : See if var can be in other states in the dest, but not
2727 : in other states in the src?
2728 : Must have multiple sibling edges. */
2729 :
2730 2599 : if (event->should_filter_p (m_verbosity))
2731 : {
2732 35 : log ("filtering events %i and %i: CFG edge", idx, idx + 1);
2733 35 : path->delete_event (idx);
2734 : /* Also delete the corresponding event_kind::end_cfg_edge. */
2735 35 : gcc_assert (path->get_checker_event (idx)->get_kind ()
2736 : == event_kind::end_cfg_edge);
2737 35 : path->delete_event (idx);
2738 : }
2739 : }
2740 : break;
2741 :
2742 : case event_kind::end_cfg_edge:
2743 : /* These come in pairs with event_kind::start_cfg_edge events and are
2744 : filtered when their start event is filtered. */
2745 : break;
2746 :
2747 : case event_kind::catch_:
2748 : case event_kind::throw_:
2749 : case event_kind::unwind:
2750 : /* Don't filter these. */
2751 : break;
2752 :
2753 1397 : case event_kind::call_:
2754 1397 : {
2755 1397 : call_event *event = (call_event *)base_event;
2756 1397 : const region_model *callee_model
2757 1397 : = event->m_eedge.m_dest->get_state ().m_region_model;
2758 1397 : const region_model *caller_model
2759 1397 : = event->m_eedge.m_src->get_state ().m_region_model;
2760 1397 : tree callee_var
2761 1397 : = callee_model->get_representative_tree (uncanonicalized_sval);
2762 1397 : callsite_expr expr;
2763 :
2764 1397 : tree caller_var;
2765 1397 : if (auto op = event->get_call_and_return_op ())
2766 : {
2767 1397 : tree callee_fndecl
2768 1397 : = event->m_eedge.m_dest->get_point ().get_fndecl ();
2769 1397 : caller_var
2770 1397 : = op->map_expr_from_callee_to_caller (callee_fndecl,
2771 : callee_var,
2772 : &expr);
2773 : }
2774 : else
2775 0 : caller_var
2776 0 : = caller_model->get_representative_tree (uncanonicalized_sval);
2777 :
2778 1397 : if (caller_var)
2779 : {
2780 228 : if (get_logger ())
2781 : {
2782 0 : label_text sval_desc = uncanonicalized_sval->get_desc ();
2783 0 : log ("event %i:"
2784 : " recording critical state for %qs at call"
2785 : " from %qE in callee to %qE in caller",
2786 : idx, sval_desc.get (), callee_var, caller_var);
2787 0 : }
2788 228 : if (expr.param_p ())
2789 228 : event->record_critical_state (caller_var, state);
2790 : }
2791 : }
2792 1397 : break;
2793 :
2794 818 : case event_kind::return_:
2795 818 : {
2796 818 : if (uncanonicalized_sval)
2797 : {
2798 628 : return_event *event = (return_event *)base_event;
2799 628 : const region_model *caller_model
2800 628 : = event->m_eedge.m_dest->get_state ().m_region_model;
2801 628 : tree caller_var
2802 628 : = caller_model->get_representative_tree (uncanonicalized_sval);
2803 628 : const region_model *callee_model
2804 628 : = event->m_eedge.m_src->get_state ().m_region_model;
2805 628 : callsite_expr expr;
2806 :
2807 628 : tree callee_var;
2808 :
2809 628 : if (auto op = event->get_call_and_return_op ())
2810 : {
2811 628 : tree callee_fndecl
2812 628 : = event->m_eedge.m_src->get_point ().get_fndecl ();
2813 628 : callee_var
2814 628 : = op->map_expr_from_caller_to_callee (callee_fndecl,
2815 : caller_var,
2816 : &expr);
2817 : }
2818 : else
2819 0 : callee_var
2820 0 : = callee_model->get_representative_tree (uncanonicalized_sval);
2821 :
2822 628 : if (callee_var)
2823 : {
2824 157 : if (get_logger ())
2825 : {
2826 0 : label_text sval_desc
2827 0 : = uncanonicalized_sval->get_desc ();
2828 0 : log ("event %i:"
2829 : " recording critical state for %qs at return"
2830 : " from %qE in caller to %qE in callee",
2831 : idx, sval_desc.get (), callee_var, callee_var);
2832 0 : }
2833 157 : if (expr.return_value_p ())
2834 70 : event->record_critical_state (callee_var, state);
2835 : }
2836 : }
2837 : }
2838 : break;
2839 :
2840 : case event_kind::inlined_call:
2841 : /* We don't expect to see these yet, as they're added later.
2842 : We'd want to keep them around. */
2843 : break;
2844 :
2845 : case event_kind::setjmp_:
2846 : /* TODO: only show setjmp_events that matter i.e. those for which
2847 : there is a later rewind event using them. */
2848 : case event_kind::rewind_from_longjmp:
2849 : case event_kind::rewind_to_setjmp:
2850 : break;
2851 :
2852 : case event_kind::warning:
2853 : /* Always show the final "warning" event in the path. */
2854 : break;
2855 : }
2856 32912 : idx--;
2857 : }
2858 4386 : }
2859 :
2860 : /* Subroutine of diagnostic_manager::prune_for_sm_diagnostic.
2861 : If *EXPR is not suitable to be the expression of interest in
2862 : an sm-diagnostic, set *EXPR to NULL and log. */
2863 :
2864 : void
2865 0 : diagnostic_manager::update_for_unsuitable_sm_exprs (tree *expr) const
2866 : {
2867 0 : gcc_assert (expr);
2868 0 : if (*expr && !can_be_expr_of_interest_p (*expr))
2869 : {
2870 0 : log ("new var %qE is unsuitable; setting var to NULL", *expr);
2871 0 : *expr = NULL_TREE;
2872 : }
2873 0 : }
2874 :
2875 : /* Second pass of diagnostic_manager::prune_path: remove redundant
2876 : interprocedural information.
2877 :
2878 : For example, given:
2879 : (1)- calling "f2" from "f1"
2880 : (2)--- entry to "f2"
2881 : (3)--- calling "f3" from "f2"
2882 : (4)----- entry to "f3"
2883 : (5)--- returning to "f2" to "f3"
2884 : (6)- returning to "f1" to "f2"
2885 : with no other intervening events, then none of these events are
2886 : likely to be interesting to the user.
2887 :
2888 : Prune [..., call, function-entry, return, ...] triples repeatedly
2889 : until nothing has changed. For the example above, this would
2890 : remove events (3, 4, 5), and then remove events (1, 2, 6). */
2891 :
2892 : void
2893 4386 : diagnostic_manager::prune_interproc_events (checker_path *path) const
2894 : {
2895 4386 : bool changed = false;
2896 4632 : do
2897 : {
2898 4632 : changed = false;
2899 4632 : int idx = (signed)path->num_events () - 1;
2900 23896 : while (idx >= 0)
2901 : {
2902 : /* Prune [..., call, function-entry, return, ...] triples. */
2903 19264 : if (idx + 2 < (signed)path->num_events ()
2904 10290 : && path->get_checker_event (idx)->is_call_p ()
2905 1104 : && path->get_checker_event (idx + 1)->is_function_entry_p ()
2906 20360 : && path->get_checker_event (idx + 2)->is_return_p ())
2907 : {
2908 533 : if (get_logger ())
2909 : {
2910 0 : label_text desc
2911 0 : (path->get_checker_event (idx)->get_desc
2912 0 : (*global_dc->get_reference_printer ()));
2913 0 : log ("filtering events %i-%i:"
2914 : " irrelevant call/entry/return: %s",
2915 : idx, idx + 2, desc.get ());
2916 0 : }
2917 533 : path->delete_event (idx + 2);
2918 533 : path->delete_event (idx + 1);
2919 533 : path->delete_event (idx);
2920 533 : changed = true;
2921 533 : idx--;
2922 533 : continue;
2923 533 : }
2924 :
2925 : /* Prune [..., call, return, ...] pairs
2926 : (for -fanalyzer-verbosity=0). */
2927 18731 : if (idx + 1 < (signed)path->num_events ()
2928 13965 : && path->get_checker_event (idx)->is_call_p ()
2929 19669 : && path->get_checker_event (idx + 1)->is_return_p ())
2930 : {
2931 4 : if (get_logger ())
2932 : {
2933 0 : label_text desc
2934 0 : (path->get_checker_event (idx)->get_desc
2935 0 : (*global_dc->get_reference_printer ()));
2936 0 : log ("filtering events %i-%i:"
2937 : " irrelevant call/return: %s",
2938 : idx, idx + 1, desc.get ());
2939 0 : }
2940 4 : path->delete_event (idx + 1);
2941 4 : path->delete_event (idx);
2942 4 : changed = true;
2943 4 : idx--;
2944 4 : continue;
2945 4 : }
2946 :
2947 18727 : idx--;
2948 : }
2949 :
2950 : }
2951 : while (changed);
2952 4386 : }
2953 :
2954 : /* Remove everything within [call point, IDX]. For consistency,
2955 : IDX should represent the return event of the frame to delete,
2956 : or if there is none it should be the last event of the frame.
2957 : After this function, IDX designates the event prior to calling
2958 : this frame. */
2959 :
2960 : static void
2961 0 : prune_frame (checker_path *path, int &idx)
2962 : {
2963 0 : gcc_assert (idx >= 0);
2964 0 : int nesting = 1;
2965 0 : if (path->get_checker_event (idx)->is_return_p ())
2966 0 : nesting = 0;
2967 0 : do
2968 : {
2969 0 : if (path->get_checker_event (idx)->is_call_p ())
2970 0 : nesting--;
2971 0 : else if (path->get_checker_event (idx)->is_return_p ())
2972 0 : nesting++;
2973 :
2974 0 : path->delete_event (idx--);
2975 0 : } while (idx >= 0 && nesting != 0);
2976 0 : }
2977 :
2978 : /* This function is called when fanalyzer-show-events-in-system-headers
2979 : is disabled and will prune the diagnostic of all events within a
2980 : system header, only keeping the entry and exit events to the header.
2981 : This should be called after diagnostic_manager::prune_interproc_events
2982 : so that successive events [system header call, system header return]
2983 : are preserved thereafter.
2984 :
2985 : Given a diagnostics path diving into a system header in the form
2986 : [
2987 : prefix events...,
2988 : system header call,
2989 : system header entry,
2990 : events within system headers...,
2991 : system header return,
2992 : suffix events...
2993 : ]
2994 :
2995 : then transforms it into
2996 : [
2997 : prefix events...,
2998 : system header call,
2999 : system header return,
3000 : suffix events...
3001 : ]. */
3002 :
3003 : void
3004 4384 : diagnostic_manager::prune_system_headers (checker_path *path) const
3005 : {
3006 4384 : int idx = (signed)path->num_events () - 1;
3007 20697 : while (idx >= 0)
3008 : {
3009 16313 : const checker_event *event = path->get_checker_event (idx);
3010 : /* Prune everything between
3011 : [..., system entry, (...), system return, ...]. */
3012 16313 : if (event->is_return_p ()
3013 16313 : && in_system_header_at (event->get_location ()))
3014 : {
3015 0 : int ret_idx = idx;
3016 0 : prune_frame (path, idx);
3017 :
3018 0 : if (get_logger ())
3019 : {
3020 0 : log ("filtering system headers events %i-%i:",
3021 : idx, ret_idx);
3022 : }
3023 : // Delete function entry within system headers.
3024 0 : if (idx >= 0)
3025 : {
3026 0 : event = path->get_checker_event (idx);
3027 0 : if (event->is_function_entry_p ()
3028 0 : && in_system_header_at (event->get_location ()))
3029 : {
3030 0 : if (get_logger ())
3031 : {
3032 0 : label_text desc
3033 0 : (event->get_desc (*global_dc->get_reference_printer ()));
3034 0 : log ("filtering event %i:"
3035 : "system header entry event: %s",
3036 : idx, desc.get ());
3037 0 : }
3038 :
3039 0 : path->delete_event (idx);
3040 : }
3041 : }
3042 : }
3043 :
3044 16313 : idx--;
3045 : }
3046 4384 : }
3047 :
3048 : /* Return true iff event IDX within PATH is on the same line as REF_EXP_LOC. */
3049 :
3050 : static bool
3051 2694 : same_line_as_p (const expanded_location &ref_exp_loc,
3052 : checker_path *path, unsigned idx)
3053 : {
3054 2694 : const checker_event *ev = path->get_checker_event (idx);
3055 2694 : expanded_location idx_exp_loc = expand_location (ev->get_location ());
3056 2694 : gcc_assert (ref_exp_loc.file);
3057 2694 : if (idx_exp_loc.file == nullptr)
3058 : return false;
3059 2671 : if (strcmp (ref_exp_loc.file, idx_exp_loc.file))
3060 : return false;
3061 2667 : return ref_exp_loc.line == idx_exp_loc.line;
3062 : }
3063 :
3064 : /* This path-readability optimization reduces the verbosity of compound
3065 : conditional statements (without needing to reconstruct the AST, which
3066 : has already been lost).
3067 :
3068 : For example, it converts:
3069 :
3070 : | 61 | if (cp[0] != '\0' && cp[0] != '#')
3071 : | | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3072 : | | | | |
3073 : | | | | (6) ...to here
3074 : | | | (7) following ‘true’ branch...
3075 : | | (5) following ‘true’ branch...
3076 : | 62 | {
3077 : | 63 | alias = cp++;
3078 : | | ~~~~
3079 : | | |
3080 : | | (8) ...to here
3081 :
3082 : into:
3083 :
3084 : | 61 | if (cp[0] != '\0' && cp[0] != '#')
3085 : | | ~
3086 : | | |
3087 : | | (5) following ‘true’ branch...
3088 : | 62 | {
3089 : | 63 | alias = cp++;
3090 : | | ~~~~
3091 : | | |
3092 : | | (6) ...to here
3093 :
3094 : by combining events 5-8 into new events 5-6.
3095 :
3096 : Find runs of consecutive (start_cfg_edge_event, end_cfg_edge_event) pairs
3097 : in which all events apart from the final end_cfg_edge_event are on the same
3098 : line, and for which either all the CFG edges are TRUE edges, or all are
3099 : FALSE edges.
3100 :
3101 : Consolidate each such run into a
3102 : (start_consolidated_cfg_edges_event, end_consolidated_cfg_edges_event)
3103 : pair. */
3104 :
3105 : void
3106 4386 : diagnostic_manager::consolidate_conditions (checker_path *path) const
3107 : {
3108 : /* Don't simplify edges if we're debugging them. */
3109 4386 : if (flag_analyzer_verbose_edges)
3110 : return;
3111 :
3112 11852 : for (int start_idx = 0;
3113 32385 : start_idx < (signed)path->num_events () - 1;
3114 : start_idx++)
3115 : {
3116 11852 : if (path->cfg_edge_pair_at_p (start_idx))
3117 : {
3118 2480 : const checker_event *old_start_ev
3119 2480 : = path->get_checker_event (start_idx);
3120 2480 : expanded_location start_exp_loc
3121 2480 : = expand_location (old_start_ev->get_location ());
3122 2480 : if (start_exp_loc.file == nullptr)
3123 2150 : continue;
3124 2480 : if (!same_line_as_p (start_exp_loc, path, start_idx + 1))
3125 2150 : continue;
3126 :
3127 : /* Are we looking for a run of all TRUE edges, or all FALSE edges? */
3128 330 : gcc_assert (old_start_ev->get_kind () == event_kind::start_cfg_edge);
3129 330 : const start_cfg_edge_event *old_start_cfg_ev
3130 : = (const start_cfg_edge_event *)old_start_ev;
3131 330 : bool edge_sense;
3132 330 : if (!old_start_cfg_ev->maybe_get_edge_sense (&edge_sense))
3133 0 : continue;
3134 :
3135 : /* Find a run of CFG start/end event pairs from
3136 : [start_idx, next_idx)
3137 : where all apart from the final event are on the same line,
3138 : and all are either TRUE or FALSE edges, matching the initial. */
3139 330 : int next_idx = start_idx + 2;
3140 330 : while (path->cfg_edge_pair_at_p (next_idx)
3141 414 : && same_line_as_p (start_exp_loc, path, next_idx))
3142 : {
3143 119 : const checker_event *iter_ev
3144 119 : = path->get_checker_event (next_idx);
3145 119 : gcc_assert (iter_ev->get_kind () == event_kind::start_cfg_edge);
3146 119 : const start_cfg_edge_event *iter_cfg_ev
3147 : = (const start_cfg_edge_event *)iter_ev;
3148 119 : bool iter_edge_sense;
3149 119 : if (!iter_cfg_ev->maybe_get_edge_sense (&iter_edge_sense))
3150 : break;
3151 113 : if (iter_edge_sense != edge_sense)
3152 : break;
3153 84 : next_idx += 2;
3154 : }
3155 :
3156 : /* If we have more than one pair in the run, consolidate. */
3157 330 : if (next_idx > start_idx + 2)
3158 : {
3159 79 : const checker_event *old_end_ev
3160 79 : = path->get_checker_event (next_idx - 1);
3161 79 : log ("consolidating CFG edge events %i-%i into %i-%i",
3162 : start_idx, next_idx - 1, start_idx, start_idx +1);
3163 79 : auto new_start_ev
3164 : = std::make_unique<start_consolidated_cfg_edges_event>
3165 79 : (event_loc_info (old_start_ev->get_location (),
3166 : old_start_ev->get_fndecl (),
3167 79 : old_start_ev->get_stack_depth ()),
3168 79 : edge_sense);
3169 79 : auto new_end_ev
3170 : = std::make_unique<end_consolidated_cfg_edges_event>
3171 79 : (event_loc_info (old_end_ev->get_location (),
3172 : old_end_ev->get_fndecl (),
3173 79 : old_end_ev->get_stack_depth ()));
3174 79 : path->replace_event (start_idx, std::move (new_start_ev));
3175 79 : path->replace_event (start_idx + 1, std::move (new_end_ev));
3176 79 : path->delete_events (start_idx + 2, next_idx - (start_idx + 2));
3177 79 : }
3178 : }
3179 : }
3180 : }
3181 :
3182 : /* Consolidate runs of consecutive unwind_event. */
3183 :
3184 : void
3185 4386 : diagnostic_manager::consolidate_unwind_events (checker_path *path) const
3186 : {
3187 : /* Don't simplify edges if we're debugging them. */
3188 4386 : if (flag_analyzer_verbose_edges)
3189 : return;
3190 :
3191 11846 : for (int start_idx = 0;
3192 32373 : start_idx < (signed)path->num_events () - 1;
3193 : start_idx++)
3194 : {
3195 : /* Find a run of consecutive unwind_event instances. */
3196 11846 : if (path->get_checker_event (start_idx)->get_kind ()
3197 : != event_kind::unwind)
3198 11837 : continue;
3199 9 : int iter_idx = start_idx + 1;
3200 15 : while (iter_idx < (int)path->num_events ())
3201 15 : if (path->get_checker_event (iter_idx)->get_kind ()
3202 : == event_kind::unwind)
3203 6 : ++iter_idx;
3204 : else
3205 : break;
3206 :
3207 : /* iter_idx should now be one after the last unwind_event in the run. */
3208 9 : const int last_idx = iter_idx - 1;
3209 9 : if (last_idx == start_idx)
3210 3 : continue;
3211 :
3212 6 : gcc_assert (last_idx > start_idx);
3213 :
3214 6 : log ("consolidating unwind events %i-%i into %i",
3215 : start_idx, last_idx, start_idx);
3216 :
3217 6 : unwind_event *first_event
3218 6 : = (unwind_event *)path->get_checker_event (start_idx);
3219 6 : const unwind_event *last_event
3220 6 : = (const unwind_event *)path->get_checker_event (last_idx);
3221 6 : first_event->m_num_frames += last_event->m_num_frames;
3222 6 : path->delete_events (start_idx + 1, last_idx - start_idx);
3223 : }
3224 : }
3225 :
3226 : /* Final pass of diagnostic_manager::prune_path.
3227 :
3228 : If all we're left with is in one function, then filter function entry
3229 : events. */
3230 :
3231 : void
3232 4386 : diagnostic_manager::finish_pruning (checker_path *path) const
3233 : {
3234 4386 : if (!path->interprocedural_p ())
3235 : {
3236 3599 : int idx = path->num_events () - 1;
3237 26403 : while (idx >= 0 && idx < (signed)path->num_events ())
3238 : {
3239 11402 : checker_event *base_event = path->get_checker_event (idx);
3240 11402 : if (base_event->get_kind () == event_kind::function_entry)
3241 : {
3242 3503 : log ("filtering event %i:"
3243 : " function entry for purely intraprocedural path", idx);
3244 3503 : path->delete_event (idx);
3245 : }
3246 11402 : idx--;
3247 : }
3248 : }
3249 4386 : }
3250 :
3251 : } // namespace ana
3252 :
3253 : #endif /* #if ENABLE_ANALYZER */
|