Java is increasingly gaining acceptance as an application platform for embedded systems. Many of the embedded systems, such as mobile devices and smart cards, have very limited memory spaces. Therefore, reducing memory space required to run Java applications is critical for memory-constrained embedded systems.
In this thesis, we present a static analysis technique for reducing heap space requirements of Java applications. We develop a new data-flow analysis for detecting dead references to objects, which are defined as references that are not removed although they are no longer necessary. Our analysis technique also determines program points where we can remove dead references by assigning null to reference fields. Assigning null to those fields allows a garbage collector to reclaim objects referenced by the fields in a more timely manner, and hence, saves heap space occupied by the objects.
We have implemented our data-flow analysis algorithms for Java applications and applied it to a number of benchmark programs. Guided by the list of dead references and null-assignable program points, we have modified the source code of the benchmark programs. Our experimental results show that space saving up to 8.1% can be achieved, but savings vary from application to application.
Since our analysis may generate false positives, the technique is not applicable to automatic program transformation. However, the results presented in this thesis demonstrate that our analysis is practical for large applications and effective for reducing heap space requirements.
자바는 오늘날 모바일 기기와 스마트 카드와 같은 여러 임베디드 시스템들의 어플리케이션 플랫폼으로 널리 사용되고 있다. 이들 시스템들은 가격과 기기의 크기, 그리고 에너지 소비량 등의 이유 때문에 매우 제한적인 메모리 크기를 가지고 있다. 따라서 자바 어플리케이션을 실행하는데 필요한 메모리의 크기를 줄이는 것은 매우 중요한 문제이다.
이 논문에서는 자바 프로그램이 실행 중에 사용하는 힙(heap)의 크기를 줄일 수 있는 데이터 흐름 분석 기법을 제안한다. 이 기법은 우선 자바 바이트 코드를 정적으로 분석하여 각 메쏘드들에서 필드들이 정의되고 사용되는 방식 ('사용되기 전에 정의될 수 있다', '항상 정의된다' 등)을 알아낸다. 이 정보를 이용하여 더 이상 쓰이지 않음에도 불구하고 필요없이 레퍼런스 값을 유지하는 필드(field) 들을 찾을 수 있고, 더 나아가 필드들의 liveness 분석을 수행하면 각 필드에 null 을 할당할 수 있는 프로그램 포인트(program point)를 찾을 수 있다. 이 분석을 통해 얻은 프로그램 포인트들에서 null을 필드에 할당하면 garbage collector 는 그 필드가 가리키고 있던 객체를 더욱 빨리 회수할 수 있게 되고, 이로 인해 객체들이 차지하는 힙 공간을 줄일 수 있다.
논문에서 제안한 분석 기법을 적용시킨 툴을 개발하여 벤치마크를 위한 자바 프로그램들에 대해 분석을 수행하였다. 분석을 통하여 최대 17%의 레퍼런스 필드들이 필요 없는 레퍼런스 값을 가질 수 있다는 결과를 얻었고, 이 분석 결과를 바탕으로 필드에 null을 할당하거나, 필드를 로컬 변수로 만드는 방식으로 프로그램들을 수정하였다. 이러한 수정을 했을 때 우리는 프로그램이 수행하는 데 필요한 힙의 크기를 최대 8.1%, 평균 4.6% 줄일 수 있음을 알 수 있었다.
이 분석 기법은 거짓 경보(false positives)를 발생시킬 수 있기 때문에 자동적인 프로그램 변형에는 사용할 수 없다. 하지만 이 분석을 통하여 프로그램이 사용하는 메모리 크기를 줄이기 위한 매우 유용한 정보들을 개발자에게 제공할 수 있고, 실험 결과를 통하여 이 기법이 큰 프로그램에 적용 가능하고 힙의 크기를 줄이는 데 어느 정도 효과적임을 알 수 있었다.