跳转至

实验步骤

  1. 加载前端提供的中间代码, 视情况进行一些前处理.
  2. 视情况而定, 生成部分在代码生成时会用到的信息, 如变量的引用信息.
  3. 根据每条 IR 的类型, 参数类型确定对应的代码生成.
    • 寄存器全部被占用时直接抛出异常, 完成的标准为跑过样例 input-code.txt
  1. 加载前端提供的中间代码, 并进行一些前处理(对于想要完成寄存器分配的同学, 这步可以大大简化代码生成时繁琐的类型判断).
  2. 生成在代码生成时会用到的信息, 如变量的引用信息. (对于想要完成寄存器分配的同学, 这步可以在代码生成阶段便捷地取得你需要的信息).
  3. 根据每条 IR 的类型和参数, 目前的寄存器占用状态, 变量的生存信息, 内存的使用情况, 确定对应的代码生成.
    1. 进指令判断寄存器占用情况, 当占用满时需要溢出到内存中.
    2. 出指令判断变量存活情况, 释放占用的内存和寄存器.
    3. 完成的标准见 附加题.

提示

映射的维护

无论是否想要完成寄存器分配, 你都需要维护的信息为寄存器的占用信息. 这个信息可以通过一个 Map<IRVariable, Reg> 或 Map<Reg, IRVariable> 进行维护, 取决于你需要通过 IRVariable 拿到占用的 Reg 还是通过 Reg 找到占用其的 IRVariable. 通过 key 查找 value 的行为在 HashMap 中时间复杂度为 O(1).

Map 可以简单理解为一个单射, 通过 key 可以马上拿到其的像, 然而找到原像就相对复杂了. 而有时候我们更希望这个映射可以双向查找, 当然前提是这个映射本身就是一个双射. 于是我们期望维护一个可以双向查找的双射, 然而在 Java 的容器里没有双射, 需要自行想办法.

一个双射实现 
// 双射
public class BMap<K, V> {
    private final Map<K, V> KVmap = new HashMap<>();
    private final Map<V, K> VKmap = new HashMap<>();

    public void removeByKey(K key) {
        VKmap.remove(KVmap.remove(key));
    }

    public void removeByValue(V value) {
        KVmap.remove(VKmap.remove(value));

    }

    public boolean containsKey(K key) {
        return KVmap.containsKey(key);
    }

    public boolean containsValue(V value) {
        return VKmap.containsKey(value);
    }

    public void replace(K key, V value) {
        // 对于双射关系, 将会删除交叉项
        removeByKey(key);
        removeByValue(value);
        KVmap.put(key, value);
        VKmap.put(value, key);
    }

    public V getByKey(K key) {
        return KVmap.get(key);
    }

    public K getByValue(V value) {
        return VKmap.get(value);
    }
}

集合的维护

你可能需要维护集合, 并期望在尽可能短的时间里查找到某个元素是否在该集合中. 在 Java 中你可以通过使用 Set 实现. 特别的, 若你不需要集合中元素的加入顺序这一信息, 使用 HashSet, 若你需要这个信息, 使用 LinkedHashSet.

equals 与 hashCode 方法的重载

上述的集合对于对象的相等和对象的哈希值都通过 equals 与 hashCode 方法获取. 当你的对象没有实现单例, 包括显式或者隐式(即类定义或工厂方法未体现, 但在实际代码中是单例的), 也就是可能出现几个对象实际上是同一个然而却由于多次创建导致了指向不同的对象示例. 这时候需要手动重载 equals 与 hashCode 方法. 

class Student{
    int id;
    String name;
    int age;
    String school;

    @Override
    public boolean equals(Object obj){
        // 对于学生, 从实际情况来看 id 和 school 可以唯一确定
        return obj instanceof Student stu
            && name.equals(stu.name)
            && school.equals(stu.school);
    }

    @Override
    public int hashCode(){
        // 在 equals 里考虑的所有域都要考虑进来
        return Objects.hash(id, school);
    }
}