void putchar(char);
#define N 10
int in[N] = {10, 32, -1, 567, 3, 18, 1, -51, 789, 0};
|
; PDP-11 assembly generated by lcc 4.2 ; assemble with MACRO-11 .INCLUDE /LCC.MLB/ .RADIX 10 fp=%5 ; R5 is frame pointer .ENABL LSB ; file-wide local symbols .GLOBL in in: .WORD 10 .WORD 32 .WORD -1 .WORD 567 .WORD 3 .WORD 18 .WORD 1 .WORD -51 .WORD 789 .WORD 0 |
|
/* exchange - exchange *x and *y */
void exchange(x, y) int *x, *y; {
int t;
t = *x; *x = *y; *y = t;
}
There is an extra MOV in the code that I can't prevent lcc from generating. It seems to want to put x in a temporary register, but actually makes the code worse. The function should consist of just three MOVs. |
.GLOBL exchange .SBTTL exchange exchange: mov fp,-(sp) ; save frame pointer mov sp,fp clr -(sp) ; alloc stack frame ; mov 4(fp),r4 ; reg <- opd mov (r4),-2(fp) ; ASGNI2 mov @ 6(fp),(r4) ; ASGNI2 mov -2(fp),@ 6(fp) ; ASGNI2 1$: ; mov fp,sp ; pop stack frame mov (sp)+,fp ; restore frame pointer rts pc |
|
/* output unsigned decimal number */
void putu(unsigned n) {
unsigned d;
if (d = n/10)
putu(d);
putchar(n%10 + '0');
}
|
.GLOBL putu .SBTTL putu putu: mov fp,-(sp) ; save frame pointer mov sp,fp mov r3,-(sp) ; save ; mov 4(fp),r1 ; reg <- opd mov #10,r0 ; reg <- opd jsr pc,$DIVU ; DIVU2 mov r0,r3 ; LOADU2 tst r0 beq 3$ mov r3,-(sp) ; ARGU2 jsr pc,putu add #2,sp ; pop args 3$: mov 4(fp),r1 ; reg <- opd mov #10,r0 ; reg <- opd jsr pc,$DIVU ; MODU2 mov r1,r4 add #48,r4 movb r4,-(sp) ; ARGI2(CVII2) jsr pc,putchar add #2,sp ; pop args 2$: ; mov (sp)+,r3 ; restore mov (sp)+,fp ; restore frame pointer rts pc |
|
void putd(int n) {
if (n < 0) {
putchar('-');
putu(-n);
}else putu(n);
}
In two places, the compiler is unnecessarily loading n into a register. The ARGI2 rule should directly push 4(FP) and then negate top of stack. However lcc inserts a "LOAD" operator above the operand, which breaks any template we might write to prevent this. |
.GLOBL putd .SBTTL putd putd: mov fp,-(sp) ; save frame pointer mov sp,fp ; tst 4(fp) bpl 6$ mov #45,-(sp) ; ARGI2 jsr pc,putchar add #2,sp ; pop args mov 4(fp),r4 ; reg <- opd neg r4 mov r4,-(sp) ; ARGU2 jsr pc,putu add #2,sp ; pop args br 7$ 6$: mov 4(fp),r4 ; reg <- opd mov r4,-(sp) ; ARGU2 jsr pc,putu add #2,sp ; pop args 7$: 5$: ; mov (sp)+,fp ; restore frame pointer rts pc |
|
/* partition - partition a[i..j] */
int partition(a, i, j) int a[]; {
int v, k;
j++;
k = i;
v = a[k];
while (i < j) {
do i++; while (a[i] < v);
do j--; while (a[j] > v);
if (i < j) exchange(&a[i], &a[j]);
}
exchange(&a[k], &a[j]);
return j;
}
The ARGP2 rules are working well for us here, and the direct CMP of two frame variables is nice to see. |
.GLOBL partition .SBTTL partition partition: mov fp,-(sp) ; save frame pointer mov sp,fp mov r2,-(sp) ; save mov r3,-(sp) ; save ; inc 8(fp) mov 6(fp),r2 ; reg <- opd mov r2,r4 asl r4 add 4(fp),r4 mov (r4),r3 ; reg <- opd br 10$ 9$: 12$: inc 6(fp) 13$: mov 6(fp),r4 ; reg <- opd asl r4 add 4(fp),r4 cmp (r4),r3 blt 12$ 15$: dec 8(fp) 16$: mov 8(fp),r4 ; reg <- opd asl r4 add 4(fp),r4 cmp (r4),r3 bgt 15$ cmp 6(fp),8(fp) bge 18$ mov 4(fp),r4 ; reg <- opd mov 8(fp),r1 ; reg <- opd asl r1 mov r1,-(sp) add r4,(sp) ; ARGP2(ADDP2) mov 6(fp),r1 ; reg <- opd asl r1 mov r1,-(sp) add r4,(sp) ; ARGP2(ADDP2) jsr pc,exchange add #4,sp ; pop args 18$: 10$: cmp 6(fp),8(fp) blt 9$ mov 4(fp),r4 ; reg <- opd mov 8(fp),r1 ; reg <- opd asl r1 mov r1,-(sp) add r4,(sp) ; ARGP2(ADDP2) mov r2,r1 asl r1 mov r1,-(sp) add r4,(sp) ; ARGP2(ADDP2) jsr pc,exchange add #4,sp ; pop args mov 8(fp),r0 ; reg <- opd 8$: ; mov (sp)+,r3 ; restore mov (sp)+,r2 ; restore mov (sp)+,fp ; restore frame pointer rts pc |
|
/* quick - quicksort a[lb..ub] */
void quick(a, lb, ub) int a[]; {
int k, partition();
if (lb >= ub)
return;
k = partition(a, lb, ub);
quick(a, lb, k - 1);
quick(a, k + 1, ub);
}
ARGI2 again working well (DEC and INC top of stack). |
.GLOBL quick .SBTTL quick quick: mov fp,-(sp) ; save frame pointer mov sp,fp mov r3,-(sp) ; save ; cmp 6(fp),8(fp) blt 21$ br 20$ 21$: mov 8(fp),-(sp) ; ARGI2 mov 6(fp),-(sp) ; ARGI2 mov 4(fp),-(sp) ; ARGP2 jsr pc,partition add #6,sp ; pop args mov r0,r3 ; LOADI2 mov r3,-(sp) dec (sp) ; ARGI2(SUBI1) mov 6(fp),-(sp) ; ARGI2 mov 4(fp),-(sp) ; ARGP2 jsr pc,quick add #6,sp ; pop args mov 8(fp),-(sp) ; ARGI2 mov r3,-(sp) inc (sp) ; ARGI2(ADDI1) mov 4(fp),-(sp) ; ARGP2 jsr pc,quick add #6,sp ; pop args 20$: ; mov (sp)+,r3 ; restore mov (sp)+,fp ; restore frame pointer rts pc |
|
/* sort - sort a[0..n-1] into increasing order */
void sort(a, n) int a[]; {
quick(a, 0, n-1);
}
|
.GLOBL sort .SBTTL sort sort: mov fp,-(sp) ; save frame pointer mov sp,fp ; mov 6(fp),-(sp) dec (sp) ; ARGI2(SUBI1) clr -(sp) ; ARGI2 mov 4(fp),-(sp) ; ARGP2 jsr pc,quick add #6,sp ; pop args 23$: ; mov (sp)+,fp ; restore frame pointer rts pc |
|
int main() {
int i;
sort(in, N);
for (i = 0; i < N; i++) {
putd(in[i]);
putchar(' ');
}
return 0;
}
|
.GLOBL main .SBTTL main main: mov r3,-(sp) ; save ; mov #10,-(sp) ; ARGI2 mov #in,-(sp) ; ARGP2 jsr pc,sort add #4,sp ; pop args clr r3 25$: mov r3,r4 asl r4 mov in (r4),-(sp) ; ARGI2 jsr pc,putd add #2,sp ; pop args mov #32,-(sp) ; ARGI2 jsr pc,putchar add #2,sp ; pop args 26$: inc r3 cmp r3, #10 blt 25$ clr r0 24$: ; mov (sp)+,r3 ; restore rts pc .END |
Assemble and list, link, and run above code.
.mac/list:tt1: sort
.MAIN. MACRO V05.03b 02:04
Table of contents
3- 18 EXCHANGE
3- 35 PUTU
3- 66 PUTD
3- 94 PARTITION
3- 162 QUICK
3- 197 SORT
3- 214 MAIN
...snip...
.MAIN. MACRO V05.03b 02:04 Page 3
1 000012 .RADIX 10
2 000005 FP=%5 ; R5 IS FRAME POINTER
3 .ENABL LSB ; FILE-WIDE LOCAL SYMBOLS
4
5 .GLOBL IN
6 000000 IN:
7 000000 000012 .WORD 10
8 000002 000040 .WORD 32
9 000004 177777 .WORD -1
10 000006 001067 .WORD 567
11 000010 000003 .WORD 3
12 000012 000022 .WORD 18
13 000014 000001 .WORD 1
14 000016 177715 .WORD -51
15 000020 001425 .WORD 789
16 000022 000000 .WORD 0
17 .GLOBL EXCHANGE
18 .SBTTL EXCHANGE
19 000024 EXCHANGE:
20 000024 010546 MOV FP,-(SP) ; SAVE FRAME POINTER
21 000026 010605 MOV SP,FP
22 000030 010346 MOV R3,-(SP) ; SAVE
23 ;
24 000032 016504 000004 MOV 4(FP),R4 ; REG <- OPD
25 000036 011403 MOV (R4),R3 ; REG <- OPD
26 000040 017514 000006 MOV @ 6(FP),(R4) ; ASGNI2
27 000044 010375 000006 MOV R3,@ 6(FP) ; ASGNI2
28 000050 1$:
29 ;
30 000050 012603 MOV (SP)+,R3 ; RESTORE
31 000052 012605 MOV (SP)+,FP ; RESTORE FRAME POINTER
32 000054 000207 RTS PC
33
34 .GLOBL PUTU
35 .SBTTL PUTU
36 000056 PUTU:
37 000056 010546 MOV FP,-(SP) ; SAVE FRAME POINTER
38 000060 010605 MOV SP,FP
39 000062 010346 MOV R3,-(SP) ; SAVE
40 ;
41 000064 016501 000004 MOV 4(FP),R1 ; REG <- OPD
42 000070 012700 000012 MOV #10,R0 ; REG <- OPD
43 000074 004767 000000G JSR PC,$DIVU ; DIVU2
44 000100 010003 MOV R0,R3 ; LOADU2
45 000102 005700 TST R0
46 000104 001405 BEQ 3$
47 000106 010346 MOV R3,-(SP) ; ARGU2
48 000110 004767 177742 JSR PC,PUTU
49 000114 062706 000002 ADD #2,SP ; POP ARGS
50 000120 3$:
51 000120 016501 000004 MOV 4(FP),R1 ; REG <- OPD
52 000124 012700 000012 MOV #10,R0 ; REG <- OPD
53 000130 004767 000000G JSR PC,$DIVU ; MODU2
54 000134 010104 MOV R1,R4
55 000136 062704 000060 ADD #48,R4
56 000142 110446 MOVB R4,-(SP) ; ARGI2(CVII2)
57 000144 004767 000000G JSR PC,PUTCHAR
.MAIN. MACRO V05.03b 02:04 Page 3-1
PUTU
58 000150 062706 000002 ADD #2,SP ; POP ARGS
59 000154 2$:
60 ;
61 000154 012603 MOV (SP)+,R3 ; RESTORE
62 000156 012605 MOV (SP)+,FP ; RESTORE FRAME POINTER
63 000160 000207 RTS PC
64
65 .GLOBL PUTD
66 .SBTTL PUTD
67 000162 PUTD:
68 000162 010546 MOV FP,-(SP) ; SAVE FRAME POINTER
69 000164 010605 MOV SP,FP
70 ;
71 000166 005765 000004 TST 4(FP)
72 000172 100017 BPL 6$
73 000174 012746 000055 MOV #45,-(SP) ; ARGI2
74 000200 004767 000000G JSR PC,PUTCHAR
75 000204 062706 000002 ADD #2,SP ; POP ARGS
76 000210 016504 000004 MOV 4(FP),R4 ; REG <- OPD
77 000214 005404 NEG R4
78 000216 010446 MOV R4,-(SP) ; ARGU2
79 000220 004767 177632 JSR PC,PUTU
80 000224 062706 000002 ADD #2,SP ; POP ARGS
81 000230 000407 BR 7$
82 000232 6$:
83 000232 016504 000004 MOV 4(FP),R4 ; REG <- OPD
84 000236 010446 MOV R4,-(SP) ; ARGU2
85 000240 004767 177612 JSR PC,PUTU
86 000244 062706 000002 ADD #2,SP ; POP ARGS
87 000250 7$:
88 000250 5$:
89 ;
90 000250 012605 MOV (SP)+,FP ; RESTORE FRAME POINTER
91 000252 000207 RTS PC
92
93 .GLOBL PARTITION
94 .SBTTL PARTITION
95 000254 PARTITION:
96 000254 010546 MOV FP,-(SP) ; SAVE FRAME POINTER
97 000256 010605 MOV SP,FP
98 000260 010246 MOV R2,-(SP) ; SAVE
99 000262 010346 MOV R3,-(SP) ; SAVE
100 ;
101 000264 005265 000010 INC 8(FP)
102 000270 016502 000006 MOV 6(FP),R2 ; REG <- OPD
103 000274 010204 MOV R2,R4
104 000276 006304 ASL R4
105 000300 066504 000004 ADD 4(FP),R4
106 000304 011403 MOV (R4),R3 ; REG <- OPD
107 000306 000446 BR 10$
108 000310 9$:
109 000310 12$:
110 000310 005265 000006 INC 6(FP)
111 000314 13$:
112 000314 016504 000006 MOV 6(FP),R4 ; REG <- OPD
113 000320 006304 ASL R4
114 000322 066504 000004 ADD 4(FP),R4
.MAIN. MACRO V05.03b 02:04 Page 3-2
PARTITION
115 000326 021403 CMP (R4),R3
116 000330 002767 BLT 12$
117 000332 15$:
118 000332 005365 000010 DEC 8(FP)
119 000336 16$:
120 000336 016504 000010 MOV 8(FP),R4 ; REG <- OPD
121 000342 006304 ASL R4
122 000344 066504 000004 ADD 4(FP),R4
123 000350 021403 CMP (R4),R3
124 000352 003367 BGT 15$
125 000354 026565 000006 000010 CMP 6(FP),8(FP)
126 000362 002020 BGE 18$
127 000364 016504 000004 MOV 4(FP),R4 ; REG <- OPD
128 000370 016501 000010 MOV 8(FP),R1 ; REG <- OPD
129 000374 006301 ASL R1
130 000376 010146 MOV R1,-(SP)
131 000400 060416 ADD R4,(SP) ; ARGP2(ADDP2)
132 000402 016501 000006 MOV 6(FP),R1 ; REG <- OPD
133 000406 006301 ASL R1
134 000410 010146 MOV R1,-(SP)
135 000412 060416 ADD R4,(SP) ; ARGP2(ADDP2)
136 000414 004767 177404 JSR PC,EXCHANGE
137 000420 062706 000004 ADD #4,SP ; POP ARGS
138 000424 18$:
139 000424 10$:
140 000424 026565 000006 000010 CMP 6(FP),8(FP)
141 000432 002726 BLT 9$
142 000434 016504 000004 MOV 4(FP),R4 ; REG <- OPD
143 000440 016501 000010 MOV 8(FP),R1 ; REG <- OPD
144 000444 006301 ASL R1
145 000446 010146 MOV R1,-(SP)
146 000450 060416 ADD R4,(SP) ; ARGP2(ADDP2)
147 000452 010201 MOV R2,R1
148 000454 006301 ASL R1
149 000456 010146 MOV R1,-(SP)
150 000460 060416 ADD R4,(SP) ; ARGP2(ADDP2)
151 000462 004767 177336 JSR PC,EXCHANGE
152 000466 062706 000004 ADD #4,SP ; POP ARGS
153 000472 016500 000010 MOV 8(FP),R0 ; REG <- OPD
154 000476 8$:
155 ;
156 000476 012603 MOV (SP)+,R3 ; RESTORE
157 000500 012602 MOV (SP)+,R2 ; RESTORE
158 000502 012605 MOV (SP)+,FP ; RESTORE FRAME POINTER
159 000504 000207 RTS PC
160
161 .GLOBL QUICK
162 .SBTTL QUICK
163 000506 QUICK:
164 000506 010546 MOV FP,-(SP) ; SAVE FRAME POINTER
165 000510 010605 MOV SP,FP
166 000512 010346 MOV R3,-(SP) ; SAVE
167 ;
168 000514 026565 000006 000010 CMP 6(FP),8(FP)
169 000522 002401 BLT 21$
170 000524 000437 BR 20$
171 000526 21$:
.MAIN. MACRO V05.03b 02:04 Page 3-3
QUICK
172 000526 016546 000010 MOV 8(FP),-(SP) ; ARGI2
173 000532 016546 000006 MOV 6(FP),-(SP) ; ARGI2
174 000536 016546 000004 MOV 4(FP),-(SP) ; ARGP2
175 000542 004767 177506 JSR PC,PARTITION
176 000546 062706 000006 ADD #6,SP ; POP ARGS
177 000552 010003 MOV R0,R3 ; LOADI2
178 000554 010346 MOV R3,-(SP)
179 000556 005316 DEC (SP) ; ARGI2(SUBI1)
180 000560 016546 000006 MOV 6(FP),-(SP) ; ARGI2
181 000564 016546 000004 MOV 4(FP),-(SP) ; ARGP2
182 000570 004767 177712 JSR PC,QUICK
183 000574 062706 000006 ADD #6,SP ; POP ARGS
184 000600 016546 000010 MOV 8(FP),-(SP) ; ARGI2
185 000604 010346 MOV R3,-(SP)
186 000606 005216 INC (SP) ; ARGI2(ADDI1)
187 000610 016546 000004 MOV 4(FP),-(SP) ; ARGP2
188 000614 004767 177666 JSR PC,QUICK
189 000620 062706 000006 ADD #6,SP ; POP ARGS
190 000624 20$:
191 ;
192 000624 012603 MOV (SP)+,R3 ; RESTORE
193 000626 012605 MOV (SP)+,FP ; RESTORE FRAME POINTER
194 000630 000207 RTS PC
195
196 .GLOBL SORT
197 .SBTTL SORT
198 000632 SORT:
199 000632 010546 MOV FP,-(SP) ; SAVE FRAME POINTER
200 000634 010605 MOV SP,FP
201 ;
202 000636 016546 000006 MOV 6(FP),-(SP)
203 000642 005316 DEC (SP) ; ARGI2(SUBI1)
204 000644 005046 CLR -(SP) ; ARGI2
205 000646 016546 000004 MOV 4(FP),-(SP) ; ARGP2
206 000652 004767 177630 JSR PC,QUICK
207 000656 062706 000006 ADD #6,SP ; POP ARGS
208 000662 23$:
209 ;
210 000662 012605 MOV (SP)+,FP ; RESTORE FRAME POINTER
211 000664 000207 RTS PC
212
213 .GLOBL MAIN
214 .SBTTL MAIN
215 000666 MAIN:
216 000666 010346 MOV R3,-(SP) ; SAVE
217 ;
218 000670 012746 000012 MOV #10,-(SP) ; ARGI2
219 000674 012746 000000' MOV #IN,-(SP) ; ARGP2
220 000700 004767 177726 JSR PC,SORT
221 000704 062706 000004 ADD #4,SP ; POP ARGS
222 000710 005003 CLR R3
223 000712 25$:
224 000712 010304 MOV R3,R4
225 000714 006304 ASL R4
226 000716 016446 000000' MOV IN (R4),-(SP) ; ARGI2
227 000722 004767 177234 JSR PC,PUTD
228 000726 062706 000002 ADD #2,SP ; POP ARGS
.MAIN. MACRO V05.03b 02:04 Page 3-4
MAIN
229 000732 012746 000040 MOV #32,-(SP) ; ARGI2
230 000736 004767 000000G JSR PC,PUTCHAR
231 000742 062706 000002 ADD #2,SP ; POP ARGS
232 000746 26$:
233 000746 005203 INC R3
234 000750 020327 000012 CMP R3, #10
235 000754 002756 BLT 25$
236 000756 005000 CLR R0
237 000760 24$:
238 ;
239 000760 012603 MOV (SP)+,R3 ; RESTORE
240 000762 000207 RTS PC
241
242 000001 .END
.MAIN. MACRO V05.03b 02:04 Page 3-5
Symbol table
EXCHAN 000024RG MAIN 000666RG PUTCHA= ****** GX PUTU 000056RG SORT 000632RG
FP =%000005 PARTIT 000254RG PUTD 000162RG QUICK 000506RG $DIVU = ****** GX
IN 000000RG
. ABS. 000000 000 (RW,I,GBL,ABS,OVR)
000764 001 (RW,I,LCL,REL,CON)
Errors detected: 0
*** Assembler statistics
Work file reads: 0
Work file writes: 0
Size of work file: 9202 Words ( 36 Pages)
Size of core pool: 13056 Words ( 51 Pages)
Operating system: RT-11
Elapsed time: 00:00:01.28
DK:SORT,TT1:SORT=DK:SORT
.link sort,lccrt
.sort
-51 -1 0 1 3 10 18 32 567 789
.