Question on Aliasing and invariant load hoisting

Hi,

I have the below test case.

–snip–
struct st {

int a;
int b;
};

int * ptr;
int x,y;

void bar(int *x);

void foo() {
struct st obj;
bar(&obj.b);
if(x)
obj.a =x;
else
obj.a =y;

for (int i=0; i<obj.a;i++)
ptr[i]=i;
}

–snip–

LLVM IR produced at -O3 is shown below.

ref: https://godbolt.org/z/WPlmfr

–Snip–

%8 = getelementptr inbounds %struct.st, %struct.st* %1, i64 0, i32 0, !dbg !39
store i32 %7, i32* %8, align 4, !dbg !40
call void @llvm.dbg.value(metadata i32 0, metadata !26, metadata !DIExpression()), !dbg !41
%9 = icmp sgt i32 %7, 0, !dbg !42
br i1 %9, label %10, label %12, !dbg !44

%11 = load i32*, i32** @ptr, align 8, !tbaa !45
br label %13, !dbg !44

call void @llvm.lifetime.end.p0i8(i64 8, i8* nonnull %2) #4, !dbg !47
ret void, !dbg !47

%14 = phi i64 [ 0, %10 ], [ %17, %13 ]
call void @llvm.dbg.value(metadata i64 %14, metadata !26, metadata !DIExpression()), !dbg !41
%15 = getelementptr inbounds i32, i32* %11, i64 %14, !dbg !48
%16 = trunc i64 %14 to i32, !dbg !49
store i32 %16, i32* %15, align 4, !dbg !49, !tbaa !33
%17 = add nuw nsw i64 %14, 1, !dbg !50
call void @llvm.dbg.value(metadata i32 undef, metadata !26, metadata !DIExpression(DW_OP_plus_uconst, 1, DW_OP_stack_value)), !dbg !41
%18 = load i32, i32* %8, align 4, !dbg !51, !tbaa !52
%19 = sext i32 %18 to i64, !dbg !42
%20 = icmp slt i64 %17, %19, !dbg !42
br i1 %20, label %13, label %12, !dbg !44, !llvm.loop !54
}
–Snip—

Question is why the load IR and sext IR (obj.a) is not getting hoisted out of the loop?
–Snip–

%18 = load i32, i32* %8, align 4, !dbg !51, !tbaa !52
%19 = sext i32 %18 to i64, !dbg !42

–Snip

is it because the “obj.a” can alias with “ptr” ?

We are passing only “&obj.b” to bar. But still variable “ptr” is considered to be aliasing with “obj.a” ?

regards,

Venkat.

Hi Venkataramanan,

is it because the "obj.a" can alias with "ptr" ?

Yes. At the IR level there's nothing to stop @bar from
getelementptring backwards and accessing other parts of %1.

I believe it would be somewhere between invalid and
implementation-defined[*] at the C or C++ levels, but modelling that
would be quite tricky. I thnk you'd need some kind of finer-grained
escape analysis, supported by metadata (because there are constructs
with otherwise very similar IR that *are* valid, for example if obj
was an int[2]).

Cheers.

Tim.

[*] Casts to/from ints are implementation-defined, so a compiler could
allow it via "(int *)((uintptr_t)x - 4)" regardless of what the
standard otherwise says. I don't recall seeing any discussion on
whether Clang does or wants to do that.

The whole object "escapes" into bar as it can be defined similar to the code below:

void bar(int *x) {
  struct st *ST = ((char*)x) - offsetof(struct st, b));
  ptr = &ST->a;
  *ptr = 999; // Initial upper bound, overwritten by ptr[0] = 0;
}

Hi Tim,

Thank you for the clarifying this.

Hi Venkataramanan,

is it because the “obj.a” can alias with “ptr” ?

Yes. At the IR level there’s nothing to stop @bar from
getelementptring backwards and accessing other parts of %1.

I believe it would be somewhere between invalid and
implementation-defined[*] at the C or C++ levels, but modelling that
would be quite tricky. I thnk you’d need some kind of finer-grained
escape analysis, supported by metadata (because there are constructs
with otherwise very similar IR that are valid, for example if obj
was an int[2]).

Cheers.

Tim.

So we can still do some inter procedural analysis, and check if only the passed bytes is accessed in all those escaping places?

[*] Casts to/from ints are implementation-defined, so a compiler could
allow it via “(int *)((uintptr_t)x - 4)” regardless of what the
standard otherwise says. I don’t recall seeing any discussion on
whether Clang does or wants to do that.

regards,
Venkat.

Hi Johannes,

The whole object “escapes” into bar as it can be defined similar to the code below:

void bar(int *x) {
struct st ST = ((char)x) - offsetof(struct st, b));
ptr = &ST->a;
*ptr = 999; // Initial upper bound, overwritten by ptr[0] = 0;
}

Yes I was trying to do this. Thank you.


Johannes Doerfert
Researcher

Argonne National Laboratory
Lemont, IL 60439, USA

jdoerfert@anl.gov

regards,
Venkat.