gcc/analyzer/feasible-graph.cc

   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 #include "config.h"
  22 #define INCLUDE_MEMORY
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tree.h"
  26 #include "pretty-print.h"
  27 #include "gcc-rich-location.h"
  28 #include "gimple-pretty-print.h"
  29 #include "function.h"
  30 #include "diagnostic-core.h"
  31 #include "diagnostic-event-id.h"
  32 #include "diagnostic-path.h"
  33 #include "bitmap.h"
  34 #include "ordered-hash-map.h"
  35 #include "analyzer/analyzer.h"
  36 #include "analyzer/analyzer-logging.h"
  37 #include "analyzer/sm.h"
  38 #include "analyzer/pending-diagnostic.h"
  39 #include "analyzer/diagnostic-manager.h"
  40 #include "analyzer/call-string.h"
  41 #include "analyzer/program-point.h"
  42 #include "analyzer/store.h"
  43 #include "analyzer/region-model.h"
  44 #include "analyzer/constraint-manager.h"
  45 #include "cfg.h"
  46 #include "basic-block.h"
  47 #include "gimple.h"
  48 #include "gimple-iterator.h"
  49 #include "cgraph.h"
  50 #include "digraph.h"
  51 #include "analyzer/supergraph.h"
  52 #include "analyzer/program-state.h"
  53 #include "analyzer/exploded-graph.h"
  54 #include "analyzer/feasible-graph.h"
  55
  56 #if ENABLE_ANALYZER
  57
  58 namespace ana {
  59
  60 /* class base_feasible_node : public dnode<fg_traits>.  */
  61
  62 /* Print an id to PP for this node suitable for use in .dot dumps.  */
  63
  64 void
  65 base_feasible_node::dump_dot_id (pretty_printer *pp) const
  66 {
  67   pp_printf (pp, "fnode_%i", m_index);
  68 }
  69
  70 /* class feasible_node : public base_feasible_node.  */
  71
  72 /* Implementation of dump_dot vfunc for feasible_node.  */
  73
  74 void
  75 feasible_node::dump_dot (graphviz_out *gv,
  76                         const dump_args_t &) const
  77 {
  78   pretty_printer *pp = gv->get_pp ();
  79
  80   dump_dot_id (pp);
  81   pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
  82              m_inner_node->get_dot_fillcolor ());
  83   pp_write_text_to_stream (pp);
  84
  85   pp_printf (pp, "FN: %i (EN: %i); len=%i", m_index, m_inner_node->m_index,
  86              m_path_length);
  87   pp_newline (pp);
  88
  89   format f (true);
  90   m_inner_node->get_point ().print (pp, f);
  91   pp_newline (pp);
  92
  93   /* Show the model at this point along expansion of the feasible path,
  94      rather than the model within the enode.  */
  95   m_state.get_model ().dump_to_pp (pp, true, true);
  96   pp_newline (pp);
  97
  98   m_inner_node->dump_processed_stmts (pp);
  99   m_inner_node->dump_saved_diagnostics (pp);
 100
 101   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
 102
 103   pp_string (pp, "\"];\n\n");
 104   pp_flush (pp);
 105 }
 106
 107 /* Attempt to get the region_model for this node's state at TARGET_STMT.
 108    Return true and write to *OUT if found.
 109    Return false if there's a problem.  */
 110
 111 bool
 112 feasible_node::get_state_at_stmt (const gimple *target_stmt,
 113                                   region_model *out) const
 114 {
 115   if (!target_stmt)
 116     return false;
 117
 118   feasibility_state result (m_state);
 119
 120   /* Update state for the stmts that were processed in each enode.  */
 121   for (unsigned stmt_idx = 0; stmt_idx < m_inner_node->m_num_processed_stmts;
 122        stmt_idx++)
 123     {
 124       const gimple *stmt = m_inner_node->get_processed_stmt (stmt_idx);
 125       if (stmt == target_stmt)
 126         {
 127           *out = result.get_model ();
 128           return true;
 129         }
 130       result.update_for_stmt (stmt);
 131     }
 132
 133   /* TARGET_STMT not found; wrong node?  */
 134   return false;
 135 }
 136
 137 /* Implementation of dump_dot vfunc for infeasible_node.
 138    In particular, show the rejected constraint.  */
 139
 140 void
 141 infeasible_node::dump_dot (graphviz_out *gv,
 142                            const dump_args_t &) const
 143 {
 144   pretty_printer *pp = gv->get_pp ();
 145
 146   dump_dot_id (pp);
 147   pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
 148              m_inner_node->get_dot_fillcolor ());
 149   pp_write_text_to_stream (pp);
 150
 151   pp_printf (pp, "infeasible edge to EN: %i", m_inner_node->m_index);
 152   pp_newline (pp);
 153
 154   pp_string (pp, "rejected constraint:");
 155   pp_newline (pp);
 156   m_rc->dump_to_pp (pp);
 157
 158   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
 159
 160   pp_string (pp, "\"];\n\n");
 161   pp_flush (pp);
 162 }
 163
 164 /* class base_feasible_edge : public dedge<fg_traits>.  */
 165
 166 /* Implementation of dump_dot vfunc for base_easible_edge.  */
 167
 168 void
 169 base_feasible_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
 170 {
 171   pretty_printer *pp = gv->get_pp ();
 172
 173   m_src->dump_dot_id (pp);
 174   pp_string (pp, " -> ");
 175   m_dest->dump_dot_id (pp);
 176
 177   m_inner_edge->dump_dot_label (pp);
 178 }
 179
 180 /* class feasible_graph : public digraph <fg_traits>.  */
 181
 182 /* Ctor for feasible_graph.  */
 183
 184 feasible_graph::feasible_graph ()
 185 : m_num_infeasible (0)
 186 {
 187 }
 188
 189 /* Add a feasible_node to this graph for ENODE, STATE with the
 190    given PATH_LENGTH. */
 191
 192 feasible_node *
 193 feasible_graph::add_node (const exploded_node *enode,
 194                           const feasibility_state &state,
 195                           unsigned path_length)
 196 {
 197   /* We don't attempt get_or_create here.  */
 198   feasible_node *fnode = new feasible_node (enode, m_nodes.length (),
 199                                             state, path_length);
 200   digraph<fg_traits>::add_node (fnode);
 201   return fnode;
 202 }
 203
 204 /* Add an infeasible_node to this graph and an infeasible_edge connecting
 205    to it from SRC_FNODE, capturing a failure of RC along EEDGE.  */
 206
 207 void
 208 feasible_graph::add_feasibility_problem (feasible_node *src_fnode,
 209                                          const exploded_edge *eedge,
 210                                          std::unique_ptr<rejected_constraint> rc)
 211 {
 212   infeasible_node *dst_fnode
 213     = new infeasible_node (eedge->m_dest, m_nodes.length (), std::move (rc));
 214   digraph<fg_traits>::add_node (dst_fnode);
 215   add_edge (new infeasible_edge (src_fnode, dst_fnode, eedge));
 216   m_num_infeasible++;
 217 }
 218
 219 /* Make an exploded_path from the origin to FNODE's exploded_node,
 220    following the edges in the feasible_graph.  */
 221
 222 std::unique_ptr<exploded_path>
 223 feasible_graph::make_epath (feasible_node *fnode) const
 224 {
 225   std::unique_ptr<exploded_path> epath (new exploded_path ());
 226
 227   /* FG is actually a tree.  Built the path backwards, by walking
 228      backwards from FNODE until we reach the origin.  */
 229   while (fnode->get_inner_node ()->m_index != 0)
 230     {
 231       gcc_assert (fnode->m_preds.length () == 1);
 232       feasible_edge *pred_fedge
 233         = static_cast <feasible_edge *> (fnode->m_preds[0]);
 234       epath->m_edges.safe_push (pred_fedge->get_inner_edge ());
 235       fnode = static_cast <feasible_node *> (pred_fedge->m_src);
 236     }
 237
 238   /* Now reverse it.  */
 239   epath->m_edges.reverse ();
 240
 241   return epath;
 242 }
 243
 244 /* Dump the path to DST_FNODE in textual form to PP.  */
 245
 246 void
 247 feasible_graph::dump_feasible_path (const feasible_node &dst_fnode,
 248                                     pretty_printer *pp) const
 249 {
 250   const feasible_node *fnode = &dst_fnode;
 251
 252   auto_vec<const feasible_edge *> fpath;
 253
 254   /* FG is actually a tree.  Built the path backwards, by walking
 255      backwards from FNODE until we reach the origin.  */
 256   while (fnode->get_inner_node ()->m_index != 0)
 257     {
 258       gcc_assert (fnode->m_preds.length () == 1);
 259       feasible_edge *pred_fedge
 260         = static_cast <feasible_edge *> (fnode->m_preds[0]);
 261       fpath.safe_push (pred_fedge);
 262       fnode = static_cast <const feasible_node *> (pred_fedge->m_src);
 263     }
 264
 265   /* Now reverse it.  */
 266   fpath.reverse ();
 267
 268   for (unsigned i = 0; i < fpath.length (); i++)
 269     {
 270       const feasible_edge *fedge = fpath[i];
 271       const feasible_node *src_fnode
 272         = static_cast <const feasible_node *> (fedge->m_src);
 273       const feasible_node *dest_fnode
 274         = static_cast <const feasible_node *> (fedge->m_dest);
 275
 276       pp_printf (pp, "fpath[%i]: FN %i (EN %i) -> FN %i (EN %i)",
 277                  i,
 278                  src_fnode->get_index (),
 279                  src_fnode->get_inner_node ()->m_index,
 280                  dest_fnode->get_index (),
 281                  dest_fnode->get_inner_node ()->m_index);
 282       pp_newline (pp);
 283       pp_printf (pp, "  FN %i (EN %i):",
 284                  dest_fnode->get_index (),
 285                  dest_fnode->get_inner_node ()->m_index);
 286       pp_newline (pp);
 287       const program_point &point = dest_fnode->get_inner_node ()->get_point ();
 288       point.print (pp, format (true));
 289       dest_fnode->get_state ().dump_to_pp (pp, true, true);
 290       pp_newline (pp);
 291     }
 292 }
 293
 294 /* Dump the path to DST_FNODE in textual form to FILENAME.  */
 295
 296 void
 297 feasible_graph::dump_feasible_path (const feasible_node &dst_fnode,
 298                                     const char *filename) const
 299 {
 300   FILE *fp = fopen (filename, "w");
 301   pretty_printer pp;
 302   pp_format_decoder (&pp) = default_tree_printer;
 303   pp.buffer->stream = fp;
 304   dump_feasible_path (dst_fnode, &pp);
 305   pp_flush (&pp);
 306   fclose (fp);
 307 }
 308
 309 /* Dump stats about this graph to LOGGER.  */
 310
 311 void
 312 feasible_graph::log_stats (logger *logger) const
 313 {
 314   logger->log ("#nodes: %i", m_nodes.length ());
 315   logger->log ("#edges: %i", m_edges.length ());
 316   logger->log ("#feasible nodes: %i", m_nodes.length () - m_num_infeasible);
 317   logger->log ("#feasible edges: %i", m_edges.length () - m_num_infeasible);
 318   logger->log ("#infeasible nodes/edges: %i", m_num_infeasible);
 319 }
 320
 321 } // namespace ana
 322
 323 #endif /* #if ENABLE_ANALYZER */