/*  Pawn compiler - Staging buffer and optimizer

 *

 *  The staging buffer

 *  ------------------

 *  The staging buffer allows buffered output of generated code, deletion

 *  of redundant code, optimization by a tinkering process and reversing

 *  the ouput of evaluated expressions (which is used for the reversed

 *  evaluation of arguments in functions).

 *  Initially, stgwrite() writes to the file directly, but after a call to

 *  stgset(TRUE), output is redirected to the buffer. After a call to

 *  stgset(FALSE), stgwrite()'s output is directed to the file again. Thus

 *  only one routine is used for writing to the output, which can be

 *  buffered output or direct output.

 *

 *  staging buffer variables:   stgbuf  - the buffer

 *                              stgidx  - current index in the staging buffer

 *                              staging - if true, write to the staging buffer;

 *                                        if false, write to file directly.

 *

 * The peephole optimizer uses a dual "pipeline". The staging buffer (described

 * above) gets optimized for each expression or sub-expression in a function

 * call. The peephole optimizer is recursive, but it does not span multiple

 * sub-expressions. However, the data gets written to a second buffer that

 * behaves much like the staging buffer. This second buffer gathers all

 * optimized strings from the staging buffer for a complete expression. The

 * peephole optmizer then runs over this second buffer to find optimzations

 * across function parameter boundaries.

 *

 *

 *  Copyright (c) ITB CompuPhase, 1997-2006

 *

 *  This software is provided "as-is", without any express or implied warranty.

 *  In no event will the authors be held liable for any damages arising from

 *  the use of this software.

 *

 *  Permission is granted to anyone to use this software for any purpose,

 *  including commercial applications, and to alter it and redistribute it

 *  freely, subject to the following restrictions:

 *

 *  1.  The origin of this software must not be misrepresented; you must not

 *      claim that you wrote the original software. If you use this software in

 *      a product, an acknowledgment in the product documentation would be

 *      appreciated but is not required.

 *  2.  Altered source versions must be plainly marked as such, and must not be

 *      misrepresented as being the original software.

 *  3.  This notice may not be removed or altered from any source distribution.

 *

 *  Version: $Id$

 */

#include <assert.h>

#include <stdio.h>

#include <stdlib.h>     /* for atoi() */

#include <string.h>

#include <ctype.h>

#if defined FORTIFY

  #include <alloc/fortify.h>

#endif

#include "sc.h"

#if defined _MSC_VER

  #pragma warning(push)

  #pragma warning(disable:4125)  /* decimal digit terminates octal escape sequence */

#endif

#include "sc7.scp"

#if defined _MSC_VER

  #pragma warning(pop)

#endif

static int stgstring(char *start,char *end);

static void stgopt(char *start,char *end,int (*outputfunc)(char *str));

#define sSTG_GROW   512

#define sSTG_MAX    20480

static char *stgbuf=NULL;

static int stgmax=0;    /* current size of the staging buffer */

static char *stgpipe=NULL;

static int pipemax=0;   /* current size of the stage pipe, a second staging buffer */

static int pipeidx=0;

#define CHECK_STGBUFFER(index) if ((int)(index)>=stgmax)  grow_stgbuffer(&stgbuf, stgmax, (index)+1)

#define CHECK_STGPIPE(index)   if ((int)(index)>=pipemax) grow_stgbuffer(&stgpipe, pipemax, (index)+1)

static void grow_stgbuffer(char **buffer, int curmax, int requiredsize)

{

  char *p;

  int clear= (*buffer==NULL); /* if previously none, empty buffer explicitly */

  assert(curmax<requiredsize);

  /* if the staging buffer (holding intermediate code for one line) grows

   * over a few kBytes, there is probably a run-away expression

   */

  if (requiredsize>sSTG_MAX)

    error(102,"staging buffer");    /* staging buffer overflow (fatal error) */

  curmax=requiredsize+sSTG_GROW;

  if (*buffer!=NULL)

    p=(char *)realloc(*buffer,curmax*sizeof(char));

  else

    p=(char *)malloc(curmax*sizeof(char));

  if (p==NULL)

    error(102,"staging buffer");    /* staging buffer overflow (fatal error) */

  *buffer=p;

  if (clear)

    **buffer='\0';

}

