diff options
| author | Eli Friedman <eli.friedman@gmail.com> | 2011-07-20 21:35:53 +0000 |
|---|---|---|
| committer | Eli Friedman <eli.friedman@gmail.com> | 2011-07-20 21:35:53 +0000 |
| commit | 5b60e1b6fc5bdce06599512069037944f2194703 (patch) | |
| tree | 26d52591d33ed528e486d6b60990844c8c1e70b7 | |
| parent | c3d48cee49257ea1666986d98c5d268262ad1e9b (diff) | |
| download | external_llvm-5b60e1b6fc5bdce06599512069037944f2194703.zip external_llvm-5b60e1b6fc5bdce06599512069037944f2194703.tar.gz external_llvm-5b60e1b6fc5bdce06599512069037944f2194703.tar.bz2 | |
Commit LangRef changes for LLVM concurrency model. Start of supporting C++0x memory model and atomics. See thread on llvmdev titled "Reviving the new LLVM concurrency model".
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135624 91177308-0d34-0410-b5e6-96231b3b80d8
| -rw-r--r-- | docs/LangRef.html | 86 |
1 files changed, 86 insertions, 0 deletions
diff --git a/docs/LangRef.html b/docs/LangRef.html index 5959b3d..07720e5 100644 --- a/docs/LangRef.html +++ b/docs/LangRef.html @@ -53,6 +53,7 @@ <li><a href="#datalayout">Data Layout</a></li> <li><a href="#pointeraliasing">Pointer Aliasing Rules</a></li> <li><a href="#volatile">Volatile Memory Accesses</a></li> + <li><a href="#memmodel">Memory Model for Concurrent Operations</a></li> </ol> </li> <li><a href="#typesystem">Type System</a> @@ -1470,6 +1471,91 @@ synchronization behavior.</p> </div> +<!-- ======================================================================= --> +<h3> + <a name="memmodel">Memory Model for Concurrent Operations</a> +</h3> + +<div> + +<p>The LLVM IR does not define any way to start parallel threads of execution +or to register signal handlers. Nonetheless, there are platform-specific +ways to create them, and we define LLVM IR's behavior in their presence. This +model is inspired by the C++0x memory model.</p> + +<p>We define a <i>happens-before</i> partial order as the least partial order +that</p> +<ul> + <li>Is a superset of single-thread program order, and</li> + <li>When a <i>synchronizes-with</i> <tt>b</tt>, includes an edge from + <tt>a</tt> to <tt>b</tt>. <i>Synchronizes-with</i> pairs are introduced + by platform-specific techniques, like pthread locks, thread + creation, thread joining, etc., and by the atomic operations described + in the <a href="#int_atomics">Atomic intrinsics</a> section.</li> +</ul> + +<p>Note that program order does not introduce <i>happens-before</i> edges +between a thread and signals executing inside that thread.</p> + +<p>Every (defined) read operation (load instructions, memcpy, atomic +loads/read-modify-writes, etc.) <var>R</var> reads a series of bytes written by +(defined) write operations (store instructions, atomic +stores/read-modify-writes, memcpy, etc.). For each byte, <var>R</var> reads the +value written by some write that it <i>may see</i>, given any relevant +<i>happens-before</i> constraints. <var>R<sub>byte</sub></var> may +see any write to the same byte, except:</p> + +<ul> + <li>If <var>write<sub>1</sub></var> happens before + <var>write<sub>2</sub></var>, and <var>write<sub>2</sub></var> happens + before <var>R<sub>byte</sub></var>, then <var>R<sub>byte</sub></var> + must not see <var>write<sub>1</sub></var>. + <li>If <var>R<sub>byte</sub></var> happens before <var>write<sub>3</var>, + then <var>R<sub>byte</sub></var> must not see + <var>write<sub>3</sub></var>. +</ul> + +<p>Given that definition, <var>R<sub>byte</sub></var> is defined as follows: +<ul> + <li>If there is no write to the same byte that happens before + <var>R<sub>byte</sub></var>, <var>R<sub>byte</sub></var> returns + <tt>undef</tt> for that byte. + <li>If <var>R<sub>byte</sub></var> may see exactly one write, + <var>R<sub>byte</sub></var> returns the value written by that + write.</li> + <li>If <var>R<sub>byte</sub></var> and all the writes it may see are + atomic, it chooses one of those writes and returns it value. + Given any two bytes in a given read <var>R</var>, if the set of + writes <var>R<sub>byte</sub></var> may see is the same as the set + of writes another byte may see, they will both choose the same write. + <li>Otherwise <var>R<sub>byte</sub></var> returns <tt>undef</tt>.</li> +</ul> + +<p><var>R</var> returns the value composed of the series of bytes it read. +This implies that some bytes within the value may be <tt>undef</tt> +<b>without</b> the entire value being <tt>undef</tt>. Note that this only +defines the semantics of the operation; it doesn't mean that targets will +emit more than one instruction to read the series of bytes.</p> + +<p>Note that in cases where none of the atomic intrinsics are used, this model +places only one restriction on IR transformations on top of what is required +for single-threaded execution: introducing a store to a byte which might not +otherwise be stored to can introduce undefined behavior.</p> + +<!-- FIXME: This model assumes all targets where concurrency is relevant have +a byte-size store which doesn't affect adjacent bytes. As far as I can tell, +none of the backends currently in the tree fall into this category; however, +there might be targets which care. If there are, we want a paragraph +like the following: + +Targets may specify that stores narrower than a certain width are not +available; on such a target, for the purposes of this model, treat any +non-atomic write with an alignment or width less than the minimum width +as if it writes to the relevant surrounding bytes. +--> + +</div> + </div> <!-- *********************************************************************** --> |