sys/src/cmd/1l/pass.c

   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(s->type == SBSS)
  17                         s->type = SDATA;
  18                 if(s->type != SDATA)
  19                         diag("initialize non-data (%d): %s\n%P",
  20                                 s->type, s->name, p);
  21                 t = p->from.offset + p->from.displace;
  22                 if(t > s->value)
  23                         diag("initialize bounds (%ld): %s\n%P",
  24                                 s->value, s->name, p);
  25         }
  26
  27         /* allocate small guys */
  28         datsize = 0;
  29         for(i=0; i<NHASH; i++)
  30         for(s = hash[i]; s != S; s = s->link) {
  31                 if(s->type != SDATA)
  32                 if(s->type != SBSS)
  33                         continue;
  34                 t = s->value;
  35                 if(t == 0) {
  36                         diag("%s: no size", s->name);
  37                         t = 1;
  38                 }
  39                 t = rnd(t, 4);;
  40                 s->value = t;
  41                 if(t > MINSIZ)
  42                         continue;
  43                 s->value = datsize;
  44                 datsize += t;
  45                 s->type = SDATA1;
  46         }
  47
  48         /* allocate the rest of the data */
  49         for(i=0; i<NHASH; i++)
  50         for(s = hash[i]; s != S; s = s->link) {
  51                 if(s->type != SDATA) {
  52                         if(s->type == SDATA1)
  53                                 s->type = SDATA;
  54                         continue;
  55                 }
  56                 t = s->value;
  57                 s->value = datsize;
  58                 datsize += t;
  59         }
  60
  61         if(debug['j']) {
  62                 /*
  63                  * pad data with bss that fits up to next
  64                  * 8k boundary, then push data to 8k
  65                  */
  66                 u = rnd(datsize, 8192);
  67                 u -= datsize;
  68                 for(i=0; i<NHASH; i++)
  69                 for(s = hash[i]; s != S; s = s->link) {
  70                         if(s->type != SBSS)
  71                                 continue;
  72                         t = s->value;
  73                         if(t > u)
  74                                 continue;
  75                         u -= t;
  76                         s->value = datsize;
  77                         s->type = SDATA;
  78                         datsize += t;
  79                 }
  80                 datsize += u;
  81         }
  82
  83         /* now the bss */
  84         bsssize = 0;
  85         for(i=0; i<NHASH; i++)
  86         for(s = hash[i]; s != S; s = s->link) {
  87                 if(s->type != SBSS)
  88                         continue;
  89                 t = s->value;
  90                 s->value = bsssize + datsize;
  91                 bsssize += t;
  92         }
  93         xdefine("bdata", SDATA, 0L);
  94         xdefine("edata", SDATA, datsize);
  95         xdefine("end", SBSS, datsize+bsssize);
  96 }
  97
  98 Prog*
  99 brchain(Prog *p)
 100 {
 101         int i;
 102
 103         for(i=0; i<20; i++) {
 104                 if(p == P || p->as != ABRA)
 105                         return p;
 106                 p = p->pcond;
 107         }
 108         return P;
 109 }
 110
 111 void
 112 follow(void)
 113 {
 114         Prog *p;
 115         long o;
 116
 117         if(debug['v'])
 118                 Bprint(&bso, "%5.2f follow\n", cputime());
 119         Bflush(&bso);
 120         firstp = prg();
 121         lastp = firstp;
 122         xfol(textp);
 123         lastp->link = P;
 124         firstp = firstp->link;
 125         o = 0; /* set */
 126         for(p = firstp; p != P; p = p->link) {
 127                 if(p->as == ATEXT)
 128                         curtext = p;
 129
 130                 p->stkoff = -1; /* initialization for stkoff */
 131                 if(p->as == ATEXT) {
 132                         p->stkoff = 0;
 133                         o = p->to.offset;
 134                         continue;
 135                 }
 136                 if(p->as == AADJSP && p->from.offset == 0) {
 137                         p->stkoff = o;
 138                         continue;
 139                 }
 140         }
 141 }
 142
 143 void
 144 xfol(Prog *p)
 145 {
 146         Prog *q;
 147         int i;
 148         enum as a;
 149
 150 loop:
 151         if(p == P)
 152                 return;
 153         if(p->as == ATEXT)
 154                 curtext = p;
 155         if(p->as == ABRA)
 156         if((q = p->pcond) != P) {
 157                 p->mark = 1;
 158                 p = q;
 159                 if(p->mark == 0)
 160                         goto loop;
 161         }
 162         if(p->mark) {
 163                 /* copy up to 4 instructions to avoid branch */
 164                 for(i=0,q=p; i<4; i++,q=q->link) {
 165                         if(q == P)
 166                                 break;
 167                         if(q == lastp)
 168                                 break;
 169                         a = q->as;
 170                         if(a == ANOP) {
 171                                 i--;
 172                                 continue;
 173                         }
 174                         if(a == ABRA || a == ARTS || a == ARTE)
 175                                 break;
 176                         if(q->pcond == P || q->pcond->mark)
 177                                 continue;
 178                         if(a == ABSR || a == ADBF)
 179                                 continue;
 180                         for(;;) {
 181                                 if(p->as == ANOP) {
 182                                         p = p->link;
 183                                         continue;
 184                                 }
 185                                 q = copyp(p);
 186                                 p = p->link;
 187                                 q->mark = 1;
 188                                 lastp->link = q;
 189                                 lastp = q;
 190                                 if(q->as != a || q->pcond == P || q->pcond->mark)
 191                                         continue;
 192                                 q->as = relinv(q->as);
 193                                 p = q->pcond;
 194                                 q->pcond = q->link;
 195                                 q->link = p;
 196                                 xfol(q->link);
 197                                 p = q->link;
 198                                 if(p->mark)
 199                                         return;
 200                                 goto loop;
 201                         }
 202                 } /* */
 203                 q = prg();
 204                 q->as = ABRA;
 205                 q->line = p->line;
 206                 q->to.type = D_BRANCH;
 207                 q->to.offset = p->pc;
 208                 q->pcond = p;
 209                 p = q;
 210         }
 211         p->mark = 1;
 212         lastp->link = p;
 213         lastp = p;
 214         a = p->as;
 215         if(a == ARTS || a == ABRA || a == ARTE)
 216                 return;
 217         if(p->pcond != P)
 218         if(a != ABSR) {
 219                 q = brchain(p->link);
 220                 if(q != P && q->mark)
 221                 if(a != ADBF) {
 222                         p->as = relinv(a);
 223                         p->link = p->pcond;
 224                         p->pcond = q;
 225                 }
 226                 xfol(p->link);
 227                 q = brchain(p->pcond);
 228                 if(q->mark) {
 229                         p->pcond = q;
 230                         return;
 231                 }
 232                 p = q;
 233                 goto loop;
 234         }
 235         p = p->link;
 236         goto loop;
 237 }
 238
 239 int
 240 relinv(int a)
 241 {
 242
 243         switch(a) {
 244         case ABEQ:      return ABNE;
 245         case ABNE:      return ABEQ;
 246         case ABLE:      return ABGT;
 247         case ABLS:      return ABHI;
 248         case ABLT:      return ABGE;
 249         case ABMI:      return ABPL;
 250         case ABGE:      return ABLT;
 251         case ABPL:      return ABMI;
 252         case ABGT:      return ABLE;
 253         case ABHI:      return ABLS;
 254         case ABCS:      return ABCC;
 255         case ABCC:      return ABCS;
 256         case AFBEQ:     return AFBNE;
 257         case AFBF:      return AFBT;
 258         case AFBGE:     return AFBLT;
 259         case AFBGT:     return AFBLE;
 260         case AFBLE:     return AFBGT;
 261         case AFBLT:     return AFBGE;
 262         case AFBNE:     return AFBEQ;
 263         case AFBT:      return AFBF;
 264         }
 265         diag("unknown relation: %s in %s", anames[a], TNAME);
 266         return a;
 267 }
 268
 269 void
 270 patch(void)
 271 {
 272         long c;
 273         Prog *p, *q;
 274         Sym *s;
 275         long vexit;
 276
 277         if(debug['v'])
 278                 Bprint(&bso, "%5.2f mkfwd\n", cputime());
 279         Bflush(&bso);
 280         mkfwd();
 281         if(debug['v'])
 282                 Bprint(&bso, "%5.2f patch\n", cputime());
 283         Bflush(&bso);
 284         s = lookup("exit", 0);
 285         vexit = s->value;
 286         for(p = firstp; p != P; p = p->link) {
 287                 if(p->as == ATEXT)
 288                         curtext = p;
 289                 if((p->as == ABSR || p->as == ARTS) && p->to.sym != S) {
 290                         s = p->to.sym;
 291                         if(s->type != STEXT) {
 292                                 diag("undefined: %s in %s", s->name, TNAME);
 293                                 s->type = STEXT;
 294                                 s->value = vexit;
 295                         }
 296                         p->to.offset = s->value;
 297                         p->to.type = D_BRANCH;
 298                 }
 299                 if(p->to.type != D_BRANCH)
 300                         continue;
 301                 c = p->to.offset;
 302                 for(q = firstp; q != P;) {
 303                         if(q->forwd != P)
 304                         if(c >= q->forwd->pc) {
 305                                 q = q->forwd;
 306                                 continue;
 307                         }
 308                         if(c == q->pc)
 309                                 break;
 310                         q = q->link;
 311                 }
 312                 if(q == P) {
 313                         diag("branch out of range in %s\n%P", TNAME, p);
 314                         p->to.type = D_NONE;
 315                 }
 316                 p->pcond = q;
 317         }
 318
 319         for(p = firstp; p != P; p = p->link) {
 320                 if(p->as == ATEXT)
 321                         curtext = p;
 322                 p->mark = 0;    /* initialization for follow */
 323                 if(p->pcond != P) {
 324                         p->pcond = brloop(p->pcond);
 325                         if(p->pcond != P)
 326                         if(p->to.type == D_BRANCH)
 327                                 p->to.offset = p->pcond->pc;
 328                 }
 329         }
 330 }
 331
 332 #define LOG     5
 333 void
 334 mkfwd(void)
 335 {
 336         Prog *p;
 337         int i;
 338         long dwn[LOG], cnt[LOG];
 339         Prog *lst[LOG];
 340
 341         for(i=0; i<LOG; i++) {
 342                 if(i == 0)
 343                         cnt[i] = 1; else
 344                         cnt[i] = LOG * cnt[i-1];
 345                 dwn[i] = 1;
 346                 lst[i] = P;
 347         }
 348         i = 0;
 349         for(p = firstp; p != P; p = p->link) {
 350                 if(p->as == ATEXT)
 351                         curtext = p;
 352                 i--;
 353                 if(i < 0)
 354                         i = LOG-1;
 355                 p->forwd = P;
 356                 dwn[i]--;
 357                 if(dwn[i] <= 0) {
 358                         dwn[i] = cnt[i];
 359                         if(lst[i] != P)
 360                                 lst[i]->forwd = p;
 361                         lst[i] = p;
 362                 }
 363         }
 364 }
 365
 366 Prog*
 367 brloop(Prog *p)
 368 {
 369         int c;
 370         Prog *q;
 371
 372         c = 0;
 373         for(q = p; q != P; q = q->pcond) {
 374                 if(q->as != ABRA)
 375                         break;
 376                 c++;
 377                 if(c >= 5000)
 378                         return P;
 379         }
 380         return q;
 381 }
 382
 383 void
 384 dostkoff(void)
 385 {
 386         Prog *p, *q, *qq;
 387         long s, t;
 388         int a;
 389         Optab *o;
 390
 391         if(debug['v'])
 392                 Bprint(&bso, "%5.2f stkoff\n", cputime());
 393         Bflush(&bso);
 394         s = 0;
 395         for(p = firstp; p != P; p = p->link) {
 396                 if(p->as == ATEXT) {
 397                         curtext = p;
 398                         s = p->to.offset;
 399                         if(s == 0)
 400                                 continue;
 401                         p = nprg(p);
 402                         p->as = AADJSP;
 403                         p->from.type = D_CONST;
 404                         p->from.offset = s;
 405                         p->stkoff = 0;
 406                         continue;
 407                 }
 408                 t = 0;
 409                 for(q = p; q != P; q = q->pcond) {
 410                         if(q->as == ATEXT)
 411                                 break;
 412                         if(q->stkoff >= 0)
 413                                 if(q->stkoff != s)
 414                                         diag("stack offset %ld is %ld sb %ld in %s\n%P",
 415                                                 q->pc, q->stkoff, s, TNAME, p);
 416                         q->stkoff = s;
 417                         if(t++ > 100) {
 418                                 diag("loop in stack offset 1: %P", p);
 419                                 break;
 420                         }
 421                 }
 422                 o = &optab[p->as];
 423                 if(p->to.type == D_TOS)
 424                         s -= o->dstsp;
 425                 if(p->from.type == D_TOS)
 426                         s -= o->srcsp;
 427                 if(p->as == AADJSP)
 428                         s += p->from.offset;
 429                 if(p->as == APEA)
 430                         s += 4;
 431                 t = 0;
 432                 for(q = p->link; q != P; q = q->pcond) {
 433                         if(q->as == ATEXT) {
 434                                 q = P;
 435                                 break;
 436                         }
 437                         if(q->stkoff >= 0)
 438                                 break;
 439                         if(t++ > 100) {
 440                                 diag("loop in stack offset 2: %P", p);
 441                                 break;
 442                         }
 443                 }
 444                 if(q == P || q->stkoff == s)
 445                         continue;
 446                 if(p->as == ABRA || p->as == ARTS || p->as == ARTE) {
 447                         s = q->stkoff;
 448                         continue;
 449                 }
 450                 t = q->stkoff - s;
 451                 s = q->stkoff;
 452                 p = nprg(p);
 453                 p->as = AADJSP;
 454                 p->stkoff = s - t;
 455                 p->from.type = D_CONST;
 456                 p->from.offset = t;
 457         }
 458
 459         if(debug['v'])
 460                 Bprint(&bso, "%5.2f rewrite\n", cputime());
 461         Bflush(&bso);
 462         for(p = firstp; p != P; p = p->link) {
 463                 if(p->as == ATEXT)
 464                         curtext = p;
 465                 a = p->from.type & D_MASK;
 466                 if(a == D_AUTO)
 467                         p->from.offset += p->stkoff;
 468                 if(a == D_PARAM)
 469                         p->from.offset += p->stkoff + 4;
 470                 a = p->to.type & D_MASK;
 471                 if(a == D_AUTO)
 472                         p->to.offset += p->stkoff;
 473                 if(a == D_PARAM)
 474                         p->to.offset += p->stkoff + 4;
 475                 switch(p->as) {
 476                 default:
 477                         continue;
 478
 479                 case AMOVW:
 480                         if(p->from.type != D_CCR)
 481                                 continue;
 482                         a = p->to.type;
 483                         if((a < D_R0 || a > D_R0+7) && a != D_TOS)
 484                                 diag("bad dest for MOVCC %P", p);
 485                         p->as = ALEA;
 486                         p->from.type = I_INDIR|(D_A0+7);
 487                         p->from.offset = -2;
 488                         p->to.type = D_A0+7;
 489
 490                         p = nprg(p);
 491                         p->as = ABSR;
 492                         p->to.type = D_BRANCH;
 493                         p->pcond = prog_ccr;
 494                         p->to.sym = prog_ccr->from.sym;
 495
 496                         if(a != D_TOS) {
 497                                 p = nprg(p);
 498                                 p->as = AMOVW;
 499                                 p->from.type = D_TOS;
 500                                 p->to.type = a;
 501                         }
 502                         continue;
 503
 504                 case AEXTBL:
 505                         a = p->to.type;
 506                         if(a < D_R0 || a > D_R0+7)
 507                                 diag("bad dest for EXTB");
 508                         p->as = AEXTBW;
 509
 510                         p = nprg(p);
 511                         p->as = AEXTWL;
 512                         p->to.type = a;
 513                         continue;
 514
 515                 case AMULSL:
 516                 case AMULUL:
 517                         qq = prog_mull;
 518                         goto mdcom;
 519                 case ADIVSL:
 520                         qq = prog_divsl;
 521                         goto mdcom;
 522                 case ADIVUL:
 523                         qq = prog_divul;
 524                 mdcom:
 525                         if(debug['m'])
 526                                 continue;
 527                         a = p->to.type;
 528                         if(a < D_R0 || a > D_R0+7)
 529                                 diag("bad dest for mul/div");
 530                         p->as = AMOVL;
 531                         p->to.type = D_TOS;
 532
 533                         p = nprg(p);
 534                         p->as = AMOVL;
 535                         p->from.type = a;
 536                         p->to.type = D_TOS;
 537
 538                         p = nprg(p);
 539                         p->as = ABSR;
 540                         p->to.type = D_BRANCH;
 541                         p->pcond = qq;
 542                         p->to.sym = qq->from.sym;
 543
 544                         p = nprg(p);
 545                         p->as = AMOVL;
 546                         p->from.type = D_TOS;
 547                         p->to.type = a;
 548
 549                         p = nprg(p);
 550                         p->as = AMOVL;
 551                         p->from.type = D_TOS;
 552                         p->to.type = a+1;
 553                         if(qq == prog_mull)
 554                                 p->to.type = a;
 555                         continue;
 556
 557                 case ARTS:
 558                         break;
 559                 }
 560                 if(p->stkoff == 0)
 561                         continue;
 562
 563                 p->as = AADJSP;
 564                 p->from.type = D_CONST;
 565                 p->from.offset = -p->stkoff;
 566
 567                 p = nprg(p);
 568                 p->as = ARTS;
 569                 p->stkoff = 0;
 570         }
 571 }
 572
 573 long
 574 atolwhex(char *s)
 575 {
 576         long n;
 577         int f;
 578
 579         n = 0;
 580         f = 0;
 581         while(*s == ' ' || *s == '\t')
 582                 s++;
 583         if(*s == '-' || *s == '+') {
 584                 if(*s++ == '-')
 585                         f = 1;
 586                 while(*s == ' ' || *s == '\t')
 587                         s++;
 588         }
 589         if(s[0]=='0' && s[1]){
 590                 if(s[1]=='x' || s[1]=='X'){
 591                         s += 2;
 592                         for(;;){
 593                                 if(*s >= '0' && *s <= '9')
 594                                         n = n*16 + *s++ - '0';
 595                                 else if(*s >= 'a' && *s <= 'f')
 596                                         n = n*16 + *s++ - 'a' + 10;
 597                                 else if(*s >= 'A' && *s <= 'F')
 598                                         n = n*16 + *s++ - 'A' + 10;
 599                                 else
 600                                         break;
 601                         }
 602                 } else
 603                         while(*s >= '0' && *s <= '7')
 604                                 n = n*8 + *s++ - '0';
 605         } else
 606                 while(*s >= '0' && *s <= '9')
 607                         n = n*10 + *s++ - '0';
 608         if(f)
 609                 n = -n;
 610         return n;
 611 }
 612
 613 void
 614 undef(void)
 615 {
 616         int i;
 617         Sym *s;
 618
 619         for(i=0; i<NHASH; i++)
 620         for(s = hash[i]; s != S; s = s->link)
 621                 if(s->type == SXREF)
 622                         diag("%s: not defined", s->name);
 623 }
 624
 625 void
 626 initmuldiv1(void)
 627 {
 628         lookup("_mull", 0)->type = SXREF;
 629         lookup("_divsl", 0)->type = SXREF;
 630         lookup("_divul", 0)->type = SXREF;
 631         lookup("_ccr", 0)->type = SXREF;
 632 }
 633
 634 void
 635 initmuldiv2(void)
 636 {
 637         Sym *s1, *s2, *s3, *s4;
 638         Prog *p;
 639
 640         if(prog_mull != P)
 641                 return;
 642         s1 = lookup("_mull", 0);
 643         s2 = lookup("_divsl", 0);
 644         s3 = lookup("_divul", 0);
 645         s4 = lookup("_ccr", 0);
 646         for(p = firstp; p != P; p = p->link)
 647                 if(p->as == ATEXT) {
 648                         if(p->from.sym == s1)
 649                                 prog_mull = p;
 650                         if(p->from.sym == s2)
 651                                 prog_divsl = p;
 652                         if(p->from.sym == s3)
 653                                 prog_divul = p;
 654                         if(p->from.sym == s4)
 655                                 prog_ccr = p;
 656                 }
 657         if(prog_mull == P) {
 658                 diag("undefined: %s", s1->name);
 659                 prog_mull = curtext;
 660         }
 661         if(prog_divsl == P) {
 662                 diag("undefined: %s", s2->name);
 663                 prog_divsl = curtext;
 664         }
 665         if(prog_divul == P) {
 666                 diag("undefined: %s", s3->name);
 667                 prog_divul = curtext;
 668         }
 669         if(prog_ccr == P) {
 670                 diag("undefined: %s", s4->name);
 671                 prog_ccr = curtext;
 672         }
 673 }