用VB+LLVM写一个山寨编译器第八章结论

acme_pjz · 发表于 2010-11-19 23:31:20

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

第八章、结论 - ￥#%&……￥?￥%￥#%这就免了吧

……

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

[不管怎么说，先挖坑

……过几天再填上（当然可能不是在一楼填了）]

download · 发表于 2010-11-20 08:01:31

不管怎么说,先占个沙发听课

acme_pjz · 发表于 2010-12-4 11:51:58

欢迎来到“用LLVM写一个山寨编译器”教程的最后一章。本章其实没什么内容

不过我还是要把官方英文版教程翻译一下……

教程总结

在前几章教程中，我们把我们的山寨“万花筒”语言从一个没用的玩具，逐渐发展成了一个有一些有趣（但是可能仍然没用）的玩具。:)

看看我们走了多远是有趣的，而且我们写的代码还很少（包括注释1700多行，不包括注释1400多行，比这个 http://www.vbgood.com/viewthread.php?tid=98316 要少40%

）。我们建立了整个词法分析器、语法分析器、抽象语法树构建、代码生成器，以及可以互动的主循环（附带JIT编译支持！）

（稍后我会提到再加不到100行的代码，你就可以真编译你的程序成.obj文件了，可以被VB/C/C++的链接器调用了

---译者注）

我们的语言支持一些有趣的功能：允许用户自定义双目和单目运算符，使用JIT编译来实现程序运行，也支持一些控制流构建，通过SSA形式。

这个教程的部分想法是为了向你展示定义、构建自己的语言，以及在其中寻找乐趣是如何的容易和简单。编写一个编译器并不需要吓人的或者神秘的过程！到现在为止你已经看完了一些基础内容，我强烈建议你自行“黑”掉这份教程的代码（hack on it）。

acme_pjz · 发表于 2010-12-4 12:30:21

举一些例子，你可以尝试加入如下功能：

?全局变量支持 - 尽管全局变量在现代软件工程中的地位是受到疑问的，但是在小型简单山寨程序，像“万花筒”中，还是有用的。在现在我们的程序中是很容易添加全局变量支持的：在查符号表的时候看看是否是全局变量。用LLVMAddGlobal以及相关函数来添加、处理全局变量。

?变量的类型 - “万花筒”语言当前只支持double类型。这使得语言的语法很简单，因为你根本不需要指定变量类型。不同的语言有不同的方法来处理变量类型。最简单的处理方法是让用户必须指定每个变量的类型。这时追加保存每个变量的类型到符号表中。

?数组、结构体、向量，等等 - 当你添加好数据类型之后，你就可以以各种有趣的方式来扩展类型系统了。简单数组是比较容易而且在很多应用中是非常有用的。把它们添加进去几乎就是LLVM指令getelementptr的练习：这个指令是非常令人捉摸不透，而且非常规的，甚至在官方帮助中有一个专门的FAQ！如果你想支持一些递归结构（例如链表），请一定要读官方帮助中的相关内容。

?标准运行库 - 我们现在的语言支持用户访问任意的外部函数。如果你想扩展语言使得其支持更高级的功能，一般你要给这些功能写一个运行库，例如你想实现Hash表的功能，你并不希望每个函数调用都内联到用户的程序里面去，而是把Hash表的相关函数写成一个运行时库。

?内存管理 - “万花筒”语言当前只能访问堆栈。如果能调用malloc/free函数无疑是很酷的。或者你想实现一个垃圾回收器，如果这样的话请仔细阅读官方帮助，里面有LLVM垃圾收集器的详细描述。

?调试支持 - LLVM支持DWARF调试信息的输出，这种格式能被一般的调试器，例如GDB接受。（不过M$不认识这种格式 ---译者注）添加调试信息的支持也是简单直接的。最好方法是用“llvm-gcc -g -O0”编译一些C/C++源代码，看看生成了什么内容。

?异常处理支持 - LLVM支持“zero cost exceptions”（不知道是什么意思

---译者注）生成，而且可以与其他语言生成的代码互动。你也可以生成代码，使得每个函数都返回一个是否出错的信息，然后显式判断（恐怕VB是这么干的