SC_FUNC void stgbuffer_cleanup(void)

{

  if (stgbuf!=NULL) {

    free(stgbuf);

    stgbuf=NULL;

    stgmax=0;

  } /* if */

  if (stgpipe!=NULL) {

    free(stgpipe);

    stgpipe=NULL;

    pipemax=0;

    pipeidx=0;

  } /* if */

}

/* the variables "stgidx" and "staging" are declared in "scvars.c" */

/*  stgmark

 *

 *  Copies a mark into the staging buffer. At this moment there are three

 *  possible marks:

 *     sSTARTREORDER    identifies the beginning of a series of expression

 *                      strings that must be written to the output file in

 *                      reordered order

 *    sENDREORDER       identifies the end of 'reverse evaluation'

 *    sEXPRSTART + idx  only valid within a block that is evaluated in

 *                      reordered order, it identifies the start of an

 *                      expression; the "idx" value is the argument position

 *

 *  Global references: stgidx  (altered)

 *                     stgbuf  (altered)

 *                     staging (referred to only)

 */

SC_FUNC void stgmark(char mark)

{

  if (staging) {

    CHECK_STGBUFFER(stgidx);

    stgbuf[stgidx++]=mark;

  } /* if */

}

static int rebuffer(char *str)

{

  if (sc_status==statWRITE) {

    if (pipeidx>=2 && stgpipe[pipeidx-1]=='\0' && stgpipe[pipeidx-2]!='\n')

      pipeidx-=1;                      /* overwrite last '\0' */

    while (*str!='\0') {               /* copy to staging buffer */

      CHECK_STGPIPE(pipeidx);

      stgpipe[pipeidx++]=*str++;

    } /* while */

    CHECK_STGPIPE(pipeidx);

    stgpipe[pipeidx++]='\0';

  } /* if */

  return TRUE;

}

static int filewrite(char *str)

{

  if (sc_status==statWRITE)

    return pc_writeasm(outf,str);

  return TRUE;

}

/*  stgwrite

 *

 *  Writes the string "st" to the staging buffer or to the output file. In the

 *  case of writing to the staging buffer, the terminating byte of zero is

 *  copied too, but... the optimizer can only work on complete lines (not on

 *  fractions of it. Therefore if the string is staged, if the last character

 *  written to the buffer is a '\0' and the previous-to-last is not a '\n',

 *  the string is concatenated to the last string in the buffer (the '\0' is

 *  overwritten). This also means an '\n' used in the middle of a string isn't

 *  recognized and could give wrong results with the optimizer.

 *  Even when writing to the output file directly, all strings are buffered

 *  until a whole line is complete.

 *

 *  Global references: stgidx  (altered)

 *                     stgbuf  (altered)

 *                     staging (referred to only)

 */

SC_FUNC void stgwrite(const char *st)

{

  int len;

  if (staging) {

    assert(stgidx==0 || stgbuf!=NULL);  /* staging buffer must be valid if there is (apparently) something in it */

    if (stgidx>=2 && stgbuf[stgidx-1]=='\0' && stgbuf[stgidx-2]!='\n')

      stgidx-=1;                       /* overwrite last '\0' */

    while (*st!='\0') {                /* copy to staging buffer */

      CHECK_STGBUFFER(stgidx);

      stgbuf[stgidx++]=*st++;

    } /* while */

    CHECK_STGBUFFER(stgidx);

    stgbuf[stgidx++]='\0';

  } else {

    len=(stgbuf!=NULL) ? strlen(stgbuf) : 0;

    CHECK_STGBUFFER(len+strlen(st)+1);

    strcat(stgbuf,st);

    len=strlen(stgbuf);

    if (len>0 && stgbuf[len-1]=='\n') {

      filewrite(stgbuf);

      stgbuf[0]='\0';

    } /* if */

  } /* if */

}

