VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
查看: 8544|回复: 7

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

[复制链接]
 楼主| 发表于 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


[我先挖个坑哈,过几天再填上(当然可能不是在一楼填了)]
发表于 2010-11-19 23:30:08 | 显示全部楼层
中间代码是什么鸟样的,发个看看

评分

参与人数 1人气 +1 收起 理由
acme_pjz + 1 中间代码的样子请参考C++教程

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 发表于 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:

  1. Public Function CodeGen() As Long
  2. '
  3. End Function
复制代码
注意现在里面什么都不写。为了让你了解VB的接口类到底是怎么回事,请现在点击“运行”菜单-->全编译执行,看看会怎样?提示“编译错误:类模块需要实现 'CodeGen' 为接口 'ExprAST'。”看到了吧,VB的接口类可以看成山寨的继承,但是只继承方法,不继承方法内部的实现……

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

(译者注:由于LLVM设计的比较奇怪,或者由于我没仔细看,没找到SSA Value的删除函数这意味着LLVM可能有严重的内存泄漏问题……大家先测试一下看看是不是如此……)

然后声明几个全局对象:

  1. Public hModule As Long
  2. Public hBuilder As Long
  3. Public NamedValues As New Collection

  4. '...

  5. Public Sub Main()
  6. '...
  7. Form1.Show
  8. AllocConsole
  9. '///
  10. ChDrive Left(App.Path, 1)
  11. ChDir App.Path + "\..\..\vs2005\release"
  12. '///
  13. hModule = LLVMModuleCreateWithName("Module1")
  14. hBuilder = LLVMCreateBuilder
  15. '...
复制代码
其中hModule是模块的句柄,就像VB里面一些函数放在一个标准模块里面一样……hBuilder是中间代码创建器的句柄,用这个来往函数里面插入代码……NamedValues保存当前的变量列表(在编译原理里面叫做“符号表”),通过变量名称来返回该变量所对应的SSA Value的句柄。

由于VB的集合有一个讨厌的地方:Key不区分大小写所以我写了一个山寨函数来转换一下字符串,你也可以用别的方法,例如Scripting Runtime里面的Dictionary对象,这个可以区分大小写……

  1. 'workaround for stupid VB collection :-3
  2. Public Function StringToHex(ByVal s As String) As String
  3. Dim i As Long
  4. For i = 1 To Len(s)
  5.   StringToHex = StringToHex + Right("000" + Hex(AscW(Mid(s, i, 1)) And &HFFFF&), 4)
  6. Next i
  7. 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文件了……

评分

参与人数 1威望 +11 人气 +3 收起 理由
shanhan + 11 + 3 赞一个

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-21 17:01:32 | 显示全部楼层
本帖最后由 acme_pjz 于 2010-11-21 17:02 编辑

表达式代码生成

还记得刚才的编译错误么?现在我们开始把这些错误补上首先是NumberExprAST.cls:

  1. Private Function ExprAST_CodeGen() As Long
  2. ExprAST_CodeGen = LLVMConstReal(LLVMDoubleType, fValue)
  3. End Function
复制代码
这个代码太简单了,就是创建一个浮点常量,不解释……

再看下一个,VariableExprAST.cls:

  1. Private Function ExprAST_CodeGen() As Long
  2.   '// Look this variable up in the function.
  3.   On Error Resume Next
  4.   Dim V As Long
  5.   Err.Clear
  6.   V = NamedValues.Item(StringToHex(sName))
  7.   If Err.Number Then
  8.     pError "Unknown variable name"
  9.   Else
  10.     ExprAST_CodeGen = V
  11.   End If
  12. End Function
复制代码
这个要稍微解释一下,还记得我们定义了一个山寨字符串转换函数么?用这个函数来转换变量名,然后查表……如果查不到就会出错,出错了就提示“变量未定义”;如果查到了就直接返回变量的句柄……

