xref: /inferno-os/utils/tl/pass.c (revision 50b0dbb170df61467e42c7ea4deb0b5692d15f4c)
1 #include	"l.h"
2 
3 void
4 dodata(void)
5 {
6 	int i, t;
7 	Sym *s;
8 	Prog *p;
9 	long orig, v;
10 
11 	if(debug['v'])
12 		Bprint(&bso, "%5.2f dodata\n", cputime());
13 	Bflush(&bso);
14 	for(p = datap; p != P; p = p->link) {
15 		s = p->from.sym;
16 		if(p->as == ADYNT || p->as == AINIT)
17 			s->value = dtype;
18 		if(s->type == SBSS)
19 			s->type = SDATA;
20 		if(s->type != SDATA)
21 			diag("initialize non-data (%d): %s\n%P",
22 				s->type, s->name, p);
23 		v = p->from.offset + p->reg;
24 		if(v > s->value)
25 			diag("initialize bounds (%ld): %s\n%P",
26 				s->value, s->name, p);
27 		if((s->type == SBSS || s->type == SDATA) && (p->to.type == D_CONST || p->to.type == D_OCONST) && (p->to.name == D_EXTERN || p->to.name == D_STATIC)){
28 			s = p->to.sym;
29 			if(s != S && (s->type == STEXT || s->type == SLEAF || s->type == SCONST || s->type == SXREF))
30 				s->fnptr = 1;
31 		}
32 	}
33 
34 	if(debug['t']) {
35 		/*
36 		 * pull out string constants
37 		 */
38 		for(p = datap; p != P; p = p->link) {
39 			s = p->from.sym;
40 			if(p->to.type == D_SCONST)
41 				s->type = SSTRING;
42 		}
43 	}
44 
45 	/*
46 	 * pass 1
47 	 *	assign 'small' variables to data segment
48 	 *	(rational is that data segment is more easily
49 	 *	 addressed through offset on R12)
50 	 */
51 	orig = 0;
52 	for(i=0; i<NHASH; i++)
53 	for(s = hash[i]; s != S; s = s->link) {
54 		t = s->type;
55 		if(t != SDATA && t != SBSS)
56 			continue;
57 		v = s->value;
58 		if(v == 0) {
59 			diag("%s: no size", s->name);
60 			v = 1;
61 		}
62 		while(v & 3)
63 			v++;
64 		s->value = v;
65 		if(v > MINSIZ)
66 			continue;
67 		s->value = orig;
68 		orig += v;
69 		s->type = SDATA1;
70 	}
71 
72 	/*
73 	 * pass 2
74 	 *	assign large 'data' variables to data segment
75 	 */
76 	for(i=0; i<NHASH; i++)
77 	for(s = hash[i]; s != S; s = s->link) {
78 		t = s->type;
79 		if(t != SDATA) {
80 			if(t == SDATA1)
81 				s->type = SDATA;
82 			continue;
83 		}
84 		v = s->value;
85 		s->value = orig;
86 		orig += v;
87 	}
88 
89 	while(orig & 7)
90 		orig++;
91 	datsize = orig;
92 
93 	/*
94 	 * pass 3
95 	 *	everything else to bss segment
96 	 */
97 	for(i=0; i<NHASH; i++)
98 	for(s = hash[i]; s != S; s = s->link) {
99 		if(s->type != SBSS)
100 			continue;
101 		v = s->value;
102 		s->value = orig;
103 		orig += v;
104 	}
105 	while(orig & 7)
106 		orig++;
107 	bsssize = orig-datsize;
108 
109 	xdefine("setR12", SDATA, 0L+BIG);
110 	xdefine("bdata", SDATA, 0L);
111 	xdefine("edata", SDATA, datsize);
112 	xdefine("end", SBSS, datsize+bsssize);
113 	xdefine("etext", STEXT, 0L);
114 }
115 
116 void
117 undef(void)
118 {
119 	int i;
120 	Sym *s;
121 
122 	for(i=0; i<NHASH; i++)
123 	for(s = hash[i]; s != S; s = s->link)
124 		if(s->type == SXREF)
125 			diag("%s: not defined", s->name);
126 }
127 
128 Prog*
129 brchain(Prog *p)
130 {
131 	int i;
132 
133 	for(i=0; i<20; i++) {
134 		if(p == P || p->as != AB)
135 			return p;
136 		p = p->cond;
137 	}
138 	return P;
139 }
140 
141 int
142 relinv(int a)
143 {
144 	switch(a) {
145 	case ABEQ:	return ABNE;
146 	case ABNE:	return ABEQ;
147 	case ABCS:	return ABCC;
148 	case ABHS:	return ABLO;
149 	case ABCC:	return ABCS;
150 	case ABLO:	return ABHS;
151 	case ABMI:	return ABPL;
152 	case ABPL:	return ABMI;
153 	case ABVS:	return ABVC;
154 	case ABVC:	return ABVS;
155 	case ABHI:	return ABLS;
156 	case ABLS:	return ABHI;
157 	case ABGE:	return ABLT;
158 	case ABLT:	return ABGE;
159 	case ABGT:	return ABLE;
160 	case ABLE:	return ABGT;
161 	}
162 	diag("unknown relation: %s", anames[a]);
163 	return a;
164 }
165 
166 void
167 follow(void)
168 {
169 	if(debug['v'])
170 		Bprint(&bso, "%5.2f follow\n", cputime());
171 	Bflush(&bso);
172 
173 	firstp = prg();
174 	lastp = firstp;
175 	xfol(textp);
176 
177 	firstp = firstp->link;
178 	lastp->link = P;
179 }
180 
181 void
182 xfol(Prog *p)
183 {
184 	Prog *q, *r;
185 	int a, i;
186 
187 loop:
188 	if(p == P)
189 		return;
190 	setarch(p);
191 	a = p->as;
192 	if(a == ATEXT)
193 		curtext = p;
194 	if(a == AB) {
195 		q = p->cond;
196 		if(q != P) {
197 			p->mark |= FOLL;
198 			p = q;
199 			if(!(p->mark & FOLL))
200 				goto loop;
201 		}
202 	}
203 	if(p->mark & FOLL) {
204 		for(i=0,q=p; i<4; i++,q=q->link) {
205 			if(q == lastp)
206 				break;
207 			a = q->as;
208 			if(a == ANOP) {
209 				i--;
210 				continue;
211 			}
212 			if(a == AB || (a == ARET && q->scond == 14) || a == ARFE)
213 				goto copy;
214 			if(!q->cond || (q->cond->mark&FOLL))
215 				continue;
216 			if(a != ABEQ && a != ABNE)
217 				continue;
218 		copy:
219 			for(;;) {
220 				r = prg();
221 				*r = *p;
222 				if(!(r->mark&FOLL))
223 					print("cant happen 1\n");
224 				r->mark |= FOLL;
225 				if(p != q) {
226 					p = p->link;
227 					lastp->link = r;
228 					lastp = r;
229 					continue;
230 				}
231 				lastp->link = r;
232 				lastp = r;
233 				if(a == AB || (a == ARET && q->scond == 14) || a == ARFE)
234 					return;
235 				r->as = ABNE;
236 				if(a == ABNE)
237 					r->as = ABEQ;
238 				r->cond = p->link;
239 				r->link = p->cond;
240 				if(!(r->link->mark&FOLL))
241 					xfol(r->link);
242 				if(!(r->cond->mark&FOLL))
243 					print("cant happen 2\n");
244 				return;
245 			}
246 		}
247 		a = AB;
248 		q = prg();
249 		q->as = a;
250 		q->line = p->line;
251 		q->to.type = D_BRANCH;
252 		q->to.offset = p->pc;
253 		q->cond = p;
254 		p = q;
255 	}
256 	p->mark |= FOLL;
257 	lastp->link = p;
258 	lastp = p;
259 	if(a == AB || (a == ARET && p->scond == 14) || a == ARFE){
260 		return;
261 	}
262 	if(p->cond != P)
263 	if(a != ABL && a != ABX && p->link != P) {
264 		q = brchain(p->link);
265 		if(a != ATEXT && a != ABCASE)
266 		if(q != P && (q->mark&FOLL)) {
267 			p->as = relinv(a);
268 			p->link = p->cond;
269 			p->cond = q;
270 		}
271 		xfol(p->link);
272 		q = brchain(p->cond);
273 		if(q == P)
274 			q = p->cond;
275 		if(q->mark&FOLL) {
276 			p->cond = q;
277 			return;
278 		}
279 		p = q;
280 		goto loop;
281 	}
282 	p = p->link;
283 	goto loop;
284 }
285 
286 void
287 patch(void)
288 {
289 	long c, vexit;
290 	Prog *p, *q;
291 	Sym *s, *s1;
292 	int a;
293 
294 	if(debug['v'])
295 		Bprint(&bso, "%5.2f patch\n", cputime());
296 	Bflush(&bso);
297 	mkfwd();
298 	s = lookup("exit", 0);
299 	vexit = s->value;
300 	for(p = firstp; p != P; p = p->link) {
301 		setarch(p);
302 		a = p->as;
303 		if(a == ATEXT)
304 			curtext = p;
305 		if(seenthumb && a == ABL){
306 			// if((s = p->to.sym) != S && (s1 = curtext->from.sym) != S)
307 			//	print("%s calls %s\n", s1->name, s->name);
308 			 if((s = p->to.sym) != S && (s1 = curtext->from.sym) != S && s->thumb != s1->thumb)
309 				s->foreign = 1;
310 		}
311 		if((a == ABL || a == ABX || a == AB || a == ARET) &&
312 		   p->to.type != D_BRANCH && p->to.sym != S) {
313 			s = p->to.sym;
314 			switch(s->type) {
315 			default:
316 				diag("undefined: %s\n%P", s->name, p);
317 				s->type = STEXT;
318 				s->value = vexit;
319 				break;
320 			case STEXT:
321 				p->to.offset = s->value;
322 				p->to.type = D_BRANCH;
323 				break;
324 			case SUNDEF:
325 				if(p->as != ABL)
326 					diag("help: SUNDEF in AB || ARET");
327 				p->to.offset = 0;
328 				p->to.type = D_BRANCH;
329 				p->cond = UP;
330 				break;
331 			}
332 		}
333 		if(p->to.type != D_BRANCH || p->cond == UP)
334 			continue;
335 		c = p->to.offset;
336 		for(q = firstp; q != P;) {
337 			if(q->forwd != P)
338 			if(c >= q->forwd->pc) {
339 				q = q->forwd;
340 				continue;
341 			}
342 			if(c == q->pc)
343 				break;
344 			q = q->link;
345 		}
346 		if(q == P) {
347 			diag("branch out of range %ld\n%P", c, p);
348 			p->to.type = D_NONE;
349 		}
350 		p->cond = q;
351 	}
352 
353 	for(p = firstp; p != P; p = p->link) {
354 		setarch(p);
355 		a = p->as;
356 		if(p->as == ATEXT)
357 			curtext = p;
358 		if(seenthumb && a == ABL) {
359 #ifdef CALLEEBX
360 			if(0)
361 				{}
362 #else
363 			if((s = p->to.sym) != S && (s->foreign || s->fnptr))
364 				p->as = ABX;
365 #endif
366 			else if(p->to.type == D_OREG)
367 				p->as = ABX;
368 		}
369 		if(p->cond != P && p->cond != UP) {
370 			p->cond = brloop(p->cond);
371 			if(p->cond != P)
372 			if(p->to.type == D_BRANCH)
373 				p->to.offset = p->cond->pc;
374 		}
375 	}
376 }
377 
378 #define	LOG	5
379 void
380 mkfwd(void)
381 {
382 	Prog *p;
383 	long dwn[LOG], cnt[LOG], i;
384 	Prog *lst[LOG];
385 
386 	for(i=0; i<LOG; i++) {
387 		if(i == 0)
388 			cnt[i] = 1; else
389 			cnt[i] = LOG * cnt[i-1];
390 		dwn[i] = 1;
391 		lst[i] = P;
392 	}
393 	i = 0;
394 	for(p = firstp; p != P; p = p->link) {
395 		if(p->as == ATEXT)
396 			curtext = p;
397 		i--;
398 		if(i < 0)
399 			i = LOG-1;
400 		p->forwd = P;
401 		dwn[i]--;
402 		if(dwn[i] <= 0) {
403 			dwn[i] = cnt[i];
404 			if(lst[i] != P)
405 				lst[i]->forwd = p;
406 			lst[i] = p;
407 		}
408 	}
409 }
410 
411 Prog*
412 brloop(Prog *p)
413 {
414 	Prog *q;
415 	int c;
416 
417 	for(c=0; p!=P;) {
418 		if(p->as != AB)
419 			return p;
420 		q = p->cond;
421 		if(q <= p) {
422 			c++;
423 			if(q == p || c > 5000)
424 				break;
425 		}
426 		p = q;
427 	}
428 	return P;
429 }
430 
431 long
432 atolwhex(char *s)
433 {
434 	long n;
435 	int f;
436 
437 	n = 0;
438 	f = 0;
439 	while(*s == ' ' || *s == '\t')
440 		s++;
441 	if(*s == '-' || *s == '+') {
442 		if(*s++ == '-')
443 			f = 1;
444 		while(*s == ' ' || *s == '\t')
445 			s++;
446 	}
447 	if(s[0]=='0' && s[1]){
448 		if(s[1]=='x' || s[1]=='X'){
449 			s += 2;
450 			for(;;){
451 				if(*s >= '0' && *s <= '9')
452 					n = n*16 + *s++ - '0';
453 				else if(*s >= 'a' && *s <= 'f')
454 					n = n*16 + *s++ - 'a' + 10;
455 				else if(*s >= 'A' && *s <= 'F')
456 					n = n*16 + *s++ - 'A' + 10;
457 				else
458 					break;
459 			}
460 		} else
461 			while(*s >= '0' && *s <= '7')
462 				n = n*8 + *s++ - '0';
463 	} else
464 		while(*s >= '0' && *s <= '9')
465 			n = n*10 + *s++ - '0';
466 	if(f)
467 		n = -n;
468 	return n;
469 }
470 
471 long
472 rnd(long v, long r)
473 {
474 	long c;
475 
476 	if(r <= 0)
477 		return v;
478 	v += r - 1;
479 	c = v % r;
480 	if(c < 0)
481 		c += r;
482 	v -= c;
483 	return v;
484 }
485 
486 #define Reachable(n)	if((s = lookup(n, 0)) != nil) s->used++
487 
488 static void
489 rused(Adr *a)
490 {
491 	Sym *s = a->sym;
492 
493 	if(s == S)
494 		return;
495 	if(a->type == D_OREG || a->type == D_OCONST || a->type == D_CONST){
496 		if(a->name == D_EXTERN || a->name == D_STATIC){
497 			if(s->used == 0)
498 				s->used = 1;
499 		}
500 	}
501 	else if(a->type == D_BRANCH){
502 		if(s->used == 0)
503 			s->used = 1;
504 	}
505 }
506 
507 void
508 reachable()
509 {
510 	Prog *p, *prev, *prevt, *nextt, *q;
511 	Sym *s, *s0;
512 	int i, todo;
513 	char *a;
514 
515 	Reachable("_div");
516 	Reachable("_divu");
517 	Reachable("_mod");
518 	Reachable("_modu");
519 	a = INITENTRY;
520 	if(*a >= '0' && *a <= '9')
521 		return;
522 	s = lookup(a, 0);
523 	if(s == nil)
524 		return;
525 	if(s->type == 0){
526 		s->used = 1;	// to stop asm complaining
527 		for(p = firstp; p != P && p->as != ATEXT; p = p->link)
528 			;
529 		if(p == nil)
530 			return;
531 		s = p->from.sym;
532 	}
533 	s->used = 1;
534 	do{
535 		todo = 0;
536 		for(p = firstp; p != P; p = p->link){
537 			if(p->as == ATEXT && (s0 = p->from.sym)->used == 1){
538 				todo = 1;
539 				for(q = p->link; q != P && q->as != ATEXT; q = q->link){
540 					rused(&q->from);
541 					rused(&q->to);
542 				}
543 				s0->used = 2;
544 			}
545 		}
546 		for(p = datap; p != P; p = p->link){
547 			if((s0 = p->from.sym)->used == 1){
548 				todo = 1;
549 				for(q = p; q != P; q = q->link){	// data can be scattered
550 					if(q->from.sym == s0)
551 						rused(&q->to);
552 				}
553 				s0->used = 2;
554 			}
555 		}
556 	}while(todo);
557 	prev = nil;
558 	prevt = nextt = nil;
559 	for(p = firstp; p != P; ){
560 		if(p->as == ATEXT){
561 			prevt = nextt;
562 			nextt = p;
563 		}
564 		if(p->as == ATEXT && (s0 = p->from.sym)->used == 0){
565 			s0->type = SREMOVED;
566 			for(q = p->link; q != P && q->as != ATEXT; q = q->link)
567 				;
568 			if(q != p->cond)
569 				diag("bad ptr in reachable()");
570 			if(prev == nil)
571 				firstp = q;
572 			else
573 				prev->link = q;
574 			if(q == nil)
575 				lastp = prev;
576 			if(prevt == nil)
577 				textp = q;
578 			else
579 				prevt->cond = q;
580 			if(q == nil)
581 				etextp = prevt;
582 			nextt = prevt;
583 			if(debug['V'])
584 				print("%s unused\n", s0->name);
585 			p = q;
586 		}
587 		else{
588 			prev = p;
589 			p = p->link;
590 		}
591 	}
592 	prevt = nil;
593 	for(p = datap; p != nil; ){
594 		if((s0 = p->from.sym)->used == 0){
595 			s0->type = SREMOVED;
596 			prev = prevt;
597 			for(q = p; q != nil; q = q->link){
598 				if(q->from.sym == s0){
599 					if(prev == nil)
600 						datap = q->link;
601 					else
602 						prev->link = q->link;
603 				}
604 				else
605 					prev = q;
606 			}
607 			if(debug['V'])
608 				print("%s unused (data)\n", s0->name);
609 			p = prevt->link;
610 		}
611 		else{
612 			prevt = p;
613 			p = p->link;
614 		}
615 	}
616 	for(i=0; i<NHASH; i++){
617 		for(s = hash[i]; s != S; s = s->link){
618 			if(s->used == 0)
619 				s->type = SREMOVED;
620 		}
621 	}
622 }
623 
624 static void
625 fused(Adr *a, Prog *p, Prog *ct)
626 {
627 	Sym *s = a->sym;
628 	Use *u;
629 
630 	if(s == S)
631 		return;
632 	if(a->type == D_OREG || a->type == D_OCONST || a->type == D_CONST){
633 		if(a->name == D_EXTERN || a->name == D_STATIC){
634 			u = malloc(sizeof(Use));
635 			u->p = p;
636 			u->ct = ct;
637 			u->link = s->use;
638 			s->use = u;
639 		}
640 	}
641 	else if(a->type == D_BRANCH){
642 		u = malloc(sizeof(Use));
643 		u->p = p;
644 		u->ct = ct;
645 		u->link = s->use;
646 		s->use = u;
647 	}
648 }
649 
650 static int
651 ckfpuse(Prog *p, Prog *ct, Sym *fp, Sym *r)
652 {
653 	int reg;
654 
655 	USED(fp);
656 	USED(ct);
657 	if(p->from.sym == r && p->as == AMOVW && (p->from.type == D_CONST || p->from.type == D_OREG) && p->reg == NREG && p->to.type == D_REG){
658 		reg = p->to.reg;
659 		for(p = p->link; p != P && p->as != ATEXT; p = p->link){
660 			if((p->as == ABL || p->as == ABX) && p->to.type == D_OREG && p->to.reg == reg)
661 				return 1;
662 			if(!debug['F'] && (isbranch(p) || p->as == ARET)){
663 				// print("%s: branch %P in %s\n", fp->name, p, ct->from.sym->name);
664 				return 0;
665 			}
666 			if((p->from.type == D_REG || p->from.type == D_OREG) && p->from.reg == reg){
667 				if(!debug['F'] && p->to.type != D_REG){
668 					// print("%s: store %P in %s\n", fp->name, p, ct->from.sym->name);
669 					return 0;
670 				}
671 				reg = p->to.reg;
672 			}
673 		}
674 	}
675 	// print("%s: no MOVW O(R), R\n", fp->name);
676 	return debug['F'];
677 }
678 
679 static void
680 setfpuse(Prog *p, Sym *fp, Sym *r)
681 {
682 	int reg;
683 
684 	if(p->from.sym == r && p->as == AMOVW && (p->from.type == D_CONST || p->from.type == D_OREG) && p->reg == NREG && p->to.type == D_REG){
685 		reg = p->to.reg;
686 		for(p = p->link; p != P && p->as != ATEXT; p = p->link){
687 			if((p->as == ABL || p->as == ABX) && p->to.type == D_OREG && p->to.reg == reg){
688 				fp->fnptr = 0;
689 				p->as = ABL;	// safe to do so
690 // print("simplified %s call\n", fp->name);
691 				break;
692 			}
693 			if(!debug['F'] && (isbranch(p) || p->as == ARET))
694 				diag("bad setfpuse call");
695 			if((p->from.type == D_REG || p->from.type == D_OREG) && p->from.reg == reg){
696 				if(!debug['F'] && p->to.type != D_REG)
697 					diag("bad setfpuse call");
698 				reg = p->to.reg;
699 			}
700 		}
701 	}
702 }
703 
704 static int
705 cksymuse(Sym *s, int t)
706 {
707 	Prog *p;
708 
709 	for(p = datap; p != P; p = p->link){
710 		if(p->from.sym == s && p->to.sym != nil && strcmp(p->to.sym->name, ".string") != 0 && p->to.sym->thumb != t){
711 			// print("%s %s %d %d ", p->from.sym->name, p->to.sym->name, p->to.sym->thumb, t);
712 			return 0;
713 		}
714 	}
715 	return 1;
716 }
717 
718 /* check the use of s at the given point */
719 static int
720 ckuse(Sym *s, Sym *s0, Use *u)
721 {
722 	Sym *s1;
723 
724 	s1 = u->p->from.sym;
725 // print("ckuse %s %s %s\n", s->name, s0->name, s1 ? s1->name : "nil");
726 	if(u->ct == nil){	/* in data area */
727 		if(s0 == s && !cksymuse(s1, s0->thumb)){
728 			// print("%s: cksymuse fails\n", s0->name);
729 			return 0;
730 		}
731 		for(u = s1->use; u != U; u = u->link)
732 			if(!ckuse(s1, s0, u))
733 				return 0;
734 	}
735 	else{		/* in text area */
736 		if(u->ct->from.sym->thumb != s0->thumb){
737 			// print("%s(%d): foreign call %s(%d)\n", s0->name, s0->thumb, u->ct->from.sym->name, u->ct->from.sym->thumb);
738 			return 0;
739 		}
740 		return ckfpuse(u->p, u->ct, s0, s);
741 	}
742 	return 1;
743 }
744 
745 static void
746 setuse(Sym *s, Sym *s0, Use *u)
747 {
748 	Sym *s1;
749 
750 	s1 = u->p->from.sym;
751 	if(u->ct == nil){	/* in data area */
752 		for(u = s1->use; u != U; u = u->link)
753 			setuse(s1, s0, u);
754 	}
755 	else{		/* in text area */
756 		setfpuse(u->p, s0, s);
757 	}
758 }
759 
760 /* detect BX O(R) which can be done as BL O(R) */
761 void
762 fnptrs()
763 {
764 	int i;
765 	Sym *s;
766 	Prog *p;
767 	Use *u;
768 
769 	for(i=0; i<NHASH; i++){
770 		for(s = hash[i]; s != S; s = s->link){
771 			if(s->fnptr && (s->type == STEXT || s->type == SLEAF || s->type == SCONST)){
772 				// print("%s : fnptr %d %d\n", s->name, s->thumb, s->foreign);
773 			}
774 		}
775 	}
776 	/* record use of syms */
777 	for(p = firstp; p != P; p = p->link){
778 		if(p->as == ATEXT)
779 			curtext = p;
780 		else{
781 			fused(&p->from, p, curtext);
782 			fused(&p->to, p, curtext);
783 		}
784 	}
785 	for(p = datap; p != P; p = p->link)
786 		fused(&p->to, p, nil);
787 
788 	/* now look for fn ptrs */
789 	for(i=0; i<NHASH; i++){
790 		for(s = hash[i]; s != S; s = s->link){
791 			if(s->fnptr && (s->type == STEXT || s->type == SLEAF || s->type == SCONST)){
792 				for(u = s->use; u != U; u = u->link){
793 					if(!ckuse(s, s, u))
794 						break;
795 				}
796 				if(u == U){		// can simplify
797 					for(u = s->use; u != U; u = u->link)
798 						setuse(s, s, u);
799 				}
800 			}
801 		}
802 	}
803 
804 	/*  now free Use structures */
805 }
806 
807 void
808 import(void)
809 {
810 	int i;
811 	Sym *s;
812 
813 	for(i = 0; i < NHASH; i++)
814 		for(s = hash[i]; s != S; s = s->link)
815 			if(s->sig != 0 && s->type == SXREF && (nimports == 0 || s->subtype == SIMPORT)){
816 				undefsym(s);
817 				Bprint(&bso, "IMPORT: %s sig=%lux v=%ld\n", s->name, s->sig, s->value);
818 			}
819 }
820 
821 void
822 ckoff(Sym *s, long v)
823 {
824 	if(v < 0 || v >= 1<<Roffset)
825 		diag("relocation offset %ld for %s out of range", v, s->name);
826 }
827 
828 static Prog*
829 newdata(Sym *s, int o, int w, int t)
830 {
831 	Prog *p;
832 
833 	p = prg();
834 	p->link = datap;
835 	datap = p;
836 	p->as = ADATA;
837 	p->reg = w;
838 	p->from.type = D_OREG;
839 	p->from.name = t;
840 	p->from.sym = s;
841 	p->from.offset = o;
842 	p->to.type = D_CONST;
843 	p->to.name = D_NONE;
844 	return p;
845 }
846 
847 void
848 export(void)
849 {
850 	int i, j, n, off, nb, sv, ne;
851 	Sym *s, *et, *str, **esyms;
852 	Prog *p;
853 	char buf[NSNAME], *t;
854 
855 	n = 0;
856 	for(i = 0; i < NHASH; i++)
857 		for(s = hash[i]; s != S; s = s->link)
858 			if(s->sig != 0 && s->type != SXREF && s->type != SUNDEF && (nexports == 0 || s->subtype == SEXPORT))
859 				n++;
860 	esyms = malloc(n*sizeof(Sym*));
861 	ne = n;
862 	n = 0;
863 	for(i = 0; i < NHASH; i++)
864 		for(s = hash[i]; s != S; s = s->link)
865 			if(s->sig != 0 && s->type != SXREF && s->type != SUNDEF && (nexports == 0 || s->subtype == SEXPORT))
866 				esyms[n++] = s;
867 	for(i = 0; i < ne-1; i++)
868 		for(j = i+1; j < ne; j++)
869 			if(strcmp(esyms[i]->name, esyms[j]->name) > 0){
870 				s = esyms[i];
871 				esyms[i] = esyms[j];
872 				esyms[j] = s;
873 			}
874 
875 	nb = 0;
876 	off = 0;
877 	et = lookup(EXPTAB, 0);
878 	if(et->type != 0 && et->type != SXREF)
879 		diag("%s already defined", EXPTAB);
880 	et->type = SDATA;
881 	str = lookup(".string", 0);
882 	if(str->type == 0)
883 		str->type = SDATA;
884 	sv = str->value;
885 	for(i = 0; i < ne; i++){
886 		s = esyms[i];
887 		Bprint(&bso, "EXPORT: %s sig=%lux t=%d\n", s->name, s->sig, s->type);
888 
889 		/* signature */
890 		p = newdata(et, off, sizeof(long), D_EXTERN);
891 		off += sizeof(long);
892 		p->to.offset = s->sig;
893 
894 		/* address */
895 		p = newdata(et, off, sizeof(long), D_EXTERN);
896 		off += sizeof(long);
897 		p->to.name = D_EXTERN;
898 		p->to.sym = s;
899 
900 		/* string */
901 		t = s->name;
902 		n = strlen(t)+1;
903 		for(;;){
904 			buf[nb++] = *t;
905 			sv++;
906 			if(nb >= NSNAME){
907 				p = newdata(str, sv-NSNAME, NSNAME, D_STATIC);
908 				p->to.type = D_SCONST;
909 				p->to.sval = malloc(NSNAME);
910 				memmove(p->to.sval, buf, NSNAME);
911 				nb = 0;
912 			}
913 			if(*t++ == 0)
914 				break;
915 		}
916 
917 		/* name */
918 		p = newdata(et, off, sizeof(long), D_EXTERN);
919 		off += sizeof(long);
920 		p->to.name = D_STATIC;
921 		p->to.sym = str;
922 		p->to.offset = sv-n;
923 	}
924 
925 	if(nb > 0){
926 		p = newdata(str, sv-nb, nb, D_STATIC);
927 		p->to.type = D_SCONST;
928 		p->to.sval = malloc(NSNAME);
929 		memmove(p->to.sval, buf, nb);
930 	}
931 
932 	for(i = 0; i < 3; i++){
933 		newdata(et, off, sizeof(long), D_EXTERN);
934 		off += sizeof(long);
935 	}
936 	et->value = off;
937 	if(sv == 0)
938 		sv = 1;
939 	str->value = sv;
940 	exports = ne;
941 	free(esyms);
942 }
943