xref: /inferno-os/limbo/optim.c (revision 1ca4518d984a3e2dee44a160397cb720c61d2449)
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