Idempotent Slices with Applications to Code-Size Reduction

이 논문은 일반 제어 흐름 그래프에 적용 가능한 건전하고 효율적인 GSA 기반 멱등성 역 슬라이스 추출 알고리즘을 제안하고, 이를 활용하여 비연속 명령어들을 병합하는 희소 코드 크기 축소 최적화 기법을 통해 특정 벤치마크에서 최대 7.24% 의 코드 크기 감소를 달성함을 보여줍니다.

핵심

🍳 요리 레시피와 '반복되는 맛' (핵심 아이디어)

컴퓨터 프로그램은 요리 레시피와 비슷합니다. "재료 (데이터) 를 넣고, 섞고, 굽고"라는 일련의 명령어들이 모여서 최종 요리를 만들어내죠.

이 논문은 **"어떤 요리의 맛을 내는 데 꼭 필요한 재료와 과정만 따로 떼어내서, 그걸 '공통 레시피'로 만들어 여러 번 쓰면 어떨까?"**라고 묻습니다.

예를 들어, "김치찌개"를 만들 때, "김치 다지기"와 "양념 섞기" 과정이 100 번이나 반복된다고 칩시다. 보통은 100 번마다 그 과정을 다시 적어두죠. 하지만 이 논문은 **"이 '김치 다지기 + 양념 섞기' 과정은 매번 똑같은 결과를 내니까 (이를 '멱등성'이라고 합니다), 이걸 따로 '김치 준비'라는 작은 함수로 만들어서 100 번 호출하게 하면 어떨까?"**라고 제안합니다.

🧩 기존 방법의 한계 (왜 새로운 게 필요한가요?)

과거에도 비슷한 시도가 있었습니다. 하지만 그 방법들은 두 가지 큰 문제가 있었습니다.

1. 너무 단순한 생각: "이 과정이 반복되니까 뺄 수 있겠지?"라고 생각하다가, 실제로는 그 과정이 다른 복잡한 조건 (예: "만약 불이 너무 세다면..." 같은 분기) 에 따라 달라지는 경우를 놓쳐서, 프로그램을 망가뜨리는 실수를 저지르곤 했습니다.
2. 연속된 부분만 찾음: "A, B, C, D"처럼 줄줄이 이어진 명령어만 찾아냈습니다. 하지만 실제 프로그램에서는 "A... (다른 작업)... B... (다른 작업)... C"처럼 중간에 다른 작업이 끼어 있어도, A, B, C 만 합치면 똑같은 결과가 나오는 경우가 많습니다. 기존 방법은 이런 '잘게 쪼개진' 반복을 찾아내지 못했습니다.

🛠️ 이 논문의 해결책: '게이트'가 달린 지도 (GSA 형식)

이 연구팀은 프로그램을 분석할 때, **"게이트 (문) 가 달린 지도"**를 사용했습니다.

• 기존 지도 (SSA): "여기서 A 와 B 가 합쳐집니다"라고만 적혀 있어서, 어떤 조건으로 합쳐지는지 알 수 없었습니다.
• 새 지도 (GSA): "A 와 B 가 합쳐지는데, 문 (게이트) 이 열려있을 때만 A 가 들어옵니다"라고 정확히 적어줍니다.

이 '게이트'를 통해 연구팀은 **"이 과정은 어떤 조건이든 상관없이, 똑같은 입력을 받으면 항상 똑같은 결과만 내놓는다"**는 것을 100% 확신할 수 있게 되었습니다. 그래서 안전하게 그 부분을 잘라내서 따로 만들 수 있게 된 것입니다.

📉 실제 효과: 옷장 정리 (코드 크기 감소)

이 기술을 적용해서 실험해 보니 놀라운 결과가 나왔습니다.

• 옷장 정리: 2,000 개가 넘는 프로그램 (옷장) 을 정리했습니다.
• 결과: 특정 프로그램에서는 코드 크기가 12% 이상 줄어들었습니다. (마치 옷장에서 불필요한 옷을 버리고, 같은 옷을 하나로 통합한 것과 같습니다.)
• 특이점: 기존 방법들이 찾지 못했던, 중간에 다른 작업이 끼어 있는 복잡한 반복 패턴도 찾아내서 정리해냈습니다.

⚖️ 장단점 (무슨 대가가 있나요?)

• 장점: 프로그램이 작아져서 저장 공간을 아끼고, 메모리 효율이 좋아집니다. (특히 'GlobalDataFlow-dbl' 같은 프로그램은 실행 속도도 빨라졌습니다.)
• 단점: 이 정리를 하는 과정 (컴파일 시간) 이 평소보다 약 4% 정도 더 걸립니다. 하지만, 한 번만 정리하면 프로그램이 작아지고 실행될 때 이득을 보므로, 개발 단계에서 약간의 시간이 더 걸리는 것은 감수할 만하다고 말합니다.

