View Issue Details

IDProjectCategoryView StatusLast Update
0032811FPCCompilerpublic2019-12-30 23:43
ReporterAdam DingleAssigned ToFlorian 
PrioritynormalSeverityminorReproducibilityalways
Status resolvedResolutionfixed 
Product Version3.0.2Product Build 
Target VersionFixed in Version3.3.1 
Summary0032811: eliminate tail recursion for functions with var parameters
DescriptionCurrently the optimizer won't eliminate tail recursion for functions that have var parameters. This is evident in opttail.pas, where there is code starting at the comment

    { check if the parameters actually would support tail recursion elimination }

the scans the parameters and exits if any of them have the var (or out) attribute.

That's too bad, since it's convenient to write many data structure operations recursively. For example, here's an insert procedure for a binary tree. Without this optimization, it could run out of stack space if the tree is unbalanced and tall.

===

type
  node = record
    i: integer;
    left: ^node;
    right: ^node;
  end;
  pnode = ^node;

procedure insert(var t: pnode; i: integer);
begin
  if t = nil then
    begin
      new(t);
      t^.i := i;
      t^.left := nil;
      t^.right := nil;
    end
  else
    if i < t^.i
      then insert(t^.left, i)
      else insert(t^.right, i);
end;
TagsNo tags attached.
Fixed in Revision43824
FPCOldBugId
FPCTarget-
Attached Files

Activities

Anton

2017-12-11 19:59

reporter   ~0104641

Indeed, this code should not be compiled at all, because the type of "t^.left" is not "pnode". This can cause serious errors, so bug in compiler, I think. But this is a different issue.

The correct type declaration is as follows:
type
  pnode = ^node;
  node = record
    i: integer;
    left: pnode;
    right: pnode;
  end;

Thaddy de Koning

2017-12-11 20:48

reporter   ~0104643

Last edited: 2017-12-11 20:53

View 4 revisions

And integer is not a good way to express a node entry pointer: should be ptrUint.
type
  pnode = ^node;
  node = record
    i: ptrUint;
    left: pnode;
    right: pnode;
  end;

Meaning long before the recursion fails with an out-of-memory or stack problems you have an integer overflow..........At half your memory size...

Issue History

Date Modified Username Field Change
2017-12-11 16:24 Adam Dingle New Issue
2017-12-11 19:59 Anton Note Added: 0104641
2017-12-11 20:48 Thaddy de Koning Note Added: 0104643
2017-12-11 20:49 Thaddy de Koning Note Edited: 0104643 View Revisions
2017-12-11 20:52 Thaddy de Koning Note Edited: 0104643 View Revisions
2017-12-11 20:53 Thaddy de Koning Note Edited: 0104643 View Revisions
2019-12-30 23:43 Florian Assigned To => Florian
2019-12-30 23:43 Florian Status new => resolved
2019-12-30 23:43 Florian Resolution open => fixed
2019-12-30 23:43 Florian Fixed in Version => 3.3.1
2019-12-30 23:43 Florian Fixed in Revision => 43824
2019-12-30 23:43 Florian FPCTarget => -