你好 Ciallo～(∠・ω< )⌒☆
欢迎使用本模板！

Intro

@Yousa-Mirage ·

什么是编译器(What is a Compiler)

编译器通常较大,大概是10000至1000000行代码

如何学习 (How to Learn)

理论部分

实验部分

参考书是虎书,使用Tiger语言,考试的时候要求能够读懂

模块与接口 (Modules and Interfaces)

使用多个模块和接口

各个阶段(章节梗概)

Lexical Analysis 词法分析

Overview

编译过程

lexical analysis

注意我们接下来使用形式化方法来研究

词元(Lexical Token)

概念

token

Token Example

  float match0(char *s) /* find a zero */
  { if (!strncmp(s, "0.0", 3))
    return 0.;
  }
FLOAT       ID(match0)  LPAREN  CHAR    STAR ID(s)
RPAREN      LBRACE      IF      LPAREN  BANG
ID(strncmp) LPAREN      ID(s)   COMMA   STRING(0.0)
COMMA       NUM(3)      RPAREN  RPAREN  RETURN
REAL(0.0)   SEMI        RBRACE  EOF

non-tokens

词法规则

正则表达式(Regular Expression)

相关概念

Regular Expression由以下规则定义

  1. Atomic：空串 ε 对应语言 L(ε) = ∅, 单个字符 a 对应语言 L(a) = {a}（最小单元)

  2. Composite： (|相当于∪)

    • Alternation:

    • Concatenation:

    • Repetitions:

有自动机可以接受的语言是正则的

词法规范必须是完善的

注意

有限自动机(Finite automata)

定义有限自动机 Finite automata

有限自动机

初始状态和最终状态可以是同一个

图 1 状态图表示自动机

确定性有限自动机 DFA (Deterministic Finite Automata)

  1. 特点:每一步的转移都是确定的，执行逻辑：输入一个字符串，从初始状态，每次取出第一个字符，根据当前状态和字符查找转移函数，得到下一个状态，直到字符串为空

  2. 表示当前状态 configuration

    • C = (q,ω)，q为当前状态，ω为当前剩余的字符串

  3. 表示状态的转移 Yield

    • 可一步转移到：yields in one step

      • 记为
      • 即从当前状态再读取一个字符，可以转移到下一个状态

    • 可转移到：yields

      • 记为

  4. 自动机接受 Accepts字符串

    • 当我们从初始状态s开始，经过由字符串ω 规定的转移路径，最终可能到达最终状态q，也可能到达非最终状态
    • 即可以从初始状态s经过由字符串ω 规定的转移路径，最终转到最终状态q，且剩余的字符串为空
    • 否则,如果没有边可以走,或者停在了non-final状态,则认为拒绝 Reject该字符串

  5. 自动机对应的语言

    • ，也就是说，M accept L的条件有两个：

      • M接受所有L(M)中的字符串
      • 此外，M不接受L(M)以外的字符串
    • 接受语言的唯一性：很好证明

将正则表达式转为DFA

DFA实现

DFA解决最长匹配问题

非确定性有限自动机(Non-Deterministic Finite Automata)

概念:NFA

  1. 特点:每一步的转移可能不确定，即使得到了当前状态和下一个接收的symbol，也不一定能确定下一个状态

  2. NFA和DFA的区别：

    • 同一个状态,同一个条件,可以有多个转移方案:对于一个输入，NFA 可以有多种路线(分支路线)，有些会被接受，有些会被拒绝，但只要有一种路线能够接受，就认为 NFA 接受该输入，（反之所有的都拒绝了，则认为NFA不接受该输入）

    • 因此,我们不使用函数δ而是大写的Δ来表示状态的转移,这种转移不是一个函数而是一个关系，称为transation relation：

    • 上式中读入的字符可以是空字符e,意味着可以有 e-transition，即不消耗字符的转移

“一种理解方式：NFA 可以猜测该往哪里转移，且总能猜对,NFA只是纯数学的定义，但是不妨碍我们理解其概念，比如使用并行的思想来理解NFA的概念。 “

