diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -845,6 +845,17 @@ return false; } +/// Assuming To can be reached from both From and Between, does Between lie on +/// every path from From to To? +static bool liesBetween(const Instruction *From, Instruction *Between, + const Instruction *To, DominatorTree *DT) { + if (From->getParent() == Between->getParent()) + return DT->dominates(From, Between); + SmallSet Exclusion; + Exclusion.insert(Between->getParent()); + return !isPotentiallyReachable(From, To, &Exclusion, DT); +} + /// Try to locate the three instruction involved in a missed /// load-elimination case that is due to an intervening store. static void reportMayClobberedLoad(LoadInst *LI, MemDepResult DepInfo, @@ -861,15 +872,41 @@ for (auto *U : LI->getPointerOperand()->users()) if (U != LI && (isa(U) || isa(U)) && DT->dominates(cast(U), LI)) { - // FIXME: for now give up if there are multiple memory accesses that - // dominate the load. We need further analysis to decide which one is - // that we're forwarding from. - if (OtherAccess) - OtherAccess = nullptr; - else + // Use the most immediately dominating value + if (OtherAccess) { + if (DT->dominates(cast(OtherAccess), cast(U))) + OtherAccess = U; + else + assert(DT->dominates(cast(U), + cast(OtherAccess))); + } else OtherAccess = U; } + if (!OtherAccess) { + // There is no dominating use, check if we can find a closest non-dominating + // use that lies between any other potentially available use and LI. + for (auto *U : LI->getPointerOperand()->users()) { + if (U != LI && (isa(U) || isa(U)) && + isPotentiallyReachable(cast(U), LI, nullptr, DT)) { + if (OtherAccess) { + if (liesBetween(cast(OtherAccess), cast(U), + LI, DT)) { + OtherAccess = U; + } else if (!liesBetween(cast(U), + cast(OtherAccess), LI, DT)) { + // These uses are both partially available at LI were it not for the + // clobber, but neither lies strictly after the other. + OtherAccess = nullptr; + break; + } // else: keep current OtherAccess since it lies between U and LI + } else { + OtherAccess = U; + } + } + } + } + if (OtherAccess) R << " in favor of " << NV("OtherAccess", OtherAccess); diff --git a/llvm/test/Transforms/GVN/opt-remarks-multiple-users.ll b/llvm/test/Transforms/GVN/opt-remarks-multiple-users.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/GVN/opt-remarks-multiple-users.ll @@ -0,0 +1,54 @@ +; RUN: opt < %s -gvn -o /dev/null -pass-remarks-output=%t -S +; RUN: cat %t | FileCheck %s + +; CHECK: --- !Missed +; CHECK-NEXT: Pass: gvn +; CHECK-NEXT: Name: LoadClobbered +; CHECK-NEXT: Function: multipleUsers +; CHECK-NEXT: Args: +; CHECK-NEXT: - String: 'load of type ' +; CHECK-NEXT: - Type: i32 +; CHECK-NEXT: - String: ' not eliminated' +; CHECK-NEXT: - String: ' in favor of ' +; CHECK-NEXT: - OtherAccess: store +; CHECK-NEXT: - String: ' because it is clobbered by ' +; CHECK-NEXT: - ClobberedBy: call +; CHECK-NEXT: ... +; CHECK: --- !Missed +; CHECK-NEXT: Pass: gvn +; CHECK-NEXT: Name: LoadClobbered +; CHECK-NEXT: Function: multipleUsers +; CHECK-NEXT: Args: +; CHECK-NEXT: - String: 'load of type ' +; CHECK-NEXT: - Type: i32 +; CHECK-NEXT: - String: ' not eliminated' +; CHECK-NEXT: - String: ' in favor of ' +; CHECK-NEXT: - OtherAccess: load +; CHECK-NEXT: - String: ' because it is clobbered by ' +; CHECK-NEXT: - ClobberedBy: call +; CHECK-NEXT: ... + +; ModuleID = 'bugpoint-reduced-simplified.bc' +source_filename = "gvn-test.c" +target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define dso_local void @multipleUsers(i32* %a, i32 %b) local_unnamed_addr #0 { +entry: + store i32 %b, i32* %a, align 4 + tail call void @clobberingFunc() #1 + %0 = load i32, i32* %a, align 4 + tail call void @clobberingFunc() #1 + %1 = load i32, i32* %a, align 4 + %add2 = add nsw i32 %1, %0 + unreachable +} + +declare dso_local void @clobberingFunc() local_unnamed_addr #0 + +attributes #0 = { "use-soft-float"="false" } +attributes #1 = { nounwind } + +!llvm.ident = !{!0} + +!0 = !{!"clang version 10.0.0 (git@github.com:llvm/llvm-project.git a2f6ae9abffcba260c22bb235879f0576bf3b783)"} diff --git a/llvm/test/Transforms/GVN/opt-remarks-non-dominating.ll b/llvm/test/Transforms/GVN/opt-remarks-non-dominating.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/GVN/opt-remarks-non-dominating.ll @@ -0,0 +1,123 @@ +; RUN: opt < %s -gvn -o /dev/null -pass-remarks-output=%t -S +; RUN: cat %t | FileCheck %s + +; CHECK: --- !Missed +; CHECK-NEXT: Pass: gvn +; CHECK-NEXT: Name: LoadClobbered +; CHECK-NEXT: Function: multipleUsers1 +; CHECK-NEXT: Args: +; CHECK-NEXT: - String: 'load of type ' +; CHECK-NEXT: - Type: i32 +; CHECK-NEXT: - String: ' not eliminated' +; CHECK-NEXT: - String: ' in favor of ' +; CHECK-NEXT: - OtherAccess: store +; CHECK-NEXT: - String: ' because it is clobbered by ' +; CHECK-NEXT: - ClobberedBy: call +; CHECK-NEXT: ... +; CHECK: --- !Missed +; CHECK-NEXT: Pass: gvn +; CHECK-NEXT: Name: LoadClobbered +; CHECK-NEXT: Function: multipleUsers2 +; CHECK-NEXT: Args: +; CHECK-NEXT: - String: 'load of type ' +; CHECK-NEXT: - Type: i32 +; CHECK-NEXT: - String: ' not eliminated' +; CHECK-NEXT: - String: ' in favor of ' +; CHECK-NEXT: - OtherAccess: load +; CHECK-NEXT: - String: ' because it is clobbered by ' +; CHECK-NEXT: - ClobberedBy: call +; CHECK-NEXT: ... +; CHECK: --- !Missed +; CHECK-NEXT: Pass: gvn +; CHECK-NEXT: Name: LoadClobbered +; CHECK-NEXT: Function: multipleUsers2 +; CHECK-NEXT: Args: +; CHECK-NEXT: - String: 'load of type ' +; CHECK-NEXT: - Type: i32 +; CHECK-NEXT: - String: ' not eliminated' +; CHECK-NEXT: - String: ' in favor of ' +; CHECK-NEXT: - OtherAccess: load +; CHECK-NEXT: - String: ' because it is clobbered by ' +; CHECK-NEXT: - ClobberedBy: call +; CHECK-NEXT: ... +; CHECK: --- !Missed +; CHECK-NEXT: Pass: gvn +; CHECK-NEXT: Name: LoadClobbered +; CHECK-NEXT: Function: multipleUsers3 +; CHECK-NEXT: Args: +; CHECK-NEXT: - String: 'load of type ' +; CHECK-NEXT: - Type: i32 +; CHECK-NEXT: - String: ' not eliminated' +; CHECK-NEXT: - String: ' because it is clobbered by ' +; CHECK-NEXT: - ClobberedBy: call +; CHECK-NEXT: ... + + +; ModuleID = 'bugpoint-reduced-simplified.bc' +source_filename = "gvn-test.c" +target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +define dso_local void @multipleUsers1(i32* %a) local_unnamed_addr #0 { +entry: + br i1 undef, label %if.then, label %if.end + +if.then: ; preds = %entry + store i32 undef, i32* %a, align 4 + br label %if.end + +if.end: ; preds = %if.then, %entry + tail call void @clobberingFunc() #1 + %0 = load i32, i32* %a, align 4 + %mul2 = shl nsw i32 %0, 1 + store i32 %mul2, i32* %a, align 4 + ret void +} + +declare dso_local void @clobberingFunc() local_unnamed_addr #0 + +define dso_local void @multipleUsers2(i32* %a) local_unnamed_addr #0 { +entry: + br i1 undef, label %if.then, label %if.end5 + +if.then: ; preds = %entry + %0 = load i32, i32* %a, align 4 + %mul = mul nsw i32 %0, 10 + tail call void @clobberingFunc() #1 + %1 = load i32, i32* %a, align 4 + %mul3 = mul nsw i32 %1, 5 + tail call void @clobberingFunc() #1 + br label %if.end5 + +if.end5: ; preds = %if.then, %entry + %2 = load i32, i32* %a, align 4 + %mul9 = shl nsw i32 %2, 1 + store i32 %mul9, i32* %a, align 4 + ret void +} + +define dso_local void @multipleUsers3(i32* %a) local_unnamed_addr #0 { +entry: + br i1 undef, label %if.end5.sink.split, label %if.else + +if.else: ; preds = %entry + store i32 undef, i32* %a, align 4 + br label %if.end5 + +if.end5.sink.split: ; preds = %entry + store i32 undef, i32* %a, align 4 + br label %if.end5 + +if.end5: ; preds = %if.end5.sink.split, %if.else + tail call void @clobberingFunc() #1 + %0 = load i32, i32* %a, align 4 + %mul7 = shl nsw i32 %0, 1 + ret void +} + +attributes #0 = { "use-soft-float"="false" } +attributes #1 = { nounwind } + +!llvm.ident = !{!0} + +!0 = !{!"clang version 11.0.0 (git@github.com:hnrklssn/thesis-llvm.git 05da7f0ea394d3994834bb5e387a191388691fc2)"}