Critical Section, Be Gone!

To remove the costly synchronization from Java programs, many researchers employ an escape analysis that identifies objects that cannot be accessed by multiple threads and hence do not require synchronization. This approach, however, does not attempt to optimize objects that do escape a thread. These escaping objects may be optimized when, generally speaking, no thread writes to them after they escape their creator thread. We present a shape analysis that constructs an accurate static picture of the connectivity of shared objects. Its results feed a flow-sensitive data-flow analysis that determines which objects a thread has locked when it writes to a location visible to other threads. If an object\'s lock does not protect such a write, the object does not need to be locked. Ignoring the locking operations of this object will not only reduce the amount of locking but also increase program concurrency, potentially leading to a significant speed-up.