기본 블록
컴퓨팅에서, 기본 블록 (basic block)은 엔트리 외에는 들어오는 분기가 없고, 출구 외에는 나가는 분기가 없는 직선 코드열이다.[1] 이 제한된 형태는 기본 블록을 분석하는 용도로 매우 유용하게 만든다.[2] 컴파일러들은 보통 분석 과정의 첫 번째로 프로그램들을 그들의 기본 블록들로 분해한다. 기본 블록들은 제어 흐름 그래프에서 정점 또는 노드의 형태를 갖는다.
정의 편집
기본 블록에 있는 코드는 다음을 갖는다:
- 하나의 엔트리 포인트, 이것은 프로그램 어디에서든 점프 명령어의 목적지인 코드가 내부에 없다는 것을 의미한다.
- 하나의 종료 포인트, 이것은 오직 마지막 명령어가 프로그램이 다른 기본 블록에 있는 코드의 실행을 시작할 수 있게 한다는 것을 의미한다.
이러한 환경 하에서, 기본 블록의 첫 번째 명령어가 실행될 때마다, 나머지 명령어들은 필연적으로 순서에 따라 정확히 한 번 실행된다.[3]
코드는 소스 코드, 어셈블리 코드 또는 다른 순차 명령어 집합일 것이다.
더 형식적으로, 순차 명령어 집합은 다음과 같다면 기본 블록을 형성한다.
- 각 위치가 지배하거나, 항상 다음 위치들의 전에 실행되는 명령어
- 순서에서 어떠한 명령어도 두 명령어들 사이를 실행할 수 없다.
이 정의는 몇몇 방식들에서, 직관적인것 보다 더 일반적이다. 예를 들면, 이것은 다른 점프들의 대상이 아닌 레이블에 대한 무조건적인 점프를 허용한다. 이 정의는 알고리즘을 설계할 때 기본 블록들이 쉽게 동작하게 만들어 주는 속성들을 상징한다.
제어가 블록의 끝에 도달한 후에 전달되는 블록을 블록의 후임자(successor)라고 하며, 블록에 들어올 때 제어가 오는 블록을 전임자(predecessor)라고 한다. 기본 블록의 시작은 한 위치 이상에서의 점프이다.
생성 알고리즘 편집
코드 목록에서 기본 블록들을 생성하는 알고리즘은 간단하다: 분석기는 코드를 스캔하고, 블록 경계를 마킹하는데, 이것은 블록을 시작하거나 끝내는 명령어이다(이 명령어들이 제어를 전달하거나 다른 지점에서 받아들이기 때문). 그 후 리스트는 간단하게 이러한 각 지점들에서 잘라지고, 기본 블록들은 남게 된다.
공식적인 정의에 따라, 이 방식이 항상 최대 기본 블록들을 생성하지는 않는다는 것에 주의하라. 하지만 이것들은 보통 충분하다(최대한의 기본 블록들이란 기본 블록의 정의를 위반하지 않으면서, 인접한 블록들을 포함하면서 확장될 수 없는 기본 블록들이다[4]).
입력: 순차 명령어 집합 (대부분 3-어드레스 코드).[5] 출력: 정확히 한 블록 안에서 각 3-어드레스 선언을 갖는 기본 블록들의 리스트.
1 단계. 코드에서 리더를 식별한다. 리더들은 다음의 세 분류에 포함되는 명령어들이다:
- 첫 번째 명령어는 리더이다.
- 조건 또는 무조건 goto/jump 명령어의 대상은 리더이다.
- 조건 또는 무조건 goto/jump 명령어의 바로 다음 명령어는 리더이다.
2 단계. 리더에서 시작해서 다음 리더까지의(다음 리더는 포함하지 않는다) 명령어들의 모든 집합은 시작하는 리더에 상응하는 기본 블록이다.
그러므로 모든 기본 블록을 리더를 갖는다.
기본 블록을 끝내는 명령어들은 다음을 포함한다:
- 직접이나 간접 모두, 조건 그리고 무조건 분기
- 호출한 프로시저로의 리턴
- 예외를 던질 수 있는 명령어들
- 만약 이것들이 반환하지 않는다는 가정 하에, 함수 호출들은 기본 블록의 끝에서 기본 블록을 끝낼 수 있다. 이러한 함수들은 예외를 던지거나 C의
longjmp그리고exit같은 특별한 호출을 하는 함수들이다. - 리턴 명령어 자신
새로운 기본 블록을 시작하는 명령어들은 다음을 포함한다:
- 프로시저 그리고 함수 엔트리 포인트들
- 점프나 분기의 대상들
- 몇몇 조건 분기들에 따라오는 "완료되지 못하는" 명령어들
- 예외를 던진 후에 따라오는 명령어들
- 예외 처리기
제어가 절대로 기본 블록의 끝에 전달될 수 없기 때문에, 몇몇 블록 경계들은 기본 블록들을 찾은 후에 수정되어야 한다는 점에 주의하라. 특히, 완료되지 못하는 조건 분기들은 반드시 쌍방 분기로 바뀌고, 예외를 던지는 함수 호출들은 반드시 무조건 점프로 뒤에 더해져야 한다. 이러한 것들은 하는 것은 다른 블록들의 시작에 레이블을 추가하는 것을 필요로 한다.
같이 보기 편집
각주 편집
- ↑ Hennessy, John L., and David A. Patterson.
- ↑ "Control Flow Analysis" by Frances E. Allen
- ↑ "Global Common Subexpression Elimination" by John Cocke
- ↑ Modern Compiler Design by Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs, and Koen G. Langendoen p320
- ↑ Compiler Principles, Techniques and Tools, Aho Sethi Ullman