）。你也可以显式调用setjmp/longjmp语句。总之就是有多种方法来实现错误处理。

?面向对象、泛型、数据库、复数、图形化编程支持…… - 你能添加到语言中的疯狂想法是没有尽头的

。

?非常规的用途 - 到目前为止，我们谈论的是用LLVM来做通常很多人都感兴趣的事情：做一个特定语言的编译器。但是有很多其它的人们未考虑到的领域，也能使用编译器的技术。例如LLVM被用来做OpenGL硬件加速支持，转换C++成Flash动作脚本代码，还有许多其他可爱而聪明的东西。没准哪天你是第一个用LLVM实现将正则表达式实时JIT编译成汇编代码的人呢？

祝你玩得愉快 - 试着做一些疯狂的、不一般的事情。做一个编译器----像许多其它人做的一样----比起尝试一些略微疯狂或者古怪的想法来说，是不太有趣的。如果你遇到困难了，或者想谈谈相关方面的内容，请给LLVM邮件列表发邮件，具体可参见LLVM官方网站。（或者到VBGood论坛发帖

---译者注）

#￥%￥#……%?￥%￥#%?#￥?#%￥#%#￥%后面的内容似乎比较无趣，请大家自己看英文原版吧

acme_pjz · 发表于 2010-12-6 17:54:25

本帖最后由 acme_pjz 于 2010-12-6 18:34 编辑

接下来是补充内容：怎么用VB+LLVM编写一个真的能编译出机器码的编译器

……

说明：需要更新的LLVM DLL以及声明文件，在http://www.vbgood.com/viewthread.php?tid=98505&page=3#pid568460下载……

用“万花筒”语言编写DLL供VB调用

由于“万花筒”语言目前连数据类型都没有，所以不能调用API，想MsgBox一下都很难。所以我们干脆用“万花筒”编写DLL算了，这样不用调用任何API也能编出有用的内容

。

由于以前我们的函数全都是cdecl的，所以VB不能直接调用，我们先改造“万花筒”语言，新增一个关键字“stdcall”：

Public Enum enumToken
'...
  '/// new keywords
  tok_stdcall = -14
End Enum

'...

Public Function gettok() As Long
'...
  Case "stdcall": ret = tok_stdcall
'...

然后修改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 isOperator As Boolean
Public Precedence As Long '// Precedence if a binary op.
Public CallType As LLVMCallConv

'...

修改ParsePrototype函数：

Public Function ParsePrototype() As PrototypeAST
  Dim Kind As Long
  Dim BinaryPrecedence As Long
  Dim FnName As String
  Dim CallType As LLVMCallConv

  BinaryPrecedence = 30

  If CurTok = tok_stdcall Then
CallType = LLVMX86StdcallCallConv
getNextToken
  End If

'...

  obj.CallType = CallType
  Set ParsePrototype = obj
End Function

acme_pjz · 发表于 2010-12-6 18:43:49

接下来修改PrototypeAST的代码生成函数：

Public Function CodeGen() As Long

'...

  F = LLVMAddFunction(hModule, sName, FT)
  LLVMSetLinkage F, LLVMExternalLinkage
  LLVMSetFunctionCallConv F, CallType

'...

修改CallExprAST的代码生成函数，要不然它会老是以cdecl方式调用函数，会出错的，报unreachable

：

Private Function ExprAST_CodeGen() As Long

'...

  i = LLVMBuildCall(hBuilder, CalleeF, V(0), m, "calltmp")
  LLVMSetInstructionCallConv i, LLVMGetFunctionCallConv(CalleeF)
  ExprAST_CodeGen = i
End Function

我们的小修改到此完成。这个小修改有严重的Bug，就是允许多次extern不同CallType的函数，大家自行修正哈

……

接下来开始写生成obj文件的代码了

……

[未完待续……]

acme_pjz · 发表于 2010-12-6 22:52:01

为了初始化汇编生成器，在Main里面添加如下代码：

