Page MenuHomePhabricator

[LibCalls] Add `nosync` to known library calls
Changes PlannedPublic

Authored by jdoerfert on Mar 14 2021, 10:39 AM.

Details

Summary

A lot of library calls cannot be used to synchronize with other threads
of execution. This is useful to know, e.g., for heap-2-stack on GPUs.

Diff Detail

Unit TestsFailed

TimeTest
140 msx64 debian > LLVM.Transforms/InferFunctionAttrs::annotate.ll
Script: -- : 'RUN: at line 1'; /mnt/disks/ssd0/agent/llvm-project/build/bin/opt < /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/InferFunctionAttrs/annotate.ll -mtriple=x86_64-- -inferattrs -S | /mnt/disks/ssd0/agent/llvm-project/build/bin/FileCheck -check-prefix=CHECK-UNKNOWN /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/InferFunctionAttrs/annotate.ll
30 msx64 debian > LLVM.Transforms/LICM::strlen.ll
Script: -- : 'RUN: at line 1'; /mnt/disks/ssd0/agent/llvm-project/build/bin/opt -S -inferattrs -basic-aa -licm < /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/LICM/strlen.ll | /mnt/disks/ssd0/agent/llvm-project/build/bin/FileCheck /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/LICM/strlen.ll
80 msx64 debian > LLVM.Transforms/LoopIdiom::basic.ll
Script: -- : 'RUN: at line 2'; /mnt/disks/ssd0/agent/llvm-project/build/bin/opt -basic-aa -loop-idiom < /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/LoopIdiom/basic.ll -S | /mnt/disks/ssd0/agent/llvm-project/build/bin/FileCheck /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/LoopIdiom/basic.ll
260 msx64 windows > LLVM.Transforms/InferFunctionAttrs::annotate.ll
Script: -- : 'RUN: at line 1'; c:\ws\w16e2-1\llvm-project\premerge-checks\build\bin\opt.exe < C:\ws\w16e2-1\llvm-project\premerge-checks\llvm\test\Transforms\InferFunctionAttrs\annotate.ll -mtriple=x86_64-- -inferattrs -S | c:\ws\w16e2-1\llvm-project\premerge-checks\build\bin\filecheck.exe -check-prefix=CHECK-UNKNOWN C:\ws\w16e2-1\llvm-project\premerge-checks\llvm\test\Transforms\InferFunctionAttrs\annotate.ll
60 msx64 windows > LLVM.Transforms/LICM::strlen.ll
Script: -- : 'RUN: at line 1'; c:\ws\w16e2-1\llvm-project\premerge-checks\build\bin\opt.exe -S -inferattrs -basic-aa -licm < C:\ws\w16e2-1\llvm-project\premerge-checks\llvm\test\Transforms\LICM\strlen.ll | c:\ws\w16e2-1\llvm-project\premerge-checks\build\bin\filecheck.exe C:\ws\w16e2-1\llvm-project\premerge-checks\llvm\test\Transforms\LICM\strlen.ll
View Full Test Results (6 Failed)

Event Timeline

jdoerfert created this revision.Mar 14 2021, 10:39 AM
jdoerfert requested review of this revision.Mar 14 2021, 10:39 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 14 2021, 10:39 AM

To be safe, what do you think about marking nosync to ops that can be represented as a series of loads/stores or scalar ops only? For example, I believe memset is nosync because it is equivalent to a series of nonatomic stores.
For side-effecting operations, such as printf, I'm not 100% sure whether it is nosync. printf interacts with cout to properly flush buffers, which might do some interactions.

llvm/lib/Transforms/Utils/BuildLibCalls.cpp
528

C17's 7.22.3 Memory management functions has this paragraph:

  1. For purposes of determining the existence of a data race, memory allocation functions behave as though they accessed only memory locations accessible through their arguments and not other static duration storage. These functions may, however, visibly modify the storage that they allocate or deallocate. Calls to these functions that allocate or deallocate a particular region of memory shall occur in a single total order, and each such deallocation call shall synchronize with the next allocation (if any) in this order.

Should we conservatively assume that allocation/deallocation fns may synchronize with other threads?

978

This implies that if comparator fn executs any atomic operation then qsort raises UB, IIUC.
I think it depends, it may want to safely call some complex function which may involve atomic operations (e.g. increase/decrease reference counter).
I think it is safe to conservatively assume that qsort may sync with other threads.

1100

These functions may raise FE exceptions; would it be safe to assume that calling two ldexp, both of which setting FE exceptions, is UB?

For side-effecting operations, such as printf, I'm not 100% sure whether it is nosync. printf interacts with cout to properly flush buffers, which might do some interactions.

I tried to avoid all file operations, we can also avoid printf and friends.

llvm/lib/Transforms/Utils/BuildLibCalls.cpp
528

My original purpose was to add nosync to malloc and free :(

I guess what this says is that if you have two threads.
T1: allocate memory, get address P, deallocate it.
T2: allocate memory, get address P

You now know T1 deallocated P.

Worst case we could derive this for call sites if the pointer P was never observed (=captured).

978

right.

1100

I don't understand the question.

aqjune added inline comments.Mar 15 2021, 5:45 AM
llvm/lib/Transforms/Utils/BuildLibCalls.cpp
528

Worst case we could derive this for call sites if the pointer P was never observed (=captured).

I think it is safer and okay maybe, but since a few malloc implementation such as glibc's one typically has a lock to correctly manipulate allocated areas inside, showing the validity of attaching nosync seems non-trivial to me.

I have a question about the background btw - Does GPU's malloc need to use atomic operations? If GPU's malloc is simpler and they are not guaranteed to synchronize, attaching nosync can be justified.

1100

My question was whether math library fns can use atomic operations to update errno.

I just found that errno is defined as a thread-local storage; I believe it's okay now.

jdoerfert planned changes to this revision.Mar 15 2021, 8:39 AM

I'll send an email to cfe-dev at some point soon to ask about the malloc/free semantics, wrt. nosync but also other things.
Thanks for the input, I might update this to only include the safe things before the email is send.

llvm/lib/Transforms/Utils/BuildLibCalls.cpp
528

The question is not necessarily if the impl. uses an atomic or is synchronized but if it "leaks" out. So can the user establish a proper happens-before relation between two threads with malloc/free. If it doesn't, nosync is fine regardless of the impl. because of the "as-if" rule.

aqjune added inline comments.Mar 15 2021, 10:16 AM
llvm/lib/Transforms/Utils/BuildLibCalls.cpp
528

If no issue is found, I believe defining malloc that is never escaped as returning an isolated allocation that can never be used to communicate with the outer world (unknown functions or threads) will be great too.