VBGood网站全文搜索 Google

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

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
查看: 7804|回复: 11

[讨论] 用VB+LLVM写一个山寨编译器 第七章 变量的支持

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

第七章、变量的支持 - 讨论怎么让用户自定义局部变量,还有赋值运算符……还演示了怎么用LLVM创建SSA形式,事实上你的程序根本不需要手工创建SSA形式!

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


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

本帖被以下淘专辑推荐:

发表于 2010-11-20 08:02:42 | 显示全部楼层
在沙发的坑里等科学家讲课
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-26 13:19:06 | 显示全部楼层
本帖最后由 acme_pjz 于 2010-11-26 15:44 编辑

为偷懒起见,我先把工程文件发上来……

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


llvm-vb-test-ch7.rar (11.95 KB, 下载次数: 356)
回复 支持 反对

使用道具 举报

发表于 2010-11-26 14:07:54 | 显示全部楼层
哈哈,我就是等这个文件...
回复 支持 反对

使用道具 举报

发表于 2010-11-26 14:08:25 | 显示全部楼层
PS:好像和以前的有重复?
回复 支持 反对

使用道具 举报

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

5# download

不会吧?不是加了一个VarExprAST等功能么(局部变量)……

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


LLVM的内存指针

虽然LLVM要求每个寄存器值必须是SSA形式,但并没有要求内存对象是SSA形式。例如上面的代码,我们可以直接取G,H的值,而G,H并没有被重命名,也没有变成新的版本。(有些编译器确实会尝试对内存对象也设置版本。)

所以我们的主意是:给每个局部变量分配一个在栈中的内存。我们需要一个在LLVM中表示栈中的变量的方法。

在LLVM中,所有内存操作都是显式的(load/store语句),而且中间语句被小心地设计使得可以避免使用“address-of”语句。注意到全局变量“@G/@H”定义的时候写的是i32,但是@G/@H本身仍然是“i32*”类型,指向变量所在的内存地址。栈中的变量也有类似的性质,不过它们是用LLVM alloca语句创建的:

