Warning: Attempt to read property "date" on null in /usr/local/www/websvn.planix.org/blame.php on line 247

Warning: Attempt to read property "msg" on null in /usr/local/www/websvn.planix.org/blame.php on line 247
WebSVN – planix.SVN – Blame – /os/branches/feature_fixcpp/sys/src/cmd/5c/peep.c – Rev 2

Subversion Repositories planix.SVN

Rev

Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 1
#include "gc.h"
2
 
3
int xtramodes(Reg*, Adr*);
4
 
5
void
6
peep(void)
7
{
8
	Reg *r, *r1, *r2;
9
	Prog *p, *p1;
10
	int t;
11
/*
12
 * complete R structure
13
 */
14
	t = 0;
15
	for(r=firstr; r!=R; r=r1) {
16
		r1 = r->link;
17
		if(r1 == R)
18
			break;
19
		p = r->prog->link;
20
		while(p != r1->prog)
21
		switch(p->as) {
22
		default:
23
			r2 = rega();
24
			r->link = r2;
25
			r2->link = r1;
26
 
27
			r2->prog = p;
28
			r2->p1 = r;
29
			r->s1 = r2;
30
			r2->s1 = r1;
31
			r1->p1 = r2;
32
 
33
			r = r2;
34
			t++;
35
 
36
		case ADATA:
37
		case AGLOBL:
38
		case ANAME:
39
		case ASIGNAME:
40
			p = p->link;
41
		}
42
	}
43
 
44
loop1:
45
	t = 0;
46
	for(r=firstr; r!=R; r=r->link) {
47
		p = r->prog;
48
		if(p->as == ASLL || p->as == ASRL || p->as == ASRA) {
49
			/*
50
			 * elide shift into D_SHIFT operand of subsequent instruction
51
			 */
52
			if(shiftprop(r)) {
53
				excise(r);
54
				t++;
55
			}
56
		}
57
		if(p->as == AMOVW || p->as == AMOVF || p->as == AMOVD)
58
		if(regtyp(&p->to)) {
59
			if(p->from.type == D_CONST)
60
				constprop(&p->from, &p->to, r->s1);
61
			else if(regtyp(&p->from))
62
			if(p->from.type == p->to.type) {
63
				if(copyprop(r)) {
64
					excise(r);
65
					t++;
66
				} else
67
				if(subprop(r) && copyprop(r)) {
68
					excise(r);
69
					t++;
70
				}
71
			}
72
		}
73
	}
74
	if(t)
75
		goto loop1;
76
	/*
77
	 * look for MOVB x,R; MOVB R,R
78
	 */
79
	for(r=firstr; r!=R; r=r->link) {
80
		p = r->prog;
81
		switch(p->as) {
82
		default:
83
			continue;
84
		case AEOR:
85
			/*
86
			 * EOR -1,x,y => MVN x,y
87
			 */
88
			if(p->from.type == D_CONST && p->from.offset == -1) {
89
				p->as = AMVN;
90
				p->from.type = D_REG;
91
				if(p->reg != NREG)
92
					p->from.reg = p->reg;
93
				else
94
					p->from.reg = p->to.reg;
95
				p->reg = NREG;
96
			}
97
			continue;
98
		case AMOVH:
99
		case AMOVHU:
100
		case AMOVB:
101
		case AMOVBU:
102
			if(p->to.type != D_REG)
103
				continue;
104
			break;
105
		}
106
		r1 = r->link;
107
		if(r1 == R)
108
			continue;
109
		p1 = r1->prog;
110
		if(p1->as != p->as)
111
			continue;
112
		if(p1->from.type != D_REG || p1->from.reg != p->to.reg)
113
			continue;
114
		if(p1->to.type != D_REG || p1->to.reg != p->to.reg)
115
			continue;
116
		excise(r1);
117
	}
118
 
119
	for(r=firstr; r!=R; r=r->link) {
120
		p = r->prog;
121
		switch(p->as) {
122
		case AMOVW:
123
		case AMOVB:
124
		case AMOVBU:
125
			if(p->from.type == D_OREG && p->from.offset == 0)
126
				xtramodes(r, &p->from);
127
			else if(p->to.type == D_OREG && p->to.offset == 0)
128
				xtramodes(r, &p->to);
129
			else
130
				continue;
131
			break;
132
		case ACMP:
133
			/*
134
			 * elide CMP $0,x if calculation of x can set condition codes
135
			 */
136
			if(p->from.type != D_CONST || p->from.offset != 0)
137
				continue;
138
			r2 = r->s1;
139
			if(r2 == R)
140
				continue;
141
			t = r2->prog->as;
142
			switch(t) {
143
			default:
144
				continue;
145
			case ABEQ:
146
			case ABNE:
147
			case ABMI:
148
			case ABPL:
149
				break;
150
			case ABGE:
151
				t = ABPL;
152
				break;
153
			case ABLT:
154
				t = ABMI;
155
				break;
156
			case ABHI:
157
				t = ABNE;
158
				break;
159
			case ABLS:
160
				t = ABEQ;
161
				break;
162
			}
163
			r1 = r;
164
			do
165
				r1 = uniqp(r1);
166
			while (r1 != R && r1->prog->as == ANOP);
167
			if(r1 == R)
168
				continue;
169
			p1 = r1->prog;
170
			if(p1->to.type != D_REG)
171
				continue;
172
			if(p1->to.reg != p->reg)
173
			if(!(p1->as == AMOVW && p1->from.type == D_REG && p1->from.reg == p->reg))
174
				continue;
175
			switch(p1->as) {
176
			default:
177
				continue;
178
			case AMOVW:
179
				if(p1->from.type != D_REG)
180
					continue;
181
			case AAND:
182
			case AEOR:
183
			case AORR:
184
			case ABIC:
185
			case AMVN:
186
			case ASUB:
187
			case ARSB:
188
			case AADD:
189
			case AADC:
190
			case ASBC:
191
			case ARSC:
192
				break;
193
			}
194
			p1->scond |= C_SBIT;
195
			r2->prog->as = t;
196
			excise(r);
197
			continue;
198
		}
199
	}
200
 
201
	predicate();
202
}
203
 