接下来是运算符的,BinaryExprAST.cls:

  1. Private Function ExprAST_CodeGen() As Long
  2.   Dim L As Long, R As Long
  3.   L = LHS.CodeGen
  4.   If L = 0 Then Exit Function
  5.   R = RHS.CodeGen
  6.   If R = 0 Then Exit Function
  7.   
  8.   Select Case Op
  9.   Case ["+"]: ExprAST_CodeGen = LLVMBuildFAdd(hBuilder, L, R, "addtmp")
  10.   Case ["-"]: ExprAST_CodeGen = LLVMBuildFSub(hBuilder, L, R, "subtmp")
  11.   Case ["*"]: ExprAST_CodeGen = LLVMBuildFMul(hBuilder, L, R, "multmp")
  12.   Case ["/"]: ExprAST_CodeGen = LLVMBuildFDiv(hBuilder, L, R, "divtmp")
  13.   Case ["<"]
  14.     L = LLVMBuildFCmp(hBuilder, LLVMRealULT, L, R, "cmptmp")
  15.     '// Convert bool 0/1 to double 0.0 or 1.0
  16.     ExprAST_CodeGen = LLVMBuildUIToFP(hBuilder, L, LLVMDoubleType, "booltmp")
  17.   Case Else
  18.     pError "invalid binary operator"
  19.   End Select
  20. 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),稍微有点麻烦:

  1. Private Function ExprAST_CodeGen() As Long
  2.   '// Look up the name in the global module table.
  3.   Dim CalleeF As Long
  4.   CalleeF = LLVMGetNamedFunction(hModule, Callee)
  5.   If CalleeF = 0 Then
  6.     pError "Unknown function referenced"
  7.     Exit Function
  8.   End If
  9.   
  10.   '// If argument mismatch error.
  11.   Dim m As Long
  12.   m = Args.Count
  13.   If LLVMCountParams(CalleeF) <> m Then
  14.     pError "Incorrect # arguments passed"
  15.     Exit Function
  16.   End If

  17.   Dim obj As ExprAST, i As Long
  18.   Dim V() As Long
  19.   ReDim V(m)
  20.   For i = 0 To m - 1
  21.     Set obj = Args.Item(i + 1)
  22.     V(i) = obj.CodeGen
  23.     If V(i) = 0 Then Exit Function
  24.   Next i
  25.   
  26.   ExprAST_CodeGen = LLVMBuildCall(hBuilder, CalleeF, V(0), m, "calltmp")
  27. End Function
复制代码
先调用LLVMGetNamedFunction看看要调用的函数定义了没有,如果没定义的话就报错退出。然后看看参数个数是否一样多,如果不一样也报错退出。然后创建一个数组,对每个参数调用代码生成函数,把返回值填到数组里面去,然后创建函数调用语句,就OK了……

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

[未完待续……]
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-21 17:36:06 | 显示全部楼层
函数代码创建

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

  1. '========PrototypeAST.cls

  2. Option Explicit

  3. Private Declare Function lstrlen Lib "kernel32.dll" Alias "lstrlenA" (ByRef lpString As Any) As Long
  4. Private Declare Sub CopyMemory Lib "kernel32.dll" Alias "RtlMoveMemory" (ByRef Destination As Any, ByRef Source As Any, ByVal Length As Long)

  5. '/// PrototypeAST - This class represents the "prototype" for a function,
  6. '/// which captures its name, and its argument names (thus implicitly the number
  7. '/// of arguments the function takes).

  8. Public sName As String
  9. Public Args As New Collection 'std::vector<std::string> Args

  10. Public Function CodeGen() As Long
  11.   '// Make the function type:  double(double,double) etc.
  12.   Dim Doubles() As Long
  13.   Dim i As Long, m As Long
  14.   Dim FT As Long, F As Long
  15.   m = Args.Count
  16.   ReDim Doubles(m)
  17.   For i = 0 To m - 1
  18.     Doubles(i) = LLVMDoubleType
  19.   Next i
  20.   FT = LLVMFunctionType(LLVMDoubleType, Doubles(0), m, 0)
  21.   'a workaround for a stupid bug in LLVM: string can be "" but can't be vbNullString
  22.   If sName = "" Then sName = ""
  23.   F = LLVMAddFunction(hModule, sName, FT)
  24.   LLVMSetLinkage F, LLVMExternalLinkage
