From 27b1e3bd4f7a064a2672e30cc6be31433ebd300b Mon Sep 17 00:00:00 2001 From: Joseph Tremoulet Date: Fri, 30 Nov 2018 19:20:02 +0000 Subject: [Mem2Reg] Fix nondeterministic corner case Summary: When mem2reg inserts phi nodes in blocks with unreachable predecessors, it adds undef operands for those incoming edges. When there are multiple such predecessors, the order is currently based on the address of the BasicBlocks. This change fixes that by using the BBNumbers in the sort/search predicates, as is done elsewhere in mem2reg to ensure determinism. Also adds a testcase with a bunch of unreachable preds, which (nodeterministically) fails without the fix. Reviewers: majnemer Reviewed By: majnemer Subscribers: mgrang, llvm-commits Differential Revision: https://reviews.llvm.org/D55077 llvm-svn: 348024 --- llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'llvm/lib/Transforms') diff --git a/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp index 6773ad7bfc7..a53083c31e3 100644 --- a/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ b/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -751,14 +751,18 @@ void PromoteMem2Reg::run() { // Ok, now we know that all of the PHI nodes are missing entries for some // basic blocks. Start by sorting the incoming predecessors for efficient // access. - llvm::sort(Preds); + auto CompareBBNumbers = [this](BasicBlock *A, BasicBlock *B) { + return BBNumbers.lookup(A) < BBNumbers.lookup(B); + }; + llvm::sort(Preds, CompareBBNumbers); // Now we loop through all BB's which have entries in SomePHI and remove // them from the Preds list. for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) { // Do a log(n) search of the Preds list for the entry we want. SmallVectorImpl::iterator EntIt = std::lower_bound( - Preds.begin(), Preds.end(), SomePHI->getIncomingBlock(i)); + Preds.begin(), Preds.end(), SomePHI->getIncomingBlock(i), + CompareBBNumbers); assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i) && "PHI node has entry for a block which is not a predecessor!"); -- cgit v1.2.3