1 /* Classes for representing locations within the program.
2 Copyright (C) 2019-2021 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 "analyzer/call-string.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/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");
119 case PK_BEFORE_SUPERNODE
:
122 pp_printf (pp
, "before SN: %i (from SN: %i)",
123 m_supernode
->m_index
, m_from_edge
->m_src
->m_index
);
125 pp_printf (pp
, "before SN: %i (NULL from-edge)",
126 m_supernode
->m_index
);
128 for (gphi_iterator gpi
129 = const_cast<supernode
*>(get_supernode ())->start_phis ();
130 !gsi_end_p (gpi
); gsi_next (&gpi
))
132 const gphi
*phi
= gpi
.phi ();
133 pp_gimple_stmt_1 (pp
, phi
, 0, (dump_flags_t
)0);
139 pp_printf (pp
, "before (SN: %i stmt: %i): ", m_supernode
->m_index
,
142 pp_gimple_stmt_1 (pp
, get_stmt (), 0, (dump_flags_t
)0);
146 print_source_line (pp
);
150 case PK_AFTER_SUPERNODE
:
151 pp_printf (pp
, "after SN: %i", m_supernode
->m_index
);
156 /* Generate a hash value for this function_point. */
159 function_point::hash () const
161 inchash::hash hstate
;
163 hstate
.add_int (m_supernode
->m_index
);
164 hstate
.add_ptr (m_from_edge
);
165 hstate
.add_int (m_stmt_idx
);
166 hstate
.add_int (m_kind
);
167 return hstate
.end ();
170 /* Get the function at this point, if any. */
173 function_point::get_function () const
176 return m_supernode
->m_fun
;
181 /* Get the gimple stmt for this function_point, if any. */
184 function_point::get_stmt () const
186 if (m_kind
== PK_BEFORE_STMT
)
187 return m_supernode
->m_stmts
[m_stmt_idx
];
188 else if (m_kind
== PK_AFTER_SUPERNODE
)
189 return m_supernode
->get_last_stmt ();
194 /* Get a location for this function_point, if any. */
197 function_point::get_location () const
199 const gimple
*stmt
= get_stmt ();
201 return stmt
->location
;
202 if (m_kind
== PK_BEFORE_SUPERNODE
)
203 return m_supernode
->get_start_location ();
204 else if (m_kind
== PK_AFTER_SUPERNODE
)
205 return m_supernode
->get_end_location ();
207 return UNKNOWN_LOCATION
;
210 /* Create a function_point representing the entrypoint of function FUN. */
213 function_point::from_function_entry (const supergraph
&sg
, function
*fun
)
215 return before_supernode (sg
.get_node_for_function_entry (fun
), NULL
);
218 /* Create a function_point representing entering supernode SUPERNODE,
219 having reached it via FROM_EDGE (which could be NULL). */
222 function_point::before_supernode (const supernode
*supernode
,
223 const superedge
*from_edge
)
225 if (from_edge
&& from_edge
->get_kind () != SUPEREDGE_CFG_EDGE
)
227 return function_point (supernode
, from_edge
, 0, PK_BEFORE_SUPERNODE
);
230 /* A subclass of diagnostic_context for use by
231 program_point::print_source_line. */
233 class debug_diagnostic_context
: public diagnostic_context
236 debug_diagnostic_context ()
238 diagnostic_initialize (this, 0);
239 show_line_numbers_p
= true;
242 ~debug_diagnostic_context ()
244 diagnostic_finish (this);
248 /* Print the source line (if any) for this function_point to PP. */
251 function_point::print_source_line (pretty_printer
*pp
) const
253 const gimple
*stmt
= get_stmt ();
256 // TODO: monospace font
257 debug_diagnostic_context tmp_dc
;
258 gcc_rich_location
richloc (stmt
->location
);
259 diagnostic_show_locus (&tmp_dc
, &richloc
, DK_ERROR
);
260 pp_string (pp
, pp_formatted_text (tmp_dc
.printer
));
263 /* class program_point. */
265 /* Print this program_point to PP. */
268 program_point::print (pretty_printer
*pp
, const format
&f
) const
270 pp_string (pp
, "callstring: ");
271 m_call_string
.print (pp
);
274 m_function_point
.print (pp
, f
);
277 /* Dump this point to stderr. */
280 program_point::dump () const
283 pp_show_color (&pp
) = pp_show_color (global_dc
->printer
);
284 pp
.buffer
->stream
= stderr
;
285 print (&pp
, format (true));
289 /* Return a new json::object of the form
291 "snode_idx" : int (optional), the index of the supernode,
292 "from_edge_snode_idx" : int (only for kind=='PK_BEFORE_SUPERNODE'),
293 "stmt_idx": int (only for kind=='PK_BEFORE_STMT',
294 "call_string": object for the call_string}. */
297 program_point::to_json () const
299 json::object
*point_obj
= new json::object ();
301 point_obj
->set ("kind",
302 new json::string (point_kind_to_string (get_kind ())));
304 if (get_supernode ())
305 point_obj
->set ("snode_idx",
306 new json::integer_number (get_supernode ()->m_index
));
311 case PK_BEFORE_SUPERNODE
:
312 if (const superedge
*sedge
= get_from_edge ())
313 point_obj
->set ("from_edge_snode_idx",
314 new json::integer_number (sedge
->m_src
->m_index
));
317 point_obj
->set ("stmt_idx", new json::integer_number (get_stmt_idx ()));
321 point_obj
->set ("call_string", m_call_string
.to_json ());
326 /* Generate a hash value for this program_point. */
329 program_point::hash () const
331 inchash::hash hstate
;
332 hstate
.merge_hash (m_function_point
.hash ());
333 hstate
.merge_hash (m_call_string
.hash ());
334 return hstate
.end ();
337 /* Get the function * at DEPTH within the call stack. */
340 program_point::get_function_at_depth (unsigned depth
) const
342 gcc_assert (depth
<= m_call_string
.length ());
343 if (depth
== m_call_string
.length ())
344 return m_function_point
.get_function ();
346 return m_call_string
[depth
]->get_caller_function ();
349 /* Assert that this object is sane. */
352 program_point::validate () const
354 /* Skip this in a release build. */
359 m_call_string
.validate ();
360 /* The "callee" of the final entry in the callstring should be the
361 function of the m_function_point. */
362 if (m_call_string
.length () > 0)
363 gcc_assert (m_call_string
[m_call_string
.length () - 1]->get_callee_function ()
367 /* Check to see if SUCC is a valid edge to take (ensuring that we have
368 interprocedurally valid paths in the exploded graph, and enforcing
371 Update the call string if SUCC is a call or a return.
373 Return true if SUCC can be taken, or false otherwise.
375 This is the "point" half of exploded_node::on_edge. */
378 program_point::on_edge (exploded_graph
&eg
,
379 const superedge
*succ
)
381 logger
* const logger
= eg
.get_logger ();
383 switch (succ
->m_kind
)
385 case SUPEREDGE_CFG_EDGE
:
387 const cfg_superedge
*cfg_sedge
= as_a
<const cfg_superedge
*> (succ
);
389 /* Reject abnormal edges; we special-case setjmp/longjmp. */
390 if (cfg_sedge
->get_flags () & EDGE_ABNORMAL
)
397 const call_superedge
*call_sedge
= as_a
<const call_superedge
*> (succ
);
399 if (eg
.get_analysis_plan ().use_summary_p (call_sedge
->m_cedge
))
402 logger
->log ("rejecting call edge: using summary instead");
406 /* Add the callsite to the call string. */
407 m_call_string
.push_call (eg
.get_supergraph (), call_sedge
);
409 /* Impose a maximum recursion depth and don't analyze paths
410 that exceed it further.
411 This is something of a blunt workaround, but it only
412 applies to recursion (and mutual recursion), not to
413 general call stacks. */
414 if (m_call_string
.calc_recursion_depth ()
415 > param_analyzer_max_recursion_depth
)
418 logger
->log ("rejecting call edge: recursion limit exceeded");
419 // TODO: issue a sorry for this?
425 case SUPEREDGE_RETURN
:
427 /* Require that we return to the call site in the call string. */
428 if (m_call_string
.empty_p ())
431 logger
->log ("rejecting return edge: empty call string");
434 const return_superedge
*top_of_stack
= m_call_string
.pop ();
435 if (top_of_stack
!= succ
)
438 logger
->log ("rejecting return edge: return to wrong callsite");
444 case SUPEREDGE_INTRAPROCEDURAL_CALL
:
446 const callgraph_superedge
*cg_sedge
447 = as_a
<const callgraph_superedge
*> (succ
);
448 /* Consider turning this edge into a use of an
449 interprocedural summary. */
450 if (eg
.get_analysis_plan ().use_summary_p (cg_sedge
->m_cedge
))
453 logger
->log ("using function summary for %qE in %qE",
454 cg_sedge
->get_callee_decl (),
455 cg_sedge
->get_caller_decl ());
460 /* Otherwise, we ignore these edges */
462 logger
->log ("rejecting interprocedural edge");
471 /* Comparator for program points within the same supernode,
472 for implementing worklist::key_t comparison operators.
473 Return negative if POINT_A is before POINT_B
474 Return positive if POINT_A is after POINT_B
475 Return 0 if they are equal. */
478 function_point::cmp_within_supernode_1 (const function_point
&point_a
,
479 const function_point
&point_b
)
481 gcc_assert (point_a
.get_supernode () == point_b
.get_supernode ());
483 switch (point_a
.m_kind
)
487 case PK_BEFORE_SUPERNODE
:
488 switch (point_b
.m_kind
)
492 case PK_BEFORE_SUPERNODE
:
496 if (point_a
.m_from_edge
)
497 a_src_idx
= point_a
.m_from_edge
->m_src
->m_index
;
498 if (point_b
.m_from_edge
)
499 b_src_idx
= point_b
.m_from_edge
->m_src
->m_index
;
500 return a_src_idx
- b_src_idx
;
505 case PK_AFTER_SUPERNODE
:
510 switch (point_b
.m_kind
)
514 case PK_BEFORE_SUPERNODE
:
518 return point_a
.m_stmt_idx
- point_b
.m_stmt_idx
;
520 case PK_AFTER_SUPERNODE
:
524 case PK_AFTER_SUPERNODE
:
525 switch (point_b
.m_kind
)
529 case PK_BEFORE_SUPERNODE
:
533 case PK_AFTER_SUPERNODE
:
540 /* Comparator for program points within the same supernode,
541 for implementing worklist::key_t comparison operators.
542 Return negative if POINT_A is before POINT_B
543 Return positive if POINT_A is after POINT_B
544 Return 0 if they are equal. */
547 function_point::cmp_within_supernode (const function_point
&point_a
,
548 const function_point
&point_b
)
550 int result
= cmp_within_supernode_1 (point_a
, point_b
);
552 /* Check that the ordering is symmetric */
554 int reversed
= cmp_within_supernode_1 (point_b
, point_a
);
555 gcc_assert (reversed
== -result
);
561 /* Comparator for imposing an order on function_points. */
564 function_point::cmp (const function_point
&point_a
,
565 const function_point
&point_b
)
567 int idx_a
= point_a
.m_supernode
? point_a
.m_supernode
->m_index
: -1;
568 int idx_b
= point_b
.m_supernode
? point_b
.m_supernode
->m_index
: -1;
569 if (int cmp_idx
= idx_a
- idx_b
)
571 gcc_assert (point_a
.m_supernode
== point_b
.m_supernode
);
572 if (point_a
.m_supernode
)
573 return cmp_within_supernode (point_a
, point_b
);
578 /* Comparator for use by vec<function_point>::qsort. */
581 function_point::cmp_ptr (const void *p1
, const void *p2
)
583 const function_point
*fp1
= (const function_point
*)p1
;
584 const function_point
*fp2
= (const function_point
*)p2
;
585 return cmp (*fp1
, *fp2
);
588 /* For PK_BEFORE_STMT, go to next stmt (or to PK_AFTER_SUPERNODE). */
591 function_point::next_stmt ()
593 gcc_assert (m_kind
== PK_BEFORE_STMT
);
594 if (++m_stmt_idx
== m_supernode
->m_stmts
.length ())
596 m_kind
= PK_AFTER_SUPERNODE
;
601 /* For those program points for which there is a uniquely-defined
602 successor, return it. */
605 program_point::get_next () const
607 switch (m_function_point
.get_kind ())
612 case PK_AFTER_SUPERNODE
:
613 gcc_unreachable (); /* Not uniquely defined. */
614 case PK_BEFORE_SUPERNODE
:
615 if (get_supernode ()->m_stmts
.length () > 0)
616 return before_stmt (get_supernode (), 0, get_call_string ());
618 return after_supernode (get_supernode (), get_call_string ());
621 unsigned next_idx
= get_stmt_idx ();
622 if (next_idx
< get_supernode ()->m_stmts
.length ())
623 return before_stmt (get_supernode (), next_idx
, get_call_string ());
625 return after_supernode (get_supernode (), get_call_string ());
634 /* Verify that function_point::operator== works as expected. */
637 test_function_point_equality ()
639 const supernode
*snode
= NULL
;
641 function_point a
= function_point (snode
, NULL
, 0,
642 PK_BEFORE_SUPERNODE
);
643 function_point b
= function_point::before_supernode (snode
, NULL
);
647 /* Verify that function_point::cmp_within_supernode works as expected. */
650 test_function_point_ordering ()
652 const supernode
*snode
= NULL
;
653 const call_string call_string
;
655 /* Populate an array with various points within the same
657 auto_vec
<function_point
> points
;
658 points
.safe_push (function_point::before_supernode (snode
, NULL
));
659 points
.safe_push (function_point::before_stmt (snode
, 0));
660 points
.safe_push (function_point::before_stmt (snode
, 1));
661 points
.safe_push (function_point::after_supernode (snode
));
663 /* Check all pairs. */
665 function_point
*point_a
;
666 FOR_EACH_VEC_ELT (points
, i
, point_a
)
669 function_point
*point_b
;
670 FOR_EACH_VEC_ELT (points
, j
, point_b
)
672 int cmp
= function_point::cmp_within_supernode (*point_a
, *point_b
);
676 ASSERT_TRUE (cmp
< 0);
678 ASSERT_TRUE (cmp
> 0);
683 /* Verify that program_point::operator== works as expected. */
686 test_program_point_equality ()
688 const supernode
*snode
= NULL
;
690 const call_string cs
;
692 program_point a
= program_point::before_supernode (snode
, NULL
,
695 program_point b
= program_point::before_supernode (snode
, NULL
,
699 // TODO: verify with non-empty callstrings, with different edges
702 /* Run all of the selftests within this file. */
705 analyzer_program_point_cc_tests ()
707 test_function_point_equality ();
708 test_function_point_ordering ();
709 test_program_point_equality ();
712 } // namespace selftest
714 #endif /* CHECKING_P */
718 #endif /* #if ENABLE_ANALYZER */