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