1  /* Digraph reachability.
       2     Copyright (C) 2020-2023 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  
      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 */