[GVN] Patch for invalid GVN replacement

[alexgatea]

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

[nikic]

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]

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

[alexgatea]

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

[nikic]

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 LIT test to the suggested reduced test case.

[nikic]

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]

Two more notes:

• It looks like https://github.com/llvm/llvm-project/commit/d4f55c0b1b878df2aa28f0df382158cb69ed9e74 was a previous attempt to fix a version of this issue.
• https://github.com/llvm/llvm-project/blob/524c640090a8463305acbafd7606f1db3c1256e2/llvm/lib/Transforms/Scalar/GVN.cpp#L2836 detects the PRE across back-edge case. It currently has an additional check on the instruction operands. If we drop that check, then that fixes the test case. The only other test this change affects is the test_shortcut_safe test from the previous point.

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.

[alexgatea]

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.

[nikic]

LGTM

llvm/test/Transforms/GVN/PRE/load-pre-identical-branches.ll

1

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

[alexgatea]

@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 test name

[nikic]

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

[alexgatea]

In D136095#3898515, @nikic wrote:

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

@nikic Sure: Alex Gatea <[e-mail]>

[alexgatea]

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

llvm/lib/Transforms/Scalar/GVN.cpp

bool GVNPass::performScalarPRE(Instruction *CurInst) {
   SmallVector<std::pair<Value *, BasicBlock *>, 8> predMap;
   for (BasicBlock *P : predecessors(CurrentBlock)) {
     // We're not interested in PRE where blocks with predecessors that are
     // not reachable.
     if (!DT->isReachableFromEntry(P)) {
       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<Instruction>(U.get()))
-            return Inst->getParent() == CurrentBlock;
-          return false;
-        })) {
+    if (BlockRPONumber[P] >= BlockRPONumber[CurrentBlock]) {
       NumWithout = 2;
       break;
     }
 
     uint32_t TValNo = VN.phiTranslate(P, CurrentBlock, ValNo, *this);
     Value *predV = findLeader(P, TValNo);
     if (!predV) {
       predMap.push_back(std::make_pair(static_cast<Value *>(nullptr), P));

llvm/test/Transforms/GVN/PRE/load-pre-identical-branches.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -gvn -S < %s | FileCheck %s
+
+; Check that PRE-LOAD with two identical branches 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

 ; 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
 ; actually processed. Make sure we can deal with the situation.
 
 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]]
 ;
 
   br i1 %tst, label %sext1, label %pre.dest
 
 pre.dest: