1 /* Digraph reachability. 2 Copyright (C) 2020-2022 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_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 reachability(const graph_t & graph,const node_t * target_node)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 reachable_from_p(const node_t * src_node)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 */ 77