/* bfc.c - Don Yang (uguu.org)

   Optimizing BF to C compiler.

   08/29/04
                                                                           */
/*@ -branchstate -usedef -nullret @*/

#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/* Maximum data size for output program */
#define MAX_DATA_TAPE_SIZE    0x10000

/* String used for indentation */
#define INDENT                "\t"

/* Minimum number of zero cell operations required to switch to using memset */
#define MEMSET_THRESHOLD      4

/* Source templates
   Define PARSE_ARGS to allow output C programs to open files specified
   on command line for input/output (makes program run slower).         */
#define COMMON_HEADER                                                \
   "#ifdef _WIN32\n"                                                 \
   INDENT"#include<windows.h>\n"                                     \
   INDENT"#include<stdio.h>\n"                                       \
   INDENT"#include<string.h>\n"                                      \
   INDENT"#pragma warning(disable:4100)\n"                           \
   "#else\n"                                                         \
   INDENT"#include<signal.h>\n"                                      \
   INDENT"#include<stdio.h>\n"                                       \
   INDENT"#include<stdlib.h>\n"                                      \
   INDENT"#include<string.h>\n"                                      \
   "#endif\n"                                                        \
   "\n"                                                              \
   "#ifdef _WIN32\n"                                                 \
   "static LONG WINAPI ExceptionHandler("                            \
      "/*@unused@*/LPEXCEPTION_POINTERS p)\n"                        \
   "{\n"                                                             \
   INDENT"(void)puts(\"fatal exception caught\");\n"                 \
   INDENT"ExitProcess(1);\n"                                         \
   INDENT"return EXCEPTION_EXECUTE_HANDLER;\n"                       \
   "}\n"                                                             \
   "static void TrapExceptions(void)\n"                              \
   "{\n"                                                             \
   INDENT"(void)SetUnhandledExceptionFilter(ExceptionHandler);\n"    \
   "}\n"                                                             \
   "#else\n"                                                         \
   "static void ExceptionHandler(/*@unused@*/int s)\n"               \
   "{\n"                                                             \
   INDENT"(void)puts(\"fatal exception caught\");\n"                 \
   INDENT"exit(EXIT_FAILURE);\n"                                     \
   "}\n"                                                             \
   "static void TrapExceptions(void)\n"                              \
   "{\n"                                                             \
   INDENT"(void)signal(SIGSEGV, ExceptionHandler);\n"                \
   "}\n"                                                             \
   "#endif\n"

#ifdef PARSE_ARGS
   #define CODE_HEADER                                                     \
      "/*[*/\n"                                                            \
      COMMON_HEADER                                                        \
      "static int Tape[%d];\n"                                             \
      "int main(int argc, char **argv)\n"                                  \
      "{\n"                                                                \
      INDENT"FILE *infile, *outfile;\n"                                    \
      INDENT"int *x;\n"                                                    \
      INDENT"TrapExceptions();\n"                                          \
      INDENT"infile = stdin;\n"                                            \
      INDENT"outfile = stdout;\n"                                          \
      INDENT"if( argc > 1 )\n"                                             \
      INDENT"{\n"                                                          \
      INDENT INDENT"if( (infile = fopen(argv[1], \"rb\")) == NULL )\n"     \
      INDENT INDENT INDENT                                                 \
         "return printf(\"Can not open %%s for reading\\n\", argv[1]);\n"  \
      INDENT INDENT"if( argc > 2 )\n"                                      \
      INDENT INDENT"{\n"                                                   \
      INDENT INDENT INDENT"if( (outfile = fopen(argv[2], \"wb+\")) == NULL )\n"\
      INDENT INDENT INDENT INDENT                                          \
         "return printf(\"Can not open %%s for writing\\n\", argv[2]);\n"  \
      INDENT INDENT"}\n"                                                   \
      INDENT"}\n"                                                          \
      INDENT"x = (int*)memset(Tape, 0, %d * sizeof(int));\n"
   #define CODE_FOOTER                                                     \
      INDENT"(void)fclose(infile);\n"                                      \
      INDENT"(void)fclose(outfile);\n"                                     \
      INDENT"return 0;\n"                                                  \
      "}\n"                                                                \
      "/*]*/\n"
   #define CODE_GETC "fgetc(infile)"
   #define CODE_PUTC "(void)fputc(*x, outfile)"