将正则表达式转为NFA

NFA转DFA

注意如果DFA包含一个及以上的NFA终止状态,那么我们认为该DFA到达终止状态,到达最终状态时,这个DFA中可能包含多个NFA状态,此时我们根据优先级确定输出的token类型

练习题

图 7 将以上NFA转化为DFA,见作业
图 8 PPT中的举例

DFA的简化

化简DFA

图 10 化简DFA的过程

注意 标识不同token的final state是不等价的,因此在初始化时,除了将final states和non-final states划分,也需要将识别不同token的final state单独分组,即∏={K-F ,F1,F2,…,Fk}

词法分析器的生成器(Lex)

概念

代码分析

Parsing 语法分析

Overview

语法分析

图 11 Parser接收Lexer生成的token流,生成抽象语法树

作用

图 12 语法分析树的作用

构造语法分析器

上下文无关文法(Context-free grammar)

概念

Context-free grammars由以下规则定义(TCS中的定义)

Context-free Language

语法分析器的生成规则

推导

四则运算的推导

  1. E -> E * E
  2. E -> E / E
  3. E -> E + E
  4. E -> E - E
  5. E -> id
  6. E -> num
  7. E -> (E)

歧义

四则运算的推导

文件结束符(EOF)

总结 光知道语法规则是不够的,为了获得Parse Tree,我们还需要能够根据(语法规则+输入串)构建Parse Tree的算法(机器),即Parser:

  1. Universal Parser:任意的CFG都能生成分析器,然而非常低效,因为经常需要回溯
  2. Top-Down Parser:从根节点向叶子结点构建
  3. Bottom-Up Parser:从叶子结点向根结点构建

从上到下分析(Top-Down Parsing)


Top-Down Parsing的过程就是为输入寻找最左推导的过程

从一个例子出发

寻找最左推导

递归下降分析(Recursive-descent parsing)

注意

预测分析(Predictive Parsing)

