[llvm-bugs] [Bug 41781] New: Parallelism breaks alias analysis assumptions

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=41781

            Bug ID: 41781
           Summary: Parallelism breaks alias analysis assumptions
           Product: new-bugs
           Version: 6.0
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: jdoerfert at anl.gov
                CC: htmldeveloper at gmail.com, llvm-bugs at lists.llvm.org

Created attachment 21902
  --> https://bugs.llvm.org/attachment.cgi?id=21902&action=edit
7 test cases to check various alterations of the same concurrent access
scenario

Parallelism, regardless of the source, breaks with assumptions various parts of
the alias analyses have wrt. the invariance of memory.

In a nutshell, the problem is that parallel executing threads can synchronize,
e.g., through barriers, atomics, etc., which causes memory state to
"conceptually change", even if the memory is inaccessible to the synchronizing
event.

As an example, take the code below (also test 6 in the attached file). It shows
how a static global variable G1, which doesn't have its address taken*, can
change its value at a synchronization point without it being a race. This is
problematic because from a "sequential execution standpoint" the value of the
global cannot change. Though, because multiple threads execute the same code
concurrently, it can.

*So all uses of G6 are shown below.

---------------------------------------------------------

static int G6 = -1;

void test_6(void) {
#pragma omp parallel num_threads(2)
  {
    int tid = omp_get_thread_num();

                  // G6 = -1

    if (tid == 0)
      G6 = 0;

    barrier();    // G6 = 0

    if (tid == 1)
      G6 = 1;

    barrier();    // G6 = 1

    if (tid == 0)
      print(G6);  // expected: 1, got 0
  }
}


---------------------------------------------------------


I attached 7 individual tests out of which clang fails the last three. (gcc
only fails the last, which is the one shown above.) However, the others only
"pass" because of the inability of the GlobalsModRef analysis to distinguish
accesses with a constant offset into a constant size internal array, something
we could reasonably add at any point in time.

The tests use OpenMP but there should not be a difference even if the source of
parallelism is pthreads, CUDA, OpenCL, ...

The only solution we came up with so far is to make the alias analysis aware
that "potentially synchronizing" instructions affect everything except
identified local objects that haven't escaped yet. 

(Given that there are also other reasons to derive "no-synchronize" as an
attribute, we will now look into that now and start a discussion on potential
fixes for this problem.)

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20190507/6abc5ac6/attachment-0001.html>