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, @@ -858,17 +869,45 @@ R << "load of type " << NV("Type", LI->getType()) << " not eliminated" << setExtraArgs(); - for (auto *U : LI->getPointerOperand()->users()) - if (U != LI && (isa(U) || isa(U)) && + for (auto *U : LI->getPointerOperand()->users()) { + if (U != LI && (isa(U) || isa(U)) && cast(U)->getFunction() == LI->getFunction() && 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)) && + cast(U)->getFunction() == LI->getFunction() && + 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,106 @@ +; 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: ... +; 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: 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: ... + +; 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" + +; Tests that a last clobbering use can be determined even in the presence of +; multiple users, given that one of them lies on a path between every other +; potentially clobbering use and the load. + +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 + ret void +} + +; Ignore uses in other functions + +define dso_local void @multipleUsers2(i32 %b) local_unnamed_addr #0 { +entry: + store i32 %b, i32* @g, align 4 + tail call void @clobberingFunc() #1 + %0 = load i32, i32* @g, align 4 + tail call void @clobberingFunc() #1 + %1 = load i32, i32* @g, align 4 + %add3 = add nsw i32 %1, %0 + ret void +} + +declare dso_local void @clobberingFunc() local_unnamed_addr #0 + +@g = external global i32 + +define dso_local void @globalUser(i32 %b) local_unnamed_addr #0 { +entry: + store i32 %b, i32* @g, align 4 + ret void +} + + +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,176 @@ +; 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: nonDominating1 +; 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: nonDominating2 +; 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: nonDominating2 +; 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: nonDominating3 +; 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: ... +; CHECK: --- !Missed +; CHECK-NEXT: Pass: gvn +; CHECK-NEXT: Name: LoadClobbered +; CHECK-NEXT: Function: nonDominating4 +; 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: ... + + +; 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" + +; Confirm that the partial redundancy being clobbered by the call to +; clobberingFunc() between store and load is identified. + +define dso_local void @nonDominating1(i32* %a, i1 %cond, i32 %b) local_unnamed_addr #0 { +entry: + br i1 %cond, label %if.then, label %if.end + +if.then: ; preds = %entry + store i32 %b, 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 + +; More complex version of nonDominating1(), this time with loads. The values +; already loaded into %0 and %1 cannot replace %2 due to clobbering calls. +; %1 is not clobbered by the first call however, and %0 is irrelevant for the +; second one since %1 is more recently available. + +define dso_local void @nonDominating2(i32* %a, i1 %cond) local_unnamed_addr #0 { +entry: + br i1 %cond, 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 +} + +; The two stores are both partially available at %0 (were it not for the +; clobbering call), however neither is strictly more recent than the other, so +; no attempt is made to identify what value could have potentially been reused +; otherwise. Just report that the load cannot be eliminated. + +define dso_local void @nonDominating3(i32* %a, i32 %b, i32 %c, i1 %cond) local_unnamed_addr #0 { +entry: + br i1 %cond, label %if.end5.sink.split, label %if.else + +if.else: ; preds = %entry + store i32 %b, i32* %a, align 4 + br label %if.end5 + +if.end5.sink.split: ; preds = %entry + store i32 %c, 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 +} + +; Make sure isPotentiallyReachable() is not called for an instruction +; outside the current function, as it will cause a crash. + +define dso_local void @nonDominating4(i1 %cond, i32 %b) local_unnamed_addr #0 { +entry: + br i1 %cond, label %if.then, label %if.end + +if.then: ; preds = %entry + store i32 %b, i32* @g, align 4 + br label %if.end + +if.end: ; preds = %if.then, %entry + tail call void @clobberingFunc() #1 + %0 = load i32, i32* @g, align 4 + %mul2 = shl nsw i32 %0, 1 + store i32 %mul2, i32* @g, align 4 + ret void +} + +@g = external global i32 + +define dso_local void @globalUser(i32 %b) local_unnamed_addr #0 { +entry: + store i32 %b, i32* @g, align 4 + 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)"}