]>
Commit | Line | Data |
---|---|---|
004f2c07 | 1 | /* Digraph reachability. |
7adcbafe | 2 | Copyright (C) 2020-2022 Free Software Foundation, Inc. |
004f2c07 DM |
3 | Contributed by David Malcolm <dmalcolm@redhat.com>. |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it | |
8 | under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 3, or (at your option) | |
10 | any later version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but | |
13 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GCC; see the file COPYING3. If not see | |
19 | <http://www.gnu.org/licenses/>. */ | |
20 | ||
21 | #ifndef GCC_ANALYZER_REACHABILITY_H | |
22 | #define GCC_ANALYZER_REACHABILITY_H | |
23 | ||
24 | namespace ana { | |
25 | ||
26 | /* The set of nodes from which a target node in a digraph can be reached. */ | |
27 | // TODO(stage1): move to gcc | |
28 | ||
29 | template <typename GraphTraits> | |
30 | class reachability | |
31 | { | |
32 | public: | |
33 | typedef typename GraphTraits::graph_t graph_t; | |
34 | typedef typename GraphTraits::node_t node_t; | |
35 | typedef typename GraphTraits::edge_t edge_t; | |
36 | ||
37 | reachability (const graph_t &graph, | |
38 | const node_t *target_node) | |
39 | : m_indices (graph.m_nodes.length ()) | |
40 | { | |
41 | bitmap_clear (m_indices); | |
42 | auto_vec<const node_t *> worklist; | |
43 | worklist.safe_push (target_node); | |
44 | bitmap_set_bit (m_indices, target_node->m_index); | |
45 | ||
46 | while (worklist.length () > 0) | |
47 | { | |
48 | const node_t *next = worklist.pop (); | |
49 | unsigned i; | |
50 | edge_t *pred; | |
51 | FOR_EACH_VEC_ELT (next->m_preds, i, pred) | |
52 | { | |
53 | if (!reachable_from_p (pred->m_src)) | |
54 | { | |
55 | worklist.safe_push (pred->m_src); | |
56 | bitmap_set_bit (m_indices, pred->m_src->m_index); | |
57 | } | |
58 | } | |
59 | } | |
60 | } | |
61 | ||
62 | bool reachable_from_p (const node_t *src_node) const | |
63 | { | |
64 | return bitmap_bit_p (m_indices, src_node->m_index); | |
65 | } | |
66 | ||
67 | private: | |
68 | /* The nodes that can reach the target. */ | |
69 | auto_sbitmap m_indices; | |
70 | }; | |
71 | ||
72 | //TODO: selftests for reachability | |
73 | ||
74 | } // namespace ana | |
75 | ||
76 | #endif /* GCC_ANALYZER_REACHABILITY_H */ |