gcc/analyzer/infinite-recursion.cc

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