Strictly declarative specification of sophisticated points-to analyses

We present the D framework for points-to analysis of Java programs. D builds on the idea of specifying pointer analysis algorithms declaratively, using Datalog: a logic-based language for defining (recursive) relations. We carry the declarative approach further than past work by describ-ing the full end-to-end analysis in Datalog and optimizing aggressively using a novel technique that takes into account Datalog incremental evaluation. As a result, D achieves several benefits, including full order-of-magnitude improvements in runtime. We compare D with Lhoták and Hendren’s P, which defines the state of the art for context-sensitive analyses. For the exact same logical points-to definitions (and, consequently, identi-cal precision) D is more than 15x faster than P for a 1-call-site sensitive analysis of the DaCapo benchmarks, with lower but still substantial speedups for other important analyses. Additionally, D scales to very precise analyses that are impossible with P and Whaley et al.’s bddbddb, directly addressing open problems in past literature. Finally, our implementation is modular and can be easily configured to analyses with a wide range of characteristics, largely due to its declarativeness. 1