1 #include "l.h"
2
3 void
dodata(void)4 dodata(void)
5 {
6 int i, t;
7 Sym *s;
8 Prog *p, *p1;
9 vlong orig, orig1, 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 (%lld): %s\n%P",
26 s->value, s->name, p);
27 }
28
29 /*
30 * pass 1
31 * assign 'small' variables to data segment
32 * (rational is that data segment is more easily
33 * addressed through offset on REGSB)
34 */
35 orig = 0;
36 for(i=0; i<NHASH; i++)
37 for(s = hash[i]; s != S; s = s->link) {
38 t = s->type;
39 if(t != SDATA && t != SBSS)
40 continue;
41 v = s->value;
42 if(v == 0) {
43 diag("%s: no size", s->name);
44 v = 1;
45 }
46 v = rnd(v, 4);
47 s->value = v;
48 if(v > MINSIZ)
49 continue;
50 if(v >= 8)
51 orig = rnd(orig, 8);
52 s->value = orig;
53 orig += v;
54 s->type = SDATA1;
55 }
56 orig1 = orig;
57
58 /*
59 * pass 2
60 * assign 'data' variables to data segment
61 */
62 for(i=0; i<NHASH; i++)
63 for(s = hash[i]; s != S; s = s->link) {
64 t = s->type;
65 if(t != SDATA) {
66 if(t == SDATA1)
67 s->type = SDATA;
68 continue;
69 }
70 v = s->value;
71 if(v >= 8)
72 orig = rnd(orig, 8);
73 s->value = orig;
74 orig += v;
75 s->type = SDATA1;
76 }
77
78 if(orig)
79 orig = rnd(orig, 8);
80 datsize = orig;
81
82 /*
83 * pass 3
84 * everything else to bss segment
85 */
86 for(i=0; i<NHASH; i++)
87 for(s = hash[i]; s != S; s = s->link) {
88 if(s->type != SBSS)
89 continue;
90 v = s->value;
91 if(v >= 8)
92 orig = rnd(orig, 8);
93 s->value = orig;
94 orig += v;
95 }
96 if(orig)
97 orig = rnd(orig, 8);
98 bsssize = orig-datsize;
99
100 /*
101 * pass 4
102 * add literals to all large values.
103 * at this time:
104 * small data is allocated DATA
105 * large data is allocated DATA1
106 * large bss is allocated BSS
107 * the new literals are loaded between
108 * small data and large data.
109 */
110 orig = 0;
111 for(p = firstp; p != P; p = p->link) {
112 if(p->as != AMOVW)
113 continue;
114 if(p->from.type != D_CONST)
115 continue;
116 if(s = p->from.sym) {
117 t = s->type;
118 if(t != SDATA && t != SDATA1 && t != SBSS)
119 continue;
120 t = p->from.name;
121 if(t != D_EXTERN && t != D_STATIC)
122 continue;
123 v = s->value + p->from.offset;
124 if(v >= 0 && v <= 0xffff)
125 continue;
126 if(!strcmp(s->name, "setSB"))
127 continue;
128 /* size should be 19 max */
129 if(strlen(s->name) >= 10) /* has loader address */
130 sprint(literal, "$%p.%llux", s, p->from.offset);
131 else
132 sprint(literal, "$%s.%d.%llux", s->name, s->version, p->from.offset);
133 } else {
134 if(p->from.name != D_NONE)
135 continue;
136 if(p->from.reg != NREG)
137 continue;
138 v = p->from.offset;
139 if(v >= -0x7fff-1 && v <= 0x7fff)
140 continue;
141 if(!(v & 0xffff))
142 continue;
143 if(v)
144 continue; /* quicker to build it than load it */
145 /* size should be 9 max */
146 sprint(literal, "$%llux", v);
147 }
148 s = lookup(literal, 0);
149 if(s->type == 0) {
150 s->type = SDATA;
151 s->value = orig1+orig;
152 orig += 4;
153 p1 = prg();
154 p1->as = ADATA;
155 p1->line = p->line;
156 p1->from.type = D_OREG;
157 p1->from.sym = s;
158 p1->from.name = D_EXTERN;
159 p1->reg = 4;
160 p1->to = p->from;
161 p1->link = datap;
162 datap = p1;
163 }
164 if(s->type != SDATA)
165 diag("literal not data: %s", s->name);
166 p->from.type = D_OREG;
167 p->from.sym = s;
168 p->from.name = D_EXTERN;
169 p->from.offset = 0;
170 continue;
171 }
172 while(orig & 7)
173 orig++;
174 /*
175 * pass 5
176 * re-adjust offsets
177 */
178 for(i=0; i<NHASH; i++)
179 for(s = hash[i]; s != S; s = s->link) {
180 t = s->type;
181 if(t == SBSS) {
182 s->value += orig;
183 continue;
184 }
185 if(t == SDATA1) {
186 s->type = SDATA;
187 s->value += orig;
188 continue;
189 }
190 }
191 datsize += orig;
192 xdefine("setSB", SDATA, 0+BIG);
193 xdefine("bdata", SDATA, 0);
194 xdefine("edata", SDATA, datsize);
195 xdefine("end", SBSS, datsize+bsssize);
196 xdefine("etext", STEXT, 0);
197 }
198
199 void
undef(void)200 undef(void)
201 {
202 int i;
203 Sym *s;
204
205 for(i=0; i<NHASH; i++)
206 for(s = hash[i]; s != S; s = s->link)
207 if(s->type == SXREF)
208 diag("%s: not defined", s->name);
209 }
210
211 int
relinv(int a)212 relinv(int a)
213 {
214
215 switch(a) {
216 case ABEQ: return ABNE;
217 case ABNE: return ABEQ;
218
219 case ABGE: return ABLT;
220 case ABLT: return ABGE;
221
222 case ABGT: return ABLE;
223 case ABLE: return ABGT;
224
225 case ABVC: return ABVS;
226 case ABVS: return ABVC;
227 }
228 return 0;
229 }
230
231 void
follow(void)232 follow(void)
233 {
234
235 if(debug['v'])
236 Bprint(&bso, "%5.2f follow\n", cputime());
237 Bflush(&bso);
238
239 firstp = prg();
240 lastp = firstp;
241
242 xfol(textp);
243
244 firstp = firstp->link;
245 lastp->link = P;
246 }
247
248 void
xfol(Prog * p)249 xfol(Prog *p)
250 {
251 Prog *q, *r;
252 int a, b, i;
253
254 loop:
255 if(p == P)
256 return;
257 a = p->as;
258 if(a == ATEXT)
259 curtext = p;
260 if(a == ABR) {
261 q = p->cond;
262 if((p->mark&NOSCHED) || q && (q->mark&NOSCHED)){
263 p->mark |= FOLL;
264 lastp->link = p;
265 lastp = p;
266 p = p->link;
267 xfol(p);
268 p = q;
269 if(p && !(p->mark & FOLL))
270 goto loop;
271 return;
272 }
273 if(q != P) {
274 p->mark |= FOLL;
275 p = q;
276 if(!(p->mark & FOLL))
277 goto loop;
278 }
279 }
280 if(p->mark & FOLL) {
281 for(i=0,q=p; i<4; i++,q=q->link) {
282 if(q == lastp || (q->mark&NOSCHED))
283 break;
284 b = 0; /* set */
285 a = q->as;
286 if(a == ANOP) {
287 i--;
288 continue;
289 }
290 if(a == ABR || a == ARETURN || a == ARFI || a == ARFCI || a == ARFID || a == AHRFID)
291 goto copy;
292 if(!q->cond || (q->cond->mark&FOLL))
293 continue;
294 b = relinv(a);
295 if(!b)
296 continue;
297 copy:
298 for(;;) {
299 r = prg();
300 *r = *p;
301 if(!(r->mark&FOLL))
302 print("cant happen 1\n");
303 r->mark |= FOLL;
304 if(p != q) {
305 p = p->link;
306 lastp->link = r;
307 lastp = r;
308 continue;
309 }
310 lastp->link = r;
311 lastp = r;
312 if(a == ABR || a == ARETURN || a == ARFI || a == ARFCI || a == ARFID || a == AHRFID)
313 return;
314 r->as = b;
315 r->cond = p->link;
316 r->link = p->cond;
317 if(!(r->link->mark&FOLL))
318 xfol(r->link);
319 if(!(r->cond->mark&FOLL))
320 print("cant happen 2\n");
321 return;
322 }
323 }
324
325 a = ABR;
326 q = prg();
327 q->as = a;
328 q->line = p->line;
329 q->to.type = D_BRANCH;
330 q->to.offset = p->pc;
331 q->cond = p;
332 p = q;
333 }
334 p->mark |= FOLL;
335 lastp->link = p;
336 lastp = p;
337 if(a == ABR || a == ARETURN || a == ARFI || a == ARFCI || a == ARFID || a == AHRFID){
338 if(p->mark & NOSCHED){
339 p = p->link;
340 goto loop;
341 }
342 return;
343 }
344 if(p->cond != P)
345 if(a != ABL && p->link != P) {
346 xfol(p->link);
347 p = p->cond;
348 if(p == P || (p->mark&FOLL))
349 return;
350 goto loop;
351 }
352 p = p->link;
353 goto loop;
354 }
355
356 void
patch(void)357 patch(void)
358 {
359 long c;
360 Prog *p, *q;
361 Sym *s;
362 int a;
363 vlong vexit;
364
365 if(debug['v'])
366 Bprint(&bso, "%5.2f patch\n", cputime());
367 Bflush(&bso);
368 mkfwd();
369 s = lookup("exit", 0);
370 vexit = s->value;
371 for(p = firstp; p != P; p = p->link) {
372 a = p->as;
373 if(a == ATEXT)
374 curtext = p;
375 if((a == ABL || a == ARETURN) && p->to.sym != S) {
376 s = p->to.sym;
377 if(s->type != STEXT && s->type != SUNDEF) {
378 diag("undefined: %s\n%P", s->name, p);
379 s->type = STEXT;
380 s->value = vexit;
381 }
382 if(s->type == SUNDEF){
383 p->to.offset = 0;
384 p->cond = UP;
385 }
386 else
387 p->to.offset = s->value;
388 p->to.type = D_BRANCH;
389 }
390 if(p->to.type != D_BRANCH || p->cond == UP)
391 continue;
392 c = p->to.offset;
393 for(q = firstp; q != P;) {
394 if(q->forwd != P)
395 if(c >= q->forwd->pc) {
396 q = q->forwd;
397 continue;
398 }
399 if(c == q->pc)
400 break;
401 q = q->link;
402 }
403 if(q == P) {
404 diag("branch out of range %ld\n%P", c, p);
405 p->to.type = D_NONE;
406 }
407 p->cond = q;
408 }
409
410 for(p = firstp; p != P; p = p->link) {
411 if(p->as == ATEXT)
412 curtext = p;
413 p->mark = 0; /* initialization for follow */
414 if(p->cond != P && p->cond != UP) {
415 p->cond = brloop(p->cond);
416 if(p->cond != P)
417 if(p->to.type == D_BRANCH)
418 p->to.offset = p->cond->pc;
419 }
420 }
421 }
422
423 #define LOG 5
424 void
mkfwd(void)425 mkfwd(void)
426 {
427 Prog *p;
428 long dwn[LOG], cnt[LOG], i;
429 Prog *lst[LOG];
430
431 for(i=0; i<LOG; i++) {
432 if(i == 0)
433 cnt[i] = 1; else
434 cnt[i] = LOG * cnt[i-1];
435 dwn[i] = 1;
436 lst[i] = P;
437 }
438 i = 0;
439 for(p = firstp; p != P; p = p->link) {
440 if(p->as == ATEXT)
441 curtext = p;
442 i--;
443 if(i < 0)
444 i = LOG-1;
445 p->forwd = P;
446 dwn[i]--;
447 if(dwn[i] <= 0) {
448 dwn[i] = cnt[i];
449 if(lst[i] != P)
450 lst[i]->forwd = p;
451 lst[i] = p;
452 }
453 }
454 }
455
456 Prog*
brloop(Prog * p)457 brloop(Prog *p)
458 {
459 Prog *q;
460 int c;
461
462 for(c=0; p!=P;) {
463 if(p->as != ABR || (p->mark&NOSCHED))
464 return p;
465 q = p->cond;
466 if(q <= p) {
467 c++;
468 if(q == p || c > 5000)
469 break;
470 }
471 p = q;
472 }
473 return P;
474 }
475
476 vlong
atolwhex(char * s)477 atolwhex(char *s)
478 {
479 vlong n;
480 int f;
481
482 n = 0;
483 f = 0;
484 while(*s == ' ' || *s == '\t')
485 s++;
486 if(*s == '-' || *s == '+') {
487 if(*s++ == '-')
488 f = 1;
489 while(*s == ' ' || *s == '\t')
490 s++;
491 }
492 if(s[0]=='0' && s[1]){
493 if(s[1]=='x' || s[1]=='X'){
494 s += 2;
495 for(;;){
496 if(*s >= '0' && *s <= '9')
497 n = n*16 + *s++ - '0';
498 else if(*s >= 'a' && *s <= 'f')
499 n = n*16 + *s++ - 'a' + 10;
500 else if(*s >= 'A' && *s <= 'F')
501 n = n*16 + *s++ - 'A' + 10;
502 else
503 break;
504 }
505 } else
506 while(*s >= '0' && *s <= '7')
507 n = n*8 + *s++ - '0';
508 } else
509 while(*s >= '0' && *s <= '9')
510 n = n*10 + *s++ - '0';
511 if(f)
512 n = -n;
513 return n;
514 }
515
516 vlong
rnd(vlong v,long r)517 rnd(vlong v, long r)
518 {
519 vlong c;
520
521 if(r <= 0)
522 return v;
523 v += r - 1;
524 c = v % r;
525 if(c < 0)
526 c += r;
527 v -= c;
528 return v;
529 }
530
531 void
import(void)532 import(void)
533 {
534 int i;
535 Sym *s;
536
537 for(i = 0; i < NHASH; i++)
538 for(s = hash[i]; s != S; s = s->link)
539 if(s->sig != 0 && s->type == SXREF && (nimports == 0 || s->subtype == SIMPORT)){
540 undefsym(s);
541 Bprint(&bso, "IMPORT: %s sig=%lux v=%lld\n", s->name, s->sig, s->value);
542 if(debug['S'])
543 s->sig = 0;
544 }
545 }
546
547 void
ckoff(Sym * s,vlong v)548 ckoff(Sym *s, vlong v)
549 {
550 if(v < 0 || v >= 1<<Roffset)
551 diag("relocation offset %lld for %s out of range", v, s->name);
552 }
553
554 static Prog*
newdata(Sym * s,int o,int w,int t)555 newdata(Sym *s, int o, int w, int t)
556 {
557 Prog *p;
558
559 p = prg();
560 p->link = datap;
561 datap = p;
562 p->as = ADATA;
563 p->reg = w;
564 p->from.type = D_OREG;
565 p->from.name = t;
566 p->from.sym = s;
567 p->from.offset = o;
568 p->to.type = D_CONST;
569 p->to.name = D_NONE;
570 return p;
571 }
572
573 void
export(void)574 export(void)
575 {
576 int i, j, n, off, nb, sv, ne;
577 Sym *s, *et, *str, **esyms;
578 Prog *p;
579 char buf[NSNAME], *t;
580
581 n = 0;
582 for(i = 0; i < NHASH; i++)
583 for(s = hash[i]; s != S; s = s->link)
584 if(s->type != SXREF && s->type != SUNDEF && (nexports == 0 && s->sig != 0 || s->subtype == SEXPORT || allexport))
585 n++;
586 esyms = malloc(n*sizeof(Sym*));
587 ne = n;
588 n = 0;
589 for(i = 0; i < NHASH; i++)
590 for(s = hash[i]; s != S; s = s->link)
591 if(s->type != SXREF && s->type != SUNDEF && (nexports == 0 && s->sig != 0 || s->subtype == SEXPORT || allexport))
592 esyms[n++] = s;
593 for(i = 0; i < ne-1; i++)
594 for(j = i+1; j < ne; j++)
595 if(strcmp(esyms[i]->name, esyms[j]->name) > 0){
596 s = esyms[i];
597 esyms[i] = esyms[j];
598 esyms[j] = s;
599 }
600
601 nb = 0;
602 off = 0;
603 et = lookup(EXPTAB, 0);
604 if(et->type != 0 && et->type != SXREF)
605 diag("%s already defined", EXPTAB);
606 et->type = SDATA;
607 str = lookup(".string", 0);
608 if(str->type == 0)
609 str->type = SDATA;
610 sv = str->value;
611 for(i = 0; i < ne; i++){
612 s = esyms[i];
613 Bprint(&bso, "EXPORT: %s sig=%lux t=%d\n", s->name, s->sig, s->type);
614
615 /* signature */
616 p = newdata(et, off, sizeof(long), D_EXTERN);
617 off += sizeof(long);
618 p->to.offset = s->sig;
619
620 /* address */
621 p = newdata(et, off, sizeof(long), D_EXTERN);
622 off += sizeof(long); /* TO DO: bug */
623 p->to.name = D_EXTERN;
624 p->to.sym = s;
625
626 /* string */
627 t = s->name;
628 n = strlen(t)+1;
629 for(;;){
630 buf[nb++] = *t;
631 sv++;
632 if(nb >= NSNAME){
633 p = newdata(str, sv-NSNAME, NSNAME, D_STATIC);
634 p->to.type = D_SCONST;
635 memmove(p->to.sval, buf, NSNAME);
636 nb = 0;
637 }
638 if(*t++ == 0)
639 break;
640 }
641
642 /* name */
643 p = newdata(et, off, sizeof(long), D_EXTERN);
644 off += sizeof(long);
645 p->to.name = D_STATIC;
646 p->to.sym = str;
647 p->to.offset = sv-n;
648 }
649
650 if(nb > 0){
651 p = newdata(str, sv-nb, nb, D_STATIC);
652 p->to.type = D_SCONST;
653 memmove(p->to.sval, buf, nb);
654 }
655
656 for(i = 0; i < 3; i++){
657 newdata(et, off, sizeof(long), D_EXTERN);
658 off += sizeof(long);
659 }
660 et->value = off;
661 if(sv == 0)
662 sv = 1;
663 str->value = sv;
664 exports = ne;
665 free(esyms);
666 }
667