gcc/analyzer/feasible-graph.h

   1 /* A graph for exploring trees of feasible paths through the egraph.
   2    Copyright (C) 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_FEASIBLE_GRAPH_H
  22 #define GCC_ANALYZER_FEASIBLE_GRAPH_H
  23
  24 namespace ana {
  25
  26 /* Forward decls.  */
  27
  28 class base_feasible_node;
  29   class feasible_node;
  30   class infeasible_node;
  31 class base_feasible_edge;
  32   class feasible_edge;
  33   class infeasible_edge;
  34 class feasible_graph;
  35 class feasible_cluster;
  36
  37 /* A traits class for feasible_graph.  */
  38
  39 struct fg_traits
  40 {
  41   typedef base_feasible_node node_t;
  42   typedef base_feasible_edge edge_t;
  43   typedef feasible_graph graph_t;
  44   struct dump_args_t
  45   {
  46     typedef typename eg_traits::dump_args_t inner_args_t;
  47
  48     dump_args_t (const inner_args_t &inner_args)
  49     : m_inner_args (inner_args)
  50     {
  51     }
  52
  53     const inner_args_t &m_inner_args;
  54   };
  55   typedef feasible_cluster cluster_t;
  56 };
  57
  58 /* Base class of node within a feasible_graph.
  59    There can be 0 or more base_feasible_nodes per exploded_node.  */
  60
  61 class base_feasible_node : public dnode<fg_traits>
  62 {
  63  public:
  64   void dump_dot_id (pretty_printer *pp) const;
  65
  66   const exploded_node *get_inner_node () const { return m_inner_node; }
  67   unsigned get_index () const { return m_index; }
  68
  69  protected:
  70   base_feasible_node (const exploded_node *inner_node, unsigned index)
  71   : m_inner_node (inner_node), m_index (index)
  72   {}
  73
  74   const exploded_node *m_inner_node;
  75   unsigned m_index;
  76 };
  77
  78 /* Subclass of base_feasible_node for a node that is reachable via a
  79    feasible path, with a particular state.  */
  80
  81 class feasible_node : public base_feasible_node
  82 {
  83 public:
  84   feasible_node (const exploded_node *inner_node, unsigned index,
  85                  const feasibility_state &state,
  86                  unsigned path_length)
  87   : base_feasible_node (inner_node, index),
  88     m_state (state),
  89     m_path_length (path_length)
  90   {
  91   }
  92
  93   void dump_dot (graphviz_out *gv,
  94                  const dump_args_t &args) const FINAL OVERRIDE;
  95
  96   const feasibility_state &get_state () const { return m_state; }
  97   const region_model &get_model () const { return m_state.get_model (); }
  98   const auto_sbitmap &get_snodes_visited () const
  99   {
 100     return m_state.get_snodes_visited ();
 101   }
 102
 103   unsigned get_path_length () const { return m_path_length; }
 104
 105 private:
 106   feasibility_state m_state;
 107   unsigned m_path_length;
 108 };
 109
 110 /* Subclass of base_feasible_node for a node that requires following
 111    an infeasible edge to reach (and thus terminating this part of the
 112    exploration).  */
 113
 114 class infeasible_node : public base_feasible_node
 115 {
 116 public:
 117   infeasible_node (const exploded_node *inner_node, unsigned index,
 118                    rejected_constraint *rc)
 119   : base_feasible_node (inner_node, index),
 120     m_rc (rc)
 121   {
 122   }
 123   ~infeasible_node () { delete m_rc; }
 124
 125   void dump_dot (graphviz_out *gv,
 126                  const dump_args_t &args) const FINAL OVERRIDE;
 127
 128 private:
 129   rejected_constraint *m_rc;
 130 };
 131
 132 /* Base class of edge within a feasible_graph.  */
 133
 134 class base_feasible_edge : public dedge<fg_traits>
 135 {
 136  public:
 137   void dump_dot (graphviz_out *gv,
 138                  const dump_args_t &args) const FINAL OVERRIDE;
 139
 140   const exploded_edge *get_inner_edge () const { return m_inner_edge; }
 141
 142  protected:
 143   base_feasible_edge (base_feasible_node *src, base_feasible_node *dest,
 144                       const exploded_edge *inner_edge)
 145   : dedge<fg_traits> (src, dest), m_inner_edge (inner_edge)
 146   {
 147   }
 148
 149   const exploded_edge *m_inner_edge;
 150 };
 151
 152 /* Subclass of base_feasible_edge for connecting two feasible_nodes.  */
 153
 154 class feasible_edge : public base_feasible_edge
 155 {
 156  public:
 157   feasible_edge (feasible_node *src, feasible_node *dest,
 158                  const exploded_edge *inner_edge)
 159   : base_feasible_edge (src, dest, inner_edge)
 160   {
 161   }
 162 };
 163
 164 /* Subclass of base_feasible_edge for connecting a feasible_node
 165    to an infeasible_node (and thus terminating this part of the
 166    exploration).  */
 167
 168 class infeasible_edge : public base_feasible_edge
 169 {
 170  public:
 171   infeasible_edge (feasible_node *src, infeasible_node *dest,
 172                    const exploded_edge *inner_edge)
 173   : base_feasible_edge (src, dest, inner_edge)
 174   {
 175   }
 176 };
 177
 178 /* A digraph subclass for exploring trees of feasible paths through
 179    the egraph.  This is actually a tree.
 180
 181    The paths within the graph of feasible_nodes express feasible paths
 182    through the graph, and it also captures known infeasible edges,
 183    which is invaluable for debugging.  */
 184
 185 class feasible_graph : public digraph <fg_traits>
 186 {
 187  public:
 188   feasible_graph ();
 189
 190   feasible_node *add_node (const exploded_node *enode,
 191                            const feasibility_state &state,
 192                            unsigned path_length);
 193
 194   void add_feasibility_problem (feasible_node *src_fnode,
 195                                 const exploded_edge *eedge,
 196                                 rejected_constraint *rc);
 197
 198   exploded_path *make_epath (feasible_node *fnode) const;
 199
 200   unsigned get_num_infeasible () const { return m_num_infeasible; }
 201
 202   void log_stats (logger *logger) const;
 203
 204 private:
 205   unsigned m_num_infeasible;
 206 };
 207
 208 class feasible_cluster : public cluster <fg_traits>
 209 {
 210 };
 211
 212 } // namespace ana
 213
 214 #endif /* GCC_ANALYZER_FEASIBLE_GRAPH_H */