Branch data Line data Source code
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>.
4 : :
5 : : This file is part of GCC.
6 : :
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)
10 : : any later version.
11 : :
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.
16 : :
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/>. */
20 : :
21 : : #include "analyzer/common.h"
22 : :
23 : : #include "diagnostics/event-id.h"
24 : : #include "gcc-rich-location.h"
25 : : #include "gimple-pretty-print.h"
26 : : #include "sbitmap.h"
27 : : #include "selftest.h"
28 : : #include "shortest-paths.h"
29 : :
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"
43 : :
44 : : #if ENABLE_ANALYZER
45 : :
46 : : namespace ana {
47 : :
48 : : /* Get a string for PK. */
49 : :
50 : : const char *
51 : 14 : point_kind_to_string (enum point_kind pk)
52 : : {
53 : 14 : switch (pk)
54 : : {
55 : 0 : default:
56 : 0 : gcc_unreachable ();
57 : : case PK_ORIGIN:
58 : : return "PK_ORIGIN";
59 : 4 : case PK_BEFORE_SUPERNODE:
60 : 4 : return "PK_BEFORE_SUPERNODE";
61 : 4 : case PK_BEFORE_STMT:
62 : 4 : return "PK_BEFORE_STMT";
63 : 4 : case PK_AFTER_SUPERNODE:
64 : 4 : return "PK_AFTER_SUPERNODE";
65 : 0 : case PK_EMPTY:
66 : 0 : return "PK_EMPTY";
67 : 0 : case PK_DELETED:
68 : 0 : return "PK_DELETED";
69 : : }
70 : : }
71 : :
72 : : /* class function_point. */
73 : :
74 : 3716856 : function_point::function_point (const supernode *supernode,
75 : : const superedge *from_edge,
76 : : unsigned stmt_idx,
77 : 3716856 : enum point_kind kind)
78 : 3716856 : : m_supernode (supernode), m_from_edge (from_edge),
79 : 3716856 : m_stmt_idx (stmt_idx), m_kind (kind)
80 : : {
81 : 3716856 : if (from_edge)
82 : : {
83 : 216736 : gcc_checking_assert (m_kind == PK_BEFORE_SUPERNODE);
84 : 216736 : gcc_checking_assert (from_edge->get_kind () == SUPEREDGE_CFG_EDGE);
85 : : }
86 : 3716856 : if (stmt_idx)
87 : 596272 : gcc_checking_assert (m_kind == PK_BEFORE_STMT);
88 : 3716856 : }
89 : :
90 : : /* Print this function_point to PP. */
91 : :
92 : : void
93 : 6131 : function_point::print (pretty_printer *pp, const format &f) const
94 : : {
95 : 6131 : switch (get_kind ())
96 : : {
97 : 0 : default:
98 : 0 : gcc_unreachable ();
99 : :
100 : 30 : case PK_ORIGIN:
101 : 30 : pp_printf (pp, "origin");
102 : 30 : if (f.m_newlines)
103 : 20 : pp_newline (pp);
104 : : break;
105 : :
106 : 599 : case PK_BEFORE_SUPERNODE:
107 : 599 : {
108 : 599 : if (m_from_edge)
109 : : {
110 : 517 : if (basic_block bb = m_from_edge->m_src->m_bb)
111 : 517 : pp_printf (pp, "before SN: %i (from SN: %i (bb: %i))",
112 : 517 : m_supernode->m_index, m_from_edge->m_src->m_index,
113 : : bb->index);
114 : : else
115 : 0 : pp_printf (pp, "before SN: %i (from SN: %i)",
116 : 0 : m_supernode->m_index, m_from_edge->m_src->m_index);
117 : : }
118 : : else
119 : 82 : pp_printf (pp, "before SN: %i (NULL from-edge)",
120 : 82 : m_supernode->m_index);
121 : 599 : f.spacer (pp);
122 : 599 : for (gphi_iterator gpi
123 : 599 : = const_cast<supernode *>(get_supernode ())->start_phis ();
124 : 805 : !gsi_end_p (gpi); gsi_next (&gpi))
125 : : {
126 : 206 : const gphi *phi = gpi.phi ();
127 : 206 : pp_gimple_stmt_1 (pp, phi, 0, (dump_flags_t)0);
128 : : }
129 : : }
130 : : break;
131 : :
132 : 3647 : case PK_BEFORE_STMT:
133 : 3647 : pp_printf (pp, "before (SN: %i stmt: %i): ", m_supernode->m_index,
134 : 3647 : m_stmt_idx);
135 : 3647 : f.spacer (pp);
136 : 3647 : pp_gimple_stmt_1 (pp, get_stmt (), 0, (dump_flags_t)0);
137 : 3647 : if (f.m_newlines)
138 : : {
139 : 349 : pp_newline (pp);
140 : 349 : print_source_line (pp);
141 : : }
142 : : break;
143 : :
144 : 1855 : case PK_AFTER_SUPERNODE:
145 : 1855 : pp_printf (pp, "after SN: %i", m_supernode->m_index);
146 : 1855 : if (f.m_newlines)
147 : 292 : pp_newline (pp);
148 : : break;
149 : : }
150 : 6131 : }
151 : :
152 : : /* Generate a hash value for this function_point. */
153 : :
154 : : hashval_t
155 : 18762775 : function_point::hash () const
156 : : {
157 : 18762775 : inchash::hash hstate;
158 : 18762775 : if (m_supernode)
159 : 18643333 : hstate.add_int (m_supernode->m_index);
160 : 18762775 : hstate.add_ptr (m_from_edge);
161 : 18762775 : hstate.add_int (m_stmt_idx);
162 : 18762775 : hstate.add_int (m_kind);
163 : 18762775 : return hstate.end ();
164 : : }
165 : :
166 : : /* Get the function at this point, if any. */
167 : :
168 : : function *
169 : 7374015 : function_point::get_function () const
170 : : {
171 : 7374015 : if (m_supernode)
172 : 7351350 : return m_supernode->m_fun;
173 : : else
174 : : return nullptr;
175 : : }
176 : :
177 : : /* Get the gimple stmt for this function_point, if any. */
178 : :
179 : : const gimple *
180 : 1108418 : function_point::get_stmt () const
181 : : {
182 : 1108418 : if (m_kind == PK_BEFORE_STMT)
183 : 806498 : return m_supernode->m_stmts[m_stmt_idx];
184 : 301920 : else if (m_kind == PK_AFTER_SUPERNODE)
185 : 143737 : return m_supernode->get_last_stmt ();
186 : : else
187 : : return nullptr;
188 : : }
189 : :
190 : : /* Get a location for this function_point, if any. */
191 : :
192 : : location_t
193 : 7982 : function_point::get_location () const
194 : : {
195 : 7982 : const gimple *stmt = get_stmt ();
196 : 7982 : if (stmt)
197 : 2703 : return stmt->location;
198 : 5279 : if (m_kind == PK_BEFORE_SUPERNODE)
199 : 5177 : return m_supernode->get_start_location ();
200 : 102 : else if (m_kind == PK_AFTER_SUPERNODE)
201 : 98 : return m_supernode->get_end_location ();
202 : : else
203 : : return UNKNOWN_LOCATION;
204 : : }
205 : :
206 : : /* Return true if this function_point is a before_stmt for
207 : : the final stmt in its supernode. */
208 : :
209 : : bool
210 : 7655 : function_point::final_stmt_p () const
211 : : {
212 : 7655 : if (m_kind != PK_BEFORE_STMT)
213 : : return false;
214 : 15310 : return m_stmt_idx == get_supernode ()->m_stmts.length () - 1;
215 : : }
216 : :
217 : : /* Create a function_point representing the entrypoint of function FUN. */
218 : :
219 : : function_point
220 : 9981 : function_point::from_function_entry (const supergraph &sg, const function &fun)
221 : : {
222 : 9981 : return before_supernode (sg.get_node_for_function_entry (fun), nullptr);
223 : : }
224 : :
225 : : /* Create a function_point representing entering supernode SUPERNODE,
226 : : having reached it via FROM_EDGE (which could be nullptr). */
227 : :
228 : : function_point
229 : 288243 : function_point::before_supernode (const supernode *supernode,
230 : : const superedge *from_edge)
231 : : {
232 : 288243 : if (from_edge && from_edge->get_kind () != SUPEREDGE_CFG_EDGE)
233 : : from_edge = nullptr;
234 : 288243 : return function_point (supernode, from_edge, 0, PK_BEFORE_SUPERNODE);
235 : : }
236 : :
237 : : /* A subclass of diagnostics::context for use by
238 : : program_point::print_source_line. */
239 : :
240 : : class debug_diagnostic_context : public diagnostics::context
241 : : {
242 : : public:
243 : 349 : debug_diagnostic_context ()
244 : 349 : {
245 : 349 : diagnostic_initialize (this, 0);
246 : 349 : auto &source_printing_opts = get_source_printing_options ();
247 : 349 : source_printing_opts.show_line_numbers_p = true;
248 : 349 : source_printing_opts.enabled = true;
249 : 349 : }
250 : 349 : ~debug_diagnostic_context ()
251 : : {
252 : 698 : diagnostic_finish (this);
253 : 349 : }
254 : : };
255 : :
256 : : /* Print the source line (if any) for this function_point to PP. */
257 : :
258 : : void
259 : 349 : function_point::print_source_line (pretty_printer *pp) const
260 : : {
261 : 349 : const gimple *stmt = get_stmt ();
262 : 349 : if (!stmt)
263 : 0 : return;
264 : : // TODO: monospace font
265 : 349 : debug_diagnostic_context tmp_dc;
266 : 349 : gcc_rich_location richloc (stmt->location);
267 : 349 : diagnostics::source_print_policy source_policy (tmp_dc);
268 : 349 : gcc_assert (pp);
269 : 349 : source_policy.print (*pp, richloc, diagnostics::kind::error, nullptr);
270 : 349 : pp_string (pp, pp_formatted_text (tmp_dc.get_reference_printer ()));
271 : 698 : }
272 : :
273 : : /* class program_point. */
274 : :
275 : : /* Print this program_point to PP. */
276 : :
277 : : void
278 : 3328 : program_point::print (pretty_printer *pp, const format &f) const
279 : : {
280 : 3328 : pp_string (pp, "callstring: ");
281 : 3328 : m_call_string->print (pp);
282 : 3328 : f.spacer (pp);
283 : :
284 : 3328 : m_function_point.print (pp, f);
285 : 3328 : }
286 : :
287 : : /* Dump this point to stderr. */
288 : :
289 : : DEBUG_FUNCTION void
290 : 0 : program_point::dump () const
291 : : {
292 : 0 : tree_dump_pretty_printer pp (stderr);
293 : 0 : print (&pp, format (true));
294 : 0 : }
295 : :
296 : : /* Return a new json::object of the form
297 : : {"kind" : str,
298 : : "snode_idx" : int (optional), the index of the supernode,
299 : : "from_edge_snode_idx" : int (only for kind=='PK_BEFORE_SUPERNODE'),
300 : : "stmt_idx": int (only for kind=='PK_BEFORE_STMT',
301 : : "call_string": object for the call_string}. */
302 : :
303 : : std::unique_ptr<json::object>
304 : 0 : program_point::to_json () const
305 : : {
306 : 0 : auto point_obj = std::make_unique<json::object> ();
307 : :
308 : 0 : point_obj->set_string ("kind", point_kind_to_string (get_kind ()));
309 : :
310 : 0 : if (get_supernode ())
311 : 0 : point_obj->set_integer ("snode_idx", get_supernode ()->m_index);
312 : :
313 : 0 : switch (get_kind ())
314 : : {
315 : : default: break;
316 : 0 : case PK_BEFORE_SUPERNODE:
317 : 0 : if (const superedge *sedge = get_from_edge ())
318 : 0 : point_obj->set_integer ("from_edge_snode_idx", sedge->m_src->m_index);
319 : : break;
320 : 0 : case PK_BEFORE_STMT:
321 : 0 : point_obj->set_integer ("stmt_idx", get_stmt_idx ());
322 : 0 : break;
323 : : }
324 : :
325 : 0 : point_obj->set ("call_string", m_call_string->to_json ());
326 : :
327 : 0 : return point_obj;
328 : : }
329 : :
330 : : /* Update the callstack to represent a call from caller to callee.
331 : :
332 : : Generally used to push a custom call to a perticular program point
333 : : where we don't have a superedge representing the call. */
334 : : void
335 : 80 : program_point::push_to_call_stack (const supernode *caller,
336 : : const supernode *callee)
337 : : {
338 : 80 : m_call_string = m_call_string->push_call (callee, caller);
339 : 80 : }
340 : :
341 : : /* Pop the topmost call from the current callstack. */
342 : : void
343 : 1672 : program_point::pop_from_call_stack ()
344 : : {
345 : 1672 : m_call_string = m_call_string->get_parent ();
346 : 1672 : gcc_assert (m_call_string);
347 : 1672 : }
348 : :
349 : : /* Generate a hash value for this program_point. */
350 : :
351 : : hashval_t
352 : 4837924 : program_point::hash () const
353 : : {
354 : 4837924 : inchash::hash hstate;
355 : 4837924 : hstate.merge_hash (m_function_point.hash ());
356 : 4837924 : hstate.add_ptr (m_call_string);
357 : 4837924 : return hstate.end ();
358 : : }
359 : :
360 : : /* Get the function * at DEPTH within the call stack. */
361 : :
362 : : function *
363 : 1203123 : program_point::get_function_at_depth (unsigned depth) const
364 : : {
365 : 1889843 : gcc_assert (depth <= m_call_string->length ());
366 : 1203123 : if (depth == m_call_string->length ())
367 : 759425 : return m_function_point.get_function ();
368 : : else
369 : 443698 : return get_call_string ()[depth].get_caller_function ();
370 : : }
371 : :
372 : : /* Assert that this object is sane. */
373 : :
374 : : void
375 : 766041 : program_point::validate () const
376 : : {
377 : : /* Skip this in a release build. */
378 : : #if !CHECKING_P
379 : : return;
380 : : #endif
381 : :
382 : 766041 : m_call_string->validate ();
383 : : /* The "callee" of the final entry in the callstring should be the
384 : : function of the m_function_point. */
385 : 766041 : if (m_call_string->length () > 0)
386 : 243022 : gcc_assert
387 : : ((*m_call_string)[m_call_string->length () - 1].get_callee_function ()
388 : : == get_function ());
389 : 766041 : }
390 : :
391 : : /* Check to see if SUCC is a valid edge to take (ensuring that we have
392 : : interprocedurally valid paths in the exploded graph, and enforcing
393 : : recursion limits).
394 : :
395 : : Update the call string if SUCC is a call or a return.
396 : :
397 : : Return true if SUCC can be taken, or false otherwise.
398 : :
399 : : This is the "point" half of exploded_node::on_edge. */
400 : :
401 : : bool
402 : 148187 : program_point::on_edge (exploded_graph &eg,
403 : : const superedge *succ)
404 : : {
405 : 148187 : logger * const logger = eg.get_logger ();
406 : 148187 : LOG_FUNC (logger);
407 : 148187 : switch (succ->m_kind)
408 : : {
409 : 113015 : case SUPEREDGE_CFG_EDGE:
410 : 113015 : {
411 : 113015 : const cfg_superedge *cfg_sedge = as_a <const cfg_superedge *> (succ);
412 : :
413 : 113015 : if (cfg_sedge->get_flags () & EDGE_ABNORMAL)
414 : : {
415 : 131 : const supernode *src_snode = cfg_sedge->m_src;
416 : 131 : if (gimple *last_stmt = src_snode->get_last_stmt ())
417 : 124 : if (last_stmt->code == GIMPLE_GOTO)
418 : : {
419 : : /* For the program_point aspect here, consider all
420 : : out-edges from goto stmts to be valid; we'll
421 : : consider state separately. */
422 : : return true;
423 : : }
424 : :
425 : : /* Reject other kinds of abnormal edges;
426 : : we special-case setjmp/longjmp. */
427 : : return false;
428 : : }
429 : : }
430 : : break;
431 : :
432 : 7656 : case SUPEREDGE_CALL:
433 : 7656 : {
434 : 7656 : const call_superedge *call_sedge = as_a <const call_superedge *> (succ);
435 : :
436 : 7656 : if (eg.get_analysis_plan ().use_summary_p (call_sedge->m_cedge))
437 : : {
438 : 922 : if (logger)
439 : 0 : logger->log ("rejecting call edge: using summary instead");
440 : 922 : return false;
441 : : }
442 : :
443 : : /* Add the callsite to the call string. */
444 : 6734 : m_call_string = m_call_string->push_call (eg.get_supergraph (),
445 : : call_sedge);
446 : :
447 : : /* Impose a maximum recursion depth and don't analyze paths
448 : : that exceed it further.
449 : : This is something of a blunt workaround, but it only
450 : : applies to recursion (and mutual recursion), not to
451 : : general call stacks. */
452 : 6734 : if (m_call_string->calc_recursion_depth ()
453 : 6734 : > param_analyzer_max_recursion_depth)
454 : : {
455 : 511 : if (logger)
456 : 0 : logger->log ("rejecting call edge: recursion limit exceeded");
457 : : // TODO: issue a sorry for this?
458 : 511 : return false;
459 : : }
460 : : }
461 : : break;
462 : :
463 : 18457 : case SUPEREDGE_RETURN:
464 : 18457 : {
465 : : /* Require that we return to the call site in the call string. */
466 : 18457 : if (m_call_string->empty_p ())
467 : : {
468 : 3813 : if (logger)
469 : 0 : logger->log ("rejecting return edge: empty call string");
470 : 12619 : return false;
471 : : }
472 : 14644 : const call_string::element_t &top_of_stack
473 : 14644 : = m_call_string->get_top_of_stack ();
474 : 14644 : m_call_string = m_call_string->get_parent ();
475 : 14644 : call_string::element_t current_call_string_element (succ->m_dest,
476 : 14644 : succ->m_src);
477 : 14644 : if (top_of_stack != current_call_string_element)
478 : : {
479 : 8806 : if (logger)
480 : 0 : logger->log ("rejecting return edge: return to wrong callsite");
481 : 8806 : return false;
482 : : }
483 : : }
484 : 5838 : break;
485 : :
486 : 9059 : case SUPEREDGE_INTRAPROCEDURAL_CALL:
487 : 9059 : {
488 : 9059 : const callgraph_superedge *cg_sedge
489 : 9059 : = as_a <const callgraph_superedge *> (succ);
490 : : /* Consider turning this edge into a use of an
491 : : interprocedural summary. */
492 : 9059 : if (eg.get_analysis_plan ().use_summary_p (cg_sedge->m_cedge))
493 : : {
494 : 922 : if (logger)
495 : 0 : logger->log ("using function summary for %qE in %qE",
496 : : cg_sedge->get_callee_decl (),
497 : : cg_sedge->get_caller_decl ());
498 : 922 : return true;
499 : : }
500 : : else
501 : : {
502 : : /* Otherwise, we ignore these edges */
503 : 8137 : if (logger)
504 : 0 : logger->log ("rejecting interprocedural edge");
505 : 8137 : return false;
506 : : }
507 : : }
508 : : }
509 : :
510 : : return true;
511 : 148187 : }
512 : :
513 : : /* Comparator for program points within the same supernode,
514 : : for implementing worklist::key_t comparison operators.
515 : : Return negative if POINT_A is before POINT_B
516 : : Return positive if POINT_A is after POINT_B
517 : : Return 0 if they are equal. */
518 : :
519 : : int
520 : 494136 : function_point::cmp_within_supernode_1 (const function_point &point_a,
521 : : const function_point &point_b)
522 : : {
523 : 494136 : gcc_assert (point_a.get_supernode () == point_b.get_supernode ());
524 : :
525 : 494136 : switch (point_a.m_kind)
526 : : {
527 : 0 : default:
528 : 0 : gcc_unreachable ();
529 : 248404 : case PK_BEFORE_SUPERNODE:
530 : 248404 : switch (point_b.m_kind)
531 : : {
532 : 0 : default:
533 : 0 : gcc_unreachable ();
534 : 244272 : case PK_BEFORE_SUPERNODE:
535 : 244272 : {
536 : 244272 : int a_src_idx = -1;
537 : 244272 : int b_src_idx = -1;
538 : 244272 : if (point_a.m_from_edge)
539 : 230380 : a_src_idx = point_a.m_from_edge->m_src->m_index;
540 : 244272 : if (point_b.m_from_edge)
541 : 230380 : b_src_idx = point_b.m_from_edge->m_src->m_index;
542 : 244272 : return a_src_idx - b_src_idx;
543 : : }
544 : : break;
545 : :
546 : : case PK_BEFORE_STMT:
547 : : case PK_AFTER_SUPERNODE:
548 : : return -1;
549 : : }
550 : 133160 : break;
551 : 133160 : case PK_BEFORE_STMT:
552 : 133160 : switch (point_b.m_kind)
553 : : {
554 : 0 : default:
555 : 0 : gcc_unreachable ();
556 : : case PK_BEFORE_SUPERNODE:
557 : : return 1;
558 : :
559 : 108834 : case PK_BEFORE_STMT:
560 : 108834 : return point_a.m_stmt_idx - point_b.m_stmt_idx;
561 : :
562 : : case PK_AFTER_SUPERNODE:
563 : : return -1;
564 : : }
565 : 112572 : break;
566 : 112572 : case PK_AFTER_SUPERNODE:
567 : 112572 : switch (point_b.m_kind)
568 : : {
569 : 0 : default:
570 : 0 : gcc_unreachable ();
571 : : case PK_BEFORE_SUPERNODE:
572 : : case PK_BEFORE_STMT:
573 : : return 1;
574 : :
575 : : case PK_AFTER_SUPERNODE:
576 : : return 0;
577 : : }
578 : : break;
579 : : }
580 : : }
581 : :
582 : : /* Comparator for program points within the same supernode,
583 : : for implementing worklist::key_t comparison operators.
584 : : Return negative if POINT_A is before POINT_B
585 : : Return positive if POINT_A is after POINT_B
586 : : Return 0 if they are equal. */
587 : :
588 : : int
589 : 247068 : function_point::cmp_within_supernode (const function_point &point_a,
590 : : const function_point &point_b)
591 : : {
592 : 247068 : int result = cmp_within_supernode_1 (point_a, point_b);
593 : :
594 : : /* Check that the ordering is symmetric */
595 : : #if CHECKING_P
596 : 247068 : int reversed = cmp_within_supernode_1 (point_b, point_a);
597 : 247068 : gcc_assert (reversed == -result);
598 : : #endif
599 : :
600 : 247068 : return result;
601 : : }
602 : :
603 : : /* Comparator for imposing an order on function_points. */
604 : :
605 : : int
606 : 4299 : function_point::cmp (const function_point &point_a,
607 : : const function_point &point_b)
608 : : {
609 : 4299 : int idx_a = point_a.m_supernode ? point_a.m_supernode->m_index : -1;
610 : 4299 : int idx_b = point_b.m_supernode ? point_b.m_supernode->m_index : -1;
611 : 4299 : if (int cmp_idx = idx_a - idx_b)
612 : : return cmp_idx;
613 : 3175 : gcc_assert (point_a.m_supernode == point_b.m_supernode);
614 : 3175 : if (point_a.m_supernode)
615 : 3175 : return cmp_within_supernode (point_a, point_b);
616 : : else
617 : : return 0;
618 : : }
619 : :
620 : : /* Comparator for use by vec<function_point>::qsort. */
621 : :
622 : : int
623 : 1795 : function_point::cmp_ptr (const void *p1, const void *p2)
624 : : {
625 : 1795 : const function_point *fp1 = (const function_point *)p1;
626 : 1795 : const function_point *fp2 = (const function_point *)p2;
627 : 1795 : return cmp (*fp1, *fp2);
628 : : }
629 : :
630 : : /* For PK_BEFORE_STMT, go to next stmt (or to PK_AFTER_SUPERNODE). */
631 : :
632 : : void
633 : 73204 : function_point::next_stmt ()
634 : : {
635 : 73204 : gcc_assert (m_kind == PK_BEFORE_STMT);
636 : 146408 : if (++m_stmt_idx == m_supernode->m_stmts.length ())
637 : : {
638 : 18373 : m_kind = PK_AFTER_SUPERNODE;
639 : 18373 : m_stmt_idx = 0;
640 : : }
641 : 73204 : }
642 : :
643 : : /* For those function points for which there is a uniquely-defined
644 : : successor, return it. */
645 : :
646 : : function_point
647 : 53202 : function_point::get_next () const
648 : : {
649 : 53202 : switch (get_kind ())
650 : : {
651 : 0 : default:
652 : 0 : gcc_unreachable ();
653 : 0 : case PK_ORIGIN:
654 : 0 : case PK_AFTER_SUPERNODE:
655 : 0 : gcc_unreachable (); /* Not uniquely defined. */
656 : 14658 : case PK_BEFORE_SUPERNODE:
657 : 14658 : if (get_supernode ()->m_stmts.length () > 0)
658 : 12066 : return before_stmt (get_supernode (), 0);
659 : : else
660 : 2592 : return after_supernode (get_supernode ());
661 : 38544 : case PK_BEFORE_STMT:
662 : 38544 : {
663 : 38544 : unsigned next_idx = get_stmt_idx () + 1;
664 : 38544 : if (next_idx < get_supernode ()->m_stmts.length ())
665 : 24909 : return before_stmt (get_supernode (), next_idx);
666 : : else
667 : 13635 : return after_supernode (get_supernode ());
668 : : }
669 : : }
670 : : }
671 : :
672 : : /* class program_point. */
673 : :
674 : : program_point
675 : 3366 : program_point::origin (const region_model_manager &mgr)
676 : : {
677 : 3366 : return program_point (function_point (nullptr, nullptr,
678 : 6732 : 0, PK_ORIGIN),
679 : 3366 : mgr.get_empty_call_string ());
680 : : }
681 : :
682 : : program_point
683 : 9981 : program_point::from_function_entry (const region_model_manager &mgr,
684 : : const supergraph &sg,
685 : : const function &fun)
686 : : {
687 : 9981 : return program_point (function_point::from_function_entry (sg, fun),
688 : 9981 : mgr.get_empty_call_string ());
689 : : }
690 : :
691 : : /* For those program points for which there is a uniquely-defined
692 : : successor, return it. */
693 : :
694 : : program_point
695 : 103042 : program_point::get_next () const
696 : : {
697 : 103042 : switch (m_function_point.get_kind ())
698 : : {
699 : 0 : default:
700 : 0 : gcc_unreachable ();
701 : 0 : case PK_ORIGIN:
702 : 0 : case PK_AFTER_SUPERNODE:
703 : 0 : gcc_unreachable (); /* Not uniquely defined. */
704 : 102843 : case PK_BEFORE_SUPERNODE:
705 : 102843 : if (get_supernode ()->m_stmts.length () > 0)
706 : 69723 : return before_stmt (get_supernode (), 0, get_call_string ());
707 : : else
708 : 33120 : return after_supernode (get_supernode (), get_call_string ());
709 : 199 : case PK_BEFORE_STMT:
710 : 199 : {
711 : 199 : unsigned next_idx = get_stmt_idx () + 1;
712 : 199 : if (next_idx < get_supernode ()->m_stmts.length ())
713 : 112 : return before_stmt (get_supernode (), next_idx, get_call_string ());
714 : : else
715 : 87 : return after_supernode (get_supernode (), get_call_string ());
716 : : }
717 : : }
718 : : }
719 : :
720 : : /* Return true iff POINT_A and POINT_B share the same function and
721 : : call_string, both directly, and when attempting to undo inlining
722 : : information. */
723 : :
724 : : bool
725 : 110 : program_point::effectively_intraprocedural_p (const program_point &point_a,
726 : : const program_point &point_b)
727 : : {
728 : : /* First, compare without considering inlining info. */
729 : 110 : if (point_a.get_function ()
730 : 110 : != point_b.get_function ())
731 : : return false;
732 : 110 : if (&point_a.get_call_string ()
733 : 110 : != &point_b.get_call_string ())
734 : : return false;
735 : :
736 : : /* Consider inlining info; they must have originally come from
737 : : the same function and have been inlined in the same way. */
738 : 110 : location_t loc_a = point_a.get_location ();
739 : 110 : location_t loc_b = point_b.get_location ();
740 : 110 : inlining_iterator iter_a (loc_a);
741 : 110 : inlining_iterator iter_b (loc_b);
742 : 314 : while (!(iter_a.done_p () || iter_b.done_p ()))
743 : : {
744 : 110 : if (iter_a.done_p () || iter_b.done_p ())
745 : : return false;
746 : :
747 : 110 : if (iter_a.get_fndecl () != iter_b.get_fndecl ())
748 : : return false;
749 : 108 : if (iter_a.get_callsite () != iter_b.get_callsite ())
750 : : return false;
751 : 108 : if (iter_a.get_block () != iter_b.get_block ())
752 : : return false;
753 : :
754 : 94 : iter_a.next ();
755 : 94 : iter_b.next ();
756 : : }
757 : :
758 : : return true;
759 : : }
760 : :
761 : : #if CHECKING_P
762 : :
763 : : namespace selftest {
764 : :
765 : : /* Verify that function_point::operator== works as expected. */
766 : :
767 : : static void
768 : 4 : test_function_point_equality ()
769 : : {
770 : 4 : const supernode *snode = nullptr;
771 : :
772 : 4 : function_point a = function_point (snode, nullptr, 0,
773 : 4 : PK_BEFORE_SUPERNODE);
774 : 4 : function_point b = function_point::before_supernode (snode, nullptr);
775 : 4 : ASSERT_EQ (a, b);
776 : 4 : }
777 : :
778 : : /* Verify that function_point::cmp_within_supernode works as expected. */
779 : :
780 : : static void
781 : 4 : test_function_point_ordering ()
782 : : {
783 : 4 : const supernode *snode = nullptr;
784 : :
785 : : /* Populate an array with various points within the same
786 : : snode, in order. */
787 : 4 : auto_vec<function_point> points;
788 : 4 : points.safe_push (function_point::before_supernode (snode, nullptr));
789 : 4 : points.safe_push (function_point::before_stmt (snode, 0));
790 : 4 : points.safe_push (function_point::before_stmt (snode, 1));
791 : 4 : points.safe_push (function_point::after_supernode (snode));
792 : :
793 : : /* Check all pairs. */
794 : 4 : unsigned i;
795 : 4 : function_point *point_a;
796 : 40 : FOR_EACH_VEC_ELT (points, i, point_a)
797 : : {
798 : : unsigned j;
799 : : function_point *point_b;
800 : 80 : FOR_EACH_VEC_ELT (points, j, point_b)
801 : : {
802 : 64 : int cmp = function_point::cmp_within_supernode (*point_a, *point_b);
803 : 64 : if (i == j)
804 : 16 : ASSERT_EQ (cmp, 0);
805 : 64 : if (i < j)
806 : 24 : ASSERT_TRUE (cmp < 0);
807 : 64 : if (i > j)
808 : 24 : ASSERT_TRUE (cmp > 0);
809 : : }
810 : : }
811 : 4 : }
812 : :
813 : : /* Verify that program_point::operator== works as expected. */
814 : :
815 : : static void
816 : 4 : test_program_point_equality ()
817 : : {
818 : 4 : region_model_manager mgr;
819 : :
820 : 4 : const supernode *snode = nullptr;
821 : :
822 : 4 : const call_string &cs = mgr.get_empty_call_string ();
823 : :
824 : 4 : program_point a = program_point::before_supernode (snode, nullptr,
825 : : cs);
826 : :
827 : 4 : program_point b = program_point::before_supernode (snode, nullptr,
828 : : cs);
829 : :
830 : 4 : ASSERT_EQ (a, b);
831 : : // TODO: verify with non-empty callstrings, with different edges
832 : 4 : }
833 : :
834 : : /* Run all of the selftests within this file. */
835 : :
836 : : void
837 : 4 : analyzer_program_point_cc_tests ()
838 : : {
839 : 4 : test_function_point_equality ();
840 : 4 : test_function_point_ordering ();
841 : 4 : test_program_point_equality ();
842 : 4 : }
843 : :
844 : : } // namespace selftest
845 : :
846 : : #endif /* CHECKING_P */
847 : :
848 : : } // namespace ana
849 : :
850 : : #endif /* #if ENABLE_ANALYZER */
|
