Оптимизация компилятора BF

Question

Я написал простой переводчик brainfuck2c. Я добавил небольшую оптимизацию (для движений указателей), но я думаю об оптимизации дополнений/вычитаний, например, у нас есть код вроде ++++, который переводится в mem[0]+=1;mem[0]+=1;mem[0]+=1;mem[0]+=1;. Моя цель заключается в том, чтобы мой интерпретатор оптимизировал добавления и вычитание для вывода следующего кода для этого: mem[0]+=4;. Код, который я написал (только с оптимизацией стрелок); Я знаю, что это не «C++ style», но я программист на C. Итак, как реализовать оптимизацию добавления/подкадра? Я немного искал в googled, но я нашел только решения python, и я не использовал их, потому что я их не понимаю, и решения, использующие внешние библиотеки (например, LLVM).

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

int main(int argc, char** argv){ 
    int pos = 0; 
    int amount = 0; 
    int brackets = 0; 
    if(argc!=2)exit(0); 
    FILE* f = fopen(argv[1], "r"); 
    if(f!=NULL){ 
     char* outbuffer = malloc(1024*1024*1024); 
     char c = fgetc(f); 
     strcpy(outbuffer, "int getch(void);\nvoid putch(int);\nint main(){\n"); 
     while(!feof(f)){ 
      if(c == '<'){ 
       if(pos==0)pos=65536; 
       else pos--; 
      } 
      if(c == '>'){ 
       if(pos==65536)pos=0; 
       else pos++; 
      } 
      if(c == '['){ 
       brackets++; 
       sprintf(outbuffer, "while(mem[%d]){", pos); 
      } 
      if(c == ']'){ 
       brackets--; 
       sprintf(outbuffer, "}"); 
      } 
      if(c == '+'){ 
       sprintf(outbuffer, "mem[%d]+=1;", pos); 
      } 
      if(c == '-'){ 
       sprintf(outbuffer, "mem[%d]-=1;", pos); 
      } 
      if(c == '.'){ 
       sprintf(outbuffer, "putch(mem[%d]);", pos); 
      }if(c == '.'){ 
       sprintf(outbuffer, "mem[%d] = getch();", pos); 
      } 
      c = fgetc(f); 
     } 
     if(brackets == 1){ 
      printf("Compilation succesfull. "); 
      printf("Generated Code:\n%s", outbuffer); 
      free(outbuffer); 
     } 
     else{ 
      printf("Comilation fault. Unbalanced brackets."); 
      free(outbuffer); 
     } 
    } 
} 

Хорошо, я нашел ответ. Я создал отдельные функции; Это может быть полезно при написании компилятора с C backend; Спасибо Джин за помощью.

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

int minus(FILE* f){ 
    int c; 
    int amount = 0; 
    while ((c = getc(f)) == '-') 
     amount++; 
    ungetc(c, f); 
    return amount; 
} 

int plus(FILE* f){ 
    int c; 
    int amount = 0; 
    while ((c = getc(f)) == '+') 
     amount++; 
    ungetc(c, f); 
    return amount; 
} 

int main(int argc, char** argv){ 
    int pos = 0; 
    int brackets = 0; 
    if(argc!=2)exit(0); 
    int amount = 1; 
    FILE* f = fopen(argv[1], "r"); 
    if(f!=NULL){ 
     char* outbuffer = (char*)malloc(1024*1024); 
     strcpy(outbuffer, "int getch(void);\nvoid putch(int);\nint main(){\n"); 
     while(!feof(f)){ 
      printf("Iterating."); 
      char c = fgetc(f); 
      if(c == '<'){ 
       if(pos==0)pos=65536; 
       else pos--; 
      } 
      if(c == '>'){ 
       if(pos==65536)pos=0; 
       else pos++; 
      } 
      if(c == '['){ 
       brackets++; 
       sprintf(outbuffer, "%swhile(mem[%d]){",outbuffer,pos); 
      } 
      if(c == ']'){ 
       brackets--; 
       sprintf(outbuffer, "%s}", outbuffer); 
      } 
      if(c == '+'){ 
       amount = plus(f)+1; 
       sprintf(outbuffer, "%smem[%d]+=%d;",outbuffer, pos, amount); 
      } 
      if(c == '-'){ 
       amount = minus(f)+1; 
       sprintf(outbuffer, "%smem[%d]-=%d;",outbuffer, pos, amount); 
      } 
      if(c == '.'){ 
       sprintf(outbuffer, "%sputch(mem[%d]);",outbuffer, pos); 
      } 
      if(c == '.'){ 
       sprintf(outbuffer, "%smem[%d]=getch();",outbuffer, pos); 
      } 
     } 
     if(brackets == 0){ 
      printf("Compilation succesfull. "); 
      printf("Generated Code:\n%s", outbuffer); 
      free(outbuffer); 
     } 
     else{ 
      printf("Comilation fault. Unbalanced brackets."); 
      free(outbuffer); 
     } 
    } 
} 

Answer 1

Общий подход, который используют компиляторы для этих простых упрощений, - это генерировать код лениво.

Вместо того, чтобы сразу испускать код для данной функции HLL, он хранится в удобной структуре данных, которая служит в качестве буфера. После добавления каждого нового фрагмента кода оптимизатор проверяет буфер и применяет правила переписывания шаблонов, которые уменьшают стоимость буферизованного кода без изменения его значения.

В вашем случае правило будет выглядеть как X += m; X += n; --> X += (m+n);. 1.e, переписать два приращения одного и того же l-значения как однократное приращение на сумму исходных двух.

Другой тривиальный пример: X += 0 --> <nothing>. 1.e, стираем приращения на ноль.

Код хранится в буфере, если он еще может соответствовать одному из правил. Когда это невозможно, оно, наконец, испускается и удаляется.

Буфер иногда называют «глазок» в поток вывода команд. Поэтому этот метод улучшения кода называется «оптимизацией глазок». Вы можете многому научиться, ища этот термин.

Существует множество схем для реализации буфера. Для выражений символьный стек операнда может работать хорошо. Для операторов обычный подход заключается в том, чтобы хранить очередь FIFO 2- или 3- адресного кода, абстрактное представление выходного кода.