1 /* The analysis "engine".
2 Copyright (C) 2019-2024 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/>. */
22 #define INCLUDE_MEMORY
24 #include "coretypes.h"
25 #include "make-unique.h"
27 #include "fold-const.h"
28 #include "gcc-rich-location.h"
29 #include "diagnostic-core.h"
30 #include "diagnostic-event-id.h"
31 #include "diagnostic-path.h"
33 #include "pretty-print.h"
36 #include "ordered-hash-map.h"
37 #include "analyzer/analyzer.h"
38 #include "analyzer/analyzer-logging.h"
39 #include "analyzer/call-string.h"
40 #include "analyzer/program-point.h"
41 #include "analyzer/store.h"
42 #include "analyzer/region-model.h"
43 #include "analyzer/constraint-manager.h"
44 #include "analyzer/sm.h"
45 #include "analyzer/pending-diagnostic.h"
46 #include "analyzer/diagnostic-manager.h"
48 #include "basic-block.h"
50 #include "gimple-iterator.h"
51 #include "gimple-pretty-print.h"
54 #include "analyzer/supergraph.h"
55 #include "analyzer/program-state.h"
56 #include "analyzer/exploded-graph.h"
57 #include "analyzer/analysis-plan.h"
58 #include "analyzer/checker-path.h"
59 #include "analyzer/state-purge.h"
60 #include "analyzer/bar-chart.h"
61 #include "analyzer/call-info.h"
66 #include "stringpool.h"
69 #include "analyzer/known-function-manager.h"
70 #include "analyzer/call-summary.h"
72 /* For an overview, see gcc/doc/analyzer.texi. */
78 /* class impl_region_model_context : public region_model_context. */
80 impl_region_model_context::
81 impl_region_model_context (exploded_graph
&eg
,
82 exploded_node
*enode_for_diag
,
83 const program_state
*old_state
,
84 program_state
*new_state
,
85 uncertainty_t
*uncertainty
,
86 path_context
*path_ctxt
,
88 stmt_finder
*stmt_finder
,
89 bool *out_could_have_done_work
)
90 : m_eg (&eg
), m_logger (eg
.get_logger ()),
91 m_enode_for_diag (enode_for_diag
),
92 m_old_state (old_state
),
93 m_new_state (new_state
),
95 m_stmt_finder (stmt_finder
),
96 m_ext_state (eg
.get_ext_state ()),
97 m_uncertainty (uncertainty
),
98 m_path_ctxt (path_ctxt
),
99 m_out_could_have_done_work (out_could_have_done_work
)
103 impl_region_model_context::
104 impl_region_model_context (program_state
*state
,
105 const extrinsic_state
&ext_state
,
106 uncertainty_t
*uncertainty
,
108 : m_eg (NULL
), m_logger (logger
), m_enode_for_diag (NULL
),
112 m_stmt_finder (NULL
),
113 m_ext_state (ext_state
),
114 m_uncertainty (uncertainty
),
116 m_out_could_have_done_work (nullptr)
121 impl_region_model_context::warn (std::unique_ptr
<pending_diagnostic
> d
,
122 const stmt_finder
*custom_finder
)
124 LOG_FUNC (get_logger ());
125 auto curr_stmt_finder
= custom_finder
? custom_finder
: m_stmt_finder
;
126 if (m_stmt
== NULL
&& curr_stmt_finder
== NULL
)
129 get_logger ()->log ("rejecting diagnostic: no stmt");
134 bool terminate_path
= d
->terminate_path_p ();
135 pending_location
ploc (m_enode_for_diag
,
136 m_enode_for_diag
->get_supernode (),
139 if (m_eg
->get_diagnostic_manager ().add_diagnostic (ploc
,
144 && flag_analyzer_suppress_followups
)
145 m_path_ctxt
->terminate_path ();
153 impl_region_model_context::add_note (std::unique_ptr
<pending_note
> pn
)
155 LOG_FUNC (get_logger ());
157 m_eg
->get_diagnostic_manager ().add_note (std::move (pn
));
161 impl_region_model_context::add_event (std::unique_ptr
<checker_event
> event
)
163 LOG_FUNC (get_logger ());
165 m_eg
->get_diagnostic_manager ().add_event (std::move (event
));
169 impl_region_model_context::on_svalue_leak (const svalue
*sval
)
172 for (sm_state_map
*smap
: m_new_state
->m_checker_states
)
173 smap
->on_svalue_leak (sval
, this);
177 impl_region_model_context::
178 on_liveness_change (const svalue_set
&live_svalues
,
179 const region_model
*model
)
181 for (sm_state_map
*smap
: m_new_state
->m_checker_states
)
182 smap
->on_liveness_change (live_svalues
, model
, this);
186 impl_region_model_context::on_unknown_change (const svalue
*sval
,
189 if (!sval
->can_have_associated_state_p ())
191 for (sm_state_map
*smap
: m_new_state
->m_checker_states
)
192 smap
->on_unknown_change (sval
, is_mutable
, m_ext_state
);
196 impl_region_model_context::on_escaped_function (tree fndecl
)
198 m_eg
->on_escaped_function (fndecl
);
202 impl_region_model_context::get_uncertainty ()
204 return m_uncertainty
;
207 /* Purge state involving SVAL. The region_model has already been purged,
208 so we only need to purge other state in the program_state:
212 impl_region_model_context::purge_state_involving (const svalue
*sval
)
216 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, i
, smap
)
217 smap
->purge_state_involving (sval
, m_ext_state
);
221 impl_region_model_context::bifurcate (std::unique_ptr
<custom_edge_info
> info
)
224 m_path_ctxt
->bifurcate (std::move (info
));
228 impl_region_model_context::terminate_path ()
231 return m_path_ctxt
->terminate_path ();
234 /* struct setjmp_record. */
237 setjmp_record::cmp (const setjmp_record
&rec1
, const setjmp_record
&rec2
)
239 if (int cmp_enode
= rec1
.m_enode
->m_index
- rec2
.m_enode
->m_index
)
241 gcc_assert (&rec1
== &rec2
);
245 /* class setjmp_svalue : public svalue. */
247 /* Implementation of svalue::accept vfunc for setjmp_svalue. */
250 setjmp_svalue::accept (visitor
*v
) const
252 v
->visit_setjmp_svalue (this);
255 /* Implementation of svalue::dump_to_pp vfunc for setjmp_svalue. */
258 setjmp_svalue::dump_to_pp (pretty_printer
*pp
, bool simple
) const
261 pp_printf (pp
, "SETJMP(EN: %i)", get_enode_index ());
263 pp_printf (pp
, "setjmp_svalue(EN%i)", get_enode_index ());
266 /* Get the index of the stored exploded_node. */
269 setjmp_svalue::get_enode_index () const
271 return m_setjmp_record
.m_enode
->m_index
;
274 /* Concrete implementation of sm_context, wiring it up to the rest of this
277 class impl_sm_context
: public sm_context
280 impl_sm_context (exploded_graph
&eg
,
282 const state_machine
&sm
,
283 exploded_node
*enode_for_diag
,
284 const program_state
*old_state
,
285 program_state
*new_state
,
286 const sm_state_map
*old_smap
,
287 sm_state_map
*new_smap
,
288 path_context
*path_ctxt
,
289 const stmt_finder
*stmt_finder
= NULL
,
290 bool unknown_side_effects
= false)
291 : sm_context (sm_idx
, sm
),
292 m_logger (eg
.get_logger ()),
293 m_eg (eg
), m_enode_for_diag (enode_for_diag
),
294 m_old_state (old_state
), m_new_state (new_state
),
295 m_old_smap (old_smap
), m_new_smap (new_smap
),
296 m_path_ctxt (path_ctxt
),
297 m_stmt_finder (stmt_finder
),
298 m_unknown_side_effects (unknown_side_effects
)
302 logger
*get_logger () const { return m_logger
.get_logger (); }
304 tree
get_fndecl_for_call (const gcall
*call
) final override
306 impl_region_model_context old_ctxt
307 (m_eg
, m_enode_for_diag
, NULL
, NULL
, NULL
/*m_enode->get_state ()*/,
309 region_model
*model
= m_new_state
->m_region_model
;
310 return model
->get_fndecl_for_call (call
, &old_ctxt
);
313 state_machine::state_t
get_state (const gimple
*stmt ATTRIBUTE_UNUSED
,
314 tree var
) final override
316 logger
* const logger
= get_logger ();
318 /* Use NULL ctxt on this get_rvalue call to avoid triggering
319 uninitialized value warnings. */
320 const svalue
*var_old_sval
321 = m_old_state
->m_region_model
->get_rvalue (var
, NULL
);
323 state_machine::state_t current
324 = m_old_smap
->get_state (var_old_sval
, m_eg
.get_ext_state ());
327 state_machine::state_t
get_state (const gimple
*stmt ATTRIBUTE_UNUSED
,
328 const svalue
*sval
) final override
330 logger
* const logger
= get_logger ();
332 state_machine::state_t current
333 = m_old_smap
->get_state (sval
, m_eg
.get_ext_state ());
338 void set_next_state (const gimple
*,
340 state_machine::state_t to
,
341 tree origin
) final override
343 logger
* const logger
= get_logger ();
345 const svalue
*var_new_sval
346 = m_new_state
->m_region_model
->get_rvalue (var
, NULL
);
347 const svalue
*origin_new_sval
348 = m_new_state
->m_region_model
->get_rvalue (origin
, NULL
);
350 /* We use the new sval here to avoid issues with uninitialized values. */
351 state_machine::state_t current
352 = m_old_smap
->get_state (var_new_sval
, m_eg
.get_ext_state ());
354 logger
->log ("%s: state transition of %qE: %s -> %s",
357 current
->get_name (),
359 m_new_smap
->set_state (m_new_state
->m_region_model
, var_new_sval
,
360 to
, origin_new_sval
, m_eg
.get_ext_state ());
363 void set_next_state (const gimple
*stmt
,
365 state_machine::state_t to
,
366 tree origin
) final override
368 logger
* const logger
= get_logger ();
370 impl_region_model_context old_ctxt
371 (m_eg
, m_enode_for_diag
, NULL
, NULL
, NULL
/*m_enode->get_state ()*/,
374 const svalue
*origin_new_sval
375 = m_new_state
->m_region_model
->get_rvalue (origin
, NULL
);
377 state_machine::state_t current
378 = m_old_smap
->get_state (sval
, m_eg
.get_ext_state ());
381 logger
->start_log_line ();
382 logger
->log_partial ("%s: state transition of ",
384 sval
->dump_to_pp (logger
->get_printer (), true);
385 logger
->log_partial (": %s -> %s",
386 current
->get_name (),
388 logger
->end_log_line ();
390 m_new_smap
->set_state (m_new_state
->m_region_model
, sval
,
391 to
, origin_new_sval
, m_eg
.get_ext_state ());
394 void warn (const supernode
*snode
, const gimple
*stmt
,
396 std::unique_ptr
<pending_diagnostic
> d
) final override
398 LOG_FUNC (get_logger ());
400 const svalue
*var_old_sval
401 = m_old_state
->m_region_model
->get_rvalue (var
, NULL
);
402 state_machine::state_t current
404 ? m_old_smap
->get_state (var_old_sval
, m_eg
.get_ext_state ())
405 : m_old_smap
->get_global_state ());
406 bool terminate_path
= d
->terminate_path_p ();
407 pending_location
ploc (m_enode_for_diag
, snode
, stmt
, m_stmt_finder
);
408 m_eg
.get_diagnostic_manager ().add_diagnostic
410 var
, var_old_sval
, current
, std::move (d
));
413 && flag_analyzer_suppress_followups
)
414 m_path_ctxt
->terminate_path ();
417 void warn (const supernode
*snode
, const gimple
*stmt
,
419 std::unique_ptr
<pending_diagnostic
> d
) final override
421 LOG_FUNC (get_logger ());
423 state_machine::state_t current
425 ? m_old_smap
->get_state (sval
, m_eg
.get_ext_state ())
426 : m_old_smap
->get_global_state ());
427 bool terminate_path
= d
->terminate_path_p ();
428 pending_location
ploc (m_enode_for_diag
, snode
, stmt
, m_stmt_finder
);
429 m_eg
.get_diagnostic_manager ().add_diagnostic
431 NULL_TREE
, sval
, current
, std::move (d
));
434 && flag_analyzer_suppress_followups
)
435 m_path_ctxt
->terminate_path ();
438 /* Hook for picking more readable trees for SSA names of temporaries,
439 so that rather than e.g.
440 "double-free of '<unknown>'"
442 "double-free of 'inbuf.data'". */
444 tree
get_diagnostic_tree (tree expr
) final override
446 /* Only for SSA_NAMEs of temporaries; otherwise, return EXPR, as it's
447 likely to be the least surprising tree to report. */
448 if (TREE_CODE (expr
) != SSA_NAME
)
450 if (SSA_NAME_VAR (expr
) != NULL
)
453 gcc_assert (m_new_state
);
454 const svalue
*sval
= m_new_state
->m_region_model
->get_rvalue (expr
, NULL
);
455 /* Find trees for all regions storing the value. */
456 if (tree t
= m_new_state
->m_region_model
->get_representative_tree (sval
))
462 tree
get_diagnostic_tree (const svalue
*sval
) final override
464 return m_new_state
->m_region_model
->get_representative_tree (sval
);
467 state_machine::state_t
get_global_state () const final override
469 return m_old_state
->m_checker_states
[m_sm_idx
]->get_global_state ();
472 void set_global_state (state_machine::state_t state
) final override
474 m_new_state
->m_checker_states
[m_sm_idx
]->set_global_state (state
);
477 void clear_all_per_svalue_state () final override
479 m_new_state
->m_checker_states
[m_sm_idx
]->clear_all_per_svalue_state ();
482 void on_custom_transition (custom_transition
*transition
) final override
484 transition
->impl_transition (&m_eg
,
485 const_cast<exploded_node
*> (m_enode_for_diag
),
489 tree
is_zero_assignment (const gimple
*stmt
) final override
491 const gassign
*assign_stmt
= dyn_cast
<const gassign
*> (stmt
);
494 impl_region_model_context old_ctxt
495 (m_eg
, m_enode_for_diag
, m_old_state
, m_new_state
, NULL
, NULL
, stmt
);
496 if (const svalue
*sval
497 = m_new_state
->m_region_model
->get_gassign_result (assign_stmt
,
499 if (tree cst
= sval
->maybe_get_constant ())
501 return gimple_assign_lhs (assign_stmt
);
505 path_context
*get_path_context () const final override
510 bool unknown_side_effects_p () const final override
512 return m_unknown_side_effects
;
515 const program_state
*get_old_program_state () const final override
520 const program_state
*get_new_program_state () const final override
526 exploded_graph
&m_eg
;
527 exploded_node
*m_enode_for_diag
;
528 const program_state
*m_old_state
;
529 program_state
*m_new_state
;
530 const sm_state_map
*m_old_smap
;
531 sm_state_map
*m_new_smap
;
532 path_context
*m_path_ctxt
;
533 const stmt_finder
*m_stmt_finder
;
535 /* Are we handling an external function with unknown side effects? */
536 bool m_unknown_side_effects
;
540 impl_region_model_context::
541 get_state_map_by_name (const char *name
,
542 sm_state_map
**out_smap
,
543 const state_machine
**out_sm
,
544 unsigned *out_sm_idx
,
545 std::unique_ptr
<sm_context
> *out_sm_context
)
551 if (!m_ext_state
.get_sm_idx_by_name (name
, &sm_idx
))
554 const state_machine
*sm
= &m_ext_state
.get_sm (sm_idx
);
555 sm_state_map
*new_smap
= m_new_state
->m_checker_states
[sm_idx
];
557 *out_smap
= new_smap
;
560 *out_sm_idx
= sm_idx
;
563 const sm_state_map
*old_smap
= m_old_state
->m_checker_states
[sm_idx
];
565 = make_unique
<impl_sm_context
> (*m_eg
,
580 /* Subclass of stmt_finder for finding the best stmt to report the leak at,
581 given the emission path. */
583 class leak_stmt_finder
: public stmt_finder
586 leak_stmt_finder (const exploded_graph
&eg
, tree var
)
587 : m_eg (eg
), m_var (var
) {}
589 std::unique_ptr
<stmt_finder
> clone () const final override
591 return make_unique
<leak_stmt_finder
> (m_eg
, m_var
);
594 const gimple
*find_stmt (const exploded_path
&epath
)
597 logger
* const logger
= m_eg
.get_logger ();
600 if (m_var
&& TREE_CODE (m_var
) == SSA_NAME
)
602 /* Locate the final write to this SSA name in the path. */
603 const gimple
*def_stmt
= SSA_NAME_DEF_STMT (m_var
);
606 bool found
= epath
.find_stmt_backwards (def_stmt
, &idx_of_def_stmt
);
610 /* What was the next write to the underlying var
611 after the SSA name was set? (if any). */
613 for (unsigned idx
= idx_of_def_stmt
+ 1;
614 idx
< epath
.m_edges
.length ();
617 const exploded_edge
*eedge
= epath
.m_edges
[idx
];
619 logger
->log ("eedge[%i]: EN %i -> EN %i",
621 eedge
->m_src
->m_index
,
622 eedge
->m_dest
->m_index
);
623 const exploded_node
*dst_node
= eedge
->m_dest
;
624 const program_point
&dst_point
= dst_node
->get_point ();
625 const gimple
*stmt
= dst_point
.get_stmt ();
628 if (const gassign
*assign
= dyn_cast
<const gassign
*> (stmt
))
630 tree lhs
= gimple_assign_lhs (assign
);
631 if (TREE_CODE (lhs
) == SSA_NAME
632 && SSA_NAME_VAR (lhs
) == SSA_NAME_VAR (m_var
))
640 /* Look backwards for the first statement with a location. */
642 const exploded_edge
*eedge
;
643 FOR_EACH_VEC_ELT_REVERSE (epath
.m_edges
, i
, eedge
)
646 logger
->log ("eedge[%i]: EN %i -> EN %i",
648 eedge
->m_src
->m_index
,
649 eedge
->m_dest
->m_index
);
650 const exploded_node
*dst_node
= eedge
->m_dest
;
651 const program_point
&dst_point
= dst_node
->get_point ();
652 const gimple
*stmt
= dst_point
.get_stmt ();
654 if (get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
663 const exploded_graph
&m_eg
;
667 /* A measurement of how good EXPR is for presenting to the user, so
668 that e.g. we can say prefer printing
669 "leak of 'tmp.m_ptr'"
671 "leak of '<unknown>'". */
674 readability (const_tree expr
)
676 /* Arbitrarily-chosen "high readability" value. */
677 const int HIGH_READABILITY
= 65536;
680 switch (TREE_CODE (expr
))
684 /* Impose a slight readability penalty relative to that of
686 return readability (TREE_OPERAND (expr
, 0)) - 16;
690 if (tree var
= SSA_NAME_VAR (expr
))
692 if (DECL_ARTIFICIAL (var
))
694 /* If we have an SSA name for an artificial var,
695 only use it if it has a debug expr associated with
696 it that fixup_tree_for_diagnostic can use. */
697 if (VAR_P (var
) && DECL_HAS_DEBUG_EXPR_P (var
))
698 return readability (DECL_DEBUG_EXPR (var
)) - 1;
702 /* Slightly favor the underlying var over the SSA name to
703 avoid having them compare equal. */
704 return readability (var
) - 1;
707 /* Avoid printing '<unknown>' for SSA names for temporaries. */
714 if (DECL_NAME (expr
))
715 return HIGH_READABILITY
;
717 /* We don't want to print temporaries. For example, the C FE
718 prints them as e.g. "<Uxxxx>" where "xxxx" is the low 16 bits
719 of the tree pointer (see pp_c_tree_decl_identifier). */
723 /* Printing "<return-value>" isn't ideal, but is less awful than
724 trying to print a temporary. */
725 return HIGH_READABILITY
/ 2;
729 /* Impose a moderate readability penalty for casts. */
730 const int CAST_PENALTY
= 32;
731 return readability (TREE_OPERAND (expr
, 0)) - CAST_PENALTY
;
735 return HIGH_READABILITY
;
744 /* A qsort comparator for trees to sort them into most user-readable to
745 least user-readable. */
748 readability_comparator (const void *p1
, const void *p2
)
750 path_var pv1
= *(path_var
const *)p1
;
751 path_var pv2
= *(path_var
const *)p2
;
753 const int tree_r1
= readability (pv1
.m_tree
);
754 const int tree_r2
= readability (pv2
.m_tree
);
756 /* Favor items that are deeper on the stack and hence more recent;
757 this also favors locals over globals. */
758 const int COST_PER_FRAME
= 64;
759 const int depth_r1
= pv1
.m_stack_depth
* COST_PER_FRAME
;
760 const int depth_r2
= pv2
.m_stack_depth
* COST_PER_FRAME
;
762 /* Combine the scores from the tree and from the stack depth.
763 This e.g. lets us have a slightly penalized cast in the most
764 recent stack frame "beat" an uncast value in an older stack frame. */
765 const int sum_r1
= tree_r1
+ depth_r1
;
766 const int sum_r2
= tree_r2
+ depth_r2
;
767 if (int cmp
= sum_r2
- sum_r1
)
770 /* Otherwise, more readable trees win. */
771 if (int cmp
= tree_r2
- tree_r1
)
774 /* Otherwise, if they have the same readability, then impose an
775 arbitrary deterministic ordering on them. */
777 if (int cmp
= TREE_CODE (pv1
.m_tree
) - TREE_CODE (pv2
.m_tree
))
780 switch (TREE_CODE (pv1
.m_tree
))
785 if (int cmp
= (SSA_NAME_VERSION (pv1
.m_tree
)
786 - SSA_NAME_VERSION (pv2
.m_tree
)))
792 if (int cmp
= DECL_UID (pv1
.m_tree
) - DECL_UID (pv2
.m_tree
))
797 /* TODO: We ought to find ways of sorting such cases. */
801 /* Return true is SNODE is the EXIT node of a function, or is one
802 of the final snodes within its function.
804 Specifically, handle the final supernodes before the EXIT node,
805 for the case of clobbers that happen immediately before exiting.
806 We need a run of snodes leading to the return_p snode, where all edges are
807 intraprocedural, and every snode has just one successor.
809 We use this when suppressing leak reports at the end of "main". */
812 returning_from_function_p (const supernode
*snode
)
818 const supernode
*iter
= snode
;
821 if (iter
->return_p ())
823 if (iter
->m_succs
.length () != 1)
825 const superedge
*sedge
= iter
->m_succs
[0];
826 if (sedge
->get_kind () != SUPEREDGE_CFG_EDGE
)
828 iter
= sedge
->m_dest
;
830 /* Impose a limit to ensure we terminate for pathological cases.
832 We only care about the final 3 nodes, due to cases like:
834 (clobber causing leak)
846 /* Find the best tree for SVAL and call SM's on_leak vfunc with it.
847 If on_leak returns a pending_diagnostic, queue it up to be reported,
848 so that we potentially complain about a leak of SVAL in the given STATE. */
851 impl_region_model_context::on_state_leak (const state_machine
&sm
,
853 state_machine::state_t state
)
855 logger
* const logger
= get_logger ();
859 logger
->start_log_line ();
860 logger
->log_partial ("considering leak of ");
861 sval
->dump_to_pp (logger
->get_printer (), true);
862 logger
->end_log_line ();
868 /* m_old_state also needs to be non-NULL so that the sm_ctxt can look
869 up the old state of SVAL. */
870 gcc_assert (m_old_state
);
872 /* SVAL has leaked within the new state: it is not used by any reachable
874 We need to convert it back to a tree, but since it's likely no regions
875 use it, we have to find the "best" tree for it in the old_state. */
878 = m_old_state
->m_region_model
->get_representative_path_var (sval
,
881 /* Strip off top-level casts */
882 if (leaked_pv
.m_tree
&& TREE_CODE (leaked_pv
.m_tree
) == NOP_EXPR
)
883 leaked_pv
.m_tree
= TREE_OPERAND (leaked_pv
.m_tree
, 0);
885 /* This might be NULL; the pending_diagnostic subclasses need to cope
887 tree leaked_tree
= leaked_pv
.m_tree
;
891 logger
->log ("best leaked_tree: %qE", leaked_tree
);
893 logger
->log ("best leaked_tree: NULL");
896 leak_stmt_finder
stmt_finder (*m_eg
, leaked_tree
);
897 gcc_assert (m_enode_for_diag
);
899 /* Don't complain about leaks when returning from "main". */
900 if (returning_from_function_p (m_enode_for_diag
->get_supernode ()))
902 tree fndecl
= m_enode_for_diag
->get_function ()->decl
;
903 if (id_equal (DECL_NAME (fndecl
), "main"))
906 logger
->log ("not reporting leak from main");
911 tree leaked_tree_for_diag
= fixup_tree_for_diagnostic (leaked_tree
);
912 std::unique_ptr
<pending_diagnostic
> pd
= sm
.on_leak (leaked_tree_for_diag
);
915 pending_location
ploc (m_enode_for_diag
,
916 m_enode_for_diag
->get_supernode (),
919 m_eg
->get_diagnostic_manager ().add_diagnostic
921 leaked_tree_for_diag
, sval
, state
, std::move (pd
));
925 /* Implementation of region_model_context::on_condition vfunc.
926 Notify all state machines about the condition, which could lead to
927 state transitions. */
930 impl_region_model_context::on_condition (const svalue
*lhs
,
936 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
938 const state_machine
&sm
= m_ext_state
.get_sm (sm_idx
);
939 impl_sm_context
sm_ctxt (*m_eg
, sm_idx
, sm
, m_enode_for_diag
,
940 m_old_state
, m_new_state
,
941 m_old_state
->m_checker_states
[sm_idx
],
942 m_new_state
->m_checker_states
[sm_idx
],
944 sm
.on_condition (&sm_ctxt
,
946 ? m_enode_for_diag
->get_supernode ()
953 /* Implementation of region_model_context::on_bounded_ranges vfunc.
954 Notify all state machines about the ranges, which could lead to
955 state transitions. */
958 impl_region_model_context::on_bounded_ranges (const svalue
&sval
,
959 const bounded_ranges
&ranges
)
963 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
965 const state_machine
&sm
= m_ext_state
.get_sm (sm_idx
);
966 impl_sm_context
sm_ctxt (*m_eg
, sm_idx
, sm
, m_enode_for_diag
,
967 m_old_state
, m_new_state
,
968 m_old_state
->m_checker_states
[sm_idx
],
969 m_new_state
->m_checker_states
[sm_idx
],
971 sm
.on_bounded_ranges (&sm_ctxt
,
973 ? m_enode_for_diag
->get_supernode ()
975 m_stmt
, sval
, ranges
);
979 /* Implementation of region_model_context::on_pop_frame vfunc.
980 Notify all state machines about the frame being popped, which
981 could lead to states being discarded. */
984 impl_region_model_context::on_pop_frame (const frame_region
*frame_reg
)
988 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
990 const state_machine
&sm
= m_ext_state
.get_sm (sm_idx
);
991 sm
.on_pop_frame (smap
, frame_reg
);
995 /* Implementation of region_model_context::on_phi vfunc.
996 Notify all state machines about the phi, which could lead to
997 state transitions. */
1000 impl_region_model_context::on_phi (const gphi
*phi
, tree rhs
)
1004 FOR_EACH_VEC_ELT (m_new_state
->m_checker_states
, sm_idx
, smap
)
1006 const state_machine
&sm
= m_ext_state
.get_sm (sm_idx
);
1007 impl_sm_context
sm_ctxt (*m_eg
, sm_idx
, sm
, m_enode_for_diag
,
1008 m_old_state
, m_new_state
,
1009 m_old_state
->m_checker_states
[sm_idx
],
1010 m_new_state
->m_checker_states
[sm_idx
],
1012 sm
.on_phi (&sm_ctxt
, m_enode_for_diag
->get_supernode (), phi
, rhs
);
1016 /* Implementation of region_model_context::on_unexpected_tree_code vfunc.
1017 Mark the new state as being invalid for further exploration.
1018 TODO(stage1): introduce a warning for when this occurs. */
1021 impl_region_model_context::on_unexpected_tree_code (tree t
,
1022 const dump_location_t
&loc
)
1024 logger
* const logger
= get_logger ();
1026 logger
->log ("unhandled tree code: %qs in %qs at %s:%i",
1027 get_tree_code_name (TREE_CODE (t
)),
1028 loc
.get_impl_location ().m_function
,
1029 loc
.get_impl_location ().m_file
,
1030 loc
.get_impl_location ().m_line
);
1032 m_new_state
->m_valid
= false;
1035 /* Implementation of region_model_context::maybe_did_work vfunc.
1036 Mark that "externally visible work" has occurred, and thus we
1037 shouldn't report an infinite loop here. */
1040 impl_region_model_context::maybe_did_work ()
1042 if (m_out_could_have_done_work
)
1043 *m_out_could_have_done_work
= true;
1046 /* struct point_and_state. */
1048 /* Assert that this object is sane. */
1051 point_and_state::validate (const extrinsic_state
&ext_state
) const
1053 /* Skip this in a release build. */
1058 m_point
.validate ();
1060 m_state
.validate (ext_state
);
1062 /* Verify that the callstring's model of the stack corresponds to that
1063 of the region_model. */
1064 /* They should have the same depth. */
1065 gcc_assert (m_point
.get_stack_depth ()
1066 == m_state
.m_region_model
->get_stack_depth ());
1067 /* Check the functions in the callstring vs those in the frames
1069 for (const frame_region
*iter_frame
1070 = m_state
.m_region_model
->get_current_frame ();
1071 iter_frame
; iter_frame
= iter_frame
->get_calling_frame ())
1073 int index
= iter_frame
->get_index ();
1074 gcc_assert (m_point
.get_function_at_depth (index
)
1075 == iter_frame
->get_function ());
1079 /* Subroutine of print_enode_indices: print a run of indices from START_IDX
1080 to END_IDX to PP, using and updating *FIRST_RUN. */
1083 print_run (pretty_printer
*pp
, int start_idx
, int end_idx
,
1087 pp_string (pp
, ", ");
1089 if (start_idx
== end_idx
)
1090 pp_printf (pp
, "EN: %i", start_idx
);
1092 pp_printf (pp
, "EN: %i-%i", start_idx
, end_idx
);
1095 /* Print the indices within ENODES to PP, collecting them as
1096 runs/singletons e.g. "EN: 4-7, EN: 20-23, EN: 42". */
1099 print_enode_indices (pretty_printer
*pp
,
1100 const auto_vec
<exploded_node
*> &enodes
)
1102 int cur_start_idx
= -1;
1103 int cur_finish_idx
= -1;
1104 bool first_run
= true;
1106 exploded_node
*enode
;
1107 FOR_EACH_VEC_ELT (enodes
, i
, enode
)
1109 if (cur_start_idx
== -1)
1111 gcc_assert (cur_finish_idx
== -1);
1112 cur_start_idx
= cur_finish_idx
= enode
->m_index
;
1116 if (enode
->m_index
== cur_finish_idx
+ 1)
1117 /* Continuation of a run. */
1118 cur_finish_idx
= enode
->m_index
;
1121 /* Finish existing run, start a new one. */
1122 gcc_assert (cur_start_idx
>= 0);
1123 gcc_assert (cur_finish_idx
>= 0);
1124 print_run (pp
, cur_start_idx
, cur_finish_idx
,
1126 cur_start_idx
= cur_finish_idx
= enode
->m_index
;
1130 /* Finish any existing run. */
1131 if (cur_start_idx
>= 0)
1133 gcc_assert (cur_finish_idx
>= 0);
1134 print_run (pp
, cur_start_idx
, cur_finish_idx
,
1139 /* struct eg_traits::dump_args_t. */
1141 /* The <FILENAME>.eg.dot output can quickly become unwieldy if we show
1142 full details for all enodes (both in terms of CPU time to render it,
1143 and in terms of being meaningful to a human viewing it).
1145 If we show just the IDs then the resulting graph is usually viewable,
1146 but then we have to keep switching back and forth between the .dot
1147 view and other dumps.
1149 This function implements a heuristic for showing detail at the enodes
1150 that (we hope) matter, and just the ID at other enodes, fixing the CPU
1151 usage of the .dot viewer, and drawing the attention of the viewer
1154 Return true if ENODE should be shown in detail in .dot output.
1155 Return false if no detail should be shown for ENODE. */
1158 eg_traits::dump_args_t::show_enode_details_p (const exploded_node
&enode
) const
1160 /* If the number of exploded nodes isn't too large, we may as well show
1161 all enodes in full detail in the .dot output. */
1162 if (m_eg
.m_nodes
.length ()
1163 <= (unsigned) param_analyzer_max_enodes_for_full_dump
)
1166 /* Otherwise, assume that what's most interesting are state explosions,
1167 and thus the places where this happened.
1168 Expand enodes at program points where we hit the per-enode limit, so we
1169 can investigate what exploded. */
1170 const per_program_point_data
*per_point_data
1171 = m_eg
.get_per_program_point_data (enode
.get_point ());
1172 return per_point_data
->m_excess_enodes
> 0;
1175 /* class exploded_node : public dnode<eg_traits>. */
1178 exploded_node::status_to_str (enum status s
)
1182 default: gcc_unreachable ();
1183 case STATUS_WORKLIST
: return "WORKLIST";
1184 case STATUS_PROCESSED
: return "PROCESSED";
1185 case STATUS_MERGER
: return "MERGER";
1186 case STATUS_BULK_MERGED
: return "BULK_MERGED";
1190 /* exploded_node's ctor. */
1192 exploded_node::exploded_node (const point_and_state
&ps
,
1194 : m_ps (ps
), m_status (STATUS_WORKLIST
), m_index (index
),
1195 m_num_processed_stmts (0)
1197 gcc_checking_assert (ps
.get_state ().m_region_model
->canonicalized_p ());
1200 /* Get the stmt that was processed in this enode at index IDX.
1201 IDX is an index within the stmts processed at this enode, rather
1202 than within those of the supernode. */
1205 exploded_node::get_processed_stmt (unsigned idx
) const
1207 gcc_assert (idx
< m_num_processed_stmts
);
1208 const program_point
&point
= get_point ();
1209 gcc_assert (point
.get_kind () == PK_BEFORE_STMT
);
1210 const supernode
*snode
= get_supernode ();
1211 const unsigned int point_stmt_idx
= point
.get_stmt_idx ();
1212 const unsigned int idx_within_snode
= point_stmt_idx
+ idx
;
1213 const gimple
*stmt
= snode
->m_stmts
[idx_within_snode
];
1217 /* For use by dump_dot, get a value for the .dot "fillcolor" attribute.
1218 Colorize by sm-state, to make it easier to see how sm-state propagates
1219 through the exploded_graph. */
1222 exploded_node::get_dot_fillcolor () const
1224 const program_state
&state
= get_state ();
1226 /* We want to be able to easily distinguish the no-sm-state case,
1227 and to be able to distinguish cases where there's a single state
1230 Sum the sm_states, and use the result to choose from a table,
1231 modulo table-size, special-casing the "no sm-state" case. */
1232 int total_sm_state
= 0;
1235 FOR_EACH_VEC_ELT (state
.m_checker_states
, i
, smap
)
1237 for (sm_state_map::iterator_t iter
= smap
->begin ();
1238 iter
!= smap
->end ();
1240 total_sm_state
+= (*iter
).second
.m_state
->get_id ();
1241 total_sm_state
+= smap
->get_global_state ()->get_id ();
1244 if (total_sm_state
> 0)
1246 /* An arbitrarily-picked collection of light colors. */
1247 const char * const colors
[]
1248 = {"azure", "coral", "cornsilk", "lightblue", "yellow",
1249 "honeydew", "lightpink", "lightsalmon", "palegreen1",
1250 "wheat", "seashell"};
1251 const int num_colors
= ARRAY_SIZE (colors
);
1252 return colors
[total_sm_state
% num_colors
];
1259 /* Implementation of dnode::dump_dot vfunc for exploded_node. */
1262 exploded_node::dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const
1264 pretty_printer
*pp
= gv
->get_pp ();
1267 pp_printf (pp
, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
1268 get_dot_fillcolor ());
1269 pp_write_text_to_stream (pp
);
1271 pp_printf (pp
, "EN: %i", m_index
);
1272 if (m_status
== STATUS_MERGER
)
1273 pp_string (pp
, " (merger)");
1274 else if (m_status
== STATUS_BULK_MERGED
)
1275 pp_string (pp
, " (bulk merged)");
1278 if (args
.show_enode_details_p (*this))
1281 m_ps
.get_point ().print (pp
, f
);
1284 const extrinsic_state
&ext_state
= args
.m_eg
.get_ext_state ();
1285 const program_state
&state
= m_ps
.get_state ();
1286 state
.dump_to_pp (ext_state
, false, true, pp
);
1289 dump_processed_stmts (pp
);
1292 dump_saved_diagnostics (pp
);
1294 args
.dump_extra_info (this, pp
);
1296 pp_write_text_as_dot_label_to_stream (pp
, /*for_record=*/true);
1298 pp_string (pp
, "\"];\n\n");
1300 /* It can be hard to locate the saved diagnostics as text within the
1301 enode nodes, so add extra nodes to the graph for each saved_diagnostic,
1303 Compare with dump_saved_diagnostics. */
1306 const saved_diagnostic
*sd
;
1307 FOR_EACH_VEC_ELT (m_saved_diagnostics
, i
, sd
)
1309 sd
->dump_as_dot_node (pp
);
1311 /* Add edge connecting this enode to the saved_diagnostic. */
1313 pp_string (pp
, " -> ");
1314 sd
->dump_dot_id (pp
);
1315 pp_string (pp
, " [style=\"dotted\" arrowhead=\"none\"];");
1323 /* Show any stmts that were processed within this enode,
1324 and their index within the supernode. */
1326 exploded_node::dump_processed_stmts (pretty_printer
*pp
) const
1328 if (m_num_processed_stmts
> 0)
1330 const program_point
&point
= get_point ();
1331 gcc_assert (point
.get_kind () == PK_BEFORE_STMT
);
1332 const supernode
*snode
= get_supernode ();
1333 const unsigned int point_stmt_idx
= point
.get_stmt_idx ();
1335 pp_printf (pp
, "stmts: %i", m_num_processed_stmts
);
1337 for (unsigned i
= 0; i
< m_num_processed_stmts
; i
++)
1339 const unsigned int idx_within_snode
= point_stmt_idx
+ i
;
1340 const gimple
*stmt
= snode
->m_stmts
[idx_within_snode
];
1341 pp_printf (pp
, " %i: ", idx_within_snode
);
1342 pp_gimple_stmt_1 (pp
, stmt
, 0, (dump_flags_t
)0);
1348 /* Dump any saved_diagnostics at this enode to PP. */
1351 exploded_node::dump_saved_diagnostics (pretty_printer
*pp
) const
1354 const saved_diagnostic
*sd
;
1355 FOR_EACH_VEC_ELT (m_saved_diagnostics
, i
, sd
)
1357 pp_printf (pp
, "DIAGNOSTIC: %s (sd: %i)",
1358 sd
->m_d
->get_kind (), sd
->get_index ());
1363 /* Dump this to PP in a form suitable for use as an id in .dot output. */
1366 exploded_node::dump_dot_id (pretty_printer
*pp
) const
1368 pp_printf (pp
, "exploded_node_%i", m_index
);
1371 /* Dump a multiline representation of this node to PP. */
1374 exploded_node::dump_to_pp (pretty_printer
*pp
,
1375 const extrinsic_state
&ext_state
) const
1377 pp_printf (pp
, "EN: %i", m_index
);
1381 m_ps
.get_point ().print (pp
, f
);
1384 m_ps
.get_state ().dump_to_pp (ext_state
, false, true, pp
);
1388 /* Dump a multiline representation of this node to FILE. */
1391 exploded_node::dump (FILE *fp
,
1392 const extrinsic_state
&ext_state
) const
1395 pp_format_decoder (&pp
) = default_tree_printer
;
1396 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
1397 pp
.buffer
->stream
= fp
;
1398 dump_to_pp (&pp
, ext_state
);
1402 /* Dump a multiline representation of this node to stderr. */
1405 exploded_node::dump (const extrinsic_state
&ext_state
) const
1407 dump (stderr
, ext_state
);
1410 /* Return a new json::object of the form
1411 {"point" : object for program_point,
1412 "state" : object for program_state,
1415 "processed_stmts" : int}. */
1418 exploded_node::to_json (const extrinsic_state
&ext_state
) const
1420 json::object
*enode_obj
= new json::object ();
1422 enode_obj
->set ("point", get_point ().to_json ());
1423 enode_obj
->set ("state", get_state ().to_json (ext_state
));
1424 enode_obj
->set ("status", new json::string (status_to_str (m_status
)));
1425 enode_obj
->set ("idx", new json::integer_number (m_index
));
1426 enode_obj
->set ("processed_stmts",
1427 new json::integer_number (m_num_processed_stmts
));
1434 /* Return true if FNDECL has a gimple body. */
1435 // TODO: is there a pre-canned way to do this?
1438 fndecl_has_gimple_body_p (tree fndecl
)
1440 if (fndecl
== NULL_TREE
)
1443 cgraph_node
*n
= cgraph_node::get (fndecl
);
1447 return n
->has_gimple_body_p ();
1452 /* Modify STATE in place, applying the effects of the stmt at this node's
1455 exploded_node::on_stmt_flags
1456 exploded_node::on_stmt (exploded_graph
&eg
,
1457 const supernode
*snode
,
1459 program_state
*state
,
1460 uncertainty_t
*uncertainty
,
1461 bool *out_could_have_done_work
,
1462 path_context
*path_ctxt
)
1464 logger
*logger
= eg
.get_logger ();
1468 logger
->start_log_line ();
1469 pp_gimple_stmt_1 (logger
->get_printer (), stmt
, 0, (dump_flags_t
)0);
1470 logger
->end_log_line ();
1473 /* Update input_location in case of ICE: make it easier to track down which
1474 source construct we're failing to handle. */
1475 input_location
= stmt
->location
;
1477 gcc_assert (state
->m_region_model
);
1479 /* Preserve the old state. It is used here for looking
1480 up old checker states, for determining state transitions, and
1481 also within impl_region_model_context and impl_sm_context for
1482 going from tree to svalue_id. */
1483 const program_state
old_state (*state
);
1485 impl_region_model_context
ctxt (eg
, this,
1486 &old_state
, state
, uncertainty
,
1487 path_ctxt
, stmt
, nullptr,
1488 out_could_have_done_work
);
1490 /* Handle call summaries here. */
1491 if (cgraph_edge
*cgedge
1492 = supergraph_call_edge (snode
->get_function (), stmt
))
1493 if (eg
.get_analysis_plan ().use_summary_p (cgedge
))
1495 function
*called_fn
= get_ultimate_function_for_cgraph_edge (cgedge
);
1496 per_function_data
*called_fn_data
1497 = eg
.get_per_function_data (called_fn
);
1499 return replay_call_summaries (eg
,
1501 as_a
<const gcall
*> (stmt
),
1509 bool unknown_side_effects
= false;
1510 bool terminate_path
= false;
1512 on_stmt_pre (eg
, stmt
, state
, &terminate_path
,
1513 &unknown_side_effects
, &ctxt
);
1516 return on_stmt_flags::terminate_path ();
1520 FOR_EACH_VEC_ELT (old_state
.m_checker_states
, sm_idx
, smap
)
1522 const state_machine
&sm
= eg
.get_ext_state ().get_sm (sm_idx
);
1523 const sm_state_map
*old_smap
1524 = old_state
.m_checker_states
[sm_idx
];
1525 sm_state_map
*new_smap
= state
->m_checker_states
[sm_idx
];
1526 impl_sm_context
sm_ctxt (eg
, sm_idx
, sm
, this, &old_state
, state
,
1527 old_smap
, new_smap
, path_ctxt
, NULL
,
1528 unknown_side_effects
);
1530 /* Allow the state_machine to handle the stmt. */
1531 if (sm
.on_stmt (&sm_ctxt
, snode
, stmt
))
1532 unknown_side_effects
= false;
1535 if (path_ctxt
->terminate_path_p ())
1536 return on_stmt_flags::terminate_path ();
1538 on_stmt_post (stmt
, state
, unknown_side_effects
, &ctxt
);
1540 return on_stmt_flags ();
1543 /* Handle the pre-sm-state part of STMT, modifying STATE in-place.
1544 Write true to *OUT_TERMINATE_PATH if the path should be terminated.
1545 Write true to *OUT_UNKNOWN_SIDE_EFFECTS if the stmt has unknown
1549 exploded_node::on_stmt_pre (exploded_graph
&eg
,
1551 program_state
*state
,
1552 bool *out_terminate_path
,
1553 bool *out_unknown_side_effects
,
1554 region_model_context
*ctxt
)
1556 /* Handle special-case calls that require the full program_state. */
1557 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
1559 if (is_special_named_call_p (call
, "__analyzer_dump", 0))
1561 /* Handle the builtin "__analyzer_dump" by dumping state
1563 state
->dump (eg
.get_ext_state (), true);
1566 else if (is_special_named_call_p (call
, "__analyzer_dump_state", 2))
1568 state
->impl_call_analyzer_dump_state (call
, eg
.get_ext_state (),
1572 else if (is_setjmp_call_p (call
))
1574 state
->m_region_model
->on_setjmp (call
, this, ctxt
);
1576 ctxt
->maybe_did_work ();
1579 else if (is_longjmp_call_p (call
))
1581 on_longjmp (eg
, call
, state
, ctxt
);
1582 *out_terminate_path
= true;
1584 ctxt
->maybe_did_work ();
1589 /* Otherwise, defer to m_region_model. */
1590 state
->m_region_model
->on_stmt_pre (stmt
,
1591 out_unknown_side_effects
,
1595 /* Handle the post-sm-state part of STMT, modifying STATE in-place. */
1598 exploded_node::on_stmt_post (const gimple
*stmt
,
1599 program_state
*state
,
1600 bool unknown_side_effects
,
1601 region_model_context
*ctxt
)
1603 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
1604 state
->m_region_model
->on_call_post (call
, unknown_side_effects
, ctxt
);
1607 /* A concrete call_info subclass representing a replay of a call summary. */
1609 class call_summary_edge_info
: public call_info
1612 call_summary_edge_info (const call_details
&cd
,
1613 function
*called_fn
,
1614 call_summary
*summary
,
1615 const extrinsic_state
&ext_state
)
1617 m_called_fn (called_fn
),
1618 m_summary (summary
),
1619 m_ext_state (ext_state
)
1622 bool update_state (program_state
*state
,
1623 const exploded_edge
*,
1624 region_model_context
*ctxt
) const final override
1626 /* Update STATE based on summary_end_state. */
1627 call_details
cd (get_call_details (state
->m_region_model
, ctxt
));
1628 call_summary_replay
r (cd
, m_called_fn
, m_summary
, m_ext_state
);
1629 const program_state
&summary_end_state
= m_summary
->get_state ();
1630 return state
->replay_call_summary (r
, summary_end_state
);
1633 bool update_model (region_model
*model
,
1634 const exploded_edge
*,
1635 region_model_context
*ctxt
) const final override
1637 /* Update STATE based on summary_end_state. */
1638 call_details
cd (get_call_details (model
, ctxt
));
1639 call_summary_replay
r (cd
, m_called_fn
, m_summary
, m_ext_state
);
1640 const program_state
&summary_end_state
= m_summary
->get_state ();
1641 model
->replay_call_summary (r
, *summary_end_state
.m_region_model
);
1645 label_text
get_desc (bool /*can_colorize*/) const final override
1647 return m_summary
->get_desc ();
1651 function
*m_called_fn
;
1652 call_summary
*m_summary
;
1653 const extrinsic_state
&m_ext_state
;
1656 /* Use PATH_CTXT to bifurcate, which when handled will add custom edges
1657 for a replay of the various feasible summaries in CALLED_FN_DATA. */
1659 exploded_node::on_stmt_flags
1660 exploded_node::replay_call_summaries (exploded_graph
&eg
,
1661 const supernode
*snode
,
1662 const gcall
*call_stmt
,
1663 program_state
*state
,
1664 path_context
*path_ctxt
,
1665 function
*called_fn
,
1666 per_function_data
*called_fn_data
,
1667 region_model_context
*ctxt
)
1669 logger
*logger
= eg
.get_logger ();
1672 gcc_assert (called_fn
);
1673 gcc_assert (called_fn_data
);
1675 /* Each summary will call bifurcate on the PATH_CTXT. */
1676 for (auto summary
: called_fn_data
->m_summaries
)
1677 replay_call_summary (eg
, snode
, call_stmt
, state
,
1678 path_ctxt
, called_fn
, summary
, ctxt
);
1679 path_ctxt
->terminate_path ();
1681 return on_stmt_flags ();
1684 /* Use PATH_CTXT to bifurcate, which when handled will add a
1685 custom edge for a replay of SUMMARY, if the summary's
1686 conditions are feasible based on the current state. */
1689 exploded_node::replay_call_summary (exploded_graph
&eg
,
1690 const supernode
*snode
,
1691 const gcall
*call_stmt
,
1692 program_state
*old_state
,
1693 path_context
*path_ctxt
,
1694 function
*called_fn
,
1695 call_summary
*summary
,
1696 region_model_context
*ctxt
)
1698 logger
*logger
= eg
.get_logger ();
1701 gcc_assert (call_stmt
);
1702 gcc_assert (old_state
);
1703 gcc_assert (called_fn
);
1704 gcc_assert (summary
);
1707 logger
->log ("using %s as summary for call to %qE from %qE",
1708 summary
->get_desc ().get (),
1710 snode
->get_function ()->decl
);
1711 const extrinsic_state
&ext_state
= eg
.get_ext_state ();
1712 const program_state
&summary_end_state
= summary
->get_state ();
1715 pretty_printer
*pp
= logger
->get_printer ();
1717 logger
->start_log_line ();
1718 pp_string (pp
, "callsite state: ");
1719 old_state
->dump_to_pp (ext_state
, true, false, pp
);
1720 logger
->end_log_line ();
1722 logger
->start_log_line ();
1723 pp_string (pp
, "summary end state: ");
1724 summary_end_state
.dump_to_pp (ext_state
, true, false, pp
);
1725 logger
->end_log_line ();
1728 program_state
new_state (*old_state
);
1730 call_details
cd (call_stmt
, new_state
.m_region_model
, ctxt
);
1731 call_summary_replay
r (cd
, called_fn
, summary
, ext_state
);
1734 path_ctxt
->bifurcate (make_unique
<call_summary_edge_info
> (cd
,
1741 /* Consider the effect of following superedge SUCC from this node.
1743 Return true if it's feasible to follow the edge, or false
1746 Examples: if it's the "true" branch within
1747 a CFG and we know the conditional is false, we know it's infeasible.
1748 If it's one of multiple interprocedual "return" edges, then only
1749 the edge back to the most recent callsite is feasible.
1751 Update NEXT_STATE accordingly (e.g. to record that a condition was
1752 true or false, or that the NULL-ness of a pointer has been checked,
1753 pushing/popping stack frames, etc).
1755 Update NEXT_POINT accordingly (updating the call string). */
1758 exploded_node::on_edge (exploded_graph
&eg
,
1759 const superedge
*succ
,
1760 program_point
*next_point
,
1761 program_state
*next_state
,
1762 uncertainty_t
*uncertainty
)
1764 LOG_FUNC (eg
.get_logger ());
1766 if (!next_point
->on_edge (eg
, succ
))
1769 if (!next_state
->on_edge (eg
, this, succ
, uncertainty
))
1775 /* Verify that the stack at LONGJMP_POINT is still valid, given a call
1776 to "setjmp" at SETJMP_POINT - the stack frame that "setjmp" was
1777 called in must still be valid.
1779 Caveat: this merely checks the call_strings in the points; it doesn't
1780 detect the case where a frame returns and is then called again. */
1783 valid_longjmp_stack_p (const program_point
&longjmp_point
,
1784 const program_point
&setjmp_point
)
1786 const call_string
&cs_at_longjmp
= longjmp_point
.get_call_string ();
1787 const call_string
&cs_at_setjmp
= setjmp_point
.get_call_string ();
1789 if (cs_at_longjmp
.length () < cs_at_setjmp
.length ())
1792 /* Check that the call strings match, up to the depth of the
1794 for (unsigned depth
= 0; depth
< cs_at_setjmp
.length (); depth
++)
1795 if (cs_at_longjmp
[depth
] != cs_at_setjmp
[depth
])
1801 /* A pending_diagnostic subclass for complaining about bad longjmps,
1802 where the enclosing function of the "setjmp" has returned (and thus
1803 the stack frame no longer exists). */
1805 class stale_jmp_buf
: public pending_diagnostic_subclass
<stale_jmp_buf
>
1808 stale_jmp_buf (const gcall
*setjmp_call
, const gcall
*longjmp_call
,
1809 const program_point
&setjmp_point
)
1810 : m_setjmp_call (setjmp_call
), m_longjmp_call (longjmp_call
),
1811 m_setjmp_point (setjmp_point
), m_stack_pop_event (NULL
)
1814 int get_controlling_option () const final override
1816 return OPT_Wanalyzer_stale_setjmp_buffer
;
1819 bool emit (diagnostic_emission_context
&ctxt
) final override
1821 return ctxt
.warn ("%qs called after enclosing function of %qs has returned",
1822 get_user_facing_name (m_longjmp_call
),
1823 get_user_facing_name (m_setjmp_call
));
1826 const char *get_kind () const final override
1827 { return "stale_jmp_buf"; }
1829 bool operator== (const stale_jmp_buf
&other
) const
1831 return (m_setjmp_call
== other
.m_setjmp_call
1832 && m_longjmp_call
== other
.m_longjmp_call
);
1836 maybe_add_custom_events_for_superedge (const exploded_edge
&eedge
,
1837 checker_path
*emission_path
)
1840 /* Detect exactly when the stack first becomes invalid,
1841 and issue an event then. */
1842 if (m_stack_pop_event
)
1844 const exploded_node
*src_node
= eedge
.m_src
;
1845 const program_point
&src_point
= src_node
->get_point ();
1846 const exploded_node
*dst_node
= eedge
.m_dest
;
1847 const program_point
&dst_point
= dst_node
->get_point ();
1848 if (valid_longjmp_stack_p (src_point
, m_setjmp_point
)
1849 && !valid_longjmp_stack_p (dst_point
, m_setjmp_point
))
1851 /* Compare with diagnostic_manager::add_events_for_superedge. */
1852 const int src_stack_depth
= src_point
.get_stack_depth ();
1853 m_stack_pop_event
= new precanned_custom_event
1854 (event_loc_info (src_point
.get_location (),
1855 src_point
.get_fndecl (),
1857 "stack frame is popped here, invalidating saved environment");
1858 emission_path
->add_event
1859 (std::unique_ptr
<custom_event
> (m_stack_pop_event
));
1865 label_text
describe_final_event (const evdesc::final_event
&ev
) final override
1867 if (m_stack_pop_event
)
1868 return ev
.formatted_print
1869 ("%qs called after enclosing function of %qs returned at %@",
1870 get_user_facing_name (m_longjmp_call
),
1871 get_user_facing_name (m_setjmp_call
),
1872 m_stack_pop_event
->get_id_ptr ());
1874 return ev
.formatted_print
1875 ("%qs called after enclosing function of %qs has returned",
1876 get_user_facing_name (m_longjmp_call
),
1877 get_user_facing_name (m_setjmp_call
));;
1882 const gcall
*m_setjmp_call
;
1883 const gcall
*m_longjmp_call
;
1884 program_point m_setjmp_point
;
1885 custom_event
*m_stack_pop_event
;
1888 /* Handle LONGJMP_CALL, a call to longjmp or siglongjmp.
1890 Attempt to locate where setjmp/sigsetjmp was called on the jmp_buf and build
1891 an exploded_node and exploded_edge to it representing a rewind to that frame,
1892 handling the various kinds of failure that can occur. */
1895 exploded_node::on_longjmp (exploded_graph
&eg
,
1896 const gcall
*longjmp_call
,
1897 program_state
*new_state
,
1898 region_model_context
*ctxt
)
1900 tree buf_ptr
= gimple_call_arg (longjmp_call
, 0);
1901 gcc_assert (POINTER_TYPE_P (TREE_TYPE (buf_ptr
)));
1903 region_model
*new_region_model
= new_state
->m_region_model
;
1904 const svalue
*buf_ptr_sval
= new_region_model
->get_rvalue (buf_ptr
, ctxt
);
1905 const region
*buf
= new_region_model
->deref_rvalue (buf_ptr_sval
, buf_ptr
,
1908 const svalue
*buf_content_sval
1909 = new_region_model
->get_store_value (buf
, ctxt
);
1910 const setjmp_svalue
*setjmp_sval
1911 = buf_content_sval
->dyn_cast_setjmp_svalue ();
1915 const setjmp_record tmp_setjmp_record
= setjmp_sval
->get_setjmp_record ();
1917 /* Build a custom enode and eedge for rewinding from the longjmp/siglongjmp
1918 call back to the setjmp/sigsetjmp. */
1919 rewind_info_t
rewind_info (tmp_setjmp_record
, longjmp_call
);
1921 const gcall
*setjmp_call
= rewind_info
.get_setjmp_call ();
1922 const program_point
&setjmp_point
= rewind_info
.get_setjmp_point ();
1924 const program_point
&longjmp_point
= get_point ();
1926 /* Verify that the setjmp's call_stack hasn't been popped. */
1927 if (!valid_longjmp_stack_p (longjmp_point
, setjmp_point
))
1929 ctxt
->warn (make_unique
<stale_jmp_buf
> (setjmp_call
,
1935 gcc_assert (longjmp_point
.get_stack_depth ()
1936 >= setjmp_point
.get_stack_depth ());
1938 /* Update the state for use by the destination node. */
1940 /* Stash the current number of diagnostics so that we can update
1941 any that this adds to show where the longjmp is rewinding to. */
1943 diagnostic_manager
*dm
= &eg
.get_diagnostic_manager ();
1944 unsigned prev_num_diagnostics
= dm
->get_num_diagnostics ();
1946 new_region_model
->on_longjmp (longjmp_call
, setjmp_call
,
1947 setjmp_point
.get_stack_depth (), ctxt
);
1949 /* Detect leaks in the new state relative to the old state. */
1950 program_state::detect_leaks (get_state (), *new_state
, NULL
,
1951 eg
.get_ext_state (), ctxt
);
1953 program_point next_point
1954 = program_point::after_supernode (setjmp_point
.get_supernode (),
1955 setjmp_point
.get_call_string ());
1958 = eg
.get_or_create_node (next_point
, *new_state
, this);
1960 /* Create custom exploded_edge for a longjmp. */
1963 exploded_edge
*eedge
1964 = eg
.add_edge (const_cast<exploded_node
*> (this), next
, NULL
, true,
1965 make_unique
<rewind_info_t
> (tmp_setjmp_record
,
1968 /* For any diagnostics that were queued here (such as leaks) we want
1969 the checker_path to show the rewinding events after the "final event"
1970 so that the user sees where the longjmp is rewinding to (otherwise the
1971 path is meaningless).
1973 For example, we want to emit something like:
1975 | NN | longjmp (env, 1);
1976 | | ~~~~~~~~~~~~~~~~
1978 | | (10) 'ptr' leaks here; was allocated at (7)
1979 | | (11) rewinding from 'longjmp' in 'inner'...
1985 | NN | i = setjmp(env);
1988 | | (12) ...to 'setjmp' in 'outer' (saved at (2))
1990 where the "final" event above is event (10), but we want to append
1991 events (11) and (12) afterwards.
1993 Do this by setting m_trailing_eedge on any diagnostics that were
1995 unsigned num_diagnostics
= dm
->get_num_diagnostics ();
1996 for (unsigned i
= prev_num_diagnostics
; i
< num_diagnostics
; i
++)
1998 saved_diagnostic
*sd
= dm
->get_saved_diagnostic (i
);
1999 sd
->m_trailing_eedge
= eedge
;
2004 /* Subroutine of exploded_graph::process_node for finding the successors
2005 of the supernode for a function exit basic block.
2007 Ensure that pop_frame is called, potentially queuing diagnostics about
2011 exploded_node::detect_leaks (exploded_graph
&eg
)
2013 LOG_FUNC_1 (eg
.get_logger (), "EN: %i", m_index
);
2015 gcc_assert (get_point ().get_supernode ()->return_p ());
2017 /* If we're not a "top-level" function, do nothing; pop_frame
2018 will be called when handling the return superedge. */
2019 if (get_point ().get_stack_depth () > 1)
2022 /* We have a "top-level" function. */
2023 gcc_assert (get_point ().get_stack_depth () == 1);
2025 const program_state
&old_state
= get_state ();
2027 /* Work with a temporary copy of the state: pop the frame, and see
2028 what leaks (via purge_unused_svalues). */
2029 program_state
new_state (old_state
);
2031 gcc_assert (new_state
.m_region_model
);
2033 uncertainty_t uncertainty
;
2034 impl_region_model_context
ctxt (eg
, this,
2035 &old_state
, &new_state
, &uncertainty
, NULL
,
2037 const svalue
*result
= NULL
;
2038 new_state
.m_region_model
->pop_frame (NULL
, &result
, &ctxt
);
2039 program_state::detect_leaks (old_state
, new_state
, result
,
2040 eg
.get_ext_state (), &ctxt
);
2043 /* Dump the successors and predecessors of this enode to OUTF. */
2046 exploded_node::dump_succs_and_preds (FILE *outf
) const
2051 auto_vec
<exploded_node
*> preds (m_preds
.length ());
2052 FOR_EACH_VEC_ELT (m_preds
, i
, e
)
2053 preds
.quick_push (e
->m_src
);
2055 print_enode_indices (&pp
, preds
);
2056 fprintf (outf
, "preds: %s\n",
2057 pp_formatted_text (&pp
));
2060 auto_vec
<exploded_node
*> succs (m_succs
.length ());
2061 FOR_EACH_VEC_ELT (m_succs
, i
, e
)
2062 succs
.quick_push (e
->m_dest
);
2064 print_enode_indices (&pp
, succs
);
2065 fprintf (outf
, "succs: %s\n",
2066 pp_formatted_text (&pp
));
2070 /* class dynamic_call_info_t : public custom_edge_info. */
2072 /* Implementation of custom_edge_info::update_model vfunc
2073 for dynamic_call_info_t.
2075 Update state for a dynamically discovered call (or return), by pushing
2076 or popping the a frame for the appropriate function. */
2079 dynamic_call_info_t::update_model (region_model
*model
,
2080 const exploded_edge
*eedge
,
2081 region_model_context
*ctxt
) const
2084 if (m_is_returning_call
)
2085 model
->update_for_return_gcall (m_dynamic_call
, ctxt
);
2088 function
*callee
= eedge
->m_dest
->get_function ();
2089 model
->update_for_gcall (m_dynamic_call
, ctxt
, callee
);
2094 /* Implementation of custom_edge_info::add_events_to_path vfunc
2095 for dynamic_call_info_t. */
2098 dynamic_call_info_t::add_events_to_path (checker_path
*emission_path
,
2099 const exploded_edge
&eedge
) const
2101 const exploded_node
*src_node
= eedge
.m_src
;
2102 const program_point
&src_point
= src_node
->get_point ();
2103 const int src_stack_depth
= src_point
.get_stack_depth ();
2104 const exploded_node
*dest_node
= eedge
.m_dest
;
2105 const program_point
&dest_point
= dest_node
->get_point ();
2106 const int dest_stack_depth
= dest_point
.get_stack_depth ();
2108 if (m_is_returning_call
)
2109 emission_path
->add_event
2110 (make_unique
<return_event
> (eedge
,
2111 event_loc_info (m_dynamic_call
2112 ? m_dynamic_call
->location
2114 dest_point
.get_fndecl (),
2115 dest_stack_depth
)));
2117 emission_path
->add_event
2118 (make_unique
<call_event
> (eedge
,
2119 event_loc_info (m_dynamic_call
2120 ? m_dynamic_call
->location
2122 src_point
.get_fndecl (),
2126 /* class rewind_info_t : public custom_edge_info. */
2128 /* Implementation of custom_edge_info::update_model vfunc
2131 Update state for the special-case of a rewind of a longjmp
2132 to a setjmp (which doesn't have a superedge, but does affect
2136 rewind_info_t::update_model (region_model
*model
,
2137 const exploded_edge
*eedge
,
2138 region_model_context
*) const
2141 const program_point
&longjmp_point
= eedge
->m_src
->get_point ();
2142 const program_point
&setjmp_point
= eedge
->m_dest
->get_point ();
2144 gcc_assert (longjmp_point
.get_stack_depth ()
2145 >= setjmp_point
.get_stack_depth ());
2147 model
->on_longjmp (get_longjmp_call (),
2149 setjmp_point
.get_stack_depth (), NULL
);
2153 /* Implementation of custom_edge_info::add_events_to_path vfunc
2154 for rewind_info_t. */
2157 rewind_info_t::add_events_to_path (checker_path
*emission_path
,
2158 const exploded_edge
&eedge
) const
2160 const exploded_node
*src_node
= eedge
.m_src
;
2161 const program_point
&src_point
= src_node
->get_point ();
2162 const int src_stack_depth
= src_point
.get_stack_depth ();
2163 const exploded_node
*dst_node
= eedge
.m_dest
;
2164 const program_point
&dst_point
= dst_node
->get_point ();
2165 const int dst_stack_depth
= dst_point
.get_stack_depth ();
2167 emission_path
->add_event
2168 (make_unique
<rewind_from_longjmp_event
>
2170 event_loc_info (get_longjmp_call ()->location
,
2171 src_point
.get_fndecl (),
2174 emission_path
->add_event
2175 (make_unique
<rewind_to_setjmp_event
>
2177 event_loc_info (get_setjmp_call ()->location
,
2178 dst_point
.get_fndecl (),
2183 /* class exploded_edge : public dedge<eg_traits>. */
2185 /* exploded_edge's ctor. */
2187 exploded_edge::exploded_edge (exploded_node
*src
, exploded_node
*dest
,
2188 const superedge
*sedge
, bool could_do_work
,
2189 std::unique_ptr
<custom_edge_info
> custom_info
)
2190 : dedge
<eg_traits
> (src
, dest
), m_sedge (sedge
),
2191 m_custom_info (std::move (custom_info
)),
2192 m_could_do_work_p (could_do_work
)
2196 /* Implementation of dedge::dump_dot vfunc for exploded_edge.
2197 Use the label of the underlying superedge, if any. */
2200 exploded_edge::dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
2202 pretty_printer
*pp
= gv
->get_pp ();
2204 m_src
->dump_dot_id (pp
);
2205 pp_string (pp
, " -> ");
2206 m_dest
->dump_dot_id (pp
);
2207 dump_dot_label (pp
);
2210 /* Second half of exploded_edge::dump_dot. This is split out
2211 for use by trimmed_graph::dump_dot and base_feasible_edge::dump_dot. */
2214 exploded_edge::dump_dot_label (pretty_printer
*pp
) const
2216 const char *style
= "\"solid,bold\"";
2217 const char *color
= "black";
2219 const char *constraint
= "true";
2222 switch (m_sedge
->m_kind
)
2226 case SUPEREDGE_CFG_EDGE
:
2228 case SUPEREDGE_CALL
:
2230 //constraint = "false";
2232 case SUPEREDGE_RETURN
:
2234 //constraint = "false";
2236 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
2237 style
= "\"dotted\"";
2243 style
= "\"dotted\"";
2247 (" [style=%s, color=%s, weight=%d, constraint=%s,"
2249 style
, color
, weight
, constraint
);
2252 m_sedge
->dump_label_to_pp (pp
, false);
2253 else if (m_custom_info
)
2254 m_custom_info
->print (pp
);
2256 pp_printf (pp
, "%s",
2257 could_do_work_p () ? "(could do work)" : "DOES NO WORK");
2259 //pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
2261 pp_printf (pp
, "\"];\n");
2264 /* Return a new json::object of the form
2265 {"src_idx": int, the index of the source exploded edge,
2266 "dst_idx": int, the index of the destination exploded edge,
2267 "sedge": (optional) object for the superedge, if any,
2268 "custom": (optional) str, a description, if this is a custom edge}. */
2271 exploded_edge::to_json () const
2273 json::object
*eedge_obj
= new json::object ();
2274 eedge_obj
->set ("src_idx", new json::integer_number (m_src
->m_index
));
2275 eedge_obj
->set ("dst_idx", new json::integer_number (m_dest
->m_index
));
2277 eedge_obj
->set ("sedge", m_sedge
->to_json ());
2281 pp_format_decoder (&pp
) = default_tree_printer
;
2282 m_custom_info
->print (&pp
);
2283 eedge_obj
->set ("custom", new json::string (pp_formatted_text (&pp
)));
2292 stats::stats (int num_supernodes
)
2293 : m_node_reuse_count (0),
2294 m_node_reuse_after_merge_count (0),
2295 m_num_supernodes (num_supernodes
)
2297 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
2301 /* Log these stats in multiline form to LOGGER. */
2304 stats::log (logger
*logger
) const
2306 gcc_assert (logger
);
2307 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
2308 if (m_num_nodes
[i
] > 0)
2309 logger
->log ("m_num_nodes[%s]: %i",
2310 point_kind_to_string (static_cast <enum point_kind
> (i
)),
2312 logger
->log ("m_node_reuse_count: %i", m_node_reuse_count
);
2313 logger
->log ("m_node_reuse_after_merge_count: %i",
2314 m_node_reuse_after_merge_count
);
2317 /* Dump these stats in multiline form to OUT. */
2320 stats::dump (FILE *out
) const
2322 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
2323 if (m_num_nodes
[i
] > 0)
2324 fprintf (out
, "m_num_nodes[%s]: %i\n",
2325 point_kind_to_string (static_cast <enum point_kind
> (i
)),
2327 fprintf (out
, "m_node_reuse_count: %i\n", m_node_reuse_count
);
2328 fprintf (out
, "m_node_reuse_after_merge_count: %i\n",
2329 m_node_reuse_after_merge_count
);
2331 if (m_num_supernodes
> 0)
2332 fprintf (out
, "PK_AFTER_SUPERNODE nodes per supernode: %.2f\n",
2333 (float)m_num_nodes
[PK_AFTER_SUPERNODE
] / (float)m_num_supernodes
);
2336 /* Return the total number of enodes recorded within this object. */
2339 stats::get_total_enodes () const
2342 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
2343 result
+= m_num_nodes
[i
];
2347 /* struct per_function_data. */
2349 per_function_data::~per_function_data ()
2351 for (auto iter
: m_summaries
)
2356 per_function_data::add_call_summary (exploded_node
*node
)
2358 m_summaries
.safe_push (new call_summary (this, node
));
2361 /* strongly_connected_components's ctor. Tarjan's SCC algorithm. */
2363 strongly_connected_components::
2364 strongly_connected_components (const supergraph
&sg
, logger
*logger
)
2365 : m_sg (sg
), m_per_node (m_sg
.num_nodes ())
2368 auto_timevar
tv (TV_ANALYZER_SCC
);
2370 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2371 m_per_node
.quick_push (per_node_data ());
2373 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2374 if (m_per_node
[i
].m_index
== -1)
2381 /* Dump this object to stderr. */
2384 strongly_connected_components::dump () const
2386 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2388 const per_node_data
&v
= m_per_node
[i
];
2389 fprintf (stderr
, "SN %i: index: %i lowlink: %i on_stack: %i\n",
2390 i
, v
.m_index
, v
.m_lowlink
, v
.m_on_stack
);
2394 /* Return a new json::array of per-snode SCC ids. */
2397 strongly_connected_components::to_json () const
2399 json::array
*scc_arr
= new json::array ();
2400 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2401 scc_arr
->append (new json::integer_number (get_scc_id (i
)));
2405 /* Subroutine of strongly_connected_components's ctor, part of Tarjan's
2409 strongly_connected_components::strong_connect (unsigned index
)
2411 supernode
*v_snode
= m_sg
.get_node_by_index (index
);
2413 /* Set the depth index for v to the smallest unused index. */
2414 per_node_data
*v
= &m_per_node
[index
];
2416 v
->m_lowlink
= index
;
2417 m_stack
.safe_push (index
);
2418 v
->m_on_stack
= true;
2421 /* Consider successors of v. */
2424 FOR_EACH_VEC_ELT (v_snode
->m_succs
, i
, sedge
)
2426 if (sedge
->get_kind () != SUPEREDGE_CFG_EDGE
2427 && sedge
->get_kind () != SUPEREDGE_INTRAPROCEDURAL_CALL
)
2429 supernode
*w_snode
= sedge
->m_dest
;
2430 per_node_data
*w
= &m_per_node
[w_snode
->m_index
];
2431 if (w
->m_index
== -1)
2433 /* Successor w has not yet been visited; recurse on it. */
2434 strong_connect (w_snode
->m_index
);
2435 v
->m_lowlink
= MIN (v
->m_lowlink
, w
->m_lowlink
);
2437 else if (w
->m_on_stack
)
2439 /* Successor w is in stack S and hence in the current SCC
2440 If w is not on stack, then (v, w) is a cross-edge in the DFS
2441 tree and must be ignored. */
2442 v
->m_lowlink
= MIN (v
->m_lowlink
, w
->m_index
);
2446 /* If v is a root node, pop the stack and generate an SCC. */
2448 if (v
->m_lowlink
== v
->m_index
)
2452 int idx
= m_stack
.pop ();
2453 w
= &m_per_node
[idx
];
2454 w
->m_on_stack
= false;
2459 /* worklist's ctor. */
2461 worklist::worklist (const exploded_graph
&eg
, const analysis_plan
&plan
)
2462 : m_scc (eg
.get_supergraph (), eg
.get_logger ()),
2464 m_queue (key_t (*this, NULL
))
2468 /* Return the number of nodes in the worklist. */
2471 worklist::length () const
2473 return m_queue
.nodes ();
2476 /* Return the next node in the worklist, removing it. */
2479 worklist::take_next ()
2481 return m_queue
.extract_min ();
2484 /* Return the next node in the worklist without removing it. */
2487 worklist::peek_next ()
2489 return m_queue
.min ();
2492 /* Add ENODE to the worklist. */
2495 worklist::add_node (exploded_node
*enode
)
2497 gcc_assert (enode
->get_status () == exploded_node::STATUS_WORKLIST
);
2498 m_queue
.insert (key_t (*this, enode
), enode
);
2501 /* Comparator for implementing worklist::key_t comparison operators.
2502 Return negative if KA is before KB
2503 Return positive if KA is after KB
2504 Return 0 if they are equal.
2506 The ordering of the worklist is critical for performance and for
2507 avoiding node explosions. Ideally we want all enodes at a CFG join-point
2508 with the same callstring to be sorted next to each other in the worklist
2509 so that a run of consecutive enodes can be merged and processed "in bulk"
2510 rather than individually or pairwise, minimizing the number of new enodes
2514 worklist::key_t::cmp (const worklist::key_t
&ka
, const worklist::key_t
&kb
)
2516 const program_point
&point_a
= ka
.m_enode
->get_point ();
2517 const program_point
&point_b
= kb
.m_enode
->get_point ();
2518 const call_string
&call_string_a
= point_a
.get_call_string ();
2519 const call_string
&call_string_b
= point_b
.get_call_string ();
2521 /* Order empty-callstring points with different functions based on the
2522 analysis_plan, so that we generate summaries before they are used. */
2523 if (flag_analyzer_call_summaries
2524 && call_string_a
.empty_p ()
2525 && call_string_b
.empty_p ()
2526 && point_a
.get_function () != NULL
2527 && point_b
.get_function () != NULL
2528 && point_a
.get_function () != point_b
.get_function ())
2530 if (int cmp
= ka
.m_worklist
.m_plan
.cmp_function (point_a
.get_function (),
2531 point_b
.get_function ()))
2535 /* Sort by callstring, so that nodes with deeper call strings are processed
2536 before those with shallower call strings.
2545 then we want the path inside the function call to be fully explored up
2546 to the return to the join BB before we explore on the "no fn call" path,
2547 so that both enodes at the join BB reach the front of the worklist at
2548 the same time and thus have a chance of being merged. */
2549 int cs_cmp
= call_string::cmp (call_string_a
, call_string_b
);
2554 int scc_id_a
= ka
.get_scc_id (ka
.m_enode
);
2555 int scc_id_b
= kb
.get_scc_id (kb
.m_enode
);
2556 if (scc_id_a
!= scc_id_b
)
2557 return scc_id_a
- scc_id_b
;
2559 /* If in same SCC, order by supernode index (an arbitrary but stable
2561 const supernode
*snode_a
= ka
.m_enode
->get_supernode ();
2562 const supernode
*snode_b
= kb
.m_enode
->get_supernode ();
2563 if (snode_a
== NULL
)
2565 if (snode_b
!= NULL
)
2569 /* Both are NULL. */
2572 if (snode_b
== NULL
)
2575 /* Neither are NULL. */
2576 gcc_assert (snode_a
&& snode_b
);
2577 if (snode_a
->m_index
!= snode_b
->m_index
)
2578 return snode_a
->m_index
- snode_b
->m_index
;
2580 gcc_assert (snode_a
== snode_b
);
2582 /* Order within supernode via program point. */
2583 int within_snode_cmp
2584 = function_point::cmp_within_supernode (point_a
.get_function_point (),
2585 point_b
.get_function_point ());
2586 if (within_snode_cmp
)
2587 return within_snode_cmp
;
2589 /* Otherwise, we ought to have the same program_point. */
2590 gcc_assert (point_a
== point_b
);
2592 const program_state
&state_a
= ka
.m_enode
->get_state ();
2593 const program_state
&state_b
= kb
.m_enode
->get_state ();
2595 /* Sort by sm-state, so that identical sm-states are grouped
2596 together in the worklist. */
2597 for (unsigned sm_idx
= 0; sm_idx
< state_a
.m_checker_states
.length ();
2600 sm_state_map
*smap_a
= state_a
.m_checker_states
[sm_idx
];
2601 sm_state_map
*smap_b
= state_b
.m_checker_states
[sm_idx
];
2603 if (int smap_cmp
= sm_state_map::cmp (*smap_a
, *smap_b
))
2607 /* Otherwise, we have two enodes at the same program point but with
2608 different states. We don't have a good total ordering on states,
2609 so order them by enode index, so that we have at least have a
2611 return ka
.m_enode
->m_index
- kb
.m_enode
->m_index
;
2614 /* Return a new json::object of the form
2615 {"scc" : [per-snode-IDs]}, */
2618 worklist::to_json () const
2620 json::object
*worklist_obj
= new json::object ();
2622 worklist_obj
->set ("scc", m_scc
.to_json ());
2624 /* The following field isn't yet being JSONified:
2627 return worklist_obj
;
2630 /* exploded_graph's ctor. */
2632 exploded_graph::exploded_graph (const supergraph
&sg
, logger
*logger
,
2633 const extrinsic_state
&ext_state
,
2634 const state_purge_map
*purge_map
,
2635 const analysis_plan
&plan
,
2637 : m_sg (sg
), m_logger (logger
),
2638 m_worklist (*this, plan
),
2639 m_ext_state (ext_state
),
2640 m_purge_map (purge_map
),
2642 m_diagnostic_manager (logger
, ext_state
.get_engine (), verbosity
),
2643 m_global_stats (m_sg
.num_nodes ()),
2644 m_functionless_stats (m_sg
.num_nodes ()),
2645 m_PK_AFTER_SUPERNODE_per_snode (m_sg
.num_nodes ())
2647 m_origin
= get_or_create_node
2648 (program_point::origin (*ext_state
.get_model_manager ()),
2649 program_state (ext_state
), NULL
);
2650 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2651 m_PK_AFTER_SUPERNODE_per_snode
.quick_push (i
);
2654 /* exploded_graph's dtor. */
2656 exploded_graph::~exploded_graph ()
2658 for (auto iter
: m_per_point_data
)
2660 for (auto iter
: m_per_function_data
)
2662 for (auto iter
: m_per_function_stats
)
2664 for (auto iter
: m_per_call_string_data
)
2668 /* Subroutine for use when implementing __attribute__((tainted_args))
2669 on functions and on function pointer fields in structs.
2671 Called on STATE representing a call to FNDECL.
2672 Mark all params of FNDECL in STATE as "tainted". Mark the value of all
2673 regions pointed to by params of FNDECL as "tainted".
2675 Return true if successful; return false if the "taint" state machine
2679 mark_params_as_tainted (program_state
*state
, tree fndecl
,
2680 const extrinsic_state
&ext_state
)
2682 unsigned taint_sm_idx
;
2683 if (!ext_state
.get_sm_idx_by_name ("taint", &taint_sm_idx
))
2685 sm_state_map
*smap
= state
->m_checker_states
[taint_sm_idx
];
2687 const state_machine
&sm
= ext_state
.get_sm (taint_sm_idx
);
2688 state_machine::state_t tainted
= sm
.get_state_by_name ("tainted");
2690 region_model_manager
*mgr
= ext_state
.get_model_manager ();
2692 function
*fun
= DECL_STRUCT_FUNCTION (fndecl
);
2695 for (tree iter_parm
= DECL_ARGUMENTS (fndecl
); iter_parm
;
2696 iter_parm
= DECL_CHAIN (iter_parm
))
2698 tree param
= iter_parm
;
2699 if (tree parm_default_ssa
= ssa_default_def (fun
, iter_parm
))
2700 param
= parm_default_ssa
;
2701 const region
*param_reg
= state
->m_region_model
->get_lvalue (param
, NULL
);
2702 const svalue
*init_sval
= mgr
->get_or_create_initial_value (param_reg
);
2703 smap
->set_state (state
->m_region_model
, init_sval
,
2704 tainted
, NULL
/*origin_new_sval*/, ext_state
);
2705 if (POINTER_TYPE_P (TREE_TYPE (param
)))
2707 const region
*pointee_reg
= mgr
->get_symbolic_region (init_sval
);
2708 /* Mark "*param" as tainted. */
2709 const svalue
*init_pointee_sval
2710 = mgr
->get_or_create_initial_value (pointee_reg
);
2711 smap
->set_state (state
->m_region_model
, init_pointee_sval
,
2712 tainted
, NULL
/*origin_new_sval*/, ext_state
);
2719 /* Custom event for use by tainted_args_function_info when a function
2720 has been marked with __attribute__((tainted_args)). */
2722 class tainted_args_function_custom_event
: public custom_event
2725 tainted_args_function_custom_event (const event_loc_info
&loc_info
)
2726 : custom_event (loc_info
),
2727 m_fndecl (loc_info
.m_fndecl
)
2731 label_text
get_desc (bool can_colorize
) const final override
2733 return make_label_text
2735 "function %qE marked with %<__attribute__((tainted_args))%>",
2743 /* Custom exploded_edge info for top-level calls to a function
2744 marked with __attribute__((tainted_args)). */
2746 class tainted_args_function_info
: public custom_edge_info
2749 tainted_args_function_info (tree fndecl
)
2753 void print (pretty_printer
*pp
) const final override
2755 pp_string (pp
, "call to tainted_args function");
2758 bool update_model (region_model
*,
2759 const exploded_edge
*,
2760 region_model_context
*) const final override
2766 void add_events_to_path (checker_path
*emission_path
,
2767 const exploded_edge
&) const final override
2769 emission_path
->add_event
2770 (make_unique
<tainted_args_function_custom_event
>
2771 (event_loc_info (DECL_SOURCE_LOCATION (m_fndecl
), m_fndecl
, 0)));
2778 /* Ensure that there is an exploded_node representing an external call to
2779 FUN, adding it to the worklist if creating it.
2781 Add an edge from the origin exploded_node to the function entrypoint
2784 Return the exploded_node for the entrypoint to the function. */
2787 exploded_graph::add_function_entry (function
*fun
)
2789 gcc_assert (gimple_has_body_p (fun
->decl
));
2791 /* Be idempotent. */
2792 if (m_functions_with_enodes
.contains (fun
))
2794 logger
* const logger
= get_logger ();
2796 logger
->log ("entrypoint for %qE already exists", fun
->decl
);
2801 = program_point::from_function_entry (*m_ext_state
.get_model_manager (),
2803 program_state
state (m_ext_state
);
2804 state
.push_frame (m_ext_state
, fun
);
2806 std::unique_ptr
<custom_edge_info
> edge_info
= NULL
;
2808 if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (fun
->decl
)))
2810 if (mark_params_as_tainted (&state
, fun
->decl
, m_ext_state
))
2811 edge_info
= make_unique
<tainted_args_function_info
> (fun
->decl
);
2817 exploded_node
*enode
= get_or_create_node (point
, state
, NULL
);
2821 add_edge (m_origin
, enode
, NULL
, false, std::move (edge_info
));
2823 m_functions_with_enodes
.add (fun
);
2828 /* Get or create an exploded_node for (POINT, STATE).
2829 If a new node is created, it is added to the worklist.
2831 Use ENODE_FOR_DIAG, a pre-existing enode, for any diagnostics
2832 that need to be emitted (e.g. when purging state *before* we have
2836 exploded_graph::get_or_create_node (const program_point
&point
,
2837 const program_state
&state
,
2838 exploded_node
*enode_for_diag
)
2840 logger
* const logger
= get_logger ();
2845 pretty_printer
*pp
= logger
->get_printer ();
2846 logger
->start_log_line ();
2847 pp_string (pp
, "point: ");
2848 point
.print (pp
, f
);
2849 logger
->end_log_line ();
2850 logger
->start_log_line ();
2851 pp_string (pp
, "state: ");
2852 state
.dump_to_pp (m_ext_state
, true, false, pp
);
2853 logger
->end_log_line ();
2856 /* Stop exploring paths for which we don't know how to effectively
2861 logger
->log ("invalid state; not creating node");
2865 auto_cfun
sentinel (point
.get_function ());
2867 state
.validate (get_ext_state ());
2869 //state.dump (get_ext_state ());
2871 /* Prune state to try to improve the chances of a cache hit,
2872 avoiding generating redundant nodes. */
2873 uncertainty_t uncertainty
;
2874 program_state pruned_state
2875 = state
.prune_for_point (*this, point
, enode_for_diag
, &uncertainty
);
2877 pruned_state
.validate (get_ext_state ());
2879 //pruned_state.dump (get_ext_state ());
2883 pretty_printer
*pp
= logger
->get_printer ();
2884 logger
->start_log_line ();
2885 pp_string (pp
, "pruned_state: ");
2886 pruned_state
.dump_to_pp (m_ext_state
, true, false, pp
);
2887 logger
->end_log_line ();
2888 pruned_state
.m_region_model
->dump_to_pp (logger
->get_printer (), true,
2892 stats
*per_fn_stats
= get_or_create_function_stats (point
.get_function ());
2895 = &get_or_create_per_call_string_data (point
.get_call_string ())->m_stats
;
2897 point_and_state
ps (point
, pruned_state
);
2898 ps
.validate (m_ext_state
);
2899 if (exploded_node
**slot
= m_point_and_state_to_node
.get (&ps
))
2901 /* An exploded_node for PS already exists. */
2903 logger
->log ("reused EN: %i", (*slot
)->m_index
);
2904 m_global_stats
.m_node_reuse_count
++;
2905 per_fn_stats
->m_node_reuse_count
++;
2906 per_cs_stats
->m_node_reuse_count
++;
2910 per_program_point_data
*per_point_data
2911 = get_or_create_per_program_point_data (point
);
2913 /* Consider merging state with another enode at this program_point. */
2914 if (flag_analyzer_state_merge
)
2916 exploded_node
*existing_enode
;
2918 FOR_EACH_VEC_ELT (per_point_data
->m_enodes
, i
, existing_enode
)
2921 logger
->log ("considering merging with existing EN: %i for point",
2922 existing_enode
->m_index
);
2923 gcc_assert (existing_enode
->get_point () == point
);
2924 const program_state
&existing_state
= existing_enode
->get_state ();
2926 /* This merges successfully within the loop. */
2928 program_state
merged_state (m_ext_state
);
2929 if (pruned_state
.can_merge_with_p (existing_state
, m_ext_state
, point
,
2932 merged_state
.validate (m_ext_state
);
2934 logger
->log ("merging new state with that of EN: %i",
2935 existing_enode
->m_index
);
2937 /* Try again for a cache hit.
2938 Whether we get one or not, merged_state's value_ids have no
2939 relationship to those of the input state, and thus to those
2940 of CHANGE, so we must purge any svalue_ids from *CHANGE. */
2941 ps
.set_state (merged_state
);
2943 if (exploded_node
**slot
= m_point_and_state_to_node
.get (&ps
))
2945 /* An exploded_node for PS already exists. */
2947 logger
->log ("reused EN: %i", (*slot
)->m_index
);
2948 m_global_stats
.m_node_reuse_after_merge_count
++;
2949 per_fn_stats
->m_node_reuse_after_merge_count
++;
2950 per_cs_stats
->m_node_reuse_after_merge_count
++;
2956 logger
->log ("not merging new state with that of EN: %i",
2957 existing_enode
->m_index
);
2961 /* Impose a limit on the number of enodes per program point, and
2962 simply stop if we exceed it. */
2963 if ((int)per_point_data
->m_enodes
.length ()
2964 >= param_analyzer_max_enodes_per_program_point
)
2967 point
.print (&pp
, format (false));
2968 print_enode_indices (&pp
, per_point_data
->m_enodes
);
2970 logger
->log ("not creating enode; too many at program point: %s",
2971 pp_formatted_text (&pp
));
2972 warning_at (point
.get_location (), OPT_Wanalyzer_too_complex
,
2973 "terminating analysis for this program point: %s",
2974 pp_formatted_text (&pp
));
2975 per_point_data
->m_excess_enodes
++;
2979 ps
.validate (m_ext_state
);
2981 /* An exploded_node for "ps" doesn't already exist; create one. */
2982 exploded_node
*node
= new exploded_node (ps
, m_nodes
.length ());
2984 m_point_and_state_to_node
.put (node
->get_ps_key (), node
);
2986 /* Update per-program_point data. */
2987 per_point_data
->m_enodes
.safe_push (node
);
2989 const enum point_kind node_pk
= node
->get_point ().get_kind ();
2990 m_global_stats
.m_num_nodes
[node_pk
]++;
2991 per_fn_stats
->m_num_nodes
[node_pk
]++;
2992 per_cs_stats
->m_num_nodes
[node_pk
]++;
2994 if (node_pk
== PK_AFTER_SUPERNODE
)
2995 m_PK_AFTER_SUPERNODE_per_snode
[point
.get_supernode ()->m_index
]++;
3000 pretty_printer
*pp
= logger
->get_printer ();
3001 logger
->log ("created EN: %i", node
->m_index
);
3002 logger
->start_log_line ();
3003 pp_string (pp
, "point: ");
3004 point
.print (pp
, f
);
3005 logger
->end_log_line ();
3006 logger
->start_log_line ();
3007 pp_string (pp
, "pruned_state: ");
3008 pruned_state
.dump_to_pp (m_ext_state
, true, false, pp
);
3009 logger
->end_log_line ();
3012 /* Add the new node to the worlist. */
3013 m_worklist
.add_node (node
);
3017 /* Add an exploded_edge from SRC to DEST, recording its association
3018 with SEDGE (which may be NULL), and, if non-NULL, taking ownership
3019 of CUSTOM_INFO. COULD_DO_WORK is used for detecting infinite loops.
3020 Return the newly-created eedge. */
3023 exploded_graph::add_edge (exploded_node
*src
, exploded_node
*dest
,
3024 const superedge
*sedge
, bool could_do_work
,
3025 std::unique_ptr
<custom_edge_info
> custom_info
)
3028 get_logger ()->log ("creating edge EN: %i -> EN: %i",
3029 src
->m_index
, dest
->m_index
);
3031 = new exploded_edge (src
, dest
, sedge
, could_do_work
,
3032 std::move (custom_info
));
3033 digraph
<eg_traits
>::add_edge (e
);
3037 /* Ensure that this graph has per-program_point-data for POINT;
3038 borrow a pointer to it. */
3040 per_program_point_data
*
3042 get_or_create_per_program_point_data (const program_point
&point
)
3044 if (per_program_point_data
**slot
= m_per_point_data
.get (&point
))
3047 per_program_point_data
*per_point_data
= new per_program_point_data (point
);
3048 m_per_point_data
.put (&per_point_data
->m_key
, per_point_data
);
3049 return per_point_data
;
3052 /* Get this graph's per-program-point-data for POINT if there is any,
3055 per_program_point_data
*
3056 exploded_graph::get_per_program_point_data (const program_point
&point
) const
3058 if (per_program_point_data
**slot
3059 = const_cast <point_map_t
&> (m_per_point_data
).get (&point
))
3065 /* Ensure that this graph has per-call_string-data for CS;
3066 borrow a pointer to it. */
3068 per_call_string_data
*
3069 exploded_graph::get_or_create_per_call_string_data (const call_string
&cs
)
3071 if (per_call_string_data
**slot
= m_per_call_string_data
.get (&cs
))
3074 per_call_string_data
*data
= new per_call_string_data (cs
, m_sg
.num_nodes ());
3075 m_per_call_string_data
.put (&data
->m_key
,
3080 /* Ensure that this graph has per-function-data for FUN;
3081 borrow a pointer to it. */
3084 exploded_graph::get_or_create_per_function_data (function
*fun
)
3086 if (per_function_data
**slot
= m_per_function_data
.get (fun
))
3089 per_function_data
*data
= new per_function_data ();
3090 m_per_function_data
.put (fun
, data
);
3094 /* Get this graph's per-function-data for FUN if there is any,
3098 exploded_graph::get_per_function_data (function
*fun
) const
3100 if (per_function_data
**slot
3101 = const_cast <per_function_data_t
&> (m_per_function_data
).get (fun
))
3107 /* Return true if FUN should be traversed directly, rather than only as
3108 called via other functions. */
3111 toplevel_function_p (function
*fun
, logger
*logger
)
3113 /* Don't directly traverse into functions that have an "__analyzer_"
3114 prefix. Doing so is useful for the analyzer test suite, allowing
3115 us to have functions that are called in traversals, but not directly
3116 explored, thus testing how the analyzer handles calls and returns.
3117 With this, we can have DejaGnu directives that cover just the case
3118 of where a function is called by another function, without generating
3119 excess messages from the case of the first function being traversed
3121 #define ANALYZER_PREFIX "__analyzer_"
3122 if (!strncmp (IDENTIFIER_POINTER (DECL_NAME (fun
->decl
)), ANALYZER_PREFIX
,
3123 strlen (ANALYZER_PREFIX
)))
3126 logger
->log ("not traversing %qE (starts with %qs)",
3127 fun
->decl
, ANALYZER_PREFIX
);
3132 logger
->log ("traversing %qE (all checks passed)", fun
->decl
);
3137 /* Custom event for use by tainted_call_info when a callback field has been
3138 marked with __attribute__((tainted_args)), for labelling the field. */
3140 class tainted_args_field_custom_event
: public custom_event
3143 tainted_args_field_custom_event (tree field
)
3144 : custom_event (event_loc_info (DECL_SOURCE_LOCATION (field
), NULL_TREE
, 0)),
3149 label_text
get_desc (bool can_colorize
) const final override
3151 return make_label_text (can_colorize
,
3153 " is marked with %<__attribute__((tainted_args))%>",
3154 m_field
, DECL_CONTEXT (m_field
));
3161 /* Custom event for use by tainted_call_info when a callback field has been
3162 marked with __attribute__((tainted_args)), for labelling the function used
3163 in that callback. */
3165 class tainted_args_callback_custom_event
: public custom_event
3168 tainted_args_callback_custom_event (const event_loc_info
&loc_info
,
3170 : custom_event (loc_info
),
3175 label_text
get_desc (bool can_colorize
) const final override
3177 return make_label_text (can_colorize
,
3178 "function %qE used as initializer for field %qE"
3179 " marked with %<__attribute__((tainted_args))%>",
3180 get_fndecl (), m_field
);
3187 /* Custom edge info for use when adding a function used by a callback field
3188 marked with '__attribute__((tainted_args))'. */
3190 class tainted_args_call_info
: public custom_edge_info
3193 tainted_args_call_info (tree field
, tree fndecl
, location_t loc
)
3194 : m_field (field
), m_fndecl (fndecl
), m_loc (loc
)
3197 void print (pretty_printer
*pp
) const final override
3199 pp_string (pp
, "call to tainted field");
3202 bool update_model (region_model
*,
3203 const exploded_edge
*,
3204 region_model_context
*) const final override
3210 void add_events_to_path (checker_path
*emission_path
,
3211 const exploded_edge
&) const final override
3213 /* Show the field in the struct declaration, e.g.
3214 "(1) field 'store' is marked with '__attribute__((tainted_args))'" */
3215 emission_path
->add_event
3216 (make_unique
<tainted_args_field_custom_event
> (m_field
));
3218 /* Show the callback in the initializer
3220 "(2) function 'gadget_dev_desc_UDC_store' used as initializer
3221 for field 'store' marked with '__attribute__((tainted_args))'". */
3222 emission_path
->add_event
3223 (make_unique
<tainted_args_callback_custom_event
>
3224 (event_loc_info (m_loc
, m_fndecl
, 0),
3234 /* Given an initializer at LOC for FIELD marked with
3235 '__attribute__((tainted_args))' initialized with FNDECL, add an
3236 entrypoint to FNDECL to EG (and to its worklist) where the params to
3237 FNDECL are marked as tainted. */
3240 add_tainted_args_callback (exploded_graph
*eg
, tree field
, tree fndecl
,
3243 logger
*logger
= eg
->get_logger ();
3247 if (!gimple_has_body_p (fndecl
))
3250 const extrinsic_state
&ext_state
= eg
->get_ext_state ();
3252 function
*fun
= DECL_STRUCT_FUNCTION (fndecl
);
3256 = program_point::from_function_entry (*ext_state
.get_model_manager (),
3257 eg
->get_supergraph (), fun
);
3258 program_state
state (ext_state
);
3259 state
.push_frame (ext_state
, fun
);
3261 if (!mark_params_as_tainted (&state
, fndecl
, ext_state
))
3267 exploded_node
*enode
= eg
->get_or_create_node (point
, state
, NULL
);
3271 logger
->log ("created EN %i for tainted_args %qE entrypoint",
3272 enode
->m_index
, fndecl
);
3275 logger
->log ("did not create enode for tainted_args %qE entrypoint",
3281 eg
->add_edge (eg
->get_origin (), enode
, NULL
, false,
3282 make_unique
<tainted_args_call_info
> (field
, fndecl
, loc
));
3285 /* Callback for walk_tree for finding callbacks within initializers;
3286 ensure that any callback initializer where the corresponding field is
3287 marked with '__attribute__((tainted_args))' is treated as an entrypoint
3288 to the analysis, special-casing that the inputs to the callback are
3292 add_any_callbacks (tree
*tp
, int *, void *data
)
3294 exploded_graph
*eg
= (exploded_graph
*)data
;
3295 if (TREE_CODE (*tp
) == CONSTRUCTOR
)
3297 /* Find fields with the "tainted_args" attribute.
3298 walk_tree only walks the values, not the index values;
3299 look at the index values. */
3300 unsigned HOST_WIDE_INT idx
;
3301 constructor_elt
*ce
;
3303 for (idx
= 0; vec_safe_iterate (CONSTRUCTOR_ELTS (*tp
), idx
, &ce
);
3305 if (ce
->index
&& TREE_CODE (ce
->index
) == FIELD_DECL
)
3306 if (lookup_attribute ("tainted_args", DECL_ATTRIBUTES (ce
->index
)))
3308 tree value
= ce
->value
;
3309 if (TREE_CODE (value
) == ADDR_EXPR
3310 && TREE_CODE (TREE_OPERAND (value
, 0)) == FUNCTION_DECL
)
3311 add_tainted_args_callback (eg
, ce
->index
,
3312 TREE_OPERAND (value
, 0),
3313 EXPR_LOCATION (value
));
3320 /* Add initial nodes to EG, with entrypoints for externally-callable
3324 exploded_graph::build_initial_worklist ()
3326 logger
* const logger
= get_logger ();
3330 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
3332 function
*fun
= node
->get_fun ();
3333 if (!toplevel_function_p (fun
, logger
))
3335 exploded_node
*enode
= add_function_entry (fun
);
3339 logger
->log ("created EN %i for %qE entrypoint",
3340 enode
->m_index
, fun
->decl
);
3342 logger
->log ("did not create enode for %qE entrypoint", fun
->decl
);
3346 /* Find callbacks that are reachable from global initializers. */
3347 varpool_node
*vpnode
;
3348 FOR_EACH_VARIABLE (vpnode
)
3350 tree decl
= vpnode
->decl
;
3351 tree init
= DECL_INITIAL (decl
);
3354 walk_tree (&init
, add_any_callbacks
, this, NULL
);
3358 /* The main loop of the analysis.
3359 Take freshly-created exploded_nodes from the worklist, calling
3360 process_node on them to explore the <point, state> graph.
3361 Add edges to their successors, potentially creating new successors
3362 (which are also added to the worklist). */
3365 exploded_graph::process_worklist ()
3367 logger
* const logger
= get_logger ();
3369 auto_timevar
tv (TV_ANALYZER_WORKLIST
);
3371 while (m_worklist
.length () > 0)
3373 exploded_node
*node
= m_worklist
.take_next ();
3374 gcc_assert (node
->get_status () == exploded_node::STATUS_WORKLIST
);
3375 gcc_assert (node
->m_succs
.length () == 0
3376 || node
== m_origin
);
3379 logger
->log ("next to process: EN: %i", node
->m_index
);
3381 /* If we have a run of nodes that are before-supernode, try merging and
3382 processing them together, rather than pairwise or individually. */
3383 if (flag_analyzer_state_merge
&& node
!= m_origin
)
3384 if (maybe_process_run_of_before_supernode_enodes (node
))
3387 /* Avoid exponential explosions of nodes by attempting to merge
3388 nodes that are at the same program point and which have
3389 sufficiently similar state. */
3390 if (flag_analyzer_state_merge
&& node
!= m_origin
)
3391 if (exploded_node
*node_2
= m_worklist
.peek_next ())
3393 gcc_assert (node_2
->get_status ()
3394 == exploded_node::STATUS_WORKLIST
);
3395 gcc_assert (node
->m_succs
.length () == 0);
3396 gcc_assert (node_2
->m_succs
.length () == 0);
3398 gcc_assert (node
!= node_2
);
3401 logger
->log ("peek worklist: EN: %i", node_2
->m_index
);
3403 if (node
->get_point () == node_2
->get_point ())
3405 const program_point
&point
= node
->get_point ();
3409 pretty_printer
*pp
= logger
->get_printer ();
3410 logger
->start_log_line ();
3412 ("got potential merge EN: %i and EN: %i at ",
3413 node
->m_index
, node_2
->m_index
);
3414 point
.print (pp
, f
);
3415 logger
->end_log_line ();
3417 const program_state
&state
= node
->get_state ();
3418 const program_state
&state_2
= node_2
->get_state ();
3420 /* They shouldn't be equal, or we wouldn't have two
3422 gcc_assert (state
!= state_2
);
3424 program_state
merged_state (m_ext_state
);
3425 if (state
.can_merge_with_p (state_2
, m_ext_state
,
3426 point
, &merged_state
))
3429 logger
->log ("merging EN: %i and EN: %i",
3430 node
->m_index
, node_2
->m_index
);
3432 if (merged_state
== state
)
3434 /* Then merge node_2 into node by adding an edge. */
3435 add_edge (node_2
, node
, NULL
, false);
3437 /* Remove node_2 from the worklist. */
3438 m_worklist
.take_next ();
3439 node_2
->set_status (exploded_node::STATUS_MERGER
);
3441 /* Continue processing "node" below. */
3443 else if (merged_state
== state_2
)
3445 /* Then merge node into node_2, and leave node_2
3446 in the worklist, to be processed on the next
3448 add_edge (node
, node_2
, NULL
, false);
3449 node
->set_status (exploded_node::STATUS_MERGER
);
3454 /* We have a merged state that differs from
3455 both state and state_2. */
3457 /* Remove node_2 from the worklist. */
3458 m_worklist
.take_next ();
3460 /* Create (or get) an exploded node for the merged
3461 states, adding to the worklist. */
3462 exploded_node
*merged_enode
3463 = get_or_create_node (node
->get_point (),
3464 merged_state
, node
);
3465 if (merged_enode
== NULL
)
3469 logger
->log ("merged EN: %i and EN: %i into EN: %i",
3470 node
->m_index
, node_2
->m_index
,
3471 merged_enode
->m_index
);
3473 /* "node" and "node_2" have both now been removed
3474 from the worklist; we should not process them.
3476 "merged_enode" may be a new node; if so it will be
3477 processed in a subsequent iteration.
3478 Alternatively, "merged_enode" could be an existing
3479 node; one way the latter can
3480 happen is if we end up merging a succession of
3481 similar nodes into one. */
3483 /* If merged_node is one of the two we were merging,
3484 add it back to the worklist to ensure it gets
3487 Add edges from the merged nodes to it (but not a
3489 if (merged_enode
== node
)
3490 m_worklist
.add_node (merged_enode
);
3493 add_edge (node
, merged_enode
, NULL
, false);
3494 node
->set_status (exploded_node::STATUS_MERGER
);
3497 if (merged_enode
== node_2
)
3498 m_worklist
.add_node (merged_enode
);
3501 add_edge (node_2
, merged_enode
, NULL
, false);
3502 node_2
->set_status (exploded_node::STATUS_MERGER
);
3509 /* TODO: should we attempt more than two nodes,
3510 or just do pairs of nodes? (and hope that we get
3511 a cascade of mergers). */
3515 process_node (node
);
3518 /* Impose a hard limit on the number of exploded nodes, to ensure
3519 that the analysis terminates in the face of pathological state
3520 explosion (or bugs).
3522 Specifically, the limit is on the number of PK_AFTER_SUPERNODE
3523 exploded nodes, looking at supernode exit events.
3525 We use exit rather than entry since there can be multiple
3526 entry ENs, one per phi; the number of PK_AFTER_SUPERNODE ought
3527 to be equivalent to the number of supernodes multiplied by the
3528 number of states. */
3529 const int limit
= m_sg
.num_nodes () * param_analyzer_bb_explosion_factor
;
3530 if (m_global_stats
.m_num_nodes
[PK_AFTER_SUPERNODE
] > limit
)
3533 logger
->log ("bailing out; too many nodes");
3534 warning_at (node
->get_point ().get_location (),
3535 OPT_Wanalyzer_too_complex
,
3536 "analysis bailed out early"
3537 " (%i 'after-snode' enodes; %i enodes)",
3538 m_global_stats
.m_num_nodes
[PK_AFTER_SUPERNODE
],
3545 /* Attempt to process a consecutive run of sufficiently-similar nodes in
3546 the worklist at a CFG join-point (having already popped ENODE from the
3547 head of the worklist).
3549 If ENODE's point is of the form (before-supernode, SNODE) and the next
3550 nodes in the worklist are a consecutive run of enodes of the same form,
3551 for the same supernode as ENODE (but potentially from different in-edges),
3552 process them all together, setting their status to STATUS_BULK_MERGED,
3554 Otherwise, return false, in which case ENODE must be processed in the
3557 When processing them all together, generate successor states based
3558 on phi nodes for the appropriate CFG edges, and then attempt to merge
3559 these states into a minimal set of merged successor states, partitioning
3560 the inputs by merged successor state.
3562 Create new exploded nodes for all of the merged states, and add edges
3563 connecting the input enodes to the corresponding merger exploded nodes.
3565 We hope we have a much smaller number of merged successor states
3566 compared to the number of input enodes - ideally just one,
3567 if all successor states can be merged.
3569 Processing and merging many together as one operation rather than as
3570 pairs avoids scaling issues where per-pair mergers could bloat the
3571 graph with merger nodes (especially so after switch statements). */
3575 maybe_process_run_of_before_supernode_enodes (exploded_node
*enode
)
3577 /* A struct for tracking per-input state. */
3580 item (exploded_node
*input_enode
)
3581 : m_input_enode (input_enode
),
3582 m_processed_state (input_enode
->get_state ()),
3586 exploded_node
*m_input_enode
;
3587 program_state m_processed_state
;
3591 gcc_assert (enode
->get_status () == exploded_node::STATUS_WORKLIST
);
3592 gcc_assert (enode
->m_succs
.length () == 0);
3594 const program_point
&point
= enode
->get_point ();
3596 if (point
.get_kind () != PK_BEFORE_SUPERNODE
)
3599 const supernode
*snode
= point
.get_supernode ();
3601 logger
* const logger
= get_logger ();
3604 /* Find a run of enodes in the worklist that are before the same supernode,
3605 but potentially from different in-edges. */
3606 auto_vec
<exploded_node
*> enodes
;
3607 enodes
.safe_push (enode
);
3608 while (exploded_node
*enode_2
= m_worklist
.peek_next ())
3610 gcc_assert (enode_2
->get_status ()
3611 == exploded_node::STATUS_WORKLIST
);
3612 gcc_assert (enode_2
->m_succs
.length () == 0);
3614 const program_point
&point_2
= enode_2
->get_point ();
3616 if (point_2
.get_kind () == PK_BEFORE_SUPERNODE
3617 && point_2
.get_supernode () == snode
3618 && &point_2
.get_call_string () == &point
.get_call_string ())
3620 enodes
.safe_push (enode_2
);
3621 m_worklist
.take_next ();
3627 /* If the only node is ENODE, then give up. */
3628 if (enodes
.length () == 1)
3632 logger
->log ("got run of %i enodes for SN: %i",
3633 enodes
.length (), snode
->m_index
);
3635 /* All of these enodes have a shared successor point (even if they
3636 were for different in-edges). */
3637 program_point
next_point (point
.get_next ());
3639 /* Calculate the successor state for each enode in enodes. */
3640 auto_delete_vec
<item
> items (enodes
.length ());
3642 exploded_node
*iter_enode
;
3643 FOR_EACH_VEC_ELT (enodes
, i
, iter_enode
)
3645 item
*it
= new item (iter_enode
);
3646 items
.quick_push (it
);
3647 const program_state
&state
= iter_enode
->get_state ();
3648 program_state
*next_state
= &it
->m_processed_state
;
3649 next_state
->validate (m_ext_state
);
3650 const program_point
&iter_point
= iter_enode
->get_point ();
3651 if (const superedge
*iter_sedge
= iter_point
.get_from_edge ())
3653 uncertainty_t uncertainty
;
3654 impl_region_model_context
ctxt (*this, iter_enode
,
3656 &uncertainty
, NULL
, NULL
);
3657 const cfg_superedge
*last_cfg_superedge
3658 = iter_sedge
->dyn_cast_cfg_superedge ();
3659 if (last_cfg_superedge
)
3660 next_state
->m_region_model
->update_for_phis
3661 (snode
, last_cfg_superedge
, &ctxt
);
3663 next_state
->validate (m_ext_state
);
3666 /* Attempt to partition the items into a set of merged states.
3667 We hope we have a much smaller number of merged states
3668 compared to the number of input enodes - ideally just one,
3669 if all can be merged. */
3670 auto_delete_vec
<program_state
> merged_states
;
3671 auto_vec
<item
*> first_item_for_each_merged_state
;
3673 FOR_EACH_VEC_ELT (items
, i
, it
)
3675 const program_state
&it_state
= it
->m_processed_state
;
3676 program_state
*merged_state
;
3677 unsigned iter_merger_idx
;
3678 FOR_EACH_VEC_ELT (merged_states
, iter_merger_idx
, merged_state
)
3680 merged_state
->validate (m_ext_state
);
3681 program_state
merge (m_ext_state
);
3682 if (it_state
.can_merge_with_p (*merged_state
, m_ext_state
,
3683 next_point
, &merge
))
3685 *merged_state
= merge
;
3686 merged_state
->validate (m_ext_state
);
3687 it
->m_merger_idx
= iter_merger_idx
;
3689 logger
->log ("reusing merger state %i for item %i (EN: %i)",
3690 it
->m_merger_idx
, i
, it
->m_input_enode
->m_index
);
3694 /* If it couldn't be merged with any existing merged_states,
3695 create a new one. */
3696 if (it
->m_merger_idx
== -1)
3698 it
->m_merger_idx
= merged_states
.length ();
3699 merged_states
.safe_push (new program_state (it_state
));
3700 first_item_for_each_merged_state
.safe_push (it
);
3702 logger
->log ("using new merger state %i for item %i (EN: %i)",
3703 it
->m_merger_idx
, i
, it
->m_input_enode
->m_index
);
3706 gcc_assert (it
->m_merger_idx
>= 0);
3707 gcc_assert ((unsigned)it
->m_merger_idx
< merged_states
.length ());
3710 /* Create merger nodes. */
3711 auto_vec
<exploded_node
*> next_enodes (merged_states
.length ());
3712 program_state
*merged_state
;
3713 FOR_EACH_VEC_ELT (merged_states
, i
, merged_state
)
3715 exploded_node
*src_enode
3716 = first_item_for_each_merged_state
[i
]->m_input_enode
;
3718 = get_or_create_node (next_point
, *merged_state
, src_enode
);
3719 /* "next" could be NULL; we handle that when adding the edges below. */
3720 next_enodes
.quick_push (next
);
3724 logger
->log ("using EN: %i for merger state %i", next
->m_index
, i
);
3726 logger
->log ("using NULL enode for merger state %i", i
);
3730 /* Create edges from each input enode to the appropriate successor enode.
3731 Update the status of the now-processed input enodes. */
3732 FOR_EACH_VEC_ELT (items
, i
, it
)
3734 exploded_node
*next
= next_enodes
[it
->m_merger_idx
];
3736 add_edge (it
->m_input_enode
, next
, NULL
,
3737 false); /* no "work" is done during merger. */
3738 it
->m_input_enode
->set_status (exploded_node::STATUS_BULK_MERGED
);
3742 logger
->log ("merged %i in-enodes into %i out-enode(s) at SN: %i",
3743 items
.length (), merged_states
.length (), snode
->m_index
);
3748 /* Return true if STMT must appear at the start of its exploded node, and
3749 thus we can't consolidate its effects within a run of other statements,
3750 where PREV_STMT was the previous statement. */
3753 stmt_requires_new_enode_p (const gimple
*stmt
,
3754 const gimple
*prev_stmt
)
3756 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
3758 /* Stop consolidating at calls to
3759 "__analyzer_dump_exploded_nodes", so they always appear at the
3760 start of an exploded_node. */
3761 if (is_special_named_call_p (call
, "__analyzer_dump_exploded_nodes",
3765 /* sm-signal.cc injects an additional custom eedge at "signal" calls
3766 from the registration enode to the handler enode, separate from the
3767 regular next state, which defeats the "detect state change" logic
3768 in process_node. Work around this via special-casing, to ensure
3769 we split the enode immediately before any "signal" call. */
3770 if (is_special_named_call_p (call
, "signal", 2))
3774 /* If we had a PREV_STMT with an unknown location, and this stmt
3775 has a known location, then if a state change happens here, it
3776 could be consolidated into PREV_STMT, giving us an event with
3777 no location. Ensure that STMT gets its own exploded_node to
3779 if (get_pure_location (prev_stmt
->location
) == UNKNOWN_LOCATION
3780 && get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
3786 /* Return true if OLD_STATE and NEW_STATE are sufficiently different that
3787 we should split enodes and create an exploded_edge separating them
3788 (which makes it easier to identify state changes of intereset when
3789 constructing checker_paths). */
3792 state_change_requires_new_enode_p (const program_state
&old_state
,
3793 const program_state
&new_state
)
3795 /* Changes in dynamic extents signify creations of heap/alloca regions
3796 and resizings of heap regions; likely to be of interest in
3797 diagnostic paths. */
3798 if (old_state
.m_region_model
->get_dynamic_extents ()
3799 != new_state
.m_region_model
->get_dynamic_extents ())
3802 /* Changes in sm-state are of interest. */
3805 FOR_EACH_VEC_ELT (old_state
.m_checker_states
, sm_idx
, smap
)
3807 const sm_state_map
*old_smap
= old_state
.m_checker_states
[sm_idx
];
3808 const sm_state_map
*new_smap
= new_state
.m_checker_states
[sm_idx
];
3809 if (*old_smap
!= *new_smap
)
3816 /* Create enodes and eedges for the function calls that doesn't have an
3817 underlying call superedge.
3819 Such case occurs when GCC's middle end didn't know which function to
3820 call but the analyzer does (with the help of current state).
3822 Some example such calls are dynamically dispatched calls to virtual
3823 functions or calls that happen via function pointer. */
3826 exploded_graph::maybe_create_dynamic_call (const gcall
*call
,
3828 exploded_node
*node
,
3829 program_state next_state
,
3830 program_point
&next_point
,
3831 uncertainty_t
*uncertainty
,
3836 const program_point
*this_point
= &node
->get_point ();
3837 function
*fun
= DECL_STRUCT_FUNCTION (fn_decl
);
3840 const supergraph
&sg
= this->get_supergraph ();
3841 supernode
*sn_entry
= sg
.get_node_for_function_entry (fun
);
3842 supernode
*sn_exit
= sg
.get_node_for_function_exit (fun
);
3844 program_point new_point
3845 = program_point::before_supernode (sn_entry
,
3847 this_point
->get_call_string ());
3849 new_point
.push_to_call_stack (sn_exit
,
3850 next_point
.get_supernode());
3852 /* Impose a maximum recursion depth and don't analyze paths
3853 that exceed it further.
3854 This is something of a blunt workaround, but it only
3855 applies to recursion (and mutual recursion), not to
3856 general call stacks. */
3857 if (new_point
.get_call_string ().calc_recursion_depth ()
3858 > param_analyzer_max_recursion_depth
)
3861 logger
->log ("rejecting call edge: recursion limit exceeded");
3865 next_state
.push_call (*this, node
, call
, uncertainty
);
3867 if (next_state
.m_valid
)
3870 logger
->log ("Discovered call to %s [SN: %i -> SN: %i]",
3872 this_point
->get_supernode ()->m_index
,
3875 exploded_node
*enode
= get_or_create_node (new_point
,
3879 add_edge (node
,enode
, NULL
,
3880 false, /* No work is done by the call itself. */
3881 make_unique
<dynamic_call_info_t
> (call
));
3888 /* Subclass of path_context for use within exploded_graph::process_node,
3889 so that we can split states e.g. at "realloc" calls. */
3891 class impl_path_context
: public path_context
3894 impl_path_context (const program_state
*cur_state
,
3896 : m_cur_state (cur_state
),
3898 m_terminate_path (false)
3902 bool bifurcation_p () const
3904 return m_custom_eedge_infos
.length () > 0;
3907 const program_state
&get_state_at_bifurcation () const
3909 gcc_assert (m_state_at_bifurcation
);
3910 return *m_state_at_bifurcation
;
3914 bifurcate (std::unique_ptr
<custom_edge_info
> info
) final override
3917 m_logger
->log ("bifurcating path");
3919 if (m_state_at_bifurcation
)
3920 /* Verify that the state at bifurcation is consistent when we
3921 split into multiple out-edges. */
3922 gcc_assert (*m_state_at_bifurcation
== *m_cur_state
);
3924 /* Take a copy of the cur_state at the moment when bifurcation
3926 m_state_at_bifurcation
3927 = std::unique_ptr
<program_state
> (new program_state (*m_cur_state
));
3929 /* Take ownership of INFO. */
3930 m_custom_eedge_infos
.safe_push (info
.release ());
3933 void terminate_path () final override
3936 m_logger
->log ("terminating path");
3937 m_terminate_path
= true;
3940 bool terminate_path_p () const final override
3942 return m_terminate_path
;
3945 const vec
<custom_edge_info
*> & get_custom_eedge_infos ()
3947 return m_custom_eedge_infos
;
3951 const program_state
*m_cur_state
;
3955 /* Lazily-created copy of the state before the split. */
3956 std::unique_ptr
<program_state
> m_state_at_bifurcation
;
3958 auto_vec
<custom_edge_info
*> m_custom_eedge_infos
;
3960 bool m_terminate_path
;
3963 /* A subclass of pending_diagnostic for complaining about jumps through NULL
3964 function pointers. */
3966 class jump_through_null
: public pending_diagnostic_subclass
<jump_through_null
>
3969 jump_through_null (const gcall
*call
)
3973 const char *get_kind () const final override
3975 return "jump_through_null";
3978 bool operator== (const jump_through_null
&other
) const
3980 return m_call
== other
.m_call
;
3983 int get_controlling_option () const final override
3985 return OPT_Wanalyzer_jump_through_null
;
3988 bool emit (diagnostic_emission_context
&ctxt
) final override
3990 return ctxt
.warn ("jump through null pointer");
3993 label_text
describe_final_event (const evdesc::final_event
&ev
) final override
3995 return ev
.formatted_print ("jump through null pointer here");
3999 const gcall
*m_call
;
4002 /* The core of exploded_graph::process_worklist (the main analysis loop),
4003 handling one node in the worklist.
4005 Get successor <point, state> pairs for NODE, calling get_or_create on
4006 them, and adding an exploded_edge to each successors.
4008 Freshly-created nodes will be added to the worklist. */
4011 exploded_graph::process_node (exploded_node
*node
)
4013 logger
* const logger
= get_logger ();
4014 LOG_FUNC_1 (logger
, "EN: %i", node
->m_index
);
4016 node
->set_status (exploded_node::STATUS_PROCESSED
);
4018 const program_point
&point
= node
->get_point ();
4020 /* Update cfun and input_location in case of an ICE: make it easier to
4021 track down which source construct we're failing to handle. */
4022 auto_cfun
sentinel (node
->get_function ());
4023 const gimple
*stmt
= point
.get_stmt ();
4025 input_location
= stmt
->location
;
4027 const program_state
&state
= node
->get_state ();
4030 pretty_printer
*pp
= logger
->get_printer ();
4031 logger
->start_log_line ();
4032 pp_string (pp
, "point: ");
4033 point
.print (pp
, format (false));
4034 pp_string (pp
, ", state: ");
4035 state
.dump_to_pp (m_ext_state
, true, false, pp
);
4036 logger
->end_log_line ();
4039 switch (point
.get_kind ())
4044 /* This node exists to simplify finding the shortest path
4045 to an exploded_node. */
4048 case PK_BEFORE_SUPERNODE
:
4050 program_state
next_state (state
);
4051 uncertainty_t uncertainty
;
4053 if (point
.get_from_edge ())
4055 impl_region_model_context
ctxt (*this, node
,
4056 &state
, &next_state
,
4057 &uncertainty
, NULL
, NULL
);
4058 const cfg_superedge
*last_cfg_superedge
4059 = point
.get_from_edge ()->dyn_cast_cfg_superedge ();
4060 if (last_cfg_superedge
)
4061 next_state
.m_region_model
->update_for_phis
4062 (node
->get_supernode (),
4065 program_state::detect_leaks (state
, next_state
, NULL
,
4066 get_ext_state (), &ctxt
);
4069 program_point
next_point (point
.get_next ());
4070 exploded_node
*next
= get_or_create_node (next_point
, next_state
, node
);
4072 add_edge (node
, next
, NULL
,
4073 false); /* Assume no work is done at phi nodes. */
4076 case PK_BEFORE_STMT
:
4078 /* Determine the effect of a run of one or more statements
4079 within one supernode, generating an edge to the program_point
4080 after the last statement that's processed.
4082 Stop iterating statements and thus consolidating into one enode
4084 - reaching the end of the statements in the supernode
4085 - if an sm-state-change occurs (so that it gets its own
4087 - if "-fanalyzer-fine-grained" is active
4088 - encountering certain statements must appear at the start of
4089 their enode (for which stmt_requires_new_enode_p returns true)
4091 Update next_state in-place, to get the result of the one
4092 or more stmts that are processed.
4094 Split the node in-place if an sm-state-change occurs, so that
4095 the sm-state-change occurs on an edge where the src enode has
4096 exactly one stmt, the one that caused the change. */
4097 program_state
next_state (state
);
4099 impl_path_context
path_ctxt (&next_state
, logger
);
4101 bool could_have_done_work
= false;
4102 uncertainty_t uncertainty
;
4103 const supernode
*snode
= point
.get_supernode ();
4105 const gimple
*prev_stmt
= NULL
;
4106 for (stmt_idx
= point
.get_stmt_idx ();
4107 stmt_idx
< snode
->m_stmts
.length ();
4110 const gimple
*stmt
= snode
->m_stmts
[stmt_idx
];
4112 if (stmt_idx
> point
.get_stmt_idx ())
4113 if (stmt_requires_new_enode_p (stmt
, prev_stmt
))
4120 program_state
old_state (next_state
);
4122 /* Process the stmt. */
4123 exploded_node::on_stmt_flags flags
4124 = node
->on_stmt (*this, snode
, stmt
, &next_state
, &uncertainty
,
4125 &could_have_done_work
, &path_ctxt
);
4126 node
->m_num_processed_stmts
++;
4128 /* If flags.m_terminate_path, stop analyzing; any nodes/edges
4129 will have been added by on_stmt (e.g. for handling longjmp). */
4130 if (flags
.m_terminate_path
)
4133 if (next_state
.m_region_model
)
4135 impl_region_model_context
ctxt (*this, node
,
4136 &old_state
, &next_state
,
4137 &uncertainty
, NULL
, stmt
);
4138 program_state::detect_leaks (old_state
, next_state
, NULL
,
4139 get_ext_state (), &ctxt
);
4142 unsigned next_idx
= stmt_idx
+ 1;
4143 program_point next_point
4144 = (next_idx
< point
.get_supernode ()->m_stmts
.length ()
4145 ? program_point::before_stmt (point
.get_supernode (), next_idx
,
4146 point
.get_call_string ())
4147 : program_point::after_supernode (point
.get_supernode (),
4148 point
.get_call_string ()));
4149 next_state
= next_state
.prune_for_point (*this, next_point
, node
,
4152 if (flag_analyzer_fine_grained
4153 || state_change_requires_new_enode_p (old_state
, next_state
)
4154 || path_ctxt
.bifurcation_p ()
4155 || path_ctxt
.terminate_path_p ())
4157 program_point split_point
4158 = program_point::before_stmt (point
.get_supernode (),
4160 point
.get_call_string ());
4161 if (split_point
!= node
->get_point ())
4163 /* If we're not at the start of NODE, split the enode at
4164 this stmt, so we have:
4166 so that when split_enode is processed the next edge
4169 and any state change will effectively occur on that
4170 latter edge, and split_enode will contain just stmt. */
4172 logger
->log ("getting split_enode");
4173 exploded_node
*split_enode
4174 = get_or_create_node (split_point
, old_state
, node
);
4177 /* "stmt" will be reprocessed when split_enode is
4179 node
->m_num_processed_stmts
--;
4181 logger
->log ("creating edge to split_enode");
4182 add_edge (node
, split_enode
, NULL
, could_have_done_work
);
4186 /* If we're at the start of NODE, stop iterating,
4187 so that an edge will be created from NODE to
4188 (next_point, next_state) below. */
4192 unsigned next_idx
= stmt_idx
+ 1;
4193 program_point next_point
4194 = (next_idx
< point
.get_supernode ()->m_stmts
.length ()
4195 ? program_point::before_stmt (point
.get_supernode (), next_idx
,
4196 point
.get_call_string ())
4197 : program_point::after_supernode (point
.get_supernode (),
4198 point
.get_call_string ()));
4199 if (path_ctxt
.terminate_path_p ())
4202 logger
->log ("not adding node: terminating path");
4207 = get_or_create_node (next_point
, next_state
, node
);
4209 add_edge (node
, next
, NULL
, could_have_done_work
);
4212 /* If we have custom edge infos, "bifurcate" the state
4213 accordingly, potentially creating a new state/enode/eedge
4214 instances. For example, to handle a "realloc" call, we
4215 might split into 3 states, for the "failure",
4216 "resizing in place", and "moving to a new buffer" cases. */
4217 for (auto edge_info_iter
: path_ctxt
.get_custom_eedge_infos ())
4219 /* Take ownership of the edge infos from the path_ctxt. */
4220 std::unique_ptr
<custom_edge_info
> edge_info (edge_info_iter
);
4223 logger
->start_log_line ();
4224 logger
->log_partial ("bifurcating for edge: ");
4225 edge_info
->print (logger
->get_printer ());
4226 logger
->end_log_line ();
4228 program_state bifurcated_new_state
4229 (path_ctxt
.get_state_at_bifurcation ());
4231 /* Apply edge_info to state. */
4232 impl_region_model_context
4233 bifurcation_ctxt (*this,
4234 node
, // enode_for_diag
4235 &path_ctxt
.get_state_at_bifurcation (),
4236 &bifurcated_new_state
,
4237 NULL
, // uncertainty_t *uncertainty
4238 NULL
, // path_context *path_ctxt
4240 if (edge_info
->update_state (&bifurcated_new_state
,
4241 NULL
, /* no exploded_edge yet. */
4244 exploded_node
*next2
4245 = get_or_create_node (next_point
, bifurcated_new_state
, node
);
4247 add_edge (node
, next2
, NULL
,
4248 true /* assume that work could be done */,
4249 std::move (edge_info
));
4254 logger
->log ("infeasible state, not adding node");
4259 case PK_AFTER_SUPERNODE
:
4261 bool found_a_superedge
= false;
4262 bool is_an_exit_block
= false;
4263 /* If this is an EXIT BB, detect leaks, and potentially
4264 create a function summary. */
4265 if (point
.get_supernode ()->return_p ())
4267 is_an_exit_block
= true;
4268 node
->detect_leaks (*this);
4269 if (flag_analyzer_call_summaries
4270 && point
.get_call_string ().empty_p ())
4272 /* TODO: create function summary
4273 There can be more than one; each corresponds to a different
4274 final enode in the function. */
4277 pretty_printer
*pp
= logger
->get_printer ();
4278 logger
->start_log_line ();
4280 ("would create function summary for %qE; state: ",
4281 point
.get_fndecl ());
4282 state
.dump_to_pp (m_ext_state
, true, false, pp
);
4283 logger
->end_log_line ();
4285 per_function_data
*per_fn_data
4286 = get_or_create_per_function_data (point
.get_function ());
4287 per_fn_data
->add_call_summary (node
);
4290 /* Traverse into successors of the supernode. */
4293 FOR_EACH_VEC_ELT (point
.get_supernode ()->m_succs
, i
, succ
)
4295 found_a_superedge
= true;
4298 label_text
succ_desc (succ
->get_description (false));
4299 logger
->log ("considering SN: %i -> SN: %i (%s)",
4300 succ
->m_src
->m_index
, succ
->m_dest
->m_index
,
4304 program_point next_point
4305 = program_point::before_supernode (succ
->m_dest
, succ
,
4306 point
.get_call_string ());
4307 program_state
next_state (state
);
4308 uncertainty_t uncertainty
;
4310 /* Make use the current state and try to discover and analyse
4311 indirect function calls (a call that doesn't have an underlying
4312 cgraph edge representing call).
4314 Some examples of such calls are virtual function calls
4315 and calls that happen via a function pointer. */
4316 if (succ
->m_kind
== SUPEREDGE_INTRAPROCEDURAL_CALL
4317 && !(succ
->get_any_callgraph_edge ()))
4320 = point
.get_supernode ()->get_final_call ();
4322 impl_region_model_context
ctxt (*this,
4330 region_model
*model
= state
.m_region_model
;
4331 bool call_discovered
= false;
4333 if (tree fn_decl
= model
->get_fndecl_for_call (call
, &ctxt
))
4334 call_discovered
= maybe_create_dynamic_call (call
,
4341 if (!call_discovered
)
4343 /* Check for jump through NULL. */
4344 if (tree fn_ptr
= gimple_call_fn (call
))
4346 const svalue
*fn_ptr_sval
4347 = model
->get_rvalue (fn_ptr
, &ctxt
);
4348 if (fn_ptr_sval
->all_zeroes_p ())
4349 ctxt
.warn (make_unique
<jump_through_null
> (call
));
4352 /* An unknown function or a special function was called
4353 at this point, in such case, don't terminate the
4354 analysis of the current function.
4356 The analyzer handles calls to such functions while
4357 analysing the stmt itself, so the function call
4358 must have been handled by the anlyzer till now. */
4360 = get_or_create_node (next_point
,
4364 add_edge (node
, next
, succ
,
4365 true /* assume that work is done */);
4369 if (!node
->on_edge (*this, succ
, &next_point
, &next_state
,
4373 logger
->log ("skipping impossible edge to SN: %i",
4374 succ
->m_dest
->m_index
);
4377 exploded_node
*next
= get_or_create_node (next_point
, next_state
,
4381 add_edge (node
, next
, succ
, false);
4383 /* We might have a function entrypoint. */
4384 detect_infinite_recursion (next
);
4388 /* Return from the calls which doesn't have a return superedge.
4389 Such case occurs when GCC's middle end didn't knew which function to
4390 call but analyzer did. */
4391 if ((is_an_exit_block
&& !found_a_superedge
)
4392 && (!point
.get_call_string ().empty_p ()))
4394 const call_string
&cs
= point
.get_call_string ();
4395 program_point next_point
4396 = program_point::before_supernode (cs
.get_caller_node (),
4399 program_state
next_state (state
);
4400 uncertainty_t uncertainty
;
4403 = next_point
.get_supernode ()->get_returning_call ();
4406 next_state
.returning_call (*this, node
, call
, &uncertainty
);
4408 if (next_state
.m_valid
)
4410 next_point
.pop_from_call_stack ();
4411 exploded_node
*enode
= get_or_create_node (next_point
,
4415 add_edge (node
, enode
, NULL
, false,
4416 make_unique
<dynamic_call_info_t
> (call
, true));
4424 /* Ensure that this graph has a stats instance for FN, return it.
4425 FN can be NULL, in which case a stats instances is returned covering
4426 "functionless" parts of the graph (the origin node). */
4429 exploded_graph::get_or_create_function_stats (function
*fn
)
4432 return &m_functionless_stats
;
4434 if (stats
**slot
= m_per_function_stats
.get (fn
))
4438 int num_supernodes
= fn
? n_basic_blocks_for_fn (fn
) : 0;
4439 /* not quite the num supernodes, but nearly. */
4440 stats
*new_stats
= new stats (num_supernodes
);
4441 m_per_function_stats
.put (fn
, new_stats
);
4446 /* Print bar charts to PP showing:
4447 - the number of enodes per function, and
4448 - for each function:
4449 - the number of enodes per supernode/BB
4450 - the number of excess enodes per supernode/BB beyond the
4451 per-program-point limit, if there were any. */
4454 exploded_graph::print_bar_charts (pretty_printer
*pp
) const
4456 cgraph_node
*cgnode
;
4458 pp_string (pp
, "enodes per function:");
4460 bar_chart enodes_per_function
;
4461 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode
)
4463 function
*fn
= cgnode
->get_fun ();
4464 const stats
* const *s_ptr
4465 = const_cast <function_stat_map_t
&> (m_per_function_stats
).get (fn
);
4466 enodes_per_function
.add_item (function_name (fn
),
4467 s_ptr
? (*s_ptr
)->get_total_enodes () : 0);
4469 enodes_per_function
.print (pp
);
4471 /* Accumulate number of enodes per supernode. */
4472 auto_vec
<unsigned> enodes_per_supernode (m_sg
.num_nodes ());
4473 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
4474 enodes_per_supernode
.quick_push (0);
4476 exploded_node
*enode
;
4477 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
4479 const supernode
*iter_snode
= enode
->get_supernode ();
4482 enodes_per_supernode
[iter_snode
->m_index
]++;
4485 /* Accumulate excess enodes per supernode. */
4486 auto_vec
<unsigned> excess_enodes_per_supernode (m_sg
.num_nodes ());
4487 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
4488 excess_enodes_per_supernode
.quick_push (0);
4489 for (point_map_t::iterator iter
= m_per_point_data
.begin ();
4490 iter
!= m_per_point_data
.end (); ++iter
)
4492 const program_point
*point
= (*iter
).first
;
4493 const supernode
*iter_snode
= point
->get_supernode ();
4496 const per_program_point_data
*point_data
= (*iter
).second
;
4497 excess_enodes_per_supernode
[iter_snode
->m_index
]
4498 += point_data
->m_excess_enodes
;
4501 /* Show per-function bar_charts of enodes per supernode/BB. */
4502 pp_string (pp
, "per-function enodes per supernode/BB:");
4504 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode
)
4506 function
*fn
= cgnode
->get_fun ();
4507 pp_printf (pp
, "function: %qs", function_name (fn
));
4510 bar_chart enodes_per_snode
;
4511 bar_chart excess_enodes_per_snode
;
4512 bool have_excess_enodes
= false;
4513 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
4515 const supernode
*iter_snode
= m_sg
.get_node_by_index (i
);
4516 if (iter_snode
->get_function () != fn
)
4518 pretty_printer tmp_pp
;
4519 pp_printf (&tmp_pp
, "sn %i (bb %i)",
4520 iter_snode
->m_index
, iter_snode
->m_bb
->index
);
4521 enodes_per_snode
.add_item (pp_formatted_text (&tmp_pp
),
4522 enodes_per_supernode
[iter_snode
->m_index
]);
4523 const int num_excess
4524 = excess_enodes_per_supernode
[iter_snode
->m_index
];
4525 excess_enodes_per_snode
.add_item (pp_formatted_text (&tmp_pp
),
4528 have_excess_enodes
= true;
4530 enodes_per_snode
.print (pp
);
4531 if (have_excess_enodes
)
4533 pp_printf (pp
, "EXCESS ENODES:");
4535 excess_enodes_per_snode
.print (pp
);
4540 /* Write all stats information to this graph's logger, if any. */
4543 exploded_graph::log_stats () const
4545 logger
* const logger
= get_logger ();
4551 m_ext_state
.get_engine ()->log_stats (logger
);
4553 logger
->log ("m_sg.num_nodes (): %i", m_sg
.num_nodes ());
4554 logger
->log ("m_nodes.length (): %i", m_nodes
.length ());
4555 logger
->log ("m_edges.length (): %i", m_edges
.length ());
4556 logger
->log ("remaining enodes in worklist: %i", m_worklist
.length ());
4558 logger
->log ("global stats:");
4559 m_global_stats
.log (logger
);
4561 for (function_stat_map_t::iterator iter
= m_per_function_stats
.begin ();
4562 iter
!= m_per_function_stats
.end ();
4565 function
*fn
= (*iter
).first
;
4566 log_scope
s (logger
, function_name (fn
));
4567 (*iter
).second
->log (logger
);
4570 print_bar_charts (logger
->get_printer ());
4573 /* Dump all stats information to OUT. */
4576 exploded_graph::dump_stats (FILE *out
) const
4578 fprintf (out
, "m_sg.num_nodes (): %i\n", m_sg
.num_nodes ());
4579 fprintf (out
, "m_nodes.length (): %i\n", m_nodes
.length ());
4580 fprintf (out
, "m_edges.length (): %i\n", m_edges
.length ());
4581 fprintf (out
, "remaining enodes in worklist: %i", m_worklist
.length ());
4583 fprintf (out
, "global stats:\n");
4584 m_global_stats
.dump (out
);
4586 for (function_stat_map_t::iterator iter
= m_per_function_stats
.begin ();
4587 iter
!= m_per_function_stats
.end ();
4590 function
*fn
= (*iter
).first
;
4591 fprintf (out
, "function: %s\n", function_name (fn
));
4592 (*iter
).second
->dump (out
);
4595 fprintf (out
, "PK_AFTER_SUPERNODE per supernode:\n");
4596 for (unsigned i
= 0; i
< m_PK_AFTER_SUPERNODE_per_snode
.length (); i
++)
4597 fprintf (out
, " SN %i: %3i\n", i
, m_PK_AFTER_SUPERNODE_per_snode
[i
]);
4601 exploded_graph::dump_states_for_supernode (FILE *out
,
4602 const supernode
*snode
) const
4604 fprintf (out
, "PK_AFTER_SUPERNODE nodes for SN: %i\n", snode
->m_index
);
4606 exploded_node
*enode
;
4608 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
4610 const supernode
*iter_snode
= enode
->get_supernode ();
4611 if (enode
->get_point ().get_kind () == PK_AFTER_SUPERNODE
4612 && iter_snode
== snode
)
4615 pp_format_decoder (&pp
) = default_tree_printer
;
4616 enode
->get_state ().dump_to_pp (m_ext_state
, true, false, &pp
);
4617 fprintf (out
, "state %i: EN: %i\n %s\n",
4618 state_idx
++, enode
->m_index
,
4619 pp_formatted_text (&pp
));
4622 fprintf (out
, "#exploded_node for PK_AFTER_SUPERNODE for SN: %i = %i\n",
4623 snode
->m_index
, state_idx
);
4626 /* Return a new json::object of the form
4627 {"nodes" : [objs for enodes],
4628 "edges" : [objs for eedges],
4629 "ext_state": object for extrinsic_state,
4630 "diagnostic_manager": object for diagnostic_manager}. */
4633 exploded_graph::to_json () const
4635 json::object
*egraph_obj
= new json::object ();
4639 json::array
*nodes_arr
= new json::array ();
4642 FOR_EACH_VEC_ELT (m_nodes
, i
, n
)
4643 nodes_arr
->append (n
->to_json (m_ext_state
));
4644 egraph_obj
->set ("nodes", nodes_arr
);
4649 json::array
*edges_arr
= new json::array ();
4652 FOR_EACH_VEC_ELT (m_edges
, i
, n
)
4653 edges_arr
->append (n
->to_json ());
4654 egraph_obj
->set ("edges", edges_arr
);
4657 /* m_sg is JSONified at the top-level. */
4659 egraph_obj
->set ("ext_state", m_ext_state
.to_json ());
4660 egraph_obj
->set ("worklist", m_worklist
.to_json ());
4661 egraph_obj
->set ("diagnostic_manager", m_diagnostic_manager
.to_json ());
4663 /* The following fields aren't yet being JSONified:
4664 const state_purge_map *const m_purge_map;
4665 const analysis_plan &m_plan;
4666 stats m_global_stats;
4667 function_stat_map_t m_per_function_stats;
4668 stats m_functionless_stats;
4669 call_string_data_map_t m_per_call_string_data;
4670 auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode; */
4675 /* class exploded_path. */
4679 exploded_path::exploded_path (const exploded_path
&other
)
4680 : m_edges (other
.m_edges
.length ())
4683 const exploded_edge
*eedge
;
4684 FOR_EACH_VEC_ELT (other
.m_edges
, i
, eedge
)
4685 m_edges
.quick_push (eedge
);
4688 /* Look for the last use of SEARCH_STMT within this path.
4689 If found write the edge's index to *OUT_IDX and return true, otherwise
4693 exploded_path::find_stmt_backwards (const gimple
*search_stmt
,
4697 const exploded_edge
*eedge
;
4698 FOR_EACH_VEC_ELT_REVERSE (m_edges
, i
, eedge
)
4700 const exploded_node
*dst_node
= eedge
->m_dest
;
4701 const program_point
&dst_point
= dst_node
->get_point ();
4702 const gimple
*stmt
= dst_point
.get_stmt ();
4703 if (stmt
== search_stmt
)
4712 /* Get the final exploded_node in this path, which must be non-empty. */
4715 exploded_path::get_final_enode () const
4717 gcc_assert (m_edges
.length () > 0);
4718 return m_edges
[m_edges
.length () - 1]->m_dest
;
4721 /* Check state along this path, returning true if it is feasible.
4722 If OUT is non-NULL, and the path is infeasible, write a new
4723 feasibility_problem to *OUT. */
4726 exploded_path::feasible_p (logger
*logger
,
4727 std::unique_ptr
<feasibility_problem
> *out
,
4728 engine
*eng
, const exploded_graph
*eg
) const
4732 feasibility_state
state (eng
->get_model_manager (),
4733 eg
->get_supergraph ());
4735 /* Traverse the path, updating this state. */
4736 for (unsigned edge_idx
= 0; edge_idx
< m_edges
.length (); edge_idx
++)
4738 const exploded_edge
*eedge
= m_edges
[edge_idx
];
4740 logger
->log ("considering edge %i: EN:%i -> EN:%i",
4742 eedge
->m_src
->m_index
,
4743 eedge
->m_dest
->m_index
);
4745 std::unique_ptr
<rejected_constraint
> rc
;
4746 if (!state
.maybe_update_for_edge (logger
, eedge
, nullptr, &rc
))
4751 const exploded_node
&src_enode
= *eedge
->m_src
;
4752 const program_point
&src_point
= src_enode
.get_point ();
4753 const gimple
*last_stmt
4754 = src_point
.get_supernode ()->get_last_stmt ();
4755 *out
= ::make_unique
<feasibility_problem
> (edge_idx
, *eedge
,
4764 logger
->log ("state after edge %i: EN:%i -> EN:%i",
4766 eedge
->m_src
->m_index
,
4767 eedge
->m_dest
->m_index
);
4768 logger
->start_log_line ();
4769 state
.get_model ().dump_to_pp (logger
->get_printer (), true, false);
4770 logger
->end_log_line ();
4777 /* Dump this path in multiline form to PP.
4778 If EXT_STATE is non-NULL, then show the nodes. */
4781 exploded_path::dump_to_pp (pretty_printer
*pp
,
4782 const extrinsic_state
*ext_state
) const
4784 for (unsigned i
= 0; i
< m_edges
.length (); i
++)
4786 const exploded_edge
*eedge
= m_edges
[i
];
4787 pp_printf (pp
, "m_edges[%i]: EN %i -> EN %i",
4789 eedge
->m_src
->m_index
,
4790 eedge
->m_dest
->m_index
);
4794 eedge
->m_dest
->dump_to_pp (pp
, *ext_state
);
4798 /* Dump this path in multiline form to FP. */
4801 exploded_path::dump (FILE *fp
, const extrinsic_state
*ext_state
) const
4804 pp_format_decoder (&pp
) = default_tree_printer
;
4805 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
4806 pp
.buffer
->stream
= fp
;
4807 dump_to_pp (&pp
, ext_state
);
4811 /* Dump this path in multiline form to stderr. */
4814 exploded_path::dump (const extrinsic_state
*ext_state
) const
4816 dump (stderr
, ext_state
);
4819 /* Dump this path verbosely to FILENAME. */
4822 exploded_path::dump_to_file (const char *filename
,
4823 const extrinsic_state
&ext_state
) const
4825 FILE *fp
= fopen (filename
, "w");
4829 pp_format_decoder (&pp
) = default_tree_printer
;
4830 pp
.buffer
->stream
= fp
;
4831 dump_to_pp (&pp
, &ext_state
);
4836 /* class feasibility_problem. */
4839 feasibility_problem::dump_to_pp (pretty_printer
*pp
) const
4841 pp_printf (pp
, "edge from EN: %i to EN: %i",
4842 m_eedge
.m_src
->m_index
, m_eedge
.m_dest
->m_index
);
4845 pp_string (pp
, "; rejected constraint: ");
4846 m_rc
->dump_to_pp (pp
);
4847 pp_string (pp
, "; rmodel: ");
4848 m_rc
->get_model ().dump_to_pp (pp
, true, false);
4852 /* class feasibility_state. */
4854 /* Ctor for feasibility_state, at the beginning of a path. */
4856 feasibility_state::feasibility_state (region_model_manager
*manager
,
4857 const supergraph
&sg
)
4858 : m_model (manager
),
4859 m_snodes_visited (sg
.m_nodes
.length ())
4861 bitmap_clear (m_snodes_visited
);
4864 /* Copy ctor for feasibility_state, for extending a path. */
4866 feasibility_state::feasibility_state (const feasibility_state
&other
)
4867 : m_model (other
.m_model
),
4868 m_snodes_visited (const_sbitmap (other
.m_snodes_visited
)->n_bits
)
4870 bitmap_copy (m_snodes_visited
, other
.m_snodes_visited
);
4873 feasibility_state::feasibility_state (const region_model
&model
,
4874 const supergraph
&sg
)
4876 m_snodes_visited (sg
.m_nodes
.length ())
4878 bitmap_clear (m_snodes_visited
);
4882 feasibility_state::operator= (const feasibility_state
&other
)
4884 m_model
= other
.m_model
;
4885 bitmap_copy (m_snodes_visited
, other
.m_snodes_visited
);
4889 /* The heart of feasibility-checking.
4891 Attempt to update this state in-place based on traversing EEDGE
4893 Update the model for the stmts in the src enode.
4894 Attempt to add constraints for EEDGE.
4896 If feasible, return true.
4897 Otherwise, return false and write to *OUT_RC. */
4901 maybe_update_for_edge (logger
*logger
,
4902 const exploded_edge
*eedge
,
4903 region_model_context
*ctxt
,
4904 std::unique_ptr
<rejected_constraint
> *out_rc
)
4906 const exploded_node
&src_enode
= *eedge
->m_src
;
4907 const program_point
&src_point
= src_enode
.get_point ();
4910 logger
->start_log_line ();
4911 src_point
.print (logger
->get_printer (), format (false));
4912 logger
->end_log_line ();
4915 /* Update state for the stmts that were processed in each enode. */
4916 for (unsigned stmt_idx
= 0; stmt_idx
< src_enode
.m_num_processed_stmts
;
4919 const gimple
*stmt
= src_enode
.get_processed_stmt (stmt_idx
);
4921 /* Update cfun and input_location in case of ICE: make it easier to
4922 track down which source construct we're failing to handle. */
4923 auto_cfun
sentinel (src_point
.get_function ());
4924 input_location
= stmt
->location
;
4926 update_for_stmt (stmt
);
4929 const superedge
*sedge
= eedge
->m_sedge
;
4934 label_text
desc (sedge
->get_description (false));
4935 logger
->log (" sedge: SN:%i -> SN:%i %s",
4936 sedge
->m_src
->m_index
,
4937 sedge
->m_dest
->m_index
,
4941 const gimple
*last_stmt
= src_point
.get_supernode ()->get_last_stmt ();
4942 if (!m_model
.maybe_update_for_edge (*sedge
, last_stmt
, ctxt
, out_rc
))
4946 logger
->start_log_line ();
4947 logger
->log_partial ("rejecting due to region model: ");
4948 m_model
.dump_to_pp (logger
->get_printer (), true, false);
4949 logger
->end_log_line ();
4956 /* Special-case the initial eedge from the origin node to the
4957 initial function by pushing a frame for it. */
4958 if (src_point
.get_kind () == PK_ORIGIN
)
4960 gcc_assert (eedge
->m_src
->m_index
== 0);
4961 gcc_assert (eedge
->m_dest
->get_point ().get_kind ()
4962 == PK_BEFORE_SUPERNODE
);
4963 function
*fun
= eedge
->m_dest
->get_function ();
4965 m_model
.push_frame (fun
, NULL
, ctxt
);
4967 logger
->log (" pushing frame for %qD", fun
->decl
);
4969 else if (eedge
->m_custom_info
)
4971 eedge
->m_custom_info
->update_model (&m_model
, eedge
, ctxt
);
4975 /* Handle phi nodes on an edge leaving a PK_BEFORE_SUPERNODE (to
4976 a PK_BEFORE_STMT, or a PK_AFTER_SUPERNODE if no stmts).
4977 This will typically not be associated with a superedge. */
4978 if (src_point
.get_from_edge ())
4980 const cfg_superedge
*last_cfg_superedge
4981 = src_point
.get_from_edge ()->dyn_cast_cfg_superedge ();
4982 const exploded_node
&dst_enode
= *eedge
->m_dest
;
4983 const unsigned dst_snode_idx
= dst_enode
.get_supernode ()->m_index
;
4984 if (last_cfg_superedge
)
4987 logger
->log (" update for phis");
4988 m_model
.update_for_phis (src_enode
.get_supernode (),
4991 /* If we've entering an snode that we've already visited on this
4992 epath, then we need do fix things up for loops; see the
4993 comment for store::loop_replay_fixup.
4994 Perhaps we should probably also verify the callstring,
4995 and track program_points, but hopefully doing it by supernode
4997 if (bitmap_bit_p (m_snodes_visited
, dst_snode_idx
))
4998 m_model
.loop_replay_fixup (dst_enode
.get_state ().m_region_model
);
5000 bitmap_set_bit (m_snodes_visited
, dst_snode_idx
);
5005 /* Update this object for the effects of STMT. */
5008 feasibility_state::update_for_stmt (const gimple
*stmt
)
5010 if (const gassign
*assign
= dyn_cast
<const gassign
*> (stmt
))
5011 m_model
.on_assignment (assign
, NULL
);
5012 else if (const gasm
*asm_stmt
= dyn_cast
<const gasm
*> (stmt
))
5013 m_model
.on_asm_stmt (asm_stmt
, NULL
);
5014 else if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
5016 bool unknown_side_effects
= m_model
.on_call_pre (call
, NULL
);
5017 m_model
.on_call_post (call
, unknown_side_effects
, NULL
);
5019 else if (const greturn
*return_
= dyn_cast
<const greturn
*> (stmt
))
5020 m_model
.on_return (return_
, NULL
);
5023 /* Dump this object to PP. */
5026 feasibility_state::dump_to_pp (pretty_printer
*pp
,
5027 bool simple
, bool multiline
) const
5029 m_model
.dump_to_pp (pp
, simple
, multiline
);
5032 /* A family of cluster subclasses for use when generating .dot output for
5033 exploded graphs (-fdump-analyzer-exploded-graph), for grouping the
5034 enodes into hierarchical boxes.
5036 All functionless enodes appear in the top-level graph.
5037 Every (function, call_string) pair gets its own cluster. Within that
5038 cluster, each supernode gets its own cluster.
5040 Hence all enodes relating to a particular function with a particular
5041 callstring will be in a cluster together; all enodes for the same
5042 function but with a different callstring will be in a different
5045 /* Base class of cluster for clustering exploded_node instances in .dot
5046 output, based on various subclass-specific criteria. */
5048 class exploded_cluster
: public cluster
<eg_traits
>
5052 /* Cluster containing all exploded_node instances for one supernode. */
5054 class supernode_cluster
: public exploded_cluster
5057 supernode_cluster (const supernode
*supernode
) : m_supernode (supernode
) {}
5061 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const final override
5063 gv
->println ("subgraph \"cluster_supernode_%i\" {", m_supernode
->m_index
);
5065 gv
->println ("style=\"dashed\";");
5066 gv
->println ("label=\"SN: %i (bb: %i; scc: %i)\";",
5067 m_supernode
->m_index
, m_supernode
->m_bb
->index
,
5068 args
.m_eg
.get_scc_id (*m_supernode
));
5071 exploded_node
*enode
;
5072 FOR_EACH_VEC_ELT (m_enodes
, i
, enode
)
5073 enode
->dump_dot (gv
, args
);
5075 /* Terminate subgraph. */
5080 void add_node (exploded_node
*en
) final override
5082 m_enodes
.safe_push (en
);
5085 /* Comparator for use by auto_vec<supernode_cluster *>::qsort. */
5087 static int cmp_ptr_ptr (const void *p1
, const void *p2
)
5089 const supernode_cluster
*c1
5090 = *(const supernode_cluster
* const *)p1
;
5091 const supernode_cluster
*c2
5092 = *(const supernode_cluster
* const *)p2
;
5093 return c1
->m_supernode
->m_index
- c2
->m_supernode
->m_index
;
5097 const supernode
*m_supernode
;
5098 auto_vec
<exploded_node
*> m_enodes
;
5101 /* Cluster containing all supernode_cluster instances for one
5102 (function, call_string) pair. */
5104 class function_call_string_cluster
: public exploded_cluster
5107 function_call_string_cluster (function
*fun
, const call_string
&cs
)
5108 : m_fun (fun
), m_cs (cs
) {}
5110 ~function_call_string_cluster ()
5112 for (map_t::iterator iter
= m_map
.begin ();
5113 iter
!= m_map
.end ();
5115 delete (*iter
).second
;
5118 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const final override
5120 const char *funcname
= function_name (m_fun
);
5122 gv
->println ("subgraph \"cluster_function_%s\" {",
5123 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (m_fun
->decl
)));
5125 gv
->write_indent ();
5126 gv
->print ("label=\"call string: ");
5127 m_cs
.print (gv
->get_pp ());
5128 gv
->print (" function: %s \";", funcname
);
5131 /* Dump m_map, sorting it to avoid churn when comparing dumps. */
5132 auto_vec
<supernode_cluster
*> child_clusters (m_map
.elements ());
5133 for (map_t::iterator iter
= m_map
.begin ();
5134 iter
!= m_map
.end ();
5136 child_clusters
.quick_push ((*iter
).second
);
5138 child_clusters
.qsort (supernode_cluster::cmp_ptr_ptr
);
5141 supernode_cluster
*child_cluster
;
5142 FOR_EACH_VEC_ELT (child_clusters
, i
, child_cluster
)
5143 child_cluster
->dump_dot (gv
, args
);
5145 /* Terminate subgraph. */
5150 void add_node (exploded_node
*en
) final override
5152 const supernode
*supernode
= en
->get_supernode ();
5153 gcc_assert (supernode
);
5154 supernode_cluster
**slot
= m_map
.get (supernode
);
5156 (*slot
)->add_node (en
);
5159 supernode_cluster
*child
= new supernode_cluster (supernode
);
5160 m_map
.put (supernode
, child
);
5161 child
->add_node (en
);
5165 /* Comparator for use by auto_vec<function_call_string_cluster *>. */
5167 static int cmp_ptr_ptr (const void *p1
, const void *p2
)
5169 const function_call_string_cluster
*c1
5170 = *(const function_call_string_cluster
* const *)p1
;
5171 const function_call_string_cluster
*c2
5172 = *(const function_call_string_cluster
* const *)p2
;
5174 = strcmp (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c1
->m_fun
->decl
)),
5175 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c2
->m_fun
->decl
))))
5177 return call_string::cmp (c1
->m_cs
, c2
->m_cs
);
5182 const call_string
&m_cs
;
5183 typedef ordered_hash_map
<const supernode
*, supernode_cluster
*> map_t
;
5187 /* Keys for root_cluster. */
5189 struct function_call_string
5191 function_call_string (function
*fun
, const call_string
*cs
)
5192 : m_fun (fun
), m_cs (cs
)
5199 const call_string
*m_cs
;
5204 template <> struct default_hash_traits
<function_call_string
>
5205 : public pod_hash_traits
<function_call_string
>
5207 static const bool empty_zero_p
= false;
5212 pod_hash_traits
<function_call_string
>::hash (value_type v
)
5214 return (pointer_hash
<function
>::hash (v
.m_fun
)
5215 ^ pointer_hash
<const call_string
>::hash (v
.m_cs
));
5220 pod_hash_traits
<function_call_string
>::equal (const value_type
&existing
,
5221 const value_type
&candidate
)
5223 return existing
.m_fun
== candidate
.m_fun
&& &existing
.m_cs
== &candidate
.m_cs
;
5227 pod_hash_traits
<function_call_string
>::mark_deleted (value_type
&v
)
5229 v
.m_fun
= reinterpret_cast<function
*> (1);
5233 pod_hash_traits
<function_call_string
>::mark_empty (value_type
&v
)
5239 pod_hash_traits
<function_call_string
>::is_deleted (value_type v
)
5241 return v
.m_fun
== reinterpret_cast<function
*> (1);
5245 pod_hash_traits
<function_call_string
>::is_empty (value_type v
)
5247 return v
.m_fun
== NULL
;
5252 /* Top-level cluster for generating .dot output for exploded graphs,
5253 handling the functionless nodes, and grouping the remaining nodes by
5256 class root_cluster
: public exploded_cluster
5261 for (map_t::iterator iter
= m_map
.begin ();
5262 iter
!= m_map
.end ();
5264 delete (*iter
).second
;
5267 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const final override
5270 exploded_node
*enode
;
5271 FOR_EACH_VEC_ELT (m_functionless_enodes
, i
, enode
)
5272 enode
->dump_dot (gv
, args
);
5274 /* Dump m_map, sorting it to avoid churn when comparing dumps. */
5275 auto_vec
<function_call_string_cluster
*> child_clusters (m_map
.elements ());
5276 for (map_t::iterator iter
= m_map
.begin ();
5277 iter
!= m_map
.end ();
5279 child_clusters
.quick_push ((*iter
).second
);
5281 child_clusters
.qsort (function_call_string_cluster::cmp_ptr_ptr
);
5283 function_call_string_cluster
*child_cluster
;
5284 FOR_EACH_VEC_ELT (child_clusters
, i
, child_cluster
)
5285 child_cluster
->dump_dot (gv
, args
);
5288 void add_node (exploded_node
*en
) final override
5290 function
*fun
= en
->get_function ();
5293 m_functionless_enodes
.safe_push (en
);
5297 const call_string
&cs
= en
->get_point ().get_call_string ();
5298 function_call_string
key (fun
, &cs
);
5299 function_call_string_cluster
**slot
= m_map
.get (key
);
5301 (*slot
)->add_node (en
);
5304 function_call_string_cluster
*child
5305 = new function_call_string_cluster (fun
, cs
);
5306 m_map
.put (key
, child
);
5307 child
->add_node (en
);
5312 typedef hash_map
<function_call_string
, function_call_string_cluster
*> map_t
;
5315 /* This should just be the origin exploded_node. */
5316 auto_vec
<exploded_node
*> m_functionless_enodes
;
5319 /* Subclass of range_label for use within
5320 exploded_graph::dump_exploded_nodes for implementing
5321 -fdump-analyzer-exploded-nodes: a label for a specific
5324 class enode_label
: public range_label
5327 enode_label (const extrinsic_state
&ext_state
,
5328 exploded_node
*enode
)
5329 : m_ext_state (ext_state
), m_enode (enode
) {}
5331 label_text
get_text (unsigned) const final override
5334 pp_format_decoder (&pp
) = default_tree_printer
;
5335 m_enode
->get_state ().dump_to_pp (m_ext_state
, true, false, &pp
);
5336 return make_label_text (false, "EN: %i: %s",
5337 m_enode
->m_index
, pp_formatted_text (&pp
));
5341 const extrinsic_state
&m_ext_state
;
5342 exploded_node
*m_enode
;
5345 /* Postprocessing support for dumping the exploded nodes.
5346 Handle -fdump-analyzer-exploded-nodes,
5347 -fdump-analyzer-exploded-nodes-2, and the
5348 "__analyzer_dump_exploded_nodes" builtin. */
5351 exploded_graph::dump_exploded_nodes () const
5354 /* Locate calls to __analyzer_dump_exploded_nodes. */
5355 // Print how many egs there are for them?
5356 /* Better: log them as we go, and record the exploded nodes
5359 /* Show every enode. */
5361 /* Gather them by stmt, so that we can more clearly see the
5362 "hotspots" requiring numerous exploded nodes. */
5364 /* Alternatively, simply throw them all into one big rich_location
5365 and see if the label-printing will sort it out...
5366 This requires them all to be in the same source file. */
5368 if (flag_dump_analyzer_exploded_nodes
)
5370 auto_timevar
tv (TV_ANALYZER_DUMP
);
5371 gcc_rich_location
richloc (UNKNOWN_LOCATION
);
5373 exploded_node
*enode
;
5374 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
5376 if (const gimple
*stmt
= enode
->get_stmt ())
5378 if (get_pure_location (richloc
.get_loc ()) == UNKNOWN_LOCATION
)
5379 richloc
.set_range (0, stmt
->location
, SHOW_RANGE_WITH_CARET
);
5381 richloc
.add_range (stmt
->location
,
5382 SHOW_RANGE_WITHOUT_CARET
,
5383 new enode_label (m_ext_state
, enode
));
5386 warning_at (&richloc
, 0, "%i exploded nodes", m_nodes
.length ());
5388 /* Repeat the warning without all the labels, so that message is visible
5389 (the other one may well have scrolled past the terminal limit). */
5390 warning_at (richloc
.get_loc (), 0,
5391 "%i exploded nodes", m_nodes
.length ());
5393 if (m_worklist
.length () > 0)
5394 warning_at (richloc
.get_loc (), 0,
5395 "worklist still contains %i nodes", m_worklist
.length ());
5398 /* Dump the egraph in textual form to a dump file. */
5399 if (flag_dump_analyzer_exploded_nodes_2
)
5401 auto_timevar
tv (TV_ANALYZER_DUMP
);
5403 = concat (dump_base_name
, ".eg.txt", NULL
);
5404 FILE *outf
= fopen (filename
, "w");
5406 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
5409 fprintf (outf
, "exploded graph for %s\n", dump_base_name
);
5410 fprintf (outf
, " nodes: %i\n", m_nodes
.length ());
5411 fprintf (outf
, " edges: %i\n", m_edges
.length ());
5414 exploded_node
*enode
;
5415 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
5417 fprintf (outf
, "\nEN %i:\n", enode
->m_index
);
5418 enode
->dump_succs_and_preds (outf
);
5420 enode
->get_point ().print (&pp
, format (true));
5421 fprintf (outf
, "%s\n", pp_formatted_text (&pp
));
5422 enode
->get_state ().dump_to_file (m_ext_state
, false, true, outf
);
5428 /* Dump the egraph in textual form to multiple dump files, one per enode. */
5429 if (flag_dump_analyzer_exploded_nodes_3
)
5431 auto_timevar
tv (TV_ANALYZER_DUMP
);
5434 exploded_node
*enode
;
5435 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
5438 = xasprintf ("%s.en-%i.txt", dump_base_name
, i
);
5439 FILE *outf
= fopen (filename
, "w");
5441 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
5444 fprintf (outf
, "EN %i:\n", enode
->m_index
);
5445 enode
->dump_succs_and_preds (outf
);
5447 enode
->get_point ().print (&pp
, format (true));
5448 fprintf (outf
, "%s\n", pp_formatted_text (&pp
));
5449 enode
->get_state ().dump_to_file (m_ext_state
, false, true, outf
);
5455 /* Emit a warning at any call to "__analyzer_dump_exploded_nodes",
5456 giving the number of processed exploded nodes for "before-stmt",
5457 and the IDs of processed, merger, and worklist enodes.
5459 We highlight the count of *processed* enodes since this is of most
5460 interest in DejaGnu tests for ensuring that state merger has
5463 We don't show the count of merger and worklist enodes, as this is
5464 more of an implementation detail of the merging/worklist that we
5465 don't want to bake into our expected DejaGnu messages. */
5468 exploded_node
*enode
;
5469 hash_set
<const gimple
*> seen
;
5470 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
5472 if (enode
->get_point ().get_kind () != PK_BEFORE_STMT
)
5475 if (const gimple
*stmt
= enode
->get_stmt ())
5476 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
5477 if (is_special_named_call_p (call
, "__analyzer_dump_exploded_nodes",
5480 if (seen
.contains (stmt
))
5483 auto_vec
<exploded_node
*> processed_enodes
;
5484 auto_vec
<exploded_node
*> merger_enodes
;
5485 auto_vec
<exploded_node
*> worklist_enodes
;
5486 /* This is O(N^2). */
5488 exploded_node
*other_enode
;
5489 FOR_EACH_VEC_ELT (m_nodes
, j
, other_enode
)
5491 if (other_enode
->get_point ().get_kind () != PK_BEFORE_STMT
)
5493 if (other_enode
->get_stmt () == stmt
)
5494 switch (other_enode
->get_status ())
5498 case exploded_node::STATUS_WORKLIST
:
5499 worklist_enodes
.safe_push (other_enode
);
5501 case exploded_node::STATUS_PROCESSED
:
5502 processed_enodes
.safe_push (other_enode
);
5504 case exploded_node::STATUS_MERGER
:
5505 merger_enodes
.safe_push (other_enode
);
5511 pp_character (&pp
, '[');
5512 print_enode_indices (&pp
, processed_enodes
);
5513 if (merger_enodes
.length () > 0)
5515 pp_string (&pp
, "] merger(s): [");
5516 print_enode_indices (&pp
, merger_enodes
);
5518 if (worklist_enodes
.length () > 0)
5520 pp_string (&pp
, "] worklist: [");
5521 print_enode_indices (&pp
, worklist_enodes
);
5523 pp_character (&pp
, ']');
5525 warning_n (stmt
->location
, 0, processed_enodes
.length (),
5526 "%i processed enode: %s",
5527 "%i processed enodes: %s",
5528 processed_enodes
.length (), pp_formatted_text (&pp
));
5531 /* If the argument is non-zero, then print all of the states
5532 of the various enodes. */
5533 tree t_arg
= fold (gimple_call_arg (call
, 0));
5534 if (TREE_CODE (t_arg
) != INTEGER_CST
)
5536 error_at (call
->location
,
5537 "integer constant required for arg 1");
5540 int i_arg
= TREE_INT_CST_LOW (t_arg
);
5543 exploded_node
*other_enode
;
5544 FOR_EACH_VEC_ELT (processed_enodes
, j
, other_enode
)
5546 fprintf (stderr
, "%i of %i: EN %i:\n",
5547 j
+ 1, processed_enodes
.length (),
5548 other_enode
->m_index
);
5549 other_enode
->dump_succs_and_preds (stderr
);
5551 other_enode
->get_state ().dump (m_ext_state
, false);
5558 DEBUG_FUNCTION exploded_node
*
5559 exploded_graph::get_node_by_index (int idx
) const
5561 exploded_node
*enode
= m_nodes
[idx
];
5562 gcc_assert (enode
->m_index
== idx
);
5566 /* Ensure that there is an exploded_node for a top-level call to FNDECL. */
5569 exploded_graph::on_escaped_function (tree fndecl
)
5571 logger
* const logger
= get_logger ();
5572 LOG_FUNC_1 (logger
, "%qE", fndecl
);
5574 cgraph_node
*cgnode
= cgraph_node::get (fndecl
);
5578 function
*fun
= cgnode
->get_fun ();
5582 if (!gimple_has_body_p (fndecl
))
5585 exploded_node
*enode
= add_function_entry (fun
);
5589 logger
->log ("created EN %i for %qE entrypoint",
5590 enode
->m_index
, fun
->decl
);
5592 logger
->log ("did not create enode for %qE entrypoint", fun
->decl
);
5596 /* A collection of classes for visualizing the callgraph in .dot form
5597 (as represented in the supergraph). */
5599 /* Forward decls. */
5600 class viz_callgraph_node
;
5601 class viz_callgraph_edge
;
5602 class viz_callgraph
;
5603 class viz_callgraph_cluster
;
5605 /* Traits for using "digraph.h" to visualize the callgraph. */
5607 struct viz_callgraph_traits
5609 typedef viz_callgraph_node node_t
;
5610 typedef viz_callgraph_edge edge_t
;
5611 typedef viz_callgraph graph_t
;
5614 dump_args_t (const exploded_graph
*eg
) : m_eg (eg
) {}
5615 const exploded_graph
*m_eg
;
5617 typedef viz_callgraph_cluster cluster_t
;
5620 /* Subclass of dnode representing a function within the callgraph. */
5622 class viz_callgraph_node
: public dnode
<viz_callgraph_traits
>
5624 friend class viz_callgraph
;
5627 viz_callgraph_node (function
*fun
, int index
)
5628 : m_fun (fun
), m_index (index
), m_num_supernodes (0), m_num_superedges (0)
5633 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const final override
5635 pretty_printer
*pp
= gv
->get_pp ();
5638 pp_printf (pp
, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
5640 pp_write_text_to_stream (pp
);
5642 pp_printf (pp
, "VCG: %i: %s", m_index
, function_name (m_fun
));
5645 pp_printf (pp
, "supernodes: %i\n", m_num_supernodes
);
5648 pp_printf (pp
, "superedges: %i\n", m_num_superedges
);
5654 exploded_node
*enode
;
5655 unsigned num_enodes
= 0;
5656 FOR_EACH_VEC_ELT (args
.m_eg
->m_nodes
, i
, enode
)
5658 if (enode
->get_point ().get_function () == m_fun
)
5661 pp_printf (pp
, "enodes: %i\n", num_enodes
);
5664 // TODO: also show the per-callstring breakdown
5665 const exploded_graph::call_string_data_map_t
*per_cs_data
5666 = args
.m_eg
->get_per_call_string_data ();
5667 for (exploded_graph::call_string_data_map_t::iterator iter
5668 = per_cs_data
->begin ();
5669 iter
!= per_cs_data
->end ();
5672 const call_string
*cs
= (*iter
).first
;
5673 //per_call_string_data *data = (*iter).second;
5675 FOR_EACH_VEC_ELT (args
.m_eg
->m_nodes
, i
, enode
)
5677 if (enode
->get_point ().get_function () == m_fun
5678 && &enode
->get_point ().get_call_string () == cs
)
5684 pp_printf (pp
, ": %i\n", num_enodes
);
5688 /* Show any summaries. */
5689 per_function_data
*data
= args
.m_eg
->get_per_function_data (m_fun
);
5693 pp_printf (pp
, "summaries: %i\n", data
->m_summaries
.length ());
5694 for (auto summary
: data
->m_summaries
)
5696 pp_printf (pp
, "\nsummary: %s:\n", summary
->get_desc ().get ());
5697 const extrinsic_state
&ext_state
= args
.m_eg
->get_ext_state ();
5698 const program_state
&state
= summary
->get_state ();
5699 state
.dump_to_pp (ext_state
, false, true, pp
);
5705 pp_write_text_as_dot_label_to_stream (pp
, /*for_record=*/true);
5706 pp_string (pp
, "\"];\n\n");
5710 void dump_dot_id (pretty_printer
*pp
) const
5712 pp_printf (pp
, "vcg_%i", m_index
);
5718 int m_num_supernodes
;
5719 int m_num_superedges
;
5722 /* Subclass of dedge representing a callgraph edge. */
5724 class viz_callgraph_edge
: public dedge
<viz_callgraph_traits
>
5727 viz_callgraph_edge (viz_callgraph_node
*src
, viz_callgraph_node
*dest
)
5728 : dedge
<viz_callgraph_traits
> (src
, dest
)
5731 void dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
5734 pretty_printer
*pp
= gv
->get_pp ();
5736 const char *style
= "\"solid,bold\"";
5737 const char *color
= "black";
5739 const char *constraint
= "true";
5741 m_src
->dump_dot_id (pp
);
5742 pp_string (pp
, " -> ");
5743 m_dest
->dump_dot_id (pp
);
5745 (" [style=%s, color=%s, weight=%d, constraint=%s,"
5747 style
, color
, weight
, constraint
);
5748 pp_printf (pp
, "\"];\n");
5752 /* Subclass of digraph representing the callgraph. */
5754 class viz_callgraph
: public digraph
<viz_callgraph_traits
>
5757 viz_callgraph (const supergraph
&sg
);
5759 viz_callgraph_node
*get_vcg_node_for_function (function
*fun
)
5761 return *m_map
.get (fun
);
5764 viz_callgraph_node
*get_vcg_node_for_snode (supernode
*snode
)
5766 return get_vcg_node_for_function (snode
->m_fun
);
5770 hash_map
<function
*, viz_callgraph_node
*> m_map
;
5773 /* Placeholder subclass of cluster. */
5775 class viz_callgraph_cluster
: public cluster
<viz_callgraph_traits
>
5779 /* viz_callgraph's ctor. */
5781 viz_callgraph::viz_callgraph (const supergraph
&sg
)
5784 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5786 function
*fun
= node
->get_fun ();
5787 viz_callgraph_node
*vcg_node
5788 = new viz_callgraph_node (fun
, m_nodes
.length ());
5789 m_map
.put (fun
, vcg_node
);
5790 add_node (vcg_node
);
5795 FOR_EACH_VEC_ELT (sg
.m_edges
, i
, sedge
)
5797 viz_callgraph_node
*vcg_src
= get_vcg_node_for_snode (sedge
->m_src
);
5799 get_vcg_node_for_function (vcg_src
->m_fun
)->m_num_superedges
++;
5800 if (sedge
->dyn_cast_call_superedge ())
5802 viz_callgraph_node
*vcg_dest
= get_vcg_node_for_snode (sedge
->m_dest
);
5803 viz_callgraph_edge
*vcg_edge
5804 = new viz_callgraph_edge (vcg_src
, vcg_dest
);
5805 add_edge (vcg_edge
);
5810 FOR_EACH_VEC_ELT (sg
.m_nodes
, i
, snode
)
5813 get_vcg_node_for_function (snode
->m_fun
)->m_num_supernodes
++;
5817 /* Dump the callgraph to FILENAME. */
5820 dump_callgraph (const supergraph
&sg
, const char *filename
,
5821 const exploded_graph
*eg
)
5823 FILE *outf
= fopen (filename
, "w");
5828 viz_callgraph
vcg (sg
);
5829 vcg
.dump_dot (filename
, NULL
, viz_callgraph_traits::dump_args_t (eg
));
5834 /* Dump the callgraph to "<srcfile>.callgraph.dot". */
5837 dump_callgraph (const supergraph
&sg
, const exploded_graph
*eg
)
5839 auto_timevar
tv (TV_ANALYZER_DUMP
);
5840 char *filename
= concat (dump_base_name
, ".callgraph.dot", NULL
);
5841 dump_callgraph (sg
, filename
, eg
);
5845 /* Subclass of dot_annotator for implementing
5846 DUMP_BASE_NAME.supergraph-eg.dot, a post-analysis dump of the supergraph.
5848 Annotate the supergraph nodes by printing the exploded nodes in concise
5849 form within them, next to their pertinent statements where appropriate,
5850 colorizing the exploded nodes based on sm-state.
5851 Also show saved diagnostics within the exploded nodes, giving information
5852 on whether they were feasible, and, if infeasible, where the problem
5855 class exploded_graph_annotator
: public dot_annotator
5858 exploded_graph_annotator (const exploded_graph
&eg
)
5861 /* Avoid O(N^2) by prepopulating m_enodes_per_snodes. */
5864 FOR_EACH_VEC_ELT (eg
.get_supergraph ().m_nodes
, i
, snode
)
5865 m_enodes_per_snodes
.safe_push (new auto_vec
<exploded_node
*> ());
5866 exploded_node
*enode
;
5867 FOR_EACH_VEC_ELT (m_eg
.m_nodes
, i
, enode
)
5868 if (enode
->get_supernode ())
5869 m_enodes_per_snodes
[enode
->get_supernode ()->m_index
]->safe_push (enode
);
5872 /* Show exploded nodes for BEFORE_SUPERNODE points before N. */
5873 bool add_node_annotations (graphviz_out
*gv
, const supernode
&n
,
5875 const final override
5880 pretty_printer
*pp
= gv
->get_pp ();
5883 pp_string (pp
, "BEFORE");
5884 pp_printf (pp
, " (scc: %i)", m_eg
.get_scc_id (n
));
5888 exploded_node
*enode
;
5889 bool had_enode
= false;
5890 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[n
.m_index
], i
, enode
)
5892 gcc_assert (enode
->get_supernode () == &n
);
5893 const program_point
&point
= enode
->get_point ();
5894 if (point
.get_kind () != PK_BEFORE_SUPERNODE
)
5896 print_enode (gv
, enode
);
5900 pp_string (pp
, "<TD BGCOLOR=\"red\">UNREACHED</TD>");
5906 /* Show exploded nodes for STMT. */
5907 void add_stmt_annotations (graphviz_out
*gv
, const gimple
*stmt
,
5909 const final override
5913 pretty_printer
*pp
= gv
->get_pp ();
5915 const supernode
*snode
5916 = m_eg
.get_supergraph ().get_supernode_for_stmt (stmt
);
5918 exploded_node
*enode
;
5919 bool had_td
= false;
5920 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[snode
->m_index
], i
, enode
)
5922 const program_point
&point
= enode
->get_point ();
5923 if (point
.get_kind () != PK_BEFORE_STMT
)
5925 if (point
.get_stmt () != stmt
)
5927 print_enode (gv
, enode
);
5938 /* Show exploded nodes for AFTER_SUPERNODE points after N. */
5939 bool add_after_node_annotations (graphviz_out
*gv
, const supernode
&n
)
5940 const final override
5943 pretty_printer
*pp
= gv
->get_pp ();
5946 pp_string (pp
, "AFTER");
5950 exploded_node
*enode
;
5951 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[n
.m_index
], i
, enode
)
5953 gcc_assert (enode
->get_supernode () == &n
);
5954 const program_point
&point
= enode
->get_point ();
5955 if (point
.get_kind () != PK_AFTER_SUPERNODE
)
5957 print_enode (gv
, enode
);
5965 /* Concisely print a TD element for ENODE, showing the index, status,
5966 and any saved_diagnostics at the enode. Colorize it to show sm-state.
5968 Ideally we'd dump ENODE's state here, hidden behind some kind of
5969 interactive disclosure method like a tooltip, so that the states
5970 can be explored without overwhelming the graph.
5971 However, I wasn't able to get graphviz/xdot to show tooltips on
5972 individual elements within a HTML-like label. */
5973 void print_enode (graphviz_out
*gv
, const exploded_node
*enode
) const
5975 pretty_printer
*pp
= gv
->get_pp ();
5976 pp_printf (pp
, "<TD BGCOLOR=\"%s\">",
5977 enode
->get_dot_fillcolor ());
5978 pp_printf (pp
, "<TABLE BORDER=\"0\">");
5980 pp_printf (pp
, "EN: %i", enode
->m_index
);
5981 switch (enode
->get_status ())
5985 case exploded_node::STATUS_WORKLIST
:
5986 pp_string (pp
, "(W)");
5988 case exploded_node::STATUS_PROCESSED
:
5990 case exploded_node::STATUS_MERGER
:
5991 pp_string (pp
, "(M)");
5993 case exploded_node::STATUS_BULK_MERGED
:
5994 pp_string (pp
, "(BM)");
5999 /* Dump any saved_diagnostics at this enode. */
6000 for (unsigned i
= 0; i
< enode
->get_num_diagnostics (); i
++)
6002 const saved_diagnostic
*sd
= enode
->get_saved_diagnostic (i
);
6003 print_saved_diagnostic (gv
, sd
);
6005 pp_printf (pp
, "</TABLE>");
6006 pp_printf (pp
, "</TD>");
6009 /* Print a TABLE element for SD, showing the kind, the length of the
6010 exploded_path, whether the path was feasible, and if infeasible,
6011 what the problem was. */
6012 void print_saved_diagnostic (graphviz_out
*gv
,
6013 const saved_diagnostic
*sd
) const
6015 pretty_printer
*pp
= gv
->get_pp ();
6017 pp_printf (pp
, "<TABLE BORDER=\"0\">");
6019 pp_string (pp
, "<TD BGCOLOR=\"green\">");
6020 pp_printf (pp
, "DIAGNOSTIC: %s", sd
->m_d
->get_kind ());
6023 if (sd
->get_best_epath ())
6024 pp_printf (pp
, "epath length: %i", sd
->get_epath_length ());
6026 pp_printf (pp
, "no best epath");
6028 if (const feasibility_problem
*p
= sd
->get_feasibility_problem ())
6031 pp_printf (pp
, "INFEASIBLE at eedge %i: EN:%i -> EN:%i",
6033 p
->m_eedge
.m_src
->m_index
,
6034 p
->m_eedge
.m_dest
->m_index
);
6035 pp_write_text_as_html_like_dot_to_stream (pp
);
6038 p
->m_eedge
.m_sedge
->dump (pp
);
6039 pp_write_text_as_html_like_dot_to_stream (pp
);
6042 pp_gimple_stmt_1 (pp
, p
->m_last_stmt
, 0, (dump_flags_t
)0);
6043 pp_write_text_as_html_like_dot_to_stream (pp
);
6045 /* Ideally we'd print p->m_model here; see the notes above about
6048 pp_printf (pp
, "</TABLE>");
6052 const exploded_graph
&m_eg
;
6053 auto_delete_vec
<auto_vec
<exploded_node
*> > m_enodes_per_snodes
;
6056 /* Implement -fdump-analyzer-json. */
6059 dump_analyzer_json (const supergraph
&sg
,
6060 const exploded_graph
&eg
)
6062 auto_timevar
tv (TV_ANALYZER_DUMP
);
6063 char *filename
= concat (dump_base_name
, ".analyzer.json.gz", NULL
);
6064 gzFile output
= gzopen (filename
, "w");
6067 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
6072 json::object
*toplev_obj
= new json::object ();
6073 toplev_obj
->set ("sgraph", sg
.to_json ());
6074 toplev_obj
->set ("egraph", eg
.to_json ());
6077 toplev_obj
->print (&pp
, flag_diagnostics_json_formatting
);
6078 pp_formatted_text (&pp
);
6082 if (gzputs (output
, pp_formatted_text (&pp
)) == EOF
6083 || gzclose (output
))
6084 error_at (UNKNOWN_LOCATION
, "error writing %qs", filename
);
6089 /* Concrete subclass of plugin_analyzer_init_iface, allowing plugins
6090 to register new state machines. */
6092 class plugin_analyzer_init_impl
: public plugin_analyzer_init_iface
6095 plugin_analyzer_init_impl (auto_delete_vec
<state_machine
> *checkers
,
6096 known_function_manager
*known_fn_mgr
,
6098 : m_checkers (checkers
),
6099 m_known_fn_mgr (known_fn_mgr
),
6103 void register_state_machine (std::unique_ptr
<state_machine
> sm
) final override
6105 LOG_SCOPE (m_logger
);
6106 m_checkers
->safe_push (sm
.release ());
6109 void register_known_function (const char *name
,
6110 std::unique_ptr
<known_function
> kf
) final override
6112 LOG_SCOPE (m_logger
);
6113 m_known_fn_mgr
->add (name
, std::move (kf
));
6116 logger
*get_logger () const final override
6122 auto_delete_vec
<state_machine
> *m_checkers
;
6123 known_function_manager
*m_known_fn_mgr
;
6127 /* Run the analysis "engine". */
6130 impl_run_checkers (logger
*logger
)
6136 logger
->log ("BITS_BIG_ENDIAN: %i", BITS_BIG_ENDIAN
? 1 : 0);
6137 logger
->log ("BYTES_BIG_ENDIAN: %i", BYTES_BIG_ENDIAN
? 1 : 0);
6138 logger
->log ("WORDS_BIG_ENDIAN: %i", WORDS_BIG_ENDIAN
? 1 : 0);
6139 log_stashed_constants (logger
);
6142 /* If using LTO, ensure that the cgraph nodes have function bodies. */
6144 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
6145 node
->get_untransformed_body ();
6147 /* Create the supergraph. */
6148 supergraph
sg (logger
);
6150 engine
eng (&sg
, logger
);
6152 state_purge_map
*purge_map
= NULL
;
6154 if (flag_analyzer_state_purge
)
6155 purge_map
= new state_purge_map (sg
, eng
.get_model_manager (), logger
);
6157 if (flag_dump_analyzer_supergraph
)
6159 /* Dump supergraph pre-analysis. */
6160 auto_timevar
tv (TV_ANALYZER_DUMP
);
6161 char *filename
= concat (dump_base_name
, ".supergraph.dot", NULL
);
6162 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, NULL
);
6163 sg
.dump_dot (filename
, args
);
6167 if (flag_dump_analyzer_state_purge
)
6169 auto_timevar
tv (TV_ANALYZER_DUMP
);
6170 state_purge_annotator
a (purge_map
);
6171 char *filename
= concat (dump_base_name
, ".state-purge.dot", NULL
);
6172 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, &a
);
6173 sg
.dump_dot (filename
, args
);
6177 auto_delete_vec
<state_machine
> checkers
;
6178 make_checkers (checkers
, logger
);
6180 register_known_functions (*eng
.get_known_function_manager (),
6181 *eng
.get_model_manager ());
6183 plugin_analyzer_init_impl
data (&checkers
,
6184 eng
.get_known_function_manager (),
6186 invoke_plugin_callbacks (PLUGIN_ANALYZER_INIT
, &data
);
6192 FOR_EACH_VEC_ELT (checkers
, i
, sm
)
6193 logger
->log ("checkers[%i]: %s", i
, sm
->get_name ());
6196 /* Extrinsic state shared by nodes in the graph. */
6197 const extrinsic_state
ext_state (checkers
, &eng
, logger
);
6199 const analysis_plan
plan (sg
, logger
);
6201 /* The exploded graph. */
6202 exploded_graph
eg (sg
, logger
, ext_state
, purge_map
, plan
,
6203 analyzer_verbosity
);
6205 /* Add entrypoints to the graph for externally-callable functions. */
6206 eg
.build_initial_worklist ();
6208 /* Now process the worklist, exploring the <point, state> graph. */
6209 eg
.process_worklist ();
6211 if (warn_analyzer_infinite_loop
)
6212 eg
.detect_infinite_loops ();
6214 if (flag_dump_analyzer_exploded_graph
)
6216 auto_timevar
tv (TV_ANALYZER_DUMP
);
6218 = concat (dump_base_name
, ".eg.dot", NULL
);
6219 exploded_graph::dump_args_t
args (eg
);
6221 eg
.dump_dot (filename
, &c
, args
);
6225 /* Now emit any saved diagnostics. */
6226 eg
.get_diagnostic_manager ().emit_saved_diagnostics (eg
);
6228 eg
.dump_exploded_nodes ();
6232 if (flag_dump_analyzer_callgraph
)
6233 dump_callgraph (sg
, &eg
);
6235 if (flag_dump_analyzer_supergraph
)
6237 /* Dump post-analysis form of supergraph. */
6238 auto_timevar
tv (TV_ANALYZER_DUMP
);
6239 char *filename
= concat (dump_base_name
, ".supergraph-eg.dot", NULL
);
6240 exploded_graph_annotator
a (eg
);
6241 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, &a
);
6242 sg
.dump_dot (filename
, args
);
6246 if (flag_dump_analyzer_json
)
6247 dump_analyzer_json (sg
, eg
);
6249 if (flag_dump_analyzer_untracked
)
6250 eng
.get_model_manager ()->dump_untracked_regions ();
6255 /* Handle -fdump-analyzer and -fdump-analyzer-stderr. */
6256 static FILE *dump_fout
= NULL
;
6258 /* Track if we're responsible for closing dump_fout. */
6259 static bool owns_dump_fout
= false;
6261 /* If dumping is enabled, attempt to create dump_fout if it hasn't already
6262 been opened. Return it. */
6265 get_or_create_any_logfile ()
6269 if (flag_dump_analyzer_stderr
)
6271 else if (flag_dump_analyzer
)
6273 char *dump_filename
= concat (dump_base_name
, ".analyzer.txt", NULL
);
6274 dump_fout
= fopen (dump_filename
, "w");
6275 free (dump_filename
);
6277 owns_dump_fout
= true;
6283 /* External entrypoint to the analysis "engine".
6284 Set up any dumps, then call impl_run_checkers. */
6289 /* Save input_location. */
6290 location_t saved_input_location
= input_location
;
6293 log_user
the_logger (NULL
);
6294 get_or_create_any_logfile ();
6296 the_logger
.set_logger (new logger (dump_fout
, 0, 0,
6297 *global_dc
->printer
));
6298 LOG_SCOPE (the_logger
.get_logger ());
6300 impl_run_checkers (the_logger
.get_logger ());
6302 /* end of lifetime of the_logger (so that dump file is closed after the
6303 various dtors run). */
6309 owns_dump_fout
= false;
6313 /* Restore input_location. Subsequent passes may assume that input_location
6314 is some arbitrary value *not* in the block tree, which might be violated
6315 if we didn't restore it. */
6316 input_location
= saved_input_location
;
6321 #endif /* #if ENABLE_ANALYZER */