NaiveCompiler 前端设计

语义分析 (semantic analysis)

编译器在完成语法分析之后的步骤为语义分析，该步骤会添加语义信息到 Parse Tree 中，并构建符号表(Symbol Table)。

在这个过程中，会同时进行语义检测，例如：类型检查（type checking），以及定义赋值检查（definite assignment analysis）等。

语义分析通常是基于 Parse Tree 或者 AST 进行。 NaiveCompiler 的语义分析实现于 analysis_handler.py 中。 analysis_handler.py 中的类继承 visitor.py 中实现的 visitor 访问模式类 NodeVisitor，实现对 AST 的访问和分析。

Clang 中的语义分析定义于 SemaChecking.cpp 中。同样是通过 Visitor 模式实现。

Visitor 模式及其实现

Visitor 模式是《设计模式》(GoF design patterns)中的 23 个设计模式之一，可以实现算法和实际对象结构的分离，可以在不修改对象结构的情况下给对象添加新的方法。

在 C++ 中可以利用函数重载，double dispatch 来实现 visitor 模式，不需要修改已定义好的 class 源码。而 Python 中则更为简单，通过反射获取类名即可实现。

Visitor 模式还有一个好处，即遍历 AST 时，所有的节点都是继承自 ASTNode，所以可以方便的递归遍历整颗树，并只对感兴趣的节点做处理。

在 NaiveCompiler 的前端中， visitor 都继承自 visitor.py 中的 NodeVisitor。该源码修改自 CPython 自身的 NodeVisitor(定义于/Lib/ast.py)。

class NodeVisitor(object):
    def visit(self, node):
        method = 'visit_' + node.__class__.__name__
        visitor = getattr(self, method, self.generic_visit)
        return visitor(node)

    def generic_visit(self, node):
        for c in node.children():
            self.visit(c)

要实现特定的功能只需要继承该类，以 visit_XXX 的方式定义想要处理的节点，没有定义对应函数的节点会调用 generic_visit 函数，自动访问其子节点。

例如做定义赋值检查（definite assignment analysis）时， AnalysisVisitor 继承 NodeVisitor ，并在访问到函数定义时切换到针对 FuncDef 的类。

class FuncHelper(NodeVisitor):
    def __init__(self):
        self.scope = Scope()
        
    def _has_error(self):
        return self.scope.has_error
    
    def visit_TypeDecl(self, node):
        # print 'TypeDecl', node.__class__.__name__
        self.scope.define_symbol(node._id.name, node._type)

    def visit_DeclStmt(self, node):
        # self.generic_visit(node.decl)
        self.visit_TypeDecl(node.decl)
        
    def visit_ContinueStmt(self, node):
        logging.error("continue outside loop!")
        self.scope.has_error = True

    def visit_BreakStmt(self, node):
        logging.error("break outside loop!")
        self.scope.has_error = True
        
    def visit_Assignment(self, node):
        if type(node.cast_expr) is VariableSymbol:
            self.scope.resolve_symbol(node.cast_expr.name)
        #helper = AssignmentExprHelper(self.scope)
        #helper.visit(node)

可以看到，在访问到声明和赋值语句时，会回调 visit_TypeDecl 和 visit_Assignment。

其中 visit_TypeDecl 会在符号表中注册该变量，而 visit_Assignment 会检测该变量是否存在于符号表中(同时也可以检测变量的类型和赋值的对象是否相同)。

而 visit_BreakStmt 和 visit_ContinueStmt 则会检查是否有循环外的 break 和 continue 语句。因为循环语句会触发 visit_WhileStmt ，进入 LoopHelper 对象进行下一步处理，在没有进去 LoopHelper 访问到的 break 和 continue 即为循环外定义的非法语句。

中间代码生成

通常的代码生成过程为：源代码解析为的 AST 或者三地址代码，生成高级的中间代码(HIR)，然后可能会生成中级的中间代码(MIR)或低级的中间代码(LIR)，中间代码一般是机器无关的代码，最后编译器在中间代码的基础上生成机器相关的代码（例如 x86 汇编代码）。MIR 基本上适合大多是优化，HIR 则用于依赖分析等场景，LIR 用于明确指明寄存器和地址等的优化，参考《高级编译器的设计与实现》(鲸书)第四章《中间表示》。

Compiler Generation Framework

最常见的 HIR 即为抽象语法树(AST)，而 MIR 需要表示源代码的变量、临时变量、寄存器，能够把控制流归约为简单的有条件跳转和无条件跳转、函数调用(call)、和返回(ret)，还需要用明显的操作来支持块结构(BasicBlock)和过程(Function)。

BasicBlock 是 CFG 的基本组成部分，有一系列除了头和尾没有分支的代码序列，一个 BasicBlock 中的代码会按顺序依次执行。

一个 BasicBlock 只能有一个入口(entry point)，意味着 BasicBlock 中的代码不能是某个跳转指令的目标。一个 BasicBlock 只能有一个出口(exit point)，代表只有 BasicBlock 中的最后一条指令才允许跳转到另外的 BasicBlock 中开始执行。

