LCOV - code coverage report
Current view: top level - gcc/analyzer - infinite-loop.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 77.5 % 267 207
Test Date: 2024-11-30 13:30:02 Functions: 88.9 % 18 16
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Detection of infinite loops.
       2                 :             :    Copyright (C) 2022-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 "fold-const.h"
      27                 :             : #include "gcc-rich-location.h"
      28                 :             : #include "alloc-pool.h"
      29                 :             : #include "fibonacci_heap.h"
      30                 :             : #include "shortest-paths.h"
      31                 :             : #include "diagnostic-core.h"
      32                 :             : #include "diagnostic-event-id.h"
      33                 :             : #include "diagnostic-path.h"
      34                 :             : #include "function.h"
      35                 :             : #include "pretty-print.h"
      36                 :             : #include "sbitmap.h"
      37                 :             : #include "bitmap.h"
      38                 :             : #include "tristate.h"
      39                 :             : #include "ordered-hash-map.h"
      40                 :             : #include "selftest.h"
      41                 :             : #include "json.h"
      42                 :             : #include "analyzer/analyzer.h"
      43                 :             : #include "analyzer/analyzer-logging.h"
      44                 :             : #include "analyzer/call-string.h"
      45                 :             : #include "analyzer/program-point.h"
      46                 :             : #include "analyzer/store.h"
      47                 :             : #include "analyzer/region-model.h"
      48                 :             : #include "analyzer/constraint-manager.h"
      49                 :             : #include "analyzer/sm.h"
      50                 :             : #include "analyzer/pending-diagnostic.h"
      51                 :             : #include "analyzer/diagnostic-manager.h"
      52                 :             : #include "cfg.h"
      53                 :             : #include "basic-block.h"
      54                 :             : #include "gimple.h"
      55                 :             : #include "gimple-iterator.h"
      56                 :             : #include "gimple-pretty-print.h"
      57                 :             : #include "cgraph.h"
      58                 :             : #include "digraph.h"
      59                 :             : #include "analyzer/supergraph.h"
      60                 :             : #include "analyzer/program-state.h"
      61                 :             : #include "analyzer/exploded-graph.h"
      62                 :             : #include "analyzer/checker-path.h"
      63                 :             : #include "analyzer/feasible-graph.h"
      64                 :             : #include "make-unique.h"
      65                 :             : #include "diagnostic-format-sarif.h"
      66                 :             : 
      67                 :             : /* A bundle of data characterizing a particular infinite loop
      68                 :             :    identified within the exploded graph.  */
      69                 :             : 
      70                 :          88 : struct infinite_loop
      71                 :             : {
      72                 :          88 :   infinite_loop (const exploded_node &enode,
      73                 :             :                 location_t loc,
      74                 :             :                 std::vector<const exploded_edge *> &&eedges,
      75                 :             :                 logger *logger)
      76                 :          88 :   : m_enode (enode),
      77                 :          88 :     m_loc (loc),
      78                 :          88 :     m_eedge_vec (eedges)
      79                 :             :   {
      80                 :          88 :     LOG_SCOPE (logger);
      81                 :          88 :     if (logger)
      82                 :             :       {
      83                 :           0 :         logger->start_log_line ();
      84                 :           0 :         logger->log_partial ("infinite loop: EN: %i", m_enode.m_index);
      85                 :           0 :         for (auto eedge : m_eedge_vec)
      86                 :             :           {
      87                 :           0 :             logger->log_partial (" ->");
      88                 :           0 :             if (const superedge *sedge = eedge->m_sedge)
      89                 :             :               {
      90                 :           0 :                 sedge->dump_label_to_pp (logger->get_printer (), false);
      91                 :             :               }
      92                 :           0 :             logger->log_partial (" EN: %i", eedge->m_dest->m_index);
      93                 :             :           }
      94                 :           0 :         logger->end_log_line ();
      95                 :             :       }
      96                 :          88 :   }
      97                 :             : 
      98                 :             :   bool
      99                 :          87 :   operator== (const infinite_loop &other) const
     100                 :             :   {
     101                 :             :     /* Compare underlying supernode, rather than enodes, so that
     102                 :             :        we don't get duplicates in functions that are called from
     103                 :             :        elsewhere.  */
     104                 :          87 :     return (m_enode.get_supernode () == other.m_enode.get_supernode ()
     105                 :          87 :             && m_loc == other.m_loc);
     106                 :             :   }
     107                 :             : 
     108                 :             :   std::unique_ptr<json::object>
     109                 :           0 :   to_json () const
     110                 :             :   {
     111                 :           0 :     auto loop_obj = ::make_unique<json::object> ();
     112                 :           0 :     loop_obj->set_integer ("enode", m_enode.m_index);
     113                 :           0 :     auto edge_arr = ::make_unique<json::array> ();
     114                 :           0 :     for (auto eedge : m_eedge_vec)
     115                 :           0 :       edge_arr->append (eedge->to_json ());
     116                 :           0 :     loop_obj->set ("eedges", std::move (edge_arr));
     117                 :           0 :     return loop_obj;
     118                 :           0 :   }
     119                 :             : 
     120                 :             :   const exploded_node &m_enode;
     121                 :             :   location_t m_loc;
     122                 :             :   std::vector<const exploded_edge *> m_eedge_vec;
     123                 :             : };
     124                 :             : 
     125                 :             : /* A custom subclass of start_cfg_edge_event that rewords the
     126                 :             :    message to indicate that the CFG edge is *always* taken on
     127                 :             :    subsequent iterations, assuming it's been taken once. */
     128                 :             : 
     129                 :             : class perpetual_start_cfg_edge_event : public start_cfg_edge_event
     130                 :             : {
     131                 :             : public:
     132                 :          55 :   perpetual_start_cfg_edge_event (const exploded_edge &eedge,
     133                 :             :                                   const event_loc_info &loc_info)
     134                 :          55 :   : start_cfg_edge_event (eedge, loc_info)
     135                 :             :   {
     136                 :             :   }
     137                 :             : 
     138                 :         110 :   void print_desc (pretty_printer &pp) const final override
     139                 :             :   {
     140                 :         110 :     bool user_facing = !flag_analyzer_verbose_edges;
     141                 :         110 :     label_text edge_desc (m_sedge->get_description (user_facing));
     142                 :         110 :     if (user_facing)
     143                 :             :       {
     144                 :         110 :         if (edge_desc.get () && strlen (edge_desc.get ()) > 0)
     145                 :             :           {
     146                 :         110 :             label_text cond_desc
     147                 :         110 :               = maybe_describe_condition (pp_show_color (&pp));
     148                 :         110 :             if (cond_desc.get ())
     149                 :          92 :               pp_printf (&pp,
     150                 :             :                          "%s: always following %qs branch...",
     151                 :             :                          cond_desc.get (), edge_desc.get ());
     152                 :             :             else
     153                 :          18 :               pp_printf (&pp,
     154                 :             :                          "if it ever follows %qs branch,"
     155                 :             :                          " it will always do so...",
     156                 :             :                          edge_desc.get ());
     157                 :         110 :           }
     158                 :             :       }
     159                 :             :     else
     160                 :           0 :       return start_cfg_edge_event::print_desc (pp);
     161                 :         110 :   }
     162                 :             : };
     163                 :             : 
     164                 :             : class looping_back_event : public start_cfg_edge_event
     165                 :             : {
     166                 :             : public:
     167                 :          68 :   looping_back_event (const exploded_edge &eedge,
     168                 :             :                       const event_loc_info &loc_info)
     169                 :          68 :   : start_cfg_edge_event (eedge, loc_info)
     170                 :             :   {
     171                 :             :   }
     172                 :             : 
     173                 :         136 :   void print_desc (pretty_printer &pp) const final override
     174                 :             :   {
     175                 :         136 :     pp_string (&pp, "looping back...");
     176                 :         136 :   }
     177                 :             : };
     178                 :             : 
     179                 :             : /* A subclass of pending_diagnostic for complaining about suspected
     180                 :             :    infinite loops.  */
     181                 :             : 
     182                 :             : class infinite_loop_diagnostic
     183                 :             : : public pending_diagnostic_subclass<infinite_loop_diagnostic>
     184                 :             : {
     185                 :             : public:
     186                 :          88 :   infinite_loop_diagnostic (std::unique_ptr<infinite_loop> inf_loop)
     187                 :          88 :     : m_inf_loop (std::move (inf_loop))
     188                 :             :   {
     189                 :          88 :     gcc_assert (m_inf_loop != nullptr);
     190                 :          88 :   }
     191                 :             : 
     192                 :         341 :   const char *get_kind () const final override
     193                 :             :   {
     194                 :         341 :     return "infinite_loop_diagnostic";
     195                 :             :   }
     196                 :             : 
     197                 :          87 :   bool operator== (const infinite_loop_diagnostic &other) const
     198                 :             :   {
     199                 :          87 :     return *m_inf_loop == *other.m_inf_loop;
     200                 :             :   }
     201                 :             : 
     202                 :          79 :   int get_controlling_option () const final override
     203                 :             :   {
     204                 :          79 :     return OPT_Wanalyzer_infinite_loop;
     205                 :             :   }
     206                 :             : 
     207                 :          79 :   bool emit (diagnostic_emission_context &ctxt) final override
     208                 :             :   {
     209                 :             :     /* "CWE-835: Loop with Unreachable Exit Condition ('Infinite Loop')". */
     210                 :          79 :     ctxt.add_cwe (835);
     211                 :          79 :     return ctxt.warn ("infinite loop");
     212                 :             :   }
     213                 :             : 
     214                 :         386 :   bool maybe_add_custom_events_for_superedge (const exploded_edge &,
     215                 :             :                                               checker_path *)
     216                 :             :     final override
     217                 :             :   {
     218                 :             :     /* Don't add any regular events; instead we add them after pruning as
     219                 :             :        part of the "final" warning.  */
     220                 :         386 :     return true;
     221                 :             :   }
     222                 :             : 
     223                 :             :   bool
     224                 :         158 :   describe_final_event (pretty_printer &pp,
     225                 :             :                         const evdesc::final_event &) final override
     226                 :             :   {
     227                 :         158 :     pp_string (&pp, "infinite loop here");
     228                 :         158 :     return true;
     229                 :             :   }
     230                 :             : 
     231                 :             :   /* Customize the location where the warning_event appears.  */
     232                 :          79 :   void add_final_event (const state_machine *,
     233                 :             :                         const exploded_node *enode,
     234                 :             :                         const event_loc_info &,
     235                 :             :                         tree,
     236                 :             :                         state_machine::state_t,
     237                 :             :                         checker_path *emission_path) final override
     238                 :             :   {
     239                 :          79 :     emission_path->add_event
     240                 :          79 :       (make_unique<warning_event>
     241                 :         158 :        (event_loc_info (m_inf_loop->m_loc,
     242                 :         158 :                         enode->get_function ()->decl,
     243                 :          79 :                         enode->get_stack_depth ()),
     244                 :             :         enode,
     245                 :          79 :         nullptr, nullptr, nullptr));
     246                 :             : 
     247                 :          79 :     logger *logger = emission_path->get_logger ();
     248                 :             : 
     249                 :             :     /* EMISSION_PATH has the path to the entry of the infinite loop.
     250                 :             :        Add extra edges showing the loop itself.  */
     251                 :         488 :     for (auto eedge : m_inf_loop->m_eedge_vec)
     252                 :             :       {
     253                 :         409 :         if (logger)
     254                 :           0 :           logger->log ("EN: %i -> EN: %i",
     255                 :           0 :                        eedge->m_src->m_index,
     256                 :           0 :                        eedge->m_dest->m_index);
     257                 :         409 :         if (!eedge->m_sedge)
     258                 :         273 :           continue;
     259                 :             : 
     260                 :         140 :         const cfg_superedge *cfg_sedge
     261                 :         140 :           = eedge->m_sedge->dyn_cast_cfg_superedge ();
     262                 :         140 :         if (!cfg_sedge)
     263                 :           4 :           continue;
     264                 :             : 
     265                 :         136 :         const exploded_node *src_node = eedge->m_src;
     266                 :         136 :         const program_point &src_point = src_node->get_point ();
     267                 :         136 :         const exploded_node *dst_node = eedge->m_dest;
     268                 :         136 :         const program_point &dst_point = dst_node->get_point ();
     269                 :         136 :         const int src_stack_depth = src_point.get_stack_depth ();
     270                 :         136 :         const int dst_stack_depth = dst_point.get_stack_depth ();
     271                 :         136 :         const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt ();
     272                 :             : 
     273                 :         136 :         event_loc_info loc_info_from
     274                 :          31 :           (last_stmt ? last_stmt->location : cfg_sedge->get_goto_locus (),
     275                 :             :            src_point.get_fndecl (),
     276                 :         136 :            src_stack_depth);
     277                 :         136 :         event_loc_info loc_info_to
     278                 :             :           (dst_point.get_supernode ()->get_start_location (),
     279                 :             :            dst_point.get_fndecl (),
     280                 :         136 :            dst_stack_depth);
     281                 :             : 
     282                 :         272 :         if (const switch_cfg_superedge *switch_cfg_sedge
     283                 :         136 :               = cfg_sedge->dyn_cast_switch_cfg_superedge ())
     284                 :             :           {
     285                 :           7 :             if (switch_cfg_sedge->implicitly_created_default_p ())
     286                 :             :               {
     287                 :           6 :                 emission_path->add_event
     288                 :           6 :                   (make_unique<perpetual_start_cfg_edge_event> (*eedge,
     289                 :             :                                                                 loc_info_from));
     290                 :           6 :                 emission_path->add_event
     291                 :           6 :                   (make_unique<end_cfg_edge_event>
     292                 :          12 :                    (*eedge,
     293                 :             :                     loc_info_to));
     294                 :             :               }
     295                 :             :           }
     296                 :             : 
     297                 :         136 :         if (cfg_sedge->true_value_p ())
     298                 :             :           {
     299                 :          49 :             emission_path->add_event
     300                 :          49 :               (make_unique<perpetual_start_cfg_edge_event> (*eedge,
     301                 :             :                                                             loc_info_from));
     302                 :          49 :             emission_path->add_event
     303                 :          49 :               (make_unique<end_cfg_edge_event>
     304                 :          98 :                (*eedge,
     305                 :             :                 loc_info_to));
     306                 :             :           }
     307                 :          87 :         else if (cfg_sedge->false_value_p ())
     308                 :             :           {
     309                 :           0 :             emission_path->add_event
     310                 :           0 :               (make_unique<perpetual_start_cfg_edge_event> (*eedge,
     311                 :             :                                                             loc_info_from));
     312                 :           0 :             emission_path->add_event
     313                 :           0 :               (make_unique<end_cfg_edge_event>
     314                 :           0 :                (*eedge,
     315                 :             :                 loc_info_to));
     316                 :             :           }
     317                 :          87 :         else if (cfg_sedge->back_edge_p ())
     318                 :             :           {
     319                 :          68 :             emission_path->add_event
     320                 :          68 :               (make_unique<looping_back_event> (*eedge, loc_info_from));
     321                 :          68 :             emission_path->add_event
     322                 :          68 :               (make_unique<end_cfg_edge_event>
     323                 :         136 :                (*eedge,
     324                 :             :                 loc_info_to));
     325                 :             :           }
     326                 :             :       }
     327                 :          79 :   }
     328                 :             : 
     329                 :           0 :   void maybe_add_sarif_properties (sarif_object &result_obj)
     330                 :             :     const final override
     331                 :             :   {
     332                 :           0 :     sarif_property_bag &props = result_obj.get_or_create_properties ();
     333                 :             : #define PROPERTY_PREFIX "gcc/analyzer/infinite_loop_diagnostic/"
     334                 :           0 :     props.set (PROPERTY_PREFIX "inf_loop", m_inf_loop->to_json ());
     335                 :             : #undef PROPERTY_PREFIX
     336                 :           0 :   }
     337                 :             : 
     338                 :             : private:
     339                 :             :   std::unique_ptr<infinite_loop> m_inf_loop;
     340                 :             : };
     341                 :             : 
     342                 :             : /* If ENODE has an in-edge corresponding to a CFG backedge, return that
     343                 :             :    exploded in-edge.
     344                 :             :    Otherwise, return nullptr.  */
     345                 :             : 
     346                 :             : static const exploded_edge *
     347                 :      358035 : get_in_edge_back_edge (const exploded_node &enode)
     348                 :             : {
     349                 :     1435148 :   for (auto in_edge : enode.m_preds)
     350                 :             :     {
     351                 :      372558 :       const superedge *sedge = in_edge->m_sedge;
     352                 :      372558 :       if (!sedge)
     353                 :      253259 :         continue;
     354                 :      119299 :       const cfg_superedge *cfg_sedge = sedge->dyn_cast_cfg_superedge ();
     355                 :      119299 :       if (!cfg_sedge)
     356                 :       12840 :         continue;
     357                 :      106459 :       if (cfg_sedge->back_edge_p ())
     358                 :             :         return in_edge;
     359                 :             :     }
     360                 :             :   return nullptr;
     361                 :             : }
     362                 :             : 
     363                 :             : /* Subclass of region_model_context that rejects conditional branches that
     364                 :             :    aren't known for definite.  */
     365                 :             : 
     366                 :             : class infinite_loop_checking_context : public noop_region_model_context
     367                 :             : {
     368                 :             : public:
     369                 :       21731 :   infinite_loop_checking_context () : m_unusable (false) {}
     370                 :             : 
     371                 :        4868 :   bool checking_for_infinite_loop_p () const override { return true; }
     372                 :        3276 :   void on_unusable_in_infinite_loop () override { m_unusable = true; }
     373                 :             : 
     374                 :       21731 :   bool unusable_p () const { return m_unusable; }
     375                 :             : 
     376                 :             : private:
     377                 :             :   bool m_unusable;
     378                 :             : };
     379                 :             : 
     380                 :             : /* Determine if an infinite loop starts at ENODE.
     381                 :             :    Return the loop if it is found, nullptr otherwise.
     382                 :             : 
     383                 :             :    Look for cycles in the exploded graph in which:
     384                 :             :    - no externally visible work occurs
     385                 :             :    - no escape from the cycle
     386                 :             :    - the program state is "sufficiently concrete" at each step:
     387                 :             :      - no unknown activity could be occurring
     388                 :             :      - the worklist was fully drained for each enode in the cycle
     389                 :             :        i.e. every enode in the cycle is processed.  */
     390                 :             : 
     391                 :             : static std::unique_ptr<infinite_loop>
     392                 :      358035 : starts_infinite_loop_p (const exploded_node &enode,
     393                 :             :                         const exploded_graph &eg,
     394                 :             :                         logger *logger)
     395                 :             : {
     396                 :      358035 :   LOG_FUNC_1 (logger, "considering EN: %i", enode.m_index);
     397                 :             : 
     398                 :             :   /* Only consider enodes that have a CFG back edge as an in-edge.  */
     399                 :      358035 :   if (const exploded_edge *back_edge = get_in_edge_back_edge (enode))
     400                 :             :     {
     401                 :        5129 :       if (logger)
     402                 :           9 :         logger->log ("got backedge from EN: %i",
     403                 :           9 :                      back_edge->m_src->m_index);
     404                 :             :     }
     405                 :             :   else
     406                 :             :     {
     407                 :      352906 :       if (logger)
     408                 :         106 :         logger->log ("rejecting: no backedge in in-edges");
     409                 :      352906 :       return nullptr;
     410                 :             :     }
     411                 :             : 
     412                 :             :   /* Support for dumping an .infinite-loop.dot file visualizing the
     413                 :             :      traversal for this enode.  */
     414                 :        5129 :   std::unique_ptr<feasible_graph> fg;
     415                 :        5129 :   feasible_node *curr_fnode = nullptr;
     416                 :             : 
     417                 :        5129 :   if (flag_dump_analyzer_infinite_loop)
     418                 :           0 :     fg = ::make_unique<feasible_graph> ();
     419                 :             : 
     420                 :        5129 :   location_t first_loc = UNKNOWN_LOCATION;
     421                 :        5129 :   const exploded_node *iter = &enode;
     422                 :        5129 :   feasibility_state state (*enode.get_state ().m_region_model,
     423                 :        5129 :                            eg.get_supergraph ());
     424                 :             : 
     425                 :        5129 :   if (fg)
     426                 :           0 :     curr_fnode = fg->add_node (&enode, state, 0);
     427                 :             : 
     428                 :        5129 :   hash_set<const exploded_node *> visited;
     429                 :        5129 :   std::vector<const exploded_edge *> eedges;
     430                 :       16478 :   while (1)
     431                 :             :     {
     432                 :       21607 :       if (logger)
     433                 :          27 :         logger->log ("iter: EN: %i", iter->m_index);
     434                 :             :       /* Analysis bailed out before processing this node.  */
     435                 :       21607 :       if (iter->get_status () == exploded_node::STATUS_WORKLIST)
     436                 :             :         {
     437                 :           5 :           if (logger)
     438                 :           0 :             logger->log ("rejecting: EN: %i is still in worklist",
     439                 :           0 :                          iter->m_index);
     440                 :        5129 :           return nullptr;
     441                 :             :         }
     442                 :       21602 :       if (visited.contains (iter))
     443                 :             :         {
     444                 :             :           /* We've looped back on ourselves.  ENODE is in the loop
     445                 :             :              itself if ENODE is the first place we looped back,
     446                 :             :              as opposed to being on a path to a loop.  */
     447                 :         251 :           if (iter == &enode)
     448                 :             :             {
     449                 :          88 :               if (logger)
     450                 :           0 :                 logger->log ("accepting: looped back to EN: %i",
     451                 :           0 :                              iter->m_index);
     452                 :          88 :               if (fg)
     453                 :             :                 {
     454                 :           0 :                   auto_timevar tv (TV_ANALYZER_DUMP);
     455                 :           0 :                   pretty_printer pp;
     456                 :           0 :                   pp_printf (&pp, "%s.en%i.infinite-loop.dot",
     457                 :           0 :                              dump_base_name, enode.m_index);
     458                 :           0 :                   char *filename = xstrdup (pp_formatted_text (&pp));
     459                 :           0 :                   feasible_graph::dump_args_t dump_args (eg);
     460                 :           0 :                   fg->dump_dot (filename, nullptr, dump_args);
     461                 :           0 :                   free (filename);
     462                 :           0 :                 }
     463                 :          88 :               return ::make_unique<infinite_loop> (enode,
     464                 :             :                                                    first_loc,
     465                 :             :                                                    std::move (eedges),
     466                 :          88 :                                                    logger);
     467                 :             :             }
     468                 :             :           else
     469                 :             :             {
     470                 :         163 :               if (logger)
     471                 :           0 :                 logger->log ("rejecting: looped back to EN: %i, not to EN: %i",
     472                 :           0 :                              iter->m_index, enode.m_index);
     473                 :         163 :               return nullptr;
     474                 :             :             }
     475                 :             :         }
     476                 :       21351 :       visited.add (iter);
     477                 :       21351 :       if (first_loc == UNKNOWN_LOCATION)
     478                 :             :         {
     479                 :        5165 :           location_t enode_loc = iter->get_point ().get_location ();
     480                 :        5165 :           if (enode_loc != UNKNOWN_LOCATION)
     481                 :        5117 :             first_loc = enode_loc;
     482                 :             :         }
     483                 :             : 
     484                 :             :       /* Find the out-edges that are feasible, given the
     485                 :             :          constraints here.  */
     486                 :       21351 :       typedef std::pair<feasibility_state, const exploded_edge *> pair_t;
     487                 :       21351 :       std::vector<pair_t> succs;
     488                 :       81704 :       for (auto out_edge : iter->m_succs)
     489                 :             :         {
     490                 :       21731 :           log_scope s (logger, "considering out-edge",
     491                 :             :                        "EN:%i -> EN:%i",
     492                 :       21731 :                        out_edge->m_src->m_index,
     493                 :       21731 :                        out_edge->m_dest->m_index);
     494                 :       21731 :           feasibility_state next_state (state);
     495                 :             : 
     496                 :             :           /* Use this context to require edge conditions to be known,
     497                 :             :              rather than be merely "possible".  */
     498                 :       21731 :           infinite_loop_checking_context ctxt;
     499                 :       21731 :           if (next_state.maybe_update_for_edge (logger,
     500                 :             :                                                 out_edge,
     501                 :             :                                                 &ctxt,
     502                 :             :                                                 nullptr))
     503                 :       17886 :             succs.push_back (pair_t (next_state, out_edge));
     504                 :       21731 :           if (ctxt.unusable_p ())
     505                 :             :             {
     506                 :             :               /* If we get here, then we have e.g. a gcond where
     507                 :             :                  the condition is UNKNOWN, or a condition
     508                 :             :                  based on a widening_svalue.  Reject such paths.  */
     509                 :        3276 :               if (logger)
     510                 :           6 :                 logger->log ("rejecting: unusable");
     511                 :        3276 :               return nullptr;
     512                 :             :             }
     513                 :       21731 :         }
     514                 :             : 
     515                 :       18075 :       if (succs.size () != 1)
     516                 :             :         {
     517                 :         555 :           if (logger)
     518                 :           0 :             logger->log ("rejecting: %i feasible successors",
     519                 :           0 :                          (int)succs.size ());
     520                 :         555 :           return nullptr;
     521                 :             :         }
     522                 :       17520 :       const feasibility_state &next_state = succs[0].first;
     523                 :       17520 :       const exploded_edge *out_eedge = succs[0].second;
     524                 :       17520 :       if (out_eedge->could_do_work_p ())
     525                 :             :         {
     526                 :        1042 :           if (logger)
     527                 :           3 :             logger->log ("rejecting: edge could do work");
     528                 :        1042 :           return nullptr;
     529                 :             :         }
     530                 :       16478 :       if (fg)
     531                 :             :         {
     532                 :           0 :           feasible_node *next_fnode = fg->add_node (out_eedge->m_dest,
     533                 :             :                                                     next_state,
     534                 :           0 :                                                     fg->m_nodes.length ());
     535                 :           0 :           fg->add_edge (new feasible_edge (curr_fnode, next_fnode, out_eedge));
     536                 :           0 :           curr_fnode = next_fnode;
     537                 :             :         }
     538                 :       16478 :       state = next_state;
     539                 :       16478 :       eedges.push_back (out_eedge);
     540                 :       16478 :       if (first_loc == UNKNOWN_LOCATION)
     541                 :             :         {
     542                 :          36 :           if (out_eedge->m_sedge)
     543                 :           6 :             if (::edge cfg_edge = out_eedge->m_sedge->get_any_cfg_edge ())
     544                 :           6 :               if (cfg_edge->goto_locus > BUILTINS_LOCATION)
     545                 :           0 :                 first_loc = cfg_edge->goto_locus;
     546                 :             :         }
     547                 :       16478 :       iter = out_eedge->m_dest;
     548                 :       21351 :     }
     549                 :      358035 : }
     550                 :             : 
     551                 :             : /* Implementation of -Wanalyzer-infinite-loop.  */
     552                 :             : 
     553                 :             : void
     554                 :        3197 : exploded_graph::detect_infinite_loops ()
     555                 :             : {
     556                 :        3197 :   LOG_FUNC (get_logger ());
     557                 :        3197 :   auto_timevar tv (TV_ANALYZER_INFINITE_LOOPS);
     558                 :             : 
     559                 :             :   /* Track all enodes we've warned for; both the loop entrypoints
     560                 :             :      and all the enodes within those loops.  */
     561                 :        3197 :   hash_set<const exploded_node *> warned_for;
     562                 :             : 
     563                 :      367680 :   for (auto enode : m_nodes)
     564                 :             :     {
     565                 :      358097 :       if (get_logger ())
     566                 :         230 :         get_logger ()->log ("visited: %i out of %i",
     567                 :         115 :                             (int)warned_for.elements (), m_nodes.length ());
     568                 :             : 
     569                 :             :       /* Only warn about the first enode we encounter in each cycle.  */
     570                 :      358097 :       if (warned_for.contains(enode))
     571                 :          62 :         continue;
     572                 :             : 
     573                 :      358035 :       if (std::unique_ptr<infinite_loop> inf_loop
     574                 :      358035 :             = starts_infinite_loop_p (*enode, *this, get_logger ()))
     575                 :             :         {
     576                 :          88 :           const supernode *snode = enode->get_supernode ();
     577                 :             : 
     578                 :          88 :           if (get_logger ())
     579                 :           0 :             get_logger ()->log ("EN: %i from starts_infinite_loop_p",
     580                 :           0 :                                 enode->m_index);
     581                 :             : 
     582                 :         622 :           for (auto iter : inf_loop->m_eedge_vec)
     583                 :         534 :             warned_for.add (iter->m_src);
     584                 :          88 :           gcc_assert (warned_for.contains(enode));
     585                 :             : 
     586                 :          88 :           if (inf_loop->m_loc == UNKNOWN_LOCATION)
     587                 :             :             {
     588                 :           0 :               if (get_logger ())
     589                 :           0 :                 get_logger ()->log
     590                 :           0 :                   ("no location available for reporting infinite loop");
     591                 :           0 :               continue;
     592                 :             :             }
     593                 :             : 
     594                 :          88 :           pending_location ploc (enode, snode, inf_loop->m_loc);
     595                 :          88 :           auto d
     596                 :          88 :             = ::make_unique<infinite_loop_diagnostic> (std::move (inf_loop));
     597                 :          88 :           get_diagnostic_manager ().add_diagnostic (ploc, std::move (d));
     598                 :      358123 :         }
     599                 :             :     }
     600                 :        3197 : }
        

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.