Author: tstellar
Date: Thu Nov 12 14:04:50 2015
New Revision: 252938
URL: http://llvm.org/viewvc/llvm-project?rev=252938&view=rev
Log:
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.
------------------------------------------------------------------------
Modified:
llvm/branches/release_37/lib/Transforms/Utils/Local.cpp
llvm/branches/release_37/unittests/Transforms/Utils/Local.cpp
Modified: llvm/branches/release_37/lib/Transforms/Utils/Local.cpp
URL:
http://llvm.org/viewvc/llvm-project/llvm/branches/release_37/lib/Transforms/Utils/Local.cpp?rev=252938&r1=252937&r2=252938&view=diff
==============================================================================
--- llvm/branches/release_37/lib/Transforms/Utils/Local.cpp (original)
+++ llvm/branches/release_37/lib/Transforms/Utils/Local.cpp Thu Nov 12 14:04:50
2015
@@ -869,6 +869,11 @@ bool llvm::EliminateDuplicatePHINodes(Ba
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();
}
}
Modified: llvm/branches/release_37/unittests/Transforms/Utils/Local.cpp
URL:
http://llvm.org/viewvc/llvm-project/llvm/branches/release_37/unittests/Transforms/Utils/Local.cpp?rev=252938&r1=252937&r2=252938&view=diff
==============================================================================
--- llvm/branches/release_37/unittests/Transforms/Utils/Local.cpp (original)
+++ llvm/branches/release_37/unittests/Transforms/Utils/Local.cpp Thu Nov 12
14:04:50 2015
@@ -58,3 +58,40 @@ TEST(Local, RecursivelyDeleteDeadPHINode
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());
+}
_______________________________________________
llvm-branch-commits mailing list
llvm-branch-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
