FST TCS 2007 Satellite Workshop
Compiler Techniques and their Applications

IARCS will felicitate Prof. Priti Shankar on the occasion of her 60^th birthday.

Objectives

Techniques used in compiler development have brought together various strands of research in computer science --- theory of computation, efficient algorithms, logic and semantics, computer architecture, numerical methods, optimizations for application specific computation, software engineering and formal methods. This strong theoretical basis has had a very welcome effect in making compiler and language translators among the most reliable (least buggy) forms of software.

There have been several significant developments in compiler techniques in the last decade, as well as deployment of these techniques in applications beyond traditional compilers, e.g., in web-services, etc. New static analysis techniques have been proposed, which make possible more precise analyses, and new architectural paradigms have required fresh approaches to code generation. Even the traditional area of compiler design has posed new Grand Challenges, such as the one proposed by Tony Hoare for developing a formally verified compiler.

Within India, there is a gradually increasing number of researchers working in the area of Programming Languages, and their design and implementation. However, this community needs to grow far more rapidly and to attract much greater participation from interested researchers. The objective of this workshop is to introduce researchers interested in theory and foundational computer science to new techniques and problems in the field.

Schedule

• Heap Reference Analysis by Prof. Uday Khedker
  

  This talk presents some recent advances in data flow anlaysis for discovering properties of heap data. This important because despite significant progress in the theory and practice of program analysis, analysing properties of heap data has not reached the same level of maturity as the analysis of static and stack data. The spatial and temporal structure of stack and static data is well understood while that of heap data seems arbitrary and is unbounded. We devise bounded representations which summarize properties of the heap data. This summarization is based on the structure of the program which manipulates the heap. The resulting summary representations are certain kinds of graphs called access graphs. The boundedness of these representations and the monotonicity of the operations to manipulate them make it possible to compute them through data flow analysis.

  Prof. Uday Khedker is interested in the area of optimising compilers. Current sub-areas of interest include Interprocedural Data Flow Analysis, Heap Reference Analysis, Static Inferencing of Flow Sensitive Polymorphic Types, and Compiler Verification. A recent research thrust involves cleaning up the GNU Compiler Collection (GCC) to simplify its deployment, retargetting, and enhancements. Other goals include increasing its trustworthiness as well as the quality of generated code. Two focussed activities involve

  • (a) incorporating our precise, general, and efficient interprocedural data flow analysis algorithms in GCC, and
  • (b) simplifying machine descriptions by changing the instruction selection mechanism in GCC.

  His group has conducted a workshop on GCC Internals to explain their findings to the GCC community. More details about his current research can be found in the presentation available here.
  Home page of Uday Khedker

• Guarded Dependences and Data Model Recovery by Dr G. Ramalingam
  

  In this talk, I will start off with a motivating application: reverse engineering semantically sound object-oriented data models from programs written in weakly-typed languages. I will introduce a novel form of guarded, transitive, data-dependence. I will present a polynomial-time path-sensitive analysis to compute these dependences. I will then present an algorithm for distilling the set of computed guarded dependences into a data-model for the program.
  (Joint work with Raghavan Komondoor)
  

  Dr G. Ramalingam received his B.Tech. from IIT Madras in 1987, and his Ph.D. from the University of Wisconsin at Madison in 1993. He was a Research Staff Member at IBM T. J. Watson Research Center from 1993 to 2006. He joined Microsoft Research in Bangalore in 2006. His interests are in the area of static program analysis and its applications.
  Home page of G. Ramalingam

• Worst Case Execution Time Estimation in the presence of Data Cache by Prof. Y. N. Srikant
  

  This talk describes techniques to estimate the worst case execution time of executable code on architectures with data caches. The underlying mechanism is Abstract Interpretation, which is used for the dual purposes of tracking address computations and cache behavior. A heuristic is also proposed which generates likely worst case estimates. This can be used in soft real time systems and also for reasoning about the tightness of the safe estimate. The precision of the estimates is user-controlled and can be traded off against analysis time. Executables are analyzed directly, which, apart from enhancing precision, renders the method language independent.
  

  Background assumed: Basic program analysis techniques. Familiarity with abstract interpretation will be useful, but not essential.

  Prof. Y. N. Srikant received his B.E in Electronics from Bangalore University, and M.E and Ph.D in Computer Science from the Computer Science and Automation department at the Indian Institute of Science. His area of interest is compiler design. He is the co-editor of a handbook on advanced compiler design published by CRC Press in 2002 (revised edition to appear in January 2008).
  Home page of Y. N. Srikant

• Compiling for multicore systems by V. Krishna Nandivada

  Multicore systems, with their forceful entry into the market, have shown the inadequacy of the existing compiler techniques. The focus of this talk would be on the multicore systems and their impact on the compiler research/development. We will also spend some time describing our experience in compiling for multicore systems.

  Dr V. Krishna Nandivada obtained his Bachelors from R.E.C Rourkela, Masters from Indian Institute of Science, and PhD from University of California, Los Angeles. He is currently working in the X10 compiler group, at IBM India Research Lab. His interests include program analysis and program optimization.
  Home page of V. Krishna Nandivada

• WYSINWYX: What You See Is Not What You eXecute by Thomas Reps

  What You See Is Not What You eXecute: Computers do not execute source-code programs; they execute machine-code programs that are generated from source code. Not only can the WYSINWYX phenomenon create a mismatch between what a programmer intends and what is actually executed by the processor, it can cause analyses that are performed on source code -- which is the approach followed by most security-analysis tools -- to fail to detect bugs and security vulnerabilities.

  To address the WYSINWYX problem, we have developed algorithms to recover information from stripped executables about the memory-access operations that the program performs. These algorithms are used in the CodeSurfer/x86 tool to construct intermediate representations that are used for browsing, inspecting, and analyzing stripped x86 executables. Recently, this infrastructure has been used to create a tool for looking for bugs in stripped device-driver executables.

  Joint work with G. Balakrishnan (UW->NEC), J. Lim (UW), and T. Teitelbaum (Cornell and GrammaTech, Inc.).
  Home page of Thomas Reps

This workshop is made possible due to the generous sponsorship of Microsoft Research India.

Organizers

• Sanjiva Prasad, IIT Delhi

We'd like to acknowledge the help given by Kamal Lodaya with the organization of this workshop.