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