Predictive Parsing(LL(k) parsing)

  1. 第一步:对于一个非终结符，获取其所有可能生成的字符串的第一个token

    • 为了形式化的描述,我们需要引入几个新概念:

      First() and Follow() set

      • γ,β,σ:a string of terminal and nonterminal symbols
      • t:a terminal symbol
      • X:a non-terminal symbol
      • S:the start symbol

      • FIRST(γ):if γ ->* tβ,then t ∈ First(γ)

        • γ 可以生成一个由t开始的字符串
        • FIRST(γ) 是所有这样的t的集合

      • Follow(X):if S->* β Xt σ,then t ∈ Follow(X)

        • 从起始符号开始,如果能够生成一个字符串,其中t紧跟着X,则t属于Follow(X)
        • Follow(X) 是所有这样的t的集合

      推论

      • 很明显,If the derivation contains XYZt where Y and Z both can derive ε, t ∈Follow(X)
      • 这就意味着,计算Follow(X)的时候,我们还要查看后续的非终结符是否可以生成空串

    • 找到First(X)和Follow(X)的算法:

      找到First(X)和Follow(X)的算法

      • 使用递归手段获得First(X):

      • Base case:

        1. 如果X为终结符,则First(X)={X}
        2. 如果X为非终结符,则First(X)首先初始化为空集

      • inductive step:

        1. 如果X -> Y1 Y2… Yn,则First(X) = First(X) ∪ First(Y1 Y2… Yn) = First(X) ∪ F1 ∪ F2… ∪ Fn,其中

          • F1 = First(Y1)
          • F2 = First(Y2) if Y1 ->* ε Otherwise, F2 = ∅
          • F3 = First(Y3) if Y1Y2 ->* ε Otherwise, F3 = ∅
          • …
          • Fn = First(Yn) if Y1Y2… Yn-1 ->* ε Otherwise, Fn = ∅
        2. 首先我们很容易看出,First(Y1)包含于First(X),因为Y1是X的第一个符号
        3. 其次,如果Y1可以生成空串,那么该情况下将其忽略,X生成的第一个non-terminal可以生成自Y2,Y3…Yn,需要把First(Y2)加入First(X)中,以此类推,如果Y2能够生成空串,就把First(Y3)加入First(X)中…
      • 使用类似手段获得Follow(X):

      • Base case:

        • 初始化Follow(X)={}

      • Inductive step:

        • For any strings α , β , if Y -> αXβ , then Follow(X) = Follow(X) ∪ First(β),这一步需要我们检查产生式的右边部分
        • For any strings α , β , if Y -> αXβ and β -> ε, Follow(X) = Follow(X) ∪ Follow(Y),同样,如果X后面的符号可以生成空串,就要查看生成式左边(LHS)的Follow()了

    • 从上面可以看出,知道一个非终结符是否能够产生空串十分重要,为了判定,我们引入新的概念:

      Nullable Symbols

      • Nullable(X)=True if X->ε

      • 使用迭代算法获得Nullable(X):

        获得Nullable for each symbol X:i
        Nullable(x)=False d
        repeat i
        for each productionX->Y1Y2…Yk: i
        if Nullable(Yi)=True for 1<=i<=k: i
        Nullable(X)=True d d d
        until Nullable did not change in this iteration

      • 以上的算法一定可停机,因为单调有上界

    • 伪代码:

      伪代码 下面是PPT中获得First/Follow/Nullable的算法,这是一个3个set一起算的算法,实际上我们会按照Nullable->First->Follow的顺序分开计算:

      计算First/Follow/Nullable Initialize FIRST and FOLLOW to all empty sets, and nullable to all false.
      for each terminal symbol Z i
      FIRST[Z]←{Z} d
      repeat i
      for each production X →Y1 Y2 ···Yk: i
      for each i from 1 to k, each j from i +1 to k: i
      if all the Yi are nullable i
      then nullable[X]←true d
      if Y1 ···Yi−1 are all nullable i
      then FIRST[X]←FIRST[X] ∪ FIRST[Yi] d
      if Yi+1 ···Yk are all nullable i
      then FOLLOW[Yi]←FOLLOW[Yi] ∪ FOLLOW[X] d
      if Yi+1 ···Yj−1 are all nullable i
      then FOLLOW[Yi ]←FOLLOW[Yi] ∪ FIRST[Yj ] d d d
      until FIRST, FOLLOW, and nullable did not change in this iteration

    • 下面用一个具体的例子来说明获得First(X)和Follow(X)的过程:

      获得First(X)和Follow(X)的过程

      • Grammar:

        1. Z -> X Y Z
        2. Z -> d
        3. Y -> c
        4. Y ->
        5. X -> a
        6. X -> Y

      • 获取NUllable(X):

        1. 第一次遍历:Y可空
        2. 第二次遍历:X可空
        3. 第三次遍历:没有变化

        • 确定了Nullable(X):

          NullableFirstFollow
          ZFalse
          YTrue
          XTrue

      • 获得First(X):

        1. 观察Z的First:

          • 很明显,Z的First包含d
          • 检查X,X的First包含a,X->Y,Y可空,需要检查Y
          • 检查Y,Y的First包含c,Y可空,需要检查Z,但是没有意义了
        2. XY的First都已经确定

        • 于是我们确定了First:

          NullableFirstFollow
          ZFalse{d,a,c}
          YTrue{c}
          XTrue{a,c}

        First内部产生的,因此我们需要观察的是生成式左边,而Follow是外部的,因此需要观察生成式右边

      • 获得Follow(X):

        1. 观察第一条,得到:

          • First(Y)中的都属于Follow(X)
          • X可以为空,因此First(Z)中的都属于Follow(X)
          • First(Z)中的都属于Follow(Y)
        2. 观察后续几条,没有发现新的

        • 总结:

          NullableFirstFollow
          ZFalse{d,a,c}{}
          YTrue{c}{d,a,c}
          XTrue{a,c}{d,a,c}

  2. 第二步:确定选择产生式的条件:

    • 对于某个非终结符X,如果它的某个产生式X->γ 满足一下任意一条,那么就可以选择该产生式:

      1. 下一个token在First(γ)中
      2. 下一个token在Follow(X)中,并且γ ->* ε

    • 在前面的例子中,我们已经得到了下表:

      NullableFirstFollow
      ZFalse{d,a,c}{}
      YTrue{c}{d,a,c}
      XTrue{a,c}{d,a,c}

    • 以及以下生成式:

      1. Z -> X Y Z
      2. Z -> d
      3. Y -> c
      4. Y ->
      5. X -> a
      6. X -> Y

    • 下面开始检查:

      1. 对于Z:

        1. 读到a

          1. 选择Z -> X Y Z,First(XYZ)={d,a,c},因此可以选择该产生式
          2. 选择Z -> d,First(d)={d},忽略

        2. 读到d

          1. 选择Z -> X Y Z,First(XYZ)={d,a,c},因此可以选择该产生式
          2. 选择Z -> d,First(d)={d},因此可以选择

        3. 读到c

          1. 选择Z -> X Y Z,First(XYZ)={d,a,c},因此可以选择该产生式
          2. 选择Z -> d,First(d)={d},忽略

      2. 对于Y:

        1. 读到c

          1. 选择Y -> c,First(c)={c},因此可以选择
          2. 选择Y ->,查看Follow(Y),Follow(Y)={d,a,c},因此可以选择

        2. 读到d

          1. 选择Y -> c,First(c)={c},忽略
          2. 选择Y ->,查看Follow(Y),Follow(Y)={d,a,c},因此可以选择

        3. 读到a

          1. 选择Y -> c,First(c)={c},忽略
          2. 选择Y ->,查看Follow(Y),Follow(Y)={d,a,c},因此可以选择

      3. 对于X:

        1. 读到a

          1. 选择X -> a,First(a)={a},因此可以选择
          2. 选择X -> Y,Y可产生空串,查看Folllow(X)={a,c,d},因此可以选择

        2. 读到c

          1. 选择X -> a,First(a)={a},忽略
          2. 选择X -> Y,Y可产生空串,查看Folllow(X)={a,c,d},因此可以选择

        3. 读到d

          1. 选择X -> a,First(a)={a},忽略
          2. 选择X -> Y,Y可产生空串,查看Folllow(X)={a,c,d},因此可以选择

  3. 第三步:获得Parsing table

    • 基于上面得到的规律,我们可以构造一张表,用于描述当前非终结符在读取到下一个token时的选择:
    • 如果在实际匹配的时候获得的结果是一个Empty entry,说明发生了语法错误
    • 如果每一个格子都有小于等于1个enrty,那么称其为LL(1)文法(Left-to-right parse, left-most derivation, 1 symbol lookahead)
    • 类似的,LL(2)文法的lookahead token为aa,ab,ba,bb,ac,ca…

    注意 任何有二义性的文法都不是LL(K)文法