204
void
205
excise(Reg *r)
206
{
207
	Prog *p;
208
 
209
	p = r->prog;
210
	p->as = ANOP;
211
	p->scond = zprog.scond;
212
	p->from = zprog.from;
213
	p->to = zprog.to;
214
	p->reg = zprog.reg; /**/
215
}
216
 
217
Reg*
218
uniqp(Reg *r)
219
{
220
	Reg *r1;
221
 
222
	r1 = r->p1;
223
	if(r1 == R) {
224
		r1 = r->p2;
225
		if(r1 == R || r1->p2link != R)
226
			return R;
227
	} else
228
		if(r->p2 != R)
229
			return R;
230
	return r1;
231
}
232
 
233
Reg*
234
uniqs(Reg *r)
235
{
236
	Reg *r1;
237
 
238
	r1 = r->s1;
239
	if(r1 == R) {
240
		r1 = r->s2;
241
		if(r1 == R)
242
			return R;
243
	} else
244
		if(r->s2 != R)
245
			return R;
246
	return r1;
247
}
248
 
249
int
250
regtyp(Adr *a)
251
{
252
 
253
	if(a->type == D_REG)
254
		return 1;
255
	if(a->type == D_FREG)
256
		return 1;
257
	return 0;
258
}
259
 
260
/*
261
 * the idea is to substitute
262
 * one register for another
263
 * from one MOV to another
264
 *	MOV	a, R0
265
 *	ADD	b, R0	/ no use of R1
266
 *	MOV	R0, R1
267
 * would be converted to
268
 *	MOV	a, R1
269
 *	ADD	b, R1
270
 *	MOV	R1, R0
271
 * hopefully, then the former or latter MOV
272
 * will be eliminated by copy propagation.
273
 */
274
int
275
subprop(Reg *r0)
276
{
277
	Prog *p;
278
	Adr *v1, *v2;
279
	Reg *r;
280
	int t;
281
 
282
	p = r0->prog;
283
	v1 = &p->from;
284
	if(!regtyp(v1))
285
		return 0;
286
	v2 = &p->to;
287
	if(!regtyp(v2))
288
		return 0;
289
	for(r=uniqp(r0); r!=R; r=uniqp(r)) {
290
		if(uniqs(r) == R)
291
			break;
292
		p = r->prog;
293
		switch(p->as) {
294
		case ABL:
295
			return 0;
296
 
297
		case ACMP:
298
		case ACMN:
299
		case AADD:
300
		case ASUB:
301
		case ARSB:
302
		case ASLL:
303
		case ASRL:
304
		case ASRA:
305
		case AORR:
306
		case AAND:
307
		case AEOR:
308
		case AMUL:
309
		case ADIV:
310
		case ADIVU:
311
 
312
		case ACMPF:
313
		case ACMPD:
314
		case AADDD:
315
		case AADDF:
316
		case ASUBD:
317
		case ASUBF:
318
		case AMULD:
319
		case AMULF:
320
		case ADIVD:
321
		case ADIVF:
322
			if(p->to.type == v1->type)
323
			if(p->to.reg == v1->reg) {
324
				if(p->reg == NREG)
325
					p->reg = p->to.reg;
326
				goto gotit;
327
			}
328
			break;
329
 
330
		case AMOVF:
331
		case AMOVD:
332
		case AMOVW:
333
			if(p->to.type == v1->type)
334
			if(p->to.reg == v1->reg)
335
				goto gotit;
336
			break;
337
 
338
		case AMOVM:
339
			t = 1<<v2->reg;
340
			if((p->from.type == D_CONST && (p->from.offset&t)) ||
341
			   (p->to.type == D_CONST && (p->to.offset&t)))
342
				return 0;
343
			break;
344
		}
345
		if(copyau(&p->from, v2) ||
346
		   copyau1(p, v2) ||
347
		   copyau(&p->to, v2))
348
			break;
349
		if(copysub(&p->from, v1, v2, 0) ||
350
		   copysub1(p, v1, v2, 0) ||
351
		   copysub(&p->to, v1, v2, 0))
352
			break;
353
	}
354
	return 0;
355
 
356
gotit:
357
	copysub(&p->to, v1, v2, 1);
358
	if(debug['P']) {
359
		print("gotit: %D->%D\n%P", v1, v2, r->prog);
360
		if(p->from.type == v2->type)
361
			print(" excise");
362
		print("\n");
363
	}
364
	for(r=uniqs(r); r!=r0; r=uniqs(r)) {
365
		p = r->prog;
366
		copysub(&p->from, v1, v2, 1);
367
		copysub1(p, v1, v2, 1);
368
		copysub(&p->to, v1, v2, 1);
369
		if(debug['P'])
370
			print("%P\n", r->prog);
371
	}
372
	t = v1->reg;
373
	v1->reg = v2->reg;
374
	v2->reg = t;
375
	if(debug['P'])
376
		print("%P last\n", r->prog);
377
	return 1;
378
}
379
 
