用VB+LLVM写一个山寨编译器第三章中间代码的生成

acme_pjz · 发表于 2010-11-19 23:25:27

本帖最后由 acme_pjz 于 2010-11-20 11:56 编辑

第三章、LLVM IR 中间代码的生成 - 当AST生成之后我们将会看到，生成中间代码是多么的容易

英文C++版本地址：http://www.llvm.org/releases/2.8/docs/tutorial/LangImpl3.html

[我先挖个坑哈，过几天再填上（当然可能不是在一楼填了）]

download · 发表于 2010-11-19 23:30:08

中间代码是什么鸟样的,发个看看

acme_pjz · 发表于 2010-11-21 15:49:39

本帖最后由 acme_pjz 于 2010-11-21 16:01 编辑

第三章介绍

欢迎来到“用LLVM写一个山寨编译器”第三章。这一章将把上一章创建的抽象语法树转换成中间语言。这将会教给你一点点有关LLVM如何工作的信息，而且我们将会演示LLVM使用起来是多么简单。相比之下，前两章我们创建词法分析器和语法分析器所花的工夫要大得多。

注意：这一章（和所有接下来的章节）我们需要LLVM库和（VB）声明文件。请到 http://www.vbgood.com/viewthread.php?tid=98505&page=2#pid565946 下载这些文件。

给我们的类加上代码创建函数

首先我们先在所有AST节点类里面添加CodeGen函数。首先是ExprAST.cls：

Public Function CodeGen() As Long
'
End Function

复制代码

注意现在里面什么都不写。为了让你了解VB的接口类到底是怎么回事，请现在点击“运行”菜单-->全编译执行，看看会怎样？提示“编译错误：类模块需要实现 'CodeGen' 为接口 'ExprAST'。”

看到了吧，VB的接口类可以看成山寨的继承，但是只继承方法，不继承方法内部的实现……

CodeGen函数的目的是生成一个表示当前节点的LLVM静态单赋值形式（SSA Form）的值(SSA Value)的句柄，在C里面叫做LLVMValueRef，在VB里面就是简单的Long啦

……

（译者注：由于LLVM设计的比较奇怪，或者由于我没仔细看，没找到SSA Value的删除函数

这意味着LLVM可能有严重的内存泄漏问题

……大家先测试一下看看是不是如此……）

然后声明几个全局对象：

Public hModule As Long
Public hBuilder As Long
Public NamedValues As New Collection
'...
Public Sub Main()
'...
Form1.Show
AllocConsole
'///
ChDrive Left(App.Path, 1)
ChDir App.Path + "\..\..\vs2005\release"
'///
hModule = LLVMModuleCreateWithName("Module1")
hBuilder = LLVMCreateBuilder
'...

复制代码

其中hModule是模块的句柄，就像VB里面一些函数放在一个标准模块里面一样

……hBuilder是中间代码创建器的句柄，用这个来往函数里面插入代码……NamedValues保存当前的变量列表（在编译原理里面叫做“符号表”），通过变量名称来返回该变量所对应的SSA Value的句柄。

由于VB的集合有一个讨厌的地方：Key不区分大小写

所以我写了一个山寨函数来转换一下字符串，你也可以用别的方法，例如Scripting Runtime里面的Dictionary对象，这个可以区分大小写……

'workaround for stupid VB collection :-3
Public Function StringToHex(ByVal s As String) As String
Dim i As Long
For i = 1 To Len(s)
StringToHex = StringToHex + Right("000" + Hex(AscW(Mid(s, i, 1)) And &HFFFF&), 4)
Next i
End Function

复制代码

接下来开始正式些中间代码生成的代码了

……

[未完待续……]

================ FAQ ================

1、Q：“AllocConsole”未定义。blah blah blah……
A：

……自己查API浏览器吧……

2、Q：为什么要AllocConsole啊？
A：因为LLVM有几个讨厌的函数是直接向标准输出填东西的，所以如果没有AllocConsole的话你就看不到那些消息了……昨天我调了一个下午的当前进程标准输出重定向，不是没反应就是卡死，后来又想直接API钩子 GetStdHandle和WriteFile，结果超级不稳定，只好放弃了……

