Compilers
198:415, Spring 2022

Announcements

• Homework 6 deadline extension: Friday, Apri 29
• Project 3 is now available; deadline: Wednesday, May 4,
• Project 2 new deadline: Wednesday, April 20, 11:59pm. Submission instructions will be posted on canvas
• For information and questions related to COVID-19, please visit https://coronavirus.rutgers.edu .
• In order to enter a Rutgers Campus building, please use My Campus Pass to register. This system is meant for contact tracing.
  
  Please see a short introductory video describing the class (less than 3 minutes).
  

Description

Introduction to compiler construction. Course contents include the following: Formal translation of programming languages, program syntax and semantics. Finite state recognizers and regular grammars. Context-free parsing techniques such as LL(k) and LR(k). Attribute grammars, syntax-directed translation schema, type checking, register allocation, instruction selection, code generation, data flow analysis and code improvement transformations (code optimizations), parallelism, dependence analysis, quantum computing.

Staff

• Ulrich (Uli) Kremer (uli@cs.rutgers.edu)
  Office hours: Tuesday, 3:00-4:00pm (Webex link)
  
  
• Section 01: Jonathan Garcia-Mallen (jag619@cs.rutgers.edu)
  Office hours: Thursday, 3:00-4:00pm ( Zoom link)
  
  
• TA Section 02: Jonathan Garcia-Mallen (jag619@cs.rutgers.edu)
  Office hours: Thursday, 3:00-4:00pm ( Zoom link)
  

Prerequisites, Lectures and Recitations

• Section 01 (07676): Wednesday 5:40pm - 6:35pm, SEC 208 Busch Campus
  
• Section 02 (07677): Wednesday 7:30pm - 8:25pm, SEC 117 Busch Campus
  

Textbooks

• required (EAC): K. Cooper and L. Torczon: Engineering a Compiler (2nd edition)
  Morgan-Kaufmann Publishers, 2012, ISBN ISBN-13: 978-0120884780, ISBN-10: 012088478X
  This is the second edition. This text is available online for free (click here) .
  
  
• recommended (ALSU): Aho, Lam, Sethi and Ullman: Compilers: Principles, Techniques, and Tools (Dragon Book, Second Edition)
  Addison-Wesley, 2007, ISBN 0-321-48681-1
  This is the second edition. The first edition of the book can also be used.

Tentative Syllabus

Overview (EAC §1)
Instruction scheduling (EAC §12)
Local register allocation (EAC §13)
Scanning (EAC §2)
Parsing (EAC §3)
Context sensitive analysis (EAC §4)
Static and dynamic representations in compiled code (EAC §6 & §7)
Introduction to optimization (EAC §8)
Code selection (EAC §11)
Compilation strategies for parallel architectures
Compilation strategies for non-traditional computing models

There will be three programming projects and eight homework assignments.

Academic Integrity

This course requires that every student adheres to the Academic Integrity Policy. DO NOT CHEAT ! If you have any questions whether a particular activity is considered cheating, talk to the instructor. You have to make sure that all your project files are read protected. If you don't know how to do this in Linux, ask your TA. Leaving a project file unprotected and thereby visible to your fellow students is considered cheating.

If you need an extension to a project or homework, let the instructor know as early as possible.

Read/post questions, submit homeworks, track your grades

Please post questions regarding homeworks and projects using Rutgers's Piazza system . DO NOT send homework or project questions directly to a TA or me. THANKS!
You should read the canvas/piazza 415 site at least every other day!

We use Canvas to submit homeworks and publish your grades.

MIDTERM and Quizzes (tentative)

There will be two midterms. First midterm on Wednesday, February 23, in class.

FINAL EXAM

Tuesday, May 10, 1:00pm - 2:00pm, location: TBD

Lecture Notes

• January 19, 2022 -- Lecture 1
  Course overview, what are compilers, why studying compiler design, front end, back end, middle end, optimizations, register allocation, instruction scheduling
  Reading: EAC Chapter 1
  Online lecture at webex link .
  
  
