COMP 412: Compiler Construction for Undergraduates
Keith Cooper
Linda Torczon
Department of Computer Science
Rice University
Houston, Texas, USA
Fall 2015: Room 180, Dell Butcher Hall, Monday, Wednesday, Friday, 11:00am


Slides and/or Notes

  1. Introduction and First Content

  2. The Compiler's Front End   (from a Lab 1 perspective)
  3. Local Register Allocation    (Lab 1 related lecture)
  4. Lab 1: Additional Information on the ILOC Virtual Machine and the Simulator's Trace Facility
  5. Lab 1: Slides from the Q and A Session
  6. Lab 1: Slides from the Performance Tutorial

  7. Lexical Analysis, I
  8. Lexical Analysis, II   Thompson's Construction (&, perhaps, the Subset Construction)
          + a remark on allocation time versus runtime
  9. Lexical Analysis, III   Subset Construction, Brzozowksi's Algorithm, Kleene's Algorithm
  10. Lexical Analysis, IV  DFA Minimization with Hopcroft's Algorithm
  11. Lexical Analysis, V   Implementing Scanners   <= Lecture not given, slides are for reference
  12. Notes On Java Garbage Collection   <= New

  13. Parsing, I   Context-Free Grammars and Ambiguity
  14. Parsing, II   Ambiguity, Intro to Top-Down Parsing
  15. Parsing, III   Left recursion, left factoring, top-down parsing
  16. Parsing, IV   FIRST, FOLLOW, recursive descent
  17. Parsing, V   recursive descent, LL(1), start of bottom-up parsing

  18. Material Covered on the First Hour Exam

    You are responsible for material above this line on the first exam

    Material below this line is covered on the second exam

  19. Parsing, VI   handles in a bottom-up, LR style parser
  20. Parsing, VII   more LR(1) examples
  21. Parsing, VIII   the Canonical LR(1) table construction
  22. Parsing, IX, the last parsing lecture:     another LR(1) example, shift/reduce conflicts, LL vs LR, associativity, and shrinking the ACTION / GOTO tables

  23. Lab 2: Slides from the Q and A Session

  24. Intermediate Representations for Code   trees, DAGs, graphs,
  25. Intermediate Representations, Part 2   linear codes, hybrids, generating IR in recursive descent parsers

  26. Semantic Elaboration, 1   analysis beyond a context-free grammar
  27. Semantic Elaboration, 2

  28. Code Generation Preliminaries   Code Shape, Extending Expressions, Storage Layout, ...
  29. Code Shape for Expressions   ILP, tree balancing, assignment, allocation and deallocation
    Paper mentioned in class and lecture notes:   Robert Floyd, "An Algorithm for Coding Efficient Arithmetic Operations," CACM 4(1), January 1961, pages 42-51.

  30. Generating Code for Arrays
  31. More About Expressions   Structures, Records, Strings, and Calls
    Column mentioned in the lecture: Poul-Henning Kamp, "The Most Expensive One-byte Mistake", ACM Queue, July 25, 2011
  32. Procedure Calls, II   activation records, linkages, long digression into hardware memory hierarchy (cache structure)
  33. Storage Layout
  34. Lexical Scoping and Addressability   symbol tables, access links, and displays

    You are responsible for material above this line on the second exam

    Material below this line is covered on the third exam

  35. Naming: ALLs and OOLs   see also Sections 5.5 and B.4 in EaC2e
  36. Runtime support for OOLs
    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.

  37. Local Instruction Scheduling   Lecture on algorithms for Lab 3
    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
  38. Slides from the Lab 3 Question and Answer Sessions    <== Question and Answer Session
  39. Slides from the Lab 3 Performance Tutorial                    <== Performance Tutorial

  40. Just-In-Time Compilers and Runtime Optimizers
    Papers mentioned in the lecture:

  41. Local Value Numbering    Quick foray into Chapter 8
  42. Superlocal Value Numbering    extended basic blocks, mention of SSA Form

  43. Instruction Selection: Preliminaries
  44. Instruction Selection by Tree-Pattern Matching
  45. Instruction Selection by Peephole Optimization

  46. Data-flow Analysis: A Quick Introduction    dominators, live variables, reaching definitions
    Important background information for the next lecture

  47. Global Register Allocation via Graph Coloring    a reasonably complete treatment of the Chaitin and Briggs allocators

  48. Graph-Coloring Register Allocation, II    plus Linear Scan

  49. Instruction Scheduling: Beyond Basic Blocks    superlocal scheduling, trace scheduling


Fall 2015 Syllabus

Comp 412 Home Last modified Friday, 04-Dec-2015 16:08:10 CST.