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