코드 모션

Code motion

컴퓨터 과학에서 코드 호스팅, 코드 싱킹, 루프 인바리어트 코드 모션 또는 코드 팩토링이라고도 하는 코드 모션은 성능 또는 크기 편익을 위해 프로그램 내에서 코드를 이동하는 모든 프로세스의 포괄적 용어로서, 대부분의 최적 컴파일러에서 수행되는 공통 최적화다.코드 모션을 둘러싼 용어의 일관성 없는 의미 때문에 다른 유형의 코드 모션을 구별하기가 어려울 수 있다.

사용하다

코드 모션은 다양한 용도와 이점을 가지고 있으며, 그 중 상당수는 구현 과정에서 서로 중복된다.

사용되지 않거나 사용하지 않는 작업 제거

최적 컴파일러가 조립 지침 "b"에 대한 잠재적으로 쓸모없는 호출을 사용 지점으로 가라앉혀 제거하는 것을 그린 다이어그램.

게으른 코드 동작으로도 알려진 코드 싱킹은 명령을 사용하는 분기로 이동하여 낭비되는 명령을 줄이는 기법의 용어다.[1]분기 전에 작업이 실행되고 분기 경로 중 하나만 해당 작업의 결과를 사용하는 경우, 코드 싱킹은 해당 작업을 사용할 분기로 이동하는 것을 수반한다.

이 기법은 결과가 폐기되거나 사용되지 않을 때 코드를 제거한다는 점에서 데드 코드 제거의 한 형태지만, 데드 코드 제거와는 대조적으로 실행 코드 경로에서 그 명령의 결과의 사용 가능성이 있더라도 무의미한 지시를 제거할 수 있다.

프로그램 크기 축소

모든 작업이 이전에 실행 중인 다른 작업에 종속되지 않는다고 가정하는, 코드 팩토링을 사용하여 크기를 최적화하는 것을 보여주는 다이어그램.

코드 팩토링(Code Factoring)은 분기의 공통 의존성을 그 위의 분기로 병합하는 크기 최적화 기법의 용어다.[2]인자를 인수하는 정수가 숫자를 가능한 가장 작은 형태(요인)로 분해하는 것과 마찬가지로, 코드인자는 복제가 남아 있지 않을 때까지 공통의 "인자"를 병합하여 가능한 가장 작은 형태로 코드를 변환한다.

종속성 스톨 감소

주요 기사:지시 스케줄링
컴파일러가 의존성 그래프를 관찰함으로써 코드 이동과 함께 조립된 코드에서 종속성을 방지하는 방법의 예.비질서한 실행 발전으로 인해 최적화는 현대 CPU에 아무런 이점이 없을 수 있다.

글로벌 코드 모션, 로컬 코드 모션, 코드 스케줄링, 명령 스케줄링, 코드 호이스트/싱킹은 모두 CPU 내에서 실행의 효율성을 향상시키기 위해 지침을 재배열(또는 "예약")하는 기법의 용어다.[3][4] 현대의 CPU는 클록 사이클당 5개 이상의 지시사항을 스케줄링할 수 있다.그러나 CPU는 현재(또는 아직 실행되지 않은) 명령의 데이터에 의존하는 명령을 스케줄링할 수 없다.컴파일러는 CPU가 임의의 시점에서 처리할 수 있는 명령의 양을 최대화하는 방식으로 의존성을 상호 유지한다.[5]

소멸된 Intel Itanium 아키텍처에서 분기 예측(BRP) 명령은 컴파일러에 의해 분기 위로 수동으로 호스팅되어 분기가 CPU에 의해 즉시 취해질 수 있다.Itanium은 프로세서의 효율성을 극대화하기 위해 CPU의 추가 코드 스케줄링에 의존한다.[6]

루프-상변형 코드 운동

주요 기사:루프-상변형 코드 운동
실행 그래프에 대한 루프 내 변위 코드 동작을 나타내는 다이어그램.이것은 D가 루프 실행 사이에 불변한다고 가정한다.

루프-상변형 코드 동작은 루프-상변형 코드를 루프 외부의 위치로 이동하는 과정으로, 동일한 결과에 대해 일부 계산이 두 번 수행되는 것을 방지하여 루프의 실행 시간을 단축시킬 수 있다.

컴파일러 예제

LLVM

LLVM은 단일 정적 할당 양식에 싱킹 패스가 있다.LLVM 15.0은 코드 경로 중 하나라도 스토어 지침을 포함하거나 오류를 발생시킬 수 있는 경우 작동을 중지하지 않는다.[7]또한 LLVM은 명령을 루프에 침몰시키지 않는다.

GCC

GNU 컴파일러 컬렉션은 컴파일된 프로그램의 크기를 줄이기 위한 목적으로 "코드 팩터링"이라는 이름으로 코드 모션을 구현한다.[8]GCC는 "기존의존속성을 무효화하거나 새로운 것을 도입하지 않는다"고 하면 어떤 코드도 위아래로 이동시킬 것이다.[9]

루아지트

LuaJIT는 "Allocation saming"이라는 이름으로 코드 싱킹을 사용하여 컴파일된 코드가 루프 내에서 임시 객체를 할당하고 수집하는 데 소비하는 시간을 줄인다.[10]할당 싱킹은 할당된 개체가 실행 코드를 벗어날 수 있는 실행 경로로 할당을 이동하므로 힙 할당이 필요하다.제거된 모든 할당은 해당 필드에 대한 로드-투 스토어 포워딩으로 채워진다.[11]

참고 항목

참조

  1. ^ Craft, Michael; Offut, Jefferson (1994). "Using compiler optimization techniques to detect equivalent mutants". Software: Testing, Verification, and Reliability. 4 (3): 131–154. Retrieved 25 February 2022.
  2. ^ 로키, 가보르 등2004년 GCC 개발자 서밋 진행2004.
  3. ^ 파세, 저스터스 등CompCert에서 사전 예약 기회를 높이기 위한 코드 변환.디스. 과학 석사 논문.우니베르시테 그레노블 알페스https://whatw-verimages.imag. fr/~boulme/CPP_2022/FASSE-Justus-MSC-Esistance_2021. pdf, 2021.
  4. ^ Gupta, Rajiv (1998). "A code motion framework for global instruction scheduling". Compiler Construction: 219–233.
  5. ^ 장, 포화 P, 기타"슈퍼스칼라 및 슈퍼파이프라인 프로세서에 대한 사전 코드 스케줄링의 중요성." IEEE Transactions on Computers 44.3 (1995): 353-370
  6. ^ Sharangpani, H.; Arora, H. (September 2000). "Itanium processor microarchitecture". IEEE Micro. 20 (5): 24–43. doi:10.1109/40.877948. ISSN 1937-4143.
  7. ^ "LLVM: lib/Transforms/Scalar/Sink.cpp Source File". llvm.org. Retrieved 25 February 2022.
  8. ^ "Code Factoring Optimizations - GNU Project". gcc.gnu.org. Retrieved 25 February 2022.
  9. ^ "GCC Developer's Summit 2004 - Code Factoring.pdf" (PDF). gnu.org. Retrieved 25 February 2022.
  10. ^ "Allocation sinking in git HEAD - luajit - FreeLists". www.freelists.org. Retrieved 25 February 2022.
  11. ^ "Allocation Sinking Optimization". wiki.luajit.org.