Simple Alias Causes Unexpected Memory Dependency

Beginners
1

Hi,

I’m learning dependence analysis with LLVM. I created the following program:

int main(void) {
	int a[2];
	int *p = a; // alias
	int b, c;

	a[0] = 1337;
	a[1] = 777;
	b = p[0];
	c = p[1];

	return 0;
}

I convert this program to LLVM IR with clang -S -emit-llvm ./test.c and print the memory dependencies with: opt -print-memdeps -analyze ./test.ll.
This yields the following output:

Printing analysis 'Print MemDeps of function' for function 'main':
--- 8< ---
    Def from:   store i32* %6, i32** %3, align 8
  %9 = load i32*, i32** %3, align 8

    Clobber from:   store i32 777, i32* %8, align 4
  %11 = load i32, i32* %10, align 4

    Def from:   %4 = alloca i32, align 4
  store i32 %11, i32* %4, align 4

    Def from:   %9 = load i32*, i32** %3, align 8
  %12 = load i32*, i32** %3, align 8

    Clobber from:   store i32 777, i32* %8, align 4
  %14 = load i32, i32* %13, align 4

    Def from:   %5 = alloca i32, align 4
  store i32 %14, i32* %5, align 4

This would seem to indicate that both the C instructions b = p[0]; and c = p[1]; are dependent on the instruction a[1] = 777;.
However, I would imaging the instruction b = p[0]; should be dependent only on a[0] = 1337; instead.

Could someone help me understand what’s going wrong here?
Is there a better way to extract dependencies from a program?

Here follow the versions of clang and opt that I use:

$ clang --version
clang version 10.0.0-4ubuntu1 
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin

$ opt --version
LLVM (http://llvm.org/):
  LLVM version 10.0.0
  
  Optimized build.
  Default target: x86_64-pc-linux-gnu
  Host CPU: tigerlake
2

Run -sroa first before -print-memdeps. Clang without -O{1,2,3} will default to -O0 and the LLVM-IR you get will use stack memory rather than (virtual) registers. Most passes expect -sroa (or mem2reg) to be run first in order for them to work properly.

3

Thanks for the suggestion!
Do I run it as opt -sroa -print-memdeps -analyze ./test.ll?
This does not appear to have an effect on the output.

4

You need to add -Xclang -disable-O0-optnone to the clang invocation or optnone will be in the IR and disable all optimizations/transformations. You can manually remove optnone from the IR as well. If you run sroa then you’ll see the entire code is removed as it is all unnecessary: Compiler Explorer

5

Ah, I see!
Is there a way to perform memory dependence analysis on non-optimized code?
My goal is to use LLVM on a minimal program, implementing a specific data-flow scenario.
This is the idea behind my example program above and why it only contains unnecessary code.

6

You did in the beginning. That said, there is little point in using things different to their intended behavior as the result is probably not useful for comparisons anyway.
I mean, if A requires B to work and I only run A, is it really a flaw of A if nothing happens?

Instead, use things as intended but make your example actually meaningful: Compiler Explorer
Note that SROA will still fold away most of the code even if you return/use b and c.
Thus, your “alias” is not really a problem because in SSA form the assignment simply folds away anyway.
Most non-trivial examples require input: Compiler Explorer