BasicBlock(简称 BB 块)之间的关系为，BB块结束后跳转的目标称作 successors，一个 BB 块可能有多个 successors （条件跳转）。跳转到先有 BB 块的称作 predecessors，一个 BB 块也可能有多个 predecessors。

下面将以 clang 和 gcc 为例，通过下面的 testif.c 来说明常见的中间代码形式和生成过程。

testif.c

int main()
{
  int a = 1;
  if (a > 0) {
      return 1;
  }
  return 0;
}

Clang 中的中间代码生成

Clang 中会先将 AST 划分为 CFG(Control-flow_graph), 用于进一步的分析和平台无关的优化。然后再以类似划分 CFG 的逻辑划分 Basic Blocks，并生成三地址代码。

Clang 中会生成 LLVM 的 IR，再调用 LLVM 生成目标机器码，使用 clang -S -emit-llvm $1 可以 dump 出 Clang 生成的 LLVM IR。以下面的测试代码为例:

生成的 testif.ll 代码如下：

define i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  store i32 1, i32* %2, align 4
  %3 = load i32, i32* %2, align 4
  %4 = icmp sgt i32 %3, 0
  br i1 %4, label %5, label %6

; <label>:5:                                      ; preds = %0
  store i32 1, i32* %1, align 4
  br label %7

; <label>:6:                                      ; preds = %0
  store i32 0, i32* %1, align 4
  br label %7

; <label>:7:                                      ; preds = %6, %5
  %8 = load i32, i32* %1, align 4
  ret i32 %8
}

可以看到 C 代码中的 if 语句编译为了 icmp 和 br，然后 if 和 else 分支分别对应 label 5 和 label6。而 label 7 为 if 后续的语句，可以看到 label 7 的注释中标注有 preds = %6, %5，其代表着 label 7 的前置 label 为 5 和 6，这代表了 BasicBlock 间的关系。除了第一个 BasicBlock，如果某个 BasicBlock 没有前置的 BasicBlock，则该分支为无效的分支。下面我们将一起来看一下 BasicBlock 的具体概念。

GCC 中的中间代码生成

以上面的 testif.c 为例，使用 gcc -fdump-tree-all testif.c 可以 dump 出 gcc 中的中间语言 gimple(.gimple 文件，为高级的中间表达式) 以及 cfg(.cfg 由高级的gimple生成低级的中间表达式)。

上面的 testif.c 生成的 cfg 如下

;;  nodes: 0 1 2 3 4 5
;; 2 succs { 3 4 }
;; 3 succs { 5 }
;; 4 succs { 5 }
;; 5 succs { 1 }
main ()
{
  int a;
  int D.1798;

  <bb 2> [0.00%]:
  a = 1;
  if (a > 0)
    goto <bb 3>; [0.00%]
  else
    goto <bb 4>; [0.00%]

  <bb 3> [0.00%]:
  D.1798 = 1;
  goto <bb 5> (<L2>); [0.00%]

  <bb 4> [0.00%]:
  D.1798 = 0;

<L2> [0.00%]:
  return D.1798;

}

关于 gcc 的 gimple 中间表达式可以参考 https://www.cse.iitb.ac.in/grc/gcc-workshop-09/downloads/gccw09-gimple.pdf，其主要关注下面三个方面：

简化控制流：将代码转换为简单的一系列语句(statment) 和跳转。
简化表达式：例如 -=、+=
简化作用域：将变量包括临时变量移动到作用域开始处

NaiveCompiler 中的中间代码生成

NaiveCompiler 中构建 CFG 后没有进行接下来的分析操作，直接开始做代码生成。

在做完语义分析生成 AST 之后 NaiveCompiler 将循环和条件语句改写为中间代码，分成多个 Baisc Block，并序列化中间代码的语法树，提供给后端 C++ 引擎以便调用 LLVM 来生成 IR 最后编译为目标文件。

示例的 testif.c 对应的语法树如下:

python compiler.py --show-ast tests/testif.c 
----------- show ast ------------
AST: 
  FuncDef: return_type=int, storage=extern
    MethodSymbol: name=main
    DeclarationList: 
    StmtList: 
      DeclStmt: 
        TypeDecl: _type=int, storage=auto
          VariableSymbol: name=a
          Const: _type=int, val=1
      IfStmt: 
        BinaryOp: op=>
          VariableSymbol: name=a
          Const: _type=int, val=0
        StmtList: 
          ReturnStmt: 
            Const: _type=int, val=1
      ReturnStmt: 
        Const: _type=int, val=0

因为后端使用 LLVM 来做代码生成，NavieCompiler 前端中生成的中间代码需要配合 LLVM，考虑 LLVM 代码生成的 API 中，是以 BasicBlock 为基本模块的，并且并无 if 等条件语句，和 for、while 等循环语句，而是类似汇编中的 cmp 语句，和跳转语句 br。（区别为 x86 汇编中 cmp 只有一个，cmp 后会设置条件寄存器，然后有多种 jmp 语句来根据条件寄存器的标志位进行跳转。而 LLVM 的 IR 中 cmp 可以传入比较参数，而跳转均为 br，br 可以带条件结果或者不带条件直接跳转）。

