|
Computer Science Seminar Date and time: Monday, 26 September, 14:00 Venue: Lecture Hall 4, CMI Precise and Scalable Interprocedural Analysis Pritam Gharat 26-09-22 Abstract Computing precise (fully flow- and context-sensitive) and exhaustive (as against demand-driven) data-flow information is known to be expensive. Top-down approaches require repeated analysis of a procedure for separate contexts. Bottom-up approaches need to construct context-independent procedure summaries that are compact and yet precise. This talk explores two research investigations in this space. In the first work, we have defined precise procedure summaries for bottom up context-sensitive pointer analysis. This is challenging because a procedure summary should model unknown pointees accessed indirectly through pointers that may be defined in the callers. We propose a novel abstraction called the generalized points-to graph (GPG) that is a compact representation of bottom- up procedure summaries in terms of memory updates and control flow between them. The effectiveness of GPGs lies in the fact that they discard as much control flow as possible without losing precision. This is the reason GPGs are very small even for main procedures that contain the effect of the entire program. The main idea behind computing points-to information using a bottom-up approach was to bring the definition of a pointer and its dereferences in the same procedure by inlining procedure summaries at call sites. Our second work takes this idea to its logical conclusion by extending it to all variables thereby defining context-sensitive SSA (aka CoS-SSA) which is fully precise in terms of Read-after-Write (aka RaW) dependences even in the presence of pointers and recursion. Unlike traditional intraprocedural SSA, CoS-SSA constructs SSA variables for scalars that are defined and used directly or indirectly through pointers across different procedures. In the spirit of classical (intraprocedural) SSA bringing flow sensitivity for free, CoS-SSA brings both flow and context sensitivity for free in that any client can perform sparse context-sensitive interprocedural analysis on it without maintaining contexts.
|