复制代码
首先看看有几个参数,创建一个数组和参数个数一样大,里面全部填上Double类型,表示每个参数都是Double类型……然后调用LLVMFunctionType创建函数类型,函数返回值也是Double,最后一个“0”表示参数个数是固定的……

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

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

然后判断函数是否重复定义。因为C/C++里面允许多次声明同一个函数,所以我们的山寨语言也希望能这样,不过VB是没有这个功能的所以如果你想写一个山寨Basic,这些东西可以忽略掉……

  1.   '// If F conflicted, there was already something named 'Name'.  If it has a
  2.   '// body, don't allow redefinition or reextern.
  3.   Dim lp As Long, s As String
  4.   lp = LLVMGetValueName(F)
  5.   If lp <> 0 Then
  6.     i = lstrlen(ByVal lp)
  7.     If i > 0 Then
  8.       s = LeftB(Space(i \ 2 + 1), i)
  9.       CopyMemory ByVal StrPtr(s), ByVal lp, i
  10.       s = StrConv(s, vbUnicode)
  11.     End If
  12.   End If
  13.   If s <> sName Then
  14.     '// Delete the one we just made and get the existing one.
  15.     LLVMDeleteFunction F
  16.     F = LLVMGetNamedFunction(hModule, sName)
复制代码
首先获得我们刚刚创建的函数名称。由于API的返回值不能是String,所以只能写Long,我们需要写一些讨厌的API调用代码,把一个字符串从Long所指向的指针里面拿出来。前面说过LLVM有一个特点:如果重复定义一个东西的话,新定义的那个会自动重命名,加上一个编号。所哟我们判断一下新的名字是不是我们原来指定的那个。如果不是的话就说明重复定义了,这时把刚刚定义的函数删掉,从已经定义的函数里找出我们想要的那个。

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

  1.     '// If F already has a body, reject this.
  2.     If LLVMCountBasicBlocks(F) > 0 Then
  3.       pError "redefinition of function"
  4.       Exit Function
  5.     End If
  6.    
  7.     '// If F took a different number of args, reject.
  8.     If LLVMCountParams(F) <> m Then
  9.       pError "redefinition of function with different # args"
  10.       Exit Function
  11.     End If
  12.   End If
复制代码
获取当前函数的基本块数量(LLVMCountBasicBlocks),如果不是0就说明实现过了。然后判断参数个数……

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

  1.   '// Set names for all arguments.
  2.   Dim AI As Long
  3.   For i = 0 To m - 1
  4.     AI = LLVMGetParam(F, i)
  5.     s = Args.Item(i + 1)
  6.     LLVMSetValueName AI, s
  7.    
  8.     '// Add arguments to variable symbol table.
  9.     On Error Resume Next
  10.     s = StringToHex(s)
  11.     NamedValues.Remove s
  12.     NamedValues.Add AI, s
  13.     On Error GoTo 0
  14.   Next i
  15.   CodeGen = F
  16. End Function
复制代码
参数名称同时被填到LLVM内部的函数参数信息里面(LLVMGetParam+LLVMSetValueName),以及我们的符号表里面(先删掉已有的,再添加新的够山寨的吧?)

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

接下来是函数实现的创建了,FunctionAST.cls:

  1. Public Function CodeGen() As Long
  2.   Set NamedValues = New Collection
  3.   
  4.   Dim TheFunction As Long
  5.   TheFunction = Proto.CodeGen
  6.   If TheFunction = 0 Then Exit Function
复制代码
首先把符号表整个干掉。够山寨的吧?如果有全局变量等东西,这个办法就是错的了……然后创建函数声明的代码。如果创建失败,就直接退出去。

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

  1.   '// Create a new basic block to start insertion into.
  2.   Dim BB As Long
  3.   BB = LLVMAppendBasicBlock(TheFunction, "entry")
  4.   LLVMPositionBuilderAtEnd hBuilder, BB
