실행시간 전문화를 위한 집합기반분석의 준비 = Preparing Set-Based Analysis for Run-time Specialization

국문 초록 (Abstract)

정적 분석을 사용하여 프로그램의 입력에 의존하는 성질을 예측하는 방법을 제안한다. 제안된 방법은 입력에 무관한 성질을 예측하도록 설계된 정적 분석을 입력에 의존하는 성질을 예측하는 분석으로 변환한다. 이 방법은 실행 중에 프로그램의 성질을 알아내기 위해서 실행중인 프로그램을 관찰하는 코드가 필요 없고 계측된 자료를 모으는 과정도 필요 없다.
정적 분석의 가장 마지막 부분을 프로그램의 실행 시간으로 미루는 것이 이 논문의 핵심 아이디어다. 먼저 정적 분석을 분석하여, 프로그램의 입력에 민감하여 프로그램의 실행시간으로 연기되어야 하는 부분을 찾아낸다. 그 후, 값을 자르는 분석을 사용하여 이 부분을 재구성하여 프로그램의 입력에 대한 간단한 멤버쉽 테스트에 의해 분석이 풀어질 수 있도록 한다. 이런 재구성 과정을 통해 준비된 분석들은 프로그램의 입력이 나타나기만 하면 순간적으로, 동시에 풀려질 수 있다.
모든 과정은 엄밀하게 정의되고 증명되었다.

다국어 초록 (Multilingual Abstract)

We present a technique of using static analysis for estimating program's input-dependent properties. A static analysis that is originally designed for estimating the input-independent properties of programs is transformed into one that can safely estimate the input-dependent properties at the programs' input occurrence. No profile is collected and no probing codes inside the running program are needed.
Our ideais to defer the finish of the static analysis to the program's run-time. By analyzing the static analysis, we identify the parts of the analysis that are sensitive to the program's inputs, hence need to be deferred to the program's run-time. Then by using an analysis named static value-slicing, we short-cut some of the dynamic parts so that they are solved by simple membership tests for the program's input. This re-formulation accelerates the analysis; once the program's input occurs the prepared dynamic parts can immediately and simultaneously start to resolve.
Every step of our technique is formally defined and proven correct.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 소스 언어 L
• 3. 출발점 : 집합 기반 분석
• 4. 파생 분석 I: 동적 관계식을 미루자
• 5. 파생 분석 II: 값을 자르는 분석을 통해 동적 관계식을 준비하자
• 6. 관련 연구
• 7. 결론
• 참고문헌
• A. 증명
• 저자소개