In
computing
Computing is any goal-oriented activity requiring, benefiting from, or creating computer, computing machinery. It includes the study and experimentation of algorithmic processes, and the development of both computer hardware, hardware and softw ...
, an extended basic block is a collection of
basic blocks of the code within a
program with certain properties that make them highly amenable to optimizations. Many
compiler optimizations operate on extended basic blocks.
Definition
An extended basic block is a maximal collection of basic blocks where:
* only the first basic block can have multiple predecessor basic blocks;
* all the other basic blocks have one single predecessor basic block, which must be within the collection of basic blocks.
Uses
Many local optimizations that operate on basic blocks can be easily extended to operate on extended basic blocks. An example is
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 sin ...
which removes duplicate expressions. In its simplest form it is a local optimization, operating only on basic blocks.
See also
*
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 ...
*
Control-flow graph
In computer science, a control-flow graph (CFG) is a representation, using graph notation, of all paths that might be traversed through a program during its execution. The control-flow graph was conceived by Frances E. Allen, who noted that ...
*
Tracing just-in-time compilation
Tracing just-in-time compilation is a technique used by virtual machines to Optimization (computer science), optimize the execution of a program at Run time (program lifecycle phase), runtime. This is done by recording a linear sequence of freque ...
Notes
External links
Basic Blocks - GNU Compiler Collection
{{DEFAULTSORT:Basic Block
Compiler construction