#else
   #define CODE_HEADER                                                     \
      "/*[*/\n"                                                            \
      COMMON_HEADER                                                        \
      "static int Tape[%d];\n"                                             \
      "int main(void)\n"                                                   \
      "{\n"                                                                \
      INDENT"int *x;\n"                                                    \
      INDENT"TrapExceptions();\n"                                          \
      INDENT"x = (int*)memset(Tape, 0, %d * sizeof(int));\n"
   #define CODE_FOOTER                                                     \
      INDENT"return 0;\n"                                                  \
      "}\n"                                                                \
      "/*]*/\n"
   #define CODE_GETC "getchar()"
   #define CODE_PUTC "(void)putchar(*x)"
#endif


typedef struct b_atom
{
   int offset, delta;
   struct b_atom *l, *r;
} BAtom;

typedef struct
{
   /*@only@*/BAtom *a;  /* Changes to tape */
   int cursor;          /* Cursor position delta */
   int op;              /* [ ] , . operators or 0 */
} Atom;

typedef struct _node
{
   union
   {
      struct _node *sub;
      /*@only@*/Atom *atom;
   } x;
   int leaf, mult;
   struct _node *next;
} Node;


static int AddDelta(Atom *a, int delta);
static int AddDeltaA(BAtom **a, int offset, int delta);
static /*@null@*/Atom *CreateAtom(void);
static /*@null@*/Node *CreateNode(/*@null@*/Atom *a);
static void DumpAtom(FILE *outfile, int depth, Atom *a);
static void DumpAtomA(FILE *outfile, int depth, BAtom *a, int *cursor);
static void DumpParseTree(FILE *outfile, int depth, Node *tree);
static void FreeAtom(/*@only@*/Atom *a) /*@releases a@*/;
static void FreeAtomA(/*@only@*/BAtom *a) /*@releases a@*/;
static void FreeParseTree(/*@only@*//*@null@*/Node *root) /*@releases root@*/;
static /*@null@*/Atom *GetAtom(FILE *infile);
static void Indent(FILE *outfile, int depth);
static int IsCopyExpr(Node *expr);
static int IsCopyExprA(BAtom *a, int base);
static int IsMassZeroExpr(Node *expr);
static int IsNopAtom(Atom *a);
static int IsNopAtomA(BAtom *a);
static int IsSearchExpr(Node *expr);
static int IsShiftAtom(Atom *a);
static int IsZeroExpr(Node *expr);
static /*@null@*/Node *Parse(FILE *infile, int depth);
static void WriteAtom(FILE *outfile, int depth, Atom *atom);
static void WriteAtomA(FILE *outfile, int depth, int t, BAtom *a, int *cursor);
static void WriteCode(FILE *outfile, Node *node);
static void WriteCopyExpr(FILE *outfile, int depth, Node *expr);
static void WriteCopyExprA(FILE *outfile, int depth, BAtom *a);
static void WriteDelta(FILE *outfile, int delta);
static void WriteIndex(FILE *outfile, int index);
static int WriteMassZeroExpr(FILE *outfile, int depth, Node **node);
static void WriteSearchExpr(FILE *outfile, int depth, int step);
static void WriteSubCode(FILE *outfile, int depth, Node *node);
static int WriteZeroExpr(FILE *outfile, int depth);

