| M68K Ada Technical Summary: For mission-critical applications on Motorola M68000 family computers | ||
|---|---|---|
| Prev | Appendix A. Examples of Generated Code | Next |
Using an informal functional notation, Ackermann's function is defined as follows:
From the point of view of benchmarking, Ackermann's function is interesting because it consists almost entirely of subprogram calls, and nests the calls deeply if required. The number of calls and the degree of nesting is controlled using the two arguments.
We use A(3,6) as the benchmark. This gives us 172233 calls, with a nesting depth of 511.
Example A-3. Ada Source Code for Ackermann's Function
function Ackermann (M, N : in Integer) return Integer is
begin
if M = 0 then
return N + 1;
elsif N = 0 then
return Ackermann (M - 1, 1);
else
return Ackermann (M - 1, Ackermann (M, N - 1));
end if;
end Ackermann;
Ackermann's function provides two opportunities for tail recursion optimization, both of which are taken here. The two parameters are passed in register, and the calling procedure saves any live registers across a call.
The generated code is given in Example A-4. For this version of the summary the code was generated at optimization level 2.
Example A-4. Generated Code for Ackermann's Function
1 .file "ack.adb" 2 gcc2_compiled.: 3 __gnu_compiled_ada: 4 .text 5 .even 6 .globl _ada_ackermann 7 _ada_ackermann: 8 0000 4E56 0000 link.w %a6,#0 9 0004 2F0A move.l %a2,-(%sp) 10 0006 226E 0008 move.l 8(%a6),%a1 11 000a 206E 000C move.l 12(%a6),%a0 12 000e BBCF cmp.l %sp,%a5 13 0010 6B02 bmi.b .+4 14 0012 4E45 trap #5 15 .L5: 16 0014 4A89 tst.l %a1 17 0016 6606 jbne .L2 18 0018 2008 move.l %a0,%d0 19 001a 5280 addq.l #1,%d0 20 001c 6022 jbra .L6 21 .even 22 .L2: 23 001e 4A88 tst.l %a0 24 0020 6608 jbne .L4 25 0022 5389 subq.l #1,%a1 26 0024 307C 0001 move.w #1,%a0 27 0028 60EA jbra .L5 28 .even 29 .L4: 30 002a 45E9 FFFF lea (-1,%a1),%a2 31 002e 4868 FFFF pea -1(%a0) 32 0032 2F09 move.l %a1,-(%sp) 33 0034 4EBA FFCA jsr _ada_ackermann 34 0038 224A move.l %a2,%a1 35 003a 2040 move.l %d0,%a0 36 003c 508F addq.l #8,%sp 37 003e 60D4 jbra .L5 38 .even 39 .L6: 40 0040 246E FFFC move.l -4(%a6),%a2 41 0044 4E5E unlk %a6 42 0046 4E75 rts