Write barrier removal by static analysis
We present a set of static analyses for removing write barriers in programs that use generational garbage collection. To our knowledge, these axe the first analyses for this purpose. Our Intraprocedural analysis uses a flow-sensitive pointer analysis to locate variables that must point to the most recently allocated object, then eliminates write barriers on stores to objects accessed via one of these variables. The Callee Type Extension incorporates information about the types of objects allocated in invoked methods, while the Caller Context Extension incorporates information about the most recently allocated object at call sites that invoke the currently analyzed method. Results from our implemented system show that our Full Interprocedural analysis, which incorporates both extensions, can eliminate the majority of the write barriers in most of the programs in our benchmark set, producing modest performance improvements of up to 7% of the overall execution time. Moreover, by dynamically instrumenting the executable, we are able to show that for all but two of our nine benchmark programs, our analysis is close to optimal in the sense that it eliminates the write barriers for almost all store instructions observed not to create a reference from an older object to a younger object.
write barriers generational garbage collection pointer analysis program analysis