1f8f0c3f2Sralph #ifndef lint
2*10bf529aSdonn static char *sccsid ="@(#)code.c 1.10 (Berkeley) 05/31/88";
3f8f0c3f2Sralph #endif lint
4f8f0c3f2Sralph
51854df5cSralph # include "pass1.h"
6d28c766eSlinton # include <sys/types.h>
7d28c766eSlinton # include <a.out.h>
8d28c766eSlinton # include <stab.h>
9d28c766eSlinton
10d28c766eSlinton int proflg = 0; /* are we generating profiling code? */
11d28c766eSlinton int strftn = 0; /* is the current function one which returns a value */
12d28c766eSlinton int gdebug;
13d28c766eSlinton int fdefflag; /* are we within a function definition ? */
148f17cd74Sdonn #ifndef STABDOT
15d28c766eSlinton char NULLNAME[8];
168f17cd74Sdonn #endif
17d28c766eSlinton int labelno;
18d28c766eSlinton
19c0436b9cSmckusick # define putstr(s) fputs((s), stdout)
20c0436b9cSmckusick
branch(n)21d28c766eSlinton branch( n ){
22d28c766eSlinton /* output a branch to label n */
23d28c766eSlinton /* exception is an ordinary function branching to retlab: then, return */
24e535b582Sdonn if( nerrors ) return;
25d28c766eSlinton if( n == retlab && !strftn ){
26c0436b9cSmckusick putstr( " ret\n" );
27d28c766eSlinton }
28d28c766eSlinton else printf( " jbr L%d\n", n );
29d28c766eSlinton }
30d28c766eSlinton
31d28c766eSlinton int lastloc = { -1 };
32d28c766eSlinton
33d28c766eSlinton short log2tab[] = {0, 0, 1, 2, 2, 3, 3, 3, 3};
34d28c766eSlinton #define LOG2SZ 9
35d28c766eSlinton
defalign(n)36d28c766eSlinton defalign(n) {
37d28c766eSlinton /* cause the alignment to become a multiple of n */
38d28c766eSlinton n /= SZCHAR;
39d28c766eSlinton if( lastloc != PROG && n > 1 ) printf( " .align %d\n", n >= 0 && n < LOG2SZ ? log2tab[n] : 0 );
40d28c766eSlinton }
41d28c766eSlinton
locctr(l)42d28c766eSlinton locctr( l ){
43d28c766eSlinton register temp;
44d28c766eSlinton /* l is PROG, ADATA, DATA, STRNG, ISTRNG, or STAB */
45d28c766eSlinton
46d28c766eSlinton if( l == lastloc ) return(l);
47d28c766eSlinton temp = lastloc;
48d28c766eSlinton lastloc = l;
49e535b582Sdonn if( nerrors ) return(temp);
50d28c766eSlinton switch( l ){
51d28c766eSlinton
52d28c766eSlinton case PROG:
53c0436b9cSmckusick putstr( " .text\n" );
54d28c766eSlinton psline();
55d28c766eSlinton break;
56d28c766eSlinton
57d28c766eSlinton case DATA:
58d28c766eSlinton case ADATA:
59c0436b9cSmckusick putstr( " .data\n" );
60d28c766eSlinton break;
61d28c766eSlinton
62d28c766eSlinton case STRNG:
63c0436b9cSmckusick putstr( " .data 1\n" );
64d28c766eSlinton break;
65d28c766eSlinton
66d28c766eSlinton case ISTRNG:
67c0436b9cSmckusick putstr( " .data 2\n" );
68d28c766eSlinton break;
69d28c766eSlinton
70d28c766eSlinton case STAB:
71c0436b9cSmckusick putstr( " .stab\n" );
72d28c766eSlinton break;
73d28c766eSlinton
74d28c766eSlinton default:
75d28c766eSlinton cerror( "illegal location counter" );
76d28c766eSlinton }
77d28c766eSlinton
78d28c766eSlinton return( temp );
79d28c766eSlinton }
80d28c766eSlinton
deflab(n)81d28c766eSlinton deflab( n ){
82d28c766eSlinton /* output something to define the current position as label n */
83*10bf529aSdonn if (nerrors) return;
84d28c766eSlinton printf( "L%d:\n", n );
85d28c766eSlinton }
86d28c766eSlinton
87d28c766eSlinton int crslab = 10;
88d28c766eSlinton
getlab()89d28c766eSlinton getlab(){
90d28c766eSlinton /* return a number usable for a label */
91d28c766eSlinton return( ++crslab );
92d28c766eSlinton }
93d28c766eSlinton
94d28c766eSlinton
95d28c766eSlinton int ent_mask[] = {
96d28c766eSlinton 0,0,0,0,0, 0xfc0, 0xf80, 0xf00, 0xe00, 0xc00, 0x800, 0};
97d28c766eSlinton
98d28c766eSlinton int reg_use = 11;
99d28c766eSlinton
efcode()100d28c766eSlinton efcode(){
101d28c766eSlinton /* code for the end of a function */
102d28c766eSlinton
103d28c766eSlinton if( strftn ){ /* copy output (in R2) to caller */
104d28c766eSlinton register NODE *l, *r;
105d28c766eSlinton register struct symtab *p;
106d28c766eSlinton register TWORD t;
107d28c766eSlinton int i;
108d28c766eSlinton
109d28c766eSlinton p = &stab[curftn];
110d28c766eSlinton t = p->stype;
111d28c766eSlinton t = DECREF(t);
112d28c766eSlinton
113d28c766eSlinton deflab( retlab );
114d28c766eSlinton
115d28c766eSlinton i = getlab(); /* label for return area */
116d28c766eSlinton #ifndef LCOMM
117c0436b9cSmckusick putstr(" .data\n" );
118c0436b9cSmckusick putstr(" .align 2\n" );
119d28c766eSlinton printf("L%d: .space %d\n", i, tsize(t, p->dimoff, p->sizoff)/SZCHAR );
120c0436b9cSmckusick putstr(" .text\n" );
121d28c766eSlinton #else
122d28c766eSlinton { int sz = tsize(t, p->dimoff, p->sizoff) / SZCHAR;
123f14878d2Sdonn if (sz % (SZINT/SZCHAR))
124f14878d2Sdonn sz += (SZINT/SZCHAR) - (sz % (SZINT/SZCHAR));
125d28c766eSlinton printf(" .lcomm L%d,%d\n", i, sz);
126d28c766eSlinton }
127d28c766eSlinton #endif
128d28c766eSlinton psline();
129d28c766eSlinton printf(" movab L%d,r1\n", i);
130d28c766eSlinton
131d28c766eSlinton reached = 1;
132d28c766eSlinton l = block( REG, NIL, NIL, PTR|t, p->dimoff, p->sizoff );
133d28c766eSlinton l->tn.rval = 1; /* R1 */
134d28c766eSlinton l->tn.lval = 0; /* no offset */
135d28c766eSlinton r = block( REG, NIL, NIL, PTR|t, p->dimoff, p->sizoff );
136d28c766eSlinton r->tn.rval = 0; /* R0 */
137d28c766eSlinton r->tn.lval = 0;
138d28c766eSlinton l = buildtree( UNARY MUL, l, NIL );
139d28c766eSlinton r = buildtree( UNARY MUL, r, NIL );
140d28c766eSlinton l = buildtree( ASSIGN, l, r );
141d28c766eSlinton l->in.op = FREE;
142d28c766eSlinton ecomp( l->in.left );
143d28c766eSlinton printf( " movab L%d,r0\n", i );
144d28c766eSlinton /* turn off strftn flag, so return sequence will be generated */
145d28c766eSlinton strftn = 0;
146d28c766eSlinton }
147d28c766eSlinton branch( retlab );
148d28c766eSlinton #ifndef VMS
149d28c766eSlinton printf( " .set L%d,0x%x\n", ftnno, ent_mask[reg_use] );
150d28c766eSlinton #else
151d28c766eSlinton printf( " .set L%d,%d # Hex = 0x%x\n", ftnno, 0x3c| ent_mask[reg_use], ent_mask[reg_use] );
152d28c766eSlinton /* KLS kludge, under VMS if you use regs 2-5, you must save them. */
153d28c766eSlinton #endif
154d28c766eSlinton reg_use = 11;
155d28c766eSlinton p2bend();
156d28c766eSlinton fdefflag = 0;
157d28c766eSlinton }
158d28c766eSlinton
159d28c766eSlinton int ftlab1, ftlab2;
160d28c766eSlinton
bfcode(a,n)161d28c766eSlinton bfcode( a, n ) int a[]; {
162d28c766eSlinton /* code for the beginning of a function; a is an array of
163d28c766eSlinton indices in stab for the arguments; n is the number */
164d28c766eSlinton register i;
165d28c766eSlinton register temp;
166d28c766eSlinton register struct symtab *p;
167d28c766eSlinton int off;
168f14878d2Sdonn #ifdef TRUST_REG_CHAR_AND_REG_SHORT
169d28c766eSlinton char *toreg();
170f14878d2Sdonn #endif
171d28c766eSlinton
172e535b582Sdonn if( nerrors ) return;
1738f17cd74Sdonn (void) locctr( PROG );
174d28c766eSlinton p = &stab[curftn];
175c0436b9cSmckusick putstr( " .align 1\n");
176d28c766eSlinton defnam( p );
177d28c766eSlinton temp = p->stype;
178d28c766eSlinton temp = DECREF(temp);
179d28c766eSlinton strftn = (temp==STRTY) || (temp==UNIONTY);
180d28c766eSlinton
181d28c766eSlinton retlab = getlab();
182d28c766eSlinton
183d28c766eSlinton /* routine prolog */
184d28c766eSlinton
185d28c766eSlinton printf( " .word L%d\n", ftnno);
186d28c766eSlinton ftlab1 = getlab();
187d28c766eSlinton ftlab2 = getlab();
188d28c766eSlinton printf( " jbr L%d\n", ftlab1);
189d28c766eSlinton printf( "L%d:\n", ftlab2);
190d28c766eSlinton if( proflg ) { /* profile code */
191d28c766eSlinton i = getlab();
192d28c766eSlinton printf(" movab L%d,r0\n", i);
193c0436b9cSmckusick putstr(" jsb mcount\n");
194c0436b9cSmckusick putstr(" .data\n");
195c0436b9cSmckusick putstr(" .align 2\n");
196d28c766eSlinton printf("L%d: .long 0\n", i);
197c0436b9cSmckusick putstr(" .text\n");
198d28c766eSlinton psline();
199d28c766eSlinton }
200d28c766eSlinton
201d28c766eSlinton off = ARGINIT;
202d28c766eSlinton
203d28c766eSlinton for( i=0; i<n; ++i ){
204d28c766eSlinton p = &stab[a[i]];
205d28c766eSlinton if( p->sclass == REGISTER ){
206d28c766eSlinton temp = p->offset; /* save register number */
207d28c766eSlinton p->sclass = PARAM; /* forget that it is a register */
208d28c766eSlinton p->offset = NOOFFSET;
2098f17cd74Sdonn (void) oalloc( p, &off );
210f14878d2Sdonn #ifdef TRUST_REG_CHAR_AND_REG_SHORT /* and reg double */
211d28c766eSlinton /*tbl*/ printf( " %s %d(ap),r%d\n", toreg(p->stype), p->offset/SZCHAR, temp );
212f14878d2Sdonn #else
213f14878d2Sdonn /*tbl*/ printf( " movl %d(ap),r%d\n", p->offset/SZCHAR, temp );
214f14878d2Sdonn #endif
215d28c766eSlinton p->offset = temp; /* remember register number */
216d28c766eSlinton p->sclass = REGISTER; /* remember that it is a register */
217d28c766eSlinton }
218d28c766eSlinton else if( p->stype == STRTY || p->stype == UNIONTY ) {
219d28c766eSlinton p->offset = NOOFFSET;
220d28c766eSlinton if( oalloc( p, &off ) ) cerror( "bad argument" );
221d28c766eSlinton SETOFF( off, ALSTACK );
222d28c766eSlinton }
223d28c766eSlinton else {
224d28c766eSlinton if( oalloc( p, &off ) ) cerror( "bad argument" );
225d28c766eSlinton }
226d28c766eSlinton
227d28c766eSlinton }
228e535b582Sdonn if (gdebug && !nerrors) {
2295e08cd5cSsam #ifdef STABDOT
2305e08cd5cSsam pstabdot(N_SLINE, lineno);
2315e08cd5cSsam #else
2325e08cd5cSsam pstab(NULLNAME, N_SLINE);
2335e08cd5cSsam printf("0,%d,LL%d\n", lineno, labelno);
2345e08cd5cSsam printf("LL%d:\n", labelno++);
2355e08cd5cSsam #endif
2365e08cd5cSsam }
237d28c766eSlinton fdefflag = 1;
238d28c766eSlinton }
239d28c766eSlinton
bccode()240d28c766eSlinton bccode(){ /* called just before the first executable statment */
241d28c766eSlinton /* by now, the automatics and register variables are allocated */
242d28c766eSlinton SETOFF( autooff, SZINT );
243d28c766eSlinton /* set aside store area offset */
244d28c766eSlinton p2bbeg( autooff, regvar );
245d28c766eSlinton reg_use = (reg_use > regvar ? regvar : reg_use);
246d28c766eSlinton }
247d28c766eSlinton
248b89c02b0Sdonn /*ARGSUSED*/
ejobcode(flag)249d28c766eSlinton ejobcode( flag ){
250d28c766eSlinton /* called just before final exit */
251d28c766eSlinton /* flag is 1 if errors, 0 if none */
252d28c766eSlinton }
253d28c766eSlinton
254e535b582Sdonn #ifndef aobeg
aobeg()255d28c766eSlinton aobeg(){
256d28c766eSlinton /* called before removing automatics from stab */
257d28c766eSlinton }
258e535b582Sdonn #endif aobeg
259d28c766eSlinton
260e535b582Sdonn #ifndef aocode
261b89c02b0Sdonn /*ARGSUSED*/
262d28c766eSlinton aocode(p) struct symtab *p; {
263d28c766eSlinton /* called when automatic p removed from stab */
264d28c766eSlinton }
265e535b582Sdonn #endif aocode
266d28c766eSlinton
267e535b582Sdonn #ifndef aoend
aoend()268d28c766eSlinton aoend(){
269d28c766eSlinton /* called after removing all automatics from stab */
270d28c766eSlinton }
271e535b582Sdonn #endif aoend
272d28c766eSlinton
defnam(p)273d28c766eSlinton defnam( p ) register struct symtab *p; {
274d28c766eSlinton /* define the current location as the name p->sname */
275d28c766eSlinton
276d28c766eSlinton if( p->sclass == EXTDEF ){
277d28c766eSlinton printf( " .globl %s\n", exname( p->sname ) );
278d28c766eSlinton }
279d28c766eSlinton if( p->sclass == STATIC && p->slevel>1 ) deflab( p->offset );
280d28c766eSlinton else printf( "%s:\n", exname( p->sname ) );
281d28c766eSlinton
282d28c766eSlinton }
283d28c766eSlinton
bycode(t,i)284d28c766eSlinton bycode( t, i ){
285d28c766eSlinton #ifdef ASSTRINGS
286d28c766eSlinton static int lastoctal = 0;
287d28c766eSlinton #endif
288d28c766eSlinton
289d28c766eSlinton /* put byte i+1 in a string */
290d28c766eSlinton
291e535b582Sdonn if ( nerrors ) return;
292d28c766eSlinton #ifdef ASSTRINGS
293d28c766eSlinton
294d28c766eSlinton i &= 077;
295d28c766eSlinton if ( t < 0 ){
296c0436b9cSmckusick if ( i != 0 ) putstr( "\"\n" );
297d28c766eSlinton } else {
298c0436b9cSmckusick if ( i == 0 ) putstr("\t.ascii\t\"");
299d28c766eSlinton if ( t == '\\' || t == '"'){
300d28c766eSlinton lastoctal = 0;
301d28c766eSlinton printf("\\%c", t);
302d28c766eSlinton }
303d28c766eSlinton /*
304d28c766eSlinton * We escape the colon in strings so that
305d28c766eSlinton * c2 will, in its infinite wisdom, interpret
306d28c766eSlinton * the characters preceding the colon as a label.
307d28c766eSlinton * If we didn't escape the colon, c2 would
308d28c766eSlinton * throw away any trailing blanks or tabs after
309d28c766eSlinton * the colon, but reconstruct a assembly
310d28c766eSlinton * language semantically correct program.
311d28c766eSlinton * C2 hasn't been taught about strings.
312d28c766eSlinton */
313d28c766eSlinton else if ( t == ':' || t < 040 || t >= 0177 ){
314d28c766eSlinton lastoctal++;
315d28c766eSlinton printf("\\%o",t);
316d28c766eSlinton }
317d28c766eSlinton else if ( lastoctal && '0' <= t && t <= '9' ){
318d28c766eSlinton lastoctal = 0;
319d28c766eSlinton printf("\"\n\t.ascii\t\"%c", t );
320d28c766eSlinton }
321d28c766eSlinton else
322d28c766eSlinton {
323d28c766eSlinton lastoctal = 0;
324d28c766eSlinton putchar(t);
325d28c766eSlinton }
326c0436b9cSmckusick if ( i == 077 ) putstr("\"\n");
327d28c766eSlinton }
328d28c766eSlinton #else
329d28c766eSlinton
330d28c766eSlinton i &= 07;
331d28c766eSlinton if( t < 0 ){ /* end of the string */
332c0436b9cSmckusick if( i != 0 ) putchar( '\n' );
333d28c766eSlinton }
334d28c766eSlinton
335d28c766eSlinton else { /* stash byte t into string */
336c0436b9cSmckusick if( i == 0 ) putstr( " .byte " );
337c0436b9cSmckusick else putchar( ',' );
338d28c766eSlinton printf( "0x%x", t );
339c0436b9cSmckusick if( i == 07 ) putchar( '\n' );
340d28c766eSlinton }
341d28c766eSlinton #endif
342d28c766eSlinton }
343d28c766eSlinton
zecode(n)344d28c766eSlinton zecode( n ){
345d28c766eSlinton /* n integer words of zeros */
346d28c766eSlinton OFFSZ temp;
347d28c766eSlinton if( n <= 0 ) return;
348d28c766eSlinton printf( " .space %d\n", (SZINT/SZCHAR)*n );
349d28c766eSlinton temp = n;
350d28c766eSlinton inoff += temp*SZINT;
351d28c766eSlinton }
352d28c766eSlinton
353b89c02b0Sdonn /*ARGSUSED*/
fldal(t)354d28c766eSlinton fldal( t ) unsigned t; { /* return the alignment of field of type t */
355d28c766eSlinton uerror( "illegal field type" );
356d28c766eSlinton return( ALINT );
357d28c766eSlinton }
358d28c766eSlinton
359b89c02b0Sdonn /*ARGSUSED*/
360d28c766eSlinton fldty( p ) struct symtab *p; { /* fix up type of field p */
361d28c766eSlinton ;
362d28c766eSlinton }
363d28c766eSlinton
364b89c02b0Sdonn /*ARGSUSED*/
where(c)365d28c766eSlinton where(c){ /* print location of error */
366d28c766eSlinton /* c is either 'u', 'c', or 'w' */
367d28c766eSlinton /* GCOS version */
368d28c766eSlinton fprintf( stderr, "%s, line %d: ", ftitle, lineno );
369d28c766eSlinton }
370d28c766eSlinton
371d28c766eSlinton
372f14878d2Sdonn #ifdef TRUST_REG_CHAR_AND_REG_SHORT
373d28c766eSlinton /* tbl - toreg() returns a pointer to a char string
374d28c766eSlinton which is the correct "register move" for the passed type
375d28c766eSlinton */
376d28c766eSlinton struct type_move {TWORD fromtype; char tostrng[8];} toreg_strs[] =
377d28c766eSlinton {
378f14878d2Sdonn INT, "movl",
379f14878d2Sdonn UNSIGNED, "movl",
380f14878d2Sdonn DOUBLE, "movq",
381d28c766eSlinton CHAR, "cvtbl",
382d28c766eSlinton SHORT, "cvtwl",
383d28c766eSlinton UCHAR, "movzbl",
384d28c766eSlinton USHORT, "movzwl",
385f8f0c3f2Sralph 0, ""
386d28c766eSlinton };
387d28c766eSlinton
388d28c766eSlinton char
toreg(type)389d28c766eSlinton *toreg(type)
390d28c766eSlinton TWORD type;
391d28c766eSlinton {
392d28c766eSlinton struct type_move *p;
393d28c766eSlinton
394f8f0c3f2Sralph for ( p=toreg_strs; p->fromtype != 0; p++)
395d28c766eSlinton if (p->fromtype == type) return(p->tostrng);
396d28c766eSlinton
397d28c766eSlinton /* type not found, must be a pointer type */
398d28c766eSlinton return("movl");
399d28c766eSlinton }
400d28c766eSlinton /* tbl */
401f14878d2Sdonn #endif
402d28c766eSlinton
403d28c766eSlinton
main(argc,argv)404d28c766eSlinton main( argc, argv ) char *argv[]; {
405d28c766eSlinton #ifdef BUFSTDERR
406d28c766eSlinton char errbuf[BUFSIZ];
407d28c766eSlinton setbuf(stderr, errbuf);
408d28c766eSlinton #endif
409d28c766eSlinton return(mainp1( argc, argv ));
410d28c766eSlinton }
411d28c766eSlinton
412d28c766eSlinton struct sw heapsw[SWITSZ]; /* heap for switches */
413d28c766eSlinton
genswitch(p,n)414d28c766eSlinton genswitch(p,n) register struct sw *p;{
415d28c766eSlinton /* p points to an array of structures, each consisting
416d28c766eSlinton of a constant value and a label.
417d28c766eSlinton The first is >=0 if there is a default label;
418d28c766eSlinton its value is the label number
419d28c766eSlinton The entries p[1] to p[n] are the nontrivial cases
420d28c766eSlinton */
421d28c766eSlinton register i;
422d28c766eSlinton register CONSZ j, range;
423d28c766eSlinton register dlab, swlab;
424d28c766eSlinton
425e535b582Sdonn if( nerrors ) return;
426d28c766eSlinton range = p[n].sval-p[1].sval;
427d28c766eSlinton
428d28c766eSlinton if( range>0 && range <= 3*n && n>=4 ){ /* implement a direct switch */
429d28c766eSlinton
430d28c766eSlinton swlab = getlab();
431d28c766eSlinton dlab = p->slab >= 0 ? p->slab : getlab();
432d28c766eSlinton
433d28c766eSlinton /* already in r0 */
434d28c766eSlinton printf(" casel r0,$%ld,$%ld\n", p[1].sval, range);
435d28c766eSlinton printf("L%d:\n", swlab);
436d28c766eSlinton for( i=1,j=p[1].sval; i<=n; j++) {
437d28c766eSlinton printf(" .word L%d-L%d\n", (j == p[i].sval ? ((j=p[i++].sval), p[i-1].slab) : dlab),
438d28c766eSlinton swlab);
439d28c766eSlinton }
440d28c766eSlinton
441d28c766eSlinton if( p->slab >= 0 ) branch( dlab );
442d28c766eSlinton else printf("L%d:\n", dlab);
443d28c766eSlinton return;
444d28c766eSlinton
445d28c766eSlinton }
446d28c766eSlinton
447d28c766eSlinton if( n>8 ) { /* heap switch */
448d28c766eSlinton
449d28c766eSlinton heapsw[0].slab = dlab = p->slab >= 0 ? p->slab : getlab();
450d28c766eSlinton makeheap(p, n, 1); /* build heap */
451d28c766eSlinton
452d28c766eSlinton walkheap(1, n); /* produce code */
453d28c766eSlinton
454d28c766eSlinton if( p->slab >= 0 )
455d28c766eSlinton branch( dlab );
456d28c766eSlinton else
457d28c766eSlinton printf("L%d:\n", dlab);
458d28c766eSlinton return;
459d28c766eSlinton }
460d28c766eSlinton
461d28c766eSlinton /* debugging code */
462d28c766eSlinton
463d28c766eSlinton /* out for the moment
464d28c766eSlinton if( n >= 4 ) werror( "inefficient switch: %d, %d", n, (int) (range/n) );
465d28c766eSlinton */
466d28c766eSlinton
467d28c766eSlinton /* simple switch code */
468d28c766eSlinton
469d28c766eSlinton for( i=1; i<=n; ++i ){
470d28c766eSlinton /* already in r0 */
471d28c766eSlinton
472c0436b9cSmckusick putstr( " cmpl r0,$" );
473d28c766eSlinton printf( CONFMT, p[i].sval );
474d28c766eSlinton printf( "\n jeql L%d\n", p[i].slab );
475d28c766eSlinton }
476d28c766eSlinton
477d28c766eSlinton if( p->slab>=0 ) branch( p->slab );
478d28c766eSlinton }
479d28c766eSlinton
makeheap(p,m,n)480d28c766eSlinton makeheap(p, m, n)
481d28c766eSlinton register struct sw *p;
482d28c766eSlinton {
483d28c766eSlinton register int q;
484d28c766eSlinton
4858f17cd74Sdonn q = selectheap(m);
486d28c766eSlinton heapsw[n] = p[q];
487d28c766eSlinton if( q>1 ) makeheap(p, q-1, 2*n);
488d28c766eSlinton if( q<m ) makeheap(p+q, m-q, 2*n+1);
489d28c766eSlinton }
490d28c766eSlinton
selectheap(m)4918f17cd74Sdonn selectheap(m) {
492d28c766eSlinton register int l,i,k;
493d28c766eSlinton
494d28c766eSlinton for(i=1; ; i*=2)
495d28c766eSlinton if( (i-1) > m ) break;
496d28c766eSlinton l = ((k = i/2 - 1) + 1)/2;
497d28c766eSlinton return( l + (m-k < l ? m-k : l));
498d28c766eSlinton }
499d28c766eSlinton
walkheap(start,limit)500d28c766eSlinton walkheap(start, limit)
501d28c766eSlinton {
502d28c766eSlinton int label;
503d28c766eSlinton
504d28c766eSlinton
505d28c766eSlinton if( start > limit ) return;
506d28c766eSlinton printf(" cmpl r0,$%d\n", heapsw[start].sval);
507d28c766eSlinton printf(" jeql L%d\n", heapsw[start].slab);
508d28c766eSlinton if( (2*start) > limit ) {
509d28c766eSlinton printf(" jbr L%d\n", heapsw[0].slab);
510d28c766eSlinton return;
511d28c766eSlinton }
512d28c766eSlinton if( (2*start+1) <= limit ) {
513d28c766eSlinton label = getlab();
514d28c766eSlinton printf(" jgtr L%d\n", label);
515d28c766eSlinton } else
516d28c766eSlinton printf(" jgtr L%d\n", heapsw[0].slab);
517d28c766eSlinton walkheap( 2*start, limit);
518d28c766eSlinton if( (2*start+1) <= limit ) {
519d28c766eSlinton printf("L%d:\n", label);
520d28c766eSlinton walkheap( 2*start+1, limit);
521d28c766eSlinton }
522d28c766eSlinton }
523