[GVN] Invalidate MDA when deduplicating phi nodes

[nikic]

Summary

Duplicate phi nodes were being directly removed, without invalidating MDA. This could result in a new phi node being allocated at the same address, incorrectly reusing a cache entry.

Fix this by optionally allowing EliminateDuplicatePHINodes() to collect phi nodes to remove into a vector, which allows GVN to handle removal itself.

Fixes https://github.com/llvm/llvm-project/issues/64598.

[nikic]

llvm/test/Transforms/GVN/pr64598.ll

3

I got this test case by llvm-reducing between "good opt" and "bad opt", so I'm not sure how meaningful it is. I haven't pre-committed this test because address reuse might be flaky.

I would have preferred to instead expose the issue by adding an AssertingVH in MemDepAnalysis. Unfortunately, the problematic value is part of using ValueIsLoadPair = PointerIntPair<const Value *, 1, bool> and there is no easy way to use AssertingVH in there (even if switching to std::pair, given how it is used).

[Carrot]

llvm/include/llvm/Transforms/Utils/Local.h

169

Why not use SmallPtrSet?

[nikic]

llvm/include/llvm/Transforms/Utils/Local.h

169

I was trying to make sure the order is deterministic -- maybe it doesn't matter though?

[Carrot]

llvm/include/llvm/Transforms/Utils/Local.h

169

Each PHINode address is unique, and it is only used to check if a PHI instruction is contained in the set in function EliminateDuplicatePHINodes, and later delete all instructions in the set. So I think the order doesn't matter.

[nikic]

Use SmallPtrSet instead of SmallSetVector.

[fhahn]

llvm/lib/Transforms/Utils/Local.cpp

1290

It might simplify the code in the static functions if ToRemove would be required for the static functions and have a loop to remove them in EliminateDuplicatePHINodes if the pointer is null?

llvm/test/Transforms/GVN/pr64598.ll

3

I sounds like the test as is to be the best option we have for now unfortunately

[nikic]

Always use the set in the implementation, implement set-less overload on top of it.

[nikic]

ping

[Carrot]

Looks good to me.

llvm/include/llvm/Transforms/Utils/Local.h

 /// possible, eliminate BB by rewriting all the predecessors to branch to the
 /// successor block and return true. If we can't transform, return false.
 bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
                                              DomTreeUpdater *DTU = nullptr);
 
 /// Check for and eliminate duplicate PHI nodes in this block. This doesn't try
 /// to be clever about PHI nodes which differ only in the order of the incoming
 /// values, but instcombine orders them so it usually won't matter.
-bool EliminateDuplicatePHINodes(BasicBlock *BB);
+///
+/// If ToRemove is specified, then phi nodes will be added to this vector
+/// instead of being directly removed.
+bool EliminateDuplicatePHINodes(
+    BasicBlock *BB, SmallPtrSetImpl<PHINode *> *ToRemove = nullptr);
 
 /// This function is used to do simplification of a CFG.  For example, it
 /// adjusts branches to branches to eliminate the extra hop, it eliminates
 /// unreachable basic blocks, and does other peephole optimization of the CFG.
 /// It returns true if a modification was made, possibly deleting the basic
 /// block that was pointed to. LoopHeaders is an optional input parameter
 /// providing the set of loop headers that SimplifyCFG should not eliminate.
 extern cl::opt<bool> RequireAndPreserveDomTree;

llvm/lib/Transforms/Scalar/GVN.cpp

