DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Choe, Kwang-Moo | - |
dc.contributor.advisor | 최광무 | - |
dc.contributor.author | Choi, Woong-Sik | - |
dc.contributor.author | 최웅식 | - |
dc.date.accessioned | 2011-12-13T05:27:49Z | - |
dc.date.available | 2011-12-13T05:27:49Z | - |
dc.date.issued | 2010 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=455452&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/33324 | - |
dc.description | 학위논문(박사) - 한국과학기술원 : 전산학과, 2010.08, [ vi, 78 p. ] | - |
dc.description.abstract | 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. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | C language | - |
dc.subject | cycle elimination | - |
dc.subject | pointer analysis | - |
dc.subject | program analysis | - |
dc.subject | binary decision diagram | - |
dc.subject | 이진 의사결정 다이어그램 | - |
dc.subject | C 언어 | - |
dc.subject | 사이클 제거 기법 | - |
dc.subject | 포인터 분석 | - |
dc.subject | 프로그램 분석 | - |
dc.title | Cycle elimination for context-sensitive pointer analysis | - |
dc.title.alternative | 호출 문맥을 고려하는 포인터 분석에서의 사이클 제거 기법 | - |
dc.type | Thesis(Ph.D) | - |
dc.identifier.CNRN | 455452/325007 | - |
dc.description.department | 한국과학기술원 : 전산학과, | - |
dc.identifier.uid | 020025308 | - |
dc.contributor.localauthor | Choe, Kwang-Moo | - |
dc.contributor.localauthor | 최광무 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.