개요

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

목차

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

학습목표

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

코드 최적화의 정의

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

코드 최적화를 분류

  • 최적화가 적용되는 프로그램의 영역
    • 지역 최적화(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 명령 제거, 효율적인 명령어 선택, 레지스터 할당과 배정, 명령어 스케쥴링 등이 있음

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

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

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

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

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

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