编译器架构的王者LLVM——（6）多遍翻译的宏翻译系统

2023-12-03 10:42:46

LLVM平台，短短几年间，改变了众多编程语言的走向，也催生了一大批具有特色的编程语言的出现，不愧为编译器架构的王者，也荣获2012年ACM软件系统奖 —— 题记

版权声明：本文为 西风逍遥游 原创文章，转载请注明出处 西风世界 http://blog.csdn.net/xfxyy_sxfancy

上次我们讨论了构建语法树的基本模型，我们能够利用Lex+Bison+Node,几个组件将我们的目标语法翻译成AST语法树了，在第四章，我们也给出了RedApple这款实现型小编译器的语法结构，那么我们的准备工作基于基本完成。

我们在搞定了AST语法树的构建后，需要有一种机制，能够遍历整棵语法树，然后将其翻译为LLVM的一个模块，然后再输出成.bc字节码。

这种机制我称其为多趟宏翻译系统，因为它要多次扫描整棵语法树，每次扫描需要的部分，然后构建整个模块。我希望能实现类似Java的语法特性，无需考虑定义顺序，只要定义了，那么就能够找到该符号。这样我们就需要合理的扫描顺序。

扫描顺序的确定

首先，我们必须先扫描出所有的类型，因为类型的声明很重要，没有类型声明，就无法构建函数。
其次，我们要扫描出所有的函数，为其构建函数的声明。
最后，我们扫描出所有的函数定义，构建每个函数的函数体。

这样我们是三次扫描，无需担心效率问题，因为前两次扫描都是在根节点下一层，扫描的元素非常少，所以处理起来很快。

待扫描的AST语法树

这是我们之前生成好的AST语法树，结构还算清晰吧。我们能用的遍历手段也就是上次我们实现的next指针，然后不断的去判断当前节点的数据，然后对应的代码生成出来。

为了能够区分每条语句的含义，我在每个列表最前，都添加了翻译宏的名称，这个设计是仿照lisp做的，宏相当于是编译器中的函数，处理元数据，然后将其翻译成对应的内容。

例如这段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
void (int k, int g) {
    int y = k + g;
    printf("%dn", y);
    if (k + g < 5) printf("rightn");
}	


void go(int k) {
    int a = 0;
    while (a < k) {
        printf("go-%dn", a);
        a = a + 1;
    }
}

void print(int k) {
    for (int i = 0; i < 10; i = i+1) {
        printf("hello-%dn",i);
    } 
}


void main() {
    printf("hello worldn");
    hello(1,2);
    print(9);
}

其AST语法树如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
 
Node
    Node
        String function
        String void
        String hello
        Node
            Node
                String set
                String int
                String k

            Node
                String set
                String int
                String g

        Node
            Node
                String set
                String int
                String y
                Node
                    String opt2
                    String +
                    ID k
                    ID g


            Node
                String call
                String printf
                String %d

                ID y

            Node
                String if
                Node
                    String opt2
                    String <
                    Node
                        String opt2
                        String +
                        ID k
                        ID g

                    Int 5

                Node
                    String call
                    String printf
                    String right

    Node
        String function
        String void
        String go
        Node
            Node
                String set
                String int
                String k

        Node
            Node
                String set
                String int
                String a
                Int 0

            Node
                String while
                Node
                    String opt2
                    String <
                    ID a
                    ID k

                Node
                    Node
                        String call
                        String printf
                        String go-%d

                        ID a

                    Node
                        String opt2
                        String =
                        ID a
                        Node
                            String opt2
                            String +
                            ID a
                            Int 1

    Node
        String function
        String void
        String print
        Node
            Node
                String set
                String int
                String k

        Node
            Node
                String for
                Node
                    String set
                    String int
                    String i
                    Int 0

                Node
                    String opt2
                    String <
                    ID i
                    Int 10

                Node
                    String opt2
                    String =
                    ID i
                    Node
                        String opt2
                        String +
                        ID i
                        Int 1


                Node
                    Node
                        String call
                        String printf
                        String hello-%d

                        ID i



    Node
        String function
        String void
        String main
        Node
        Node
            Node
                String call
                String printf
                String hello world


            Node
                String call
                String hello
                Int 1
                Int 2

            Node
                String call
                String print
                Int 9

扫描中的上下文

由于翻译过程中，我们还需要LLVMContext变量，符号表，宏定义表等必要信息，我们还需要自己实现一个上下文类，来存储必要的信息，上下文类需要在第一遍扫描前就初始化好。

例如我们在翻译中，遇到了一个变量，那么该变量是临时的还是全局的呢？是什么类型，都需要我们在符号表中存储表达，另外当前翻译的语句是属于哪条宏，该怎么翻译？我们必须有一个类来保存这些信息。

