| M1750 Ada Technical Summary: For mission-critical applications | ||
|---|---|---|
| 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_Benchmark (M, N : in Integer) return Integer is
begin
if M = 0 then
return N + 1;
elsif N = 0 then
return Ackermann_Benchmark (M - 1, 1);
else
return Ackermann_Benchmark (M - 1, Ackermann_Benchmark (M, N - 1));
end if;
end Ackermann_Benchmark;
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 with all checks on. Recompiling with checks off saves 14 bytes.
Example A-4. Generated Code for Ackermann's Function
1 .file "ackermann_benchmark.adb" 2 gcc2_compiled.: 3 __gnu_compiled_ada: 4 .text 5 .global _ada_ackermann_benchmark 6 _ada_ackermann_benchmark: 7 0000 B2F0 sisp r15,1 8 0002 9FEE pshm r14,r14 9 0004 81EF lr r14,r15 10 0006 8120 lr r2,r0 11 0008 8101 lr r0,r1 12 000a 81BF lr r11,r15 13 000c 4AB9 8000 xorm r11,0x8000 14 0010 F0B0 0000 c r11,_stack_limit 15 0014 7B02 bge .+4 16 0016 7708 bex 8 17 .L5: 18 0018 4A2A 0000 cim r2,0 19 001c 7A03 jnz .L2 20 001e A200 aisp r0,1 21 0020 7413 j .L6 22 .L2: 23 0022 4A0A 0000 cim r0,0 24 0026 7A04 jnz .L4 25 0028 B220 sisp r2,1 26 002a 8200 lisp r0,1 27 002c 74F6 j .L5 28 .L4: 29 002e 8532 FFFF lim r3,-1,r2 30 0032 903E 0001 st r3,1,r14 31 0036 8110 lr r1,r0 32 0038 B210 sisp r1,1 33 003a 8102 lr r0,r2 34 003c 7EF0 0000 sjs r15,_ada_ackermann_benchmark 35 0040 802E 0001 l r2,1,r14 36 0044 74EA j .L5 37 .L6: 38 0046 81FE lr r15,r14 39 0048 8FEE popm r14,r14 40 004a A2F0 aisp r15,1 41 004c 7FF0 urs r15