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