WebSVN – planix.SVN – Blame – /os/branches/planix-v0/sys/src/cmd/kl/sched.c

Rev	Author	Line No.	Line
2	-	1	`#include "l.h"`
		2
		3	`enum`
		4	`{`
		5	`E_ICC = 1<<0,`
		6	`E_FCC = 1<<1,`
		7	`E_MEM = 1<<2,`
		8	`E_MEMSP = 1<<3, /* uses offset and size */`
		9	`E_MEMSB = 1<<4, /* uses offset and size */`
		10	`ANYMEM = E_MEM\|E_MEMSP\|E_MEMSB,`
		11	`ALL = ~0`
		12	`};`
		13
		14	`typedef struct Sch Sch;`
		15	`typedef struct Dep Dep;`
		16
		17	`struct Dep`
		18	`{`
		19	`ulong ireg;`
		20	`ulong freg;`
		21	`ulong cc;`
		22	`};`
		23	`struct Sch`
		24	`{`
		25	`Prog p;`
		26	`Dep set;`
		27	`Dep used;`
		28	`long soffset;`
		29	`char size;`
		30	`char nop;`
		31	`char comp;`
		32	`};`
		33
		34	`void regsused(Sch, Prog);`
		35	`int depend(Sch, Sch);`
		36	`int conflict(Sch, Sch);`
		37	`int offoverlap(Sch, Sch);`
		38	`void dumpbits(Sch, Dep);`
		39
		40	`void`
		41	`sched(Prog p0, Prog pe)`
		42	`{`
		43	`Prog p, q;`
		44	`Sch sch[NSCHED], s, t, u, se, stmp;`
		45
		46	`/*`
		47	`* build side structure`
		48	`*/`
		49	`s = sch;`
		50	`for(p=p0;; p=p->link) {`
		51	`memset(s, 0, sizeof(*s));`
		52	`s->p = *p;`
		53	`regsused(s, p);`
		54	`if(debug['X']) {`
		55	`Bprint(&bso, "%P\tset", &s->p);`
		56	`dumpbits(s, &s->set);`
		57	`Bprint(&bso, "; used");`
		58	`dumpbits(s, &s->used);`
		59	`if(s->comp)`
		60	`Bprint(&bso, "; compound");`
		61	`if(s->p.mark & LOAD)`
		62	`Bprint(&bso, "; load");`
		63	`if(s->p.mark & BRANCH)`
		64	`Bprint(&bso, "; branch");`
		65	`if(s->p.mark & FCMP)`
		66	`Bprint(&bso, "; fcmp");`
		67	`Bprint(&bso, "\n");`
		68	`}`
		69	`s++;`
		70	`if(p == pe)`
		71	`break;`
		72	`}`
		73	`se = s;`
		74
		75	`for(s=se-1; s>=sch; s--) {`
		76	`/*`
		77	`* branch delay slot`
		78	`*/`
		79	`if(s->p.mark & BRANCH) {`
		80	`/* t is the trial instruction to use */`
		81	`for(t=s-1; t>=sch; t--) {`
		82	`if(t->comp \|\| (t->p.mark & FCMP))`
		83	`goto no1;`
		84	`for(u=t+1; u<=s; u++)`
		85	`if(depend(u, t))`
		86	`goto no1;`
		87	`goto out1;`
		88	`no1:;`
		89	`}`
		90	`if(debug['X'])`
		91	`Bprint(&bso, "?b%P\n", &s->p);`
		92	`s->nop = 1;`
		93	`continue;`
		94
		95	`out1:`
		96	`if(debug['X']) {`
		97	`Bprint(&bso, "!b%P\n", &t->p);`
		98	`Bprint(&bso, "%P\n", &s->p);`
		99	`}`
		100	`stmp = *t;`
		101	`memmove(t, t+1, (uchar)s - (uchar)t);`
		102	`*s = stmp;`
		103	`s--;`
		104	`continue;`
		105	`}`
		106
		107	`/*`
		108	`* load delay. interlocked.`
		109	`*/`
		110	`if(s->p.mark & LOAD) {`
		111	`if(s >= se-1)`
		112	`continue;`
		113	`if(!conflict(s, (s+1)))`
		114	`continue;`
		115	`/*`
		116	`* s is load, s+1 is immediate use of result`
		117	`* t is the trial instruction to insert between s and s+1`
		118	`*/`
		119	`for(t=s-1; t>=sch; t--) {`
		120	`if(t->p.mark & BRANCH)`
		121	`goto no2;`
		122	`if(t->p.mark & FCMP)`
		123	`if((s+1)->p.mark & BRANCH)`
		124	`goto no2;`
		125	`if(t->p.mark & LOAD)`
		126	`if(conflict(t, (s+1)))`
		127	`goto no2;`
		128	`for(u=t+1; u<=s; u++)`
		129	`if(depend(u, t))`
		130	`goto no2;`
		131	`goto out2;`
		132	`no2:;`
		133	`}`
		134	`if(debug['X'])`
		135	`Bprint(&bso, "?l%P\n", &s->p);`
		136	`continue;`
		137	`out2:`
		138	`if(debug['X']) {`
		139	`Bprint(&bso, "!l%P\n", &t->p);`
		140	`Bprint(&bso, "%P\n", &s->p);`
		141	`}`
		142	`stmp = *t;`
		143	`memmove(t, t+1, (uchar)s - (uchar)t);`
		144	`*s = stmp;`
		145	`s--;`
		146	`continue;`
		147	`}`
		148
		149	`/*`
		150	`* fop2 delay.`
		151	`*/`
		152	`if(s->p.mark & FCMP) {`
		153	`if(s >= se-1) {`
		154	`s->nop = 1;`
		155	`continue;`
		156	`}`
		157	`if(!((s+1)->p.mark & BRANCH))`
		158	`continue;`
		159	`/* t is the trial instruction to use */`
		160	`for(t=s-1; t>=sch; t--) {`
		161	`for(u=t+1; u<=s; u++)`
		162	`if(depend(u, t))`
		163	`goto no3;`
		164	`goto out3;`
		165	`no3:;`
		166	`}`
		167	`if(debug['X'])`
		168	`Bprint(&bso, "?f%P\n", &s->p);`
		169	`s->nop = 1;`
		170	`continue;`
		171	`out3:`
		172	`if(debug['X']) {`
		173	`Bprint(&bso, "!f%P\n", &t->p);`
		174	`Bprint(&bso, "%P\n", &s->p);`
		175	`}`
		176	`stmp = *t;`
		177	`memmove(t, t+1, (uchar)s - (uchar)t);`
		178	`*s = stmp;`
		179	`s--;`
		180	`continue;`
		181	`}`
		182	`}`
		183
		184	`/*`
		185	`* put it all back`
		186	`*/`
		187	`for(s=sch, p=p0; s<se; s++, p=q) {`
		188	`q = p->link;`
		189	`if(q != s->p.link) {`
		190	`*p = s->p;`
		191	`p->link = q;`
		192	`}`
		193	`if(s->nop)`
		194	`addnop(p);`
		195	`}`
		196	`if(debug['X'])`
		197	`Bprint(&bso, "\n");`
		198	`}`
		199
		200	`void`
		201	`regsused(Sch s, Prog realp)`
		202	`{`
		203	`int c, ar, ad, ld, sz;`
		204	`ulong m;`
		205	`Prog *p;`
		206
		207	`p = &s->p;`
		208	`s->comp = compound(p);`
		209	`s->nop = 0;`
		210	`if(s->comp) {`
		211	`s->set.ireg \|= 1<<REGTMP;`
		212	`s->used.ireg \|= 1<<REGTMP;`
		213	`}`
		214	`ar = 0; /* dest is really reference */`
		215	`ad = 0; /* source/dest is really address */`
		216	`ld = 0; /* opcode is load instruction */`
		217	`sz = 20; /* size of load/store for overlap computation */`
		218
		219	`/*`
		220	`* flags based on opcode`
		221	`*/`
		222	`switch(p->as) {`
		223	`case ATEXT:`
		224	`curtext = realp;`
		225	`autosize = p->to.offset + 4;`
		226	`ad = 1;`
		227	`break;`
		228	`case AJMPL:`
		229	`c = p->reg;`
		230	`if(c == NREG)`
		231	`c = REGLINK;`
		232	`s->set.ireg \|= 1<<c;`
		233	`ar = 1;`
		234	`ad = 1;`
		235	`break;`
		236	`case AJMP:`
		237	`ar = 1;`
		238	`ad = 1;`
		239	`break;`
		240	`case ACMP:`
		241	`s->set.cc \|= E_ICC;`
		242	`ar = 1;`
		243	`break;`
		244	`case AFCMPD:`
		245	`case AFCMPED:`
		246	`case AFCMPEF:`
		247	`case AFCMPEX:`
		248	`case AFCMPF:`
		249	`case AFCMPX:`
		250	`s->set.cc \|= E_FCC;`
		251	`ar = 1;`
		252	`break;`
		253	`case ABE:`
		254	`case ABNE:`
		255	`case ABLE:`
		256	`case ABG:`
		257	`case ABL:`
		258	`case ABGE:`
		259	`case ABLEU:`
		260	`case ABGU:`
		261	`case ABCS:`
		262	`case ABCC:`
		263	`case ABNEG:`
		264	`case ABPOS:`
		265	`case ABVC:`
		266	`case ABVS:`
		267	`s->used.cc \|= E_ICC;`
		268	`ar = 1;`
		269	`break;`
		270	`case AFBE:`
		271	`case AFBLG:`
		272	`case AFBG:`
		273	`case AFBLE:`
		274	`case AFBGE:`
		275	`case AFBL:`
		276	`s->used.cc \|= E_FCC;`
		277	`ar = 1;`
		278	`break;`
		279	`case AMOVB:`
		280	`case AMOVBU:`
		281	`sz = 1;`
		282	`ld = 1;`
		283	`break;`
		284	`case AMOVH:`
		285	`case AMOVHU:`
		286	`sz = 2;`
		287	`ld = 1;`
		288	`break;`
		289	`case AFMOVF:`
		290	`case AMOVW:`
		291	`sz = 4;`
		292	`ld = 1;`
		293	`break;`
		294	`case AMOVD:`
		295	`case AFMOVD:`
		296	`sz = 8;`
		297	`ld = 1;`
		298	`break;`
		299	`case AFMOVX: /* gok */`
		300	`sz = 16;`
		301	`ld = 1;`
		302	`break;`
		303	`case AADDCC:`
		304	`case AADDXCC:`
		305	`case AANDCC:`
		306	`case AANDNCC:`
		307	`case AORCC:`
		308	`case AORNCC:`
		309	`case ASUBCC:`
		310	`case ASUBXCC:`
		311	`case ATADDCC:`
		312	`case ATADDCCTV:`
		313	`case ATSUBCC:`
		314	`case ATSUBCCTV:`
		315	`case AXNORCC:`
		316	`case AXORCC:`
		317	`s->set.cc \|= E_ICC;`
		318	`break;`
		319	`case ADIV:`
		320	`case ADIVL:`
		321	`case AMOD:`
		322	`case AMODL:`
		323	`case AMUL:`
		324	`case AMULSCC:`
		325	`case ATAS:`
		326	`s->set.ireg = ALL;`
		327	`s->set.freg = ALL;`
		328	`s->set.cc = ALL;`
		329	`break;`
		330	`}`
		331
		332	`/*`
		333	`* flags based on 'to' field`
		334	`*/`
		335	`c = p->to.class;`
		336	`if(c == 0) {`
		337	`c = aclass(&p->to) + 1;`
		338	`p->to.class = c;`
		339	`}`
		340	`c--;`
		341	`switch(c) {`
		342	`default:`
		343	`print("unknown class %d %D\n", c, &p->to);`
		344
		345	`case C_ZCON:`
		346	`case C_SCON:`
		347	`case C_UCON:`
		348	`case C_LCON:`
		349	`case C_NONE:`
		350	`case C_SBRA:`
		351	`case C_LBRA:`
		352	`break;`
		353	`case C_CREG:`
		354	`case C_FSR:`
		355	`case C_FQ:`
		356	`case C_PREG:`
		357	`s->set.ireg = ALL;`
		358	`s->set.freg = ALL;`
		359	`s->set.cc = ALL;`
		360	`break;`
		361	`case C_ZOREG:`
		362	`case C_SOREG:`
		363	`case C_LOREG:`
		364	`case C_ASI:`
		365	`c = p->to.reg;`
		366	`s->used.ireg \|= 1<<c;`
		367	`if(ad)`
		368	`break;`
		369	`s->size = sz;`
		370	`s->soffset = regoff(&p->to);`
		371
		372	`m = ANYMEM;`
		373	`if(c == REGSB)`
		374	`m = E_MEMSB;`
		375	`if(c == REGSP)`
		376	`m = E_MEMSP;`
		377
		378	`if(ar)`
		379	`s->used.cc \|= m;`
		380	`else`
		381	`s->set.cc \|= m;`
		382	`break;`
		383	`case C_SACON:`
		384	`case C_LACON:`
		385	`s->used.ireg \|= 1<<REGSP;`
		386	`break;`
		387	`case C_SECON:`
		388	`case C_LECON:`
		389	`s->used.ireg \|= 1<<REGSB;`
		390	`break;`
		391	`case C_REG:`
		392	`if(ar)`
		393	`s->used.ireg \|= 1<<p->to.reg;`
		394	`else`
		395	`s->set.ireg \|= 1<<p->to.reg;`
		396	`break;`
		397	`case C_FREG:`
		398	`/* do better -- determine double prec */`
		399	`if(ar) {`
		400	`s->used.freg \|= 1<<p->to.reg;`
		401	`s->used.freg \|= 1<<(p->to.reg\|1);`
		402	`} else {`
		403	`s->set.freg \|= 1<<p->to.reg;`
		404	`s->set.freg \|= 1<<(p->to.reg\|1);`
		405	`}`
		406	`break;`
		407	`case C_SAUTO:`
		408	`case C_LAUTO:`
		409	`case C_ESAUTO:`
		410	`case C_OSAUTO:`
		411	`case C_ELAUTO:`
		412	`case C_OLAUTO:`
		413	`s->used.ireg \|= 1<<REGSP;`
		414	`if(ad)`
		415	`break;`
		416	`s->size = sz;`
		417	`s->soffset = regoff(&p->to);`
		418
		419	`if(ar)`
		420	`s->used.cc \|= E_MEMSP;`
		421	`else`
		422	`s->set.cc \|= E_MEMSP;`
		423	`break;`
		424	`case C_SEXT:`
		425	`case C_LEXT:`
		426	`case C_ESEXT:`
		427	`case C_OSEXT:`
		428	`case C_ELEXT:`
		429	`case C_OLEXT:`
		430	`s->used.ireg \|= 1<<REGSB;`
		431	`if(ad)`
		432	`break;`
		433	`s->size = sz;`
		434	`s->soffset = regoff(&p->to);`
		435
		436	`if(ar)`
		437	`s->used.cc \|= E_MEMSB;`
		438	`else`
		439	`s->set.cc \|= E_MEMSB;`
		440	`break;`
		441	`}`
		442
		443	`/*`
		444	`* flags based on 'from' field`
		445	`*/`
		446	`c = p->from.class;`
		447	`if(c == 0) {`
		448	`c = aclass(&p->from) + 1;`
		449	`p->from.class = c;`
		450	`}`
		451	`c--;`
		452	`switch(c) {`
		453	`default:`
		454	`print("unknown class %d %D\n", c, &p->from);`
		455
		456	`case C_ZCON:`
		457	`case C_SCON:`
		458	`case C_UCON:`
		459	`case C_LCON:`
		460	`case C_NONE:`
		461	`case C_SBRA:`
		462	`case C_LBRA:`
		463	`c = p->from.reg;`
		464	`if(c != NREG)`
		465	`s->used.ireg \|= 1<<c;`
		466	`break;`
		467	`case C_CREG:`
		468	`case C_FSR:`
		469	`case C_FQ:`
		470	`case C_PREG:`
		471	`s->set.ireg = ALL;`
		472	`s->set.freg = ALL;`
		473	`s->set.cc = ALL;`
		474	`break;`
		475	`case C_ZOREG:`
		476	`case C_SOREG:`
		477	`case C_LOREG:`
		478	`case C_ASI:`
		479	`c = p->from.reg;`
		480	`s->used.ireg \|= 1<<c;`
		481	`if(ld)`
		482	`p->mark \|= LOAD;`
		483	`if(ad)`
		484	`break;`
		485	`s->size = sz;`
		486	`s->soffset = regoff(&p->from);`
		487
		488	`m = ANYMEM;`
		489	`if(c == REGSB)`
		490	`m = E_MEMSB;`
		491	`if(c == REGSP)`
		492	`m = E_MEMSP;`
		493
		494	`s->used.cc \|= m;`
		495	`break;`
		496	`case C_SACON:`
		497	`case C_LACON:`
		498	`s->used.ireg \|= 1<<REGSP;`
		499	`break;`
		500	`case C_SECON:`
		501	`case C_LECON:`
		502	`s->used.ireg \|= 1<<REGSB;`
		503	`break;`
		504	`case C_REG:`
		505	`s->used.ireg \|= 1<<p->from.reg;`
		506	`break;`
		507	`case C_FREG:`
		508	`/* do better -- determine double prec */`
		509	`s->used.freg \|= 1<<p->from.reg;`
		510	`s->used.freg \|= 1<<(p->from.reg\|1);`
		511	`break;`
		512	`case C_SAUTO:`
		513	`case C_LAUTO:`
		514	`case C_ESAUTO:`
		515	`case C_ELAUTO:`
		516	`case C_OSAUTO:`
		517	`case C_OLAUTO:`
		518	`s->used.ireg \|= 1<<REGSP;`
		519	`if(ld)`
		520	`p->mark \|= LOAD;`
		521	`if(ad)`
		522	`break;`
		523	`s->size = sz;`
		524	`s->soffset = regoff(&p->from);`
		525
		526	`s->used.cc \|= E_MEMSP;`
		527	`break;`
		528	`case C_SEXT:`
		529	`case C_LEXT:`
		530	`case C_ESEXT:`
		531	`case C_ELEXT:`
		532	`case C_OSEXT:`
		533	`case C_OLEXT:`
		534	`s->used.ireg \|= 1<<REGSB;`
		535	`if(ld)`
		536	`p->mark \|= LOAD;`
		537	`if(ad)`
		538	`break;`
		539	`s->size = sz;`
		540	`s->soffset = regoff(&p->from);`
		541
		542	`s->used.cc \|= E_MEMSB;`
		543	`break;`
		544	`}`
		545
		546	`c = p->reg;`
		547	`if(c != NREG) {`
		548	`if(p->from.type == D_FREG \|\| p->to.type == D_FREG) {`
		549	`s->used.freg \|= 1<<c;`
		550	`s->used.freg \|= 1<<(c\|1);`
		551	`} else`
		552	`s->used.ireg \|= 1<<c;`
		553	`}`
		554	`s->set.ireg &= ~(1<<0); /* R0 cant be set */`
		555	`}`
		556
		557	`/*`
		558	`* test to see if 2 instrictions can be`
		559	`* interchanged without changing semantics`
		560	`*/`
		561	`int`
		562	`depend(Sch sa, Sch sb)`
		563	`{`
		564	`ulong x;`
		565
		566	`if(sa->set.ireg & (sb->set.ireg\|sb->used.ireg))`
		567	`return 1;`
		568	`if(sb->set.ireg & sa->used.ireg)`
		569	`return 1;`
		570
		571	`if(sa->set.freg & (sb->set.freg\|sb->used.freg))`
		572	`return 1;`
		573	`if(sb->set.freg & sa->used.freg)`
		574	`return 1;`
		575
		576	`x = (sa->set.cc & (sb->set.cc\|sb->used.cc)) \|`
		577	`(sb->set.cc & sa->used.cc);`
		578	`if(x) {`
		579	`/*`
		580	`* allow SB and SP to pass each other.`
		581	`* allow SB to pass SB iff doffsets are ok`
		582	`* anything else conflicts`
		583	`*/`
		584	`if(x != E_MEMSP && x != E_MEMSB)`
		585	`return 1;`
		586	`x = sa->set.cc \| sb->set.cc \|`
		587	`sa->used.cc \| sb->used.cc;`
		588	`if(x & E_MEM)`
		589	`return 1;`
		590	`if(offoverlap(sa, sb))`
		591	`return 1;`
		592	`}`
		593
		594	`return 0;`
		595	`}`
		596
		597	`int`
		598	`offoverlap(Sch sa, Sch sb)`
		599	`{`
		600
		601	`if(sa->soffset < sb->soffset) {`
		602	`if(sa->soffset+sa->size > sb->soffset)`
		603	`return 1;`
		604	`return 0;`
		605	`}`
		606	`if(sb->soffset+sb->size > sa->soffset)`
		607	`return 1;`
		608	`return 0;`
		609	`}`
		610
		611	`/*`
		612	`* test 2 adjacent instructions`
		613	`* and find out if inserted instructions`
		614	`* are desired to prevent stalls.`
		615	`* first instruction is a load instruction.`
		616	`*/`
		617	`int`
		618	`conflict(Sch sa, Sch sb)`
		619	`{`
		620
		621	`if(sa->set.ireg & sb->used.ireg)`
		622	`return 1;`
		623	`if(sa->set.freg & sb->used.freg)`
		624	`return 1;`
		625	`return 0;`
		626	`}`
		627
		628	`int`
		629	`compound(Prog *p)`
		630	`{`
		631	`Optab *o;`
		632
		633	`o = oplook(p);`
		634	`if(o->size != 4)`
		635	`return 1;`
		636	`if(p->to.type == D_REG && p->to.reg == REGSB)`
		637	`return 1;`
		638	`return 0;`
		639	`}`
		640
		641	`void`
		642	`dumpbits(Sch s, Dep d)`
		643	`{`
		644	`int i;`
		645
		646	`for(i=0; i<32; i++)`
		647	`if(d->ireg & (1<<i))`
		648	`Bprint(&bso, " R%d", i);`
		649	`for(i=0; i<32; i++)`
		650	`if(d->freg & (1<<i))`
		651	`Bprint(&bso, " F%d", i);`
		652	`for(i=0; i<32; i++)`
		653	`switch(d->cc & (1<<i)) {`
		654	`default:`
		655	`break;`
		656	`case E_ICC:`
		657	`Bprint(&bso, " ICC");`
		658	`break;`
		659	`case E_FCC:`
		660	`Bprint(&bso, " FCC");`
		661	`break;`
		662	`case E_MEM:`
		663	`Bprint(&bso, " MEM%d", s->size);`
		664	`break;`
		665	`case E_MEMSB:`
		666	`Bprint(&bso, " SB%d", s->size);`
		667	`break;`
		668	`case E_MEMSP:`
		669	`Bprint(&bso, " SP%d", s->size);`
		670	`break;`
		671	`}`
		672	`}`

Subversion Repositories planix.SVN

(root)/os/branches/planix-v0/sys/src/cmd/kl/sched.c – Rev 9