Yesterday, I've implemented tail recursion optimization (http://svn.freepascal.org/svn/fpc/trunk/compiler/opttail.pas resulting in http://www.hu.freepascal.org/fpcircbot/cgipastebin?msgid=158 pp11 is the new compiler, fpc11 the old, both are 2.1.1). It isn't enabled yet because it still needs some fine tuning. The question is however when should it be enabled? With -OoTAILREC? -O3? Something different?

It doesn't always improve performance ? It takes much more code ?

Micha

Op Tue, 10 Oct 2006, schreef Florian Klaempfl:

Yesterday, I've implemented tail recursion optimization (http://svn.freepascal.org/svn/fpc/trunk/compiler/opttail.pas resulting in http://www.hu.freepascal.org/fpcircbot/cgipastebin?msgid=158 pp11 is the new compiler, fpc11 the old, both are 2.1.1).

Wow!

It isn't enabled yet because it still needs some fine tuning. The question is however when should it be enabled? With -OoTAILREC? -O3? Something different?

If the optimization needs significant processing power, -O3. If it doesn't but is debug safe, -O1, if it is not debug safe, -O2.

A separate option -OoTAILREC is IMHO not necessary.

Daniël

Daniël Mantione wrote

If the optimization needs significant processing power, -O3. If it doesn't but is debug safe, -O1, if it is not debug safe, -O2.

It's definitely not debug safe, since it messes up stack information.

A separate option -OoTAILREC is IMHO not necessary.

All possible optimizations have their -Oo-switch for individual enabling disabling (like regvars, peepholeopt, asmcse, stackframe, loopunroll). It's both useful for debugging the individual optimizations and in case a user's program is incompatible with a particular optimization (either due to a bug in the optimization or an inherent requirement -- e.g., we could add -Oonostackframe at the end of the compiler switches for the RTL's object unit when compiling for x86).

Jonas

Well, it's use for real world applications is limited but for the typical recursive useless benchmark stuff it's nice to have and it wasn't much work.

Not really. I didn't try it yet but it shouldn't mess up much. The optimziation is done completely on the node level, the pascal code would look like http://www.hu.freepascal.org/fpcircbot/cgipastebin?msgid=156 except that there are temps involved to calculate the new parameters because calculating one parameter could require the original value of another one.

So it will probably -OoTAILREC and automatically included in -O2.

e.g., we could add -Oonostackframe at the end of the compiler switches for the RTL's object unit when compiling for x86).

What we still need are switches in the sources to enable particular optimizations.

Limited to what? Binary tree data structures only? ;)

Vinzent.

?

Well, real world binary trees are usually limited by memory latencies because of their random access patterns so some tail recursion optimziation helps little.

Which means that the parameter values cannot be properly seen in the debugger, no? Also, do you actually insert goto/label nodes? That would degrade the performance of the register variable assignment because of the current limitations concerning flow analysis (i.e., for sufficiently complex routines, the tail recursion optimization may currently result in performance degradation rather than improvement compared to using regvars without it).

{$optimization nostackframe}

should work.

Jonas

Florian Klaempfl wrote

>> -OoTAILREC? -O3? Something different? > It doesn't always improve performance ? It takes much more code ? ?

I thought the difference between -O2 and -O3 is that -O3 is not actually guaranteed to improve "global" performance, for example due to the code expanding a lot. So therefore the question: does it always improve performance ? Does it blow up code size a lot ?

Micha

Op Tue, 10 Oct 2006, schreef Micha Nelissen:

I don't think so, because for tail recursion optimization you assign the parameters to the local variables (should not be larger than pushing them) and then jump to the start of the procedure (should not be larger than calling).

Daniël

Op Tue, 10 Oct 2006, schreef Vinzent Hoefler:

Well, I think the answer is here that any programmer that focuses on performance will already remove recursions manually. However, users compare compilers using benchmarks, so having optimizations for those makes sense.

Daniël

This is a hidden step, but the callstack window isn't done properly, that's true.

The recursive call is usually inside an if anyways so the ssa optimizer is lost anyways, no? But as I said, for the usual benchmark case it works great (the code is almost on pair with gcc after a quick look at it):

.balign 16,0x90
.globl P$ACKERMAN_ACK$LONGINT$LONGINT$$LONGINT
P$ACKERMAN_ACK$LONGINT$LONGINT$$LONGINT:
# Temps allocated between esp+0 and esp+16
# [ackermann.pp]
# [8] begin
subl $16,%esp
# Var M located in register ebx
# Var N located in register esi
# Var $result located in register edi
movl %ebx,(%esp)
movl %esi,4(%esp)
movl %edi,8(%esp)
movl %eax,%ebx
movl %edx,%esi
.Lj5:
# [9] if M = 0 then Ack := N+1
testl %ebx,%ebx
jne .Lj7
movl %esi,%eax
incl %eax
movl %eax,%edi
jmp .Lj10
.Lj7:
# [10] else if N = 0 then Ack := Ack(M-1, 1)
testl %esi,%esi
jne .Lj12
movl $1,%edx
decl %ebx
movl %edx,%esi
jmp .Lj5
.Lj12:
# [11] else Ack := Ack(M-1, Ack(M, N-1));
movl %esi,%edx
decl %edx
movl %ebx,%eax
call P$ACKERMAN_ACK$LONGINT$LONGINT$$LONGINT
decl %ebx
movl %eax,%esi
jmp .Lj5
.Lj21:
.Lj10:
# [12] end;
movl %edi,%eax
movl (%esp),%ebx
movl 4(%esp),%esi
movl 8(%esp),%edi
addl $16,%esp
ret

