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