1 #include "limbo.h"
2
3 #define bzero bbzero /* bsd name space pollution */
4 /*
5 (r, s) := f(); => r, s have def on same pc
6 s = g(); => this def kills previous r def (and s def)
7 solution: r has def pc, s has def pc+1 and next instruction has pc pc+2
8 */
9
10 #define BLEN (8*sizeof(ulong))
11 #define BSHIFT 5 /* assumes ulong 4 */
12 #define BMASK (BLEN-1)
13
14 #define SIGN(n) (1<<(n-1))
15 #define MSK(n) (SIGN(n)|(SIGN(n)-1))
16 #define MASK(a, b) (MSK((b)-(a)+1)<<(a))
17
18 #define isnilsrc(s) ((s)->start.line == 0 && (s)->stop.line == 0 && (s)->start.pos == 0 && (s)->stop.pos == 0)
19
20 #define limbovar(d) ((d)->sym->name[0] != '.')
21 #define structure(t) ((t)->kind == Tadt || (t)->kind == Ttuple)
22
23 enum
24 {
25 Bclr,
26 Band,
27 Bandinv,
28 Bstore,
29 Bandrev,
30 Bnoop,
31 Bxor,
32 Bor,
33 Bnor,
34 Bequiv,
35 Binv,
36 Bimpby,
37 Brev,
38 Bimp,
39 Bnand,
40 Bset,
41 };
42
43 enum
44 {
45 Suse = 1,
46 Muse = 2,
47 Duse = 4,
48 Sdef = 8,
49 Mdef = 16,
50 Ddef = 32,
51 Tuse1 = 64, /* fixed point temporary */
52 Tuse2 = 128, /* fixed point temporary */
53 Mduse = 256, /* D used if M nil */
54
55 None = 0,
56 Unop = Suse|Ddef,
57 Cunop = Muse|Ddef,
58 Threop = Suse|Muse|Ddef,
59 Binop = Suse|Muse|Ddef|Mduse,
60 Mbinop = Suse|Mdef|Duse, /* strange */
61 Abinop=Suse|Duse|Ddef,
62 Mabinop = Suse|Muse|Duse|Ddef,
63 Use1 = Suse,
64 Use2 = Suse|Duse,
65 Use3 = Suse|Muse|Duse,
66 };
67
68 enum
69 {
70 Sshift = 10,
71 Mshift = 5,
72 Dshift = 0,
73 };
74
75 #define S(x) ((x)<<Sshift)
76 #define M(x) ((x)<<Mshift)
77 #define D(x) ((x)<<Dshift)
78
79 #define SS(x) (((x)>>Sshift)&0x1f)
80 #define SM(x) (((x)>>Mshift)&0x1f)
81 #define SD(x) (((x)>>Dshift)&0x1f)
82
83 enum
84 {
85 I = 0, /* ignore */
86 B = 1, /* byte */
87 W = 4, /* int */
88 P = 4, /* pointer */
89 A = 4, /* array */
90 C = 4, /* string */
91 X = 4, /* fixed */
92 R = 4, /* float */
93 L = 8, /* big */
94 F = 8, /* real */
95 Sh = 2, /* short */
96 Pc = 4, /* pc */
97 Mp = 16, /* memory */
98
99 Bop2 = S(B)|D(B),
100 Bop = S(B)|M(B)|D(B),
101 Bopb = S(B)|M(B)|D(Pc),
102 Wop2 = S(W)|D(W),
103 Wop = S(W)|M(W)|D(W),
104 Wopb = S(W)|M(W)|D(Pc),
105 Lop2 = S(L)|D(L),
106 Lop = S(L)|M(L)|D(L),
107 Lopb = S(L)|M(L)|D(Pc),
108 Cop2 = Wop2,
109 Cop = Wop,
110 Copb = Wopb,
111 Fop2 = Lop2,
112 Fop = Lop,
113 Fopb = Lopb,
114 Xop = Wop,
115 };
116
117 typedef struct Array Array;
118 typedef struct Bits Bits;
119 typedef struct Blist Blist;
120 typedef struct Block Block;
121 typedef struct Idlist Idlist;
122 typedef struct Optab Optab;
123
124 struct Array
125 {
126 int n;
127 int m;
128 Block **a;
129 };
130
131 struct Bits
132 {
133 int n;
134 ulong *b;
135 };
136
137 struct Blist
138 {
139 Block *block;
140 Blist *next;
141 };
142
143 struct Block
144 {
145 int dfn;
146 int flags;
147 Inst *first;
148 Inst *last;
149 Block *prev;
150 Block *next;
151 Blist *pred;
152 Blist *succ;
153 Bits kill;
154 Bits gen;
155 Bits in;
156 Bits out;
157 };
158
159 struct Idlist
160 {
161 int id;
162 Idlist *next;
163 };
164
165 struct Optab
166 {
167 short flags;
168 short size;
169 };
170
171 Block zblock;
172 Decl *regdecls;
173 Idlist *frelist;
174 Idlist *deflist;
175 Idlist *uselist;
176
177 static void
addlist(Idlist ** hd,int id)178 addlist(Idlist **hd, int id)
179 {
180 Idlist *il;
181
182 if(frelist == nil)
183 il = (Idlist*)malloc(sizeof(Idlist));
184 else{
185 il = frelist;
186 frelist = frelist->next;
187 }
188 il->id = id;
189 il->next = *hd;
190 *hd = il;
191 }
192
193 static void
freelist(Idlist ** hd)194 freelist(Idlist **hd)
195 {
196 Idlist *il;
197
198 for(il = *hd; il != nil && il->next != nil; il = il->next)
199 ;
200 if(il != nil){
201 il->next = frelist;
202 frelist = *hd;
203 *hd = nil;
204 }
205 }
206
207 Optab opflags[] = {
208 /* INOP */ None, 0,
209 /* IALT */ Unop, S(Mp)|D(W),
210 /* INBALT */ Unop, S(Mp)|D(W),
211 /* IGOTO */ Use2, S(W)|D(I),
212 /* ICALL */ Use2, S(P)|D(Pc),
213 /* IFRAME */ Unop, S(W)|D(P),
214 /* ISPAWN */ Use2, S(P)|D(Pc),
215 /* IRUNT */ None, 0,
216 /* ILOAD */ Threop, S(C)|M(P)|D(P),
217 /* IMCALL */ Use3, S(P)|M(W)|D(P),
218 /* IMSPAWN */ Use3, S(P)|M(W)|D(P),
219 /* IMFRAME */ Threop, S(P)|M(W)|D(P),
220 /* IRET */ None, 0,
221 /* IJMP */ Duse, D(Pc),
222 /* ICASE */ Use2, S(W)|D(I),
223 /* IEXIT */ None, 0,
224 /* INEW */ Unop, S(W)|D(P),
225 /* INEWA */ Threop, S(W)|M(W)|D(P),
226 /* INEWCB */ Cunop, M(W)|D(P),
227 /* INEWCW */ Cunop, M(W)|D(P),
228 /* INEWCF */ Cunop, M(W)|D(P),
229 /* INEWCP */ Cunop, M(W)|D(P),
230 /* INEWCM */ Threop, S(W)|M(W)|D(P),
231 /* INEWCMP */ Threop, S(W)|M(W)|D(P),
232 /* ISEND */ Use2, S(Mp)|D(P),
233 /* IRECV */ Unop, S(P)|D(Mp),
234 /* ICONSB */ Abinop, S(B)|D(P),
235 /* ICONSW */ Abinop, S(W)|D(P),
236 /* ICONSP */ Abinop, S(P)|D(P),
237 /* ICONSF */ Abinop, S(F)|D(P),
238 /* ICONSM */ Mabinop, S(Mp)|M(W)|D(P),
239 /* ICONSMP */ Mabinop, S(Mp)|M(W)|D(P),
240 /* IHEADB */ Unop, S(P)|D(B),
241 /* IHEADW */ Unop, S(P)|D(W),
242 /* IHEADP */ Unop, S(P)|D(P),
243 /* IHEADF */ Unop, S(P)|D(F),
244 /* IHEADM */ Threop, S(P)|M(W)|D(Mp),
245 /* IHEADMP */ Threop, S(P)|M(W)|D(Mp),
246 /* ITAIL */ Unop, S(P)|D(P),
247 /* ILEA */ Ddef, S(Mp)|D(P), /* S done specially cos of ALT */
248 /* IINDX */ Mbinop, S(P)|M(P)|D(W),
249 /* IMOVP */ Unop, S(P)|D(P),
250 /* IMOVM */ Threop, S(Mp)|M(W)|D(Mp),
251 /* IMOVMP */ Threop, S(Mp)|M(W)|D(Mp),
252 /* IMOVB */ Unop, Bop2,
253 /* IMOVW */ Unop, Wop2,
254 /* IMOVF */ Unop, Fop2,
255 /* ICVTBW */ Unop, S(B)|D(W),
256 /* ICVTWB */ Unop, S(W)|D(B),
257 /* ICVTFW */ Unop, S(F)|D(W),
258 /* ICVTWF */ Unop, S(W)|D(F),
259 /* ICVTCA */ Unop, S(C)|D(A),
260 /* ICVTAC */ Unop, S(A)|D(C),
261 /* ICVTWC */ Unop, S(W)|D(C),
262 /* ICVTCW */ Unop, S(C)|D(W),
263 /* ICVTFC */ Unop, S(F)|D(C),
264 /* ICVTCF */ Unop, S(C)|D(F),
265 /* IADDB */ Binop, Bop,
266 /* IADDW */ Binop, Wop,
267 /* IADDF */ Binop, Fop,
268 /* ISUBB */ Binop, Bop,
269 /* ISUBW */ Binop, Wop,
270 /* ISUBF */ Binop, Fop,
271 /* IMULB */ Binop, Bop,
272 /* IMULW */ Binop, Wop,
273 /* IMULF */ Binop, Fop,
274 /* IDIVB */ Binop, Bop,
275 /* IDIVW */ Binop, Wop,
276 /* IDIVF */ Binop, Fop,
277 /* IMODW */ Binop, Wop,
278 /* IMODB */ Binop, Bop,
279 /* IANDB */ Binop, Bop,
280 /* IANDW */ Binop, Wop,
281 /* IORB */ Binop, Bop,
282 /* IORW */ Binop, Wop,
283 /* IXORB */ Binop, Bop,
284 /* IXORW */ Binop, Wop,
285 /* ISHLB */ Binop, S(W)|M(B)|D(B),
286 /* ISHLW */ Binop, Wop,
287 /* ISHRB */ Binop, S(W)|M(B)|D(B),
288 /* ISHRW */ Binop, Wop,
289 /* IINSC */ Mabinop, S(W)|M(W)|D(C),
290 /* IINDC */ Threop, S(C)|M(W)|D(W),
291 /* IADDC */ Binop, Cop,
292 /* ILENC */ Unop, S(C)|D(W),
293 /* ILENA */ Unop, S(A)|D(W),
294 /* ILENL */ Unop, S(P)|D(W),
295 /* IBEQB */ Use3, Bopb,
296 /* IBNEB */ Use3, Bopb,
297 /* IBLTB */ Use3, Bopb,
298 /* IBLEB */ Use3, Bopb,
299 /* IBGTB */ Use3, Bopb,
300 /* IBGEB */ Use3, Bopb,
301 /* IBEQW */ Use3, Wopb,
302 /* IBNEW */ Use3, Wopb,
303 /* IBLTW */ Use3, Wopb,
304 /* IBLEW */ Use3, Wopb,
305 /* IBGTW */ Use3, Wopb,
306 /* IBGEW */ Use3, Wopb,
307 /* IBEQF */ Use3, Fopb,
308 /* IBNEF */ Use3, Fopb,
309 /* IBLTF */ Use3, Fopb,
310 /* IBLEF */ Use3, Fopb,
311 /* IBGTF */ Use3, Fopb,
312 /* IBGEF */ Use3, Fopb,
313 /* IBEQC */ Use3, Copb,
314 /* IBNEC */ Use3, Copb,
315 /* IBLTC */ Use3, Copb,
316 /* IBLEC */ Use3, Copb,
317 /* IBGTC */ Use3, Copb,
318 /* IBGEC */ Use3, Copb,
319 /* ISLICEA */ Mabinop, S(W)|M(W)|D(P),
320 /* ISLICELA */ Use3, S(P)|M(W)|D(P),
321 /* ISLICEC */ Mabinop, S(W)|M(W)|D(C),
322 /* IINDW */ Mbinop, S(P)|M(P)|D(W),
323 /* IINDF */ Mbinop, S(P)|M(P)|D(W),
324 /* IINDB */ Mbinop, S(P)|M(P)|D(W),
325 /* INEGF */ Unop, Fop2,
326 /* IMOVL */ Unop, Lop2,
327 /* IADDL */ Binop, Lop,
328 /* ISUBL */ Binop, Lop,
329 /* IDIVL */ Binop, Lop,
330 /* IMODL */ Binop, Lop,
331 /* IMULL */ Binop, Lop,
332 /* IANDL */ Binop, Lop,
333 /* IORL */ Binop, Lop,
334 /* IXORL */ Binop, Lop,
335 /* ISHLL */ Binop, S(W)|M(L)|D(L),
336 /* ISHRL */ Binop, S(W)|M(L)|D(L),
337 /* IBNEL */ Use3, Lopb,
338 /* IBLTL */ Use3, Lopb,
339 /* IBLEL */ Use3, Lopb,
340 /* IBGTL */ Use3, Lopb,
341 /* IBGEL */ Use3, Lopb,
342 /* IBEQL */ Use3, Lopb,
343 /* ICVTLF */ Unop, S(L)|D(F),
344 /* ICVTFL */ Unop, S(F)|D(L),
345 /* ICVTLW */ Unop, S(L)|D(W),
346 /* ICVTWL */ Unop, S(W)|D(L),
347 /* ICVTLC */ Unop, S(L)|D(C),
348 /* ICVTCL */ Unop, S(C)|D(L),
349 /* IHEADL */ Unop, S(P)|D(L),
350 /* ICONSL */ Abinop, S(L)|D(P),
351 /* INEWCL */ Cunop, M(W)|D(P),
352 /* ICASEC */ Use2, S(C)|D(I),
353 /* IINDL */ Mbinop, S(P)|M(P)|D(W),
354 /* IMOVPC */ Unop, S(W)|D(P),
355 /* ITCMP */ Use2, S(P)|D(P),
356 /* IMNEWZ */ Threop, S(P)|M(W)|D(P),
357 /* ICVTRF */ Unop, S(R)|D(F),
358 /* ICVTFR */ Unop, S(F)|D(R),
359 /* ICVTWS */ Unop, S(W)|D(Sh),
360 /* ICVTSW */ Unop, S(Sh)|D(W),
361 /* ILSRW */ Binop, Wop,
362 /* ILSRL */ Binop, S(W)|M(L)|D(L),
363 /* IECLR */ None, 0,
364 /* INEWZ */ Unop, S(W)|D(P),
365 /* INEWAZ */ Threop, S(W)|M(W)|D(P),
366 /* IRAISE */ Use1, S(P),
367 /* ICASEL */ Use2, S(L)|D(I),
368 /* IMULX */ Binop|Tuse2, Xop,
369 /* IDIVX */ Binop|Tuse2, Xop,
370 /* ICVTXX */ Threop, Xop,
371 /* IMULX0 */ Binop|Tuse1|Tuse2, Xop,
372 /* IDIVX0 */ Binop|Tuse1|Tuse2, Xop,
373 /* ICVTXX0 */ Threop|Tuse1, Xop,
374 /* IMULX1 */ Binop|Tuse1|Tuse2, Xop,
375 /* IDIVX1 */ Binop|Tuse1|Tuse2, Xop,
376 /* ICVTXX1 */ Threop|Tuse1, Xop,
377 /* ICVTFX */ Threop, S(F)|M(F)|D(X),
378 /* ICVTXF */ Threop, S(X)|M(F)|D(F),
379 /* IEXPW */ Binop, S(W)|M(W)|D(W),
380 /* IEXPL */ Binop, S(W)|M(L)|D(L),
381 /* IEXPF */ Binop, S(W)|M(F)|D(F),
382 /* ISELF */ Ddef, D(P),
383 /* IEXC */ None, 0,
384 /* IEXC0 */ None, 0,
385 /* INOOP */ None, 0,
386 };
387
388 /*
389 static int
390 pop(int i)
391 {
392 i = (i & 0x55555555) + ((i>>1) & 0x55555555);
393 i = (i & 0x33333333) + ((i>>2) & 0x33333333);
394 i = (i & 0x0F0F0F0F) + ((i>>4) & 0x0F0F0F0F);
395 i = (i & 0x00FF00FF) + ((i>>8) & 0x00FF00FF);
396 i = (i & 0x0000FFFF) + ((i>>16) & 0x0000FFFF);
397 return i;
398 }
399 */
400
401 static int
bitc(uint x)402 bitc(uint x)
403 {
404 uint n;
405
406 n = (x>>1)&0x77777777;
407 x -= n;
408 n = (n>>1)&0x77777777;
409 x -= n;
410 n = (n>>1)&0x77777777;
411 x -= n;
412 x = (x+(x>>4))&0x0f0f0f0f;
413 x *= 0x01010101;
414 return x>>24;
415 }
416
417 /*
418 static int
419 top(uint x)
420 {
421 int i;
422
423 for(i = -1; x; i++)
424 x >>= 1;
425 return i;
426 }
427 */
428
429 static int
topb(uint x)430 topb(uint x)
431 {
432 int i;
433
434 if(x == 0)
435 return -1;
436 i = 0;
437 if(x&0xffff0000){
438 i |= 16;
439 x >>= 16;
440 }
441 if(x&0xff00){
442 i |= 8;
443 x >>= 8;
444 }
445 if(x&0xf0){
446 i |= 4;
447 x >>= 4;
448 }
449 if(x&0xc){
450 i |= 2;
451 x >>= 2;
452 }
453 if(x&0x2)
454 i |= 1;
455 return i;
456 }
457
458 /*
459 static int
460 lowb(uint x)
461 {
462 int i;
463
464 if(x == 0)
465 return -1;
466 for(i = BLEN; x; i--)
467 x <<= 1;
468 return i;
469 }
470 */
471
472 static int
lowb(uint x)473 lowb(uint x)
474 {
475 int i;
476
477 if(x == 0)
478 return -1;
479 i = 0;
480 if((x&0xffff) == 0){
481 i |= 16;
482 x >>= 16;
483 }
484 if((x&0xff) == 0){
485 i |= 8;
486 x >>= 8;
487 }
488 if((x&0xf) == 0){
489 i |= 4;
490 x >>= 4;
491 }
492 if((x&0x3) == 0){
493 i |= 2;
494 x >>= 2;
495 }
496 return i+1-(x&1);
497 }
498
499 static void
pbit(int x,int n)500 pbit(int x, int n)
501 {
502 int i, m;
503
504 m = 1;
505 for(i = 0; i < BLEN; i++){
506 if(x&m)
507 print("%d ", i+n);
508 m <<= 1;
509 }
510 }
511
512 static ulong
bop(int o,ulong s,ulong d)513 bop(int o, ulong s, ulong d)
514 {
515 switch(o){
516 case Bclr: return 0;
517 case Band: return s & d;
518 case Bandinv: return s & ~d;
519 case Bstore: return s;
520 case Bandrev: return ~s & d;
521 case Bnoop: return d;
522 case Bxor: return s ^ d;
523 case Bor: return s | d;
524 case Bnor: return ~(s | d);
525 case Bequiv: return ~(s ^ d);
526 case Binv: return ~d;
527 case Bimpby: return s | ~d;
528 case Brev: return ~s;
529 case Bimp: return ~s | d;
530 case Bnand: return ~(s & d);
531 case Bset: return 0xffffffff;
532 }
533 return 0;
534 }
535
536 static Bits
bnew(int n,int bits)537 bnew(int n, int bits)
538 {
539 Bits b;
540
541 if(bits)
542 b.n = (n+BLEN-1)>>BSHIFT;
543 else
544 b.n = n;
545 b.b = allocmem(b.n*sizeof(ulong));
546 memset(b.b, 0, b.n*sizeof(ulong));
547 return b;
548 }
549
550 static void
bfree(Bits b)551 bfree(Bits b)
552 {
553 free(b.b);
554 }
555
556 static void
bset(Bits b,int n)557 bset(Bits b, int n)
558 {
559 b.b[n>>BSHIFT] |= 1<<(n&BMASK);
560 }
561
562 static void
bclr(Bits b,int n)563 bclr(Bits b, int n)
564 {
565 b.b[n>>BSHIFT] &= ~(1<<(n&BMASK));
566 }
567
568 static int
bmem(Bits b,int n)569 bmem(Bits b, int n)
570 {
571 return b.b[n>>BSHIFT] & (1<<(n&BMASK));
572 }
573
574 static void
bsets(Bits b,int m,int n)575 bsets(Bits b, int m, int n)
576 {
577 int i, c1, c2;
578
579 c1 = m>>BSHIFT;
580 c2 = n>>BSHIFT;
581 m &= BMASK;
582 n &= BMASK;
583 if(c1 == c2){
584 b.b[c1] |= MASK(m, n);
585 return;
586 }
587 for(i = c1+1; i < c2; i++)
588 b.b[i] = 0xffffffff;
589 b.b[c1] |= MASK(m, BLEN-1);
590 b.b[c2] |= MASK(0, n);
591 }
592
593 static void
bclrs(Bits b,int m,int n)594 bclrs(Bits b, int m, int n)
595 {
596 int i, c1, c2;
597
598 if(n < 0)
599 n = (b.n<<BSHIFT)-1;
600 c1 = m>>BSHIFT;
601 c2 = n>>BSHIFT;
602 m &= BMASK;
603 n &= BMASK;
604 if(c1 == c2){
605 b.b[c1] &= ~MASK(m, n);
606 return;
607 }
608 for(i = c1+1; i < c2; i++)
609 b.b[i] = 0;
610 b.b[c1] &= ~MASK(m, BLEN-1);
611 b.b[c2] &= ~MASK(0, n);
612 }
613
614 /* b = a op b */
615 static Bits
boper(int o,Bits a,Bits b)616 boper(int o, Bits a, Bits b)
617 {
618 int i, n;
619
620 n = a.n;
621 if(b.n != n)
622 fatal("boper %d %d %d", o, a.n, b.n);
623 for(i = 0; i < n; i++)
624 b.b[i] = bop(o, a.b[i], b.b[i]);
625 return b;
626 }
627
628 static int
beq(Bits a,Bits b)629 beq(Bits a, Bits b)
630 {
631 int i, n;
632
633 n = a.n;
634 for(i = 0; i < n; i++)
635 if(a.b[i] != b.b[i])
636 return 0;
637 return 1;
638 }
639
640 static int
bzero(Bits b)641 bzero(Bits b)
642 {
643 int i, n;
644
645 n = b.n;
646 for(i = 0; i < n; i++)
647 if(b.b[i] != 0)
648 return 0;
649 return 1;
650 }
651
652 static int
bitcnt(Bits b)653 bitcnt(Bits b)
654 {
655 int i, m, n;
656
657 m = b.n;
658 n = 0;
659 for(i = 0; i < m; i++)
660 n += bitc(b.b[i]);
661 return n;
662 }
663
664 static int
topbit(Bits b)665 topbit(Bits b)
666 {
667 int i, n;
668
669 n = b.n;
670 for(i = n-1; i >= 0; i--)
671 if(b.b[i] != 0)
672 return (i<<BSHIFT)+topb(b.b[i]);
673 return -1;
674 }
675
676 static int
lowbit(Bits b)677 lowbit(Bits b)
678 {
679 int i, n;
680
681 n = b.n;
682 for(i = 0; i < n; i++)
683 if(b.b[i] != 0)
684 return (i<<BSHIFT)+lowb(b.b[i]);
685 return -1;
686 }
687
688 static void
pbits(Bits b)689 pbits(Bits b)
690 {
691 int i, n;
692
693 n = b.n;
694 for(i = 0; i < n; i++)
695 pbit(b.b[i], i<<BSHIFT);
696 }
697
698 static char*
decname(Decl * d)699 decname(Decl *d)
700 {
701 if(d->sym == nil)
702 return "<nil>";
703 return d->sym->name;
704 }
705
706 static void
warning(Inst * i,char * s,Decl * d,Decl * sd)707 warning(Inst *i, char *s, Decl *d, Decl *sd)
708 {
709 int n;
710 char *f;
711 Decl *ds;
712
713 n = 0;
714 for(ds = sd; ds != nil; ds = ds->next)
715 if(ds->link == d)
716 n += strlen(ds->sym->name)+1;
717 if(n == 0){
718 warn(i->src.start, "%s: %s", d->sym->name, s);
719 return;
720 }
721 n += strlen(d->sym->name);
722 f = malloc(n+1);
723 strcpy(f, d->sym->name);
724 for(ds = sd; ds != nil; ds = ds->next){
725 if(ds->link == d){
726 strcat(f, "/");
727 strcat(f, ds->sym->name);
728 }
729 }
730 warn(i->src.start, "%s: %s", f, s);
731 free(f);
732 }
733
734 static int
inspc(Inst * in)735 inspc(Inst *in)
736 {
737 int n;
738 Inst *i;
739
740 n = 0;
741 for(i = in; i != nil; i = i->next)
742 i->pc = n++;
743 return n;
744 }
745
746 static Inst*
pc2i(Block * b,int pc)747 pc2i(Block *b, int pc)
748 {
749 Inst *i;
750
751 for( ; b != nil; b = b->next){
752 if(pc > b->last->pc)
753 continue;
754 for(i = b->first; ; i = i->next){
755 if(i->pc == pc)
756 return i;
757 if(i == b->last)
758 fatal("pc2i a");
759 }
760 }
761 fatal("pc2i b");
762 return nil;
763 }
764
765 static void
padr(int am,Addr * a,Inst * br)766 padr(int am, Addr *a, Inst *br)
767 {
768 long reg;
769
770 if(br != nil){
771 print("$%ld", br->pc);
772 return;
773 }
774 reg = a->reg;
775 if(a->decl != nil && am != Adesc)
776 reg += a->decl->offset;
777 switch(am){
778 case Anone:
779 print("-");
780 break;
781 case Aimm:
782 case Apc:
783 case Adesc:
784 print("$%ld", a->offset);
785 break;
786 case Aoff:
787 print("$%ld", a->decl->iface->offset);
788 break;
789 case Anoff:
790 print("-$%ld", a->decl->iface->offset);
791 break;
792 case Afp:
793 print("%ld(fp)", reg);
794 break;
795 case Afpind:
796 print("%ld(%ld(fp))", a->offset, reg);
797 break;
798 case Amp:
799 print("%ld(mp)", reg);
800 break;
801 case Ampind:
802 print("%ld(%ld(mp))", a->offset, reg);
803 break;
804 case Aldt:
805 print("$%ld", reg);
806 break;
807 case Aerr:
808 default:
809 print("%ld(%ld(?%d?))", a->offset, reg, am);
810 break;
811 }
812 }
813
814 static void
pins(Inst * i)815 pins(Inst *i)
816 {
817 /* print("%L %ld ", i->src.start, i->pc); */
818 print(" %ld ", i->pc);
819 if(i->op < MAXDIS)
820 print("%s", instname[i->op]);
821 else
822 print("noop");
823 print(" ");
824 padr(i->sm, &i->s, nil);
825 print(", ");
826 padr(i->mm, &i->m, nil);
827 print(", ");
828 padr(i->dm, &i->d, i->branch);
829 print("\n");
830 }
831
832 static void
blfree(Blist * bl)833 blfree(Blist *bl)
834 {
835 Blist *nbl;
836
837 for( ; bl != nil; bl = nbl){
838 nbl = bl->next;
839 free(bl);
840 }
841 }
842
843 static void
freebits(Bits * bs,int nv)844 freebits(Bits *bs, int nv)
845 {
846 int i;
847
848 for(i = 0; i < nv; i++)
849 bfree(bs[i]);
850 free(bs);
851 }
852
853 static void
freeblks(Block * b)854 freeblks(Block *b)
855 {
856 Block *nb;
857
858 for( ; b != nil; b = nb){
859 blfree(b->pred);
860 blfree(b->succ);
861 bfree(b->kill);
862 bfree(b->gen);
863 bfree(b->in);
864 bfree(b->out);
865 nb = b->next;
866 free(b);
867 }
868 }
869
870 static int
len(Decl * d)871 len(Decl *d)
872 {
873 int n;
874
875 n = 0;
876 for( ; d != nil; d = d->next)
877 n++;
878 return n;
879 }
880
881 static Bits*
allocbits(int nv,int npc)882 allocbits(int nv, int npc)
883 {
884 int i;
885 Bits *defs;
886
887 defs = (Bits*)allocmem(nv*sizeof(Bits));
888 for(i = 0; i < nv; i++)
889 defs[i] = bnew(npc, 1);
890 return defs;
891 }
892
893 static int
bitcount(Bits * bs,int nv)894 bitcount(Bits *bs, int nv)
895 {
896 int i, n;
897
898 n = 0;
899 for(i = 0; i < nv; i++)
900 n += bitcnt(bs[i]);
901 return n;
902 }
903
904 static Block*
mkblock(Inst * i)905 mkblock(Inst *i)
906 {
907 Block *b;
908
909 b = allocmem(sizeof(Block));
910 *b = zblock;
911 b->first = b->last = i;
912 return b;
913 }
914
915 static Blist*
mkblist(Block * b,Blist * nbl)916 mkblist(Block *b, Blist *nbl)
917 {
918 Blist *bl;
919
920 bl = allocmem(sizeof(Blist));
921 bl->block = b;
922 bl->next = nbl;
923 return bl;
924 }
925
926 static void
leader(Inst * i,Array * ab)927 leader(Inst *i, Array *ab)
928 {
929 int m, n;
930 Block *b, **a;
931
932 if(i != nil && i->pc == 0){
933 if((n = ab->n) == (m = ab->m)){
934 a = ab->a;
935 ab->a = allocmem(2*m*sizeof(Block*));
936 memcpy(ab->a, a, m*sizeof(Block*));
937 ab->m = 2*m;
938 free(a);
939 }
940 b = mkblock(i);
941 b->dfn = n;
942 ab->a[n] = b;
943 i->pc = ab->n = n+1;
944 }
945 }
946
947 static Block*
findb(Inst * i,Array * ab)948 findb(Inst *i, Array *ab)
949 {
950 if(i == nil)
951 return nil;
952 if(i->pc <= 0)
953 fatal("pc <= 0 in findb");
954 return ab->a[i->pc-1];
955 }
956
957 static int
memb(Block * b,Blist * bl)958 memb(Block *b, Blist *bl)
959 {
960 for( ; bl != nil; bl = bl->next)
961 if(bl->block == b)
962 return 1;
963 return 0;
964 }
965
966 static int
canfallthrough(Inst * i)967 canfallthrough(Inst *i)
968 {
969 if(i == nil)
970 return 0;
971 switch(i->op){
972 case IGOTO:
973 case ICASE:
974 case ICASEL:
975 case ICASEC:
976 case IRET:
977 case IEXIT:
978 case IRAISE:
979 case IJMP:
980 return 0;
981 case INOOP:
982 return i->branch != nil;
983 }
984 return 1;
985 }
986
987 static void
predsucc(Block * b1,Block * b2)988 predsucc(Block *b1, Block *b2)
989 {
990 if(b1 == nil || b2 == nil)
991 return;
992 if(!memb(b1, b2->pred))
993 b2->pred = mkblist(b1, b2->pred);
994 if(!memb(b2, b1->succ))
995 b1->succ = mkblist(b2, b1->succ);
996 }
997
998 static Block*
mkblocks(Inst * in,int * nb)999 mkblocks(Inst *in, int *nb)
1000 {
1001 Inst *i;
1002 Block *b, *firstb, *lastb;
1003 Label *lab;
1004 Array *ab;
1005 int j, n;
1006
1007 ab = allocmem(sizeof(Array));
1008 ab->n = 0;
1009 ab->m = 16;
1010 ab->a = allocmem(ab->m*sizeof(Block*));
1011 leader(in, ab);
1012 for(i = in; i != nil; i = i->next){
1013 switch(i->op){
1014 case IGOTO:
1015 case ICASE:
1016 case ICASEL:
1017 case ICASEC:
1018 case INOOP:
1019 if(i->op == INOOP && i->branch != nil){
1020 leader(i->branch, ab);
1021 leader(i->next, ab);
1022 break;
1023 }
1024 leader(i->d.decl->ty->cse->iwild, ab);
1025 lab = i->d.decl->ty->cse->labs;
1026 n = i->d.decl->ty->cse->nlab;
1027 for(j = 0; j < n; j++)
1028 leader(lab[j].inst, ab);
1029 leader(i->next, ab);
1030 break;
1031 case IRET:
1032 case IEXIT:
1033 case IRAISE:
1034 leader(i->next, ab);
1035 break;
1036 case IJMP:
1037 leader(i->branch, ab);
1038 leader(i->next, ab);
1039 break;
1040 default:
1041 if(i->branch != nil){
1042 leader(i->branch, ab);
1043 leader(i->next, ab);
1044 }
1045 break;
1046 }
1047 }
1048 firstb = lastb = mkblock(nil);
1049 for(i = in; i != nil; i = i->next){
1050 if(i->pc != 0){
1051 b = findb(i, ab);
1052 b->prev = lastb;
1053 lastb->next = b;
1054 if(canfallthrough(lastb->last))
1055 predsucc(lastb, b);
1056 lastb = b;
1057 }
1058 else
1059 lastb->last = i;
1060 switch(i->op){
1061 case IGOTO:
1062 case ICASE:
1063 case ICASEL:
1064 case ICASEC:
1065 case INOOP:
1066 if(i->op == INOOP && i->branch != nil){
1067 b = findb(i->next, ab);
1068 predsucc(lastb, b);
1069 b = findb(i->branch, ab);
1070 predsucc(lastb, b);
1071 break;
1072 }
1073 b = findb(i->d.decl->ty->cse->iwild, ab);
1074 predsucc(lastb, b);
1075 lab = i->d.decl->ty->cse->labs;
1076 n = i->d.decl->ty->cse->nlab;
1077 for(j = 0; j < n; j++){
1078 b = findb(lab[j].inst, ab);
1079 predsucc(lastb, b);
1080 }
1081 break;
1082 case IRET:
1083 case IEXIT:
1084 case IRAISE:
1085 break;
1086 case IJMP:
1087 b = findb(i->branch, ab);
1088 predsucc(lastb, b);
1089 break;
1090 default:
1091 if(i->branch != nil){
1092 b = findb(i->next, ab);
1093 predsucc(lastb, b);
1094 b = findb(i->branch, ab);
1095 predsucc(lastb, b);
1096 }
1097 break;
1098 }
1099 }
1100 *nb = ab->n;
1101 free(ab->a);
1102 free(ab);
1103 b = firstb->next;
1104 b->prev = nil;
1105 return b;
1106 }
1107
1108 static int
back(Block * b1,Block * b2)1109 back(Block *b1, Block *b2)
1110 {
1111 return b1->dfn >= b2->dfn;
1112 }
1113
1114 static void
pblocks(Block * b,int nb)1115 pblocks(Block *b, int nb)
1116 {
1117 Inst *i;
1118 Blist *bl;
1119
1120 print("--------------------%d blocks--------------------\n", nb);
1121 print("------------------------------------------------\n");
1122 for( ; b != nil; b = b->next){
1123 print("dfn=%d\n", b->dfn);
1124 print(" pred ");
1125 for(bl = b->pred; bl != nil; bl = bl->next)
1126 print("%d%s ", bl->block->dfn, back(bl->block, b) ? "*" : "");
1127 print("\n");
1128 print(" succ ");
1129 for(bl = b->succ; bl != nil; bl = bl->next)
1130 print("%d%s ", bl->block->dfn, back(b, bl->block) ? "*" : "");
1131 print("\n");
1132 for(i = b->first; i != nil; i = i->next){
1133 // print(" %I\n", i);
1134 pins(i);
1135 if(i == b->last)
1136 break;
1137 }
1138 }
1139 print("------------------------------------------------\n");
1140 }
1141
1142 static void
ckblocks(Inst * in,Block * b,int nb)1143 ckblocks(Inst *in, Block *b, int nb)
1144 {
1145 int n;
1146 Block *lastb;
1147
1148 if(b->first != in)
1149 fatal("A - %d", b->dfn);
1150 n = 0;
1151 lastb = nil;
1152 for( ; b != nil; b = b->next){
1153 n++;
1154 if(b->prev != lastb)
1155 fatal("a - %d\n", b->dfn);
1156 if(b->prev != nil && b->prev->next != b)
1157 fatal("b - %d\n", b->dfn);
1158 if(b->next != nil && b->next->prev != b)
1159 fatal("c - %d\n", b->dfn);
1160
1161 if(b->prev != nil && b->prev->last->next != b->first)
1162 fatal("B - %d\n", b->dfn);
1163 if(b->next != nil && b->last->next != b->next->first)
1164 fatal("C - %d\n", b->dfn);
1165 if(b->next == nil && b->last->next != nil)
1166 fatal("D - %d\n", b->dfn);
1167
1168 if(b->last->branch != nil && b->succ->block->first != b->last->branch)
1169 fatal("0 - %d\n", b->dfn);
1170
1171 lastb = b;
1172 }
1173 if(n != nb)
1174 fatal("N - %d %d\n", n, nb);
1175 }
1176
1177 static void
dfs0(Block * b,int * n)1178 dfs0(Block *b, int *n)
1179 {
1180 Block *s;
1181 Blist *bl;
1182
1183 b->flags = 1;
1184 for(bl = b->succ; bl != nil; bl = bl->next){
1185 s = bl->block;
1186 if(s->flags == 0)
1187 dfs0(s, n);
1188 }
1189 b->dfn = --(*n);
1190 }
1191
1192 static int
dfs(Block * b,int nb)1193 dfs(Block *b, int nb)
1194 {
1195 int n, u;
1196 Block *b0;
1197
1198 b0 = b;
1199 n = nb;
1200 dfs0(b0, &n);
1201 u = 0;
1202 for(b = b0; b != nil; b = b->next){
1203 if(b->flags == 0){ /* unreachable: see foldbranch */
1204 fatal("found unreachable code");
1205 u++;
1206 b->prev->next = b->next;
1207 if(b->next){
1208 b->next->prev = b->prev;
1209 b->prev->last->next = b->next->first;
1210 }
1211 else
1212 b->prev->last->next = nil;
1213 }
1214 b->flags = 0;
1215 }
1216 if(u){
1217 for(b = b0; b != nil; b = b->next)
1218 b->dfn -= u;
1219 }
1220 return nb-u;
1221 }
1222
1223 static void
loop0(Block * b)1224 loop0(Block *b)
1225 {
1226 Block *p;
1227 Blist *bl;
1228
1229 b->flags = 1;
1230 for(bl = b->pred; bl != nil; bl = bl->next){
1231 p = bl->block;
1232 if(p->flags == 0)
1233 loop0(p);
1234 }
1235 }
1236
1237 /* b1->b2 a back edge */
1238 static void
loop(Block * b,Block * b1,Block * b2)1239 loop(Block *b, Block *b1, Block *b2)
1240 {
1241 if(0 && debug['o'])
1242 print("back edge %d->%d\n", b1->dfn, b2->dfn);
1243 b2->flags = 1;
1244 if(b1->flags == 0)
1245 loop0(b1);
1246 if(0 && debug['o'])
1247 print(" loop ");
1248 for( ; b != nil; b = b->next){
1249 if(b->flags && 0 && debug['o'])
1250 print("%d ", b->dfn);
1251 b->flags = 0;
1252 }
1253 if(0 && debug['o'])
1254 print("\n");
1255 }
1256
1257 static void
loops(Block * b)1258 loops(Block *b)
1259 {
1260 Block *b0;
1261 Blist *bl;
1262
1263 b0 = b;
1264 for( ; b != nil; b = b->next){
1265 for(bl = b->succ; bl != nil; bl = bl->next){
1266 if(back(b, bl->block))
1267 loop(b0, b, bl->block);
1268 }
1269 }
1270 }
1271
1272 static int
imm(int m,Addr * a)1273 imm(int m, Addr *a)
1274 {
1275 if(m == Aimm)
1276 return a->offset;
1277 fatal("bad immediate value");
1278 return -1;
1279 }
1280
1281 static int
desc(int m,Addr * a)1282 desc(int m, Addr *a)
1283 {
1284 if(m == Adesc)
1285 return a->decl->desc->size;
1286 fatal("bad descriptor value");
1287 return -1;
1288 }
1289
1290 static int
fpoff(int m,Addr * a)1291 fpoff(int m, Addr *a)
1292 {
1293 int off;
1294 Decl *d;
1295
1296 if(m == Afp || m == Afpind){
1297 off = a->reg;
1298 if((d = a->decl) != nil)
1299 off += d->offset;
1300 return off;
1301 }
1302 return -1;
1303 }
1304
1305 static int
size(Inst * i)1306 size(Inst *i)
1307 {
1308 switch(i->op){
1309 case ISEND:
1310 case IRECV:
1311 case IALT:
1312 case INBALT:
1313 case ILEA:
1314 return i->m.offset;
1315 case IMOVM:
1316 case IHEADM:
1317 case ICONSM:
1318 return imm(i->mm, &i->m);
1319 case IMOVMP:
1320 case IHEADMP:
1321 case ICONSMP:
1322 return desc(i->mm, &i->m);
1323 break;
1324 }
1325 fatal("bad op in size");
1326 return -1;
1327 }
1328
1329 static Decl*
mkdec(int o)1330 mkdec(int o)
1331 {
1332 Decl *d;
1333
1334 d = mkdecl(&nosrc, Dlocal, tint);
1335 d->offset = o;
1336 return d;
1337 }
1338
1339 static void
mkdecls(void)1340 mkdecls(void)
1341 {
1342 regdecls = mkdec(REGRET*IBY2WD);
1343 regdecls->next = mkdec(STemp);
1344 regdecls->next->next = mkdec(DTemp);
1345 }
1346
1347 static Decl*
sharedecls(Decl * d)1348 sharedecls(Decl *d)
1349 {
1350 Decl *ld;
1351
1352 ld = d;
1353 for(d = d->next ; d != nil; d = d->next){
1354 if(d->offset <= ld->offset)
1355 break;
1356 ld = d;
1357 }
1358 return d;
1359 }
1360
1361 static int
finddec(int o,int s,Decl * vars,int * nv,Inst * i)1362 finddec(int o, int s, Decl *vars, int *nv, Inst *i)
1363 {
1364 int m, n;
1365 Decl *d;
1366
1367 n = 0;
1368 for(d = vars; d != nil; d = d->next){
1369 if(o >= d->offset && o < d->offset+d->ty->size){
1370 m = 1;
1371 while(o+s > d->offset+d->ty->size){
1372 m++;
1373 d = d->next;
1374 }
1375 *nv = m;
1376 return n;
1377 }
1378 n++;
1379 }
1380 // print("%d %d missing\n", o, s);
1381 pins(i);
1382 fatal("missing decl");
1383 return -1;
1384 }
1385
1386 static void
setud(Bits * b,int id,int n,int pc)1387 setud(Bits *b, int id, int n, int pc)
1388 {
1389 if(id < 0)
1390 return;
1391 while(--n >= 0)
1392 bset(b[id++], pc);
1393 }
1394
1395 static void
ud(Inst * i,Decl * vars,Bits * uses,Bits * defs)1396 ud(Inst *i, Decl *vars, Bits *uses, Bits *defs)
1397 {
1398 ushort f;
1399 int id, j, nv, pc, sz, s, m, d, ss, sm, sd;
1400 Optab *t;
1401 Idlist *l;
1402
1403 pc = i->pc;
1404 ss = 0;
1405 t = &opflags[i->op];
1406 f = t->flags;
1407 sz = t->size;
1408 s = fpoff(i->sm, &i->s);
1409 m = fpoff(i->mm, &i->m);
1410 d = fpoff(i->dm, &i->d);
1411 if(f&Mduse && i->mm == Anone)
1412 f |= Duse;
1413 if(s >= 0){
1414 if(i->sm == Afp){
1415 ss = SS(sz);
1416 if(ss == Mp)
1417 ss = size(i);
1418 }
1419 else
1420 ss = IBY2WD;
1421 id = finddec(s, ss, vars, &nv, i);
1422 if(f&Suse)
1423 setud(uses, id, nv, pc);
1424 if(f&Sdef){
1425 if(i->sm == Afp)
1426 setud(defs, id, nv, pc);
1427 else
1428 setud(uses, id, nv, pc);
1429 }
1430 }
1431 if(m >= 0){
1432 if(i->mm == Afp){
1433 sm = SM(sz);
1434 if(sm == Mp)
1435 sm = size(i);
1436 }
1437 else
1438 sm = IBY2WD;
1439 id = finddec(m, sm, vars, &nv, i);
1440 if(f&Muse)
1441 setud(uses, id, nv, pc);
1442 if(f&Mdef){
1443 if(i->mm == Afp)
1444 setud(defs, id, nv, pc);
1445 else
1446 setud(uses, id, nv, pc);
1447 }
1448 }
1449 if(d >= 0){
1450 if(i->dm == Afp){
1451 sd = SD(sz);
1452 if(sd == Mp)
1453 sd = size(i);
1454 }
1455 else
1456 sd = IBY2WD;
1457 id = finddec(d, sd, vars, &nv, i);
1458 if(f&Duse)
1459 setud(uses, id, nv, pc);
1460 if(f&Ddef){
1461 if(i->dm == Afp)
1462 setud(defs, id, nv, pc);
1463 else
1464 setud(uses, id, nv, pc);
1465 }
1466 }
1467 if(f&Tuse1){
1468 id = finddec(STemp, IBY2WD, vars, &nv, i);
1469 setud(uses, id, nv, pc);
1470 }
1471 if(f&Tuse2){
1472 id = finddec(DTemp, IBY2WD, vars, &nv, i);
1473 setud(uses, id, nv, pc);
1474 }
1475 if(i->op == ILEA){
1476 if(s >= 0){
1477 id = finddec(s, ss, vars, &nv, i);
1478 if(i->sm == Afp && i->m.reg == 0)
1479 setud(defs, id, nv, pc);
1480 else
1481 setud(uses, id, nv, pc);
1482 }
1483 }
1484 if(0)
1485 switch(i->op){
1486 case ILEA:
1487 if(s >= 0){
1488 id = finddec(s, ss, vars, &nv, i);
1489 if(id < 0)
1490 break;
1491 for(j = 0; j < nv; j++){
1492 if(i->sm == Afp && i->m.reg == 0)
1493 addlist(&deflist, id++);
1494 else
1495 addlist(&uselist, id++);
1496 }
1497 }
1498 break;
1499 case IALT:
1500 case INBALT:
1501 case ICALL:
1502 case IMCALL:
1503 for(l = deflist; l != nil; l = l->next){
1504 id = l->id;
1505 bset(defs[id], pc);
1506 }
1507 for(l = uselist; l != nil; l = l->next){
1508 id = l->id;
1509 bset(uses[id], pc);
1510 }
1511 freelist(&deflist);
1512 freelist(&uselist);
1513 break;
1514 }
1515 }
1516
1517 static void
usedef(Inst * in,Decl * vars,Bits * uses,Bits * defs)1518 usedef(Inst *in, Decl *vars, Bits *uses, Bits *defs)
1519 {
1520 Inst *i;
1521
1522 for(i = in; i != nil; i = i->next)
1523 ud(i, vars, uses, defs);
1524 }
1525
1526 static void
pusedef(Bits * ud,int nv,Decl * d,char * s)1527 pusedef(Bits *ud, int nv, Decl *d, char *s)
1528 {
1529 int i;
1530
1531 print("%s\n", s);
1532 for(i = 0; i < nv; i++){
1533 if(!bzero(ud[i])){
1534 print("\t%s(%ld): ", decname(d), d->offset);
1535 pbits(ud[i]);
1536 print("\n");
1537 }
1538 d = d->next;
1539 }
1540 }
1541
1542 static void
dummydefs(Bits * defs,int nv,int npc)1543 dummydefs(Bits *defs, int nv, int npc)
1544 {
1545 int i;
1546
1547 for(i = 0; i < nv; i++)
1548 bset(defs[i], npc++);
1549 }
1550
1551 static void
dogenkill(Block * b,Bits * defs,int nv)1552 dogenkill(Block *b, Bits *defs, int nv)
1553 {
1554 int i, n, t;
1555 Bits v;
1556
1557 n = defs[0].n;
1558 v = bnew(n, 0);
1559 for( ; b != nil; b = b->next){
1560 b->gen = bnew(n, 0);
1561 b->kill = bnew(n, 0);
1562 b->in = bnew(n, 0);
1563 b->out = bnew(n, 0);
1564 for(i = 0; i < nv; i++){
1565 boper(Bclr, v, v);
1566 bsets(v, b->first->pc, b->last->pc);
1567 boper(Band, defs[i], v);
1568 t = topbit(v);
1569 if(t >= 0)
1570 bset(b->gen, t);
1571 else
1572 continue;
1573 boper(Bclr, v, v);
1574 bsets(v, b->first->pc, b->last->pc);
1575 boper(Binv, v, v);
1576 boper(Band, defs[i], v);
1577 boper(Bor, v, b->kill);
1578 }
1579 }
1580 bfree(v);
1581 }
1582
1583 static void
udflow(Block * b,int nv,int npc)1584 udflow(Block *b, int nv, int npc)
1585 {
1586 int iter;
1587 Block *b0, *p;
1588 Blist *bl;
1589 Bits newin;
1590
1591 b0 = b;
1592 for(b = b0; b != nil; b = b->next)
1593 boper(Bstore, b->gen, b->out);
1594 newin = bnew(b0->in.n, 0);
1595 iter = 1;
1596 while(iter){
1597 iter = 0;
1598 for(b = b0; b != nil; b = b->next){
1599 boper(Bclr, newin, newin);
1600 for(bl = b->pred; bl != nil; bl = bl->next){
1601 p = bl->block;
1602 boper(Bor, p->out, newin);
1603 }
1604 if(b == b0)
1605 bsets(newin, npc, npc+nv-1);
1606 if(!beq(b->in, newin))
1607 iter = 1;
1608 boper(Bstore, newin, b->in);
1609 boper(Bstore, b->in, b->out);
1610 boper(Bandrev, b->kill, b->out);
1611 boper(Bor, b->gen, b->out);
1612 }
1613 }
1614 bfree(newin);
1615 }
1616
1617 static void
pflows(Block * b)1618 pflows(Block *b)
1619 {
1620 for( ; b != nil; b = b->next){
1621 print("block %d\n", b->dfn);
1622 print(" gen: "); pbits(b->gen); print("\n");
1623 print(" kill: "); pbits(b->kill); print("\n");
1624 print(" in: "); pbits(b->in); print("\n");
1625 print(" out: "); pbits(b->out); print("\n");
1626 }
1627 }
1628
1629 static int
set(Decl * d)1630 set(Decl *d)
1631 {
1632 if(d->store == Darg)
1633 return 1;
1634 if(d->sym == nil) /* || d->sym->name[0] == '.') */
1635 return 1;
1636 if(tattr[d->ty->kind].isptr || d->ty->kind == Texception)
1637 return 1;
1638 return 0;
1639 }
1640
1641 static int
used(Decl * d)1642 used(Decl *d)
1643 {
1644 if(d->sym == nil ) /* || d->sym->name[0] == '.') */
1645 return 1;
1646 return 0;
1647 }
1648
1649 static void
udchain(Block * b,Decl * ds,int nv,int npc,Bits * defs,Bits * uses,Decl * sd)1650 udchain(Block *b, Decl *ds, int nv, int npc, Bits *defs, Bits *uses, Decl *sd)
1651 {
1652 int i, n, p, q;
1653 Bits d, u, dd, ud;
1654 Block *b0;
1655 Inst *in;
1656
1657 b0 = b;
1658 n = defs[0].n;
1659 u = bnew(n, 0);
1660 d = bnew(n, 0);
1661 dd = bnew(n, 0);
1662 ud = bnew(n, 0);
1663 for(i = 0; i < nv; i++){
1664 boper(Bstore, defs[i], ud);
1665 bclr(ud, npc+i);
1666 for(b = b0 ; b != nil; b = b->next){
1667 boper(Bclr, u, u);
1668 bsets(u, b->first->pc, b->last->pc);
1669 boper(Band, uses[i], u);
1670 boper(Bclr, d, d);
1671 bsets(d, b->first->pc, b->last->pc);
1672 boper(Band, defs[i], d);
1673 for(;;){
1674 p = topbit(u);
1675 if(p < 0)
1676 break;
1677 bclr(u, p);
1678 bclrs(d, p, -1);
1679 q = topbit(d);
1680 if(q >= 0){
1681 bclr(ud, q);
1682 if(debug['o'])
1683 print("udc b=%d v=%d(%s/%ld) u=%d d=%d\n", b->dfn, i, decname(ds), ds->offset, p, q);
1684 }
1685 else{
1686 boper(Bstore, defs[i], dd);
1687 boper(Band, b->in, dd);
1688 boper(Bandrev, dd, ud);
1689 if(!bzero(dd)){
1690 if(debug['o']){
1691 print("udc b=%d v=%d(%s/%ld) u=%d d=", b->dfn, i, decname(ds), ds->offset, p);
1692 pbits(dd);
1693 print("\n");
1694 }
1695 if(bmem(dd, npc+i) && !set(ds))
1696 warning(pc2i(b0, p), "used and not set", ds, sd);
1697 }
1698 else
1699 fatal("no defs in udchain");
1700 }
1701 }
1702 }
1703 for(;;){
1704 p = topbit(ud);
1705 if(p < 0)
1706 break;
1707 bclr(ud, p);
1708 if(!used(ds)){
1709 in = pc2i(b0, p);
1710 if(isnilsrc(&in->src)) /* nilling code */
1711 in->op = INOOP; /* elim p from bitmaps ? */
1712 else if(limbovar(ds) && !structure(ds->ty))
1713 warning(in, "set and not used", ds, sd);
1714 }
1715 }
1716 ds = ds->next;
1717 }
1718 bfree(u);
1719 bfree(d);
1720 bfree(dd);
1721 bfree(ud);
1722 }
1723
1724 static void
ckflags(void)1725 ckflags(void)
1726 {
1727 int i, j, k, n;
1728 Optab *o;
1729
1730 n = nelem(opflags);
1731 o = opflags;
1732 for(i = 0; i < n; i++){
1733 j = (o->flags&(Suse|Sdef)) != 0;
1734 k = SS(o->size) != 0;
1735 if(j != k){
1736 if(!(j == 0 && k == 1 && i == ILEA))
1737 fatal("S %ld %s\n", o-opflags, instname[i]);
1738 }
1739 j = (o->flags&(Muse|Mdef)) != 0;
1740 k = SM(o->size) != 0;
1741 if(j != k)
1742 fatal("M %ld %s\n", o-opflags, instname[i]);
1743 j = (o->flags&(Duse|Ddef)) != 0;
1744 k = SD(o->size) != 0;
1745 if(j != k){
1746 if(!(j == 1 && k == 0 && (i == IGOTO || i == ICASE || i == ICASEC || i == ICASEL)))
1747 fatal("D %ld %s\n", o-opflags, instname[i]);
1748 }
1749 o++;
1750 }
1751 }
1752
1753 void
optim(Inst * in,Decl * d)1754 optim(Inst *in, Decl *d)
1755 {
1756 int nb, npc, nv, nd, nu;
1757 Block *b;
1758 Bits *uses, *defs;
1759 Decl *sd;
1760
1761 ckflags();
1762 if(debug['o'])
1763 print("************************************************\nfunction %s\n************************************************\n", d->sym->name);
1764 if(in == nil || errors > 0)
1765 return;
1766 d = d->ty->ids;
1767 if(regdecls == nil)
1768 mkdecls();
1769 regdecls->next->next->next = d;
1770 d = regdecls;
1771 sd = sharedecls(d);
1772 if(debug['o'])
1773 printdecls(d);
1774 b = mkblocks(in, &nb);
1775 ckblocks(in, b, nb);
1776 npc = inspc(in);
1777 nb = dfs(b, nb);
1778 if(debug['o'])
1779 pblocks(b, nb);
1780 loops(b);
1781 nv = len(d);
1782 uses = allocbits(nv, npc+nv);
1783 defs = allocbits(nv, npc+nv);
1784 dummydefs(defs, nv, npc);
1785 usedef(in, d, uses, defs);
1786 if(debug['o']){
1787 pusedef(uses, nv, d, "uses");
1788 pusedef(defs, nv, d, "defs");
1789 }
1790 nu = bitcount(uses, nv);
1791 nd = bitcount(defs, nv);
1792 dogenkill(b, defs, nv);
1793 udflow(b, nv, npc);
1794 if(debug['o'])
1795 pflows(b);
1796 udchain(b, d, nv, npc, defs, uses, sd);
1797 freeblks(b);
1798 freebits(uses, nv);
1799 freebits(defs, nv);
1800 if(debug['o'])
1801 print("nb=%d npc=%d nv=%d nd=%d nu=%d\n", nb, npc, nv, nd, nu);
1802 }
1803
1804