6 분 소요

이번 포스트는 컴파일러의 5번째 단계인 Code Optimization에 대해 다룬다.

Code Optimization

Code Optimizer란?

  • 컴파일러의 중요한 목표 중 하나 = 효율적인 코드 생성
  • Source -> Target code로 번역할 때 효율을 개선할 수 있다.
  • 보통 IR 단계에서 많이 수행된다.
    • Source level에서 하기에는 너무 고수준이다.
    • Target code에서 하기에는 너무 저수준이다.
  • 목표
    • 실행 시간을 감소, 메모리 사용량 감소, 코드 크기 감소, 전력 소비 감소
    • 다만 프로그램의 semantic은 보존한다.

Baisc Blocks (기본 블록)

  • 연속적인 명령어 집합으로 Jump target이나 Jump source가 없는 구간이다.
  • Basic Block 내부에서는 항상 순차적으로 진행한다.
  • 어떻게 찾을 수 있는가?
    • Entry Point : 항상 처음 명령어부터 실행된다.
    • Exit Point : Basic Block 중간에서는 절대 Jump가 발생하지 않는다.
      • Jump가 발생했다면 그 부분이 Basic Block의 끝 부분

Control Flow Graps (CFG)

  • Basic Block 간의 흐름을 Graph로 나타낸 것
  • 대부분의 Optimization은 Basic Block 단위 또는 CFG 단위로 수행된다.
    • Global 단위도 CFG를 기반으로 전역적인 분석을 수행해야 한다.

Local Optimizations

Common Subexpression Elimination

  • 프로그램 내에서 같은 계산을 여러 번 하는 경우에 사용된다.

  • 이미 계산이 되어있으니 한번 만 계산하고 이것을 재사용한다.

Q. Subexpression이란?

  • 어떤 표현식 E가 코드 내 여러 위치에서 항상 동일한 값을 산출한다.
  • 유효한 조건
    • 해당 Subexpression을 구성하는 변수들의 값이 중간에 변경되지 않아야 한다.
    • 변수의 정의가 도중에 변경되지 않아야 CSE가 가능하다.

  • 구현하는 방법 ? : DAG를 사용한다.

    • Available Expression Anlaysis를 활용한 방법으로도 대체할 수 있다.

Directed Acyclic Graphs (DAG)

  • 방향성이 있는 비순환 그래프
  • 표현식을 DAG로 표현하면 중복된 계산을 자연스럽게 공유할 수 있다.
  • CSE를 위한 중복 검사 + 공유 저장이 가능한 자료구조
  • 해쉬 테이블을 사용하여 구성한다.

Global과 Local 에서 다 사용되는 분석들

Available Expression Analysis

  • 프로그램의 각 지점에서 어떤 Expression이 이미 계산되어 있고 그 결과가 유효한지를 분석하는 기법
  • CSE를 구현할 때 DAG를 명시적으로 만들지 않고 사용이 가능하다.
  • Available한다는 뜻
    • 그 지점까지 오는 모든 경로에서 E가 이미 계산되어있다.
    • 그 이후로 E에 사용된 변수들의 값이 변경되지 않다.
  • Block간 (Global)에서 더 유용하게 쓰인다.
  • 표현 방법
    • {a * a, b * t0}
  • 기본적인 아이디어
    • Generate : 블락 내부에서 계산되어 Available하게 되는 표현식들의 집합으로 조건이 만족되면 그 이후로 그 값을 재사용할 수 있다.
    • Kill : 블락 내부에서 변수 값을 변경함으로써 특정 표현식을 무효화시키는 경우로 하나라도 변경하게 되면 더이상 유효하지 않다.(재사용할 수가 없다.)
    • “Kill을 먼저 적용한 다음에 Gen을 적용해야 한다.”
      • X = X + 1과 같은 예시에서 활용
  • 한계
    • 현재 지점에서 어떤 표현식이 Available한지 분석은 가능하지만, 조금만 경로가 달라도 Available 판단이 불가능하다.
    • 또한 변 assigned value가 redefined될 때 어떤 것을 넣어야할지도 판단이 불가능하다.
      • => 새로운 접근 방법 : Reaching Definitions

Reaching Definitions

  • Reaching : 현재 지점에 도달하는 모든 변수의 정의를 분석하는 것
  • 현재 프로그램 포인트에서 변수 X의 값은 어디서 정의된 것인지를 추적한다.
  • Copy Propagation, Dead Code Elimination에 필요하다.
  • 표현 방법
    • {to = b + c, t1 = a * a }

