1 /* Classes for representing locations within the program.
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
23 #define INCLUDE_VECTOR
25 #include "coretypes.h"
27 #include "gimple-pretty-print.h"
28 #include "gcc-rich-location.h"
29 #include "ordered-hash-map.h"
34 #include "basic-block.h"
36 #include "gimple-iterator.h"
38 #include "analyzer/analyzer.h"
39 #include "analyzer/analyzer-logging.h"
40 #include "analyzer/call-string.h"
41 #include "analyzer/supergraph.h"
42 #include "analyzer/program-point.h"
46 #include "analyzer/store.h"
47 #include "analyzer/region-model.h"
48 #include "analyzer/sm.h"
49 #include "analyzer/program-state.h"
50 #include "diagnostic-event-id.h"
51 #include "analyzer/pending-diagnostic.h"
52 #include "analyzer/diagnostic-manager.h"
53 #include "shortest-paths.h"
54 #include "analyzer/exploded-graph.h"
55 #include "analyzer/analysis-plan.h"
56 #include "analyzer/inlining-iterator.h"
62 /* Get a string for PK. */
65 point_kind_to_string (enum point_kind pk
)
73 case PK_BEFORE_SUPERNODE
:
74 return "PK_BEFORE_SUPERNODE";
76 return "PK_BEFORE_STMT";
77 case PK_AFTER_SUPERNODE
:
78 return "PK_AFTER_SUPERNODE";
86 /* class function_point. */
88 function_point::function_point (const supernode
*supernode
,
89 const superedge
*from_edge
,
92 : m_supernode (supernode
), m_from_edge (from_edge
),
93 m_stmt_idx (stmt_idx
), m_kind (kind
)
97 gcc_checking_assert (m_kind
== PK_BEFORE_SUPERNODE
);
98 gcc_checking_assert (from_edge
->get_kind () == SUPEREDGE_CFG_EDGE
);
101 gcc_checking_assert (m_kind
== PK_BEFORE_STMT
);
104 /* Print this function_point to PP. */
107 function_point::print (pretty_printer
*pp
, const format
&f
) const
115 pp_printf (pp
, "origin");
120 case PK_BEFORE_SUPERNODE
:
124 if (basic_block bb
= m_from_edge
->m_src
->m_bb
)
125 pp_printf (pp
, "before SN: %i (from SN: %i (bb: %i))",
126 m_supernode
->m_index
, m_from_edge
->m_src
->m_index
,
129 pp_printf (pp
, "before SN: %i (from SN: %i)",
130 m_supernode
->m_index
, m_from_edge
->m_src
->m_index
);
133 pp_printf (pp
, "before SN: %i (NULL from-edge)",
134 m_supernode
->m_index
);
136 for (gphi_iterator gpi
137 = const_cast<supernode
*>(get_supernode ())->start_phis ();
138 !gsi_end_p (gpi
); gsi_next (&gpi
))
140 const gphi
*phi
= gpi
.phi ();
141 pp_gimple_stmt_1 (pp
, phi
, 0, (dump_flags_t
)0);
147 pp_printf (pp
, "before (SN: %i stmt: %i): ", m_supernode
->m_index
,
150 pp_gimple_stmt_1 (pp
, get_stmt (), 0, (dump_flags_t
)0);
154 print_source_line (pp
);
158 case PK_AFTER_SUPERNODE
:
159 pp_printf (pp
, "after SN: %i", m_supernode
->m_index
);
166 /* Generate a hash value for this function_point. */
169 function_point::hash () const
171 inchash::hash hstate
;
173 hstate
.add_int (m_supernode
->m_index
);
174 hstate
.add_ptr (m_from_edge
);
175 hstate
.add_int (m_stmt_idx
);
176 hstate
.add_int (m_kind
);
177 return hstate
.end ();
180 /* Get the function at this point, if any. */
183 function_point::get_function () const
186 return m_supernode
->m_fun
;
191 /* Get the gimple stmt for this function_point, if any. */
194 function_point::get_stmt () const
196 if (m_kind
== PK_BEFORE_STMT
)
197 return m_supernode
->m_stmts
[m_stmt_idx
];
198 else if (m_kind
== PK_AFTER_SUPERNODE
)
199 return m_supernode
->get_last_stmt ();
204 /* Get a location for this function_point, if any. */
207 function_point::get_location () const
209 const gimple
*stmt
= get_stmt ();
211 return stmt
->location
;
212 if (m_kind
== PK_BEFORE_SUPERNODE
)
213 return m_supernode
->get_start_location ();
214 else if (m_kind
== PK_AFTER_SUPERNODE
)
215 return m_supernode
->get_end_location ();
217 return UNKNOWN_LOCATION
;
220 /* Return true if this function_point is a before_stmt for
221 the final stmt in its supernode. */
224 function_point::final_stmt_p () const
226 if (m_kind
!= PK_BEFORE_STMT
)
228 return m_stmt_idx
== get_supernode ()->m_stmts
.length () - 1;
231 /* Create a function_point representing the entrypoint of function FUN. */
234 function_point::from_function_entry (const supergraph
&sg
, const function
&fun
)
236 return before_supernode (sg
.get_node_for_function_entry (fun
), NULL
);
239 /* Create a function_point representing entering supernode SUPERNODE,
240 having reached it via FROM_EDGE (which could be NULL). */
243 function_point::before_supernode (const supernode
*supernode
,
244 const superedge
*from_edge
)
246 if (from_edge
&& from_edge
->get_kind () != SUPEREDGE_CFG_EDGE
)
248 return function_point (supernode
, from_edge
, 0, PK_BEFORE_SUPERNODE
);
251 /* A subclass of diagnostic_context for use by
252 program_point::print_source_line. */
254 class debug_diagnostic_context
: public diagnostic_context
257 debug_diagnostic_context ()
259 diagnostic_initialize (this, 0);
260 m_source_printing
.show_line_numbers_p
= true;
261 m_source_printing
.enabled
= true;
263 ~debug_diagnostic_context ()
265 diagnostic_finish (this);
269 /* Print the source line (if any) for this function_point to PP. */
272 function_point::print_source_line (pretty_printer
*pp
) const
274 const gimple
*stmt
= get_stmt ();
277 // TODO: monospace font
278 debug_diagnostic_context tmp_dc
;
279 gcc_rich_location
richloc (stmt
->location
);
280 diagnostic_show_locus (&tmp_dc
, &richloc
, DK_ERROR
);
281 pp_string (pp
, pp_formatted_text (tmp_dc
.printer
));
284 /* class program_point. */
286 /* Print this program_point to PP. */
289 program_point::print (pretty_printer
*pp
, const format
&f
) const
291 pp_string (pp
, "callstring: ");
292 m_call_string
->print (pp
);
295 m_function_point
.print (pp
, f
);
298 /* Dump this point to stderr. */
301 program_point::dump () const
304 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
305 pp
.set_output_stream (stderr
);
306 print (&pp
, format (true));
310 /* Return a new json::object of the form
312 "snode_idx" : int (optional), the index of the supernode,
313 "from_edge_snode_idx" : int (only for kind=='PK_BEFORE_SUPERNODE'),
314 "stmt_idx": int (only for kind=='PK_BEFORE_STMT',
315 "call_string": object for the call_string}. */
318 program_point::to_json () const
320 json::object
*point_obj
= new json::object ();
322 point_obj
->set ("kind",
323 new json::string (point_kind_to_string (get_kind ())));
325 if (get_supernode ())
326 point_obj
->set ("snode_idx",
327 new json::integer_number (get_supernode ()->m_index
));
332 case PK_BEFORE_SUPERNODE
:
333 if (const superedge
*sedge
= get_from_edge ())
334 point_obj
->set ("from_edge_snode_idx",
335 new json::integer_number (sedge
->m_src
->m_index
));
338 point_obj
->set ("stmt_idx", new json::integer_number (get_stmt_idx ()));
342 point_obj
->set ("call_string", m_call_string
->to_json ());
347 /* Update the callstack to represent a call from caller to callee.
349 Generally used to push a custom call to a perticular program point
350 where we don't have a superedge representing the call. */
352 program_point::push_to_call_stack (const supernode
*caller
,
353 const supernode
*callee
)
355 m_call_string
= m_call_string
->push_call (callee
, caller
);
358 /* Pop the topmost call from the current callstack. */
360 program_point::pop_from_call_stack ()
362 m_call_string
= m_call_string
->get_parent ();
363 gcc_assert (m_call_string
);
366 /* Generate a hash value for this program_point. */
369 program_point::hash () const
371 inchash::hash hstate
;
372 hstate
.merge_hash (m_function_point
.hash ());
373 hstate
.add_ptr (m_call_string
);
374 return hstate
.end ();
377 /* Get the function * at DEPTH within the call stack. */
380 program_point::get_function_at_depth (unsigned depth
) const
382 gcc_assert (depth
<= m_call_string
->length ());
383 if (depth
== m_call_string
->length ())
384 return m_function_point
.get_function ();
386 return get_call_string ()[depth
].get_caller_function ();
389 /* Assert that this object is sane. */
392 program_point::validate () const
394 /* Skip this in a release build. */
399 m_call_string
->validate ();
400 /* The "callee" of the final entry in the callstring should be the
401 function of the m_function_point. */
402 if (m_call_string
->length () > 0)
404 ((*m_call_string
)[m_call_string
->length () - 1].get_callee_function ()
408 /* Check to see if SUCC is a valid edge to take (ensuring that we have
409 interprocedurally valid paths in the exploded graph, and enforcing
412 Update the call string if SUCC is a call or a return.
414 Return true if SUCC can be taken, or false otherwise.
416 This is the "point" half of exploded_node::on_edge. */
419 program_point::on_edge (exploded_graph
&eg
,
420 const superedge
*succ
)
422 logger
* const logger
= eg
.get_logger ();
424 switch (succ
->m_kind
)
426 case SUPEREDGE_CFG_EDGE
:
428 const cfg_superedge
*cfg_sedge
= as_a
<const cfg_superedge
*> (succ
);
430 if (cfg_sedge
->get_flags () & EDGE_ABNORMAL
)
432 const supernode
*src_snode
= cfg_sedge
->m_src
;
433 if (gimple
*last_stmt
= src_snode
->get_last_stmt ())
434 if (last_stmt
->code
== GIMPLE_GOTO
)
436 /* For the program_point aspect here, consider all
437 out-edges from goto stmts to be valid; we'll
438 consider state separately. */
442 /* Reject other kinds of abnormal edges;
443 we special-case setjmp/longjmp. */
451 const call_superedge
*call_sedge
= as_a
<const call_superedge
*> (succ
);
453 if (eg
.get_analysis_plan ().use_summary_p (call_sedge
->m_cedge
))
456 logger
->log ("rejecting call edge: using summary instead");
460 /* Add the callsite to the call string. */
461 m_call_string
= m_call_string
->push_call (eg
.get_supergraph (),
464 /* Impose a maximum recursion depth and don't analyze paths
465 that exceed it further.
466 This is something of a blunt workaround, but it only
467 applies to recursion (and mutual recursion), not to
468 general call stacks. */
469 if (m_call_string
->calc_recursion_depth ()
470 > param_analyzer_max_recursion_depth
)
473 logger
->log ("rejecting call edge: recursion limit exceeded");
474 // TODO: issue a sorry for this?
480 case SUPEREDGE_RETURN
:
482 /* Require that we return to the call site in the call string. */
483 if (m_call_string
->empty_p ())
486 logger
->log ("rejecting return edge: empty call string");
489 const call_string::element_t
&top_of_stack
490 = m_call_string
->get_top_of_stack ();
491 m_call_string
= m_call_string
->get_parent ();
492 call_string::element_t
current_call_string_element (succ
->m_dest
,
494 if (top_of_stack
!= current_call_string_element
)
497 logger
->log ("rejecting return edge: return to wrong callsite");
503 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
505 const callgraph_superedge
*cg_sedge
506 = as_a
<const callgraph_superedge
*> (succ
);
507 /* Consider turning this edge into a use of an
508 interprocedural summary. */
509 if (eg
.get_analysis_plan ().use_summary_p (cg_sedge
->m_cedge
))
512 logger
->log ("using function summary for %qE in %qE",
513 cg_sedge
->get_callee_decl (),
514 cg_sedge
->get_caller_decl ());
519 /* Otherwise, we ignore these edges */
521 logger
->log ("rejecting interprocedural edge");
530 /* Comparator for program points within the same supernode,
531 for implementing worklist::key_t comparison operators.
532 Return negative if POINT_A is before POINT_B
533 Return positive if POINT_A is after POINT_B
534 Return 0 if they are equal. */
537 function_point::cmp_within_supernode_1 (const function_point
&point_a
,
538 const function_point
&point_b
)
540 gcc_assert (point_a
.get_supernode () == point_b
.get_supernode ());
542 switch (point_a
.m_kind
)
546 case PK_BEFORE_SUPERNODE
:
547 switch (point_b
.m_kind
)
551 case PK_BEFORE_SUPERNODE
:
555 if (point_a
.m_from_edge
)
556 a_src_idx
= point_a
.m_from_edge
->m_src
->m_index
;
557 if (point_b
.m_from_edge
)
558 b_src_idx
= point_b
.m_from_edge
->m_src
->m_index
;
559 return a_src_idx
- b_src_idx
;
564 case PK_AFTER_SUPERNODE
:
569 switch (point_b
.m_kind
)
573 case PK_BEFORE_SUPERNODE
:
577 return point_a
.m_stmt_idx
- point_b
.m_stmt_idx
;
579 case PK_AFTER_SUPERNODE
:
583 case PK_AFTER_SUPERNODE
:
584 switch (point_b
.m_kind
)
588 case PK_BEFORE_SUPERNODE
:
592 case PK_AFTER_SUPERNODE
:
599 /* Comparator for program points within the same supernode,
600 for implementing worklist::key_t comparison operators.
601 Return negative if POINT_A is before POINT_B
602 Return positive if POINT_A is after POINT_B
603 Return 0 if they are equal. */
606 function_point::cmp_within_supernode (const function_point
&point_a
,
607 const function_point
&point_b
)
609 int result
= cmp_within_supernode_1 (point_a
, point_b
);
611 /* Check that the ordering is symmetric */
613 int reversed
= cmp_within_supernode_1 (point_b
, point_a
);
614 gcc_assert (reversed
== -result
);
620 /* Comparator for imposing an order on function_points. */
623 function_point::cmp (const function_point
&point_a
,
624 const function_point
&point_b
)
626 int idx_a
= point_a
.m_supernode
? point_a
.m_supernode
->m_index
: -1;
627 int idx_b
= point_b
.m_supernode
? point_b
.m_supernode
->m_index
: -1;
628 if (int cmp_idx
= idx_a
- idx_b
)
630 gcc_assert (point_a
.m_supernode
== point_b
.m_supernode
);
631 if (point_a
.m_supernode
)
632 return cmp_within_supernode (point_a
, point_b
);
637 /* Comparator for use by vec<function_point>::qsort. */
640 function_point::cmp_ptr (const void *p1
, const void *p2
)
642 const function_point
*fp1
= (const function_point
*)p1
;
643 const function_point
*fp2
= (const function_point
*)p2
;
644 return cmp (*fp1
, *fp2
);
647 /* For PK_BEFORE_STMT, go to next stmt (or to PK_AFTER_SUPERNODE). */
650 function_point::next_stmt ()
652 gcc_assert (m_kind
== PK_BEFORE_STMT
);
653 if (++m_stmt_idx
== m_supernode
->m_stmts
.length ())
655 m_kind
= PK_AFTER_SUPERNODE
;
660 /* For those function points for which there is a uniquely-defined
661 successor, return it. */
664 function_point::get_next () const
671 case PK_AFTER_SUPERNODE
:
672 gcc_unreachable (); /* Not uniquely defined. */
673 case PK_BEFORE_SUPERNODE
:
674 if (get_supernode ()->m_stmts
.length () > 0)
675 return before_stmt (get_supernode (), 0);
677 return after_supernode (get_supernode ());
680 unsigned next_idx
= get_stmt_idx () + 1;
681 if (next_idx
< get_supernode ()->m_stmts
.length ())
682 return before_stmt (get_supernode (), next_idx
);
684 return after_supernode (get_supernode ());
689 /* class program_point. */
692 program_point::origin (const region_model_manager
&mgr
)
694 return program_point (function_point (NULL
, NULL
,
696 mgr
.get_empty_call_string ());
700 program_point::from_function_entry (const region_model_manager
&mgr
,
701 const supergraph
&sg
,
704 return program_point (function_point::from_function_entry (sg
, fun
),
705 mgr
.get_empty_call_string ());
708 /* For those program points for which there is a uniquely-defined
709 successor, return it. */
712 program_point::get_next () const
714 switch (m_function_point
.get_kind ())
719 case PK_AFTER_SUPERNODE
:
720 gcc_unreachable (); /* Not uniquely defined. */
721 case PK_BEFORE_SUPERNODE
:
722 if (get_supernode ()->m_stmts
.length () > 0)
723 return before_stmt (get_supernode (), 0, get_call_string ());
725 return after_supernode (get_supernode (), get_call_string ());
728 unsigned next_idx
= get_stmt_idx () + 1;
729 if (next_idx
< get_supernode ()->m_stmts
.length ())
730 return before_stmt (get_supernode (), next_idx
, get_call_string ());
732 return after_supernode (get_supernode (), get_call_string ());
737 /* Return true iff POINT_A and POINT_B share the same function and
738 call_string, both directly, and when attempting to undo inlining
742 program_point::effectively_intraprocedural_p (const program_point
&point_a
,
743 const program_point
&point_b
)
745 /* First, compare without considering inlining info. */
746 if (point_a
.get_function ()
747 != point_b
.get_function ())
749 if (&point_a
.get_call_string ()
750 != &point_b
.get_call_string ())
753 /* Consider inlining info; they must have originally come from
754 the same function and have been inlined in the same way. */
755 location_t loc_a
= point_a
.get_location ();
756 location_t loc_b
= point_b
.get_location ();
757 inlining_iterator
iter_a (loc_a
);
758 inlining_iterator
iter_b (loc_b
);
759 while (!(iter_a
.done_p () || iter_b
.done_p ()))
761 if (iter_a
.done_p () || iter_b
.done_p ())
764 if (iter_a
.get_fndecl () != iter_b
.get_fndecl ())
766 if (iter_a
.get_callsite () != iter_b
.get_callsite ())
768 if (iter_a
.get_block () != iter_b
.get_block ())
782 /* Verify that function_point::operator== works as expected. */
785 test_function_point_equality ()
787 const supernode
*snode
= NULL
;
789 function_point a
= function_point (snode
, NULL
, 0,
790 PK_BEFORE_SUPERNODE
);
791 function_point b
= function_point::before_supernode (snode
, NULL
);
795 /* Verify that function_point::cmp_within_supernode works as expected. */
798 test_function_point_ordering ()
800 const supernode
*snode
= NULL
;
802 /* Populate an array with various points within the same
804 auto_vec
<function_point
> points
;
805 points
.safe_push (function_point::before_supernode (snode
, NULL
));
806 points
.safe_push (function_point::before_stmt (snode
, 0));
807 points
.safe_push (function_point::before_stmt (snode
, 1));
808 points
.safe_push (function_point::after_supernode (snode
));
810 /* Check all pairs. */
812 function_point
*point_a
;
813 FOR_EACH_VEC_ELT (points
, i
, point_a
)
816 function_point
*point_b
;
817 FOR_EACH_VEC_ELT (points
, j
, point_b
)
819 int cmp
= function_point::cmp_within_supernode (*point_a
, *point_b
);
823 ASSERT_TRUE (cmp
< 0);
825 ASSERT_TRUE (cmp
> 0);
830 /* Verify that program_point::operator== works as expected. */
833 test_program_point_equality ()
835 region_model_manager mgr
;
837 const supernode
*snode
= NULL
;
839 const call_string
&cs
= mgr
.get_empty_call_string ();
841 program_point a
= program_point::before_supernode (snode
, NULL
,
844 program_point b
= program_point::before_supernode (snode
, NULL
,
848 // TODO: verify with non-empty callstrings, with different edges
851 /* Run all of the selftests within this file. */
854 analyzer_program_point_cc_tests ()
856 test_function_point_equality ();
857 test_function_point_ordering ();
858 test_program_point_equality ();
861 } // namespace selftest
863 #endif /* CHECKING_P */
867 #endif /* #if ENABLE_ANALYZER */