I remembered that I have a working copy of the Intel PL/M-80 compiler. This is the code it generated:
Code:
00003 ;
00004 ; FIB: PROCEDURE(N) ADDRESS REENTRANT;
00005 ; DECLARE N BYTE;
00006 ;
00007 ; IF N < 2
00008 ; THEN
00009 ; RETURN N;
00010 ; ELSE
00011 ; RETURN FIB(N - 1) + FIB(N - 2);
00012 ;
00013 ; END FIB;
00014 ;
00015 ;
00016 ; 15,672,184 cycles
00017 ;
0100 00018 FIB:
0100 41 [5] 00019 mov B,C ; Put N in upper byte
0101 C5 [11] 00020 push B ; Push it on the stack
0102 33 [5] 00021 inx SP ; Give back unused lower byte
00022
0103 21 0000 [10] 00023 lxi H,0 ; Point to N on the stack
0106 39 [10] 00024 dad SP
0107 7E [7] 00025 mov A,M ; Get N
0108 FE 02 [7] 00026 cpi 2 ; Is it < 2?
010A D2 0116 [10] 00027 jnc L_0116 ; No
00028
010D 21 0000 [10] 00029 lxi H,0 ; Point to N on the stack
0110 39 [10] 00030 dad SP
0111 6E [7] 00031 mov L,M ; Get N
0112 26 00 [7] 00032 mvi H,0
00033
0114 33 [5] 00034 inx SP ; Get rid of N on the stack
00035
0115 C9 [10] 00036 ret
00037
0116 00038 L_0116:
0116 21 0000 [10] 00039 lxi H,0 ; Point to N on the stack
0119 39 [10] 00040 dad SP
011A 7E [7] 00041 mov A,M ; Get N
011B 3D [5] 00042 dcr A ; Make that N - 1
011C 4F [5] 00043 mov C,A ; Pass it in register C
011D CD 0100 [17] 00044 call FIB ; Calculate FIB(N - 1)
00045
0120 E5 [11] 00046 push H ; Stash result
00047
0121 21 0002 [10] 00048 lxi H,2 ; Point to N on the stack
0124 39 [10] 00049 dad SP
0125 7E [7] 00050 mov A,M ; Get N
0126 3D [5] 00051 dcr A ; Make that N - 2
0127 3D [5] 00052 dcr A
0128 4F [5] 00053 mov C,A ; Pass it in register C
0129 CD 0100 [17] 00054 call FIB ; Calculate FIB(N - 2)
00055
012C C1 [10] 00056 pop B ; Recover FIB(N - 1)
012D 09 [10] 00057 dad B ; Add them
00058
012E 33 [5] 00059 inx SP ; Get rid of N on the stack
00060
012F C9 [10] 00061 ret
00062
0130 00063 Test:
0130 0E 17 [7] 00064 mvi C,23 ; Calculate FIB(23)
0132 CD 0100 [17] 00065 call FIB
00066
0130 00067 end Test
PL/M provides only two types of variables, unsigned 8-bit called BYTE and unsigned 16-bit called ADDRESS. Coding TARAI in PL/M required biasing the numbers by two to keep them positive, otherwise the X <= Y comparison does not work.
It took quite a bit of study to figure out what was going on with this one. It is not very tight code, but it still managed to beat SDCC.
Code:
00003 ;
00004 ; TARAI: PROCEDURE(X, Y, Z) BYTE REENTRANT;
00005 ; DECLARE (X, Y, Z) BYTE;
00006 ;
00007 ; IF X <= Y
00008 ; THEN
00009 ; RETURN Y;
00010 ; ELSE
00011 ; RETURN TARAI(TARAI(X - 1, Y, Z),
00012 ; TARAI(Y - 1, Z, X),
00013 ; TARAI(Z - 1, X, Y));
00014 ;
00015 ; END TARAI;
00016 ;
00017 ;
00018 ; 275,171,653 cycles
00019 ;
0100 00020 TARAI:
00021
00022 ; SP ---+
00023 ; !
00024 ; +-----+-----+-----+-----+
00025 ; | RAL | RAH | X | ? |
00026 ; +-----+-----+-----+-----+
00027
0100 21 0000 [10] 00028 lxi H,0 ; Point to return address on the stack
0103 39 [10] 00029 dad SP
00030
0104 53 [5] 00031 mov D,E ; Put Z in upper byte
0105 D5 [11] 00032 push D ; Push it on the stack
0106 33 [5] 00033 inx SP ; Give back unused lower byte
00034
00035 ; SP ---+
00036 ; !
00037 ; +-----+-----+-----+-----+-----+
00038 ; | Z | RAL | RAH | X | ? |
00039 ; +-----+-----+-----+-----+-----+
00040
0107 41 [5] 00041 mov B,C ; Put Y in upper byte
0108 C5 [11] 00042 push B ; Push it on the stack
0109 33 [5] 00043 inx SP ; Give back unused lower byte
00044
00045 ; SP ---+
00046 ; !
00047 ; +-----+-----+-----+-----+-----+-----+
00048 ; | Y | Z | RAL | RAH | X | ? |
00049 ; +-----+-----+-----+-----+-----+-----+
00050
010A 5E [7] 00051 mov E,M ; Get low byte of return address
010B 23 [5] 00052 inx H
010C 56 [7] 00053 mov D,M ; Get high byte of return address
010D 23 [5] 00054 inx H
00055
010E 46 [7] 00056 mov B,M ; Get X
00057
010F 73 [7] 00058 mov M,E ; Replace X and unused byte with return addr
0110 23 [5] 00059 inx H
0111 72 [7] 00060 mov M,D
00061
0112 C5 [11] 00062 push B ; Push X into the stack
0113 33 [5] 00063 inx SP ; Give back unused lower byte
00064
00065 ; SP ---+
00066 ; !
00067 ; +-----+-----+-----+-----+-----+-----+-----+
00068 ; | X | Y | Z | RAL | RAH | RAL | RAH |
00069 ; +-----+-----+-----+-----+-----+-----+-----+
00070
0114 21 0001 [10] 00071 lxi H,1 ; Point to Y on the stack
0117 39 [10] 00072 dad SP
00073
0118 7E [7] 00074 mov A,M ; Get Y
00075
0119 21 0000 [10] 00076 lxi H,0 ; Point to X on the stack
011C 39 [10] 00077 dad SP
00078
011D BE [7] 00079 cmp M ; If X <= Y?
011E DA 012A [10] 00080 jc L_012A ; No
00081
0121 21 0001 [10] 00082 lxi H,1 ; Point to Y on the stack
0124 39 [10] 00083 dad SP
00084
0125 7E [7] 00085 mov A,M ; Get Y
00086
0126 33 [5] 00087 inx SP ; Get rid of X
0127 E1 [10] 00088 pop H ; Get rid of Y and Z
0128 E1 [10] 00089 pop H ; Get rid of extra copy of return address
00090
0129 C9 [10] 00091 ret
00092
012A 00093 L_012A:
00094
00095 ; SP ---+
00096 ; !
00097 ; +-----+-----+-----+-----+-----+-----+-----+
00098 ; | X | Y | Z | RAL | RAH | RAL | RAH |
00099 ; +-----+-----+-----+-----+-----+-----+-----+
00100
012A 21 0000 [10] 00101 lxi H,0 ; Point to X on the stack
012D 39 [10] 00102 dad SP
00103
012E 7E [7] 00104 mov A,M ; Get X
012F 3D [5] 00105 dcr A ; Make it X - 1
0130 4F [5] 00106 mov C,A ; Push it in the lower byte
0131 C5 [11] 00107 push B
00108
00109 ; SP ---+
00110 ; !
00111 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+
00112 ; | X-1 | ? | X | Y | Z | RAL | RAH | RAL | RAH |
00113 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+
00114
0132 23 [5] 00115 inx H ; Point to Y
0133 4E [7] 00116 mov C,M ; Get Y
0134 21 0004 [10] 00117 lxi H,4 ; Point to Z
0137 39 [10] 00118 dad SP
0138 5E [7] 00119 mov E,M ; Get Z
0139 CD 0100 [17] 00120 call TARAI ; Calculate TARAI(X - 1, Y, Z)
00121
00122 ; SP ---+
00123 ; !
00124 ; +-----+-----+-----+-----+-----+-----+-----+
00125 ; | X | Y | Z | RAL | RAH | RAL | RAH |
00126 ; +-----+-----+-----+-----+-----+-----+-----+
00127
013C 4F [5] 00128 mov C,A ; Push first value in lower byte
013D C5 [11] 00129 push B
00130
00131 ; SP ---+
00132 ; !
00133 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+
00134 ; | 1st | ? | X | Y | Z | RAL | RAH | RAL | RAH |
00135 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+
00136
013E 21 0003 [10] 00137 lxi H,3 ; Point to copy of Y on the stack
0141 39 [10] 00138 dad SP
0142 7E [7] 00139 mov A,M ; Get Y
0143 3D [5] 00140 dcr A ; Make it Y - 1
0144 4F [5] 00141 mov C,A ; Push it in the lower byte
0145 C5 [11] 00142 push B
00143
00144 ; SP ---+
00145 ; !
00146 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
00147 ; | Y-1 | ? | 1st | ? | X | Y | Z | RAL | RAH | RAL | RAH |
00148 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
00149
0146 23 [5] 00150 inx H ; Point to Z on the stack
0147 4E [7] 00151 mov C,M ; Get Z
0148 21 0004 [10] 00152 lxi H,4 ; Point to X on the stack
014B 39 [10] 00153 dad SP
014C 5E [7] 00154 mov E,M
014D CD 0100 [17] 00155 call TARAI ; Calculate TARAI(Y - 1, Z, X)
00156
00157 ; SP ---+
00158 ; !
00159 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+
00160 ; | 1st | ? | X | Y | Z | RAL | RAH | RAL | RAH |
00161 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+
00162
0150 F5 [11] 00163 push PSW ; Push second value in upper byte
00164
00165 ; SP ---+
00166 ; !
00167 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
00168 ; | CCR | 2nd | 1st | ? | X | Y | Z | RAL | RAH | RAL | RAH |
00169 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
00170
0151 21 0006 [10] 00171 lxi H,6 ; Point to Z on the stack
0154 39 [10] 00172 dad SP
0155 7E [7] 00173 mov A,M ; Get Z
0156 3D [5] 00174 dcr A ; Make it Z - 1
0157 4F [5] 00175 mov C,A ; Push it in the lower byte
0158 C5 [11] 00176 push B
00177
00178 ; SP ---+
00179 ; !
00180 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
00181 ; | Z-1 | ? | CCR | 2nd | 1st | ? | X | Y | Z | RAL | RAH | RAL | RAH |
00182 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
00183
0159 2B [5] 00184 dcx H ; Point to X on the stack
015A 2B [5] 00185 dcx H
015B 4E [7] 00186 mov C,M ; Get X
015C 21 0007 [10] 00187 lxi H,7 ; Point to Y on the stack
015F 39 [10] 00188 dad SP
0160 5E [7] 00189 mov E,M ; Get Y
0161 CD 0100 [17] 00190 call TARAI ; Calculate TARAI(Z - 1, X, Y)
00191
00192 ; SP ---+
00193 ; !
00194 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
00195 ; | CCR | 2nd | 1st | ? | X | Y | Z | RAL | RAH | RAL | RAH |
00196 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
00197
0164 5F [5] 00198 mov E,A ; Pass as third value
0165 C1 [10] 00199 pop B ; Recover second value
00200
00201 ; SP ---+
00202 ; !
00203 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+
00204 ; | 1st | ? | X | Y | Z | RAL | RAH | RAL | RAH |
00205 ; +-----+-----+-----+-----+-----+-----+-----+-----+-----+
00206
0166 48 [5] 00207 mov C,B
0167 CD 0100 [17] 00208 call TARAI ; Calculate final TARAI
00209
00210 ; SP ---+
00211 ; !
00212 ; +-----+-----+-----+-----+-----+-----+-----+
00213 ; | X | Y | Z | RAL | RAH | RAL | RAH |
00214 ; +-----+-----+-----+-----+-----+-----+-----+
00215
016A 33 [5] 00216 inx SP ; Get rid of X
016B E1 [10] 00217 pop H ; Get rid of Y and Z
016C E1 [10] 00218 pop H ; Get rid of extra copy of return address
00219
016D C9 [10] 00220 ret
00221
016E 00222 Start:
016E 0E 0C [7] 00223 mvi C,12
0170 C5 [11] 00224 push B
0171 1E 02 [7] 00225 mvi E,2
0173 0E 03 [7] 00226 mvi C,3
0175 CD 0100 [17] 00227 call TARAI
00228
016E 00229 end Start
Login
Register
FAQ
Search
