Collaboration diagram for tailcall:

Data Fields
gimple_stmt_iterator	call_gsi

bool	tail_recursion

tree	mult

tree	add

struct tailcall *	next

Detailed Description

Tail call optimization on trees.
   Copyright (C) 2003-2024 Free Software Foundation, Inc.

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/>.

The file implements the tail recursion elimination.  It is also used to
analyze the tail calls in general, passing the results to the rtl level
where they are used for sibcall optimization.

In addition to the standard tail recursion elimination, we handle the most
trivial cases of making the call tail recursive by creating accumulators.
For example the following function

int sum (int n)
{
  if (n > 0)
    return n + sum (n - 1);
  else
    return 0;
}

is transformed into

int sum (int n)
{
  int acc = 0;

  while (n > 0)
    acc += n--;

  return acc;
}

To do this, we maintain two accumulators (a_acc and m_acc) that indicate
when we reach the return x statement, we should return a_acc + x * m_acc
instead.  They are initially initialized to 0 and 1, respectively,
so the semantics of the function is obviously preserved.  If we are
guaranteed that the value of the accumulator never change, we
omit the accumulator.

There are three cases how the function may exit.  The first one is
handled in adjust_return_value, the other two in adjust_accumulator_values
(the second case is actually a special case of the third one and we
present it separately just for clarity):

1) Just return x, where x is not in any of the remaining special shapes.
   We rewrite this to a gimple equivalent of return m_acc * x + a_acc.

2) return f (...), where f is the current function, is rewritten in a
   classical tail-recursion elimination way, into assignment of arguments
   and jump to the start of the function.  Values of the accumulators
   are unchanged.

3) return a + m * f(...), where a and m do not depend on call to f.
   To preserve the semantics described before we want this to be rewritten
   in such a way that we finally return

   a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).

   I.e. we increase a_acc by a * m_acc, multiply m_acc by m and
   eliminate the tail call to f.  Special cases when the value is just
   added or just multiplied are obtained by setting a = 0 or m = 1.

TODO -- it is possible to do similar tricks for other operations.

A structure that describes the tailcall.

Field Documentation

◆ add

tree tailcall::add

Referenced by eliminate_tail_call().

◆ call_gsi

gimple_stmt_iterator tailcall::call_gsi

Referenced by eliminate_tail_call(), and optimize_tail_call().

◆ mult

tree tailcall::mult

Referenced by eliminate_tail_call().

◆ next

struct tailcall* tailcall::next

Referenced by tree_optimize_tail_calls_1().

◆ tail_recursion

bool tailcall::tail_recursion

Referenced by find_tail_calls(), and optimize_tail_call().

The documentation for this struct was generated from the following file:

tree-tailcall.cc