VBGood网站全文搜索 Google

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

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
查看: 8276|回复: 10

[讨论] 用VB+LLVM写一个山寨编译器 第五章 判断和循环语句的实现

[复制链接]
 楼主| 发表于 2010-11-19 23:28:13 | 显示全部楼层 |阅读模式
本帖最后由 acme_pjz 于 2010-11-20 11:56 编辑

第五章、给语言加上判断和循环语句功能 - 如题,这给我们讨论静态单赋值形式(SSA)和控制流优化的机会

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


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

评分

参与人数 2威望 +32 人气 +6 收起 理由
shanhan + 19 + 3 神马都是浮云
download + 13 + 3 补分...

查看全部评分

本帖被以下淘专辑推荐:

发表于 2010-11-20 08:04:52 | 显示全部楼层
哈哈,沙发还是我的,楼主被不明真象的人扣分了,
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-20 11:11:38 | 显示全部楼层
本帖最后由 acme_pjz 于 2010-11-20 12:00 编辑
没内容- -   威望 -5 人气 -1


既然有网友抱怨说“没有内容”,那我就先暂时把C++英文原版地址发上来,有谁等不及而且英语和C++都比较好的可以先去看看(说实话我英语也很烂,翻译得不对的地方请指出)……

实在是不好意思,我先挖坑,内容下星期再补……
回复 支持 反对

使用道具 举报

发表于 2010-11-22 14:28:58 | 显示全部楼层
看到这章了...mark一下
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-23 14:23:44 | 显示全部楼层
本帖最后由 acme_pjz 于 2010-11-23 23:20 编辑

第五章介绍

欢迎来到“用LLVM写一个山寨编译器”第五章。前4章我们实现了一个简单的山寨语言“万花筒”,可以创建中间代码、优化,并进行JIT编译。不幸的是,现在“万花筒”语言还没什么用,因为没有流程控制语句。在这一章中,我们将给“万花筒”语言加if/then/else和for支持。

======================================

我先把第五章完整代码贴上来哈有空了再接着把教程补上……

注意:这一章(和所有接下来的章节)我们需要LLVM库和(VB)声明文件。请到 http://www.vbgood.com/viewthread ... mp;page=2#pid565946 下载这些文件。

llvm-vb-test-ch5.rar (9.87 KB, 下载次数: 767)

评分

参与人数 1威望 +6 人气 +1 收起 理由
夜的影子 + 6 + 1 fei chang hao

查看全部评分

回复 支持 反对

使用道具 举报

发表于 2010-11-23 18:06:38 | 显示全部楼层
下到了,加分...
每一种解释都要加一个类?
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-23 23:22:58 | 显示全部楼层
6# download

如果要面向对象实现的话确实是这样……这个在C++里面不是什么大问题,不过鉴于VB6对象的运行效率太低,所以我考虑在VB6能不能用别的方法,比如结构体加上一个nType标记……

==============================================

好了,言归正传:

判断语句的实现

扩展“万花筒”语言使得支持判断语句的过程是直截了当的。我们要扩展词法分析器,语法分析器,抽象语法树和LLVM中间代码生成器。这个

例子很不错,因为它向我们显示了怎么逐渐“增长”语言的特性,当你有了新想法的时候。

我们先看看我们能做到什么功能:

def fib(x)
  if x < 3 then
    1
  else
    fib(x-1)+fib(x-2);


在“万花筒”语言中,所有的东西都是表达式,没有语句。因此If/Then/Else语句更像C里面的x?y:z语句(或者VB里面的IIf语句)。

现在我们把这个任务分成几个部分来完成:

判断语句的词法分析器

这个很简单,只要添加如下代码就可以了,原理也很简单:

Public Enum enumToken
'...
  '// control
  tok_if = -6
  tok_then = -7
  tok_else = -8

'...
End Enum

'...

Public Function gettok() As Long
'...
  Select Case IdentifierStr
'...
  Case "if": ret = tok_if
  Case "then": ret = tok_then
  Case "else": ret = tok_else

'...


判断语句的抽象语法树节点

添加一个类,叫做IfExprAST.cls:

  1. Option Explicit

  2. '/// IfExprAST - Expression class for if/then/else.

  3. Implements ExprAST

  4. Public objCond As ExprAST
  5. Public objThen As ExprAST
  6. Public objElse As ExprAST
复制代码
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-23 23:24:01 | 显示全部楼层
判断语句的语法分析器

