1 /* Classes for representing locations within the program.
2 Copyright (C) 2019-2022 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/>. */
23 #include "coretypes.h"
25 #include "gimple-pretty-print.h"
26 #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"
46 #include "analyzer/store.h"
47 #include "analyzer/region-model.h"
48 #include "analyzer/sm.h"
49 #include "analyzer/program-state.h"
50 #include "alloc-pool.h"
51 #include "fibonacci_heap.h"
52 #include "diagnostic-event-id.h"
53 #include "analyzer/pending-diagnostic.h"
54 #include "analyzer/diagnostic-manager.h"
55 #include "shortest-paths.h"
56 #include "analyzer/exploded-graph.h"
57 #include "analyzer/analysis-plan.h"
63 /* Get a string for PK. */
66 point_kind_to_string (enum point_kind pk
)
74 case PK_BEFORE_SUPERNODE
:
75 return "PK_BEFORE_SUPERNODE";
77 return "PK_BEFORE_STMT";
78 case PK_AFTER_SUPERNODE
:
79 return "PK_AFTER_SUPERNODE";
87 /* class function_point. */
89 function_point::function_point (const supernode
*supernode
,
90 const superedge
*from_edge
,
93 : m_supernode (supernode
), m_from_edge (from_edge
),
94 m_stmt_idx (stmt_idx
), m_kind (kind
)
98 gcc_checking_assert (m_kind
== PK_BEFORE_SUPERNODE
);
99 gcc_checking_assert (from_edge
->get_kind () == SUPEREDGE_CFG_EDGE
);
102 gcc_checking_assert (m_kind
== PK_BEFORE_STMT
);
105 /* Print this function_point to PP. */
108 function_point::print (pretty_printer
*pp
, const format
&f
) const
116 pp_printf (pp
, "origin");
121 case PK_BEFORE_SUPERNODE
:
125 if (basic_block bb
= m_from_edge
->m_src
->m_bb
)
126 pp_printf (pp
, "before SN: %i (from SN: %i (bb: %i))",
127 m_supernode
->m_index
, m_from_edge
->m_src
->m_index
,
130 pp_printf (pp
, "before SN: %i (from SN: %i)",
131 m_supernode
->m_index
, m_from_edge
->m_src
->m_index
);
134 pp_printf (pp
, "before SN: %i (NULL from-edge)",
135 m_supernode
->m_index
);
137 for (gphi_iterator gpi
138 = const_cast<supernode
*>(get_supernode ())->start_phis ();
139 !gsi_end_p (gpi
); gsi_next (&gpi
))
141 const gphi
*phi
= gpi
.phi ();
142 pp_gimple_stmt_1 (pp
, phi
, 0, (dump_flags_t
)0);
148 pp_printf (pp
, "before (SN: %i stmt: %i): ", m_supernode
->m_index
,
151 pp_gimple_stmt_1 (pp
, get_stmt (), 0, (dump_flags_t
)0);
155 print_source_line (pp
);
159 case PK_AFTER_SUPERNODE
:
160 pp_printf (pp
, "after SN: %i", m_supernode
->m_index
);
167 /* Generate a hash value for this function_point. */
170 function_point::hash () const
172 inchash::hash hstate
;
174 hstate
.add_int (m_supernode
->m_index
);
175 hstate
.add_ptr (m_from_edge
);
176 hstate
.add_int (m_stmt_idx
);
177 hstate
.add_int (m_kind
);
178 return hstate
.end ();
181 /* Get the function at this point, if any. */
184 function_point::get_function () const
187 return m_supernode
->m_fun
;
192 /* Get the gimple stmt for this function_point, if any. */
195 function_point::get_stmt () const
197 if (m_kind
== PK_BEFORE_STMT
)
198 return m_supernode
->m_stmts
[m_stmt_idx
];
199 else if (m_kind
== PK_AFTER_SUPERNODE
)
200 return m_supernode
->get_last_stmt ();
205 /* Get a location for this function_point, if any. */
208 function_point::get_location () const
210 const gimple
*stmt
= get_stmt ();
212 return stmt
->location
;
213 if (m_kind
== PK_BEFORE_SUPERNODE
)
214 return m_supernode
->get_start_location ();
215 else if (m_kind
== PK_AFTER_SUPERNODE
)
216 return m_supernode
->get_end_location ();
218 return UNKNOWN_LOCATION
;
221 /* Return true if this function_point is a before_stmt for
222 the final stmt in its supernode. */
225 function_point::final_stmt_p () const
227 if (m_kind
!= PK_BEFORE_STMT
)
229 return m_stmt_idx
== get_supernode ()->m_stmts
.length () - 1;
232 /* Create a function_point representing the entrypoint of function FUN. */
235 function_point::from_function_entry (const supergraph
&sg
, function
*fun
)
237 return before_supernode (sg
.get_node_for_function_entry (fun
), NULL
);
240 /* Create a function_point representing entering supernode SUPERNODE,
241 having reached it via FROM_EDGE (which could be NULL). */
244 function_point::before_supernode (const supernode
*supernode
,
245 const superedge
*from_edge
)
247 if (from_edge
&& from_edge
->get_kind () != SUPEREDGE_CFG_EDGE
)
249 return function_point (supernode
, from_edge
, 0, PK_BEFORE_SUPERNODE
);
252 /* A subclass of diagnostic_context for use by
253 program_point::print_source_line. */
255 class debug_diagnostic_context
: public diagnostic_context
258 debug_diagnostic_context ()
260 diagnostic_initialize (this, 0);
261 show_line_numbers_p
= true;
264 ~debug_diagnostic_context ()
266 diagnostic_finish (this);
270 /* Print the source line (if any) for this function_point to PP. */
273 function_point::print_source_line (pretty_printer
*pp
) const
275 const gimple
*stmt
= get_stmt ();
278 // TODO: monospace font
279 debug_diagnostic_context tmp_dc
;
280 gcc_rich_location
richloc (stmt
->location
);
281 diagnostic_show_locus (&tmp_dc
, &richloc
, DK_ERROR
);
282 pp_string (pp
, pp_formatted_text (tmp_dc
.printer
));
285 /* class program_point. */
287 /* Print this program_point to PP. */
290 program_point::print (pretty_printer
*pp
, const format
&f
) const
292 pp_string (pp
, "callstring: ");
293 m_call_string
->print (pp
);
296 m_function_point
.print (pp
, f
);
299 /* Dump this point to stderr. */
302 program_point::dump () const
305 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
306 pp
.buffer
->stream
= stderr
;
307 print (&pp
, format (true));
311 /* Return a new json::object of the form
313 "snode_idx" : int (optional), the index of the supernode,
314 "from_edge_snode_idx" : int (only for kind=='PK_BEFORE_SUPERNODE'),
315 "stmt_idx": int (only for kind=='PK_BEFORE_STMT',
316 "call_string": object for the call_string}. */
319 program_point::to_json () const
321 json::object
*point_obj
= new json::object ();
323 point_obj
->set ("kind",
324 new json::string (point_kind_to_string (get_kind ())));
326 if (get_supernode ())
327 point_obj
->set ("snode_idx",
328 new json::integer_number (get_supernode ()->m_index
));
333 case PK_BEFORE_SUPERNODE
:
334 if (const superedge
*sedge
= get_from_edge ())
335 point_obj
->set ("from_edge_snode_idx",
336 new json::integer_number (sedge
->m_src
->m_index
));
339 point_obj
->set ("stmt_idx", new json::integer_number (get_stmt_idx ()));
343 point_obj
->set ("call_string", m_call_string
->to_json ());
348 /* Update the callstack to represent a call from caller to callee.
350 Generally used to push a custom call to a perticular program point
351 where we don't have a superedge representing the call. */
353 program_point::push_to_call_stack (const supernode
*caller
,
354 const supernode
*callee
)
356 m_call_string
= m_call_string
->push_call (callee
, caller
);
359 /* Pop the topmost call from the current callstack. */
361 program_point::pop_from_call_stack ()
363 m_call_string
= m_call_string
->get_parent ();
364 gcc_assert (m_call_string
);
367 /* Generate a hash value for this program_point. */
370 program_point::hash () const
372 inchash::hash hstate
;
373 hstate
.merge_hash (m_function_point
.hash ());
374 hstate
.add_ptr (m_call_string
);
375 return hstate
.end ();
378 /* Get the function * at DEPTH within the call stack. */
381 program_point::get_function_at_depth (unsigned depth
) const
383 gcc_assert (depth
<= m_call_string
->length ());
384 if (depth
== m_call_string
->length ())
385 return m_function_point
.get_function ();
387 return get_call_string ()[depth
].get_caller_function ();
390 /* Assert that this object is sane. */
393 program_point::validate () const
395 /* Skip this in a release build. */
400 m_call_string
->validate ();
401 /* The "callee" of the final entry in the callstring should be the
402 function of the m_function_point. */
403 if (m_call_string
->length () > 0)
405 ((*m_call_string
)[m_call_string
->length () - 1].get_callee_function ()
409 /* Check to see if SUCC is a valid edge to take (ensuring that we have
410 interprocedurally valid paths in the exploded graph, and enforcing
413 Update the call string if SUCC is a call or a return.
415 Return true if SUCC can be taken, or false otherwise.
417 This is the "point" half of exploded_node::on_edge. */
420 program_point::on_edge (exploded_graph
&eg
,
421 const superedge
*succ
)
423 logger
* const logger
= eg
.get_logger ();
425 switch (succ
->m_kind
)
427 case SUPEREDGE_CFG_EDGE
:
429 const cfg_superedge
*cfg_sedge
= as_a
<const cfg_superedge
*> (succ
);
431 /* Reject abnormal edges; we special-case setjmp/longjmp. */
432 if (cfg_sedge
->get_flags () & EDGE_ABNORMAL
)
439 const call_superedge
*call_sedge
= as_a
<const call_superedge
*> (succ
);
441 if (eg
.get_analysis_plan ().use_summary_p (call_sedge
->m_cedge
))
444 logger
->log ("rejecting call edge: using summary instead");
448 /* Add the callsite to the call string. */
449 m_call_string
= m_call_string
->push_call (eg
.get_supergraph (),
452 /* Impose a maximum recursion depth and don't analyze paths
453 that exceed it further.
454 This is something of a blunt workaround, but it only
455 applies to recursion (and mutual recursion), not to
456 general call stacks. */
457 if (m_call_string
->calc_recursion_depth ()
458 > param_analyzer_max_recursion_depth
)
461 logger
->log ("rejecting call edge: recursion limit exceeded");
462 // TODO: issue a sorry for this?
468 case SUPEREDGE_RETURN
:
470 /* Require that we return to the call site in the call string. */
471 if (m_call_string
->empty_p ())
474 logger
->log ("rejecting return edge: empty call string");
477 const call_string::element_t
&top_of_stack
478 = m_call_string
->get_top_of_stack ();
479 m_call_string
= m_call_string
->get_parent ();
480 call_string::element_t
current_call_string_element (succ
->m_dest
,
482 if (top_of_stack
!= current_call_string_element
)
485 logger
->log ("rejecting return edge: return to wrong callsite");
491 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
493 const callgraph_superedge
*cg_sedge
494 = as_a
<const callgraph_superedge
*> (succ
);
495 /* Consider turning this edge into a use of an
496 interprocedural summary. */
497 if (eg
.get_analysis_plan ().use_summary_p (cg_sedge
->m_cedge
))
500 logger
->log ("using function summary for %qE in %qE",
501 cg_sedge
->get_callee_decl (),
502 cg_sedge
->get_caller_decl ());
507 /* Otherwise, we ignore these edges */
509 logger
->log ("rejecting interprocedural edge");
518 /* Comparator for program points within the same supernode,
519 for implementing worklist::key_t comparison operators.
520 Return negative if POINT_A is before POINT_B
521 Return positive if POINT_A is after POINT_B
522 Return 0 if they are equal. */
525 function_point::cmp_within_supernode_1 (const function_point
&point_a
,
526 const function_point
&point_b
)
528 gcc_assert (point_a
.get_supernode () == point_b
.get_supernode ());
530 switch (point_a
.m_kind
)
534 case PK_BEFORE_SUPERNODE
:
535 switch (point_b
.m_kind
)
539 case PK_BEFORE_SUPERNODE
:
543 if (point_a
.m_from_edge
)
544 a_src_idx
= point_a
.m_from_edge
->m_src
->m_index
;
545 if (point_b
.m_from_edge
)
546 b_src_idx
= point_b
.m_from_edge
->m_src
->m_index
;
547 return a_src_idx
- b_src_idx
;
552 case PK_AFTER_SUPERNODE
:
557 switch (point_b
.m_kind
)
561 case PK_BEFORE_SUPERNODE
:
565 return point_a
.m_stmt_idx
- point_b
.m_stmt_idx
;
567 case PK_AFTER_SUPERNODE
:
571 case PK_AFTER_SUPERNODE
:
572 switch (point_b
.m_kind
)
576 case PK_BEFORE_SUPERNODE
:
580 case PK_AFTER_SUPERNODE
:
587 /* Comparator for program points within the same supernode,
588 for implementing worklist::key_t comparison operators.
589 Return negative if POINT_A is before POINT_B
590 Return positive if POINT_A is after POINT_B
591 Return 0 if they are equal. */
594 function_point::cmp_within_supernode (const function_point
&point_a
,
595 const function_point
&point_b
)
597 int result
= cmp_within_supernode_1 (point_a
, point_b
);
599 /* Check that the ordering is symmetric */
601 int reversed
= cmp_within_supernode_1 (point_b
, point_a
);
602 gcc_assert (reversed
== -result
);
608 /* Comparator for imposing an order on function_points. */
611 function_point::cmp (const function_point
&point_a
,
612 const function_point
&point_b
)
614 int idx_a
= point_a
.m_supernode
? point_a
.m_supernode
->m_index
: -1;
615 int idx_b
= point_b
.m_supernode
? point_b
.m_supernode
->m_index
: -1;
616 if (int cmp_idx
= idx_a
- idx_b
)
618 gcc_assert (point_a
.m_supernode
== point_b
.m_supernode
);
619 if (point_a
.m_supernode
)
620 return cmp_within_supernode (point_a
, point_b
);
625 /* Comparator for use by vec<function_point>::qsort. */
628 function_point::cmp_ptr (const void *p1
, const void *p2
)
630 const function_point
*fp1
= (const function_point
*)p1
;
631 const function_point
*fp2
= (const function_point
*)p2
;
632 return cmp (*fp1
, *fp2
);
635 /* For PK_BEFORE_STMT, go to next stmt (or to PK_AFTER_SUPERNODE). */
638 function_point::next_stmt ()
640 gcc_assert (m_kind
== PK_BEFORE_STMT
);
641 if (++m_stmt_idx
== m_supernode
->m_stmts
.length ())
643 m_kind
= PK_AFTER_SUPERNODE
;
648 /* For those function points for which there is a uniquely-defined
649 successor, return it. */
652 function_point::get_next () const
659 case PK_AFTER_SUPERNODE
:
660 gcc_unreachable (); /* Not uniquely defined. */
661 case PK_BEFORE_SUPERNODE
:
662 if (get_supernode ()->m_stmts
.length () > 0)
663 return before_stmt (get_supernode (), 0);
665 return after_supernode (get_supernode ());
668 unsigned next_idx
= get_stmt_idx () + 1;
669 if (next_idx
< get_supernode ()->m_stmts
.length ())
670 return before_stmt (get_supernode (), next_idx
);
672 return after_supernode (get_supernode ());
677 /* class program_point. */
680 program_point::origin (const region_model_manager
&mgr
)
682 return program_point (function_point (NULL
, NULL
,
684 mgr
.get_empty_call_string ());
688 program_point::from_function_entry (const region_model_manager
&mgr
,
689 const supergraph
&sg
,
692 return program_point (function_point::from_function_entry (sg
, fun
),
693 mgr
.get_empty_call_string ());
696 /* For those program points for which there is a uniquely-defined
697 successor, return it. */
700 program_point::get_next () const
702 switch (m_function_point
.get_kind ())
707 case PK_AFTER_SUPERNODE
:
708 gcc_unreachable (); /* Not uniquely defined. */
709 case PK_BEFORE_SUPERNODE
:
710 if (get_supernode ()->m_stmts
.length () > 0)
711 return before_stmt (get_supernode (), 0, get_call_string ());
713 return after_supernode (get_supernode (), get_call_string ());
716 unsigned next_idx
= get_stmt_idx () + 1;
717 if (next_idx
< get_supernode ()->m_stmts
.length ())
718 return before_stmt (get_supernode (), next_idx
, get_call_string ());
720 return after_supernode (get_supernode (), get_call_string ());
729 /* Verify that function_point::operator== works as expected. */
732 test_function_point_equality ()
734 const supernode
*snode
= NULL
;
736 function_point a
= function_point (snode
, NULL
, 0,
737 PK_BEFORE_SUPERNODE
);
738 function_point b
= function_point::before_supernode (snode
, NULL
);
742 /* Verify that function_point::cmp_within_supernode works as expected. */
745 test_function_point_ordering ()
747 const supernode
*snode
= NULL
;
749 /* Populate an array with various points within the same
751 auto_vec
<function_point
> points
;
752 points
.safe_push (function_point::before_supernode (snode
, NULL
));
753 points
.safe_push (function_point::before_stmt (snode
, 0));
754 points
.safe_push (function_point::before_stmt (snode
, 1));
755 points
.safe_push (function_point::after_supernode (snode
));
757 /* Check all pairs. */
759 function_point
*point_a
;
760 FOR_EACH_VEC_ELT (points
, i
, point_a
)
763 function_point
*point_b
;
764 FOR_EACH_VEC_ELT (points
, j
, point_b
)
766 int cmp
= function_point::cmp_within_supernode (*point_a
, *point_b
);
770 ASSERT_TRUE (cmp
< 0);
772 ASSERT_TRUE (cmp
> 0);
777 /* Verify that program_point::operator== works as expected. */
780 test_program_point_equality ()
782 region_model_manager mgr
;
784 const supernode
*snode
= NULL
;
786 const call_string
&cs
= mgr
.get_empty_call_string ();
788 program_point a
= program_point::before_supernode (snode
, NULL
,
791 program_point b
= program_point::before_supernode (snode
, NULL
,
795 // TODO: verify with non-empty callstrings, with different edges
798 /* Run all of the selftests within this file. */
801 analyzer_program_point_cc_tests ()
803 test_function_point_equality ();
804 test_function_point_ordering ();
805 test_program_point_equality ();
808 } // namespace selftest
810 #endif /* CHECKING_P */
814 #endif /* #if ENABLE_ANALYZER */