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