Line data    Source code

       1              : /* Digraph reachability.
       2              :    Copyright (C) 2020-2026 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         3991 : 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         3991 :   reachability (const graph_t &graph,
      38              :                 const node_t *target_node)
      39         7982 :   : m_indices (graph.m_nodes.length ())
      40              :   {
      41         3991 :     bitmap_clear (m_indices);
      42         3991 :     auto_vec<const node_t *> worklist;
      43         3991 :     worklist.safe_push (target_node);
      44         3991 :     bitmap_set_bit (m_indices, target_node->m_index);
      45              : 
      46        68822 :     while (worklist.length () > 0)
      47              :       {
      48        64831 :         const node_t *next = worklist.pop ();
      49              :         unsigned i;
      50              :         edge_t *pred;
      51       196853 :         FOR_EACH_VEC_ELT (next->m_preds, i, pred)
      52              :           {
      53        63200 :             if (!reachable_from_p (pred->m_src))
      54              :               {
      55        60840 :                 worklist.safe_push (pred->m_src);
      56        60840 :                 bitmap_set_bit (m_indices, pred->m_src->m_index);
      57              :               }
      58              :           }
      59              :       }
      60         3991 :   }
      61              : 
      62        93757 :   bool reachable_from_p (const node_t *src_node) const
      63              :   {
      64        93757 :     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 */