c - BF 编译器优化

Question

我写了简单的 brainfuck2c 翻译器。我添加了轻微的优化(针对指针移动)，但我考虑优化加法/减法，例如我们有像 ++++ 这样的代码，它会转换为 mem[0]+= 1;内存[0]+=1;内存[0]+=1;内存[0]+=1;。我的目标是让我的解释器优化加法和减法以为此输出以下代码:mem[0]+=4;。我写的代码(只有箭头优化)；我知道这不是“C++ 风格”，但我是 C 程序员。那么如何实现加法/减法优化呢？我用谷歌搜索了一下，但我只找到了 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 后端的编译器时，它会很有帮助；感谢 Gene 的帮助。

#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); .即，将相同 l 值的两个增量重写为原始两个增量之和的单个增量。

另一个简单的例子:X += 0 --> <nothing> .即，将增量删除为零。

只要代码可能与其中一条规则匹配，它就会一直保存在缓冲区中。当这不可能时，它最终被发出并删除。

缓冲区有时被称为指令输出流的“窥视孔”。因此这种改进代码的方法被称为“窥孔优化”。您可以通过搜索这个词学到很多东西。

有很多实现缓冲区的方案。对于表达式，符号操作数栈可以很好地工作。对于语句，通常的方法是存储 2 或 3 地址代码的 FIFO 队列，这是输出代码的抽象表示。