개요

컴파일러의 코드 최적화에 대해 알아본다. 이 글은 내공 있는 프로그래머로 길러주는 컴파일러의 이해의 내용을 기반으로 함을 미리 밝힌다. 책 내용이 괜찮으니 관심있으신 분들은 사보는것을 추천한다.(필자는 이해관계자는 아님을 밝힌다.)

목차

컴파일러 강의 다른 포스팅은 아래의 링크를 참고하자.

• 컴파일러 강의 #1, 개요
• 컴파일러 강의 #2, 형식언어와 유한 오토마타
• 컴파일러 강의 #3, 컴파일러의 어휘분석
• 컴파일러 강의 #4, 문맥자유 문법과 푸시다운 오토마타
• 컴파일러 강의 #5, 컴파일러의 구문 분석
• 컴파일러 강의 #6, 의미 분석과 형 검사
• 컴파일러 강의 #7, 중간 언어와 중간 코드 생성
• 컴파일러 강의 #8, 코드 최적화

학습목표

• 코드 최적화
  • 코드 최적화에 대해 이해
• 기본 블록과 흐름 그래프
  • 기본 블록과 제어 흐름 그래프, 흐름 분석에 대해 이해
• 최적화 기법
  • 핍홀 최적화 기법, 지역 최적화 기법, 루프 최적화 기법, 전 역 최적화 기법, 기계 종속적 최적화 기법 등의 대해 이해

코드 최적화의 정의

• 동등한 의미를 가지면서 실행시간이나 메모리를 줄이는 것
• 최고 좋다는 의미보다 개선하는다는 의미로 사용

코드 최적화를 분류

• 최적화가 적용되는 프로그램의 영역
  • 지역 최적화(local optimization)
  • 전역 최적화(global optimization, intra-procedural optimization)
  • 프로시저 간 최적화(inter-procedural optimization)
• 기능적인 측면
  • 실행 시간 최적화
  • 메모리 최적화
• 최적화가 많이 이뤄지는 부분
  • 루프(혹은 반복문) 최적화
  • 단일문 최적화
• 목적 기계의 의존성
  • 기계 독립적 최적화(machine independent optimization)
  • 기계 종속적 최적화(machine dependent optimization)

기본 블록과 흐름 그래프

• 지역/전역/프로시저/루프 최적화를 위해 전체 프로그램을 기본 블록 단위로 분할하여 최적화
• 기본 블록
  • 지역 최적화의 기본 단위
  • 제어가 시작점으로 들어와서 끝점으로 나갈때까지 정지(halt)나 분기의 가능성이 없는 연속적인 코드들의 집합

기본 블럭인 확인 예제

리더를 통한 기본 블럭 나누기

흐름 그래프

• 흐름그래프란 기본 블록의 집합에 제어 흐름 정보를 추가하여 만든 방향 그래프
• 구성
  • 노드 : 기본 블럭
  • 간선 : 분기
• 진입노드, 진출노드 추가

흐름 그래프 예제

3주소코드, 기본블록, 흐름그래프

흐름분석

• 좋은 코드를 생성하기 위해 코드 최적화기(code optimizer)는 프로그램의 전체 적인 정보를 모으고, 이 정보를 흐름 그래프의 각 블록에 제공해야 한다.
• 자료흐름분석은 유효변수, 공통 부분식 등에 대한 정보를 모으는 일을 한다.
• 정적 분석법은 최적화 컴파일러가 최적화의 기회가 제공되는 위치를 파악하고 어떤 지점에서 코드 변형을 적용하는 것이 안정한지 증명하는것

핍홀 최적화 기법

• 핍홀은 연속적인 몇개의 명령어의 집합
• 작은 코드의 집합에서 최적화를 수행함

핍홀 최적화 기법: 중복된 명령어 제거 예제

• 중복 명령어 제거
  • 중복되는 LOAD나 STORE 명령문을 제거하는 방법이다.

아래와 같은 코드를 보자.

  LOAD R1, x
  STORE x, R1

이해를 위해 핍홀이 2개라고 가정하면
x를 R1으로 로드하고 다시 R1을 x로 저장하는것은 무의미하므로
store를 삭제할 수 있다.

핍홀 최적화 기법: 도달 불가능한 코드 제거

