PIP: Making Andersen’s Points-to Analysis Sound and Practical for Incomplete C Programs
This program is tentative and subject to change.
Compiling files individually lends itself well to parallelization, but forces the compiler to operate on incomplete programs. State-of-the-art points-to analyses guarantee sound solutions only for complete programs, requiring summary functions to describe any missing program parts. Summary functions are rarely available in production compilers, however, where soundness and efficiency are non-negotiable. This paper presents an Andersen-style points-to analysis that efficiently produces sound solutions for incomplete C programs. The analysis accomplishes soundness by tracking memory locations and pointers that are accessible from external modules, and efficiency by performing this tracking implicitly in the constraint graph. We show that implicit pointee tracking makes the constraint solver 15$\times$ faster than any combination of five different state-of-the-art techniques using explicit pointee tracking. We also present the Prefer Implicit Pointees (PIP) technique that further reduces the use of explicit pointees. PIP gives an additional speedup of 1.9$\times$, compared to the fastest solver configuration not benefiting from PIP. The precision of the analysis is evaluated in terms of an alias-analysis client, where it reduces the number of \texttt{MayAlias}-responses by 40% compared to LLVM's BasicAA pass alone. Finally, we show that the analysis is scalable in terms of memory, making it suitable for optimizing compilers in practice.
This program is tentative and subject to change.
Tue 3 FebDisplayed time zone: Hobart change
14:10 - 15:30 | |||
14:10 20mTalk | PIP: Making Andersen’s Points-to Analysis Sound and Practical for Incomplete C Programs Main Conference Håvard Rognebakke Krogstie NTNU, Helge Bahmann Independent Researcher, Magnus Själander Norwegian University of Science and Technology (NTNU), Nico Reissmann Independent Researcher Pre-print Media Attached | ||
14:30 20mTalk | Thinking Fast and Correct: Automated Rewriting of Numerical Code through Compiler Augmentation Main Conference Siyuan Brant Qian University of Illinois at Urbana-Champaign, Vimarsh Sathia University of Illinois Urbana Champaign, Ivan Ivanov Institute of Science Tokyo, Jan Hueckelheim Argonne National Laboratory, Paul Hovland Argonne National Laboratory, William S. Moses University of Illinois Urbana-Champaign Pre-print Media Attached | ||
14:50 20mTalk | PolyUFC: Polyhedral Compilation Meets Roofline Analysis for Uncore Frequency Capping Main Conference Nilesh Rajendra Shah Indian Institute of Technology Hyderabad, India, M V V S Manoj Kumar IIT Hyderabad, Dhairya Baxi IIT Hyderabad, Ramakrishna Upadrasta IIT Hyderabad Pre-print | ||
15:10 20mTalk | Accelerating App Recompilation across Android System Updates by Code Reusing Main Conference Hongtao Wu Wuhan University, Yu Chen Wuhan University, Mengfei Xie Wuhan University, Futeng Yang Guangdong OPPO Mobile Telecommunications, Jun Yan Guangdong OPPO Mobile Telecommunications, Jiang Ma OPPO Electronics Corp., Jianming Fu Wuhan University, Jason Xue MBZUAI, Qingan Li Wuhan University, China Pre-print | ||