subr.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537
  1. #ifndef NORCSID
  2. static char rcsid[] = "$Id$";
  3. #endif
  4. #include <stdlib.h>
  5. #include "assert.h"
  6. #include <stdio.h>
  7. #include "param.h"
  8. #include "tables.h"
  9. #include "types.h"
  10. #include <cg_pattern.h>
  11. #include "data.h"
  12. #include "result.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. extern string myalloc();
  21. unsigned codegen();
  22. match(tp,tep,optexp) register token_p tp; register set_p tep; {
  23. register bitno;
  24. token_p ct;
  25. result_t result;
  26. if (tp->t_token == -1) { /* register frame */
  27. bitno = tp->t_att[0].ar+1;
  28. if (tep->set_val[bitno>>4]&(1<<(bitno&017)))
  29. if (tep->set_val[0]&1 || getrefcount(tp->t_att[0].ar, FALSE)<=1)
  30. goto oklabel;
  31. return(0);
  32. } else { /* token frame */
  33. bitno = tp->t_token+NREGS+1;
  34. if ((tep->set_val[bitno>>4]&(1<<(bitno&017)))==0)
  35. return(0);
  36. }
  37. oklabel:
  38. if (optexp==0)
  39. return(1);
  40. ct=curtoken;
  41. curtoken=tp;
  42. result=compute(&enodes[optexp]);
  43. curtoken=ct;
  44. return(result.e_v.e_con);
  45. }
  46. instance(instno,token) register token_p token; {
  47. register inst_p inp;
  48. int i;
  49. token_p tp;
  50. struct reginfo *rp;
  51. int regno;
  52. result_t result;
  53. if (instno==0) {
  54. token->t_token = 0;
  55. for(i=0;i<TOKENSIZE;i++)
  56. token->t_att[i].aw=0;
  57. return;
  58. }
  59. inp= &tokeninstances[instno];
  60. switch(inp->in_which) {
  61. default:
  62. assert(FALSE);
  63. case IN_COPY:
  64. tp= &fakestack[stackheight-inp->in_info[0]];
  65. if (inp->in_info[1]==0) {
  66. *token = *tp;
  67. } else {
  68. token->t_token= -1;
  69. #if MAXMEMBERS!=0
  70. if (tp->t_token == -1) {
  71. rp = &machregs[tp->t_att[0].ar];
  72. token->t_att[0].ar=rp->r_members[inp->in_info[1]-1];
  73. } else {
  74. #endif
  75. assert(tokens[tp->t_token].t_type[inp->in_info[1]-1] == EV_REG);
  76. token->t_att[0].ar=tp->t_att[inp->in_info[1]-1].ar;
  77. #if MAXMEMBERS!=0
  78. }
  79. #endif
  80. }
  81. return;
  82. case IN_RIDENT:
  83. token->t_token= -1;
  84. token->t_att[0].ar= inp->in_info[0];
  85. return;
  86. #ifdef REGVARS
  87. case IN_REGVAR:
  88. result=compute(&enodes[inp->in_info[0]]);
  89. i=isregvar((long)result.e_v.e_con);
  90. assert(i>0);
  91. token->t_token= -1;
  92. token->t_att[0].ar = i;
  93. return;
  94. #endif
  95. case IN_ALLOC:
  96. token->t_token= -1;
  97. regno=allreg[inp->in_info[0]];
  98. #if MAXMEMBERS!=0
  99. if (inp->in_info[1])
  100. regno=machregs[regno].r_members[inp->in_info[1]-1];
  101. #endif
  102. token->t_att[0].ar = regno;
  103. return;
  104. case IN_DESCR:
  105. token->t_token=inp->in_info[0];
  106. for (i=0;i<TOKENSIZE;i++)
  107. if (inp->in_info[i+1]==0) {
  108. assert(tokens[token->t_token].t_type[i]==0);
  109. token->t_att[i].aw=0;
  110. } else {
  111. result=compute(&enodes[inp->in_info[i+1]]);
  112. assert(tokens[token->t_token].t_type[i]==result.e_typ);
  113. if (result.e_typ==EV_INT)
  114. token->t_att[i].aw=result.e_v.e_con;
  115. else if (result.e_typ==EV_STR)
  116. token->t_att[i].as= result.e_v.e_str;
  117. else
  118. token->t_att[i].ar=result.e_v.e_reg;
  119. }
  120. return;
  121. }
  122. }
  123. cinstance(instno,token,tp,regno) register token_p token,tp; {
  124. register inst_p inp;
  125. int i;
  126. struct reginfo *rp;
  127. result_t result;
  128. int sh; /* saved stackheight */
  129. assert(instno!=0);
  130. inp= &tokeninstances[instno];
  131. switch(inp->in_which) {
  132. default:
  133. assert(FALSE);
  134. case IN_COPY:
  135. assert(inp->in_info[0] == 1);
  136. if (inp->in_info[1]==0) {
  137. *token = *tp;
  138. } else {
  139. token->t_token= -1;
  140. #if MAXMEMBERS!=0
  141. if (tp->t_token == -1) {
  142. rp = &machregs[tp->t_att[0].ar];
  143. token->t_att[0].ar=rp->r_members[inp->in_info[1]-1];
  144. } else {
  145. #endif
  146. assert(tokens[tp->t_token].t_type[inp->in_info[1]-1] == EV_REG);
  147. token->t_att[0].ar=tp->t_att[inp->in_info[1]-1].ar;
  148. #if MAXMEMBERS!=0
  149. }
  150. #endif
  151. }
  152. return;
  153. case IN_RIDENT:
  154. token->t_token= -1;
  155. token->t_att[0].ar= inp->in_info[0];
  156. return;
  157. case IN_ALLOC:
  158. token->t_token= -1;
  159. assert(inp->in_info[0]==0);
  160. #if MAXMEMBERS!=0
  161. if (inp->in_info[1])
  162. regno=machregs[regno].r_members[inp->in_info[1]-1];
  163. #endif
  164. token->t_att[0].ar = regno;
  165. return;
  166. case IN_DESCR:
  167. sh = stackheight;
  168. stackheight = tp - fakestack + 1;
  169. token->t_token=inp->in_info[0];
  170. for (i=0;i<TOKENSIZE;i++)
  171. if (inp->in_info[i+1]==0) {
  172. assert(tokens[token->t_token].t_type[i]==0);
  173. token->t_att[i].aw=0;
  174. } else {
  175. result=compute(&enodes[inp->in_info[i+1]]);
  176. assert(tokens[token->t_token].t_type[i]==result.e_typ);
  177. if (result.e_typ==EV_INT)
  178. token->t_att[i].aw=result.e_v.e_con;
  179. else if (result.e_typ==EV_STR)
  180. token->t_att[i].as= result.e_v.e_str;
  181. else
  182. token->t_att[i].ar=result.e_v.e_reg;
  183. }
  184. stackheight = sh;
  185. return;
  186. }
  187. }
  188. eqtoken(tp1,tp2) token_p tp1,tp2; {
  189. register i;
  190. register tkdef_p tdp;
  191. if (tp1->t_token!=tp2->t_token)
  192. return(0);
  193. if (tp1->t_token==0)
  194. return(1);
  195. if (tp1->t_token==-1) {
  196. if (tp1->t_att[0].ar!=tp2->t_att[0].ar)
  197. return(0);
  198. return(1);
  199. }
  200. tdp = &tokens[tp1->t_token];
  201. for (i=0;i<TOKENSIZE;i++)
  202. switch(tdp->t_type[i]) {
  203. default:
  204. return(1);
  205. case EV_INT:
  206. if (tp1->t_att[i].aw != tp2->t_att[i].aw)
  207. return(0);
  208. break;
  209. case EV_REG:
  210. if (tp1->t_att[i].ar != tp2->t_att[i].ar)
  211. return(0);
  212. break;
  213. case EV_STR:
  214. if (strcmp(tp1->t_att[i].as, tp2->t_att[i].as))
  215. return(0);
  216. break;
  217. }
  218. return(1);
  219. }
  220. distance(cindex) {
  221. register char *bp;
  222. register i;
  223. register token_p tp;
  224. int tokexp,tpl;
  225. int expsize,toksize,exact;
  226. int xsekt=0;
  227. bp = &coderules[cindex];
  228. switch( (*bp)&037 ) {
  229. default:
  230. return(stackheight==0 ? 0 : 100);
  231. case DO_MATCH:
  232. break;
  233. case DO_XXMATCH:
  234. xsekt++;
  235. case DO_XMATCH:
  236. xsekt++;
  237. break;
  238. }
  239. tpl= ((*bp++)>>5)&07;
  240. if (stackheight < tpl) {
  241. if (xsekt)
  242. return(MAXINT);
  243. tpl = stackheight;
  244. } else
  245. if (stackheight != tpl && xsekt==2)
  246. return(MAXINT);
  247. exact=0;
  248. tp= &fakestack[stackheight-1];
  249. for (i=0;i<tpl;i++,tp--) {
  250. getint(tokexp,bp);
  251. if (!match(tp, &machsets[tokexp], 0)) {
  252. if (xsekt)
  253. return(MAXINT);
  254. expsize = ssize(tokexp);
  255. toksize = tsize(tp);
  256. if (expsize>toksize)
  257. return(100);
  258. if (expsize<toksize)
  259. return(99-i);
  260. } else
  261. exact++;
  262. }
  263. if (exact==tpl) {
  264. if (xsekt)
  265. return(0);
  266. return(10-exact);
  267. }
  268. return(20-exact);
  269. }
  270. unsigned costcalc(cost) cost_t cost; {
  271. result_t result1,result2;
  272. extern unsigned cc1,cc2,cc3,cc4;
  273. result1=compute(&enodes[cost.c_size]);
  274. result2=compute(&enodes[cost.c_time]);
  275. assert(result1.e_typ == EV_INT && result2.e_typ == EV_INT);
  276. return(result1.e_v.e_con*cc1/cc2 + result2.e_v.e_con*cc3/cc4);
  277. }
  278. ssize(tokexpno) {
  279. return(machsets[tokexpno].set_size);
  280. }
  281. tsize(tp) register token_p tp; {
  282. if (tp->t_token==-1)
  283. return(machregs[tp->t_att[0].ar].r_size);
  284. return(tokens[tp->t_token].t_size);
  285. }
  286. #ifdef MAXSPLIT
  287. instsize(tinstno,tp) token_p tp; {
  288. inst_p inp;
  289. struct reginfo *rp;
  290. inp = &tokeninstances[tinstno];
  291. switch(inp->in_which) {
  292. default:
  293. assert(FALSE);
  294. case IN_COPY:
  295. assert(inp->in_info[0]==1);
  296. #if MAXMEMBERS!=0
  297. if (inp->in_info[1]==0)
  298. #endif
  299. return(tsize(tp));
  300. #if MAXMEMBERS!=0
  301. else {
  302. assert(tp->t_token == -1);
  303. rp = &machregs[tp->t_att[0].ar];
  304. return(machregs[rp->r_members[inp->in_info[1]-1]].r_size);
  305. }
  306. #endif
  307. case IN_RIDENT:
  308. return(machregs[inp->in_info[0]].r_size);
  309. case IN_ALLOC:
  310. assert(FALSE); /* cannot occur in splitting coercion */
  311. case IN_DESCR:
  312. return(tokens[inp->in_info[0]].t_size);
  313. }
  314. }
  315. #endif /* MAXSPLIT */
  316. tref(tp,amount) register token_p tp; {
  317. register i;
  318. register tkdef_p tdp;
  319. if (tp->t_token==-1)
  320. chrefcount(tp->t_att[0].ar,amount,FALSE);
  321. else {
  322. tdp= &tokens[tp->t_token];
  323. for(i=0;i<TOKENSIZE;i++)
  324. if (tdp->t_type[i]==EV_REG)
  325. chrefcount(tp->t_att[i].ar,amount,FALSE);
  326. }
  327. }
  328. #define MAXSAVE 10
  329. #ifdef MAXSPLIT
  330. split(tp,ip,ply,toplevel) token_p tp; int *ip; {
  331. c2_p cp;
  332. token_t savestack[MAXSAVE];
  333. int ok;
  334. register i;
  335. int diff;
  336. token_p stp;
  337. int tpl;
  338. for (cp=c2coercs;cp< &c2coercs[NC2]; cp++) {
  339. if (!match(tp,&machsets[cp->c2_texpno],0))
  340. continue;
  341. ok=1;
  342. for (i=0; ok && i<cp->c2_nsplit;i++) {
  343. if (ip[i]==0)
  344. goto found;
  345. if (instsize(cp->c2_repl[i],tp) != ssize(ip[i]))
  346. ok=0;
  347. }
  348. goto found;
  349. }
  350. return(0);
  351. found:
  352. assert(stackheight+cp->c2_nsplit-1<MAXFSTACK);
  353. stp = &fakestack[stackheight-1];
  354. diff = stp - tp;
  355. assert(diff<=MAXSAVE);
  356. for (i=1;i<=diff;i++)
  357. savestack[i-1] = tp[i]; /* save top of stack */
  358. stackheight -= diff;
  359. tpl = tokpatlen;
  360. tokpatlen = 1;
  361. codegen(&coderules[cp->c2_codep],ply,toplevel,MAXINT,0);
  362. tokpatlen = tpl;
  363. for (i=0;i<diff;i++) /* restore top of stack */
  364. fakestack[stackheight++] = savestack[i];
  365. return(cp->c2_nsplit);
  366. }
  367. #endif /* MAXSPLIT */
  368. unsigned docoerc(tp,cp,ply,toplevel,forced) token_p tp; c3_p cp; {
  369. token_t savestack[MAXSAVE];
  370. token_p stp;
  371. int i,diff;
  372. unsigned cost;
  373. int tpl; /* saved tokpatlen */
  374. stp = &fakestack[stackheight-1];
  375. diff = stp -tp;
  376. assert(diff<=MAXSAVE);
  377. for (i=1;i<=diff;i++)
  378. savestack[i-1] = tp[i];
  379. stackheight -= diff;
  380. tpl = tokpatlen;
  381. tokpatlen = 1;
  382. cost = codegen(&coderules[cp->c3_codep],ply,toplevel,MAXINT,forced);
  383. tokpatlen = tpl;
  384. for (i=0;i<diff;i++)
  385. fakestack[stackheight++] = savestack[i];
  386. nallreg = 0;
  387. return(cost);
  388. }
  389. unsigned stackupto(limit,ply,toplevel) token_p limit; {
  390. token_t savestack[MAXFSTACK];
  391. token_p stp;
  392. int i,diff;
  393. int tpl; /* saved tokpatlen */
  394. int nareg; /* saved nareg */
  395. int areg[MAXALLREG];
  396. c1_p cp;
  397. register token_p tp;
  398. unsigned totalcost=0;
  399. struct reginfo *rp,**rpp;
  400. for (tp=fakestack;tp<=limit;limit--) {
  401. for (cp=c1coercs;cp< &c1coercs[NC1]; cp++) {
  402. if (match(tp,&machsets[cp->c1_texpno],cp->c1_expr)) {
  403. if (cp->c1_prop>=0) {
  404. for (rpp=reglist[cp->c1_prop];
  405. (rp = *rpp)!=0 &&
  406. getrefcount((int)(rp-machregs), TRUE)!=0;
  407. rpp++)
  408. ;
  409. if (rp==0)
  410. continue;
  411. /* look for other possibility */
  412. }
  413. stp = &fakestack[stackheight-1];
  414. diff = stp -tp;
  415. assert(diff<=MAXFSTACK);
  416. for (i=1;i<=diff;i++)
  417. savestack[i-1] = tp[i];
  418. stackheight -= diff;
  419. tpl = tokpatlen;
  420. tokpatlen = 1;
  421. nareg = nallreg;
  422. for (i=0;i<nareg;i++)
  423. areg[i] = allreg[i];
  424. if (cp->c1_prop>=0) {
  425. nallreg=1; allreg[0] = rp-machregs;
  426. chrefcount(allreg[0],1,FALSE);
  427. } else
  428. nallreg=0;
  429. totalcost+= codegen(&coderules[cp->c1_codep],ply,toplevel,MAXINT,0);
  430. totalcost+= costcalc(cp->c1_cost);
  431. tokpatlen = tpl;
  432. for (i=0;i<diff;i++)
  433. fakestack[stackheight++] = savestack[i];
  434. nallreg=nareg;
  435. for (i=0;i<nareg;i++)
  436. allreg[i] = areg[i];
  437. goto contin;
  438. }
  439. }
  440. assert(FALSE);
  441. contin: ;
  442. }
  443. return(totalcost);
  444. }
  445. c3_p findcoerc(tp,tep) token_p tp; set_p tep; {
  446. register c3_p cp;
  447. token_t rtoken;
  448. register i;
  449. register struct reginfo **rpp;
  450. for (cp=c3coercs;cp< &c3coercs[NC3]; cp++) {
  451. if (tp!=(token_p) 0) {
  452. if (!match(tp,&machsets[cp->c3_texpno],0))
  453. continue;
  454. } else {
  455. if (cp->c3_texpno!=0)
  456. continue;
  457. }
  458. if (cp->c3_prop==0) { /* no reg needed */
  459. cinstance(cp->c3_repl,&rtoken,tp,0);
  460. if (match(&rtoken,tep,0))
  461. return(cp);
  462. } else {
  463. curreglist = (rl_p) myalloc(sizeof (rl_t));
  464. curreglist->rl_n = 0;
  465. for (rpp=reglist[cp->c3_prop];*rpp;rpp++) {
  466. i = *rpp - machregs;
  467. cinstance(cp->c3_repl,&rtoken,tp,i);
  468. if (match(&rtoken,tep,0))
  469. curreglist->rl_list[curreglist->rl_n++] = i;
  470. }
  471. if (curreglist->rl_n != 0)
  472. return(cp);
  473. myfree(curreglist);
  474. }
  475. }
  476. return(0); /* nothing found */
  477. }
  478. error(s,a1,a2,a3,a4,a5,a6,a7,a8) char *s; {
  479. fatal(s,a1,a2,a3,a4,a5,a6,a7,a8);
  480. }
  481. fatal(s,a1,a2,a3,a4,a5,a6,a7,a8) char *s; {
  482. fprintf(stderr,"Error: ");
  483. fprintf(stderr,s,a1,a2,a3,a4,a5,a6,a7,a8);
  484. fprintf(stderr,"\n");
  485. out_finish();
  486. abort();
  487. exit(-1);
  488. }
  489. #ifndef NDEBUG
  490. badassertion(asstr,file,line) char *asstr, *file; {
  491. fatal("Assertion \"%s\" failed %s(%d)",asstr,file,line);
  492. }
  493. #endif
  494. max(a,b) {
  495. return(a>b ? a : b);
  496. }