• January 24, 2022 -- Lecture 2
  Backend, instruction scheduling, ILOC, aliasing, code shape, register-register vs. memory-memory model
  Reading: EAC Chapter 12.1 - 12.3; Appendix A (ILOC)
  Online lecture at webex link .
  
  
• January 26, 2022 -- Lecture 3
  Dependencies, dependence/precedence graph, longest latency-weighted path (critical path), forward list scheduling
  Reading: EAC Chapter 12.1 - 12.3; Appendix A (ILOC)
  Online lecture at webex link .
  Recitation slides.
  
  
• January 31, 2022 -- Lecture 4
  Forward list scheduling example, different scheduling heuristics
  Reading: EAC Chapter 12.1 - 12.3; Appendix A (ILOC)
  In-person lecture SEC-118, Busch Campus
  
  
• February 2, 2022 -- Lecture 5
  Register allocation, top-down allocation, feasible registers
  Reading: EAC Chapter 13.1 - 13.3; Appendix A (ILOC)
  In-person lecture SEC-118, Busch Campus
  
  
• February 7, 2022 -- Lecture 6
  Live ranges, MAXLIVE, top-down allocation example
  Reading: EAC Chapter 13.1 - 13.3; Appendix A (ILOC)
  In-person lecture SEC-118, Busch Campus
  
  
• February 9, 2022 -- Lecture 7
  Top-down allocation example, spill code generation, bottom-up allocation
  Reading: EAC Chapter 13.1 - 13.3; Appendix A (ILOC)
  In-person lecture SEC-118, Busch Campus
  
  
• February 14, 2022 -- Lecture 8
  More bottom-up allocation, introduction to lexical analysis
  Reading: EAC Chapter 13.1 - 13.3; Appendix A (ILOC); EAC Chapter 2.1 - 2.3
  In-person lecture SEC-118, Busch Campus
  
  
• February 16, 2022 -- Lecture 9
  Lexical analysis, regular expressions, DFA and NFA
  Reading: EAC Chapter 2.1 - 2.3
  In-person lecture SEC-118, Busch Campus
  
  
• February 21, 2022 -- Lecture 10
  Automatic translation of regular expressions to minimal DFAs: epsilon-NFA, Thompson construction, simulating NFA with a DFA
  Reading: EAC Chapter 2.1 - 2.3
  In-person lecture SEC-118, Busch Campus
  
  
• February 23, 2022 -- Midterm-1 (60 minutes)
  In-person SEC-118, Busch Campus
  
  
• February 28, 2022 -- Lecture 11
  Automatic translation of regular expressions to minimal DFAs: DFA minimization
  Reading: EAC Chapter 2.1 - 2.3
  In-person lecture SEC-118, Busch Campus
  
  
• March 2, 2022 -- Lecture 12
  Syntax analysis, CFG, derivations, ambiguity, resolving ambiguity, high-level comparison top-down and bottom-up strategies
  Reading: EAC Chapter 3.1 - 3.2
  In-person lecture SEC-118, Busch Campus
  
  
• March 7, 2022 -- Lecture 13
  Top-down parsing, left-recursion removal, FIRST sets, LL(1) grammars, FOLLOW sets
  Reading: EAC Chapter 3.1 - 3.3
  In-person lecture SEC-118, Busch Campus
  
  
• March 9, 2022 -- Lecture 14
  LL(1) grammar example, recursive descent parsing, left factoring, concluding remarks LL parsing
  Reading: EAC Chapter 3.3
  In-person lecture SEC-118, Busch Campus
  
  
• March 12 - March 20, 2022 -- Spring Recess
  
  
• March 21, 2022 -- Lecture 15
  Introduction to bottom-up parsing, bottom-up parsing example, handle, shift-reduce parsing, skeleton LR(1) parsing algorithm
  Reading: EAC Chapter 3.4
  In-person lecture SEC-118, Busch Campus
  
  
