Tai-e Assignments 踩坑记录

本来想一步步 git commit 传到 github 上的，后来发现不能直接上传解题代码，遂删库跑路（在写完 A1 之前 qwq）。

写到 A2 的时候就已经踩了不少坑，感觉还是有必要记录一下，万一真有幸运读者看到这个辣鸡的博客之后就成功 AC 了呢（

A1: 活跃变量分析和迭代求解器

活跃变量分析

• SetFact newBoundaryFact(CFG) 和 SetFact newInitialFact()
  • 返回一个空的 SetFact 即可
• boolean transferNode(Stmt,SetFact,SetFact)
  • 注意拷贝要用 out.copy() 方法而不是直接赋值
  • 要将一个 interface 实例当成某个 implementation class 的实例使用需要先用 instanceof 判断然后用 (Var) 强制转换

迭代求解器

• Solver.initializeBackward(CFG,DataflowResult)
  • 为了实现 meetInto 方法，需要将 IN 和 OUT 都赋上初值

A2: 常量传播和 Worklist 求解器

常量传播

• CPFact newBoundaryFact(CFG)
  • 为了 safety 的考虑，这里要初始化为 NAC
  • 我们要将所有出现在 CFG 中的 variables 全部初始化，所以需要用到 cfg.getIR().getParams()
  • 初始化的时候需要注意，对于 variable $v$，先检查是否属于 Integer 再进行初始化
• Value meetValue(Value,Value)
  • 就是课上讲到的 lattice 上的 $\cap$ 操作，分类讨论一下即可
• boolean transferNode(Stmt,CPFact,CPFact)
  • 
    只需要考虑 DefinitionStmt
  • 可以使用 CPFact 的 copyFrom() 方法更新的同时返回是否改变
  • 同样要考虑 variable 是否满足 canHoldInt
• Value evaluate(Exp,CPFact)
  • 
    根据这个判断 exp 分类讨论进行处理
  • 对应 Var 类型应该调用 in.get(v) 来得到 variable $v$ 的值
  • 对应 ArithmeticExp 类型中的 DIV 或者 REM 时注意判断除数/模数如果是 0 要返回 NAC
  • 对于 exp 的 operand lhs 和 rhs，两个中有一个为 NAC 时也要考虑如果 rhs 是 Constant 并且为 0 的情况
  • 最后如果 exp 不属于上图中的任一类型，应该返回 NAC 而不是 Undef，作业网站上有提到但是我没注意到（

Worklist 求解器

• Solver.initializeForward(CFG,DataflowResult)
  • 和 A1 一样记得 IN 和 OUT 都要赋值
• WorkListSolver.doSolveForward(CFG,DataflowResult)
  • worklist 本质只是一个元素不重复的普通的容器，你可以使用任意满足上述要求数据结构存储，但是用一个 HashSet 更省心（

A3: 死代码检测

死代码检测器

• Preparation: 把前两次作业的代码蒯进来，记得合并一下 backward 和 forward 的部分
• Set<Stmt> analyze(IR)
  • 主要注意一下 switch 语句可能会 fall through 的情况，本来以为这里需要用到 dfs，但是看了一眼 CFG 图，貌似 hit 到的 case 后面会有边连接到会 fall through 的 case，所以直接把 hit 的 case 加进来之后不管就行了
  • 其他基本就是一个大模拟了，建议先做一遍猪国杀练练手（bushi