于是我们先不谈实现，将接口写出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
class CodeGenContext;
typedef Value* (*CodeGenFunction)(CodeGenContext*, Node*);
typedef struct _funcReg
{
    const char*     name;
    CodeGenFunction func;
} FuncReg;


class CodeGenContext
{
public:
    CodeGenContext(Node* node);
    ~CodeGenContext();


    void PreInit();
    void PreTypeInit();
    void Init();

    void MakeBegin() { 
        MacroMake(root); 
    }

    // 这个函数是用来一条条翻译Node宏的
    Value* MacroMake(Node* node);
    // 递归翻译该节点下的所有宏
    void MacroMakeAll(Node* node); 
    CodeGenFunction getMacro(string& str);

    // C++注册宏
    // void AddMacros(const FuncReg* macro_funcs); // 为只添加不替换保留
    void AddOrReplaceMacros(const FuncReg* macro_funcs);

    // 代码块栈的相关操作
    BasicBlock* getNowBlock();
    BasicBlock* createBlock();
    BasicBlock* createBlock(Function* f);

    // 获取当前模块中已注册的函数
    Function* getFunction(Node* node);
    Function* getFunction(std::string& name);
    void nowFunction(Function* _nowFunc);

    void setModule(Module* pM) { M = pM; }
    Module* getModule() { return M; }
    void setContext(LLVMContext* pC) { Context = pC; }
    LLVMContext* getContext() { return Context; }

    // 类型的定义和查找
    void DefType(string name, Type* t);
    Type* FindType(string& name);
    Type* FindType(Node*);

    void SaveMacros();
    void RecoverMacros();

    bool isSave() { return _save; }
    void setIsSave(bool save) { _save = save; }

    id* FindST(Node* node) const;

    id* FindST(string& str) const {
        return st->find(str);
    }
    IDTable* st;
private:
    // 语法树根节点
    Node* root;

    // 当前的LLVM Module
    Module* M;
    LLVMContext* Context;
    Function* nowFunc;
    BasicBlock* nowBlock;

    // 这是用来查找是否有该宏定义的
    map<string, CodeGenFunction> macro_map;

    // 这个栈是用来临时保存上面的查询表的
    stack<map<string, CodeGenFunction> > macro_save_stack;

    void setNormalType();

    // 用来记录当前是读取还是存入状态
    bool _save;
};

宏的注册

宏是内部的非常重要的函数，本身是一个C函数指针，宏有唯一的名字，通过map表，去查找该宏对应的函数，然后调用其对当前的语法节点进行解析。

宏函数的定义：

1
 
typedef Value* (*CodeGenFunction)(CodeGenContext*, Node*);

注册我是仿照lua的方式设计的，将函数指针组织成数组，然后初始化进入结构体：

1
2
3
4
5
6
7
8
9
10
11
12
13
 
extern const FuncReg macro_funcs[] = {
    {"function", function_macro},
    {"struct",   struct_macro},
    {"set",      set_macro},
    {"call",     call_macro},
    {"opt2",     opt2_macro},
    {"for",      for_macro},
    {"while",    while_macro},
    {"if",       if_macro},
    {"return",   return_macro},
    {"new",      new_macro},
    {NULL, NULL}
};

这样写是为了方便我们一次就导入一批函数进入我们的系统。函数指针我还是习惯使用C指针，一般避免使用C++的成员指针，那样太复杂，而且不容易和其他模块链接，因为C++是没有标准ABI的，但C语言有。

实现扫描的引导

扫描其实很简单了，如果当前节点是个字符串，而且在宏定义中能够找到，那么我们就调用这条宏来处理，否则如果是列表的化，就对每一条分别递归处理。

宏的查找我直接使用了stl模版库中的map和string，非常的方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
Value* CodeGenContext::MacroMake(Node* node) {
    if (node == NULL) return NULL;

    if (node->isStringNode()) {
        StringNode* str_node = (StringNode*)node;
        CodeGenFunction func = getMacro(str_node->getStr());
        if (func != NULL) {
            return func(this, node->getNext());
        } 
        return NULL;
    } 
    if (node->getChild() != NULL && node->getChild()->isStringNode())
        return MacroMake(node->getChild());
    Value* ans;
    for (Node* p = node->getChild(); p != NULL; p = p->getNext()) 
        ans = MacroMake(p);
    return ans;
}

CodeGenFunction CodeGenContext::getMacro(string& str) {
    auto func = macro_map.find(str);
    if (func != macro_map.end()) return func->second;
    else return NULL;
}

原文:大专栏  编译器架构的王者LLVM——（6）多遍翻译的宏翻译系统


上一篇：LLVM 的编译框架基本流程探索（Clang AST语法树）


下一篇：LLVM + libFuzzer 使用方法