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

Lecture

Closure Conversion and Dataflow Analysis

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 closure conversion techniques for mutually-recursive functions, discussing cyclic and shared closures. It explains the transformation process, highlighting inefficiencies in the translation and presenting an improved version that splits functions into a wrapper and worker. The lecture also addresses hoisting functions post-closure conversion and the formalization of available expressions in dataflow analysis. It delves into solving equations iteratively to find the largest sets satisfying the analysis, and generalizes the dataflow equations for available expressions. The session concludes by exploring the scope of dataflow analysis and its applications in program optimization.

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)

Data-flow analysis

Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program's control-flow graph (CFG) is used to determine those parts of a program to which a particular value assigned to a variable might propagate. The information gathered is often used by compilers when optimizing a program. A canonical example of a data-flow analysis is reaching definitions.

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.

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.

Parsing expression grammar

In computer science, a parsing expression grammar (PEG) is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s. Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG.

Closure (computer programming)

In programming languages, a closure, also lexical closure or function closure, is a technique for implementing lexically scoped name binding in a language with first-class functions. Operationally, a closure is a record storing a function together with an environment. The environment is a mapping associating each free variable of the function (variables that are used locally, but defined in an enclosing scope) with the value or reference to which the name was bound when the closure was created.

Related lectures (37)

Covers the efficiency of register machines over stack machines, memory organization, and mapping instructions.

Optimization with Constraints: KKT Conditions

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

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

Optimization Methods: Theory Discussion

Explores optimization methods, including unconstrained problems, linear programming, and heuristic approaches.