/*  stgout

 *

 *  Writes the staging buffer to the output file via stgstring() (for

 *  reversing expressions in the buffer) and stgopt() (for optimizing). It

 *  resets "stgidx".

 *

 *  Global references: stgidx  (altered)

 *                     stgbuf  (referred to only)

 *                     staging (referred to only)

 */

SC_FUNC void stgout(int index)

{

  int reordered=0;

  int idx;

  if (!staging)

    return;

  assert(pipeidx==0);

  /* first pass: sub-expressions */

  if (sc_status==statWRITE)

    reordered=stgstring(&stgbuf[index],&stgbuf[stgidx]);

  stgidx=index;

  /* second pass: optimize the buffer created in the first pass */

  if (sc_status==statWRITE) {

    if (reordered) {

      stgopt(stgpipe,stgpipe+pipeidx,filewrite);

    } else {

      /* there is no sense in re-optimizing if the order of the sub-expressions

       * did not change; so output directly

       */

      for (idx=0; idx<pipeidx; idx+=strlen(stgpipe+idx)+1)

        filewrite(stgpipe+idx);

    } /* if */

  } /* if */

  pipeidx=0;  /* reset second pipe */

}

typedef struct {

  char *start,*end;

} argstack;

/*  stgstring

 *

 *  Analyses whether code strings should be output to the file as they appear

 *  in the staging buffer or whether portions of it should be re-ordered.

 *  Re-ordering takes place in function argument lists; Pawn passes arguments

 *  to functions from right to left. When arguments are "named" rather than

 *  positional, the order in the source stream is indeterminate.

 *  This function calls itself recursively in case it needs to re-order code

 *  strings, and it uses a private stack (or list) to mark the start and the

 *  end of expressions in their correct (reversed) order.

 *  In any case, stgstring() sends a block as large as possible to the

 *  optimizer stgopt().

 *

 *  In "reorder" mode, each set of code strings must start with the token

 *  sEXPRSTART, even the first. If the token sSTARTREORDER is represented

 *  by '[', sENDREORDER by ']' and sEXPRSTART by '|' the following applies:

 *     '[]...'     valid, but useless; no output

 *     '[|...]     valid, but useless; only one string

 *     '[|...|...] valid and usefull

 *     '[...|...]  invalid, first string doesn't start with '|'

 *     '[|...|]    invalid

 */

static int stgstring(char *start,char *end)

{

  char *ptr;

  int nest,argc,arg;

  argstack *stack;

  int reordered=0;

  while (start<end) {

    if (*start==sSTARTREORDER) {

      start+=1;         /* skip token */

      /* allocate a argstack with sMAXARGS items */

      stack=(argstack *)malloc(sMAXARGS*sizeof(argstack));

      if (stack==NULL)

        error(103);     /* insufficient memory */

      reordered=1;      /* mark that the expression is reordered */

      nest=1;           /* nesting counter */

      argc=0;           /* argument counter */

      arg=-1;           /* argument index; no valid argument yet */

      do {

        switch (*start) {

        case sSTARTREORDER:

          nest++;

          start++;

          break;

        case sENDREORDER:

          nest--;

          start++;

          break;

        default:

          if ((*start & sEXPRSTART)==sEXPRSTART) {

            if (nest==1) {

              if (arg>=0)

                stack[arg].end=start-1; /* finish previous argument */

              arg=(unsigned char)*start - sEXPRSTART;

              stack[arg].start=start+1;

              if (arg>=argc)

                argc=arg+1;

            } /* if */

            start++;

          } else {

            start+=strlen(start)+1;

          } /* if */

        } /* switch */

      } while (nest); /* enddo */

      if (arg>=0)

        stack[arg].end=start-1;   /* finish previous argument */

      while (argc>0) {

        argc--;

        stgstring(stack[argc].start,stack[argc].end);

      } /* while */

      free(stack);

    } else {

      ptr=start;

      while (ptr<end && *ptr!=sSTARTREORDER)

        ptr+=strlen(ptr)+1;

      stgopt(start,ptr,rebuffer);

      start=ptr;

    } /* if */

  } /* while */

  return reordered;

}

