all.h

   1 #include <assert.h>
   2 #include <inttypes.h>
   3 #include <limits.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7
   8 #define MAKESURE(what, x) typedef char make_sure_##what[(x)?1:-1]
   9 #define die(...) die_(__FILE__, __VA_ARGS__)
  10
  11 typedef unsigned char uchar;
  12 typedef unsigned int uint;
  13 typedef unsigned long ulong;
  14 typedef unsigned long long bits;
  15
  16 typedef struct BSet BSet;
  17 typedef struct Ref Ref;
  18 typedef struct Op Op;
  19 typedef struct Ins Ins;
  20 typedef struct Phi Phi;
  21 typedef struct Blk Blk;
  22 typedef struct Use Use;
  23 typedef struct Sym Sym;
  24 typedef struct Alias Alias;
  25 typedef struct Tmp Tmp;
  26 typedef struct Con Con;
  27 typedef struct Addr Mem;
  28 typedef struct Fn Fn;
  29 typedef struct Typ Typ;
  30 typedef struct Field Field;
  31 typedef struct Dat Dat;
  32 typedef struct Lnk Lnk;
  33 typedef struct Target Target;
  34
  35 enum {
  36         NString = 72,
  37         NIns    = 1 << 20,
  38         NAlign  = 3,
  39         NField  = 32,
  40         NBit    = CHAR_BIT * sizeof(bits),
  41 };
  42
  43 struct Target {
  44         char name[16];
  45         char apple;
  46         int gpr0;   /* first general purpose reg */
  47         int ngpr;
  48         int fpr0;   /* first floating point reg */
  49         int nfpr;
  50         bits rglob; /* globally live regs (e.g., sp, fp) */
  51         int nrglob;
  52         int *rsave; /* caller-save */
  53         int nrsave[2];
  54         bits (*retregs)(Ref, int[2]);
  55         bits (*argregs)(Ref, int[2]);
  56         int (*memargs)(int);
  57         void (*abi0)(Fn *);
  58         void (*abi1)(Fn *);
  59         void (*isel)(Fn *);
  60         void (*emitfn)(Fn *, FILE *);
  61         void (*emitfin)(FILE *);
  62         char asloc[4];
  63         char assym[4];
  64 };
  65
  66 #define BIT(n) ((bits)1 << (n))
  67
  68 enum {
  69         RXX = 0,
  70         Tmp0 = NBit, /* first non-reg temporary */
  71 };
  72
  73 struct BSet {
  74         uint nt;
  75         bits *t;
  76 };
  77
  78 struct Ref {
  79         uint type:3;
  80         uint val:29;
  81 };
  82
  83 enum {
  84         RTmp,
  85         RCon,
  86         RInt,
  87         RType, /* last kind to come out of the parser */
  88         RSlot,
  89         RCall,
  90         RMem,
  91 };
  92
  93 #define R        (Ref){RTmp, 0}
  94 #define UNDEF    (Ref){RCon, 0}  /* represents uninitialized data */
  95 #define CON_Z    (Ref){RCon, 1}
  96 #define TMP(x)   (Ref){RTmp, x}
  97 #define CON(x)   (Ref){RCon, x}
  98 #define SLOT(x)  (Ref){RSlot, (x)&0x1fffffff}
  99 #define TYPE(x)  (Ref){RType, x}
 100 #define CALL(x)  (Ref){RCall, x}
 101 #define MEM(x)   (Ref){RMem, x}
 102 #define INT(x)   (Ref){RInt, (x)&0x1fffffff}
 103
 104 static inline int req(Ref a, Ref b)
 105 {
 106         return a.type == b.type && a.val == b.val;
 107 }
 108
 109 static inline int rtype(Ref r)
 110 {
 111         if (req(r, R))
 112                 return -1;
 113         return r.type;
 114 }
 115
 116 static inline int rsval(Ref r)
 117 {
 118         return ((int32_t)r.val << 3) >> 3;
 119 }
 120
 121 enum CmpI {
 122         Cieq,
 123         Cine,
 124         Cisge,
 125         Cisgt,
 126         Cisle,
 127         Cislt,
 128         Ciuge,
 129         Ciugt,
 130         Ciule,
 131         Ciult,
 132         NCmpI,
 133 };
 134
 135 enum CmpF {
 136         Cfeq,
 137         Cfge,
 138         Cfgt,
 139         Cfle,
 140         Cflt,
 141         Cfne,
 142         Cfo,
 143         Cfuo,
 144         NCmpF,
 145         NCmp = NCmpI + NCmpF,
 146 };
 147
 148 enum O {
 149         Oxxx,
 150 #define O(op, x, y) O##op,
 151         #include "ops.h"
 152         NOp,
 153 };
 154
 155 enum J {
 156         Jxxx,
 157 #define JMPS(X)                                 \
 158         X(retw)   X(retl)   X(rets)   X(retd)   \
 159         X(retsb)  X(retub)  X(retsh)  X(retuh)  \
 160         X(retc)   X(ret0)   X(jmp)    X(jnz)    \
 161         X(jfieq)  X(jfine)  X(jfisge) X(jfisgt) \
 162         X(jfisle) X(jfislt) X(jfiuge) X(jfiugt) \
 163         X(jfiule) X(jfiult) X(jffeq)  X(jffge)  \
 164         X(jffgt)  X(jffle)  X(jfflt)  X(jffne)  \
 165         X(jffo)   X(jffuo)  X(hlt)
 166 #define X(j) J##j,
 167         JMPS(X)
 168 #undef X
 169         NJmp
 170 };
 171
 172 enum {
 173         Ocmpw = Oceqw,
 174         Ocmpw1 = Ocultw,
 175         Ocmpl = Oceql,
 176         Ocmpl1 = Ocultl,
 177         Ocmps = Oceqs,
 178         Ocmps1 = Ocuos,
 179         Ocmpd = Oceqd,
 180         Ocmpd1 = Ocuod,
 181         Oalloc = Oalloc4,
 182         Oalloc1 = Oalloc16,
 183         Oflag = Oflagieq,
 184         Oflag1 = Oflagfuo,
 185         NPubOp = Onop,
 186         Jjf = Jjfieq,
 187         Jjf1 = Jjffuo,
 188 };
 189
 190 #define INRANGE(x, l, u) ((unsigned)(x) - l <= u - l) /* linear in x */
 191 #define isstore(o) INRANGE(o, Ostoreb, Ostored)
 192 #define isload(o) INRANGE(o, Oloadsb, Oload)
 193 #define isext(o) INRANGE(o, Oextsb, Oextuw)
 194 #define ispar(o) INRANGE(o, Opar, Opare)
 195 #define isarg(o) INRANGE(o, Oarg, Oargv)
 196 #define isret(j) INRANGE(j, Jretw, Jret0)
 197 #define isparbh(o) INRANGE(o, Oparsb, Oparuh)
 198 #define isargbh(o) INRANGE(o, Oargsb, Oarguh)
 199 #define isretbh(j) INRANGE(j, Jretsb, Jretuh)
 200
 201 enum {
 202         Kx = -1, /* "top" class (see usecheck() and clsmerge()) */
 203         Kw,
 204         Kl,
 205         Ks,
 206         Kd
 207 };
 208
 209 #define KWIDE(k) ((k)&1)
 210 #define KBASE(k) ((k)>>1)
 211
 212 struct Op {
 213         char *name;
 214         short argcls[2][4];
 215         int canfold;
 216 };
 217
 218 struct Ins {
 219         uint op:30;
 220         uint cls:2;
 221         Ref to;
 222         Ref arg[2];
 223 };
 224
 225 struct Phi {
 226         Ref to;
 227         Ref *arg;
 228         Blk **blk;
 229         uint narg;
 230         int cls;
 231         Phi *link;
 232 };
 233
 234 struct Blk {
 235         Phi *phi;
 236         Ins *ins;
 237         uint nins;
 238         struct {
 239                 short type;
 240                 Ref arg;
 241         } jmp;
 242         Blk *s1;
 243         Blk *s2;
 244         Blk *link;
 245
 246         uint id;
 247         uint visit;
 248
 249         Blk *idom;
 250         Blk *dom, *dlink;
 251         Blk **fron;
 252         uint nfron;
 253
 254         Blk **pred;
 255         uint npred;
 256         BSet in[1], out[1], gen[1];
 257         int nlive[2];
 258         int loop;
 259         char name[NString];
 260 };
 261
 262 struct Use {
 263         enum {
 264                 UXXX,
 265                 UPhi,
 266                 UIns,
 267                 UJmp,
 268         } type;
 269         uint bid;
 270         union {
 271                 Ins *ins;
 272                 Phi *phi;
 273         } u;
 274 };
 275
 276 struct Sym {
 277         enum {
 278                 SGlo,
 279                 SThr,
 280         } type;
 281         uint32_t id;
 282 };
 283
 284 enum {
 285         NoAlias,
 286         MayAlias,
 287         MustAlias
 288 };
 289
 290 struct Alias {
 291         enum {
 292                 ABot = 0,
 293                 ALoc = 1, /* stack local */
 294                 ACon = 2,
 295                 AEsc = 3, /* stack escaping */
 296                 ASym = 4,
 297                 AUnk = 6,
 298         #define astack(t) ((t) & 1)
 299         } type;
 300         int base;
 301         int64_t offset;
 302         union {
 303                 Sym sym;
 304                 struct {
 305                         int sz; /* -1 if > NBit */
 306                         bits m;
 307                 } loc;
 308         } u;
 309         Alias *slot;
 310 };
 311
 312 struct Tmp {
 313         char name[NString];
 314         Ins *def;
 315         Use *use;
 316         uint ndef, nuse;
 317         uint bid; /* id of a defining block */
 318         uint cost;
 319         int slot; /* -1 for unset */
 320         short cls;
 321         struct {
 322                 int r;  /* register or -1 */
 323                 int w;  /* weight */
 324                 bits m; /* avoid these registers */
 325         } hint;
 326         int phi;
 327         Alias alias;
 328         enum {
 329                 WFull,
 330                 Wsb, /* must match Oload/Oext order */
 331                 Wub,
 332                 Wsh,
 333                 Wuh,
 334                 Wsw,
 335                 Wuw
 336         } width;
 337         int visit;
 338 };
 339
 340 struct Con {
 341         enum {
 342                 CUndef,
 343                 CBits,
 344                 CAddr,
 345         } type;
 346         Sym sym;
 347         union {
 348                 int64_t i;
 349                 double d;
 350                 float s;
 351         } bits;
 352         char flt; /* 1 to print as s, 2 to print as d */
 353 };
 354
 355 typedef struct Addr Addr;
 356
 357 struct Addr { /* amd64 addressing */
 358         Con offset;
 359         Ref base;
 360         Ref index;
 361         int scale;
 362 };
 363
 364 struct Lnk {
 365         char export;
 366         char thread;
 367         char align;
 368         char *sec;
 369         char *secf;
 370 };
 371
 372 struct Fn {
 373         Blk *start;
 374         Tmp *tmp;
 375         Con *con;
 376         Mem *mem;
 377         int ntmp;
 378         int ncon;
 379         int nmem;
 380         uint nblk;
 381         int retty; /* index in typ[], -1 if no aggregate return */
 382         Ref retr;
 383         Blk **rpo;
 384         bits reg;
 385         int slot;
 386         char vararg;
 387         char dynalloc;
 388         char name[NString];
 389         Lnk lnk;
 390 };
 391
 392 struct Typ {
 393         char name[NString];
 394         char isdark;
 395         char isunion;
 396         int align;
 397         uint64_t size;
 398         uint nunion;
 399         struct Field {
 400                 enum {
 401                         FEnd,
 402                         Fb,
 403                         Fh,
 404                         Fw,
 405                         Fl,
 406                         Fs,
 407                         Fd,
 408                         FPad,
 409                         FTyp,
 410                 } type;
 411                 uint len; /* or index in typ[] for FTyp */
 412         } (*fields)[NField+1];
 413 };
 414
 415 struct Dat {
 416         enum {
 417                 DStart,
 418                 DEnd,
 419                 DB,
 420                 DH,
 421                 DW,
 422                 DL,
 423                 DZ
 424         } type;
 425         char *name;
 426         Lnk *lnk;
 427         union {
 428                 int64_t num;
 429                 double fltd;
 430                 float flts;
 431                 char *str;
 432                 struct {
 433                         char *name;
 434                         int64_t off;
 435                 } ref;
 436         } u;
 437         char isref;
 438         char isstr;
 439 };
 440
 441 /* main.c */
 442 extern Target T;
 443 extern char debug['Z'+1];
 444
 445 /* util.c */
 446 typedef enum {
 447         PHeap, /* free() necessary */
 448         PFn, /* discarded after processing the function */
 449 } Pool;
 450
 451 extern Typ *typ;
 452 extern Ins insb[NIns], *curi;
 453 uint32_t hash(char *);
 454 void die_(char *, char *, ...) __attribute__((noreturn));
 455 void *emalloc(size_t);
 456 void *alloc(size_t);
 457 void freeall(void);
 458 void *vnew(ulong, size_t, Pool);
 459 void vfree(void *);
 460 void vgrow(void *, ulong);
 461 uint32_t intern(char *);
 462 char *str(uint32_t);
 463 int argcls(Ins *, int);
 464 int isreg(Ref);
 465 int iscmp(int, int *, int *);
 466 void emit(int, int, Ref, Ref, Ref);
 467 void emiti(Ins);
 468 void idup(Ins **, Ins *, ulong);
 469 Ins *icpy(Ins *, Ins *, ulong);
 470 int cmpop(int);
 471 int cmpneg(int);
 472 int clsmerge(short *, short);
 473 int phicls(int, Tmp *);
 474 Ref newtmp(char *, int, Fn *);
 475 void chuse(Ref, int, Fn *);
 476 int symeq(Sym, Sym);
 477 Ref newcon(Con *, Fn *);
 478 Ref getcon(int64_t, Fn *);
 479 int addcon(Con *, Con *);
 480 void salloc(Ref, Ref, Fn *);
 481 void dumpts(BSet *, Tmp *, FILE *);
 482
 483 void bsinit(BSet *, uint);
 484 void bszero(BSet *);
 485 uint bscount(BSet *);
 486 void bsset(BSet *, uint);
 487 void bsclr(BSet *, uint);
 488 void bscopy(BSet *, BSet *);
 489 void bsunion(BSet *, BSet *);
 490 void bsinter(BSet *, BSet *);
 491 void bsdiff(BSet *, BSet *);
 492 int bsequal(BSet *, BSet *);
 493 int bsiter(BSet *, int *);
 494
 495 static inline int
 496 bshas(BSet *bs, uint elt)
 497 {
 498         assert(elt < bs->nt * NBit);
 499         return (bs->t[elt/NBit] & BIT(elt%NBit)) != 0;
 500 }
 501
 502 /* parse.c */
 503 extern Op optab[NOp];
 504 void parse(FILE *, char *, void (Dat *), void (Fn *));
 505 void printfn(Fn *, FILE *);
 506 void printref(Ref, Fn *, FILE *);
 507 void err(char *, ...) __attribute__((noreturn));
 508
 509 /* abi.c */
 510 void elimsb(Fn *);
 511
 512 /* cfg.c */
 513 Blk *blknew(void);
 514 void edgedel(Blk *, Blk **);
 515 void fillpreds(Fn *);
 516 void fillrpo(Fn *);
 517 void filldom(Fn *);
 518 int sdom(Blk *, Blk *);
 519 int dom(Blk *, Blk *);
 520 void fillfron(Fn *);
 521 void loopiter(Fn *, void (*)(Blk *, Blk *));
 522 void fillloop(Fn *);
 523 void simpljmp(Fn *);
 524
 525 /* mem.c */
 526 void promote(Fn *);
 527 void coalesce(Fn *);
 528
 529 /* alias.c */
 530 void fillalias(Fn *);
 531 void getalias(Alias *, Ref, Fn *);
 532 int alias(Ref, int, int, Ref, int, int *, Fn *);
 533 int escapes(Ref, Fn *);
 534
 535 /* load.c */
 536 int loadsz(Ins *);
 537 int storesz(Ins *);
 538 void loadopt(Fn *);
 539
 540 /* ssa.c */
 541 void filluse(Fn *);
 542 void fillpreds(Fn *);
 543 void fillrpo(Fn *);
 544 void ssa(Fn *);
 545 void ssacheck(Fn *);
 546
 547 /* copy.c */
 548 void copy(Fn *);
 549
 550 /* fold.c */
 551 void fold(Fn *);
 552
 553 /* simpl.c */
 554 void simpl(Fn *);
 555
 556 /* live.c */
 557 void liveon(BSet *, Blk *, Blk *);
 558 void filllive(Fn *);
 559
 560 /* spill.c */
 561 void fillcost(Fn *);
 562 void spill(Fn *);
 563
 564 /* rega.c */
 565 void rega(Fn *);
 566
 567 /* emit.c */
 568 void emitfnlnk(char *, Lnk *, FILE *);
 569 void emitdat(Dat *, FILE *);
 570 int stashbits(void *, int);
 571 void elf_emitfnfin(char *, FILE *);
 572 void elf_emitfin(FILE *);
 573 void macho_emitfin(FILE *);