1 /* The analysis "engine".
2 Copyright (C) 2019-2020 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
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)
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.
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/>. */
23 #include "coretypes.h"
25 #include "fold-const.h"
26 #include "gcc-rich-location.h"
27 #include "alloc-pool.h"
28 #include "fibonacci_heap.h"
29 #include "shortest-paths.h"
30 #include "diagnostic-core.h"
31 #include "diagnostic-event-id.h"
32 #include "diagnostic-path.h"
34 #include "pretty-print.h"
38 #include "ordered-hash-map.h"
41 #include "analyzer/analyzer.h"
42 #include "analyzer/analyzer-logging.h"
43 #include "analyzer/call-string.h"
44 #include "analyzer/program-point.h"
45 #include "analyzer/store.h"
46 #include "analyzer/region-model.h"
47 #include "analyzer/constraint-manager.h"
48 #include "analyzer/sm.h"
49 #include "analyzer/pending-diagnostic.h"
50 #include "analyzer/diagnostic-manager.h"
52 #include "basic-block.h"
54 #include "gimple-iterator.h"
55 #include "gimple-pretty-print.h"
58 #include "analyzer/supergraph.h"
59 #include "analyzer/program-state.h"
60 #include "analyzer/exploded-graph.h"
61 #include "analyzer/analysis-plan.h"
62 #include "analyzer/checker-path.h"
63 #include "analyzer/state-purge.h"
64 #include "analyzer/bar-chart.h"
68 /* For an overview, see gcc/doc/analyzer.texi. */
74 /* class impl_region_model_context : public region_model_context. */
76 impl_region_model_context::
77 impl_region_model_context (exploded_graph
&eg
,
78 const exploded_node
*enode_for_diag
,
79 const program_state
*old_state
,
80 program_state
*new_state
,
82 stmt_finder
*stmt_finder
)
83 : m_eg (&eg
), m_logger (eg
.get_logger ()),
84 m_enode_for_diag (enode_for_diag
),
85 m_old_state (old_state
),
86 m_new_state (new_state
),
88 m_stmt_finder (stmt_finder
),
89 m_ext_state (eg
.get_ext_state ())
93 impl_region_model_context::
94 impl_region_model_context (program_state
*state
,
95 const extrinsic_state
&ext_state
,
97 : m_eg (NULL
), m_logger (logger
), m_enode_for_diag (NULL
),
101 m_stmt_finder (NULL
),
102 m_ext_state (ext_state
)
107 impl_region_model_context::warn (pending_diagnostic
*d
)
109 LOG_FUNC (get_logger ());
111 m_eg
->get_diagnostic_manager ().add_diagnostic
112 (m_enode_for_diag
, m_enode_for_diag
->get_supernode (),
113 m_stmt
, m_stmt_finder
, d
);
117 impl_region_model_context::on_svalue_leak (const svalue
*sval
)
122 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
123 smap
->on_svalue_leak (sval
, this);
127 impl_region_model_context::
128 on_liveness_change (const svalue_set
&live_svalues
,
129 const region_model
*model
)
133 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
134 smap
->on_liveness_change (live_svalues
, model
, this);
138 impl_region_model_context::on_unknown_change (const svalue
*sval
,
143 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
144 smap
->on_unknown_change (sval
, is_mutable
, m_ext_state
);
148 impl_region_model_context::on_escaped_function (tree fndecl
)
150 m_eg
->on_escaped_function (fndecl
);
153 /* struct setjmp_record. */
156 setjmp_record::cmp (const setjmp_record
&rec1
, const setjmp_record
&rec2
)
158 if (int cmp_enode
= rec1
.m_enode
->m_index
- rec2
.m_enode
->m_index
)
160 gcc_assert (&rec1
== &rec2
);
164 /* class setjmp_svalue : public svalue. */
166 /* Implementation of svalue::accept vfunc for setjmp_svalue. */
169 setjmp_svalue::accept (visitor
*v
) const
171 v
->visit_setjmp_svalue (this);
174 /* Implementation of svalue::dump_to_pp vfunc for setjmp_svalue. */
177 setjmp_svalue::dump_to_pp (pretty_printer
*pp
, bool simple
) const
180 pp_printf (pp
, "SETJMP(EN: %i)", get_enode_index ());
182 pp_printf (pp
, "setjmp_svalue(EN%i)", get_enode_index ());
185 /* Get the index of the stored exploded_node. */
188 setjmp_svalue::get_enode_index () const
190 return m_setjmp_record
.m_enode
->m_index
;
193 /* Concrete implementation of sm_context, wiring it up to the rest of this
196 class impl_sm_context
: public sm_context
199 impl_sm_context (exploded_graph
&eg
,
201 const state_machine
&sm
,
202 const exploded_node
*enode_for_diag
,
203 const program_state
*old_state
,
204 program_state
*new_state
,
205 const sm_state_map
*old_smap
,
206 sm_state_map
*new_smap
,
207 stmt_finder
*stmt_finder
= NULL
)
208 : sm_context (sm_idx
, sm
),
209 m_logger (eg
.get_logger ()),
210 m_eg (eg
), m_enode_for_diag (enode_for_diag
),
211 m_old_state (old_state
), m_new_state (new_state
),
212 m_old_smap (old_smap
), m_new_smap (new_smap
),
213 m_stmt_finder (stmt_finder
)
217 logger
*get_logger () const { return m_logger
.get_logger (); }
219 tree
get_fndecl_for_call (const gcall
*call
) FINAL OVERRIDE
221 impl_region_model_context old_ctxt
222 (m_eg
, m_enode_for_diag
, NULL
, NULL
/*m_enode->get_state ()*/,
224 region_model
*model
= m_new_state
->m_region_model
;
225 return model
->get_fndecl_for_call (call
, &old_ctxt
);
228 state_machine::state_t
get_state (const gimple
*stmt
,
231 logger
* const logger
= get_logger ();
233 impl_region_model_context old_ctxt
234 (m_eg
, m_enode_for_diag
, NULL
, NULL
/*m_enode->get_state ()*/,
236 const svalue
*var_old_sval
237 = m_old_state
->m_region_model
->get_rvalue (var
, &old_ctxt
);
239 state_machine::state_t current
240 = m_old_smap
->get_state (var_old_sval
, m_eg
.get_ext_state ());
244 void set_next_state (const gimple
*stmt
,
246 state_machine::state_t to
,
249 logger
* const logger
= get_logger ();
251 impl_region_model_context old_ctxt
252 (m_eg
, m_enode_for_diag
, NULL
, NULL
/*m_enode->get_state ()*/,
254 const svalue
*var_old_sval
255 = m_old_state
->m_region_model
->get_rvalue (var
, &old_ctxt
);
257 impl_region_model_context
new_ctxt (m_eg
, m_enode_for_diag
,
258 m_old_state
, m_new_state
,
260 const svalue
*var_new_sval
261 = m_new_state
->m_region_model
->get_rvalue (var
, &new_ctxt
);
262 const svalue
*origin_new_sval
263 = m_new_state
->m_region_model
->get_rvalue (origin
, &new_ctxt
);
265 state_machine::state_t current
266 = m_old_smap
->get_state (var_old_sval
, m_eg
.get_ext_state ());
268 logger
->log ("%s: state transition of %qE: %s -> %s",
271 current
->get_name (),
273 m_new_smap
->set_state (m_new_state
->m_region_model
, var_new_sval
,
274 to
, origin_new_sval
, m_eg
.get_ext_state ());
277 void warn (const supernode
*snode
, const gimple
*stmt
,
278 tree var
, pending_diagnostic
*d
) FINAL OVERRIDE
280 LOG_FUNC (get_logger ());
281 gcc_assert (d
); // take ownership
282 impl_region_model_context old_ctxt
283 (m_eg
, m_enode_for_diag
, m_old_state
, m_new_state
, NULL
);
285 const svalue
*var_old_sval
286 = m_old_state
->m_region_model
->get_rvalue (var
, &old_ctxt
);
287 state_machine::state_t current
289 ? m_old_smap
->get_state (var_old_sval
, m_eg
.get_ext_state ())
290 : m_old_smap
->get_global_state ());
291 m_eg
.get_diagnostic_manager ().add_diagnostic
292 (&m_sm
, m_enode_for_diag
, snode
, stmt
, m_stmt_finder
,
293 var
, var_old_sval
, current
, d
);
296 /* Hook for picking more readable trees for SSA names of temporaries,
297 so that rather than e.g.
298 "double-free of '<unknown>'"
300 "double-free of 'inbuf.data'". */
302 tree
get_diagnostic_tree (tree expr
) FINAL OVERRIDE
304 /* Only for SSA_NAMEs of temporaries; otherwise, return EXPR, as it's
305 likely to be the least surprising tree to report. */
306 if (TREE_CODE (expr
) != SSA_NAME
)
308 if (SSA_NAME_VAR (expr
) != NULL
)
311 gcc_assert (m_new_state
);
312 const svalue
*sval
= m_new_state
->m_region_model
->get_rvalue (expr
, NULL
);
313 /* Find trees for all regions storing the value. */
314 if (tree t
= m_new_state
->m_region_model
->get_representative_tree (sval
))
320 state_machine::state_t
get_global_state () const FINAL OVERRIDE
322 return m_old_state
->m_checker_states
[m_sm_idx
]->get_global_state ();
325 void set_global_state (state_machine::state_t state
) FINAL OVERRIDE
327 m_new_state
->m_checker_states
[m_sm_idx
]->set_global_state (state
);
330 void on_custom_transition (custom_transition
*transition
) FINAL OVERRIDE
332 transition
->impl_transition (&m_eg
,
333 const_cast<exploded_node
*> (m_enode_for_diag
),
337 tree
is_zero_assignment (const gimple
*stmt
) FINAL OVERRIDE
339 const gassign
*assign_stmt
= dyn_cast
<const gassign
*> (stmt
);
342 impl_region_model_context old_ctxt
343 (m_eg
, m_enode_for_diag
, m_old_state
, m_new_state
, stmt
);
344 if (const svalue
*sval
345 = m_new_state
->m_region_model
->get_gassign_result (assign_stmt
,
347 if (tree cst
= sval
->maybe_get_constant ())
349 return gimple_assign_lhs (assign_stmt
);
354 exploded_graph
&m_eg
;
355 const exploded_node
*m_enode_for_diag
;
356 const program_state
*m_old_state
;
357 program_state
*m_new_state
;
358 const sm_state_map
*m_old_smap
;
359 sm_state_map
*m_new_smap
;
360 stmt_finder
*m_stmt_finder
;
363 /* Subclass of stmt_finder for finding the best stmt to report the leak at,
364 given the emission path. */
366 class leak_stmt_finder
: public stmt_finder
369 leak_stmt_finder (const exploded_graph
&eg
, tree var
)
370 : m_eg (eg
), m_var (var
) {}
372 stmt_finder
*clone () const FINAL OVERRIDE
374 return new leak_stmt_finder (m_eg
, m_var
);
377 const gimple
*find_stmt (const exploded_path
&epath
)
380 logger
* const logger
= m_eg
.get_logger ();
383 if (m_var
&& TREE_CODE (m_var
) == SSA_NAME
)
385 /* Locate the final write to this SSA name in the path. */
386 const gimple
*def_stmt
= SSA_NAME_DEF_STMT (m_var
);
389 bool found
= epath
.find_stmt_backwards (def_stmt
, &idx_of_def_stmt
);
393 /* What was the next write to the underlying var
394 after the SSA name was set? (if any). */
396 for (unsigned idx
= idx_of_def_stmt
+ 1;
397 idx
< epath
.m_edges
.length ();
400 const exploded_edge
*eedge
= epath
.m_edges
[idx
];
402 logger
->log ("eedge[%i]: EN %i -> EN %i",
404 eedge
->m_src
->m_index
,
405 eedge
->m_dest
->m_index
);
406 const exploded_node
*dst_node
= eedge
->m_dest
;
407 const program_point
&dst_point
= dst_node
->get_point ();
408 const gimple
*stmt
= dst_point
.get_stmt ();
411 if (const gassign
*assign
= dyn_cast
<const gassign
*> (stmt
))
413 tree lhs
= gimple_assign_lhs (assign
);
414 if (TREE_CODE (lhs
) == SSA_NAME
415 && SSA_NAME_VAR (lhs
) == SSA_NAME_VAR (m_var
))
423 /* Look backwards for the first statement with a location. */
425 const exploded_edge
*eedge
;
426 FOR_EACH_VEC_ELT_REVERSE (epath
.m_edges
, i
, eedge
)
429 logger
->log ("eedge[%i]: EN %i -> EN %i",
431 eedge
->m_src
->m_index
,
432 eedge
->m_dest
->m_index
);
433 const exploded_node
*dst_node
= eedge
->m_dest
;
434 const program_point
&dst_point
= dst_node
->get_point ();
435 const gimple
*stmt
= dst_point
.get_stmt ();
437 if (get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
446 const exploded_graph
&m_eg
;
450 /* A measurement of how good EXPR is for presenting to the user, so
451 that e.g. we can say prefer printing
452 "leak of 'tmp.m_ptr'"
454 "leak of '<unknown>'". */
457 readability (const_tree expr
)
460 switch (TREE_CODE (expr
))
464 /* Impose a slight readability penalty relative to that of
466 return readability (TREE_OPERAND (expr
, 0)) - 16;
470 if (tree var
= SSA_NAME_VAR (expr
))
471 /* Slightly favor the underlying var over the SSA name to
472 avoid having them compare equal. */
473 return readability (var
) - 1;
474 /* Avoid printing '<unknown>' for SSA names for temporaries. */
481 if (DECL_NAME (expr
))
482 /* Arbitrarily-chosen "high readability" value. */
485 /* We don't want to print temporaries. For example, the C FE
486 prints them as e.g. "<Uxxxx>" where "xxxx" is the low 16 bits
487 of the tree pointer (see pp_c_tree_decl_identifier). */
491 /* Printing "<return-value>" isn't ideal, but is less awful than
492 trying to print a temporary. */
502 /* A qsort comparator for trees to sort them into most user-readable to
503 least user-readable. */
506 readability_comparator (const void *p1
, const void *p2
)
508 path_var pv1
= *(path_var
const *)p1
;
509 path_var pv2
= *(path_var
const *)p2
;
511 int r1
= readability (pv1
.m_tree
);
512 int r2
= readability (pv2
.m_tree
);
513 if (int cmp
= r2
- r1
)
516 /* Favor items that are deeper on the stack and hence more recent;
517 this also favors locals over globals. */
518 if (int cmp
= pv2
.m_stack_depth
- pv1
.m_stack_depth
)
521 /* Otherwise, if they have the same readability, then impose an
522 arbitrary deterministic ordering on them. */
524 if (int cmp
= TREE_CODE (pv1
.m_tree
) - TREE_CODE (pv2
.m_tree
))
527 switch (TREE_CODE (pv1
.m_tree
))
532 if (int cmp
= (SSA_NAME_VERSION (pv1
.m_tree
)
533 - SSA_NAME_VERSION (pv2
.m_tree
)))
539 if (int cmp
= DECL_UID (pv1
.m_tree
) - DECL_UID (pv2
.m_tree
))
544 /* TODO: We ought to find ways of sorting such cases. */
548 /* Find the best tree for SVAL and call SM's on_leak vfunc with it.
549 If on_leak returns a pending_diagnostic, queue it up to be reported,
550 so that we potentially complain about a leak of SVAL in the given STATE. */
553 impl_region_model_context::on_state_leak (const state_machine
&sm
,
555 state_machine::state_t state
)
557 logger
* const logger
= get_logger ();
561 logger
->start_log_line ();
562 logger
->log_partial ("considering leak of ");
563 sval
->dump_to_pp (logger
->get_printer (), true);
564 logger
->end_log_line ();
570 /* m_old_state also needs to be non-NULL so that the sm_ctxt can look
571 up the old state of SVAL. */
572 gcc_assert (m_old_state
);
574 /* SVAL has leaked within the new state: it is not used by any reachable
576 We need to convert it back to a tree, but since it's likely no regions
577 use it, we have to find the "best" tree for it in the old_state. */
580 = m_old_state
->m_region_model
->get_representative_path_var (sval
,
583 /* This might be NULL; the pending_diagnostic subclasses need to cope
585 tree leaked_tree
= leaked_pv
.m_tree
;
589 logger
->log ("best leaked_tree: %qE", leaked_tree
);
591 logger
->log ("best leaked_tree: NULL");
594 leak_stmt_finder
stmt_finder (*m_eg
, leaked_tree
);
595 gcc_assert (m_enode_for_diag
);
597 /* Don't complain about leaks when returning from "main". */
598 if (m_enode_for_diag
->get_supernode ()
599 && m_enode_for_diag
->get_supernode ()->return_p ())
601 tree fndecl
= m_enode_for_diag
->get_function ()->decl
;
602 if (id_equal (DECL_NAME (fndecl
), "main"))
605 logger
->log ("not reporting leak from main");
610 pending_diagnostic
*pd
= sm
.on_leak (leaked_tree
);
612 m_eg
->get_diagnostic_manager ().add_diagnostic
613 (&sm
, m_enode_for_diag
, m_enode_for_diag
->get_supernode (),
614 m_stmt
, &stmt_finder
,
615 leaked_tree
, sval
, state
, pd
);
618 /* Implementation of region_model_context::on_condition vfunc.
619 Notify all state machines about the condition, which could lead to
620 state transitions. */
623 impl_region_model_context::on_condition (tree lhs
, enum tree_code op
, tree rhs
)
627 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
629 const state_machine
&sm
= m_ext_state
.get_sm (sm_idx
);
630 impl_sm_context
sm_ctxt (*m_eg
, sm_idx
, sm
, m_enode_for_diag
,
631 m_old_state
, m_new_state
,
632 m_old_state
->m_checker_states
[sm_idx
],
633 m_new_state
->m_checker_states
[sm_idx
]);
634 sm
.on_condition (&sm_ctxt
,
635 m_enode_for_diag
->get_supernode (), m_stmt
,
640 /* Implementation of region_model_context::on_phi vfunc.
641 Notify all state machines about the phi, which could lead to
642 state transitions. */
645 impl_region_model_context::on_phi (const gphi
*phi
, tree rhs
)
649 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
651 const state_machine
&sm
= m_ext_state
.get_sm (sm_idx
);
652 impl_sm_context
sm_ctxt (*m_eg
, sm_idx
, sm
, m_enode_for_diag
,
653 m_old_state
, m_new_state
,
654 m_old_state
->m_checker_states
[sm_idx
],
655 m_new_state
->m_checker_states
[sm_idx
]);
656 sm
.on_phi (&sm_ctxt
, m_enode_for_diag
->get_supernode (), phi
, rhs
);
660 /* Implementation of region_model_context::on_unexpected_tree_code vfunc.
661 Mark the new state as being invalid for further exploration.
662 TODO(stage1): introduce a warning for when this occurs. */
665 impl_region_model_context::on_unexpected_tree_code (tree t
,
666 const dump_location_t
&loc
)
668 logger
* const logger
= get_logger ();
670 logger
->log ("unhandled tree code: %qs in %qs at %s:%i",
671 get_tree_code_name (TREE_CODE (t
)),
672 loc
.get_impl_location ().m_function
,
673 loc
.get_impl_location ().m_file
,
674 loc
.get_impl_location ().m_line
);
676 m_new_state
->m_valid
= false;
679 /* struct point_and_state. */
681 /* Assert that this object is sane. */
684 point_and_state::validate (const extrinsic_state
&ext_state
) const
686 /* Skip this in a release build. */
693 m_state
.validate (ext_state
);
695 /* Verify that the callstring's model of the stack corresponds to that
696 of the region_model. */
697 /* They should have the same depth. */
698 gcc_assert (m_point
.get_stack_depth ()
699 == m_state
.m_region_model
->get_stack_depth ());
700 /* Check the functions in the callstring vs those in the frames
702 for (const frame_region
*iter_frame
703 = m_state
.m_region_model
->get_current_frame ();
704 iter_frame
; iter_frame
= iter_frame
->get_calling_frame ())
706 int index
= iter_frame
->get_index ();
707 gcc_assert (m_point
.get_function_at_depth (index
)
708 == iter_frame
->get_function ());
712 /* Subroutine of print_enode_indices: print a run of indices from START_IDX
713 to END_IDX to PP, using and updating *FIRST_RUN. */
716 print_run (pretty_printer
*pp
, int start_idx
, int end_idx
,
720 pp_string (pp
, ", ");
722 if (start_idx
== end_idx
)
723 pp_printf (pp
, "EN: %i", start_idx
);
725 pp_printf (pp
, "EN: %i-%i", start_idx
, end_idx
);
728 /* Print the indices within ENODES to PP, collecting them as
729 runs/singletons e.g. "EN: 4-7, EN: 20-23, EN: 42". */
732 print_enode_indices (pretty_printer
*pp
,
733 const auto_vec
<exploded_node
*> &enodes
)
735 int cur_start_idx
= -1;
736 int cur_finish_idx
= -1;
737 bool first_run
= true;
739 exploded_node
*enode
;
740 FOR_EACH_VEC_ELT (enodes
, i
, enode
)
742 if (cur_start_idx
== -1)
744 gcc_assert (cur_finish_idx
== -1);
745 cur_start_idx
= cur_finish_idx
= enode
->m_index
;
749 if (enode
->m_index
== cur_finish_idx
+ 1)
750 /* Continuation of a run. */
751 cur_finish_idx
= enode
->m_index
;
754 /* Finish existing run, start a new one. */
755 gcc_assert (cur_start_idx
>= 0);
756 gcc_assert (cur_finish_idx
>= 0);
757 print_run (pp
, cur_start_idx
, cur_finish_idx
,
759 cur_start_idx
= cur_finish_idx
= enode
->m_index
;
763 /* Finish any existing run. */
764 if (cur_start_idx
>= 0)
766 gcc_assert (cur_finish_idx
>= 0);
767 print_run (pp
, cur_start_idx
, cur_finish_idx
,
772 /* struct eg_traits::dump_args_t. */
774 /* The <FILENAME>.eg.dot output can quickly become unwieldy if we show
775 full details for all enodes (both in terms of CPU time to render it,
776 and in terms of being meaningful to a human viewing it).
778 If we show just the IDs then the resulting graph is usually viewable,
779 but then we have to keep switching back and forth between the .dot
780 view and other dumps.
782 This function implements a heuristic for showing detail at the enodes
783 that (we hope) matter, and just the ID at other enodes, fixing the CPU
784 usage of the .dot viewer, and drawing the attention of the viewer
787 Return true if ENODE should be shown in detail in .dot output.
788 Return false if no detail should be shown for ENODE. */
791 eg_traits::dump_args_t::show_enode_details_p (const exploded_node
&enode
) const
793 /* If the number of exploded nodes isn't too large, we may as well show
794 all enodes in full detail in the .dot output. */
795 if (m_eg
.m_nodes
.length ()
796 <= (unsigned) param_analyzer_max_enodes_for_full_dump
)
799 /* Otherwise, assume that what's most interesting are state explosions,
800 and thus the places where this happened.
801 Expand enodes at program points where we hit the per-enode limit, so we
802 can investigate what exploded. */
803 const per_program_point_data
*per_point_data
804 = m_eg
.get_per_program_point_data (enode
.get_point ());
805 return per_point_data
->m_excess_enodes
> 0;
808 /* class exploded_node : public dnode<eg_traits>. */
811 exploded_node::status_to_str (enum status s
)
815 default: gcc_unreachable ();
816 case STATUS_WORKLIST
: return "WORKLIST";
817 case STATUS_PROCESSED
: return "PROCESSED";
818 case STATUS_MERGER
: return "MERGER";
819 case STATUS_BULK_MERGED
: return "BULK_MERGED";
823 /* exploded_node's ctor. */
825 exploded_node::exploded_node (const point_and_state
&ps
,
827 : m_ps (ps
), m_status (STATUS_WORKLIST
), m_index (index
),
828 m_num_processed_stmts (0)
830 gcc_checking_assert (ps
.get_state ().m_region_model
->canonicalized_p ());
833 /* Get the stmt that was processed in this enode at index IDX.
834 IDX is an index within the stmts processed at this enode, rather
835 than within those of the supernode. */
838 exploded_node::get_processed_stmt (unsigned idx
) const
840 gcc_assert (idx
< m_num_processed_stmts
);
841 const program_point
&point
= get_point ();
842 gcc_assert (point
.get_kind () == PK_BEFORE_STMT
);
843 const supernode
*snode
= get_supernode ();
844 const unsigned int point_stmt_idx
= point
.get_stmt_idx ();
845 const unsigned int idx_within_snode
= point_stmt_idx
+ idx
;
846 const gimple
*stmt
= snode
->m_stmts
[idx_within_snode
];
850 /* For use by dump_dot, get a value for the .dot "fillcolor" attribute.
851 Colorize by sm-state, to make it easier to see how sm-state propagates
852 through the exploded_graph. */
855 exploded_node::get_dot_fillcolor () const
857 const program_state
&state
= get_state ();
859 /* We want to be able to easily distinguish the no-sm-state case,
860 and to be able to distinguish cases where there's a single state
863 Sum the sm_states, and use the result to choose from a table,
864 modulo table-size, special-casing the "no sm-state" case. */
865 int total_sm_state
= 0;
868 FOR_EACH_VEC_ELT (state
.m_checker_states
, i
, smap
)
870 for (sm_state_map::iterator_t iter
= smap
->begin ();
871 iter
!= smap
->end ();
873 total_sm_state
+= (*iter
).second
.m_state
->get_id ();
874 total_sm_state
+= smap
->get_global_state ()->get_id ();
877 if (total_sm_state
> 0)
879 /* An arbitrarily-picked collection of light colors. */
880 const char * const colors
[]
881 = {"azure", "coral", "cornsilk", "lightblue", "yellow",
882 "honeydew", "lightpink", "lightsalmon", "palegreen1",
883 "wheat", "seashell"};
884 const int num_colors
= sizeof (colors
) / sizeof (colors
[0]);
885 return colors
[total_sm_state
% num_colors
];
892 /* Implementation of dnode::dump_dot vfunc for exploded_node. */
895 exploded_node::dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const
897 pretty_printer
*pp
= gv
->get_pp ();
900 pp_printf (pp
, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
901 get_dot_fillcolor ());
902 pp_write_text_to_stream (pp
);
904 pp_printf (pp
, "EN: %i", m_index
);
905 if (m_status
== STATUS_MERGER
)
906 pp_string (pp
, " (merger)");
907 else if (m_status
== STATUS_BULK_MERGED
)
908 pp_string (pp
, " (bulk merged)");
911 if (args
.show_enode_details_p (*this))
914 m_ps
.get_point ().print (pp
, f
);
917 const extrinsic_state
&ext_state
= args
.m_eg
.get_ext_state ();
918 const program_state
&state
= m_ps
.get_state ();
919 state
.dump_to_pp (ext_state
, false, true, pp
);
922 /* Show any stmts that were processed within this enode,
923 and their index within the supernode. */
924 if (m_num_processed_stmts
> 0)
926 const program_point
&point
= get_point ();
927 gcc_assert (point
.get_kind () == PK_BEFORE_STMT
);
928 const supernode
*snode
= get_supernode ();
929 const unsigned int point_stmt_idx
= point
.get_stmt_idx ();
931 pp_printf (pp
, "stmts: %i", m_num_processed_stmts
);
933 for (unsigned i
= 0; i
< m_num_processed_stmts
; i
++)
935 const unsigned int idx_within_snode
= point_stmt_idx
+ i
;
936 const gimple
*stmt
= snode
->m_stmts
[idx_within_snode
];
937 pp_printf (pp
, " %i: ", idx_within_snode
);
938 pp_gimple_stmt_1 (pp
, stmt
, 0, (dump_flags_t
)0);
944 /* Dump any saved_diagnostics at this enode. */
946 const diagnostic_manager
&dm
= args
.m_eg
.get_diagnostic_manager ();
947 for (unsigned i
= 0; i
< dm
.get_num_diagnostics (); i
++)
949 const saved_diagnostic
*sd
= dm
.get_saved_diagnostic (i
);
950 if (sd
->m_enode
== this)
952 pp_printf (pp
, "DIAGNOSTIC: %s", sd
->m_d
->get_kind ());
958 pp_write_text_as_dot_label_to_stream (pp
, /*for_record=*/true);
960 pp_string (pp
, "\"];\n\n");
964 /* Dump this to PP in a form suitable for use as an id in .dot output. */
967 exploded_node::dump_dot_id (pretty_printer
*pp
) const
969 pp_printf (pp
, "exploded_node_%i", m_index
);
972 /* Dump a multiline representation of this node to PP. */
975 exploded_node::dump_to_pp (pretty_printer
*pp
,
976 const extrinsic_state
&ext_state
) const
978 pp_printf (pp
, "EN: %i", m_index
);
982 m_ps
.get_point ().print (pp
, f
);
985 m_ps
.get_state ().dump_to_pp (ext_state
, false, true, pp
);
989 /* Dump a multiline representation of this node to FILE. */
992 exploded_node::dump (FILE *fp
,
993 const extrinsic_state
&ext_state
) const
996 pp_format_decoder (&pp
) = default_tree_printer
;
997 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
998 pp
.buffer
->stream
= fp
;
999 dump_to_pp (&pp
, ext_state
);
1003 /* Dump a multiline representation of this node to stderr. */
1006 exploded_node::dump (const extrinsic_state
&ext_state
) const
1008 dump (stderr
, ext_state
);
1011 /* Return a new json::object of the form
1012 {"point" : object for program_point,
1013 "state" : object for program_state,
1016 "processed_stmts" : int}. */
1019 exploded_node::to_json (const extrinsic_state
&ext_state
) const
1021 json::object
*enode_obj
= new json::object ();
1023 enode_obj
->set ("point", get_point ().to_json ());
1024 enode_obj
->set ("state", get_state ().to_json (ext_state
));
1025 enode_obj
->set ("status", new json::string (status_to_str (m_status
)));
1026 enode_obj
->set ("idx", new json::integer_number (m_index
));
1027 enode_obj
->set ("processed_stmts",
1028 new json::integer_number (m_num_processed_stmts
));
1035 /* Return true if FNDECL has a gimple body. */
1036 // TODO: is there a pre-canned way to do this?
1039 fndecl_has_gimple_body_p (tree fndecl
)
1041 if (fndecl
== NULL_TREE
)
1044 cgraph_node
*n
= cgraph_node::get (fndecl
);
1048 return n
->has_gimple_body_p ();
1053 /* A pending_diagnostic subclass for implementing "__analyzer_dump_path". */
1055 class dump_path_diagnostic
1056 : public pending_diagnostic_subclass
<dump_path_diagnostic
>
1059 bool emit (rich_location
*richloc
) FINAL OVERRIDE
1061 inform (richloc
, "path");
1065 const char *get_kind () const FINAL OVERRIDE
{ return "dump_path_diagnostic"; }
1067 bool operator== (const dump_path_diagnostic
&) const
1073 /* Modify STATE in place, applying the effects of the stmt at this node's
1076 exploded_node::on_stmt_flags
1077 exploded_node::on_stmt (exploded_graph
&eg
,
1078 const supernode
*snode
,
1080 program_state
*state
) const
1082 logger
*logger
= eg
.get_logger ();
1086 logger
->start_log_line ();
1087 pp_gimple_stmt_1 (logger
->get_printer (), stmt
, 0, (dump_flags_t
)0);
1088 logger
->end_log_line ();
1091 /* Update input_location in case of ICE: make it easier to track down which
1092 source construct we're failing to handle. */
1093 input_location
= stmt
->location
;
1095 gcc_assert (state
->m_region_model
);
1097 /* Preserve the old state. It is used here for looking
1098 up old checker states, for determining state transitions, and
1099 also within impl_region_model_context and impl_sm_context for
1100 going from tree to svalue_id. */
1101 const program_state
old_state (*state
);
1103 impl_region_model_context
ctxt (eg
, this,
1107 bool unknown_side_effects
= false;
1109 switch (gimple_code (stmt
))
1112 /* No-op for now. */
1117 const gassign
*assign
= as_a
<const gassign
*> (stmt
);
1118 state
->m_region_model
->on_assignment (assign
, &ctxt
);
1123 /* No-op for now. */
1128 /* Track whether we have a gcall to a function that's not recognized by
1129 anything, for which we don't have a function body, or for which we
1130 don't know the fndecl. */
1131 const gcall
*call
= as_a
<const gcall
*> (stmt
);
1133 /* Debugging/test support. */
1134 if (is_special_named_call_p (call
, "__analyzer_describe", 2))
1135 state
->m_region_model
->impl_call_analyzer_describe (call
, &ctxt
);
1136 else if (is_special_named_call_p (call
, "__analyzer_dump", 0))
1138 /* Handle the builtin "__analyzer_dump" by dumping state
1140 state
->dump (eg
.get_ext_state (), true);
1142 else if (is_special_named_call_p (call
, "__analyzer_dump_path", 0))
1144 /* Handle the builtin "__analyzer_dump_path" by queuing a
1145 diagnostic at this exploded_node. */
1146 ctxt
.warn (new dump_path_diagnostic ());
1148 else if (is_special_named_call_p (call
, "__analyzer_dump_region_model",
1151 /* Handle the builtin "__analyzer_dump_region_model" by dumping
1152 the region model's state to stderr. */
1153 state
->m_region_model
->dump (false);
1155 else if (is_special_named_call_p (call
, "__analyzer_eval", 1))
1156 state
->m_region_model
->impl_call_analyzer_eval (call
, &ctxt
);
1157 else if (is_special_named_call_p (call
, "__analyzer_break", 0))
1159 /* Handle the builtin "__analyzer_break" by triggering a
1161 /* TODO: is there a good cross-platform way to do this? */
1164 else if (is_special_named_call_p (call
,
1165 "__analyzer_dump_exploded_nodes",
1168 /* This is handled elsewhere. */
1170 else if (is_setjmp_call_p (call
))
1171 state
->m_region_model
->on_setjmp (call
, this, &ctxt
);
1172 else if (is_longjmp_call_p (call
))
1174 on_longjmp (eg
, call
, state
, &ctxt
);
1175 return on_stmt_flags::terminate_path ();
1178 unknown_side_effects
1179 = state
->m_region_model
->on_call_pre (call
, &ctxt
);
1185 const greturn
*return_
= as_a
<const greturn
*> (stmt
);
1186 state
->m_region_model
->on_return (return_
, &ctxt
);
1191 bool any_sm_changes
= false;
1194 FOR_EACH_VEC_ELT (old_state
.m_checker_states
, sm_idx
, smap
)
1196 const state_machine
&sm
= eg
.get_ext_state ().get_sm (sm_idx
);
1197 const sm_state_map
*old_smap
1198 = old_state
.m_checker_states
[sm_idx
];
1199 sm_state_map
*new_smap
= state
->m_checker_states
[sm_idx
];
1200 impl_sm_context
sm_ctxt (eg
, sm_idx
, sm
, this, &old_state
, state
,
1201 old_smap
, new_smap
);
1202 /* Allow the state_machine to handle the stmt. */
1203 if (sm
.on_stmt (&sm_ctxt
, snode
, stmt
))
1204 unknown_side_effects
= false;
1205 if (*old_smap
!= *new_smap
)
1206 any_sm_changes
= true;
1209 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
1210 state
->m_region_model
->on_call_post (call
, unknown_side_effects
, &ctxt
);
1212 return on_stmt_flags (any_sm_changes
);
1215 /* Consider the effect of following superedge SUCC from this node.
1217 Return true if it's feasible to follow the edge, or false
1220 Examples: if it's the "true" branch within
1221 a CFG and we know the conditional is false, we know it's infeasible.
1222 If it's one of multiple interprocedual "return" edges, then only
1223 the edge back to the most recent callsite is feasible.
1225 Update NEXT_STATE accordingly (e.g. to record that a condition was
1226 true or false, or that the NULL-ness of a pointer has been checked,
1227 pushing/popping stack frames, etc).
1229 Update NEXT_POINT accordingly (updating the call string). */
1232 exploded_node::on_edge (exploded_graph
&eg
,
1233 const superedge
*succ
,
1234 program_point
*next_point
,
1235 program_state
*next_state
) const
1237 LOG_FUNC (eg
.get_logger ());
1239 if (!next_point
->on_edge (eg
, succ
))
1242 if (!next_state
->on_edge (eg
, *this, succ
))
1248 /* Verify that the stack at LONGJMP_POINT is still valid, given a call
1249 to "setjmp" at SETJMP_POINT - the stack frame that "setjmp" was
1250 called in must still be valid.
1252 Caveat: this merely checks the call_strings in the points; it doesn't
1253 detect the case where a frame returns and is then called again. */
1256 valid_longjmp_stack_p (const program_point
&longjmp_point
,
1257 const program_point
&setjmp_point
)
1259 const call_string
&cs_at_longjmp
= longjmp_point
.get_call_string ();
1260 const call_string
&cs_at_setjmp
= setjmp_point
.get_call_string ();
1262 if (cs_at_longjmp
.length () < cs_at_setjmp
.length ())
1265 /* Check that the call strings match, up to the depth of the
1267 for (unsigned depth
= 0; depth
< cs_at_setjmp
.length (); depth
++)
1268 if (cs_at_longjmp
[depth
] != cs_at_setjmp
[depth
])
1274 /* A pending_diagnostic subclass for complaining about bad longjmps,
1275 where the enclosing function of the "setjmp" has returned (and thus
1276 the stack frame no longer exists). */
1278 class stale_jmp_buf
: public pending_diagnostic_subclass
<dump_path_diagnostic
>
1281 stale_jmp_buf (const gcall
*setjmp_call
, const gcall
*longjmp_call
,
1282 const program_point
&setjmp_point
)
1283 : m_setjmp_call (setjmp_call
), m_longjmp_call (longjmp_call
),
1284 m_setjmp_point (setjmp_point
), m_stack_pop_event (NULL
)
1287 bool emit (rich_location
*richloc
) FINAL OVERRIDE
1290 (richloc
, OPT_Wanalyzer_stale_setjmp_buffer
,
1291 "%qs called after enclosing function of %qs has returned",
1292 get_user_facing_name (m_longjmp_call
),
1293 get_user_facing_name (m_setjmp_call
));
1296 const char *get_kind () const FINAL OVERRIDE
1297 { return "stale_jmp_buf"; }
1299 bool operator== (const stale_jmp_buf
&other
) const
1301 return (m_setjmp_call
== other
.m_setjmp_call
1302 && m_longjmp_call
== other
.m_longjmp_call
);
1306 maybe_add_custom_events_for_superedge (const exploded_edge
&eedge
,
1307 checker_path
*emission_path
)
1310 /* Detect exactly when the stack first becomes invalid,
1311 and issue an event then. */
1312 if (m_stack_pop_event
)
1314 const exploded_node
*src_node
= eedge
.m_src
;
1315 const program_point
&src_point
= src_node
->get_point ();
1316 const exploded_node
*dst_node
= eedge
.m_dest
;
1317 const program_point
&dst_point
= dst_node
->get_point ();
1318 if (valid_longjmp_stack_p (src_point
, m_setjmp_point
)
1319 && !valid_longjmp_stack_p (dst_point
, m_setjmp_point
))
1321 /* Compare with diagnostic_manager::add_events_for_superedge. */
1322 const int src_stack_depth
= src_point
.get_stack_depth ();
1323 m_stack_pop_event
= new custom_event
1324 (src_point
.get_location (),
1325 src_point
.get_fndecl (),
1327 "stack frame is popped here, invalidating saved environment");
1328 emission_path
->add_event (m_stack_pop_event
);
1334 label_text
describe_final_event (const evdesc::final_event
&ev
)
1336 if (m_stack_pop_event
)
1337 return ev
.formatted_print
1338 ("%qs called after enclosing function of %qs returned at %@",
1339 get_user_facing_name (m_longjmp_call
),
1340 get_user_facing_name (m_setjmp_call
),
1341 m_stack_pop_event
->get_id_ptr ());
1343 return ev
.formatted_print
1344 ("%qs called after enclosing function of %qs has returned",
1345 get_user_facing_name (m_longjmp_call
),
1346 get_user_facing_name (m_setjmp_call
));;
1351 const gcall
*m_setjmp_call
;
1352 const gcall
*m_longjmp_call
;
1353 program_point m_setjmp_point
;
1354 custom_event
*m_stack_pop_event
;
1357 /* Handle LONGJMP_CALL, a call to longjmp or siglongjmp.
1359 Attempt to locate where setjmp/sigsetjmp was called on the jmp_buf and build
1360 an exploded_node and exploded_edge to it representing a rewind to that frame,
1361 handling the various kinds of failure that can occur. */
1364 exploded_node::on_longjmp (exploded_graph
&eg
,
1365 const gcall
*longjmp_call
,
1366 program_state
*new_state
,
1367 region_model_context
*ctxt
) const
1369 tree buf_ptr
= gimple_call_arg (longjmp_call
, 0);
1370 gcc_assert (POINTER_TYPE_P (TREE_TYPE (buf_ptr
)));
1372 region_model
*new_region_model
= new_state
->m_region_model
;
1373 const svalue
*buf_ptr_sval
= new_region_model
->get_rvalue (buf_ptr
, ctxt
);
1374 const region
*buf
= new_region_model
->deref_rvalue (buf_ptr_sval
, buf_ptr
,
1377 const svalue
*buf_content_sval
= new_region_model
->get_store_value (buf
);
1378 const setjmp_svalue
*setjmp_sval
1379 = buf_content_sval
->dyn_cast_setjmp_svalue ();
1383 const setjmp_record tmp_setjmp_record
= setjmp_sval
->get_setjmp_record ();
1385 /* Build a custom enode and eedge for rewinding from the longjmp/siglongjmp
1386 call back to the setjmp/sigsetjmp. */
1387 rewind_info_t
rewind_info (tmp_setjmp_record
, longjmp_call
);
1389 const gcall
*setjmp_call
= rewind_info
.get_setjmp_call ();
1390 const program_point
&setjmp_point
= rewind_info
.get_setjmp_point ();
1392 const program_point
&longjmp_point
= get_point ();
1394 /* Verify that the setjmp's call_stack hasn't been popped. */
1395 if (!valid_longjmp_stack_p (longjmp_point
, setjmp_point
))
1397 ctxt
->warn (new stale_jmp_buf (setjmp_call
, longjmp_call
, setjmp_point
));
1401 gcc_assert (longjmp_point
.get_stack_depth ()
1402 >= setjmp_point
.get_stack_depth ());
1404 /* Update the state for use by the destination node. */
1406 /* Stash the current number of diagnostics so that we can update
1407 any that this adds to show where the longjmp is rewinding to. */
1409 diagnostic_manager
*dm
= &eg
.get_diagnostic_manager ();
1410 unsigned prev_num_diagnostics
= dm
->get_num_diagnostics ();
1412 new_region_model
->on_longjmp (longjmp_call
, setjmp_call
,
1413 setjmp_point
.get_stack_depth (), ctxt
);
1415 /* Detect leaks in the new state relative to the old state. */
1416 program_state::detect_leaks (get_state (), *new_state
, NULL
,
1417 eg
.get_ext_state (), ctxt
);
1419 program_point next_point
1420 = program_point::after_supernode (setjmp_point
.get_supernode (),
1421 setjmp_point
.get_call_string ());
1424 = eg
.get_or_create_node (next_point
, *new_state
, this);
1426 /* Create custom exploded_edge for a longjmp. */
1429 exploded_edge
*eedge
1430 = eg
.add_edge (const_cast<exploded_node
*> (this), next
, NULL
,
1431 new rewind_info_t (tmp_setjmp_record
, longjmp_call
));
1433 /* For any diagnostics that were queued here (such as leaks) we want
1434 the checker_path to show the rewinding events after the "final event"
1435 so that the user sees where the longjmp is rewinding to (otherwise the
1436 path is meaningless).
1438 For example, we want to emit something like:
1440 | NN | longjmp (env, 1);
1441 | | ~~~~~~~~~~~~~~~~
1443 | | (10) 'ptr' leaks here; was allocated at (7)
1444 | | (11) rewinding from 'longjmp' in 'inner'...
1450 | NN | i = setjmp(env);
1453 | | (12) ...to 'setjmp' in 'outer' (saved at (2))
1455 where the "final" event above is event (10), but we want to append
1456 events (11) and (12) afterwards.
1458 Do this by setting m_trailing_eedge on any diagnostics that were
1460 unsigned num_diagnostics
= dm
->get_num_diagnostics ();
1461 for (unsigned i
= prev_num_diagnostics
; i
< num_diagnostics
; i
++)
1463 saved_diagnostic
*sd
= dm
->get_saved_diagnostic (i
);
1464 sd
->m_trailing_eedge
= eedge
;
1469 /* Subroutine of exploded_graph::process_node for finding the successors
1470 of the supernode for a function exit basic block.
1472 Ensure that pop_frame is called, potentially queuing diagnostics about
1476 exploded_node::detect_leaks (exploded_graph
&eg
) const
1478 LOG_FUNC_1 (eg
.get_logger (), "EN: %i", m_index
);
1480 gcc_assert (get_point ().get_supernode ()->return_p ());
1482 /* If we're not a "top-level" function, do nothing; pop_frame
1483 will be called when handling the return superedge. */
1484 if (get_point ().get_stack_depth () > 1)
1487 /* We have a "top-level" function. */
1488 gcc_assert (get_point ().get_stack_depth () == 1);
1490 const program_state
&old_state
= get_state ();
1492 /* Work with a temporary copy of the state: pop the frame, and see
1493 what leaks (via purge_unused_svalues). */
1494 program_state
new_state (old_state
);
1496 gcc_assert (new_state
.m_region_model
);
1498 impl_region_model_context
ctxt (eg
, this,
1499 &old_state
, &new_state
,
1501 const svalue
*result
= NULL
;
1502 new_state
.m_region_model
->pop_frame (NULL
, &result
, &ctxt
);
1503 program_state::detect_leaks (old_state
, new_state
, result
,
1504 eg
.get_ext_state (), &ctxt
);
1507 /* Dump the successors and predecessors of this enode to OUTF. */
1510 exploded_node::dump_succs_and_preds (FILE *outf
) const
1515 auto_vec
<exploded_node
*> preds (m_preds
.length ());
1516 FOR_EACH_VEC_ELT (m_preds
, i
, e
)
1517 preds
.quick_push (e
->m_src
);
1519 print_enode_indices (&pp
, preds
);
1520 fprintf (outf
, "preds: %s\n",
1521 pp_formatted_text (&pp
));
1524 auto_vec
<exploded_node
*> succs (m_succs
.length ());
1525 FOR_EACH_VEC_ELT (m_succs
, i
, e
)
1526 succs
.quick_push (e
->m_dest
);
1528 print_enode_indices (&pp
, succs
);
1529 fprintf (outf
, "succs: %s\n",
1530 pp_formatted_text (&pp
));
1534 /* class rewind_info_t : public exploded_edge::custom_info_t. */
1536 /* Implementation of exploded_edge::custom_info_t::update_model vfunc
1539 Update state for the special-case of a rewind of a longjmp
1540 to a setjmp (which doesn't have a superedge, but does affect
1544 rewind_info_t::update_model (region_model
*model
,
1545 const exploded_edge
&eedge
)
1547 const program_point
&longjmp_point
= eedge
.m_src
->get_point ();
1548 const program_point
&setjmp_point
= eedge
.m_dest
->get_point ();
1550 gcc_assert (longjmp_point
.get_stack_depth ()
1551 >= setjmp_point
.get_stack_depth ());
1553 model
->on_longjmp (get_longjmp_call (),
1555 setjmp_point
.get_stack_depth (), NULL
);
1558 /* Implementation of exploded_edge::custom_info_t::add_events_to_path vfunc
1559 for rewind_info_t. */
1562 rewind_info_t::add_events_to_path (checker_path
*emission_path
,
1563 const exploded_edge
&eedge
)
1565 const exploded_node
*src_node
= eedge
.m_src
;
1566 const program_point
&src_point
= src_node
->get_point ();
1567 const int src_stack_depth
= src_point
.get_stack_depth ();
1568 const exploded_node
*dst_node
= eedge
.m_dest
;
1569 const program_point
&dst_point
= dst_node
->get_point ();
1570 const int dst_stack_depth
= dst_point
.get_stack_depth ();
1572 emission_path
->add_event
1573 (new rewind_from_longjmp_event
1574 (&eedge
, get_longjmp_call ()->location
,
1575 src_point
.get_fndecl (),
1576 src_stack_depth
, this));
1577 emission_path
->add_event
1578 (new rewind_to_setjmp_event
1579 (&eedge
, get_setjmp_call ()->location
,
1580 dst_point
.get_fndecl (),
1581 dst_stack_depth
, this));
1584 /* class exploded_edge : public dedge<eg_traits>. */
1586 /* exploded_edge's ctor. */
1588 exploded_edge::exploded_edge (exploded_node
*src
, exploded_node
*dest
,
1589 const superedge
*sedge
,
1590 custom_info_t
*custom_info
)
1591 : dedge
<eg_traits
> (src
, dest
), m_sedge (sedge
),
1592 m_custom_info (custom_info
)
1596 /* exploded_edge's dtor. */
1598 exploded_edge::~exploded_edge ()
1600 delete m_custom_info
;
1603 /* Implementation of dedge::dump_dot vfunc for exploded_edge.
1604 Use the label of the underlying superedge, if any. */
1607 exploded_edge::dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
1609 pretty_printer
*pp
= gv
->get_pp ();
1611 const char *style
= "\"solid,bold\"";
1612 const char *color
= "black";
1614 const char *constraint
= "true";
1617 switch (m_sedge
->m_kind
)
1621 case SUPEREDGE_CFG_EDGE
:
1623 case SUPEREDGE_CALL
:
1625 //constraint = "false";
1627 case SUPEREDGE_RETURN
:
1629 //constraint = "false";
1631 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
1632 style
= "\"dotted\"";
1638 style
= "\"dotted\"";
1641 m_src
->dump_dot_id (pp
);
1642 pp_string (pp
, " -> ");
1643 m_dest
->dump_dot_id (pp
);
1645 (" [style=%s, color=%s, weight=%d, constraint=%s,"
1647 style
, color
, weight
, constraint
);
1650 m_sedge
->dump_label_to_pp (pp
, false);
1651 else if (m_custom_info
)
1652 m_custom_info
->print (pp
);
1654 //pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
1656 pp_printf (pp
, "\"];\n");
1659 /* Return a new json::object of the form
1660 {"src_idx": int, the index of the source exploded edge,
1661 "dst_idx": int, the index of the destination exploded edge,
1662 "sedge": (optional) object for the superedge, if any,
1663 "custom": (optional) str, a description, if this is a custom edge}. */
1666 exploded_edge::to_json () const
1668 json::object
*eedge_obj
= new json::object ();
1669 eedge_obj
->set ("src_idx", new json::integer_number (m_src
->m_index
));
1670 eedge_obj
->set ("dst_idx", new json::integer_number (m_dest
->m_index
));
1672 eedge_obj
->set ("sedge", m_sedge
->to_json ());
1676 pp_format_decoder (&pp
) = default_tree_printer
;
1677 m_custom_info
->print (&pp
);
1678 eedge_obj
->set ("custom", new json::string (pp_formatted_text (&pp
)));
1687 stats::stats (int num_supernodes
)
1688 : m_node_reuse_count (0),
1689 m_node_reuse_after_merge_count (0),
1690 m_num_supernodes (num_supernodes
)
1692 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
1696 /* Log these stats in multiline form to LOGGER. */
1699 stats::log (logger
*logger
) const
1701 gcc_assert (logger
);
1702 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
1703 if (m_num_nodes
[i
] > 0)
1704 logger
->log ("m_num_nodes[%s]: %i",
1705 point_kind_to_string (static_cast <enum point_kind
> (i
)),
1707 logger
->log ("m_node_reuse_count: %i", m_node_reuse_count
);
1708 logger
->log ("m_node_reuse_after_merge_count: %i",
1709 m_node_reuse_after_merge_count
);
1712 /* Dump these stats in multiline form to OUT. */
1715 stats::dump (FILE *out
) const
1717 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
1718 if (m_num_nodes
[i
] > 0)
1719 fprintf (out
, "m_num_nodes[%s]: %i\n",
1720 point_kind_to_string (static_cast <enum point_kind
> (i
)),
1722 fprintf (out
, "m_node_reuse_count: %i\n", m_node_reuse_count
);
1723 fprintf (out
, "m_node_reuse_after_merge_count: %i\n",
1724 m_node_reuse_after_merge_count
);
1726 if (m_num_supernodes
> 0)
1727 fprintf (out
, "PK_AFTER_SUPERNODE nodes per supernode: %.2f\n",
1728 (float)m_num_nodes
[PK_AFTER_SUPERNODE
] / (float)m_num_supernodes
);
1731 /* Return the total number of enodes recorded within this object. */
1734 stats::get_total_enodes () const
1737 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
1738 result
+= m_num_nodes
[i
];
1742 /* strongly_connected_components's ctor. Tarjan's SCC algorithm. */
1744 strongly_connected_components::
1745 strongly_connected_components (const supergraph
&sg
, logger
*logger
)
1746 : m_sg (sg
), m_per_node (m_sg
.num_nodes ())
1749 auto_timevar
tv (TV_ANALYZER_SCC
);
1751 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
1752 m_per_node
.quick_push (per_node_data ());
1754 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
1755 if (m_per_node
[i
].m_index
== -1)
1762 /* Dump this object to stderr. */
1765 strongly_connected_components::dump () const
1767 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
1769 const per_node_data
&v
= m_per_node
[i
];
1770 fprintf (stderr
, "SN %i: index: %i lowlink: %i on_stack: %i\n",
1771 i
, v
.m_index
, v
.m_lowlink
, v
.m_on_stack
);
1775 /* Subroutine of strongly_connected_components's ctor, part of Tarjan's
1779 strongly_connected_components::strong_connect (unsigned index
)
1781 supernode
*v_snode
= m_sg
.get_node_by_index (index
);
1783 /* Set the depth index for v to the smallest unused index. */
1784 per_node_data
*v
= &m_per_node
[index
];
1786 v
->m_lowlink
= index
;
1787 m_stack
.safe_push (index
);
1788 v
->m_on_stack
= true;
1791 /* Consider successors of v. */
1794 FOR_EACH_VEC_ELT (v_snode
->m_succs
, i
, sedge
)
1796 if (sedge
->get_kind () != SUPEREDGE_CFG_EDGE
1797 && sedge
->get_kind () != SUPEREDGE_INTRAPROCEDURAL_CALL
)
1799 supernode
*w_snode
= sedge
->m_dest
;
1800 per_node_data
*w
= &m_per_node
[w_snode
->m_index
];
1801 if (w
->m_index
== -1)
1803 /* Successor w has not yet been visited; recurse on it. */
1804 strong_connect (w_snode
->m_index
);
1805 v
->m_lowlink
= MIN (v
->m_lowlink
, w
->m_lowlink
);
1807 else if (w
->m_on_stack
)
1809 /* Successor w is in stack S and hence in the current SCC
1810 If w is not on stack, then (v, w) is a cross-edge in the DFS
1811 tree and must be ignored. */
1812 v
->m_lowlink
= MIN (v
->m_lowlink
, w
->m_index
);
1816 /* If v is a root node, pop the stack and generate an SCC. */
1818 if (v
->m_lowlink
== v
->m_index
)
1822 int idx
= m_stack
.pop ();
1823 w
= &m_per_node
[idx
];
1824 w
->m_on_stack
= false;
1829 /* worklist's ctor. */
1831 worklist::worklist (const exploded_graph
&eg
, const analysis_plan
&plan
)
1832 : m_scc (eg
.get_supergraph (), eg
.get_logger ()),
1834 m_queue (key_t (*this, NULL
))
1838 /* Return the number of nodes in the worklist. */
1841 worklist::length () const
1843 return m_queue
.nodes ();
1846 /* Return the next node in the worklist, removing it. */
1849 worklist::take_next ()
1851 return m_queue
.extract_min ();
1854 /* Return the next node in the worklist without removing it. */
1857 worklist::peek_next ()
1859 return m_queue
.min ();
1862 /* Add ENODE to the worklist. */
1865 worklist::add_node (exploded_node
*enode
)
1867 gcc_assert (enode
->get_status () == exploded_node::STATUS_WORKLIST
);
1868 m_queue
.insert (key_t (*this, enode
), enode
);
1871 /* Comparator for implementing worklist::key_t comparison operators.
1872 Return negative if KA is before KB
1873 Return positive if KA is after KB
1874 Return 0 if they are equal.
1876 The ordering of the worklist is critical for performance and for
1877 avoiding node explosions. Ideally we want all enodes at a CFG join-point
1878 with the same callstring to be sorted next to each other in the worklist
1879 so that a run of consecutive enodes can be merged and processed "in bulk"
1880 rather than individually or pairwise, minimizing the number of new enodes
1884 worklist::key_t::cmp (const worklist::key_t
&ka
, const worklist::key_t
&kb
)
1886 const program_point
&point_a
= ka
.m_enode
->get_point ();
1887 const program_point
&point_b
= kb
.m_enode
->get_point ();
1888 const call_string
&call_string_a
= point_a
.get_call_string ();
1889 const call_string
&call_string_b
= point_b
.get_call_string ();
1891 /* Order empty-callstring points with different functions based on the
1892 analysis_plan, so that we generate summaries before they are used. */
1893 if (flag_analyzer_call_summaries
1894 && call_string_a
.empty_p ()
1895 && call_string_b
.empty_p ()
1896 && point_a
.get_function () != NULL
1897 && point_b
.get_function () != NULL
1898 && point_a
.get_function () != point_b
.get_function ())
1900 if (int cmp
= ka
.m_worklist
.m_plan
.cmp_function (point_a
.get_function (),
1901 point_b
.get_function ()))
1905 /* First, order by SCC. */
1906 int scc_id_a
= ka
.get_scc_id (ka
.m_enode
);
1907 int scc_id_b
= kb
.get_scc_id (kb
.m_enode
);
1908 if (scc_id_a
!= scc_id_b
)
1909 return scc_id_a
- scc_id_b
;
1911 /* If in same SCC, order by supernode index (an arbitrary but stable
1913 const supernode
*snode_a
= ka
.m_enode
->get_supernode ();
1914 const supernode
*snode_b
= kb
.m_enode
->get_supernode ();
1915 if (snode_a
== NULL
)
1917 if (snode_b
!= NULL
)
1921 /* Both are NULL. */
1924 if (snode_b
== NULL
)
1927 /* Neither are NULL. */
1928 gcc_assert (snode_a
&& snode_b
);
1929 if (snode_a
->m_index
!= snode_b
->m_index
)
1930 return snode_a
->m_index
- snode_b
->m_index
;
1932 gcc_assert (snode_a
== snode_b
);
1934 /* The points might vary by callstring; try sorting by callstring. */
1935 int cs_cmp
= call_string::cmp (call_string_a
, call_string_b
);
1939 /* Order within supernode via program point. */
1940 int within_snode_cmp
1941 = function_point::cmp_within_supernode (point_a
.get_function_point (),
1942 point_b
.get_function_point ());
1943 if (within_snode_cmp
)
1944 return within_snode_cmp
;
1946 /* Otherwise, we ought to have the same program_point. */
1947 gcc_assert (point_a
== point_b
);
1949 const program_state
&state_a
= ka
.m_enode
->get_state ();
1950 const program_state
&state_b
= kb
.m_enode
->get_state ();
1952 /* Sort by sm-state, so that identical sm-states are grouped
1953 together in the worklist. */
1954 for (unsigned sm_idx
= 0; sm_idx
< state_a
.m_checker_states
.length ();
1957 sm_state_map
*smap_a
= state_a
.m_checker_states
[sm_idx
];
1958 sm_state_map
*smap_b
= state_b
.m_checker_states
[sm_idx
];
1960 if (int smap_cmp
= sm_state_map::cmp (*smap_a
, *smap_b
))
1964 /* Otherwise, we have two enodes at the same program point but with
1965 different states. We don't have a good total ordering on states,
1966 so order them by enode index, so that we have at least have a
1968 return ka
.m_enode
->m_index
- kb
.m_enode
->m_index
;
1971 /* exploded_graph's ctor. */
1973 exploded_graph::exploded_graph (const supergraph
&sg
, logger
*logger
,
1974 const extrinsic_state
&ext_state
,
1975 const state_purge_map
*purge_map
,
1976 const analysis_plan
&plan
,
1978 : m_sg (sg
), m_logger (logger
),
1979 m_worklist (*this, plan
),
1980 m_ext_state (ext_state
),
1981 m_purge_map (purge_map
),
1983 m_diagnostic_manager (logger
, ext_state
.get_engine (), verbosity
),
1984 m_global_stats (m_sg
.num_nodes ()),
1985 m_functionless_stats (m_sg
.num_nodes ()),
1986 m_PK_AFTER_SUPERNODE_per_snode (m_sg
.num_nodes ())
1988 m_origin
= get_or_create_node (program_point::origin (),
1989 program_state (ext_state
), NULL
);
1990 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
1991 m_PK_AFTER_SUPERNODE_per_snode
.quick_push (i
);
1994 /* exploded_graph's dtor. */
1996 exploded_graph::~exploded_graph ()
1998 for (function_stat_map_t::iterator iter
= m_per_function_stats
.begin ();
1999 iter
!= m_per_function_stats
.end ();
2001 delete (*iter
).second
;
2003 for (point_map_t::iterator iter
= m_per_point_data
.begin ();
2004 iter
!= m_per_point_data
.end ();
2006 delete (*iter
).second
;
2009 /* Ensure that there is an exploded_node representing an external call to
2010 FUN, adding it to the worklist if creating it.
2012 Add an edge from the origin exploded_node to the function entrypoint
2015 Return the exploded_node for the entrypoint to the function. */
2018 exploded_graph::add_function_entry (function
*fun
)
2020 gcc_assert (gimple_has_body_p (fun
->decl
));
2022 /* Be idempotent. */
2023 if (m_functions_with_enodes
.contains (fun
))
2025 logger
* const logger
= get_logger ();
2027 logger
->log ("entrypoint for %qE already exists", fun
->decl
);
2031 program_point point
= program_point::from_function_entry (m_sg
, fun
);
2032 program_state
state (m_ext_state
);
2033 state
.push_frame (m_ext_state
, fun
);
2038 exploded_node
*enode
= get_or_create_node (point
, state
, NULL
);
2042 add_edge (m_origin
, enode
, NULL
);
2044 m_functions_with_enodes
.add (fun
);
2049 /* Get or create an exploded_node for (POINT, STATE).
2050 If a new node is created, it is added to the worklist.
2052 Use ENODE_FOR_DIAG, a pre-existing enode, for any diagnostics
2053 that need to be emitted (e.g. when purging state *before* we have
2057 exploded_graph::get_or_create_node (const program_point
&point
,
2058 const program_state
&state
,
2059 const exploded_node
*enode_for_diag
)
2061 logger
* const logger
= get_logger ();
2066 pretty_printer
*pp
= logger
->get_printer ();
2067 logger
->start_log_line ();
2068 pp_string (pp
, "point: ");
2069 point
.print (pp
, f
);
2070 logger
->end_log_line ();
2071 logger
->start_log_line ();
2072 pp_string (pp
, "state: ");
2073 state
.dump_to_pp (m_ext_state
, true, false, pp
);
2074 logger
->end_log_line ();
2077 /* Stop exploring paths for which we don't know how to effectively
2082 logger
->log ("invalid state; not creating node");
2086 auto_cfun
sentinel (point
.get_function ());
2088 state
.validate (get_ext_state ());
2090 //state.dump (get_ext_state ());
2092 /* Prune state to try to improve the chances of a cache hit,
2093 avoiding generating redundant nodes. */
2094 program_state pruned_state
2095 = state
.prune_for_point (*this, point
, enode_for_diag
);
2097 pruned_state
.validate (get_ext_state ());
2099 //pruned_state.dump (get_ext_state ());
2103 pretty_printer
*pp
= logger
->get_printer ();
2104 logger
->start_log_line ();
2105 pp_string (pp
, "pruned_state: ");
2106 pruned_state
.dump_to_pp (m_ext_state
, true, false, pp
);
2107 logger
->end_log_line ();
2108 pruned_state
.m_region_model
->dump_to_pp (logger
->get_printer (), true,
2112 stats
*per_fn_stats
= get_or_create_function_stats (point
.get_function ());
2115 = &get_or_create_per_call_string_data (point
.get_call_string ())->m_stats
;
2117 point_and_state
ps (point
, pruned_state
);
2118 ps
.validate (m_ext_state
);
2119 if (exploded_node
**slot
= m_point_and_state_to_node
.get (&ps
))
2121 /* An exploded_node for PS already exists. */
2123 logger
->log ("reused EN: %i", (*slot
)->m_index
);
2124 m_global_stats
.m_node_reuse_count
++;
2125 per_fn_stats
->m_node_reuse_count
++;
2126 per_cs_stats
->m_node_reuse_count
++;
2130 per_program_point_data
*per_point_data
2131 = get_or_create_per_program_point_data (point
);
2133 /* Consider merging state with another enode at this program_point. */
2134 if (flag_analyzer_state_merge
)
2136 exploded_node
*existing_enode
;
2138 FOR_EACH_VEC_ELT (per_point_data
->m_enodes
, i
, existing_enode
)
2141 logger
->log ("considering merging with existing EN: %i for point",
2142 existing_enode
->m_index
);
2143 gcc_assert (existing_enode
->get_point () == point
);
2144 const program_state
&existing_state
= existing_enode
->get_state ();
2146 /* This merges successfully within the loop. */
2148 program_state
merged_state (m_ext_state
);
2149 if (pruned_state
.can_merge_with_p (existing_state
, point
,
2153 logger
->log ("merging new state with that of EN: %i",
2154 existing_enode
->m_index
);
2156 /* Try again for a cache hit.
2157 Whether we get one or not, merged_state's value_ids have no
2158 relationship to those of the input state, and thus to those
2159 of CHANGE, so we must purge any svalue_ids from *CHANGE. */
2160 ps
.set_state (merged_state
);
2162 if (exploded_node
**slot
= m_point_and_state_to_node
.get (&ps
))
2164 /* An exploded_node for PS already exists. */
2166 logger
->log ("reused EN: %i", (*slot
)->m_index
);
2167 m_global_stats
.m_node_reuse_after_merge_count
++;
2168 per_fn_stats
->m_node_reuse_after_merge_count
++;
2169 per_cs_stats
->m_node_reuse_after_merge_count
++;
2175 logger
->log ("not merging new state with that of EN: %i",
2176 existing_enode
->m_index
);
2180 /* Impose a limit on the number of enodes per program point, and
2181 simply stop if we exceed it. */
2182 if ((int)per_point_data
->m_enodes
.length ()
2183 >= param_analyzer_max_enodes_per_program_point
)
2186 point
.print (&pp
, format (false));
2187 print_enode_indices (&pp
, per_point_data
->m_enodes
);
2189 logger
->log ("not creating enode; too many at program point: %s",
2190 pp_formatted_text (&pp
));
2191 warning_at (point
.get_location (), OPT_Wanalyzer_too_complex
,
2192 "terminating analysis for this program point: %s",
2193 pp_formatted_text (&pp
));
2194 per_point_data
->m_excess_enodes
++;
2198 ps
.validate (m_ext_state
);
2200 /* An exploded_node for "ps" doesn't already exist; create one. */
2201 exploded_node
*node
= new exploded_node (ps
, m_nodes
.length ());
2203 m_point_and_state_to_node
.put (node
->get_ps_key (), node
);
2205 /* Update per-program_point data. */
2206 per_point_data
->m_enodes
.safe_push (node
);
2208 const enum point_kind node_pk
= node
->get_point ().get_kind ();
2209 m_global_stats
.m_num_nodes
[node_pk
]++;
2210 per_fn_stats
->m_num_nodes
[node_pk
]++;
2211 per_cs_stats
->m_num_nodes
[node_pk
]++;
2213 if (node_pk
== PK_AFTER_SUPERNODE
)
2214 m_PK_AFTER_SUPERNODE_per_snode
[point
.get_supernode ()->m_index
]++;
2219 pretty_printer
*pp
= logger
->get_printer ();
2220 logger
->log ("created EN: %i", node
->m_index
);
2221 logger
->start_log_line ();
2222 pp_string (pp
, "point: ");
2223 point
.print (pp
, f
);
2224 logger
->end_log_line ();
2225 logger
->start_log_line ();
2226 pp_string (pp
, "pruned_state: ");
2227 pruned_state
.dump_to_pp (m_ext_state
, true, false, pp
);
2228 logger
->end_log_line ();
2231 /* Add the new node to the worlist. */
2232 m_worklist
.add_node (node
);
2236 /* Add an exploded_edge from SRC to DEST, recording its association
2237 with SEDGE (which may be NULL), and, if non-NULL, taking ownership
2239 Return the newly-created eedge. */
2242 exploded_graph::add_edge (exploded_node
*src
, exploded_node
*dest
,
2243 const superedge
*sedge
,
2244 exploded_edge::custom_info_t
*custom_info
)
2247 get_logger ()->log ("creating edge EN: %i -> EN: %i",
2248 src
->m_index
, dest
->m_index
);
2249 exploded_edge
*e
= new exploded_edge (src
, dest
, sedge
, custom_info
);
2250 digraph
<eg_traits
>::add_edge (e
);
2254 /* Ensure that this graph has per-program_point-data for POINT;
2255 borrow a pointer to it. */
2257 per_program_point_data
*
2259 get_or_create_per_program_point_data (const program_point
&point
)
2261 if (per_program_point_data
**slot
= m_per_point_data
.get (&point
))
2264 per_program_point_data
*per_point_data
= new per_program_point_data (point
);
2265 m_per_point_data
.put (&per_point_data
->m_key
, per_point_data
);
2266 return per_point_data
;
2269 /* Get this graph's per-program-point-data for POINT if there is any,
2272 per_program_point_data
*
2273 exploded_graph::get_per_program_point_data (const program_point
&point
) const
2275 if (per_program_point_data
**slot
2276 = const_cast <point_map_t
&> (m_per_point_data
).get (&point
))
2282 /* Ensure that this graph has per-call_string-data for CS;
2283 borrow a pointer to it. */
2285 per_call_string_data
*
2286 exploded_graph::get_or_create_per_call_string_data (const call_string
&cs
)
2288 if (per_call_string_data
**slot
= m_per_call_string_data
.get (&cs
))
2291 per_call_string_data
*data
= new per_call_string_data (cs
, m_sg
.num_nodes ());
2292 m_per_call_string_data
.put (&data
->m_key
,
2297 /* Ensure that this graph has per-function-data for FUN;
2298 borrow a pointer to it. */
2301 exploded_graph::get_or_create_per_function_data (function
*fun
)
2303 if (per_function_data
**slot
= m_per_function_data
.get (fun
))
2306 per_function_data
*data
= new per_function_data ();
2307 m_per_function_data
.put (fun
, data
);
2311 /* Get this graph's per-function-data for FUN if there is any,
2315 exploded_graph::get_per_function_data (function
*fun
) const
2317 if (per_function_data
**slot
2318 = const_cast <per_function_data_t
&> (m_per_function_data
).get (fun
))
2324 /* Return true if NODE and FUN should be traversed directly, rather than
2325 called via other functions. */
2328 toplevel_function_p (cgraph_node
*node
, function
*fun
, logger
*logger
)
2330 /* TODO: better logic here
2331 e.g. only if more than one caller, and significantly complicated.
2332 Perhaps some whole-callgraph analysis to decide if it's worth summarizing
2333 an edge, and if so, we need summaries. */
2334 if (flag_analyzer_call_summaries
)
2336 int num_call_sites
= 0;
2337 for (cgraph_edge
*edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
2340 /* For now, if there's more than one in-edge, and we want call
2341 summaries, do it at the top level so that there's a chance
2342 we'll have a summary when we need one. */
2343 if (num_call_sites
> 1)
2346 logger
->log ("traversing %qE (%i call sites)",
2347 fun
->decl
, num_call_sites
);
2352 if (!TREE_PUBLIC (fun
->decl
))
2355 logger
->log ("not traversing %qE (static)", fun
->decl
);
2360 logger
->log ("traversing %qE (all checks passed)", fun
->decl
);
2365 /* Callback for walk_tree for finding callbacks within initializers;
2366 ensure they are treated as possible entrypoints to the analysis. */
2369 add_any_callbacks (tree
*tp
, int *, void *data
)
2371 exploded_graph
*eg
= (exploded_graph
*)data
;
2372 if (TREE_CODE (*tp
) == FUNCTION_DECL
)
2373 eg
->on_escaped_function (*tp
);
2377 /* Add initial nodes to EG, with entrypoints for externally-callable
2381 exploded_graph::build_initial_worklist ()
2383 logger
* const logger
= get_logger ();
2387 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
2389 function
*fun
= node
->get_fun ();
2390 if (!toplevel_function_p (node
, fun
, logger
))
2392 exploded_node
*enode
= add_function_entry (fun
);
2396 logger
->log ("created EN %i for %qE entrypoint",
2397 enode
->m_index
, fun
->decl
);
2399 logger
->log ("did not create enode for %qE entrypoint", fun
->decl
);
2403 /* Find callbacks that are reachable from global initializers. */
2404 varpool_node
*vpnode
;
2405 FOR_EACH_VARIABLE (vpnode
)
2407 tree decl
= vpnode
->decl
;
2408 if (!TREE_PUBLIC (decl
))
2410 tree init
= DECL_INITIAL (decl
);
2413 walk_tree (&init
, add_any_callbacks
, this, NULL
);
2417 /* The main loop of the analysis.
2418 Take freshly-created exploded_nodes from the worklist, calling
2419 process_node on them to explore the <point, state> graph.
2420 Add edges to their successors, potentially creating new successors
2421 (which are also added to the worklist). */
2424 exploded_graph::process_worklist ()
2426 logger
* const logger
= get_logger ();
2428 auto_timevar
tv (TV_ANALYZER_WORKLIST
);
2430 while (m_worklist
.length () > 0)
2432 exploded_node
*node
= m_worklist
.take_next ();
2433 gcc_assert (node
->get_status () == exploded_node::STATUS_WORKLIST
);
2434 gcc_assert (node
->m_succs
.length () == 0
2435 || node
== m_origin
);
2438 logger
->log ("next to process: EN: %i", node
->m_index
);
2440 /* If we have a run of nodes that are before-supernode, try merging and
2441 processing them together, rather than pairwise or individually. */
2442 if (flag_analyzer_state_merge
&& node
!= m_origin
)
2443 if (maybe_process_run_of_before_supernode_enodes (node
))
2446 /* Avoid exponential explosions of nodes by attempting to merge
2447 nodes that are at the same program point and which have
2448 sufficiently similar state. */
2449 if (flag_analyzer_state_merge
&& node
!= m_origin
)
2450 if (exploded_node
*node_2
= m_worklist
.peek_next ())
2452 gcc_assert (node_2
->get_status ()
2453 == exploded_node::STATUS_WORKLIST
);
2454 gcc_assert (node
->m_succs
.length () == 0);
2455 gcc_assert (node_2
->m_succs
.length () == 0);
2457 gcc_assert (node
!= node_2
);
2460 logger
->log ("peek worklist: EN: %i", node_2
->m_index
);
2462 if (node
->get_point () == node_2
->get_point ())
2464 const program_point
&point
= node
->get_point ();
2468 pretty_printer
*pp
= logger
->get_printer ();
2469 logger
->start_log_line ();
2471 ("got potential merge EN: %i and EN: %i at ",
2472 node
->m_index
, node_2
->m_index
);
2473 point
.print (pp
, f
);
2474 logger
->end_log_line ();
2476 const program_state
&state
= node
->get_state ();
2477 const program_state
&state_2
= node_2
->get_state ();
2479 /* They shouldn't be equal, or we wouldn't have two
2481 gcc_assert (state
!= state_2
);
2483 program_state
merged_state (m_ext_state
);
2484 if (state
.can_merge_with_p (state_2
, point
, &merged_state
))
2487 logger
->log ("merging EN: %i and EN: %i",
2488 node
->m_index
, node_2
->m_index
);
2490 if (merged_state
== state
)
2492 /* Then merge node_2 into node by adding an edge. */
2493 add_edge (node_2
, node
, NULL
);
2495 /* Remove node_2 from the worklist. */
2496 m_worklist
.take_next ();
2497 node_2
->set_status (exploded_node::STATUS_MERGER
);
2499 /* Continue processing "node" below. */
2501 else if (merged_state
== state_2
)
2503 /* Then merge node into node_2, and leave node_2
2504 in the worklist, to be processed on the next
2506 add_edge (node
, node_2
, NULL
);
2507 node
->set_status (exploded_node::STATUS_MERGER
);
2512 /* We have a merged state that differs from
2513 both state and state_2. */
2515 /* Remove node_2 from the worklist. */
2516 m_worklist
.take_next ();
2518 /* Create (or get) an exploded node for the merged
2519 states, adding to the worklist. */
2520 exploded_node
*merged_enode
2521 = get_or_create_node (node
->get_point (),
2522 merged_state
, node
);
2523 if (merged_enode
== NULL
)
2527 logger
->log ("merged EN: %i and EN: %i into EN: %i",
2528 node
->m_index
, node_2
->m_index
,
2529 merged_enode
->m_index
);
2531 /* "node" and "node_2" have both now been removed
2532 from the worklist; we should not process them.
2534 "merged_enode" may be a new node; if so it will be
2535 processed in a subsequent iteration.
2536 Alternatively, "merged_enode" could be an existing
2537 node; one way the latter can
2538 happen is if we end up merging a succession of
2539 similar nodes into one. */
2541 /* If merged_node is one of the two we were merging,
2542 add it back to the worklist to ensure it gets
2545 Add edges from the merged nodes to it (but not a
2547 if (merged_enode
== node
)
2548 m_worklist
.add_node (merged_enode
);
2551 add_edge (node
, merged_enode
, NULL
);
2552 node
->set_status (exploded_node::STATUS_MERGER
);
2555 if (merged_enode
== node_2
)
2556 m_worklist
.add_node (merged_enode
);
2559 add_edge (node_2
, merged_enode
, NULL
);
2560 node_2
->set_status (exploded_node::STATUS_MERGER
);
2567 /* TODO: should we attempt more than two nodes,
2568 or just do pairs of nodes? (and hope that we get
2569 a cascade of mergers). */
2573 process_node (node
);
2576 /* Impose a hard limit on the number of exploded nodes, to ensure
2577 that the analysis terminates in the face of pathological state
2578 explosion (or bugs).
2580 Specifically, the limit is on the number of PK_AFTER_SUPERNODE
2581 exploded nodes, looking at supernode exit events.
2583 We use exit rather than entry since there can be multiple
2584 entry ENs, one per phi; the number of PK_AFTER_SUPERNODE ought
2585 to be equivalent to the number of supernodes multiplied by the
2586 number of states. */
2587 const int limit
= m_sg
.num_nodes () * param_analyzer_bb_explosion_factor
;
2588 if (m_global_stats
.m_num_nodes
[PK_AFTER_SUPERNODE
] > limit
)
2591 logger
->log ("bailing out; too many nodes");
2592 warning_at (node
->get_point ().get_location (),
2593 OPT_Wanalyzer_too_complex
,
2594 "analysis bailed out early"
2595 " (%i 'after-snode' enodes; %i enodes)",
2596 m_global_stats
.m_num_nodes
[PK_AFTER_SUPERNODE
],
2603 /* Attempt to process a consecutive run of sufficiently-similar nodes in
2604 the worklist at a CFG join-point (having already popped ENODE from the
2605 head of the worklist).
2607 If ENODE's point is of the form (before-supernode, SNODE) and the next
2608 nodes in the worklist are a consecutive run of enodes of the same form,
2609 for the same supernode as ENODE (but potentially from different in-edges),
2610 process them all together, setting their status to STATUS_BULK_MERGED,
2612 Otherwise, return false, in which case ENODE must be processed in the
2615 When processing them all together, generate successor states based
2616 on phi nodes for the appropriate CFG edges, and then attempt to merge
2617 these states into a minimal set of merged successor states, partitioning
2618 the inputs by merged successor state.
2620 Create new exploded nodes for all of the merged states, and add edges
2621 connecting the input enodes to the corresponding merger exploded nodes.
2623 We hope we have a much smaller number of merged successor states
2624 compared to the number of input enodes - ideally just one,
2625 if all successor states can be merged.
2627 Processing and merging many together as one operation rather than as
2628 pairs avoids scaling issues where per-pair mergers could bloat the
2629 graph with merger nodes (especially so after switch statements). */
2633 maybe_process_run_of_before_supernode_enodes (exploded_node
*enode
)
2635 /* A struct for tracking per-input state. */
2638 item (exploded_node
*input_enode
)
2639 : m_input_enode (input_enode
),
2640 m_processed_state (input_enode
->get_state ()),
2644 exploded_node
*m_input_enode
;
2645 program_state m_processed_state
;
2649 gcc_assert (enode
->get_status () == exploded_node::STATUS_WORKLIST
);
2650 gcc_assert (enode
->m_succs
.length () == 0);
2652 const program_point
&point
= enode
->get_point ();
2654 if (point
.get_kind () != PK_BEFORE_SUPERNODE
)
2657 const supernode
*snode
= point
.get_supernode ();
2659 logger
* const logger
= get_logger ();
2662 /* Find a run of enodes in the worklist that are before the same supernode,
2663 but potentially from different in-edges. */
2664 auto_vec
<exploded_node
*> enodes
;
2665 enodes
.safe_push (enode
);
2666 while (exploded_node
*enode_2
= m_worklist
.peek_next ())
2668 gcc_assert (enode_2
->get_status ()
2669 == exploded_node::STATUS_WORKLIST
);
2670 gcc_assert (enode_2
->m_succs
.length () == 0);
2672 const program_point
&point_2
= enode_2
->get_point ();
2674 if (point_2
.get_kind () == PK_BEFORE_SUPERNODE
2675 && point_2
.get_supernode () == snode
2676 && point_2
.get_call_string () == point
.get_call_string ())
2678 enodes
.safe_push (enode_2
);
2679 m_worklist
.take_next ();
2685 /* If the only node is ENODE, then give up. */
2686 if (enodes
.length () == 1)
2690 logger
->log ("got run of %i enodes for SN: %i",
2691 enodes
.length (), snode
->m_index
);
2693 /* All of these enodes have a shared successor point (even if they
2694 were for different in-edges). */
2695 program_point
next_point (point
.get_next ());
2697 /* Calculate the successor state for each enode in enodes. */
2698 auto_delete_vec
<item
> items (enodes
.length ());
2700 exploded_node
*iter_enode
;
2701 FOR_EACH_VEC_ELT (enodes
, i
, iter_enode
)
2703 item
*it
= new item (iter_enode
);
2704 items
.quick_push (it
);
2705 const program_state
&state
= iter_enode
->get_state ();
2706 program_state
*next_state
= &it
->m_processed_state
;
2707 const program_point
&iter_point
= iter_enode
->get_point ();
2708 if (const superedge
*iter_sedge
= iter_point
.get_from_edge ())
2710 impl_region_model_context
ctxt (*this, iter_enode
,
2711 &state
, next_state
, NULL
);
2712 const cfg_superedge
*last_cfg_superedge
2713 = iter_sedge
->dyn_cast_cfg_superedge ();
2714 if (last_cfg_superedge
)
2715 next_state
->m_region_model
->update_for_phis
2716 (snode
, last_cfg_superedge
, &ctxt
);
2720 /* Attempt to partition the items into a set of merged states.
2721 We hope we have a much smaller number of merged states
2722 compared to the number of input enodes - ideally just one,
2723 if all can be merged. */
2724 auto_delete_vec
<program_state
> merged_states
;
2725 auto_vec
<item
*> first_item_for_each_merged_state
;
2727 FOR_EACH_VEC_ELT (items
, i
, it
)
2729 const program_state
&it_state
= it
->m_processed_state
;
2730 program_state
*merged_state
;
2731 unsigned iter_merger_idx
;
2732 FOR_EACH_VEC_ELT (merged_states
, iter_merger_idx
, merged_state
)
2734 program_state
merge (m_ext_state
);
2735 if (it_state
.can_merge_with_p (*merged_state
, next_point
, &merge
))
2737 *merged_state
= merge
;
2738 it
->m_merger_idx
= iter_merger_idx
;
2740 logger
->log ("reusing merger state %i for item %i (EN: %i)",
2741 it
->m_merger_idx
, i
, it
->m_input_enode
->m_index
);
2745 /* If it couldn't be merged with any existing merged_states,
2746 create a new one. */
2747 if (it
->m_merger_idx
== -1)
2749 it
->m_merger_idx
= merged_states
.length ();
2750 merged_states
.safe_push (new program_state (it_state
));
2751 first_item_for_each_merged_state
.safe_push (it
);
2753 logger
->log ("using new merger state %i for item %i (EN: %i)",
2754 it
->m_merger_idx
, i
, it
->m_input_enode
->m_index
);
2757 gcc_assert (it
->m_merger_idx
>= 0);
2758 gcc_assert ((unsigned)it
->m_merger_idx
< merged_states
.length ());
2761 /* Create merger nodes. */
2762 auto_vec
<exploded_node
*> next_enodes (merged_states
.length ());
2763 program_state
*merged_state
;
2764 FOR_EACH_VEC_ELT (merged_states
, i
, merged_state
)
2766 exploded_node
*src_enode
2767 = first_item_for_each_merged_state
[i
]->m_input_enode
;
2769 = get_or_create_node (next_point
, *merged_state
, src_enode
);
2770 /* "next" could be NULL; we handle that when adding the edges below. */
2771 next_enodes
.quick_push (next
);
2775 logger
->log ("using EN: %i for merger state %i", next
->m_index
, i
);
2777 logger
->log ("using NULL enode for merger state %i", i
);
2781 /* Create edges from each input enode to the appropriate successor enode.
2782 Update the status of the now-processed input enodes. */
2783 FOR_EACH_VEC_ELT (items
, i
, it
)
2785 exploded_node
*next
= next_enodes
[it
->m_merger_idx
];
2787 add_edge (it
->m_input_enode
, next
, NULL
);
2788 it
->m_input_enode
->set_status (exploded_node::STATUS_BULK_MERGED
);
2792 logger
->log ("merged %i in-enodes into %i out-enode(s) at SN: %i",
2793 items
.length (), merged_states
.length (), snode
->m_index
);
2798 /* Return true if STMT must appear at the start of its exploded node, and
2799 thus we can't consolidate its effects within a run of other statements,
2800 where PREV_STMT was the previous statement. */
2803 stmt_requires_new_enode_p (const gimple
*stmt
,
2804 const gimple
*prev_stmt
)
2806 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
2808 /* Stop consolidating at calls to
2809 "__analyzer_dump_exploded_nodes", so they always appear at the
2810 start of an exploded_node. */
2811 if (is_special_named_call_p (call
, "__analyzer_dump_exploded_nodes",
2815 /* sm-signal.cc injects an additional custom eedge at "signal" calls
2816 from the registration enode to the handler enode, separate from the
2817 regular next state, which defeats the "detect state change" logic
2818 in process_node. Work around this via special-casing, to ensure
2819 we split the enode immediately before any "signal" call. */
2820 if (is_special_named_call_p (call
, "signal", 2))
2824 /* If we had a PREV_STMT with an unknown location, and this stmt
2825 has a known location, then if a state change happens here, it
2826 could be consolidated into PREV_STMT, giving us an event with
2827 no location. Ensure that STMT gets its own exploded_node to
2829 if (get_pure_location (prev_stmt
->location
) == UNKNOWN_LOCATION
2830 && get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
2836 /* The core of exploded_graph::process_worklist (the main analysis loop),
2837 handling one node in the worklist.
2839 Get successor <point, state> pairs for NODE, calling get_or_create on
2840 them, and adding an exploded_edge to each successors.
2842 Freshly-created nodes will be added to the worklist. */
2845 exploded_graph::process_node (exploded_node
*node
)
2847 logger
* const logger
= get_logger ();
2848 LOG_FUNC_1 (logger
, "EN: %i", node
->m_index
);
2850 node
->set_status (exploded_node::STATUS_PROCESSED
);
2852 const program_point
&point
= node
->get_point ();
2854 /* Update cfun and input_location in case of an ICE: make it easier to
2855 track down which source construct we're failing to handle. */
2856 auto_cfun
sentinel (node
->get_function ());
2857 const gimple
*stmt
= point
.get_stmt ();
2859 input_location
= stmt
->location
;
2861 const program_state
&state
= node
->get_state ();
2864 pretty_printer
*pp
= logger
->get_printer ();
2865 logger
->start_log_line ();
2866 pp_string (pp
, "point: ");
2867 point
.print (pp
, format (false));
2868 pp_string (pp
, ", state: ");
2869 state
.dump_to_pp (m_ext_state
, true, false, pp
);
2870 logger
->end_log_line ();
2873 switch (point
.get_kind ())
2878 /* This node exists to simplify finding the shortest path
2879 to an exploded_node. */
2882 case PK_BEFORE_SUPERNODE
:
2884 program_state
next_state (state
);
2886 if (point
.get_from_edge ())
2888 impl_region_model_context
ctxt (*this, node
,
2889 &state
, &next_state
, NULL
);
2890 const cfg_superedge
*last_cfg_superedge
2891 = point
.get_from_edge ()->dyn_cast_cfg_superedge ();
2892 if (last_cfg_superedge
)
2893 next_state
.m_region_model
->update_for_phis
2894 (node
->get_supernode (),
2899 program_point
next_point (point
.get_next ());
2900 exploded_node
*next
= get_or_create_node (next_point
, next_state
, node
);
2902 add_edge (node
, next
, NULL
);
2905 case PK_BEFORE_STMT
:
2907 /* Determine the effect of a run of one or more statements
2908 within one supernode, generating an edge to the program_point
2909 after the last statement that's processed.
2911 Stop iterating statements and thus consolidating into one enode
2913 - reaching the end of the statements in the supernode
2914 - if an sm-state-change occurs (so that it gets its own
2916 - if "-fanalyzer-fine-grained" is active
2917 - encountering certain statements must appear at the start of
2918 their enode (for which stmt_requires_new_enode_p returns true)
2920 Update next_state in-place, to get the result of the one
2921 or more stmts that are processed.
2923 Split the node in-place if an sm-state-change occurs, so that
2924 the sm-state-change occurs on an edge where the src enode has
2925 exactly one stmt, the one that caused the change. */
2926 program_state
next_state (state
);
2927 const supernode
*snode
= point
.get_supernode ();
2929 const gimple
*prev_stmt
= NULL
;
2930 for (stmt_idx
= point
.get_stmt_idx ();
2931 stmt_idx
< snode
->m_stmts
.length ();
2934 const gimple
*stmt
= snode
->m_stmts
[stmt_idx
];
2936 if (stmt_idx
> point
.get_stmt_idx ())
2937 if (stmt_requires_new_enode_p (stmt
, prev_stmt
))
2944 program_state
old_state (next_state
);
2946 /* Process the stmt. */
2947 exploded_node::on_stmt_flags flags
2948 = node
->on_stmt (*this, snode
, stmt
, &next_state
);
2949 node
->m_num_processed_stmts
++;
2951 /* If flags.m_terminate_path, stop analyzing; any nodes/edges
2952 will have been added by on_stmt (e.g. for handling longjmp). */
2953 if (flags
.m_terminate_path
)
2956 if (next_state
.m_region_model
)
2958 impl_region_model_context
ctxt (*this, node
,
2959 &old_state
, &next_state
, stmt
);
2960 program_state::detect_leaks (old_state
, next_state
, NULL
,
2961 get_ext_state (), &ctxt
);
2964 unsigned next_idx
= stmt_idx
+ 1;
2965 program_point next_point
2966 = (next_idx
< point
.get_supernode ()->m_stmts
.length ()
2967 ? program_point::before_stmt (point
.get_supernode (), next_idx
,
2968 point
.get_call_string ())
2969 : program_point::after_supernode (point
.get_supernode (),
2970 point
.get_call_string ()));
2971 next_state
= next_state
.prune_for_point (*this, next_point
, node
);
2973 if (flags
.m_sm_changes
|| flag_analyzer_fine_grained
)
2975 program_point split_point
2976 = program_point::before_stmt (point
.get_supernode (),
2978 point
.get_call_string ());
2979 if (split_point
!= node
->get_point ())
2981 /* If we're not at the start of NODE, split the enode at
2982 this stmt, so we have:
2984 so that when split_enode is processed the next edge
2987 and any state change will effectively occur on that
2988 latter edge, and split_enode will contain just stmt. */
2990 logger
->log ("getting split_enode");
2991 exploded_node
*split_enode
2992 = get_or_create_node (split_point
, old_state
, node
);
2995 /* "stmt" will be reprocessed when split_enode is
2997 node
->m_num_processed_stmts
--;
2999 logger
->log ("creating edge to split_enode");
3000 add_edge (node
, split_enode
, NULL
);
3004 /* If we're at the start of NODE, stop iterating,
3005 so that an edge will be created from NODE to
3006 (next_point, next_state) below. */
3010 unsigned next_idx
= stmt_idx
+ 1;
3011 program_point next_point
3012 = (next_idx
< point
.get_supernode ()->m_stmts
.length ()
3013 ? program_point::before_stmt (point
.get_supernode (), next_idx
,
3014 point
.get_call_string ())
3015 : program_point::after_supernode (point
.get_supernode (),
3016 point
.get_call_string ()));
3017 exploded_node
*next
= get_or_create_node (next_point
, next_state
, node
);
3019 add_edge (node
, next
, NULL
);
3022 case PK_AFTER_SUPERNODE
:
3024 /* If this is an EXIT BB, detect leaks, and potentially
3025 create a function summary. */
3026 if (point
.get_supernode ()->return_p ())
3028 node
->detect_leaks (*this);
3029 if (flag_analyzer_call_summaries
3030 && point
.get_call_string ().empty_p ())
3032 /* TODO: create function summary
3033 There can be more than one; each corresponds to a different
3034 final enode in the function. */
3037 pretty_printer
*pp
= logger
->get_printer ();
3038 logger
->start_log_line ();
3040 ("would create function summary for %qE; state: ",
3041 point
.get_fndecl ());
3042 state
.dump_to_pp (m_ext_state
, true, false, pp
);
3043 logger
->end_log_line ();
3045 per_function_data
*per_fn_data
3046 = get_or_create_per_function_data (point
.get_function ());
3047 per_fn_data
->add_call_summary (node
);
3050 /* Traverse into successors of the supernode. */
3053 FOR_EACH_VEC_ELT (point
.get_supernode ()->m_succs
, i
, succ
)
3056 logger
->log ("considering SN: %i -> SN: %i",
3057 succ
->m_src
->m_index
, succ
->m_dest
->m_index
);
3059 program_point next_point
3060 = program_point::before_supernode (succ
->m_dest
, succ
,
3061 point
.get_call_string ());
3062 program_state
next_state (state
);
3064 if (!node
->on_edge (*this, succ
, &next_point
, &next_state
))
3067 logger
->log ("skipping impossible edge to SN: %i",
3068 succ
->m_dest
->m_index
);
3072 exploded_node
*next
= get_or_create_node (next_point
, next_state
,
3075 add_edge (node
, next
, succ
);
3082 /* Ensure that this graph has a stats instance for FN, return it.
3083 FN can be NULL, in which case a stats instances is returned covering
3084 "functionless" parts of the graph (the origin node). */
3087 exploded_graph::get_or_create_function_stats (function
*fn
)
3090 return &m_functionless_stats
;
3092 if (stats
**slot
= m_per_function_stats
.get (fn
))
3096 int num_supernodes
= fn
? n_basic_blocks_for_fn (fn
) : 0;
3097 /* not quite the num supernodes, but nearly. */
3098 stats
*new_stats
= new stats (num_supernodes
);
3099 m_per_function_stats
.put (fn
, new_stats
);
3104 /* Print bar charts to PP showing:
3105 - the number of enodes per function, and
3106 - for each function:
3107 - the number of enodes per supernode/BB
3108 - the number of excess enodes per supernode/BB beyond the
3109 per-program-point limit, if there were any. */
3112 exploded_graph::print_bar_charts (pretty_printer
*pp
) const
3114 cgraph_node
*cgnode
;
3116 pp_string (pp
, "enodes per function:");
3118 bar_chart enodes_per_function
;
3119 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode
)
3121 function
*fn
= cgnode
->get_fun ();
3122 const stats
* const *s_ptr
3123 = const_cast <function_stat_map_t
&> (m_per_function_stats
).get (fn
);
3124 enodes_per_function
.add_item (function_name (fn
),
3125 s_ptr
? (*s_ptr
)->get_total_enodes () : 0);
3127 enodes_per_function
.print (pp
);
3129 /* Accumulate number of enodes per supernode. */
3130 auto_vec
<unsigned> enodes_per_supernode (m_sg
.num_nodes ());
3131 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
3132 enodes_per_supernode
.quick_push (0);
3134 exploded_node
*enode
;
3135 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
3137 const supernode
*iter_snode
= enode
->get_supernode ();
3140 enodes_per_supernode
[iter_snode
->m_index
]++;
3143 /* Accumulate excess enodes per supernode. */
3144 auto_vec
<unsigned> excess_enodes_per_supernode (m_sg
.num_nodes ());
3145 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
3146 excess_enodes_per_supernode
.quick_push (0);
3147 for (point_map_t::iterator iter
= m_per_point_data
.begin ();
3148 iter
!= m_per_point_data
.end (); ++iter
)
3150 const program_point
*point
= (*iter
).first
;
3151 const supernode
*iter_snode
= point
->get_supernode ();
3154 const per_program_point_data
*point_data
= (*iter
).second
;
3155 excess_enodes_per_supernode
[iter_snode
->m_index
]
3156 += point_data
->m_excess_enodes
;
3159 /* Show per-function bar_charts of enodes per supernode/BB. */
3160 pp_string (pp
, "per-function enodes per supernode/BB:");
3162 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode
)
3164 function
*fn
= cgnode
->get_fun ();
3165 pp_printf (pp
, "function: %qs", function_name (fn
));
3168 bar_chart enodes_per_snode
;
3169 bar_chart excess_enodes_per_snode
;
3170 bool have_excess_enodes
= false;
3171 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
3173 const supernode
*iter_snode
= m_sg
.get_node_by_index (i
);
3174 if (iter_snode
->get_function () != fn
)
3176 pretty_printer tmp_pp
;
3177 pp_printf (&tmp_pp
, "sn %i (bb %i)",
3178 iter_snode
->m_index
, iter_snode
->m_bb
->index
);
3179 enodes_per_snode
.add_item (pp_formatted_text (&tmp_pp
),
3180 enodes_per_supernode
[iter_snode
->m_index
]);
3181 const int num_excess
3182 = excess_enodes_per_supernode
[iter_snode
->m_index
];
3183 excess_enodes_per_snode
.add_item (pp_formatted_text (&tmp_pp
),
3186 have_excess_enodes
= true;
3188 enodes_per_snode
.print (pp
);
3189 if (have_excess_enodes
)
3191 pp_printf (pp
, "EXCESS ENODES:");
3193 excess_enodes_per_snode
.print (pp
);
3198 /* Write all stats information to this graph's logger, if any. */
3201 exploded_graph::log_stats () const
3203 logger
* const logger
= get_logger ();
3209 m_ext_state
.get_engine ()->log_stats (logger
);
3211 logger
->log ("m_sg.num_nodes (): %i", m_sg
.num_nodes ());
3212 logger
->log ("m_nodes.length (): %i", m_nodes
.length ());
3213 logger
->log ("m_edges.length (): %i", m_edges
.length ());
3214 logger
->log ("remaining enodes in worklist: %i", m_worklist
.length ());
3216 logger
->log ("global stats:");
3217 m_global_stats
.log (logger
);
3219 for (function_stat_map_t::iterator iter
= m_per_function_stats
.begin ();
3220 iter
!= m_per_function_stats
.end ();
3223 function
*fn
= (*iter
).first
;
3224 log_scope
s (logger
, function_name (fn
));
3225 (*iter
).second
->log (logger
);
3228 print_bar_charts (logger
->get_printer ());
3231 /* Dump all stats information to OUT. */
3234 exploded_graph::dump_stats (FILE *out
) const
3236 fprintf (out
, "m_sg.num_nodes (): %i\n", m_sg
.num_nodes ());
3237 fprintf (out
, "m_nodes.length (): %i\n", m_nodes
.length ());
3238 fprintf (out
, "m_edges.length (): %i\n", m_edges
.length ());
3239 fprintf (out
, "remaining enodes in worklist: %i", m_worklist
.length ());
3241 fprintf (out
, "global stats:\n");
3242 m_global_stats
.dump (out
);
3244 for (function_stat_map_t::iterator iter
= m_per_function_stats
.begin ();
3245 iter
!= m_per_function_stats
.end ();
3248 function
*fn
= (*iter
).first
;
3249 fprintf (out
, "function: %s\n", function_name (fn
));
3250 (*iter
).second
->dump (out
);
3253 fprintf (out
, "PK_AFTER_SUPERNODE per supernode:\n");
3254 for (unsigned i
= 0; i
< m_PK_AFTER_SUPERNODE_per_snode
.length (); i
++)
3255 fprintf (out
, " SN %i: %3i\n", i
, m_PK_AFTER_SUPERNODE_per_snode
[i
]);
3259 exploded_graph::dump_states_for_supernode (FILE *out
,
3260 const supernode
*snode
) const
3262 fprintf (out
, "PK_AFTER_SUPERNODE nodes for SN: %i\n", snode
->m_index
);
3264 exploded_node
*enode
;
3266 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
3268 const supernode
*iter_snode
= enode
->get_supernode ();
3269 if (enode
->get_point ().get_kind () == PK_AFTER_SUPERNODE
3270 && iter_snode
== snode
)
3273 pp_format_decoder (&pp
) = default_tree_printer
;
3274 enode
->get_state ().dump_to_pp (m_ext_state
, true, false, &pp
);
3275 fprintf (out
, "state %i: EN: %i\n %s\n",
3276 state_idx
++, enode
->m_index
,
3277 pp_formatted_text (&pp
));
3280 fprintf (out
, "#exploded_node for PK_AFTER_SUPERNODE for SN: %i = %i\n",
3281 snode
->m_index
, state_idx
);
3284 /* Return a new json::object of the form
3285 {"nodes" : [objs for enodes],
3286 "edges" : [objs for eedges],
3287 "ext_state": object for extrinsic_state,
3288 "diagnostic_manager": object for diagnostic_manager}. */
3291 exploded_graph::to_json () const
3293 json::object
*egraph_obj
= new json::object ();
3297 json::array
*nodes_arr
= new json::array ();
3300 FOR_EACH_VEC_ELT (m_nodes
, i
, n
)
3301 nodes_arr
->append (n
->to_json (m_ext_state
));
3302 egraph_obj
->set ("nodes", nodes_arr
);
3307 json::array
*edges_arr
= new json::array ();
3310 FOR_EACH_VEC_ELT (m_edges
, i
, n
)
3311 edges_arr
->append (n
->to_json ());
3312 egraph_obj
->set ("edges", edges_arr
);
3315 /* m_sg is JSONified at the top-level. */
3317 egraph_obj
->set ("ext_state", m_ext_state
.to_json ());
3318 egraph_obj
->set ("diagnostic_manager", m_diagnostic_manager
.to_json ());
3320 /* The following fields aren't yet being JSONified:
3321 worklist m_worklist;
3322 const state_purge_map *const m_purge_map;
3323 const analysis_plan &m_plan;
3324 stats m_global_stats;
3325 function_stat_map_t m_per_function_stats;
3326 stats m_functionless_stats;
3327 call_string_data_map_t m_per_call_string_data;
3328 auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode; */
3333 /* Look for the last use of SEARCH_STMT within this path.
3334 If found write the edge's index to *OUT_IDX and return true, otherwise
3338 exploded_path::find_stmt_backwards (const gimple
*search_stmt
,
3342 const exploded_edge
*eedge
;
3343 FOR_EACH_VEC_ELT_REVERSE (m_edges
, i
, eedge
)
3345 const exploded_node
*dst_node
= eedge
->m_dest
;
3346 const program_point
&dst_point
= dst_node
->get_point ();
3347 const gimple
*stmt
= dst_point
.get_stmt ();
3348 if (stmt
== search_stmt
)
3357 /* Get the final exploded_node in this path, which must be non-empty. */
3360 exploded_path::get_final_enode () const
3362 gcc_assert (m_edges
.length () > 0);
3363 return m_edges
[m_edges
.length () - 1]->m_dest
;
3366 /* Check state along this path, returning true if it is feasible.
3367 If OUT is non-NULL, and the path is infeasible, write a new
3368 feasibility_problem to *OUT. */
3371 exploded_path::feasible_p (logger
*logger
, feasibility_problem
**out
,
3372 engine
*eng
, const exploded_graph
*eg
) const
3376 auto_sbitmap
snodes_visited (eg
->get_supergraph ().m_nodes
.length ());
3378 /* Traverse the path, updating this model. */
3379 region_model
model (eng
->get_model_manager ());
3380 for (unsigned edge_idx
= 0; edge_idx
< m_edges
.length (); edge_idx
++)
3382 const exploded_edge
*eedge
= m_edges
[edge_idx
];
3384 logger
->log ("considering edge %i: EN:%i -> EN:%i",
3386 eedge
->m_src
->m_index
,
3387 eedge
->m_dest
->m_index
);
3388 const exploded_node
&src_enode
= *eedge
->m_src
;
3389 const program_point
&src_point
= src_enode
.get_point ();
3392 logger
->start_log_line ();
3393 src_point
.print (logger
->get_printer (), format (false));
3394 logger
->end_log_line ();
3397 /* Update state for the stmts that were processed in each enode. */
3398 for (unsigned stmt_idx
= 0; stmt_idx
< src_enode
.m_num_processed_stmts
;
3401 const gimple
*stmt
= src_enode
.get_processed_stmt (stmt_idx
);
3403 /* Update cfun and input_location in case of ICE: make it easier to
3404 track down which source construct we're failing to handle. */
3405 auto_cfun
sentinel (src_point
.get_function ());
3406 input_location
= stmt
->location
;
3408 if (const gassign
*assign
= dyn_cast
<const gassign
*> (stmt
))
3409 model
.on_assignment (assign
, NULL
);
3410 else if (const greturn
*return_
= dyn_cast
<const greturn
*> (stmt
))
3411 model
.on_return (return_
, NULL
);
3414 const superedge
*sedge
= eedge
->m_sedge
;
3418 logger
->log (" sedge: SN:%i -> SN:%i %s",
3419 sedge
->m_src
->m_index
,
3420 sedge
->m_dest
->m_index
,
3421 sedge
->get_description (false));
3423 const gimple
*last_stmt
= src_point
.get_supernode ()->get_last_stmt ();
3424 rejected_constraint
*rc
= NULL
;
3425 if (!model
.maybe_update_for_edge (*sedge
, last_stmt
, NULL
, &rc
))
3429 logger
->log ("rejecting due to region model");
3430 model
.dump_to_pp (logger
->get_printer (), true, false);
3433 *out
= new feasibility_problem (edge_idx
, *eedge
,
3442 /* Special-case the initial eedge from the origin node to the
3443 initial function by pushing a frame for it. */
3446 gcc_assert (eedge
->m_src
->m_index
== 0);
3447 gcc_assert (src_point
.get_kind () == PK_ORIGIN
);
3448 gcc_assert (eedge
->m_dest
->get_point ().get_kind ()
3449 == PK_BEFORE_SUPERNODE
);
3450 function
*fun
= eedge
->m_dest
->get_function ();
3452 model
.push_frame (fun
, NULL
, NULL
);
3454 logger
->log (" pushing frame for %qD", fun
->decl
);
3456 else if (eedge
->m_custom_info
)
3458 eedge
->m_custom_info
->update_model (&model
, *eedge
);
3462 /* Handle phi nodes on an edge leaving a PK_BEFORE_SUPERNODE (to
3463 a PK_BEFORE_STMT, or a PK_AFTER_SUPERNODE if no stmts).
3464 This will typically not be associated with a superedge. */
3465 if (src_point
.get_from_edge ())
3467 const cfg_superedge
*last_cfg_superedge
3468 = src_point
.get_from_edge ()->dyn_cast_cfg_superedge ();
3469 const exploded_node
&dst_enode
= *eedge
->m_dest
;
3470 const unsigned dst_snode_idx
= dst_enode
.get_supernode ()->m_index
;
3471 if (last_cfg_superedge
)
3474 logger
->log (" update for phis");
3475 model
.update_for_phis (src_enode
.get_supernode (),
3478 /* If we've entering an snode that we've already visited on this
3479 epath, then we need do fix things up for loops; see the
3480 comment for store::loop_replay_fixup.
3481 Perhaps we should probably also verify the callstring,
3482 and track program_points, but hopefully doing it by supernode
3484 if (bitmap_bit_p (snodes_visited
, dst_snode_idx
))
3485 model
.loop_replay_fixup (dst_enode
.get_state ().m_region_model
);
3487 bitmap_set_bit (snodes_visited
, dst_snode_idx
);
3492 logger
->log ("state after edge %i: EN:%i -> EN:%i",
3494 eedge
->m_src
->m_index
,
3495 eedge
->m_dest
->m_index
);
3496 logger
->start_log_line ();
3497 model
.dump_to_pp (logger
->get_printer (), true, false);
3498 logger
->end_log_line ();
3505 /* Dump this path in multiline form to PP. */
3508 exploded_path::dump_to_pp (pretty_printer
*pp
) const
3510 for (unsigned i
= 0; i
< m_edges
.length (); i
++)
3512 const exploded_edge
*eedge
= m_edges
[i
];
3513 pp_printf (pp
, "m_edges[%i]: EN %i -> EN %i",
3515 eedge
->m_src
->m_index
,
3516 eedge
->m_dest
->m_index
);
3521 /* Dump this path in multiline form to FP. */
3524 exploded_path::dump (FILE *fp
) const
3527 pp_format_decoder (&pp
) = default_tree_printer
;
3528 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
3529 pp
.buffer
->stream
= fp
;
3534 /* Dump this path in multiline form to stderr. */
3537 exploded_path::dump () const
3542 /* class feasibility_problem. */
3545 feasibility_problem::dump_to_pp (pretty_printer
*pp
) const
3547 pp_printf (pp
, "edge from EN: %i to EN: %i",
3548 m_eedge
.m_src
->m_index
, m_eedge
.m_dest
->m_index
);
3551 pp_string (pp
, "; rejected constraint: ");
3552 m_rc
->dump_to_pp (pp
);
3553 pp_string (pp
, "; rmodel: ");
3554 m_rc
->m_model
.dump_to_pp (pp
, true, false);
3558 /* A family of cluster subclasses for use when generating .dot output for
3559 exploded graphs (-fdump-analyzer-exploded-graph), for grouping the
3560 enodes into hierarchical boxes.
3562 All functionless enodes appear in the top-level graph.
3563 Every (function, call_string) pair gets its own cluster. Within that
3564 cluster, each supernode gets its own cluster.
3566 Hence all enodes relating to a particular function with a particular
3567 callstring will be in a cluster together; all enodes for the same
3568 function but with a different callstring will be in a different
3571 /* Base class of cluster for clustering exploded_node instances in .dot
3572 output, based on various subclass-specific criteria. */
3574 class exploded_cluster
: public cluster
<eg_traits
>
3578 /* Cluster containing all exploded_node instances for one supernode. */
3580 class supernode_cluster
: public exploded_cluster
3583 supernode_cluster (const supernode
*supernode
) : m_supernode (supernode
) {}
3587 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const FINAL OVERRIDE
3589 gv
->println ("subgraph \"cluster_supernode_%i\" {", m_supernode
->m_index
);
3591 gv
->println ("style=\"dashed\";");
3592 gv
->println ("label=\"SN: %i (bb: %i; scc: %i)\";",
3593 m_supernode
->m_index
, m_supernode
->m_bb
->index
,
3594 args
.m_eg
.get_scc_id (*m_supernode
));
3597 exploded_node
*enode
;
3598 FOR_EACH_VEC_ELT (m_enodes
, i
, enode
)
3599 enode
->dump_dot (gv
, args
);
3601 /* Terminate subgraph. */
3606 void add_node (exploded_node
*en
) FINAL OVERRIDE
3608 m_enodes
.safe_push (en
);
3611 /* Comparator for use by auto_vec<supernode_cluster *>::qsort. */
3613 static int cmp_ptr_ptr (const void *p1
, const void *p2
)
3615 const supernode_cluster
*c1
3616 = *(const supernode_cluster
* const *)p1
;
3617 const supernode_cluster
*c2
3618 = *(const supernode_cluster
* const *)p2
;
3619 return c1
->m_supernode
->m_index
- c2
->m_supernode
->m_index
;
3623 const supernode
*m_supernode
;
3624 auto_vec
<exploded_node
*> m_enodes
;
3627 /* Cluster containing all supernode_cluster instances for one
3628 (function, call_string) pair. */
3630 class function_call_string_cluster
: public exploded_cluster
3633 function_call_string_cluster (function
*fun
, call_string cs
)
3634 : m_fun (fun
), m_cs (cs
) {}
3636 ~function_call_string_cluster ()
3638 for (map_t::iterator iter
= m_map
.begin ();
3639 iter
!= m_map
.end ();
3641 delete (*iter
).second
;
3644 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const FINAL OVERRIDE
3646 const char *funcname
= function_name (m_fun
);
3648 gv
->println ("subgraph \"cluster_function_%s\" {",
3649 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (m_fun
->decl
)));
3651 gv
->write_indent ();
3652 gv
->print ("label=\"call string: ");
3653 m_cs
.print (gv
->get_pp ());
3654 gv
->print (" function: %s \";", funcname
);
3657 /* Dump m_map, sorting it to avoid churn when comparing dumps. */
3658 auto_vec
<supernode_cluster
*> child_clusters (m_map
.elements ());
3659 for (map_t::iterator iter
= m_map
.begin ();
3660 iter
!= m_map
.end ();
3662 child_clusters
.quick_push ((*iter
).second
);
3664 child_clusters
.qsort (supernode_cluster::cmp_ptr_ptr
);
3667 supernode_cluster
*child_cluster
;
3668 FOR_EACH_VEC_ELT (child_clusters
, i
, child_cluster
)
3669 child_cluster
->dump_dot (gv
, args
);
3671 /* Terminate subgraph. */
3676 void add_node (exploded_node
*en
) FINAL OVERRIDE
3678 const supernode
*supernode
= en
->get_supernode ();
3679 gcc_assert (supernode
);
3680 supernode_cluster
**slot
= m_map
.get (supernode
);
3682 (*slot
)->add_node (en
);
3685 supernode_cluster
*child
= new supernode_cluster (supernode
);
3686 m_map
.put (supernode
, child
);
3687 child
->add_node (en
);
3691 /* Comparator for use by auto_vec<function_call_string_cluster *>. */
3693 static int cmp_ptr_ptr (const void *p1
, const void *p2
)
3695 const function_call_string_cluster
*c1
3696 = *(const function_call_string_cluster
* const *)p1
;
3697 const function_call_string_cluster
*c2
3698 = *(const function_call_string_cluster
* const *)p2
;
3700 = strcmp (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c1
->m_fun
->decl
)),
3701 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c2
->m_fun
->decl
))))
3703 return call_string::cmp (c1
->m_cs
, c2
->m_cs
);
3709 typedef ordered_hash_map
<const supernode
*, supernode_cluster
*> map_t
;
3713 /* Keys for root_cluster. */
3715 struct function_call_string
3717 function_call_string (function
*fun
, call_string cs
)
3718 : m_fun (fun
), m_cs (cs
)
3729 template <> struct default_hash_traits
<function_call_string
>
3730 : public pod_hash_traits
<function_call_string
>
3732 static const bool empty_zero_p
= false;
3737 pod_hash_traits
<function_call_string
>::hash (value_type v
)
3739 return pointer_hash
<function
>::hash (v
.m_fun
) ^ v
.m_cs
.hash ();
3744 pod_hash_traits
<function_call_string
>::equal (const value_type
&existing
,
3745 const value_type
&candidate
)
3747 return existing
.m_fun
== candidate
.m_fun
&& existing
.m_cs
== candidate
.m_cs
;
3751 pod_hash_traits
<function_call_string
>::mark_deleted (value_type
&v
)
3753 v
.m_fun
= reinterpret_cast<function
*> (1);
3757 pod_hash_traits
<function_call_string
>::mark_empty (value_type
&v
)
3763 pod_hash_traits
<function_call_string
>::is_deleted (value_type v
)
3765 return v
.m_fun
== reinterpret_cast<function
*> (1);
3769 pod_hash_traits
<function_call_string
>::is_empty (value_type v
)
3771 return v
.m_fun
== NULL
;
3776 /* Top-level cluster for generating .dot output for exploded graphs,
3777 handling the functionless nodes, and grouping the remaining nodes by
3780 class root_cluster
: public exploded_cluster
3785 for (map_t::iterator iter
= m_map
.begin ();
3786 iter
!= m_map
.end ();
3788 delete (*iter
).second
;
3791 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const FINAL OVERRIDE
3794 exploded_node
*enode
;
3795 FOR_EACH_VEC_ELT (m_functionless_enodes
, i
, enode
)
3796 enode
->dump_dot (gv
, args
);
3798 /* Dump m_map, sorting it to avoid churn when comparing dumps. */
3799 auto_vec
<function_call_string_cluster
*> child_clusters (m_map
.elements ());
3800 for (map_t::iterator iter
= m_map
.begin ();
3801 iter
!= m_map
.end ();
3803 child_clusters
.quick_push ((*iter
).second
);
3805 child_clusters
.qsort (function_call_string_cluster::cmp_ptr_ptr
);
3807 function_call_string_cluster
*child_cluster
;
3808 FOR_EACH_VEC_ELT (child_clusters
, i
, child_cluster
)
3809 child_cluster
->dump_dot (gv
, args
);
3812 void add_node (exploded_node
*en
) FINAL OVERRIDE
3814 function
*fun
= en
->get_function ();
3817 m_functionless_enodes
.safe_push (en
);
3821 const call_string
&cs
= en
->get_point ().get_call_string ();
3822 function_call_string
key (fun
, cs
);
3823 function_call_string_cluster
**slot
= m_map
.get (key
);
3825 (*slot
)->add_node (en
);
3828 function_call_string_cluster
*child
3829 = new function_call_string_cluster (fun
, cs
);
3830 m_map
.put (key
, child
);
3831 child
->add_node (en
);
3836 /* This can't be an ordered_hash_map, as we can't store vec<call_string>,
3837 since it's not a POD; vec<>::quick_push has:
3839 and the slot isn't initialized, so the assignment op dies when cleaning up
3840 un-inited *slot (within the truncate call). */
3841 typedef hash_map
<function_call_string
, function_call_string_cluster
*> map_t
;
3844 /* This should just be the origin exploded_node. */
3845 auto_vec
<exploded_node
*> m_functionless_enodes
;
3848 /* Subclass of range_label for use within
3849 exploded_graph::dump_exploded_nodes for implementing
3850 -fdump-analyzer-exploded-nodes: a label for a specific
3853 class enode_label
: public range_label
3856 enode_label (const extrinsic_state
&ext_state
,
3857 exploded_node
*enode
)
3858 : m_ext_state (ext_state
), m_enode (enode
) {}
3860 label_text
get_text (unsigned) const FINAL OVERRIDE
3863 pp_format_decoder (&pp
) = default_tree_printer
;
3864 m_enode
->get_state ().dump_to_pp (m_ext_state
, true, false, &pp
);
3865 return make_label_text (false, "EN: %i: %s",
3866 m_enode
->m_index
, pp_formatted_text (&pp
));
3870 const extrinsic_state
&m_ext_state
;
3871 exploded_node
*m_enode
;
3874 /* Postprocessing support for dumping the exploded nodes.
3875 Handle -fdump-analyzer-exploded-nodes,
3876 -fdump-analyzer-exploded-nodes-2, and the
3877 "__analyzer_dump_exploded_nodes" builtin. */
3880 exploded_graph::dump_exploded_nodes () const
3883 /* Locate calls to __analyzer_dump_exploded_nodes. */
3884 // Print how many egs there are for them?
3885 /* Better: log them as we go, and record the exploded nodes
3888 /* Show every enode. */
3890 /* Gather them by stmt, so that we can more clearly see the
3891 "hotspots" requiring numerous exploded nodes. */
3893 /* Alternatively, simply throw them all into one big rich_location
3894 and see if the label-printing will sort it out...
3895 This requires them all to be in the same source file. */
3897 if (flag_dump_analyzer_exploded_nodes
)
3899 auto_timevar
tv (TV_ANALYZER_DUMP
);
3900 gcc_rich_location
richloc (UNKNOWN_LOCATION
);
3902 exploded_node
*enode
;
3903 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
3905 if (const gimple
*stmt
= enode
->get_stmt ())
3907 if (get_pure_location (richloc
.get_loc ()) == UNKNOWN_LOCATION
)
3908 richloc
.set_range (0, stmt
->location
, SHOW_RANGE_WITH_CARET
);
3910 richloc
.add_range (stmt
->location
,
3911 SHOW_RANGE_WITHOUT_CARET
,
3912 new enode_label (m_ext_state
, enode
));
3915 warning_at (&richloc
, 0, "%i exploded nodes", m_nodes
.length ());
3917 /* Repeat the warning without all the labels, so that message is visible
3918 (the other one may well have scrolled past the terminal limit). */
3919 warning_at (richloc
.get_loc (), 0,
3920 "%i exploded nodes", m_nodes
.length ());
3922 if (m_worklist
.length () > 0)
3923 warning_at (richloc
.get_loc (), 0,
3924 "worklist still contains %i nodes", m_worklist
.length ());
3927 /* Dump the egraph in textual form to a dump file. */
3928 if (flag_dump_analyzer_exploded_nodes_2
)
3930 auto_timevar
tv (TV_ANALYZER_DUMP
);
3932 = concat (dump_base_name
, ".eg.txt", NULL
);
3933 FILE *outf
= fopen (filename
, "w");
3935 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
3938 fprintf (outf
, "exploded graph for %s\n", dump_base_name
);
3939 fprintf (outf
, " nodes: %i\n", m_nodes
.length ());
3940 fprintf (outf
, " edges: %i\n", m_edges
.length ());
3943 exploded_node
*enode
;
3944 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
3946 fprintf (outf
, "\nEN %i:\n", enode
->m_index
);
3947 enode
->dump_succs_and_preds (outf
);
3949 enode
->get_point ().print (&pp
, format (true));
3950 fprintf (outf
, "%s\n", pp_formatted_text (&pp
));
3951 enode
->get_state ().dump_to_file (m_ext_state
, false, true, outf
);
3957 /* Dump the egraph in textual form to multiple dump files, one per enode. */
3958 if (flag_dump_analyzer_exploded_nodes_3
)
3960 auto_timevar
tv (TV_ANALYZER_DUMP
);
3963 exploded_node
*enode
;
3964 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
3967 = xasprintf ("%s.en-%i.txt", dump_base_name
, i
);
3968 FILE *outf
= fopen (filename
, "w");
3970 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
3973 fprintf (outf
, "EN %i:\n", enode
->m_index
);
3974 enode
->dump_succs_and_preds (outf
);
3976 enode
->get_point ().print (&pp
, format (true));
3977 fprintf (outf
, "%s\n", pp_formatted_text (&pp
));
3978 enode
->get_state ().dump_to_file (m_ext_state
, false, true, outf
);
3984 /* Emit a warning at any call to "__analyzer_dump_exploded_nodes",
3985 giving the number of processed exploded nodes for "before-stmt",
3986 and the IDs of processed, merger, and worklist enodes.
3988 We highlight the count of *processed* enodes since this is of most
3989 interest in DejaGnu tests for ensuring that state merger has
3992 We don't show the count of merger and worklist enodes, as this is
3993 more of an implementation detail of the merging/worklist that we
3994 don't want to bake into our expected DejaGnu messages. */
3997 exploded_node
*enode
;
3998 hash_set
<const gimple
*> seen
;
3999 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
4001 if (enode
->get_point ().get_kind () != PK_BEFORE_STMT
)
4004 if (const gimple
*stmt
= enode
->get_stmt ())
4005 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
4006 if (is_special_named_call_p (call
, "__analyzer_dump_exploded_nodes",
4009 if (seen
.contains (stmt
))
4012 auto_vec
<exploded_node
*> processed_enodes
;
4013 auto_vec
<exploded_node
*> merger_enodes
;
4014 auto_vec
<exploded_node
*> worklist_enodes
;
4015 /* This is O(N^2). */
4017 exploded_node
*other_enode
;
4018 FOR_EACH_VEC_ELT (m_nodes
, j
, other_enode
)
4020 if (other_enode
->get_point ().get_kind () != PK_BEFORE_STMT
)
4022 if (other_enode
->get_stmt () == stmt
)
4023 switch (other_enode
->get_status ())
4027 case exploded_node::STATUS_WORKLIST
:
4028 worklist_enodes
.safe_push (other_enode
);
4030 case exploded_node::STATUS_PROCESSED
:
4031 processed_enodes
.safe_push (other_enode
);
4033 case exploded_node::STATUS_MERGER
:
4034 merger_enodes
.safe_push (other_enode
);
4040 pp_character (&pp
, '[');
4041 print_enode_indices (&pp
, processed_enodes
);
4042 if (merger_enodes
.length () > 0)
4044 pp_string (&pp
, "] merger(s): [");
4045 print_enode_indices (&pp
, merger_enodes
);
4047 if (worklist_enodes
.length () > 0)
4049 pp_string (&pp
, "] worklist: [");
4050 print_enode_indices (&pp
, worklist_enodes
);
4052 pp_character (&pp
, ']');
4054 warning_n (stmt
->location
, 0, processed_enodes
.length (),
4055 "%i processed enode: %s",
4056 "%i processed enodes: %s",
4057 processed_enodes
.length (), pp_formatted_text (&pp
));
4060 /* If the argument is non-zero, then print all of the states
4061 of the various enodes. */
4062 tree t_arg
= fold (gimple_call_arg (call
, 0));
4063 if (TREE_CODE (t_arg
) != INTEGER_CST
)
4065 error_at (call
->location
,
4066 "integer constant required for arg 1");
4069 int i_arg
= TREE_INT_CST_LOW (t_arg
);
4072 exploded_node
*other_enode
;
4073 FOR_EACH_VEC_ELT (processed_enodes
, j
, other_enode
)
4075 fprintf (stderr
, "%i of %i: EN %i:\n",
4076 j
+ 1, processed_enodes
.length (),
4077 other_enode
->m_index
);
4078 other_enode
->dump_succs_and_preds (stderr
);
4080 other_enode
->get_state ().dump (m_ext_state
, false);
4087 DEBUG_FUNCTION exploded_node
*
4088 exploded_graph::get_node_by_index (int idx
) const
4090 exploded_node
*enode
= m_nodes
[idx
];
4091 gcc_assert (enode
->m_index
== idx
);
4095 /* Ensure that there is an exploded_node for a top-level call to FNDECL. */
4098 exploded_graph::on_escaped_function (tree fndecl
)
4100 logger
* const logger
= get_logger ();
4101 LOG_FUNC_1 (logger
, "%qE", fndecl
);
4103 cgraph_node
*cgnode
= cgraph_node::get (fndecl
);
4107 function
*fun
= cgnode
->get_fun ();
4111 if (!gimple_has_body_p (fndecl
))
4114 exploded_node
*enode
= add_function_entry (fun
);
4118 logger
->log ("created EN %i for %qE entrypoint",
4119 enode
->m_index
, fun
->decl
);
4121 logger
->log ("did not create enode for %qE entrypoint", fun
->decl
);
4125 /* A collection of classes for visualizing the callgraph in .dot form
4126 (as represented in the supergraph). */
4128 /* Forward decls. */
4129 class viz_callgraph_node
;
4130 class viz_callgraph_edge
;
4131 class viz_callgraph
;
4132 class viz_callgraph_cluster
;
4134 /* Traits for using "digraph.h" to visualize the callgraph. */
4136 struct viz_callgraph_traits
4138 typedef viz_callgraph_node node_t
;
4139 typedef viz_callgraph_edge edge_t
;
4140 typedef viz_callgraph graph_t
;
4143 dump_args_t (const exploded_graph
*eg
) : m_eg (eg
) {}
4144 const exploded_graph
*m_eg
;
4146 typedef viz_callgraph_cluster cluster_t
;
4149 /* Subclass of dnode representing a function within the callgraph. */
4151 class viz_callgraph_node
: public dnode
<viz_callgraph_traits
>
4153 friend class viz_callgraph
;
4156 viz_callgraph_node (function
*fun
, int index
)
4157 : m_fun (fun
), m_index (index
), m_num_supernodes (0), m_num_superedges (0)
4162 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const FINAL OVERRIDE
4164 pretty_printer
*pp
= gv
->get_pp ();
4167 pp_printf (pp
, " [shape=none,margin=0,style=filled,fillcolor=%s,label=<",
4169 pp_string (pp
, "<TABLE BORDER=\"0\">");
4170 pp_write_text_to_stream (pp
);
4173 pp_printf (pp
, "VCG: %i: %s", m_index
, function_name (m_fun
));
4178 pp_printf (pp
, "supernodes: %i\n", m_num_supernodes
);
4183 pp_printf (pp
, "superedges: %i\n", m_num_superedges
);
4190 exploded_node
*enode
;
4191 unsigned num_enodes
= 0;
4192 FOR_EACH_VEC_ELT (args
.m_eg
->m_nodes
, i
, enode
)
4194 if (enode
->get_point ().get_function () == m_fun
)
4198 pp_printf (pp
, "enodes: %i\n", num_enodes
);
4202 // TODO: also show the per-callstring breakdown
4203 const exploded_graph::call_string_data_map_t
*per_cs_data
4204 = args
.m_eg
->get_per_call_string_data ();
4205 for (exploded_graph::call_string_data_map_t::iterator iter
4206 = per_cs_data
->begin ();
4207 iter
!= per_cs_data
->end ();
4210 const call_string
*cs
= (*iter
).first
;
4211 //per_call_string_data *data = (*iter).second;
4213 FOR_EACH_VEC_ELT (args
.m_eg
->m_nodes
, i
, enode
)
4215 if (enode
->get_point ().get_function () == m_fun
4216 && enode
->get_point ().get_call_string () == *cs
)
4223 pp_printf (pp
, ": %i\n", num_enodes
);
4224 pp_write_text_as_html_like_dot_to_stream (pp
);
4229 /* Show any summaries. */
4230 per_function_data
*data
= args
.m_eg
->get_per_function_data (m_fun
);
4235 pp_printf (pp
, "summaries: %i\n", data
->m_summaries
.length ());
4236 pp_write_text_as_html_like_dot_to_stream (pp
);
4241 pp_string (pp
, "</TABLE>>];\n\n");
4245 void dump_dot_id (pretty_printer
*pp
) const
4247 pp_printf (pp
, "vcg_%i", m_index
);
4253 int m_num_supernodes
;
4254 int m_num_superedges
;
4257 /* Subclass of dedge representing a callgraph edge. */
4259 class viz_callgraph_edge
: public dedge
<viz_callgraph_traits
>
4262 viz_callgraph_edge (viz_callgraph_node
*src
, viz_callgraph_node
*dest
)
4263 : dedge
<viz_callgraph_traits
> (src
, dest
)
4266 void dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
4269 pretty_printer
*pp
= gv
->get_pp ();
4271 const char *style
= "\"solid,bold\"";
4272 const char *color
= "black";
4274 const char *constraint
= "true";
4276 m_src
->dump_dot_id (pp
);
4277 pp_string (pp
, " -> ");
4278 m_dest
->dump_dot_id (pp
);
4280 (" [style=%s, color=%s, weight=%d, constraint=%s,"
4282 style
, color
, weight
, constraint
);
4283 pp_printf (pp
, "\"];\n");
4287 /* Subclass of digraph representing the callgraph. */
4289 class viz_callgraph
: public digraph
<viz_callgraph_traits
>
4292 viz_callgraph (const supergraph
&sg
);
4294 viz_callgraph_node
*get_vcg_node_for_function (function
*fun
)
4296 return *m_map
.get (fun
);
4299 viz_callgraph_node
*get_vcg_node_for_snode (supernode
*snode
)
4301 return get_vcg_node_for_function (snode
->m_fun
);
4305 hash_map
<function
*, viz_callgraph_node
*> m_map
;
4308 /* Placeholder subclass of cluster. */
4310 class viz_callgraph_cluster
: public cluster
<viz_callgraph_traits
>
4314 /* viz_callgraph's ctor. */
4316 viz_callgraph::viz_callgraph (const supergraph
&sg
)
4319 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4321 function
*fun
= node
->get_fun ();
4322 viz_callgraph_node
*vcg_node
4323 = new viz_callgraph_node (fun
, m_nodes
.length ());
4324 m_map
.put (fun
, vcg_node
);
4325 add_node (vcg_node
);
4330 FOR_EACH_VEC_ELT (sg
.m_edges
, i
, sedge
)
4332 viz_callgraph_node
*vcg_src
= get_vcg_node_for_snode (sedge
->m_src
);
4334 get_vcg_node_for_function (vcg_src
->m_fun
)->m_num_superedges
++;
4335 if (sedge
->dyn_cast_call_superedge ())
4337 viz_callgraph_node
*vcg_dest
= get_vcg_node_for_snode (sedge
->m_dest
);
4338 viz_callgraph_edge
*vcg_edge
4339 = new viz_callgraph_edge (vcg_src
, vcg_dest
);
4340 add_edge (vcg_edge
);
4345 FOR_EACH_VEC_ELT (sg
.m_nodes
, i
, snode
)
4348 get_vcg_node_for_function (snode
->m_fun
)->m_num_supernodes
++;
4352 /* Dump the callgraph to FILENAME. */
4355 dump_callgraph (const supergraph
&sg
, const char *filename
,
4356 const exploded_graph
*eg
)
4358 FILE *outf
= fopen (filename
, "w");
4363 viz_callgraph
vcg (sg
);
4364 vcg
.dump_dot (filename
, NULL
, viz_callgraph_traits::dump_args_t (eg
));
4369 /* Dump the callgraph to "<srcfile>.callgraph.dot". */
4372 dump_callgraph (const supergraph
&sg
, const exploded_graph
*eg
)
4374 auto_timevar
tv (TV_ANALYZER_DUMP
);
4375 char *filename
= concat (dump_base_name
, ".callgraph.dot", NULL
);
4376 dump_callgraph (sg
, filename
, eg
);
4380 /* Subclass of dot_annotator for implementing
4381 DUMP_BASE_NAME.supergraph-eg.dot, a post-analysis dump of the supergraph.
4383 Annotate the supergraph nodes by printing the exploded nodes in concise
4384 form within them, next to their pertinent statements where appropriate,
4385 colorizing the exploded nodes based on sm-state.
4386 Also show saved diagnostics within the exploded nodes, giving information
4387 on whether they were feasible, and, if infeasible, where the problem
4390 class exploded_graph_annotator
: public dot_annotator
4393 exploded_graph_annotator (const exploded_graph
&eg
)
4396 /* Avoid O(N^2) by prepopulating m_enodes_per_snodes. */
4399 FOR_EACH_VEC_ELT (eg
.get_supergraph ().m_nodes
, i
, snode
)
4400 m_enodes_per_snodes
.safe_push (new auto_vec
<exploded_node
*> ());
4401 exploded_node
*enode
;
4402 FOR_EACH_VEC_ELT (m_eg
.m_nodes
, i
, enode
)
4403 if (enode
->get_supernode ())
4404 m_enodes_per_snodes
[enode
->get_supernode ()->m_index
]->safe_push (enode
);
4407 /* Show exploded nodes for BEFORE_SUPERNODE points before N. */
4408 bool add_node_annotations (graphviz_out
*gv
, const supernode
&n
,
4410 const FINAL OVERRIDE
4415 pretty_printer
*pp
= gv
->get_pp ();
4418 pp_string (pp
, "BEFORE");
4419 pp_printf (pp
, " (scc: %i)", m_eg
.get_scc_id (n
));
4423 exploded_node
*enode
;
4424 bool had_enode
= false;
4425 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[n
.m_index
], i
, enode
)
4427 gcc_assert (enode
->get_supernode () == &n
);
4428 const program_point
&point
= enode
->get_point ();
4429 if (point
.get_kind () != PK_BEFORE_SUPERNODE
)
4431 print_enode (gv
, enode
);
4435 pp_string (pp
, "<TD BGCOLOR=\"red\">UNREACHED</TD>");
4441 /* Show exploded nodes for STMT. */
4442 void add_stmt_annotations (graphviz_out
*gv
, const gimple
*stmt
,
4444 const FINAL OVERRIDE
4448 pretty_printer
*pp
= gv
->get_pp ();
4450 const supernode
*snode
4451 = m_eg
.get_supergraph ().get_supernode_for_stmt (stmt
);
4453 exploded_node
*enode
;
4454 bool had_td
= false;
4455 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[snode
->m_index
], i
, enode
)
4457 const program_point
&point
= enode
->get_point ();
4458 if (point
.get_kind () != PK_BEFORE_STMT
)
4460 if (point
.get_stmt () != stmt
)
4462 print_enode (gv
, enode
);
4473 /* Show exploded nodes for AFTER_SUPERNODE points after N. */
4474 bool add_after_node_annotations (graphviz_out
*gv
, const supernode
&n
)
4475 const FINAL OVERRIDE
4478 pretty_printer
*pp
= gv
->get_pp ();
4481 pp_string (pp
, "AFTER");
4485 exploded_node
*enode
;
4486 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[n
.m_index
], i
, enode
)
4488 gcc_assert (enode
->get_supernode () == &n
);
4489 const program_point
&point
= enode
->get_point ();
4490 if (point
.get_kind () != PK_AFTER_SUPERNODE
)
4492 print_enode (gv
, enode
);
4500 /* Concisely print a TD element for ENODE, showing the index, status,
4501 and any saved_diagnostics at the enode. Colorize it to show sm-state.
4503 Ideally we'd dump ENODE's state here, hidden behind some kind of
4504 interactive disclosure method like a tooltip, so that the states
4505 can be explored without overwhelming the graph.
4506 However, I wasn't able to get graphviz/xdot to show tooltips on
4507 individual elements within a HTML-like label. */
4508 void print_enode (graphviz_out
*gv
, const exploded_node
*enode
) const
4510 pretty_printer
*pp
= gv
->get_pp ();
4511 pp_printf (pp
, "<TD BGCOLOR=\"%s\">",
4512 enode
->get_dot_fillcolor ());
4513 pp_printf (pp
, "<TABLE BORDER=\"0\">");
4515 pp_printf (pp
, "EN: %i", enode
->m_index
);
4516 switch (enode
->get_status ())
4520 case exploded_node::STATUS_WORKLIST
:
4521 pp_string (pp
, "(W)");
4523 case exploded_node::STATUS_PROCESSED
:
4525 case exploded_node::STATUS_MERGER
:
4526 pp_string (pp
, "(M)");
4528 case exploded_node::STATUS_BULK_MERGED
:
4529 pp_string (pp
, "(BM)");
4533 /* Dump any saved_diagnostics at this enode. */
4535 const diagnostic_manager
&dm
= m_eg
.get_diagnostic_manager ();
4536 for (unsigned i
= 0; i
< dm
.get_num_diagnostics (); i
++)
4538 const saved_diagnostic
*sd
= dm
.get_saved_diagnostic (i
);
4539 if (sd
->m_enode
== enode
)
4540 print_saved_diagnostic (gv
, sd
);
4543 pp_printf (pp
, "</TABLE>");
4544 pp_printf (pp
, "</TD>");
4547 /* Print a TABLE element for SD, showing the kind, the length of the
4548 exploded_path, whether the path was feasible, and if infeasible,
4549 what the problem was. */
4550 void print_saved_diagnostic (graphviz_out
*gv
,
4551 const saved_diagnostic
*sd
) const
4553 pretty_printer
*pp
= gv
->get_pp ();
4555 pp_printf (pp
, "<TABLE BORDER=\"0\">");
4557 pp_string (pp
, "<TD BGCOLOR=\"green\">");
4558 pp_printf (pp
, "DIAGNOSTIC: %s", sd
->m_d
->get_kind ());
4561 pp_printf (pp
, "epath length: %i", sd
->get_epath_length ());
4563 switch (sd
->get_status ())
4566 case saved_diagnostic::STATUS_NEW
:
4569 case saved_diagnostic::STATUS_INFEASIBLE_PATH
:
4572 pp_printf (pp
, "INFEASIBLE");
4574 const feasibility_problem
*p
= sd
->get_feasibility_problem ();
4577 pp_printf (pp
, "at eedge %i: EN:%i -> EN:%i",
4579 p
->m_eedge
.m_src
->m_index
,
4580 p
->m_eedge
.m_dest
->m_index
);
4581 pp_write_text_as_html_like_dot_to_stream (pp
);
4584 p
->m_eedge
.m_sedge
->dump (pp
);
4585 pp_write_text_as_html_like_dot_to_stream (pp
);
4588 pp_gimple_stmt_1 (pp
, p
->m_last_stmt
, 0, (dump_flags_t
)0);
4589 pp_write_text_as_html_like_dot_to_stream (pp
);
4591 /* Ideally we'd print p->m_model here; see the notes above about
4595 case saved_diagnostic::STATUS_FEASIBLE_PATH
:
4597 pp_printf (pp
, "FEASIBLE");
4601 pp_printf (pp
, "</TABLE>");
4605 const exploded_graph
&m_eg
;
4606 auto_delete_vec
<auto_vec
<exploded_node
*> > m_enodes_per_snodes
;
4609 /* Implement -fdump-analyzer-json. */
4612 dump_analyzer_json (const supergraph
&sg
,
4613 const exploded_graph
&eg
)
4615 auto_timevar
tv (TV_ANALYZER_DUMP
);
4616 char *filename
= concat (dump_base_name
, ".analyzer.json.gz", NULL
);
4617 gzFile output
= gzopen (filename
, "w");
4620 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
4625 json::object
*toplev_obj
= new json::object ();
4626 toplev_obj
->set ("sgraph", sg
.to_json ());
4627 toplev_obj
->set ("egraph", eg
.to_json ());
4630 toplev_obj
->print (&pp
);
4631 pp_formatted_text (&pp
);
4635 if (gzputs (output
, pp_formatted_text (&pp
)) == EOF
4636 || gzclose (output
))
4637 error_at (UNKNOWN_LOCATION
, "error writing %qs", filename
);
4642 /* Concrete subclass of plugin_analyzer_init_iface, allowing plugins
4643 to register new state machines. */
4645 class plugin_analyzer_init_impl
: public plugin_analyzer_init_iface
4648 plugin_analyzer_init_impl (auto_delete_vec
<state_machine
> *checkers
,
4650 : m_checkers (checkers
),
4654 void register_state_machine (state_machine
*sm
) FINAL OVERRIDE
4656 m_checkers
->safe_push (sm
);
4659 logger
*get_logger () const FINAL OVERRIDE
4665 auto_delete_vec
<state_machine
> *m_checkers
;
4669 /* Run the analysis "engine". */
4672 impl_run_checkers (logger
*logger
)
4676 /* If using LTO, ensure that the cgraph nodes have function bodies. */
4678 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4679 node
->get_untransformed_body ();
4683 /* Create the supergraph. */
4684 supergraph
sg (logger
);
4686 state_purge_map
*purge_map
= NULL
;
4688 if (flag_analyzer_state_purge
)
4689 purge_map
= new state_purge_map (sg
, logger
);
4691 if (flag_dump_analyzer_supergraph
)
4693 /* Dump supergraph pre-analysis. */
4694 auto_timevar
tv (TV_ANALYZER_DUMP
);
4695 char *filename
= concat (dump_base_name
, ".supergraph.dot", NULL
);
4696 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, NULL
);
4697 sg
.dump_dot (filename
, args
);
4701 if (flag_dump_analyzer_state_purge
)
4703 auto_timevar
tv (TV_ANALYZER_DUMP
);
4704 state_purge_annotator
a (purge_map
);
4705 char *filename
= concat (dump_base_name
, ".state-purge.dot", NULL
);
4706 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, &a
);
4707 sg
.dump_dot (filename
, args
);
4711 auto_delete_vec
<state_machine
> checkers
;
4712 make_checkers (checkers
, logger
);
4714 plugin_analyzer_init_impl
data (&checkers
, logger
);
4715 invoke_plugin_callbacks (PLUGIN_ANALYZER_INIT
, &data
);
4721 FOR_EACH_VEC_ELT (checkers
, i
, sm
)
4722 logger
->log ("checkers[%i]: %s", i
, sm
->get_name ());
4725 /* Extrinsic state shared by nodes in the graph. */
4726 const extrinsic_state
ext_state (checkers
, &eng
, logger
);
4728 const analysis_plan
plan (sg
, logger
);
4730 /* The exploded graph. */
4731 exploded_graph
eg (sg
, logger
, ext_state
, purge_map
, plan
,
4732 analyzer_verbosity
);
4734 /* Add entrypoints to the graph for externally-callable functions. */
4735 eg
.build_initial_worklist ();
4737 /* Now process the worklist, exploring the <point, state> graph. */
4738 eg
.process_worklist ();
4740 if (flag_dump_analyzer_exploded_graph
)
4742 auto_timevar
tv (TV_ANALYZER_DUMP
);
4744 = concat (dump_base_name
, ".eg.dot", NULL
);
4745 exploded_graph::dump_args_t
args (eg
);
4747 eg
.dump_dot (filename
, &c
, args
);
4751 /* Now emit any saved diagnostics. */
4752 eg
.get_diagnostic_manager ().emit_saved_diagnostics (eg
);
4754 eg
.dump_exploded_nodes ();
4758 if (flag_dump_analyzer_callgraph
)
4759 dump_callgraph (sg
, &eg
);
4761 if (flag_dump_analyzer_supergraph
)
4763 /* Dump post-analysis form of supergraph. */
4764 auto_timevar
tv (TV_ANALYZER_DUMP
);
4765 char *filename
= concat (dump_base_name
, ".supergraph-eg.dot", NULL
);
4766 exploded_graph_annotator
a (eg
);
4767 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, &a
);
4768 sg
.dump_dot (filename
, args
);
4772 if (flag_dump_analyzer_json
)
4773 dump_analyzer_json (sg
, eg
);
4778 /* External entrypoint to the analysis "engine".
4779 Set up any dumps, then call impl_run_checkers. */
4784 /* Save input_location. */
4785 location_t saved_input_location
= input_location
;
4787 /* Handle -fdump-analyzer and -fdump-analyzer-stderr. */
4788 FILE *dump_fout
= NULL
;
4789 /* Track if we're responsible for closing dump_fout. */
4790 bool owns_dump_fout
= false;
4791 if (flag_dump_analyzer_stderr
)
4793 else if (flag_dump_analyzer
)
4795 char *dump_filename
= concat (dump_base_name
, ".analyzer.txt", NULL
);
4796 dump_fout
= fopen (dump_filename
, "w");
4797 free (dump_filename
);
4799 owns_dump_fout
= true;
4803 log_user
the_logger (NULL
);
4805 the_logger
.set_logger (new logger (dump_fout
, 0, 0,
4806 *global_dc
->printer
));
4807 LOG_SCOPE (the_logger
.get_logger ());
4809 impl_run_checkers (the_logger
.get_logger ());
4811 /* end of lifetime of the_logger (so that dump file is closed after the
4812 various dtors run). */
4818 /* Restore input_location. Subsequent passes may assume that input_location
4819 is some arbitrary value *not* in the block tree, which might be violated
4820 if we didn't restore it. */
4821 input_location
= saved_input_location
;
4826 #endif /* #if ENABLE_ANALYZER */