Register Allocation

Parsing

Type Checking

Instruction Scheduling

Garbage Collection

Loops

Dataflow Analysis

Partial Redundancy Elimination

Constant Propagation

JoeQ Framework

Software Pipelining

Parallelization

Loop Transformations

Pipelined Parallelism

Pointer Analysis

BDDs in Pointer Analysis

Satisfiability Modulo Theories (SMT)

Natural Language Programming

CS 243: Program Analysis and Optimizations Stanford University Winter 2023 Focuses on efficient high-level programming through code optimization and program analysis for quality improvement. Also explores automatic memory management and natural language coding through machine learning. ## What do we teach?

- How do we make high-level programming languages efficient by optimizing the code? (Data-flow analysis)
- Machine learning and scientific computing need a lot of cycles; machines such as GPUs are complex to code. How do we automatically generate efficient code for these machines effectively. (Parallelism and Locality)
- Can we use program analysis to improve the quality of the code such as detecting security bugs in programs? (Pointer analysis, Satisfiability Modulo Theories)
- How do we automatically manage memory efficiently so users do not have to manage it themselves? (Garbage collection)
- The highest programming language is obviously natural language. With the recent introduction of large language models such as GPT3 and CodeX, how do we let consumers code in natural language using machine learning? Note: no prior knowledge in machine learning is needed. (Neural networks)

## How do you learn this?

As compilers are one of the most complex programs we write, by teaching compilers, we are also teaching software engineering. It is a course where programming and mathematics meet. We show how to apply general mathematical concepts (fixpoint computations, graph theory, linear algebra, binary decision diagrams, neural networks) to handle various complex programming problems. You will learn how to formulate solutions to problems, and not just memorizing prior work. ## Course Emphasis

- **Methodology: apply the methodology to other real life problems**
    - Problem statement
        - Which problem to solve?
    - Theory and Algorithm 
        -Theoretical frameworks 
        - Algorithms
    - Experimentation: Hands-on experience (Weekly programming/written homeworks)
- **Compiler knowledge:**
    - Non-goal: how to build a complete optimizing compiler
    - Important algorithms
    - Exposure to new ideas
    - Background to learn existing techniques CS 103 or CS 103B, and CS 107; Java programming language experience 

CS 243: Program Analysis and Optimizations

Lexical Analysis

Implementation of Lexical Analysis

Syntax-Directed Translation

Top-Down Parsing 

Bottom-Up Parsing

Semantic Analysis

Run-time Environments

Code Generation

Operational Semantics

Intermediate Code

Local Optimization

Global Optimization

Automatic Memory Management

CS 143 Compilers Stanford University Spring 2022 Combination of theoretical and practical perspectives on compiler design. This course emphasizes correctness over performance, providing a deep understanding of compiler structure and functioning. ## Course Structure

- Course has theoretical and practical aspects
- Need both in programming languages!
- Written assignments + exams = theory
- Programming assignments = practice Open the lid of compilers and see inside
- Understand what they do
- Understand how they work
- Understand how to build them

Correctness over performance
- Correctness is essential in compilers
- They must produce correct code
- CS143 is more like CS103+CS110 than CS107
- Other classes focus on performance (CS149, CS243)  There is no required textbook. You can optionally use “Compilers: Principles, Techniques, and Tools” by Aho, Lam, Sethi and Ullman as a reference.

CS 143 Compilers

Boolean

Function (computer programming)

Lambda

Regular Expressions

Intermediate Representations

Compiler

Functional Programming (FP)

OCaml

Pattern Matching

Types

Custom Types

S-Expression

Unary Operations

Correctness and Testing

Conditional (computer programming)

Binary Operations

Naming Expressions

Pairs

Handling Errors

Tail Call Optimization

First-Class Functions

Function Pointers

Optimization

Constant Folding

CS 164: Programming Languages and Compilers UC Berkeley Fall 2022 Explores how compilers translate high-level languages into machine-understandable code, offering practical experience with developing compilers for various languages. Also covers reasoning about compiler correctness and understanding runtime errors.  Have you ever wondered why C programs seem to run faster than Python programs? Have you ever been confused by an error message and wondered why Java couldn’t understand your program? In CS 164, we’ll learn how compilers take in code in one language and produce code in another; in particular, we’ll learn how to translate high-level languages into code that your computer’s processor can understand. We’ll get hands-on practice developing compilers for a series of increasingly complex languages. Along the way, we’ll learn some general best practices for developing and testing complex software systems. After completing this course, students will be able to:

- Develop programs to translate between different programming languages
- More broadly, develop programs that operate on programs
- Explain the relationship between compilers and interpreters, and the differences between them
- Understand the tools they use to run programs—and the errors those tools produce
- Assign meaning to high-level language constructs
- Implement high-level language constructs
- Reason about what it means for a compiler to be correct
- Reason about undefined behavior
- Read and write assembly language
- Write a parser - [CS 61B. Data Structures](https://www2.eecs.berkeley.edu/Courses/CS61B/)
- [CS 61C. Machine Structures](https://www2.eecs.berkeley.edu/Courses/CS61C/)

### Course Culture

Students taking CS 164 come from a wide range of backgrounds. We hope to foster an inclusive and safe learning environment based on curiosity rather than competition. All members of the course community—the instructor, students, and GSIs—are expected to treat each other with courtesy and respect. Some of the responsibility for that lies with the staff, but a lot of it ultimately rests with you, the students. There is no textbook for the course; all readings will be provided digitally.

CS 164: Programming Languages and Compilers

Static Single-assignment (SSA)

Control-flow Graph (CFG)

Basic Blocks

Instruction Selection

Middle End

Dataflow Theory

Lexing

Typechecking

Static Semantics

Calling Conventions

Dynamic Semantics

Mutable Store

struct (C programming language)

Locality

Alias Analysis

15-411 Compiler Design Carnegie Mellon University Fall 2020 Comprehensive study of compiler design and implementation, examining interaction between language design and runtime organization. Topics include program analysis, code generation, optimization, memory management. This course covers the design and implementation of compiler and runtime systems for high-level languages, and examines the interaction between language design, compiler design, and runtime organization. Topics covered include lexical and syntactic analysis, type-checking, program analysis, code generation and optimization, memory management, and runtime organization. - Distinguish the main phases of a state-of-the-art compiler
- Understand static and dynamic semantics of an imperative language
- Develop parsers and lexers using parser generators and combinators
- Perform semantic analysis
- Translate abstract syntax trees to intermediate representations and static single assignment form
- Analyze the dataflow in an imperative language
- Perform standard compiler optimizations
- Generate efficient assembly code for a modern architecture
- Allocate registers using a graph-coloring algorithm
- Understand opportunities and limitations of compiler optimizations
- Appreciate design tradeoffs how representation affects optimizations
- Automatically manage memory using garbage collection
- Develop complex software following high-level specifications  

15-411 Compiler Design

Compiler is a computer program that translates code written in a high-level programming language (such as C++ or Java) into machine code that can be executed by a computer. By learning Compilers, you can gain a deeper understanding of how code is executed by a computer, which helps you write more efficient and effective programs. It also enables you to create new programming langauges or optimizing existing ones.

Compilers

Computer Science

Compilers

Prerequisites

Common concepts