DFA 패턴 매칭을 위한 코드 최적화기의 자동적 생성
Automatic Generation of Code Optimizer for DFA Pattern Matching
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
주어진 입력 프로그램과 의미적으로 동등하면서 좀 더 효율적인 코드로 바꾸는 것을 코드 최적화라 하며, 이런 과정은 코드 최적화기에 의해 수행된다. 본 논문에서는 코드 최적화기를 자동적으로 생성하는 도구인 코드 최적화기 생성기를 설계하고 구현하였다. 즉, 패턴 형식에 대한 표현을 입력으로 받아 기술된 형태의 최적화 코드를 찾아내는 DFA 패턴 매칭을 위한 코드 최적화기를 자동적으로 생성하는 것이다. DFA 패턴 매칭은 패턴들의 정규화 과정을 통해 패턴 검색 시 발생하는 중복 비교를 제거하여, 패턴 형태의 단순화 및 구조를 개선함으로 비용이 적게 든다. DFA 패턴 매칭을 위한 코드 최적화기의 자동적 생성은 다양한 형태의 중간코드로 바뀌더라도 해당하는 코드 최적화기를 만들어야 하는 수고를 덜어줌으로써 코드 최적화에 대한 정형화(formalism)를 할 수 있다. 또한, DFA로 구성되어 최적화를 하기 때문에 최적화 속도가 빠르고, 코드 최적화기를 만드는데 필요한 시간과 비용을 절약할 수 있는 장점을 가진다.
Abstract
Code Optimization is converting to a code that is equivalent to given program but more efficient, and this process is processed in Code Optimizer. This paper designed and processed Code Optimizer Generator that automatically generates Code Optimizer. In other words, Code Optimizer is automatically generated for DFA Pattern Matching which finds the optimal code for the incoming pattern description. DFA Pattern Matching removes redundancy comparisons that occur when patterns are sought for through normalization process and improves simplification and structure of pattern shapes for low cost. Automatic generation of Code Optimization for DFA Pattern Matching eliminates extra effort to generate Code Optimizer every time the code undergoes various transformations, and enables formalism of Code Optimization. Also, the advantage of making DFA for optimization is that it is faster and saves cost of Code Optimizer Generator.
참고문헌 (14)
- A. V. Aho, "LR Parsing", pp.99~124 (1974)
- Fraser, "“Automatic Generation of Fast Optimizing Code Generators ” Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation", pp.79~84 (1988)
- Christopher W. Fraser, "Finite- State Code Generation", 34(5), pp.270~280 (1999)
- David A, "“The design of a parser generator ” Proceedings of the 16th annual Southeast regional conference", pp.82~86 (1978)
- Diomidis, "Declarative Peephole Optimization using String Pattern Matching", 34(2), pp.47~51 (1999)
- Fabrice Le Fessant, "Optimizing Pattern Matching", 36(10), pp.26~37 (2001)
- Ancona, "“Efficient Construction of LR", pp.150~178 (1991)
- Cattell, "“Automatic Derivation of Code Generators from Machine Descriptions", pp.173~190 (1980)
- Rudolf Landwehr, "“Experience with an Automatic Code Generator Generator", pp.56~66 (1982)
- Sunglim Yun, "Table-Driven Code Optimizer", pp.59~63 (2005)
- Thomas E, "“Optimization Aspects of Compiler-Compilers", pp.10~17 (1970)
- 오세만, "컴파일러 입문 개정판" (2004), 정익사, 서울
- 윤성림, "패턴 테이블을 이용한 코드 최적화", 8(11), pp.1556~1564 (2005)
- 윤성림, "DFA를 이용한 코드 최적화", 12(1), pp.523~526 (2005)