/******************************************************************** main */
int main(int argc, char **argv)
{
   FILE *infile, *outfile;
   Node *tree;

   infile = stdin;
   outfile = stdout;
   if( argc > 1 )
   {
      if( (infile = fopen(argv[1], "rb")) == NULL )
      {
         printf("Can not open %s\n", argv[1]);
         return -1;
      }
      if( argc > 2 )
      {
         if( (outfile = fopen(argv[2], "wb+")) == NULL )
         {
            (void)fclose(infile);
            printf("Can not create %s\n", argv[2]);
            return -1;
         }
      }
   }

   if( (tree = Parse(infile, 0)) != NULL )
   {
      /* Write C code */
      WriteCode(outfile, tree);

      /* Write indented parse tree.
         This ensures the output is still executable with a BF interpreter. */
      (void)fputs("/*{\n", outfile);
      DumpParseTree(outfile, 1, tree);
      (void)fputs("}*/\n", outfile);

      FreeParseTree(tree);
   }

   (void)fclose(infile);
   (void)fclose(outfile);
   return 0;
}


/**************************************************************** AddDelta */
static int AddDelta(Atom *a, int delta)
{
   return AddDeltaA(&(a->a), a->cursor, delta);
}
static int AddDeltaA(BAtom **a, int offset, int delta)
{
   /*@dependent@*/BAtom *A;
   int cmp;

   for(; *a != NULL; a = (cmp < 0) ? &((*a)->l) : &((*a)->r))
   {
      if( (cmp = (offset - (*a)->offset)) == 0 )
      {
         (*a)->delta += delta;
         return 0;
      }
   }
   if( (*a = A = (BAtom*)malloc(sizeof(BAtom))) == NULL )
      /*@i2@*/return -1;
   A->offset = offset;
   A->delta = delta;
   A->l = A->r = NULL;
   /*@i1@*/return 0;
}

/************************************************************** CreateAtom */
static /*@null@*/Atom *CreateAtom(void)
{
   /*@dependent@*/Atom *a;

   if( (a = (Atom*)malloc(sizeof(Atom))) == NULL )
      return NULL;
   a->a = NULL;
   a->cursor = a->op = 0;
   /*@i1@*/return a;
}

/************************************************************** CreateNode */
static /*@null@*/Node *CreateNode(/*@null@*/Atom *a)
{
   /*@dependent@*/Node *n;

   if( (n = (Node*)malloc(sizeof(Node))) == NULL )
      return NULL;
   if( a == NULL )
   {
      n->x.sub = n->next = NULL;
      n->leaf = 0;
   }
   else
   {
      /*@i2@*/n->x.atom = a;
      n->leaf = 1;
      n->next = NULL;
   }
   n->mult = -1;
   return n;
}

/**************************************************************** DumpAtom */
static void DumpAtom(FILE *outfile, int depth, Atom *a)
{
   int i;

   if( a->op != 0 )
   {
      Indent(outfile, depth);
      fprintf(outfile, "%c\n", (char)(a->op));
      return;
   }
   i = 0;
   DumpAtomA(outfile, depth, a->a, &i);

   if( i != a->cursor )
   {
      Indent(outfile, depth);
      if( i > a->cursor ) for(; i > a->cursor; i--) (void)fputc('<', outfile);
      else                for(; i < a->cursor; i++) (void)fputc('>', outfile);
      (void)fputc('\n', outfile);
   }
}
static void DumpAtomA(FILE *outfile, int depth, BAtom *a, int *cursor)
{
   int i;

   for(; a != NULL; a = a->r)
   {
      DumpAtomA(outfile, depth, a->l, cursor);
      if( a->delta != 0 )
      {
         Indent(outfile, depth);
         for(; *cursor > a->offset; --*cursor) (void)fputc('<', outfile);
         for(; *cursor < a->offset; ++*cursor) (void)fputc('>', outfile);

         if( a->delta < 0 )
            for(i = 0; i > a->delta; i--) (void)fputc('-', outfile);
         else
            for(i = 0; i < a->delta; i++) (void)fputc('+', outfile);
         (void)fputc('\n', outfile);
      }
   }
}

