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 @@ -931,6 +931,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 *Load, MemDepResult DepInfo, @@ -944,17 +955,46 @@ R << "load of type " << NV("Type", Load->getType()) << " not eliminated" << setExtraArgs(); - for (auto *U : Load->getPointerOperand()->users()) + for (auto *U : Load->getPointerOperand()->users()) { if (U != Load && (isa(U) || isa(U)) && + cast(U)->getFunction() == Load->getFunction() && DT->dominates(cast(U), Load)) { - // 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 Load. + for (auto *U : Load->getPointerOperand()->users()) { + if (U != Load && (isa(U) || isa(U)) && + cast(U)->getFunction() == Load->getFunction() && + isPotentiallyReachable(cast(U), Load, nullptr, DT)) { + if (OtherAccess) { + if (liesBetween(cast(OtherAccess), cast(U), + Load, DT)) { + OtherAccess = U; + } else if (!liesBetween(cast(U), + cast(OtherAccess), Load, DT)) { + // These uses are both partially available at Load 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 Load + } 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,137 @@ +; 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: DebugLoc: { File: '/tmp/s.c', Line: 2, Column: 2 } +; 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: DebugLoc: { File: '/tmp/s.c', Line: 1, Column: 1 } +; CHECK-NEXT: ... +; CHECK: --- !Missed +; CHECK-NEXT: Pass: gvn +; CHECK-NEXT: Name: LoadClobbered +; CHECK-NEXT: DebugLoc: { File: '/tmp/s.c', Line: 4, Column: 4 } +; 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: DebugLoc: { File: '/tmp/s.c', Line: 2, Column: 2 } +; CHECK-NEXT: - String: ' because it is clobbered by ' +; CHECK-NEXT: - ClobberedBy: call +; CHECK-NEXT: DebugLoc: { File: '/tmp/s.c', Line: 3, Column: 3 } +; 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, !dbg !10 + %0 = load i32, i32* %a, align 4, !dbg !11 + tail call void @clobberingFunc() #1, !dbg !12 + %1 = load i32, i32* %a, align 4, !dbg !13 + %add2 = add nsw i32 %1, %0 + ret void +} + +; CHECK: --- !Missed +; CHECK-NEXT: Pass: gvn +; CHECK-NEXT: Name: LoadClobbered +; CHECK-NEXT: DebugLoc: { File: '/tmp/s.c', Line: 2, Column: 2 } +; 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: DebugLoc: { File: '/tmp/s.c', Line: 1, Column: 1 } +; CHECK-NEXT: ... +; CHECK: --- !Missed +; CHECK-NEXT: Pass: gvn +; CHECK-NEXT: Name: LoadClobbered +; CHECK-NEXT: DebugLoc: { File: '/tmp/s.c', Line: 4, Column: 4 } +; 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: DebugLoc: { File: '/tmp/s.c', Line: 2, Column: 2 } +; CHECK-NEXT: - String: ' because it is clobbered by ' +; CHECK-NEXT: - ClobberedBy: call +; CHECK-NEXT: DebugLoc: { File: '/tmp/s.c', Line: 3, Column: 3 } +; CHECK-NEXT: ... + +; 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, !dbg !15 + %0 = load i32, i32* @g, align 4, !dbg !16 + tail call void @clobberingFunc() #1, !dbg !17 + %1 = load i32, i32* @g, align 4, !dbg !18 + %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.dbg.cu = !{!1} +!llvm.module.flags = !{!4, !5, !6} +!llvm.ident = !{!0} + +!0 = !{!"clang version 10.0.0 (git@github.com:llvm/llvm-project.git a2f6ae9abffcba260c22bb235879f0576bf3b783)"} +!1 = distinct !DICompileUnit(language: DW_LANG_C99, file: !2, producer: "clang version 4.0.0 (trunk 282540) (llvm/trunk 282542)", isOptimized: true, runtimeVersion: 0, emissionKind: LineTablesOnly, enums: !3) +!2 = !DIFile(filename: "/tmp/s.c", directory: "/tmp") +!3 = !{} +!4 = !{i32 2, !"Dwarf Version", i32 4} +!5 = !{i32 2, !"Debug Info Version", i32 3} +!6 = !{i32 1, !"PIC Level", i32 2} +!8 = distinct !DISubprogram(name: "multipleUsers", scope: !2, file: !2, line: 1, type: !9, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: true, unit: !1, retainedNodes: !3) +!9 = !DISubroutineType(types: !3) +!10 = !DILocation(line: 1, column: 1, scope: !8) +!11 = !DILocation(line: 2, column: 2, scope: !8) +!12 = !DILocation(line: 3, column: 3, scope: !8) +!13 = !DILocation(line: 4, column: 4, scope: !8) +!14 = distinct !DISubprogram(name: "multipleUsers2", scope: !2, file: !2, line: 2, type: !9, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: true, unit: !1, retainedNodes: !3) +!15 = !DILocation(line: 1, column: 1, scope: !14) +!16 = !DILocation(line: 2, column: 2, scope: !14) +!17 = !DILocation(line: 3, column: 3, scope: !14) +!18 = !DILocation(line: 4, column: 4, scope: !14) + 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,206 @@ +; RUN: opt < %s -gvn -o /dev/null -pass-remarks-output=%t -S +; RUN: cat %t | FileCheck %s + + +; 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" + +; 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: ... + +; 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 + +; CHECK: --- !Missed +; CHECK-NEXT: Pass: gvn +; CHECK-NEXT: Name: LoadClobbered +; CHECK-NEXT: DebugLoc: { File: '/tmp/s.c', Line: 3, Column: 3 } +; 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: DebugLoc: { File: '/tmp/s.c', Line: 1, Column: 1 } +; CHECK-NEXT: - String: ' because it is clobbered by ' +; CHECK-NEXT: - ClobberedBy: call +; CHECK-NEXT: DebugLoc: { File: '/tmp/s.c', Line: 2, Column: 2 } +; CHECK-NEXT: ... +; CHECK: --- !Missed +; CHECK-NEXT: Pass: gvn +; CHECK-NEXT: Name: LoadClobbered +; CHECK-NEXT: DebugLoc: { File: '/tmp/s.c', Line: 5, Column: 5 } +; 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: DebugLoc: { File: '/tmp/s.c', Line: 3, Column: 3 } +; CHECK-NEXT: - String: ' because it is clobbered by ' +; CHECK-NEXT: - ClobberedBy: call +; CHECK-NEXT: DebugLoc: { File: '/tmp/s.c', Line: 4, Column: 4 } +; CHECK-NEXT: ... + +; 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, !dbg !14 + %mul = mul nsw i32 %0, 10 + tail call void @clobberingFunc() #1, !dbg !15 + %1 = load i32, i32* %a, align 4, !dbg !16 + %mul3 = mul nsw i32 %1, 5 + tail call void @clobberingFunc() #1, !dbg !17 + br label %if.end5 + +if.end5: ; preds = %if.then, %entry + %2 = load i32, i32* %a, align 4, !dbg !18 + %mul9 = shl nsw i32 %2, 1 + store i32 %mul9, i32* %a, align 4 + ret void +} + +; 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: ... + +; 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 +} + +; 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: ... + +; 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} +!llvm.dbg.cu = !{!1} +!llvm.module.flags = !{!4, !5, !6} + +!0 = !{!"clang version 10.0.0 (git@github.com:llvm/llvm-project.git a2f6ae9abffcba260c22bb235879f0576bf3b783)"} + +!1 = distinct !DICompileUnit(language: DW_LANG_C99, file: !2, producer: "clang version 4.0.0 (trunk 282540) (llvm/trunk 282542)", isOptimized: true, runtimeVersion: 0, emissionKind: LineTablesOnly, enums: !3) +!2 = !DIFile(filename: "/tmp/s.c", directory: "/tmp") +!3 = !{} +!4 = !{i32 2, !"Dwarf Version", i32 4} +!5 = !{i32 2, !"Debug Info Version", i32 3} +!6 = !{i32 1, !"PIC Level", i32 2} +!8 = distinct !DISubprogram(name: "nonDominating2", scope: !2, file: !2, line: 1, type: !9, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: true, unit: !1, retainedNodes: !3) +!9 = !DISubroutineType(types: !10) +!10 = !{null, !11, !12, !12, !13} +!11 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !12, size: 64) +!12 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed) +!13 = !DIBasicType(name: "_Bool", size: 8, encoding: DW_ATE_boolean) +!14 = !DILocation(line: 1, column: 1, scope: !8) +!15 = !DILocation(line: 2, column: 2, scope: !8) +!16 = !DILocation(line: 3, column: 3, scope: !8) +!17 = !DILocation(line: 4, column: 4, scope: !8) +!18 = !DILocation(line: 5, column: 5, scope: !8) +