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