Bill,
Thanks for explaining your examples (there was another typo in Ex 4 that
had thrown me off, but now I understand).
About the problems you cite with my approach -
Summary: the last two points you make are good and valid ones, but I
think relatively easy to fix; i.e., I don't see any show stoppers (yet).
Details:
>
> I have two problems with this. First, this definition depends upon
> "all possible execution traces". But "all possible execution traces"
> depends upon the acyclic flow dependence constraint, so you have a
> circular definition.
No, there is no circularity. You may want to read my definition of
execution again (it is the second definition on the page you saw on
Monday). There is no mention of acyclic flow dependence constraint or
anything remotely connected to it. Maybe you can tell me what you are
looking at when you say the above, and it will indicate why the
misunderstanding.
>
> But even if you fixed that, it is still fundamentally flawed, because
> "all possible execution traces" is too broad.
>
> For example, we had:
>
> Ex 2:
> Initially, x = y = 0
>
> Thread 1:
> r1 = x
> r2 = r1*r1 - r1 + 1
> y = r2
>
> Thread 2:
> r3 = y
> r4 = r4*r4 - r4 + 1
> x = r4
>
>
> We modify example 2 slightly so that r2 and r4 aren't always 1:
>
> Ex 2a:
> Initially, x = y = z = 0, z is final
>
> Thread 1:
> z = Integer.getInteger("offset",1).intValue();
>
> Thread 2:
> join thread 1
> r5 = z
> r1 = x
> r2 = r1*r1 - r1 + r5
> y = r2
>
> Thread 3:
> join thread 1
> r6 = z
> r3 = y
> r4 = r4*r4 - r4 + r6
> x = r4
>
> Now, a JIT running after thread 1 has could decide that r5 and r6 are
> the constants 1 and get us back to the code and optimization from Ex
> 2.
>
> The problem is that "all possible execution traces" is too broad.
> First, the JIT may run after some computation has been performed, and
> so already know that the set of possible executions is limited.
> Secondly, the compiler may not that it won't generate all possible
> execution traces, and take that into account in deciding whether
> something is effectively constant.
Both are good and valid points, but I think (relatively) easily fixed as
follows. Let me do the second one first:
> Secondly, the compiler may not that it won't generate all possible
> execution traces, and take that into account in deciding whether
> something is effectively constant.
Can you give an example? If the compiler can reason that it won't
generate all possible execution traces, then it has to have some
explicit model of what it can generate that is independent of the model.
We should be able to incorporate that model in my definition of "all
possible executions." So can you elaborate on: how the compiler can
formalize what possible execution traces it will generate, independent
of the memory model, and then use that information to perform
optimizations?
Regardless, your point is well taken and I made a modification to narrow
down "all possible executions" for the flow dependence. See
http://www.cs.uiuc.edu/~sadve/jmm-new.pdf [At this point, I'll recommend
this document only for Bill. Once I write up an accompanying
description, it will be clearer for others.] This modification also
takes care of Ex. 2a above (assuming joins are considered
synchronization).
> First, the JIT may run after some computation has been performed, and
> so already know that the set of possible executions is limited.
Again, I don't see a fundamental problem. If the JIT is going to change
the code part-way through the execution depending on what has happened,
then it should use a different flow dependence relation in its analysis
depending on what executions are possible with the new assumptions. In
our static context, this issue can be handled by saying explicitly that
code specialization is allowed before analysis. Since Ex. 2a is already
taken care of by the previous part, consider a harder modification of 2a
to illustrate this:
Flag1 and Flag2 are volatile
Thread 1
z = 1
Flag = 1
Thread 2
z = 2
Flag = 2
Thread 3
while ((Flag1 != 1) && (Flag2 !=2)) {;}
r5 = z
r1 = x
r2 = r1*r1 - r1 + r5
y = r2
Thread 4:
r6 = z
r3 = y
r4 = r3*r3 - r3 + r6
x = r4
Applying specialization, it is legal to transform the code of threads 3
and 4 to:
Thread 3
while ((Flag1 != 1) && (Flag2 != 2)) {;}
r5 = z
If (r5 == 1) {
r1 = x
r2 = r1*r1 - r1 + r5
y = r2
}
Else {
r1 = x
r2 = r1*r1 - r1 + r5
y = r2
}
Thread 4
while ((Flag1 != 1) && (Flag2 !=2)) {;}
r6 = z
If (r6 == 1) {
r3 = x
r4 = r3*r3 - r3 + r6
y = r4
}
Else {
r3 = x
r4 = r3*r3 - r3 + r6
y = r4
}
Now coupled with my previous change, there is no flow dependence from
r2/r4 when r5/r6 return 1 for z.
You may say the above is messy, but that's effectively what the JIT is
doing when it recompiles assuming the knowledge that z=1.
Please let me know if I missed something. Meanwhile, I'll continue to
think about how this could be covered in a simpler way. But in any case,
it still seems to me that the fundamental approach of using flow
dependences is valid - further tweaks may be required to determine what
executions to consider, but so far, it still seems better than relying
on an informal statement for full coverage of this issue.
Also, it seems to me that there would be some JIT related issues with
your model as well?
Thanks,
Sarita
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:41 EDT