Branch data     Line data    Source code

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