]>
Commit | Line | Data |
---|---|---|
757bf1df DM |
1 | /* The analysis "engine". |
2 | Copyright (C) 2019-2020 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 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tree.h" | |
25 | #include "fold-const.h" | |
26 | #include "gcc-rich-location.h" | |
27 | #include "alloc-pool.h" | |
28 | #include "fibonacci_heap.h" | |
29 | #include "shortest-paths.h" | |
30 | #include "diagnostic-core.h" | |
31 | #include "diagnostic-event-id.h" | |
32 | #include "diagnostic-path.h" | |
33 | #include "function.h" | |
34 | #include "pretty-print.h" | |
35 | #include "sbitmap.h" | |
36 | #include "tristate.h" | |
37 | #include "ordered-hash-map.h" | |
38 | #include "selftest.h" | |
39 | #include "analyzer/analyzer.h" | |
40 | #include "analyzer/analyzer-logging.h" | |
41 | #include "analyzer/region-model.h" | |
42 | #include "analyzer/constraint-manager.h" | |
43 | #include "analyzer/sm.h" | |
44 | #include "analyzer/pending-diagnostic.h" | |
45 | #include "analyzer/diagnostic-manager.h" | |
46 | #include "cfg.h" | |
47 | #include "basic-block.h" | |
48 | #include "gimple.h" | |
49 | #include "gimple-iterator.h" | |
50 | #include "cgraph.h" | |
51 | #include "digraph.h" | |
52 | #include "analyzer/supergraph.h" | |
53 | #include "analyzer/call-string.h" | |
54 | #include "analyzer/program-point.h" | |
55 | #include "analyzer/program-state.h" | |
56 | #include "analyzer/exploded-graph.h" | |
57 | #include "analyzer/analysis-plan.h" | |
58 | #include "analyzer/checker-path.h" | |
59 | #include "analyzer/state-purge.h" | |
60 | ||
61 | /* For an overview, see gcc/doc/analyzer.texi. */ | |
62 | ||
63 | #if ENABLE_ANALYZER | |
64 | ||
75038aa6 DM |
65 | namespace ana { |
66 | ||
757bf1df DM |
67 | static int readability_comparator (const void *p1, const void *p2); |
68 | ||
49e9a999 | 69 | /* class impl_region_model_context : public region_model_context. */ |
757bf1df DM |
70 | |
71 | impl_region_model_context:: | |
72 | impl_region_model_context (exploded_graph &eg, | |
73 | const exploded_node *enode_for_diag, | |
74 | const program_state *old_state, | |
75 | program_state *new_state, | |
76 | state_change *change, | |
77 | const gimple *stmt, | |
78 | stmt_finder *stmt_finder) | |
79 | : m_eg (&eg), m_logger (eg.get_logger ()), | |
80 | m_enode_for_diag (enode_for_diag), | |
81 | m_old_state (old_state), | |
82 | m_new_state (new_state), | |
83 | m_change (change), | |
84 | m_stmt (stmt), | |
85 | m_stmt_finder (stmt_finder), | |
86 | m_ext_state (eg.get_ext_state ()) | |
87 | { | |
88 | } | |
89 | ||
90 | impl_region_model_context:: | |
91 | impl_region_model_context (program_state *state, | |
92 | state_change *change, | |
93 | const extrinsic_state &ext_state) | |
94 | : m_eg (NULL), m_logger (NULL), m_enode_for_diag (NULL), | |
95 | m_old_state (NULL), | |
96 | m_new_state (state), | |
97 | m_change (change), | |
98 | m_stmt (NULL), | |
99 | m_stmt_finder (NULL), | |
100 | m_ext_state (ext_state) | |
101 | { | |
102 | } | |
103 | ||
104 | void | |
105 | impl_region_model_context::warn (pending_diagnostic *d) | |
106 | { | |
107 | LOG_FUNC (get_logger ()); | |
108 | if (m_eg) | |
109 | m_eg->get_diagnostic_manager ().add_diagnostic | |
110 | (m_enode_for_diag, m_enode_for_diag->get_supernode (), | |
111 | m_stmt, m_stmt_finder, d); | |
112 | } | |
113 | ||
114 | void | |
115 | impl_region_model_context::remap_svalue_ids (const svalue_id_map &map) | |
116 | { | |
117 | m_new_state->remap_svalue_ids (map); | |
118 | if (m_change) | |
119 | m_change->remap_svalue_ids (map); | |
120 | } | |
121 | ||
122 | int | |
123 | impl_region_model_context::on_svalue_purge (svalue_id first_unused_sid, | |
124 | const svalue_id_map &map) | |
125 | { | |
126 | int total = 0; | |
127 | int sm_idx; | |
128 | sm_state_map *smap; | |
129 | FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap) | |
130 | { | |
131 | const state_machine &sm = m_ext_state.get_sm (sm_idx); | |
132 | total += smap->on_svalue_purge (sm, sm_idx, first_unused_sid, | |
133 | map, this); | |
134 | } | |
135 | if (m_change) | |
136 | total += m_change->on_svalue_purge (first_unused_sid); | |
137 | return total; | |
138 | } | |
139 | ||
ef7827b0 DM |
140 | void |
141 | impl_region_model_context::on_unknown_change (svalue_id sid) | |
142 | { | |
143 | int sm_idx; | |
144 | sm_state_map *smap; | |
145 | FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap) | |
146 | smap->on_unknown_change (sid); | |
147 | } | |
148 | ||
757bf1df DM |
149 | /* class setjmp_svalue : public svalue. */ |
150 | ||
151 | /* Compare the fields of this setjmp_svalue with OTHER, returning true | |
152 | if they are equal. | |
153 | For use by svalue::operator==. */ | |
154 | ||
155 | bool | |
156 | setjmp_svalue::compare_fields (const setjmp_svalue &other) const | |
157 | { | |
fd9982bb | 158 | return m_setjmp_record == other.m_setjmp_record; |
757bf1df DM |
159 | } |
160 | ||
161 | /* Implementation of svalue::add_to_hash vfunc for setjmp_svalue. */ | |
162 | ||
163 | void | |
164 | setjmp_svalue::add_to_hash (inchash::hash &hstate) const | |
165 | { | |
fd9982bb | 166 | hstate.add_int (m_setjmp_record.m_enode->m_index); |
757bf1df DM |
167 | } |
168 | ||
169 | /* Get the index of the stored exploded_node. */ | |
170 | ||
171 | int | |
fd9982bb | 172 | setjmp_svalue::get_enode_index () const |
757bf1df | 173 | { |
fd9982bb | 174 | return m_setjmp_record.m_enode->m_index; |
757bf1df DM |
175 | } |
176 | ||
177 | /* Implementation of svalue::print_details vfunc for setjmp_svalue. */ | |
178 | ||
179 | void | |
180 | setjmp_svalue::print_details (const region_model &model ATTRIBUTE_UNUSED, | |
181 | svalue_id this_sid ATTRIBUTE_UNUSED, | |
182 | pretty_printer *pp) const | |
183 | { | |
fd9982bb | 184 | pp_printf (pp, "setjmp: EN: %i", get_enode_index ()); |
757bf1df DM |
185 | } |
186 | ||
187 | /* Concrete implementation of sm_context, wiring it up to the rest of this | |
188 | file. */ | |
189 | ||
190 | class impl_sm_context : public sm_context | |
191 | { | |
192 | public: | |
193 | impl_sm_context (exploded_graph &eg, | |
194 | int sm_idx, | |
195 | const state_machine &sm, | |
196 | const exploded_node *enode_for_diag, | |
197 | const program_state *old_state, | |
198 | program_state *new_state, | |
199 | state_change *change, | |
200 | const sm_state_map *old_smap, | |
201 | sm_state_map *new_smap, | |
202 | stmt_finder *stmt_finder = NULL) | |
203 | : sm_context (sm_idx, sm), | |
204 | m_logger (eg.get_logger ()), | |
205 | m_eg (eg), m_enode_for_diag (enode_for_diag), | |
206 | m_old_state (old_state), m_new_state (new_state), | |
207 | m_change (change), | |
208 | m_old_smap (old_smap), m_new_smap (new_smap), | |
209 | m_stmt_finder (stmt_finder) | |
210 | { | |
211 | } | |
212 | ||
213 | logger *get_logger () const { return m_logger.get_logger (); } | |
214 | ||
215 | tree get_fndecl_for_call (const gcall *call) FINAL OVERRIDE | |
216 | { | |
217 | impl_region_model_context old_ctxt | |
218 | (m_eg, m_enode_for_diag, NULL, NULL/*m_enode->get_state ()*/, | |
219 | m_change, call); | |
220 | region_model *model = m_new_state->m_region_model; | |
221 | return model->get_fndecl_for_call (call, &old_ctxt); | |
222 | } | |
223 | ||
224 | void on_transition (const supernode *node ATTRIBUTE_UNUSED, | |
225 | const gimple *stmt ATTRIBUTE_UNUSED, | |
226 | tree var, | |
227 | state_machine::state_t from, | |
228 | state_machine::state_t to, | |
229 | tree origin) FINAL OVERRIDE | |
230 | { | |
231 | logger * const logger = get_logger (); | |
232 | LOG_FUNC (logger); | |
233 | impl_region_model_context old_ctxt | |
234 | (m_eg, m_enode_for_diag, NULL, NULL/*m_enode->get_state ()*/, | |
235 | m_change, stmt); | |
236 | svalue_id var_old_sid | |
237 | = m_old_state->m_region_model->get_rvalue (var, &old_ctxt); | |
238 | ||
239 | impl_region_model_context new_ctxt (m_eg, m_enode_for_diag, | |
240 | m_old_state, m_new_state, | |
241 | m_change, NULL); | |
242 | svalue_id var_new_sid | |
243 | = m_new_state->m_region_model->get_rvalue (var, &new_ctxt); | |
244 | svalue_id origin_new_sid | |
245 | = m_new_state->m_region_model->get_rvalue (origin, &new_ctxt); | |
246 | ||
247 | state_machine::state_t current = m_old_smap->get_state (var_old_sid); | |
248 | if (current == from) | |
249 | { | |
250 | if (logger) | |
251 | logger->log ("%s: state transition of %qE: %s -> %s", | |
252 | m_sm.get_name (), | |
253 | var, | |
254 | m_sm.get_state_name (from), | |
255 | m_sm.get_state_name (to)); | |
256 | m_new_smap->set_state (m_new_state->m_region_model, var_new_sid, | |
257 | to, origin_new_sid); | |
258 | if (m_change) | |
259 | m_change->add_sm_change (m_sm_idx, var_new_sid, from, to); | |
260 | } | |
261 | } | |
262 | ||
263 | void warn_for_state (const supernode *snode, const gimple *stmt, | |
264 | tree var, state_machine::state_t state, | |
265 | pending_diagnostic *d) FINAL OVERRIDE | |
266 | { | |
267 | LOG_FUNC (get_logger ()); | |
268 | gcc_assert (d); // take ownership | |
269 | ||
270 | impl_region_model_context old_ctxt | |
271 | (m_eg, m_enode_for_diag, m_old_state, m_new_state, m_change, NULL); | |
272 | state_machine::state_t current; | |
273 | if (var) | |
274 | { | |
275 | svalue_id var_old_sid | |
276 | = m_old_state->m_region_model->get_rvalue (var, &old_ctxt); | |
277 | current = m_old_smap->get_state (var_old_sid); | |
278 | } | |
279 | else | |
280 | current = m_old_smap->get_global_state (); | |
281 | ||
282 | if (state == current) | |
283 | { | |
284 | m_eg.get_diagnostic_manager ().add_diagnostic | |
285 | (&m_sm, m_enode_for_diag, snode, stmt, m_stmt_finder, | |
286 | var, state, d); | |
287 | } | |
288 | else | |
289 | delete d; | |
290 | } | |
291 | ||
292 | /* Hook for picking more readable trees for SSA names of temporaries, | |
293 | so that rather than e.g. | |
294 | "double-free of '<unknown>'" | |
295 | we can print: | |
296 | "double-free of 'inbuf.data'". */ | |
297 | ||
298 | tree get_readable_tree (tree expr) FINAL OVERRIDE | |
299 | { | |
300 | /* Only for SSA_NAMEs of temporaries; otherwise, return EXPR, as it's | |
301 | likely to be the least surprising tree to report. */ | |
302 | if (TREE_CODE (expr) != SSA_NAME) | |
303 | return expr; | |
304 | if (SSA_NAME_VAR (expr) != NULL) | |
305 | return expr; | |
306 | ||
307 | gcc_assert (m_new_state); | |
308 | svalue_id sid = m_new_state->m_region_model->get_rvalue (expr, NULL); | |
309 | /* Find trees for all regions storing the value. */ | |
310 | auto_vec<path_var> pvs; | |
311 | m_new_state->m_region_model->get_path_vars_for_svalue (sid, &pvs); | |
312 | if (pvs.length () < 1) | |
313 | return expr; | |
314 | /* Pick the "best" such tree. */ | |
315 | // TODO: should we also consider (and consolidate) equiv classes? | |
316 | pvs.qsort (readability_comparator); | |
317 | return pvs[0].m_tree; | |
318 | } | |
319 | ||
320 | state_machine::state_t get_global_state () const FINAL OVERRIDE | |
321 | { | |
322 | return m_old_state->m_checker_states[m_sm_idx]->get_global_state (); | |
323 | } | |
324 | ||
325 | void set_global_state (state_machine::state_t state) FINAL OVERRIDE | |
326 | { | |
327 | m_new_state->m_checker_states[m_sm_idx]->set_global_state (state); | |
328 | } | |
329 | ||
330 | void on_custom_transition (custom_transition *transition) FINAL OVERRIDE | |
331 | { | |
332 | transition->impl_transition (&m_eg, | |
333 | const_cast<exploded_node *> (m_enode_for_diag), | |
334 | m_sm_idx); | |
335 | } | |
336 | ||
337 | log_user m_logger; | |
338 | exploded_graph &m_eg; | |
339 | const exploded_node *m_enode_for_diag; | |
340 | const program_state *m_old_state; | |
341 | program_state *m_new_state; | |
342 | state_change *m_change; | |
343 | const sm_state_map *m_old_smap; | |
344 | sm_state_map *m_new_smap; | |
345 | stmt_finder *m_stmt_finder; | |
346 | }; | |
347 | ||
348 | /* Subclass of stmt_finder for finding the best stmt to report the leak at, | |
349 | given the emission path. */ | |
350 | ||
351 | class leak_stmt_finder : public stmt_finder | |
352 | { | |
353 | public: | |
354 | leak_stmt_finder (const exploded_graph &eg, tree var) | |
355 | : m_eg (eg), m_var (var) {} | |
356 | ||
357 | stmt_finder *clone () const FINAL OVERRIDE | |
358 | { | |
359 | return new leak_stmt_finder (m_eg, m_var); | |
360 | } | |
361 | ||
362 | const gimple *find_stmt (const exploded_path &epath) | |
363 | FINAL OVERRIDE | |
364 | { | |
365 | logger * const logger = m_eg.get_logger (); | |
366 | LOG_FUNC (logger); | |
367 | ||
368 | if (TREE_CODE (m_var) == SSA_NAME) | |
369 | { | |
370 | /* Locate the final write to this SSA name in the path. */ | |
371 | const gimple *def_stmt = SSA_NAME_DEF_STMT (m_var); | |
372 | ||
373 | int idx_of_def_stmt; | |
374 | bool found = epath.find_stmt_backwards (def_stmt, &idx_of_def_stmt); | |
375 | if (!found) | |
376 | goto not_found; | |
377 | ||
378 | /* What was the next write to the underlying var | |
379 | after the SSA name was set? (if any). */ | |
380 | ||
381 | for (unsigned idx = idx_of_def_stmt + 1; | |
382 | idx < epath.m_edges.length (); | |
383 | ++idx) | |
384 | { | |
385 | const exploded_edge *eedge = epath.m_edges[idx]; | |
386 | if (logger) | |
387 | logger->log ("eedge[%i]: EN %i -> EN %i", | |
388 | idx, | |
389 | eedge->m_src->m_index, | |
390 | eedge->m_dest->m_index); | |
391 | const exploded_node *dst_node = eedge->m_dest; | |
392 | const program_point &dst_point = dst_node->get_point (); | |
393 | const gimple *stmt = dst_point.get_stmt (); | |
394 | if (!stmt) | |
395 | continue; | |
396 | if (const gassign *assign = dyn_cast <const gassign *> (stmt)) | |
397 | { | |
398 | tree lhs = gimple_assign_lhs (assign); | |
399 | if (TREE_CODE (lhs) == SSA_NAME | |
400 | && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (m_var)) | |
401 | return assign; | |
402 | } | |
403 | } | |
404 | } | |
405 | ||
406 | not_found: | |
407 | ||
408 | /* Look backwards for the first statement with a location. */ | |
409 | int i; | |
410 | const exploded_edge *eedge; | |
411 | FOR_EACH_VEC_ELT_REVERSE (epath.m_edges, i, eedge) | |
412 | { | |
413 | if (logger) | |
414 | logger->log ("eedge[%i]: EN %i -> EN %i", | |
415 | i, | |
416 | eedge->m_src->m_index, | |
417 | eedge->m_dest->m_index); | |
418 | const exploded_node *dst_node = eedge->m_dest; | |
419 | const program_point &dst_point = dst_node->get_point (); | |
420 | const gimple *stmt = dst_point.get_stmt (); | |
421 | if (stmt) | |
8397af8e | 422 | if (get_pure_location (stmt->location) != UNKNOWN_LOCATION) |
757bf1df DM |
423 | return stmt; |
424 | } | |
425 | ||
426 | gcc_unreachable (); | |
427 | return NULL; | |
428 | } | |
429 | ||
430 | private: | |
431 | const exploded_graph &m_eg; | |
432 | tree m_var; | |
433 | }; | |
434 | ||
435 | /* A measurement of how good EXPR is for presenting to the user, so | |
436 | that e.g. we can say prefer printing | |
437 | "leak of 'tmp.m_ptr'" | |
438 | over: | |
439 | "leak of '<unknown>'". */ | |
440 | ||
441 | static int | |
442 | readability (const_tree expr) | |
443 | { | |
444 | gcc_assert (expr); | |
445 | switch (TREE_CODE (expr)) | |
446 | { | |
447 | case COMPONENT_REF: | |
448 | case MEM_REF: | |
449 | /* Impose a slight readability penalty relative to that of | |
450 | operand 0. */ | |
451 | return readability (TREE_OPERAND (expr, 0)) - 1; | |
452 | ||
453 | case SSA_NAME: | |
454 | { | |
455 | if (tree var = SSA_NAME_VAR (expr)) | |
456 | return readability (var); | |
457 | /* Avoid printing '<unknown>' for SSA names for temporaries. */ | |
458 | return -1; | |
459 | } | |
460 | break; | |
461 | ||
462 | case VAR_DECL: | |
463 | /* Arbitrarily-chosen "high readability" value. */ | |
464 | return 256; | |
465 | ||
466 | default: | |
467 | return 0; | |
468 | } | |
469 | ||
470 | return 0; | |
471 | } | |
472 | ||
473 | /* A qsort comparator for trees to sort them into most user-readable to | |
474 | least user-readable. */ | |
475 | ||
476 | static int | |
477 | readability_comparator (const void *p1, const void *p2) | |
478 | { | |
479 | path_var pv1 = *(path_var const *)p1; | |
480 | path_var pv2 = *(path_var const *)p2; | |
481 | ||
482 | /* TODO: should we consider stack depths? */ | |
483 | int r1 = readability (pv1.m_tree); | |
484 | int r2 = readability (pv2.m_tree); | |
485 | ||
486 | return r2 - r1; | |
487 | } | |
488 | ||
489 | /* Create an sm_context and use it to call SM's on_leak vfunc, so that | |
490 | it can potentially complain about a leak of DST_SID (in a new region_model) | |
491 | in the given STATE, where MAP can be used to map SID back to an "old" | |
492 | region_model. */ | |
493 | ||
494 | void | |
495 | impl_region_model_context::on_state_leak (const state_machine &sm, | |
496 | int sm_idx, | |
497 | svalue_id dst_sid, | |
498 | svalue_id first_unused_sid, | |
499 | const svalue_id_map &map, | |
500 | state_machine::state_t state) | |
501 | { | |
502 | logger * const logger = get_logger (); | |
503 | LOG_SCOPE (logger); | |
504 | if (logger) | |
505 | logger->log ("considering leak of sv%i", dst_sid.as_int ()); | |
506 | ||
507 | if (!m_eg) | |
508 | return; | |
509 | ||
510 | /* m_old_state also needs to be non-NULL so that the sm_ctxt can look | |
511 | up the old state of the sid. */ | |
512 | gcc_assert (m_old_state); | |
513 | ||
514 | /* Don't report on sid leaking if it's equal to one of the used sids. | |
515 | For example, given: | |
516 | some_non_trivial_expression = malloc (sizeof (struct foo)); | |
517 | we have: | |
518 | _1 = malloc; (void *) | |
519 | some_non_trivial_expression = _1; (struct foo *) | |
520 | and at leak-detection time we may have: | |
521 | sv5: {type: 'struct foo *', &r3} (used) | |
522 | sv6: {type: 'void *', &r3} (unused) | |
523 | where both point to the same region. We don't want to report a | |
524 | leak of sv6, so we reject the report due to its equality with sv5. */ | |
525 | gcc_assert (m_new_state); | |
526 | gcc_assert (!first_unused_sid.null_p ()); | |
527 | for (int i = 0; i < first_unused_sid.as_int (); i++) | |
528 | { | |
529 | svalue_id used_sid = svalue_id::from_int (i); | |
530 | ||
531 | /* Use the "_without_cm" form of eval_condition, since | |
532 | we're half-way through purging - we don't want to introduce new | |
533 | equivalence classes into the constraint_manager for "sid" and | |
534 | for each of the used_sids. */ | |
535 | const region_model &rm = *m_new_state->m_region_model; | |
536 | tristate eq = rm.eval_condition_without_cm (dst_sid, EQ_EXPR, used_sid); | |
537 | if (eq.is_true ()) | |
538 | { | |
539 | if (logger) | |
540 | logger->log ("rejecting leak of sv%i due to equality with sv%i", | |
541 | dst_sid.as_int (), used_sid.as_int ()); | |
542 | return; | |
543 | } | |
544 | } | |
545 | ||
546 | /* SID has leaked within the new state: no regions use it. | |
547 | We need to convert it back to a tree, but since no regions use it, we | |
548 | have to use MAP to convert it back to an svalue_id within the old state. | |
549 | We can then look that svalue_id up to locate regions and thus tree(s) | |
550 | that use it. */ | |
551 | ||
552 | svalue_id old_sid = map.get_src_for_dst (dst_sid); | |
553 | ||
554 | auto_vec<path_var> leaked_pvs; | |
555 | m_old_state->m_region_model->get_path_vars_for_svalue (old_sid, &leaked_pvs); | |
556 | ||
557 | if (leaked_pvs.length () < 1) | |
558 | return; | |
559 | ||
560 | /* Find "best" leaked tree. | |
561 | Sort the leaks into most human-readable first, through | |
562 | to least user-readable. Given that we only emit one | |
563 | leak per EC, this ought to ensure that we pick the most | |
564 | user-readable description of each leaking EC. | |
565 | This assumes that all vars in the EC have the same state. */ | |
566 | leaked_pvs.qsort (readability_comparator); | |
567 | ||
568 | tree leaked_tree = leaked_pvs[0].m_tree; | |
569 | if (logger) | |
570 | logger->log ("best leaked_tree: %qE", leaked_tree); | |
571 | ||
572 | leak_stmt_finder stmt_finder (*m_eg, leaked_tree); | |
573 | impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag, | |
574 | m_old_state, m_new_state, | |
575 | m_change, | |
576 | m_old_state->m_checker_states[sm_idx], | |
577 | m_new_state->m_checker_states[sm_idx], | |
578 | &stmt_finder); | |
579 | gcc_assert (m_enode_for_diag); | |
580 | ||
581 | /* Don't complain about leaks when returning from "main". */ | |
582 | if (m_enode_for_diag->get_supernode () | |
583 | && m_enode_for_diag->get_supernode ()->return_p ()) | |
584 | { | |
585 | tree fndecl = m_enode_for_diag->get_function ()->decl; | |
586 | if (0 == strcmp (IDENTIFIER_POINTER (DECL_NAME (fndecl)), "main")) | |
587 | { | |
588 | if (logger) | |
589 | logger->log ("not reporting leak from main"); | |
590 | return; | |
591 | } | |
592 | } | |
593 | ||
594 | pending_diagnostic *pd = sm.on_leak (leaked_tree); | |
595 | if (pd) | |
596 | m_eg->get_diagnostic_manager ().add_diagnostic | |
597 | (&sm, m_enode_for_diag, m_enode_for_diag->get_supernode (), | |
598 | m_stmt, &stmt_finder, | |
599 | leaked_tree, state, pd); | |
600 | } | |
601 | ||
602 | /* Implementation of region_model_context::on_inherited_svalue vfunc | |
603 | for impl_region_model_context. | |
604 | Notify all checkers that CHILD_SID has been created from PARENT_SID, | |
605 | so that those state machines that inherit state can propagate the state | |
606 | from parent to child. */ | |
607 | ||
608 | void | |
609 | impl_region_model_context::on_inherited_svalue (svalue_id parent_sid, | |
610 | svalue_id child_sid) | |
611 | { | |
612 | if (!m_new_state) | |
613 | return; | |
614 | ||
615 | int sm_idx; | |
616 | sm_state_map *smap; | |
617 | FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap) | |
618 | { | |
619 | const state_machine &sm = m_ext_state.get_sm (sm_idx); | |
620 | if (sm.inherited_state_p ()) | |
621 | smap->on_inherited_svalue (parent_sid, child_sid); | |
622 | } | |
623 | } | |
624 | ||
625 | /* Implementation of region_model_context::on_cast vfunc | |
626 | for impl_region_model_context. | |
627 | Notify all checkers that DST_SID is a cast of SRC_SID, so that sm-state | |
628 | can be propagated from src to dst. */ | |
629 | ||
630 | void | |
631 | impl_region_model_context::on_cast (svalue_id src_sid, | |
632 | svalue_id dst_sid) | |
633 | { | |
634 | if (!m_new_state) | |
635 | return; | |
636 | ||
637 | int sm_idx; | |
638 | sm_state_map *smap; | |
639 | FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap) | |
640 | smap->on_cast (src_sid, dst_sid); | |
641 | } | |
642 | ||
643 | /* Implementation of region_model_context::on_condition vfunc. | |
644 | Notify all state machines about the condition, which could lead to | |
645 | state transitions. */ | |
646 | ||
647 | void | |
648 | impl_region_model_context::on_condition (tree lhs, enum tree_code op, tree rhs) | |
649 | { | |
650 | int sm_idx; | |
651 | sm_state_map *smap; | |
652 | FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap) | |
653 | { | |
654 | const state_machine &sm = m_ext_state.get_sm (sm_idx); | |
655 | impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag, | |
656 | m_old_state, m_new_state, | |
657 | m_change, | |
658 | m_old_state->m_checker_states[sm_idx], | |
659 | m_new_state->m_checker_states[sm_idx]); | |
660 | sm.on_condition (&sm_ctxt, | |
661 | m_enode_for_diag->get_supernode (), m_stmt, | |
662 | lhs, op, rhs); | |
663 | } | |
664 | } | |
665 | ||
8525d1f5 DM |
666 | /* Implementation of region_model_context::on_phi vfunc. |
667 | Notify all state machines about the phi, which could lead to | |
668 | state transitions. */ | |
669 | ||
670 | void | |
671 | impl_region_model_context::on_phi (const gphi *phi, tree rhs) | |
672 | { | |
673 | int sm_idx; | |
674 | sm_state_map *smap; | |
675 | FOR_EACH_VEC_ELT (m_new_state->m_checker_states, sm_idx, smap) | |
676 | { | |
677 | const state_machine &sm = m_ext_state.get_sm (sm_idx); | |
678 | impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag, | |
679 | m_old_state, m_new_state, | |
680 | m_change, | |
681 | m_old_state->m_checker_states[sm_idx], | |
682 | m_new_state->m_checker_states[sm_idx]); | |
683 | sm.on_phi (&sm_ctxt, m_enode_for_diag->get_supernode (), phi, rhs); | |
684 | } | |
685 | } | |
686 | ||
757bf1df DM |
687 | /* struct point_and_state. */ |
688 | ||
689 | /* Assert that this object is sane. */ | |
690 | ||
691 | void | |
692 | point_and_state::validate (const extrinsic_state &ext_state) const | |
693 | { | |
694 | /* Skip this in a release build. */ | |
695 | #if !CHECKING_P | |
696 | return; | |
697 | #endif | |
698 | ||
699 | m_point.validate (); | |
700 | ||
701 | m_state.validate (ext_state); | |
702 | ||
703 | /* Verify that the callstring's model of the stack corresponds to that | |
704 | of the region_model. */ | |
705 | /* They should have the same depth. */ | |
706 | gcc_assert (m_point.get_stack_depth () | |
707 | == m_state.m_region_model->get_stack_depth ()); | |
708 | /* Check the functions in the callstring vs those in the frames | |
709 | at each depth. */ | |
710 | for (int depth = 0; depth < m_point.get_stack_depth (); ++depth) | |
711 | { | |
712 | gcc_assert (m_point.get_function_at_depth (depth) | |
713 | == m_state.m_region_model->get_function_at_depth (depth)); | |
714 | } | |
715 | } | |
716 | ||
717 | /* Subroutine of print_enode_indices: print a run of indices from START_IDX | |
718 | to END_IDX to PP, using and updating *FIRST_RUN. */ | |
719 | ||
720 | static void | |
721 | print_run (pretty_printer *pp, int start_idx, int end_idx, | |
722 | bool *first_run) | |
723 | { | |
724 | if (!(*first_run)) | |
725 | pp_string (pp, ", "); | |
726 | *first_run = false; | |
727 | if (start_idx == end_idx) | |
728 | pp_printf (pp, "EN: %i", start_idx); | |
729 | else | |
730 | pp_printf (pp, "EN: %i-%i", start_idx, end_idx); | |
731 | } | |
732 | ||
733 | /* Print the indices within ENODES to PP, collecting them as | |
734 | runs/singletons e.g. "EN: 4-7, EN: 20-23, EN: 42". */ | |
735 | ||
736 | static void | |
737 | print_enode_indices (pretty_printer *pp, | |
738 | const auto_vec<exploded_node *> &enodes) | |
739 | { | |
740 | int cur_start_idx = -1; | |
741 | int cur_finish_idx = -1; | |
742 | bool first_run = true; | |
743 | unsigned i; | |
744 | exploded_node *enode; | |
745 | FOR_EACH_VEC_ELT (enodes, i, enode) | |
746 | { | |
747 | if (cur_start_idx == -1) | |
748 | { | |
749 | gcc_assert (cur_finish_idx == -1); | |
750 | cur_start_idx = cur_finish_idx = enode->m_index; | |
751 | } | |
752 | else | |
753 | { | |
754 | if (enode->m_index == cur_finish_idx + 1) | |
755 | /* Continuation of a run. */ | |
756 | cur_finish_idx = enode->m_index; | |
757 | else | |
758 | { | |
759 | /* Finish existing run, start a new one. */ | |
760 | gcc_assert (cur_start_idx >= 0); | |
761 | gcc_assert (cur_finish_idx >= 0); | |
762 | print_run (pp, cur_start_idx, cur_finish_idx, | |
763 | &first_run); | |
764 | cur_start_idx = cur_finish_idx = enode->m_index; | |
765 | } | |
766 | } | |
767 | } | |
768 | /* Finish any existing run. */ | |
769 | if (cur_start_idx >= 0) | |
770 | { | |
771 | gcc_assert (cur_finish_idx >= 0); | |
772 | print_run (pp, cur_start_idx, cur_finish_idx, | |
773 | &first_run); | |
774 | } | |
775 | } | |
776 | ||
777 | /* For use by dump_dot, get a value for the .dot "fillcolor" attribute. | |
778 | Colorize by sm-state, to make it easier to see how sm-state propagates | |
779 | through the exploded_graph. */ | |
780 | ||
781 | const char * | |
782 | exploded_node::get_dot_fillcolor () const | |
783 | { | |
784 | const program_state &state = get_state (); | |
785 | ||
786 | /* We want to be able to easily distinguish the no-sm-state case, | |
787 | and to be able to distinguish cases where there's a single state | |
788 | from each other. | |
789 | ||
790 | Sum the sm_states, and use the result to choose from a table, | |
791 | modulo table-size, special-casing the "no sm-state" case. */ | |
792 | int total_sm_state = 0; | |
793 | int i; | |
794 | sm_state_map *smap; | |
795 | FOR_EACH_VEC_ELT (state.m_checker_states, i, smap) | |
796 | { | |
797 | for (sm_state_map::iterator_t iter = smap->begin (); | |
798 | iter != smap->end (); | |
799 | ++iter) | |
800 | total_sm_state += (*iter).second.m_state; | |
801 | total_sm_state += smap->get_global_state (); | |
802 | } | |
803 | ||
804 | if (total_sm_state > 0) | |
805 | { | |
806 | /* An arbitrarily-picked collection of light colors. */ | |
807 | const char * const colors[] | |
808 | = {"azure", "coral", "cornsilk", "lightblue", "yellow"}; | |
809 | const int num_colors = sizeof (colors) / sizeof (colors[0]); | |
810 | return colors[total_sm_state % num_colors]; | |
811 | } | |
812 | else | |
813 | /* No sm-state. */ | |
814 | return "lightgrey"; | |
815 | } | |
816 | ||
817 | /* Implementation of dnode::dump_dot vfunc for exploded_node. */ | |
818 | ||
819 | void | |
820 | exploded_node::dump_dot (graphviz_out *gv, const dump_args_t &args) const | |
821 | { | |
822 | pretty_printer *pp = gv->get_pp (); | |
823 | ||
824 | dump_dot_id (pp); | |
825 | pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"", | |
826 | get_dot_fillcolor ()); | |
827 | pp_write_text_to_stream (pp); | |
828 | ||
829 | pp_printf (pp, "EN: %i", m_index); | |
a4d3bfc0 DM |
830 | if (m_status == STATUS_MERGER) |
831 | pp_string (pp, " (merger)"); | |
757bf1df DM |
832 | pp_newline (pp); |
833 | ||
834 | format f (true); | |
835 | m_ps.get_point ().print (pp, f); | |
836 | pp_newline (pp); | |
837 | ||
838 | const extrinsic_state &ext_state = args.m_eg.get_ext_state (); | |
839 | const program_state &state = m_ps.get_state (); | |
840 | state.dump_to_pp (ext_state, true, pp); | |
841 | pp_newline (pp); | |
842 | ||
843 | { | |
844 | int i; | |
845 | sm_state_map *smap; | |
846 | FOR_EACH_VEC_ELT (state.m_checker_states, i, smap) | |
847 | { | |
848 | if (!smap->is_empty_p ()) | |
849 | { | |
850 | pp_printf (pp, "%s: ", ext_state.get_name (i)); | |
851 | smap->print (ext_state.get_sm (i), pp); | |
852 | pp_newline (pp); | |
853 | } | |
854 | } | |
855 | } | |
856 | ||
857 | pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true); | |
858 | ||
859 | pp_string (pp, "\"];\n\n"); | |
860 | pp_flush (pp); | |
861 | } | |
862 | ||
863 | /* Dump this to PP in a form suitable for use as an id in .dot output. */ | |
864 | ||
865 | void | |
866 | exploded_node::dump_dot_id (pretty_printer *pp) const | |
867 | { | |
868 | pp_printf (pp, "exploded_node_%i", m_index); | |
869 | } | |
870 | ||
871 | /* Dump a multiline representation of this node to PP. */ | |
872 | ||
873 | void | |
874 | exploded_node::dump_to_pp (pretty_printer *pp, | |
875 | const extrinsic_state &ext_state) const | |
876 | { | |
877 | pp_printf (pp, "EN: %i", m_index); | |
878 | pp_newline (pp); | |
879 | ||
880 | format f (true); | |
881 | m_ps.get_point ().print (pp, f); | |
882 | pp_newline (pp); | |
883 | ||
884 | m_ps.get_state ().dump_to_pp (ext_state, false, pp); | |
885 | pp_newline (pp); | |
886 | } | |
887 | ||
888 | /* Dump a multiline representation of this node to FILE. */ | |
889 | ||
890 | void | |
891 | exploded_node::dump (FILE *fp, | |
892 | const extrinsic_state &ext_state) const | |
893 | { | |
894 | pretty_printer pp; | |
895 | pp_format_decoder (&pp) = default_tree_printer; | |
896 | pp_show_color (&pp) = pp_show_color (global_dc->printer); | |
897 | pp.buffer->stream = fp; | |
898 | dump_to_pp (&pp, ext_state); | |
899 | pp_flush (&pp); | |
900 | } | |
901 | ||
902 | /* Dump a multiline representation of this node to stderr. */ | |
903 | ||
904 | DEBUG_FUNCTION void | |
905 | exploded_node::dump (const extrinsic_state &ext_state) const | |
906 | { | |
907 | dump (stderr, ext_state); | |
908 | } | |
909 | ||
75038aa6 DM |
910 | } // namespace ana |
911 | ||
757bf1df DM |
912 | /* Return true if FNDECL has a gimple body. */ |
913 | // TODO: is there a pre-canned way to do this? | |
914 | ||
ef7827b0 | 915 | bool |
757bf1df DM |
916 | fndecl_has_gimple_body_p (tree fndecl) |
917 | { | |
918 | if (fndecl == NULL_TREE) | |
919 | return false; | |
920 | ||
921 | cgraph_node *n = cgraph_node::get (fndecl); | |
922 | if (!n) | |
923 | return false; | |
924 | ||
925 | return n->has_gimple_body_p (); | |
926 | } | |
927 | ||
75038aa6 DM |
928 | namespace ana { |
929 | ||
757bf1df DM |
930 | /* A pending_diagnostic subclass for implementing "__analyzer_dump_path". */ |
931 | ||
932 | class dump_path_diagnostic | |
933 | : public pending_diagnostic_subclass<dump_path_diagnostic> | |
934 | { | |
935 | public: | |
936 | bool emit (rich_location *richloc) FINAL OVERRIDE | |
937 | { | |
938 | inform (richloc, "path"); | |
939 | return true; | |
940 | } | |
941 | ||
942 | const char *get_kind () const FINAL OVERRIDE { return "dump_path_diagnostic"; } | |
943 | ||
944 | bool operator== (const dump_path_diagnostic &) const | |
945 | { | |
946 | return true; | |
947 | } | |
948 | }; | |
949 | ||
950 | /* Modify STATE in place, applying the effects of the stmt at this node's | |
951 | point. */ | |
952 | ||
953 | exploded_node::on_stmt_flags | |
954 | exploded_node::on_stmt (exploded_graph &eg, | |
955 | const supernode *snode, | |
956 | const gimple *stmt, | |
957 | program_state *state, | |
958 | state_change *change) const | |
959 | { | |
960 | /* Preserve the old state. It is used here for looking | |
961 | up old checker states, for determining state transitions, and | |
962 | also within impl_region_model_context and impl_sm_context for | |
963 | going from tree to svalue_id. */ | |
964 | const program_state old_state (*state); | |
965 | ||
966 | impl_region_model_context ctxt (eg, this, | |
967 | &old_state, state, change, | |
968 | stmt); | |
969 | ||
970 | if (const gassign *assign = dyn_cast <const gassign *> (stmt)) | |
971 | state->m_region_model->on_assignment (assign, &ctxt); | |
972 | ||
973 | if (const greturn *return_ = dyn_cast <const greturn *> (stmt)) | |
974 | state->m_region_model->on_return (return_, &ctxt); | |
975 | ||
ef7827b0 DM |
976 | /* Track whether we have a gcall to a function that's not recognized by |
977 | anything, for which we don't have a function body, or for which we | |
978 | don't know the fndecl. */ | |
979 | bool unknown_side_effects = false; | |
757bf1df DM |
980 | if (const gcall *call = dyn_cast <const gcall *> (stmt)) |
981 | { | |
982 | /* Debugging/test support. */ | |
983 | if (is_special_named_call_p (call, "__analyzer_dump", 0)) | |
984 | { | |
985 | /* Handle the builtin "__analyzer_dump" by dumping state | |
986 | to stderr. */ | |
987 | dump (eg.get_ext_state ()); | |
988 | } | |
989 | else if (is_special_named_call_p (call, "__analyzer_dump_path", 0)) | |
990 | { | |
991 | /* Handle the builtin "__analyzer_dump_path" by queuing a | |
992 | diagnostic at this exploded_node. */ | |
993 | ctxt.warn (new dump_path_diagnostic ()); | |
994 | } | |
995 | else if (is_special_named_call_p (call, "__analyzer_dump_region_model", 0)) | |
996 | { | |
997 | /* Handle the builtin "__analyzer_dump_region_model" by dumping | |
998 | the region model's state to stderr. */ | |
999 | state->m_region_model->dump (false); | |
1000 | } | |
1001 | else if (is_special_named_call_p (call, "__analyzer_eval", 1)) | |
1002 | { | |
1003 | /* Handle the builtin "__analyzer_eval" by evaluating the input | |
1004 | and dumping as a dummy warning, so that test cases can use | |
1005 | dg-warning to validate the result (and so unexpected warnings will | |
1006 | lead to DejaGnu failures). */ | |
1007 | tree t_arg = gimple_call_arg (call, 0); | |
1008 | tristate t | |
1009 | = state->m_region_model->eval_condition (t_arg, | |
1010 | NE_EXPR, | |
1011 | integer_zero_node, | |
1012 | &ctxt); | |
1013 | warning_at (call->location, 0, "%s", t.as_string ()); | |
1014 | } | |
1015 | else if (is_special_named_call_p (call, "__analyzer_break", 0)) | |
1016 | { | |
1017 | /* Handle the builtin "__analyzer_break" by triggering a | |
1018 | breakpoint. */ | |
1019 | /* TODO: is there a good cross-platform way to do this? */ | |
1020 | raise (SIGINT); | |
1021 | } | |
ef7827b0 DM |
1022 | else if (is_special_named_call_p (call, "__analyzer_dump_exploded_nodes", |
1023 | 1)) | |
1024 | { | |
1025 | /* This is handled elsewhere. */ | |
1026 | } | |
342e14ff | 1027 | else if (is_setjmp_call_p (call)) |
757bf1df DM |
1028 | state->m_region_model->on_setjmp (call, this, &ctxt); |
1029 | else if (is_longjmp_call_p (call)) | |
1030 | { | |
1031 | on_longjmp (eg, call, state, &ctxt); | |
1032 | return on_stmt_flags::terminate_path (); | |
1033 | } | |
1034 | else | |
ef7827b0 | 1035 | unknown_side_effects = state->m_region_model->on_call_pre (call, &ctxt); |
757bf1df DM |
1036 | } |
1037 | ||
1038 | bool any_sm_changes = false; | |
1039 | int sm_idx; | |
1040 | sm_state_map *smap; | |
1041 | FOR_EACH_VEC_ELT (old_state.m_checker_states, sm_idx, smap) | |
1042 | { | |
1043 | const state_machine &sm = eg.get_ext_state ().get_sm (sm_idx); | |
1044 | const sm_state_map *old_smap | |
1045 | = old_state.m_checker_states[sm_idx]; | |
1046 | sm_state_map *new_smap = state->m_checker_states[sm_idx]; | |
91f993b7 DM |
1047 | impl_sm_context sm_ctxt (eg, sm_idx, sm, this, &old_state, state, |
1048 | change, | |
1049 | old_smap, new_smap); | |
757bf1df | 1050 | /* Allow the state_machine to handle the stmt. */ |
91f993b7 | 1051 | if (sm.on_stmt (&sm_ctxt, snode, stmt)) |
ef7827b0 DM |
1052 | unknown_side_effects = false; |
1053 | else | |
757bf1df DM |
1054 | { |
1055 | /* For those stmts that were not handled by the state machine. */ | |
1056 | if (const gcall *call = dyn_cast <const gcall *> (stmt)) | |
1057 | { | |
91f993b7 DM |
1058 | tree callee_fndecl |
1059 | = state->m_region_model->get_fndecl_for_call (call, &ctxt); | |
757bf1df DM |
1060 | |
1061 | if (!fndecl_has_gimple_body_p (callee_fndecl)) | |
1062 | new_smap->purge_for_unknown_fncall (eg, sm, call, callee_fndecl, | |
1063 | state->m_region_model); | |
1064 | } | |
1065 | } | |
1066 | if (*old_smap != *new_smap) | |
1067 | any_sm_changes = true; | |
1068 | } | |
1069 | ||
1070 | if (const gcall *call = dyn_cast <const gcall *> (stmt)) | |
ef7827b0 | 1071 | state->m_region_model->on_call_post (call, unknown_side_effects, &ctxt); |
757bf1df DM |
1072 | |
1073 | return on_stmt_flags (any_sm_changes); | |
1074 | } | |
1075 | ||
1076 | /* Consider the effect of following superedge SUCC from this node. | |
1077 | ||
1078 | Return true if it's feasible to follow the edge, or false | |
1079 | if it's infeasible. | |
1080 | ||
1081 | Examples: if it's the "true" branch within | |
1082 | a CFG and we know the conditional is false, we know it's infeasible. | |
1083 | If it's one of multiple interprocedual "return" edges, then only | |
1084 | the edge back to the most recent callsite is feasible. | |
1085 | ||
1086 | Update NEXT_STATE accordingly (e.g. to record that a condition was | |
1087 | true or false, or that the NULL-ness of a pointer has been checked, | |
1088 | pushing/popping stack frames, etc). | |
1089 | ||
1090 | Update NEXT_POINT accordingly (updating the call string). */ | |
1091 | ||
1092 | bool | |
1093 | exploded_node::on_edge (exploded_graph &eg, | |
1094 | const superedge *succ, | |
1095 | program_point *next_point, | |
1096 | program_state *next_state, | |
1097 | state_change *change) const | |
1098 | { | |
1099 | LOG_FUNC (eg.get_logger ()); | |
1100 | ||
1101 | if (!next_point->on_edge (eg, succ)) | |
1102 | return false; | |
1103 | ||
1104 | if (!next_state->on_edge (eg, *this, succ, change)) | |
1105 | return false; | |
1106 | ||
1107 | return true; | |
1108 | } | |
1109 | ||
1110 | /* Verify that the stack at LONGJMP_POINT is still valid, given a call | |
1111 | to "setjmp" at SETJMP_POINT - the stack frame that "setjmp" was | |
1112 | called in must still be valid. | |
1113 | ||
1114 | Caveat: this merely checks the call_strings in the points; it doesn't | |
1115 | detect the case where a frame returns and is then called again. */ | |
1116 | ||
1117 | static bool | |
1118 | valid_longjmp_stack_p (const program_point &longjmp_point, | |
1119 | const program_point &setjmp_point) | |
1120 | { | |
1121 | const call_string &cs_at_longjmp = longjmp_point.get_call_string (); | |
1122 | const call_string &cs_at_setjmp = setjmp_point.get_call_string (); | |
1123 | ||
1124 | if (cs_at_longjmp.length () < cs_at_setjmp.length ()) | |
1125 | return false; | |
1126 | ||
1127 | /* Check that the call strings match, up to the depth of the | |
1128 | setjmp point. */ | |
1129 | for (unsigned depth = 0; depth < cs_at_setjmp.length (); depth++) | |
1130 | if (cs_at_longjmp[depth] != cs_at_setjmp[depth]) | |
1131 | return false; | |
1132 | ||
1133 | return true; | |
1134 | } | |
1135 | ||
1136 | /* A pending_diagnostic subclass for complaining about bad longjmps, | |
1137 | where the enclosing function of the "setjmp" has returned (and thus | |
1138 | the stack frame no longer exists). */ | |
1139 | ||
1140 | class stale_jmp_buf : public pending_diagnostic_subclass<dump_path_diagnostic> | |
1141 | { | |
1142 | public: | |
1143 | stale_jmp_buf (const gcall *setjmp_call, const gcall *longjmp_call) | |
1144 | : m_setjmp_call (setjmp_call), m_longjmp_call (longjmp_call) | |
1145 | {} | |
1146 | ||
1147 | bool emit (rich_location *richloc) FINAL OVERRIDE | |
1148 | { | |
1149 | return warning_at | |
1150 | (richloc, OPT_Wanalyzer_stale_setjmp_buffer, | |
1151 | "%qs called after enclosing function of %qs has returned", | |
342e14ff DM |
1152 | get_user_facing_name (m_longjmp_call), |
1153 | get_user_facing_name (m_setjmp_call)); | |
757bf1df DM |
1154 | } |
1155 | ||
1156 | const char *get_kind () const FINAL OVERRIDE | |
1157 | { return "stale_jmp_buf"; } | |
1158 | ||
1159 | bool operator== (const stale_jmp_buf &other) const | |
1160 | { | |
1161 | return (m_setjmp_call == other.m_setjmp_call | |
1162 | && m_longjmp_call == other.m_longjmp_call); | |
1163 | } | |
1164 | ||
1165 | private: | |
1166 | const gcall *m_setjmp_call; | |
1167 | const gcall *m_longjmp_call; | |
1168 | }; | |
1169 | ||
342e14ff | 1170 | /* Handle LONGJMP_CALL, a call to longjmp or siglongjmp. |
757bf1df | 1171 | |
342e14ff DM |
1172 | Attempt to locate where setjmp/sigsetjmp was called on the jmp_buf and build |
1173 | an exploded_node and exploded_edge to it representing a rewind to that frame, | |
757bf1df DM |
1174 | handling the various kinds of failure that can occur. */ |
1175 | ||
1176 | void | |
1177 | exploded_node::on_longjmp (exploded_graph &eg, | |
1178 | const gcall *longjmp_call, | |
1179 | program_state *new_state, | |
1180 | region_model_context *ctxt) const | |
1181 | { | |
1182 | tree buf_ptr = gimple_call_arg (longjmp_call, 0); | |
1183 | ||
1184 | region_model *new_region_model = new_state->m_region_model; | |
1185 | region_id buf_rid = new_region_model->deref_rvalue (buf_ptr, ctxt); | |
1186 | region *buf = new_region_model->get_region (buf_rid); | |
1187 | if (!buf) | |
1188 | return; | |
1189 | ||
1190 | svalue_id buf_content_sid | |
1191 | = buf->get_value (*new_region_model, false, ctxt); | |
1192 | svalue *buf_content_sval = new_region_model->get_svalue (buf_content_sid); | |
1193 | if (!buf_content_sval) | |
1194 | return; | |
1195 | setjmp_svalue *setjmp_sval = buf_content_sval->dyn_cast_setjmp_svalue (); | |
1196 | if (!setjmp_sval) | |
1197 | return; | |
1198 | ||
fd9982bb DM |
1199 | const setjmp_record tmp_setjmp_record = setjmp_sval->get_setjmp_record (); |
1200 | ||
342e14ff DM |
1201 | /* Build a custom enode and eedge for rewinding from the longjmp/siglongjmp |
1202 | call back to the setjmp/sigsetjmp. */ | |
1203 | rewind_info_t rewind_info (tmp_setjmp_record, longjmp_call); | |
757bf1df DM |
1204 | |
1205 | const gcall *setjmp_call = rewind_info.get_setjmp_call (); | |
1206 | const program_point &setjmp_point = rewind_info.get_setjmp_point (); | |
1207 | ||
1208 | const program_point &longjmp_point = get_point (); | |
1209 | ||
1210 | /* Verify that the setjmp's call_stack hasn't been popped. */ | |
1211 | if (!valid_longjmp_stack_p (longjmp_point, setjmp_point)) | |
1212 | { | |
1213 | ctxt->warn (new stale_jmp_buf (setjmp_call, longjmp_call)); | |
1214 | return; | |
1215 | } | |
1216 | ||
1217 | gcc_assert (longjmp_point.get_stack_depth () | |
1218 | >= setjmp_point.get_stack_depth ()); | |
1219 | ||
1220 | /* Update the state for use by the destination node. */ | |
1221 | ||
1222 | /* Stash the current number of diagnostics so that we can update | |
1223 | any that this adds to show where the longjmp is rewinding to. */ | |
1224 | ||
1225 | diagnostic_manager *dm = &eg.get_diagnostic_manager (); | |
1226 | unsigned prev_num_diagnostics = dm->get_num_diagnostics (); | |
1227 | ||
1228 | new_region_model->on_longjmp (longjmp_call, setjmp_call, | |
1229 | setjmp_point.get_stack_depth (), ctxt); | |
1230 | ||
1231 | program_point next_point | |
1232 | = program_point::after_supernode (setjmp_point.get_supernode (), | |
1233 | setjmp_point.get_call_string ()); | |
1234 | ||
1235 | state_change change; | |
1236 | exploded_node *next = eg.get_or_create_node (next_point, *new_state, &change); | |
1237 | ||
1238 | /* Create custom exploded_edge for a longjmp. */ | |
1239 | if (next) | |
1240 | { | |
1241 | exploded_edge *eedge | |
1242 | = eg.add_edge (const_cast<exploded_node *> (this), next, NULL, | |
1243 | change, | |
342e14ff | 1244 | new rewind_info_t (tmp_setjmp_record, longjmp_call)); |
757bf1df DM |
1245 | |
1246 | /* For any diagnostics that were queued here (such as leaks) we want | |
1247 | the checker_path to show the rewinding events after the "final event" | |
1248 | so that the user sees where the longjmp is rewinding to (otherwise the | |
1249 | path is meaningless). | |
1250 | ||
1251 | For example, we want to emit something like: | |
1252 | | NN | { | |
1253 | | NN | longjmp (env, 1); | |
1254 | | | ~~~~~~~~~~~~~~~~ | |
1255 | | | | | |
1256 | | | (10) 'ptr' leaks here; was allocated at (7) | |
1257 | | | (11) rewinding from 'longjmp' in 'inner'... | |
1258 | | | |
1259 | <-------------+ | |
1260 | | | |
1261 | 'outer': event 12 | |
1262 | | | |
1263 | | NN | i = setjmp(env); | |
1264 | | | ^~~~~~ | |
1265 | | | | | |
1266 | | | (12) ...to 'setjmp' in 'outer' (saved at (2)) | |
1267 | ||
1268 | where the "final" event above is event (10), but we want to append | |
1269 | events (11) and (12) afterwards. | |
1270 | ||
1271 | Do this by setting m_trailing_eedge on any diagnostics that were | |
1272 | just saved. */ | |
1273 | unsigned num_diagnostics = dm->get_num_diagnostics (); | |
1274 | for (unsigned i = prev_num_diagnostics; i < num_diagnostics; i++) | |
1275 | { | |
1276 | saved_diagnostic *sd = dm->get_saved_diagnostic (i); | |
1277 | sd->m_trailing_eedge = eedge; | |
1278 | } | |
1279 | } | |
1280 | } | |
1281 | ||
1282 | /* Subroutine of exploded_graph::process_node for finding the successors | |
1283 | of the supernode for a function exit basic block. | |
1284 | ||
1285 | Ensure that pop_frame is called, potentially queuing diagnostics about | |
1286 | leaks. */ | |
1287 | ||
1288 | void | |
1289 | exploded_node::detect_leaks (exploded_graph &eg) const | |
1290 | { | |
1291 | LOG_FUNC_1 (eg.get_logger (), "EN: %i", m_index); | |
1292 | ||
1293 | gcc_assert (get_point ().get_supernode ()->return_p ()); | |
1294 | ||
1295 | /* If we're not a "top-level" function, do nothing; pop_frame | |
1296 | will be called when handling the return superedge. */ | |
1297 | if (get_point ().get_stack_depth () > 1) | |
1298 | return; | |
1299 | ||
1300 | /* We have a "top-level" function. */ | |
1301 | gcc_assert (get_point ().get_stack_depth () == 1); | |
1302 | ||
1303 | const program_state &old_state = get_state (); | |
1304 | ||
1305 | /* Work with a temporary copy of the state: pop the frame, and see | |
1306 | what leaks (via purge_unused_svalues). */ | |
1307 | program_state new_state (old_state); | |
1308 | ||
1309 | gcc_assert (new_state.m_region_model); | |
1310 | ||
1311 | purge_stats stats; | |
1312 | impl_region_model_context ctxt (eg, this, | |
1313 | &old_state, &new_state, | |
1314 | NULL, | |
1315 | get_stmt ()); | |
1316 | new_state.m_region_model->pop_frame (true, &stats, &ctxt); | |
1317 | } | |
1318 | ||
1319 | /* Dump the successors and predecessors of this enode to OUTF. */ | |
1320 | ||
1321 | void | |
1322 | exploded_node::dump_succs_and_preds (FILE *outf) const | |
1323 | { | |
1324 | unsigned i; | |
1325 | exploded_edge *e; | |
1326 | { | |
1327 | auto_vec<exploded_node *> preds (m_preds.length ()); | |
1328 | FOR_EACH_VEC_ELT (m_preds, i, e) | |
1329 | preds.quick_push (e->m_src); | |
1330 | pretty_printer pp; | |
1331 | print_enode_indices (&pp, preds); | |
1332 | fprintf (outf, "preds: %s\n", | |
1333 | pp_formatted_text (&pp)); | |
1334 | } | |
1335 | { | |
1336 | auto_vec<exploded_node *> succs (m_succs.length ()); | |
1337 | FOR_EACH_VEC_ELT (m_succs, i, e) | |
1338 | succs.quick_push (e->m_dest); | |
1339 | pretty_printer pp; | |
1340 | print_enode_indices (&pp, succs); | |
1341 | fprintf (outf, "succs: %s\n", | |
1342 | pp_formatted_text (&pp)); | |
1343 | } | |
1344 | } | |
1345 | ||
1346 | /* class rewind_info_t : public exploded_edge::custom_info_t. */ | |
1347 | ||
1348 | /* Implementation of exploded_edge::custom_info_t::update_model vfunc | |
1349 | for rewind_info_t. | |
1350 | ||
1351 | Update state for the special-case of a rewind of a longjmp | |
1352 | to a setjmp (which doesn't have a superedge, but does affect | |
1353 | state). */ | |
1354 | ||
1355 | void | |
1356 | rewind_info_t::update_model (region_model *model, | |
1357 | const exploded_edge &eedge) | |
1358 | { | |
757bf1df DM |
1359 | const program_point &longjmp_point = eedge.m_src->get_point (); |
1360 | const program_point &setjmp_point = eedge.m_dest->get_point (); | |
1361 | ||
1362 | gcc_assert (longjmp_point.get_stack_depth () | |
1363 | >= setjmp_point.get_stack_depth ()); | |
1364 | ||
5aebfb71 | 1365 | model->on_longjmp (get_longjmp_call (), |
757bf1df DM |
1366 | get_setjmp_call (), |
1367 | setjmp_point.get_stack_depth (), NULL); | |
1368 | } | |
1369 | ||
1370 | /* Implementation of exploded_edge::custom_info_t::add_events_to_path vfunc | |
1371 | for rewind_info_t. */ | |
1372 | ||
1373 | void | |
1374 | rewind_info_t::add_events_to_path (checker_path *emission_path, | |
1375 | const exploded_edge &eedge) | |
1376 | { | |
1377 | const exploded_node *src_node = eedge.m_src; | |
1378 | const program_point &src_point = src_node->get_point (); | |
1379 | const int src_stack_depth = src_point.get_stack_depth (); | |
1380 | const exploded_node *dst_node = eedge.m_dest; | |
1381 | const program_point &dst_point = dst_node->get_point (); | |
1382 | const int dst_stack_depth = dst_point.get_stack_depth (); | |
1383 | ||
1384 | emission_path->add_event | |
1385 | (new rewind_from_longjmp_event | |
5aebfb71 | 1386 | (&eedge, get_longjmp_call ()->location, |
757bf1df | 1387 | src_point.get_fndecl (), |
342e14ff | 1388 | src_stack_depth, this)); |
757bf1df DM |
1389 | emission_path->add_event |
1390 | (new rewind_to_setjmp_event | |
1391 | (&eedge, get_setjmp_call ()->location, | |
1392 | dst_point.get_fndecl (), | |
1393 | dst_stack_depth, this)); | |
1394 | } | |
1395 | ||
26d949c8 | 1396 | /* class exploded_edge : public dedge<eg_traits>. */ |
757bf1df DM |
1397 | |
1398 | /* exploded_edge's ctor. */ | |
1399 | ||
1400 | exploded_edge::exploded_edge (exploded_node *src, exploded_node *dest, | |
a60d9889 | 1401 | const extrinsic_state &ext_state, |
757bf1df DM |
1402 | const superedge *sedge, |
1403 | const state_change &change, | |
1404 | custom_info_t *custom_info) | |
26d949c8 | 1405 | : dedge<eg_traits> (src, dest), m_sedge (sedge), m_change (change), |
757bf1df DM |
1406 | m_custom_info (custom_info) |
1407 | { | |
a60d9889 | 1408 | change.validate (dest->get_state (), ext_state); |
757bf1df DM |
1409 | } |
1410 | ||
1411 | /* exploded_edge's dtor. */ | |
1412 | ||
1413 | exploded_edge::~exploded_edge () | |
1414 | { | |
1415 | delete m_custom_info; | |
1416 | } | |
1417 | ||
1418 | /* Implementation of dedge::dump_dot vfunc for exploded_edge. | |
1419 | Use the label of the underlying superedge, if any. */ | |
1420 | ||
1421 | void | |
1422 | exploded_edge::dump_dot (graphviz_out *gv, const dump_args_t &args) const | |
1423 | { | |
1424 | pretty_printer *pp = gv->get_pp (); | |
1425 | ||
1426 | const char *style = "\"solid,bold\""; | |
1427 | const char *color = "black"; | |
1428 | int weight = 10; | |
1429 | const char *constraint = "true"; | |
1430 | ||
1431 | if (m_sedge) | |
1432 | switch (m_sedge->m_kind) | |
1433 | { | |
1434 | default: | |
1435 | gcc_unreachable (); | |
1436 | case SUPEREDGE_CFG_EDGE: | |
1437 | break; | |
1438 | case SUPEREDGE_CALL: | |
1439 | color = "red"; | |
1440 | //constraint = "false"; | |
1441 | break; | |
1442 | case SUPEREDGE_RETURN: | |
1443 | color = "green"; | |
1444 | //constraint = "false"; | |
1445 | break; | |
1446 | case SUPEREDGE_INTRAPROCEDURAL_CALL: | |
1447 | style = "\"dotted\""; | |
1448 | break; | |
1449 | } | |
1450 | if (m_custom_info) | |
1451 | { | |
1452 | color = "red"; | |
1453 | style = "\"dotted\""; | |
1454 | } | |
1455 | ||
1456 | m_src->dump_dot_id (pp); | |
1457 | pp_string (pp, " -> "); | |
1458 | m_dest->dump_dot_id (pp); | |
1459 | pp_printf (pp, | |
1460 | (" [style=%s, color=%s, weight=%d, constraint=%s," | |
1461 | " headlabel=\""), | |
1462 | style, color, weight, constraint); | |
1463 | ||
1464 | if (m_sedge) | |
1465 | m_sedge->dump_label_to_pp (pp, false); | |
1466 | else if (m_custom_info) | |
1467 | m_custom_info->print (pp); | |
1468 | ||
1469 | m_change.dump (pp, args.m_eg.get_ext_state ()); | |
1470 | //pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/false); | |
1471 | ||
1472 | pp_printf (pp, "\"];\n"); | |
1473 | } | |
1474 | ||
1475 | /* struct stats. */ | |
1476 | ||
1477 | /* stats' ctor. */ | |
1478 | ||
1479 | stats::stats (int num_supernodes) | |
1480 | : m_node_reuse_count (0), | |
1481 | m_node_reuse_after_merge_count (0), | |
1482 | m_num_supernodes (num_supernodes) | |
1483 | { | |
1484 | for (int i = 0; i < NUM_POINT_KINDS; i++) | |
1485 | m_num_nodes[i] = 0; | |
1486 | } | |
1487 | ||
1488 | /* Log these stats in multiline form to LOGGER. */ | |
1489 | ||
1490 | void | |
1491 | stats::log (logger *logger) const | |
1492 | { | |
1493 | gcc_assert (logger); | |
1494 | for (int i = 0; i < NUM_POINT_KINDS; i++) | |
1495 | logger->log ("m_num_nodes[%s]: %i", | |
1496 | point_kind_to_string (static_cast <enum point_kind> (i)), | |
1497 | m_num_nodes[i]); | |
1498 | logger->log ("m_node_reuse_count: %i", m_node_reuse_count); | |
1499 | logger->log ("m_node_reuse_after_merge_count: %i", | |
1500 | m_node_reuse_after_merge_count); | |
1501 | } | |
1502 | ||
1503 | /* Dump these stats in multiline form to OUT. */ | |
1504 | ||
1505 | void | |
1506 | stats::dump (FILE *out) const | |
1507 | { | |
1508 | for (int i = 0; i < NUM_POINT_KINDS; i++) | |
1509 | fprintf (out, "m_num_nodes[%s]: %i\n", | |
1510 | point_kind_to_string (static_cast <enum point_kind> (i)), | |
1511 | m_num_nodes[i]); | |
1512 | fprintf (out, "m_node_reuse_count: %i\n", m_node_reuse_count); | |
1513 | fprintf (out, "m_node_reuse_after_merge_count: %i\n", | |
1514 | m_node_reuse_after_merge_count); | |
1515 | ||
1516 | if (m_num_supernodes > 0) | |
1517 | fprintf (out, "PK_AFTER_SUPERNODE nodes per supernode: %.2f\n", | |
1518 | (float)m_num_nodes[PK_AFTER_SUPERNODE] / (float)m_num_supernodes); | |
1519 | } | |
1520 | ||
1521 | /* strongly_connected_components's ctor. Tarjan's SCC algorithm. */ | |
1522 | ||
1523 | strongly_connected_components:: | |
1524 | strongly_connected_components (const supergraph &sg, logger *logger) | |
1525 | : m_sg (sg), m_per_node (m_sg.num_nodes ()) | |
1526 | { | |
1527 | LOG_SCOPE (logger); | |
1528 | auto_timevar tv (TV_ANALYZER_SCC); | |
1529 | ||
1530 | for (int i = 0; i < m_sg.num_nodes (); i++) | |
1531 | m_per_node.quick_push (per_node_data ()); | |
1532 | ||
1533 | for (int i = 0; i < m_sg.num_nodes (); i++) | |
1534 | if (m_per_node[i].m_index == -1) | |
1535 | strong_connect (i); | |
1536 | ||
1537 | if (0) | |
1538 | dump (); | |
1539 | } | |
1540 | ||
1541 | /* Dump this object to stderr. */ | |
1542 | ||
1543 | DEBUG_FUNCTION void | |
1544 | strongly_connected_components::dump () const | |
1545 | { | |
1546 | for (int i = 0; i < m_sg.num_nodes (); i++) | |
1547 | { | |
1548 | const per_node_data &v = m_per_node[i]; | |
1549 | fprintf (stderr, "SN %i: index: %i lowlink: %i on_stack: %i\n", | |
1550 | i, v.m_index, v.m_lowlink, v.m_on_stack); | |
1551 | } | |
1552 | } | |
1553 | ||
1554 | /* Subroutine of strongly_connected_components's ctor, part of Tarjan's | |
1555 | SCC algorithm. */ | |
1556 | ||
1557 | void | |
1558 | strongly_connected_components::strong_connect (unsigned index) | |
1559 | { | |
1560 | supernode *v_snode = m_sg.get_node_by_index (index); | |
1561 | ||
1562 | /* Set the depth index for v to the smallest unused index. */ | |
1563 | per_node_data *v = &m_per_node[index]; | |
1564 | v->m_index = index; | |
1565 | v->m_lowlink = index; | |
1566 | m_stack.safe_push (index); | |
1567 | v->m_on_stack = true; | |
1568 | index++; | |
1569 | ||
1570 | /* Consider successors of v. */ | |
1571 | unsigned i; | |
1572 | superedge *sedge; | |
1573 | FOR_EACH_VEC_ELT (v_snode->m_succs, i, sedge) | |
1574 | { | |
1575 | supernode *w_snode = sedge->m_dest; | |
1576 | per_node_data *w = &m_per_node[w_snode->m_index]; | |
1577 | if (w->m_index == -1) | |
1578 | { | |
1579 | /* Successor w has not yet been visited; recurse on it. */ | |
1580 | strong_connect (w_snode->m_index); | |
1581 | v->m_lowlink = MIN (v->m_lowlink, w->m_lowlink); | |
1582 | } | |
1583 | else if (w->m_on_stack) | |
1584 | { | |
1585 | /* Successor w is in stack S and hence in the current SCC | |
1586 | If w is not on stack, then (v, w) is a cross-edge in the DFS | |
1587 | tree and must be ignored. */ | |
1588 | v->m_lowlink = MIN (v->m_lowlink, w->m_index); | |
1589 | } | |
1590 | } | |
1591 | ||
1592 | /* If v is a root node, pop the stack and generate an SCC. */ | |
1593 | ||
1594 | if (v->m_lowlink == v->m_index) | |
1595 | { | |
1596 | per_node_data *w; | |
1597 | do { | |
1598 | int idx = m_stack.pop (); | |
1599 | w = &m_per_node[idx]; | |
1600 | w->m_on_stack = false; | |
1601 | } while (w != v); | |
1602 | } | |
1603 | } | |
1604 | ||
1605 | /* worklist's ctor. */ | |
1606 | ||
1607 | worklist::worklist (const exploded_graph &eg, const analysis_plan &plan) | |
1608 | : m_eg (eg), | |
1609 | m_scc (eg.get_supergraph (), eg.get_logger ()), | |
1610 | m_plan (plan), | |
1611 | m_queue (key_t (*this, NULL)) | |
1612 | { | |
1613 | } | |
1614 | ||
1615 | /* Return the number of nodes in the worklist. */ | |
1616 | ||
1617 | unsigned | |
1618 | worklist::length () const | |
1619 | { | |
1620 | return m_queue.nodes (); | |
1621 | } | |
1622 | ||
1623 | /* Return the next node in the worklist, removing it. */ | |
1624 | ||
1625 | exploded_node * | |
1626 | worklist::take_next () | |
1627 | { | |
1628 | return m_queue.extract_min (); | |
1629 | } | |
1630 | ||
1631 | /* Return the next node in the worklist without removing it. */ | |
1632 | ||
1633 | exploded_node * | |
1634 | worklist::peek_next () | |
1635 | { | |
1636 | return m_queue.min (); | |
1637 | } | |
1638 | ||
1639 | /* Add ENODE to the worklist. */ | |
1640 | ||
1641 | void | |
1642 | worklist::add_node (exploded_node *enode) | |
1643 | { | |
a4d3bfc0 | 1644 | gcc_assert (enode->get_status () == exploded_node::STATUS_WORKLIST); |
757bf1df DM |
1645 | m_queue.insert (key_t (*this, enode), enode); |
1646 | } | |
1647 | ||
1648 | /* Comparator for implementing worklist::key_t comparison operators. | |
1649 | Return negative if KA is before KB | |
1650 | Return positive if KA is after KB | |
1651 | Return 0 if they are equal. */ | |
1652 | ||
1653 | int | |
6a81cabc | 1654 | worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb) |
757bf1df DM |
1655 | { |
1656 | const program_point &point_a = ka.m_enode->get_point (); | |
1657 | const program_point &point_b = kb.m_enode->get_point (); | |
1658 | const call_string &call_string_a = point_a.get_call_string (); | |
1659 | const call_string &call_string_b = point_b.get_call_string (); | |
1660 | ||
1661 | /* Order empty-callstring points with different functions based on the | |
1662 | analysis_plan, so that we generate summaries before they are used. */ | |
1663 | if (flag_analyzer_call_summaries | |
1664 | && call_string_a.empty_p () | |
1665 | && call_string_b.empty_p () | |
1666 | && point_a.get_function () != NULL | |
1667 | && point_b.get_function () != NULL | |
1668 | && point_a.get_function () != point_b.get_function ()) | |
1669 | { | |
1670 | return ka.m_worklist.m_plan.cmp_function (point_a.get_function (), | |
1671 | point_b.get_function ()); | |
1672 | } | |
1673 | ||
1674 | /* First, order by SCC. */ | |
1675 | int scc_id_a = ka.get_scc_id (ka.m_enode); | |
1676 | int scc_id_b = kb.get_scc_id (kb.m_enode); | |
1677 | if (scc_id_a != scc_id_b) | |
1678 | return scc_id_a - scc_id_b; | |
1679 | ||
1680 | /* If in same SCC, order by supernode index (an arbitrary but stable | |
1681 | ordering). */ | |
1682 | const supernode *snode_a = ka.m_enode->get_supernode (); | |
1683 | const supernode *snode_b = kb.m_enode->get_supernode (); | |
1684 | if (snode_a == NULL) | |
1685 | { | |
1686 | if (snode_b != NULL) | |
1687 | /* One is NULL. */ | |
1688 | return -1; | |
1689 | else | |
1690 | /* Both are NULL. */ | |
1691 | return 0; | |
1692 | } | |
1693 | if (snode_b == NULL) | |
1694 | /* One is NULL. */ | |
1695 | return 1; | |
1696 | /* Neither are NULL. */ | |
1697 | gcc_assert (snode_a && snode_b); | |
1698 | if (snode_a->m_index != snode_b->m_index) | |
1699 | return snode_a->m_index - snode_b->m_index; | |
1700 | ||
1701 | gcc_assert (snode_a == snode_b); | |
1702 | ||
1703 | /* Order within supernode via program point. */ | |
1704 | int within_snode_cmp | |
1705 | = function_point::cmp_within_supernode (point_a.get_function_point (), | |
1706 | point_b.get_function_point ()); | |
1707 | if (within_snode_cmp) | |
1708 | return within_snode_cmp; | |
1709 | ||
1710 | /* The points might vary by callstring; try sorting by callstring. */ | |
1711 | int cs_cmp = call_string::cmp (call_string_a, call_string_b); | |
1712 | if (cs_cmp) | |
1713 | return cs_cmp; | |
1714 | ||
1715 | /* Otherwise, we ought to have the same program_point. */ | |
1716 | gcc_assert (point_a == point_b); | |
1717 | ||
1718 | const program_state &state_a = ka.m_enode->get_state (); | |
1719 | const program_state &state_b = kb.m_enode->get_state (); | |
1720 | ||
1721 | /* Sort by sm-state, so that identical sm-states are grouped | |
1722 | together in the worklist. | |
1723 | For now, sort by the hash value (might not be deterministic). */ | |
1724 | for (unsigned sm_idx = 0; sm_idx < state_a.m_checker_states.length (); | |
1725 | ++sm_idx) | |
1726 | { | |
1727 | sm_state_map *smap_a = state_a.m_checker_states[sm_idx]; | |
1728 | sm_state_map *smap_b = state_b.m_checker_states[sm_idx]; | |
1729 | ||
6a81cabc DM |
1730 | hashval_t hash_a = smap_a->hash (); |
1731 | hashval_t hash_b = smap_b->hash (); | |
1732 | if (hash_a < hash_b) | |
1733 | return -1; | |
1734 | else if (hash_a > hash_b) | |
1735 | return 1; | |
757bf1df DM |
1736 | } |
1737 | ||
1738 | /* Otherwise, we have two enodes at the same program point but with | |
1739 | different states. We don't have a good total ordering on states, | |
1740 | so order them by enode index, so that we have at least have a | |
1741 | stable sort. */ | |
1742 | return ka.m_enode->m_index - kb.m_enode->m_index; | |
1743 | } | |
1744 | ||
757bf1df DM |
1745 | /* exploded_graph's ctor. */ |
1746 | ||
1747 | exploded_graph::exploded_graph (const supergraph &sg, logger *logger, | |
1748 | const extrinsic_state &ext_state, | |
1749 | const state_purge_map *purge_map, | |
1750 | const analysis_plan &plan, | |
1751 | int verbosity) | |
1752 | : m_sg (sg), m_logger (logger), | |
1753 | m_worklist (*this, plan), | |
1754 | m_ext_state (ext_state), | |
1755 | m_purge_map (purge_map), | |
1756 | m_plan (plan), | |
1757 | m_diagnostic_manager (logger, verbosity), | |
1758 | m_global_stats (m_sg.num_nodes ()), | |
1759 | m_functionless_stats (m_sg.num_nodes ()), | |
1760 | m_PK_AFTER_SUPERNODE_per_snode (m_sg.num_nodes ()) | |
1761 | { | |
1762 | m_origin = get_or_create_node (program_point (function_point (NULL, NULL, | |
1763 | 0, PK_ORIGIN), | |
1764 | call_string ()), | |
1765 | program_state (ext_state), NULL); | |
1766 | for (int i = 0; i < m_sg.num_nodes (); i++) | |
1767 | m_PK_AFTER_SUPERNODE_per_snode.quick_push (i); | |
1768 | } | |
1769 | ||
1770 | /* exploded_graph's dtor. */ | |
1771 | ||
1772 | exploded_graph::~exploded_graph () | |
1773 | { | |
1774 | for (function_stat_map_t::iterator iter = m_per_function_stats.begin (); | |
1775 | iter != m_per_function_stats.end (); | |
1776 | ++iter) | |
1777 | delete (*iter).second; | |
1778 | ||
1779 | for (point_map_t::iterator iter = m_per_point_data.begin (); | |
1780 | iter != m_per_point_data.end (); | |
1781 | ++iter) | |
1782 | delete (*iter).second; | |
1783 | } | |
1784 | ||
1785 | /* Ensure that there is an exploded_node representing an external call to | |
1786 | FUN, adding it to the worklist if creating it. | |
1787 | ||
1788 | Add an edge from the origin exploded_node to the function entrypoint | |
1789 | exploded_node. | |
1790 | ||
1791 | Return the exploded_node for the entrypoint to the function. */ | |
1792 | ||
1793 | exploded_node * | |
1794 | exploded_graph::add_function_entry (function *fun) | |
1795 | { | |
1796 | program_point point = program_point::from_function_entry (m_sg, fun); | |
1797 | program_state state (m_ext_state); | |
1798 | state.m_region_model->push_frame (fun, NULL, NULL); | |
1799 | ||
1800 | exploded_node *enode = get_or_create_node (point, state, NULL); | |
1801 | /* We should never fail to add such a node. */ | |
1802 | gcc_assert (enode); | |
1803 | state_change change; | |
1804 | add_edge (m_origin, enode, NULL, change); | |
1805 | return enode; | |
1806 | } | |
1807 | ||
1808 | /* Get or create an exploded_node for (POINT, STATE). | |
1809 | If a new node is created, it is added to the worklist. | |
1810 | If CHANGE is non-NULL, use it to suppress some purging of state, | |
1811 | to make generation of state_change_event instances easier. */ | |
1812 | ||
1813 | exploded_node * | |
1814 | exploded_graph::get_or_create_node (const program_point &point, | |
1815 | const program_state &state, | |
1816 | state_change *change) | |
1817 | { | |
1818 | logger * const logger = get_logger (); | |
1819 | LOG_FUNC (logger); | |
1820 | if (logger) | |
1821 | { | |
1822 | format f (false); | |
1823 | pretty_printer *pp = logger->get_printer (); | |
1824 | logger->start_log_line (); | |
1825 | pp_string (pp, "point: "); | |
1826 | point.print (pp, f); | |
1827 | logger->end_log_line (); | |
1828 | logger->start_log_line (); | |
1829 | pp_string (pp, "state: "); | |
1830 | state.dump (m_ext_state, true); | |
1831 | logger->end_log_line (); | |
1832 | } | |
1833 | ||
1834 | auto_cfun sentinel (point.get_function ()); | |
1835 | ||
1836 | state.validate (get_ext_state ()); | |
1837 | ||
1838 | //state.dump (get_ext_state ()); | |
1839 | ||
1840 | /* Prune state to try to improve the chances of a cache hit, | |
1841 | avoiding generating redundant nodes. */ | |
1842 | program_state pruned_state = state.prune_for_point (*this, point, change); | |
1843 | ||
1844 | pruned_state.validate (get_ext_state ()); | |
1845 | ||
1846 | //pruned_state.dump (get_ext_state ()); | |
1847 | ||
1848 | if (logger) | |
1849 | { | |
1850 | pretty_printer *pp = logger->get_printer (); | |
1851 | logger->start_log_line (); | |
1852 | pp_string (pp, "pruned_state: "); | |
1853 | pruned_state.dump_to_pp (m_ext_state, true, pp); | |
1854 | logger->end_log_line (); | |
1855 | pruned_state.m_region_model->dump_to_pp (logger->get_printer (), true); | |
1856 | } | |
1857 | ||
1858 | stats *per_fn_stats = get_or_create_function_stats (point.get_function ()); | |
1859 | ||
1860 | stats *per_cs_stats | |
1861 | = &get_or_create_per_call_string_data (point.get_call_string ())->m_stats; | |
1862 | ||
1863 | point_and_state ps (point, pruned_state); | |
1864 | ps.validate (m_ext_state); | |
1865 | if (exploded_node **slot = m_point_and_state_to_node.get (&ps)) | |
1866 | { | |
1867 | /* An exploded_node for PS already exists. */ | |
1868 | if (logger) | |
1869 | logger->log ("reused EN: %i", (*slot)->m_index); | |
1870 | m_global_stats.m_node_reuse_count++; | |
1871 | per_fn_stats->m_node_reuse_count++; | |
1872 | per_cs_stats->m_node_reuse_count++; | |
1873 | return *slot; | |
1874 | } | |
1875 | ||
1876 | per_program_point_data *per_point_data | |
1877 | = get_or_create_per_program_point_data (point); | |
1878 | ||
1879 | /* Consider merging state with another enode at this program_point. */ | |
1880 | if (flag_analyzer_state_merge) | |
1881 | { | |
1882 | exploded_node *existing_enode; | |
1883 | unsigned i; | |
1884 | FOR_EACH_VEC_ELT (per_point_data->m_enodes, i, existing_enode) | |
1885 | { | |
1886 | if (logger) | |
1887 | logger->log ("considering merging with existing EN: %i for point", | |
1888 | existing_enode->m_index); | |
1889 | gcc_assert (existing_enode->get_point () == point); | |
1890 | const program_state &existing_state = existing_enode->get_state (); | |
1891 | ||
1892 | /* This merges successfully within the loop. */ | |
1893 | ||
1894 | program_state merged_state (m_ext_state); | |
1895 | if (pruned_state.can_merge_with_p (existing_state, m_ext_state, | |
1896 | &merged_state)) | |
1897 | { | |
1898 | if (logger) | |
1899 | logger->log ("merging new state with that of EN: %i", | |
1900 | existing_enode->m_index); | |
1901 | ||
a60d9889 DM |
1902 | /* Try again for a cache hit. |
1903 | Whether we get one or not, merged_state's value_ids have no | |
1904 | relationship to those of the input state, and thus to those | |
1905 | of CHANGE, so we must purge any svalue_ids from *CHANGE. */ | |
757bf1df | 1906 | ps.set_state (merged_state); |
a60d9889 DM |
1907 | if (change) |
1908 | change->on_svalue_purge (svalue_id::from_int (0)); | |
1909 | ||
757bf1df DM |
1910 | if (exploded_node **slot = m_point_and_state_to_node.get (&ps)) |
1911 | { | |
1912 | /* An exploded_node for PS already exists. */ | |
1913 | if (logger) | |
1914 | logger->log ("reused EN: %i", (*slot)->m_index); | |
1915 | m_global_stats.m_node_reuse_after_merge_count++; | |
1916 | per_fn_stats->m_node_reuse_after_merge_count++; | |
1917 | per_cs_stats->m_node_reuse_after_merge_count++; | |
1918 | return *slot; | |
1919 | } | |
757bf1df DM |
1920 | } |
1921 | else | |
1922 | if (logger) | |
1923 | logger->log ("not merging new state with that of EN: %i", | |
1924 | existing_enode->m_index); | |
1925 | } | |
1926 | } | |
1927 | ||
1928 | /* Impose a limit on the number of enodes per program point, and | |
1929 | simply stop if we exceed it. */ | |
1930 | if ((int)per_point_data->m_enodes.length () | |
1931 | > param_analyzer_max_enodes_per_program_point) | |
1932 | { | |
1933 | if (logger) | |
1934 | logger->log ("not creating enode; too many at program point"); | |
1935 | warning_at (point.get_location (), OPT_Wanalyzer_too_complex, | |
1936 | "terminating analysis for this program point"); | |
1937 | return NULL; | |
1938 | } | |
1939 | ||
1940 | ps.validate (m_ext_state); | |
1941 | ||
1942 | /* An exploded_node for "ps" doesn't already exist; create one. */ | |
1943 | exploded_node *node = new exploded_node (ps, m_nodes.length ()); | |
1944 | add_node (node); | |
1945 | m_point_and_state_to_node.put (node->get_ps_key (), node); | |
1946 | ||
1947 | /* Update per-program_point data. */ | |
1948 | per_point_data->m_enodes.safe_push (node); | |
1949 | ||
1950 | const enum point_kind node_pk = node->get_point ().get_kind (); | |
1951 | m_global_stats.m_num_nodes[node_pk]++; | |
1952 | per_fn_stats->m_num_nodes[node_pk]++; | |
1953 | per_cs_stats->m_num_nodes[node_pk]++; | |
1954 | ||
1955 | if (node_pk == PK_AFTER_SUPERNODE) | |
1956 | m_PK_AFTER_SUPERNODE_per_snode[point.get_supernode ()->m_index]++; | |
1957 | ||
1958 | if (logger) | |
1959 | { | |
1960 | format f (false); | |
1961 | pretty_printer *pp = logger->get_printer (); | |
1962 | logger->log ("created EN: %i", node->m_index); | |
1963 | logger->start_log_line (); | |
1964 | pp_string (pp, "point: "); | |
1965 | point.print (pp, f); | |
1966 | logger->end_log_line (); | |
1967 | logger->start_log_line (); | |
1968 | pp_string (pp, "pruned_state: "); | |
1969 | pruned_state.dump_to_pp (m_ext_state, true, pp); | |
1970 | logger->end_log_line (); | |
1971 | } | |
1972 | ||
1973 | /* Add the new node to the worlist. */ | |
1974 | m_worklist.add_node (node); | |
1975 | return node; | |
1976 | } | |
1977 | ||
1978 | /* Add an exploded_edge from SRC to DEST, recording its association | |
1979 | with SEDGE (which may be NULL), and, if non-NULL, taking ownership | |
1980 | of REWIND_INFO. | |
1981 | Return the newly-created eedge. */ | |
1982 | ||
1983 | exploded_edge * | |
1984 | exploded_graph::add_edge (exploded_node *src, exploded_node *dest, | |
1985 | const superedge *sedge, | |
1986 | const state_change &change, | |
1987 | exploded_edge::custom_info_t *custom_info) | |
1988 | { | |
a60d9889 DM |
1989 | exploded_edge *e = new exploded_edge (src, dest, m_ext_state, |
1990 | sedge, change, custom_info); | |
26d949c8 | 1991 | digraph<eg_traits>::add_edge (e); |
757bf1df DM |
1992 | return e; |
1993 | } | |
1994 | ||
1995 | /* Ensure that this graph has per-program_point-data for POINT; | |
1996 | borrow a pointer to it. */ | |
1997 | ||
1998 | per_program_point_data * | |
1999 | exploded_graph:: | |
2000 | get_or_create_per_program_point_data (const program_point &point) | |
2001 | { | |
2002 | if (per_program_point_data **slot = m_per_point_data.get (&point)) | |
2003 | return *slot; | |
2004 | ||
2005 | per_program_point_data *per_point_data = new per_program_point_data (point); | |
2006 | m_per_point_data.put (&per_point_data->m_key, per_point_data); | |
2007 | return per_point_data; | |
2008 | } | |
2009 | ||
2010 | /* Ensure that this graph has per-call_string-data for CS; | |
2011 | borrow a pointer to it. */ | |
2012 | ||
2013 | per_call_string_data * | |
2014 | exploded_graph::get_or_create_per_call_string_data (const call_string &cs) | |
2015 | { | |
2016 | if (per_call_string_data **slot = m_per_call_string_data.get (&cs)) | |
2017 | return *slot; | |
2018 | ||
2019 | per_call_string_data *data = new per_call_string_data (cs, m_sg.num_nodes ()); | |
2020 | m_per_call_string_data.put (&data->m_key, | |
2021 | data); | |
2022 | return data; | |
2023 | } | |
2024 | ||
2025 | /* Ensure that this graph has per-function-data for FUN; | |
2026 | borrow a pointer to it. */ | |
2027 | ||
2028 | per_function_data * | |
2029 | exploded_graph::get_or_create_per_function_data (function *fun) | |
2030 | { | |
2031 | if (per_function_data **slot = m_per_function_data.get (fun)) | |
2032 | return *slot; | |
2033 | ||
2034 | per_function_data *data = new per_function_data (); | |
2035 | m_per_function_data.put (fun, data); | |
2036 | return data; | |
2037 | } | |
2038 | ||
2039 | /* Get this graph's per-function-data for FUN if there is any, | |
2040 | otherwise NULL. */ | |
2041 | ||
2042 | per_function_data * | |
2043 | exploded_graph::get_per_function_data (function *fun) const | |
2044 | { | |
2045 | if (per_function_data **slot | |
2046 | = const_cast <per_function_data_t &> (m_per_function_data).get (fun)) | |
2047 | return *slot; | |
2048 | ||
2049 | return NULL; | |
2050 | } | |
2051 | ||
2052 | /* Return true if NODE and FUN should be traversed directly, rather than | |
2053 | called via other functions. */ | |
2054 | ||
2055 | static bool | |
2056 | toplevel_function_p (cgraph_node *node, function *fun, logger *logger) | |
2057 | { | |
2058 | /* TODO: better logic here | |
2059 | e.g. only if more than one caller, and significantly complicated. | |
2060 | Perhaps some whole-callgraph analysis to decide if it's worth summarizing | |
2061 | an edge, and if so, we need summaries. */ | |
2062 | if (flag_analyzer_call_summaries) | |
2063 | { | |
2064 | int num_call_sites = 0; | |
2065 | for (cgraph_edge *edge = node->callers; edge; edge = edge->next_caller) | |
2066 | ++num_call_sites; | |
2067 | ||
2068 | /* For now, if there's more than one in-edge, and we want call | |
2069 | summaries, do it at the top level so that there's a chance | |
2070 | we'll have a summary when we need one. */ | |
2071 | if (num_call_sites > 1) | |
2072 | { | |
2073 | if (logger) | |
2074 | logger->log ("traversing %qE (%i call sites)", | |
2075 | fun->decl, num_call_sites); | |
2076 | return true; | |
2077 | } | |
2078 | } | |
2079 | ||
2080 | if (!TREE_PUBLIC (fun->decl)) | |
2081 | { | |
2082 | if (logger) | |
2083 | logger->log ("not traversing %qE (static)", fun->decl); | |
2084 | return false; | |
2085 | } | |
2086 | ||
2087 | if (logger) | |
2088 | logger->log ("traversing %qE (all checks passed)", fun->decl); | |
2089 | ||
2090 | return true; | |
2091 | } | |
2092 | ||
2093 | /* Add initial nodes to EG, with entrypoints for externally-callable | |
2094 | functions. */ | |
2095 | ||
2096 | void | |
2097 | exploded_graph::build_initial_worklist () | |
2098 | { | |
2099 | logger * const logger = get_logger (); | |
2100 | LOG_SCOPE (logger); | |
2101 | ||
2102 | cgraph_node *node; | |
2103 | FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) | |
2104 | { | |
2105 | function *fun = node->get_fun (); | |
2106 | if (!toplevel_function_p (node, fun, logger)) | |
2107 | continue; | |
2108 | exploded_node *enode = add_function_entry (fun); | |
2109 | if (logger) | |
2110 | logger->log ("created EN %i for %qE entrypoint", | |
2111 | enode->m_index, fun->decl); | |
2112 | } | |
2113 | } | |
2114 | ||
2115 | /* The main loop of the analysis. | |
2116 | Take freshly-created exploded_nodes from the worklist, calling | |
2117 | process_node on them to explore the <point, state> graph. | |
2118 | Add edges to their successors, potentially creating new successors | |
2119 | (which are also added to the worklist). */ | |
2120 | ||
2121 | void | |
2122 | exploded_graph::process_worklist () | |
2123 | { | |
2124 | logger * const logger = get_logger (); | |
2125 | LOG_SCOPE (logger); | |
2126 | auto_timevar tv (TV_ANALYZER_WORKLIST); | |
2127 | ||
2128 | while (m_worklist.length () > 0) | |
2129 | { | |
2130 | exploded_node *node = m_worklist.take_next (); | |
a4d3bfc0 | 2131 | gcc_assert (node->get_status () == exploded_node::STATUS_WORKLIST); |
757bf1df DM |
2132 | gcc_assert (node->m_succs.length () == 0 |
2133 | || node == m_origin); | |
2134 | ||
2135 | if (logger) | |
2136 | logger->log ("next to process: EN: %i", node->m_index); | |
2137 | ||
2138 | /* Avoid exponential explosions of nodes by attempting to merge | |
2139 | nodes that are at the same program point and which have | |
2140 | sufficiently similar state. */ | |
2141 | if (flag_analyzer_state_merge && node != m_origin) | |
2142 | if (exploded_node *node_2 = m_worklist.peek_next ()) | |
2143 | { | |
a4d3bfc0 DM |
2144 | gcc_assert (node_2->get_status () |
2145 | == exploded_node::STATUS_WORKLIST); | |
757bf1df DM |
2146 | gcc_assert (node->m_succs.length () == 0); |
2147 | gcc_assert (node_2->m_succs.length () == 0); | |
2148 | ||
2149 | gcc_assert (node != node_2); | |
2150 | ||
2151 | if (logger) | |
2152 | logger->log ("peek worklist: EN: %i", node_2->m_index); | |
2153 | ||
2154 | if (node->get_point () == node_2->get_point ()) | |
2155 | { | |
2156 | if (logger) | |
2157 | { | |
2158 | format f (false); | |
2159 | pretty_printer *pp = logger->get_printer (); | |
2160 | logger->start_log_line (); | |
2161 | logger->log_partial | |
2162 | ("got potential merge EN: %i and EN: %i at ", | |
2163 | node->m_index, node_2->m_index); | |
2164 | node->get_point ().print (pp, f); | |
2165 | logger->end_log_line (); | |
2166 | } | |
2167 | ||
2168 | const program_state &state = node->get_state (); | |
2169 | const program_state &state_2 = node_2->get_state (); | |
2170 | ||
2171 | /* They shouldn't be equal, or we wouldn't have two | |
2172 | separate nodes. */ | |
2173 | gcc_assert (state != state_2); | |
2174 | ||
2175 | program_state merged_state (m_ext_state); | |
2176 | state_change change; | |
2177 | if (state.can_merge_with_p (state_2, m_ext_state, | |
2178 | &merged_state)) | |
2179 | { | |
2180 | if (logger) | |
2181 | logger->log ("merging EN: %i and EN: %i", | |
2182 | node->m_index, node_2->m_index); | |
2183 | ||
2184 | if (merged_state == state) | |
2185 | { | |
2186 | /* Then merge node_2 into node by adding an edge. */ | |
2187 | add_edge (node_2, node, NULL, change); | |
2188 | ||
2189 | /* Remove node_2 from the worklist. */ | |
2190 | m_worklist.take_next (); | |
a4d3bfc0 | 2191 | node_2->set_status (exploded_node::STATUS_MERGER); |
757bf1df DM |
2192 | |
2193 | /* Continue processing "node" below. */ | |
2194 | } | |
2195 | else if (merged_state == state_2) | |
2196 | { | |
2197 | /* Then merge node into node_2, and leave node_2 | |
2198 | in the worklist, to be processed on the next | |
2199 | iteration. */ | |
2200 | add_edge (node, node_2, NULL, change); | |
a4d3bfc0 | 2201 | node->set_status (exploded_node::STATUS_MERGER); |
757bf1df DM |
2202 | continue; |
2203 | } | |
2204 | else | |
2205 | { | |
2206 | /* We have a merged state that differs from | |
2207 | both state and state_2. */ | |
2208 | ||
2209 | /* Remove node_2 from the worklist. */ | |
2210 | m_worklist.take_next (); | |
2211 | ||
2212 | /* Create (or get) an exploded node for the merged | |
2213 | states, adding to the worklist. */ | |
2214 | exploded_node *merged_enode | |
2215 | = get_or_create_node (node->get_point (), | |
2216 | merged_state, &change); | |
2217 | if (merged_enode == NULL) | |
2218 | continue; | |
2219 | ||
2220 | if (logger) | |
2221 | logger->log ("merged EN: %i and EN: %i into EN: %i", | |
2222 | node->m_index, node_2->m_index, | |
2223 | merged_enode->m_index); | |
2224 | ||
2225 | /* "node" and "node_2" have both now been removed | |
2226 | from the worklist; we should not process them. | |
2227 | ||
2228 | "merged_enode" may be a new node; if so it will be | |
2229 | processed in a subsequent iteration. | |
2230 | Alternatively, "merged_enode" could be an existing | |
2231 | node; one way the latter can | |
2232 | happen is if we end up merging a succession of | |
2233 | similar nodes into one. */ | |
2234 | ||
2235 | /* If merged_node is one of the two we were merging, | |
2236 | add it back to the worklist to ensure it gets | |
2237 | processed. | |
2238 | ||
2239 | Add edges from the merged nodes to it (but not a | |
2240 | self-edge). */ | |
2241 | if (merged_enode == node) | |
2242 | m_worklist.add_node (merged_enode); | |
2243 | else | |
a4d3bfc0 DM |
2244 | { |
2245 | add_edge (node, merged_enode, NULL, change); | |
2246 | node->set_status (exploded_node::STATUS_MERGER); | |
2247 | } | |
757bf1df DM |
2248 | |
2249 | if (merged_enode == node_2) | |
2250 | m_worklist.add_node (merged_enode); | |
2251 | else | |
a4d3bfc0 DM |
2252 | { |
2253 | add_edge (node_2, merged_enode, NULL, change); | |
2254 | node_2->set_status (exploded_node::STATUS_MERGER); | |
2255 | } | |
757bf1df DM |
2256 | |
2257 | continue; | |
2258 | } | |
2259 | } | |
2260 | ||
2261 | /* TODO: should we attempt more than two nodes, | |
2262 | or just do pairs of nodes? (and hope that we get | |
2263 | a cascade of mergers). */ | |
2264 | } | |
2265 | } | |
2266 | ||
2267 | process_node (node); | |
2268 | ||
2269 | /* Impose a hard limit on the number of exploded nodes, to ensure | |
2270 | that the analysis terminates in the face of pathological state | |
2271 | explosion (or bugs). | |
2272 | ||
2273 | Specifically, the limit is on the number of PK_AFTER_SUPERNODE | |
2274 | exploded nodes, looking at supernode exit events. | |
2275 | ||
2276 | We use exit rather than entry since there can be multiple | |
2277 | entry ENs, one per phi; the number of PK_AFTER_SUPERNODE ought | |
2278 | to be equivalent to the number of supernodes multiplied by the | |
2279 | number of states. */ | |
2280 | const int limit = m_sg.num_nodes () * param_analyzer_bb_explosion_factor; | |
2281 | if (m_global_stats.m_num_nodes[PK_AFTER_SUPERNODE] > limit) | |
2282 | { | |
2283 | if (logger) | |
2284 | logger->log ("bailing out; too many nodes"); | |
2285 | warning_at (node->get_point ().get_location (), | |
2286 | OPT_Wanalyzer_too_complex, | |
2287 | "analysis bailed out early" | |
2288 | " (%i 'after-snode' enodes; %i enodes)", | |
2289 | m_global_stats.m_num_nodes[PK_AFTER_SUPERNODE], | |
2290 | m_nodes.length ()); | |
2291 | return; | |
2292 | } | |
2293 | } | |
2294 | } | |
2295 | ||
2296 | /* Return true if STMT must appear at the start of its exploded node, and | |
2297 | thus we can't consolidate its effects within a run of other statements, | |
2298 | where PREV_STMT was the previous statement. */ | |
2299 | ||
2300 | static bool | |
2301 | stmt_requires_new_enode_p (const gimple *stmt, | |
2302 | const gimple *prev_stmt) | |
2303 | { | |
2304 | /* Stop consolidating at calls to | |
2305 | "__analyzer_dump_exploded_nodes", so they always appear at the | |
2306 | start of an exploded_node. */ | |
2307 | if (const gcall *call = dyn_cast <const gcall *> (stmt)) | |
2308 | if (is_special_named_call_p (call, "__analyzer_dump_exploded_nodes", | |
2309 | 1)) | |
2310 | return true; | |
2311 | ||
2312 | /* If we had a PREV_STMT with an unknown location, and this stmt | |
2313 | has a known location, then if a state change happens here, it | |
2314 | could be consolidated into PREV_STMT, giving us an event with | |
2315 | no location. Ensure that STMT gets its own exploded_node to | |
2316 | avoid this. */ | |
8397af8e DM |
2317 | if (get_pure_location (prev_stmt->location) == UNKNOWN_LOCATION |
2318 | && get_pure_location (stmt->location) != UNKNOWN_LOCATION) | |
757bf1df DM |
2319 | return true; |
2320 | ||
2321 | return false; | |
2322 | } | |
2323 | ||
2324 | /* The core of exploded_graph::process_worklist (the main analysis loop), | |
2325 | handling one node in the worklist. | |
2326 | ||
2327 | Get successor <point, state> pairs for NODE, calling get_or_create on | |
2328 | them, and adding an exploded_edge to each successors. | |
2329 | ||
2330 | Freshly-created nodes will be added to the worklist. */ | |
2331 | ||
2332 | void | |
2333 | exploded_graph::process_node (exploded_node *node) | |
2334 | { | |
2335 | logger * const logger = get_logger (); | |
2336 | LOG_FUNC_1 (logger, "EN: %i", node->m_index); | |
2337 | ||
a4d3bfc0 DM |
2338 | node->set_status (exploded_node::STATUS_PROCESSED); |
2339 | ||
757bf1df DM |
2340 | const program_point &point = node->get_point (); |
2341 | ||
2342 | /* Update cfun and input_location in case of an ICE: make it easier to | |
2343 | track down which source construct we're failing to handle. */ | |
2344 | auto_cfun sentinel (node->get_function ()); | |
2345 | const gimple *stmt = point.get_stmt (); | |
2346 | if (stmt) | |
2347 | input_location = stmt->location; | |
2348 | ||
2349 | const program_state &state = node->get_state (); | |
2350 | if (logger) | |
2351 | { | |
2352 | pretty_printer *pp = logger->get_printer (); | |
2353 | logger->start_log_line (); | |
2354 | pp_string (pp, "point: "); | |
2355 | point.print (pp, format (false)); | |
2356 | pp_string (pp, ", state: "); | |
2357 | state.dump_to_pp (m_ext_state, true, pp); | |
2358 | logger->end_log_line (); | |
2359 | } | |
2360 | ||
2361 | switch (point.get_kind ()) | |
2362 | { | |
2363 | default: | |
2364 | gcc_unreachable (); | |
2365 | case PK_ORIGIN: | |
2366 | /* This node exists to simplify finding the shortest path | |
2367 | to an exploded_node. */ | |
2368 | break; | |
2369 | ||
2370 | case PK_BEFORE_SUPERNODE: | |
2371 | { | |
2372 | program_state next_state (state); | |
2373 | state_change change; | |
2374 | ||
2375 | if (point.get_from_edge ()) | |
2376 | { | |
2377 | impl_region_model_context ctxt (*this, node, | |
2378 | &state, &next_state, &change, | |
2379 | NULL); | |
2380 | const cfg_superedge *last_cfg_superedge | |
2381 | = point.get_from_edge ()->dyn_cast_cfg_superedge (); | |
2382 | if (last_cfg_superedge) | |
2383 | next_state.m_region_model->update_for_phis | |
2384 | (node->get_supernode (), | |
2385 | last_cfg_superedge, | |
2386 | &ctxt); | |
2387 | } | |
2388 | ||
2389 | if (point.get_supernode ()->m_stmts.length () > 0) | |
2390 | { | |
2391 | program_point next_point | |
2392 | = program_point::before_stmt (point.get_supernode (), 0, | |
2393 | point.get_call_string ()); | |
2394 | exploded_node *next | |
2395 | = get_or_create_node (next_point, next_state, &change); | |
2396 | if (next) | |
2397 | add_edge (node, next, NULL, change); | |
2398 | } | |
2399 | else | |
2400 | { | |
2401 | program_point next_point | |
2402 | = program_point::after_supernode (point.get_supernode (), | |
2403 | point.get_call_string ()); | |
2404 | exploded_node *next = get_or_create_node (next_point, next_state, | |
2405 | &change); | |
2406 | if (next) | |
2407 | add_edge (node, next, NULL, change); | |
2408 | } | |
2409 | } | |
2410 | break; | |
2411 | case PK_BEFORE_STMT: | |
2412 | { | |
2413 | /* Determine the effect of a run of one or more statements | |
2414 | within one supernode, generating an edge to the program_point | |
2415 | after the last statement that's processed. | |
2416 | ||
2417 | Stop iterating statements and thus consolidating into one enode | |
2418 | when: | |
2419 | - reaching the end of the statements in the supernode | |
2420 | - if an sm-state-change occurs (so that it gets its own | |
2421 | exploded_node) | |
2422 | - if "-fanalyzer-fine-grained" is active | |
2423 | - encountering certain statements must appear at the start of | |
2424 | their enode (for which stmt_requires_new_enode_p returns true) | |
2425 | ||
2426 | Update next_state in-place, to get the result of the one | |
2427 | or more stmts that are processed. */ | |
2428 | program_state next_state (state); | |
2429 | state_change change; | |
2430 | const supernode *snode = point.get_supernode (); | |
2431 | unsigned stmt_idx; | |
2432 | const gimple *prev_stmt = NULL; | |
2433 | for (stmt_idx = point.get_stmt_idx (); | |
2434 | stmt_idx < snode->m_stmts.length (); | |
2435 | stmt_idx++) | |
2436 | { | |
2437 | const gimple *stmt = snode->m_stmts[stmt_idx]; | |
2438 | ||
2439 | if (stmt_idx > point.get_stmt_idx ()) | |
2440 | if (stmt_requires_new_enode_p (stmt, prev_stmt)) | |
2441 | { | |
2442 | stmt_idx--; | |
2443 | break; | |
2444 | } | |
2445 | prev_stmt = stmt; | |
2446 | ||
2447 | /* Process the stmt. */ | |
2448 | exploded_node::on_stmt_flags flags | |
2449 | = node->on_stmt (*this, snode, stmt, &next_state, &change); | |
2450 | ||
2451 | /* If flags.m_terminate_path, stop analyzing; any nodes/edges | |
2452 | will have been added by on_stmt (e.g. for handling longjmp). */ | |
2453 | if (flags.m_terminate_path) | |
2454 | return; | |
2455 | ||
2456 | if (flags.m_sm_changes || flag_analyzer_fine_grained) | |
2457 | break; | |
2458 | } | |
2459 | unsigned next_idx = stmt_idx + 1; | |
2460 | program_point next_point | |
2461 | = (next_idx < point.get_supernode ()->m_stmts.length () | |
2462 | ? program_point::before_stmt (point.get_supernode (), next_idx, | |
2463 | point.get_call_string ()) | |
2464 | : program_point::after_supernode (point.get_supernode (), | |
2465 | point.get_call_string ())); | |
2466 | exploded_node *next = get_or_create_node (next_point, | |
2467 | next_state, &change); | |
2468 | if (next) | |
2469 | add_edge (node, next, NULL, change); | |
2470 | } | |
2471 | break; | |
2472 | case PK_AFTER_SUPERNODE: | |
2473 | { | |
2474 | /* If this is an EXIT BB, detect leaks, and potentially | |
2475 | create a function summary. */ | |
2476 | if (point.get_supernode ()->return_p ()) | |
2477 | { | |
2478 | node->detect_leaks (*this); | |
2479 | if (flag_analyzer_call_summaries | |
2480 | && point.get_call_string ().empty_p ()) | |
2481 | { | |
2482 | /* TODO: create function summary | |
2483 | There can be more than one; each corresponds to a different | |
2484 | final enode in the function. */ | |
2485 | if (logger) | |
2486 | { | |
2487 | pretty_printer *pp = logger->get_printer (); | |
2488 | logger->start_log_line (); | |
2489 | logger->log_partial | |
2490 | ("would create function summary for %qE; state: ", | |
2491 | point.get_fndecl ()); | |
2492 | state.dump_to_pp (m_ext_state, true, pp); | |
2493 | logger->end_log_line (); | |
2494 | } | |
2495 | per_function_data *per_fn_data | |
2496 | = get_or_create_per_function_data (point.get_function ()); | |
2497 | per_fn_data->add_call_summary (node); | |
2498 | } | |
2499 | } | |
2500 | /* Traverse into successors of the supernode. */ | |
2501 | int i; | |
2502 | superedge *succ; | |
2503 | FOR_EACH_VEC_ELT (point.get_supernode ()->m_succs, i, succ) | |
2504 | { | |
2505 | if (logger) | |
2506 | logger->log ("considering SN: %i -> SN: %i", | |
2507 | succ->m_src->m_index, succ->m_dest->m_index); | |
2508 | ||
2509 | state_change change; | |
2510 | ||
2511 | program_point next_point | |
2512 | = program_point::before_supernode (succ->m_dest, succ, | |
2513 | point.get_call_string ()); | |
2514 | program_state next_state (state); | |
2515 | ||
2516 | if (!node->on_edge (*this, succ, &next_point, &next_state, &change)) | |
2517 | { | |
2518 | if (logger) | |
2519 | logger->log ("skipping impossible edge to SN: %i", | |
2520 | succ->m_dest->m_index); | |
2521 | continue; | |
2522 | } | |
2523 | ||
2524 | exploded_node *next = get_or_create_node (next_point, next_state, | |
2525 | &change); | |
2526 | if (next) | |
2527 | add_edge (node, next, succ, change); | |
2528 | } | |
2529 | } | |
2530 | break; | |
2531 | } | |
2532 | } | |
2533 | ||
2534 | /* Ensure that this graph has a stats instance for FN, return it. | |
2535 | FN can be NULL, in which case a stats instances is returned covering | |
2536 | "functionless" parts of the graph (the origin node). */ | |
2537 | ||
2538 | stats * | |
2539 | exploded_graph::get_or_create_function_stats (function *fn) | |
2540 | { | |
2541 | if (!fn) | |
2542 | return &m_functionless_stats; | |
2543 | ||
2544 | if (stats **slot = m_per_function_stats.get (fn)) | |
2545 | return *slot; | |
2546 | else | |
2547 | { | |
2548 | int num_supernodes = fn ? n_basic_blocks_for_fn (fn) : 0; | |
2549 | /* not quite the num supernodes, but nearly. */ | |
2550 | stats *new_stats = new stats (num_supernodes); | |
2551 | m_per_function_stats.put (fn, new_stats); | |
2552 | return new_stats; | |
2553 | } | |
2554 | } | |
2555 | ||
2556 | /* Write all stats information to this graph's logger, if any. */ | |
2557 | ||
2558 | void | |
2559 | exploded_graph::log_stats () const | |
2560 | { | |
2561 | logger * const logger = get_logger (); | |
2562 | if (!logger) | |
2563 | return; | |
2564 | ||
2565 | LOG_SCOPE (logger); | |
2566 | ||
2567 | logger->log ("m_sg.num_nodes (): %i", m_sg.num_nodes ()); | |
2568 | logger->log ("m_nodes.length (): %i", m_nodes.length ()); | |
2569 | logger->log ("m_edges.length (): %i", m_edges.length ()); | |
2570 | ||
2571 | logger->log ("global stats:"); | |
2572 | m_global_stats.log (logger); | |
2573 | ||
2574 | for (function_stat_map_t::iterator iter = m_per_function_stats.begin (); | |
2575 | iter != m_per_function_stats.end (); | |
2576 | ++iter) | |
2577 | { | |
2578 | function *fn = (*iter).first; | |
2579 | log_scope s (logger, function_name (fn)); | |
2580 | (*iter).second->log (logger); | |
2581 | } | |
2582 | } | |
2583 | ||
2584 | /* Dump all stats information to OUT. */ | |
2585 | ||
2586 | void | |
2587 | exploded_graph::dump_stats (FILE *out) const | |
2588 | { | |
2589 | fprintf (out, "m_sg.num_nodes (): %i\n", m_sg.num_nodes ()); | |
2590 | fprintf (out, "m_nodes.length (): %i\n", m_nodes.length ()); | |
2591 | fprintf (out, "m_edges.length (): %i\n", m_edges.length ()); | |
2592 | ||
2593 | fprintf (out, "global stats:\n"); | |
2594 | m_global_stats.dump (out); | |
2595 | ||
2596 | for (function_stat_map_t::iterator iter = m_per_function_stats.begin (); | |
2597 | iter != m_per_function_stats.end (); | |
2598 | ++iter) | |
2599 | { | |
2600 | function *fn = (*iter).first; | |
2601 | fprintf (out, "function: %s\n", function_name (fn)); | |
2602 | (*iter).second->dump (out); | |
2603 | } | |
2604 | ||
2605 | fprintf (out, "PK_AFTER_SUPERNODE per supernode:\n"); | |
2606 | for (unsigned i = 0; i < m_PK_AFTER_SUPERNODE_per_snode.length (); i++) | |
2607 | fprintf (out, " SN %i: %3i\n", i, m_PK_AFTER_SUPERNODE_per_snode[i]); | |
2608 | } | |
2609 | ||
2610 | void | |
2611 | exploded_graph::dump_states_for_supernode (FILE *out, | |
2612 | const supernode *snode) const | |
2613 | { | |
2614 | fprintf (out, "PK_AFTER_SUPERNODE nodes for SN: %i\n", snode->m_index); | |
2615 | int i; | |
2616 | exploded_node *enode; | |
2617 | int state_idx = 0; | |
2618 | FOR_EACH_VEC_ELT (m_nodes, i, enode) | |
2619 | { | |
2620 | const supernode *iter_snode = enode->get_supernode (); | |
2621 | if (enode->get_point ().get_kind () == PK_AFTER_SUPERNODE | |
2622 | && iter_snode == snode) | |
2623 | { | |
2624 | pretty_printer pp; | |
2625 | pp_format_decoder (&pp) = default_tree_printer; | |
2626 | enode->get_state ().dump_to_pp (m_ext_state, true, &pp); | |
2627 | fprintf (out, "state %i: EN: %i\n %s\n", | |
2628 | state_idx++, enode->m_index, | |
2629 | pp_formatted_text (&pp)); | |
2630 | } | |
2631 | } | |
2632 | fprintf (out, "#exploded_node for PK_AFTER_SUPERNODE for SN: %i = %i\n", | |
2633 | snode->m_index, state_idx); | |
2634 | } | |
2635 | ||
2636 | /* Look for the last use of SEARCH_STMT within this path. | |
2637 | If found write the edge's index to *OUT_IDX and return true, otherwise | |
2638 | return false. */ | |
2639 | ||
2640 | bool | |
2641 | exploded_path::find_stmt_backwards (const gimple *search_stmt, | |
2642 | int *out_idx) const | |
2643 | { | |
2644 | int i; | |
2645 | const exploded_edge *eedge; | |
2646 | FOR_EACH_VEC_ELT_REVERSE (m_edges, i, eedge) | |
2647 | { | |
2648 | const exploded_node *dst_node = eedge->m_dest; | |
2649 | const program_point &dst_point = dst_node->get_point (); | |
2650 | const gimple *stmt = dst_point.get_stmt (); | |
2651 | if (stmt == search_stmt) | |
2652 | { | |
2653 | *out_idx = i; | |
2654 | return true; | |
2655 | } | |
2656 | } | |
2657 | return false; | |
2658 | } | |
2659 | ||
2660 | /* Get the final exploded_node in this path, which must be non-empty. */ | |
2661 | ||
2662 | exploded_node * | |
2663 | exploded_path::get_final_enode () const | |
2664 | { | |
2665 | gcc_assert (m_edges.length () > 0); | |
2666 | return m_edges[m_edges.length () - 1]->m_dest; | |
2667 | } | |
2668 | ||
2669 | /* Check state along this path, returning true if it is feasible. */ | |
2670 | ||
2671 | bool | |
2672 | exploded_path::feasible_p (logger *logger) const | |
2673 | { | |
2674 | LOG_SCOPE (logger); | |
2675 | ||
2676 | /* Traverse the path, updating this model. */ | |
2677 | region_model model; | |
2678 | for (unsigned i = 0; i < m_edges.length (); i++) | |
2679 | { | |
2680 | const exploded_edge *eedge = m_edges[i]; | |
2681 | if (logger) | |
2682 | logger->log ("considering edge %i: EN:%i -> EN:%i", | |
2683 | i, | |
2684 | eedge->m_src->m_index, | |
2685 | eedge->m_dest->m_index); | |
2686 | const exploded_node &src_enode = *eedge->m_src; | |
2687 | const program_point &src_point = src_enode.get_point (); | |
2688 | if (logger) | |
2689 | { | |
2690 | logger->start_log_line (); | |
2691 | src_point.print (logger->get_printer (), format (false)); | |
2692 | logger->end_log_line (); | |
2693 | } | |
2694 | ||
2695 | if (const gimple *stmt = src_point.get_stmt ()) | |
2696 | { | |
2697 | /* Update cfun and input_location in case of ICE: make it easier to | |
2698 | track down which source construct we're failing to handle. */ | |
2699 | auto_cfun sentinel (src_point.get_function ()); | |
2700 | input_location = stmt->location; | |
2701 | ||
2702 | if (const gassign *assign = dyn_cast <const gassign *> (stmt)) | |
2703 | model.on_assignment (assign, NULL); | |
2704 | else if (const greturn *return_ = dyn_cast <const greturn *> (stmt)) | |
2705 | model.on_return (return_, NULL); | |
2706 | } | |
2707 | ||
2708 | const superedge *sedge = eedge->m_sedge; | |
2709 | if (sedge) | |
2710 | { | |
2711 | if (logger) | |
2712 | logger->log (" sedge: SN:%i -> SN:%i %s", | |
2713 | sedge->m_src->m_index, | |
2714 | sedge->m_dest->m_index, | |
2715 | sedge->get_description (false)); | |
2716 | ||
2717 | const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt (); | |
2718 | if (!model.maybe_update_for_edge (*sedge, last_stmt, NULL)) | |
2719 | { | |
2720 | if (logger) | |
2721 | { | |
2722 | logger->log ("rejecting due to region model"); | |
2723 | model.dump_to_pp (logger->get_printer (), false); | |
2724 | } | |
2725 | return false; | |
2726 | } | |
2727 | } | |
2728 | else | |
2729 | { | |
2730 | /* Special-case the initial eedge from the origin node to the | |
2731 | initial function by pushing a frame for it. */ | |
2732 | if (i == 0) | |
2733 | { | |
2734 | gcc_assert (eedge->m_src->m_index == 0); | |
2735 | gcc_assert (src_point.get_kind () == PK_ORIGIN); | |
2736 | gcc_assert (eedge->m_dest->get_point ().get_kind () | |
2737 | == PK_BEFORE_SUPERNODE); | |
2738 | function *fun = eedge->m_dest->get_function (); | |
2739 | gcc_assert (fun); | |
2740 | model.push_frame (fun, NULL, NULL); | |
2741 | if (logger) | |
2742 | logger->log (" pushing frame for %qD", fun->decl); | |
2743 | } | |
2744 | else if (eedge->m_custom_info) | |
2745 | eedge->m_custom_info->update_model (&model, *eedge); | |
2746 | } | |
2747 | ||
2748 | /* Handle phi nodes on an edge leaving a PK_BEFORE_SUPERNODE (to | |
2749 | a PK_BEFORE_STMT, or a PK_AFTER_SUPERNODE if no stmts). | |
2750 | This will typically not be associated with a superedge. */ | |
2751 | if (src_point.get_from_edge ()) | |
2752 | { | |
2753 | const cfg_superedge *last_cfg_superedge | |
2754 | = src_point.get_from_edge ()->dyn_cast_cfg_superedge (); | |
2755 | if (last_cfg_superedge) | |
2756 | { | |
2757 | if (logger) | |
2758 | logger->log (" update for phis"); | |
2759 | model.update_for_phis (src_enode.get_supernode (), | |
2760 | last_cfg_superedge, | |
2761 | NULL); | |
2762 | } | |
2763 | } | |
2764 | ||
2765 | if (logger) | |
2766 | { | |
2767 | logger->log ("state after edge %i: EN:%i -> EN:%i", | |
2768 | i, | |
2769 | eedge->m_src->m_index, | |
2770 | eedge->m_dest->m_index); | |
2771 | logger->start_log_line (); | |
2772 | model.dump_to_pp (logger->get_printer (), true); | |
2773 | logger->end_log_line (); | |
2774 | } | |
2775 | } | |
2776 | ||
2777 | return true; | |
2778 | } | |
2779 | ||
2780 | /* Dump this path in multiline form to PP. */ | |
2781 | ||
2782 | void | |
2783 | exploded_path::dump_to_pp (pretty_printer *pp) const | |
2784 | { | |
2785 | for (unsigned i = 0; i < m_edges.length (); i++) | |
2786 | { | |
2787 | const exploded_edge *eedge = m_edges[i]; | |
2788 | pp_printf (pp, "m_edges[%i]: EN %i -> EN %i", | |
2789 | i, | |
2790 | eedge->m_src->m_index, | |
2791 | eedge->m_dest->m_index); | |
2792 | pp_newline (pp); | |
2793 | } | |
2794 | } | |
2795 | ||
2796 | /* Dump this path in multiline form to FP. */ | |
2797 | ||
2798 | void | |
2799 | exploded_path::dump (FILE *fp) const | |
2800 | { | |
2801 | pretty_printer pp; | |
2802 | pp_format_decoder (&pp) = default_tree_printer; | |
2803 | pp_show_color (&pp) = pp_show_color (global_dc->printer); | |
2804 | pp.buffer->stream = fp; | |
2805 | dump_to_pp (&pp); | |
2806 | pp_flush (&pp); | |
2807 | } | |
2808 | ||
2809 | /* Dump this path in multiline form to stderr. */ | |
2810 | ||
2811 | DEBUG_FUNCTION void | |
2812 | exploded_path::dump () const | |
2813 | { | |
2814 | dump (stderr); | |
2815 | } | |
2816 | ||
2817 | /* A family of cluster subclasses for use when generating .dot output for | |
2818 | exploded graphs (-fdump-analyzer-exploded-graph), for grouping the | |
2819 | enodes into hierarchical boxes. | |
2820 | ||
2821 | All functionless enodes appear in the top-level graph. | |
2822 | Every (function, call_string) pair gets its own cluster. Within that | |
2823 | cluster, each supernode gets its own cluster. | |
2824 | ||
2825 | Hence all enodes relating to a particular function with a particular | |
2826 | callstring will be be in a cluster together; all enodes for the same | |
2827 | function but with a different callstring will be in a different | |
2828 | cluster. */ | |
2829 | ||
2830 | /* Base class of cluster for clustering exploded_node instances in .dot | |
2831 | output, based on various subclass-specific criteria. */ | |
2832 | ||
2833 | class exploded_cluster : public cluster<eg_traits> | |
2834 | { | |
2835 | }; | |
2836 | ||
2837 | /* Cluster containing all exploded_node instances for one supernode. */ | |
2838 | ||
2839 | class supernode_cluster : public exploded_cluster | |
2840 | { | |
2841 | public: | |
2842 | supernode_cluster (const supernode *supernode) : m_supernode (supernode) {} | |
2843 | ||
2844 | // TODO: dtor? | |
2845 | ||
2846 | void dump_dot (graphviz_out *gv, const dump_args_t &args) const FINAL OVERRIDE | |
2847 | { | |
2848 | gv->println ("subgraph \"cluster_supernode_%p\" {", | |
2849 | (const void *)this); | |
2850 | gv->indent (); | |
2851 | gv->println ("style=\"dashed\";"); | |
73f38658 DM |
2852 | gv->println ("label=\"SN: %i (bb: %i)\";", |
2853 | m_supernode->m_index, m_supernode->m_bb->index); | |
757bf1df DM |
2854 | |
2855 | int i; | |
2856 | exploded_node *enode; | |
2857 | FOR_EACH_VEC_ELT (m_enodes, i, enode) | |
2858 | enode->dump_dot (gv, args); | |
2859 | ||
2860 | /* Terminate subgraph. */ | |
2861 | gv->outdent (); | |
2862 | gv->println ("}"); | |
2863 | } | |
2864 | ||
2865 | void add_node (exploded_node *en) FINAL OVERRIDE | |
2866 | { | |
2867 | m_enodes.safe_push (en); | |
2868 | } | |
2869 | ||
2870 | private: | |
2871 | const supernode *m_supernode; | |
2872 | auto_vec <exploded_node *> m_enodes; | |
2873 | }; | |
2874 | ||
2875 | /* Cluster containing all supernode_cluster instances for one | |
2876 | (function, call_string) pair. */ | |
2877 | ||
2878 | class function_call_string_cluster : public exploded_cluster | |
2879 | { | |
2880 | public: | |
2881 | function_call_string_cluster (function *fun, call_string cs) | |
2882 | : m_fun (fun), m_cs (cs) {} | |
2883 | ||
2884 | ~function_call_string_cluster () | |
2885 | { | |
2886 | for (map_t::iterator iter = m_map.begin (); | |
2887 | iter != m_map.end (); | |
2888 | ++iter) | |
2889 | delete (*iter).second; | |
2890 | } | |
2891 | ||
2892 | void dump_dot (graphviz_out *gv, const dump_args_t &args) const FINAL OVERRIDE | |
2893 | { | |
2894 | const char *funcname = function_name (m_fun); | |
2895 | ||
2896 | gv->println ("subgraph \"cluster_function_%p\" {", (const void *)this); | |
2897 | gv->indent (); | |
2898 | gv->write_indent (); | |
2899 | gv->print ("label=\"call string: "); | |
2900 | m_cs.print (gv->get_pp ()); | |
2901 | gv->print (" function: %s \";", funcname); | |
2902 | gv->print ("\n"); | |
2903 | ||
2904 | for (map_t::iterator iter = m_map.begin (); | |
2905 | iter != m_map.end (); | |
2906 | ++iter) | |
2907 | (*iter).second->dump_dot (gv, args); | |
2908 | ||
2909 | /* Terminate subgraph. */ | |
2910 | gv->outdent (); | |
2911 | gv->println ("}"); | |
2912 | } | |
2913 | ||
2914 | void add_node (exploded_node *en) FINAL OVERRIDE | |
2915 | { | |
2916 | const supernode *supernode = en->get_supernode (); | |
2917 | gcc_assert (supernode); | |
2918 | supernode_cluster **slot = m_map.get (supernode); | |
2919 | if (slot) | |
2920 | (*slot)->add_node (en); | |
2921 | else | |
2922 | { | |
2923 | supernode_cluster *child = new supernode_cluster (supernode); | |
2924 | m_map.put (supernode, child); | |
2925 | child->add_node (en); | |
2926 | } | |
2927 | } | |
2928 | ||
2929 | private: | |
2930 | function *m_fun; | |
2931 | call_string m_cs; | |
2932 | typedef ordered_hash_map<const supernode *, supernode_cluster *> map_t; | |
2933 | map_t m_map; | |
2934 | }; | |
2935 | ||
2936 | /* Keys for root_cluster. */ | |
2937 | ||
2938 | struct function_call_string | |
2939 | { | |
2940 | function_call_string (function *fun, call_string cs) | |
2941 | : m_fun (fun), m_cs (cs) | |
2942 | { | |
2943 | gcc_assert (fun); | |
2944 | } | |
2945 | ||
2946 | function *m_fun; | |
2947 | call_string m_cs; | |
2948 | }; | |
2949 | ||
75038aa6 DM |
2950 | } // namespace ana |
2951 | ||
757bf1df DM |
2952 | template <> struct default_hash_traits<function_call_string> |
2953 | : public pod_hash_traits<function_call_string> | |
2954 | { | |
2955 | static const bool empty_zero_p = false; | |
2956 | }; | |
2957 | ||
2958 | template <> | |
2959 | inline hashval_t | |
2960 | pod_hash_traits<function_call_string>::hash (value_type v) | |
2961 | { | |
2962 | return pointer_hash <function>::hash (v.m_fun) ^ v.m_cs.hash (); | |
2963 | } | |
2964 | ||
2965 | template <> | |
2966 | inline bool | |
2967 | pod_hash_traits<function_call_string>::equal (const value_type &existing, | |
2968 | const value_type &candidate) | |
2969 | { | |
2970 | return existing.m_fun == candidate.m_fun && existing.m_cs == candidate.m_cs; | |
2971 | } | |
2972 | template <> | |
2973 | inline void | |
2974 | pod_hash_traits<function_call_string>::mark_deleted (value_type &v) | |
2975 | { | |
2976 | v.m_fun = reinterpret_cast<function *> (1); | |
2977 | } | |
2978 | template <> | |
2979 | inline void | |
2980 | pod_hash_traits<function_call_string>::mark_empty (value_type &v) | |
2981 | { | |
1dae549d | 2982 | v.m_fun = NULL; |
757bf1df DM |
2983 | } |
2984 | template <> | |
2985 | inline bool | |
2986 | pod_hash_traits<function_call_string>::is_deleted (value_type v) | |
2987 | { | |
2988 | return v.m_fun == reinterpret_cast<function *> (1); | |
2989 | } | |
2990 | template <> | |
2991 | inline bool | |
2992 | pod_hash_traits<function_call_string>::is_empty (value_type v) | |
2993 | { | |
1dae549d | 2994 | return v.m_fun == NULL; |
757bf1df DM |
2995 | } |
2996 | ||
75038aa6 DM |
2997 | namespace ana { |
2998 | ||
757bf1df DM |
2999 | /* Top-level cluster for generating .dot output for exploded graphs, |
3000 | handling the functionless nodes, and grouping the remaining nodes by | |
3001 | callstring. */ | |
3002 | ||
3003 | class root_cluster : public exploded_cluster | |
3004 | { | |
3005 | public: | |
3006 | ~root_cluster () | |
3007 | { | |
3008 | for (map_t::iterator iter = m_map.begin (); | |
3009 | iter != m_map.end (); | |
3010 | ++iter) | |
3011 | delete (*iter).second; | |
3012 | } | |
3013 | ||
3014 | void dump_dot (graphviz_out *gv, const dump_args_t &args) const FINAL OVERRIDE | |
3015 | { | |
3016 | int i; | |
3017 | exploded_node *enode; | |
3018 | FOR_EACH_VEC_ELT (m_functionless_enodes, i, enode) | |
3019 | enode->dump_dot (gv, args); | |
3020 | ||
3021 | for (map_t::iterator iter = m_map.begin (); | |
3022 | iter != m_map.end (); | |
3023 | ++iter) | |
3024 | (*iter).second->dump_dot (gv, args); | |
3025 | } | |
3026 | ||
3027 | void add_node (exploded_node *en) FINAL OVERRIDE | |
3028 | { | |
3029 | function *fun = en->get_function (); | |
3030 | if (!fun) | |
3031 | { | |
3032 | m_functionless_enodes.safe_push (en); | |
3033 | return; | |
3034 | } | |
3035 | ||
3036 | const call_string &cs = en->get_point ().get_call_string (); | |
3037 | function_call_string key (fun, cs); | |
3038 | function_call_string_cluster **slot = m_map.get (key); | |
3039 | if (slot) | |
3040 | (*slot)->add_node (en); | |
3041 | else | |
3042 | { | |
3043 | function_call_string_cluster *child | |
3044 | = new function_call_string_cluster (fun, cs); | |
3045 | m_map.put (key, child); | |
3046 | child->add_node (en); | |
3047 | } | |
3048 | } | |
3049 | ||
3050 | private: | |
3051 | /* This can't be an ordered_hash_map, as we can't store vec<call_string>, | |
3052 | since it's not a POD; vec<>::quick_push has: | |
3053 | *slot = obj; | |
3054 | and the slot isn't initialized, so the assignment op dies when cleaning up | |
3055 | un-inited *slot (within the truncate call). */ | |
3056 | typedef hash_map<function_call_string, function_call_string_cluster *> map_t; | |
3057 | map_t m_map; | |
3058 | ||
3059 | /* This should just be the origin exploded_node. */ | |
3060 | auto_vec <exploded_node *> m_functionless_enodes; | |
3061 | }; | |
3062 | ||
3063 | /* Subclass of range_label for use within | |
3064 | exploded_graph::dump_exploded_nodes for implementing | |
3065 | -fdump-analyzer-exploded-nodes: a label for a specific | |
3066 | exploded_node. */ | |
3067 | ||
3068 | class enode_label : public range_label | |
3069 | { | |
3070 | public: | |
3071 | enode_label (const extrinsic_state &ext_state, | |
3072 | exploded_node *enode) | |
3073 | : m_ext_state (ext_state), m_enode (enode) {} | |
3074 | ||
3075 | label_text get_text (unsigned) const FINAL OVERRIDE | |
3076 | { | |
3077 | pretty_printer pp; | |
3078 | pp_format_decoder (&pp) = default_tree_printer; | |
3079 | m_enode->get_state ().dump_to_pp (m_ext_state, true, &pp); | |
3080 | return make_label_text (false, "EN: %i: %s", | |
3081 | m_enode->m_index, pp_formatted_text (&pp)); | |
3082 | } | |
3083 | ||
3084 | private: | |
3085 | const extrinsic_state &m_ext_state; | |
3086 | exploded_node *m_enode; | |
3087 | }; | |
3088 | ||
3089 | /* Postprocessing support for dumping the exploded nodes. | |
3090 | Handle -fdump-analyzer-exploded-nodes, | |
3091 | -fdump-analyzer-exploded-nodes-2, and the | |
3092 | "__analyzer_dump_exploded_nodes" builtin. */ | |
3093 | ||
3094 | void | |
3095 | exploded_graph::dump_exploded_nodes () const | |
3096 | { | |
3097 | // TODO | |
3098 | /* Locate calls to __analyzer_dump_exploded_nodes. */ | |
3099 | // Print how many egs there are for them? | |
3100 | /* Better: log them as we go, and record the exploded nodes | |
3101 | in question. */ | |
3102 | ||
3103 | /* Show every enode. */ | |
3104 | ||
3105 | /* Gather them by stmt, so that we can more clearly see the | |
3106 | "hotspots" requiring numerous exploded nodes. */ | |
3107 | ||
3108 | /* Alternatively, simply throw them all into one big rich_location | |
3109 | and see if the label-printing will sort it out... | |
3110 | This requires them all to be in the same source file. */ | |
3111 | ||
3112 | if (flag_dump_analyzer_exploded_nodes) | |
3113 | { | |
3114 | auto_timevar tv (TV_ANALYZER_DUMP); | |
3115 | gcc_rich_location richloc (UNKNOWN_LOCATION); | |
3116 | unsigned i; | |
3117 | exploded_node *enode; | |
3118 | FOR_EACH_VEC_ELT (m_nodes, i, enode) | |
3119 | { | |
3120 | if (const gimple *stmt = enode->get_stmt ()) | |
3121 | { | |
8397af8e | 3122 | if (get_pure_location (richloc.get_loc ()) == UNKNOWN_LOCATION) |
757bf1df DM |
3123 | richloc.set_range (0, stmt->location, SHOW_RANGE_WITH_CARET); |
3124 | else | |
3125 | richloc.add_range (stmt->location, | |
3126 | SHOW_RANGE_WITHOUT_CARET, | |
3127 | new enode_label (m_ext_state, enode)); | |
3128 | } | |
3129 | } | |
3130 | warning_at (&richloc, 0, "%i exploded nodes", m_nodes.length ()); | |
3131 | ||
3132 | /* Repeat the warning without all the labels, so that message is visible | |
3133 | (the other one may well have scrolled past the terminal limit). */ | |
3134 | warning_at (richloc.get_loc (), 0, | |
3135 | "%i exploded nodes", m_nodes.length ()); | |
3136 | ||
3137 | if (m_worklist.length () > 0) | |
3138 | warning_at (richloc.get_loc (), 0, | |
3139 | "worklist still contains %i nodes", m_worklist.length ()); | |
3140 | } | |
3141 | ||
3142 | /* Dump the egraph in textual form to a dump file. */ | |
3143 | if (flag_dump_analyzer_exploded_nodes_2) | |
3144 | { | |
3145 | auto_timevar tv (TV_ANALYZER_DUMP); | |
3146 | char *filename | |
3147 | = concat (dump_base_name, ".eg.txt", NULL); | |
3148 | FILE *outf = fopen (filename, "w"); | |
3149 | if (!outf) | |
3150 | error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename); | |
3151 | free (filename); | |
3152 | ||
3153 | fprintf (outf, "exploded graph for %s\n", dump_base_name); | |
3154 | fprintf (outf, " nodes: %i\n", m_nodes.length ()); | |
3155 | fprintf (outf, " edges: %i\n", m_edges.length ()); | |
3156 | ||
3157 | unsigned i; | |
3158 | exploded_node *enode; | |
3159 | FOR_EACH_VEC_ELT (m_nodes, i, enode) | |
3160 | { | |
3161 | fprintf (outf, "\nEN %i:\n", enode->m_index); | |
3162 | enode->dump_succs_and_preds (outf); | |
3163 | pretty_printer pp; | |
3164 | enode->get_point ().print (&pp, format (true)); | |
3165 | fprintf (outf, "%s\n", pp_formatted_text (&pp)); | |
3166 | enode->get_state ().dump_to_file (m_ext_state, false, outf); | |
3167 | } | |
3168 | ||
3169 | fclose (outf); | |
3170 | } | |
3171 | ||
3172 | /* Dump the egraph in textual form to multiple dump files, one per enode. */ | |
3173 | if (flag_dump_analyzer_exploded_nodes_3) | |
3174 | { | |
3175 | auto_timevar tv (TV_ANALYZER_DUMP); | |
3176 | ||
3177 | unsigned i; | |
3178 | exploded_node *enode; | |
3179 | FOR_EACH_VEC_ELT (m_nodes, i, enode) | |
3180 | { | |
3181 | char *filename | |
3182 | = xasprintf ("%s.en-%i.txt", dump_base_name, i); | |
3183 | FILE *outf = fopen (filename, "w"); | |
3184 | if (!outf) | |
3185 | error_at (UNKNOWN_LOCATION, "unable to open %qs for writing", filename); | |
3186 | free (filename); | |
3187 | ||
3188 | fprintf (outf, "EN %i:\n", enode->m_index); | |
3189 | enode->dump_succs_and_preds (outf); | |
3190 | pretty_printer pp; | |
3191 | enode->get_point ().print (&pp, format (true)); | |
3192 | fprintf (outf, "%s\n", pp_formatted_text (&pp)); | |
3193 | enode->get_state ().dump_to_file (m_ext_state, false, outf); | |
3194 | ||
3195 | fclose (outf); | |
3196 | } | |
3197 | } | |
3198 | ||
3199 | /* Emit a warning at any call to "__analyzer_dump_exploded_nodes", | |
a4d3bfc0 | 3200 | giving the number of processed exploded nodes for "before-stmt", |
a0e4929b | 3201 | and the IDs of processed, merger, and worklist enodes. |
a4d3bfc0 DM |
3202 | |
3203 | We highlight the count of *processed* enodes since this is of most | |
3204 | interest in DejaGnu tests for ensuring that state merger has | |
3205 | happened. | |
3206 | ||
a0e4929b DM |
3207 | We don't show the count of merger and worklist enodes, as this is |
3208 | more of an implementation detail of the merging/worklist that we | |
3209 | don't want to bake into our expected DejaGnu messages. */ | |
757bf1df DM |
3210 | |
3211 | unsigned i; | |
3212 | exploded_node *enode; | |
3213 | hash_set<const gimple *> seen; | |
3214 | FOR_EACH_VEC_ELT (m_nodes, i, enode) | |
3215 | { | |
3216 | if (enode->get_point ().get_kind () != PK_BEFORE_STMT) | |
3217 | continue; | |
3218 | ||
3219 | if (const gimple *stmt = enode->get_stmt ()) | |
3220 | if (const gcall *call = dyn_cast <const gcall *> (stmt)) | |
3221 | if (is_special_named_call_p (call, "__analyzer_dump_exploded_nodes", | |
3222 | 1)) | |
3223 | { | |
3224 | if (seen.contains (stmt)) | |
3225 | continue; | |
3226 | ||
a4d3bfc0 DM |
3227 | auto_vec<exploded_node *> processed_enodes; |
3228 | auto_vec<exploded_node *> merger_enodes; | |
a0e4929b | 3229 | auto_vec<exploded_node *> worklist_enodes; |
757bf1df DM |
3230 | /* This is O(N^2). */ |
3231 | unsigned j; | |
757bf1df DM |
3232 | exploded_node *other_enode; |
3233 | FOR_EACH_VEC_ELT (m_nodes, j, other_enode) | |
3234 | { | |
3235 | if (other_enode->get_point ().get_kind () != PK_BEFORE_STMT) | |
3236 | continue; | |
3237 | if (other_enode->get_stmt () == stmt) | |
a4d3bfc0 DM |
3238 | switch (other_enode->get_status ()) |
3239 | { | |
3240 | default: | |
3241 | gcc_unreachable (); | |
a0e4929b DM |
3242 | case exploded_node::STATUS_WORKLIST: |
3243 | worklist_enodes.safe_push (other_enode); | |
3244 | break; | |
a4d3bfc0 DM |
3245 | case exploded_node::STATUS_PROCESSED: |
3246 | processed_enodes.safe_push (other_enode); | |
3247 | break; | |
3248 | case exploded_node::STATUS_MERGER: | |
3249 | merger_enodes.safe_push (other_enode); | |
3250 | break; | |
3251 | } | |
757bf1df DM |
3252 | } |
3253 | ||
3254 | pretty_printer pp; | |
a4d3bfc0 DM |
3255 | pp_character (&pp, '['); |
3256 | print_enode_indices (&pp, processed_enodes); | |
3257 | if (merger_enodes.length () > 0) | |
3258 | { | |
3259 | pp_string (&pp, "] merger(s): ["); | |
3260 | print_enode_indices (&pp, merger_enodes); | |
3261 | } | |
a0e4929b DM |
3262 | if (worklist_enodes.length () > 0) |
3263 | { | |
3264 | pp_string (&pp, "] worklist: ["); | |
3265 | print_enode_indices (&pp, worklist_enodes); | |
3266 | } | |
a4d3bfc0 | 3267 | pp_character (&pp, ']'); |
757bf1df | 3268 | |
a4d3bfc0 DM |
3269 | warning_n (stmt->location, 0, processed_enodes.length (), |
3270 | "%i processed enode: %s", | |
3271 | "%i processed enodes: %s", | |
3272 | processed_enodes.length (), pp_formatted_text (&pp)); | |
757bf1df DM |
3273 | seen.add (stmt); |
3274 | ||
3275 | /* If the argument is non-zero, then print all of the states | |
3276 | of the various enodes. */ | |
3277 | tree t_arg = fold (gimple_call_arg (call, 0)); | |
3278 | if (TREE_CODE (t_arg) != INTEGER_CST) | |
3279 | { | |
3280 | error_at (call->location, | |
3281 | "integer constant required for arg 1"); | |
3282 | return; | |
3283 | } | |
3284 | int i_arg = TREE_INT_CST_LOW (t_arg); | |
3285 | if (i_arg) | |
3286 | { | |
3287 | exploded_node *other_enode; | |
a4d3bfc0 | 3288 | FOR_EACH_VEC_ELT (processed_enodes, j, other_enode) |
757bf1df DM |
3289 | { |
3290 | fprintf (stderr, "%i of %i: EN %i:\n", | |
a4d3bfc0 DM |
3291 | j + 1, processed_enodes.length (), |
3292 | other_enode->m_index); | |
757bf1df DM |
3293 | other_enode->dump_succs_and_preds (stderr); |
3294 | /* Dump state. */ | |
3295 | other_enode->get_state ().dump (m_ext_state, false); | |
3296 | } | |
3297 | } | |
3298 | } | |
3299 | } | |
3300 | } | |
3301 | ||
3302 | /* A collection of classes for visualizing the callgraph in .dot form | |
3303 | (as represented in the supergraph). */ | |
3304 | ||
3305 | /* Forward decls. */ | |
3306 | class viz_callgraph_node; | |
3307 | class viz_callgraph_edge; | |
3308 | class viz_callgraph; | |
3309 | class viz_callgraph_cluster; | |
3310 | ||
3311 | /* Traits for using "digraph.h" to visualize the callgraph. */ | |
3312 | ||
3313 | struct viz_callgraph_traits | |
3314 | { | |
3315 | typedef viz_callgraph_node node_t; | |
3316 | typedef viz_callgraph_edge edge_t; | |
3317 | typedef viz_callgraph graph_t; | |
3318 | struct dump_args_t | |
3319 | { | |
3320 | dump_args_t (const exploded_graph *eg) : m_eg (eg) {} | |
3321 | const exploded_graph *m_eg; | |
3322 | }; | |
3323 | typedef viz_callgraph_cluster cluster_t; | |
3324 | }; | |
3325 | ||
3326 | /* Subclass of dnode representing a function within the callgraph. */ | |
3327 | ||
3328 | class viz_callgraph_node : public dnode<viz_callgraph_traits> | |
3329 | { | |
3330 | friend class viz_callgraph; | |
3331 | ||
3332 | public: | |
3333 | viz_callgraph_node (function *fun, int index) | |
3334 | : m_fun (fun), m_index (index), m_num_supernodes (0), m_num_superedges (0) | |
3335 | { | |
3336 | gcc_assert (fun); | |
3337 | } | |
3338 | ||
3339 | void dump_dot (graphviz_out *gv, const dump_args_t &args) const FINAL OVERRIDE | |
3340 | { | |
3341 | pretty_printer *pp = gv->get_pp (); | |
3342 | ||
3343 | dump_dot_id (pp); | |
3344 | pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=<", | |
3345 | "lightgrey"); | |
3346 | pp_string (pp, "<TABLE BORDER=\"0\">"); | |
3347 | pp_write_text_to_stream (pp); | |
3348 | ||
3349 | gv->begin_tr (); | |
3350 | pp_printf (pp, "VCG: %i: %s", m_index, function_name (m_fun)); | |
3351 | gv->end_tr (); | |
3352 | pp_newline (pp); | |
3353 | ||
3354 | gv->begin_tr (); | |
3355 | pp_printf (pp, "supernodes: %i\n", m_num_supernodes); | |
3356 | gv->end_tr (); | |
3357 | pp_newline (pp); | |
3358 | ||
3359 | gv->begin_tr (); | |
3360 | pp_printf (pp, "superedges: %i\n", m_num_superedges); | |
3361 | gv->end_tr (); | |
3362 | pp_newline (pp); | |
3363 | ||
3364 | if (args.m_eg) | |
3365 | { | |
3366 | unsigned i; | |
3367 | exploded_node *enode; | |
3368 | unsigned num_enodes = 0; | |
3369 | FOR_EACH_VEC_ELT (args.m_eg->m_nodes, i, enode) | |
3370 | { | |
3371 | if (enode->get_point ().get_function () == m_fun) | |
3372 | num_enodes++; | |
3373 | } | |
3374 | gv->begin_tr (); | |
3375 | pp_printf (pp, "enodes: %i\n", num_enodes); | |
3376 | gv->end_tr (); | |
3377 | pp_newline (pp); | |
3378 | ||
3379 | // TODO: also show the per-callstring breakdown | |
3380 | const exploded_graph::call_string_data_map_t *per_cs_data | |
3381 | = args.m_eg->get_per_call_string_data (); | |
26d949c8 | 3382 | for (exploded_graph::call_string_data_map_t::iterator iter |
757bf1df DM |
3383 | = per_cs_data->begin (); |
3384 | iter != per_cs_data->end (); | |
3385 | ++iter) | |
3386 | { | |
3387 | const call_string *cs = (*iter).first; | |
3388 | //per_call_string_data *data = (*iter).second; | |
3389 | num_enodes = 0; | |
3390 | FOR_EACH_VEC_ELT (args.m_eg->m_nodes, i, enode) | |
3391 | { | |
3392 | if (enode->get_point ().get_function () == m_fun | |
3393 | && enode->get_point ().get_call_string () == *cs) | |
3394 | num_enodes++; | |
3395 | } | |
3396 | if (num_enodes > 0) | |
3397 | { | |
3398 | gv->begin_tr (); | |
3399 | cs->print (pp); | |
3400 | pp_printf (pp, ": %i\n", num_enodes); | |
3401 | pp_write_text_as_html_like_dot_to_stream (pp); | |
3402 | gv->end_tr (); | |
3403 | } | |
3404 | } | |
3405 | ||
3406 | /* Show any summaries. */ | |
3407 | per_function_data *data = args.m_eg->get_per_function_data (m_fun); | |
3408 | if (data) | |
3409 | { | |
3410 | pp_newline (pp); | |
3411 | gv->begin_tr (); | |
3412 | pp_printf (pp, "summaries: %i\n", data->m_summaries.length ()); | |
3413 | pp_write_text_as_html_like_dot_to_stream (pp); | |
3414 | gv->end_tr (); | |
3415 | } | |
3416 | } | |
3417 | ||
3418 | pp_string (pp, "</TABLE>>];\n\n"); | |
3419 | pp_flush (pp); | |
3420 | } | |
3421 | ||
3422 | void dump_dot_id (pretty_printer *pp) const | |
3423 | { | |
3424 | pp_printf (pp, "vcg_%i", m_index); | |
3425 | } | |
3426 | ||
3427 | private: | |
3428 | function *m_fun; | |
3429 | int m_index; | |
3430 | int m_num_supernodes; | |
3431 | int m_num_superedges; | |
3432 | }; | |
3433 | ||
3434 | /* Subclass of dedge representing a callgraph edge. */ | |
3435 | ||
3436 | class viz_callgraph_edge : public dedge<viz_callgraph_traits> | |
3437 | { | |
3438 | public: | |
3439 | viz_callgraph_edge (viz_callgraph_node *src, viz_callgraph_node *dest, | |
3440 | const call_superedge *call_sedge) | |
26d949c8 | 3441 | : dedge<viz_callgraph_traits> (src, dest), |
757bf1df DM |
3442 | m_call_sedge (call_sedge) |
3443 | {} | |
3444 | ||
3445 | void dump_dot (graphviz_out *gv, const dump_args_t &) const | |
3446 | FINAL OVERRIDE | |
3447 | { | |
3448 | pretty_printer *pp = gv->get_pp (); | |
3449 | ||
3450 | const char *style = "\"solid,bold\""; | |
3451 | const char *color = "black"; | |
3452 | int weight = 10; | |
3453 | const char *constraint = "true"; | |
3454 | ||
3455 | m_src->dump_dot_id (pp); | |
3456 | pp_string (pp, " -> "); | |
3457 | m_dest->dump_dot_id (pp); | |
3458 | pp_printf (pp, | |
3459 | (" [style=%s, color=%s, weight=%d, constraint=%s," | |
3460 | " headlabel=\""), | |
3461 | style, color, weight, constraint); | |
3462 | pp_printf (pp, "\"];\n"); | |
3463 | } | |
3464 | ||
3465 | private: | |
3466 | const call_superedge * const m_call_sedge; | |
3467 | }; | |
3468 | ||
3469 | /* Subclass of digraph representing the callgraph. */ | |
3470 | ||
3471 | class viz_callgraph : public digraph<viz_callgraph_traits> | |
3472 | { | |
3473 | public: | |
3474 | viz_callgraph (const supergraph &sg); | |
3475 | ||
3476 | viz_callgraph_node *get_vcg_node_for_function (function *fun) | |
3477 | { | |
3478 | return *m_map.get (fun); | |
3479 | } | |
3480 | ||
3481 | viz_callgraph_node *get_vcg_node_for_snode (supernode *snode) | |
3482 | { | |
3483 | return get_vcg_node_for_function (snode->m_fun); | |
3484 | } | |
3485 | ||
3486 | private: | |
3487 | const supergraph &m_sg; | |
3488 | hash_map<function *, viz_callgraph_node *> m_map; | |
3489 | }; | |
3490 | ||
3491 | /* Placeholder subclass of cluster. */ | |
3492 | ||
3493 | class viz_callgraph_cluster : public cluster<viz_callgraph_traits> | |
3494 | { | |
3495 | }; | |
3496 | ||
3497 | /* viz_callgraph's ctor. */ | |
3498 | ||
3499 | viz_callgraph::viz_callgraph (const supergraph &sg) | |
3500 | : m_sg (sg) | |
3501 | { | |
3502 | cgraph_node *node; | |
3503 | FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) | |
3504 | { | |
3505 | function *fun = node->get_fun (); | |
3506 | viz_callgraph_node *vcg_node | |
3507 | = new viz_callgraph_node (fun, m_nodes.length ()); | |
3508 | m_map.put (fun, vcg_node); | |
3509 | add_node (vcg_node); | |
3510 | } | |
3511 | ||
3512 | unsigned i; | |
3513 | superedge *sedge; | |
3514 | FOR_EACH_VEC_ELT (sg.m_edges, i, sedge) | |
3515 | { | |
3516 | viz_callgraph_node *vcg_src = get_vcg_node_for_snode (sedge->m_src); | |
3517 | if (vcg_src->m_fun) | |
3518 | get_vcg_node_for_function (vcg_src->m_fun)->m_num_superedges++; | |
3519 | if (const call_superedge *call_sedge = sedge->dyn_cast_call_superedge ()) | |
3520 | { | |
3521 | viz_callgraph_node *vcg_dest = get_vcg_node_for_snode (sedge->m_dest); | |
3522 | viz_callgraph_edge *vcg_edge | |
3523 | = new viz_callgraph_edge (vcg_src, vcg_dest, call_sedge); | |
3524 | add_edge (vcg_edge); | |
3525 | } | |
3526 | } | |
3527 | ||
3528 | supernode *snode; | |
3529 | FOR_EACH_VEC_ELT (sg.m_nodes, i, snode) | |
3530 | { | |
3531 | if (snode->m_fun) | |
3532 | get_vcg_node_for_function (snode->m_fun)->m_num_supernodes++; | |
3533 | } | |
3534 | } | |
3535 | ||
3536 | /* Dump the callgraph to FILENAME. */ | |
3537 | ||
3538 | static void | |
3539 | dump_callgraph (const supergraph &sg, const char *filename, | |
3540 | const exploded_graph *eg) | |
3541 | { | |
3542 | FILE *outf = fopen (filename, "w"); | |
3543 | if (!outf) | |
3544 | return; | |
3545 | ||
3546 | // TODO | |
3547 | viz_callgraph vcg (sg); | |
3548 | vcg.dump_dot (filename, NULL, viz_callgraph_traits::dump_args_t (eg)); | |
3549 | ||
3550 | fclose (outf); | |
3551 | } | |
3552 | ||
3553 | /* Dump the callgraph to "<srcfile>.callgraph.dot". */ | |
3554 | ||
3555 | static void | |
3556 | dump_callgraph (const supergraph &sg, const exploded_graph *eg) | |
3557 | { | |
3558 | auto_timevar tv (TV_ANALYZER_DUMP); | |
3559 | char *filename = concat (dump_base_name, ".callgraph.dot", NULL); | |
3560 | dump_callgraph (sg, filename, eg); | |
3561 | free (filename); | |
3562 | } | |
3563 | ||
3564 | /* Run the analysis "engine". */ | |
3565 | ||
3566 | void | |
3567 | impl_run_checkers (logger *logger) | |
3568 | { | |
3569 | LOG_SCOPE (logger); | |
3570 | ||
3571 | /* If using LTO, ensure that the cgraph nodes have function bodies. */ | |
3572 | cgraph_node *node; | |
3573 | FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) | |
3574 | node->get_untransformed_body (); | |
3575 | ||
3576 | /* Create the supergraph. */ | |
3577 | supergraph sg (logger); | |
3578 | ||
3579 | state_purge_map *purge_map = NULL; | |
3580 | ||
3581 | if (flag_analyzer_state_purge) | |
3582 | purge_map = new state_purge_map (sg, logger); | |
3583 | ||
3584 | if (flag_dump_analyzer_supergraph) | |
3585 | { | |
3586 | auto_timevar tv (TV_ANALYZER_DUMP); | |
3587 | char *filename = concat (dump_base_name, ".supergraph.dot", NULL); | |
3588 | supergraph::dump_args_t args ((enum supergraph_dot_flags)0, NULL); | |
3589 | sg.dump_dot (filename, args); | |
3590 | free (filename); | |
3591 | } | |
3592 | ||
3593 | if (flag_dump_analyzer_state_purge) | |
3594 | { | |
3595 | auto_timevar tv (TV_ANALYZER_DUMP); | |
3596 | state_purge_annotator a (purge_map); | |
3597 | char *filename = concat (dump_base_name, ".state-purge.dot", NULL); | |
3598 | supergraph::dump_args_t args ((enum supergraph_dot_flags)0, &a); | |
3599 | sg.dump_dot (filename, args); | |
3600 | free (filename); | |
3601 | } | |
3602 | ||
3603 | auto_delete_vec <state_machine> checkers; | |
3604 | make_checkers (checkers, logger); | |
3605 | ||
3606 | if (logger) | |
3607 | { | |
3608 | int i; | |
3609 | state_machine *sm; | |
3610 | FOR_EACH_VEC_ELT (checkers, i, sm) | |
3611 | logger->log ("checkers[%i]: %s", i, sm->get_name ()); | |
3612 | } | |
3613 | ||
3614 | /* Extrinsic state shared by nodes in the graph. */ | |
3615 | const extrinsic_state ext_state (checkers); | |
3616 | ||
3617 | const analysis_plan plan (sg, logger); | |
3618 | ||
3619 | /* The exploded graph. */ | |
3620 | exploded_graph eg (sg, logger, ext_state, purge_map, plan, | |
3621 | analyzer_verbosity); | |
3622 | ||
3623 | /* Add entrypoints to the graph for externally-callable functions. */ | |
3624 | eg.build_initial_worklist (); | |
3625 | ||
3626 | /* Now process the worklist, exploring the <point, state> graph. */ | |
3627 | eg.process_worklist (); | |
3628 | ||
3629 | if (flag_dump_analyzer_exploded_graph) | |
3630 | { | |
3631 | auto_timevar tv (TV_ANALYZER_DUMP); | |
3632 | char *filename | |
3633 | = concat (dump_base_name, ".eg.dot", NULL); | |
3634 | exploded_graph::dump_args_t args (eg); | |
3635 | root_cluster c; | |
3636 | eg.dump_dot (filename, &c, args); | |
3637 | free (filename); | |
3638 | } | |
3639 | ||
3640 | /* Now emit any saved diagnostics. */ | |
3641 | eg.get_diagnostic_manager ().emit_saved_diagnostics (eg); | |
3642 | ||
3643 | eg.dump_exploded_nodes (); | |
3644 | ||
3645 | eg.log_stats (); | |
3646 | ||
3647 | if (flag_dump_analyzer_callgraph) | |
3648 | dump_callgraph (sg, &eg); | |
3649 | ||
3650 | delete purge_map; | |
3651 | } | |
3652 | ||
3653 | /* External entrypoint to the analysis "engine". | |
3654 | Set up any dumps, then call impl_run_checkers. */ | |
3655 | ||
3656 | void | |
3657 | run_checkers () | |
3658 | { | |
2fbea419 DM |
3659 | /* Save input_location. */ |
3660 | location_t saved_input_location = input_location; | |
3661 | ||
757bf1df DM |
3662 | /* Handle -fdump-analyzer and -fdump-analyzer-stderr. */ |
3663 | FILE *dump_fout = NULL; | |
3664 | /* Track if we're responsible for closing dump_fout. */ | |
3665 | bool owns_dump_fout = false; | |
3666 | if (flag_dump_analyzer_stderr) | |
3667 | dump_fout = stderr; | |
3668 | else if (flag_dump_analyzer) | |
3669 | { | |
3670 | char *dump_filename = concat (dump_base_name, ".analyzer.txt", NULL); | |
3671 | dump_fout = fopen (dump_filename, "w"); | |
3672 | free (dump_filename); | |
3673 | if (dump_fout) | |
3674 | owns_dump_fout = true; | |
3675 | } | |
3676 | ||
3677 | { | |
3678 | log_user the_logger (NULL); | |
3679 | if (dump_fout) | |
3680 | the_logger.set_logger (new logger (dump_fout, 0, 0, | |
3681 | *global_dc->printer)); | |
3682 | LOG_SCOPE (the_logger.get_logger ()); | |
3683 | ||
3684 | impl_run_checkers (the_logger.get_logger ()); | |
3685 | ||
3686 | /* end of lifetime of the_logger (so that dump file is closed after the | |
3687 | various dtors run). */ | |
3688 | } | |
3689 | ||
3690 | if (owns_dump_fout) | |
3691 | fclose (dump_fout); | |
2fbea419 DM |
3692 | |
3693 | /* Restore input_location. Subsequent passes may assume that input_location | |
3694 | is some arbitrary value *not* in the block tree, which might be violated | |
3695 | if we didn't restore it. */ | |
3696 | input_location = saved_input_location; | |
757bf1df DM |
3697 | } |
3698 | ||
75038aa6 DM |
3699 | } // namespace ana |
3700 | ||
757bf1df | 3701 | #endif /* #if ENABLE_ANALYZER */ |