寄存器分配引论


序一
序二
前言

第1章    基础知识
    1.1    控制流图
        1.1.1    流图的定义
        1.1.2    流图的数据结构
        1.1.3    流图的构造
    1.2    活跃分析
        1.2.1    数据流方程
        1.2.2    不动点算法
    1.3    干涉图
    1.4    寄存器分配
        1.4.1    栈分配策略
        1.4.2    寄存器分配策略
    1.5    深入阅读

第2章    图着色分配
    2.1    基本思想
    2.2    Kempe算法
        2.2.1    Kempe定理及其应用
        2.2.2    乐观着色
    2.3    溢出
        2.3.1    溢出着色
        2.3.2    溢出策略
    2.4    接合
        2.4.1    激进接合
        2.4.2    保守接合
        2.4.3    迭代接合
    2.5    干涉的保守性
    2.6    深入阅读

第3章    线性扫描分配
    3.1    基本思想
    3.2    活跃区间分析
        3.2.1    线性序
        3.2.2    活跃区间算法
    3.3    线性扫描分配
        3.3.1    分配算法
        3.3.2    溢出和接合
        3.3.3    时间复杂度
    3.4    深入阅读

第4章    弦图分配
    4.1    弦图
    4.2    弦图基本性质
        4.2.1    OO消去序列
        4.2.2    O大势算法
    4.3    弦图分配算法
        4.3.1    分配算法
        4.3.2    溢出
        4.3.3    接合
        4.3.4    时间复杂度
    4.4    深入阅读

第5章    SSA分配
    5.1    SSA及其基本性质
        5.1.1    SSA的性质与构造
        5.1.2    语义
        5.1.3    SSA消去
    5.2    SSA上的活跃分析和干涉图
        5.2.1    活跃分析算法
        5.2.2    SSA与弦图
    5.3    SSA寄存器分配算法
        5.3.1    整体架构
        5.3.2    溢出
        5.3.3    着色
        5.3.4    φ消去
        5.3.5    接合
        5.3.6    时间复杂度
    5.4    深入阅读

第6章    线性规划分配
    6.1    整数线性规划基础
        6.1.1    线性规划的定义
        6.1.2    线性规划的求解
        6.1.3    问题求解的模型
    6.2    寄存器分配
        6.2.1    约束生成
        6.2.2    目标函数
        6.2.3    约束求解
    6.3    寄存器指派
        6.3.1    活跃区间切分
        6.3.2    指派算法
        6.3.3    时间复杂度
    6.4    深入阅读

第7章    PBQP分配
    7.1    二次分配问题基础
        7.1.1    二次分配问题
        7.1.2    PBQP
    7.2    PBQP寄存器分配模型
        7.2.1    问题求解的一般步骤
        7.2.2    寄存器分配的PBQP模型
        7.2.3    PBQP图
    7.3    PBQP寄存器分配算法
        7.3.1    PBQP寄存器分配算法
        7.3.2    PBQP求解算法
        7.3.3    时间复杂度
    7.4    深入阅读

参考文献
寄存器分配引论

目 录

目录
