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