'...
LLVMInitializeAllTargetInfos
LLVMInitializeAllTargets
LLVMInitializeAllAsmPrinters
LLVMInitializeAllAsmParsers
'...

然后在Form1里面新增一个按钮Command3，标题么随便你

……

'test only!!!
Private Sub Command3_Click()
Dim s As String, lp As Long
Dim hPass As Long
Dim hStream As Long, hRawStream As Long
Dim hTargetMachine As Long
'///
'创建一个C++里面的ofstream我在DLL代码里面新增了相关C接口代码，返回ofstream的指针，让VB6也++一下，哈哈……
'输出文件名你可以自己改，或者要求用户输入……
hStream = Util_CreateOStreamFromFile(App.Path + "\test.obj", LLVMOpenMode_binary)
'创建一个LLVM raw_ostream 用来输出汇编代码/目标文件/运行结果等功能。可以通过C++的ostream，C++的string，还有LLVM的内部变长数组来创建raw_ostream。
hRawStream = LLVMCreateRaw_OS_OStream(hStream)
'通过raw_ostream创建一个formatted_raw_ostream。第二个参数表示释放formatted_raw_ostream的时候同时释放raw_ostream，这样我们可以偷懒少写一句代码:)。
hRawStream = LLVMCreateFormattedRawOStream(hRawStream, 1)
'///
's = Space(128)
'CopyMemory ByVal StrPtr(s), ByVal LLVMGetTarget(hModule), 256&
's = StrConv(LeftB(s, InStrB(1, s, ChrB(0)) - 1), vbUnicode)
'设置当前目标机器的类型。可以设置成Linux哟……（本来是想自动获取的，没想到获取到的竟然是空白）
s = "i686-pc-mingw32"
'///
'创建一个FunctionPassManager用来生成代码。
hPass = LLVMCreateFunctionPassManagerForModule(hModule)
'创建目标机器描述。第二个参数可以填目标机特性，比如是否支持MMX,SSE什么的。不过我不知道怎么填，所以留空了……
hTargetMachine = LLVMCreateTargetMachine(s, "")
If hTargetMachine Then
  '添加生成代码步骤到FunctionPassManager里面。没什么好说的，自己看函数的参数名就知道了……注意一下，函数返回值是0表示成功，非0表示失败。
  If LLVMTargetMachineAddPassesToEmitFile(hTargetMachine, hPass, hRawStream, CGFT_ObjectFile, LLVMCodeGenOpt_Aggressive, 0) = 0 Then
Dim F As Long
'初始化FunctionPassManager，获取第一个函数。
LLVMInitializeFunctionPassManager hPass
F = LLVMGetFirstFunction(hModule)
Do Until F = 0
   '判断函数名，看看是不是TopLevelExpr导出的匿名函数，如果是的话就不编译。
   lp = LLVMGetValueName(F)
   If lp Then
      s = Space(8)
      CopyMemory ByVal StrPtr(s), ByVal lp, 16&
      lp = InStrB(1, s, ChrB(0))
      If lp > 0 Then s = LeftB(s, lp - 1)
      s = StrConv(s, vbUnicode)
      lp = s = "" Or IsNumeric(s)
   End If
   If lp = 0 Then
      '再看看有没有函数体，如果没有的话也不编译。
      If LLVMCountBasicBlocks(F) > 0 Then
      LLVMRunFunctionPassManager hPass, F
      End If
   End If
   F = LLVMGetNextFunction(F)
Loop
'完了……
LLVMFinalizeFunctionPassManager hPass
MsgBox "OK!"
  Else
MsgBox "Can't add code generation pass"
  End If
  LLVMDisposeTargetMachine hTargetMachine
Else
  MsgBox "Can't create target machine"
End If
'释放内存。
LLVMDisposePassManager hPass
'///
LLVMDisposeRaw_OStream hRawStream
Util_DisposeOStream hStream
End Sub

看到了吧，添加不到100行代码就能编译obj文件了

……

acme_pjz · 发表于 2010-12-6 23:16:05

然后我们小小地升级一下，干脆把“:”运算符内置算了

：

'Main函数：

