|
145
|
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
|
|
|
65 namespace ana {
|
|
|
66
|
|
|
67 static int readability_comparator (const void *p1, const void *p2);
|
|
|
68
|
|
|
69 /* class impl_region_model_context : public region_model_context. */
|
|
|
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
|
|
|
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
|
|
|
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 {
|
|
|
158 return m_setjmp_record == other.m_setjmp_record;
|
|
|
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 {
|
|
|
166 hstate.add_int (m_setjmp_record.m_enode->m_index);
|
|
|
167 }
|
|
|
168
|
|
|
169 /* Get the index of the stored exploded_node. */
|
|
|
170
|
|
|
171 int
|
|
|
172 setjmp_svalue::get_enode_index () const
|
|
|
173 {
|
|
|
174 return m_setjmp_record.m_enode->m_index;
|
|
|
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 {
|
|
|
184 pp_printf (pp, "setjmp: EN: %i", get_enode_index ());
|
|
|
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)
|
|
|
422 if (get_pure_location (stmt->location) != UNKNOWN_LOCATION)
|
|
|
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
|
|
|
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
|
|
|
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);
|
|
|
830 if (m_status == STATUS_MERGER)
|
|
|
831 pp_string (pp, " (merger)");
|
|
|
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
|
|
|
910 } // namespace ana
|
|
|
911
|
|
|
912 /* Return true if FNDECL has a gimple body. */
|
|
|
913 // TODO: is there a pre-canned way to do this?
|
|
|
914
|
|
|
915 bool
|
|
|
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
|
|
|
928 namespace ana {
|
|
|
929
|
|
|
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
|
|
|
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;
|
|
|
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 }
|
|
|
1022 else if (is_special_named_call_p (call, "__analyzer_dump_exploded_nodes",
|
|
|
1023 1))
|
|
|
1024 {
|
|
|
1025 /* This is handled elsewhere. */
|
|
|
1026 }
|
|
|
1027 else if (is_setjmp_call_p (call))
|
|
|
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
|
|
|
1035 unknown_side_effects = state->m_region_model->on_call_pre (call, &ctxt);
|
|
|
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];
|
|
|
1047 impl_sm_context sm_ctxt (eg, sm_idx, sm, this, &old_state, state,
|
|
|
1048 change,
|
|
|
1049 old_smap, new_smap);
|
|
|
1050 /* Allow the state_machine to handle the stmt. */
|
|
|
1051 if (sm.on_stmt (&sm_ctxt, snode, stmt))
|
|
|
1052 unknown_side_effects = false;
|
|
|
1053 else
|
|
|
1054 {
|
|
|
1055 /* For those stmts that were not handled by the state machine. */
|
|
|
1056 if (const gcall *call = dyn_cast <const gcall *> (stmt))
|
|
|
1057 {
|
|
|
1058 tree callee_fndecl
|
|
|
1059 = state->m_region_model->get_fndecl_for_call (call, &ctxt);
|
|
|
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))
|
|
|
1071 state->m_region_model->on_call_post (call, unknown_side_effects, &ctxt);
|
|
|
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",
|
|
|
1152 get_user_facing_name (m_longjmp_call),
|
|
|
1153 get_user_facing_name (m_setjmp_call));
|
|
|
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
|
|
|
1170 /* Handle LONGJMP_CALL, a call to longjmp or siglongjmp.
|
|
|
1171
|
|
|
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,
|
|
|
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
|
|
|
1199 const setjmp_record tmp_setjmp_record = setjmp_sval->get_setjmp_record ();
|
|
|
1200
|
|
|
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);
|
|
|
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,
|
|
|
1244 new rewind_info_t (tmp_setjmp_record, longjmp_call));
|
|
|
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 {
|
|
|
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
|
|
|
1365 model->on_longjmp (get_longjmp_call (),
|
|
|
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
|
|
|
1386 (&eedge, get_longjmp_call ()->location,
|
|
|
1387 src_point.get_fndecl (),
|
|
|
1388 src_stack_depth, this));
|
|
|
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
|
|
|
1396 /* class exploded_edge : public dedge<eg_traits>. */
|
|
|
1397
|
|
|
1398 /* exploded_edge's ctor. */
|
|
|
1399
|
|
|
1400 exploded_edge::exploded_edge (exploded_node *src, exploded_node *dest,
|
|
|
1401 const extrinsic_state &ext_state,
|
|
|
1402 const superedge *sedge,
|
|
|
1403 const state_change &change,
|
|
|
1404 custom_info_t *custom_info)
|
|
|
1405 : dedge<eg_traits> (src, dest), m_sedge (sedge), m_change (change),
|
|
|
1406 m_custom_info (custom_info)
|
|
|
1407 {
|
|
|
1408 change.validate (dest->get_state (), ext_state);
|
|
|
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 {
|
|
|
1644 gcc_assert (enode->get_status () == exploded_node::STATUS_WORKLIST);
|
|
|
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
|
|
|
1654 worklist::key_t::cmp (const worklist::key_t &ka, const worklist::key_t &kb)
|
|
|
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
|
|
|
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;
|
|
|
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
|
|
|
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
|
|
|
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. */
|
|
|
1906 ps.set_state (merged_state);
|
|
|
1907 if (change)
|
|
|
1908 change->on_svalue_purge (svalue_id::from_int (0));
|
|
|
1909
|
|
|
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 }
|
|
|
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 {
|
|
|
1989 exploded_edge *e = new exploded_edge (src, dest, m_ext_state,
|
|
|
1990 sedge, change, custom_info);
|
|
|
1991 digraph<eg_traits>::add_edge (e);
|
|
|
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 ();
|
|
|
2131 gcc_assert (node->get_status () == exploded_node::STATUS_WORKLIST);
|
|
|
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 {
|
|
|
2144 gcc_assert (node_2->get_status ()
|
|
|
2145 == exploded_node::STATUS_WORKLIST);
|
|
|
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 ();
|
|
|
2191 node_2->set_status (exploded_node::STATUS_MERGER);
|
|
|
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);
|
|
|
2201 node->set_status (exploded_node::STATUS_MERGER);
|
|
|
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
|
|
|
2244 {
|
|
|
2245 add_edge (node, merged_enode, NULL, change);
|
|
|
2246 node->set_status (exploded_node::STATUS_MERGER);
|
|
|
2247 }
|
|
|
2248
|
|
|
2249 if (merged_enode == node_2)
|
|
|
2250 m_worklist.add_node (merged_enode);
|
|
|
2251 else
|
|
|
2252 {
|
|
|
2253 add_edge (node_2, merged_enode, NULL, change);
|
|
|
2254 node_2->set_status (exploded_node::STATUS_MERGER);
|
|
|
2255 }
|
|
|
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. */
|
|
|
2317 if (get_pure_location (prev_stmt->location) == UNKNOWN_LOCATION
|
|
|
2318 && get_pure_location (stmt->location) != UNKNOWN_LOCATION)
|
|
|
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
|
|
|
2338 node->set_status (exploded_node::STATUS_PROCESSED);
|
|
|
2339
|
|
|
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\";");
|
|
|
2852 gv->println ("label=\"SN: %i (bb: %i)\";",
|
|
|
2853 m_supernode->m_index, m_supernode->m_bb->index);
|
|
|
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
|
|
|
2950 } // namespace ana
|
|
|
2951
|
|
|
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 {
|
|
|
2982 v.m_fun = NULL;
|
|
|
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 {
|
|
|
2994 return v.m_fun == NULL;
|
|
|
2995 }
|
|
|
2996
|
|
|
2997 namespace ana {
|
|
|
2998
|
|
|
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 {
|
|
|
3122 if (get_pure_location (richloc.get_loc ()) == UNKNOWN_LOCATION)
|
|
|
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",
|
|
|
3200 giving the number of processed exploded nodes for "before-stmt",
|
|
|
3201 and the IDs of processed, merger, and worklist enodes.
|
|
|
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
|
|
|
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. */
|
|
|
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
|
|
|
3227 auto_vec<exploded_node *> processed_enodes;
|
|
|
3228 auto_vec<exploded_node *> merger_enodes;
|
|
|
3229 auto_vec<exploded_node *> worklist_enodes;
|
|
|
3230 /* This is O(N^2). */
|
|
|
3231 unsigned j;
|
|
|
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)
|
|
|
3238 switch (other_enode->get_status ())
|
|
|
3239 {
|
|
|
3240 default:
|
|
|
3241 gcc_unreachable ();
|
|
|
3242 case exploded_node::STATUS_WORKLIST:
|
|
|
3243 worklist_enodes.safe_push (other_enode);
|
|
|
3244 break;
|
|
|
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 }
|
|
|
3252 }
|
|
|
3253
|
|
|
3254 pretty_printer pp;
|
|
|
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 }
|
|
|
3262 if (worklist_enodes.length () > 0)
|
|
|
3263 {
|
|
|
3264 pp_string (&pp, "] worklist: [");
|
|
|
3265 print_enode_indices (&pp, worklist_enodes);
|
|
|
3266 }
|
|
|
3267 pp_character (&pp, ']');
|
|
|
3268
|
|
|
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));
|
|
|
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;
|
|
|
3288 FOR_EACH_VEC_ELT (processed_enodes, j, other_enode)
|
|
|
3289 {
|
|
|
3290 fprintf (stderr, "%i of %i: EN %i:\n",
|
|
|
3291 j + 1, processed_enodes.length (),
|
|
|
3292 other_enode->m_index);
|
|
|
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 ();
|
|
|
3382 for (exploded_graph::call_string_data_map_t::iterator iter
|
|
|
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)
|
|
|
3441 : dedge<viz_callgraph_traits> (src, dest),
|
|
|
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 {
|
|
|
3659 /* Save input_location. */
|
|
|
3660 location_t saved_input_location = input_location;
|
|
|
3661
|
|
|
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);
|
|
|
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;
|
|
|
3697 }
|
|
|
3698
|
|
|
3699 } // namespace ana
|
|
|
3700
|
|
|
3701 #endif /* #if ENABLE_ANALYZER */
|
