modules/src/em_opt/outputdfa.c

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