LCOV - code coverage report
Current view: top level - gcc/analyzer - infinite-recursion.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 93.2 % 219 204
Test Date: 2024-12-21 13:15:12 Functions: 94.7 % 19 18
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

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

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.