Optimizing Compilers for Modern Architectures Pointer Analysis
Point-to analysis, Symbolic Range Analysis, and ATLAS automatic JAVA library points-to analysis are discussed in the context of optimizing compilers for modern architectures. These analyses cover the handling of pointers, pointer arithmetic, thread safety, heap allocations, and more to enhance compiler performance and efficiency.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Pointer analysis John Rollinson & Kaiyuan Li 15745 - Optimizing Compilers for Modern Architectures, Spring 2019
Point-to analysis when... Pointer arithmetic Not helpful (or no access to) source code Multiple threads
Symbolic Range Analysis Global Analysis: Local Analysis: Heap allocations treated as unique memory locations Pointers tracked as a set of memory locations and corresponding range offsets Pointers do not alias when there is no range overlap at each possible memory location Solves path-sensitive false positives for global analysis (pointers inside a loop) Models each as a unique memory location and performs local overlap analysis for that memory location Paisante, Vitor, et al. "Symbolic range analysis of pointers." 2016 IEEE/ACM International Symposium on Code Generation and Optimization (CGO). IEEE, 2016.
ATLAS: automatic JAVA library points-to analysis Dynamic analysis, flow-insensitive, context-sensitive, iterative Libraries are blackboxes Minimize false positives (precise but not sound) For local optimization, but not for transformation Based on Andersen s algorithm Heap effects of functions (fragments) 2 steps: guess (precise) -> check (accurate) Bastani, Osbert, et al. "Active learning of points-to specifications." Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 2018.
ATLAS: automatic JAVA library points-to analysis Guess (specification search space & testing specifications): Problem: guess too many Solution: path specification (context sensitive) Using unit tests to guarantee precise S box = ob this set this get r get
ATLAS: automatic JAVA library points-to analysis Check (specification inference): Problem: infinite possibilities Solution: active language learning algorithm via unit tests Finally convert path specifications to code fragment S box = ob this set ( this clone r clone)* this get r get
Sparse Flow-Sensitive Pointer Analysis for Multithreaded Programs (FSAM) Whole program points-to analysis for generic Pthread-based concurrent C programs Multi-stage analysis: Run Andersen s analysis (fast, but imprecise) Generate sparse def-use model: Use sequential model to approximate def-use chains for each memory location Identify may-happen-in-parallel (MHP) relations between threads Remove MHP relations prevented by locks Add parallel execution def-use relationships into sparse graph Use existing sparse def-use analysis on the new def-use model 1-2 orders of magnitude faster than non-sparse analysis Sui, Yulei, Peng Di, and Jingling Xue. "Sparse flow-sensitive pointer analysis for multithreaded programs." Proceedings of the 2016 International Symposium on Code Generation and Optimization. ACM, 2016.
FSAM: Example t0 t1 t2 t0 t1 t2 Flow-Sensitive Pointer Analysis main: S1: *p = fork(t1, foo) S2: = *p join(t1) S3: *p = fork(t2, foo) lock(l1) S4: *p = ... unlock(l1) join(t2) S5: *p = S6: = *p Andersen s Pointer Analysis S1 S1 S7 S7 S2 S2 S8 S8 S3 S3 S7 S7 S4 S4 S8 S8 S5 S5 Foo: lock(l2) S7: *q = S8: *q = ... unlock(l2) S6 S6 Sequential approximation Fork/join adjustments May happen in parallel Ignored because of lock For variable in may alias set for both q & p
