In the field of
compiler optimization
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 con ...
s, available expressions is an analysis algorithm that determines for each point in the program the set of
expressions that need not be recomputed. Those expressions are said to be ''available'' at such a point. To be available on a program point, the operands of the expression should not be modified on any path from the occurrence of that expression to the program point.
The analysis is an example of a forward
data flow analysis
In the pursuit of knowledge, data (; ) is a collection of discrete values that convey information, describing quantity, quality, fact, statistics, other basic units of meaning, or simply sequences of symbols that may be further interpreted. ...
problem. A set of available expressions is maintained. Each statement is analysed to see whether it changes the operands of one or more available expressions. This yields sets of available expressions at the end of each
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 decom ...
, known as the outset in data flow analysis terms. An expression is available at the start of a basic block if it is available at the end of each of the basic block's predecessors. This gives a set of equations in terms of available sets, which can be solved by an iterative algorithm.
Available expression analysis is used to do global
common subexpression elimination In compiler theory, common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a sing ...
(CSE). If an expression is available at a point, there is no need to re-evaluate it.
References
* Aho, Sethi & Ullman: ''Compilers - Principles, Techniques, and Tools'' Addison-Wesley Publishing Company 1986
Compiler optimizations
Data-flow analysis
{{compsci-stub