|
145
|
1 /* Classes for managing a directed graph of <point, state> pairs.
|
|
|
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 #ifndef GCC_ANALYZER_EXPLODED_GRAPH_H
|
|
|
22 #define GCC_ANALYZER_EXPLODED_GRAPH_H
|
|
|
23
|
|
|
24 namespace ana {
|
|
|
25
|
|
|
26 /* Concrete implementation of region_model_context, wiring it up to the
|
|
|
27 rest of the analysis engine. */
|
|
|
28
|
|
|
29 class impl_region_model_context : public region_model_context
|
|
|
30 {
|
|
|
31 public:
|
|
|
32 impl_region_model_context (exploded_graph &eg,
|
|
|
33 const exploded_node *enode_for_diag,
|
|
|
34
|
|
|
35 /* TODO: should we be getting the ECs from the
|
|
|
36 old state, rather than the new? */
|
|
|
37 const program_state *old_state,
|
|
|
38 program_state *new_state,
|
|
|
39 state_change *change,
|
|
|
40
|
|
|
41 const gimple *stmt,
|
|
|
42 stmt_finder *stmt_finder = NULL);
|
|
|
43
|
|
|
44 impl_region_model_context (program_state *state,
|
|
|
45 state_change *change,
|
|
|
46 const extrinsic_state &ext_state);
|
|
|
47
|
|
|
48 void warn (pending_diagnostic *d) FINAL OVERRIDE;
|
|
|
49
|
|
|
50 void remap_svalue_ids (const svalue_id_map &map) FINAL OVERRIDE;
|
|
|
51
|
|
|
52 int on_svalue_purge (svalue_id first_unused_sid,
|
|
|
53 const svalue_id_map &map) FINAL OVERRIDE;
|
|
|
54
|
|
|
55 logger *get_logger () FINAL OVERRIDE
|
|
|
56 {
|
|
|
57 return m_logger.get_logger ();
|
|
|
58 }
|
|
|
59
|
|
|
60 void on_state_leak (const state_machine &sm,
|
|
|
61 int sm_idx,
|
|
|
62 svalue_id sid,
|
|
|
63 svalue_id first_unused_sid,
|
|
|
64 const svalue_id_map &map,
|
|
|
65 state_machine::state_t state);
|
|
|
66
|
|
|
67 void on_inherited_svalue (svalue_id parent_sid,
|
|
|
68 svalue_id child_sid) FINAL OVERRIDE;
|
|
|
69
|
|
|
70 void on_cast (svalue_id src_sid,
|
|
|
71 svalue_id dst_sid) FINAL OVERRIDE;
|
|
|
72
|
|
|
73 void on_condition (tree lhs, enum tree_code op, tree rhs) FINAL OVERRIDE;
|
|
|
74
|
|
|
75 void on_unknown_change (svalue_id sid ATTRIBUTE_UNUSED) FINAL OVERRIDE;
|
|
|
76
|
|
|
77 void on_phi (const gphi *phi, tree rhs) FINAL OVERRIDE;
|
|
|
78
|
|
|
79 exploded_graph *m_eg;
|
|
|
80 log_user m_logger;
|
|
|
81 const exploded_node *m_enode_for_diag;
|
|
|
82 const program_state *m_old_state;
|
|
|
83 program_state *m_new_state;
|
|
|
84 state_change *m_change;
|
|
|
85 const gimple *m_stmt;
|
|
|
86 stmt_finder *m_stmt_finder;
|
|
|
87 const extrinsic_state &m_ext_state;
|
|
|
88 };
|
|
|
89
|
|
|
90 /* A <program_point, program_state> pair, used internally by
|
|
|
91 exploded_node as its immutable data, and as a key for identifying
|
|
|
92 exploded_nodes we've already seen in the graph. */
|
|
|
93
|
|
|
94 class point_and_state
|
|
|
95 {
|
|
|
96 public:
|
|
|
97 point_and_state (const program_point &point,
|
|
|
98 const program_state &state)
|
|
|
99 : m_point (point),
|
|
|
100 m_state (state),
|
|
|
101 m_hash (m_point.hash () ^ m_state.hash ())
|
|
|
102 {
|
|
|
103 }
|
|
|
104
|
|
|
105 hashval_t hash () const
|
|
|
106 {
|
|
|
107 return m_hash;
|
|
|
108 }
|
|
|
109 bool operator== (const point_and_state &other) const
|
|
|
110 {
|
|
|
111 return m_point == other.m_point && m_state == other.m_state;
|
|
|
112 }
|
|
|
113
|
|
|
114 const program_point &get_point () const { return m_point; }
|
|
|
115 const program_state &get_state () const { return m_state; }
|
|
|
116
|
|
|
117 void set_state (const program_state &state)
|
|
|
118 {
|
|
|
119 m_state = state;
|
|
|
120 m_hash = m_point.hash () ^ m_state.hash ();
|
|
|
121 }
|
|
|
122
|
|
|
123 void validate (const extrinsic_state &ext_state) const;
|
|
|
124
|
|
|
125 private:
|
|
|
126 program_point m_point;
|
|
|
127 program_state m_state;
|
|
|
128 hashval_t m_hash;
|
|
|
129 };
|
|
|
130
|
|
|
131 /* A traits class for exploded graphs and their nodes and edges. */
|
|
|
132
|
|
|
133 struct eg_traits
|
|
|
134 {
|
|
|
135 typedef exploded_node node_t;
|
|
|
136 typedef exploded_edge edge_t;
|
|
|
137 typedef exploded_graph graph_t;
|
|
|
138 struct dump_args_t
|
|
|
139 {
|
|
|
140 dump_args_t (const exploded_graph &eg) : m_eg (eg) {}
|
|
|
141 const exploded_graph &m_eg;
|
|
|
142 };
|
|
|
143 typedef exploded_cluster cluster_t;
|
|
|
144 };
|
|
|
145
|
|
|
146 /* An exploded_node is a unique, immutable <point, state> pair within the
|
|
|
147 exploded_graph.
|
|
|
148 Each exploded_node has a unique index within the graph
|
|
|
149 (for ease of debugging). */
|
|
|
150
|
|
|
151 class exploded_node : public dnode<eg_traits>
|
|
|
152 {
|
|
|
153 public:
|
|
|
154 /* Has this enode had exploded_graph::process_node called on it?
|
|
|
155 This allows us to distinguish enodes that were merged during
|
|
|
156 worklist-handling, and thus never had process_node called on them
|
|
|
157 (in favor of processing the merged node). */
|
|
|
158 enum status
|
|
|
159 {
|
|
|
160 /* Node is in the worklist. */
|
|
|
161 STATUS_WORKLIST,
|
|
|
162
|
|
|
163 /* Node has had exploded_graph::process_node called on it. */
|
|
|
164 STATUS_PROCESSED,
|
|
|
165
|
|
|
166 /* Node was left unprocessed due to merger; it won't have had
|
|
|
167 exploded_graph::process_node called on it. */
|
|
|
168 STATUS_MERGER
|
|
|
169 };
|
|
|
170
|
|
|
171 exploded_node (point_and_state ps,
|
|
|
172 int index)
|
|
|
173 : m_ps (ps), m_status (STATUS_WORKLIST), m_index (index)
|
|
|
174 {
|
|
|
175 gcc_checking_assert (ps.get_state ().m_region_model->canonicalized_p ());
|
|
|
176 }
|
|
|
177
|
|
|
178 hashval_t hash () const { return m_ps.hash (); }
|
|
|
179
|
|
|
180 void dump_dot (graphviz_out *gv, const dump_args_t &args)
|
|
|
181 const FINAL OVERRIDE;
|
|
|
182 void dump_dot_id (pretty_printer *pp) const;
|
|
|
183
|
|
|
184 void dump_to_pp (pretty_printer *pp, const extrinsic_state &ext_state) const;
|
|
|
185 void dump (FILE *fp, const extrinsic_state &ext_state) const;
|
|
|
186 void dump (const extrinsic_state &ext_state) const;
|
|
|
187
|
|
|
188 /* The result of on_stmt. */
|
|
|
189 struct on_stmt_flags
|
|
|
190 {
|
|
|
191 on_stmt_flags (bool sm_changes)
|
|
|
192 : m_sm_changes (sm_changes),
|
|
|
193 m_terminate_path (false)
|
|
|
194 {}
|
|
|
195
|
|
|
196 static on_stmt_flags terminate_path ()
|
|
|
197 {
|
|
|
198 return on_stmt_flags (true, true);
|
|
|
199 }
|
|
|
200
|
|
|
201 static on_stmt_flags state_change (bool any_sm_changes)
|
|
|
202 {
|
|
|
203 return on_stmt_flags (any_sm_changes, false);
|
|
|
204 }
|
|
|
205
|
|
|
206 /* Did any sm-changes occur handling the stmt. */
|
|
|
207 bool m_sm_changes : 1;
|
|
|
208
|
|
|
209 /* Should we stop analyzing this path (on_stmt may have already
|
|
|
210 added nodes/edges, e.g. when handling longjmp). */
|
|
|
211 bool m_terminate_path : 1;
|
|
|
212
|
|
|
213 private:
|
|
|
214 on_stmt_flags (bool sm_changes,
|
|
|
215 bool terminate_path)
|
|
|
216 : m_sm_changes (sm_changes),
|
|
|
217 m_terminate_path (terminate_path)
|
|
|
218 {}
|
|
|
219 };
|
|
|
220
|
|
|
221 on_stmt_flags on_stmt (exploded_graph &eg,
|
|
|
222 const supernode *snode,
|
|
|
223 const gimple *stmt,
|
|
|
224 program_state *state,
|
|
|
225 state_change *change) const;
|
|
|
226 bool on_edge (exploded_graph &eg,
|
|
|
227 const superedge *succ,
|
|
|
228 program_point *next_point,
|
|
|
229 program_state *next_state,
|
|
|
230 state_change *change) const;
|
|
|
231 void on_longjmp (exploded_graph &eg,
|
|
|
232 const gcall *call,
|
|
|
233 program_state *new_state,
|
|
|
234 region_model_context *ctxt) const;
|
|
|
235
|
|
|
236 void detect_leaks (exploded_graph &eg) const;
|
|
|
237
|
|
|
238 const program_point &get_point () const { return m_ps.get_point (); }
|
|
|
239 const supernode *get_supernode () const
|
|
|
240 {
|
|
|
241 return get_point ().get_supernode ();
|
|
|
242 }
|
|
|
243 function *get_function () const
|
|
|
244 {
|
|
|
245 return get_point ().get_function ();
|
|
|
246 }
|
|
|
247 int get_stack_depth () const
|
|
|
248 {
|
|
|
249 return get_point ().get_stack_depth ();
|
|
|
250 }
|
|
|
251 const gimple *get_stmt () const { return get_point ().get_stmt (); }
|
|
|
252
|
|
|
253 const program_state &get_state () const { return m_ps.get_state (); }
|
|
|
254
|
|
|
255 const point_and_state *get_ps_key () const { return &m_ps; }
|
|
|
256 const program_point *get_point_key () const { return &m_ps.get_point (); }
|
|
|
257
|
|
|
258 void dump_succs_and_preds (FILE *outf) const;
|
|
|
259
|
|
|
260 enum status get_status () const { return m_status; }
|
|
|
261 void set_status (enum status status)
|
|
|
262 {
|
|
|
263 gcc_assert (m_status == STATUS_WORKLIST);
|
|
|
264 m_status = status;
|
|
|
265 }
|
|
|
266
|
|
|
267 private:
|
|
|
268 DISABLE_COPY_AND_ASSIGN (exploded_node);
|
|
|
269
|
|
|
270 const char * get_dot_fillcolor () const;
|
|
|
271
|
|
|
272 /* The <program_point, program_state> pair. This is const, as it
|
|
|
273 is immutable once the exploded_node has been created. */
|
|
|
274 const point_and_state m_ps;
|
|
|
275
|
|
|
276 enum status m_status;
|
|
|
277
|
|
|
278 public:
|
|
|
279 /* The index of this exploded_node. */
|
|
|
280 const int m_index;
|
|
|
281 };
|
|
|
282
|
|
|
283 /* An edge within the exploded graph.
|
|
|
284 Some exploded_edges have an underlying superedge; others don't. */
|
|
|
285
|
|
|
286 class exploded_edge : public dedge<eg_traits>
|
|
|
287 {
|
|
|
288 public:
|
|
|
289 /* Abstract base class for associating custom data with an
|
|
|
290 exploded_edge, for handling non-standard edges such as
|
|
|
291 rewinding from a longjmp, signal handlers, etc. */
|
|
|
292 class custom_info_t
|
|
|
293 {
|
|
|
294 public:
|
|
|
295 virtual ~custom_info_t () {}
|
|
|
296
|
|
|
297 /* Hook for making .dot label more readable . */
|
|
|
298 virtual void print (pretty_printer *pp) = 0;
|
|
|
299
|
|
|
300 /* Hook for updating MODEL within exploded_path::feasible_p. */
|
|
|
301 virtual void update_model (region_model *model,
|
|
|
302 const exploded_edge &eedge) = 0;
|
|
|
303
|
|
|
304 virtual void add_events_to_path (checker_path *emission_path,
|
|
|
305 const exploded_edge &eedge) = 0;
|
|
|
306 };
|
|
|
307
|
|
|
308 exploded_edge (exploded_node *src, exploded_node *dest,
|
|
|
309 const extrinsic_state &ext_state,
|
|
|
310 const superedge *sedge,
|
|
|
311 const state_change &change,
|
|
|
312 custom_info_t *custom_info);
|
|
|
313 ~exploded_edge ();
|
|
|
314 void dump_dot (graphviz_out *gv, const dump_args_t &args)
|
|
|
315 const FINAL OVERRIDE;
|
|
|
316
|
|
|
317 //private:
|
|
|
318 const superedge *const m_sedge;
|
|
|
319
|
|
|
320 const state_change m_change;
|
|
|
321
|
|
|
322 /* NULL for most edges; will be non-NULL for special cases
|
|
|
323 such as an unwind from a longjmp to a setjmp, or when
|
|
|
324 a signal is delivered to a signal-handler.
|
|
|
325
|
|
|
326 Owned by this class. */
|
|
|
327 custom_info_t *m_custom_info;
|
|
|
328
|
|
|
329 private:
|
|
|
330 DISABLE_COPY_AND_ASSIGN (exploded_edge);
|
|
|
331 };
|
|
|
332
|
|
|
333 /* Extra data for an exploded_edge that represents a rewind from a
|
|
|
334 longjmp to a setjmp (or from a siglongjmp to a sigsetjmp). */
|
|
|
335
|
|
|
336 class rewind_info_t : public exploded_edge::custom_info_t
|
|
|
337 {
|
|
|
338 public:
|
|
|
339 rewind_info_t (const setjmp_record &setjmp_record,
|
|
|
340 const gcall *longjmp_call)
|
|
|
341 : m_setjmp_record (setjmp_record),
|
|
|
342 m_longjmp_call (longjmp_call)
|
|
|
343 {}
|
|
|
344
|
|
|
345 void print (pretty_printer *pp) FINAL OVERRIDE
|
|
|
346 {
|
|
|
347 pp_string (pp, "rewind");
|
|
|
348 }
|
|
|
349
|
|
|
350 void update_model (region_model *model,
|
|
|
351 const exploded_edge &eedge) FINAL OVERRIDE;
|
|
|
352
|
|
|
353 void add_events_to_path (checker_path *emission_path,
|
|
|
354 const exploded_edge &eedge) FINAL OVERRIDE;
|
|
|
355
|
|
|
356 const program_point &get_setjmp_point () const
|
|
|
357 {
|
|
|
358 const program_point &origin_point = get_enode_origin ()->get_point ();
|
|
|
359
|
|
|
360 /* "origin_point" ought to be before the call to "setjmp". */
|
|
|
361 gcc_assert (origin_point.get_kind () == PK_BEFORE_STMT);
|
|
|
362
|
|
|
363 /* TODO: assert that it's the final stmt in its supernode. */
|
|
|
364
|
|
|
365 return origin_point;
|
|
|
366 }
|
|
|
367
|
|
|
368 const gcall *get_setjmp_call () const
|
|
|
369 {
|
|
|
370 return m_setjmp_record.m_setjmp_call;
|
|
|
371 }
|
|
|
372
|
|
|
373 const gcall *get_longjmp_call () const
|
|
|
374 {
|
|
|
375 return m_longjmp_call;
|
|
|
376 }
|
|
|
377
|
|
|
378 const exploded_node *get_enode_origin () const
|
|
|
379 {
|
|
|
380 return m_setjmp_record.m_enode;
|
|
|
381 }
|
|
|
382
|
|
|
383 private:
|
|
|
384 setjmp_record m_setjmp_record;
|
|
|
385 const gcall *m_longjmp_call;
|
|
|
386 };
|
|
|
387
|
|
|
388 /* Statistics about aspects of an exploded_graph. */
|
|
|
389
|
|
|
390 struct stats
|
|
|
391 {
|
|
|
392 stats (int num_supernodes);
|
|
|
393 void log (logger *logger) const;
|
|
|
394 void dump (FILE *out) const;
|
|
|
395
|
|
|
396 int m_num_nodes[NUM_POINT_KINDS];
|
|
|
397 int m_node_reuse_count;
|
|
|
398 int m_node_reuse_after_merge_count;
|
|
|
399 int m_num_supernodes;
|
|
|
400 };
|
|
|
401
|
|
|
402 /* Traits class for ensuring uniqueness of point_and_state data within
|
|
|
403 an exploded_graph. */
|
|
|
404
|
|
|
405 struct eg_hash_map_traits
|
|
|
406 {
|
|
|
407 typedef const point_and_state *key_type;
|
|
|
408 typedef exploded_node *value_type;
|
|
|
409 typedef exploded_node *compare_type;
|
|
|
410
|
|
|
411 static inline hashval_t hash (const key_type &k)
|
|
|
412 {
|
|
|
413 gcc_assert (k != NULL);
|
|
|
414 gcc_assert (k != reinterpret_cast<key_type> (1));
|
|
|
415 return k->hash ();
|
|
|
416 }
|
|
|
417 static inline bool equal_keys (const key_type &k1, const key_type &k2)
|
|
|
418 {
|
|
|
419 gcc_assert (k1 != NULL);
|
|
|
420 gcc_assert (k2 != NULL);
|
|
|
421 gcc_assert (k1 != reinterpret_cast<key_type> (1));
|
|
|
422 gcc_assert (k2 != reinterpret_cast<key_type> (1));
|
|
|
423 if (k1 && k2)
|
|
|
424 return *k1 == *k2;
|
|
|
425 else
|
|
|
426 /* Otherwise they must both be non-NULL. */
|
|
|
427 return k1 == k2;
|
|
|
428 }
|
|
|
429 template <typename T>
|
|
|
430 static inline void remove (T &)
|
|
|
431 {
|
|
|
432 /* empty; the nodes are handled elsewhere. */
|
|
|
433 }
|
|
|
434 template <typename T>
|
|
|
435 static inline void mark_deleted (T &entry)
|
|
|
436 {
|
|
|
437 entry.m_key = reinterpret_cast<key_type> (1);
|
|
|
438 }
|
|
|
439 template <typename T>
|
|
|
440 static inline void mark_empty (T &entry)
|
|
|
441 {
|
|
|
442 entry.m_key = NULL;
|
|
|
443 }
|
|
|
444 template <typename T>
|
|
|
445 static inline bool is_deleted (const T &entry)
|
|
|
446 {
|
|
|
447 return entry.m_key == reinterpret_cast<key_type> (1);
|
|
|
448 }
|
|
|
449 template <typename T>
|
|
|
450 static inline bool is_empty (const T &entry)
|
|
|
451 {
|
|
|
452 return entry.m_key == NULL;
|
|
|
453 }
|
|
|
454 static const bool empty_zero_p = false;
|
|
|
455 };
|
|
|
456
|
|
|
457 /* Per-program_point data for an exploded_graph. */
|
|
|
458
|
|
|
459 struct per_program_point_data
|
|
|
460 {
|
|
|
461 per_program_point_data (const program_point &key)
|
|
|
462 : m_key (key)
|
|
|
463 {}
|
|
|
464
|
|
|
465 const program_point m_key;
|
|
|
466 auto_vec<exploded_node *> m_enodes;
|
|
|
467 };
|
|
|
468
|
|
|
469 /* Traits class for storing per-program_point data within
|
|
|
470 an exploded_graph. */
|
|
|
471
|
|
|
472 struct eg_point_hash_map_traits
|
|
|
473 {
|
|
|
474 typedef const program_point *key_type;
|
|
|
475 typedef per_program_point_data *value_type;
|
|
|
476 typedef per_program_point_data *compare_type;
|
|
|
477
|
|
|
478 static inline hashval_t hash (const key_type &k)
|
|
|
479 {
|
|
|
480 gcc_assert (k != NULL);
|
|
|
481 gcc_assert (k != reinterpret_cast<key_type> (1));
|
|
|
482 return k->hash ();
|
|
|
483 }
|
|
|
484 static inline bool equal_keys (const key_type &k1, const key_type &k2)
|
|
|
485 {
|
|
|
486 gcc_assert (k1 != NULL);
|
|
|
487 gcc_assert (k2 != NULL);
|
|
|
488 gcc_assert (k1 != reinterpret_cast<key_type> (1));
|
|
|
489 gcc_assert (k2 != reinterpret_cast<key_type> (1));
|
|
|
490 if (k1 && k2)
|
|
|
491 return *k1 == *k2;
|
|
|
492 else
|
|
|
493 /* Otherwise they must both be non-NULL. */
|
|
|
494 return k1 == k2;
|
|
|
495 }
|
|
|
496 template <typename T>
|
|
|
497 static inline void remove (T &)
|
|
|
498 {
|
|
|
499 /* empty; the nodes are handled elsewhere. */
|
|
|
500 }
|
|
|
501 template <typename T>
|
|
|
502 static inline void mark_deleted (T &entry)
|
|
|
503 {
|
|
|
504 entry.m_key = reinterpret_cast<key_type> (1);
|
|
|
505 }
|
|
|
506 template <typename T>
|
|
|
507 static inline void mark_empty (T &entry)
|
|
|
508 {
|
|
|
509 entry.m_key = NULL;
|
|
|
510 }
|
|
|
511 template <typename T>
|
|
|
512 static inline bool is_deleted (const T &entry)
|
|
|
513 {
|
|
|
514 return entry.m_key == reinterpret_cast<key_type> (1);
|
|
|
515 }
|
|
|
516 template <typename T>
|
|
|
517 static inline bool is_empty (const T &entry)
|
|
|
518 {
|
|
|
519 return entry.m_key == NULL;
|
|
|
520 }
|
|
|
521 static const bool empty_zero_p = false;
|
|
|
522 };
|
|
|
523
|
|
|
524 /* Data about a particular call_string within an exploded_graph. */
|
|
|
525
|
|
|
526 struct per_call_string_data
|
|
|
527 {
|
|
|
528 per_call_string_data (const call_string &key, int num_supernodes)
|
|
|
529 : m_key (key), m_stats (num_supernodes)
|
|
|
530 {}
|
|
|
531
|
|
|
532 const call_string m_key;
|
|
|
533 stats m_stats;
|
|
|
534 };
|
|
|
535
|
|
|
536 /* Traits class for storing per-call_string data within
|
|
|
537 an exploded_graph. */
|
|
|
538
|
|
|
539 struct eg_call_string_hash_map_traits
|
|
|
540 {
|
|
|
541 typedef const call_string *key_type;
|
|
|
542 typedef per_call_string_data *value_type;
|
|
|
543 typedef per_call_string_data *compare_type;
|
|
|
544
|
|
|
545 static inline hashval_t hash (const key_type &k)
|
|
|
546 {
|
|
|
547 gcc_assert (k != NULL);
|
|
|
548 gcc_assert (k != reinterpret_cast<key_type> (1));
|
|
|
549 return k->hash ();
|
|
|
550 }
|
|
|
551 static inline bool equal_keys (const key_type &k1, const key_type &k2)
|
|
|
552 {
|
|
|
553 gcc_assert (k1 != NULL);
|
|
|
554 gcc_assert (k2 != NULL);
|
|
|
555 gcc_assert (k1 != reinterpret_cast<key_type> (1));
|
|
|
556 gcc_assert (k2 != reinterpret_cast<key_type> (1));
|
|
|
557 if (k1 && k2)
|
|
|
558 return *k1 == *k2;
|
|
|
559 else
|
|
|
560 /* Otherwise they must both be non-NULL. */
|
|
|
561 return k1 == k2;
|
|
|
562 }
|
|
|
563 template <typename T>
|
|
|
564 static inline void remove (T &)
|
|
|
565 {
|
|
|
566 /* empty; the nodes are handled elsewhere. */
|
|
|
567 }
|
|
|
568 template <typename T>
|
|
|
569 static inline void mark_deleted (T &entry)
|
|
|
570 {
|
|
|
571 entry.m_key = reinterpret_cast<key_type> (1);
|
|
|
572 }
|
|
|
573 template <typename T>
|
|
|
574 static inline void mark_empty (T &entry)
|
|
|
575 {
|
|
|
576 entry.m_key = NULL;
|
|
|
577 }
|
|
|
578 template <typename T>
|
|
|
579 static inline bool is_deleted (const T &entry)
|
|
|
580 {
|
|
|
581 return entry.m_key == reinterpret_cast<key_type> (1);
|
|
|
582 }
|
|
|
583 template <typename T>
|
|
|
584 static inline bool is_empty (const T &entry)
|
|
|
585 {
|
|
|
586 return entry.m_key == NULL;
|
|
|
587 }
|
|
|
588 static const bool empty_zero_p = false;
|
|
|
589 };
|
|
|
590
|
|
|
591 /* Data about a particular function within an exploded_graph. */
|
|
|
592
|
|
|
593 struct per_function_data
|
|
|
594 {
|
|
|
595 per_function_data () {}
|
|
|
596
|
|
|
597 void add_call_summary (exploded_node *node)
|
|
|
598 {
|
|
|
599 m_summaries.safe_push (node);
|
|
|
600 }
|
|
|
601
|
|
|
602 auto_vec<exploded_node *> m_summaries;
|
|
|
603 };
|
|
|
604
|
|
|
605
|
|
|
606 /* The strongly connected components of a supergraph.
|
|
|
607 In particular, this allows us to compute a partial ordering
|
|
|
608 of supernodes. */
|
|
|
609
|
|
|
610 class strongly_connected_components
|
|
|
611 {
|
|
|
612 public:
|
|
|
613 strongly_connected_components (const supergraph &sg, logger *logger);
|
|
|
614
|
|
|
615 int get_scc_id (int node_index) const
|
|
|
616 {
|
|
|
617 return m_per_node[node_index].m_lowlink;
|
|
|
618 }
|
|
|
619
|
|
|
620 void dump () const;
|
|
|
621
|
|
|
622 private:
|
|
|
623 struct per_node_data
|
|
|
624 {
|
|
|
625 per_node_data ()
|
|
|
626 : m_index (-1), m_lowlink (-1), m_on_stack (false)
|
|
|
627 {}
|
|
|
628
|
|
|
629 int m_index;
|
|
|
630 int m_lowlink;
|
|
|
631 bool m_on_stack;
|
|
|
632 };
|
|
|
633
|
|
|
634 void strong_connect (unsigned index);
|
|
|
635
|
|
|
636 const supergraph &m_sg;
|
|
|
637 auto_vec<unsigned> m_stack;
|
|
|
638 auto_vec<per_node_data> m_per_node;
|
|
|
639 };
|
|
|
640
|
|
|
641 /* The worklist of exploded_node instances that have been added to
|
|
|
642 an exploded_graph, but that haven't yet been processed to find
|
|
|
643 their successors (or warnings).
|
|
|
644
|
|
|
645 The enodes are stored in a priority queue, ordered by a topological
|
|
|
646 sort of the SCCs in the supergraph, so that enodes for the same
|
|
|
647 program_point should appear at the front of the queue together.
|
|
|
648 This allows for state-merging at CFG join-points, so that
|
|
|
649 sufficiently-similar enodes can be merged into one. */
|
|
|
650
|
|
|
651 class worklist
|
|
|
652 {
|
|
|
653 public:
|
|
|
654 worklist (const exploded_graph &eg, const analysis_plan &plan);
|
|
|
655 unsigned length () const;
|
|
|
656 exploded_node *take_next ();
|
|
|
657 exploded_node *peek_next ();
|
|
|
658 void add_node (exploded_node *enode);
|
|
|
659
|
|
|
660 private:
|
|
|
661 class key_t
|
|
|
662 {
|
|
|
663 public:
|
|
|
664 key_t (const worklist &w, exploded_node *enode)
|
|
|
665 : m_worklist (w), m_enode (enode)
|
|
|
666 {}
|
|
|
667
|
|
|
668 bool operator< (const key_t &other) const
|
|
|
669 {
|
|
|
670 return cmp (*this, other) < 0;
|
|
|
671 }
|
|
|
672
|
|
|
673 bool operator== (const key_t &other) const
|
|
|
674 {
|
|
|
675 return cmp (*this, other) == 0;
|
|
|
676 }
|
|
|
677
|
|
|
678 bool operator> (const key_t &other) const
|
|
|
679 {
|
|
|
680 return !(*this == other || *this < other);
|
|
|
681 }
|
|
|
682
|
|
|
683 private:
|
|
|
684 static int cmp (const key_t &ka, const key_t &kb);
|
|
|
685
|
|
|
686 int get_scc_id (const exploded_node *enode) const
|
|
|
687 {
|
|
|
688 const supernode *snode = enode->get_supernode ();
|
|
|
689 if (snode == NULL)
|
|
|
690 return 0;
|
|
|
691 return m_worklist.m_scc.get_scc_id (snode->m_index);
|
|
|
692 }
|
|
|
693
|
|
|
694 const worklist &m_worklist;
|
|
|
695 exploded_node *m_enode;
|
|
|
696 };
|
|
|
697
|
|
|
698 /* The order is important here: m_scc needs to stick around
|
|
|
699 until after m_queue has finished being cleaned up (the dtor
|
|
|
700 calls the ordering fns). */
|
|
|
701 const exploded_graph &m_eg;
|
|
|
702 strongly_connected_components m_scc;
|
|
|
703 const analysis_plan &m_plan;
|
|
|
704
|
|
|
705 /* Priority queue, backed by a fibonacci_heap. */
|
|
|
706 typedef fibonacci_heap<key_t, exploded_node> queue_t;
|
|
|
707 queue_t m_queue;
|
|
|
708 };
|
|
|
709
|
|
|
710 /* An exploded_graph is a directed graph of unique <point, state> pairs.
|
|
|
711 It also has a worklist of nodes that are waiting for their successors
|
|
|
712 to be added to the graph. */
|
|
|
713
|
|
|
714 class exploded_graph : public digraph<eg_traits>
|
|
|
715 {
|
|
|
716 public:
|
|
|
717 typedef hash_map <const call_string *, per_call_string_data *,
|
|
|
718 eg_call_string_hash_map_traits> call_string_data_map_t;
|
|
|
719
|
|
|
720 exploded_graph (const supergraph &sg, logger *logger,
|
|
|
721 const extrinsic_state &ext_state,
|
|
|
722 const state_purge_map *purge_map,
|
|
|
723 const analysis_plan &plan,
|
|
|
724 int verbosity);
|
|
|
725 ~exploded_graph ();
|
|
|
726
|
|
|
727 logger *get_logger () const { return m_logger.get_logger (); }
|
|
|
728
|
|
|
729 const supergraph &get_supergraph () const { return m_sg; }
|
|
|
730 const extrinsic_state &get_ext_state () const { return m_ext_state; }
|
|
|
731 const state_purge_map *get_purge_map () const { return m_purge_map; }
|
|
|
732 const analysis_plan &get_analysis_plan () const { return m_plan; }
|
|
|
733
|
|
|
734 exploded_node *get_origin () const { return m_origin; }
|
|
|
735
|
|
|
736 exploded_node *add_function_entry (function *fun);
|
|
|
737
|
|
|
738 void build_initial_worklist ();
|
|
|
739 void process_worklist ();
|
|
|
740 void process_node (exploded_node *node);
|
|
|
741
|
|
|
742 exploded_node *get_or_create_node (const program_point &point,
|
|
|
743 const program_state &state,
|
|
|
744 state_change *change);
|
|
|
745 exploded_edge *add_edge (exploded_node *src, exploded_node *dest,
|
|
|
746 const superedge *sedge,
|
|
|
747 const state_change &change,
|
|
|
748 exploded_edge::custom_info_t *custom = NULL);
|
|
|
749
|
|
|
750 per_program_point_data *
|
|
|
751 get_or_create_per_program_point_data (const program_point &);
|
|
|
752
|
|
|
753 per_call_string_data *
|
|
|
754 get_or_create_per_call_string_data (const call_string &);
|
|
|
755
|
|
|
756 per_function_data *
|
|
|
757 get_or_create_per_function_data (function *);
|
|
|
758 per_function_data *get_per_function_data (function *) const;
|
|
|
759
|
|
|
760 void save_diagnostic (const state_machine &sm,
|
|
|
761 const exploded_node *enode,
|
|
|
762 const supernode *node, const gimple *stmt,
|
|
|
763 stmt_finder *finder,
|
|
|
764 tree var, state_machine::state_t state,
|
|
|
765 pending_diagnostic *d);
|
|
|
766
|
|
|
767 diagnostic_manager &get_diagnostic_manager ()
|
|
|
768 {
|
|
|
769 return m_diagnostic_manager;
|
|
|
770 }
|
|
|
771
|
|
|
772 stats *get_global_stats () { return &m_global_stats; }
|
|
|
773 stats *get_or_create_function_stats (function *fn);
|
|
|
774 void log_stats () const;
|
|
|
775 void dump_stats (FILE *) const;
|
|
|
776 void dump_states_for_supernode (FILE *, const supernode *snode) const;
|
|
|
777 void dump_exploded_nodes () const;
|
|
|
778
|
|
|
779 const call_string_data_map_t *get_per_call_string_data () const
|
|
|
780 { return &m_per_call_string_data; }
|
|
|
781
|
|
|
782 private:
|
|
|
783 DISABLE_COPY_AND_ASSIGN (exploded_graph);
|
|
|
784
|
|
|
785 const supergraph &m_sg;
|
|
|
786
|
|
|
787 log_user m_logger;
|
|
|
788
|
|
|
789 /* Map from point/state to exploded node.
|
|
|
790 To avoid duplication we store point_and_state
|
|
|
791 *pointers* as keys, rather than point_and_state, using the
|
|
|
792 instance from within the exploded_node, with a custom hasher. */
|
|
|
793 typedef hash_map <const point_and_state *, exploded_node *,
|
|
|
794 eg_hash_map_traits> map_t;
|
|
|
795 map_t m_point_and_state_to_node;
|
|
|
796
|
|
|
797 /* Map from program_point to per-program_point data. */
|
|
|
798 typedef hash_map <const program_point *, per_program_point_data *,
|
|
|
799 eg_point_hash_map_traits> point_map_t;
|
|
|
800 point_map_t m_per_point_data;
|
|
|
801
|
|
|
802 worklist m_worklist;
|
|
|
803
|
|
|
804 exploded_node *m_origin;
|
|
|
805
|
|
|
806 const extrinsic_state &m_ext_state;
|
|
|
807
|
|
|
808 const state_purge_map *const m_purge_map;
|
|
|
809
|
|
|
810 const analysis_plan &m_plan;
|
|
|
811
|
|
|
812 typedef hash_map<function *, per_function_data *> per_function_data_t;
|
|
|
813 per_function_data_t m_per_function_data;
|
|
|
814
|
|
|
815 diagnostic_manager m_diagnostic_manager;
|
|
|
816
|
|
|
817 /* Stats. */
|
|
|
818 stats m_global_stats;
|
|
|
819 typedef ordered_hash_map<function *, stats *> function_stat_map_t;
|
|
|
820 function_stat_map_t m_per_function_stats;
|
|
|
821 stats m_functionless_stats;
|
|
|
822
|
|
|
823 call_string_data_map_t m_per_call_string_data;
|
|
|
824
|
|
|
825 auto_vec<int> m_PK_AFTER_SUPERNODE_per_snode;
|
|
|
826 };
|
|
|
827
|
|
|
828 /* A path within an exploded_graph: a sequence of edges. */
|
|
|
829
|
|
|
830 class exploded_path
|
|
|
831 {
|
|
|
832 public:
|
|
|
833 exploded_path () : m_edges () {}
|
|
|
834 exploded_path (const exploded_path &other);
|
|
|
835 exploded_path & operator= (const exploded_path &other);
|
|
|
836
|
|
|
837 unsigned length () const { return m_edges.length (); }
|
|
|
838
|
|
|
839 bool find_stmt_backwards (const gimple *search_stmt,
|
|
|
840 int *out_idx) const;
|
|
|
841
|
|
|
842 exploded_node *get_final_enode () const;
|
|
|
843
|
|
|
844 void dump_to_pp (pretty_printer *pp) const;
|
|
|
845 void dump (FILE *fp) const;
|
|
|
846 void dump () const;
|
|
|
847
|
|
|
848 bool feasible_p (logger *logger) const;
|
|
|
849
|
|
|
850 auto_vec<const exploded_edge *> m_edges;
|
|
|
851 };
|
|
|
852
|
|
|
853 /* Finding the shortest exploded_path within an exploded_graph. */
|
|
|
854
|
|
|
855 typedef shortest_paths<eg_traits, exploded_path> shortest_exploded_paths;
|
|
|
856
|
|
|
857 /* Abstract base class for use when passing NULL as the stmt for
|
|
|
858 a possible warning, allowing the choice of stmt to be deferred
|
|
|
859 until after we have an emission path (and know we're emitting a
|
|
|
860 warning). */
|
|
|
861
|
|
|
862 class stmt_finder
|
|
|
863 {
|
|
|
864 public:
|
|
|
865 virtual ~stmt_finder () {}
|
|
|
866 virtual stmt_finder *clone () const = 0;
|
|
|
867 virtual const gimple *find_stmt (const exploded_path &epath) = 0;
|
|
|
868 };
|
|
|
869
|
|
|
870 // TODO: split the above up?
|
|
|
871
|
|
|
872 } // namespace ana
|
|
|
873
|
|
|
874 #endif /* GCC_ANALYZER_EXPLODED_GRAPH_H */
|
