diff options
author | Tom Stellard <thomas.stellard@amd.com> | 2015-11-12 20:04:50 +0000 |
---|---|---|
committer | Tom Stellard <thomas.stellard@amd.com> | 2015-11-12 20:04:50 +0000 |
commit | 489d180cec46e95498ddff9b76086cd8cca7abeb (patch) | |
tree | 82a0addc0499923ec15e613db81fee727ca6713f | |
parent | a9269ea69feb871b25e03e11aa49b43e90b44754 (diff) | |
download | llvm-489d180cec46e95498ddff9b76086cd8cca7abeb.tar.gz |
Merging r246694:
------------------------------------------------------------------------
r246694 | benny.kra | 2015-09-02 15:52:23 -0400 (Wed, 02 Sep 2015) | 44 lines
[RemoveDuplicatePHINodes] Start over after removing a PHI.
This makes RemoveDuplicatePHINodes more effective and fixes an assertion
failure. Triggering the assertions requires a DenseSet reallocation
so this change only contains a constructive test.
I'll explain the issue with a small example. In the following function
there's a duplicate PHI, %4 and %5 are identical. When this is found
the DenseSet in RemoveDuplicatePHINodes contains %2, %3 and %4.
define void @F() {
br label %1
; <label>:1 ; preds = %1, %0
%2 = phi i32 [ 42, %0 ], [ %4, %1 ]
%3 = phi i32 [ 42, %0 ], [ %5, %1 ]
%4 = phi i32 [ 42, %0 ], [ 23, %1 ]
%5 = phi i32 [ 42, %0 ], [ 23, %1 ]
br label %1
}
after RemoveDuplicatePHINodes runs the function looks like this. %3 has
changed and is now identical to %2, but RemoveDuplicatePHINodes never
saw this.
define void @F() {
br label %1
; <label>:1 ; preds = %1, %0
%2 = phi i32 [ 42, %0 ], [ %4, %1 ]
%3 = phi i32 [ 42, %0 ], [ %4, %1 ]
%4 = phi i32 [ 42, %0 ], [ 23, %1 ]
br label %1
}
If the DenseSet does a reallocation now it will reinsert all
keys and stumble over %3 now having a different hash value than it had
when inserted into the map for the first time. This change clears the
set whenever a PHI is deleted and starts the progress from the
beginning, allowing %3 to be deleted and avoiding inconsistent DenseSet
state. This potentially has a negative performance impact because
it rescans all PHIs, but I don't think that this ever makes a difference
in practice.
------------------------------------------------------------------------
git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_37@252938 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | lib/Transforms/Utils/Local.cpp | 5 | ||||
-rw-r--r-- | unittests/Transforms/Utils/Local.cpp | 37 |
2 files changed, 42 insertions, 0 deletions
diff --git a/lib/Transforms/Utils/Local.cpp b/lib/Transforms/Utils/Local.cpp index 50ca6234d0b7..ba8af47b54e1 100644 --- a/lib/Transforms/Utils/Local.cpp +++ b/lib/Transforms/Utils/Local.cpp @@ -869,6 +869,11 @@ bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) { PN->replaceAllUsesWith(*Inserted.first); PN->eraseFromParent(); Changed = true; + + // The RAUW can change PHIs that we already visited. Start over from the + // beginning. + PHISet.clear(); + I = BB->begin(); } } diff --git a/unittests/Transforms/Utils/Local.cpp b/unittests/Transforms/Utils/Local.cpp index f0c3ecfbb9b8..2ff560475551 100644 --- a/unittests/Transforms/Utils/Local.cpp +++ b/unittests/Transforms/Utils/Local.cpp @@ -58,3 +58,40 @@ TEST(Local, RecursivelyDeleteDeadPHINodes) { delete bb0; delete bb1; } + +TEST(Local, RemoveDuplicatePHINodes) { + LLVMContext &C(getGlobalContext()); + IRBuilder<> B(C); + + std::unique_ptr<Function> F( + Function::Create(FunctionType::get(B.getVoidTy(), false), + GlobalValue::ExternalLinkage, "F")); + BasicBlock *Entry(BasicBlock::Create(C, "", F.get())); + BasicBlock *BB(BasicBlock::Create(C, "", F.get())); + BranchInst::Create(BB, Entry); + + B.SetInsertPoint(BB); + + AssertingVH<PHINode> P1 = B.CreatePHI(Type::getInt32Ty(C), 2); + P1->addIncoming(B.getInt32(42), Entry); + + PHINode *P2 = B.CreatePHI(Type::getInt32Ty(C), 2); + P2->addIncoming(B.getInt32(42), Entry); + + AssertingVH<PHINode> P3 = B.CreatePHI(Type::getInt32Ty(C), 2); + P3->addIncoming(B.getInt32(42), Entry); + P3->addIncoming(B.getInt32(23), BB); + + PHINode *P4 = B.CreatePHI(Type::getInt32Ty(C), 2); + P4->addIncoming(B.getInt32(42), Entry); + P4->addIncoming(B.getInt32(23), BB); + + P1->addIncoming(P3, BB); + P2->addIncoming(P4, BB); + BranchInst::Create(BB, BB); + + // Verify that we can eliminate PHIs that become duplicates after chaning PHIs + // downstream. + EXPECT_TRUE(EliminateDuplicatePHINodes(BB)); + EXPECT_EQ(3U, BB->size()); +} |