MENU

【编译原理】5、代码生成

June 1, 2020 • Read: 98 • 编程之路,编译原理

编译原理目录
1、词法分析
2、语法分析(重点)
3、语法制导翻译与抽象语法树
4、语义分析
5、代码生成
6、中间代码与程序分析
7、代码优化

五、代码生成

代码生成任务:抽象语法树 => 翻译1 => 中间表示1 => 翻译2 => 中间表示2 => ... => 翻译n => 中间表示n => 汇编

最简单的结构

抽象语法树 => 翻译(代码生成) => 汇编

6.1 代码生成的任务

  • 负责把源程序翻译成“目标机器”上的代码

    • 目标机器:可以是真实物理机器、可以是虚拟机。
  • 两个重要任务:

    • 给源程序的数据分配计算资源
    • 给源程序的代码选择指令

6.1.1 给数据分配计算资源

  • 源程序的数据:

    • 全局变量、局部变量、动态分配
  • 机器计算资源:

    • 寄存器、数据区、代码区、栈区、堆区
  • 根据程序的特点和编译器的设计目标,合理的为数据分配计算资源

    • 例如:变量放在内存里还是寄存器里?

6.1.2 给代码选择合适的机器指令

  • 源程序的代码:

    • 表达式运算、语句、函数等
  • 机器指令:

    • 算术运算、比较、跳转、函数调用返回
  • 用机器指令实现高层代码的语义

    • 等价性
    • 对机器指令集体系结构(ISA)的熟悉

6.1.3 路线图

  • 为了理清代码生成涉及的重要问题和解决方案,将研究两种不同的ISA上的代码生成技术

    • 栈计算机Stack
    • 寄存器计算机Reg

6.2 栈式计算机

  • 栈式计算机在历史上非常流行(上世纪70年代曾有很多栈式计算机)
  • 但今天已经基本上已经退出了历史舞台(效率问题)
  • 我们还要讨论栈式计算机的代码生成技术的原因是:

    • 给栈式计算机生成代码是最容易的
    • 仍然有许多栈式的虚拟机:Pascal P codeJava virtual machine (JVM)Postscript...

6.2.1 栈式计算机Stack的结构

  • 内存:存放所有的变量
  • 栈:进行运算的空间
  • 执行引擎:指令的执行

6.2.2 栈计算机的指令集(ISA)

是Java字节码的一个子集!

指令的语义:

  • push
push NUM:
    top++;
    stack[top] = NUM;
  • load x
load x:
    top++;
    stack[top] = x; // 从内存中加载到栈顶
  • store x
store x:
    x = stack[top];
    top--;
  • add
add:
    temp = stack[top-1] + stack[top];
    top -= 2;
    push temp;
  • times
times:
    temp = stack[top-1] * stack[top];
    top -= 2;
    push temp;
  • and
and:
    temp = stack[top-1] && stack[top];
    top -= 2;
    push temp;

6.2.3 变量的内存分配伪指令

  • Stack机器只支持一种数据类型int,并且给变量x分配内存的伪指令是: .int x
  • Stack机器在装载一个程序时,就会读取伪指令,并且给相关变量分配内存空间。

示例:

6.3 栈式计算机的代码生成

6.3.1 ++递归下降代码生成算法++ :从C--到Stack

6.3.2 表达式的代码生成

// 不变式:表达式的值总在栈顶
Gen_E(E e)
  switch (e)
      case n: emit ("push n"); break;
      case id: emit ("load id"); break;
      case true: emit ("push 1"); break;
      case false: emit ("push 0"); break;
      case e1+e2: Gen_E (e1);
                  Gen_E (e2);
                  emit ("add");
                  break;
      case e1&&e2: Gen_E (e1);
                  Gen_E (e2);
                  emit ("and");
                  break;

6.3.3 语句的代码生成

// 不变式:栈的规模不变
Gen_S(S s)
  switch (s)
      case id=e:  Gen_E(e);
                  emit("store id");
                  break;
      case printi(e): Gen_E(e);
                      emit ("printi");
          break;
      case printb(e): Gen_E(e);
                      emit ("printb");
                      break;

6.3.4 类型的代码生成

// 不变式:只生成.int类型
Gen_T(T t)
  switch (t)
      case int:  emit (".int");
                 break;
      case bool: emit (".int");
                 break;

6.3.5 变量声明的代码生成

// 不变式:只生成.int类型
Gen_D(T id; D)
  Gen_T (T);
  emit (" id");
  Gen_D (D);

6.3.6 程序的代码生成

Gen_P(D S)
    Gen_D (D);
    Gen_S (S);

6.4 寄存器计算机及其代码生成

  • 寄存器计算机是目前最流行的机器体系结构之一

    • 效率很高
    • 机器体系结构规整
  • 机器基于寄存器架构:

    • 典型的有16、 32或更多个寄存器,所有操作都在寄存器中进行。
    • 访存都通过load/store进行,内存不能直接运算。

6.4.1 寄存器计算机Reg的结构

  • 内存:存放溢出的变量
  • 寄存器:进行运算的空间,假设有无限多个
  • 执行引擎:指令的执行

6.4.2 寄存器计算机的指令集

注意:movn n, r 是把整数n的值赋给r,源操作数在左,目的操作数在右。后面同理

6.4.3 变量的寄存器分配伪指令

  • Reg机器只支持一种数据类型int,并且给变量x分配寄存器的伪指令是: .int x
  • 在代码生成的阶段,假设Reg机器上有无限多个寄存器。因此每个声明变量和临时变量都会占用一个(虚拟)寄存器。
  • 把虚拟寄存器分配到物理寄存器的过程称为寄存器分配。

6.4.4 递归下降代码生成算法:从C--到Reg

6.4.5 表达式的代码生成

// 不变式:表达式的值在函数返回的寄存器中
R_t Gen_E(E e)
  switch (e)
    case n: r = fresh(); //拿到一个寄存器
            emit ("movn n, r");
            return r;
    case id:  r = fresh ();
              emit ("mov id, r");
              return r;
    case true:  r = fresh ();
                emit ("movn 1, r");
                return r;
    case false: r = fresh ();
                emit ("movn 0, r");
                return r;
    case e1+e2: r1 = Gen_E(e1);
                r2 = Gen_E(e2);
                r3 = fresh();
                emit ("add r1, r2, r3");
                return r3;
    case e1&&e2:  r1 = Gen_E(e1);
                  r2 = Gen_E(e2);
                  r3 = fresh();
                  emit ("and r1, r2, r3");
                  return r3; // 非短路

6.4.6 语句的代码生成

Gen_S(S s)
  switch (s)
    case id=e: r = Gen_E(e);
               emit("mov r, id");
               break;
    case printi(e): r = Gen_E(e);
                    emit ("printi r");
                    break;
    case printb(e): r = Gen_E(e);
                    emit ("printb r");
                    break;

6.4.7 类型的代码生成

// 不变式:只生成.int类型
Gen_T(T t)
  switch (t)
    case int: emit (".int");
              break;
    case bool: emit (".int");
               break;

6.4.8 变量声明的代码生成

// 不变式:只生成.int类型
Gen_D(T id; D)
  Gen_T (T);
  emit (" id");
  Gen_D (D);

6.4.9 程序的代码生成

Gen_P(D S)
  Gen_D (D);
  Gen_S (S);

6.4.10 示例

- - - 结束 - - -
  • 文章标题:【编译原理】5、代码生成
  • 文章链接:https://blog.canye365.cn/archives/310.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 11, 2021