🎯 결론: "함께 쓰면 더 강력해집니다"

이 논문은 "이 새로운 방법 (SBCR) 이 기존 방법들 (IROutliner, FMSA) 보다 무조건 더 낫다"고 주장하지 않습니다. 대신, **"이 세 가지 방법은 서로 다른 옷을 찾아내는 안목을 가지고 있다"**고 말합니다.

• IROutliner: 연속된 옷을 찾습니다.
• FMSA: 비슷한 패턴의 옷을 찾습니다.
• 이 논문 (SBCR): 중간에 다른 옷이 끼어 있어도, 핵심만 따지면 같은 옷인 것을 찾습니다.

이 세 가지를 순서대로 적용하면, 기존에 못 찾던 옷까지 찾아내서 최대 14% 까지 코드 크기를 줄일 수 있다는 것이 결론입니다.

💡 한 줄 요약

**"컴퓨터 프로그램 속에 숨겨진 '똑같은 맛'을 내는 복잡한 과정들을 찾아내어, '공통 레시피'로 만들어 반복 사용을 줄임으로써 프로그램을 더 작고 효율적으로 만드는 새로운 정리 기술"**입니다.

기술 요약

1. 문제 정의 (Problem)

• 배경: 프로그램의 특정 값 (변수) 을 계산하는 데 필요한 최대 부분 프로그램을 "멱등성 후방 슬라이스 (Idempotent Backward Slice)"라고 정의합니다. 이는 동일한 입력에 대해 항상 동일한 결과를 내고, 프로그램의 가시적 상태를 변경하지 않는 (부작용이 없는) 코드 조각입니다.
• 기존 연구의 한계: Guimaraes 와 Pereira [10] 는 LLVM 중간 표현 (IR) 에서 'eager' 평가를 'strict' (lazy) 평가로 변환하기 위해 멱등성 슬라이스를 사용했습니다. 그러나 그들의 알고리즘은 두 가지 주요 상황에서 실패했습니다.
  1. 전통적 SSA 속성 (CSSA) 을 만족하지 않는 경우: $\phi$-함수와 관련된 변수의 라이브 범위가 겹치는 프로그램에서 슬라이스를 추출하지 못함.
  2. 특정 제어 흐름 구조 (Hammock 구조가 아님): 단일 진입/단일 종료 (Single-Entry-Single-Exit) 영역으로 분해되지 않는 복잡한 제어 흐름 그래프 (CFG) 에서 슬라이스를 잘못 식별하거나 누락함.
• 목표: 이러한 결함을 보완하여, 일반 CFG 와 GSA(Gated Static Single Assignment) 형식을 기반으로 정확하고 (Sound) 효율적인 멱등성 슬라이스 추출 알고리즘을 개발하고, 이를 활용한 코드 크기 감소 최적화를 수행하는 것입니다.

2. 방법론 (Methodology)

2.1 멱등성 후방 슬라이스 (Idempotent Backward Slices)

• 정의: 슬라이스 기준 (criterion) 변수 $v$에 대해, $v$를 계산하는 모든 데이터 및 제어 의존성을 포함하되, 슬라이스 내부에서 정의된 변수가 외부 루프를 벗어나지 않도록 제한된 부분 프로그램을 의미합니다.
• GSA(Gated SSA) 형식 활용:
  • 기존 SSA 는 $\phi$-함수만 사용하여 데이터 의존성은 명시하지만 제어 의존성은 암시적입니다.
  • 이 논문은 Tu 와 Padua [22] 의 알고리즘을 사용하여 GSA 형식을 구축합니다. GSA 는 $\phi$-함수를 $\gamma$-함수 (분기 조건 명시), $\mu$-함수 (루프 헤더), $\eta$-함수 (값 게이트) 로 대체하여 데이터와 제어 의존성을 모두 명시적으로 표현합니다.
  • 이를 통해 슬라이스 추출 시 제어 흐름을 정확히 추적할 수 있게 됩니다.

2.2 슬라이스 식별 알고리즘

• 알고리즘: GSA 형식으로 변환된 프로그램에서 기준 변수 $v$에 대해 **후방 의존성 그래프 (Backward Dependence Graph)**를 탐색합니다.
• 중단 조건 (Stop Criteria):
  1. 루프 제한: 슬라이스는 기준 변수가 정의된 루프를 벗어날 수 없습니다. (루프 깊이가 다른 $\mu$-함수나 더 낮은 깊이의 변수에서 탐색 중단)
  2. 함수 제한: 슬라이스는 함수 경계를 넘지 않습니다. (함수 인자는 중단 지점)
• 복원: 추출된 슬라이스 영역은 "Attraction" 및 "Transposition" 규칙을 적용하여 단일 진입 (Single-Entry) 을 가진 독립적인 함수로 재구성됩니다.

2.3 슬라이스 기반 코드 크기 감소 (SBCR)

