CMP 2
From LRDE
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
This page contains the log of the topics of the Compiler Construction Course 1 and Compiler Construction Course 2 for Ing1 students of class EPITA 2010 (i.e., from November 2007 to July 2008). The topic was started with the Formal Languages Lecture; see the ThlLog2010.
Lecture 1: Friday 2007-11-23 (4 hours): Introduction to the Project, Development Tools (%roland%)
- The Tiger Project.
- Ressources (http://www.lrde.epita.fr/~akim/ccmp/).
- Assignments (http://www.lrde.epita.fr/~akim/ccmp/assignments.html).
- Appel's books.
- Tiger Compiler Reference Manual (http://www.lrde.epita.fr/~akim/ccmp/tiger.html).
- epita.cours.compile.
- Goals (C++, OO, DP, Management, Several Iterations, Testing, Documenting, Maintaining, Fixing, Understanding Computers, English).
- Non goals (Compiler Construction).
- Rules of the Game.
- No copy between groups.
- Tests are part of the project (test cases and frameworks should not be exchanged).
- Fixing mistakes earlier is better.
- Work between groups is encouraged as long as they don't cheat.
- Tests.
- Tests matter.
- Rules.
- A bug => a test.
- A suspicious behavior => one or several tests to isolate it.
- Don't throw away tests!
- Don't exchange tests! (bis repetita).
- C Compilation model (cpp, cc1, as, ld).
- Width of a compiler pipe (line, function, compilation unit).
- Compilers handling multiple input (sources languages) and multiple outputs (target assembly languages/processors).
- The case of GCC.
- Factoring the compiler components: intermediate representation(s).
- Front-end and back-ends.
- The Tiger Compiler pipe (annotated with tools and steps).
- Front-end: TC-0 - TC-6 (mandatory part).
- Back-end: TC-7 - TC-9 (optional part).
- Misc: students should overcome Make, Makefiles and seperate compilation, etc.
- Ressources (http://www.lrde.epita.fr/~akim/ccmp/).
- Development Tools. See the lecture notes:
dev-tools.pdf and dev-tools-handout-4.pdf.
- A first glance at Abstract Syntax Trees. See the lecture notes:
ast.pdf and ast-handout-4.pdf, pages 1 to 13.
Lecture 2: Friday 2007-12-07 (4 hours): Scanner and Abstract Syntax (%roland%)
- Scanner. See the lecture notes, scanner.pdf and
- Abstract Syntax. See the lecture notes, ast.pdf and
ast-handout-4.pdf (sections 1 and 2).
Lecture 3: Monday 2007-12-10 (4 hours): Abstract Syntax, cont. (%roland%)
- Abstract Syntax (cont.). See the lecture notes, ast.pdf and
ast-handout-4.pdf (sections 3 and 4).
- Short overview of the TC-1 tarball.
Lecture 4: Thursday 2007-12-13 (2 hours): More on AST Visitors (%roland%)
- More on Visitors.
- Visitor (reminder).
- DefaultVisitor.
- Handling the constness of the visited tree: ConstVisitor and DefaultConstVisitor.
- Factoring Visitors implementation w.r.t. this constness: select_const, GenVisitor<Const> (and GenDefaultVisitor<Const>); first example of a C++ template metaprogramming technique.
- Implementations of polymorphic method calls (dynamic dispatch).
- The C++ approach: virtual tables.
- The SmartEiffel (and Tiger) approach: close-world assertion and comprehensive dispatch based on tests (if / switch).
- Tiger and Panther (subset of Tiger w/o object constructs).
- The path from "AST + bindings + types" to HIR: translation, TC-5 (reminder).
- Two flavor of the language: with object constructs (Tiger) and without (Panther); options --object-*.
- Handling object constructs before the translation: object desugaring (Tiger -> Panther).
- The need for two Visitor hierarchies before the translation.
- Using inheritance to factor...
- ...but a naive approach doesn't work.
- Adding dummy methods for non-object Visitors.
- Factoring using a mixin-based approach: NonObjectVisitor.
- Handling the constness: NonObjectConstVisitor and GenObjectConstVisitor<Const>.
Lecture 5: Thursday 2007-12-20 (4 hours): Names, identifiers and bindings (%roland%)
- Symbols, Identifiers and Bindings. See the lecture notes, names.pdf and names-handout-4.pdf.
Lecture 6: Friday 2007-12-21 (4 hours): Type-checking (%roland%)
- Types. See the lecture notes, type-checking.pdf
and type-checking-handout-4.pdf
- Sequent Calculus
- In English: "If alpha is of type Int in the context Gamma and beta is of type Int in the context Gamma,
then alpha + beta is of type Int in the context Gamma."
- Using symbols (where ||- ("tee" or "turnstile") is the symbol meaning "yields" or "proves"):
%TABLE{tableborder="0" tablerules="rows" cellpadding="3" cellspacing="3" databg="none"}%
Γ |- α : Int Γ |- α : Int |
Γ |- α + β : Int |
- Examples of type rules: addition of 2 integers, if-then-else, if-then, addition of 3 integers, comparison of two variables, etc.
- Type inference
- (a_ ? _b : _c_) > 0
- (a_ ? _b : f_ (_b)) > 0
- (a_ ? _b : f_ (_c)) > 0
- Some details on the implementation of types and type-checking within the Tiger Compiler.
- Hierarchy of types (src/type/)
- src/type/README.
- Implementing atomic types: singletons.
- Resolving aliased types: Named and actual().
- Insight of some visit methods from the TypeChecker.
- Hierarchy of types (src/type/)
Warning: Display title "CMP 2" overrides earlier display title "CMP 1".
Lecture 1: Monday 2008-02-11 (2 hours): Intermediate languages, part 1 (%roland%)
- Intermediate languages. See the lecture notes, intermediate.pdf and intermediate-handout-4.pdf (pages 1 to 47, spim Memory Model)
Lecture 2: Monday 2008-02-25 (2 hours): Intermediate languages, part 2 (%roland%)
- Intermediate languages. See the lecture notes, intermediate.pdf and intermediate-handout-4.pdf (pages 48 to 76, Clever Translations)
Lecture 3: Monday 2008-03-10 (2 hours): TC-5, Canonization (TC-6) (%roland%)
- TC-5, Canonization (TC-6). See the lecture notes, intermediate.pdf and intermediate-handout-4.pdf (pages 77 to 102)
Lecture 4: Wednesday 2008-04-23 (2 hours): RISC, MIPS, Instruction Selection (TC-7) (%roland%)
- The RISC architecture and the MIPS R2000 assembly languagel; instruction selection. See the lecture notes, instr-selection.pdf and instr-selection-handout-4.pdf.
- Samples of MonoBURG inputs from the Tiger Compiler.
Lecture 5: Monday 2008-04-28 (2 hours): Liveness Analysis (LC-8), Register Allocation, part 1 (TC-9) (%roland%)
- Liveness analysis. See the lecture notes, liveness.pdf and liveness-handout-4.pdf
- An example of consrtuction of a a liveness graph, based on the the first control flow graph from the slides.
- Register allocation (first half). See the lecture notes, regalloc.pdf and regalloc-handout-4.pdf (page 1 to 62, Coalescing).
- Register allocation (second half). See the lecture notes, regalloc.pdf and regalloc-handout-4.pdf (page 63 to the end).
- Subprograms. See TylaLogIng2010, lecture 3.
-- %roland% - 16 May 2008