Lecture

Closure Conversion and Dataflow Analysis

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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.

Instructor

Michel Schinz

Teaching & PhD Courses Advanced compiler construction CS-420 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. Practice of object-oriented programming CS-108 Students improve their knowledge of Java and put it into practice by implementing a sizeable project. They learn how t

Official source

Ontological neighbourhood

Computer engineering

Computer programming: Compilers

Related concepts (31)

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.

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.

Regular expression

A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a match pattern in text. Usually such patterns are used by string-searching algorithms for "find" or "find and replace" operations on strings, or for input validation. Regular expression techniques are developed in theoretical computer science and formal language theory. The concept of regular expressions began in the 1950s, when the American mathematician Stephen Cole Kleene formalized the concept of a regular language.

Related lectures (64)

Code Optimization: Speeding-up Analyses

Explores techniques to speed up dataflow analyses and discusses the importance of node ordering and post-order traversal.

Dataflow Analysis: Translation Inefficiencies and Optimizations

Explores translation inefficiencies, optimizations, hoisting functions, closure conversion, and dataflow analysis concepts like available expressions and live variables.

Optimization with Constraints: KKT Conditions

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

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

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

Related concepts (31)

Optimizing compiler

Parsing expression grammar

Dead-code elimination

Regular expression