From 24a49e99f386432fc6fa46faf6e2ba91cfaed2df Mon Sep 17 00:00:00 2001 From: Nuno Lopes Date: Wed, 26 Jan 2022 10:10:22 +0000 Subject: [PATCH] [NewGVN] FIx phi-of-ops in the presence of memory read operations The phi-of-ops functionality has a function OpIsSafeForPHIOfOps to determine when it's safe to create the new phi. But this function only checks for the obvious dominator conditions and ignores memory. This patch takes the conservative approach and disables phi-of-ops whenever there's a load that doesn't dominate the phi, as its value may be affected by a store inside the loop. This can be improved later to check aliasing between the load/stores. Fixes https://llvm.org/PR53277 Reviewed By: asbirlea Differential Revision: https://reviews.llvm.org/D117999 --- llvm/lib/Transforms/Scalar/NewGVN.cpp | 9 ++++ llvm/test/Transforms/NewGVN/phi-of-ops-loads.ll | 70 +++++++++++++++++++------ llvm/test/Transforms/NewGVN/storeoverstore.ll | 33 +++++++----- 3 files changed, 85 insertions(+), 27 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/NewGVN.cpp b/llvm/lib/Transforms/Scalar/NewGVN.cpp index 6890ad38..2476e6c4 100644 --- a/llvm/lib/Transforms/Scalar/NewGVN.cpp +++ b/llvm/lib/Transforms/Scalar/NewGVN.cpp @@ -2587,6 +2587,15 @@ bool NewGVN::OpIsSafeForPHIOfOpsHelper( } auto *OrigI = cast(V); + // When we hit an instruction that reads memory (load, call, etc), we must + // consider any store that may happen in the loop. For now, we assume the + // worst: there is a store in the loop that alias with this read. + // The case where the load is outside the loop is already covered by the + // dominator check above. + // TODO: relax this condition + if (OrigI->mayReadFromMemory()) + return false; + for (auto *Op : OrigI->operand_values()) { if (!isa(Op)) continue; diff --git a/llvm/test/Transforms/NewGVN/phi-of-ops-loads.ll b/llvm/test/Transforms/NewGVN/phi-of-ops-loads.ll index 63a16d6..335b3b0 100644 --- a/llvm/test/Transforms/NewGVN/phi-of-ops-loads.ll +++ b/llvm/test/Transforms/NewGVN/phi-of-ops-loads.ll @@ -1,15 +1,15 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -passes=newgvn -enable-phi-of-ops=true -S -o - %s | FileCheck %s -define void @store-in-loop(i8* %p, i8* %q) { -; CHECK-LABEL: @store-in-loop( +define void @hoisted-load(i8* %p, i8* %q) { +; CHECK-LABEL: @hoisted-load( ; CHECK-NEXT: bb56: +; CHECK-NEXT: [[N60:%.*]] = load i8, i8* [[P:%.*]], align 1 ; CHECK-NEXT: br label [[BB57:%.*]] ; CHECK: bb57: ; CHECK-NEXT: [[PHIOFOPS:%.*]] = phi i1 [ true, [[BB56:%.*]] ], [ [[N62:%.*]], [[BB229:%.*]] ] ; CHECK-NEXT: [[N59:%.*]] = phi i1 [ false, [[BB229]] ], [ true, [[BB56]] ] ; CHECK-NEXT: [[IDX:%.*]] = phi i8 [ 0, [[BB56]] ], [ [[INC:%.*]], [[BB229]] ] -; CHECK-NEXT: [[N60:%.*]] = load i8, i8* [[P:%.*]], align 1 ; CHECK-NEXT: [[N62]] = icmp ne i8 [[N60]], 2 ; CHECK-NEXT: br i1 [[PHIOFOPS]], label [[BB229]], label [[BB237:%.*]] ; CHECK: bb229: @@ -20,6 +20,44 @@ define void @store-in-loop(i8* %p, i8* %q) { ; CHECK-NEXT: ret void ; bb56: + %n60 = load i8, i8* %p + br label %bb57 + +bb57: + %n59 = phi i1 [ false, %bb229 ], [ true, %bb56 ] + %idx = phi i8 [0, %bb56], [%inc, %bb229] + %n62 = icmp ne i8 %n60, 2 + %n63 = or i1 %n59, %n62 + br i1 %n63, label %bb229, label %bb237 + +bb229: + %inc = add i8 %idx, 1 + store i8 %inc, i8* %q + br label %bb57 + +bb237: + ret void +} + +define void @store-in-loop(i8* %p, i8* %q) { +; CHECK-LABEL: @store-in-loop( +; CHECK-NEXT: bb56: +; CHECK-NEXT: br label [[BB57:%.*]] +; CHECK: bb57: +; CHECK-NEXT: [[N59:%.*]] = phi i1 [ false, [[BB229:%.*]] ], [ true, [[BB56:%.*]] ] +; CHECK-NEXT: [[IDX:%.*]] = phi i8 [ 0, [[BB56]] ], [ [[INC:%.*]], [[BB229]] ] +; CHECK-NEXT: [[N60:%.*]] = load i8, i8* [[P:%.*]], align 1 +; CHECK-NEXT: [[N62:%.*]] = icmp ne i8 [[N60]], 2 +; CHECK-NEXT: [[N63:%.*]] = or i1 [[N59]], [[N62]] +; CHECK-NEXT: br i1 [[N63]], label [[BB229]], label [[BB237:%.*]] +; CHECK: bb229: +; CHECK-NEXT: [[INC]] = add i8 [[IDX]], 1 +; CHECK-NEXT: store i8 [[INC]], i8* [[Q:%.*]], align 1 +; CHECK-NEXT: br label [[BB57]] +; CHECK: bb237: +; CHECK-NEXT: ret void +; +bb56: br label %bb57 bb57: @@ -39,17 +77,18 @@ bb237: ret void } +; TODO: we should support this case define void @no-alias-store-in-loop(i8* noalias %p, i8* noalias %q) { ; CHECK-LABEL: @no-alias-store-in-loop( ; CHECK-NEXT: bb56: ; CHECK-NEXT: br label [[BB57:%.*]] ; CHECK: bb57: -; CHECK-NEXT: [[PHIOFOPS:%.*]] = phi i1 [ true, [[BB56:%.*]] ], [ [[N62:%.*]], [[BB229:%.*]] ] -; CHECK-NEXT: [[N59:%.*]] = phi i1 [ false, [[BB229]] ], [ true, [[BB56]] ] +; CHECK-NEXT: [[N59:%.*]] = phi i1 [ false, [[BB229:%.*]] ], [ true, [[BB56:%.*]] ] ; CHECK-NEXT: [[IDX:%.*]] = phi i8 [ 0, [[BB56]] ], [ [[INC:%.*]], [[BB229]] ] ; CHECK-NEXT: [[N60:%.*]] = load i8, i8* [[P:%.*]], align 1 -; CHECK-NEXT: [[N62]] = icmp ne i8 [[N60]], 2 -; CHECK-NEXT: br i1 [[PHIOFOPS]], label [[BB229]], label [[BB237:%.*]] +; CHECK-NEXT: [[N62:%.*]] = icmp ne i8 [[N60]], 2 +; CHECK-NEXT: [[N63:%.*]] = or i1 [[N59]], [[N62]] +; CHECK-NEXT: br i1 [[N63]], label [[BB229]], label [[BB237:%.*]] ; CHECK: bb229: ; CHECK-NEXT: [[INC]] = add i8 [[IDX]], 1 ; CHECK-NEXT: store i8 [[INC]], i8* [[Q:%.*]], align 1 @@ -82,11 +121,11 @@ define void @function-in-loop(i8* %p) { ; CHECK-NEXT: bb56: ; CHECK-NEXT: br label [[BB57:%.*]] ; CHECK: bb57: -; CHECK-NEXT: [[PHIOFOPS:%.*]] = phi i1 [ true, [[BB56:%.*]] ], [ [[N62:%.*]], [[BB229:%.*]] ] -; CHECK-NEXT: [[N59:%.*]] = phi i1 [ false, [[BB229]] ], [ true, [[BB56]] ] +; CHECK-NEXT: [[N59:%.*]] = phi i1 [ false, [[BB229:%.*]] ], [ true, [[BB56:%.*]] ] ; CHECK-NEXT: [[N60:%.*]] = load i8, i8* [[P:%.*]], align 1 -; CHECK-NEXT: [[N62]] = icmp ne i8 [[N60]], 2 -; CHECK-NEXT: br i1 [[PHIOFOPS]], label [[BB229]], label [[BB237:%.*]] +; CHECK-NEXT: [[N62:%.*]] = icmp ne i8 [[N60]], 2 +; CHECK-NEXT: [[N63:%.*]] = or i1 [[N59]], [[N62]] +; CHECK-NEXT: br i1 [[N63]], label [[BB229]], label [[BB237:%.*]] ; CHECK: bb229: ; CHECK-NEXT: call void @f() ; CHECK-NEXT: br label [[BB57]] @@ -111,16 +150,17 @@ bb237: ret void } +; TODO: we should support this case define void @nowrite-function-in-loop(i8* %p) { ; CHECK-LABEL: @nowrite-function-in-loop( ; CHECK-NEXT: bb56: ; CHECK-NEXT: br label [[BB57:%.*]] ; CHECK: bb57: -; CHECK-NEXT: [[PHIOFOPS:%.*]] = phi i1 [ true, [[BB56:%.*]] ], [ [[N62:%.*]], [[BB229:%.*]] ] -; CHECK-NEXT: [[N59:%.*]] = phi i1 [ false, [[BB229]] ], [ true, [[BB56]] ] +; CHECK-NEXT: [[N59:%.*]] = phi i1 [ false, [[BB229:%.*]] ], [ true, [[BB56:%.*]] ] ; CHECK-NEXT: [[N60:%.*]] = load i8, i8* [[P:%.*]], align 1 -; CHECK-NEXT: [[N62]] = icmp ne i8 [[N60]], 2 -; CHECK-NEXT: br i1 [[PHIOFOPS]], label [[BB229]], label [[BB237:%.*]] +; CHECK-NEXT: [[N62:%.*]] = icmp ne i8 [[N60]], 2 +; CHECK-NEXT: [[N63:%.*]] = or i1 [[N59]], [[N62]] +; CHECK-NEXT: br i1 [[N63]], label [[BB229]], label [[BB237:%.*]] ; CHECK: bb229: ; CHECK-NEXT: call void @f() #[[ATTR0:[0-9]+]] ; CHECK-NEXT: br label [[BB57]] diff --git a/llvm/test/Transforms/NewGVN/storeoverstore.ll b/llvm/test/Transforms/NewGVN/storeoverstore.ll index 385f187..0e4a4ec 100644 --- a/llvm/test/Transforms/NewGVN/storeoverstore.ll +++ b/llvm/test/Transforms/NewGVN/storeoverstore.ll @@ -12,12 +12,16 @@ define i32 @foo(i32*, i32) { ; CHECK-NEXT: store i32 5, i32* [[TMP0:%.*]], align 4 ; CHECK-NEXT: [[TMP3:%.*]] = icmp ne i32 [[TMP1:%.*]], 0 ; CHECK-NEXT: br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP5:%.*]] -; CHECK: br label [[TMP5]] -; CHECK: [[PHIOFOPS:%.*]] = phi i32 [ 10, [[TMP2:%.*]] ], [ 15, [[TMP4]] ] -; CHECK-NEXT: [[DOT0:%.*]] = phi i32 [ 10, [[TMP4]] ], [ 5, [[TMP2]] ] -; CHECK-NEXT: br i1 [[TMP3]], label [[TMP6:%.*]], label [[TMP7:%.*]] -; CHECK: br label [[TMP7]] -; CHECK: [[DOT1:%.*]] = phi i32 [ [[PHIOFOPS]], [[TMP6]] ], [ [[DOT0]], [[TMP5]] ] +; CHECK: 4: +; CHECK-NEXT: br label [[TMP5]] +; CHECK: 5: +; CHECK-NEXT: [[DOT0:%.*]] = phi i32 [ 10, [[TMP4]] ], [ 5, [[TMP2:%.*]] ] +; CHECK-NEXT: br i1 [[TMP3]], label [[TMP6:%.*]], label [[TMP8:%.*]] +; CHECK: 6: +; CHECK-NEXT: [[TMP7:%.*]] = add nsw i32 [[DOT0]], 5 +; CHECK-NEXT: br label [[TMP8]] +; CHECK: 8: +; CHECK-NEXT: [[DOT1:%.*]] = phi i32 [ [[TMP7]], [[TMP6]] ], [ [[DOT0]], [[TMP5]] ] ; CHECK-NEXT: ret i32 [[DOT1]] ; store i32 5, i32* %0, align 4 @@ -52,13 +56,18 @@ define i32 @foo2(i32*, i32) { ; CHECK-NEXT: store i32 5, i32* [[TMP0:%.*]], align 4 ; CHECK-NEXT: [[TMP3:%.*]] = icmp ne i32 [[TMP1:%.*]], 0 ; CHECK-NEXT: br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP5:%.*]] -; CHECK: br label [[TMP6:%.*]] -; CHECK: br label [[TMP6]] -; CHECK: [[PHIOFOPS:%.*]] = phi i32 [ 10, [[TMP5]] ], [ 15, [[TMP4]] ] +; CHECK: 4: +; CHECK-NEXT: br label [[TMP6:%.*]] +; CHECK: 5: +; CHECK-NEXT: br label [[TMP6]] +; CHECK: 6: ; CHECK-NEXT: [[DOT0:%.*]] = phi i32 [ 10, [[TMP4]] ], [ 5, [[TMP5]] ] -; CHECK-NEXT: br i1 [[TMP3]], label [[TMP7:%.*]], label [[TMP8:%.*]] -; CHECK: br label [[TMP8]] -; CHECK: [[DOT1:%.*]] = phi i32 [ [[PHIOFOPS]], [[TMP7]] ], [ [[DOT0]], [[TMP6]] ] +; CHECK-NEXT: br i1 [[TMP3]], label [[TMP7:%.*]], label [[TMP9:%.*]] +; CHECK: 7: +; CHECK-NEXT: [[TMP8:%.*]] = add nsw i32 [[DOT0]], 5 +; CHECK-NEXT: br label [[TMP9]] +; CHECK: 9: +; CHECK-NEXT: [[DOT1:%.*]] = phi i32 [ [[TMP8]], [[TMP7]] ], [ [[DOT0]], [[TMP6]] ] ; CHECK-NEXT: ret i32 [[DOT1]] ; store i32 5, i32* %0, align 4 -- 2.7.4