• 프로세스:
  1. 프로그램 내 멱등성 슬라이스 식별.
  2. 식별된 슬라이스를 별도의 함수로 분리 (Outlining).
  3. 동일한 슬라이스 (Isomorphic Slices) 식별: LLVM 의 mergefunc 패스를 활용하여 구조적으로 동일한 함수들을 찾습니다.
  4. 병합 및 비용 모델 적용: 중복된 슬라이스 함수를 하나로 병합하고, 원본 코드를 함수 호출로 대체합니다.
• 비용 모델 (Cost Model): 슬라이스 분리 및 병합이 코드 크기를 줄이는지 판단하기 위해 3 가지 파라미터를 사용합니다.
  • $I$: 슬라이스의 명령어 개수 (제한: 3 < $I$ $\le$ 20)
  • $P$: 함수 인자 개수 (제한: $P \le$ 1)
  • $C$: 슬라이스 발생 횟수 (제한: $C \ge$ 10)
  • 이 모델은 불필요한 함수 호출 오버헤드가 발생하는 것을 방지합니다.

3. 주요 기여 (Key Contributions)

1. 정형화된 멱등성 슬라이스 정의: 기존 알고리즘이 놓쳤던 복잡한 제어 흐름 (Hammock 구조가 아닌 경우) 과 CSSA 가 아닌 프로그램에서도 정확한 슬라이스를 추출할 수 있는 이론적 기반을 마련했습니다.
2. GSA 기반 효율적 알고리즘: GSA 형식을 활용하여 데이터와 제어 의존성을 통합적으로 처리함으로써, 선형 시간 (Linear time) 에 슬라이스를 식별하고 추출하는 알고리즘을 제시했습니다.
3. 새로운 코드 크기 최적화 (SBCR): 기존 방법론 (IROutliner, FMSA) 과는 달리, 비연속적인 (non-contiguous) 명령어 시퀀스나 루프 내부의 코드를 슬라이스로 추출하여 병합할 수 있는 새로운 최적화 기법을 제안했습니다.
4. LLVM 구현 및 평가: LLVM 17.0.6 에 패치를 적용하여 2,007 개의 테스트 프로그램 (LLVM Test Suite) 에서 광범위한 실험을 수행했습니다.

4. 실험 결과 (Results)

• 코드 크기 감소:
  • 특정 벤치마크 (최적화된 -Os 플래그 적용 프로그램) 에서 최대 -7.24% 의 .text 섹션 크기 감소를 달성했습니다.
  • 가장 큰 개선은 AMGmk 벤치마크에서 **-12.49%**의 감소 효과를 보였습니다.
  • 기존 기법 (IROutliner, FMSA) 은 이 특정 벤치마크에서 각각 -0.94%, -5.59% 의 감소만 보였습니다.
• 상호 보완성: SBCR 은 기존 기법들과 중복되지 않으며, 서로 다른 중복 패턴을 발견합니다. 세 기법을 결합 (IROutliner $\to$ SBCR $\to$ FMSA) 했을 때, **명령어 수 기준 -14.43%**의 추가 감소 효과를 확인했습니다.
• 실행 시간 및 컴파일 오버헤드:
  • 실행 시간에는 통계적으로 유의미한 저하가 없었으며, 일부 벤치마크에서는 캐시 국소성 (Locality) 향상으로 인해 성능이 개선되기도 했습니다.
  • 컴파일 시간은 평균 4.22% 증가했으나, 전체 컴파일 파이프라인 대비 수용 가능한 수준입니다.
  • 이론적으로는 $O(N^2)$의 복잡도를 가지나, 실제 벤치마크에서는 슬라이스 크기가 작고 조건을 만족하는 슬라이스가 적어 **거의 선형 (Near-linear)**으로 확장되는 것을 확인했습니다.

5. 의의 및 결론 (Significance)

• 새로운 중복성 단위: 멱등성 슬라이스는 "참조 투명성 (Referential Transparency)"을 가진 계산 단위로, 기존에 발견되지 않았던 미세한 (fine-grained) 중복 코드를 효과적으로 제거할 수 있습니다.
• 범용성: 단일 진입/단일 종료 구조에 국한되지 않고, 루프 내부나 복잡한 분기 구조를 가진 코드에서도 안전하게 슬라이스를 추출할 수 있습니다.
• 미래 작업: 과도한 슬라이스 추출로 인한 코드 크기 증가를 방지하기 위한 비용 모델의 정교화와 프로파일 가이드 최적화 (PGO) 와의 통합이 향후 과제로 제시되었습니다.

이 논문은 컴파일러 최적화 분야에서 GSA 형식을 슬라이싱의 기초로 활용한 최초의 체계적인 접근법 중 하나이며, 코드 크기 감소에 있어 기존 기술들의 한계를 극복하는 강력한 대안을 제시합니다.