380
/*
381
 * The idea is to remove redundant copies.
382
 *	v1->v2	F=0
383
 *	(use v2	s/v2/v1/)*
384
 *	set v1	F=1
385
 *	use v2	return fail
386
 *	-----------------
387
 *	v1->v2	F=0
388
 *	(use v2	s/v2/v1/)*
389
 *	set v1	F=1
390
 *	set v2	return success
391
 */
392
int
393
copyprop(Reg *r0)
394
{
395
	Prog *p;
396
	Adr *v1, *v2;
397
	Reg *r;
398
 
399
	p = r0->prog;
400
	v1 = &p->from;
401
	v2 = &p->to;
402
	if(copyas(v1, v2))
403
		return 1;
404
	for(r=firstr; r!=R; r=r->link)
405
		r->active = 0;
406
	return copy1(v1, v2, r0->s1, 0);
407
}
408
 
409
int
410
copy1(Adr *v1, Adr *v2, Reg *r, int f)
411
{
412
	int t;
413
	Prog *p;
414
 
415
	if(r->active) {
416
		if(debug['P'])
417
			print("act set; return 1\n");
418
		return 1;
419
	}
420
	r->active = 1;
421
	if(debug['P'])
422
		print("copy %D->%D f=%d\n", v1, v2, f);
423
	for(; r != R; r = r->s1) {
424
		p = r->prog;
425
		if(debug['P'])
426
			print("%P", p);
427
		if(!f && uniqp(r) == R) {
428
			f = 1;
429
			if(debug['P'])
430
				print("; merge; f=%d", f);
431
		}
432
		t = copyu(p, v2, A);
433
		switch(t) {
434
		case 2:	/* rar, cant split */
435
			if(debug['P'])
436
				print("; %Drar; return 0\n", v2);
437
			return 0;
438
 
439
		case 3:	/* set */
440
			if(debug['P'])
441
				print("; %Dset; return 1\n", v2);
442
			return 1;
443
 
444
		case 1:	/* used, substitute */
445
		case 4:	/* use and set */
446
			if(f) {
447
				if(!debug['P'])
448
					return 0;
449
				if(t == 4)
450
					print("; %Dused+set and f=%d; return 0\n", v2, f);
451
				else
452
					print("; %Dused and f=%d; return 0\n", v2, f);
453
				return 0;
454
			}
455
			if(copyu(p, v2, v1)) {
456
				if(debug['P'])
457
					print("; sub fail; return 0\n");
458
				return 0;
459
			}
460
			if(debug['P'])
461
				print("; sub%D/%D", v2, v1);
462
			if(t == 4) {
463
				if(debug['P'])
464
					print("; %Dused+set; return 1\n", v2);
465
				return 1;
466
			}
467
			break;
468
		}
469
		if(!f) {
470
			t = copyu(p, v1, A);
471
			if(!f && (t == 2 || t == 3 || t == 4)) {
472
				f = 1;
473
				if(debug['P'])
474
					print("; %Dset and !f; f=%d", v1, f);
475
			}
476
		}
477
		if(debug['P'])
478
			print("\n");
479
		if(r->s2)
480
			if(!copy1(v1, v2, r->s2, f))
481
				return 0;
482
	}
483
	return 1;
484
}
485
 
486
/*
487
 * The idea is to remove redundant constants.
488
 *	$c1->v1
489
 *	($c1->v2 s/$c1/v1)*
490
 *	set v1  return
491
 * The v1->v2 should be eliminated by copy propagation.
492
 */
493
void
494
constprop(Adr *c1, Adr *v1, Reg *r)
495
{
496
	Prog *p;
497
 
498
	if(debug['C'])
499
		print("constprop %D->%D\n", c1, v1);
500
	for(; r != R; r = r->s1) {
501
		p = r->prog;
502
		if(debug['C'])
503
			print("%P", p);
504
		if(uniqp(r) == R) {
505
			if(debug['C'])
506
				print("; merge; return\n");
507
			return;
508
		}
509
		if(p->as == AMOVW && copyas(&p->from, c1)) {
510
				if(debug['C'])
511
					print("; sub%D/%D", &p->from, v1);
512
				p->from = *v1;
513
		} else if(copyu(p, v1, A) > 1) {
514
			if(debug['C'])
515
				print("; %Dset; return\n", v1);
516
			return;
517
		}
518
		if(debug['C'])
519
			print("\n");
520
		if(r->s2)
521
			constprop(c1, v1, r->s2);
522
	}
523
}
524
 
525
/*
526
 * ASLL x,y,w
527
 * .. (not use w, not set x y w)
528
 * AXXX w,a,b (a != w)
529
 * .. (not use w)
530
 * (set w)
531
 * ----------- changed to
532
 * ..
533
 * AXXX (x<<y),a,b
534
 * ..
535
 */
