**Instructor**: Amey Karkare (, )**TAs**: Binapani Beria (), Sushmita Nikose ()**Timings**: Tue,Fri: 2:00PM - 3:25PM

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 either to the instructor or the TAs should begin with subject line "**[CS618]**" -- without any spaces in the course code (and without quotes). Email not complying to this rule **will NOT be entertained**.

- Project Presentation Schedule

- Slides for lecture #20 uploaded below (on 18th October 2016).
- Slides for lecture #19 uploaded below (on 18th October 2016).
- Slides for lecture #18 uploaded below (on 15th October 2016).
- Slides for lecture #17 uploaded below (on 14th October 2016).
- Slides for lecture #15,16 uploaded below (on 07th October 2016).
- Reading material for Call-strings approach for Interprocedural Analysis added below (on 27th September 2016).
- Project Proposals are due soon. Submit via Moodle.
- Slides for lecture #13,14 uploaded below (on 20th September 2016).
- Slides for lecture #12 uploaded below (on 15th September 2016).
- Assignment #4 (Part A and B) released on 30th August 2016. Submit via Moodle.
- Slides for lecture #11 uploaded below (on 30th August 2016).
**Evaluation Scheme Updated**below (on 26th August 2016).- Slides for lecture #9,#10 uploaded below (on 26th August 2016).
- Assignment #3 released on 19th August 2016. Submit via Moodle.
- Slides for lecture #8 uploaded below (on 19th August 2016).
- Slides for lecture #6, #7 uploaded below (on 16th August 2016).
- Quiz #1 in class on 12th August 2016
- Slides for lecture #5 uploaded below (on 08th August 2016).
- Assignment #2 released on 05th August 2016. Submit via Moodle.
- Slides for lecture #4 uploaded below (on 05th August 2016).
- Slides for lecture #3 uploaded below (on 29th July 2016).
- Slides for lecture #2 uploaded below (on 23rd July 2016).
- Slides for introductory lecture (#1) uploaded below (on 20th July 2016).
- Fill this google form if you plan to credit/audit this course.
- Make sure you are subscribed to Moodle Page for CS618 if you plan to credit/audit this course.

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.

# | Description | Handout | Slides | References |
---|---|---|---|---|

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. | Interprocedural analysis | [handouts] | [slides] | |

13. | ... (Functional Approach) | [handouts] | [slides] | |

--. | ... (Call-strings Approach) | [handouts] | [slides] | By Prof Uday |

14. | Liveness based Garbage Collection | [handouts] | [slides] | [paper1][paper2] |

--. | ... (continued) | [Mohri-Nederhoff Transformation] | ||

15. | Pointer Analysis | [handouts] | [slides] | [Anderson's][Steensgaard's] |

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

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

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

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

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

--: **Reading Assignment**

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

- Assignment 4B : Deadline 01st October 2016
- Assignment 4A : Deadline 20th September 2016 Solutions
- Assignment 3 : Deadline 30th August 2016 Solutions
- Assignment 2 : Deadline 19th August 2016 Solutions
- Assignment 1 : Deadline 30th July 2016

Thanks to TAs(Binapani Beria, Sushmita Nikose ) for the solutions to the assignments. ******

**Project Proposal**: Deadline 06th October 2016

The course project gives you a chance to explore a specific area of compiler implementation in more depth. You will be required to **implement** some compiler feature, and perform an **experimental evaluation** of your implementation. You may do your implementation within any freely-available compiler infrastructure (e.g. LLVM, gcc, Soot, etc.)

You will report on your project in a paper in the style of a research paper (approx. 10 pages), and give a presentation/demo of your project to the class. LaTeX and MS Word templates for the paper format are available from SIGPLAN.

- Project can be done individually or in a group of two.

Important: Use of git version control system on **bitbucket** is **required** for programming assignments and project.

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:
- Garbage Collection
- Program Synthesis
- Program Testing and Debugging
- Types and Programming

**Credit**

Assignments | 15% |

Quizzes | 10% |

Mid semester exam | 15% |

End semester exam | 25% |

Course Project | 35% |

(Proposal: 5%, Report: 10%, Implementation: 15%, Presentation: 5%) |

**Audit**

- Assignments |

- Mid semester exam |

- Quizzes |

- Paper Critique and Presentation |

Must get **satisfactory marks** in midsem/quizzes. Must be present for at least **half** of the total number of quizzes.

- cscope and ctags: Code browing utilities
- Eclipse: A Java based Integrated Development Environment
- LaTeX: A document preparation system

- Journals
- International Journal of Parallel Programming
- Journal of the ACM
- Communications of the ACM
- ACM Transactions on Programming Languages
- IEEE Software
- IEEE Computer
- IEEE Transactions on Computers
- IEEE Transactions on Parallel and Distributed Systems
- IEEE Transactions on Software Engineering
- IBM Journal of Research and Development
- IBM Systems Journal
- SIAM Jounal of Computing
- SIGPLAN Notices
- ACTA INFORMATICA

- Conference Proceedings
- International Conferences on Parallel Processing (ICPP)
- Proceedings of International Conf on Software Engineering (ICSE)
- Lecture Notes in Computer Science series.
- Proceedings of SIGPLAN conference on Programming Language Design and Implementation (PLDI)
- ACM Transactions on Programming Languages and Systemes (TOPLAS)
- ACM Symposium on Principles of Programming Languages (POPL)
- Proceedings SIGPLAN Simposium on Compiler Construction (CC)
- Annual International Symposium on Computer Architecture (ISCA)
- Proc. International Conference on Architectural Support for Programming Languages and Operating Systems (IEEE) (ASPLOS)
- International Parallel Processing Symposium, IEEE Computer Society.
- International Static Analysis Symposium (SAS)
- and many more ...

- 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

Last Modified at : Wed Nov 16 10:49:57 IST 2016