diff --git a/llvm/include/llvm/Transforms/Utils/Local.h b/llvm/include/llvm/Transforms/Utils/Local.h --- a/llvm/include/llvm/Transforms/Utils/Local.h +++ b/llvm/include/llvm/Transforms/Utils/Local.h @@ -162,8 +162,18 @@ /// 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. +/// +/// This overload removes the duplicate PHI nodes directly. bool EliminateDuplicatePHINodes(BasicBlock *BB); +/// 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. +/// +/// This overload collects the PHI nodes to be removed into the ToRemove set. +bool EliminateDuplicatePHINodes(BasicBlock *BB, + SmallPtrSetImpl &ToRemove); + /// 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. diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -2766,7 +2766,10 @@ // 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 PHINodesToRemove; + ChangedFunction |= EliminateDuplicatePHINodes(BB, PHINodesToRemove); + for (PHINode *PN : PHINodesToRemove) + removeInstruction(PN); for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp --- a/llvm/lib/Transforms/Utils/Local.cpp +++ b/llvm/lib/Transforms/Utils/Local.cpp @@ -1247,7 +1247,9 @@ return true; } -static bool EliminateDuplicatePHINodesNaiveImpl(BasicBlock *BB) { +static bool +EliminateDuplicatePHINodesNaiveImpl(BasicBlock *BB, + SmallPtrSetImpl &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. @@ -1263,12 +1265,14 @@ // 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(J); ++J) { + if (ToRemove.contains(DuplicatePN)) + continue; if (!DuplicatePN->isIdenticalToWhenDefined(PN)) continue; // A duplicate. Replace this PHI with the base PHI. ++NumPHICSEs; DuplicatePN->replaceAllUsesWith(PN); - DuplicatePN->eraseFromParent(); + ToRemove.insert(DuplicatePN); Changed = true; // The RAUW can change PHIs that we already visited. @@ -1279,7 +1283,9 @@ return Changed; } -static bool EliminateDuplicatePHINodesSetBasedImpl(BasicBlock *BB) { +static bool +EliminateDuplicatePHINodesSetBasedImpl(BasicBlock *BB, + SmallPtrSetImpl &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. @@ -1343,12 +1349,14 @@ // Examine each PHI. bool Changed = false; for (auto I = BB->begin(); PHINode *PN = dyn_cast(I++);) { + if (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); - PN->eraseFromParent(); + ToRemove.insert(PN); Changed = true; // The RAUW can change PHIs that we already visited. Start over from the @@ -1361,14 +1369,23 @@ return Changed; } -bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { +bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB, + SmallPtrSetImpl &ToRemove) { if ( #ifndef NDEBUG !PHICSEDebugHash && #endif hasNItemsOrLess(BB->phis(), PHICSENumPHISmallSize)) - return EliminateDuplicatePHINodesNaiveImpl(BB); - return EliminateDuplicatePHINodesSetBasedImpl(BB); + return EliminateDuplicatePHINodesNaiveImpl(BB, ToRemove); + return EliminateDuplicatePHINodesSetBasedImpl(BB, ToRemove); +} + +bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { + SmallPtrSet ToRemove; + bool Changed = EliminateDuplicatePHINodes(BB, ToRemove); + for (PHINode *PN : ToRemove) + PN->eraseFromParent(); + return Changed; } /// If the specified pointer points to an object that we control, try to modify diff --git a/llvm/test/Transforms/GVN/pr64598.ll b/llvm/test/Transforms/GVN/pr64598.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/GVN/pr64598.ll @@ -0,0 +1,103 @@ +; 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}