gcc/analyzer/feasible-graph.h

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