gcc/analyzer/reachability.h

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