Re: Synchronisation and Optimisation

[Patrick LAM <plam@sable.mcgill.ca>]

Stephen Cheng writes:

> Lets for the moment assume that a Java application correctly
> synchronises all variables acess across multiple thread. It is
> critical that the optimisation algorithms to produce an optimised
> version that provides correctly synchronised access to all shared
> variables, and exhibits the "same" behaviour. I would however argue
> that it is not necessary for the optimisation algorithms to produce a
> "correct" optimised version if the original program does not correctly
> synchronise all shared variable. Under the Java VM specification, such
> programs (even unoptimised) would never not have a deterministic
> behaviour, and they would behave differently under different VMs.

Concurrent programs can produce nondeterministic behaviour on
different executions under the same VM, even if they properly
synchronize access.

As Etienne said, the Java memory model is not great.  You should
definitely consult the links that he provided.

Also note that local variables are always unshared, although if they
refer to objects, then field reads will need to occur under locks.  Soot
doesn't do a lot of things that are going to be affected by concurrency.

There are two types of races you might want to worry about.  Consider the
following class:

class Point
{
    int x, y;
    Point (int x, int y) { this.x = x; this.y = y; }
}

and the following code:

    void foo()
    {
        Point p = new Point(0,0);
        synchronized(p) { p.x += 2; }
        synchronized(p) { p.y += 5; }
    }

This code 'properly synchronizes access to p' but exposes the state
p(2,0) which is probably (but not certainly) not what you want.

> When Soot translates from bytecode to Jimple, monitorenter and
> monitorexit bytecodes are respectively translated to Jimple
> EnterMonitorStmt and ExitMonitorStmt. Soot does not create additional
> Jimple assign statements to "flush" the variables. In other words the
> algorithms built on Jimple must specifically and independentally take
> account of the effects of ExitMonitorStmt and EnterMonitorStmt, since
> Jimple is no longer strict-SSA.

Jimple doesn't actually use SSA, although there are some SSA-like
properties in Jimple.  Furthermore, you don't need additional
statements to flush variables, since local variables are unaffected.
What *is* unsafe is moving field reads and writes past monitor
statements.  I don't think Soot does that.

Rhodes Brown writes:

> I am not that familiar with Soot's handling of synchronization
> relative to the standard optimizations. Perhaps someone else could
> comment.

Soot is mostly insensitive to synchronization.  Any analyses that
might be affected by synchronization issues should explicitly be
aware of it, and I don't think the standard Soot analyses are
affected.

pat