LCOV - code coverage report
Current view: top level - gcc/analyzer - feasible-graph.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 82.0 % 122 100
Test Date: 2024-12-21 13:15:12 Functions: 83.3 % 12 10
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* A graph for exploring trees of feasible paths through the egraph.
       2                 :             :    Copyright (C) 2021-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                 :             : #include "config.h"
      22                 :             : #define INCLUDE_VECTOR
      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                 :         356 : base_feasible_node::dump_dot_id (pretty_printer *pp) const
      66                 :             : {
      67                 :         356 :   pp_printf (pp, "fnode_%i", m_index);
      68                 :         356 : }
      69                 :             : 
      70                 :             : /* class feasible_node : public base_feasible_node.  */
      71                 :             : 
      72                 :             : /* Implementation of dump_dot vfunc for feasible_node.  */
      73                 :             : 
      74                 :             : void
      75                 :         124 : feasible_node::dump_dot (graphviz_out *gv,
      76                 :             :                         const dump_args_t &) const
      77                 :             : {
      78                 :         124 :   pretty_printer *pp = gv->get_pp ();
      79                 :             : 
      80                 :         124 :   dump_dot_id (pp);
      81                 :         124 :   pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
      82                 :         124 :              m_inner_node->get_dot_fillcolor ());
      83                 :         124 :   pp_write_text_to_stream (pp);
      84                 :             : 
      85                 :         124 :   pp_printf (pp, "FN: %i (EN: %i); len=%i", m_index, m_inner_node->m_index,
      86                 :         124 :              m_path_length);
      87                 :         124 :   pp_newline (pp);
      88                 :             : 
      89                 :         124 :   format f (true);
      90                 :         124 :   m_inner_node->get_point ().print (pp, f);
      91                 :         124 :   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                 :         124 :   m_state.get_model ().dump_to_pp (pp, true, true);
      96                 :         124 :   pp_newline (pp);
      97                 :             : 
      98                 :         124 :   m_inner_node->dump_processed_stmts (pp);
      99                 :         124 :   m_inner_node->dump_saved_diagnostics (pp);
     100                 :             : 
     101                 :         124 :   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
     102                 :             : 
     103                 :         124 :   pp_string (pp, "\"];\n\n");
     104                 :         124 :   pp_flush (pp);
     105                 :         124 : }
     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                 :        1131 : feasible_node::get_state_at_stmt (const gimple *target_stmt,
     113                 :             :                                   region_model *out) const
     114                 :             : {
     115                 :        1131 :   if (!target_stmt)
     116                 :             :     return false;
     117                 :             : 
     118                 :        1131 :   feasibility_state result (m_state);
     119                 :             : 
     120                 :             :   /* Update state for the stmts that were processed in each enode.  */
     121                 :        2579 :   for (unsigned stmt_idx = 0; stmt_idx < m_inner_node->m_num_processed_stmts;
     122                 :             :        stmt_idx++)
     123                 :             :     {
     124                 :        2469 :       const gimple *stmt = m_inner_node->get_processed_stmt (stmt_idx);
     125                 :        2469 :       if (stmt == target_stmt)
     126                 :             :         {
     127                 :        1021 :           *out = result.get_model ();
     128                 :        1021 :           return true;
     129                 :             :         }
     130                 :        1448 :       result.update_for_stmt (stmt);
     131                 :             :     }
     132                 :             : 
     133                 :             :   /* TARGET_STMT not found; wrong node?  */
     134                 :             :   return false;
     135                 :        1131 : }
     136                 :             : 
     137                 :             : /* Implementation of dump_dot vfunc for infeasible_node.
     138                 :             :    In particular, show the rejected constraint.  */
     139                 :             : 
     140                 :             : void
     141                 :           0 : infeasible_node::dump_dot (graphviz_out *gv,
     142                 :             :                            const dump_args_t &) const
     143                 :             : {
     144                 :           0 :   pretty_printer *pp = gv->get_pp ();
     145                 :             : 
     146                 :           0 :   dump_dot_id (pp);
     147                 :           0 :   pp_printf (pp, " [shape=none,margin=0,style=filled,fillcolor=%s,label=\"",
     148                 :           0 :              m_inner_node->get_dot_fillcolor ());
     149                 :           0 :   pp_write_text_to_stream (pp);
     150                 :             : 
     151                 :           0 :   pp_printf (pp, "infeasible edge to EN: %i", m_inner_node->m_index);
     152                 :           0 :   pp_newline (pp);
     153                 :             : 
     154                 :           0 :   pp_string (pp, "rejected constraint:");
     155                 :           0 :   pp_newline (pp);
     156                 :           0 :   m_rc->dump_to_pp (pp);
     157                 :             : 
     158                 :           0 :   pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
     159                 :             : 
     160                 :           0 :   pp_string (pp, "\"];\n\n");
     161                 :           0 :   pp_flush (pp);
     162                 :           0 : }
     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                 :         116 : base_feasible_edge::dump_dot (graphviz_out *gv, const dump_args_t &) const
     170                 :             : {
     171                 :         116 :   pretty_printer *pp = gv->get_pp ();
     172                 :             : 
     173                 :         116 :   m_src->dump_dot_id (pp);
     174                 :         116 :   pp_string (pp, " -> ");
     175                 :         116 :   m_dest->dump_dot_id (pp);
     176                 :             : 
     177                 :         116 :   m_inner_edge->dump_dot_label (pp);
     178                 :         116 : }
     179                 :             : 
     180                 :             : /* class feasible_graph : public digraph <fg_traits>.  */
     181                 :             : 
     182                 :             : /* Ctor for feasible_graph.  */
     183                 :             : 
     184                 :        6624 : feasible_graph::feasible_graph ()
     185                 :        6624 : : m_num_infeasible (0)
     186                 :             : {
     187                 :        6624 : }
     188                 :             : 
     189                 :             : /* Add a feasible_node to this graph for ENODE, STATE with the
     190                 :             :    given PATH_LENGTH. */
     191                 :             : 
     192                 :             : feasible_node *
     193                 :      163991 : 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                 :      163991 :   feasible_node *fnode = new feasible_node (enode, m_nodes.length (),
     199                 :      321358 :                                             state, path_length);
     200                 :      163991 :   digraph<fg_traits>::add_node (fnode);
     201                 :      163991 :   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                 :        2010 : feasible_graph::add_feasibility_problem (feasible_node *src_fnode,
     209                 :             :                                          const exploded_edge *eedge,
     210                 :             :                                          std::unique_ptr<rejected_constraint> rc)
     211                 :             : {
     212                 :        2010 :   infeasible_node *dst_fnode
     213                 :        4020 :     = new infeasible_node (eedge->m_dest, m_nodes.length (), std::move (rc));
     214                 :        2010 :   digraph<fg_traits>::add_node (dst_fnode);
     215                 :        2010 :   add_edge (new infeasible_edge (src_fnode, dst_fnode, eedge));
     216                 :        2010 :   m_num_infeasible++;
     217                 :        2010 : }
     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                 :        6351 : feasible_graph::make_epath (feasible_node *fnode) const
     224                 :             : {
     225                 :        6351 :   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                 :      106882 :   while (fnode->get_inner_node ()->m_index != 0)
     230                 :             :     {
     231                 :      100531 :       gcc_assert (fnode->m_preds.length () == 1);
     232                 :      100531 :       feasible_edge *pred_fedge
     233                 :      100531 :         = static_cast <feasible_edge *> (fnode->m_preds[0]);
     234                 :      100531 :       epath->m_edges.safe_push (pred_fedge->get_inner_edge ());
     235                 :      100531 :       fnode = static_cast <feasible_node *> (pred_fedge->m_src);
     236                 :             :     }
     237                 :             : 
     238                 :             :   /* Now reverse it.  */
     239                 :        6351 :   epath->m_edges.reverse ();
     240                 :             : 
     241                 :        6351 :   return epath;
     242                 :             : }
     243                 :             : 
     244                 :             : /* Dump the path to DST_FNODE in textual form to PP.  */
     245                 :             : 
     246                 :             : void
     247                 :           8 : feasible_graph::dump_feasible_path (const feasible_node &dst_fnode,
     248                 :             :                                     pretty_printer *pp) const
     249                 :             : {
     250                 :           8 :   const feasible_node *fnode = &dst_fnode;
     251                 :             : 
     252                 :           8 :   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                 :         124 :   while (fnode->get_inner_node ()->m_index != 0)
     257                 :             :     {
     258                 :         116 :       gcc_assert (fnode->m_preds.length () == 1);
     259                 :         116 :       feasible_edge *pred_fedge
     260                 :         116 :         = static_cast <feasible_edge *> (fnode->m_preds[0]);
     261                 :         116 :       fpath.safe_push (pred_fedge);
     262                 :         116 :       fnode = static_cast <const feasible_node *> (pred_fedge->m_src);
     263                 :             :     }
     264                 :             : 
     265                 :             :   /* Now reverse it.  */
     266                 :           8 :   fpath.reverse ();
     267                 :             : 
     268                 :         124 :   for (unsigned i = 0; i < fpath.length (); i++)
     269                 :             :     {
     270                 :         116 :       const feasible_edge *fedge = fpath[i];
     271                 :         116 :       const feasible_node *src_fnode
     272                 :             :         = static_cast <const feasible_node *> (fedge->m_src);
     273                 :         116 :       const feasible_node *dest_fnode
     274                 :             :         = static_cast <const feasible_node *> (fedge->m_dest);
     275                 :             : 
     276                 :         116 :       pp_printf (pp, "fpath[%i]: FN %i (EN %i) -> FN %i (EN %i)",
     277                 :             :                  i,
     278                 :             :                  src_fnode->get_index (),
     279                 :         116 :                  src_fnode->get_inner_node ()->m_index,
     280                 :             :                  dest_fnode->get_index (),
     281                 :         116 :                  dest_fnode->get_inner_node ()->m_index);
     282                 :         116 :       pp_newline (pp);
     283                 :         116 :       pp_printf (pp, "  FN %i (EN %i):",
     284                 :             :                  dest_fnode->get_index (),
     285                 :         116 :                  dest_fnode->get_inner_node ()->m_index);
     286                 :         116 :       pp_newline (pp);
     287                 :         116 :       const program_point &point = dest_fnode->get_inner_node ()->get_point ();
     288                 :         116 :       point.print (pp, format (true));
     289                 :         116 :       dest_fnode->get_state ().dump_to_pp (pp, true, true);
     290                 :         116 :       pp_newline (pp);
     291                 :             :     }
     292                 :           8 : }
     293                 :             : 
     294                 :             : /* Dump the path to DST_FNODE in textual form to FILENAME.  */
     295                 :             : 
     296                 :             : void
     297                 :           8 : feasible_graph::dump_feasible_path (const feasible_node &dst_fnode,
     298                 :             :                                     const char *filename) const
     299                 :             : {
     300                 :           8 :   FILE *fp = fopen (filename, "w");
     301                 :           8 :   pretty_printer pp;
     302                 :           8 :   pp_format_decoder (&pp) = default_tree_printer;
     303                 :           8 :   pp.set_output_stream (fp);
     304                 :           8 :   dump_feasible_path (dst_fnode, &pp);
     305                 :           8 :   pp_flush (&pp);
     306                 :           8 :   fclose (fp);
     307                 :           8 : }
     308                 :             : 
     309                 :             : /* Dump stats about this graph to LOGGER.  */
     310                 :             : 
     311                 :             : void
     312                 :           0 : feasible_graph::log_stats (logger *logger) const
     313                 :             : {
     314                 :           0 :   logger->log ("#nodes: %i", m_nodes.length ());
     315                 :           0 :   logger->log ("#edges: %i", m_edges.length ());
     316                 :           0 :   logger->log ("#feasible nodes: %i", m_nodes.length () - m_num_infeasible);
     317                 :           0 :   logger->log ("#feasible edges: %i", m_edges.length () - m_num_infeasible);
     318                 :           0 :   logger->log ("#infeasible nodes/edges: %i", m_num_infeasible);
     319                 :           0 : }
     320                 :             : 
     321                 :             : } // namespace ana
     322                 :             : 
     323                 :             : #endif /* #if ENABLE_ANALYZER */
        

Generated by: LCOV version 2.1-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.