sys/src/cmd/kl/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 && v <= 0xffff)
 144                                 continue;
 145                         if(!(v & 0xffff))
 146                                 continue;
 147                         /* size should be 9 max */
 148                         snprint(literal, sizeof literal, "$%lux", v);
 149                 }
 150                 s = lookup(literal, 0);
 151                 if(s->type == 0) {
 152                         s->type = SDATA;
 153                         s->value = orig1+orig;
 154                         orig += 4;
 155                         p1 = prg();
 156                         p1->as = ADATA;
 157                         p1->line = p->line;
 158                         p1->from.type = D_OREG;
 159                         p1->from.sym = s;
 160                         p1->from.name = D_EXTERN;
 161                         p1->reg = 4;
 162                         p1->to = p->from;
 163                         p1->link = datap;
 164                         datap = p1;
 165                 }
 166                 if(s->type != SDATA)
 167                         diag("literal not data: %s", s->name);
 168                 p->from.type = D_OREG;
 169                 p->from.sym = s;
 170                 p->from.name = D_EXTERN;
 171                 p->from.offset = 0;
 172                 continue;
 173         }
 174         while(orig & 7)
 175                 orig++;
 176         /*
 177          * pass 5
 178          *      re-adjust offsets
 179          */
 180         for(i=0; i<NHASH; i++)
 181         for(s = hash[i]; s != S; s = s->link) {
 182                 t = s->type;
 183                 if(t == SBSS) {
 184                         s->value += orig;
 185                         continue;
 186                 }
 187                 if(t == SDATA1) {
 188                         s->type = SDATA;
 189                         s->value += orig;
 190                         continue;
 191                 }
 192         }
 193         datsize += orig;
 194         xdefine("setSB", SDATA, 0L+BIG);
 195         xdefine("bdata", SDATA, 0L);
 196         xdefine("edata", SDATA, datsize);
 197         xdefine("end", SBSS, datsize+bsssize);
 198         xdefine("etext", STEXT, 0L);
 199 }
 200
 201 void
 202 undef(void)
 203 {
 204         int i;
 205         Sym *s;
 206
 207         for(i=0; i<NHASH; i++)
 208         for(s = hash[i]; s != S; s = s->link)
 209                 if(s->type == SXREF)
 210                         diag("%s: not defined", s->name);
 211 }
 212
 213 int
 214 relinv(int a)
 215 {
 216
 217         switch(a) {
 218         case ABA:       return ABN;
 219         case ABN:       return ABA;
 220
 221         case ABE:       return ABNE;
 222         case ABNE:      return ABE;
 223
 224         case ABLE:      return ABG;
 225         case ABG:       return ABLE;
 226
 227         case ABL:       return ABGE;
 228         case ABGE:      return ABL;
 229
 230         case ABLEU:     return ABGU;
 231         case ABGU:      return ABLEU;
 232
 233         case ABCS:      return ABCC;
 234         case ABCC:      return ABCS;
 235
 236         case ABNEG:     return ABPOS;
 237         case ABPOS:     return ABNEG;
 238
 239         case ABVC:      return ABVS;
 240         case ABVS:      return ABVC;
 241
 242         case AFBN:      return AFBA;
 243         case AFBA:      return AFBN;
 244
 245         case AFBE:      return AFBLG;
 246         case AFBLG:     return AFBE;
 247
 248         case AFBG:      return AFBLE;
 249         case AFBLE:     return AFBG;
 250
 251         case AFBGE:     return AFBL;
 252         case AFBL:      return AFBGE;
 253
 254         /* unordered fp compares have no inverse
 255                 that traps in the same way */
 256         }
 257         return 0;
 258 }
 259
 260 void
 261 follow(void)
 262 {
 263
 264         if(debug['v'])
 265                 Bprint(&bso, "%5.2f follow\n", cputime());
 266         Bflush(&bso);
 267
 268         firstp = prg();
 269         lastp = firstp;
 270
 271         xfol(textp);
 272
 273         firstp = firstp->link;
 274         lastp->link = P;
 275 }
 276
 277 void
 278 xfol(Prog *p)
 279 {
 280         Prog *q, *r;
 281         int a, b, i;
 282
 283 loop:
 284         if(p == P)
 285                 return;
 286         a = p->as;
 287         if(a == ATEXT)
 288                 curtext = p;
 289         if(a == AJMP) {
 290                 q = p->cond;
 291                 if((p->mark&NOSCHED) || q && (q->mark&NOSCHED)){
 292                         p->mark |= FOLL;
 293                         lastp->link = p;
 294                         lastp = p;
 295                         p = p->link;
 296                         xfol(p);
 297                         p = q;
 298                         if(p && !(p->mark & FOLL))
 299                                 goto loop;
 300                         return;
 301                 }
 302                 if(q != P) {
 303                         p->mark |= FOLL;
 304                         p = q;
 305                         if(!(p->mark & FOLL))
 306                                 goto loop;
 307                 }
 308         }
 309         if(p->mark & FOLL) {
 310                 for(i=0,q=p; i<4; i++,q=q->link) {
 311                         if(q == lastp || (q->mark&NOSCHED))
 312                                 break;
 313                         b = 0;          /* set */
 314                         a = q->as;
 315                         if(a == ANOP) {
 316                                 i--;
 317                                 continue;
 318                         }
 319                         if(a == AJMP || a == ARETURN || a == ARETT)
 320                                 goto copy;
 321                         if(!q->cond || (q->cond->mark&FOLL))
 322                                 continue;
 323                         b = relinv(a);
 324                         if(!b)
 325                                 continue;
 326                 copy:
 327                         for(;;) {
 328                                 r = prg();
 329                                 *r = *p;
 330                                 if(!(r->mark&FOLL))
 331                                         print("cant happen 1\n");
 332                                 r->mark |= FOLL;
 333                                 if(p != q) {
 334                                         p = p->link;
 335                                         lastp->link = r;
 336                                         lastp = r;
 337                                         continue;
 338                                 }
 339                                 lastp->link = r;
 340                                 lastp = r;
 341                                 if(a == AJMP || a == ARETURN || a == ARETT)
 342                                         return;
 343                                 r->as = b;
 344                                 r->cond = p->link;
 345                                 r->link = p->cond;
 346                                 if(!(r->link->mark&FOLL))
 347                                         xfol(r->link);
 348                                 if(!(r->cond->mark&FOLL))
 349                                         print("cant happen 2\n");
 350                                 return;
 351                         }
 352                 }
 353
 354                 a = AJMP;
 355                 q = prg();
 356                 q->as = a;
 357                 q->line = p->line;
 358                 q->to.type = D_BRANCH;
 359                 q->to.offset = p->pc;
 360                 q->cond = p;
 361                 p = q;
 362         }
 363         p->mark |= FOLL;
 364         lastp->link = p;
 365         lastp = p;
 366         if(a == AJMP || a == ARETURN || a == ARETT){
 367                 if(p->mark & NOSCHED){
 368                         p = p->link;
 369                         goto loop;
 370                 }
 371                 return;
 372         }
 373         if(p->cond != P)
 374         if(a != AJMPL && p->link != P) {
 375                 xfol(p->link);
 376                 p = p->cond;
 377                 if(p == P || (p->mark&FOLL))
 378                         return;
 379                 goto loop;
 380         }
 381         p = p->link;
 382         goto loop;
 383 }
 384
 385 void
 386 patch(void)
 387 {
 388         long c, vexit;
 389         Prog *p, *q;
 390         Sym *s;
 391         int a;
 392
 393         if(debug['v'])
 394                 Bprint(&bso, "%5.2f patch\n", cputime());
 395         Bflush(&bso);
 396         mkfwd();
 397         s = lookup("exit", 0);
 398         vexit = s->value;
 399         for(p = firstp; p != P; p = p->link) {
 400                 a = p->as;
 401                 if(a == ATEXT)
 402                         curtext = p;
 403                 if((a == AJMPL || a == ARETURN) && p->to.sym != S) {
 404                         s = p->to.sym;
 405                         if(s->type != STEXT) {
 406                                 diag("undefined: %s\n%P", s->name, p);
 407                                 s->type = STEXT;
 408                                 s->value = vexit;
 409                         }
 410                         p->to.offset = s->value;
 411                         p->to.type = D_BRANCH;
 412                 }
 413                 if(p->to.type != D_BRANCH)
 414                         continue;
 415                 c = p->to.offset;
 416                 for(q = firstp; q != P;) {
 417                         if(q->forwd != P)
 418                         if(c >= q->forwd->pc) {
 419                                 q = q->forwd;
 420                                 continue;
 421                         }
 422                         if(c == q->pc)
 423                                 break;
 424                         q = q->link;
 425                 }
 426                 if(q == P) {
 427                         diag("branch out of range %ld\n%P", c, p);
 428                         p->to.type = D_NONE;
 429                 }
 430                 p->cond = q;
 431         }
 432
 433         for(p = firstp; p != P; p = p->link) {
 434                 if(p->as == ATEXT)
 435                         curtext = p;
 436                 if(p->cond != P) {
 437                         p->cond = brloop(p->cond);
 438                         if(p->cond != P)
 439                         if(p->to.type == D_BRANCH)
 440                                 p->to.offset = p->cond->pc;
 441                 }
 442         }
 443 }
 444
 445 #define LOG     5
 446 void
 447 mkfwd(void)
 448 {
 449         Prog *p;
 450         long dwn[LOG], cnt[LOG], i;
 451         Prog *lst[LOG];
 452
 453         for(i=0; i<LOG; i++) {
 454                 if(i == 0)
 455                         cnt[i] = 1; else
 456                         cnt[i] = LOG * cnt[i-1];
 457                 dwn[i] = 1;
 458                 lst[i] = P;
 459         }
 460         i = 0;
 461         for(p = firstp; p != P; p = p->link) {
 462                 if(p->as == ATEXT)
 463                         curtext = p;
 464                 i--;
 465                 if(i < 0)
 466                         i = LOG-1;
 467                 p->forwd = P;
 468                 dwn[i]--;
 469                 if(dwn[i] <= 0) {
 470                         dwn[i] = cnt[i];
 471                         if(lst[i] != P)
 472                                 lst[i]->forwd = p;
 473                         lst[i] = p;
 474                 }
 475         }
 476 }
 477
 478 Prog*
 479 brloop(Prog *p)
 480 {
 481         Prog *q;
 482         int c;
 483
 484         for(c=0; p!=P;) {
 485                 if(p->as != AJMP || (p->mark&NOSCHED))
 486                         return p;
 487                 q = p->cond;
 488                 if(q <= p) {
 489                         c++;
 490                         if(q == p || c > 5000)
 491                                 break;
 492                 }
 493                 p = q;
 494         }
 495         return P;
 496 }
 497
 498 long
 499 atolwhex(char *s)
 500 {
 501         long n;
 502         int f;
 503
 504         n = 0;
 505         f = 0;
 506         while(*s == ' ' || *s == '\t')
 507                 s++;
 508         if(*s == '-' || *s == '+') {
 509                 if(*s++ == '-')
 510                         f = 1;
 511                 while(*s == ' ' || *s == '\t')
 512                         s++;
 513         }
 514         if(s[0]=='0' && s[1]){
 515                 if(s[1]=='x' || s[1]=='X'){
 516                         s += 2;
 517                         for(;;){
 518                                 if(*s >= '0' && *s <= '9')
 519                                         n = n*16 + *s++ - '0';
 520                                 else if(*s >= 'a' && *s <= 'f')
 521                                         n = n*16 + *s++ - 'a' + 10;
 522                                 else if(*s >= 'A' && *s <= 'F')
 523                                         n = n*16 + *s++ - 'A' + 10;
 524                                 else
 525                                         break;
 526                         }
 527                 } else
 528                         while(*s >= '0' && *s <= '7')
 529                                 n = n*8 + *s++ - '0';
 530         } else
 531                 while(*s >= '0' && *s <= '9')
 532                         n = n*10 + *s++ - '0';
 533         if(f)
 534                 n = -n;
 535         return n;
 536 }
 537
 538 long
 539 rnd(long v, long r)
 540 {
 541         long c;
 542
 543         if(r <= 0)
 544                 return v;
 545         v += r - 1;
 546         c = v % r;
 547         if(c < 0)
 548                 c += r;
 549         v -= c;
 550         return v;
 551 }