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

Subversion Repositories planix.SVN

(root)/os/branches/feature_fixcpp/sys/src/cmd/kc/reg.c – Rev 87