▼(CPSC 411 2019W2 – Introduction to Compiler Construction
On this page:
(CPSC 411 2019W2 – Introduction to Compiler Construction
7.5.0.17
    ← prev  up  next → 

(CPSC 411 2019W2 – Introduction to Compiler Construction

The goal of this course is to give students experience designing, implementing, and extending programming languages. Students will start from a machine language, the x86-64 CPU instruction set with Linux system calls (x64), and incrementally build a compiler for a subset of Racket to this machine language. In the proceess, students will practice building, extending, and maintaining a complex piece of software, and practice creating, enforcing, and exploiting abstractions formalized in programming languages.

The course assumes familiarity with basic functional programming in Racket, and some simple imperative programming in assembly.

    1 CPSC 411 Syllabus

      1.1 Land Acknowledgement

      1.2 Course Description

      1.3 Course Information

      1.4 Prerequisites

      1.5 Course Materials

      1.6 Contacts

        1.6.1 Communication about the Course

      1.7 Course Structure

        1.7.1 Working in Groups

      1.8 Learning Objectives

      1.9 Schedule of Topics

      1.10 Evaluation

        1.10.1 Late Policy

        1.10.2 Project Evaluation

        1.10.3 Important: We will grade you on design

        1.10.4 Sharing Tests

      1.11 Copying and Plagiarism Policy

    2 Course Calendar

    3 The Compiler Design Recipe

      3.1 Systematic Program Design for Compilers

      3.2 The Compiler Template Recipe

    4 Organizing Racket Code

      4.1 Organizing your code to keep your graders sane

    5 Compiler 0: x64 to elf64

      5.1 Assignment Summary

      5.2 Language Diagram

      5.3 Preface

      5.4 x64: The First Target Language

        5.4.1 x64 by example

        5.4.2 x64-linux

        5.4.3 x64-macos

        5.4.4 x64-windows

      5.5 Testing Your Development Machine

      5.6 x64 References

    6 Compiler 1: Paren-x64 to x64

      6.1 Assignment Summary

      6.2 Language Diagram

      6.3 Preface: What’s bad about x64

      6.4 x64-411: Our x64 Subset

      6.5 Paren-x64: The First Source Language

        6.5.1 Paren-x64 Definition

          6.5.1.1 Run-time systems.

    7 Compiler 2: Values-lang to x64

      7.1 Assignment Summary

      7.2 Language Diagram

      7.3 Preface

      7.4 Exposing Memory in Paren-x64

      7.5 Loc-lang

      7.6 Values-lang

    8 Compiler 3: Register Allocation (Original)

      8.1 Assignment Summary

      8.2 Language Diagram

      8.3 Register Allocation

      8.4 Conflict Analysis

      8.5 Undead Analysis

      8.6 Optimizing assign-homes

    9 Compiler 3: Register Allocation (Corrected)

      9.1 Assignment Summary

      9.2 Language Diagram

      9.3 Register Allocation

      9.4 Undead and Conflict Analysis

        9.4.1 Undeadness Analysis

        9.4.2 Conflict Analysis

      9.5 Optimizing assign-homes

    10 Compiler 4: Adding Control Flow (Original)

      10.1 Assignment Summary

      10.2 Language Diagram

      10.3 Related Reading

      10.4 Preface: What’s wrong with Values-lang

      10.5 Exposing Control-Flow Primitives

      10.6 Blocks: Abstracting labeled instructions

      10.7 Abstracting Low-level Control Flow

      10.8 Thinking like a compiler

      10.9 Hints

    11 Compiler 4: Adding Control Flow (Corrected)

      11.1 Assignment Summary

      11.2 Language Diagram

      11.3 Related Reading

      11.4 Preface: What’s wrong with Values-lang

      11.5 Exposing Control-Flow Primitives

      11.6 Blocks: Abstracting labeled instructions

        11.6.1 Nested tails

      11.7 Abstracting Low-level Control Flow

      11.8 Register Allocation

        11.8.1 Undead analysis, globally

        11.8.2 Control-flow Analysis, and use/def chains

        11.8.3 Conflict Analysis

        11.8.4 Global Register Allocation

      11.9 Thinking like a compiler

    12 Assignment 5: The CPSC411 Compiler Recovery and Reinvestment Assignment of 2020.

      12.1 Assignment Summary

      12.2 Fixing Your Code

      12.3 Submitting Your Report

      12.4 Code Walks

      12.5 Marking

    13 Compiler 6: Calling Conventions

      13.1 Assignment Summary

      13.2 Language Diagram

      13.3 New Source Language

      13.4 Calling Conventions Introduction

        13.4.1 Designing a Calling Convention Translation

      13.5 Designing New Intermediate Languages

      13.6 Implementing Calling Convention

      13.7 Assigning Frames

      13.8 Adjusting the Register Allocator

      13.9 Implementing New Abstractions

      13.10 Filling in the details

    14 Compiler 7: Immediate Data Types

      14.1 Assignment Summary

      14.2 Language Diagram

      14.3 Preface: What’s Wrong with Values-lang v6

      14.4 Introduction to Tagged Object Representation

      14.5 Exposing Bitwise Operations in Paren-x64

      14.6 Exposing Bitwise Operations in Block-lang

      14.7 Specifying Data Type Representation

        14.7.1 select-instructions

        14.7.2 a-normalize

        14.7.3 specify-representation

        14.7.4 implement-safe-primops

        14.7.5 uniquify

    15 Compiler 8: Structured Data Types

      15.1 Assignment Summary

      15.2 Language Diagram

      15.3 Preface: What’s wrong with Exprs-Lang v7

      15.4 Exposing Heap Pointers in the Back-end

        15.4.1 generate-x64

        15.4.2 implement-mops

        15.4.3 patch-instructions

        15.4.4 Exposing mops up the pipeline

        15.4.5 expose-allocation-pointer

        15.4.6 select-instructions

        15.4.7 a-normalize

        15.4.8 specify-representation

        15.4.9 implement-safe-apply

        15.4.10 implement-safe-primops

        15.4.11 uniquify

    16 Compiler 9: First-class Functions

      16.1 Assignment Summary

      16.2 Language Diagram

      16.3 Preface: What’s wrong with Exprs-Lang v8

      16.4 Administrative Passes

        16.4.1 uniquify

        16.4.2 define->letrec

        16.4.3 optimize-direct-calls

        16.4.4 dox-lambdas

        16.4.5 implement-safe-primops

      16.5 Closure Conversion

        16.5.1 uncover-free

        16.5.2 convert-closures

        16.5.3 Challenge: optimize-known-call

        16.5.4 hoist-lambdas

        16.5.5 implement-closures

        16.5.6 sequentialize-let

        16.5.7 implement-safe-apply

        16.5.8 specify-representation

    17 Compiler 10: Recursive Data and Syntactic Sugar

      17.1 Assignment Summary

      17.2 Language Diagram

      17.3 Preface: What’s wrong with Exprs-Lang v9

      17.4 Preliminary Passes

        17.4.1 uniquify

        17.4.2 define->letrec

      17.5 Resolving Recursive Binding

        17.5.1 purify-letrec

        17.5.2 convert-assigned

        17.5.3 dox-lambdas, implement-safe-primops, uncover-free, convert-closures

      17.6 Syntactic Sugar

        17.6.1 Preface: What’s wrong with Racketish?

        17.6.2 uniquify

        17.6.3 expand-macros

      17.7 )

    18 Assignment 11: The CPSC411 Compiler Encore

      18.1 Assignment Summary

      18.2 Fixing Your Code

      18.3 Submitting Your Report

      18.4 Marking

    ← prev  up  next →