通过重写文法修复漏洞

处理语法错误

总结

  1. 至此我们学习了构建LL(K) parser(Predictive Parsing),为一些简单的CFG构建parser,如果构建失败,说明这并不是一个LL(K)文法,需要进行一些修改,比如左因子化,消除左递归等等
  2. LL(k)文法向前看k个token就必须选择一个产生式,超过这个长度就选择不了,接下来介绍一些更加强大的构建方式

自底向上分析(Bottom-Up Parsing)

概念

Bottom-Up Parsing

从一个例子出发

LR(1) Parsing

使用DFA描述Parser

注意

描述/构造一个LR(0) Parser

确定Parser的状态转移

确定Parser的行为

构建Parsing Table

Simple LR(SLR) Parsing

注意

LR(1) Parsing

LALR(1) Parsing

实践中使用LR Parsing

实现Parser (Implementation)

手写Parser

Yacc

基础语法
yyval的类型问题:

  1. 第一种方法:使用%union关键字在.y文件中直接声明,不同类型的变量占用同一块数据空间,根据需要将数据解析为对应的数据类型

    %union { double val;
char op;}
    • 使用上面的方式修改Rule部分:
  2. 第二种方法:定义一个新的类型,然后将YYSTYLE定义为该类型,然而必须手动定义 #define YYSTYPE ASTNode
