1 /* Classes for representing locations within the program.
2 Copyright (C) 2019-2025 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/>. */
21 #include "analyzer/common.h"
23 #include "diagnostic-event-id.h"
24 #include "gcc-rich-location.h"
25 #include "gimple-pretty-print.h"
28 #include "shortest-paths.h"
30 #include "analyzer/analyzer-logging.h"
31 #include "analyzer/call-string.h"
32 #include "analyzer/supergraph.h"
33 #include "analyzer/program-point.h"
34 #include "analyzer/store.h"
35 #include "analyzer/region-model.h"
36 #include "analyzer/sm.h"
37 #include "analyzer/program-state.h"
38 #include "analyzer/pending-diagnostic.h"
39 #include "analyzer/diagnostic-manager.h"
40 #include "analyzer/exploded-graph.h"
41 #include "analyzer/analysis-plan.h"
42 #include "analyzer/inlining-iterator.h"
48 /* Get a string for PK. */
51 point_kind_to_string (enum point_kind pk
)
59 case PK_BEFORE_SUPERNODE
:
60 return "PK_BEFORE_SUPERNODE";
62 return "PK_BEFORE_STMT";
63 case PK_AFTER_SUPERNODE
:
64 return "PK_AFTER_SUPERNODE";
72 /* class function_point. */
74 function_point::function_point (const supernode
*supernode
,
75 const superedge
*from_edge
,
78 : m_supernode (supernode
), m_from_edge (from_edge
),
79 m_stmt_idx (stmt_idx
), m_kind (kind
)
83 gcc_checking_assert (m_kind
== PK_BEFORE_SUPERNODE
);
84 gcc_checking_assert (from_edge
->get_kind () == SUPEREDGE_CFG_EDGE
);
87 gcc_checking_assert (m_kind
== PK_BEFORE_STMT
);
90 /* Print this function_point to PP. */
93 function_point::print (pretty_printer
*pp
, const format
&f
) const
101 pp_printf (pp
, "origin");
106 case PK_BEFORE_SUPERNODE
:
110 if (basic_block bb
= m_from_edge
->m_src
->m_bb
)
111 pp_printf (pp
, "before SN: %i (from SN: %i (bb: %i))",
112 m_supernode
->m_index
, m_from_edge
->m_src
->m_index
,
115 pp_printf (pp
, "before SN: %i (from SN: %i)",
116 m_supernode
->m_index
, m_from_edge
->m_src
->m_index
);
119 pp_printf (pp
, "before SN: %i (NULL from-edge)",
120 m_supernode
->m_index
);
122 for (gphi_iterator gpi
123 = const_cast<supernode
*>(get_supernode ())->start_phis ();
124 !gsi_end_p (gpi
); gsi_next (&gpi
))
126 const gphi
*phi
= gpi
.phi ();
127 pp_gimple_stmt_1 (pp
, phi
, 0, (dump_flags_t
)0);
133 pp_printf (pp
, "before (SN: %i stmt: %i): ", m_supernode
->m_index
,
136 pp_gimple_stmt_1 (pp
, get_stmt (), 0, (dump_flags_t
)0);
140 print_source_line (pp
);
144 case PK_AFTER_SUPERNODE
:
145 pp_printf (pp
, "after SN: %i", m_supernode
->m_index
);
152 /* Generate a hash value for this function_point. */
155 function_point::hash () const
157 inchash::hash hstate
;
159 hstate
.add_int (m_supernode
->m_index
);
160 hstate
.add_ptr (m_from_edge
);
161 hstate
.add_int (m_stmt_idx
);
162 hstate
.add_int (m_kind
);
163 return hstate
.end ();
166 /* Get the function at this point, if any. */
169 function_point::get_function () const
172 return m_supernode
->m_fun
;
177 /* Get the gimple stmt for this function_point, if any. */
180 function_point::get_stmt () const
182 if (m_kind
== PK_BEFORE_STMT
)
183 return m_supernode
->m_stmts
[m_stmt_idx
];
184 else if (m_kind
== PK_AFTER_SUPERNODE
)
185 return m_supernode
->get_last_stmt ();
190 /* Get a location for this function_point, if any. */
193 function_point::get_location () const
195 const gimple
*stmt
= get_stmt ();
197 return stmt
->location
;
198 if (m_kind
== PK_BEFORE_SUPERNODE
)
199 return m_supernode
->get_start_location ();
200 else if (m_kind
== PK_AFTER_SUPERNODE
)
201 return m_supernode
->get_end_location ();
203 return UNKNOWN_LOCATION
;
206 /* Return true if this function_point is a before_stmt for
207 the final stmt in its supernode. */
210 function_point::final_stmt_p () const
212 if (m_kind
!= PK_BEFORE_STMT
)
214 return m_stmt_idx
== get_supernode ()->m_stmts
.length () - 1;
217 /* Create a function_point representing the entrypoint of function FUN. */
220 function_point::from_function_entry (const supergraph
&sg
, const function
&fun
)
222 return before_supernode (sg
.get_node_for_function_entry (fun
), nullptr);
225 /* Create a function_point representing entering supernode SUPERNODE,
226 having reached it via FROM_EDGE (which could be nullptr). */
229 function_point::before_supernode (const supernode
*supernode
,
230 const superedge
*from_edge
)
232 if (from_edge
&& from_edge
->get_kind () != SUPEREDGE_CFG_EDGE
)
234 return function_point (supernode
, from_edge
, 0, PK_BEFORE_SUPERNODE
);
237 /* A subclass of diagnostic_context for use by
238 program_point::print_source_line. */
240 class debug_diagnostic_context
: public diagnostic_context
243 debug_diagnostic_context ()
245 diagnostic_initialize (this, 0);
246 m_source_printing
.show_line_numbers_p
= true;
247 m_source_printing
.enabled
= true;
249 ~debug_diagnostic_context ()
251 diagnostic_finish (this);
255 /* Print the source line (if any) for this function_point to PP. */
258 function_point::print_source_line (pretty_printer
*pp
) const
260 const gimple
*stmt
= get_stmt ();
263 // TODO: monospace font
264 debug_diagnostic_context tmp_dc
;
265 gcc_rich_location
richloc (stmt
->location
);
266 diagnostic_source_print_policy
source_policy (tmp_dc
);
268 source_policy
.print (*pp
, richloc
, DK_ERROR
, nullptr);
269 pp_string (pp
, pp_formatted_text (tmp_dc
.get_reference_printer ()));
272 /* class program_point. */
274 /* Print this program_point to PP. */
277 program_point::print (pretty_printer
*pp
, const format
&f
) const
279 pp_string (pp
, "callstring: ");
280 m_call_string
->print (pp
);
283 m_function_point
.print (pp
, f
);
286 /* Dump this point to stderr. */
289 program_point::dump () const
291 tree_dump_pretty_printer
pp (stderr
);
292 print (&pp
, format (true));
295 /* Return a new json::object of the form
297 "snode_idx" : int (optional), the index of the supernode,
298 "from_edge_snode_idx" : int (only for kind=='PK_BEFORE_SUPERNODE'),
299 "stmt_idx": int (only for kind=='PK_BEFORE_STMT',
300 "call_string": object for the call_string}. */
302 std::unique_ptr
<json::object
>
303 program_point::to_json () const
305 auto point_obj
= std::make_unique
<json::object
> ();
307 point_obj
->set_string ("kind", point_kind_to_string (get_kind ()));
309 if (get_supernode ())
310 point_obj
->set_integer ("snode_idx", get_supernode ()->m_index
);
315 case PK_BEFORE_SUPERNODE
:
316 if (const superedge
*sedge
= get_from_edge ())
317 point_obj
->set_integer ("from_edge_snode_idx", sedge
->m_src
->m_index
);
320 point_obj
->set_integer ("stmt_idx", get_stmt_idx ());
324 point_obj
->set ("call_string", m_call_string
->to_json ());
329 /* Update the callstack to represent a call from caller to callee.
331 Generally used to push a custom call to a perticular program point
332 where we don't have a superedge representing the call. */
334 program_point::push_to_call_stack (const supernode
*caller
,
335 const supernode
*callee
)
337 m_call_string
= m_call_string
->push_call (callee
, caller
);
340 /* Pop the topmost call from the current callstack. */
342 program_point::pop_from_call_stack ()
344 m_call_string
= m_call_string
->get_parent ();
345 gcc_assert (m_call_string
);
348 /* Generate a hash value for this program_point. */
351 program_point::hash () const
353 inchash::hash hstate
;
354 hstate
.merge_hash (m_function_point
.hash ());
355 hstate
.add_ptr (m_call_string
);
356 return hstate
.end ();
359 /* Get the function * at DEPTH within the call stack. */
362 program_point::get_function_at_depth (unsigned depth
) const
364 gcc_assert (depth
<= m_call_string
->length ());
365 if (depth
== m_call_string
->length ())
366 return m_function_point
.get_function ();
368 return get_call_string ()[depth
].get_caller_function ();
371 /* Assert that this object is sane. */
374 program_point::validate () const
376 /* Skip this in a release build. */
381 m_call_string
->validate ();
382 /* The "callee" of the final entry in the callstring should be the
383 function of the m_function_point. */
384 if (m_call_string
->length () > 0)
386 ((*m_call_string
)[m_call_string
->length () - 1].get_callee_function ()
390 /* Check to see if SUCC is a valid edge to take (ensuring that we have
391 interprocedurally valid paths in the exploded graph, and enforcing
394 Update the call string if SUCC is a call or a return.
396 Return true if SUCC can be taken, or false otherwise.
398 This is the "point" half of exploded_node::on_edge. */
401 program_point::on_edge (exploded_graph
&eg
,
402 const superedge
*succ
)
404 logger
* const logger
= eg
.get_logger ();
406 switch (succ
->m_kind
)
408 case SUPEREDGE_CFG_EDGE
:
410 const cfg_superedge
*cfg_sedge
= as_a
<const cfg_superedge
*> (succ
);
412 if (cfg_sedge
->get_flags () & EDGE_ABNORMAL
)
414 const supernode
*src_snode
= cfg_sedge
->m_src
;
415 if (gimple
*last_stmt
= src_snode
->get_last_stmt ())
416 if (last_stmt
->code
== GIMPLE_GOTO
)
418 /* For the program_point aspect here, consider all
419 out-edges from goto stmts to be valid; we'll
420 consider state separately. */
424 /* Reject other kinds of abnormal edges;
425 we special-case setjmp/longjmp. */
433 const call_superedge
*call_sedge
= as_a
<const call_superedge
*> (succ
);
435 if (eg
.get_analysis_plan ().use_summary_p (call_sedge
->m_cedge
))
438 logger
->log ("rejecting call edge: using summary instead");
442 /* Add the callsite to the call string. */
443 m_call_string
= m_call_string
->push_call (eg
.get_supergraph (),
446 /* Impose a maximum recursion depth and don't analyze paths
447 that exceed it further.
448 This is something of a blunt workaround, but it only
449 applies to recursion (and mutual recursion), not to
450 general call stacks. */
451 if (m_call_string
->calc_recursion_depth ()
452 > param_analyzer_max_recursion_depth
)
455 logger
->log ("rejecting call edge: recursion limit exceeded");
456 // TODO: issue a sorry for this?
462 case SUPEREDGE_RETURN
:
464 /* Require that we return to the call site in the call string. */
465 if (m_call_string
->empty_p ())
468 logger
->log ("rejecting return edge: empty call string");
471 const call_string::element_t
&top_of_stack
472 = m_call_string
->get_top_of_stack ();
473 m_call_string
= m_call_string
->get_parent ();
474 call_string::element_t
current_call_string_element (succ
->m_dest
,
476 if (top_of_stack
!= current_call_string_element
)
479 logger
->log ("rejecting return edge: return to wrong callsite");
485 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
487 const callgraph_superedge
*cg_sedge
488 = as_a
<const callgraph_superedge
*> (succ
);
489 /* Consider turning this edge into a use of an
490 interprocedural summary. */
491 if (eg
.get_analysis_plan ().use_summary_p (cg_sedge
->m_cedge
))
494 logger
->log ("using function summary for %qE in %qE",
495 cg_sedge
->get_callee_decl (),
496 cg_sedge
->get_caller_decl ());
501 /* Otherwise, we ignore these edges */
503 logger
->log ("rejecting interprocedural edge");
512 /* Comparator for program points within the same supernode,
513 for implementing worklist::key_t comparison operators.
514 Return negative if POINT_A is before POINT_B
515 Return positive if POINT_A is after POINT_B
516 Return 0 if they are equal. */
519 function_point::cmp_within_supernode_1 (const function_point
&point_a
,
520 const function_point
&point_b
)
522 gcc_assert (point_a
.get_supernode () == point_b
.get_supernode ());
524 switch (point_a
.m_kind
)
528 case PK_BEFORE_SUPERNODE
:
529 switch (point_b
.m_kind
)
533 case PK_BEFORE_SUPERNODE
:
537 if (point_a
.m_from_edge
)
538 a_src_idx
= point_a
.m_from_edge
->m_src
->m_index
;
539 if (point_b
.m_from_edge
)
540 b_src_idx
= point_b
.m_from_edge
->m_src
->m_index
;
541 return a_src_idx
- b_src_idx
;
546 case PK_AFTER_SUPERNODE
:
551 switch (point_b
.m_kind
)
555 case PK_BEFORE_SUPERNODE
:
559 return point_a
.m_stmt_idx
- point_b
.m_stmt_idx
;
561 case PK_AFTER_SUPERNODE
:
565 case PK_AFTER_SUPERNODE
:
566 switch (point_b
.m_kind
)
570 case PK_BEFORE_SUPERNODE
:
574 case PK_AFTER_SUPERNODE
:
581 /* Comparator for program points within the same supernode,
582 for implementing worklist::key_t comparison operators.
583 Return negative if POINT_A is before POINT_B
584 Return positive if POINT_A is after POINT_B
585 Return 0 if they are equal. */
588 function_point::cmp_within_supernode (const function_point
&point_a
,
589 const function_point
&point_b
)
591 int result
= cmp_within_supernode_1 (point_a
, point_b
);
593 /* Check that the ordering is symmetric */
595 int reversed
= cmp_within_supernode_1 (point_b
, point_a
);
596 gcc_assert (reversed
== -result
);
602 /* Comparator for imposing an order on function_points. */
605 function_point::cmp (const function_point
&point_a
,
606 const function_point
&point_b
)
608 int idx_a
= point_a
.m_supernode
? point_a
.m_supernode
->m_index
: -1;
609 int idx_b
= point_b
.m_supernode
? point_b
.m_supernode
->m_index
: -1;
610 if (int cmp_idx
= idx_a
- idx_b
)
612 gcc_assert (point_a
.m_supernode
== point_b
.m_supernode
);
613 if (point_a
.m_supernode
)
614 return cmp_within_supernode (point_a
, point_b
);
619 /* Comparator for use by vec<function_point>::qsort. */
622 function_point::cmp_ptr (const void *p1
, const void *p2
)
624 const function_point
*fp1
= (const function_point
*)p1
;
625 const function_point
*fp2
= (const function_point
*)p2
;
626 return cmp (*fp1
, *fp2
);
629 /* For PK_BEFORE_STMT, go to next stmt (or to PK_AFTER_SUPERNODE). */
632 function_point::next_stmt ()
634 gcc_assert (m_kind
== PK_BEFORE_STMT
);
635 if (++m_stmt_idx
== m_supernode
->m_stmts
.length ())
637 m_kind
= PK_AFTER_SUPERNODE
;
642 /* For those function points for which there is a uniquely-defined
643 successor, return it. */
646 function_point::get_next () const
653 case PK_AFTER_SUPERNODE
:
654 gcc_unreachable (); /* Not uniquely defined. */
655 case PK_BEFORE_SUPERNODE
:
656 if (get_supernode ()->m_stmts
.length () > 0)
657 return before_stmt (get_supernode (), 0);
659 return after_supernode (get_supernode ());
662 unsigned next_idx
= get_stmt_idx () + 1;
663 if (next_idx
< get_supernode ()->m_stmts
.length ())
664 return before_stmt (get_supernode (), next_idx
);
666 return after_supernode (get_supernode ());
671 /* class program_point. */
674 program_point::origin (const region_model_manager
&mgr
)
676 return program_point (function_point (nullptr, nullptr,
678 mgr
.get_empty_call_string ());
682 program_point::from_function_entry (const region_model_manager
&mgr
,
683 const supergraph
&sg
,
686 return program_point (function_point::from_function_entry (sg
, fun
),
687 mgr
.get_empty_call_string ());
690 /* For those program points for which there is a uniquely-defined
691 successor, return it. */
694 program_point::get_next () const
696 switch (m_function_point
.get_kind ())
701 case PK_AFTER_SUPERNODE
:
702 gcc_unreachable (); /* Not uniquely defined. */
703 case PK_BEFORE_SUPERNODE
:
704 if (get_supernode ()->m_stmts
.length () > 0)
705 return before_stmt (get_supernode (), 0, get_call_string ());
707 return after_supernode (get_supernode (), get_call_string ());
710 unsigned next_idx
= get_stmt_idx () + 1;
711 if (next_idx
< get_supernode ()->m_stmts
.length ())
712 return before_stmt (get_supernode (), next_idx
, get_call_string ());
714 return after_supernode (get_supernode (), get_call_string ());
719 /* Return true iff POINT_A and POINT_B share the same function and
720 call_string, both directly, and when attempting to undo inlining
724 program_point::effectively_intraprocedural_p (const program_point
&point_a
,
725 const program_point
&point_b
)
727 /* First, compare without considering inlining info. */
728 if (point_a
.get_function ()
729 != point_b
.get_function ())
731 if (&point_a
.get_call_string ()
732 != &point_b
.get_call_string ())
735 /* Consider inlining info; they must have originally come from
736 the same function and have been inlined in the same way. */
737 location_t loc_a
= point_a
.get_location ();
738 location_t loc_b
= point_b
.get_location ();
739 inlining_iterator
iter_a (loc_a
);
740 inlining_iterator
iter_b (loc_b
);
741 while (!(iter_a
.done_p () || iter_b
.done_p ()))
743 if (iter_a
.done_p () || iter_b
.done_p ())
746 if (iter_a
.get_fndecl () != iter_b
.get_fndecl ())
748 if (iter_a
.get_callsite () != iter_b
.get_callsite ())
750 if (iter_a
.get_block () != iter_b
.get_block ())
764 /* Verify that function_point::operator== works as expected. */
767 test_function_point_equality ()
769 const supernode
*snode
= nullptr;
771 function_point a
= function_point (snode
, nullptr, 0,
772 PK_BEFORE_SUPERNODE
);
773 function_point b
= function_point::before_supernode (snode
, nullptr);
777 /* Verify that function_point::cmp_within_supernode works as expected. */
780 test_function_point_ordering ()
782 const supernode
*snode
= nullptr;
784 /* Populate an array with various points within the same
786 auto_vec
<function_point
> points
;
787 points
.safe_push (function_point::before_supernode (snode
, nullptr));
788 points
.safe_push (function_point::before_stmt (snode
, 0));
789 points
.safe_push (function_point::before_stmt (snode
, 1));
790 points
.safe_push (function_point::after_supernode (snode
));
792 /* Check all pairs. */
794 function_point
*point_a
;
795 FOR_EACH_VEC_ELT (points
, i
, point_a
)
798 function_point
*point_b
;
799 FOR_EACH_VEC_ELT (points
, j
, point_b
)
801 int cmp
= function_point::cmp_within_supernode (*point_a
, *point_b
);
805 ASSERT_TRUE (cmp
< 0);
807 ASSERT_TRUE (cmp
> 0);
812 /* Verify that program_point::operator== works as expected. */
815 test_program_point_equality ()
817 region_model_manager mgr
;
819 const supernode
*snode
= nullptr;
821 const call_string
&cs
= mgr
.get_empty_call_string ();
823 program_point a
= program_point::before_supernode (snode
, nullptr,
826 program_point b
= program_point::before_supernode (snode
, nullptr,
830 // TODO: verify with non-empty callstrings, with different edges
833 /* Run all of the selftests within this file. */
836 analyzer_program_point_cc_tests ()
838 test_function_point_equality ();
839 test_function_point_ordering ();
840 test_program_point_equality ();
843 } // namespace selftest
845 #endif /* CHECKING_P */
849 #endif /* #if ENABLE_ANALYZER */