/*********************************************************** DumpParseTree */
static void DumpParseTree(FILE *outfile, int depth, Node *tree)
{
   int prune;

   for(prune = (depth > 1) ? 0 : 1; tree != NULL; tree = tree->next)
   {
      if( tree->leaf != 0 )
      {
         DumpAtom(outfile, depth, tree->x.atom);
         prune = 0;
      }
      else
      {
         /* Prune loops immediately following [].
            This ensures feeding the generated C code back to the compiler
            will produce the same C code after two generations.            */
         if( prune != 0 )
            continue;

         if( IsZeroExpr(tree->x.sub) != 0 )
         {
            Indent(outfile, depth);
            (void)fputs("[-]\n", outfile);
         }
         else
         {
            Indent(outfile, depth); (void)fputs("[\n", outfile);
            DumpParseTree(outfile, depth + 1, tree->x.sub);
            Indent(outfile, depth); (void)fputs("]\n", outfile);
         }
         prune = 1;
      }
   }
}

/**************************************************************** FreeAtom */
static void FreeAtom(/*@only@*/Atom *a) /*@releases a@*/
{
   FreeAtomA(a->a);
   free(a);
}
static void FreeAtomA(/*@only@*/BAtom *a) /*@releases a@*/
{
   BAtom *n;

   for(; a != NULL; a = n)
   {
      FreeAtomA(a->l);
      n = a->r;
      free(a);
   }
}

/*********************************************************** FreeParseTree */
static void FreeParseTree(/*@only@*//*@null@*/Node *root) /*@releases root@*/
{
   Node *n;

   for(; root != NULL; root = n)
   {
      if( root->leaf == 0 )
         FreeParseTree(root->x.sub);
      n = root->next;
      free(root);
   }
}

/***************************************************************** GetAtom */
static /*@null@*/Atom *GetAtom(FILE *infile)
{
   Atom *a;
   int c;

   if( (c = fgetc(infile)) == EOF )
      return NULL;
   if( (a = CreateAtom()) == NULL )
   {
      (void)puts("out of memory");
      return NULL;
   }
   if( c == (int)'[' || c == (int)']' || c == (int)',' || c == (int)'.' )
   {
      a->op = c;
      return a;
   }

   do
   {
      if( c == (int)'<' )        { a->cursor--; }
      else if( c == (int)'>' )   { a->cursor++; }
      else if( c == (int)'-' )
      {
         if( AddDelta(a, -1) != 0 )
         {
            FreeAtom(a);
            (void)puts("out of memory");
            return NULL;
         }
      }
      else if( c == (int)'+' )
      {
         if( AddDelta(a, +1) != 0 )
         {
            FreeAtom(a);
            (void)puts("out of memory");
            return NULL;
         }
      }
      else if( c == (int)'[' || c == (int)']' ||
               c == (int)',' || c == (int)'.' )
      {
         (void)ungetc(c, infile);
         break;
      }
   } while( (c = fgetc(infile)) != EOF );
   return a;
}

/****************************************************************** Indent */
static void Indent(FILE *outfile, int depth)
{
   int i;
   for(i = 0; i < depth; i++)
      (void)fputs(INDENT, outfile);
}

/************************************************************** IsCopyExpr */
static int IsCopyExpr(Node *expr)
{
   int base, delta;

   for(base = delta = 0; expr != NULL; expr = expr->next)
   {
      if( expr->leaf == 0 )         return 0;
      if( expr->x.atom->op != 0 )   return 0;
      delta += IsCopyExprA(expr->x.atom->a, base);
      base -= expr->x.atom->cursor;
   }

   return (base == 0 && delta == -1) ? 1 : 0;
}
static int IsCopyExprA(BAtom *a, int base)
{
   int cmp;

   for(; a != NULL; a = (cmp < 0) ? a->l : a->r)
   {
      if( (cmp = (base - a->offset)) == 0 )
         return a->delta;
   }
   return 0;
}

/********************************************************** IsMassZeroExpr */
static int IsMassZeroExpr(Node *expr)
{
   int l, r, x;

   for(l = r = x = 0; expr != NULL; expr = expr->next)
   {
      if( expr->leaf != 0 )
      {
         /* Check for continuous region */
         if( IsShiftAtom(expr->x.atom) == 0 )
            break;
         if( x + expr->x.atom->cursor < l - 1 ||
             x + expr->x.atom->cursor > r + 1 )
            break;
         x += expr->x.atom->cursor;
      }
      else
      {
         /* Check for zero operation */
         if( IsZeroExpr(expr->x.sub) == 0 )
            break;
         if( x < l ) l = x;
         if( x > r ) r = x;
      }
   }
   assert(r >= l && l <= 0);
   return (r - l >= MEMSET_THRESHOLD) ? 1 : 0;
}

