컴파일러가 최적화를 할 때 의존성 파악은 가장 중요한 작업 중 하나다.

• 컴파일러는 최적의 명령어 실행 순서를 정할 수 있다.
  • 이것을 보통 명령어 재배치(instruction reordering) 혹은 명령어 스케줄링(instruction scheduling)최적화 라고 부른다.

데이터 의존성(data dependency)

• 두 명령어 사이에서 일어나는 데이터 의존성은 읽기/쓰기의 순서에 따라 RAW, WAW, WAR이라는 의존성으로 구분할 수 있다.

RAW(Read-After-Write) 의존성

1: x = y + 1;
2: z = x * 2;

• 2번에서 x를 읽기 위해서는, 1번에서 x의 값이 정해져야 하기 때문에 2번을 먼저 수행할 수 없다.

WAR(Write-After-Read) 의존성

1: z = x * 2;
2: x = y + 1;

• 1번에서 x의 값을 읽기 때문에, 2번을 1번보다 먼저 수행할 수 없다.

WAW(Write-After-Write)

1: x = z * 2;
2: x = y + 1;

• 같은 대상에 값이 쓰여지기 때문에 의존성이 생긴다.

의존성 제거

프로그램 코드가 위 세가지 데이터 의존성중 하나라도 있으면 일단 순서대로 실행해야 정확한 결과를 얻을 수 있다.

하지만 WAR/WAW의 경우 약간의 트릭을 통해 의존성을 제거할 수 있다.

// WAR
1: z = x * 2;
2: x = y + 1;
3: a = x / 2;
// x -> x1
1': z = x * 2;
2': x1 = y + 1;
3': a = x1 / 2;

• 명령어 2의 변수명 x를 바꿈으로서 의존성이 제거 되었다.

// WAW
1: x = z * 2;
2: x = y + 1;
3: a = x / 2;
// x -> x1
1': x = z * 2;
2': x1 = y + 1;
3': a = x1 / 2;

• WAW또한 이름 변경을 통해 의존성을 제거했다.