在mdlMain里面添加如下代码:

  1. '/// ifexpr ::= 'if' expression 'then' expression 'else' expression
  2. Public Function ParseIfExpr() As ExprAST
  3.   Dim objCond As ExprAST
  4.   Dim objThen As ExprAST
  5.   Dim objElse As ExprAST
  6.   
  7.   getNextToken '// eat the if.
  8.   
  9.   '// condition.
  10.   Set objCond = ParseExpression
  11.   If objCond Is Nothing Then Exit Function
  12.   
  13.   If CurTok <> tok_then Then
  14.     pError "expected then"
  15.     Exit Function
  16.   End If
  17.   getNextToken '// eat the then
  18.   
  19.   Set objThen = ParseExpression
  20.   If objThen Is Nothing Then Exit Function
  21.   
  22.   If CurTok <> tok_else Then
  23.     pError "expected else"
  24.     Exit Function
  25.   End If
  26.   
  27.   getNextToken
  28.   
  29.   Set objElse = ParseExpression
  30.   If objElse Is Nothing Then Exit Function
  31.   
  32.   Dim obj As New IfExprAST
  33.   Set obj.objCond = objCond
  34.   Set obj.objThen = objThen
  35.   Set obj.objElse = objElse
  36.   Set ParseIfExpr = obj
  37. End Function
复制代码
看了前面几章教程之后,相信大家应该很容易看懂这段代码……

然后修改ParsePrimary函数,添加如下代码:

  1.   Case tok_if:         Set ParsePrimary = ParseIfExpr
复制代码
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-23 23:25:23 | 显示全部楼层
本帖最后由 acme_pjz 于 2010-11-23 23:26 编辑

判断语句的中间代码生成

显然,为了实现判断语句,我们需要一些新的东西,例如跳转语句,还有条件跳转语句。例如考虑如下源代码:
extern foo();
extern bar();
def baz(x) if x then foo() else bar();

将会编译成如下中间代码:
declare double @foo()

declare double @bar()

define double @baz(double %x) {
entry:
    %ifcond = fcmp one double %x, 0.000000e+00
    br i1 %ifcond, label %then, label %else


then:        ; preds = %entry
    %calltmp = call double @foo()
    br label %ifcont


else:        ; preds = %entry
    %calltmp1 = call double @bar()
    br label %ifcont


ifcont:        ; preds = %else, %then
    %iftmp = ????????
    ret double %iftmp
}


其中的蓝色代码是条件跳转的意思,如果条件成立调到第一个分支,否则调到第二个分支。绿色代码当然是无条件跳转啦现在的关键问题是红色语句。这个iftmp是calltmp或者calltmp1,但是具体是哪个值要看是从什么地方跳转过来的。如果从then语句块过来的,就是calltmp;如果从else语句块过来的,就是calltmp1。

这样的操作在静态单赋值形式(SSA)里面有一个专门的名字:Phi(Φ)语句。简单地说,这语句的功能是它能“记住”程序的执行是从哪个基本块跳过来的,并且能根据这个信息选择不同的值作为输出。具体的介绍可以参见维基百科……

    %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]


一般有两种地方会用到Φ语句,一个是对局部变量的操作(x = 1; x = x + 1;等等),还有一个就是条件语句、分支语句等。第一种情况不需要你手工创建Φ语句,因为LLVM有局部变量支持、分析、优化功能;第二种情况嘛,如果你觉得比较简单方便的话可以用……

接下来我们正式开始中间代码生成器。在IfExprAST.cls里面添加如下代码:

  1. Private Function ExprAST_CodeGen() As Long
  2.   Dim CondV As Long, ThenV As Long, ElseV As Long
  3.   CondV = objCond.CodeGen
  4.   If CondV = 0 Then Exit Function
  5.   
  6.   '// Convert condition to a bool by comparing equal to 0.0.
  7.   CondV = LLVMBuildFCmp(hBuilder, LLVMRealONE, CondV, LLVMConstReal(LLVMDoubleType, 0), "ifcond")
复制代码
If语句除了开头的基本块之外,还需要再添加3个基本块:Then的,Else的,还有End If之后的。我们先获得当前正在生成的函数,然后往里面添加基本块。然后就可以创建条件跳转语句了:

  1.   Dim TheFunction As Long
  2.   TheFunction = LLVMGetBasicBlockParent(LLVMGetInsertBlock(hBuilder))
  3.   
  4.   '// Create blocks for the then and else cases.  Insert the 'then' block at the
  5.   '// end of the function.
  6.   Dim ThenBB As Long, ElseBB As Long, MergeBB As Long
  7.   ThenBB = LLVMAppendBasicBlock(TheFunction, "then")
  8.   ElseBB = LLVMAppendBasicBlock(TheFunction, "else")
  9.   MergeBB = LLVMAppendBasicBlock(TheFunction, "ifcont")

  10.   LLVMBuildCondBr hBuilder, CondV, ThenBB, ElseBB
复制代码
然后创建Then部分。创建完成后,当前基本块可能会发生变化(例如嵌套的If语句)。所以要重新获取一次当前的基本块:

  1.   '// Emit then value.
  2.   LLVMPositionBuilderAtEnd hBuilder, ThenBB
  3.   
  4.   ThenV = objThen.CodeGen
  5.   If ThenV = 0 Then Exit Function
  6.   
  7.   LLVMBuildBr hBuilder, MergeBB
  8.   '// Codegen of 'Then' can change the current block, update ThenBB for the PHI.
  9.   ThenBB = LLVMGetInsertBlock(hBuilder)
