codegen.c 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973
  1. #ifndef NORCSID
  2. static char rcsid[] = "$Id$";
  3. #endif
  4. #include "assert.h"
  5. #include "param.h"
  6. #include "tables.h"
  7. #include "types.h"
  8. #include <cgg_cg.h>
  9. #include "data.h"
  10. #include "result.h"
  11. #include "state.h"
  12. #include "equiv.h"
  13. #include "extern.h"
  14. /*
  15. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  16. * See the copyright notice in the ACK home directory, in the file "Copyright".
  17. *
  18. * Author: Hans van Staveren
  19. */
  20. #define ALLOW_NEXTEM /* code generator is allowed new try of NEXTEM
  21. in exceptional cases */
  22. byte startupcode[] = { DO_NEXTEM };
  23. byte *nextem();
  24. unsigned costcalc();
  25. unsigned docoerc();
  26. unsigned stackupto();
  27. string tostring();
  28. string ad2str();
  29. #ifdef NDEBUG
  30. #define DEBUG(string)
  31. #else
  32. #include <stdio.h>
  33. #define DEBUG(string) {if(Debug) fprintf(stderr,"%-*d%s\n",4*level,level,string);}
  34. #endif
  35. #define BROKE() {assert(origcp!=startupcode || !paniced);DEBUG("BROKE");totalcost=INFINITY;goto doreturn;}
  36. #define CHKCOST() {if (totalcost>=costlimit) BROKE();}
  37. #ifdef TABLEDEBUG
  38. int tablelines[MAXTDBUG];
  39. int ntableline;
  40. int set_fd,set_size;
  41. short *set_val;
  42. char *set_flag;
  43. #endif
  44. unsigned codegen(codep,ply,toplevel,costlimit,forced) byte *codep; unsigned costlimit; {
  45. #ifndef NDEBUG
  46. byte *origcp=codep;
  47. static int level=0;
  48. #endif
  49. unsigned totalcost = 0;
  50. int inscoerc=0;
  51. int procarg[MAXPROCARG+1];
  52. #ifdef ALLOW_NEXTEM
  53. static int paniced;
  54. char *savebp = 0;
  55. #endif
  56. state_t state;
  57. #define SAVEST savestatus(&state)
  58. #define RESTST restorestatus(&state)
  59. #define FREEST /* nothing */
  60. #ifdef TABLEDEBUG
  61. extern char *tablename;
  62. #endif
  63. #ifndef NDEBUG
  64. assert(costlimit <= INFINITY);
  65. level++;
  66. DEBUG("Entering codegen");
  67. if (Debug > 1) fprintf(stderr, "toplevel = %d\n", toplevel);
  68. #endif
  69. for (;;) {
  70. switch( (*codep++)&037 ) {
  71. default:
  72. assert(FALSE);
  73. /* NOTREACHED */
  74. #ifdef TABLEDEBUG
  75. case DO_DLINE: {
  76. int n;
  77. getint(n,codep);
  78. tablelines[ntableline++] = n;
  79. if (ntableline>=MAXTDBUG)
  80. ntableline -= MAXTDBUG;
  81. if (set_fd)
  82. set_val[n>>4] &= ~(1<<(n&017));
  83. #ifndef NDEBUG
  84. if (Debug)
  85. fprintf(stderr,"code from \"%s\", line %d\n",tablename,n);
  86. #endif
  87. break;
  88. }
  89. #endif
  90. case DO_NEXTEM: {
  91. byte *bp;
  92. int n;
  93. unsigned mindistance,dist;
  94. register i;
  95. int cindex;
  96. int npos,pos[MAXRULE];
  97. unsigned mincost,t;
  98. DEBUG("NEXTEM");
  99. tokpatlen = 0;
  100. nallreg=0;
  101. if (toplevel) {
  102. garbage_collect();
  103. totalcost=0;
  104. } else {
  105. if (--ply <= 0)
  106. goto doreturn;
  107. }
  108. if (stackheight>MAXFSTACK-7) {
  109. #ifndef NDEBUG
  110. if (Debug)
  111. fprintf(stderr,"Fakestack overflow threatens(%d), action ...\n",stackheight);
  112. #endif
  113. totalcost += stackupto(&fakestack[6],ply,toplevel);
  114. }
  115. #ifndef ALLOW_NEXTEM
  116. bp = nextem(toplevel);
  117. #else
  118. if (toplevel) paniced=0;
  119. savebp = nextem(toplevel);
  120. panic:
  121. if (toplevel) totalcost = 0;
  122. bp = savebp;
  123. #endif
  124. if (bp == 0) {
  125. /*
  126. * No pattern found, can be pseudo or error
  127. * in table.
  128. */
  129. if (toplevel) {
  130. codep--;
  131. DEBUG("pseudo");
  132. dopseudo();
  133. } else
  134. goto doreturn;
  135. } else {
  136. #ifndef NDEBUG
  137. chkregs();
  138. #endif
  139. if (! toplevel) {
  140. ply -= emp-saveemp+1;
  141. if (ply <= 0) ply = 1;
  142. }
  143. n = *bp++;
  144. if (n==0) { /* "procedure" */
  145. int j, nargs;
  146. getint(i,bp);
  147. getint(nargs,bp);
  148. assert(nargs <= MAXPROCARG);
  149. for (j = 0; j < nargs; j++) {
  150. getint(procarg[j],bp);
  151. }
  152. bp= &pattern[i];
  153. n = *bp++;
  154. DEBUG("PROC_CALL");
  155. }
  156. assert(n>0 && n<=MAXRULE);
  157. if (n>1) {
  158. mindistance = MAXINT; npos=0;
  159. for(i=0;i<n;i++) {
  160. getint(cindex,bp);
  161. dist=distance(cindex);
  162. #ifndef NDEBUG
  163. if (Debug)
  164. fprintf(stderr,"distance of pos %d is %u\n",i,dist);
  165. #endif
  166. if (dist<=mindistance
  167. #ifdef ALLOW_NEXTEM
  168. || paniced
  169. #endif
  170. ) {
  171. if (dist<mindistance) {
  172. if(dist==0)
  173. goto gotit;
  174. npos=0;
  175. mindistance = dist;
  176. }
  177. #ifdef ALLOW_NEXTEM
  178. if (dist < MAXINT)
  179. #endif
  180. pos[npos++] = cindex;
  181. }
  182. }
  183. assert(mindistance<MAXINT);
  184. if (npos>1) {
  185. /*
  186. * More than 1 tokenpattern is a candidate.
  187. * Decision has to be made by lookahead.
  188. */
  189. SAVEST;
  190. mincost = costlimit-totalcost+1;
  191. assert(mincost <= INFINITY);
  192. for(i=0;i<npos;i++) {
  193. t=codegen(&coderules[pos[i]],ply,FALSE,
  194. costlimit<MAXINT?mincost:MAXINT,0);
  195. #ifndef NDEBUG
  196. if (Debug)
  197. fprintf(stderr,"mincost %u,cost %u,pos %d\n",mincost,t,i);
  198. #endif
  199. if (t<mincost) {
  200. mincost = t;
  201. cindex = pos[i];
  202. }
  203. RESTST;
  204. }
  205. FREEST;
  206. if (totalcost+mincost>costlimit) {
  207. BROKE();
  208. }
  209. } else {
  210. cindex = pos[0];
  211. }
  212. } else {
  213. getint(cindex,bp);
  214. }
  215. gotit:
  216. /*
  217. * Now cindex contains the code-index of the best candidate
  218. * so proceed to use it.
  219. */
  220. codep = &coderules[cindex];
  221. }
  222. break;
  223. }
  224. case DO_COERC: {
  225. DEBUG("COERC");
  226. tokpatlen=1;
  227. inscoerc=1;
  228. break;
  229. }
  230. case DO_XXMATCH:
  231. DEBUG("XXMATCH");
  232. case DO_XMATCH: {
  233. register i;
  234. int temp;
  235. DEBUG("XMATCH");
  236. tokpatlen=(codep[-1]>>5)&07;
  237. for (i=0;i<tokpatlen;i++)
  238. getint(temp,codep);
  239. break; /* match already checked by distance() */
  240. }
  241. case DO_MATCH: {
  242. register i;
  243. int j;
  244. unsigned mincost,t;
  245. token_p tp;
  246. int size,lsize;
  247. int tokexp[MAXPATLEN];
  248. int nregneeded;
  249. token_p regtp[MAXCREG];
  250. c3_p regcp[MAXCREG];
  251. rl_p regls[MAXCREG];
  252. c3_p cp,findcoerc();
  253. #ifdef MAXSPLIT
  254. int sret;
  255. #endif
  256. int stackpad = 0;
  257. struct perm *tup,*ntup,*besttup,*tuples();
  258. DEBUG("MATCH");
  259. tokpatlen=(codep[-1]>>5)&07;
  260. for(i=0;i<tokpatlen;i++)
  261. getint(tokexp[i],codep);
  262. tokexp[i] = 0;
  263. tp = &fakestack[stackheight-1];
  264. i=0;
  265. while (i<tokpatlen && tp>=fakestack) {
  266. size=tsize(tp);
  267. while (i<tokpatlen && (lsize=ssize(tokexp[i]))<=size) {
  268. size -= lsize;
  269. i++;
  270. }
  271. if (i<tokpatlen && size!=0) {
  272. totalcost += stackupto(tp,ply,toplevel);
  273. CHKCOST();
  274. break;
  275. }
  276. tp--;
  277. }
  278. tp = &fakestack[stackheight-1];
  279. i=0;
  280. while (i<tokpatlen && tp >= fakestack) {
  281. size = tsize(tp);
  282. lsize= ssize(tokexp[i]);
  283. if (size != lsize) { /* find coercion */
  284. #ifdef MAXSPLIT
  285. sret = split(tp,&tokexp[i],ply,toplevel);
  286. if (sret==0) {
  287. #endif /* MAXSPLIT */
  288. totalcost += stackupto(tp,ply,toplevel);
  289. CHKCOST();
  290. break;
  291. #ifdef MAXSPLIT
  292. }
  293. i += sret;
  294. #endif /* MAXSPLIT */
  295. } else
  296. i += 1;
  297. tp--;
  298. }
  299. nextmatch:
  300. tp = &fakestack[stackheight-1];
  301. i=0; nregneeded = 0;
  302. while (i<tokpatlen && tp>=fakestack) {
  303. if (!match(tp,&machsets[tokexp[i]],0)) {
  304. cp = findcoerc(tp, &machsets[tokexp[i]]);
  305. #ifndef NDEBUG
  306. if (Debug>1) fprintf(stderr,"findcoerc returns 0x%x at position %d\n",(unsigned)cp,i);
  307. #endif
  308. if (cp==0) {
  309. for (j=0;j<nregneeded;j++)
  310. regtp[j] -= (tp-fakestack+1);
  311. totalcost += stackupto(tp,ply,toplevel);
  312. CHKCOST();
  313. break;
  314. } else {
  315. if (cp->c3_prop<0) {
  316. totalcost+=docoerc(tp,cp,ply,toplevel,0);
  317. CHKCOST();
  318. } else {
  319. #ifndef NDEBUG
  320. if(Debug>1) fprintf(stderr,"Register of type %d needed, remembering...\n",cp->c3_prop);
  321. #endif
  322. assert(nregneeded<MAXCREG);
  323. regtp[nregneeded] = tp;
  324. regcp[nregneeded] = cp;
  325. regls[nregneeded] = curreglist;
  326. nregneeded++;
  327. }
  328. }
  329. }
  330. i++; tp--;
  331. }
  332. if (tokpatlen>stackheight) {
  333. #ifndef NDEBUG
  334. if(Debug>1) fprintf(stderr,"Pattern too long, %d with only %d items on stack\n",
  335. tokpatlen,stackheight);
  336. #endif
  337. stackpad = tokpatlen-stackheight;
  338. for (j=stackheight-1;j>=0;j--)
  339. fakestack[j+stackpad] = fakestack[j];
  340. for (j=0;j<stackpad;j++)
  341. fakestack[j].t_token=0;
  342. stackheight += stackpad;
  343. for (j=0;j<nregneeded;j++)
  344. regtp[j] += stackpad;
  345. for (tp = &fakestack[stackpad-1];i<tokpatlen && tp>=fakestack;i++,tp--) {
  346. cp = findcoerc((token_p) 0, &machsets[tokexp[i]]);
  347. if (cp==0) {
  348. for (j=0;j<nregneeded;j++)
  349. myfree((string) (regls[j]));
  350. #ifndef ALLOW_NEXTEM
  351. assert(!toplevel);
  352. BROKE();
  353. #else
  354. assert(!(toplevel&&paniced));
  355. if (paniced) goto normalfailed;
  356. totalcost = INFINITY;
  357. for (i=0;i<stackheight-stackpad;i++)
  358. fakestack[i] = fakestack[i+stackpad];
  359. stackheight -= stackpad;
  360. goto doreturn;
  361. #endif
  362. }
  363. if (cp->c3_prop<0) {
  364. totalcost+=docoerc(tp,cp,ply,toplevel,0);
  365. CHKCOST();
  366. } else {
  367. assert(nregneeded<MAXCREG);
  368. regtp[nregneeded] = tp;
  369. regcp[nregneeded] = cp;
  370. regls[nregneeded] = curreglist;
  371. nregneeded++;
  372. }
  373. }
  374. } else
  375. stackpad=0;
  376. assert(i==tokpatlen);
  377. if (nregneeded==0)
  378. break;
  379. SAVEST;
  380. mincost=costlimit-totalcost+1;
  381. tup = tuples(regls,nregneeded);
  382. besttup=0;
  383. for (; tup != 0; tup = ntup) {
  384. #ifndef NDEBUG
  385. if(Debug>1) { fprintf(stderr,"Next tuple %d,%d,%d,%d\n",
  386. tup->p_rar[0],
  387. tup->p_rar[1],
  388. tup->p_rar[2],
  389. tup->p_rar[3]);
  390. fprintf(stderr, "totalcost = %u, costlimit = %u, mincost = %u\n",
  391. totalcost, costlimit, mincost);
  392. }
  393. #endif
  394. ntup = tup->p_next;
  395. for (i=0,t=0;i<nregneeded && t<mincost; i++)
  396. t += docoerc(regtp[i],regcp[i],ply,FALSE,tup->p_rar[i]);
  397. #ifndef NDEBUG
  398. if (Debug > 1) fprintf(stderr, "cost after coercions: %u\n", t);
  399. #endif
  400. if ( t<mincost && tokpatlen<=stackheight ) {
  401. #ifndef NDEBUG
  402. if (Debug>2)
  403. fprintf(stderr,"Continuing match after coercions\n");
  404. #endif
  405. t += codegen(codep,ply,FALSE,mincost<MAXINT?mincost-t:MAXINT,0);
  406. }
  407. if ( t<mincost && tokpatlen<=stackheight ) {
  408. mincost = t;
  409. besttup = tup;
  410. } else
  411. myfree((string) tup);
  412. RESTST;
  413. }
  414. FREEST;
  415. for (i=0;i<nregneeded;i++)
  416. myfree((string)(regls[i]));
  417. if (totalcost+mincost>costlimit) {
  418. if (besttup)
  419. myfree((string)besttup);
  420. normalfailed: if (stackpad!=tokpatlen) {
  421. if (stackpad) {
  422. for (i=0;i<stackheight-stackpad;i++)
  423. fakestack[i] = fakestack[i+stackpad];
  424. stackheight -= stackpad;
  425. if (costlimit<MAXINT)
  426. BROKE();
  427. totalcost += stackupto(&fakestack[stackheight-1],ply,toplevel);
  428. } else
  429. totalcost += stackupto(fakestack,ply,toplevel);
  430. CHKCOST();
  431. goto nextmatch;
  432. }
  433. totalcost += mincost;
  434. for (i=0;i<stackheight-stackpad;i++)
  435. fakestack[i] = fakestack[i+stackpad];
  436. stackheight -= stackpad;
  437. BROKE();
  438. }
  439. for (i=0;i<nregneeded;i++)
  440. totalcost += docoerc(regtp[i],regcp[i],ply,toplevel,besttup->p_rar[i]);
  441. assert(totalcost <= costlimit);
  442. myfree((string)besttup);
  443. break;
  444. }
  445. case DO_TOSTACK:
  446. case DO_REMOVE: {
  447. int texpno,nodeno;
  448. token_p tp;
  449. struct reginfo *rp;
  450. int doremove = (codep[-1] & 037) == DO_REMOVE;
  451. extern int allsetno;
  452. DEBUG(doremove ? "REMOVE" : "TOSTACK");
  453. if (codep[-1]&32) {
  454. getint(texpno,codep);
  455. getint(nodeno,codep);
  456. } else {
  457. getint(texpno,codep);
  458. nodeno=0;
  459. }
  460. if (texpno == allsetno) {
  461. totalcost += stackupto(&fakestack[stackheight-tokpatlen-1],ply,toplevel);
  462. CHKCOST();
  463. if (doremove) for (rp=machregs;rp<machregs+NREGS;rp++)
  464. rp->r_contents.t_token=0;
  465. break;
  466. }
  467. for (tp= &fakestack[stackheight-tokpatlen-1];tp>=&fakestack[0];tp--)
  468. if (match(tp,&machsets[texpno],nodeno)) {
  469. /* investigate possible coercion to register */
  470. totalcost += stackupto(tp,ply,toplevel);
  471. CHKCOST();
  472. break;
  473. }
  474. if (doremove) for (rp=machregs;rp<machregs+NREGS;rp++) {
  475. if (rp->r_contents.t_token != 0 &&
  476. match(&rp->r_contents,&machsets[texpno],nodeno)) {
  477. #ifndef NDEBUG
  478. if (Debug > 1) fprintf(stderr, "killing reg %ld (%s)\n", (long)(rp-machregs), rp->r_repr ? codestrings[rp->r_repr] : "cc");
  479. #endif
  480. rp->r_contents.t_token=0;
  481. }
  482. }
  483. break;
  484. }
  485. case DO_KILLREG:
  486. case DO_RREMOVE: { /* register remove */
  487. register i;
  488. int nodeno;
  489. token_p tp;
  490. tkdef_p tdp;
  491. result_t result;
  492. int dokill = (codep[-1] & 037) == DO_KILLREG;
  493. DEBUG(dokill ? "KILLREG" : "RREMOVE");
  494. getint(nodeno,codep);
  495. compute(&enodes[nodeno], &result);
  496. if (result.e_typ!=EV_REG)
  497. break;
  498. if ( in_stack(result.e_v.e_reg) ) BROKE() ; /* Check aside-stack */
  499. if (dokill) {
  500. /* kill register, and kill condition codes if they are set to
  501. this register
  502. */
  503. machregs[result.e_v.e_reg].r_contents.t_token = 0;
  504. if (machregs[0].r_contents.t_token == -1 &&
  505. machregs[0].r_contents.t_att[0].ar == result.e_v.e_reg) {
  506. machregs[0].r_contents.t_token = 0;
  507. }
  508. }
  509. for (tp= &fakestack[stackheight-tokpatlen-1];tp>=&fakestack[0];tp--)
  510. if (tp->t_token==-1) {
  511. if(tp->t_att[0].ar==result.e_v.e_reg)
  512. goto gotone;
  513. } else {
  514. tdp = &tokens[tp->t_token];
  515. for(i=0;i<TOKENSIZE;i++)
  516. if (tdp->t_type[i]==EV_REG &&
  517. tp->t_att[i].ar==result.e_v.e_reg)
  518. goto gotone;
  519. }
  520. break;
  521. gotone:
  522. /* investigate possible coercion to register */
  523. totalcost += stackupto(tp,ply,toplevel);
  524. CHKCOST();
  525. break;
  526. }
  527. case DO_DEALLOCATE: {
  528. register i;
  529. tkdef_p tdp;
  530. int tinstno;
  531. token_t token;
  532. DEBUG("DEALLOCATE");
  533. getint(tinstno,codep);
  534. instance(tinstno,&token);
  535. if (token.t_token==-1)
  536. chrefcount(token.t_att[0].ar,-1,TRUE);
  537. else {
  538. tdp= &tokens[token.t_token];
  539. for (i=0;i<TOKENSIZE;i++)
  540. if (tdp->t_type[i]==EV_REG)
  541. chrefcount(token.t_att[i].ar,-1,TRUE);
  542. }
  543. break;
  544. }
  545. case DO_REALLOCATE: {
  546. struct reginfo *rp;
  547. DEBUG("REALLOCATE");
  548. for(rp=machregs+1;rp<machregs+NREGS;rp++)
  549. if(rp->r_tcount) {
  550. rp->r_refcount -= rp->r_tcount;
  551. rp->r_tcount = 0;
  552. }
  553. break;
  554. }
  555. case DO_ALLOCATE: {
  556. register i;
  557. int j;
  558. int tinstno;
  559. int npos,npos2,pos[NREGS],pos2[NREGS];
  560. unsigned mincost,t;
  561. struct reginfo *rp,**rpp;
  562. token_t token,token2;
  563. int propno;
  564. int exactmatch;
  565. int decision;
  566. if (codep[-1]&32) {
  567. getint(propno,codep);
  568. getint(tinstno,codep);
  569. DEBUG("ALLOCATE,INIT");
  570. } else {
  571. getint(propno,codep);
  572. tinstno=0;
  573. DEBUG("ALLOCATE,EMPTY");
  574. }
  575. instance(tinstno,&token);
  576. if (!forced) {
  577. do {
  578. npos=exactmatch=0;
  579. for(rpp=reglist[propno];rp= *rpp; rpp++)
  580. if (getrefcount((int)(rp-machregs), FALSE)==0) {
  581. pos[npos++] = rp-machregs;
  582. if (eqtoken(&rp->r_contents,&token))
  583. pos2[exactmatch++] = rp-machregs;
  584. }
  585. /*
  586. * Now pos[] contains all free registers with desired
  587. * property. If none then some stacking has to take place.
  588. */
  589. if (npos==0) {
  590. if (stackheight<=tokpatlen) {
  591. if (!toplevel) {
  592. BROKE();
  593. } else {
  594. if (paniced)
  595. fatal("No regs available");
  596. totalcost += stackupto( &fakestack[0],ply,toplevel);
  597. goto panic;
  598. }
  599. }
  600. totalcost += stackupto( &fakestack[0],ply,toplevel);
  601. CHKCOST();
  602. }
  603. } while (npos==0);
  604. if (!exactmatch && tinstno!=0) {
  605. /*
  606. * No exact match, but we were looking for a particular
  607. * token. Now try to find registers of which no
  608. * known contents is available (the others might still
  609. * be useful).
  610. */
  611. for (i=0;i<npos;i++)
  612. if (machregs[pos[i]].r_contents.t_token == 0) {
  613. pos2[exactmatch++] = pos[i];
  614. }
  615. }
  616. if (!exactmatch) {
  617. npos2=npos;
  618. for(i=0;i<npos;i++)
  619. pos2[i]=pos[i];
  620. } else {
  621. /*
  622. * Now we are reducing the number of possible registers.
  623. * We take only one equally likely register out of every
  624. * equivalence class as given by set of properties.
  625. */
  626. npos2=0;
  627. for(i=0;i<exactmatch;i++) {
  628. pos2[npos2++] = pos2[i];
  629. for(j=0;j<npos2-1;j++)
  630. if (eqregclass(pos2[j],pos2[i])) {
  631. npos2--;
  632. break;
  633. }
  634. }
  635. }
  636. /*
  637. * Now pos2[] contains all possibilities to try, if more than
  638. * one, lookahead is necessary.
  639. */
  640. token2.t_token= -1;
  641. for (i=1;i<TOKENSIZE;i++)
  642. token2.t_att[i].aw=0;
  643. decision=pos2[0];
  644. if (npos2!=1) {
  645. SAVEST;
  646. mincost=costlimit-totalcost+1;
  647. for(j=0;j<npos2;j++) {
  648. chrefcount(pos2[j],1,FALSE);
  649. token2.t_att[0].ar=pos2[j];
  650. allreg[nallreg++] = pos2[j];
  651. if (token.t_token != 0)
  652. t=move(&token,&token2,ply,FALSE,mincost);
  653. else {
  654. t = 0;
  655. erasereg(pos2[j]);
  656. }
  657. if (t<mincost)
  658. t += codegen(codep,ply,FALSE,mincost<MAXINT?mincost-t:MAXINT,0);
  659. if (t<mincost) {
  660. mincost=t;
  661. decision=pos2[j];
  662. }
  663. RESTST;
  664. }
  665. FREEST;
  666. if (totalcost+mincost>costlimit)
  667. BROKE();
  668. }
  669. } else {
  670. decision = forced;
  671. if (getrefcount(decision, FALSE)!=0)
  672. BROKE();
  673. token2.t_token = -1;
  674. }
  675. chrefcount(decision,1,FALSE);
  676. token2.t_att[0].ar=decision;
  677. if (token.t_token != 0) {
  678. totalcost+=move(&token,&token2,ply,toplevel,MAXINT);
  679. CHKCOST();
  680. } else
  681. erasereg(decision);
  682. allreg[nallreg++]=decision;
  683. break;
  684. }
  685. case DO_INSTR: {
  686. register i;
  687. int n;
  688. int tinstno;
  689. token_t token;
  690. int stringno;
  691. DEBUG("INSTR");
  692. n=((codep[-1]>>5)&07);
  693. getint(stringno,codep);
  694. if (toplevel) {
  695. swtxt();
  696. if (stringno>10000) {
  697. assert(stringno < 100001 + MAXPROCARG);
  698. genstr(procarg[stringno-10001]);
  699. } else
  700. genstr(stringno);
  701. }
  702. for(i=0;i<n;i++) {
  703. getint(tinstno,codep);
  704. instance(tinstno,&token);
  705. if (toplevel)
  706. prtoken(&token,i==0 ? ' ' : ',');
  707. if (token.t_token>0)
  708. totalcost += tokens[token.t_token].t_cost.ct_space;
  709. }
  710. if (toplevel)
  711. gennl();
  712. CHKCOST();
  713. break;
  714. }
  715. case DO_MOVE: {
  716. int tinstno;
  717. token_t token,token2;
  718. DEBUG("MOVE");
  719. getint(tinstno,codep);
  720. instance(tinstno,&token);
  721. getint(tinstno,codep);
  722. instance(tinstno,&token2);
  723. totalcost += move(&token,&token2,ply,toplevel,costlimit-totalcost+1);
  724. CHKCOST();
  725. break;
  726. }
  727. case DO_TEST: {
  728. int tinstno;
  729. token_t token;
  730. DEBUG("TEST");
  731. getint(tinstno,codep);
  732. instance(tinstno,&token);
  733. totalcost += test(&token,ply,toplevel,costlimit-totalcost+1);
  734. CHKCOST();
  735. break;
  736. }
  737. case DO_SETCC: {
  738. int tinstno;
  739. token_t token;
  740. DEBUG("SETCC");
  741. getint(tinstno,codep);
  742. instance(tinstno,&token);
  743. setcc(&token);
  744. break;
  745. }
  746. case DO_ERASE: {
  747. int nodeno;
  748. result_t result;
  749. DEBUG("ERASE");
  750. getint(nodeno,codep);
  751. compute(&enodes[nodeno], &result);
  752. assert(result.e_typ!=EV_INT && result.e_typ!=EV_ADDR);
  753. if (result.e_typ==EV_REG)
  754. erasereg(result.e_v.e_reg);
  755. break;
  756. }
  757. case DO_TOKREPLACE: {
  758. register i;
  759. int tinstno;
  760. int repllen;
  761. token_t reptoken[MAXREPLLEN];
  762. DEBUG("TOKREPLACE");
  763. assert(stackheight>=tokpatlen);
  764. repllen=(codep[-1]>>5)&07;
  765. #ifndef NDEBUG
  766. if (Debug>2)
  767. fprintf(stderr,"Stackheight=%d, tokpatlen=%d, repllen=%d %s\n",
  768. stackheight,tokpatlen,repllen,inscoerc ? "(inscoerc)":"");
  769. #endif
  770. for(i=0;i<repllen;i++) {
  771. getint(tinstno,codep);
  772. instance(tinstno,&reptoken[i]);
  773. tref(&reptoken[i],1);
  774. }
  775. for(i=0;i<tokpatlen;i++) {
  776. if (!inscoerc)
  777. tref(&fakestack[stackheight-1],-1);
  778. stackheight--;
  779. }
  780. for (i=0;i<repllen;i++) {
  781. assert(stackheight<MAXFSTACK);
  782. fakestack[stackheight++] = reptoken[i];
  783. }
  784. for(i=0;i<nallreg;i++)
  785. chrefcount(allreg[i],-1,FALSE);
  786. break;
  787. }
  788. case DO_EMREPLACE: {
  789. register i;
  790. int j;
  791. int nodeno;
  792. result_t result[MAXEMREPLLEN];
  793. int emrepllen,eminstr;
  794. DEBUG("EMREPLACE");
  795. emrepllen=(codep[-1]>>5)&07;
  796. j=emp-emlines;
  797. if (emrepllen>j) {
  798. assert(nemlines+emrepllen-j<MAXEMLINES);
  799. for (i=nemlines;i>=0;i--)
  800. emlines[i+emrepllen-j] = emlines[i];
  801. nemlines += emrepllen-j;
  802. emp += emrepllen-j;
  803. }
  804. emp -= emrepllen;
  805. for (i=0;i<emrepllen;i++) {
  806. getint(eminstr,codep);
  807. getint(nodeno,codep);
  808. emp[i].em_instr = eminstr;
  809. compute(&enodes[nodeno], &result[i]);
  810. }
  811. for (i=0;i<emrepllen;i++) {
  812. switch(result[i].e_typ) {
  813. default:
  814. assert(FALSE);
  815. case 0:
  816. emp[i].em_optyp = OPNO;
  817. emp[i].em_soper = 0;
  818. break;
  819. case EV_INT:
  820. emp[i].em_optyp = OPINT;
  821. emp[i].em_soper = tostring(result[i].e_v.e_con);
  822. emp[i].em_u.em_ioper = result[i].e_v.e_con;
  823. break;
  824. case EV_ADDR:
  825. emp[i].em_optyp = OPSYMBOL;
  826. emp[i].em_soper = ad2str(result[i].e_v.e_addr);
  827. break;
  828. }
  829. }
  830. if (!toplevel) {
  831. ply += emrepllen;
  832. #ifndef NDEBUG
  833. if (Debug > 4)
  834. fprintf(stderr, "ply becomes %d\n", ply);
  835. #endif
  836. }
  837. break;
  838. }
  839. case DO_COST: {
  840. cost_t cost;
  841. DEBUG("COST");
  842. getint(cost.ct_space,codep);
  843. getint(cost.ct_time,codep);
  844. totalcost += costcalc(cost);
  845. CHKCOST();
  846. break;
  847. }
  848. #ifdef REGVARS
  849. case DO_PRETURN: {
  850. if (toplevel) {
  851. swtxt();
  852. regreturn(); /* in mach.c */
  853. }
  854. break;
  855. }
  856. #endif
  857. case DO_RETURN:
  858. DEBUG("RETURN");
  859. assert(origcp!=startupcode);
  860. #ifndef NDEBUG
  861. level--;
  862. #endif
  863. return(totalcost);
  864. #ifdef USE_TES
  865. case DO_LABDEF: {
  866. int index;
  867. DEBUG("LABDEF");
  868. getint(index,codep);
  869. if (toplevel) {
  870. swtxt();
  871. printlabel(index);
  872. }
  873. break;
  874. }
  875. #endif
  876. }
  877. }
  878. doreturn:
  879. #ifdef ALLOW_NEXTEM
  880. if (toplevel && totalcost == INFINITY && ! paniced) {
  881. DEBUG("PANIC!");
  882. totalcost += stackupto(&fakestack[stackheight-1], ply, toplevel);
  883. #ifndef NDEBUG
  884. if (Debug > 2)
  885. fprintf(stderr, "Stackheight = %d\n", stackheight);
  886. #endif
  887. paniced = 1;
  888. tokpatlen = 0;
  889. goto panic;
  890. }
  891. #endif
  892. #ifndef NDEBUG
  893. level--;
  894. #endif
  895. return(totalcost);
  896. }
  897. readcodebytes() {
  898. #ifndef CODEINC
  899. register fd;
  900. extern int ncodebytes;
  901. if ((fd=open("code",0))<0) {
  902. error("Can't open code");
  903. }
  904. if (read(fd,coderules,ncodebytes)!=ncodebytes) {
  905. error("Short read from code");
  906. }
  907. close(fd);
  908. #endif
  909. }
  910. #ifdef TABLEDEBUG
  911. initlset(f) char *f; {
  912. extern char *myalloc();
  913. set_flag = f;
  914. if ((set_fd=open(f+1,2))<0)
  915. error("Can't open %s rw",f+1);
  916. read(set_fd,&set_size,sizeof(int));
  917. set_val=( short *) myalloc(set_size);
  918. read(set_fd,set_val,set_size);
  919. }
  920. termlset() {
  921. if (set_fd) {
  922. lseek(set_fd,(long) sizeof(int),0);
  923. write(set_fd,set_val,set_size);
  924. close(set_fd);
  925. if (set_flag[0]=='u') {
  926. register i;
  927. fprintf(stderr,"Unused code rules:\n\n");
  928. for(i=0;i<8*set_size;i++)
  929. if(set_val[i>>4]&(1<<(i&017)))
  930. fprintf(stderr,"\"%s\", line %d\n",tablename,i);
  931. }
  932. }
  933. }
  934. #endif