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
, m_ext_state
, 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
);
1500 gcc_assert (called_fn
);
1501 return replay_call_summaries (eg
,
1503 as_a
<const gcall
*> (stmt
),
1512 bool unknown_side_effects
= false;
1513 bool terminate_path
= false;
1515 on_stmt_pre (eg
, stmt
, state
, &terminate_path
,
1516 &unknown_side_effects
, &ctxt
);
1519 return on_stmt_flags::terminate_path ();
1523 FOR_EACH_VEC_ELT (old_state
.m_checker_states
, sm_idx
, smap
)
1525 const state_machine
&sm
= eg
.get_ext_state ().get_sm (sm_idx
);
1526 const sm_state_map
*old_smap
1527 = old_state
.m_checker_states
[sm_idx
];
1528 sm_state_map
*new_smap
= state
->m_checker_states
[sm_idx
];
1529 impl_sm_context
sm_ctxt (eg
, sm_idx
, sm
, this, &old_state
, state
,
1530 old_smap
, new_smap
, path_ctxt
, NULL
,
1531 unknown_side_effects
);
1533 /* Allow the state_machine to handle the stmt. */
1534 if (sm
.on_stmt (&sm_ctxt
, snode
, stmt
))
1535 unknown_side_effects
= false;
1538 if (path_ctxt
->terminate_path_p ())
1539 return on_stmt_flags::terminate_path ();
1541 on_stmt_post (stmt
, state
, unknown_side_effects
, &ctxt
);
1543 return on_stmt_flags ();
1546 /* Handle the pre-sm-state part of STMT, modifying STATE in-place.
1547 Write true to *OUT_TERMINATE_PATH if the path should be terminated.
1548 Write true to *OUT_UNKNOWN_SIDE_EFFECTS if the stmt has unknown
1552 exploded_node::on_stmt_pre (exploded_graph
&eg
,
1554 program_state
*state
,
1555 bool *out_terminate_path
,
1556 bool *out_unknown_side_effects
,
1557 region_model_context
*ctxt
)
1559 /* Handle special-case calls that require the full program_state. */
1560 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
1562 if (is_special_named_call_p (call
, "__analyzer_dump", 0))
1564 /* Handle the builtin "__analyzer_dump" by dumping state
1566 state
->dump (eg
.get_ext_state (), true);
1569 else if (is_special_named_call_p (call
, "__analyzer_dump_state", 2))
1571 state
->impl_call_analyzer_dump_state (call
, eg
.get_ext_state (),
1575 else if (is_setjmp_call_p (call
))
1577 state
->m_region_model
->on_setjmp (call
, this, ctxt
);
1579 ctxt
->maybe_did_work ();
1582 else if (is_longjmp_call_p (call
))
1584 on_longjmp (eg
, call
, state
, ctxt
);
1585 *out_terminate_path
= true;
1587 ctxt
->maybe_did_work ();
1592 /* Otherwise, defer to m_region_model. */
1593 state
->m_region_model
->on_stmt_pre (stmt
,
1594 out_unknown_side_effects
,
1598 /* Handle the post-sm-state part of STMT, modifying STATE in-place. */
1601 exploded_node::on_stmt_post (const gimple
*stmt
,
1602 program_state
*state
,
1603 bool unknown_side_effects
,
1604 region_model_context
*ctxt
)
1606 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
1607 state
->m_region_model
->on_call_post (call
, unknown_side_effects
, ctxt
);
1610 /* A concrete call_info subclass representing a replay of a call summary. */
1612 class call_summary_edge_info
: public call_info
1615 call_summary_edge_info (const call_details
&cd
,
1616 const function
&called_fn
,
1617 call_summary
*summary
,
1618 const extrinsic_state
&ext_state
)
1619 : call_info (cd
, called_fn
),
1620 m_called_fn (called_fn
),
1621 m_summary (summary
),
1622 m_ext_state (ext_state
)
1625 bool update_state (program_state
*state
,
1626 const exploded_edge
*,
1627 region_model_context
*ctxt
) const final override
1629 /* Update STATE based on summary_end_state. */
1630 call_details
cd (get_call_details (state
->m_region_model
, ctxt
));
1631 call_summary_replay
r (cd
, m_called_fn
, m_summary
, m_ext_state
);
1632 const program_state
&summary_end_state
= m_summary
->get_state ();
1633 return state
->replay_call_summary (r
, summary_end_state
);
1636 bool update_model (region_model
*model
,
1637 const exploded_edge
*,
1638 region_model_context
*ctxt
) const final override
1640 /* Update STATE based on summary_end_state. */
1641 call_details
cd (get_call_details (model
, ctxt
));
1642 call_summary_replay
r (cd
, m_called_fn
, m_summary
, m_ext_state
);
1643 const program_state
&summary_end_state
= m_summary
->get_state ();
1644 model
->replay_call_summary (r
, *summary_end_state
.m_region_model
);
1648 label_text
get_desc (bool /*can_colorize*/) const final override
1650 return m_summary
->get_desc ();
1654 const function
&m_called_fn
;
1655 call_summary
*m_summary
;
1656 const extrinsic_state
&m_ext_state
;
1659 /* Use PATH_CTXT to bifurcate, which when handled will add custom edges
1660 for a replay of the various feasible summaries in CALLED_FN_DATA. */
1662 exploded_node::on_stmt_flags
1663 exploded_node::replay_call_summaries (exploded_graph
&eg
,
1664 const supernode
*snode
,
1665 const gcall
*call_stmt
,
1666 program_state
*state
,
1667 path_context
*path_ctxt
,
1668 const function
&called_fn
,
1669 per_function_data
&called_fn_data
,
1670 region_model_context
*ctxt
)
1672 logger
*logger
= eg
.get_logger ();
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 const 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 (summary
);
1706 logger
->log ("using %s as summary for call to %qE from %qE",
1707 summary
->get_desc ().get (),
1709 snode
->get_function ()->decl
);
1710 const extrinsic_state
&ext_state
= eg
.get_ext_state ();
1711 const program_state
&summary_end_state
= summary
->get_state ();
1714 pretty_printer
*pp
= logger
->get_printer ();
1716 logger
->start_log_line ();
1717 pp_string (pp
, "callsite state: ");
1718 old_state
->dump_to_pp (ext_state
, true, false, pp
);
1719 logger
->end_log_line ();
1721 logger
->start_log_line ();
1722 pp_string (pp
, "summary end state: ");
1723 summary_end_state
.dump_to_pp (ext_state
, true, false, pp
);
1724 logger
->end_log_line ();
1727 program_state
new_state (*old_state
);
1729 call_details
cd (call_stmt
, new_state
.m_region_model
, ctxt
);
1730 call_summary_replay
r (cd
, called_fn
, summary
, ext_state
);
1733 path_ctxt
->bifurcate (make_unique
<call_summary_edge_info
> (cd
,
1740 /* Consider the effect of following superedge SUCC from this node.
1742 Return true if it's feasible to follow the edge, or false
1745 Examples: if it's the "true" branch within
1746 a CFG and we know the conditional is false, we know it's infeasible.
1747 If it's one of multiple interprocedual "return" edges, then only
1748 the edge back to the most recent callsite is feasible.
1750 Update NEXT_STATE accordingly (e.g. to record that a condition was
1751 true or false, or that the NULL-ness of a pointer has been checked,
1752 pushing/popping stack frames, etc).
1754 Update NEXT_POINT accordingly (updating the call string). */
1757 exploded_node::on_edge (exploded_graph
&eg
,
1758 const superedge
*succ
,
1759 program_point
*next_point
,
1760 program_state
*next_state
,
1761 uncertainty_t
*uncertainty
)
1763 LOG_FUNC (eg
.get_logger ());
1765 if (!next_point
->on_edge (eg
, succ
))
1768 if (!next_state
->on_edge (eg
, this, succ
, uncertainty
))
1774 /* Verify that the stack at LONGJMP_POINT is still valid, given a call
1775 to "setjmp" at SETJMP_POINT - the stack frame that "setjmp" was
1776 called in must still be valid.
1778 Caveat: this merely checks the call_strings in the points; it doesn't
1779 detect the case where a frame returns and is then called again. */
1782 valid_longjmp_stack_p (const program_point
&longjmp_point
,
1783 const program_point
&setjmp_point
)
1785 const call_string
&cs_at_longjmp
= longjmp_point
.get_call_string ();
1786 const call_string
&cs_at_setjmp
= setjmp_point
.get_call_string ();
1788 if (cs_at_longjmp
.length () < cs_at_setjmp
.length ())
1791 /* Check that the call strings match, up to the depth of the
1793 for (unsigned depth
= 0; depth
< cs_at_setjmp
.length (); depth
++)
1794 if (cs_at_longjmp
[depth
] != cs_at_setjmp
[depth
])
1800 /* A pending_diagnostic subclass for complaining about bad longjmps,
1801 where the enclosing function of the "setjmp" has returned (and thus
1802 the stack frame no longer exists). */
1804 class stale_jmp_buf
: public pending_diagnostic_subclass
<stale_jmp_buf
>
1807 stale_jmp_buf (const gcall
*setjmp_call
, const gcall
*longjmp_call
,
1808 const program_point
&setjmp_point
)
1809 : m_setjmp_call (setjmp_call
), m_longjmp_call (longjmp_call
),
1810 m_setjmp_point (setjmp_point
), m_stack_pop_event (NULL
)
1813 int get_controlling_option () const final override
1815 return OPT_Wanalyzer_stale_setjmp_buffer
;
1818 bool emit (diagnostic_emission_context
&ctxt
) final override
1820 return ctxt
.warn ("%qs called after enclosing function of %qs has returned",
1821 get_user_facing_name (m_longjmp_call
),
1822 get_user_facing_name (m_setjmp_call
));
1825 const char *get_kind () const final override
1826 { return "stale_jmp_buf"; }
1828 bool operator== (const stale_jmp_buf
&other
) const
1830 return (m_setjmp_call
== other
.m_setjmp_call
1831 && m_longjmp_call
== other
.m_longjmp_call
);
1835 maybe_add_custom_events_for_superedge (const exploded_edge
&eedge
,
1836 checker_path
*emission_path
)
1839 /* Detect exactly when the stack first becomes invalid,
1840 and issue an event then. */
1841 if (m_stack_pop_event
)
1843 const exploded_node
*src_node
= eedge
.m_src
;
1844 const program_point
&src_point
= src_node
->get_point ();
1845 const exploded_node
*dst_node
= eedge
.m_dest
;
1846 const program_point
&dst_point
= dst_node
->get_point ();
1847 if (valid_longjmp_stack_p (src_point
, m_setjmp_point
)
1848 && !valid_longjmp_stack_p (dst_point
, m_setjmp_point
))
1850 /* Compare with diagnostic_manager::add_events_for_superedge. */
1851 const int src_stack_depth
= src_point
.get_stack_depth ();
1852 m_stack_pop_event
= new precanned_custom_event
1853 (event_loc_info (src_point
.get_location (),
1854 src_point
.get_fndecl (),
1856 "stack frame is popped here, invalidating saved environment");
1857 emission_path
->add_event
1858 (std::unique_ptr
<custom_event
> (m_stack_pop_event
));
1864 label_text
describe_final_event (const evdesc::final_event
&ev
) final override
1866 if (m_stack_pop_event
)
1867 return ev
.formatted_print
1868 ("%qs called after enclosing function of %qs returned at %@",
1869 get_user_facing_name (m_longjmp_call
),
1870 get_user_facing_name (m_setjmp_call
),
1871 m_stack_pop_event
->get_id_ptr ());
1873 return ev
.formatted_print
1874 ("%qs called after enclosing function of %qs has returned",
1875 get_user_facing_name (m_longjmp_call
),
1876 get_user_facing_name (m_setjmp_call
));;
1881 const gcall
*m_setjmp_call
;
1882 const gcall
*m_longjmp_call
;
1883 program_point m_setjmp_point
;
1884 custom_event
*m_stack_pop_event
;
1887 /* Handle LONGJMP_CALL, a call to longjmp or siglongjmp.
1889 Attempt to locate where setjmp/sigsetjmp was called on the jmp_buf and build
1890 an exploded_node and exploded_edge to it representing a rewind to that frame,
1891 handling the various kinds of failure that can occur. */
1894 exploded_node::on_longjmp (exploded_graph
&eg
,
1895 const gcall
*longjmp_call
,
1896 program_state
*new_state
,
1897 region_model_context
*ctxt
)
1899 tree buf_ptr
= gimple_call_arg (longjmp_call
, 0);
1900 gcc_assert (POINTER_TYPE_P (TREE_TYPE (buf_ptr
)));
1902 region_model
*new_region_model
= new_state
->m_region_model
;
1903 const svalue
*buf_ptr_sval
= new_region_model
->get_rvalue (buf_ptr
, ctxt
);
1904 const region
*buf
= new_region_model
->deref_rvalue (buf_ptr_sval
, buf_ptr
,
1907 const svalue
*buf_content_sval
1908 = new_region_model
->get_store_value (buf
, ctxt
);
1909 const setjmp_svalue
*setjmp_sval
1910 = buf_content_sval
->dyn_cast_setjmp_svalue ();
1914 const setjmp_record tmp_setjmp_record
= setjmp_sval
->get_setjmp_record ();
1916 /* Build a custom enode and eedge for rewinding from the longjmp/siglongjmp
1917 call back to the setjmp/sigsetjmp. */
1918 rewind_info_t
rewind_info (tmp_setjmp_record
, longjmp_call
);
1920 const gcall
*setjmp_call
= rewind_info
.get_setjmp_call ();
1921 const program_point
&setjmp_point
= rewind_info
.get_setjmp_point ();
1923 const program_point
&longjmp_point
= get_point ();
1925 /* Verify that the setjmp's call_stack hasn't been popped. */
1926 if (!valid_longjmp_stack_p (longjmp_point
, setjmp_point
))
1928 ctxt
->warn (make_unique
<stale_jmp_buf
> (setjmp_call
,
1934 gcc_assert (longjmp_point
.get_stack_depth ()
1935 >= setjmp_point
.get_stack_depth ());
1937 /* Update the state for use by the destination node. */
1939 /* Stash the current number of diagnostics so that we can update
1940 any that this adds to show where the longjmp is rewinding to. */
1942 diagnostic_manager
*dm
= &eg
.get_diagnostic_manager ();
1943 unsigned prev_num_diagnostics
= dm
->get_num_diagnostics ();
1945 new_region_model
->on_longjmp (longjmp_call
, setjmp_call
,
1946 setjmp_point
.get_stack_depth (), ctxt
);
1948 /* Detect leaks in the new state relative to the old state. */
1949 program_state::detect_leaks (get_state (), *new_state
, NULL
,
1950 eg
.get_ext_state (), ctxt
);
1952 program_point next_point
1953 = program_point::after_supernode (setjmp_point
.get_supernode (),
1954 setjmp_point
.get_call_string ());
1957 = eg
.get_or_create_node (next_point
, *new_state
, this);
1959 /* Create custom exploded_edge for a longjmp. */
1962 exploded_edge
*eedge
1963 = eg
.add_edge (const_cast<exploded_node
*> (this), next
, NULL
, true,
1964 make_unique
<rewind_info_t
> (tmp_setjmp_record
,
1967 /* For any diagnostics that were queued here (such as leaks) we want
1968 the checker_path to show the rewinding events after the "final event"
1969 so that the user sees where the longjmp is rewinding to (otherwise the
1970 path is meaningless).
1972 For example, we want to emit something like:
1974 | NN | longjmp (env, 1);
1975 | | ~~~~~~~~~~~~~~~~
1977 | | (10) 'ptr' leaks here; was allocated at (7)
1978 | | (11) rewinding from 'longjmp' in 'inner'...
1984 | NN | i = setjmp(env);
1987 | | (12) ...to 'setjmp' in 'outer' (saved at (2))
1989 where the "final" event above is event (10), but we want to append
1990 events (11) and (12) afterwards.
1992 Do this by setting m_trailing_eedge on any diagnostics that were
1994 unsigned num_diagnostics
= dm
->get_num_diagnostics ();
1995 for (unsigned i
= prev_num_diagnostics
; i
< num_diagnostics
; i
++)
1997 saved_diagnostic
*sd
= dm
->get_saved_diagnostic (i
);
1998 sd
->m_trailing_eedge
= eedge
;
2003 /* Subroutine of exploded_graph::process_node for finding the successors
2004 of the supernode for a function exit basic block.
2006 Ensure that pop_frame is called, potentially queuing diagnostics about
2010 exploded_node::detect_leaks (exploded_graph
&eg
)
2012 LOG_FUNC_1 (eg
.get_logger (), "EN: %i", m_index
);
2014 gcc_assert (get_point ().get_supernode ()->return_p ());
2016 /* If we're not a "top-level" function, do nothing; pop_frame
2017 will be called when handling the return superedge. */
2018 if (get_point ().get_stack_depth () > 1)
2021 /* We have a "top-level" function. */
2022 gcc_assert (get_point ().get_stack_depth () == 1);
2024 const program_state
&old_state
= get_state ();
2026 /* Work with a temporary copy of the state: pop the frame, and see
2027 what leaks (via purge_unused_svalues). */
2028 program_state
new_state (old_state
);
2030 gcc_assert (new_state
.m_region_model
);
2032 uncertainty_t uncertainty
;
2033 impl_region_model_context
ctxt (eg
, this,
2034 &old_state
, &new_state
, &uncertainty
, NULL
,
2036 const svalue
*result
= NULL
;
2037 new_state
.m_region_model
->pop_frame (NULL
, &result
, &ctxt
);
2038 program_state::detect_leaks (old_state
, new_state
, result
,
2039 eg
.get_ext_state (), &ctxt
);
2042 /* Dump the successors and predecessors of this enode to OUTF. */
2045 exploded_node::dump_succs_and_preds (FILE *outf
) const
2050 auto_vec
<exploded_node
*> preds (m_preds
.length ());
2051 FOR_EACH_VEC_ELT (m_preds
, i
, e
)
2052 preds
.quick_push (e
->m_src
);
2054 print_enode_indices (&pp
, preds
);
2055 fprintf (outf
, "preds: %s\n",
2056 pp_formatted_text (&pp
));
2059 auto_vec
<exploded_node
*> succs (m_succs
.length ());
2060 FOR_EACH_VEC_ELT (m_succs
, i
, e
)
2061 succs
.quick_push (e
->m_dest
);
2063 print_enode_indices (&pp
, succs
);
2064 fprintf (outf
, "succs: %s\n",
2065 pp_formatted_text (&pp
));
2069 /* class dynamic_call_info_t : public custom_edge_info. */
2071 /* Implementation of custom_edge_info::update_model vfunc
2072 for dynamic_call_info_t.
2074 Update state for a dynamically discovered call (or return), by pushing
2075 or popping the a frame for the appropriate function. */
2078 dynamic_call_info_t::update_model (region_model
*model
,
2079 const exploded_edge
*eedge
,
2080 region_model_context
*ctxt
) const
2083 if (m_is_returning_call
)
2084 model
->update_for_return_gcall (m_dynamic_call
, ctxt
);
2087 function
*callee
= eedge
->m_dest
->get_function ();
2088 model
->update_for_gcall (m_dynamic_call
, ctxt
, callee
);
2093 /* Implementation of custom_edge_info::add_events_to_path vfunc
2094 for dynamic_call_info_t. */
2097 dynamic_call_info_t::add_events_to_path (checker_path
*emission_path
,
2098 const exploded_edge
&eedge
) const
2100 const exploded_node
*src_node
= eedge
.m_src
;
2101 const program_point
&src_point
= src_node
->get_point ();
2102 const int src_stack_depth
= src_point
.get_stack_depth ();
2103 const exploded_node
*dest_node
= eedge
.m_dest
;
2104 const program_point
&dest_point
= dest_node
->get_point ();
2105 const int dest_stack_depth
= dest_point
.get_stack_depth ();
2107 if (m_is_returning_call
)
2108 emission_path
->add_event
2109 (make_unique
<return_event
> (eedge
,
2110 event_loc_info (m_dynamic_call
2111 ? m_dynamic_call
->location
2113 dest_point
.get_fndecl (),
2114 dest_stack_depth
)));
2116 emission_path
->add_event
2117 (make_unique
<call_event
> (eedge
,
2118 event_loc_info (m_dynamic_call
2119 ? m_dynamic_call
->location
2121 src_point
.get_fndecl (),
2125 /* class rewind_info_t : public custom_edge_info. */
2127 /* Implementation of custom_edge_info::update_model vfunc
2130 Update state for the special-case of a rewind of a longjmp
2131 to a setjmp (which doesn't have a superedge, but does affect
2135 rewind_info_t::update_model (region_model
*model
,
2136 const exploded_edge
*eedge
,
2137 region_model_context
*) const
2140 const program_point
&longjmp_point
= eedge
->m_src
->get_point ();
2141 const program_point
&setjmp_point
= eedge
->m_dest
->get_point ();
2143 gcc_assert (longjmp_point
.get_stack_depth ()
2144 >= setjmp_point
.get_stack_depth ());
2146 model
->on_longjmp (get_longjmp_call (),
2148 setjmp_point
.get_stack_depth (), NULL
);
2152 /* Implementation of custom_edge_info::add_events_to_path vfunc
2153 for rewind_info_t. */
2156 rewind_info_t::add_events_to_path (checker_path
*emission_path
,
2157 const exploded_edge
&eedge
) const
2159 const exploded_node
*src_node
= eedge
.m_src
;
2160 const program_point
&src_point
= src_node
->get_point ();
2161 const int src_stack_depth
= src_point
.get_stack_depth ();
2162 const exploded_node
*dst_node
= eedge
.m_dest
;
2163 const program_point
&dst_point
= dst_node
->get_point ();
2164 const int dst_stack_depth
= dst_point
.get_stack_depth ();
2166 emission_path
->add_event
2167 (make_unique
<rewind_from_longjmp_event
>
2169 event_loc_info (get_longjmp_call ()->location
,
2170 src_point
.get_fndecl (),
2173 emission_path
->add_event
2174 (make_unique
<rewind_to_setjmp_event
>
2176 event_loc_info (get_setjmp_call ()->location
,
2177 dst_point
.get_fndecl (),
2182 /* class exploded_edge : public dedge<eg_traits>. */
2184 /* exploded_edge's ctor. */
2186 exploded_edge::exploded_edge (exploded_node
*src
, exploded_node
*dest
,
2187 const superedge
*sedge
, bool could_do_work
,
2188 std::unique_ptr
<custom_edge_info
> custom_info
)
2189 : dedge
<eg_traits
> (src
, dest
), m_sedge (sedge
),
2190 m_custom_info (std::move (custom_info
)),
2191 m_could_do_work_p (could_do_work
)
2195 /* Implementation of dedge::dump_dot vfunc for exploded_edge.
2196 Use the label of the underlying superedge, if any. */
2199 exploded_edge::dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
2201 pretty_printer
*pp
= gv
->get_pp ();
2203 m_src
->dump_dot_id (pp
);
2204 pp_string (pp
, " -> ");
2205 m_dest
->dump_dot_id (pp
);
2206 dump_dot_label (pp
);
2209 /* Second half of exploded_edge::dump_dot. This is split out
2210 for use by trimmed_graph::dump_dot and base_feasible_edge::dump_dot. */
2213 exploded_edge::dump_dot_label (pretty_printer
*pp
) const
2215 const char *style
= "\"solid,bold\"";
2216 const char *color
= "black";
2218 const char *constraint
= "true";
2221 switch (m_sedge
->m_kind
)
2225 case SUPEREDGE_CFG_EDGE
:
2227 case SUPEREDGE_CALL
:
2229 //constraint = "false";
2231 case SUPEREDGE_RETURN
:
2233 //constraint = "false";
2235 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
2236 style
= "\"dotted\"";
2242 style
= "\"dotted\"";
2246 (" [style=%s, color=%s, weight=%d, constraint=%s,"
2248 style
, color
, weight
, constraint
);
2251 m_sedge
->dump_label_to_pp (pp
, false);
2252 else if (m_custom_info
)
2253 m_custom_info
->print (pp
);
2255 pp_printf (pp
, "%s",
2256 could_do_work_p () ? "(could do work)" : "DOES NO WORK");
2258 //pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false);
2260 pp_printf (pp
, "\"];\n");
2263 /* Return a new json::object of the form
2264 {"src_idx": int, the index of the source exploded edge,
2265 "dst_idx": int, the index of the destination exploded edge,
2266 "sedge": (optional) object for the superedge, if any,
2267 "custom": (optional) str, a description, if this is a custom edge}. */
2270 exploded_edge::to_json () const
2272 json::object
*eedge_obj
= new json::object ();
2273 eedge_obj
->set ("src_idx", new json::integer_number (m_src
->m_index
));
2274 eedge_obj
->set ("dst_idx", new json::integer_number (m_dest
->m_index
));
2276 eedge_obj
->set ("sedge", m_sedge
->to_json ());
2280 pp_format_decoder (&pp
) = default_tree_printer
;
2281 m_custom_info
->print (&pp
);
2282 eedge_obj
->set ("custom", new json::string (pp_formatted_text (&pp
)));
2291 stats::stats (int num_supernodes
)
2292 : m_node_reuse_count (0),
2293 m_node_reuse_after_merge_count (0),
2294 m_num_supernodes (num_supernodes
)
2296 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
2300 /* Log these stats in multiline form to LOGGER. */
2303 stats::log (logger
*logger
) const
2305 gcc_assert (logger
);
2306 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
2307 if (m_num_nodes
[i
] > 0)
2308 logger
->log ("m_num_nodes[%s]: %i",
2309 point_kind_to_string (static_cast <enum point_kind
> (i
)),
2311 logger
->log ("m_node_reuse_count: %i", m_node_reuse_count
);
2312 logger
->log ("m_node_reuse_after_merge_count: %i",
2313 m_node_reuse_after_merge_count
);
2316 /* Dump these stats in multiline form to OUT. */
2319 stats::dump (FILE *out
) const
2321 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
2322 if (m_num_nodes
[i
] > 0)
2323 fprintf (out
, "m_num_nodes[%s]: %i\n",
2324 point_kind_to_string (static_cast <enum point_kind
> (i
)),
2326 fprintf (out
, "m_node_reuse_count: %i\n", m_node_reuse_count
);
2327 fprintf (out
, "m_node_reuse_after_merge_count: %i\n",
2328 m_node_reuse_after_merge_count
);
2330 if (m_num_supernodes
> 0)
2331 fprintf (out
, "PK_AFTER_SUPERNODE nodes per supernode: %.2f\n",
2332 (float)m_num_nodes
[PK_AFTER_SUPERNODE
] / (float)m_num_supernodes
);
2335 /* Return the total number of enodes recorded within this object. */
2338 stats::get_total_enodes () const
2341 for (int i
= 0; i
< NUM_POINT_KINDS
; i
++)
2342 result
+= m_num_nodes
[i
];
2346 /* struct per_function_data. */
2348 per_function_data::~per_function_data ()
2350 for (auto iter
: m_summaries
)
2355 per_function_data::add_call_summary (exploded_node
*node
)
2357 m_summaries
.safe_push (new call_summary (this, node
));
2360 /* strongly_connected_components's ctor. Tarjan's SCC algorithm. */
2362 strongly_connected_components::
2363 strongly_connected_components (const supergraph
&sg
, logger
*logger
)
2364 : m_sg (sg
), m_per_node (m_sg
.num_nodes ())
2367 auto_timevar
tv (TV_ANALYZER_SCC
);
2369 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2370 m_per_node
.quick_push (per_node_data ());
2372 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2373 if (m_per_node
[i
].m_index
== -1)
2380 /* Dump this object to stderr. */
2383 strongly_connected_components::dump () const
2385 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2387 const per_node_data
&v
= m_per_node
[i
];
2388 fprintf (stderr
, "SN %i: index: %i lowlink: %i on_stack: %i\n",
2389 i
, v
.m_index
, v
.m_lowlink
, v
.m_on_stack
);
2393 /* Return a new json::array of per-snode SCC ids. */
2396 strongly_connected_components::to_json () const
2398 json::array
*scc_arr
= new json::array ();
2399 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2400 scc_arr
->append (new json::integer_number (get_scc_id (i
)));
2404 /* Subroutine of strongly_connected_components's ctor, part of Tarjan's
2408 strongly_connected_components::strong_connect (unsigned index
)
2410 supernode
*v_snode
= m_sg
.get_node_by_index (index
);
2412 /* Set the depth index for v to the smallest unused index. */
2413 per_node_data
*v
= &m_per_node
[index
];
2415 v
->m_lowlink
= index
;
2416 m_stack
.safe_push (index
);
2417 v
->m_on_stack
= true;
2420 /* Consider successors of v. */
2423 FOR_EACH_VEC_ELT (v_snode
->m_succs
, i
, sedge
)
2425 if (sedge
->get_kind () != SUPEREDGE_CFG_EDGE
2426 && sedge
->get_kind () != SUPEREDGE_INTRAPROCEDURAL_CALL
)
2428 supernode
*w_snode
= sedge
->m_dest
;
2429 per_node_data
*w
= &m_per_node
[w_snode
->m_index
];
2430 if (w
->m_index
== -1)
2432 /* Successor w has not yet been visited; recurse on it. */
2433 strong_connect (w_snode
->m_index
);
2434 v
->m_lowlink
= MIN (v
->m_lowlink
, w
->m_lowlink
);
2436 else if (w
->m_on_stack
)
2438 /* Successor w is in stack S and hence in the current SCC
2439 If w is not on stack, then (v, w) is a cross-edge in the DFS
2440 tree and must be ignored. */
2441 v
->m_lowlink
= MIN (v
->m_lowlink
, w
->m_index
);
2445 /* If v is a root node, pop the stack and generate an SCC. */
2447 if (v
->m_lowlink
== v
->m_index
)
2451 int idx
= m_stack
.pop ();
2452 w
= &m_per_node
[idx
];
2453 w
->m_on_stack
= false;
2458 /* worklist's ctor. */
2460 worklist::worklist (const exploded_graph
&eg
, const analysis_plan
&plan
)
2461 : m_scc (eg
.get_supergraph (), eg
.get_logger ()),
2463 m_queue (key_t (*this, NULL
))
2467 /* Return the number of nodes in the worklist. */
2470 worklist::length () const
2472 return m_queue
.nodes ();
2475 /* Return the next node in the worklist, removing it. */
2478 worklist::take_next ()
2480 return m_queue
.extract_min ();
2483 /* Return the next node in the worklist without removing it. */
2486 worklist::peek_next ()
2488 return m_queue
.min ();
2491 /* Add ENODE to the worklist. */
2494 worklist::add_node (exploded_node
*enode
)
2496 gcc_assert (enode
->get_status () == exploded_node::STATUS_WORKLIST
);
2497 m_queue
.insert (key_t (*this, enode
), enode
);
2500 /* Comparator for implementing worklist::key_t comparison operators.
2501 Return negative if KA is before KB
2502 Return positive if KA is after KB
2503 Return 0 if they are equal.
2505 The ordering of the worklist is critical for performance and for
2506 avoiding node explosions. Ideally we want all enodes at a CFG join-point
2507 with the same callstring to be sorted next to each other in the worklist
2508 so that a run of consecutive enodes can be merged and processed "in bulk"
2509 rather than individually or pairwise, minimizing the number of new enodes
2513 worklist::key_t::cmp (const worklist::key_t
&ka
, const worklist::key_t
&kb
)
2515 const program_point
&point_a
= ka
.m_enode
->get_point ();
2516 const program_point
&point_b
= kb
.m_enode
->get_point ();
2517 const call_string
&call_string_a
= point_a
.get_call_string ();
2518 const call_string
&call_string_b
= point_b
.get_call_string ();
2520 /* Order empty-callstring points with different functions based on the
2521 analysis_plan, so that we generate summaries before they are used. */
2522 if (flag_analyzer_call_summaries
2523 && call_string_a
.empty_p ()
2524 && call_string_b
.empty_p ()
2525 && point_a
.get_function () != NULL
2526 && point_b
.get_function () != NULL
2527 && point_a
.get_function () != point_b
.get_function ())
2529 if (int cmp
= ka
.m_worklist
.m_plan
.cmp_function (point_a
.get_function (),
2530 point_b
.get_function ()))
2534 /* Sort by callstring, so that nodes with deeper call strings are processed
2535 before those with shallower call strings.
2544 then we want the path inside the function call to be fully explored up
2545 to the return to the join BB before we explore on the "no fn call" path,
2546 so that both enodes at the join BB reach the front of the worklist at
2547 the same time and thus have a chance of being merged. */
2548 int cs_cmp
= call_string::cmp (call_string_a
, call_string_b
);
2553 int scc_id_a
= ka
.get_scc_id (ka
.m_enode
);
2554 int scc_id_b
= kb
.get_scc_id (kb
.m_enode
);
2555 if (scc_id_a
!= scc_id_b
)
2556 return scc_id_a
- scc_id_b
;
2558 /* If in same SCC, order by supernode index (an arbitrary but stable
2560 const supernode
*snode_a
= ka
.m_enode
->get_supernode ();
2561 const supernode
*snode_b
= kb
.m_enode
->get_supernode ();
2562 if (snode_a
== NULL
)
2564 if (snode_b
!= NULL
)
2568 /* Both are NULL. */
2571 if (snode_b
== NULL
)
2574 /* Neither are NULL. */
2575 gcc_assert (snode_a
&& snode_b
);
2576 if (snode_a
->m_index
!= snode_b
->m_index
)
2577 return snode_a
->m_index
- snode_b
->m_index
;
2579 gcc_assert (snode_a
== snode_b
);
2581 /* Order within supernode via program point. */
2582 int within_snode_cmp
2583 = function_point::cmp_within_supernode (point_a
.get_function_point (),
2584 point_b
.get_function_point ());
2585 if (within_snode_cmp
)
2586 return within_snode_cmp
;
2588 /* Otherwise, we ought to have the same program_point. */
2589 gcc_assert (point_a
== point_b
);
2591 const program_state
&state_a
= ka
.m_enode
->get_state ();
2592 const program_state
&state_b
= kb
.m_enode
->get_state ();
2594 /* Sort by sm-state, so that identical sm-states are grouped
2595 together in the worklist. */
2596 for (unsigned sm_idx
= 0; sm_idx
< state_a
.m_checker_states
.length ();
2599 sm_state_map
*smap_a
= state_a
.m_checker_states
[sm_idx
];
2600 sm_state_map
*smap_b
= state_b
.m_checker_states
[sm_idx
];
2602 if (int smap_cmp
= sm_state_map::cmp (*smap_a
, *smap_b
))
2606 /* Otherwise, we have two enodes at the same program point but with
2607 different states. We don't have a good total ordering on states,
2608 so order them by enode index, so that we have at least have a
2610 return ka
.m_enode
->m_index
- kb
.m_enode
->m_index
;
2613 /* Return a new json::object of the form
2614 {"scc" : [per-snode-IDs]}, */
2617 worklist::to_json () const
2619 json::object
*worklist_obj
= new json::object ();
2621 worklist_obj
->set ("scc", m_scc
.to_json ());
2623 /* The following field isn't yet being JSONified:
2626 return worklist_obj
;
2629 /* exploded_graph's ctor. */
2631 exploded_graph::exploded_graph (const supergraph
&sg
, logger
*logger
,
2632 const extrinsic_state
&ext_state
,
2633 const state_purge_map
*purge_map
,
2634 const analysis_plan
&plan
,
2636 : m_sg (sg
), m_logger (logger
),
2637 m_worklist (*this, plan
),
2638 m_ext_state (ext_state
),
2639 m_purge_map (purge_map
),
2641 m_diagnostic_manager (logger
, ext_state
.get_engine (), verbosity
),
2642 m_global_stats (m_sg
.num_nodes ()),
2643 m_functionless_stats (m_sg
.num_nodes ()),
2644 m_PK_AFTER_SUPERNODE_per_snode (m_sg
.num_nodes ())
2646 m_origin
= get_or_create_node
2647 (program_point::origin (*ext_state
.get_model_manager ()),
2648 program_state (ext_state
), NULL
);
2649 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
2650 m_PK_AFTER_SUPERNODE_per_snode
.quick_push (i
);
2653 /* exploded_graph's dtor. */
2655 exploded_graph::~exploded_graph ()
2657 for (auto iter
: m_per_point_data
)
2659 for (auto iter
: m_per_function_data
)
2661 for (auto iter
: m_per_function_stats
)
2663 for (auto iter
: m_per_call_string_data
)
2667 /* Subroutine for use when implementing __attribute__((tainted_args))
2668 on functions and on function pointer fields in structs.
2670 Called on STATE representing a call to FNDECL.
2671 Mark all params of FNDECL in STATE as "tainted". Mark the value of all
2672 regions pointed to by params of FNDECL as "tainted".
2674 Return true if successful; return false if the "taint" state machine
2678 mark_params_as_tainted (program_state
*state
, tree fndecl
,
2679 const extrinsic_state
&ext_state
)
2681 unsigned taint_sm_idx
;
2682 if (!ext_state
.get_sm_idx_by_name ("taint", &taint_sm_idx
))
2684 sm_state_map
*smap
= state
->m_checker_states
[taint_sm_idx
];
2686 const state_machine
&sm
= ext_state
.get_sm (taint_sm_idx
);
2687 state_machine::state_t tainted
= sm
.get_state_by_name ("tainted");
2689 region_model_manager
*mgr
= ext_state
.get_model_manager ();
2691 function
*fun
= DECL_STRUCT_FUNCTION (fndecl
);
2694 for (tree iter_parm
= DECL_ARGUMENTS (fndecl
); iter_parm
;
2695 iter_parm
= DECL_CHAIN (iter_parm
))
2697 tree param
= iter_parm
;
2698 if (tree parm_default_ssa
= ssa_default_def (fun
, iter_parm
))
2699 param
= parm_default_ssa
;
2700 const region
*param_reg
= state
->m_region_model
->get_lvalue (param
, NULL
);
2701 const svalue
*init_sval
= mgr
->get_or_create_initial_value (param_reg
);
2702 smap
->set_state (state
->m_region_model
, init_sval
,
2703 tainted
, NULL
/*origin_new_sval*/, ext_state
);
2704 if (POINTER_TYPE_P (TREE_TYPE (param
)))
2706 const region
*pointee_reg
= mgr
->get_symbolic_region (init_sval
);
2707 /* Mark "*param" as tainted. */
2708 const svalue
*init_pointee_sval
2709 = mgr
->get_or_create_initial_value (pointee_reg
);
2710 smap
->set_state (state
->m_region_model
, init_pointee_sval
,
2711 tainted
, NULL
/*origin_new_sval*/, ext_state
);
2718 /* Custom event for use by tainted_args_function_info when a function
2719 has been marked with __attribute__((tainted_args)). */
2721 class tainted_args_function_custom_event
: public custom_event
2724 tainted_args_function_custom_event (const event_loc_info
&loc_info
)
2725 : custom_event (loc_info
),
2726 m_fndecl (loc_info
.m_fndecl
)
2730 label_text
get_desc (bool can_colorize
) const final override
2732 return make_label_text
2734 "function %qE marked with %<__attribute__((tainted_args))%>",
2742 /* Custom exploded_edge info for top-level calls to a function
2743 marked with __attribute__((tainted_args)). */
2745 class tainted_args_function_info
: public custom_edge_info
2748 tainted_args_function_info (tree fndecl
)
2752 void print (pretty_printer
*pp
) const final override
2754 pp_string (pp
, "call to tainted_args function");
2757 bool update_model (region_model
*,
2758 const exploded_edge
*,
2759 region_model_context
*) const final override
2765 void add_events_to_path (checker_path
*emission_path
,
2766 const exploded_edge
&) const final override
2768 emission_path
->add_event
2769 (make_unique
<tainted_args_function_custom_event
>
2770 (event_loc_info (DECL_SOURCE_LOCATION (m_fndecl
), m_fndecl
, 0)));
2777 /* Ensure that there is an exploded_node representing an external call to
2778 FUN, adding it to the worklist if creating it.
2780 Add an edge from the origin exploded_node to the function entrypoint
2783 Return the exploded_node for the entrypoint to the function. */
2786 exploded_graph::add_function_entry (const function
&fun
)
2788 gcc_assert (gimple_has_body_p (fun
.decl
));
2790 /* Be idempotent. */
2791 function
*key
= const_cast<function
*> (&fun
);
2792 if (m_functions_with_enodes
.contains (key
))
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 (key
);
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 (const 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 ();
3334 if (!toplevel_function_p (*fun
, logger
))
3336 exploded_node
*enode
= add_function_entry (*fun
);
3340 logger
->log ("created EN %i for %qE entrypoint",
3341 enode
->m_index
, fun
->decl
);
3343 logger
->log ("did not create enode for %qE entrypoint", fun
->decl
);
3347 /* Find callbacks that are reachable from global initializers. */
3348 varpool_node
*vpnode
;
3349 FOR_EACH_VARIABLE (vpnode
)
3351 tree decl
= vpnode
->decl
;
3352 tree init
= DECL_INITIAL (decl
);
3355 walk_tree (&init
, add_any_callbacks
, this, NULL
);
3359 /* The main loop of the analysis.
3360 Take freshly-created exploded_nodes from the worklist, calling
3361 process_node on them to explore the <point, state> graph.
3362 Add edges to their successors, potentially creating new successors
3363 (which are also added to the worklist). */
3366 exploded_graph::process_worklist ()
3368 logger
* const logger
= get_logger ();
3370 auto_timevar
tv (TV_ANALYZER_WORKLIST
);
3372 while (m_worklist
.length () > 0)
3374 exploded_node
*node
= m_worklist
.take_next ();
3375 gcc_assert (node
->get_status () == exploded_node::STATUS_WORKLIST
);
3376 gcc_assert (node
->m_succs
.length () == 0
3377 || node
== m_origin
);
3380 logger
->log ("next to process: EN: %i", node
->m_index
);
3382 /* If we have a run of nodes that are before-supernode, try merging and
3383 processing them together, rather than pairwise or individually. */
3384 if (flag_analyzer_state_merge
&& node
!= m_origin
)
3385 if (maybe_process_run_of_before_supernode_enodes (node
))
3388 /* Avoid exponential explosions of nodes by attempting to merge
3389 nodes that are at the same program point and which have
3390 sufficiently similar state. */
3391 if (flag_analyzer_state_merge
&& node
!= m_origin
)
3392 if (exploded_node
*node_2
= m_worklist
.peek_next ())
3394 gcc_assert (node_2
->get_status ()
3395 == exploded_node::STATUS_WORKLIST
);
3396 gcc_assert (node
->m_succs
.length () == 0);
3397 gcc_assert (node_2
->m_succs
.length () == 0);
3399 gcc_assert (node
!= node_2
);
3402 logger
->log ("peek worklist: EN: %i", node_2
->m_index
);
3404 if (node
->get_point () == node_2
->get_point ())
3406 const program_point
&point
= node
->get_point ();
3410 pretty_printer
*pp
= logger
->get_printer ();
3411 logger
->start_log_line ();
3413 ("got potential merge EN: %i and EN: %i at ",
3414 node
->m_index
, node_2
->m_index
);
3415 point
.print (pp
, f
);
3416 logger
->end_log_line ();
3418 const program_state
&state
= node
->get_state ();
3419 const program_state
&state_2
= node_2
->get_state ();
3421 /* They shouldn't be equal, or we wouldn't have two
3423 gcc_assert (state
!= state_2
);
3425 program_state
merged_state (m_ext_state
);
3426 if (state
.can_merge_with_p (state_2
, m_ext_state
,
3427 point
, &merged_state
))
3430 logger
->log ("merging EN: %i and EN: %i",
3431 node
->m_index
, node_2
->m_index
);
3433 if (merged_state
== state
)
3435 /* Then merge node_2 into node by adding an edge. */
3436 add_edge (node_2
, node
, NULL
, false);
3438 /* Remove node_2 from the worklist. */
3439 m_worklist
.take_next ();
3440 node_2
->set_status (exploded_node::STATUS_MERGER
);
3442 /* Continue processing "node" below. */
3444 else if (merged_state
== state_2
)
3446 /* Then merge node into node_2, and leave node_2
3447 in the worklist, to be processed on the next
3449 add_edge (node
, node_2
, NULL
, false);
3450 node
->set_status (exploded_node::STATUS_MERGER
);
3455 /* We have a merged state that differs from
3456 both state and state_2. */
3458 /* Remove node_2 from the worklist. */
3459 m_worklist
.take_next ();
3461 /* Create (or get) an exploded node for the merged
3462 states, adding to the worklist. */
3463 exploded_node
*merged_enode
3464 = get_or_create_node (node
->get_point (),
3465 merged_state
, node
);
3466 if (merged_enode
== NULL
)
3470 logger
->log ("merged EN: %i and EN: %i into EN: %i",
3471 node
->m_index
, node_2
->m_index
,
3472 merged_enode
->m_index
);
3474 /* "node" and "node_2" have both now been removed
3475 from the worklist; we should not process them.
3477 "merged_enode" may be a new node; if so it will be
3478 processed in a subsequent iteration.
3479 Alternatively, "merged_enode" could be an existing
3480 node; one way the latter can
3481 happen is if we end up merging a succession of
3482 similar nodes into one. */
3484 /* If merged_node is one of the two we were merging,
3485 add it back to the worklist to ensure it gets
3488 Add edges from the merged nodes to it (but not a
3490 if (merged_enode
== node
)
3491 m_worklist
.add_node (merged_enode
);
3494 add_edge (node
, merged_enode
, NULL
, false);
3495 node
->set_status (exploded_node::STATUS_MERGER
);
3498 if (merged_enode
== node_2
)
3499 m_worklist
.add_node (merged_enode
);
3502 add_edge (node_2
, merged_enode
, NULL
, false);
3503 node_2
->set_status (exploded_node::STATUS_MERGER
);
3510 /* TODO: should we attempt more than two nodes,
3511 or just do pairs of nodes? (and hope that we get
3512 a cascade of mergers). */
3516 process_node (node
);
3519 /* Impose a hard limit on the number of exploded nodes, to ensure
3520 that the analysis terminates in the face of pathological state
3521 explosion (or bugs).
3523 Specifically, the limit is on the number of PK_AFTER_SUPERNODE
3524 exploded nodes, looking at supernode exit events.
3526 We use exit rather than entry since there can be multiple
3527 entry ENs, one per phi; the number of PK_AFTER_SUPERNODE ought
3528 to be equivalent to the number of supernodes multiplied by the
3529 number of states. */
3530 const int limit
= m_sg
.num_nodes () * param_analyzer_bb_explosion_factor
;
3531 if (m_global_stats
.m_num_nodes
[PK_AFTER_SUPERNODE
] > limit
)
3534 logger
->log ("bailing out; too many nodes");
3535 warning_at (node
->get_point ().get_location (),
3536 OPT_Wanalyzer_too_complex
,
3537 "analysis bailed out early"
3538 " (%i 'after-snode' enodes; %i enodes)",
3539 m_global_stats
.m_num_nodes
[PK_AFTER_SUPERNODE
],
3546 /* Attempt to process a consecutive run of sufficiently-similar nodes in
3547 the worklist at a CFG join-point (having already popped ENODE from the
3548 head of the worklist).
3550 If ENODE's point is of the form (before-supernode, SNODE) and the next
3551 nodes in the worklist are a consecutive run of enodes of the same form,
3552 for the same supernode as ENODE (but potentially from different in-edges),
3553 process them all together, setting their status to STATUS_BULK_MERGED,
3555 Otherwise, return false, in which case ENODE must be processed in the
3558 When processing them all together, generate successor states based
3559 on phi nodes for the appropriate CFG edges, and then attempt to merge
3560 these states into a minimal set of merged successor states, partitioning
3561 the inputs by merged successor state.
3563 Create new exploded nodes for all of the merged states, and add edges
3564 connecting the input enodes to the corresponding merger exploded nodes.
3566 We hope we have a much smaller number of merged successor states
3567 compared to the number of input enodes - ideally just one,
3568 if all successor states can be merged.
3570 Processing and merging many together as one operation rather than as
3571 pairs avoids scaling issues where per-pair mergers could bloat the
3572 graph with merger nodes (especially so after switch statements). */
3576 maybe_process_run_of_before_supernode_enodes (exploded_node
*enode
)
3578 /* A struct for tracking per-input state. */
3581 item (exploded_node
*input_enode
)
3582 : m_input_enode (input_enode
),
3583 m_processed_state (input_enode
->get_state ()),
3587 exploded_node
*m_input_enode
;
3588 program_state m_processed_state
;
3592 gcc_assert (enode
->get_status () == exploded_node::STATUS_WORKLIST
);
3593 gcc_assert (enode
->m_succs
.length () == 0);
3595 const program_point
&point
= enode
->get_point ();
3597 if (point
.get_kind () != PK_BEFORE_SUPERNODE
)
3600 const supernode
*snode
= point
.get_supernode ();
3602 logger
* const logger
= get_logger ();
3605 /* Find a run of enodes in the worklist that are before the same supernode,
3606 but potentially from different in-edges. */
3607 auto_vec
<exploded_node
*> enodes
;
3608 enodes
.safe_push (enode
);
3609 while (exploded_node
*enode_2
= m_worklist
.peek_next ())
3611 gcc_assert (enode_2
->get_status ()
3612 == exploded_node::STATUS_WORKLIST
);
3613 gcc_assert (enode_2
->m_succs
.length () == 0);
3615 const program_point
&point_2
= enode_2
->get_point ();
3617 if (point_2
.get_kind () == PK_BEFORE_SUPERNODE
3618 && point_2
.get_supernode () == snode
3619 && &point_2
.get_call_string () == &point
.get_call_string ())
3621 enodes
.safe_push (enode_2
);
3622 m_worklist
.take_next ();
3628 /* If the only node is ENODE, then give up. */
3629 if (enodes
.length () == 1)
3633 logger
->log ("got run of %i enodes for SN: %i",
3634 enodes
.length (), snode
->m_index
);
3636 /* All of these enodes have a shared successor point (even if they
3637 were for different in-edges). */
3638 program_point
next_point (point
.get_next ());
3640 /* Calculate the successor state for each enode in enodes. */
3641 auto_delete_vec
<item
> items (enodes
.length ());
3643 exploded_node
*iter_enode
;
3644 FOR_EACH_VEC_ELT (enodes
, i
, iter_enode
)
3646 item
*it
= new item (iter_enode
);
3647 items
.quick_push (it
);
3648 const program_state
&state
= iter_enode
->get_state ();
3649 program_state
*next_state
= &it
->m_processed_state
;
3650 next_state
->validate (m_ext_state
);
3651 const program_point
&iter_point
= iter_enode
->get_point ();
3652 if (const superedge
*iter_sedge
= iter_point
.get_from_edge ())
3654 uncertainty_t uncertainty
;
3655 impl_region_model_context
ctxt (*this, iter_enode
,
3657 &uncertainty
, NULL
, NULL
);
3658 const cfg_superedge
*last_cfg_superedge
3659 = iter_sedge
->dyn_cast_cfg_superedge ();
3660 if (last_cfg_superedge
)
3661 next_state
->m_region_model
->update_for_phis
3662 (snode
, last_cfg_superedge
, &ctxt
);
3664 next_state
->validate (m_ext_state
);
3667 /* Attempt to partition the items into a set of merged states.
3668 We hope we have a much smaller number of merged states
3669 compared to the number of input enodes - ideally just one,
3670 if all can be merged. */
3671 auto_delete_vec
<program_state
> merged_states
;
3672 auto_vec
<item
*> first_item_for_each_merged_state
;
3674 FOR_EACH_VEC_ELT (items
, i
, it
)
3676 const program_state
&it_state
= it
->m_processed_state
;
3677 program_state
*merged_state
;
3678 unsigned iter_merger_idx
;
3679 FOR_EACH_VEC_ELT (merged_states
, iter_merger_idx
, merged_state
)
3681 merged_state
->validate (m_ext_state
);
3682 program_state
merge (m_ext_state
);
3683 if (it_state
.can_merge_with_p (*merged_state
, m_ext_state
,
3684 next_point
, &merge
))
3686 *merged_state
= merge
;
3687 merged_state
->validate (m_ext_state
);
3688 it
->m_merger_idx
= iter_merger_idx
;
3690 logger
->log ("reusing merger state %i for item %i (EN: %i)",
3691 it
->m_merger_idx
, i
, it
->m_input_enode
->m_index
);
3695 /* If it couldn't be merged with any existing merged_states,
3696 create a new one. */
3697 if (it
->m_merger_idx
== -1)
3699 it
->m_merger_idx
= merged_states
.length ();
3700 merged_states
.safe_push (new program_state (it_state
));
3701 first_item_for_each_merged_state
.safe_push (it
);
3703 logger
->log ("using new merger state %i for item %i (EN: %i)",
3704 it
->m_merger_idx
, i
, it
->m_input_enode
->m_index
);
3707 gcc_assert (it
->m_merger_idx
>= 0);
3708 gcc_assert ((unsigned)it
->m_merger_idx
< merged_states
.length ());
3711 /* Create merger nodes. */
3712 auto_vec
<exploded_node
*> next_enodes (merged_states
.length ());
3713 program_state
*merged_state
;
3714 FOR_EACH_VEC_ELT (merged_states
, i
, merged_state
)
3716 exploded_node
*src_enode
3717 = first_item_for_each_merged_state
[i
]->m_input_enode
;
3719 = get_or_create_node (next_point
, *merged_state
, src_enode
);
3720 /* "next" could be NULL; we handle that when adding the edges below. */
3721 next_enodes
.quick_push (next
);
3725 logger
->log ("using EN: %i for merger state %i", next
->m_index
, i
);
3727 logger
->log ("using NULL enode for merger state %i", i
);
3731 /* Create edges from each input enode to the appropriate successor enode.
3732 Update the status of the now-processed input enodes. */
3733 FOR_EACH_VEC_ELT (items
, i
, it
)
3735 exploded_node
*next
= next_enodes
[it
->m_merger_idx
];
3737 add_edge (it
->m_input_enode
, next
, NULL
,
3738 false); /* no "work" is done during merger. */
3739 it
->m_input_enode
->set_status (exploded_node::STATUS_BULK_MERGED
);
3743 logger
->log ("merged %i in-enodes into %i out-enode(s) at SN: %i",
3744 items
.length (), merged_states
.length (), snode
->m_index
);
3749 /* Return true if STMT must appear at the start of its exploded node, and
3750 thus we can't consolidate its effects within a run of other statements,
3751 where PREV_STMT was the previous statement. */
3754 stmt_requires_new_enode_p (const gimple
*stmt
,
3755 const gimple
*prev_stmt
)
3757 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
3759 /* Stop consolidating at calls to
3760 "__analyzer_dump_exploded_nodes", so they always appear at the
3761 start of an exploded_node. */
3762 if (is_special_named_call_p (call
, "__analyzer_dump_exploded_nodes",
3766 /* sm-signal.cc injects an additional custom eedge at "signal" calls
3767 from the registration enode to the handler enode, separate from the
3768 regular next state, which defeats the "detect state change" logic
3769 in process_node. Work around this via special-casing, to ensure
3770 we split the enode immediately before any "signal" call. */
3771 if (is_special_named_call_p (call
, "signal", 2))
3775 /* If we had a PREV_STMT with an unknown location, and this stmt
3776 has a known location, then if a state change happens here, it
3777 could be consolidated into PREV_STMT, giving us an event with
3778 no location. Ensure that STMT gets its own exploded_node to
3780 if (get_pure_location (prev_stmt
->location
) == UNKNOWN_LOCATION
3781 && get_pure_location (stmt
->location
) != UNKNOWN_LOCATION
)
3787 /* Return true if OLD_STATE and NEW_STATE are sufficiently different that
3788 we should split enodes and create an exploded_edge separating them
3789 (which makes it easier to identify state changes of intereset when
3790 constructing checker_paths). */
3793 state_change_requires_new_enode_p (const program_state
&old_state
,
3794 const program_state
&new_state
)
3796 /* Changes in dynamic extents signify creations of heap/alloca regions
3797 and resizings of heap regions; likely to be of interest in
3798 diagnostic paths. */
3799 if (old_state
.m_region_model
->get_dynamic_extents ()
3800 != new_state
.m_region_model
->get_dynamic_extents ())
3803 /* Changes in sm-state are of interest. */
3806 FOR_EACH_VEC_ELT (old_state
.m_checker_states
, sm_idx
, smap
)
3808 const sm_state_map
*old_smap
= old_state
.m_checker_states
[sm_idx
];
3809 const sm_state_map
*new_smap
= new_state
.m_checker_states
[sm_idx
];
3810 if (*old_smap
!= *new_smap
)
3817 /* Create enodes and eedges for the function calls that doesn't have an
3818 underlying call superedge.
3820 Such case occurs when GCC's middle end didn't know which function to
3821 call but the analyzer does (with the help of current state).
3823 Some example such calls are dynamically dispatched calls to virtual
3824 functions or calls that happen via function pointer. */
3827 exploded_graph::maybe_create_dynamic_call (const gcall
*call
,
3829 exploded_node
*node
,
3830 program_state next_state
,
3831 program_point
&next_point
,
3832 uncertainty_t
*uncertainty
,
3837 const program_point
*this_point
= &node
->get_point ();
3838 function
*fun
= DECL_STRUCT_FUNCTION (fn_decl
);
3841 const supergraph
&sg
= this->get_supergraph ();
3842 supernode
*sn_entry
= sg
.get_node_for_function_entry (*fun
);
3843 supernode
*sn_exit
= sg
.get_node_for_function_exit (*fun
);
3845 program_point new_point
3846 = program_point::before_supernode (sn_entry
,
3848 this_point
->get_call_string ());
3850 new_point
.push_to_call_stack (sn_exit
,
3851 next_point
.get_supernode());
3853 /* Impose a maximum recursion depth and don't analyze paths
3854 that exceed it further.
3855 This is something of a blunt workaround, but it only
3856 applies to recursion (and mutual recursion), not to
3857 general call stacks. */
3858 if (new_point
.get_call_string ().calc_recursion_depth ()
3859 > param_analyzer_max_recursion_depth
)
3862 logger
->log ("rejecting call edge: recursion limit exceeded");
3866 next_state
.push_call (*this, node
, call
, uncertainty
);
3868 if (next_state
.m_valid
)
3871 logger
->log ("Discovered call to %s [SN: %i -> SN: %i]",
3873 this_point
->get_supernode ()->m_index
,
3876 exploded_node
*enode
= get_or_create_node (new_point
,
3880 add_edge (node
,enode
, NULL
,
3881 false, /* No work is done by the call itself. */
3882 make_unique
<dynamic_call_info_t
> (call
));
3889 /* Subclass of path_context for use within exploded_graph::process_node,
3890 so that we can split states e.g. at "realloc" calls. */
3892 class impl_path_context
: public path_context
3895 impl_path_context (const program_state
*cur_state
,
3897 : m_cur_state (cur_state
),
3899 m_terminate_path (false)
3903 bool bifurcation_p () const
3905 return m_custom_eedge_infos
.length () > 0;
3908 const program_state
&get_state_at_bifurcation () const
3910 gcc_assert (m_state_at_bifurcation
);
3911 return *m_state_at_bifurcation
;
3915 bifurcate (std::unique_ptr
<custom_edge_info
> info
) final override
3918 m_logger
->log ("bifurcating path");
3920 if (m_state_at_bifurcation
)
3921 /* Verify that the state at bifurcation is consistent when we
3922 split into multiple out-edges. */
3923 gcc_assert (*m_state_at_bifurcation
== *m_cur_state
);
3925 /* Take a copy of the cur_state at the moment when bifurcation
3927 m_state_at_bifurcation
3928 = std::unique_ptr
<program_state
> (new program_state (*m_cur_state
));
3930 /* Take ownership of INFO. */
3931 m_custom_eedge_infos
.safe_push (info
.release ());
3934 void terminate_path () final override
3937 m_logger
->log ("terminating path");
3938 m_terminate_path
= true;
3941 bool terminate_path_p () const final override
3943 return m_terminate_path
;
3946 const vec
<custom_edge_info
*> & get_custom_eedge_infos ()
3948 return m_custom_eedge_infos
;
3952 const program_state
*m_cur_state
;
3956 /* Lazily-created copy of the state before the split. */
3957 std::unique_ptr
<program_state
> m_state_at_bifurcation
;
3959 auto_vec
<custom_edge_info
*> m_custom_eedge_infos
;
3961 bool m_terminate_path
;
3964 /* A subclass of pending_diagnostic for complaining about jumps through NULL
3965 function pointers. */
3967 class jump_through_null
: public pending_diagnostic_subclass
<jump_through_null
>
3970 jump_through_null (const gcall
*call
)
3974 const char *get_kind () const final override
3976 return "jump_through_null";
3979 bool operator== (const jump_through_null
&other
) const
3981 return m_call
== other
.m_call
;
3984 int get_controlling_option () const final override
3986 return OPT_Wanalyzer_jump_through_null
;
3989 bool emit (diagnostic_emission_context
&ctxt
) final override
3991 return ctxt
.warn ("jump through null pointer");
3994 label_text
describe_final_event (const evdesc::final_event
&ev
) final override
3996 return ev
.formatted_print ("jump through null pointer here");
4000 const gcall
*m_call
;
4003 /* The core of exploded_graph::process_worklist (the main analysis loop),
4004 handling one node in the worklist.
4006 Get successor <point, state> pairs for NODE, calling get_or_create on
4007 them, and adding an exploded_edge to each successors.
4009 Freshly-created nodes will be added to the worklist. */
4012 exploded_graph::process_node (exploded_node
*node
)
4014 logger
* const logger
= get_logger ();
4015 LOG_FUNC_1 (logger
, "EN: %i", node
->m_index
);
4017 node
->set_status (exploded_node::STATUS_PROCESSED
);
4019 const program_point
&point
= node
->get_point ();
4021 /* Update cfun and input_location in case of an ICE: make it easier to
4022 track down which source construct we're failing to handle. */
4023 auto_cfun
sentinel (node
->get_function ());
4024 const gimple
*stmt
= point
.get_stmt ();
4026 input_location
= stmt
->location
;
4028 const program_state
&state
= node
->get_state ();
4031 pretty_printer
*pp
= logger
->get_printer ();
4032 logger
->start_log_line ();
4033 pp_string (pp
, "point: ");
4034 point
.print (pp
, format (false));
4035 pp_string (pp
, ", state: ");
4036 state
.dump_to_pp (m_ext_state
, true, false, pp
);
4037 logger
->end_log_line ();
4040 switch (point
.get_kind ())
4045 /* This node exists to simplify finding the shortest path
4046 to an exploded_node. */
4049 case PK_BEFORE_SUPERNODE
:
4051 program_state
next_state (state
);
4052 uncertainty_t uncertainty
;
4054 if (point
.get_from_edge ())
4056 impl_region_model_context
ctxt (*this, node
,
4057 &state
, &next_state
,
4058 &uncertainty
, NULL
, NULL
);
4059 const cfg_superedge
*last_cfg_superedge
4060 = point
.get_from_edge ()->dyn_cast_cfg_superedge ();
4061 if (last_cfg_superedge
)
4062 next_state
.m_region_model
->update_for_phis
4063 (node
->get_supernode (),
4066 program_state::detect_leaks (state
, next_state
, NULL
,
4067 get_ext_state (), &ctxt
);
4070 program_point
next_point (point
.get_next ());
4071 exploded_node
*next
= get_or_create_node (next_point
, next_state
, node
);
4073 add_edge (node
, next
, NULL
,
4074 false); /* Assume no work is done at phi nodes. */
4077 case PK_BEFORE_STMT
:
4079 /* Determine the effect of a run of one or more statements
4080 within one supernode, generating an edge to the program_point
4081 after the last statement that's processed.
4083 Stop iterating statements and thus consolidating into one enode
4085 - reaching the end of the statements in the supernode
4086 - if an sm-state-change occurs (so that it gets its own
4088 - if "-fanalyzer-fine-grained" is active
4089 - encountering certain statements must appear at the start of
4090 their enode (for which stmt_requires_new_enode_p returns true)
4092 Update next_state in-place, to get the result of the one
4093 or more stmts that are processed.
4095 Split the node in-place if an sm-state-change occurs, so that
4096 the sm-state-change occurs on an edge where the src enode has
4097 exactly one stmt, the one that caused the change. */
4098 program_state
next_state (state
);
4100 impl_path_context
path_ctxt (&next_state
, logger
);
4102 bool could_have_done_work
= false;
4103 uncertainty_t uncertainty
;
4104 const supernode
*snode
= point
.get_supernode ();
4106 const gimple
*prev_stmt
= NULL
;
4107 for (stmt_idx
= point
.get_stmt_idx ();
4108 stmt_idx
< snode
->m_stmts
.length ();
4111 const gimple
*stmt
= snode
->m_stmts
[stmt_idx
];
4113 if (stmt_idx
> point
.get_stmt_idx ())
4114 if (stmt_requires_new_enode_p (stmt
, prev_stmt
))
4121 program_state
old_state (next_state
);
4123 /* Process the stmt. */
4124 exploded_node::on_stmt_flags flags
4125 = node
->on_stmt (*this, snode
, stmt
, &next_state
, &uncertainty
,
4126 &could_have_done_work
, &path_ctxt
);
4127 node
->m_num_processed_stmts
++;
4129 /* If flags.m_terminate_path, stop analyzing; any nodes/edges
4130 will have been added by on_stmt (e.g. for handling longjmp). */
4131 if (flags
.m_terminate_path
)
4134 if (next_state
.m_region_model
)
4136 impl_region_model_context
ctxt (*this, node
,
4137 &old_state
, &next_state
,
4138 &uncertainty
, NULL
, stmt
);
4139 program_state::detect_leaks (old_state
, next_state
, NULL
,
4140 get_ext_state (), &ctxt
);
4143 unsigned next_idx
= stmt_idx
+ 1;
4144 program_point next_point
4145 = (next_idx
< point
.get_supernode ()->m_stmts
.length ()
4146 ? program_point::before_stmt (point
.get_supernode (), next_idx
,
4147 point
.get_call_string ())
4148 : program_point::after_supernode (point
.get_supernode (),
4149 point
.get_call_string ()));
4150 next_state
= next_state
.prune_for_point (*this, next_point
, node
,
4153 if (flag_analyzer_fine_grained
4154 || state_change_requires_new_enode_p (old_state
, next_state
)
4155 || path_ctxt
.bifurcation_p ()
4156 || path_ctxt
.terminate_path_p ())
4158 program_point split_point
4159 = program_point::before_stmt (point
.get_supernode (),
4161 point
.get_call_string ());
4162 if (split_point
!= node
->get_point ())
4164 /* If we're not at the start of NODE, split the enode at
4165 this stmt, so we have:
4167 so that when split_enode is processed the next edge
4170 and any state change will effectively occur on that
4171 latter edge, and split_enode will contain just stmt. */
4173 logger
->log ("getting split_enode");
4174 exploded_node
*split_enode
4175 = get_or_create_node (split_point
, old_state
, node
);
4178 /* "stmt" will be reprocessed when split_enode is
4180 node
->m_num_processed_stmts
--;
4182 logger
->log ("creating edge to split_enode");
4183 add_edge (node
, split_enode
, NULL
, could_have_done_work
);
4187 /* If we're at the start of NODE, stop iterating,
4188 so that an edge will be created from NODE to
4189 (next_point, next_state) below. */
4193 unsigned next_idx
= stmt_idx
+ 1;
4194 program_point next_point
4195 = (next_idx
< point
.get_supernode ()->m_stmts
.length ()
4196 ? program_point::before_stmt (point
.get_supernode (), next_idx
,
4197 point
.get_call_string ())
4198 : program_point::after_supernode (point
.get_supernode (),
4199 point
.get_call_string ()));
4200 if (path_ctxt
.terminate_path_p ())
4203 logger
->log ("not adding node: terminating path");
4208 = get_or_create_node (next_point
, next_state
, node
);
4210 add_edge (node
, next
, NULL
, could_have_done_work
);
4213 /* If we have custom edge infos, "bifurcate" the state
4214 accordingly, potentially creating a new state/enode/eedge
4215 instances. For example, to handle a "realloc" call, we
4216 might split into 3 states, for the "failure",
4217 "resizing in place", and "moving to a new buffer" cases. */
4218 for (auto edge_info_iter
: path_ctxt
.get_custom_eedge_infos ())
4220 /* Take ownership of the edge infos from the path_ctxt. */
4221 std::unique_ptr
<custom_edge_info
> edge_info (edge_info_iter
);
4224 logger
->start_log_line ();
4225 logger
->log_partial ("bifurcating for edge: ");
4226 edge_info
->print (logger
->get_printer ());
4227 logger
->end_log_line ();
4229 program_state bifurcated_new_state
4230 (path_ctxt
.get_state_at_bifurcation ());
4232 /* Apply edge_info to state. */
4233 impl_region_model_context
4234 bifurcation_ctxt (*this,
4235 node
, // enode_for_diag
4236 &path_ctxt
.get_state_at_bifurcation (),
4237 &bifurcated_new_state
,
4238 NULL
, // uncertainty_t *uncertainty
4239 NULL
, // path_context *path_ctxt
4241 if (edge_info
->update_state (&bifurcated_new_state
,
4242 NULL
, /* no exploded_edge yet. */
4245 exploded_node
*next2
4246 = get_or_create_node (next_point
, bifurcated_new_state
, node
);
4248 add_edge (node
, next2
, NULL
,
4249 true /* assume that work could be done */,
4250 std::move (edge_info
));
4255 logger
->log ("infeasible state, not adding node");
4260 case PK_AFTER_SUPERNODE
:
4262 bool found_a_superedge
= false;
4263 bool is_an_exit_block
= false;
4264 /* If this is an EXIT BB, detect leaks, and potentially
4265 create a function summary. */
4266 if (point
.get_supernode ()->return_p ())
4268 is_an_exit_block
= true;
4269 node
->detect_leaks (*this);
4270 if (flag_analyzer_call_summaries
4271 && point
.get_call_string ().empty_p ())
4273 /* TODO: create function summary
4274 There can be more than one; each corresponds to a different
4275 final enode in the function. */
4278 pretty_printer
*pp
= logger
->get_printer ();
4279 logger
->start_log_line ();
4281 ("would create function summary for %qE; state: ",
4282 point
.get_fndecl ());
4283 state
.dump_to_pp (m_ext_state
, true, false, pp
);
4284 logger
->end_log_line ();
4286 per_function_data
*per_fn_data
4287 = get_or_create_per_function_data (point
.get_function ());
4288 per_fn_data
->add_call_summary (node
);
4291 /* Traverse into successors of the supernode. */
4294 FOR_EACH_VEC_ELT (point
.get_supernode ()->m_succs
, i
, succ
)
4296 found_a_superedge
= true;
4299 label_text
succ_desc (succ
->get_description (false));
4300 logger
->log ("considering SN: %i -> SN: %i (%s)",
4301 succ
->m_src
->m_index
, succ
->m_dest
->m_index
,
4305 program_point next_point
4306 = program_point::before_supernode (succ
->m_dest
, succ
,
4307 point
.get_call_string ());
4308 program_state
next_state (state
);
4309 uncertainty_t uncertainty
;
4311 /* Make use the current state and try to discover and analyse
4312 indirect function calls (a call that doesn't have an underlying
4313 cgraph edge representing call).
4315 Some examples of such calls are virtual function calls
4316 and calls that happen via a function pointer. */
4317 if (succ
->m_kind
== SUPEREDGE_INTRAPROCEDURAL_CALL
4318 && !(succ
->get_any_callgraph_edge ()))
4321 = point
.get_supernode ()->get_final_call ();
4323 impl_region_model_context
ctxt (*this,
4331 region_model
*model
= state
.m_region_model
;
4332 bool call_discovered
= false;
4334 if (tree fn_decl
= model
->get_fndecl_for_call (call
, &ctxt
))
4335 call_discovered
= maybe_create_dynamic_call (call
,
4342 if (!call_discovered
)
4344 /* Check for jump through NULL. */
4345 if (tree fn_ptr
= gimple_call_fn (call
))
4347 const svalue
*fn_ptr_sval
4348 = model
->get_rvalue (fn_ptr
, &ctxt
);
4349 if (fn_ptr_sval
->all_zeroes_p ())
4350 ctxt
.warn (make_unique
<jump_through_null
> (call
));
4353 /* An unknown function or a special function was called
4354 at this point, in such case, don't terminate the
4355 analysis of the current function.
4357 The analyzer handles calls to such functions while
4358 analysing the stmt itself, so the function call
4359 must have been handled by the anlyzer till now. */
4361 = get_or_create_node (next_point
,
4365 add_edge (node
, next
, succ
,
4366 true /* assume that work is done */);
4370 if (!node
->on_edge (*this, succ
, &next_point
, &next_state
,
4374 logger
->log ("skipping impossible edge to SN: %i",
4375 succ
->m_dest
->m_index
);
4378 exploded_node
*next
= get_or_create_node (next_point
, next_state
,
4382 add_edge (node
, next
, succ
, false);
4384 /* We might have a function entrypoint. */
4385 detect_infinite_recursion (next
);
4389 /* Return from the calls which doesn't have a return superedge.
4390 Such case occurs when GCC's middle end didn't knew which function to
4391 call but analyzer did. */
4392 if ((is_an_exit_block
&& !found_a_superedge
)
4393 && (!point
.get_call_string ().empty_p ()))
4395 const call_string
&cs
= point
.get_call_string ();
4396 program_point next_point
4397 = program_point::before_supernode (cs
.get_caller_node (),
4400 program_state
next_state (state
);
4401 uncertainty_t uncertainty
;
4404 = next_point
.get_supernode ()->get_returning_call ();
4407 next_state
.returning_call (*this, node
, call
, &uncertainty
);
4409 if (next_state
.m_valid
)
4411 next_point
.pop_from_call_stack ();
4412 exploded_node
*enode
= get_or_create_node (next_point
,
4416 add_edge (node
, enode
, NULL
, false,
4417 make_unique
<dynamic_call_info_t
> (call
, true));
4425 /* Ensure that this graph has a stats instance for FN, return it.
4426 FN can be NULL, in which case a stats instances is returned covering
4427 "functionless" parts of the graph (the origin node). */
4430 exploded_graph::get_or_create_function_stats (function
*fn
)
4433 return &m_functionless_stats
;
4435 if (stats
**slot
= m_per_function_stats
.get (fn
))
4439 int num_supernodes
= fn
? n_basic_blocks_for_fn (fn
) : 0;
4440 /* not quite the num supernodes, but nearly. */
4441 stats
*new_stats
= new stats (num_supernodes
);
4442 m_per_function_stats
.put (fn
, new_stats
);
4447 /* Print bar charts to PP showing:
4448 - the number of enodes per function, and
4449 - for each function:
4450 - the number of enodes per supernode/BB
4451 - the number of excess enodes per supernode/BB beyond the
4452 per-program-point limit, if there were any. */
4455 exploded_graph::print_bar_charts (pretty_printer
*pp
) const
4457 cgraph_node
*cgnode
;
4459 pp_string (pp
, "enodes per function:");
4461 bar_chart enodes_per_function
;
4462 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode
)
4464 function
*fn
= cgnode
->get_fun ();
4465 const stats
* const *s_ptr
4466 = const_cast <function_stat_map_t
&> (m_per_function_stats
).get (fn
);
4467 enodes_per_function
.add_item (function_name (fn
),
4468 s_ptr
? (*s_ptr
)->get_total_enodes () : 0);
4470 enodes_per_function
.print (pp
);
4472 /* Accumulate number of enodes per supernode. */
4473 auto_vec
<unsigned> enodes_per_supernode (m_sg
.num_nodes ());
4474 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
4475 enodes_per_supernode
.quick_push (0);
4477 exploded_node
*enode
;
4478 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
4480 const supernode
*iter_snode
= enode
->get_supernode ();
4483 enodes_per_supernode
[iter_snode
->m_index
]++;
4486 /* Accumulate excess enodes per supernode. */
4487 auto_vec
<unsigned> excess_enodes_per_supernode (m_sg
.num_nodes ());
4488 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
4489 excess_enodes_per_supernode
.quick_push (0);
4490 for (point_map_t::iterator iter
= m_per_point_data
.begin ();
4491 iter
!= m_per_point_data
.end (); ++iter
)
4493 const program_point
*point
= (*iter
).first
;
4494 const supernode
*iter_snode
= point
->get_supernode ();
4497 const per_program_point_data
*point_data
= (*iter
).second
;
4498 excess_enodes_per_supernode
[iter_snode
->m_index
]
4499 += point_data
->m_excess_enodes
;
4502 /* Show per-function bar_charts of enodes per supernode/BB. */
4503 pp_string (pp
, "per-function enodes per supernode/BB:");
4505 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (cgnode
)
4507 function
*fn
= cgnode
->get_fun ();
4508 pp_printf (pp
, "function: %qs", function_name (fn
));
4511 bar_chart enodes_per_snode
;
4512 bar_chart excess_enodes_per_snode
;
4513 bool have_excess_enodes
= false;
4514 for (int i
= 0; i
< m_sg
.num_nodes (); i
++)
4516 const supernode
*iter_snode
= m_sg
.get_node_by_index (i
);
4517 if (iter_snode
->get_function () != fn
)
4519 pretty_printer tmp_pp
;
4520 pp_printf (&tmp_pp
, "sn %i (bb %i)",
4521 iter_snode
->m_index
, iter_snode
->m_bb
->index
);
4522 enodes_per_snode
.add_item (pp_formatted_text (&tmp_pp
),
4523 enodes_per_supernode
[iter_snode
->m_index
]);
4524 const int num_excess
4525 = excess_enodes_per_supernode
[iter_snode
->m_index
];
4526 excess_enodes_per_snode
.add_item (pp_formatted_text (&tmp_pp
),
4529 have_excess_enodes
= true;
4531 enodes_per_snode
.print (pp
);
4532 if (have_excess_enodes
)
4534 pp_printf (pp
, "EXCESS ENODES:");
4536 excess_enodes_per_snode
.print (pp
);
4541 /* Write all stats information to this graph's logger, if any. */
4544 exploded_graph::log_stats () const
4546 logger
* const logger
= get_logger ();
4552 m_ext_state
.get_engine ()->log_stats (logger
);
4554 logger
->log ("m_sg.num_nodes (): %i", m_sg
.num_nodes ());
4555 logger
->log ("m_nodes.length (): %i", m_nodes
.length ());
4556 logger
->log ("m_edges.length (): %i", m_edges
.length ());
4557 logger
->log ("remaining enodes in worklist: %i", m_worklist
.length ());
4559 logger
->log ("global stats:");
4560 m_global_stats
.log (logger
);
4562 for (function_stat_map_t::iterator iter
= m_per_function_stats
.begin ();
4563 iter
!= m_per_function_stats
.end ();
4566 function
*fn
= (*iter
).first
;
4567 log_scope
s (logger
, function_name (fn
));
4568 (*iter
).second
->log (logger
);
4571 print_bar_charts (logger
->get_printer ());
4574 /* Dump all stats information to OUT. */
4577 exploded_graph::dump_stats (FILE *out
) const
4579 fprintf (out
, "m_sg.num_nodes (): %i\n", m_sg
.num_nodes ());
4580 fprintf (out
, "m_nodes.length (): %i\n", m_nodes
.length ());
4581 fprintf (out
, "m_edges.length (): %i\n", m_edges
.length ());
4582 fprintf (out
, "remaining enodes in worklist: %i", m_worklist
.length ());
4584 fprintf (out
, "global stats:\n");
4585 m_global_stats
.dump (out
);
4587 for (function_stat_map_t::iterator iter
= m_per_function_stats
.begin ();
4588 iter
!= m_per_function_stats
.end ();
4591 function
*fn
= (*iter
).first
;
4592 fprintf (out
, "function: %s\n", function_name (fn
));
4593 (*iter
).second
->dump (out
);
4596 fprintf (out
, "PK_AFTER_SUPERNODE per supernode:\n");
4597 for (unsigned i
= 0; i
< m_PK_AFTER_SUPERNODE_per_snode
.length (); i
++)
4598 fprintf (out
, " SN %i: %3i\n", i
, m_PK_AFTER_SUPERNODE_per_snode
[i
]);
4602 exploded_graph::dump_states_for_supernode (FILE *out
,
4603 const supernode
*snode
) const
4605 fprintf (out
, "PK_AFTER_SUPERNODE nodes for SN: %i\n", snode
->m_index
);
4607 exploded_node
*enode
;
4609 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
4611 const supernode
*iter_snode
= enode
->get_supernode ();
4612 if (enode
->get_point ().get_kind () == PK_AFTER_SUPERNODE
4613 && iter_snode
== snode
)
4616 pp_format_decoder (&pp
) = default_tree_printer
;
4617 enode
->get_state ().dump_to_pp (m_ext_state
, true, false, &pp
);
4618 fprintf (out
, "state %i: EN: %i\n %s\n",
4619 state_idx
++, enode
->m_index
,
4620 pp_formatted_text (&pp
));
4623 fprintf (out
, "#exploded_node for PK_AFTER_SUPERNODE for SN: %i = %i\n",
4624 snode
->m_index
, state_idx
);
4627 /* Return a new json::object of the form
4628 {"nodes" : [objs for enodes],
4629 "edges" : [objs for eedges],
4630 "ext_state": object for extrinsic_state,
4631 "diagnostic_manager": object for diagnostic_manager}. */
4634 exploded_graph::to_json () const
4636 json::object
*egraph_obj
= new json::object ();
4640 json::array
*nodes_arr
= new json::array ();
4643 FOR_EACH_VEC_ELT (m_nodes
, i
, n
)
4644 nodes_arr
->append (n
->to_json (m_ext_state
));
4645 egraph_obj
->set ("nodes", nodes_arr
);
4650 json::array
*edges_arr
= new json::array ();
4653 FOR_EACH_VEC_ELT (m_edges
, i
, n
)
4654 edges_arr
->append (n
->to_json ());
4655 egraph_obj
->set ("edges", edges_arr
);
4658 /* m_sg is JSONified at the top-level. */
4660 egraph_obj
->set ("ext_state", m_ext_state
.to_json ());
4661 egraph_obj
->set ("worklist", m_worklist
.to_json ());
4662 egraph_obj
->set ("diagnostic_manager", m_diagnostic_manager
.to_json ());
4664 /* The following fields aren't yet being JSONified:
4665 const state_purge_map *const m_purge_map;
4666 const analysis_plan &m_plan;
4667 stats m_global_stats;
4668 function_stat_map_t m_per_function_stats;
4669 stats m_functionless_stats;
4670 call_string_data_map_t m_per_call_string_data;
4671 auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode; */
4676 /* class exploded_path. */
4680 exploded_path::exploded_path (const exploded_path
&other
)
4681 : m_edges (other
.m_edges
.length ())
4684 const exploded_edge
*eedge
;
4685 FOR_EACH_VEC_ELT (other
.m_edges
, i
, eedge
)
4686 m_edges
.quick_push (eedge
);
4689 /* Look for the last use of SEARCH_STMT within this path.
4690 If found write the edge's index to *OUT_IDX and return true, otherwise
4694 exploded_path::find_stmt_backwards (const gimple
*search_stmt
,
4698 const exploded_edge
*eedge
;
4699 FOR_EACH_VEC_ELT_REVERSE (m_edges
, i
, eedge
)
4701 const exploded_node
*dst_node
= eedge
->m_dest
;
4702 const program_point
&dst_point
= dst_node
->get_point ();
4703 const gimple
*stmt
= dst_point
.get_stmt ();
4704 if (stmt
== search_stmt
)
4713 /* Get the final exploded_node in this path, which must be non-empty. */
4716 exploded_path::get_final_enode () const
4718 gcc_assert (m_edges
.length () > 0);
4719 return m_edges
[m_edges
.length () - 1]->m_dest
;
4722 /* Check state along this path, returning true if it is feasible.
4723 If OUT is non-NULL, and the path is infeasible, write a new
4724 feasibility_problem to *OUT. */
4727 exploded_path::feasible_p (logger
*logger
,
4728 std::unique_ptr
<feasibility_problem
> *out
,
4729 engine
*eng
, const exploded_graph
*eg
) const
4733 feasibility_state
state (eng
->get_model_manager (),
4734 eg
->get_supergraph ());
4736 /* Traverse the path, updating this state. */
4737 for (unsigned edge_idx
= 0; edge_idx
< m_edges
.length (); edge_idx
++)
4739 const exploded_edge
*eedge
= m_edges
[edge_idx
];
4741 logger
->log ("considering edge %i: EN:%i -> EN:%i",
4743 eedge
->m_src
->m_index
,
4744 eedge
->m_dest
->m_index
);
4746 std::unique_ptr
<rejected_constraint
> rc
;
4747 if (!state
.maybe_update_for_edge (logger
, eedge
, nullptr, &rc
))
4752 const exploded_node
&src_enode
= *eedge
->m_src
;
4753 const program_point
&src_point
= src_enode
.get_point ();
4754 const gimple
*last_stmt
4755 = src_point
.get_supernode ()->get_last_stmt ();
4756 *out
= ::make_unique
<feasibility_problem
> (edge_idx
, *eedge
,
4765 logger
->log ("state after edge %i: EN:%i -> EN:%i",
4767 eedge
->m_src
->m_index
,
4768 eedge
->m_dest
->m_index
);
4769 logger
->start_log_line ();
4770 state
.get_model ().dump_to_pp (logger
->get_printer (), true, false);
4771 logger
->end_log_line ();
4778 /* Dump this path in multiline form to PP.
4779 If EXT_STATE is non-NULL, then show the nodes. */
4782 exploded_path::dump_to_pp (pretty_printer
*pp
,
4783 const extrinsic_state
*ext_state
) const
4785 for (unsigned i
= 0; i
< m_edges
.length (); i
++)
4787 const exploded_edge
*eedge
= m_edges
[i
];
4788 pp_printf (pp
, "m_edges[%i]: EN %i -> EN %i",
4790 eedge
->m_src
->m_index
,
4791 eedge
->m_dest
->m_index
);
4795 eedge
->m_dest
->dump_to_pp (pp
, *ext_state
);
4799 /* Dump this path in multiline form to FP. */
4802 exploded_path::dump (FILE *fp
, const extrinsic_state
*ext_state
) const
4805 pp_format_decoder (&pp
) = default_tree_printer
;
4806 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
4807 pp
.buffer
->stream
= fp
;
4808 dump_to_pp (&pp
, ext_state
);
4812 /* Dump this path in multiline form to stderr. */
4815 exploded_path::dump (const extrinsic_state
*ext_state
) const
4817 dump (stderr
, ext_state
);
4820 /* Dump this path verbosely to FILENAME. */
4823 exploded_path::dump_to_file (const char *filename
,
4824 const extrinsic_state
&ext_state
) const
4826 FILE *fp
= fopen (filename
, "w");
4830 pp_format_decoder (&pp
) = default_tree_printer
;
4831 pp
.buffer
->stream
= fp
;
4832 dump_to_pp (&pp
, &ext_state
);
4837 /* class feasibility_problem. */
4840 feasibility_problem::dump_to_pp (pretty_printer
*pp
) const
4842 pp_printf (pp
, "edge from EN: %i to EN: %i",
4843 m_eedge
.m_src
->m_index
, m_eedge
.m_dest
->m_index
);
4846 pp_string (pp
, "; rejected constraint: ");
4847 m_rc
->dump_to_pp (pp
);
4848 pp_string (pp
, "; rmodel: ");
4849 m_rc
->get_model ().dump_to_pp (pp
, true, false);
4853 /* class feasibility_state. */
4855 /* Ctor for feasibility_state, at the beginning of a path. */
4857 feasibility_state::feasibility_state (region_model_manager
*manager
,
4858 const supergraph
&sg
)
4859 : m_model (manager
),
4860 m_snodes_visited (sg
.m_nodes
.length ())
4862 bitmap_clear (m_snodes_visited
);
4865 /* Copy ctor for feasibility_state, for extending a path. */
4867 feasibility_state::feasibility_state (const feasibility_state
&other
)
4868 : m_model (other
.m_model
),
4869 m_snodes_visited (const_sbitmap (other
.m_snodes_visited
)->n_bits
)
4871 bitmap_copy (m_snodes_visited
, other
.m_snodes_visited
);
4874 feasibility_state::feasibility_state (const region_model
&model
,
4875 const supergraph
&sg
)
4877 m_snodes_visited (sg
.m_nodes
.length ())
4879 bitmap_clear (m_snodes_visited
);
4883 feasibility_state::operator= (const feasibility_state
&other
)
4885 m_model
= other
.m_model
;
4886 bitmap_copy (m_snodes_visited
, other
.m_snodes_visited
);
4890 /* The heart of feasibility-checking.
4892 Attempt to update this state in-place based on traversing EEDGE
4894 Update the model for the stmts in the src enode.
4895 Attempt to add constraints for EEDGE.
4897 If feasible, return true.
4898 Otherwise, return false and write to *OUT_RC. */
4902 maybe_update_for_edge (logger
*logger
,
4903 const exploded_edge
*eedge
,
4904 region_model_context
*ctxt
,
4905 std::unique_ptr
<rejected_constraint
> *out_rc
)
4907 const exploded_node
&src_enode
= *eedge
->m_src
;
4908 const program_point
&src_point
= src_enode
.get_point ();
4911 logger
->start_log_line ();
4912 src_point
.print (logger
->get_printer (), format (false));
4913 logger
->end_log_line ();
4916 /* Update state for the stmts that were processed in each enode. */
4917 for (unsigned stmt_idx
= 0; stmt_idx
< src_enode
.m_num_processed_stmts
;
4920 const gimple
*stmt
= src_enode
.get_processed_stmt (stmt_idx
);
4922 /* Update cfun and input_location in case of ICE: make it easier to
4923 track down which source construct we're failing to handle. */
4924 auto_cfun
sentinel (src_point
.get_function ());
4925 input_location
= stmt
->location
;
4927 update_for_stmt (stmt
);
4930 const superedge
*sedge
= eedge
->m_sedge
;
4935 label_text
desc (sedge
->get_description (false));
4936 logger
->log (" sedge: SN:%i -> SN:%i %s",
4937 sedge
->m_src
->m_index
,
4938 sedge
->m_dest
->m_index
,
4942 const gimple
*last_stmt
= src_point
.get_supernode ()->get_last_stmt ();
4943 if (!m_model
.maybe_update_for_edge (*sedge
, last_stmt
, ctxt
, out_rc
))
4947 logger
->start_log_line ();
4948 logger
->log_partial ("rejecting due to region model: ");
4949 m_model
.dump_to_pp (logger
->get_printer (), true, false);
4950 logger
->end_log_line ();
4957 /* Special-case the initial eedge from the origin node to the
4958 initial function by pushing a frame for it. */
4959 if (src_point
.get_kind () == PK_ORIGIN
)
4961 gcc_assert (eedge
->m_src
->m_index
== 0);
4962 gcc_assert (eedge
->m_dest
->get_point ().get_kind ()
4963 == PK_BEFORE_SUPERNODE
);
4964 function
*fun
= eedge
->m_dest
->get_function ();
4966 m_model
.push_frame (*fun
, NULL
, ctxt
);
4968 logger
->log (" pushing frame for %qD", fun
->decl
);
4970 else if (eedge
->m_custom_info
)
4972 eedge
->m_custom_info
->update_model (&m_model
, eedge
, ctxt
);
4976 /* Handle phi nodes on an edge leaving a PK_BEFORE_SUPERNODE (to
4977 a PK_BEFORE_STMT, or a PK_AFTER_SUPERNODE if no stmts).
4978 This will typically not be associated with a superedge. */
4979 if (src_point
.get_from_edge ())
4981 const cfg_superedge
*last_cfg_superedge
4982 = src_point
.get_from_edge ()->dyn_cast_cfg_superedge ();
4983 const exploded_node
&dst_enode
= *eedge
->m_dest
;
4984 const unsigned dst_snode_idx
= dst_enode
.get_supernode ()->m_index
;
4985 if (last_cfg_superedge
)
4988 logger
->log (" update for phis");
4989 m_model
.update_for_phis (src_enode
.get_supernode (),
4992 /* If we've entering an snode that we've already visited on this
4993 epath, then we need do fix things up for loops; see the
4994 comment for store::loop_replay_fixup.
4995 Perhaps we should probably also verify the callstring,
4996 and track program_points, but hopefully doing it by supernode
4998 if (bitmap_bit_p (m_snodes_visited
, dst_snode_idx
))
4999 m_model
.loop_replay_fixup (dst_enode
.get_state ().m_region_model
);
5001 bitmap_set_bit (m_snodes_visited
, dst_snode_idx
);
5006 /* Update this object for the effects of STMT. */
5009 feasibility_state::update_for_stmt (const gimple
*stmt
)
5011 if (const gassign
*assign
= dyn_cast
<const gassign
*> (stmt
))
5012 m_model
.on_assignment (assign
, NULL
);
5013 else if (const gasm
*asm_stmt
= dyn_cast
<const gasm
*> (stmt
))
5014 m_model
.on_asm_stmt (asm_stmt
, NULL
);
5015 else if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
5017 bool unknown_side_effects
= m_model
.on_call_pre (call
, NULL
);
5018 m_model
.on_call_post (call
, unknown_side_effects
, NULL
);
5020 else if (const greturn
*return_
= dyn_cast
<const greturn
*> (stmt
))
5021 m_model
.on_return (return_
, NULL
);
5024 /* Dump this object to PP. */
5027 feasibility_state::dump_to_pp (pretty_printer
*pp
,
5028 bool simple
, bool multiline
) const
5030 m_model
.dump_to_pp (pp
, simple
, multiline
);
5033 /* A family of cluster subclasses for use when generating .dot output for
5034 exploded graphs (-fdump-analyzer-exploded-graph), for grouping the
5035 enodes into hierarchical boxes.
5037 All functionless enodes appear in the top-level graph.
5038 Every (function, call_string) pair gets its own cluster. Within that
5039 cluster, each supernode gets its own cluster.
5041 Hence all enodes relating to a particular function with a particular
5042 callstring will be in a cluster together; all enodes for the same
5043 function but with a different callstring will be in a different
5046 /* Base class of cluster for clustering exploded_node instances in .dot
5047 output, based on various subclass-specific criteria. */
5049 class exploded_cluster
: public cluster
<eg_traits
>
5053 /* Cluster containing all exploded_node instances for one supernode. */
5055 class supernode_cluster
: public exploded_cluster
5058 supernode_cluster (const supernode
*supernode
) : m_supernode (supernode
) {}
5062 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const final override
5064 gv
->println ("subgraph \"cluster_supernode_%i\" {", m_supernode
->m_index
);
5066 gv
->println ("style=\"dashed\";");
5067 gv
->println ("label=\"SN: %i (bb: %i; scc: %i)\";",
5068 m_supernode
->m_index
, m_supernode
->m_bb
->index
,
5069 args
.m_eg
.get_scc_id (*m_supernode
));
5072 exploded_node
*enode
;
5073 FOR_EACH_VEC_ELT (m_enodes
, i
, enode
)
5074 enode
->dump_dot (gv
, args
);
5076 /* Terminate subgraph. */
5081 void add_node (exploded_node
*en
) final override
5083 m_enodes
.safe_push (en
);
5086 /* Comparator for use by auto_vec<supernode_cluster *>::qsort. */
5088 static int cmp_ptr_ptr (const void *p1
, const void *p2
)
5090 const supernode_cluster
*c1
5091 = *(const supernode_cluster
* const *)p1
;
5092 const supernode_cluster
*c2
5093 = *(const supernode_cluster
* const *)p2
;
5094 return c1
->m_supernode
->m_index
- c2
->m_supernode
->m_index
;
5098 const supernode
*m_supernode
;
5099 auto_vec
<exploded_node
*> m_enodes
;
5102 /* Cluster containing all supernode_cluster instances for one
5103 (function, call_string) pair. */
5105 class function_call_string_cluster
: public exploded_cluster
5108 function_call_string_cluster (function
*fun
, const call_string
&cs
)
5109 : m_fun (fun
), m_cs (cs
) {}
5111 ~function_call_string_cluster ()
5113 for (map_t::iterator iter
= m_map
.begin ();
5114 iter
!= m_map
.end ();
5116 delete (*iter
).second
;
5119 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const final override
5121 const char *funcname
= function_name (m_fun
);
5123 gv
->println ("subgraph \"cluster_function_%s\" {",
5124 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (m_fun
->decl
)));
5126 gv
->write_indent ();
5127 gv
->print ("label=\"call string: ");
5128 m_cs
.print (gv
->get_pp ());
5129 gv
->print (" function: %s \";", funcname
);
5132 /* Dump m_map, sorting it to avoid churn when comparing dumps. */
5133 auto_vec
<supernode_cluster
*> child_clusters (m_map
.elements ());
5134 for (map_t::iterator iter
= m_map
.begin ();
5135 iter
!= m_map
.end ();
5137 child_clusters
.quick_push ((*iter
).second
);
5139 child_clusters
.qsort (supernode_cluster::cmp_ptr_ptr
);
5142 supernode_cluster
*child_cluster
;
5143 FOR_EACH_VEC_ELT (child_clusters
, i
, child_cluster
)
5144 child_cluster
->dump_dot (gv
, args
);
5146 /* Terminate subgraph. */
5151 void add_node (exploded_node
*en
) final override
5153 const supernode
*supernode
= en
->get_supernode ();
5154 gcc_assert (supernode
);
5155 supernode_cluster
**slot
= m_map
.get (supernode
);
5157 (*slot
)->add_node (en
);
5160 supernode_cluster
*child
= new supernode_cluster (supernode
);
5161 m_map
.put (supernode
, child
);
5162 child
->add_node (en
);
5166 /* Comparator for use by auto_vec<function_call_string_cluster *>. */
5168 static int cmp_ptr_ptr (const void *p1
, const void *p2
)
5170 const function_call_string_cluster
*c1
5171 = *(const function_call_string_cluster
* const *)p1
;
5172 const function_call_string_cluster
*c2
5173 = *(const function_call_string_cluster
* const *)p2
;
5175 = strcmp (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c1
->m_fun
->decl
)),
5176 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c2
->m_fun
->decl
))))
5178 return call_string::cmp (c1
->m_cs
, c2
->m_cs
);
5183 const call_string
&m_cs
;
5184 typedef ordered_hash_map
<const supernode
*, supernode_cluster
*> map_t
;
5188 /* Keys for root_cluster. */
5190 struct function_call_string
5192 function_call_string (function
*fun
, const call_string
*cs
)
5193 : m_fun (fun
), m_cs (cs
)
5200 const call_string
*m_cs
;
5205 template <> struct default_hash_traits
<function_call_string
>
5206 : public pod_hash_traits
<function_call_string
>
5208 static const bool empty_zero_p
= false;
5213 pod_hash_traits
<function_call_string
>::hash (value_type v
)
5215 return (pointer_hash
<function
>::hash (v
.m_fun
)
5216 ^ pointer_hash
<const call_string
>::hash (v
.m_cs
));
5221 pod_hash_traits
<function_call_string
>::equal (const value_type
&existing
,
5222 const value_type
&candidate
)
5224 return existing
.m_fun
== candidate
.m_fun
&& &existing
.m_cs
== &candidate
.m_cs
;
5228 pod_hash_traits
<function_call_string
>::mark_deleted (value_type
&v
)
5230 v
.m_fun
= reinterpret_cast<function
*> (1);
5234 pod_hash_traits
<function_call_string
>::mark_empty (value_type
&v
)
5240 pod_hash_traits
<function_call_string
>::is_deleted (value_type v
)
5242 return v
.m_fun
== reinterpret_cast<function
*> (1);
5246 pod_hash_traits
<function_call_string
>::is_empty (value_type v
)
5248 return v
.m_fun
== NULL
;
5253 /* Top-level cluster for generating .dot output for exploded graphs,
5254 handling the functionless nodes, and grouping the remaining nodes by
5257 class root_cluster
: public exploded_cluster
5262 for (map_t::iterator iter
= m_map
.begin ();
5263 iter
!= m_map
.end ();
5265 delete (*iter
).second
;
5268 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const final override
5271 exploded_node
*enode
;
5272 FOR_EACH_VEC_ELT (m_functionless_enodes
, i
, enode
)
5273 enode
->dump_dot (gv
, args
);
5275 /* Dump m_map, sorting it to avoid churn when comparing dumps. */
5276 auto_vec
<function_call_string_cluster
*> child_clusters (m_map
.elements ());
5277 for (map_t::iterator iter
= m_map
.begin ();
5278 iter
!= m_map
.end ();
5280 child_clusters
.quick_push ((*iter
).second
);
5282 child_clusters
.qsort (function_call_string_cluster::cmp_ptr_ptr
);
5284 function_call_string_cluster
*child_cluster
;
5285 FOR_EACH_VEC_ELT (child_clusters
, i
, child_cluster
)
5286 child_cluster
->dump_dot (gv
, args
);
5289 void add_node (exploded_node
*en
) final override
5291 function
*fun
= en
->get_function ();
5294 m_functionless_enodes
.safe_push (en
);
5298 const call_string
&cs
= en
->get_point ().get_call_string ();
5299 function_call_string
key (fun
, &cs
);
5300 function_call_string_cluster
**slot
= m_map
.get (key
);
5302 (*slot
)->add_node (en
);
5305 function_call_string_cluster
*child
5306 = new function_call_string_cluster (fun
, cs
);
5307 m_map
.put (key
, child
);
5308 child
->add_node (en
);
5313 typedef hash_map
<function_call_string
, function_call_string_cluster
*> map_t
;
5316 /* This should just be the origin exploded_node. */
5317 auto_vec
<exploded_node
*> m_functionless_enodes
;
5320 /* Subclass of range_label for use within
5321 exploded_graph::dump_exploded_nodes for implementing
5322 -fdump-analyzer-exploded-nodes: a label for a specific
5325 class enode_label
: public range_label
5328 enode_label (const extrinsic_state
&ext_state
,
5329 exploded_node
*enode
)
5330 : m_ext_state (ext_state
), m_enode (enode
) {}
5332 label_text
get_text (unsigned) const final override
5335 pp_format_decoder (&pp
) = default_tree_printer
;
5336 m_enode
->get_state ().dump_to_pp (m_ext_state
, true, false, &pp
);
5337 return make_label_text (false, "EN: %i: %s",
5338 m_enode
->m_index
, pp_formatted_text (&pp
));
5342 const extrinsic_state
&m_ext_state
;
5343 exploded_node
*m_enode
;
5346 /* Postprocessing support for dumping the exploded nodes.
5347 Handle -fdump-analyzer-exploded-nodes,
5348 -fdump-analyzer-exploded-nodes-2, and the
5349 "__analyzer_dump_exploded_nodes" builtin. */
5352 exploded_graph::dump_exploded_nodes () const
5355 /* Locate calls to __analyzer_dump_exploded_nodes. */
5356 // Print how many egs there are for them?
5357 /* Better: log them as we go, and record the exploded nodes
5360 /* Show every enode. */
5362 /* Gather them by stmt, so that we can more clearly see the
5363 "hotspots" requiring numerous exploded nodes. */
5365 /* Alternatively, simply throw them all into one big rich_location
5366 and see if the label-printing will sort it out...
5367 This requires them all to be in the same source file. */
5369 if (flag_dump_analyzer_exploded_nodes
)
5371 auto_timevar
tv (TV_ANALYZER_DUMP
);
5372 gcc_rich_location
richloc (UNKNOWN_LOCATION
);
5374 exploded_node
*enode
;
5375 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
5377 if (const gimple
*stmt
= enode
->get_stmt ())
5379 if (get_pure_location (richloc
.get_loc ()) == UNKNOWN_LOCATION
)
5380 richloc
.set_range (0, stmt
->location
, SHOW_RANGE_WITH_CARET
);
5382 richloc
.add_range (stmt
->location
,
5383 SHOW_RANGE_WITHOUT_CARET
,
5384 new enode_label (m_ext_state
, enode
));
5387 warning_at (&richloc
, 0, "%i exploded nodes", m_nodes
.length ());
5389 /* Repeat the warning without all the labels, so that message is visible
5390 (the other one may well have scrolled past the terminal limit). */
5391 warning_at (richloc
.get_loc (), 0,
5392 "%i exploded nodes", m_nodes
.length ());
5394 if (m_worklist
.length () > 0)
5395 warning_at (richloc
.get_loc (), 0,
5396 "worklist still contains %i nodes", m_worklist
.length ());
5399 /* Dump the egraph in textual form to a dump file. */
5400 if (flag_dump_analyzer_exploded_nodes_2
)
5402 auto_timevar
tv (TV_ANALYZER_DUMP
);
5404 = concat (dump_base_name
, ".eg.txt", NULL
);
5405 FILE *outf
= fopen (filename
, "w");
5407 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
5410 fprintf (outf
, "exploded graph for %s\n", dump_base_name
);
5411 fprintf (outf
, " nodes: %i\n", m_nodes
.length ());
5412 fprintf (outf
, " edges: %i\n", m_edges
.length ());
5415 exploded_node
*enode
;
5416 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
5418 fprintf (outf
, "\nEN %i:\n", enode
->m_index
);
5419 enode
->dump_succs_and_preds (outf
);
5421 enode
->get_point ().print (&pp
, format (true));
5422 fprintf (outf
, "%s\n", pp_formatted_text (&pp
));
5423 enode
->get_state ().dump_to_file (m_ext_state
, false, true, outf
);
5429 /* Dump the egraph in textual form to multiple dump files, one per enode. */
5430 if (flag_dump_analyzer_exploded_nodes_3
)
5432 auto_timevar
tv (TV_ANALYZER_DUMP
);
5435 exploded_node
*enode
;
5436 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
5439 = xasprintf ("%s.en-%i.txt", dump_base_name
, i
);
5440 FILE *outf
= fopen (filename
, "w");
5442 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
5445 fprintf (outf
, "EN %i:\n", enode
->m_index
);
5446 enode
->dump_succs_and_preds (outf
);
5448 enode
->get_point ().print (&pp
, format (true));
5449 fprintf (outf
, "%s\n", pp_formatted_text (&pp
));
5450 enode
->get_state ().dump_to_file (m_ext_state
, false, true, outf
);
5456 /* Emit a warning at any call to "__analyzer_dump_exploded_nodes",
5457 giving the number of processed exploded nodes for "before-stmt",
5458 and the IDs of processed, merger, and worklist enodes.
5460 We highlight the count of *processed* enodes since this is of most
5461 interest in DejaGnu tests for ensuring that state merger has
5464 We don't show the count of merger and worklist enodes, as this is
5465 more of an implementation detail of the merging/worklist that we
5466 don't want to bake into our expected DejaGnu messages. */
5469 exploded_node
*enode
;
5470 hash_set
<const gimple
*> seen
;
5471 FOR_EACH_VEC_ELT (m_nodes
, i
, enode
)
5473 if (enode
->get_point ().get_kind () != PK_BEFORE_STMT
)
5476 if (const gimple
*stmt
= enode
->get_stmt ())
5477 if (const gcall
*call
= dyn_cast
<const gcall
*> (stmt
))
5478 if (is_special_named_call_p (call
, "__analyzer_dump_exploded_nodes",
5481 if (seen
.contains (stmt
))
5484 auto_vec
<exploded_node
*> processed_enodes
;
5485 auto_vec
<exploded_node
*> merger_enodes
;
5486 auto_vec
<exploded_node
*> worklist_enodes
;
5487 /* This is O(N^2). */
5489 exploded_node
*other_enode
;
5490 FOR_EACH_VEC_ELT (m_nodes
, j
, other_enode
)
5492 if (other_enode
->get_point ().get_kind () != PK_BEFORE_STMT
)
5494 if (other_enode
->get_stmt () == stmt
)
5495 switch (other_enode
->get_status ())
5499 case exploded_node::STATUS_WORKLIST
:
5500 worklist_enodes
.safe_push (other_enode
);
5502 case exploded_node::STATUS_PROCESSED
:
5503 processed_enodes
.safe_push (other_enode
);
5505 case exploded_node::STATUS_MERGER
:
5506 merger_enodes
.safe_push (other_enode
);
5512 pp_character (&pp
, '[');
5513 print_enode_indices (&pp
, processed_enodes
);
5514 if (merger_enodes
.length () > 0)
5516 pp_string (&pp
, "] merger(s): [");
5517 print_enode_indices (&pp
, merger_enodes
);
5519 if (worklist_enodes
.length () > 0)
5521 pp_string (&pp
, "] worklist: [");
5522 print_enode_indices (&pp
, worklist_enodes
);
5524 pp_character (&pp
, ']');
5526 warning_n (stmt
->location
, 0, processed_enodes
.length (),
5527 "%i processed enode: %s",
5528 "%i processed enodes: %s",
5529 processed_enodes
.length (), pp_formatted_text (&pp
));
5532 /* If the argument is non-zero, then print all of the states
5533 of the various enodes. */
5534 tree t_arg
= fold (gimple_call_arg (call
, 0));
5535 if (TREE_CODE (t_arg
) != INTEGER_CST
)
5537 error_at (call
->location
,
5538 "integer constant required for arg 1");
5541 int i_arg
= TREE_INT_CST_LOW (t_arg
);
5544 exploded_node
*other_enode
;
5545 FOR_EACH_VEC_ELT (processed_enodes
, j
, other_enode
)
5547 fprintf (stderr
, "%i of %i: EN %i:\n",
5548 j
+ 1, processed_enodes
.length (),
5549 other_enode
->m_index
);
5550 other_enode
->dump_succs_and_preds (stderr
);
5552 other_enode
->get_state ().dump (m_ext_state
, false);
5559 DEBUG_FUNCTION exploded_node
*
5560 exploded_graph::get_node_by_index (int idx
) const
5562 exploded_node
*enode
= m_nodes
[idx
];
5563 gcc_assert (enode
->m_index
== idx
);
5567 /* Ensure that there is an exploded_node for a top-level call to FNDECL. */
5570 exploded_graph::on_escaped_function (tree fndecl
)
5572 logger
* const logger
= get_logger ();
5573 LOG_FUNC_1 (logger
, "%qE", fndecl
);
5575 cgraph_node
*cgnode
= cgraph_node::get (fndecl
);
5579 function
*fun
= cgnode
->get_fun ();
5583 if (!gimple_has_body_p (fndecl
))
5586 exploded_node
*enode
= add_function_entry (*fun
);
5590 logger
->log ("created EN %i for %qE entrypoint",
5591 enode
->m_index
, fun
->decl
);
5593 logger
->log ("did not create enode for %qE entrypoint", fun
->decl
);
5597 /* A collection of classes for visualizing the callgraph in .dot form
5598 (as represented in the supergraph). */
5600 /* Forward decls. */
5601 class viz_callgraph_node
;
5602 class viz_callgraph_edge
;
5603 class viz_callgraph
;
5604 class viz_callgraph_cluster
;
5606 /* Traits for using "digraph.h" to visualize the callgraph. */
5608 struct viz_callgraph_traits
5610 typedef viz_callgraph_node node_t
;
5611 typedef viz_callgraph_edge edge_t
;
5612 typedef viz_callgraph graph_t
;
5615 dump_args_t (const exploded_graph
*eg
) : m_eg (eg
) {}
5616 const exploded_graph
*m_eg
;
5618 typedef viz_callgraph_cluster cluster_t
;
5621 /* Subclass of dnode representing a function within the callgraph. */
5623 class viz_callgraph_node
: public dnode
<viz_callgraph_traits
>
5625 friend class viz_callgraph
;
5628 viz_callgraph_node (function
*fun
, int index
)
5629 : m_fun (fun
), m_index (index
), m_num_supernodes (0), m_num_superedges (0)
5634 void dump_dot (graphviz_out
*gv
, const dump_args_t
&args
) const final override
5636 pretty_printer
*pp
= gv
->get_pp ();
5639 pp_printf (pp
, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
5641 pp_write_text_to_stream (pp
);
5643 pp_printf (pp
, "VCG: %i: %s", m_index
, function_name (m_fun
));
5646 pp_printf (pp
, "supernodes: %i\n", m_num_supernodes
);
5649 pp_printf (pp
, "superedges: %i\n", m_num_superedges
);
5655 exploded_node
*enode
;
5656 unsigned num_enodes
= 0;
5657 FOR_EACH_VEC_ELT (args
.m_eg
->m_nodes
, i
, enode
)
5659 if (enode
->get_point ().get_function () == m_fun
)
5662 pp_printf (pp
, "enodes: %i\n", num_enodes
);
5665 // TODO: also show the per-callstring breakdown
5666 const exploded_graph::call_string_data_map_t
*per_cs_data
5667 = args
.m_eg
->get_per_call_string_data ();
5668 for (exploded_graph::call_string_data_map_t::iterator iter
5669 = per_cs_data
->begin ();
5670 iter
!= per_cs_data
->end ();
5673 const call_string
*cs
= (*iter
).first
;
5674 //per_call_string_data *data = (*iter).second;
5676 FOR_EACH_VEC_ELT (args
.m_eg
->m_nodes
, i
, enode
)
5678 if (enode
->get_point ().get_function () == m_fun
5679 && &enode
->get_point ().get_call_string () == cs
)
5685 pp_printf (pp
, ": %i\n", num_enodes
);
5689 /* Show any summaries. */
5690 per_function_data
*data
= args
.m_eg
->get_per_function_data (m_fun
);
5694 pp_printf (pp
, "summaries: %i\n", data
->m_summaries
.length ());
5695 for (auto summary
: data
->m_summaries
)
5697 pp_printf (pp
, "\nsummary: %s:\n", summary
->get_desc ().get ());
5698 const extrinsic_state
&ext_state
= args
.m_eg
->get_ext_state ();
5699 const program_state
&state
= summary
->get_state ();
5700 state
.dump_to_pp (ext_state
, false, true, pp
);
5706 pp_write_text_as_dot_label_to_stream (pp
, /*for_record=*/true);
5707 pp_string (pp
, "\"];\n\n");
5711 void dump_dot_id (pretty_printer
*pp
) const
5713 pp_printf (pp
, "vcg_%i", m_index
);
5719 int m_num_supernodes
;
5720 int m_num_superedges
;
5723 /* Subclass of dedge representing a callgraph edge. */
5725 class viz_callgraph_edge
: public dedge
<viz_callgraph_traits
>
5728 viz_callgraph_edge (viz_callgraph_node
*src
, viz_callgraph_node
*dest
)
5729 : dedge
<viz_callgraph_traits
> (src
, dest
)
5732 void dump_dot (graphviz_out
*gv
, const dump_args_t
&) const
5735 pretty_printer
*pp
= gv
->get_pp ();
5737 const char *style
= "\"solid,bold\"";
5738 const char *color
= "black";
5740 const char *constraint
= "true";
5742 m_src
->dump_dot_id (pp
);
5743 pp_string (pp
, " -> ");
5744 m_dest
->dump_dot_id (pp
);
5746 (" [style=%s, color=%s, weight=%d, constraint=%s,"
5748 style
, color
, weight
, constraint
);
5749 pp_printf (pp
, "\"];\n");
5753 /* Subclass of digraph representing the callgraph. */
5755 class viz_callgraph
: public digraph
<viz_callgraph_traits
>
5758 viz_callgraph (const supergraph
&sg
);
5760 viz_callgraph_node
*get_vcg_node_for_function (function
*fun
)
5762 return *m_map
.get (fun
);
5765 viz_callgraph_node
*get_vcg_node_for_snode (supernode
*snode
)
5767 return get_vcg_node_for_function (snode
->m_fun
);
5771 hash_map
<function
*, viz_callgraph_node
*> m_map
;
5774 /* Placeholder subclass of cluster. */
5776 class viz_callgraph_cluster
: public cluster
<viz_callgraph_traits
>
5780 /* viz_callgraph's ctor. */
5782 viz_callgraph::viz_callgraph (const supergraph
&sg
)
5785 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
5787 function
*fun
= node
->get_fun ();
5788 viz_callgraph_node
*vcg_node
5789 = new viz_callgraph_node (fun
, m_nodes
.length ());
5790 m_map
.put (fun
, vcg_node
);
5791 add_node (vcg_node
);
5796 FOR_EACH_VEC_ELT (sg
.m_edges
, i
, sedge
)
5798 viz_callgraph_node
*vcg_src
= get_vcg_node_for_snode (sedge
->m_src
);
5800 get_vcg_node_for_function (vcg_src
->m_fun
)->m_num_superedges
++;
5801 if (sedge
->dyn_cast_call_superedge ())
5803 viz_callgraph_node
*vcg_dest
= get_vcg_node_for_snode (sedge
->m_dest
);
5804 viz_callgraph_edge
*vcg_edge
5805 = new viz_callgraph_edge (vcg_src
, vcg_dest
);
5806 add_edge (vcg_edge
);
5811 FOR_EACH_VEC_ELT (sg
.m_nodes
, i
, snode
)
5814 get_vcg_node_for_function (snode
->m_fun
)->m_num_supernodes
++;
5818 /* Dump the callgraph to FILENAME. */
5821 dump_callgraph (const supergraph
&sg
, const char *filename
,
5822 const exploded_graph
*eg
)
5824 FILE *outf
= fopen (filename
, "w");
5829 viz_callgraph
vcg (sg
);
5830 vcg
.dump_dot (filename
, NULL
, viz_callgraph_traits::dump_args_t (eg
));
5835 /* Dump the callgraph to "<srcfile>.callgraph.dot". */
5838 dump_callgraph (const supergraph
&sg
, const exploded_graph
*eg
)
5840 auto_timevar
tv (TV_ANALYZER_DUMP
);
5841 char *filename
= concat (dump_base_name
, ".callgraph.dot", NULL
);
5842 dump_callgraph (sg
, filename
, eg
);
5846 /* Subclass of dot_annotator for implementing
5847 DUMP_BASE_NAME.supergraph-eg.dot, a post-analysis dump of the supergraph.
5849 Annotate the supergraph nodes by printing the exploded nodes in concise
5850 form within them, next to their pertinent statements where appropriate,
5851 colorizing the exploded nodes based on sm-state.
5852 Also show saved diagnostics within the exploded nodes, giving information
5853 on whether they were feasible, and, if infeasible, where the problem
5856 class exploded_graph_annotator
: public dot_annotator
5859 exploded_graph_annotator (const exploded_graph
&eg
)
5862 /* Avoid O(N^2) by prepopulating m_enodes_per_snodes. */
5865 FOR_EACH_VEC_ELT (eg
.get_supergraph ().m_nodes
, i
, snode
)
5866 m_enodes_per_snodes
.safe_push (new auto_vec
<exploded_node
*> ());
5867 exploded_node
*enode
;
5868 FOR_EACH_VEC_ELT (m_eg
.m_nodes
, i
, enode
)
5869 if (enode
->get_supernode ())
5870 m_enodes_per_snodes
[enode
->get_supernode ()->m_index
]->safe_push (enode
);
5873 /* Show exploded nodes for BEFORE_SUPERNODE points before N. */
5874 bool add_node_annotations (graphviz_out
*gv
, const supernode
&n
,
5876 const final override
5881 pretty_printer
*pp
= gv
->get_pp ();
5884 pp_string (pp
, "BEFORE");
5885 pp_printf (pp
, " (scc: %i)", m_eg
.get_scc_id (n
));
5889 exploded_node
*enode
;
5890 bool had_enode
= false;
5891 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[n
.m_index
], i
, enode
)
5893 gcc_assert (enode
->get_supernode () == &n
);
5894 const program_point
&point
= enode
->get_point ();
5895 if (point
.get_kind () != PK_BEFORE_SUPERNODE
)
5897 print_enode (gv
, enode
);
5901 pp_string (pp
, "<TD BGCOLOR=\"red\">UNREACHED</TD>");
5907 /* Show exploded nodes for STMT. */
5908 void add_stmt_annotations (graphviz_out
*gv
, const gimple
*stmt
,
5910 const final override
5914 pretty_printer
*pp
= gv
->get_pp ();
5916 const supernode
*snode
5917 = m_eg
.get_supergraph ().get_supernode_for_stmt (stmt
);
5919 exploded_node
*enode
;
5920 bool had_td
= false;
5921 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[snode
->m_index
], i
, enode
)
5923 const program_point
&point
= enode
->get_point ();
5924 if (point
.get_kind () != PK_BEFORE_STMT
)
5926 if (point
.get_stmt () != stmt
)
5928 print_enode (gv
, enode
);
5939 /* Show exploded nodes for AFTER_SUPERNODE points after N. */
5940 bool add_after_node_annotations (graphviz_out
*gv
, const supernode
&n
)
5941 const final override
5944 pretty_printer
*pp
= gv
->get_pp ();
5947 pp_string (pp
, "AFTER");
5951 exploded_node
*enode
;
5952 FOR_EACH_VEC_ELT (*m_enodes_per_snodes
[n
.m_index
], i
, enode
)
5954 gcc_assert (enode
->get_supernode () == &n
);
5955 const program_point
&point
= enode
->get_point ();
5956 if (point
.get_kind () != PK_AFTER_SUPERNODE
)
5958 print_enode (gv
, enode
);
5966 /* Concisely print a TD element for ENODE, showing the index, status,
5967 and any saved_diagnostics at the enode. Colorize it to show sm-state.
5969 Ideally we'd dump ENODE's state here, hidden behind some kind of
5970 interactive disclosure method like a tooltip, so that the states
5971 can be explored without overwhelming the graph.
5972 However, I wasn't able to get graphviz/xdot to show tooltips on
5973 individual elements within a HTML-like label. */
5974 void print_enode (graphviz_out
*gv
, const exploded_node
*enode
) const
5976 pretty_printer
*pp
= gv
->get_pp ();
5977 pp_printf (pp
, "<TD BGCOLOR=\"%s\">",
5978 enode
->get_dot_fillcolor ());
5979 pp_printf (pp
, "<TABLE BORDER=\"0\">");
5981 pp_printf (pp
, "EN: %i", enode
->m_index
);
5982 switch (enode
->get_status ())
5986 case exploded_node::STATUS_WORKLIST
:
5987 pp_string (pp
, "(W)");
5989 case exploded_node::STATUS_PROCESSED
:
5991 case exploded_node::STATUS_MERGER
:
5992 pp_string (pp
, "(M)");
5994 case exploded_node::STATUS_BULK_MERGED
:
5995 pp_string (pp
, "(BM)");
6000 /* Dump any saved_diagnostics at this enode. */
6001 for (unsigned i
= 0; i
< enode
->get_num_diagnostics (); i
++)
6003 const saved_diagnostic
*sd
= enode
->get_saved_diagnostic (i
);
6004 print_saved_diagnostic (gv
, sd
);
6006 pp_printf (pp
, "</TABLE>");
6007 pp_printf (pp
, "</TD>");
6010 /* Print a TABLE element for SD, showing the kind, the length of the
6011 exploded_path, whether the path was feasible, and if infeasible,
6012 what the problem was. */
6013 void print_saved_diagnostic (graphviz_out
*gv
,
6014 const saved_diagnostic
*sd
) const
6016 pretty_printer
*pp
= gv
->get_pp ();
6018 pp_printf (pp
, "<TABLE BORDER=\"0\">");
6020 pp_string (pp
, "<TD BGCOLOR=\"green\">");
6021 pp_printf (pp
, "DIAGNOSTIC: %s", sd
->m_d
->get_kind ());
6024 if (sd
->get_best_epath ())
6025 pp_printf (pp
, "epath length: %i", sd
->get_epath_length ());
6027 pp_printf (pp
, "no best epath");
6029 if (const feasibility_problem
*p
= sd
->get_feasibility_problem ())
6032 pp_printf (pp
, "INFEASIBLE at eedge %i: EN:%i -> EN:%i",
6034 p
->m_eedge
.m_src
->m_index
,
6035 p
->m_eedge
.m_dest
->m_index
);
6036 pp_write_text_as_html_like_dot_to_stream (pp
);
6039 p
->m_eedge
.m_sedge
->dump (pp
);
6040 pp_write_text_as_html_like_dot_to_stream (pp
);
6043 pp_gimple_stmt_1 (pp
, p
->m_last_stmt
, 0, (dump_flags_t
)0);
6044 pp_write_text_as_html_like_dot_to_stream (pp
);
6046 /* Ideally we'd print p->m_model here; see the notes above about
6049 pp_printf (pp
, "</TABLE>");
6053 const exploded_graph
&m_eg
;
6054 auto_delete_vec
<auto_vec
<exploded_node
*> > m_enodes_per_snodes
;
6057 /* Implement -fdump-analyzer-json. */
6060 dump_analyzer_json (const supergraph
&sg
,
6061 const exploded_graph
&eg
)
6063 auto_timevar
tv (TV_ANALYZER_DUMP
);
6064 char *filename
= concat (dump_base_name
, ".analyzer.json.gz", NULL
);
6065 gzFile output
= gzopen (filename
, "w");
6068 error_at (UNKNOWN_LOCATION
, "unable to open %qs for writing", filename
);
6073 json::object
*toplev_obj
= new json::object ();
6074 toplev_obj
->set ("sgraph", sg
.to_json ());
6075 toplev_obj
->set ("egraph", eg
.to_json ());
6078 toplev_obj
->print (&pp
, flag_diagnostics_json_formatting
);
6079 pp_formatted_text (&pp
);
6083 if (gzputs (output
, pp_formatted_text (&pp
)) == EOF
6084 || gzclose (output
))
6085 error_at (UNKNOWN_LOCATION
, "error writing %qs", filename
);
6090 /* Concrete subclass of plugin_analyzer_init_iface, allowing plugins
6091 to register new state machines. */
6093 class plugin_analyzer_init_impl
: public plugin_analyzer_init_iface
6096 plugin_analyzer_init_impl (auto_delete_vec
<state_machine
> *checkers
,
6097 known_function_manager
*known_fn_mgr
,
6099 : m_checkers (checkers
),
6100 m_known_fn_mgr (known_fn_mgr
),
6104 void register_state_machine (std::unique_ptr
<state_machine
> sm
) final override
6106 LOG_SCOPE (m_logger
);
6107 m_checkers
->safe_push (sm
.release ());
6110 void register_known_function (const char *name
,
6111 std::unique_ptr
<known_function
> kf
) final override
6113 LOG_SCOPE (m_logger
);
6114 m_known_fn_mgr
->add (name
, std::move (kf
));
6117 logger
*get_logger () const final override
6123 auto_delete_vec
<state_machine
> *m_checkers
;
6124 known_function_manager
*m_known_fn_mgr
;
6128 /* Run the analysis "engine". */
6131 impl_run_checkers (logger
*logger
)
6137 logger
->log ("BITS_BIG_ENDIAN: %i", BITS_BIG_ENDIAN
? 1 : 0);
6138 logger
->log ("BYTES_BIG_ENDIAN: %i", BYTES_BIG_ENDIAN
? 1 : 0);
6139 logger
->log ("WORDS_BIG_ENDIAN: %i", WORDS_BIG_ENDIAN
? 1 : 0);
6140 log_stashed_constants (logger
);
6143 /* If using LTO, ensure that the cgraph nodes have function bodies. */
6145 FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node
)
6146 node
->get_untransformed_body ();
6148 /* Create the supergraph. */
6149 supergraph
sg (logger
);
6151 engine
eng (&sg
, logger
);
6153 state_purge_map
*purge_map
= NULL
;
6155 if (flag_analyzer_state_purge
)
6156 purge_map
= new state_purge_map (sg
, eng
.get_model_manager (), logger
);
6158 if (flag_dump_analyzer_supergraph
)
6160 /* Dump supergraph pre-analysis. */
6161 auto_timevar
tv (TV_ANALYZER_DUMP
);
6162 char *filename
= concat (dump_base_name
, ".supergraph.dot", NULL
);
6163 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, NULL
);
6164 sg
.dump_dot (filename
, args
);
6168 if (flag_dump_analyzer_state_purge
)
6170 auto_timevar
tv (TV_ANALYZER_DUMP
);
6171 state_purge_annotator
a (purge_map
);
6172 char *filename
= concat (dump_base_name
, ".state-purge.dot", NULL
);
6173 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, &a
);
6174 sg
.dump_dot (filename
, args
);
6178 auto_delete_vec
<state_machine
> checkers
;
6179 make_checkers (checkers
, logger
);
6181 register_known_functions (*eng
.get_known_function_manager (),
6182 *eng
.get_model_manager ());
6184 plugin_analyzer_init_impl
data (&checkers
,
6185 eng
.get_known_function_manager (),
6187 invoke_plugin_callbacks (PLUGIN_ANALYZER_INIT
, &data
);
6193 FOR_EACH_VEC_ELT (checkers
, i
, sm
)
6194 logger
->log ("checkers[%i]: %s", i
, sm
->get_name ());
6197 /* Extrinsic state shared by nodes in the graph. */
6198 const extrinsic_state
ext_state (checkers
, &eng
, logger
);
6200 const analysis_plan
plan (sg
, logger
);
6202 /* The exploded graph. */
6203 exploded_graph
eg (sg
, logger
, ext_state
, purge_map
, plan
,
6204 analyzer_verbosity
);
6206 /* Add entrypoints to the graph for externally-callable functions. */
6207 eg
.build_initial_worklist ();
6209 /* Now process the worklist, exploring the <point, state> graph. */
6210 eg
.process_worklist ();
6212 if (warn_analyzer_infinite_loop
)
6213 eg
.detect_infinite_loops ();
6215 if (flag_dump_analyzer_exploded_graph
)
6217 auto_timevar
tv (TV_ANALYZER_DUMP
);
6219 = concat (dump_base_name
, ".eg.dot", NULL
);
6220 exploded_graph::dump_args_t
args (eg
);
6222 eg
.dump_dot (filename
, &c
, args
);
6226 /* Now emit any saved diagnostics. */
6227 eg
.get_diagnostic_manager ().emit_saved_diagnostics (eg
);
6229 eg
.dump_exploded_nodes ();
6233 if (flag_dump_analyzer_callgraph
)
6234 dump_callgraph (sg
, &eg
);
6236 if (flag_dump_analyzer_supergraph
)
6238 /* Dump post-analysis form of supergraph. */
6239 auto_timevar
tv (TV_ANALYZER_DUMP
);
6240 char *filename
= concat (dump_base_name
, ".supergraph-eg.dot", NULL
);
6241 exploded_graph_annotator
a (eg
);
6242 supergraph::dump_args_t
args ((enum supergraph_dot_flags
)0, &a
);
6243 sg
.dump_dot (filename
, args
);
6247 if (flag_dump_analyzer_json
)
6248 dump_analyzer_json (sg
, eg
);
6250 if (flag_dump_analyzer_untracked
)
6251 eng
.get_model_manager ()->dump_untracked_regions ();
6256 /* Handle -fdump-analyzer and -fdump-analyzer-stderr. */
6257 static FILE *dump_fout
= NULL
;
6259 /* Track if we're responsible for closing dump_fout. */
6260 static bool owns_dump_fout
= false;
6262 /* If dumping is enabled, attempt to create dump_fout if it hasn't already
6263 been opened. Return it. */
6266 get_or_create_any_logfile ()
6270 if (flag_dump_analyzer_stderr
)
6272 else if (flag_dump_analyzer
)
6274 char *dump_filename
= concat (dump_base_name
, ".analyzer.txt", NULL
);
6275 dump_fout
= fopen (dump_filename
, "w");
6276 free (dump_filename
);
6278 owns_dump_fout
= true;
6284 /* External entrypoint to the analysis "engine".
6285 Set up any dumps, then call impl_run_checkers. */
6290 /* Save input_location. */
6291 location_t saved_input_location
= input_location
;
6294 log_user
the_logger (NULL
);
6295 get_or_create_any_logfile ();
6297 the_logger
.set_logger (new logger (dump_fout
, 0, 0,
6298 *global_dc
->printer
));
6299 LOG_SCOPE (the_logger
.get_logger ());
6301 impl_run_checkers (the_logger
.get_logger ());
6303 /* end of lifetime of the_logger (so that dump file is closed after the
6304 various dtors run). */
6310 owns_dump_fout
= false;
6314 /* Restore input_location. Subsequent passes may assume that input_location
6315 is some arbitrary value *not* in the block tree, which might be violated
6316 if we didn't restore it. */
6317 input_location
= saved_input_location
;
6322 #endif /* #if ENABLE_ANALYZER */