part3.md

B3 活跃变量分析

在第三部分，你需要完成活跃变量分析。

• 任务3-1

  你需要补充include/Optimize/LiveVar.h和src/Optimize/LiveVar.cpp中的LiveVar类，来实现一个完整的活跃变量分析算法，分析所有BasicBlock块的入口和出口的活跃变量，该算法基于SSA形式的CFG。
  在本次实验的框架中,BasicBlock类实现了4个和活跃变量分析相关的函数，你需要调用它们，设置所有BasicBlock的入口与出口处的活跃变量，以完成实验：

  // 设置该BasicBlock入口处的活跃变量集合。若活跃变量集合发生改变，返回true, 否则返回false。
  bool set_live_in(PtrSet<Value> in)
  // 设置该BasicBlock出口处的活跃变量集合。若活跃变量集合发生改变，返回true, 否则返回false。
  bool set_live_out(PtrSet<Value> out)
  // 获取该BasicBlock入口处的活跃变量集合
  PtrSet<Value>& get_live_in()
  // 获取该BasicBlock出口处的活跃变量集合
  PtrSet<Value>& get_live_out()

  LiveVar类中的execute函数会被调用来执行你实现的活跃变量分析算法，你需要将你的实现流程体现在该函数中。

  测试会将你的分析得到的每个基本块的IN和OUT和正确答案匹配。在本地环境下，你可以在test目录中使用python test_live_var.py来测试活跃变量分析算法的正确性。脚本生成的live_var.out和test.ll文件是临时文件，你可以忽略它。

• 任务3-2

  在实验报告doc/reports/B3.md中回答下列问题

  • B3-1. 请说明你实现的活跃变量分析算法的设计思路。

• Tips

  和上课时所讲的活跃变量分析不同，本次实验的活跃变量分析需要考虑phi指令，而数据流方程：$\rm OUT[B] =\cup_{S是B的后继}IN[S]$ 的定义蕴含着基本块S入口处活跃的变量在基本块S所有前驱的出口处都是活跃的。
  由于phi指令的特殊性(phi指令文档见doc/SysYFIR.md Phi小节)，例如%0 = phi [%op1, %bb1], [%op2, %bb2]如果使用如上数据流方程，则默认此phi指令同时产生了op1与op2的活跃性，而事实上只有控制流从%bb1传过来才有%op1的活跃性，从%bb2传过来才有%op2的活跃性。因此你需要对此数据流方程做一些修改。

  参考--dot-cfg选项，你可以使用opt --dot-cfg <xxx.ll>生成包含控制流图CFG的.dot文件(opt一般会和clang一起安装)，然后使用dot -Tpng -o <xxx.png> <xxx.dot>生成特定函数的CFG对应的png图片。dot工具可以通过sudo apt-get install graphviz安装。