编译器设计（第2版）

20131104-notes-on-compiler-design.txt

编译器设计（第2版）
跳转至： 导航、 搜索

    p34 从NFA到DFA：Thompson子集构造法（e-closure）
    p39 从DFA到最小DFA：Hopcroft算法（检测２个状态是否等价）
    p55 DFA最小化：Brzozowski算法
        给定NFA n，等价的最小DFA：Reachable( subset( reverse( reachable( subset( reverse(n)))))) 
    p116 LL(1)、LR(1)
        SLR(1)用FOLLOW集来区分移进和归约，不再需要look ahead符号
        LALR(1)：集合中表示状态的项是一些关键项，其他项可从关键项导出，与SLR(1)等效 
    p176 IR
        IBM的FORTRAN H：4元组 + CFG
        GCC：GIMPLE -> RTL
        LLVM
        Open64：WHIRL 
    3地址表达式 + SSA？
        每次操作中使用某个名字作为参数时，该名字都编码了对应值的来源信息 
    p185 用于RISC的编译器倾向于寄存器到寄存器的模型 ...
        如果能够证明只有某个名字才能访问这个值，那么就可以把该值保存在寄存器中，否则必须保守地保存在内存中。 
    p205 作用域
        词法：一个名字引用的是词法上最接近的定义
        动态：自由变量绑定到运行时最近创建的同名变量
            早期LISP使用了动态作用域，在解释器中易于实现，但编译器中的高效实现则较为困难，
            可能产生难以检测难以理解的bug 
        Scheme中几乎所有对象（数据、（函数）表达式）处于单一名字空间，通过嵌套let可以产生任意深度的词法作用域 
    p206 Algol里的AR（活动记录）——为何在这里浪费大量篇幅呢？
    p20 Algol里的call by name
        编译器必须为每个名字产生一个函数，对相应的实参求值并返回一个指针，称为thunk
            R语言实现了thunk的惰性形式 
    p228 标准链接过程：过程：prologue/epilogue序列，调用：precall/postreturn序列
    p309 LVN（Local Value Numbering）算法
    p321 SVN（扩展到EBB）
    p328 活动信息
        汇点、DOM集、。。。等 
    p365 数据流分析 -> 静态单赋值形式
        Φ函数？
        p376 从SSA到其他形式的转换
            只需去掉下标，删除 Φ函数？但如果代码被重排或值重命名过，这种方法可能会产生不正确的代码
            ２个更微妙的问题：
                丢失复制（lost copy）：不可拆分关键边与复制折叠的共同作用将导致丢失复制问题
                交换（swap）：采用一个二阶段的复制协议。。。 
        p380 稀疏简单常量传播（SSCP） 
    p338 结构性数据流算法和可归约性
    p399 标量优化（略）
        LCM（Lazy Code Motion）
        code hoisting/sinking
        p451 TCO
        p435 LFTR 
    p450 通过树模式匹配进行指令选择
        BURS 
    p458 窥孔优化
        GCC RTL：将RTL解释为树，使用根据目标机器描述建立的简单树模式匹配程序
        （LLVM TableGen似乎也是这样的？）——有意思～ 
    指令调度＊
        软件流水线的策略＊＊ 
    寄存器分配（图着色）＊
    附录：ILOC