bool GVNPass::processBlock(BasicBlock *BB) {
   // Clearing map before every BB because it can be used only for single BB.
   ReplaceOperandsWithMap.clear();
   bool ChangedFunction = false;
 
   // Since we may not have visited the input blocks of the phis, we can't
   // use our normal hash approach for phis.  Instead, simply look for
   // obvious duplicates.  The first pass of GVN will tend to create
   // identical phis, and the second or later passes can eliminate them.
-  ChangedFunction |= EliminateDuplicatePHINodes(BB);
+  SmallPtrSet<PHINode *, 8> PHINodesToRemove;
+  ChangedFunction |= EliminateDuplicatePHINodes(BB, &PHINodesToRemove);
+  for (PHINode *PN : PHINodesToRemove)
+    removeInstruction(PN);
 
   for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
        BI != BE;) {
     if (!ReplaceOperandsWithMap.empty())
       ChangedFunction |= replaceOperandsForInBlockEquality(&*BI);
     ChangedFunction |= processInstruction(&*BI);
 
     if (InstrsToErase.empty()) {

llvm/lib/Transforms/Utils/Local.cpp

bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
   if (DTU)
     DTU->applyUpdates(Updates);
 
   DeleteDeadBlock(BB, DTU);
 
   return true;
 }
 
-static bool EliminateDuplicatePHINodesNaiveImpl(BasicBlock *BB) {
+static bool
+EliminateDuplicatePHINodesNaiveImpl(BasicBlock *BB,
+                                    SmallPtrSetImpl<PHINode *> *ToRemove) {
   // This implementation doesn't currently consider undef operands
   // specially. Theoretically, two phis which are identical except for
   // one having an undef where the other doesn't could be collapsed.
 
   bool Changed = false;
 
   // Examine each PHI.
   // Note that increment of I must *NOT* be in the iteration_expression, since
   // we don't want to immediately advance when we restart from the beginning.
   for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I);) {
     ++I;
     // Is there an identical PHI node in this basic block?
     // Note that we only look in the upper square's triangle,
     // we already checked that the lower triangle PHI's aren't identical.
     for (auto J = I; PHINode *DuplicatePN = dyn_cast<PHINode>(J); ++J) {
+      if (ToRemove && ToRemove->contains(DuplicatePN))
+        continue;
       if (!DuplicatePN->isIdenticalToWhenDefined(PN))
         continue;
       // A duplicate. Replace this PHI with the base PHI.
       ++NumPHICSEs;
       DuplicatePN->replaceAllUsesWith(PN);
+      if (ToRemove)
+        ToRemove->insert(DuplicatePN);
+      else
         DuplicatePN->eraseFromParent();
       Changed = true;
 
       // The RAUW can change PHIs that we already visited.
       I = BB->begin();
       break; // Start over from the beginning.
     }
   }
   return Changed;
 }
 
-static bool EliminateDuplicatePHINodesSetBasedImpl(BasicBlock *BB) {
+static bool
+EliminateDuplicatePHINodesSetBasedImpl(BasicBlock *BB,
+                                       SmallPtrSetImpl<PHINode *> *ToRemove) {
   // This implementation doesn't currently consider undef operands
   // specially. Theoretically, two phis which are identical except for
   // one having an undef where the other doesn't could be collapsed.
 
   struct PHIDenseMapInfo {
     static PHINode *getEmptyKey() {
       return DenseMapInfo<PHINode *>::getEmptyKey();
     }
#endif
 
   // Set of unique PHINodes.
   DenseSet<PHINode *, PHIDenseMapInfo> PHISet;
   PHISet.reserve(4 * PHICSENumPHISmallSize);
 
   // Examine each PHI.
   bool Changed = false;
   for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) {
+    if (ToRemove && ToRemove->contains(PN))
+      continue;
     auto Inserted = PHISet.insert(PN);
     if (!Inserted.second) {
       // A duplicate. Replace this PHI with its duplicate.
       ++NumPHICSEs;
       PN->replaceAllUsesWith(*Inserted.first);
+      if (ToRemove)
+        ToRemove->insert(PN);
+      else
         PN->eraseFromParent();
       Changed = true;
 
       // The RAUW can change PHIs that we already visited. Start over from the
       // beginning.
       PHISet.clear();
       I = BB->begin();
     }
   }
 
   return Changed;
 }
 
-bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
+bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB,
+                                      SmallPtrSetImpl<PHINode *> *ToRemove) {
   if (
 #ifndef NDEBUG
       !PHICSEDebugHash &&
 #endif
       hasNItemsOrLess(BB->phis(), PHICSENumPHISmallSize))
-    return EliminateDuplicatePHINodesNaiveImpl(BB);
-  return EliminateDuplicatePHINodesSetBasedImpl(BB);
+    return EliminateDuplicatePHINodesNaiveImpl(BB, ToRemove);
+  return EliminateDuplicatePHINodesSetBasedImpl(BB, ToRemove);
 }
 
 /// If the specified pointer points to an object that we control, try to modify
 /// the object's alignment to PrefAlign. Returns a minimum known alignment of
 /// the value after the operation, which may be lower than PrefAlign.
 ///
 /// Increating value alignment isn't often possible though. If alignment is
 /// important, a more reliable approach is to simply align all global variables

