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 | point_kind_to_string (enum point_kind pk) |
65 | { |
66 | switch (pk) |
67 | { |
68 | default: |
69 | gcc_unreachable (); |
70 | case PK_ORIGIN: |
71 | return "PK_ORIGIN" ; |
72 | case PK_BEFORE_SUPERNODE: |
73 | return "PK_BEFORE_SUPERNODE" ; |
74 | case PK_BEFORE_STMT: |
75 | return "PK_BEFORE_STMT" ; |
76 | case PK_AFTER_SUPERNODE: |
77 | return "PK_AFTER_SUPERNODE" ; |
78 | case PK_EMPTY: |
79 | return "PK_EMPTY" ; |
80 | case PK_DELETED: |
81 | return "PK_DELETED" ; |
82 | } |
83 | } |
84 | |
85 | /* class function_point. */ |
86 | |
87 | function_point::function_point (const supernode *supernode, |
88 | const superedge *from_edge, |
89 | unsigned stmt_idx, |
90 | enum point_kind kind) |
91 | : m_supernode (supernode), m_from_edge (from_edge), |
92 | m_stmt_idx (stmt_idx), m_kind (kind) |
93 | { |
94 | if (from_edge) |
95 | { |
96 | gcc_checking_assert (m_kind == PK_BEFORE_SUPERNODE); |
97 | gcc_checking_assert (from_edge->get_kind () == SUPEREDGE_CFG_EDGE); |
98 | } |
99 | if (stmt_idx) |
100 | gcc_checking_assert (m_kind == PK_BEFORE_STMT); |
101 | } |
102 | |
103 | /* Print this function_point to PP. */ |
104 | |
105 | void |
106 | function_point::print (pretty_printer *pp, const format &f) const |
107 | { |
108 | switch (get_kind ()) |
109 | { |
110 | default: |
111 | gcc_unreachable (); |
112 | |
113 | case PK_ORIGIN: |
114 | pp_printf (pp, "origin" ); |
115 | if (f.m_newlines) |
116 | pp_newline (pp); |
117 | break; |
118 | |
119 | case PK_BEFORE_SUPERNODE: |
120 | { |
121 | if (m_from_edge) |
122 | { |
123 | if (basic_block bb = m_from_edge->m_src->m_bb) |
124 | pp_printf (pp, "before SN: %i (from SN: %i (bb: %i))" , |
125 | m_supernode->m_index, m_from_edge->m_src->m_index, |
126 | bb->index); |
127 | else |
128 | pp_printf (pp, "before SN: %i (from SN: %i)" , |
129 | m_supernode->m_index, m_from_edge->m_src->m_index); |
130 | } |
131 | else |
132 | pp_printf (pp, "before SN: %i (NULL from-edge)" , |
133 | m_supernode->m_index); |
134 | f.spacer (pp); |
135 | for (gphi_iterator gpi |
136 | = const_cast<supernode *>(get_supernode ())->start_phis (); |
137 | !gsi_end_p (i: gpi); gsi_next (i: &gpi)) |
138 | { |
139 | const gphi *phi = gpi.phi (); |
140 | pp_gimple_stmt_1 (pp, phi, 0, (dump_flags_t)0); |
141 | } |
142 | } |
143 | break; |
144 | |
145 | case PK_BEFORE_STMT: |
146 | pp_printf (pp, "before (SN: %i stmt: %i): " , m_supernode->m_index, |
147 | m_stmt_idx); |
148 | f.spacer (pp); |
149 | pp_gimple_stmt_1 (pp, get_stmt (), 0, (dump_flags_t)0); |
150 | if (f.m_newlines) |
151 | { |
152 | pp_newline (pp); |
153 | print_source_line (pp); |
154 | } |
155 | break; |
156 | |
157 | case PK_AFTER_SUPERNODE: |
158 | pp_printf (pp, "after SN: %i" , m_supernode->m_index); |
159 | if (f.m_newlines) |
160 | pp_newline (pp); |
161 | break; |
162 | } |
163 | } |
164 | |
165 | /* Generate a hash value for this function_point. */ |
166 | |
167 | hashval_t |
168 | function_point::hash () const |
169 | { |
170 | inchash::hash hstate; |
171 | if (m_supernode) |
172 | hstate.add_int (v: m_supernode->m_index); |
173 | hstate.add_ptr (ptr: m_from_edge); |
174 | hstate.add_int (v: m_stmt_idx); |
175 | hstate.add_int (v: m_kind); |
176 | return hstate.end (); |
177 | } |
178 | |
179 | /* Get the function at this point, if any. */ |
180 | |
181 | function * |
182 | function_point::get_function () const |
183 | { |
184 | if (m_supernode) |
185 | 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 | function_point::get_stmt () const |
194 | { |
195 | if (m_kind == PK_BEFORE_STMT) |
196 | return m_supernode->m_stmts[m_stmt_idx]; |
197 | else if (m_kind == PK_AFTER_SUPERNODE) |
198 | 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 | function_point::get_location () const |
207 | { |
208 | const gimple *stmt = get_stmt (); |
209 | if (stmt) |
210 | return stmt->location; |
211 | if (m_kind == PK_BEFORE_SUPERNODE) |
212 | return m_supernode->get_start_location (); |
213 | else if (m_kind == PK_AFTER_SUPERNODE) |
214 | 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 | function_point::final_stmt_p () const |
224 | { |
225 | if (m_kind != PK_BEFORE_STMT) |
226 | return false; |
227 | 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 | function_point::from_function_entry (const supergraph &sg, const function &fun) |
234 | { |
235 | return before_supernode (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 | function_point::before_supernode (const supernode *supernode, |
243 | const superedge *from_edge) |
244 | { |
245 | if (from_edge && from_edge->get_kind () != SUPEREDGE_CFG_EDGE) |
246 | from_edge = NULL; |
247 | 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 | debug_diagnostic_context () |
257 | { |
258 | diagnostic_initialize (context: this, n_opts: 0); |
259 | m_source_printing.show_line_numbers_p = true; |
260 | m_source_printing.enabled = true; |
261 | } |
262 | ~debug_diagnostic_context () |
263 | { |
264 | diagnostic_finish (context: this); |
265 | } |
266 | }; |
267 | |
268 | /* Print the source line (if any) for this function_point to PP. */ |
269 | |
270 | void |
271 | function_point::print_source_line (pretty_printer *pp) const |
272 | { |
273 | const gimple *stmt = get_stmt (); |
274 | if (!stmt) |
275 | return; |
276 | // TODO: monospace font |
277 | debug_diagnostic_context tmp_dc; |
278 | gcc_rich_location richloc (stmt->location); |
279 | diagnostic_show_locus (context: &tmp_dc, richloc: &richloc, diagnostic_kind: DK_ERROR); |
280 | pp_string (pp, pp_formatted_text (tmp_dc.printer)); |
281 | } |
282 | |
283 | /* class program_point. */ |
284 | |
285 | /* Print this program_point to PP. */ |
286 | |
287 | void |
288 | program_point::print (pretty_printer *pp, const format &f) const |
289 | { |
290 | pp_string (pp, "callstring: " ); |
291 | m_call_string->print (pp); |
292 | f.spacer (pp); |
293 | |
294 | m_function_point.print (pp, f); |
295 | } |
296 | |
297 | /* Dump this point to stderr. */ |
298 | |
299 | DEBUG_FUNCTION void |
300 | program_point::dump () const |
301 | { |
302 | pretty_printer pp; |
303 | pp_show_color (&pp) = pp_show_color (global_dc->printer); |
304 | pp.buffer->stream = stderr; |
305 | print (pp: &pp, f: format (true)); |
306 | pp_flush (&pp); |
307 | } |
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 | program_point::to_json () const |
318 | { |
319 | json::object *point_obj = new json::object (); |
320 | |
321 | point_obj->set (key: "kind" , |
322 | v: new json::string (point_kind_to_string (pk: get_kind ()))); |
323 | |
324 | if (get_supernode ()) |
325 | point_obj->set (key: "snode_idx" , |
326 | v: new json::integer_number (get_supernode ()->m_index)); |
327 | |
328 | switch (get_kind ()) |
329 | { |
330 | default: break; |
331 | case PK_BEFORE_SUPERNODE: |
332 | if (const superedge *sedge = get_from_edge ()) |
333 | point_obj->set (key: "from_edge_snode_idx" , |
334 | v: new json::integer_number (sedge->m_src->m_index)); |
335 | break; |
336 | case PK_BEFORE_STMT: |
337 | point_obj->set (key: "stmt_idx" , v: new json::integer_number (get_stmt_idx ())); |
338 | break; |
339 | } |
340 | |
341 | point_obj->set (key: "call_string" , v: m_call_string->to_json ()); |
342 | |
343 | 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 | program_point::push_to_call_stack (const supernode *caller, |
352 | const supernode *callee) |
353 | { |
354 | m_call_string = m_call_string->push_call (src: callee, dest: caller); |
355 | } |
356 | |
357 | /* Pop the topmost call from the current callstack. */ |
358 | void |
359 | program_point::pop_from_call_stack () |
360 | { |
361 | m_call_string = m_call_string->get_parent (); |
362 | gcc_assert (m_call_string); |
363 | } |
364 | |
365 | /* Generate a hash value for this program_point. */ |
366 | |
367 | hashval_t |
368 | program_point::hash () const |
369 | { |
370 | inchash::hash hstate; |
371 | hstate.merge_hash (other: m_function_point.hash ()); |
372 | hstate.add_ptr (ptr: m_call_string); |
373 | return hstate.end (); |
374 | } |
375 | |
376 | /* Get the function * at DEPTH within the call stack. */ |
377 | |
378 | function * |
379 | program_point::get_function_at_depth (unsigned depth) const |
380 | { |
381 | gcc_assert (depth <= m_call_string->length ()); |
382 | if (depth == m_call_string->length ()) |
383 | return m_function_point.get_function (); |
384 | else |
385 | return get_call_string ()[depth].get_caller_function (); |
386 | } |
387 | |
388 | /* Assert that this object is sane. */ |
389 | |
390 | void |
391 | program_point::validate () const |
392 | { |
393 | /* Skip this in a release build. */ |
394 | #if !CHECKING_P |
395 | return; |
396 | #endif |
397 | |
398 | 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 | if (m_call_string->length () > 0) |
402 | gcc_assert |
403 | ((*m_call_string)[m_call_string->length () - 1].get_callee_function () |
404 | == get_function ()); |
405 | } |
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 | program_point::on_edge (exploded_graph &eg, |
419 | const superedge *succ) |
420 | { |
421 | logger * const logger = eg.get_logger (); |
422 | LOG_FUNC (logger); |
423 | switch (succ->m_kind) |
424 | { |
425 | case SUPEREDGE_CFG_EDGE: |
426 | { |
427 | const cfg_superedge *cfg_sedge = as_a <const cfg_superedge *> (p: succ); |
428 | |
429 | if (cfg_sedge->get_flags () & EDGE_ABNORMAL) |
430 | { |
431 | const supernode *src_snode = cfg_sedge->m_src; |
432 | if (gimple *last_stmt = src_snode->get_last_stmt ()) |
433 | 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 | case SUPEREDGE_CALL: |
449 | { |
450 | const call_superedge *call_sedge = as_a <const call_superedge *> (p: succ); |
451 | |
452 | if (eg.get_analysis_plan ().use_summary_p (edge: call_sedge->m_cedge)) |
453 | { |
454 | if (logger) |
455 | logger->log (fmt: "rejecting call edge: using summary instead" ); |
456 | return false; |
457 | } |
458 | |
459 | /* Add the callsite to the call string. */ |
460 | m_call_string = m_call_string->push_call (sg: eg.get_supergraph (), |
461 | sedge: 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 | if (m_call_string->calc_recursion_depth () |
469 | > param_analyzer_max_recursion_depth) |
470 | { |
471 | if (logger) |
472 | logger->log (fmt: "rejecting call edge: recursion limit exceeded" ); |
473 | // TODO: issue a sorry for this? |
474 | return false; |
475 | } |
476 | } |
477 | break; |
478 | |
479 | case SUPEREDGE_RETURN: |
480 | { |
481 | /* Require that we return to the call site in the call string. */ |
482 | if (m_call_string->empty_p ()) |
483 | { |
484 | if (logger) |
485 | logger->log (fmt: "rejecting return edge: empty call string" ); |
486 | return false; |
487 | } |
488 | const call_string::element_t &top_of_stack |
489 | = m_call_string->get_top_of_stack (); |
490 | m_call_string = m_call_string->get_parent (); |
491 | call_string::element_t current_call_string_element (succ->m_dest, |
492 | succ->m_src); |
493 | if (top_of_stack != current_call_string_element) |
494 | { |
495 | if (logger) |
496 | logger->log (fmt: "rejecting return edge: return to wrong callsite" ); |
497 | return false; |
498 | } |
499 | } |
500 | break; |
501 | |
502 | case SUPEREDGE_INTRAPROCEDURAL_CALL: |
503 | { |
504 | const callgraph_superedge *cg_sedge |
505 | = as_a <const callgraph_superedge *> (p: succ); |
506 | /* Consider turning this edge into a use of an |
507 | interprocedural summary. */ |
508 | if (eg.get_analysis_plan ().use_summary_p (edge: cg_sedge->m_cedge)) |
509 | { |
510 | if (logger) |
511 | logger->log (fmt: "using function summary for %qE in %qE" , |
512 | cg_sedge->get_callee_decl (), |
513 | cg_sedge->get_caller_decl ()); |
514 | return true; |
515 | } |
516 | else |
517 | { |
518 | /* Otherwise, we ignore these edges */ |
519 | if (logger) |
520 | logger->log (fmt: "rejecting interprocedural edge" ); |
521 | return false; |
522 | } |
523 | } |
524 | } |
525 | |
526 | return true; |
527 | } |
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 | function_point::cmp_within_supernode_1 (const function_point &point_a, |
537 | const function_point &point_b) |
538 | { |
539 | gcc_assert (point_a.get_supernode () == point_b.get_supernode ()); |
540 | |
541 | switch (point_a.m_kind) |
542 | { |
543 | default: |
544 | gcc_unreachable (); |
545 | case PK_BEFORE_SUPERNODE: |
546 | switch (point_b.m_kind) |
547 | { |
548 | default: |
549 | gcc_unreachable (); |
550 | case PK_BEFORE_SUPERNODE: |
551 | { |
552 | int a_src_idx = -1; |
553 | int b_src_idx = -1; |
554 | if (point_a.m_from_edge) |
555 | a_src_idx = point_a.m_from_edge->m_src->m_index; |
556 | if (point_b.m_from_edge) |
557 | b_src_idx = point_b.m_from_edge->m_src->m_index; |
558 | 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 | break; |
567 | case PK_BEFORE_STMT: |
568 | switch (point_b.m_kind) |
569 | { |
570 | default: |
571 | gcc_unreachable (); |
572 | case PK_BEFORE_SUPERNODE: |
573 | return 1; |
574 | |
575 | case PK_BEFORE_STMT: |
576 | return point_a.m_stmt_idx - point_b.m_stmt_idx; |
577 | |
578 | case PK_AFTER_SUPERNODE: |
579 | return -1; |
580 | } |
581 | break; |
582 | case PK_AFTER_SUPERNODE: |
583 | switch (point_b.m_kind) |
584 | { |
585 | default: |
586 | 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 | function_point::cmp_within_supernode (const function_point &point_a, |
606 | const function_point &point_b) |
607 | { |
608 | int result = cmp_within_supernode_1 (point_a, point_b); |
609 | |
610 | /* Check that the ordering is symmetric */ |
611 | #if CHECKING_P |
612 | int reversed = cmp_within_supernode_1 (point_a: point_b, point_b: point_a); |
613 | gcc_assert (reversed == -result); |
614 | #endif |
615 | |
616 | return result; |
617 | } |
618 | |
619 | /* Comparator for imposing an order on function_points. */ |
620 | |
621 | int |
622 | function_point::cmp (const function_point &point_a, |
623 | const function_point &point_b) |
624 | { |
625 | int idx_a = point_a.m_supernode ? point_a.m_supernode->m_index : -1; |
626 | int idx_b = point_b.m_supernode ? point_b.m_supernode->m_index : -1; |
627 | if (int cmp_idx = idx_a - idx_b) |
628 | return cmp_idx; |
629 | gcc_assert (point_a.m_supernode == point_b.m_supernode); |
630 | if (point_a.m_supernode) |
631 | 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 | function_point::cmp_ptr (const void *p1, const void *p2) |
640 | { |
641 | const function_point *fp1 = (const function_point *)p1; |
642 | const function_point *fp2 = (const function_point *)p2; |
643 | return cmp (point_a: *fp1, point_b: *fp2); |
644 | } |
645 | |
646 | /* For PK_BEFORE_STMT, go to next stmt (or to PK_AFTER_SUPERNODE). */ |
647 | |
648 | void |
649 | function_point::next_stmt () |
650 | { |
651 | gcc_assert (m_kind == PK_BEFORE_STMT); |
652 | if (++m_stmt_idx == m_supernode->m_stmts.length ()) |
653 | { |
654 | m_kind = PK_AFTER_SUPERNODE; |
655 | m_stmt_idx = 0; |
656 | } |
657 | } |
658 | |
659 | /* For those function points for which there is a uniquely-defined |
660 | successor, return it. */ |
661 | |
662 | function_point |
663 | function_point::get_next () const |
664 | { |
665 | switch (get_kind ()) |
666 | { |
667 | default: |
668 | gcc_unreachable (); |
669 | case PK_ORIGIN: |
670 | case PK_AFTER_SUPERNODE: |
671 | gcc_unreachable (); /* Not uniquely defined. */ |
672 | case PK_BEFORE_SUPERNODE: |
673 | if (get_supernode ()->m_stmts.length () > 0) |
674 | return before_stmt (supernode: get_supernode (), stmt_idx: 0); |
675 | else |
676 | return after_supernode (supernode: get_supernode ()); |
677 | case PK_BEFORE_STMT: |
678 | { |
679 | unsigned next_idx = get_stmt_idx () + 1; |
680 | if (next_idx < get_supernode ()->m_stmts.length ()) |
681 | return before_stmt (supernode: get_supernode (), stmt_idx: next_idx); |
682 | else |
683 | return after_supernode (supernode: get_supernode ()); |
684 | } |
685 | } |
686 | } |
687 | |
688 | /* class program_point. */ |
689 | |
690 | program_point |
691 | program_point::origin (const region_model_manager &mgr) |
692 | { |
693 | return program_point (function_point (NULL, NULL, |
694 | 0, PK_ORIGIN), |
695 | mgr.get_empty_call_string ()); |
696 | } |
697 | |
698 | program_point |
699 | program_point::from_function_entry (const region_model_manager &mgr, |
700 | const supergraph &sg, |
701 | const function &fun) |
702 | { |
703 | return program_point (function_point::from_function_entry (sg, fun), |
704 | 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 | program_point::get_next () const |
712 | { |
713 | switch (m_function_point.get_kind ()) |
714 | { |
715 | default: |
716 | gcc_unreachable (); |
717 | case PK_ORIGIN: |
718 | case PK_AFTER_SUPERNODE: |
719 | gcc_unreachable (); /* Not uniquely defined. */ |
720 | case PK_BEFORE_SUPERNODE: |
721 | if (get_supernode ()->m_stmts.length () > 0) |
722 | return before_stmt (supernode: get_supernode (), stmt_idx: 0, call_string: get_call_string ()); |
723 | else |
724 | return after_supernode (supernode: get_supernode (), call_string: get_call_string ()); |
725 | case PK_BEFORE_STMT: |
726 | { |
727 | unsigned next_idx = get_stmt_idx () + 1; |
728 | if (next_idx < get_supernode ()->m_stmts.length ()) |
729 | return before_stmt (supernode: get_supernode (), stmt_idx: next_idx, call_string: get_call_string ()); |
730 | else |
731 | return after_supernode (supernode: get_supernode (), call_string: 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 | 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 | if (point_a.get_function () |
746 | != point_b.get_function ()) |
747 | return false; |
748 | if (&point_a.get_call_string () |
749 | != &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 | location_t loc_a = point_a.get_location (); |
755 | location_t loc_b = point_b.get_location (); |
756 | inlining_iterator iter_a (loc_a); |
757 | inlining_iterator iter_b (loc_b); |
758 | while (!(iter_a.done_p () || iter_b.done_p ())) |
759 | { |
760 | if (iter_a.done_p () || iter_b.done_p ()) |
761 | return false; |
762 | |
763 | if (iter_a.get_fndecl () != iter_b.get_fndecl ()) |
764 | return false; |
765 | if (iter_a.get_callsite () != iter_b.get_callsite ()) |
766 | return false; |
767 | if (iter_a.get_block () != iter_b.get_block ()) |
768 | return false; |
769 | |
770 | iter_a.next (); |
771 | 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 | test_function_point_equality () |
785 | { |
786 | const supernode *snode = NULL; |
787 | |
788 | function_point a = function_point (snode, NULL, 0, |
789 | PK_BEFORE_SUPERNODE); |
790 | function_point b = function_point::before_supernode (supernode: snode, NULL); |
791 | ASSERT_EQ (a, b); |
792 | } |
793 | |
794 | /* Verify that function_point::cmp_within_supernode works as expected. */ |
795 | |
796 | static void |
797 | test_function_point_ordering () |
798 | { |
799 | const supernode *snode = NULL; |
800 | |
801 | /* Populate an array with various points within the same |
802 | snode, in order. */ |
803 | auto_vec<function_point> points; |
804 | points.safe_push (obj: function_point::before_supernode (supernode: snode, NULL)); |
805 | points.safe_push (obj: function_point::before_stmt (supernode: snode, stmt_idx: 0)); |
806 | points.safe_push (obj: function_point::before_stmt (supernode: snode, stmt_idx: 1)); |
807 | points.safe_push (obj: function_point::after_supernode (supernode: snode)); |
808 | |
809 | /* Check all pairs. */ |
810 | unsigned i; |
811 | function_point *point_a; |
812 | FOR_EACH_VEC_ELT (points, i, point_a) |
813 | { |
814 | unsigned j; |
815 | function_point *point_b; |
816 | FOR_EACH_VEC_ELT (points, j, point_b) |
817 | { |
818 | int cmp = function_point::cmp_within_supernode (point_a: *point_a, point_b: *point_b); |
819 | if (i == j) |
820 | ASSERT_EQ (cmp, 0); |
821 | if (i < j) |
822 | ASSERT_TRUE (cmp < 0); |
823 | if (i > j) |
824 | ASSERT_TRUE (cmp > 0); |
825 | } |
826 | } |
827 | } |
828 | |
829 | /* Verify that program_point::operator== works as expected. */ |
830 | |
831 | static void |
832 | test_program_point_equality () |
833 | { |
834 | region_model_manager mgr; |
835 | |
836 | const supernode *snode = NULL; |
837 | |
838 | const call_string &cs = mgr.get_empty_call_string (); |
839 | |
840 | program_point a = program_point::before_supernode (supernode: snode, NULL, |
841 | call_string: cs); |
842 | |
843 | program_point b = program_point::before_supernode (supernode: snode, NULL, |
844 | call_string: cs); |
845 | |
846 | ASSERT_EQ (a, b); |
847 | // TODO: verify with non-empty callstrings, with different edges |
848 | } |
849 | |
850 | /* Run all of the selftests within this file. */ |
851 | |
852 | void |
853 | analyzer_program_point_cc_tests () |
854 | { |
855 | test_function_point_equality (); |
856 | test_function_point_ordering (); |
857 | test_program_point_equality (); |
858 | } |
859 | |
860 | } // namespace selftest |
861 | |
862 | #endif /* CHECKING_P */ |
863 | |
864 | } // namespace ana |
865 | |
866 | #endif /* #if ENABLE_ANALYZER */ |
867 | |