mach/proto/cg/subr.c

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