3、Q：为什么要ChDrive和ChDir啊？
A：因为我这里dll没有放在VB工程所在文件夹，所以直接调用的话会“文件未找到”……所以先把当前目录切换到dll所在目录就可以直接加载dll文件了

……

acme_pjz · 发表于 2010-11-21 17:01:32

本帖最后由 acme_pjz 于 2010-11-21 17:02 编辑

表达式代码生成

还记得刚才的编译错误么？现在我们开始把这些错误补上

首先是NumberExprAST.cls：

Private Function ExprAST_CodeGen() As Long
ExprAST_CodeGen = LLVMConstReal(LLVMDoubleType, fValue)
End Function

复制代码

这个代码太简单了，就是创建一个浮点常量，不解释

……

再看下一个，VariableExprAST.cls：

Private Function ExprAST_CodeGen() As Long
'// Look this variable up in the function.
On Error Resume Next
Dim V As Long
Err.Clear
V = NamedValues.Item(StringToHex(sName))
If Err.Number Then
pError "Unknown variable name"
Else
ExprAST_CodeGen = V
End If
End Function

复制代码

这个要稍微解释一下，还记得我们定义了一个山寨字符串转换函数么？用这个函数来转换变量名，然后查表……如果查不到就会出错，出错了就提示“变量未定义”；如果查到了就直接返回变量的句柄……

接下来是运算符的，BinaryExprAST.cls：

Private Function ExprAST_CodeGen() As Long
Dim L As Long, R As Long
L = LHS.CodeGen
If L = 0 Then Exit Function
R = RHS.CodeGen
If R = 0 Then Exit Function
Select Case Op
Case ["+"]: ExprAST_CodeGen = LLVMBuildFAdd(hBuilder, L, R, "addtmp")
Case ["-"]: ExprAST_CodeGen = LLVMBuildFSub(hBuilder, L, R, "subtmp")
Case ["*"]: ExprAST_CodeGen = LLVMBuildFMul(hBuilder, L, R, "multmp")
Case ["/"]: ExprAST_CodeGen = LLVMBuildFDiv(hBuilder, L, R, "divtmp")
Case ["<"]
L = LLVMBuildFCmp(hBuilder, LLVMRealULT, L, R, "cmptmp")
'// Convert bool 0/1 to double 0.0 or 1.0
ExprAST_CodeGen = LLVMBuildUIToFP(hBuilder, L, LLVMDoubleType, "booltmp")
Case Else
pError "invalid binary operator"
End Select
End Function

复制代码

首先生成两个操作数的中间代码，看看是否生成失败，如果失败了直接退出……然后看看是哪种运算，加减乘除简单，调用LLVMBuildFxxx函数就行了，F是“浮点”(float，不是拼音fu dian !!!

)，xxx就是加(add)减(sub)乘(mul)除(div)啦……

注意到LLVMBuildFxxx的最后一个参数是字符串，这个参数用来表明运算结果的名字，没什么大的用处，就是最后显示中间代码的时候好看一点而已……另外LLVM在遇到重名的时候会自动把后面的名字加上编号……

需要说一下的是小于运算符，首先作浮点比较，LLVMRealULT的意思是不可比较大小(U)或者小于(LT)，结果是一个1位的整数（无符号：0/1，有符号：0/-1，如果是VB的话用有符号正好，False=0,True=-1

），然后再把无符号整数转换成浮点数（LLVMBuildUIToFP）……

接下来是函数调用的实现（CallExprAST.cls），稍微有点麻烦：

Private Function ExprAST_CodeGen() As Long
'// Look up the name in the global module table.
Dim CalleeF As Long
CalleeF = LLVMGetNamedFunction(hModule, Callee)
If CalleeF = 0 Then
pError "Unknown function referenced"
Exit Function
End If
'// If argument mismatch error.
Dim m As Long
m = Args.Count
If LLVMCountParams(CalleeF) <> m Then
pError "Incorrect # arguments passed"
Exit Function
End If
Dim obj As ExprAST, i As Long
Dim V() As Long
ReDim V(m)
For i = 0 To m - 1
Set obj = Args.Item(i + 1)
V(i) = obj.CodeGen
If V(i) = 0 Then Exit Function
Next i
ExprAST_CodeGen = LLVMBuildCall(hBuilder, CalleeF, V(0), m, "calltmp")
End Function

