sys/src/cmd/2l/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         Sym *s;
 117
 118         if(debug['v'])
 119                 Bprint(&bso, "%5.2f follow\n", cputime());
 120         Bflush(&bso);
 121         firstp = prg();
 122         lastp = firstp;
 123         xfol(textp);
 124         lastp->link = P;
 125         firstp = firstp->link;
 126         o = 0; /* set */
 127         for(p = firstp; p != P; p = p->link) {
 128                 if(p->as == ATEXT)
 129                         curtext = p;
 130                 if(p->as == ABCASE) {   /* initialization for dodata */
 131                         s = p->from.sym;
 132                         if(s->type == SBSS)
 133                                 s->type = SDATA;
 134                         if(s->type != SDATA)
 135                                 diag("BCASE of non-data: %s in %s\n%P",
 136                                         s->name, TNAME, p);
 137                 }
 138
 139                 p->stkoff = -1; /* initialization for stkoff */
 140                 if(p->as == ATEXT) {
 141                         p->stkoff = 0;
 142                         o = p->to.offset;
 143                         continue;
 144                 }
 145                 if(p->as == AADJSP && p->from.offset == 0) {
 146                         p->stkoff = o;
 147                         continue;
 148                 }
 149         }
 150 }
 151
 152 void
 153 xfol(Prog *p)
 154 {
 155         Prog *q;
 156         int i;
 157         enum as a;
 158
 159 loop:
 160         if(p == P)
 161                 return;
 162         if(p->as == ATEXT)
 163                 curtext = p;
 164         if(p->as == ABRA)
 165         if((q = p->pcond) != P) {
 166                 p->mark = 1;
 167                 p = q;
 168                 if(p->mark == 0)
 169                         goto loop;
 170         }
 171         if(p->mark) {
 172                 /* copy up to 4 instructions to avoid branch */
 173                 for(i=0,q=p; i<4; i++,q=q->link) {
 174                         if(q == P)
 175                                 break;
 176                         if(q == lastp)
 177                                 break;
 178                         a = q->as;
 179                         if(a == ANOP) {
 180                                 i--;
 181                                 continue;
 182                         }
 183                         if(a == ABRA || a == ARTS || a == ARTE)
 184                                 break;
 185                         if(q->pcond == P || q->pcond->mark)
 186                                 continue;
 187                         if(a == ABSR || a == ABCASE || a == ADBF)
 188                                 continue;
 189                         for(;;) {
 190                                 if(p->as == ANOP) {
 191                                         p = p->link;
 192                                         continue;
 193                                 }
 194                                 q = copyp(p);
 195                                 p = p->link;
 196                                 q->mark = 1;
 197                                 lastp->link = q;
 198                                 lastp = q;
 199                                 if(q->as != a || q->pcond == P || q->pcond->mark)
 200                                         continue;
 201                                 q->as = relinv(q->as);
 202                                 p = q->pcond;
 203                                 q->pcond = q->link;
 204                                 q->link = p;
 205                                 xfol(q->link);
 206                                 p = q->link;
 207                                 if(p->mark)
 208                                         return;
 209                                 goto loop;
 210                         }
 211                 } /* */
 212                 q = prg();
 213                 q->as = ABRA;
 214                 q->line = p->line;
 215                 q->to.type = D_BRANCH;
 216                 q->to.offset = p->pc;
 217                 q->pcond = p;
 218                 p = q;
 219         }
 220         p->mark = 1;
 221         lastp->link = p;
 222         lastp = p;
 223         a = p->as;
 224         if(a == ARTS || a == ABRA || a == ARTE)
 225                 return;
 226         if(p->pcond != P)
 227         if(a != ABSR) {
 228                 q = brchain(p->link);
 229                 if(q != P && q->mark)
 230                 if(a != ABCASE && a != ADBF) {
 231                         p->as = relinv(a);
 232                         p->link = p->pcond;
 233                         p->pcond = q;
 234                 }
 235                 xfol(p->link);
 236                 q = brchain(p->pcond);
 237                 if(q->mark) {
 238                         p->pcond = q;
 239                         return;
 240                 }
 241                 p = q;
 242                 goto loop;
 243         }
 244         p = p->link;
 245         goto loop;
 246 }
 247
 248 int
 249 relinv(int a)
 250 {
 251
 252         switch(a) {
 253         case ABEQ:      return ABNE;
 254         case ABNE:      return ABEQ;
 255         case ABLE:      return ABGT;
 256         case ABLS:      return ABHI;
 257         case ABLT:      return ABGE;
 258         case ABMI:      return ABPL;
 259         case ABGE:      return ABLT;
 260         case ABPL:      return ABMI;
 261         case ABGT:      return ABLE;
 262         case ABHI:      return ABLS;
 263         case ABCS:      return ABCC;
 264         case ABCC:      return ABCS;
 265         case AFBEQ:     return AFBNE;
 266         case AFBF:      return AFBT;
 267         case AFBGE:     return AFBLT;
 268         case AFBGT:     return AFBLE;
 269         case AFBLE:     return AFBGT;
 270         case AFBLT:     return AFBGE;
 271         case AFBNE:     return AFBEQ;
 272         case AFBT:      return AFBF;
 273         }
 274         diag("unknown relation: %s in %s", anames[a], TNAME);
 275         return a;
 276 }
 277
 278 void
 279 patch(void)
 280 {
 281         long c;
 282         Prog *p, *q;
 283         Sym *s;
 284         long vexit;
 285
 286         if(debug['v'])
 287                 Bprint(&bso, "%5.2f mkfwd\n", cputime());
 288         Bflush(&bso);
 289         mkfwd();
 290         if(debug['v'])
 291                 Bprint(&bso, "%5.2f patch\n", cputime());
 292         Bflush(&bso);
 293         s = lookup("exit", 0);
 294         vexit = s->value;
 295         for(p = firstp; p != P; p = p->link) {
 296                 if(p->as == ATEXT)
 297                         curtext = p;
 298                 if((p->as == ABSR || p->as == ARTS) && p->to.sym != S) {
 299                         s = p->to.sym;
 300                         if(s->type != STEXT) {
 301                                 diag("undefined: %s in %s", s->name, TNAME);
 302                                 s->type = STEXT;
 303                                 s->value = vexit;
 304                         }
 305                         p->to.offset = s->value;
 306                         p->to.type = D_BRANCH;
 307                 }
 308                 if(p->to.type != D_BRANCH)
 309                         continue;
 310                 c = p->to.offset;
 311                 for(q = firstp; q != P;) {
 312                         if(q->forwd != P)
 313                         if(c >= q->forwd->pc) {
 314                                 q = q->forwd;
 315                                 continue;
 316                         }
 317                         if(c == q->pc)
 318                                 break;
 319                         q = q->link;
 320                 }
 321                 if(q == P) {
 322                         diag("branch out of range in %s\n%P", TNAME, p);
 323                         p->to.type = D_NONE;
 324                 }
 325                 p->pcond = q;
 326         }
 327
 328         for(p = firstp; p != P; p = p->link) {
 329                 if(p->as == ATEXT)
 330                         curtext = p;
 331                 p->mark = 0;    /* initialization for follow */
 332                 if(p->pcond != P) {
 333                         p->pcond = brloop(p->pcond);
 334                         if(p->pcond != P)
 335                         if(p->to.type == D_BRANCH)
 336                                 p->to.offset = p->pcond->pc;
 337                 }
 338         }
 339 }
 340
 341 #define LOG     5
 342 void
 343 mkfwd(void)
 344 {
 345         Prog *p;
 346         int i;
 347         long dwn[LOG], cnt[LOG];
 348         Prog *lst[LOG];
 349
 350         for(i=0; i<LOG; i++) {
 351                 if(i == 0)
 352                         cnt[i] = 1; else
 353                         cnt[i] = LOG * cnt[i-1];
 354                 dwn[i] = 1;
 355                 lst[i] = P;
 356         }
 357         i = 0;
 358         for(p = firstp; p != P; p = p->link) {
 359                 if(p->as == ATEXT)
 360                         curtext = p;
 361                 i--;
 362                 if(i < 0)
 363                         i = LOG-1;
 364                 p->forwd = P;
 365                 dwn[i]--;
 366                 if(dwn[i] <= 0) {
 367                         dwn[i] = cnt[i];
 368                         if(lst[i] != P)
 369                                 lst[i]->forwd = p;
 370                         lst[i] = p;
 371                 }
 372         }
 373 }
 374
 375 Prog*
 376 brloop(Prog *p)
 377 {
 378         int c;
 379         Prog *q;
 380
 381         c = 0;
 382         for(q = p; q != P; q = q->pcond) {
 383                 if(q->as != ABRA)
 384                         break;
 385                 c++;
 386                 if(c >= 5000)
 387                         return P;
 388         }
 389         return q;
 390 }
 391
 392 void
 393 dostkoff(void)
 394 {
 395         Prog *p, *q;
 396         long s, t;
 397         int a;
 398         Optab *o;
 399
 400         if(debug['v'])
 401                 Bprint(&bso, "%5.2f stkoff\n", cputime());
 402         Bflush(&bso);
 403         s = 0;
 404         for(p = firstp; p != P; p = p->link) {
 405                 if(p->as == ATEXT) {
 406                         curtext = p;
 407                         s = p->to.offset;
 408                         if(s == 0)
 409                                 continue;
 410                         p = appendp(p);
 411                         p->as = AADJSP;
 412                         p->from.type = D_CONST;
 413                         p->from.offset = s;
 414                         p->stkoff = 0;
 415                         continue;
 416                 }
 417                 for(q = p; q != P; q = q->pcond) {
 418                         if(q->as == ATEXT)
 419                                 break;
 420                         if(q->stkoff >= 0)
 421                                 if(q->stkoff != s)
 422                                         diag("stack offset %ld is %ld sb %ld in %s\n%P",
 423                                                 q->pc, q->stkoff, s, TNAME, p);
 424                         q->stkoff = s;
 425                 }
 426                 o = &optab[p->as];
 427                 if(p->to.type == D_TOS)
 428                         s -= o->dstsp;
 429                 if(p->from.type == D_TOS)
 430                         s -= o->srcsp;
 431                 if(p->as == AADJSP)
 432                         s += p->from.offset;
 433                 if(p->as == APEA)
 434                         s += 4;
 435                 for(q = p->link; q != P; q = q->pcond) {
 436                         if(q->as == ATEXT) {
 437                                 q = P;
 438                                 break;
 439                         }
 440                         if(q->stkoff >= 0)
 441                                 break;
 442                 }
 443                 if(q == P || q->stkoff == s)
 444                         continue;
 445                 if(p->as == ABRA || p->as == ARTS || p->as == ARTE) {
 446                         s = q->stkoff;
 447                         continue;
 448                 }
 449                 if(p->link->as == ABCASE)
 450                         diag("BCASE with stack offset in %s", TNAME);
 451                 t = q->stkoff - s;
 452                 s = q->stkoff;
 453                 p = appendp(p);
 454                 p->as = AADJSP;
 455                 p->stkoff = s - t;
 456                 p->from.type = D_CONST;
 457                 p->from.offset = t;
 458         }
 459
 460         for(p = firstp; p != P; p = p->link) {
 461                 if(p->as == ATEXT)
 462                         curtext = p;
 463                 a = p->from.type & D_MASK;
 464                 if(a == D_AUTO)
 465                         p->from.offset += p->stkoff;
 466                 if(a == D_PARAM)
 467                         p->from.offset += p->stkoff + 4;
 468                 a = p->to.type & D_MASK;
 469                 if(a == D_AUTO)
 470                         p->to.offset += p->stkoff;
 471                 if(a == D_PARAM)
 472                         p->to.offset += p->stkoff + 4;
 473                 if(p->as != ARTS)
 474                         continue;
 475                 if(p->stkoff == 0)
 476                         continue;
 477                 q = p;
 478                 p = appendp(p);
 479                 p->as = ARTS;
 480                 p->stkoff = 0;
 481
 482                 q->as = AADJSP;
 483                 q->from.type = D_CONST;
 484                 q->from.offset = -q->stkoff;
 485         }
 486 }
 487
 488 long
 489 atolwhex(char *s)
 490 {
 491         long n;
 492         int f;
 493
 494         n = 0;
 495         f = 0;
 496         while(*s == ' ' || *s == '\t')
 497                 s++;
 498         if(*s == '-' || *s == '+') {
 499                 if(*s++ == '-')
 500                         f = 1;
 501                 while(*s == ' ' || *s == '\t')
 502                         s++;
 503         }
 504         if(s[0]=='0' && s[1]){
 505                 if(s[1]=='x' || s[1]=='X'){
 506                         s += 2;
 507                         for(;;){
 508                                 if(*s >= '0' && *s <= '9')
 509                                         n = n*16 + *s++ - '0';
 510                                 else if(*s >= 'a' && *s <= 'f')
 511                                         n = n*16 + *s++ - 'a' + 10;
 512                                 else if(*s >= 'A' && *s <= 'F')
 513                                         n = n*16 + *s++ - 'A' + 10;
 514                                 else
 515                                         break;
 516                         }
 517                 } else
 518                         while(*s >= '0' && *s <= '7')
 519                                 n = n*8 + *s++ - '0';
 520         } else
 521                 while(*s >= '0' && *s <= '9')
 522                         n = n*10 + *s++ - '0';
 523         if(f)
 524                 n = -n;
 525         return n;
 526 }
 527
 528 void
 529 undef(void)
 530 {
 531         int i;
 532         Sym *s;
 533
 534         for(i=0; i<NHASH; i++)
 535         for(s = hash[i]; s != S; s = s->link)
 536                 if(s->type == SXREF)
 537                         diag("%s: not defined", s->name);
 538 }