불필요한 코드 제거

컴파일러 이론에서 불필요한 코드 제거(Dead-code elimination, DCE, dead-code removal, dead-code stripping, 또는 dead-code strip)는 불필요한 코드(프로그램 결과에 영향을 미치지 않는 코드)를 제거하는 컴파일러 최적화이다. 이러한 코드를 제거하면 몇 가지 이점이 있다. 프로그램 크기를 줄여 일부 상황에서 중요한 고려 사항이 되고 전송할 바이트 수와 같은 리소스 사용량을 줄이며 실행 중인 프로그램이 관련 없는 연산을 실행하는 것을 피하게 하여 실행 시간을 단축한다. 또한 프로그램 구조를 단순화하여 추가 최적화를 가능하게 한다. 불필요한 코드에는 절대로 실행될 수 없는 코드(도달 불가능한 코드)와 불필요한 변수(쓰여졌지만 다시는 읽히지 않는 변수)에만 영향을 미치는, 즉 프로그램과 무관한 코드가 포함된다.

예시

다음은 C로 작성된 예시이다.

int foo(void) {
  int a = 24;
  int b = 25; /* Assignment to dead variable */
  int c;
  c = a * 4;
  return c;
  b = 24; /* Unreachable code */
  return 0;
}

값 사용에 대한 간단한 분석은 첫 번째 할당 후 b의 값이 foo 내부에서 사용되지 않음을 보여준다. 게다가 b는 foo 내부에 지역 변수로 선언되었으므로 foo 외부에서는 그 값을 사용할 수 없다. 따라서 변수 b는 불필요하며 최적화 프로그램은 해당 저장 공간을 회수하고 초기화를 제거할 수 있다.

또한 첫 번째 return 문이 무조건 실행되고 그 뒤에 "goto"가 도달할 수 있는 레이블이 없으므로, 두 번째 b에 대한 할당에 도달하는 실행 경로는 존재하지 않는다. 따라서 해당 할당은 도달 불가능하며 제거될 수 있다. 만약 해당 프로시저에 return 문 뒤에 레이블이 있고 프로시저의 다른 곳에 goto와 같은 더 복잡한 제어 흐름이 있었다면, b에 대한 할당에 도달할 수 있는 실행 경로가 존재했을 수도 있다.

또한 함수 내에서 일부 계산이 수행되더라도 그 값은 이 함수 스코프 외부에서 접근 가능한 위치에 저장되지 않는다. 게다가 함수가 정적 값(96)을 반환한다는 점을 고려할 때, 반환하는 값으로 단순화될 수 있다 (이 단순화는 상수 폴딩이라고 한다).

대부분의 고급 컴파일러는 불필요한 코드 제거를 활성화하는 옵션을 제공하며, 때로는 다양한 수준으로 제공한다. 낮은 수준은 실행될 수 없는 명령어만 제거할 수 있다. 높은 수준은 사용되지 않는 변수에 대한 공간도 예약하지 않을 수 있다. 더 높은 수준은 목적 없는 명령어 또는 함수를 판별하고 제거할 수 있다.

불필요한 코드 제거의 일반적인 사용 사례는 전처리기를 통한 선택적 코드 포함의 대안이다. 다음 코드를 고려해 보자.

int main(void) {
  int a = 5;
  int b = 6;
  int c;
  c = a * (b / 2);
  if (0) {   /* DEBUG */
    printf("%d\n", c);
  }
  return c;
}

표현식 0은 항상 거짓으로 평가되므로 if 문 내부의 코드는 절대로 실행될 수 없으며, 불필요한 코드 제거는 최적화된 프로그램에서 이를 완전히 제거한다. 이 기술은 디버그에서 선택적으로 코드 블록을 활성화하는 데 흔히 사용된다. 불필요한 코드 제거가 있는 최적화 프로그램을 사용하면 동일한 작업을 수행하기 위해 전처리기를 사용할 필요가 없어진다.

실제로 최적화 프로그램이 발견하는 불필요한 코드의 대부분은 최적화 프로그램의 다른 변환에 의해 생성된다. 예를 들어, 연산자 강도 감소의 고전적인 기술은 코드에 새로운 계산을 삽입하고 이전의 더 비싼 계산을 불필요하게 만든다. 이어진 불필요한 코드 제거는 이러한 계산을 제거하고 효과를 완료한다 (강도 감소 알고리즘을 복잡하게 하지 않고).

역사적으로 불필요한 코드 제거는 데이터 흐름 분석에서 파생된 정보를 사용하여 수행되었다. 정적 단일 대입 형식(SSA)에 기반한 알고리즘은 론 사이트론(Ron Cytron) 등이 쓴 SSA 형식에 대한 원본 학술 논문에 나타난다. 로버트 실링스버그(Robert Shillingsburg, aka Shillner)는 이 알고리즘을 개선하고 쓸모없는 제어 흐름 연산을 제거하기 위한 동반 알고리즘을 개발했다.

