Hi,
I have a doubt with GEP transformation in the instruction-combiner.
Consider below test-case:
struct ABC {
int A;
int B[100];
struct XYZ {
int X;
int Y[100];
} OBJ;
};
void Setup(struct ABC *);
int foo(int offset) {
struct ABC *Ptr = malloc(sizeof(struct ABC));
Setup(Ptr);
return Ptr->OBJ.X + Ptr->OBJ.Y[33];
}
Generated IR for the test-case:
define i32 @foo(i32 %offset) local_unnamed_addr #0 {
entry:
%call = tail call i8* @malloc(i64 808)
%0 = bitcast i8* %call to %struct.ABC*
tail call void @Setup(%struct.ABC* %0) #3
%OBJ = getelementptr inbounds i8, i8* %call, i64 404
%X = bitcast i8* %OBJ to i32*
%1 = load i32, i32* %X, align 4, !tbaa !2
%arrayidx = getelementptr inbounds i8, i8* %call, i64 540
%2 = bitcast i8* %arrayidx to i32*
%3 = load i32, i32* %2, align 4, !tbaa !8
%add = add nsw i32 %3, %1
ret i32 %add
}
Instruction combiner transforms GEPs to i8 type, because of this the GEP offset
looks weird and the actual type information is missing on GEP.
I expected the GEPs to use the actual type offsetting for which the memory is
allocated.
Expected IR:
; Function Attrs: nounwind uwtable
define i32 @foo(i32 %offset) local_unnamed_addr #0 {
entry:
%call = tail call i8* @malloc(i64 808)
%0 = bitcast i8* %call to %struct.ABC*
tail call void @Setup(%struct.ABC* %0) #3
%X = getelementptr inbounds %struct.ABC, %struct.ABC* %0, i64 0, i32 2, i32 0
%1 = load i32, i32* %X, align 4, !tbaa !2
%arrayidx = getelementptr inbounds %struct.ABC, %struct.ABC* %0, i64 0, i32 2,
i32 1, i64 33
%2 = load i32, i32* %arrayidx, align 4, !tbaa !8
%add = add nsw i32 %2, %1
ret i32 %add
}
In the above IR the GEP offsetting looks very explicit for the type struct.ABC.
Looking at the InstCombiner source found the below code is responsible for it:
1914 /// See if we can simplify:
1915 /// X = bitcast A* to B*
1916 /// Y = gep X, <...constant indices...>
1917 /// into a gep of the original struct. This is important for SROA and
alias
1918 /// analysis of unions. If "A" is also a bitcast, wait for A/X
to be merged.
1919 if (BitCastInst *BCI = dyn_cast<BitCastInst>(PtrOp)) {
1920 ....
I'm not sure how transforming GEP offset to i8 type will help alias analysis
& SROA for the mentioned test case.
Regards,
Ashutosh
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170810/f17a3f0e/attachment.html>
I agree that’s a bit strange.
I dunno about SROA, but BasicAA certainly knows about structs and unions. I
don’t think right now it has any problem handling those. (and if there’s some
case it doesn’t, shouldn’t be hard to fix)
Also, BasicAA has special rules for arrays of structs that can conclude no-alias
even if some of the indexes aren’t constants. So you could even turn those
no-alias results into may-alias; instcombine is losing information here.
I guess you could lookup the history to see why/when that transformation was
introduced if noone remembers.
Nuno
From: Nema, Ashutosh via llvm-dev
Sent: Thursday, August 10, 2017 8:22 AM
To: llvm-dev
Subject: [llvm-dev] InstCombine GEP
Hi,
I have a doubt with GEP transformation in the instruction-combiner.
Consider below test-case:
struct ABC {
int A;
int B[100];
struct XYZ {
int X;
int Y[100];
} OBJ;
};
void Setup(struct ABC *);
int foo(int offset) {
struct ABC *Ptr = malloc(sizeof(struct ABC));
Setup(Ptr);
return Ptr->OBJ.X + Ptr->OBJ.Y[33];
}
Generated IR for the test-case:
define i32 @foo(i32 %offset) local_unnamed_addr #0 {
entry:
%call = tail call i8* @malloc(i64 808)
%0 = bitcast i8* %call to %struct.ABC*
tail call void @Setup(%struct.ABC* %0) #3
%OBJ = getelementptr inbounds i8, i8* %call, i64 404
%X = bitcast i8* %OBJ to i32*
%1 = load i32, i32* %X, align 4, !tbaa !2
%arrayidx = getelementptr inbounds i8, i8* %call, i64 540
%2 = bitcast i8* %arrayidx to i32*
%3 = load i32, i32* %2, align 4, !tbaa !8
%add = add nsw i32 %3, %1
ret i32 %add
}
Instruction combiner transforms GEPs to i8 type, because of this the GEP offset
looks weird and the actual type information is missing on GEP.
I expected the GEPs to use the actual type offsetting for which the memory is
allocated.
Expected IR:
; Function Attrs: nounwind uwtable
define i32 @foo(i32 %offset) local_unnamed_addr #0 {
entry:
%call = tail call i8* @malloc(i64 808)
%0 = bitcast i8* %call to %struct.ABC*
tail call void @Setup(%struct.ABC* %0) #3
%X = getelementptr inbounds %struct.ABC, %struct.ABC* %0, i64 0, i32 2, i32 0
%1 = load i32, i32* %X, align 4, !tbaa !2
%arrayidx = getelementptr inbounds %struct.ABC, %struct.ABC* %0, i64 0, i32 2,
i32 1, i64 33
%2 = load i32, i32* %arrayidx, align 4, !tbaa !8
%add = add nsw i32 %2, %1
ret i32 %add
}
In the above IR the GEP offsetting looks very explicit for the type struct.ABC.
Looking at the InstCombiner source found the below code is responsible for it:
1914 /// See if we can simplify:
1915 /// X = bitcast A* to B*
1916 /// Y = gep X, <...constant indices...>
1917 /// into a gep of the original struct. This is important for SROA and
alias
1918 /// analysis of unions. If "A" is also a bitcast, wait for A/X
to be merged.
1919 if (BitCastInst *BCI = dyn_cast<BitCastInst>(PtrOp)) {
1920 ....
I’m not sure how transforming GEP offset to i8 type will help alias analysis
& SROA for the mentioned test case.
Regards,
Ashutosh
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170810/28bf3864/attachment.html>
Hi Ashutosh, On Thu, Aug 10, 2017 at 12:22 AM, Nema, Ashutosh via llvm-dev <llvm-dev at lists.llvm.org> wrote:> I’m not sure how transforming GEP offset to i8 type will help alias analysis > & SROA for the mentioned test case.It should neither help nor hinder AA or SROA -- the two GEPs (the complex one and the simple one) are equivalent. Since memory isn't typed in LLVM, having the GEP in terms of %struct.ABC does not provide any extra information. -- Sanjoy> > > > Regards, > > Ashutosh > > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >
> On Thu, Aug 10, 2017 at 12:22 AM, Nema, Ashutosh via llvm-dev <llvm-dev at lists.llvm.org> wrote: >> I’m not sure how transforming GEP offset to i8 type will help alias >> analysis & SROA for the mentioned test case. > > It should neither help nor hinder AA or SROA -- the two GEPs (the complex one and the simple one) are equivalent. > Since memory isn't typed in LLVM, having the GEP in terms of %struct.ABC does not provide any extra information.Memory is somewhat typed, since if you store something with a type and load the same location with a different type that's not valid (let's call it poison). Also, BasicAA has the following rule, with constants c1 and c2, and arbitrary values x, y: a[x][c1] no-alias a[y][c2] if: the distance between c1 and c2 is sufficient to guarantee that the accesses will be disjoint due to ending up in different array slots. For this rule it's important to know what's the size of each array element. This information is lost if GEPs are flattened. But I agree that LLVM itself doesn't exploit types for AA extensively. For example, a pointer based in a struct field may alias another field of the same struct, even if at C/C++ level that's probably not allowed. Nuno
On Thu, Aug 10, 2017 at 10:24 AM, Sanjoy Das via llvm-dev < llvm-dev at lists.llvm.org> wrote:> Hi Ashutosh, > > On Thu, Aug 10, 2017 at 12:22 AM, Nema, Ashutosh via llvm-dev > <llvm-dev at lists.llvm.org> wrote: > > I’m not sure how transforming GEP offset to i8 type will help alias > analysis > > & SROA for the mentioned test case. > > It should neither help nor hinder AA or SROA -- the two GEPs (the > complex one and the simple one) are equivalent. Since memory isn't > typed in LLVM, having the GEP in terms of %struct.ABC does not provide > any extra information. >FWIW: Having memory be untyped strongly hinders field sensitive analysis :) It's okay for non, obviously. I also get the desire to avoid bitcasts. But field-sensitive analysis of any sort requires knowing that memory has structures and arrays, and we've said "no it doesn't :) So either you spend all your time trying to recover that based on the indexing operations you see(at precision loss), provide metadata and base your analysis on the metadata (which must stay semantically correct, since you are effectively ignoring the addressing operation), or give up. (Analyses like DSA attempt to recover it). We already miss pretty basic field aliasing cases in C++ due to the above :( -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170814/bd36a6ee/attachment.html>