Static detection of loop-invariant data structures

Abstract. As a culture, object-orientation encourages programmers to create ob-jects, both short- and long-lived, without concern for cost. Excessive object cre-ation and initialization can cause severe runtime bloat, which degrades signif-icantly application performance and scalability. A frequently-occurring coding pattern that may lead to large volumes of (temporary) objects is the creation of objects that, while allocated per loop iteration, contain values independent of spe-cific iterations. Finding these objects and moving them out of loops requires so-phisticated interprocedural analysis, a task that is difficult for traditional dataflow analyses such as loop-invariant code motion to accomplish. Our work targets data structures that are loop-invariant, and presents a static type and effect system to detect loop-invariant data structures. For each loop, our anal-ysis inspects each logical data structure in order to find those that have disjoint instances per loop iteration and contain loop-invariant data. Instead of automat-ically hoisting them to improve performance (which is over-conservative), we report hoistability measurements for each disjoint loop data structure detected by our analysis. Eventually these data structures are ranked based on these measure-ments and are presented to the user to help manual tuning. We have performed a variety of studies on a set of 19 moderate/large-sized Java benchmarks. With the help of hoistability measurements, we found optimization opportunities in most of the programs that we inspected and achieved significant performance improve-ments in some of them (e.g., 82.1 % running time reduction).