Embedded Actions
冲突
优先级指令

错误恢复(Error Recovery)

关于错误恢复

局部错误恢复(Local Error Recovery)

Local Error Recovery

全局错误修复(Global Error Repair)

Abstract Syntax 抽象语法

语义动作(Semantic Action)

编译器的作用

递归下降分析

在Yacc中实现语义动作

抽象语法树(Abstract Parse Tree)

关于抽象语法树

具象语法树(Concrete Parse Tree)

抽象语法树(Abstract Parse Tree)

实现AST

typedef struct A_exp_ *A_exp;
struct A_exp_ {
  enum {A_numExp, A_plusExp, A_timesExp} kind; 
  union {
    int num; 
    struct {A_exp left; A_exp right;} plus;
    struct {A_exp left; A_exp right;} times; 
  } u; 
};
A_exp A_NumExp(int num);
A_exp A_PlusExp(A_exp left, A_exp right);
A_exp A_TimesExp(A_exp left, A_exp right);
A_exp A_PlusExp(A_exp left, A_exp right) {
  A_exp e = checked_malloc(sizeof(*e));
  e->kind = A_plusExp;
  e->u.plus.left = left;
  e->u.plus.right = right;
  return e;
}

维护token位置信息

Semantic Analysis 语义分析

Overview

符号表(Symbol Table)

概念

符号表

多个符号表共存的情况

符号表的实现

Tiger编译器中的符号表

类型检查(Type Checking)

总结

  1. 如何定义合法的表达式,包括:int,string,nil,array of int
  2. 如何定义类型等价
  3. 如何确定类型检查的规则

Tiger语言中的Type

Tiger语言中的Type

定义类型的等价

定义类型的等价

  1. 名字等价(name equivalence,NE):T1 and T2 are equivalent iff T1 and T2 are identical type names defined by the exact same type declaration.
  2. 结构等价(structural equivalence,SE):T1 and T2 are equivalent iff T1 and T2 are composed of the same constructors applied in the same order.

Tiger的名称空间和环境

Tiger的名称空间

注意

Tiger的类型检查

Activation Records 活动记录


Overview

栈帧(Stack Frame)

栈指针(Stack Pointer)

  1. 函数调用时:

    • 将老FP保存在frame中
    • FP = SP
    • SP = SP - size of frame

  2. f退出时:

    • SP = FP
    • 取回老FP

    如果f的frame size固定,那么改变更简单,FP只要变成SP+size即可,否则,需要由compiler计算

寄存器(Register)

参数传递(incoming arguments, outgoing arguments)

返回地址(Return Address)

总结

静态链接(Static Link)

基于逐层访问的静态链接

使用Display代替Static Link

Lambda lifting

higher-order functions

Tiger中的Frames(Frames in Tiger)

Interface

局部变量(Local Variables)

Temporaries and Labels

  1. Temps : abstract names for local variables
  2. Labels: abstract names for static memory addresses
/* temp.h */
typedef struct Temp_temp_ *Temp_temp;
Temp_temp Temp_newtemp(void);

typedef S_symbol Temp_label;
Temp_label Temp_newlabel(void);
Temp_label Temp_namedlabel(string name);
string Temp_labelstring(Temp_label s);

typedef struct Temp_tempList_ *Temp_tempList;
struct Temp_tempList_ {Temp_temp head; Temp_tempList tail;}
Temp_tempList Temp_TempList(Temp_temp head, Temp_tempList tail);