Common Subexpression Elimination을 만족하기 위한 조건

  1. Expression E가 현재 시점에서 Available해야 한다.
    • 이미 계산된 적이 있고, 그 이후로 사용된 변수들의 값이 변경되지 않았어야 한다.
  2. E의 결과를 들고 있는 유효한 변수가 존재해야 한다.
    • 어떤 변수에 저장해놨다가 재사용한다.
    • 즉, 그 변수가 현재 시점에서도 유효해야 한다. 그 변수에 대한 정의가 현재까지 Reach하고 있어야 한다.

Copy Propagation

  • 복사된 변수 사용을 원래의 변수로 대체하는 최적화 기법이다.
  • x = y 와 같은 코드가 있을 때, 이는 불필요한 변수 사용이다.
    • 레지스터 할당 시에도 도움이 안됨.
  • 변수의 값이 중간에 변경하면 안되기 때문에 Reaching Definition Analysis를 기반으로 적용이 가능하다.

Dead Code Elimination

  • Dead Code란? :
    • 계산되기는 하지만 절대로 사용되지 않는 값을 말한다.
    • 즉 제거가 가능하다.
  • Dead Code인지 판단하기 위해서는 해당 변수가 향후 사용될 가능성이 있는지 없는지에 대한 확인이 필요하다.
    • 이를 찾기 위한 방법이 Available Expression, Reaching Definition 으로는 할 수가 없다.
    • 새로운 방법이 필요 => Live Variable Analysis

Live-Variable Analysis

  • Live Variable이란?
    • 현재 프로그램 지점에서 앞으로 실행 중에 그 변수 값이 참조(사용)될 가능성이 있는 변수
    • 즉 변수 값이 현재 쓸모 있는 상태인지를 판단하는 것이다.

  • 프로그램의 종료에서는 Live Variable이 없다.

  • 계산 시 주의할 점
    • Live Variable은 Backward로 계산해야 한다. (뒤에서 앞으로)
    • 정의가 발생되면 해당 변수는 Kill 된다.
      • 이미 있어도 새로 정의되면 이전 값은 사용될 수가 없다.
    • RHS가 Constant이면 변수는 없다.
  • 변수 값이 더 이상 사용되지 않을거라면 그 변수에 값을 넣는 것도 의미가 없다. -> 즉, 제거가 가능하다.

Arithmetic Simplification

  • 산술 연산 중에서 결과가 뻔한 연산을 미리 단순하게 바꾸는 과정
  • 수학적 성질을 이용해 연산 자체를 줄여서 최적화를 한다.
  • 적용 예시
    • x * 1 => x
    • x + 0 => x
  • 특징
    • 안전한 최적화 (항상 적용이 가능하다.)
    • 의미도 변하지 않는다.
    • 부동소수점과 같은 경우 오차 문제를 조심해야 한다.

Constant Folding

  • 컴파일 타임에 이미 값을 알 수 있는 상수 연산을 미리 계산해서 결과를 바꿔버리는 것을 의미한다.
  • 실행 시가 아니라 컴파일 시점에 결과를 계산해서 실행시간을 절약할 수 있다.

  • 예시) x = 2 + 3=> x = 5

  • RHS가 전부 상수 일 때만 가능하다.

Global Optimizations

  • Local Optimizations 은 Basic Block 내에서만 중복된 계산을 제거하였다.
  • Global Optimization은 Basic Block을 넘어 전체 Control Flow Graph(CFG)에서도 중복된 계산을 제거한다.
  • 왜 필요한가?
    • 많은 경우 중복 계산은 Block 사이에서도 발생한다.

In & OUT set

  • IN[B] : Block B 시작 지점에서의 Data-flow 정보
  • OUT[B] : Block B 끝난 후의 Data-flow 정보
    • 여기서 Data- flow 정보란? : set of variables

Dead-Code Elimination (in Global Optimization) 과정 설명

  1. 전체 CFG에 관하여 Live Variable Analysis 수행
    • IN / OUT set을 계산한다.
  2. 각 Blockd에서 Local analysis 와 Optimize를 수행한다.
  3. 1번과 2번 step을 변화가 없을 때까지 수행한다.

Global Data-Flow Analysis

  Available Expressions Reaching Definitions Live Variables
Domain Sets of expressions Sets of definitions Sets of variables
Application Common subexpression elimination Common subexpression elimination
Copy Propagation		 Dead code elimination
Direction Forwards Forwards Backwards
Boundary OUT[ENTRY] = ∅ OUT[ENTRY] = ∅ IN[EXIT] = ∅

Availalbe Expressions

  • 현재 시점에서 어떤 expression이 Availble 한지?

  • Direction : Forwards (앞으로 진행)

  • OUT[ENTRY] = ∅ (프로그램 시작 전에는 아무 expression도 available 하지 않다.)

