This is an archive of the discontinued LLVM Phabricator instance.

Differential D136095

[GVN] Patch for invalid GVN replacement
ClosedPublic

Authored by alexgatea on Oct 17 2022, 10:25 AM.

Details

Reviewers
fhahn
arsenm
nikic
nlopes
spatel
Commits
rG7d0648cb6c5f: [GVN] Patch for invalid GVN replacement
Summary

The way in which GVNPass is currently replacing uses of the instruction being processed with a value already computed is incorrect because it's not considering the possibility that both the replacement and the use are in the same block with the replacement coming after the use. This happens for example when both the blocks we branch to contain identical shl values, as in the LIT test provided. Prior to this patch, this test case results in an invalid dominator tree.

More details in the issue https://github.com/llvm/llvm-project/issues/58418

Diff Detail

Event Timeline

alexgatea created this revision.Oct 17 2022, 10:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 17 2022, 10:25 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
alexgatea requested review of this revision.Oct 17 2022, 10:25 AM
Herald added a subscriber: llvm-commits. · View Herald TranscriptOct 17 2022, 10:25 AM
alexgatea added reviewers: fhahn, arsenm.Oct 17 2022, 10:27 AM
Herald added a subscriber: wdng. · View Herald TranscriptOct 17 2022, 10:27 AM
alexgatea updated this revision to Diff 468252.Oct 17 2022, 10:31 AM
alexgatea edited the summary of this revision. (Show Details)Oct 17 2022, 10:57 AM
nikic added a subscriber: nikic.Oct 17 2022, 10:57 AM

Please upload the patch with full context (-U99999). It would also be helpful to provide some more information on the issue, like which uses are being replaced by what instruction and why does GVN try to do that.

alexgatea updated this revision to Diff 468263.EditedOct 17 2022, 11:14 AM

Changed to full context differential and provided more information in the description

alexgatea edited the summary of this revision. (Show Details)Oct 17 2022, 11:25 AM
Harbormaster completed remote builds in B192541: Diff 468263.Oct 17 2022, 12:21 PM
alexgatea updated this revision to Diff 470213.Oct 24 2022, 10:35 AM
nikic added a reviewer: nikic.Oct 24 2022, 10:40 AM
Harbormaster completed remote builds in B193982: Diff 470213.Oct 24 2022, 12:40 PM
alexgatea added a comment.EditedOct 24 2022, 1:20 PM

Fyi the build fails due to clang-format, but I checked locally and the improperly formatted lines are not related to my patch

alexgatea added reviewers: nlopes, spatel.Oct 28 2022, 6:14 AM
nikic added a comment.EditedOct 28 2022, 7:42 AM

Haven't looked into this deeply yet, but here is a reduced test case:

declare void @use(i32)

define void @test1(i1 %c, i32 %arg) {
  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
}

Probably the presence of irreducible control-flow is the important bit.

Edit: For reference, this is the output we currently get with disabled verifier:

declare void @use(i32)

define void @test1(i1 %c, i32 %arg) {
  br i1 %c, label %bb1, label %bb2

bb1:                                              ; preds = %0
  %shl1 = shl i32 %arg, 2
  br label %bb3

bb2:                                              ; preds = %bb3, %0
  call void @use(i32 %.pre)
  %.pre = shl i32 %arg, 2
  br label %bb3

bb3:                                              ; preds = %bb2, %bb1
  %shl3.pre-phi = phi i32 [ %.pre, %bb2 ], [ %shl1, %bb1 ]
  %gep = getelementptr i32, ptr null, i32 %shl3.pre-phi
  %v = load i32, ptr %gep, align 4
  call void @use(i32 %v)
  br label %bb2
}
alexgatea updated this revision to Diff 471559.EditedOct 28 2022, 8:16 AM
alexgatea edited the summary of this revision. (Show Details)

Updated LIT test to the suggested reduced test case.

nikic added a comment.Oct 28 2022, 8:27 AM

Here is my current understanding of the issue: For loads of GEPs, we try to perform scalar PRE during the main GVN pass, while for everything else it is done afterwards, see: https://github.com/llvm/llvm-project/blob/524c640090a8463305acbafd7606f1db3c1256e2/llvm/lib/Transforms/Scalar/GVN.cpp#L1777-L1783

