Lecture

Dataflow Analysis: Optimization

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 dataflow analysis for optimization purposes, focusing on equations solving, live variables, reaching definitions, and very busy expressions. It explains how to speed up dataflow analyses using work-list algorithms, equation ordering, basic blocks, and bit-vectors. The instructor emphasizes the importance of intermediate representations (IRs) in code optimization and discusses rewriting optimizations in machine-independent contexts.

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 (32)

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

Program optimization

In computer science, program optimization, code optimization, or software optimization, is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources. In general, a computer program may be optimized so that it executes more rapidly, or to make it capable of operating with less memory storage or other resources, or draw less power. Although the word "optimization" shares the same root as "optimal", it is rare for the process of optimization to produce a truly optimal system.

In-place algorithm

In computer science, an in-place algorithm is an algorithm that operates directly on the input data structure without requiring extra space proportional to the input size. In other words, it modifies the input in place, without creating a separate copy of the data structure. An algorithm which is not in-place is sometimes called not-in-place or out-of-place. In-place can have slightly different meanings. In its strictest form, the algorithm can only have a constant amount of extra space, counting everything including function calls and pointers.

Divide-and-conquer algorithm

In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as sorting (e.g., quicksort, merge sort), multiplying large numbers (e.

Selection algorithm

In computer science, a selection algorithm is an algorithm for finding the th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the th order statistic. Selection includes as special cases the problems of finding the minimum, median, and maximum element in the collection. Selection algorithms include quickselect, and the median of medians algorithm. When applied to a collection of values, these algorithms take linear time, as expressed using big O notation.

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.

Set Cover: Integrality Gap

Explores the integrality gap concept in set cover and multiplicative weights algorithms.

Dataflow Analysis: Translation Inefficiencies and Optimizations

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

Algorithms: Summary of the week

Covers algorithms for searching, sorting, optimization, and the Halting Problem.

Optimizing Recursive Queries