Basic block

Basic block

In computing, a basic block is code that has one entry point (i.e., no code within it is the destination of a jump instruction), one exit point and no jump instructions contained within it. The start of a basic block may be jumped to from more than one location. The end of a basic block may be a jump instruction or the statement before the destination of a jump instruction. Basic blocks are usually the basic unit to which compiler optimizations are applied. Basic blocks form the vertices or nodes in a control flow graph.

The code may be source code, assembly code or some other sequence of instructions.

More formally, a sequence of instructions forms a basic block if the instruction in each position dominates, or always executes before, all those in later positions, and no other instruction executes between two instructions in the sequence. This definition is more general than the intuitive one in some ways. For example, it allows unconditional jumps to labels not targeted by other jumps. This definition embodies the properties that make basic blocks easy to work with when constructing an algorithm.

The blocks to which control may transfer after reaching the end of a block are called that block's "successors", while the blocks from which control may have come when entering a block are called that block's "predecessors".

The algorithm for generating basic blocks from a listing of code is simple: you scan over the code, marking "block boundaries", which are instructions which may either begin or end a block because they either transfer control or accept control from another point. Then, the listing is simply "cut" at each of these points, and basic blocks remain. Note that this method does not always generate "maximal" basic blocks, by the formal definition, but they are usually sufficient.

Instructions that end a basic block include
*Unconditional and conditional branches, both direct and indirect.
*Returns to a calling procedure
*Instructions which may throw an exception
*Function calls can be at the end of a basic block if they may not return, such as functions which throw exceptions or special calls like C's longjmp and exit.

Instructions which begin a new basic block include
*Procedure and function entry points
*Targets of jumps or branches
*"Fall-through" instructions following some conditional branches
*Instructions following ones that throw exceptions
*Exception handlers

Note that, because control can never pass through the end of a basic block, some block boundaries may have to be modified after finding the basic blocks. In particular, fall-through conditional branches must be changed to two-way branches, and function calls throwing exceptions must have unconditional jumps added after them. Doing these may require adding labels to the beginning of other blocks.

ee also

*Control flow graph

External links

* [ Basic Blocks - GNU Compiler Collection]

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • basic block — noun A sequence of contiguous instructions that contain no jumps or labels. Dividing the code into basic blocks makes analysis of control flow much easier …   Wiktionary

  • extended basic block — noun A sequence of contiguous instructions that contain no labels; unlike basic blocks they may contain jumps An extended basic block can show more easily when expressions have already been calculated …   Wiktionary

  • Block E (Minneapolis) — Block E is the name of a block on Hennepin Avenue in downtown Minneapolis that is also bordered by 7th Street, 1st Avenue North, and 6th Street. It is considered part of the Downtown West neighborhood in Minneapolis, but the block is more of a… …   Wikipedia

  • BASIC extension — BASIC toolkits (aka BASIC extensions) mdash;not to be confused with widget toolkits mdash;were a common type of program for 1980s 8 bit home computers. Generally third party extensions, they added additional features to a computer s built in… …   Wikipedia

  • Basic rate interface — (BRI, 2B+D, 2B1D) is an Integrated Services Digital Network (ISDN) configuration defined in the physical layer standard I.430 produced by the ITU. This configuration consists of two 64 kbit/s bearer channels (B channels) and one 16 kbit/s data… …   Wikipedia

  • Basic Access Control — (BAC) is a mechanism specified to ensure only authorized parties can wirelessly read personal information from passports with an RFID chip. It uses data such as the passport number, date of birth and expiration date to negotiate a session key.… …   Wikipedia

  • Basic Multilingual Plane — Logo von Unicode Unicode [ˈjuːnɪkoʊd] ist ein internationaler Standard, in dem langfristig für jedes sinntragende Schriftzeichen oder Textelement aller bekannten Schriftkulturen und Zeichensysteme ein digitaler Code festgelegt wird. Ziel ist es,… …   Deutsch Wikipedia

  • Block (programming) — In computer programming, a block is a section of code which is grouped together. Blocks consist of one or more declarations and statements. A programming language that permits the creation of blocks, including blocks nested within other blocks,… …   Wikipedia

  • Basic Latin unicode block — The Basic Latin unicode block (full name: C0 Controls and Basic Latin) is the first block of the Unicode standard, and the only block which is encoded in one byte in UTF 8. The block contains all the letters and control codes of the ASCII… …   Wikipedia

  • Block design — In combinatorial mathematics, a block design (more fully, a balanced incomplete block design) is a particular kind of set system, which has long standing applications to experimental design (an area of statistics) as well as purely combinatorial… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”