typedef struct Temp_labelList_ *Temp_labelList;
struct Temp_labelList_{Temp_label head; Temp_labelList tail;}
Temp_labelList Temp_LabelList(Temp_label head, Temp_labelList tail);

Translate Layer

Intermediate Code 中间语言

Overview

IR树(IR tree)

概念

IR tree节点

将AST转为IRT(AST to IR tree)

概念

翻译表达式

表达式的转换

简单变量 Simple Variable

数组变量

现在我们能够理解为什么所有变量都是一个字长了,因为不会进行深拷贝

Structured L-values

处理数组元素和记录域

算数

条件表达式

Example

while循环

for表达式

函数调用

翻译声明


变量声明
函数声明
其他

Canonical IR 规范中间表示(Basic Block&Trace)

Overview

第一步:重写IR树(Rewriting IR Tree)

canonical tree

消除ESEQ

将CALL节点移动至顶部

消除SEQ节点

总结

第二步:划分基本块(Dividing into Basic Blocks)


基本块

将程序分割为基本块

第三步:轨迹 Traces(真正解决cjump问题)

获得最小化的trace集合

DFS Put all basic blocks into Q
while Q is not empty do i
start a new trace T
pop the head element of Q
while b is not marked i
mark b;append b to the end of T
for each successor of b do i
if the successor is not marked do i
b <- successor d d d
end the current Trace

优化算法

Abstract Assembly Code 抽象汇编指令

Overview

树型与指令集(Tree Pattern and Instruction Set)

树型

树型与指令集的对应

算法(Matching Algorithm)

覆盖算法

Maximal Munch

Dynamic proigramming

指令流出

算法复杂度

CISC指令集(CISC Instruction Set)

有关CISC指令集

问题与解决

Tiger实现(Tiger Implementation)


Liveness Analysis 活跃分析

Overview

流程图分析(Dataflow Graph Analysis)

描述数据流图

注意

活跃性推导

注意

时间复杂度分析

一些讨论(Discussions)

改进

实现

静态/动态活跃性(Static/Dynamic liveness)

Register Allocation 寄存器分配

Overview

冲突图(Interference Graphs)

概念

表示冲突情况

染色算法(Coloring Algorithm)

Build

Simplify

Spill

注意 spill还分为actual spill和potential spill,前者才是真正溢出的节点

Select

总结

