Data-flow analysis | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

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. A simple way to perform data-flow analysis of programs is to set up data-flow equations for each node of the control-flow graph and solve them by repeatedly calculating the output from the input locally at each node until the whole system stabilizes, i.e., it reaches a fixpoint. This general approach, also known as Kildall's method, was developed by Gary Kildall while teaching at the Naval Postgraduate School. Data-flow analysis is the process of collecting information about the way the variables are defined and used in the program. It attempts to obtain particular information at each point in a procedure. Usually, it is enough to obtain this information at the boundaries of basic blocks, since from that it is easy to compute the information at points in the basic block. In forward flow analysis, the exit state of a block is a function of the block's entry state. This function is the composition of the effects of the statements in the block. The entry state of a block is a function of the exit states of its predecessors. This yields a set of data-flow equations: For each block b: In this, is the transfer function of the block . It works on the entry state , yielding the exit state . The join operation combines the exit states of the predecessors of , yielding the entry state of . After solving this set of equations, the entry and/or exit states of the blocks can be used to derive properties of the program at the block boundaries. The transfer function of each statement separately can be applied to get information at a point inside a basic block.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (3)

Related people (2)

Related concepts (11)

Related courses (5)

Related lectures (64)

Constant folding

Constant folding and constant propagation are related compiler optimizations used by many modern compilers. An advanced form of constant propagation known as sparse conditional constant propagation can more accurately propagate constants and simultaneously remove dead code. Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime. Terms in constant expressions are typically simple literals, such as the integer literal 2, but they may also be variables whose values are known at compile time.

Use-define chain

Within computer science, a Use-Definition Chain (UD Chain) is a data structure that consists of a use, U, of a variable, and all the definitions, D, of that variable that can reach that use without any other intervening definitions. A UD Chain generally means the assignment of some value to a variable. A counterpart of a UD Chain is a Definition-Use Chain (DU Chain), which consists of a definition, D, of a variable and all the uses, U, reachable from that definition without any other intervening definitions.

Basic block

In compiler construction, a basic block is a straight-line code sequence with no branches in except to the entry and no branches out except at the exit. This restricted form makes a basic block highly amenable to analysis. Compilers usually decompose programs into their basic blocks as a first step in the analysis process. Basic blocks form the vertices or nodes in a control-flow graph. The code in a basic block has: One entry point, meaning that no code within it is the destination of a jump instruction anywhere in the program.

Non-Volatile Memory (NVM) is an emerging type of memory device that provides fast, byte-addressable, and high-capacity durable storage. NVM sits on the memory bus and allows durable data structures de

EPFL2021

Stability of time-sensitive networks: strategies for partial regulation

Nicolò Dal Fabbro

In time-sensitive networks, regulators can be used to reshape traffic, and their usage may be necessary to guarantee stability by providing worst-case delay bounds. In this project, I study partial re

2020

Numerical Simulation and Flow Analysis of an Elbow Diffuser

Sebastiano Mauri

EPFL/LMH2002

CS-550: Formal verification

We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to u

MATH-101(de): Analysis I (German)

Es werden die Grundlagen der Analysis sowie der Differential- und Integralrechnung von Funktionen einer reellen Veränderlichen erarbeitet.

CIVIL-557: Decision-aid methodologies in transportation

The course proposes an introduction to operations research, big data analysis, and mathematical modelling for decision support in transportation systems.

Wurzelkriterium: Majorantenkriterium MATH-101(de): Analysis I (German)

Covers the Majorantenkriterium and Wurzelkriterium for convergence tests of series.

Boolean Types and Control Structures

Explores boolean types, logical operators, and control structures in Python, emphasizing the evaluation of expressions and the use of relational operators.

The transhipment problem, The maximum flow problem MOOC: Optimization: principles and algorithms - Linear optimization

Explores the maximum flow and transhipment problems in network optimization.