复制代码

先调用LLVMGetNamedFunction看看要调用的函数定义了没有，如果没定义的话就报错退出。然后看看参数个数是否一样多，如果不一样也报错退出。然后创建一个数组，对每个参数调用代码生成函数，把返回值填到数组里面去，然后创建函数调用语句，就OK了

……

到现在我们就完成表达式代码创建的部分了。如果你喜欢可以添加更多类型的表达式

……接下来我们要创建函数的代码了。

[未完待续……]

acme_pjz · 发表于 2010-11-21 17:36:06

函数代码创建

函数创建比较麻烦一些，因为要处理函数参数个数、函数名称等信息，所以代码也比较丑陋……首先是函数声明代码生成：

'========PrototypeAST.cls
Option Explicit
Private Declare Function lstrlen Lib "kernel32.dll" Alias "lstrlenA" (ByRef lpString As Any) As Long
Private Declare Sub CopyMemory Lib "kernel32.dll" Alias "RtlMoveMemory" (ByRef Destination As Any, ByRef Source As Any, ByVal Length As Long)
'/// PrototypeAST - This class represents the "prototype" for a function,
'/// which captures its name, and its argument names (thus implicitly the number
'/// of arguments the function takes).
Public sName As String
Public Args As New Collection 'std::vector<std::string> Args
Public Function CodeGen() As Long
'// Make the function type: double(double,double) etc.
Dim Doubles() As Long
Dim i As Long, m As Long
Dim FT As Long, F As Long
m = Args.Count
ReDim Doubles(m)
For i = 0 To m - 1
Doubles(i) = LLVMDoubleType
Next i
FT = LLVMFunctionType(LLVMDoubleType, Doubles(0), m, 0)
'a workaround for a stupid bug in LLVM: string can be "" but can't be vbNullString
If sName = "" Then sName = ""
F = LLVMAddFunction(hModule, sName, FT)
LLVMSetLinkage F, LLVMExternalLinkage

复制代码

首先看看有几个参数，创建一个数组和参数个数一样大，里面全部填上Double类型，表示每个参数都是Double类型……然后调用LLVMFunctionType创建函数类型，函数返回值也是Double，最后一个“0”表示参数个数是固定的……

然后调用LLVMAddFunction往我们的模块里面添加一个函数……然后我发现LLVM有一个奇怪的Bug，字符串不能传vbNullString进去，要不然会非法操作……只能传""进去，所以要写一个看似没用的代码（If sName = "" Then sName = ""

）来修正这个Bug……

设置链接类型为LLVMExternalLinkage说明这个函数可能在模块之外实现的（例如sin）或者可以被模块之外的代码引用……

然后判断函数是否重复定义。因为C/C++里面允许多次声明同一个函数，所以我们的山寨语言也希望能这样，不过VB是没有这个功能的

所以如果你想写一个山寨Basic，这些东西可以忽略掉

……

'// If F conflicted, there was already something named 'Name'. If it has a
'// body, don't allow redefinition or reextern.
Dim lp As Long, s As String
lp = LLVMGetValueName(F)
If lp <> 0 Then
i = lstrlen(ByVal lp)
If i > 0 Then
s = LeftB(Space(i \ 2 + 1), i)
CopyMemory ByVal StrPtr(s), ByVal lp, i
s = StrConv(s, vbUnicode)
End If
End If
If s <> sName Then
'// Delete the one we just made and get the existing one.
LLVMDeleteFunction F
F = LLVMGetNamedFunction(hModule, sName)

复制代码

首先获得我们刚刚创建的函数名称。由于API的返回值不能是String，所以只能写Long，我们需要写一些讨厌的API调用代码，把一个字符串从Long所指向的指针里面拿出来。前面说过LLVM有一个特点：如果重复定义一个东西的话，新定义的那个会自动重命名，加上一个编号。所哟我们判断一下新的名字是不是我们原来指定的那个。如果不是的话就说明重复定义了，这时把刚刚定义的函数删掉，从已经定义的函数里找出我们想要的那个。