/*************************************************************** IsNopAtom */
static int IsNopAtom(Atom *a)
{
   return (a->op != 0) ? 0 : (a->cursor != 0) ? 0 : IsNopAtomA(a->a);
}
static int IsNopAtomA(BAtom *a)
{
   for(; a != NULL; a = a->r)
   {
      if( a->delta != 0 )           return 0;
      if( IsNopAtomA(a->l) == 0 )   return 0;
   }
   return 1;
}

/************************************************************ IsSearchExpr */
static int IsSearchExpr(Node *expr)
{
   int shift;

   for(shift = 0; expr != NULL; expr = expr->next)
   {
      if( expr->leaf == 0 )                  return 0;
      if( IsShiftAtom(expr->x.atom) == 0 )   return 0;
      shift += expr->x.atom->cursor;
   }
   return shift;
}

/************************************************************* IsShiftAtom */
static int IsShiftAtom(Atom *a)
{
   return (a->op != 0) ? 0 : IsNopAtomA(a->a);
}

/************************************************************** IsZeroExpr */
static int IsZeroExpr(Node *expr)
{
   if( expr->leaf == 0 || expr->next != NULL )
      return 0;
   if( expr->x.atom->op != 0 ||
       expr->x.atom->cursor != 0 ||
       expr->x.atom->a == NULL )
      return 0;
   if( expr->x.atom->a->l != NULL ||
       expr->x.atom->a->r != NULL ||
       expr->x.atom->a->delta != -1 )
      return 0;
   return 1;
}

/******************************************************************* Parse */
static /*@null@*/Node *Parse(FILE *infile, int depth)
{
   Node *head, *tail, *node;
   Atom *a;

   head = tail = NULL;
   while( (a = GetAtom(infile)) != NULL )
   {
      if( IsNopAtom(a) != 0 )
      {
         FreeAtom(a);
         continue;
      }
      if( a->op == (int)'[' )
      {
         /* Start loop */
         FreeAtom(a);
         if( (node = CreateNode(NULL)) == NULL )
         {
            (void)puts("out of memory");
            FreeParseTree(head);
            return NULL;
         }
         if( (node->x.sub = Parse(infile, depth + 1)) == NULL )
         {
            FreeParseTree(head);
            free(node);
            return NULL;
         }
      }
      else if( a->op == (int)']' )
      {
         /* Close current loop */
         if( head == NULL )
         {
            /* Possible [] infinite loop, return NOP atom nontheless */
            if( (head = CreateNode(a)) == NULL )
            {
               (void)puts("out of memory");
               FreeAtom(a);
               return NULL;
            }
            a->op = 0;
            assert(a->a == NULL && a->cursor == 0);
         }
         else
         {
            FreeAtom(a);
         }
         return head;
      }
      else
      {
         /* Non-looping operation */
         if( (node = CreateNode(a)) == NULL )
         {
            (void)puts("out of memory");
            FreeParseTree(head);
            FreeAtom(a);
            return NULL;
         }
      }

      /* Add to parse tree */
      assert(node != NULL);
      if( tail == NULL )
      {
         head = tail = node;
      }
      else
      {
         tail->next = node;
         tail = node;
      }
   }

   if( depth > 0 )
   {
      FreeParseTree(head);
      printf("unbalanced [] at depth %d\n", depth);
      return NULL;
   }
   return head;
}

