outputdfa.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643
  1. #ifndef NORCSID
  2. static char rcsidp5[] = "$Id$";
  3. #endif
  4. #include "parser.h"
  5. #include "Lpars.h"
  6. FILE *ofile;
  7. PRIVATE openofile();
  8. PRIVATE installofile();
  9. PRIVATE UNLINK();
  10. PRIVATE RENAME();
  11. PRIVATE outdfa();
  12. PRIVATE outmnems();
  13. PRIVATE outdotrans();
  14. PRIVATE outoneaction();
  15. PRIVATE outrepl();
  16. PRIVATE outexp();
  17. PRIVATE outext();
  18. PRIVATE outop();
  19. outputnopt()
  20. {
  21. openofile("dfa.c");
  22. outdfa();
  23. installofile();
  24. openofile("trans.c");
  25. outdotrans();
  26. installofile();
  27. openofile("incalls.r");
  28. outputincalls();
  29. installofile();
  30. }
  31. static char ofilename[80];
  32. static char ofiletemp[80];
  33. PRIVATE
  34. openofile(filename)
  35. char *filename;
  36. {
  37. char *strcpy(), *strcat();
  38. strcpy(ofilename,filename);
  39. strcpy(ofiletemp,filename);
  40. strcat(ofiletemp,".new");
  41. if((ofile=fopen(ofiletemp,"w"))==NULL) {
  42. fprintf(stderr,"Fatal Error: cannot open output file %s\n",ofiletemp);
  43. sys_stop(S_EXIT);
  44. }
  45. }
  46. PRIVATE
  47. installofile()
  48. {
  49. /*
  50. * if contents of newly generated ofiletemp is different
  51. * from that of ofilename then copy over old file else
  52. * delete newly generated file
  53. */
  54. register FILE *f1, *f2;
  55. register int c1, c2;
  56. fclose(ofile);
  57. if((f1 = fopen(ofiletemp,"r")) == NULL) {
  58. fprintf(stderr,"Fatal Error: cannont reopen file %s\n",ofiletemp);
  59. sys_stop(S_EXIT);
  60. }
  61. if((f2 = fopen(ofilename,"r")) == NULL) {
  62. fclose(f1);
  63. RENAME(ofiletemp,ofilename);
  64. return;
  65. }
  66. do {
  67. c1 = getc(f1);
  68. c2 = getc(f2);
  69. } while (c1 == c2 && c1 != EOF);
  70. fclose(f1);
  71. fclose(f2);
  72. if (c1 != c2) {
  73. RENAME(ofiletemp,ofilename);
  74. }
  75. else UNLINK(ofiletemp);
  76. }
  77. PRIVATE
  78. UNLINK(x)
  79. char *x;
  80. {
  81. /* Must remove the file "x" */
  82. unlink(x); /* systemcall to remove file */
  83. }
  84. PRIVATE
  85. RENAME(x,y)
  86. char *x, *y;
  87. {
  88. /* Must move the file "x" to the file "y" */
  89. unlink(y);
  90. if(link(x,y)!=0) {
  91. fprintf(stderr,"Cannot link to %s",y);
  92. sys_stop(S_EXIT);
  93. }
  94. unlink(x);
  95. }
  96. # define MAXOPCODE 255
  97. # define EMPTY -1
  98. int *next, *check, *base;
  99. unsigned currsize; /* current size of next and check arrays */
  100. int maxpos = 0; /* highest used position in these arrayes */
  101. PRIVATE
  102. increase_next(size)
  103. int size;
  104. {
  105. /* realloc arrays next and check so they are at least
  106. * of size 'size'
  107. */
  108. char *Realloc();
  109. unsigned newsize = currsize;
  110. register int i;
  111. do {
  112. newsize *= 2;
  113. } while (newsize<size);
  114. printf("Note: Extending next/check arrays from %d to %d\n",currsize,newsize);
  115. next = (int *)Realloc(next,newsize);
  116. check = (int *)Realloc(check,newsize);
  117. /* clear ends of new arrays */
  118. for(i=currsize;i<newsize;i++)
  119. next[i] = check[i] = EMPTY;
  120. currsize = newsize;
  121. }
  122. PRIVATE
  123. store_row(state,row)
  124. int state;
  125. register int *row;
  126. {
  127. /* find a place to store row in arrays */
  128. register b,i,o;
  129. register int *n = next;
  130. b=0;
  131. for(;;) {
  132. /* look for first possible place to store it */
  133. for(i=0;i<MAXOPCODE;i++) {
  134. if(row[i]) {
  135. if((o = b+i)>currsize) increase_next(o);
  136. if(n[o]!=EMPTY) goto nextpos;
  137. }
  138. }
  139. /* found a place */
  140. base[state]=b;
  141. for(i=0;i<MAXOPCODE;i++)
  142. if(row[i]) {
  143. if((o=b+i) >maxpos) maxpos = o;
  144. next[o] = row[i];
  145. check[o] = state;
  146. }
  147. return;
  148. nextpos:
  149. ++b;
  150. }
  151. }
  152. PRIVATE
  153. outdfa()
  154. {
  155. register int s,i;
  156. register struct state *p;
  157. int nout, ncpy, ngto;
  158. int row[MAXOPCODE];
  159. int numinrow;
  160. int numentries = 0;
  161. fprintf(ofile,"#include \"nopt.h\"\n");
  162. fprintf(ofile,"\n");
  163. fprintf(ofile,"int OO_maxreplacement = %d;\n", maxreplacement);
  164. fprintf(ofile,"\n");
  165. /* find how many entries in dfa */
  166. for(s=0;s<=higheststate;s++)
  167. for(p=states[s];p!=(struct state *)NULL;p=p->next)
  168. numentries++;
  169. /* start with next and check arrays twice this size */
  170. currsize = 2 * numentries;
  171. next = (int *)Malloc(currsize*sizeof(int));
  172. check = (int *)Malloc(currsize*sizeof(int));
  173. base = (int *)Malloc(((unsigned)(higheststate+1))*sizeof(int));
  174. /* fill next array with EMPTY */
  175. for(i=0;i<currsize;i++) check[i]=next[i]=EMPTY;
  176. for(s=0;s<=higheststate;s++) {
  177. /* empty row */
  178. for(i=0;i<MAXOPCODE;i++) row[i]=0;
  179. numinrow = 0;
  180. /* fill in non zero entries */
  181. for(p=states[s];p!=(struct state *)NULL;p=p->next) {
  182. numinrow++;
  183. row[p->op->id_opcode] = p->goto_state;
  184. }
  185. /* look for a place to store row */
  186. if(numinrow)
  187. store_row(s,row);
  188. else
  189. base[s] = EMPTY;
  190. }
  191. /* give some statistics on size of dfa */
  192. printf("Number of patterns: %d\n", numpatterns);
  193. printf("Longest pattern: %d\n", maxpattern);
  194. printf("Longest replacement: %d\n", maxreplacement);
  195. printf("Dfa contains %d states and %d distinct state/opcode pairs\n",
  196. higheststate+1,numentries);
  197. printf("Compacted using row displacement into %d entries\n",maxpos);
  198. /* output the arrays */
  199. fprintf(ofile,"struct dfa OO_checknext[] = {\n");
  200. for(i=0;i<=maxpos;i++) {
  201. fprintf(ofile,"\t/* %4d */\t",i);
  202. fprintf(ofile,"{%4d,%4d},\n", check[i], next[i]);
  203. }
  204. fprintf(ofile,"};\n\n");
  205. fprintf(ofile,"struct dfa *OO_base[] = {\n");
  206. for(s=0;s<=higheststate;s++) {
  207. fprintf(ofile,"\t/* %4d: ",s);
  208. outmnems(patterns[s]);
  209. fprintf(ofile,"*/\t");
  210. if(base[s]==EMPTY)
  211. fprintf(ofile,"0,\n");
  212. else
  213. fprintf(ofile,"&OO_checknext[%4d],\n", base[s]);
  214. }
  215. fprintf(ofile,"};\n\n");
  216. fprintf(ofile,"struct dodefault OO_default[] = {\n");
  217. for(s=0;s<=higheststate;s++) {
  218. fprintf(ofile,"\t/* %4d: ",s);
  219. outmnems(patterns[s]);
  220. fprintf(ofile,"*/\t");
  221. findfail(s,&nout,&ncpy,&ngto);
  222. fprintf(ofile,"{%4d,%4d},\n", nout,ngto);
  223. }
  224. fprintf(ofile,"};\n\n");
  225. }
  226. PRIVATE
  227. outmnems(l)
  228. struct mnems l;
  229. {
  230. int i;
  231. for(i=1;i<=l.m_len;i++)
  232. fprintf(ofile,"%s ",l.m_elems[i-1]->op_code->id_text);
  233. }
  234. PRIVATE int
  235. sametest(s1,s2,e1,e2)
  236. int s1,s2;
  237. struct exp_node *e1,*e2;
  238. {
  239. /* return 1 if tests are identical */
  240. if(e1) {
  241. if(!e2) return 0;
  242. if(e1->node_type!=e2->node_type) return 0;
  243. switch(e1->node_type) {
  244. case LOGAND:
  245. case LOGOR:
  246. case BITAND:
  247. case BITOR:
  248. case XOR:
  249. case MINUS:
  250. case PLUS:
  251. case TIMES:
  252. case DIV:
  253. case MOD:
  254. case EQ:
  255. case NE:
  256. case LT:
  257. case LE:
  258. case GT:
  259. case GE:
  260. case LSHIFT:
  261. case RSHIFT:
  262. case COMMA:
  263. case SAMESIGN:
  264. case SFIT:
  265. case UFIT:
  266. case ROTATE:
  267. case SAMEEXT:
  268. case SAMENAM:
  269. return (sametest(s1,s2,e1->exp_left,e2->exp_left) &&
  270. sametest(s1,s2,e1->exp_right,e2->exp_right));
  271. case NOT:
  272. case COMP:
  273. case UPLUS:
  274. case UMINUS:
  275. return sametest(s1,s2,e1->exp_left,e2->exp_left);
  276. case DEFINED:
  277. case UNDEFINED:
  278. case INT:
  279. return (e1->leaf_val == e2->leaf_val);
  280. case PATARG:
  281. /* depends on pattern !! */
  282. if (e1->leaf_val != e2->leaf_val) return 0;
  283. return (patterns[s1].m_elems[e1->leaf_val-1]->
  284. op_code->id_argfmt
  285. == patterns[s2].m_elems[e2->leaf_val-1]->
  286. op_code->id_argfmt);
  287. case PSIZE:
  288. case WSIZE:
  289. case DWSIZE:
  290. return 1;
  291. }
  292. /*NOTREACHED*/
  293. }
  294. else return (e2==0);
  295. }
  296. PRIVATE int
  297. samerepl(s1,s2,r1,r2)
  298. int s1,s2;
  299. struct mnems r1,r2;
  300. {
  301. /* return 1 if replacements are identical */
  302. register int i;
  303. register struct mnem_elem *m1,*m2;
  304. if (r1.m_len != r2.m_len) return 0; /* different length */
  305. for(i=0;i<r1.m_len;i++) {
  306. m1=r1.m_elems[i];
  307. m2=r2.m_elems[i];
  308. if(m1->op_code!=m2->op_code) return 0;
  309. if(!sametest(s1,s2,m1->arg,m2->arg)) return 0;
  310. }
  311. return 1;
  312. }
  313. PRIVATE int
  314. samecode(s1,s2)
  315. int s1,s2;
  316. {
  317. /* return 1 if replacement code of state s1 and s2 are identical */
  318. register struct action *a1,*a2;
  319. if (patterns[s1].m_len != patterns[s2].m_len) return 0;
  320. a1 = actions[s1];
  321. a2 = actions[s2];
  322. while(a1) {
  323. if(!a2) return 0; /* a2 is shorter */
  324. if(!samerepl(s1,s2,a1->replacement,a2->replacement)) return 0;
  325. if(!sametest(s1,s2,a1->test,a2->test)) return 0;
  326. a1 = a1->next;
  327. a2 = a2->next;
  328. }
  329. if(a2) return 0; /* a2 is longer */
  330. return 1;
  331. }
  332. PRIVATE
  333. outdotrans()
  334. {
  335. register int s,t;
  336. struct action *a;
  337. int seennontested;
  338. int *farray;
  339. fprintf(ofile,"#include \"nopt.h\"\n\n");
  340. /* keep track of which procedure used for each state */
  341. farray = (int *)Malloc((unsigned)(higheststate+1)*sizeof(int));
  342. for(s=0;s<=higheststate;s++) farray[s] = EMPTY;
  343. /* output the functions avoiding duplicates */
  344. for(s=0;s<=higheststate;s++) {
  345. if(actions[s]!=(struct action *)NULL) {
  346. /* first look for a previous identical function */
  347. for(t=0;t<s;t++) {
  348. if(actions[t]!=(struct action *)NULL &&
  349. samecode(s,t)) {
  350. /* use state 't' instead */
  351. farray[s]=t;
  352. goto next_func;
  353. }
  354. }
  355. /* no identical function so make new one */
  356. farray[s] = s;
  357. fprintf(ofile,"\nstatic do%dtrans() {\n",s);
  358. fprintf(ofile,"\tregister p_instr patt = OO_patternqueue;\n");
  359. fprintf(ofile,"\t/* ");
  360. outmnems(patterns[s]);
  361. fprintf(ofile," */\n");
  362. seennontested=0;
  363. for(a=actions[s];a!=(struct action *)NULL;a=a->next) {
  364. if(a->test!=(struct exp_node *)NULL) {
  365. fprintf(ofile,"\tif(");
  366. outexp(a->test,s);
  367. fprintf(ofile,") {\n");
  368. outoneaction(s,a);
  369. fprintf(ofile,"\t\treturn;\n");
  370. fprintf(ofile,"\t}\n");
  371. }
  372. else {
  373. if(seennontested) {
  374. fprintf(stderr,"parser: more than one untested action on state %d\n",s);
  375. nerrors++;
  376. }
  377. seennontested++;
  378. outoneaction(s,a);
  379. }
  380. }
  381. fprintf(ofile,"}\n");
  382. }
  383. next_func:
  384. continue;
  385. }
  386. /* output the array itself */
  387. fprintf(ofile,"\n\nint (*OO_ftrans[])()=\n{\n");
  388. for(s=0;s<=higheststate;s++) {
  389. if(farray[s]!=EMPTY)
  390. fprintf(ofile,"\tdo%dtrans,\n",farray[s]);
  391. else
  392. fprintf(ofile,"\t0,\n");
  393. }
  394. fprintf(ofile,"};\n");
  395. }
  396. PRIVATE
  397. outoneaction(s,a)
  398. int s;
  399. struct action *a;
  400. {
  401. fprintf(ofile,"\t\t/* -> ");
  402. outmnems(a->replacement);
  403. fprintf(ofile," */\n");
  404. fprintf(ofile,"#ifdef STATS\n");
  405. fprintf(ofile,"\t\tif(OO_wrstats) fprintf(stderr,\"%d\\n\");\n",a->linenum);
  406. fprintf(ofile,"#endif\n");
  407. outrepl(s,a->replacement);
  408. findworst(patterns[s],a->replacement);
  409. }
  410. PRIVATE
  411. outrepl(state,repl)
  412. int state;
  413. struct mnems repl;
  414. {
  415. /*
  416. /* Contruct <repl>=r1 r2 ... rn and put on output queue.
  417. */
  418. int n = repl.m_len;
  419. int i;
  420. for(i=1;i<=n;i++) {
  421. struct mnem_elem *ri = repl.m_elems[i-1];
  422. char *mnem = ri->op_code->id_text;
  423. switch(ri->op_code->id_argfmt) {
  424. case NOARG:
  425. fprintf(ofile,"\t\tEM_Rop(op_%s);\n",mnem);
  426. break;
  427. case CST:
  428. fprintf(ofile,"\t\tEM_Rcst(op_%s,",mnem);
  429. fprintf(ofile,"(arith)");
  430. outexp(ri->arg,state);
  431. fprintf(ofile,");\n");
  432. break;
  433. case CSTOPT:
  434. if(ri->arg) {
  435. fprintf(ofile,"\t\tEM_Rcst(op_%s,",mnem);
  436. fprintf(ofile,"(arith)");
  437. outexp(ri->arg,state);
  438. }
  439. else {
  440. fprintf(ofile,"\t\tEM_Rnarg(op_%s);\n",mnem);
  441. }
  442. fprintf(ofile,");\n");
  443. break;
  444. case LAB:
  445. fprintf(ofile,"\t\tEM_Rilb(op_%s,",mnem);
  446. outexp(ri->arg,state);
  447. fprintf(ofile,");\n");
  448. break;
  449. case DEFILB:
  450. fprintf(ofile,"\t\tEM_Rdefilb(op_%s,",mnem);
  451. outexp(ri->arg,state);
  452. fprintf(ofile,");\n");
  453. break;
  454. case PNAM:
  455. fprintf(ofile,"\t\tEM_Rpro(op_%s,",mnem);
  456. outexp(ri->arg,state);
  457. fprintf(ofile,");\n");
  458. break;
  459. case EXT:
  460. fprintf(ofile,"\t\tOO_mkext(GETNXTREPL(), op_%s,",mnem);
  461. outexp(ri->arg,state);
  462. fprintf(ofile,");\n");
  463. break;
  464. }
  465. }
  466. }
  467. PRIVATE
  468. outexp(e,state)
  469. struct exp_node *e;
  470. int state;
  471. {
  472. switch(e->node_type) {
  473. case LOGAND:
  474. case LOGOR:
  475. case BITAND:
  476. case BITOR:
  477. case XOR:
  478. case MINUS:
  479. case PLUS:
  480. case TIMES:
  481. case DIV:
  482. case MOD:
  483. case EQ:
  484. case NE:
  485. case LT:
  486. case LE:
  487. case GT:
  488. case GE:
  489. case LSHIFT:
  490. case RSHIFT:
  491. fprintf(ofile,"(");
  492. outexp(e->exp_left,state);
  493. outop(e->node_type);
  494. outexp(e->exp_right,state);
  495. fprintf(ofile,")");
  496. break;
  497. case NOT:
  498. case COMP:
  499. case UPLUS:
  500. case UMINUS:
  501. fprintf(ofile,"(");
  502. outop(e->node_type);
  503. outexp(e->exp_left,state);
  504. fprintf(ofile,")");
  505. break;
  506. case DEFINED:
  507. fprintf(ofile,"DEFINED(patt[%d])",e->leaf_val-1);
  508. break;
  509. case UNDEFINED:
  510. fprintf(ofile,"!DEFINED(patt[%d])",e->leaf_val-1);
  511. break;
  512. case COMMA:
  513. outext(e->exp_left);
  514. fprintf(ofile,",");
  515. fprintf(ofile,"(arith)");
  516. outexp(e->exp_right,state);
  517. break;
  518. case SAMESIGN:
  519. case SFIT:
  520. case UFIT:
  521. case ROTATE:
  522. outop(e->node_type);
  523. fprintf(ofile,"(arith)");
  524. outexp(e->exp_left,state);
  525. fprintf(ofile,",");
  526. fprintf(ofile,"(arith)");
  527. outexp(e->exp_right,state);
  528. fprintf(ofile,")");
  529. break;
  530. case SAMEEXT:
  531. case SAMENAM:
  532. outop(e->node_type);
  533. outext(e->exp_left);
  534. fprintf(ofile,",");
  535. outext(e->exp_right);
  536. fprintf(ofile,")");
  537. break;
  538. case PATARG:
  539. switch(patterns[state].m_elems[e->leaf_val-1]->op_code->id_argfmt) {
  540. case NOARG:
  541. fprintf(stderr,"error: mnem %d has no argument\n",e->leaf_val);
  542. nerrors++;
  543. break;
  544. case CST:
  545. case CSTOPT:
  546. fprintf(ofile,"CST(patt[%d])",e->leaf_val-1);
  547. break;
  548. case LAB:
  549. fprintf(ofile,"LAB(patt[%d])",e->leaf_val-1);
  550. break;
  551. case DEFILB:
  552. fprintf(ofile,"DEFILB(patt[%d])",e->leaf_val-1);
  553. break;
  554. case PNAM:
  555. fprintf(ofile,"PNAM(patt[%d])",e->leaf_val-1);
  556. break;
  557. case EXT:
  558. fprintf(ofile,"OO_offset(patt+%d)",e->leaf_val-1);
  559. break;
  560. }
  561. break;
  562. case PSIZE:
  563. fprintf(ofile,"OO_PSIZE"); break;
  564. case WSIZE:
  565. fprintf(ofile,"OO_WSIZE"); break;
  566. case DWSIZE:
  567. fprintf(ofile,"OO_DWSIZE"); break;
  568. case INT:
  569. fprintf(ofile,"%d",e->leaf_val); break;
  570. }
  571. }
  572. PRIVATE
  573. outext(e)
  574. struct exp_node *e;
  575. {
  576. if(e->node_type!=PATARG) {
  577. fprintf(stderr,"Internal error in outext of parser\n");
  578. nerrors++;
  579. }
  580. fprintf(ofile,"patt+%d",e->leaf_val-1);
  581. }
  582. PRIVATE
  583. outop(op)
  584. int op;
  585. {
  586. switch(op) {
  587. case LOGAND: fprintf(ofile,"&&"); break;
  588. case LOGOR: fprintf(ofile,"||"); break;
  589. case BITAND: fprintf(ofile,"&"); break;
  590. case BITOR: fprintf(ofile,"|"); break;
  591. case XOR: fprintf(ofile,"^"); break;
  592. case MINUS: fprintf(ofile,"-"); break;
  593. case PLUS: fprintf(ofile,"+"); break;
  594. case TIMES: fprintf(ofile,"*"); break;
  595. case DIV: fprintf(ofile,"/"); break;
  596. case MOD: fprintf(ofile,"%%"); break;
  597. case EQ: fprintf(ofile,"=="); break;
  598. case NE: fprintf(ofile,"!="); break;
  599. case LT: fprintf(ofile,"<"); break;
  600. case LE: fprintf(ofile,"<="); break;
  601. case GT: fprintf(ofile,">"); break;
  602. case GE: fprintf(ofile,">="); break;
  603. case LSHIFT: fprintf(ofile,"<<"); break;
  604. case RSHIFT: fprintf(ofile,">>"); break;
  605. case NOT: fprintf(ofile,"!"); break;
  606. case COMP: fprintf(ofile,"~"); break;
  607. case UPLUS: fprintf(ofile,"+"); break;
  608. case UMINUS: fprintf(ofile,"-"); break;
  609. case SAMESIGN: fprintf(ofile,"OO_signsame("); break;
  610. case SFIT: fprintf(ofile,"OO_sfit("); break;
  611. case UFIT: fprintf(ofile,"OO_ufit("); break;
  612. case ROTATE: fprintf(ofile,"OO_rotate("); break;
  613. case SAMEEXT: fprintf(ofile,"OO_extsame("); break;
  614. case SAMENAM: fprintf(ofile,"OO_namsame("); break;
  615. }
  616. }