536
#define FAIL(msg) { if(debug['H']) print("\t%s; FAILURE\n", msg); return 0; }
537
int
538
shiftprop(Reg *r)
539
{
540
	Reg *r1;
541
	Prog *p, *p1, *p2;
542
	int n, o;
543
	Adr a;
544
 
545
	p = r->prog;
546
	if(p->to.type != D_REG)
547
		FAIL("BOTCH: result not reg");
548
	n = p->to.reg;
549
	a = zprog.from;
550
	if(p->reg != NREG && p->reg != p->to.reg) {
551
		a.type = D_REG;
552
		a.reg = p->reg;
553
	}
554
	if(debug['H'])
555
		print("shiftprop\n%P", p);
556
	r1 = r;
557
	for(;;) {
558
		/* find first use of shift result; abort if shift operands or result are changed */
559
		r1 = uniqs(r1);
560
		if(r1 == R)
561
			FAIL("branch");
562
		if(uniqp(r1) == R)
563
			FAIL("merge");
564
		p1 = r1->prog;
565
		if(debug['H'])
566
			print("\n%P", p1);
567
		switch(copyu(p1, &p->to, A)) {
568
		case 0:	/* not used or set */
569
			if((p->from.type == D_REG && copyu(p1, &p->from, A) > 1) ||
570
			   (a.type == D_REG && copyu(p1, &a, A) > 1))
571
				FAIL("args modified");
572
			continue;
573
		case 3:	/* set, not used */
574
			FAIL("BOTCH: noref");
575
		}
576
		break;
577
	}
578
	/* check whether substitution can be done */
579
	switch(p1->as) {
580
	default:
581
		FAIL("non-dpi");
582
	case AAND:
583
	case AEOR:
584
	case AADD:
585
	case AADC:
586
	case AORR:
587
	case ASUB:
588
	case ARSB:
589
	case ASBC:
590
	case ARSC:
591
		if(p1->reg == n || (p1->reg == NREG && p1->to.type == D_REG && p1->to.reg == n)) {
592
			if(p1->from.type != D_REG)
593
				FAIL("can't swap");
594
			p1->reg = p1->from.reg;
595
			p1->from.reg = n;
596
			switch(p1->as) {
597
			case ASUB:
598
				p1->as = ARSB;
599
				break;
600
			case ARSB:
601
				p1->as = ASUB;
602
				break;
603
			case ASBC:
604
				p1->as = ARSC;
605
				break;
606
			case ARSC:
607
				p1->as = ASBC;
608
				break;
609
			}
610
			if(debug['H'])
611
				print("\t=>%P", p1);
612
		}
613
	case ABIC:
614
	case ACMP:
615
	case ACMN:
616
		if(p1->reg == n)
617
			FAIL("can't swap");
618
		if(p1->reg == NREG && p1->to.reg == n)
619
			FAIL("shift result used twice");
620
	case AMVN:
621
		if(p1->from.type == D_SHIFT)
622
			FAIL("shift result used in shift");
623
		if(p1->from.type != D_REG || p1->from.reg != n)
624
			FAIL("BOTCH: where is it used?");
625
		break;
626
	}
627
	/* check whether shift result is used subsequently */
628
	p2 = p1;
629
	if(p1->to.reg != n)
630
	for (;;) {
631
		r1 = uniqs(r1);
632
		if(r1 == R)
633
			FAIL("inconclusive");
634
		p1 = r1->prog;
635
		if(debug['H'])
636
			print("\n%P", p1);
637
		switch(copyu(p1, &p->to, A)) {
638
		case 0:	/* not used or set */
639
			continue;
640
		case 3: /* set, not used */
641
			break;
642
		default:/* used */
643
			FAIL("reused");
644
		}
645
		break;
646
	}
647
	/* make the substitution */
648
	p2->from.type = D_SHIFT;
649
	p2->from.reg = NREG;
650
	o = p->reg;
651
	if(o == NREG)
652
		o = p->to.reg;
653
	switch(p->from.type){
654
	case D_CONST:
655
		o |= (p->from.offset&0x1f)<<7;
656
		break;
657
	case D_REG:
658
		o |= (1<<4) | (p->from.reg<<8);
659
		break;
660
	}
661
	switch(p->as){
662
	case ASLL:
663
		o |= 0<<5;
664
		break;
665
	case ASRL:
666
		o |= 1<<5;
667
		break;
668
	case ASRA:
669
		o |= 2<<5;
670
		break;
671
	}
672
	p2->from.offset = o;
673
	if(debug['H'])
674
		print("\t=>%P\tSUCCEED\n", p2);
675
	return 1;
676
}
677
 
678
Reg*
679
findpre(Reg *r, Adr *v)
680
{
681
	Reg *r1;
682
 
683
	for(r1=uniqp(r); r1!=R; r=r1,r1=uniqp(r)) {
684
		if(uniqs(r1) != r)
685
			return R;
686
		switch(copyu(r1->prog, v, A)) {
687
		case 1: /* used */
688
		case 2: /* read-alter-rewrite */
689
			return R;
690
		case 3: /* set */
691
		case 4: /* set and used */
692
			return r1;
693
		}
694
	}
695
	return R;
696
}
697
 
698
Reg*
699
findinc(Reg *r, Reg *r2, Adr *v)
700
{
701
	Reg *r1;
702
	Prog *p;
703
 
704
 
705
	for(r1=uniqs(r); r1!=R && r1!=r2; r=r1,r1=uniqs(r)) {
706
		if(uniqp(r1) != r)
707
			return R;
708
		switch(copyu(r1->prog, v, A)) {
709
		case 0: /* not touched */
710
			continue;
711
		case 4: /* set and used */
712
			p = r1->prog;
713
			if(p->as == AADD)
714
			if(p->from.type == D_CONST)
715
			if(p->from.offset > -4096 && p->from.offset < 4096)
716
				return r1;
717
		default:
718
			return R;
719
		}
720
	}
721
	return R;
722
}
723
 
