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