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