724
int
725
nochange(Reg *r, Reg *r2, Prog *p)
726
{
727
	Adr a[3];
728
	int i, n;
729
 
730
	if(r == r2)
731
		return 1;
732
	n = 0;
733
	if(p->reg != NREG && p->reg != p->to.reg) {
734
		a[n].type = D_REG;
735
		a[n++].reg = p->reg;
736
	}
737
	switch(p->from.type) {
738
	case D_SHIFT:
739
		a[n].type = D_REG;
740
		a[n++].reg = p->from.offset&0xf;
741
	case D_REG:
742
		a[n].type = D_REG;
743
		a[n++].reg = p->from.reg;
744
	}
745
	if(n == 0)
746
		return 1;
747
	for(; r!=R && r!=r2; r=uniqs(r)) {
748
		p = r->prog;
749
		for(i=0; i<n; i++)
750
			if(copyu(p, &a[i], A) > 1)
751
				return 0;
752
	}
753
	return 1;
754
}
755
 
756
int
757
findu1(Reg *r, Adr *v)
758
{
759
	for(; r != R; r = r->s1) {
760
		if(r->active)
761
			return 0;
762
		r->active = 1;
763
		switch(copyu(r->prog, v, A)) {
764
		case 1: /* used */
765
		case 2: /* read-alter-rewrite */
766
		case 4: /* set and used */
767
			return 1;
768
		case 3: /* set */
769
			return 0;
770
		}
771
		if(r->s2)
772
			if (findu1(r->s2, v))
773
				return 1;
774
	}
775
	return 0;
776
}
777
 
778
int
779
finduse(Reg *r, Adr *v)
780
{
781
	Reg *r1;
782
 
783
	for(r1=firstr; r1!=R; r1=r1->link)
784
		r1->active = 0;
785
	return findu1(r, v);
786
}
787
 
788
int
789
xtramodes(Reg *r, Adr *a)
790
{
791
	Reg *r1, *r2, *r3;
792
	Prog *p, *p1;
793
	Adr v;
794
 
795
	p = r->prog;
796
	if(debug['h'] && p->as == AMOVB && p->from.type == D_OREG)	/* byte load */
797
		return 0;
798
	v = *a;
799
	v.type = D_REG;
800
	r1 = findpre(r, &v);
801
	if(r1 != R) {
802
		p1 = r1->prog;
803
		if(p1->to.type == D_REG && p1->to.reg == v.reg)
804
		switch(p1->as) {
805
		case AADD:
806
			if(p1->from.type == D_REG ||
807
			   (p1->from.type == D_SHIFT && (p1->from.offset&(1<<4)) == 0 &&
808
			    (p->as != AMOVB || (a == &p->from && (p1->from.offset&~0xf) == 0))) ||
809
			   (p1->from.type == D_CONST && 
810
			    p1->from.offset > -4096 && p1->from.offset < 4096))
811
			if(nochange(uniqs(r1), r, p1)) {
812
				if(a != &p->from || v.reg != p->to.reg)
813
				if (finduse(r->s1, &v)) {
814
					if(p1->reg == NREG || p1->reg == v.reg)
815
						/* pre-indexing */
816
						p->scond |= C_WBIT;
817
					else return 0;	
818
				}
819
				switch (p1->from.type) {
820
				case D_REG:
821
					/* register offset */
822
					a->type = D_SHIFT;
823
					a->offset = p1->from.reg;
824
					break;
825
				case D_SHIFT:
826
					/* scaled register offset */
827
					a->type = D_SHIFT;
828
				case D_CONST:
829
					/* immediate offset */
830
					a->offset = p1->from.offset;
831
					break;
832
				}
833
				if(p1->reg != NREG)
834
					a->reg = p1->reg;
835
				excise(r1);
836
				return 1;
837
			}
838
			break;
839
		case AMOVW:
840
			if(p1->from.type == D_REG)
841
			if((r2 = findinc(r1, r, &p1->from)) != R) {
842
			for(r3=uniqs(r2); r3->prog->as==ANOP; r3=uniqs(r3))
843
				;
844
			if(r3 == r) {
845
				/* post-indexing */
846
				p1 = r2->prog;
847
				a->reg = p1->to.reg;
848
				a->offset = p1->from.offset;
849
				p->scond |= C_PBIT;
850
				if(!finduse(r, &r1->prog->to))
851
					excise(r1);
852
				excise(r2);
853
				return 1;
854
			}
855
			}
856
			break;
857
		}
858
	}
859
	if(a != &p->from || a->reg != p->to.reg)
860
	if((r1 = findinc(r, R, &v)) != R) {
861
		/* post-indexing */
862
		p1 = r1->prog;
863
		a->offset = p1->from.offset;
864
		p->scond |= C_PBIT;
865
		excise(r1);
866
		return 1;
867
	}
868
	return 0;
869
}
870
 
871
/*
872
 * return
873
 * 1 if v only used (and substitute),
874
 * 2 if read-alter-rewrite
875
 * 3 if set
876
 * 4 if set and used
877
 * 0 otherwise (not touched)
878
 */
