[GVN] Propagate llvm.access.group metadata of loads

[kawashima-fj]

Summary

Before this change, the llvm.access.group metadata was dropped
when moving a load instruction in GVN. This prevents vectorizing
a C/C++ loop with #pragma clang loop vectorize(assume_safety).
This change propagates the metadata as well as other metadata if
it is safe (the move-destination basic block and source basic
block belong to the same loop).

[kawashima-fj]

Ping.
I know many people are on holiday this week. If you have time, please review this patch. I'm on holiday from tomorrow.

[kawashima-fj]

Ping.
Can anyone review? Is there an appropriate reviewer?

[fhahn]

This seems reasonable to me, as we should only reduce the number of loads executed during PRE. If they are in the same loop, the metadata should stay valid, as we do not access any additional locations.

Would it be possible to add a simple test case where we move a load from a sub-loop into a parent loop?

llvm/test/Transforms/GVN/PRE/load-pre-metadata-accsess-group.ll

9

can you simplify the test to only the required instructions? e.g. not all access here should be needed, nor all parameters, nor all arithmetic instructions, etc

Once it is cut down, it would probably be good to explicitly match the blocks that were inserted as part of GVN PRE.

Also, do we need the dedicated preheader/exit blocks?

[kawashima-fj]

Simplify the test code.

[kawashima-fj]

In D93503#2479425, @fhahn wrote:

This seems reasonable to me, as we should only reduce the number of loads executed during PRE. If they are in the same loop, the metadata should stay valid, as we do not access any additional locations.

Would it be possible to add a simple test case where we move a load from a sub-loop into a parent loop?

Thanks for your review.
The test in the previous revision is refined. I might not understand your comment correctly. If I missed something, please let me know.
My colleague, who fixed this issue, is busy now. The requested additional test can be added next week or so.

[asbirlea]

Looks reasonable to me as well, that the metadata info should hold at the same loop level.

[fhahn]

In D93503#2483527, @kawashima-fj wrote:

In D93503#2479425, @fhahn wrote:

This seems reasonable to me, as we should only reduce the number of loads executed during PRE. If they are in the same loop, the metadata should stay valid, as we do not access any additional locations.

Would it be possible to add a simple test case where we move a load from a sub-loop into a parent loop?

Thanks for your review.
The test in the previous revision is refined. I might not understand your comment correctly. If I missed something, please let me know.

Thanks for cleaning up the test. It left a few additional small suggestions. I think for that test it would be good to add CHECK lines for all code generated during PRE. Given it is quite small, you could use llvm/utils/update_test_checks.py to auto-generate the check lines. Also, I think it would be good to pre-commit the test with check lines for current trunk and then update the patch to just show the diff in CHECK lines with this patch.

My colleague, who fixed this issue, is busy now. The requested additional test can be added next week or so.

That would be great.

llvm/test/Transforms/GVN/PRE/load-pre-metadata-accsess-group.ll

32

Is the !llvm.loop metadata needed?

34

That should not be needed.

[kawashima-fj]

Update test.

• Remove unnecessary metadata (!llvm.loop, llvm.loop.parallel_accesses, llvm.loop.vectorize.enable)
• Add a test (function) which moves a load from a sub-loop into a parent loop
• Use llvm/utils/update_test_checks.py to generate CHECK lines

[kawashima-fj]

I'm sorry for the late response. I (and my colleague) updated the test.

In D93503#2484226, @fhahn wrote:

Thanks for cleaning up the test. It left a few additional small suggestions. I think for that test it would be good to add CHECK lines for all code generated during PRE. Given it is quite small, you could use llvm/utils/update_test_checks.py to auto-generate the check lines. Also, I think it would be good to pre-commit the test with check lines for current trunk and then update the patch to just show the diff in CHECK lines with this patch.

You mean I should push two commits to the GitHub repository, right?
The first one is only the test file with CHECK-lines generated by update_test_checks.py with current master branch.
The second one is update of the GVN source file and CHECK-lines generated by update_test_checks.py with the new source code.
I'm newbie to LLVM. Your suggestion is very helpful. Thanks.

