In
computing
Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, ...
, 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
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 cons ...
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 si ...
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 deco ...
*
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 discovered 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 optimize the execution of a program at runtime. This is done by recording a linear sequence of frequently executed operations, compiling them to native machine code an ...
Notes
External links
Basic Blocks - GNU Compiler Collection
{{DEFAULTSORT:Basic Block
Compiler construction