• March 23, 2022 -- Lecture 16
  LR(1) parsing, LR(1) items, LR(1) canonical collection
  Reading: EAC Chapter 3.4
  In-person lecture SEC-118, Busch Campus
  
  
• March 28, 2022 -- Lecture 17
  LR error recovery; lex and yacc; context-sentitive analysis, attribute grammars, inherited and synthesized attributes, syntax-directed translation
  Reading: EAC Chapter 3.4, 4
  In-person lecture SEC-118, Busch Campus
  
  
• March 30, 2022 -- Lecture 18
  Syntax-directed translation, yacc (bison), project 2
  Reading: EAC Chapter 4
  In-person lecture SEC-118, Busch Campus
  
  
• April 4, 2022 -- Lecture 19
  Type systems, type expressions, type variables, type names, type inference rules, symbol table implementations
  Reading: EAC Chapter 4
  In-person lecture SEC-118, Busch Campus
  
  
• April 6, 2022 -- Midterm-2 (60 minutes)
  In-person SEC-118, Busch Campus
  
  
• April 11, 2022 -- Lecture 20
  Code generation
  Reading: EAC Chapter 7
  In-person lecture SEC-118, Busch Campus
  
  
• April 13, 2022 -- Lecture 21
  Code generation, intermediate representations
  Reading: EAC Chapter 7, 5
  In-person lecture SEC-118, Busch Campus
  
  
• April 18, 2022 -- Lecture 22
  Compiler optimizations
  Reading: ALSU Chapter 9
  In-person lecture SEC-118, Busch Campus
  
  
• April 20, 2022 -- Lecture 23
  Procedure abstraction, runtime stack, stack frame, lexical scoping, control and access links
  Reading: EAC Chapter 6
  In-person lecture SEC-118, Busch Campus
  
  
• April 25, 2022 -- Lecture 24
  More on procedure abstraction, runtime stack, stack frame, lexical scoping, control and access links
  Reading: EAC Chapter 6
  In-person lecture SEC-118, Busch Campus
  
  
• April 27, 2022 -- Lecture 25
  Maintaining and using access links, displays
  Reading: EAC Chapter 6
  In-person lecture SEC-118, Busch Campus
  
  
• May 2, 2022 (last class) -- Lecture 26
  parameter passing styles, procedure linkage; wrap-up syntax analysis: SLR(1), LALR(1) vs LR(1)
  Reading: EAC Chapter 6, 3.4
  In-person lecture SEC-118, Busch Campus
  
  
• May 10, 2022 -- Final exam, in class (60 minutes), 1:00pm - 2:00pm
  In-person (scheduled final exam hours, exam code C)
  
  

Homeworks

Please submit your homework solution as a single pdf file through canvas.

• Homework problem set 1
  New deadline: Friday, February 11, 2022
  
  
• Homework problem set 2
  Deadline: Wednesday, February 16, 2022
  
  
• Homework problem set 3
  New Deadline: Thursday, March 10, 2022
  
  
• Homework problem set 4
  New Deadline: Friday, April 1, 2022
  
  
• Homework problem set 5
  New Deadline: Wednesday, April 20, 2022
  
  
• Homework problem set 6
  New Deadline: Friday, April 29, 2022
  
  

Projects

All projects are INDIVIDUAL, NOT GROUP projects. For the projects, we use the machines in the ilab cluster. The ilab cluster machines contains the listing of valid hostnames available for projects. You have the same home directory across all machines of the ilab cluster .

• Project 1: A local instruction scheduler .
  NEW deadlines: (1) Code - March 10, 2022, at 11:59pm; (2) Report - March 11, 2022, at 11:59pm.
  
  
• Project 2: A Simple Compiler Front-End
  New due date: Friday, April 22, at 11:59pm
  
  
• Project 3: Local Dead-Code Elimination
  Due date: Wednesday, May 4, at 11:59pm
  
  

Acknowledgement

This course has been based on courses taught by Keith Cooper at Rice University and Chau-Wen Tseng at the University of Maryland.