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

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 hello(int k, int g) {
    int y = k + g;
    printf("%d\n", y);
    if (k + g < 5) printf("right\n");
}	


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

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


void main() {
    printf("hello world\n");
    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——（7）函数的翻译方法

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

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

函数的翻译方法

前面介绍了许多编译器架构上面的特点，如何组织语法树、如果多遍扫描语法树。今天开始，我们就要设计本编译器中最核心的部分了，如何设计一个编译时宏，再利用LLVM按顺序生成模块。

设计宏

我们的编译器可以说是宏驱动的，因为我们扫描每个语法节点后，都会考察当前是不是一个合法的宏，例如我们来分析一下上一章的示例代码：

1
2
3
void hello(int k, int g) {
    ......
}

我暂时隐藏了函数体部分，让大家先关注一下函数头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
String function
      String void
      String hello
      Node
          Node
              String set
              String int
              String k

          Node
              String set
              String int
              String g

      Node
      	......

我们的语法树的每一层相当于是链表组织的，通过next指针都可以找到下一个元素。
而语法树的开头部分，是一个“function”的宏名称，这个部分就是提示我们用哪个宏函数来翻译用的。

接下来的节点就是： 返回类型，函数名，参数表，函数体

例如参数表，里面的内容很多，但我们扫描时，它们是一个整体，进行识别。

所以我们的宏的形式实际上就是这样：

1
(function 返回类型 函数名 (形参表) (函数体))

括号括起来的部分表示是一个列表，而不是一个元素。

宏函数的编写

我们之前已经定义了宏的函数形式，我们需要传入的有我们自己的上下文类和当前要处理的Node节点，返回的是LLVM的Value类型（各个语句的抽象基类）

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

于是我们将这个函数实现出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static Value* function_macro(CodeGenContext* context, Node* node) {
    // 第一个参数, 返回类型


    // 第二个参数, 函数名
    node = node->getNext();


    // 第三个参数, 参数表
    Node* args_node = node = node->getNext();


    // 第四个参数, 代码块
    node = node->getNext();

    return F;
}

获取一个字符串代表的类型，往往不是一件容易的事，尤其在存在结构体和类的情况下，这时，我们往往需要查一下符号表，检查这个字符串是否为类型，以及是什么样的类型，是基本类型、结构体，还是函数指针或者指向其他结构的指针等等。
获取类型，往往是LLVM中非常重要的一步。

我们这里先写一下查符号表的接口，不做实现，接下来的章节中，我们会介绍经典的栈式符号表的实现。

第二个参数是函数名，我们将其保存在临时变量中待用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static Value* function_type_macro(CodeGenContext* context, Node* node) {
    // 第一个参数, 返回类型
    Type* ret_type = context->FindType(node);

    // 第二个参数, 函数名
    node = node->getNext();
    std::string function_name = node->getStr();

    // 第三个参数, 参数表
    Node* args_node = node = node->getNext();

    // 第四个参数, 代码块
    node = node->getNext();

    return F;
}

接下来的参数表也许是很不好实现的一部分，因为其嵌套比较复杂，不过思路还好，就是不断的去扫描节点，这样我们就可以写出如下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 第三个参数, 参数表
Node* args_node = node = node->getNext();
std::vector<Type*> type_vec;   // 类型列表
std::vector<std::string> arg_name; // 参数名列表
if (args_node->getChild() != NULL) {
    for (Node* pC = args_node->getChild(); 
         pC != NULL; pC = pC->getNext() ) 
    {
        Node* pSec = pC->getChild()->getNext();
        Type* t = context->FindType(pSec);
        type_vec.push_back(t);
        arg_name.push_back(pSec->getNext()->getStr());	
    }
}

其实有了前三个参数，我们就可以构建LLVM中的函数声明了，这样是不用写函数体代码的。
LLVM里很多对象都有这个特点，函数可以只声明函数头，解析完函数体后再将其填回去。结构体也一样，可以先声明符号，回头再向里填入类型信息。这些特性都是方便生成声明的实现，并且在多遍扫描的实现中也会显得很灵活。

我们下面来声明这个函数：

1
2
3
4
5
6
7
// 先合成一个函数
FunctionType *FT = FunctionType::get(ret_type, type_vec, 
    /*not vararg*/false);

Module* M = context->getModule();
Function *F = Function::Create(FT, Function::ExternalLinkage, 
    function_name, M);

这里，我们使用了函数类型，这也是派生自Type的其中一个类，函数类型也可以getPointerTo来获取函数指针类型。
另外，如果构建函数时，添加了Function::ExternalLinkage参数，就相当于C语言的extern关键字，确定这个函数要导出符号。这样，你写的函数就能够被外部链接，或者作为外部函数的声明使用。

函数的特殊问题

接下来我们要创建函数的代码块，但这部分代码实际上和上面的不是在同一个函数中实现的，应该说，他们不是在一趟扫描中。
我们知道，如果要让一个函数内的代码块能够调用在任意位置声明的函数，那么我们就必须对所有函数都先处理刚才讲过的前三个参数，这样函数的声明就有了，在之后的正式扫描中，才有了如下的代码块生成部分：

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
// 第四个参数, 代码块
node = node->getNext();
BasicBlock* bb = context->createBlock(F); // 创建新的Block

// 特殊处理参数表, 这个地方特别坑，你必须给每个函数的参数
// 手动AllocaInst开空间，再用StoreInst存一遍才行，否则一Load就报错
// context->MacroMake(args_node->getChild());
if (args_node->getChild() != NULL) {
    context->MacroMake(args_node);
    int i = 0;
    for (auto arg = F->arg_begin(); i != arg_name.size(); ++arg, ++i) {
        arg->setName(arg_name[i]);
        Value* argumentValue = arg;
        ValueSymbolTable* st = bb->getValueSymbolTable();
        Value* v = st->lookup(arg_name[i]);
        new StoreInst(argumentValue, v, false, bb);
    }
}
context->MacroMake(node);

// 处理块结尾
bb = context->getNowBlock();
if (bb->getTerminator() == NULL)
    ReturnInst::Create(*(context->getContext()), bb);
return F;

这个地方问题非常多，我先保留一个悬念，在接下来代码块和变量存储与加载的讲解中，我会再次提到这个部分的特殊处理。

编译器架构的王者LLVM——（9）栈式符号表的构建

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

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

栈式符号表的构建

栈式符号表对于一款编译器，无疑是核心的组件。
无论你在做什么符号扫描，那么都离不开符号表，如何得知一个符号是否定义，以及它的类型，那么唯有查看符号表中的记录。
栈式符号表并不复杂，但思想精妙，本文，将介绍一款栈式符号表的原理及简单构建。

源代码的例子

首先我们来看一段C代码

1
2
3
4
5
6
7
8
9
10
11
12
int a[3] = { 100, 10, 1};

int work() {
    if (a[0] == 100) { // 这里的a指向的是全局符号a
        int a = 99999; // 重新定义了局部符号    下图的符号表是扫描到这里后的情况
        for (int i = 0; i< 10; ++i) {
            a /= 3; // 由于局部符号优先级较高，引用局部符号
        }
        return a; // 局部符号
    }
    return a[0]; // 局部符号生命周期已过，找到全局符号
}

于是我们发现，符号表在局部声明变量后，将局部符号增加了，这和全局符号并不冲突，而是优先级不同，越靠近栈顶，越先发现

用C++的map和stack构建符号表

如果考虑效率的话，最佳选择是用C语言构建符号表，这样操作起来会更快，但我们毕竟目前考虑开发的简便型而言，用C++的map就可以方便地实现符号表。

首先我们做一个局部符号表，由于其中不会有重复的符号名，所以我们只要简单的将其存放起来即可。
然后符号表还需要记录很多类型信息、指针信息等，我们设计一个结构体表示它们：

1
2
3
4
5
6
7
8
9
10
enum SymbolType
{
    var_t, type_t, struct_t, enum_t, delegate_t, function_t
};

struct id {
    int        level;
    SymbolType type;
    void*      data;
};

我们目前是简单起见，由于还不知道都可能放哪些东西，例如数组符号，肯定要包含数组长度、维度等信息，各种变量都会包含类型信息，所以我们这里放了一个void*的指针，到时候需要的化，就强制转换一下。

这里其实定义一个基类，需要存储的内容去多态派生也是可以的，没做主要是因为可能存放的东西类型很多，暂时先用一个void*，这样可能方便一点。

于是我们的局部符号表就有了：

1
2
3
4
5
6
7
8
9
10
class IDMap
{
public:
    IDMap();
    ~IDMap();
    id* find(string& str) const; // 查找一个符号
    void insert(string& str, int level, SymbolType type, void* data); // 插入一个符号
private:
    map<string,id*> ID_map;
};

我想查找和插入都是C++中map的基础函数，大家应该很轻松就能实现吧。

再弄一个栈来存储一个IDMap：

1
2
3
4
5
6
7
8
9
10
11
12
class IDTable
{
public:
    IDTable();
    id* find(string& str) const;
    void insert(string& str,SymbolType type, void* data);
    void push(); // 压栈和弹栈操作，例如在函数的解析时，需要压栈，一个函数解析完，就弹栈
    void pop();
    int getLevel(); // 获取当前的层级，如果为0，则说明是只有全局符号了
private:
    deque<IDMap> ID_stack;
};

这里用deque而没用stack的原因是，deque支持随机访问，而stack只能访问栈顶。

寻找时，就按照从栈顶到栈底的顺序依次寻找符号：

1
2
3
4
5
6
7
8
id* IDTable::find(string& idname) const {
    for (auto p = ID_stack.rbegin(); p != ID_stack.rend(); ++p) {
        const IDMap& imap = *p;
        id* pid = imap.find(idname);
        if (pid != NULL) return pid;
    }
    return NULL;
}

插入时，就往栈顶，当前最新的符号表里面插入：

1
2
3
4
void IDTable::insert(string& str,SymbolType type, void* data) {
    IDMap& imap = ID_stack.back();
    imap.insert(str,getLevel(), type, data);
}

这样，一款简易的栈式符号表就构建好了。

附1：Github参考源码

idmap.h
idmap.cpp
idtable.h
idtable.cpp

附2：Graphviz的绘图源码

Graphviz绘图真的非常爽，上面的数据结构图就是用它的dot画的，想了解的朋友可以参考我之前写的 结构化图形绘制利器Graphviz：

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
digraph g {
    graph [
        rankdir = "LR"
    ];
    node [
        fontsize = "16"
        shape = "ellipse"
    ];
    edge [
    ];

    "node0" [
        label = "<f0> stack | <f1> | <f2> | ..."
        shape = "record"	
    ];

    "node1" [
        label = "<f0> 全局符号 | a | work |  | ..."
        shape = "record"
    ]

    "node2" [
        label = "<f0> 局部符号 | a |  | ..."
        shape = "record"
    ]

    "node0":f1 -> "node1":f0 [
        id = 0
    ];

    "node0":f2 -> "node2":f0 [
        id = 1
    ];

}

使用Sphinx翻译LLVM的中文文档

Sphinx是一款非常方便的文档生成工具，以前就早有耳闻，最近计划将LLVM的文档翻译一些，在打开LLVM的文档源文件后发现，整个文档部分整理的非常整洁。下载的最新版LLVM-3.8版的源码，已经完全使用Sphinx生成文档，于是我也学习了一些Sphinx的相关用法。

more >>