复制代码
接下来创建代码:

  1.   Dim RetVal As Long
  2.   RetVal = Body.CodeGen
  3.   If RetVal Then
  4.     '// Finish off the function.
  5.     LLVMBuildRet hBuilder, RetVal

  6.     '// Validate the generated code, checking for consistency.
  7.     LLVMVerifyFunction TheFunction, LLVMPrintMessageAction

  8.     CodeGen = TheFunction
  9.     Exit Function
  10.   End If

  11.   '// Error reading body, remove function.
  12.   LLVMDeleteFunction TheFunction
  13. 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,你先自己想一想吧

[未完待续……]
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-21 18:33:39 | 显示全部楼层
现在我们基本完成了,再把剩下的修改过的代码补上:


  1. Public Sub HandleDefinition()
  2.   Dim obj As FunctionAST, i As Long
  3.   Set obj = ParseDefinition
  4.   If Not obj Is Nothing Then
  5.     i = obj.CodeGen
  6.     If i Then
  7.       printf "Parsed a function definition." + vbCrLf
  8.       LLVMDumpValue i
  9.     End If
  10.   Else
  11.     '// Skip token for error recovery.
  12.     getNextToken
  13.   End If
  14. End Sub

  15. Public Sub HandleExtern()
  16.   Dim obj As PrototypeAST, i As Long
  17.   Set obj = ParseExtern
  18.   If Not obj Is Nothing Then
  19.     i = obj.CodeGen
  20.     If i Then
  21.       printf "Parsed an extern" + vbCrLf
  22.       LLVMDumpValue i
  23.     End If
  24.   Else
  25.     '// Skip token for error recovery.
  26.     getNextToken
  27.   End If
  28. End Sub

  29. Public Sub HandleTopLevelExpression()
  30.   '// Evaluate a top-level expression into an anonymous function.
  31.   Dim obj As FunctionAST, i As Long
  32.   Set obj = ParseTopLevelExpr
  33.   If Not obj Is Nothing Then
  34.     i = obj.CodeGen
  35.     If i Then
  36.       printf "Parsed a top-level expr" + vbCrLf
  37.       LLVMDumpValue i
  38.     End If
  39.   Else
  40.     '// Skip token for error recovery.
  41.     getNextToken
  42.   End If
  43. End Sub

  44. Public Sub Main()
  45. '// Install standard binary operators.
  46. '// 1 is lowest precedence.
  47. BinopPrecedence(["<"]) = 10
  48. BinopPrecedence(["+"]) = 20
  49. BinopPrecedence(["-"]) = 20
  50. BinopPrecedence(["*"]) = 40 '// highest.
  51. BinopPrecedence(["/"]) = 40
  52. '///
  53. Form1.Show
  54. AllocConsole
  55. '///
  56. hModule = LLVMModuleCreateWithName("Module1")
  57. hBuilder = LLVMCreateBuilder
  58. '///

  59.   '// Prime the first token.
  60.   printf "ready> "
  61.   getNextToken

  62.   '// Run the main "interpreter loop" now.
  63.   MainLoop

  64. '///
  65. LLVMDisposeBuilder hBuilder
  66. LLVMDisposeModule hModule
  67. FreeConsole
  68. End Sub
复制代码
然后在Form1里面再加一个按钮Command2:

  1. Private Sub Command2_Click()
  2. '// Print out all of the generated code.
  3. LLVMDumpModule hModule
  4. 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

无标题-2.png

下面是工程源代码:

llvm-vb-test-ch3.rar (6.97 KB, 下载次数: 854)
回复 支持 反对

使用道具 举报

发表于 2010-11-22 13:40:48 | 显示全部楼层
看完了,太爽太过瘾了.
回复 支持 反对

使用道具 举报

发表于 2011-11-17 14:24:13 | 显示全部楼层
download 发表于 2010-11-22 13:40
看完了,太爽太过瘾了.


看完了,太爽太过瘾了.+1
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

文字版|手机版|小黑屋|VBGood  

GMT+8, 2019-8-25 23:18

VB爱好者乐园(VBGood)
快速回复 返回顶部 返回列表