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 = 32,
  35         NPred   = 63,
  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 isstore(o) (Ostoreb <= o && o <= Ostored)
 175 #define isload(o) (Oloadsb <= o && o <= Oload)
 176 #define isext(o) (Oextsb <= o && o <= Oextuw)
 177 #define ispar(o) (Opar <= o && o <= Opare)
 178 #define isarg(o) (Oarg <= o && o <= Oarge)
 179 #define isret(j) (Jret0 <= j && j <= 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         Ref to;
 201         Ref arg[2];
 202         uint cls:2;
 203 };
 204
 205 struct Phi {
 206         Ref to;
 207         Ref arg[NPred];
 208         Blk *blk[NPred];
 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         int 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 cost;
 283         short slot; /* -1 for unset */
 284         short cls;
 285         struct {
 286                 int r;  /* register or -1 */
 287                 int w;  /* weight */
 288                 bits m; /* avoid these registers */
 289         } hint;
 290         int phi;
 291         Alias alias;
 292         enum {
 293                 WFull,
 294                 Wsb, /* must match Oload/Oext order */
 295                 Wub,
 296                 Wsh,
 297                 Wuh,
 298                 Wsw,
 299                 Wuw
 300         } width;
 301         int visit;
 302 };
 303
 304 struct Con {
 305         enum {
 306                 CUndef,
 307                 CBits,
 308                 CAddr,
 309         } type;
 310         uint32_t label;
 311         union {
 312                 int64_t i;
 313                 double d;
 314                 float s;
 315         } bits;
 316         char flt; /* 1 to print as s, 2 to print as d */
 317         char local;
 318 };
 319
 320 typedef struct Addr Addr;
 321
 322 struct Addr { /* amd64 addressing */
 323         Con offset;
 324         Ref base;
 325         Ref index;
 326         int scale;
 327 };
 328
 329 struct Fn {
 330         Blk *start;
 331         Tmp *tmp;
 332         Con *con;
 333         Mem *mem;
 334         int ntmp;
 335         int ncon;
 336         int nmem;
 337         uint nblk;
 338         int retty; /* index in typ[], -1 if no aggregate return */
 339         Ref retr;
 340         Blk **rpo;
 341         bits reg;
 342         int slot;
 343         char export;
 344         char vararg;
 345         char dynalloc;
 346         char name[NString];
 347 };
 348
 349 struct Typ {
 350         char name[NString];
 351         int dark;
 352         int align;
 353         uint64_t size;
 354         uint nunion;
 355         struct Field {
 356                 enum {
 357                         FEnd,
 358                         Fb,
 359                         Fh,
 360                         Fw,
 361                         Fl,
 362                         Fs,
 363                         Fd,
 364                         FPad,
 365                         FTyp,
 366                 } type;
 367                 uint len; /* or index in typ[] for FTyp */
 368         } (*fields)[NField+1];
 369 };
 370
 371 struct Dat {
 372         enum {
 373                 DStart,
 374                 DEnd,
 375                 DName,
 376                 DAlign,
 377                 DB,
 378                 DH,
 379                 DW,
 380                 DL,
 381                 DZ
 382         } type;
 383         union {
 384                 int64_t num;
 385                 double fltd;
 386                 float flts;
 387                 char *str;
 388                 struct {
 389                         char *nam;
 390                         int64_t off;
 391                 } ref;
 392         } u;
 393         char isref;
 394         char isstr;
 395         char export;
 396 };
 397
 398 /* main.c */
 399 extern Target T;
 400 extern char debug['Z'+1];
 401
 402 /* util.c */
 403 typedef enum {
 404         Pheap, /* free() necessary */
 405         Pfn, /* discarded after processing the function */
 406 } Pool;
 407
 408 extern Typ *typ;
 409 extern Ins insb[NIns], *curi;
 410 uint32_t hash(char *);
 411 void die_(char *, char *, ...) __attribute__((noreturn));
 412 void *emalloc(size_t);
 413 void *alloc(size_t);
 414 void freeall(void);
 415 void *vnew(ulong, size_t, Pool);
 416 void vfree(void *);
 417 void vgrow(void *, ulong);
 418 uint32_t intern(char *);
 419 char *str(uint32_t);
 420 int argcls(Ins *, int);
 421 int isreg(Ref);
 422 int iscmp(int, int *, int *);
 423 void emit(int, int, Ref, Ref, Ref);
 424 void emiti(Ins);
 425 void idup(Ins **, Ins *, ulong);
 426 Ins *icpy(Ins *, Ins *, ulong);
 427 int cmpop(int);
 428 int cmpneg(int);
 429 int clsmerge(short *, short);
 430 int phicls(int, Tmp *);
 431 Ref newtmp(char *, int, Fn *);
 432 void chuse(Ref, int, Fn *);
 433 Ref getcon(int64_t, Fn *);
 434 void addcon(Con *, Con *);
 435 void blit(Ref, uint, Ref, uint, Fn *);
 436 void dumpts(BSet *, Tmp *, FILE *);
 437
 438 void bsinit(BSet *, uint);
 439 void bszero(BSet *);
 440 uint bscount(BSet *);
 441 void bsset(BSet *, uint);
 442 void bsclr(BSet *, uint);
 443 void bscopy(BSet *, BSet *);
 444 void bsunion(BSet *, BSet *);
 445 void bsinter(BSet *, BSet *);
 446 void bsdiff(BSet *, BSet *);
 447 int bsequal(BSet *, BSet *);
 448 int bsiter(BSet *, int *);
 449
 450 static inline int
 451 bshas(BSet *bs, uint elt)
 452 {
 453         assert(elt < bs->nt * NBit);
 454         return (bs->t[elt/NBit] & BIT(elt%NBit)) != 0;
 455 }
 456
 457 /* parse.c */
 458 extern Op optab[NOp];
 459 void parse(FILE *, char *, void (Dat *), void (Fn *));
 460 void printfn(Fn *, FILE *);
 461 void printref(Ref, Fn *, FILE *);
 462 void err(char *, ...) __attribute__((noreturn));
 463
 464 /* cfg.c */
 465 Blk *blknew(void);
 466 void edgedel(Blk *, Blk **);
 467 void fillpreds(Fn *);
 468 void fillrpo(Fn *);
 469 void filldom(Fn *);
 470 int sdom(Blk *, Blk *);
 471 int dom(Blk *, Blk *);
 472 void fillfron(Fn *);
 473 void loopiter(Fn *, void (*)(Blk *, Blk *));
 474 void fillloop(Fn *);
 475 void simpljmp(Fn *);
 476
 477 /* mem.c */
 478 void memopt(Fn *);
 479
 480 /* alias.c */
 481 void fillalias(Fn *);
 482 int alias(Ref, int, Ref, int, int *, Fn *);
 483 int escapes(Ref, Fn *);
 484
 485 /* load.c */
 486 int loadsz(Ins *);
 487 int storesz(Ins *);
 488 void loadopt(Fn *);
 489
 490 /* ssa.c */
 491 void filluse(Fn *);
 492 void fillpreds(Fn *);
 493 void fillrpo(Fn *);
 494 void ssa(Fn *);
 495 void ssacheck(Fn *);
 496
 497 /* simpl.c */
 498 void simpl(Fn *);
 499
 500 /* copy.c */
 501 void copy(Fn *);
 502
 503 /* fold.c */
 504 void fold(Fn *);
 505
 506 /* live.c */
 507 void liveon(BSet *, Blk *, Blk *);
 508 void filllive(Fn *);
 509
 510 /* spill.c */
 511 void fillcost(Fn *);
 512 void spill(Fn *);
 513
 514 /* rega.c */
 515 void rega(Fn *);
 516
 517 /* gas.c */
 518 extern char *gasloc;
 519 extern char *gassym;
 520 void gasemitdat(Dat *, FILE *);
 521 int gasstash(void *, int);
 522 void gasemitfin(FILE *);