<div dir="ltr">Ah right, I had missed the cbz, my bad. It is indeed sound under that condition.<div>My point was that just hoisting/sinking unconditionally the memory accesses is unsound. It is good news that gcc learnt how to do it carefully :)</div>
</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, Sep 2, 2014 at 4:36 PM, Filip Pizlo <span dir="ltr"><<a href="mailto:fpizlo@apple.com" target="_blank">fpizlo@apple.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="auto"><div>I think gcc is right. </div><div><br></div><div>It inserted a branch for n == 0 (the cbz at the top), so that's not a problem. </div><div><br></div><div>In all other regards, this is safe: if you examine the sequence of loads and stores, it eliminated all but the first load and all but the last store. How's that unsafe?</div>
<div><br></div><div>If I had to guess, the bug here is that LLVM doesn't want to hoist the load over the condition (which it is right to want to avoid) but it fails to realize that the condition is true for the first iteration. <span class="HOEnZb"><font color="#888888"><br>
<br>-Filip</font></span></div><div><div class="h5"><div><br>On Sep 2, 2014, at 4:23 PM, Robin Morisset <<a href="mailto:morisset@google.com" target="_blank">morisset@google.com</a>> wrote:<br><br></div><blockquote type="cite">
<div><div dir="ltr">The problem here is that doing this can introduce a race which is undefined at the IR level.<div>In the example you gave above I suspect that this is a bug in GCC. I may have missed something in the assembly, but it appears that gcc loads a copy of globalvar in w3, does stuff with w3 and then stores w3 in globalvar. This is unsound in the case where the loop is run with n = 0.</div>

<div>For an example, if you have a thread run foo(0,0) in a loop (so not doing anything) and another thread doing:</div><div>for (int i = 0 ; i <1000000 ; ++i) {</div><div>    globalvar = i;</div><div>    assert(globalvar == i);</div>

<div>}</div><div>the code should never assert. But if you host the load/store out of the loop (as GCC appears to do), then occasionaly there will be something like</div><div>thread 2: globalvar = i (= 42)</div><div>thread 1: w3 = globalvar (= 42)</div>

<div>thread 2: ++i</div><div>thread 2: globalvar = i (= 43)</div><div>thread 1: globalvar =w3 (= 42)</div><div>thread 2: assert(globalvar == i) </div><div>And it will assert (42 == 43) and crash.</div><div><br></div><div>

Shorter answer:</div><div>- speculatively executing stores is unsound because the value may have been modified behind your back by another thread.</div><div>- speculatively executing loads might not be observable in some specific case but may always introduce races, thus introducing undefined behaviour and breaking assumptions that other passes may rely on.</div>

<div><br></div><div>Best regards,</div><div>Robin</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, Sep 2, 2014 at 3:46 PM, Balaram Makam <span dir="ltr"><<a href="mailto:bmakam@codeaurora.org" target="_blank">bmakam@codeaurora.org</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">All,<br>
<br>
If we can speculatively execute a load instruction, why isn’t it safe to hoist it out by promoting it to a scalar in LICM pass?<br>
<br>
<br>
There is a comment in LICM pass that if a load/store is conditional then it is not safe because it would break the LLVM concurrency model (See commit 73bfa4a).<br>
It has an IR test for checking this in test/Transforms/LICM/scalar-promote-memmodel.ll<br>
<br>
However, I have a sample code where GCC is able to promote the memory to scalar and hoist/sink load/store out of loop but LLVM cannot.<br>
Is GCC being aggressive here or LLVM missing out an opportunity?<br>
<br>
Here is my sample code:<br>
<br>
extern int globalvar;<br>
void foo(int n , int incr) {<br>
  unsigned int i;<br>
  for (i = 0 ; i < n; i += incr ) {<br>
    if (i < n/2)<br>
      globalvar += incr;<br>
  }<br>
return;<br>
}<br>
<br>
GCC output:<br>
<br>
$ aarch64-linux-gnu-g++ -S -o -  -O3  -ffast-math -march=armv8-a+simd test.cpp<br>
        .arch armv8-a+fp+simd<br>
        .file   "test.cpp"<br>
        .text<br>
        .align  2<br>
        .global _Z3fooii<br>
        .type   _Z3fooii, %function<br>
_Z3fooii:<br>
.LFB0:<br>
        .cfi_startproc<br>
        cbz     w0, .L1<br>
        adrp    x6, globalvar<br>
        add     w5, w0, w0, lsr 31<br>
        ldr     w3, [x6,#:lo12:globalvar]                        <== hoist load of globalvar<br>
        mov     w2, 0<br>
        asr     w5, w5, 1<br>
.L4:<br>
        cmp     w5, w2<br>
        add     w2, w2, w1<br>
        add     w4, w3, w1<br>
        csel    w3, w4, w3, hi<br>
        cmp     w2, w0<br>
        bcc     .L4<br>
        str     w3, [x6,#:lo12:globalvar]                       <== sink store of globalvar<br>
.L1:<br>
        ret<br>
        .cfi_endproc<br>
.LFE0:<br>
        .size   _Z3fooii, .-_Z3fooii<br>
        .ident  "GCC: (crosstool-NG linaro-1.13.1-4.8-2014.01 - Linaro GCC 2013.11) 4.9.0"<br>
<br>
LLVM output:<br>
<br>
$ clang-aarch64-x++ -S -o - -O3 -ffast-math -fslp-vectorize test.cpp<br>
        .text<br>
        .file   "test.cpp"<br>
        .globl  _Z3fooii<br>
        .align  2<br>
        .type   _Z3fooii,@function<br>
_Z3fooii:                               // @_Z3fooii<br>
// BB#0:                                // %entry<br>
        cbz     w0, .LBB0_5<br>
// BB#1:                                // %<a href="http://for.body.lr.ph" target="_blank">for.body.lr.ph</a><br>
        mov      w8, wzr<br>
        cmp      w0, #0                 // =0<br>
        cinc     w9, w0, lt<br>
        asr     w9, w9, #1<br>
        adrp    x10, globalvar<br>
.LBB0_2:                                // %for.body<br>
                                        // =>This Inner Loop Header: Depth=1<br>
        cmp      w8, w9<br>
        b.hs    .LBB0_4<br>
// BB#3:                                // %if.then<br>
                                        //   in Loop: Header=BB0_2 Depth=1<br>
        ldr     w11, [x10, :lo12:globalvar]                     <===== load inside loop<br>
        add      w11, w11, w1<br>
        str     w11, [x10, :lo12:globalvar]                      <==== store inside loop<br>
.LBB0_4:                                // %for.inc<br>
                                        //   in Loop: Header=BB0_2 Depth=1<br>
        add      w8, w8, w1<br>
        cmp      w8, w0<br>
        b.lo    .LBB0_2<br>
.LBB0_5:                                // %for.end<br>
        ret<br>
.Ltmp1:<br>
        .size   _Z3fooii, .Ltmp1-_Z3fooii<br>
<br>
<br>
        .ident  "clang version 3.6.0 "<br>
<br>
Thanks,<br>
Balaram<br>
<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote></div><br></div>
</div></blockquote><blockquote type="cite"><div><span>_______________________________________________</span><br><span>LLVM Developers mailing list</span><br><span><a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a></span><br>
<span><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a></span><br></div></blockquote></div></div></div></blockquote></div><br></div>