Compiler

scope 是规定了标识符在程序中可访问的范围. 多个scope之间是互不相交的.

例如, 下面有两个作用域, 一个是for loop之内的.另外一个是除了for循环体之外的函数体.

void fun(int n) {
  int a;              // scope 1

  for(n = 0;n<10;n++){//===
    int a = n*n;      //  |===>  scope 2 
    printf("%d\n",a); //===
  }
                      // scope 1
}

大多数语言采用静态作用域, 即作用域只依赖程序的文本, 而不是运行时的行为. 动态作用域则相反, 作用域依赖于程序运行时的行为.

void foo(int x) {
  int a = 3;
  bar(3);  // 对于动态语言, eg:早期的lisp, 此处将成功打印出3. 
}

void bar(int y){
  printf("%d", a); // 而对于像C这样的static scope语言, 这里显然无法通过编译. 
}

例, C语言中的标识符绑定被下面的东西引入:

• 函数定义 function definitons
• struct definitions
• variable definitions
• struct中字段的定义.
• 函数参数的声明

虽然大多数标识符满足最近嵌套作用域原则. 但仍有例外:

1. C++ 中的成员函数可以在class之外定义. 但在这些函数的定义中仍然能访问class成员.
2. C++ 中的向前forward声明, 使得 前面定义的类可以引用定义在后面的类.

在C中,block就是最常见的作用域scope. 在早期的C中, 一个scope中的变量声明必须全都放在开头,之后才能使用变量. AST结构如下:

	  代码块
       /         \
 声明list       语句list
 /  |  \       /   |   \
d1  d2  d3    s1   s2  s3 

而现在的C语言允许声明和普通语句混合:

      代码块
       /       
  代码块项目list 
  /    |     \     \ 
语句1 声明1  语句2  声明2 .. 

每当进入一个scope / 代码块 ,就会创建一个用来保存变量声明/定义的上下文context. 而每当离开一个scope时, 相应的上下文就会被销毁.

这种context是什么?

所谓函数是一段代码, 位于代码段, 是只读的. 但是每个函数被调用时都包含着对应当前实例的特有数据: 入参, 局部变量, 中间结果 … 这些数据是运行时动态创建的, 不能放在代码段中. 因此需要有某种数据结构来管理每个函数调用对应的特有数据.这种结构就是栈stack.

一门语言中的函数的语法决定了如何实现函数调用. 比较复杂的函数实现就是所谓的高阶函数: 入参和返回值都可以是函数. 并且为了支持能够返回一个函数对象, 语法也必须支持嵌套的函数定义. 这些函数的特性增加了实现的难度:

let myfunc x = 
  let
    bar y = x + y 
  in 
  bar 
;;

# let bar =myfunc 2 ;;
val bar : int -> int = <fun>

为了实现上的简单, 暂时不考虑返回一个函数对象的情况. 仅允许嵌套函数定义.

这里的栈不是标准的栈 – 仅支持push/pop/peek. 因为要访问变量, 因此要实现为数组.并用一个指针来标记栈顶, 即栈指针sp. 这个数组是从高地址向低地址方向生长的.就像山洞中的钟乳石.

存放于栈的每个函数调用对应的特有数据被称为一个frame. 一个栈帧中通常包含这些部分: 入参,函数内声明的局部变量,返回地址,计算的中间结果,保存的寄存器.

某些局部变量不放在寄存器中, 而是存放于stack中, 这些被占用的寄存器可能会与该函数调用的其他函数相冲突. 因此需要将其保存栈中.

int foo(int x , int y)
{
  int temp = x + 1;
  int temp2 = x - y ;
  return temp * temp2 ;
}

foo:                                    # -O0
        pushq   %rbp            # 保存帧指针 
        movq    %rsp, %rbp      # 
        movl    %edi, -4(%rbp)  # x
        movl    %esi, -8(%rbp)  # y
        movl    -4(%rbp), %eax  # x
        addl    $1, %eax        # x+1 
        movl    %eax, -12(%rbp) # x+1 -> temp 
        movl    -4(%rbp), %eax  # x
        subl    -8(%rbp), %eax  # x - y 
        movl    %eax, -16(%rbp) # x - y -> temp2  
        movl    -12(%rbp), %eax # temp
        imull   -16(%rbp), %eax # temp * temp2 -> return value 
        popq    %rbp            # 恢复 帧指针 
        retq

int main() {
    foo(3,7);
    return 0;
}

main:                                   # @main
        pushq   %rbp
        movq    %rsp, %rbp 
        subq    $16, %rsp       # 为foo分配栈帧16 = 4*4字节
        movl    $0, -4(%rbp)    # 
        movl    $3, %edi 
        movl    $7, %esi
        callq   foo
        xorl    %eax, %eax
        addq    $16, %rsp
        popq    %rbp
        retq

调用者负责分配栈帧空间,被调者自己负责调整 <iframe width="800px" height="200px" src="https://godbolt.org/e#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,selection:(endColumn:19,endLineNumber:31,positionColumn:19,positionLineNumber:31,selectionStartColumn:19,selectionStartLineNumber:31,startColumn:19,startLineNumber:31),source:'%0Aint+foo(int+x+,+int+y)%7B%0A++++//char+a+%3D+0%3B%0A++++int+temp+%3D+x+%2B+1%3B%0A++++int+temp2+%3D+x+-y+%3B%0A+++%0A++++return+temp+*+temp2+%3B%0A%0A%7D%0A%0A/*+Type+your+code+here,+or+load+an+example.+*/%0Aint+square()+__attribute__((noinline))%7B%0A++++char+aa+%3D!'a!'+%3B%0A++++long+long+le+%3D+0%3B%0A++++long+long+hi+%3D+12%3B%0A++++long+long+le1+%3D+0%3B%0A++++long+long+hi1+%3D+12%3B%0A+++++++long+long+le2+%3D+0%3B%0A++++long+long+hi2+%3D+12%3B%0A++//foo(3,7)%3B%0A++++return+le+%2B+hi%3B%0A%7D%0Astruct+foo+%7B%0A++++int+i%3B%0A++++long+long+l%3B%0A++++long+long+ll%3B%0A%0A%7D%3B%0Aint+main()+%7B%0A++++struct+foo+myfoo%3B%0A++++myfoo.i+%3D+100%3B%0A++++//square()%3B%0A++++return+0%3B%0A%7D'),l:'5',n:'0',o:'C+source+%231',t:'0')),k:45.67398119122257,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:cclang1500,deviceViewOpen:'1',filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'0',intel:'1',libraryCode:'1',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,libs:!(),options:'-O0',selection:(endColumn:32,endLineNumber:34,positionColumn:32,positionLineNumber:34,selectionStartColumn:32,selectionStartLineNumber:34,startColumn:32,startLineNumber:34),source:1),l:'5',n:'0',o:'+x86-64+clang+15.0.0+(Editor+%231)',t:'0')),k:54.326018808777434,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4"></iframe>

高阶函数 -> 嵌套定义的函数 -> 逃逸变量(内存中) -> 静态链访问

    Semant 
  TRANSLATE    接口 
  Translate    实现
FRAME    TEMP  接口
Frame    Temp  实现

在语义分析阶段之前, 先对AST调用 FindEscape 将是否为逃逸变量标记好.

函数声明:

Semant.transDec -> Translate.newlevel -> Frame.newFrame

Frame 层不知道静态链的存在, 而上层的 Translate 负责静态链的分配.

局部变量声明:

Frame.access 代表了变量存放的位置: 内存/寄存器?

Translate.access 比它多了level信息

Semant + lev -> Translate.allocLocal lev esc -> Frame.allocLocal ==> 返回 access

函数中可以有局部变量. 每次函数调用都会创建一份其局部变量的实例.

Tiger编译器的栈帧

栈帧的接口:

module type FRAME = sig
  type frame
  type access

  val newFrame: {name:Temp.label,formals:bool list} -> frame
  val allocLocal: frame -> bool -> access

  val name: frame -> Temp.label
  val formals: frame -> access list
      ...
end

特定的目标机器:

module MipsFrame : FRAME = struct
  ...
end

实现:

module Frame : FRAME = MipsFrame ;; 

创建一个新的栈帧对象:

Frame.newFrame { name=g; formals= [true;false;false] };;

module MipsFrame: FRAME = struct
  ...
  type access = InFrame of int
              | InReg of Temp.temp 
  ...
end

Frame.allocLocal f true ;;
(* 返回一个 Frame.access of InFrame 类型的值 *)

module FIND_ESCAPE = sig
  val findEscape: Absyn.exp -> unit
end

module FindEscape : FIND_ESCAPE = struct
  type depth = int
  type escEnv = (depth * bool ref) Symbol.table (* symbol --> (嵌套层级深度, 是否为逃逸变量) *)

  let traverseVar (env:escEnv) (d:depth) (s:Absyn.var) : unit = (* ... *) ;;
  and traverseExp (env:exvEnv) (d:depth) (s:Absyn.exp) : unit = (* ... *) ;;
  and traverseDecs (env:exvEnv) (d:depth) (s:Absyn.dec list) : escEnv =  (* ... *) ;;

  let findEscape (prog: Absyn.exp) : unit = (* ... *) ;;
end

当在静态函数嵌套深度为 d 处发现了一个 变量声明 / 形参声明, 例如:

VarDec {name=symbol("a"); escape=r; (* ... *)} 

则将类型为 bool ref 的值设为 false. 将绑定 "a" -> (d,r) 加入到环境(escEnv)中.

