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