mach/proto/top/top.c

   1 /* $Id: top.c,v 1.12 1994/06/24 13:29:07 ceriel Exp $ */
   2 /*
   3  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
   4  * See the copyright notice in the ACK home directory, in the file "Copyright".
   5  */
   6 #include <stdio.h>
   7 #include "gen.h"
   8 #include "top.h"
   9 #include "queue.h"
  10
  11 /* STANDARD MACHINE-INDEPENT C CODE *************/
  12
  13 extern char *lstrip();
  14 extern instr_p newinstr();
  15 extern instr_p read_instr();
  16 extern instr_p gen_instr();
  17 extern char * malloc();
  18 extern char *strcat();
  19 extern char *strcpy();
  20 extern char *strncpy();
  21
  22 struct variable var[NRVARS+1];
  23 struct variable ANY;  /* ANY symbol matching any instruction */
  24
  25 char *REST;  /* Opcode of first instruction not matched by current pattern */
  26
  27 #include "gen.c"
  28
  29
  30 /* Macros for efficiency: */
  31
  32 #define is_white(c)     ( (c) == ' ' || (c) == '\t')
  33
  34 /* Skip white space in the unprocessed part of instruction 'ip' */
  35 #define skip_white(ip)  while (is_white(*(ip)->rest_line)) (ip)->rest_line++
  36
  37 main()
  38 {
  39         optimize();
  40         exit(0);
  41 }
  42
  43
  44 /* Optimize the standard input.
  45  * The optimizer uses a moving window. The instructions in the current
  46  * window are matched against a set of patterns generated from the
  47  * machine description table. If the match fails, the first instruction of
  48  * the window is moved to a back-up queue and a new instruction is
  49  * read from the input and appended to the end of the window.
  50  * If a matching pattern is found (and its operands etc. are ok),
  51  * the instructions at the head of the window are replaced by new
  52  * instructions, as indicated in the descriptor table; a new window
  53  * is created, consisting of the back-up instructions and the new
  54  * instructions and the rest of the old window. So effectively the
  55  * window moves a bit to the left after every hit. Hence sequences of
  56  * optimizations like:
  57  *      movl r0,x ; cmpl $0,x  -> movl r0,x ; tstl x -> movl r0,x
  58  * are captured without having a separate pattern for "movl ; cmpl".
  59  *
  60  * Whenever the backup queue exceeds some threshold, its first instruction
  61  * is written to the output and is removed.
  62  */
  63
  64 optimize()
  65 {
  66         struct queue_t windowq, backupq;
  67         queue window, backup;
  68         instr_p ip;
  69
  70         window = &windowq;
  71         backup = &backupq;
  72         empty_queue(window);
  73         empty_queue(backup);
  74         fill_window(window,MIN_WINDOW_SIZE);
  75         while (!empty(window)) {
  76                 if (try_hashentry(hashtab[hash(window)],window) ||
  77                     try_hashentry(hashany,window)) {
  78                         join_queues(backup,window);
  79                 } else {
  80                         ip = qhead(window);
  81                         remove_head(window);
  82                         add(backup,ip);
  83                         if (qlength(backup) > MIN_WINDOW_SIZE)  {
  84                                 write_first(backup);
  85                         }
  86                 }
  87                 fill_window(window,MIN_WINDOW_SIZE);
  88         }
  89         while (!empty(backup)) write_first(backup);
  90 }
  91
  92
  93
  94 bool try_hashentry(list,window)
  95         int *list;
  96         queue window;
  97 {
  98         register int *pp;
  99         patdescr_p p;
 100
 101         for (pp = list; *pp != -1; pp++) {
 102                 p = &patterns[*pp];
 103                 if (check_pattern(p,window) &&
 104                     check_operands(p,window) &&
 105                     check_constraint(*pp)) {
 106                         xform(p,window);
 107                         return TRUE;
 108                 }
 109         }
 110         return FALSE;
 111 }
 112
 113
 114 /* TEMP. */
 115
 116 /* int hash(w)
 117         queue w;
 118 {
 119         instr_p ip;
 120
 121         ip = qhead(w);
 122         return ip->opc[0] % 31;
 123 }
 124 */
 125
 126
 127 int hash(w)
 128         queue w;
 129 {
 130         register char *p;
 131         register sum,i;
 132         instr_p ip;
 133
 134         ip = qhead(w);
 135 /*      for (sum=0,p=ip->opc;*p;p++)
 136                 sum += *p;
 137 */
 138
 139         for (sum=i=0,p=ip->opc;*p;i += 3)
 140                 sum += (*p++)<<(i&03);
 141         return(sum%128);
 142 }
 143
 144 /* Fill the working window until it contains at least 'len' items.
 145  * When end-of-file is encountered it may contain fewer items.
 146  */
 147
 148 fill_window(w,len)
 149         register queue w;
 150 {
 151         register instr_p ip;
 152
 153         while(qlength(w) < len) {
 154                 if ((ip = read_instr()) == NIL) break;
 155                 ip->rest_line = ip->line;
 156                 set_opcode(ip);
 157                 add(w,ip);
 158         }
 159 }
 160
 161 write_first(w)
 162         queue w;
 163 {
 164         register instr_p ip = qhead(w);
 165
 166         fputs(ip->line, stdout);
 167         remove_head(w);
 168         oldinstr(ip);
 169 }
 170
 171
 172 /* Try to recognize the opcode part of an instruction */
 173
 174 set_opcode(ip)
 175         register instr_p ip;
 176 {
 177         register char *p,*q;
 178         char *qlim;
 179
 180         if (ip->state == JUNK) return;
 181         skip_white(ip);
 182         p = ip->rest_line;
 183         if (*p == LABEL_STARTER) {
 184                 strcpy(ip->opc,"labdef");
 185                 ip->state = ONLY_OPC;
 186                 return;
 187         }
 188         q = ip->opc;
 189         qlim = q + MAX_OPC_LEN;
 190         while(*p != OPC_TERMINATOR && *p != '\n') {
 191                 if (q == qlim) {
 192                         ip->state = JUNK;
 193                         return;
 194                 }
 195                 *q++ = *p++;
 196         }
 197         *q = '\0';
 198         ip->rest_line = p;
 199         ip->state = (well_shaped(ip->opc) ? ONLY_OPC : JUNK);
 200 }
 201
 202
 203
 204 /* Check if pattern 'p' matches the current input */
 205
 206 bool check_pattern(p,w)
 207         patdescr_p p;
 208         queue w;
 209 {
 210         register idescr_p id_p;
 211         idescr_p idlim;
 212         register instr_p ip;
 213
 214         ip = qhead(w);
 215         ANY.vstate = UNINSTANTIATED;
 216         idlim = &p->pat[p->patlen];
 217         for (id_p = p->pat; id_p < idlim; id_p++) {
 218                 if (ip == NIL || ip->state == JUNK) return FALSE;
 219                 if (id_p->opcode == (char *) 0) {
 220                         unify(ip->opc,&ANY);
 221                 } else {
 222                         if (strcmp(ip->opc,id_p->opcode) != 0) return FALSE;
 223                 }
 224                 ip = next(ip);
 225         }
 226         REST = ip->opc;
 227         return TRUE;
 228 }
 229
 230
 231
 232 bool check_operands(p,w)
 233         patdescr_p p;
 234         queue w;
 235 {
 236         register instr_p ip;
 237         register idescr_p id_p;
 238         int n;
 239
 240         /* fprintf(stderr,"try pattern %d\n",p-patterns); */
 241         clear_vars();
 242         for (id_p = p->pat, ip = qhead(w); id_p < &p->pat[p->patlen];
 243                                           id_p++, ip = next(ip)) {
 244                 assert(ip != NIL);
 245                 if (ip->state == JUNK ||
 246                     (ip->state == ONLY_OPC && !split_operands(ip))) {
 247                         return FALSE;
 248                 }
 249                 for (n = 0; n < MAXOP; n++) {
 250                         if (!opmatch(&id_p->templates[n],ip->op[n])) {
 251                                 return FALSE;
 252                         }
 253                 }
 254         }
 255         /* fprintf(stderr,"yes\n"); */
 256         return TRUE;
 257 }
 258
 259
 260
 261 /* Reset all variables to uninstantiated */
 262
 263 clear_vars()
 264 {
 265         register v;
 266
 267         for (v = 1; v <= NRVARS; v++) var[v].vstate = UNINSTANTIATED;
 268 }
 269
 270
 271 /* See if operand 's' matches the operand described by template 't'.
 272  * As a side effect, any uninstantiated variables used in the
 273  * template may become instantiated. For such a variable we also
 274  * check if it satisfies the constraint imposed on it in the
 275  * mode-definitions part of the table.
 276  */
 277
 278 bool opmatch(t,s)
 279         templ_p t;
 280         char *s;
 281 {
 282         char *l, buf[MAXOPLEN+1];
 283         bool was_instantiated;
 284         int vno;
 285
 286         vno = t->varno;
 287         if (vno == -1 || s[0] == '\0' ) {
 288                 return (vno == -1 && s[0] == '\0');
 289         }
 290         was_instantiated = (var[vno].vstate == INSTANTIATED);
 291         strcpy(buf,s);
 292         if ( (l=lstrip(buf,t->lctxt)) != NULLSTRING && rstrip(l,t->rctxt)) {
 293                 return (vno == 0 && *l == '\0') ||
 294                        (vno != 0 && unify(l,&var[vno]) &&
 295                         (was_instantiated || tok_chk(vno)));
 296         }
 297         return FALSE;
 298 }
 299
 300
 301
 302 /* Try to recognize the operands of an instruction */
 303
 304 bool split_operands(ip)
 305         register instr_p ip;
 306 {
 307         register int i;
 308         bool res;
 309
 310         if (strcmp(ip->opc,"labdef") ==0) {
 311                 labeldef(ip);
 312         } else {
 313                 for (i = 0; operand(ip,i) && op_separator(ip); i++);
 314         }
 315         res = remainder_empty(ip);
 316         ip->state = (res ? DONE : JUNK);
 317         return res;
 318 }
 319
 320
 321
 322 labeldef(ip)
 323         register instr_p ip;
 324 {
 325         register char *p;
 326         int oplen;
 327
 328         p = ip->rest_line;
 329         while( *p != LABEL_TERMINATOR) p++;
 330         oplen = p - ip->rest_line;
 331         if (oplen == 0 || oplen > MAXOPLEN) return;
 332         strncpy(ip->op[0],ip->rest_line,oplen);
 333         ip->op[0][oplen] = '\0';
 334         ip->rest_line = ++p;
 335         return;
 336 }
 337
 338
 339
 340
 341 /* Try to recognize the next operand of instruction 'ip' */
 342
 343 bool operand(ip,n)
 344         register instr_p ip;
 345 {
 346         register char *p;
 347         int oplen;
 348 #ifdef PAREN_OPEN
 349         int nesting = 0;
 350 #else
 351 #define nesting 0
 352 #endif
 353
 354         skip_white(ip);
 355         p = ip->rest_line;
 356         while((*p != OP_SEPARATOR || nesting) && *p != '\n') {
 357 #ifdef PAREN_OPEN
 358                 if (strindex(PAREN_OPEN, *p) != 0) nesting++;
 359                 else if (strindex(PAREN_CLOSE, *p) != 0) nesting--;
 360 #endif
 361                 p++;
 362         }
 363         oplen = p - ip->rest_line;
 364         if (oplen == 0 || oplen > MAXOPLEN) return FALSE;
 365         strncpy(ip->op[n],ip->rest_line,oplen);
 366         ip->op[n][oplen] = '\0';
 367         ip->rest_line = p;
 368         return TRUE;
 369 #ifdef nesting
 370 #undef nesting
 371 #endif
 372 }
 373
 374
 375
 376 /* See if the unprocessed part of instruction 'ip' is empty
 377  * (or contains only white space).
 378  */
 379
 380 bool remainder_empty(ip)
 381         instr_p ip;
 382 {
 383         skip_white(ip);
 384         return *ip->rest_line == '\n';
 385 }
 386
 387
 388 /* Try to match 'ctxt' at the beginning of string 'str'. If this
 389  * succeeds then return a pointer to the rest (unmatched part) of 'str'.
 390  */
 391
 392 char *lstrip(str,ctxt)
 393         register char *str, *ctxt;
 394 {
 395         assert(ctxt != NULLSTRING);
 396         while (*str != '\0' && *str == *ctxt) {
 397                 str++;
 398                 ctxt++;
 399         }
 400         return (*ctxt == '\0' ? str : NULLSTRING);
 401 }
 402
 403
 404
 405 /* Try to match 'ctxt' at the end of 'str'. If this succeeds then
 406  * replace truncate 'str'.
 407  */
 408
 409 bool rstrip(str,ctxt)
 410         char *str,*ctxt;
 411 {
 412         register char *s, *c;
 413
 414         for (s = str; *s != '\0'; s++);
 415         for (c = ctxt; *c != '\0'; c++);
 416         while (c >= ctxt) {
 417                 if (s < str || *s != *c--) return FALSE;
 418                 *s-- = '\0';
 419         }
 420         return TRUE;
 421 }
 422
 423
 424
 425 /* Try to unify variable 'v' with string 'str'. If the variable
 426  * was instantiated the unification only succeeds if the variable
 427  * and the string match; else the unification succeeds and the
 428  * variable becomes instantiated to the string.
 429  */
 430
 431 bool unify(str,v)
 432         char *str;
 433         register struct variable *v;
 434 {
 435         if (v->vstate == UNINSTANTIATED) {
 436                 v->vstate = INSTANTIATED;
 437                 strcpy(v->value,str);
 438                 return TRUE;
 439         } else {
 440                 return strcmp(v->value,str) == 0;
 441         }
 442 }
 443
 444
 445
 446 /* Transform the working window according to pattern 'p' */
 447
 448 xform(p,w)
 449         patdescr_p p;
 450         queue w;
 451 {
 452         register instr_p ip;
 453         int i;
 454
 455         for (i = 0; i < p->patlen; i++) {
 456                 ip = qhead(w);
 457                 remove_head(w);
 458                 oldinstr(ip);
 459         }
 460         replacement(p,w);
 461 }
 462
 463
 464
 465 /* Generate the replacement for pattern 'p' and insert it
 466  * at the front of the working window.
 467  * Note that we generate instructions in reverser order.
 468  */
 469
 470 replacement(p,w)
 471         register patdescr_p p;
 472         queue w;
 473 {
 474         register idescr_p id_p;
 475
 476         for (id_p = &p->repl[p->replen-1]; id_p >= p->repl; id_p--) {
 477                 insert(w,gen_instr(id_p));
 478         }
 479 }
 480
 481
 482
 483 /* Generate an instruction described by 'id_p'.
 484  * We build a 'line' for the new instruction and call set_opcode()
 485  * to re-recognize its opcode. Hence generated instructions are treated
 486  * in exactly the same way as normal instructions that are just read in.
 487  */
 488
 489 instr_p gen_instr(id_p)
 490         idescr_p id_p;
 491 {
 492         char *opc;
 493         instr_p ip;
 494         register templ_p t;
 495         register char *s;
 496         bool islabdef;
 497         int n;
 498         static char tmp[] = "x";
 499
 500         ip = newinstr();
 501         s = ip->line;
 502         opc = id_p->opcode;
 503         if (opc == (char *) 0) opc = ANY.value;
 504         if (strcmp(opc,"labdef") == 0) {
 505                 islabdef = TRUE;
 506                 s[0] = '\0';
 507         } else {
 508                 strcpy(s,opc);
 509                 tmp[0] = OPC_TERMINATOR;
 510                 strcat(s,tmp);
 511                 islabdef = FALSE;
 512         }
 513         for (n = 0; n < MAXOP;) {
 514                 t = &id_p->templates[n++];
 515                 if (t->varno == -1) break;
 516                 strcat(s,t->lctxt);
 517                 if (t->varno != 0) strcat(s,var[t->varno].value);
 518                 strcat(s,t->rctxt);
 519                 if (n<MAXOP && id_p->templates[n].varno!=-1) {
 520                         tmp[0] = OP_SEPARATOR;
 521                         strcat(s,tmp);
 522                 }
 523         }
 524         if (islabdef) {
 525                 tmp[0] = LABEL_TERMINATOR;
 526                 strcat(s,tmp);
 527         }
 528         strcat(s,"\n");
 529         ip->rest_line = ip->line;
 530         set_opcode(ip);
 531         return ip;
 532 }
 533
 534
 535
 536 /* Reading and writing instructions.
 537  * An instruction is assumed to be on one line. The line
 538  * is copied to the 'line' field of an instruction struct,
 539  * terminated by a \n and \0. If the line is too long (>MAXLINELEN),
 540  * it is split into pieces of length MAXLINELEN and the state of
 541  * each such struct is set to JUNK (so it will not be optimized).
 542  */
 543
 544 static bool junk_state = FALSE;  /* TRUE while processing a very long line */
 545
 546 instr_p read_instr()
 547 {
 548         instr_p ip;
 549         register int c;
 550         register char *p;
 551         register FILE *inp = stdin;
 552         char *plim;
 553
 554         ip = newinstr();
 555         plim = &ip->line[MAXLINELEN];
 556         if (( c = getc(inp)) == EOF) return NIL;
 557         for (p = ip->line; p < plim;) {
 558                 *p++ = c;
 559                 if (c == '\n') {
 560                         *p = '\0';
 561                         if (junk_state) ip->state = JUNK;
 562                         junk_state = FALSE;
 563                         return ip;
 564                 }
 565                 c = getc(inp);
 566         }
 567         ungetc(c,inp);
 568         *p = '\0';
 569         junk_state = ip->state = JUNK;
 570         return ip;
 571 }
 572
 573
 574
 575 /* Core allocation.
 576  * As all instruction struct have the same size we can re-use every struct.
 577  * We maintain a pool of free instruction structs.
 578  */
 579
 580 static instr_p instr_pool;
 581 int nr_mallocs = 0; /* for statistics */
 582
 583 instr_p newinstr()
 584 {
 585         register instr_p ip;
 586         int i;
 587
 588         if (instr_pool == NIL) {
 589                 instr_pool = (instr_p) malloc(sizeof(struct instruction));
 590                 instr_pool->fw = 0;
 591                 nr_mallocs++;
 592         }
 593         assert(instr_pool != NIL);
 594         ip = instr_pool;
 595         instr_pool = instr_pool->fw;
 596         ip->fw = ip->bw = NIL;
 597         ip->rest_line = NULLSTRING;
 598         ip->line[0] = ip->opc[0] = '\0';
 599         ip->state = ONLY_OPC;
 600         for (i = 0; i < MAXOP; i++) ip->op[i][0] = '\0';
 601         return ip;
 602 }
 603
 604 oldinstr(ip)
 605         instr_p ip;
 606 {
 607         ip->fw = instr_pool;
 608         instr_pool = ip;
 609 }
 610
 611
 612
 613 /* Debugging stuff */
 614
 615 badassertion(file,line)
 616         char *file;
 617         unsigned line;
 618 {
 619         fprintf(stderr,"assertion failed file %s, line %u\n",file,line);
 620         error("assertion");
 621 }
 622
 623 /* VARARGS1 */
 624 error(s,a)
 625         char *s,*a;
 626 {
 627         fprintf(stderr,s,a);
 628         fprintf(stderr,"\n");
 629         _cleanup();
 630         abort();
 631         exit(-1);
 632 }
 633
 634 /* Low level routines */
 635
 636 bool op_separator(ip)
 637         instr_p ip;
 638 {
 639         skip_white(ip);
 640         if (*(ip->rest_line) == OP_SEPARATOR) {
 641                 ip->rest_line++;
 642                 return TRUE;
 643         } else {
 644                 return FALSE;
 645         }
 646 }
 647
 648
 649
 650 bool well_shaped(opc)
 651         char *opc;
 652 {
 653         return is_letter(opc[0]);
 654 }
 655
 656
 657 bool is_letter(c)
 658 {
 659         return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
 660 }
 661
 662 /* is_white(c) : turned into a macro, see beginning of file */
 663