/*************************************************************** WriteAtom */
static void WriteAtom(FILE *outfile, int depth, Atom *atom)
{
   int cursor;

   if( atom->op == (int)'.' )
   {
      Indent(outfile, depth);
      (void)fputs(CODE_PUTC";\n", outfile);
   }
   else if( atom->op == (int)',' )
   {
      Indent(outfile, depth);
      (void)fputs("*x = "CODE_GETC";\n", outfile);
   }
   else
   {
      cursor = 0;
      WriteAtomA(outfile, depth, 1, atom->a, &cursor);
      if( (cursor = atom->cursor - cursor) != 0 )
      {
         Indent(outfile, depth);
         (void)fputc('x', outfile);
         WriteDelta(outfile, cursor);
         (void)fputs(";\n", outfile);
      }
   }
}
static void WriteAtomA(FILE *outfile, int depth, int t, BAtom *a, int *cursor)
{
   for(; a != NULL; a = a->r)
   {
      WriteAtomA(outfile, depth, 0, a->l, cursor);
      if( a->delta != 0 )
      {
         Indent(outfile, depth);

         /* Preincrement/predecrement */
         if( a->delta == 1 )
         {
            (void)fputs("++", outfile);
         }
         else if( a->delta == -1 )
         {
            (void)fputs("--", outfile);
         }

         /* Cell address */
         if( t != 0 && a->r == NULL )
         {
            /* Move cursor before writing if for last cell to be written */
            if( a->offset < *cursor )
            {
               if( a->offset == *cursor - 1 )
                  (void)fputs("*--x", outfile);
               else
                  fprintf(outfile, "*(x -= %d)", *cursor - a->offset);
            }
            else if( a->offset > *cursor )
            {
               if( a->offset == *cursor + 1 )
                  (void)fputs("*++x", outfile);
               else
                  fprintf(outfile, "*(x += %d)", a->offset - *cursor);
            }
            else
            {
               (void)fputs("*x", outfile);
            }
            *cursor = a->offset;
         }
         else
         {
            /* ... otherwise, keep cursor in same location and use offset */
            WriteIndex(outfile, a->offset - *cursor);
         }

         /* Delta */
         if( a->delta != 1 && a->delta != -1 )
            WriteDelta(outfile, a->delta);
         (void)fputs(";\n", outfile);
      }
   }
}

/*************************************************************** WriteCode */
static void WriteCode(FILE *outfile, Node *node)
{
   /* Header */
   fprintf(outfile, CODE_HEADER, MAX_DATA_TAPE_SIZE, MAX_DATA_TAPE_SIZE);

   /* Code */
   WriteSubCode(outfile, 1, node);

   /* Footer */
   (void)fputs(CODE_FOOTER, outfile);
}

/*********************************************************** WriteCopyExpr */
static void WriteCopyExpr(FILE *outfile, int depth, Node *expr)
{
   Indent(outfile, depth); (void)fputs("if( *x != 0 )\n", outfile);
   Indent(outfile, depth); (void)fputs("{\n", outfile);
   for(; expr != NULL; expr = expr->next)
   {
      assert(expr->leaf != 0);
      assert(expr->x.atom->op == 0);
      WriteCopyExprA(outfile, depth + 1, expr->x.atom->a);
   }
   Indent(outfile, depth + 1); (void)fputs("*x = 0;\n", outfile);
   Indent(outfile, depth); (void)fputs("}\n", outfile);
}
static void WriteCopyExprA(FILE *outfile, int depth, BAtom *a)
{
   for(; a != NULL; a = a->r)
   {
      WriteCopyExprA(outfile, depth, a->l);
      if( a->delta == 0 || a->offset == 0 )
         continue;
      Indent(outfile, depth);
      WriteIndex(outfile, a->offset);
      if( a->delta == 1 )
      {
         (void)fputs(" += *x;\n", outfile);
      }
      else if( a->delta == -1 )
      {
         (void)fputs(" -= *x;\n", outfile);
      }
      else
      {
         fprintf(outfile, " += %d * *x;\n", a->delta);
      }
   }
}

/************************************************************** WriteDelta */
static void WriteDelta(FILE *outfile, int delta)
{
   if( delta > 0 )
   {
      if( delta == 1 )  (void)fputs("++", outfile);
      else              fprintf(outfile, " += %d", delta);
   }
   else
   {
      if( delta == -1 ) (void)fputs("--", outfile);
      else              fprintf(outfile, " -= %d", -delta);
   }
}

