WebSVN – planix.SVN – Blame – /os/branches/planix-v0/sys/src/cmd/8c/reg.c

Rev	Author	Line No.	Line
2	-	1	`#include "gc.h"`
		2
		3	`Reg*`
		4	`rega(void)`
		5	`{`
		6	`Reg *r;`
		7
		8	`r = freer;`
		9	`if(r == R) {`
		10	`r = alloc(sizeof(*r));`
		11	`} else`
		12	`freer = r->link;`
		13
		14	`*r = zreg;`
		15	`return r;`
		16	`}`
		17
		18	`int`
		19	`rcmp(const void a1, const void a2)`
		20	`{`
		21	`Rgn p1, p2;`
		22	`int c1, c2;`
		23
		24	`p1 = (Rgn*)a1;`
		25	`p2 = (Rgn*)a2;`
		26	`c1 = p2->cost;`
		27	`c2 = p1->cost;`
		28	`if(c1 -= c2)`
		29	`return c1;`
		30	`return p2->varno - p1->varno;`
		31	`}`
		32
		33	`void`
		34	`regopt(Prog *p)`
		35	`{`
		36	`Reg r, r1, *r2;`
		37	`Prog *p1;`
		38	`int i, z;`
		39	`long initpc, val, npc;`
		40	`ulong vreg;`
		41	`Bits bit;`
		42	`struct`
		43	`{`
		44	`long m;`
		45	`long c;`
		46	`Reg* p;`
		47	`} log5[6], *lp;`
		48
		49	`firstr = R;`
		50	`lastr = R;`
		51	`nvar = 0;`
		52	`regbits = RtoB(D_SP) \| RtoB(D_AX);`
		53	`for(z=0; z<BITS; z++) {`
		54	`externs.b[z] = 0;`
		55	`params.b[z] = 0;`
		56	`consts.b[z] = 0;`
		57	`addrs.b[z] = 0;`
		58	`}`
		59
		60	`/*`
		61	`* pass 1`
		62	`* build aux data structure`
		63	`* allocate pcs`
		64	`* find use and set of variables`
		65	`*/`
		66	`val = 5L * 5L * 5L * 5L * 5L;`
		67	`lp = log5;`
		68	`for(i=0; i<5; i++) {`
		69	`lp->m = val;`
		70	`lp->c = 0;`
		71	`lp->p = R;`
		72	`val /= 5L;`
		73	`lp++;`
		74	`}`
		75	`val = 0;`
		76	`for(; p != P; p = p->link) {`
		77	`switch(p->as) {`
		78	`case ADATA:`
		79	`case AGLOBL:`
		80	`case ANAME:`
		81	`case ASIGNAME:`
		82	`continue;`
		83	`}`
		84	`r = rega();`
		85	`if(firstr == R) {`
		86	`firstr = r;`
		87	`lastr = r;`
		88	`} else {`
		89	`lastr->link = r;`
		90	`r->p1 = lastr;`
		91	`lastr->s1 = r;`
		92	`lastr = r;`
		93	`}`
		94	`r->prog = p;`
		95	`r->pc = val;`
		96	`val++;`
		97
		98	`lp = log5;`
		99	`for(i=0; i<5; i++) {`
		100	`lp->c--;`
		101	`if(lp->c <= 0) {`
		102	`lp->c = lp->m;`
		103	`if(lp->p != R)`
		104	`lp->p->log5 = r;`
		105	`lp->p = r;`
		106	`(lp+1)->c = 0;`
		107	`break;`
		108	`}`
		109	`lp++;`
		110	`}`
		111
		112	`r1 = r->p1;`
		113	`if(r1 != R)`
		114	`switch(r1->prog->as) {`
		115	`case ARET:`
		116	`case AJMP:`
		117	`case AIRETL:`
		118	`r->p1 = R;`
		119	`r1->s1 = R;`
		120	`}`
		121
		122	`bit = mkvar(r, &p->from, p->as==AMOVL);`
		123	`if(bany(&bit))`
		124	`switch(p->as) {`
		125	`/*`
		126	`* funny`
		127	`*/`
		128	`case ALEAL:`
		129	`for(z=0; z<BITS; z++)`
		130	`addrs.b[z] \|= bit.b[z];`
		131	`break;`
		132
		133	`/*`
		134	`* left side read`
		135	`*/`
		136	`default:`
		137	`for(z=0; z<BITS; z++)`
		138	`r->use1.b[z] \|= bit.b[z];`
		139	`break;`
		140	`}`
		141
		142	`bit = mkvar(r, &p->to, 0);`
		143	`if(bany(&bit))`
		144	`switch(p->as) {`
		145	`default:`
		146	`diag(Z, "reg: unknown op: %A", p->as);`
		147	`break;`
		148
		149	`/*`
		150	`* right side read`
		151	`*/`
		152	`case ACMPB:`
		153	`case ACMPL:`
		154	`case ACMPW:`
		155	`for(z=0; z<BITS; z++)`
		156	`r->use2.b[z] \|= bit.b[z];`
		157	`break;`
		158
		159	`/*`
		160	`* right side write`
		161	`*/`
		162	`case ANOP:`
		163	`case AMOVL:`
		164	`case AMOVB:`
		165	`case AMOVW:`
		166	`case AMOVBLSX:`
		167	`case AMOVBLZX:`
		168	`case AMOVWLSX:`
		169	`case AMOVWLZX:`
		170	`for(z=0; z<BITS; z++)`
		171	`r->set.b[z] \|= bit.b[z];`
		172	`break;`
		173
		174	`/*`
		175	`* right side read+write`
		176	`*/`
		177	`case AADDB:`
		178	`case AADDL:`
		179	`case AADDW:`
		180	`case AANDB:`
		181	`case AANDL:`
		182	`case AANDW:`
		183	`case ASUBB:`
		184	`case ASUBL:`
		185	`case ASUBW:`
		186	`case AORB:`
		187	`case AORL:`
		188	`case AORW:`
		189	`case AXORB:`
		190	`case AXORL:`
		191	`case AXORW:`
		192	`case ASALB:`
		193	`case ASALL:`
		194	`case ASALW:`
		195	`case ASARB:`
		196	`case ASARL:`
		197	`case ASARW:`
		198	`case AROLB:`
		199	`case AROLL:`
		200	`case AROLW:`
		201	`case ARORB:`
		202	`case ARORL:`
		203	`case ARORW:`
		204	`case ASHLB:`
		205	`case ASHLL:`
		206	`case ASHLW:`
		207	`case ASHRB:`
		208	`case ASHRL:`
		209	`case ASHRW:`
		210	`case AIMULL:`
		211	`case AIMULW:`
		212	`case ANEGL:`
		213	`case ANOTL:`
		214	`case AADCL:`
		215	`case ASBBL:`
		216	`for(z=0; z<BITS; z++) {`
		217	`r->set.b[z] \|= bit.b[z];`
		218	`r->use2.b[z] \|= bit.b[z];`
		219	`}`
		220	`break;`
		221
		222	`/*`
		223	`* funny`
		224	`*/`
		225	`case AFMOVDP:`
		226	`case AFMOVFP:`
		227	`case AFMOVLP:`
		228	`case AFMOVVP:`
		229	`case AFMOVWP:`
		230	`case ACALL:`
		231	`for(z=0; z<BITS; z++)`
		232	`addrs.b[z] \|= bit.b[z];`
		233	`break;`
		234	`}`
		235
		236	`switch(p->as) {`
		237	`case AIMULL:`
		238	`case AIMULW:`
		239	`if(p->to.type != D_NONE)`
		240	`break;`
		241
		242	`case AIDIVB:`
		243	`case AIDIVL:`
		244	`case AIDIVW:`
		245	`case AIMULB:`
		246	`case ADIVB:`
		247	`case ADIVL:`
		248	`case ADIVW:`
		249	`case AMULB:`
		250	`case AMULL:`
		251	`case AMULW:`
		252
		253	`case ACWD:`
		254	`case ACDQ:`
		255	`r->regu \|= RtoB(D_AX) \| RtoB(D_DX);`
		256	`break;`
		257
		258	`case AREP:`
		259	`case AREPN:`
		260	`case ALOOP:`
		261	`case ALOOPEQ:`
		262	`case ALOOPNE:`
		263	`r->regu \|= RtoB(D_CX);`
		264	`break;`
		265
		266	`case AMOVSB:`
		267	`case AMOVSL:`
		268	`case AMOVSW:`
		269	`case ACMPSB:`
		270	`case ACMPSL:`
		271	`case ACMPSW:`
		272	`r->regu \|= RtoB(D_SI) \| RtoB(D_DI);`
		273	`break;`
		274
		275	`case ASTOSB:`
		276	`case ASTOSL:`
		277	`case ASTOSW:`
		278	`case ASCASB:`
		279	`case ASCASL:`
		280	`case ASCASW:`
		281	`r->regu \|= RtoB(D_AX) \| RtoB(D_DI);`
		282	`break;`
		283
		284	`case AINSB:`
		285	`case AINSL:`
		286	`case AINSW:`
		287	`case AOUTSB:`
		288	`case AOUTSL:`
		289	`case AOUTSW:`
		290	`r->regu \|= RtoB(D_DI) \| RtoB(D_DX);`
		291	`break;`
		292
		293	`case AFSTSW:`
		294	`case ASAHF:`
		295	`r->regu \|= RtoB(D_AX);`
		296	`break;`
		297	`}`
		298	`}`
		299	`if(firstr == R)`
		300	`return;`
		301	`initpc = pc - val;`
		302	`npc = val;`
		303
		304	`/*`
		305	`* pass 2`
		306	`* turn branch references to pointers`
		307	`* build back pointers`
		308	`*/`
		309	`for(r = firstr; r != R; r = r->link) {`
		310	`p = r->prog;`
		311	`if(p->to.type == D_BRANCH) {`
		312	`val = p->to.offset - initpc;`
		313	`r1 = firstr;`
		314	`while(r1 != R) {`
		315	`r2 = r1->log5;`
		316	`if(r2 != R && val >= r2->pc) {`
		317	`r1 = r2;`
		318	`continue;`
		319	`}`
		320	`if(r1->pc == val)`
		321	`break;`
		322	`r1 = r1->link;`
		323	`}`
		324	`if(r1 == R) {`
		325	`nearln = p->lineno;`
		326	`diag(Z, "ref not found\n%P", p);`
		327	`continue;`
		328	`}`
		329	`if(r1 == r) {`
		330	`nearln = p->lineno;`
		331	`diag(Z, "ref to self\n%P", p);`
		332	`continue;`
		333	`}`
		334	`r->s2 = r1;`
		335	`r->p2link = r1->p2;`
		336	`r1->p2 = r;`
		337	`}`
		338	`}`
		339	`if(debug['R']) {`
		340	`p = firstr->prog;`
		341	`print("\n%L %D\n", p->lineno, &p->from);`
		342	`}`
		343
		344	`/*`
		345	`* pass 2.5`
		346	`* find looping structure`
		347	`*/`
		348	`for(r = firstr; r != R; r = r->link)`
		349	`r->active = 0;`
		350	`change = 0;`
		351	`loopit(firstr, npc);`
		352	`if(debug['R'] && debug['v']) {`
		353	`print("\nlooping structure:\n");`
		354	`for(r = firstr; r != R; r = r->link) {`
		355	`print("%ld:%P", r->loop, r->prog);`
		356	`for(z=0; z<BITS; z++)`
		357	`bit.b[z] = r->use1.b[z] \|`
		358	`r->use2.b[z] \|`
		359	`r->set.b[z];`
		360	`if(bany(&bit)) {`
		361	`print("\t");`
		362	`if(bany(&r->use1))`
		363	`print(" u1=%B", r->use1);`
		364	`if(bany(&r->use2))`
		365	`print(" u2=%B", r->use2);`
		366	`if(bany(&r->set))`
		367	`print(" st=%B", r->set);`
		368	`}`
		369	`print("\n");`
		370	`}`
		371	`}`
		372
		373	`/*`
		374	`* pass 3`
		375	`* iterate propagating usage`
		376	`* back until flow graph is complete`
		377	`*/`
		378	`loop1:`
		379	`change = 0;`
		380	`for(r = firstr; r != R; r = r->link)`
		381	`r->active = 0;`
		382	`for(r = firstr; r != R; r = r->link)`
		383	`if(r->prog->as == ARET)`
		384	`prop(r, zbits, zbits);`
		385	`loop11:`
		386	`/* pick up unreachable code */`
		387	`i = 0;`
		388	`for(r = firstr; r != R; r = r1) {`
		389	`r1 = r->link;`
		390	`if(r1 && r1->active && !r->active) {`
		391	`prop(r, zbits, zbits);`
		392	`i = 1;`
		393	`}`
		394	`}`
		395	`if(i)`
		396	`goto loop11;`
		397	`if(change)`
		398	`goto loop1;`
		399
		400
		401	`/*`
		402	`* pass 4`
		403	`* iterate propagating register/variable synchrony`
		404	`* forward until graph is complete`
		405	`*/`
		406	`loop2:`
		407	`change = 0;`
		408	`for(r = firstr; r != R; r = r->link)`
		409	`r->active = 0;`
		410	`synch(firstr, zbits);`
		411	`if(change)`
		412	`goto loop2;`
		413
		414
		415	`/*`
		416	`* pass 5`
		417	`* isolate regions`
		418	`* calculate costs (paint1)`
		419	`*/`
		420	`r = firstr;`
		421	`if(r) {`
		422	`for(z=0; z<BITS; z++)`
		423	`bit.b[z] = (r->refahead.b[z] \| r->calahead.b[z]) &`
		424	`~(externs.b[z] \| params.b[z] \| addrs.b[z] \| consts.b[z]);`
		425	`if(bany(&bit)) {`
		426	`nearln = r->prog->lineno;`
		427	`warn(Z, "used and not set: %B", bit);`
		428	`if(debug['R'] && !debug['w'])`
		429	`print("used and not set: %B\n", bit);`
		430	`}`
		431	`}`
		432	`if(debug['R'] && debug['v'])`
		433	`print("\nprop structure:\n");`
		434	`for(r = firstr; r != R; r = r->link)`
		435	`r->act = zbits;`
		436	`rgp = region;`
		437	`nregion = 0;`
		438	`for(r = firstr; r != R; r = r->link) {`
		439	`if(debug['R'] && debug['v']) {`
		440	`print("%P\t", r->prog);`
		441	`if(bany(&r->set))`
		442	`print("s:%B ", r->set);`
		443	`if(bany(&r->refahead))`
		444	`print("ra:%B ", r->refahead);`
		445	`if(bany(&r->calahead))`
		446	`print("ca:%B ", r->calahead);`
		447	`print("\n");`
		448	`}`
		449	`for(z=0; z<BITS; z++)`
		450	`bit.b[z] = r->set.b[z] &`
		451	`~(r->refahead.b[z] \| r->calahead.b[z] \| addrs.b[z]);`
		452	`if(bany(&bit)) {`
		453	`nearln = r->prog->lineno;`
		454	`warn(Z, "set and not used: %B", bit);`
		455	`if(debug['R'])`
		456	`print("set and not used: %B\n", bit);`
		457	`excise(r);`
		458	`}`
		459	`for(z=0; z<BITS; z++)`
		460	`bit.b[z] = LOAD(r) & ~(r->act.b[z] \| addrs.b[z]);`
		461	`while(bany(&bit)) {`
		462	`i = bnum(bit);`
		463	`rgp->enter = r;`
		464	`rgp->varno = i;`
		465	`change = 0;`
		466	`if(debug['R'] && debug['v'])`
		467	`print("\n");`
		468	`paint1(r, i);`
		469	`bit.b[i/32] &= ~(1L<<(i%32));`
		470	`if(change <= 0) {`
		471	`if(debug['R'])`
		472	`print("%L$%d: %B\n",`
		473	`r->prog->lineno, change, blsh(i));`
		474	`continue;`
		475	`}`
		476	`rgp->cost = change;`
		477	`nregion++;`
		478	`if(nregion >= NRGN) {`
		479	`warn(Z, "too many regions");`
		480	`goto brk;`
		481	`}`
		482	`rgp++;`
		483	`}`
		484	`}`
		485	`brk:`
		486	`qsort(region, nregion, sizeof(region[0]), rcmp);`
		487
		488	`/*`
		489	`* pass 6`
		490	`* determine used registers (paint2)`
		491	`* replace code (paint3)`
		492	`*/`
		493	`rgp = region;`
		494	`for(i=0; i<nregion; i++) {`
		495	`bit = blsh(rgp->varno);`
		496	`vreg = paint2(rgp->enter, rgp->varno);`
		497	`vreg = allreg(vreg, rgp);`
		498	`if(debug['R']) {`
		499	`print("%L$%d %R: %B\n",`
		500	`rgp->enter->prog->lineno,`
		501	`rgp->cost,`
		502	`rgp->regno,`
		503	`bit);`
		504	`}`
		505	`if(rgp->regno != 0)`
		506	`paint3(rgp->enter, rgp->varno, vreg, rgp->regno);`
		507	`rgp++;`
		508	`}`
		509	`/*`
		510	`* pass 7`
		511	`* peep-hole on basic block`
		512	`*/`
		513	`if(!debug['R'] \|\| debug['P'])`
		514	`peep();`
		515
		516	`/*`
		517	`* pass 8`
		518	`* recalculate pc`
		519	`*/`
		520	`val = initpc;`
		521	`for(r = firstr; r != R; r = r1) {`
		522	`r->pc = val;`
		523	`p = r->prog;`
		524	`p1 = P;`
		525	`r1 = r->link;`
		526	`if(r1 != R)`
		527	`p1 = r1->prog;`
		528	`for(; p != p1; p = p->link) {`
		529	`switch(p->as) {`
		530	`default:`
		531	`val++;`
		532	`break;`
		533
		534	`case ANOP:`
		535	`case ADATA:`
		536	`case AGLOBL:`
		537	`case ANAME:`
		538	`case ASIGNAME:`
		539	`break;`
		540	`}`
		541	`}`
		542	`}`
		543	`pc = val;`
		544
		545	`/*`
		546	`* fix up branches`
		547	`*/`
		548	`if(debug['R'])`
		549	`if(bany(&addrs))`
		550	`print("addrs: %B\n", addrs);`
		551
		552	`r1 = 0; /* set */`
		553	`for(r = firstr; r != R; r = r->link) {`
		554	`p = r->prog;`
		555	`if(p->to.type == D_BRANCH)`
		556	`p->to.offset = r->s2->pc;`
		557	`r1 = r;`
		558	`}`
		559
		560	`/*`
		561	`* last pass`
		562	`* eliminate nops`
		563	`* free aux structures`
		564	`*/`
		565	`for(p = firstr->prog; p != P; p = p->link){`
		566	`while(p->link && p->link->as == ANOP)`
		567	`p->link = p->link->link;`
		568	`}`
		569	`if(r1 != R) {`
		570	`r1->link = freer;`
		571	`freer = firstr;`
		572	`}`
		573	`}`
		574
		575	`/*`
		576	`* add mov b,rn`
		577	`* just after r`
		578	`*/`
		579	`void`
		580	`addmove(Reg *r, int bn, int rn, int f)`
		581	`{`
		582	`Prog p, p1;`
		583	`Adr *a;`
		584	`Var *v;`
		585
		586	`p1 = alloc(sizeof(*p1));`
		587	`*p1 = zprog;`
		588	`p = r->prog;`
		589
		590	`p1->link = p->link;`
		591	`p->link = p1;`
		592	`p1->lineno = p->lineno;`
		593
		594	`v = var + bn;`
		595
		596	`a = &p1->to;`
		597	`a->sym = v->sym;`
		598	`a->offset = v->offset;`
		599	`a->etype = v->etype;`
		600	`a->type = v->name;`
		601
		602	`p1->as = AMOVL;`
		603	`if(v->etype == TCHAR \|\| v->etype == TUCHAR)`
		604	`p1->as = AMOVB;`
		605	`if(v->etype == TSHORT \|\| v->etype == TUSHORT)`
		606	`p1->as = AMOVW;`
		607
		608	`p1->from.type = rn;`
		609	`if(!f) {`
		610	`p1->from = *a;`
		611	`*a = zprog.from;`
		612	`a->type = rn;`
		613	`if(v->etype == TUCHAR)`
		614	`p1->as = AMOVB;`
		615	`if(v->etype == TUSHORT)`
		616	`p1->as = AMOVW;`
		617	`}`
		618	`if(debug['R'])`
		619	`print("%P\t.a%P\n", p, p1);`
		620	`}`
		621
		622	`ulong`
		623	`doregbits(int r)`
		624	`{`
		625	`ulong b;`
		626
		627	`b = 0;`
		628	`if(r >= D_INDIR)`
		629	`r -= D_INDIR;`
		630	`if(r >= D_AX && r <= D_DI)`
		631	`b \|= RtoB(r);`
		632	`else`
		633	`if(r >= D_AL && r <= D_BL)`
		634	`b \|= RtoB(r-D_AL+D_AX);`
		635	`else`
		636	`if(r >= D_AH && r <= D_BH)`
		637	`b \|= RtoB(r-D_AH+D_AX);`
		638	`return b;`
		639	`}`
		640
		641	`Bits`
		642	`mkvar(Reg r, Adr a, int isro)`
		643	`{`
		644	`Var *v;`
		645	`int i, t, n, et, z;`
		646	`long o;`
		647	`Bits bit;`
		648	`Sym *s;`
		649
		650	`/*`
		651	`* mark registers used`
		652	`*/`
		653	`t = a->type;`
		654	`r->regu \|= doregbits(t);`
		655	`r->regu \|= doregbits(a->index);`
		656	`et = a->etype;`
		657
		658	`switch(t) {`
		659	`default:`
		660	`goto none;`
		661	`case D_INDIR+D_GS:`
		662	`if(!isro \|\| 1)`
		663	`goto none;`
		664	`n = t;`
		665	`{static Sym er; a->sym = &er;}`
		666	`a->sym->name = "$extreg";`
		667	`break;`
		668	`case D_ADDR:`
		669	`a->type = a->index;`
		670	`bit = mkvar(r, a, 0);`
		671	`for(z=0; z<BITS; z++)`
		672	`addrs.b[z] \|= bit.b[z];`
		673	`a->type = t;`
		674	`goto none;`
		675	`case D_EXTERN:`
		676	`case D_STATIC:`
		677	`case D_PARAM:`
		678	`case D_AUTO:`
		679	`n = t;`
		680	`break;`
		681	`}`
		682	`s = a->sym;`
		683	`if(s == S)`
		684	`goto none;`
		685	`if(s->name[0] == '.')`
		686	`goto none;`
		687	`o = a->offset;`
		688	`v = var;`
		689	`for(i=0; i<nvar; i++) {`
		690	`if(s == v->sym)`
		691	`if(n == v->name)`
		692	`if(o == v->offset)`
		693	`goto out;`
		694	`v++;`
		695	`}`
		696	`if(nvar >= NVAR) {`
		697	`if(debug['w'] > 1 && s)`
		698	`warn(Z, "variable not optimized: %s", s->name);`
		699	`goto none;`
		700	`}`
		701	`i = nvar;`
		702	`nvar++;`
		703	`v = &var[i];`
		704	`v->sym = s;`
		705	`v->offset = o;`
		706	`v->name = n;`
		707	`v->etype = et;`
		708	`if(debug['R'])`
		709	`print("bit=%2d et=%2d %D\n", i, et, a);`
		710
		711	`out:`
		712	`bit = blsh(i);`
		713	`if(n == D_EXTERN \|\| n == D_STATIC)`
		714	`for(z=0; z<BITS; z++)`
		715	`externs.b[z] \|= bit.b[z];`
		716	`if(n == D_PARAM)`
		717	`for(z=0; z<BITS; z++)`
		718	`params.b[z] \|= bit.b[z];`
		719	`if(v->etype != et \|\| !typechlpfd[et]) /* funny punning */`
		720	`for(z=0; z<BITS; z++)`
		721	`addrs.b[z] \|= bit.b[z];`
		722	`return bit;`
		723
		724	`none:`
		725	`return zbits;`
		726	`}`
		727
		728	`void`
		729	`prop(Reg *r, Bits ref, Bits cal)`
		730	`{`
		731	`Reg r1, r2;`
		732	`int z;`
		733
		734	`for(r1 = r; r1 != R; r1 = r1->p1) {`
		735	`for(z=0; z<BITS; z++) {`
		736	`ref.b[z] \|= r1->refahead.b[z];`
		737	`if(ref.b[z] != r1->refahead.b[z]) {`
		738	`r1->refahead.b[z] = ref.b[z];`
		739	`change++;`
		740	`}`
		741	`cal.b[z] \|= r1->calahead.b[z];`
		742	`if(cal.b[z] != r1->calahead.b[z]) {`
		743	`r1->calahead.b[z] = cal.b[z];`
		744	`change++;`
		745	`}`
		746	`}`
		747	`switch(r1->prog->as) {`
		748	`case ACALL:`
		749	`for(z=0; z<BITS; z++) {`
		750	`cal.b[z] \|= ref.b[z] \| externs.b[z];`
		751	`ref.b[z] = 0;`
		752	`}`
		753	`break;`
		754
		755	`case ATEXT:`
		756	`for(z=0; z<BITS; z++) {`
		757	`cal.b[z] = 0;`
		758	`ref.b[z] = 0;`
		759	`}`
		760	`break;`
		761
		762	`case ARET:`
		763	`for(z=0; z<BITS; z++) {`
		764	`cal.b[z] = externs.b[z];`
		765	`ref.b[z] = 0;`
		766	`}`
		767	`}`
		768	`for(z=0; z<BITS; z++) {`
		769	`ref.b[z] = (ref.b[z] & ~r1->set.b[z]) \|`
		770	`r1->use1.b[z] \| r1->use2.b[z];`
		771	`cal.b[z] &= ~(r1->set.b[z] \| r1->use1.b[z] \| r1->use2.b[z]);`
		772	`r1->refbehind.b[z] = ref.b[z];`
		773	`r1->calbehind.b[z] = cal.b[z];`
		774	`}`
		775	`if(r1->active)`
		776	`break;`
		777	`r1->active = 1;`
		778	`}`
		779	`for(; r != r1; r = r->p1)`
		780	`for(r2 = r->p2; r2 != R; r2 = r2->p2link)`
		781	`prop(r2, r->refbehind, r->calbehind);`
		782	`}`
		783
		784	`/*`
		785	`* find looping structure`
		786	`*`
		787	`* 1) find reverse postordering`
		788	`* 2) find approximate dominators,`
		789	`* the actual dominators if the flow graph is reducible`
		790	`* otherwise, dominators plus some other non-dominators.`
		791	`* See Matthew S. Hecht and Jeffrey D. Ullman,`
		792	`* "Analysis of a Simple Algorithm for Global Data Flow Problems",`
		793	`* Conf. Record of ACM Symp. on Principles of Prog. Langs, Boston, Massachusetts,`
		794	`* Oct. 1-3, 1973, pp. 207-217.`
		795	`* 3) find all nodes with a predecessor dominated by the current node.`
		796	`* such a node is a loop head.`
		797	`* recursively, all preds with a greater rpo number are in the loop`
		798	`*/`
		799	`long`
		800	`postorder(Reg r, Reg *rpo2r, long n)`
		801	`{`
		802	`Reg *r1;`
		803
		804	`r->rpo = 1;`
		805	`r1 = r->s1;`
		806	`if(r1 && !r1->rpo)`
		807	`n = postorder(r1, rpo2r, n);`
		808	`r1 = r->s2;`
		809	`if(r1 && !r1->rpo)`
		810	`n = postorder(r1, rpo2r, n);`
		811	`rpo2r[n] = r;`
		812	`n++;`
		813	`return n;`
		814	`}`
		815
		816	`long`
		817	`rpolca(long *idom, long rpo1, long rpo2)`
		818	`{`
		819	`long t;`
		820
		821	`if(rpo1 == -1)`
		822	`return rpo2;`
		823	`while(rpo1 != rpo2){`
		824	`if(rpo1 > rpo2){`
		825	`t = rpo2;`
		826	`rpo2 = rpo1;`
		827	`rpo1 = t;`
		828	`}`
		829	`while(rpo1 < rpo2){`
		830	`t = idom[rpo2];`
		831	`if(t >= rpo2)`
		832	`fatal(Z, "bad idom");`
		833	`rpo2 = t;`
		834	`}`
		835	`}`
		836	`return rpo1;`
		837	`}`
		838
		839	`int`
		840	`doms(long *idom, long r, long s)`
		841	`{`
		842	`while(s > r)`
		843	`s = idom[s];`
		844	`return s == r;`
		845	`}`
		846
		847	`int`
		848	`loophead(long idom, Reg r)`
		849	`{`
		850	`long src;`
		851
		852	`src = r->rpo;`
		853	`if(r->p1 != R && doms(idom, src, r->p1->rpo))`
		854	`return 1;`
		855	`for(r = r->p2; r != R; r = r->p2link)`
		856	`if(doms(idom, src, r->rpo))`
		857	`return 1;`
		858	`return 0;`
		859	`}`
		860
		861	`void`
		862	`loopmark(Reg *rpo2r, long head, Reg r)`
		863	`{`
		864	`if(r->rpo < head \|\| r->active == head)`
		865	`return;`
		866	`r->active = head;`
		867	`r->loop += LOOP;`
		868	`if(r->p1 != R)`
		869	`loopmark(rpo2r, head, r->p1);`
		870	`for(r = r->p2; r != R; r = r->p2link)`
		871	`loopmark(rpo2r, head, r);`
		872	`}`
		873
		874	`void`
		875	`loopit(Reg *r, long nr)`
		876	`{`
		877	`Reg *r1;`
		878	`long i, d, me;`
		879
		880	`if(nr > maxnr) {`
		881	`rpo2r = alloc(nr * sizeof(Reg*));`
		882	`idom = alloc(nr * sizeof(long));`
		883	`maxnr = nr;`
		884	`}`
		885
		886	`d = postorder(r, rpo2r, 0);`
		887	`if(d > nr)`
		888	`fatal(Z, "too many reg nodes");`
		889	`nr = d;`
		890	`for(i = 0; i < nr / 2; i++){`
		891	`r1 = rpo2r[i];`
		892	`rpo2r[i] = rpo2r[nr - 1 - i];`
		893	`rpo2r[nr - 1 - i] = r1;`
		894	`}`
		895	`for(i = 0; i < nr; i++)`
		896	`rpo2r[i]->rpo = i;`
		897
		898	`idom[0] = 0;`
		899	`for(i = 0; i < nr; i++){`
		900	`r1 = rpo2r[i];`
		901	`me = r1->rpo;`
		902	`d = -1;`
		903	`if(r1->p1 != R && r1->p1->rpo < me)`
		904	`d = r1->p1->rpo;`
		905	`for(r1 = r1->p2; r1 != nil; r1 = r1->p2link)`
		906	`if(r1->rpo < me)`
		907	`d = rpolca(idom, d, r1->rpo);`
		908	`idom[i] = d;`
		909	`}`
		910
		911	`for(i = 0; i < nr; i++){`
		912	`r1 = rpo2r[i];`
		913	`r1->loop++;`
		914	`if(r1->p2 != R && loophead(idom, r1))`
		915	`loopmark(rpo2r, i, r1);`
		916	`}`
		917	`}`
		918
		919	`void`
		920	`synch(Reg *r, Bits dif)`
		921	`{`
		922	`Reg *r1;`
		923	`int z;`
		924
		925	`for(r1 = r; r1 != R; r1 = r1->s1) {`
		926	`for(z=0; z<BITS; z++) {`
		927	`dif.b[z] = (dif.b[z] &`
		928	`~(~r1->refbehind.b[z] & r1->refahead.b[z])) \|`
		929	`r1->set.b[z] \| r1->regdiff.b[z];`
		930	`if(dif.b[z] != r1->regdiff.b[z]) {`
		931	`r1->regdiff.b[z] = dif.b[z];`
		932	`change++;`
		933	`}`
		934	`}`
		935	`if(r1->active)`
		936	`break;`
		937	`r1->active = 1;`
		938	`for(z=0; z<BITS; z++)`
		939	`dif.b[z] &= ~(~r1->calbehind.b[z] & r1->calahead.b[z]);`
		940	`if(r1->s2 != R)`
		941	`synch(r1->s2, dif);`
		942	`}`
		943	`}`
		944
		945	`ulong`
		946	`allreg(ulong b, Rgn *r)`
		947	`{`
		948	`Var *v;`
		949	`int i;`
		950
		951	`v = var + r->varno;`
		952	`r->regno = 0;`
		953	`switch(v->etype) {`
		954
		955	`default:`
		956	`diag(Z, "unknown etype %d/%d", bitno(b), v->etype);`
		957	`break;`
		958
		959	`case TCHAR:`
		960	`case TUCHAR:`
		961	`case TSHORT:`
		962	`case TUSHORT:`
		963	`case TINT:`
		964	`case TUINT:`
		965	`case TLONG:`
		966	`case TULONG:`
		967	`case TIND:`
		968	`case TARRAY:`
		969	`i = BtoR(~b);`
		970	`if(i && r->cost > 0) {`
		971	`r->regno = i;`
		972	`return RtoB(i);`
		973	`}`
		974	`break;`
		975
		976	`case TDOUBLE:`
		977	`case TFLOAT:`
		978	`break;`
		979	`}`
		980	`return 0;`
		981	`}`
		982
		983	`void`
		984	`paint1(Reg *r, int bn)`
		985	`{`
		986	`Reg *r1;`
		987	`Prog *p;`
		988	`int z;`
		989	`ulong bb;`
		990
		991	`z = bn/32;`
		992	`bb = 1L<<(bn%32);`
		993	`if(r->act.b[z] & bb)`
		994	`return;`
		995	`for(;;) {`
		996	`if(!(r->refbehind.b[z] & bb))`
		997	`break;`
		998	`r1 = r->p1;`
		999	`if(r1 == R)`
		1000	`break;`
		1001	`if(!(r1->refahead.b[z] & bb))`
		1002	`break;`
		1003	`if(r1->act.b[z] & bb)`
		1004	`break;`
		1005	`r = r1;`
		1006	`}`
		1007
		1008	`if(LOAD(r) & ~(r->set.b[z]&~(r->use1.b[z]\|r->use2.b[z])) & bb) {`
		1009	`change -= CLOAD * r->loop;`
		1010	`if(debug['R'] && debug['v'])`
		1011	`print("%ld%P\tld %B $%d\n", r->loop,`
		1012	`r->prog, blsh(bn), change);`
		1013	`}`
		1014	`for(;;) {`
		1015	`r->act.b[z] \|= bb;`
		1016	`p = r->prog;`
		1017
		1018	`if(r->use1.b[z] & bb) {`
		1019	`change += CREF * r->loop;`
		1020	`if(p->as == AFMOVL \|\| p->as == AFMOVW)`
		1021	`if(BtoR(bb) != D_F0)`
		1022	`change = -CINF;`
		1023	`if(debug['R'] && debug['v'])`
		1024	`print("%ld%P\tu1 %B $%d\n", r->loop,`
		1025	`p, blsh(bn), change);`
		1026	`}`
		1027
		1028	`if((r->use2.b[z]\|r->set.b[z]) & bb) {`
		1029	`change += CREF * r->loop;`
		1030	`if(p->as == AFMOVL \|\| p->as == AFMOVW)`
		1031	`if(BtoR(bb) != D_F0)`
		1032	`change = -CINF;`
		1033	`if(debug['R'] && debug['v'])`
		1034	`print("%ld%P\tu2 %B $%d\n", r->loop,`
		1035	`p, blsh(bn), change);`
		1036	`}`
		1037
		1038	`if(STORE(r) & r->regdiff.b[z] & bb) {`
		1039	`change -= CLOAD * r->loop;`
		1040	`if(p->as == AFMOVL \|\| p->as == AFMOVW)`
		1041	`if(BtoR(bb) != D_F0)`
		1042	`change = -CINF;`
		1043	`if(debug['R'] && debug['v'])`
		1044	`print("%ld%P\tst %B $%d\n", r->loop,`
		1045	`p, blsh(bn), change);`
		1046	`}`
		1047
		1048	`if(r->refbehind.b[z] & bb)`
		1049	`for(r1 = r->p2; r1 != R; r1 = r1->p2link)`
		1050	`if(r1->refahead.b[z] & bb)`
		1051	`paint1(r1, bn);`
		1052
		1053	`if(!(r->refahead.b[z] & bb))`
		1054	`break;`
		1055	`r1 = r->s2;`
		1056	`if(r1 != R)`
		1057	`if(r1->refbehind.b[z] & bb)`
		1058	`paint1(r1, bn);`
		1059	`r = r->s1;`
		1060	`if(r == R)`
		1061	`break;`
		1062	`if(r->act.b[z] & bb)`
		1063	`break;`
		1064	`if(!(r->refbehind.b[z] & bb))`
		1065	`break;`
		1066	`}`
		1067	`}`
		1068
		1069	`ulong`
		1070	`regset(Reg *r, ulong bb)`
		1071	`{`
		1072	`ulong b, set;`
		1073	`Adr v;`
		1074	`int c;`
		1075
		1076	`set = 0;`
		1077	`v = zprog.from;`
		1078	`while(b = bb & ~(bb-1)) {`
		1079	`v.type = BtoR(b);`
		1080	`c = copyu(r->prog, &v, A);`
		1081	`if(c == 3)`
		1082	`set \|= b;`
		1083	`bb &= ~b;`
		1084	`}`
		1085	`return set;`
		1086	`}`
		1087
		1088	`ulong`
		1089	`reguse(Reg *r, ulong bb)`
		1090	`{`
		1091	`ulong b, set;`
		1092	`Adr v;`
		1093	`int c;`
		1094
		1095	`set = 0;`
		1096	`v = zprog.from;`
		1097	`while(b = bb & ~(bb-1)) {`
		1098	`v.type = BtoR(b);`
		1099	`c = copyu(r->prog, &v, A);`
		1100	`if(c == 1 \|\| c == 2 \|\| c == 4)`
		1101	`set \|= b;`
		1102	`bb &= ~b;`
		1103	`}`
		1104	`return set;`
		1105	`}`
		1106
		1107	`ulong`
		1108	`paint2(Reg *r, int bn)`
		1109	`{`
		1110	`Reg *r1;`
		1111	`int z;`
		1112	`ulong bb, vreg, x;`
		1113
		1114	`z = bn/32;`
		1115	`bb = 1L << (bn%32);`
		1116	`vreg = regbits;`
		1117	`if(!(r->act.b[z] & bb))`
		1118	`return vreg;`
		1119	`for(;;) {`
		1120	`if(!(r->refbehind.b[z] & bb))`
		1121	`break;`
		1122	`r1 = r->p1;`
		1123	`if(r1 == R)`
		1124	`break;`
		1125	`if(!(r1->refahead.b[z] & bb))`
		1126	`break;`
		1127	`if(!(r1->act.b[z] & bb))`
		1128	`break;`
		1129	`r = r1;`
		1130	`}`
		1131	`for(;;) {`
		1132	`r->act.b[z] &= ~bb;`
		1133
		1134	`vreg \|= r->regu;`
		1135
		1136	`if(r->refbehind.b[z] & bb)`
		1137	`for(r1 = r->p2; r1 != R; r1 = r1->p2link)`
		1138	`if(r1->refahead.b[z] & bb)`
		1139	`vreg \|= paint2(r1, bn);`
		1140
		1141	`if(!(r->refahead.b[z] & bb))`
		1142	`break;`
		1143	`r1 = r->s2;`
		1144	`if(r1 != R)`
		1145	`if(r1->refbehind.b[z] & bb)`
		1146	`vreg \|= paint2(r1, bn);`
		1147	`r = r->s1;`
		1148	`if(r == R)`
		1149	`break;`
		1150	`if(!(r->act.b[z] & bb))`
		1151	`break;`
		1152	`if(!(r->refbehind.b[z] & bb))`
		1153	`break;`
		1154	`}`
		1155
		1156	`bb = vreg;`
		1157	`for(; r; r=r->s1) {`
		1158	`x = r->regu & ~bb;`
		1159	`if(x) {`
		1160	`vreg \|= reguse(r, x);`
		1161	`bb \|= regset(r, x);`
		1162	`}`
		1163	`}`
		1164	`return vreg;`
		1165	`}`
		1166
		1167	`void`
		1168	`paint3(Reg *r, int bn, long rb, int rn)`
		1169	`{`
		1170	`Reg *r1;`
		1171	`Prog *p;`
		1172	`int z;`
		1173	`ulong bb;`
		1174
		1175	`z = bn/32;`
		1176	`bb = 1L << (bn%32);`
		1177	`if(r->act.b[z] & bb)`
		1178	`return;`
		1179	`for(;;) {`
		1180	`if(!(r->refbehind.b[z] & bb))`
		1181	`break;`
		1182	`r1 = r->p1;`
		1183	`if(r1 == R)`
		1184	`break;`
		1185	`if(!(r1->refahead.b[z] & bb))`
		1186	`break;`
		1187	`if(r1->act.b[z] & bb)`
		1188	`break;`
		1189	`r = r1;`
		1190	`}`
		1191
		1192	`if(LOAD(r) & ~(r->set.b[z] & ~(r->use1.b[z]\|r->use2.b[z])) & bb)`
		1193	`addmove(r, bn, rn, 0);`
		1194	`for(;;) {`
		1195	`r->act.b[z] \|= bb;`
		1196	`p = r->prog;`
		1197
		1198	`if(r->use1.b[z] & bb) {`
		1199	`if(debug['R'])`
		1200	`print("%P", p);`
		1201	`addreg(&p->from, rn);`
		1202	`if(debug['R'])`
		1203	`print("\t.c%P\n", p);`
		1204	`}`
		1205	`if((r->use2.b[z]\|r->set.b[z]) & bb) {`
		1206	`if(debug['R'])`
		1207	`print("%P", p);`
		1208	`addreg(&p->to, rn);`
		1209	`if(debug['R'])`
		1210	`print("\t.c%P\n", p);`
		1211	`}`
		1212
		1213	`if(STORE(r) & r->regdiff.b[z] & bb)`
		1214	`addmove(r, bn, rn, 1);`
		1215	`r->regu \|= rb;`
		1216
		1217	`if(r->refbehind.b[z] & bb)`
		1218	`for(r1 = r->p2; r1 != R; r1 = r1->p2link)`
		1219	`if(r1->refahead.b[z] & bb)`
		1220	`paint3(r1, bn, rb, rn);`
		1221
		1222	`if(!(r->refahead.b[z] & bb))`
		1223	`break;`
		1224	`r1 = r->s2;`
		1225	`if(r1 != R)`
		1226	`if(r1->refbehind.b[z] & bb)`
		1227	`paint3(r1, bn, rb, rn);`
		1228	`r = r->s1;`
		1229	`if(r == R)`
		1230	`break;`
		1231	`if(r->act.b[z] & bb)`
		1232	`break;`
		1233	`if(!(r->refbehind.b[z] & bb))`
		1234	`break;`
		1235	`}`
		1236	`}`
		1237
		1238	`void`
		1239	`addreg(Adr *a, int rn)`
		1240	`{`
		1241
		1242	`a->sym = 0;`
		1243	`a->offset = 0;`
		1244	`a->type = rn;`
		1245	`}`
		1246
		1247	`long`
		1248	`RtoB(int r)`
		1249	`{`
		1250
		1251	`if(r < D_AX \|\| r > D_DI)`
		1252	`return 0;`
		1253	`return 1L << (r-D_AX);`
		1254	`}`
		1255
		1256	`int`
		1257	`BtoR(long b)`
		1258	`{`
		1259
		1260	`b &= 0xffL;`
		1261	`if(b == 0)`
		1262	`return 0;`
		1263	`return bitno(b) + D_AX;`
		1264	`}`

Subversion Repositories planix.SVN

(root)/os/branches/planix-v0/sys/src/cmd/8c/reg.c – Rev 2