GCC Bugzilla has been upgraded from version 4.4.9 to 5.0rc3. If you see any problem, please report it to bug 64968.

Bug 48363

Summary: Recursion not converted into a loop
Product: gcc Reporter: Tobias Burnus <burnus>
Component: middle-endAssignee: Not yet assigned to anyone <unassigned>
Status: NEW ---    
Severity: normal Keywords: missed-optimization
Priority: P3    
Version: 4.7.0   
Target Milestone: ---   
Host: Target:
Build: Known to work:
Known to fail: Last reconfirmed: 2011-03-30 15:01:37

Description Tobias Burnus 2011-03-30 12:15:48 UTC
For the following Fortran program, the recursion could be replaced by a loop. That's what happening for the related C program, but for the Fortran program the recursion remains. (Tried with -O3.)

(I guess the I/O statement (_gfortran_st_write* and _gfortran_transfer_*_write) confuse the ME, but I do not see why that should prevent the loop transformation. Hints how to modify the FE to help the ME are welcome, too.)

! Fortran version
call x (1)
contains
  recursive subroutine x (i)
    use iso_fortran_env
    integer, value :: i
    if (mod (i, 1000000) == 0) write (error_unit,'(a,i0)')'i=', i
    call x (i+1)
  end subroutine x
end


/* C version */
#include <stdio.h>
static void
x (int i) {
  if (!(i % 1000000))
    fprintf(stderr, "i=%d\n", i);
  x(i + 1);
}
int main () {
  x (1);
}
Comment 1 Richard Biener 2011-03-30 15:01:37 UTC
The parameter has its address taken in

  _gfortran_transfer_integer_write (&dt_parm.0, &i, 4);

thus we can't tail-recurse here (well, at least not as trivial as if
that wasn't the case).
Comment 2 Tobias Burnus 2011-03-30 15:38:13 UTC
(In reply to comment #1)
> The parameter has its address taken in
>   _gfortran_transfer_integer_write (&dt_parm.0, &i, 4);

True, but the value is not modified - which the ME should know as the "fn spec" is ".wR"
Comment 3 Richard Biener 2011-03-30 15:54:28 UTC
(In reply to comment #2)
> (In reply to comment #1)
> > The parameter has its address taken in
> >   _gfortran_transfer_integer_write (&dt_parm.0, &i, 4);
> 
> True, but the value is not modified - which the ME should know as the "fn spec"
> is ".wR"

The parameter is not in SSA form so tail-recursion would have to insert
a store and reload the value at appropriate places.  It doesn't support that.