而 LLVM 中的代码(IR)都属于某个函数，而其基本的组成模块为 BasicBlock，每个 BasicBlock 都有一个编号，可以供其他 BasicBlock 跳转时使用。

NaiveCompiler 中 Basic Block 的生成逻辑实现在 codegen.py 中。以上面的 testif.c 为例，使用 python compiler --show-cfg 得到 CFG 如下:

Func  main
4 Entry
Succs: [3]

3
DeclStmt:
  TypeDecl: _type=int, storage=auto
    VariableSymbol: name=a
    Const: _type=int, val=1
CMPJMP: id1=2, id2=1
  BinaryOp: op=>
    VariableSymbol: name=a
    Const: _type=int, val=0
Succs: [2, 1]

2
ReturnStmt:
  Const: _type=int, val=1
Succs: [0]

1
ReturnStmt:
  Const: _type=int, val=0
Succs: [0]

0 Exit
Succs: []

BasicBlock

codegen.py 中，首先定义了 BasicBlock 的基本结构，按照上面的定义，一个基本块需要有一个独立的 ID，以及跳转到该基本块的前置基本块(preds)和该基本块的后续基本块(successors)，还需要 LoopTarget 和 Terminator 辅助循环语句的生成，当然，语句列表(stmts)也不能少。

class BasicBlock(object):
    """ Hold a BasicBlock, To Replace AST Label"""
    BlockKind = ["Reachable", "Unreachable", "Unknown"] # 该 BasicBlock 是否可达
    def __init__(self):
        self.Label = None # Label
        self.Label_id = -1 # Label id
        self.block_id = id_generator.next() # block id
        self.block_name = ''
        self.stmts = [] # StmtList
        self.preds = []
        self.successors = []
        self.Terminator = None
        self.LoopTarget = None

CodeGenerator

代码生成时，以每个 Function 作为一个模块，每个模块由多个基本块组成，其中有一个默认得 Entry 和一个 Exit 块。

def build_basic_blocks(ast):
    basic_blocks = {}
    for c in ast.children():
        if c.__class__ is FuncDef:
            bb = CodeGenModule.build_basic_blocks(c.body, c)
            basic_blocks[c] = bb
    return basic_blocks

定义 CodeGenerator 用于代码生成，其中 cgm 存放当前模块的所有基本块，该类中定义的 current_block 和 current_successor 负责确定当前处理的基本块和当前块的后续基本块。

class CodeGenerator(object):
    """ 至低向上构建 CFG，向构建继承的 block 再构建 上一层的 block"""
    Terminator_STMTS = ["BreakStmt", "ContinueStmt", "ReturnStmt"]
    def __init__(self):
        self.cgm = CodeGenModule()
        self.current_block = None
        self.current_successor = None
        self.break_jumptarget = None
        self.continue_jumptarget = None

CodeGenerator 反向遍历 FuncDef 节点的 StmtList 子节点，构建 CFG。其代码参考了 Clang 的 CFG.cpp。

# CFG.cpp::1124
# https://code.woboq.org/llvm/clang/lib/Analysis/CFG.cpp.html#_ZN12_GLOBAL__N_110CFGBuilder11createBlockEb
def build_basic_blocks(self, node, parent):
    """ 将 StmtList 转换为 CFG，从尾向头遍历子节点"""
    assert node.__class__.__name__ == 'StmtList'
    self.current_successor = self.create_block() # exit Block
    self.current_block = None
    
    block = self.visit(node)
    
    if block is not None:
        self.current_successor = block

    return self.cgm

因为从尾向头遍历，所以先创建第一个默认的 Exit Block，并设置为 current_successor，这样遍历到倒数第一个语句时，将会自动创建一个基本块并将其 Exit Block 添加到其 successors 中。

因为 FuncDef 的第一个 node 为 StmtList，默认的 visit 函数会调用 visit_StmtList

def visit(self, node):
    """ Visit a Stmt.
    """
    node_class =  node.__class__.__name__
    # print node_class
    if issubclass(node.__class__, Statement) or node.__class__ is StmtList:
        method = 'visit_' + node_class
        visitor = getattr(self, method)
    else:
        logger.warning("Unsupported Stmt: {0}".format(node_class))
        sys.exit(1)
    return visitor(node)

# https://code.woboq.org/llvm/clang/lib/Analysis/CFG.cpp.html VisitCompoundStmt
def visit_StmtList(self, node):
    last_block = self.current_block
    for c in node.children()[::-1]:
        tmp = self.visit(c)
        if tmp:
            last_block = tmp
    return last_block

可以看到 visit_StmtList 会反向遍历其子节点，即每个 Stmt，并返回最后一个不为空的基本块，如果没有发生运行错误，该块应为 Entry Block。

Refs

https://en.wikipedia.org/wiki/Basic_block https://www.cse.iitb.ac.in/grc/gcc-workshop-09/downloads/gccw09-gimple.pdf http://amnoid.de/tmp/clangtut/tut.html