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