llvm/test/Transforms/GVN/pr64598.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt -S -passes=gvn < %s | FileCheck %s
+
+define i32 @main(i64 %x, ptr %d, ptr noalias %p) {
+; CHECK-LABEL: define i32 @main
+; CHECK-SAME: (i64 [[X:%.*]], ptr [[D:%.*]], ptr noalias [[P:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[T1_PRE_PRE_PRE:%.*]] = load ptr, ptr [[P]], align 8
+; CHECK-NEXT:    [[T2_PRE_PRE_PRE:%.*]] = load ptr, ptr [[T1_PRE_PRE_PRE]], align 8, !tbaa [[TBAA0:![0-9]+]]
+; CHECK-NEXT:    [[T3_PRE_PRE_PRE:%.*]] = load ptr, ptr [[T2_PRE_PRE_PRE]], align 8
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[T2_PRE_PRE:%.*]] = phi ptr [ [[T2_PRE_PRE23:%.*]], [[LOOP_LATCH:%.*]] ], [ [[T2_PRE_PRE_PRE]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[T1_PRE_PRE:%.*]] = phi ptr [ [[T1_PRE_PRE19:%.*]], [[LOOP_LATCH]] ], [ [[T1_PRE_PRE_PRE]], [[ENTRY]] ]
+; CHECK-NEXT:    br label [[LOOP2:%.*]]
+; CHECK:       loop2:
+; CHECK-NEXT:    [[T2_PRE_PRE25:%.*]] = phi ptr [ [[T2_PRE_PRE23]], [[LOOP2_LATCH_LOOP2_CRIT_EDGE:%.*]] ], [ [[T2_PRE_PRE]], [[LOOP]] ]
+; CHECK-NEXT:    [[T1_PRE_PRE21:%.*]] = phi ptr [ [[T1_PRE_PRE19]], [[LOOP2_LATCH_LOOP2_CRIT_EDGE]] ], [ [[T1_PRE_PRE]], [[LOOP]] ]
+; CHECK-NEXT:    [[T3_PRE:%.*]] = phi ptr [ [[T3_PRE16:%.*]], [[LOOP2_LATCH_LOOP2_CRIT_EDGE]] ], [ [[T3_PRE_PRE_PRE]], [[LOOP]] ]
+; CHECK-NEXT:    [[T2_PRE:%.*]] = phi ptr [ [[T2_PRE13:%.*]], [[LOOP2_LATCH_LOOP2_CRIT_EDGE]] ], [ [[T2_PRE_PRE]], [[LOOP]] ]
+; CHECK-NEXT:    [[T1_PRE:%.*]] = phi ptr [ [[T1_PRE10:%.*]], [[LOOP2_LATCH_LOOP2_CRIT_EDGE]] ], [ [[T1_PRE_PRE]], [[LOOP]] ]
+; CHECK-NEXT:    br label [[LOOP3:%.*]]
+; CHECK:       loop3:
+; CHECK-NEXT:    [[T2_PRE_PRE24:%.*]] = phi ptr [ [[T2_PRE_PRE23]], [[LOOP3_LATCH:%.*]] ], [ [[T2_PRE_PRE25]], [[LOOP2]] ]
+; CHECK-NEXT:    [[T1_PRE_PRE20:%.*]] = phi ptr [ [[T1_PRE_PRE19]], [[LOOP3_LATCH]] ], [ [[T1_PRE_PRE21]], [[LOOP2]] ]
+; CHECK-NEXT:    [[T3_PRE17:%.*]] = phi ptr [ [[T3_PRE16]], [[LOOP3_LATCH]] ], [ [[T3_PRE]], [[LOOP2]] ]
+; CHECK-NEXT:    [[T2_PRE14:%.*]] = phi ptr [ [[T2_PRE13]], [[LOOP3_LATCH]] ], [ [[T2_PRE]], [[LOOP2]] ]
+; CHECK-NEXT:    [[T1_PRE11:%.*]] = phi ptr [ [[T1_PRE10]], [[LOOP3_LATCH]] ], [ [[T1_PRE]], [[LOOP2]] ]
+; CHECK-NEXT:    [[T78:%.*]] = phi ptr [ [[T7:%.*]], [[LOOP3_LATCH]] ], [ [[T3_PRE]], [[LOOP2]] ]
+; CHECK-NEXT:    [[T66:%.*]] = phi ptr [ [[T6:%.*]], [[LOOP3_LATCH]] ], [ [[T2_PRE]], [[LOOP2]] ]
+; CHECK-NEXT:    [[T54:%.*]] = phi ptr [ [[T5:%.*]], [[LOOP3_LATCH]] ], [ [[T1_PRE]], [[LOOP2]] ]
+; CHECK-NEXT:    [[TOBOOL_NOT2_I:%.*]] = icmp eq i64 [[X]], 0
+; CHECK-NEXT:    br i1 false, label [[LOOP3_LOOP3_LATCH_CRIT_EDGE:%.*]], label [[FOR_BODY_LR_PH_I:%.*]]
+; CHECK:       loop3.loop3.latch_crit_edge:
+; CHECK-NEXT:    br label [[LOOP3_LATCH]]
+; CHECK:       for.body.lr.ph.i:
+; CHECK-NEXT:    store i32 0, ptr [[P]], align 4
+; CHECK-NEXT:    [[T5_PRE:%.*]] = load ptr, ptr [[P]], align 8
+; CHECK-NEXT:    [[T6_PRE:%.*]] = load ptr, ptr [[T5_PRE]], align 8, !tbaa [[TBAA0]]
+; CHECK-NEXT:    [[T7_PRE:%.*]] = load ptr, ptr [[T6_PRE]], align 8
+; CHECK-NEXT:    br label [[LOOP3_LATCH]]
+; CHECK:       loop3.latch:
+; CHECK-NEXT:    [[T2_PRE_PRE23]] = phi ptr [ [[T2_PRE_PRE24]], [[LOOP3_LOOP3_LATCH_CRIT_EDGE]] ], [ [[T6_PRE]], [[FOR_BODY_LR_PH_I]] ]
+; CHECK-NEXT:    [[T1_PRE_PRE19]] = phi ptr [ [[T1_PRE_PRE20]], [[LOOP3_LOOP3_LATCH_CRIT_EDGE]] ], [ [[T5_PRE]], [[FOR_BODY_LR_PH_I]] ]
+; CHECK-NEXT:    [[T3_PRE16]] = phi ptr [ [[T3_PRE17]], [[LOOP3_LOOP3_LATCH_CRIT_EDGE]] ], [ [[T7_PRE]], [[FOR_BODY_LR_PH_I]] ]
+; CHECK-NEXT:    [[T2_PRE13]] = phi ptr [ [[T2_PRE14]], [[LOOP3_LOOP3_LATCH_CRIT_EDGE]] ], [ [[T6_PRE]], [[FOR_BODY_LR_PH_I]] ]
+; CHECK-NEXT:    [[T1_PRE10]] = phi ptr [ [[T1_PRE11]], [[LOOP3_LOOP3_LATCH_CRIT_EDGE]] ], [ [[T5_PRE]], [[FOR_BODY_LR_PH_I]] ]
+; CHECK-NEXT:    [[T7]] = phi ptr [ [[T78]], [[LOOP3_LOOP3_LATCH_CRIT_EDGE]] ], [ [[T7_PRE]], [[FOR_BODY_LR_PH_I]] ]
+; CHECK-NEXT:    [[T6]] = phi ptr [ [[T66]], [[LOOP3_LOOP3_LATCH_CRIT_EDGE]] ], [ [[T6_PRE]], [[FOR_BODY_LR_PH_I]] ]
+; CHECK-NEXT:    [[T5]] = phi ptr [ [[T54]], [[LOOP3_LOOP3_LATCH_CRIT_EDGE]] ], [ [[T5_PRE]], [[FOR_BODY_LR_PH_I]] ]
+; CHECK-NEXT:    br i1 false, label [[LOOP2_LATCH:%.*]], label [[LOOP3]]
+; CHECK:       loop2.latch:
+; CHECK-NEXT:    br i1 false, label [[LOOP2_LATCH_LOOP2_CRIT_EDGE]], label [[LOOP_LATCH]]
+; CHECK:       loop2.latch.loop2_crit_edge:
+; CHECK-NEXT:    br label [[LOOP2]]
+; CHECK:       loop.latch:
+; CHECK-NEXT:    store i32 0, ptr [[D]], align 4, !tbaa [[TBAA4:![0-9]+]]
+; CHECK-NEXT:    br label [[LOOP]]
+;
+entry:
+  br label %loop
+
+loop:
+  br label %loop2
+
+loop2:
+  br label %loop3
+
+loop3:
+  %t1 = load ptr, ptr %p, align 8
+  %t2 = load ptr, ptr %t1, align 8, !tbaa !0
+  %t3 = load ptr, ptr %t2, align 8
+  %t4 = load i8, ptr %t3, align 1
+  %tobool.not2.i = icmp eq i64 %x, 0
+  br i1 false, label %loop3.latch, label %for.body.lr.ph.i
+
+for.body.lr.ph.i:
+  store i32 0, ptr %p, align 4
+  br label %w.exit.loopexit
+
+w.exit.loopexit:
+  br label %loop3.latch
+
+loop3.latch:
+  %t5 = load ptr, ptr %p, align 8
+  %t6 = load ptr, ptr %t5, align 8, !tbaa !0
+  %t7 = load ptr, ptr %t6, align 8
+  br i1 false, label %loop2.latch, label %loop3
+
+loop2.latch:
+  br i1 false, label %loop2, label %loop.latch
+
+loop.latch:
+  store i32 0, ptr %d, align 4, !tbaa !4
+  br label %loop
+}
+
+!0 = !{!1, !1, i64 0}
+!1 = !{!"any pointer", !2, i64 0}
+!2 = !{!"omnipotent char", !3, i64 0}
+!3 = !{!"Simple C/C++ TBAA"}
+!4 = !{!5, !5, i64 0}
+!5 = !{!"int", !2, i64 0}