879
int
880
copyu(Prog *p, Adr *v, Adr *s)
881
{
882
 
883
	switch(p->as) {
884
 
885
	default:
886
		if(debug['P'])
887
			print(" (???)");
888
		return 2;
889
 
890
	case AMOVM:
891
		if(v->type != D_REG)
892
			return 0;
893
		if(p->from.type == D_CONST) {	/* read reglist, read/rar */
894
			if(s != A) {
895
				if(p->from.offset&(1<<v->reg))
896
					return 1;
897
				if(copysub(&p->to, v, s, 1))
898
					return 1;
899
				return 0;
900
			}
901
			if(copyau(&p->to, v)) {
902
				if(p->scond&C_WBIT)
903
					return 2;
904
				return 1;
905
			}
906
			if(p->from.offset&(1<<v->reg))
907
				return 1;
908
		} else {			/* read/rar, write reglist */
909
			if(s != A) {
910
				if(p->to.offset&(1<<v->reg))
911
					return 1;
912
				if(copysub(&p->from, v, s, 1))
913
					return 1;
914
				return 0;
915
			}
916
			if(copyau(&p->from, v)) {
917
				if(p->scond&C_WBIT)
918
					return 2;
919
				if(p->to.offset&(1<<v->reg))
920
					return 4;
921
				return 1;
922
			}
923
			if(p->to.offset&(1<<v->reg))
924
				return 3;
925
		}
926
		return 0;
927
 
928
	case ANOP:	/* read, write */
929
	case AMOVW:
930
	case AMOVF:
931
	case AMOVD:
932
	case AMOVH:
933
	case AMOVHU:
934
	case AMOVB:
935
	case AMOVBU:
936
	case AMOVDW:
937
	case AMOVWD:
938
	case AMOVFD:
939
	case AMOVDF:
940
		if(p->scond&(C_WBIT|C_PBIT))
941
		if(v->type == D_REG) {
942
			if(p->from.type == D_OREG || p->from.type == D_SHIFT) {
943
				if(p->from.reg == v->reg)
944
					return 2;
945
			} else {
946
		  		if(p->to.reg == v->reg)
947
				return 2;
948
			}
949
		}
950
		if(s != A) {
951
			if(copysub(&p->from, v, s, 1))
952
				return 1;
953
			if(!copyas(&p->to, v))
954
				if(copysub(&p->to, v, s, 1))
955
					return 1;
956
			return 0;
957
		}
958
		if(copyas(&p->to, v)) {
959
			if(copyau(&p->from, v))
960
				return 4;
961
			return 3;
962
		}
963
		if(copyau(&p->from, v))
964
			return 1;
965
		if(copyau(&p->to, v))
966
			return 1;
967
		return 0;
968
 
969
 
970
	case AADD:	/* read, read, write */
971
	case ASUB:
972
	case ARSB:
973
	case ASLL:
974
	case ASRL:
975
	case ASRA:
976
	case AORR:
977
	case AAND:
978
	case AEOR:
979
	case AMUL:
980
	case ADIV:
981
	case ADIVU:
982
	case AADDF:
983
	case AADDD:
984
	case ASUBF:
985
	case ASUBD:
986
	case AMULF:
987
	case AMULD:
988
	case ADIVF:
989
	case ADIVD:
990
 
991
	case ACMPF:
992
	case ACMPD:
993
	case ACMP:
994
	case ACMN:
995
	case ACASE:
996
		if(s != A) {
997
			if(copysub(&p->from, v, s, 1))
998
				return 1;
999
			if(copysub1(p, v, s, 1))
1000
				return 1;
1001
			if(!copyas(&p->to, v))
1002
				if(copysub(&p->to, v, s, 1))
1003
					return 1;
1004
			return 0;
1005
		}
1006
		if(copyas(&p->to, v)) {
1007
			if(p->reg == NREG)
1008
				p->reg = p->to.reg;
1009
			if(copyau(&p->from, v))
1010
				return 4;
1011
			if(copyau1(p, v))
1012
				return 4;
1013
			return 3;
1014
		}
1015
		if(copyau(&p->from, v))
1016
			return 1;
1017
		if(copyau1(p, v))
1018
			return 1;
1019
		if(copyau(&p->to, v))
1020
			return 1;
1021
		return 0;
1022
 
1023
	case ABEQ:	/* read, read */
1024
	case ABNE:
1025
	case ABCS:
1026
	case ABHS:
1027
	case ABCC:
1028
	case ABLO:
1029
	case ABMI:
1030
	case ABPL:
1031
	case ABVS:
1032
	case ABVC:
1033
	case ABHI:
1034
	case ABLS:
1035
	case ABGE:
1036
	case ABLT:
1037
	case ABGT:
1038
	case ABLE:
1039
		if(s != A) {
1040
			if(copysub(&p->from, v, s, 1))
1041
				return 1;
1042
			return copysub1(p, v, s, 1);
1043
		}
1044
		if(copyau(&p->from, v))
1045
			return 1;
1046
		if(copyau1(p, v))
1047
			return 1;
1048
		return 0;
1049
 
1050
	case AB:	/* funny */
1051
		if(s != A) {
1052
			if(copysub(&p->to, v, s, 1))
1053
				return 1;
1054
			return 0;
1055
		}
1056
		if(copyau(&p->to, v))
1057
			return 1;
1058
		return 0;
1059
 
1060
	case ARET:	/* funny */
1061
		if(v->type == D_REG)
1062
		if(v->reg == REGRET)
1063
			return 2;
1064
		if(v->type == D_FREG)
1065
		if(v->reg == FREGRET)
1066
			return 2;
1067
 
1068
	case ABL:	/* funny */
1069
		if(v->type == D_REG) {
1070
			if(v->reg <= REGEXT && v->reg > exregoffset)
1071
				return 2;
1072
			if(v->reg == (uchar)REGARG)
1073
				return 2;
1074
		}
1075
		if(v->type == D_FREG)
1076
			if(v->reg <= FREGEXT && v->reg > exfregoffset)
1077
				return 2;
1078
 
1079
		if(s != A) {
1080
			if(copysub(&p->to, v, s, 1))
1081
				return 1;
1082
			return 0;
1083
		}
1084
		if(copyau(&p->to, v))
1085
			return 4;
1086
		return 3;
1087
 
1088
	case ATEXT:	/* funny */
1089
		if(v->type == D_REG)
1090
			if(v->reg == (uchar)REGARG)
1091
				return 3;
1092
		return 0;
1093
	}
1094
}
1095
 
