CS6004: Code Optimization for Object-Oriented Languages

Offering: Spring 2024

About the course

Object-oriented languages have become a popular medium for designing large real-world systems. In spite of the several abstraction layers, programs written in modern OO languages (such as Java and C#) achieve comparable (and sometimes, higher) performance relative to lower level non-OO languages, on both single and multi-core systems. This has become possible with the adoption of several novel optimizations, introduced over the last couple of decades. This course aims to uncover many powerful optimizations implemented in OO runtimes, with focus on further research in this direction.

Contents:

• Fundamentals. OO abstraction; classes and interfaces; inheritance and polymorphism. Memory organization: Stack and heap; object allocation and storage: fields, functions and methods. Object headers and ordinary object pointers (oops). Dispatch using virtual tables.

• Heap analysis. Object abstractions: allocation sites, access paths, modeling nulls and static fields. Points-to information; field- and flow-sensitivity. Intra- and inter-procedural analysis. Alias analysis and variations. Heap cloning.

• Optimizations involving allocation and field-access. Escape analysis and stack allocation. Scalar replacement. Field privatization. Value types and object inlining. Object colocation. Path-sensitive optimizations (partial escape analysis). Garbage collection (liveness for objects). Distributed object access.

• Optimizations involving method dispatch. Class hierarchy analysis, rapid type analysis, variable type analysis, context-insensitive pointer analysis. Object- and type-sensitivity based context-sensitive analysis.

• Speculative optimizations. Introduction to speculation and deoptimization. Guards and framestate nodes; their interaction and placement. Speculative type resolution. Speculative method inlining and polymorphic inline caching (PIC). Code versioning.

• Recent developments. Performance considerations: various metrics; balancing efficiency and precision. Static+dynamic analysis. Dynamic features: reflection, callbacks, hot-code replacement, dynamic classloading. Reducing deoptimization overheads.

References:

1. Yannis Smaragdakis and George Balatsouras. Pointer Analysis. Foundations and Trends in Programming Languages Vol. 2 No. 1. 2015.
2. Andrew W. Appel. Modern Compiler Implementation in Java. Second Edition. Cambridge University Press. 2004.
3. Y. N. Srikant and P. Shankar (Ed.) The Compiler Design Handbook: Optimizations and Machine Code Generation. CRC Press. 2002.
4. Amer Diwan, Kathryn S. McKinley, J. Moss and B. J. Eliot. Using Types to Analyze and Optimize Object-Oriented Programs. Computer Science Department Faculty Publication Series, University of Massachusetts – Amherst. 2001.
5. Joshua Bloch. Effective Java. Third Edition. Addison-Wesley Professional Publication. 2017.

Logistics

• Credits: 3-0-0-6.

• Prerequisites: Exposure to a UG course on compilers. Or consent of the instructor.

• Audience: Elective for UG and PG students.

• Instructor: Manas Thakur.

• TAs: Aditya Anand (23d0381), Kushagra Shandilya (21q050010), G. Siva Prasad Reddy (23m0747).

• Slot: 6 (Wed and Fri, 11:05am-12:30pm).

• Classroom: LC 301.

• Office hour: Thu, 11:30am-12:30pm.

Evaluation

1. Programming (assignments, project): 45
2. Mid-sem exam: 20
3. End-sem exam: 25
4. Topic scribes: 6
5. Course participation: 4