Dan Bonachea's CS 265 Expert Topic Page

Array Access Loop Optimizations

Motivation:

At a recent Titanium project meeting, a need was expressed for adding optimizations in the Titanium compiler to streamline accesses to Java arrays within loops (currently, Titanium array accesses within foreach loops are highly optimized, but Java array accesses and all accesses within Java for loops apparently are not). I was encouraged by the group to pursue the addition of these optimizations as my 265 semester project to help alleviate bottlenecks which have been demonstrated in legacy Java benchmarks compiled under Titanium. This seems like a worthwhile and reasonable goal for my semester research project, and I've chosen my "expert topic" to provide support for this project.

Therefore, I’d like my topic to deal with the optimization of array accesses within loops. If this topic seems overly broad, then I can confine my study to one or more of the typical constituent optimizations such as invariant code motion, strength reduction or induction variable elimination.

Updated Status:

I've concluded my investigation of my expert topic. My lecture on 4/6 covered various topics in loop optimization (invariant and induction variable analysis, reassociation, strength reduction, linear test replacement) and bounds checking elimination.  The lecture focused on the material in ARZ Ch. 9 (for the loop optimizations) and the Gupta 93 paper (for the bounds checking elimination).

Here are the lecture notes (they were drawn from several sources):

Loop Optimization Resources (in rough order of importance):

Bounds Checking Elimination Papers (in rough order of importance):


Back to Dan's Home Page