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