제어 흐름 그래프
제어 흐름 그래프(영어: Control-flow graph, CFG)는 프로그램이 실행 중에 횡단할 수 있는 모든 경로를 그래프 표기법을 사용하여 표현한 것이다.
CFG는 많은 컴파일러 최적화와 정적 프로그램 분석 툴에서 핵심 요소이다.
정의
편집CFG에서 그래프의 각 노드(node)는 기본 블록 (basic block)을 표현한다. 즉, 점프가 없는 코드의 직선 조각이다. (점프는 블록의 시작과 끝을 나눈다.) 방향성의 엣지(edge)들은 제어 흐름에서 점프를 나타낸다. 대부분의 경우에 흐름 그래프가 진입하는 엔트리 블록과 모든 제어 흐름이 떠나는 "종료 블록"이라는 두 특별히 고안된 블록을 지닌다.
이것의 구조 절차 때문에 (사소하지 않은 CFG에서) 모든 A→B 엣지는 다음의 속성을 갖는다.
- 출력 차수 (outdegree) (A) > 1 또는 진입차수(indegree) (B) > 1 (또는 둘 다).[1]
그러므로 CFG는 적어도 개념적으로는 프로그램의 흐름 그래프(모든 노드가 각각의 명령어를 표현하는 그래프)에서 시작하고, 위의 술어를 조작하는 모든 엣지 수축(edge contraction)을 수행함으로써 (즉, 소스가 단일 종료를 갖거나 목적지가 단일 엔트리인 모든 엣지를 줄이며) 얻어질 수 있다. 이 수축 기반 알고리즘은 CFG 구조를 시각화하는데 도움을 준다는 점 외에는 실용적인 중요성은 없다.
예시
편집다음의 코드 부분을 보자.
0: (A) t0 = read_num 1: (A) if t0 mod 2 == 0 2: (B) print t0 + " is even." 3: (B) goto 5 4: (C) print t0 + " is odd." 5: (D) end program
위에서, 우리는 4개의 기본 블록을 갖는다. A는 0부터 1, B는 2부터 3, C는 4 그리고 D는 5다. 특히, A의 경우 엔트리 블록이며, D의 경우 종료 블록이다. 그리고 라인 4와 5는 점프 대상이다. 이 코드의 그래프는 A부터 B, A부터 C, B부터 D 그리고 C부터 D까지의 엣지를 갖는다.
도달 가능성
편집도달 가능성은 최적화 시에 유용한 그래프 속성이다.
만약 서브그래프가 엔트리 블록에 포함된 서브 그래프와 연결되지 않았다면, 이 서브그래프는 실행 중에 도달할 수 없으며, 일반 조건에서 안전하게 제거될 수 있다.
만약 종료 블록이 엔트리 블록에서 도달 불가능하다면, 무한 루프가 존재할 수 있다. 정지 문제처럼 모든 무한 루프가 탐지되는 것은 아니다. 또한 거기에 정지 순서도 존재할 수 있다.
도달 불가능한 코드와 무한 루프는 프로그래머가 명시적으로 그것을 코딩하지 않았어도 생길 수 있다. 상수 전파와 상수 폴딩 같은 점프 스레딩에 의한 최적화는 엣지를 CFG에서 제거함으로써 여러 기본 블록을 하나로 붕괴시킬 수 있다.
지배 관계
편집만약 모든 경로에서 블록 N에 도달하는 엔트리가 블록 M을 거쳐야 한다면 블록 M은 블록 N을 지배한다.
역방향으로, 만약 블록 N에서 종료 까지의 모든 경로가 블록 M을 거쳐야 한다면, 블록 M은 블록 N을 후지배(postdominate)한다.
다른말로 해서, M은 엔트리부터 N까지의 모든 경로에서 마지막으로 지배한다. 각 블록들은 고유한 즉각적 (immediate) 지배관계를 갖는다.
비슷하게, 즉각적 지배와 즉각적 후지배도 존재한다.
지배자 트리 (dominator tree)는 지배 관계를 묘사하는 보조적인 데이터 구조이다. 만약 블록 M이 블록 N을 즉각적으로 지배한다면, 블록 M부터 블록 N까지 원(arc)이 생긴다. 이 그래프는 각 블록이 고유한 즉각적 지배자를 갖은 이후로 트리가 된다. 이 트리는 엔트리 블록부터 갈라져 나온다. Lengauer-Tarjan's algorithm을 사용해 효율적으로 계산될 수 있다.
후지배자 트리 (postdominator tree)는 지배자 트리의 유사체이다. 이 트리는 종료 블록부터 갈라져 나온다.
특별한 엣지
편집백 엣지 (back edge)는 이미 DFS 동안 만났던 블록에 대한 포인터이다. 백 엣지는 대표적인 루프이다.
크리티컬 엣지 (critical edge)는 소스 블록을 떠나는 유익한 엣지도 아니고, 목적 블록에 도달하는 유일한 엣지도 아니다. 이러한 엣지들은 반드시 쪼개져야 한다. 즉, 다른 엣지들에 대한 영향 없이 계산을 삽입하기 위하여 새로운 블록이 엣지 중간에 생성되어야 한다.
불가능한 엣지 (impossible edge 또는 fake edge)는 종료 블록이 모든 블록들을 후지배하는 속성을 보존하기 위해 단독으로 추가된 엣지이다. 이것은 영원히 지나갈 수 없다.
루프 관리
편집루프 헤더(종종 루프의 엔트리 포인트라고 불리는)는 루프를 형성하는 백 엣지의 대상인 지배자이다. 루프 헤더는 루프 몸체의 모든 블록들을 지배한다. 블록은 하나 이상의 루프를 위한 루프 헤더이다. 루프 헤더가 없는 경우 루프는 여러 엔트리 포인트를 가질 수 있다.
블록 M이 여러 들어오는 엣지들의 지배자이며, 몇몇은 백 엣지라고 가정해 보자. (즉, M은 루프 헤더이다.) M을 Mpre 와 Mloop라는 두 블록으로 쪼개는 것은 여러 최적화된 경로에 이득이 된다. M의 내용과 백 엣지들은 Mloop가 되며, 나머지 엣지들은 Mpre가 되고, Mpre 에서 Mloop 까지의 새로운 엣지가 삽입된다. (즉, Mpre는 Mloop의 즉각적인 지배자이다.) 시작할 때, Mpre는 비어 있겠지만, loop-invariant code motion 같은 경로들은 이것을 덧붙일 수 있다. Mpre는 loop pre-header라고도 불리며, Mloop 는 루프 헤더가 될 것이다.
같이 보기
편집노트
편집- ↑ Peri L. Tarr; Alexander L. Wolf (2011). 《Engineering of Software: The Continuing Contributions of Leon J. Osterweil》. Springer Science & Business Media. 58쪽. ISBN 978-3-642-19823-6.
외부 링크
편집- The Machine-SUIF Control Flow Graph Library
- GNU Compiler Collection Internals
- Paper "Infrastructure for Profile Driven Optimizations in GCC Compiler" by Zdeněk Dvořák et al.
- 예시
- http://compilers.cs.ucla.edu/avrora/cfg.html Archived 2011년 8월 25일 - 웨이백 머신