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