[4 Oct]

Since our last meeting I did the following things:

Found out how I could find an estimation of the impact of interprocedural analysis in removing the instrumentations (for last use analysis). Implemented part of this idea. Upper limit is the number of objects that "must-escape" to the caller or "must-sink" to callee.

Thought about the interprocedural analysis. Have a semi-formal specification.

Realized that the Must Alias Graph ( where must alias sets are represented as nodes and edges labeled with fields connect these nodes) is necessary to propagate dataflow information (liveness in this case) across method boundaries (caller to callee and callee to caller). So all my effort in must alias analysis is not wasted.

As I was saying during Maikel's talk, must alias analysis can be pretty useful in cutting down the size of slice that span across method boundary (callee to caller).

But bulk of the amount I spent fixing some serious bugs in the must analysis. I also did a CPU and memory profiling and have made a lot of changes to improve the performance. The performace improving changes are mostly inspired from the fact that there are very few alias sets – most of them are singletons and there are very less number of field edges connectibg them.

I am beginning to like this particular topic very much – programming with assertions/specifications. I have been thinking about this since summer. But in course of implementing this must alias analysis, I am seeing that assertions are very effective in catching bugs. I think, till software verification becomes practical (I doubt it would ever be!), specification-based programming will the only practical and effective solution. Automated test generation is also too difficult to be useful for large general purpose program (more than Red-Black trees :).

But I feel that it would be much more effective if assertions are written more systematically, which then become specification. The idea is not new. But I see there are very few systems: Java Modeling Language (Gary Leaven at iastate.edu) is the only tool that looks promising. But I dont see any program analysis being done to optimize the instrumentations that is needed to check the specification during runtime. Martin Rinard has recently published a tech report on "purity analysis" that checks some of the "pure method" assertions in JML statically.

For JML, they have a compiler that translates the specifications into Java code and naively inserts that into the application. But I think there is a big scope for program analysis in optimizing these instrumentations. It will have also straight forward extension to on-the field instrumentation – how do we divide the instrumentation overhead among various copies of the software?

Last modified 5 October 2004 at 1:02 am by Saswat Anand