From fc7654a67b314cbd75d8268544be8b69fbe99cdd Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Sat, 27 Oct 2018 16:53:45 +0000 Subject: [PATCH] [Local] Keep K's range if K does not move when combining metadata. As K has to dominate I, IIUC I's range metadata must be a subset of K's. After Eli's recent clarification to the LangRef, loading a value outside of the range is undefined behavior. Therefore if I's range contains elements outside of K's range and we would load one such value, K would cause undefined behavior. In cases like hoisting/sinking, we still want the most generic range over all code paths to/from the hoist/sink point. As suggested in the patches related to D47339, I will refactor the handling of those scenarios and try to decouple it from this function as follow up, once we switched to a similar handling of metadata in most of combineMetadata. I updated some tests checking mostly the merging of metadata to keep the metadata of to dominating load. The most interesting one is probably test8 in test/Transforms/JumpThreading/thread-loads.ll. It contained a comment about the alias metadata preventing us to eliminate the branch, but it seem like the actual problem currently is that we merge the ranges of both loads and cannot eliminate the icmp afterwards. With this patch, we manage to eliminate the icmp, as the range of the first load excludes 8. Reviewers: efriedma, nlopes, davide Reviewed By: efriedma Differential Revision: https://reviews.llvm.org/D51629 llvm-svn: 345456 --- llvm/lib/Transforms/Utils/Local.cpp | 10 +++++++- llvm/test/Transforms/GVN/range.ll | 27 +++++++++++----------- .../InstCombine/load-combine-metadata.ll | 2 +- llvm/test/Transforms/JumpThreading/thread-loads.ll | 12 ++++++---- llvm/test/Transforms/NewGVN/range.ll | 27 +++++++++++----------- 5 files changed, 44 insertions(+), 34 deletions(-) diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp index 82fb765..0dcd737 100644 --- a/llvm/lib/Transforms/Utils/Local.cpp +++ b/llvm/lib/Transforms/Utils/Local.cpp @@ -2315,7 +2315,15 @@ void llvm::combineMetadata(Instruction *K, const Instruction *J, K->setMetadata(Kind, MDNode::intersect(JMD, KMD)); break; case LLVMContext::MD_range: - K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD)); + + // If K does move, use most generic range. Otherwise keep the range of + // K. + if (DoesKMove) + // FIXME: If K does move, we should drop the range info and nonnull. + // Currently this function is used with DoesKMove in passes + // doing hoisting/sinking and the current behavior of using the + // most generic range is correct in those cases. + K->setMetadata(Kind, MDNode::getMostGenericRange(JMD, KMD)); break; case LLVMContext::MD_fpmath: K->setMetadata(Kind, MDNode::getMostGenericFPMath(JMD, KMD)); diff --git a/llvm/test/Transforms/GVN/range.ll b/llvm/test/Transforms/GVN/range.ll index 39acc0c..fd5fa56b 100644 --- a/llvm/test/Transforms/GVN/range.ll +++ b/llvm/test/Transforms/GVN/range.ll @@ -2,7 +2,7 @@ define i32 @test1(i32* %p) { ; CHECK-LABEL: @test1(i32* %p) -; CHECK: %a = load i32, i32* %p, !range !0 +; CHECK: %a = load i32, i32* %p, !range ![[RANGE0:[0-9]+]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !0 %b = load i32, i32* %p, !range !0 @@ -12,8 +12,7 @@ define i32 @test1(i32* %p) { define i32 @test2(i32* %p) { ; CHECK-LABEL: @test2(i32* %p) -; CHECK: %a = load i32, i32* %p -; CHECK-NOT: range +; CHECK: %a = load i32, i32* %p, !range ![[RANGE0]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !0 %b = load i32, i32* %p @@ -23,7 +22,7 @@ define i32 @test2(i32* %p) { define i32 @test3(i32* %p) { ; CHECK-LABEL: @test3(i32* %p) -; CHECK: %a = load i32, i32* %p, !range ![[DISJOINT_RANGE:[0-9]+]] +; CHECK: %a = load i32, i32* %p, !range ![[RANGE0]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !0 %b = load i32, i32* %p, !range !1 @@ -33,7 +32,7 @@ define i32 @test3(i32* %p) { define i32 @test4(i32* %p) { ; CHECK-LABEL: @test4(i32* %p) -; CHECK: %a = load i32, i32* %p, !range ![[MERGED_RANGE:[0-9]+]] +; CHECK: %a = load i32, i32* %p, !range ![[RANGE0]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !0 %b = load i32, i32* %p, !range !2 @@ -43,7 +42,7 @@ define i32 @test4(i32* %p) { define i32 @test5(i32* %p) { ; CHECK-LABEL: @test5(i32* %p) -; CHECK: %a = load i32, i32* %p, !range ![[MERGED_SIGNED_RANGE:[0-9]+]] +; CHECK: %a = load i32, i32* %p, !range ![[RANGE3:[0-9]+]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !3 %b = load i32, i32* %p, !range !4 @@ -53,7 +52,7 @@ define i32 @test5(i32* %p) { define i32 @test6(i32* %p) { ; CHECK-LABEL: @test6(i32* %p) -; CHECK: %a = load i32, i32* %p, !range ![[MERGED_TEST6:[0-9]+]] +; CHECK: %a = load i32, i32* %p, !range ![[RANGE5:[0-9]+]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !5 %b = load i32, i32* %p, !range !6 @@ -63,7 +62,7 @@ define i32 @test6(i32* %p) { define i32 @test7(i32* %p) { ; CHECK-LABEL: @test7(i32* %p) -; CHECK: %a = load i32, i32* %p, !range ![[MERGED_TEST7:[0-9]+]] +; CHECK: %a = load i32, i32* %p, !range ![[RANGE7:[0-9]+]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !7 %b = load i32, i32* %p, !range !8 @@ -73,7 +72,7 @@ define i32 @test7(i32* %p) { define i32 @test8(i32* %p) { ; CHECK-LABEL: @test8(i32* %p) -; CHECK: %a = load i32, i32* %p +; CHECK: %a = load i32, i32* %p, !range ![[RANGE9:[0-9]+]] ; CHECK-NOT: range ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !9 @@ -82,11 +81,11 @@ define i32 @test8(i32* %p) { ret i32 %c } -; CHECK: ![[DISJOINT_RANGE]] = !{i32 0, i32 2, i32 3, i32 5} -; CHECK: ![[MERGED_RANGE]] = !{i32 0, i32 5} -; CHECK: ![[MERGED_SIGNED_RANGE]] = !{i32 -5, i32 -2, i32 1, i32 5} -; CHECK: ![[MERGED_TEST6]] = !{i32 10, i32 1} -; CHECK: ![[MERGED_TEST7]] = !{i32 3, i32 4, i32 5, i32 2} +; CHECK: ![[RANGE0]] = !{i32 0, i32 2} +; CHECK: ![[RANGE3]] = !{i32 -5, i32 -2} +; CHECK: ![[RANGE5]] = !{i32 10, i32 1} +; CHECK: ![[RANGE7]] = !{i32 1, i32 2, i32 3, i32 4} +; CHECK: ![[RANGE9]] = !{i32 1, i32 5} !0 = !{i32 0, i32 2} !1 = !{i32 3, i32 5} diff --git a/llvm/test/Transforms/InstCombine/load-combine-metadata.ll b/llvm/test/Transforms/InstCombine/load-combine-metadata.ll index b7f42e7..536f1bb 100644 --- a/llvm/test/Transforms/InstCombine/load-combine-metadata.ll +++ b/llvm/test/Transforms/InstCombine/load-combine-metadata.ll @@ -17,7 +17,7 @@ define void @test_load_load_combine_metadata(i32*, i32*, i32*) { ret void } -; CHECK: ![[RANGE]] = !{i32 0, i32 5, i32 7, i32 9} +; CHECK: ![[RANGE]] = !{i32 0, i32 5} !0 = !{ i32 0, i32 5 } !1 = !{ i32 7, i32 9 } !2 = !{!2} diff --git a/llvm/test/Transforms/JumpThreading/thread-loads.ll b/llvm/test/Transforms/JumpThreading/thread-loads.ll index 3606e79..1156f39 100644 --- a/llvm/test/Transforms/JumpThreading/thread-loads.ll +++ b/llvm/test/Transforms/JumpThreading/thread-loads.ll @@ -246,13 +246,15 @@ bb3: ret i32 %res.0 } -; Make sure we merge the aliasing metadata. (If we don't, we have a load -; with the wrong metadata, so the branch gets incorrectly eliminated.) +; Make sure we merge the aliasing metadata. We keep the range metadata for the +; first load, as it dominates the second load. Hence we can eliminate the +; branch. define void @test8(i32*, i32*, i32*) { ; CHECK-LABEL: @test8( -; CHECK: %a = load i32, i32* %0, !range !4 +; CHECK: %a = load i32, i32* %0, !range ![[RANGE4:[0-9]+]] ; CHECK-NEXT: store i32 %a -; CHECK: br i1 %c +; CHECK-NEXT: %xxx = tail call i32 (...) @f1() +; CHECK-NEXT: ret void %a = load i32, i32* %0, !tbaa !0, !range !4, !alias.scope !9, !noalias !10 %b = load i32, i32* %0, !range !5 store i32 %a, i32* %1 @@ -525,6 +527,8 @@ right_x: ret i32 10 } +; CHECK: ![[RANGE4]] = !{i32 0, i32 1} + !0 = !{!3, !3, i64 0} !1 = !{!"omnipotent char", !2} !2 = !{!"Simple C/C++ TBAA"} diff --git a/llvm/test/Transforms/NewGVN/range.ll b/llvm/test/Transforms/NewGVN/range.ll index 55efa59..29b911c 100644 --- a/llvm/test/Transforms/NewGVN/range.ll +++ b/llvm/test/Transforms/NewGVN/range.ll @@ -2,7 +2,7 @@ define i32 @test1(i32* %p) { ; CHECK-LABEL: @test1(i32* %p) -; CHECK: %a = load i32, i32* %p, !range !0 +; CHECK: %a = load i32, i32* %p, !range ![[RANGE0:[0-9]+]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !0 %b = load i32, i32* %p, !range !0 @@ -12,8 +12,7 @@ define i32 @test1(i32* %p) { define i32 @test2(i32* %p) { ; CHECK-LABEL: @test2(i32* %p) -; CHECK: %a = load i32, i32* %p -; CHECK-NOT: range +; CHECK: %a = load i32, i32* %p, !range ![[RANGE0]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !0 %b = load i32, i32* %p @@ -23,7 +22,7 @@ define i32 @test2(i32* %p) { define i32 @test3(i32* %p) { ; CHECK-LABEL: @test3(i32* %p) -; CHECK: %a = load i32, i32* %p, !range ![[DISJOINT_RANGE:[0-9]+]] +; CHECK: %a = load i32, i32* %p, !range ![[RANGE0]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !0 %b = load i32, i32* %p, !range !1 @@ -33,7 +32,7 @@ define i32 @test3(i32* %p) { define i32 @test4(i32* %p) { ; CHECK-LABEL: @test4(i32* %p) -; CHECK: %a = load i32, i32* %p, !range ![[MERGED_RANGE:[0-9]+]] +; CHECK: %a = load i32, i32* %p, !range ![[RANGE0]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !0 %b = load i32, i32* %p, !range !2 @@ -43,7 +42,7 @@ define i32 @test4(i32* %p) { define i32 @test5(i32* %p) { ; CHECK-LABEL: @test5(i32* %p) -; CHECK: %a = load i32, i32* %p, !range ![[MERGED_SIGNED_RANGE:[0-9]+]] +; CHECK: %a = load i32, i32* %p, !range ![[RANGE3:[0-9]+]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !3 %b = load i32, i32* %p, !range !4 @@ -53,7 +52,7 @@ define i32 @test5(i32* %p) { define i32 @test6(i32* %p) { ; CHECK-LABEL: @test6(i32* %p) -; CHECK: %a = load i32, i32* %p, !range ![[MERGED_TEST6:[0-9]+]] +; CHECK: %a = load i32, i32* %p, !range ![[RANGE5:[0-9]+]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !5 %b = load i32, i32* %p, !range !6 @@ -63,7 +62,7 @@ define i32 @test6(i32* %p) { define i32 @test7(i32* %p) { ; CHECK-LABEL: @test7(i32* %p) -; CHECK: %a = load i32, i32* %p, !range ![[MERGED_TEST7:[0-9]+]] +; CHECK: %a = load i32, i32* %p, !range ![[RANGE7:[0-9]+]] ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !7 %b = load i32, i32* %p, !range !8 @@ -73,7 +72,7 @@ define i32 @test7(i32* %p) { define i32 @test8(i32* %p) { ; CHECK-LABEL: @test8(i32* %p) -; CHECK: %a = load i32, i32* %p +; CHECK: %a = load i32, i32* %p, !range ![[RANGE9:[0-9]+]] ; CHECK-NOT: range ; CHECK: %c = add i32 %a, %a %a = load i32, i32* %p, !range !9 @@ -82,11 +81,11 @@ define i32 @test8(i32* %p) { ret i32 %c } -; CHECK: ![[DISJOINT_RANGE]] = !{i32 0, i32 2, i32 3, i32 5} -; CHECK: ![[MERGED_RANGE]] = !{i32 0, i32 5} -; CHECK: ![[MERGED_SIGNED_RANGE]] = !{i32 -5, i32 -2, i32 1, i32 5} -; CHECK: ![[MERGED_TEST6]] = !{i32 10, i32 1} -; CHECK: ![[MERGED_TEST7]] = !{i32 3, i32 4, i32 5, i32 2} +; CHECK: ![[RANGE0]] = !{i32 0, i32 2} +; CHECK: ![[RANGE3]] = !{i32 -5, i32 -2} +; CHECK: ![[RANGE5]] = !{i32 10, i32 1} +; CHECK: ![[RANGE7]] = !{i32 1, i32 2, i32 3, i32 4} +; CHECK: ![[RANGE9]] = !{i32 1, i32 5} !0 = !{i32 0, i32 2} !1 = !{i32 3, i32 5} -- 2.7.4