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.

Definition
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.
 One exit point, meaning that only the last instruction can cause the program to begin executing code in a different basic block.
Under these circumstances, whenever the first instruction in a basic block is executed, the rest of the instructions are necessarily executed exactly once and in order.

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 (always executes before) all those in later positions.
 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 start of a basic block may be jumped to from more than one location.

Creation algorithm
The algorithm for generating basic blocks from a listing of code is simple: the analyser scans over the code, marking block boundaries, which are instructions that 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 (maximal basic blocks are basic blocks that cannot be extended by including adjacent blocks without violating the definition of a basic block).

Input: A sequence of instructions (mostly three-address code).

Output: A list of basic blocks with each three-address statement in exactly one block.

 Identify the leaders in the code. Leaders are instructions that come under any of the following 3 categories:
 It is the first instruction. The first instruction is a leader.
 The target of a conditional or an unconditional goto/jump instruction is a leader.
 The instruction that immediately follows a conditional or an unconditional goto/jump instruction is a leader.
 Starting from a leader, the set of all following instructions until and not including the next leader is the basic block corresponding to the starting leader. Thus every basic block has a leader.

Instructions that end a basic block include the following:
 unconditional and conditional branches, both direct and indirect;
 returns to a calling procedure;
 instructions that may throw an exception;
 function calls can be at the end of a basic block if they can not return, such as functions that throw exceptions or special calls like C's longjmp and exit.

Instructions that begin a new basic block include the following:
 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 instructions may have to be modified to find 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.

See also

 Block (programming)
 Control-flow graph
 Decision-to-decision path
 Extended basic block
 Linear code sequence and jump

References

External links
 Basic Blocks - GNU Compiler Collection
 Extended Basic Block - Wiktionary

Compiler construction
컴퓨팅에서, 기본 블록 (basic block)은 엔트리 외에는 들어오는 분기가 없고, 출구 외에는 나가는 분기가 없는 직선 코드열이다. 이 제한된 형태는 기본 블록을 분석하는 용도로 매우 유용하게 만든다. 컴파일러들은 보통 분석 과정의 첫 번째로 프로그램들을 그들의 기본 블록들로 분해한다. 기본 블록들은 제어 흐름 그래프에서 정점 또는 노드의 형태를 갖는다.

정의 
기본 블록에 있는 코드는 다음을 갖는다:
 하나의 엔트리 포인트, 이것은 프로그램 어디에서든 점프 명령어의 목적지인 코드가 내부에 없다는 것을 의미한다.
 하나의 종료 포인트, 이것은 오직 마지막 명령어가 프로그램이 다른 기본 블록에 있는 코드의 실행을 시작할 수 있게 한다는 것을 의미한다.
이러한 환경 하에서, 기본 블록의 첫 번째 명령어가 실행될 때마다, 나머지 명령어들은 필연적으로 순서에 따라 정확히 한 번 실행된다.

코드는 소스 코드, 어셈블리 코드 또는 다른 순차 명령어 집합일 것이다.

더 형식적으로, 순차 명령어 집합은 다음과 같다면 기본 블록을 형성한다.
 각 위치가 지배하거나, 항상 다음 위치들의 전에 실행되는 명령어
 순서에서 어떠한 명령어도 두 명령어들 사이를 실행할 수 없다.
이 정의는 몇몇 방식들에서, 직관적인것 보다 더 일반적이다. 예를 들면, 이것은 다른 점프들의 대상이 아닌 레이블에 대한 무조건적인 점프를 허용한다. 이 정의는 알고리즘을 설계할 때 기본 블록들이 쉽게 동작하게 만들어 주는 속성들을 상징한다.

제어가 블록의 끝에 도달한 후에 전달되는 블록을 블록의 후임자(successor)라고 하며, 블록에 들어올 때 제어가 오는 블록을 전임자(predecessor)라고 한다. 기본 블록의 시작은 한 위치 이상에서의 점프이다.

생성 알고리즘 
코드 목록에서 기본 블록들을 생성하는 알고리즘은 간단하다: 분석기는 코드를 스캔하고, 블록 경계를 마킹하는데, 이것은 블록을 시작하거나 끝내는 명령어이다(이 명령어들이 제어를 전달하거나 다른 지점에서 받아들이기 때문). 그 후 리스트는 간단하게 이러한 각 지점들에서 잘라지고, 기본 블록들은 남게 된다.

공식적인 정의에 따라, 이 방식이 항상 최대 기본 블록들을 생성하지는 않는다는 것에 주의하라. 하지만 이것들은 보통 충분하다(최대한의 기본 블록들이란 기본 블록의 정의를 위반하지 않으면서, 인접한 블록들을 포함하면서 확장될 수 없는 기본 블록들이다).

입력: 순차 명령어 집합 (대부분 3-어드레스 코드).
출력: 정확히 한 블록 안에서 각 3-어드레스 선언을 갖는 기본 블록들의 리스트.

1 단계. 코드에서 리더를 식별한다. 리더들은 다음의 세 분류에 포함되는 명령어들이다:
 첫 번째 명령어는 리더이다.
 조건 또는 무조건 goto/jump 명령어의 대상은 리더이다.
 조건 또는 무조건 goto/jump 명령어의 바로 다음 명령어는 리더이다.
2 단계. 리더에서 시작해서 다음 리더까지의(다음 리더는 포함하지 않는다) 명령어들의 모든 집합은 시작하는 리더에 상응하는 기본 블록이다.

그러므로 모든 기본 블록을 리더를 갖는다.

기본 블록을 끝내는 명령어들은 다음을 포함한다:
 직접이나 간접 모두, 조건 그리고 무조건 분기
 호출한 프로시저로의 리턴
 예외를 던질 수 있는 명령어들
 만약 이것들이 반환하지 않는다는 가정 하에, 함수 호출들은 기본 블록의 끝에서 기본 블록을 끝낼 수 있다. 이러한 함수들은 예외를 던지거나 C의 longjmp 그리고 exit 같은 특별한 호출을 하는 함수들이다.
 리턴 명령어 자신
새로운 기본 블록을 시작하는 명령어들은 다음을 포함한다:
 프로시저 그리고 함수 엔트리 포인트들
 점프나 분기의 대상들
 몇몇 조건 분기들에 따라오는 "완료되지 못하는" 명령어들
 예외를 던진 후에 따라오는 명령어들
 예외 처리기
제어가 절대로 기본 블록의 끝에 전달될 수 없기 때문에, 몇몇 블록 경계들은 기본 블록들을 찾은 후에 수정되어야 한다는 점에 주의하라. 특히, 완료되지 못하는 조건 분기들은 반드시 쌍방 분기로 바뀌고, 예외를 던지는 함수 호출들은 반드시 무조건 점프로 뒤에 더해져야 한다. 이러한 것들은 하는 것은 다른 블록들의 시작에 레이블을 추가하는 것을 필요로 한다.

같이 보기 
 블록 (프로그래밍)
 제어 흐름 그래프
 확장된 기본 블록
 선형 코드열과 점프

각주

외부 링크 
 Basic Blocks - GNU Compiler Collection
 Extended Basic Block - Wiktionary
컴파일러 구성