Reaching Definitions

  • 어떤 변수 정의가 현재 시점에 Reach 했는지?
  • Direction : Forwards (앞으로 진행)
  • OUT[ENTRY] = ∅ (프로그램 시작 전에는 아무 expression도 available 하지 않다.)

Live Variables

  • 현재 시점에서 앞으로 참조될 가능성이 있는 변수 집합
  • Direction : Backwards (뒤에서 앞으로 진행)
  • IN[EXIT] = ∅ (프로그램의 끝에는 Live한 변수가 없기 때문에)

Global Live-Variable Analysis

\[IN[B] = use_B ∪ (OUT[B] - def_B)\]
  • Use_B : Block B 내부에서 그 변수 값이 사용된 변수들의 집합
    • 해당 Block 내에서 사용한 적이 있는 변수
    • RHS에 사용된 적이 있는 변수
  • Def_B : Block B 내부에서 정의된 변수들의 집합
    • 해당 Block 내에서 새로 값이 할당된 변수들

해석하면 다음과 같다.

IN[B] 수식은 “Block 내부에서 사용하는 변수들” + “Block 이후에서 여전히 Live한 변수 중에서, B에서 다시 정의되지 않은 변수들”

=> 이를 통해 Dead Code Elimination, Register Allocation 등에서 변수의 Live 여부를 정확하게 판단이 가능하다.

  • Global Live-Variable Pesudo Code
IN[EXIT] = ∅
for (each basic block B other then EXIT) IN[B] = ∅;
while (changes to any IN occur)
	for (each basic block B other then EXIT) {
		OUT[B] = U IN[S]
		IN[B] = use_B U (OUT[B] - def_B)
	}

Global Reaching Definition Analysis

\[OUT[B] = gen_B ∪ (IN[B] - kill_B)\]
  • Gen_B : Block B 내부에서 정의된 정의들의 집합
    • 즉 B가 끝날 때 이 정의는 무조건 Reaching 하고 있다.
    • Block B 내부에서 정의된 변수들의 정의
  • Kill_B : Block B 내부에서 정의가 kill 되는 정의들의 집합
    • 어떤 변수 x를 정의하고, x에 대한 다른곳에서 온 모든 정의는 kill 된다.

해석하면 다음과 같다.

OUT[B] 수식은 “B 내부에서 새로 정의한 것” 과 “B 이전에서 온 정의들 중에서 B에서 다시 정의되지 않은 것”을 합친 것을 말한다.

  • 현재 프로그램의 어떤 지점에서 어떤 변수의 정의가 도달(Reaching)하고 있는가를 분석하는 것
  • Copy Propagation, Dead Code Elimination 에 사용된다.
  • Global Reaching Definition Pesudo Code
OUT[ENTRY] = ∅
for (each basic block B other then ENTRY) OUT[B] = ∅
while (changes to any OUT occur)
	for (each basic block B other than ENTRY) {
		IN[B] = U OUT[P]
		OUT[B] = gen_B U (IN[B] - kill_B)
	}

Global Available Expressions Analysis

\[OUT[B] = e_gen[B] ∪ (IN[B] - e_kill[B])\]
  • e_gen[B] : Block B 내부에서 생성된 표현들의 집합
    • Block B를 통과하고 나면 이 표현식은 Available 하다.
    • 즉, B 내부에서 계산이 완료된 표현식들
  • e_kill[B] : Block B 내부에서 Kill된 표현식들의 집합
    • RHS에 등장한 변수들 중, LHS에 정의된 변수와 관련된 표현식을 kill 한다.

해석하면 다음과 같다.

OUT[B] 수식은 “Block B 내부에서 계산 완료된 표현식들” 과 “Block 이전에서 Available했던 표현식들 중에서 B 내부에 kIll되지 않은 표현식들”의 합집합이다.

주의할 점

i = i + 1 처럼 단순한 계산은 맞지만, 표현식의 결과가 변수에 저장되지 않는 표현식들은 e_gen에 포함되지 않는다.

  • Global Available Expressions Pesudo Code
OUT[ENTRY] = ∅
for (each basic block B other than ENTRY) OUT[B] = U;
while (changes to any OUT occur)
	for (each basic block B otehr then EMPTY) {
		IN[B] = Intersection OUT[P]
		OUT[B] = e_gen_B U (IN[B] - e_kill_B)
	}

다음 포스트로는 컴파일러의 마지막 단계인 Code Generator에 대해 다룰 예정이다.

태그:

카테고리:

업데이트:

참고

Concurrency, Locks

8 분 소요

이번 포스트는 OS의 Concurrency와 Locks에 대해 다룬다.