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"
67 /* For an overview, see gcc/doc/analyzer.texi. */
73 /* class impl_region_model_context : public region_model_context. */
75 impl_region_model_context::
76 impl_region_model_context (exploded_graph
&eg
,
77 const exploded_node
*enode_for_diag
,
78 const program_state
*old_state
,
79 program_state
*new_state
,
81 stmt_finder
*stmt_finder
)
82 : m_eg (&eg
), m_logger (eg
.get_logger ()),
83 m_enode_for_diag (enode_for_diag
),
84 m_old_state (old_state
),
85 m_new_state (new_state
),
87 m_stmt_finder (stmt_finder
),
88 m_ext_state (eg
.get_ext_state ())
92 impl_region_model_context::
93 impl_region_model_context (program_state
*state
,
94 const extrinsic_state
&ext_state
,
96 : m_eg (NULL
), m_logger (logger
), m_enode_for_diag (NULL
),
100 m_stmt_finder (NULL
),
101 m_ext_state (ext_state
)
106 impl_region_model_context::warn (pending_diagnostic
*d
)
108 LOG_FUNC (get_logger ());
110 m_eg
->get_diagnostic_manager ().add_diagnostic
111 (m_enode_for_diag
, m_enode_for_diag
->get_supernode (),
112 m_stmt
, m_stmt_finder
, d
);
116 impl_region_model_context::on_svalue_leak (const svalue
*sval
)
121 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
122 smap
->on_svalue_leak (sval
, this);
126 impl_region_model_context::
127 on_liveness_change (const svalue_set
&live_svalues
,
128 const region_model
*model
)
132 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
133 smap
->on_liveness_change (live_svalues
, model
, this);
137 impl_region_model_context::on_unknown_change (const svalue
*sval
,
142 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
143 smap
->on_unknown_change (sval
, is_mutable
, m_ext_state
);
147 impl_region_model_context::on_escaped_function (tree fndecl
)
149 m_eg
->on_escaped_function (fndecl
);
152 /* class setjmp_svalue : public svalue. */
154 /* Implementation of svalue::accept vfunc for setjmp_svalue. */
157 setjmp_svalue::accept (visitor
*v
) const
159 v
->visit_setjmp_svalue (this);
162 /* Implementation of svalue::dump_to_pp vfunc for setjmp_svalue. */
165 setjmp_svalue::dump_to_pp (pretty_printer
*pp
, bool simple
) const
168 pp_printf (pp
, "SETJMP(EN: %i)", get_enode_index ());
170 pp_printf (pp
, "setjmp_svalue(EN%i)", get_enode_index ());
173 /* Get the index of the stored exploded_node. */
176 setjmp_svalue::get_enode_index () const
178 return m_setjmp_record
.m_enode
->m_index
;
181 /* Concrete implementation of sm_context, wiring it up to the rest of this
184 class impl_sm_context
: public sm_context
187 impl_sm_context (exploded_graph
&eg
,
189 const state_machine
&sm
,
190 const exploded_node
*enode_for_diag
,
191 const program_state
*old_state
,
192 program_state
*new_state
,
193 const sm_state_map
*old_smap
,
194 sm_state_map
*new_smap
,
195 stmt_finder
*stmt_finder
= NULL
)
196 : sm_context (sm_idx
, sm
),
197 m_logger (eg
.get_logger ()),
198 m_eg (eg
), m_enode_for_diag (enode_for_diag
),
199 m_old_state (old_state
), m_new_state (new_state
),
200 m_old_smap (old_smap
), m_new_smap (new_smap
),
201 m_stmt_finder (stmt_finder
)
205 logger
*get_logger () const { return m_logger
.get_logger (); }
207 tree
get_fndecl_for_call (const gcall
*call
) FINAL OVERRIDE
209 impl_region_model_context old_ctxt
210 (m_eg
, m_enode_for_diag
, NULL
, NULL
/*m_enode->get_state ()*/,
212 region_model
*model
= m_new_state
->m_region_model
;
213 return model
->get_fndecl_for_call (call
, &old_ctxt
);
216 state_machine::state_t
get_state (const gimple
*stmt
,
219 logger
* const logger
= get_logger ();
221 impl_region_model_context old_ctxt
222 (m_eg
, m_enode_for_diag
, NULL
, NULL
/*m_enode->get_state ()*/,
224 const svalue
*var_old_sval
225 = m_old_state
->m_region_model
->get_rvalue (var
, &old_ctxt
);
227 state_machine::state_t current
228 = m_old_smap
->get_state (var_old_sval
, m_eg
.get_ext_state ());
232 void set_next_state (const gimple
*stmt
,
234 state_machine::state_t to
,
237 logger
* const logger
= get_logger ();
239 impl_region_model_context old_ctxt
240 (m_eg
, m_enode_for_diag
, NULL
, NULL
/*m_enode->get_state ()*/,
242 const svalue
*var_old_sval
243 = m_old_state
->m_region_model
->get_rvalue (var
, &old_ctxt
);
245 impl_region_model_context
new_ctxt (m_eg
, m_enode_for_diag
,
246 m_old_state
, m_new_state
,
248 const svalue
*var_new_sval
249 = m_new_state
->m_region_model
->get_rvalue (var
, &new_ctxt
);
250 const svalue
*origin_new_sval
251 = m_new_state
->m_region_model
->get_rvalue (origin
, &new_ctxt
);
253 state_machine::state_t current
254 = m_old_smap
->get_state (var_old_sval
, m_eg
.get_ext_state ());
256 logger
->log ("%s: state transition of %qE: %s -> %s",
259 current
->get_name (),
261 m_new_smap
->set_state (m_new_state
->m_region_model
, var_new_sval
,
262 to
, origin_new_sval
, m_eg
.get_ext_state ());
265 void warn (const supernode
*snode
, const gimple
*stmt
,
266 tree var
, pending_diagnostic
*d
) FINAL OVERRIDE
268 LOG_FUNC (get_logger ());
269 gcc_assert (d
); // take ownership
270 impl_region_model_context old_ctxt
271 (m_eg
, m_enode_for_diag
, m_old_state
, m_new_state
, NULL
);
273 const svalue
*var_old_sval
274 = m_old_state
->m_region_model
->get_rvalue (var
, &old_ctxt
);
275 state_machine::state_t current
277 ? m_old_smap
->get_state (var_old_sval
, m_eg
.get_ext_state ())
278 : m_old_smap
->get_global_state ());
279 m_eg
.get_diagnostic_manager ().add_diagnostic
280 (&m_sm
, m_enode_for_diag
, snode
, stmt
, m_stmt_finder
,
281 var
, var_old_sval
, current
, d
);
284 /* Hook for picking more readable trees for SSA names of temporaries,
285 so that rather than e.g.
286 "double-free of '<unknown>'"
288 "double-free of 'inbuf.data'". */
290 tree
get_diagnostic_tree (tree expr
) FINAL OVERRIDE
292 /* Only for SSA_NAMEs of temporaries; otherwise, return EXPR, as it's
293 likely to be the least surprising tree to report. */
294 if (TREE_CODE (expr
) != SSA_NAME
)
296 if (SSA_NAME_VAR (expr
) != NULL
)
299 gcc_assert (m_new_state
);
300 const svalue
*sval
= m_new_state
->m_region_model
->get_rvalue (expr
, NULL
);
301 /* Find trees for all regions storing the value. */
302 if (tree t
= m_new_state
->m_region_model
->get_representative_tree (sval
))
308 state_machine::state_t
get_global_state () const FINAL OVERRIDE
310 return m_old_state
->m_checker_states
[m_sm_idx
]->get_global_state ();
313 void set_global_state (state_machine::state_t state
) FINAL OVERRIDE
315 m_new_state
->m_checker_states
[m_sm_idx
]->set_global_state (state
);
318 void on_custom_transition (custom_transition
*transition
) FINAL OVERRIDE
320 transition
->impl_transition (&m_eg
,
321 const_cast<exploded_node
*> (m_enode_for_diag
),
325 tree
is_zero_assignment (const gimple
*stmt
) FINAL OVERRIDE
327 const gassign
*assign_stmt
= dyn_cast
<const gassign
*> (stmt
);
330 impl_region_model_context old_ctxt
331 (m_eg
, m_enode_for_diag
, m_old_state
, m_new_state
, stmt
);
332 if (const svalue
*sval
333 = m_new_state
->m_region_model
->get_gassign_result (assign_stmt
,
335 if (tree cst
= sval
->maybe_get_constant ())
337 return gimple_assign_lhs (assign_stmt
);
342 exploded_graph
&m_eg
;
343 const exploded_node
*m_enode_for_diag
;
344 const program_state
*m_old_state
;
345 program_state
*m_new_state
;
346 const sm_state_map
*m_old_smap
;
347 sm_state_map
*m_new_smap
;
348 stmt_finder
*m_stmt_finder
;
351 /* Subclass of stmt_finder for finding the best stmt to report the leak at,
352 given the emission path. */
354 class leak_stmt_finder
: public stmt_finder
357 leak_stmt_finder (const exploded_graph
&eg
, tree var
)
358 : m_eg (eg
), m_var (var
) {}
360 stmt_finder
*clone () const FINAL OVERRIDE
362 return new leak_stmt_finder (m_eg
, m_var
);
365 const gimple
*find_stmt (const exploded_path
&epath
)
368 logger
* const logger
= m_eg
.get_logger ();
371 if (m_var
&& TREE_CODE (m_var
) == SSA_NAME
)
373 /* Locate the final write to this SSA name in the path. */
374 const gimple
*def_stmt
= SSA_NAME_DEF_STMT (m_var
);
377 bool found
= epath
.find_stmt_backwards (def_stmt
, &idx_of_def_stmt
);
381 /* What was the next write to the underlying var
382 after the SSA name was set? (if any). */
384 for (unsigned idx
= idx_of_def_stmt
+ 1;
385 idx
< epath
.m_edges
.length ();
388 const exploded_edge
*eedge
= epath
.m_edges
[idx
];
390 logger
->log ("eedge[%i]: EN %i -> EN %i",
392 eedge
->m_src
->m_index
,
393 eedge
->m_dest
->m_index
);
394 const exploded_node
*dst_node
= eedge
->m_dest
;
395 const program_point
&dst_point
= dst_node
->get_point ();
396 const gimple
*stmt
= dst_point
.get_stmt ();
399 if (const gassign
*assign
= dyn_cast
<const gassign
*> (stmt
))
401 tree lhs
= gimple_assign_lhs (assign
);
402 if (TREE_CODE (lhs
) == SSA_NAME
403 && SSA_NAME_VAR (lhs
) == SSA_NAME_VAR (m_var
))
411 /* Look backwards for the first statement with a location. */
413 const exploded_edge
*eedge
;
414 FOR_EACH_VEC_ELT_REVERSE (epath
.m_edges
, i
, eedge
)
417 logger
->log ("eedge[%i]: EN %i -> EN %i",
419 eedge
->m_src
->m_index
,
420 eedge
->m_dest
->m_index
);
421 const exploded_node
*dst_node
= eedge
->m_dest
;
422 const program_point
&dst_point
= dst_node
->get_point ();
423 const gimple
*stmt
= dst_point
.get_stmt ();
425 if (get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
434 const exploded_graph
&m_eg
;
438 /* A measurement of how good EXPR is for presenting to the user, so
439 that e.g. we can say prefer printing
440 "leak of 'tmp.m_ptr'"
442 "leak of '<unknown>'". */
445 readability (const_tree expr
)
448 switch (TREE_CODE (expr
))
452 /* Impose a slight readability penalty relative to that of
454 return readability (TREE_OPERAND (expr
, 0)) - 16;
458 if (tree var
= SSA_NAME_VAR (expr
))
459 /* Slightly favor the underlying var over the SSA name to
460 avoid having them compare equal. */
461 return readability (var
) - 1;
462 /* Avoid printing '<unknown>' for SSA names for temporaries. */
469 if (DECL_NAME (expr
))
470 /* Arbitrarily-chosen "high readability" value. */
473 /* We don't want to print temporaries. For example, the C FE
474 prints them as e.g. "<Uxxxx>" where "xxxx" is the low 16 bits
475 of the tree pointer (see pp_c_tree_decl_identifier). */
479 /* Printing "<return-value>" isn't ideal, but is less awful than
480 trying to print a temporary. */
490 /* A qsort comparator for trees to sort them into most user-readable to
491 least user-readable. */
494 readability_comparator (const void *p1
, const void *p2
)
496 path_var pv1
= *(path_var
const *)p1
;
497 path_var pv2
= *(path_var
const *)p2
;
499 int r1
= readability (pv1
.m_tree
);
500 int r2
= readability (pv2
.m_tree
);
501 if (int cmp
= r2
- r1
)
504 /* Favor items that are deeper on the stack and hence more recent;
505 this also favors locals over globals. */
506 if (int cmp
= pv2
.m_stack_depth
- pv1
.m_stack_depth
)
509 /* TODO: We ought to find ways of sorting such cases. */
513 /* Find the best tree for SVAL and call SM's on_leak vfunc with it.
514 If on_leak returns a pending_diagnostic, queue it up to be reported,
515 so that we potentially complain about a leak of SVAL in the given STATE. */
518 impl_region_model_context::on_state_leak (const state_machine
&sm
,
520 state_machine::state_t state
)
522 logger
* const logger
= get_logger ();
526 logger
->start_log_line ();
527 logger
->log_partial ("considering leak of ");
528 sval
->dump_to_pp (logger
->get_printer (), true);
529 logger
->end_log_line ();
535 /* m_old_state also needs to be non-NULL so that the sm_ctxt can look
536 up the old state of SVAL. */
537 gcc_assert (m_old_state
);
539 /* SVAL has leaked within the new state: it is not used by any reachable
541 We need to convert it back to a tree, but since it's likely no regions
542 use it, we have to find the "best" tree for it in the old_state. */
545 = m_old_state
->m_region_model
->get_representative_path_var (sval
,
548 /* This might be NULL; the pending_diagnostic subclasses need to cope
550 tree leaked_tree
= leaked_pv
.m_tree
;
554 logger
->log ("best leaked_tree: %qE", leaked_tree
);
556 logger
->log ("best leaked_tree: NULL");
559 leak_stmt_finder
stmt_finder (*m_eg
, leaked_tree
);
560 gcc_assert (m_enode_for_diag
);
562 /* Don't complain about leaks when returning from "main". */
563 if (m_enode_for_diag
->get_supernode ()
564 && m_enode_for_diag
->get_supernode ()->return_p ())
566 tree fndecl
= m_enode_for_diag
->get_function ()->decl
;
567 if (id_equal (DECL_NAME (fndecl
), "main"))
570 logger
->log ("not reporting leak from main");
575 pending_diagnostic
*pd
= sm
.on_leak (leaked_tree
);
577 m_eg
->get_diagnostic_manager ().add_diagnostic
578 (&sm
, m_enode_for_diag
, m_enode_for_diag
->get_supernode (),
579 m_stmt
, &stmt_finder
,
580 leaked_tree
, sval
, state
, pd
);
583 /* Implementation of region_model_context::on_condition vfunc.
584 Notify all state machines about the condition, which could lead to
585 state transitions. */
588 impl_region_model_context::on_condition (tree lhs
, enum tree_code op
, tree rhs
)
592 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
594 const state_machine
&sm
= m_ext_state
.get_sm (sm_idx
);
595 impl_sm_context
sm_ctxt (*m_eg
, sm_idx
, sm
, m_enode_for_diag
,
596 m_old_state
, m_new_state
,
597 m_old_state
->m_checker_states
[sm_idx
],
598 m_new_state
->m_checker_states
[sm_idx
]);
599 sm
.on_condition (&sm_ctxt
,
600 m_enode_for_diag
->get_supernode (), m_stmt
,
605 /* Implementation of region_model_context::on_phi vfunc.
606 Notify all state machines about the phi, which could lead to
607 state transitions. */
610 impl_region_model_context::on_phi (const gphi
*phi
, tree rhs
)
614 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
616 const state_machine
&sm
= m_ext_state
.get_sm (sm_idx
);
617 impl_sm_context
sm_ctxt (*m_eg
, sm_idx
, sm
, m_enode_for_diag
,
618 m_old_state
, m_new_state
,
619 m_old_state
->m_checker_states
[sm_idx
],
620 m_new_state
->m_checker_states
[sm_idx
]);
621 sm
.on_phi (&sm_ctxt
, m_enode_for_diag
->get_supernode (), phi
, rhs
);
625 /* Implementation of region_model_context::on_unexpected_tree_code vfunc.
626 Mark the new state as being invalid for further exploration.
627 TODO(stage1): introduce a warning for when this occurs. */
630 impl_region_model_context::on_unexpected_tree_code (tree t
,
631 const dump_location_t
&loc
)
633 logger
* const logger
= get_logger ();
635 logger
->log ("unhandled tree code: %qs in %qs at %s:%i",
636 get_tree_code_name (TREE_CODE (t
)),
637 loc
.get_impl_location ().m_function
,
638 loc
.get_impl_location ().m_file
,
639 loc
.get_impl_location ().m_line
);
641 m_new_state
->m_valid
= false;
644 /* struct point_and_state. */
646 /* Assert that this object is sane. */
649 point_and_state::validate (const extrinsic_state
&ext_state
) const
651 /* Skip this in a release build. */
658 m_state
.validate (ext_state
);
660 /* Verify that the callstring's model of the stack corresponds to that
661 of the region_model. */
662 /* They should have the same depth. */
663 gcc_assert (m_point
.get_stack_depth ()
664 == m_state
.m_region_model
->get_stack_depth ());
665 /* Check the functions in the callstring vs those in the frames
667 for (const frame_region
*iter_frame
668 = m_state
.m_region_model
->get_current_frame ();
669 iter_frame
; iter_frame
= iter_frame
->get_calling_frame ())
671 int index
= iter_frame
->get_index ();
672 gcc_assert (m_point
.get_function_at_depth (index
)
673 == iter_frame
->get_function ());
677 /* Subroutine of print_enode_indices: print a run of indices from START_IDX
678 to END_IDX to PP, using and updating *FIRST_RUN. */
681 print_run (pretty_printer
*pp
, int start_idx
, int end_idx
,
685 pp_string (pp
, ", ");
687 if (start_idx
== end_idx
)
688 pp_printf (pp
, "EN: %i", start_idx
);
690 pp_printf (pp
, "EN: %i-%i", start_idx
, end_idx
);
693 /* Print the indices within ENODES to PP, collecting them as
694 runs/singletons e.g. "EN: 4-7, EN: 20-23, EN: 42". */
697 print_enode_indices (pretty_printer
*pp
,
698 const auto_vec
<exploded_node
*> &enodes
)
700 int cur_start_idx
= -1;
701 int cur_finish_idx
= -1;
702 bool first_run
= true;
704 exploded_node
*enode
;
705 FOR_EACH_VEC_ELT (enodes
, i
, enode
)
707 if (cur_start_idx
== -1)
709 gcc_assert (cur_finish_idx
== -1);
710 cur_start_idx
= cur_finish_idx
= enode
->m_index
;
714 if (enode
->m_index
== cur_finish_idx
+ 1)
715 /* Continuation of a run. */
716 cur_finish_idx
= enode
->m_index
;
719 /* Finish existing run, start a new one. */
720 gcc_assert (cur_start_idx
>= 0);
721 gcc_assert (cur_finish_idx
>= 0);
722 print_run (pp
, cur_start_idx
, cur_finish_idx
,
724 cur_start_idx
= cur_finish_idx
= enode
->m_index
;
728 /* Finish any existing run. */
729 if (cur_start_idx
>= 0)
731 gcc_assert (cur_finish_idx
>= 0);
732 print_run (pp
, cur_start_idx
, cur_finish_idx
,
737 /* struct eg_traits::dump_args_t. */
739 /* The <FILENAME>.eg.dot output can quickly become unwieldy if we show
740 full details for all enodes (both in terms of CPU time to render it,
741 and in terms of being meaningful to a human viewing it).
743 If we show just the IDs then the resulting graph is usually viewable,
744 but then we have to keep switching back and forth between the .dot
745 view and other dumps.
747 This function implements a heuristic for showing detail at the enodes
748 that (we hope) matter, and just the ID at other enodes, fixing the CPU
749 usage of the .dot viewer, and drawing the attention of the viewer
752 Return true if ENODE should be shown in detail in .dot output.
753 Return false if no detail should be shown for ENODE. */
756 eg_traits::dump_args_t::show_enode_details_p (const exploded_node
&enode
) const
758 /* If the number of exploded nodes isn't too large, we may as well show
759 all enodes in full detail in the .dot output. */
760 if (m_eg
.m_nodes
.length ()
761 <= (unsigned) param_analyzer_max_enodes_for_full_dump
)
764 /* Otherwise, assume that what's most interesting are state explosions,
765 and thus the places where this happened.
766 Expand enodes at program points where we hit the per-enode limit, so we
767 can investigate what exploded. */
768 const per_program_point_data
*per_point_data
769 = m_eg
.get_per_program_point_data (enode
.get_point ());
770 return per_point_data
->m_excess_enodes
> 0;
773 /* class exploded_node : public dnode<eg_traits>. */
776 exploded_node::status_to_str (enum status s
)
780 default: gcc_unreachable ();
781 case STATUS_WORKLIST
: return "WORKLIST";
782 case STATUS_PROCESSED
: return "PROCESSED";
783 case STATUS_MERGER
: return "MERGER";
784 case STATUS_BULK_MERGED
: return "BULK_MERGED";
788 /* exploded_node's ctor. */
790 exploded_node::exploded_node (const point_and_state
&ps
,
792 : m_ps (ps
), m_status (STATUS_WORKLIST
), m_index (index
),
793 m_num_processed_stmts (0)
795 gcc_checking_assert (ps
.get_state ().m_region_model
->canonicalized_p ());
798 /* Get the stmt that was processed in this enode at index IDX.
799 IDX is an index within the stmts processed at this enode, rather
800 than within those of the supernode. */
803 exploded_node::get_processed_stmt (unsigned idx
) const
805 gcc_assert (idx
< m_num_processed_stmts
);
806 const program_point
&point
= get_point ();
807 gcc_assert (point
.get_kind () == PK_BEFORE_STMT
);
808 const supernode
*snode
= get_supernode ();
809 const unsigned int point_stmt_idx
= point
.get_stmt_idx ();
810 const unsigned int idx_within_snode
= point_stmt_idx
+ idx
;
811 const gimple
*stmt
= snode
->m_stmts
[idx_within_snode
];
815 /* For use by dump_dot, get a value for the .dot "fillcolor" attribute.
816 Colorize by sm-state, to make it easier to see how sm-state propagates
817 through the exploded_graph. */
820 exploded_node::get_dot_fillcolor () const
822 const program_state
&state
= get_state ();
824 /* We want to be able to easily distinguish the no-sm-state case,
825 and to be able to distinguish cases where there's a single state
828 Sum the sm_states, and use the result to choose from a table,
829 modulo table-size, special-casing the "no sm-state" case. */
830 int total_sm_state
= 0;
833 FOR_EACH_VEC_ELT (state
.m_checker_states
, i
, smap
)
835 for (sm_state_map::iterator_t iter
= smap
->begin ();
836 iter
!= smap
->end ();
838 total_sm_state
+= (*iter
).second
.m_state
->get_id ();
839 total_sm_state
+= smap
->get_global_state ()->get_id ();
842 if (total_sm_state
> 0)
844 /* An arbitrarily-picked collection of light colors. */
845 const char * const colors
[]
846 = {"azure", "coral", "cornsilk", "lightblue", "yellow",
847 "honeydew", "lightpink", "lightsalmon", "palegreen1",
848 "wheat", "seashell"};
849 const int num_colors
= sizeof (colors
) / sizeof (colors
[0]);
850 return colors
[total_sm_state
% num_colors
];
857 /* Implementation of dnode::dump_dot vfunc for exploded_node. */
860 exploded_node::dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const
862 pretty_printer
*pp
= gv
->get_pp ();
865 pp_printf (pp
, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
866 get_dot_fillcolor ());
867 pp_write_text_to_stream (pp
);
869 pp_printf (pp
, "EN: %i", m_index
);
870 if (m_status
== STATUS_MERGER
)
871 pp_string (pp
, " (merger)");
872 else if (m_status
== STATUS_BULK_MERGED
)
873 pp_string (pp
, " (bulk merged)");
876 if (args
.show_enode_details_p (*this))
879 m_ps
.get_point ().print (pp
, f
);
882 const extrinsic_state
&ext_state
= args
.m_eg
.get_ext_state ();
883 const program_state
&state
= m_ps
.get_state ();
884 state
.dump_to_pp (ext_state
, false, true, pp
);
887 /* Show any stmts that were processed within this enode,
888 and their index within the supernode. */
889 if (m_num_processed_stmts
> 0)
891 const program_point
&point
= get_point ();
892 gcc_assert (point
.get_kind () == PK_BEFORE_STMT
);
893 const supernode
*snode
= get_supernode ();
894 const unsigned int point_stmt_idx
= point
.get_stmt_idx ();
896 pp_printf (pp
, "stmts: %i", m_num_processed_stmts
);
898 for (unsigned i
= 0; i
< m_num_processed_stmts
; i
++)
900 const unsigned int idx_within_snode
= point_stmt_idx
+ i
;
901 const gimple
*stmt
= snode
->m_stmts
[idx_within_snode
];
902 pp_printf (pp
, " %i: ", idx_within_snode
);
903 pp_gimple_stmt_1 (pp
, stmt
, 0, (dump_flags_t
)0);
909 /* Dump any saved_diagnostics at this enode. */
911 const diagnostic_manager
&dm
= args
.m_eg
.get_diagnostic_manager ();
912 for (unsigned i
= 0; i
< dm
.get_num_diagnostics (); i
++)
914 const saved_diagnostic
*sd
= dm
.get_saved_diagnostic (i
);
915 if (sd
->m_enode
== this)
917 pp_printf (pp
, "DIAGNOSTIC: %s", sd
->m_d
->get_kind ());
923 pp_write_text_as_dot_label_to_stream (pp
, /*for_record=*/true);
925 pp_string (pp
, "\"];\n\n");
929 /* Dump this to PP in a form suitable for use as an id in .dot output. */
932 exploded_node::dump_dot_id (pretty_printer
*pp
) const
934 pp_printf (pp
, "exploded_node_%i", m_index
);
937 /* Dump a multiline representation of this node to PP. */
940 exploded_node::dump_to_pp (pretty_printer
*pp
,
941 const extrinsic_state
&ext_state
) const
943 pp_printf (pp
, "EN: %i", m_index
);
947 m_ps
.get_point ().print (pp
, f
);
950 m_ps
.get_state ().dump_to_pp (ext_state
, false, true, pp
);
954 /* Dump a multiline representation of this node to FILE. */
957 exploded_node::dump (FILE *fp
,
958 const extrinsic_state
&ext_state
) const
961 pp_format_decoder (&pp
) = default_tree_printer
;
962 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
963 pp
.buffer
->stream
= fp
;
964 dump_to_pp (&pp
, ext_state
);
968 /* Dump a multiline representation of this node to stderr. */
971 exploded_node::dump (const extrinsic_state
&ext_state
) const
973 dump (stderr
, ext_state
);
976 /* Return a new json::object of the form
977 {"point" : object for program_point,
978 "state" : object for program_state,
981 "processed_stmts" : int}. */
984 exploded_node::to_json (const extrinsic_state
&ext_state
) const
986 json::object
*enode_obj
= new json::object ();
988 enode_obj
->set ("point", get_point ().to_json ());
989 enode_obj
->set ("state", get_state ().to_json (ext_state
));
990 enode_obj
->set ("status", new json::string (status_to_str (m_status
)));
991 enode_obj
->set ("idx", new json::integer_number (m_index
));
992 enode_obj
->set ("processed_stmts",
993 new json::integer_number (m_num_processed_stmts
));
1000 /* Return true if FNDECL has a gimple body. */
1001 // TODO: is there a pre-canned way to do this?
1004 fndecl_has_gimple_body_p (tree fndecl
)
1006 if (fndecl
== NULL_TREE
)
1009 cgraph_node
*n
= cgraph_node::get (fndecl
);
1013 return n
->has_gimple_body_p ();
1018 /* A pending_diagnostic subclass for implementing "__analyzer_dump_path". */
1020 class dump_path_diagnostic
1021 : public pending_diagnostic_subclass
<dump_path_diagnostic
>
1024 bool emit (rich_location
*richloc
) FINAL OVERRIDE
1026 inform (richloc
, "path");
1030 const char *get_kind () const FINAL OVERRIDE
{ return "dump_path_diagnostic"; }
1032 bool operator== (const dump_path_diagnostic
&) const
1038 /* Modify STATE in place, applying the effects of the stmt at this node's
1041 exploded_node::on_stmt_flags
1042 exploded_node::on_stmt (exploded_graph
&eg
,
1043 const supernode
*snode
,
1045 program_state
*state
) const
1047 logger
*logger
= eg
.get_logger ();
1051 logger
->start_log_line ();
1052 pp_gimple_stmt_1 (logger
->get_printer (), stmt
, 0, (dump_flags_t
)0);
1053 logger
->end_log_line ();
1056 /* Update input_location in case of ICE: make it easier to track down which
1057 source construct we're failing to handle. */
1058 input_location
= stmt
->location
;
1060 gcc_assert (state
->m_region_model
);
1062 /* Preserve the old state. It is used here for looking
1063 up old checker states, for determining state transitions, and
1064 also within impl_region_model_context and impl_sm_context for
1065 going from tree to svalue_id. */
1066 const program_state
old_state (*state
);
1068 impl_region_model_context
ctxt (eg
, this,
1072 bool unknown_side_effects
= false;
1074 switch (gimple_code (stmt
))
1077 /* No-op for now. */
1082 const gassign
*assign
= as_a
<const gassign
*> (stmt
);
1083 state
->m_region_model
->on_assignment (assign
, &ctxt
);
1088 /* No-op for now. */
1093 /* Track whether we have a gcall to a function that's not recognized by
1094 anything, for which we don't have a function body, or for which we
1095 don't know the fndecl. */
1096 const gcall
*call
= as_a
<const gcall
*> (stmt
);
1098 /* Debugging/test support. */
1099 if (is_special_named_call_p (call
, "__analyzer_describe", 2))
1100 state
->m_region_model
->impl_call_analyzer_describe (call
, &ctxt
);
1101 else if (is_special_named_call_p (call
, "__analyzer_dump", 0))
1103 /* Handle the builtin "__analyzer_dump" by dumping state
1105 state
->dump (eg
.get_ext_state (), true);
1107 else if (is_special_named_call_p (call
, "__analyzer_dump_path", 0))
1109 /* Handle the builtin "__analyzer_dump_path" by queuing a
1110 diagnostic at this exploded_node. */
1111 ctxt
.warn (new dump_path_diagnostic ());
1113 else if (is_special_named_call_p (call
, "__analyzer_dump_region_model",
1116 /* Handle the builtin "__analyzer_dump_region_model" by dumping
1117 the region model's state to stderr. */
1118 state
->m_region_model
->dump (false);
1120 else if (is_special_named_call_p (call
, "__analyzer_eval", 1))
1121 state
->m_region_model
->impl_call_analyzer_eval (call
, &ctxt
);
1122 else if (is_special_named_call_p (call
, "__analyzer_break", 0))
1124 /* Handle the builtin "__analyzer_break" by triggering a
1126 /* TODO: is there a good cross-platform way to do this? */
1129 else if (is_special_named_call_p (call
,
1130 "__analyzer_dump_exploded_nodes",
1133 /* This is handled elsewhere. */
1135 else if (is_setjmp_call_p (call
))
1136 state
->m_region_model
->on_setjmp (call
, this, &ctxt
);
1137 else if (is_longjmp_call_p (call
))
1139 on_longjmp (eg
, call
, state
, &ctxt
);
1140 return on_stmt_flags::terminate_path ();
1143 unknown_side_effects
1144 = state
->m_region_model
->on_call_pre (call
, &ctxt
);
1150 const greturn
*return_
= as_a
<const greturn
*> (stmt
);
1151 state
->m_region_model
->on_return (return_
, &ctxt
);
1156 bool any_sm_changes
= false;
1159 FOR_EACH_VEC_ELT (old_state
.m_checker_states
, sm_idx
, smap
)
1161 const state_machine
&sm
= eg
.get_ext_state ().get_sm (sm_idx
);
1162 const sm_state_map
*old_smap
1163 = old_state
.m_checker_states
[sm_idx
];
1164 sm_state_map
*new_smap
= state
->m_checker_states
[sm_idx
];
1165 impl_sm_context
sm_ctxt (eg
, sm_idx
, sm
, this, &old_state
, state
,
1166 old_smap
, new_smap
);
1167 /* Allow the state_machine to handle the stmt. */
1168 if (sm
.on_stmt (&sm_ctxt
, snode
, stmt
))
1169 unknown_side_effects
= false;
1170 if (*old_smap
!= *new_smap
)
1171 any_sm_changes
= true;
1174 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
1175 state
->m_region_model
->on_call_post (call
, unknown_side_effects
, &ctxt
);
1177 return on_stmt_flags (any_sm_changes
);
1180 /* Consider the effect of following superedge SUCC from this node.
1182 Return true if it's feasible to follow the edge, or false
1185 Examples: if it's the "true" branch within
1186 a CFG and we know the conditional is false, we know it's infeasible.
1187 If it's one of multiple interprocedual "return" edges, then only
1188 the edge back to the most recent callsite is feasible.
1190 Update NEXT_STATE accordingly (e.g. to record that a condition was
1191 true or false, or that the NULL-ness of a pointer has been checked,
1192 pushing/popping stack frames, etc).
1194 Update NEXT_POINT accordingly (updating the call string). */
1197 exploded_node::on_edge (exploded_graph
&eg
,
1198 const superedge
*succ
,
1199 program_point
*next_point
,
1200 program_state
*next_state
) const
1202 LOG_FUNC (eg
.get_logger ());
1204 if (!next_point
->on_edge (eg
, succ
))
1207 if (!next_state
->on_edge (eg
, *this, succ
))
1213 /* Verify that the stack at LONGJMP_POINT is still valid, given a call
1214 to "setjmp" at SETJMP_POINT - the stack frame that "setjmp" was
1215 called in must still be valid.
1217 Caveat: this merely checks the call_strings in the points; it doesn't
1218 detect the case where a frame returns and is then called again. */
1221 valid_longjmp_stack_p (const program_point
&longjmp_point
,
1222 const program_point
&setjmp_point
)
1224 const call_string
&cs_at_longjmp
= longjmp_point
.get_call_string ();
1225 const call_string
&cs_at_setjmp
= setjmp_point
.get_call_string ();
1227 if (cs_at_longjmp
.length () < cs_at_setjmp
.length ())
1230 /* Check that the call strings match, up to the depth of the
1232 for (unsigned depth
= 0; depth
< cs_at_setjmp
.length (); depth
++)
1233 if (cs_at_longjmp
[depth
] != cs_at_setjmp
[depth
])
1239 /* A pending_diagnostic subclass for complaining about bad longjmps,
1240 where the enclosing function of the "setjmp" has returned (and thus
1241 the stack frame no longer exists). */
1243 class stale_jmp_buf
: public pending_diagnostic_subclass
<dump_path_diagnostic
>
1246 stale_jmp_buf (const gcall
*setjmp_call
, const gcall
*longjmp_call
)
1247 : m_setjmp_call (setjmp_call
), m_longjmp_call (longjmp_call
)
1250 bool emit (rich_location
*richloc
) FINAL OVERRIDE
1253 (richloc
, OPT_Wanalyzer_stale_setjmp_buffer
,
1254 "%qs called after enclosing function of %qs has returned",
1255 get_user_facing_name (m_longjmp_call
),
1256 get_user_facing_name (m_setjmp_call
));
1259 const char *get_kind () const FINAL OVERRIDE
1260 { return "stale_jmp_buf"; }
1262 bool operator== (const stale_jmp_buf
&other
) const
1264 return (m_setjmp_call
== other
.m_setjmp_call
1265 && m_longjmp_call
== other
.m_longjmp_call
);
1269 const gcall
*m_setjmp_call
;
1270 const gcall
*m_longjmp_call
;
1273 /* Handle LONGJMP_CALL, a call to longjmp or siglongjmp.
1275 Attempt to locate where setjmp/sigsetjmp was called on the jmp_buf and build
1276 an exploded_node and exploded_edge to it representing a rewind to that frame,
1277 handling the various kinds of failure that can occur. */
1280 exploded_node::on_longjmp (exploded_graph
&eg
,
1281 const gcall
*longjmp_call
,
1282 program_state
*new_state
,
1283 region_model_context
*ctxt
) const
1285 tree buf_ptr
= gimple_call_arg (longjmp_call
, 0);
1286 gcc_assert (POINTER_TYPE_P (TREE_TYPE (buf_ptr
)));
1288 region_model
*new_region_model
= new_state
->m_region_model
;
1289 const svalue
*buf_ptr_sval
= new_region_model
->get_rvalue (buf_ptr
, ctxt
);
1290 const region
*buf
= new_region_model
->deref_rvalue (buf_ptr_sval
, buf_ptr
,
1293 const svalue
*buf_content_sval
= new_region_model
->get_store_value (buf
);
1294 const setjmp_svalue
*setjmp_sval
1295 = buf_content_sval
->dyn_cast_setjmp_svalue ();
1299 const setjmp_record tmp_setjmp_record
= setjmp_sval
->get_setjmp_record ();
1301 /* Build a custom enode and eedge for rewinding from the longjmp/siglongjmp
1302 call back to the setjmp/sigsetjmp. */
1303 rewind_info_t
rewind_info (tmp_setjmp_record
, longjmp_call
);
1305 const gcall
*setjmp_call
= rewind_info
.get_setjmp_call ();
1306 const program_point
&setjmp_point
= rewind_info
.get_setjmp_point ();
1308 const program_point
&longjmp_point
= get_point ();
1310 /* Verify that the setjmp's call_stack hasn't been popped. */
1311 if (!valid_longjmp_stack_p (longjmp_point
, setjmp_point
))
1313 ctxt
->warn (new stale_jmp_buf (setjmp_call
, longjmp_call
));
1317 gcc_assert (longjmp_point
.get_stack_depth ()
1318 >= setjmp_point
.get_stack_depth ());
1320 /* Update the state for use by the destination node. */
1322 /* Stash the current number of diagnostics so that we can update
1323 any that this adds to show where the longjmp is rewinding to. */
1325 diagnostic_manager
*dm
= &eg
.get_diagnostic_manager ();
1326 unsigned prev_num_diagnostics
= dm
->get_num_diagnostics ();
1328 new_region_model
->on_longjmp (longjmp_call
, setjmp_call
,
1329 setjmp_point
.get_stack_depth (), ctxt
);
1331 /* Detect leaks in the new state relative to the old state. */
1332 program_state::detect_leaks (get_state (), *new_state
, NULL
,
1333 eg
.get_ext_state (), ctxt
);
1335 program_point next_point
1336 = program_point::after_supernode (setjmp_point
.get_supernode (),
1337 setjmp_point
.get_call_string ());
1340 = eg
.get_or_create_node (next_point
, *new_state
, this);
1342 /* Create custom exploded_edge for a longjmp. */
1345 exploded_edge
*eedge
1346 = eg
.add_edge (const_cast<exploded_node
*> (this), next
, NULL
,
1347 new rewind_info_t (tmp_setjmp_record
, longjmp_call
));
1349 /* For any diagnostics that were queued here (such as leaks) we want
1350 the checker_path to show the rewinding events after the "final event"
1351 so that the user sees where the longjmp is rewinding to (otherwise the
1352 path is meaningless).
1354 For example, we want to emit something like:
1356 | NN | longjmp (env, 1);
1357 | | ~~~~~~~~~~~~~~~~
1359 | | (10) 'ptr' leaks here; was allocated at (7)
1360 | | (11) rewinding from 'longjmp' in 'inner'...
1366 | NN | i = setjmp(env);
1369 | | (12) ...to 'setjmp' in 'outer' (saved at (2))
1371 where the "final" event above is event (10), but we want to append
1372 events (11) and (12) afterwards.
1374 Do this by setting m_trailing_eedge on any diagnostics that were
1376 unsigned num_diagnostics
= dm
->get_num_diagnostics ();
1377 for (unsigned i
= prev_num_diagnostics
; i
< num_diagnostics
; i
++)
1379 saved_diagnostic
*sd
= dm
->get_saved_diagnostic (i
);
1380 sd
->m_trailing_eedge
= eedge
;
1385 /* Subroutine of exploded_graph::process_node for finding the successors
1386 of the supernode for a function exit basic block.
1388 Ensure that pop_frame is called, potentially queuing diagnostics about
1392 exploded_node::detect_leaks (exploded_graph
&eg
) const
1394 LOG_FUNC_1 (eg
.get_logger (), "EN: %i", m_index
);
1396 gcc_assert (get_point ().get_supernode ()->return_p ());
1398 /* If we're not a "top-level" function, do nothing; pop_frame
1399 will be called when handling the return superedge. */
1400 if (get_point ().get_stack_depth () > 1)
1403 /* We have a "top-level" function. */
1404 gcc_assert (get_point ().get_stack_depth () == 1);
1406 const program_state
&old_state
= get_state ();
1408 /* Work with a temporary copy of the state: pop the frame, and see
1409 what leaks (via purge_unused_svalues). */
1410 program_state
new_state (old_state
);
1412 gcc_assert (new_state
.m_region_model
);
1414 impl_region_model_context
ctxt (eg
, this,
1415 &old_state
, &new_state
,
1417 const svalue
*result
= NULL
;
1418 new_state
.m_region_model
->pop_frame (NULL
, &result
, &ctxt
);
1419 program_state::detect_leaks (old_state
, new_state
, result
,
1420 eg
.get_ext_state (), &ctxt
);
1423 /* Dump the successors and predecessors of this enode to OUTF. */
1426 exploded_node::dump_succs_and_preds (FILE *outf
) const
1431 auto_vec
<exploded_node
*> preds (m_preds
.length ());
1432 FOR_EACH_VEC_ELT (m_preds
, i
, e
)
1433 preds
.quick_push (e
->m_src
);
1435 print_enode_indices (&pp
, preds
);
1436 fprintf (outf
, "preds: %s\n",
1437 pp_formatted_text (&pp
));
1440 auto_vec
<exploded_node
*> succs (m_succs
.length ());
1441 FOR_EACH_VEC_ELT (m_succs
, i
, e
)
1442 succs
.quick_push (e
->m_dest
);
1444 print_enode_indices (&pp
, succs
);
1445 fprintf (outf
, "succs: %s\n",
1446 pp_formatted_text (&pp
));
1450 /* class rewind_info_t : public exploded_edge::custom_info_t. */
1452 /* Implementation of exploded_edge::custom_info_t::update_model vfunc
1455 Update state for the special-case of a rewind of a longjmp
1456 to a setjmp (which doesn't have a superedge, but does affect
1460 rewind_info_t::update_model (region_model
*model
,
1461 const exploded_edge
&eedge
)
1463 const program_point
&longjmp_point
= eedge
.m_src
->get_point ();
1464 const program_point
&setjmp_point
= eedge
.m_dest
->get_point ();
1466 gcc_assert (longjmp_point
.get_stack_depth ()
1467 >= setjmp_point
.get_stack_depth ());
1469 model
->on_longjmp (get_longjmp_call (),
1471 setjmp_point
.get_stack_depth (), NULL
);
1474 /* Implementation of exploded_edge::custom_info_t::add_events_to_path vfunc
1475 for rewind_info_t. */
1478 rewind_info_t::add_events_to_path (checker_path
*emission_path
,
1479 const exploded_edge
&eedge
)
1481 const exploded_node
*src_node
= eedge
.m_src
;
1482 const program_point
&src_point
= src_node
->get_point ();
1483 const int src_stack_depth
= src_point
.get_stack_depth ();
1484 const exploded_node
*dst_node
= eedge
.m_dest
;
1485 const program_point
&dst_point
= dst_node
->get_point ();
1486 const int dst_stack_depth
= dst_point
.get_stack_depth ();
1488 emission_path
->add_event
1489 (new rewind_from_longjmp_event
1490 (&eedge
, get_longjmp_call ()->location
,
1491 src_point
.get_fndecl (),
1492 src_stack_depth
, this));
1493 emission_path
->add_event
1494 (new rewind_to_setjmp_event
1495 (&eedge
, get_setjmp_call ()->location
,
1496 dst_point
.get_fndecl (),
1497 dst_stack_depth
, this));
1500 /* class exploded_edge : public dedge<eg_traits>. */
1502 /* exploded_edge's ctor. */
1504 exploded_edge::exploded_edge (exploded_node
*src
, exploded_node
*dest
,
1505 const superedge
*sedge
,
1506 custom_info_t
*custom_info
)
1507 : dedge
<eg_traits
> (src
, dest
), m_sedge (sedge
),
1508 m_custom_info (custom_info
)
1512 /* exploded_edge's dtor. */
1514 exploded_edge::~exploded_edge ()
1516 delete m_custom_info
;
1519 /* Implementation of dedge::dump_dot vfunc for exploded_edge.
1520 Use the label of the underlying superedge, if any. */
1523 exploded_edge::dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
1525 pretty_printer
*pp
= gv
->get_pp ();
1527 const char *style
= "\"solid,bold\"";
1528 const char *color
= "black";
1530 const char *constraint
= "true";
1533 switch (m_sedge
->m_kind
)
1537 case SUPEREDGE_CFG_EDGE
:
1539 case SUPEREDGE_CALL
:
1541 //constraint = "false";
1543 case SUPEREDGE_RETURN
:
1545 //constraint = "false";
1547 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
1548 style
= "\"dotted\"";
1554 style
= "\"dotted\"";
1557 m_src
->dump_dot_id (pp
);
1558 pp_string (pp
, " -> ");
1559 m_dest
->dump_dot_id (pp
);
1561 (" [style=%s, color=%s, weight=%d, constraint=%s,"
1563 style
, color
, weight
, constraint
);
1566 m_sedge
->dump_label_to_pp (pp
, false);
1567 else if (m_custom_info
)
1568 m_custom_info
->print (pp
);
1570 //pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
1572 pp_printf (pp
, "\"];\n");
1575 /* Return a new json::object of the form
1576 {"src_idx": int, the index of the source exploded edge,
1577 "dst_idx": int, the index of the destination exploded edge,
1578 "sedge": (optional) object for the superedge, if any,
1579 "custom": (optional) str, a description, if this is a custom edge}. */
1582 exploded_edge::to_json () const
1584 json::object
*eedge_obj
= new json::object ();
1585 eedge_obj
->set ("src_idx", new json::integer_number (m_src
->m_index
));
1586 eedge_obj
->set ("dst_idx", new json::integer_number (m_dest
->m_index
));
1588 eedge_obj
->set ("sedge", m_sedge
->to_json ());
1592 pp_format_decoder (&pp
) = default_tree_printer
;
1593 m_custom_info
->print (&pp
);
1594 eedge_obj
->set ("custom", new json::string (pp_formatted_text (&pp
)));
1603 stats::stats (int num_supernodes
)
1604 : m_node_reuse_count (0),
1605 m_node_reuse_after_merge_count (0),
1606 m_num_supernodes (num_supernodes
)
1608 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
1612 /* Log these stats in multiline form to LOGGER. */
1615 stats::log (logger
*logger
) const
1617 gcc_assert (logger
);
1618 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
1619 if (m_num_nodes
[i
] > 0)
1620 logger
->log ("m_num_nodes[%s]: %i",
1621 point_kind_to_string (static_cast <enum point_kind
> (i
)),
1623 logger
->log ("m_node_reuse_count: %i", m_node_reuse_count
);
1624 logger
->log ("m_node_reuse_after_merge_count: %i",
1625 m_node_reuse_after_merge_count
);
1628 /* Dump these stats in multiline form to OUT. */
1631 stats::dump (FILE *out
) const
1633 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
1634 if (m_num_nodes
[i
] > 0)
1635 fprintf (out
, "m_num_nodes[%s]: %i\n",
1636 point_kind_to_string (static_cast <enum point_kind
> (i
)),
1638 fprintf (out
, "m_node_reuse_count: %i\n", m_node_reuse_count
);
1639 fprintf (out
, "m_node_reuse_after_merge_count: %i\n",
1640 m_node_reuse_after_merge_count
);
1642 if (m_num_supernodes
> 0)
1643 fprintf (out
, "PK_AFTER_SUPERNODE nodes per supernode: %.2f\n",
1644 (float)m_num_nodes
[PK_AFTER_SUPERNODE
] / (float)m_num_supernodes
);
1647 /* Return the total number of enodes recorded within this object. */
1650 stats::get_total_enodes () const
1653 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
1654 result
+= m_num_nodes
[i
];
1658 /* strongly_connected_components's ctor. Tarjan's SCC algorithm. */
1660 strongly_connected_components::
1661 strongly_connected_components (const supergraph
&sg
, logger
*logger
)
1662 : m_sg (sg
), m_per_node (m_sg
.num_nodes ())
1665 auto_timevar
tv (TV_ANALYZER_SCC
);
1667 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
1668 m_per_node
.quick_push (per_node_data ());
1670 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
1671 if (m_per_node
[i
].m_index
== -1)
1678 /* Dump this object to stderr. */
1681 strongly_connected_components::dump () const
1683 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
1685 const per_node_data
&v
= m_per_node
[i
];
1686 fprintf (stderr
, "SN %i: index: %i lowlink: %i on_stack: %i\n",
1687 i
, v
.m_index
, v
.m_lowlink
, v
.m_on_stack
);
1691 /* Subroutine of strongly_connected_components's ctor, part of Tarjan's
1695 strongly_connected_components::strong_connect (unsigned index
)
1697 supernode
*v_snode
= m_sg
.get_node_by_index (index
);
1699 /* Set the depth index for v to the smallest unused index. */
1700 per_node_data
*v
= &m_per_node
[index
];
1702 v
->m_lowlink
= index
;
1703 m_stack
.safe_push (index
);
1704 v
->m_on_stack
= true;
1707 /* Consider successors of v. */
1710 FOR_EACH_VEC_ELT (v_snode
->m_succs
, i
, sedge
)
1712 if (sedge
->get_kind () != SUPEREDGE_CFG_EDGE
1713 && sedge
->get_kind () != SUPEREDGE_INTRAPROCEDURAL_CALL
)
1715 supernode
*w_snode
= sedge
->m_dest
;
1716 per_node_data
*w
= &m_per_node
[w_snode
->m_index
];
1717 if (w
->m_index
== -1)
1719 /* Successor w has not yet been visited; recurse on it. */
1720 strong_connect (w_snode
->m_index
);
1721 v
->m_lowlink
= MIN (v
->m_lowlink
, w
->m_lowlink
);
1723 else if (w
->m_on_stack
)
1725 /* Successor w is in stack S and hence in the current SCC
1726 If w is not on stack, then (v, w) is a cross-edge in the DFS
1727 tree and must be ignored. */
1728 v
->m_lowlink
= MIN (v
->m_lowlink
, w
->m_index
);
1732 /* If v is a root node, pop the stack and generate an SCC. */
1734 if (v
->m_lowlink
== v
->m_index
)
1738 int idx
= m_stack
.pop ();
1739 w
= &m_per_node
[idx
];
1740 w
->m_on_stack
= false;
1745 /* worklist's ctor. */
1747 worklist::worklist (const exploded_graph
&eg
, const analysis_plan
&plan
)
1748 : m_scc (eg
.get_supergraph (), eg
.get_logger ()),
1750 m_queue (key_t (*this, NULL
))
1754 /* Return the number of nodes in the worklist. */
1757 worklist::length () const
1759 return m_queue
.nodes ();
1762 /* Return the next node in the worklist, removing it. */
1765 worklist::take_next ()
1767 return m_queue
.extract_min ();
1770 /* Return the next node in the worklist without removing it. */
1773 worklist::peek_next ()
1775 return m_queue
.min ();
1778 /* Add ENODE to the worklist. */
1781 worklist::add_node (exploded_node
*enode
)
1783 gcc_assert (enode
->get_status () == exploded_node::STATUS_WORKLIST
);
1784 m_queue
.insert (key_t (*this, enode
), enode
);
1787 /* Comparator for implementing worklist::key_t comparison operators.
1788 Return negative if KA is before KB
1789 Return positive if KA is after KB
1790 Return 0 if they are equal.
1792 The ordering of the worklist is critical for performance and for
1793 avoiding node explosions. Ideally we want all enodes at a CFG join-point
1794 with the same callstring to be sorted next to each other in the worklist
1795 so that a run of consecutive enodes can be merged and processed "in bulk"
1796 rather than individually or pairwise, minimizing the number of new enodes
1800 worklist::key_t::cmp (const worklist::key_t
&ka
, const worklist::key_t
&kb
)
1802 const program_point
&point_a
= ka
.m_enode
->get_point ();
1803 const program_point
&point_b
= kb
.m_enode
->get_point ();
1804 const call_string
&call_string_a
= point_a
.get_call_string ();
1805 const call_string
&call_string_b
= point_b
.get_call_string ();
1807 /* Order empty-callstring points with different functions based on the
1808 analysis_plan, so that we generate summaries before they are used. */
1809 if (flag_analyzer_call_summaries
1810 && call_string_a
.empty_p ()
1811 && call_string_b
.empty_p ()
1812 && point_a
.get_function () != NULL
1813 && point_b
.get_function () != NULL
1814 && point_a
.get_function () != point_b
.get_function ())
1816 return ka
.m_worklist
.m_plan
.cmp_function (point_a
.get_function (),
1817 point_b
.get_function ());
1820 /* First, order by SCC. */
1821 int scc_id_a
= ka
.get_scc_id (ka
.m_enode
);
1822 int scc_id_b
= kb
.get_scc_id (kb
.m_enode
);
1823 if (scc_id_a
!= scc_id_b
)
1824 return scc_id_a
- scc_id_b
;
1826 /* If in same SCC, order by supernode index (an arbitrary but stable
1828 const supernode
*snode_a
= ka
.m_enode
->get_supernode ();
1829 const supernode
*snode_b
= kb
.m_enode
->get_supernode ();
1830 if (snode_a
== NULL
)
1832 if (snode_b
!= NULL
)
1836 /* Both are NULL. */
1839 if (snode_b
== NULL
)
1842 /* Neither are NULL. */
1843 gcc_assert (snode_a
&& snode_b
);
1844 if (snode_a
->m_index
!= snode_b
->m_index
)
1845 return snode_a
->m_index
- snode_b
->m_index
;
1847 gcc_assert (snode_a
== snode_b
);
1849 /* The points might vary by callstring; try sorting by callstring. */
1850 int cs_cmp
= call_string::cmp (call_string_a
, call_string_b
);
1854 /* Order within supernode via program point. */
1855 int within_snode_cmp
1856 = function_point::cmp_within_supernode (point_a
.get_function_point (),
1857 point_b
.get_function_point ());
1858 if (within_snode_cmp
)
1859 return within_snode_cmp
;
1861 /* Otherwise, we ought to have the same program_point. */
1862 gcc_assert (point_a
== point_b
);
1864 const program_state
&state_a
= ka
.m_enode
->get_state ();
1865 const program_state
&state_b
= kb
.m_enode
->get_state ();
1867 /* Sort by sm-state, so that identical sm-states are grouped
1868 together in the worklist.
1869 For now, sort by the hash value (might not be deterministic). */
1870 for (unsigned sm_idx
= 0; sm_idx
< state_a
.m_checker_states
.length ();
1873 sm_state_map
*smap_a
= state_a
.m_checker_states
[sm_idx
];
1874 sm_state_map
*smap_b
= state_b
.m_checker_states
[sm_idx
];
1876 hashval_t hash_a
= smap_a
->hash ();
1877 hashval_t hash_b
= smap_b
->hash ();
1878 if (hash_a
< hash_b
)
1880 else if (hash_a
> hash_b
)
1884 /* Otherwise, we have two enodes at the same program point but with
1885 different states. We don't have a good total ordering on states,
1886 so order them by enode index, so that we have at least have a
1888 return ka
.m_enode
->m_index
- kb
.m_enode
->m_index
;
1891 /* exploded_graph's ctor. */
1893 exploded_graph::exploded_graph (const supergraph
&sg
, logger
*logger
,
1894 const extrinsic_state
&ext_state
,
1895 const state_purge_map
*purge_map
,
1896 const analysis_plan
&plan
,
1898 : m_sg (sg
), m_logger (logger
),
1899 m_worklist (*this, plan
),
1900 m_ext_state (ext_state
),
1901 m_purge_map (purge_map
),
1903 m_diagnostic_manager (logger
, ext_state
.get_engine (), verbosity
),
1904 m_global_stats (m_sg
.num_nodes ()),
1905 m_functionless_stats (m_sg
.num_nodes ()),
1906 m_PK_AFTER_SUPERNODE_per_snode (m_sg
.num_nodes ())
1908 m_origin
= get_or_create_node (program_point::origin (),
1909 program_state (ext_state
), NULL
);
1910 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
1911 m_PK_AFTER_SUPERNODE_per_snode
.quick_push (i
);
1914 /* exploded_graph's dtor. */
1916 exploded_graph::~exploded_graph ()
1918 for (function_stat_map_t::iterator iter
= m_per_function_stats
.begin ();
1919 iter
!= m_per_function_stats
.end ();
1921 delete (*iter
).second
;
1923 for (point_map_t::iterator iter
= m_per_point_data
.begin ();
1924 iter
!= m_per_point_data
.end ();
1926 delete (*iter
).second
;
1929 /* Ensure that there is an exploded_node representing an external call to
1930 FUN, adding it to the worklist if creating it.
1932 Add an edge from the origin exploded_node to the function entrypoint
1935 Return the exploded_node for the entrypoint to the function. */
1938 exploded_graph::add_function_entry (function
*fun
)
1940 /* Be idempotent. */
1941 if (m_functions_with_enodes
.contains (fun
))
1943 logger
* const logger
= get_logger ();
1945 logger
->log ("entrypoint for %qE already exists", fun
->decl
);
1949 program_point point
= program_point::from_function_entry (m_sg
, fun
);
1950 program_state
state (m_ext_state
);
1951 state
.push_frame (m_ext_state
, fun
);
1956 exploded_node
*enode
= get_or_create_node (point
, state
, NULL
);
1957 /* We should never fail to add such a node. */
1959 add_edge (m_origin
, enode
, NULL
);
1961 m_functions_with_enodes
.add (fun
);
1966 /* Get or create an exploded_node for (POINT, STATE).
1967 If a new node is created, it is added to the worklist.
1969 Use ENODE_FOR_DIAG, a pre-existing enode, for any diagnostics
1970 that need to be emitted (e.g. when purging state *before* we have
1974 exploded_graph::get_or_create_node (const program_point
&point
,
1975 const program_state
&state
,
1976 const exploded_node
*enode_for_diag
)
1978 logger
* const logger
= get_logger ();
1983 pretty_printer
*pp
= logger
->get_printer ();
1984 logger
->start_log_line ();
1985 pp_string (pp
, "point: ");
1986 point
.print (pp
, f
);
1987 logger
->end_log_line ();
1988 logger
->start_log_line ();
1989 pp_string (pp
, "state: ");
1990 state
.dump_to_pp (m_ext_state
, true, false, pp
);
1991 logger
->end_log_line ();
1994 /* Stop exploring paths for which we don't know how to effectively
1999 logger
->log ("invalid state; not creating node");
2003 auto_cfun
sentinel (point
.get_function ());
2005 state
.validate (get_ext_state ());
2007 //state.dump (get_ext_state ());
2009 /* Prune state to try to improve the chances of a cache hit,
2010 avoiding generating redundant nodes. */
2011 program_state pruned_state
2012 = state
.prune_for_point (*this, point
, enode_for_diag
);
2014 pruned_state
.validate (get_ext_state ());
2016 //pruned_state.dump (get_ext_state ());
2020 pretty_printer
*pp
= logger
->get_printer ();
2021 logger
->start_log_line ();
2022 pp_string (pp
, "pruned_state: ");
2023 pruned_state
.dump_to_pp (m_ext_state
, true, false, pp
);
2024 logger
->end_log_line ();
2025 pruned_state
.m_region_model
->dump_to_pp (logger
->get_printer (), true,
2029 stats
*per_fn_stats
= get_or_create_function_stats (point
.get_function ());
2032 = &get_or_create_per_call_string_data (point
.get_call_string ())->m_stats
;
2034 point_and_state
ps (point
, pruned_state
);
2035 ps
.validate (m_ext_state
);
2036 if (exploded_node
**slot
= m_point_and_state_to_node
.get (&ps
))
2038 /* An exploded_node for PS already exists. */
2040 logger
->log ("reused EN: %i", (*slot
)->m_index
);
2041 m_global_stats
.m_node_reuse_count
++;
2042 per_fn_stats
->m_node_reuse_count
++;
2043 per_cs_stats
->m_node_reuse_count
++;
2047 per_program_point_data
*per_point_data
2048 = get_or_create_per_program_point_data (point
);
2050 /* Consider merging state with another enode at this program_point. */
2051 if (flag_analyzer_state_merge
)
2053 exploded_node
*existing_enode
;
2055 FOR_EACH_VEC_ELT (per_point_data
->m_enodes
, i
, existing_enode
)
2058 logger
->log ("considering merging with existing EN: %i for point",
2059 existing_enode
->m_index
);
2060 gcc_assert (existing_enode
->get_point () == point
);
2061 const program_state
&existing_state
= existing_enode
->get_state ();
2063 /* This merges successfully within the loop. */
2065 program_state
merged_state (m_ext_state
);
2066 if (pruned_state
.can_merge_with_p (existing_state
, point
,
2070 logger
->log ("merging new state with that of EN: %i",
2071 existing_enode
->m_index
);
2073 /* Try again for a cache hit.
2074 Whether we get one or not, merged_state's value_ids have no
2075 relationship to those of the input state, and thus to those
2076 of CHANGE, so we must purge any svalue_ids from *CHANGE. */
2077 ps
.set_state (merged_state
);
2079 if (exploded_node
**slot
= m_point_and_state_to_node
.get (&ps
))
2081 /* An exploded_node for PS already exists. */
2083 logger
->log ("reused EN: %i", (*slot
)->m_index
);
2084 m_global_stats
.m_node_reuse_after_merge_count
++;
2085 per_fn_stats
->m_node_reuse_after_merge_count
++;
2086 per_cs_stats
->m_node_reuse_after_merge_count
++;
2092 logger
->log ("not merging new state with that of EN: %i",
2093 existing_enode
->m_index
);
2097 /* Impose a limit on the number of enodes per program point, and
2098 simply stop if we exceed it. */
2099 if ((int)per_point_data
->m_enodes
.length ()
2100 > param_analyzer_max_enodes_per_program_point
)
2103 point
.print (&pp
, format (false));
2104 print_enode_indices (&pp
, per_point_data
->m_enodes
);
2106 logger
->log ("not creating enode; too many at program point: %s",
2107 pp_formatted_text (&pp
));
2108 warning_at (point
.get_location (), OPT_Wanalyzer_too_complex
,
2109 "terminating analysis for this program point: %s",
2110 pp_formatted_text (&pp
));
2111 per_point_data
->m_excess_enodes
++;
2115 ps
.validate (m_ext_state
);
2117 /* An exploded_node for "ps" doesn't already exist; create one. */
2118 exploded_node
*node
= new exploded_node (ps
, m_nodes
.length ());
2120 m_point_and_state_to_node
.put (node
->get_ps_key (), node
);
2122 /* Update per-program_point data. */
2123 per_point_data
->m_enodes
.safe_push (node
);
2125 const enum point_kind node_pk
= node
->get_point ().get_kind ();
2126 m_global_stats
.m_num_nodes
[node_pk
]++;
2127 per_fn_stats
->m_num_nodes
[node_pk
]++;
2128 per_cs_stats
->m_num_nodes
[node_pk
]++;
2130 if (node_pk
== PK_AFTER_SUPERNODE
)
2131 m_PK_AFTER_SUPERNODE_per_snode
[point
.get_supernode ()->m_index
]++;
2136 pretty_printer
*pp
= logger
->get_printer ();
2137 logger
->log ("created EN: %i", node
->m_index
);
2138 logger
->start_log_line ();
2139 pp_string (pp
, "point: ");
2140 point
.print (pp
, f
);
2141 logger
->end_log_line ();
2142 logger
->start_log_line ();
2143 pp_string (pp
, "pruned_state: ");
2144 pruned_state
.dump_to_pp (m_ext_state
, true, false, pp
);
2145 logger
->end_log_line ();
2148 /* Add the new node to the worlist. */
2149 m_worklist
.add_node (node
);
2153 /* Add an exploded_edge from SRC to DEST, recording its association
2154 with SEDGE (which may be NULL), and, if non-NULL, taking ownership
2156 Return the newly-created eedge. */
2159 exploded_graph::add_edge (exploded_node
*src
, exploded_node
*dest
,
2160 const superedge
*sedge
,
2161 exploded_edge::custom_info_t
*custom_info
)
2164 get_logger ()->log ("creating edge EN: %i -> EN: %i",
2165 src
->m_index
, dest
->m_index
);
2166 exploded_edge
*e
= new exploded_edge (src
, dest
, sedge
, custom_info
);
2167 digraph
<eg_traits
>::add_edge (e
);
2171 /* Ensure that this graph has per-program_point-data for POINT;
2172 borrow a pointer to it. */
2174 per_program_point_data
*
2176 get_or_create_per_program_point_data (const program_point
&point
)
2178 if (per_program_point_data
**slot
= m_per_point_data
.get (&point
))
2181 per_program_point_data
*per_point_data
= new per_program_point_data (point
);
2182 m_per_point_data
.put (&per_point_data
->m_key
, per_point_data
);
2183 return per_point_data
;
2186 /* Get this graph's per-program-point-data for POINT if there is any,
2189 per_program_point_data
*
2190 exploded_graph::get_per_program_point_data (const program_point
&point
) const
2192 if (per_program_point_data
**slot
2193 = const_cast <point_map_t
&> (m_per_point_data
).get (&point
))
2199 /* Ensure that this graph has per-call_string-data for CS;
2200 borrow a pointer to it. */
2202 per_call_string_data
*
2203 exploded_graph::get_or_create_per_call_string_data (const call_string
&cs
)
2205 if (per_call_string_data
**slot
= m_per_call_string_data
.get (&cs
))
2208 per_call_string_data
*data
= new per_call_string_data (cs
, m_sg
.num_nodes ());
2209 m_per_call_string_data
.put (&data
->m_key
,
2214 /* Ensure that this graph has per-function-data for FUN;
2215 borrow a pointer to it. */
2218 exploded_graph::get_or_create_per_function_data (function
*fun
)
2220 if (per_function_data
**slot
= m_per_function_data
.get (fun
))
2223 per_function_data
*data
= new per_function_data ();
2224 m_per_function_data
.put (fun
, data
);
2228 /* Get this graph's per-function-data for FUN if there is any,
2232 exploded_graph::get_per_function_data (function
*fun
) const
2234 if (per_function_data
**slot
2235 = const_cast <per_function_data_t
&> (m_per_function_data
).get (fun
))
2241 /* Return true if NODE and FUN should be traversed directly, rather than
2242 called via other functions. */
2245 toplevel_function_p (cgraph_node
*node
, function
*fun
, logger
*logger
)
2247 /* TODO: better logic here
2248 e.g. only if more than one caller, and significantly complicated.
2249 Perhaps some whole-callgraph analysis to decide if it's worth summarizing
2250 an edge, and if so, we need summaries. */
2251 if (flag_analyzer_call_summaries
)
2253 int num_call_sites
= 0;
2254 for (cgraph_edge
*edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
2257 /* For now, if there's more than one in-edge, and we want call
2258 summaries, do it at the top level so that there's a chance
2259 we'll have a summary when we need one. */
2260 if (num_call_sites
> 1)
2263 logger
->log ("traversing %qE (%i call sites)",
2264 fun
->decl
, num_call_sites
);
2269 if (!TREE_PUBLIC (fun
->decl
))
2272 logger
->log ("not traversing %qE (static)", fun
->decl
);
2277 logger
->log ("traversing %qE (all checks passed)", fun
->decl
);
2282 /* Callback for walk_tree for finding callbacks within initializers;
2283 ensure they are treated as possible entrypoints to the analysis. */
2286 add_any_callbacks (tree
*tp
, int *, void *data
)
2288 exploded_graph
*eg
= (exploded_graph
*)data
;
2289 if (TREE_CODE (*tp
) == FUNCTION_DECL
)
2290 eg
->on_escaped_function (*tp
);
2294 /* Add initial nodes to EG, with entrypoints for externally-callable
2298 exploded_graph::build_initial_worklist ()
2300 logger
* const logger
= get_logger ();
2304 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
2306 function
*fun
= node
->get_fun ();
2307 if (!toplevel_function_p (node
, fun
, logger
))
2309 exploded_node
*enode
= add_function_entry (fun
);
2313 logger
->log ("created EN %i for %qE entrypoint",
2314 enode
->m_index
, fun
->decl
);
2316 logger
->log ("did not create enode for %qE entrypoint", fun
->decl
);
2320 /* Find callbacks that are reachable from global initializers. */
2321 varpool_node
*vpnode
;
2322 FOR_EACH_VARIABLE (vpnode
)
2324 tree decl
= vpnode
->decl
;
2325 if (!TREE_PUBLIC (decl
))
2327 tree init
= DECL_INITIAL (decl
);
2330 walk_tree (&init
, add_any_callbacks
, this, NULL
);
2334 /* The main loop of the analysis.
2335 Take freshly-created exploded_nodes from the worklist, calling
2336 process_node on them to explore the <point, state> graph.
2337 Add edges to their successors, potentially creating new successors
2338 (which are also added to the worklist). */
2341 exploded_graph::process_worklist ()
2343 logger
* const logger
= get_logger ();
2345 auto_timevar
tv (TV_ANALYZER_WORKLIST
);
2347 while (m_worklist
.length () > 0)
2349 exploded_node
*node
= m_worklist
.take_next ();
2350 gcc_assert (node
->get_status () == exploded_node::STATUS_WORKLIST
);
2351 gcc_assert (node
->m_succs
.length () == 0
2352 || node
== m_origin
);
2355 logger
->log ("next to process: EN: %i", node
->m_index
);
2357 /* If we have a run of nodes that are before-supernode, try merging and
2358 processing them together, rather than pairwise or individually. */
2359 if (flag_analyzer_state_merge
&& node
!= m_origin
)
2360 if (maybe_process_run_of_before_supernode_enodes (node
))
2363 /* Avoid exponential explosions of nodes by attempting to merge
2364 nodes that are at the same program point and which have
2365 sufficiently similar state. */
2366 if (flag_analyzer_state_merge
&& node
!= m_origin
)
2367 if (exploded_node
*node_2
= m_worklist
.peek_next ())
2369 gcc_assert (node_2
->get_status ()
2370 == exploded_node::STATUS_WORKLIST
);
2371 gcc_assert (node
->m_succs
.length () == 0);
2372 gcc_assert (node_2
->m_succs
.length () == 0);
2374 gcc_assert (node
!= node_2
);
2377 logger
->log ("peek worklist: EN: %i", node_2
->m_index
);
2379 if (node
->get_point () == node_2
->get_point ())
2381 const program_point
&point
= node
->get_point ();
2385 pretty_printer
*pp
= logger
->get_printer ();
2386 logger
->start_log_line ();
2388 ("got potential merge EN: %i and EN: %i at ",
2389 node
->m_index
, node_2
->m_index
);
2390 point
.print (pp
, f
);
2391 logger
->end_log_line ();
2393 const program_state
&state
= node
->get_state ();
2394 const program_state
&state_2
= node_2
->get_state ();
2396 /* They shouldn't be equal, or we wouldn't have two
2398 gcc_assert (state
!= state_2
);
2400 program_state
merged_state (m_ext_state
);
2401 if (state
.can_merge_with_p (state_2
, point
, &merged_state
))
2404 logger
->log ("merging EN: %i and EN: %i",
2405 node
->m_index
, node_2
->m_index
);
2407 if (merged_state
== state
)
2409 /* Then merge node_2 into node by adding an edge. */
2410 add_edge (node_2
, node
, NULL
);
2412 /* Remove node_2 from the worklist. */
2413 m_worklist
.take_next ();
2414 node_2
->set_status (exploded_node::STATUS_MERGER
);
2416 /* Continue processing "node" below. */
2418 else if (merged_state
== state_2
)
2420 /* Then merge node into node_2, and leave node_2
2421 in the worklist, to be processed on the next
2423 add_edge (node
, node_2
, NULL
);
2424 node
->set_status (exploded_node::STATUS_MERGER
);
2429 /* We have a merged state that differs from
2430 both state and state_2. */
2432 /* Remove node_2 from the worklist. */
2433 m_worklist
.take_next ();
2435 /* Create (or get) an exploded node for the merged
2436 states, adding to the worklist. */
2437 exploded_node
*merged_enode
2438 = get_or_create_node (node
->get_point (),
2439 merged_state
, node
);
2440 if (merged_enode
== NULL
)
2444 logger
->log ("merged EN: %i and EN: %i into EN: %i",
2445 node
->m_index
, node_2
->m_index
,
2446 merged_enode
->m_index
);
2448 /* "node" and "node_2" have both now been removed
2449 from the worklist; we should not process them.
2451 "merged_enode" may be a new node; if so it will be
2452 processed in a subsequent iteration.
2453 Alternatively, "merged_enode" could be an existing
2454 node; one way the latter can
2455 happen is if we end up merging a succession of
2456 similar nodes into one. */
2458 /* If merged_node is one of the two we were merging,
2459 add it back to the worklist to ensure it gets
2462 Add edges from the merged nodes to it (but not a
2464 if (merged_enode
== node
)
2465 m_worklist
.add_node (merged_enode
);
2468 add_edge (node
, merged_enode
, NULL
);
2469 node
->set_status (exploded_node::STATUS_MERGER
);
2472 if (merged_enode
== node_2
)
2473 m_worklist
.add_node (merged_enode
);
2476 add_edge (node_2
, merged_enode
, NULL
);
2477 node_2
->set_status (exploded_node::STATUS_MERGER
);
2484 /* TODO: should we attempt more than two nodes,
2485 or just do pairs of nodes? (and hope that we get
2486 a cascade of mergers). */
2490 process_node (node
);
2493 /* Impose a hard limit on the number of exploded nodes, to ensure
2494 that the analysis terminates in the face of pathological state
2495 explosion (or bugs).
2497 Specifically, the limit is on the number of PK_AFTER_SUPERNODE
2498 exploded nodes, looking at supernode exit events.
2500 We use exit rather than entry since there can be multiple
2501 entry ENs, one per phi; the number of PK_AFTER_SUPERNODE ought
2502 to be equivalent to the number of supernodes multiplied by the
2503 number of states. */
2504 const int limit
= m_sg
.num_nodes () * param_analyzer_bb_explosion_factor
;
2505 if (m_global_stats
.m_num_nodes
[PK_AFTER_SUPERNODE
] > limit
)
2508 logger
->log ("bailing out; too many nodes");
2509 warning_at (node
->get_point ().get_location (),
2510 OPT_Wanalyzer_too_complex
,
2511 "analysis bailed out early"
2512 " (%i 'after-snode' enodes; %i enodes)",
2513 m_global_stats
.m_num_nodes
[PK_AFTER_SUPERNODE
],
2520 /* Attempt to process a consecutive run of sufficiently-similar nodes in
2521 the worklist at a CFG join-point (having already popped ENODE from the
2522 head of the worklist).
2524 If ENODE's point is of the form (before-supernode, SNODE) and the next
2525 nodes in the worklist are a consecutive run of enodes of the same form,
2526 for the same supernode as ENODE (but potentially from different in-edges),
2527 process them all together, setting their status to STATUS_BULK_MERGED,
2529 Otherwise, return false, in which case ENODE must be processed in the
2532 When processing them all together, generate successor states based
2533 on phi nodes for the appropriate CFG edges, and then attempt to merge
2534 these states into a minimal set of merged successor states, partitioning
2535 the inputs by merged successor state.
2537 Create new exploded nodes for all of the merged states, and add edges
2538 connecting the input enodes to the corresponding merger exploded nodes.
2540 We hope we have a much smaller number of merged successor states
2541 compared to the number of input enodes - ideally just one,
2542 if all successor states can be merged.
2544 Processing and merging many together as one operation rather than as
2545 pairs avoids scaling issues where per-pair mergers could bloat the
2546 graph with merger nodes (especially so after switch statements). */
2550 maybe_process_run_of_before_supernode_enodes (exploded_node
*enode
)
2552 /* A struct for tracking per-input state. */
2555 item (exploded_node
*input_enode
)
2556 : m_input_enode (input_enode
),
2557 m_processed_state (input_enode
->get_state ()),
2561 exploded_node
*m_input_enode
;
2562 program_state m_processed_state
;
2566 gcc_assert (enode
->get_status () == exploded_node::STATUS_WORKLIST
);
2567 gcc_assert (enode
->m_succs
.length () == 0);
2569 const program_point
&point
= enode
->get_point ();
2571 if (point
.get_kind () != PK_BEFORE_SUPERNODE
)
2574 const supernode
*snode
= point
.get_supernode ();
2576 logger
* const logger
= get_logger ();
2579 /* Find a run of enodes in the worklist that are before the same supernode,
2580 but potentially from different in-edges. */
2581 auto_vec
<exploded_node
*> enodes
;
2582 enodes
.safe_push (enode
);
2583 while (exploded_node
*enode_2
= m_worklist
.peek_next ())
2585 gcc_assert (enode_2
->get_status ()
2586 == exploded_node::STATUS_WORKLIST
);
2587 gcc_assert (enode_2
->m_succs
.length () == 0);
2589 const program_point
&point_2
= enode_2
->get_point ();
2591 if (point_2
.get_kind () == PK_BEFORE_SUPERNODE
2592 && point_2
.get_supernode () == snode
2593 && point_2
.get_call_string () == point
.get_call_string ())
2595 enodes
.safe_push (enode_2
);
2596 m_worklist
.take_next ();
2602 /* If the only node is ENODE, then give up. */
2603 if (enodes
.length () == 1)
2607 logger
->log ("got run of %i enodes for SN: %i",
2608 enodes
.length (), snode
->m_index
);
2610 /* All of these enodes have a shared successor point (even if they
2611 were for different in-edges). */
2612 program_point
next_point (point
.get_next ());
2614 /* Calculate the successor state for each enode in enodes. */
2615 auto_delete_vec
<item
> items (enodes
.length ());
2617 exploded_node
*iter_enode
;
2618 FOR_EACH_VEC_ELT (enodes
, i
, iter_enode
)
2620 item
*it
= new item (iter_enode
);
2621 items
.quick_push (it
);
2622 const program_state
&state
= iter_enode
->get_state ();
2623 program_state
*next_state
= &it
->m_processed_state
;
2624 const program_point
&iter_point
= iter_enode
->get_point ();
2625 if (const superedge
*iter_sedge
= iter_point
.get_from_edge ())
2627 impl_region_model_context
ctxt (*this, iter_enode
,
2628 &state
, next_state
, NULL
);
2629 const cfg_superedge
*last_cfg_superedge
2630 = iter_sedge
->dyn_cast_cfg_superedge ();
2631 if (last_cfg_superedge
)
2632 next_state
->m_region_model
->update_for_phis
2633 (snode
, last_cfg_superedge
, &ctxt
);
2637 /* Attempt to partition the items into a set of merged states.
2638 We hope we have a much smaller number of merged states
2639 compared to the number of input enodes - ideally just one,
2640 if all can be merged. */
2641 auto_delete_vec
<program_state
> merged_states
;
2642 auto_vec
<item
*> first_item_for_each_merged_state
;
2644 FOR_EACH_VEC_ELT (items
, i
, it
)
2646 const program_state
&it_state
= it
->m_processed_state
;
2647 program_state
*merged_state
;
2648 unsigned iter_merger_idx
;
2649 FOR_EACH_VEC_ELT (merged_states
, iter_merger_idx
, merged_state
)
2651 program_state
merge (m_ext_state
);
2652 if (it_state
.can_merge_with_p (*merged_state
, next_point
, &merge
))
2654 *merged_state
= merge
;
2655 it
->m_merger_idx
= iter_merger_idx
;
2657 logger
->log ("reusing merger state %i for item %i (EN: %i)",
2658 it
->m_merger_idx
, i
, it
->m_input_enode
->m_index
);
2662 /* If it couldn't be merged with any existing merged_states,
2663 create a new one. */
2664 if (it
->m_merger_idx
== -1)
2666 it
->m_merger_idx
= merged_states
.length ();
2667 merged_states
.safe_push (new program_state (it_state
));
2668 first_item_for_each_merged_state
.safe_push (it
);
2670 logger
->log ("using new merger state %i for item %i (EN: %i)",
2671 it
->m_merger_idx
, i
, it
->m_input_enode
->m_index
);
2674 gcc_assert (it
->m_merger_idx
>= 0);
2675 gcc_assert ((unsigned)it
->m_merger_idx
< merged_states
.length ());
2678 /* Create merger nodes. */
2679 auto_vec
<exploded_node
*> next_enodes (merged_states
.length ());
2680 program_state
*merged_state
;
2681 FOR_EACH_VEC_ELT (merged_states
, i
, merged_state
)
2683 exploded_node
*src_enode
2684 = first_item_for_each_merged_state
[i
]->m_input_enode
;
2686 = get_or_create_node (next_point
, *merged_state
, src_enode
);
2687 /* "next" could be NULL; we handle that when adding the edges below. */
2688 next_enodes
.quick_push (next
);
2692 logger
->log ("using EN: %i for merger state %i", next
->m_index
, i
);
2694 logger
->log ("using NULL enode for merger state %i", i
);
2698 /* Create edges from each input enode to the appropriate successor enode.
2699 Update the status of the now-processed input enodes. */
2700 FOR_EACH_VEC_ELT (items
, i
, it
)
2702 exploded_node
*next
= next_enodes
[it
->m_merger_idx
];
2704 add_edge (it
->m_input_enode
, next
, NULL
);
2705 it
->m_input_enode
->set_status (exploded_node::STATUS_BULK_MERGED
);
2709 logger
->log ("merged %i in-enodes into %i out-enode(s) at SN: %i",
2710 items
.length (), merged_states
.length (), snode
->m_index
);
2715 /* Return true if STMT must appear at the start of its exploded node, and
2716 thus we can't consolidate its effects within a run of other statements,
2717 where PREV_STMT was the previous statement. */
2720 stmt_requires_new_enode_p (const gimple
*stmt
,
2721 const gimple
*prev_stmt
)
2723 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
2725 /* Stop consolidating at calls to
2726 "__analyzer_dump_exploded_nodes", so they always appear at the
2727 start of an exploded_node. */
2728 if (is_special_named_call_p (call
, "__analyzer_dump_exploded_nodes",
2732 /* sm-signal.cc injects an additional custom eedge at "signal" calls
2733 from the registration enode to the handler enode, separate from the
2734 regular next state, which defeats the "detect state change" logic
2735 in process_node. Work around this via special-casing, to ensure
2736 we split the enode immediately before any "signal" call. */
2737 if (is_special_named_call_p (call
, "signal", 2))
2741 /* If we had a PREV_STMT with an unknown location, and this stmt
2742 has a known location, then if a state change happens here, it
2743 could be consolidated into PREV_STMT, giving us an event with
2744 no location. Ensure that STMT gets its own exploded_node to
2746 if (get_pure_location (prev_stmt
->location
) == UNKNOWN_LOCATION
2747 && get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
2753 /* The core of exploded_graph::process_worklist (the main analysis loop),
2754 handling one node in the worklist.
2756 Get successor <point, state> pairs for NODE, calling get_or_create on
2757 them, and adding an exploded_edge to each successors.
2759 Freshly-created nodes will be added to the worklist. */
2762 exploded_graph::process_node (exploded_node
*node
)
2764 logger
* const logger
= get_logger ();
2765 LOG_FUNC_1 (logger
, "EN: %i", node
->m_index
);
2767 node
->set_status (exploded_node::STATUS_PROCESSED
);
2769 const program_point
&point
= node
->get_point ();
2771 /* Update cfun and input_location in case of an ICE: make it easier to
2772 track down which source construct we're failing to handle. */
2773 auto_cfun
sentinel (node
->get_function ());
2774 const gimple
*stmt
= point
.get_stmt ();
2776 input_location
= stmt
->location
;
2778 const program_state
&state
= node
->get_state ();
2781 pretty_printer
*pp
= logger
->get_printer ();
2782 logger
->start_log_line ();
2783 pp_string (pp
, "point: ");
2784 point
.print (pp
, format (false));
2785 pp_string (pp
, ", state: ");
2786 state
.dump_to_pp (m_ext_state
, true, false, pp
);
2787 logger
->end_log_line ();
2790 switch (point
.get_kind ())
2795 /* This node exists to simplify finding the shortest path
2796 to an exploded_node. */
2799 case PK_BEFORE_SUPERNODE
:
2801 program_state
next_state (state
);
2803 if (point
.get_from_edge ())
2805 impl_region_model_context
ctxt (*this, node
,
2806 &state
, &next_state
, NULL
);
2807 const cfg_superedge
*last_cfg_superedge
2808 = point
.get_from_edge ()->dyn_cast_cfg_superedge ();
2809 if (last_cfg_superedge
)
2810 next_state
.m_region_model
->update_for_phis
2811 (node
->get_supernode (),
2816 program_point
next_point (point
.get_next ());
2817 exploded_node
*next
= get_or_create_node (next_point
, next_state
, node
);
2819 add_edge (node
, next
, NULL
);
2822 case PK_BEFORE_STMT
:
2824 /* Determine the effect of a run of one or more statements
2825 within one supernode, generating an edge to the program_point
2826 after the last statement that's processed.
2828 Stop iterating statements and thus consolidating into one enode
2830 - reaching the end of the statements in the supernode
2831 - if an sm-state-change occurs (so that it gets its own
2833 - if "-fanalyzer-fine-grained" is active
2834 - encountering certain statements must appear at the start of
2835 their enode (for which stmt_requires_new_enode_p returns true)
2837 Update next_state in-place, to get the result of the one
2838 or more stmts that are processed.
2840 Split the node in-place if an sm-state-change occurs, so that
2841 the sm-state-change occurs on an edge where the src enode has
2842 exactly one stmt, the one that caused the change. */
2843 program_state
next_state (state
);
2844 const supernode
*snode
= point
.get_supernode ();
2846 const gimple
*prev_stmt
= NULL
;
2847 for (stmt_idx
= point
.get_stmt_idx ();
2848 stmt_idx
< snode
->m_stmts
.length ();
2851 const gimple
*stmt
= snode
->m_stmts
[stmt_idx
];
2853 if (stmt_idx
> point
.get_stmt_idx ())
2854 if (stmt_requires_new_enode_p (stmt
, prev_stmt
))
2861 program_state
old_state (next_state
);
2863 /* Process the stmt. */
2864 exploded_node::on_stmt_flags flags
2865 = node
->on_stmt (*this, snode
, stmt
, &next_state
);
2866 node
->m_num_processed_stmts
++;
2868 /* If flags.m_terminate_path, stop analyzing; any nodes/edges
2869 will have been added by on_stmt (e.g. for handling longjmp). */
2870 if (flags
.m_terminate_path
)
2873 if (next_state
.m_region_model
)
2875 impl_region_model_context
ctxt (*this, node
,
2876 &old_state
, &next_state
, stmt
);
2877 program_state::detect_leaks (old_state
, next_state
, NULL
,
2878 get_ext_state (), &ctxt
);
2881 unsigned next_idx
= stmt_idx
+ 1;
2882 program_point next_point
2883 = (next_idx
< point
.get_supernode ()->m_stmts
.length ()
2884 ? program_point::before_stmt (point
.get_supernode (), next_idx
,
2885 point
.get_call_string ())
2886 : program_point::after_supernode (point
.get_supernode (),
2887 point
.get_call_string ()));
2888 next_state
= next_state
.prune_for_point (*this, next_point
, node
);
2890 if (flags
.m_sm_changes
|| flag_analyzer_fine_grained
)
2892 program_point split_point
2893 = program_point::before_stmt (point
.get_supernode (),
2895 point
.get_call_string ());
2896 if (split_point
!= node
->get_point ())
2898 /* If we're not at the start of NODE, split the enode at
2899 this stmt, so we have:
2901 so that when split_enode is processed the next edge
2904 and any state change will effectively occur on that
2905 latter edge, and split_enode will contain just stmt. */
2907 logger
->log ("getting split_enode");
2908 exploded_node
*split_enode
2909 = get_or_create_node (split_point
, old_state
, node
);
2912 /* "stmt" will be reprocessed when split_enode is
2914 node
->m_num_processed_stmts
--;
2916 logger
->log ("creating edge to split_enode");
2917 add_edge (node
, split_enode
, NULL
);
2921 /* If we're at the start of NODE, stop iterating,
2922 so that an edge will be created from NODE to
2923 (next_point, next_state) below. */
2927 unsigned next_idx
= stmt_idx
+ 1;
2928 program_point next_point
2929 = (next_idx
< point
.get_supernode ()->m_stmts
.length ()
2930 ? program_point::before_stmt (point
.get_supernode (), next_idx
,
2931 point
.get_call_string ())
2932 : program_point::after_supernode (point
.get_supernode (),
2933 point
.get_call_string ()));
2934 exploded_node
*next
= get_or_create_node (next_point
, next_state
, node
);
2936 add_edge (node
, next
, NULL
);
2939 case PK_AFTER_SUPERNODE
:
2941 /* If this is an EXIT BB, detect leaks, and potentially
2942 create a function summary. */
2943 if (point
.get_supernode ()->return_p ())
2945 node
->detect_leaks (*this);
2946 if (flag_analyzer_call_summaries
2947 && point
.get_call_string ().empty_p ())
2949 /* TODO: create function summary
2950 There can be more than one; each corresponds to a different
2951 final enode in the function. */
2954 pretty_printer
*pp
= logger
->get_printer ();
2955 logger
->start_log_line ();
2957 ("would create function summary for %qE; state: ",
2958 point
.get_fndecl ());
2959 state
.dump_to_pp (m_ext_state
, true, false, pp
);
2960 logger
->end_log_line ();
2962 per_function_data
*per_fn_data
2963 = get_or_create_per_function_data (point
.get_function ());
2964 per_fn_data
->add_call_summary (node
);
2967 /* Traverse into successors of the supernode. */
2970 FOR_EACH_VEC_ELT (point
.get_supernode ()->m_succs
, i
, succ
)
2973 logger
->log ("considering SN: %i -> SN: %i",
2974 succ
->m_src
->m_index
, succ
->m_dest
->m_index
);
2976 program_point next_point
2977 = program_point::before_supernode (succ
->m_dest
, succ
,
2978 point
.get_call_string ());
2979 program_state
next_state (state
);
2981 if (!node
->on_edge (*this, succ
, &next_point
, &next_state
))
2984 logger
->log ("skipping impossible edge to SN: %i",
2985 succ
->m_dest
->m_index
);
2989 exploded_node
*next
= get_or_create_node (next_point
, next_state
,
2992 add_edge (node
, next
, succ
);
2999 /* Ensure that this graph has a stats instance for FN, return it.
3000 FN can be NULL, in which case a stats instances is returned covering
3001 "functionless" parts of the graph (the origin node). */
3004 exploded_graph::get_or_create_function_stats (function
*fn
)
3007 return &m_functionless_stats
;
3009 if (stats
**slot
= m_per_function_stats
.get (fn
))
3013 int num_supernodes
= fn
? n_basic_blocks_for_fn (fn
) : 0;
3014 /* not quite the num supernodes, but nearly. */
3015 stats
*new_stats
= new stats (num_supernodes
);
3016 m_per_function_stats
.put (fn
, new_stats
);
3021 /* Print bar charts to PP showing:
3022 - the number of enodes per function, and
3023 - for each function:
3024 - the number of enodes per supernode/BB
3025 - the number of excess enodes per supernode/BB beyond the
3026 per-program-point limit, if there were any. */
3029 exploded_graph::print_bar_charts (pretty_printer
*pp
) const
3031 cgraph_node
*cgnode
;
3033 pp_string (pp
, "enodes per function:");
3035 bar_chart enodes_per_function
;
3036 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode
)
3038 function
*fn
= cgnode
->get_fun ();
3039 const stats
* const *s_ptr
3040 = const_cast <function_stat_map_t
&> (m_per_function_stats
).get (fn
);
3041 enodes_per_function
.add_item (function_name (fn
),
3042 s_ptr
? (*s_ptr
)->get_total_enodes () : 0);
3044 enodes_per_function
.print (pp
);
3046 /* Accumulate number of enodes per supernode. */
3047 auto_vec
<unsigned> enodes_per_supernode (m_sg
.num_nodes ());
3048 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
3049 enodes_per_supernode
.quick_push (0);
3051 exploded_node
*enode
;
3052 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
3054 const supernode
*iter_snode
= enode
->get_supernode ();
3057 enodes_per_supernode
[iter_snode
->m_index
]++;
3060 /* Accumulate excess enodes per supernode. */
3061 auto_vec
<unsigned> excess_enodes_per_supernode (m_sg
.num_nodes ());
3062 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
3063 excess_enodes_per_supernode
.quick_push (0);
3064 for (point_map_t::iterator iter
= m_per_point_data
.begin ();
3065 iter
!= m_per_point_data
.end (); ++iter
)
3067 const program_point
*point
= (*iter
).first
;
3068 const supernode
*iter_snode
= point
->get_supernode ();
3071 const per_program_point_data
*point_data
= (*iter
).second
;
3072 excess_enodes_per_supernode
[iter_snode
->m_index
]
3073 += point_data
->m_excess_enodes
;
3076 /* Show per-function bar_charts of enodes per supernode/BB. */
3077 pp_string (pp
, "per-function enodes per supernode/BB:");
3079 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode
)
3081 function
*fn
= cgnode
->get_fun ();
3082 pp_printf (pp
, "function: %qs", function_name (fn
));
3085 bar_chart enodes_per_snode
;
3086 bar_chart excess_enodes_per_snode
;
3087 bool have_excess_enodes
= false;
3088 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
3090 const supernode
*iter_snode
= m_sg
.get_node_by_index (i
);
3091 if (iter_snode
->get_function () != fn
)
3093 pretty_printer tmp_pp
;
3094 pp_printf (&tmp_pp
, "sn %i (bb %i)",
3095 iter_snode
->m_index
, iter_snode
->m_bb
->index
);
3096 enodes_per_snode
.add_item (pp_formatted_text (&tmp_pp
),
3097 enodes_per_supernode
[iter_snode
->m_index
]);
3098 const int num_excess
3099 = excess_enodes_per_supernode
[iter_snode
->m_index
];
3100 excess_enodes_per_snode
.add_item (pp_formatted_text (&tmp_pp
),
3103 have_excess_enodes
= true;
3105 enodes_per_snode
.print (pp
);
3106 if (have_excess_enodes
)
3108 pp_printf (pp
, "EXCESS ENODES:");
3110 excess_enodes_per_snode
.print (pp
);
3115 /* Write all stats information to this graph's logger, if any. */
3118 exploded_graph::log_stats () const
3120 logger
* const logger
= get_logger ();
3126 m_ext_state
.get_engine ()->log_stats (logger
);
3128 logger
->log ("m_sg.num_nodes (): %i", m_sg
.num_nodes ());
3129 logger
->log ("m_nodes.length (): %i", m_nodes
.length ());
3130 logger
->log ("m_edges.length (): %i", m_edges
.length ());
3131 logger
->log ("remaining enodes in worklist: %i", m_worklist
.length ());
3133 logger
->log ("global stats:");
3134 m_global_stats
.log (logger
);
3136 for (function_stat_map_t::iterator iter
= m_per_function_stats
.begin ();
3137 iter
!= m_per_function_stats
.end ();
3140 function
*fn
= (*iter
).first
;
3141 log_scope
s (logger
, function_name (fn
));
3142 (*iter
).second
->log (logger
);
3145 print_bar_charts (logger
->get_printer ());
3148 /* Dump all stats information to OUT. */
3151 exploded_graph::dump_stats (FILE *out
) const
3153 fprintf (out
, "m_sg.num_nodes (): %i\n", m_sg
.num_nodes ());
3154 fprintf (out
, "m_nodes.length (): %i\n", m_nodes
.length ());
3155 fprintf (out
, "m_edges.length (): %i\n", m_edges
.length ());
3156 fprintf (out
, "remaining enodes in worklist: %i", m_worklist
.length ());
3158 fprintf (out
, "global stats:\n");
3159 m_global_stats
.dump (out
);
3161 for (function_stat_map_t::iterator iter
= m_per_function_stats
.begin ();
3162 iter
!= m_per_function_stats
.end ();
3165 function
*fn
= (*iter
).first
;
3166 fprintf (out
, "function: %s\n", function_name (fn
));
3167 (*iter
).second
->dump (out
);
3170 fprintf (out
, "PK_AFTER_SUPERNODE per supernode:\n");
3171 for (unsigned i
= 0; i
< m_PK_AFTER_SUPERNODE_per_snode
.length (); i
++)
3172 fprintf (out
, " SN %i: %3i\n", i
, m_PK_AFTER_SUPERNODE_per_snode
[i
]);
3176 exploded_graph::dump_states_for_supernode (FILE *out
,
3177 const supernode
*snode
) const
3179 fprintf (out
, "PK_AFTER_SUPERNODE nodes for SN: %i\n", snode
->m_index
);
3181 exploded_node
*enode
;
3183 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
3185 const supernode
*iter_snode
= enode
->get_supernode ();
3186 if (enode
->get_point ().get_kind () == PK_AFTER_SUPERNODE
3187 && iter_snode
== snode
)
3190 pp_format_decoder (&pp
) = default_tree_printer
;
3191 enode
->get_state ().dump_to_pp (m_ext_state
, true, false, &pp
);
3192 fprintf (out
, "state %i: EN: %i\n %s\n",
3193 state_idx
++, enode
->m_index
,
3194 pp_formatted_text (&pp
));
3197 fprintf (out
, "#exploded_node for PK_AFTER_SUPERNODE for SN: %i = %i\n",
3198 snode
->m_index
, state_idx
);
3201 /* Return a new json::object of the form
3202 {"nodes" : [objs for enodes],
3203 "edges" : [objs for eedges],
3204 "ext_state": object for extrinsic_state,
3205 "diagnostic_manager": object for diagnostic_manager}. */
3208 exploded_graph::to_json () const
3210 json::object
*egraph_obj
= new json::object ();
3214 json::array
*nodes_arr
= new json::array ();
3217 FOR_EACH_VEC_ELT (m_nodes
, i
, n
)
3218 nodes_arr
->append (n
->to_json (m_ext_state
));
3219 egraph_obj
->set ("nodes", nodes_arr
);
3224 json::array
*edges_arr
= new json::array ();
3227 FOR_EACH_VEC_ELT (m_edges
, i
, n
)
3228 edges_arr
->append (n
->to_json ());
3229 egraph_obj
->set ("edges", edges_arr
);
3232 /* m_sg is JSONified at the top-level. */
3234 egraph_obj
->set ("ext_state", m_ext_state
.to_json ());
3235 egraph_obj
->set ("diagnostic_manager", m_diagnostic_manager
.to_json ());
3237 /* The following fields aren't yet being JSONified:
3238 worklist m_worklist;
3239 const state_purge_map *const m_purge_map;
3240 const analysis_plan &m_plan;
3241 stats m_global_stats;
3242 function_stat_map_t m_per_function_stats;
3243 stats m_functionless_stats;
3244 call_string_data_map_t m_per_call_string_data;
3245 auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode; */
3250 /* Look for the last use of SEARCH_STMT within this path.
3251 If found write the edge's index to *OUT_IDX and return true, otherwise
3255 exploded_path::find_stmt_backwards (const gimple
*search_stmt
,
3259 const exploded_edge
*eedge
;
3260 FOR_EACH_VEC_ELT_REVERSE (m_edges
, i
, eedge
)
3262 const exploded_node
*dst_node
= eedge
->m_dest
;
3263 const program_point
&dst_point
= dst_node
->get_point ();
3264 const gimple
*stmt
= dst_point
.get_stmt ();
3265 if (stmt
== search_stmt
)
3274 /* Get the final exploded_node in this path, which must be non-empty. */
3277 exploded_path::get_final_enode () const
3279 gcc_assert (m_edges
.length () > 0);
3280 return m_edges
[m_edges
.length () - 1]->m_dest
;
3283 /* Check state along this path, returning true if it is feasible.
3284 If OUT is non-NULL, and the path is infeasible, write a new
3285 feasibility_problem to *OUT. */
3288 exploded_path::feasible_p (logger
*logger
, feasibility_problem
**out
,
3289 engine
*eng
, const exploded_graph
*eg
) const
3293 auto_sbitmap
snodes_visited (eg
->get_supergraph ().m_nodes
.length ());
3295 /* Traverse the path, updating this model. */
3296 region_model
model (eng
->get_model_manager ());
3297 for (unsigned edge_idx
= 0; edge_idx
< m_edges
.length (); edge_idx
++)
3299 const exploded_edge
*eedge
= m_edges
[edge_idx
];
3301 logger
->log ("considering edge %i: EN:%i -> EN:%i",
3303 eedge
->m_src
->m_index
,
3304 eedge
->m_dest
->m_index
);
3305 const exploded_node
&src_enode
= *eedge
->m_src
;
3306 const program_point
&src_point
= src_enode
.get_point ();
3309 logger
->start_log_line ();
3310 src_point
.print (logger
->get_printer (), format (false));
3311 logger
->end_log_line ();
3314 /* Update state for the stmts that were processed in each enode. */
3315 for (unsigned stmt_idx
= 0; stmt_idx
< src_enode
.m_num_processed_stmts
;
3318 const gimple
*stmt
= src_enode
.get_processed_stmt (stmt_idx
);
3320 /* Update cfun and input_location in case of ICE: make it easier to
3321 track down which source construct we're failing to handle. */
3322 auto_cfun
sentinel (src_point
.get_function ());
3323 input_location
= stmt
->location
;
3325 if (const gassign
*assign
= dyn_cast
<const gassign
*> (stmt
))
3326 model
.on_assignment (assign
, NULL
);
3327 else if (const greturn
*return_
= dyn_cast
<const greturn
*> (stmt
))
3328 model
.on_return (return_
, NULL
);
3331 const superedge
*sedge
= eedge
->m_sedge
;
3335 logger
->log (" sedge: SN:%i -> SN:%i %s",
3336 sedge
->m_src
->m_index
,
3337 sedge
->m_dest
->m_index
,
3338 sedge
->get_description (false));
3340 const gimple
*last_stmt
= src_point
.get_supernode ()->get_last_stmt ();
3341 rejected_constraint
*rc
= NULL
;
3342 if (!model
.maybe_update_for_edge (*sedge
, last_stmt
, NULL
, &rc
))
3346 logger
->log ("rejecting due to region model");
3347 model
.dump_to_pp (logger
->get_printer (), true, false);
3350 *out
= new feasibility_problem (edge_idx
, *eedge
,
3359 /* Special-case the initial eedge from the origin node to the
3360 initial function by pushing a frame for it. */
3363 gcc_assert (eedge
->m_src
->m_index
== 0);
3364 gcc_assert (src_point
.get_kind () == PK_ORIGIN
);
3365 gcc_assert (eedge
->m_dest
->get_point ().get_kind ()
3366 == PK_BEFORE_SUPERNODE
);
3367 function
*fun
= eedge
->m_dest
->get_function ();
3369 model
.push_frame (fun
, NULL
, NULL
);
3371 logger
->log (" pushing frame for %qD", fun
->decl
);
3373 else if (eedge
->m_custom_info
)
3375 eedge
->m_custom_info
->update_model (&model
, *eedge
);
3379 /* Handle phi nodes on an edge leaving a PK_BEFORE_SUPERNODE (to
3380 a PK_BEFORE_STMT, or a PK_AFTER_SUPERNODE if no stmts).
3381 This will typically not be associated with a superedge. */
3382 if (src_point
.get_from_edge ())
3384 const cfg_superedge
*last_cfg_superedge
3385 = src_point
.get_from_edge ()->dyn_cast_cfg_superedge ();
3386 const exploded_node
&dst_enode
= *eedge
->m_dest
;
3387 const unsigned dst_snode_idx
= dst_enode
.get_supernode ()->m_index
;
3388 if (last_cfg_superedge
)
3391 logger
->log (" update for phis");
3392 model
.update_for_phis (src_enode
.get_supernode (),
3395 /* If we've entering an snode that we've already visited on this
3396 epath, then we need do fix things up for loops; see the
3397 comment for store::loop_replay_fixup.
3398 Perhaps we should probably also verify the callstring,
3399 and track program_points, but hopefully doing it by supernode
3401 if (bitmap_bit_p (snodes_visited
, dst_snode_idx
))
3402 model
.loop_replay_fixup (dst_enode
.get_state ().m_region_model
);
3404 bitmap_set_bit (snodes_visited
, dst_snode_idx
);
3409 logger
->log ("state after edge %i: EN:%i -> EN:%i",
3411 eedge
->m_src
->m_index
,
3412 eedge
->m_dest
->m_index
);
3413 logger
->start_log_line ();
3414 model
.dump_to_pp (logger
->get_printer (), true, false);
3415 logger
->end_log_line ();
3422 /* Dump this path in multiline form to PP. */
3425 exploded_path::dump_to_pp (pretty_printer
*pp
) const
3427 for (unsigned i
= 0; i
< m_edges
.length (); i
++)
3429 const exploded_edge
*eedge
= m_edges
[i
];
3430 pp_printf (pp
, "m_edges[%i]: EN %i -> EN %i",
3432 eedge
->m_src
->m_index
,
3433 eedge
->m_dest
->m_index
);
3438 /* Dump this path in multiline form to FP. */
3441 exploded_path::dump (FILE *fp
) const
3444 pp_format_decoder (&pp
) = default_tree_printer
;
3445 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
3446 pp
.buffer
->stream
= fp
;
3451 /* Dump this path in multiline form to stderr. */
3454 exploded_path::dump () const
3459 /* class feasibility_problem. */
3462 feasibility_problem::dump_to_pp (pretty_printer
*pp
) const
3464 pp_printf (pp
, "edge from EN: %i to EN: %i",
3465 m_eedge
.m_src
->m_index
, m_eedge
.m_dest
->m_index
);
3468 pp_string (pp
, "; rejected constraint: ");
3469 m_rc
->dump_to_pp (pp
);
3470 pp_string (pp
, "; rmodel: ");
3471 m_rc
->m_model
.dump_to_pp (pp
, true, false);
3475 /* A family of cluster subclasses for use when generating .dot output for
3476 exploded graphs (-fdump-analyzer-exploded-graph), for grouping the
3477 enodes into hierarchical boxes.
3479 All functionless enodes appear in the top-level graph.
3480 Every (function, call_string) pair gets its own cluster. Within that
3481 cluster, each supernode gets its own cluster.
3483 Hence all enodes relating to a particular function with a particular
3484 callstring will be in a cluster together; all enodes for the same
3485 function but with a different callstring will be in a different
3488 /* Base class of cluster for clustering exploded_node instances in .dot
3489 output, based on various subclass-specific criteria. */
3491 class exploded_cluster
: public cluster
<eg_traits
>
3495 /* Cluster containing all exploded_node instances for one supernode. */
3497 class supernode_cluster
: public exploded_cluster
3500 supernode_cluster (const supernode
*supernode
) : m_supernode (supernode
) {}
3504 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const FINAL OVERRIDE
3506 gv
->println ("subgraph \"cluster_supernode_%p\" {",
3507 (const void *)this);
3509 gv
->println ("style=\"dashed\";");
3510 gv
->println ("label=\"SN: %i (bb: %i; scc: %i)\";",
3511 m_supernode
->m_index
, m_supernode
->m_bb
->index
,
3512 args
.m_eg
.get_scc_id (*m_supernode
));
3515 exploded_node
*enode
;
3516 FOR_EACH_VEC_ELT (m_enodes
, i
, enode
)
3517 enode
->dump_dot (gv
, args
);
3519 /* Terminate subgraph. */
3524 void add_node (exploded_node
*en
) FINAL OVERRIDE
3526 m_enodes
.safe_push (en
);
3530 const supernode
*m_supernode
;
3531 auto_vec
<exploded_node
*> m_enodes
;
3534 /* Cluster containing all supernode_cluster instances for one
3535 (function, call_string) pair. */
3537 class function_call_string_cluster
: public exploded_cluster
3540 function_call_string_cluster (function
*fun
, call_string cs
)
3541 : m_fun (fun
), m_cs (cs
) {}
3543 ~function_call_string_cluster ()
3545 for (map_t::iterator iter
= m_map
.begin ();
3546 iter
!= m_map
.end ();
3548 delete (*iter
).second
;
3551 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const FINAL OVERRIDE
3553 const char *funcname
= function_name (m_fun
);
3555 gv
->println ("subgraph \"cluster_function_%p\" {", (const void *)this);
3557 gv
->write_indent ();
3558 gv
->print ("label=\"call string: ");
3559 m_cs
.print (gv
->get_pp ());
3560 gv
->print (" function: %s \";", funcname
);
3563 for (map_t::iterator iter
= m_map
.begin ();
3564 iter
!= m_map
.end ();
3566 (*iter
).second
->dump_dot (gv
, args
);
3568 /* Terminate subgraph. */
3573 void add_node (exploded_node
*en
) FINAL OVERRIDE
3575 const supernode
*supernode
= en
->get_supernode ();
3576 gcc_assert (supernode
);
3577 supernode_cluster
**slot
= m_map
.get (supernode
);
3579 (*slot
)->add_node (en
);
3582 supernode_cluster
*child
= new supernode_cluster (supernode
);
3583 m_map
.put (supernode
, child
);
3584 child
->add_node (en
);
3591 typedef ordered_hash_map
<const supernode
*, supernode_cluster
*> map_t
;
3595 /* Keys for root_cluster. */
3597 struct function_call_string
3599 function_call_string (function
*fun
, call_string cs
)
3600 : m_fun (fun
), m_cs (cs
)
3611 template <> struct default_hash_traits
<function_call_string
>
3612 : public pod_hash_traits
<function_call_string
>
3614 static const bool empty_zero_p
= false;
3619 pod_hash_traits
<function_call_string
>::hash (value_type v
)
3621 return pointer_hash
<function
>::hash (v
.m_fun
) ^ v
.m_cs
.hash ();
3626 pod_hash_traits
<function_call_string
>::equal (const value_type
&existing
,
3627 const value_type
&candidate
)
3629 return existing
.m_fun
== candidate
.m_fun
&& existing
.m_cs
== candidate
.m_cs
;
3633 pod_hash_traits
<function_call_string
>::mark_deleted (value_type
&v
)
3635 v
.m_fun
= reinterpret_cast<function
*> (1);
3639 pod_hash_traits
<function_call_string
>::mark_empty (value_type
&v
)
3645 pod_hash_traits
<function_call_string
>::is_deleted (value_type v
)
3647 return v
.m_fun
== reinterpret_cast<function
*> (1);
3651 pod_hash_traits
<function_call_string
>::is_empty (value_type v
)
3653 return v
.m_fun
== NULL
;
3658 /* Top-level cluster for generating .dot output for exploded graphs,
3659 handling the functionless nodes, and grouping the remaining nodes by
3662 class root_cluster
: public exploded_cluster
3667 for (map_t::iterator iter
= m_map
.begin ();
3668 iter
!= m_map
.end ();
3670 delete (*iter
).second
;
3673 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const FINAL OVERRIDE
3676 exploded_node
*enode
;
3677 FOR_EACH_VEC_ELT (m_functionless_enodes
, i
, enode
)
3678 enode
->dump_dot (gv
, args
);
3680 for (map_t::iterator iter
= m_map
.begin ();
3681 iter
!= m_map
.end ();
3683 (*iter
).second
->dump_dot (gv
, args
);
3686 void add_node (exploded_node
*en
) FINAL OVERRIDE
3688 function
*fun
= en
->get_function ();
3691 m_functionless_enodes
.safe_push (en
);
3695 const call_string
&cs
= en
->get_point ().get_call_string ();
3696 function_call_string
key (fun
, cs
);
3697 function_call_string_cluster
**slot
= m_map
.get (key
);
3699 (*slot
)->add_node (en
);
3702 function_call_string_cluster
*child
3703 = new function_call_string_cluster (fun
, cs
);
3704 m_map
.put (key
, child
);
3705 child
->add_node (en
);
3710 /* This can't be an ordered_hash_map, as we can't store vec<call_string>,
3711 since it's not a POD; vec<>::quick_push has:
3713 and the slot isn't initialized, so the assignment op dies when cleaning up
3714 un-inited *slot (within the truncate call). */
3715 typedef hash_map
<function_call_string
, function_call_string_cluster
*> map_t
;
3718 /* This should just be the origin exploded_node. */
3719 auto_vec
<exploded_node
*> m_functionless_enodes
;
3722 /* Subclass of range_label for use within
3723 exploded_graph::dump_exploded_nodes for implementing
3724 -fdump-analyzer-exploded-nodes: a label for a specific
3727 class enode_label
: public range_label
3730 enode_label (const extrinsic_state
&ext_state
,
3731 exploded_node
*enode
)
3732 : m_ext_state (ext_state
), m_enode (enode
) {}
3734 label_text
get_text (unsigned) const FINAL OVERRIDE
3737 pp_format_decoder (&pp
) = default_tree_printer
;
3738 m_enode
->get_state ().dump_to_pp (m_ext_state
, true, false, &pp
);
3739 return make_label_text (false, "EN: %i: %s",
3740 m_enode
->m_index
, pp_formatted_text (&pp
));
3744 const extrinsic_state
&m_ext_state
;
3745 exploded_node
*m_enode
;
3748 /* Postprocessing support for dumping the exploded nodes.
3749 Handle -fdump-analyzer-exploded-nodes,
3750 -fdump-analyzer-exploded-nodes-2, and the
3751 "__analyzer_dump_exploded_nodes" builtin. */
3754 exploded_graph::dump_exploded_nodes () const
3757 /* Locate calls to __analyzer_dump_exploded_nodes. */
3758 // Print how many egs there are for them?
3759 /* Better: log them as we go, and record the exploded nodes
3762 /* Show every enode. */
3764 /* Gather them by stmt, so that we can more clearly see the
3765 "hotspots" requiring numerous exploded nodes. */
3767 /* Alternatively, simply throw them all into one big rich_location
3768 and see if the label-printing will sort it out...
3769 This requires them all to be in the same source file. */
3771 if (flag_dump_analyzer_exploded_nodes
)
3773 auto_timevar
tv (TV_ANALYZER_DUMP
);
3774 gcc_rich_location
richloc (UNKNOWN_LOCATION
);
3776 exploded_node
*enode
;
3777 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
3779 if (const gimple
*stmt
= enode
->get_stmt ())
3781 if (get_pure_location (richloc
.get_loc ()) == UNKNOWN_LOCATION
)
3782 richloc
.set_range (0, stmt
->location
, SHOW_RANGE_WITH_CARET
);
3784 richloc
.add_range (stmt
->location
,
3785 SHOW_RANGE_WITHOUT_CARET
,
3786 new enode_label (m_ext_state
, enode
));
3789 warning_at (&richloc
, 0, "%i exploded nodes", m_nodes
.length ());
3791 /* Repeat the warning without all the labels, so that message is visible
3792 (the other one may well have scrolled past the terminal limit). */
3793 warning_at (richloc
.get_loc (), 0,
3794 "%i exploded nodes", m_nodes
.length ());
3796 if (m_worklist
.length () > 0)
3797 warning_at (richloc
.get_loc (), 0,
3798 "worklist still contains %i nodes", m_worklist
.length ());
3801 /* Dump the egraph in textual form to a dump file. */
3802 if (flag_dump_analyzer_exploded_nodes_2
)
3804 auto_timevar
tv (TV_ANALYZER_DUMP
);
3806 = concat (dump_base_name
, ".eg.txt", NULL
);
3807 FILE *outf
= fopen (filename
, "w");
3809 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
3812 fprintf (outf
, "exploded graph for %s\n", dump_base_name
);
3813 fprintf (outf
, " nodes: %i\n", m_nodes
.length ());
3814 fprintf (outf
, " edges: %i\n", m_edges
.length ());
3817 exploded_node
*enode
;
3818 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
3820 fprintf (outf
, "\nEN %i:\n", enode
->m_index
);
3821 enode
->dump_succs_and_preds (outf
);
3823 enode
->get_point ().print (&pp
, format (true));
3824 fprintf (outf
, "%s\n", pp_formatted_text (&pp
));
3825 enode
->get_state ().dump_to_file (m_ext_state
, false, true, outf
);
3831 /* Dump the egraph in textual form to multiple dump files, one per enode. */
3832 if (flag_dump_analyzer_exploded_nodes_3
)
3834 auto_timevar
tv (TV_ANALYZER_DUMP
);
3837 exploded_node
*enode
;
3838 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
3841 = xasprintf ("%s.en-%i.txt", dump_base_name
, i
);
3842 FILE *outf
= fopen (filename
, "w");
3844 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
3847 fprintf (outf
, "EN %i:\n", enode
->m_index
);
3848 enode
->dump_succs_and_preds (outf
);
3850 enode
->get_point ().print (&pp
, format (true));
3851 fprintf (outf
, "%s\n", pp_formatted_text (&pp
));
3852 enode
->get_state ().dump_to_file (m_ext_state
, false, true, outf
);
3858 /* Emit a warning at any call to "__analyzer_dump_exploded_nodes",
3859 giving the number of processed exploded nodes for "before-stmt",
3860 and the IDs of processed, merger, and worklist enodes.
3862 We highlight the count of *processed* enodes since this is of most
3863 interest in DejaGnu tests for ensuring that state merger has
3866 We don't show the count of merger and worklist enodes, as this is
3867 more of an implementation detail of the merging/worklist that we
3868 don't want to bake into our expected DejaGnu messages. */
3871 exploded_node
*enode
;
3872 hash_set
<const gimple
*> seen
;
3873 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
3875 if (enode
->get_point ().get_kind () != PK_BEFORE_STMT
)
3878 if (const gimple
*stmt
= enode
->get_stmt ())
3879 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
3880 if (is_special_named_call_p (call
, "__analyzer_dump_exploded_nodes",
3883 if (seen
.contains (stmt
))
3886 auto_vec
<exploded_node
*> processed_enodes
;
3887 auto_vec
<exploded_node
*> merger_enodes
;
3888 auto_vec
<exploded_node
*> worklist_enodes
;
3889 /* This is O(N^2). */
3891 exploded_node
*other_enode
;
3892 FOR_EACH_VEC_ELT (m_nodes
, j
, other_enode
)
3894 if (other_enode
->get_point ().get_kind () != PK_BEFORE_STMT
)
3896 if (other_enode
->get_stmt () == stmt
)
3897 switch (other_enode
->get_status ())
3901 case exploded_node::STATUS_WORKLIST
:
3902 worklist_enodes
.safe_push (other_enode
);
3904 case exploded_node::STATUS_PROCESSED
:
3905 processed_enodes
.safe_push (other_enode
);
3907 case exploded_node::STATUS_MERGER
:
3908 merger_enodes
.safe_push (other_enode
);
3914 pp_character (&pp
, '[');
3915 print_enode_indices (&pp
, processed_enodes
);
3916 if (merger_enodes
.length () > 0)
3918 pp_string (&pp
, "] merger(s): [");
3919 print_enode_indices (&pp
, merger_enodes
);
3921 if (worklist_enodes
.length () > 0)
3923 pp_string (&pp
, "] worklist: [");
3924 print_enode_indices (&pp
, worklist_enodes
);
3926 pp_character (&pp
, ']');
3928 warning_n (stmt
->location
, 0, processed_enodes
.length (),
3929 "%i processed enode: %s",
3930 "%i processed enodes: %s",
3931 processed_enodes
.length (), pp_formatted_text (&pp
));
3934 /* If the argument is non-zero, then print all of the states
3935 of the various enodes. */
3936 tree t_arg
= fold (gimple_call_arg (call
, 0));
3937 if (TREE_CODE (t_arg
) != INTEGER_CST
)
3939 error_at (call
->location
,
3940 "integer constant required for arg 1");
3943 int i_arg
= TREE_INT_CST_LOW (t_arg
);
3946 exploded_node
*other_enode
;
3947 FOR_EACH_VEC_ELT (processed_enodes
, j
, other_enode
)
3949 fprintf (stderr
, "%i of %i: EN %i:\n",
3950 j
+ 1, processed_enodes
.length (),
3951 other_enode
->m_index
);
3952 other_enode
->dump_succs_and_preds (stderr
);
3954 other_enode
->get_state ().dump (m_ext_state
, false);
3961 DEBUG_FUNCTION exploded_node
*
3962 exploded_graph::get_node_by_index (int idx
) const
3964 exploded_node
*enode
= m_nodes
[idx
];
3965 gcc_assert (enode
->m_index
== idx
);
3969 /* Ensure that there is an exploded_node for a top-level call to FNDECL. */
3972 exploded_graph::on_escaped_function (tree fndecl
)
3974 logger
* const logger
= get_logger ();
3975 LOG_FUNC_1 (logger
, "%qE", fndecl
);
3977 cgraph_node
*cgnode
= cgraph_node::get (fndecl
);
3981 function
*fun
= cgnode
->get_fun ();
3985 exploded_node
*enode
= add_function_entry (fun
);
3989 logger
->log ("created EN %i for %qE entrypoint",
3990 enode
->m_index
, fun
->decl
);
3992 logger
->log ("did not create enode for %qE entrypoint", fun
->decl
);
3996 /* A collection of classes for visualizing the callgraph in .dot form
3997 (as represented in the supergraph). */
3999 /* Forward decls. */
4000 class viz_callgraph_node
;
4001 class viz_callgraph_edge
;
4002 class viz_callgraph
;
4003 class viz_callgraph_cluster
;
4005 /* Traits for using "digraph.h" to visualize the callgraph. */
4007 struct viz_callgraph_traits
4009 typedef viz_callgraph_node node_t
;
4010 typedef viz_callgraph_edge edge_t
;
4011 typedef viz_callgraph graph_t
;
4014 dump_args_t (const exploded_graph
*eg
) : m_eg (eg
) {}
4015 const exploded_graph
*m_eg
;
4017 typedef viz_callgraph_cluster cluster_t
;
4020 /* Subclass of dnode representing a function within the callgraph. */
4022 class viz_callgraph_node
: public dnode
<viz_callgraph_traits
>
4024 friend class viz_callgraph
;
4027 viz_callgraph_node (function
*fun
, int index
)
4028 : m_fun (fun
), m_index (index
), m_num_supernodes (0), m_num_superedges (0)
4033 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const FINAL OVERRIDE
4035 pretty_printer
*pp
= gv
->get_pp ();
4038 pp_printf (pp
, " [shape=none,margin=0,style=filled,fillcolor=%s,label=<",
4040 pp_string (pp
, "<TABLE BORDER=\"0\">");
4041 pp_write_text_to_stream (pp
);
4044 pp_printf (pp
, "VCG: %i: %s", m_index
, function_name (m_fun
));
4049 pp_printf (pp
, "supernodes: %i\n", m_num_supernodes
);
4054 pp_printf (pp
, "superedges: %i\n", m_num_superedges
);
4061 exploded_node
*enode
;
4062 unsigned num_enodes
= 0;
4063 FOR_EACH_VEC_ELT (args
.m_eg
->m_nodes
, i
, enode
)
4065 if (enode
->get_point ().get_function () == m_fun
)
4069 pp_printf (pp
, "enodes: %i\n", num_enodes
);
4073 // TODO: also show the per-callstring breakdown
4074 const exploded_graph::call_string_data_map_t
*per_cs_data
4075 = args
.m_eg
->get_per_call_string_data ();
4076 for (exploded_graph::call_string_data_map_t::iterator iter
4077 = per_cs_data
->begin ();
4078 iter
!= per_cs_data
->end ();
4081 const call_string
*cs
= (*iter
).first
;
4082 //per_call_string_data *data = (*iter).second;
4084 FOR_EACH_VEC_ELT (args
.m_eg
->m_nodes
, i
, enode
)
4086 if (enode
->get_point ().get_function () == m_fun
4087 && enode
->get_point ().get_call_string () == *cs
)
4094 pp_printf (pp
, ": %i\n", num_enodes
);
4095 pp_write_text_as_html_like_dot_to_stream (pp
);
4100 /* Show any summaries. */
4101 per_function_data
*data
= args
.m_eg
->get_per_function_data (m_fun
);
4106 pp_printf (pp
, "summaries: %i\n", data
->m_summaries
.length ());
4107 pp_write_text_as_html_like_dot_to_stream (pp
);
4112 pp_string (pp
, "</TABLE>>];\n\n");
4116 void dump_dot_id (pretty_printer
*pp
) const
4118 pp_printf (pp
, "vcg_%i", m_index
);
4124 int m_num_supernodes
;
4125 int m_num_superedges
;
4128 /* Subclass of dedge representing a callgraph edge. */
4130 class viz_callgraph_edge
: public dedge
<viz_callgraph_traits
>
4133 viz_callgraph_edge (viz_callgraph_node
*src
, viz_callgraph_node
*dest
)
4134 : dedge
<viz_callgraph_traits
> (src
, dest
)
4137 void dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
4140 pretty_printer
*pp
= gv
->get_pp ();
4142 const char *style
= "\"solid,bold\"";
4143 const char *color
= "black";
4145 const char *constraint
= "true";
4147 m_src
->dump_dot_id (pp
);
4148 pp_string (pp
, " -> ");
4149 m_dest
->dump_dot_id (pp
);
4151 (" [style=%s, color=%s, weight=%d, constraint=%s,"
4153 style
, color
, weight
, constraint
);
4154 pp_printf (pp
, "\"];\n");
4158 /* Subclass of digraph representing the callgraph. */
4160 class viz_callgraph
: public digraph
<viz_callgraph_traits
>
4163 viz_callgraph (const supergraph
&sg
);
4165 viz_callgraph_node
*get_vcg_node_for_function (function
*fun
)
4167 return *m_map
.get (fun
);
4170 viz_callgraph_node
*get_vcg_node_for_snode (supernode
*snode
)
4172 return get_vcg_node_for_function (snode
->m_fun
);
4176 hash_map
<function
*, viz_callgraph_node
*> m_map
;
4179 /* Placeholder subclass of cluster. */
4181 class viz_callgraph_cluster
: public cluster
<viz_callgraph_traits
>
4185 /* viz_callgraph's ctor. */
4187 viz_callgraph::viz_callgraph (const supergraph
&sg
)
4190 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4192 function
*fun
= node
->get_fun ();
4193 viz_callgraph_node
*vcg_node
4194 = new viz_callgraph_node (fun
, m_nodes
.length ());
4195 m_map
.put (fun
, vcg_node
);
4196 add_node (vcg_node
);
4201 FOR_EACH_VEC_ELT (sg
.m_edges
, i
, sedge
)
4203 viz_callgraph_node
*vcg_src
= get_vcg_node_for_snode (sedge
->m_src
);
4205 get_vcg_node_for_function (vcg_src
->m_fun
)->m_num_superedges
++;
4206 if (sedge
->dyn_cast_call_superedge ())
4208 viz_callgraph_node
*vcg_dest
= get_vcg_node_for_snode (sedge
->m_dest
);
4209 viz_callgraph_edge
*vcg_edge
4210 = new viz_callgraph_edge (vcg_src
, vcg_dest
);
4211 add_edge (vcg_edge
);
4216 FOR_EACH_VEC_ELT (sg
.m_nodes
, i
, snode
)
4219 get_vcg_node_for_function (snode
->m_fun
)->m_num_supernodes
++;
4223 /* Dump the callgraph to FILENAME. */
4226 dump_callgraph (const supergraph
&sg
, const char *filename
,
4227 const exploded_graph
*eg
)
4229 FILE *outf
= fopen (filename
, "w");
4234 viz_callgraph
vcg (sg
);
4235 vcg
.dump_dot (filename
, NULL
, viz_callgraph_traits::dump_args_t (eg
));
4240 /* Dump the callgraph to "<srcfile>.callgraph.dot". */
4243 dump_callgraph (const supergraph
&sg
, const exploded_graph
*eg
)
4245 auto_timevar
tv (TV_ANALYZER_DUMP
);
4246 char *filename
= concat (dump_base_name
, ".callgraph.dot", NULL
);
4247 dump_callgraph (sg
, filename
, eg
);
4251 /* Subclass of dot_annotator for implementing
4252 DUMP_BASE_NAME.supergraph-eg.dot, a post-analysis dump of the supergraph.
4254 Annotate the supergraph nodes by printing the exploded nodes in concise
4255 form within them, next to their pertinent statements where appropriate,
4256 colorizing the exploded nodes based on sm-state.
4257 Also show saved diagnostics within the exploded nodes, giving information
4258 on whether they were feasible, and, if infeasible, where the problem
4261 class exploded_graph_annotator
: public dot_annotator
4264 exploded_graph_annotator (const exploded_graph
&eg
)
4267 /* Avoid O(N^2) by prepopulating m_enodes_per_snodes. */
4270 FOR_EACH_VEC_ELT (eg
.get_supergraph ().m_nodes
, i
, snode
)
4271 m_enodes_per_snodes
.safe_push (new auto_vec
<exploded_node
*> ());
4272 exploded_node
*enode
;
4273 FOR_EACH_VEC_ELT (m_eg
.m_nodes
, i
, enode
)
4274 if (enode
->get_supernode ())
4275 m_enodes_per_snodes
[enode
->get_supernode ()->m_index
]->safe_push (enode
);
4278 /* Show exploded nodes for BEFORE_SUPERNODE points before N. */
4279 bool add_node_annotations (graphviz_out
*gv
, const supernode
&n
,
4281 const FINAL OVERRIDE
4286 pretty_printer
*pp
= gv
->get_pp ();
4289 pp_string (pp
, "BEFORE");
4290 pp_printf (pp
, " (scc: %i)", m_eg
.get_scc_id (n
));
4294 exploded_node
*enode
;
4295 bool had_enode
= false;
4296 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[n
.m_index
], i
, enode
)
4298 gcc_assert (enode
->get_supernode () == &n
);
4299 const program_point
&point
= enode
->get_point ();
4300 if (point
.get_kind () != PK_BEFORE_SUPERNODE
)
4302 print_enode (gv
, enode
);
4306 pp_string (pp
, "<TD BGCOLOR=\"red\">UNREACHED</TD>");
4312 /* Show exploded nodes for STMT. */
4313 void add_stmt_annotations (graphviz_out
*gv
, const gimple
*stmt
,
4315 const FINAL OVERRIDE
4319 pretty_printer
*pp
= gv
->get_pp ();
4321 const supernode
*snode
4322 = m_eg
.get_supergraph ().get_supernode_for_stmt (stmt
);
4324 exploded_node
*enode
;
4325 bool had_td
= false;
4326 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[snode
->m_index
], i
, enode
)
4328 const program_point
&point
= enode
->get_point ();
4329 if (point
.get_kind () != PK_BEFORE_STMT
)
4331 if (point
.get_stmt () != stmt
)
4333 print_enode (gv
, enode
);
4344 /* Show exploded nodes for AFTER_SUPERNODE points after N. */
4345 bool add_after_node_annotations (graphviz_out
*gv
, const supernode
&n
)
4346 const FINAL OVERRIDE
4349 pretty_printer
*pp
= gv
->get_pp ();
4352 pp_string (pp
, "AFTER");
4356 exploded_node
*enode
;
4357 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[n
.m_index
], i
, enode
)
4359 gcc_assert (enode
->get_supernode () == &n
);
4360 const program_point
&point
= enode
->get_point ();
4361 if (point
.get_kind () != PK_AFTER_SUPERNODE
)
4363 print_enode (gv
, enode
);
4371 /* Concisely print a TD element for ENODE, showing the index, status,
4372 and any saved_diagnostics at the enode. Colorize it to show sm-state.
4374 Ideally we'd dump ENODE's state here, hidden behind some kind of
4375 interactive disclosure method like a tooltip, so that the states
4376 can be explored without overwhelming the graph.
4377 However, I wasn't able to get graphviz/xdot to show tooltips on
4378 individual elements within a HTML-like label. */
4379 void print_enode (graphviz_out
*gv
, const exploded_node
*enode
) const
4381 pretty_printer
*pp
= gv
->get_pp ();
4382 pp_printf (pp
, "<TD BGCOLOR=\"%s\">",
4383 enode
->get_dot_fillcolor ());
4384 pp_printf (pp
, "<TABLE BORDER=\"0\">");
4386 pp_printf (pp
, "EN: %i", enode
->m_index
);
4387 switch (enode
->get_status ())
4391 case exploded_node::STATUS_WORKLIST
:
4392 pp_string (pp
, "(W)");
4394 case exploded_node::STATUS_PROCESSED
:
4396 case exploded_node::STATUS_MERGER
:
4397 pp_string (pp
, "(M)");
4399 case exploded_node::STATUS_BULK_MERGED
:
4400 pp_string (pp
, "(BM)");
4404 /* Dump any saved_diagnostics at this enode. */
4406 const diagnostic_manager
&dm
= m_eg
.get_diagnostic_manager ();
4407 for (unsigned i
= 0; i
< dm
.get_num_diagnostics (); i
++)
4409 const saved_diagnostic
*sd
= dm
.get_saved_diagnostic (i
);
4410 if (sd
->m_enode
== enode
)
4411 print_saved_diagnostic (gv
, sd
);
4414 pp_printf (pp
, "</TABLE>");
4415 pp_printf (pp
, "</TD>");
4418 /* Print a TABLE element for SD, showing the kind, the length of the
4419 exploded_path, whether the path was feasible, and if infeasible,
4420 what the problem was. */
4421 void print_saved_diagnostic (graphviz_out
*gv
,
4422 const saved_diagnostic
*sd
) const
4424 pretty_printer
*pp
= gv
->get_pp ();
4426 pp_printf (pp
, "<TABLE BORDER=\"0\">");
4428 pp_string (pp
, "<TD BGCOLOR=\"green\">");
4429 pp_printf (pp
, "DIAGNOSTIC: %s", sd
->m_d
->get_kind ());
4432 pp_printf (pp
, "epath length: %i", sd
->get_epath_length ());
4434 switch (sd
->get_status ())
4437 case saved_diagnostic::STATUS_NEW
:
4440 case saved_diagnostic::STATUS_INFEASIBLE_PATH
:
4443 pp_printf (pp
, "INFEASIBLE");
4445 const feasibility_problem
*p
= sd
->get_feasibility_problem ();
4448 pp_printf (pp
, "at eedge %i: EN:%i -> EN:%i",
4450 p
->m_eedge
.m_src
->m_index
,
4451 p
->m_eedge
.m_dest
->m_index
);
4452 pp_write_text_as_html_like_dot_to_stream (pp
);
4455 p
->m_eedge
.m_sedge
->dump (pp
);
4456 pp_write_text_as_html_like_dot_to_stream (pp
);
4459 pp_gimple_stmt_1 (pp
, p
->m_last_stmt
, 0, (dump_flags_t
)0);
4460 pp_write_text_as_html_like_dot_to_stream (pp
);
4462 /* Ideally we'd print p->m_model here; see the notes above about
4466 case saved_diagnostic::STATUS_FEASIBLE_PATH
:
4468 pp_printf (pp
, "FEASIBLE");
4472 pp_printf (pp
, "</TABLE>");
4476 const exploded_graph
&m_eg
;
4477 auto_delete_vec
<auto_vec
<exploded_node
*> > m_enodes_per_snodes
;
4480 /* Implement -fdump-analyzer-json. */
4483 dump_analyzer_json (const supergraph
&sg
,
4484 const exploded_graph
&eg
)
4486 auto_timevar
tv (TV_ANALYZER_DUMP
);
4487 char *filename
= concat (dump_base_name
, ".analyzer.json.gz", NULL
);
4488 gzFile output
= gzopen (filename
, "w");
4491 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
4496 json::object
*toplev_obj
= new json::object ();
4497 toplev_obj
->set ("sgraph", sg
.to_json ());
4498 toplev_obj
->set ("egraph", eg
.to_json ());
4501 toplev_obj
->print (&pp
);
4502 pp_formatted_text (&pp
);
4506 if (gzputs (output
, pp_formatted_text (&pp
)) == EOF
4507 || gzclose (output
))
4508 error_at (UNKNOWN_LOCATION
, "error writing %qs", filename
);
4513 /* Run the analysis "engine". */
4516 impl_run_checkers (logger
*logger
)
4520 /* If using LTO, ensure that the cgraph nodes have function bodies. */
4522 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
4523 node
->get_untransformed_body ();
4527 /* Create the supergraph. */
4528 supergraph
sg (logger
);
4530 state_purge_map
*purge_map
= NULL
;
4532 if (flag_analyzer_state_purge
)
4533 purge_map
= new state_purge_map (sg
, logger
);
4535 if (flag_dump_analyzer_supergraph
)
4537 /* Dump supergraph pre-analysis. */
4538 auto_timevar
tv (TV_ANALYZER_DUMP
);
4539 char *filename
= concat (dump_base_name
, ".supergraph.dot", NULL
);
4540 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, NULL
);
4541 sg
.dump_dot (filename
, args
);
4545 if (flag_dump_analyzer_state_purge
)
4547 auto_timevar
tv (TV_ANALYZER_DUMP
);
4548 state_purge_annotator
a (purge_map
);
4549 char *filename
= concat (dump_base_name
, ".state-purge.dot", NULL
);
4550 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, &a
);
4551 sg
.dump_dot (filename
, args
);
4555 auto_delete_vec
<state_machine
> checkers
;
4556 make_checkers (checkers
, logger
);
4562 FOR_EACH_VEC_ELT (checkers
, i
, sm
)
4563 logger
->log ("checkers[%i]: %s", i
, sm
->get_name ());
4566 /* Extrinsic state shared by nodes in the graph. */
4567 const extrinsic_state
ext_state (checkers
, &eng
, logger
);
4569 const analysis_plan
plan (sg
, logger
);
4571 /* The exploded graph. */
4572 exploded_graph
eg (sg
, logger
, ext_state
, purge_map
, plan
,
4573 analyzer_verbosity
);
4575 /* Add entrypoints to the graph for externally-callable functions. */
4576 eg
.build_initial_worklist ();
4578 /* Now process the worklist, exploring the <point, state> graph. */
4579 eg
.process_worklist ();
4581 if (flag_dump_analyzer_exploded_graph
)
4583 auto_timevar
tv (TV_ANALYZER_DUMP
);
4585 = concat (dump_base_name
, ".eg.dot", NULL
);
4586 exploded_graph::dump_args_t
args (eg
);
4588 eg
.dump_dot (filename
, &c
, args
);
4592 /* Now emit any saved diagnostics. */
4593 eg
.get_diagnostic_manager ().emit_saved_diagnostics (eg
);
4595 eg
.dump_exploded_nodes ();
4599 if (flag_dump_analyzer_callgraph
)
4600 dump_callgraph (sg
, &eg
);
4602 if (flag_dump_analyzer_supergraph
)
4604 /* Dump post-analysis form of supergraph. */
4605 auto_timevar
tv (TV_ANALYZER_DUMP
);
4606 char *filename
= concat (dump_base_name
, ".supergraph-eg.dot", NULL
);
4607 exploded_graph_annotator
a (eg
);
4608 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, &a
);
4609 sg
.dump_dot (filename
, args
);
4613 if (flag_dump_analyzer_json
)
4614 dump_analyzer_json (sg
, eg
);
4619 /* External entrypoint to the analysis "engine".
4620 Set up any dumps, then call impl_run_checkers. */
4625 /* Save input_location. */
4626 location_t saved_input_location
= input_location
;
4628 /* Handle -fdump-analyzer and -fdump-analyzer-stderr. */
4629 FILE *dump_fout
= NULL
;
4630 /* Track if we're responsible for closing dump_fout. */
4631 bool owns_dump_fout
= false;
4632 if (flag_dump_analyzer_stderr
)
4634 else if (flag_dump_analyzer
)
4636 char *dump_filename
= concat (dump_base_name
, ".analyzer.txt", NULL
);
4637 dump_fout
= fopen (dump_filename
, "w");
4638 free (dump_filename
);
4640 owns_dump_fout
= true;
4644 log_user
the_logger (NULL
);
4646 the_logger
.set_logger (new logger (dump_fout
, 0, 0,
4647 *global_dc
->printer
));
4648 LOG_SCOPE (the_logger
.get_logger ());
4650 impl_run_checkers (the_logger
.get_logger ());
4652 /* end of lifetime of the_logger (so that dump file is closed after the
4653 various dtors run). */
4659 /* Restore input_location. Subsequent passes may assume that input_location
4660 is some arbitrary value *not* in the block tree, which might be violated
4661 if we didn't restore it. */
4662 input_location
= saved_input_location
;
4667 #endif /* #if ENABLE_ANALYZER */