define i32 @example() {
entry:
        %X = alloca i32           ; type of %X is i32*.
        ...
        %tmp = load i32* %X       ; load the stack value %X from the stack.
        %tmp2 = add i32 %tmp, 1   ; increment it
        store i32 %tmp2, i32* %X  ; store it back
        ...


上面的代码演示了怎么在LLVM IR里面声明和使用一个局部变量。有了局部变量,我们前面的例子可以改写为:

@G = weak global i32 0   ; type of @G is i32*
@H = weak global i32 0   ; type of @H is i32*

define i32 @test(i1 %Condition) {
entry:
        %X = alloca i32           ; type of %X is i32*.
        br i1 %Condition, label %cond_true, label %cond_false

cond_true:
        %X.0 = load i32* @G
        store i32 %X.0, i32* %X   ; Update X
        br label %cond_next

cond_false:
        %X.1 = load i32* @H
        store i32 %X.1, i32* %X   ; Update X
        br label %cond_next

cond_next:
        %X.2 = load i32* %X       ; Read X
        ret i32 %X.2
}


看到了吧,我们其实完全不需要PHI节点就可以完成If语句……我们总结起来有以下四点:

1、每个局部变量变成一个栈中的内存申请操作。
2、对局部变量的读取操作变成一个load语句。
3、对局部变量的赋值操作变成一个store语句。
4、取局部变量的地址只需要直接使用局部变量的名称。

这样我们就解决了代码生成的问题。但是这样生成的代码效率会很低。幸运的是,LLVM内置了一些优化步骤,比如“mem2reg”优化可以把一些不是很复杂情况下的局部变量转换成SSA寄存器,并在合适的地方插入PHI节点。“scalarrepl”优化的功能会更强大一些。

当然另一个方法就是自己写PHI节点生成算法不过我们不建议这样做,因为你自己写的程序,不经过大量测试的话,里面难免会有一些Bug,而且速度也不一定很快。而LLVM内置的算法是有很多开源软件的程序员和志愿者写的,而且经过大量的测试,估计速度应该比你的程序运行的快,Bug也更少……

接下来开始在“万花筒”里面实现局部变量……
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-26 16:21:37 | 显示全部楼层
“万花筒”语言里面局部变量的语法

为了在“万花筒”语言里面使用局部变量,我们需要升级“万花筒”的语法。有两点:

1、赋值运算符“=”的问题。
2、定义新的变量的问题。

第一个问题正如问题本身所说,而至于第二个问题,目前我们已经有函数本身输入参数,以及循环参数可以作为局部变量。然后我们再加上一个让用户自行定义局部变量的语句。举个例子:

# Define ':' for sequencing: as a low-precedence operator that ignores operands
# and just returns the RHS.
def binary : 1 (x y) y;

# Recursive fib, we could do this before.
def fib(x)
  if (x < 3) then
    1
  else
    fib(x-1)+fib(x-2);

# Iterative fib.
def fibi(x)
  var a = 1, b = 1, c in
  (for i = 3, i < x in
     c = a + b :
     a = b :
     b = c
) :
  b;

# Call it.
fibi(10);


把已有变量修改成局部变量

我们需要修改符号表中保存的内容,不是保存变量的值,而是保存变量的地址。然后我们要修改函数声明和for循环的相关处理函数,使得它们能保存变量的地址到符号表中。

先新建一个辅助函数:

  1. '/// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
  2. '/// the function.  This is used for mutable variables etc.
  3. Public Function CreateEntryBlockAlloca(ByVal TheFunction As Long, ByVal VarName As String) As Long
  4.   Dim TmpB As Long, BB As Long, i As Long
  5.   TmpB = LLVMCreateBuilder
  6.   BB = LLVMGetEntryBasicBlock(TheFunction)
  7.   i = LLVMGetFirstInstruction(BB)
  8.   If i Then LLVMPositionBuilderBefore TmpB, i Else LLVMPositionBuilderAtEnd TmpB, BB
  9.   CreateEntryBlockAlloca = LLVMBuildAlloca(TmpB, LLVMDoubleType, VarName)
  10.   LLVMDisposeBuilder TmpB
  11. End Function
复制代码
这段看起来很滑稽的代码其作用是在给定函数的入口处增加局部变量声明语句。先创建一个临时的中间语言创建器,把它定位到当前函数的最开始。然后创建一个Alloca语句,并返回这个语句。最后把临时的中间语言创建器销毁掉(创建完马上销毁,这个效率可够低的

然后我们修改VariableExprAST的代码创建函数:

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
    '// Load the value.
    ExprAST_CodeGen = LLVMBuildLoad(hBuilder, V, sName)

  End If
End Function


然后修改ForExprAST的代码创建函数。由于原板教程就写得一塌糊涂,所以似乎我把循环的内部逻辑给改乱了,好像总是多运行一次循环……

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
  PreheaderBB = LLVMGetInsertBlock(hBuilder)
  TheFunction = LLVMGetBasicBlockParent(PreheaderBB)
  LoopBB = LLVMAppendBasicBlock(TheFunction, "loop")
  
  '// 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)
  
  '// 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

  '// Compute the end condition.
  Dim EndCond As Long
  EndCond = objEnd.CodeGen
  If EndCond = 0 Then
    UnShadowVariable s, OldVal
    Exit Function
  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
  
  '// Convert condition to a bool by comparing equal to 0.0.
  EndCond = LLVMBuildFCmp(hBuilder, LLVMRealONE, EndCond, LLVMConstReal(LLVMDoubleType, 0), "loopcond")

  '// Create the "after loop" block and insert it.
  Dim LoopEndBB As Long, AfterBB As Long
  LoopEndBB = LLVMGetInsertBlock(hBuilder)
  AfterBB = LLVMAppendBasicBlock(TheFunction, "afterloop")
  
  '// Insert the conditional branch into the end of LoopEndBB.
  LLVMBuildCondBr hBuilder, EndCond, LoopBB, AfterBB
  
  '// 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


注意到现在我们不再需要手工创建PHI节点了
回复 支持 反对

使用道具 举报

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

为了自动把函数的所有参数也保存到局部变量里面去,我们在PrototypeAST里面定义一个辅助函数:

  1. '/// CreateArgumentAllocas - Create an alloca for each argument and register the
  2. '/// argument in the symbol table so that references to it will succeed.
  3. Public Sub CreateArgumentAllocas(ByVal F As Long)
  4.   Dim i As Long, m As Long, s As String, Alloca As Long
  5.   m = Args.Count
  6.   For i = 0 To m - 1
  7.     s = Args.Item(i + 1)
  8.     '// Create an alloca for this variable.
  9.     Alloca = CreateEntryBlockAlloca(F, s)
  10.     '// Store the initial value into the alloca.
  11.     LLVMBuildStore hBuilder, LLVMGetParam(F, i), Alloca
  12.     '// Add arguments to variable symbol table.
  13.     On Error Resume Next
  14.     s = StringToHex(s)
  15.     NamedValues.Remove s
  16.     NamedValues.Add Alloca, s
  17.     On Error GoTo 0
  18.   Next i
  19. End Sub
复制代码
然后把PrototypeAST里面CodeGen里面的关于NamedValues的操作的语句删掉。修改FunctionAST的代码,使得它能保存函数的参数到局部变量里面:

Public Function CodeGen() As Long
  Set NamedValues = New Collection
  
  Dim TheFunction As Long
  TheFunction = Proto.CodeGen
  If TheFunction = 0 Then Exit Function
  
  '// If this is an operator, install it.
  If Proto.isBinaryOp Then
    BinopPrecedence(Proto.getOperatorName) = Proto.Precedence
  End If

  '// Create a new basic block to start insertion into.
  Dim BB As Long
  BB = LLVMAppendBasicBlock(TheFunction, "entry")
  LLVMPositionBuilderAtEnd hBuilder, BB
  
  '// Add all arguments to the symbol table and create their allocas.
  Proto.CreateArgumentAllocas TheFunction


'...


然后在Main函数里面添加如下代码:

'...

'// Set up the optimizer pipeline.  Start with registering info about how the
'// target lays out data structures.
LLVMAddTargetData LLVMGetExecutionEngineTargetData(hExecutionEngine), hFPManager
'// Promote allocas to registers.
LLVMAddPromoteMemoryToRegisterPass hFPManager

'// Do simple "peephole" optimizations and bit-twiddling optzns.
LLVMAddInstructionCombiningPass hFPManager

'...


这样可以把局部变量给优化掉,要不然我们会得到十分愚蠢的代码:

define double @fib(double %x) {
entry:
        %x1 = alloca double
        store double %x, double* %x1
        %x2 = load double* %x1

        %cmptmp = fcmp ult double %x2, 3.000000e+00
        %booltmp = uitofp i1 %cmptmp to double
        %ifcond = fcmp one double %booltmp, 0.000000e+00
        br i1 %ifcond, label %then, label %else

then:                ; preds = %entry
        br label %ifcont

else:                ; preds = %entry
        %x3 = load double* %x1

        %subtmp = fsub double %x3, 1.000000e+00
        %calltmp = call double @fib(double %subtmp)
        %x4 = load double* %x1

        %subtmp5 = fsub double %x4, 2.000000e+00
        %calltmp6 = call double @fib(double %subtmp5)
        %addtmp = fadd double %calltmp, %calltmp6
        br label %ifcont

ifcont:                ; preds = %else, %then
        %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
        ret double %iftmp
}


其中红色的部分是没用的低效率语句。注意到If/Then/Else语句我们并没有改写成局部变量形式,因为用PHI节点来表示If语句实在是太方便了,完全没必要改成局部变量形式……

赋值运算符

我们在Main函数里面新增下列语句:
Public Sub Main()
'// Install standard binary operators.
'// 1 is lowest precedence.
BinopPrecedence(["="]) = 2

BinopPrecedence(["<"]) = 10
BinopPrecedence(["+"]) = 20
BinopPrecedence(["-"]) = 20

'...


然后我们修改BinaryExprAST的代码生成,使得它支持赋值运算符:
Private Function ExprAST_CodeGen() As Long
  Dim L As Long, R As Long
  '// Special case '=' because we don't want to emit the LHS as an expression.
  If Op = ["="] Then
    '// Assignment requires the LHS to be an identifier.
    Dim LHSE As VariableExprAST
    On Error Resume Next
    Err.Clear
    Set LHSE = LHS
    If Err.Number Then
      pError "destination of '=' must be a variable"
      Exit Function
    End If
    On Error GoTo 0

   
    '// Codegen the RHS.
    R = RHS.CodeGen
    If R = 0 Then Exit Function

    '// Look up the name.
    On Error Resume Next
    Err.Clear
    L = NamedValues.Item(StringToHex(LHSE.sName))
    If Err.Number Then
      pError "Unknown variable name"
      Exit Function
    End If
    On Error GoTo 0

   
    LLVMBuildStore hBuilder, R, L
    ExprAST_CodeGen = R
    Exit Function
  End If


  L = LHS.CodeGen
  If L = 0 Then Exit Function
  R = RHS.CodeGen
  If R = 0 Then Exit Function
'...


首先先判断是否是赋值运算符,因为我们不希望左边的表达式(被赋值的变量)被求值。(蓝色代码)先判断左边是不是一个变量,直接用VB的动态类型转换,看看是否出错。如果出错了说明左边不是个变量。

然后生成右边表达式的代码。(绿色代码)查询当前是否存在这个局部变量,如果不存在报错退出。然后把右边表达式的值保存到变量里面去,并返回右边表达式的值(使得我们可以写“X = (Y = Z)”这样的代码)。函数退出。

注意到这样写会有一个严重Bug:赋值运算符支持了,但是判断两个变量是否相等的运算符就没有了。请大家自行想办法解决……

然后我们进行测试:
# Define ':' for sequencing: as a low-precedence operator that ignores operands
# and just returns the RHS.
def binary : 1 (x y) y;

def test(x)
  printd(x) :
  x = 4 :
  printd(x);

test(123);

应该显示出“123”和“4”。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2010-11-26 16:58:06 | 显示全部楼层
用户定义的局部变量

先添加词法分析支持:

'...
  '// var definition
  tok_var = -13
'...
  Case "var": ret = tok_var
'...


然后添加一个新的类,VarExprAST.cls:

  1. Option Explicit

  2. '/// VarExprAST - Expression class for var/in

  3. Implements ExprAST

  4. Public VarNames As New Collection
  5. Public Body As ExprAST
复制代码
var/in语句允许用户定义一连串局部变量,每个变量允许有可选的初值。这些信息保存在VarNames集合里面,其中每一个元素是变体,每个变体v是一个数组,v(0)是变量名,v(1)是初值对应的ExprAST节点。(高度山寨低效率实现

然后我们添加语法分析支持:

  1. '/// varexpr ::= 'var' identifier ('=' expression)?
  2. '//                    (',' identifier ('=' expression)?)* 'in' expression
  3. Public Function ParseVarExpr() As ExprAST
  4.   Dim obj As New VarExprAST
  5.   Dim sName As String, objInit As ExprAST
  6.   
  7.   getNextToken '// eat the var.

  8.   '// At least one variable name is required.
  9.   If CurTok <> tok_identifier Then
  10.     pError "expected identifier after var"
  11.     Exit Function
  12.   End If

  13.   Do
  14.     sName = IdentifierStr
  15.     getNextToken '// eat identifier.

  16.     '// Read the optional initializer.
  17.     Set objInit = Nothing
  18.     If CurTok = ["="] Then
  19.       getNextToken '// eat the '='.
  20.       
  21.       Set objInit = ParseExpression
  22.       If objInit Is Nothing Then Exit Function
  23.     End If
  24.    
  25.     obj.VarNames.Add Array(sName, objInit)
  26.    
  27.     '// End of var list, exit loop.
  28.     If CurTok <> [","] Then Exit Do
  29.     getNextToken '// eat the ','.
  30.    
  31.     If CurTok <> tok_identifier Then
  32.       pError "expected identifier list after var"
  33.       Exit Function
  34.     End If
  35.   Loop
  36.   
  37.   '// At this point, we have to have 'in'.
  38.   If CurTok <> tok_in Then
  39.     pError "expected 'in' keyword after 'var'"
  40.     Exit Function
  41.   End If
  42.   getNextToken '// eat 'in'.
  43.   
  44.   Set obj.Body = ParseExpression
  45.   If obj.Body Is Nothing Then Exit Function
  46.   
  47.   Set ParseVarExpr = obj
  48. End Function

  49. '/// primary
  50. '///   ::= identifierexpr
  51. '///   ::= numberexpr
  52. '///   ::= parenexpr
  53. '///   ::= ifexpr
  54. '///   ::= forexpr
  55. '///   ::= varexpr
  56. Public Function ParsePrimary() As ExprAST
  57.   Select Case CurTok
  58.   Case tok_identifier: Set ParsePrimary = ParseIdentifierExpr
  59.   Case tok_number:     Set ParsePrimary = ParseNumberExpr
  60.   Case ["("]:          Set ParsePrimary = ParseParenExpr
  61.   Case tok_if:         Set ParsePrimary = ParseIfExpr
  62.   Case tok_for:        Set ParsePrimary = ParseForExpr
  63.   Case tok_var:        Set ParsePrimary = ParseVarExpr
  64.   Case Else: pError "unknown token when expecting an expression"
  65.   End Select
  66. End Function
复制代码
代码比较长,但是思路很简单,不仔细解释了……注意到山寨代码VarNames.Add Array(sName, objInit)了吧……

然后是最重要的,VarExprAST的代码生成函数:

  1. Private Function ExprAST_CodeGen() As Long
  2.   Dim bError As Boolean
  3.   Dim OldBindings() As Long, i As Long, m As Long
  4.   Dim TheFunction As Long
  5.   Dim V As Variant, VarName As String, objInit As ExprAST
  6.   Dim InitVal As Long, Alloca As Long, BodyVal As Long
  7.   
  8.   m = VarNames.Count
  9.   ReDim OldBindings(m)
  10.   
  11.   TheFunction = LLVMGetBasicBlockParent(LLVMGetInsertBlock(hBuilder))

  12.   '// Register all variables and emit their initializer.
  13.   For i = 0 To m - 1
  14.     V = VarNames.Item(i + 1)
  15.     VarName = V(0)
  16.     Set objInit = V(1)

  17.     '// Emit the initializer before adding the variable to scope, this prevents
  18.     '// the initializer from referencing the variable itself, and permits stuff
  19.     '// like this:
  20.     '//  var a = 1 in
  21.     '//    var a = a in ...   # refers to outer 'a'.
  22.     If Not objInit Is Nothing Then
  23.       InitVal = objInit.CodeGen
  24.       If InitVal = 0 Then
  25.         bError = True
  26.         m = i
  27.         Exit For
  28.       End If
  29.     Else '// If not specified, use 0.0.
  30.       InitVal = LLVMConstReal(LLVMDoubleType, 0)
  31.     End If
  32.    
  33.     Alloca = CreateEntryBlockAlloca(TheFunction, VarName)
  34.     LLVMBuildStore hBuilder, InitVal, Alloca

  35.     '// Remember the old variable binding so that we can restore the binding when
  36.     '// we unrecurse.
  37.     OldBindings(i) = ShadowVariable(StringToHex(VarName), Alloca)
  38.   Next i
  39.   
  40.   '// Codegen the body, now that all vars are in scope.
  41.   If Not bError Then
  42.     BodyVal = Body.CodeGen
  43.     If BodyVal = 0 Then bError = True
  44.   End If

  45.   '// Pop all our variables from scope.
  46.   For i = 0 To m - 1
  47.     UnShadowVariable StringToHex(VarNames.Item(i + 1)(0)), OldBindings(i)
  48.   Next i

  49.   '// Return the body computation.
  50.   If Not bError Then ExprAST_CodeGen = BodyVal
  51. End Function
复制代码
为了使符号表保持正常(C++版本的代码可没管这么多,编译错误之后符号表乱得一团糟),我们定义bError表示是否出错。用OldBindings数组保存每个变量名所对应的旧的变量(如果有的话)。用一个变体读出集合的元素,然后开始山寨。计算初值的时候如果出错的话,就直接退出初始化步骤,保存下已经初始化的局部变量数量,以便之后还原。剩下的部分不需要解释了吧

然后我们的代码就全部完成了。大家可以测试一下循环式Fibonacci数列的计算函数,参观一下优化的中间代码,看看是个什么效果……

[第七章到此结束,完整工程在3楼]

评分

参与人数 1人气 +3 收起 理由
shanhan + 3 神马都是浮云

查看全部评分

回复 支持 反对

使用道具 举报

发表于 2010-12-7 09:44:39 | 显示全部楼层
:)看不懂  ...
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2019-7-23 19:19

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