<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Oct 10, 2017, at 4:01 PM, James Dennett <<a href="mailto:james.dennett@gmail.com" class="">james.dennett@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote">On Tue, Oct 10, 2017 at 12:23 PM, John McCall via cfe-dev <span dir="ltr" class=""><<a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">cfe-dev@lists.llvm.org</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><br class=""><div class=""><div class=""><div class="h5"><blockquote type="cite" class=""><div class="">On Oct 10, 2017, at 2:57 PM, John McCall via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">cfe-dev@lists.llvm.org</a>> wrote:</div><br class="m_7413606527186370467Apple-interchange-newline"><div class=""><div style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" class=""><blockquote type="cite" class=""><div class="">On Oct 10, 2017, at 12:12 PM, Hal Finkel via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">cfe-dev@lists.llvm.org</a>> wrote:</div><div class=""><div bgcolor="#FFFFFF" text="#000000" class=""><p class="">[+Richard, Chandler]<br class=""></p><br class=""><div class="m_7413606527186370467moz-cite-prefix">On 10/09/2017 07:00 PM, Hans Wennborg via cfe-dev wrote:<br class=""></div><blockquote type="cite" class=""><pre class="">I am not a language lawyer, but I'll atttempt to answer anyway.
On Mon, Oct 9, 2017 at 2:16 PM, Kreitzer, David L via cfe-dev
<a class="m_7413606527186370467moz-txt-link-rfc2396E" href="mailto:cfe-dev@lists.llvm.org" target="_blank"><cfe-dev@lists.llvm.org></a> wrote:
</pre><blockquote type="cite" class=""><pre class="">This llvm patch, <a class="m_7413606527186370467moz-txt-link-freetext" href="https://reviews.llvm.org/D37289" target="_blank">https://reviews.llvm.org/<wbr class="">D37289</a>, attempts to do an optimization
that involves speculating loads. The patch itself needs some work regardless,
but we are questioning the legality of the optimization, which is currently
performed by both gcc and icc. The desired transformation looks like this:
typedef struct S {
char padding[4088];
struct S *p1;
struct S *p2;
} S;
struct S* f1(struct S *s, int x)
{
S *r;
if (x)
r = s->p1;
else
r = s->p2;
return r;
}
TO
struct S* f1(struct S *s, int x)
{
return (x) ? s->p1 : s->p2;
}
The fundamental question seems to be whether loading one member of struct S
makes it valid to load other members of the same struct.
</pre></blockquote><pre class="">Yes, I believe that's true. If we're dereferencing s on both paths, it
must point to a struct S object, and then loading from any member of
that object should be fine.</pre></blockquote><br class="">I also believe that this is correct.<br class=""><br class="">I think that Chandler summarized some things to be careful about in this regard here:<br class=""> <span class="m_7413606527186370467Apple-converted-space"> </span><a class="m_7413606527186370467moz-txt-link-freetext" href="http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20170807/477944.html" target="_blank">http://lists.llvm.org/<wbr class="">pipermail/llvm-commits/Week-<wbr class="">of-Mon-20170807/477944.html</a><br class=""><br class="">Of the three points highlighted here, the second clearly might apply:<br class=""><blockquote type="cite" class=""><pre style="white-space:pre-wrap;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;word-spacing:0px" class="">2) Related to #1, there are applications that rely on this memory model,
for example structures where entire regions of the structure live in
protected pages and cannot be correctly accessed.</pre></blockquote><br class="">This, however, is clearly an extension to the standard memory model, and I see no reason to support this by default. Speculatively loading cache lines under contention from other cores might not be a good thing to do for performance reasons, but that's not a correctness issue.<br class=""></div></div></blockquote><div class=""><br class=""></div>I agree that this optimization is legal under the C and C++ specs.</div></div></blockquote><div class=""><br class=""></div></div></div>Sorry, I'd meant to add a proviso to this. It's legal under the C and C++</div><div class="">specs to the same extent that any load speculation is.</div><div class=""><br class=""></div><div class="">In general, load speculation is theoretically problematic in C/C++ because</div><div class="">it is undefined behavior to have a race even if the race is spurious. For example,</div><div class="">a program containing a load that races with a store has undefined behavior even</div><div class="">if the result of the load is never used. Therefore, strictly speaking, speculating a</div><div class="">load can introduce a race that didn't otherwise exist, meaning that it can introduce</div><div class="">undefined behavior to a program, </div></div></blockquote><div class=""><br class=""></div><div class="">This is where the argument falls down. If there's no race in the source code, the behavior *is* defined. It doesn't matter that the hardware might have a racy read in the implementation, so long as it doesn't affect the behavior of the abstract machine.</div></div></div></div></div></blockquote><div><br class=""></div>Okay, sorry, let me be more precise about abstract machines.<br class=""><div><br class=""></div>If an implementation used the rules of the C abstract machine for its intermediate representation, it would not be allowed to speculate loads because doing so would introduce undefined behavior on the abstract machine. It doesn't matter what the actual target machine would do.</div><div><br class=""></div><div>Now, Clang and other LLVM frontends do not use the C abstract machine for their intermediate representations: they use LLVM, and LLVM is its own abstract language with its own abstract machine and its own concept of undefined behavior. A frontend generating LLVM is doing a source-to-source transformation which is expected to maintain semantics, including the absence of undefined behavior. LLVM's abstract machine says that racing loads do not have undefined behavior, they merely yield undef. (I hadn't checked this specifically and didn't realize the LLVM rule was so much weaker than the C rule, for which I apologize.) So speculating a load in LLVM is fine, at least as far as races go.</div><div><br class=""></div><div>TSan appears to be assuming that the loads and stores it sees have C-machine semantics, which only works in close coordination with the frontend.</div><div><br class=""></div><div>John.</div><div><br class=""></div><div><blockquote type="cite" class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class="">meaning that it's not a legal transformation. </div></div></blockquote><div class=""><br class=""></div><div class="">There might be other reasons (maybe practical reasons) why this isn't permitted, but it's not because it introduces UB (it doesn't).</div></div></div></div></blockquote><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""> <br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""> Now,</div><div class="">AFAIK LLVM doesn't have any multi-threaded analyses that would actually</div><div class="">miscompile such a speculation, but it can still matter because e.g. TSan emits code</div><div class="">that dynamically enforces the memory model, and it will dutifully report the race here.</div><div class=""><br class=""></div><div class="">(Or, to quote from C11 5.1.2.4p28:</div><div class=""><br class=""></div><div class=""> Transformations that introduce a speculative read of a potentially shared memory</div><div class=""> location may not preserve the semantics of the program as defined in this standard,</div><div class=""> since they potentially introduce a data race.</div></div></blockquote><div class=""><br class=""></div><div class="">I think this is somewhat muddy, and essentially contradicted by the text immediately following it:</div><div class=""> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""> However, they are typically valid in the</div><div class=""> context of an optimizing compiler that targets a specific machine with well-defined</div><div class=""> semantics for data races. They would be invalid for a hypothetical machine that is</div><div class=""> not tolerant of races or provides hardware race detection.</div><div class=""><br class=""></div><div class="">In this sense, TSan makes an arbitrary machine race-intolerant.)</div></div></blockquote><div class=""><br class=""></div><div class="">Right, this transformation is invalid according to TSan (and a compiler targeting TSan should not apply it) . Apart from such debug implementations, I'm not aware of an extant platform on which it's problematic.</div></div></div></div></div></blockquote><div><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><br class=""></div><div class="">-- James</div><div class=""><br class=""></div></div></div></div>
</div></blockquote></div><br class=""></body></html>