공통 하위 표현 제거

Common subexpression elimination

컴파일러 이론에서 공통 하위표현제거(CSE)는 동일한 식(즉, 모두 동일한 값으로 평가)의 인스턴스를 검색하여 계산값을 보유하는 단일 변수로 교체할 가치가 있는지 여부를 분석하는 컴파일러 최적화다.[1]

예

다음 코드에서:

a = b * c + g; d = b * c * e;

코드를 다음과 같이 변환할 가치가 있을 수 있다.

tmp = b * c; a = tmp + g; d = tmp * e;

저장 및 검색 비용인 경우tmp계산 비용보다 적다.b * c여분의 시간

원칙,

CSE 수행 가능성은 이용 가능한 표현식 분석(데이터 흐름 분석)을 기반으로 한다.표현b*c다음과 같은 경우 프로그램의 p 지점에서 이용할 수 있다.

  • 초기 노드에서 p 평가까지의 모든 경로b*cp에 도달하기 전에,
  • 그리고 에 대한 숙제가 없다.b또는c평가 후 그러나 p.

최적기에 의해 수행되는 비용/편익 분석은 스토어의 비용이tmp곱셈의 비용보다 적다. 실제로, 레지스터가 유의한 값과 같은 다른 요소들.

컴파일러 작성자는 CSE의 두 가지 종류를 구분한다.

  • 단일 기본 블록 내에서 로컬 공통 하위 표현식 제거 작업
  • 전지구적 공통 하위표현 제거는 전체 절차에서 작용한다.

두 종류 모두 프로그램의 어느 지점에서 어떤 식을 사용할 수 있는지에 대한 데이터 흐름 분석에 의존한다.

혜택들

CSE 수행의 이점은 일반적으로 사용되는 최적화일 정도로 충분히 크다.

위의 예와 같은 간단한 경우에서 프로그래머는 코드를 작성하는 동안 중복된 표현을 수동으로 제거할 수 있다.CSE의 가장 큰 소스는 어레이 인덱싱 계산과 같이 개발자가 수동으로 개입할 수 없는 컴파일러에서 생성된 중간 코드 시퀀스다.경우에 따라 언어의 특징은 많은 중복된 표현을 만들 수 있다.예를 들어, 매크로 확장이 원래 소스 코드에 나타나지 않는 일반적인 하위 익스프레션을 야기할 수 있는 C 매크로.

컴파일러는 가치를 보유하기 위해 만들어진 임시변통의 수에 대해 신중할 필요가 있다.과도한 수의 임시 값은 레지스터 압력을 발생시켜 레지스터를 메모리에 흘리게 할 수 있으며, 이는 단순히 산술 결과가 필요할 때 다시 계산하는 것보다 더 오래 걸릴 수 있다.

참고 항목

참조

  1. ^ Steven Muchnick; Muchnick and Associates (15 August 1997). Advanced Compiler Design Implementation. Morgan Kaufmann. ISBN 978-1-55860-320-2. Common subexpression elimination.