사용할 변수의 예측에 사용되는 반복적 알고리즘의 계산순서 재정렬을 통한 수행 속도 개선 = Improvement of Iterative Algorithm for Live Variable Analysis based on Computation Reordering

국문 초록 (Abstract)

기존의 LVA를 수행하는 알고리즘은 반복적 정보흐름분석(Iterative Data Flow Analysis - DFA) 프레임워크에 따라 프로그램 전체를 반복적으로 스캔하면서 진행되어진다. Zephyr[1] 컴파일러의 경우 이와 같은 반복적 알고리즘으로 LVA를 수행하는 시간이 전체 컴파일 시간에서 약 7%를 차지하고 있다.
기존 LVA 알고리즘은 여러 가지로 개선할 점들이 있다. LVA를 수행하는 기존의 반복적 알고리즘은 알고리즘의 특성상 방문하지 않아도 되는 basic block들에 대한 방문이 잦고, 살아있는 변수들의 집합을 점차적으로 증가해 가면서 구하는 특성상 큰 변수들의 집합에 대한 연산을 계속 하게 된다.
우리는 기존의 알고리즘과 달리 사용된 변수들(USE set)에 대해 Control Flow Graph(CFG)에서 거슬러 올라가면서 LVA를 수행하는 반복적인 알고리즘의 개선안을 제안하고자 한다. 이는 기존의 알고리즘과 같은 결과를 내면서 더 빠른 알고리즘이다. DFA에서의 flow equation을 적용하는 순서를 바꿈으로써 많은 중복 계산을 줄일 수 있다. 이러한 방법으로 인해 basic block을 방문해야만 하는 횟수를 줄이면서 전체 수행 시간을 단축시킨다. 간단한 추가 구현만으로 Zephyr 컴파일러에서의 실험 결과에서 LVA만을 수행하는 시간에서 기존의 알고리즘보다 36.4% 짧은 시간을 사용하였고, 이는 전체 컴파일 시간을 2.6% 줄이는 효과를 가져왔다.

다국어 초록 (Multilingual Abstract)

The classical approaches for computing Live Variable Analysis(LVA) use iterative algorithms across the entire programs based on the Data Flow Analysis framework. In case of Zephyr compiler, average execution time of LVA takes 7% of the compilation time for the benchmark programs.
The classical LVA algorithm has many aspects for improvement. The iterative algorithm for LVA scans useless basic blocks and calculates large sets of variables repeatedly.
We propose the improvement of iterative algorithm for LVA based on used variables' upward movement. Our algorithm produces the same result as the previous iterative algorithm. It is based on use-def chain. Reordering of applying the flow equation in DFA reduces the number of visiting basic blocks and redundant flow equation executions, which improves overall processing time. Experimental results say that our algorithm can reduce 36.4% of LVA execution time and 2.6% of overall computation time in Zephyr compiler with benchmark programs.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 기존 Live Variable Analysis 알고리즘
• 4. 기존 Live Variable Analysis 알고리즘의 개선
• 5. 구현 및 실험 결과
• 6. 결론 및 향후 연구 과제
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 J. B. Kam, "pages 305-317" -1977, 3

2 Evelyn Duesterwald, "and Mary Lou Soffa. Reducing the Cost of Data Flow Analysis By Congruence Partitioning. In International Conference on Compiler Construction"

3 Keith D. Cooper, "and Linda Torczon. How to Build an Interference Graph. In Software-Practice and Experience" 1 :

4 Michael P. Gerlek, "and Eric Stoltz. A Reference Chain Approach for Live Variables. Technical Report CSE 94-029"

5 "MediaBench Homepage"

6 Massimiliano Poletto, "Linear Scan Register Allocation" -1999, 5

7 Glenn Ammons, "Improving Data-flow Analysis with Path Profiles." 1998.

8 Keith D. Cooper, "Fast Copy Coalescing and Live-Range Identification" 2002.

9 S. W. K. Tjiang, "A tool for builing optimizers. In SIGPLAN Conference on Programming Language Design and Implementation" 1992.

10 C. Samuel Hsieh, "A fine-grained data-flow analysis framework" 34 (34): -1997, 9

11 Wankang Zhao, "A System for Interactive Code Improvement." 2002.

12 Susan L. Graham,Mark N. Wegman. A Fast, "172-202" 1976-, 1