qbe

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

all.h (8366B)


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