/************************************************************** WriteIndex */
static void WriteIndex(FILE *outfile, int index)
{
   if( index == 0 )
   {
      (void)fputs("*x", outfile);
   }
   else
   {
      if( index > 0 )
         fprintf(outfile, "*(x + %d)", index);
      else
         fprintf(outfile, "*(x - %d)", -index);
   }
}

/******************************************************* WriteMassZeroExpr */
static int WriteMassZeroExpr(FILE *outfile, int depth, Node **node)
{
   Node *expr, *last;
   int l, r, x, x0;

   expr = last = *node;
   for(l = r = x = x0 = 0; expr != NULL; expr = expr->next)
   {
      if( expr->leaf != 0 )
      {
         /* Check for continuous region */
         if( IsShiftAtom(expr->x.atom) == 0 )
            break;
         if( x + expr->x.atom->cursor < l - 1 ||
             x + expr->x.atom->cursor > r + 1 )
            break;
         x += expr->x.atom->cursor;
      }
      else
      {
         /* Check for zero operation */
         if( IsZeroExpr(expr->x.sub) == 0 )
            break;
         if( x < l ) l = x;
         if( x > r ) r = x;
      }
      last = expr;
   }
   assert(*node != last);
   *node = last;

   Indent(outfile, depth);
   if( l == 0 )
      fprintf(outfile, "memset(x, 0, %d * sizeof(int));\n", r-l+1);
   else
      fprintf(outfile, "memset(x - %d, 0, %d * sizeof(int));\n", -l, r-l+1);
   if( x != 0 )
   {
      Indent(outfile, depth);
      (void)fputc('x', outfile);
      WriteDelta(outfile, x);
      (void)fputs(";\n", outfile);
   }
   return (x >= l && x <= r) ? 1 : 0;
}

/********************************************************* WriteSearchExpr */
static void WriteSearchExpr(FILE *outfile, int depth, int step)
{
   Indent(outfile, depth);
   (void)fputs("for(; *x != 0;", outfile);
   if( step != 0 )
   {
      (void)fputs(" x", outfile);
      WriteDelta(outfile, step);
   }
   (void)fputs(");\n", outfile);
}

/************************************************************ WriteSubCode */
static void WriteSubCode(FILE *outfile, int depth, Node *node)
{
   int s, prune;

   for(prune = (depth > 1) ? 0 : 1; node != NULL; node = node->next)
   {
      if( node->leaf != 0 )
      {
         /* Non-looping code */
         WriteAtom(outfile, depth, node->x.atom);
         prune = 0;
      }
      else
      {
         /* Loops - discard if condition is guaranteed to be false */
         if( prune != 0 )
            continue;

         if( IsZeroExpr(node->x.sub) != 0 )
         {
            /* Zero loop */
            if( IsMassZeroExpr(node) != 0 )
               prune = WriteMassZeroExpr(outfile, depth, &node);
            else
               prune = WriteZeroExpr(outfile, depth);
         }
         else if( IsCopyExpr(node->x.sub) != 0 )
         {
            /* Copy loop */
            WriteCopyExpr(outfile, depth, node->x.sub);
            prune = 1;
         }
         else if( (s = IsSearchExpr(node->x.sub)) != 0 )
         {
            /* Search loop */
            WriteSearchExpr(outfile, depth, s);
            prune = 1;
         }
         else
         {
            /* Generic loop */
            Indent(outfile, depth); (void)fputs("while( *x != 0 )\n", outfile);
            Indent(outfile, depth); (void)fputs("{\n", outfile);
            WriteSubCode(outfile, depth + 1, node->x.sub);
            Indent(outfile, depth); (void)fputs("}\n", outfile);
            prune = 1;
         }
      }
   }
}

/*********************************************************** WriteZeroExpr */
static int WriteZeroExpr(FILE *outfile, int depth)
{
   Indent(outfile, depth);
   (void)fputs("*x = 0;\n", outfile);
   return 1;
}