qbe

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

all.h (8711B)


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