1 /* Classes for representing locations within the program.
2 Copyright (C) 2019-2023 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"
26 #include "gimple-pretty-print.h"
27 #include "gcc-rich-location.h"
28 #include "ordered-hash-map.h"
33 #include "basic-block.h"
35 #include "gimple-iterator.h"
37 #include "analyzer/analyzer.h"
38 #include "analyzer/analyzer-logging.h"
39 #include "analyzer/call-string.h"
40 #include "analyzer/supergraph.h"
41 #include "analyzer/program-point.h"
45 #include "analyzer/store.h"
46 #include "analyzer/region-model.h"
47 #include "analyzer/sm.h"
48 #include "analyzer/program-state.h"
49 #include "diagnostic-event-id.h"
50 #include "analyzer/pending-diagnostic.h"
51 #include "analyzer/diagnostic-manager.h"
52 #include "shortest-paths.h"
53 #include "analyzer/exploded-graph.h"
54 #include "analyzer/analysis-plan.h"
60 /* Get a string for PK. */
63 point_kind_to_string (enum point_kind pk
)
71 case PK_BEFORE_SUPERNODE
:
72 return "PK_BEFORE_SUPERNODE";
74 return "PK_BEFORE_STMT";
75 case PK_AFTER_SUPERNODE
:
76 return "PK_AFTER_SUPERNODE";
84 /* class function_point. */
86 function_point::function_point (const supernode
*supernode
,
87 const superedge
*from_edge
,
90 : m_supernode (supernode
), m_from_edge (from_edge
),
91 m_stmt_idx (stmt_idx
), m_kind (kind
)
95 gcc_checking_assert (m_kind
== PK_BEFORE_SUPERNODE
);
96 gcc_checking_assert (from_edge
->get_kind () == SUPEREDGE_CFG_EDGE
);
99 gcc_checking_assert (m_kind
== PK_BEFORE_STMT
);
102 /* Print this function_point to PP. */
105 function_point::print (pretty_printer
*pp
, const format
&f
) const
113 pp_printf (pp
, "origin");
118 case PK_BEFORE_SUPERNODE
:
122 if (basic_block bb
= m_from_edge
->m_src
->m_bb
)
123 pp_printf (pp
, "before SN: %i (from SN: %i (bb: %i))",
124 m_supernode
->m_index
, m_from_edge
->m_src
->m_index
,
127 pp_printf (pp
, "before SN: %i (from SN: %i)",
128 m_supernode
->m_index
, m_from_edge
->m_src
->m_index
);
131 pp_printf (pp
, "before SN: %i (NULL from-edge)",
132 m_supernode
->m_index
);
134 for (gphi_iterator gpi
135 = const_cast<supernode
*>(get_supernode ())->start_phis ();
136 !gsi_end_p (gpi
); gsi_next (&gpi
))
138 const gphi
*phi
= gpi
.phi ();
139 pp_gimple_stmt_1 (pp
, phi
, 0, (dump_flags_t
)0);
145 pp_printf (pp
, "before (SN: %i stmt: %i): ", m_supernode
->m_index
,
148 pp_gimple_stmt_1 (pp
, get_stmt (), 0, (dump_flags_t
)0);
152 print_source_line (pp
);
156 case PK_AFTER_SUPERNODE
:
157 pp_printf (pp
, "after SN: %i", m_supernode
->m_index
);
164 /* Generate a hash value for this function_point. */
167 function_point::hash () const
169 inchash::hash hstate
;
171 hstate
.add_int (m_supernode
->m_index
);
172 hstate
.add_ptr (m_from_edge
);
173 hstate
.add_int (m_stmt_idx
);
174 hstate
.add_int (m_kind
);
175 return hstate
.end ();
178 /* Get the function at this point, if any. */
181 function_point::get_function () const
184 return m_supernode
->m_fun
;
189 /* Get the gimple stmt for this function_point, if any. */
192 function_point::get_stmt () const
194 if (m_kind
== PK_BEFORE_STMT
)
195 return m_supernode
->m_stmts
[m_stmt_idx
];
196 else if (m_kind
== PK_AFTER_SUPERNODE
)
197 return m_supernode
->get_last_stmt ();
202 /* Get a location for this function_point, if any. */
205 function_point::get_location () const
207 const gimple
*stmt
= get_stmt ();
209 return stmt
->location
;
210 if (m_kind
== PK_BEFORE_SUPERNODE
)
211 return m_supernode
->get_start_location ();
212 else if (m_kind
== PK_AFTER_SUPERNODE
)
213 return m_supernode
->get_end_location ();
215 return UNKNOWN_LOCATION
;
218 /* Return true if this function_point is a before_stmt for
219 the final stmt in its supernode. */
222 function_point::final_stmt_p () const
224 if (m_kind
!= PK_BEFORE_STMT
)
226 return m_stmt_idx
== get_supernode ()->m_stmts
.length () - 1;
229 /* Create a function_point representing the entrypoint of function FUN. */
232 function_point::from_function_entry (const supergraph
&sg
, function
*fun
)
234 return before_supernode (sg
.get_node_for_function_entry (fun
), NULL
);
237 /* Create a function_point representing entering supernode SUPERNODE,
238 having reached it via FROM_EDGE (which could be NULL). */
241 function_point::before_supernode (const supernode
*supernode
,
242 const superedge
*from_edge
)
244 if (from_edge
&& from_edge
->get_kind () != SUPEREDGE_CFG_EDGE
)
246 return function_point (supernode
, from_edge
, 0, PK_BEFORE_SUPERNODE
);
249 /* A subclass of diagnostic_context for use by
250 program_point::print_source_line. */
252 class debug_diagnostic_context
: public diagnostic_context
255 debug_diagnostic_context ()
257 diagnostic_initialize (this, 0);
258 show_line_numbers_p
= true;
261 ~debug_diagnostic_context ()
263 diagnostic_finish (this);
267 /* Print the source line (if any) for this function_point to PP. */
270 function_point::print_source_line (pretty_printer
*pp
) const
272 const gimple
*stmt
= get_stmt ();
275 // TODO: monospace font
276 debug_diagnostic_context tmp_dc
;
277 gcc_rich_location
richloc (stmt
->location
);
278 diagnostic_show_locus (&tmp_dc
, &richloc
, DK_ERROR
);
279 pp_string (pp
, pp_formatted_text (tmp_dc
.printer
));
282 /* class program_point. */
284 /* Print this program_point to PP. */
287 program_point::print (pretty_printer
*pp
, const format
&f
) const
289 pp_string (pp
, "callstring: ");
290 m_call_string
->print (pp
);
293 m_function_point
.print (pp
, f
);
296 /* Dump this point to stderr. */
299 program_point::dump () const
302 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
303 pp
.buffer
->stream
= stderr
;
304 print (&pp
, format (true));
308 /* Return a new json::object of the form
310 "snode_idx" : int (optional), the index of the supernode,
311 "from_edge_snode_idx" : int (only for kind=='PK_BEFORE_SUPERNODE'),
312 "stmt_idx": int (only for kind=='PK_BEFORE_STMT',
313 "call_string": object for the call_string}. */
316 program_point::to_json () const
318 json::object
*point_obj
= new json::object ();
320 point_obj
->set ("kind",
321 new json::string (point_kind_to_string (get_kind ())));
323 if (get_supernode ())
324 point_obj
->set ("snode_idx",
325 new json::integer_number (get_supernode ()->m_index
));
330 case PK_BEFORE_SUPERNODE
:
331 if (const superedge
*sedge
= get_from_edge ())
332 point_obj
->set ("from_edge_snode_idx",
333 new json::integer_number (sedge
->m_src
->m_index
));
336 point_obj
->set ("stmt_idx", new json::integer_number (get_stmt_idx ()));
340 point_obj
->set ("call_string", m_call_string
->to_json ());
345 /* Update the callstack to represent a call from caller to callee.
347 Generally used to push a custom call to a perticular program point
348 where we don't have a superedge representing the call. */
350 program_point::push_to_call_stack (const supernode
*caller
,
351 const supernode
*callee
)
353 m_call_string
= m_call_string
->push_call (callee
, caller
);
356 /* Pop the topmost call from the current callstack. */
358 program_point::pop_from_call_stack ()
360 m_call_string
= m_call_string
->get_parent ();
361 gcc_assert (m_call_string
);
364 /* Generate a hash value for this program_point. */
367 program_point::hash () const
369 inchash::hash hstate
;
370 hstate
.merge_hash (m_function_point
.hash ());
371 hstate
.add_ptr (m_call_string
);
372 return hstate
.end ();
375 /* Get the function * at DEPTH within the call stack. */
378 program_point::get_function_at_depth (unsigned depth
) const
380 gcc_assert (depth
<= m_call_string
->length ());
381 if (depth
== m_call_string
->length ())
382 return m_function_point
.get_function ();
384 return get_call_string ()[depth
].get_caller_function ();
387 /* Assert that this object is sane. */
390 program_point::validate () const
392 /* Skip this in a release build. */
397 m_call_string
->validate ();
398 /* The "callee" of the final entry in the callstring should be the
399 function of the m_function_point. */
400 if (m_call_string
->length () > 0)
402 ((*m_call_string
)[m_call_string
->length () - 1].get_callee_function ()
406 /* Check to see if SUCC is a valid edge to take (ensuring that we have
407 interprocedurally valid paths in the exploded graph, and enforcing
410 Update the call string if SUCC is a call or a return.
412 Return true if SUCC can be taken, or false otherwise.
414 This is the "point" half of exploded_node::on_edge. */
417 program_point::on_edge (exploded_graph
&eg
,
418 const superedge
*succ
)
420 logger
* const logger
= eg
.get_logger ();
422 switch (succ
->m_kind
)
424 case SUPEREDGE_CFG_EDGE
:
426 const cfg_superedge
*cfg_sedge
= as_a
<const cfg_superedge
*> (succ
);
428 /* Reject abnormal edges; we special-case setjmp/longjmp. */
429 if (cfg_sedge
->get_flags () & EDGE_ABNORMAL
)
436 const call_superedge
*call_sedge
= as_a
<const call_superedge
*> (succ
);
438 if (eg
.get_analysis_plan ().use_summary_p (call_sedge
->m_cedge
))
441 logger
->log ("rejecting call edge: using summary instead");
445 /* Add the callsite to the call string. */
446 m_call_string
= m_call_string
->push_call (eg
.get_supergraph (),
449 /* Impose a maximum recursion depth and don't analyze paths
450 that exceed it further.
451 This is something of a blunt workaround, but it only
452 applies to recursion (and mutual recursion), not to
453 general call stacks. */
454 if (m_call_string
->calc_recursion_depth ()
455 > param_analyzer_max_recursion_depth
)
458 logger
->log ("rejecting call edge: recursion limit exceeded");
459 // TODO: issue a sorry for this?
465 case SUPEREDGE_RETURN
:
467 /* Require that we return to the call site in the call string. */
468 if (m_call_string
->empty_p ())
471 logger
->log ("rejecting return edge: empty call string");
474 const call_string::element_t
&top_of_stack
475 = m_call_string
->get_top_of_stack ();
476 m_call_string
= m_call_string
->get_parent ();
477 call_string::element_t
current_call_string_element (succ
->m_dest
,
479 if (top_of_stack
!= current_call_string_element
)
482 logger
->log ("rejecting return edge: return to wrong callsite");
488 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
490 const callgraph_superedge
*cg_sedge
491 = as_a
<const callgraph_superedge
*> (succ
);
492 /* Consider turning this edge into a use of an
493 interprocedural summary. */
494 if (eg
.get_analysis_plan ().use_summary_p (cg_sedge
->m_cedge
))
497 logger
->log ("using function summary for %qE in %qE",
498 cg_sedge
->get_callee_decl (),
499 cg_sedge
->get_caller_decl ());
504 /* Otherwise, we ignore these edges */
506 logger
->log ("rejecting interprocedural edge");
515 /* Comparator for program points within the same supernode,
516 for implementing worklist::key_t comparison operators.
517 Return negative if POINT_A is before POINT_B
518 Return positive if POINT_A is after POINT_B
519 Return 0 if they are equal. */
522 function_point::cmp_within_supernode_1 (const function_point
&point_a
,
523 const function_point
&point_b
)
525 gcc_assert (point_a
.get_supernode () == point_b
.get_supernode ());
527 switch (point_a
.m_kind
)
531 case PK_BEFORE_SUPERNODE
:
532 switch (point_b
.m_kind
)
536 case PK_BEFORE_SUPERNODE
:
540 if (point_a
.m_from_edge
)
541 a_src_idx
= point_a
.m_from_edge
->m_src
->m_index
;
542 if (point_b
.m_from_edge
)
543 b_src_idx
= point_b
.m_from_edge
->m_src
->m_index
;
544 return a_src_idx
- b_src_idx
;
549 case PK_AFTER_SUPERNODE
:
554 switch (point_b
.m_kind
)
558 case PK_BEFORE_SUPERNODE
:
562 return point_a
.m_stmt_idx
- point_b
.m_stmt_idx
;
564 case PK_AFTER_SUPERNODE
:
568 case PK_AFTER_SUPERNODE
:
569 switch (point_b
.m_kind
)
573 case PK_BEFORE_SUPERNODE
:
577 case PK_AFTER_SUPERNODE
:
584 /* Comparator for program points within the same supernode,
585 for implementing worklist::key_t comparison operators.
586 Return negative if POINT_A is before POINT_B
587 Return positive if POINT_A is after POINT_B
588 Return 0 if they are equal. */
591 function_point::cmp_within_supernode (const function_point
&point_a
,
592 const function_point
&point_b
)
594 int result
= cmp_within_supernode_1 (point_a
, point_b
);
596 /* Check that the ordering is symmetric */
598 int reversed
= cmp_within_supernode_1 (point_b
, point_a
);
599 gcc_assert (reversed
== -result
);
605 /* Comparator for imposing an order on function_points. */
608 function_point::cmp (const function_point
&point_a
,
609 const function_point
&point_b
)
611 int idx_a
= point_a
.m_supernode
? point_a
.m_supernode
->m_index
: -1;
612 int idx_b
= point_b
.m_supernode
? point_b
.m_supernode
->m_index
: -1;
613 if (int cmp_idx
= idx_a
- idx_b
)
615 gcc_assert (point_a
.m_supernode
== point_b
.m_supernode
);
616 if (point_a
.m_supernode
)
617 return cmp_within_supernode (point_a
, point_b
);
622 /* Comparator for use by vec<function_point>::qsort. */
625 function_point::cmp_ptr (const void *p1
, const void *p2
)
627 const function_point
*fp1
= (const function_point
*)p1
;
628 const function_point
*fp2
= (const function_point
*)p2
;
629 return cmp (*fp1
, *fp2
);
632 /* For PK_BEFORE_STMT, go to next stmt (or to PK_AFTER_SUPERNODE). */
635 function_point::next_stmt ()
637 gcc_assert (m_kind
== PK_BEFORE_STMT
);
638 if (++m_stmt_idx
== m_supernode
->m_stmts
.length ())
640 m_kind
= PK_AFTER_SUPERNODE
;
645 /* For those function points for which there is a uniquely-defined
646 successor, return it. */
649 function_point::get_next () const
656 case PK_AFTER_SUPERNODE
:
657 gcc_unreachable (); /* Not uniquely defined. */
658 case PK_BEFORE_SUPERNODE
:
659 if (get_supernode ()->m_stmts
.length () > 0)
660 return before_stmt (get_supernode (), 0);
662 return after_supernode (get_supernode ());
665 unsigned next_idx
= get_stmt_idx () + 1;
666 if (next_idx
< get_supernode ()->m_stmts
.length ())
667 return before_stmt (get_supernode (), next_idx
);
669 return after_supernode (get_supernode ());
674 /* class program_point. */
677 program_point::origin (const region_model_manager
&mgr
)
679 return program_point (function_point (NULL
, NULL
,
681 mgr
.get_empty_call_string ());
685 program_point::from_function_entry (const region_model_manager
&mgr
,
686 const supergraph
&sg
,
689 return program_point (function_point::from_function_entry (sg
, fun
),
690 mgr
.get_empty_call_string ());
693 /* For those program points for which there is a uniquely-defined
694 successor, return it. */
697 program_point::get_next () const
699 switch (m_function_point
.get_kind ())
704 case PK_AFTER_SUPERNODE
:
705 gcc_unreachable (); /* Not uniquely defined. */
706 case PK_BEFORE_SUPERNODE
:
707 if (get_supernode ()->m_stmts
.length () > 0)
708 return before_stmt (get_supernode (), 0, get_call_string ());
710 return after_supernode (get_supernode (), get_call_string ());
713 unsigned next_idx
= get_stmt_idx () + 1;
714 if (next_idx
< get_supernode ()->m_stmts
.length ())
715 return before_stmt (get_supernode (), next_idx
, get_call_string ());
717 return after_supernode (get_supernode (), get_call_string ());
726 /* Verify that function_point::operator== works as expected. */
729 test_function_point_equality ()
731 const supernode
*snode
= NULL
;
733 function_point a
= function_point (snode
, NULL
, 0,
734 PK_BEFORE_SUPERNODE
);
735 function_point b
= function_point::before_supernode (snode
, NULL
);
739 /* Verify that function_point::cmp_within_supernode works as expected. */
742 test_function_point_ordering ()
744 const supernode
*snode
= NULL
;
746 /* Populate an array with various points within the same
748 auto_vec
<function_point
> points
;
749 points
.safe_push (function_point::before_supernode (snode
, NULL
));
750 points
.safe_push (function_point::before_stmt (snode
, 0));
751 points
.safe_push (function_point::before_stmt (snode
, 1));
752 points
.safe_push (function_point::after_supernode (snode
));
754 /* Check all pairs. */
756 function_point
*point_a
;
757 FOR_EACH_VEC_ELT (points
, i
, point_a
)
760 function_point
*point_b
;
761 FOR_EACH_VEC_ELT (points
, j
, point_b
)
763 int cmp
= function_point::cmp_within_supernode (*point_a
, *point_b
);
767 ASSERT_TRUE (cmp
< 0);
769 ASSERT_TRUE (cmp
> 0);
774 /* Verify that program_point::operator== works as expected. */
777 test_program_point_equality ()
779 region_model_manager mgr
;
781 const supernode
*snode
= NULL
;
783 const call_string
&cs
= mgr
.get_empty_call_string ();
785 program_point a
= program_point::before_supernode (snode
, NULL
,
788 program_point b
= program_point::before_supernode (snode
, NULL
,
792 // TODO: verify with non-empty callstrings, with different edges
795 /* Run all of the selftests within this file. */
798 analyzer_program_point_cc_tests ()
800 test_function_point_equality ();
801 test_function_point_ordering ();
802 test_program_point_equality ();
805 } // namespace selftest
807 #endif /* CHECKING_P */
811 #endif /* #if ENABLE_ANALYZER */