codegen.c 21 KB

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