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