02247 Compiler Construction — Spring 2023

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

These lecture notes are also available in PDF format.

Important

The home page for this course (with course plan, calendar, groups, project submission…) is on DTU Learn: https://learn.inside.dtu.dk/d2l/home/145305

These lecture notes will be updated throughout the course. The latest updates are listed in the ChangeLog.

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?
  • Closures that Capture Immutable Variables
  • Closures that Capture Mutable Variables
  • 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
• ChangeLog