1 /* Id: pass2.h,v 1.142 2015/08/13 11:56:03 ragge Exp */
2 /* $NetBSD: pass2.h,v 1.1.1.7 2016/02/09 20:29:17 plunky Exp $ */
3 /*
4 * Copyright(C) Caldera International Inc. 2001-2002. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * Redistributions of source code and documentation must retain the above
11 * copyright notice, this list of conditions and the following disclaimer.
12 * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditionsand the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * All advertising materials mentioning features or use of this software
16 * must display the following acknowledgement:
17 * This product includes software developed or owned by Caldera
18 * International, Inc.
19 * Neither the name of Caldera International, Inc. nor the names of other
20 * contributors may be used to endorse or promote products derived from
21 * this software without specific prior written permission.
22 *
23 * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
24 * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
25 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
26 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
27 * DISCLAIMED. IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE
28 * FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OFLIABILITY, WHETHER IN CONTRACT,
32 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
33 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34 * POSSIBILITY OF SUCH DAMAGE.
35 */
36 #include <sys/types.h>
37
38 #ifndef MKEXT
39 #include "external.h"
40 #else
41 typedef unsigned int bittype; /* XXX - for basicblock */
42 #define BIT2BYTE(a) (((a) + 31) / 32)
43 #endif
44 #include "manifest.h"
45
46 /* cookies, used as arguments to codgen */
47 #define FOREFF 01 /* compute for effects only */
48 #define INAREG 02 /* compute into a register */
49 #define INBREG 04 /* compute into a register */
50 #define INCREG 010 /* compute into a register */
51 #define INDREG 020 /* compute into a register */
52 #define INREGS (INAREG|INBREG|INCREG|INDREG)
53 #define FORCC 040 /* compute for condition codes only */
54 #define QUIET 0100 /* tell geninsn() to not complain if fail */
55 #define INTEMP 010000 /* compute into a temporary location */
56 #define FORREW 040000 /* search the table for a rewrite rule */
57 #define INEREG 0x10000 /* compute into a register, > 16 bits */
58 #define INFREG 0x20000 /* compute into a register, > 16 bits */
59 #define INGREG 0x40000 /* compute into a register, > 16 bits */
60
61 /*
62 * OP descriptors,
63 * the ASG operator may be used on some of these
64 */
65 #define OPSIMP 010000 /* +, -, &, |, ^ */
66 #define OPCOMM 010002 /* +, &, |, ^ */
67 #define OPMUL 010004 /* *, / */
68 #define OPDIV 010006 /* /, % */
69 #define OPUNARY 010010 /* unary ops */
70 #define OPLEAF 010012 /* leaves */
71 #define OPANY 010014 /* any op... */
72 #define OPLOG 010016 /* logical ops */
73 #define OPFLOAT 010020 /* +, -, *, or / (for floats) */
74 #define OPSHFT 010022 /* <<, >> */
75 #define OPLTYPE 010024 /* leaf type nodes (e.g, NAME, ICON, etc.) */
76
77 /* shapes */
78 #define SANY 01 /* same as FOREFF */
79 #define SAREG 02 /* same as INAREG */
80 #define SBREG 04 /* same as INBREG */
81 #define SCREG 010 /* same as INCREG */
82 #define SDREG 020 /* same as INDREG */
83 #define SCC 040 /* same as FORCC */
84 #define SNAME 0100
85 #define SCON 0200
86 #define SFLD 0400
87 #define SOREG 01000
88 #define STARNM 02000
89 #define STARREG 04000
90 #define SWADD 040000
91 #define SPECIAL 0100000
92 #define SZERO SPECIAL
93 #define SONE (SPECIAL|1)
94 #define SMONE (SPECIAL|2)
95 #define SCCON (SPECIAL|3) /* -256 <= constant < 256 */
96 #define SSCON (SPECIAL|4) /* -32768 <= constant < 32768 */
97 #define SSOREG (SPECIAL|5) /* non-indexed OREG */
98 #define MAXSPECIAL (SPECIAL|5)
99 #define SEREG 0x10000 /* same as INEREG */
100 #define SFREG 0x20000 /* same as INFREG */
101 #define SGREG 0x40000 /* same as INGREG */
102
103 /* These are used in rstatus[] in conjunction with SxREG */
104 #define TEMPREG 01000
105 #define PERMREG 02000
106
107 /* tshape() return values */
108 #define SRNOPE 0 /* Cannot match any shape */
109 #define SRDIR 1 /* Direct match */
110 #define SROREG 2 /* Can convert into OREG */
111 #define SRREG 3 /* Must put into REG */
112
113 /* find*() return values */
114 #define FRETRY -2
115 #define FFAIL -1
116
117 /* INTEMP is carefully not conflicting with shapes */
118
119 /* types */
120 #define TCHAR 01 /* char */
121 #define TSHORT 02 /* short */
122 #define TINT 04 /* int */
123 #define TLONG 010 /* long */
124 #define TFLOAT 020 /* float */
125 #define TDOUBLE 040 /* double */
126 #define TPOINT 0100 /* pointer to something */
127 #define TUCHAR 0200 /* unsigned char */
128 #define TUSHORT 0400 /* unsigned short */
129 #define TUNSIGNED 01000 /* unsigned int */
130 #define TULONG 02000 /* unsigned long */
131 #define TPTRTO 04000 /* pointer to one of the above */
132 #define TANY 010000 /* matches anything within reason */
133 #define TSTRUCT 020000 /* structure or union */
134 #define TLONGLONG 040000 /* long long */
135 #define TULONGLONG 0100000 /* unsigned long long */
136 #define TLDOUBLE 0200000 /* long double; exceeds 16 bit */
137 #define TFTN 0400000 /* function pointer; exceeds 16 bit */
138
139 /* reclamation cookies */
140 #define RNULL 0 /* clobber result */
141 #define RLEFT 01
142 #define RRIGHT 02
143 #define RESC1 04
144 #define RESC2 010
145 #define RESC3 020
146 #define RDEST 040
147 #define RESCC 04000
148 #define RNOP 010000 /* DANGER: can cause loops.. */
149
150 /* needs */
151 #define NASL 0x0001 /* may share left register */
152 #define NASR 0x0002 /* may share right register */
153 #define NAREG 0x0004
154 #define NACOUNT 0x000c
155 #define NBSL 0x0010
156 #define NBSR 0x0020
157 #define NBREG 0x0040
158 #define NBCOUNT 0x00c0
159 #define NCSL 0x0100
160 #define NCSR 0x0200
161 #define NCREG 0x0400
162 #define NCCOUNT 0x0c00
163 #define NTEMP 0x1000
164 #define NTMASK 0x3000
165 #define NSPECIAL 0x4000 /* need special register treatment */
166 #define REWRITE 0x8000
167 #define NDSL 0x00010000 /* Above 16 bit */
168 #define NDSR 0x00020000 /* Above 16 bit */
169 #define NDREG 0x00040000 /* Above 16 bit */
170 #define NDCOUNT 0x000c0000
171 #define NESL 0x00100000 /* Above 16 bit */
172 #define NESR 0x00200000 /* Above 16 bit */
173 #define NEREG 0x00400000 /* Above 16 bit */
174 #define NECOUNT 0x00c00000
175 #define NFSL 0x01000000 /* Above 16 bit */
176 #define NFSR 0x02000000 /* Above 16 bit */
177 #define NFREG 0x04000000 /* Above 16 bit */
178 #define NFCOUNT 0x0c000000
179 #define NGSL 0x10000000 /* Above 16 bit */
180 #define NGSR 0x20000000 /* Above 16 bit */
181 #undef NGREG /* XXX - linux exposes NGREG to public */
182 #define NGREG 0x40000000 /* Above 16 bit */
183 #define NGCOUNT 0xc0000000
184
185 /* special treatment */
186 #define NLEFT (0001) /* left leg register (moveadd) */
187 #define NOLEFT (0002) /* avoid regs for left (addedge) */
188 #define NRIGHT (0004) /* right leg register */
189 #define NORIGHT (0010) /* avoid reg for right */
190 #define NEVER (0020) /* registers trashed (addalledges) */
191 #define NRES (0040) /* result register (moveadd) */
192 #define NMOVTO (0100) /* move between classes */
193
194
195 #define MUSTDO 010000 /* force register requirements */
196 #define NOPREF 020000 /* no preference for register assignment */
197
198 #define isreg(p) (p->n_op == REG || p->n_op == TEMP)
199
200 extern int fregs;
201
202 /* code tables */
203 extern struct optab {
204 int op;
205 int visit;
206 int lshape;
207 int ltype;
208 int rshape;
209 int rtype;
210 int needs;
211 int rewrite;
212 char *cstring;
213 } table[];
214
215 /* Special needs for register allocations */
216 struct rspecial {
217 int op, num;
218 #if 0
219 int left; /* left leg register */
220 int noleft; /* avoid regs for left */
221 int right; /* right leg register */
222 int noright; /* avoid right leg register */
223 int *rmask; /* array of destroyed registers */
224 int res; /* Result ends up here */
225 // void (*rew)(struct optab *, NODE *); /* special rewrite */
226 #endif
227 };
228
229 struct p2env;
230 #define NRESC 4
231 extern NODE resc[];
232 extern int p2autooff, p2maxautooff;
233
234 extern NODE
235 *talloc(void),
236 *eread(void),
237 *mklnode(int, CONSZ, int, TWORD),
238 *mkbinode(int, NODE *, NODE *, TWORD),
239 *mkunode(int, NODE *, int, TWORD),
240 *getlr(NODE *p, int);
241
242 void eoftn(struct interpass_prolog *);
243 void prologue(struct interpass_prolog *);
244 void e2print(NODE *p, int down, int *a, int *b);
245 void myoptim(struct interpass *);
246 void cbgen(int op, int label);
247 int match(NODE *p, int cookie);
248 int acceptable(struct optab *);
249 int special(NODE *, int);
250 int setasg(NODE *, int);
251 int setuni(NODE *, int);
252 int sucomp(NODE *);
253 int nsucomp(NODE *);
254 int setorder(NODE *);
255 int geninsn(NODE *, int cookie);
256 void adrput(FILE *, NODE *);
257 void comperr(char *str, ...);
258 void genregs(NODE *p);
259 void ngenregs(struct p2env *);
260 NODE *store(NODE *);
261 struct interpass *ipnode(NODE *);
262 void deflab(int);
263 void rmove(int, int, TWORD);
264 int rspecial(struct optab *, int);
265 struct rspecial *nspecial(struct optab *q);
266 void printip(struct interpass *pole);
267 int findops(NODE *p, int);
268 int findasg(NODE *p, int);
269 int finduni(NODE *p, int);
270 int findumul(NODE *p, int);
271 int findleaf(NODE *p, int);
272 int relops(NODE *p);
273 #ifdef FINDMOPS
274 int findmops(NODE *p, int);
275 int treecmp(NODE *p1, NODE *p2);
276 #endif
277 void offstar(NODE *p, int shape);
278 int gclass(TWORD);
279 void lastcall(NODE *);
280 void myreader(struct interpass *pole);
281 int oregok(NODE *p, int sharp);
282 void myormake(NODE *);
283 int *livecall(NODE *);
284 void prtreg(NODE *);
285 char *prcook(int);
286 int myxasm(struct interpass *ip, NODE *p);
287 int xasmcode(char *s);
288 int freetemp(int k);
289 NODE *storenode(TWORD t, int k);
290 void storemod(NODE *, int k, int reg);
291 int rewfld(NODE *p);
292 void canon(NODE *);
293 void mycanon(NODE *);
294 void oreg2(NODE *p, void *);
295 int shumul(NODE *p, int);
296 NODE *deluseless(NODE *p);
297 int getlab2(void);
298 int tshape(NODE *, int);
299 void conput(FILE *, NODE *);
300 int shtemp(NODE *p);
301 int ttype(TWORD t, int tword);
302 void expand(NODE *, int, char *);
303 void hopcode(int, int);
304 void adrcon(CONSZ);
305 void zzzcode(NODE *, int);
306 void insput(NODE *);
307 void upput(NODE *, int);
308 int tlen(NODE *p);
309 int setbin(NODE *);
310 int notoff(TWORD, int, CONSZ, char *);
311 int fldexpand(NODE *, int, char **);
312 int flshape(NODE *p);
313 int ncnt(int needs);
314 void mainp2(void);
315
316 extern char *rnames[];
317
318 extern int classmask(int), tclassmask(int);
319 extern void cmapinit(void);
320 extern int aliasmap(int adjclass, int regnum);
321 extern int regK[];
322 #define CLASSA 1
323 #define CLASSB 2
324 #define CLASSC 3
325 #define CLASSD 4
326 #define CLASSE 5
327 #define CLASSF 6
328 #define CLASSG 7
329
330 /* used when parsing xasm codes */
331 #define XASMVAL(x) ((x) & 0377) /* get val from codeword */
332 #define XASMVAL1(x) (((x) >> 16) & 0377) /* get val from codeword */
333 #define XASMVAL2(x) (((x) >> 24) & 0377) /* get val from codeword */
334 #define XASMASG 0x100 /* = */
335 #define XASMCONSTR 0x200 /* & */
336 #define XASMINOUT 0x400 /* + */
337 #define XASMALL (XASMASG|XASMCONSTR|XASMINOUT)
338 #define XASMISINP(cw) (((cw) & XASMASG) == 0) /* input operand */
339 #define XASMISOUT(cw) ((cw) & (XASMASG|XASMINOUT)) /* output operand */
340
341 /* routines to handle double indirection */
342 #ifdef R2REGS
343 void makeor2(NODE *p, NODE *q, int, int);
344 int base(NODE *);
345 int offset(NODE *p, int);
346 #endif
347
348 extern int lineno;
349 extern int ndebug;
350 extern int b2debug, c2debug, e2debug, f2debug, g2debug, o2debug;
351 extern int r2debug, s2debug, t2debug, u2debug, x2debug;
352
353 extern int dope[]; /* a vector containing operator information */
354 extern char *opst[]; /* a vector containing names for ops */
355
356 #ifdef PCC_DEBUG
357
358 static inline int
optype(int o)359 optype(int o)
360 {
361 if (o >= MAXOP+1)
362 cerror("optype");
363 return (dope[o]&TYFLG);
364 }
365
366 static inline int
asgop(int o)367 asgop(int o)
368 {
369 if (o >= MAXOP+1)
370 cerror("asgop");
371 return (dope[o]&ASGFLG);
372 }
373
374 static inline int
logop(int o)375 logop(int o)
376 {
377 if (o >= MAXOP+1)
378 cerror("logop");
379 return (dope[o]&LOGFLG);
380 }
381
382 static inline int
callop(int o)383 callop(int o)
384 {
385 if (o >= MAXOP+1)
386 cerror("callop");
387 return (dope[o]&CALLFLG);
388 }
389
390 #else
391
392 #define optype(o) (dope[o]&TYFLG)
393 #define asgop(o) (dope[o]&ASGFLG)
394 #define logop(o) (dope[o]&LOGFLG)
395 #define callop(o) (dope[o]&CALLFLG)
396
397 #endif
398
399 /* macros for doing double indexing */
400 #define R2PACK(x,y,z) (0200*((x)+1)+y+040000*z)
401 #define R2UPK1(x) ((((x)>>7)-1)&0177)
402 #define R2UPK2(x) ((x)&0177)
403 #define R2UPK3(x) (x>>14)
404 #define R2TEST(x) ((x)>=0200)
405
406 /*
407 * Layout of findops() return value:
408 * bit 0 whether left shall go into a register.
409 * bit 1 whether right shall go into a register.
410 * bit 2 entry is only used for side effects.
411 * bit 3 if condition codes are used.
412 *
413 * These values should be synced with FOREFF/FORCC.
414 */
415 #define ISMOPS 001
416 #define RREG 002
417 #define RVEFF 004
418 #define RVCC 010
419 #define DORIGHT 020
420 #define SCLASS(v,x) ((v) |= ((x) << 5))
421 #define TCLASS(x) (((x) >> 5) & 7)
422 #define TBSH 8
423 #define TBLIDX(idx) ((idx) >> TBSH)
424 #define MKIDX(tbl,mod) (((tbl) << TBSH) | (mod))
425
426 #ifndef BREGS
427 #define BREGS 0
428 #define TBREGS 0
429 #endif
430 #define REGBIT(x) (1 << (x))
431 #ifndef PERMTYPE
432 #define PERMTYPE(a) (INT)
433 #endif
434
435 /* Flags for the dataflow code */
436 /* do the live/dead analysis */
437 #define DO_LIVEDEAD 0x01
438 /* compute avail expressions */
439 #define DO_AVAILEXPR 0x02
440 /* Do an update on the live/dead. One variable only */
441 #define DO_UPDATELD 0x04
442 /* Do an update on available expressions, one variable has changed */
443 #define DO_UPDATEEX 0x08
444
445 void emit(struct interpass *);
446 void optimize(struct p2env *);
447
448 struct basicblock {
449 DLIST_ENTRY(basicblock) bbelem;
450 SLIST_HEAD(, cfgnode) parents; /* CFG - parents to this node */
451 SLIST_HEAD(, cfgnode) child; /* Children, usually max 2 of them */
452 int bbnum; /* this basic block number */
453 unsigned int dfnum; /* DFS-number */
454 unsigned int dfparent; /* Parent in DFS */
455 unsigned int semi;
456 unsigned int ancestor;
457 unsigned int idom;
458 unsigned int samedom;
459 bittype *bucket;
460 bittype *df;
461 bittype *dfchildren;
462 bittype *Aorig;
463 bittype *Aphi;
464 SLIST_HEAD(, phiinfo) phi;
465
466 bittype *gen, *killed, *in, *out; /* Liveness analysis */
467
468 struct interpass *first; /* first element of basic block */
469 struct interpass *last; /* last element of basic block */
470 };
471
472 struct labelinfo {
473 struct basicblock **arr;
474 int size;
475 unsigned int low;
476 };
477
478 struct bblockinfo {
479 int size;
480 struct basicblock **arr;
481 };
482
483 struct varinfo {
484 struct pvarinfo **arr;
485 SLIST_HEAD(, varstack) *stack;
486 int size;
487 int low;
488 };
489
490 struct pvarinfo {
491 struct pvarinfo *next;
492 struct basicblock *bb;
493 TWORD n_type;
494 };
495
496 struct varstack {
497 SLIST_ENTRY(varstack) varstackelem;
498 int tmpregno;
499 };
500
501
502 struct cfgnode {
503 SLIST_ENTRY(cfgnode) cfgelem;
504 SLIST_ENTRY(cfgnode) chld;
505 struct basicblock *bblock;
506 };
507
508 struct phiinfo {
509 SLIST_ENTRY(phiinfo) phielem;
510 int tmpregno;
511 int newtmpregno;
512 TWORD n_type;
513 int size;
514 int *intmpregno;
515 };
516
517 /*
518 * Description of the pass2 environment.
519 * There will be only one of these structs. It is used to keep
520 * all state descriptions during the compilation of a function
521 * in one place.
522 */
523 struct p2env {
524 struct interpass ipole; /* all statements */
525 struct interpass_prolog *ipp, *epp; /* quick references */
526 struct bblockinfo bbinfo;
527 struct labelinfo labinfo;
528 struct basicblock bblocks;
529 int nbblocks;
530 };
531
532 extern struct p2env p2env;
533
534 /*
535 * C compiler second pass extra defines.
536 */
537 #define PHI (MAXOP + 1) /* Used in SSA trees */
538
539 enum {
540 ATTR_P2_FIRST = ATTR_MI_MAX + 1,
541 ATTR_P2STRUCT,
542 #ifdef ATTR_P2_TARGET
543 ATTR_P2_TARGET,
544 #endif
545 ATTR_P2_MAX
546 };
547