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