# 상수 전파 (Constant Propagation)

**상수 전파**(Constant Propagation)는 컴파일러 최적화 기법 중 하나로, 프로그램 실행 시 특정 변수나 표현식의 값이 컴파일 시점이나 실행 시점에 상수(constant)로 결정될 수 있음을 활용하여 코드를 더 효율적으로 만드는 기술입니다. 이 기법은 정적 분석(Static Analysis)의 한 형태로, 불필요한 연산을 제거하거나 조건부 분기를 단순화하여 실행 속도를 높이고 코드 크기를 줄이는 데 기여합니다.

## 개요

컴파일러는 소스 코드를 기계어 또는 중간 표현(IR, Intermediate Representation)으로 변환하는 과정에서 다양한 최적화를 수행합니다. 그중 상수 전파는 데이터 흐름 분석(Data Flow Analysis)을 기반으로 합니다. 컴파일러가 변수에 할당된 값이 항상 동일한 상수임을 감지하면, 해당 변수가 사용되는 모든 곳에 직접 상수 값을 대입하거나, 해당 변수를 사용하는 연산을 미리 계산하여 결과값으로 대체합니다.

예를 들어, `int x = 10; int y = x + 5;`라는 코드가 있을 때, 컴파일러는 `x`가 항상 `10`임을 알기 때문에 `y`의 초기화 과정을 `int y = 10 + 5;`로 변경하고, 최종적으로 `int y = 15;`로 단순화할 수 있습니다. 이는 런타임 시 추가적인 덧셈 연산을 생략함을 의미합니다.

## 동작 원리 및 알고리즘

상수 전파는 일반적으로 제어 흐름 그래프(Control Flow Graph, CFG)를 사용하여 구현됩니다. 주요 단계는 다음과 같습니다.

### 1. 데이터 흐름 분석
컴파일러는 프로그램의 각 지점에서 변수가 가질 수 있는 값의 집합을 추적합니다. 각 변수는 다음 세 가지 상태 중 하나로 분류됩니다:
*   **상수(Constant)**: 명확하게 알려진 상수 값 (예: 42, "hello")
*   **미정(Undef)**: 값이 알려지지 않음
*   **비상수(Non-constant)**: 상수가 아님 (예: 다른 변수의 참조, 함수 호출 결과)

### 2. 전파(Propagation)
CFG의 각 노드(블록)를 순회하며 상수 정보를 전파합니다.
*   **할당문**: `x = c` (c는 상수)라면, `x`의 상태를 '상수 c'로 업데이트합니다.
*   **연산문**: `x = a + b`라면, `a`와 `b`가 모두 상수일 경우 `x`를 상수로 설정합니다. 그렇지 않으면 `x`를 '비상수'로 처리합니다.
*   **분기문**: `if (x == 5)`에서 `x`가 상수 5라면, 조건은 항상 참이므로 해당 분기만 남기고 다른 분기는 제거할 수 있습니다.

### 3. 고정점(Fixed Point) 도달
상수 정보는 프로그램의 여러 경로를 통해 순환적으로 전파될 수 있습니다. 따라서 분석이 수렴하여 더 이상 새로운 상수 정보가 발견되지 않을 때까지 반복적으로 분석을 수행합니다.

## 최적화 효과

상수 전파는 단독으로 사용되기보다 다른 최적화 기법들과 결합하여 시너지 효과를 냅니다.

| 최적화 기법 | 상수 전파와의 상호작용 | 효과 |
| :--- | :--- | :--- |
| **사이드 효과 제거 (Dead Code Elimination)** | 상수 전파로 인해 조건문이 항상 참/거짓이 되면, 실행되지 않는 코드 블록을 제거할 수 있습니다. | 코드 크기 감소, 불필요한 분기 오버헤드 제거 |
| **상수-fold (Constant Folding)** | 연산자의 피연산자가 모두 상수일 경우, 컴파일 시점에 연산 결과를 미리 계산합니다. | 런타임 연산 비용 절감 |
| **레지스터 할당 최적화** | 상수 값은 즉시 값(Immediate)으로 처리되거나 레지스터에 할당되지 않을 수 있어 레지스터 압력을 줄입니다. | 레지스터 스패일링(Store/Load) 감소 |

## 예시

다음 C 코드 예시를 통해 상수 전파의 효과를 확인해 보겠습니다.

```c
// 최적화 전
int calculate(int a) {
    int x = 10;
    int y = x + 5;
    if (y == 15) {
        return a * 2;
    } else {
        return a + 1;
    }
}
```

컴파일러가 상수 전파를 적용하면 다음과 같이 변환됩니다.

1.  `x`는 상수 `10`으로 결정됨.
2.  `y = x + 5`는 `y = 10 + 5`로 간주되며, `y`는 상수 `15`로 결정됨.
3.  `if (y == 15)`는 `if (15 == 15)`가 되어 조건이 항상 참임을 알 수 있음.
4.  `else` 블록은 실행되지 않으므로 제거됨.

```c
// 최적화 후 (개념적 결과)
int calculate(int a) {
    return a * 2;
}
```

이 과정에서 `y` 변수는 완전히 제거되었으며, 조건부 분기 연산도 사라졌습니다.

## 한계 및 주의사항

상수 전파는 강력한 최적화 기법이지만 다음과 같은 한계가 있습니다.

*   **정적 분석의 한계**: 런타임에 결정되는 값(예: 사용자 입력, 파일 읽기, 시스템 시간)은 정적 분석으로 상수임을 보장할 수 없습니다.
*   **메모리 접근**: 포인터나 참조를 통해 간접적으로 메모리에 접근하는 경우, 컴파일러가 해당 메모리 위치의 값이 상수인지 여부를 정확히 파악하기 어렵습니다. 이를 해결하기 위해 컴파일러는 메모리 모델에 대한 가정(Memory Model Assumptions)을 사용하거나, 분석의 정밀도를 낮추는 트레이드오프를 감수해야 합니다.
*   **분석 비용**: 복잡한 프로그램에서 정확한 상수 전파를 수행하려면 상당한 컴파일 시간과 메모리가 소요됩니다. 따라서 실제 컴파일러는 정밀도와 성능 사이의 균형을 맞추기 위해 제한된 범위 내에서 상수 전파를 적용합니다.

## 관련 문서 및 참고 자료

*   **데이터 흐름 분석 (Data Flow Analysis)**: 변수의 값이 프로그램 전체에서 어떻게 흐르는지 분석하는 기법.
*   **사이드 효과 제거 (Dead Code Elimination)**: 실행 결과에 영향을 주지 않는 코드를 제거하는 최적화.
*   **정적 코드 분석 (Static Code Analysis)**: 프로그램 실행 없이 소스 코드를 분석하는 방법론.
*   **LLVM Compiler Infrastructure**: 상수 전파를 포함한 다양한 최적화 패스를 제공하는 오픈 소스 컴파일러 프레임워크.

상수 전파는 GCC, Clang, MSVC 등 주요 컴파일러의 기본 최적화 단계에 포함되어 있으며, `-O1` 이상의 최적화 레벨에서 활성화되어 성능 향상에 기여합니다.