'...
BinopPrecedence(["/"]) = 40
BinopPrecedence([":"]) = 1
'...

'BinaryExprAST：

Private Function ExprAST_CodeGen() As Long
'...
Select Case Op
'...
Case [":"]: ExprAST_CodeGen = R
'...

然后修正For循环的一个小Bug：

Option Explicit
'/// ForExprAST - Expression class for for/in.
Implements ExprAST
Public VarName As String
Public objStart As ExprAST, objEnd As ExprAST, objStep As ExprAST, objBody As ExprAST
Private Function ExprAST_CodeGen() As Long
'// Emit the start code first, without 'variable' in scope.
Dim StartVal As Long
StartVal = objStart.CodeGen
If StartVal = 0 Then Exit Function
'// Make the new basic block for the loop header, inserting after current
'// block.
Dim TheFunction As Long
Dim PreheaderBB As Long, LoopBB As Long, LoopBB_1 As Long, AfterBB As Long
PreheaderBB = LLVMGetInsertBlock(hBuilder)
TheFunction = LLVMGetBasicBlockParent(PreheaderBB)
LoopBB = LLVMAppendBasicBlock(TheFunction, "loop")
LoopBB_1 = LLVMAppendBasicBlock(TheFunction, "loop_1")
AfterBB = LLVMAppendBasicBlock(TheFunction, "afterloop")
'// Create an alloca for the variable in the entry block.
Dim Alloca As Long
Alloca = CreateEntryBlockAlloca(TheFunction, VarName)
'// Store the value into the alloca.
LLVMBuildStore hBuilder, StartVal, Alloca
'// Insert an explicit fall through from the current block to the LoopBB.
LLVMBuildBr hBuilder, LoopBB
'// Start insertion in LoopBB.
LLVMPositionBuilderAtEnd hBuilder, LoopBB
'// Within the loop, the variable is defined equal to the PHI node. If it
'// shadows an existing variable, we have to restore it, so save it now.
Dim OldVal As Long, s As String
s = StringToHex(VarName)
OldVal = ShadowVariable(s, Alloca)
'========modified: loop condition moves here.
'// Compute the end condition.
Dim EndCond As Long
EndCond = objEnd.CodeGen
If EndCond = 0 Then
UnShadowVariable s, OldVal
Exit Function
End If
'// Convert condition to a bool by comparing equal to 0.0.
EndCond = LLVMBuildFCmp(hBuilder, LLVMRealONE, EndCond, LLVMConstReal(LLVMDoubleType, 0), "loopcond")
'// Insert the conditional branch into the end of LoopEndBB.
LLVMBuildCondBr hBuilder, EndCond, LoopBB_1, AfterBB
'========modified: loop body moves to LoopBB_1
LLVMPositionBuilderAtEnd hBuilder, LoopBB_1
'========end of modify
'// Emit the body of the loop. This, like any other expr, can change the
'// current BB. Note that we ignore the value computed by the body, but don't
'// allow an error.
If objBody.CodeGen = 0 Then
UnShadowVariable s, OldVal
Exit Function
End If
'// Emit the step value.
Dim StepVal As Long
If Not objStep Is Nothing Then
StepVal = objStep.CodeGen
If StepVal = 0 Then
UnShadowVariable s, OldVal
Exit Function
End If
Else
'// If not specified, use 1.0.
StepVal = LLVMConstReal(LLVMDoubleType, 1)
End If
'// Reload, increment, and restore the alloca. This handles the case where
'// the body of the loop mutates the variable.
Dim CurVar As Long, NextVar As Long
CurVar = LLVMBuildLoad(hBuilder, Alloca, VarName)
NextVar = LLVMBuildFAdd(hBuilder, CurVar, StepVal, "nextvar")
LLVMBuildStore hBuilder, NextVar, Alloca
'========modified: jump to run next loop
LLVMBuildBr hBuilder, LoopBB
'========end of modify
'// Any new code will be inserted in AfterBB.
LLVMPositionBuilderAtEnd hBuilder, AfterBB
'// Restore the unshadowed variable.
UnShadowVariable s, OldVal
'// for expr always returns 0.0.
ExprAST_CodeGen = LLVMConstReal(LLVMDoubleType, 0)
End Function

