Branch data Line data Source code
1 : : /* The analysis "engine".
2 : : Copyright (C) 2019-2026 Free Software Foundation, Inc.
3 : : Contributed by David Malcolm <dmalcolm@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it
8 : : under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but
13 : : WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : : General Public License for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : #include "analyzer/common.h"
22 : :
23 : : #include <zlib.h>
24 : :
25 : : #include "cfg.h"
26 : : #include "gcc-rich-location.h"
27 : : #include "gimple-iterator.h"
28 : : #include "gimple-pretty-print.h"
29 : : #include "cgraph.h"
30 : : #include "fold-const.h"
31 : : #include "digraph.h"
32 : : #include "plugin.h"
33 : : #include "target.h"
34 : : #include "stringpool.h"
35 : : #include "attribs.h"
36 : : #include "tree-dfa.h"
37 : : #include "gimple-predict.h"
38 : : #include "context.h"
39 : : #include "channels.h"
40 : :
41 : : #include "text-art/dump.h"
42 : :
43 : : #include "analyzer/analyzer-logging.h"
44 : : #include "analyzer/call-string.h"
45 : : #include "analyzer/program-point.h"
46 : : #include "analyzer/store.h"
47 : : #include "analyzer/region-model.h"
48 : : #include "analyzer/constraint-manager.h"
49 : : #include "analyzer/sm.h"
50 : : #include "analyzer/pending-diagnostic.h"
51 : : #include "analyzer/diagnostic-manager.h"
52 : : #include "analyzer/supergraph.h"
53 : : #include "analyzer/program-state.h"
54 : : #include "analyzer/exploded-graph.h"
55 : : #include "analyzer/analysis-plan.h"
56 : : #include "analyzer/checker-path.h"
57 : : #include "analyzer/state-purge.h"
58 : : #include "analyzer/bar-chart.h"
59 : : #include "analyzer/call-info.h"
60 : : #include "analyzer/known-function-manager.h"
61 : : #include "analyzer/call-summary.h"
62 : : #include "analyzer/impl-sm-context.h"
63 : :
64 : : /* For an overview, see gcc/doc/analyzer.texi. */
65 : :
66 : : #if ENABLE_ANALYZER
67 : :
68 : : namespace ana {
69 : :
70 : : /* class impl_region_model_context : public region_model_context. */
71 : :
72 : 1347021 : impl_region_model_context::
73 : : impl_region_model_context (exploded_graph &eg,
74 : : exploded_node *enode_for_diag,
75 : : const program_state *old_state,
76 : : program_state *new_state,
77 : : uncertainty_t *uncertainty,
78 : : path_context *path_ctxt,
79 : : const gimple *stmt,
80 : 1347021 : bool *out_could_have_done_work)
81 : 1347021 : : m_eg (&eg), m_logger (eg.get_logger ()),
82 : 1347021 : m_enode_for_diag (enode_for_diag),
83 : 1347021 : m_old_state (old_state),
84 : 1347021 : m_new_state (new_state),
85 : 1347021 : m_stmt (stmt),
86 : 1347021 : m_ext_state (eg.get_ext_state ()),
87 : 1347021 : m_uncertainty (uncertainty),
88 : 1347021 : m_path_ctxt (path_ctxt),
89 : 1347021 : m_out_could_have_done_work (out_could_have_done_work)
90 : : {
91 : 1347021 : }
92 : :
93 : 4 : impl_region_model_context::
94 : : impl_region_model_context (program_state *state,
95 : : const extrinsic_state &ext_state,
96 : : uncertainty_t *uncertainty,
97 : 4 : logger *logger)
98 : 4 : : m_eg (nullptr), m_logger (logger), m_enode_for_diag (nullptr),
99 : 4 : m_old_state (nullptr),
100 : 4 : m_new_state (state),
101 : 4 : m_stmt (nullptr),
102 : 4 : m_ext_state (ext_state),
103 : 4 : m_uncertainty (uncertainty),
104 : 4 : m_path_ctxt (nullptr),
105 : 4 : m_out_could_have_done_work (nullptr)
106 : : {
107 : 4 : }
108 : :
109 : : bool
110 : 3016 : impl_region_model_context::warn_at (std::unique_ptr<pending_diagnostic> d,
111 : : pending_location &&ploc)
112 : : {
113 : 3016 : LOG_FUNC (get_logger ());
114 : 3016 : if (m_eg)
115 : : {
116 : 3016 : bool terminate_path = d->terminate_path_p ();
117 : 3016 : if (m_eg->get_diagnostic_manager ().add_diagnostic (std::move (ploc),
118 : : std::move (d)))
119 : : {
120 : 2977 : if (m_path_ctxt
121 : 2124 : && terminate_path
122 : 836 : && flag_analyzer_suppress_followups)
123 : 631 : m_path_ctxt->terminate_path ();
124 : 2977 : return true;
125 : : }
126 : : }
127 : : return false;
128 : 3016 : }
129 : :
130 : : void
131 : 193 : impl_region_model_context::add_note (std::unique_ptr<pending_note> pn)
132 : : {
133 : 193 : LOG_FUNC (get_logger ());
134 : 193 : if (m_eg)
135 : 193 : m_eg->get_diagnostic_manager ().add_note (std::move (pn));
136 : 193 : }
137 : :
138 : : void
139 : 158 : impl_region_model_context::add_event (std::unique_ptr<checker_event> event)
140 : : {
141 : 158 : LOG_FUNC (get_logger ());
142 : 158 : if (m_eg)
143 : 158 : m_eg->get_diagnostic_manager ().add_event (std::move (event));
144 : 158 : }
145 : :
146 : : void
147 : 86363 : impl_region_model_context::on_svalue_leak (const svalue *sval)
148 : :
149 : : {
150 : 863293 : for (sm_state_map *smap : m_new_state->m_checker_states)
151 : 604204 : smap->on_svalue_leak (sval, this);
152 : 86363 : }
153 : :
154 : : void
155 : 482427 : impl_region_model_context::
156 : : on_liveness_change (const svalue_set &live_svalues,
157 : : const region_model *model)
158 : : {
159 : 4822109 : for (sm_state_map *smap : m_new_state->m_checker_states)
160 : 3374828 : smap->on_liveness_change (live_svalues, model, m_ext_state, this);
161 : 482427 : }
162 : :
163 : : void
164 : 51852 : impl_region_model_context::on_unknown_change (const svalue *sval,
165 : : bool is_mutable)
166 : : {
167 : 51852 : if (!sval->can_have_associated_state_p ())
168 : : return;
169 : 422025 : for (sm_state_map *smap : m_new_state->m_checker_states)
170 : 295392 : smap->on_unknown_change (sval, is_mutable, m_ext_state);
171 : : }
172 : :
173 : : void
174 : 310 : impl_region_model_context::on_escaped_function (tree fndecl)
175 : : {
176 : 310 : m_eg->on_escaped_function (fndecl);
177 : 310 : }
178 : :
179 : : uncertainty_t *
180 : 4093288 : impl_region_model_context::get_uncertainty ()
181 : : {
182 : 4093288 : return m_uncertainty;
183 : : }
184 : :
185 : : /* Purge state involving SVAL. The region_model has already been purged,
186 : : so we only need to purge other state in the program_state:
187 : : the sm-state. */
188 : :
189 : : void
190 : 15743 : impl_region_model_context::purge_state_involving (const svalue *sval)
191 : : {
192 : 15743 : int i;
193 : 15743 : sm_state_map *smap;
194 : 125944 : FOR_EACH_VEC_ELT (m_new_state->m_checker_states, i, smap)
195 : 110201 : smap->purge_state_involving (sval, m_ext_state);
196 : 15743 : }
197 : :
198 : : void
199 : 8256 : impl_region_model_context::bifurcate (std::unique_ptr<custom_edge_info> info)
200 : : {
201 : 8256 : if (m_path_ctxt)
202 : 8256 : m_path_ctxt->bifurcate (std::move (info));
203 : 8256 : }
204 : :
205 : : void
206 : 1154 : impl_region_model_context::terminate_path ()
207 : : {
208 : 1154 : if (m_path_ctxt)
209 : 1154 : return m_path_ctxt->terminate_path ();
210 : : }
211 : :
212 : : /* struct setjmp_record. */
213 : :
214 : : int
215 : 0 : setjmp_record::cmp (const setjmp_record &rec1, const setjmp_record &rec2)
216 : : {
217 : 0 : if (int cmp_enode = rec1.m_enode->m_index - rec2.m_enode->m_index)
218 : : return cmp_enode;
219 : 0 : gcc_assert (&rec1 == &rec2);
220 : : return 0;
221 : : }
222 : :
223 : : /* class setjmp_svalue : public svalue. */
224 : :
225 : : /* Implementation of svalue::accept vfunc for setjmp_svalue. */
226 : :
227 : : void
228 : 942 : setjmp_svalue::accept (visitor *v) const
229 : : {
230 : 942 : v->visit_setjmp_svalue (this);
231 : 942 : }
232 : :
233 : : /* Implementation of svalue::dump_to_pp vfunc for setjmp_svalue. */
234 : :
235 : : void
236 : 0 : setjmp_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
237 : : {
238 : 0 : if (simple)
239 : 0 : pp_printf (pp, "SETJMP(EN: %i)", get_enode_index ());
240 : : else
241 : 0 : pp_printf (pp, "setjmp_svalue(EN%i)", get_enode_index ());
242 : 0 : }
243 : :
244 : : /* Implementation of svalue::print_dump_widget_label vfunc for
245 : : setjmp_svalue. */
246 : :
247 : : void
248 : 0 : setjmp_svalue::print_dump_widget_label (pretty_printer *pp) const
249 : : {
250 : 0 : pp_printf (pp, "setjmp_svalue(EN: %i)", get_enode_index ());
251 : 0 : }
252 : :
253 : : /* Implementation of svalue::add_dump_widget_children vfunc for
254 : : setjmp_svalue. */
255 : :
256 : : void
257 : 0 : setjmp_svalue::
258 : : add_dump_widget_children (text_art::tree_widget &,
259 : : const text_art::dump_widget_info &) const
260 : : {
261 : : /* No children. */
262 : 0 : }
263 : :
264 : : /* Get the index of the stored exploded_node. */
265 : :
266 : : int
267 : 0 : setjmp_svalue::get_enode_index () const
268 : : {
269 : 0 : return m_setjmp_record.m_enode->m_index;
270 : : }
271 : :
272 : : bool
273 : 722539 : impl_region_model_context::
274 : : get_state_map_by_name (const char *name,
275 : : sm_state_map **out_smap,
276 : : const state_machine **out_sm,
277 : : unsigned *out_sm_idx,
278 : : std::unique_ptr<sm_context> *out_sm_context)
279 : : {
280 : 722539 : if (!m_new_state)
281 : : return false;
282 : :
283 : 719528 : unsigned sm_idx;
284 : 719528 : if (!m_ext_state.get_sm_idx_by_name (name, &sm_idx))
285 : : return false;
286 : :
287 : 719061 : const state_machine *sm = &m_ext_state.get_sm (sm_idx);
288 : 719061 : sm_state_map *new_smap = m_new_state->m_checker_states[sm_idx];
289 : :
290 : 719061 : *out_smap = new_smap;
291 : 719061 : *out_sm = sm;
292 : 719061 : if (out_sm_idx)
293 : 718295 : *out_sm_idx = sm_idx;
294 : 719061 : if (out_sm_context)
295 : : {
296 : 748 : const sm_state_map *old_smap = m_old_state->m_checker_states[sm_idx];
297 : 748 : *out_sm_context
298 : 748 : = std::make_unique<impl_sm_context> (*m_eg,
299 : : sm_idx,
300 : : *sm,
301 : 748 : m_enode_for_diag,
302 : 748 : m_old_state,
303 : 748 : m_new_state,
304 : : old_smap,
305 : : new_smap,
306 : 748 : m_path_ctxt,
307 : 1496 : false);
308 : : }
309 : : return true;
310 : : }
311 : :
312 : : /* Subclass of pending_location::fixer_for_epath for finding the best stmt
313 : : to report the leak at, given the emission path. */
314 : :
315 : : class leak_ploc_fixer_for_epath : public pending_location::fixer_for_epath
316 : : {
317 : : public:
318 : 1298 : leak_ploc_fixer_for_epath (const exploded_graph &eg, tree var)
319 : 1298 : : m_eg (eg), m_var (var)
320 : : {}
321 : :
322 : : void
323 : 1182 : fixup_for_epath (const exploded_path &epath,
324 : : pending_location &ploc) const final override
325 : : {
326 : 1182 : logger * const logger = m_eg.get_logger ();
327 : 1182 : LOG_FUNC (logger);
328 : :
329 : : /* Handle the interprocedural case where we leak the retval at a return
330 : : because the caller discards the return value. */
331 : 1182 : if (m_var
332 : 1002 : && TREE_CODE (m_var) == RESULT_DECL)
333 : : {
334 : 6 : auto &point = ploc.m_enode->get_point ();
335 : 12 : if (point.get_stack_depth () > 1)
336 : 6 : if (point.get_supernode ()->exit_p ())
337 : : {
338 : : /* Get the program_point for the call within the caller. */
339 : 6 : auto &cs = point.get_call_string ();
340 : 6 : auto caller_snode = cs.get_return_node_in_caller ();
341 : 6 : gcc_assert (caller_snode);
342 : 6 : program_point caller_point (caller_snode, *cs.get_parent ());
343 : 6 : ploc.m_event_loc_info = event_loc_info (caller_point);
344 : 6 : return;
345 : : }
346 : : }
347 : :
348 : : /* Handle the case where we have e.g.:
349 : : | var = malloc (N);
350 : : | var = NULL;
351 : : which with SSA becomes e.g.:
352 : : | var_0 = malloc (N);
353 : : | var_1 = nullptr;
354 : : and thus leads to the leak being found at the enode where "var_0" goes
355 : : out of scope.
356 : : Fix up the location of the leak to report it at the write of NULL. */
357 : 1176 : if (m_var && TREE_CODE (m_var) == SSA_NAME)
358 : : {
359 : 804 : log_scope sentinel (logger, "looking for write to sibling SSA name");
360 : : /* Locate the final write to this SSA name in the path. */
361 : 804 : const gimple *def_stmt = SSA_NAME_DEF_STMT (m_var);
362 : :
363 : 804 : int idx_of_def_stmt;
364 : 804 : if (epath.find_stmt_backwards (def_stmt, &idx_of_def_stmt))
365 : : {
366 : : /* What was the next write to the underlying var
367 : : after the SSA name was set? (if any). */
368 : :
369 : 712 : for (unsigned idx = idx_of_def_stmt + 1;
370 : 10054 : idx < epath.m_edges.length ();
371 : : ++idx)
372 : : {
373 : 9344 : const exploded_edge *eedge = epath.m_edges[idx];
374 : 9344 : if (logger)
375 : 0 : logger->log ("eedge[%i]: EN %i -> EN %i",
376 : : idx,
377 : 0 : eedge->m_src->m_index,
378 : 0 : eedge->m_dest->m_index);
379 : 9344 : const gimple *stmt = eedge->maybe_get_stmt ();
380 : 9344 : if (!stmt)
381 : 2554 : continue;
382 : 11596 : if (const gassign *assign = dyn_cast <const gassign *> (stmt))
383 : : {
384 : 2254 : tree lhs = gimple_assign_lhs (assign);
385 : 2254 : if (TREE_CODE (lhs) == SSA_NAME
386 : 3728 : && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (m_var))
387 : : {
388 : 2 : if (logger)
389 : 0 : logger->log ("using location 0%lx from gassign",
390 : 0 : assign->location);
391 : 2 : ploc.m_event_loc_info.m_loc = assign->location;
392 : 2 : return;
393 : : }
394 : : }
395 : : }
396 : : }
397 : 804 : }
398 : :
399 : : /* If the epath ends at a function exit node, the location is at
400 : : the final "}". Try walking backward along EPATH, looking for a
401 : : the first suitable stmt with a better location. */
402 : 1174 : gcc_assert (ploc.m_enode->get_supernode ());
403 : 1174 : const greturn *return_stmt = nullptr;
404 : 1174 : if (ploc.m_enode->get_supernode ()->exit_p ()
405 : 1174 : && has_return_stmt_p (epath, return_stmt, logger))
406 : : {
407 : : /* If we have "return SSA_NAME;" on EPATH, keep track of the
408 : : pertinent SSA name as we walk backwards through EPATH. */
409 : 756 : tree retval = NULL_TREE;
410 : 756 : if (return_stmt)
411 : 756 : retval = gimple_return_retval (return_stmt);
412 : :
413 : 756 : log_scope sentinel (logger, "walking backward along epath");
414 : 756 : int idx;
415 : 756 : const exploded_edge *eedge;
416 : 3046 : FOR_EACH_VEC_ELT_REVERSE (epath.m_edges, idx, eedge)
417 : : {
418 : 2240 : if (logger)
419 : : {
420 : 0 : logger->log ("eedge[%i]: EN %i -> EN %i",
421 : : idx,
422 : 0 : eedge->m_src->m_index,
423 : 0 : eedge->m_dest->m_index);
424 : 0 : if (retval)
425 : 0 : logger->log (" retval: %qE", retval);
426 : : }
427 : 2240 : if (auto op = eedge->maybe_get_op ())
428 : : {
429 : 1288 : if (retval)
430 : 406 : if (auto phis = op->dyn_cast_phis_for_edge_op ())
431 : : {
432 : 184 : for (auto iter : phis->get_pairs ())
433 : 92 : if (retval == iter.m_dst)
434 : : {
435 : : /* We have "PHI(RETVAL = SRC);"
436 : : Track SRC instead */
437 : 92 : retval = iter.m_src;
438 : 92 : if (logger)
439 : 0 : logger->log ("updating retval to %qE", retval);
440 : : }
441 : : }
442 : 1288 : if (const gimple *stmt = op->maybe_get_stmt ())
443 : 1196 : if (consider_stmt_location_p (*stmt, retval))
444 : 952 : if (useful_location_p (stmt->location))
445 : : {
446 : 706 : if (logger)
447 : 0 : logger->log ("using location 0x%lx from stmt",
448 : 0 : stmt->location);
449 : 706 : ploc.m_event_loc_info.m_loc = stmt->location;
450 : 706 : return;
451 : : }
452 : : }
453 : : }
454 : 756 : }
455 : 1182 : }
456 : :
457 : : private:
458 : : static bool
459 : 756 : has_return_stmt_p (const exploded_path &epath,
460 : : const greturn *&out_greturn,
461 : : logger *logger)
462 : : {
463 : 756 : LOG_SCOPE (logger);
464 : :
465 : 756 : int idx;
466 : 756 : const exploded_edge *eedge;
467 : 2028 : FOR_EACH_VEC_ELT_REVERSE (epath.m_edges, idx, eedge)
468 : : {
469 : 1272 : if (eedge->m_src->get_stack_depth ()
470 : 2544 : != eedge->m_dest->get_stack_depth ())
471 : : {
472 : : /* We have interprocedural activity, and
473 : : presumably are no longer in the function where
474 : : EPATH terminates.
475 : : Give up. */
476 : : return false;
477 : : }
478 : 1272 : if (auto op = eedge->maybe_get_op ())
479 : : {
480 : 756 : switch (op->get_kind ())
481 : : {
482 : : default:
483 : : break;
484 : 756 : case operation::kind::return_stmt:
485 : 756 : if (logger)
486 : 0 : logger->log ("found return_stmt");
487 : 756 : out_greturn = &((const greturn_op *)op)->get_greturn ();
488 : 756 : return true;
489 : 0 : case operation::kind::predict_stmt:
490 : 0 : {
491 : 0 : auto &stmt = ((const gimple_stmt_op *)op)->get_stmt ();
492 : 0 : switch (gimple_predict_predictor (&stmt))
493 : : {
494 : 0 : case PRED_TREE_EARLY_RETURN:
495 : : /* Assume this is due to a "return;" in the user's
496 : : code. */
497 : 0 : if (logger)
498 : 0 : logger->log ("assuming a return: PRED_TREE_EARLY_RETURN");
499 : 0 : return true;
500 : : default:
501 : : break;
502 : : }
503 : : }
504 : : break;
505 : : }
506 : : }
507 : : }
508 : : return false;
509 : 756 : }
510 : :
511 : : /* When certain statements show up on the epath of a leak
512 : : at an exit node, if they have locations, these locations
513 : : tend to be better locations for the leak.
514 : : Return true for such statements (but without checking their
515 : : locations). */
516 : : static bool
517 : 1196 : consider_stmt_location_p (const gimple &stmt,
518 : : tree retval)
519 : : {
520 : 1196 : if (retval && TREE_CODE (retval) == SSA_NAME)
521 : 312 : if (&stmt == SSA_NAME_DEF_STMT (retval))
522 : : return true;
523 : :
524 : 1172 : switch (stmt.code)
525 : : {
526 : : default:
527 : : break;
528 : 92 : case GIMPLE_CALL:
529 : 92 : {
530 : 92 : const gcall &call = *as_a <const gcall *> (&stmt);
531 : 92 : if (is_cxa_end_catch_p (call))
532 : : return true;
533 : : }
534 : : break;
535 : : case GIMPLE_PREDICT:
536 : : case GIMPLE_RETURN:
537 : : return true;
538 : : }
539 : : return false;
540 : : }
541 : :
542 : : const exploded_graph &m_eg;
543 : : tree m_var;
544 : : };
545 : :
546 : : std::unique_ptr<pending_location::fixer_for_epath>
547 : 0 : make_ploc_fixer_for_epath_for_leak_diagnostic (const exploded_graph &eg,
548 : : tree var)
549 : : {
550 : 0 : return std::make_unique<leak_ploc_fixer_for_epath> (eg, var);
551 : : }
552 : :
553 : : /* A measurement of how good EXPR is for presenting to the user, so
554 : : that e.g. we can say prefer printing
555 : : "leak of 'tmp.m_ptr'"
556 : : over:
557 : : "leak of '<unknown>'". */
558 : :
559 : : static int
560 : 10672 : readability (const_tree expr)
561 : : {
562 : : /* Arbitrarily-chosen "high readability" value. */
563 : 19889 : const int HIGH_READABILITY = 65536;
564 : :
565 : 19889 : gcc_assert (expr);
566 : 19889 : switch (TREE_CODE (expr))
567 : : {
568 : 2524 : case COMPONENT_REF:
569 : 2524 : case MEM_REF:
570 : : /* Impose a slight readability penalty relative to that of
571 : : operand 0. */
572 : 2524 : return readability (TREE_OPERAND (expr, 0)) - 16;
573 : :
574 : 7700 : case SSA_NAME:
575 : 7700 : {
576 : 7700 : if (tree var = SSA_NAME_VAR (expr))
577 : : {
578 : 5665 : if (DECL_ARTIFICIAL (var))
579 : : {
580 : : /* If we have an SSA name for an artificial var,
581 : : only use it if it has a debug expr associated with
582 : : it that fixup_tree_for_diagnostic can use. */
583 : 12 : if (VAR_P (var) && DECL_HAS_DEBUG_EXPR_P (var))
584 : 0 : return readability (DECL_DEBUG_EXPR (var)) - 1;
585 : : }
586 : : else
587 : : {
588 : : /* Slightly favor the underlying var over the SSA name to
589 : : avoid having them compare equal. */
590 : 5653 : return readability (var) - 1;
591 : : }
592 : : }
593 : : /* Avoid printing '<unknown>' for SSA names for temporaries. */
594 : : return -1;
595 : : }
596 : 6997 : break;
597 : :
598 : 6997 : case PARM_DECL:
599 : 6997 : case VAR_DECL:
600 : 6997 : if (DECL_NAME (expr))
601 : : return HIGH_READABILITY;
602 : : else
603 : : /* We don't want to print temporaries. For example, the C FE
604 : : prints them as e.g. "<Uxxxx>" where "xxxx" is the low 16 bits
605 : : of the tree pointer (see pp_c_tree_decl_identifier). */
606 : : return -1;
607 : :
608 : : case RESULT_DECL:
609 : : /* Printing "<return-value>" isn't ideal, but is less awful than
610 : : trying to print a temporary. */
611 : : return HIGH_READABILITY / 2;
612 : :
613 : 1040 : case NOP_EXPR:
614 : 1040 : {
615 : : /* Impose a moderate readability penalty for casts. */
616 : 1040 : const int CAST_PENALTY = 32;
617 : 1040 : return readability (TREE_OPERAND (expr, 0)) - CAST_PENALTY;
618 : : }
619 : :
620 : : case INTEGER_CST:
621 : : return HIGH_READABILITY;
622 : :
623 : 184 : default:
624 : 184 : return 0;
625 : : }
626 : :
627 : : return 0;
628 : : }
629 : :
630 : : /* A qsort comparator for trees to sort them into most user-readable to
631 : : least user-readable. */
632 : :
633 : : int
634 : 5336 : readability_comparator (const void *p1, const void *p2)
635 : : {
636 : 5336 : path_var pv1 = *(path_var const *)p1;
637 : 5336 : path_var pv2 = *(path_var const *)p2;
638 : :
639 : 5336 : const int tree_r1 = readability (pv1.m_tree);
640 : 5336 : const int tree_r2 = readability (pv2.m_tree);
641 : :
642 : : /* Favor items that are deeper on the stack and hence more recent;
643 : : this also favors locals over globals. */
644 : 5336 : const int COST_PER_FRAME = 64;
645 : 5336 : const int depth_r1 = pv1.m_stack_depth * COST_PER_FRAME;
646 : 5336 : const int depth_r2 = pv2.m_stack_depth * COST_PER_FRAME;
647 : :
648 : : /* Combine the scores from the tree and from the stack depth.
649 : : This e.g. lets us have a slightly penalized cast in the most
650 : : recent stack frame "beat" an uncast value in an older stack frame. */
651 : 5336 : const int sum_r1 = tree_r1 + depth_r1;
652 : 5336 : const int sum_r2 = tree_r2 + depth_r2;
653 : 5336 : if (int cmp = sum_r2 - sum_r1)
654 : : return cmp;
655 : :
656 : : /* Otherwise, more readable trees win. */
657 : 942 : if (int cmp = tree_r2 - tree_r1)
658 : : return cmp;
659 : :
660 : : /* Otherwise, if they have the same readability, then impose an
661 : : arbitrary deterministic ordering on them. */
662 : :
663 : 942 : if (int cmp = TREE_CODE (pv1.m_tree) - TREE_CODE (pv2.m_tree))
664 : : return cmp;
665 : :
666 : 882 : switch (TREE_CODE (pv1.m_tree))
667 : : {
668 : : default:
669 : : break;
670 : 852 : case SSA_NAME:
671 : 852 : if (int cmp = (SSA_NAME_VERSION (pv1.m_tree)
672 : 852 : - SSA_NAME_VERSION (pv2.m_tree)))
673 : : return cmp;
674 : : break;
675 : 0 : case PARM_DECL:
676 : 0 : case VAR_DECL:
677 : 0 : case RESULT_DECL:
678 : 0 : if (int cmp = DECL_UID (pv1.m_tree) - DECL_UID (pv2.m_tree))
679 : : return cmp;
680 : : break;
681 : : }
682 : :
683 : : /* TODO: We ought to find ways of sorting such cases. */
684 : : return 0;
685 : : }
686 : :
687 : : /* Return true is SNODE is the EXIT node of a function, or is one
688 : : of the final snodes within its function.
689 : :
690 : : Specifically, handle the final supernodes before the EXIT node,
691 : : for the case of clobbers that happen immediately before exiting.
692 : : We need a run of snodes leading to the return_p snode, where all edges are
693 : : intraprocedural, and every snode has just one successor.
694 : :
695 : : We use this when suppressing leak reports at the end of "main". */
696 : :
697 : : static bool
698 : 1613 : returning_from_function_p (const supernode *snode)
699 : : {
700 : 1613 : if (!snode)
701 : : return false;
702 : :
703 : : unsigned count = 0;
704 : : const supernode *iter = snode;
705 : 2584 : while (true)
706 : : {
707 : 2584 : if (iter->exit_p ())
708 : : return true;
709 : 1667 : if (iter->m_succs.length () != 1)
710 : : return false;
711 : 1500 : const superedge *sedge = iter->m_succs[0];
712 : :
713 : 1500 : if (auto op = sedge->get_op ())
714 : 1209 : if (op->get_kind () == operation::kind::return_stmt)
715 : : return true;
716 : :
717 : 1005 : iter = sedge->m_dest;
718 : :
719 : : /* Impose a limit to ensure we terminate for pathological cases.
720 : :
721 : : We only care about the final 3 nodes, due to cases like:
722 : : BB:
723 : : (clobber causing leak)
724 : :
725 : : BB:
726 : : <label>:
727 : : return _val;
728 : :
729 : : EXIT BB.*/
730 : 1005 : if (++count > 4)
731 : : return false;
732 : : }
733 : : }
734 : :
735 : : /* Find the best tree for SVAL and call SM's on_leak vfunc with it.
736 : : If on_leak returns a pending_diagnostic, queue it up to be reported,
737 : : so that we potentially complain about a leak of SVAL in the given STATE. */
738 : :
739 : : void
740 : 1613 : impl_region_model_context::on_state_leak (const state_machine &sm,
741 : : const svalue *sval,
742 : : state_machine::state_t state)
743 : : {
744 : 1613 : logger * const logger = get_logger ();
745 : 1613 : LOG_SCOPE (logger);
746 : 1613 : if (logger)
747 : : {
748 : 0 : logger->start_log_line ();
749 : 0 : logger->log_partial ("considering leak of ");
750 : 0 : sval->dump_to_pp (logger->get_printer (), true);
751 : 0 : logger->end_log_line ();
752 : : }
753 : :
754 : 1613 : if (!m_eg)
755 : : return;
756 : :
757 : : /* m_old_state also needs to be non-NULL so that the sm_ctxt can look
758 : : up the old state of SVAL. */
759 : 1613 : gcc_assert (m_old_state);
760 : :
761 : : /* SVAL has leaked within the new state: it is not used by any reachable
762 : : regions.
763 : : We need to convert it back to a tree, but since it's likely no regions
764 : : use it, we have to find the "best" tree for it in the old_state. */
765 : 1613 : svalue_set visited;
766 : 1613 : path_var leaked_pv
767 : 1613 : = m_old_state->m_region_model->get_representative_path_var (sval,
768 : : &visited,
769 : : nullptr);
770 : :
771 : : /* Strip off top-level casts */
772 : 1613 : if (leaked_pv.m_tree && TREE_CODE (leaked_pv.m_tree) == NOP_EXPR)
773 : 94 : leaked_pv.m_tree = TREE_OPERAND (leaked_pv.m_tree, 0);
774 : :
775 : : /* This might be NULL; the pending_diagnostic subclasses need to cope
776 : : with this. */
777 : 1613 : tree leaked_tree = leaked_pv.m_tree;
778 : 1613 : if (logger)
779 : : {
780 : 0 : if (leaked_tree)
781 : 0 : logger->log ("best leaked_tree: %qE", leaked_tree);
782 : : else
783 : 0 : logger->log ("best leaked_tree: NULL");
784 : : }
785 : :
786 : 1613 : gcc_assert (m_enode_for_diag);
787 : :
788 : : /* Don't complain about leaks when returning from "main". */
789 : 1613 : if (returning_from_function_p (m_enode_for_diag->get_supernode ()))
790 : : {
791 : 1446 : tree fndecl = m_enode_for_diag->get_function ()->decl;
792 : 1446 : if (id_equal (DECL_NAME (fndecl), "main"))
793 : : {
794 : 66 : if (logger)
795 : 0 : logger->log ("not reporting leak from main");
796 : 66 : return;
797 : : }
798 : : }
799 : :
800 : 1547 : tree leaked_tree_for_diag = fixup_tree_for_diagnostic (leaked_tree);
801 : 1547 : std::unique_ptr<pending_diagnostic> pd = sm.on_leak (leaked_tree_for_diag,
802 : : m_old_state,
803 : 1547 : m_new_state);
804 : 1547 : if (pd)
805 : : {
806 : 1298 : pending_location ploc (get_pending_location_for_diag ());
807 : 1298 : ploc.m_fixer_for_epath
808 : 1298 : = std::make_unique<leak_ploc_fixer_for_epath> (*m_eg, leaked_tree);
809 : 1298 : m_eg->get_diagnostic_manager ().add_diagnostic
810 : 1298 : (&sm, std::move (ploc),
811 : : leaked_tree_for_diag, sval, state, std::move (pd));
812 : 1298 : }
813 : 1613 : }
814 : :
815 : : /* Implementation of region_model_context::on_condition vfunc.
816 : : Notify all state machines about the condition, which could lead to
817 : : state transitions. */
818 : :
819 : : void
820 : 34256 : impl_region_model_context::on_condition (const svalue *lhs,
821 : : enum tree_code op,
822 : : const svalue *rhs)
823 : : {
824 : 34256 : int sm_idx;
825 : 34256 : sm_state_map *smap;
826 : 273838 : FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
827 : : {
828 : 239582 : const state_machine &sm = m_ext_state.get_sm (sm_idx);
829 : 479164 : impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
830 : : m_old_state, m_new_state,
831 : 479164 : m_old_state->m_checker_states[sm_idx],
832 : 479164 : m_new_state->m_checker_states[sm_idx],
833 : 239582 : m_path_ctxt);
834 : 239582 : sm.on_condition (sm_ctxt, lhs, op, rhs);
835 : 239582 : }
836 : 34256 : }
837 : :
838 : : /* Implementation of region_model_context::on_bounded_ranges vfunc.
839 : : Notify all state machines about the ranges, which could lead to
840 : : state transitions. */
841 : :
842 : : void
843 : 6095 : impl_region_model_context::on_bounded_ranges (const svalue &sval,
844 : : const bounded_ranges &ranges)
845 : : {
846 : 6095 : int sm_idx;
847 : 6095 : sm_state_map *smap;
848 : 48760 : FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
849 : : {
850 : 42665 : const state_machine &sm = m_ext_state.get_sm (sm_idx);
851 : 85330 : impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
852 : : m_old_state, m_new_state,
853 : 85330 : m_old_state->m_checker_states[sm_idx],
854 : 85330 : m_new_state->m_checker_states[sm_idx],
855 : 42665 : m_path_ctxt);
856 : 42665 : sm.on_bounded_ranges (sm_ctxt, sval, ranges);
857 : 42665 : }
858 : 6095 : }
859 : :
860 : : /* Implementation of region_model_context::on_pop_frame vfunc.
861 : : Notify all state machines about the frame being popped, which
862 : : could lead to states being discarded. */
863 : :
864 : : void
865 : 23401 : impl_region_model_context::on_pop_frame (const frame_region *frame_reg)
866 : : {
867 : 23401 : int sm_idx;
868 : 23401 : sm_state_map *smap;
869 : 186840 : FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
870 : : {
871 : 163439 : const state_machine &sm = m_ext_state.get_sm (sm_idx);
872 : 163439 : sm.on_pop_frame (smap, frame_reg);
873 : : }
874 : 23401 : }
875 : :
876 : : /* Implementation of region_model_context::on_phi vfunc.
877 : : Notify all state machines about the phi, which could lead to
878 : : state transitions. */
879 : :
880 : : void
881 : 0 : impl_region_model_context::on_phi (const gphi *phi, tree rhs)
882 : : {
883 : 0 : int sm_idx;
884 : 0 : sm_state_map *smap;
885 : 0 : FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap)
886 : : {
887 : 0 : const state_machine &sm = m_ext_state.get_sm (sm_idx);
888 : 0 : impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag,
889 : : m_old_state, m_new_state,
890 : 0 : m_old_state->m_checker_states[sm_idx],
891 : 0 : m_new_state->m_checker_states[sm_idx],
892 : 0 : m_path_ctxt);
893 : 0 : sm.on_phi (sm_ctxt, phi, rhs);
894 : 0 : }
895 : 0 : }
896 : :
897 : : /* Implementation of region_model_context::on_unexpected_tree_code vfunc.
898 : : Mark the new state as being invalid for further exploration.
899 : : TODO(stage1): introduce a warning for when this occurs. */
900 : :
901 : : void
902 : 50 : impl_region_model_context::on_unexpected_tree_code (tree t,
903 : : const dump_location_t &loc)
904 : : {
905 : 50 : logger * const logger = get_logger ();
906 : 50 : if (logger)
907 : 0 : logger->log ("unhandled tree code: %qs in %qs at %s:%i",
908 : 0 : get_tree_code_name (TREE_CODE (t)),
909 : 0 : loc.get_impl_location ().m_function,
910 : 0 : loc.get_impl_location ().m_file,
911 : 0 : loc.get_impl_location ().m_line);
912 : 50 : if (m_new_state)
913 : 50 : m_new_state->m_valid = false;
914 : 50 : }
915 : :
916 : : /* Implementation of region_model_context::maybe_did_work vfunc.
917 : : Mark that "externally visible work" has occurred, and thus we
918 : : shouldn't report an infinite loop here. */
919 : :
920 : : void
921 : 24429 : impl_region_model_context::maybe_did_work ()
922 : : {
923 : 24429 : if (m_out_could_have_done_work)
924 : 22886 : *m_out_could_have_done_work = true;
925 : 24429 : }
926 : :
927 : : pending_location
928 : 4314 : impl_region_model_context::get_pending_location_for_diag () const
929 : : {
930 : 4314 : if (m_stmt && useful_location_p (m_stmt->location))
931 : 3001 : return pending_location (m_enode_for_diag, m_stmt->location);
932 : : else
933 : 1313 : return pending_location (m_enode_for_diag);
934 : : }
935 : :
936 : : /* struct point_and_state. */
937 : :
938 : : /* Assert that this object is sane. */
939 : :
940 : : void
941 : 783603 : point_and_state::validate (const extrinsic_state &ext_state) const
942 : : {
943 : : /* Skip this in a release build. */
944 : : #if !CHECKING_P
945 : : return;
946 : : #endif
947 : :
948 : 783603 : m_point.validate ();
949 : :
950 : 783603 : m_state.validate (ext_state);
951 : :
952 : : /* Verify that the callstring's model of the stack corresponds to that
953 : : of the region_model. */
954 : : /* They should have the same depth. */
955 : 1560562 : gcc_assert (m_point.get_stack_depth ()
956 : : == m_state.m_region_model->get_stack_depth ());
957 : : /* Check the functions in the callstring vs those in the frames
958 : : at each depth. */
959 : 1148768 : for (const frame_region *iter_frame
960 : 783603 : = m_state.m_region_model->get_current_frame ();
961 : 1932371 : iter_frame; iter_frame = iter_frame->get_calling_frame ())
962 : : {
963 : 1148768 : int index = iter_frame->get_index ();
964 : 1148768 : gcc_assert (m_point.get_function_at_depth (index)
965 : : == &iter_frame->get_function ());
966 : : }
967 : 783603 : }
968 : :
969 : : /* Subroutine of print_enode_indices: print a run of indices from START_IDX
970 : : to END_IDX to PP, using and updating *FIRST_RUN. */
971 : :
972 : : static void
973 : 9935 : print_run (pretty_printer *pp, int start_idx, int end_idx,
974 : : bool *first_run)
975 : : {
976 : 9935 : if (!(*first_run))
977 : 7031 : pp_string (pp, ", ");
978 : 9935 : *first_run = false;
979 : 9935 : if (start_idx == end_idx)
980 : 6902 : pp_printf (pp, "EN: %i", start_idx);
981 : : else
982 : 3033 : pp_printf (pp, "EN: %i-%i", start_idx, end_idx);
983 : 9935 : }
984 : :
985 : : /* Print the indices within ENODES to PP, collecting them as
986 : : runs/singletons e.g. "EN: 4-7, EN: 20-23, EN: 42". */
987 : :
988 : : static void
989 : 2916 : print_enode_indices (pretty_printer *pp,
990 : : const auto_vec<exploded_node *> &enodes)
991 : : {
992 : 2916 : int cur_start_idx = -1;
993 : 2916 : int cur_finish_idx = -1;
994 : 2916 : bool first_run = true;
995 : 2916 : unsigned i;
996 : 2916 : exploded_node *enode;
997 : 21445 : FOR_EACH_VEC_ELT (enodes, i, enode)
998 : : {
999 : 18529 : if (cur_start_idx == -1)
1000 : : {
1001 : 2904 : gcc_assert (cur_finish_idx == -1);
1002 : 2904 : cur_start_idx = cur_finish_idx = enode->m_index;
1003 : : }
1004 : : else
1005 : : {
1006 : 15625 : if (enode->m_index == cur_finish_idx + 1)
1007 : : /* Continuation of a run. */
1008 : : cur_finish_idx = enode->m_index;
1009 : : else
1010 : : {
1011 : : /* Finish existing run, start a new one. */
1012 : 7031 : gcc_assert (cur_start_idx >= 0);
1013 : 7031 : gcc_assert (cur_finish_idx >= 0);
1014 : 7031 : print_run (pp, cur_start_idx, cur_finish_idx,
1015 : : &first_run);
1016 : 7031 : cur_start_idx = cur_finish_idx = enode->m_index;
1017 : : }
1018 : : }
1019 : : }
1020 : : /* Finish any existing run. */
1021 : 2916 : if (cur_start_idx >= 0)
1022 : : {
1023 : 2904 : gcc_assert (cur_finish_idx >= 0);
1024 : 2904 : print_run (pp, cur_start_idx, cur_finish_idx,
1025 : : &first_run);
1026 : : }
1027 : 2916 : }
1028 : :
1029 : : /* struct eg_traits::dump_args_t. */
1030 : :
1031 : : /* The <FILENAME>.eg.dot output can quickly become unwieldy if we show
1032 : : full details for all enodes (both in terms of CPU time to render it,
1033 : : and in terms of being meaningful to a human viewing it).
1034 : :
1035 : : If we show just the IDs then the resulting graph is usually viewable,
1036 : : but then we have to keep switching back and forth between the .dot
1037 : : view and other dumps.
1038 : :
1039 : : This function implements a heuristic for showing detail at the enodes
1040 : : that (we hope) matter, and just the ID at other enodes, fixing the CPU
1041 : : usage of the .dot viewer, and drawing the attention of the viewer
1042 : : to these enodes.
1043 : :
1044 : : Return true if ENODE should be shown in detail in .dot output.
1045 : : Return false if no detail should be shown for ENODE. */
1046 : :
1047 : : bool
1048 : 507 : eg_traits::dump_args_t::show_enode_details_p (const exploded_node &enode) const
1049 : : {
1050 : : /* If the number of exploded nodes isn't too large, we may as well show
1051 : : all enodes in full detail in the .dot output. */
1052 : 507 : if (m_eg.m_nodes.length ()
1053 : 507 : <= (unsigned) param_analyzer_max_enodes_for_full_dump)
1054 : : return true;
1055 : :
1056 : : /* Otherwise, assume that what's most interesting are state explosions,
1057 : : and thus the places where this happened.
1058 : : Expand enodes at program points where we hit the per-enode limit, so we
1059 : : can investigate what exploded. */
1060 : 0 : const per_program_point_data *per_point_data
1061 : 0 : = m_eg.get_per_program_point_data (enode.get_point ());
1062 : 0 : return per_point_data->m_excess_enodes > 0;
1063 : : }
1064 : :
1065 : : /* class exploded_node : public dnode<eg_traits>. */
1066 : :
1067 : : const char *
1068 : 0 : exploded_node::status_to_str (enum status s)
1069 : : {
1070 : 0 : switch (s)
1071 : : {
1072 : 0 : default: gcc_unreachable ();
1073 : : case status::worklist: return "worklist";
1074 : 0 : case status::processed: return "processed";
1075 : 0 : case status::special: return "special";
1076 : 0 : case status::merger: return "merger";
1077 : 0 : case status::bulk_merged: return "bulk_merged";
1078 : : }
1079 : : }
1080 : :
1081 : : /* exploded_node's ctor. */
1082 : :
1083 : 388177 : exploded_node::exploded_node (const point_and_state &ps,
1084 : 388177 : int index)
1085 : 388177 : : m_ps (ps), m_status (status::worklist), m_index (index),
1086 : 388177 : m_num_processed_stmts (0)
1087 : : {
1088 : 388177 : gcc_checking_assert (ps.get_state ().m_region_model->canonicalized_p ());
1089 : 388177 : }
1090 : :
1091 : : /* For use by dump_dot, get a value for the .dot "fillcolor" attribute.
1092 : : Colorize by sm-state, to make it easier to see how sm-state propagates
1093 : : through the exploded_graph. */
1094 : :
1095 : : const char *
1096 : 1014 : exploded_node::get_dot_fillcolor () const
1097 : : {
1098 : 1014 : const program_state &state = get_state ();
1099 : :
1100 : : /* We want to be able to easily distinguish the no-sm-state case,
1101 : : and to be able to distinguish cases where there's a single state
1102 : : from each other.
1103 : :
1104 : : Sum the sm_states, and use the result to choose from a table,
1105 : : modulo table-size, special-casing the "no sm-state" case. */
1106 : 1014 : int total_sm_state = 0;
1107 : 1014 : int i;
1108 : 1014 : sm_state_map *smap;
1109 : 8112 : FOR_EACH_VEC_ELT (state.m_checker_states, i, smap)
1110 : : {
1111 : 8450 : for (sm_state_map::iterator_t iter = smap->begin ();
1112 : 8450 : iter != smap->end ();
1113 : 1352 : ++iter)
1114 : 1352 : total_sm_state += (*iter).second.m_state->get_id ();
1115 : 7098 : total_sm_state += smap->get_global_state ()->get_id ();
1116 : : }
1117 : :
1118 : 1014 : if (total_sm_state > 0)
1119 : : {
1120 : : /* An arbitrarily-picked collection of light colors. */
1121 : 752 : const char * const colors[]
1122 : : = {"azure", "coral", "cornsilk", "lightblue", "yellow",
1123 : : "honeydew", "lightpink", "lightsalmon", "palegreen1",
1124 : : "wheat", "seashell"};
1125 : 752 : const int num_colors = ARRAY_SIZE (colors);
1126 : 752 : return colors[total_sm_state % num_colors];
1127 : : }
1128 : : else
1129 : : /* No sm-state. */
1130 : : return "lightgrey";
1131 : : }
1132 : :
1133 : : /* Implementation of dnode::dump_dot vfunc for exploded_node. */
1134 : :
1135 : : void
1136 : 507 : exploded_node::dump_dot (graphviz_out *gv, const dump_args_t &args) const
1137 : : {
1138 : 507 : pretty_printer *pp = gv->get_pp ();
1139 : :
1140 : 507 : dump_dot_id (pp);
1141 : 507 : pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
1142 : : get_dot_fillcolor ());
1143 : 507 : pp_write_text_to_stream (pp);
1144 : :
1145 : 507 : pp_printf (pp, "EN: %i", m_index);
1146 : 507 : if (m_status == status::merger)
1147 : 12 : pp_string (pp, " (merger)");
1148 : 495 : else if (m_status == status::bulk_merged)
1149 : 0 : pp_string (pp, " (bulk merged)");
1150 : 507 : pp_newline (pp);
1151 : :
1152 : 507 : if (args.show_enode_details_p (*this))
1153 : : {
1154 : 507 : format f (true);
1155 : 507 : m_ps.get_point ().print (pp, f);
1156 : 507 : pp_newline (pp);
1157 : :
1158 : 507 : bool show_state = true;
1159 : :
1160 : : /* Don't show the state if we have a single predecessor
1161 : : and the state hasn't changed. */
1162 : 507 : if (m_preds.length () == 1
1163 : 499 : && get_state () == m_preds[0]->m_src->get_state ())
1164 : : show_state = false;
1165 : :
1166 : 393 : if (show_state)
1167 : : {
1168 : 393 : const extrinsic_state &ext_state = args.m_eg.get_ext_state ();
1169 : 393 : const program_state &state = m_ps.get_state ();
1170 : 393 : state.dump_to_pp (ext_state, false, true, pp);
1171 : 393 : pp_newline (pp);
1172 : : }
1173 : : }
1174 : :
1175 : 507 : dump_saved_diagnostics (pp);
1176 : :
1177 : 507 : args.dump_extra_info (this, pp);
1178 : :
1179 : 507 : pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
1180 : :
1181 : 507 : pp_string (pp, "\"];\n\n");
1182 : :
1183 : : /* It can be hard to locate the saved diagnostics as text within the
1184 : : enode nodes, so add extra nodes to the graph for each saved_diagnostic,
1185 : : highlighted in red.
1186 : : Compare with dump_saved_diagnostics. */
1187 : 507 : {
1188 : 507 : unsigned i;
1189 : 507 : const saved_diagnostic *sd;
1190 : 1022 : FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
1191 : : {
1192 : 8 : sd->dump_as_dot_node (pp);
1193 : :
1194 : : /* Add edge connecting this enode to the saved_diagnostic. */
1195 : 8 : dump_dot_id (pp);
1196 : 8 : pp_string (pp, " -> ");
1197 : 8 : sd->dump_dot_id (pp);
1198 : 8 : pp_string (pp, " [style=\"dotted\" arrowhead=\"none\"];");
1199 : 8 : pp_newline (pp);
1200 : : }
1201 : : }
1202 : :
1203 : 507 : pp_flush (pp);
1204 : 507 : }
1205 : :
1206 : : /* Dump any saved_diagnostics at this enode to PP. */
1207 : :
1208 : : void
1209 : 581 : exploded_node::dump_saved_diagnostics (pretty_printer *pp) const
1210 : : {
1211 : 581 : unsigned i;
1212 : 581 : const saved_diagnostic *sd;
1213 : 593 : FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
1214 : : {
1215 : 12 : pp_printf (pp, "DIAGNOSTIC: %s (sd: %i)",
1216 : 12 : sd->m_d->get_kind (), sd->get_index ());
1217 : 12 : pp_newline (pp);
1218 : : }
1219 : 581 : }
1220 : :
1221 : : /* Dump this to PP in a form suitable for use as an id in .dot output. */
1222 : :
1223 : : void
1224 : 1545 : exploded_node::dump_dot_id (pretty_printer *pp) const
1225 : : {
1226 : 1545 : pp_printf (pp, "exploded_node_%i", m_index);
1227 : 1545 : }
1228 : :
1229 : : /* Dump a multiline representation of this node to PP. */
1230 : :
1231 : : void
1232 : 0 : exploded_node::dump_to_pp (pretty_printer *pp,
1233 : : const extrinsic_state &ext_state) const
1234 : : {
1235 : 0 : pp_printf (pp, "EN: %i", m_index);
1236 : 0 : pp_newline (pp);
1237 : :
1238 : 0 : format f (true);
1239 : 0 : m_ps.get_point ().print (pp, f);
1240 : 0 : pp_newline (pp);
1241 : :
1242 : 0 : m_ps.get_state ().dump_to_pp (ext_state, false, true, pp);
1243 : 0 : pp_newline (pp);
1244 : 0 : }
1245 : :
1246 : : /* Dump a multiline representation of this node to FILE. */
1247 : :
1248 : : void
1249 : 0 : exploded_node::dump (FILE *fp,
1250 : : const extrinsic_state &ext_state) const
1251 : : {
1252 : 0 : tree_dump_pretty_printer pp (fp);
1253 : 0 : dump_to_pp (&pp, ext_state);
1254 : 0 : }
1255 : :
1256 : : /* Dump a multiline representation of this node to stderr. */
1257 : :
1258 : : DEBUG_FUNCTION void
1259 : 0 : exploded_node::dump (const extrinsic_state &ext_state) const
1260 : : {
1261 : 0 : dump (stderr, ext_state);
1262 : 0 : }
1263 : :
1264 : : /* Return a new json::object of the form
1265 : : {"point" : object for program_point,
1266 : : "state" : object for program_state,
1267 : : "status" : str,
1268 : : "idx" : int,
1269 : : "processed_stmts" : int}. */
1270 : :
1271 : : std::unique_ptr<json::object>
1272 : 0 : exploded_node::to_json (const extrinsic_state &ext_state) const
1273 : : {
1274 : 0 : auto enode_obj = std::make_unique<json::object> ();
1275 : :
1276 : 0 : enode_obj->set ("point", get_point ().to_json ());
1277 : 0 : enode_obj->set ("state", get_state ().to_json (ext_state));
1278 : 0 : enode_obj->set_string ("status", status_to_str (m_status));
1279 : 0 : enode_obj->set_integer ("idx", m_index);
1280 : 0 : enode_obj->set_integer ("processed_stmts", m_num_processed_stmts);
1281 : :
1282 : 0 : return enode_obj;
1283 : : }
1284 : :
1285 : : } // namespace ana
1286 : :
1287 : : /* Return true if FNDECL has a gimple body. */
1288 : : // TODO: is there a pre-canned way to do this?
1289 : :
1290 : : bool
1291 : 17389 : fndecl_has_gimple_body_p (tree fndecl)
1292 : : {
1293 : 17389 : if (fndecl == NULL_TREE)
1294 : : return false;
1295 : :
1296 : 17389 : cgraph_node *n = cgraph_node::get (fndecl);
1297 : 17389 : if (!n)
1298 : : return false;
1299 : :
1300 : 17389 : return n->has_gimple_body_p ();
1301 : : }
1302 : :
1303 : : namespace ana {
1304 : :
1305 : : /* Verify that the stack at LONGJMP_POINT is still valid, given a call
1306 : : to "setjmp" at SETJMP_POINT - the stack frame that "setjmp" was
1307 : : called in must still be valid.
1308 : :
1309 : : Caveat: this merely checks the call_strings in the points; it doesn't
1310 : : detect the case where a frame returns and is then called again. */
1311 : :
1312 : : static bool
1313 : 111 : valid_longjmp_stack_p (const program_point &longjmp_point,
1314 : : const program_point &setjmp_point)
1315 : : {
1316 : 111 : const call_string &cs_at_longjmp = longjmp_point.get_call_string ();
1317 : 111 : const call_string &cs_at_setjmp = setjmp_point.get_call_string ();
1318 : :
1319 : 282 : if (cs_at_longjmp.length () < cs_at_setjmp.length ())
1320 : : return false;
1321 : :
1322 : : /* Check that the call strings match, up to the depth of the
1323 : : setjmp point. */
1324 : 150 : for (unsigned depth = 0; depth < cs_at_setjmp.length (); depth++)
1325 : 65 : if (cs_at_longjmp[depth] != cs_at_setjmp[depth])
1326 : : return false;
1327 : :
1328 : : return true;
1329 : : }
1330 : :
1331 : : /* A pending_diagnostic subclass for complaining about bad longjmps,
1332 : : where the enclosing function of the "setjmp" has returned (and thus
1333 : : the stack frame no longer exists). */
1334 : :
1335 : : class stale_jmp_buf : public pending_diagnostic_subclass<stale_jmp_buf>
1336 : : {
1337 : : public:
1338 : 5 : stale_jmp_buf (const gcall &setjmp_call, const gcall &longjmp_call,
1339 : : const program_point &setjmp_point)
1340 : 5 : : m_setjmp_call (setjmp_call), m_longjmp_call (longjmp_call),
1341 : 5 : m_setjmp_point (setjmp_point), m_stack_pop_event (nullptr)
1342 : : {}
1343 : :
1344 : 10 : int get_controlling_option () const final override
1345 : : {
1346 : 10 : return OPT_Wanalyzer_stale_setjmp_buffer;
1347 : : }
1348 : :
1349 : 5 : bool emit (diagnostic_emission_context &ctxt) final override
1350 : : {
1351 : 5 : return ctxt.warn ("%qs called after enclosing function of %qs has returned",
1352 : : get_user_facing_name (m_longjmp_call),
1353 : 5 : get_user_facing_name (m_setjmp_call));
1354 : : }
1355 : :
1356 : 25 : const char *get_kind () const final override
1357 : 25 : { return "stale_jmp_buf"; }
1358 : :
1359 : 5 : bool operator== (const stale_jmp_buf &other) const
1360 : : {
1361 : 5 : return (&m_setjmp_call == &other.m_setjmp_call
1362 : 5 : && &m_longjmp_call == &other.m_longjmp_call);
1363 : : }
1364 : :
1365 : : bool
1366 : 51 : maybe_add_custom_events_for_eedge (const exploded_edge &eedge,
1367 : : checker_path *emission_path)
1368 : : final override
1369 : : {
1370 : : /* Detect exactly when the stack first becomes invalid,
1371 : : and issue an event then. */
1372 : 51 : if (m_stack_pop_event)
1373 : : return false;
1374 : 51 : const exploded_node *src_node = eedge.m_src;
1375 : 51 : const program_point &src_point = src_node->get_point ();
1376 : 51 : const exploded_node *dst_node = eedge.m_dest;
1377 : 51 : const program_point &dst_point = dst_node->get_point ();
1378 : 51 : if (valid_longjmp_stack_p (src_point, m_setjmp_point)
1379 : 51 : && !valid_longjmp_stack_p (dst_point, m_setjmp_point))
1380 : : {
1381 : : /* Compare with diagnostic_manager::add_events_for_superedge. */
1382 : 5 : const int src_stack_depth = src_point.get_stack_depth ();
1383 : 10 : m_stack_pop_event = new precanned_custom_event
1384 : 5 : (event_loc_info (src_point.get_location (),
1385 : : src_point.get_fndecl (),
1386 : 10 : src_stack_depth),
1387 : 10 : "stack frame is popped here, invalidating saved environment");
1388 : 5 : emission_path->add_event
1389 : 5 : (std::unique_ptr<custom_event> (m_stack_pop_event));
1390 : 5 : return false;
1391 : : }
1392 : : return false;
1393 : : }
1394 : :
1395 : : bool
1396 : 10 : describe_final_event (pretty_printer &pp,
1397 : : const evdesc::final_event &) final override
1398 : : {
1399 : 10 : if (m_stack_pop_event)
1400 : 10 : pp_printf (&pp,
1401 : : "%qs called after enclosing function of %qs returned at %@",
1402 : : get_user_facing_name (m_longjmp_call),
1403 : : get_user_facing_name (m_setjmp_call),
1404 : : m_stack_pop_event->get_id_ptr ());
1405 : : else
1406 : 0 : pp_printf (&pp,
1407 : : "%qs called after enclosing function of %qs has returned",
1408 : : get_user_facing_name (m_longjmp_call),
1409 : : get_user_facing_name (m_setjmp_call));
1410 : 10 : return true;
1411 : : }
1412 : :
1413 : :
1414 : : private:
1415 : : const gcall &m_setjmp_call;
1416 : : const gcall &m_longjmp_call;
1417 : : program_point m_setjmp_point;
1418 : : custom_event *m_stack_pop_event;
1419 : : };
1420 : :
1421 : : /* Handle LONGJMP_CALL, a call to longjmp or siglongjmp.
1422 : :
1423 : : Attempt to locate where setjmp/sigsetjmp was called on the jmp_buf and build
1424 : : an exploded_node and exploded_edge to it representing a rewind to that frame,
1425 : : handling the various kinds of failure that can occur. */
1426 : :
1427 : : void
1428 : 63 : exploded_node::on_longjmp (exploded_graph &eg,
1429 : : const gcall &longjmp_call,
1430 : : program_state *new_state,
1431 : : region_model_context *ctxt)
1432 : : {
1433 : 63 : tree buf_ptr = gimple_call_arg (&longjmp_call, 0);
1434 : 63 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (buf_ptr)));
1435 : :
1436 : 63 : region_model *new_region_model = new_state->m_region_model;
1437 : 63 : const svalue *buf_ptr_sval = new_region_model->get_rvalue (buf_ptr, ctxt);
1438 : 63 : const region *buf = new_region_model->deref_rvalue (buf_ptr_sval, buf_ptr,
1439 : : ctxt);
1440 : :
1441 : 63 : const svalue *buf_content_sval
1442 : 63 : = new_region_model->get_store_value (buf, ctxt);
1443 : 63 : const setjmp_svalue *setjmp_sval
1444 : 63 : = buf_content_sval->dyn_cast_setjmp_svalue ();
1445 : 63 : if (!setjmp_sval)
1446 : 43 : return;
1447 : :
1448 : 25 : const setjmp_record tmp_setjmp_record = setjmp_sval->get_setjmp_record ();
1449 : :
1450 : : /* Build a custom enode and eedge for rewinding from the longjmp/siglongjmp
1451 : : call back to the setjmp/sigsetjmp. */
1452 : 25 : rewind_info_t rewind_info (tmp_setjmp_record, longjmp_call);
1453 : :
1454 : 25 : const gcall &setjmp_call = rewind_info.get_setjmp_call ();
1455 : 25 : const program_point point_before_setjmp = rewind_info.get_point_before_setjmp ();
1456 : 25 : const program_point point_after_setjmp = rewind_info.get_point_after_setjmp ();
1457 : :
1458 : 25 : const program_point &longjmp_point = get_point ();
1459 : :
1460 : : /* Verify that the setjmp's call_stack hasn't been popped. */
1461 : 25 : if (!valid_longjmp_stack_p (longjmp_point, point_after_setjmp))
1462 : : {
1463 : 5 : ctxt->warn (std::make_unique<stale_jmp_buf> (setjmp_call,
1464 : : longjmp_call,
1465 : : point_before_setjmp));
1466 : 5 : return;
1467 : : }
1468 : :
1469 : 60 : gcc_assert (longjmp_point.get_stack_depth ()
1470 : : >= point_after_setjmp.get_stack_depth ());
1471 : :
1472 : : /* Update the state for use by the destination node. */
1473 : :
1474 : : /* Stash the current number of diagnostics so that we can update
1475 : : any that this adds to show where the longjmp is rewinding to. */
1476 : :
1477 : 20 : diagnostic_manager *dm = &eg.get_diagnostic_manager ();
1478 : 20 : unsigned prev_num_diagnostics = dm->get_num_diagnostics ();
1479 : :
1480 : 40 : new_region_model->on_longjmp (longjmp_call, setjmp_call,
1481 : : point_after_setjmp.get_stack_depth (), ctxt);
1482 : :
1483 : : /* Detect leaks in the new state relative to the old state. */
1484 : 20 : program_state::detect_leaks (get_state (), *new_state, nullptr,
1485 : : eg.get_ext_state (), ctxt);
1486 : 20 : exploded_node *next
1487 : 20 : = eg.get_or_create_node (point_after_setjmp, *new_state, this);
1488 : :
1489 : : /* Create custom exploded_edge for a longjmp. */
1490 : 20 : if (next)
1491 : : {
1492 : 20 : exploded_edge *eedge
1493 : 20 : = eg.add_edge (const_cast<exploded_node *> (this), next, nullptr, true,
1494 : 20 : std::make_unique<rewind_info_t> (tmp_setjmp_record,
1495 : : longjmp_call));
1496 : :
1497 : : /* For any diagnostics that were queued here (such as leaks) we want
1498 : : the checker_path to show the rewinding events after the "final event"
1499 : : so that the user sees where the longjmp is rewinding to (otherwise the
1500 : : path is meaningless).
1501 : :
1502 : : For example, we want to emit something like:
1503 : : | NN | {
1504 : : | NN | longjmp (env, 1);
1505 : : | | ~~~~~~~~~~~~~~~~
1506 : : | | |
1507 : : | | (10) 'ptr' leaks here; was allocated at (7)
1508 : : | | (11) rewinding from 'longjmp' in 'inner'...
1509 : : |
1510 : : <-------------+
1511 : : |
1512 : : 'outer': event 12
1513 : : |
1514 : : | NN | i = setjmp(env);
1515 : : | | ^~~~~~
1516 : : | | |
1517 : : | | (12) ...to 'setjmp' in 'outer' (saved at (2))
1518 : :
1519 : : where the "final" event above is event (10), but we want to append
1520 : : events (11) and (12) afterwards.
1521 : :
1522 : : Do this by setting m_trailing_eedge on any diagnostics that were
1523 : : just saved. */
1524 : 20 : unsigned num_diagnostics = dm->get_num_diagnostics ();
1525 : 28 : for (unsigned i = prev_num_diagnostics; i < num_diagnostics; i++)
1526 : : {
1527 : 8 : saved_diagnostic *sd = dm->get_saved_diagnostic (i);
1528 : 8 : sd->m_trailing_eedge = eedge;
1529 : : }
1530 : : }
1531 : 25 : }
1532 : :
1533 : : /* Subclass of call_info for exploded edges that express
1534 : : a throw or rethrow of an exception (actually a call
1535 : : to __cxa_throw or __cxa_rethrow). */
1536 : :
1537 : : class throw_custom_edge : public call_info
1538 : : {
1539 : : public:
1540 : 187 : throw_custom_edge (const call_details &cd,
1541 : : tree type,
1542 : : bool is_rethrow)
1543 : 187 : : call_info (cd),
1544 : 187 : m_type (type),
1545 : 187 : m_is_rethrow (is_rethrow)
1546 : : {
1547 : : }
1548 : :
1549 : 0 : void print (pretty_printer *pp) const final override
1550 : : {
1551 : 0 : if (m_is_rethrow)
1552 : : {
1553 : 0 : if (m_type)
1554 : 0 : pp_printf (pp, "rethrowing %qT", m_type);
1555 : : else
1556 : 0 : pp_printf (pp, "rethrowing");
1557 : : }
1558 : : else
1559 : : {
1560 : 0 : if (m_type)
1561 : 0 : pp_printf (pp, "throwing %qT", m_type);
1562 : : else
1563 : 0 : pp_printf (pp, "throwing");
1564 : : }
1565 : 0 : }
1566 : :
1567 : 0 : void print_desc (pretty_printer &pp) const final override
1568 : : {
1569 : 0 : print (&pp);
1570 : 0 : }
1571 : :
1572 : 274 : bool update_model (region_model *model,
1573 : : const exploded_edge *,
1574 : : region_model_context *ctxt) const final override
1575 : : {
1576 : 274 : if (m_is_rethrow)
1577 : : {
1578 : 102 : if (auto eh_node = model->get_current_caught_exception ())
1579 : 75 : model->push_thrown_exception (*eh_node);
1580 : : else
1581 : : {
1582 : : /* We have a rethrow of some unknown exception.
1583 : : We don't have a good way of representing this;
1584 : : leave the exception stack empty. */
1585 : : }
1586 : : }
1587 : : else
1588 : : {
1589 : 172 : call_details cd (get_call_details (model, ctxt));
1590 : :
1591 : 172 : const svalue *exception_sval = cd.get_arg_svalue (0);
1592 : 172 : const svalue *tinfo_sval = cd.get_arg_svalue (1);
1593 : 172 : const svalue *destructor_sval = cd.get_arg_svalue (2);
1594 : :
1595 : : /* Push a new exception_node on the model's m_exception_stack. */
1596 : 172 : exception_node eh_node (exception_sval, tinfo_sval, destructor_sval);
1597 : 172 : model->push_thrown_exception (eh_node);
1598 : : }
1599 : :
1600 : 274 : return true;
1601 : : }
1602 : :
1603 : 69 : void add_events_to_path (checker_path *emission_path,
1604 : : const exploded_edge &eedge,
1605 : : pending_diagnostic &) const final override
1606 : : {
1607 : 69 : const exploded_node *dst_node = eedge.m_dest;
1608 : 69 : const program_point &dst_point = dst_node->get_point ();
1609 : 69 : const int dst_stack_depth = dst_point.get_stack_depth ();
1610 : :
1611 : 69 : const gcall &call = get_call_stmt ();
1612 : :
1613 : 69 : emission_path->add_event
1614 : 69 : (std::make_unique<explicit_throw_event>
1615 : 69 : (event_loc_info (call.location,
1616 : : dst_point.get_fndecl (),
1617 : 69 : dst_stack_depth),
1618 : : dst_node,
1619 : : call,
1620 : 69 : m_type,
1621 : 69 : m_is_rethrow));
1622 : 69 : }
1623 : :
1624 : : private:
1625 : : tree m_type;
1626 : : bool m_is_rethrow;
1627 : : };
1628 : :
1629 : : /* Subclass of custom_edge_info for an exploded edge that expresses
1630 : : unwinding one stack frame during exception handling. */
1631 : :
1632 : : class unwind_custom_edge : public custom_edge_info
1633 : : {
1634 : : public:
1635 : 6407 : unwind_custom_edge (location_t loc)
1636 : 6407 : : m_loc (loc)
1637 : : {
1638 : : }
1639 : :
1640 : 0 : void print (pretty_printer *pp) const final override
1641 : : {
1642 : 0 : pp_printf (pp, "unwinding frame");
1643 : 0 : }
1644 : :
1645 : 6423 : bool update_model (region_model *model,
1646 : : const exploded_edge *,
1647 : : region_model_context *ctxt) const final override
1648 : : {
1649 : 6423 : model->pop_frame (NULL_TREE, nullptr, ctxt, nullptr, false);
1650 : 6423 : return true;
1651 : : }
1652 : :
1653 : 16 : void add_events_to_path (checker_path *emission_path,
1654 : : const exploded_edge &eedge,
1655 : : pending_diagnostic &) const final override
1656 : : {
1657 : 16 : const exploded_node *src_node = eedge.m_src;
1658 : 16 : const program_point &src_point = src_node->get_point ();
1659 : 16 : const int src_stack_depth = src_point.get_stack_depth ();
1660 : 16 : emission_path->add_event
1661 : 32 : (std::make_unique<unwind_event> (event_loc_info (m_loc,
1662 : : src_point.get_fndecl (),
1663 : 16 : src_stack_depth)));
1664 : 16 : }
1665 : :
1666 : : private:
1667 : : location_t m_loc;
1668 : : };
1669 : :
1670 : : /* Locate an SNODE that's a CFG edge with the EH flag,
1671 : : or return nullptr. */
1672 : :
1673 : : static const superedge *
1674 : 7143 : get_eh_outedge (const supernode &snode)
1675 : : {
1676 : 26267 : for (auto out_sedge : snode.m_succs)
1677 : 6646 : if (::edge cfg_edge = out_sedge->get_any_cfg_edge ())
1678 : 1153 : if (cfg_edge->flags & EDGE_EH)
1679 : : return out_sedge;
1680 : :
1681 : : // Not found
1682 : : return nullptr;
1683 : : }
1684 : :
1685 : : /* Given THROWN_ENODE, which expreses a throw or rethrow occurring at
1686 : : THROW_STMT, unwind intraprocedurally and interprocedurally to find
1687 : : the next eh_dispatch statement to handle exceptions, if any.
1688 : :
1689 : : Add eedges and enodes to this graph expressing the actions taken
1690 : : to reach an enode containing the eh_dispatch stmt, if any.
1691 : : Only the final enode is added to this graph's worklist.
1692 : :
1693 : : Use CTXT to warn about problems e.g. memory leaks due to stack frames
1694 : : being unwound. */
1695 : :
1696 : : void
1697 : 5969 : exploded_graph::unwind_from_exception (exploded_node &thrown_enode,
1698 : : const gimple *throw_stmt,
1699 : : region_model_context *ctxt)
1700 : : {
1701 : 5969 : logger * const logger = get_logger ();
1702 : 5969 : LOG_FUNC_1 (logger, "thrown EN: %i", thrown_enode.m_index);
1703 : :
1704 : : /* Iteratively unwind the stack looking for an out-cfg-edge
1705 : : flagged EH. */
1706 : 5969 : exploded_node *iter_enode = &thrown_enode;
1707 : 5969 : while (iter_enode)
1708 : : {
1709 : : /* If we have an out-cfg-edge flagged EH, follow that,
1710 : : presumably to a bb with a label and an eh_dispatch stmt.
1711 : : Otherwise assume no out-cfgs-edges, and we are unwinding to the
1712 : : caller. */
1713 : 7143 : if (auto sedge = get_eh_outedge (*iter_enode->get_supernode ()))
1714 : : {
1715 : : /* Intraprocedural case.
1716 : : Assume we have an out-edge flagged with EH leading to
1717 : : code for dispatch to catch handlers. */
1718 : 736 : const program_point next_point
1719 : 736 : (sedge->m_dest,
1720 : 736 : iter_enode->get_point ().get_call_string ());
1721 : 736 : exploded_node *next_enode
1722 : 736 : = get_or_create_node (next_point,
1723 : : iter_enode->get_state (),
1724 : : iter_enode,
1725 : : /* Add this enode to the worklist. */
1726 : : true);
1727 : 736 : if (!next_enode)
1728 : : return;
1729 : :
1730 : 736 : add_edge (iter_enode, next_enode, nullptr, false, nullptr);
1731 : 736 : return;
1732 : : }
1733 : : else
1734 : : {
1735 : : /* Interprocedural case.
1736 : : No out-cfg-edge. Unwind one stack frame. */
1737 : 6407 : program_state unwound_state (iter_enode->get_state ());
1738 : 6407 : location_t loc = throw_stmt ? throw_stmt->location : UNKNOWN_LOCATION;
1739 : 6407 : auto unwind_edge_info
1740 : 6407 : = std::make_unique<unwind_custom_edge> (loc);
1741 : 6407 : unwind_edge_info->update_model (unwound_state.m_region_model, nullptr,
1742 : : ctxt);
1743 : :
1744 : : /* Detect leaks in the new state relative to the old state.
1745 : : Use an alternate ctxt that uses the original enode and the stmt
1746 : : (if any) for the location of any diagnostics. */
1747 : 6407 : {
1748 : 6407 : uncertainty_t uncertainty;
1749 : 6407 : impl_region_model_context ctxt (*this,
1750 : : &thrown_enode,
1751 : 6407 : &iter_enode->get_state (),
1752 : : &unwound_state,
1753 : : &uncertainty,
1754 : : nullptr,
1755 : 6407 : throw_stmt);
1756 : 6407 : program_state::detect_leaks (iter_enode->get_state (),
1757 : : unwound_state,
1758 : : nullptr,
1759 : : get_ext_state (), &ctxt);
1760 : 6407 : }
1761 : 6407 : const call_string &cs = iter_enode->get_point ().get_call_string ();
1762 : 6407 : if (cs.empty_p ())
1763 : : {
1764 : : /* Top-level stack frame in analysis: unwinding
1765 : : to the outside world that called us. */
1766 : : return;
1767 : : }
1768 : : else
1769 : : {
1770 : : /* Nested function in analysis: unwinding to
1771 : : the callsite in the analysis (or beyond). */
1772 : 1593 : program_point unwound_point (cs.get_return_node_in_caller (), cs);
1773 : 1593 : unwound_point.pop_from_call_stack ();
1774 : :
1775 : 1593 : exploded_node *after_unwind_enode
1776 : 1593 : = get_or_create_node (unwound_point,
1777 : : std::move (unwound_state),
1778 : : iter_enode,
1779 : : /* Don't add this enode to the
1780 : : worklist; we will process it
1781 : : on the next iteration. */
1782 : : false);
1783 : :
1784 : 1593 : if (!after_unwind_enode)
1785 : 419 : return;
1786 : :
1787 : 1174 : add_edge (iter_enode, after_unwind_enode, nullptr, true,
1788 : 1174 : std::move (unwind_edge_info));
1789 : 1174 : iter_enode = after_unwind_enode;
1790 : : }
1791 : 6407 : }
1792 : : }
1793 : 5969 : }
1794 : :
1795 : : /* Handle THROW_CALL, a call to __cxa_throw or __cxa_rethrow.
1796 : :
1797 : : Create an eedge and destination enode for the throw/rethrow, adding
1798 : : them to this egraph. The new enode isn't added to the worklist, but
1799 : : instead exploded_graph::unwind_from_exception is immediately called
1800 : : on it, potentially creating more eedges and enodes leading to an
1801 : : eh_handler stmt. */
1802 : :
1803 : : void
1804 : 187 : exploded_node::on_throw (exploded_graph &eg,
1805 : : const gcall &throw_call,
1806 : : const program_point &after_throw_point,
1807 : : program_state *new_state,
1808 : : bool is_rethrow,
1809 : : region_model_context *ctxt)
1810 : : {
1811 : 187 : region_model *model = new_state->m_region_model;
1812 : 187 : call_details cd (throw_call, model, ctxt);
1813 : :
1814 : : /* Create an enode and eedge for the "throw". */
1815 : 187 : tree type = NULL_TREE;
1816 : 187 : if (is_rethrow)
1817 : : {
1818 : 81 : const exception_node *eh_node = model->get_current_caught_exception ();
1819 : 66 : if (eh_node)
1820 : 66 : type = eh_node->maybe_get_type ();
1821 : : else
1822 : : {
1823 : : /* We have a "throw;" but no exception to rethrow.
1824 : : Presumably the top-level of the analysis is an
1825 : : entrypoint for handling exceptions, so we will
1826 : : simulate fully unwinding. */
1827 : : }
1828 : : }
1829 : : else
1830 : : {
1831 : 106 : const svalue *tinfo_sval = cd.get_arg_svalue (1);
1832 : 106 : type = tinfo_sval->maybe_get_type_from_typeinfo ();
1833 : : }
1834 : :
1835 : 187 : auto throw_edge_info
1836 : 187 : = std::make_unique<throw_custom_edge> (cd, type, is_rethrow);
1837 : 187 : throw_edge_info->update_model (model, nullptr, ctxt);
1838 : :
1839 : 187 : exploded_node *after_throw_enode
1840 : 187 : = eg.get_or_create_node (after_throw_point, *new_state, this,
1841 : : /* Don't add to worklist; we process
1842 : : this immediately below. */
1843 : : false);
1844 : :
1845 : 187 : if (!after_throw_enode)
1846 : 0 : return;
1847 : :
1848 : : /* Create custom exploded_edge for a throw. */
1849 : 187 : eg.add_edge (this, after_throw_enode, nullptr, true,
1850 : 187 : std::move (throw_edge_info));
1851 : :
1852 : 187 : eg.unwind_from_exception (*after_throw_enode, &throw_call, ctxt);
1853 : 187 : }
1854 : :
1855 : : /* Subroutine of exploded_graph::process_node for finding the successors
1856 : : of the supernode for a function exit basic block.
1857 : :
1858 : : Ensure that pop_frame is called, potentially queuing diagnostics about
1859 : : leaks. */
1860 : :
1861 : : void
1862 : 11202 : exploded_node::detect_leaks (exploded_graph &eg)
1863 : : {
1864 : 11202 : LOG_FUNC_1 (eg.get_logger (), "EN: %i", m_index);
1865 : :
1866 : 11202 : gcc_assert (get_point ().get_supernode ()->exit_p ());
1867 : :
1868 : : /* If we're not a "top-level" function, do nothing; pop_frame
1869 : : will be called when handling the return superedge. */
1870 : 11202 : if (get_point ().get_stack_depth () > 1)
1871 : 0 : return;
1872 : :
1873 : : /* We have a "top-level" function. */
1874 : 11202 : gcc_assert (get_point ().get_stack_depth () == 1);
1875 : :
1876 : 11202 : const program_state &old_state = get_state ();
1877 : :
1878 : : /* Work with a temporary copy of the state: pop the frame, and see
1879 : : what leaks (via purge_unused_svalues). */
1880 : 11202 : program_state new_state (old_state);
1881 : :
1882 : 11202 : gcc_assert (new_state.m_region_model);
1883 : :
1884 : 11202 : uncertainty_t uncertainty;
1885 : 11202 : impl_region_model_context ctxt (eg, this,
1886 : : &old_state, &new_state, &uncertainty, nullptr,
1887 : 11202 : nullptr);
1888 : 11202 : const svalue *result = nullptr;
1889 : 11202 : new_state.m_region_model->pop_frame (nullptr, &result, &ctxt, nullptr);
1890 : 11202 : program_state::detect_leaks (old_state, new_state, result,
1891 : : eg.get_ext_state (), &ctxt);
1892 : 22404 : }
1893 : :
1894 : : /* Dump the successors and predecessors of this enode to OUTF. */
1895 : :
1896 : : void
1897 : 0 : exploded_node::dump_succs_and_preds (FILE *outf) const
1898 : : {
1899 : 0 : unsigned i;
1900 : 0 : exploded_edge *e;
1901 : 0 : {
1902 : 0 : auto_vec<exploded_node *> preds (m_preds.length ());
1903 : 0 : FOR_EACH_VEC_ELT (m_preds, i, e)
1904 : 0 : preds.quick_push (e->m_src);
1905 : 0 : pretty_printer pp;
1906 : 0 : print_enode_indices (&pp, preds);
1907 : 0 : fprintf (outf, "preds: %s\n",
1908 : : pp_formatted_text (&pp));
1909 : 0 : }
1910 : 0 : {
1911 : 0 : auto_vec<exploded_node *> succs (m_succs.length ());
1912 : 0 : FOR_EACH_VEC_ELT (m_succs, i, e)
1913 : 0 : succs.quick_push (e->m_dest);
1914 : 0 : pretty_printer pp;
1915 : 0 : print_enode_indices (&pp, succs);
1916 : 0 : fprintf (outf, "succs: %s\n",
1917 : : pp_formatted_text (&pp));
1918 : 0 : }
1919 : 0 : }
1920 : :
1921 : : // class interprocedural_call : public custom_edge_info
1922 : :
1923 : : void
1924 : 8 : interprocedural_call::print (pretty_printer *pp) const
1925 : : {
1926 : 8 : pp_string (pp, "call to ");
1927 : 8 : pp_gimple_stmt_1 (pp, &m_call_stmt, 0, (dump_flags_t)0);
1928 : 8 : }
1929 : :
1930 : : void
1931 : 8 : interprocedural_call::get_dot_attrs (const char *&/*out_style*/,
1932 : : const char *&out_color) const
1933 : : {
1934 : 8 : out_color = "red";
1935 : 8 : }
1936 : :
1937 : : bool
1938 : 6773 : interprocedural_call::update_state (program_state *state,
1939 : : const exploded_edge *eedge,
1940 : : region_model_context *ctxt) const
1941 : : {
1942 : 6773 : return update_model (state->m_region_model, eedge, ctxt);
1943 : : }
1944 : :
1945 : : bool
1946 : 11380 : interprocedural_call::update_model (region_model *model,
1947 : : const exploded_edge */*eedge*/,
1948 : : region_model_context *ctxt) const
1949 : : {
1950 : 11380 : model->update_for_gcall (m_call_stmt, ctxt, &m_callee_fun);
1951 : 11380 : return true;
1952 : : }
1953 : :
1954 : : void
1955 : 1221 : interprocedural_call::add_events_to_path (checker_path *emission_path,
1956 : : const exploded_edge &eedge,
1957 : : pending_diagnostic &pd) const
1958 : : {
1959 : 1221 : pd.add_call_event (eedge, m_call_stmt, *emission_path);
1960 : 1221 : }
1961 : :
1962 : : // class interprocedural_return : public custom_edge_info
1963 : :
1964 : : void
1965 : 16 : interprocedural_return::print (pretty_printer *pp) const
1966 : : {
1967 : 16 : pp_string (pp, "return from ");
1968 : 16 : pp_gimple_stmt_1 (pp, &m_call_stmt, 0, (dump_flags_t)0);
1969 : 16 : }
1970 : :
1971 : : void
1972 : 8 : interprocedural_return::get_dot_attrs (const char *&/*out_style*/,
1973 : : const char *&out_color) const
1974 : : {
1975 : 8 : out_color = "green";
1976 : 8 : }
1977 : :
1978 : : bool
1979 : 5770 : interprocedural_return::update_state (program_state *state,
1980 : : const exploded_edge *eedge,
1981 : : region_model_context *ctxt) const
1982 : : {
1983 : 5770 : return update_model (state->m_region_model, eedge, ctxt);
1984 : : }
1985 : :
1986 : : bool
1987 : 8332 : interprocedural_return::update_model (region_model *model,
1988 : : const exploded_edge */*eedge*/,
1989 : : region_model_context *ctxt) const
1990 : : {
1991 : 8332 : model->update_for_return_gcall (m_call_stmt, ctxt);
1992 : 8332 : return true;
1993 : : }
1994 : :
1995 : : void
1996 : 629 : interprocedural_return::add_events_to_path (checker_path *emission_path,
1997 : : const exploded_edge &eedge,
1998 : : pending_diagnostic &) const
1999 : : {
2000 : 629 : const program_point &dst_point = eedge.m_dest->get_point ();
2001 : 629 : emission_path->add_event
2002 : 1258 : (std::make_unique<return_event>
2003 : 629 : (eedge,
2004 : 1258 : event_loc_info (m_call_stmt.location,
2005 : : dst_point.get_fndecl (),
2006 : 1258 : dst_point.get_stack_depth ())));
2007 : 629 : }
2008 : :
2009 : : /* class rewind_info_t : public custom_edge_info. */
2010 : :
2011 : : /* Implementation of custom_edge_info::update_model vfunc
2012 : : for rewind_info_t.
2013 : :
2014 : : Update state for the special-case of a rewind of a longjmp
2015 : : to a setjmp (which doesn't have a superedge, but does affect
2016 : : state). */
2017 : :
2018 : : bool
2019 : 11 : rewind_info_t::update_model (region_model *model,
2020 : : const exploded_edge *eedge,
2021 : : region_model_context *) const
2022 : : {
2023 : 11 : gcc_assert (eedge);
2024 : 11 : const program_point &longjmp_point = eedge->m_src->get_point ();
2025 : 11 : const program_point &setjmp_point = eedge->m_dest->get_point ();
2026 : :
2027 : 33 : gcc_assert (longjmp_point.get_stack_depth ()
2028 : : >= setjmp_point.get_stack_depth ());
2029 : :
2030 : 22 : model->on_longjmp (get_longjmp_call (),
2031 : : get_setjmp_call (),
2032 : : setjmp_point.get_stack_depth (), nullptr);
2033 : 11 : return true;
2034 : : }
2035 : :
2036 : : /* Implementation of custom_edge_info::add_events_to_path vfunc
2037 : : for rewind_info_t. */
2038 : :
2039 : : void
2040 : 15 : rewind_info_t::add_events_to_path (checker_path *emission_path,
2041 : : const exploded_edge &eedge,
2042 : : pending_diagnostic &) const
2043 : : {
2044 : 15 : const exploded_node *src_node = eedge.m_src;
2045 : 15 : const program_point &src_point = src_node->get_point ();
2046 : 15 : const int src_stack_depth = src_point.get_stack_depth ();
2047 : 15 : const exploded_node *dst_node = eedge.m_dest;
2048 : 15 : const program_point &dst_point = dst_node->get_point ();
2049 : 15 : const int dst_stack_depth = dst_point.get_stack_depth ();
2050 : :
2051 : 15 : emission_path->add_event
2052 : 15 : (std::make_unique<rewind_from_longjmp_event>
2053 : 15 : (&eedge,
2054 : 15 : event_loc_info (get_longjmp_call ().location,
2055 : : src_point.get_fndecl (),
2056 : 15 : src_stack_depth),
2057 : 15 : this));
2058 : 15 : emission_path->add_event
2059 : 15 : (std::make_unique<rewind_to_setjmp_event>
2060 : 15 : (&eedge,
2061 : 15 : event_loc_info (get_setjmp_call ().location,
2062 : : dst_point.get_fndecl (),
2063 : 15 : dst_stack_depth),
2064 : 15 : this));
2065 : 15 : }
2066 : :
2067 : : /* class exploded_edge : public dedge<eg_traits>. */
2068 : :
2069 : : /* exploded_edge's ctor. */
2070 : :
2071 : 402172 : exploded_edge::exploded_edge (exploded_node *src, exploded_node *dest,
2072 : : const superedge *sedge, bool could_do_work,
2073 : 402172 : std::unique_ptr<custom_edge_info> custom_info)
2074 : 402172 : : dedge<eg_traits> (src, dest), m_sedge (sedge),
2075 : 402172 : m_custom_info (std::move (custom_info)),
2076 : 402172 : m_could_do_work_p (could_do_work)
2077 : : {
2078 : 402172 : }
2079 : :
2080 : : /* Implementation of dedge::dump_dot vfunc for exploded_edge.
2081 : : Use the label of the underlying superedge, if any. */
2082 : :
2083 : : void
2084 : 515 : exploded_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
2085 : : {
2086 : 515 : pretty_printer *pp = gv->get_pp ();
2087 : :
2088 : 515 : m_src->dump_dot_id (pp);
2089 : 515 : pp_string (pp, " -> ");
2090 : 515 : m_dest->dump_dot_id (pp);
2091 : 515 : dump_dot_label (pp);
2092 : 515 : }
2093 : :
2094 : : /* Second half of exploded_edge::dump_dot. This is split out
2095 : : for use by trimmed_graph::dump_dot and base_feasible_edge::dump_dot. */
2096 : :
2097 : : void
2098 : 585 : exploded_edge::dump_dot_label (pretty_printer *pp) const
2099 : : {
2100 : 585 : const char *style = "\"solid,bold\"";
2101 : 585 : const char *color = "black";
2102 : 585 : int weight = 10;
2103 : 585 : const char *constraint = "true";
2104 : :
2105 : 585 : if (m_sedge)
2106 : : {
2107 : 539 : if (m_sedge->get_op ())
2108 : 426 : style = "\"solid\"";
2109 : : else
2110 : 113 : style = "\"dotted\"";
2111 : : }
2112 : 585 : if (m_custom_info)
2113 : 22 : m_custom_info->get_dot_attrs (style, color);
2114 : :
2115 : 585 : pp_printf (pp,
2116 : : (" [style=%s, color=%s, weight=%d, constraint=%s,"
2117 : : " headlabel=\""),
2118 : : style, color, weight, constraint);
2119 : 585 : pp_flush (pp);
2120 : :
2121 : 585 : if (m_sedge)
2122 : 539 : m_sedge->dump_label_to_pp (pp, false);
2123 : 46 : else if (m_custom_info)
2124 : 14 : m_custom_info->print (pp);
2125 : :
2126 : 1132 : pp_printf (pp, "%s",
2127 : 585 : could_do_work_p () ? "(could do work)" : "DOES NO WORK");
2128 : :
2129 : 585 : pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
2130 : :
2131 : 585 : pp_printf (pp, "\"];\n");
2132 : 585 : }
2133 : :
2134 : : /* Return a new json::object of the form
2135 : : {"src_idx": int, the index of the source exploded edge,
2136 : : "dst_idx": int, the index of the destination exploded edge,
2137 : : "sedge": (optional) object for the superedge, if any,
2138 : : "custom": (optional) str, a description, if this is a custom edge}. */
2139 : :
2140 : : std::unique_ptr<json::object>
2141 : 0 : exploded_edge::to_json () const
2142 : : {
2143 : 0 : auto eedge_obj = std::make_unique<json::object> ();
2144 : 0 : eedge_obj->set_integer ("src_idx", m_src->m_index);
2145 : 0 : eedge_obj->set_integer ("dst_idx", m_dest->m_index);
2146 : 0 : if (m_sedge)
2147 : 0 : eedge_obj->set ("sedge", m_sedge->to_json ());
2148 : 0 : if (m_custom_info)
2149 : : {
2150 : 0 : pretty_printer pp;
2151 : 0 : pp_format_decoder (&pp) = default_tree_printer;
2152 : 0 : m_custom_info->print (&pp);
2153 : 0 : eedge_obj->set_string ("custom", pp_formatted_text (&pp));
2154 : 0 : }
2155 : 0 : return eedge_obj;
2156 : : }
2157 : :
2158 : : const gimple *
2159 : 22987 : exploded_edge::maybe_get_stmt () const
2160 : : {
2161 : 22987 : auto op = maybe_get_op ();
2162 : 22987 : if (!op)
2163 : : return nullptr;
2164 : 18275 : return op->maybe_get_stmt ();
2165 : : }
2166 : :
2167 : : const operation *
2168 : 27277 : exploded_edge::maybe_get_op () const
2169 : : {
2170 : 27277 : if (!m_sedge)
2171 : : return nullptr;
2172 : 26065 : return m_sedge->get_op ();
2173 : : }
2174 : :
2175 : : /* struct stats. */
2176 : :
2177 : : /* stats' ctor. */
2178 : :
2179 : 25180 : stats::stats (int num_supernodes)
2180 : 25180 : : m_num_nodes (0),
2181 : 25180 : m_node_reuse_count (0),
2182 : 25180 : m_node_reuse_after_merge_count (0),
2183 : 25180 : m_num_supernodes (num_supernodes)
2184 : : {
2185 : 25180 : }
2186 : :
2187 : : /* Log these stats in multiline form to LOGGER. */
2188 : :
2189 : : void
2190 : 4 : stats::log (logger *logger) const
2191 : : {
2192 : 4 : gcc_assert (logger);
2193 : 4 : logger->log ("m_num_nodes: %i", m_num_nodes);
2194 : 4 : logger->log ("m_node_reuse_count: %i", m_node_reuse_count);
2195 : 4 : logger->log ("m_node_reuse_after_merge_count: %i",
2196 : 4 : m_node_reuse_after_merge_count);
2197 : 4 : }
2198 : :
2199 : : /* Dump these stats in multiline form to OUT. */
2200 : :
2201 : : void
2202 : 0 : stats::dump (FILE *out) const
2203 : : {
2204 : 0 : fprintf (out, "m_num_nodes: %i\n", m_num_nodes);
2205 : 0 : fprintf (out, "m_node_reuse_count: %i\n", m_node_reuse_count);
2206 : 0 : fprintf (out, "m_node_reuse_after_merge_count: %i\n",
2207 : 0 : m_node_reuse_after_merge_count);
2208 : :
2209 : 0 : if (m_num_supernodes > 0)
2210 : 0 : fprintf (out, "enodes per supernode: %.2f\n",
2211 : 0 : (float)m_num_nodes / (float)m_num_supernodes);
2212 : 0 : }
2213 : :
2214 : : /* Return the total number of enodes recorded within this object. */
2215 : :
2216 : : int
2217 : 2 : stats::get_total_enodes () const
2218 : : {
2219 : 2 : return m_num_nodes;
2220 : : }
2221 : :
2222 : : /* struct per_function_data. */
2223 : :
2224 : 367 : per_function_data::~per_function_data ()
2225 : : {
2226 : 1734 : for (auto iter : m_summaries)
2227 : 633 : delete iter;
2228 : 367 : }
2229 : :
2230 : : void
2231 : 633 : per_function_data::add_call_summary (exploded_node *node)
2232 : : {
2233 : 633 : m_summaries.safe_push (new call_summary (this, node));
2234 : 633 : }
2235 : :
2236 : : /* strongly_connected_components's ctor. Tarjan's SCC algorithm. */
2237 : :
2238 : 3324 : strongly_connected_components::
2239 : 3324 : strongly_connected_components (const supergraph &sg, logger *logger)
2240 : 6644 : : m_sg (sg), m_per_node (m_sg.m_nodes.length ())
2241 : : {
2242 : 3324 : LOG_SCOPE (logger);
2243 : 3324 : auto_timevar tv (TV_ANALYZER_SCC);
2244 : :
2245 : 184586 : for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
2246 : 181262 : m_per_node.quick_push (per_node_data ());
2247 : :
2248 : 191226 : for (auto snode : m_sg.m_nodes)
2249 : 181262 : if (m_per_node[snode->m_id].m_id == -1)
2250 : 10132 : strong_connect (snode->m_id, logger);
2251 : :
2252 : 3324 : if (0)
2253 : : dump ();
2254 : 3324 : }
2255 : :
2256 : : /* Dump this object to stderr. */
2257 : :
2258 : : DEBUG_FUNCTION void
2259 : 0 : strongly_connected_components::dump () const
2260 : : {
2261 : 0 : fprintf (stderr, "Stack: [");
2262 : 0 : bool first = true;
2263 : 0 : for (auto i : m_stack)
2264 : : {
2265 : 0 : if (first)
2266 : : first = false;
2267 : : else
2268 : 0 : fprintf (stderr, ", ");
2269 : 0 : fprintf (stderr, "%i", i);
2270 : : }
2271 : 0 : fprintf (stderr, "]\n");
2272 : 0 : for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
2273 : : {
2274 : 0 : const per_node_data &v = m_per_node[i];
2275 : 0 : fprintf (stderr, "SN %lu: index: %i lowlink: %i on_stack: %i\n",
2276 : 0 : i, v.m_id, v.m_lowlink, v.m_on_stack);
2277 : : }
2278 : 0 : }
2279 : :
2280 : : /* Return a new json::array of per-snode SCC ids. */
2281 : :
2282 : : std::unique_ptr<json::array>
2283 : 0 : strongly_connected_components::to_json () const
2284 : : {
2285 : 0 : auto scc_arr = std::make_unique<json::array> ();
2286 : 0 : for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
2287 : 0 : scc_arr->append (std::make_unique<json::integer_number> (get_scc_id (i)));
2288 : 0 : return scc_arr;
2289 : : }
2290 : :
2291 : : /* Subroutine of strongly_connected_components's ctor, part of Tarjan's
2292 : : SCC algorithm. */
2293 : :
2294 : : void
2295 : 181262 : strongly_connected_components::strong_connect (unsigned id,
2296 : : logger *logger)
2297 : : {
2298 : 181262 : supernode *v_snode = m_sg.m_nodes[id];
2299 : 181262 : if (!v_snode)
2300 : 181262 : return;
2301 : :
2302 : : /* Set the depth index for v to the smallest unused index. */
2303 : 181262 : per_node_data *v = &m_per_node[id];
2304 : 181262 : v->m_id = id;
2305 : 181262 : v->m_lowlink = id;
2306 : 181262 : m_stack.safe_push (id);
2307 : 181262 : v->m_on_stack = true;
2308 : 181262 : id++;
2309 : :
2310 : : /* Consider successors of v. */
2311 : 181262 : unsigned i;
2312 : 181262 : superedge *sedge;
2313 : 362376 : FOR_EACH_VEC_ELT (v_snode->m_succs, i, sedge)
2314 : : {
2315 : 181114 : supernode *w_snode = sedge->m_dest;
2316 : 181114 : per_node_data *w = &m_per_node[w_snode->m_id];
2317 : 181114 : if (w->m_id == -1)
2318 : : {
2319 : : /* Successor w has not yet been visited; recurse on it. */
2320 : 171130 : strong_connect (w_snode->m_id, logger);
2321 : 171130 : v->m_lowlink = MIN (v->m_lowlink, w->m_lowlink);
2322 : : }
2323 : 9984 : else if (w->m_on_stack)
2324 : : {
2325 : : /* Successor w is in stack S and hence in the current SCC
2326 : : If w is not on stack, then (v, w) is a cross-edge in the DFS
2327 : : tree and must be ignored. */
2328 : 2128 : v->m_lowlink = MIN (v->m_lowlink, w->m_id);
2329 : : }
2330 : : }
2331 : :
2332 : : /* If v is a root node, pop the stack and generate an SCC. */
2333 : :
2334 : 181262 : if (v->m_lowlink == v->m_id)
2335 : : {
2336 : 165210 : if (logger)
2337 : 8 : logger->log ("got SCC root node: SN %i", v->m_id);
2338 : 181262 : per_node_data *w;
2339 : 181262 : do {
2340 : 181262 : int id = m_stack.pop ();
2341 : 181262 : w = &m_per_node[id];
2342 : 181262 : w->m_on_stack = false;
2343 : 181262 : if (logger)
2344 : 36 : logger->log (" popping SN %i", w->m_id);
2345 : 181262 : } while (w != v);
2346 : : }
2347 : : }
2348 : :
2349 : : /* worklist's ctor. */
2350 : :
2351 : 3324 : worklist::worklist (const exploded_graph &eg, const analysis_plan &plan)
2352 : 3324 : : m_scc (eg.get_supergraph (), eg.get_logger ()),
2353 : 3324 : m_plan (plan),
2354 : 3324 : m_queue (key_t (*this, nullptr))
2355 : : {
2356 : 3324 : }
2357 : :
2358 : : /* Return the number of nodes in the worklist. */
2359 : :
2360 : : unsigned
2361 : 363568 : worklist::length () const
2362 : : {
2363 : 363568 : return m_queue.nodes ();
2364 : : }
2365 : :
2366 : : /* Return the next node in the worklist, removing it. */
2367 : :
2368 : : exploded_node *
2369 : 380067 : worklist::take_next ()
2370 : : {
2371 : 380067 : return m_queue.extract_min ();
2372 : : }
2373 : :
2374 : : /* Return the next node in the worklist without removing it. */
2375 : :
2376 : : exploded_node *
2377 : 401040 : worklist::peek_next ()
2378 : : {
2379 : 401040 : return m_queue.min ();
2380 : : }
2381 : :
2382 : : /* Add ENODE to the worklist. */
2383 : :
2384 : : void
2385 : 381108 : worklist::add_node (exploded_node *enode)
2386 : : {
2387 : 381108 : gcc_assert (enode->get_status () == exploded_node::status::worklist);
2388 : 381108 : m_queue.insert (key_t (*this, enode), enode);
2389 : 381108 : }
2390 : :
2391 : : /* Comparator for implementing worklist::key_t comparison operators.
2392 : : Return negative if KA is before KB
2393 : : Return positive if KA is after KB
2394 : : Return 0 if they are equal.
2395 : :
2396 : : The ordering of the worklist is critical for performance and for
2397 : : avoiding node explosions. Ideally we want all enodes at a CFG join-point
2398 : : with the same callstring to be sorted next to each other in the worklist
2399 : : so that a run of consecutive enodes can be merged and processed "in bulk"
2400 : : rather than individually or pairwise, minimizing the number of new enodes
2401 : : created. */
2402 : :
2403 : : int
2404 : 1895215 : worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb)
2405 : : {
2406 : 1895215 : const program_point &point_a = ka.m_enode->get_point ();
2407 : 1895215 : const program_point &point_b = kb.m_enode->get_point ();
2408 : 1895215 : const call_string &call_string_a = point_a.get_call_string ();
2409 : 1895215 : const call_string &call_string_b = point_b.get_call_string ();
2410 : :
2411 : : /* Order empty-callstring points with different functions based on the
2412 : : analysis_plan, so that we generate summaries before they are used. */
2413 : 1895215 : if (flag_analyzer_call_summaries
2414 : 199910 : && call_string_a.empty_p ()
2415 : 176072 : && call_string_b.empty_p ()
2416 : 176072 : && point_a.get_function () != nullptr
2417 : 2020800 : && point_b.get_function () != nullptr
2418 : 2070907 : && point_a.get_function () != point_b.get_function ())
2419 : : {
2420 : 50107 : if (int cmp = ka.m_worklist.m_plan.cmp_function (point_a.get_function (),
2421 : : point_b.get_function ()))
2422 : : return cmp;
2423 : : }
2424 : :
2425 : : /* Sort by callstring, so that nodes with deeper call strings are processed
2426 : : before those with shallower call strings.
2427 : : If we have
2428 : : splitting BB
2429 : : / \
2430 : : / \
2431 : : fn call no fn call
2432 : : \ /
2433 : : \ /
2434 : : join BB
2435 : : then we want the path inside the function call to be fully explored up
2436 : : to the return to the join BB before we explore on the "no fn call" path,
2437 : : so that both enodes at the join BB reach the front of the worklist at
2438 : : the same time and thus have a chance of being merged. */
2439 : 1845108 : int cs_cmp = call_string::cmp (call_string_a, call_string_b);
2440 : 1845108 : if (cs_cmp)
2441 : : return cs_cmp;
2442 : :
2443 : : /* Order by SCC. */
2444 : 1663566 : int scc_id_a = ka.get_scc_id (ka.m_enode);
2445 : 1663566 : int scc_id_b = kb.get_scc_id (kb.m_enode);
2446 : 1663566 : if (scc_id_a != scc_id_b)
2447 : 1272644 : return scc_id_a - scc_id_b;
2448 : :
2449 : : /* If in same SCC, order by supernode index (an arbitrary but stable
2450 : : ordering). */
2451 : 390922 : const supernode *snode_a = ka.m_enode->get_supernode ();
2452 : 390922 : const supernode *snode_b = kb.m_enode->get_supernode ();
2453 : 390922 : if (snode_a == nullptr)
2454 : : {
2455 : 0 : if (snode_b != nullptr)
2456 : : /* One is nullptr. */
2457 : : return -1;
2458 : : else
2459 : : /* Both are nullptr. */
2460 : 0 : return 0;
2461 : : }
2462 : 390922 : if (snode_b == nullptr)
2463 : : /* One is nullptr. */
2464 : : return 1;
2465 : : /* Neither are nullptr. */
2466 : 387608 : gcc_assert (snode_a && snode_b);
2467 : 387608 : if (snode_a->m_bb->index != snode_b->m_bb->index)
2468 : 34555 : return snode_a->m_bb->index - snode_b->m_bb->index;
2469 : 353053 : if (snode_a->m_id != snode_b->m_id)
2470 : 54501 : return snode_a->m_id - snode_b->m_id;
2471 : :
2472 : 298552 : gcc_assert (snode_a == snode_b);
2473 : :
2474 : : /* Otherwise, we ought to have the same program_point. */
2475 : 298552 : gcc_assert (point_a == point_b);
2476 : :
2477 : : const program_state &state_a = ka.m_enode->get_state ();
2478 : : const program_state &state_b = kb.m_enode->get_state ();
2479 : :
2480 : : /* Sort by sm-state, so that identical sm-states are grouped
2481 : : together in the worklist. */
2482 : 1313041 : for (unsigned sm_idx = 0; sm_idx < state_a.m_checker_states.length ();
2483 : : ++sm_idx)
2484 : : {
2485 : 1202430 : sm_state_map *smap_a = state_a.m_checker_states[sm_idx];
2486 : 1202430 : sm_state_map *smap_b = state_b.m_checker_states[sm_idx];
2487 : :
2488 : 1202430 : if (int smap_cmp = sm_state_map::cmp (*smap_a, *smap_b))
2489 : : return smap_cmp;
2490 : : }
2491 : :
2492 : : /* Otherwise, we have two enodes at the same program point but with
2493 : : different states. We don't have a good total ordering on states,
2494 : : so order them by enode index, so that we have at least have a
2495 : : stable sort. */
2496 : 110611 : return ka.m_enode->m_index - kb.m_enode->m_index;
2497 : : }
2498 : :
2499 : : /* Return a new json::object of the form
2500 : : {"scc" : [per-snode-IDs]}, */
2501 : :
2502 : : std::unique_ptr<json::object>
2503 : 0 : worklist::to_json () const
2504 : : {
2505 : 0 : auto worklist_obj = std::make_unique<json::object> ();
2506 : :
2507 : 0 : worklist_obj->set ("scc", m_scc.to_json ());
2508 : :
2509 : : /* The following field isn't yet being JSONified:
2510 : : queue_t m_queue; */
2511 : :
2512 : 0 : return worklist_obj;
2513 : : }
2514 : :
2515 : : /* exploded_graph's ctor. */
2516 : :
2517 : 3324 : exploded_graph::exploded_graph (const supergraph &sg, logger *logger,
2518 : : const extrinsic_state &ext_state,
2519 : : const state_purge_map *purge_map,
2520 : : const analysis_plan &plan,
2521 : 3324 : int verbosity)
2522 : 3324 : : m_sg (sg), m_logger (logger),
2523 : 3324 : m_worklist (*this, plan),
2524 : 3324 : m_ext_state (ext_state),
2525 : 3324 : m_purge_map (purge_map),
2526 : 3324 : m_plan (plan),
2527 : 3324 : m_diagnostic_manager (logger, ext_state.get_engine (), verbosity),
2528 : 6644 : m_global_stats (m_sg.m_nodes.length ()),
2529 : 9968 : m_functionless_stats (m_sg.m_nodes.length ())
2530 : : {
2531 : 6648 : m_origin = get_or_create_node
2532 : 3324 : (program_point::origin (*ext_state.get_model_manager ()),
2533 : 6648 : program_state (ext_state), nullptr);
2534 : 3324 : }
2535 : :
2536 : : /* exploded_graph's dtor. */
2537 : :
2538 : 3324 : exploded_graph::~exploded_graph ()
2539 : : {
2540 : 464076 : for (auto iter : m_per_point_data)
2541 : 460752 : delete iter.second;
2542 : 4058 : for (auto iter : m_per_function_data)
2543 : 367 : delete iter.second;
2544 : 16772 : for (auto iter : m_per_function_stats)
2545 : 10128 : delete iter.second;
2546 : 20132 : for (auto iter : m_per_call_string_data)
2547 : 8404 : delete iter.second;
2548 : 6648 : }
2549 : :
2550 : : /* Subroutine for use when implementing __attribute__((tainted_args))
2551 : : on functions and on function pointer fields in structs.
2552 : :
2553 : : Called on STATE representing a call to FNDECL.
2554 : : Mark all params of FNDECL in STATE as "tainted". Mark the value of all
2555 : : regions pointed to by params of FNDECL as "tainted".
2556 : :
2557 : : Return true if successful; return false if the "taint" state machine
2558 : : was not found. */
2559 : :
2560 : : static bool
2561 : 184 : mark_params_as_tainted (program_state *state, tree fndecl,
2562 : : const extrinsic_state &ext_state)
2563 : : {
2564 : 184 : unsigned taint_sm_idx;
2565 : 184 : if (!ext_state.get_sm_idx_by_name ("taint", &taint_sm_idx))
2566 : : return false;
2567 : 184 : sm_state_map *smap = state->m_checker_states[taint_sm_idx];
2568 : :
2569 : 184 : const state_machine &sm = ext_state.get_sm (taint_sm_idx);
2570 : 184 : state_machine::state_t tainted = sm.get_state_by_name ("tainted");
2571 : :
2572 : 184 : region_model_manager *mgr = ext_state.get_model_manager ();
2573 : :
2574 : 184 : function *fun = DECL_STRUCT_FUNCTION (fndecl);
2575 : 184 : gcc_assert (fun);
2576 : :
2577 : 435 : for (tree iter_parm = DECL_ARGUMENTS (fndecl); iter_parm;
2578 : 251 : iter_parm = DECL_CHAIN (iter_parm))
2579 : : {
2580 : 251 : tree param = iter_parm;
2581 : 251 : if (tree parm_default_ssa = ssa_default_def (fun, iter_parm))
2582 : 193 : param = parm_default_ssa;
2583 : 251 : const region *param_reg = state->m_region_model->get_lvalue (param, nullptr);
2584 : 251 : const svalue *init_sval = mgr->get_or_create_initial_value (param_reg);
2585 : 251 : smap->set_state (state->m_region_model, init_sval,
2586 : : tainted, nullptr /*origin_new_sval*/, ext_state);
2587 : 251 : if (POINTER_TYPE_P (TREE_TYPE (param)))
2588 : : {
2589 : 48 : const region *pointee_reg = mgr->get_symbolic_region (init_sval);
2590 : : /* Mark "*param" as tainted. */
2591 : 48 : const svalue *init_pointee_sval
2592 : 48 : = mgr->get_or_create_initial_value (pointee_reg);
2593 : 48 : smap->set_state (state->m_region_model, init_pointee_sval,
2594 : : tainted, nullptr /*origin_new_sval*/, ext_state);
2595 : : }
2596 : : }
2597 : :
2598 : : return true;
2599 : : }
2600 : :
2601 : : /* Custom event for use by tainted_args_function_info when a function
2602 : : has been marked with __attribute__((tainted_args)). */
2603 : :
2604 : : class tainted_args_function_custom_event : public custom_event
2605 : : {
2606 : : public:
2607 : 108 : tainted_args_function_custom_event (const event_loc_info &loc_info)
2608 : 108 : : custom_event (loc_info),
2609 : 108 : m_fndecl (loc_info.m_fndecl)
2610 : : {
2611 : : }
2612 : :
2613 : : void
2614 : 216 : print_desc (pretty_printer &pp) const final override
2615 : : {
2616 : 216 : pp_printf (&pp,
2617 : : "function %qE marked with %<__attribute__((tainted_args))%>",
2618 : 216 : m_fndecl);
2619 : 216 : }
2620 : :
2621 : : private:
2622 : : tree m_fndecl;
2623 : : };
2624 : :
2625 : : /* Custom exploded_edge info for top-level calls to a function
2626 : : marked with __attribute__((tainted_args)). */
2627 : :
2628 : : class tainted_args_function_info : public custom_edge_info
2629 : : {
2630 : : public:
2631 : 174 : tainted_args_function_info (tree fndecl)
2632 : 174 : : m_fndecl (fndecl)
2633 : : {}
2634 : :
2635 : 0 : void print (pretty_printer *pp) const final override
2636 : : {
2637 : 0 : pp_string (pp, "call to tainted_args function");
2638 : 0 : };
2639 : :
2640 : 164 : bool update_model (region_model *model,
2641 : : const exploded_edge *eedge,
2642 : : region_model_context *ctxt) const final override
2643 : : {
2644 : 164 : function *fun = eedge->m_dest->get_function ();
2645 : 164 : gcc_assert (fun);
2646 : 164 : model->push_frame (*fun, nullptr, nullptr, ctxt);
2647 : 164 : return true;
2648 : : }
2649 : :
2650 : 108 : void add_events_to_path (checker_path *emission_path,
2651 : : const exploded_edge &,
2652 : : pending_diagnostic &) const final override
2653 : : {
2654 : 108 : emission_path->add_event
2655 : 108 : (std::make_unique<tainted_args_function_custom_event>
2656 : 108 : (event_loc_info (DECL_SOURCE_LOCATION (m_fndecl), m_fndecl, 0)));
2657 : 108 : }
2658 : :
2659 : : private:
2660 : : tree m_fndecl;
2661 : : };
2662 : :
2663 : : /* Ensure that there is an exploded_node representing an external call to
2664 : : FUN, adding it to the worklist if creating it.
2665 : :
2666 : : Add an edge from the origin exploded_node to the function entrypoint
2667 : : exploded_node.
2668 : :
2669 : : Return the exploded_node for the entrypoint to the function. */
2670 : :
2671 : : exploded_node *
2672 : 10288 : exploded_graph::add_function_entry (const function &fun)
2673 : : {
2674 : 10288 : gcc_assert (gimple_has_body_p (fun.decl));
2675 : :
2676 : : /* Be idempotent. */
2677 : 10288 : function *key = const_cast<function *> (&fun);
2678 : 10288 : if (m_functions_with_enodes.contains (key))
2679 : : {
2680 : 306 : logger * const logger = get_logger ();
2681 : 306 : if (logger)
2682 : 0 : logger->log ("entrypoint for %qE already exists", fun.decl);
2683 : 306 : return nullptr;
2684 : : }
2685 : :
2686 : 9982 : program_point point
2687 : 9982 : = program_point::from_function_entry (*m_ext_state.get_model_manager (),
2688 : : m_sg, fun);
2689 : 9982 : program_state state (m_ext_state);
2690 : 9982 : state.push_frame (m_ext_state, fun);
2691 : :
2692 : 9982 : std::unique_ptr<custom_edge_info> edge_info = nullptr;
2693 : :
2694 : 9982 : if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (fun.decl)))
2695 : : {
2696 : 174 : if (mark_params_as_tainted (&state, fun.decl, m_ext_state))
2697 : 174 : edge_info = std::make_unique<tainted_args_function_info> (fun.decl);
2698 : : }
2699 : :
2700 : 9982 : if (!state.m_valid)
2701 : : return nullptr;
2702 : :
2703 : 9982 : exploded_node *enode = get_or_create_node (point, state, nullptr);
2704 : 9982 : if (!enode)
2705 : : return nullptr;
2706 : :
2707 : 9974 : add_edge (m_origin, enode, nullptr, false, std::move (edge_info));
2708 : :
2709 : 9974 : m_functions_with_enodes.add (key);
2710 : :
2711 : 9974 : return enode;
2712 : 9982 : }
2713 : :
2714 : : /* Get or create an exploded_node for (POINT, STATE).
2715 : : If a new node is created and ADD_TO_WORKLIST is true,
2716 : : it is added to the worklist.
2717 : :
2718 : : Use ENODE_FOR_DIAG, a pre-existing enode, for any diagnostics
2719 : : that need to be emitted (e.g. when purging state *before* we have
2720 : : a new enode). */
2721 : :
2722 : : exploded_node *
2723 : 396029 : exploded_graph::get_or_create_node (const program_point &point,
2724 : : const program_state &state,
2725 : : exploded_node *enode_for_diag,
2726 : : bool add_to_worklist)
2727 : : {
2728 : 396029 : logger * const logger = get_logger ();
2729 : 396029 : LOG_FUNC (logger);
2730 : 396029 : if (logger)
2731 : : {
2732 : 171 : format f (false);
2733 : 171 : pretty_printer *pp = logger->get_printer ();
2734 : 171 : logger->start_log_line ();
2735 : 171 : pp_string (pp, "point: ");
2736 : 171 : point.print (pp, f);
2737 : 171 : logger->end_log_line ();
2738 : 171 : logger->start_log_line ();
2739 : 171 : pp_string (pp, "state: ");
2740 : 171 : state.dump_to_pp (m_ext_state, true, false, pp);
2741 : 171 : logger->end_log_line ();
2742 : : }
2743 : :
2744 : : /* Stop exploring paths for which we don't know how to effectively
2745 : : model the state. */
2746 : 396029 : if (!state.m_valid)
2747 : : {
2748 : 0 : if (logger)
2749 : 0 : logger->log ("invalid state; not creating node");
2750 : 0 : return nullptr;
2751 : : }
2752 : :
2753 : 396029 : if (point.get_call_string ().calc_recursion_depth ()
2754 : 396029 : > param_analyzer_max_recursion_depth)
2755 : : {
2756 : 603 : if (logger)
2757 : 0 : logger->log ("rejecting node: recursion limit exceeded");
2758 : 603 : return nullptr;
2759 : : }
2760 : :
2761 : 787528 : auto_cfun sentinel (point.get_function ());
2762 : :
2763 : 395426 : state.validate (get_ext_state ());
2764 : :
2765 : : //state.dump (get_ext_state ());
2766 : :
2767 : : /* Prune state to try to improve the chances of a cache hit,
2768 : : avoiding generating redundant nodes. */
2769 : 395426 : uncertainty_t uncertainty;
2770 : 395426 : program_state pruned_state
2771 : 395426 : = state.prune_for_point (*this, point, enode_for_diag, &uncertainty);
2772 : :
2773 : 395426 : pruned_state.validate (get_ext_state ());
2774 : :
2775 : : //pruned_state.dump (get_ext_state ());
2776 : :
2777 : 395426 : if (logger)
2778 : : {
2779 : 171 : pretty_printer *pp = logger->get_printer ();
2780 : 171 : logger->start_log_line ();
2781 : 171 : pp_string (pp, "pruned_state: ");
2782 : 171 : pruned_state.dump_to_pp (m_ext_state, true, false, pp);
2783 : 171 : logger->end_log_line ();
2784 : 171 : pruned_state.m_region_model->dump_to_pp (logger->get_printer (), true,
2785 : : false);
2786 : : }
2787 : :
2788 : 787528 : stats *per_fn_stats = get_or_create_function_stats (point.get_function ());
2789 : :
2790 : 395426 : stats *per_cs_stats
2791 : 395426 : = &get_or_create_per_call_string_data (point.get_call_string ())->m_stats;
2792 : :
2793 : 395426 : point_and_state ps (point, pruned_state);
2794 : 395426 : ps.validate (m_ext_state);
2795 : 395426 : if (exploded_node **slot = m_point_and_state_to_node.get (&ps))
2796 : : {
2797 : : /* An exploded_node for PS already exists. */
2798 : 3255 : if (logger)
2799 : 10 : logger->log ("reused EN: %i", (*slot)->m_index);
2800 : 3255 : m_global_stats.m_node_reuse_count++;
2801 : 3255 : per_fn_stats->m_node_reuse_count++;
2802 : 3255 : per_cs_stats->m_node_reuse_count++;
2803 : 3255 : return *slot;
2804 : : }
2805 : :
2806 : 392171 : per_program_point_data *per_point_data
2807 : 392171 : = get_or_create_per_program_point_data (point);
2808 : :
2809 : : /* Consider merging state with another enode at this program_point. */
2810 : 923601 : if (flag_analyzer_state_merge && point.state_merge_at_p ())
2811 : : {
2812 : : exploded_node *existing_enode;
2813 : : unsigned i;
2814 : 375085 : FOR_EACH_VEC_ELT (per_point_data->m_enodes, i, existing_enode)
2815 : : {
2816 : 232712 : if (logger)
2817 : 127 : logger->log ("considering merging with existing EN: %i for point",
2818 : 127 : existing_enode->m_index);
2819 : 232712 : gcc_assert (existing_enode->get_point () == point);
2820 : 232712 : const program_state &existing_state = existing_enode->get_state ();
2821 : :
2822 : : /* This merges successfully within the loop. */
2823 : :
2824 : 232712 : program_state merged_state (m_ext_state);
2825 : 232712 : if (pruned_state.can_merge_with_p (existing_state, m_ext_state, point,
2826 : : &merged_state))
2827 : : {
2828 : 26943 : merged_state.validate (m_ext_state);
2829 : 26943 : if (logger)
2830 : 60 : logger->log ("merging new state with that of EN: %i",
2831 : 60 : existing_enode->m_index);
2832 : :
2833 : : /* Try again for a cache hit.
2834 : : Whether we get one or not, merged_state's value_ids have no
2835 : : relationship to those of the input state, and thus to those
2836 : : of CHANGE, so we must purge any svalue_ids from *CHANGE. */
2837 : 26943 : ps.set_state (merged_state);
2838 : :
2839 : 26943 : if (exploded_node **slot = m_point_and_state_to_node.get (&ps))
2840 : : {
2841 : : /* An exploded_node for PS already exists. */
2842 : 1807 : if (logger)
2843 : 0 : logger->log ("reused EN: %i", (*slot)->m_index);
2844 : 1807 : m_global_stats.m_node_reuse_after_merge_count++;
2845 : 1807 : per_fn_stats->m_node_reuse_after_merge_count++;
2846 : 1807 : per_cs_stats->m_node_reuse_after_merge_count++;
2847 : 1807 : return *slot;
2848 : : }
2849 : : }
2850 : : else
2851 : 205769 : if (logger)
2852 : 67 : logger->log ("not merging new state with that of EN: %i",
2853 : 67 : existing_enode->m_index);
2854 : 232712 : }
2855 : : }
2856 : :
2857 : : /* Impose a limit on the number of enodes per program point, and
2858 : : simply stop if we exceed it. */
2859 : 390364 : if ((int)per_point_data->m_enodes.length ()
2860 : 390364 : >= param_analyzer_max_enodes_per_program_point)
2861 : : {
2862 : 2187 : pretty_printer pp;
2863 : 2187 : point.print (&pp, format (false));
2864 : 2187 : print_enode_indices (&pp, per_point_data->m_enodes);
2865 : 2187 : if (logger)
2866 : 0 : logger->log ("not creating enode; too many at program point: %s",
2867 : : pp_formatted_text (&pp));
2868 : 4370 : warning_at (point.get_location (), OPT_Wanalyzer_too_complex,
2869 : : "terminating analysis for this program point: %s",
2870 : : pp_formatted_text (&pp));
2871 : 2187 : per_point_data->m_excess_enodes++;
2872 : 2187 : return nullptr;
2873 : 2187 : }
2874 : :
2875 : 388177 : ps.validate (m_ext_state);
2876 : :
2877 : : /* An exploded_node for "ps" doesn't already exist; create one. */
2878 : 773034 : exploded_node *node = new exploded_node (ps, m_nodes.length ());
2879 : 388177 : add_node (node);
2880 : 388177 : m_point_and_state_to_node.put (node->get_ps_key (), node);
2881 : :
2882 : : /* Update per-program_point data. */
2883 : 388177 : per_point_data->m_enodes.safe_push (node);
2884 : :
2885 : 388177 : m_global_stats.m_num_nodes++;
2886 : 388177 : per_fn_stats->m_num_nodes++;
2887 : 388177 : per_cs_stats->m_num_nodes++;
2888 : :
2889 : 388177 : if (logger)
2890 : : {
2891 : 161 : format f (false);
2892 : 161 : pretty_printer *pp = logger->get_printer ();
2893 : 161 : logger->log ("created EN: %i", node->m_index);
2894 : 161 : logger->start_log_line ();
2895 : 161 : pp_string (pp, "point: ");
2896 : 161 : point.print (pp, f);
2897 : 161 : logger->end_log_line ();
2898 : 161 : logger->start_log_line ();
2899 : 161 : pp_string (pp, "state: ");
2900 : 161 : ps.get_state ().dump_to_pp (m_ext_state, true, false, pp);
2901 : 161 : logger->end_log_line ();
2902 : : }
2903 : :
2904 : : /* Add the new node to the worlist. */
2905 : 388177 : if (add_to_worklist)
2906 : 381103 : m_worklist.add_node (node);
2907 : : else
2908 : 7074 : node->set_status (exploded_node::status::special);
2909 : : return node;
2910 : 791455 : }
2911 : :
2912 : : /* Add an exploded_edge from SRC to DEST, recording its association
2913 : : with SEDGE (which may be NULL), and, if non-NULL, taking ownership
2914 : : of CUSTOM_INFO. COULD_DO_WORK is used for detecting infinite loops.
2915 : : Return the newly-created eedge. */
2916 : :
2917 : : exploded_edge *
2918 : 402172 : exploded_graph::add_edge (exploded_node *src, exploded_node *dest,
2919 : : const superedge *sedge, bool could_do_work,
2920 : : std::unique_ptr<custom_edge_info> custom_info)
2921 : : {
2922 : 402172 : if (get_logger ())
2923 : 172 : get_logger ()->log ("creating edge EN: %i -> EN: %i",
2924 : 172 : src->m_index, dest->m_index);
2925 : 402172 : exploded_edge *e
2926 : : = new exploded_edge (src, dest, sedge, could_do_work,
2927 : 402172 : std::move (custom_info));
2928 : 402172 : digraph<eg_traits>::add_edge (e);
2929 : 402172 : return e;
2930 : : }
2931 : :
2932 : : /* Ensure that this graph has per-program_point-data for POINT;
2933 : : borrow a pointer to it. */
2934 : :
2935 : : per_program_point_data *
2936 : 392171 : exploded_graph::
2937 : : get_or_create_per_program_point_data (const program_point &point)
2938 : : {
2939 : 392171 : if (per_program_point_data **slot = m_per_point_data.get (&point))
2940 : 161795 : return *slot;
2941 : :
2942 : 230376 : per_program_point_data *per_point_data = new per_program_point_data (point);
2943 : 230376 : m_per_point_data.put (&per_point_data->m_key, per_point_data);
2944 : 230376 : return per_point_data;
2945 : : }
2946 : :
2947 : : /* Get this graph's per-program-point-data for POINT if there is any,
2948 : : otherwise nullptr. */
2949 : :
2950 : : per_program_point_data *
2951 : 0 : exploded_graph::get_per_program_point_data (const program_point &point) const
2952 : : {
2953 : 0 : if (per_program_point_data **slot
2954 : 0 : = const_cast <point_map_t &> (m_per_point_data).get (&point))
2955 : 0 : return *slot;
2956 : :
2957 : : return nullptr;
2958 : : }
2959 : :
2960 : : /* Ensure that this graph has per-call_string-data for CS;
2961 : : borrow a pointer to it. */
2962 : :
2963 : : per_call_string_data *
2964 : 395426 : exploded_graph::get_or_create_per_call_string_data (const call_string &cs)
2965 : : {
2966 : 395426 : if (per_call_string_data **slot = m_per_call_string_data.get (&cs))
2967 : 387022 : return *slot;
2968 : :
2969 : 16804 : per_call_string_data *data = new per_call_string_data (cs, m_sg.m_nodes.length ());
2970 : 8404 : m_per_call_string_data.put (&data->m_key,
2971 : : data);
2972 : 8404 : return data;
2973 : : }
2974 : :
2975 : : /* Ensure that this graph has per-function-data for FUN;
2976 : : borrow a pointer to it. */
2977 : :
2978 : : per_function_data *
2979 : 633 : exploded_graph::get_or_create_per_function_data (function *fun)
2980 : : {
2981 : 633 : if (per_function_data **slot = m_per_function_data.get (fun))
2982 : 266 : return *slot;
2983 : :
2984 : 367 : per_function_data *data = new per_function_data ();
2985 : 367 : m_per_function_data.put (fun, data);
2986 : 367 : return data;
2987 : : }
2988 : :
2989 : : /* Get this graph's per-function-data for FUN if there is any,
2990 : : otherwise nullptr. */
2991 : :
2992 : : per_function_data *
2993 : 791 : exploded_graph::get_per_function_data (function *fun) const
2994 : : {
2995 : 1582 : if (per_function_data **slot
2996 : 791 : = const_cast <per_function_data_t &> (m_per_function_data).get (fun))
2997 : 753 : return *slot;
2998 : :
2999 : : return nullptr;
3000 : : }
3001 : :
3002 : : /* Return true if FUN should be traversed directly, rather than only as
3003 : : called via other functions. */
3004 : :
3005 : : static bool
3006 : 10132 : toplevel_function_p (const function &fun, logger *logger)
3007 : : {
3008 : : /* Don't directly traverse into functions that have an "__analyzer_"
3009 : : prefix. Doing so is useful for the analyzer test suite, allowing
3010 : : us to have functions that are called in traversals, but not directly
3011 : : explored, thus testing how the analyzer handles calls and returns.
3012 : : With this, we can have DejaGnu directives that cover just the case
3013 : : of where a function is called by another function, without generating
3014 : : excess messages from the case of the first function being traversed
3015 : : directly. */
3016 : : #define ANALYZER_PREFIX "__analyzer_"
3017 : 10132 : if (!strncmp (IDENTIFIER_POINTER (DECL_NAME (fun.decl)), ANALYZER_PREFIX,
3018 : : strlen (ANALYZER_PREFIX)))
3019 : : {
3020 : 150 : if (logger)
3021 : 0 : logger->log ("not traversing %qE (starts with %qs)",
3022 : : fun.decl, ANALYZER_PREFIX);
3023 : 150 : return false;
3024 : : }
3025 : :
3026 : 9982 : if (logger)
3027 : 2 : logger->log ("traversing %qE (all checks passed)", fun.decl);
3028 : :
3029 : : return true;
3030 : : }
3031 : :
3032 : : /* Custom event for use by tainted_call_info when a callback field has been
3033 : : marked with __attribute__((tainted_args)), for labelling the field. */
3034 : :
3035 : : class tainted_args_field_custom_event : public custom_event
3036 : : {
3037 : : public:
3038 : 4 : tainted_args_field_custom_event (tree field)
3039 : 4 : : custom_event (event_loc_info (DECL_SOURCE_LOCATION (field), NULL_TREE, 0)),
3040 : 4 : m_field (field)
3041 : : {
3042 : 4 : }
3043 : :
3044 : 8 : void print_desc (pretty_printer &pp) const final override
3045 : : {
3046 : 8 : pp_printf (&pp,
3047 : : "field %qE of %qT"
3048 : : " is marked with %<__attribute__((tainted_args))%>",
3049 : 8 : m_field, DECL_CONTEXT (m_field));
3050 : 8 : }
3051 : :
3052 : : private:
3053 : : tree m_field;
3054 : : };
3055 : :
3056 : : /* Custom event for use by tainted_call_info when a callback field has been
3057 : : marked with __attribute__((tainted_args)), for labelling the function used
3058 : : in that callback. */
3059 : :
3060 : : class tainted_args_callback_custom_event : public custom_event
3061 : : {
3062 : : public:
3063 : 4 : tainted_args_callback_custom_event (const event_loc_info &loc_info,
3064 : : tree field)
3065 : 4 : : custom_event (loc_info),
3066 : 4 : m_field (field)
3067 : : {
3068 : : }
3069 : :
3070 : 8 : void print_desc (pretty_printer &pp) const final override
3071 : : {
3072 : 8 : pp_printf (&pp,
3073 : : "function %qE used as initializer for field %qE"
3074 : : " marked with %<__attribute__((tainted_args))%>",
3075 : 8 : get_fndecl (), m_field);
3076 : 8 : }
3077 : :
3078 : : private:
3079 : : tree m_field;
3080 : : };
3081 : :
3082 : : /* Custom edge info for use when adding a function used by a callback field
3083 : : marked with '__attribute__((tainted_args))'. */
3084 : :
3085 : : class tainted_args_call_info : public custom_edge_info
3086 : : {
3087 : : public:
3088 : 10 : tainted_args_call_info (tree field, tree fndecl, location_t loc)
3089 : 10 : : m_field (field), m_fndecl (fndecl), m_loc (loc)
3090 : : {}
3091 : :
3092 : 0 : void print (pretty_printer *pp) const final override
3093 : : {
3094 : 0 : pp_string (pp, "call to tainted field");
3095 : 0 : };
3096 : :
3097 : 9 : bool update_model (region_model *model,
3098 : : const exploded_edge *eedge,
3099 : : region_model_context *) const final override
3100 : : {
3101 : 18 : model->push_frame (*eedge->m_dest->get_function (),
3102 : : nullptr, nullptr, nullptr);
3103 : 9 : return true;
3104 : : }
3105 : :
3106 : 4 : void add_events_to_path (checker_path *emission_path,
3107 : : const exploded_edge &,
3108 : : pending_diagnostic &) const final override
3109 : : {
3110 : : /* Show the field in the struct declaration, e.g.
3111 : : "(1) field 'store' is marked with '__attribute__((tainted_args))'" */
3112 : 4 : emission_path->add_event
3113 : 4 : (std::make_unique<tainted_args_field_custom_event> (m_field));
3114 : :
3115 : : /* Show the callback in the initializer
3116 : : e.g.
3117 : : "(2) function 'gadget_dev_desc_UDC_store' used as initializer
3118 : : for field 'store' marked with '__attribute__((tainted_args))'". */
3119 : 4 : emission_path->add_event
3120 : 4 : (std::make_unique<tainted_args_callback_custom_event>
3121 : 4 : (event_loc_info (m_loc, m_fndecl, 0),
3122 : : m_field));
3123 : 4 : }
3124 : :
3125 : : private:
3126 : : tree m_field;
3127 : : tree m_fndecl;
3128 : : location_t m_loc;
3129 : : };
3130 : :
3131 : : /* Given an initializer at LOC for FIELD marked with
3132 : : '__attribute__((tainted_args))' initialized with FNDECL, add an
3133 : : entrypoint to FNDECL to EG (and to its worklist) where the params to
3134 : : FNDECL are marked as tainted. */
3135 : :
3136 : : static void
3137 : 10 : add_tainted_args_callback (exploded_graph *eg, tree field, tree fndecl,
3138 : : location_t loc)
3139 : : {
3140 : 10 : logger *logger = eg->get_logger ();
3141 : :
3142 : 10 : LOG_SCOPE (logger);
3143 : :
3144 : 10 : if (!gimple_has_body_p (fndecl))
3145 : : return;
3146 : :
3147 : 10 : const extrinsic_state &ext_state = eg->get_ext_state ();
3148 : :
3149 : 10 : function *fun = DECL_STRUCT_FUNCTION (fndecl);
3150 : 10 : gcc_assert (fun);
3151 : :
3152 : 10 : program_point point
3153 : 10 : = program_point::from_function_entry (*ext_state.get_model_manager (),
3154 : : eg->get_supergraph (), *fun);
3155 : 10 : program_state state (ext_state);
3156 : 10 : state.push_frame (ext_state, *fun);
3157 : :
3158 : 10 : if (!mark_params_as_tainted (&state, fndecl, ext_state))
3159 : : return;
3160 : :
3161 : 10 : if (!state.m_valid)
3162 : : return;
3163 : :
3164 : 10 : exploded_node *enode = eg->get_or_create_node (point, state, nullptr);
3165 : 10 : if (logger)
3166 : : {
3167 : 0 : if (enode)
3168 : 0 : logger->log ("created EN %i for tainted_args %qE entrypoint",
3169 : 0 : enode->m_index, fndecl);
3170 : : else
3171 : : {
3172 : 0 : logger->log ("did not create enode for tainted_args %qE entrypoint",
3173 : : fndecl);
3174 : 0 : return;
3175 : : }
3176 : : }
3177 : :
3178 : 10 : eg->add_edge (eg->get_origin (), enode, nullptr, false,
3179 : 10 : std::make_unique<tainted_args_call_info> (field, fndecl, loc));
3180 : 10 : }
3181 : :
3182 : : /* Callback for walk_tree for finding callbacks within initializers;
3183 : : ensure that any callback initializer where the corresponding field is
3184 : : marked with '__attribute__((tainted_args))' is treated as an entrypoint
3185 : : to the analysis, special-casing that the inputs to the callback are
3186 : : untrustworthy. */
3187 : :
3188 : : static tree
3189 : 27622 : add_any_callbacks (tree *tp, int *, void *data)
3190 : : {
3191 : 27622 : exploded_graph *eg = (exploded_graph *)data;
3192 : 27622 : if (TREE_CODE (*tp) == CONSTRUCTOR)
3193 : : {
3194 : : /* Find fields with the "tainted_args" attribute.
3195 : : walk_tree only walks the values, not the index values;
3196 : : look at the index values. */
3197 : : unsigned HOST_WIDE_INT idx;
3198 : : constructor_elt *ce;
3199 : :
3200 : 18482 : for (idx = 0; vec_safe_iterate (CONSTRUCTOR_ELTS (*tp), idx, &ce);
3201 : : idx++)
3202 : 13731 : if (ce->index && TREE_CODE (ce->index) == FIELD_DECL)
3203 : 12773 : if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (ce->index)))
3204 : : {
3205 : 10 : tree value = ce->value;
3206 : 10 : if (TREE_CODE (value) == ADDR_EXPR
3207 : 10 : && TREE_CODE (TREE_OPERAND (value, 0)) == FUNCTION_DECL)
3208 : 20 : add_tainted_args_callback (eg, ce->index,
3209 : 10 : TREE_OPERAND (value, 0),
3210 : 10 : EXPR_LOCATION (value));
3211 : : }
3212 : : }
3213 : :
3214 : 27622 : return NULL_TREE;
3215 : : }
3216 : :
3217 : : /* Add initial nodes to EG, with entrypoints for externally-callable
3218 : : functions. */
3219 : :
3220 : : void
3221 : 3324 : exploded_graph::build_initial_worklist ()
3222 : : {
3223 : 3324 : logger * const logger = get_logger ();
3224 : 3324 : LOG_SCOPE (logger);
3225 : :
3226 : 3324 : cgraph_node *node;
3227 : 13456 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
3228 : : {
3229 : 10132 : function *fun = node->get_fun ();
3230 : 10132 : gcc_assert (fun);
3231 : 10132 : if (!toplevel_function_p (*fun, logger))
3232 : 150 : continue;
3233 : 9982 : exploded_node *enode = add_function_entry (*fun);
3234 : 9982 : if (logger)
3235 : : {
3236 : 2 : if (enode)
3237 : 2 : logger->log ("created EN %i for %qE entrypoint",
3238 : 2 : enode->m_index, fun->decl);
3239 : : else
3240 : 0 : logger->log ("did not create enode for %qE entrypoint", fun->decl);
3241 : : }
3242 : : }
3243 : :
3244 : : /* Find callbacks that are reachable from global initializers. */
3245 : 3324 : varpool_node *vpnode;
3246 : 9330 : FOR_EACH_VARIABLE (vpnode)
3247 : : {
3248 : 6006 : tree decl = vpnode->decl;
3249 : 6006 : tree init = DECL_INITIAL (decl);
3250 : 6006 : if (!init)
3251 : 1237 : continue;
3252 : 4769 : walk_tree (&init, add_any_callbacks, this, nullptr);
3253 : : }
3254 : 3324 : }
3255 : :
3256 : : /* The main loop of the analysis.
3257 : : Take freshly-created exploded_nodes from the worklist, calling
3258 : : process_node on them to explore the <point, state> graph.
3259 : : Add edges to their successors, potentially creating new successors
3260 : : (which are also added to the worklist). */
3261 : :
3262 : : void
3263 : 3324 : exploded_graph::process_worklist ()
3264 : : {
3265 : 3324 : logger * const logger = get_logger ();
3266 : 3324 : LOG_SCOPE (logger);
3267 : 3324 : auto_timevar tv (TV_ANALYZER_WORKLIST);
3268 : :
3269 : 366890 : while (m_worklist.length () > 0)
3270 : : {
3271 : 360319 : exploded_node *node = m_worklist.take_next ();
3272 : 360319 : gcc_assert (node->get_status () == exploded_node::status::worklist);
3273 : :
3274 : 360319 : if (logger)
3275 : 154 : logger->log ("next to process: EN: %i", node->m_index);
3276 : :
3277 : : /* If we have a run of nodes at the same point, try merging and
3278 : : processing them together, rather than pairwise or individually. */
3279 : 360319 : if (flag_analyzer_state_merge
3280 : 360319 : && node->get_point ().state_merge_at_p ())
3281 : 121950 : if (maybe_process_run_of_enodes (node))
3282 : 7067 : goto handle_limit;
3283 : :
3284 : : /* Avoid exponential explosions of nodes by attempting to merge
3285 : : nodes that are at the same program point and which have
3286 : : sufficiently similar state. */
3287 : 353252 : if (flag_analyzer_state_merge && node != m_origin)
3288 : 346995 : if (exploded_node *node_2 = m_worklist.peek_next ())
3289 : : {
3290 : 296891 : gcc_assert (node_2->get_status ()
3291 : : == exploded_node::status::worklist);
3292 : 296891 : gcc_assert (node != node_2);
3293 : :
3294 : 296891 : if (logger)
3295 : 132 : logger->log ("peek worklist: EN: %i", node_2->m_index);
3296 : :
3297 : 296891 : if (node->get_point () == node_2->get_point ())
3298 : : {
3299 : 64069 : const program_point &point = node->get_point ();
3300 : 64069 : if (logger)
3301 : : {
3302 : 28 : format f (false);
3303 : 28 : pretty_printer *pp = logger->get_printer ();
3304 : 28 : logger->start_log_line ();
3305 : 28 : logger->log_partial
3306 : 28 : ("got potential merge EN: %i and EN: %i at ",
3307 : 28 : node->m_index, node_2->m_index);
3308 : 28 : point.print (pp, f);
3309 : 28 : logger->end_log_line ();
3310 : : }
3311 : 64069 : const program_state &state = node->get_state ();
3312 : 64069 : const program_state &state_2 = node_2->get_state ();
3313 : :
3314 : : /* They shouldn't be equal, or we wouldn't have two
3315 : : separate nodes. */
3316 : 64069 : gcc_assert (state != state_2);
3317 : :
3318 : 64069 : program_state merged_state (m_ext_state);
3319 : 64069 : if (state.can_merge_with_p (state_2, m_ext_state,
3320 : : point, &merged_state))
3321 : : {
3322 : 2588 : if (logger)
3323 : 3 : logger->log ("merging EN: %i and EN: %i",
3324 : 3 : node->m_index, node_2->m_index);
3325 : :
3326 : 2588 : if (merged_state == state)
3327 : : {
3328 : : /* Then merge node_2 into node by adding an edge. */
3329 : 447 : add_edge (node_2, node, nullptr, false);
3330 : :
3331 : : /* Remove node_2 from the worklist. */
3332 : 447 : m_worklist.take_next ();
3333 : 447 : node_2->set_status (exploded_node::status::merger);
3334 : :
3335 : : /* Continue processing "node" below. */
3336 : : }
3337 : 2141 : else if (merged_state == state_2)
3338 : : {
3339 : : /* Then merge node into node_2, and leave node_2
3340 : : in the worklist, to be processed on the next
3341 : : iteration. */
3342 : 1288 : add_edge (node, node_2, nullptr, false);
3343 : 1288 : node->set_status (exploded_node::status::merger);
3344 : 1288 : continue;
3345 : : }
3346 : : else
3347 : : {
3348 : : /* We have a merged state that differs from
3349 : : both state and state_2. */
3350 : :
3351 : : /* Remove node_2 from the worklist. */
3352 : 853 : m_worklist.take_next ();
3353 : :
3354 : : /* Create (or get) an exploded node for the merged
3355 : : states, adding to the worklist. */
3356 : 853 : exploded_node *merged_enode
3357 : 853 : = get_or_create_node (node->get_point (),
3358 : : merged_state, node);
3359 : 853 : if (merged_enode == nullptr)
3360 : 78 : continue;
3361 : :
3362 : 775 : if (logger)
3363 : 2 : logger->log ("merged EN: %i and EN: %i into EN: %i",
3364 : 2 : node->m_index, node_2->m_index,
3365 : 2 : merged_enode->m_index);
3366 : :
3367 : : /* "node" and "node_2" have both now been removed
3368 : : from the worklist; we should not process them.
3369 : :
3370 : : "merged_enode" may be a new node; if so it will be
3371 : : processed in a subsequent iteration.
3372 : : Alternatively, "merged_enode" could be an existing
3373 : : node; one way the latter can
3374 : : happen is if we end up merging a succession of
3375 : : similar nodes into one. */
3376 : :
3377 : : /* If merged_node is one of the two we were merging,
3378 : : add it back to the worklist to ensure it gets
3379 : : processed.
3380 : :
3381 : : Add edges from the merged nodes to it (but not a
3382 : : self-edge). */
3383 : 775 : if (merged_enode == node)
3384 : 0 : m_worklist.add_node (merged_enode);
3385 : : else
3386 : : {
3387 : 775 : add_edge (node, merged_enode, nullptr, false);
3388 : 775 : node->set_status (exploded_node::status::merger);
3389 : : }
3390 : :
3391 : 775 : if (merged_enode == node_2)
3392 : 5 : m_worklist.add_node (merged_enode);
3393 : : else
3394 : : {
3395 : 770 : add_edge (node_2, merged_enode, nullptr, false);
3396 : 770 : node_2->set_status (exploded_node::status::merger);
3397 : : }
3398 : :
3399 : 775 : continue;
3400 : 775 : }
3401 : : }
3402 : :
3403 : : /* TODO: should we attempt more than two nodes,
3404 : : or just do pairs of nodes? (and hope that we get
3405 : : a cascade of mergers). */
3406 : 64069 : }
3407 : : }
3408 : :
3409 : 351111 : process_node (node);
3410 : :
3411 : 358178 : handle_limit:
3412 : : /* Impose a hard limit on the number of exploded nodes, to ensure
3413 : : that the analysis terminates in the face of pathological state
3414 : : explosion (or bugs). */
3415 : 358178 : const int limit
3416 : : = (// Per-supernode limit:
3417 : 358178 : (m_sg.num_nodes () * param_analyzer_bb_explosion_factor)
3418 : : // Allow one for the "origin" enode:
3419 : 358178 : + 1);
3420 : 358178 : if (m_global_stats.m_num_nodes > limit)
3421 : : {
3422 : 77 : if (logger)
3423 : 0 : logger->log ("bailing out; too many nodes");
3424 : 231 : warning_at (node->get_point ().get_location (),
3425 : 77 : OPT_Wanalyzer_too_complex,
3426 : : "analysis bailed out early"
3427 : : " (%i enodes)",
3428 : : m_nodes.length ());
3429 : 77 : return;
3430 : : }
3431 : : }
3432 : 3324 : }
3433 : :
3434 : : /* Attempt to process a consecutive run of sufficiently-similar nodes in
3435 : : the worklist at a point flagged with state_merge_at_p (having already
3436 : : popped ENODE from the head of the worklist).
3437 : :
3438 : : If we have a consecutive run of enodes in the worklist all of which have
3439 : : a single out-edge where all these out-edges are supports_bulk_merge_p and
3440 : : all have the same successor snode and call string, then
3441 : : process them all together, setting their status to status::bulk_merged,
3442 : : and return true.
3443 : : Otherwise, return false, in which case ENODE must be processed in the
3444 : : normal way.
3445 : :
3446 : : When processing them all together, generate successor states based
3447 : : on the edge op update_state_for_bulk_merger, and then attempt to merge
3448 : : these states into a minimal set of merged successor states, partitioning
3449 : : the inputs by merged successor state.
3450 : :
3451 : : Create new exploded nodes for all of the merged states, and add edges
3452 : : connecting the input enodes to the corresponding merger exploded nodes.
3453 : :
3454 : : We hope we have a much smaller number of merged successor states
3455 : : compared to the number of input enodes - ideally just one,
3456 : : if all successor states can be merged.
3457 : :
3458 : : Processing and merging many together as one operation rather than as
3459 : : pairs avoids scaling issues where per-pair mergers could bloat the
3460 : : graph with merger nodes (especially so after switch statements). */
3461 : :
3462 : : bool
3463 : 121950 : exploded_graph::
3464 : : maybe_process_run_of_enodes (exploded_node *enode)
3465 : : {
3466 : : /* A struct for tracking per-input state. */
3467 : 25515 : struct item
3468 : : {
3469 : 25515 : item (exploded_node *input_enode)
3470 : 25515 : : m_input_enode (input_enode),
3471 : 25515 : m_processed_state (input_enode->get_state ()),
3472 : 25515 : m_merger_idx (-1)
3473 : : {}
3474 : :
3475 : : exploded_node *m_input_enode;
3476 : : program_state m_processed_state;
3477 : : int m_merger_idx;
3478 : : };
3479 : :
3480 : 121950 : gcc_assert (enode->get_status () == exploded_node::status::worklist);
3481 : :
3482 : 121950 : const program_point &src_point = enode->get_point ();
3483 : 121950 : const supernode *src_snode = src_point.get_supernode ();
3484 : :
3485 : 121950 : logger * const logger = get_logger ();
3486 : 121950 : LOG_SCOPE (logger);
3487 : :
3488 : 184147 : if (src_snode->m_succs.length () != 1)
3489 : : return false;
3490 : :
3491 : 97794 : auto sedge = src_snode->m_succs[0];
3492 : :
3493 : 97794 : if (!sedge->supports_bulk_merge_p ())
3494 : : return false;
3495 : :
3496 : 35597 : const supernode *dst_snode = src_snode->m_succs[0]->m_dest;
3497 : :
3498 : : /* Find a run of enodes in the worklist that all have single out-sedges
3499 : : go to the same supernode, all of which are bulk-mergeable (i.e. have
3500 : : a simple single intraprocedural outcome). */
3501 : 35597 : auto_vec <exploded_node *> enodes;
3502 : 35597 : enodes.safe_push (enode);
3503 : 54045 : while (exploded_node *enode_2 = m_worklist.peek_next ())
3504 : : {
3505 : 48254 : gcc_assert (enode_2->get_status ()
3506 : : == exploded_node::status::worklist);
3507 : 48254 : gcc_assert (enode_2->m_succs.length () == 0);
3508 : :
3509 : 48254 : const program_point &point_2 = enode_2->get_point ();
3510 : 48254 : const supernode *src_snode_2 = point_2.get_supernode ();
3511 : :
3512 : 48254 : if (src_snode_2->m_succs.length () != 1)
3513 : : break;
3514 : 47397 : auto sedge_2 = src_snode_2->m_succs[0];
3515 : 47397 : if (sedge_2->m_dest != dst_snode)
3516 : : break;
3517 : 19568 : if (&point_2.get_call_string () != &src_point.get_call_string ())
3518 : : break;
3519 : 18448 : if (!sedge_2->supports_bulk_merge_p ())
3520 : : break;
3521 : :
3522 : 18448 : enodes.safe_push (enode_2);
3523 : 18448 : m_worklist.take_next ();
3524 : 18448 : }
3525 : :
3526 : : /* If the only node is ENODE, then give up. */
3527 : 35597 : if (enodes.length () == 1)
3528 : : return false;
3529 : :
3530 : 7067 : if (logger)
3531 : 3 : logger->log ("got run of %i bulk-mergable enodes going to SN: %i",
3532 : 3 : enodes.length (), dst_snode->m_id);
3533 : :
3534 : : /* All of these enodes have a shared intraprocedural successor point
3535 : : (even if they were for different in-edges). */
3536 : 7067 : program_point next_point (sedge->m_dest,
3537 : 7067 : src_point.get_call_string ());
3538 : :
3539 : : /* Calculate the successor state for each enode in enodes. */
3540 : 14134 : auto_delete_vec<item> items (enodes.length ());
3541 : 7067 : unsigned i;
3542 : 7067 : exploded_node *iter_enode;
3543 : 32582 : FOR_EACH_VEC_ELT (enodes, i, iter_enode)
3544 : : {
3545 : 25515 : item *it = new item (iter_enode);
3546 : 25515 : items.quick_push (it);
3547 : 25515 : const program_state &state = iter_enode->get_state ();
3548 : 25515 : program_state *next_state = &it->m_processed_state;
3549 : 25515 : next_state->validate (m_ext_state);
3550 : 25515 : gcc_assert (iter_enode->get_supernode ()->m_succs.length () == 1);
3551 : 25515 : const superedge *iter_sedge = iter_enode->get_supernode ()->m_succs[0];
3552 : 25515 : if (auto op = iter_sedge->get_op ())
3553 : 408 : op->update_state_for_bulk_merger (state, *next_state);
3554 : 25515 : next_state->validate (m_ext_state);
3555 : : }
3556 : :
3557 : : /* Attempt to partition the items into a set of merged states.
3558 : : We hope we have a much smaller number of merged states
3559 : : compared to the number of input enodes - ideally just one,
3560 : : if all can be merged. */
3561 : 7067 : auto_delete_vec <program_state> merged_states;
3562 : 7067 : auto_vec<item *> first_item_for_each_merged_state;
3563 : 7067 : item *it;
3564 : 32582 : FOR_EACH_VEC_ELT (items, i, it)
3565 : : {
3566 : 25515 : const program_state &it_state = it->m_processed_state;
3567 : 25515 : program_state *merged_state;
3568 : 25515 : unsigned iter_merger_idx;
3569 : 63720 : FOR_EACH_VEC_ELT (merged_states, iter_merger_idx, merged_state)
3570 : : {
3571 : 47986 : merged_state->validate (m_ext_state);
3572 : 47986 : program_state merge (m_ext_state);
3573 : 47986 : if (it_state.can_merge_with_p (*merged_state, m_ext_state,
3574 : : next_point, &merge))
3575 : : {
3576 : 9781 : *merged_state = merge;
3577 : 9781 : merged_state->validate (m_ext_state);
3578 : 9781 : it->m_merger_idx = iter_merger_idx;
3579 : 9781 : if (logger)
3580 : 0 : logger->log ("reusing merger state %i for item %i (EN: %i)",
3581 : 0 : it->m_merger_idx, i, it->m_input_enode->m_index);
3582 : 9781 : goto got_merger;
3583 : : }
3584 : 47986 : }
3585 : : /* If it couldn't be merged with any existing merged_states,
3586 : : create a new one. */
3587 : 15734 : if (it->m_merger_idx == -1)
3588 : : {
3589 : 15734 : it->m_merger_idx = merged_states.length ();
3590 : 15734 : merged_states.safe_push (new program_state (it_state));
3591 : 15734 : first_item_for_each_merged_state.safe_push (it);
3592 : 15734 : if (logger)
3593 : 7 : logger->log ("using new merger state %i for item %i (EN: %i)",
3594 : 7 : it->m_merger_idx, i, it->m_input_enode->m_index);
3595 : : }
3596 : 0 : got_merger:
3597 : 25515 : gcc_assert (it->m_merger_idx >= 0);
3598 : 25515 : gcc_assert ((unsigned)it->m_merger_idx < merged_states.length ());
3599 : : }
3600 : :
3601 : : /* Create merger nodes. */
3602 : 21201 : auto_vec<exploded_node *> next_enodes (merged_states.length ());
3603 : 7067 : program_state *merged_state;
3604 : 22801 : FOR_EACH_VEC_ELT (merged_states, i, merged_state)
3605 : : {
3606 : 15734 : exploded_node *src_enode
3607 : 15734 : = first_item_for_each_merged_state[i]->m_input_enode;
3608 : 15734 : exploded_node *next
3609 : 15734 : = get_or_create_node (next_point, *merged_state, src_enode);
3610 : : /* "next" could be nullptr; we handle that when adding the edges below. */
3611 : 15734 : next_enodes.quick_push (next);
3612 : 15734 : if (logger)
3613 : : {
3614 : 7 : if (next)
3615 : 7 : logger->log ("using EN: %i for merger state %i", next->m_index, i);
3616 : : else
3617 : 0 : logger->log ("using NULL enode for merger state %i", i);
3618 : : }
3619 : : }
3620 : :
3621 : : /* Create edges from each input enode to the appropriate successor enode.
3622 : : Update the status of the now-processed input enodes. */
3623 : 32582 : FOR_EACH_VEC_ELT (items, i, it)
3624 : : {
3625 : 25515 : exploded_node *next = next_enodes[it->m_merger_idx];
3626 : 25515 : if (next)
3627 : : {
3628 : 24971 : gcc_assert (it->m_input_enode->get_supernode ()->m_succs.length ()
3629 : : == 1);
3630 : 24971 : const superedge *sedge
3631 : 24971 : = it->m_input_enode->get_supernode ()->m_succs[0];
3632 : 24971 : add_edge (it->m_input_enode, next, sedge,
3633 : : false); /* no "work" is done during merger. */
3634 : : }
3635 : 25515 : it->m_input_enode->set_status (exploded_node::status::bulk_merged);
3636 : : }
3637 : :
3638 : 7067 : if (logger)
3639 : 6 : logger->log ("merged %i in-enodes into %i out-enode(s) at SN: %i",
3640 : 3 : items.length (), merged_states.length (), dst_snode->m_id);
3641 : :
3642 : 7067 : return true;
3643 : 129017 : }
3644 : :
3645 : : /* The core of exploded_graph::process_worklist (the main analysis loop),
3646 : : handling one node in the worklist.
3647 : :
3648 : : Get successor <point, state> pairs for NODE, calling get_or_create on
3649 : : them, and adding an exploded_edge to each successors.
3650 : :
3651 : : Freshly-created nodes will be added to the worklist. */
3652 : :
3653 : : void
3654 : 351111 : exploded_graph::process_node (exploded_node *node)
3655 : : {
3656 : 351111 : logger * const logger = get_logger ();
3657 : 351111 : LOG_FUNC_1 (logger, "EN: %i", node->m_index);
3658 : :
3659 : 351111 : node->set_status (exploded_node::status::processed);
3660 : :
3661 : 351111 : const program_point &point = node->get_point ();
3662 : :
3663 : : /* Update cfun and input_location in case of an ICE: make it easier to
3664 : : track down which source construct we're failing to handle. */
3665 : 698902 : auto_cfun sentinel (node->get_function ());
3666 : :
3667 : 351111 : input_location = node->get_location ();
3668 : :
3669 : 351111 : const program_state &state = node->get_state ();
3670 : 351111 : if (logger)
3671 : : {
3672 : 149 : pretty_printer *pp = logger->get_printer ();
3673 : 149 : logger->start_log_line ();
3674 : 149 : pp_string (pp, "point: ");
3675 : 149 : point.print (pp, format (false));
3676 : 149 : pp_string (pp, ", state: ");
3677 : 149 : state.dump_to_pp (m_ext_state, true, false, pp);
3678 : 149 : logger->end_log_line ();
3679 : : }
3680 : :
3681 : : /* Don't do anything for the origin enode; the initial population of the
3682 : : worklist has already added successor enodes. */
3683 : 351111 : if (point.get_supernode () == nullptr)
3684 : : return;
3685 : :
3686 : : /* Specialcase for EXIT BBs, which don't have out-edges. */
3687 : 347791 : if (point.get_supernode ()->exit_p ())
3688 : : {
3689 : 16972 : gcc_assert (point.get_supernode ()->m_succs.length () == 0);
3690 : :
3691 : 16972 : if (point.get_stack_depth () > 1)
3692 : : {
3693 : : /* Interprocedural return. */
3694 : 5770 : auto &src_call_string = point.get_call_string ();
3695 : :
3696 : 5770 : const call_string::element_t &top_of_stack
3697 : 5770 : = src_call_string.get_top_of_stack ();
3698 : 5770 : const call_string *dst_call_string = src_call_string.get_parent ();
3699 : 5770 : const program_point dst_point
3700 : : (top_of_stack.get_return_snode_in_caller (),
3701 : 5770 : *dst_call_string);
3702 : 5770 : auto edge_info
3703 : 5770 : = std::make_unique<interprocedural_return> (top_of_stack.get_call_stmt ());
3704 : :
3705 : 5770 : const program_state &src_state (node->get_state ());
3706 : 5770 : program_state dst_state (src_state);
3707 : 5770 : uncertainty_t uncertainty;
3708 : 5770 : impl_region_model_context ctxt (*this, node,
3709 : : &src_state, &dst_state, &uncertainty,
3710 : : nullptr,
3711 : 5770 : nullptr);
3712 : 5770 : edge_info->update_state (&dst_state, nullptr, &ctxt);
3713 : :
3714 : 5770 : program_state::detect_leaks (src_state, dst_state,
3715 : : nullptr, get_ext_state (),
3716 : : &ctxt);
3717 : :
3718 : 11540 : if (exploded_node *next
3719 : 5770 : = get_or_create_node (dst_point, dst_state, node))
3720 : 5658 : add_edge (node, next, nullptr, false,
3721 : 5658 : std::move (edge_info));
3722 : 11540 : }
3723 : : else
3724 : : {
3725 : : /* End of top-level of analysis for this function.
3726 : : Detect leaks, and potentially create a function summary. */
3727 : 11202 : node->detect_leaks (*this);
3728 : :
3729 : 11202 : if (flag_analyzer_call_summaries
3730 : 11202 : && point.get_call_string ().empty_p ())
3731 : : {
3732 : : /* TODO: create function summary
3733 : : There can be more than one; each corresponds to a different
3734 : : final enode in the function. */
3735 : 633 : if (logger)
3736 : : {
3737 : 0 : pretty_printer *pp = logger->get_printer ();
3738 : 0 : logger->start_log_line ();
3739 : 0 : logger->log_partial
3740 : 0 : ("would create function summary for %qE; state: ",
3741 : : point.get_fndecl ());
3742 : 0 : state.dump_to_pp (m_ext_state, true, false, pp);
3743 : 0 : logger->end_log_line ();
3744 : : }
3745 : 633 : per_function_data *per_fn_data
3746 : 633 : = get_or_create_per_function_data (point.get_function ());
3747 : 633 : per_fn_data->add_call_summary (node);
3748 : : }
3749 : : }
3750 : :
3751 : 16972 : return;
3752 : : }
3753 : :
3754 : : /* Traverse into successors of the supernode. */
3755 : : int i;
3756 : : superedge *succ;
3757 : 1019957 : FOR_EACH_VEC_ELT (point.get_supernode ()->m_succs, i, succ)
3758 : : {
3759 : 359155 : if (logger)
3760 : : {
3761 : 158 : label_text succ_desc (succ->get_description (false));
3762 : 158 : logger->log ("considering SN: %i -> SN: %i (%s)",
3763 : 158 : succ->m_src->m_id, succ->m_dest->m_id,
3764 : : succ_desc.get ());
3765 : 158 : }
3766 : :
3767 : 359155 : program_point next_point (succ->m_dest, point.get_call_string ());
3768 : 359155 : program_state next_state (state);
3769 : 359155 : uncertainty_t uncertainty;
3770 : :
3771 : : /* Find the outcome(s) of any operation on the edge. */
3772 : 359155 : operation_context op_ctxt (*this, *node, *succ);
3773 : :
3774 : : /* Skip EH edges. */
3775 : 359155 : if (auto cfg_edge = succ->get_any_cfg_edge ())
3776 : 114444 : if (cfg_edge->flags & EDGE_EH)
3777 : 919 : continue;
3778 : :
3779 : 358236 : if (auto op = succ->get_op ())
3780 : 303680 : op->execute (op_ctxt);
3781 : : else
3782 : : {
3783 : : /* No-op.
3784 : : Unconditional goto to the dst point, which
3785 : : must be in same function.
3786 : : The supernode changes, but the callstring and
3787 : : state do not change. */
3788 : 54556 : if (logger)
3789 : 20 : logger->log ("handling no-op edge");
3790 : 54556 : auto dst_point (op_ctxt.get_next_intraprocedural_point ());
3791 : 54556 : if (exploded_node *next
3792 : 54556 : = get_or_create_node (dst_point,
3793 : : node->get_state (),
3794 : : node))
3795 : 54387 : add_edge (node, next, succ, false);
3796 : : }
3797 : 359155 : }
3798 : 351111 : }
3799 : :
3800 : : /* Ensure that this graph has a stats instance for FN, return it.
3801 : : FN can be nullptr, in which case a stats instances is returned covering
3802 : : "functionless" parts of the graph (the origin node). */
3803 : :
3804 : : stats *
3805 : 395426 : exploded_graph::get_or_create_function_stats (function *fn)
3806 : : {
3807 : 395426 : if (!fn)
3808 : 3324 : return &m_functionless_stats;
3809 : :
3810 : 392102 : if (stats **slot = m_per_function_stats.get (fn))
3811 : 381974 : return *slot;
3812 : : else
3813 : : {
3814 : 10128 : int num_supernodes = 0;
3815 : 1611769 : for (auto snode : m_sg.m_nodes)
3816 : 1581385 : if (snode->get_function () == fn)
3817 : 181228 : ++num_supernodes;
3818 : 10128 : stats *new_stats = new stats (num_supernodes);
3819 : 10128 : m_per_function_stats.put (fn, new_stats);
3820 : 10128 : return new_stats;
3821 : : }
3822 : : }
3823 : :
3824 : : /* Print bar charts to PP showing:
3825 : : - the number of enodes per function, and
3826 : : - for each function:
3827 : : - the number of enodes per supernode/BB
3828 : : - the number of excess enodes per supernode/BB beyond the
3829 : : per-program-point limit, if there were any. */
3830 : :
3831 : : void
3832 : 2 : exploded_graph::print_bar_charts (pretty_printer *pp) const
3833 : : {
3834 : 2 : cgraph_node *cgnode;
3835 : :
3836 : 2 : pp_string (pp, "enodes per function:");
3837 : 2 : pp_newline (pp);
3838 : 2 : bar_chart enodes_per_function;
3839 : 4 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
3840 : : {
3841 : 2 : function *fn = cgnode->get_fun ();
3842 : 2 : const stats * const *s_ptr
3843 : 2 : = const_cast <function_stat_map_t &> (m_per_function_stats).get (fn);
3844 : 4 : enodes_per_function.add_item (function_name (fn),
3845 : 2 : s_ptr ? (*s_ptr)->get_total_enodes () : 0);
3846 : : }
3847 : 2 : enodes_per_function.print (pp);
3848 : :
3849 : : /* Accumulate number of enodes per supernode. */
3850 : 4 : auto_vec<unsigned> enodes_per_supernode (m_sg.m_nodes.length ());
3851 : 76 : for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
3852 : 36 : enodes_per_supernode.quick_push (0);
3853 : : int i;
3854 : : exploded_node *enode;
3855 : 163 : FOR_EACH_VEC_ELT (m_nodes, i, enode)
3856 : : {
3857 : 161 : const supernode *iter_snode = enode->get_supernode ();
3858 : 161 : if (!iter_snode)
3859 : 2 : continue;
3860 : 159 : enodes_per_supernode[iter_snode->m_id]++;
3861 : : }
3862 : :
3863 : : /* Accumulate excess enodes per supernode. */
3864 : 4 : auto_vec<unsigned> excess_enodes_per_supernode (m_sg.m_nodes.length ());
3865 : 38 : for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
3866 : 36 : excess_enodes_per_supernode.quick_push (0);
3867 : 40 : for (point_map_t::iterator iter = m_per_point_data.begin ();
3868 : 78 : iter != m_per_point_data.end (); ++iter)
3869 : : {
3870 : 38 : const program_point *point = (*iter).first;
3871 : 38 : const supernode *iter_snode = point->get_supernode ();
3872 : 38 : if (!iter_snode)
3873 : 2 : continue;
3874 : 36 : const per_program_point_data *point_data = (*iter).second;
3875 : 36 : excess_enodes_per_supernode[iter_snode->m_id]
3876 : 36 : += point_data->m_excess_enodes;
3877 : : }
3878 : :
3879 : : /* Show per-function bar_charts of enodes per supernode/BB. */
3880 : 2 : pp_string (pp, "per-function enodes per supernode/BB:");
3881 : 2 : pp_newline (pp);
3882 : 4 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode)
3883 : : {
3884 : 2 : function *fn = cgnode->get_fun ();
3885 : 2 : pp_printf (pp, "function: %qs", function_name (fn));
3886 : 2 : pp_newline (pp);
3887 : :
3888 : 2 : bar_chart enodes_per_snode;
3889 : 2 : bar_chart excess_enodes_per_snode;
3890 : 2 : bool have_excess_enodes = false;
3891 : 38 : for (size_t i = 0; i < m_sg.m_nodes.length (); i++)
3892 : : {
3893 : 36 : const supernode *iter_snode = m_sg.m_nodes[i];
3894 : 36 : if (iter_snode->get_function () != fn)
3895 : 0 : continue;
3896 : 36 : pretty_printer tmp_pp;
3897 : 36 : pp_printf (&tmp_pp, "sn %i (bb %i)",
3898 : 36 : iter_snode->m_id, iter_snode->m_bb->index);
3899 : 36 : enodes_per_snode.add_item (pp_formatted_text (&tmp_pp),
3900 : 36 : enodes_per_supernode[iter_snode->m_id]);
3901 : 36 : const int num_excess
3902 : 36 : = excess_enodes_per_supernode[iter_snode->m_id];
3903 : 36 : excess_enodes_per_snode.add_item (pp_formatted_text (&tmp_pp),
3904 : : num_excess);
3905 : 36 : if (num_excess)
3906 : 0 : have_excess_enodes = true;
3907 : 36 : }
3908 : 2 : enodes_per_snode.print (pp);
3909 : 2 : if (have_excess_enodes)
3910 : : {
3911 : 0 : pp_printf (pp, "EXCESS ENODES:");
3912 : 0 : pp_newline (pp);
3913 : 0 : excess_enodes_per_snode.print (pp);
3914 : : }
3915 : 2 : }
3916 : 2 : }
3917 : :
3918 : : /* Write all stats information to this graph's logger, if any. */
3919 : :
3920 : : void
3921 : 3324 : exploded_graph::log_stats () const
3922 : : {
3923 : 3324 : logger * const logger = get_logger ();
3924 : 3324 : if (!logger)
3925 : 3322 : return;
3926 : :
3927 : 2 : LOG_SCOPE (logger);
3928 : :
3929 : 2 : m_ext_state.get_engine ()->log_stats (logger);
3930 : :
3931 : 4 : logger->log ("m_sg.num_nodes (): %i", m_sg.num_nodes ());
3932 : 4 : logger->log ("m_nodes.length (): %i", m_nodes.length ());
3933 : 4 : logger->log ("m_edges.length (): %i", m_edges.length ());
3934 : 2 : logger->log ("remaining enodes in worklist: %i", m_worklist.length ());
3935 : :
3936 : 2 : logger->log ("global stats:");
3937 : 2 : m_global_stats.log (logger);
3938 : :
3939 : 2 : for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
3940 : 8 : iter != m_per_function_stats.end ();
3941 : 2 : ++iter)
3942 : : {
3943 : 2 : function *fn = (*iter).first;
3944 : 2 : log_scope s (logger, function_name (fn));
3945 : 2 : (*iter).second->log (logger);
3946 : 2 : }
3947 : :
3948 : 2 : print_bar_charts (logger->get_printer ());
3949 : 2 : }
3950 : :
3951 : : /* Dump all stats information to OUT. */
3952 : :
3953 : : void
3954 : 0 : exploded_graph::dump_stats (FILE *out) const
3955 : : {
3956 : 0 : fprintf (out, "m_sg.num_nodes (): %i\n", m_sg.num_nodes ());
3957 : 0 : fprintf (out, "m_nodes.length (): %i\n", m_nodes.length ());
3958 : 0 : fprintf (out, "m_edges.length (): %i\n", m_edges.length ());
3959 : 0 : fprintf (out, "remaining enodes in worklist: %i", m_worklist.length ());
3960 : :
3961 : 0 : fprintf (out, "global stats:\n");
3962 : 0 : m_global_stats.dump (out);
3963 : :
3964 : 0 : for (function_stat_map_t::iterator iter = m_per_function_stats.begin ();
3965 : 0 : iter != m_per_function_stats.end ();
3966 : 0 : ++iter)
3967 : : {
3968 : 0 : function *fn = (*iter).first;
3969 : 0 : fprintf (out, "function: %s\n", function_name (fn));
3970 : 0 : (*iter).second->dump (out);
3971 : : }
3972 : 0 : }
3973 : :
3974 : : /* Return a new json::object of the form
3975 : : {"nodes" : [objs for enodes],
3976 : : "edges" : [objs for eedges],
3977 : : "ext_state": object for extrinsic_state,
3978 : : "diagnostic_manager": object for diagnostic_manager}. */
3979 : :
3980 : : std::unique_ptr<json::object>
3981 : 0 : exploded_graph::to_json () const
3982 : : {
3983 : 0 : auto egraph_obj = std::make_unique<json::object> ();
3984 : :
3985 : : /* Nodes. */
3986 : 0 : {
3987 : 0 : auto nodes_arr = std::make_unique<json::array> ();
3988 : 0 : unsigned i;
3989 : 0 : exploded_node *n;
3990 : 0 : FOR_EACH_VEC_ELT (m_nodes, i, n)
3991 : 0 : nodes_arr->append (n->to_json (m_ext_state));
3992 : 0 : egraph_obj->set ("nodes", std::move (nodes_arr));
3993 : 0 : }
3994 : :
3995 : : /* Edges. */
3996 : 0 : {
3997 : 0 : auto edges_arr = std::make_unique<json::array> ();
3998 : 0 : unsigned i;
3999 : 0 : exploded_edge *n;
4000 : 0 : FOR_EACH_VEC_ELT (m_edges, i, n)
4001 : 0 : edges_arr->append (n->to_json ());
4002 : 0 : egraph_obj->set ("edges", std::move (edges_arr));
4003 : 0 : }
4004 : :
4005 : : /* m_sg is JSONified at the top-level. */
4006 : :
4007 : 0 : egraph_obj->set ("ext_state", m_ext_state.to_json ());
4008 : 0 : egraph_obj->set ("worklist", m_worklist.to_json ());
4009 : 0 : egraph_obj->set ("diagnostic_manager", m_diagnostic_manager.to_json ());
4010 : :
4011 : : /* The following fields aren't yet being JSONified:
4012 : : const state_purge_map *const m_purge_map;
4013 : : const analysis_plan &m_plan;
4014 : : stats m_global_stats;
4015 : : function_stat_map_t m_per_function_stats;
4016 : : stats m_functionless_stats;
4017 : : call_string_data_map_t m_per_call_string_data; */
4018 : :
4019 : 0 : return egraph_obj;
4020 : : }
4021 : :
4022 : : /* class exploded_path. */
4023 : :
4024 : : /* Copy ctor. */
4025 : :
4026 : 4 : exploded_path::exploded_path (const exploded_path &other)
4027 : 8 : : m_edges (other.m_edges.length ())
4028 : : {
4029 : 4 : int i;
4030 : 4 : const exploded_edge *eedge;
4031 : 41 : FOR_EACH_VEC_ELT (other.m_edges, i, eedge)
4032 : 33 : m_edges.quick_push (eedge);
4033 : 4 : }
4034 : :
4035 : : /* Look for the last use of SEARCH_STMT within this path.
4036 : : If found write the edge's index to *OUT_IDX and return true, otherwise
4037 : : return false. */
4038 : :
4039 : : bool
4040 : 804 : exploded_path::find_stmt_backwards (const gimple *search_stmt,
4041 : : int *out_idx) const
4042 : : {
4043 : 804 : int i;
4044 : 804 : const exploded_edge *eedge;
4045 : 11614 : FOR_EACH_VEC_ELT_REVERSE (m_edges, i, eedge)
4046 : 10718 : if (search_stmt->code == GIMPLE_PHI)
4047 : : {
4048 : : /* Each phis_for_edge_op instance handles multiple phi stmts
4049 : : at once, so we have to special-case the search for a phi stmt. */
4050 : 778 : if (auto op = eedge->maybe_get_op ())
4051 : 562 : if (auto phis_op = op->dyn_cast_phis_for_edge_op ())
4052 : 88 : if (phis_op->defines_ssa_name_p (gimple_phi_result (search_stmt)))
4053 : : {
4054 : 40 : *out_idx = i;
4055 : 40 : return true;
4056 : : }
4057 : : }
4058 : : else
4059 : : {
4060 : : /* Non-phi stmt. */
4061 : 9940 : if (const gimple *stmt = eedge->maybe_get_stmt ())
4062 : 7232 : if (stmt == search_stmt)
4063 : : {
4064 : 672 : *out_idx = i;
4065 : 672 : return true;
4066 : : }
4067 : : }
4068 : : return false;
4069 : : }
4070 : :
4071 : : /* Get the final exploded_node in this path, which must be non-empty. */
4072 : :
4073 : : exploded_node *
4074 : 12030 : exploded_path::get_final_enode () const
4075 : : {
4076 : 12030 : gcc_assert (m_edges.length () > 0);
4077 : 12030 : return m_edges[m_edges.length () - 1]->m_dest;
4078 : : }
4079 : :
4080 : : /* Check state along this path, returning true if it is feasible.
4081 : : If OUT is non-NULL, and the path is infeasible, write a new
4082 : : feasibility_problem to *OUT. */
4083 : :
4084 : : bool
4085 : 4 : exploded_path::feasible_p (logger *logger,
4086 : : std::unique_ptr<feasibility_problem> *out,
4087 : : engine *eng, const exploded_graph *eg) const
4088 : : {
4089 : 4 : LOG_SCOPE (logger);
4090 : :
4091 : 4 : feasibility_state state (eng->get_model_manager (),
4092 : 4 : eg->get_supergraph ());
4093 : :
4094 : : /* Traverse the path, updating this state. */
4095 : 33 : for (unsigned edge_idx = 0; edge_idx < m_edges.length (); edge_idx++)
4096 : : {
4097 : 33 : const exploded_edge *eedge = m_edges[edge_idx];
4098 : 33 : if (logger)
4099 : 0 : logger->log ("considering edge %i: EN:%i -> EN:%i",
4100 : : edge_idx,
4101 : 0 : eedge->m_src->m_index,
4102 : 0 : eedge->m_dest->m_index);
4103 : :
4104 : 33 : std::unique_ptr <rejected_constraint> rc;
4105 : 33 : if (!state.maybe_update_for_edge (logger, eedge, nullptr, &rc))
4106 : : {
4107 : 4 : gcc_assert (rc);
4108 : 4 : if (out)
4109 : 8 : *out = std::make_unique<feasibility_problem> (edge_idx, *eedge,
4110 : 4 : std::move (rc));
4111 : 4 : return false;
4112 : : }
4113 : :
4114 : 29 : if (logger)
4115 : : {
4116 : 0 : logger->log ("state after edge %i: EN:%i -> EN:%i",
4117 : : edge_idx,
4118 : 0 : eedge->m_src->m_index,
4119 : 0 : eedge->m_dest->m_index);
4120 : 0 : logger->start_log_line ();
4121 : 0 : state.get_model ().dump_to_pp (logger->get_printer (), true, false);
4122 : 0 : logger->end_log_line ();
4123 : : }
4124 : 33 : }
4125 : :
4126 : 0 : return true;
4127 : 4 : }
4128 : :
4129 : : /* Dump this path in multiline form to PP.
4130 : : If EXT_STATE is non-NULL, then show the nodes. */
4131 : :
4132 : : void
4133 : 0 : exploded_path::dump_to_pp (pretty_printer *pp,
4134 : : const extrinsic_state *ext_state) const
4135 : : {
4136 : 0 : for (unsigned i = 0; i < m_edges.length (); i++)
4137 : : {
4138 : 0 : const exploded_edge *eedge = m_edges[i];
4139 : 0 : pp_printf (pp, "m_edges[%i]: EN %i -> EN %i",
4140 : : i,
4141 : 0 : eedge->m_src->m_index,
4142 : 0 : eedge->m_dest->m_index);
4143 : 0 : pp_newline (pp);
4144 : :
4145 : 0 : if (ext_state)
4146 : 0 : eedge->m_dest->dump_to_pp (pp, *ext_state);
4147 : : }
4148 : 0 : }
4149 : :
4150 : : /* Dump this path in multiline form to FP. */
4151 : :
4152 : : void
4153 : 0 : exploded_path::dump (FILE *fp, const extrinsic_state *ext_state) const
4154 : : {
4155 : 0 : tree_dump_pretty_printer pp (fp);
4156 : 0 : dump_to_pp (&pp, ext_state);
4157 : 0 : }
4158 : :
4159 : : /* Dump this path in multiline form to stderr. */
4160 : :
4161 : : DEBUG_FUNCTION void
4162 : 0 : exploded_path::dump (const extrinsic_state *ext_state) const
4163 : : {
4164 : 0 : dump (stderr, ext_state);
4165 : 0 : }
4166 : :
4167 : : /* Dump this path verbosely to FILENAME. */
4168 : :
4169 : : void
4170 : 0 : exploded_path::dump_to_file (const char *filename,
4171 : : const extrinsic_state &ext_state) const
4172 : : {
4173 : 0 : FILE *fp = fopen (filename, "w");
4174 : 0 : if (!fp)
4175 : 0 : return;
4176 : 0 : pretty_printer pp;
4177 : 0 : pp_format_decoder (&pp) = default_tree_printer;
4178 : 0 : pp.set_output_stream (fp);
4179 : 0 : dump_to_pp (&pp, &ext_state);
4180 : 0 : pp_flush (&pp);
4181 : 0 : fclose (fp);
4182 : 0 : }
4183 : :
4184 : : /* class feasibility_problem. */
4185 : :
4186 : : void
4187 : 4 : feasibility_problem::dump_to_pp (pretty_printer *pp) const
4188 : : {
4189 : 4 : pp_printf (pp, "edge from EN: %i to EN: %i",
4190 : 4 : m_eedge.m_src->m_index, m_eedge.m_dest->m_index);
4191 : 4 : if (m_rc)
4192 : : {
4193 : 4 : pp_string (pp, "; rejected constraint: ");
4194 : 4 : m_rc->dump_to_pp (pp);
4195 : 4 : pp_string (pp, "; rmodel: ");
4196 : 4 : m_rc->get_model ().dump_to_pp (pp, true, false);
4197 : : }
4198 : 4 : }
4199 : :
4200 : : /* class feasibility_state. */
4201 : :
4202 : : /* Ctor for feasibility_state, at the beginning of a path. */
4203 : :
4204 : 6409 : feasibility_state::feasibility_state (region_model_manager *manager,
4205 : 6409 : const supergraph &sg)
4206 : 6409 : : m_model (manager),
4207 : 12818 : m_snodes_visited (sg.m_nodes.length ())
4208 : : {
4209 : 6409 : bitmap_clear (m_snodes_visited);
4210 : 6409 : }
4211 : :
4212 : : /* Copy ctor for feasibility_state, for extending a path. */
4213 : :
4214 : 471790 : feasibility_state::feasibility_state (const feasibility_state &other)
4215 : 471790 : : m_model (other.m_model),
4216 : 471790 : m_snodes_visited (const_sbitmap (other.m_snodes_visited)->n_bits)
4217 : : {
4218 : 471790 : bitmap_copy (m_snodes_visited, other.m_snodes_visited);
4219 : 471790 : }
4220 : :
4221 : 5754 : feasibility_state::feasibility_state (const region_model &model,
4222 : 5754 : const supergraph &sg)
4223 : 5754 : : m_model (model),
4224 : 11508 : m_snodes_visited (sg.m_nodes.length ())
4225 : : {
4226 : 5754 : bitmap_clear (m_snodes_visited);
4227 : 5754 : }
4228 : :
4229 : : feasibility_state &
4230 : 58549 : feasibility_state::operator= (const feasibility_state &other)
4231 : : {
4232 : 58549 : m_model = other.m_model;
4233 : 58549 : bitmap_copy (m_snodes_visited, other.m_snodes_visited);
4234 : 58549 : return *this;
4235 : : }
4236 : :
4237 : : /* The heart of feasibility-checking.
4238 : :
4239 : : Attempt to update this state in-place based on traversing EEDGE
4240 : : in a path.
4241 : : Update the model for the stmts in the src enode.
4242 : : Attempt to add constraints for EEDGE.
4243 : :
4244 : : If feasible, return true.
4245 : : Otherwise, return false and write to *OUT_RC. */
4246 : :
4247 : : bool
4248 : 206098 : feasibility_state::
4249 : : maybe_update_for_edge (logger *logger,
4250 : : const exploded_edge *eedge,
4251 : : region_model_context *ctxt,
4252 : : std::unique_ptr<rejected_constraint> *out_rc)
4253 : : {
4254 : 206098 : const exploded_node &src_enode = *eedge->m_src;
4255 : 206098 : const program_point &src_point = src_enode.get_point ();
4256 : 206098 : if (logger)
4257 : : {
4258 : 65 : logger->start_log_line ();
4259 : 65 : src_point.print (logger->get_printer (), format (false));
4260 : 65 : logger->end_log_line ();
4261 : : }
4262 : :
4263 : 206098 : if (eedge->m_custom_info)
4264 : 8791 : eedge->m_custom_info->update_model (&m_model, eedge, ctxt);
4265 : : else
4266 : : {
4267 : 197307 : const superedge *sedge = eedge->m_sedge;
4268 : 197307 : if (sedge)
4269 : : {
4270 : 189484 : if (logger)
4271 : : {
4272 : 65 : label_text desc (sedge->get_description (false));
4273 : 65 : logger->log (" sedge: SN:%i -> SN:%i %s",
4274 : 65 : sedge->m_src->m_id,
4275 : 65 : sedge->m_dest->m_id,
4276 : : desc.get ());
4277 : 65 : }
4278 : :
4279 : 189484 : if (sedge->get_op ())
4280 : 151883 : if (!sedge->get_op ()->execute_for_feasibility (*eedge,
4281 : : *this,
4282 : : ctxt,
4283 : : out_rc))
4284 : : {
4285 : 6633 : if (logger)
4286 : : {
4287 : 8 : logger->start_log_line ();
4288 : 8 : logger->log_partial ("rejecting due to region model: ");
4289 : 8 : m_model.dump_to_pp (logger->get_printer (), true, false);
4290 : 8 : logger->end_log_line ();
4291 : : }
4292 : 6633 : return false;
4293 : : }
4294 : : }
4295 : : else
4296 : : {
4297 : : /* Special-case the initial eedge from the origin node to the
4298 : : initial function by pushing a frame for it. */
4299 : 7823 : if (eedge->m_src->m_index == 0)
4300 : : {
4301 : 6236 : function *fun = eedge->m_dest->get_function ();
4302 : 6236 : gcc_assert (fun);
4303 : 6236 : m_model.push_frame (*fun, nullptr, nullptr, ctxt);
4304 : 6236 : if (logger)
4305 : 0 : logger->log (" pushing frame for %qD", fun->decl);
4306 : : }
4307 : : }
4308 : : }
4309 : :
4310 : :
4311 : 199465 : {
4312 : 199465 : const exploded_node &dst_enode = *eedge->m_dest;
4313 : 199465 : const unsigned dst_snode_idx = dst_enode.get_supernode ()->m_id;
4314 : 199465 : bitmap_set_bit (m_snodes_visited, dst_snode_idx);
4315 : : }
4316 : :
4317 : 199465 : return true;
4318 : : }
4319 : :
4320 : : /* Dump this object to PP. */
4321 : :
4322 : : void
4323 : 70 : feasibility_state::dump_to_pp (pretty_printer *pp,
4324 : : bool simple, bool multiline) const
4325 : : {
4326 : 70 : m_model.dump_to_pp (pp, simple, multiline);
4327 : 70 : }
4328 : :
4329 : : /* A family of cluster subclasses for use when generating .dot output for
4330 : : exploded graphs (-fdump-analyzer-exploded-graph), for grouping the
4331 : : enodes into hierarchical boxes.
4332 : :
4333 : : All functionless enodes appear in the top-level graph.
4334 : : Every (function, call_string) pair gets its own cluster. Within that
4335 : : cluster, each supernode gets its own cluster.
4336 : :
4337 : : Hence all enodes relating to a particular function with a particular
4338 : : callstring will be in a cluster together; all enodes for the same
4339 : : function but with a different callstring will be in a different
4340 : : cluster. */
4341 : :
4342 : : /* Base class of cluster for clustering exploded_node instances in .dot
4343 : : output, based on various subclass-specific criteria. */
4344 : :
4345 : 1291 : class exploded_cluster : public cluster<eg_traits>
4346 : : {
4347 : : };
4348 : :
4349 : : /* Cluster containing all exploded_node instances for one supernode. */
4350 : :
4351 : : class supernode_cluster : public exploded_cluster
4352 : : {
4353 : : public:
4354 : 429 : supernode_cluster (const supernode *supernode) : m_supernode (supernode) {}
4355 : :
4356 : : // TODO: dtor?
4357 : :
4358 : 429 : void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
4359 : : {
4360 : 429 : gv->println ("subgraph \"cluster_supernode_%i\" {", m_supernode->m_id);
4361 : 429 : gv->indent ();
4362 : 429 : gv->println ("style=\"dashed\";");
4363 : 858 : gv->println ("label=\"SN: %i (bb: %i; scc: %i)\";",
4364 : 429 : m_supernode->m_id, m_supernode->m_bb->index,
4365 : 429 : args.m_eg.get_scc_id (*m_supernode));
4366 : :
4367 : 429 : int i;
4368 : 429 : exploded_node *enode;
4369 : 1287 : FOR_EACH_VEC_ELT (m_enodes, i, enode)
4370 : 429 : enode->dump_dot (gv, args);
4371 : :
4372 : : /* Terminate subgraph. */
4373 : 429 : gv->outdent ();
4374 : 429 : gv->println ("}");
4375 : 429 : }
4376 : :
4377 : 429 : void add_node (exploded_node *en) final override
4378 : : {
4379 : 0 : m_enodes.safe_push (en);
4380 : 0 : }
4381 : :
4382 : : /* Comparator for use by auto_vec<supernode_cluster *>::qsort. */
4383 : :
4384 : 0 : static int cmp_ptr_ptr (const void *p1, const void *p2)
4385 : : {
4386 : 0 : const supernode_cluster *c1
4387 : : = *(const supernode_cluster * const *)p1;
4388 : 0 : const supernode_cluster *c2
4389 : : = *(const supernode_cluster * const *)p2;
4390 : 0 : return c1->m_supernode->m_id - c2->m_supernode->m_id;
4391 : : }
4392 : :
4393 : : private:
4394 : : const supernode *m_supernode;
4395 : : auto_vec <exploded_node *> m_enodes;
4396 : : };
4397 : :
4398 : : /* Cluster containing all supernode_cluster instances for one
4399 : : (function, call_string) pair. */
4400 : :
4401 : : class function_call_string_cluster : public exploded_cluster
4402 : : {
4403 : : public:
4404 : 429 : function_call_string_cluster (function *fun, const call_string &cs)
4405 : 429 : : m_fun (fun), m_cs (cs) {}
4406 : :
4407 : 858 : ~function_call_string_cluster ()
4408 : 429 : {
4409 : 429 : for (map_t::iterator iter = m_map.begin ();
4410 : 1716 : iter != m_map.end ();
4411 : 429 : ++iter)
4412 : 429 : delete (*iter).second;
4413 : 858 : }
4414 : :
4415 : 429 : void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
4416 : : {
4417 : 429 : const char *funcname = function_name (m_fun);
4418 : :
4419 : 858 : gv->println ("subgraph \"cluster_function_%s\" {",
4420 : 429 : IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (m_fun->decl)));
4421 : 429 : gv->indent ();
4422 : 429 : gv->write_indent ();
4423 : 429 : gv->print ("label=\"call string: ");
4424 : 429 : m_cs.print (gv->get_pp ());
4425 : 429 : gv->print (" function: %s \";", funcname);
4426 : 429 : gv->print ("\n");
4427 : :
4428 : : /* Dump m_map, sorting it to avoid churn when comparing dumps. */
4429 : 429 : auto_vec<supernode_cluster *> child_clusters (m_map.elements ());
4430 : 429 : for (map_t::iterator iter = m_map.begin ();
4431 : 1716 : iter != m_map.end ();
4432 : 429 : ++iter)
4433 : 429 : child_clusters.quick_push ((*iter).second);
4434 : :
4435 : 429 : child_clusters.qsort (supernode_cluster::cmp_ptr_ptr);
4436 : :
4437 : : unsigned i;
4438 : : supernode_cluster *child_cluster;
4439 : 858 : FOR_EACH_VEC_ELT (child_clusters, i, child_cluster)
4440 : 429 : child_cluster->dump_dot (gv, args);
4441 : :
4442 : : /* Terminate subgraph. */
4443 : 429 : gv->outdent ();
4444 : 429 : gv->println ("}");
4445 : 429 : }
4446 : :
4447 : 429 : void add_node (exploded_node *en) final override
4448 : : {
4449 : 429 : const supernode *supernode = en->get_supernode ();
4450 : 429 : gcc_assert (supernode);
4451 : 429 : supernode_cluster **slot = m_map.get (supernode);
4452 : 429 : if (slot)
4453 : 0 : (*slot)->add_node (en);
4454 : : else
4455 : : {
4456 : 429 : supernode_cluster *child = new supernode_cluster (supernode);
4457 : 429 : m_map.put (supernode, child);
4458 : 429 : child->add_node (en);
4459 : : }
4460 : 429 : }
4461 : :
4462 : : /* Comparator for use by auto_vec<function_call_string_cluster *>. */
4463 : :
4464 : 17691 : static int cmp_ptr_ptr (const void *p1, const void *p2)
4465 : : {
4466 : 17691 : const function_call_string_cluster *c1
4467 : : = *(const function_call_string_cluster * const *)p1;
4468 : 17691 : const function_call_string_cluster *c2
4469 : : = *(const function_call_string_cluster * const *)p2;
4470 : 35382 : if (int cmp_names
4471 : 17691 : = strcmp (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c1->m_fun->decl)),
4472 : 17691 : IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c2->m_fun->decl))))
4473 : : return cmp_names;
4474 : 5009 : return call_string::cmp (c1->m_cs, c2->m_cs);
4475 : : }
4476 : :
4477 : : private:
4478 : : function *m_fun;
4479 : : const call_string &m_cs;
4480 : : typedef ordered_hash_map<const supernode *, supernode_cluster *> map_t;
4481 : : map_t m_map;
4482 : : };
4483 : :
4484 : : /* Keys for root_cluster. */
4485 : :
4486 : : struct function_call_string
4487 : : {
4488 : 429 : function_call_string (function *fun, const call_string *cs)
4489 : 429 : : m_fun (fun), m_cs (cs)
4490 : : {
4491 : 429 : gcc_assert (fun);
4492 : 429 : gcc_assert (cs);
4493 : 429 : }
4494 : :
4495 : : function *m_fun;
4496 : : const call_string *m_cs;
4497 : : };
4498 : :
4499 : : } // namespace ana
4500 : :
4501 : : template <> struct default_hash_traits<function_call_string>
4502 : : : public pod_hash_traits<function_call_string>
4503 : : {
4504 : : static const bool empty_zero_p = false;
4505 : : };
4506 : :
4507 : : template <>
4508 : : inline hashval_t
4509 : 6203 : pod_hash_traits<function_call_string>::hash (value_type v)
4510 : : {
4511 : 6203 : return (pointer_hash <function>::hash (v.m_fun)
4512 : 6203 : ^ pointer_hash <const call_string>::hash (v.m_cs));
4513 : : }
4514 : :
4515 : : template <>
4516 : : inline bool
4517 : 29447 : pod_hash_traits<function_call_string>::equal (const value_type &existing,
4518 : : const value_type &candidate)
4519 : : {
4520 : 29447 : return existing.m_fun == candidate.m_fun && &existing.m_cs == &candidate.m_cs;
4521 : : }
4522 : : template <>
4523 : : inline void
4524 : : pod_hash_traits<function_call_string>::mark_deleted (value_type &v)
4525 : : {
4526 : : v.m_fun = reinterpret_cast<function *> (1);
4527 : : }
4528 : : template <>
4529 : : inline void
4530 : 1932 : pod_hash_traits<function_call_string>::mark_empty (value_type &v)
4531 : : {
4532 : 1932 : v.m_fun = nullptr;
4533 : : }
4534 : : template <>
4535 : : inline bool
4536 : 46956 : pod_hash_traits<function_call_string>::is_deleted (value_type v)
4537 : : {
4538 : 46956 : return v.m_fun == reinterpret_cast<function *> (1);
4539 : : }
4540 : : template <>
4541 : : inline bool
4542 : 103507 : pod_hash_traits<function_call_string>::is_empty (value_type v)
4543 : : {
4544 : 103078 : return v.m_fun == nullptr;
4545 : : }
4546 : :
4547 : : namespace ana {
4548 : :
4549 : : /* Top-level cluster for generating .dot output for exploded graphs,
4550 : : handling the functionless nodes, and grouping the remaining nodes by
4551 : : callstring. */
4552 : :
4553 : : class root_cluster : public exploded_cluster
4554 : : {
4555 : : public:
4556 : 4 : ~root_cluster ()
4557 : 4 : {
4558 : 433 : for (map_t::iterator iter = m_map.begin ();
4559 : 433 : iter != m_map.end ();
4560 : 429 : ++iter)
4561 : 429 : delete (*iter).second;
4562 : 4 : }
4563 : :
4564 : 4 : void dump_dot (graphviz_out *gv, const dump_args_t &args) const final override
4565 : : {
4566 : 4 : int i;
4567 : 4 : exploded_node *enode;
4568 : 8 : FOR_EACH_VEC_ELT (m_functionless_enodes, i, enode)
4569 : 4 : enode->dump_dot (gv, args);
4570 : :
4571 : : /* Dump m_map, sorting it to avoid churn when comparing dumps. */
4572 : 4 : auto_vec<function_call_string_cluster *> child_clusters (m_map.elements ());
4573 : 4 : for (map_t::iterator iter = m_map.begin ();
4574 : 433 : iter != m_map.end ();
4575 : 429 : ++iter)
4576 : 429 : child_clusters.quick_push ((*iter).second);
4577 : :
4578 : 4 : child_clusters.qsort (function_call_string_cluster::cmp_ptr_ptr);
4579 : :
4580 : : function_call_string_cluster *child_cluster;
4581 : 437 : FOR_EACH_VEC_ELT (child_clusters, i, child_cluster)
4582 : 429 : child_cluster->dump_dot (gv, args);
4583 : 4 : }
4584 : :
4585 : 433 : void add_node (exploded_node *en) final override
4586 : : {
4587 : 433 : function *fun = en->get_function ();
4588 : 429 : if (!fun)
4589 : : {
4590 : 4 : m_functionless_enodes.safe_push (en);
4591 : 4 : return;
4592 : : }
4593 : :
4594 : 429 : const call_string &cs = en->get_point ().get_call_string ();
4595 : 429 : function_call_string key (fun, &cs);
4596 : 429 : function_call_string_cluster **slot = m_map.get (key);
4597 : 429 : if (slot)
4598 : 0 : (*slot)->add_node (en);
4599 : : else
4600 : : {
4601 : 429 : function_call_string_cluster *child
4602 : 429 : = new function_call_string_cluster (fun, cs);
4603 : 429 : m_map.put (key, child);
4604 : 429 : child->add_node (en);
4605 : : }
4606 : : }
4607 : :
4608 : : private:
4609 : : typedef hash_map<function_call_string, function_call_string_cluster *> map_t;
4610 : : map_t m_map;
4611 : :
4612 : : /* This should just be the origin exploded_node. */
4613 : : auto_vec <exploded_node *> m_functionless_enodes;
4614 : : };
4615 : :
4616 : : /* Subclass of range_label for use within
4617 : : exploded_graph::dump_exploded_nodes for implementing
4618 : : -fdump-analyzer-exploded-nodes: a label for a specific
4619 : : exploded_node. */
4620 : :
4621 : : class enode_label : public range_label
4622 : : {
4623 : : public:
4624 : 0 : enode_label (const extrinsic_state &ext_state,
4625 : : exploded_node *enode)
4626 : 0 : : m_ext_state (ext_state), m_enode (enode) {}
4627 : :
4628 : 0 : label_text get_text (unsigned) const final override
4629 : : {
4630 : 0 : pretty_printer pp;
4631 : 0 : pp_format_decoder (&pp) = default_tree_printer;
4632 : 0 : m_enode->get_state ().dump_to_pp (m_ext_state, true, false, &pp);
4633 : 0 : return make_label_text (false, "EN: %i: %s",
4634 : 0 : m_enode->m_index, pp_formatted_text (&pp));
4635 : 0 : }
4636 : :
4637 : : private:
4638 : : const extrinsic_state &m_ext_state;
4639 : : exploded_node *m_enode;
4640 : : };
4641 : :
4642 : : /* Postprocessing support for dumping the exploded nodes.
4643 : : Handle -fdump-analyzer-exploded-nodes,
4644 : : -fdump-analyzer-exploded-nodes-2, and the
4645 : : "__analyzer_dump_exploded_nodes" builtin. */
4646 : :
4647 : : void
4648 : 3324 : exploded_graph::dump_exploded_nodes () const
4649 : : {
4650 : : // TODO
4651 : : /* Locate calls to __analyzer_dump_exploded_nodes. */
4652 : : // Print how many egs there are for them?
4653 : : /* Better: log them as we go, and record the exploded nodes
4654 : : in question. */
4655 : :
4656 : : /* Show every enode. */
4657 : :
4658 : : /* Gather them by stmt, so that we can more clearly see the
4659 : : "hotspots" requiring numerous exploded nodes. */
4660 : :
4661 : : /* Alternatively, simply throw them all into one big rich_location
4662 : : and see if the label-printing will sort it out...
4663 : : This requires them all to be in the same source file. */
4664 : :
4665 : 3324 : if (flag_dump_analyzer_exploded_nodes)
4666 : : {
4667 : 0 : auto_timevar tv (TV_ANALYZER_DUMP);
4668 : 0 : gcc_rich_location richloc (UNKNOWN_LOCATION);
4669 : 0 : unsigned i;
4670 : 0 : exploded_node *enode;
4671 : 0 : FOR_EACH_VEC_ELT (m_nodes, i, enode)
4672 : : {
4673 : 0 : location_t loc = enode->get_location ();
4674 : 0 : if (get_pure_location (richloc.get_loc ()) == UNKNOWN_LOCATION)
4675 : 0 : richloc.set_range (0, loc, SHOW_RANGE_WITH_CARET);
4676 : : else
4677 : 0 : richloc.add_range (loc,
4678 : : SHOW_RANGE_WITHOUT_CARET,
4679 : 0 : new enode_label (m_ext_state, enode));
4680 : : }
4681 : 0 : warning_at (&richloc, 0, "%i exploded nodes", m_nodes.length ());
4682 : :
4683 : : /* Repeat the warning without all the labels, so that message is visible
4684 : : (the other one may well have scrolled past the terminal limit). */
4685 : 0 : warning_at (richloc.get_loc (), 0,
4686 : : "%i exploded nodes", m_nodes.length ());
4687 : :
4688 : 0 : if (m_worklist.length () > 0)
4689 : 0 : warning_at (richloc.get_loc (), 0,
4690 : : "worklist still contains %i nodes", m_worklist.length ());
4691 : 0 : }
4692 : :
4693 : : /* Dump the egraph in textual form to a dump file. */
4694 : 3324 : if (flag_dump_analyzer_exploded_nodes_2)
4695 : : {
4696 : 0 : auto_timevar tv (TV_ANALYZER_DUMP);
4697 : 0 : char *filename
4698 : 0 : = concat (dump_base_name, ".eg.txt", nullptr);
4699 : 0 : FILE *outf = fopen (filename, "w");
4700 : 0 : if (!outf)
4701 : 0 : error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
4702 : 0 : free (filename);
4703 : :
4704 : 0 : fprintf (outf, "exploded graph for %s\n", dump_base_name);
4705 : 0 : fprintf (outf, " nodes: %i\n", m_nodes.length ());
4706 : 0 : fprintf (outf, " edges: %i\n", m_edges.length ());
4707 : :
4708 : 0 : unsigned i;
4709 : 0 : exploded_node *enode;
4710 : 0 : FOR_EACH_VEC_ELT (m_nodes, i, enode)
4711 : : {
4712 : 0 : fprintf (outf, "\nEN %i:\n", enode->m_index);
4713 : 0 : enode->dump_succs_and_preds (outf);
4714 : 0 : pretty_printer pp;
4715 : 0 : enode->get_point ().print (&pp, format (true));
4716 : 0 : fprintf (outf, "%s\n", pp_formatted_text (&pp));
4717 : 0 : text_art::dump_to_file (enode->get_state (), outf);
4718 : 0 : }
4719 : :
4720 : 0 : fclose (outf);
4721 : 0 : }
4722 : :
4723 : : /* Dump the egraph in textual form to multiple dump files, one per enode. */
4724 : 3324 : if (flag_dump_analyzer_exploded_nodes_3)
4725 : : {
4726 : 0 : auto_timevar tv (TV_ANALYZER_DUMP);
4727 : :
4728 : 0 : unsigned i;
4729 : 0 : exploded_node *enode;
4730 : 0 : FOR_EACH_VEC_ELT (m_nodes, i, enode)
4731 : : {
4732 : 0 : char *filename
4733 : 0 : = xasprintf ("%s.en-%i.txt", dump_base_name, i);
4734 : 0 : FILE *outf = fopen (filename, "w");
4735 : 0 : if (!outf)
4736 : 0 : error_at (UNKNOWN_LOCATION, "unable to open %qs for writing",
4737 : : filename);
4738 : 0 : free (filename);
4739 : :
4740 : 0 : fprintf (outf, "EN %i:\n", enode->m_index);
4741 : 0 : enode->dump_succs_and_preds (outf);
4742 : 0 : pretty_printer pp;
4743 : 0 : enode->get_point ().print (&pp, format (true));
4744 : 0 : fprintf (outf, "%s\n", pp_formatted_text (&pp));
4745 : 0 : text_art::dump_to_file (enode->get_state (), outf);
4746 : :
4747 : 0 : fclose (outf);
4748 : 0 : }
4749 : 0 : }
4750 : :
4751 : : /* Emit a warning at any call to "__analyzer_dump_exploded_nodes",
4752 : : giving the number of processed exploded nodes at the snode before
4753 : : the call, and the IDs of processed, merger, and worklist enodes.
4754 : :
4755 : : We highlight the count of *processed* enodes since this is of most
4756 : : interest in DejaGnu tests for ensuring that state merger has
4757 : : happened.
4758 : :
4759 : : We don't show the count of merger and worklist enodes, as this is
4760 : : more of an implementation detail of the merging/worklist that we
4761 : : don't want to bake into our expected DejaGnu messages. */
4762 : :
4763 : 3324 : unsigned i;
4764 : 3324 : exploded_node *enode;
4765 : 3324 : hash_set<const gimple *> seen;
4766 : 394821 : FOR_EACH_VEC_ELT (m_nodes, i, enode)
4767 : : {
4768 : 388177 : const supernode *snode = enode->get_supernode ();
4769 : 388177 : if (!snode)
4770 : 3320 : continue;
4771 : 384857 : if (snode->m_succs.length () != 1)
4772 : 43252 : continue;
4773 : 341605 : const superedge *sedge = snode->m_succs[0];
4774 : 341605 : if (!sedge->get_op ())
4775 : 79888 : continue;
4776 : 261717 : const call_and_return_op *op
4777 : 261717 : = sedge->get_op ()->dyn_cast_call_and_return_op ();
4778 : 261717 : if (!op)
4779 : 200215 : continue;
4780 : 61502 : const gcall &call = op->get_gcall ();
4781 : 61502 : if (is_special_named_call_p (call, "__analyzer_dump_exploded_nodes", 1))
4782 : : {
4783 : 1129 : if (seen.contains (&call))
4784 : 444 : continue;
4785 : :
4786 : 685 : auto_vec<exploded_node *> processed_enodes;
4787 : 685 : auto_vec<exploded_node *> merger_enodes;
4788 : 685 : auto_vec<exploded_node *> worklist_enodes;
4789 : : /* This is O(N^2). */
4790 : 685 : unsigned j;
4791 : 685 : exploded_node *other_enode;
4792 : 121420 : FOR_EACH_VEC_ELT (m_nodes, j, other_enode)
4793 : : {
4794 : 120735 : if (other_enode->get_supernode () == snode)
4795 : 1129 : switch (other_enode->get_status ())
4796 : : {
4797 : 0 : default:
4798 : 0 : gcc_unreachable ();
4799 : 0 : case exploded_node::status::worklist:
4800 : 0 : worklist_enodes.safe_push (other_enode);
4801 : 0 : break;
4802 : 1060 : case exploded_node::status::processed:
4803 : 1060 : processed_enodes.safe_push (other_enode);
4804 : 1060 : break;
4805 : 69 : case exploded_node::status::merger:
4806 : 69 : merger_enodes.safe_push (other_enode);
4807 : 69 : break;
4808 : : }
4809 : : }
4810 : :
4811 : 1370 : pretty_printer pp;
4812 : 685 : pp_character (&pp, '[');
4813 : 685 : print_enode_indices (&pp, processed_enodes);
4814 : 685 : if (merger_enodes.length () > 0)
4815 : : {
4816 : 44 : pp_string (&pp, "] merger(s): [");
4817 : 44 : print_enode_indices (&pp, merger_enodes);
4818 : : }
4819 : 685 : if (worklist_enodes.length () > 0)
4820 : : {
4821 : 0 : pp_string (&pp, "] worklist: [");
4822 : 0 : print_enode_indices (&pp, worklist_enodes);
4823 : : }
4824 : 685 : pp_character (&pp, ']');
4825 : :
4826 : 1370 : warning_n (call.location, 0, processed_enodes.length (),
4827 : : "%i processed enode: %s",
4828 : : "%i processed enodes: %s",
4829 : : processed_enodes.length (), pp_formatted_text (&pp));
4830 : 685 : seen.add (&call);
4831 : :
4832 : : /* If the argument is non-zero, then print all of the states
4833 : : of the various enodes. */
4834 : 685 : tree t_arg = fold (gimple_call_arg (&call, 0));
4835 : 685 : if (TREE_CODE (t_arg) != INTEGER_CST)
4836 : : {
4837 : 0 : error_at (snode->m_loc,
4838 : : "integer constant required for arg 1");
4839 : 0 : return;
4840 : : }
4841 : 685 : int i_arg = TREE_INT_CST_LOW (t_arg);
4842 : 685 : if (i_arg)
4843 : : {
4844 : : exploded_node *other_enode;
4845 : 685 : FOR_EACH_VEC_ELT (processed_enodes, j, other_enode)
4846 : : {
4847 : 0 : fprintf (stderr, "%i of %i: EN %i:\n",
4848 : : j + 1, processed_enodes.length (),
4849 : 0 : other_enode->m_index);
4850 : 0 : other_enode->dump_succs_and_preds (stderr);
4851 : : /* Dump state. */
4852 : 0 : other_enode->get_state ().dump (m_ext_state, false);
4853 : : }
4854 : : }
4855 : 685 : }
4856 : : }
4857 : 3324 : }
4858 : :
4859 : : DEBUG_FUNCTION exploded_node *
4860 : 0 : exploded_graph::get_node_by_index (int idx) const
4861 : : {
4862 : 0 : exploded_node *enode = m_nodes[idx];
4863 : 0 : gcc_assert (enode->m_index == idx);
4864 : 0 : return enode;
4865 : : }
4866 : :
4867 : : /* Ensure that there is an exploded_node for a top-level call to FNDECL. */
4868 : :
4869 : : void
4870 : 310 : exploded_graph::on_escaped_function (tree fndecl)
4871 : : {
4872 : 310 : logger * const logger = get_logger ();
4873 : 310 : LOG_FUNC_1 (logger, "%qE", fndecl);
4874 : :
4875 : 310 : cgraph_node *cgnode = cgraph_node::get (fndecl);
4876 : 310 : if (!cgnode)
4877 : : return;
4878 : :
4879 : 310 : function *fun = cgnode->get_fun ();
4880 : 310 : if (!fun)
4881 : : return;
4882 : :
4883 : 306 : if (!gimple_has_body_p (fndecl))
4884 : : return;
4885 : :
4886 : 306 : exploded_node *enode = add_function_entry (*fun);
4887 : 306 : if (logger)
4888 : : {
4889 : 0 : if (enode)
4890 : 0 : logger->log ("created EN %i for %qE entrypoint",
4891 : 0 : enode->m_index, fun->decl);
4892 : : else
4893 : 0 : logger->log ("did not create enode for %qE entrypoint", fun->decl);
4894 : : }
4895 : 310 : }
4896 : :
4897 : : /* Subclass of dot_annotator for implementing
4898 : : DUMP_BASE_NAME.supergraph.N.eg.dot, a post-analysis dump of the supergraph.
4899 : :
4900 : : Annotate the supergraph nodes by printing the exploded nodes in concise
4901 : : form within them, colorizing the exploded nodes based on sm-state.
4902 : : Also show saved diagnostics within the exploded nodes, giving information
4903 : : on whether they were feasible, and, if infeasible, where the problem
4904 : : was. */
4905 : :
4906 : 4 : class exploded_graph_annotator : public dot_annotator
4907 : : {
4908 : : public:
4909 : 4 : exploded_graph_annotator (const exploded_graph &eg)
4910 : 4 : : m_eg (eg)
4911 : : {
4912 : : /* Avoid O(N^2) by prepopulating m_enodes_per_snode_id. */
4913 : 390 : for (size_t i = 0; i < eg.get_supergraph ().m_nodes.length (); ++i)
4914 : 191 : m_enodes_per_snode_id.push_back (std::vector<exploded_node *> ());
4915 : : exploded_node *enode;
4916 : : unsigned i;
4917 : 437 : FOR_EACH_VEC_ELT (m_eg.m_nodes, i, enode)
4918 : 433 : if (enode->get_supernode ())
4919 : 429 : m_enodes_per_snode_id[enode->get_supernode ()->m_id].push_back (enode);
4920 : 4 : }
4921 : :
4922 : : /* Show exploded nodes for N. */
4923 : 191 : void add_node_annotations (graphviz_out *gv, const supernode &n)
4924 : : const final override
4925 : : {
4926 : 191 : gv->begin_tr ();
4927 : 191 : pretty_printer *pp = gv->get_pp ();
4928 : :
4929 : 191 : if (m_enodes_per_snode_id[n.m_id].empty ())
4930 : 4 : pp_string (pp, "<TD BGCOLOR=\"red\">UNREACHED</TD>");
4931 : : else
4932 : : {
4933 : : /* Adding an empty TD here makes the actual enodes
4934 : : be right-aligned and tightly packed, greatly
4935 : : improving the readability of the graph. */
4936 : 187 : pp_string (pp, "<TD></TD>");
4937 : 616 : for (auto enode : m_enodes_per_snode_id[n.m_id])
4938 : : {
4939 : 429 : gcc_assert (enode->get_supernode () == &n);
4940 : 429 : print_enode (gv, enode);
4941 : : }
4942 : : }
4943 : :
4944 : 191 : pp_flush (pp);
4945 : 191 : gv->end_tr ();
4946 : 191 : }
4947 : :
4948 : : void
4949 : 4 : add_extra_objects (graphviz_out *gv) const final override
4950 : : {
4951 : 4 : pretty_printer *pp = gv->get_pp ();
4952 : :
4953 : 4 : pp_string (pp, "en_0 [shape=none,margin=0,style=filled,label=<<TABLE><TR>");
4954 : 4 : print_enode (gv, m_eg.m_nodes[0]);
4955 : 4 : pp_string (pp, "</TR></TABLE>>];\n\n");
4956 : 4 : pp_flush (pp);
4957 : :
4958 : 4 : unsigned i;
4959 : 4 : exploded_edge *eedge;
4960 : 449 : FOR_EACH_VEC_ELT (m_eg.m_edges, i, eedge)
4961 : : {
4962 : 445 : print_enode_port (pp, *eedge->m_src, "s");
4963 : 445 : pp_string (pp, " -> ");
4964 : 445 : print_enode_port (pp, *eedge->m_dest, "n");
4965 : 445 : dot::attr_list attrs;
4966 : 445 : attrs.add (dot::id ("style"), dot::id ("dotted"));
4967 : 445 : if (eedge->m_custom_info)
4968 : : {
4969 : 22 : pretty_printer info_pp;
4970 : 22 : pp_format_decoder (&info_pp) = default_tree_printer;
4971 : 22 : eedge->m_custom_info->print (&info_pp);
4972 : 44 : attrs.add (dot::id ("label"),
4973 : 44 : dot::id (pp_formatted_text (&info_pp)));
4974 : 22 : }
4975 : 445 : dot::writer w (*pp);
4976 : 445 : attrs.print (w);
4977 : 445 : pp_newline (pp);
4978 : 445 : }
4979 : 4 : }
4980 : :
4981 : : private:
4982 : : void
4983 : 890 : print_enode_port (pretty_printer *pp,
4984 : : const exploded_node &enode,
4985 : : const char *compass_pt) const
4986 : : {
4987 : 890 : if (const supernode *snode = enode.get_supernode ())
4988 : 878 : pp_printf (pp, "node_%i:en_%i:%s",
4989 : 878 : snode->m_id, enode.m_index, compass_pt);
4990 : : else
4991 : 12 : pp_printf (pp, "en_%i:%s",
4992 : 12 : enode.m_index, compass_pt);
4993 : 890 : }
4994 : :
4995 : : /* Concisely print a TD element for ENODE, showing the index, status,
4996 : : and any saved_diagnostics at the enode. Colorize it to show sm-state.
4997 : :
4998 : : Ideally we'd dump ENODE's state here, hidden behind some kind of
4999 : : interactive disclosure method like a tooltip, so that the states
5000 : : can be explored without overwhelming the graph.
5001 : : However, I wasn't able to get graphviz/xdot to show tooltips on
5002 : : individual elements within a HTML-like label. */
5003 : 433 : void print_enode (graphviz_out *gv, const exploded_node *enode) const
5004 : : {
5005 : 433 : pretty_printer *pp = gv->get_pp ();
5006 : 433 : pp_printf (pp, "<TD BGCOLOR=\"%s\">",
5007 : : enode->get_dot_fillcolor ());
5008 : 433 : pp_printf (pp, "<TABLE BORDER=\"0\" PORT=\"en_%i\">", enode->m_index);
5009 : 433 : gv->begin_trtd ();
5010 : 433 : pp_printf (pp, "EN: %i", enode->m_index);
5011 : 433 : switch (enode->get_status ())
5012 : : {
5013 : 0 : default:
5014 : 0 : gcc_unreachable ();
5015 : 0 : case exploded_node::status::worklist:
5016 : 0 : pp_string (pp, "(W)");
5017 : 0 : break;
5018 : : case exploded_node::status::processed:
5019 : : break;
5020 : 6 : case exploded_node::status::special:
5021 : 6 : pp_string (pp, "(S)");
5022 : 6 : break;
5023 : 12 : case exploded_node::status::merger:
5024 : 12 : pp_string (pp, "(M)");
5025 : 12 : break;
5026 : 0 : case exploded_node::status::bulk_merged:
5027 : 0 : pp_string (pp, "(BM)");
5028 : 0 : break;
5029 : : }
5030 : 433 : gv->end_tdtr ();
5031 : :
5032 : : /* Dump any saved_diagnostics at this enode. */
5033 : 437 : for (unsigned i = 0; i < enode->get_num_diagnostics (); i++)
5034 : : {
5035 : 4 : const saved_diagnostic *sd = enode->get_saved_diagnostic (i);
5036 : 4 : print_saved_diagnostic (gv, sd);
5037 : : }
5038 : 433 : pp_printf (pp, "</TABLE>");
5039 : 433 : pp_printf (pp, "</TD>");
5040 : 433 : }
5041 : :
5042 : : /* Print a TABLE element for SD, showing the kind, the length of the
5043 : : exploded_path, whether the path was feasible, and if infeasible,
5044 : : what the problem was. */
5045 : 4 : void print_saved_diagnostic (graphviz_out *gv,
5046 : : const saved_diagnostic *sd) const
5047 : : {
5048 : 4 : pretty_printer *pp = gv->get_pp ();
5049 : 4 : gv->begin_trtd ();
5050 : 4 : pp_printf (pp, "<TABLE BORDER=\"0\">");
5051 : 4 : gv->begin_tr ();
5052 : 4 : pp_string (pp, "<TD BGCOLOR=\"green\">");
5053 : 4 : pp_printf (pp, "DIAGNOSTIC: %s", sd->m_d->get_kind ());
5054 : 4 : gv->end_tdtr ();
5055 : 4 : gv->begin_trtd ();
5056 : 4 : if (sd->get_best_epath ())
5057 : 4 : pp_printf (pp, "epath length: %i", sd->get_epath_length ());
5058 : : else
5059 : 0 : pp_printf (pp, "no best epath");
5060 : 4 : gv->end_tdtr ();
5061 : 4 : if (const feasibility_problem *p = sd->get_feasibility_problem ())
5062 : : {
5063 : 0 : gv->begin_trtd ();
5064 : 0 : pp_printf (pp, "INFEASIBLE at eedge %i: EN:%i -> EN:%i",
5065 : 0 : p->m_eedge_idx,
5066 : 0 : p->m_eedge.m_src->m_index,
5067 : 0 : p->m_eedge.m_dest->m_index);
5068 : 0 : pp_write_text_as_html_like_dot_to_stream (pp);
5069 : 0 : gv->end_tdtr ();
5070 : 0 : gv->begin_trtd ();
5071 : 0 : p->m_eedge.m_sedge->dump (pp);
5072 : 0 : pp_write_text_as_html_like_dot_to_stream (pp);
5073 : 0 : gv->end_tdtr ();
5074 : : /* Ideally we'd print p->m_model here; see the notes above about
5075 : : tooltips. */
5076 : : }
5077 : 4 : pp_printf (pp, "</TABLE>");
5078 : 4 : gv->end_tdtr ();
5079 : 4 : }
5080 : :
5081 : : const exploded_graph &m_eg;
5082 : : std::vector<std::vector <exploded_node *> > m_enodes_per_snode_id;
5083 : : };
5084 : :
5085 : : /* Implement -fdump-analyzer-json. */
5086 : :
5087 : : static void
5088 : 0 : dump_analyzer_json (const supergraph &sg,
5089 : : const exploded_graph &eg)
5090 : : {
5091 : 0 : auto_timevar tv (TV_ANALYZER_DUMP);
5092 : 0 : char *filename = concat (dump_base_name, ".analyzer.json.gz", nullptr);
5093 : 0 : gzFile output = gzopen (filename, "w");
5094 : 0 : if (!output)
5095 : : {
5096 : 0 : error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename);
5097 : 0 : free (filename);
5098 : 0 : return;
5099 : : }
5100 : :
5101 : 0 : auto toplev_obj = std::make_unique<json::object> ();
5102 : 0 : toplev_obj->set ("sgraph", sg.to_json ());
5103 : 0 : toplev_obj->set ("egraph", eg.to_json ());
5104 : :
5105 : 0 : pretty_printer pp;
5106 : 0 : toplev_obj->print (&pp, flag_diagnostics_json_formatting);
5107 : 0 : pp_formatted_text (&pp);
5108 : :
5109 : 0 : if (gzputs (output, pp_formatted_text (&pp)) == EOF
5110 : 0 : || gzclose (output))
5111 : 0 : error_at (UNKNOWN_LOCATION, "error writing %qs", filename);
5112 : :
5113 : 0 : free (filename);
5114 : 0 : }
5115 : :
5116 : : /* Concrete subclass of on_ana_init, allowing plugins to register
5117 : : new state machines. */
5118 : :
5119 : : class impl_on_ana_init : public gcc::topics::analyzer_events::on_ana_init
5120 : : {
5121 : : public:
5122 : 38 : impl_on_ana_init (std::vector<std::unique_ptr<state_machine>> &checkers,
5123 : : known_function_manager &known_fn_mgr,
5124 : : logger *logger)
5125 : 38 : : m_checkers (checkers),
5126 : 38 : m_known_fn_mgr (known_fn_mgr),
5127 : 38 : m_logger (logger)
5128 : : {}
5129 : :
5130 : : void
5131 : 1 : register_state_machine (std::unique_ptr<state_machine> sm)
5132 : : const final override
5133 : : {
5134 : 1 : LOG_SCOPE (m_logger);
5135 : 1 : m_checkers.push_back (std::move (sm));
5136 : 1 : }
5137 : :
5138 : : void
5139 : 107 : register_known_function (const char *name,
5140 : : std::unique_ptr<known_function> kf)
5141 : : const final override
5142 : : {
5143 : 107 : LOG_SCOPE (m_logger);
5144 : 107 : m_known_fn_mgr.add (name, std::move (kf));
5145 : 107 : }
5146 : :
5147 : : logger *
5148 : 39 : get_logger () const final override
5149 : : {
5150 : 39 : return m_logger;
5151 : : }
5152 : :
5153 : : private:
5154 : : std::vector<std::unique_ptr<state_machine>> &m_checkers;
5155 : : known_function_manager &m_known_fn_mgr;
5156 : : logger *m_logger;
5157 : : };
5158 : :
5159 : : static void
5160 : 13300 : maybe_dump_supergraph (const supergraph &sg, const char *name,
5161 : : const dot_annotator *annotator = nullptr,
5162 : : const exploded_graph *eg = nullptr)
5163 : : {
5164 : 13300 : static int dump_idx = 0;
5165 : 13300 : if (!flag_dump_analyzer_supergraph)
5166 : 13280 : return;
5167 : :
5168 : 20 : auto_timevar tv (TV_ANALYZER_DUMP);
5169 : 20 : std::string filename (dump_base_name);
5170 : 20 : filename += ".supergraph.";
5171 : 40 : filename += std::to_string (dump_idx++);
5172 : 20 : filename += ".";
5173 : 20 : filename += name;
5174 : 20 : filename += ".dot";
5175 : 20 : supergraph::dump_args_t args
5176 : : ((enum supergraph_dot_flags)SUPERGRAPH_DOT_SHOW_BBS,
5177 : : annotator,
5178 : 20 : eg);
5179 : 20 : sg.dump_dot (filename.c_str (), args);
5180 : 20 : }
5181 : :
5182 : : /* Run the analysis "engine". */
5183 : :
5184 : : void
5185 : 3324 : impl_run_checkers (logger *logger)
5186 : : {
5187 : 3324 : LOG_SCOPE (logger);
5188 : :
5189 : 3324 : if (logger)
5190 : : {
5191 : 2 : logger->log ("BITS_BIG_ENDIAN: %i", BITS_BIG_ENDIAN ? 1 : 0);
5192 : 2 : logger->log ("BYTES_BIG_ENDIAN: %i", BYTES_BIG_ENDIAN ? 1 : 0);
5193 : 2 : logger->log ("WORDS_BIG_ENDIAN: %i", WORDS_BIG_ENDIAN ? 1 : 0);
5194 : 2 : log_stashed_constants (logger);
5195 : : }
5196 : :
5197 : : /* If using LTO, ensure that the cgraph nodes have function bodies. */
5198 : 3324 : cgraph_node *node;
5199 : 13456 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
5200 : 10132 : node->get_untransformed_body ();
5201 : :
5202 : 3324 : region_model_manager mgr;
5203 : :
5204 : : /* Create the supergraph. */
5205 : 3324 : supergraph sg (mgr, logger);
5206 : :
5207 : 3324 : maybe_dump_supergraph (sg, "original");
5208 : :
5209 : 3324 : sg.fixup_locations (logger);
5210 : :
5211 : 3324 : maybe_dump_supergraph (sg, "fixup-locations");
5212 : :
5213 : 3324 : engine eng (mgr, &sg);
5214 : :
5215 : 3324 : state_purge_map *purge_map = nullptr;
5216 : 3324 : if (flag_analyzer_state_purge)
5217 : 3316 : purge_map = new state_purge_map (sg, eng.get_model_manager (), logger);
5218 : :
5219 : 3324 : if (flag_analyzer_simplify_supergraph)
5220 : : {
5221 : 3324 : sg.simplify (logger);
5222 : 3324 : maybe_dump_supergraph (sg, "simplified");
5223 : : }
5224 : :
5225 : 3324 : sg.sort_nodes (logger);
5226 : 3324 : maybe_dump_supergraph (sg, "sorted");
5227 : :
5228 : 3324 : if (flag_dump_analyzer_state_purge)
5229 : : {
5230 : 4 : auto_timevar tv (TV_ANALYZER_DUMP);
5231 : 4 : state_purge_annotator a (purge_map);
5232 : 4 : char *filename = concat (dump_base_name, ".state-purge.dot", nullptr);
5233 : 4 : supergraph::dump_args_t args ((enum supergraph_dot_flags)0, &a, nullptr);
5234 : 4 : sg.dump_dot (filename, args);
5235 : 4 : free (filename);
5236 : 4 : }
5237 : :
5238 : 3324 : auto checkers = make_checkers (logger);
5239 : :
5240 : 3324 : register_known_functions (*eng.get_known_function_manager (),
5241 : 3324 : *eng.get_model_manager ());
5242 : :
5243 : 3324 : if (auto channel
5244 : 3324 : = g->get_channels ().analyzer_events_channel.get_if_active ())
5245 : 38 : channel->publish (impl_on_ana_init (checkers,
5246 : 38 : *eng.get_known_function_manager (),
5247 : 38 : logger));
5248 : :
5249 : 3324 : if (logger)
5250 : : {
5251 : 2 : int i = 0;
5252 : 16 : for (auto &sm : checkers)
5253 : 14 : logger->log ("checkers[%i]: %s", ++i, sm->get_name ());
5254 : : }
5255 : :
5256 : : /* Extrinsic state shared by nodes in the graph. */
5257 : 3324 : const extrinsic_state ext_state (std::move (checkers), &eng, logger);
5258 : :
5259 : 3324 : const analysis_plan plan (sg, logger);
5260 : :
5261 : : /* The exploded graph. */
5262 : 3324 : exploded_graph eg (sg, logger, ext_state, purge_map, plan,
5263 : 3324 : analyzer_verbosity);
5264 : :
5265 : : /* Add entrypoints to the graph for externally-callable functions. */
5266 : 3324 : eg.build_initial_worklist ();
5267 : :
5268 : : /* Now process the worklist, exploring the <point, state> graph. */
5269 : 3324 : eg.process_worklist ();
5270 : :
5271 : 3324 : if (warn_analyzer_infinite_loop)
5272 : 3324 : eg.detect_infinite_loops ();
5273 : :
5274 : 3324 : if (flag_dump_analyzer_exploded_graph)
5275 : : {
5276 : 4 : auto_timevar tv (TV_ANALYZER_DUMP);
5277 : 4 : char *filename
5278 : 4 : = concat (dump_base_name, ".eg.dot", nullptr);
5279 : 4 : exploded_graph::dump_args_t args (eg);
5280 : 4 : root_cluster c;
5281 : 4 : eg.dump_dot (filename, &c, args);
5282 : 4 : free (filename);
5283 : 4 : }
5284 : :
5285 : : /* Now emit any saved diagnostics. */
5286 : 3324 : eg.get_diagnostic_manager ().emit_saved_diagnostics (eg);
5287 : :
5288 : 3324 : eg.dump_exploded_nodes ();
5289 : :
5290 : 3324 : eg.log_stats ();
5291 : :
5292 : 3324 : if (flag_dump_analyzer_supergraph)
5293 : : {
5294 : : /* Dump post-analysis form of supergraph. */
5295 : 4 : exploded_graph_annotator a (eg);
5296 : 4 : maybe_dump_supergraph (sg, "eg", &a, &eg);
5297 : 4 : }
5298 : :
5299 : 3324 : if (flag_dump_analyzer_json)
5300 : 0 : dump_analyzer_json (sg, eg);
5301 : :
5302 : 3324 : if (flag_dump_analyzer_untracked)
5303 : 23 : eng.get_model_manager ()->dump_untracked_regions ();
5304 : :
5305 : 3324 : delete purge_map;
5306 : :
5307 : : /* Free up any dominance info that we may have created. */
5308 : 13456 : FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
5309 : : {
5310 : 10132 : function *fun = node->get_fun ();
5311 : 10132 : free_dominance_info (fun, CDI_DOMINATORS);
5312 : : }
5313 : 3324 : }
5314 : :
5315 : : /* Handle -fdump-analyzer and -fdump-analyzer-stderr. */
5316 : : static FILE *dump_fout = nullptr;
5317 : :
5318 : : /* Track if we're responsible for closing dump_fout. */
5319 : : static bool owns_dump_fout = false;
5320 : :
5321 : : /* If dumping is enabled, attempt to create dump_fout if it hasn't already
5322 : : been opened. Return it. */
5323 : :
5324 : : FILE *
5325 : 6690 : get_or_create_any_logfile ()
5326 : : {
5327 : 6690 : if (!dump_fout)
5328 : : {
5329 : 6688 : if (flag_dump_analyzer_stderr)
5330 : 0 : dump_fout = stderr;
5331 : 6688 : else if (flag_dump_analyzer)
5332 : : {
5333 : 2 : char *dump_filename = concat (dump_base_name, ".analyzer.txt", nullptr);
5334 : 2 : dump_fout = fopen (dump_filename, "w");
5335 : 2 : free (dump_filename);
5336 : 2 : if (dump_fout)
5337 : 2 : owns_dump_fout = true;
5338 : : }
5339 : : }
5340 : 6690 : return dump_fout;
5341 : : }
5342 : :
5343 : : /* External entrypoint to the analysis "engine".
5344 : : Set up any dumps, then call impl_run_checkers. */
5345 : :
5346 : : void
5347 : 3324 : run_checkers ()
5348 : : {
5349 : : /* Save input_location. */
5350 : 3324 : location_t saved_input_location = input_location;
5351 : :
5352 : 3324 : {
5353 : 3324 : log_user the_logger (nullptr);
5354 : 3324 : get_or_create_any_logfile ();
5355 : 3324 : if (dump_fout)
5356 : 2 : the_logger.set_logger (new logger (dump_fout, 0, 0,
5357 : 2 : *global_dc->get_reference_printer ()));
5358 : 3324 : LOG_SCOPE (the_logger.get_logger ());
5359 : :
5360 : 3324 : impl_run_checkers (the_logger.get_logger ());
5361 : :
5362 : : /* end of lifetime of the_logger (so that dump file is closed after the
5363 : : various dtors run). */
5364 : 3324 : }
5365 : :
5366 : 3324 : if (owns_dump_fout)
5367 : : {
5368 : 2 : fclose (dump_fout);
5369 : 2 : owns_dump_fout = false;
5370 : 2 : dump_fout = nullptr;
5371 : : }
5372 : :
5373 : : /* Restore input_location. Subsequent passes may assume that input_location
5374 : : is some arbitrary value *not* in the block tree, which might be violated
5375 : : if we didn't restore it. */
5376 : 3324 : input_location = saved_input_location;
5377 : 3324 : }
5378 : :
5379 : : } // namespace ana
5380 : :
5381 : : #endif /* #if ENABLE_ANALYZER */
|
