COMP 412: Compiler Construction for Undergraduates
Keith Cooper
Zoran Budimlic
Department of Computer Science
Rice University
Houston, Texas, USA
Fall 2017: HZ 212 on Monday, Wednesday, and Friday at 11:00am


Slides and/or Notes

  1. Introduction to the Course
    Read Chapter 1 for Wednesday

  2. The Compiler's Front End (Lab 1)     Slides Related to Lab 1
  3. Local Register Allocation (Lab 1)
  4. Lab 1 Tutorial Slides

  5. Implementing Scanners      (Lecture not presented, here for reference in Lab 1)

  6. Lexical Analysis, I      Chapter 2 in EaC2e
  7. Lexical Analysis, II     Thompson's Construction, Subset Construction
  8. Lexical Analysis, III    DFA Minimization
    Draft Text on Hopcroft's Algorithm from 3rd edition of EaC
  9. Lab 1 Tutorial 2 Slides

  10. Introduction to Parsing     Chapter 3 in EaC2e, Start of Top-Down Parsing
  11. Parsing, II
  12. Parsing, III     Recursive descent parsing
  13. Parsing, IV     First and Follow Sets, LL(1) Parsing

  14. Parsing, V     Bottom-up Parsing and Handles
  15. Parsing, VI     LR(1) parsers: how they work & preliminaries for the table construction
  16. Parsing, VII     Canonical LR(1) Table Construction Algorithm
  17. Parsing, VII     Wrap up for LR parsing

  18. Introduction to Syntax-Directed Translation     Chapter 4 in EaC2e
  19. Intermediate Representations     Chapter 5 in EaC2e + other corners of EaC2e
  20. Intermediate Representations, part II
  21. More Syntax-Directed Translation     Details on the Midterm as well
    A practice exam

    Material above this line is covered on the midterm exam

    Material below this line is covered on the final exam

  22. Code Shape
    Paper mentioned in class and lecture notes:   Robert Floyd, "An Algorithm for Coding Efficient Arithmetic Operations," CACM 4(1), January 1961, pages 42-51.

  23. Naming
  24. Storage Layout and Memory Systems
  25. Garbage Collection

  26. Local Instruction Scheduling     <== Lab 3

  27. Lab 3 Tutorial 1 Slides
  28. Paper mentioned in the lecture:    Gibbons and Muchnick's classic paper (1986) "Efficient Instruction Scheduling for a Pipelined Architecture," in Proceedings of the SIGPLAN 1986 Symposium on Compiler Construction

  29. Assignment Statements
  30. Assignment Statments, Continued
    Column mentioned in the lecture: Poul-Henning Kamp, "The Most Expensive One-byte Mistake", ACM Queue, July 25, 2011
  31. Implementing Control-Flow Constructs
  32. Procedure and Function Calls
  33. Procedure and Function Calls, Part II
  34. Lab 3 Tutorial 2 Slides

  35. Runtime support for naming in Algol-like languages
  36. Runtime support for naming in object-oriented languages
  37. Runtime support for naming in object-oriented language, Part IIs
    Paper mentioned in the lecture: L.P. Deutsch and A.M Schiffman, "Efficient Implementation of the Smalltalk-80 System," ACM Symposium on Principles of Programming Languages (POPL), 1984.

  38. Local Value Numbering     Chapter 8
  39. Eliminating Useless and Unreachable Code     Chapter 10

  40. Introduction to Instruction Selection
  41. Selection by Tree-Pattern Matching     Reading: Section 11.3 of 3rd edition of EaC
  42. Selection by Peephole Optimization     Reading: Section 11.5 in 2nd edition of EaC

  43. Regional Scheduling Techniques     Chapter 12

  44. Just-In-Time Compilers and Runtime Optimizers
    Paper:    Michael Paleczny, Chris Vick, and Cliff Click, " The Java HotSpot(TM) Server Compiler," Proceedings of JVM '01, April 2001.
    Paper:    Vasanth Bala, Evelyn Duesterwald, Sanjeev Banerjia, " Dynamo: A Transparent Dynamic Optimization System," Proceedings of the ACM SIGPLAN 2000 Symposium on Programming Language Design and Implementation, May 2000.
    Paper:    See also: Deutsch-Schiffman paper referenced in (37) above.

Additional Materials

  1. Information on the ILOC Virtual Machine and its Trace Facility
  2. The Software Stack
    What happens to code after compilation?
  3. Notes on Garbage Collection in Java
    It is hard to understand your Java lab's performance without understanding garbage collection and its impact on running times.


Fall 2017 Syllabus

Comp 412 Home Last modified Friday, 01-Dec-2017 10:32:26 CST.