src/bin/embryo_cc_sc7.c

   1 /*  Small compiler - Staging buffer and optimizer
   2  *
   3  *  The staging buffer
   4  *  ------------------
   5  *  The staging buffer allows buffered output of generated code, deletion
   6  *  of redundant code, optimization by a tinkering process and reversing
   7  *  the ouput of evaluated expressions (which is used for the reversed
   8  *  evaluation of arguments in functions).
   9  *  Initially, stgwrite() writes to the file directly, but after a call to
  10  *  stgset(TRUE), output is redirected to the buffer. After a call to
  11  *  stgset(FALSE), stgwrite()'s output is directed to the file again. Thus
  12  *  only one routine is used for writing to the output, which can be
  13  *  buffered output or direct output.
  14  *
  15  *  staging buffer variables:   stgbuf  - the buffer
  16  *                              stgidx  - current index in the staging buffer
  17  *                              staging - if true, write to the staging buffer;
  18  *                                        if false, write to file directly.
  19  *
  20  *  Copyright (c) ITB CompuPhase, 1997-2003
  21  *
  22  *  This software is provided "as-is", without any express or implied warranty.
  23  *  In no event will the authors be held liable for any damages arising from
  24  *  the use of this software.
  25  *
  26  *  Permission is granted to anyone to use this software for any purpose,
  27  *  including commercial applications, and to alter it and redistribute it
  28  *  freely, subject to the following restrictions:
  29  *
  30  *  1.  The origin of this software must not be misrepresented; you must not
  31  *      claim that you wrote the original software. If you use this software in
  32  *      a product, an acknowledgment in the product documentation would be
  33  *      appreciated but is not required.
  34  *  2.  Altered source versions must be plainly marked as such, and must not be
  35  *      misrepresented as being the original software.
  36  *  3.  This notice may not be removed or altered from any source distribution.
  37  *
  38  *  Version: $Id$
  39  */
  40
  41 /*
  42  * vim:ts=8:sw=3:sts=8:noexpandtab:cino=>5n-3f0^-2{2
  43  */
  44
  45 #ifdef HAVE_CONFIG_H
  46 # include <config.h>
  47 #endif
  48
  49 #include <assert.h>
  50 #include <stdio.h>
  51 #include <stdlib.h>             /* for atoi() */
  52 #include <string.h>
  53 #include <ctype.h>
  54
  55 #include "embryo_cc_sc.h"
  56
  57 #if defined _MSC_VER
  58 #pragma warning(push)
  59 #pragma warning(disable:4125)   /* decimal digit terminates octal escape sequence */
  60 #endif
  61
  62 #include "embryo_cc_sc7.scp"
  63
  64 #if defined _MSC_VER
  65 #pragma warning(pop)
  66 #endif
  67
  68 static void         stgstring(char *start, char *end);
  69 static void         stgopt(char *start, char *end);
  70
  71 #define sSTG_GROW   512
  72 #define sSTG_MAX    20480
  73
  74 static char        *stgbuf = NULL;
  75 static int          stgmax = 0; /* current size of the staging buffer */
  76
  77 #define CHECK_STGBUFFER(index) if ((int)(index)>=stgmax) grow_stgbuffer((index)+1)
  78
  79 static void
  80 grow_stgbuffer(int requiredsize)
  81 {
  82    char               *p;
  83    int                 clear = stgbuf == NULL;  /* if previously none, empty buffer explicitly */
  84
  85    assert(stgmax < requiredsize);
  86    /* if the staging buffer (holding intermediate code for one line) grows
  87     * over a few kBytes, there is probably a run-away expression
  88     */
  89    if (requiredsize > sSTG_MAX)
  90       error(102, "staging buffer");     /* staging buffer overflow (fatal error) */
  91    stgmax = requiredsize + sSTG_GROW;
  92    if (stgbuf != NULL)
  93       p = (char *)realloc(stgbuf, stgmax * sizeof(char));
  94    else
  95       p = (char *)malloc(stgmax * sizeof(char));
  96    if (p == NULL)
  97       error(102, "staging buffer");     /* staging buffer overflow (fatal error) */
  98    stgbuf = p;
  99    if (clear)
 100       *stgbuf = '\0';
 101 }
 102
 103 void
 104 stgbuffer_cleanup(void)
 105 {
 106    if (stgbuf != NULL)
 107      {
 108         free(stgbuf);
 109         stgbuf = NULL;
 110         stgmax = 0;
 111      }                          /* if */
 112 }
 113
 114 /* the variables "stgidx" and "staging" are declared in "scvars.c" */
 115
 116 /*  stgmark
 117  *
 118  *  Copies a mark into the staging buffer. At this moment there are three
 119  *  possible marks:
 120  *     sSTARTREORDER    identifies the beginning of a series of expression
 121  *                      strings that must be written to the output file in
 122  *                      reordered order
 123  *    sENDREORDER       identifies the end of 'reverse evaluation'
 124  *    sEXPRSTART + idx  only valid within a block that is evaluated in
 125  *                      reordered order, it identifies the start of an
 126  *                      expression; the "idx" value is the argument position
 127  *
 128  *  Global references: stgidx  (altered)
 129  *                     stgbuf  (altered)
 130  *                     staging (referred to only)
 131  */
 132 void
 133 stgmark(char mark)
 134 {
 135    if (staging)
 136      {
 137         CHECK_STGBUFFER(stgidx);
 138         stgbuf[stgidx++] = mark;
 139      }                          /* if */
 140 }
 141
 142 static int
 143 filewrite(char *str)
 144 {
 145    if (sc_status == statWRITE)
 146       return sc_writeasm(outf, str);
 147    return TRUE;
 148 }
 149
 150 /*  stgwrite
 151  *
 152  *  Writes the string "st" to the staging buffer or to the output file. In the
 153  *  case of writing to the staging buffer, the terminating byte of zero is
 154  *  copied too, but... the optimizer can only work on complete lines (not on
 155  *  fractions of it. Therefore if the string is staged, if the last character
 156  *  written to the buffer is a '\0' and the previous-to-last is not a '\n',
 157  *  the string is concatenated to the last string in the buffer (the '\0' is
 158  *  overwritten). This also means an '\n' used in the middle of a string isn't
 159  *  recognized and could give wrong results with the optimizer.
 160  *  Even when writing to the output file directly, all strings are buffered
 161  *  until a whole line is complete.
 162  *
 163  *  Global references: stgidx  (altered)
 164  *                     stgbuf  (altered)
 165  *                     staging (referred to only)
 166  */
 167 void
 168 stgwrite(char *st)
 169 {
 170    int                 len;
 171
 172    CHECK_STGBUFFER(0);
 173    if (staging)
 174      {
 175         if (stgidx >= 2 && stgbuf[stgidx - 1] == '\0'
 176             && stgbuf[stgidx - 2] != '\n')
 177            stgidx -= 1;         /* overwrite last '\0' */
 178         while (*st != '\0')
 179           {                     /* copy to staging buffer */
 180              CHECK_STGBUFFER(stgidx);
 181              stgbuf[stgidx++] = *st++;
 182           }                     /* while */
 183         CHECK_STGBUFFER(stgidx);
 184         stgbuf[stgidx++] = '\0';
 185      }
 186    else
 187      {
 188         CHECK_STGBUFFER(strlen(stgbuf) + strlen(st) + 1);
 189         strcat(stgbuf, st);
 190         len = strlen(stgbuf);
 191         if (len > 0 && stgbuf[len - 1] == '\n')
 192           {
 193              filewrite(stgbuf);
 194              stgbuf[0] = '\0';
 195           }                     /* if */
 196      }                          /* if */
 197 }
 198
 199 /*  stgout
 200  *
 201  *  Writes the staging buffer to the output file via stgstring() (for
 202  *  reversing expressions in the buffer) and stgopt() (for optimizing). It
 203  *  resets "stgidx".
 204  *
 205  *  Global references: stgidx  (altered)
 206  *                     stgbuf  (referred to only)
 207  *                     staging (referred to only)
 208  */
 209 void
 210 stgout(int index)
 211 {
 212    if (!staging)
 213       return;
 214    stgstring(&stgbuf[index], &stgbuf[stgidx]);
 215    stgidx = index;
 216 }
 217
 218 typedef struct
 219 {
 220    char               *start, *end;
 221 } argstack;
 222
 223 /*  stgstring
 224  *
 225  *  Analyses whether code strings should be output to the file as they appear
 226  *  in the staging buffer or whether portions of it should be re-ordered.
 227  *  Re-ordering takes place in function argument lists; Small passes arguments
 228  *  to functions from right to left. When arguments are "named" rather than
 229  *  positional, the order in the source stream is indeterminate.
 230  *  This function calls itself recursively in case it needs to re-order code
 231  *  strings, and it uses a private stack (or list) to mark the start and the
 232  *  end of expressions in their correct (reversed) order.
 233  *  In any case, stgstring() sends a block as large as possible to the
 234  *  optimizer stgopt().
 235  *
 236  *  In "reorder" mode, each set of code strings must start with the token
 237  *  sEXPRSTART, even the first. If the token sSTARTREORDER is represented
 238  *  by '[', sENDREORDER by ']' and sEXPRSTART by '|' the following applies:
 239  *     '[]...'     valid, but useless; no output
 240  *     '[|...]     valid, but useless; only one string
 241  *     '[|...|...] valid and usefull
 242  *     '[...|...]  invalid, first string doesn't start with '|'
 243  *     '[|...|]    invalid
 244  */
 245 static void
 246 stgstring(char *start, char *end)
 247 {
 248    char               *ptr;
 249    int                 nest, argc, arg;
 250    argstack           *stack;
 251
 252    while (start < end)
 253      {
 254         if (*start == sSTARTREORDER)
 255           {
 256              start += 1;        /* skip token */
 257              /* allocate a argstack with sMAXARGS items */
 258              stack = (argstack *) malloc(sMAXARGS * sizeof(argstack));
 259              if (stack == NULL)
 260                 error(103);     /* insufficient memory */
 261              nest = 1;          /* nesting counter */
 262              argc = 0;          /* argument counter */
 263              arg = -1;          /* argument index; no valid argument yet */
 264              do
 265                {
 266                   switch (*start)
 267                     {
 268                     case sSTARTREORDER:
 269                        nest++;
 270                        start++;
 271                        break;
 272                     case sENDREORDER:
 273                        nest--;
 274                        start++;
 275                        break;
 276                     default:
 277                        if ((*start & sEXPRSTART) == sEXPRSTART)
 278                          {
 279                             if (nest == 1)
 280                               {
 281                                  if (arg >= 0)
 282                                     stack[arg].end = start - 1; /* finish previous argument */
 283                                  arg = (unsigned char)*start - sEXPRSTART;
 284                                  stack[arg].start = start + 1;
 285                                  if (arg >= argc)
 286                                     argc = arg + 1;
 287                               } /* if */
 288                             start++;
 289                          }
 290                        else
 291                          {
 292                             start += strlen(start) + 1;
 293                          }      /* if */
 294                     }           /* switch */
 295                }
 296              while (nest);      /* enddo */
 297              if (arg >= 0)
 298                 stack[arg].end = start - 1;     /* finish previous argument */
 299              while (argc > 0)
 300                {
 301                   argc--;
 302                   stgstring(stack[argc].start, stack[argc].end);
 303                }                /* while */
 304              free(stack);
 305           }
 306         else
 307           {
 308              ptr = start;
 309              while (ptr < end && *ptr != sSTARTREORDER)
 310                 ptr += strlen(ptr) + 1;
 311              stgopt(start, ptr);
 312              start = ptr;
 313           }                     /* if */
 314      }                          /* while */
 315 }
 316
 317 /*  stgdel
 318  *
 319  *  Scraps code from the staging buffer by resetting "stgidx" to "index".
 320  *
 321  *  Global references: stgidx (altered)
 322  *                     staging (reffered to only)
 323  */
 324 void
 325 stgdel(int index, cell code_index)
 326 {
 327    if (staging)
 328      {
 329         stgidx = index;
 330         code_idx = code_index;
 331      }                          /* if */
 332 }
 333
 334 int
 335 stgget(int *index, cell * code_index)
 336 {
 337    if (staging)
 338      {
 339         *index = stgidx;
 340         *code_index = code_idx;
 341      }                          /* if */
 342    return staging;
 343 }
 344
 345 /*  stgset
 346  *
 347  *  Sets staging on or off. If it's turned off, the staging buffer must be
 348  *  initialized to an empty string. If it's turned on, the routine makes sure
 349  *  the index ("stgidx") is set to 0 (it should already be 0).
 350  *
 351  *  Global references: staging  (altered)
 352  *                     stgidx   (altered)
 353  *                     stgbuf   (contents altered)
 354  */
 355 void
 356 stgset(int onoff)
 357 {
 358    staging = onoff;
 359    if (staging)
 360      {
 361         assert(stgidx == 0);
 362         stgidx = 0;
 363         CHECK_STGBUFFER(stgidx);
 364         /* write any contents that may be put in the buffer by stgwrite()
 365          * when "staging" was 0
 366          */
 367         if (stgbuf[0] != '\0')
 368            filewrite(stgbuf);
 369      }                          /* if */
 370    stgbuf[0] = '\0';
 371 }
 372
 373 /* phopt_init
 374  * Initialize all sequence strings of the peehole optimizer. The strings
 375  * are embedded in the .EXE file in compressed format, here we expand
 376  * them (and allocate memory for the sequences).
 377  */
 378 static SEQUENCE    *sequences;
 379
 380 int
 381 phopt_init(void)
 382 {
 383    int                 number, i, len;
 384    char                str[160];
 385
 386    /* count number of sequences */
 387    for (number = 0; sequences_cmp[number].find != NULL; number++)
 388       /* nothing */ ;
 389    number++;                    /* include an item for the NULL terminator */
 390
 391    if ((sequences = (SEQUENCE *) malloc(number * sizeof(SEQUENCE))) == NULL)
 392       return FALSE;
 393
 394    /* pre-initialize all to NULL (in case of failure) */
 395    for (i = 0; i < number; i++)
 396      {
 397         sequences[i].find = NULL;
 398         sequences[i].replace = NULL;
 399         sequences[i].savesize = 0;
 400      }                          /* for */
 401
 402    /* expand all strings */
 403    for (i = 0; i < number - 1; i++)
 404      {
 405         len =
 406            strexpand(str, (unsigned char *)sequences_cmp[i].find, sizeof str,
 407                      SCPACK_TABLE);
 408         assert(len <= sizeof str);
 409         assert(len == (int)strlen(str) + 1);
 410         sequences[i].find = (char *)malloc(len);
 411         if (sequences[i].find != NULL)
 412            strcpy(sequences[i].find, str);
 413         len =
 414            strexpand(str, (unsigned char *)sequences_cmp[i].replace, sizeof str,
 415                      SCPACK_TABLE);
 416         assert(len <= sizeof str);
 417         assert(len == (int)strlen(str) + 1);
 418         sequences[i].replace = (char *)malloc(len);
 419         if (sequences[i].replace != NULL)
 420            strcpy(sequences[i].replace, str);
 421         sequences[i].savesize = sequences_cmp[i].savesize;
 422         if (sequences[i].find == NULL || sequences[i].replace == NULL)
 423            return phopt_cleanup();
 424      }                          /* for */
 425
 426    return TRUE;
 427 }
 428
 429 int
 430 phopt_cleanup(void)
 431 {
 432    int                 i;
 433
 434    if (sequences != NULL)
 435      {
 436         i = 0;
 437         while (sequences[i].find != NULL || sequences[i].replace != NULL)
 438           {
 439              if (sequences[i].find != NULL)
 440                 free(sequences[i].find);
 441              if (sequences[i].replace != NULL)
 442                 free(sequences[i].replace);
 443              i++;
 444           }                     /* while */
 445         free(sequences);
 446         sequences = NULL;
 447      }                          /* if */
 448    return FALSE;
 449 }
 450
 451 #define _maxoptvars     4
 452 #define _aliasmax       10      /* a 32-bit number can be represented in
 453                                  * 9 decimal digits */
 454
 455 static int
 456 matchsequence(char *start, char *end, char *pattern,
 457               char symbols[_maxoptvars][_aliasmax + 1], int *match_length)
 458 {
 459    int                 var, i;
 460    char                str[_aliasmax + 1];
 461    char               *start_org = start;
 462
 463    *match_length = 0;
 464    for (var = 0; var < _maxoptvars; var++)
 465       symbols[var][0] = '\0';
 466
 467    while (*start == '\t' || *start == ' ')
 468       start++;
 469    while (*pattern)
 470      {
 471         if (start >= end)
 472            return FALSE;
 473         switch (*pattern)
 474           {
 475           case '%':             /* new "symbol" */
 476              pattern++;
 477              assert(isdigit(*pattern));
 478              var = atoi(pattern) - 1;
 479              assert(var >= 0 && var < _maxoptvars);
 480              assert(alphanum(*start));
 481              for (i = 0; start < end && alphanum(*start); i++, start++)
 482                {
 483                   assert(i <= _aliasmax);
 484                   str[i] = *start;
 485                }                /* for */
 486              str[i] = '\0';
 487              if (symbols[var][0] != '\0')
 488                {
 489                   if (strcmp(symbols[var], str) != 0)
 490                      return FALSE;      /* symbols should be identical */
 491                }
 492              else
 493                {
 494                   strcpy(symbols[var], str);
 495                }                /* if */
 496              break;
 497           case ' ':
 498              if (*start != '\t' && *start != ' ')
 499                 return FALSE;
 500              while ((start < end && *start == '\t') || *start == ' ')
 501                 start++;
 502              break;
 503           case '!':
 504              while ((start < end && *start == '\t') || *start == ' ')
 505                 start++;        /* skip trailing white space */
 506              if (*start != '\n')
 507                 return FALSE;
 508              assert(*(start + 1) == '\0');
 509              start += 2;        /* skip '\n' and '\0' */
 510              if (*(pattern + 1) != '\0')
 511                 while ((start < end && *start == '\t') || *start == ' ')
 512                    start++;     /* skip leading white space of next instruction */
 513              break;
 514           default:
 515              if (tolower(*start) != tolower(*pattern))
 516                 return FALSE;
 517              start++;
 518           }                     /* switch */
 519         pattern++;
 520      }                          /* while */
 521
 522    *match_length = (int)(start - start_org);
 523    return TRUE;
 524 }
 525
 526 static char        *
 527 replacesequence(char *pattern, char symbols[_maxoptvars][_aliasmax + 1],
 528                 int *repl_length)
 529 {
 530    char               *lptr;
 531    int                 var;
 532    char               *buffer;
 533
 534    /* calculate the length of the new buffer
 535     * this is the length of the pattern plus the length of all symbols (note
 536     * that the same symbol may occur multiple times in the pattern) plus
 537     * line endings and startings ('\t' to start a line and '\n\0' to end one)
 538     */
 539    assert(repl_length != NULL);
 540    *repl_length = 0;
 541    lptr = pattern;
 542    while (*lptr)
 543      {
 544         switch (*lptr)
 545           {
 546           case '%':
 547              lptr++;            /* skip '%' */
 548              assert(isdigit(*lptr));
 549              var = atoi(lptr) - 1;
 550              assert(var >= 0 && var < _maxoptvars);
 551              assert(symbols[var][0] != '\0');   /* variable should be defined */
 552              *repl_length += strlen(symbols[var]);
 553              break;
 554           case '!':
 555              *repl_length += 3; /* '\t', '\n' & '\0' */
 556              break;
 557           default:
 558              *repl_length += 1;
 559           }                     /* switch */
 560         lptr++;
 561      }                          /* while */
 562
 563    /* allocate a buffer to replace the sequence in */
 564    if ((buffer = malloc(*repl_length)) == NULL)
 565      {
 566         error(103);
 567         return NULL;
 568      }
 569
 570    /* replace the pattern into this temporary buffer */
 571    lptr = buffer;
 572    *lptr++ = '\t';              /* the "replace" patterns do not have tabs */
 573    while (*pattern)
 574      {
 575         assert((int)(lptr - buffer) < *repl_length);
 576         switch (*pattern)
 577           {
 578           case '%':
 579              /* write out the symbol */
 580              pattern++;
 581              assert(isdigit(*pattern));
 582              var = atoi(pattern) - 1;
 583              assert(var >= 0 && var < _maxoptvars);
 584              assert(symbols[var][0] != '\0');   /* variable should be defined */
 585              strcpy(lptr, symbols[var]);
 586              lptr += strlen(symbols[var]);
 587              break;
 588           case '!':
 589              /* finish the line, optionally start the next line with an indent */
 590              *lptr++ = '\n';
 591              *lptr++ = '\0';
 592              if (*(pattern + 1) != '\0')
 593                 *lptr++ = '\t';
 594              break;
 595           default:
 596              *lptr++ = *pattern;
 597           }                     /* switch */
 598         pattern++;
 599      }                          /* while */
 600
 601    assert((int)(lptr - buffer) == *repl_length);
 602    return buffer;
 603 }
 604
 605 static void
 606 strreplace(char *dest, char *replace, int sub_length, int repl_length,
 607            int dest_length)
 608 {
 609    int                 offset = sub_length - repl_length;
 610
 611    if (offset > 0)              /* delete a section */
 612       memmove(dest, dest + offset, dest_length - offset);
 613    else if (offset < 0)         /* insert a section */
 614       memmove(dest - offset, dest, dest_length);
 615    memcpy(dest, replace, repl_length);
 616 }
 617
 618 /*  stgopt
 619  *
 620  *  Optimizes the staging buffer by checking for series of instructions that
 621  *  can be coded more compact. The routine expects the lines in the staging
 622  *  buffer to be separated with '\n' and '\0' characters.
 623  *
 624  *  The longest sequences must be checked first.
 625  */
 626
 627 static void
 628 stgopt(char *start, char *end)
 629 {
 630    char                symbols[_maxoptvars][_aliasmax + 1];
 631    int                 seq, match_length, repl_length;
 632
 633    assert(sequences != NULL);
 634    while (start < end)
 635      {
 636         if ((sc_debug & sNOOPTIMIZE) != 0 || sc_status != statWRITE)
 637           {
 638              /* do not match anything if debug-level is maximum */
 639              filewrite(start);
 640           }
 641         else
 642           {
 643              seq = 0;
 644              while (sequences[seq].find != NULL)
 645                {
 646                   assert(seq >= 0);
 647                   if (matchsequence
 648                       (start, end, sequences[seq].find, symbols, &match_length))
 649                     {
 650                        char               *replace =
 651                           replacesequence(sequences[seq].replace, symbols,
 652                                           &repl_length);
 653                        /* If the replacement is bigger than the original section, we may need
 654                         * to "grow" the staging buffer. This is quite complex, due to the
 655                         * re-ordering of expressions that can also happen in the staging
 656                         * buffer. In addition, it should not happen: the peephole optimizer
 657                         * must replace sequences with *shorter* sequences, not longer ones.
 658                         * So, I simply forbid sequences that are longer than the ones they
 659                         * are meant to replace.
 660                         */
 661                        assert(match_length >= repl_length);
 662                        if (match_length >= repl_length)
 663                          {
 664                             strreplace(start, replace, match_length,
 665                                        repl_length, (int)(end - start));
 666                             end -= match_length - repl_length;
 667                             free(replace);
 668                             code_idx -= sequences[seq].savesize;
 669                             seq = 0;    /* restart search for matches */
 670                          }
 671                        else
 672                          {
 673                             /* actually, we should never get here (match_length<repl_length) */
 674                             assert(0);
 675                             seq++;
 676                          }      /* if */
 677                     }
 678                   else
 679                     {
 680                        seq++;
 681                     }           /* if */
 682                }                /* while */
 683              assert(sequences[seq].find == NULL);
 684              filewrite(start);
 685           }                     /* if */
 686         assert(start < end);
 687         start += strlen(start) + 1;     /* to next string */
 688      }                          /* while (start<end) */
 689 }
 690
 691 #undef SCPACK_TABLE