Lei Zhao
2012-Jul-13 18:48 UTC
[LLVMdev] LLVM IR atomics: difference between unordered and monotonic?
Hi All, I am reading about LLVM IR atomics (http://llvm.org/docs/Atomics.html) and get confused about the difference between "Unordered" and "Monotonic". In particular, I am not sure I understand the statement of "It essentially guarantees that if you take all the operations affecting a specific address, a consistent ordering exists.". For me, it means that for the following example, if {r1,r2} = {1,2}, {r3,r4} = {2,1} is not allowed under "Monotonic" but allowed under "Unordered". Is this all how "Monotonic" is stronger than "Unordered"? If not, can anyone provide an example where other behaviors are allowed under "Unordered" but not "Monotonic"? ---------------------------------------------------------------------------------------- T1 T2 T3 T4 W(X)=1 W(X)=2 r1=R(X) r3=R(X) r2=R(X) r4=R(X) * Legend: four threads run in parallel; W(X)/R(X) meaning atomic write/read of X. ---------------------------------------------------------------------------------------- Thank you. - Lei -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120713/f0935a3c/attachment.html>
Jeffrey Yasskin
2012-Jul-13 19:12 UTC
[LLVMdev] LLVM IR atomics: difference between unordered and monotonic?
If you understand the difference between the Java and C++ memory model, "Unordered" is how to represent ordinary Java variables, while "Monotonic" is how to represent memory_order_relaxed operations on C++11 atomics. If you don't understand the Java and C++ memory models, read http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2480.html and http://unladen-swallow.googlecode.com/files/journal.pdf (why is there no better location for this file?). On Fri, Jul 13, 2012 at 11:48 AM, Lei Zhao <leizhao833 at gmail.com> wrote:> Hi All, > > I am reading about LLVM IR atomics (http://llvm.org/docs/Atomics.html) and > get confused about the difference between "Unordered" and "Monotonic". In > particular, I am not sure I understand the statement of "It essentially > guarantees that if you take all the operations affecting a specific address, > a consistent ordering exists.". For me, it means that for the following > example, if {r1,r2} = {1,2}, {r3,r4} = {2,1} is not allowed under > "Monotonic" but allowed under "Unordered". Is this all how "Monotonic" is > stronger than "Unordered"? If not, can anyone provide an example where other > behaviors are allowed under "Unordered" but not "Monotonic"? > > > ---------------------------------------------------------------------------------------- > T1 T2 T3 T4 > W(X)=1 W(X)=2 r1=R(X) r3=R(X) > r2=R(X) r4=R(X) > > * Legend: four threads run in parallel; W(X)/R(X) meaning atomic write/read > of X. > ---------------------------------------------------------------------------------------- > > Thank you. > > - Lei > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
Jeffrey Yasskin
2012-Jul-13 19:22 UTC
[LLVMdev] LLVM IR atomics: difference between unordered and monotonic?
On Fri, Jul 13, 2012 at 11:48 AM, Lei Zhao <leizhao833 at gmail.com> wrote:> Hi All, > > I am reading about LLVM IR atomics (http://llvm.org/docs/Atomics.html) and > get confused about the difference between "Unordered" and "Monotonic". In > particular, I am not sure I understand the statement of "It essentially > guarantees that if you take all the operations affecting a specific address, > a consistent ordering exists.". For me, it means that for the following > example, if {r1,r2} = {1,2}, {r3,r4} = {2,1} is not allowed under > "Monotonic" but allowed under "Unordered". Is this all how "Monotonic" is > stronger than "Unordered"? If not, can anyone provide an example where other > behaviors are allowed under "Unordered" but not "Monotonic"? > > > ---------------------------------------------------------------------------------------- > T1 T2 T3 T4 > W(X)=1 W(X)=2 r1=R(X) r3=R(X) > r2=R(X) r4=R(X) > > * Legend: four threads run in parallel; W(X)/R(X) meaning atomic write/read > of X. > ----------------------------------------------------------------------------------------Another litmus test is that with "unordered" variables, it's permissible to run: T1 T2 W(X)=1 r1=R(X) r2=R(X) r3=R(X) With X initially 0, and see r1==r3==0, but r2==1. Consider optimizing code where &X == x == y, and the code was actually "r1=*x; r2=*y; r3=*x;". Monotonic rules this out. Jeffrey