LCOV - code coverage report
Current view: top level - gcc/analyzer - infinite-recursion.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 92.6 % 231 214
Test Date: 2026-11-14 16:39:50 Functions: 95.7 % 23 22
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Detection of infinite recursion.
       2              :    Copyright (C) 2022-2026 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 "analyzer/common.h"
      22              : 
      23              : #include "cfg.h"
      24              : #include "gimple-iterator.h"
      25              : #include "gimple-pretty-print.h"
      26              : #include "cgraph.h"
      27              : #include "digraph.h"
      28              : #include "diagnostics/sarif-sink.h"
      29              : 
      30              : #include "analyzer/analyzer-logging.h"
      31              : #include "analyzer/call-string.h"
      32              : #include "analyzer/program-point.h"
      33              : #include "analyzer/store.h"
      34              : #include "analyzer/region-model.h"
      35              : #include "analyzer/constraint-manager.h"
      36              : #include "analyzer/sm.h"
      37              : #include "analyzer/pending-diagnostic.h"
      38              : #include "analyzer/diagnostic-manager.h"
      39              : #include "analyzer/supergraph.h"
      40              : #include "analyzer/program-state.h"
      41              : #include "analyzer/exploded-graph.h"
      42              : #include "analyzer/checker-path.h"
      43              : #include "analyzer/feasible-graph.h"
      44              : 
      45              : /* A subclass of pending_diagnostic for complaining about suspected
      46              :    infinite recursion.  */
      47              : 
      48              : class infinite_recursion_diagnostic
      49              : : public pending_diagnostic_subclass<infinite_recursion_diagnostic>
      50              : {
      51              : public:
      52          481 :   infinite_recursion_diagnostic (const exploded_node *prev_entry_enode,
      53              :                                  const exploded_node *new_entry_enode,
      54              :                                  tree callee_fndecl)
      55          481 :   : m_prev_entry_enode (prev_entry_enode),
      56          481 :     m_new_entry_enode (new_entry_enode),
      57          481 :     m_callee_fndecl (callee_fndecl),
      58          481 :     m_prev_entry_event (nullptr)
      59              :   {}
      60              : 
      61         2770 :   const char *get_kind () const final override
      62              :   {
      63         2770 :     return "infinite_recursion_diagnostic";
      64              :   }
      65              : 
      66          412 :   bool operator== (const infinite_recursion_diagnostic &other) const
      67              :   {
      68          412 :     return m_callee_fndecl == other.m_callee_fndecl;
      69              :   }
      70              : 
      71          628 :   int get_controlling_option () const final override
      72              :   {
      73          628 :     return OPT_Wanalyzer_infinite_recursion;
      74              :   }
      75              : 
      76          147 :   bool emit (diagnostic_emission_context &ctxt) final override
      77              :   {
      78              :     /* "CWE-674: Uncontrolled Recursion".  */
      79          147 :     ctxt.add_cwe (674);
      80          147 :     return ctxt.warn ("infinite recursion");
      81              :   }
      82              : 
      83              :   bool
      84          294 :   describe_final_event (pretty_printer &pp,
      85              :                         const evdesc::final_event &) final override
      86              :   {
      87          294 :     const int frames_consumed = (m_new_entry_enode->get_stack_depth ()
      88          294 :                                  - m_prev_entry_enode->get_stack_depth ());
      89          294 :     if (frames_consumed > 1)
      90           64 :       pp_printf (&pp,
      91              :                  "apparently infinite chain of mutually-recursive function"
      92              :                  " calls, consuming %i stack frames per recursion",
      93              :                  frames_consumed);
      94              :     else
      95          230 :       pp_string (&pp, "apparently infinite recursion");
      96          294 :     return true;
      97              :   }
      98              : 
      99              :   void
     100          385 :   add_function_entry_event (const exploded_edge &eedge,
     101              :                             checker_path *emission_path,
     102              :                             const state_transition_at_call *state_trans) final override
     103              :   {
     104              :     /* Subclass of function_entry_event for use when reporting both
     105              :        the initial and subsequent entries to the function of interest,
     106              :        allowing for cross-referencing the first event in the description
     107              :        of the second.  */
     108            0 :     class recursive_function_entry_event : public function_entry_event
     109              :     {
     110              :     public:
     111          294 :       recursive_function_entry_event (const program_point &dst_point,
     112              :                                       const program_state &dst_state,
     113              :                                       const infinite_recursion_diagnostic &pd,
     114              :                                       bool topmost)
     115          294 :       : function_entry_event (event_loc_info (dst_point),
     116              :                               dst_state,
     117              :                               nullptr),
     118          294 :         m_pd (pd),
     119          294 :         m_topmost (topmost)
     120              :       {
     121          294 :       }
     122              : 
     123              :       void
     124          588 :       print_desc (pretty_printer &pp) const final override
     125              :       {
     126          588 :         if (m_topmost)
     127              :           {
     128          294 :             if (m_pd.m_prev_entry_event
     129          294 :                 && m_pd.m_prev_entry_event->get_id_ptr ()->known_p ())
     130          294 :               pp_printf (&pp,
     131              :                          "recursive entry to %qE; previously entered at %@",
     132          294 :                          m_effective_fndecl,
     133          294 :                          m_pd.m_prev_entry_event->get_id_ptr ());
     134              :             else
     135            0 :               pp_printf (&pp,
     136              :                          "recursive entry to %qE",
     137            0 :                          m_effective_fndecl);
     138              :           }
     139              :         else
     140          294 :           pp_printf (&pp,
     141              :                      "initial entry to %qE",
     142          294 :                      m_effective_fndecl);
     143          588 :       }
     144              : 
     145              :     private:
     146              :       const infinite_recursion_diagnostic &m_pd;
     147              :       bool m_topmost;
     148              :     };
     149          385 :     const exploded_node *dst_node = eedge.m_dest;
     150          385 :     const program_point &dst_point = dst_node->get_point ();
     151          385 :     if (eedge.m_dest == m_prev_entry_enode)
     152              :       {
     153          147 :         gcc_assert (m_prev_entry_event == nullptr);
     154          147 :         std::unique_ptr<checker_event> prev_entry_event
     155              :           = std::make_unique <recursive_function_entry_event>
     156          147 :               (dst_point,
     157              :                dst_node->get_state (),
     158          147 :                *this, false);
     159          147 :         m_prev_entry_event = prev_entry_event.get ();
     160          147 :         emission_path->add_event (std::move (prev_entry_event));
     161          147 :       }
     162          238 :     else if (eedge.m_dest == m_new_entry_enode)
     163          147 :       emission_path->add_event
     164          147 :         (std::make_unique<recursive_function_entry_event>
     165          147 :          (dst_point, dst_node->get_state (), *this, true));
     166              :     else
     167           91 :       pending_diagnostic::add_function_entry_event (eedge, emission_path,
     168              :                                                     state_trans);
     169          385 :   }
     170              : 
     171              :   /* Customize the location where the warning_event appears, putting
     172              :      it at the topmost entrypoint to the function.  */
     173          147 :   void add_final_event (const state_machine *,
     174              :                         const exploded_node *enode,
     175              :                         const event_loc_info &,
     176              :                         tree,
     177              :                         state_machine::state_t,
     178              :                         checker_path *emission_path) final override
     179              :   {
     180          147 :     gcc_assert (m_new_entry_enode);
     181          147 :     emission_path->add_event
     182          147 :       (std::make_unique<warning_event>
     183          147 :        (event_loc_info (m_new_entry_enode->get_supernode
     184              :                           ()->get_location (),
     185              :                         m_callee_fndecl,
     186          147 :                         m_new_entry_enode->get_stack_depth ()),
     187              :         enode,
     188          147 :         nullptr, nullptr, nullptr));
     189          147 :   }
     190              : 
     191              :   /* Reject paths in which conjured svalues have affected control flow
     192              :      since m_prev_entry_enode.  */
     193              : 
     194          473 :   bool check_valid_fpath_p (const feasible_node &final_fnode)
     195              :     const final override
     196              :   {
     197              :     /* Reject paths in which calls with unknown side effects have occurred
     198              :        since m_prev_entry_enode.
     199              :        Find num calls with side effects.  Walk backward until we reach the
     200              :        pref */
     201          473 :     gcc_assert (final_fnode.get_inner_node () == m_new_entry_enode);
     202              : 
     203              :     /* FG is actually a tree.  Walk backwards from FINAL_FNODE until we
     204              :        reach the prev_entry_enode (or the origin).  */
     205              :     const feasible_node *iter_fnode = &final_fnode;
     206         2677 :     while (iter_fnode->get_inner_node ()->m_index != 0)
     207              :       {
     208         2677 :         gcc_assert (iter_fnode->m_preds.length () == 1);
     209              : 
     210         2677 :         feasible_edge *pred_fedge
     211         2677 :           = static_cast <feasible_edge *> (iter_fnode->m_preds[0]);
     212              : 
     213              :         /* Determine if conjured svalues have affected control flow
     214              :            since the prev entry node.  */
     215         2677 :         if (fedge_uses_conjured_value_p (pred_fedge))
     216              :           /* If so, then reject this diagnostic.  */
     217              :           return false;
     218         2616 :         iter_fnode = static_cast <feasible_node *> (pred_fedge->m_src);
     219         2616 :         if (iter_fnode->get_inner_node () == m_prev_entry_enode)
     220              :           /* Accept this diagnostic.  */
     221              :           return true;
     222              :     }
     223              : 
     224              :     /* We shouldn't get here; if we do, reject the diagnostic.  */
     225            0 :     gcc_unreachable ();
     226              :     return false;
     227              :   }
     228              : 
     229              :   void
     230            0 :   maybe_add_sarif_properties (diagnostics::sarif_object &result_obj)
     231              :     const final override
     232              :   {
     233            0 :     auto &props = result_obj.get_or_create_properties ();
     234              : #define PROPERTY_PREFIX "gcc/analyzer/infinite_recursion_diagnostic/"
     235            0 :     props.set_integer (PROPERTY_PREFIX "prev_entry_enode",
     236            0 :                        m_prev_entry_enode->m_index);
     237            0 :     props.set_integer (PROPERTY_PREFIX "new_entry_enode",
     238            0 :                        m_new_entry_enode->m_index);
     239              : #undef PROPERTY_PREFIX
     240            0 :   }
     241              : 
     242              : private:
     243              :   /* Return true iff control flow along FEDGE was affected by
     244              :      a conjured_svalue.  */
     245         2677 :   static bool fedge_uses_conjured_value_p (feasible_edge *fedge)
     246              :   {
     247         2677 :     const exploded_edge *eedge = fedge->get_inner_edge ();
     248         2677 :     const superedge *sedge = eedge->m_sedge;
     249         2677 :     if (!sedge)
     250              :       return false;
     251         2677 :     auto op = sedge->get_op ();
     252         2677 :     if (!op)
     253              :       return false;
     254         1875 :     const control_flow_op *ctrlflow_op = op->dyn_cast_control_flow_op ();
     255         1875 :     if (!ctrlflow_op)
     256              :       return false;
     257              : 
     258          485 :     const gimple &last_stmt = ctrlflow_op->get_ctrlflow_stmt ();
     259              : 
     260          485 :     const feasible_node *dst_fnode
     261              :       = static_cast<const feasible_node *> (fedge->m_dest);
     262          485 :     const region_model &model = dst_fnode->get_state ().get_model ();
     263              : 
     264          485 :     if (const gcond *cond_stmt = dyn_cast <const gcond *> (&last_stmt))
     265              :       {
     266          443 :         if (expr_uses_conjured_value_p (model, gimple_cond_lhs (cond_stmt)))
     267              :           return true;
     268          412 :         if (expr_uses_conjured_value_p (model, gimple_cond_rhs (cond_stmt)))
     269              :           return true;
     270              :       }
     271           42 :     else if (const gswitch *switch_stmt
     272         2719 :                = dyn_cast <const gswitch *> (&last_stmt))
     273              :       {
     274           42 :         if (expr_uses_conjured_value_p (model,
     275              :                                         gimple_switch_index (switch_stmt)))
     276              :           return true;
     277              :       }
     278              :     return false;
     279              :   }
     280              : 
     281              :   /* Return true iff EXPR is affected by a conjured_svalue.  */
     282          897 :   static bool expr_uses_conjured_value_p (const region_model &model,
     283              :                                           tree expr)
     284              :   {
     285         1794 :     class conjured_bit_vector_finder : public symbolic::node_visitor
     286              :     {
     287              :     public:
     288          897 :       conjured_bit_vector_finder () : m_found_conjured_svalues (false)
     289              :       {
     290              :       }
     291              : 
     292              :       bool
     293          142 :       visit_bit_vector (const symbolic::bit_vector &bv) final override
     294              :       {
     295          142 :         if (!node_visitor::visit_bit_vector (bv))
     296              :           return false;
     297          142 :         if (bv.dyn_cast_conjured_bit_vector ())
     298           65 :           m_found_conjured_svalues = true;
     299              :         return true;
     300              :       }
     301              : 
     302              :       bool m_found_conjured_svalues;
     303              :     };
     304              : 
     305          897 :     const svalue *sval = model.get_rvalue (expr, nullptr);
     306          897 :     conjured_bit_vector_finder v;
     307          897 :     sval->accept_node_visitor (v);
     308          897 :     return v.m_found_conjured_svalues;
     309          897 :   }
     310              : 
     311              :   const exploded_node *m_prev_entry_enode;
     312              :   const exploded_node *m_new_entry_enode;
     313              :   tree m_callee_fndecl;
     314              :   const checker_event *m_prev_entry_event;
     315              : };
     316              : 
     317              : /* Return true iff ENODE is at a function entrypoint.  */
     318              : 
     319              : static bool
     320       278582 : is_entrypoint_p (exploded_node *enode)
     321              : {
     322              :   /* Look for an entrypoint to a function...  */
     323            0 :   const supernode *snode = enode->get_supernode ();
     324       278582 :   if (!snode)
     325              :     return false;
     326       278582 :   return snode->entry_p ();
     327              : }
     328              : 
     329              : /* Walk backwards through the eg, looking for the first
     330              :    enode we find that's also the entrypoint of the same function.  */
     331              : 
     332              : exploded_node *
     333         1176 : exploded_graph::find_previous_entry_to (function *top_of_stack_fun,
     334              :                                         exploded_node *enode) const
     335              : {
     336         1176 :   auto_vec<exploded_node *> worklist;
     337         1176 :   hash_set<exploded_node *> visited;
     338              : 
     339         1176 :   visited.add (enode);
     340         4704 :   for (auto in_edge : enode->m_preds)
     341         1176 :     worklist.safe_push (in_edge->m_src);
     342              : 
     343        14393 :   while (worklist.length () > 0)
     344              :     {
     345        13217 :       exploded_node *iter = worklist.pop ();
     346              : 
     347        13217 :       if (is_entrypoint_p (iter)
     348        13217 :           && iter->get_function () == top_of_stack_fun)
     349         1176 :         return iter;
     350              : 
     351        12041 :       if (visited.contains (iter))
     352           28 :         continue;
     353        12013 :       visited.add (iter);
     354        48286 :       for (auto in_edge : iter->m_preds)
     355        12247 :         worklist.safe_push (in_edge->m_src);
     356              :     }
     357              : 
     358              :   /* Not found.  */
     359              :   return nullptr;
     360         1176 : }
     361              : 
     362              : /* Given BASE_REG within ENCLOSING_FRAME (such as a function parameter),
     363              :    remap it to the equivalent region within EQUIV_PREV_FRAME.
     364              : 
     365              :    For example, given param "n" within frame "foo@3", and equiv prev frame
     366              :    "foo@1", remap it to param "n" within frame "foo@1".  */
     367              : 
     368              : static const region *
     369          988 : remap_enclosing_frame (const region *base_reg,
     370              :                        const frame_region *enclosing_frame,
     371              :                        const frame_region *equiv_prev_frame,
     372              :                        region_model_manager *mgr)
     373              : {
     374          988 :   gcc_assert (base_reg->get_parent_region () == enclosing_frame);
     375          988 :   switch (base_reg->get_kind ())
     376              :     {
     377            0 :     default:
     378              :       /* We should only encounter params and varargs at the topmost
     379              :          entrypoint.  */
     380            0 :       gcc_unreachable ();
     381              : 
     382           18 :     case RK_VAR_ARG:
     383           18 :       {
     384           18 :         const var_arg_region *var_arg_reg = (const var_arg_region *)base_reg;
     385           18 :         return mgr->get_var_arg_region (equiv_prev_frame,
     386           18 :                                         var_arg_reg->get_index ());
     387              :       }
     388          970 :     case RK_DECL:
     389          970 :       {
     390          970 :         const decl_region *decl_reg = (const decl_region *)base_reg;
     391          970 :         return equiv_prev_frame->get_region_for_local (mgr,
     392              :                                                        decl_reg->get_decl (),
     393          970 :                                                        nullptr);
     394              :       }
     395              :     }
     396              : }
     397              : 
     398              : /* Return true iff NODE is unknown, or contains an unknown value.  */
     399              : 
     400              : static bool
     401         6649 : contains_unknown_p (const symbolic::node &node)
     402              : {
     403        13298 :   struct unknown_finder : public symbolic::node_visitor
     404              :   {
     405         6649 :     unknown_finder ()
     406         6649 :     : m_found_unknown (false)
     407              :     {
     408              :     }
     409              : 
     410              :     bool
     411         8716 :     visit_svalue (const svalue &sval) final override
     412              :     {
     413         8716 :       if (!symbolic::node_visitor::visit_svalue (sval))
     414              :         return false;
     415         8716 :       if (sval.get_kind () == SK_UNKNOWN)
     416            0 :         m_found_unknown = true;
     417              :       return true;
     418              :     }
     419              : 
     420              :     bool
     421         6145 :     visit_bit_vector (const symbolic::bit_vector &bv) final override
     422              :     {
     423         6145 :       if (!symbolic::node_visitor::visit_bit_vector (bv))
     424              :         return false;
     425         6145 :       if (auto *tristate_bv = bv.dyn_cast_tristate_bit_vector ())
     426          307 :         if (tristate_bv->get_bit_value () == tristate::unknown ())
     427           88 :           m_found_unknown = true;
     428              :       return true;
     429              :     }
     430              : 
     431              :     bool
     432        13029 :     visit_bit_contents (const symbolic::bit_contents &bc) final override
     433              :     {
     434        13029 :       if (!symbolic::node_visitor::visit_bit_contents (bc))
     435              :         return false;
     436        13029 :       if (bc.get_kind () == symbolic::bit_contents::kind::untracked)
     437           34 :         m_found_unknown = true;
     438              :       return true;
     439              :     }
     440              : 
     441              :     bool m_found_unknown;
     442         6649 :   } v;
     443              : 
     444         6649 :   node.accept_node_visitor (v);
     445         6649 :   return v.m_found_unknown;
     446         6649 : }
     447              : 
     448              : /* Subroutine of sufficiently_different_p.  Compare the store bindings
     449              :    for BASE_REG within NEW_ENTRY_ENODE and PREV_ENTRY_ENODE.
     450              : 
     451              :    Return true if the state of NEW_ENTRY_ENODE is sufficiently different
     452              :    from PREV_ENTRY_ENODE within BASE_REG to suggest that some variant is
     453              :    being modified, and thus the recursion isn't infinite.
     454              : 
     455              :    Return false if the states for BASE_REG are effectively the same.  */
     456              : 
     457              : static bool
     458         4085 : sufficiently_different_region_binding_p (exploded_node *new_entry_enode,
     459              :                                          exploded_node *prev_entry_enode,
     460              :                                          const region *base_reg)
     461              : {
     462              :   /* Compare the stores of the two enodes.  */
     463         4085 :   const region_model &new_model
     464         4085 :     = *new_entry_enode->get_state ().m_region_model;
     465         4085 :   const region_model &prev_model
     466         4085 :     = *prev_entry_enode->get_state ().m_region_model;
     467              : 
     468              :   /* Get the contents of BASE_REG within the new frame.  */
     469         4085 :   const symbolic::bit_contents &new_contents
     470         4085 :     = new_model.get_bit_contents (*base_reg);
     471              : 
     472              :   /* If any part of the contents is UNKNOWN (e.g. due to hitting
     473              :      complexity limits) assume that it differs from the previous
     474              :      value.  */
     475         4085 :   if (contains_unknown_p (new_contents))
     476              :     return true;
     477              : 
     478              :   /* Get the equivalent contents within the old enode.  */
     479         3963 :   const symbolic::bit_contents *prev_contents;
     480              : 
     481         7926 :   if (const frame_region *enclosing_frame
     482         3963 :       = base_reg->maybe_get_frame_region ())
     483              :     {
     484              :       /* We have a binding within a frame in the new entry enode.  */
     485              : 
     486              :       /* Consider changes in bindings below the original entry
     487              :          to the recursion.  */
     488         3581 :       const int old_stack_depth = prev_entry_enode->get_stack_depth ();
     489         3581 :       if (enclosing_frame->get_stack_depth () < old_stack_depth)
     490         1194 :         prev_contents = &prev_model.get_bit_contents (*base_reg);
     491              :       else
     492              :         {
     493              :           /* Ignore bindings within frames below the new entry node.  */
     494         2387 :           const int new_stack_depth = new_entry_enode->get_stack_depth ();
     495         2387 :           if (enclosing_frame->get_stack_depth () < new_stack_depth)
     496              :             return false;
     497              : 
     498              :           /* We have a binding within the frame of the new entry node,
     499              :              presumably a parameter.  */
     500              : 
     501              :           /* Get the value within the equivalent frame of
     502              :              the old entrypoint; typically will be the initial_svalue
     503              :              of the parameter.  */
     504          988 :           const frame_region *equiv_prev_frame
     505          988 :             = prev_model.get_current_frame ();
     506          988 :           const region *equiv_prev_base_reg
     507          988 :             = remap_enclosing_frame (base_reg,
     508              :                                      enclosing_frame,
     509              :                                      equiv_prev_frame,
     510              :                                      new_model.get_manager ());
     511          988 :           prev_contents = &prev_model.get_bit_contents (*equiv_prev_base_reg);
     512              :         }
     513              :     }
     514              :   else
     515          382 :     prev_contents = &prev_model.get_bit_contents (*base_reg);
     516              : 
     517              : 
     518              :   /* If the prev_sval contains UNKNOWN (e.g. due to hitting complexity limits)
     519              :      assume that it will differ from any new value.  */
     520         2564 :   if (contains_unknown_p (*prev_contents))
     521              :     return true;
     522              : 
     523         2564 :   if (&new_contents != prev_contents)
     524          573 :     return true;
     525              : 
     526              :   return false;
     527              : }
     528              : 
     529              : /* Compare the state of memory at NEW_ENTRY_ENODE and PREV_ENTRY_ENODE,
     530              :    both of which are entrypoints to the same function, where recursion has
     531              :    occurred.
     532              : 
     533              :    Return true if the state of NEW_ENTRY_ENODE is sufficiently different
     534              :    from PREV_ENTRY_ENODE to suggest that some variant is being modified,
     535              :    and thus the recursion isn't infinite.
     536              : 
     537              :    Return false if the states are effectively the same, suggesting that
     538              :    the recursion is infinite.
     539              : 
     540              :    For example, consider mutually recursive functions "foo" and "bar".
     541              :    At the entrypoint to a "foo" frame where we've detected recursion,
     542              :    we might have three frames on the stack: the new 'foo'@3, an inner
     543              :    'bar'@2, and the innermost 'foo'@1.
     544              : 
     545              :      (gdb) call enode->dump(m_ext_state)
     546              :      EN: 16
     547              :      callstring: [(SN: 9 -> SN: 3 in foo), (SN: 5 -> SN: 8 in bar)]
     548              :      before SN: 0 (NULL from-edge)
     549              : 
     550              :      rmodel:
     551              :      stack depth: 3
     552              :        frame (index 2): frame: ‘foo’@3
     553              :        frame (index 1): frame: ‘bar’@2
     554              :        frame (index 0): frame: ‘foo’@1
     555              :      clusters within root region
     556              :        cluster for: (*INIT_VAL(f_4(D)))
     557              :      clusters within frame: ‘bar’@2
     558              :        cluster for: b_2(D): INIT_VAL(f_4(D))
     559              :      clusters within frame: ‘foo’@3
     560              :        cluster for: f_4(D): INIT_VAL(f_4(D))
     561              :      m_called_unknown_fn: FALSE
     562              : 
     563              :    whereas for the previous entry node we'd have just the innermost
     564              :    'foo'@1
     565              : 
     566              :      (gdb) call prev_entry_enode->dump(m_ext_state)
     567              :      EN: 1
     568              :      callstring: []
     569              :      before SN: 0 (NULL from-edge)
     570              : 
     571              :      rmodel:
     572              :      stack depth: 1
     573              :        frame (index 0): frame: ‘foo’@1
     574              :      clusters within root region
     575              :        cluster for: (*INIT_VAL(f_4(D)))
     576              :      m_called_unknown_fn: FALSE
     577              : 
     578              :    We want to abstract away frames 1 and 2 in the new entry enode,
     579              :    and compare its frame 3 with the frame 1 in the previous entry
     580              :    enode, and determine if enough state changes between them to
     581              :    rule out infinite recursion.  */
     582              : 
     583              : static bool
     584         1176 : sufficiently_different_p (exploded_node *new_entry_enode,
     585              :                           exploded_node *prev_entry_enode,
     586              :                           logger *logger)
     587              : {
     588         1176 :   LOG_SCOPE (logger);
     589         1176 :   gcc_assert (new_entry_enode);
     590         1176 :   gcc_assert (prev_entry_enode);
     591         1176 :   gcc_assert (is_entrypoint_p (new_entry_enode));
     592         1176 :   gcc_assert (is_entrypoint_p (prev_entry_enode));
     593              : 
     594              :   /* Compare the stores of the two enodes.  */
     595         1176 :   const region_model &new_model
     596         1176 :     = *new_entry_enode->get_state ().m_region_model;
     597         1176 :   const store &new_store = *new_model.get_store ();
     598              : 
     599         4566 :   for (auto kv : new_store)
     600              :     {
     601         4085 :       const region *base_reg = kv.first;
     602         4085 :       if (sufficiently_different_region_binding_p (new_entry_enode,
     603              :                                                    prev_entry_enode,
     604              :                                                    base_reg))
     605          695 :         return true;
     606              :     }
     607              : 
     608              :   /* No significant differences found.  */
     609          481 :   return false;
     610         1176 : }
     611              : 
     612              : /* Implementation of -Wanalyzer-infinite-recursion.
     613              : 
     614              :    Called when adding ENODE to the graph, after adding its first in-edge.
     615              : 
     616              :    For function entrypoints, see if recursion has occurred, and, if so,
     617              :    check if the state of memory changed between the recursion levels,
     618              :    which would suggest some kind of decreasing variant that leads to
     619              :    termination.
     620              : 
     621              :    For recursive calls where the state of memory is effectively unchanged
     622              :    between recursion levels, warn with -Wanalyzer-infinite-recursion.  */
     623              : 
     624              : void
     625       263013 : exploded_graph::detect_infinite_recursion (exploded_node *enode)
     626              : {
     627       263013 :   if (!is_entrypoint_p (enode))
     628       262532 :     return;
     629         8987 :   function *top_of_stack_fun = enode->get_function ();
     630         8987 :   gcc_assert (top_of_stack_fun);
     631              : 
     632              :   /* ....where a call to that function is already in the call string.  */
     633         8987 :   const call_string &call_string = enode->get_point ().get_call_string ();
     634              : 
     635         8987 :   if (call_string.count_occurrences_of_function (top_of_stack_fun) < 2)
     636              :     return;
     637              : 
     638         1176 :   tree fndecl = top_of_stack_fun->decl;
     639              : 
     640         1176 :   log_scope s (get_logger (),
     641              :                "checking for infinite recursion",
     642              :                "considering recursion at EN: %i entering %qE",
     643         1176 :                enode->m_index, fndecl);
     644              : 
     645              :   /* Find enode that's the entrypoint for the previous frame for fndecl
     646              :      in the recursion.  */
     647         1176 :   exploded_node *prev_entry_enode
     648         1176 :     = find_previous_entry_to (top_of_stack_fun, enode);
     649         1176 :   gcc_assert (prev_entry_enode);
     650         1176 :   if (get_logger ())
     651            0 :     get_logger ()->log ("previous entrypoint to %qE is EN: %i",
     652            0 :                         fndecl, prev_entry_enode->m_index);
     653              : 
     654              :   /* Look for changes to the state of memory between the recursion levels.  */
     655         1176 :   if (sufficiently_different_p (enode, prev_entry_enode, get_logger ()))
     656          695 :     return;
     657              : 
     658              :   /* Otherwise, the state of memory is effectively the same between the two
     659              :      recursion levels; warn.  */
     660          481 :   pending_location ploc (enode,
     661          481 :                          call_string.get_top_of_stack ().get_call_stmt ().location);
     662          481 :   get_diagnostic_manager ().add_diagnostic
     663          481 :     (std::move (ploc),
     664          481 :      std::make_unique<infinite_recursion_diagnostic> (prev_entry_enode,
     665              :                                                       enode,
     666              :                                                       fndecl));
     667         1176 : }
        

Generated by: LCOV version 2.5.0-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.