/*  stgdel

 *

 *  Scraps code from the staging buffer by resetting "stgidx" to "index".

 *

 *  Global references: stgidx (altered)

 *                     staging (reffered to only)

 */

SC_FUNC void stgdel(int index,cell code_index)

{

  if (staging) {

    stgidx=index;

    code_idx=code_index;

  } /* if */

}

SC_FUNC int stgget(int *index,cell *code_index)

{

  if (staging) {

    *index=stgidx;

    *code_index=code_idx;

  } /* if */

  return staging;

}

/*  stgset

 *

 *  Sets staging on or off. If it's turned off, the staging buffer must be

 *  initialized to an empty string. If it's turned on, the routine makes sure

 *  the index ("stgidx") is set to 0 (it should already be 0).

 *

 *  Global references: staging  (altered)

 *                     stgidx   (altered)

 *                     stgbuf   (contents altered)

 */

SC_FUNC void stgset(int onoff)

{

  staging=onoff;

  if (staging){

    assert(stgidx==0);

    stgidx=0;

    CHECK_STGBUFFER(stgidx);

    /* write any contents that may be put in the buffer by stgwrite()

     * when "staging" was 0

     */

    if (strlen(stgbuf)>0)

      filewrite(stgbuf);

  } /* if */

  stgbuf[0]='\0';

}

/* phopt_init

 * Initialize all sequence strings of the peehole optimizer. The strings

 * are embedded in the .EXE file in compressed format, here we expand

 * them (and allocate memory for the sequences).

 */

static SEQUENCE *sequences;

SC_FUNC int phopt_init(void)

{

  int number, i, len;

  char str[160];

  /* count number of sequences */

  for (number=0; sequences_cmp[number].find!=NULL; number++)

    /* nothing */;

  number++;             /* include an item for the NULL terminator */

  if ((sequences=(SEQUENCE*)malloc(number * sizeof(SEQUENCE)))==NULL)

    return FALSE;

  /* pre-initialize all to NULL (in case of failure) */

  for (i=0; i<number; i++) {

    sequences[i].find=NULL;

    sequences[i].replace=NULL;

    sequences[i].savesize=0;

  } /* for */

  /* expand all strings */

  for (i=0; i<number-1; i++) {

    len = strexpand(str,(unsigned char*)sequences_cmp[i].find,sizeof str,SCPACK_TABLE);

    assert(len<=sizeof str);

    assert(len==(int)strlen(str)+1);

    sequences[i].find=(char*)malloc(len);

    if (sequences[i].find!=NULL)

      strcpy(sequences[i].find,str);

    len = strexpand(str,(unsigned char*)sequences_cmp[i].replace,sizeof str,SCPACK_TABLE);

    assert(len<=sizeof str);

    assert(len==(int)strlen(str)+1);

    sequences[i].replace=(char*)malloc(len);

    if (sequences[i].replace!=NULL)

      strcpy(sequences[i].replace,str);

    sequences[i].savesize=sequences_cmp[i].savesize;

    if (sequences[i].find==NULL || sequences[i].replace==NULL)

      return phopt_cleanup();

  } /* for */

  return TRUE;

}

SC_FUNC int phopt_cleanup(void)

{

  int i;

  if (sequences!=NULL) {

    i=0;

    while (sequences[i].find!=NULL || sequences[i].replace!=NULL) {

      if (sequences[i].find!=NULL)

        free(sequences[i].find);

      if (sequences[i].replace!=NULL)

        free(sequences[i].replace);

      i++;

    } /* while */

    free(sequences);

    sequences=NULL;

  } /* if */

  return FALSE;

}

#define MAX_OPT_VARS    5

#define MAX_OPT_CAT     5       /* max. values that are concatenated */

#if sNAMEMAX > (PAWN_CELL_SIZE/4) * MAX_OPT_CAT

  #define MAX_ALIAS       sNAMEMAX

#else

  #define MAX_ALIAS       (PAWN_CELL_SIZE/4) * MAX_OPT_CAT

#endif