BTW: Does the assembler optimizer track flag usage? Then we could remove some of the

movl %esi,%eax
incl %eax

like pairs.

Didn't know about it :)

For the part inside the if: yes. But not for the part coming before it. What's more important however is that goto/label not only removes the usage of SSA, it also means that all register variables are allocated at the start of the function and only freed at the end. Without goto/label, register variables are only allocated between their first and last use (usage in a loop means allocation until the end of that loop).

There's a FlagsUsed field in the ttaiprop record which is set to true if the flags result of that instruction is used.

Jonas

Practical argument:
the assembler code _is_ better for the code I tested and up to as twice as fast as the original one.

Theoretical argument:
- using the tail goto you've one function with one set of variables being active across the the whole function
- using a recursive call you've at least two sets of variables: the caller and the callee ones. Though one set is only active at a limited part of the function, the set of the caller is still in use while the callee is called though they (the caller variables) are spilled.

I guess it could be used to change to code above to leal 1(%esi),%eax
?

Or is this slower on some CPUs?

Op Tue, 10 Oct 2006, schreef Florian Klaempfl:

In the worst case, as fast. Some cpu's use an extra clock cycle through the ALU to calculate the effective address (Pentium 1 if I recall well).

RISC86 cpus (k6..opteron) use their load/store unit to calculate this, so it might speed up because one extra ALU is free, or slow down because the load/store unit is occupied by another instruction.

Daniël

Florian Klaempfl wrote

Practical argument: the assembler code _is_ better for the code I tested and up to as twice as fast as the original one.

That's indeed true for an extremely small function with so few local variables/parameters that even on an i386 it doesn't need spilling in the absence of register allocation optimizations. That's why I said it *may* currently degrade performance in more complex functions (it also may not, I really don't know, it was just a remark).

The first point is just as much a downside as an upside in the current situation, because parameters/variables which are used without being destroyed by some function call can normally be put in a (reusable) volatile register. Now they need a non-volatile register during the entire function.

The fact that you get such a speedup is in my view mainly an indication of the fact that the function barely does anything, and that almost half the time is spent in setting up and tearing down stack frames. So it's logical that register allocation has little influence and that optimizations which remove this stack frame logic help a lot.

I guess it could be used to change to code above to leal 1(%esi),%eax ?

Yes.

Or is this slower on some CPUs?

I don't know.

Jonas

Jonas Maebe wrote:

[...]

Well, basically I agree with all your points ;) That's why I said the optimization is almost useless for real world programs. Nevertheless it helps for the benchmarks and gcc does it to. I'll try to find out the influence on the compiler/rtl, there are some examples where it applies (from ftl\inc\objpas.inc):

      class function TObject.getinterfaceentry(const iid : tguid) : pinterfaceentry;
        var
          i: integer;
          intftable: pinterfacetable;
          Res: pinterfaceentry;
        begin
          getinterfaceentry:=nil;
          intftable:=pinterfacetable((pointer(Self)+vmtIntfTable)^);
          if assigned(intftable) then begin
            i:=intftable^.EntryCount;
            ;
            while (i>0) and
               not (assigned(Res^.iid) and IsGUIDEqual(Res^.iid^,iid)) do begin
              inc(Res);
              dec(i);
            end;
            if (i>0) then
              getinterfaceentry:=Res;
          end;
          if (getinterfaceentry=nil)and not(classparent=nil) then
            getinterfaceentry:=classparent.getinterfaceentry(iid)
        end;

I tried this with the recursive benchmark:
http://svn.freepascal.org/svn/fpc/trunk/tests/bench/shootout/src/recursive.pp

Using fpc
2.0.4: 9.1 s
2.1.1: 8.1 s
with {$OPTIMIZATION tailrec}: 6.0 s.

gcc is 2.6 times faster than fpc 2.0.4 (see
http://shootout.alioth.debian.org/gp4/benchmark.php?test=recursive&lang=all) so it would do 3.5 seconds about this benchmark.

Vincent

Vincent Snijders wrote

I tried this with the recursive benchmark: http://svn.freepascal.org/svn/fpc/trunk/tests/bench/shootout/src/recursive.pp

How much does leaving fwait away help?

There is a small, but measurable difference:
fpc 2.0.4: 9.04
fpc 2.0.4 without fwait: 8.96

So, there is some speedup, but not spectacular.

Vincent

Since I found no test regression nor a problems with make all I enabled the optimization for x86-64, i386, sparc and arm. I leave powerpc(64) to Jonas, he might do so or not ;)

Florian Klaempfl wrote

Since I found no test regression nor a problems with make all I enabled the optimization for x86-64, i386, sparc and arm. I leave powerpc(64) to Jonas, he might do so or not ;)

Yesterday I checked and could not find a single difference in generated PPC code for the compiler and RTL with or without - Ootailrec... The only place where I saw any difference was in the ackermann benchmark...

Jonas

On a side note, fixing branch priority (order? I like compiler programming but I'm not very into it :-( ) takes the run time down by about 20% on a Duron system...

Do you plan to add some related tricks to FPC? (I'm not talking about the advanced "lively analysis" that is in the to-do, but rather some simple tricks like moving code throwing exceptions as if was in the 'else' block, or (in the uncertain optimizations) move to 'else' the biggest block or blocks containing a single or constant assignment...)

Cheers,
Flávio

Yes, that's what I found too :) But there are some cases which I've to check why they aren't optimized.