프로그램 의존성 분석을 위한 포인터 분석기의 구현 = (An) Implementation of Pointer Analysis for Program Dependence Analysis in C Programs

국문 초록 (Abstract)

의존성 그래프(dependence graph)는 컴파일러 최적화 분야에 도입되어 유용하게 사용되고 있으며 또한 프로그램 자르기(program slicing) 분야에서 활용가치가 높은 프로그램 표현 방식이다. 우리는 의존성 그래프를 생성하는 시스템을 구현하였지만 포인터(pointer)가 포함된 프로그램의 의존성 그래프를 생성할 때에는 별칭(alias) 문제로 인하여 잘못된 의존성이 나타나기도 한다. 본 논문에서는 C 언어의 의존성 그래프의 정확성을 높이기 위해 프로그램 흐름을 고려하고 배열의 인덱스와 구조체의 필드를 개별적으로 인식하는 포인터 분석기(pointer analyzer)를 자료 흐름 분석(data flow analysis)법으로 구현하였다. 구현한 포인터 분석기를 적용한 결과 포인터가 포함된 프로그램에서도 정확한 의존성 그래프를 얻을 수 있었다.

다국어 초록 (Multilingual Abstract)

The dependence graph is one of abstract representations of a program for optimization phase in compilation. It is also well known that dependence graphs are useful for program slicing and program analyses. If you build a dependence graph constructor for source codes with pointer variables such as C programs, then you need the alias information of the pointer variables for the resultant graphs not to have unsound dependences for a given source code. This thesis implements a pointer analyzer which is useful for the dependence graph constructor. Our pointer analyzer for C programs is flow-sensitive and handles arrays and structures in a way that data flow analysis deals with indexes of arrays and fields of structures respectively. In result we could use our pointer analyzer to build a dependence graph constructor which accepts C programs with pointer variables.

목차 (Table of Contents)

• 목차 = ⅰ
• 그림목차 = ⅲ
• 요약 = ⅵ
• 제1장 서론 = 1
• 제2장 의존성 그래프 = 4
• 2.1 의존성 그래프의 개념 = 4
• 2.2 SDG 유용성 = 6
• 2.3 포인터 분석의 필요성 = 9
• 제3장 포인터 분석 = 11
• 3.1 배경 지식 = 12
• 3.1.1 별칭 표현 = 13
• 3.1.2 흐름 민감성 = 14
• 3.1.3 분석을 위한 골격 = 16
• 3.2 포인터 분석 = 18
• 3.2.1 실행 경로 구별 = 18
• 3.2.2 Source Alias Set = 19
• 3.2.3 전달 경로 집합 = 23
• 3.3 포인터 분석 구현 = 26
• 3.3.1 별칭 표현을 위한 자료 구조 = 26
• 3.3.2 대입문의 AST 타입 = 27
• 3.3.3 대입문의 AST 예제 = 29
• 3.3.4 구조체 = 33
• 3.3.5 배열 = 41
• 3.3.6 함수 입출력 추적 = 48
• 제4장 결과 및 분석 = 49
• 4.1 순차 구조의 소스 분석 = 49
• 4.2 반복문이 포함된 소스 분석 = 53
• 제5장 결론 = 56
• 참고문헌 = 57
• Abstract = 60
• 부록 = 61
• 부록1. 구현 함수 역할 = 62
• 부록2. analyze_instr 함수 코드 = 65
• 부록3. analyze_lval 함수 코드 = 66
• 부록4. analyze_instr 함수 코드 = 67
• 부록5. 함수 입출력 추적 = 68