<div dir="ltr">FTR: <a href="http://llvm-reviews.chandlerc.com/D2227">http://llvm-reviews.chandlerc.com/D2227</a> sent for review to fix the tsan-hostile load speculation. <div><br></div><div>--kcc </div></div><div class="gmail_extra">
<br><br><div class="gmail_quote">On Wed, Nov 20, 2013 at 9:01 AM, Kostya Serebryany <span dir="ltr"><<a href="mailto:kcc@google.com" target="_blank">kcc@google.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote"><div class="im">On Tue, Nov 19, 2013 at 10:20 PM, David Chisnall <span dir="ltr"><<a href="mailto:David.Chisnall@cl.cam.ac.uk" target="_blank">David.Chisnall@cl.cam.ac.uk</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div>On 19 Nov 2013, at 17:58, Kostya Serebryany <<a href="mailto:kcc@google.com" target="_blank">kcc@google.com</a>> wrote:<br>
<br>
> On Tue, Nov 19, 2013 at 9:56 PM, Kuperstein, Michael M <<a href="mailto:michael.m.kuperstein@intel.com" target="_blank">michael.m.kuperstein@intel.com</a>> wrote:<br>
>> What I’m trying to say is that according to my understanding of the C++11 memory model, even in that small reproducer, the store to g and the load from g are in fact a data race.<br>
>><br>
>> (This is regardless of the fact the load is protected by a branch that is not taken.)<br>
><br>
> My understanding of the standard is quite the opposite.<br>
<br>
</div>I agree. It is a potential data race, if the branch is taken then it definitely is a race because the standard explicitly does not define an ordering on loads and stores of non-atomic variables unless some happens-before relationship is established by some other operation (which does not occur in this example). In the case where the branch is not taken, then there is no data race because in the C++ abstract machine there is no load, whether there is one in the underlying concrete machine or not.<br>
<br>
I believe that this transform is valid, because there are only two possible cases here:<br>
<br>
- Some other code has established a happens-before relationship between the load and the stores, giving a well-defined ordering, however this code is not visible in the function foo() and so the load may happen anywhere.<br>
<br>
- No other code establishes a happens-before relationship, and therefore the order of the load and the store is completely undefined and as long as the load doesn't trap it is completely safe to hoist it.<br>
<br>
HOWEVER, I would dispute describing this transform as an optimisation in this case.</blockquote><div><br></div></div><div>You have a good point: evaluating such transformation on single-threaded benchmarks (e.g. SPEC) makes no sense </div>
<div>if we care about multi-threaded code. And evaluating performance of anything like this on a multi-threaded code is hard too. </div><div>And it's very easy to prepare a synthetic test case where this optimization will cause 4x slowdown (see below). </div>
<div>But if we disable this transformation someone surely will come and complain :) </div><div>Another data point: gcc 4.6.3 does this too. </div><div><br></div><div><br></div><div><div>==> if-bench.cc <==</div><div>
#include <pthread.h></div><div>#include <unistd.h></div><div><br></div><div>extern int foo(int);</div><div>extern void bar(int);</div><div><br></div><div>#ifndef N</div><div>#define N (1UL << 30)</div><div>
#endif</div><div><br></div><div>void *Thread(void *p) {</div><div> for (long i = 0; i < N; i++)</div><div> foo(0);</div><div> return 0;</div><div>}</div><div><br></div><div>int main() {</div><div> pthread_t t[3];</div>
<div> pthread_create(&t[0], 0, Thread, 0);</div><div> pthread_create(&t[1], 0, Thread, 0);</div><div> pthread_create(&t[2], 0, Thread, 0);</div><div> for (long i = 0; i < N; i++)</div><div> bar(i);</div>
<div> pthread_join(t[0], 0);</div><div> pthread_join(t[1], 0);</div><div> pthread_join(t[2], 0);</div><div>}</div><div><br></div><div>==> g.cc <==</div><div class="im"><div>int g;</div><div><br></div><div>int foo(int cond) {</div>
<div> if (cond)</div><div> return g;</div></div><div> // If we replace 'g' with g*g*g*g, the benchmark becomes 4x faster.</div><div> return 0;</div><div>}</div><div><br></div><div>void bar(int i) { g = i; }</div>
</div><div><br></div><div><br></div><div><div>% clang if-bench.cc g.cc -lpthread -O1 && time ./a.out </div></div><div><br></div><div><br></div><div>--kcc </div><div class="im"><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
If the two threads are running on different cores, then we have likely introduced some false sharing and have forced the two cores to exchange some bus traffic for cache coherency, even though is is completely valid in the C++ abstract machine model for the load of g to return a stale cache value. This is only a real problem on strongly ordered architectures (e.g. x86), but given the relative cost of a cache shootdown and everything else in this test case (with the exception of the thread creation), I wouldn't be surprised if it ended up slowing things down. Especially given that a modern superscalar CPU will speculatively execute the load ANYWAY if it can do so from cache, and if it can't then the performance improvement from doing it before the branch will likely be negligible.<br>
<br>
For single-core, in-order, single-issue architectures, or multicore, weakly ordered, in-order, single-issue architectures, it's probably a win...<br>
<span><font color="#888888"><br>
David<br>
<br>
</font></span></blockquote></div></div><br></div></div>
</blockquote></div><br></div>