1	/* The analysis "engine".
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 "make-unique.h"
26	#include "tree.h"
27	#include "fold-const.h"
28	#include "gcc-rich-location.h"
29	#include "diagnostic-core.h"
30	#include "diagnostic-event-id.h"
31	#include "diagnostic-path.h"
32	#include "function.h"
33	#include "pretty-print.h"
34	#include "sbitmap.h"
35	#include "bitmap.h"
36	#include "ordered-hash-map.h"
37	#include "analyzer/analyzer.h"
38	#include "analyzer/analyzer-logging.h"
39	#include "analyzer/call-string.h"
40	#include "analyzer/program-point.h"
41	#include "analyzer/store.h"
42	#include "analyzer/region-model.h"
43	#include "analyzer/constraint-manager.h"
44	#include "analyzer/sm.h"
45	#include "analyzer/pending-diagnostic.h"
46	#include "analyzer/diagnostic-manager.h"
47	#include "cfg.h"
48	#include "basic-block.h"
49	#include "gimple.h"
50	#include "gimple-iterator.h"
51	#include "gimple-pretty-print.h"
52	#include "cgraph.h"
53	#include "digraph.h"
54	#include "analyzer/supergraph.h"
55	#include "analyzer/program-state.h"
56	#include "analyzer/exploded-graph.h"
57	#include "analyzer/analysis-plan.h"
58	#include "analyzer/checker-path.h"
59	#include "analyzer/state-purge.h"
60	#include "analyzer/bar-chart.h"
61	#include "analyzer/call-info.h"
62	#include <zlib.h>
63	#include "plugin.h"
64	#include "target.h"
65	#include <memory>
66	#include "stringpool.h"
67	#include "attribs.h"
68	#include "tree-dfa.h"
69	#include "analyzer/known-function-manager.h"
70	#include "analyzer/call-summary.h"
71
72	/* For an overview, see gcc/doc/analyzer.texi. */
73
74	#if ENABLE_ANALYZER
75
76	namespace ana {
77
78	/* class impl_region_model_context : public region_model_context. */
79
80	impl_region_model_context::
81	impl_region_model_context (exploded_graph &eg,
82	exploded_node *enode_for_diag,
83	const program_state *old_state,
84	program_state *new_state,
85	uncertainty_t *uncertainty,
86	path_context *path_ctxt,
87	const gimple *stmt,
88	stmt_finder *stmt_finder,
89	bool *out_could_have_done_work)
90	: m_eg (&eg), m_logger (eg.get_logger ()),
91	m_enode_for_diag (enode_for_diag),
92	m_old_state (old_state),
93	m_new_state (new_state),
94	m_stmt (stmt),
95	m_stmt_finder (stmt_finder),
96	m_ext_state (eg.get_ext_state ()),
97	m_uncertainty (uncertainty),
98	m_path_ctxt (path_ctxt),
99	m_out_could_have_done_work (out_could_have_done_work)
100	{
101	}
102
103	impl_region_model_context::
104	impl_region_model_context (program_state *state,
105	const extrinsic_state &ext_state,
106	uncertainty_t *uncertainty,
107	logger *logger)
108	: m_eg (NULL), m_logger (logger), m_enode_for_diag (NULL),
109	m_old_state (NULL),
110	m_new_state (state),
111	m_stmt (NULL),
112	m_stmt_finder (NULL),
113	m_ext_state (ext_state),
114	m_uncertainty (uncertainty),
115	m_path_ctxt (NULL),
116	m_out_could_have_done_work (nullptr)
117	{
118	}
119
120	bool
121	impl_region_model_context::warn (std::unique_ptr<pending_diagnostic> d,
122	const stmt_finder *custom_finder)
123	{
124	LOG_FUNC (get_logger ());
125	auto curr_stmt_finder = custom_finder ? custom_finder : m_stmt_finder;
126	if (m_stmt == NULL && curr_stmt_finder == NULL)
127	{
128	if (get_logger ())
129	get_logger ()->log (fmt: "rejecting diagnostic: no stmt");
130	return false;
131	}
132	if (m_eg)
133	{
134	bool terminate_path = d->terminate_path_p ();
135	pending_location ploc (m_enode_for_diag,
136	m_enode_for_diag->get_supernode (),
137	m_stmt,
138	curr_stmt_finder);
139	if (m_eg->get_diagnostic_manager ().add_diagnostic (ploc,
140	d: std::move (d)))
141	{
142	if (m_path_ctxt
143	&& terminate_path
144	&& flag_analyzer_suppress_followups)
145	m_path_ctxt->terminate_path ();
146	return true;
147	}
148	}
149	return false;
150	}
151
152	void
153	impl_region_model_context::add_note (std::unique_ptr<pending_note> pn)
154	{
155	LOG_FUNC (get_logger ());
156	if (m_eg)
157	m_eg->get_diagnostic_manager ().add_note (pn: std::move (pn));
158	}
159
160	void
161	impl_region_model_context::add_event (std::unique_ptr<checker_event> event)
162	{
163	LOG_FUNC (get_logger ());
164	if (m_eg)
165	m_eg->get_diagnostic_manager ().add_event (event: std::move (event));
166	}
167
168	void
169	impl_region_model_context::on_svalue_leak (const svalue *sval)
170
171	{
172	for (sm_state_map *smap : m_new_state->m_checker_states)
173	smap->on_svalue_leak (sval, ctxt: this);
174	}
175
176	void
177	impl_region_model_context::
178	on_liveness_change (const svalue_set &live_svalues,
179	const region_model *model)
180	{
181	for (sm_state_map *smap : m_new_state->m_checker_states)
182	smap->on_liveness_change (live_svalues, model, ext_state: m_ext_state, ctxt: this);
183	}
184
185	void
186	impl_region_model_context::on_unknown_change (const svalue *sval,
187	bool is_mutable)
188	{
189	if (!sval->can_have_associated_state_p ())
190	return;
191	for (sm_state_map *smap : m_new_state->m_checker_states)
192	smap->on_unknown_change (sval, is_mutable, ext_state: m_ext_state);
193	}
194
195	void
196	impl_region_model_context::on_escaped_function (tree fndecl)
197	{
198	m_eg->on_escaped_function (fndecl);
199	}
200
201	uncertainty_t *
202	impl_region_model_context::get_uncertainty ()
203	{
204	return m_uncertainty;
205	}
206
207	/* Purge state involving SVAL. The region_model has already been purged,
208	so we only need to purge other state in the program_state:
209	the sm-state. */
210
211	void
212	impl_region_model_context::purge_state_involving (const svalue *sval)
213	{
214	int i;
215	sm_state_map *smap;
216	FOR_EACH_VEC_ELT (m_new_state->m_checker_states, i, smap)
217	smap->purge_state_involving (sval, ext_state: m_ext_state);
218	}
219
220	void
221	impl_region_model_context::bifurcate (std::unique_ptr<custom_edge_info> info)
222	{
223	if (m_path_ctxt)
224	m_path_ctxt->bifurcate (info: std::move (info));
225	}
226
227	void
228	impl_region_model_context::terminate_path ()
229	{
230	if (m_path_ctxt)
231	return m_path_ctxt->terminate_path ();
232	}
233
234	/* struct setjmp_record. */
235
236	int
237	setjmp_record::cmp (const setjmp_record &rec1, const setjmp_record &rec2)
238	{
239	if (int cmp_enode = rec1.m_enode->m_index - rec2.m_enode->m_index)
240	return cmp_enode;
241	gcc_assert (&rec1 == &rec2);
242	return 0;
243	}
244
245	/* class setjmp_svalue : public svalue. */
246
247	/* Implementation of svalue::accept vfunc for setjmp_svalue. */
248
249	void
250	setjmp_svalue::accept (visitor *v) const
251	{
252	v->visit_setjmp_svalue (this);
253	}
254
255	/* Implementation of svalue::dump_to_pp vfunc for setjmp_svalue. */
256
257	void
258	setjmp_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
259	{
260	if (simple)
261	pp_printf (pp, "SETJMP(EN: %i)", get_enode_index ());
262	else
263	pp_printf (pp, "setjmp_svalue(EN%i)", get_enode_index ());
264	}
265
266	/* Get the index of the stored exploded_node. */
267
268	int
269	setjmp_svalue::get_enode_index () const
270	{
271	return m_setjmp_record.m_enode->m_index;
272	}
273
274	/* Concrete implementation of sm_context, wiring it up to the rest of this
275	file. */
276
277	class impl_sm_context : public sm_context
278	{
279	public:
280	impl_sm_context (exploded_graph &eg,
281	int sm_idx,
282	const state_machine &sm,
283	exploded_node *enode_for_diag,
284	const program_state *old_state,
285	program_state *new_state,
286	const sm_state_map *old_smap,
287	sm_state_map *new_smap,
288	path_context *path_ctxt,
289	const stmt_finder *stmt_finder = NULL,
290	bool unknown_side_effects = false)
291	: sm_context (sm_idx, sm),
292	m_logger (eg.get_logger ()),
293	m_eg (eg), m_enode_for_diag (enode_for_diag),
294	m_old_state (old_state), m_new_state (new_state),
295	m_old_smap (old_smap), m_new_smap (new_smap),
296	m_path_ctxt (path_ctxt),
297	m_stmt_finder (stmt_finder),
298	m_unknown_side_effects (unknown_side_effects)
299	{
300	}
301
302	logger *get_logger () const { return m_logger.get_logger (); }
303
304	tree get_fndecl_for_call (const gcall *call) final override
305	{
306	impl_region_model_context old_ctxt
307	(m_eg, m_enode_for_diag, NULL, NULL, NULL/*m_enode->get_state ()*/,
308	NULL, call);
309	region_model *model = m_new_state->m_region_model;
310	return model->get_fndecl_for_call (call, ctxt: &old_ctxt);
311	}
312
313	state_machine::state_t get_state (const gimple *stmt ATTRIBUTE_UNUSED,
314	tree var) final override
315	{
316	logger * const logger = get_logger ();
317	LOG_FUNC (logger);
318	/* Use NULL ctxt on this get_rvalue call to avoid triggering
319	uninitialized value warnings. */
320	const svalue *var_old_sval
321	= m_old_state->m_region_model->get_rvalue (expr: var, NULL);
322
323	state_machine::state_t current
324	= m_old_smap->get_state (sval: var_old_sval, ext_state: m_eg.get_ext_state ());
325	return current;
326	}
327	state_machine::state_t get_state (const gimple *stmt ATTRIBUTE_UNUSED,
328	const svalue *sval) final override
329	{
330	logger * const logger = get_logger ();
331	LOG_FUNC (logger);
332	state_machine::state_t current
333	= m_old_smap->get_state (sval, ext_state: m_eg.get_ext_state ());
334	return current;
335	}
336
337
338	void set_next_state (const gimple *,
339	tree var,
340	state_machine::state_t to,
341	tree origin) final override
342	{
343	logger * const logger = get_logger ();
344	LOG_FUNC (logger);
345	const svalue *var_new_sval
346	= m_new_state->m_region_model->get_rvalue (expr: var, NULL);
347	const svalue *origin_new_sval
348	= m_new_state->m_region_model->get_rvalue (expr: origin, NULL);
349
350	/* We use the new sval here to avoid issues with uninitialized values. */
351	state_machine::state_t current
352	= m_old_smap->get_state (sval: var_new_sval, ext_state: m_eg.get_ext_state ());
353	if (logger)
354	logger->log (fmt: "%s: state transition of %qE: %s -> %s",
355	m_sm.get_name (),
356	var,
357	current->get_name (),
358	to->get_name ());
359	m_new_smap->set_state (model: m_new_state->m_region_model, sval: var_new_sval,
360	state: to, origin: origin_new_sval, ext_state: m_eg.get_ext_state ());
361	}
362
363	void set_next_state (const gimple *stmt,
364	const svalue *sval,
365	state_machine::state_t to,
366	tree origin) final override
367	{
368	logger * const logger = get_logger ();
369	LOG_FUNC (logger);
370	impl_region_model_context old_ctxt
371	(m_eg, m_enode_for_diag, NULL, NULL, NULL/*m_enode->get_state ()*/,
372	NULL, stmt);
373
374	const svalue *origin_new_sval
375	= m_new_state->m_region_model->get_rvalue (expr: origin, NULL);
376
377	state_machine::state_t current
378	= m_old_smap->get_state (sval, ext_state: m_eg.get_ext_state ());
379	if (logger)
380	{
381	logger->start_log_line ();
382	logger->log_partial (fmt: "%s: state transition of ",
383	m_sm.get_name ());
384	sval->dump_to_pp (pp: logger->get_printer (), simple: true);
385	logger->log_partial (fmt: ": %s -> %s",
386	current->get_name (),
387	to->get_name ());
388	logger->end_log_line ();
389	}
390	m_new_smap->set_state (model: m_new_state->m_region_model, sval,
391	state: to, origin: origin_new_sval, ext_state: m_eg.get_ext_state ());
392	}
393
394	void warn (const supernode *snode, const gimple *stmt,
395	tree var,
396	std::unique_ptr<pending_diagnostic> d) final override
397	{
398	LOG_FUNC (get_logger ());
399	gcc_assert (d);
400	const svalue *var_old_sval
401	= m_old_state->m_region_model->get_rvalue (expr: var, NULL);
402	state_machine::state_t current
403	= (var
404	? m_old_smap->get_state (sval: var_old_sval, ext_state: m_eg.get_ext_state ())
405	: m_old_smap->get_global_state ());
406	bool terminate_path = d->terminate_path_p ();
407	pending_location ploc (m_enode_for_diag, snode, stmt, m_stmt_finder);
408	m_eg.get_diagnostic_manager ().add_diagnostic
409	(sm: &m_sm, ploc,
410	var, sval: var_old_sval, state: current, d: std::move (d));
411	if (m_path_ctxt
412	&& terminate_path
413	&& flag_analyzer_suppress_followups)
414	m_path_ctxt->terminate_path ();
415	}
416
417	void warn (const supernode *snode, const gimple *stmt,
418	const svalue *sval,
419	std::unique_ptr<pending_diagnostic> d) final override
420	{
421	LOG_FUNC (get_logger ());
422	gcc_assert (d);
423	state_machine::state_t current
424	= (sval
425	? m_old_smap->get_state (sval, ext_state: m_eg.get_ext_state ())
426	: m_old_smap->get_global_state ());
427	bool terminate_path = d->terminate_path_p ();
428	pending_location ploc (m_enode_for_diag, snode, stmt, m_stmt_finder);
429	m_eg.get_diagnostic_manager ().add_diagnostic
430	(sm: &m_sm, ploc,
431	NULL_TREE, sval, state: current, d: std::move (d));
432	if (m_path_ctxt
433	&& terminate_path
434	&& flag_analyzer_suppress_followups)
435	m_path_ctxt->terminate_path ();
436	}
437
438	/* Hook for picking more readable trees for SSA names of temporaries,
439	so that rather than e.g.
440	"double-free of '<unknown>'"
441	we can print:
442	"double-free of 'inbuf.data'". */
443
444	tree get_diagnostic_tree (tree expr) final override
445	{
446	/* Only for SSA_NAMEs of temporaries; otherwise, return EXPR, as it's
447	likely to be the least surprising tree to report. */
448	if (TREE_CODE (expr) != SSA_NAME)
449	return expr;
450	if (SSA_NAME_VAR (expr) != NULL)
451	return expr;
452
453	gcc_assert (m_new_state);
454	const svalue *sval = m_new_state->m_region_model->get_rvalue (expr, NULL);
455	/* Find trees for all regions storing the value. */
456	if (tree t = m_new_state->m_region_model->get_representative_tree (sval))
457	return t;
458	else
459	return expr;
460	}
461
462	tree get_diagnostic_tree (const svalue *sval) final override
463	{
464	return m_new_state->m_region_model->get_representative_tree (sval);
465	}
466
467	state_machine::state_t get_global_state () const final override
468	{
469	return m_old_state->m_checker_states[m_sm_idx]->get_global_state ();
470	}
471
472	void set_global_state (state_machine::state_t state) final override
473	{
474	m_new_state->m_checker_states[m_sm_idx]->set_global_state (state);
475	}
476
477	void clear_all_per_svalue_state () final override
478	{
479	m_new_state->m_checker_states[m_sm_idx]->clear_all_per_svalue_state ();
480	}
481
482	void on_custom_transition (custom_transition *transition) final override
483	{
484	transition->impl_transition (eg: &m_eg,
485	src_enode: const_cast<exploded_node *> (m_enode_for_diag),
486	sm_idx: m_sm_idx);
487	}
488
489	tree is_zero_assignment (const gimple *stmt) final override
490	{
491	const gassign *assign_stmt = dyn_cast <const gassign *> (p: stmt);
492	if (!assign_stmt)
493	return NULL_TREE;
494	impl_region_model_context old_ctxt
495	(m_eg, m_enode_for_diag, m_old_state, m_new_state, NULL, NULL, stmt);
496	if (const svalue *sval
497	= m_new_state->m_region_model->get_gassign_result (assign: assign_stmt,
498	ctxt: &old_ctxt))
499	if (tree cst = sval->maybe_get_constant ())
500	if (::zerop(cst))
501	return gimple_assign_lhs (gs: assign_stmt);
502	return NULL_TREE;
503	}
504
505	path_context *get_path_context () const final override
506	{
507	return m_path_ctxt;
508	}
509
510	bool unknown_side_effects_p () const final override
511	{
512	return m_unknown_side_effects;
513	}
514
515	const program_state *get_old_program_state () const final override
516	{
517	return m_old_state;
518	}
519
520	const program_state *get_new_program_state () const final override
521	{
522	return m_new_state;
523	}
524
525	log_user m_logger;
526	exploded_graph &m_eg;
527	exploded_node *m_enode_for_diag;
528	const program_state *m_old_state;
529	program_state *m_new_state;
530	const sm_state_map *m_old_smap;
531	sm_state_map *m_new_smap;
532	path_context *m_path_ctxt;
533	const stmt_finder *m_stmt_finder;
534
535	/* Are we handling an external function with unknown side effects? */
536	bool m_unknown_side_effects;
537	};
538
539	bool
540	impl_region_model_context::
541	get_state_map_by_name (const char *name,
542	sm_state_map **out_smap,
543	const state_machine **out_sm,
544	unsigned *out_sm_idx,
545	std::unique_ptr<sm_context> *out_sm_context)
546	{
547	if (!m_new_state)
548	return false;
549
550	unsigned sm_idx;
551	if (!m_ext_state.get_sm_idx_by_name (name, out: &sm_idx))
552	return false;
553
554	const state_machine *sm = &m_ext_state.get_sm (idx: sm_idx);
555	sm_state_map *new_smap = m_new_state->m_checker_states[sm_idx];
556
557	*out_smap = new_smap;
558	*out_sm = sm;
559	if (out_sm_idx)
560	*out_sm_idx = sm_idx;
561	if (out_sm_context)
562	{
563	const sm_state_map *old_smap = m_old_state->m_checker_states[sm_idx];
564	*out_sm_context
565	= make_unique<impl_sm_context> (args&: *m_eg,
566	args&: sm_idx,
567	args: *sm,
568	args&: m_enode_for_diag,
569	args&: m_old_state,
570	args&: m_new_state,
571	args&: old_smap,
572	args&: new_smap,
573	args&: m_path_ctxt,
574	args&: m_stmt_finder,
575	args: false);
576	}
577	return true;
578	}
579
580	/* Subclass of stmt_finder for finding the best stmt to report the leak at,
581	given the emission path. */
582
583	class leak_stmt_finder : public stmt_finder
584	{
585	public:
586	leak_stmt_finder (const exploded_graph &eg, tree var)
587	: m_eg (eg), m_var (var) {}
588
589	std::unique_ptr<stmt_finder> clone () const final override
590	{
591	return make_unique<leak_stmt_finder> (args: m_eg, args: m_var);
592	}
593
594	const gimple *find_stmt (const exploded_path &epath)
595	final override
596	{
597	logger * const logger = m_eg.get_logger ();
598	LOG_FUNC (logger);
599
600	if (m_var && TREE_CODE (m_var) == SSA_NAME)
601	{
602	/* Locate the final write to this SSA name in the path. */
603	const gimple *def_stmt = SSA_NAME_DEF_STMT (m_var);
604
605	int idx_of_def_stmt;
606	bool found = epath.find_stmt_backwards (search_stmt: def_stmt, out_idx: &idx_of_def_stmt);
607	if (!found)
608	goto not_found;
609
610	/* What was the next write to the underlying var
611	after the SSA name was set? (if any). */
612
613	for (unsigned idx = idx_of_def_stmt + 1;
614	idx < epath.m_edges.length ();
615	++idx)
616	{
617	const exploded_edge *eedge = epath.m_edges[idx];
618	if (logger)
619	logger->log (fmt: "eedge[%i]: EN %i -> EN %i",
620	idx,
621	eedge->m_src->m_index,
622	eedge->m_dest->m_index);
623	const exploded_node *dst_node = eedge->m_dest;
624	const program_point &dst_point = dst_node->get_point ();
625	const gimple *stmt = dst_point.get_stmt ();
626	if (!stmt)
627	continue;
628	if (const gassign *assign = dyn_cast <const gassign *> (p: stmt))
629	{
630	tree lhs = gimple_assign_lhs (gs: assign);
631	if (TREE_CODE (lhs) == SSA_NAME
632	&& SSA_NAME_VAR (lhs) == SSA_NAME_VAR (m_var))
633	return assign;
634	}
635	}
636	}
637
638	not_found:
639
640	/* Look backwards for the first statement with a location. */
641	int i;
642	const exploded_edge *eedge;
643	FOR_EACH_VEC_ELT_REVERSE (epath.m_edges, i, eedge)
644	{
645	if (logger)
646	logger->log (fmt: "eedge[%i]: EN %i -> EN %i",
647	i,
648	eedge->m_src->m_index,
649	eedge->m_dest->m_index);
650	const exploded_node *dst_node = eedge->m_dest;
651	const program_point &dst_point = dst_node->get_point ();
652	const gimple *stmt = dst_point.get_stmt ();
653	if (stmt)
654	if (get_pure_location (loc: stmt->location) != UNKNOWN_LOCATION)
655	return stmt;
656	}
657
658	gcc_unreachable ();
659	return NULL;
660	}
661
662	private:
663	const exploded_graph &m_eg;
664	tree m_var;
665	};
666
667	/* A measurement of how good EXPR is for presenting to the user, so
668	that e.g. we can say prefer printing
669	"leak of 'tmp.m_ptr'"
670	over:
671	"leak of '<unknown>'". */
672
673	static int
674	readability (const_tree expr)
675	{
676	/* Arbitrarily-chosen "high readability" value. */
677	const int HIGH_READABILITY = 65536;
678
679	gcc_assert (expr);
680	switch (TREE_CODE (expr))
681	{
682	case COMPONENT_REF:
683	case MEM_REF:
684	/* Impose a slight readability penalty relative to that of
685	operand 0. */
686	return readability (TREE_OPERAND (expr, 0)) - 16;
687
688	case SSA_NAME:
689	{
690	if (tree var = SSA_NAME_VAR (expr))
691	{
692	if (DECL_ARTIFICIAL (var))
693	{
694	/* If we have an SSA name for an artificial var,
695	only use it if it has a debug expr associated with
696	it that fixup_tree_for_diagnostic can use. */
697	if (VAR_P (var) && DECL_HAS_DEBUG_EXPR_P (var))
698	return readability (DECL_DEBUG_EXPR (var)) - 1;
699	}
700	else
701	{
702	/* Slightly favor the underlying var over the SSA name to
703	avoid having them compare equal. */
704	return readability (expr: var) - 1;
705	}
706	}
707	/* Avoid printing '<unknown>' for SSA names for temporaries. */
708	return -1;
709	}
710	break;
711
712	case PARM_DECL:
713	case VAR_DECL:
714	if (DECL_NAME (expr))
715	return HIGH_READABILITY;
716	else
717	/* We don't want to print temporaries. For example, the C FE
718	prints them as e.g. "<Uxxxx>" where "xxxx" is the low 16 bits
719	of the tree pointer (see pp_c_tree_decl_identifier). */
720	return -1;
721
722	case RESULT_DECL:
723	/* Printing "<return-value>" isn't ideal, but is less awful than
724	trying to print a temporary. */
725	return HIGH_READABILITY / 2;
726
727	case NOP_EXPR:
728	{
729	/* Impose a moderate readability penalty for casts. */
730	const int CAST_PENALTY = 32;
731	return readability (TREE_OPERAND (expr, 0)) - CAST_PENALTY;
732	}
733
734	case INTEGER_CST:
735	return HIGH_READABILITY;
736
737	default:
738	return 0;
739	}
740
741	return 0;
742	}
743
744	/* A qsort comparator for trees to sort them into most user-readable to
745	least user-readable. */
746
747	int
748	readability_comparator (const void *p1, const void *p2)
749	{
750	path_var pv1 = *(path_var const *)p1;
751	path_var pv2 = *(path_var const *)p2;
752
753	const int tree_r1 = readability (expr: pv1.m_tree);
754	const int tree_r2 = readability (expr: pv2.m_tree);
755
756	/* Favor items that are deeper on the stack and hence more recent;
757	this also favors locals over globals. */
758	const int COST_PER_FRAME = 64;
759	const int depth_r1 = pv1.m_stack_depth * COST_PER_FRAME;
760	const int depth_r2 = pv2.m_stack_depth * COST_PER_FRAME;
761
762	/* Combine the scores from the tree and from the stack depth.
763	This e.g. lets us have a slightly penalized cast in the most
764	recent stack frame "beat" an uncast value in an older stack frame. */
765	const int sum_r1 = tree_r1 + depth_r1;
766	const int sum_r2 = tree_r2 + depth_r2;
767	if (int cmp = sum_r2 - sum_r1)
768	return cmp;
769
770	/* Otherwise, more readable trees win. */
771	if (int cmp = tree_r2 - tree_r1)
772	return cmp;
773
774	/* Otherwise, if they have the same readability, then impose an
775	arbitrary deterministic ordering on them. */
776
777	if (int cmp = TREE_CODE (pv1.m_tree) - TREE_CODE (pv2.m_tree))
778	return cmp;
779
780	switch (TREE_CODE (pv1.m_tree))
781	{
782	default:
783	break;
784	case SSA_NAME:
785	if (int cmp = (SSA_NAME_VERSION (pv1.m_tree)
786	- SSA_NAME_VERSION (pv2.m_tree)))
787	return cmp;
788	break;
789	case PARM_DECL:
790	case VAR_DECL:
791	case RESULT_DECL:
792	if (int cmp = DECL_UID (pv1.m_tree) - DECL_UID (pv2.m_tree))
793	return cmp;
794	break;
795	}
796
797	/* TODO: We ought to find ways of sorting such cases. */
798	return 0;
799	}
800
801	/* Return true is SNODE is the EXIT node of a function, or is one
802	of the final snodes within its function.
803
804	Specifically, handle the final supernodes before the EXIT node,
805	for the case of clobbers that happen immediately before exiting.
806	We need a run of snodes leading to the return_p snode, where all edges are
807	intraprocedural, and every snode has just one successor.
808
809	We use this when suppressing leak reports at the end of "main". */
810
811	static bool
812	returning_from_function_p (const supernode *snode)
813	{
814	if (!snode)
815	return false;
816
817	unsigned count = 0;
818	const supernode *iter = snode;
819	while (true)
820	{
821	if (iter->return_p ())
822	return true;
823	if (iter->m_succs.length () != 1)
824	return false;
825	const superedge *sedge = iter->m_succs[0];
826	if (sedge->get_kind () != SUPEREDGE_CFG_EDGE)
827	return false;
828	iter = sedge->m_dest;
829
830	/* Impose a limit to ensure we terminate for pathological cases.
831
832	We only care about the final 3 nodes, due to cases like:
833	BB:
834	(clobber causing leak)
835
836	BB:
837	<label>:
838	return _val;
839
840	EXIT BB.*/
841	if (++count > 3)
842	return false;
843	}
844	}
845
846	/* Find the best tree for SVAL and call SM's on_leak vfunc with it.
847	If on_leak returns a pending_diagnostic, queue it up to be reported,
848	so that we potentially complain about a leak of SVAL in the given STATE. */
849
850	void
851	impl_region_model_context::on_state_leak (const state_machine &sm,
852	const svalue *sval,
853	state_machine::state_t state)
854	{
855	logger * const logger = get_logger ();
856	LOG_SCOPE (logger);
857	if (logger)
858	{
859	logger->start_log_line ();
860	logger->log_partial (fmt: "considering leak of ");
861	sval->dump_to_pp (pp: logger->get_printer (), simple: true);
862	logger->end_log_line ();
863	}
864
865	if (!m_eg)
866	return;
867
868	/* m_old_state also needs to be non-NULL so that the sm_ctxt can look
869	up the old state of SVAL. */
870	gcc_assert (m_old_state);
871
872	/* SVAL has leaked within the new state: it is not used by any reachable
873	regions.
874	We need to convert it back to a tree, but since it's likely no regions
875	use it, we have to find the "best" tree for it in the old_state. */
876	svalue_set visited;
877	path_var leaked_pv
878	= m_old_state->m_region_model->get_representative_path_var (sval,
879	visited: &visited);
880
881	/* Strip off top-level casts */
882	if (leaked_pv.m_tree && TREE_CODE (leaked_pv.m_tree) == NOP_EXPR)
883	leaked_pv.m_tree = TREE_OPERAND (leaked_pv.m_tree, 0);
884
885	/* This might be NULL; the pending_diagnostic subclasses need to cope
886	with this. */
887	tree leaked_tree = leaked_pv.m_tree;
888	if (logger)
889	{
890	if (leaked_tree)
891	logger->log (fmt: "best leaked_tree: %qE", leaked_tree);
892	else
893	logger->log (fmt: "best leaked_tree: NULL");
894	}
895
896	leak_stmt_finder stmt_finder (*m_eg, leaked_tree);
897	gcc_assert (m_enode_for_diag);
898
899	/* Don't complain about leaks when returning from "main". */
900	if (returning_from_function_p (snode: m_enode_for_diag->get_supernode ()))
901	{
902	tree fndecl = m_enode_for_diag->get_function ()->decl;
903	if (id_equal (DECL_NAME (fndecl), str: "main"))
904	{
905	if (logger)
906	logger->log (fmt: "not reporting leak from main");
907	return;
908	}
909	}
910
911	tree leaked_tree_for_diag = fixup_tree_for_diagnostic (leaked_tree);
912	std::unique_ptr<pending_diagnostic> pd = sm.on_leak (var: leaked_tree_for_diag);
913	if (pd)
914	{
915	pending_location ploc (m_enode_for_diag,
916	m_enode_for_diag->get_supernode (),
917	m_stmt,
918	&stmt_finder);
919	m_eg->get_diagnostic_manager ().add_diagnostic
920	(sm: &sm, ploc,
921	var: leaked_tree_for_diag, sval, state, d: std::move (pd));
922	}
923	}
924
925	/* Implementation of region_model_context::on_condition vfunc.
926	Notify all state machines about the condition, which could lead to
927	state transitions. */
928
929	void
930	impl_region_model_context::on_condition (const svalue *lhs,
931	enum tree_code op,
932	const svalue *rhs)
933	{
934	int sm_idx;
935	sm_state_map *smap;
936	FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
937	{
938	const state_machine &sm = m_ext_state.get_sm (idx: sm_idx);
939	impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
940	m_old_state, m_new_state,
941	m_old_state->m_checker_states[sm_idx],
942	m_new_state->m_checker_states[sm_idx],
943	m_path_ctxt);
944	sm.on_condition (sm_ctxt: &sm_ctxt,
945	node: (m_enode_for_diag
946	? m_enode_for_diag->get_supernode ()
947	: NULL),
948	stmt: m_stmt,
949	lhs, op, rhs);
950	}
951	}
952
953	/* Implementation of region_model_context::on_bounded_ranges vfunc.
954	Notify all state machines about the ranges, which could lead to
955	state transitions. */
956
957	void
958	impl_region_model_context::on_bounded_ranges (const svalue &sval,
959	const bounded_ranges &ranges)
960	{
961	int sm_idx;
962	sm_state_map *smap;
963	FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
964	{
965	const state_machine &sm = m_ext_state.get_sm (idx: sm_idx);
966	impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
967	m_old_state, m_new_state,
968	m_old_state->m_checker_states[sm_idx],
969	m_new_state->m_checker_states[sm_idx],
970	m_path_ctxt);
971	sm.on_bounded_ranges (sm_ctxt: &sm_ctxt,
972	node: (m_enode_for_diag
973	? m_enode_for_diag->get_supernode ()
974	: NULL),
975	stmt: m_stmt, sval, ranges);
976	}
977	}
978
979	/* Implementation of region_model_context::on_pop_frame vfunc.
980	Notify all state machines about the frame being popped, which
981	could lead to states being discarded. */
982
983	void
984	impl_region_model_context::on_pop_frame (const frame_region *frame_reg)
985	{
986	int sm_idx;
987	sm_state_map *smap;
988	FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
989	{
990	const state_machine &sm = m_ext_state.get_sm (idx: sm_idx);
991	sm.on_pop_frame (smap, frame_reg);
992	}
993	}
994
995	/* Implementation of region_model_context::on_phi vfunc.
996	Notify all state machines about the phi, which could lead to
997	state transitions. */
998
999	void
1000	impl_region_model_context::on_phi (const gphi *phi, tree rhs)
1001	{
1002	int sm_idx;
1003	sm_state_map *smap;
1004	FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
1005	{
1006	const state_machine &sm = m_ext_state.get_sm (idx: sm_idx);
1007	impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
1008	m_old_state, m_new_state,
1009	m_old_state->m_checker_states[sm_idx],
1010	m_new_state->m_checker_states[sm_idx],
1011	m_path_ctxt);
1012	sm.on_phi (sm_ctxt: &sm_ctxt, node: m_enode_for_diag->get_supernode (), phi, rhs);
1013	}
1014	}
1015
1016	/* Implementation of region_model_context::on_unexpected_tree_code vfunc.
1017	Mark the new state as being invalid for further exploration.
1018	TODO(stage1): introduce a warning for when this occurs. */
1019
1020	void
1021	impl_region_model_context::on_unexpected_tree_code (tree t,
1022	const dump_location_t &loc)
1023	{
1024	logger * const logger = get_logger ();
1025	if (logger)
1026	logger->log (fmt: "unhandled tree code: %qs in %qs at %s:%i",
1027	get_tree_code_name (TREE_CODE (t)),
1028	loc.get_impl_location ().m_function,
1029	loc.get_impl_location ().m_file,
1030	loc.get_impl_location ().m_line);
1031	if (m_new_state)
1032	m_new_state->m_valid = false;
1033	}
1034
1035	/* Implementation of region_model_context::maybe_did_work vfunc.
1036	Mark that "externally visible work" has occurred, and thus we
1037	shouldn't report an infinite loop here. */
1038
1039	void
1040	impl_region_model_context::maybe_did_work ()
1041	{
1042	if (m_out_could_have_done_work)
1043	*m_out_could_have_done_work = true;
1044	}
1045
1046	/* struct point_and_state. */
1047
1048	/* Assert that this object is sane. */
1049
1050	void
1051	point_and_state::validate (const extrinsic_state &ext_state) const
1052	{
1053	/* Skip this in a release build. */
1054	#if !CHECKING_P
1055	return;
1056	#endif
1057
1058	m_point.validate ();
1059
1060	m_state.validate (ext_state);
1061
1062	/* Verify that the callstring's model of the stack corresponds to that
1063	of the region_model. */
1064	/* They should have the same depth. */
1065	gcc_assert (m_point.get_stack_depth ()
1066	== m_state.m_region_model->get_stack_depth ());
1067	/* Check the functions in the callstring vs those in the frames
1068	at each depth. */
1069	for (const frame_region *iter_frame
1070	= m_state.m_region_model->get_current_frame ();
1071	iter_frame; iter_frame = iter_frame->get_calling_frame ())
1072	{
1073	int index = iter_frame->get_index ();
1074	gcc_assert (m_point.get_function_at_depth (index)
1075	== &iter_frame->get_function ());
1076	}
1077	}
1078
1079	/* Subroutine of print_enode_indices: print a run of indices from START_IDX
1080	to END_IDX to PP, using and updating *FIRST_RUN. */
1081
1082	static void
1083	print_run (pretty_printer *pp, int start_idx, int end_idx,
1084	bool *first_run)
1085	{
1086	if (!(*first_run))
1087	pp_string (pp, ", ");
1088	*first_run = false;
1089	if (start_idx == end_idx)
1090	pp_printf (pp, "EN: %i", start_idx);
1091	else
1092	pp_printf (pp, "EN: %i-%i", start_idx, end_idx);
1093	}
1094
1095	/* Print the indices within ENODES to PP, collecting them as
1096	runs/singletons e.g. "EN: 4-7, EN: 20-23, EN: 42". */
1097
1098	static void
1099	print_enode_indices (pretty_printer *pp,
1100	const auto_vec<exploded_node *> &enodes)
1101	{
1102	int cur_start_idx = -1;
1103	int cur_finish_idx = -1;
1104	bool first_run = true;
1105	unsigned i;
1106	exploded_node *enode;
1107	FOR_EACH_VEC_ELT (enodes, i, enode)
1108	{
1109	if (cur_start_idx == -1)
1110	{
1111	gcc_assert (cur_finish_idx == -1);
1112	cur_start_idx = cur_finish_idx = enode->m_index;
1113	}
1114	else
1115	{
1116	if (enode->m_index == cur_finish_idx + 1)
1117	/* Continuation of a run. */
1118	cur_finish_idx = enode->m_index;
1119	else
1120	{
1121	/* Finish existing run, start a new one. */
1122	gcc_assert (cur_start_idx >= 0);
1123	gcc_assert (cur_finish_idx >= 0);
1124	print_run (pp, start_idx: cur_start_idx, end_idx: cur_finish_idx,
1125	first_run: &first_run);
1126	cur_start_idx = cur_finish_idx = enode->m_index;
1127	}
1128	}
1129	}
1130	/* Finish any existing run. */
1131	if (cur_start_idx >= 0)
1132	{
1133	gcc_assert (cur_finish_idx >= 0);
1134	print_run (pp, start_idx: cur_start_idx, end_idx: cur_finish_idx,
1135	first_run: &first_run);
1136	}
1137	}
1138
1139	/* struct eg_traits::dump_args_t. */
1140
1141	/* The <FILENAME>.eg.dot output can quickly become unwieldy if we show
1142	full details for all enodes (both in terms of CPU time to render it,
1143	and in terms of being meaningful to a human viewing it).
1144
1145	If we show just the IDs then the resulting graph is usually viewable,
1146	but then we have to keep switching back and forth between the .dot
1147	view and other dumps.
1148
1149	This function implements a heuristic for showing detail at the enodes
1150	that (we hope) matter, and just the ID at other enodes, fixing the CPU
1151	usage of the .dot viewer, and drawing the attention of the viewer
1152	to these enodes.
1153
1154	Return true if ENODE should be shown in detail in .dot output.
1155	Return false if no detail should be shown for ENODE. */
1156
1157	bool
1158	eg_traits::dump_args_t::show_enode_details_p (const exploded_node &enode) const
1159	{
1160	/* If the number of exploded nodes isn't too large, we may as well show
1161	all enodes in full detail in the .dot output. */
1162	if (m_eg.m_nodes.length ()
1163	<= (unsigned) param_analyzer_max_enodes_for_full_dump)
1164	return true;
1165
1166	/* Otherwise, assume that what's most interesting are state explosions,
1167	and thus the places where this happened.
1168	Expand enodes at program points where we hit the per-enode limit, so we
1169	can investigate what exploded. */
1170	const per_program_point_data *per_point_data
1171	= m_eg.get_per_program_point_data (enode.get_point ());
1172	return per_point_data->m_excess_enodes > 0;
1173	}
1174
1175	/* class exploded_node : public dnode<eg_traits>. */
1176
1177	const char *
1178	exploded_node::status_to_str (enum status s)
1179	{
1180	switch (s)
1181	{
1182	default: gcc_unreachable ();
1183	case STATUS_WORKLIST: return "WORKLIST";
1184	case STATUS_PROCESSED: return "PROCESSED";
1185	case STATUS_MERGER: return "MERGER";
1186	case STATUS_BULK_MERGED: return "BULK_MERGED";
1187	}
1188	}
1189
1190	/* exploded_node's ctor. */
1191
1192	exploded_node::exploded_node (const point_and_state &ps,
1193	int index)
1194	: m_ps (ps), m_status (STATUS_WORKLIST), m_index (index),
1195	m_num_processed_stmts (0)
1196	{
1197	gcc_checking_assert (ps.get_state ().m_region_model->canonicalized_p ());
1198	}
1199
1200	/* Get the stmt that was processed in this enode at index IDX.
1201	IDX is an index within the stmts processed at this enode, rather
1202	than within those of the supernode. */
1203
1204	const gimple *
1205	exploded_node::get_processed_stmt (unsigned idx) const
1206	{
1207	gcc_assert (idx < m_num_processed_stmts);
1208	const program_point &point = get_point ();
1209	gcc_assert (point.get_kind () == PK_BEFORE_STMT);
1210	const supernode *snode = get_supernode ();
1211	const unsigned int point_stmt_idx = point.get_stmt_idx ();
1212	const unsigned int idx_within_snode = point_stmt_idx + idx;
1213	const gimple *stmt = snode->m_stmts[idx_within_snode];
1214	return stmt;
1215	}
1216
1217	/* For use by dump_dot, get a value for the .dot "fillcolor" attribute.
1218	Colorize by sm-state, to make it easier to see how sm-state propagates
1219	through the exploded_graph. */
1220
1221	const char *
1222	exploded_node::get_dot_fillcolor () const
1223	{
1224	const program_state &state = get_state ();
1225
1226	/* We want to be able to easily distinguish the no-sm-state case,
1227	and to be able to distinguish cases where there's a single state
1228	from each other.
1229
1230	Sum the sm_states, and use the result to choose from a table,
1231	modulo table-size, special-casing the "no sm-state" case. */
1232	int total_sm_state = 0;
1233	int i;
1234	sm_state_map *smap;
1235	FOR_EACH_VEC_ELT (state.m_checker_states, i, smap)
1236	{
1237	for (sm_state_map::iterator_t iter = smap->begin ();
1238	iter != smap->end ();
1239	++iter)
1240	total_sm_state += (*iter).second.m_state->get_id ();
1241	total_sm_state += smap->get_global_state ()->get_id ();
1242	}
1243
1244	if (total_sm_state > 0)
1245	{
1246	/* An arbitrarily-picked collection of light colors. */
1247	const char * const colors[]
1248	= {"azure", "coral", "cornsilk", "lightblue", "yellow",
1249	"honeydew", "lightpink", "lightsalmon", "palegreen1",
1250	"wheat", "seashell"};
1251	const int num_colors = ARRAY_SIZE (colors);
1252	return colors[total_sm_state % num_colors];
1253	}
1254	else
1255	/* No sm-state. */
1256	return "lightgrey";
1257	}
1258
1259	/* Implementation of dnode::dump_dot vfunc for exploded_node. */
1260
1261	void
1262	exploded_node::dump_dot (graphviz_out *gv, const dump_args_t &args) const
1263	{
1264	pretty_printer *pp = gv->get_pp ();
1265
1266	dump_dot_id (pp);
1267	pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
1268	get_dot_fillcolor ());
1269	pp_write_text_to_stream (pp);
1270
1271	pp_printf (pp, "EN: %i", m_index);
1272	if (m_status == STATUS_MERGER)
1273	pp_string (pp, " (merger)");
1274	else if (m_status == STATUS_BULK_MERGED)
1275	pp_string (pp, " (bulk merged)");
1276	pp_newline (pp);
1277
1278	if (args.show_enode_details_p (enode: *this))
1279	{
1280	format f (true);
1281	m_ps.get_point ().print (pp, f);
1282	pp_newline (pp);
1283
1284	const extrinsic_state &ext_state = args.m_eg.get_ext_state ();
1285	const program_state &state = m_ps.get_state ();
1286	state.dump_to_pp (ext_state, simple: false, multiline: true, pp);
1287	pp_newline (pp);
1288
1289	dump_processed_stmts (pp);
1290	}
1291
1292	dump_saved_diagnostics (pp);
1293
1294	args.dump_extra_info (this, pp);
1295
1296	pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
1297
1298	pp_string (pp, "\"];\n\n");
1299
1300	/* It can be hard to locate the saved diagnostics as text within the
1301	enode nodes, so add extra nodes to the graph for each saved_diagnostic,
1302	highlighted in red.
1303	Compare with dump_saved_diagnostics. */
1304	{
1305	unsigned i;
1306	const saved_diagnostic *sd;
1307	FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
1308	{
1309	sd->dump_as_dot_node (pp);
1310
1311	/* Add edge connecting this enode to the saved_diagnostic. */
1312	dump_dot_id (pp);
1313	pp_string (pp, " -> ");
1314	sd->dump_dot_id (pp);
1315	pp_string (pp, " [style=\"dotted\" arrowhead=\"none\"];");
1316	pp_newline (pp);
1317	}
1318	}
1319
1320	pp_flush (pp);
1321	}
1322
1323	/* Show any stmts that were processed within this enode,
1324	and their index within the supernode. */
1325	void
1326	exploded_node::dump_processed_stmts (pretty_printer *pp) const
1327	{
1328	if (m_num_processed_stmts > 0)
1329	{
1330	const program_point &point = get_point ();
1331	gcc_assert (point.get_kind () == PK_BEFORE_STMT);
1332	const supernode *snode = get_supernode ();
1333	const unsigned int point_stmt_idx = point.get_stmt_idx ();
1334
1335	pp_printf (pp, "stmts: %i", m_num_processed_stmts);
1336	pp_newline (pp);
1337	for (unsigned i = 0; i < m_num_processed_stmts; i++)
1338	{
1339	const unsigned int idx_within_snode = point_stmt_idx + i;
1340	const gimple *stmt = snode->m_stmts[idx_within_snode];
1341	pp_printf (pp, " %i: ", idx_within_snode);
1342	pp_gimple_stmt_1 (pp, stmt, 0, (dump_flags_t)0);
1343	pp_newline (pp);
1344	}
1345	}
1346	}
1347
1348	/* Dump any saved_diagnostics at this enode to PP. */
1349
1350	void
1351	exploded_node::dump_saved_diagnostics (pretty_printer *pp) const
1352	{
1353	unsigned i;
1354	const saved_diagnostic *sd;
1355	FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
1356	{
1357	pp_printf (pp, "DIAGNOSTIC: %s (sd: %i)",
1358	sd->m_d->get_kind (), sd->get_index ());
1359	pp_newline (pp);
1360	}
1361	}
1362
1363	/* Dump this to PP in a form suitable for use as an id in .dot output. */
1364
1365	void
1366	exploded_node::dump_dot_id (pretty_printer *pp) const
1367	{
1368	pp_printf (pp, "exploded_node_%i", m_index);
1369	}
1370
1371	/* Dump a multiline representation of this node to PP. */
1372
1373	void
1374	exploded_node::dump_to_pp (pretty_printer *pp,
1375	const extrinsic_state &ext_state) const
1376	{
1377	pp_printf (pp, "EN: %i", m_index);
1378	pp_newline (pp);
1379
1380	format f (true);
1381	m_ps.get_point ().print (pp, f);
1382	pp_newline (pp);
1383
1384	m_ps.get_state ().dump_to_pp (ext_state, simple: false, multiline: true, pp);
1385	pp_newline (pp);
1386	}
1387
1388	/* Dump a multiline representation of this node to FILE. */
1389
1390	void
1391	exploded_node::dump (FILE *fp,
1392	const extrinsic_state &ext_state) const
1393	{
1394	pretty_printer pp;
1395	pp_format_decoder (&pp) = default_tree_printer;
1396	pp_show_color (&pp) = pp_show_color (global_dc->printer);
1397	pp.buffer->stream = fp;
1398	dump_to_pp (pp: &pp, ext_state);
1399	pp_flush (&pp);
1400	}
1401
1402	/* Dump a multiline representation of this node to stderr. */
1403
1404	DEBUG_FUNCTION void
1405	exploded_node::dump (const extrinsic_state &ext_state) const
1406	{
1407	dump (stderr, ext_state);
1408	}
1409
1410	/* Return a new json::object of the form
1411	{"point" : object for program_point,
1412	"state" : object for program_state,
1413	"status" : str,
1414	"idx" : int,
1415	"processed_stmts" : int}. */
1416
1417	json::object *
1418	exploded_node::to_json (const extrinsic_state &ext_state) const
1419	{
1420	json::object *enode_obj = new json::object ();
1421
1422	enode_obj->set (key: "point", v: get_point ().to_json ());
1423	enode_obj->set (key: "state", v: get_state ().to_json (ext_state));
1424	enode_obj->set (key: "status", v: new json::string (status_to_str (s: m_status)));
1425	enode_obj->set (key: "idx", v: new json::integer_number (m_index));
1426	enode_obj->set (key: "processed_stmts",
1427	v: new json::integer_number (m_num_processed_stmts));
1428
1429	return enode_obj;
1430	}
1431
1432	} // namespace ana
1433
1434	/* Return true if FNDECL has a gimple body. */
1435	// TODO: is there a pre-canned way to do this?
1436
1437	bool
1438	fndecl_has_gimple_body_p (tree fndecl)
1439	{
1440	if (fndecl == NULL_TREE)
1441	return false;
1442
1443	cgraph_node *n = cgraph_node::get (decl: fndecl);
1444	if (!n)
1445	return false;
1446
1447	return n->has_gimple_body_p ();
1448	}
1449
1450	namespace ana {
1451
1452	/* Modify STATE in place, applying the effects of the stmt at this node's
1453	point. */
1454
1455	exploded_node::on_stmt_flags
1456	exploded_node::on_stmt (exploded_graph &eg,
1457	const supernode *snode,
1458	const gimple *stmt,
1459	program_state *state,
1460	uncertainty_t *uncertainty,
1461	bool *out_could_have_done_work,
1462	path_context *path_ctxt)
1463	{
1464	logger *logger = eg.get_logger ();
1465	LOG_SCOPE (logger);
1466	if (logger)
1467	{
1468	logger->start_log_line ();
1469	pp_gimple_stmt_1 (logger->get_printer (), stmt, 0, (dump_flags_t)0);
1470	logger->end_log_line ();
1471	}
1472
1473	/* Update input_location in case of ICE: make it easier to track down which
1474	source construct we're failing to handle. */
1475	input_location = stmt->location;
1476
1477	gcc_assert (state->m_region_model);
1478
1479	/* Preserve the old state. It is used here for looking
1480	up old checker states, for determining state transitions, and
1481	also within impl_region_model_context and impl_sm_context for
1482	going from tree to svalue_id. */
1483	const program_state old_state (*state);
1484
1485	impl_region_model_context ctxt (eg, this,
1486	&old_state, state, uncertainty,
1487	path_ctxt, stmt, nullptr,
1488	out_could_have_done_work);
1489
1490	/* Handle call summaries here. */
1491	if (cgraph_edge *cgedge
1492	= supergraph_call_edge (fun: snode->get_function (), stmt))
1493	if (eg.get_analysis_plan ().use_summary_p (edge: cgedge))
1494	{
1495	function *called_fn = get_ultimate_function_for_cgraph_edge (edge: cgedge);
1496	per_function_data *called_fn_data
1497	= eg.get_per_function_data (called_fn);
1498	if (called_fn_data)
1499	{
1500	gcc_assert (called_fn);
1501	return replay_call_summaries (eg,
1502	snode,
1503	call_stmt: as_a <const gcall *> (p: stmt),
1504	state,
1505	path_ctxt,
1506	called_fn: *called_fn,
1507	called_fn_data&: *called_fn_data,
1508	ctxt: &ctxt);
1509	}
1510	}
1511
1512	bool unknown_side_effects = false;
1513	bool terminate_path = false;
1514
1515	on_stmt_pre (eg, stmt, state, out_terminate_path: &terminate_path,
1516	out_unknown_side_effects: &unknown_side_effects, ctxt: &ctxt);
1517
1518	if (terminate_path)
1519	return on_stmt_flags::terminate_path ();
1520
1521	int sm_idx;
1522	sm_state_map *smap;
1523	FOR_EACH_VEC_ELT (old_state.m_checker_states, sm_idx, smap)
1524	{
1525	const state_machine &sm = eg.get_ext_state ().get_sm (idx: sm_idx);
1526	const sm_state_map *old_smap
1527	= old_state.m_checker_states[sm_idx];
1528	sm_state_map *new_smap = state->m_checker_states[sm_idx];
1529	impl_sm_context sm_ctxt (eg, sm_idx, sm, this, &old_state, state,
1530	old_smap, new_smap, path_ctxt, NULL,
1531	unknown_side_effects);
1532
1533	/* Allow the state_machine to handle the stmt. */
1534	if (sm.on_stmt (sm_ctxt: &sm_ctxt, node: snode, stmt))
1535	unknown_side_effects = false;
1536	}
1537
1538	if (path_ctxt->terminate_path_p ())
1539	return on_stmt_flags::terminate_path ();
1540
1541	on_stmt_post (stmt, state, unknown_side_effects, ctxt: &ctxt);
1542
1543	return on_stmt_flags ();
1544	}
1545
1546	/* Handle the pre-sm-state part of STMT, modifying STATE in-place.
1547	Write true to *OUT_TERMINATE_PATH if the path should be terminated.
1548	Write true to *OUT_UNKNOWN_SIDE_EFFECTS if the stmt has unknown
1549	side effects. */
1550
1551	void
1552	exploded_node::on_stmt_pre (exploded_graph &eg,
1553	const gimple *stmt,
1554	program_state *state,
1555	bool *out_terminate_path,
1556	bool *out_unknown_side_effects,
1557	region_model_context *ctxt)
1558	{
1559	/* Handle special-case calls that require the full program_state. */
1560	if (const gcall *call = dyn_cast <const gcall *> (p: stmt))
1561	{
1562	if (is_special_named_call_p (call, funcname: "__analyzer_dump", num_args: 0))
1563	{
1564	/* Handle the builtin "__analyzer_dump" by dumping state
1565	to stderr. */
1566	state->dump (ext_state: eg.get_ext_state (), simple: true);
1567	return;
1568	}
1569	else if (is_special_named_call_p (call, funcname: "__analyzer_dump_state", num_args: 2))
1570	{
1571	state->impl_call_analyzer_dump_state (call, ext_state: eg.get_ext_state (),
1572	ctxt);
1573	return;
1574	}
1575	else if (is_setjmp_call_p (call))
1576	{
1577	state->m_region_model->on_setjmp (stmt: call, enode: this, ctxt);
1578	if (ctxt)
1579	ctxt->maybe_did_work ();
1580	return;
1581	}
1582	else if (is_longjmp_call_p (call))
1583	{
1584	on_longjmp (eg, call, new_state: state, ctxt);
1585	*out_terminate_path = true;
1586	if (ctxt)
1587	ctxt->maybe_did_work ();
1588	return;
1589	}
1590	}
1591
1592	/* Otherwise, defer to m_region_model. */
1593	state->m_region_model->on_stmt_pre (stmt,
1594	out_unknown_side_effects,
1595	ctxt);
1596	}
1597
1598	/* Handle the post-sm-state part of STMT, modifying STATE in-place. */
1599
1600	void
1601	exploded_node::on_stmt_post (const gimple *stmt,
1602	program_state *state,
1603	bool unknown_side_effects,
1604	region_model_context *ctxt)
1605	{
1606	if (const gcall *call = dyn_cast <const gcall *> (p: stmt))
1607	state->m_region_model->on_call_post (stmt: call, unknown_side_effects, ctxt);
1608	}
1609
1610	/* A concrete call_info subclass representing a replay of a call summary. */
1611
1612	class call_summary_edge_info : public call_info
1613	{
1614	public:
1615	call_summary_edge_info (const call_details &cd,
1616	const function &called_fn,
1617	call_summary *summary,
1618	const extrinsic_state &ext_state)
1619	: call_info (cd, called_fn),
1620	m_called_fn (called_fn),
1621	m_summary (summary),
1622	m_ext_state (ext_state)
1623	{}
1624
1625	bool update_state (program_state *state,
1626	const exploded_edge *,
1627	region_model_context *ctxt) const final override
1628	{
1629	/* Update STATE based on summary_end_state. */
1630	call_details cd (get_call_details (model: state->m_region_model, ctxt));
1631	call_summary_replay r (cd, m_called_fn, m_summary, m_ext_state);
1632	const program_state &summary_end_state = m_summary->get_state ();
1633	return state->replay_call_summary (r, summary: summary_end_state);
1634	}
1635
1636	bool update_model (region_model *model,
1637	const exploded_edge *,
1638	region_model_context *ctxt) const final override
1639	{
1640	/* Update STATE based on summary_end_state. */
1641	call_details cd (get_call_details (model, ctxt));
1642	call_summary_replay r (cd, m_called_fn, m_summary, m_ext_state);
1643	const program_state &summary_end_state = m_summary->get_state ();
1644	model->replay_call_summary (r, summary: *summary_end_state.m_region_model);
1645	return true;
1646	}
1647
1648	label_text get_desc (bool /*can_colorize*/) const final override
1649	{
1650	return m_summary->get_desc ();
1651	}
1652
1653	private:
1654	const function &m_called_fn;
1655	call_summary *m_summary;
1656	const extrinsic_state &m_ext_state;
1657	};
1658
1659	/* Use PATH_CTXT to bifurcate, which when handled will add custom edges
1660	for a replay of the various feasible summaries in CALLED_FN_DATA. */
1661
1662	exploded_node::on_stmt_flags
1663	exploded_node::replay_call_summaries (exploded_graph &eg,
1664	const supernode *snode,
1665	const gcall *call_stmt,
1666	program_state *state,
1667	path_context *path_ctxt,
1668	const function &called_fn,
1669	per_function_data &called_fn_data,
1670	region_model_context *ctxt)
1671	{
1672	logger *logger = eg.get_logger ();
1673	LOG_SCOPE (logger);
1674
1675	/* Each summary will call bifurcate on the PATH_CTXT. */
1676	for (auto summary : called_fn_data.m_summaries)
1677	replay_call_summary (eg, snode, call_stmt, state,
1678	path_ctxt, called_fn, summary, ctxt);
1679	path_ctxt->terminate_path ();
1680
1681	return on_stmt_flags ();
1682	}
1683
1684	/* Use PATH_CTXT to bifurcate, which when handled will add a
1685	custom edge for a replay of SUMMARY, if the summary's
1686	conditions are feasible based on the current state. */
1687
1688	void
1689	exploded_node::replay_call_summary (exploded_graph &eg,
1690	const supernode *snode,
1691	const gcall *call_stmt,
1692	program_state *old_state,
1693	path_context *path_ctxt,
1694	const function &called_fn,
1695	call_summary *summary,
1696	region_model_context *ctxt)
1697	{
1698	logger *logger = eg.get_logger ();
1699	LOG_SCOPE (logger);
1700	gcc_assert (snode);
1701	gcc_assert (call_stmt);
1702	gcc_assert (old_state);
1703	gcc_assert (summary);
1704
1705	if (logger)
1706	logger->log (fmt: "using %s as summary for call to %qE from %qE",
1707	summary->get_desc ().get (),
1708	called_fn.decl,
1709	snode->get_function ()->decl);
1710	const extrinsic_state &ext_state = eg.get_ext_state ();
1711	const program_state &summary_end_state = summary->get_state ();
1712	if (logger)
1713	{
1714	pretty_printer *pp = logger->get_printer ();
1715
1716	logger->start_log_line ();
1717	pp_string (pp, "callsite state: ");
1718	old_state->dump_to_pp (ext_state, simple: true, multiline: false, pp);
1719	logger->end_log_line ();
1720
1721	logger->start_log_line ();
1722	pp_string (pp, "summary end state: ");
1723	summary_end_state.dump_to_pp (ext_state, simple: true, multiline: false, pp);
1724	logger->end_log_line ();
1725	}
1726
1727	program_state new_state (*old_state);
1728
1729	call_details cd (call_stmt, new_state.m_region_model, ctxt);
1730	call_summary_replay r (cd, called_fn, summary, ext_state);
1731
1732	if (path_ctxt)
1733	path_ctxt->bifurcate (info: make_unique<call_summary_edge_info> (args&: cd,
1734	args: called_fn,
1735	args&: summary,
1736	args: ext_state));
1737	}
1738
1739
1740	/* Consider the effect of following superedge SUCC from this node.
1741
1742	Return true if it's feasible to follow the edge, or false
1743	if it's infeasible.
1744
1745	Examples: if it's the "true" branch within
1746	a CFG and we know the conditional is false, we know it's infeasible.
1747	If it's one of multiple interprocedual "return" edges, then only
1748	the edge back to the most recent callsite is feasible.
1749
1750	Update NEXT_STATE accordingly (e.g. to record that a condition was
1751	true or false, or that the NULL-ness of a pointer has been checked,
1752	pushing/popping stack frames, etc).
1753
1754	Update NEXT_POINT accordingly (updating the call string). */
1755
1756	bool
1757	exploded_node::on_edge (exploded_graph &eg,
1758	const superedge *succ,
1759	program_point *next_point,
1760	program_state *next_state,
1761	uncertainty_t *uncertainty)
1762	{
1763	LOG_FUNC (eg.get_logger ());
1764
1765	if (!next_point->on_edge (eg, succ))
1766	return false;
1767
1768	if (!next_state->on_edge (eg, enode: this, succ, uncertainty))
1769	return false;
1770
1771	return true;
1772	}
1773
1774	/* Verify that the stack at LONGJMP_POINT is still valid, given a call
1775	to "setjmp" at SETJMP_POINT - the stack frame that "setjmp" was
1776	called in must still be valid.
1777
1778	Caveat: this merely checks the call_strings in the points; it doesn't
1779	detect the case where a frame returns and is then called again. */
1780
1781	static bool
1782	valid_longjmp_stack_p (const program_point &longjmp_point,
1783	const program_point &setjmp_point)
1784	{
1785	const call_string &cs_at_longjmp = longjmp_point.get_call_string ();
1786	const call_string &cs_at_setjmp = setjmp_point.get_call_string ();
1787
1788	if (cs_at_longjmp.length () < cs_at_setjmp.length ())
1789	return false;
1790
1791	/* Check that the call strings match, up to the depth of the
1792	setjmp point. */
1793	for (unsigned depth = 0; depth < cs_at_setjmp.length (); depth++)
1794	if (cs_at_longjmp[depth] != cs_at_setjmp[depth])
1795	return false;
1796
1797	return true;
1798	}
1799
1800	/* A pending_diagnostic subclass for complaining about bad longjmps,
1801	where the enclosing function of the "setjmp" has returned (and thus
1802	the stack frame no longer exists). */
1803
1804	class stale_jmp_buf : public pending_diagnostic_subclass<stale_jmp_buf>
1805	{
1806	public:
1807	stale_jmp_buf (const gcall *setjmp_call, const gcall *longjmp_call,
1808	const program_point &setjmp_point)
1809	: m_setjmp_call (setjmp_call), m_longjmp_call (longjmp_call),
1810	m_setjmp_point (setjmp_point), m_stack_pop_event (NULL)
1811	{}
1812
1813	int get_controlling_option () const final override
1814	{
1815	return OPT_Wanalyzer_stale_setjmp_buffer;
1816	}
1817
1818	bool emit (diagnostic_emission_context &ctxt) final override
1819	{
1820	return ctxt.warn ("%qs called after enclosing function of %qs has returned",
1821	get_user_facing_name (call: m_longjmp_call),
1822	get_user_facing_name (call: m_setjmp_call));
1823	}
1824
1825	const char *get_kind () const final override
1826	{ return "stale_jmp_buf"; }
1827
1828	bool operator== (const stale_jmp_buf &other) const
1829	{
1830	return (m_setjmp_call == other.m_setjmp_call
1831	&& m_longjmp_call == other.m_longjmp_call);
1832	}
1833
1834	bool
1835	maybe_add_custom_events_for_superedge (const exploded_edge &eedge,
1836	checker_path *emission_path)
1837	final override
1838	{
1839	/* Detect exactly when the stack first becomes invalid,
1840	and issue an event then. */
1841	if (m_stack_pop_event)
1842	return false;
1843	const exploded_node *src_node = eedge.m_src;
1844	const program_point &src_point = src_node->get_point ();
1845	const exploded_node *dst_node = eedge.m_dest;
1846	const program_point &dst_point = dst_node->get_point ();
1847	if (valid_longjmp_stack_p (longjmp_point: src_point, setjmp_point: m_setjmp_point)
1848	&& !valid_longjmp_stack_p (longjmp_point: dst_point, setjmp_point: m_setjmp_point))
1849	{
1850	/* Compare with diagnostic_manager::add_events_for_superedge. */
1851	const int src_stack_depth = src_point.get_stack_depth ();
1852	m_stack_pop_event = new precanned_custom_event
1853	(event_loc_info (src_point.get_location (),
1854	src_point.get_fndecl (),
1855	src_stack_depth),
1856	"stack frame is popped here, invalidating saved environment");
1857	emission_path->add_event
1858	(event: std::unique_ptr<custom_event> (m_stack_pop_event));
1859	return false;
1860	}
1861	return false;
1862	}
1863
1864	label_text describe_final_event (const evdesc::final_event &ev) final override
1865	{
1866	if (m_stack_pop_event)
1867	return ev.formatted_print
1868	(fmt: "%qs called after enclosing function of %qs returned at %@",
1869	get_user_facing_name (call: m_longjmp_call),
1870	get_user_facing_name (call: m_setjmp_call),
1871	m_stack_pop_event->get_id_ptr ());
1872	else
1873	return ev.formatted_print
1874	(fmt: "%qs called after enclosing function of %qs has returned",
1875	get_user_facing_name (call: m_longjmp_call),
1876	get_user_facing_name (call: m_setjmp_call));;
1877	}
1878
1879
1880	private:
1881	const gcall *m_setjmp_call;
1882	const gcall *m_longjmp_call;
1883	program_point m_setjmp_point;
1884	custom_event *m_stack_pop_event;
1885	};
1886
1887	/* Handle LONGJMP_CALL, a call to longjmp or siglongjmp.
1888
1889	Attempt to locate where setjmp/sigsetjmp was called on the jmp_buf and build
1890	an exploded_node and exploded_edge to it representing a rewind to that frame,
1891	handling the various kinds of failure that can occur. */
1892
1893	void
1894	exploded_node::on_longjmp (exploded_graph &eg,
1895	const gcall *longjmp_call,
1896	program_state *new_state,
1897	region_model_context *ctxt)
1898	{
1899	tree buf_ptr = gimple_call_arg (gs: longjmp_call, index: 0);
1900	gcc_assert (POINTER_TYPE_P (TREE_TYPE (buf_ptr)));
1901
1902	region_model *new_region_model = new_state->m_region_model;
1903	const svalue *buf_ptr_sval = new_region_model->get_rvalue (expr: buf_ptr, ctxt);
1904	const region *buf = new_region_model->deref_rvalue (ptr_sval: buf_ptr_sval, ptr_tree: buf_ptr,
1905	ctxt);
1906
1907	const svalue *buf_content_sval
1908	= new_region_model->get_store_value (reg: buf, ctxt);
1909	const setjmp_svalue *setjmp_sval
1910	= buf_content_sval->dyn_cast_setjmp_svalue ();
1911	if (!setjmp_sval)
1912	return;
1913
1914	const setjmp_record tmp_setjmp_record = setjmp_sval->get_setjmp_record ();
1915
1916	/* Build a custom enode and eedge for rewinding from the longjmp/siglongjmp
1917	call back to the setjmp/sigsetjmp. */
1918	rewind_info_t rewind_info (tmp_setjmp_record, longjmp_call);
1919
1920	const gcall *setjmp_call = rewind_info.get_setjmp_call ();
1921	const program_point &setjmp_point = rewind_info.get_setjmp_point ();
1922
1923	const program_point &longjmp_point = get_point ();
1924
1925	/* Verify that the setjmp's call_stack hasn't been popped. */
1926	if (!valid_longjmp_stack_p (longjmp_point, setjmp_point))
1927	{
1928	ctxt->warn (d: make_unique<stale_jmp_buf> (args&: setjmp_call,
1929	args&: longjmp_call,
1930	args: setjmp_point));
1931	return;
1932	}
1933
1934	gcc_assert (longjmp_point.get_stack_depth ()
1935	>= setjmp_point.get_stack_depth ());
1936
1937	/* Update the state for use by the destination node. */
1938
1939	/* Stash the current number of diagnostics so that we can update
1940	any that this adds to show where the longjmp is rewinding to. */
1941
1942	diagnostic_manager *dm = &eg.get_diagnostic_manager ();
1943	unsigned prev_num_diagnostics = dm->get_num_diagnostics ();
1944
1945	new_region_model->on_longjmp (longjmp_call, setjmp_call,
1946	setjmp_stack_depth: setjmp_point.get_stack_depth (), ctxt);
1947
1948	/* Detect leaks in the new state relative to the old state. */
1949	program_state::detect_leaks (src_state: get_state (), dest_state: *new_state, NULL,
1950	ext_state: eg.get_ext_state (), ctxt);
1951
1952	program_point next_point
1953	= program_point::after_supernode (supernode: setjmp_point.get_supernode (),
1954	call_string: setjmp_point.get_call_string ());
1955
1956	exploded_node *next
1957	= eg.get_or_create_node (point: next_point, state: *new_state, enode_for_diag: this);
1958
1959	/* Create custom exploded_edge for a longjmp. */
1960	if (next)
1961	{
1962	exploded_edge *eedge
1963	= eg.add_edge (src: const_cast<exploded_node *> (this), dest: next, NULL, could_do_work: true,
1964	custom: make_unique<rewind_info_t> (args: tmp_setjmp_record,
1965	args&: longjmp_call));
1966
1967	/* For any diagnostics that were queued here (such as leaks) we want
1968	the checker_path to show the rewinding events after the "final event"
1969	so that the user sees where the longjmp is rewinding to (otherwise the
1970	path is meaningless).
1971
1972	For example, we want to emit something like:
1973	| NN | {
1974	| NN | longjmp (env, 1);
1975	| | ~~~~~~~~~~~~~~~~
1976	| | |
1977	| | (10) 'ptr' leaks here; was allocated at (7)
1978	| | (11) rewinding from 'longjmp' in 'inner'...
1979	|
1980	<-------------+
1981	|
1982	'outer': event 12
1983	|
1984	| NN | i = setjmp(env);
1985	| | ^~~~~~
1986	| | |
1987	| | (12) ...to 'setjmp' in 'outer' (saved at (2))
1988
1989	where the "final" event above is event (10), but we want to append
1990	events (11) and (12) afterwards.
1991
1992	Do this by setting m_trailing_eedge on any diagnostics that were
1993	just saved. */
1994	unsigned num_diagnostics = dm->get_num_diagnostics ();
1995	for (unsigned i = prev_num_diagnostics; i < num_diagnostics; i++)
1996	{
1997	saved_diagnostic *sd = dm->get_saved_diagnostic (idx: i);
1998	sd->m_trailing_eedge = eedge;
1999	}
2000	}
2001	}
2002
2003	/* Subroutine of exploded_graph::process_node for finding the successors
2004	of the supernode for a function exit basic block.
2005
2006	Ensure that pop_frame is called, potentially queuing diagnostics about
2007	leaks. */
2008
2009	void
2010	exploded_node::detect_leaks (exploded_graph &eg)
2011	{
2012	LOG_FUNC_1 (eg.get_logger (), "EN: %i", m_index);
2013
2014	gcc_assert (get_point ().get_supernode ()->return_p ());
2015
2016	/* If we're not a "top-level" function, do nothing; pop_frame
2017	will be called when handling the return superedge. */
2018	if (get_point ().get_stack_depth () > 1)
2019	return;
2020
2021	/* We have a "top-level" function. */
2022	gcc_assert (get_point ().get_stack_depth () == 1);
2023
2024	const program_state &old_state = get_state ();
2025
2026	/* Work with a temporary copy of the state: pop the frame, and see
2027	what leaks (via purge_unused_svalues). */
2028	program_state new_state (old_state);
2029
2030	gcc_assert (new_state.m_region_model);
2031
2032	uncertainty_t uncertainty;
2033	impl_region_model_context ctxt (eg, this,
2034	&old_state, &new_state, &uncertainty, NULL,
2035	get_stmt ());
2036	const svalue *result = NULL;
2037	new_state.m_region_model->pop_frame (NULL, out_result: &result, ctxt: &ctxt);
2038	program_state::detect_leaks (src_state: old_state, dest_state: new_state, extra_sval: result,
2039	ext_state: eg.get_ext_state (), ctxt: &ctxt);
2040	}
2041
2042	/* Dump the successors and predecessors of this enode to OUTF. */
2043
2044	void
2045	exploded_node::dump_succs_and_preds (FILE *outf) const
2046	{
2047	unsigned i;
2048	exploded_edge *e;
2049	{
2050	auto_vec<exploded_node *> preds (m_preds.length ());
2051	FOR_EACH_VEC_ELT (m_preds, i, e)
2052	preds.quick_push (obj: e->m_src);
2053	pretty_printer pp;
2054	print_enode_indices (pp: &pp, enodes: preds);
2055	fprintf (stream: outf, format: "preds: %s\n",
2056	pp_formatted_text (&pp));
2057	}
2058	{
2059	auto_vec<exploded_node *> succs (m_succs.length ());
2060	FOR_EACH_VEC_ELT (m_succs, i, e)
2061	succs.quick_push (obj: e->m_dest);
2062	pretty_printer pp;
2063	print_enode_indices (pp: &pp, enodes: succs);
2064	fprintf (stream: outf, format: "succs: %s\n",
2065	pp_formatted_text (&pp));
2066	}
2067	}
2068
2069	/* class dynamic_call_info_t : public custom_edge_info. */
2070
2071	/* Implementation of custom_edge_info::update_model vfunc
2072	for dynamic_call_info_t.
2073
2074	Update state for a dynamically discovered call (or return), by pushing
2075	or popping the a frame for the appropriate function. */
2076
2077	bool
2078	dynamic_call_info_t::update_model (region_model *model,
2079	const exploded_edge *eedge,
2080	region_model_context *ctxt) const
2081	{
2082	gcc_assert (eedge);
2083	if (m_is_returning_call)
2084	model->update_for_return_gcall (call_stmt: m_dynamic_call, ctxt);
2085	else
2086	{
2087	function *callee = eedge->m_dest->get_function ();
2088	model->update_for_gcall (call_stmt: m_dynamic_call, ctxt, callee);
2089	}
2090	return true;
2091	}
2092
2093	/* Implementation of custom_edge_info::add_events_to_path vfunc
2094	for dynamic_call_info_t. */
2095
2096	void
2097	dynamic_call_info_t::add_events_to_path (checker_path *emission_path,
2098	const exploded_edge &eedge) const
2099	{
2100	const exploded_node *src_node = eedge.m_src;
2101	const program_point &src_point = src_node->get_point ();
2102	const int src_stack_depth = src_point.get_stack_depth ();
2103	const exploded_node *dest_node = eedge.m_dest;
2104	const program_point &dest_point = dest_node->get_point ();
2105	const int dest_stack_depth = dest_point.get_stack_depth ();
2106
2107	if (m_is_returning_call)
2108	emission_path->add_event
2109	(event: make_unique<return_event> (args: eedge,
2110	args: event_loc_info (m_dynamic_call
2111	? m_dynamic_call->location
2112	: UNKNOWN_LOCATION,
2113	dest_point.get_fndecl (),
2114	dest_stack_depth)));
2115	else
2116	emission_path->add_event
2117	(event: make_unique<call_event> (args: eedge,
2118	args: event_loc_info (m_dynamic_call
2119	? m_dynamic_call->location
2120	: UNKNOWN_LOCATION,
2121	src_point.get_fndecl (),
2122	src_stack_depth)));
2123	}
2124
2125	/* class rewind_info_t : public custom_edge_info. */
2126
2127	/* Implementation of custom_edge_info::update_model vfunc
2128	for rewind_info_t.
2129
2130	Update state for the special-case of a rewind of a longjmp
2131	to a setjmp (which doesn't have a superedge, but does affect
2132	state). */
2133
2134	bool
2135	rewind_info_t::update_model (region_model *model,
2136	const exploded_edge *eedge,
2137	region_model_context *) const
2138	{
2139	gcc_assert (eedge);
2140	const program_point &longjmp_point = eedge->m_src->get_point ();
2141	const program_point &setjmp_point = eedge->m_dest->get_point ();
2142
2143	gcc_assert (longjmp_point.get_stack_depth ()
2144	>= setjmp_point.get_stack_depth ());
2145
2146	model->on_longjmp (longjmp_call: get_longjmp_call (),
2147	setjmp_call: get_setjmp_call (),
2148	setjmp_stack_depth: setjmp_point.get_stack_depth (), NULL);
2149	return true;
2150	}
2151
2152	/* Implementation of custom_edge_info::add_events_to_path vfunc
2153	for rewind_info_t. */
2154
2155	void
2156	rewind_info_t::add_events_to_path (checker_path *emission_path,
2157	const exploded_edge &eedge) const
2158	{
2159	const exploded_node *src_node = eedge.m_src;
2160	const program_point &src_point = src_node->get_point ();
2161	const int src_stack_depth = src_point.get_stack_depth ();
2162	const exploded_node *dst_node = eedge.m_dest;
2163	const program_point &dst_point = dst_node->get_point ();
2164	const int dst_stack_depth = dst_point.get_stack_depth ();
2165
2166	emission_path->add_event
2167	(event: make_unique<rewind_from_longjmp_event>
2168	(args: &eedge,
2169	args: event_loc_info (get_longjmp_call ()->location,
2170	src_point.get_fndecl (),
2171	src_stack_depth),
2172	args: this));
2173	emission_path->add_event
2174	(event: make_unique<rewind_to_setjmp_event>
2175	(args: &eedge,
2176	args: event_loc_info (get_setjmp_call ()->location,
2177	dst_point.get_fndecl (),
2178	dst_stack_depth),
2179	args: this));
2180	}
2181
2182	/* class exploded_edge : public dedge<eg_traits>. */
2183
2184	/* exploded_edge's ctor. */
2185
2186	exploded_edge::exploded_edge (exploded_node *src, exploded_node *dest,
2187	const superedge *sedge, bool could_do_work,
2188	std::unique_ptr<custom_edge_info> custom_info)
2189	: dedge<eg_traits> (src, dest), m_sedge (sedge),
2190	m_custom_info (std::move (custom_info)),
2191	m_could_do_work_p (could_do_work)
2192	{
2193	}
2194
2195	/* Implementation of dedge::dump_dot vfunc for exploded_edge.
2196	Use the label of the underlying superedge, if any. */
2197
2198	void
2199	exploded_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
2200	{
2201	pretty_printer *pp = gv->get_pp ();
2202
2203	m_src->dump_dot_id (pp);
2204	pp_string (pp, " -> ");
2205	m_dest->dump_dot_id (pp);
2206	dump_dot_label (pp);
2207	}
2208
2209	/* Second half of exploded_edge::dump_dot. This is split out
2210	for use by trimmed_graph::dump_dot and base_feasible_edge::dump_dot. */
2211
2212	void
2213	exploded_edge::dump_dot_label (pretty_printer *pp) const
2214	{
2215	const char *style = "\"solid,bold\"";
2216	const char *color = "black";
2217	int weight = 10;
2218	const char *constraint = "true";
2219
2220	if (m_sedge)
2221	switch (m_sedge->m_kind)
2222	{
2223	default:
2224	gcc_unreachable ();
2225	case SUPEREDGE_CFG_EDGE:
2226	break;
2227	case SUPEREDGE_CALL:
2228	color = "red";
2229	//constraint = "false";
2230	break;
2231	case SUPEREDGE_RETURN:
2232	color = "green";
2233	//constraint = "false";
2234	break;
2235	case SUPEREDGE_INTRAPROCEDURAL_CALL:
2236	style = "\"dotted\"";
2237	break;
2238	}
2239	if (m_custom_info)
2240	{
2241	color = "red";
2242	style = "\"dotted\"";
2243	}
2244
2245	pp_printf (pp,
2246	(" [style=%s, color=%s, weight=%d, constraint=%s,"
2247	" headlabel=\""),
2248	style, color, weight, constraint);
2249
2250	if (m_sedge)
2251	m_sedge->dump_label_to_pp (pp, user_facing: false);
2252	else if (m_custom_info)
2253	m_custom_info->print (pp);
2254
2255	pp_printf (pp, "%s",
2256	could_do_work_p () ? "(could do work)" : "DOES NO WORK");
2257
2258	//pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
2259
2260	pp_printf (pp, "\"];\n");
2261	}
2262
2263	/* Return a new json::object of the form
2264	{"src_idx": int, the index of the source exploded edge,
2265	"dst_idx": int, the index of the destination exploded edge,
2266	"sedge": (optional) object for the superedge, if any,
2267	"custom": (optional) str, a description, if this is a custom edge}. */
2268
2269	json::object *
2270	exploded_edge::to_json () const
2271	{
2272	json::object *eedge_obj = new json::object ();
2273	eedge_obj->set (key: "src_idx", v: new json::integer_number (m_src->m_index));
2274	eedge_obj->set (key: "dst_idx", v: new json::integer_number (m_dest->m_index));
2275	if (m_sedge)
2276	eedge_obj->set (key: "sedge", v: m_sedge->to_json ());
2277	if (m_custom_info)
2278	{
2279	pretty_printer pp;
2280	pp_format_decoder (&pp) = default_tree_printer;
2281	m_custom_info->print (pp: &pp);
2282	eedge_obj->set (key: "custom", v: new json::string (pp_formatted_text (&pp)));
2283	}
2284	return eedge_obj;
2285	}
2286
2287	/* struct stats. */
2288
2289	/* stats' ctor. */
2290
2291	stats::stats (int num_supernodes)
2292	: m_node_reuse_count (0),
2293	m_node_reuse_after_merge_count (0),
2294	m_num_supernodes (num_supernodes)
2295	{
2296	for (int i = 0; i < NUM_POINT_KINDS; i++)
2297	m_num_nodes[i] = 0;
2298	}
2299
2300	/* Log these stats in multiline form to LOGGER. */
2301
2302	void
2303	stats::log (logger *logger) const
2304	{
2305	gcc_assert (logger);
2306	for (int i = 0; i < NUM_POINT_KINDS; i++)
2307	if (m_num_nodes[i] > 0)
2308	logger->log (fmt: "m_num_nodes[%s]: %i",
2309	point_kind_to_string (pk: static_cast <enum point_kind> (i)),
2310	m_num_nodes[i]);
2311	logger->log (fmt: "m_node_reuse_count: %i", m_node_reuse_count);
2312	logger->log (fmt: "m_node_reuse_after_merge_count: %i",
2313	m_node_reuse_after_merge_count);
2314	}
2315
2316	/* Dump these stats in multiline form to OUT. */
2317
2318	void
2319	stats::dump (FILE *out) const
2320	{
2321	for (int i = 0; i < NUM_POINT_KINDS; i++)
2322	if (m_num_nodes[i] > 0)
2323	fprintf (stream: out, format: "m_num_nodes[%s]: %i\n",
2324	point_kind_to_string (pk: static_cast <enum point_kind> (i)),
2325	m_num_nodes[i]);
2326	fprintf (stream: out, format: "m_node_reuse_count: %i\n", m_node_reuse_count);
2327	fprintf (stream: out, format: "m_node_reuse_after_merge_count: %i\n",
2328	m_node_reuse_after_merge_count);
2329
2330	if (m_num_supernodes > 0)
2331	fprintf (stream: out, format: "PK_AFTER_SUPERNODE nodes per supernode: %.2f\n",
2332	(float)m_num_nodes[PK_AFTER_SUPERNODE] / (float)m_num_supernodes);
2333	}
2334
2335	/* Return the total number of enodes recorded within this object. */
2336
2337	int
2338	stats::get_total_enodes () const
2339	{
2340	int result = 0;
2341	for (int i = 0; i < NUM_POINT_KINDS; i++)
2342	result += m_num_nodes[i];
2343	return result;
2344	}
2345
2346	/* struct per_function_data. */
2347
2348	per_function_data::~per_function_data ()
2349	{
2350	for (auto iter : m_summaries)
2351	delete iter;
2352	}
2353
2354	void
2355	per_function_data::add_call_summary (exploded_node *node)
2356	{
2357	m_summaries.safe_push (obj: new call_summary (this, node));
2358	}
2359
2360	/* strongly_connected_components's ctor. Tarjan's SCC algorithm. */
2361
2362	strongly_connected_components::
2363	strongly_connected_components (const supergraph &sg, logger *logger)
2364	: m_sg (sg), m_per_node (m_sg.num_nodes ())
2365	{
2366	LOG_SCOPE (logger);
2367	auto_timevar tv (TV_ANALYZER_SCC);
2368
2369	for (int i = 0; i < m_sg.num_nodes (); i++)
2370	m_per_node.quick_push (obj: per_node_data ());
2371
2372	for (int i = 0; i < m_sg.num_nodes (); i++)
2373	if (m_per_node[i].m_index == -1)
2374	strong_connect (index: i);
2375
2376	if (0)
2377	dump ();
2378	}
2379
2380	/* Dump this object to stderr. */
2381
2382	DEBUG_FUNCTION void
2383	strongly_connected_components::dump () const
2384	{
2385	for (int i = 0; i < m_sg.num_nodes (); i++)
2386	{
2387	const per_node_data &v = m_per_node[i];
2388	fprintf (stderr, format: "SN %i: index: %i lowlink: %i on_stack: %i\n",
2389	i, v.m_index, v.m_lowlink, v.m_on_stack);
2390	}
2391	}
2392
2393	/* Return a new json::array of per-snode SCC ids. */
2394
2395	json::array *
2396	strongly_connected_components::to_json () const
2397	{
2398	json::array *scc_arr = new json::array ();
2399	for (int i = 0; i < m_sg.num_nodes (); i++)
2400	scc_arr->append (v: new json::integer_number (get_scc_id (node_index: i)));
2401	return scc_arr;
2402	}
2403
2404	/* Subroutine of strongly_connected_components's ctor, part of Tarjan's
2405	SCC algorithm. */
2406
2407	void
2408	strongly_connected_components::strong_connect (unsigned index)
2409	{
2410	supernode *v_snode = m_sg.get_node_by_index (idx: index);
2411
2412	/* Set the depth index for v to the smallest unused index. */
2413	per_node_data *v = &m_per_node[index];
2414	v->m_index = index;
2415	v->m_lowlink = index;
2416	m_stack.safe_push (obj: index);
2417	v->m_on_stack = true;
2418	index++;
2419
2420	/* Consider successors of v. */
2421	unsigned i;
2422	superedge *sedge;
2423	FOR_EACH_VEC_ELT (v_snode->m_succs, i, sedge)
2424	{
2425	if (sedge->get_kind () != SUPEREDGE_CFG_EDGE
2426	&& sedge->get_kind () != SUPEREDGE_INTRAPROCEDURAL_CALL)
2427	continue;
2428	supernode *w_snode = sedge->m_dest;
2429	per_node_data *w = &m_per_node[w_snode->m_index];
2430	if (w->m_index == -1)
2431	{
2432	/* Successor w has not yet been visited; recurse on it. */
2433	strong_connect (index: w_snode->m_index);
2434	v->m_lowlink = MIN (v->m_lowlink, w->m_lowlink);
2435	}
2436	else if (w->m_on_stack)
2437	{
2438	/* Successor w is in stack S and hence in the current SCC
2439	If w is not on stack, then (v, w) is a cross-edge in the DFS
2440	tree and must be ignored. */
2441	v->m_lowlink = MIN (v->m_lowlink, w->m_index);
2442	}
2443	}
2444
2445	/* If v is a root node, pop the stack and generate an SCC. */
2446
2447	if (v->m_lowlink == v->m_index)
2448	{
2449	per_node_data *w;
2450	do {
2451	int idx = m_stack.pop ();
2452	w = &m_per_node[idx];
2453	w->m_on_stack = false;
2454	} while (w != v);
2455	}
2456	}
2457
2458	/* worklist's ctor. */
2459
2460	worklist::worklist (const exploded_graph &eg, const analysis_plan &plan)
2461	: m_scc (eg.get_supergraph (), eg.get_logger ()),
2462	m_plan (plan),
2463	m_queue (key_t (*this, NULL))
2464	{
2465	}
2466
2467	/* Return the number of nodes in the worklist. */
2468
2469	unsigned
2470	worklist::length () const
2471	{
2472	return m_queue.nodes ();
2473	}
2474
2475	/* Return the next node in the worklist, removing it. */
2476
2477	exploded_node *
2478	worklist::take_next ()
2479	{
2480	return m_queue.extract_min ();
2481	}
2482
2483	/* Return the next node in the worklist without removing it. */
2484
2485	exploded_node *
2486	worklist::peek_next ()
2487	{
2488	return m_queue.min ();
2489	}
2490
2491	/* Add ENODE to the worklist. */
2492
2493	void
2494	worklist::add_node (exploded_node *enode)
2495	{
2496	gcc_assert (enode->get_status () == exploded_node::STATUS_WORKLIST);
2497	m_queue.insert (key: key_t (*this, enode), data: enode);
2498	}
2499
2500	/* Comparator for implementing worklist::key_t comparison operators.
2501	Return negative if KA is before KB
2502	Return positive if KA is after KB
2503	Return 0 if they are equal.
2504
2505	The ordering of the worklist is critical for performance and for
2506	avoiding node explosions. Ideally we want all enodes at a CFG join-point
2507	with the same callstring to be sorted next to each other in the worklist
2508	so that a run of consecutive enodes can be merged and processed "in bulk"
2509	rather than individually or pairwise, minimizing the number of new enodes
2510	created. */
2511
2512	int
2513	worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb)
2514	{
2515	const program_point &point_a = ka.m_enode->get_point ();
2516	const program_point &point_b = kb.m_enode->get_point ();
2517	const call_string &call_string_a = point_a.get_call_string ();
2518	const call_string &call_string_b = point_b.get_call_string ();
2519
2520	/* Order empty-callstring points with different functions based on the
2521	analysis_plan, so that we generate summaries before they are used. */
2522	if (flag_analyzer_call_summaries
2523	&& call_string_a.empty_p ()
2524	&& call_string_b.empty_p ()
2525	&& point_a.get_function () != NULL
2526	&& point_b.get_function () != NULL
2527	&& point_a.get_function () != point_b.get_function ())
2528	{
2529	if (int cmp = ka.m_worklist.m_plan.cmp_function (fun_a: point_a.get_function (),
2530	fun_b: point_b.get_function ()))
2531	return cmp;
2532	}
2533
2534	/* Sort by callstring, so that nodes with deeper call strings are processed
2535	before those with shallower call strings.
2536	If we have
2537	splitting BB
2538	/ \
2539	/ \
2540	fn call no fn call
2541	\ /
2542	\ /
2543	join BB
2544	then we want the path inside the function call to be fully explored up
2545	to the return to the join BB before we explore on the "no fn call" path,
2546	so that both enodes at the join BB reach the front of the worklist at
2547	the same time and thus have a chance of being merged. */
2548	int cs_cmp = call_string::cmp (a: call_string_a, b: call_string_b);
2549	if (cs_cmp)
2550	return cs_cmp;
2551
2552	/* Order by SCC. */
2553	int scc_id_a = ka.get_scc_id (enode: ka.m_enode);
2554	int scc_id_b = kb.get_scc_id (enode: kb.m_enode);
2555	if (scc_id_a != scc_id_b)
2556	return scc_id_a - scc_id_b;
2557
2558	/* If in same SCC, order by supernode index (an arbitrary but stable
2559	ordering). */
2560	const supernode *snode_a = ka.m_enode->get_supernode ();
2561	const supernode *snode_b = kb.m_enode->get_supernode ();
2562	if (snode_a == NULL)
2563	{
2564	if (snode_b != NULL)
2565	/* One is NULL. */
2566	return -1;
2567	else
2568	/* Both are NULL. */
2569	return 0;
2570	}
2571	if (snode_b == NULL)
2572	/* One is NULL. */
2573	return 1;
2574	/* Neither are NULL. */
2575	gcc_assert (snode_a && snode_b);
2576	if (snode_a->m_index != snode_b->m_index)
2577	return snode_a->m_index - snode_b->m_index;
2578
2579	gcc_assert (snode_a == snode_b);
2580
2581	/* Order within supernode via program point. */
2582	int within_snode_cmp
2583	= function_point::cmp_within_supernode (point_a: point_a.get_function_point (),
2584	point_b: point_b.get_function_point ());
2585	if (within_snode_cmp)
2586	return within_snode_cmp;
2587
2588	/* Otherwise, we ought to have the same program_point. */
2589	gcc_assert (point_a == point_b);
2590
2591	const program_state &state_a = ka.m_enode->get_state ();
2592	const program_state &state_b = kb.m_enode->get_state ();
2593
2594	/* Sort by sm-state, so that identical sm-states are grouped
2595	together in the worklist. */
2596	for (unsigned sm_idx = 0; sm_idx < state_a.m_checker_states.length ();
2597	++sm_idx)
2598	{
2599	sm_state_map *smap_a = state_a.m_checker_states[sm_idx];
2600	sm_state_map *smap_b = state_b.m_checker_states[sm_idx];
2601
2602	if (int smap_cmp = sm_state_map::cmp (smap_a: *smap_a, smap_b: *smap_b))
2603	return smap_cmp;
2604	}
2605
2606	/* Otherwise, we have two enodes at the same program point but with
2607	different states. We don't have a good total ordering on states,
2608	so order them by enode index, so that we have at least have a
2609	stable sort. */
2610	return ka.m_enode->m_index - kb.m_enode->m_index;
2611	}
2612
2613	/* Return a new json::object of the form
2614	{"scc" : [per-snode-IDs]}, */
2615
2616	json::object *
2617	worklist::to_json () const
2618	{
2619	json::object *worklist_obj = new json::object ();
2620
2621	worklist_obj->set (key: "scc", v: m_scc.to_json ());
2622
2623	/* The following field isn't yet being JSONified:
2624	queue_t m_queue; */
2625
2626	return worklist_obj;
2627	}
2628
2629	/* exploded_graph's ctor. */
2630
2631	exploded_graph::exploded_graph (const supergraph &sg, logger *logger,
2632	const extrinsic_state &ext_state,
2633	const state_purge_map *purge_map,
2634	const analysis_plan &plan,
2635	int verbosity)
2636	: m_sg (sg), m_logger (logger),
2637	m_worklist (*this, plan),
2638	m_ext_state (ext_state),
2639	m_purge_map (purge_map),
2640	m_plan (plan),
2641	m_diagnostic_manager (logger, ext_state.get_engine (), verbosity),
2642	m_global_stats (m_sg.num_nodes ()),
2643	m_functionless_stats (m_sg.num_nodes ()),
2644	m_PK_AFTER_SUPERNODE_per_snode (m_sg.num_nodes ())
2645	{
2646	m_origin = get_or_create_node
2647	(point: program_point::origin (mgr: *ext_state.get_model_manager ()),
2648	state: program_state (ext_state), NULL);
2649	for (int i = 0; i < m_sg.num_nodes (); i++)
2650	m_PK_AFTER_SUPERNODE_per_snode.quick_push (obj: i);
2651	}
2652
2653	/* exploded_graph's dtor. */
2654
2655	exploded_graph::~exploded_graph ()
2656	{
2657	for (auto iter : m_per_point_data)
2658	delete iter.second;
2659	for (auto iter : m_per_function_data)
2660	delete iter.second;
2661	for (auto iter : m_per_function_stats)
2662	delete iter.second;
2663	for (auto iter : m_per_call_string_data)
2664	delete iter.second;
2665	}
2666
2667	/* Subroutine for use when implementing __attribute__((tainted_args))
2668	on functions and on function pointer fields in structs.
2669
2670	Called on STATE representing a call to FNDECL.
2671	Mark all params of FNDECL in STATE as "tainted". Mark the value of all
2672	regions pointed to by params of FNDECL as "tainted".
2673
2674	Return true if successful; return false if the "taint" state machine
2675	was not found. */
2676
2677	static bool
2678	mark_params_as_tainted (program_state *state, tree fndecl,
2679	const extrinsic_state &ext_state)
2680	{
2681	unsigned taint_sm_idx;
2682	if (!ext_state.get_sm_idx_by_name (name: "taint", out: &taint_sm_idx))
2683	return false;
2684	sm_state_map *smap = state->m_checker_states[taint_sm_idx];
2685
2686	const state_machine &sm = ext_state.get_sm (idx: taint_sm_idx);
2687	state_machine::state_t tainted = sm.get_state_by_name (name: "tainted");
2688
2689	region_model_manager *mgr = ext_state.get_model_manager ();
2690
2691	function *fun = DECL_STRUCT_FUNCTION (fndecl);
2692	gcc_assert (fun);
2693
2694	for (tree iter_parm = DECL_ARGUMENTS (fndecl); iter_parm;
2695	iter_parm = DECL_CHAIN (iter_parm))
2696	{
2697	tree param = iter_parm;
2698	if (tree parm_default_ssa = ssa_default_def (fun, iter_parm))
2699	param = parm_default_ssa;
2700	const region *param_reg = state->m_region_model->get_lvalue (expr: param, NULL);
2701	const svalue *init_sval = mgr->get_or_create_initial_value (reg: param_reg);
2702	smap->set_state (model: state->m_region_model, sval: init_sval,
2703	state: tainted, NULL /*origin_new_sval*/, ext_state);
2704	if (POINTER_TYPE_P (TREE_TYPE (param)))
2705	{
2706	const region *pointee_reg = mgr->get_symbolic_region (sval: init_sval);
2707	/* Mark "*param" as tainted. */
2708	const svalue *init_pointee_sval
2709	= mgr->get_or_create_initial_value (reg: pointee_reg);
2710	smap->set_state (model: state->m_region_model, sval: init_pointee_sval,
2711	state: tainted, NULL /*origin_new_sval*/, ext_state);
2712	}
2713	}
2714
2715	return true;
2716	}
2717
2718	/* Custom event for use by tainted_args_function_info when a function
2719	has been marked with __attribute__((tainted_args)). */
2720
2721	class tainted_args_function_custom_event : public custom_event
2722	{
2723	public:
2724	tainted_args_function_custom_event (const event_loc_info &loc_info)
2725	: custom_event (loc_info),
2726	m_fndecl (loc_info.m_fndecl)
2727	{
2728	}
2729
2730	label_text get_desc (bool can_colorize) const final override
2731	{
2732	return make_label_text
2733	(can_colorize,
2734	fmt: "function %qE marked with %<__attribute__((tainted_args))%>",
2735	m_fndecl);
2736	}
2737
2738	private:
2739	tree m_fndecl;
2740	};
2741
2742	/* Custom exploded_edge info for top-level calls to a function
2743	marked with __attribute__((tainted_args)). */
2744
2745	class tainted_args_function_info : public custom_edge_info
2746	{
2747	public:
2748	tainted_args_function_info (tree fndecl)
2749	: m_fndecl (fndecl)
2750	{}
2751
2752	void print (pretty_printer *pp) const final override
2753	{
2754	pp_string (pp, "call to tainted_args function");
2755	};
2756
2757	bool update_model (region_model *,
2758	const exploded_edge *,
2759	region_model_context *) const final override
2760	{
2761	/* No-op. */
2762	return true;
2763	}
2764
2765	void add_events_to_path (checker_path *emission_path,
2766	const exploded_edge &) const final override
2767	{
2768	emission_path->add_event
2769	(event: make_unique<tainted_args_function_custom_event>
2770	(args: event_loc_info (DECL_SOURCE_LOCATION (m_fndecl), m_fndecl, 0)));
2771	}
2772
2773	private:
2774	tree m_fndecl;
2775	};
2776
2777	/* Ensure that there is an exploded_node representing an external call to
2778	FUN, adding it to the worklist if creating it.
2779
2780	Add an edge from the origin exploded_node to the function entrypoint
2781	exploded_node.
2782
2783	Return the exploded_node for the entrypoint to the function. */
2784
2785	exploded_node *
2786	exploded_graph::add_function_entry (const function &fun)
2787	{
2788	gcc_assert (gimple_has_body_p (fun.decl));
2789
2790	/* Be idempotent. */
2791	function *key = const_cast<function *> (&fun);
2792	if (m_functions_with_enodes.contains (k: key))
2793	{
2794	logger * const logger = get_logger ();
2795	if (logger)
2796	logger->log (fmt: "entrypoint for %qE already exists", fun.decl);
2797	return NULL;
2798	}
2799
2800	program_point point
2801	= program_point::from_function_entry (mgr: *m_ext_state.get_model_manager (),
2802	sg: m_sg, fun);
2803	program_state state (m_ext_state);
2804	state.push_frame (ext_state: m_ext_state, fun);
2805
2806	std::unique_ptr<custom_edge_info> edge_info = NULL;
2807
2808	if (lookup_attribute (attr_name: "tainted_args", DECL_ATTRIBUTES (fun.decl)))
2809	{
2810	if (mark_params_as_tainted (state: &state, fndecl: fun.decl, ext_state: m_ext_state))
2811	edge_info = make_unique<tainted_args_function_info> (args: fun.decl);
2812	}
2813
2814	if (!state.m_valid)
2815	return NULL;
2816
2817	exploded_node *enode = get_or_create_node (point, state, NULL);
2818	if (!enode)
2819	return NULL;
2820
2821	add_edge (src: m_origin, dest: enode, NULL, could_do_work: false, custom: std::move (edge_info));
2822
2823	m_functions_with_enodes.add (k: key);
2824
2825	return enode;
2826	}
2827
2828	/* Get or create an exploded_node for (POINT, STATE).
2829	If a new node is created, it is added to the worklist.
2830
2831	Use ENODE_FOR_DIAG, a pre-existing enode, for any diagnostics
2832	that need to be emitted (e.g. when purging state *before* we have
2833	a new enode). */
2834
2835	exploded_node *
2836	exploded_graph::get_or_create_node (const program_point &point,
2837	const program_state &state,
2838	exploded_node *enode_for_diag)
2839	{
2840	logger * const logger = get_logger ();
2841	LOG_FUNC (logger);
2842	if (logger)
2843	{
2844	format f (false);
2845	pretty_printer *pp = logger->get_printer ();
2846	logger->start_log_line ();
2847	pp_string (pp, "point: ");
2848	point.print (pp, f);
2849	logger->end_log_line ();
2850	logger->start_log_line ();
2851	pp_string (pp, "state: ");
2852	state.dump_to_pp (ext_state: m_ext_state, simple: true, multiline: false, pp);
2853	logger->end_log_line ();
2854	}
2855
2856	/* Stop exploring paths for which we don't know how to effectively
2857	model the state. */
2858	if (!state.m_valid)
2859	{
2860	if (logger)
2861	logger->log (fmt: "invalid state; not creating node");
2862	return NULL;
2863	}
2864
2865	auto_cfun sentinel (point.get_function ());
2866
2867	state.validate (ext_state: get_ext_state ());
2868
2869	//state.dump (get_ext_state ());
2870
2871	/* Prune state to try to improve the chances of a cache hit,
2872	avoiding generating redundant nodes. */
2873	uncertainty_t uncertainty;
2874	program_state pruned_state
2875	= state.prune_for_point (eg&: *this, point, enode_for_diag, uncertainty: &uncertainty);
2876
2877	pruned_state.validate (ext_state: get_ext_state ());
2878
2879	//pruned_state.dump (get_ext_state ());
2880
2881	if (logger)
2882	{
2883	pretty_printer *pp = logger->get_printer ();
2884	logger->start_log_line ();
2885	pp_string (pp, "pruned_state: ");
2886	pruned_state.dump_to_pp (ext_state: m_ext_state, simple: true, multiline: false, pp);
2887	logger->end_log_line ();
2888	pruned_state.m_region_model->dump_to_pp (pp: logger->get_printer (), simple: true,
2889	multiline: false);
2890	}
2891
2892	stats *per_fn_stats = get_or_create_function_stats (fn: point.get_function ());
2893
2894	stats *per_cs_stats
2895	= &get_or_create_per_call_string_data (point.get_call_string ())->m_stats;
2896
2897	point_and_state ps (point, pruned_state);
2898	ps.validate (ext_state: m_ext_state);
2899	if (exploded_node **slot = m_point_and_state_to_node.get (k: &ps))
2900	{
2901	/* An exploded_node for PS already exists. */
2902	if (logger)
2903	logger->log (fmt: "reused EN: %i", (*slot)->m_index);
2904	m_global_stats.m_node_reuse_count++;
2905	per_fn_stats->m_node_reuse_count++;
2906	per_cs_stats->m_node_reuse_count++;
2907	return *slot;
2908	}
2909
2910	per_program_point_data *per_point_data
2911	= get_or_create_per_program_point_data (point);
2912
2913	/* Consider merging state with another enode at this program_point. */
2914	if (flag_analyzer_state_merge)
2915	{
2916	exploded_node *existing_enode;
2917	unsigned i;
2918	FOR_EACH_VEC_ELT (per_point_data->m_enodes, i, existing_enode)
2919	{
2920	if (logger)
2921	logger->log (fmt: "considering merging with existing EN: %i for point",
2922	existing_enode->m_index);
2923	gcc_assert (existing_enode->get_point () == point);
2924	const program_state &existing_state = existing_enode->get_state ();
2925
2926	/* This merges successfully within the loop. */
2927
2928	program_state merged_state (m_ext_state);
2929	if (pruned_state.can_merge_with_p (other: existing_state, ext_state: m_ext_state, point,
2930	out: &merged_state))
2931	{
2932	merged_state.validate (ext_state: m_ext_state);
2933	if (logger)
2934	logger->log (fmt: "merging new state with that of EN: %i",
2935	existing_enode->m_index);
2936
2937	/* Try again for a cache hit.
2938	Whether we get one or not, merged_state's value_ids have no
2939	relationship to those of the input state, and thus to those
2940	of CHANGE, so we must purge any svalue_ids from *CHANGE. */
2941	ps.set_state (merged_state);
2942
2943	if (exploded_node **slot = m_point_and_state_to_node.get (k: &ps))
2944	{
2945	/* An exploded_node for PS already exists. */
2946	if (logger)
2947	logger->log (fmt: "reused EN: %i", (*slot)->m_index);
2948	m_global_stats.m_node_reuse_after_merge_count++;
2949	per_fn_stats->m_node_reuse_after_merge_count++;
2950	per_cs_stats->m_node_reuse_after_merge_count++;
2951	return *slot;
2952	}
2953	}
2954	else
2955	if (logger)
2956	logger->log (fmt: "not merging new state with that of EN: %i",
2957	existing_enode->m_index);
2958	}
2959	}
2960
2961	/* Impose a limit on the number of enodes per program point, and
2962	simply stop if we exceed it. */
2963	if ((int)per_point_data->m_enodes.length ()
2964	>= param_analyzer_max_enodes_per_program_point)
2965	{
2966	pretty_printer pp;
2967	point.print (pp: &pp, f: format (false));
2968	print_enode_indices (pp: &pp, enodes: per_point_data->m_enodes);
2969	if (logger)
2970	logger->log (fmt: "not creating enode; too many at program point: %s",
2971	pp_formatted_text (&pp));
2972	warning_at (point.get_location (), OPT_Wanalyzer_too_complex,
2973	"terminating analysis for this program point: %s",
2974	pp_formatted_text (&pp));
2975	per_point_data->m_excess_enodes++;
2976	return NULL;
2977	}
2978
2979	ps.validate (ext_state: m_ext_state);
2980
2981	/* An exploded_node for "ps" doesn't already exist; create one. */
2982	exploded_node *node = new exploded_node (ps, m_nodes.length ());
2983	add_node (node);
2984	m_point_and_state_to_node.put (k: node->get_ps_key (), v: node);
2985
2986	/* Update per-program_point data. */
2987	per_point_data->m_enodes.safe_push (obj: node);
2988
2989	const enum point_kind node_pk = node->get_point ().get_kind ();
2990	m_global_stats.m_num_nodes[node_pk]++;
2991	per_fn_stats->m_num_nodes[node_pk]++;
2992	per_cs_stats->m_num_nodes[node_pk]++;
2993
2994	if (node_pk == PK_AFTER_SUPERNODE)
2995	m_PK_AFTER_SUPERNODE_per_snode[point.get_supernode ()->m_index]++;
2996
2997	if (logger)
2998	{
2999	format f (false);
3000	pretty_printer *pp = logger->get_printer ();
3001	logger->log (fmt: "created EN: %i", node->m_index);
3002	logger->start_log_line ();
3003	pp_string (pp, "point: ");
3004	point.print (pp, f);
3005	logger->end_log_line ();
3006	logger->start_log_line ();
3007	pp_string (pp, "pruned_state: ");
3008	pruned_state.dump_to_pp (ext_state: m_ext_state, simple: true, multiline: false, pp);
3009	logger->end_log_line ();
3010	}
3011
3012	/* Add the new node to the worlist. */
3013	m_worklist.add_node (enode: node);
3014	return node;
3015	}
3016
3017	/* Add an exploded_edge from SRC to DEST, recording its association
3018	with SEDGE (which may be NULL), and, if non-NULL, taking ownership
3019	of CUSTOM_INFO. COULD_DO_WORK is used for detecting infinite loops.
3020	Return the newly-created eedge. */
3021
3022	exploded_edge *
3023	exploded_graph::add_edge (exploded_node *src, exploded_node *dest,
3024	const superedge *sedge, bool could_do_work,
3025	std::unique_ptr<custom_edge_info> custom_info)
3026	{
3027	if (get_logger ())
3028	get_logger ()->log (fmt: "creating edge EN: %i -> EN: %i",
3029	src->m_index, dest->m_index);
3030	exploded_edge *e
3031	= new exploded_edge (src, dest, sedge, could_do_work,
3032	std::move (custom_info));
3033	digraph<eg_traits>::add_edge (edge: e);
3034	return e;
3035	}
3036
3037	/* Ensure that this graph has per-program_point-data for POINT;
3038	borrow a pointer to it. */
3039
3040	per_program_point_data *
3041	exploded_graph::
3042	get_or_create_per_program_point_data (const program_point &point)
3043	{
3044	if (per_program_point_data **slot = m_per_point_data.get (k: &point))
3045	return *slot;
3046
3047	per_program_point_data *per_point_data = new per_program_point_data (point);
3048	m_per_point_data.put (k: &per_point_data->m_key, v: per_point_data);
3049	return per_point_data;
3050	}
3051
3052	/* Get this graph's per-program-point-data for POINT if there is any,
3053	otherwise NULL. */
3054
3055	per_program_point_data *
3056	exploded_graph::get_per_program_point_data (const program_point &point) const
3057	{
3058	if (per_program_point_data **slot
3059	= const_cast <point_map_t &> (m_per_point_data).get (k: &point))
3060	return *slot;
3061
3062	return NULL;
3063	}
3064
3065	/* Ensure that this graph has per-call_string-data for CS;
3066	borrow a pointer to it. */
3067
3068	per_call_string_data *
3069	exploded_graph::get_or_create_per_call_string_data (const call_string &cs)
3070	{
3071	if (per_call_string_data **slot = m_per_call_string_data.get (k: &cs))
3072	return *slot;
3073
3074	per_call_string_data *data = new per_call_string_data (cs, m_sg.num_nodes ());
3075	m_per_call_string_data.put (k: &data->m_key,
3076	v: data);
3077	return data;
3078	}
3079
3080	/* Ensure that this graph has per-function-data for FUN;
3081	borrow a pointer to it. */
3082
3083	per_function_data *
3084	exploded_graph::get_or_create_per_function_data (function *fun)
3085	{
3086	if (per_function_data **slot = m_per_function_data.get (k: fun))
3087	return *slot;
3088
3089	per_function_data *data = new per_function_data ();
3090	m_per_function_data.put (k: fun, v: data);
3091	return data;
3092	}
3093
3094	/* Get this graph's per-function-data for FUN if there is any,
3095	otherwise NULL. */
3096
3097	per_function_data *
3098	exploded_graph::get_per_function_data (function *fun) const
3099	{
3100	if (per_function_data **slot
3101	= const_cast <per_function_data_t &> (m_per_function_data).get (k: fun))
3102	return *slot;
3103
3104	return NULL;
3105	}
3106
3107	/* Return true if FUN should be traversed directly, rather than only as
3108	called via other functions. */
3109
3110	static bool
3111	toplevel_function_p (const function &fun, logger *logger)
3112	{
3113	/* Don't directly traverse into functions that have an "__analyzer_"
3114	prefix. Doing so is useful for the analyzer test suite, allowing
3115	us to have functions that are called in traversals, but not directly
3116	explored, thus testing how the analyzer handles calls and returns.
3117	With this, we can have DejaGnu directives that cover just the case
3118	of where a function is called by another function, without generating
3119	excess messages from the case of the first function being traversed
3120	directly. */
3121	#define ANALYZER_PREFIX "__analyzer_"
3122	if (!strncmp (IDENTIFIER_POINTER (DECL_NAME (fun.decl)), ANALYZER_PREFIX,
3123	n: strlen (ANALYZER_PREFIX)))
3124	{
3125	if (logger)
3126	logger->log (fmt: "not traversing %qE (starts with %qs)",
3127	fun.decl, ANALYZER_PREFIX);
3128	return false;
3129	}
3130
3131	if (logger)
3132	logger->log (fmt: "traversing %qE (all checks passed)", fun.decl);
3133
3134	return true;
3135	}
3136
3137	/* Custom event for use by tainted_call_info when a callback field has been
3138	marked with __attribute__((tainted_args)), for labelling the field. */
3139
3140	class tainted_args_field_custom_event : public custom_event
3141	{
3142	public:
3143	tainted_args_field_custom_event (tree field)
3144	: custom_event (event_loc_info (DECL_SOURCE_LOCATION (field), NULL_TREE, 0)),
3145	m_field (field)
3146	{
3147	}
3148
3149	label_text get_desc (bool can_colorize) const final override
3150	{
3151	return make_label_text (can_colorize,
3152	fmt: "field %qE of %qT"
3153	" is marked with %<__attribute__((tainted_args))%>",
3154	m_field, DECL_CONTEXT (m_field));
3155	}
3156
3157	private:
3158	tree m_field;
3159	};
3160
3161	/* Custom event for use by tainted_call_info when a callback field has been
3162	marked with __attribute__((tainted_args)), for labelling the function used
3163	in that callback. */
3164
3165	class tainted_args_callback_custom_event : public custom_event
3166	{
3167	public:
3168	tainted_args_callback_custom_event (const event_loc_info &loc_info,
3169	tree field)
3170	: custom_event (loc_info),
3171	m_field (field)
3172	{
3173	}
3174
3175	label_text get_desc (bool can_colorize) const final override
3176	{
3177	return make_label_text (can_colorize,
3178	fmt: "function %qE used as initializer for field %qE"
3179	" marked with %<__attribute__((tainted_args))%>",
3180	get_fndecl (), m_field);
3181	}
3182
3183	private:
3184	tree m_field;
3185	};
3186
3187	/* Custom edge info for use when adding a function used by a callback field
3188	marked with '__attribute__((tainted_args))'. */
3189
3190	class tainted_args_call_info : public custom_edge_info
3191	{
3192	public:
3193	tainted_args_call_info (tree field, tree fndecl, location_t loc)
3194	: m_field (field), m_fndecl (fndecl), m_loc (loc)
3195	{}
3196
3197	void print (pretty_printer *pp) const final override
3198	{
3199	pp_string (pp, "call to tainted field");
3200	};
3201
3202	bool update_model (region_model *,
3203	const exploded_edge *,
3204	region_model_context *) const final override
3205	{
3206	/* No-op. */
3207	return true;
3208	}
3209
3210	void add_events_to_path (checker_path *emission_path,
3211	const exploded_edge &) const final override
3212	{
3213	/* Show the field in the struct declaration, e.g.
3214	"(1) field 'store' is marked with '__attribute__((tainted_args))'" */
3215	emission_path->add_event
3216	(event: make_unique<tainted_args_field_custom_event> (args: m_field));
3217
3218	/* Show the callback in the initializer
3219	e.g.
3220	"(2) function 'gadget_dev_desc_UDC_store' used as initializer
3221	for field 'store' marked with '__attribute__((tainted_args))'". */
3222	emission_path->add_event
3223	(event: make_unique<tainted_args_callback_custom_event>
3224	(args: event_loc_info (m_loc, m_fndecl, 0),
3225	args: m_field));
3226	}
3227
3228	private:
3229	tree m_field;
3230	tree m_fndecl;
3231	location_t m_loc;
3232	};
3233
3234	/* Given an initializer at LOC for FIELD marked with
3235	'__attribute__((tainted_args))' initialized with FNDECL, add an
3236	entrypoint to FNDECL to EG (and to its worklist) where the params to
3237	FNDECL are marked as tainted. */
3238
3239	static void
3240	add_tainted_args_callback (exploded_graph *eg, tree field, tree fndecl,
3241	location_t loc)
3242	{
3243	logger *logger = eg->get_logger ();
3244
3245	LOG_SCOPE (logger);
3246
3247	if (!gimple_has_body_p (fndecl))
3248	return;
3249
3250	const extrinsic_state &ext_state = eg->get_ext_state ();
3251
3252	function *fun = DECL_STRUCT_FUNCTION (fndecl);
3253	gcc_assert (fun);
3254
3255	program_point point
3256	= program_point::from_function_entry (mgr: *ext_state.get_model_manager (),
3257	sg: eg->get_supergraph (), fun: *fun);
3258	program_state state (ext_state);
3259	state.push_frame (ext_state, fun: *fun);
3260
3261	if (!mark_params_as_tainted (state: &state, fndecl, ext_state))
3262	return;
3263
3264	if (!state.m_valid)
3265	return;
3266
3267	exploded_node *enode = eg->get_or_create_node (point, state, NULL);
3268	if (logger)
3269	{
3270	if (enode)
3271	logger->log (fmt: "created EN %i for tainted_args %qE entrypoint",
3272	enode->m_index, fndecl);
3273	else
3274	{
3275	logger->log (fmt: "did not create enode for tainted_args %qE entrypoint",
3276	fndecl);
3277	return;
3278	}
3279	}
3280
3281	eg->add_edge (src: eg->get_origin (), dest: enode, NULL, could_do_work: false,
3282	custom_info: make_unique<tainted_args_call_info> (args&: field, args&: fndecl, args&: loc));
3283	}
3284
3285	/* Callback for walk_tree for finding callbacks within initializers;
3286	ensure that any callback initializer where the corresponding field is
3287	marked with '__attribute__((tainted_args))' is treated as an entrypoint
3288	to the analysis, special-casing that the inputs to the callback are
3289	untrustworthy. */
3290
3291	static tree
3292	add_any_callbacks (tree *tp, int *, void *data)
3293	{
3294	exploded_graph *eg = (exploded_graph *)data;
3295	if (TREE_CODE (*tp) == CONSTRUCTOR)
3296	{
3297	/* Find fields with the "tainted_args" attribute.
3298	walk_tree only walks the values, not the index values;
3299	look at the index values. */
3300	unsigned HOST_WIDE_INT idx;
3301	constructor_elt *ce;
3302
3303	for (idx = 0; vec_safe_iterate (CONSTRUCTOR_ELTS (*tp), ix: idx, ptr: &ce);
3304	idx++)
3305	if (ce->index && TREE_CODE (ce->index) == FIELD_DECL)
3306	if (lookup_attribute (attr_name: "tainted_args", DECL_ATTRIBUTES (ce->index)))
3307	{
3308	tree value = ce->value;
3309	if (TREE_CODE (value) == ADDR_EXPR
3310	&& TREE_CODE (TREE_OPERAND (value, 0)) == FUNCTION_DECL)
3311	add_tainted_args_callback (eg, field: ce->index,
3312	TREE_OPERAND (value, 0),
3313	EXPR_LOCATION (value));
3314	}
3315	}
3316
3317	return NULL_TREE;
3318	}
3319
3320	/* Add initial nodes to EG, with entrypoints for externally-callable
3321	functions. */
3322
3323	void
3324	exploded_graph::build_initial_worklist ()
3325	{
3326	logger * const logger = get_logger ();
3327	LOG_SCOPE (logger);
3328
3329	cgraph_node *node;
3330	FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
3331	{
3332	function *fun = node->get_fun ();
3333	gcc_assert (fun);
3334	if (!toplevel_function_p (fun: *fun, logger))
3335	continue;
3336	exploded_node *enode = add_function_entry (fun: *fun);
3337	if (logger)
3338	{
3339	if (enode)
3340	logger->log (fmt: "created EN %i for %qE entrypoint",
3341	enode->m_index, fun->decl);
3342	else
3343	logger->log (fmt: "did not create enode for %qE entrypoint", fun->decl);
3344	}
3345	}
3346
3347	/* Find callbacks that are reachable from global initializers. */
3348	varpool_node *vpnode;
3349	FOR_EACH_VARIABLE (vpnode)
3350	{
3351	tree decl = vpnode->decl;
3352	tree init = DECL_INITIAL (decl);
3353	if (!init)
3354	continue;
3355	walk_tree (&init, add_any_callbacks, this, NULL);
3356	}
3357	}
3358
3359	/* The main loop of the analysis.
3360	Take freshly-created exploded_nodes from the worklist, calling
3361	process_node on them to explore the <point, state> graph.
3362	Add edges to their successors, potentially creating new successors
3363	(which are also added to the worklist). */
3364
3365	void
3366	exploded_graph::process_worklist ()
3367	{
3368	logger * const logger = get_logger ();
3369	LOG_SCOPE (logger);
3370	auto_timevar tv (TV_ANALYZER_WORKLIST);
3371
3372	while (m_worklist.length () > 0)
3373	{
3374	exploded_node *node = m_worklist.take_next ();
3375	gcc_assert (node->get_status () == exploded_node::STATUS_WORKLIST);
3376	gcc_assert (node->m_succs.length () == 0
3377	|| node == m_origin);
3378
3379	if (logger)
3380	logger->log (fmt: "next to process: EN: %i", node->m_index);
3381
3382	/* If we have a run of nodes that are before-supernode, try merging and
3383	processing them together, rather than pairwise or individually. */
3384	if (flag_analyzer_state_merge && node != m_origin)
3385	if (maybe_process_run_of_before_supernode_enodes (node))
3386	goto handle_limit;
3387
3388	/* Avoid exponential explosions of nodes by attempting to merge
3389	nodes that are at the same program point and which have
3390	sufficiently similar state. */
3391	if (flag_analyzer_state_merge && node != m_origin)
3392	if (exploded_node *node_2 = m_worklist.peek_next ())
3393	{
3394	gcc_assert (node_2->get_status ()
3395	== exploded_node::STATUS_WORKLIST);
3396	gcc_assert (node->m_succs.length () == 0);
3397	gcc_assert (node_2->m_succs.length () == 0);
3398
3399	gcc_assert (node != node_2);
3400
3401	if (logger)
3402	logger->log (fmt: "peek worklist: EN: %i", node_2->m_index);
3403
3404	if (node->get_point () == node_2->get_point ())
3405	{
3406	const program_point &point = node->get_point ();
3407	if (logger)
3408	{
3409	format f (false);
3410	pretty_printer *pp = logger->get_printer ();
3411	logger->start_log_line ();
3412	logger->log_partial
3413	(fmt: "got potential merge EN: %i and EN: %i at ",
3414	node->m_index, node_2->m_index);
3415	point.print (pp, f);
3416	logger->end_log_line ();
3417	}
3418	const program_state &state = node->get_state ();
3419	const program_state &state_2 = node_2->get_state ();
3420
3421	/* They shouldn't be equal, or we wouldn't have two
3422	separate nodes. */
3423	gcc_assert (state != state_2);
3424
3425	program_state merged_state (m_ext_state);
3426	if (state.can_merge_with_p (other: state_2, ext_state: m_ext_state,
3427	point, out: &merged_state))
3428	{
3429	if (logger)
3430	logger->log (fmt: "merging EN: %i and EN: %i",
3431	node->m_index, node_2->m_index);
3432
3433	if (merged_state == state)
3434	{
3435	/* Then merge node_2 into node by adding an edge. */
3436	add_edge (src: node_2, dest: node, NULL, could_do_work: false);
3437
3438	/* Remove node_2 from the worklist. */
3439	m_worklist.take_next ();
3440	node_2->set_status (exploded_node::STATUS_MERGER);
3441
3442	/* Continue processing "node" below. */
3443	}
3444	else if (merged_state == state_2)
3445	{
3446	/* Then merge node into node_2, and leave node_2
3447	in the worklist, to be processed on the next
3448	iteration. */
3449	add_edge (src: node, dest: node_2, NULL, could_do_work: false);
3450	node->set_status (exploded_node::STATUS_MERGER);
3451	continue;
3452	}
3453	else
3454	{
3455	/* We have a merged state that differs from
3456	both state and state_2. */
3457
3458	/* Remove node_2 from the worklist. */
3459	m_worklist.take_next ();
3460
3461	/* Create (or get) an exploded node for the merged
3462	states, adding to the worklist. */
3463	exploded_node *merged_enode
3464	= get_or_create_node (point: node->get_point (),
3465	state: merged_state, enode_for_diag: node);
3466	if (merged_enode == NULL)
3467	continue;
3468
3469	if (logger)
3470	logger->log (fmt: "merged EN: %i and EN: %i into EN: %i",
3471	node->m_index, node_2->m_index,
3472	merged_enode->m_index);
3473
3474	/* "node" and "node_2" have both now been removed
3475	from the worklist; we should not process them.
3476
3477	"merged_enode" may be a new node; if so it will be
3478	processed in a subsequent iteration.
3479	Alternatively, "merged_enode" could be an existing
3480	node; one way the latter can
3481	happen is if we end up merging a succession of
3482	similar nodes into one. */
3483
3484	/* If merged_node is one of the two we were merging,
3485	add it back to the worklist to ensure it gets
3486	processed.
3487
3488	Add edges from the merged nodes to it (but not a
3489	self-edge). */
3490	if (merged_enode == node)
3491	m_worklist.add_node (enode: merged_enode);
3492	else
3493	{
3494	add_edge (src: node, dest: merged_enode, NULL, could_do_work: false);
3495	node->set_status (exploded_node::STATUS_MERGER);
3496	}
3497
3498	if (merged_enode == node_2)
3499	m_worklist.add_node (enode: merged_enode);
3500	else
3501	{
3502	add_edge (src: node_2, dest: merged_enode, NULL, could_do_work: false);
3503	node_2->set_status (exploded_node::STATUS_MERGER);
3504	}
3505
3506	continue;
3507	}
3508	}
3509
3510	/* TODO: should we attempt more than two nodes,
3511	or just do pairs of nodes? (and hope that we get
3512	a cascade of mergers). */
3513	}
3514	}
3515
3516	process_node (node);
3517
3518	handle_limit:
3519	/* Impose a hard limit on the number of exploded nodes, to ensure
3520	that the analysis terminates in the face of pathological state
3521	explosion (or bugs).
3522
3523	Specifically, the limit is on the number of PK_AFTER_SUPERNODE
3524	exploded nodes, looking at supernode exit events.
3525
3526	We use exit rather than entry since there can be multiple
3527	entry ENs, one per phi; the number of PK_AFTER_SUPERNODE ought
3528	to be equivalent to the number of supernodes multiplied by the
3529	number of states. */
3530	const int limit = m_sg.num_nodes () * param_analyzer_bb_explosion_factor;
3531	if (m_global_stats.m_num_nodes[PK_AFTER_SUPERNODE] > limit)
3532	{
3533	if (logger)
3534	logger->log (fmt: "bailing out; too many nodes");
3535	warning_at (node->get_point ().get_location (),
3536	OPT_Wanalyzer_too_complex,
3537	"analysis bailed out early"
3538	" (%i 'after-snode' enodes; %i enodes)",
3539	m_global_stats.m_num_nodes[PK_AFTER_SUPERNODE],
3540	m_nodes.length ());
3541	return;
3542	}
3543	}
3544	}
3545
3546	/* Attempt to process a consecutive run of sufficiently-similar nodes in
3547	the worklist at a CFG join-point (having already popped ENODE from the
3548	head of the worklist).
3549
3550	If ENODE's point is of the form (before-supernode, SNODE) and the next
3551	nodes in the worklist are a consecutive run of enodes of the same form,
3552	for the same supernode as ENODE (but potentially from different in-edges),
3553	process them all together, setting their status to STATUS_BULK_MERGED,
3554	and return true.
3555	Otherwise, return false, in which case ENODE must be processed in the
3556	normal way.
3557
3558	When processing them all together, generate successor states based
3559	on phi nodes for the appropriate CFG edges, and then attempt to merge
3560	these states into a minimal set of merged successor states, partitioning
3561	the inputs by merged successor state.
3562
3563	Create new exploded nodes for all of the merged states, and add edges
3564	connecting the input enodes to the corresponding merger exploded nodes.
3565
3566	We hope we have a much smaller number of merged successor states
3567	compared to the number of input enodes - ideally just one,
3568	if all successor states can be merged.
3569
3570	Processing and merging many together as one operation rather than as
3571	pairs avoids scaling issues where per-pair mergers could bloat the
3572	graph with merger nodes (especially so after switch statements). */
3573
3574	bool
3575	exploded_graph::
3576	maybe_process_run_of_before_supernode_enodes (exploded_node *enode)
3577	{
3578	/* A struct for tracking per-input state. */
3579	struct item
3580	{
3581	item (exploded_node *input_enode)
3582	: m_input_enode (input_enode),
3583	m_processed_state (input_enode->get_state ()),
3584	m_merger_idx (-1)
3585	{}
3586
3587	exploded_node *m_input_enode;
3588	program_state m_processed_state;
3589	int m_merger_idx;
3590	};
3591
3592	gcc_assert (enode->get_status () == exploded_node::STATUS_WORKLIST);
3593	gcc_assert (enode->m_succs.length () == 0);
3594
3595	const program_point &point = enode->get_point ();
3596
3597	if (point.get_kind () != PK_BEFORE_SUPERNODE)
3598	return false;
3599
3600	const supernode *snode = point.get_supernode ();
3601
3602	logger * const logger = get_logger ();
3603	LOG_SCOPE (logger);
3604
3605	/* Find a run of enodes in the worklist that are before the same supernode,
3606	but potentially from different in-edges. */
3607	auto_vec <exploded_node *> enodes;
3608	enodes.safe_push (obj: enode);
3609	while (exploded_node *enode_2 = m_worklist.peek_next ())
3610	{
3611	gcc_assert (enode_2->get_status ()
3612	== exploded_node::STATUS_WORKLIST);
3613	gcc_assert (enode_2->m_succs.length () == 0);
3614
3615	const program_point &point_2 = enode_2->get_point ();
3616
3617	if (point_2.get_kind () == PK_BEFORE_SUPERNODE
3618	&& point_2.get_supernode () == snode
3619	&& &point_2.get_call_string () == &point.get_call_string ())
3620	{
3621	enodes.safe_push (obj: enode_2);
3622	m_worklist.take_next ();
3623	}
3624	else
3625	break;
3626	}
3627
3628	/* If the only node is ENODE, then give up. */
3629	if (enodes.length () == 1)
3630	return false;
3631
3632	if (logger)
3633	logger->log (fmt: "got run of %i enodes for SN: %i",
3634	enodes.length (), snode->m_index);
3635
3636	/* All of these enodes have a shared successor point (even if they
3637	were for different in-edges). */
3638	program_point next_point (point.get_next ());
3639
3640	/* Calculate the successor state for each enode in enodes. */
3641	auto_delete_vec<item> items (enodes.length ());
3642	unsigned i;
3643	exploded_node *iter_enode;
3644	FOR_EACH_VEC_ELT (enodes, i, iter_enode)
3645	{
3646	item *it = new item (iter_enode);
3647	items.quick_push (obj: it);
3648	const program_state &state = iter_enode->get_state ();
3649	program_state *next_state = &it->m_processed_state;
3650	next_state->validate (ext_state: m_ext_state);
3651	const program_point &iter_point = iter_enode->get_point ();
3652	if (const superedge *iter_sedge = iter_point.get_from_edge ())
3653	{
3654	uncertainty_t uncertainty;
3655	impl_region_model_context ctxt (*this, iter_enode,
3656	&state, next_state,
3657	&uncertainty, NULL, NULL);
3658	const cfg_superedge *last_cfg_superedge
3659	= iter_sedge->dyn_cast_cfg_superedge ();
3660	if (last_cfg_superedge)
3661	next_state->m_region_model->update_for_phis
3662	(snode, last_cfg_superedge, ctxt: &ctxt);
3663	}
3664	next_state->validate (ext_state: m_ext_state);
3665	}
3666
3667	/* Attempt to partition the items into a set of merged states.
3668	We hope we have a much smaller number of merged states
3669	compared to the number of input enodes - ideally just one,
3670	if all can be merged. */
3671	auto_delete_vec <program_state> merged_states;
3672	auto_vec<item *> first_item_for_each_merged_state;
3673	item *it;
3674	FOR_EACH_VEC_ELT (items, i, it)
3675	{
3676	const program_state &it_state = it->m_processed_state;
3677	program_state *merged_state;
3678	unsigned iter_merger_idx;
3679	FOR_EACH_VEC_ELT (merged_states, iter_merger_idx, merged_state)
3680	{
3681	merged_state->validate (ext_state: m_ext_state);
3682	program_state merge (m_ext_state);
3683	if (it_state.can_merge_with_p (other: *merged_state, ext_state: m_ext_state,
3684	point: next_point, out: &merge))
3685	{
3686	*merged_state = merge;
3687	merged_state->validate (ext_state: m_ext_state);
3688	it->m_merger_idx = iter_merger_idx;
3689	if (logger)
3690	logger->log (fmt: "reusing merger state %i for item %i (EN: %i)",
3691	it->m_merger_idx, i, it->m_input_enode->m_index);
3692	goto got_merger;
3693	}
3694	}
3695	/* If it couldn't be merged with any existing merged_states,
3696	create a new one. */
3697	if (it->m_merger_idx == -1)
3698	{
3699	it->m_merger_idx = merged_states.length ();
3700	merged_states.safe_push (obj: new program_state (it_state));
3701	first_item_for_each_merged_state.safe_push (obj: it);
3702	if (logger)
3703	logger->log (fmt: "using new merger state %i for item %i (EN: %i)",
3704	it->m_merger_idx, i, it->m_input_enode->m_index);
3705	}
3706	got_merger:
3707	gcc_assert (it->m_merger_idx >= 0);
3708	gcc_assert ((unsigned)it->m_merger_idx < merged_states.length ());
3709	}
3710
3711	/* Create merger nodes. */
3712	auto_vec<exploded_node *> next_enodes (merged_states.length ());
3713	program_state *merged_state;
3714	FOR_EACH_VEC_ELT (merged_states, i, merged_state)
3715	{
3716	exploded_node *src_enode
3717	= first_item_for_each_merged_state[i]->m_input_enode;
3718	exploded_node *next
3719	= get_or_create_node (point: next_point, state: *merged_state, enode_for_diag: src_enode);
3720	/* "next" could be NULL; we handle that when adding the edges below. */
3721	next_enodes.quick_push (obj: next);
3722	if (logger)
3723	{
3724	if (next)
3725	logger->log (fmt: "using EN: %i for merger state %i", next->m_index, i);
3726	else
3727	logger->log (fmt: "using NULL enode for merger state %i", i);
3728	}
3729	}
3730
3731	/* Create edges from each input enode to the appropriate successor enode.
3732	Update the status of the now-processed input enodes. */
3733	FOR_EACH_VEC_ELT (items, i, it)
3734	{
3735	exploded_node *next = next_enodes[it->m_merger_idx];
3736	if (next)
3737	add_edge (src: it->m_input_enode, dest: next, NULL,
3738	could_do_work: false); /* no "work" is done during merger. */
3739	it->m_input_enode->set_status (exploded_node::STATUS_BULK_MERGED);
3740	}
3741
3742	if (logger)
3743	logger->log (fmt: "merged %i in-enodes into %i out-enode(s) at SN: %i",
3744	items.length (), merged_states.length (), snode->m_index);
3745
3746	return true;
3747	}
3748
3749	/* Return true if STMT must appear at the start of its exploded node, and
3750	thus we can't consolidate its effects within a run of other statements,
3751	where PREV_STMT was the previous statement. */
3752
3753	static bool
3754	stmt_requires_new_enode_p (const gimple *stmt,
3755	const gimple *prev_stmt)
3756	{
3757	if (const gcall *call = dyn_cast <const gcall *> (p: stmt))
3758	{
3759	/* Stop consolidating at calls to
3760	"__analyzer_dump_exploded_nodes", so they always appear at the
3761	start of an exploded_node. */
3762	if (is_special_named_call_p (call, funcname: "__analyzer_dump_exploded_nodes",
3763	num_args: 1))
3764	return true;
3765
3766	/* sm-signal.cc injects an additional custom eedge at "signal" calls
3767	from the registration enode to the handler enode, separate from the
3768	regular next state, which defeats the "detect state change" logic
3769	in process_node. Work around this via special-casing, to ensure
3770	we split the enode immediately before any "signal" call. */
3771	if (is_special_named_call_p (call, funcname: "signal", num_args: 2))
3772	return true;
3773	}
3774
3775	/* If we had a PREV_STMT with an unknown location, and this stmt
3776	has a known location, then if a state change happens here, it
3777	could be consolidated into PREV_STMT, giving us an event with
3778	no location. Ensure that STMT gets its own exploded_node to
3779	avoid this. */
3780	if (get_pure_location (loc: prev_stmt->location) == UNKNOWN_LOCATION
3781	&& get_pure_location (loc: stmt->location) != UNKNOWN_LOCATION)
3782	return true;
3783
3784	return false;
3785	}
3786
3787	/* Return true if OLD_STATE and NEW_STATE are sufficiently different that
3788	we should split enodes and create an exploded_edge separating them
3789	(which makes it easier to identify state changes of intereset when
3790	constructing checker_paths). */
3791
3792	static bool
3793	state_change_requires_new_enode_p (const program_state &old_state,
3794	const program_state &new_state)
3795	{
3796	/* Changes in dynamic extents signify creations of heap/alloca regions
3797	and resizings of heap regions; likely to be of interest in
3798	diagnostic paths. */
3799	if (old_state.m_region_model->get_dynamic_extents ()
3800	!= new_state.m_region_model->get_dynamic_extents ())
3801	return true;
3802
3803	/* Changes in sm-state are of interest. */
3804	int sm_idx;
3805	sm_state_map *smap;
3806	FOR_EACH_VEC_ELT (old_state.m_checker_states, sm_idx, smap)
3807	{
3808	const sm_state_map *old_smap = old_state.m_checker_states[sm_idx];
3809	const sm_state_map *new_smap = new_state.m_checker_states[sm_idx];
3810	if (*old_smap != *new_smap)
3811	return true;
3812	}
3813
3814	return false;
3815	}
3816
3817	/* Create enodes and eedges for the function calls that doesn't have an
3818	underlying call superedge.
3819
3820	Such case occurs when GCC's middle end didn't know which function to
3821	call but the analyzer does (with the help of current state).
3822
3823	Some example such calls are dynamically dispatched calls to virtual
3824	functions or calls that happen via function pointer. */
3825
3826	bool
3827	exploded_graph::maybe_create_dynamic_call (const gcall *call,
3828	tree fn_decl,
3829	exploded_node *node,
3830	program_state next_state,
3831	program_point &next_point,
3832	uncertainty_t *uncertainty,
3833	logger *logger)
3834	{
3835	LOG_FUNC (logger);
3836
3837	const program_point *this_point = &node->get_point ();
3838	function *fun = DECL_STRUCT_FUNCTION (fn_decl);
3839	if (fun)
3840	{
3841	const supergraph &sg = this->get_supergraph ();
3842	supernode *sn_entry = sg.get_node_for_function_entry (fun: *fun);
3843	supernode *sn_exit = sg.get_node_for_function_exit (fun: *fun);
3844
3845	program_point new_point
3846	= program_point::before_supernode (supernode: sn_entry,
3847	NULL,
3848	call_string: this_point->get_call_string ());
3849
3850	new_point.push_to_call_stack (caller: sn_exit,
3851	callee: next_point.get_supernode());
3852
3853	/* Impose a maximum recursion depth and don't analyze paths
3854	that exceed it further.
3855	This is something of a blunt workaround, but it only
3856	applies to recursion (and mutual recursion), not to
3857	general call stacks. */
3858	if (new_point.get_call_string ().calc_recursion_depth ()
3859	> param_analyzer_max_recursion_depth)
3860	{
3861	if (logger)
3862	logger->log (fmt: "rejecting call edge: recursion limit exceeded");
3863	return false;
3864	}
3865
3866	next_state.push_call (eg&: *this, enode: node, call_stmt: call, uncertainty);
3867
3868	if (next_state.m_valid)
3869	{
3870	if (logger)
3871	logger->log (fmt: "Discovered call to %s [SN: %i -> SN: %i]",
3872	function_name(fun),
3873	this_point->get_supernode ()->m_index,
3874	sn_entry->m_index);
3875
3876	exploded_node *enode = get_or_create_node (point: new_point,
3877	state: next_state,
3878	enode_for_diag: node);
3879	if (enode)
3880	add_edge (src: node,dest: enode, NULL,
3881	could_do_work: false, /* No work is done by the call itself. */
3882	custom_info: make_unique<dynamic_call_info_t> (args&: call));
3883	return true;
3884	}
3885	}
3886	return false;
3887	}
3888
3889	/* Subclass of path_context for use within exploded_graph::process_node,
3890	so that we can split states e.g. at "realloc" calls. */
3891
3892	class impl_path_context : public path_context
3893	{
3894	public:
3895	impl_path_context (const program_state *cur_state,
3896	logger *logger)
3897	: m_cur_state (cur_state),
3898	m_logger (logger),
3899	m_terminate_path (false)
3900	{
3901	}
3902
3903	bool bifurcation_p () const
3904	{
3905	return m_custom_eedge_infos.length () > 0;
3906	}
3907
3908	const program_state &get_state_at_bifurcation () const
3909	{
3910	gcc_assert (m_state_at_bifurcation);
3911	return *m_state_at_bifurcation;
3912	}
3913
3914	void
3915	bifurcate (std::unique_ptr<custom_edge_info> info) final override
3916	{
3917	if (m_logger)
3918	m_logger->log (fmt: "bifurcating path");
3919
3920	if (m_state_at_bifurcation)
3921	/* Verify that the state at bifurcation is consistent when we
3922	split into multiple out-edges. */
3923	gcc_assert (*m_state_at_bifurcation == *m_cur_state);
3924	else
3925	/* Take a copy of the cur_state at the moment when bifurcation
3926	happens. */
3927	m_state_at_bifurcation
3928	= std::unique_ptr<program_state> (new program_state (*m_cur_state));
3929
3930	/* Take ownership of INFO. */
3931	m_custom_eedge_infos.safe_push (obj: info.release ());
3932	}
3933
3934	void terminate_path () final override
3935	{
3936	if (m_logger)
3937	m_logger->log (fmt: "terminating path");
3938	m_terminate_path = true;
3939	}
3940
3941	bool terminate_path_p () const final override
3942	{
3943	return m_terminate_path;
3944	}
3945
3946	const vec<custom_edge_info *> & get_custom_eedge_infos ()
3947	{
3948	return m_custom_eedge_infos;
3949	}
3950
3951	private:
3952	const program_state *m_cur_state;
3953
3954	logger *m_logger;
3955
3956	/* Lazily-created copy of the state before the split. */
3957	std::unique_ptr<program_state> m_state_at_bifurcation;
3958
3959	auto_vec <custom_edge_info *> m_custom_eedge_infos;
3960
3961	bool m_terminate_path;
3962	};
3963
3964	/* A subclass of pending_diagnostic for complaining about jumps through NULL
3965	function pointers. */
3966
3967	class jump_through_null : public pending_diagnostic_subclass<jump_through_null>
3968	{
3969	public:
3970	jump_through_null (const gcall *call)
3971	: m_call (call)
3972	{}
3973
3974	const char *get_kind () const final override
3975	{
3976	return "jump_through_null";
3977	}
3978
3979	bool operator== (const jump_through_null &other) const
3980	{
3981	return m_call == other.m_call;
3982	}
3983
3984	int get_controlling_option () const final override
3985	{
3986	return OPT_Wanalyzer_jump_through_null;
3987	}
3988
3989	bool emit (diagnostic_emission_context &ctxt) final override
3990	{
3991	return ctxt.warn ("jump through null pointer");
3992	}
3993
3994	label_text describe_final_event (const evdesc::final_event &ev) final override
3995	{
3996	return ev.formatted_print (fmt: "jump through null pointer here");
3997	}
3998
3999	private:
4000	const gcall *m_call;
4001	};
4002
4003	/* The core of exploded_graph::process_worklist (the main analysis loop),
4004	handling one node in the worklist.
4005
4006	Get successor <point, state> pairs for NODE, calling get_or_create on
4007	them, and adding an exploded_edge to each successors.
4008
4009	Freshly-created nodes will be added to the worklist. */
4010
4011	void
4012	exploded_graph::process_node (exploded_node *node)
4013	{
4014	logger * const logger = get_logger ();
4015	LOG_FUNC_1 (logger, "EN: %i", node->m_index);
4016
4017	node->set_status (exploded_node::STATUS_PROCESSED);
4018
4019	const program_point &point = node->get_point ();
4020
4021	/* Update cfun and input_location in case of an ICE: make it easier to
4022	track down which source construct we're failing to handle. */
4023	auto_cfun sentinel (node->get_function ());
4024	const gimple *stmt = point.get_stmt ();
4025	if (stmt)
4026	input_location = stmt->location;
4027
4028	const program_state &state = node->get_state ();
4029	if (logger)
4030	{
4031	pretty_printer *pp = logger->get_printer ();
4032	logger->start_log_line ();
4033	pp_string (pp, "point: ");
4034	point.print (pp, f: format (false));
4035	pp_string (pp, ", state: ");
4036	state.dump_to_pp (ext_state: m_ext_state, simple: true, multiline: false, pp);
4037	logger->end_log_line ();
4038	}
4039
4040	switch (point.get_kind ())
4041	{
4042	default:
4043	gcc_unreachable ();
4044	case PK_ORIGIN:
4045	/* This node exists to simplify finding the shortest path
4046	to an exploded_node. */
4047	break;
4048
4049	case PK_BEFORE_SUPERNODE:
4050	{
4051	program_state next_state (state);
4052	uncertainty_t uncertainty;
4053
4054	if (point.get_from_edge ())
4055	{
4056	impl_region_model_context ctxt (*this, node,
4057	&state, &next_state,
4058	&uncertainty, NULL, NULL);
4059	const cfg_superedge *last_cfg_superedge
4060	= point.get_from_edge ()->dyn_cast_cfg_superedge ();
4061	if (last_cfg_superedge)
4062	next_state.m_region_model->update_for_phis
4063	(snode: node->get_supernode (),
4064	last_cfg_superedge,
4065	ctxt: &ctxt);
4066	program_state::detect_leaks (src_state: state, dest_state: next_state, NULL,
4067	ext_state: get_ext_state (), ctxt: &ctxt);
4068	}
4069
4070	program_point next_point (point.get_next ());
4071	exploded_node *next = get_or_create_node (point: next_point, state: next_state, enode_for_diag: node);
4072	if (next)
4073	add_edge (src: node, dest: next, NULL,
4074	could_do_work: false); /* Assume no work is done at phi nodes. */
4075	}
4076	break;
4077	case PK_BEFORE_STMT:
4078	{
4079	/* Determine the effect of a run of one or more statements
4080	within one supernode, generating an edge to the program_point
4081	after the last statement that's processed.
4082
4083	Stop iterating statements and thus consolidating into one enode
4084	when:
4085	- reaching the end of the statements in the supernode
4086	- if an sm-state-change occurs (so that it gets its own
4087	exploded_node)
4088	- if "-fanalyzer-fine-grained" is active
4089	- encountering certain statements must appear at the start of
4090	their enode (for which stmt_requires_new_enode_p returns true)
4091
4092	Update next_state in-place, to get the result of the one
4093	or more stmts that are processed.
4094
4095	Split the node in-place if an sm-state-change occurs, so that
4096	the sm-state-change occurs on an edge where the src enode has
4097	exactly one stmt, the one that caused the change. */
4098	program_state next_state (state);
4099
4100	impl_path_context path_ctxt (&next_state, logger);
4101
4102	bool could_have_done_work = false;
4103	uncertainty_t uncertainty;
4104	const supernode *snode = point.get_supernode ();
4105	unsigned stmt_idx;
4106	const gimple *prev_stmt = NULL;
4107	for (stmt_idx = point.get_stmt_idx ();
4108	stmt_idx < snode->m_stmts.length ();
4109	stmt_idx++)
4110	{
4111	const gimple *stmt = snode->m_stmts[stmt_idx];
4112
4113	if (stmt_idx > point.get_stmt_idx ())
4114	if (stmt_requires_new_enode_p (stmt, prev_stmt))
4115	{
4116	stmt_idx--;
4117	break;
4118	}
4119	prev_stmt = stmt;
4120
4121	program_state old_state (next_state);
4122
4123	/* Process the stmt. */
4124	exploded_node::on_stmt_flags flags
4125	= node->on_stmt (eg&: *this, snode, stmt, state: &next_state, uncertainty: &uncertainty,
4126	out_could_have_done_work: &could_have_done_work, path_ctxt: &path_ctxt);
4127	node->m_num_processed_stmts++;
4128
4129	/* If flags.m_terminate_path, stop analyzing; any nodes/edges
4130	will have been added by on_stmt (e.g. for handling longjmp). */
4131	if (flags.m_terminate_path)
4132	return;
4133
4134	if (next_state.m_region_model)
4135	{
4136	impl_region_model_context ctxt (*this, node,
4137	&old_state, &next_state,
4138	&uncertainty, NULL, stmt);
4139	program_state::detect_leaks (src_state: old_state, dest_state: next_state, NULL,
4140	ext_state: get_ext_state (), ctxt: &ctxt);
4141	}
4142
4143	unsigned next_idx = stmt_idx + 1;
4144	program_point next_point
4145	= (next_idx < point.get_supernode ()->m_stmts.length ()
4146	? program_point::before_stmt (supernode: point.get_supernode (), stmt_idx: next_idx,
4147	call_string: point.get_call_string ())
4148	: program_point::after_supernode (supernode: point.get_supernode (),
4149	call_string: point.get_call_string ()));
4150	next_state = next_state.prune_for_point (eg&: *this, point: next_point, enode_for_diag: node,
4151	uncertainty: &uncertainty);
4152
4153	if (flag_analyzer_fine_grained
4154	|| state_change_requires_new_enode_p (old_state, new_state: next_state)
4155	|| path_ctxt.bifurcation_p ()
4156	|| path_ctxt.terminate_path_p ())
4157	{
4158	program_point split_point
4159	= program_point::before_stmt (supernode: point.get_supernode (),
4160	stmt_idx,
4161	call_string: point.get_call_string ());
4162	if (split_point != node->get_point ())
4163	{
4164	/* If we're not at the start of NODE, split the enode at
4165	this stmt, so we have:
4166	node -> split_enode
4167	so that when split_enode is processed the next edge
4168	we add will be:
4169	split_enode -> next
4170	and any state change will effectively occur on that
4171	latter edge, and split_enode will contain just stmt. */
4172	if (logger)
4173	logger->log (fmt: "getting split_enode");
4174	exploded_node *split_enode
4175	= get_or_create_node (point: split_point, state: old_state, enode_for_diag: node);
4176	if (!split_enode)
4177	return;
4178	/* "stmt" will be reprocessed when split_enode is
4179	processed. */
4180	node->m_num_processed_stmts--;
4181	if (logger)
4182	logger->log (fmt: "creating edge to split_enode");
4183	add_edge (src: node, dest: split_enode, NULL, could_do_work: could_have_done_work);
4184	return;
4185	}
4186	else
4187	/* If we're at the start of NODE, stop iterating,
4188	so that an edge will be created from NODE to
4189	(next_point, next_state) below. */
4190	break;
4191	}
4192	}
4193	unsigned next_idx = stmt_idx + 1;
4194	program_point next_point
4195	= (next_idx < point.get_supernode ()->m_stmts.length ()
4196	? program_point::before_stmt (supernode: point.get_supernode (), stmt_idx: next_idx,
4197	call_string: point.get_call_string ())
4198	: program_point::after_supernode (supernode: point.get_supernode (),
4199	call_string: point.get_call_string ()));
4200	if (path_ctxt.terminate_path_p ())
4201	{
4202	if (logger)
4203	logger->log (fmt: "not adding node: terminating path");
4204	}
4205	else
4206	{
4207	exploded_node *next
4208	= get_or_create_node (point: next_point, state: next_state, enode_for_diag: node);
4209	if (next)
4210	add_edge (src: node, dest: next, NULL, could_do_work: could_have_done_work);
4211	}
4212
4213	/* If we have custom edge infos, "bifurcate" the state
4214	accordingly, potentially creating a new state/enode/eedge
4215	instances. For example, to handle a "realloc" call, we
4216	might split into 3 states, for the "failure",
4217	"resizing in place", and "moving to a new buffer" cases. */
4218	for (auto edge_info_iter : path_ctxt.get_custom_eedge_infos ())
4219	{
4220	/* Take ownership of the edge infos from the path_ctxt. */
4221	std::unique_ptr<custom_edge_info> edge_info (edge_info_iter);
4222	if (logger)
4223	{
4224	logger->start_log_line ();
4225	logger->log_partial (fmt: "bifurcating for edge: ");
4226	edge_info->print (pp: logger->get_printer ());
4227	logger->end_log_line ();
4228	}
4229	program_state bifurcated_new_state
4230	(path_ctxt.get_state_at_bifurcation ());
4231
4232	/* Apply edge_info to state. */
4233	impl_region_model_context
4234	bifurcation_ctxt (*this,
4235	node, // enode_for_diag
4236	&path_ctxt.get_state_at_bifurcation (),
4237	&bifurcated_new_state,
4238	NULL, // uncertainty_t *uncertainty
4239	NULL, // path_context *path_ctxt
4240	stmt);
4241	if (edge_info->update_state (state: &bifurcated_new_state,
4242	NULL, /* no exploded_edge yet. */
4243	ctxt: &bifurcation_ctxt))
4244	{
4245	exploded_node *next2
4246	= get_or_create_node (point: next_point, state: bifurcated_new_state, enode_for_diag: node);
4247	if (next2)
4248	add_edge (src: node, dest: next2, NULL,
4249	could_do_work: true /* assume that work could be done */,
4250	custom_info: std::move (edge_info));
4251	}
4252	else
4253	{
4254	if (logger)
4255	logger->log (fmt: "infeasible state, not adding node");
4256	}
4257	}
4258	}
4259	break;
4260	case PK_AFTER_SUPERNODE:
4261	{
4262	bool found_a_superedge = false;
4263	bool is_an_exit_block = false;
4264	/* If this is an EXIT BB, detect leaks, and potentially
4265	create a function summary. */
4266	if (point.get_supernode ()->return_p ())
4267	{
4268	is_an_exit_block = true;
4269	node->detect_leaks (eg&: *this);
4270	if (flag_analyzer_call_summaries
4271	&& point.get_call_string ().empty_p ())
4272	{
4273	/* TODO: create function summary
4274	There can be more than one; each corresponds to a different
4275	final enode in the function. */
4276	if (logger)
4277	{
4278	pretty_printer *pp = logger->get_printer ();
4279	logger->start_log_line ();
4280	logger->log_partial
4281	(fmt: "would create function summary for %qE; state: ",
4282	point.get_fndecl ());
4283	state.dump_to_pp (ext_state: m_ext_state, simple: true, multiline: false, pp);
4284	logger->end_log_line ();
4285	}
4286	per_function_data *per_fn_data
4287	= get_or_create_per_function_data (fun: point.get_function ());
4288	per_fn_data->add_call_summary (node);
4289	}
4290	}
4291	/* Traverse into successors of the supernode. */
4292	int i;
4293	superedge *succ;
4294	FOR_EACH_VEC_ELT (point.get_supernode ()->m_succs, i, succ)
4295	{
4296	found_a_superedge = true;
4297	if (logger)
4298	{
4299	label_text succ_desc (succ->get_description (user_facing: false));
4300	logger->log (fmt: "considering SN: %i -> SN: %i (%s)",
4301	succ->m_src->m_index, succ->m_dest->m_index,
4302	succ_desc.get ());
4303	}
4304
4305	program_point next_point
4306	= program_point::before_supernode (supernode: succ->m_dest, from_edge: succ,
4307	call_string: point.get_call_string ());
4308	program_state next_state (state);
4309	uncertainty_t uncertainty;
4310
4311	/* Make use the current state and try to discover and analyse
4312	indirect function calls (a call that doesn't have an underlying
4313	cgraph edge representing call).
4314
4315	Some examples of such calls are virtual function calls
4316	and calls that happen via a function pointer. */
4317	if (succ->m_kind == SUPEREDGE_INTRAPROCEDURAL_CALL
4318	&& !(succ->get_any_callgraph_edge ()))
4319	{
4320	const gcall *call
4321	= point.get_supernode ()->get_final_call ();
4322
4323	impl_region_model_context ctxt (*this,
4324	node,
4325	&state,
4326	&next_state,
4327	&uncertainty,
4328	NULL,
4329	point.get_stmt());
4330
4331	region_model *model = state.m_region_model;
4332	bool call_discovered = false;
4333
4334	if (tree fn_decl = model->get_fndecl_for_call (call, ctxt: &ctxt))
4335	call_discovered = maybe_create_dynamic_call (call,
4336	fn_decl,
4337	node,
4338	next_state,
4339	next_point,
4340	uncertainty: &uncertainty,
4341	logger);
4342	if (!call_discovered)
4343	{
4344	/* Check for jump through NULL. */
4345	if (tree fn_ptr = gimple_call_fn (gs: call))
4346	{
4347	const svalue *fn_ptr_sval
4348	= model->get_rvalue (expr: fn_ptr, ctxt: &ctxt);
4349	if (fn_ptr_sval->all_zeroes_p ())
4350	ctxt.warn (d: make_unique<jump_through_null> (args&: call));
4351	}
4352
4353	/* An unknown function or a special function was called
4354	at this point, in such case, don't terminate the
4355	analysis of the current function.
4356
4357	The analyzer handles calls to such functions while
4358	analysing the stmt itself, so the function call
4359	must have been handled by the anlyzer till now. */
4360	exploded_node *next
4361	= get_or_create_node (point: next_point,
4362	state: next_state,
4363	enode_for_diag: node);
4364	if (next)
4365	add_edge (src: node, dest: next, sedge: succ,
4366	could_do_work: true /* assume that work is done */);
4367	}
4368	}
4369
4370	if (!node->on_edge (eg&: *this, succ, next_point: &next_point, next_state: &next_state,
4371	uncertainty: &uncertainty))
4372	{
4373	if (logger)
4374	logger->log (fmt: "skipping impossible edge to SN: %i",
4375	succ->m_dest->m_index);
4376	continue;
4377	}
4378	exploded_node *next = get_or_create_node (point: next_point, state: next_state,
4379	enode_for_diag: node);
4380	if (next)
4381	{
4382	add_edge (src: node, dest: next, sedge: succ, could_do_work: false);
4383
4384	/* We might have a function entrypoint. */
4385	detect_infinite_recursion (enode: next);
4386	}
4387	}
4388
4389	/* Return from the calls which doesn't have a return superedge.
4390	Such case occurs when GCC's middle end didn't knew which function to
4391	call but analyzer did. */
4392	if ((is_an_exit_block && !found_a_superedge)
4393	&& (!point.get_call_string ().empty_p ()))
4394	{
4395	const call_string &cs = point.get_call_string ();
4396	program_point next_point
4397	= program_point::before_supernode (supernode: cs.get_caller_node (),
4398	NULL,
4399	call_string: cs);
4400	program_state next_state (state);
4401	uncertainty_t uncertainty;
4402
4403	const gcall *call
4404	= next_point.get_supernode ()->get_returning_call ();
4405
4406	if (call)
4407	next_state.returning_call (eg&: *this, enode: node, call_stmt: call, uncertainty: &uncertainty);
4408
4409	if (next_state.m_valid)
4410	{
4411	next_point.pop_from_call_stack ();
4412	exploded_node *enode = get_or_create_node (point: next_point,
4413	state: next_state,
4414	enode_for_diag: node);
4415	if (enode)
4416	add_edge (src: node, dest: enode, NULL, could_do_work: false,
4417	custom_info: make_unique<dynamic_call_info_t> (args&: call, args: true));
4418	}
4419	}
4420	}
4421	break;
4422	}
4423	}
4424
4425	/* Ensure that this graph has a stats instance for FN, return it.
4426	FN can be NULL, in which case a stats instances is returned covering
4427	"functionless" parts of the graph (the origin node). */
4428
4429	stats *
4430	exploded_graph::get_or_create_function_stats (function *fn)
4431	{
4432	if (!fn)
4433	return &m_functionless_stats;
4434
4435	if (stats **slot = m_per_function_stats.get (k: fn))
4436	return *slot;
4437	else
4438	{
4439	int num_supernodes = fn ? n_basic_blocks_for_fn (fn) : 0;
4440	/* not quite the num supernodes, but nearly. */
4441	stats *new_stats = new stats (num_supernodes);
4442	m_per_function_stats.put (k: fn, v: new_stats);
4443	return new_stats;
4444	}
4445	}
4446
4447	/* Print bar charts to PP showing:
4448	- the number of enodes per function, and
4449	- for each function:
4450	- the number of enodes per supernode/BB
4451	- the number of excess enodes per supernode/BB beyond the
4452	per-program-point limit, if there were any. */
4453
4454	void
4455	exploded_graph::print_bar_charts (pretty_printer *pp) const
4456	{
4457	cgraph_node *cgnode;
4458
4459	pp_string (pp, "enodes per function:");
4460	pp_newline (pp);
4461	bar_chart enodes_per_function;
4462	FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
4463	{
4464	function *fn = cgnode->get_fun ();
4465	const stats * const *s_ptr
4466	= const_cast <function_stat_map_t &> (m_per_function_stats).get (k: fn);
4467	enodes_per_function.add_item (name: function_name (fn),
4468	value: s_ptr ? (*s_ptr)->get_total_enodes () : 0);
4469	}
4470	enodes_per_function.print (pp);
4471
4472	/* Accumulate number of enodes per supernode. */
4473	auto_vec<unsigned> enodes_per_supernode (m_sg.num_nodes ());
4474	for (int i = 0; i < m_sg.num_nodes (); i++)
4475	enodes_per_supernode.quick_push (obj: 0);
4476	int i;
4477	exploded_node *enode;
4478	FOR_EACH_VEC_ELT (m_nodes, i, enode)
4479	{
4480	const supernode *iter_snode = enode->get_supernode ();
4481	if (!iter_snode)
4482	continue;
4483	enodes_per_supernode[iter_snode->m_index]++;
4484	}
4485
4486	/* Accumulate excess enodes per supernode. */
4487	auto_vec<unsigned> excess_enodes_per_supernode (m_sg.num_nodes ());
4488	for (int i = 0; i < m_sg.num_nodes (); i++)
4489	excess_enodes_per_supernode.quick_push (obj: 0);
4490	for (point_map_t::iterator iter = m_per_point_data.begin ();
4491	iter != m_per_point_data.end (); ++iter)
4492	{
4493	const program_point *point = (*iter).first;
4494	const supernode *iter_snode = point->get_supernode ();
4495	if (!iter_snode)
4496	continue;
4497	const per_program_point_data *point_data = (*iter).second;
4498	excess_enodes_per_supernode[iter_snode->m_index]
4499	+= point_data->m_excess_enodes;
4500	}
4501
4502	/* Show per-function bar_charts of enodes per supernode/BB. */
4503	pp_string (pp, "per-function enodes per supernode/BB:");
4504	pp_newline (pp);
4505	FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
4506	{
4507	function *fn = cgnode->get_fun ();
4508	pp_printf (pp, "function: %qs", function_name (fn));
4509	pp_newline (pp);
4510
4511	bar_chart enodes_per_snode;
4512	bar_chart excess_enodes_per_snode;
4513	bool have_excess_enodes = false;
4514	for (int i = 0; i < m_sg.num_nodes (); i++)
4515	{
4516	const supernode *iter_snode = m_sg.get_node_by_index (idx: i);
4517	if (iter_snode->get_function () != fn)
4518	continue;
4519	pretty_printer tmp_pp;
4520	pp_printf (&tmp_pp, "sn %i (bb %i)",
4521	iter_snode->m_index, iter_snode->m_bb->index);
4522	enodes_per_snode.add_item (name: pp_formatted_text (&tmp_pp),
4523	value: enodes_per_supernode[iter_snode->m_index]);
4524	const int num_excess
4525	= excess_enodes_per_supernode[iter_snode->m_index];
4526	excess_enodes_per_snode.add_item (name: pp_formatted_text (&tmp_pp),
4527	value: num_excess);
4528	if (num_excess)
4529	have_excess_enodes = true;
4530	}
4531	enodes_per_snode.print (pp);
4532	if (have_excess_enodes)
4533	{
4534	pp_printf (pp, "EXCESS ENODES:");
4535	pp_newline (pp);
4536	excess_enodes_per_snode.print (pp);
4537	}
4538	}
4539	}
4540
4541	/* Write all stats information to this graph's logger, if any. */
4542
4543	void
4544	exploded_graph::log_stats () const
4545	{
4546	logger * const logger = get_logger ();
4547	if (!logger)
4548	return;
4549
4550	LOG_SCOPE (logger);
4551
4552	m_ext_state.get_engine ()->log_stats (logger);
4553
4554	logger->log (fmt: "m_sg.num_nodes (): %i", m_sg.num_nodes ());
4555	logger->log (fmt: "m_nodes.length (): %i", m_nodes.length ());
4556	logger->log (fmt: "m_edges.length (): %i", m_edges.length ());
4557	logger->log (fmt: "remaining enodes in worklist: %i", m_worklist.length ());
4558
4559	logger->log (fmt: "global stats:");
4560	m_global_stats.log (logger);
4561
4562	for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
4563	iter != m_per_function_stats.end ();
4564	++iter)
4565	{
4566	function *fn = (*iter).first;
4567	log_scope s (logger, function_name (fn));
4568	(*iter).second->log (logger);
4569	}
4570
4571	print_bar_charts (pp: logger->get_printer ());
4572	}
4573
4574	/* Dump all stats information to OUT. */
4575
4576	void
4577	exploded_graph::dump_stats (FILE *out) const
4578	{
4579	fprintf (stream: out, format: "m_sg.num_nodes (): %i\n", m_sg.num_nodes ());
4580	fprintf (stream: out, format: "m_nodes.length (): %i\n", m_nodes.length ());
4581	fprintf (stream: out, format: "m_edges.length (): %i\n", m_edges.length ());
4582	fprintf (stream: out, format: "remaining enodes in worklist: %i", m_worklist.length ());
4583
4584	fprintf (stream: out, format: "global stats:\n");
4585	m_global_stats.dump (out);
4586
4587	for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
4588	iter != m_per_function_stats.end ();
4589	++iter)
4590	{
4591	function *fn = (*iter).first;
4592	fprintf (stream: out, format: "function: %s\n", function_name (fn));
4593	(*iter).second->dump (out);
4594	}
4595
4596	fprintf (stream: out, format: "PK_AFTER_SUPERNODE per supernode:\n");
4597	for (unsigned i = 0; i < m_PK_AFTER_SUPERNODE_per_snode.length (); i++)
4598	fprintf (stream: out, format: " SN %i: %3i\n", i, m_PK_AFTER_SUPERNODE_per_snode[i]);
4599	}
4600
4601	void
4602	exploded_graph::dump_states_for_supernode (FILE *out,
4603	const supernode *snode) const
4604	{
4605	fprintf (stream: out, format: "PK_AFTER_SUPERNODE nodes for SN: %i\n", snode->m_index);
4606	int i;
4607	exploded_node *enode;
4608	int state_idx = 0;
4609	FOR_EACH_VEC_ELT (m_nodes, i, enode)
4610	{
4611	const supernode *iter_snode = enode->get_supernode ();
4612	if (enode->get_point ().get_kind () == PK_AFTER_SUPERNODE
4613	&& iter_snode == snode)
4614	{
4615	pretty_printer pp;
4616	pp_format_decoder (&pp) = default_tree_printer;
4617	enode->get_state ().dump_to_pp (ext_state: m_ext_state, simple: true, multiline: false, pp: &pp);
4618	fprintf (stream: out, format: "state %i: EN: %i\n %s\n",
4619	state_idx++, enode->m_index,
4620	pp_formatted_text (&pp));
4621	}
4622	}
4623	fprintf (stream: out, format: "#exploded_node for PK_AFTER_SUPERNODE for SN: %i = %i\n",
4624	snode->m_index, state_idx);
4625	}
4626
4627	/* Return a new json::object of the form
4628	{"nodes" : [objs for enodes],
4629	"edges" : [objs for eedges],
4630	"ext_state": object for extrinsic_state,
4631	"diagnostic_manager": object for diagnostic_manager}. */
4632
4633	json::object *
4634	exploded_graph::to_json () const
4635	{
4636	json::object *egraph_obj = new json::object ();
4637
4638	/* Nodes. */
4639	{
4640	json::array *nodes_arr = new json::array ();
4641	unsigned i;
4642	exploded_node *n;
4643	FOR_EACH_VEC_ELT (m_nodes, i, n)
4644	nodes_arr->append (v: n->to_json (ext_state: m_ext_state));
4645	egraph_obj->set (key: "nodes", v: nodes_arr);
4646	}
4647
4648	/* Edges. */
4649	{
4650	json::array *edges_arr = new json::array ();
4651	unsigned i;
4652	exploded_edge *n;
4653	FOR_EACH_VEC_ELT (m_edges, i, n)
4654	edges_arr->append (v: n->to_json ());
4655	egraph_obj->set (key: "edges", v: edges_arr);
4656	}
4657
4658	/* m_sg is JSONified at the top-level. */
4659
4660	egraph_obj->set (key: "ext_state", v: m_ext_state.to_json ());
4661	egraph_obj->set (key: "worklist", v: m_worklist.to_json ());
4662	egraph_obj->set (key: "diagnostic_manager", v: m_diagnostic_manager.to_json ());
4663
4664	/* The following fields aren't yet being JSONified:
4665	const state_purge_map *const m_purge_map;
4666	const analysis_plan &m_plan;
4667	stats m_global_stats;
4668	function_stat_map_t m_per_function_stats;
4669	stats m_functionless_stats;
4670	call_string_data_map_t m_per_call_string_data;
4671	auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode; */
4672
4673	return egraph_obj;
4674	}
4675
4676	/* class exploded_path. */
4677
4678	/* Copy ctor. */
4679
4680	exploded_path::exploded_path (const exploded_path &other)
4681	: m_edges (other.m_edges.length ())
4682	{
4683	int i;
4684	const exploded_edge *eedge;
4685	FOR_EACH_VEC_ELT (other.m_edges, i, eedge)
4686	m_edges.quick_push (obj: eedge);
4687	}
4688
4689	/* Look for the last use of SEARCH_STMT within this path.
4690	If found write the edge's index to *OUT_IDX and return true, otherwise
4691	return false. */
4692
4693	bool
4694	exploded_path::find_stmt_backwards (const gimple *search_stmt,
4695	int *out_idx) const
4696	{
4697	int i;
4698	const exploded_edge *eedge;
4699	FOR_EACH_VEC_ELT_REVERSE (m_edges, i, eedge)
4700	{
4701	const exploded_node *dst_node = eedge->m_dest;
4702	const program_point &dst_point = dst_node->get_point ();
4703	const gimple *stmt = dst_point.get_stmt ();
4704	if (stmt == search_stmt)
4705	{
4706	*out_idx = i;
4707	return true;
4708	}
4709	}
4710	return false;
4711	}
4712
4713	/* Get the final exploded_node in this path, which must be non-empty. */
4714
4715	exploded_node *
4716	exploded_path::get_final_enode () const
4717	{
4718	gcc_assert (m_edges.length () > 0);
4719	return m_edges[m_edges.length () - 1]->m_dest;
4720	}
4721
4722	/* Check state along this path, returning true if it is feasible.
4723	If OUT is non-NULL, and the path is infeasible, write a new
4724	feasibility_problem to *OUT. */
4725
4726	bool
4727	exploded_path::feasible_p (logger *logger,
4728	std::unique_ptr<feasibility_problem> *out,
4729	engine *eng, const exploded_graph *eg) const
4730	{
4731	LOG_SCOPE (logger);
4732
4733	feasibility_state state (eng->get_model_manager (),
4734	eg->get_supergraph ());
4735
4736	/* Traverse the path, updating this state. */
4737	for (unsigned edge_idx = 0; edge_idx < m_edges.length (); edge_idx++)
4738	{
4739	const exploded_edge *eedge = m_edges[edge_idx];
4740	if (logger)
4741	logger->log (fmt: "considering edge %i: EN:%i -> EN:%i",
4742	edge_idx,
4743	eedge->m_src->m_index,
4744	eedge->m_dest->m_index);
4745
4746	std::unique_ptr <rejected_constraint> rc;
4747	if (!state.maybe_update_for_edge (logger, eedge, ctxt: nullptr, out_rc: &rc))
4748	{
4749	gcc_assert (rc);
4750	if (out)
4751	{
4752	const exploded_node &src_enode = *eedge->m_src;
4753	const program_point &src_point = src_enode.get_point ();
4754	const gimple *last_stmt
4755	= src_point.get_supernode ()->get_last_stmt ();
4756	*out = ::make_unique<feasibility_problem> (args&: edge_idx, args: *eedge,
4757	args&: last_stmt,
4758	args: std::move (rc));
4759	}
4760	return false;
4761	}
4762
4763	if (logger)
4764	{
4765	logger->log (fmt: "state after edge %i: EN:%i -> EN:%i",
4766	edge_idx,
4767	eedge->m_src->m_index,
4768	eedge->m_dest->m_index);
4769	logger->start_log_line ();
4770	state.get_model ().dump_to_pp (pp: logger->get_printer (), simple: true, multiline: false);
4771	logger->end_log_line ();
4772	}
4773	}
4774
4775	return true;
4776	}
4777
4778	/* Dump this path in multiline form to PP.
4779	If EXT_STATE is non-NULL, then show the nodes. */
4780
4781	void
4782	exploded_path::dump_to_pp (pretty_printer *pp,
4783	const extrinsic_state *ext_state) const
4784	{
4785	for (unsigned i = 0; i < m_edges.length (); i++)
4786	{
4787	const exploded_edge *eedge = m_edges[i];
4788	pp_printf (pp, "m_edges[%i]: EN %i -> EN %i",
4789	i,
4790	eedge->m_src->m_index,
4791	eedge->m_dest->m_index);
4792	pp_newline (pp);
4793
4794	if (ext_state)
4795	eedge->m_dest->dump_to_pp (pp, ext_state: *ext_state);
4796	}
4797	}
4798
4799	/* Dump this path in multiline form to FP. */
4800
4801	void
4802	exploded_path::dump (FILE *fp, const extrinsic_state *ext_state) const
4803	{
4804	pretty_printer pp;
4805	pp_format_decoder (&pp) = default_tree_printer;
4806	pp_show_color (&pp) = pp_show_color (global_dc->printer);
4807	pp.buffer->stream = fp;
4808	dump_to_pp (pp: &pp, ext_state);
4809	pp_flush (&pp);
4810	}
4811
4812	/* Dump this path in multiline form to stderr. */
4813
4814	DEBUG_FUNCTION void
4815	exploded_path::dump (const extrinsic_state *ext_state) const
4816	{
4817	dump (stderr, ext_state);
4818	}
4819
4820	/* Dump this path verbosely to FILENAME. */
4821
4822	void
4823	exploded_path::dump_to_file (const char *filename,
4824	const extrinsic_state &ext_state) const
4825	{
4826	FILE *fp = fopen (filename: filename, modes: "w");
4827	if (!fp)
4828	return;
4829	pretty_printer pp;
4830	pp_format_decoder (&pp) = default_tree_printer;
4831	pp.buffer->stream = fp;
4832	dump_to_pp (pp: &pp, ext_state: &ext_state);
4833	pp_flush (&pp);
4834	fclose (stream: fp);
4835	}
4836
4837	/* class feasibility_problem. */
4838
4839	void
4840	feasibility_problem::dump_to_pp (pretty_printer *pp) const
4841	{
4842	pp_printf (pp, "edge from EN: %i to EN: %i",
4843	m_eedge.m_src->m_index, m_eedge.m_dest->m_index);
4844	if (m_rc)
4845	{
4846	pp_string (pp, "; rejected constraint: ");
4847	m_rc->dump_to_pp (pp);
4848	pp_string (pp, "; rmodel: ");
4849	m_rc->get_model ().dump_to_pp (pp, simple: true, multiline: false);
4850	}
4851	}
4852
4853	/* class feasibility_state. */
4854
4855	/* Ctor for feasibility_state, at the beginning of a path. */
4856
4857	feasibility_state::feasibility_state (region_model_manager *manager,
4858	const supergraph &sg)
4859	: m_model (manager),
4860	m_snodes_visited (sg.m_nodes.length ())
4861	{
4862	bitmap_clear (m_snodes_visited);
4863	}
4864
4865	/* Copy ctor for feasibility_state, for extending a path. */
4866
4867	feasibility_state::feasibility_state (const feasibility_state &other)
4868	: m_model (other.m_model),
4869	m_snodes_visited (const_sbitmap (other.m_snodes_visited)->n_bits)
4870	{
4871	bitmap_copy (m_snodes_visited, other.m_snodes_visited);
4872	}
4873
4874	feasibility_state::feasibility_state (const region_model &model,
4875	const supergraph &sg)
4876	: m_model (model),
4877	m_snodes_visited (sg.m_nodes.length ())
4878	{
4879	bitmap_clear (m_snodes_visited);
4880	}
4881
4882	feasibility_state &
4883	feasibility_state::operator= (const feasibility_state &other)
4884	{
4885	m_model = other.m_model;
4886	bitmap_copy (m_snodes_visited, other.m_snodes_visited);
4887	return *this;
4888	}
4889
4890	/* The heart of feasibility-checking.
4891
4892	Attempt to update this state in-place based on traversing EEDGE
4893	in a path.
4894	Update the model for the stmts in the src enode.
4895	Attempt to add constraints for EEDGE.
4896
4897	If feasible, return true.
4898	Otherwise, return false and write to *OUT_RC. */
4899
4900	bool
4901	feasibility_state::
4902	maybe_update_for_edge (logger *logger,
4903	const exploded_edge *eedge,
4904	region_model_context *ctxt,
4905	std::unique_ptr<rejected_constraint> *out_rc)
4906	{
4907	const exploded_node &src_enode = *eedge->m_src;
4908	const program_point &src_point = src_enode.get_point ();
4909	if (logger)
4910	{
4911	logger->start_log_line ();
4912	src_point.print (pp: logger->get_printer (), f: format (false));
4913	logger->end_log_line ();
4914	}
4915
4916	/* Update state for the stmts that were processed in each enode. */
4917	for (unsigned stmt_idx = 0; stmt_idx < src_enode.m_num_processed_stmts;
4918	stmt_idx++)
4919	{
4920	const gimple *stmt = src_enode.get_processed_stmt (idx: stmt_idx);
4921
4922	/* Update cfun and input_location in case of ICE: make it easier to
4923	track down which source construct we're failing to handle. */
4924	auto_cfun sentinel (src_point.get_function ());
4925	input_location = stmt->location;
4926
4927	update_for_stmt (stmt);
4928	}
4929
4930	const superedge *sedge = eedge->m_sedge;
4931	if (sedge)
4932	{
4933	if (logger)
4934	{
4935	label_text desc (sedge->get_description (user_facing: false));
4936	logger->log (fmt: " sedge: SN:%i -> SN:%i %s",
4937	sedge->m_src->m_index,
4938	sedge->m_dest->m_index,
4939	desc.get ());
4940	}
4941
4942	const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt ();
4943	if (!m_model.maybe_update_for_edge (edge: *sedge, last_stmt, ctxt, out: out_rc))
4944	{
4945	if (logger)
4946	{
4947	logger->start_log_line ();
4948	logger->log_partial (fmt: "rejecting due to region model: ");
4949	m_model.dump_to_pp (pp: logger->get_printer (), simple: true, multiline: false);
4950	logger->end_log_line ();
4951	}
4952	return false;
4953	}
4954	}
4955	else
4956	{
4957	/* Special-case the initial eedge from the origin node to the
4958	initial function by pushing a frame for it. */
4959	if (src_point.get_kind () == PK_ORIGIN)
4960	{
4961	gcc_assert (eedge->m_src->m_index == 0);
4962	gcc_assert (eedge->m_dest->get_point ().get_kind ()
4963	== PK_BEFORE_SUPERNODE);
4964	function *fun = eedge->m_dest->get_function ();
4965	gcc_assert (fun);
4966	m_model.push_frame (fun: *fun, NULL, ctxt);
4967	if (logger)
4968	logger->log (fmt: " pushing frame for %qD", fun->decl);
4969	}
4970	else if (eedge->m_custom_info)
4971	{
4972	eedge->m_custom_info->update_model (model: &m_model, eedge, ctxt);
4973	}
4974	}
4975
4976	/* Handle phi nodes on an edge leaving a PK_BEFORE_SUPERNODE (to
4977	a PK_BEFORE_STMT, or a PK_AFTER_SUPERNODE if no stmts).
4978	This will typically not be associated with a superedge. */
4979	if (src_point.get_from_edge ())
4980	{
4981	const cfg_superedge *last_cfg_superedge
4982	= src_point.get_from_edge ()->dyn_cast_cfg_superedge ();
4983	const exploded_node &dst_enode = *eedge->m_dest;
4984	const unsigned dst_snode_idx = dst_enode.get_supernode ()->m_index;
4985	if (last_cfg_superedge)
4986	{
4987	if (logger)
4988	logger->log (fmt: " update for phis");
4989	m_model.update_for_phis (snode: src_enode.get_supernode (),
4990	last_cfg_superedge,
4991	ctxt);
4992	/* If we've entering an snode that we've already visited on this
4993	epath, then we need do fix things up for loops; see the
4994	comment for store::loop_replay_fixup.
4995	Perhaps we should probably also verify the callstring,
4996	and track program_points, but hopefully doing it by supernode
4997	is good enough. */
4998	if (bitmap_bit_p (map: m_snodes_visited, bitno: dst_snode_idx))
4999	m_model.loop_replay_fixup (dst_state: dst_enode.get_state ().m_region_model);
5000	}
5001	bitmap_set_bit (map: m_snodes_visited, bitno: dst_snode_idx);
5002	}
5003	return true;
5004	}
5005
5006	/* Update this object for the effects of STMT. */
5007
5008	void
5009	feasibility_state::update_for_stmt (const gimple *stmt)
5010	{
5011	if (const gassign *assign = dyn_cast <const gassign *> (p: stmt))
5012	m_model.on_assignment (stmt: assign, NULL);
5013	else if (const gasm *asm_stmt = dyn_cast <const gasm *> (p: stmt))
5014	m_model.on_asm_stmt (asm_stmt, NULL);
5015	else if (const gcall *call = dyn_cast <const gcall *> (p: stmt))
5016	{
5017	bool unknown_side_effects = m_model.on_call_pre (stmt: call, NULL);
5018	m_model.on_call_post (stmt: call, unknown_side_effects, NULL);
5019	}
5020	else if (const greturn *return_ = dyn_cast <const greturn *> (p: stmt))
5021	m_model.on_return (stmt: return_, NULL);
5022	}
5023
5024	/* Dump this object to PP. */
5025
5026	void
5027	feasibility_state::dump_to_pp (pretty_printer *pp,
5028	bool simple, bool multiline) const
5029	{
5030	m_model.dump_to_pp (pp, simple, multiline);
5031	}
5032
5033	/* A family of cluster subclasses for use when generating .dot output for
5034	exploded graphs (-fdump-analyzer-exploded-graph), for grouping the
5035	enodes into hierarchical boxes.
5036
5037	All functionless enodes appear in the top-level graph.
5038	Every (function, call_string) pair gets its own cluster. Within that
5039	cluster, each supernode gets its own cluster.
5040
5041	Hence all enodes relating to a particular function with a particular
5042	callstring will be in a cluster together; all enodes for the same
5043	function but with a different callstring will be in a different
5044	cluster. */
5045
5046	/* Base class of cluster for clustering exploded_node instances in .dot
5047	output, based on various subclass-specific criteria. */
5048
5049	class exploded_cluster : public cluster<eg_traits>
5050	{
5051	};
5052
5053	/* Cluster containing all exploded_node instances for one supernode. */
5054
5055	class supernode_cluster : public exploded_cluster
5056	{
5057	public:
5058	supernode_cluster (const supernode *supernode) : m_supernode (supernode) {}
5059
5060	// TODO: dtor?
5061
5062	void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
5063	{
5064	gv->println (fmt: "subgraph \"cluster_supernode_%i\" {", m_supernode->m_index);
5065	gv->indent ();
5066	gv->println (fmt: "style=\"dashed\";");
5067	gv->println (fmt: "label=\"SN: %i (bb: %i; scc: %i)\";",
5068	m_supernode->m_index, m_supernode->m_bb->index,
5069	args.m_eg.get_scc_id (node: *m_supernode));
5070
5071	int i;
5072	exploded_node *enode;
5073	FOR_EACH_VEC_ELT (m_enodes, i, enode)
5074	enode->dump_dot (gv, args);
5075
5076	/* Terminate subgraph. */
5077	gv->outdent ();
5078	gv->println (fmt: "}");
5079	}
5080
5081	void add_node (exploded_node *en) final override
5082	{
5083	m_enodes.safe_push (obj: en);
5084	}
5085
5086	/* Comparator for use by auto_vec<supernode_cluster *>::qsort. */
5087
5088	static int cmp_ptr_ptr (const void *p1, const void *p2)
5089	{
5090	const supernode_cluster *c1
5091	= *(const supernode_cluster * const *)p1;
5092	const supernode_cluster *c2
5093	= *(const supernode_cluster * const *)p2;
5094	return c1->m_supernode->m_index - c2->m_supernode->m_index;
5095	}
5096
5097	private:
5098	const supernode *m_supernode;
5099	auto_vec <exploded_node *> m_enodes;
5100	};
5101
5102	/* Cluster containing all supernode_cluster instances for one
5103	(function, call_string) pair. */
5104
5105	class function_call_string_cluster : public exploded_cluster
5106	{
5107	public:
5108	function_call_string_cluster (function *fun, const call_string &cs)
5109	: m_fun (fun), m_cs (cs) {}
5110
5111	~function_call_string_cluster ()
5112	{
5113	for (map_t::iterator iter = m_map.begin ();
5114	iter != m_map.end ();
5115	++iter)
5116	delete (*iter).second;
5117	}
5118
5119	void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
5120	{
5121	const char *funcname = function_name (m_fun);
5122
5123	gv->println (fmt: "subgraph \"cluster_function_%s\" {",
5124	IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (m_fun->decl)));
5125	gv->indent ();
5126	gv->write_indent ();
5127	gv->print (fmt: "label=\"call string: ");
5128	m_cs.print (pp: gv->get_pp ());
5129	gv->print (fmt: " function: %s \";", funcname);
5130	gv->print (fmt: "\n");
5131
5132	/* Dump m_map, sorting it to avoid churn when comparing dumps. */
5133	auto_vec<supernode_cluster *> child_clusters (m_map.elements ());
5134	for (map_t::iterator iter = m_map.begin ();
5135	iter != m_map.end ();
5136	++iter)
5137	child_clusters.quick_push (obj: (*iter).second);
5138
5139	child_clusters.qsort (supernode_cluster::cmp_ptr_ptr);
5140
5141	unsigned i;
5142	supernode_cluster *child_cluster;
5143	FOR_EACH_VEC_ELT (child_clusters, i, child_cluster)
5144	child_cluster->dump_dot (gv, args);
5145
5146	/* Terminate subgraph. */
5147	gv->outdent ();
5148	gv->println (fmt: "}");
5149	}
5150
5151	void add_node (exploded_node *en) final override
5152	{
5153	const supernode *supernode = en->get_supernode ();
5154	gcc_assert (supernode);
5155	supernode_cluster **slot = m_map.get (k: supernode);
5156	if (slot)
5157	(*slot)->add_node (en);
5158	else
5159	{
5160	supernode_cluster *child = new supernode_cluster (supernode);
5161	m_map.put (k: supernode, v: child);
5162	child->add_node (en);
5163	}
5164	}
5165
5166	/* Comparator for use by auto_vec<function_call_string_cluster *>. */
5167
5168	static int cmp_ptr_ptr (const void *p1, const void *p2)
5169	{
5170	const function_call_string_cluster *c1
5171	= *(const function_call_string_cluster * const *)p1;
5172	const function_call_string_cluster *c2
5173	= *(const function_call_string_cluster * const *)p2;
5174	if (int cmp_names
5175	= strcmp (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c1->m_fun->decl)),
5176	IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c2->m_fun->decl))))
5177	return cmp_names;
5178	return call_string::cmp (a: c1->m_cs, b: c2->m_cs);
5179	}
5180
5181	private:
5182	function *m_fun;
5183	const call_string &m_cs;
5184	typedef ordered_hash_map<const supernode *, supernode_cluster *> map_t;
5185	map_t m_map;
5186	};
5187
5188	/* Keys for root_cluster. */
5189
5190	struct function_call_string
5191	{
5192	function_call_string (function *fun, const call_string *cs)
5193	: m_fun (fun), m_cs (cs)
5194	{
5195	gcc_assert (fun);
5196	gcc_assert (cs);
5197	}
5198
5199	function *m_fun;
5200	const call_string *m_cs;
5201	};
5202
5203	} // namespace ana
5204
5205	template <> struct default_hash_traits<function_call_string>
5206	: public pod_hash_traits<function_call_string>
5207	{
5208	static const bool empty_zero_p = false;
5209	};
5210
5211	template <>
5212	inline hashval_t
5213	pod_hash_traits<function_call_string>::hash (value_type v)
5214	{
5215	return (pointer_hash <function>::hash (candidate: v.m_fun)
5216	^ pointer_hash <const call_string>::hash (candidate: v.m_cs));
5217	}
5218
5219	template <>
5220	inline bool
5221	pod_hash_traits<function_call_string>::equal (const value_type &existing,
5222	const value_type &candidate)
5223	{
5224	return existing.m_fun == candidate.m_fun && &existing.m_cs == &candidate.m_cs;
5225	}
5226	template <>
5227	inline void
5228	pod_hash_traits<function_call_string>::mark_deleted (value_type &v)
5229	{
5230	v.m_fun = reinterpret_cast<function *> (1);
5231	}
5232	template <>
5233	inline void
5234	pod_hash_traits<function_call_string>::mark_empty (value_type &v)
5235	{
5236	v.m_fun = NULL;
5237	}
5238	template <>
5239	inline bool
5240	pod_hash_traits<function_call_string>::is_deleted (value_type v)
5241	{
5242	return v.m_fun == reinterpret_cast<function *> (1);
5243	}
5244	template <>
5245	inline bool
5246	pod_hash_traits<function_call_string>::is_empty (value_type v)
5247	{
5248	return v.m_fun == NULL;
5249	}
5250
5251	namespace ana {
5252
5253	/* Top-level cluster for generating .dot output for exploded graphs,
5254	handling the functionless nodes, and grouping the remaining nodes by
5255	callstring. */
5256
5257	class root_cluster : public exploded_cluster
5258	{
5259	public:
5260	~root_cluster ()
5261	{
5262	for (map_t::iterator iter = m_map.begin ();
5263	iter != m_map.end ();
5264	++iter)
5265	delete (*iter).second;
5266	}
5267
5268	void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
5269	{
5270	int i;
5271	exploded_node *enode;
5272	FOR_EACH_VEC_ELT (m_functionless_enodes, i, enode)
5273	enode->dump_dot (gv, args);
5274
5275	/* Dump m_map, sorting it to avoid churn when comparing dumps. */
5276	auto_vec<function_call_string_cluster *> child_clusters (m_map.elements ());
5277	for (map_t::iterator iter = m_map.begin ();
5278	iter != m_map.end ();
5279	++iter)
5280	child_clusters.quick_push (obj: (*iter).second);
5281
5282	child_clusters.qsort (function_call_string_cluster::cmp_ptr_ptr);
5283
5284	function_call_string_cluster *child_cluster;
5285	FOR_EACH_VEC_ELT (child_clusters, i, child_cluster)
5286	child_cluster->dump_dot (gv, args);
5287	}
5288
5289	void add_node (exploded_node *en) final override
5290	{
5291	function *fun = en->get_function ();
5292	if (!fun)
5293	{
5294	m_functionless_enodes.safe_push (obj: en);
5295	return;
5296	}
5297
5298	const call_string &cs = en->get_point ().get_call_string ();
5299	function_call_string key (fun, &cs);
5300	function_call_string_cluster **slot = m_map.get (k: key);
5301	if (slot)
5302	(*slot)->add_node (en);
5303	else
5304	{
5305	function_call_string_cluster *child
5306	= new function_call_string_cluster (fun, cs);
5307	m_map.put (k: key, v: child);
5308	child->add_node (en);
5309	}
5310	}
5311
5312	private:
5313	typedef hash_map<function_call_string, function_call_string_cluster *> map_t;
5314	map_t m_map;
5315
5316	/* This should just be the origin exploded_node. */
5317	auto_vec <exploded_node *> m_functionless_enodes;
5318	};
5319
5320	/* Subclass of range_label for use within
5321	exploded_graph::dump_exploded_nodes for implementing
5322	-fdump-analyzer-exploded-nodes: a label for a specific
5323	exploded_node. */
5324
5325	class enode_label : public range_label
5326	{
5327	public:
5328	enode_label (const extrinsic_state &ext_state,
5329	exploded_node *enode)
5330	: m_ext_state (ext_state), m_enode (enode) {}
5331
5332	label_text get_text (unsigned) const final override
5333	{
5334	pretty_printer pp;
5335	pp_format_decoder (&pp) = default_tree_printer;
5336	m_enode->get_state ().dump_to_pp (ext_state: m_ext_state, simple: true, multiline: false, pp: &pp);
5337	return make_label_text (can_colorize: false, fmt: "EN: %i: %s",
5338	m_enode->m_index, pp_formatted_text (&pp));
5339	}
5340
5341	private:
5342	const extrinsic_state &m_ext_state;
5343	exploded_node *m_enode;
5344	};
5345
5346	/* Postprocessing support for dumping the exploded nodes.
5347	Handle -fdump-analyzer-exploded-nodes,
5348	-fdump-analyzer-exploded-nodes-2, and the
5349	"__analyzer_dump_exploded_nodes" builtin. */
5350
5351	void
5352	exploded_graph::dump_exploded_nodes () const
5353	{
5354	// TODO
5355	/* Locate calls to __analyzer_dump_exploded_nodes. */
5356	// Print how many egs there are for them?
5357	/* Better: log them as we go, and record the exploded nodes
5358	in question. */
5359
5360	/* Show every enode. */
5361
5362	/* Gather them by stmt, so that we can more clearly see the
5363	"hotspots" requiring numerous exploded nodes. */
5364
5365	/* Alternatively, simply throw them all into one big rich_location
5366	and see if the label-printing will sort it out...
5367	This requires them all to be in the same source file. */
5368
5369	if (flag_dump_analyzer_exploded_nodes)
5370	{
5371	auto_timevar tv (TV_ANALYZER_DUMP);
5372	gcc_rich_location richloc (UNKNOWN_LOCATION);
5373	unsigned i;
5374	exploded_node *enode;
5375	FOR_EACH_VEC_ELT (m_nodes, i, enode)
5376	{
5377	if (const gimple *stmt = enode->get_stmt ())
5378	{
5379	if (get_pure_location (loc: richloc.get_loc ()) == UNKNOWN_LOCATION)
5380	richloc.set_range (idx: 0, loc: stmt->location, range_display_kind: SHOW_RANGE_WITH_CARET);
5381	else
5382	richloc.add_range (loc: stmt->location,
5383	range_display_kind: SHOW_RANGE_WITHOUT_CARET,
5384	label: new enode_label (m_ext_state, enode));
5385	}
5386	}
5387	warning_at (&richloc, 0, "%i exploded nodes", m_nodes.length ());
5388
5389	/* Repeat the warning without all the labels, so that message is visible
5390	(the other one may well have scrolled past the terminal limit). */
5391	warning_at (richloc.get_loc (), 0,
5392	"%i exploded nodes", m_nodes.length ());
5393
5394	if (m_worklist.length () > 0)
5395	warning_at (richloc.get_loc (), 0,
5396	"worklist still contains %i nodes", m_worklist.length ());
5397	}
5398
5399	/* Dump the egraph in textual form to a dump file. */
5400	if (flag_dump_analyzer_exploded_nodes_2)
5401	{
5402	auto_timevar tv (TV_ANALYZER_DUMP);
5403	char *filename
5404	= concat (dump_base_name, ".eg.txt", NULL);
5405	FILE *outf = fopen (filename: filename, modes: "w");
5406	if (!outf)
5407	error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
5408	free (ptr: filename);
5409
5410	fprintf (stream: outf, format: "exploded graph for %s\n", dump_base_name);
5411	fprintf (stream: outf, format: " nodes: %i\n", m_nodes.length ());
5412	fprintf (stream: outf, format: " edges: %i\n", m_edges.length ());
5413
5414	unsigned i;
5415	exploded_node *enode;
5416	FOR_EACH_VEC_ELT (m_nodes, i, enode)
5417	{
5418	fprintf (stream: outf, format: "\nEN %i:\n", enode->m_index);
5419	enode->dump_succs_and_preds (outf);
5420	pretty_printer pp;
5421	enode->get_point ().print (pp: &pp, f: format (true));
5422	fprintf (stream: outf, format: "%s\n", pp_formatted_text (&pp));
5423	enode->get_state ().dump_to_file (ext_state: m_ext_state, simple: false, multiline: true, outf);
5424	}
5425
5426	fclose (stream: outf);
5427	}
5428
5429	/* Dump the egraph in textual form to multiple dump files, one per enode. */
5430	if (flag_dump_analyzer_exploded_nodes_3)
5431	{
5432	auto_timevar tv (TV_ANALYZER_DUMP);
5433
5434	unsigned i;
5435	exploded_node *enode;
5436	FOR_EACH_VEC_ELT (m_nodes, i, enode)
5437	{
5438	char *filename
5439	= xasprintf ("%s.en-%i.txt", dump_base_name, i);
5440	FILE *outf = fopen (filename: filename, modes: "w");
5441	if (!outf)
5442	error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
5443	free (ptr: filename);
5444
5445	fprintf (stream: outf, format: "EN %i:\n", enode->m_index);
5446	enode->dump_succs_and_preds (outf);
5447	pretty_printer pp;
5448	enode->get_point ().print (pp: &pp, f: format (true));
5449	fprintf (stream: outf, format: "%s\n", pp_formatted_text (&pp));
5450	enode->get_state ().dump_to_file (ext_state: m_ext_state, simple: false, multiline: true, outf);
5451
5452	fclose (stream: outf);
5453	}
5454	}
5455
5456	/* Emit a warning at any call to "__analyzer_dump_exploded_nodes",
5457	giving the number of processed exploded nodes for "before-stmt",
5458	and the IDs of processed, merger, and worklist enodes.
5459
5460	We highlight the count of *processed* enodes since this is of most
5461	interest in DejaGnu tests for ensuring that state merger has
5462	happened.
5463
5464	We don't show the count of merger and worklist enodes, as this is
5465	more of an implementation detail of the merging/worklist that we
5466	don't want to bake into our expected DejaGnu messages. */
5467
5468	unsigned i;
5469	exploded_node *enode;
5470	hash_set<const gimple *> seen;
5471	FOR_EACH_VEC_ELT (m_nodes, i, enode)
5472	{
5473	if (enode->get_point ().get_kind () != PK_BEFORE_STMT)
5474	continue;
5475
5476	if (const gimple *stmt = enode->get_stmt ())
5477	if (const gcall *call = dyn_cast <const gcall *> (p: stmt))
5478	if (is_special_named_call_p (call, funcname: "__analyzer_dump_exploded_nodes",
5479	num_args: 1))
5480	{
5481	if (seen.contains (k: stmt))
5482	continue;
5483
5484	auto_vec<exploded_node *> processed_enodes;
5485	auto_vec<exploded_node *> merger_enodes;
5486	auto_vec<exploded_node *> worklist_enodes;
5487	/* This is O(N^2). */
5488	unsigned j;
5489	exploded_node *other_enode;
5490	FOR_EACH_VEC_ELT (m_nodes, j, other_enode)
5491	{
5492	if (other_enode->get_point ().get_kind () != PK_BEFORE_STMT)
5493	continue;
5494	if (other_enode->get_stmt () == stmt)
5495	switch (other_enode->get_status ())
5496	{
5497	default:
5498	gcc_unreachable ();
5499	case exploded_node::STATUS_WORKLIST:
5500	worklist_enodes.safe_push (obj: other_enode);
5501	break;
5502	case exploded_node::STATUS_PROCESSED:
5503	processed_enodes.safe_push (obj: other_enode);
5504	break;
5505	case exploded_node::STATUS_MERGER:
5506	merger_enodes.safe_push (obj: other_enode);
5507	break;
5508	}
5509	}
5510
5511	pretty_printer pp;
5512	pp_character (&pp, '[');
5513	print_enode_indices (pp: &pp, enodes: processed_enodes);
5514	if (merger_enodes.length () > 0)
5515	{
5516	pp_string (&pp, "] merger(s): [");
5517	print_enode_indices (pp: &pp, enodes: merger_enodes);
5518	}
5519	if (worklist_enodes.length () > 0)
5520	{
5521	pp_string (&pp, "] worklist: [");
5522	print_enode_indices (pp: &pp, enodes: worklist_enodes);
5523	}
5524	pp_character (&pp, ']');
5525
5526	warning_n (stmt->location, 0, processed_enodes.length (),
5527	"%i processed enode: %s",
5528	"%i processed enodes: %s",
5529	processed_enodes.length (), pp_formatted_text (&pp));
5530	seen.add (k: stmt);
5531
5532	/* If the argument is non-zero, then print all of the states
5533	of the various enodes. */
5534	tree t_arg = fold (gimple_call_arg (gs: call, index: 0));
5535	if (TREE_CODE (t_arg) != INTEGER_CST)
5536	{
5537	error_at (call->location,
5538	"integer constant required for arg 1");
5539	return;
5540	}
5541	int i_arg = TREE_INT_CST_LOW (t_arg);
5542	if (i_arg)
5543	{
5544	exploded_node *other_enode;
5545	FOR_EACH_VEC_ELT (processed_enodes, j, other_enode)
5546	{
5547	fprintf (stderr, format: "%i of %i: EN %i:\n",
5548	j + 1, processed_enodes.length (),
5549	other_enode->m_index);
5550	other_enode->dump_succs_and_preds (stderr);
5551	/* Dump state. */
5552	other_enode->get_state ().dump (ext_state: m_ext_state, simple: false);
5553	}
5554	}
5555	}
5556	}
5557	}
5558
5559	DEBUG_FUNCTION exploded_node *
5560	exploded_graph::get_node_by_index (int idx) const
5561	{
5562	exploded_node *enode = m_nodes[idx];
5563	gcc_assert (enode->m_index == idx);
5564	return enode;
5565	}
5566
5567	/* Ensure that there is an exploded_node for a top-level call to FNDECL. */
5568
5569	void
5570	exploded_graph::on_escaped_function (tree fndecl)
5571	{
5572	logger * const logger = get_logger ();
5573	LOG_FUNC_1 (logger, "%qE", fndecl);
5574
5575	cgraph_node *cgnode = cgraph_node::get (decl: fndecl);
5576	if (!cgnode)
5577	return;
5578
5579	function *fun = cgnode->get_fun ();
5580	if (!fun)
5581	return;
5582
5583	if (!gimple_has_body_p (fndecl))
5584	return;
5585
5586	exploded_node *enode = add_function_entry (fun: *fun);
5587	if (logger)
5588	{
5589	if (enode)
5590	logger->log (fmt: "created EN %i for %qE entrypoint",
5591	enode->m_index, fun->decl);
5592	else
5593	logger->log (fmt: "did not create enode for %qE entrypoint", fun->decl);
5594	}
5595	}
5596
5597	/* A collection of classes for visualizing the callgraph in .dot form
5598	(as represented in the supergraph). */
5599
5600	/* Forward decls. */
5601	class viz_callgraph_node;
5602	class viz_callgraph_edge;
5603	class viz_callgraph;
5604	class viz_callgraph_cluster;
5605
5606	/* Traits for using "digraph.h" to visualize the callgraph. */
5607
5608	struct viz_callgraph_traits
5609	{
5610	typedef viz_callgraph_node node_t;
5611	typedef viz_callgraph_edge edge_t;
5612	typedef viz_callgraph graph_t;
5613	struct dump_args_t
5614	{
5615	dump_args_t (const exploded_graph *eg) : m_eg (eg) {}
5616	const exploded_graph *m_eg;
5617	};
5618	typedef viz_callgraph_cluster cluster_t;
5619	};
5620
5621	/* Subclass of dnode representing a function within the callgraph. */
5622
5623	class viz_callgraph_node : public dnode<viz_callgraph_traits>
5624	{
5625	friend class viz_callgraph;
5626
5627	public:
5628	viz_callgraph_node (function *fun, int index)
5629	: m_fun (fun), m_index (index), m_num_supernodes (0), m_num_superedges (0)
5630	{
5631	gcc_assert (fun);
5632	}
5633
5634	void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
5635	{
5636	pretty_printer *pp = gv->get_pp ();
5637
5638	dump_dot_id (pp);
5639	pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
5640	"lightgrey");
5641	pp_write_text_to_stream (pp);
5642
5643	pp_printf (pp, "VCG: %i: %s", m_index, function_name (m_fun));
5644	pp_newline (pp);
5645
5646	pp_printf (pp, "supernodes: %i\n", m_num_supernodes);
5647	pp_newline (pp);
5648
5649	pp_printf (pp, "superedges: %i\n", m_num_superedges);
5650	pp_newline (pp);
5651
5652	if (args.m_eg)
5653	{
5654	unsigned i;
5655	exploded_node *enode;
5656	unsigned num_enodes = 0;
5657	FOR_EACH_VEC_ELT (args.m_eg->m_nodes, i, enode)
5658	{
5659	if (enode->get_point ().get_function () == m_fun)
5660	num_enodes++;
5661	}
5662	pp_printf (pp, "enodes: %i\n", num_enodes);
5663	pp_newline (pp);
5664
5665	// TODO: also show the per-callstring breakdown
5666	const exploded_graph::call_string_data_map_t *per_cs_data
5667	= args.m_eg->get_per_call_string_data ();
5668	for (exploded_graph::call_string_data_map_t::iterator iter
5669	= per_cs_data->begin ();
5670	iter != per_cs_data->end ();
5671	++iter)
5672	{
5673	const call_string *cs = (*iter).first;
5674	//per_call_string_data *data = (*iter).second;
5675	num_enodes = 0;
5676	FOR_EACH_VEC_ELT (args.m_eg->m_nodes, i, enode)
5677	{
5678	if (enode->get_point ().get_function () == m_fun
5679	&& &enode->get_point ().get_call_string () == cs)
5680	num_enodes++;
5681	}
5682	if (num_enodes > 0)
5683	{
5684	cs->print (pp);
5685	pp_printf (pp, ": %i\n", num_enodes);
5686	}
5687	}
5688
5689	/* Show any summaries. */
5690	per_function_data *data = args.m_eg->get_per_function_data (fun: m_fun);
5691	if (data)
5692	{
5693	pp_newline (pp);
5694	pp_printf (pp, "summaries: %i\n", data->m_summaries.length ());
5695	for (auto summary : data->m_summaries)
5696	{
5697	pp_printf (pp, "\nsummary: %s:\n", summary->get_desc ().get ());
5698	const extrinsic_state &ext_state = args.m_eg->get_ext_state ();
5699	const program_state &state = summary->get_state ();
5700	state.dump_to_pp (ext_state, simple: false, multiline: true, pp);
5701	pp_newline (pp);
5702	}
5703	}
5704	}
5705
5706	pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
5707	pp_string (pp, "\"];\n\n");
5708	pp_flush (pp);
5709	}
5710
5711	void dump_dot_id (pretty_printer *pp) const
5712	{
5713	pp_printf (pp, "vcg_%i", m_index);
5714	}
5715
5716	private:
5717	function *m_fun;
5718	int m_index;
5719	int m_num_supernodes;
5720	int m_num_superedges;
5721	};
5722
5723	/* Subclass of dedge representing a callgraph edge. */
5724
5725	class viz_callgraph_edge : public dedge<viz_callgraph_traits>
5726	{
5727	public:
5728	viz_callgraph_edge (viz_callgraph_node *src, viz_callgraph_node *dest)
5729	: dedge<viz_callgraph_traits> (src, dest)
5730	{}
5731
5732	void dump_dot (graphviz_out *gv, const dump_args_t &) const
5733	final override
5734	{
5735	pretty_printer *pp = gv->get_pp ();
5736
5737	const char *style = "\"solid,bold\"";
5738	const char *color = "black";
5739	int weight = 10;
5740	const char *constraint = "true";
5741
5742	m_src->dump_dot_id (pp);
5743	pp_string (pp, " -> ");
5744	m_dest->dump_dot_id (pp);
5745	pp_printf (pp,
5746	(" [style=%s, color=%s, weight=%d, constraint=%s,"
5747	" headlabel=\""),
5748	style, color, weight, constraint);
5749	pp_printf (pp, "\"];\n");
5750	}
5751	};
5752
5753	/* Subclass of digraph representing the callgraph. */
5754
5755	class viz_callgraph : public digraph<viz_callgraph_traits>
5756	{
5757	public:
5758	viz_callgraph (const supergraph &sg);
5759
5760	viz_callgraph_node *get_vcg_node_for_function (function *fun)
5761	{
5762	return *m_map.get (k: fun);
5763	}
5764
5765	viz_callgraph_node *get_vcg_node_for_snode (supernode *snode)
5766	{
5767	return get_vcg_node_for_function (fun: snode->m_fun);
5768	}
5769
5770	private:
5771	hash_map<function *, viz_callgraph_node *> m_map;
5772	};
5773
5774	/* Placeholder subclass of cluster. */
5775
5776	class viz_callgraph_cluster : public cluster<viz_callgraph_traits>
5777	{
5778	};
5779
5780	/* viz_callgraph's ctor. */
5781
5782	viz_callgraph::viz_callgraph (const supergraph &sg)
5783	{
5784	cgraph_node *node;
5785	FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
5786	{
5787	function *fun = node->get_fun ();
5788	viz_callgraph_node *vcg_node
5789	= new viz_callgraph_node (fun, m_nodes.length ());
5790	m_map.put (k: fun, v: vcg_node);
5791	add_node (node: vcg_node);
5792	}
5793
5794	unsigned i;
5795	superedge *sedge;
5796	FOR_EACH_VEC_ELT (sg.m_edges, i, sedge)
5797	{
5798	viz_callgraph_node *vcg_src = get_vcg_node_for_snode (snode: sedge->m_src);
5799	if (vcg_src->m_fun)
5800	get_vcg_node_for_function (fun: vcg_src->m_fun)->m_num_superedges++;
5801	if (sedge->dyn_cast_call_superedge ())
5802	{
5803	viz_callgraph_node *vcg_dest = get_vcg_node_for_snode (snode: sedge->m_dest);
5804	viz_callgraph_edge *vcg_edge
5805	= new viz_callgraph_edge (vcg_src, vcg_dest);
5806	add_edge (edge: vcg_edge);
5807	}
5808	}
5809
5810	supernode *snode;
5811	FOR_EACH_VEC_ELT (sg.m_nodes, i, snode)
5812	{
5813	if (snode->m_fun)
5814	get_vcg_node_for_function (fun: snode->m_fun)->m_num_supernodes++;
5815	}
5816	}
5817
5818	/* Dump the callgraph to FILENAME. */
5819
5820	static void
5821	dump_callgraph (const supergraph &sg, const char *filename,
5822	const exploded_graph *eg)
5823	{
5824	FILE *outf = fopen (filename: filename, modes: "w");
5825	if (!outf)
5826	return;
5827
5828	// TODO
5829	viz_callgraph vcg (sg);
5830	vcg.dump_dot (path: filename, NULL, args: viz_callgraph_traits::dump_args_t (eg));
5831
5832	fclose (stream: outf);
5833	}
5834
5835	/* Dump the callgraph to "<srcfile>.callgraph.dot". */
5836
5837	static void
5838	dump_callgraph (const supergraph &sg, const exploded_graph *eg)
5839	{
5840	auto_timevar tv (TV_ANALYZER_DUMP);
5841	char *filename = concat (dump_base_name, ".callgraph.dot", NULL);
5842	dump_callgraph (sg, filename, eg);
5843	free (ptr: filename);
5844	}
5845
5846	/* Subclass of dot_annotator for implementing
5847	DUMP_BASE_NAME.supergraph-eg.dot, a post-analysis dump of the supergraph.
5848
5849	Annotate the supergraph nodes by printing the exploded nodes in concise
5850	form within them, next to their pertinent statements where appropriate,
5851	colorizing the exploded nodes based on sm-state.
5852	Also show saved diagnostics within the exploded nodes, giving information
5853	on whether they were feasible, and, if infeasible, where the problem
5854	was. */
5855
5856	class exploded_graph_annotator : public dot_annotator
5857	{
5858	public:
5859	exploded_graph_annotator (const exploded_graph &eg)
5860	: m_eg (eg)
5861	{
5862	/* Avoid O(N^2) by prepopulating m_enodes_per_snodes. */
5863	unsigned i;
5864	supernode *snode;
5865	FOR_EACH_VEC_ELT (eg.get_supergraph ().m_nodes, i, snode)
5866	m_enodes_per_snodes.safe_push (obj: new auto_vec <exploded_node *> ());
5867	exploded_node *enode;
5868	FOR_EACH_VEC_ELT (m_eg.m_nodes, i, enode)
5869	if (enode->get_supernode ())
5870	m_enodes_per_snodes[enode->get_supernode ()->m_index]->safe_push (obj: enode);
5871	}
5872
5873	/* Show exploded nodes for BEFORE_SUPERNODE points before N. */
5874	bool add_node_annotations (graphviz_out *gv, const supernode &n,
5875	bool within_table)
5876	const final override
5877	{
5878	if (!within_table)
5879	return false;
5880	gv->begin_tr ();
5881	pretty_printer *pp = gv->get_pp ();
5882
5883	gv->begin_td ();
5884	pp_string (pp, "BEFORE");
5885	pp_printf (pp, " (scc: %i)", m_eg.get_scc_id (node: n));
5886	gv->end_td ();
5887
5888	unsigned i;
5889	exploded_node *enode;
5890	bool had_enode = false;
5891	FOR_EACH_VEC_ELT (*m_enodes_per_snodes[n.m_index], i, enode)
5892	{
5893	gcc_assert (enode->get_supernode () == &n);
5894	const program_point &point = enode->get_point ();
5895	if (point.get_kind () != PK_BEFORE_SUPERNODE)
5896	continue;
5897	print_enode (gv, enode);
5898	had_enode = true;
5899	}
5900	if (!had_enode)
5901	pp_string (pp, "<TD BGCOLOR=\"red\">UNREACHED</TD>");
5902	pp_flush (pp);
5903	gv->end_tr ();
5904	return true;
5905	}
5906
5907	/* Show exploded nodes for STMT. */
5908	void add_stmt_annotations (graphviz_out *gv, const gimple *stmt,
5909	bool within_row)
5910	const final override
5911	{
5912	if (!within_row)
5913	return;
5914	pretty_printer *pp = gv->get_pp ();
5915
5916	const supernode *snode
5917	= m_eg.get_supergraph ().get_supernode_for_stmt (stmt);
5918	unsigned i;
5919	exploded_node *enode;
5920	bool had_td = false;
5921	FOR_EACH_VEC_ELT (*m_enodes_per_snodes[snode->m_index], i, enode)
5922	{
5923	const program_point &point = enode->get_point ();
5924	if (point.get_kind () != PK_BEFORE_STMT)
5925	continue;
5926	if (point.get_stmt () != stmt)
5927	continue;
5928	print_enode (gv, enode);
5929	had_td = true;
5930	}
5931	pp_flush (pp);
5932	if (!had_td)
5933	{
5934	gv->begin_td ();
5935	gv->end_td ();
5936	}
5937	}
5938
5939	/* Show exploded nodes for AFTER_SUPERNODE points after N. */
5940	bool add_after_node_annotations (graphviz_out *gv, const supernode &n)
5941	const final override
5942	{
5943	gv->begin_tr ();
5944	pretty_printer *pp = gv->get_pp ();
5945
5946	gv->begin_td ();
5947	pp_string (pp, "AFTER");
5948	gv->end_td ();
5949
5950	unsigned i;
5951	exploded_node *enode;
5952	FOR_EACH_VEC_ELT (*m_enodes_per_snodes[n.m_index], i, enode)
5953	{
5954	gcc_assert (enode->get_supernode () == &n);
5955	const program_point &point = enode->get_point ();
5956	if (point.get_kind () != PK_AFTER_SUPERNODE)
5957	continue;
5958	print_enode (gv, enode);
5959	}
5960	pp_flush (pp);
5961	gv->end_tr ();
5962	return true;
5963	}
5964
5965	private:
5966	/* Concisely print a TD element for ENODE, showing the index, status,
5967	and any saved_diagnostics at the enode. Colorize it to show sm-state.
5968
5969	Ideally we'd dump ENODE's state here, hidden behind some kind of
5970	interactive disclosure method like a tooltip, so that the states
5971	can be explored without overwhelming the graph.
5972	However, I wasn't able to get graphviz/xdot to show tooltips on
5973	individual elements within a HTML-like label. */
5974	void print_enode (graphviz_out *gv, const exploded_node *enode) const
5975	{
5976	pretty_printer *pp = gv->get_pp ();
5977	pp_printf (pp, "<TD BGCOLOR=\"%s\">",
5978	enode->get_dot_fillcolor ());
5979	pp_printf (pp, "<TABLE BORDER=\"0\">");
5980	gv->begin_trtd ();
5981	pp_printf (pp, "EN: %i", enode->m_index);
5982	switch (enode->get_status ())
5983	{
5984	default:
5985	gcc_unreachable ();
5986	case exploded_node::STATUS_WORKLIST:
5987	pp_string (pp, "(W)");
5988	break;
5989	case exploded_node::STATUS_PROCESSED:
5990	break;
5991	case exploded_node::STATUS_MERGER:
5992	pp_string (pp, "(M)");
5993	break;
5994	case exploded_node::STATUS_BULK_MERGED:
5995	pp_string (pp, "(BM)");
5996	break;
5997	}
5998	gv->end_tdtr ();
5999
6000	/* Dump any saved_diagnostics at this enode. */
6001	for (unsigned i = 0; i < enode->get_num_diagnostics (); i++)
6002	{
6003	const saved_diagnostic *sd = enode->get_saved_diagnostic (idx: i);
6004	print_saved_diagnostic (gv, sd);
6005	}
6006	pp_printf (pp, "</TABLE>");
6007	pp_printf (pp, "</TD>");
6008	}
6009
6010	/* Print a TABLE element for SD, showing the kind, the length of the
6011	exploded_path, whether the path was feasible, and if infeasible,
6012	what the problem was. */
6013	void print_saved_diagnostic (graphviz_out *gv,
6014	const saved_diagnostic *sd) const
6015	{
6016	pretty_printer *pp = gv->get_pp ();
6017	gv->begin_trtd ();
6018	pp_printf (pp, "<TABLE BORDER=\"0\">");
6019	gv->begin_tr ();
6020	pp_string (pp, "<TD BGCOLOR=\"green\">");
6021	pp_printf (pp, "DIAGNOSTIC: %s", sd->m_d->get_kind ());
6022	gv->end_tdtr ();
6023	gv->begin_trtd ();
6024	if (sd->get_best_epath ())
6025	pp_printf (pp, "epath length: %i", sd->get_epath_length ());
6026	else
6027	pp_printf (pp, "no best epath");
6028	gv->end_tdtr ();
6029	if (const feasibility_problem *p = sd->get_feasibility_problem ())
6030	{
6031	gv->begin_trtd ();
6032	pp_printf (pp, "INFEASIBLE at eedge %i: EN:%i -> EN:%i",
6033	p->m_eedge_idx,
6034	p->m_eedge.m_src->m_index,
6035	p->m_eedge.m_dest->m_index);
6036	pp_write_text_as_html_like_dot_to_stream (pp);
6037	gv->end_tdtr ();
6038	gv->begin_trtd ();
6039	p->m_eedge.m_sedge->dump (pp);
6040	pp_write_text_as_html_like_dot_to_stream (pp);
6041	gv->end_tdtr ();
6042	gv->begin_trtd ();
6043	pp_gimple_stmt_1 (pp, p->m_last_stmt, 0, (dump_flags_t)0);
6044	pp_write_text_as_html_like_dot_to_stream (pp);
6045	gv->end_tdtr ();
6046	/* Ideally we'd print p->m_model here; see the notes above about
6047	tooltips. */
6048	}
6049	pp_printf (pp, "</TABLE>");
6050	gv->end_tdtr ();
6051	}
6052
6053	const exploded_graph &m_eg;
6054	auto_delete_vec<auto_vec <exploded_node *> > m_enodes_per_snodes;
6055	};
6056
6057	/* Implement -fdump-analyzer-json. */
6058
6059	static void
6060	dump_analyzer_json (const supergraph &sg,
6061	const exploded_graph &eg)
6062	{
6063	auto_timevar tv (TV_ANALYZER_DUMP);
6064	char *filename = concat (dump_base_name, ".analyzer.json.gz", NULL);
6065	gzFile output = gzopen (filename, "w");
6066	if (!output)
6067	{
6068	error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
6069	free (ptr: filename);
6070	return;
6071	}
6072
6073	json::object *toplev_obj = new json::object ();
6074	toplev_obj->set (key: "sgraph", v: sg.to_json ());
6075	toplev_obj->set (key: "egraph", v: eg.to_json ());
6076
6077	pretty_printer pp;
6078	toplev_obj->print (pp: &pp, flag_diagnostics_json_formatting);
6079	pp_formatted_text (&pp);
6080
6081	delete toplev_obj;
6082
6083	if (gzputs (file: output, s: pp_formatted_text (&pp)) == EOF
6084	|| gzclose (file: output))
6085	error_at (UNKNOWN_LOCATION, "error writing %qs", filename);
6086
6087	free (ptr: filename);
6088	}
6089
6090	/* Concrete subclass of plugin_analyzer_init_iface, allowing plugins
6091	to register new state machines. */
6092
6093	class plugin_analyzer_init_impl : public plugin_analyzer_init_iface
6094	{
6095	public:
6096	plugin_analyzer_init_impl (auto_delete_vec <state_machine> *checkers,
6097	known_function_manager *known_fn_mgr,
6098	logger *logger)
6099	: m_checkers (checkers),
6100	m_known_fn_mgr (known_fn_mgr),
6101	m_logger (logger)
6102	{}
6103
6104	void register_state_machine (std::unique_ptr<state_machine> sm) final override
6105	{
6106	LOG_SCOPE (m_logger);
6107	m_checkers->safe_push (obj: sm.release ());
6108	}
6109
6110	void register_known_function (const char *name,
6111	std::unique_ptr<known_function> kf) final override
6112	{
6113	LOG_SCOPE (m_logger);
6114	m_known_fn_mgr->add (name, kf: std::move (kf));
6115	}
6116
6117	logger *get_logger () const final override
6118	{
6119	return m_logger;
6120	}
6121
6122	private:
6123	auto_delete_vec <state_machine> *m_checkers;
6124	known_function_manager *m_known_fn_mgr;
6125	logger *m_logger;
6126	};
6127
6128	/* Run the analysis "engine". */
6129
6130	void
6131	impl_run_checkers (logger *logger)
6132	{
6133	LOG_SCOPE (logger);
6134
6135	if (logger)
6136	{
6137	logger->log (fmt: "BITS_BIG_ENDIAN: %i", BITS_BIG_ENDIAN ? 1 : 0);
6138	logger->log (fmt: "BYTES_BIG_ENDIAN: %i", BYTES_BIG_ENDIAN ? 1 : 0);
6139	logger->log (fmt: "WORDS_BIG_ENDIAN: %i", WORDS_BIG_ENDIAN ? 1 : 0);
6140	log_stashed_constants (logger);
6141	}
6142
6143	/* If using LTO, ensure that the cgraph nodes have function bodies. */
6144	cgraph_node *node;
6145	FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
6146	node->get_untransformed_body ();
6147
6148	/* Create the supergraph. */
6149	supergraph sg (logger);
6150
6151	engine eng (&sg, logger);
6152
6153	state_purge_map *purge_map = NULL;
6154
6155	if (flag_analyzer_state_purge)
6156	purge_map = new state_purge_map (sg, eng.get_model_manager (), logger);
6157
6158	if (flag_dump_analyzer_supergraph)
6159	{
6160	/* Dump supergraph pre-analysis. */
6161	auto_timevar tv (TV_ANALYZER_DUMP);
6162	char *filename = concat (dump_base_name, ".supergraph.dot", NULL);
6163	supergraph::dump_args_t args ((enum supergraph_dot_flags)0, NULL);
6164	sg.dump_dot (path: filename, args);
6165	free (ptr: filename);
6166	}
6167
6168	if (flag_dump_analyzer_state_purge)
6169	{
6170	auto_timevar tv (TV_ANALYZER_DUMP);
6171	state_purge_annotator a (purge_map);
6172	char *filename = concat (dump_base_name, ".state-purge.dot", NULL);
6173	supergraph::dump_args_t args ((enum supergraph_dot_flags)0, &a);
6174	sg.dump_dot (path: filename, args);
6175	free (ptr: filename);
6176	}
6177
6178	auto_delete_vec <state_machine> checkers;
6179	make_checkers (out&: checkers, logger);
6180
6181	register_known_functions (kfm&: *eng.get_known_function_manager (),
6182	rmm&: *eng.get_model_manager ());
6183
6184	plugin_analyzer_init_impl data (&checkers,
6185	eng.get_known_function_manager (),
6186	logger);
6187	invoke_plugin_callbacks (event: PLUGIN_ANALYZER_INIT, gcc_data: &data);
6188
6189	if (logger)
6190	{
6191	int i;
6192	state_machine *sm;
6193	FOR_EACH_VEC_ELT (checkers, i, sm)
6194	logger->log (fmt: "checkers[%i]: %s", i, sm->get_name ());
6195	}
6196
6197	/* Extrinsic state shared by nodes in the graph. */
6198	const extrinsic_state ext_state (checkers, &eng, logger);
6199
6200	const analysis_plan plan (sg, logger);
6201
6202	/* The exploded graph. */
6203	exploded_graph eg (sg, logger, ext_state, purge_map, plan,
6204	analyzer_verbosity);
6205
6206	/* Add entrypoints to the graph for externally-callable functions. */
6207	eg.build_initial_worklist ();
6208
6209	/* Now process the worklist, exploring the <point, state> graph. */
6210	eg.process_worklist ();
6211
6212	if (warn_analyzer_infinite_loop)
6213	eg.detect_infinite_loops ();
6214
6215	if (flag_dump_analyzer_exploded_graph)
6216	{
6217	auto_timevar tv (TV_ANALYZER_DUMP);
6218	char *filename
6219	= concat (dump_base_name, ".eg.dot", NULL);
6220	exploded_graph::dump_args_t args (eg);
6221	root_cluster c;
6222	eg.dump_dot (path: filename, root_cluster: &c, args);
6223	free (ptr: filename);
6224	}
6225
6226	/* Now emit any saved diagnostics. */
6227	eg.get_diagnostic_manager ().emit_saved_diagnostics (eg);
6228
6229	eg.dump_exploded_nodes ();
6230
6231	eg.log_stats ();
6232
6233	if (flag_dump_analyzer_callgraph)
6234	dump_callgraph (sg, eg: &eg);
6235
6236	if (flag_dump_analyzer_supergraph)
6237	{
6238	/* Dump post-analysis form of supergraph. */
6239	auto_timevar tv (TV_ANALYZER_DUMP);
6240	char *filename = concat (dump_base_name, ".supergraph-eg.dot", NULL);
6241	exploded_graph_annotator a (eg);
6242	supergraph::dump_args_t args ((enum supergraph_dot_flags)0, &a);
6243	sg.dump_dot (path: filename, args);
6244	free (ptr: filename);
6245	}
6246
6247	if (flag_dump_analyzer_json)
6248	dump_analyzer_json (sg, eg);
6249
6250	if (flag_dump_analyzer_untracked)
6251	eng.get_model_manager ()->dump_untracked_regions ();
6252
6253	delete purge_map;
6254
6255	/* Free up any dominance info that we may have created. */
6256	FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
6257	{
6258	function *fun = node->get_fun ();
6259	free_dominance_info (fun, CDI_DOMINATORS);
6260	}
6261	}
6262
6263	/* Handle -fdump-analyzer and -fdump-analyzer-stderr. */
6264	static FILE *dump_fout = NULL;
6265
6266	/* Track if we're responsible for closing dump_fout. */
6267	static bool owns_dump_fout = false;
6268
6269	/* If dumping is enabled, attempt to create dump_fout if it hasn't already
6270	been opened. Return it. */
6271
6272	FILE *
6273	get_or_create_any_logfile ()
6274	{
6275	if (!dump_fout)
6276	{
6277	if (flag_dump_analyzer_stderr)
6278	dump_fout = stderr;
6279	else if (flag_dump_analyzer)
6280	{
6281	char *dump_filename = concat (dump_base_name, ".analyzer.txt", NULL);
6282	dump_fout = fopen (filename: dump_filename, modes: "w");
6283	free (ptr: dump_filename);
6284	if (dump_fout)
6285	owns_dump_fout = true;
6286	}
6287	}
6288	return dump_fout;
6289	}
6290
6291	/* External entrypoint to the analysis "engine".
6292	Set up any dumps, then call impl_run_checkers. */
6293
6294	void
6295	run_checkers ()
6296	{
6297	/* Save input_location. */
6298	location_t saved_input_location = input_location;
6299
6300	{
6301	log_user the_logger (NULL);
6302	get_or_create_any_logfile ();
6303	if (dump_fout)
6304	the_logger.set_logger (new logger (dump_fout, 0, 0,
6305	*global_dc->printer));
6306	LOG_SCOPE (the_logger.get_logger ());
6307
6308	impl_run_checkers (logger: the_logger.get_logger ());
6309
6310	/* end of lifetime of the_logger (so that dump file is closed after the
6311	various dtors run). */
6312	}
6313
6314	if (owns_dump_fout)
6315	{
6316	fclose (stream: dump_fout);
6317	owns_dump_fout = false;
6318	dump_fout = NULL;
6319	}
6320
6321	/* Restore input_location. Subsequent passes may assume that input_location
6322	is some arbitrary value *not* in the block tree, which might be violated
6323	if we didn't restore it. */
6324	input_location = saved_input_location;
6325	}
6326
6327	} // namespace ana
6328
6329	#endif /* #if ENABLE_ANALYZER */
6330