复制代码

接下来开始测试！

acme_pjz · 发表于 2010-12-6 23:33:21

我们写几个无聊的函数来测试一下：

def stdcall fac(x)
  var n = 1 in
  (for i = 1, i < x + 0.1 in
n = n * i) :
  n;

def stdcall fib(x)
  var a = 1, b = 1, c in
  (for i = 3, i < x + 0.1 in
c = a + b :
a = b :
b = c) :
  b;

def stdcall bar(x y)
  var n = 1 in
  (for i = 1, i < y + 0.1 in
n = n * x) :
  n;

def stdcall baz(x y)
  if y < 0 then
1 / bar(x, 0 - y)
  else
bar(x, y);

def stdcall foo(x y)
  var n = 0 in
  (for i = 1, i < x + 0.1 in
n = n + baz(i, y)) :
  n;

效果：

ready> def stdcall fac(x)
  var n = 1 in
  (for i = 1, i < x + 0.1 in
n = n * i) :
  n;

def stdcall fib(x)
  var a = 1, b = 1, c in
  (for i = 3, i < x + 0.1 in
c = a + b :
a = b :
b = c) :
  b;

def stdcall bar(x y)
  var n = 1 in
  (for i = 1, i < y + 0.1 in
n = n * x) :
  n;

def stdcall baz(x y)
  if y < 0 then
1 / bar(x, 0 - y)
  else
bar(x, y);

def stdcall foo(x y)
  var n = 0 in
  (for i = 1, i < x + 0.1 in
n = n + baz(i, y)) :
  n;
ready> Parsed a function definition.

define x86_stdcallcc double @fac(double %x) {
entry:
  br label %loop

loop:                                           ; preds = %loop_1, %entry
  %n.0 = phi double [ 1.000000e+000, %entry ], [ %multmp, %loop_1 ]
  %i.0 = phi double [ 1.000000e+000, %entry ], [ %nextvar, %loop_1 ]
  %addtmp = fadd double %x, 1.000000e-001
  %cmptmp = fcmp ult double %i.0, %addtmp
  br i1 %cmptmp, label %loop_1, label %afterloop

loop_1:                                        ; preds = %loop
  %multmp = fmul double %n.0, %i.0
  %nextvar = fadd double %i.0, 1.000000e+000
  br label %loop

afterloop:                                     ; preds = %loop
  ret double %n.0
}

ready> ready> Parsed a function definition.

define x86_stdcallcc double @fib(double %x) {
entry:
  br label %loop

loop:                                           ; preds = %loop_1, %entry
  %a.0 = phi double [ 1.000000e+000, %entry ], [ %b.0, %loop_1 ]
  %b.0 = phi double [ 1.000000e+000, %entry ], [ %addtmp6, %loop_1 ]
  %i.0 = phi double [ 3.000000e+000, %entry ], [ %nextvar, %loop_1 ]
  %addtmp = fadd double %x, 1.000000e-001
  %cmptmp = fcmp ult double %i.0, %addtmp
  br i1 %cmptmp, label %loop_1, label %afterloop

loop_1:                                        ; preds = %loop
  %addtmp6 = fadd double %a.0, %b.0
  %nextvar = fadd double %i.0, 1.000000e+000
  br label %loop

afterloop:                                     ; preds = %loop
  ret double %b.0
}

ready> ready> Parsed a function definition.

define x86_stdcallcc double @bar(double %x, double %y) {
entry:
  br label %loop

loop:                                           ; preds = %loop_1, %entry
  %n.0 = phi double [ 1.000000e+000, %entry ], [ %multmp, %loop_1 ]
  %i.0 = phi double [ 1.000000e+000, %entry ], [ %nextvar, %loop_1 ]
  %addtmp = fadd double %y, 1.000000e-001
  %cmptmp = fcmp ult double %i.0, %addtmp
  br i1 %cmptmp, label %loop_1, label %afterloop

loop_1:                                        ; preds = %loop
  %multmp = fmul double %n.0, %x
  %nextvar = fadd double %i.0, 1.000000e+000
  br label %loop

afterloop:                                     ; preds = %loop
  ret double %n.0
}