동적으로 불필요한 코드 제거

불필요한 코드는 일반적으로 무조건 불필요한 것으로 간주된다. 따라서 컴파일 타임에 불필요한 코드 제거를 통해 불필요한 코드를 제거하는 것이 합리적이다.

그러나 실제로 특정 조건에서만 불필요하거나 도달 불가능한 코드 섹션이 되는 경우가 흔하며, 이는 컴파일 또는 어셈블리 시점에는 알려지지 않을 수 있다. 이러한 조건은 다양한 런타임 환경(예: 운영 체제의 다른 버전, 특정 대상 환경에 로드된 드라이버 또는 서비스의 다른 세트 및 조합)에 의해 부과될 수 있으며, 이는 코드에 다른 특수 사례 세트를 요구하지만 동시에 다른 경우에 대해 조건부 불필요한 코드가 될 수 있다. 또한 소프트웨어(예: 드라이버 또는 상주 서비스)는 사용자 기본 설정에 따라 특정 기능을 포함하거나 제외하도록 구성될 수 있어 특정 시나리오에서 사용되지 않는 코드 부분이 쓸모없게 될 수 있다. 모듈형 소프트웨어는 필요에 따라 동적으로 라이브러리를 로드하도록 개발될 수 있지만, 대부분의 경우 특정 라이브러리에서 관련 루틴만 로드하는 것은 불가능하며, 설령 이것이 지원되더라도 루틴에는 주어진 시나리오에서 불필요한 코드로 간주될 수 있지만 컴파일 타임에는 제외될 수 없었던 코드 섹션이 포함될 수 있다.

수요를 동적으로 감지하고, 종속성을 식별 및 해결하며, 이러한 조건부 불필요한 코드를 제거하고, 로드 또는 런타임에 나머지 코드를 재결합하는 데 사용되는 기술을 동적 불필요한 코드 제거 또는 동적 불필요한 명령어 제거라고 한다.

대부분의 프로그래밍 언어, 컴파일러 및 운영 체제는 동적 적재 라이브러리 및 늦은 연결 외에는 거의 또는 전혀 지원을 제공하지 않으므로 선행 컴파일된 언어로 작성되거나 어셈블리어로 작성된 언어와 함께 동적 불필요한 코드 제거를 활용하는 소프트웨어는 매우 드물다. 그러나 Just-in-time 컴파일을 수행하는 언어 구현은 동적으로 불필요한 코드 제거를 위해 최적화할 수 있다.

비록 초점은 다소 다르지만, 유사한 접근 방식은 때때로 동적 소프트웨어 업데이트 및 핫 패치에도 활용된다.

같이 보기

• 과잉 코드
• 단순화 (기호 계산)
• 부분 중복 제거
• 연언 소거
• 동적 소프트웨어 업데이트
• 동적 결합 (컴퓨팅)
• 자가 재배치
• 소프트웨어 크러프트
• 트리 쉐이킹
• 포스트 패스 최적화
• 프로파일 기반 최적화
• 수퍼옵티마이저
• 함수 다중 버전

더 읽어보기

• Bodík, Rastislav; Gupta, Rajiv (June 1997). 《Partial dead code elimination using slicing transformations》. 《Proceedings of the ACM SIGPLAN 1997 Conference on Programming Language Design and Implementation (PLDI '97)》. 682–694쪽. 
• Aho, Alfred Vaino; Sethi, Ravi; Ullman, Jeffrey David (1986). 《Compilers - Principles, Techniques and Tools》. 애디슨 웨슬리 출판사. ISBN 0-201-10194-7. 
• Muchnick, Steven Stanley (1997). 《Advanced Compiler Design and Implementation》. 모건 카우프만 퍼블리셔스. ISBN 1-55860-320-4. 
• Grune, Dick; Bal, Henri Elle; Jacobs, Ceriel J. H.; Langendoen, Koen G. (2000). 《Modern Compiler Design》. 존 와일리 & 선스. ISBN 0-471-97697-0. 
• Kennedy, Ken; Allen, Randy (2002). 〈Chapter 4.4. Data Flow Analysis - Chapter 4.4.2. Dead Code Elimination〉 2011 digital print of 1판. 《Optimizing Compilers for Modern Architectures: A Dependence-Based Approach》. 아카데믹 프레스 / 모건 카우프만 퍼블리셔스 / 엘스비어. 137, 145–147, 167쪽. ISBN 978-1-55860-286-1. LCCN 2001092381. 
• Muth, Robert; Debray, Saumya K.; Watterson, Scott; De Bosschere, Koen (January 2001). 《alto: a link-time optimizer for the Compaq Alpha.》. 《Software: Practice and Experience》 31. 67–101쪽. CiteSeerX 10.1.1.33.4933. doi:10.1002/1097-024X(200101)31:1<67::AID-SPE357>3.0.CO;2-A. S2CID 442062.  [5]

외부 링크

• C/C++ 컴파일러가 끔찍한 코드를 생성하도록 속이는 방법?