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