From 7d0648cb6c5f3c7377662a1211846f9fe03c474f Mon Sep 17 00:00:00 2001 From: Alex Gatea Date: Fri, 4 Nov 2022 14:28:17 +0100 Subject: [PATCH] [GVN] Patch for invalid GVN replacement If PRE is performed as part of the main GVN pass (to PRE GEP operands before processing loads), and it is performed across a backedge, we will end up adding the new instruction to the leader table of a block that has not yet been processed. When it will be processed, GVN will incorrectly assume that the value is already available, even though it is only available at the end of the block. Avoid this by not performing PRE across backedges. Fixes https://github.com/llvm/llvm-project/issues/58418. Differential Revision: https://reviews.llvm.org/D136095 --- llvm/lib/Transforms/Scalar/GVN.cpp | 11 +----- .../Transforms/GVN/PRE/load-pre-across-backedge.ll | 45 ++++++++++++++++++++++ llvm/test/Transforms/GVN/PRE/pre-gep-load.ll | 7 ++-- 3 files changed, 50 insertions(+), 13 deletions(-) create mode 100644 llvm/test/Transforms/GVN/PRE/load-pre-across-backedge.ll diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp index a489a89..1bc5123 100644 --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -2828,17 +2828,10 @@ bool GVNPass::performScalarPRE(Instruction *CurInst) { NumWithout = 2; break; } - // It is not safe to do PRE when P->CurrentBlock is a loop backedge, and - // when CurInst has operand defined in CurrentBlock (so it may be defined - // by phi in the loop header). + // It is not safe to do PRE when P->CurrentBlock is a loop backedge. assert(BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock) && "Invalid BlockRPONumber map."); - if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock] && - llvm::any_of(CurInst->operands(), [&](const Use &U) { - if (auto *Inst = dyn_cast(U.get())) - return Inst->getParent() == CurrentBlock; - return false; - })) { + if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock]) { NumWithout = 2; break; } diff --git a/llvm/test/Transforms/GVN/PRE/load-pre-across-backedge.ll b/llvm/test/Transforms/GVN/PRE/load-pre-across-backedge.ll new file mode 100644 index 0000000..fe7ceed --- /dev/null +++ b/llvm/test/Transforms/GVN/PRE/load-pre-across-backedge.ll @@ -0,0 +1,45 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -gvn -S < %s | FileCheck %s + +; Check that PRE-LOAD across backedge does not +; result in invalid dominator tree. +declare void @use(i32) + +define void @test1(i1 %c, i32 %arg) { +; CHECK-LABEL: @test1( +; CHECK-NEXT: br i1 [[C:%.*]], label [[BB1:%.*]], label [[DOTBB2_CRIT_EDGE:%.*]] +; CHECK: .bb2_crit_edge: +; CHECK-NEXT: [[DOTPRE:%.*]] = shl i32 [[ARG:%.*]], 2 +; CHECK-NEXT: br label [[BB2:%.*]] +; CHECK: bb1: +; CHECK-NEXT: [[SHL1:%.*]] = shl i32 [[ARG]], 2 +; CHECK-NEXT: br label [[BB3:%.*]] +; CHECK: bb2: +; CHECK-NEXT: [[SHL2_PRE_PHI:%.*]] = phi i32 [ [[DOTPRE]], [[DOTBB2_CRIT_EDGE]] ], [ [[SHL3:%.*]], [[BB3]] ] +; CHECK-NEXT: call void @use(i32 [[SHL2_PRE_PHI]]) +; CHECK-NEXT: br label [[BB3]] +; CHECK: bb3: +; CHECK-NEXT: [[SHL3]] = shl i32 [[ARG]], 2 +; CHECK-NEXT: [[GEP:%.*]] = getelementptr i32, ptr null, i32 [[SHL3]] +; CHECK-NEXT: [[V:%.*]] = load i32, ptr [[GEP]], align 4 +; CHECK-NEXT: call void @use(i32 [[V]]) +; CHECK-NEXT: br label [[BB2]] +; + br i1 %c, label %bb1, label %bb2 + +bb1: + %shl1 = shl i32 %arg, 2 + br label %bb3 + +bb2: + %shl2 = shl i32 %arg, 2 + call void @use(i32 %shl2) + br label %bb3 + +bb3: + %shl3 = shl i32 %arg, 2 + %gep = getelementptr i32, ptr null, i32 %shl3 + %v = load i32, ptr %gep, align 4 + call void @use(i32 %v) + br label %bb2 +} diff --git a/llvm/test/Transforms/GVN/PRE/pre-gep-load.ll b/llvm/test/Transforms/GVN/PRE/pre-gep-load.ll index ed3ac43..e40e6ff 100644 --- a/llvm/test/Transforms/GVN/PRE/pre-gep-load.ll +++ b/llvm/test/Transforms/GVN/PRE/pre-gep-load.ll @@ -95,14 +95,13 @@ define void @test_shortcut_safe(i1 %tst, i32 %p1, i32* %a) { ; CHECK-LABEL: @test_shortcut_safe( ; CHECK-NEXT: br i1 [[TST:%.*]], label [[SEXT1:%.*]], label [[PRE_DEST:%.*]] ; CHECK: pre.dest: -; CHECK-NEXT: [[DOTPRE:%.*]] = sext i32 [[P1:%.*]] to i64 ; CHECK-NEXT: br label [[SEXT_USE:%.*]] ; CHECK: sext1: -; CHECK-NEXT: [[IDXPROM:%.*]] = sext i32 [[P1]] to i64 +; CHECK-NEXT: [[IDXPROM:%.*]] = sext i32 [[P1:%.*]] to i64 ; CHECK-NEXT: br label [[SEXT_USE]] ; CHECK: sext.use: -; CHECK-NEXT: [[IDXPROM2_PRE_PHI:%.*]] = phi i64 [ [[IDXPROM]], [[SEXT1]] ], [ [[DOTPRE]], [[PRE_DEST]] ] -; CHECK-NEXT: [[ARRAYIDX3:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[IDXPROM2_PRE_PHI]] +; CHECK-NEXT: [[IDXPROM2:%.*]] = sext i32 [[P1]] to i64 +; CHECK-NEXT: [[ARRAYIDX3:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[IDXPROM2]] ; CHECK-NEXT: [[VAL:%.*]] = load i32, i32* [[ARRAYIDX3]], align 4 ; CHECK-NEXT: tail call void @g(i32 [[VAL]]) ; CHECK-NEXT: br label [[PRE_DEST]] -- 2.7.4