[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 ↗

(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".

[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

if (impliesEquivalanceIfTrue(CmpI)) {
       // propagateEquality above; this block is just about handling the block
       // local cases.  TODO: There's a bunch of logic in propagateEqualiy which
       // isn't duplicated for the block local case, can we share it somehow?
     }
   }
   return Changed;
 }
 
-static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) {
+static void patchAndReplaceAllUsesWith(DominatorTree *DT, Instruction *I, Value *Repl) {
   patchReplacementInstruction(I, Repl);
-  I->replaceAllUsesWith(Repl);
+  // Replace I with Repl everywhere it does not violate the dominator tree.
+  I->replaceUsesWithIf(Repl, [&Repl,&DT](Use &U) {
+                        return DT->dominates(Repl, U); 
+  });
 }
 
 /// Attempt to eliminate a load, first by eliminating it
 /// locally, and then attempting non-local elimination if that fails.
 bool GVNPass::processLoad(LoadInst *L) {
   if (!MD)
     return false;
 
if (!Dep.isDef() && !Dep.isClobber() && !isa<SelectInst>(Address)) {
     return false;
   }
 
   AvailableValue AV;
   if (AnalyzeLoadAvailability(L, Dep, Address, AV)) {
     Value *AvailableValue = AV.MaterializeAdjustedValue(L, L, *this);
 
     // Replace the load!
-    patchAndReplaceAllUsesWith(L, AvailableValue);
+    patchAndReplaceAllUsesWith(DT, L, AvailableValue);
     markInstructionForDeletion(L);
     if (MSSAU)
       MSSAU->removeMemoryAccess(L);
     ++NumGVNLoad;
     reportLoadElim(L, AvailableValue, ORE);
     // Tell MDA to reexamine the reused pointer since we might have more
     // information after forwarding it.
     if (MD && AvailableValue->getType()->isPtrOrPtrVectorTy())
if (!Repl) {
     return false;
   } else if (Repl == I) {
     // If I was the result of a shortcut PRE, it might already be in the table
     // and the best replacement for itself. Nothing to do.
     return false;
   }
 
   // Remove it!
-  patchAndReplaceAllUsesWith(I, Repl);
+  patchAndReplaceAllUsesWith(DT, I, Repl);
+  if (I->uses().empty()) {
     if (MD && Repl->getType()->isPtrOrPtrVectorTy())
       MD->invalidateCachedPointerInfo(Repl);
     markInstructionForDeletion(I);
+  }
   return true;
 }
 
 /// runOnFunction - This is the main transformation entry point for a function.
 bool GVNPass::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
                       const TargetLibraryInfo &RunTLI, AAResults &RunAA,
                       MemoryDependenceResults *RunMD, LoopInfo *LI,
                       OptimizationRemarkEmitter *RunORE, MemorySSA *MSSA) {

llvm/test/Transforms/GVN/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.
+
+@0 = internal global i32 0, align 4
+@z = external global i32, align 4
+
+declare void @foo(i32*)
+
+; Function Attrs: norecurse
+define void @test1(i32* %arg) #0 {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[I12:%.*]] = load i32, i32* [[ARG:%.*]], align 4
+; CHECK-NEXT:    [[I14:%.*]] = load i32, i32* @z, align 4
+; CHECK-NEXT:    switch i32 [[I14]], label [[BB15:%.*]] [
+; CHECK-NEXT:    i32 0, label [[BB16:%.*]]
+; CHECK-NEXT:    i32 2, label [[BB20:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb15:
+; CHECK-NEXT:    ret void
+; CHECK:       bb16:
+; CHECK-NEXT:    [[I18:%.*]] = shl i32 [[I12]], 2
+; CHECK-NEXT:    [[I19:%.*]] = getelementptr inbounds i32, i32* null, i32 [[I18]]
+; CHECK-NEXT:    tail call void @foo(i32* [[I19]])
+; CHECK-NEXT:    br label [[BB24:%.*]]
+; CHECK:       bb20:
+; CHECK-NEXT:    [[I22:%.*]] = shl i32 [[I12]], 2
+; CHECK-NEXT:    [[I23:%.*]] = getelementptr inbounds i32, i32* null, i32 [[I22]]
+; CHECK-NEXT:    tail call void @foo(i32* [[I23]])
+; CHECK-NEXT:    br label [[BB24]]
+; CHECK:       bb24:
+; CHECK-NEXT:    [[I27_PRE_PHI:%.*]] = phi i32 [ [[I22]], [[BB20]] ], [ [[I18]], [[BB16]] ]
+; CHECK-NEXT:    [[I28:%.*]] = getelementptr inbounds i32, i32* null, i32 [[I27_PRE_PHI]]
+; CHECK-NEXT:    [[I29:%.*]] = load i32, i32* [[I28]], align 4
+; CHECK-NEXT:    store i32 [[I29]], i32* @z, align 4
+; CHECK-NEXT:    br label [[BB20]]
+;
+bb:
+  %i12 = load i32, i32* %arg, align 4
+  %i14 = load i32, i32* @z, align 4
+  switch i32 %i14, label %bb15 [
+  i32 0, label %bb16
+  i32 2, label %bb20
+  ]
+
+bb15:                                             ; preds = %bb
+  ret void
+
+bb16:                                             ; preds = %bb
+  %i18 = shl i32 %i12, 2
+  %i19 = getelementptr inbounds i32, i32* null, i32 %i18
+  tail call void @foo(i32* %i19)
+  br label %bb24
+
+bb20:                                             ; preds = %bb24, %bb
+  %i22 = shl i32 %i12, 2
+  %i23 = getelementptr inbounds i32, i32* null, i32 %i22
+  tail call void @foo(i32* %i23)
+  br label %bb24
+
+bb24:                                             ; preds = %bb20, %bb16
+  %i27 = shl i32 %i12, 2
+  %i28 = getelementptr inbounds i32, i32* null , i32 %i27
+  %i29 = load i32, i32* %i28, align 4
+  store i32 %i29, i32* @z, align 4
+  br label %bb20
+}
+
+attributes #0 = { norecurse }