mach/proto/ncg/codegen.c

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