decaf-doc
  • Introduction
  • pa1a
    • 实验内容
    • lalr1使用指导
      • 编写lexer
      • impl块的可选属性
      • 产生式和语法动作
      • 解决冲突
      • 一个完整的例子
    • 抽象语法树
    • 框架中部分实现的解释
    • 文件结构
  • pa1b
    • 实验内容
    • lalr1使用指导
    • 错误恢复
    • 文件结构
  • pa2
    • 实验内容
    • 语义分析
    • 符号表
    • 语句的返回类型
    • visitor模式
    • 框架中部分实现的解释
  • pa3
    • 实验内容
    • 中间代码
    • 中间代码中的类型信息
    • 运行时存储布局
    • 面向对象机制
    • tacvm介绍
  • pa4
    • 实验内容
    • 基本块
    • 数据流分析概述
    • 数据流优化概述
    • 公共表达式提取
    • 复写传播
    • 常量传播
    • 死代码消除
  • pa5
    • 实验内容
    • 图着色基本原理
    • 改进干涉图节点
    • 着色算法
    • 预着色节点
    • 干涉图节点合并
    • 调用约定
Powered by GitBook
On this page

Was this helpful?

  1. pa3

中间代码中的类型信息

中间代码中的类型信息可以指导代码优化,所以任何成熟的中间代码一定都是保留着相当完整的类型信息的。然而因为实现的复杂度的限制,这一点在我们的tac中几乎完全没有体现出来。

以jvm的byte code为例,byte code中保留了非常丰富的类型信息,例如一句

  System.out.println("hello world");

javac生成的byte code是:

  getstatic     #2                  // Field java/lang/System.out:Ljava/io/PrintStream;
  ldc           #3                  // String hello world
  invokevirtual #4                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V

这完全不像我们的tac中,可能会算出out的位置,println在虚表中的偏移量等等,然后用访存+call来实现这次调用。表面看起来javac似乎是很"不负责任"的,因为这样的中间代码如果直接按照字面意思来执行,显然是非常低效的;然而实际上正是因为这些信息的保留,让jvm可以充分利用它来优化代码,也很自然地就支持了反射等动态特性。与这种高度抽象的设计相反,我们设计的tac都是相当底层的,但是这也只能说是无奈之举,可以想象如果不这样设计的话,后续翻译到机器码的阶段会很困难,而且模拟器也较难实现,所以说我们其实没有太多选择。

那么为什么类型信息可以帮助优化代码呢,这里可以举一个非常简单的例子:

  static int foo(A a, B b) {
    b.a = 1;
    a.a = 2;
    return b.a;
  }

假设A和B是两个java类,二者之间没有继承关系,那么可以直接断定这个函数的返回值是1,jvm做起这种优化来非常轻松。而如果中间代码只提供了这些信息:

  *(%1 + xxx) = 1
  *(%0 + yyy) = 2
  return *(%1 + xxx)

那么只通过这个函数本身来确定它的返回值是不可能的。

作为一种尝试,我往我们的tac中添加了非常有限的类型信息(其他版本的实验框架中应该是完全没有这个设定)。我们能够做的优化其实是非常初级的,这个大家到了pa4就会看到,所以我们传递的类型信息也是很简单的,包括:

  1. 访存指令的性质,它是load/store了数组,对象,还是一块"不可变"的内存区域?

    • "不可变"的内存区域包括访问虚表指针,访问虚表,访问数组长度等,对它们的store相当于赋初值

  2. 函数参数表中是否有对象/数组为参数?

在pa4中的公共表达式提取这种优化手段中我们会描述怎么样使用这些信息。再次声明我们的实现非常简单,甚至显得有些幼稚,主要目的还是展示类型信息的确可以帮助中间代码优化,并不期望真的能够达到多么优秀的优化效果。

值得注意的是,按照惯例我们的pa4和pa5并不会包含每年的新特性,所以大家在实现新特性的时候,原则上对于这些类型信息是可以随便填写的(虽然我相信按照实际意义去填写也并不是很困难),这样一来类型信息就不会给大家带来额外的难度。

Previous中间代码Next运行时存储布局

Last updated 5 years ago

Was this helpful?