Scalar PRE will insert the new instruction into the leader table for the predecessor here: https://github.com/llvm/llvm-project/blob/524c640090a8463305acbafd7606f1db3c1256e2/llvm/lib/Transforms/Scalar/GVN.cpp#L2768-L2769

In this example, we process the blocks in the order entry, bb1, bb3, bb2. When we process bb2, we add the PRE'd instruction to the leader table of bb2, so when we visit bb2, it thinks that the instruction is already available.

I don't think that the fix implemented here is the right one -- I think we need to either prevent PRE from happening in this case, or prevent the incorrect insertion into the leader table, or something along those lines.

nikic added a comment.Oct 28 2022, 8:45 AM

Two more notes:

I think this is the correct way to fix the issue. This will prevent PRE across backedges in all cases, and avoid inserting incorrect values into the leader table.

Harbormaster completed remote builds in B194947: Diff 471559.Oct 28 2022, 9:46 AM
alexgatea updated this revision to Diff 471583.Oct 28 2022, 9:47 AM
alexgatea edited the summary of this revision. (Show Details)

Updated the patch with the suggested fix, and updated my LIT test as well as the LIT test from the previous patch. I agree that this is a better approach than my initial try.

Harbormaster completed remote builds in B194964: Diff 471583.Oct 28 2022, 10:26 AM
nikic accepted this revision.Oct 31 2022, 8:28 AM

LGTM

llvm/test/Transforms/GVN/PRE/load-pre-identical-branches.ll
1 ↗(On Diff #471583)

I'd rename this to load-pre-across-backedge.ll or something, I don't think this has much to do with "identical branches".

This revision is now accepted and ready to land.Oct 31 2022, 8:28 AM
alexgatea added a comment.Oct 31 2022, 8:59 AM

@nikic Thanks for approving! Since this is my first approved patch, I don't think I have commit access. So can you please push it for me (or let me know if I'm wrong)?

alexgatea updated this revision to Diff 472036.Oct 31 2022, 9:01 AM

Updated test name

Harbormaster completed remote builds in B195284: Diff 472036.Oct 31 2022, 10:06 AM
nikic added a comment.Nov 1 2022, 1:29 AM

@alexgatea Can you please share Name <email> to use for the commit?

alexgatea added a comment.Nov 1 2022, 6:05 AM
In D136095#3898515, @nikic wrote:

@alexgatea Can you please share Name <email> to use for the commit?

@nikic Sure: Alex Gatea <alexgatea@gmail.com>

alexgatea added a comment.Nov 4 2022, 6:07 AM

@nikic I'm just wondering if you had a chance to push my commit through

Closed by commit rG7d0648cb6c5f: [GVN] Patch for invalid GVN replacement (authored by alexgatea, committed by nikic). · Explain WhyNov 4 2022, 6:30 AM
This revision was automatically updated to reflect the committed changes.
nikic added a commit: rG7d0648cb6c5f: [GVN] Patch for invalid GVN replacement.

Revision Contents

PathSize
llvm/
lib/
Transforms/
Scalar/
11 lines
test/
Transforms/
GVN/
PRE/
45 lines
7 lines

Diff 473215

llvm/lib/Transforms/Scalar/GVN.cpp

