//===-- MemorySSAUpdater.cpp - Memory SSA Updater--------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------===//
//
// This file implements the MemorySSAUpdater class.
//
//===----------------------------------------------------------------===//
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/IteratedDominanceFrontier.h"
#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Dominators.h"
#include "llvm/Support/Debug.h"
#include <algorithm>
#define DEBUG_TYPE "memoryssa"
using namespace llvm;
// This is the marker algorithm from "Simple and Efficient Construction of
// Static Single Assignment Form"
// The simple, non-marker algorithm places phi nodes at any join
// Here, we place markers, and only place phi nodes if they end up necessary.
// They are only necessary if they break a cycle (IE we recursively visit
// ourselves again), or we discover, while getting the value of the operands,
// that there are two or more definitions needing to be merged.
// This still will leave non-minimal form in the case of irreducible control
// flow, where phi nodes may be in cycles with themselves, but unnecessary.
MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(
BasicBlock *BB,
DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
// First, do a cache lookup. Without this cache, certain CFG structures
// (like a series of if statements) take exponential time to visit.
auto Cached = CachedPreviousDef.find(BB);
if (Cached != CachedPreviousDef.end())
return Cached->second;
// If this method is called from an unreachable block, return LoE.
if (!MSSA->DT->isReachableFromEntry(BB))
return MSSA->getLiveOnEntryDef();
if (BasicBlock *Pred = BB->getUniquePredecessor()) {
VisitedBlocks.insert(BB);
// Single predecessor case, just recurse, we can only have one definition.
MemoryAccess *Result = getPreviousDefFromEnd(Pred, CachedPreviousDef);
CachedPreviousDef.insert({BB, Result});
return Result;
}
if (VisitedBlocks.count(BB)) {
// We hit our node again, meaning we had a cycle, we must insert a phi
// node to break it so we have an operand. The only case this will
// insert useless phis is if we have irreducible control flow.
MemoryAccess *Result = MSSA->createMemoryPhi(BB);
CachedPreviousDef.insert({BB, Result});
return Result;
}
if (VisitedBlocks.insert(BB).second) {
// Mark us visited so we can detect a cycle
SmallVector<TrackingVH<MemoryAccess>, 8> PhiOps;
// Recurse to get the values in our predecessors for placement of a
// potential phi node. This will insert phi nodes if we cycle in order to
// break the cycle and have an operand.
bool UniqueIncomingAccess = true;
MemoryAccess *SingleAccess = nullptr;
for (auto *Pred : predecessors(BB)) {
if (MSSA->DT->isReachableFromEntry(Pred)) {
auto *IncomingAccess = getPreviousDefFromEnd(Pred, CachedPreviousDef);
if (!SingleAccess)
SingleAccess = IncomingAccess;
else if (IncomingAccess != SingleAccess)
UniqueIncomingAccess = false;
PhiOps.push_back(IncomingAccess);
} else
PhiOps.push_back(MSSA->getLiveOnEntryDef());
}
// Now try to simplify the ops to avoid placing a phi.
// This may return null if we never created a phi yet, that's okay
MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));
// See if we can avoid the phi by simplifying it.
auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
// If we couldn't simplify, we may have to create a phi
if (Result == Phi && UniqueIncomingAccess && SingleAccess) {
// A concrete Phi only exists if we created an empty one to break a cycle.
if (Phi) {
assert(Phi->operands().empty() && "Expected empty Phi");
Phi->replaceAllUsesWith(SingleAccess);
removeMemoryAccess(Phi);
}
Result = SingleAccess;
} else if (Result == Phi && !(UniqueIncomingAccess && SingleAccess)) {
if (!Phi)
Phi = MSSA->createMemoryPhi(BB);
// See if the existing phi operands match what we need.
// Unlike normal SSA, we only allow one phi node per block, so we can't just
// create a new one.
if (Phi->getNumOperands() != 0) {
// FIXME: Figure out whether this is dead code and if so remove it.
if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {
// These will have been filled in by the recursive read we did above.
llvm::copy(PhiOps, Phi->op_begin());
std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
}
} else {
unsigned i = 0;
for (auto *Pred : predecessors(BB))
Phi->addIncoming(&*PhiOps[i++], Pred);
InsertedPHIs.push_back(Phi);
}
Result = Phi;
}
// Set ourselves up for the next variable by resetting visited state.
VisitedBlocks.erase(BB);
CachedPreviousDef.insert({BB, Result});
return Result;
}
llvm_unreachable("Should have hit one of the three cases above");
}
// This starts at the memory access, and goes backwards in the block to find the
// previous definition. If a definition is not found the block of the access,
// it continues globally, creating phi nodes to ensure we have a single
// definition.
MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {
if (auto *LocalResult = getPreviousDefInBlock(MA))
return LocalResult;
DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
return getPreviousDefRecursive(MA->getBlock(), CachedPreviousDef);
}
// This starts at the memory access, and goes backwards in the block to the find
// the previous definition. If the definition is not found in the block of the
// access, it returns nullptr.
MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());
// It's possible there are no defs, or we got handed the first def to start.
if (Defs) {
// If this is a def, we can just use the def iterators.
if (!isa<MemoryUse>(MA)) {
auto Iter = MA->getReverseDefsIterator();
++Iter;
if (Iter != Defs->rend())
return &*Iter;
} else {
// Otherwise, have to walk the all access iterator.
auto End = MSSA->getWritableBlockAccesses(MA->getBlock())->rend();
for (auto &U : make_range(++MA->getReverseIterator(), End))
if (!isa<MemoryUse>(U))
return cast<MemoryAccess>(&U);
// Note that if MA comes before Defs->begin(), we won't hit a def.
return nullptr;
}
}
return nullptr;
}
// This starts at the end of block
MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(
BasicBlock *BB,
DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
auto *Defs = MSSA->getWritableBlockDefs(BB);
if (Defs) {
CachedPreviousDef.insert({BB, &*Defs->rbegin()});
return &*Defs->rbegin();
}
return getPreviousDefRecursive(BB, CachedPreviousDef);
}
// Recurse over a set of phi uses to eliminate the trivial ones
MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {
if (!Phi)
return nullptr;
TrackingVH<MemoryAccess> Res(Phi);
SmallVector<TrackingVH<Value>, 8> Uses;
std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses));
for (auto &U : Uses)
if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U))
tryRemoveTrivialPhi(UsePhi);
return Res;
}
// Eliminate trivial phis
// Phis are trivial if they are defined either by themselves, or all the same
// argument.
// IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
// We recursively try to remove them.
MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi) {
assert(Phi && "Can only remove concrete Phi.");
auto OperRange = Phi->operands();
return tryRemoveTrivialPhi(Phi, OperRange);
}
template <class RangeType>
MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
RangeType &Operands) {
// Bail out on non-opt Phis.
if (NonOptPhis.count(Phi))
return Phi;
// Detect equal or self arguments
MemoryAccess *Same = nullptr;
for (auto &Op : Operands) {
// If the same or self, good so far
if (Op == Phi || Op == Same)
continue;
// not the same, return the phi since it's not eliminatable by us
if (Same)
return Phi;
Same = cast<MemoryAccess>(&*Op);
}
// Never found a non-self reference, the phi is undef
if (Same == nullptr)
return MSSA->getLiveOnEntryDef();
if (Phi) {
Phi->replaceAllUsesWith(Same);
removeMemoryAccess(Phi);
}
// We should only end up recursing in case we replaced something, in which
// case, we may have made other Phis trivial.
return recursePhi(Same);
}
void MemorySSAUpdater::insertUse(MemoryUse *MU, bool RenameUses) {
VisitedBlocks.clear();
InsertedPHIs.clear();
MU->setDefiningAccess(getPreviousDef(MU));
// In cases without unreachable blocks, because uses do not create new
// may-defs, there are only two cases:
// 1. There was a def already below us, and therefore, we should not have
// created a phi node because it was already needed for the def.
//
// 2. There is no def below us, and therefore, there is no extra renaming work
// to do.
// In cases with unreachable blocks, where the unnecessary Phis were
// optimized out, adding the Use may re-insert those Phis. Hence, when
// inserting Uses outside of the MSSA creation process, and new Phis were
// added, rename all uses if we are asked.
if (!RenameUses && !InsertedPHIs.empty()) {
auto *Defs = MSSA->getBlockDefs(MU->getBlock());
(void)Defs;
assert((!Defs || (++Defs->begin() == Defs->end())) &&
"Block may have only a Phi or no defs");
}
if (RenameUses && InsertedPHIs.size()) {
SmallPtrSet<BasicBlock *, 16> Visited;
BasicBlock *StartBlock = MU->getBlock();
if (auto *Defs = MSSA->getWritableBlockDefs(StartBlock)) {
MemoryAccess *FirstDef = &*Defs->begin();
// Convert to incoming value if it's a memorydef. A phi *is* already an
// incoming value.
if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
FirstDef = MD->getDefiningAccess();
MSSA->renamePass(MU->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)
if (MemoryPhi *Phi = cast_or_null<MemoryPhi>(MP))
MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
}
}
// Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
MemoryAccess *NewDef) {
// Replace any operand with us an incoming block with the new defining
// access.
int i = MP->getBasicBlockIndex(BB);
assert(i != -1 && "Should have found the basic block in the phi");
// We can't just compare i against getNumOperands since one is signed and the
// other not. So use it to index into the block iterator.
for (const BasicBlock *BlockBB : llvm::drop_begin(MP->blocks(), i)) {
if (BlockBB != BB)
break;
MP->setIncomingValue(i, NewDef);
++i;
}
}
// A brief description of the algorithm:
// First, we compute what should define the new def, using the SSA
// construction algorithm.
// Then, we update the defs below us (and any new phi nodes) in the graph to
// point to the correct new defs, to ensure we only have one variable, and no
// disconnected stores.
void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
// Don't bother updating dead code.
if (!MSSA->DT->isReachableFromEntry(MD->getBlock())) {
MD->setDefiningAccess(MSSA->getLiveOnEntryDef());
return;
}
VisitedBlocks.clear();
InsertedPHIs.clear();
// See if we had a local def, and if not, go hunting.
MemoryAccess *DefBefore = getPreviousDef(MD);
bool DefBeforeSameBlock = false;
if (DefBefore->getBlock() == MD->getBlock() &&
!(isa<MemoryPhi>(DefBefore) &&
llvm::is_contained(InsertedPHIs, DefBefore)))
DefBeforeSameBlock = true;
// There is a def before us, which means we can replace any store/phi uses
// of that thing with us, since we are in the way of whatever was there
// before.
// We now define that def's memorydefs and memoryphis
if (DefBeforeSameBlock) {
DefBefore->replaceUsesWithIf(MD, [MD](Use &U) {
// Leave the MemoryUses alone.
// Also make sure we skip ourselves to avoid self references.
User *Usr = U.getUser();
return !isa<MemoryUse>(Usr) && Usr != MD;
// Defs are automatically unoptimized when the user is set to MD below,
// because the isOptimized() call will fail to find the same ID.
});
}
// and that def is now our defining access.
MD->setDefiningAccess(DefBefore);
SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());
SmallSet<WeakVH, 8> ExistingPhis;
// Remember the index where we may insert new phis.
unsigned NewPhiIndex = InsertedPHIs.size();
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
// would also have created. If there was no local def before us, we
// performed a global update, and have to search all successors and make
// sure we update the first def in each of them (following all paths until
// we hit the first def along each path). This may also insert phi nodes.
// TODO: There are other cases we can skip this work, such as when we have a
// single successor, and only used a straight line of single pred blocks
// 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.
// If this is the first def in the block and this insert is in an arbitrary
// place, compute IDF and place phis.
SmallPtrSet<BasicBlock *, 2> DefiningBlocks;
// If this is the last Def in the block, we may need additional Phis.
// Compute IDF in all cases, as renaming needs to be done even when MD is
// not the last access, because it can introduce a new access past which a
// previous access was optimized; that access needs to be reoptimized.
DefiningBlocks.insert(MD->getBlock());
for (const auto &VH : InsertedPHIs)
if (const auto *RealPHI = cast_or_null<MemoryPhi>(VH))
DefiningBlocks.insert(RealPHI->getBlock());
ForwardIDFCalculator IDFs(*MSSA->DT);
SmallVector<BasicBlock *, 32> IDFBlocks;
IDFs.setDefiningBlocks(DefiningBlocks);
IDFs.calculate(IDFBlocks);
SmallVector<AssertingVH<MemoryPhi>, 4> NewInsertedPHIs;
for (auto *BBIDF : IDFBlocks) {
auto *MPhi = MSSA->getMemoryAccess(BBIDF);
if (!MPhi) {
MPhi = MSSA->createMemoryPhi(BBIDF);
NewInsertedPHIs.push_back(MPhi);
} else {
ExistingPhis.insert(MPhi);
}
// Add the phis created into the IDF blocks to NonOptPhis, so they are not
// optimized out as trivial by the call to getPreviousDefFromEnd below.
// Once they are complete, all these Phis are added to the FixupList, and
// removed from NonOptPhis inside fixupDefs(). Existing Phis in IDF may
// need fixing as well, and potentially be trivial before this insertion,
// hence add all IDF Phis. See PR43044.
NonOptPhis.insert(MPhi);
}
for (auto &MPhi : NewInsertedPHIs) {
auto *BBIDF = MPhi->getBlock();
for (auto *Pred : predecessors(BBIDF)) {
DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
MPhi->addIncoming(getPreviousDefFromEnd(Pred, CachedPreviousDef), Pred);
}
}
// Re-take the index where we're adding the new phis, because the above call
// to getPreviousDefFromEnd, may have inserted into InsertedPHIs.
NewPhiIndex = InsertedPHIs.size();
for (auto &MPhi : NewInsertedPHIs) {
InsertedPHIs.push_back(&*MPhi);
FixupList.push_back(&*MPhi);
}
FixupList.push_back(MD);
}
// Remember the index where we stopped inserting new phis above, since the
// fixupDefs call in the loop below may insert more, that are already minimal.
unsigned NewPhiIndexEnd = InsertedPHIs.size();
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.begin() + StartingPHISize, InsertedPHIs.end());
}
// Optimize potentially non-minimal phis added in this method.
unsigned NewPhiSize = NewPhiIndexEnd - NewPhiIndex;
if (NewPhiSize)
tryRemoveTrivialPhis(ArrayRef<WeakVH>(&InsertedPHIs[NewPhiIndex], NewPhiSize));
// Now that all fixups are done, rename all uses if we are asked. The defs are
// guaranteed to be in reachable code due to the check at the method entry.
BasicBlock *StartBlock = MD->getBlock();
if (RenameUses) {
SmallPtrSet<BasicBlock *, 16> Visited;
// We are guaranteed there is a def in the block, because we just got it
// handed to us in this function.
MemoryAccess *FirstDef = &*MSSA->getWritableBlockDefs(StartBlock)->begin();
// Convert to incoming value if it's a memorydef. A phi *is* already an
// incoming value.
if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
FirstDef = MD->getDefiningAccess();
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) {
MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);
if (Phi)
MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
}
// Existing Phi blocks may need renaming too, if an access was previously
// optimized and the inserted Defs "covers" the Optimized value.
for (const auto &MP : ExistingPhis) {
MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);
if (Phi)
MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
}
}
}
void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<WeakVH> &Vars) {
SmallPtrSet<const BasicBlock *, 8> Seen;
SmallVector<const BasicBlock *, 16> Worklist;
for (const auto &Var : Vars) {
MemoryAccess *NewDef = dyn_cast_or_null<MemoryAccess>(Var);
if (!NewDef)
continue;
// 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<MemoryPhi>(NewDef))
NonOptPhis.erase(Phi);
// If there is a local def after us, we only have to rename that.
if (++DefIter != Defs->end()) {
cast<MemoryDef>(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())) {
if (auto *MP = MSSA->getMemoryAccess(S))
setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef);
else
Worklist.push_back(S);
}
while (!Worklist.empty()) {
const BasicBlock *FixupBlock = Worklist.pop_back_val();
// 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<MemoryPhi>(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<MemoryDef>(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);
}
}
}
}
}
void MemorySSAUpdater::removeEdge(BasicBlock *From, BasicBlock *To) {
if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
MPhi->unorderedDeleteIncomingBlock(From);
tryRemoveTrivialPhi(MPhi);
}
}
void MemorySSAUpdater::removeDuplicatePhiEdgesBetween(const BasicBlock *From,
const BasicBlock *To) {
if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
bool Found = false;
MPhi->unorderedDeleteIncomingIf([&](const MemoryAccess *, BasicBlock *B) {
if (From != B)
return false;
if (Found)
return true;
Found = true;
return false;
});
tryRemoveTrivialPhi(MPhi);
}
}
/// If all arguments of a MemoryPHI are defined by the same incoming
/// argument, return that argument.
static MemoryAccess *onlySingleValue(MemoryPhi *MP) {
MemoryAccess *MA = nullptr;
for (auto &Arg : MP->operands()) {
if (!MA)
MA = cast<MemoryAccess>(Arg);
else if (MA != Arg)
return nullptr;
}
return MA;
}
static MemoryAccess *getNewDefiningAccessForClone(MemoryAccess *MA,
const ValueToValueMapTy &VMap,
PhiToDefMap &MPhiMap,
bool CloneWasSimplified,
MemorySSA *MSSA) {
MemoryAccess *InsnDefining = MA;
if (MemoryDef *DefMUD = dyn_cast<MemoryDef>(InsnDefining)) {
if (!MSSA->isLiveOnEntryDef(DefMUD)) {
Instruction *DefMUDI = DefMUD->getMemoryInst();
assert(DefMUDI && "Found MemoryUseOrDef with no Instruction.");
if (Instruction *NewDefMUDI =
cast_or_null<Instruction>(VMap.lookup(DefMUDI))) {
InsnDefining = MSSA->getMemoryAccess(NewDefMUDI);
if (!CloneWasSimplified)
assert(InsnDefining && "Defining instruction cannot be nullptr.");
else if (!InsnDefining || isa<MemoryUse>(InsnDefining)) {
// The clone was simplified, it's no longer a MemoryDef, look up.
auto DefIt = DefMUD->getDefsIterator();
// Since simplified clones only occur in single block cloning, a
// previous definition must exist, otherwise NewDefMUDI would not
// have been found in VMap.
assert(DefIt != MSSA->getBlockDefs(DefMUD->getBlock())->begin() &&
"Previous def must exist");
InsnDefining = getNewDefiningAccessForClone(
&*(--DefIt), VMap, MPhiMap, CloneWasSimplified, MSSA);
}
}
}
} else {
MemoryPhi *DefPhi = cast<MemoryPhi>(InsnDefining);
if (MemoryAccess *NewDefPhi = MPhiMap.lookup(DefPhi))
InsnDefining = NewDefPhi;
}
assert(InsnDefining && "Defining instruction cannot be nullptr.");
return InsnDefining;
}
void MemorySSAUpdater::cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
const ValueToValueMapTy &VMap,
PhiToDefMap &MPhiMap,
bool CloneWasSimplified) {
const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
if (!Acc)
return;
for (const MemoryAccess &MA : *Acc) {
if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&MA)) {
Instruction *Insn = MUD->getMemoryInst();
// Entry does not exist if the clone of the block did not clone all
// instructions. This occurs in LoopRotate when cloning instructions
// from the old header to the old preheader. The cloned instruction may
// also be a simplified Value, not an Instruction (see LoopRotate).
// Also in LoopRotate, even when it's an instruction, due to it being
// simplified, it may be a Use rather than a Def, so we cannot use MUD as
// template. Calls coming from updateForClonedBlockIntoPred, ensure this.
if (Instruction *NewInsn =
dyn_cast_or_null<Instruction>(VMap.lookup(Insn))) {
MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(
NewInsn,
getNewDefiningAccessForClone(MUD->getDefiningAccess(), VMap,
MPhiMap, CloneWasSimplified, MSSA),
/*Template=*/CloneWasSimplified ? nullptr : MUD,
/*CreationMustSucceed=*/CloneWasSimplified ? false : true);
if (NewUseOrDef)
MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
}
}
}
}
void MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock(
BasicBlock *Header, BasicBlock *Preheader, BasicBlock *BEBlock) {
auto *MPhi = MSSA->getMemoryAccess(Header);
if (!MPhi)
return;
// Create phi node in the backedge block and populate it with the same
// incoming values as MPhi. Skip incoming values coming from Preheader.
auto *NewMPhi = MSSA->createMemoryPhi(BEBlock);
bool HasUniqueIncomingValue = true;
MemoryAccess *UniqueValue = nullptr;
for (unsigned I = 0, E = MPhi->getNumIncomingValues(); I != E; ++I) {
BasicBlock *IBB = MPhi->getIncomingBlock(I);
MemoryAccess *IV = MPhi->getIncomingValue(I);
if (IBB != Preheader) {
NewMPhi->addIncoming(IV, IBB);
if (HasUniqueIncomingValue) {
if (!UniqueValue)
UniqueValue = IV;
else if (UniqueValue != IV)
HasUniqueIncomingValue = false;
}
}
}
// Update incoming edges into MPhi. Remove all but the incoming edge from
// Preheader. Add an edge from NewMPhi
auto *AccFromPreheader = MPhi->getIncomingValueForBlock(Preheader);
MPhi->setIncomingValue(0, AccFromPreheader);
MPhi->setIncomingBlock(0, Preheader);
for (unsigned I = MPhi->getNumIncomingValues() - 1; I >= 1; --I)
MPhi->unorderedDeleteIncoming(I);
MPhi->addIncoming(NewMPhi, BEBlock);
// If NewMPhi is a trivial phi, remove it. Its use in the header MPhi will be
// replaced with the unique value.
tryRemoveTrivialPhi(NewMPhi);
}
void MemorySSAUpdater::updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
ArrayRef<BasicBlock *> ExitBlocks,
const ValueToValueMapTy &VMap,
bool IgnoreIncomingWithNoClones) {
PhiToDefMap MPhiMap;
auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) {
assert(Phi && NewPhi && "Invalid Phi nodes.");
BasicBlock *NewPhiBB = NewPhi->getBlock();
SmallPtrSet<BasicBlock *, 4> NewPhiBBPreds(pred_begin(NewPhiBB),
pred_end(NewPhiBB));
for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; ++It) {
MemoryAccess *IncomingAccess = Phi->getIncomingValue(It);
BasicBlock *IncBB = Phi->getIncomingBlock(It);
if (BasicBlock *NewIncBB = cast_or_null<BasicBlock>(VMap.lookup(IncBB)))
IncBB = NewIncBB;
else if (IgnoreIncomingWithNoClones)
continue;
// Now we have IncBB, and will need to add incoming from it to NewPhi.
// If IncBB is not a predecessor of NewPhiBB, then do not add it.
// NewPhiBB was cloned without that edge.
if (!NewPhiBBPreds.count(IncBB))
continue;
// Determine incoming value and add it as incoming from IncBB.
if (MemoryUseOrDef *IncMUD = dyn_cast<MemoryUseOrDef>(IncomingAccess)) {
if (!MSSA->isLiveOnEntryDef(IncMUD)) {
Instruction *IncI = IncMUD->getMemoryInst();
assert(IncI && "Found MemoryUseOrDef with no Instruction.");
if (Instruction *NewIncI =
cast_or_null<Instruction>(VMap.lookup(IncI))) {
IncMUD = MSSA->getMemoryAccess(NewIncI);
assert(IncMUD &&
"MemoryUseOrDef cannot be null, all preds processed.");
}
}
NewPhi->addIncoming(IncMUD, IncBB);
} else {
MemoryPhi *IncPhi = cast<MemoryPhi>(IncomingAccess);
if (MemoryAccess *NewDefPhi = MPhiMap.lookup(IncPhi))
NewPhi->addIncoming(NewDefPhi, IncBB);
else
NewPhi->addIncoming(IncPhi, IncBB);
}
}
if (auto *SingleAccess = onlySingleValue(NewPhi)) {
MPhiMap[Phi] = SingleAccess;
removeMemoryAccess(NewPhi);
}
};
auto ProcessBlock = [&](BasicBlock *BB) {
BasicBlock *NewBlock = cast_or_null<BasicBlock>(VMap.lookup(BB));
if (!NewBlock)
return;
assert(!MSSA->getWritableBlockAccesses(NewBlock) &&
"Cloned block should have no accesses");
// Add MemoryPhi.
if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) {
MemoryPhi *NewPhi = MSSA->createMemoryPhi(NewBlock);
MPhiMap[MPhi] = NewPhi;
}
// Update Uses and Defs.
cloneUsesAndDefs(BB, NewBlock, VMap, MPhiMap);
};
for (auto *BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
ProcessBlock(BB);
for (auto *BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
if (MemoryAccess *NewPhi = MPhiMap.lookup(MPhi))
FixPhiIncomingValues(MPhi, cast<MemoryPhi>(NewPhi));
}
void MemorySSAUpdater::updateForClonedBlockIntoPred(
BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM) {
// All defs/phis from outside BB that are used in BB, are valid uses in P1.
// Since those defs/phis must have dominated BB, and also dominate P1.
// Defs from BB being used in BB will be replaced with the cloned defs from
// VM. The uses of BB's Phi (if it exists) in BB will be replaced by the
// incoming def into the Phi from P1.
// Instructions cloned into the predecessor are in practice sometimes
// simplified, so disable the use of the template, and create an access from
// scratch.
PhiToDefMap MPhiMap;
if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
MPhiMap[MPhi] = MPhi->getIncomingValueForBlock(P1);
cloneUsesAndDefs(BB, P1, VM, MPhiMap, /*CloneWasSimplified=*/true);
}
template <typename Iter>
void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop(
ArrayRef<BasicBlock *> ExitBlocks, Iter ValuesBegin, Iter ValuesEnd,
DominatorTree &DT) {
SmallVector<CFGUpdate, 4> Updates;
// Update/insert phis in all successors of exit blocks.
for (auto *Exit : ExitBlocks)
for (const ValueToValueMapTy *VMap : make_range(ValuesBegin, ValuesEnd))
if (BasicBlock *NewExit = cast_or_null<BasicBlock>(VMap->lookup(Exit))) {
BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
Updates.push_back({DT.Insert, NewExit, ExitSucc});
}
applyInsertUpdates(Updates, DT);
}
void MemorySSAUpdater::updateExitBlocksForClonedLoop(
ArrayRef<BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap,
DominatorTree &DT) {
const ValueToValueMapTy *const Arr[] = {&VMap};
privateUpdateExitBlocksForClonedLoop(ExitBlocks, std::begin(Arr),
std::end(Arr), DT);
}
void MemorySSAUpdater::updateExitBlocksForClonedLoop(
ArrayRef<BasicBlock *> ExitBlocks,
ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT) {
auto GetPtr = [&](const std::unique_ptr<ValueToValueMapTy> &I) {
return I.get();
};
using MappedIteratorType =
mapped_iterator<const std::unique_ptr<ValueToValueMapTy> *,
decltype(GetPtr)>;
auto MapBegin = MappedIteratorType(VMaps.begin(), GetPtr);
auto MapEnd = MappedIteratorType(VMaps.end(), GetPtr);
privateUpdateExitBlocksForClonedLoop(ExitBlocks, MapBegin, MapEnd, DT);
}
void MemorySSAUpdater::applyUpdates(ArrayRef<CFGUpdate> Updates,
DominatorTree &DT, bool UpdateDT) {
SmallVector<CFGUpdate, 4> DeleteUpdates;
SmallVector<CFGUpdate, 4> RevDeleteUpdates;
SmallVector<CFGUpdate, 4> InsertUpdates;
for (const auto &Update : Updates) {
if (Update.getKind() == DT.Insert)
InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
else {
DeleteUpdates.push_back({DT.Delete, Update.getFrom(), Update.getTo()});
RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
}
}
if (!DeleteUpdates.empty()) {
if (!InsertUpdates.empty()) {
if (!UpdateDT) {
SmallVector<CFGUpdate, 0> Empty;
// Deletes are reversed applied, because this CFGView is pretending the
// deletes did not happen yet, hence the edges still exist.
DT.applyUpdates(Empty, RevDeleteUpdates);
} else {
// Apply all updates, with the RevDeleteUpdates as PostCFGView.
DT.applyUpdates(Updates, RevDeleteUpdates);
}
// Note: the MSSA update below doesn't distinguish between a GD with
// (RevDelete,false) and (Delete, true), but this matters for the DT
// updates above; for "children" purposes they are equivalent; but the
// updates themselves convey the desired update, used inside DT only.
GraphDiff<BasicBlock *> GD(RevDeleteUpdates);
applyInsertUpdates(InsertUpdates, DT, &GD);
// Update DT to redelete edges; this matches the real CFG so we can
// perform the standard update without a postview of the CFG.
DT.applyUpdates(DeleteUpdates);
} else {
if (UpdateDT)
DT.applyUpdates(DeleteUpdates);
}
} else {
if (UpdateDT)
DT.applyUpdates(Updates);
GraphDiff<BasicBlock *> GD;
applyInsertUpdates(InsertUpdates, DT, &GD);
}
// Update for deleted edges
for (auto &Update : DeleteUpdates)
removeEdge(Update.getFrom(), Update.getTo());
}
void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
DominatorTree &DT) {
GraphDiff<BasicBlock *> GD;
applyInsertUpdates(Updates, DT, &GD);
}
void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
DominatorTree &DT,
const GraphDiff<BasicBlock *> *GD) {
// Get recursive last Def, assuming well formed MSSA and updated DT.
auto GetLastDef = [&](BasicBlock *BB) -> MemoryAccess * {
while (true) {
MemorySSA::DefsList *Defs = MSSA->getWritableBlockDefs(BB);
// Return last Def or Phi in BB, if it exists.
if (Defs)
return &*(--Defs->end());
// Check number of predecessors, we only care if there's more than one.
unsigned Count = 0;
BasicBlock *Pred = nullptr;
for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BB)) {
Pred = Pi;
Count++;
if (Count == 2)
break;
}
// If BB has multiple predecessors, get last definition from IDom.
if (Count != 1) {
// [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its
// DT is invalidated. Return LoE as its last def. This will be added to
// MemoryPhi node, and later deleted when the block is deleted.
if (!DT.getNode(BB))
return MSSA->getLiveOnEntryDef();
if (auto *IDom = DT.getNode(BB)->getIDom())
if (IDom->getBlock() != BB) {
BB = IDom->getBlock();
continue;
}
return MSSA->getLiveOnEntryDef();
} else {
// Single predecessor, BB cannot be dead. GetLastDef of Pred.
assert(Count == 1 && Pred && "Single predecessor expected.");
// BB can be unreachable though, return LoE if that is the case.
if (!DT.getNode(BB))
return MSSA->getLiveOnEntryDef();
BB = Pred;
}
};
llvm_unreachable("Unable to get last definition.");
};
// Get nearest IDom given a set of blocks.
// TODO: this can be optimized by starting the search at the node with the
// lowest level (highest in the tree).
auto FindNearestCommonDominator =
[&](const SmallSetVector<BasicBlock *, 2> &BBSet) -> BasicBlock * {
BasicBlock *PrevIDom = *BBSet.begin();
for (auto *BB : BBSet)
PrevIDom = DT.findNearestCommonDominator(PrevIDom, BB);
return PrevIDom;
};
// Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not
// include CurrIDom.
auto GetNoLongerDomBlocks =
[&](BasicBlock *PrevIDom, BasicBlock *CurrIDom,
SmallVectorImpl<BasicBlock *> &BlocksPrevDom) {
if (PrevIDom == CurrIDom)
return;
BlocksPrevDom.push_back(PrevIDom);
BasicBlock *NextIDom = PrevIDom;
while (BasicBlock *UpIDom =
DT.getNode(NextIDom)->getIDom()->getBlock()) {
if (UpIDom == CurrIDom)
break;
BlocksPrevDom.push_back(UpIDom);
NextIDom = UpIDom;
}
};
// Map a BB to its predecessors: added + previously existing. To get a
// deterministic order, store predecessors as SetVectors. The order in each
// will be defined by the order in Updates (fixed) and the order given by
// children<> (also fixed). Since we further iterate over these ordered sets,
// we lose the information of multiple edges possibly existing between two
// blocks, so we'll keep and EdgeCount map for that.
// An alternate implementation could keep unordered set for the predecessors,
// traverse either Updates or children<> each time to get the deterministic
// order, and drop the usage of EdgeCount. This alternate approach would still
// require querying the maps for each predecessor, and children<> call has
// additional computation inside for creating the snapshot-graph predecessors.
// As such, we favor using a little additional storage and less compute time.
// This decision can be revisited if we find the alternative more favorable.
struct PredInfo {
SmallSetVector<BasicBlock *, 2> Added;
SmallSetVector<BasicBlock *, 2> Prev;
};
SmallDenseMap<BasicBlock *, PredInfo> PredMap;
for (const auto &Edge : Updates) {
BasicBlock *BB = Edge.getTo();
auto &AddedBlockSet = PredMap[BB].Added;
AddedBlockSet.insert(Edge.getFrom());
}
// Store all existing predecessor for each BB, at least one must exist.
SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>, int> EdgeCountMap;
SmallPtrSet<BasicBlock *, 2> NewBlocks;
for (auto &BBPredPair : PredMap) {
auto *BB = BBPredPair.first;
const auto &AddedBlockSet = BBPredPair.second.Added;
auto &PrevBlockSet = BBPredPair.second.Prev;
for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BB)) {
if (!AddedBlockSet.count(Pi))
PrevBlockSet.insert(Pi);
EdgeCountMap[{Pi, BB}]++;
}
if (PrevBlockSet.empty()) {
assert(pred_size(BB) == AddedBlockSet.size() && "Duplicate edges added.");
LLVM_DEBUG(
dbgs()
<< "Adding a predecessor to a block with no predecessors. "
"This must be an edge added to a new, likely cloned, block. "
"Its memory accesses must be already correct, assuming completed "
"via the updateExitBlocksForClonedLoop API. "
"Assert a single such edge is added so no phi addition or "
"additional processing is required.\n");
assert(AddedBlockSet.size() == 1 &&
"Can only handle adding one predecessor to a new block.");
// Need to remove new blocks from PredMap. Remove below to not invalidate
// iterator here.
NewBlocks.insert(BB);
}
}
// Nothing to process for new/cloned blocks.
for (auto *BB : NewBlocks)
PredMap.erase(BB);
SmallVector<BasicBlock *, 16> BlocksWithDefsToReplace;
SmallVector<WeakVH, 8> InsertedPhis;
// First create MemoryPhis in all blocks that don't have one. Create in the
// order found in Updates, not in PredMap, to get deterministic numbering.
for (const auto &Edge : Updates) {
BasicBlock *BB = Edge.getTo();
if (PredMap.count(BB) && !MSSA->getMemoryAccess(BB))
InsertedPhis.push_back(MSSA->createMemoryPhi(BB));
}
// Now we'll fill in the MemoryPhis with the right incoming values.
for (auto &BBPredPair : PredMap) {
auto *BB = BBPredPair.first;
const auto &PrevBlockSet = BBPredPair.second.Prev;
const auto &AddedBlockSet = BBPredPair.second.Added;
assert(!PrevBlockSet.empty() &&
"At least one previous predecessor must exist.");
// TODO: if this becomes a bottleneck, we can save on GetLastDef calls by
// keeping this map before the loop. We can reuse already populated entries
// if an edge is added from the same predecessor to two different blocks,
// and this does happen in rotate. Note that the map needs to be updated
// when deleting non-necessary phis below, if the phi is in the map by
// replacing the value with DefP1.
SmallDenseMap<BasicBlock *, MemoryAccess *> LastDefAddedPred;
for (auto *AddedPred : AddedBlockSet) {
auto *DefPn = GetLastDef(AddedPred);
assert(DefPn != nullptr && "Unable to find last definition.");
LastDefAddedPred[AddedPred] = DefPn;
}
MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB);
// If Phi is not empty, add an incoming edge from each added pred. Must
// still compute blocks with defs to replace for this block below.
if (NewPhi->getNumOperands()) {
for (auto *Pred : AddedBlockSet) {
auto *LastDefForPred = LastDefAddedPred[Pred];
for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
NewPhi->addIncoming(LastDefForPred, Pred);
}
} else {
// Pick any existing predecessor and get its definition. All other
// existing predecessors should have the same one, since no phi existed.
auto *P1 = *PrevBlockSet.begin();
MemoryAccess *DefP1 = GetLastDef(P1);
// Check DefP1 against all Defs in LastDefPredPair. If all the same,
// nothing to add.
bool InsertPhi = false;
for (auto LastDefPredPair : LastDefAddedPred)
if (DefP1 != LastDefPredPair.second) {
InsertPhi = true;
break;
}
if (!InsertPhi) {
// Since NewPhi may be used in other newly added Phis, replace all uses
// of NewPhi with the definition coming from all predecessors (DefP1),
// before deleting it.
NewPhi->replaceAllUsesWith(DefP1);
removeMemoryAccess(NewPhi);
continue;
}
// Update Phi with new values for new predecessors and old value for all
// other predecessors. Since AddedBlockSet and PrevBlockSet are ordered
// sets, the order of entries in NewPhi is deterministic.
for (auto *Pred : AddedBlockSet) {
auto *LastDefForPred = LastDefAddedPred[Pred];
for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
NewPhi->addIncoming(LastDefForPred, Pred);
}
for (auto *Pred : PrevBlockSet)
for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
NewPhi->addIncoming(DefP1, Pred);
}
// Get all blocks that used to dominate BB and no longer do after adding
// AddedBlockSet, where PrevBlockSet are the previously known predecessors.
assert(DT.getNode(BB)->getIDom() && "BB does not have valid idom");
BasicBlock *PrevIDom = FindNearestCommonDominator(PrevBlockSet);
assert(PrevIDom && "Previous IDom should exists");
BasicBlock *NewIDom = DT.getNode(BB)->getIDom()->getBlock();
assert(NewIDom && "BB should have a new valid idom");
assert(DT.dominates(NewIDom, PrevIDom) &&
"New idom should dominate old idom");
GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);
}
tryRemoveTrivialPhis(InsertedPhis);
// Create the set of blocks that now have a definition. We'll use this to
// compute IDF and add Phis there next.
SmallVector<BasicBlock *, 8> BlocksToProcess;
for (auto &VH : InsertedPhis)
if (auto *MPhi = cast_or_null<MemoryPhi>(VH))
BlocksToProcess.push_back(MPhi->getBlock());
// Compute IDF and add Phis in all IDF blocks that do not have one.
SmallVector<BasicBlock *, 32> IDFBlocks;
if (!BlocksToProcess.empty()) {
ForwardIDFCalculator IDFs(DT, GD);
SmallPtrSet<BasicBlock *, 16> DefiningBlocks(BlocksToProcess.begin(),
BlocksToProcess.end());
IDFs.setDefiningBlocks(DefiningBlocks);
IDFs.calculate(IDFBlocks);
SmallSetVector<MemoryPhi *, 4> PhisToFill;
// First create all needed Phis.
for (auto *BBIDF : IDFBlocks)
if (!MSSA->getMemoryAccess(BBIDF)) {
auto *IDFPhi = MSSA->createMemoryPhi(BBIDF);
InsertedPhis.push_back(IDFPhi);
PhisToFill.insert(IDFPhi);
}
// Then update or insert their correct incoming values.
for (auto *BBIDF : IDFBlocks) {
auto *IDFPhi = MSSA->getMemoryAccess(BBIDF);
assert(IDFPhi && "Phi must exist");
if (!PhisToFill.count(IDFPhi)) {
// Update existing Phi.
// FIXME: some updates may be redundant, try to optimize and skip some.
for (unsigned I = 0, E = IDFPhi->getNumIncomingValues(); I < E; ++I)
IDFPhi->setIncomingValue(I, GetLastDef(IDFPhi->getIncomingBlock(I)));
} else {
for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BBIDF))
IDFPhi->addIncoming(GetLastDef(Pi), Pi);
}
}
}
// Now for all defs in BlocksWithDefsToReplace, if there are uses they no
// longer dominate, replace those with the closest dominating def.
// This will also update optimized accesses, as they're also uses.
for (auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) {
if (auto DefsList = MSSA->getWritableBlockDefs(BlockWithDefsToReplace)) {
for (auto &DefToReplaceUses : *DefsList) {
BasicBlock *DominatingBlock = DefToReplaceUses.getBlock();
for (Use &U : llvm::make_early_inc_range(DefToReplaceUses.uses())) {
MemoryAccess *Usr = cast<MemoryAccess>(U.getUser());
if (MemoryPhi *UsrPhi = dyn_cast<MemoryPhi>(Usr)) {
BasicBlock *DominatedBlock = UsrPhi->getIncomingBlock(U);
if (!DT.dominates(DominatingBlock, DominatedBlock))
U.set(GetLastDef(DominatedBlock));
} else {
BasicBlock *DominatedBlock = Usr->getBlock();
if (!DT.dominates(DominatingBlock, DominatedBlock)) {
if (auto *DomBlPhi = MSSA->getMemoryAccess(DominatedBlock))
U.set(DomBlPhi);
else {
auto *IDom = DT.getNode(DominatedBlock)->getIDom();
assert(IDom && "Block must have a valid IDom.");
U.set(GetLastDef(IDom->getBlock()));
}
cast<MemoryUseOrDef>(Usr)->resetOptimized();
}
}
}
}
}
}
tryRemoveTrivialPhis(InsertedPhis);
}
// Move What before Where in the MemorySSA IR.
template <class WhereType>
void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
WhereType Where) {
// Mark MemoryPhi users of What not to be optimized.
for (auto *U : What->users())
if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))
NonOptPhis.insert(PhiUser);
// Replace all our users with our defining access.
What->replaceAllUsesWith(What->getDefiningAccess());
// Let MemorySSA take care of moving it around in the lists.
MSSA->moveTo(What, BB, Where);
// Now reinsert it into the IR and do whatever fixups needed.
if (auto *MD = dyn_cast<MemoryDef>(What))
insertDef(MD, /*RenameUses=*/true);
else
insertUse(cast<MemoryUse>(What), /*RenameUses=*/true);
// Clear dangling pointers. We added all MemoryPhi users, but not all
// of them are removed by fixupDefs().
NonOptPhis.clear();
}
// Move What before Where in the MemorySSA IR.
void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
moveTo(What, Where->getBlock(), Where->getIterator());
}
// Move What after Where in the MemorySSA IR.
void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
moveTo(What, Where->getBlock(), ++Where->getIterator());
}
void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
MemorySSA::InsertionPlace Where) {
if (Where != MemorySSA::InsertionPlace::BeforeTerminator)
return moveTo(What, BB, Where);
if (auto *Where = MSSA->getMemoryAccess(BB->getTerminator()))
return moveBefore(What, Where);
else
return moveTo(What, BB, MemorySSA::InsertionPlace::End);
}
// All accesses in To used to be in From. Move to end and update access lists.
void MemorySSAUpdater::moveAllAccesses(BasicBlock *From, BasicBlock *To,
Instruction *Start) {
MemorySSA::AccessList *Accs = MSSA->getWritableBlockAccesses(From);
if (!Accs)
return;
assert(Start->getParent() == To && "Incorrect Start instruction");
MemoryAccess *FirstInNew = nullptr;
for (Instruction &I : make_range(Start->getIterator(), To->end()))
if ((FirstInNew = MSSA->getMemoryAccess(&I)))
break;
if (FirstInNew) {
auto *MUD = cast<MemoryUseOrDef>(FirstInNew);
do {
auto NextIt = ++MUD->getIterator();
MemoryUseOrDef *NextMUD = (!Accs || NextIt == Accs->end())
? nullptr
: cast<MemoryUseOrDef>(&*NextIt);
MSSA->moveTo(MUD, To, MemorySSA::End);
// Moving MUD from Accs in the moveTo above, may delete Accs, so we need
// to retrieve it again.
Accs = MSSA->getWritableBlockAccesses(From);
MUD = NextMUD;
} while (MUD);
}
// If all accesses were moved and only a trivial Phi remains, we try to remove
// that Phi. This is needed when From is going to be deleted.
auto *Defs = MSSA->getWritableBlockDefs(From);
if (Defs && !Defs->empty())
if (auto *Phi = dyn_cast<MemoryPhi>(&*Defs->begin()))
tryRemoveTrivialPhi(Phi);
}
void MemorySSAUpdater::moveAllAfterSpliceBlocks(BasicBlock *From,
BasicBlock *To,
Instruction *Start) {
assert(MSSA->getBlockAccesses(To) == nullptr &&
"To block is expected to be free of MemoryAccesses.");
moveAllAccesses(From, To, Start);
for (BasicBlock *Succ : successors(To))
if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
}
void MemorySSAUpdater::moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
Instruction *Start) {
assert(From->getUniquePredecessor() == To &&
"From block is expected to have a single predecessor (To).");
moveAllAccesses(From, To, Start);
for (BasicBlock *Succ : successors(From))
if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
}
void MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(
BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
bool IdenticalEdgesWereMerged) {
assert(!MSSA->getWritableBlockAccesses(New) &&
"Access list should be null for a new block.");
MemoryPhi *Phi = MSSA->getMemoryAccess(Old);
if (!Phi)
return;
if (Old->hasNPredecessors(1)) {
assert(pred_size(New) == Preds.size() &&
"Should have moved all predecessors.");
MSSA->moveTo(Phi, New, MemorySSA::Beginning);
} else {
assert(!Preds.empty() && "Must be moving at least one predecessor to the "
"new immediate predecessor.");
MemoryPhi *NewPhi = MSSA->createMemoryPhi(New);
SmallPtrSet<BasicBlock *, 16> PredsSet(Preds.begin(), Preds.end());
// Currently only support the case of removing a single incoming edge when
// identical edges were not merged.
if (!IdenticalEdgesWereMerged)
assert(PredsSet.size() == Preds.size() &&
"If identical edges were not merged, we cannot have duplicate "
"blocks in the predecessors");
Phi->unorderedDeleteIncomingIf([&](MemoryAccess *MA, BasicBlock *B) {
if (PredsSet.count(B)) {
NewPhi->addIncoming(MA, B);
if (!IdenticalEdgesWereMerged)
PredsSet.erase(B);
return true;
}
return false;
});
Phi->addIncoming(NewPhi, New);
tryRemoveTrivialPhi(NewPhi);
}
}
void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA, bool OptimizePhis) {
assert(!MSSA->isLiveOnEntryDef(MA) &&
"Trying to remove the live on entry def");
// We can only delete phi nodes if they have no uses, or we can replace all
// uses with a single definition.
MemoryAccess *NewDefTarget = nullptr;
if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
// Note that it is sufficient to know that all edges of the phi node have
// the same argument. If they do, by the definition of dominance frontiers
// (which we used to place this phi), that argument must dominate this phi,
// and thus, must dominate the phi's uses, and so we will not hit the assert
// below.
NewDefTarget = onlySingleValue(MP);
assert((NewDefTarget || MP->use_empty()) &&
"We can't delete this memory phi");
} else {
NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
}
SmallSetVector<MemoryPhi *, 4> PhisToCheck;
// Re-point the uses at our defining access
if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
// Reset optimized on users of this store, and reset the uses.
// A few notes:
// 1. This is a slightly modified version of RAUW to avoid walking the
// uses twice here.
// 2. If we wanted to be complete, we would have to reset the optimized
// flags on users of phi nodes if doing the below makes a phi node have all
// the same arguments. Instead, we prefer users to removeMemoryAccess those
// phi nodes, because doing it here would be N^3.
if (MA->hasValueHandle())
ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
// Note: We assume MemorySSA is not used in metadata since it's not really
// part of the IR.
assert(NewDefTarget != MA && "Going into an infinite loop");
while (!MA->use_empty()) {
Use &U = *MA->use_begin();
if (auto *MUD = dyn_cast<MemoryUseOrDef>(U.getUser()))
MUD->resetOptimized();
if (OptimizePhis)
if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U.getUser()))
PhisToCheck.insert(MP);
U.set(NewDefTarget);
}
}
// The call below to erase will destroy MA, so we can't change the order we
// are doing things here
MSSA->removeFromLookups(MA);
MSSA->removeFromLists(MA);
// Optionally optimize Phi uses. This will recursively remove trivial phis.
if (!PhisToCheck.empty()) {
SmallVector<WeakVH, 16> PhisToOptimize{PhisToCheck.begin(),
PhisToCheck.end()};
PhisToCheck.clear();
unsigned PhisSize = PhisToOptimize.size();
while (PhisSize-- > 0)
if (MemoryPhi *MP =
cast_or_null<MemoryPhi>(PhisToOptimize.pop_back_val()))
tryRemoveTrivialPhi(MP);
}
}
void MemorySSAUpdater::removeBlocks(
const SmallSetVector<BasicBlock *, 8> &DeadBlocks) {
// First delete all uses of BB in MemoryPhis.
for (BasicBlock *BB : DeadBlocks) {
Instruction *TI = BB->getTerminator();
assert(TI && "Basic block expected to have a terminator instruction");
for (BasicBlock *Succ : successors(TI))
if (!DeadBlocks.count(Succ))
if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {
MP->unorderedDeleteIncomingBlock(BB);
tryRemoveTrivialPhi(MP);
}
// Drop all references of all accesses in BB
if (MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB))
for (MemoryAccess &MA : *Acc)
MA.dropAllReferences();
}
// Next, delete all memory accesses in each block
for (BasicBlock *BB : DeadBlocks) {
MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB);
if (!Acc)
continue;
for (MemoryAccess &MA : llvm::make_early_inc_range(*Acc)) {
MSSA->removeFromLookups(&MA);
MSSA->removeFromLists(&MA);
}
}
}
void MemorySSAUpdater::tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs) {
for (const auto &VH : UpdatedPHIs)
if (auto *MPhi = cast_or_null<MemoryPhi>(VH))
tryRemoveTrivialPhi(MPhi);
}
void MemorySSAUpdater::changeToUnreachable(const Instruction *I) {
const BasicBlock *BB = I->getParent();
// Remove memory accesses in BB for I and all following instructions.
auto BBI = I->getIterator(), BBE = BB->end();
// FIXME: If this becomes too expensive, iterate until the first instruction
// with a memory access, then iterate over MemoryAccesses.
while (BBI != BBE)
removeMemoryAccess(&*(BBI++));
// Update phis in BB's successors to remove BB.
SmallVector<WeakVH, 16> UpdatedPHIs;
for (const BasicBlock *Successor : successors(BB)) {
removeDuplicatePhiEdgesBetween(BB, Successor);
if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Successor)) {
MPhi->unorderedDeleteIncomingBlock(BB);
UpdatedPHIs.push_back(MPhi);
}
}
// Optimize trivial phis.
tryRemoveTrivialPhis(UpdatedPHIs);
}
MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
MemorySSA::InsertionPlace Point) {
MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
return NewAccess;
}
MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore(
Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
assert(I->getParent() == InsertPt->getBlock() &&
"New and old access must be in the same block");
MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
InsertPt->getIterator());
return NewAccess;
}
MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(
Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
assert(I->getParent() == InsertPt->getBlock() &&
"New and old access must be in the same block");
MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
++InsertPt->getIterator());
return NewAccess;
}
