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

   1 #include        "l.h"
   2
   3 vlong
   4 atolwhex(char *s)
   5 {
   6         vlong n;
   7         int f;
   8
   9         n = 0;
  10         f = 0;
  11         while(*s == ' ' || *s == '\t')
  12                 s++;
  13         if(*s == '-' || *s == '+') {
  14                 if(*s++ == '-')
  15                         f = 1;
  16                 while(*s == ' ' || *s == '\t')
  17                         s++;
  18         }
  19         if(s[0]=='0' && s[1]){
  20                 if(s[1]=='x' || s[1]=='X'){
  21                         s += 2;
  22                         for(;;){
  23                                 if(*s >= '0' && *s <= '9')
  24                                         n = n*16 + *s++ - '0';
  25                                 else if(*s >= 'a' && *s <= 'f')
  26                                         n = n*16 + *s++ - 'a' + 10;
  27                                 else if(*s >= 'A' && *s <= 'F')
  28                                         n = n*16 + *s++ - 'A' + 10;
  29                                 else
  30                                         break;
  31                         }
  32                 } else
  33                         while(*s >= '0' && *s <= '7')
  34                                 n = n*8 + *s++ - '0';
  35         } else
  36                 while(*s >= '0' && *s <= '9')
  37                         n = n*10 + *s++ - '0';
  38         if(f)
  39                 n = -n;
  40         return n;
  41 }
  42
  43 vlong
  44 rnd(vlong v, long r)
  45 {
  46         long c;
  47
  48         if(r <= 0)
  49                 return v;
  50         v += r - 1;
  51         c = v % r;
  52         if(c < 0)
  53                 c += r;
  54         v -= c;
  55         return v;
  56 }
  57
  58 void
  59 dodata(void)
  60 {
  61         int i, t;
  62         Sym *s;
  63         Prog *p;
  64         long orig, v;
  65
  66         if(debug['v'])
  67                 Bprint(&bso, "%5.2f dodata\n", cputime());
  68         Bflush(&bso);
  69         for(p = datap; p != P; p = p->link) {
  70                 s = p->from.sym;
  71                 if(p->as == ADYNT || p->as == AINIT)
  72                         s->value = dtype;
  73                 if(s->type == SBSS)
  74                         s->type = SDATA;
  75                 if(s->type != SDATA)
  76                         diag("initialize non-data (%d): %s\n%P",
  77                                 s->type, s->name, p);
  78                 v = p->from.offset + p->reg;
  79                 if(v > s->value)
  80                         diag("initialize bounds (%lld): %s\n%P",
  81                                 (vlong)s->value, s->name, p);
  82         }
  83
  84         if(debug['t']) {
  85                 /*
  86                  * pull out string constants
  87                  */
  88                 for(p = datap; p != P; p = p->link) {
  89                         s = p->from.sym;
  90                         if(p->to.type == D_SCONST)
  91                                 s->type = SSTRING;
  92                 }
  93         }
  94
  95         /*
  96          * pass 1
  97          *      assign 'small' variables to data segment
  98          *      (rationale is that data segment is more easily
  99          *       addressed through offset on REGSB)
 100          */
 101         orig = 0;
 102         for(i=0; i<NHASH; i++)
 103         for(s = hash[i]; s != S; s = s->link) {
 104                 t = s->type;
 105                 if(t != SDATA && t != SBSS)
 106                         continue;
 107                 v = s->value;
 108                 if(v == 0) {
 109                         diag("%s: no size", s->name);
 110                         v = 1;
 111                 }
 112                 v = rnd(v, 4);
 113                 s->value = v;
 114                 if(v > MINSIZ)
 115                         continue;
 116                 if(v >= 16)
 117                         orig = rnd(orig, 16);
 118                 else if(v >= 8)
 119                         orig = rnd(orig, 8);
 120                 s->value = orig;
 121                 orig += v;
 122                 s->type = SDATA1;
 123         }
 124
 125         /*
 126          * pass 2
 127          *      assign large 'data' variables to data segment
 128          */
 129         for(i=0; i<NHASH; i++)
 130         for(s = hash[i]; s != S; s = s->link) {
 131                 t = s->type;
 132                 if(t != SDATA) {
 133                         if(t == SDATA1)
 134                                 s->type = SDATA;
 135                         continue;
 136                 }
 137                 v = s->value;
 138                 if(v >= 16)
 139                         orig = rnd(orig, 16);
 140                 else if(v >= 8)
 141                         orig = rnd(orig, 8);
 142                 s->value = orig;
 143                 orig += v;
 144         }
 145
 146         while(orig & 7)
 147                 orig++;
 148         datsize = orig;
 149
 150         /*
 151          * pass 3
 152          *      everything else to bss segment
 153          */
 154         for(i=0; i<NHASH; i++)
 155         for(s = hash[i]; s != S; s = s->link) {
 156                 if(s->type != SBSS)
 157                         continue;
 158                 v = s->value;
 159                 if(v >= 16)
 160                         orig = rnd(orig, 16);
 161                 else if(v >= 8)
 162                         orig = rnd(orig, 8);
 163                 s->value = orig;
 164                 orig += v;
 165         }
 166         while(orig & 7)
 167                 orig++;
 168         bsssize = orig-datsize;
 169
 170         xdefine("setSB", SDATA, 0L);
 171         xdefine("bdata", SDATA, 0L);
 172         xdefine("edata", SDATA, datsize);
 173         xdefine("end", SBSS, datsize+bsssize);
 174         xdefine("etext", STEXT, 0L);
 175 }
 176
 177 Prog*
 178 brchain(Prog *p)
 179 {
 180         int i;
 181
 182         for(i=0; i<20; i++) {
 183                 if(p == P || !isbranch(p->as))
 184                         return p;
 185                 p = p->cond;
 186         }
 187         return P;
 188 }
 189
 190 void
 191 follow(void)
 192 {
 193         if(debug['v'])
 194                 Bprint(&bso, "%5.2f follow\n", cputime());
 195         Bflush(&bso);
 196
 197         firstp = prg();
 198         lastp = firstp;
 199         xfol(textp);
 200
 201         firstp = firstp->link;
 202         lastp->link = P;
 203 }
 204
 205 void
 206 xfol(Prog *p)
 207 {
 208         Prog *q, *r;
 209         int a, i;
 210
 211 loop:
 212         if(p == P)
 213                 return;
 214         a = p->as;
 215         if(a == ATEXT)
 216                 curtext = p;
 217         if(isbranch(a)) {
 218                 q = p->cond;
 219                 if(q != P) {
 220                         p->mark |= FOLL;
 221                         p = q;
 222                         if(!(p->mark & FOLL))
 223                                 goto loop;
 224                 }
 225         }
 226         if(p->mark & FOLL) {
 227                 for(i=0,q=p; i<4; i++,q=q->link) {
 228                         if(q == lastp)
 229                                 break;
 230                         a = q->as;
 231                         if(a == ANOP) {
 232                                 i--;
 233                                 continue;
 234                         }
 235                         if(isbranch(a) || isreturn(a))
 236                                 goto copy;
 237                         if(q->cond == nil || (q->cond->mark&FOLL))
 238                                 continue;
 239                         if(a != ABEQ && a != ABNE)
 240                                 continue;
 241                 copy:
 242                         for(;;) {
 243                                 r = prg();
 244                                 *r = *p;
 245                                 if(!(r->mark&FOLL))
 246                                         print("cant happen 1\n");
 247                                 r->mark |= FOLL;
 248                                 if(p != q) {
 249                                         p = p->link;
 250                                         lastp->link = r;
 251                                         lastp = r;
 252                                         continue;
 253                                 }
 254                                 lastp->link = r;
 255                                 lastp = r;
 256                                 if(isbranch(a) || isreturn(a))
 257                                         return;
 258                                 r->as = a == ABNE? ABEQ: ABNE;
 259                                 r->cond = p->link;
 260                                 r->link = p->cond;
 261                                 if(!(r->link->mark&FOLL))
 262                                         xfol(r->link);
 263                                 if(!(r->cond->mark&FOLL))
 264                                         print("cant happen 2\n");
 265                                 return;
 266                         }
 267                 }
 268                 a = branchop();
 269                 q = prg();
 270                 q->as = a;
 271                 q->line = p->line;
 272                 q->to.type = D_BRANCH;
 273                 q->to.offset = p->pc;
 274                 q->cond = p;
 275                 p = q;
 276         }
 277         p->mark |= FOLL;
 278         lastp->link = p;
 279         lastp = p;
 280         if(isbranch(a) || isreturn(a))
 281                 return;
 282         if(p->cond != P)
 283         if(!iscall(a) && p->link != P) {
 284                 q = brchain(p->link);
 285                 if(canfollow(a))
 286                 if(q != P && (q->mark&FOLL)) {
 287                         p->as = relinv(a);
 288                         p->link = p->cond;
 289                         p->cond = q;
 290                 }
 291                 xfol(p->link);
 292                 q = brchain(p->cond);
 293                 if(q == P)
 294                         q = p->cond;
 295                 if(q->mark&FOLL) {
 296                         p->cond = q;
 297                         return;
 298                 }
 299                 p = q;
 300                 goto loop;
 301         }
 302         p = p->link;
 303         goto loop;
 304 }
 305
 306 void
 307 patch(void)
 308 {
 309         long c, vexit;
 310         Prog *p, *q;
 311         Sym *s;
 312         int a;
 313
 314         if(debug['v'])
 315                 Bprint(&bso, "%5.2f patch\n", cputime());
 316         Bflush(&bso);
 317         mkfwd();
 318         s = lookup("exit", 0);
 319         vexit = s->value;
 320         for(p = firstp; p != P; p = p->link) {
 321                 a = p->as;
 322                 if(a == ATEXT)
 323                         curtext = p;
 324                 if((iscall(a) || isbranch(a) || isreturn(a)) &&
 325                    p->to.type != D_BRANCH && p->to.sym != S) {
 326                         s = p->to.sym;
 327                         switch(s->type) {
 328                         default:
 329                                 diag("undefined: %s\n%P", s->name, p);
 330                                 s->type = STEXT;
 331                                 s->value = vexit;
 332                                 break;
 333                         case STEXT:
 334                                 p->to.offset = s->value;
 335                                 break;
 336                         case SUNDEF:
 337                                 if(!iscall(p->as))
 338                                         diag("help: SUNDEF in AB || ARET");
 339                                 p->to.offset = 0;
 340                                 p->cond = UP;
 341                                 break;
 342                         }
 343                         p->to.type = D_BRANCH;
 344                 }
 345                 if(p->cond == UP)
 346                         continue;
 347                 if(p->to.type == D_BRANCH)
 348                         c = p->to.offset;
 349                 else if(p->from.type == D_BRANCH)
 350                         c = p->from.offset;
 351                 else
 352                         continue;
 353                 for(q = firstp; q != P;) {
 354                         if(q->forwd != P)
 355                         if(c >= q->forwd->pc) {
 356                                 q = q->forwd;
 357                                 continue;
 358                         }
 359                         if(c == q->pc)
 360                                 break;
 361                         q = q->link;
 362                 }
 363                 if(q == P) {
 364                         diag("branch out of range %ld\n%P", c, p);
 365                         p->to.type = D_NONE;
 366                 }
 367                 p->cond = q;
 368         }
 369
 370         for(p = firstp; p != P; p = p->link) {
 371                 if(p->as == ATEXT)
 372                         curtext = p;
 373                 if(p->cond != P && p->cond != UP) {
 374                         p->cond = brloop(p->cond);
 375                         if(p->cond != P){
 376                                 if(p->to.type == D_BRANCH)
 377                                         p->to.offset = p->cond->pc;
 378                                 if(p->from.type == D_BRANCH)
 379                                         p->from.offset = p->cond->pc;
 380                         }
 381                 }
 382         }
 383 }
 384
 385 #define LOG     6
 386 void
 387 mkfwd(void)
 388 {
 389         Prog *p;
 390         long dwn[LOG], cnt[LOG], i;
 391         Prog *lst[LOG];
 392
 393         for(i=0; i<LOG; i++) {
 394                 if(i == 0)
 395                         cnt[i] = 1; else
 396                         cnt[i] = LOG * cnt[i-1];
 397                 dwn[i] = 1;
 398                 lst[i] = P;
 399         }
 400         i = 0;
 401         for(p = firstp; p != P; p = p->link) {
 402                 if(p->as == ATEXT)
 403                         curtext = p;
 404                 i--;
 405                 if(i < 0)
 406                         i = LOG-1;
 407                 p->forwd = P;
 408                 dwn[i]--;
 409                 if(dwn[i] <= 0) {
 410                         dwn[i] = cnt[i];
 411                         if(lst[i] != P)
 412                                 lst[i]->forwd = p;
 413                         lst[i] = p;
 414                 }
 415         }
 416 }
 417
 418 Prog*
 419 brloop(Prog *p)
 420 {
 421         Prog *q;
 422         int c;
 423
 424         for(c=0; p!=P;) {
 425                 if(!isbranch(p->as))
 426                         return p;
 427                 q = p->cond;
 428                 if(q <= p) {
 429                         c++;
 430                         if(q == p || c > 5000)
 431                                 break;
 432                 }
 433                 p = q;
 434         }
 435         return P;
 436 }
 437
 438 void
 439 undef(void)
 440 {
 441         int i;
 442         Sym *s;
 443
 444         for(i=0; i<NHASH; i++)
 445         for(s = hash[i]; s != S; s = s->link)
 446                 if(s->type == SXREF)
 447                         diag("%s: not defined", s->name);
 448 }