static int matchsequence(char *start,char *end,char *pattern,

                         char symbols[MAX_OPT_VARS][MAX_ALIAS+1],

                         int *match_length)

{

  int var,i;

  char str[MAX_ALIAS+1];

  char *start_org=start;

  cell value;

  char *ptr;

  *match_length=0;

  for (var=0; var<MAX_OPT_VARS; var++)

    symbols[var][0]='\0';

  while (*start=='\t' || *start==' ')

    start++;

  while (*pattern) {

    if (start>=end)

      return FALSE;

    switch (*pattern) {

    case '%':   /* new "symbol" */

      pattern++;

      assert(isdigit(*pattern));

      var=atoi(pattern) - 1;

      assert(var>=0 && var<MAX_OPT_VARS);

      assert(*start=='-' || alphanum(*start));

      for (i=0; start<end && (*start=='-' || *start=='+' || alphanum(*start)); i++,start++) {

        assert(i<=MAX_ALIAS);

        str[i]=*start;

      } /* for */

      str[i]='\0';

      if (symbols[var][0]!='\0') {

        if (strcmp(symbols[var],str)!=0)

          return FALSE; /* symbols should be identical */

      } else {

        strcpy(symbols[var],str);

      } /* if */

      break;

    case '-':

      value=-strtol(pattern+1,&pattern,16);

      ptr=itoh((ucell)value);

      while (*ptr!='\0') {

        if (tolower(*start) != tolower(*ptr))

          return FALSE;

        start++;

        ptr++;

      } /* while */

      pattern--;  /* there is an increment following at the end of the loop */

      break;

    case ' ':

      if (*start!='\t' && *start!=' ')

        return FALSE;

      while (start<end && (*start=='\t' || *start==' '))

        start++;

      break;

    case '!':

      while (start<end && (*start=='\t' || *start==' '))

        start++;                /* skip trailing white space */

      if (*start==';')

        while (start<end && *start!='\n')

          start++;              /* skip trailing comment */

      if (*start!='\n')

        return FALSE;

      assert(*(start+1)=='\0');

      start+=2;                 /* skip '\n' and '\0' */

      if (*(pattern+1)!='\0')

        while (start<end && *start=='\t' || *start==' ')

          start++;              /* skip leading white space of next instruction */

      break;

    default:

      if (tolower(*start) != tolower(*pattern))

        return FALSE;

      start++;

    } /* switch */

    pattern++;

  } /* while */

  *match_length=(int)(start-start_org);

  return TRUE;

}

static char *replacesequence(char *pattern,char symbols[MAX_OPT_VARS][MAX_ALIAS+1],int *repl_length)

{

  char *lptr;

  int var;

  char *buffer;

  /* calculate the length of the new buffer

   * this is the length of the pattern plus the length of all symbols (note

   * that the same symbol may occur multiple times in the pattern) plus

   * line endings and startings ('\t' to start a line and '\n\0' to end one)

   */

  assert(repl_length!=NULL);

  *repl_length=0;

  lptr=pattern;

  while (*lptr) {

    switch (*lptr) {

    case '%':

      lptr++;           /* skip '%' */

      assert(isdigit(*lptr));

      var=atoi(lptr) - 1;

      assert(var>=0 && var<MAX_OPT_VARS);

      assert(symbols[var][0]!='\0');    /* variable should be defined */

      *repl_length+=strlen(symbols[var]);

      break;

    case '!':

      *repl_length+=3;  /* '\t', '\n' & '\0' */

      break;

    default:

      *repl_length+=1;

    } /* switch */

    lptr++;

  } /* while */

  /* allocate a buffer to replace the sequence in */

  if ((buffer=(char*)malloc(*repl_length))==NULL)

    return (char*)error(103);

  /* replace the pattern into this temporary buffer */

  lptr=buffer;

  *lptr++='\t';         /* the "replace" patterns do not have tabs */

  while (*pattern) {

    assert((int)(lptr-buffer)<*repl_length);

    switch (*pattern) {

    case '%':

      /* write out the symbol */

      pattern++;

      assert(isdigit(*pattern));

      var=atoi(pattern) - 1;