这个新环境被用在和这个变量处于同一作用域中的表达式中. 每当发现了符号 a 在深度大于 d 的地方被使用, 就将其绑定中的 r 设为 true.

temp 是局部变量的抽象名字. label 是静态内存地址的抽象名字.

模块 Temp 管理着两个不同名字的集合.

module type Temp = sig

  type temp
  module Table = Map.Make(temp)  (* 其中Table的key是temp类型的 *)
  val newtemp : unit -> temp
  val makestring : temp -> string

  type label = Symbol.symbol
  val newlabel: unit -> label
  val nemedlabel : string -> label

end

module type TRANSLATE = sig 
  type level  
  type access (** 和Frame.access不同,多了level这一信息. *)
  val outermost : level

  val newLevel: {parent: level; name:Temp.label; formals: bool list} -> level
  val allocLocal: level -> bool -> access
end


module Translate : TRANSLATE = struct
  ...
  type access = level * Frame.access  (* <<=!! *)
  ...
end
  ;;

语义分析阶段中的 transDec 通过调用 Translate.newLevel 为每个函数声明创建一个新的嵌套层级. 这个函数又调用 Frame.newFrame 创建了一个新的栈帧. Semant 将 level 保存在此函数的 FunEntry 数据结构中, 使得每遇到一个函数调用时, 可以将被调用函数( FunEntry )的 level 字段传回 Translate 模块. FunEntry 也需要函数的机器代码的入口处作为 label 字段.

module type Env = sig
  (** 新版本的VarEntry和FunEntry : *)
  type enventry =
      VarEntry of { access:Translate.access; ty:ty }
    | FunEntry of {
        level: Translate.level;
        label: Temp.label;
        formals: ty list;
        result: ty
      }

      ...
end

当 Semant 处理一个位于层级为 lev 的局部变量时, 它会调用 Translate.allocLocal lev esc 在本层级中创建一个变量. 参数 esc 表示是否是逃逸变量. 其返回结果为 Translate.access, 这是一个抽象数据类型(但不同于 Frame.access, 因为它必须包含关于静态链的信息). 之后, 当变量在一个表达式中被使用时, Semant 可以将其 access 传回 Translate , 以便于生成访问此变量的机器代码. 与此同时, Semant在值环境中记录着每个 VarEntry 中 access .

抽象数据类型 Translate.access 可以被实现为变量的level和其 Frame.access 的偶对:

type access = level * Frame.access

使得 Translate.allocLocal 能调用 Frame.allocLocal, 并且还可以记住变量是位于哪个层级的. 层级信息稍后在计算静态链时要用到, 变量可能从一个不同的层级中被访问.

Frame 应该独立于被编译的特定语言.许多语言没有嵌套的函数声明.因此Frame不应包含关于静态链的信息, 这是 Translate 的责任. Translate 知道每个栈帧包含着一个静态链. 静态链用寄存器被传给一个函数, 并将其存储到栈帧中.因为静态链表现得如此接近于一个形式参数, 我们将它看成是一个形参. 对于一个有着k个正常参数的函数,令 l 是标识其参数是否为逃逸变量的bool列表.则: l' = true::l 是一个新的list. 额外的true标识着静态链这个额外参数是逃逸的. 于是 newFrame(label,l') 创建了一个包含额外参数和其形参的栈帧.

例: 函数 f(x,y) 被嵌套在函数 g 中.并且g的level被记为 lev_g. 于是 Semant.transDec 可以调用:

Translate.newLevel {parent=lev_g;name=f;formals= [false;false] }

并假设 x,y 都不是逃逸变量.于是 Translate.newLevel 为形参的 bool 列表又加了一个元素:

Frame.newFrame { label, [true;false;false] } 

它会返回一个 frame . 在这个 frame 中,有三个栈帧偏移类型的值, 可以通过 Frame.formals(frame) 来访问. 返回值的首个元素是静态链在栈帧中的偏移量, 其它两个是参数 x, y 的偏移量.当 Semant 调用 Translate.formals(level) 时 , 它会得到这两个偏移量,并将其转换为 access 类型的值.

对层级保持追踪

每次对 Translate.newLevel 进行调用, Semant 必须传递外面这层的 level 值. 当为Tiger程序的main创建level时, Semant应当传递一个特殊的 level 值: Transale.outermost . 它不是Tiger的main函数的level, 而是包含了main的过程的level.所有库函数位于这个 outermost 层级.

函数 transDec 会为每个函数声明创建一个新的level, 但必须将外围函数的level传给newLevel. 这意味着 transDec 中必须包含了当前level的信息.

实现这点是很容易的, 为transDec增加额外的参数, 代表了当前的level. 并且也为transExp增加一个level参数, 这样当遇到一个函数声明时便可将level传递给 transDec.

transVar 也需要添加一个表示当前level的参数, 因为要通过计算level的差来决定访问几次静态链.