#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tree.h"
#include "fold-const.h"
#include "gcc-rich-location.h"
#include "alloc-pool.h"
#include "fibonacci_heap.h"
#include "shortest-paths.h"
#include "diagnostic-core.h"
#include "diagnostic-event-id.h"
#include "diagnostic-path.h"
#include "function.h"
#include "pretty-print.h"
#include "sbitmap.h"
#include "bitmap.h"
#include "tristate.h"
#include "ordered-hash-map.h"
#include "selftest.h"
#include "json.h"
#include "analyzer/analyzer.h"
#include "analyzer/analyzer-logging.h"
#include "analyzer/call-string.h"
#include "analyzer/program-point.h"
#include "analyzer/store.h"
#include "analyzer/region-model.h"
#include "analyzer/constraint-manager.h"
#include "analyzer/sm.h"
#include "analyzer/pending-diagnostic.h"
#include "analyzer/diagnostic-manager.h"
#include "cfg.h"
#include "basic-block.h"
#include "gimple.h"
#include "gimple-iterator.h"
#include "gimple-pretty-print.h"
#include "cgraph.h"
#include "digraph.h"
#include "analyzer/supergraph.h"
#include "analyzer/program-state.h"
#include "analyzer/exploded-graph.h"
#include "make-unique.h"
#include "analyzer/checker-path.h"
#include "analyzer/feasible-graph.h"
#include "diagnostic-format-sarif.h"

Include dependency graph for infinite-recursion.cc:

Data Structures
class	infinite_recursion_diagnostic

Macros
#define	INCLUDE_MEMORY

#define	PROPERTY_PREFIX "gcc/analyzer/infinite_recursion_diagnostic/"

Macro Definition Documentation

◆ INCLUDE_MEMORY

#define INCLUDE_MEMORY

Detection of infinite recursion.
   Copyright (C) 2022-2024 Free Software Foundation, Inc.
   Contributed by David Malcolm <dmalcolm@redhat.com>.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.

◆ PROPERTY_PREFIX

#define PROPERTY_PREFIX "gcc/analyzer/infinite_recursion_diagnostic/"

Function Documentation

◆ contains_unknown_p()

static bool contains_unknown_p ( const svalue * sval )

static

Return true iff SVAL is unknown, or contains an unknown svalue.

References ana::svalue::dyn_cast_compound_svalue(), ana::svalue::get_kind(), ggc_alloc(), and ana::SK_UNKNOWN.

Referenced by sufficiently_different_region_binding_p().

◆ is_entrypoint_p()

static bool is_entrypoint_p ( exploded_node * enode )

static

Return true iff ENODE is the PK_BEFORE_SUPERNODE at a function
entrypoint.

References ggc_alloc(), and ana::PK_BEFORE_SUPERNODE.

Referenced by ana::exploded_graph::detect_infinite_recursion(), ana::exploded_graph::find_previous_entry_to(), and sufficiently_different_p().

◆ remap_enclosing_frame()

static const region * remap_enclosing_frame	(	const region *	base_reg,
		const frame_region *	enclosing_frame,
		const frame_region *	equiv_prev_frame,
		region_model_manager *	mgr )

static

Given BASE_REG within ENCLOSING_FRAME (such as a function parameter),
remap it to the equivalent region within EQUIV_PREV_FRAME.

For example, given param "n" within frame "foo@3", and equiv prev frame
"foo@1", remap it to param "n" within frame "foo@1".

References gcc_assert, gcc_unreachable, ggc_alloc(), NULL, ana::RK_DECL, and ana::RK_VAR_ARG.

Referenced by sufficiently_different_region_binding_p().

◆ sufficiently_different_p()

static bool sufficiently_different_p	(	exploded_node *	new_entry_enode,
		exploded_node *	prev_entry_enode,
		logger *	logger )

static

Compare the state of memory at NEW_ENTRY_ENODE and PREV_ENTRY_ENODE,
both of which are entrypoints to the same function, where recursion has
occurred.

Return true if the state of NEW_ENTRY_ENODE is sufficiently different
from PREV_ENTRY_ENODE to suggest that some variant is being modified,
and thus the recursion isn't infinite.

Return false if the states are effectively the same, suggesting that
the recursion is infinite.

For example, consider mutually recursive functions "foo" and "bar".
At the entrypoint to a "foo" frame where we've detected recursion,
we might have three frames on the stack: the new 'foo'@3, an inner
'bar'@2, and the innermost 'foo'@1.

  (gdb) call enode->dump(m_ext_state)
  EN: 16
  callstring: [(SN: 9 -> SN: 3 in foo), (SN: 5 -> SN: 8 in bar)]
  before SN: 0 (NULL from-edge)

  rmodel:
  stack depth: 3
    frame (index 2): frame: ‘foo’@3
    frame (index 1): frame: ‘bar’@2
    frame (index 0): frame: ‘foo’@1
  clusters within root region
    cluster for: (*INIT_VAL(f_4(D)))
  clusters within frame: ‘bar’@2
    cluster for: b_2(D): INIT_VAL(f_4(D))
  clusters within frame: ‘foo’@3
    cluster for: f_4(D): INIT_VAL(f_4(D))
  m_called_unknown_fn: FALSE

whereas for the previous entry node we'd have just the innermost
'foo'@1

  (gdb) call prev_entry_enode->dump(m_ext_state)
  EN: 1
  callstring: []
  before SN: 0 (NULL from-edge)

  rmodel:
  stack depth: 1
    frame (index 0): frame: ‘foo’@1
  clusters within root region
    cluster for: (*INIT_VAL(f_4(D)))
  m_called_unknown_fn: FALSE

We want to abstract away frames 1 and 2 in the new entry enode,
and compare its frame 3 with the frame 1 in the previous entry
enode, and determine if enough state changes between them to
rule out infinite recursion.

References gcc_assert, ggc_alloc(), is_entrypoint_p(), LOG_SCOPE, and sufficiently_different_region_binding_p().

Referenced by ana::exploded_graph::detect_infinite_recursion().

◆ sufficiently_different_region_binding_p()

static bool sufficiently_different_region_binding_p	(	exploded_node *	new_entry_enode,
		exploded_node *	prev_entry_enode,
		const region *	base_reg )

static

Subroutine of sufficiently_different_p.  Compare the store bindings
for BASE_REG within NEW_ENTRY_ENODE and PREV_ENTRY_ENODE.

Return true if the state of NEW_ENTRY_ENODE is sufficiently different
from PREV_ENTRY_ENODE within BASE_REG to suggest that some variant is
being modified, and thus the recursion isn't infinite.

Return false if the states for BASE_REG are effectively the same.

References contains_unknown_p(), ggc_alloc(), NULL, and remap_enclosing_frame().

Referenced by sufficiently_different_p().

Functions
static bool	is_entrypoint_p (exploded_node *enode)

static const region *	remap_enclosing_frame (const region base_reg, const frame_region enclosing_frame, const frame_region equiv_prev_frame, region_model_manager mgr)

static bool	contains_unknown_p (const svalue *sval)

static bool	sufficiently_different_region_binding_p (exploded_node new_entry_enode, exploded_node prev_entry_enode, const region *base_reg)

static bool	sufficiently_different_p (exploded_node new_entry_enode, exploded_node prev_entry_enode, logger *logger)

Data Structures

Macros

Functions

Macro Definition Documentation

◆ INCLUDE_MEMORY

◆ PROPERTY_PREFIX

Function Documentation

◆ contains_unknown_p()

◆ is_entrypoint_p()

◆ remap_enclosing_frame()

◆ sufficiently_different_p()

◆ sufficiently_different_region_binding_p()