1096
int
1097
a2type(Prog *p)
1098
{
1099
 
1100
	switch(p->as) {
1101
 
1102
	case ACMP:
1103
	case ACMN:
1104
 
1105
	case AADD:
1106
	case ASUB:
1107
	case ARSB:
1108
	case ASLL:
1109
	case ASRL:
1110
	case ASRA:
1111
	case AORR:
1112
	case AAND:
1113
	case AEOR:
1114
	case AMUL:
1115
	case ADIV:
1116
	case ADIVU:
1117
		return D_REG;
1118
 
1119
	case ACMPF:
1120
	case ACMPD:
1121
 
1122
	case AADDF:
1123
	case AADDD:
1124
	case ASUBF:
1125
	case ASUBD:
1126
	case AMULF:
1127
	case AMULD:
1128
	case ADIVF:
1129
	case ADIVD:
1130
		return D_FREG;
1131
	}
1132
	return D_NONE;
1133
}
1134
 
1135
/*
1136
 * direct reference,
1137
 * could be set/use depending on
1138
 * semantics
1139
 */
1140
int
1141
copyas(Adr *a, Adr *v)
1142
{
1143
 
1144
	if(regtyp(v)) {
1145
		if(a->type == v->type)
1146
		if(a->reg == v->reg)
1147
			return 1;
1148
	} else if(v->type == D_CONST) {		/* for constprop */
1149
		if(a->type == v->type)
1150
		if(a->name == v->name)
1151
		if(a->sym == v->sym)
1152
		if(a->reg == v->reg)
1153
		if(a->offset == v->offset)
1154
			return 1;
1155
	}
1156
	return 0;
1157
}
1158
 
1159
/*
1160
 * either direct or indirect
1161
 */
1162
int
1163
copyau(Adr *a, Adr *v)
1164
{
1165
 
1166
	if(copyas(a, v))
1167
		return 1;
1168
	if(v->type == D_REG) {
1169
		if(a->type == D_OREG) {
1170
			if(v->reg == a->reg)
1171
				return 1;
1172
		} else if(a->type == D_SHIFT) {
1173
			if((a->offset&0xf) == v->reg)
1174
				return 1;
1175
			if((a->offset&(1<<4)) && (a->offset>>8) == v->reg)
1176
				return 1;
1177
		}
1178
	}
1179
	return 0;
1180
}
1181
 
1182
int
1183
copyau1(Prog *p, Adr *v)
1184
{
1185
 
1186
	if(regtyp(v)) {
1187
		if(a2type(p) == v->type)
1188
		if(p->reg == v->reg) {
1189
			if(a2type(p) != v->type)
1190
				print("botch a2type %P\n", p);
1191
			return 1;
1192
		}
1193
	}
1194
	return 0;
1195
}
1196
 
1197
/*
1198
 * substitute s for v in a
1199
 * return failure to substitute
1200
 */
1201
int
1202
copysub(Adr *a, Adr *v, Adr *s, int f)
1203
{
1204
 
1205
	if(f)
1206
	if(copyau(a, v)) {
1207
		if(a->type == D_SHIFT) {
1208
			if((a->offset&0xf) == v->reg)
1209
				a->offset = (a->offset&~0xf)|s->reg;
1210
			if((a->offset&(1<<4)) && (a->offset>>8) == v->reg)
1211
				a->offset = (a->offset&~(0xf<<8))|(s->reg<<8);
1212
		} else
1213
			a->reg = s->reg;
1214
	}
1215
	return 0;
1216
}
1217
 
1218
int
1219
copysub1(Prog *p1, Adr *v, Adr *s, int f)
1220
{
1221
 
1222
	if(f)
1223
	if(copyau1(p1, v))
1224
		p1->reg = s->reg;
1225
	return 0;
1226
}
1227
 
1228
struct {
1229
	int opcode;
1230
	int notopcode;
1231
	int scond; 
1232
	int notscond; 
1233
} predinfo[]  = { 
1234
	{ ABEQ,	ABNE,	0x0,	0x1, }, 
1235
	{ ABNE,	ABEQ,	0x1,	0x0, }, 
1236
	{ ABCS,	ABCC,	0x2,	0x3, }, 
1237
	{ ABHS,	ABLO,	0x2,	0x3, }, 
1238
	{ ABCC,	ABCS,	0x3,	0x2, }, 
1239
	{ ABLO,	ABHS,	0x3,	0x2, }, 
1240
	{ ABMI,	ABPL,	0x4,	0x5, }, 
1241
	{ ABPL,	ABMI,	0x5,	0x4, }, 
1242
	{ ABVS,	ABVC,	0x6,	0x7, }, 
1243
	{ ABVC,	ABVS,	0x7,	0x6, }, 
1244
	{ ABHI,	ABLS,	0x8,	0x9, }, 
1245
	{ ABLS,	ABHI,	0x9,	0x8, }, 
1246
	{ ABGE,	ABLT,	0xA,	0xB, }, 
1247
	{ ABLT,	ABGE,	0xB,	0xA, }, 
1248
	{ ABGT,	ABLE,	0xC,	0xD, }, 
1249
	{ ABLE,	ABGT,	0xD,	0xC, }, 
1250
}; 
1251
 
1252
typedef struct {
1253
	Reg *start;
1254
	Reg *last;
1255
	Reg *end;
1256
	int len;
1257
} Joininfo;
1258
 
1259
enum {
1260
	Join,
1261
	Split,
1262
	End,
1263
	Branch,
1264
	Setcond,
1265
	Toolong
1266
};
1267
 
1268
enum {
1269
	Falsecond,
1270
	Truecond,
1271
	Delbranch,
1272
	Keepbranch
1273
};
1274
 