llvm/test/Transforms/GVN/PRE/load-pre-metadata-accsess-group.ll

32

llvm.loop is removed.

34

llvm.loop.vectorize.enable is removed.

[kawashima-fj]

Ping.
@fhahn @asbirlea Is this OK?

[asbirlea]

LGTM.
Please wait to see if @fhahn has additional feedback.

[kawashima-fj]

@fhahn Ping. Could you confirm?

[kawashima-fj]

@fhahn Ping. Could you confirm?

[kawashima-fj]

@fhahn Ping. I addressed your comment.

[fhahn]

In D93503#2500308, @kawashima-fj wrote:

I'm sorry for the late response. I (and my colleague) updated the test.

In D93503#2484226, @fhahn wrote:

Thanks for cleaning up the test. It left a few additional small suggestions. I think for that test it would be good to add CHECK lines for all code generated during PRE. Given it is quite small, you could use llvm/utils/update_test_checks.py to auto-generate the check lines. Also, I think it would be good to pre-commit the test with check lines for current trunk and then update the patch to just show the diff in CHECK lines with this patch.

You mean I should push two commits to the GitHub repository, right?
The first one is only the test file with CHECK-lines generated by update_test_checks.py with current master branch.
The second one is update of the GVN source file and CHECK-lines generated by update_test_checks.py with the new source code.

Yep that would be the idea. You can just push the update to the existing test and then update the review.

The change LGTM.

llvm/lib/Transforms/Scalar/GVN.cpp

if (Tags)
       NewLoad->setAAMetadata(Tags);
 
     if (auto *MD = LI->getMetadata(LLVMContext::MD_invariant_load))
       NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);
     if (auto *InvGroupMD = LI->getMetadata(LLVMContext::MD_invariant_group))
       NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);
     if (auto *RangeMD = LI->getMetadata(LLVMContext::MD_range))
       NewLoad->setMetadata(LLVMContext::MD_range, RangeMD);
+    if (auto *AccessMD = LI->getMetadata(LLVMContext::MD_access_group))
+      if (this->LI && this->LI->getLoopFor(LI->getParent()) ==
+                          this->LI->getLoopFor(UnavailablePred))
+        NewLoad->setMetadata(LLVMContext::MD_access_group, AccessMD);
 
     // We do not propagate the old load's debug location, because the new
     // load now lives in a different BB, and we want to avoid a jumpy line
     // table.
     // FIXME: How do we retain source locations without causing poor debugging
     // behavior?
 
     // Add the newly created load.

