Liveness-Based Pointer Analysis
| Autor: | Prashant Singh Rawat, Alan Mycroft, Uday P. Khedker |
|---|---|
| Rok vydání: | 2012 |
| Předmět: | |
| Zdroj: | Static Analysis ISBN: 9783642331244 SAS |
| DOI: | 10.1007/978-3-642-33125-1_19 |
| Popis: | Precise flow- and context-sensitive pointer analysis (FCPA) is generally considered prohibitively expensive for large programs; most tools relax one or both of the requirements for scalability. We argue that precise FCPA has been over-harshly judged--the vast majority of points-to pairs calculated by existing algorithms are never used by any client analysis or transformation because they involve dead variables. We therefore formulate a FCPA in terms of a joint points-to and liveness analysis which we call L-FCPA. We implemented a naive L-FCPA in GCC-4.6.0 using linked lists. Evaluation on SPEC2006 showed significant increase in the precision of points-to pairs compared to GCC's analysis. Interestingly, our naive implementation turned out to be faster than GCC's analysis for all programs under 30kLoC. Further, L-FCPA showed that fewer than 4% of basic blocks had more than 8 points-to pairs. We conclude that the usable points-to information and the required context information is small and sparse and argue that approximations (e.g. weakening flow or context sensitivity) are not only undesirable but also unnecessary for performance. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|