목차
2023학년도 2학기 충남대학교 조은선 교수님의 컴파일러개론 수업 정리자료입니다.
📁 Acyclic Code Optimization
Acyclic Code란 Loop가 없는 코드를 말하며, 분석 및 최적화가 상대적으로 쉽다.
Acyclic code optimization의 종류에는 두 가지가 있다.
1. Inner basic block opt. = Intra opt. = Local opt.
부분적인 관점(단일 block 내)에서, 즉 basic block 내부에서 비효율적인 코드를 구분해내고 좀 더 효율적인 코드로 개선하는 최적화를 말한다.
2. Inter-basic block opt. = Global opt.
basic block 간의 관계를 분석하고 이를 고려하는 최적화를 말한다.
🌱 Inner Basic Block Optimization
1. Common subexpression elimination
공통된 부분이 반복해서 나타나는 경우 한 번만 계산한다.
2. Algebraic simplification
수학적인 대수 법칙을 이용해서 식을 간소화시킨다.
예를 들면 다음과 같은 경우가 있다.
x = y + 0; 혹은 x = 1 * y; >>> x = y;
t1 = 4 * j +1; t7 = t1 - 4 * j; >>> t1 = 4 * j + 1; t7 = 1;
3. Strength reduction
같은 의미를 가지면서 좀 더 비용이 적은 연산자로 바꾼다.
예를 들면 다음과 같은 경우가 있다.
하지만 이렇게 표현하면 코드 상의 가독성이 떨어진다. 때문에 프로그래머가 프로그래밍을 할 때는 왼쪽처럼 코드를 작성하되, 컴파일러가 컴파일 할 때 오른쪽과 같이 형태를 바꾸어주는 방식을 사용한다.
4. Constant folding / propagation
컴파일러가 컴파일 시간에 알 수 있는 정보를 최대한 활용하여 미리 할 수 있는 계산은 미리 한다는 의미로, 상수를 folding 및 propagation한다.
folding이란 컴파일 시간에 상수식을 직접 계산하여 그 결과를 필요한 곳에 사용하는 것을 말한다.
propagation이란 고정된 값을 가지는 변수를 상수로 대체하는 것을 말한다.
위와 같이 folding 및 propagation을 수행할 수 있고, 이를 코드 전문 내에서 더이상 propagation 및 folding할 수 없을때까지 반복 수행한다.
🌱 Inter-Basic Block Optimization
두가지 최적화 방버이 있다.
1. Global application of inner-basic block optimization
Iner basic block 최적화 방법과 유사하다.
1-1. Global common subexpression elimination
basic block 간에 나타나는 공통 부분식에 대해서 한번만 계산한다.
오른쪽 그림의 t와 같이, 코드 내에서 변하지 않을 것 같은 expression을 임시변수에 할당하는 방식을 일반적으로 많이 사용한다.
y와 z가 중간에 변하지 않는 다는것이 확인이 돼야 위처럼 변환할 수 있기 때문에, 많은 분석이 필요하다.
1-2. Global constant folding / propagation
변수의 정의와 사용이 서로 다른 block에 걸쳐 있는 경우에 대해서 도 상수를 인식하여, basic block 간 상수 폴딩과 전파가 가능하다.
첫번째 과정에서는 x자리에 1을 넣는 propagation이 수행되었고,
두번째 과정에서는 1*2를 계산하는 folding과 t자리에 2를 넣는 propagation이 수행되었으며, 추가로 2==2는 항상 true이므로 이를 true라고 계산하는 folding, false link가 필요 없으므로 최종적으로 CFG를 수정까지 한다.
2. Other transformations
Branch 숫자 줄이고, basic block 더 크게 만들기, 코드 길이 줄이기 등
2-1. Branch to unconditional branch
branch 숫자를 줄이고, 코드 길이를 줄일 수 있다.
2-2. Unconditional branch to branch
2-3. Branch to next basic block (next instr)
L1의 if문 결과가 true든 false든 L2로 이동한다.
2-4. Basic block merging
2-5. Branch to same target
if문의 then 파트와 else 파트의 goto 타겟이 동일하다.
2-6. Branch target expansion
함수 inlining과 유사.
2-7. Unreachable Code Elimination
entry에서부터 절대 도달할 수 없는 노드를 unreachable block이라고 부른다. 이러한 unreachable block을 구해 제거하는 최적화 방법이다.
일반적으로 unreachable block을 구하는 알고리즘은 다음과 같다.
1. 모든 노드들을 1이라고 가정한다.
2. entry부터 시작해서 거쳐간 노드들을 0으로 표시한다.
3. 최종적으로 1로 표시된 노드들이 unreachable block들이다.
📁 Loop Optimization
Loop는 한번 최적화하면 효과가 크다. 여러 최적화를 Loop basic block에 적용하는 것도 효과가 좋다.
Loop 고유의 최적화 기법은 loop unrolling, loop invariant, count up to zero가 있다.
1. Loop unrolling
loop body를 펼쳐서 반복 횟수 및 branch 횟수를 줄인다. 반복문도 곧 branch이므로 반복 횟수가 줄어드는 것은 branch가 줄어드는 것과 같다.
loop body가 적을 때 특히 유용하다.
2. Loop invariant
매번 동일한 값을 내는 문장은 loop 밖으로 이동시킨다.
3. Count up to zero
loop의 종료 조건을 동일한 의미를 가지면서 0과 비교하는 식으로 바꾼다.
즉 i가 1부터 증가해서 n까지 도달하는게 아니라, n에서 시작해서 0까지 도달하는 방식으로 바꾸는 것이다.
📝 문제 풀어보기
주어진 프로그램을 최대한 optimize 해보시오.
