This is an archive of the discontinued LLVM Phabricator instance.

[LoopIdiom] Keep TBAA when creating memcpy/memmove
ClosedPublic

Authored by wsmoses on Aug 17 2021, 10:36 AM.

Details

Summary

When upgrading a loop of load/store to a memcpy, the existing pass does not keep existing aliasing information. This patch allows existing aliasing information to be kept.

Diff Detail

Event Timeline

wsmoses created this revision.Aug 17 2021, 10:36 AM
wsmoses requested review of this revision.Aug 17 2021, 10:36 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 17 2021, 10:36 AM

Is there any intention why this patch misses adding TBAA to Builder::CreateMemSet?

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1387

/*Merge=*/

1397

/*isVolatile=*/

1401

/*isVolatile=*/

llvm/test/Transforms/LoopIdiom/memcpy-tbaa.ll
2

Use the new PM.

opt -passes="loop-idiom"

Hmm.. what does it mean to have a !tbaa tag on a llvm.memcpy/llvm.memmove ? The langref only seem to mention !tbaa.struct for llvm.memcpy. Is it allowed to have both a !tbaa and a !tbaa.struct ? What would that mean ?

llvm/test/Transforms/LoopIdiom/memcpy-tbaa.ll
20

Can you also add a testcase where the merge is done ? Also the actual !tbaa representation is missing for the check.

wsmoses updated this revision to Diff 370684.Sep 3 2021, 5:34 PM

Address comments

Hmm.. what does it mean to have a !tbaa tag on a llvm.memcpy/llvm.memmove ? The langref only seem to mention !tbaa.struct for llvm.memcpy. Is it allowed to have both a !tbaa and a !tbaa.struct ? What would that mean ?

I presume it's used to mark that the (src and dst) pointer have the aliasing properties of the given TBAA metadata for the entire range. I'm not sure about the lang ref, but it does appear that regular TBAA occurs on memcpy throughout the test suite.

wmoses@beast:/mnt/sabrent/wmoses/llvm-main/llvm/test ((HEAD detached from origin/main)) $ git grep "memcpy.*tbaa"
Analysis/TypeBasedAliasAnalysis/functionattrs.ll:  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %q, i64 %n, i1 false), !tbaa !1
Analysis/TypeBasedAliasAnalysis/functionattrs.ll:  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %q, i64 %n, i1 false), !tbaa !2
Analysis/TypeBasedAliasAnalysis/memcpyopt.ll:; CHECK-NEXT: tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* noundef nonnull align 1 dereferenceable(16) %p, i8* noundef nonnull align 1 dereferenceable(16) %q, i64 16, i1 false), !tbaa !0
Analysis/TypeBasedAliasAnalysis/memcpyopt.ll:  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %q, i64 16, i1 false), !tbaa !2
Analysis/TypeBasedAliasAnalysis/memcpyopt.ll:  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %q, i8* %p, i64 16, i1 false), !tbaa !2

The TBAA memcpyopt test has a meaningful use of the metadata on memcpy, namely:

$ cat Analysis/TypeBasedAliasAnalysis/memcpyopt.ll
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -S -tbaa -basic-aa -memcpyopt -instcombine < %s | FileCheck %s

target datalayout = "e-p:64:64:64"

; The second memcpy is redundant and can be deleted. There's an intervening store, but
; it has a TBAA tag which declares that it is unrelated.

define void @foo(i8* nocapture %p, i8* nocapture %q, i8* nocapture %s) nounwind {
; CHECK: @foo
; CHECK-NEXT: tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* noundef nonnull align 1 dereferenceable(16) %p, i8* noundef nonnull align 1 dereferenceable(16) %q, i64 16, i1 false), !tbaa !0
; CHECK-NEXT: store i8 2, i8* %s, align 1, !tbaa [[TAGA:!.*]]
; CHECK-NEXT: ret void
  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %q, i64 16, i1 false), !tbaa !2
  store i8 2, i8* %s, align 1, !tbaa !1
  tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %q, i8* %p, i64 16, i1 false), !tbaa !2
  ret void
}

declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1) nounwind

; CHECK: [[TAGA]] = !{[[TYPEA:!.*]], [[TYPEA]], i64 0}
; CHECK: [[TYPEA]] = !{!"A", !{{.*}}}
!0 = !{!"tbaa root"}
!1 = !{!3, !3, i64 0}
!2 = !{!4, !4, i64 0}
!3 = !{!"A", !0}
!4 = !{!"B", !0}

@jeroen.dobbelaere Is this good enough for now and we try it out?

  • A memmove test seems to be missing ?
  • When the tbaa format is in 'new struct path tbaa' (-Xclang -new-struct-path-tbaa) format, the resulting shuffling should not be valid ? aka, the new struct path tbaa contains offset and size. Offset is likely to be 0 and size should be the size of a single element.
    • Either that should be filtered out,
    • or the size should be adapted, (But what with about an unknown size ?)
    • or maybe it should be converted into 'struct path tbaa' ?
wsmoses updated this revision to Diff 402383.Jan 23 2022, 7:20 PM
wsmoses marked 2 inline comments as done.

Add memmove test and properly handle new-struct-path tbaa

@jeroen.dobbelaere Finally got around to updating this. Per your comments it now tests memmove and correctly deals with new-struct-tbaa (adding a relevant helper utility).

Let me know if you think this is good to land.

I checked the testcases for now and found some interesting effects. Can you comment on those ?

llvm/test/Transforms/LoopIdiom/memcpy-tbaa.ll
46

I get !tbaa %0. Is this what we would expect ? Shouldn't the tbaa be dropped here ? (float vs double)

82

; CHECK-NOT: tbaa

143

Shouldn't this be on the next line ?

llvm/test/Transforms/LoopIdiom/memmove-tbaa.ll
37 ↗(On Diff #402383)

I get !tbaa %0. Is this what we would expect ? Shouldn't the tbaa be dropped here ? (float vs double)

64 ↗(On Diff #402383)

This should be on the next line

wsmoses updated this revision to Diff 404622.Jan 31 2022, 11:08 AM
wsmoses marked 5 inline comments as done.

Fix rebase regression

llvm/test/Transforms/LoopIdiom/memcpy-tbaa.ll
46

Good catch, it appears the merge has become not in place. Fixed

wsmoses marked 3 inline comments as done.Jan 31 2022, 11:09 AM

Sorry about not mentioning it with the previous part.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1174

We will also need a memset test.

wsmoses updated this revision to Diff 404635.Jan 31 2022, 11:29 AM

Add memset test

wsmoses marked an inline comment as done.Jan 31 2022, 11:29 AM
wsmoses added inline comments.
llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
1174

Added, apparently I hadn't done a git add.

wsmoses updated this revision to Diff 404640.Jan 31 2022, 11:39 AM
wsmoses marked an inline comment as done.

Add memset struct-path tests

LGTM. Thanks !

This revision is now accepted and ready to land.Jan 31 2022, 12:10 PM
This revision was landed with ongoing or failed builds.Jan 31 2022, 1:28 PM
This revision was automatically updated to reflect the committed changes.