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         uint canfold:1;
 217         uint hasid:1;
 218         uint idval:1; /* identity value 0/1 */
 219 };
 220
 221 struct Ins {
 222         uint op:30;
 223         uint cls:2;
 224         Ref to;
 225         Ref arg[2];
 226 };
 227
 228 struct Phi {
 229         Ref to;
 230         Ref *arg;
 231         Blk **blk;
 232         uint narg;
 233         int cls;
 234         Phi *link;
 235 };
 236
 237 struct Blk {
 238         Phi *phi;
 239         Ins *ins;
 240         uint nins;
 241         struct {
 242                 short type;
 243                 Ref arg;
 244         } jmp;
 245         Blk *s1;
 246         Blk *s2;
 247         Blk *link;
 248
 249         uint id;
 250         uint visit;
 251
 252         Blk *idom;
 253         Blk *dom, *dlink;
 254         Blk **fron;
 255         uint nfron;
 256
 257         Blk **pred;
 258         uint npred;
 259         BSet in[1], out[1], gen[1];
 260         int nlive[2];
 261         int loop;
 262         char name[NString];
 263 };
 264
 265 struct Use {
 266         enum {
 267                 UXXX,
 268                 UPhi,
 269                 UIns,
 270                 UJmp,
 271         } type;
 272         uint bid;
 273         union {
 274                 Ins *ins;
 275                 Phi *phi;
 276         } u;
 277 };
 278
 279 struct Sym {
 280         enum {
 281                 SGlo,
 282                 SThr,
 283         } type;
 284         uint32_t id;
 285 };
 286
 287 struct Num {
 288         uchar n;
 289         uchar nl, nr;
 290         Ref l, r;
 291 };
 292
 293 enum {
 294         NoAlias,
 295         MayAlias,
 296         MustAlias
 297 };
 298
 299 struct Alias {
 300         enum {
 301                 ABot = 0,
 302                 ALoc = 1, /* stack local */
 303                 ACon = 2,
 304                 AEsc = 3, /* stack escaping */
 305                 ASym = 4,
 306                 AUnk = 6,
 307         #define astack(t) ((t) & 1)
 308         } type;
 309         int base;
 310         int64_t offset;
 311         union {
 312                 Sym sym;
 313                 struct {
 314                         int sz; /* -1 if > NBit */
 315                         bits m;
 316                 } loc;
 317         } u;
 318         Alias *slot;
 319 };
 320
 321 struct Tmp {
 322         char name[NString];
 323         Ins *def;
 324         Use *use;
 325         uint ndef, nuse;
 326         uint bid; /* id of a defining block */
 327         uint cost;
 328         int slot; /* -1 for unset */
 329         short cls;
 330         struct {
 331                 int r;  /* register or -1 */
 332                 int w;  /* weight */
 333                 bits m; /* avoid these registers */
 334         } hint;
 335         int phi;
 336         Alias alias;
 337         enum {
 338                 WFull,
 339                 Wsb, /* must match Oload/Oext order */
 340                 Wub,
 341                 Wsh,
 342                 Wuh,
 343                 Wsw,
 344                 Wuw
 345         } width;
 346         int visit;
 347 };
 348
 349 struct Con {
 350         enum {
 351                 CUndef,
 352                 CBits,
 353                 CAddr,
 354         } type;
 355         Sym sym;
 356         union {
 357                 int64_t i;
 358                 double d;
 359                 float s;
 360         } bits;
 361         char flt; /* 1 to print as s, 2 to print as d */
 362 };
 363
 364 typedef struct Addr Addr;
 365
 366 struct Addr { /* amd64 addressing */
 367         Con offset;
 368         Ref base;
 369         Ref index;
 370         int scale;
 371 };
 372
 373 struct Lnk {
 374         char export;
 375         char thread;
 376         char common;
 377         char align;
 378         char *sec;
 379         char *secf;
 380 };
 381
 382 struct Fn {
 383         Blk *start;
 384         Tmp *tmp;
 385         Con *con;
 386         Mem *mem;
 387         int ntmp;
 388         int ncon;
 389         int nmem;
 390         uint nblk;
 391         int retty; /* index in typ[], -1 if no aggregate return */
 392         Ref retr;
 393         Blk **rpo;
 394         bits reg;
 395         int slot;
 396         char vararg;
 397         char dynalloc;
 398         char name[NString];
 399         Lnk lnk;
 400 };
 401
 402 struct Typ {
 403         char name[NString];
 404         char isdark;
 405         char isunion;
 406         int align;
 407         uint64_t size;
 408         uint nunion;
 409         struct Field {
 410                 enum {
 411                         FEnd,
 412                         Fb,
 413                         Fh,
 414                         Fw,
 415                         Fl,
 416                         Fs,
 417                         Fd,
 418                         FPad,
 419                         FTyp,
 420                 } type;
 421                 uint len; /* or index in typ[] for FTyp */
 422         } (*fields)[NField+1];
 423 };
 424
 425 struct Dat {
 426         enum {
 427                 DStart,
 428                 DEnd,
 429                 DB,
 430                 DH,
 431                 DW,
 432                 DL,
 433                 DZ
 434         } type;
 435         char *name;
 436         Lnk *lnk;
 437         union {
 438                 int64_t num;
 439                 double fltd;
 440                 float flts;
 441                 char *str;
 442                 struct {
 443                         char *name;
 444                         int64_t off;
 445                 } ref;
 446         } u;
 447         char isref;
 448         char isstr;
 449 };
 450
 451 /* main.c */
 452 extern Target T;
 453 extern char debug['Z'+1];
 454
 455 /* util.c */
 456 typedef enum {
 457         PHeap, /* free() necessary */
 458         PFn, /* discarded after processing the function */
 459 } Pool;
 460
 461 extern Typ *typ;
 462 extern Ins insb[NIns], *curi;
 463 uint32_t hash(char *);
 464 void die_(char *, char *, ...) __attribute__((noreturn));
 465 void *emalloc(size_t);
 466 void *alloc(size_t);
 467 void freeall(void);
 468 void *vnew(ulong, size_t, Pool);
 469 void vfree(void *);
 470 void vgrow(void *, ulong);
 471 void strf(char[NString], char *, ...);
 472 uint32_t intern(char *);
 473 char *str(uint32_t);
 474 int argcls(Ins *, int);
 475 int isreg(Ref);
 476 int iscmp(int, int *, int *);
 477 void emit(int, int, Ref, Ref, Ref);
 478 void emiti(Ins);
 479 void idup(Ins **, Ins *, ulong);
 480 Ins *icpy(Ins *, Ins *, ulong);
 481 int cmpop(int);
 482 int cmpneg(int);
 483 int clsmerge(short *, short);
 484 int phicls(int, Tmp *);
 485 Ref newtmp(char *, int, Fn *);
 486 void chuse(Ref, int, Fn *);
 487 int symeq(Sym, Sym);
 488 Ref newcon(Con *, Fn *);
 489 Ref getcon(int64_t, Fn *);
 490 int addcon(Con *, Con *, int);
 491 void salloc(Ref, Ref, Fn *);
 492 void dumpts(BSet *, Tmp *, FILE *);
 493 void runmatch(uchar *, Num *, Ref, Ref *);
 494
 495 void bsinit(BSet *, uint);
 496 void bszero(BSet *);
 497 uint bscount(BSet *);
 498 void bsset(BSet *, uint);
 499 void bsclr(BSet *, uint);
 500 void bscopy(BSet *, BSet *);
 501 void bsunion(BSet *, BSet *);
 502 void bsinter(BSet *, BSet *);
 503 void bsdiff(BSet *, BSet *);
 504 int bsequal(BSet *, BSet *);
 505 int bsiter(BSet *, int *);
 506
 507 static inline int
 508 bshas(BSet *bs, uint elt)
 509 {
 510         assert(elt < bs->nt * NBit);
 511         return (bs->t[elt/NBit] & BIT(elt%NBit)) != 0;
 512 }
 513
 514 /* parse.c */
 515 extern Op optab[NOp];
 516 void parse(FILE *, char *, void (char *), void (Dat *), void (Fn *));
 517 void printfn(Fn *, FILE *);
 518 void printref(Ref, Fn *, FILE *);
 519 void err(char *, ...) __attribute__((noreturn));
 520
 521 /* abi.c */
 522 void elimsb(Fn *);
 523
 524 /* cfg.c */
 525 Blk *newblk(void);
 526 void edgedel(Blk *, Blk **);
 527 void fillpreds(Fn *);
 528 void fillrpo(Fn *);
 529 void filldom(Fn *);
 530 int sdom(Blk *, Blk *);
 531 int dom(Blk *, Blk *);
 532 void fillfron(Fn *);
 533 void loopiter(Fn *, void (*)(Blk *, Blk *));
 534 void fillloop(Fn *);
 535 void simpljmp(Fn *);
 536
 537 /* mem.c */
 538 void promote(Fn *);
 539 void coalesce(Fn *);
 540
 541 /* alias.c */
 542 void fillalias(Fn *);
 543 void getalias(Alias *, Ref, Fn *);
 544 int alias(Ref, int, int, Ref, int, int *, Fn *);
 545 int escapes(Ref, Fn *);
 546
 547 /* load.c */
 548 int loadsz(Ins *);
 549 int storesz(Ins *);
 550 void loadopt(Fn *);
 551
 552 /* ssa.c */
 553 void filluse(Fn *);
 554 void ssa(Fn *);
 555 void ssacheck(Fn *);
 556
 557 /* copy.c */
 558 void copy(Fn *);
 559
 560 /* fold.c */
 561 void fold(Fn *);
 562
 563 /* simpl.c */
 564 void simpl(Fn *);
 565
 566 /* live.c */
 567 void liveon(BSet *, Blk *, Blk *);
 568 void filllive(Fn *);
 569
 570 /* spill.c */
 571 void fillcost(Fn *);
 572 void spill(Fn *);
 573
 574 /* rega.c */
 575 void rega(Fn *);
 576
 577 /* emit.c */
 578 void emitfnlnk(char *, Lnk *, FILE *);
 579 void emitdat(Dat *, FILE *);
 580 void emitdbgfile(char *, FILE *);
 581 void emitdbgloc(uint, uint, FILE *);
 582 int stashbits(void *, int);
 583 void elf_emitfnfin(char *, FILE *);
 584 void elf_emitfin(FILE *);
 585 void macho_emitfin(FILE *);