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

Subversion Repositories planix.SVN

(root)/os/branches/feature_tlsv12/sys/src/cmd/qc/reg.c – Rev 2