1/* Digraph reachability.
2   Copyright (C) 2020 Free Software Foundation, Inc.
3   Contributed by David Malcolm <dmalcolm@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
24namespace 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
29template <typename GraphTraits>
30class reachability
31{
32public:
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
67private:
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 */
77