• 분기 바로 다음 문장에 있는 라벨이 없는 명령어 같은 것으로 도달할 수 없기 때문에 제거

핍홀 최적화 기법: 제어 흐름 최적화

핍홀 최적화 기법: 대수학적 간소화

• 수학적인 대수 법칙을 이용하여 식을 간소화
  $ x = y + 0 -> x = y $ (덧셈 항등 법칙)
  $ x = y * 1 -> x = y $ (곱셈 항등 법칙)

핍홀 최적화 기법: 세기 감축

• 거듭제곱 -> 곱셈
• 곱셈 -> 덧셈
• 나눗셈 -> 곱셈

핍홀 최적화 기법: 하드웨어 명령어 사용

• 특정 연산은 하드웨어 연산으로 대체

지역 최적화 기법

• 기본 블록 안에서 최적화가 이뤄짐
• 공통 부분식 제거, 복사 전파, 죽은 코드 제거, 상수 폴딩, 대수학적 간소화 등이 있음

지역 최적화 기법: 공통 부분식 제거

지역 최적화 기법: 복사전파

• 복사 전파란 치환면 f = g 이후에 가능하뎜 f대신에 g를 사용하는 방법

지역 최적화 기법: 상수폴딩

• 컴파일 할 때 상수를 포함하는 연산이 미리 계산될 수 있으면 미리 계산함

지역 최적화 기법: 대수학적 간소화

핍홀 최적화에서 이미 다룸

루프 최적화 기법

• 전체 코드의 10%가 실행시간의 90%를 차지하는 이유는 루프 때문, 따라서 최적화에서 매우 중요한 부분

루프 최적화 기법: 코드 이동

• 루프 수행 횟수와 상관없이 항상 같은 값이라면 루프 외부로 이동

루프 최적화 기법: 귀납변수 최적화

• 루프를 돌때마다 값이 일률적으로 변하는 변수

루프 최적화 기법: 루프 융합

• 루프의 오버헤드를 줄이기 위한 방법으로 여러개의 루프를 통합하는 것

루프 최적화 기법: 루프 교환

• 내부 루프와 외부 루프를 교환하는 것
• 참조 지역성을 개선

루프 최적화 기법: 루프 전개

• 루프 계산을 빠르게 하기 위해 루프를 Unrolling하는 효과를 냄
• 증가와 조건 검사의 횟수가 감소하기 때문에 수행되는 명령어의 수가 줄어듬

전역 최적화 기법

• 프로그램 전체의 흐름분석을 통해 일련의 비효율적인 코드를 좀 더 효율적인 코드로 만드는 방법
• 지역 최적화와 달리 기본 블로간 정보와 흐름 그래프를 이용하고 프로그램의 전체적인 흐름 분석을 통한 최적화 기법

전역 최적화 기법: 공통 부분식 제거

전역 최적화 기법: 상수폴딩

지역 최적화 기법에서 이미 설명

전역 최적화 기법: 도달 불가능한 코드제거

• 흐름 그래프의 입구에서 도달할 수 없는 기본 블록은 제거 가능한데, 상수 폴딩에서 사용된 예의 경우에 제어문이 항상 true이므로 false로 가는 부분이 제거 가능

전역 최적화 기법: 죽은 코드 제거

• 죽은코드란 어떤 변수가 특정 프로그램 지점 이후 전혀 사용하지 않는 값을 계산하는 문장을 말함

전역 최적화 기법: 기계 종속적 최적화 기법

• 기계의 특성에 따라 아주 달라질 수 있는 기계 종속적 최적화 기법에는 중복된 LOAD 명령 제거, 효율적인 명령어 선택, 레지스터 할당과 배정, 명령어 스케쥴링 등이 있음

전역 최적화 기법: 중복 명령어 제거

• 핍홀 최적화 기법에서 이미 설명함
• 중복되는 로드 명령문이나 저장 명령문을 제거함으로써 최적화

전역 최적화 기법: 효율적인 명령어 선택

• 동일한 기능을 가진 더 효율적인 명령어로 대치함으로써 최적화

전역 최적화 기법: 명령어 스케쥴링

• 식의 연산 순서 변경에 의해 연산이 임시 결과를 저장하거나 로드의 횟수를 최소로 함으로써 임시 변수 기억 공간을 절약할 뿐 아니라 효율적인 코드를 생산