WebSVN – planix.SVN – Blame – /os/branches/feature_unix/sys/src/cmd/vc/reg.c

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

Subversion Repositories planix.SVN

(root)/os/branches/feature_unix/sys/src/cmd/vc/reg.c – Rev 2