然后我们判断一下这个函数到底被实现过没有（这时就不能再声明了），还有参数个数是否一样：

'// If F already has a body, reject this.
If LLVMCountBasicBlocks(F) > 0 Then
pError "redefinition of function"
Exit Function
End If
'// If F took a different number of args, reject.
If LLVMCountParams(F) <> m Then
pError "redefinition of function with different # args"
Exit Function
End If
End If

复制代码

获取当前函数的基本块数量（LLVMCountBasicBlocks），如果不是0就说明实现过了。然后判断参数个数……

最后把函数的各个参数名称填上：

'// Set names for all arguments.
Dim AI As Long
For i = 0 To m - 1
AI = LLVMGetParam(F, i)
s = Args.Item(i + 1)
LLVMSetValueName AI, s
'// Add arguments to variable symbol table.
On Error Resume Next
s = StringToHex(s)
NamedValues.Remove s
NamedValues.Add AI, s
On Error GoTo 0
Next i
CodeGen = F
End Function

复制代码

参数名称同时被填到LLVM内部的函数参数信息里面（LLVMGetParam+LLVMSetValueName），以及我们的符号表里面（先删掉已有的，再添加新的

够山寨的吧？）

我们这个代码有一个Bug：函数的参数名可以重名，例如“extern foo(a b a)”。修正这个Bug应该不难，就留给我们的读者完成吧

接下来是函数实现的创建了，FunctionAST.cls：

Public Function CodeGen() As Long
Set NamedValues = New Collection
Dim TheFunction As Long
TheFunction = Proto.CodeGen
If TheFunction = 0 Then Exit Function

复制代码

首先把符号表整个干掉。够山寨的吧？如果有全局变量等东西，这个办法就是错的了

……然后创建函数声明的代码。如果创建失败，就直接退出去。

然后创建一个基本块。基本块就是用来放代码的，而且里面的代码总是顺序执行的。控制流不能跳到基本块的中间，只能跳到开头。而且基本块中间的代码执行到一半也不能跳出去，只能在末尾跳出去。创建好之后，把中间代码构建器的插入位置设置成我们新创建的基本块：

'// Create a new basic block to start insertion into.
Dim BB As Long
BB = LLVMAppendBasicBlock(TheFunction, "entry")
LLVMPositionBuilderAtEnd hBuilder, BB

复制代码

接下来创建代码：

Dim RetVal As Long
RetVal = Body.CodeGen
If RetVal Then
'// Finish off the function.
LLVMBuildRet hBuilder, RetVal
'// Validate the generated code, checking for consistency.
LLVMVerifyFunction TheFunction, LLVMPrintMessageAction
CodeGen = TheFunction
Exit Function
End If
'// Error reading body, remove function.
LLVMDeleteFunction TheFunction
End Function

复制代码

先对函数体生成代码，如果生成失败的话就把当前函数删掉，退出。如果生成成功，就在我们的基本块里面添加一个返回语句，返回表达式的结果。然后调用验证函数（LLVMVerifyFunction）看看我们生成的代码有没有问题。如果你写很复杂的编译器的话可能会经常出问题哟

。
然后返回我们创建的函数，OK

……

这段代码还有一个严重的Bug：就是如果我们先声明了一个函数，然后定义它，但是定义错了，然后我们会发现这个函数不见了

：

extern foo(a b); # ok, defines foo.
def foo(a b) c; # error, 'c' is invalid.
def bar() foo(1, 2); # error, unknown function "foo"

有很多种办法修正这个Bug，你先自己想一想吧

。

[未完待续……]

acme_pjz · 发表于 2010-11-21 18:33:39

现在我们基本完成了，再把剩下的修改过的代码补上：

