저번 글에서 dataflow analysis 를 알아봤었다.
이번에는 프로그램의 분기 구조를 분석하는 control flow analysis를 알아보자.
Dominator
이전 글에서 CFG는 BB를 노드로 가지는 그래프라고 했었다.
Entry 부터 어떤 노드 y까지 갈 수 있는 모든 길에 x노드가 있다면 x가 y를 dominate한다고 말한다.
이 dominator에는 3가지 속성이 있다.
1. 모든 BB는 자기자신을 dominate한다.
2. x가 y를 dominate하고 y가 z를 dominate하면 x가 z도 dominate한다.
3. x와 y가 둘다 z를 dominate하면, x와 y사이 dominate관계가 있다.
Dominator Tree
BB간의 dominate관계를 그래프로 나타낸 것이다.
Dominator Analysis
먼저 아래 표기법을 하나 알아야한다.
dom(BB) : BB를 dominate하는 BB들의 집합
각 BB에 대해 dom(BB0를 분석하는 방법은 아래와 같다.
일단 초기화는 아래처럼 진행한다.
dom(entry BB) : entry BB
dom(나머지 BB) : 모든 노드
기본적으로 모든 노드가 dominate한다고 가정하고, 여기서 실제 아닌 BB들은 dom()에서 제거하는 방식으로 분석한다.
어떤 BB의 모든 부모 노드들을 dominate하는 블럭이어야 이 BB를 dominate하는 것이다.
분석의 예시이다.
처음에는 모든 BB로 초기화가 되었지만 아닌 것들이 제거되면서 정답을 찾게 된다.
Natural Loop
컴파일러가 최적화를 할 때는 루프를 파악하는 것이 중요하다.
natural loop
natural loop는 loop의 진입점이 하나인 루프를 얘기한다.
몇가지 용어가 있다.
header :
loop에는 header라는 BB가 있는데 header를 지나야만 loop로 들어갈 수 있고, 루프 안의 모든 블럭을 dominate한다.
backedge :
backedge라는 것은 u → v 라는 BB관계가 있을 때, v가 u를 dominate하면 이 화살표는 backedge가 된다.
쉽게 얘기하면 자식에서 부모로 가는 화살표를 얘기한다.
natural loop를 찾는 방법
step1. BB들의 dominate관계를 파악한다.
step2. backedge들을 찾는다.
step3. 각각의 backedge와 연관된 natural loop를 찾는다.
step1은 글의 초반에서 다뤘던 방법대로 하면 된다.
step2는 CFG에서 DFS를 적용해 backedge를 찾으면 된다.
모든 u → v backedge에 대해 v가 u를 dominate하는지 체크한다.
step3에서는 u → v 인 backedge에 대해 v가 header가 된다.
이 header를 지우고 이 BB에서 나오고 들어가는 edge도 지운다.
이 때 u노드에 도달 가능한 BB들을 찾는다.
이 노드들과 u,v노드를 합쳐서 natural loop가 된다.
최적화를 위해서 같은 header를 가진 loop는 합친다.
Exit edge, Preheader
loop를 구성하는 모든 노드에 대해, 노드에서 나가는 edge가 loop에 있지 않은 BB를 가리킬 때, 이 edge는 exit edge라고 한다.
preheader는 header이전에 먼저 실행되도록 만드는 BB이다.
header로 들어가는 edge를 preheader를 가리키도록 만들어서 생성한다.
loop 실행전에 항상 실행되지만 loop동안은 실행되지 않는다.
header는 loop의 사이클마다 실행된다는 점에서 다르다.
loop-invariant computation
loop invariant computation은 루프내에서 불변하는 계산을 얘기한다.
아래 사진의 e=3 부분은 loop을 돈다고 변화가 생기는 부분이 아니니 매 루프마다 계속 실행하기보다 preheader로 이동하는게 낫다.
하지만 아래와 같은 상황에서는 약간의 문제가 발생할 수 있다.
위 그림에서 loop 전에 e=1 라는 코드가 있었다고 하자.
만약 loop이 계속 왼쪽경로로만 돈다면, e=3부분은 한번도 실행되지 않아야한다. 즉 e는 계속 1이다.
하지만 preheader로 옮긴다면 한번 실행이 되게 된다. 이때는 e=3이 된다.
따라서
loop-invariant code라고 항상 preheader로 옮길 수 있는 것은 아니다.
detecting loop invariant
어떤 A = B + C 라는 코드가 invariant한지 판단하는 조건을 알아보자.
B,C의 모든 reaching definition들이 loop 바깥에 있다면 B,C의 값은 loop을 돌면서 바뀌지 않고, 따라서 A의 값도 변하지 않는다.
또는 B,C의 reaching definition이 유일하고, 이것이 루프안의 loop-invariant코드에 있었다면 위 식은 invariant하다.
이를 반복하여 상태가 바뀌지 않을 때까지 진행한다.
아래 예시를 통해 확인해보자.
1. B,C,E는 invariant하다.
2. B,C에 의해 A도 invariant하다.
3. A에 의해 F도 invariant하다.
4. D=A+1에서 A의 reaching definition은 분기 안의 왼쪽, header위의 선언(예 : A =1)로 총 2개이다.
모든 reaching definition이 loop 바깥에 있지 않으므로 D는 invariant하지 않다.
Conditions for Code Motion
위에서 얘기했듯 모든 invaritant한 코드를 옮길 수 있는 것은 아니다.
d=a+b에서
1. a,b가 상수거나
2. a,b가 루프밖에서 정의되었거나
3. a,b가 loop-invariant여야만 옮길 수 있다.
하지만 이 조건이 전부는 아니다. 다른 조건도 있어야한다.
아래 4가지 예시에서 빨간색으로 되어있는 코드를 옮길 수 있는지 살펴보면서 알아보자.
1번 예시는 preheader를 만들어 그곳으로 옮길 수 있다.
2번째 예시에서는 preheader로 올렸다면, 만약 처음부터 조건문의 조건을 충족하지 않아서 오른쪽 경로로 돌아갈 경우 이 부분이 한번은 무조건 실행되게 된다.
pre header로 올리기 전에는 d=0이었지만 올리고 난 후는 d=a+b로 값이 바뀌는 것이다.
따라서 옮기면 안된다.
3번 예시는 두번째 loop부터 M[i]=0이 되어버린다.
4번째 예시도 첫 실행시 M[j]=0이 된다.
따라서 2,3,4번 케이스들에서는 함부로 위치를 변경할 수 없다.
그래서 아래의 추가 조건들이 필요하다.
1. 해당 코드가 모든 loop exit을 dominate해야한다. (2번예시)
2. 해당 정의는 loop안에 한번만 있어야한다. (3번예시)
3. loop전에 d가 live하면 안된다. (4번예시)
aggressive optimization
추가 조건 1번을 조금 더 공격적으로 최적화를 한다면,
만약 d=a+b에서 loop이후 d가 live하지 않을 때는 이 코드가 모든 exit을 dominate하지 않아도 preheader로 옮길 수 있다.
또 while문 같은 경우
loop가 한번도 돌지 않는 경우를 미리 빼버려 loop에 대한 최적화의 기회를 늘릴 수 있다.
unreachable code elimination
도달가능하지 않는 BB는 지워버리는 최적화도 가능하다.
loop unrolling
간단히 설명하면 loop안의 코드를 두번 연달아 작성하고 loop의 반복횟수는 반으로 줄이는 것이라고 생각하면된다.
이게 무슨 쓸모인가 싶지만, branch횟수를 줄이고 CPU레벨에서 명령어 실행시 병렬성의 측면에서 더 효율적이다.
세 가지 type가 있다.
type1,2는 loop를 들어가기 전에 몇번 반복될 지 아는 경우이다.
만약 코드가 홀수번 실행되어야하는데 2개를 묶어 loop을 줄이면 마지막1번은 추가로 실행이 필요하다.
type1은 나머지가 없는 경우, type2는 나머지가 있는 경우이다.
type3는 while처럼 몇번 실행될지 정확히 모를때이다.
아래 그림을 보면 type1, type2는 모두 branch의 횟수가 줄어든 것을 볼 수 있다.
하지만 type3는 unroll을 해도 branch를 줄일 수 없다.
이 때는 다른 변수를 사용해 data dependency를 줄인다.
data dependency가 무엇인지는 컴퓨터 구조론에서 더 자세히 배울 수 있다.
Unrolling and Instruction Scheduling
요즘 cpu는 메모리와 ALU가 병렬적으로 여러개 있다.
아래처럼 loop unrolling을 하지 않으면 loop한번에 8사이클이 걸린다.
(각 명령어는 2사이클이 걸린다고 가정)
하지만 2개를 묶어 loop unrolling하면
2번의 실행에 10사이클만 걸린다.
Profile based Optimization
branch에서 조건에 따라 코드가 실행될지 안될지 결정할 때 이 비율이 다를 수 있다.
이때 메모리 상에 주로 실행될 분기의 BB가 연달아 나오는 것이 더 이득이다.
따라서 take(실행)될 확률이 높은 BB가 연달아 나오도록 조정을 하여 최적화를 할 수 있다.
'CS > 컴파일러' 카테고리의 다른 글
| [컴파일러 이론] 13. Memory Allocation (1) | 2026.01.06 |
|---|---|
| [컴파일러 이론] 12. register allocation (0) | 2026.01.04 |
| [컴파일러 이론] 10. Dataflow Analysis (1) | 2025.12.31 |
| [컴파일러 이론] 9. Code Generation - Stack Machine (1) | 2025.12.29 |
| [컴파일러 이론] 8. Code Generation - Activation Record, stack, heap (1) | 2025.12.27 |