opal
opal copied to clipboard
opalj
Add alias analysis
Note: This pull request is based on #178 and should only be merged after that pull request.
This pull request adds two alias analyses for the alias properties added in #171: One intraprocedural alias analysis and one based on the existing points-to analysis.
I think I'm mostly happy with this PR now and will approve and merge it soon. Just have a final look into the post-dominator tree issue please. It seems very weird to do dominator and post dominator checks using different underlying representations. It would be much nicer to also use a TAC-based post-dominator tree.
I think your original strategy of borrowing from CFG's dominatorTree method should be the way to go, we'd just need to figure out why it failed in your first attempt. As far as I can tell, the foreachSuccessor method in CFG should never invoke the given function with -1, because the call in line 455 is guarded by the check in 453 and the one in 444 uses the next pc, which is the given pc + 1. It should probably be easy to debug where that -1 came from.
On another note, instead of caching the trees yourself, it might be worthwile to consider converting the dominatorTree (and postDominatorTree, once implemented) method on CFG to a lazy val. That way, no complex ad-hoc caching logic is needed and other analyses, etc., also using the dominator/post-dominator trees would also not need to recompute it.
I have managed to fix my initial approach of adding a postDominatorTree method in the cfg class. The problem was that I directly used the id's of the special exit nodes, which are -1 and -2. I am now using the ids of their predecessors, which seems to work fine: val exitNodes = normalReturnNode.predecessors.map(_.nodeId) ++ abnormalReturnNode.predecessors.map(_.nodeId).
I have also converted the dominatorTree and postDominatorTree methods to lazy val as suggested.
However, the same test which made us use a postDominatorTree is still failing. The problem is, that an exception can be thrown inside the loop which creates an edge to the abnormal return node. This again causes the immediate post dominator of the loop header to be the unique exit node of the postDom tree instead of the bb after the loop, breaking our "behind-loop" check.
Can you have another look at this? It is good work and I'd like to merge it, but I can't as long as there are still failing tests.
The remaining problem is the handling of abnormal returns inside the loop and I am not sure how to solve it. I would for now change the expected values of the two failing tests to MayAlias. If a more mature loop detection is implemented in the future this could be used here to improve the precision.