llvm dev - Jul 2019 - 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190709/3cea36d4/attachment.html>

Hi Venkataramanan,

On Mon, 8 Jul 2019 at 19:31, Venkataramanan Kumar via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> 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;
}


---------------------------------------
Johannes Doerfert
Researcher

Argonne National Laboratory
Lemont, IL 60439, USA

jdoerfert at anl.gov


________________________________________
From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of
Venkataramanan Kumar via llvm-dev <llvm-dev at lists.llvm.org>
Sent: Monday, July 8, 2019 13:31
To: llvm-dev
Subject: [llvm-dev] 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<http://struct.st>,
%struct.st<http://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 Tim,

Thank you for the clarifying this.

On Tue, 9 Jul 2019 at 00:58, Tim Northover <t.p.northover at gmail.com>
wrote:
> Hi Venkataramanan,
>
> On Mon, 8 Jul 2019 at 19:31, Venkataramanan Kumar via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> > 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190709/1565026b/attachment-0001.html>

Hi Johannes,

On Tue, 9 Jul 2019 at 01:01, Doerfert, Johannes <jdoerfert at anl.gov>
wrote:
> 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 at anl.gov
>
> regards,
Venkat.
> ________________________________________
> From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of
> Venkataramanan Kumar via llvm-dev <llvm-dev at lists.llvm.org>
> Sent: Monday, July 8, 2019 13:31
> To: llvm-dev
> Subject: [llvm-dev] 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<http://struct.st>,
%struct.st<
> http://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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190709/471e6f77/attachment.html>