창 병 모 숙명여대 전산학과 http://cs.sookmyung.ac.kr/~chang 자바 언어를 위한 CFA 창 병 모 숙명여대 전산학과 http://cs.sookmyung.ac.kr/~chang

목차 Higher-order CFA Class analysis Simpler class analyses

Higher-order CFA

Higher-order Flow Analysis Call graphs Many program analyses rely on a call-graph. There is an edge (f,g) if function f calls function g. Call graphs are easy to compute in FORTRAN. Not so easy in higher-order languages functional (ML) object-oriented (Java, C++) pointer-based (C)

Higher-order Control Flow Analysis In a functional language e1 e2 closure analysis [Shivers88] In an object oriented language e.m() class analysis or reference analysis In a pointer language (*p)() pointer analysis In each case it is unclear which function is called.

Class Analysis for Java

Java overview Dynamic binding class analysis Simpler class analyses inheritance and overriding class analysis analysis of object type Simpler class analyses CHA RTA XTA VTA

References and Inheritance An object reference can refer to an object of its class, or an object of any class related to it by inheritance For example, if Christmas extends Holiday Holiday day; day = new Christmas();

References and Inheritance A polymorphic reference one which can refer to one of several possible methods class Holiday { class Christmas extends Holiday { celebrate( ) { … } celebrate( ) { … } } } Now consider the following invocation: day.celebrate();

Dynamic binding How to determine which method is invoked the type of the object being referenced, not the reference type Dynamic binding Polymorphic references are therefore resolved at run-time. Note if an invocation is in a loop, the same line of code could execute different methods at different times

Class Analyses for Java Why class analysis for Java ? the type(class) of the object being referenced determines which method is invoked not the declared reference type The goal to approximate the classes of the objects, to which an expression may refer Also gives an approximation of the call graph

Class Analyses for Java A set variable Xe for each expression e. class names of the objects, to which the expression e may refer Set up set-constraints of the form : Xe Ê se Analysis assigns possible classes of e to Xe Solution of the constraints yield the information

Sample Constraints for Class Analyses Suppose e is each of the following expressions new C | Xe Ê {C} if e0 then e1 else e2 | Xe Ê Xe1 È Xe2 id = e1 | Xid Ê Xe1 Method call e0.m(e1) for each class C in [e0] with a method m(x1) = return em C Î Xe0 Þ Xx1 Ê Xe1 Xe Ê Xem

History in Class Analyses Constraint resolution in O(n3 ) time. This analysis was discovered by Palsberg and Schwartzbach in 1991. closely related to closure analysis for functional programs (Jones,Shivers). Fast interprocedural class analysis by node(set variable) merging Grove and Chambers in ACM POPL’98

Objects and Methods in Java class C { int n; void incr() { n++; } void decr() { n--; } } Method invocation: [[e.m(arg)]] = object * o = [[e]]; lookup(o®vtable, m)(o, [[arg]]) method table void C::incr(this) { this.n++; g} object incr decr Value of n void C::decr(this) { this.n--; }

Objects and Methods in Java Layout of method tables attached to objects based on inheritance hierarchies Transformation of method invocations into method lookups + calls. We can generate a direct call c.m using analysis if that set is a singleton {c} or if all elements in that set have the same implementation of method m

Simpler Class Analyses

CHA(Class Hierarchy Analysis) 클래스 계층구조 정보를 고려한다. 호출 그래프 각 메쏘드 호출 x.m(…) x의 타입 정보 및 클래스 계층구조

RTA(Rapid Type Analysis) 기본 아이디어 클래스 생성(instantiation) 정보를 이용하여 CHA 확장 프로그램 P에 대해서 하나의 집합-변수 Xp 프로그램 내에서 이용 가능한 (추상) 객체들을 포함 호출 그래프 각 메쏘드 호출 x.m(…) x의 타입 정보, 클래스 계층구조와 Xp 이용

XTA 기본 아이디어 호출 그래프 각 메쏘드 M 마다 하나의 집합-변수 XM 각 필드 변수 x 마다 하나의 집합-변수 Xx x의 타입 정보, 클래스 계층구조 와 XM 이용

VTA(Variable Type Analysis) 기본 아이디어 각 참조 변수 x 마다 하나의 집합-변수 Xx 참조 변수 x 가 가리키는 모든 객체 포함 호출 그래프 메쏘드 메쏘드 호출 x.m(…) x의 타입 정보, 클래스 계층구조 와 Xx 이용

Points-to Analysis