gcc/analyzer/infinite-recursion.cc

   1 /* Detection of infinite recursion.
   2    Copyright (C) 2022 Free Software Foundation, Inc.
   3    Contributed by David Malcolm <dmalcolm@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #define INCLUDE_MEMORY
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tree.h"
  26 #include "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 "diagnostic-metadata.h"
  35 #include "function.h"
  36 #include "pretty-print.h"
  37 #include "sbitmap.h"
  38 #include "bitmap.h"
  39 #include "tristate.h"
  40 #include "ordered-hash-map.h"
  41 #include "selftest.h"
  42 #include "json.h"
  43 #include "analyzer/analyzer.h"
  44 #include "analyzer/analyzer-logging.h"
  45 #include "analyzer/call-string.h"
  46 #include "analyzer/program-point.h"
  47 #include "analyzer/store.h"
  48 #include "analyzer/region-model.h"
  49 #include "analyzer/constraint-manager.h"
  50 #include "analyzer/sm.h"
  51 #include "analyzer/pending-diagnostic.h"
  52 #include "analyzer/diagnostic-manager.h"
  53 #include "cfg.h"
  54 #include "basic-block.h"
  55 #include "gimple.h"
  56 #include "gimple-iterator.h"
  57 #include "gimple-pretty-print.h"
  58 #include "cgraph.h"
  59 #include "digraph.h"
  60 #include "analyzer/supergraph.h"
  61 #include "analyzer/program-state.h"
  62 #include "analyzer/exploded-graph.h"
  63 #include "make-unique.h"
  64 #include "analyzer/checker-path.h"
  65
  66 /* A subclass of pending_diagnostic for complaining about suspected
  67    infinite recursion.  */
  68
  69 class infinite_recursion_diagnostic
  70 : public pending_diagnostic_subclass<infinite_recursion_diagnostic>
  71 {
  72 public:
  73   infinite_recursion_diagnostic (const exploded_node *prev_entry_enode,
  74                                  const exploded_node *new_entry_enode,
  75                                  tree callee_fndecl)
  76   : m_prev_entry_enode (prev_entry_enode),
  77     m_new_entry_enode (new_entry_enode),
  78     m_callee_fndecl (callee_fndecl),
  79     m_prev_entry_event (NULL)
  80   {}
  81
  82   const char *get_kind () const final override
  83   {
  84     return "infinite_recursion_diagnostic";
  85   }
  86
  87   bool operator== (const infinite_recursion_diagnostic &other) const
  88   {
  89     return m_callee_fndecl == other.m_callee_fndecl;
  90   }
  91
  92   int get_controlling_option () const final override
  93   {
  94     return OPT_Wanalyzer_infinite_recursion;
  95   }
  96
  97   bool emit (rich_location *rich_loc) final override
  98   {
  99     /* "CWE-674: Uncontrolled Recursion".  */
 100     diagnostic_metadata m;
 101     m.add_cwe (674);
 102     return warning_meta (rich_loc, m, get_controlling_option (),
 103                          "infinite recursion");
 104   }
 105
 106   label_text describe_final_event (const evdesc::final_event &ev) final override
 107   {
 108     const int frames_consumed = (m_new_entry_enode->get_stack_depth ()
 109                                  - m_prev_entry_enode->get_stack_depth ());
 110     if (frames_consumed > 1)
 111       return ev.formatted_print
 112         ("apparently infinite chain of mutually-recursive function calls,"
 113          " consuming %i stack frames per recursion",
 114          frames_consumed);
 115     else
 116       return ev.formatted_print ("apparently infinite recursion");
 117   }
 118
 119   void
 120   add_function_entry_event (const exploded_edge &eedge,
 121                             checker_path *emission_path) final override
 122   {
 123     /* Subclass of function_entry_event for use when reporting both
 124        the initial and subsequent entries to the function of interest,
 125        allowing for cross-referencing the first event in the description
 126        of the second.  */
 127     class recursive_function_entry_event : public function_entry_event
 128     {
 129     public:
 130       recursive_function_entry_event (const program_point &dst_point,
 131                                       const infinite_recursion_diagnostic &pd,
 132                                       bool topmost)
 133       : function_entry_event (dst_point),
 134         m_pd (pd),
 135         m_topmost (topmost)
 136       {
 137       }
 138
 139       label_text
 140       get_desc (bool can_colorize) const final override
 141       {
 142         if (m_topmost)
 143           {
 144             if (m_pd.m_prev_entry_event
 145                 && m_pd.m_prev_entry_event->get_id_ptr ()->known_p ())
 146               return make_label_text
 147                 (can_colorize,
 148                  "recursive entry to %qE; previously entered at %@",
 149                  m_effective_fndecl,
 150                  m_pd.m_prev_entry_event->get_id_ptr ());
 151             else
 152               return make_label_text (can_colorize, "recursive entry to %qE",
 153                                       m_effective_fndecl);
 154           }
 155         else
 156           return make_label_text (can_colorize, "initial entry to %qE",
 157                                   m_effective_fndecl);
 158       }
 159
 160     private:
 161       const infinite_recursion_diagnostic &m_pd;
 162       bool m_topmost;
 163     };
 164     const exploded_node *dst_node = eedge.m_dest;
 165     const program_point &dst_point = dst_node->get_point ();
 166     if (eedge.m_dest == m_prev_entry_enode)
 167       {
 168         gcc_assert (m_prev_entry_event == NULL);
 169         std::unique_ptr<checker_event> prev_entry_event
 170           = make_unique <recursive_function_entry_event> (dst_point,
 171                                                           *this, false);
 172         m_prev_entry_event = prev_entry_event.get ();
 173         emission_path->add_event (std::move (prev_entry_event));
 174       }
 175     else if (eedge.m_dest == m_new_entry_enode)
 176       emission_path->add_event
 177         (make_unique<recursive_function_entry_event> (dst_point, *this, true));
 178     else
 179       pending_diagnostic::add_function_entry_event (eedge, emission_path);
 180   }
 181
 182   /* Customize the location where the warning_event appears, putting
 183      it at the topmost entrypoint to the function.  */
 184   void add_final_event (const state_machine *,
 185                         const exploded_node *,
 186                         const gimple *,
 187                         tree,
 188                         state_machine::state_t,
 189                         checker_path *emission_path) final override
 190   {
 191     gcc_assert (m_new_entry_enode);
 192     emission_path->add_event
 193       (make_unique<warning_event>
 194        (event_loc_info (m_new_entry_enode->get_supernode
 195                           ()->get_start_location (),
 196                         m_callee_fndecl,
 197                         m_new_entry_enode->get_stack_depth ()),
 198         NULL, NULL, NULL));
 199   }
 200
 201 private:
 202   const exploded_node *m_prev_entry_enode;
 203   const exploded_node *m_new_entry_enode;
 204   tree m_callee_fndecl;
 205   const checker_event *m_prev_entry_event;
 206 };
 207
 208 /* Return true iff ENODE is the PK_BEFORE_SUPERNODE at a function
 209    entrypoint.  */
 210
 211 static bool
 212 is_entrypoint_p (exploded_node *enode)
 213 {
 214   /* Look for an entrypoint to a function...  */
 215   const supernode *snode = enode->get_supernode ();
 216   if (!snode)
 217     return false;
 218   if (!snode->entry_p ())
 219     return false;;
 220   const program_point &point = enode->get_point ();
 221   if (point.get_kind () != PK_BEFORE_SUPERNODE)
 222     return false;
 223   return true;
 224 }
 225
 226 /* Walk backwards through the eg, looking for the first
 227    enode we find that's also the entrypoint of the same function.  */
 228
 229 exploded_node *
 230 exploded_graph::find_previous_entry_to (function *top_of_stack_fun,
 231                                         exploded_node *enode) const
 232 {
 233   auto_vec<exploded_node *> worklist;
 234   hash_set<exploded_node *> visited;
 235
 236   visited.add (enode);
 237   for (auto in_edge : enode->m_preds)
 238     worklist.safe_push (in_edge->m_src);
 239
 240   while (worklist.length () > 0)
 241     {
 242       exploded_node *iter = worklist.pop ();
 243
 244       if (is_entrypoint_p (iter)
 245           && iter->get_function () == top_of_stack_fun)
 246         return iter;
 247
 248       if (visited.contains (iter))
 249         continue;
 250       visited.add (iter);
 251       for (auto in_edge : iter->m_preds)
 252         worklist.safe_push (in_edge->m_src);
 253     }
 254
 255   /* Not found.  */
 256   return NULL;
 257 }
 258
 259 /* Given BASE_REG within ENCLOSING_FRAME (such as a function parameter),
 260    remap it to the equivalent region within EQUIV_PREV_FRAME.
 261
 262    For example, given param "n" within frame "foo@3", and equiv prev frame
 263    "foo@1", remap it to param "n" within frame "foo@1".  */
 264
 265 static const region *
 266 remap_enclosing_frame (const region *base_reg,
 267                        const frame_region *enclosing_frame,
 268                        const frame_region *equiv_prev_frame,
 269                        region_model_manager *mgr)
 270 {
 271   gcc_assert (base_reg->get_parent_region () == enclosing_frame);
 272   switch (base_reg->get_kind ())
 273     {
 274     default:
 275       /* We should only encounter params and varargs at the topmost
 276          entrypoint.  */
 277       gcc_unreachable ();
 278
 279     case RK_VAR_ARG:
 280       {
 281         const var_arg_region *var_arg_reg = (const var_arg_region *)base_reg;
 282         return mgr->get_var_arg_region (equiv_prev_frame,
 283                                         var_arg_reg->get_index ());
 284       }
 285     case RK_DECL:
 286       {
 287         const decl_region *decl_reg = (const decl_region *)base_reg;
 288         return equiv_prev_frame->get_region_for_local (mgr,
 289                                                        decl_reg->get_decl (),
 290                                                        NULL);
 291       }
 292     }
 293 }
 294
 295 /* Compare the state of memory at NEW_ENTRY_ENODE and PREV_ENTRY_ENODE,
 296    both of which are entrypoints to the same function, where recursion has
 297    occurred.
 298
 299    Return true if the state of NEW_ENTRY_ENODE is sufficiently different
 300    from PREV_ENTRY_ENODE to suggests that some variant is being modified,
 301    and thus the recursion isn't infinite.
 302
 303    Return false if the states are effectively the same, suggesting that
 304    the recursion is infinite.
 305
 306    For example, consider mutually recursive functions "foo" and "bar".
 307    At the entrypoint to a "foo" frame where we've detected recursion,
 308    we might have three frames on the stack: the new 'foo'@3, an inner
 309    'bar'@2, and the innermost 'foo'@1.
 310
 311      (gdb) call enode->dump(m_ext_state)
 312      EN: 16
 313      callstring: [(SN: 9 -> SN: 3 in foo), (SN: 5 -> SN: 8 in bar)]
 314      before SN: 0 (NULL from-edge)
 315
 316      rmodel:
 317      stack depth: 3
 318        frame (index 2): frame: ‘foo’@3
 319        frame (index 1): frame: ‘bar’@2
 320        frame (index 0): frame: ‘foo’@1
 321      clusters within root region
 322        cluster for: (*INIT_VAL(f_4(D)))
 323      clusters within frame: ‘bar’@2
 324        cluster for: b_2(D): INIT_VAL(f_4(D))
 325      clusters within frame: ‘foo’@3
 326        cluster for: f_4(D): INIT_VAL(f_4(D))
 327      m_called_unknown_fn: FALSE
 328
 329    whereas for the previous entry node we'd have just the innermost
 330    'foo'@1
 331
 332      (gdb) call prev_entry_enode->dump(m_ext_state)
 333      EN: 1
 334      callstring: []
 335      before SN: 0 (NULL from-edge)
 336
 337      rmodel:
 338      stack depth: 1
 339        frame (index 0): frame: ‘foo’@1
 340      clusters within root region
 341        cluster for: (*INIT_VAL(f_4(D)))
 342      m_called_unknown_fn: FALSE
 343
 344    We want to abstract away frames 1 and 2 in the new entry enode,
 345    and compare its frame 3 with the frame 1 in the previous entry
 346    enode, and determine if enough state changes between them to
 347    rule out infinite recursion.  */
 348
 349 static bool
 350 sufficiently_different_p (exploded_node *new_entry_enode,
 351                           exploded_node *prev_entry_enode,
 352                           logger *logger)
 353 {
 354   LOG_SCOPE (logger);
 355   gcc_assert (new_entry_enode);
 356   gcc_assert (prev_entry_enode);
 357   gcc_assert (is_entrypoint_p (new_entry_enode));
 358   gcc_assert (is_entrypoint_p (prev_entry_enode));
 359
 360   const int new_stack_depth = new_entry_enode->get_stack_depth ();
 361
 362   /* Compare the stores of the two enodes.  */
 363   const region_model &new_model
 364     = *new_entry_enode->get_state ().m_region_model;
 365   const region_model &prev_model
 366     = *prev_entry_enode->get_state ().m_region_model;
 367   const store &new_store = *new_model.get_store ();
 368
 369   for (auto kv : new_store)
 370     {
 371       const region *base_reg = kv.first;
 372
 373       /* Get the value within the new frame.  */
 374       const svalue *new_sval
 375         = new_model.get_store_value (base_reg, NULL);
 376
 377       /* If the value is UNKNOWN (e.g. due to hitting complexity limits)
 378          assume that it differs from the previous value.  */
 379       if (new_sval->get_kind () == SK_UNKNOWN)
 380         return true;
 381
 382       /* Get the equivalent value within the old enode.  */
 383       const svalue *prev_sval;
 384
 385       if (const frame_region *enclosing_frame
 386             = base_reg->maybe_get_frame_region ())
 387         {
 388           /* We have a binding within a frame in the new entry enode.  */
 389
 390           /* Ignore bindings within frames below the new entry node.  */
 391           if (enclosing_frame->get_stack_depth () < new_stack_depth)
 392             continue;
 393
 394           /* We have a binding within the frame of the new entry node,
 395              presumably a parameter.  */
 396
 397           /* Get the value within the equivalent frame of
 398              the old entrypoint; typically will be the initial_svalue
 399              of the parameter.  */
 400           const frame_region *equiv_prev_frame
 401             = prev_model.get_current_frame ();
 402           const region *equiv_prev_base_reg
 403             = remap_enclosing_frame (base_reg,
 404                                      enclosing_frame,
 405                                      equiv_prev_frame,
 406                                      new_model.get_manager ());
 407           prev_sval = prev_model.get_store_value (equiv_prev_base_reg, NULL);
 408         }
 409       else
 410         prev_sval = prev_model.get_store_value (base_reg, NULL);
 411
 412       /* If the prev_sval is UNKNOWN (e.g. due to hitting complexity limits)
 413          assume that it will differ from any new value.  */
 414       if (prev_sval->get_kind () == SK_UNKNOWN)
 415         return true;
 416
 417       if (new_sval != prev_sval)
 418         return true;
 419     }
 420
 421   /* No significant differences found.  */
 422   return false;
 423 }
 424
 425 /* Implementation of -Wanalyzer-infinite-recursion.
 426
 427    Called when adding ENODE to the graph, after adding its first in-edge.
 428
 429    For function entrypoints, see if recursion has occurred, and, if so,
 430    check if the state of memory changed between the recursion levels,
 431    which would suggest some kind of decreasing variant that leads to
 432    termination.
 433
 434    For recursive calls where the state of memory is effectively unchanged
 435    between recursion levels, warn with -Wanalyzer-infinite-recursion.  */
 436
 437 void
 438 exploded_graph::detect_infinite_recursion (exploded_node *enode)
 439 {
 440   if (!is_entrypoint_p (enode))
 441     return;
 442   function *top_of_stack_fun = enode->get_function ();
 443   gcc_assert (top_of_stack_fun);
 444
 445   /* ....where a call to that function is already in the call string.  */
 446   const call_string &call_string = enode->get_point ().get_call_string ();
 447
 448   if (call_string.count_occurrences_of_function (top_of_stack_fun) < 2)
 449     return;
 450
 451   tree fndecl = top_of_stack_fun->decl;
 452
 453   log_scope s (get_logger (),
 454                "checking for infinite recursion",
 455                "considering recursion at EN: %i entering %qE",
 456                enode->m_index, fndecl);
 457
 458   /* Find enode that's the entrypoint for the previous frame for fndecl
 459      in the recursion.  */
 460   exploded_node *prev_entry_enode
 461     = find_previous_entry_to (top_of_stack_fun, enode);
 462   gcc_assert (prev_entry_enode);
 463   if (get_logger ())
 464     get_logger ()->log ("previous entrypoint to %qE is EN: %i",
 465                         fndecl, prev_entry_enode->m_index);
 466
 467   /* Look for changes to the state of memory between the recursion levels.  */
 468   if (sufficiently_different_p (enode, prev_entry_enode, get_logger ()))
 469     return;
 470
 471   /* Otherwise, the state of memory is effectively the same between the two
 472      recursion levels; warn.  */
 473
 474   const supernode *caller_snode = call_string.get_top_of_stack ().m_caller;
 475   const supernode *snode = enode->get_supernode ();
 476   gcc_assert (caller_snode->m_returning_call);
 477   get_diagnostic_manager ().add_diagnostic
 478     (enode, snode, caller_snode->m_returning_call, NULL,
 479      make_unique<infinite_recursion_diagnostic> (prev_entry_enode,
 480                                                  enode,
 481                                                  fndecl));
 482 }