目标语言

• 代码生成器的任务

  • 指令选择
  • 寄存器分配和指派
  • 指令排序

• 地址

  • 静态分配

    • call callee

      ST callee.staticArea, #here + 20
      BR callee.codeArea
      

    • return

      BR *callee.staticArea
      

    • name

      LD 112, #0
      LD 12(SP), #0
      

  • 栈式分配

    • call callee

      ADD SP, SP, #caller.recordSize
      ST 0(SP), #here + 16
      BR callee.codeArea
      

    • return

      BR *0(SP)
      SUB SP, SP, #caller.recordSize
      

基本块与流图

• 确定 leader
  • 第一个三地址指令
  • 任一个跳转指令
  • 任一个跳转目标指令
• 活跃性
  • 开始时非临时变量活跃
  • 反向扫描
  • i: x = y + z
    • x: 不活跃（之前的值不使用），无后续使用
    • y,z: 活跃，指明下一次使用设置为语句 i
• 循环定义
  • 存在唯一入口结点，前驱在循环之外，到达其余结点路径必然经过该结点

DAG

• DAG 图构造
  • 为基本块中每个出现的变量建立结点
  • x = y op z：建立指令结点 N，标号 op，令 x 和 N 关联
  • x = y：假设 y 关联 N，则 x 关联 N
• 消除死代码：在 DAG 图上消除没有附加活跃变量的根节点
• 数组引用
  • x=a[i] 对应于 =[] 的结点
  • a[j]=y 对应于 []= 的结点
• 指针赋值、过程调用：无法消除死码
• 重组基本块：如果两个指令间互相影响，则其顺序不该改变

代码生成器

• 尽可能把值保留在寄存器中
• 寄存器描述符：寄存器存放了哪些变量
• 地址描述符：各个变量的当前值存放在哪些位置
• getReg(I): 根据寄存器描述符合地址描述符等数据流信息，为指令 I 选择最佳的寄存器
• 减少 LD/ST 指令

寄存器分配

• v 的地址描述符可以在别的地方找到
• v 就是计算结果变量
• v 在之后不会被使用
• 生成保存指令 ST v, R 并修改地址描述符

优化

• 窥孔优化:使用滑动窗口检查目标指令
  • 冗余指令消除
  • 控制流优化
  • 代数化简/强度消减
  • 机器特有指令使用
• 全局寄存器分配
• 树重写实现指令选择
  • 重写规则：replacement <- template { action }

gcc 优化