The Story of Blind Men and the Elephant: Understanding Context Sensitivity
Details
Title: The Story of Blind Men and the Elephant: Understanding Context Sensitivity
Abstract:
Interprocedural program analysis extends the scope of analysis across procedure boundaries to capture the effect of callee procedures on the callers and vice-versa. Context-sensitive interprocedural analysis uses a context as an abstraction that distinguishes between the invocations of a procedure that may correspond to different results of analysis. These methods increase the precision of interprocedural analysis by achieving the effect of call inlining. These methods have been defined using different formalisms and hence appear as algorithms that are very different from each other. Some methods define context, whereas some do not. These methods place different kinds of restrictions on the data flow frameworks supported by them and seem to compute different kinds of values. As a consequence, it is difficult to compare the ideas behind these methods in spite of the fact that they solve essentially the same problem. We believe that these incomparable views are similar to blind men views of an elephant called context-sensitivity.
We bring out this whole-elephant-view of context sensitivity in program analysis by proposing a unified model of context sensitivity which captures the essence of context-sensitivity. Our facilitates insightful comparisons between different methods, and facilitates cross fertilization of ideas and suggest interesting improvements in the known methods.
This study was motivated by a frustrating reality that most production compilers stay away from context-sensitive analysis because the known methods do not scale to large programs. If time permits, I would like to end the talk by outlining our efforts of changing this reality.
This is a joint work with Swati Jaiswal (VNIT) and Alan Mycroft (Cambridge University).
Speaker Bio:
Dr. Uday Khedker is a Professor in the Department of Computer Science and Engineering at IIT Bombay. His areas of interest include Precise Pointer Analysis, Precise and Scalable Interprocedural Analysis, and Context-Sensitive SSA (Co-SSA). He spearheaded the GCC work at IIT Bombay through the GCC Resource Center (http://www.cse.iitb.ac.in/grc). He has published papers in leading journals and conferences, contributed chapters to the Compiler Design Handbook, and authored a book titled "Data Flow Analysis: Theory and Practice" ([http://www.cse.iitb.ac.in/~uday/dfaBook-web](http://www.cse.iitb.ac.in/~uday/dfaBook-web)), published by CRC Press. He has also worked closely with the industry as a consultant and as a trainer for advanced topics in compilers. Dr. Khedker has advised 10 Ph.D. students, close to 50 B.Tech. and M.Tech. students, and many more interns. He is a recipient of the Prof. S. P. Sukhatme Excellence in Teaching Award (2023), the Excellence in Teaching Award (CSE Dept) (2023), and the IBM Faculty Award (2007).
Website: https://www.cse.iitb.ac.in/~uday/
Google Scholar: https://scholar.google.com/citations?user=mMX9vxkAAAAJ&hl=fr
Youtube: https://www.youtube.com/channel/UCqM55vtIYwe_RyJpOunXpdQ/playlists