ready> ready> Parsed a function definition.

define x86_stdcallcc double @baz(double %x, double %y) {
entry:
  %cmptmp = fcmp ult double %y, 0.000000e+000
  br i1 %cmptmp, label %then, label %else

then:                                           ; preds = %entry
  %subtmp = fsub double 0.000000e+000, %y
  %calltmp = call x86_stdcallcc double @bar(double %x, double %subtmp)
  %divtmp = fdiv double 1.000000e+000, %calltmp
  ret double %divtmp

else:                                           ; preds = %entry
  %calltmp8 = call x86_stdcallcc double @bar(double %x, double %y)
  ret double %calltmp8
}

ready> ready> Parsed a function definition.

define x86_stdcallcc double @foo(double %x, double %y) {
entry:
  br label %loop

loop:                                           ; preds = %loop_1, %entry
  %n.0 = phi double [ 0.000000e+000, %entry ], [ %addtmp8, %loop_1 ]
  %i.0 = phi double [ 1.000000e+000, %entry ], [ %nextvar, %loop_1 ]
  %addtmp = fadd double %x, 1.000000e-001
  %cmptmp = fcmp ult double %i.0, %addtmp
  br i1 %cmptmp, label %loop_1, label %afterloop

loop_1:                                        ; preds = %loop
  %calltmp = call x86_stdcallcc double @baz(double %i.0, double %y)
  %addtmp8 = fadd double %n.0, %calltmp
  %nextvar = fadd double %i.0, 1.000000e+000
  br label %loop

afterloop:                                     ; preds = %loop
  ret double %n.0
}

ready>

输入这些函数以后，点击Command3，看看是不是“OK”了

……然后你会看到多出一个“test.obj”文件……

acme_pjz · 发表于 2010-12-6 23:44:29

然后在cmd里面运行如下语句：

link test.obj /dll /out:test.dll /noentry /align:16 /export:fac /export:fib /export:bar /export:baz /export:foo

可以把test.obj复制到VB6所在目录下运行，或者如果装了VC2005的话可以直接运行Visual Studio命令提示……

我这里是这个效果：

Microsoft (R) Incremental Linker Version 8.00.50727.42
Copyright (C) Microsoft Corporation. All rights reserved.

LINK : warning LNK4108: 已指定 /ALIGN 而没有指定 /DRIVER；映像可能不能运行
正在创建库 test.lib 和对象 test.exp

哈哈，编译成功了！

……接下来用VB调用一下

……

Option Explicit

Private Declare Function fac Lib "test.dll" (ByVal x As Double) As Double
Private Declare Function fib Lib "test.dll" (ByVal x As Double) As Double
Private Declare Function bar Lib "test.dll" (ByVal x As Double, ByVal y As Double) As Double
Private Declare Function baz Lib "test.dll" (ByVal x As Double, ByVal y As Double) As Double
Private Declare Function foo Lib "test.dll" (ByVal x As Double, ByVal y As Double) As Double

Private Sub Command1_Click()
Debug.Print fac(10), fac(20)
Debug.Print fib(10), fib(20)
Debug.Print bar(-3, 3), bar(-3, 13), bar(-3, -3)
Debug.Print baz(-3, 3), baz(-3, 13), baz(-3, -3)
Debug.Print foo(13, 3), foo(13, 13), foo(13, -3)
End Sub

输出结果：

3628800    2.43290200817664E+18
55          6765
-27          -1594323    1
-27          -1594323    -.037037037037037
8281       457593884876401          1.19931717031444

更多功能就等大家发掘啦

……

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

VBGood网站全文搜索

[讨论] 用VB+LLVM写一个山寨编译器第八章结论

本帖被以下淘专辑推荐:

VBGood网站全文搜索

[讨论] 用VB+LLVM写一个山寨编译器 第八章 结论

本帖被以下淘专辑推荐:

[讨论] 用VB+LLVM写一个山寨编译器第八章结论