Show First 20 Lines • Show All 2,822 Lines • ▼ Show 20 Linesbool GVNPass::performScalarPRE(Instruction *CurInst) {
SmallVector<std::pair<Value *, BasicBlock *>, 8> predMap; SmallVector<std::pair<Value *, BasicBlock *>, 8> predMap;
for (BasicBlock *P : predecessors(CurrentBlock)) { for (BasicBlock *P : predecessors(CurrentBlock)) {
// We're not interested in PRE where blocks with predecessors that are // We're not interested in PRE where blocks with predecessors that are
// not reachable. // not reachable.
if (!DT->isReachableFromEntry(P)) { if (!DT->isReachableFromEntry(P)) {
NumWithout = 2; NumWithout = 2;
break; break;
} }
// It is not safe to do PRE when P->CurrentBlock is a loop backedge, and // It is not safe to do PRE when P->CurrentBlock is a loop backedge.
// when CurInst has operand defined in CurrentBlock (so it may be defined
// by phi in the loop header).
assert(BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock) && assert(BlockRPONumber.count(P) && BlockRPONumber.count(CurrentBlock) &&
"Invalid BlockRPONumber map."); "Invalid BlockRPONumber map.");
if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock] && if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock]) {
llvm::any_of(CurInst->operands(), [&](const Use &U) {
if (auto *Inst = dyn_cast<Instruction>(U.get()))
return Inst->getParent() == CurrentBlock;
return false;
})) {
NumWithout = 2; NumWithout = 2;
break; break;
} }
uint32_t TValNo = VN.phiTranslate(P, CurrentBlock, ValNo, *this); uint32_t TValNo = VN.phiTranslate(P, CurrentBlock, ValNo, *this);
Value *predV = findLeader(P, TValNo); Value *predV = findLeader(P, TValNo);
if (!predV) { if (!predV) {
predMap.push_back(std::make_pair(static_cast<Value *>(nullptr), P)); predMap.push_back(std::make_pair(static_cast<Value *>(nullptr), P));
▲ Show 20 Lines • Show All 403 Lines • Show Last 20 Lines

llvm/test/Transforms/GVN/PRE/load-pre-across-backedge.ll

  • This file was added.
; 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
}

llvm/test/Transforms/GVN/PRE/pre-gep-load.ll

Show First 20 Lines • Show All 89 Lines • ▼ Show 20 Lines
; The load causes the GEP's operands to be PREd earlier than normal. The ; The load causes the GEP's operands to be PREd earlier than normal. The
; resulting sext ends up in pre.dest and in the GVN system before that BB is ; resulting sext ends up in pre.dest and in the GVN system before that BB is
; actually processed. Make sure we can deal with the situation. ; actually processed. Make sure we can deal with the situation.
define void @test_shortcut_safe(i1 %tst, i32 %p1, i32* %a) { define void @test_shortcut_safe(i1 %tst, i32 %p1, i32* %a) {
; CHECK-LABEL: @test_shortcut_safe( ; CHECK-LABEL: @test_shortcut_safe(
; CHECK-NEXT: br i1 [[TST:%.*]], label [[SEXT1:%.*]], label [[PRE_DEST:%.*]] ; CHECK-NEXT: br i1 [[TST:%.*]], label [[SEXT1:%.*]], label [[PRE_DEST:%.*]]
; CHECK: pre.dest: ; CHECK: pre.dest:
; CHECK-NEXT: [[DOTPRE:%.*]] = sext i32 [[P1:%.*]] to i64
; CHECK-NEXT: br label [[SEXT_USE:%.*]] ; CHECK-NEXT: br label [[SEXT_USE:%.*]]
; CHECK: sext1: ; 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-NEXT: br label [[SEXT_USE]]
; CHECK: sext.use: ; CHECK: sext.use:
; CHECK-NEXT: [[IDXPROM2_PRE_PHI:%.*]] = phi i64 [ [[IDXPROM]], [[SEXT1]] ], [ [[DOTPRE]], [[PRE_DEST]] ] ; CHECK-NEXT: [[IDXPROM2:%.*]] = sext i32 [[P1]] to i64
; CHECK-NEXT: [[ARRAYIDX3:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[IDXPROM2_PRE_PHI]] ; CHECK-NEXT: [[ARRAYIDX3:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[IDXPROM2]]
; CHECK-NEXT: [[VAL:%.*]] = load i32, i32* [[ARRAYIDX3]], align 4 ; CHECK-NEXT: [[VAL:%.*]] = load i32, i32* [[ARRAYIDX3]], align 4
; CHECK-NEXT: tail call void @g(i32 [[VAL]]) ; CHECK-NEXT: tail call void @g(i32 [[VAL]])
; CHECK-NEXT: br label [[PRE_DEST]] ; CHECK-NEXT: br label [[PRE_DEST]]
; ;
br i1 %tst, label %sext1, label %pre.dest br i1 %tst, label %sext1, label %pre.dest
pre.dest: pre.dest:
Show All 15 Lines