13_LLVM IR 최적화하기

1. 최적화 명령어

opt -passes='instcombine,dce,gvn,dse' -S pythonArray.ll -o testOptimized.ll

opt 명령어를 사용하면 llvm 내장에 있는 패스를 추가하여 ir을 최적화할 수 있다.

-passes='pass이름'으로 사용할 수 있다.

-S 옵션은 .ll 파일에 텍스트 형태로 저장해주는 역할을 한다.

---

2. 사용한 최적화 내장 pass

최적화 내장 pass는 LLVM 공식문서(https://llvm.org/docs/Passes.html) 에서 확인할 수 있다.

LLVM’s Analysis and Transform Passes — LLVM 18.0.0git documentation

instcombine: Combine redundant instructions

명령어를 결합하여 더 적은 수의 간단한 명령어를 만든다.

 

-dce: Dead Code Elimination

사용되지 않는 코드를 제거하여 프로그램 크기를 줄이고 실행 속도를 향상시킨다.

 

-gvn: Global Value Numbering

중복 연산을 식별하고 공통 부분 식을 하나의 값으로 대체하여 코드 중복을 제거한다.

 

-dse: Dead Store Elimination

프로그램의 불필요한 변수 할당을 제거하여 코드를 더 효율적으로 만든다.

 

해당 방법으로 300줄에서 177줄까지 줄일 수 있었다.

해당 방법으로 300줄에서 162줄까지 줄일 수 있었다.

이 패스 순서대로 추가해야 코드 길이가 가장 줄어들었다.

---

3. 시도해보았지만 추가하지 않은 내장 Pass

이외에 loop-deletion, inline, deadargelim, globalopt, globaldce, constmerge, strip-nondebug, strip-dead-prototypes,  instcombine, adce 패스들을 추가해보았었지만 결과엔 추가하지 않았다.

이 패스들을 추가했었던 이유는, 지금까지 봐왔던 ir은 코드가 상당히 길고, 사용하지 않는 변수들을 추가했으며, 중복인 코드와 예외처리 코드가 많았다. 이러한 코드를 제거하기 위해 관련된 패스들을 추가해본 것이다.

 

각 패스들을 추가 결과와 함께 살펴볼 것이다.

 

 

loop-deletion

Dead Loop Deletion Pass를 구현한다. 이 패스는 부작용이나 휘발성 명령이 없고 함수의 반환 값 계산에 기여하지 않는 무한하지 않은 계산 가능한 트립 횟수가 있는 루프를 제거하는 역할을 한다.

해당 패스를 추가해도 코드 변화가 없어서 추가하지 않았다.

 

inline

함수를 인라인화한다. 함수 호출을 피하고 해당 함수의 본문으로 대체하는 역할을 한다.

해당 패스를 추가해도 코드 변화가 없어서 추가하지 않았다.

 

deadargelim

내부 함수에서 죽은 인자를 삭제한다. 죽은 인자 제거는 다른 함수의 죽은 인자로 함수 호출에만 전달된 인자뿐만 아니라 직접적으로 죽은 인수를 제거한다.

해당 패스를 추가해도 코드 변화가 없어서 추가하지 않았다.

 

globalopt

주소를 가져오지 않는 간단한 전역 변수를 변환한다.

좌 globalopt 추가 / 우 globalopt 추가 X

해당 패스를 추가하면 코드 길이는 변화가 없고, 위 사진처럼 변수명이 추가되는 것 같았다.

코드 길이에 변화를 주지 않아 추가하지 않았다.

 

globaldce

프로그램에서 도달할 수 없는 내부 전역을 제거한다. aggressive algorithm을 사용하여 필요한 전역 변수를 모두 찾은 후 남은 항목을 삭제한다. 이를 통해 도달할 수 없는 재귀를 제거할 수 있다.

해당 패스를 추가해도 코드 변화가 없어 추가하지 않았다.

 

constmerge

중복 전역 상수를 공유되는 단일 상수로 병합한다.

해당 패스를 추가해도 코드 변화가 없어 추가하지 않았다. 살펴보던 ir에는 전역 상수가 없었으니 당연한 결과일지도 모르겠다.

 

strip-nondebug

이 패스는 코드 스트리핑을 구현한다. 특히 가상 레지스터의 이름, 내부 전역 및 함수에 대한 기호, 디버그 정보를 삭제할 수 있다.

해당 패스를 추가하면 코드 길이가 한 줄 줄어들지만, 그건 entry 브랜치 기호가 사라져서 그런 것 같다. 결과를 살펴보면 브랜치 이름들이 전부 숫자로 바뀌어있다.

해당 패스의 경우 코드의 가독성을 훨씬 떨어뜨린다고 기재되어있어 추가하지 않았다.

좌 strip-nondebug 추가 / 우 strip-nondebug 추가 X

 

strip-dead-prototypes

이 패스는 입력 모듈의 모든 함수를 반복하여 죽은 선언을 찾아 제거한다. 즉, 사용하지 않는 라이브러리 함수 선언을 제거한다.

해당 패스를 추가해도 코드 변화가 없어 추가하지 않았다.

---

4. 정리하면서 알게 된 점

이 패스들을 정리하면서 instcombine 을 추가하면 15줄이 더 줄어든다는 것을 알게 된 건데,

해당 패스를 추가했을 경우 가장 두드러지게 보인 점은 switch문에서 해당 인덱스에 있는 값을 추출하는 코드를 제거한다는 것이다.

전에 이 패스를 추가했을 때 분명 코드 길이에 변화가 없었어서 시도했지만 추가하지 않은 패스 목록에 정리해둔 것이었는데 순서를 바꾸어 추가해보니 코드의 길이가 줄어들었다.

내장 패스를 추가할 때 순서가 영향을 미친다는 것을 알게 되었다.

---

5. 더 해야 할 일

또, plugin 개발 시도를 위해 llvm을 다운 받고, 코드를 작성해보려고 했지만 모든 cpp 파일에서 헤더의 위치를 찾지 못 하고 오류가 발생해서 아직 해결하지 못 했다.

위에서 사용한 내장 Pass를 추가하는 코드와 Z3를 사용하는 코드만 생성하면 되는데 쉽지 않은 것 같다.

프로젝트가 커서 빌드하는 데에도 시간이 오래 걸린다......... C++이 좀 낯설기도 해서 더 어려운 것 같다.