[concurrency-interest] Transformation of multiple volatile readswithout intervening writes

timo.kinnunen at gmail.com timo.kinnunen at gmail.com
Fri Sep 4 23:45:15 EDT 2015


To provide some additional background information, I had found a test class named CoherenceVolatile.java here http://www.cs.umd.edu/~pugh/java/memoryModel/index.html and tested out some optimizations that I might do, if I was a compiler. Please have look. 

These are the transformations that I tested (briefly, pp==qq and pp.x is volatile):

			if(OPTIMIZED_VERSION_3) {
				j = qq.x;
				i = k = m = pp.x;
			} else if(OPTIMIZED_VERSION_2) {
				i = pp.x;
				j = qq.x;
				k = pp.x;
				i = k = m = pp.x;
			} else if(OPTIMIZED_VERSION_1) {
				do {
					i = pp.x;
					j = qq.x;
					k = pp.x;
					m = pp.x;
				} while(i != m || k != m);
			} else /* ORIGINAL_VERSION */ {
				i = pp.x;
				j = qq.x;
				k = pp.x;
				m = pp.x;
			}

On my machine all of these transformations produced executions that JMM permitted to the original version. As far as the test class could detect anyway. 

The comment in the file says “all volatile reads and writes should have sequentially consistent semantics as viewed by any two threads”. Also that “once a thread sees a volatile write to a variable by another thread, it cannot forget that it has seen the write.” As a corollary, after a thread has seen a write to a volatile variable it should forget old stale values it may have seen from earlier writes to that variable. After all, in Java volatile is supposed to be a tool for synchronization, rather than sampling.




Sent from Mail for Windows 10



From: Hans Boehm
Sent: Friday, September 4, 2015 23:54
To: timo.kinnunen at gmail.com
Cc: concurrency-interest at cs.oswego.edu
Subject: Re: [concurrency-interest] Transformation of multiple volatile readswithout intervening writes


Are you asking about transforming thread1() in isolation?  Or as part of a whole program transformation?

I think the answer to the former is no.  Assume p starts out not null, p.a starts out null, p changes to null, and then p.a changes to not null.  If the original code doesn't return prematurely, it must throw an npe, because p must be null the third time it's read.  The transformed code will return successfully in this case.

The first redundant read of p can safely be eliminated.  The second cannot.

I'm not sure the answer to the second question is interesting.

On Thu, Sep 3, 2015 at 9:27 PM, <timo.kinnunen at gmail.com> wrote:
Hi, 
 
Hopefully an easy question about permitted transformations. 
 
Initially, q.a == q, q.x == 0, p == q and npe == null. Variables p and q.a are volatile. Thread 1 is reading and threads 2 and 3 could interfere with this with their writes.
 
The code for thread 1 is:
                public static void thread1() {
                                REG r1 = p;
                                if(r1 == null) return;
                                REG r2 = p;
                                if(r2 == null) throw npe;
                                REG r3 = r2.a;
                                if(r3 == null) return;
                                REG r4 = p;
                                if(r4 == null) throw npe;
                                REG r5 = r4.a;
                                if(r5 == null) throw npe;
                                r5.x = 1;
                }
The code for threads 2 and 3 is:
                public static void thread2() {
                                REG r6 = q;
                                r6.a = null;
                                r6.a = r6;
                }
                public static void thread3() {
                                REG r7 = q;
                                p = null;
                                p = r7;
                }
 
Is a compiler permitted to transform thread 1’s code to this:
                public static void thread1b() {
                                REG r4 = p;
                                if(r4 == null) return;
                                REG r5 = r4.a;
                                if(r5 == null) return;
                                r5.x = 1;
                }
 
Because the volatile reads r1,r2,r4 do not synchronize-with reads r3,r5 or each other r2,r4 could be grouped next to r1. Reads r1 and r2 then become unnecessary synchronization that the compiler can optimize away, along with some now dead code. The compiler repeats this same optimization with r5, which gives the final transformed code. 
 
Would this be a valid compiler transformation according to the JMM?
 
 
 
Sent from Mail for Windows 10

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest at cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20150905/957eed35/attachment-0001.html>


More information about the Concurrency-interest mailing list