제어 흐름 그래프

Control-flow graph
일부 CFG의 예:
(a) if-ten-the-den-thead
(b) a while loop
(c) 두 개의 출구가 있는 자연 루프(예: if...중간에서 깨지다; 비파괴적이지만 축소할 수 없다.
(d) 수정 불가능한 CFG: 두 개의 진입점이 있는 루프(예: 잠시 또는 루프를 위한 goto)
러스트 컴파일러가 코드 생성을 수행하기 위해 사용하는 제어 흐름 그래프.

컴퓨터 과학에서, 제어 흐름 그래프(CFG)는 실행 중에 프로그램을 통해 통과될 수 있는 모든 경로를 그래프 표기법으로 표현한 것이다.제어 흐름 그래프는 Frances E에 의해 발견되었다. 리즈 T를 주목한 앨런.[1] Prosser는 이전에 흐름 분석에 부울 연결 매트릭스를 사용했다.[2]null

CFG는 많은 컴파일러 최적화 및 정적 분석 도구에 필수적이다.null

정의

제어 흐름 그래프에서 그래프의 각 노드는 기본 블록, 즉 점프나 점프 목표가 없는 직선 코드의 일부를 나타낸다. 점프 대상이 블록을 시작하고 점프 대상이 블록을 끝낸다.방향 에지는 제어 흐름에서 점프를 나타내기 위해 사용된다.대부분의 프레젠테이션에는 두 개의 특별히 지정된 블록이 있는데, 이 블록은 제어기가 흐름 그래프에 들어가는 진입 블록과 모든 제어 흐름이 나가는 출구 블록이다.[3]null

CFG에서 시공 절차 때문에 모든 에지 A→B는 다음과 같은 특성을 갖는다.

외도(A) > 1 또는 외도(B) > 1 (또는 둘 다)[4]

따라서 CFG는 최소한 개념적으로 프로그램의 (전체) 흐름 그래프(즉, 모든 노드가 개별 명령을 나타내는 그래프)에서 시작하여 위의 술어를 변조하는 모든 에지에 대해 에지 수축(즉, 단일 출구가 있고 목적지가 죄가 있는 모든 에지 수축)을 수행함으로써 얻을 수 있다.이삭을 줍다CFG는 기본 블록을 스캔하여 프로그램에서 직접 보다 효율적으로 구성할 수 있기 때문에 이 수축 기반 알고리즘은 CFG 구성을 이해하기 위한 시각화 보조 도구 외에는 실질적인 중요성이 없다.[4]null

예

다음 코드 조각을 고려하십시오.

0: (A) t0 = read_num 1: (A) t0 = 0 2: (B) print t0 + "가 짝수일 경우." 3: (B) goto 5 4: (C) print t0 + "가 홀수일 경우." 5: (D) 종료 프로그램

위의 기본 블록은 A부터 1까지, B는 2에서 3까지, C는 4에서 D까지 4가지 입니다.특히 이 경우 A가 '엔트리블록', D가 '출구블록', 4~5호선이 점프대상이다.이 조각의 그래프는 A에서 B로, A에서 C로, B에서 D로, C에서 D로 에지를 가지고 있다.null

도달성

주요 기사:도달성

도달성은 최적화에 유용한 그래프 속성이다.null

서브그래프가 입력 블록을 포함하는 서브그래프에서 연결되지 않은 경우, 서브그래프는 실행 중에 연결할 수 없으므로, 정상적인 조건에서는 안전하게 제거할 수 있다.null

출구 블록이 진입 블록에서 접근할 수 없는 경우 무한 루프가 존재할 수 있다.무한 루프도 모두 감지할 수 있는 것은 아니므로 중지 문제를 참조하십시오.그곳에는 중지 명령도 존재할 수 있다.null

프로그래머가 명시적으로 코드화하지 않더라도 접근할 수 없는 코드와 무한 루프: 연속 전파와 연속 폴딩과 같은 최적화는 여러 개의 기본 블록을 하나로 붕괴시키고 CFG에서 가장자리가 제거되는 등 그래프의 일부를 분리할 수 있다.null

지배관계

주요 기사:도미네이터(그래프 이론)

블록 N에 도달하는 진입로의 모든 경로가 블록 M을 통과해야 하는 경우 블록 M은 블록 N을 지배한다.진입 블록이 모든 블록을 지배한다.null

반대 방향에서, N에서 출구로 가는 모든 경로가 블록 M을 통과해야 할 경우 블록 M은 블록 N을 좌표로 한다.출구 블록은 모든 블록을 포스트도밍한다.null

M이 N을 지배하면 블록 M이 즉시 블록 N을 지배하고, M이 P를 지배하고, P가 N을 지배하는 등 간섭 블록 P가 없다고 한다.즉, M은 입구에서 N까지의 모든 경로에 대한 마지막 지배인이다.각 블록에는 고유한 즉각적인 지배자가 있다.null

이와 유사하게, 즉각적인 지배자와 유사하게 즉각적인 지배자의 개념이 있다.null

도미네이터 트리는 도미네이터 관계를 나타내는 보조 데이터 구조물이다.M이 N의 즉각적인 지배자라면 Block M에서 Block N까지의 호가 있다.이 그래프는 각 블록에 고유한 즉각적인 지배자가 있기 때문에 트리다.이 나무는 입구 블록에 뿌리를 두고 있다.도미네이터 트리는 렝가워를 사용하여 효율적으로 계산할 수 있다.-타르잔의 알고리즘.null

포스트 도미네이터 트리는 도미네이터 트리와 유사하다.이 나무는 출구 블록에 뿌리를 두고 있다.null

특수 모서리

백 에지는 그래프의 깊이 우선(DFS) 통과 중에 이미 충족된 블록을 가리키는 에지다.뒤쪽 가장자리는 루프의 전형이다.null

임계 에지는 소스 블록을 떠나는 유일한 에지도, 대상 블록에 들어가는 유일한 에지도 아닌 에지다.이러한 가장자리는 분할되어야 한다. 다른 가장자리에 영향을 미치지 않고 가장자리의 연산을 삽입하기 위해 가장자리의 중간에 새로운 블록을 생성해야 한다.null

비정상 엣지는 목적지를 알 수 없는 엣지다.예외 처리 구조는 그것들을 생산할 수 있다.이러한 가장자리는 최적화를 방해하는 경향이 있다.null

불가능 에지(가짜 에지라고도 함)는 출구 블록이 모든 블록을 후분류를 하는 속성을 보존하기 위해 그래프에 추가된 에지다.그것은 절대로 통과될 수 없다.null

루프 관리

루프 헤더(루프의 진입점이라고도 함)는 루프 형성 백 에지의 대상인 도미네이터다.루프 헤더는 루프 본체의 모든 블록을 지배한다.블록은 둘 이상의 루프에 대한 루프 헤더일 수 있다.루프는 복수의 진입점을 가질 수 있으며, 이 경우 "루프 헤더"가 없다.null

블럭 M이 여러 개의 수신 에지를 가진 도미네이터이며, 그 중 일부는 백 에지(따라서 M은 루프 헤더)라고 가정한다.M을 두 블록 M과pre M으로loop 분해하는 것은 여러 개의 최적화 패스가 유리하다.M과 후면 가장자리의 내용은 M으로loop 이동하고, 나머지 가장자리는 M을pre 가리키도록 이동하며, M에서pre M으로loop 새로운 가장자리를 삽입한다(M이pre M의loop 즉각적인 지배자임).초기에는 M이pre 비어있겠지만, 루프 인바리어트 코드 동작처럼 패스하면 그것을 채울 수 있다.M은pre 루프 프리헤더라고 불리며, M은loop 루프 헤더일 것이다.null

환원성

환원 가능한 CFG는 두 개의 분리형 집합으로 분할할 수 있는 가장자리, 즉 앞쪽 가장자리와 뒤쪽 가장자리로 다음과 같이 분할할 수 있다.[5]

  • 전진 에지는 모든 노드가 엔트리 노드에서 도달할 수 있는 방향의 AC 순환 그래프를 형성한다.
  • 모든 백 에지(A, B)에 대해 노드 B는 노드 A를 지배한다.

구조화된 프로그래밍 언어는 그들이 생산하는 모든 CFG가 축소될 수 있도록 설계되는 경우가 많고 IF, FOR, WID, BREak 및 CONTENT과 같은 공통 구조화된 프로그래밍 문구는 축소 가능한 그래프를 생산한다.수정할 수 없는 그래프를 만들려면 GOTO와 같은 문장이 필요하다.해석 불가능한 그래프는 일부 컴파일러 최적화에 의해 생성될 수도 있다.null

루프 연결성

CFG의 루프 연결성은 CFG의 지정된 깊이 우선 검색 트리(DFST)에 대해 정의된다.이 DFST는 시작 노드에 뿌리를 내리고 CFG의 모든 노드를 커버해야 한다.null

노드에서 DFST 조상(자체 포함) 중 하나에 이르는 CFG의 가장자리를 백 에지라고 부른다.null

루프 연결성은 CFG의 사이클이 없는 경로에서 발견된 가장 많은 수의 백 에지 수입니다.환원 가능한 CFG에서 루프 연결성은 선택된 DFST와 독립적이다.[6][7]null

루프 연결성은 데이터 흐름 분석의 시간 복잡성에 대해 추론하기 위해 사용되어 왔다.[6]null

절차간 제어 흐름 그래프

제어 흐름 그래프는 단일 절차의 제어 흐름을 나타내는 반면, 절차 간 제어 흐름 그래프는 전체 프로그램의 제어 흐름을 나타낸다.[8]null

참고 항목

참조

  1. ^ Frances E. Allen (July 1970). "Control flow analysis". SIGPLAN Notices. 5 (7): 1–19. doi:10.1145/390013.808479.
  2. ^ Reese T. Prosser (1959). "Applications of Boolean matrices to the analysis of flow diagrams". Papers presented at the December 1–3, 1959, eastern joint IRE-AIEE-ACM computer conference. pp. 133–138.
  3. ^ Yousefi, Javad (2015). Masking wrong-successor Control Flow Errors employing data redundancy. IEEE. pp. 201–205. doi:10.1109/ICCKE.2015.7365827.
  4. ^ a b Peri L. Tarr; Alexander L. Wolf (2011). Engineering of Software: The Continuing Contributions of Leon J. Osterweil. Springer Science & Business Media. p. 58. ISBN 978-3-642-19823-6.
  5. ^ http://www.cs.colostate.edu/~mstrout/CS553Fall06/슬라이드/렉처13-control.pdf[데드링크]
  6. ^ a b Kam, John B.; Ullman, Jeffrey D. (1976-01-01). "Global Data Flow Analysis and Iterative Algorithms". Journal of the ACM. 23 (1): 158–171. doi:10.1145/321921.321938. ISSN 0004-5411.
  7. ^ Offner, Carl. "Notes on Graph Algorithms Used in Optimizing Compilers" (PDF). Retrieved 13 April 2018.
  8. ^ "Control Flow Analysis" (PDF). 2016.

외부 링크

예