Coalescing

  1. Briggs

    • 算法:

      Briggs

      1. 尝试合并节点a和b
      2. 查看新节点的邻居
      3. 如果degree大于等于k的邻居节点个数小于k,就可以合并
    • 其原理在于,经过simplify的图只包含degree大于等于k的节点,邻居小于k说明可以被simplify删除

  2. George

    • 算法:

      George

      1. 查看a的每一个邻居t
      2. 如果对于每个t而言,t要么已经与b互斥,要么b的degree小于k(insignificant degree),那么就可以将其合并

    • 其原理在于,对于t而言:

      1. 同时与ab互斥,说明合并ab后不会增加t的degree
      2. degree小于k,说明它本来就可以通过simplify删除

    注意

    • 助教老师在期末复习时提到:
    • 同学们好，也有同学对这页 PPT 里 a & e 为什么不能使用 George 法则进行合并有疑问。这里统一答复一下。
    • 省流：从理论上看，其实可以使用课本上给出的 George 法则对 a & e 进行 coalescing，只不过 coalesce 后仍然无法继续进行 coloring，因此需要进入 actual spill 流程。而在具体实现中， George 只用于一边是 precolored，另一边不是 precolored 的情况，并且使用 George 法则时，下面这页 PPT 中的 b 需要对应 precolored，a 对应 non precolored node。
    • 虎书在第 11 章介绍寄存器分配的 coalesce 时，由于还没介绍到 precolored，顺序比较混乱，因此单看这一节（11.2）其实对 George 的描述并不是原文的描述。在 11.4 节讲解图染色算法实现时，有如下表述：
    • 也就是说，在实现时其实对于两边都 non-precolored 的情况，使用 Briggs；而有一边为 precolored 时使用 George。然而，在课本使用的伪代码（即 George 等人，Iterated Register Coalescing，1996 年）中，其实只使用了考虑了 precolored node 版本的 George 法则进行合并。在 Iterated Register Coalescing 这篇论文的实现细节部分，考虑了 precolored node 后对 Coalesce 条件的表述如下：
    • 而对应的伪代码中也是这么做的：
    • 是的，尽管论文前文中也说了使用 Briggs 法则进行 coalescing，但在那个部分还不涉及 precolored node。而在实现细节中考虑 precolored node 后，才真正给出了 George 法则的具体表述。如果遵循论文中的伪代码来实现，实际上并没有用到 Briggs 法则来 Coalescing。（论文内容与具体实现有些许不一致其实挺常见的，有参与科研的同学或许深有体会）这里同样给出 Briggs 等人，Improvements to Graph Coloring Register Allocation，1994 年论文中提出的 Coalesce 条件：
    • 由于不涉及 precolor node，此处与虎书上表述一致。 其实虎书这一章节的行文顺序和 George 等人的论文 Iterated Register Coalescing 基本一致，只是合并了 Briggs 法则的内容。可能虎书作者出于某些考虑将 George 法则中关于 precolored 的相关部分删去并与 Briggs 法则一起介绍，然而 George 法则在实现时只用于包含 precolored node 的情况。 不过，即使使用课本上的 George 法则对 a & e 合并，最后仍然需要进入 actual spill 阶段，只不过虎书对于这部分没有详细展开，直接快进到进行 actual spill 阶段。
    • 同学们好，之前这里对伪代码的解释有点问题。在实现中也是在有一边是precolored时使用George，两边都是non-precolored时使用Briggs。并且在使用George时，是对Non precolored node的邻居来判断是否符合条件。

总结

预先着色节点(Precolored Nodes)

概念

在分配寄存器时保护precolored nodes

一个例子

caller/callee-save的选择

总结

Garbage Collection 垃圾收集

Overview

Mark-and-Sweep Collection

算法描述

优化DFS算法

  1. 优化一:使用stack:

    function DFS(x)
  if x is a pointer and record x is not marked
    mark record x
    t ← 1
    stack[t] ← x       // push the start of DFS on stack
    while t > 0
      x ← stack[t]; t ← t – 1 // pop an item from the stack
      for each field fi of record x
        if x. fi is a pointer and record x.fi is not marked
          mark x. fi
          t ← t + 1; stack[t] ← x. fi
    • 这样我们就不使用activation records而是word(pointer)来记录,更省空间,但是stack大小可能和我们要分析的Heap大小一样了!

  2. 优化二:Pointer Reversal

    • 该方法直接在graph中进行操作,而不是使用stack

      function DFS(x)
  if x is a pointer and record x is not marked
    t ← nil
    mark x; done[x] ←  0
    while true
      i ← done[x]
      if i < # of fields in record x
        y ← x. fi
        if y is a pointer and record y is not marked
          x. fi ← t; t ← x; x ← y
          mark x; done[x] ← 0
        else
          done[x] ← i + 1
      else
        y ← x; x ← t
        if x = nil then return
        i ← done[x]
        t ← x. fi; x. fi ← y
        done[x] ← i + 1
  •done: how many fields in each record
  have been processed
  •t: the top of the stack

    • 当遇到新的record x时:

      1. Mark x
      2. 在DFS(x.fi)前,反转指向x.fi的指针,使其指向x(pointer reversal)
      3. 当DFS无法继续进行时,那么通过这个反向指针回到上一层,然后将方向恢复原样

优缺点

Reference Counts


可以类比文件系统中的Reference Count

主要思想

Reference Counts

算法

优缺点

Copying Collection

基本思想

Pointer forwarding

注意

Cheney’s Algorithm

混合算法


优缺点

Interface of the compiler

Fast Allocation

Data Layout

Pointer Map

Derived Pointers