llvm/test/Transforms/GVN/PRE/load-pre-metadata-accsess-group.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -basic-aa -gvn -enable-load-pre -S | FileCheck %s
+
+define dso_local void @test1(i32* nocapture readonly %aa, i32* nocapture %bb) local_unnamed_addr {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[IDX:%.*]] = getelementptr inbounds i32, i32* [[BB:%.*]], i64 1
+; CHECK-NEXT:    [[IDX2:%.*]] = getelementptr inbounds i32, i32* [[AA:%.*]], i64 1
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[IDX2]], align 4
+; CHECK-NEXT:    store i32 [[TMP0]], i32* [[IDX]], align 4
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ [[TMP0]], [[ENTRY:%.*]] ], [ [[DOTPRE:%.*]], [[FOR_BODY_FOR_BODY_CRIT_EDGE:%.*]] ]
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY_FOR_BODY_CRIT_EDGE]] ]
+; CHECK-NEXT:    [[IDX4:%.*]] = getelementptr inbounds i32, i32* [[AA]], i64 [[INDVARS_IV]]
+; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* [[IDX4]], align 4, !llvm.access.group !0
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    store i32 [[MUL]], i32* [[IDX4]], align 4, !llvm.access.group !0
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], 100
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY_FOR_BODY_CRIT_EDGE]], label [[FOR_END:%.*]]
+; CHECK:       for.body.for.body_crit_edge:
+; CHECK-NEXT:    [[DOTPRE]] = load i32, i32* [[IDX]], align 4, !llvm.access.group !0
+; CHECK-NEXT:    br label [[FOR_BODY]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %idx = getelementptr inbounds i32, i32* %bb, i64 1
+  %idx2 = getelementptr inbounds i32, i32* %aa, i64 1
+  %0 = load i32, i32* %idx2, align 4
+  store i32 %0, i32* %idx, align 4
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %idx4 = getelementptr inbounds i32, i32* %aa, i64 %indvars.iv
+  %1 = load i32, i32* %idx4, align 4, !llvm.access.group !0
+  %2 = load i32, i32* %idx, align 4, !llvm.access.group !0
+  %mul = mul nsw i32 %2, %1
+  store i32 %mul, i32* %idx4, align 4, !llvm.access.group !0
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 100
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+!0 = distinct !{}
+
+define dso_local void @test2(i32* nocapture readonly %aa, i32* nocapture %bb) local_unnamed_addr {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[IDX:%.*]] = getelementptr inbounds i32, i32* [[BB:%.*]], i64 1
+; CHECK-NEXT:    [[IDX2:%.*]] = getelementptr inbounds i32, i32* [[AA:%.*]], i64 1
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[IDX2]], align 4
+; CHECK-NEXT:    store i32 [[TMP0]], i32* [[IDX]], align 4
+; CHECK-NEXT:    [[DOTPRE:%.*]] = load i32, i32* [[AA]], align 4
+; CHECK-NEXT:    br label [[FOR_BODY2:%.*]]
+; CHECK:       for.body2:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ [[TMP0]], [[FOR_BODY]] ], [ [[DOTPRE1:%.*]], [[FOR_BODY2_FOR_BODY2_CRIT_EDGE:%.*]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i32 [ [[DOTPRE]], [[FOR_BODY]] ], [ [[MUL:%.*]], [[FOR_BODY2_FOR_BODY2_CRIT_EDGE]] ]
+; CHECK-NEXT:    [[INDVARS2_IV:%.*]] = phi i64 [ 0, [[FOR_BODY]] ], [ 1, [[FOR_BODY2_FOR_BODY2_CRIT_EDGE]] ]
+; CHECK-NEXT:    [[MUL]] = mul nsw i32 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    store i32 [[MUL]], i32* [[AA]], align 4, !llvm.access.group !1
+; CHECK-NEXT:    br i1 true, label [[FOR_BODY2_FOR_BODY2_CRIT_EDGE]], label [[FOR_END:%.*]]
+; CHECK:       for.body2.for.body2_crit_edge:
+; CHECK-NEXT:    [[DOTPRE1]] = load i32, i32* [[IDX]], align 4, !llvm.access.group !1
+; CHECK-NEXT:    br label [[FOR_BODY2]]
+; CHECK:       for.end:
+; CHECK-NEXT:    br i1 false, label [[FOR_END_FOR_BODY_CRIT_EDGE:%.*]], label [[END:%.*]]
+; CHECK:       for.end.for.body_crit_edge:
+; CHECK-NEXT:    br label [[FOR_BODY]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.end ]
+  %idx = getelementptr inbounds i32, i32* %bb, i64 1
+  %idx2 = getelementptr inbounds i32, i32* %aa, i64 1
+  %0 = load i32, i32* %idx2, align 4
+  store i32 %0, i32* %idx, align 4
+  br label %for.body2
+
+for.body2:
+  %indvars2.iv = phi i64 [ 0, %for.body ], [ %indvars2.iv.next, %for.body2 ]
+  %idx4 = getelementptr inbounds i32, i32* %aa, i64 %indvars.iv
+  %1 = load i32, i32* %idx4, align 4, !llvm.access.group !1
+  %2 = load i32, i32* %idx, align 4, !llvm.access.group !1
+  %mul = mul nsw i32 %2, %1
+  store i32 %mul, i32* %idx4, align 4, !llvm.access.group !1
+  %indvars2.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond2 = icmp ne i64 %indvars2.iv.next, 100
+  br i1 %exitcond2, label %for.body2, label %for.end
+
+for.end:
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp ne i64 %indvars.iv.next, 100
+  br i1 %exitcond, label %for.body, label %end
+
+end:
+  ret void
+}
+
+!1 = distinct !{}