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
11typedef unsigned char uchar;
12typedef unsigned int uint;
13typedef unsigned long ulong;
14typedef unsigned long long bits;
15
16typedef struct BSet BSet;
17typedef struct Ref Ref;
18typedef struct Op Op;
19typedef struct Ins Ins;
20typedef struct Phi Phi;
21typedef struct Blk Blk;
22typedef struct Use Use;
23typedef struct Alias Alias;
24typedef struct Tmp Tmp;
25typedef struct Con Con;
26typedef struct Addr Mem;
27typedef struct Fn Fn;
28typedef struct Typ Typ;
29typedef struct Field Field;
30typedef struct Dat Dat;
31typedef struct Lnk Lnk;
32typedef struct Target Target;
33
34enum {
35 NString = 72,
36 NIns = 1 << 20,
37 NAlign = 3,
38 NField = 32,
39 NBit = CHAR_BIT * sizeof(bits),
40};
41
42struct 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
62enum {
63 RXX = 0,
64 Tmp0 = NBit, /* first non-reg temporary */
65};
66
67struct BSet {
68 uint nt;
69 bits *t;
70};
71
72struct Ref {
73 uint type:3;
74 uint val:29;
75};
76
77enum {
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
95static inline int req(Ref a, Ref b)
96{
97 return a.type == b.type && a.val == b.val;
98}
99
100static inline int rtype(Ref r)
101{
102 if (req(r, R))
103 return -1;
104 return r.type;
105}
106
107enum 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
121enum 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
134enum O {
135 Oxxx,
136#define O(op, x, y) O##op,
137 #include "ops.h"
138 NOp,
139};
140
141enum 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
157enum {
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
183enum {
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
194struct Op {
195 char *name;
196 short argcls[2][4];
197 int canfold;
198};
199
200struct Ins {
201 uint op:30;
202 uint cls:2;
203 Ref to;
204 Ref arg[2];
205};
206
207struct Phi {
208 Ref to;
209 Ref *arg;
210 Blk **blk;
211 uint narg;
212 int cls;
213 Phi *link;
214};
215
216struct 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
244struct 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
258enum {
259 NoAlias,
260 MayAlias,
261 MustAlias
262};
263
264struct 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
280struct 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
307struct 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
323typedef struct Addr Addr;
324
325struct Addr { /* amd64 addressing */
326 Con offset;
327 Ref base;
328 Ref index;
329 int scale;
330};
331
332struct Lnk {
333 char export;
334 char align;
335 char *sec;
336 char *secf;
337};
338
339struct 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
359struct 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
382struct 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 */
409extern Target T;
410extern char debug['Z'+1];
411
412/* util.c */
413typedef enum {
414 Pheap, /* free() necessary */
415 Pfn, /* discarded after processing the function */
416} Pool;
417
418extern Typ *typ;
419extern Ins insb[NIns], *curi;
420uint32_t hash(char *);
421void die_(char *, char *, ...) __attribute__((noreturn));
422void *emalloc(size_t);
423void *alloc(size_t);
424void freeall(void);
425void *vnew(ulong, size_t, Pool);
426void vfree(void *);
427void vgrow(void *, ulong);
428uint32_t intern(char *);
429char *str(uint32_t);
430int argcls(Ins *, int);
431int isreg(Ref);
432int iscmp(int, int *, int *);
433void emit(int, int, Ref, Ref, Ref);
434void emiti(Ins);
435void idup(Ins **, Ins *, ulong);
436Ins *icpy(Ins *, Ins *, ulong);
437int cmpop(int);
438int cmpneg(int);
439int clsmerge(short *, short);
440int phicls(int, Tmp *);
441Ref newtmp(char *, int, Fn *);
442void chuse(Ref, int, Fn *);
443Ref newcon(Con *, Fn *);
444Ref getcon(int64_t, Fn *);
445int addcon(Con *, Con *);
446void blit(Ref, uint, Ref, uint, uint, Fn *);
447void blit0(Ref, Ref, uint, Fn *);
448void salloc(Ref, Ref, Fn *);
449void dumpts(BSet *, Tmp *, FILE *);
450
451void bsinit(BSet *, uint);
452void bszero(BSet *);
453uint bscount(BSet *);
454void bsset(BSet *, uint);
455void bsclr(BSet *, uint);
456void bscopy(BSet *, BSet *);
457void bsunion(BSet *, BSet *);
458void bsinter(BSet *, BSet *);
459void bsdiff(BSet *, BSet *);
460int bsequal(BSet *, BSet *);
461int bsiter(BSet *, int *);
462
463static inline int
464bshas(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 */
471extern Op optab[NOp];
472void parse(FILE *, char *, void (Dat *), void (Fn *));
473void printfn(Fn *, FILE *);
474void printref(Ref, Fn *, FILE *);
475void err(char *, ...) __attribute__((noreturn));
476
477/* cfg.c */
478Blk *blknew(void);
479void edgedel(Blk *, Blk **);
480void fillpreds(Fn *);
481void fillrpo(Fn *);
482void filldom(Fn *);
483int sdom(Blk *, Blk *);
484int dom(Blk *, Blk *);
485void fillfron(Fn *);
486void loopiter(Fn *, void (*)(Blk *, Blk *));
487void fillloop(Fn *);
488void simpljmp(Fn *);
489
490/* mem.c */
491void memopt(Fn *);
492
493/* alias.c */
494void fillalias(Fn *);
495int alias(Ref, int, Ref, int, int *, Fn *);
496int escapes(Ref, Fn *);
497
498/* load.c */
499int loadsz(Ins *);
500int storesz(Ins *);
501void loadopt(Fn *);
502
503/* ssa.c */
504void filluse(Fn *);
505void fillpreds(Fn *);
506void fillrpo(Fn *);
507void ssa(Fn *);
508void ssacheck(Fn *);
509
510/* copy.c */
511void copy(Fn *);
512
513/* fold.c */
514void fold(Fn *);
515
516/* live.c */
517void liveon(BSet *, Blk *, Blk *);
518void filllive(Fn *);
519
520/* spill.c */
521void fillcost(Fn *);
522void spill(Fn *);
523
524/* rega.c */
525void rega(Fn *);
526
527/* gas.c */
528enum Asm {
529 Gasmacho,
530 Gaself,
531};
532extern char *gasloc;
533extern char *gassym;
534void gasinit(enum Asm);
535void gasemitlnk(char *, Lnk *, char *, FILE *);
536void gasemitfntail(char *, FILE *);
537void gasemitdat(Dat *, FILE *);
538int gasstash(void *, int);
539void gasemitfin(FILE *);
540