SSA based flow-sensitive points-to analysis via value flow graph reachability using binary decision diagrams
Abstract
In 2011, Oracle Labs Australia Researchers Cristina Cifuentes et al. presented a flow-sensitive points-to analysis algorithm that, as a novelty at this time, reduced the analysis to a graph reachability problem. Performance evaluations conducted indicated that this new reduction can lead to significant runtime improvements over previously established methods. However, it was also found that for some benchmarks the space requirements of the new algorithm can be up to an order of magnitude higher. In this thesis we implemented the algorithm presented by Cifuentes into LLVM and investigated the effect on the algorithms space and time requirements when C++ STL sets are replaced by Binary Decision Diagrams as representations of the points-to sets involved. We found that by using Binary Decision Diagrams, the algorithm experiences a runtime slowdown of 27.3% while the space requirements can be reduced up to 65.6% for large enough benchmarks.