An automatic object inlining optimization and its evaluation

Automatic object inlining [19, 20] transforms heap data structures by fusing parent and child objects together. It can improve runtime by reducing object allocation and pointer dereference costs. We report continuing work studying ob-ject inlining optimizations. In particular, we present a new semantic derivation of the correctness conditions for object inlining, and program analysis which extends our previous work. And we present an object inlining transformation, fo-cusing on a new algorithm which optimizes class eld layout to minimize code expansion. Finally, we detail a fuller eval-uation on eleven programs and libraries (including Xpdf, the 25,000 line Portable Document Format (PDF) le browser) that utilizes hardware measures of impact on the memory system. We show that our analysis scales eectively to large pro-grams, nding many inlinable elds (45 in xpdf) at accept-able cost, and we show that, on some programs, it nds nearly all elds for which object inlining is correct, and av-erages 40 % of such elds across our benchmarks. We imple-ment our analyses in an advanced analysis infrastructure, and we show that, compared to traditional 1-CFA, that infrastructure provides better results and lower and more scalable cost. Across all programs, analysis identied about 30 % of objects as inlinable on average. Our transformation increases code size by only 20 % while inlining this 30 % of elds. Inlining these objects eliminated on average 28 % of eld reads, 58 % of object creations, 12 % of all loads. Fur-ther, the optimized programs have signicantly improved memory reference behavior, producing 25 % fewer L1 data cache misses and 25 % fewer read stalls. On average the runtime improved by 14%.