02247 Compiler Construction — Spring 2024

These are the lecture notes of the course 02247 Compiler Construction at DTU Compute.

Important

The home page for this course (with course plan, calendar, discussion forum, lecture recordings…) is on DTU Learn: https://learn.inside.dtu.dk/d2l/home/187668

These lecture notes will be updated throughout the course, and you will be notified in case of changes. The latest updates are listed in the ChangeLog.

Fig. 1 The main dependencies between the modules of this course. NOTE: some references and minor dependencies between modules are not shown in this diagram; they may be more or less important depending on the project ideas you will choose to work on.

Contents

• Module 0: Overview of the Course and Assessment
  • What is a Compiler?
  • Course Objectives and Rationale
  • A Taste of Hygge
  • Tools and Programming Languages Used During the Course
  • Assessment: Group Project and Oral Group Examination
  • Group Work Organisation: Some Suggestions
• Module 1: Introduction to RISC-V
  • What is RISC-V? And Why Is It Relevant?
  • Base and Floating-Point Registers
  • A Few RISC-V Assembly Instructions
  • RISC-V Assembly Program Structure
  • RARS — RISC-V Assembler and Runtime Simulator
  • References and Further Readings
  • Lab Exercises
• Module 2: The Hygge0 Language Specification
  • Formal Syntax of Hygge0
  • Formal Semantics of Hygge0
  • Type-Checking Hygge0 Programs
  • References and Further Readings
  • Lab Activities
• Module 3: Hands-On with hyggec
  • Quick Start
  • The Compiler Phases of hyggec
  • Overview of the hyggec Source Tree
  • The Abstract Syntax Tree
  • The Lexer and Parser
  • The Built-In Interpreter
  • Types and Type Checking
  • Code Generation
  • The Test Suite of hyggec
  • Example: Extending Hygge0 and hyggec with a Subtraction Operator
  • Project Ideas
• Module 4: Lab Day
• Module 5: Mutability and Loops
  • Overall Objective
  • Mutable Variables
  • “While” Loop
  • Project Ideas
• Module 6: Functions and the RISC-V Calling Convention
  • Overall Objective
  • Syntax
  • Operational Semantics
  • Typing Rules
  • The RISC-V Memory Layout, Stack, and Calling Convention
  • Implementation
  • Limitations of the Current Specification and Code Generation
  • References and Further Readings
  • Project Ideas
• Module 7: Structured Data Types and the Heap
  • Overall Objective
  • Syntax
  • Operational Semantics
  • Typing Rules
  • Implementation
  • References and Further Readings
  • Project Ideas
• Module 8: Lab Day
• Module 9: Closures
  • Overall Objective
  • What is a Closure?
  • Compiling Closures that Capture Immutable Variables
  • Interpreting and Compiling Closures that Capture Mutable Variables
  • Compiling Closures that Capture Top-Level Variables
  • Implementation
  • References and Further Readings
  • Project Ideas
• Module 10: Discriminated Unions and Recursive Types
  • Discriminated Union Types and Pattern Matching
  • Recursive Types
  • References and Further Readings
  • Project Ideas
• Module 11: Intermediate Representations and Register Allocation
  • Overall Objective
  • What is an Intermediate Representation (IR)?
  • Administrative Normal Form (ANF)
  • Transformation of a Hygge Expression into ANF
  • ANF-Based Linear Register Allocation
  • Implementation: ANF Transformation and Register Allocation in hyggec
  • References and Further Readings
  • Project Ideas
• Module 12: Optimisation
  • Overall Objective
  • Partial Evaluation
  • Copy Propagation and Common Subexpression Elimination (CSE)
  • Peephole Optimisation
  • References and Further Readings
  • Project Ideas
• Module 13: Exam Q&A and Lab Day
• ChangeLog