1439 lines · cpp
1//===-- MemorySSAUpdater.cpp - Memory SSA Updater--------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------===//8//9// This file implements the MemorySSAUpdater class.10//11//===----------------------------------------------------------------===//12#include "llvm/Analysis/MemorySSAUpdater.h"13#include "llvm/ADT/STLExtras.h"14#include "llvm/ADT/SetVector.h"15#include "llvm/ADT/SmallPtrSet.h"16#include "llvm/Analysis/IteratedDominanceFrontier.h"17#include "llvm/Analysis/LoopIterator.h"18#include "llvm/Analysis/MemorySSA.h"19#include "llvm/IR/BasicBlock.h"20#include "llvm/IR/Dominators.h"21#include "llvm/Support/Debug.h"22#include <algorithm>23 24#define DEBUG_TYPE "memoryssa"25using namespace llvm;26 27// This is the marker algorithm from "Simple and Efficient Construction of28// Static Single Assignment Form"29// The simple, non-marker algorithm places phi nodes at any join30// Here, we place markers, and only place phi nodes if they end up necessary.31// They are only necessary if they break a cycle (IE we recursively visit32// ourselves again), or we discover, while getting the value of the operands,33// that there are two or more definitions needing to be merged.34// This still will leave non-minimal form in the case of irreducible control35// flow, where phi nodes may be in cycles with themselves, but unnecessary.36MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(37 BasicBlock *BB,38 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {39 // First, do a cache lookup. Without this cache, certain CFG structures40 // (like a series of if statements) take exponential time to visit.41 auto Cached = CachedPreviousDef.find(BB);42 if (Cached != CachedPreviousDef.end())43 return Cached->second;44 45 // If this method is called from an unreachable block, return LoE.46 if (!MSSA->DT->isReachableFromEntry(BB))47 return MSSA->getLiveOnEntryDef();48 49 if (BasicBlock *Pred = BB->getUniquePredecessor()) {50 VisitedBlocks.insert(BB);51 // Single predecessor case, just recurse, we can only have one definition.52 MemoryAccess *Result = getPreviousDefFromEnd(Pred, CachedPreviousDef);53 CachedPreviousDef.insert({BB, Result});54 return Result;55 }56 57 if (VisitedBlocks.count(BB)) {58 // We hit our node again, meaning we had a cycle, we must insert a phi59 // node to break it so we have an operand. The only case this will60 // insert useless phis is if we have irreducible control flow.61 MemoryAccess *Result = MSSA->createMemoryPhi(BB);62 CachedPreviousDef.insert({BB, Result});63 return Result;64 }65 66 if (VisitedBlocks.insert(BB).second) {67 // Mark us visited so we can detect a cycle68 SmallVector<TrackingVH<MemoryAccess>, 8> PhiOps;69 70 // Recurse to get the values in our predecessors for placement of a71 // potential phi node. This will insert phi nodes if we cycle in order to72 // break the cycle and have an operand.73 bool UniqueIncomingAccess = true;74 MemoryAccess *SingleAccess = nullptr;75 for (auto *Pred : predecessors(BB)) {76 if (MSSA->DT->isReachableFromEntry(Pred)) {77 auto *IncomingAccess = getPreviousDefFromEnd(Pred, CachedPreviousDef);78 if (!SingleAccess)79 SingleAccess = IncomingAccess;80 else if (IncomingAccess != SingleAccess)81 UniqueIncomingAccess = false;82 PhiOps.push_back(IncomingAccess);83 } else84 PhiOps.push_back(MSSA->getLiveOnEntryDef());85 }86 87 // Now try to simplify the ops to avoid placing a phi.88 // This may return null if we never created a phi yet, that's okay89 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));90 91 // See if we can avoid the phi by simplifying it.92 auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);93 // If we couldn't simplify, we may have to create a phi94 if (Result == Phi && UniqueIncomingAccess && SingleAccess) {95 // A concrete Phi only exists if we created an empty one to break a cycle.96 if (Phi) {97 assert(Phi->operands().empty() && "Expected empty Phi");98 Phi->replaceAllUsesWith(SingleAccess);99 removeMemoryAccess(Phi);100 }101 Result = SingleAccess;102 } else if (Result == Phi && !(UniqueIncomingAccess && SingleAccess)) {103 if (!Phi)104 Phi = MSSA->createMemoryPhi(BB);105 106 // See if the existing phi operands match what we need.107 // Unlike normal SSA, we only allow one phi node per block, so we can't just108 // create a new one.109 if (Phi->getNumOperands() != 0) {110 // FIXME: Figure out whether this is dead code and if so remove it.111 if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {112 // These will have been filled in by the recursive read we did above.113 llvm::copy(PhiOps, Phi->op_begin());114 std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());115 }116 } else {117 unsigned i = 0;118 for (auto *Pred : predecessors(BB))119 Phi->addIncoming(&*PhiOps[i++], Pred);120 InsertedPHIs.push_back(Phi);121 }122 Result = Phi;123 }124 125 // Set ourselves up for the next variable by resetting visited state.126 VisitedBlocks.erase(BB);127 CachedPreviousDef.insert({BB, Result});128 return Result;129 }130 llvm_unreachable("Should have hit one of the three cases above");131}132 133// This starts at the memory access, and goes backwards in the block to find the134// previous definition. If a definition is not found the block of the access,135// it continues globally, creating phi nodes to ensure we have a single136// definition.137MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {138 if (auto *LocalResult = getPreviousDefInBlock(MA))139 return LocalResult;140 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;141 return getPreviousDefRecursive(MA->getBlock(), CachedPreviousDef);142}143 144// This starts at the memory access, and goes backwards in the block to the find145// the previous definition. If the definition is not found in the block of the146// access, it returns nullptr.147MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {148 auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());149 150 // It's possible there are no defs, or we got handed the first def to start.151 if (Defs) {152 // If this is a def, we can just use the def iterators.153 if (!isa<MemoryUse>(MA)) {154 auto Iter = MA->getReverseDefsIterator();155 ++Iter;156 if (Iter != Defs->rend())157 return &*Iter;158 } else {159 // Otherwise, have to walk the all access iterator.160 auto End = MSSA->getWritableBlockAccesses(MA->getBlock())->rend();161 for (auto &U : make_range(++MA->getReverseIterator(), End))162 if (!isa<MemoryUse>(U))163 return cast<MemoryAccess>(&U);164 // Note that if MA comes before Defs->begin(), we won't hit a def.165 return nullptr;166 }167 }168 return nullptr;169}170 171// This starts at the end of block172MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(173 BasicBlock *BB,174 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {175 auto *Defs = MSSA->getWritableBlockDefs(BB);176 177 if (Defs) {178 CachedPreviousDef.insert({BB, &*Defs->rbegin()});179 return &*Defs->rbegin();180 }181 182 return getPreviousDefRecursive(BB, CachedPreviousDef);183}184// Recurse over a set of phi uses to eliminate the trivial ones185MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {186 if (!Phi)187 return nullptr;188 TrackingVH<MemoryAccess> Res(Phi);189 SmallVector<TrackingVH<Value>, 8> Uses;190 std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses));191 for (auto &U : Uses)192 if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U))193 tryRemoveTrivialPhi(UsePhi);194 return Res;195}196 197// Eliminate trivial phis198// Phis are trivial if they are defined either by themselves, or all the same199// argument.200// IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)201// We recursively try to remove them.202MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi) {203 assert(Phi && "Can only remove concrete Phi.");204 auto OperRange = Phi->operands();205 return tryRemoveTrivialPhi(Phi, OperRange);206}207template <class RangeType>208MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,209 RangeType &Operands) {210 // Bail out on non-opt Phis.211 if (NonOptPhis.count(Phi))212 return Phi;213 214 // Detect equal or self arguments215 MemoryAccess *Same = nullptr;216 for (auto &Op : Operands) {217 // If the same or self, good so far218 if (Op == Phi || Op == Same)219 continue;220 // not the same, return the phi since it's not eliminatable by us221 if (Same)222 return Phi;223 Same = cast<MemoryAccess>(&*Op);224 }225 // Never found a non-self reference, the phi is undef226 if (Same == nullptr)227 return MSSA->getLiveOnEntryDef();228 if (Phi) {229 Phi->replaceAllUsesWith(Same);230 removeMemoryAccess(Phi);231 }232 233 // We should only end up recursing in case we replaced something, in which234 // case, we may have made other Phis trivial.235 return recursePhi(Same);236}237 238void MemorySSAUpdater::insertUse(MemoryUse *MU, bool RenameUses) {239 VisitedBlocks.clear();240 InsertedPHIs.clear();241 MU->setDefiningAccess(getPreviousDef(MU));242 243 // In cases without unreachable blocks, because uses do not create new244 // may-defs, there are only two cases:245 // 1. There was a def already below us, and therefore, we should not have246 // created a phi node because it was already needed for the def.247 //248 // 2. There is no def below us, and therefore, there is no extra renaming work249 // to do.250 251 // In cases with unreachable blocks, where the unnecessary Phis were252 // optimized out, adding the Use may re-insert those Phis. Hence, when253 // inserting Uses outside of the MSSA creation process, and new Phis were254 // added, rename all uses if we are asked.255 256 if (!RenameUses && !InsertedPHIs.empty()) {257 auto *Defs = MSSA->getBlockDefs(MU->getBlock());258 (void)Defs;259 assert((!Defs || (++Defs->begin() == Defs->end())) &&260 "Block may have only a Phi or no defs");261 }262 263 if (RenameUses && InsertedPHIs.size()) {264 SmallPtrSet<BasicBlock *, 16> Visited;265 BasicBlock *StartBlock = MU->getBlock();266 267 if (auto *Defs = MSSA->getWritableBlockDefs(StartBlock)) {268 MemoryAccess *FirstDef = &*Defs->begin();269 // Convert to incoming value if it's a memorydef. A phi *is* already an270 // incoming value.271 if (auto *MD = dyn_cast<MemoryDef>(FirstDef))272 FirstDef = MD->getDefiningAccess();273 274 MSSA->renamePass(MU->getBlock(), FirstDef, Visited);275 }276 // We just inserted a phi into this block, so the incoming value will277 // become the phi anyway, so it does not matter what we pass.278 for (auto &MP : InsertedPHIs)279 if (MemoryPhi *Phi = cast_or_null<MemoryPhi>(MP))280 MSSA->renamePass(Phi->getBlock(), nullptr, Visited);281 }282}283 284// Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.285static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,286 MemoryAccess *NewDef) {287 // Replace any operand with us an incoming block with the new defining288 // access.289 int i = MP->getBasicBlockIndex(BB);290 assert(i != -1 && "Should have found the basic block in the phi");291 // We can't just compare i against getNumOperands since one is signed and the292 // other not. So use it to index into the block iterator.293 for (const BasicBlock *BlockBB : llvm::drop_begin(MP->blocks(), i)) {294 if (BlockBB != BB)295 break;296 MP->setIncomingValue(i, NewDef);297 ++i;298 }299}300 301// A brief description of the algorithm:302// First, we compute what should define the new def, using the SSA303// construction algorithm.304// Then, we update the defs below us (and any new phi nodes) in the graph to305// point to the correct new defs, to ensure we only have one variable, and no306// disconnected stores.307void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {308 // Don't bother updating dead code.309 if (!MSSA->DT->isReachableFromEntry(MD->getBlock())) {310 MD->setDefiningAccess(MSSA->getLiveOnEntryDef());311 return;312 }313 314 VisitedBlocks.clear();315 InsertedPHIs.clear();316 317 // See if we had a local def, and if not, go hunting.318 MemoryAccess *DefBefore = getPreviousDef(MD);319 bool DefBeforeSameBlock = false;320 if (DefBefore->getBlock() == MD->getBlock() &&321 !(isa<MemoryPhi>(DefBefore) &&322 llvm::is_contained(InsertedPHIs, DefBefore)))323 DefBeforeSameBlock = true;324 325 // There is a def before us, which means we can replace any store/phi uses326 // of that thing with us, since we are in the way of whatever was there327 // before.328 // We now define that def's memorydefs and memoryphis329 if (DefBeforeSameBlock) {330 DefBefore->replaceUsesWithIf(MD, [MD](Use &U) {331 // Leave the MemoryUses alone.332 // Also make sure we skip ourselves to avoid self references.333 User *Usr = U.getUser();334 return !isa<MemoryUse>(Usr) && Usr != MD;335 // Defs are automatically unoptimized when the user is set to MD below,336 // because the isOptimized() call will fail to find the same ID.337 });338 }339 340 // and that def is now our defining access.341 MD->setDefiningAccess(DefBefore);342 343 SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());344 345 SmallSet<WeakVH, 8> ExistingPhis;346 347 // Remember the index where we may insert new phis.348 unsigned NewPhiIndex = InsertedPHIs.size();349 if (!DefBeforeSameBlock) {350 // If there was a local def before us, we must have the same effect it351 // did. Because every may-def is the same, any phis/etc we would create, it352 // would also have created. If there was no local def before us, we353 // performed a global update, and have to search all successors and make354 // sure we update the first def in each of them (following all paths until355 // we hit the first def along each path). This may also insert phi nodes.356 // TODO: There are other cases we can skip this work, such as when we have a357 // single successor, and only used a straight line of single pred blocks358 // backwards to find the def. To make that work, we'd have to track whether359 // getDefRecursive only ever used the single predecessor case. These types360 // of paths also only exist in between CFG simplifications.361 362 // If this is the first def in the block and this insert is in an arbitrary363 // place, compute IDF and place phis.364 SmallPtrSet<BasicBlock *, 2> DefiningBlocks;365 366 // If this is the last Def in the block, we may need additional Phis.367 // Compute IDF in all cases, as renaming needs to be done even when MD is368 // not the last access, because it can introduce a new access past which a369 // previous access was optimized; that access needs to be reoptimized.370 DefiningBlocks.insert(MD->getBlock());371 for (const auto &VH : InsertedPHIs)372 if (const auto *RealPHI = cast_or_null<MemoryPhi>(VH))373 DefiningBlocks.insert(RealPHI->getBlock());374 ForwardIDFCalculator IDFs(*MSSA->DT);375 SmallVector<BasicBlock *, 32> IDFBlocks;376 IDFs.setDefiningBlocks(DefiningBlocks);377 IDFs.calculate(IDFBlocks);378 SmallVector<AssertingVH<MemoryPhi>, 4> NewInsertedPHIs;379 for (auto *BBIDF : IDFBlocks) {380 auto *MPhi = MSSA->getMemoryAccess(BBIDF);381 if (!MPhi) {382 MPhi = MSSA->createMemoryPhi(BBIDF);383 NewInsertedPHIs.push_back(MPhi);384 } else {385 ExistingPhis.insert(MPhi);386 }387 // Add the phis created into the IDF blocks to NonOptPhis, so they are not388 // optimized out as trivial by the call to getPreviousDefFromEnd below.389 // Once they are complete, all these Phis are added to the FixupList, and390 // removed from NonOptPhis inside fixupDefs(). Existing Phis in IDF may391 // need fixing as well, and potentially be trivial before this insertion,392 // hence add all IDF Phis. See PR43044.393 NonOptPhis.insert(MPhi);394 }395 for (auto &MPhi : NewInsertedPHIs) {396 auto *BBIDF = MPhi->getBlock();397 for (auto *Pred : predecessors(BBIDF)) {398 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;399 MPhi->addIncoming(getPreviousDefFromEnd(Pred, CachedPreviousDef), Pred);400 }401 }402 403 // Re-take the index where we're adding the new phis, because the above call404 // to getPreviousDefFromEnd, may have inserted into InsertedPHIs.405 NewPhiIndex = InsertedPHIs.size();406 for (auto &MPhi : NewInsertedPHIs) {407 InsertedPHIs.push_back(&*MPhi);408 FixupList.push_back(&*MPhi);409 }410 411 FixupList.push_back(MD);412 }413 414 // Update defining access of following defs.415 unsigned NewPhiIndexEnd = InsertedPHIs.size();416 fixupDefs(FixupList);417 assert(NewPhiIndexEnd == InsertedPHIs.size() &&418 "Should not insert new phis during fixupDefs()");419 420 // Optimize potentially non-minimal phis added in this method.421 unsigned NewPhiSize = NewPhiIndexEnd - NewPhiIndex;422 if (NewPhiSize)423 tryRemoveTrivialPhis(ArrayRef<WeakVH>(&InsertedPHIs[NewPhiIndex], NewPhiSize));424 425 // Now that all fixups are done, rename all uses if we are asked. The defs are426 // guaranteed to be in reachable code due to the check at the method entry.427 BasicBlock *StartBlock = MD->getBlock();428 if (RenameUses) {429 SmallPtrSet<BasicBlock *, 16> Visited;430 // We are guaranteed there is a def in the block, because we just got it431 // handed to us in this function.432 MemoryAccess *FirstDef = &*MSSA->getWritableBlockDefs(StartBlock)->begin();433 // Convert to incoming value if it's a memorydef. A phi *is* already an434 // incoming value.435 if (auto *MD = dyn_cast<MemoryDef>(FirstDef))436 FirstDef = MD->getDefiningAccess();437 438 MSSA->renamePass(MD->getBlock(), FirstDef, Visited);439 // We just inserted a phi into this block, so the incoming value will become440 // the phi anyway, so it does not matter what we pass.441 for (auto &MP : InsertedPHIs) {442 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);443 if (Phi)444 MSSA->renamePass(Phi->getBlock(), nullptr, Visited);445 }446 // Existing Phi blocks may need renaming too, if an access was previously447 // optimized and the inserted Defs "covers" the Optimized value.448 for (const auto &MP : ExistingPhis) {449 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);450 if (Phi)451 MSSA->renamePass(Phi->getBlock(), nullptr, Visited);452 }453 }454}455 456void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<WeakVH> &Vars) {457 SmallPtrSet<const BasicBlock *, 8> Seen;458 SmallVector<const BasicBlock *, 16> Worklist;459 for (const auto &Var : Vars) {460 MemoryAccess *NewDef = dyn_cast_or_null<MemoryAccess>(Var);461 if (!NewDef)462 continue;463 // First, see if there is a local def after the operand.464 auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());465 auto DefIter = NewDef->getDefsIterator();466 467 // The temporary Phi is being fixed, unmark it for not to optimize.468 if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(NewDef))469 NonOptPhis.erase(Phi);470 471 // If there is a local def after us, we only have to rename that.472 if (++DefIter != Defs->end()) {473 cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);474 continue;475 }476 477 // Otherwise, we need to search down through the CFG.478 // For each of our successors, handle it directly if their is a phi, or479 // place on the fixup worklist.480 for (const auto *S : successors(NewDef->getBlock())) {481 if (auto *MP = MSSA->getMemoryAccess(S))482 setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef);483 else484 Worklist.push_back(S);485 }486 487 while (!Worklist.empty()) {488 const BasicBlock *FixupBlock = Worklist.pop_back_val();489 490 // Get the first def in the block that isn't a phi node.491 if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) {492 auto *FirstDef = &*Defs->begin();493 // The loop above and below should have taken care of phi nodes494 assert(!isa<MemoryPhi>(FirstDef) &&495 "Should have already handled phi nodes!");496 // We are now this def's defining access, make sure we actually dominate497 // it498 assert(MSSA->dominates(NewDef, FirstDef) &&499 "Should have dominated the new access");500 501 cast<MemoryDef>(FirstDef)->setDefiningAccess(NewDef);502 continue;503 }504 // We didn't find a def, so we must continue.505 for (const auto *S : successors(FixupBlock)) {506 // If there is a phi node, handle it.507 // Otherwise, put the block on the worklist508 if (auto *MP = MSSA->getMemoryAccess(S))509 setMemoryPhiValueForBlock(MP, FixupBlock, NewDef);510 else {511 // If we cycle, we should have ended up at a phi node that we already512 // processed. FIXME: Double check this513 if (!Seen.insert(S).second)514 continue;515 Worklist.push_back(S);516 }517 }518 }519 }520}521 522void MemorySSAUpdater::removeEdge(BasicBlock *From, BasicBlock *To) {523 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {524 MPhi->unorderedDeleteIncomingBlock(From);525 tryRemoveTrivialPhi(MPhi);526 }527}528 529void MemorySSAUpdater::removeDuplicatePhiEdgesBetween(const BasicBlock *From,530 const BasicBlock *To) {531 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {532 bool Found = false;533 MPhi->unorderedDeleteIncomingIf([&](const MemoryAccess *, BasicBlock *B) {534 if (From != B)535 return false;536 if (Found)537 return true;538 Found = true;539 return false;540 });541 tryRemoveTrivialPhi(MPhi);542 }543}544 545/// If all arguments of a MemoryPHI are defined by the same incoming546/// argument, return that argument.547static MemoryAccess *onlySingleValue(MemoryPhi *MP) {548 MemoryAccess *MA = nullptr;549 550 for (auto &Arg : MP->operands()) {551 if (!MA)552 MA = cast<MemoryAccess>(Arg);553 else if (MA != Arg)554 return nullptr;555 }556 return MA;557}558 559static MemoryAccess *getNewDefiningAccessForClone(560 MemoryAccess *MA, const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap,561 MemorySSA *MSSA, function_ref<bool(BasicBlock *BB)> IsInClonedRegion) {562 MemoryAccess *InsnDefining = MA;563 if (MemoryDef *DefMUD = dyn_cast<MemoryDef>(InsnDefining)) {564 if (MSSA->isLiveOnEntryDef(DefMUD))565 return DefMUD;566 567 // If the MemoryDef is not part of the cloned region, leave it alone.568 Instruction *DefMUDI = DefMUD->getMemoryInst();569 assert(DefMUDI && "Found MemoryUseOrDef with no Instruction.");570 if (!IsInClonedRegion(DefMUDI->getParent()))571 return DefMUD;572 573 auto *NewDefMUDI = cast_or_null<Instruction>(VMap.lookup(DefMUDI));574 InsnDefining = NewDefMUDI ? MSSA->getMemoryAccess(NewDefMUDI) : nullptr;575 if (!InsnDefining || isa<MemoryUse>(InsnDefining)) {576 // The clone was simplified, it's no longer a MemoryDef, look up.577 InsnDefining = getNewDefiningAccessForClone(578 DefMUD->getDefiningAccess(), VMap, MPhiMap, MSSA, IsInClonedRegion);579 }580 } else {581 MemoryPhi *DefPhi = cast<MemoryPhi>(InsnDefining);582 if (MemoryAccess *NewDefPhi = MPhiMap.lookup(DefPhi))583 InsnDefining = NewDefPhi;584 }585 assert(InsnDefining && "Defining instruction cannot be nullptr.");586 return InsnDefining;587}588 589void MemorySSAUpdater::cloneUsesAndDefs(590 BasicBlock *BB, BasicBlock *NewBB, const ValueToValueMapTy &VMap,591 PhiToDefMap &MPhiMap, function_ref<bool(BasicBlock *)> IsInClonedRegion,592 bool CloneWasSimplified) {593 const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);594 if (!Acc)595 return;596 for (const MemoryAccess &MA : *Acc) {597 if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&MA)) {598 Instruction *Insn = MUD->getMemoryInst();599 // Entry does not exist if the clone of the block did not clone all600 // instructions. This occurs in LoopRotate when cloning instructions601 // from the old header to the old preheader. The cloned instruction may602 // also be a simplified Value, not an Instruction (see LoopRotate).603 // Also in LoopRotate, even when it's an instruction, due to it being604 // simplified, it may be a Use rather than a Def, so we cannot use MUD as605 // template. Calls coming from updateForClonedBlockIntoPred, ensure this.606 if (Instruction *NewInsn =607 dyn_cast_or_null<Instruction>(VMap.lookup(Insn))) {608 MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(609 NewInsn,610 getNewDefiningAccessForClone(MUD->getDefiningAccess(), VMap,611 MPhiMap, MSSA, IsInClonedRegion),612 /*Template=*/CloneWasSimplified ? nullptr : MUD,613 /*CreationMustSucceed=*/false);614 if (NewUseOrDef)615 MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);616 }617 }618 }619}620 621void MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock(622 BasicBlock *Header, BasicBlock *Preheader, BasicBlock *BEBlock) {623 auto *MPhi = MSSA->getMemoryAccess(Header);624 if (!MPhi)625 return;626 627 // Create phi node in the backedge block and populate it with the same628 // incoming values as MPhi. Skip incoming values coming from Preheader.629 auto *NewMPhi = MSSA->createMemoryPhi(BEBlock);630 bool HasUniqueIncomingValue = true;631 MemoryAccess *UniqueValue = nullptr;632 for (unsigned I = 0, E = MPhi->getNumIncomingValues(); I != E; ++I) {633 BasicBlock *IBB = MPhi->getIncomingBlock(I);634 MemoryAccess *IV = MPhi->getIncomingValue(I);635 if (IBB != Preheader) {636 NewMPhi->addIncoming(IV, IBB);637 if (HasUniqueIncomingValue) {638 if (!UniqueValue)639 UniqueValue = IV;640 else if (UniqueValue != IV)641 HasUniqueIncomingValue = false;642 }643 }644 }645 646 // Update incoming edges into MPhi. Remove all but the incoming edge from647 // Preheader. Add an edge from NewMPhi648 auto *AccFromPreheader = MPhi->getIncomingValueForBlock(Preheader);649 MPhi->setIncomingValue(0, AccFromPreheader);650 MPhi->setIncomingBlock(0, Preheader);651 for (unsigned I = MPhi->getNumIncomingValues() - 1; I >= 1; --I)652 MPhi->unorderedDeleteIncoming(I);653 MPhi->addIncoming(NewMPhi, BEBlock);654 655 // If NewMPhi is a trivial phi, remove it. Its use in the header MPhi will be656 // replaced with the unique value.657 tryRemoveTrivialPhi(NewMPhi);658}659 660void MemorySSAUpdater::updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,661 ArrayRef<BasicBlock *> ExitBlocks,662 const ValueToValueMapTy &VMap,663 bool IgnoreIncomingWithNoClones) {664 SmallSetVector<BasicBlock *, 16> Blocks(665 llvm::from_range, concat<BasicBlock *const>(LoopBlocks, ExitBlocks));666 667 auto IsInClonedRegion = [&](BasicBlock *BB) { return Blocks.contains(BB); };668 669 PhiToDefMap MPhiMap;670 auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) {671 assert(Phi && NewPhi && "Invalid Phi nodes.");672 BasicBlock *NewPhiBB = NewPhi->getBlock();673 SmallPtrSet<BasicBlock *, 4> NewPhiBBPreds(llvm::from_range,674 predecessors(NewPhiBB));675 for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; ++It) {676 MemoryAccess *IncomingAccess = Phi->getIncomingValue(It);677 BasicBlock *IncBB = Phi->getIncomingBlock(It);678 679 if (BasicBlock *NewIncBB = cast_or_null<BasicBlock>(VMap.lookup(IncBB)))680 IncBB = NewIncBB;681 else if (IgnoreIncomingWithNoClones)682 continue;683 684 // Now we have IncBB, and will need to add incoming from it to NewPhi.685 686 // If IncBB is not a predecessor of NewPhiBB, then do not add it.687 // NewPhiBB was cloned without that edge.688 if (!NewPhiBBPreds.count(IncBB))689 continue;690 691 // Determine incoming value and add it as incoming from IncBB.692 NewPhi->addIncoming(getNewDefiningAccessForClone(IncomingAccess, VMap,693 MPhiMap, MSSA,694 IsInClonedRegion),695 IncBB);696 }697 if (auto *SingleAccess = onlySingleValue(NewPhi)) {698 MPhiMap[Phi] = SingleAccess;699 removeMemoryAccess(NewPhi);700 }701 };702 703 auto ProcessBlock = [&](BasicBlock *BB) {704 BasicBlock *NewBlock = cast_or_null<BasicBlock>(VMap.lookup(BB));705 if (!NewBlock)706 return;707 708 assert(!MSSA->getWritableBlockAccesses(NewBlock) &&709 "Cloned block should have no accesses");710 711 // Add MemoryPhi.712 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) {713 MemoryPhi *NewPhi = MSSA->createMemoryPhi(NewBlock);714 MPhiMap[MPhi] = NewPhi;715 }716 // Update Uses and Defs.717 cloneUsesAndDefs(BB, NewBlock, VMap, MPhiMap, IsInClonedRegion);718 };719 720 for (auto *BB : Blocks)721 ProcessBlock(BB);722 723 for (auto *BB : Blocks)724 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))725 if (MemoryAccess *NewPhi = MPhiMap.lookup(MPhi))726 FixPhiIncomingValues(MPhi, cast<MemoryPhi>(NewPhi));727}728 729void MemorySSAUpdater::updateForClonedBlockIntoPred(730 BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM) {731 // All defs/phis from outside BB that are used in BB, are valid uses in P1.732 // Since those defs/phis must have dominated BB, and also dominate P1.733 // Defs from BB being used in BB will be replaced with the cloned defs from734 // VM. The uses of BB's Phi (if it exists) in BB will be replaced by the735 // incoming def into the Phi from P1.736 // Instructions cloned into the predecessor are in practice sometimes737 // simplified, so disable the use of the template, and create an access from738 // scratch.739 PhiToDefMap MPhiMap;740 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))741 MPhiMap[MPhi] = MPhi->getIncomingValueForBlock(P1);742 cloneUsesAndDefs(743 BB, P1, VM, MPhiMap, [&](BasicBlock *CheckBB) { return BB == CheckBB; },744 /*CloneWasSimplified=*/true);745}746 747template <typename Iter>748void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop(749 ArrayRef<BasicBlock *> ExitBlocks, Iter ValuesBegin, Iter ValuesEnd,750 DominatorTree &DT) {751 SmallVector<CFGUpdate, 4> Updates;752 // Update/insert phis in all successors of exit blocks.753 for (auto *Exit : ExitBlocks)754 for (const ValueToValueMapTy *VMap : make_range(ValuesBegin, ValuesEnd))755 if (BasicBlock *NewExit = cast_or_null<BasicBlock>(VMap->lookup(Exit))) {756 BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);757 Updates.push_back({DT.Insert, NewExit, ExitSucc});758 }759 applyInsertUpdates(Updates, DT);760}761 762void MemorySSAUpdater::updateExitBlocksForClonedLoop(763 ArrayRef<BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap,764 DominatorTree &DT) {765 const ValueToValueMapTy *const Arr[] = {&VMap};766 privateUpdateExitBlocksForClonedLoop(ExitBlocks, std::begin(Arr),767 std::end(Arr), DT);768}769 770void MemorySSAUpdater::updateExitBlocksForClonedLoop(771 ArrayRef<BasicBlock *> ExitBlocks,772 ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT) {773 auto GetPtr = [&](const std::unique_ptr<ValueToValueMapTy> &I) {774 return I.get();775 };776 using MappedIteratorType =777 mapped_iterator<const std::unique_ptr<ValueToValueMapTy> *,778 decltype(GetPtr)>;779 auto MapBegin = MappedIteratorType(VMaps.begin(), GetPtr);780 auto MapEnd = MappedIteratorType(VMaps.end(), GetPtr);781 privateUpdateExitBlocksForClonedLoop(ExitBlocks, MapBegin, MapEnd, DT);782}783 784void MemorySSAUpdater::applyUpdates(ArrayRef<CFGUpdate> Updates,785 DominatorTree &DT, bool UpdateDT) {786 SmallVector<CFGUpdate, 4> DeleteUpdates;787 SmallVector<CFGUpdate, 4> RevDeleteUpdates;788 SmallVector<CFGUpdate, 4> InsertUpdates;789 for (const auto &Update : Updates) {790 if (Update.getKind() == DT.Insert)791 InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});792 else {793 DeleteUpdates.push_back({DT.Delete, Update.getFrom(), Update.getTo()});794 RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});795 }796 }797 798 if (!DeleteUpdates.empty()) {799 if (!InsertUpdates.empty()) {800 if (!UpdateDT) {801 SmallVector<CFGUpdate, 0> Empty;802 // Deletes are reversed applied, because this CFGView is pretending the803 // deletes did not happen yet, hence the edges still exist.804 DT.applyUpdates(Empty, RevDeleteUpdates);805 } else {806 // Apply all updates, with the RevDeleteUpdates as PostCFGView.807 DT.applyUpdates(Updates, RevDeleteUpdates);808 }809 810 // Note: the MSSA update below doesn't distinguish between a GD with811 // (RevDelete,false) and (Delete, true), but this matters for the DT812 // updates above; for "children" purposes they are equivalent; but the813 // updates themselves convey the desired update, used inside DT only.814 GraphDiff<BasicBlock *> GD(RevDeleteUpdates);815 applyInsertUpdates(InsertUpdates, DT, &GD);816 // Update DT to redelete edges; this matches the real CFG so we can817 // perform the standard update without a postview of the CFG.818 DT.applyUpdates(DeleteUpdates);819 } else {820 if (UpdateDT)821 DT.applyUpdates(DeleteUpdates);822 }823 } else {824 if (UpdateDT)825 DT.applyUpdates(Updates);826 GraphDiff<BasicBlock *> GD;827 applyInsertUpdates(InsertUpdates, DT, &GD);828 }829 830 // Update for deleted edges831 for (auto &Update : DeleteUpdates)832 removeEdge(Update.getFrom(), Update.getTo());833}834 835void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,836 DominatorTree &DT) {837 GraphDiff<BasicBlock *> GD;838 applyInsertUpdates(Updates, DT, &GD);839}840 841void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,842 DominatorTree &DT,843 const GraphDiff<BasicBlock *> *GD) {844 // Get recursive last Def, assuming well formed MSSA and updated DT.845 auto GetLastDef = [&](BasicBlock *BB) -> MemoryAccess * {846 while (true) {847 MemorySSA::DefsList *Defs = MSSA->getWritableBlockDefs(BB);848 // Return last Def or Phi in BB, if it exists.849 if (Defs)850 return &*(--Defs->end());851 852 // Check number of predecessors, we only care if there's more than one.853 unsigned Count = 0;854 BasicBlock *Pred = nullptr;855 for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BB)) {856 Pred = Pi;857 Count++;858 if (Count == 2)859 break;860 }861 862 // If BB has multiple predecessors, get last definition from IDom.863 if (Count != 1) {864 // [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its865 // DT is invalidated. Return LoE as its last def. This will be added to866 // MemoryPhi node, and later deleted when the block is deleted.867 if (!DT.getNode(BB))868 return MSSA->getLiveOnEntryDef();869 if (auto *IDom = DT.getNode(BB)->getIDom())870 if (IDom->getBlock() != BB) {871 BB = IDom->getBlock();872 continue;873 }874 return MSSA->getLiveOnEntryDef();875 } else {876 // Single predecessor, BB cannot be dead. GetLastDef of Pred.877 assert(Count == 1 && Pred && "Single predecessor expected.");878 // BB can be unreachable though, return LoE if that is the case.879 if (!DT.getNode(BB))880 return MSSA->getLiveOnEntryDef();881 BB = Pred;882 }883 };884 llvm_unreachable("Unable to get last definition.");885 };886 887 // Get nearest IDom given a set of blocks.888 // TODO: this can be optimized by starting the search at the node with the889 // lowest level (highest in the tree).890 auto FindNearestCommonDominator =891 [&](const SmallSetVector<BasicBlock *, 2> &BBSet) -> BasicBlock * {892 BasicBlock *PrevIDom = *BBSet.begin();893 for (auto *BB : BBSet)894 PrevIDom = DT.findNearestCommonDominator(PrevIDom, BB);895 return PrevIDom;896 };897 898 // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not899 // include CurrIDom.900 auto GetNoLongerDomBlocks =901 [&](BasicBlock *PrevIDom, BasicBlock *CurrIDom,902 SmallVectorImpl<BasicBlock *> &BlocksPrevDom) {903 if (PrevIDom == CurrIDom)904 return;905 BlocksPrevDom.push_back(PrevIDom);906 BasicBlock *NextIDom = PrevIDom;907 while (BasicBlock *UpIDom =908 DT.getNode(NextIDom)->getIDom()->getBlock()) {909 if (UpIDom == CurrIDom)910 break;911 BlocksPrevDom.push_back(UpIDom);912 NextIDom = UpIDom;913 }914 };915 916 // Map a BB to its predecessors: added + previously existing. To get a917 // deterministic order, store predecessors as SetVectors. The order in each918 // will be defined by the order in Updates (fixed) and the order given by919 // children<> (also fixed). Since we further iterate over these ordered sets,920 // we lose the information of multiple edges possibly existing between two921 // blocks, so we'll keep and EdgeCount map for that.922 // An alternate implementation could keep unordered set for the predecessors,923 // traverse either Updates or children<> each time to get the deterministic924 // order, and drop the usage of EdgeCount. This alternate approach would still925 // require querying the maps for each predecessor, and children<> call has926 // additional computation inside for creating the snapshot-graph predecessors.927 // As such, we favor using a little additional storage and less compute time.928 // This decision can be revisited if we find the alternative more favorable.929 930 struct PredInfo {931 SmallSetVector<BasicBlock *, 2> Added;932 SmallSetVector<BasicBlock *, 2> Prev;933 };934 SmallDenseMap<BasicBlock *, PredInfo> PredMap;935 936 for (const auto &Edge : Updates) {937 BasicBlock *BB = Edge.getTo();938 auto &AddedBlockSet = PredMap[BB].Added;939 AddedBlockSet.insert(Edge.getFrom());940 }941 942 // Store all existing predecessor for each BB, at least one must exist.943 SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>, int> EdgeCountMap;944 SmallPtrSet<BasicBlock *, 2> NewBlocks;945 for (auto &BBPredPair : PredMap) {946 auto *BB = BBPredPair.first;947 const auto &AddedBlockSet = BBPredPair.second.Added;948 auto &PrevBlockSet = BBPredPair.second.Prev;949 for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BB)) {950 if (!AddedBlockSet.count(Pi))951 PrevBlockSet.insert(Pi);952 EdgeCountMap[{Pi, BB}]++;953 }954 955 if (PrevBlockSet.empty()) {956 assert(pred_size(BB) == AddedBlockSet.size() && "Duplicate edges added.");957 LLVM_DEBUG(958 dbgs()959 << "Adding a predecessor to a block with no predecessors. "960 "This must be an edge added to a new, likely cloned, block. "961 "Its memory accesses must be already correct, assuming completed "962 "via the updateExitBlocksForClonedLoop API. "963 "Assert a single such edge is added so no phi addition or "964 "additional processing is required.\n");965 assert(AddedBlockSet.size() == 1 &&966 "Can only handle adding one predecessor to a new block.");967 // Need to remove new blocks from PredMap. Remove below to not invalidate968 // iterator here.969 NewBlocks.insert(BB);970 }971 }972 // Nothing to process for new/cloned blocks.973 for (auto *BB : NewBlocks)974 PredMap.erase(BB);975 976 SmallVector<BasicBlock *, 16> BlocksWithDefsToReplace;977 SmallVector<WeakVH, 8> InsertedPhis;978 979 // First create MemoryPhis in all blocks that don't have one. Create in the980 // order found in Updates, not in PredMap, to get deterministic numbering.981 for (const auto &Edge : Updates) {982 BasicBlock *BB = Edge.getTo();983 if (PredMap.count(BB) && !MSSA->getMemoryAccess(BB))984 InsertedPhis.push_back(MSSA->createMemoryPhi(BB));985 }986 987 // Now we'll fill in the MemoryPhis with the right incoming values.988 for (auto &BBPredPair : PredMap) {989 auto *BB = BBPredPair.first;990 const auto &PrevBlockSet = BBPredPair.second.Prev;991 const auto &AddedBlockSet = BBPredPair.second.Added;992 assert(!PrevBlockSet.empty() &&993 "At least one previous predecessor must exist.");994 995 // TODO: if this becomes a bottleneck, we can save on GetLastDef calls by996 // keeping this map before the loop. We can reuse already populated entries997 // if an edge is added from the same predecessor to two different blocks,998 // and this does happen in rotate. Note that the map needs to be updated999 // when deleting non-necessary phis below, if the phi is in the map by1000 // replacing the value with DefP1.1001 SmallDenseMap<BasicBlock *, MemoryAccess *> LastDefAddedPred;1002 for (auto *AddedPred : AddedBlockSet) {1003 auto *DefPn = GetLastDef(AddedPred);1004 assert(DefPn != nullptr && "Unable to find last definition.");1005 LastDefAddedPred[AddedPred] = DefPn;1006 }1007 1008 MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB);1009 // If Phi is not empty, add an incoming edge from each added pred. Must1010 // still compute blocks with defs to replace for this block below.1011 if (NewPhi->getNumOperands()) {1012 for (auto *Pred : AddedBlockSet) {1013 auto *LastDefForPred = LastDefAddedPred[Pred];1014 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)1015 NewPhi->addIncoming(LastDefForPred, Pred);1016 }1017 } else {1018 // Pick any existing predecessor and get its definition. All other1019 // existing predecessors should have the same one, since no phi existed.1020 auto *P1 = *PrevBlockSet.begin();1021 MemoryAccess *DefP1 = GetLastDef(P1);1022 1023 // Check DefP1 against all Defs in LastDefPredPair. If all the same,1024 // nothing to add.1025 bool InsertPhi = false;1026 for (auto LastDefPredPair : LastDefAddedPred)1027 if (DefP1 != LastDefPredPair.second) {1028 InsertPhi = true;1029 break;1030 }1031 if (!InsertPhi) {1032 // Since NewPhi may be used in other newly added Phis, replace all uses1033 // of NewPhi with the definition coming from all predecessors (DefP1),1034 // before deleting it.1035 NewPhi->replaceAllUsesWith(DefP1);1036 removeMemoryAccess(NewPhi);1037 continue;1038 }1039 1040 // Update Phi with new values for new predecessors and old value for all1041 // other predecessors. Since AddedBlockSet and PrevBlockSet are ordered1042 // sets, the order of entries in NewPhi is deterministic.1043 for (auto *Pred : AddedBlockSet) {1044 auto *LastDefForPred = LastDefAddedPred[Pred];1045 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)1046 NewPhi->addIncoming(LastDefForPred, Pred);1047 }1048 for (auto *Pred : PrevBlockSet)1049 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)1050 NewPhi->addIncoming(DefP1, Pred);1051 }1052 1053 // Get all blocks that used to dominate BB and no longer do after adding1054 // AddedBlockSet, where PrevBlockSet are the previously known predecessors.1055 assert(DT.getNode(BB)->getIDom() && "BB does not have valid idom");1056 BasicBlock *PrevIDom = FindNearestCommonDominator(PrevBlockSet);1057 assert(PrevIDom && "Previous IDom should exists");1058 BasicBlock *NewIDom = DT.getNode(BB)->getIDom()->getBlock();1059 assert(NewIDom && "BB should have a new valid idom");1060 assert(DT.dominates(NewIDom, PrevIDom) &&1061 "New idom should dominate old idom");1062 GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);1063 }1064 1065 tryRemoveTrivialPhis(InsertedPhis);1066 // Create the set of blocks that now have a definition. We'll use this to1067 // compute IDF and add Phis there next.1068 SmallVector<BasicBlock *, 8> BlocksToProcess;1069 for (auto &VH : InsertedPhis)1070 if (auto *MPhi = cast_or_null<MemoryPhi>(VH))1071 BlocksToProcess.push_back(MPhi->getBlock());1072 1073 // Compute IDF and add Phis in all IDF blocks that do not have one.1074 SmallVector<BasicBlock *, 32> IDFBlocks;1075 if (!BlocksToProcess.empty()) {1076 ForwardIDFCalculator IDFs(DT, GD);1077 SmallPtrSet<BasicBlock *, 16> DefiningBlocks(llvm::from_range,1078 BlocksToProcess);1079 IDFs.setDefiningBlocks(DefiningBlocks);1080 IDFs.calculate(IDFBlocks);1081 1082 SmallSetVector<MemoryPhi *, 4> PhisToFill;1083 // First create all needed Phis.1084 for (auto *BBIDF : IDFBlocks)1085 if (!MSSA->getMemoryAccess(BBIDF)) {1086 auto *IDFPhi = MSSA->createMemoryPhi(BBIDF);1087 InsertedPhis.push_back(IDFPhi);1088 PhisToFill.insert(IDFPhi);1089 }1090 // Then update or insert their correct incoming values.1091 for (auto *BBIDF : IDFBlocks) {1092 auto *IDFPhi = MSSA->getMemoryAccess(BBIDF);1093 assert(IDFPhi && "Phi must exist");1094 if (!PhisToFill.count(IDFPhi)) {1095 // Update existing Phi.1096 // FIXME: some updates may be redundant, try to optimize and skip some.1097 for (unsigned I = 0, E = IDFPhi->getNumIncomingValues(); I < E; ++I)1098 IDFPhi->setIncomingValue(I, GetLastDef(IDFPhi->getIncomingBlock(I)));1099 } else {1100 for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BBIDF))1101 IDFPhi->addIncoming(GetLastDef(Pi), Pi);1102 }1103 }1104 }1105 1106 // Now for all defs in BlocksWithDefsToReplace, if there are uses they no1107 // longer dominate, replace those with the closest dominating def.1108 // This will also update optimized accesses, as they're also uses.1109 for (auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) {1110 if (auto DefsList = MSSA->getWritableBlockDefs(BlockWithDefsToReplace)) {1111 for (auto &DefToReplaceUses : *DefsList) {1112 BasicBlock *DominatingBlock = DefToReplaceUses.getBlock();1113 // We defer resetting optimized accesses until all uses are replaced, to1114 // avoid invalidating the iterator.1115 SmallVector<MemoryUseOrDef *, 4> ResetOptimized;1116 for (Use &U : llvm::make_early_inc_range(DefToReplaceUses.uses())) {1117 MemoryAccess *Usr = cast<MemoryAccess>(U.getUser());1118 if (MemoryPhi *UsrPhi = dyn_cast<MemoryPhi>(Usr)) {1119 BasicBlock *DominatedBlock = UsrPhi->getIncomingBlock(U);1120 if (!DT.dominates(DominatingBlock, DominatedBlock))1121 U.set(GetLastDef(DominatedBlock));1122 } else {1123 BasicBlock *DominatedBlock = Usr->getBlock();1124 if (!DT.dominates(DominatingBlock, DominatedBlock)) {1125 if (auto *DomBlPhi = MSSA->getMemoryAccess(DominatedBlock))1126 U.set(DomBlPhi);1127 else {1128 auto *IDom = DT.getNode(DominatedBlock)->getIDom();1129 assert(IDom && "Block must have a valid IDom.");1130 U.set(GetLastDef(IDom->getBlock()));1131 }1132 ResetOptimized.push_back(cast<MemoryUseOrDef>(Usr));1133 }1134 }1135 }1136 1137 for (auto *Usr : ResetOptimized)1138 Usr->resetOptimized();1139 }1140 }1141 }1142 tryRemoveTrivialPhis(InsertedPhis);1143}1144 1145// Move What before Where in the MemorySSA IR.1146template <class WhereType>1147void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,1148 WhereType Where) {1149 // Mark MemoryPhi users of What not to be optimized.1150 for (auto *U : What->users())1151 if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))1152 NonOptPhis.insert(PhiUser);1153 1154 // Replace all our users with our defining access.1155 What->replaceAllUsesWith(What->getDefiningAccess());1156 1157 // Let MemorySSA take care of moving it around in the lists.1158 MSSA->moveTo(What, BB, Where);1159 1160 // Now reinsert it into the IR and do whatever fixups needed.1161 if (auto *MD = dyn_cast<MemoryDef>(What))1162 insertDef(MD, /*RenameUses=*/true);1163 else1164 insertUse(cast<MemoryUse>(What), /*RenameUses=*/true);1165 1166 // Clear dangling pointers. We added all MemoryPhi users, but not all1167 // of them are removed by fixupDefs().1168 NonOptPhis.clear();1169}1170 1171// Move What before Where in the MemorySSA IR.1172void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {1173 moveTo(What, Where->getBlock(), Where->getIterator());1174}1175 1176// Move What after Where in the MemorySSA IR.1177void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) {1178 moveTo(What, Where->getBlock(), ++Where->getIterator());1179}1180 1181void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,1182 MemorySSA::InsertionPlace Where) {1183 if (Where != MemorySSA::InsertionPlace::BeforeTerminator)1184 return moveTo(What, BB, Where);1185 1186 if (auto *Where = MSSA->getMemoryAccess(BB->getTerminator()))1187 return moveBefore(What, Where);1188 else1189 return moveTo(What, BB, MemorySSA::InsertionPlace::End);1190}1191 1192// All accesses in To used to be in From. Move to end and update access lists.1193void MemorySSAUpdater::moveAllAccesses(BasicBlock *From, BasicBlock *To,1194 Instruction *Start) {1195 1196 MemorySSA::AccessList *Accs = MSSA->getWritableBlockAccesses(From);1197 if (!Accs)1198 return;1199 1200 assert(Start->getParent() == To && "Incorrect Start instruction");1201 MemoryAccess *FirstInNew = nullptr;1202 for (Instruction &I : make_range(Start->getIterator(), To->end()))1203 if ((FirstInNew = MSSA->getMemoryAccess(&I)))1204 break;1205 if (FirstInNew) {1206 auto *MUD = cast<MemoryUseOrDef>(FirstInNew);1207 do {1208 auto NextIt = ++MUD->getIterator();1209 MemoryUseOrDef *NextMUD = (!Accs || NextIt == Accs->end())1210 ? nullptr1211 : cast<MemoryUseOrDef>(&*NextIt);1212 MSSA->moveTo(MUD, To, MemorySSA::End);1213 // Moving MUD from Accs in the moveTo above, may delete Accs, so we need1214 // to retrieve it again.1215 Accs = MSSA->getWritableBlockAccesses(From);1216 MUD = NextMUD;1217 } while (MUD);1218 }1219 1220 // If all accesses were moved and only a trivial Phi remains, we try to remove1221 // that Phi. This is needed when From is going to be deleted.1222 auto *Defs = MSSA->getWritableBlockDefs(From);1223 if (Defs && !Defs->empty())1224 if (auto *Phi = dyn_cast<MemoryPhi>(&*Defs->begin()))1225 tryRemoveTrivialPhi(Phi);1226}1227 1228void MemorySSAUpdater::moveAllAfterSpliceBlocks(BasicBlock *From,1229 BasicBlock *To,1230 Instruction *Start) {1231 assert(MSSA->getBlockAccesses(To) == nullptr &&1232 "To block is expected to be free of MemoryAccesses.");1233 moveAllAccesses(From, To, Start);1234 for (BasicBlock *Succ : successors(To))1235 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))1236 MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);1237}1238 1239void MemorySSAUpdater::moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,1240 Instruction *Start) {1241 assert(From->getUniquePredecessor() == To &&1242 "From block is expected to have a single predecessor (To).");1243 moveAllAccesses(From, To, Start);1244 for (BasicBlock *Succ : successors(From))1245 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))1246 MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);1247}1248 1249void MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(1250 BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,1251 bool IdenticalEdgesWereMerged) {1252 assert(!MSSA->getWritableBlockAccesses(New) &&1253 "Access list should be null for a new block.");1254 MemoryPhi *Phi = MSSA->getMemoryAccess(Old);1255 if (!Phi)1256 return;1257 if (Old->hasNPredecessors(1)) {1258 assert(pred_size(New) == Preds.size() &&1259 "Should have moved all predecessors.");1260 MSSA->moveTo(Phi, New, MemorySSA::Beginning);1261 } else {1262 assert(!Preds.empty() && "Must be moving at least one predecessor to the "1263 "new immediate predecessor.");1264 MemoryPhi *NewPhi = MSSA->createMemoryPhi(New);1265 SmallPtrSet<BasicBlock *, 16> PredsSet(llvm::from_range, Preds);1266 // Currently only support the case of removing a single incoming edge when1267 // identical edges were not merged.1268 if (!IdenticalEdgesWereMerged)1269 assert(PredsSet.size() == Preds.size() &&1270 "If identical edges were not merged, we cannot have duplicate "1271 "blocks in the predecessors");1272 Phi->unorderedDeleteIncomingIf([&](MemoryAccess *MA, BasicBlock *B) {1273 if (PredsSet.count(B)) {1274 NewPhi->addIncoming(MA, B);1275 if (!IdenticalEdgesWereMerged)1276 PredsSet.erase(B);1277 return true;1278 }1279 return false;1280 });1281 Phi->addIncoming(NewPhi, New);1282 tryRemoveTrivialPhi(NewPhi);1283 }1284}1285 1286void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA, bool OptimizePhis) {1287 assert(!MSSA->isLiveOnEntryDef(MA) &&1288 "Trying to remove the live on entry def");1289 // We can only delete phi nodes if they have no uses, or we can replace all1290 // uses with a single definition.1291 MemoryAccess *NewDefTarget = nullptr;1292 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {1293 // Note that it is sufficient to know that all edges of the phi node have1294 // the same argument. If they do, by the definition of dominance frontiers1295 // (which we used to place this phi), that argument must dominate this phi,1296 // and thus, must dominate the phi's uses, and so we will not hit the assert1297 // below.1298 NewDefTarget = onlySingleValue(MP);1299 assert((NewDefTarget || MP->use_empty()) &&1300 "We can't delete this memory phi");1301 } else {1302 NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();1303 }1304 1305 SmallSetVector<MemoryPhi *, 4> PhisToCheck;1306 1307 // Re-point the uses at our defining access1308 if (!isa<MemoryUse>(MA) && !MA->use_empty()) {1309 // Reset optimized on users of this store, and reset the uses.1310 // A few notes:1311 // 1. This is a slightly modified version of RAUW to avoid walking the1312 // uses twice here.1313 // 2. If we wanted to be complete, we would have to reset the optimized1314 // flags on users of phi nodes if doing the below makes a phi node have all1315 // the same arguments. Instead, we prefer users to removeMemoryAccess those1316 // phi nodes, because doing it here would be N^3.1317 if (MA->hasValueHandle())1318 ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);1319 // Note: We assume MemorySSA is not used in metadata since it's not really1320 // part of the IR.1321 1322 assert(NewDefTarget != MA && "Going into an infinite loop");1323 while (!MA->use_empty()) {1324 Use &U = *MA->use_begin();1325 if (auto *MUD = dyn_cast<MemoryUseOrDef>(U.getUser()))1326 MUD->resetOptimized();1327 if (OptimizePhis)1328 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U.getUser()))1329 PhisToCheck.insert(MP);1330 U.set(NewDefTarget);1331 }1332 }1333 1334 // The call below to erase will destroy MA, so we can't change the order we1335 // are doing things here1336 MSSA->removeFromLookups(MA);1337 MSSA->removeFromLists(MA);1338 1339 // Optionally optimize Phi uses. This will recursively remove trivial phis.1340 if (!PhisToCheck.empty()) {1341 SmallVector<WeakVH, 16> PhisToOptimize{PhisToCheck.begin(),1342 PhisToCheck.end()};1343 PhisToCheck.clear();1344 1345 unsigned PhisSize = PhisToOptimize.size();1346 while (PhisSize-- > 0)1347 if (MemoryPhi *MP =1348 cast_or_null<MemoryPhi>(PhisToOptimize.pop_back_val()))1349 tryRemoveTrivialPhi(MP);1350 }1351}1352 1353void MemorySSAUpdater::removeBlocks(1354 const SmallSetVector<BasicBlock *, 8> &DeadBlocks) {1355 // First delete all uses of BB in MemoryPhis.1356 for (BasicBlock *BB : DeadBlocks) {1357 Instruction *TI = BB->getTerminator();1358 assert(TI && "Basic block expected to have a terminator instruction");1359 for (BasicBlock *Succ : successors(TI))1360 if (!DeadBlocks.count(Succ))1361 if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {1362 MP->unorderedDeleteIncomingBlock(BB);1363 tryRemoveTrivialPhi(MP);1364 }1365 // Drop all references of all accesses in BB1366 if (MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB))1367 for (MemoryAccess &MA : *Acc)1368 MA.dropAllReferences();1369 }1370 1371 // Next, delete all memory accesses in each block1372 for (BasicBlock *BB : DeadBlocks) {1373 MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB);1374 if (!Acc)1375 continue;1376 for (MemoryAccess &MA : llvm::make_early_inc_range(*Acc)) {1377 MSSA->removeFromLookups(&MA);1378 MSSA->removeFromLists(&MA);1379 }1380 }1381}1382 1383void MemorySSAUpdater::tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs) {1384 for (const auto &VH : UpdatedPHIs)1385 if (auto *MPhi = cast_or_null<MemoryPhi>(VH))1386 tryRemoveTrivialPhi(MPhi);1387}1388 1389void MemorySSAUpdater::changeToUnreachable(const Instruction *I) {1390 const BasicBlock *BB = I->getParent();1391 // Remove memory accesses in BB for I and all following instructions.1392 auto BBI = I->getIterator(), BBE = BB->end();1393 // FIXME: If this becomes too expensive, iterate until the first instruction1394 // with a memory access, then iterate over MemoryAccesses.1395 while (BBI != BBE)1396 removeMemoryAccess(&*(BBI++));1397 // Update phis in BB's successors to remove BB.1398 SmallVector<WeakVH, 16> UpdatedPHIs;1399 for (const BasicBlock *Successor : successors(BB)) {1400 removeDuplicatePhiEdgesBetween(BB, Successor);1401 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Successor)) {1402 MPhi->unorderedDeleteIncomingBlock(BB);1403 UpdatedPHIs.push_back(MPhi);1404 }1405 }1406 // Optimize trivial phis.1407 tryRemoveTrivialPhis(UpdatedPHIs);1408}1409 1410MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(1411 Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,1412 MemorySSA::InsertionPlace Point, bool CreationMustSucceed) {1413 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(1414 I, Definition, /*Template=*/nullptr, CreationMustSucceed);1415 if (NewAccess)1416 MSSA->insertIntoListsForBlock(NewAccess, BB, Point);1417 return NewAccess;1418}1419 1420MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore(1421 Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {1422 assert(I->getParent() == InsertPt->getBlock() &&1423 "New and old access must be in the same block");1424 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);1425 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),1426 InsertPt->getIterator());1427 return NewAccess;1428}1429 1430MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(1431 Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {1432 assert(I->getParent() == InsertPt->getBlock() &&1433 "New and old access must be in the same block");1434 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);1435 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),1436 ++InsertPt->getIterator());1437 return NewAccess;1438}1439