기본 블록

Basic block

컴파일러 구조에서 기본 블록은 엔트리 이외에는 브랜치가 없고 [1][2]출구 이외에는 브랜치가 없는 직선 코드 시퀀스입니다.이 제한된 형태는 기본 블록을 분석하기 [3]쉽게 만듭니다.컴파일러는 보통 분석 프로세스의 첫 번째 단계로 프로그램을 기본 블록으로 분해합니다.기본 블록은 제어 흐름 그래프에서 정점 또는 노드를 형성합니다.

정의.

기본 블록의 코드는 다음과 같습니다.

  • 하나의 진입점. 즉, 그 안에 어떤 코드도 프로그램의 어느 곳에서도 점프 명령의 목적지가 되지 않습니다.
  • 하나의 종료 지점. 마지막 명령만 다른 기본 블록에서 코드 실행을 시작할 수 있습니다.

이러한 상황에서 기본 블록의 첫 번째 명령이 실행될 때마다 나머지 명령은 정확히 한 번 순서대로 [4][5]실행되어야 한다.

코드는 소스 코드, 어셈블리 코드 또는 기타 일련의 명령일 수 있습니다.

좀 더 형식적으로, 다음과 같은 경우 일련의 명령이 기본 블록을 형성합니다.

  • 각 위치의 명령은 이후의 위치에 있는 모든 명령을 지배하거나 항상 먼저 실행합니다.
  • 다른 명령어는 시퀀스의 두 명령 사이에서 실행되지 않습니다.

이 정의는 어떤 면에서는 직관적인 정의보다 더 일반적이다.예를 들어, 다른 점프의 표적이 아닌 라벨로 무조건 점프할 수 있다.이 정의는 알고리즘을 구성할 때 기본 블록을 사용하기 쉽게 하는 속성을 구체화합니다.

블록의 끝에 도달한 후 제어가 전송될 수 있는 블록을 블록의 후속 블록이라고 하며, 블록에 들어갈 때 제어가 이루어지는 블록을 블록의 이전 블록이라고 합니다.기본 블록의 시작은 둘 이상의 위치에서 점프할 수 있습니다.

생성 알고리즘

코드 목록에서 기본 블록을 생성하는 알고리즘은 간단합니다. 분석기가 코드를 스캔하여 블록 경계를 표시합니다. 블록 경계는 다른 지점에서 제어를 전송하거나 받아들이기 때문에 블록을 시작하거나 종료할 수 있는 명령입니다.그 후, 리스트는 각 포인트에서 간단하게 「컷」되고, 기본 블록은 남습니다.

이 방법은 형식적인 정의에 의해 항상 최대 기본 블록을 생성하는 것은 아니지만 일반적으로 충분합니다(최대 기본 블록은 기본[6] 블록의 정의를 위반하지 않고 인접 블록을 포함함으로써 확장할 수 없는 기본 블록입니다).

입력: 일련의 명령(대부분의 3주소 [7]코드).
출력: 각 3개의 주소 문이 정확히1개의 블록에 있는 기본 블록의 리스트.

  1. 코드의 리더를 특정합니다.리더는 다음 3가지 카테고리 중 하나에 해당하는 명령입니다.
    1. 첫 번째 지시입니다.첫 번째 지시는 리더입니다.
    2. 조건부 또는 무조건 goto/jump 명령의 대상은 리더입니다.
    3. 조건부 또는 무조건적인 goto/jump 명령 뒤에 이어지는 명령이 리더입니다.
  2. 리더에서 시작하여 다음 리더를 포함하거나 포함하지 않는 모든 다음 명령 집합이 출발 리더에 대응하는 기본 블록입니다.따라서 모든 기본 블록에는 리더가 있습니다.

기본 블록을 종료하는 순서는 다음과 같습니다.

  • 직접적 및 간접적 조건 없는 분기
  • 호출 프로시저로 돌아갑니다.
  • 예외를 발생시킬 수 있는 지침
  • 함수 콜은 C 및 C와 같은 예외를 발생시키는 함수나 특별한 콜을 반환할 수 없는 경우 기본 블록의 끝에 있을 수 있습니다.exit;
  • 반환 지시서 자체입니다.

새로운 기본 블록을 시작하는 순서는 다음과 같습니다.

  • 절차 및 기능 진입점
  • 점프 또는 나뭇가지 대상
  • 일부 조건부 분기에 따른 "추락" 지침
  • 예외를 발생시키는 지침에 따른 지침
  • 예외 핸들러

제어는 기본 블록의 끝을 통과할 수 없으므로 기본 블록을 찾은 후 일부 블록 경계를 수정해야 할 수 있습니다.특히 폴스루 조건부 브랜치는 양방향 브랜치로 변경해야 하며 예외를 던지는 함수 호출은 그 뒤에 무조건 점프를 추가해야 합니다.이를 수행하려면 다른 블록의 시작 부분에 레이블을 추가해야 할 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ 헤네시, 존 L.; 데이비드 A.패터슨.컴퓨터 아키텍처: 정량적 접근법.Elsevier, 2011년
  2. ^ Cooper, Keith Daniel; Torczon, Linda (2012). Engineering a compiler (2nd ed.). Amsterdam: Elsevier/Morgan Kaufmann. p. 231. ISBN 978-0120884780. OCLC 714113472.
  3. ^ Frances E의 "Control Flow Analysis".알렌.
  4. ^ Yousefi, Javad (2015). Masking wrong-successor Control Flow Errors employing data redundancy. IEEE. pp. 201–205. doi:10.1109/ICCKE.2015.7365827.
  5. ^ John Coke의 "글로벌 공통 하위 표현 제거"입니다.
  6. ^ Dick Grune, Henri E. Bal, Ceriel J. H. Jacobs 및 Koen G. Langendoen, 페이지 320에 의한 Modern Compiler Design.
  7. ^ 컴파일러의 원리, 기술 및 도구, Aho Sethi Ullman.

외부 링크