1 #include "l.h" 2 3 void 4 dodata(void) 5 { 6 int i; 7 Sym *s; 8 Prog *p; 9 long t, u; 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 t = p->from.offset + p->width; 24 if(t > s->value) 25 diag("initialize bounds (%lld): %s\n%P", 26 s->value, s->name, p); 27 } 28 /* allocate small guys */ 29 datsize = 0; 30 for(i=0; i<NHASH; i++) 31 for(s = hash[i]; s != S; s = s->link) { 32 if(s->type != SDATA) 33 if(s->type != SBSS) 34 continue; 35 t = s->value; 36 if(t == 0) { 37 diag("%s: no size", s->name); 38 t = 1; 39 } 40 t = rnd(t, 4); 41 s->value = t; 42 if(t > MINSIZ) 43 continue; 44 if(t >= 8) 45 datsize = rnd(datsize, 8); 46 s->value = datsize; 47 datsize += t; 48 s->type = SDATA1; 49 } 50 51 /* allocate the rest of the data */ 52 for(i=0; i<NHASH; i++) 53 for(s = hash[i]; s != S; s = s->link) { 54 if(s->type != SDATA) { 55 if(s->type == SDATA1) 56 s->type = SDATA; 57 continue; 58 } 59 t = s->value; 60 if(t >= 8) 61 datsize = rnd(datsize, 8); 62 s->value = datsize; 63 datsize += t; 64 } 65 if(datsize) 66 datsize = rnd(datsize, 8); 67 68 if(debug['j']) { 69 /* 70 * pad data with bss that fits up to next 71 * 8k boundary, then push data to 8k 72 */ 73 u = rnd(datsize, 8192); 74 u -= datsize; 75 for(i=0; i<NHASH; i++) 76 for(s = hash[i]; s != S; s = s->link) { 77 if(s->type != SBSS) 78 continue; 79 t = s->value; 80 if(t > u) 81 continue; 82 u -= t; 83 s->value = datsize; 84 s->type = SDATA; 85 datsize += t; 86 } 87 datsize += u; 88 } 89 90 /* now the bss */ 91 bsssize = 0; 92 for(i=0; i<NHASH; i++) 93 for(s = hash[i]; s != S; s = s->link) { 94 if(s->type != SBSS) 95 continue; 96 t = s->value; 97 if(t >= 8) 98 bsssize = rnd(bsssize, 8); 99 s->value = bsssize + datsize; 100 bsssize += t; 101 } 102 xdefine("edata", SBSS, datsize); 103 xdefine("end", SBSS, bsssize + datsize); 104 } 105 106 Prog* 107 brchain(Prog *p) 108 { 109 int i; 110 111 for(i=0; i<20; i++) { 112 if(p == P || p->as != AJMP) 113 return p; 114 p = p->pcond; 115 } 116 return P; 117 } 118 119 void 120 follow(void) 121 { 122 123 if(debug['v']) 124 Bprint(&bso, "%5.2f follow\n", cputime()); 125 Bflush(&bso); 126 firstp = prg(); 127 lastp = firstp; 128 xfol(textp); 129 lastp->link = P; 130 firstp = firstp->link; 131 } 132 133 void 134 xfol(Prog *p) 135 { 136 Prog *q; 137 int i; 138 enum as a; 139 140 loop: 141 if(p == P) 142 return; 143 if(p->as == ATEXT) 144 curtext = p; 145 if(p->as == AJMP) 146 if((q = p->pcond) != P) { 147 p->mark = 1; 148 p = q; 149 if(p->mark == 0) 150 goto loop; 151 } 152 if(p->mark) { 153 /* copy up to 4 instructions to avoid branch */ 154 for(i=0,q=p; i<4; i++,q=q->link) { 155 if(q == P) 156 break; 157 if(q == lastp) 158 break; 159 a = q->as; 160 if(a == ANOP) { 161 i--; 162 continue; 163 } 164 switch(a) { 165 case AJMP: 166 case ARET: 167 case AIRETL: 168 case AIRETQ: 169 case AIRETW: 170 case ARETFL: 171 case ARETFQ: 172 case ARETFW: 173 174 case APUSHL: 175 case APUSHFL: 176 case APUSHQ: 177 case APUSHFQ: 178 case APUSHW: 179 case APUSHFW: 180 case APOPL: 181 case APOPFL: 182 case APOPQ: 183 case APOPFQ: 184 case APOPW: 185 case APOPFW: 186 goto brk; 187 } 188 if(q->pcond == P || q->pcond->mark) 189 continue; 190 if(a == ACALL || a == ALOOP) 191 continue; 192 for(;;) { 193 if(p->as == ANOP) { 194 p = p->link; 195 continue; 196 } 197 q = copyp(p); 198 p = p->link; 199 q->mark = 1; 200 lastp->link = q; 201 lastp = q; 202 if(q->as != a || q->pcond == P || q->pcond->mark) 203 continue; 204 205 q->as = relinv(q->as); 206 p = q->pcond; 207 q->pcond = q->link; 208 q->link = p; 209 xfol(q->link); 210 p = q->link; 211 if(p->mark) 212 return; 213 goto loop; 214 } 215 } /* */ 216 brk:; 217 q = prg(); 218 q->as = AJMP; 219 q->line = p->line; 220 q->to.type = D_BRANCH; 221 q->to.offset = p->pc; 222 q->pcond = p; 223 p = q; 224 } 225 p->mark = 1; 226 lastp->link = p; 227 lastp = p; 228 a = p->as; 229 if(a == AJMP || a == ARET || a == AIRETL || a == AIRETQ || a == AIRETW || 230 a == ARETFL || a == ARETFQ || a == ARETFW) 231 return; 232 if(p->pcond != P) 233 if(a != ACALL) { 234 q = brchain(p->link); 235 if(q != P && q->mark) 236 if(a != ALOOP) { 237 p->as = relinv(a); 238 p->link = p->pcond; 239 p->pcond = q; 240 } 241 xfol(p->link); 242 q = brchain(p->pcond); 243 if(q->mark) { 244 p->pcond = q; 245 return; 246 } 247 p = q; 248 goto loop; 249 } 250 p = p->link; 251 goto loop; 252 } 253 254 int 255 relinv(int a) 256 { 257 258 switch(a) { 259 case AJEQ: return AJNE; 260 case AJNE: return AJEQ; 261 case AJLE: return AJGT; 262 case AJLS: return AJHI; 263 case AJLT: return AJGE; 264 case AJMI: return AJPL; 265 case AJGE: return AJLT; 266 case AJPL: return AJMI; 267 case AJGT: return AJLE; 268 case AJHI: return AJLS; 269 case AJCS: return AJCC; 270 case AJCC: return AJCS; 271 case AJPS: return AJPC; 272 case AJPC: return AJPS; 273 case AJOS: return AJOC; 274 case AJOC: return AJOS; 275 } 276 diag("unknown relation: %s in %s", anames[a], TNAME); 277 return a; 278 } 279 280 void 281 doinit(void) 282 { 283 Sym *s; 284 Prog *p; 285 int x; 286 287 for(p = datap; p != P; p = p->link) { 288 x = p->to.type; 289 if(x != D_EXTERN && x != D_STATIC) 290 continue; 291 s = p->to.sym; 292 if(s->type == 0 || s->type == SXREF) 293 diag("undefined %s initializer of %s", 294 s->name, p->from.sym->name); 295 p->to.offset += s->value; 296 p->to.type = D_CONST; 297 if(s->type == SDATA || s->type == SBSS) 298 p->to.offset += INITDAT; 299 } 300 } 301 302 void 303 patch(void) 304 { 305 long c; 306 Prog *p, *q; 307 Sym *s; 308 long vexit; 309 310 if(debug['v']) 311 Bprint(&bso, "%5.2f mkfwd\n", cputime()); 312 Bflush(&bso); 313 mkfwd(); 314 if(debug['v']) 315 Bprint(&bso, "%5.2f patch\n", cputime()); 316 Bflush(&bso); 317 s = lookup("exit", 0); 318 vexit = s->value; 319 for(p = firstp; p != P; p = p->link) { 320 if(p->as == ATEXT) 321 curtext = p; 322 if(p->as == ACALL || p->as == ARET) { 323 s = p->to.sym; 324 if(s) { 325 if(debug['c']) 326 Bprint(&bso, "%s calls %s\n", TNAME, s->name); 327 switch(s->type) { 328 default: 329 diag("undefined: %s in %s", s->name, TNAME); 330 s->type = STEXT; 331 s->value = vexit; 332 break; /* or fall through to set offset? */ 333 case STEXT: 334 p->to.offset = s->value; 335 break; 336 case SUNDEF: 337 p->pcond = UP; 338 p->to.offset = 0; 339 break; 340 } 341 p->to.type = D_BRANCH; 342 } 343 } 344 if(p->to.type != D_BRANCH || p->pcond == UP) 345 continue; 346 c = p->to.offset; 347 for(q = firstp; q != P;) { 348 if(q->forwd != P) 349 if(c >= q->forwd->pc) { 350 q = q->forwd; 351 continue; 352 } 353 if(c == q->pc) 354 break; 355 q = q->link; 356 } 357 if(q == P) { 358 diag("branch out of range in %s\n%P", TNAME, p); 359 p->to.type = D_NONE; 360 } 361 p->pcond = q; 362 } 363 364 for(p = firstp; p != P; p = p->link) { 365 if(p->as == ATEXT) 366 curtext = p; 367 p->mark = 0; /* initialization for follow */ 368 if(p->pcond != P && p->pcond != UP) { 369 p->pcond = brloop(p->pcond); 370 if(p->pcond != P) 371 if(p->to.type == D_BRANCH) 372 p->to.offset = p->pcond->pc; 373 } 374 } 375 } 376 377 #define LOG 5 378 void 379 mkfwd(void) 380 { 381 Prog *p; 382 int i; 383 long dwn[LOG], cnt[LOG]; 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 int c; 415 Prog *q; 416 417 c = 0; 418 for(q = p; q != P; q = q->pcond) { 419 if(q->as != AJMP) 420 break; 421 c++; 422 if(c >= 5000) 423 return P; 424 } 425 return q; 426 } 427 428 void 429 dostkoff(void) 430 { 431 Prog *p, *q; 432 long autoffset, deltasp; 433 int a, f, curframe, curbecome, maxbecome, pcsize; 434 435 curframe = 0; 436 curbecome = 0; 437 maxbecome = 0; 438 curtext = 0; 439 for(p = firstp; p != P; p = p->link) { 440 441 /* find out how much arg space is used in this TEXT */ 442 if(p->to.type == (D_INDIR+D_SP)) 443 if(p->to.offset > curframe) 444 curframe = p->to.offset; 445 446 switch(p->as) { 447 case ATEXT: 448 if(curtext && curtext->from.sym) { 449 curtext->from.sym->frame = curframe; 450 curtext->from.sym->become = curbecome; 451 if(curbecome > maxbecome) 452 maxbecome = curbecome; 453 } 454 curframe = 0; 455 curbecome = 0; 456 457 curtext = p; 458 break; 459 460 case ARET: 461 /* special form of RET is BECOME */ 462 if(p->from.type == D_CONST) 463 if(p->from.offset > curbecome) 464 curbecome = p->from.offset; 465 break; 466 } 467 } 468 if(curtext && curtext->from.sym) { 469 curtext->from.sym->frame = curframe; 470 curtext->from.sym->become = curbecome; 471 if(curbecome > maxbecome) 472 maxbecome = curbecome; 473 } 474 475 if(debug['b']) 476 print("max become = %d\n", maxbecome); 477 xdefine("ALEFbecome", STEXT, maxbecome); 478 479 curtext = 0; 480 for(p = firstp; p != P; p = p->link) { 481 switch(p->as) { 482 case ATEXT: 483 curtext = p; 484 break; 485 case ACALL: 486 if(curtext != P && curtext->from.sym != S && curtext->to.offset >= 0) { 487 f = maxbecome - curtext->from.sym->frame; 488 if(f <= 0) 489 break; 490 /* calling a become or calling a variable */ 491 if(p->to.sym == S || p->to.sym->become) { 492 curtext->to.offset += f; 493 if(debug['b']) { 494 curp = p; 495 print("%D calling %D increase %d\n", 496 &curtext->from, &p->to, f); 497 } 498 } 499 } 500 break; 501 } 502 } 503 504 autoffset = 0; 505 deltasp = 0; 506 for(p = firstp; p != P; p = p->link) { 507 if(p->as == ATEXT) { 508 curtext = p; 509 autoffset = p->to.offset; 510 if(autoffset < 0) 511 autoffset = 0; 512 if(autoffset) { 513 p = appendp(p); 514 p->as = AADJSP; 515 p->from.type = D_CONST; 516 p->from.offset = autoffset; 517 } 518 deltasp = autoffset; 519 } 520 pcsize = p->mode/8; 521 a = p->from.type; 522 if(a == D_AUTO) 523 p->from.offset += deltasp; 524 if(a == D_PARAM) 525 p->from.offset += deltasp + pcsize; 526 a = p->to.type; 527 if(a == D_AUTO) 528 p->to.offset += deltasp; 529 if(a == D_PARAM) 530 p->to.offset += deltasp + pcsize; 531 532 switch(p->as) { 533 default: 534 continue; 535 case APUSHL: 536 case APUSHFL: 537 deltasp += 4; 538 continue; 539 case APUSHQ: 540 case APUSHFQ: 541 deltasp += 8; 542 continue; 543 case APUSHW: 544 case APUSHFW: 545 deltasp += 2; 546 continue; 547 case APOPL: 548 case APOPFL: 549 deltasp -= 4; 550 continue; 551 case APOPQ: 552 case APOPFQ: 553 deltasp -= 8; 554 continue; 555 case APOPW: 556 case APOPFW: 557 deltasp -= 2; 558 continue; 559 case ARET: 560 break; 561 } 562 563 if(autoffset != deltasp) 564 diag("unbalanced PUSH/POP"); 565 if(p->from.type == D_CONST) 566 goto become; 567 568 if(autoffset) { 569 q = p; 570 p = appendp(p); 571 p->as = ARET; 572 573 q->as = AADJSP; 574 q->from.type = D_CONST; 575 q->from.offset = -autoffset; 576 } 577 continue; 578 579 become: 580 q = p; 581 p = appendp(p); 582 p->as = AJMP; 583 p->to = q->to; 584 p->pcond = q->pcond; 585 586 q->as = AADJSP; 587 q->from = zprg.from; 588 q->from.type = D_CONST; 589 q->from.offset = -autoffset; 590 q->to = zprg.to; 591 continue; 592 } 593 } 594 595 vlong 596 atolwhex(char *s) 597 { 598 vlong n; 599 int f; 600 601 n = 0; 602 f = 0; 603 while(*s == ' ' || *s == '\t') 604 s++; 605 if(*s == '-' || *s == '+') { 606 if(*s++ == '-') 607 f = 1; 608 while(*s == ' ' || *s == '\t') 609 s++; 610 } 611 if(s[0]=='0' && s[1]){ 612 if(s[1]=='x' || s[1]=='X'){ 613 s += 2; 614 for(;;){ 615 if(*s >= '0' && *s <= '9') 616 n = n*16 + *s++ - '0'; 617 else if(*s >= 'a' && *s <= 'f') 618 n = n*16 + *s++ - 'a' + 10; 619 else if(*s >= 'A' && *s <= 'F') 620 n = n*16 + *s++ - 'A' + 10; 621 else 622 break; 623 } 624 } else 625 while(*s >= '0' && *s <= '7') 626 n = n*8 + *s++ - '0'; 627 } else 628 while(*s >= '0' && *s <= '9') 629 n = n*10 + *s++ - '0'; 630 if(f) 631 n = -n; 632 return n; 633 } 634 635 void 636 undef(void) 637 { 638 int i; 639 Sym *s; 640 641 for(i=0; i<NHASH; i++) 642 for(s = hash[i]; s != S; s = s->link) 643 if(s->type == SXREF) 644 diag("%s: not defined", s->name); 645 } 646 647 void 648 import(void) 649 { 650 int i; 651 Sym *s; 652 653 for(i = 0; i < NHASH; i++) 654 for(s = hash[i]; s != S; s = s->link) 655 if(s->sig != 0 && s->type == SXREF && (nimports == 0 || s->subtype == SIMPORT)){ 656 if(s->value != 0) 657 diag("value != 0 on SXREF"); 658 undefsym(s); 659 Bprint(&bso, "IMPORT: %s sig=%lux v=%lld\n", s->name, s->sig, s->value); 660 if(debug['S']) 661 s->sig = 0; 662 } 663 } 664 665 void 666 ckoff(Sym *s, long v) 667 { 668 if(v < 0 || v >= 1<<Roffset) 669 diag("relocation offset %ld for %s out of range", v, s->name); 670 } 671 672 static Prog* 673 newdata(Sym *s, int o, int w, int t) 674 { 675 Prog *p; 676 677 p = prg(); 678 if(edatap == P) 679 datap = p; 680 else 681 edatap->link = p; 682 edatap = p; 683 p->as = ADATA; 684 p->width = w; 685 p->from.scale = w; 686 p->from.type = t; 687 p->from.sym = s; 688 p->from.offset = o; 689 p->to.type = D_CONST; 690 return p; 691 } 692 693 void 694 export(void) 695 { 696 int i, j, n, off, nb, sv, ne; 697 Sym *s, *et, *str, **esyms; 698 Prog *p; 699 char buf[NSNAME], *t; 700 701 n = 0; 702 for(i = 0; i < NHASH; i++) 703 for(s = hash[i]; s != S; s = s->link) 704 if(s->sig != 0 && s->type != SXREF && s->type != SUNDEF && (nexports == 0 || s->subtype == SEXPORT)) 705 n++; 706 esyms = malloc(n*sizeof(Sym*)); 707 ne = n; 708 n = 0; 709 for(i = 0; i < NHASH; i++) 710 for(s = hash[i]; s != S; s = s->link) 711 if(s->sig != 0 && s->type != SXREF && s->type != SUNDEF && (nexports == 0 || s->subtype == SEXPORT)) 712 esyms[n++] = s; 713 for(i = 0; i < ne-1; i++) 714 for(j = i+1; j < ne; j++) 715 if(strcmp(esyms[i]->name, esyms[j]->name) > 0){ 716 s = esyms[i]; 717 esyms[i] = esyms[j]; 718 esyms[j] = s; 719 } 720 721 nb = 0; 722 off = 0; 723 et = lookup(EXPTAB, 0); 724 if(et->type != 0 && et->type != SXREF) 725 diag("%s already defined", EXPTAB); 726 et->type = SDATA; 727 str = lookup(".string", 0); 728 if(str->type == 0) 729 str->type = SDATA; 730 sv = str->value; 731 for(i = 0; i < ne; i++){ 732 s = esyms[i]; 733 if(debug['S']) 734 s->sig = 0; 735 /* Bprint(&bso, "EXPORT: %s sig=%lux t=%d\n", s->name, s->sig, s->type); */ 736 737 /* signature */ 738 p = newdata(et, off, sizeof(long), D_EXTERN); 739 off += sizeof(long); 740 p->to.offset = s->sig; 741 742 /* address */ 743 p = newdata(et, off, sizeof(long), D_EXTERN); 744 off += sizeof(long); 745 p->to.type = D_ADDR; 746 p->to.index = D_EXTERN; 747 p->to.sym = s; 748 749 /* string */ 750 t = s->name; 751 n = strlen(t)+1; 752 for(;;){ 753 buf[nb++] = *t; 754 sv++; 755 if(nb >= NSNAME){ 756 p = newdata(str, sv-NSNAME, NSNAME, D_STATIC); 757 p->to.type = D_SCONST; 758 memmove(p->to.scon, buf, NSNAME); 759 nb = 0; 760 } 761 if(*t++ == 0) 762 break; 763 } 764 765 /* name */ 766 p = newdata(et, off, sizeof(long), D_EXTERN); 767 off += sizeof(long); 768 p->to.type = D_ADDR; 769 p->to.index = D_STATIC; 770 p->to.sym = str; 771 p->to.offset = sv-n; 772 } 773 774 if(nb > 0){ 775 p = newdata(str, sv-nb, nb, D_STATIC); 776 p->to.type = D_SCONST; 777 memmove(p->to.scon, buf, nb); 778 } 779 780 for(i = 0; i < 3; i++){ 781 newdata(et, off, sizeof(long), D_EXTERN); 782 off += sizeof(long); 783 } 784 et->value = off; 785 if(sv == 0) 786 sv = 1; 787 str->value = sv; 788 exports = ne; 789 free(esyms); 790 } 791