qbe

Internal scc patchset buffer for QBE
Log | Files | Refs | README | LICENSE

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 *);