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        (m_new_entry_enode->get_supernode ()->get_start_location (),
 195         m_callee_fndecl,
 196         m_new_entry_enode->get_stack_depth (),
 197         NULL, NULL, NULL));
 198   }
 199
 200 private:
 201   const exploded_node *m_prev_entry_enode;
 202   const exploded_node *m_new_entry_enode;
 203   tree m_callee_fndecl;
 204   const checker_event *m_prev_entry_event;
 205 };
 206
 207 /* Return true iff ENODE is the PK_BEFORE_SUPERNODE at a function
 208    entrypoint.  */
 209
 210 static bool
 211 is_entrypoint_p (exploded_node *enode)
 212 {
 213   /* Look for an entrypoint to a function...  */
 214   const supernode *snode = enode->get_supernode ();
 215   if (!snode)
 216     return false;
 217   if (!snode->entry_p ())
 218     return false;;
 219   const program_point &point = enode->get_point ();
 220   if (point.get_kind () != PK_BEFORE_SUPERNODE)
 221     return false;
 222   return true;
 223 }
 224
 225 /* Walk backwards through the eg, looking for the first
 226    enode we find that's also the entrypoint of the same function.  */
 227
 228 exploded_node *
 229 exploded_graph::find_previous_entry_to (function *top_of_stack_fun,
 230                                         exploded_node *enode) const
 231 {
 232   auto_vec<exploded_node *> worklist;
 233   hash_set<exploded_node *> visited;
 234
 235   visited.add (enode);
 236   for (auto in_edge : enode->m_preds)
 237     worklist.safe_push (in_edge->m_src);
 238
 239   while (worklist.length () > 0)
 240     {
 241       exploded_node *iter = worklist.pop ();
 242
 243       if (is_entrypoint_p (iter)
 244           && iter->get_function () == top_of_stack_fun)
 245         return iter;
 246
 247       if (visited.contains (iter))
 248         continue;
 249       visited.add (iter);
 250       for (auto in_edge : iter->m_preds)
 251         worklist.safe_push (in_edge->m_src);
 252     }
 253
 254   /* Not found.  */
 255   return NULL;
 256 }
 257
 258 /* Given BASE_REG within ENCLOSING_FRAME (such as a function parameter),
 259    remap it to the equivalent region within EQUIV_PREV_FRAME.
 260
 261    For example, given param "n" within frame "foo@3", and equiv prev frame
 262    "foo@1", remap it to param "n" within frame "foo@1".  */
 263
 264 static const region *
 265 remap_enclosing_frame (const region *base_reg,
 266                        const frame_region *enclosing_frame,
 267                        const frame_region *equiv_prev_frame,
 268                        region_model_manager *mgr)
 269 {
 270   gcc_assert (base_reg->get_parent_region () == enclosing_frame);
 271   switch (base_reg->get_kind ())
 272     {
 273     default:
 274       /* We should only encounter params and varargs at the topmost
 275          entrypoint.  */
 276       gcc_unreachable ();
 277
 278     case RK_VAR_ARG:
 279       {
 280         const var_arg_region *var_arg_reg = (const var_arg_region *)base_reg;
 281         return mgr->get_var_arg_region (equiv_prev_frame,
 282                                         var_arg_reg->get_index ());
 283       }
 284     case RK_DECL:
 285       {
 286         const decl_region *decl_reg = (const decl_region *)base_reg;
 287         return equiv_prev_frame->get_region_for_local (mgr,
 288                                                        decl_reg->get_decl (),
 289                                                        NULL);
 290       }
 291     }
 292 }
 293
 294 /* Compare the state of memory at NEW_ENTRY_ENODE and PREV_ENTRY_ENODE,
 295    both of which are entrypoints to the same function, where recursion has
 296    occurred.
 297
 298    Return true if the state of NEW_ENTRY_ENODE is sufficiently different
 299    from PREV_ENTRY_ENODE to suggests that some variant is being modified,
 300    and thus the recursion isn't infinite.
 301
 302    Return false if the states are effectively the same, suggesting that
 303    the recursion is infinite.
 304
 305    For example, consider mutually recursive functions "foo" and "bar".
 306    At the entrypoint to a "foo" frame where we've detected recursion,
 307    we might have three frames on the stack: the new 'foo'@3, an inner
 308    'bar'@2, and the innermost 'foo'@1.
 309
 310      (gdb) call enode->dump(m_ext_state)
 311      EN: 16
 312      callstring: [(SN: 9 -> SN: 3 in foo), (SN: 5 -> SN: 8 in bar)]
 313      before SN: 0 (NULL from-edge)
 314
 315      rmodel:
 316      stack depth: 3
 317        frame (index 2): frame: ‘foo’@3
 318        frame (index 1): frame: ‘bar’@2
 319        frame (index 0): frame: ‘foo’@1
 320      clusters within root region
 321        cluster for: (*INIT_VAL(f_4(D)))
 322      clusters within frame: ‘bar’@2
 323        cluster for: b_2(D): INIT_VAL(f_4(D))
 324      clusters within frame: ‘foo’@3
 325        cluster for: f_4(D): INIT_VAL(f_4(D))
 326      m_called_unknown_fn: FALSE
 327
 328    whereas for the previous entry node we'd have just the innermost
 329    'foo'@1
 330
 331      (gdb) call prev_entry_enode->dump(m_ext_state)
 332      EN: 1
 333      callstring: []
 334      before SN: 0 (NULL from-edge)
 335
 336      rmodel:
 337      stack depth: 1
 338        frame (index 0): frame: ‘foo’@1
 339      clusters within root region
 340        cluster for: (*INIT_VAL(f_4(D)))
 341      m_called_unknown_fn: FALSE
 342
 343    We want to abstract away frames 1 and 2 in the new entry enode,
 344    and compare its frame 3 with the frame 1 in the previous entry
 345    enode, and determine if enough state changes between them to
 346    rule out infinite recursion.  */
 347
 348 static bool
 349 sufficiently_different_p (exploded_node *new_entry_enode,
 350                           exploded_node *prev_entry_enode,
 351                           logger *logger)
 352 {
 353   LOG_SCOPE (logger);
 354   gcc_assert (new_entry_enode);
 355   gcc_assert (prev_entry_enode);
 356   gcc_assert (is_entrypoint_p (new_entry_enode));
 357   gcc_assert (is_entrypoint_p (prev_entry_enode));
 358
 359   const int new_stack_depth = new_entry_enode->get_stack_depth ();
 360
 361   /* Compare the stores of the two enodes.  */
 362   const region_model &new_model
 363     = *new_entry_enode->get_state ().m_region_model;
 364   const region_model &prev_model
 365     = *prev_entry_enode->get_state ().m_region_model;
 366   const store &new_store = *new_model.get_store ();
 367
 368   for (auto kv : new_store)
 369     {
 370       const region *base_reg = kv.first;
 371
 372       /* Get the value within the new frame.  */
 373       const svalue *new_sval
 374         = new_model.get_store_value (base_reg, NULL);
 375
 376       /* If the value is UNKNOWN (e.g. due to hitting complexity limits)
 377          assume that it differs from the previous value.  */
 378       if (new_sval->get_kind () == SK_UNKNOWN)
 379         return true;
 380
 381       /* Get the equivalent value within the old enode.  */
 382       const svalue *prev_sval;
 383
 384       if (const frame_region *enclosing_frame
 385             = base_reg->maybe_get_frame_region ())
 386         {
 387           /* We have a binding within a frame in the new entry enode.  */
 388
 389           /* Ignore bindings within frames below the new entry node.  */
 390           if (enclosing_frame->get_stack_depth () < new_stack_depth)
 391             continue;
 392
 393           /* We have a binding within the frame of the new entry node,
 394              presumably a parameter.  */
 395
 396           /* Get the value within the equivalent frame of
 397              the old entrypoint; typically will be the initial_svalue
 398              of the parameter.  */
 399           const frame_region *equiv_prev_frame
 400             = prev_model.get_current_frame ();
 401           const region *equiv_prev_base_reg
 402             = remap_enclosing_frame (base_reg,
 403                                      enclosing_frame,
 404                                      equiv_prev_frame,
 405                                      new_model.get_manager ());
 406           prev_sval = prev_model.get_store_value (equiv_prev_base_reg, NULL);
 407         }
 408       else
 409         prev_sval = prev_model.get_store_value (base_reg, NULL);
 410
 411       /* If the prev_sval is UNKNOWN (e.g. due to hitting complexity limits)
 412          assume that it will differ from any new value.  */
 413       if (prev_sval->get_kind () == SK_UNKNOWN)
 414         return true;
 415
 416       if (new_sval != prev_sval)
 417         return true;
 418     }
 419
 420   /* No significant differences found.  */
 421   return false;
 422 }
 423
 424 /* Implementation of -Wanalyzer-infinite-recursion.
 425
 426    Called when adding ENODE to the graph, after adding its first in-edge.
 427
 428    For function entrypoints, see if recursion has occurred, and, if so,
 429    check if the state of memory changed between the recursion levels,
 430    which would suggest some kind of decreasing variant that leads to
 431    termination.
 432
 433    For recursive calls where the state of memory is effectively unchanged
 434    between recursion levels, warn with -Wanalyzer-infinite-recursion.  */
 435
 436 void
 437 exploded_graph::detect_infinite_recursion (exploded_node *enode)
 438 {
 439   if (!is_entrypoint_p (enode))
 440     return;
 441   function *top_of_stack_fun = enode->get_function ();
 442   gcc_assert (top_of_stack_fun);
 443
 444   /* ....where a call to that function is already in the call string.  */
 445   const call_string &call_string = enode->get_point ().get_call_string ();
 446
 447   if (call_string.count_occurrences_of_function (top_of_stack_fun) < 2)
 448     return;
 449
 450   tree fndecl = top_of_stack_fun->decl;
 451
 452   log_scope s (get_logger (),
 453                "checking for infinite recursion",
 454                "considering recursion at EN: %i entering %qE",
 455                enode->m_index, fndecl);
 456
 457   /* Find enode that's the entrypoint for the previous frame for fndecl
 458      in the recursion.  */
 459   exploded_node *prev_entry_enode
 460     = find_previous_entry_to (top_of_stack_fun, enode);
 461   gcc_assert (prev_entry_enode);
 462   if (get_logger ())
 463     get_logger ()->log ("previous entrypoint to %qE is EN: %i",
 464                         fndecl, prev_entry_enode->m_index);
 465
 466   /* Look for changes to the state of memory between the recursion levels.  */
 467   if (sufficiently_different_p (enode, prev_entry_enode, get_logger ()))
 468     return;
 469
 470   /* Otherwise, the state of memory is effectively the same between the two
 471      recursion levels; warn.  */
 472
 473   const supernode *caller_snode = call_string.get_top_of_stack ().m_caller;
 474   const supernode *snode = enode->get_supernode ();
 475   gcc_assert (caller_snode->m_returning_call);
 476   get_diagnostic_manager ().add_diagnostic
 477     (enode, snode, caller_snode->m_returning_call, NULL,
 478      make_unique<infinite_recursion_diagnostic> (prev_entry_enode,
 479                                                  enode,
 480                                                  fndecl));
 481 }