Public Sub HandleDefinition()
Dim obj As FunctionAST, i As Long
Set obj = ParseDefinition
If Not obj Is Nothing Then
i = obj.CodeGen
If i Then
printf "Parsed a function definition." + vbCrLf
LLVMDumpValue i
End If
Else
'// Skip token for error recovery.
getNextToken
End If
End Sub
Public Sub HandleExtern()
Dim obj As PrototypeAST, i As Long
Set obj = ParseExtern
If Not obj Is Nothing Then
i = obj.CodeGen
If i Then
printf "Parsed an extern" + vbCrLf
LLVMDumpValue i
End If
Else
'// Skip token for error recovery.
getNextToken
End If
End Sub
Public Sub HandleTopLevelExpression()
'// Evaluate a top-level expression into an anonymous function.
Dim obj As FunctionAST, i As Long
Set obj = ParseTopLevelExpr
If Not obj Is Nothing Then
i = obj.CodeGen
If i Then
printf "Parsed a top-level expr" + vbCrLf
LLVMDumpValue i
End If
Else
'// Skip token for error recovery.
getNextToken
End If
End Sub
Public Sub Main()
'// Install standard binary operators.
'// 1 is lowest precedence.
BinopPrecedence(["<"]) = 10
BinopPrecedence(["+"]) = 20
BinopPrecedence(["-"]) = 20
BinopPrecedence(["*"]) = 40 '// highest.
BinopPrecedence(["/"]) = 40
'///
Form1.Show
AllocConsole
'///
hModule = LLVMModuleCreateWithName("Module1")
hBuilder = LLVMCreateBuilder
'///
'// Prime the first token.
printf "ready> "
getNextToken
'// Run the main "interpreter loop" now.
MainLoop
'///
LLVMDisposeBuilder hBuilder
LLVMDisposeModule hModule
FreeConsole
End Sub

复制代码

然后在Form1里面再加一个按钮Command2：

Private Sub Command2_Click()
'// Print out all of the generated code.
LLVMDumpModule hModule
End Sub

复制代码

然后你可以开始测试了

ready> 4+5;
Read top-level expression:
define double @""() {
entry:
ret double 9.000000e+00
}

可以看到4+5被自动优化成9了

……再来个复杂点的：

ready> def foo(a b) a*a + 2*a*b + b*b;
Read function definition:
define double @foo(double %a, double %b) {
entry:
      %multmp = fmul double %a, %a
      %multmp1 = fmul double 2.000000e+00, %a
      %multmp2 = fmul double %multmp1, %b
      %addtmp = fadd double %multmp, %multmp2
      %multmp3 = fmul double %b, %b
      %addtmp4 = fadd double %addtmp, %multmp3
      ret double %addtmp4
}

测试了一下算术运算。Notice the striking similarity to the LLVM builder calls that we use to create the instructions. （？？？没搞懂 ---译者注）

再来一个：

ready> def bar(a) foo(a, 4.0) + bar(31337);
Read function definition:
define double @bar(double %a) {
entry:
      %calltmp = call double @foo(double %a, double 4.000000e+00)
      %calltmp1 = call double @bar(double 3.133700e+04)
      %addtmp = fadd double %calltmp, %calltmp1
      ret double %addtmp
}

演示了一下函数调用。说明：如果你真的运行这个函数的话，会要运行很长时间

……

再看看外部函数功能：

ready> extern cos(x);
Read extern:
declare double @cos(double)

ready> cos(1.234);
Read top-level expression:
define double @""() {
entry:
%calltmp = call double @cos(double 1.234000e+00)
ret double %calltmp
}

下一章我们将加入JIT编译器和代码优化器，让这些代码编译成汇编代码，并运行

……

下面是截图：

无标题-1.png

下面是工程源代码：

llvm-vb-test-ch3.rar (6.97 KB, 下载次数: 1299)

download · 发表于 2010-11-22 13:40:48

看完了,太爽太过瘾了.

菜鸟学飞 · 发表于 2011-11-17 14:24:13

download 发表于 2010-11-22 13:40
看完了,太爽太过瘾了.

看完了,太爽太过瘾了.+1

		自动登录	找回密码
密码			立即注册

VBGood网站全文搜索

[讨论] 用VB+LLVM写一个山寨编译器第三章中间代码的生成

评分

评分

VBGood网站全文搜索

[讨论] 用VB+LLVM写一个山寨编译器 第三章 中间代码的生成

评分

评分

[讨论] 用VB+LLVM写一个山寨编译器第三章中间代码的生成