Cycle elimination for context-sensitive pointer analysis = 호출 문맥을 고려하는 포인터 분석에서의 사이클 제거 기법

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 389
  • Download : 0
Pointer analysis statically estimates the runtime pointer behavior of a program. It is an important building block of optimizing compilers and program verifiers for C programs. Various approaches with precision and performance trade-off have been proposed. Among them, two recent techniques have enabled precise, yet scalable analyses. One is cycle elimination for subset-based analysis where cyclic inclusion constraints are detected and collapsed without losing any precision. The other is the use of binary decision diagram (BDD) for cloning-based context-sensitive analysis where all non-recursive invocations are analyzed precisely. Redundancies among exponential contexts are shared automatically through BDD-encoding. Also, constraints are encoded and resolved with BDD. However, it has been shown that such fully BDD-based analysis doesn`t work in synergy with cycle elimination. In this thesis, we present a new method on cloning-based context-sensitive pointer analysis with an effective application of cycle elimination. Our method is not based on BDD. Instead, we propose a novel constraint-based formulation with context set annotations. Our constraint resolution rules are formulated entirely with set-level context operations only. So, we always handle contexts in large granularities, which replaces the need for fully BDD-based analysis. For context set representation, we directly use an invocation graph structure without BDD-encoding. Then, we make set operations efficient by applying a folklore structure sharing technique known as hash-consing to the invocation graph. Experimental results on 16 C programs ranging from 20000 to 290000 lines show that applying cycle elimination to our new formulation results in 4.5$\times$ speedup over previous fully BDD-based approach.
Advisors
Choe, Kwang-Mooresearcher최광무researcher
Description
한국과학기술원 : 전산학과,
Publisher
한국과학기술원
Issue Date
2010
Identifier
455452/325007  / 020025308
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 전산학과, 2010.08, [ vi, 78 p. ]

Keywords

C language; cycle elimination; pointer analysis; program analysis; binary decision diagram; 이진 의사결정 다이어그램; C 언어; 사이클 제거 기법; 포인터 분석; 프로그램 분석

URI
http://hdl.handle.net/10203/33324
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=455452&flag=dissertation
Appears in Collection
CS-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0