llvm dev - Jan 2015 - [LLVMdev] LLVM introduces racy read - Unsafe transformation?

Hi,

I am looking for thoughts on the following LLVM transformation.

Consider the following transformation which replaces conditional load(a)
with load(a);select instructions.

Source
--------
int a; bool flag;

int readA() {
 int r=0;
 if(flag) {
   r = a;
 }
return r;
}

Command
--------
clang++ -std=c++11 -pthread -emit-llvm <filename>.cpp -S;opt -O3
<filename>.ll -o <filename>.opt.bc -S

Target
-------

define i32 @_Z5readAv() #3 {
entry:
  %0 = load i8* @flag, align 1
  %1 = and i8 %0, 1
  %tobool = icmp eq i8 %1, 0
  %2 = load i32* @a, align 4
  %. = select i1 %tobool, i32 0, i32 %2
  ret i32 %.
}

Consider the following function writeA() runs in parallel with readA().

void writeA(){
  a = 42;
}

The source program has no data race if flag=false. But the target program
is racy due to the introduced load(a) operation.

This is a benign race since the load(a) is used only when flag=true.

However, according to the C11/C++11 consistency model the semantics of a
racy program is undefined and may have arbitrary behavior.

Thus the transformation is unsafe.

Note: The full example files are attached.

Regards,
soham
-------------- next part --------------
A non-text attachment was scrubbed...
Name: loadrace.zip
Type: application/x-zip-compressed
Size: 28366 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150126/31013770/attachment.bin>

On 26 Jan 2015, at 15:22, sohachak at mpi-sws.org wrote:
> 
> The source program has no data race if flag=false. But the target program
> is racy due to the introduced load(a) operation.
> 
> This is a benign race since the load(a) is used only when flag=true.
> 
> However, according to the C11/C++11 consistency model the semantics of a
> racy program is undefined and may have arbitrary behavior.
It's not clear to me that this is correct.  Neither variable is atomic and
so loads do not establish happens-before edges.  The load of a is not observable
and so is safe to hoist.  According to the C[++]11 model the transformed version
appears correct.  There is no guarantee of serialisation of the loads of flag
and a, because neither is atomic.

It's not actually clear to me that the original is race-free.  If flag ever
transitions from false to true without something else that establishes a
happens-before relationship between these two threads then this is racy.  If
flag is always false, then this is not racy and the LLVM output is not
*observably* racy (the IR does not permit this load to have observable side
effects, and its result is never used).  If flag is always true then this is
racy.  If flag transitions from true to false without a happens-before edge,
then this is also racy.

David

Hi,

I agree that the earlier example was already racy due to shared flag
variable. Sorry for the wrong example. Please ignore it.

I have modified the program as follows. The only shared variable is 'a'
and the following is a non-racy program.

int a;

int readA(bool flag) {
 int r=0;
  if(flag) {
    r = a;
 }
return r;
}

void writeA(){
  a = 42;
}

int main() {

 bool flag = false;
 thread first (writeA);
 thread second (readA, flag);

 first.join();
 second.join();

 return 0;
}

The generated LLVM IR

; Function Attrs: nounwind readonly uwtable
define i32 @_Z5readAb(i1 zeroext %flag) #3 {
entry:
  %0 = load i32* @a, align 4
  %. = select i1 %flag, i32 %0, i32 0
  ret i32 %.
}

; Function Attrs: nounwind uwtable
define void @_Z6writeAv() #4 {
entry:
  store i32 42, i32* @a, align 4
  ret void
}

:

In the generated IR load(a) is independent of flag value which is not the
case in the source program. Hence there is an introduced race between
load(a) and store(a) operations when readA() and writeA() runs
concurrently.

Regards,
soham

> On 26 Jan 2015, at 15:22, sohachak at mpi-sws.org wrote:
>>
>> The source program has no data race if flag=false. But the target
>> program
>> is racy due to the introduced load(a) operation.
>>
>> This is a benign race since the load(a) is used only when flag=true.
>>
>> However, according to the C11/C++11 consistency model the semantics of
a
>> racy program is undefined and may have arbitrary behavior.
>
> It's not clear to me that this is correct.  Neither variable is atomic
and
> so loads do not establish happens-before edges.  The load of a is not
> observable and so is safe to hoist.  According to the C[++]11 model the
> transformed version appears correct.  There is no guarantee of
> serialisation of the loads of flag and a, because neither is atomic.
>
> It's not actually clear to me that the original is race-free.  If flag
> ever transitions from false to true without something else that
> establishes a happens-before relationship between these two threads then
> this is racy.  If flag is always false, then this is not racy and the LLVM
> output is not *observably* racy (the IR does not permit this load to have
> observable side effects, and its result is never used).  If flag is always
> true then this is racy.  If flag transitions from true to false without a
> happens-before edge, then this is also racy.
>
> David
>
>