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