[Control Flow Analysis] - Natural Loop란?

컴파일러가 기계어 코드를 만들어 내기까지의 단계에는 Lexical Analysis, Syntax Analysis, Semantic Analysis, IR Generation, IR Optimization, Code Generation, Optimization이 있다.

Optimization 단계의 경우 최종적으로 만들어낸 기계어 코드를 바탕으로 최적화를 시키는데

예를 들어, Control Flow Analysis과 Data Flow Analysis을 바탕으로 최적화를 진행시킨다. 

여기서 Data Flow Analysis의 경우 내가 잘 모르기때문에 일단 패스할 예정 

(공부해서 추가할거임) 

Control Flow Analysis의 경우 프로그램의 제어흐름을 분석하는 것을 의미한다. 

그럼 컴파일러는 Control Flow Analysis 기술을 사용해서 어떻게 최적화를 시키느냐 

일단 최적화라는 단어의 의미는 최적화를 진행하기 전, 후의 결과가 같으면서도 코드의 성능을 높이는 것이다. 

즉, 불필요한 구문을 제거함으로써 좀 더 효율적인 기계어코드를 만들어 냄을 시사함.

(주로 Loop문을 처리, data flow analysis의 따라 statement도 최적화를 시킨다.)

일단 CFA를 바탕으로 최적화를 진행시키기 위해서는 코드를 Line By Line으로 최적화를 시키는 것은 불가능하여 

Basic Block을 바탕으로 CFA를 진행한다. 

Basic Block이란 엔트리외에는 들어오는 분기가 없고, 출구 외에는 나가는 분기가 없는 직선코드를 의미한다.

Basic Block 단위로 만들어낸 코드를 CFA를 바탕으로 기존 코드의 Natural Loop를 최적화 시킨다. 

Natural Loop란? 일단 natural loop가 뭔지 이해하기 위해서는 Loop가 뭔지 알고 넘어가야 한다. 
loop란 우리가 흔히 아는 DO, while, for, goto를 의미한다. 그리고 single entry point를 가지고 있으며 edge가 최소한 하나 이상의 사이클은 형성되어야 한다. 

그럼 Natural Loop란 loop가 중간부터 시작하지 않으며 단일 entry point를 가진다. 그리고 이 entry point node(header)가 그아래 형성된 모든 노드를 dominate(지배)함을 의미한다. 
그러나 이 지배관계만으로 natural loop의 조건으로 판단하지 않는다.

그 이유는 loop의 핵심인 엔트리 포인트로 복귀하는 것이 없기 때문이다.

그래서 이 지배개념과 더불어 loop의 entry point로 다시 진입할 수 있게 해주는 Back Edge가 구성되어 있는 것을 Natural Loop라고 부른다. Natural Loop의 특징으로 A가 B를 지배하고 B가 C를 지배하면 => A는 C를 지배하게 되는 상속적인 개념이 포함된다. (goto문은 중간부터 시작할 확률이 높아 Natural Loop문이 아니기 때문에 컴파일러가 최적화 단계에서 goto는 최적화 시키지 않는다.)

figure 1.1

위 사진은 Natural Loop이다.

figure 1.2

위의 사진인 natual loop가 아니다. 

그이유는 node h가 node b를 지배하지 않는다.

그이유는 지배관계라는 개념을 다시 한번 생각해 보면 되는데 

지배관계의 기본적인 정의는 노드 B로 가는 모든 경로가 노드 H를 거쳐야 하는데 노드 C -> 노드 D -> 노드 B로 갈 수 있는 경로가 있기때문에 h doms b로 치지 않는다.