sys/src/cmd/ql/pass.c

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