Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Optimization: Register Allocation

In course

CS-420: Advanced compiler construction

Students learn several implementation techniques for modern functional and object-oriented programming languages. They put some of them into practice by developing key parts of a compiler and run time system for a simple functional programming language. ...

Description

This lecture covers advanced compiler construction topics related to optimization techniques such as dead code elimination, common subexpression elimination, constant folding, and register allocation. The instructor explains how register allocation transforms a program using virtual registers into one using physical machine registers, with some registers possibly being spilled to memory. Techniques like graph coloring and linear scan register allocation are discussed, along with inlining heuristics and contification. The lecture also delves into interference graphs, contifiable subsets, and the process of shrinking optimizations. Various examples and exercises are provided to illustrate the concepts.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructor

Michel Schinz

Official source

Ontological neighbourhood

Computer engineering

Computer programming: Compilers

Related concepts (32)

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Optimizing compiler

In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power consumption (the last three being popular for portable computers). Compiler optimization is generally implemented using a sequence of optimizing transformations, algorithms which take a program and transform it to produce a semantically equivalent output program that uses fewer resources or executes faster.

In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers. Register allocation can happen over a basic block (local register allocation), over a whole function/procedure (global register allocation), or across function boundaries traversed via call-graph (interprocedural register allocation). When done per function/procedure the calling convention may require insertion of save/restore around each call-site.

Dead-code elimination

In compiler theory, dead-code elimination (DCE, dead-code removal, dead-code stripping, or dead-code strip) is a compiler optimization to remove dead code (code that does not affect the program results). Removing such code has several benefits: it shrinks program size, an important consideration in some contexts, and it allows the running program to avoid executing irrelevant operations, which reduces its running time. It can also enable further optimizations by simplifying program structure.

Inline expansion

In computing, inline expansion, or inlining, is a manual or compiler optimization that replaces a function call site with the body of the called function. Inline expansion is similar to macro expansion, but occurs during compilation, without changing the source code (the text), while macro expansion occurs prior to compilation, and results in different text that is then processed by the compiler. Inlining is an important optimization, but has complicated effects on performance.

Related lectures (36)

Covers register allocation using graph coloring to minimize memory access in programs.

Statistical Physics for Optimization & Learning

Covers statistical physics tools for optimization, learning, graph coloring, recommendation systems, and neural networks.

Markov Chains and Algorithm Applications

Covers the application of Markov chains and algorithms for function optimization and graph colorings.

Optimization with Constraints: KKT Conditions

Covers the KKT conditions for optimization with constraints, essential for solving constrained optimization problems efficiently.

Compiler verification: Challenges and Benefits

Explores the challenges and benefits of compiler verification, emphasizing the importance of verifying compilers for critical software.

Related concepts (32)

Graph coloring

Optimizing compiler

Dead-code elimination

Inline expansion