1275
int 
1276
isbranch(Prog *p)
1277
{
1278
	return (ABEQ <= p->as) && (p->as <= ABLE); 
1279
}
1280
 
1281
int
1282
predicable(Prog *p)
1283
{
1284
	if (isbranch(p)
1285
		|| p->as == ANOP
1286
		|| p->as == AXXX
1287
		|| p->as == ADATA
1288
		|| p->as == AGLOBL
1289
		|| p->as == AGOK
1290
		|| p->as == AHISTORY
1291
		|| p->as == ANAME
1292
		|| p->as == ASIGNAME
1293
		|| p->as == ATEXT
1294
		|| p->as == AWORD
1295
		|| p->as == ADYNT
1296
		|| p->as == AINIT
1297
		|| p->as == ABCASE
1298
		|| p->as == ACASE)
1299
		return 0; 
1300
	return 1; 
1301
}
1302
 
1303
/* 
1304
 * Depends on an analysis of the encodings performed by 5l. 
1305
 * These seem to be all of the opcodes that lead to the "S" bit
1306
 * being set in the instruction encodings. 
1307
 * 
1308
 * C_SBIT may also have been set explicitly in p->scond.
1309
 */ 
1310
int
1311
modifiescpsr(Prog *p)
1312
{
1313
	return (p->scond&C_SBIT)
1314
		|| p->as == ATST 
1315
		|| p->as == ATEQ 
1316
		|| p->as == ACMN
1317
		|| p->as == ACMP
1318
		|| p->as == AMULU
1319
		|| p->as == ADIVU
1320
		|| p->as == AMUL
1321
		|| p->as == ADIV
1322
		|| p->as == AMOD
1323
		|| p->as == AMODU
1324
		|| p->as == ABL;
1325
} 
1326
 
1327
/*
1328
 * Find the maximal chain of instructions starting with r which could
1329
 * be executed conditionally
1330
 */
1331
int
1332
joinsplit(Reg *r, Joininfo *j)
1333
{
1334
	j->start = r;
1335
	j->last = r;
1336
	j->len = 0;
1337
	do {
1338
		if (r->p2 && (r->p1 || r->p2->p2link)) {
1339
			j->end = r;
1340
			return Join;
1341
		}
1342
		if (r->s1 && r->s2) {
1343
			j->end = r;
1344
			return Split;
1345
		}
1346
		j->last = r;
1347
		if (r->prog->as != ANOP)
1348
			j->len++;
1349
		if (!r->s1 && !r->s2) {
1350
			j->end = r->link;
1351
			return End;
1352
		}
1353
		if (r->s2) {
1354
			j->end = r->s2;
1355
			return Branch;
1356
		}
1357
		if (modifiescpsr(r->prog)) {
1358
			j->end = r->s1;
1359
			return Setcond;
1360
		}
1361
		r = r->s1;
1362
	} while (j->len < 4);
1363
	j->end = r;
1364
	return Toolong;
1365
}
1366
 
1367
Reg *
1368
successor(Reg *r)
1369
{
1370
	if (r->s1)
1371
		return r->s1; 
1372
	else
1373
		return r->s2; 
1374
}
1375
 
1376
void
1377
applypred(Reg *rstart, Joininfo *j, int cond, int branch)
1378
{
1379
	int pred; 
1380
	Reg *r; 
1381
 
1382
	if(j->len == 0)
1383
		return;
1384
	if (cond == Truecond)
1385
		pred = predinfo[rstart->prog->as - ABEQ].scond;
1386
	else
1387
		pred = predinfo[rstart->prog->as - ABEQ].notscond; 
1388
 
1389
	for (r = j->start; ; r = successor(r)) {
1390
		if (r->prog->as == AB) {
1391
			if (r != j->last || branch == Delbranch)
1392
				excise(r);
1393
			else {
1394
			  if (cond == Truecond)
1395
				r->prog->as = predinfo[rstart->prog->as - ABEQ].opcode;
1396
			  else
1397
				r->prog->as = predinfo[rstart->prog->as - ABEQ].notopcode;
1398
			}
1399
		}
1400
		else if (predicable(r->prog)) 
1401
			r->prog->scond = (r->prog->scond&~C_SCOND)|pred;
1402
		if (r->s1 != r->link) {
1403
			r->s1 = r->link;
1404
			r->link->p1 = r;
1405
		}
1406
		if (r == j->last)
1407
			break;
1408
	}
1409
}
1410
 
1411
void
1412
predicate(void)
1413
{	
1414
	Reg *r;
1415
	int t1, t2;
1416
	Joininfo j1, j2;
1417
 
1418
	for(r=firstr; r!=R; r=r->link) {
1419
		if (isbranch(r->prog)) {
1420
			t1 = joinsplit(r->s1, &j1);
1421
			t2 = joinsplit(r->s2, &j2);
1422
			if(j1.last->link != j2.start)
1423
				continue;
1424
			if(j1.end == j2.end)
1425
			if((t1 == Branch && (t2 == Join || t2 == Setcond)) ||
1426
			   (t2 == Join && (t1 == Join || t1 == Setcond))) {
1427
				applypred(r, &j1, Falsecond, Delbranch);
1428
				applypred(r, &j2, Truecond, Delbranch);
1429
				excise(r);
1430
				continue;
1431
			}
1432
			if(t1 == End || t1 == Branch) {
1433
				applypred(r, &j1, Falsecond, Keepbranch);
1434
				excise(r);
1435
				continue;
1436
			}
1437
		} 
1438
	} 
1439
}