Index: include/llvm/Analysis/MemorySSAUpdater.h =================================================================== --- include/llvm/Analysis/MemorySSAUpdater.h +++ include/llvm/Analysis/MemorySSAUpdater.h @@ -48,6 +48,7 @@ #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/ErrorHandling.h" +#include namespace llvm { @@ -60,7 +61,7 @@ class MemorySSAUpdater { private: MemorySSA *MSSA; - SmallVector InsertedPHIs; + std::set> InsertedPHIs; SmallPtrSet VisitedBlocks; SmallSet, 8> NonOptPhis; @@ -173,7 +174,7 @@ MemoryAccess *recursePhi(MemoryAccess *Phi); template MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands); - void fixupDefs(const SmallVectorImpl &); + void fixupDef(MemoryAccess *); }; } // end namespace llvm Index: lib/Analysis/MemorySSAUpdater.cpp =================================================================== --- lib/Analysis/MemorySSAUpdater.cpp +++ lib/Analysis/MemorySSAUpdater.cpp @@ -100,7 +100,7 @@ unsigned i = 0; for (auto *Pred : predecessors(BB)) Phi->addIncoming(PhiOps[i++], Pred); - InsertedPHIs.push_back(Phi); + InsertedPHIs.insert(Phi); } Result = Phi; } @@ -205,6 +205,7 @@ if (Same == nullptr) return MSSA->getLiveOnEntryDef(); if (Phi) { + InsertedPHIs.erase(Phi); Phi->replaceAllUsesWith(Same); removeMemoryAccess(Phi); } @@ -278,8 +279,6 @@ // above and reset ourselves. MD->setDefiningAccess(DefBefore); - SmallVector FixupList(InsertedPHIs.begin(), - InsertedPHIs.end()); if (!DefBeforeSameBlock) { // If there was a local def before us, we must have the same effect it // did. Because every may-def is the same, any phis/etc we would create, it @@ -292,15 +291,21 @@ // backwards to find the def. To make that work, we'd have to track whether // getDefRecursive only ever used the single predecessor case. These types // of paths also only exist in between CFG simplifications. - FixupList.push_back(MD); + fixupDef(MD); } - while (!FixupList.empty()) { - unsigned StartingPHISize = InsertedPHIs.size(); - fixupDefs(FixupList); - FixupList.clear(); - // Put any new phis on the fixup list, and process them - FixupList.append(InsertedPHIs.end() - StartingPHISize, InsertedPHIs.end()); + SmallPtrSet Seen; + unsigned cnt = 0; + while (cnt != InsertedPHIs.size()) { + for (auto &MP : InsertedPHIs) { + ++cnt; + if (Seen.insert(MP).second) { + fixupDef(MP); + // We might have inserted/erased PHIs so we have to re-iterate. + cnt = 0; + break; + } + } } // Now that all fixups are done, rename all uses if we are asked. if (RenameUses) { @@ -317,73 +322,72 @@ MSSA->renamePass(MD->getBlock(), FirstDef, Visited); // We just inserted a phi into this block, so the incoming value will become // the phi anyway, so it does not matter what we pass. - for (auto *MP : InsertedPHIs) + for (auto &MP : InsertedPHIs) MSSA->renamePass(MP->getBlock(), nullptr, Visited); } } -void MemorySSAUpdater::fixupDefs(const SmallVectorImpl &Vars) { +void MemorySSAUpdater::fixupDef(MemoryAccess *NewDef) { SmallPtrSet Seen; SmallVector Worklist; - for (auto *NewDef : Vars) { - // First, see if there is a local def after the operand. - auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock()); - auto DefIter = NewDef->getDefsIterator(); - - // The temporary Phi is being fixed, unmark it for not to optimize. - if (MemoryPhi *Phi = dyn_cast_or_null(NewDef)) - NonOptPhis.erase(Phi); - - // If there is a local def after us, we only have to rename that. - if (++DefIter != Defs->end()) { - cast(DefIter)->setDefiningAccess(NewDef); - continue; - } - // Otherwise, we need to search down through the CFG. - // For each of our successors, handle it directly if their is a phi, or - // place on the fixup worklist. - for (const auto *S : successors(NewDef->getBlock())) { + // First, see if there is a local def after the operand. + auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock()); + auto DefIter = NewDef->getDefsIterator(); + + // The temporary Phi is being fixed, unmark it for not to optimize. + if (MemoryPhi *Phi = dyn_cast_or_null(NewDef)) + NonOptPhis.erase(Phi); + + // If there is a local def after us, we only have to rename that. + if (++DefIter != Defs->end()) { + cast(DefIter)->setDefiningAccess(NewDef); + return; + } + + // Otherwise, we need to search down through the CFG. + // For each of our successors, handle it directly if their is a phi, or + // place on the fixup worklist. + for (const auto *S : successors(NewDef->getBlock())) { + if (auto *MP = MSSA->getMemoryAccess(S)) + setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef); + else + Worklist.push_back(S); + } + + while (!Worklist.empty()) { + const BasicBlock *FixupBlock = Worklist.back(); + Worklist.pop_back(); + + // Get the first def in the block that isn't a phi node. + if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) { + auto *FirstDef = &*Defs->begin(); + // The loop above and below should have taken care of phi nodes + assert(!isa(FirstDef) && + "Should have already handled phi nodes!"); + // We are now this def's defining access, make sure we actually dominate + // it + assert(MSSA->dominates(NewDef, FirstDef) && + "Should have dominated the new access"); + + // This may insert new phi nodes, because we are not guaranteed the + // block we are processing has a single pred, and depending where the + // store was inserted, it may require phi nodes below it. + cast(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef)); + return; + } + // We didn't find a def, so we must continue. + for (const auto *S : successors(FixupBlock)) { + // If there is a phi node, handle it. + // Otherwise, put the block on the worklist if (auto *MP = MSSA->getMemoryAccess(S)) - setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef); - else + setMemoryPhiValueForBlock(MP, FixupBlock, NewDef); + else { + // If we cycle, we should have ended up at a phi node that we already + // processed. FIXME: Double check this + if (!Seen.insert(S).second) + continue; Worklist.push_back(S); - } - - while (!Worklist.empty()) { - const BasicBlock *FixupBlock = Worklist.back(); - Worklist.pop_back(); - - // Get the first def in the block that isn't a phi node. - if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) { - auto *FirstDef = &*Defs->begin(); - // The loop above and below should have taken care of phi nodes - assert(!isa(FirstDef) && - "Should have already handled phi nodes!"); - // We are now this def's defining access, make sure we actually dominate - // it - assert(MSSA->dominates(NewDef, FirstDef) && - "Should have dominated the new access"); - - // This may insert new phi nodes, because we are not guaranteed the - // block we are processing has a single pred, and depending where the - // store was inserted, it may require phi nodes below it. - cast(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef)); - return; - } - // We didn't find a def, so we must continue. - for (const auto *S : successors(FixupBlock)) { - // If there is a phi node, handle it. - // Otherwise, put the block on the worklist - if (auto *MP = MSSA->getMemoryAccess(S)) - setMemoryPhiValueForBlock(MP, FixupBlock, NewDef); - else { - // If we cycle, we should have ended up at a phi node that we already - // processed. FIXME: Double check this - if (!Seen.insert(S).second) - continue; - Worklist.push_back(S); - } } } } Index: test/Transforms/GVNHoist/pr37808.ll =================================================================== --- /dev/null +++ test/Transforms/GVNHoist/pr37808.ll @@ -0,0 +1,40 @@ +; RUN: opt < %s -gvn-hoist -S | FileCheck %s + +define void @func() { +; CHECK-LABEL: @func() +; CHECK: bb6: +; CHECK: store i64 0, i64* undef, align 8 +; CHECK: bb7: +; CHECK-NOT: store i64 0, i64* undef, align 8 +; CHECK: bb8: +; CHECK-NOT: store i64 0, i64* undef, align 8 + +entry: + br label %bb1 + +bb1: + br label %bb2 + +bb2: + br label %bb3 + +bb3: + br i1 undef, label %bb4, label %bb2 + +bb4: + br i1 undef, label %bb5, label %bb3 + +bb5: + br label %bb6 + +bb6: + br i1 undef, label %bb7, label %bb8 + +bb7: + store i64 0, i64* undef, align 8 + unreachable + +bb8: + store i64 0, i64* undef, align 8 + ret void +}