复制代码
对Else部分也如法炮制。注意啦,在LLVM里面,每个基本块的结束必须有一个跳转语句,或者返回语句等类似的语句,否则在校验的时候会报错。所以虽然Else部分紧跟着End If部分,理论上什么都没有的话也会自动运行到下一个基本块,但是我们根据LLVM的规范,还是要添加一个跳转语句:

  1.   '// Emit else block.
  2.   LLVMPositionBuilderAtEnd hBuilder, ElseBB
  3.   
  4.   ElseV = objElse.CodeGen
  5.   If ElseV = 0 Then Exit Function
  6.   
  7.   LLVMBuildBr hBuilder, MergeBB
  8.   '// Codegen of 'Else' can change the current block, update ElseBB for the PHI.
  9.   ElseBB = LLVMGetInsertBlock(hBuilder)
复制代码
之后就是End If的部分了。这时要用Φ语句来判断是从哪个基本块跳到这里的,并且根据此信息选择合适的输出。

  1.   '// Emit merge block.
  2.   LLVMPositionBuilderAtEnd hBuilder, MergeBB
  3.   Dim PN As Long
  4.   PN = LLVMBuildPhi(hBuilder, LLVMDoubleType, "iftmp")
  5.   
  6.   LLVMAddIncoming PN, ThenV, ThenBB, 1
  7.   LLVMAddIncoming PN, ElseV, ElseBB, 1
  8.   ExprAST_CodeGen = PN
  9. End Function
复制代码
到此为止我们完成了If语句的所有工作。我们可以测试一下效果怎样了……

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

使用道具 举报

 楼主| 发表于 2010-11-23 23:27:55 | 显示全部楼层
循环语句的实现

我们心目中想的循环语句的格式是:

for 变量名 = 起始值 , 继续条件 [ , 步长 ] in
  表达式


如果步长省略的话默认为1。这个循环语句是个山寨货:不管“继续条件”是怎样,循环总是至少运行一次。大家有兴趣的话可以自己修改源代码来修正这个Bug哈……

循环语句的词法分析器

很简单:

Public Enum enumToken
'...
  tok_for = -9
  tok_in = -10
'...
End Enum

'...

Public Function gettok() As Long
'...
  Select Case IdentifierStr
'...
  Case "for": ret = tok_for
  Case "in": ret = tok_in
'...


循环语句的抽象语法树节点

添加一个类,叫做ForExprAST.cls:

  1. Option Explicit

  2. '/// ForExprAST - Expression class for for/in.

  3. Implements ExprAST

  4. Public VarName As String
  5. Public objStart As ExprAST, objEnd As ExprAST, objStep As ExprAST, objBody As ExprAST
复制代码
循环语句的语法分析器

这个我们稍微解释一下,在读取步长的时候,看看下一个符号是不是逗号,如果不是的话说明步长被省略了……

  1. '/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
  2. Public Function ParseForExpr() As ExprAST
  3.   Dim obj As New ForExprAST
  4.   Dim objStart As ExprAST, objEnd As ExprAST, objStep As ExprAST, objBody As ExprAST
  5.   getNextToken '// eat the for.

  6.   If CurTok <> tok_identifier Then
  7.     pError "expected identifier after for"
  8.     Exit Function
  9.   End If
  10.   
  11.   obj.VarName = IdentifierStr
  12.   getNextToken '// eat identifier.
  13.   
  14.   If CurTok <> ["="] Then
  15.     pError "expected '=' after for"
  16.     Exit Function
  17.   End If
  18.   getNextToken '// eat '='.
  19.   
  20.   Set objStart = ParseExpression
  21.   If objStart Is Nothing Then Exit Function
  22.   If CurTok <> [","] Then
  23.     pError "expected ',' after for start value"
  24.     Exit Function
  25.   End If
  26.   getNextToken
  27.   
  28.   Set objEnd = ParseExpression
  29.   If objEnd Is Nothing Then Exit Function
  30.   
  31.   '// The step value is optional.
  32.   If CurTok = [","] Then
  33.     getNextToken
  34.     Set objStep = ParseExpression
  35.     If objStep Is Nothing Then Exit Function
  36.   End If
  37.   
  38.   If CurTok <> tok_in Then
  39.     pError "expected 'in' after for"
  40.     Exit Function
  41.   End If
  42.   getNextToken '// eat 'in'.
  43.   
  44.   Set objBody = ParseExpression
  45.   If objBody Is Nothing Then Exit Function

  46.   Set obj.objStart = objStart
  47.   Set obj.objEnd = objEnd
  48.   Set obj.objStep = objStep
  49.   Set obj.objBody = objBody
  50.   Set ParseForExpr = obj
  51. End Function
复制代码
然后在ParsePrimary函数里面添加如下代码:

  1.   Case tok_for:        Set ParsePrimary = ParseForExpr
复制代码
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2022-11-28 10:38

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