NJU Static Program Analysis | Assignment-4 Class Hierarchy Analysis & Interprocedural Constant Propagation.
实验信息&食用指南
见本博客A1-A3.
手册的手册不能替代手册, 看不懂的话请回去看手册. —— RicoloveFeng|SPA-Freestyle-Guidance
实验目标
基于Tai-e 框架实现 CHA & Inter Constprop.
真的还有必要在记录里补充这个吗
实验简析
其实没什么好说的, 课程 & ppt & 指南已经讲的比较明确了, 笔者在此补充一些手册写的不明确或是略去的部分.
不过本次实验涉及不少新东西, 烦请耐心阅读相关代码API.
Preparation
从Assignment2中将ConstPropogation.java
copy到本次实验目录对应位置.
需要注意的是, A2中不完全正确的实现可能会影响本次实验的本地测试.
CHABuilder
这部分tt老师贴心的在ppt中给好了算法框架, 对应本次的框架代码复刻即可.
需要注意的是, 只有在完成了该部分后,
Tai-e框架才能正确构建ICFG,
否则使用Assignment分析的结果只会为空.
推荐完成顺序 dispatch -> resolve ->
buildCallGraph
dispatch()
可以选择递归或者循环完成该部分.
dispatch()可能会失败, 此时可以返回null, 但要确保resolve()中可以正确处理这一情况.Additional: 为什么可能会失败?
resolve()中, 假设我们要处理一个Interface或者Abstract类型声明的类方法, 首先我们需要dispatch这个声明类本身, 易见此时应当得到null(接口中的方法和抽象方法无法被实例化)dispatch()得到的JMethod如果是Abstract, 同样需要返回null.Tips: 由于OOP的机制, 当
JMethod是Abstract时, 不需要继续dispatch了. 如果对此感到困惑可以去查阅相关的OOP资料.
resolve()
遍历的方式自选, 笔者采用较好实现的BFS.
尽管课上将
Interface归入了Virtual Invoke, 但按照代码框架, 这部分单独作为一个需要处理的CallKind. 不过处理起来也并非难事, 因为处理方式和VIRTUAL没有实质性区别.需要注意的是, 框架中处理Interface和Class分别有专门的API方法, 具体使用什么API, 可以阅读
ClassHierarachy,CHABuilder中也提供了访问ClassHierarachy的成员private ClassHierarchy hierarchy.STATIC方法的获取在框架中没有专门的API, 但可以使用dispatch()获取, 因此STATIC和SPRECIAL也可以一起处理.
buildCallGraph()
实现和ppt中的算法没有区别.
判断是否可达在框架中集成到了
Class CallGraph的addReachableMethod()方法中了, 可以阅读API注释获取更详细的信息.得到
callSite,callKind的方法也可以通过Class CallGraph获取.(我看看是谁不想去读API注释)
InterSovler
由于框架代码在InterSovler这一部分进行了较大幅度的重构,
因此笔者推荐先完成该部分使得对InterConstantPropopagation有一个自顶向下的认识.
同手册所说, 该部分比起A2的worklistSovler没有太大的区别,
跟着手册做即可.
注意:
该部分实例化的private final InterDataflowAnalysis<Node, Fact> analysis继承自Class AbstractInterDataflowAnalysis,
该部分的源码阅读是必不可少的.(这里不读在完成InterConstantPropopagation的时候也要读)
initialize()
- 除去icfg的入口方法使用
BoundaryInit外, 其余节点均使用NormalInit. 可以通过icfg.entryMethods()方法获取入口方法.
Tips: 需要注意的是
icfg.entryMethods()返回的是Stream类型, 遍历该类型可以使用forEach. 更多关于forEach的信息可以查阅java的文档.
1 | icfg.entryMethods().forEach(method -> { |
Confusion: 笔者在此比较困惑为何可能会出现多个入口, 虽然在网络上查询得知java中可能不止一个
main()方法, 但不知如何在tai-e框架中复现, 以及本次实验中的"多个入口"是否对应该特性.
dosolve()
与A2相比,
只需要修改处理pred Node部分为pred Edge,
可以通过getInEdgesOf()方法获得pred Edge信息,
与analysis.transferNode()对应,
可通过analysis.transferEdge()来处理pred Edge.
InterConstantPropopagation
部分API在框架中已经给出了实现, 在该部分只需要实现6个API即可.
善用A2中完成部分进行本次实验, 过程间常量传播并不影响计算常量的逻辑.
transferCallNode() & transferNonCallNode()
含义同方法名,
如果这个Node(即Stmt)是Invoke,
就称该Node为CallNode,
否则为NonCallNode.
- 需要注意的是,
过程间处理的大部分操作都在
Edge上而非Node上, 因此我们在transferCallNode()中并不会进行 add/kill def 的操作. 这一点与指南上的图片逻辑相同.
如图片所示,
Node 2在经过transferCallNode()后并没有把b添加进outFact.尽管我们可以在这里处理,
但这样有可能会让你过不去oj, 但这样会造成逻辑上的混乱, 所有的interprocedural 操作都在Edge上进行在逻辑上是一致的. 接下来对四种transferEdge的处理中会解释这一点.
- 所以对于非call Node,
可以直接使用过程内分析的
transferNode()方法, 对于call Node,transferCallNode()只需要把inFact赋值给outFact即可.
transfer**Edge
在完成该部分前, 要先知道该部分会在什么地方使用,
通过阅读Class AbstractInterDataflowAnalysis的源码API,
可以发现四种transfer**Edge
统一为了一个方法transferEdge().(如果阅读的足够仔细,
会发现两个NodeTransfer的方法也被统一为了transferNode())
注意: 如手册所言, 由于java的引用机制,
不应当对第二个参数CPFact out做任何修改.
返回值也不应是第二个参数本身,
需要深拷贝一个out或者new CPFact().
transferNormalEdge()
对于普通节点, 不需要对OutFact中的内容做修改,
直接传给Edge的target即可.
对应上文图片中的黑色实线.
transferCallToReturnEdge()
在这里要处理def kill工作, 根据框架代码,
这里的Stmt一定是Invoke,
请阅读源码API获取使用信息.
Invoke继承自DefinitionStmt, 如何获取def在之前的实验中已有涉及.
对应上文图片中的黑色虚线.
transferCallEdge()
负责传参中的Var转换.
对于
Invoke invoke, 可以通过invoke.getInvokeExp().getArgs()获取传入实参的信息.对于
JMethod callee, 可以通过callee.getIR().getParams()获取调用方法的形参信息.在tai-e框架中, 保证上述形参与实参列表顺序是一一对应的. 可以根据这一特性维护传参的转换过程.
对应上文图片中的蓝色虚线.
transferReturnEdge()
负责将调用方法的返回值传回callSite.
Class ReturnEdge的getReturnVars()的API说明讲明了为什么可能有多个返回值, 需要注意的是, 如果有多个返回值, 需要使用cp.meetValue().
对应上文图片中的红色虚线.
总结
过程间常量传播的思想还是比较巧妙的, 值得细心品味.