목차
2023학년도 2학기 충남대학교 조은선 교수님의 컴파일러개론 수업 정리자료입니다.
컴파일러 후반부.에서
기계와 직접적으로 관련이 없지만 컴파일러 과정에서 빈번하게 일어나는 단계 중 하나가 최적화.
Control flow analysis/optimization과 Dataflow analysis/optimization을 살펴보자.
📁 Optimization
최적화란 주어진 입력 프로그램과 의미적으로 동등하면서 좀 더 효율적인 코드로 바꾸는 작업을 말한다.
이때 효율적이라는 것은 실행시간이 짧고, 기억장소 요구량이 최소화되는 것이다.
최적화에서 핵심은 기본적으로 의미적으로 동등한 코드를 만드는 것. 이를 위해서 분석(analysis)를 이용한다. 분석을 통해 코드가 동등함이 보장된 이후에 계산의 횟수를 줄이거나 보다 빠른 명령을 사용하는 방법으로 최적화를 진행한다.
최적화 종류는 Control flow와 Data flow로 나눌 수 있으며, 그외에도 Inter basic block(local) optimization과 inter basic block(global) optimization으로 나누거나 cyclic(loop) code optimization과 acyclic optimization으로 나누는 방법도 있다.
📁 Control Flow Analysis
Control flow란 프로그램에서의 실행 순서를 말한다. 일반적으로는 pc를 1씩 증가시켜 갱신하는 방식으로 순서대로 실행하는데, 분기가 발생하면 순서를 뛰어넘어 이동하기도 한다.
static control flow란 컴파일러가 수행하는 작업(?)으로, 프로그램을 눈으로 보고 최대한 뽑아낼 수 잇ㄴ느 정보를 말함.
dynamic control flow란 실제로 실행시켜서 분기가 발생하면 true에 해당하는 쪽만 고려함.
즉 dynamic control flow의 경우 프로그램이 단일 path로 이루어지는 반면,
static control flow의 경우 input값을 모르기 때문에 분기가 발생하면 분기로 나누어지는 경우를 모두 고려해야한다.
static control flow의 경우, 분기로 나눠진 경우 중 1000번에 한번 될까말까 한 분기의 경우가 worst case이더라도 이를 전부 고려해야한다.
static control flow에서 나타나는 것처럼 프로그램을 실행하지 않고 실제 분기방향과 관계없이 도출되는 성질을 정적 성질(static property)이라고 한다.
CFA(Control Flow Analysis)란 코드의 분기 구조 전체를 분석해서 그래프형태의 CFG(Control Flow Graph)로 나타내고, 여기서 정적 성질을 도출해서 코드를 최적화하는 것이 목표이다.
🌱 Basic Blocks(BB)
CFG를 그리는 가장 쉬운 방법은 모든 명령마다 노드를 만들고 그 사이에 엣지를 넣는 방법. 하지만 노드 수가 너무 많아지고, 분기를 나타내기 어려움.
이때 제어흐름이 들어와서 나가기 전까지의 노드와 엣지 묶음에 분기가 없다면, 이 부분을 Basic Block이라고 한다.
즉 Basic Blocks란 동일한 execution condition을 적용받는 instruction의 묶음을 말한다. 노드 하나하나, instruction 하나하나도 basic block.
basic block 안의 초반 instruction이 실행되면, 후반 instruction도 무조건 실행이 보장된다.
그래서 운명공동체.
이때 basic block 한 instruction마다 쪼개면 노드가 너무 많아지고 복잡해진다. 오버헤드가 커짐.
그래서 basic block을 최대한 크게 만들자 한게 Maximal basic block.
Step1. BB의 첫 instruction인 leader를 구한다. 이때 leader는 프로그램의 시작 instruction이나, Branch의 target instruction이나, Branch 직후의 instruction 등이 될 수 있다.
Step2. 다음 leader 이전까지의 모든 코드를 구한다.
예를 들어 다음과 같은 조건이 있다.
L1: r7 = [r8]
L2: r1 = r2 + r3
L3: beq r1, 0, L10
L4: r4 = r5 * r6
L5: r1 = r1 + 1
L6: beq r1 100 L2
L7: beq r2 100 L10
L8: r5 = r9 + 1
L9: r7 = r7 - 3
L10: r9 = [r3]
L11: [r9] = r1
먼저 leader를 구해보자
프로그램의 시작 instruction : L1
Branch의 target instruction : L10, L2
Branch 직후의 instructin : L4, L7, L8
leader를 기준으로 instruction을 나누면 다음과 같이 구할 수 있다.
BB : , <l2, l3="">, <l4, l5,="" l6="">, , <l8, l9="">, <l10, l11=""></l10,></l8,></l4,></l2,>
beq x y L 명령어는 x와 y가 동일하면 L로 점프하라는 의미이다.
🌱 Control Flow Graph(CFG)
CFG(Control Flow Graph)란 node가 BB이고 edge가 이들의 수행 순서를 나타내는 그래프를 말한다. 즉 분기 등으로 연결된 두 BB 사이에는 edge가 존재한다.
일반적으로 CFG는 컴파일러마다 형태가 다양하지만, 대부분 2개의 추가(virtual) 노드를 도입한다.
- Entry node
- Exit node
예를 들어 CFG를 그려보자.
먼저 leader와 BB를 통해 노드를 구할 수 있다.
이후 순서에 따라 아래로 향하는 edge를 먼저 그려주고, 이후 분기가 나올때마다 필요한 연결을 edge로 이어준다.
GCC에서의 예시를 살펴보자.
왼쪽의 코드는 x라는 파일이름을 가진 일반적인 c코드이다.
이를 BB로 나눌 땐 일반적으로 then과 else 파트로 나누어진다. 그리고 각 블럭이 끝나면 BB5로 merge된다.
이때 then 파트를 실행하게 된다면 gotoBB5가 꼭 필요하다. 없다면 else파트까지 실행하게 될 것이다.
BB2를 보면 초반 코드 외에도 if문까지 들어간다. 즉 BB2의 마지막 코드는 branch여야한다.
실제로 gcc를 돌리면 오른쪽과 같이 .cfg로 끝나는 파일을 얻을 수 있다. 위 그림에 나와있는 x.c 코드는 몇가지 변수 초기화 부분이 생략되어있다.
어셈블리 코드에 대한 CFG 사례를 살펴보면, 이것도 또한 노드와 엣지가 존재하는 비슷한 형태임을 확인할 수 있다.
Weighted CFG
프로그램을 여러번 돌려보고 빈도 등의 결과를 얻는 작업을 Profiling(프로파일링)이라고 하는데, 이런 작업처럼 dynamic control flow가 필요한 경우가 있다.
Control flow profiling에는 다음과 같은 종류가 있다.
edge profile : 각 edge가 몇번씩 실행되는지를 파악한다.
block profile : 각 block이 몇번씩 실행되는지를 파악한다.
path profile : 특정 path가 몇번씩 실행되는지를 파악한다.
위 그림은 edge profile의 예시이다.
이런 프로파일링 결과를 CFG에 annotation으로 붙인 그래프를 Weighted CFG라고 한다.
위 예시의 경우 전체 프로파일링을 20번 실행해보았고, 각 edge가 몇번씩 실행되었는지 파악하여 annotation으로 붙였다.
만약 분기 결과 자주 일어나는 일이 있고 잘 일어나지 않은 일이 있을 때, 자주 일어나는 상황에 대해 효과적인 최적화를 할 수 있다. 예를들어 BB5로 가는 경우가 999, BB6으로 가는경우가 1인데 BB5와 BB6을 최적화할 때 둘 사이의 trade-off가 발생할 때 BB5에 더 우선순위를 두고 최적화하기로 결정할 수 있다. loop와 같은 경우가 있다.
📝 문제 풀어보기
Lbegin:t0 = i < 100
L1: t1 = NEG i
L2: cjump t1 Lend1
L3: t2 = c
L4: t3 = NEG t2
L5: cjump t3 Lend2
L6: t4 = d
L7: t5 = NEG t4
L8: cjump t5 Lend3
L9: t4 = b
L10: a = t4
Lend3: skip
Lend2: jump Lbegin
Lend1: skip
다음 코드에서 basic block 들을 구하시오.
