루프-상변형 코드 운동

Loop-invariant code motion

컴퓨터 프로그래밍에서 루프 인바리어 코드는 프로그램의 의미론에 영향을 주지 않고 루프 본체 밖으로 이동할 수 있는 문이나 표현식(필수 프로그래밍 언어)으로 구성된다.루프 인바리어트 코드 모션(호스팅 또는 스칼라 프로모션이라고도 함)은 이 동작을 자동으로 수행하는 컴파일러 최적화다.

예

다음 코드 샘플에서는 두 가지 최적화를 적용할 수 있다. 

인트로 i = 0; 하는 동안에 (i < n) {     x = y + z;     a[i] = 6 * i + x * x;     ++i; }

비록 계산은 했지만x = y + z그리고x * x루프-유동성(loop-silariant)이며, 코드를 루프 외부로 이동하기 전에 주의해야 한다.루프 상태가false(예를 들어, ifn음의 값을 가지며, 이 경우 루프 본체는 전혀 실행되지 않아야 한다.올바른 행동을 보장하는 한 가지 방법은 루프 외부의 조건부 분기를 사용하는 것이다.루프 조건을 평가하면 부작용이 생길 수 있으므로, 이 경우, 이 경우, 이들에 의한 추가 평가가 필요하다.if구성 요소는 다음 구성 요소를 교체하여 보상해야 한다.while고리를 끼우다do {} while. 코드가 사용된 경우do {} while애초에 루프 본체가 적어도 한 번은 실행될 수 있도록 보장되기 때문에 전체 경비절차가 필요하지 않다. 

인트로 i = 0; 만일 (i < n) {     x = y + z;     인트로 경시하다 t1 = x * x;     하다 {         a[i] = 6 * i + t1;         ++i;     } 하는 동안에 (i < n); }

이 코드는 더 최적화될 수 있다.예를 들어, 강도 감소는 루프 내부의 두 배수를 제거할 수 있다.6*i그리고a[i]() 유도 가변 제거가 용출될 수 있음i완전히이후6 * i와 보조가 맞아야 한다i둘 다 가질 필요는 없다. 둘 다 가질 필요는 없다.

불변 코드 탐지

일반적으로 도달 정의 분석은 문이나 식이 루프 불변성인지 여부를 탐지하는 데 사용된다.

예를 들어, 어떤 단순한 표현식의 피연산자에 대한 모든 도달 정의가 루프 외부에 있는 경우, 표현은 루프 밖으로 이동될 수 있다.

데이터 흐름의존성 분석을 이용한 최근의 연구는 불변 명령뿐만 아니라 내부 루프와 같은 더 큰 코드 조각도 검출할 수 있다.이 분석은 또한 임의 수준의 준항변제, 즉 루프 본체의 일정한 반복 횟수가 지나면 불변하게 되는 명령이나 코드 조각도 검출한다.

혜택들

루프에서 호스팅된 루프 인바리어트 코드는 보다 자주 실행되지 않아 속도 증가를 제공한다.이 변환의 또 다른 효과는 상수를 레지스터에 저장할 수 있게 하고 각 반복에서 주소를 계산하고 메모리(또는 캐시 라인)에 액세스할 필요가 없다는 것이다.

그러나 변수가 너무 많이 생성되면 특히 32비트 x86처럼 레지스터가 거의 없는 프로세서에 높은 레지스터 압력이 발생한다.컴파일러의 레지스터가 부족하면 일부 변수가 쏟아진다.이를 상쇄하기 위해 역최적화, 재물질화를 수행할 수 있다.

참고 항목

추가 읽기

  • 아호, 알프레드 5세; 세티, 라비; & 울만, 제프리 D. (1986)컴파일러: 원칙, 기술 및 도구.애디슨 웨슬리 ISBN0-201-10088-6.

참조

  1. ^ Moyen, Jean-Yves; Rubiano, Thomas; Seiller, Thomas (2017). "Loop Quasi-Invariant Chunk Detection". Automated Technology for Verification and Analysis. Lecture Notes in Computer Science. 10482: 91–108. doi:10.1007/978-3-319-68167-2_7. ISBN 978-3-319-68166-5.

외부 링크