**Instructor**: Amey Karkare (, )

This course aims to teach topics in program analysis and compiler optimizations.

- Code of Ethics
- Announcements
- Course Outline
- Evaluation Scheme
- Topics covered and handouts
- Assignments
- Course Project
- Supporting Material
- Research Material
- Recommended References

Any report/program/assignment you submit must **clearly distinguish** your contribution from others (webpages, softwares, report, discussions with other students). The penalty for copying in any form will be severe.

Important: All emails' subject line should begin with "**[CS738]**". Email not complying to this rule **will NOT be entertained**.

The slides are not suitable for taking prints as there is a lot of redundancy due to overlays. Use handouts if you really need a print.

The videos for the course are available through the Canvas page.

0. First Course Handout | [FCH] | ||

1. Introduction | [handouts] | [slides] | |

2. Overview of Optimizations | [handouts] | [slides] | |

3. Data Flow Analysis | [handouts] | [slides] | |

4. Data Flow Analysis (contd...) | [handouts] | [slides] | |

5. Data Flow Analysis Foundations | [handouts] | [slides] | |

6. DFA Foundations (contd ...) | [handouts] | [slides] | |

7. Flow Graph Theory | [handouts] | [slides] | |

8. Constant Propagation | [handouts] | [slides] | |

9. SSA | [handouts] | [slides] | [paper] |

10. SSA (contd ...) | [handouts] | [slides] | |

11. Conditional Constant Propagation | [handouts] | [slides] | [paper] |

12. SSA PRE | [handouts] | [slides] | [paper] |

13. SSA PRE Example | [handouts] | [slides] | |

14. Interprocedural Analysis | [handouts] | [slides] | |

15. Interprocedural Analysis: Functional Approach | [handouts] | [slides] | |

16. Interprocedural Analysis: Call-strings Approach | [handouts] | [slides] | By Prof Uday |

17. Pointer Analysis | [handouts] | [slides] | [Anderson's][Steensgaard's] [Yanniss's Tutorial] |

18. Types and Program Analysis | [handouts] | [slides] | |

19. Untyped Lambda Calculus | [handouts] | [slides] | |

20. Typed Arithmetic Expressions | [handouts] | [slides] | |

21. Simply Typed Lambda Calculus | [handouts] | [slides] | |

22. Type-based Points-to Analysis | [handouts] | [slides] | [Steensgaard's] [Manuvir's] |

There will be short assignments to give you a chance to apply the lecture material. Assignments will have some written and some programming tasks.

**Project Description**will come Here in about three weeks after the classes start.

The course will mainly cover topics from the following list (not necessarily in the same order). Not all topics listed below will be covered, and depending on class feedback, new topics may be added.

- Introduction, compiler architecture, intermediate representations
- Control flow analysis, control-flow graphs, basic blocks
- Dataflow analysis
- SSA form
- Classical optimizations (constant folding, CSE, PRE)
- Pointer and alias analysis
- Interprocedural analysis
- Advanced Topics:
- Smart Contract Vulnerability Analysis
- Garbage Collection
- Program Synthesis
- Program Testing and Debugging
- Types and Programming

**Credit**

Class Participation and Quizzes | 05% |

Assignments | 10% |

Mid semester exam | 20% |

End semester exam | 30% |

Course Project | 35% |

(Breakup: Proposal: 5% Report and Presentation: 10% Implementation: 20%) |

- Uday P. Khedker, Amitabha Sanyal, and Bageshri Karkare,
**Data Flow Analysis: Theory and Practice**, CRC Press, USA (2009).- Indian Edition is available, CRC Press, 2013.

- Appel, A.,
**Modern Compiler Implementation in Java**(or ML, or C), Cambridge University Press, 2002. - Cooper, K., Torczon, L.,
**Engineering a Compiler**, Morgan Kaufmann, 2004 - Muchnick, S.,
**Advanced Compiler Design and Implementation**, Morgan Kaufmann, 1997. - Aho, A., Lam, M., Sethi, R., Ullman, J.,
**Compilers: Principles, Techniques, & Tools**, Addison Wesley, 2007. - Y. N. Srikant, Priti Shankar,
**The Compiler Design Handbook: Optimizations and Machine Code Generation**, CRC Press, 2008 - Randy Allen, Ken Kennedy,
**Optimizing Compilers for Modern Architectures: A Dependence-based Approach**, Morgan Kaufmann, 2001