[llvm-objcopy] [COFF] Test absolute symbols wrt --strip-unneeded and --discard-all...
[llvm-complete.git] / lib / Analysis / MemorySSAUpdater.cpp
blob6c817d20368456b1196c47d9485845154d62c61a
1 //===-- MemorySSAUpdater.cpp - Memory SSA Updater--------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------===//
9 //
10 // This file implements the MemorySSAUpdater class.
12 //===----------------------------------------------------------------===//
13 #include "llvm/Analysis/MemorySSAUpdater.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/ADT/SetVector.h"
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/Analysis/IteratedDominanceFrontier.h"
18 #include "llvm/Analysis/MemorySSA.h"
19 #include "llvm/IR/DataLayout.h"
20 #include "llvm/IR/Dominators.h"
21 #include "llvm/IR/GlobalVariable.h"
22 #include "llvm/IR/IRBuilder.h"
23 #include "llvm/IR/LLVMContext.h"
24 #include "llvm/IR/Metadata.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/FormattedStream.h"
28 #include <algorithm>
30 #define DEBUG_TYPE "memoryssa"
31 using namespace llvm;
33 // This is the marker algorithm from "Simple and Efficient Construction of
34 // Static Single Assignment Form"
35 // The simple, non-marker algorithm places phi nodes at any join
36 // Here, we place markers, and only place phi nodes if they end up necessary.
37 // They are only necessary if they break a cycle (IE we recursively visit
38 // ourselves again), or we discover, while getting the value of the operands,
39 // that there are two or more definitions needing to be merged.
40 // This still will leave non-minimal form in the case of irreducible control
41 // flow, where phi nodes may be in cycles with themselves, but unnecessary.
42 MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(
43 BasicBlock *BB,
44 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
45 // First, do a cache lookup. Without this cache, certain CFG structures
46 // (like a series of if statements) take exponential time to visit.
47 auto Cached = CachedPreviousDef.find(BB);
48 if (Cached != CachedPreviousDef.end()) {
49 return Cached->second;
52 if (BasicBlock *Pred = BB->getSinglePredecessor()) {
53 // Single predecessor case, just recurse, we can only have one definition.
54 MemoryAccess *Result = getPreviousDefFromEnd(Pred, CachedPreviousDef);
55 CachedPreviousDef.insert({BB, Result});
56 return Result;
59 if (VisitedBlocks.count(BB)) {
60 // We hit our node again, meaning we had a cycle, we must insert a phi
61 // node to break it so we have an operand. The only case this will
62 // insert useless phis is if we have irreducible control flow.
63 MemoryAccess *Result = MSSA->createMemoryPhi(BB);
64 CachedPreviousDef.insert({BB, Result});
65 return Result;
68 if (VisitedBlocks.insert(BB).second) {
69 // Mark us visited so we can detect a cycle
70 SmallVector<TrackingVH<MemoryAccess>, 8> PhiOps;
72 // Recurse to get the values in our predecessors for placement of a
73 // potential phi node. This will insert phi nodes if we cycle in order to
74 // break the cycle and have an operand.
75 for (auto *Pred : predecessors(BB))
76 PhiOps.push_back(getPreviousDefFromEnd(Pred, CachedPreviousDef));
78 // Now try to simplify the ops to avoid placing a phi.
79 // This may return null if we never created a phi yet, that's okay
80 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));
82 // See if we can avoid the phi by simplifying it.
83 auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
84 // If we couldn't simplify, we may have to create a phi
85 if (Result == Phi) {
86 if (!Phi)
87 Phi = MSSA->createMemoryPhi(BB);
89 // See if the existing phi operands match what we need.
90 // Unlike normal SSA, we only allow one phi node per block, so we can't just
91 // create a new one.
92 if (Phi->getNumOperands() != 0) {
93 // FIXME: Figure out whether this is dead code and if so remove it.
94 if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {
95 // These will have been filled in by the recursive read we did above.
96 llvm::copy(PhiOps, Phi->op_begin());
97 std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
99 } else {
100 unsigned i = 0;
101 for (auto *Pred : predecessors(BB))
102 Phi->addIncoming(&*PhiOps[i++], Pred);
103 InsertedPHIs.push_back(Phi);
105 Result = Phi;
108 // Set ourselves up for the next variable by resetting visited state.
109 VisitedBlocks.erase(BB);
110 CachedPreviousDef.insert({BB, Result});
111 return Result;
113 llvm_unreachable("Should have hit one of the three cases above");
116 // This starts at the memory access, and goes backwards in the block to find the
117 // previous definition. If a definition is not found the block of the access,
118 // it continues globally, creating phi nodes to ensure we have a single
119 // definition.
120 MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {
121 if (auto *LocalResult = getPreviousDefInBlock(MA))
122 return LocalResult;
123 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
124 return getPreviousDefRecursive(MA->getBlock(), CachedPreviousDef);
127 // This starts at the memory access, and goes backwards in the block to the find
128 // the previous definition. If the definition is not found in the block of the
129 // access, it returns nullptr.
130 MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
131 auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());
133 // It's possible there are no defs, or we got handed the first def to start.
134 if (Defs) {
135 // If this is a def, we can just use the def iterators.
136 if (!isa<MemoryUse>(MA)) {
137 auto Iter = MA->getReverseDefsIterator();
138 ++Iter;
139 if (Iter != Defs->rend())
140 return &*Iter;
141 } else {
142 // Otherwise, have to walk the all access iterator.
143 auto End = MSSA->getWritableBlockAccesses(MA->getBlock())->rend();
144 for (auto &U : make_range(++MA->getReverseIterator(), End))
145 if (!isa<MemoryUse>(U))
146 return cast<MemoryAccess>(&U);
147 // Note that if MA comes before Defs->begin(), we won't hit a def.
148 return nullptr;
151 return nullptr;
154 // This starts at the end of block
155 MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(
156 BasicBlock *BB,
157 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
158 auto *Defs = MSSA->getWritableBlockDefs(BB);
160 if (Defs)
161 return &*Defs->rbegin();
163 return getPreviousDefRecursive(BB, CachedPreviousDef);
165 // Recurse over a set of phi uses to eliminate the trivial ones
166 MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {
167 if (!Phi)
168 return nullptr;
169 TrackingVH<MemoryAccess> Res(Phi);
170 SmallVector<TrackingVH<Value>, 8> Uses;
171 std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses));
172 for (auto &U : Uses) {
173 if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U)) {
174 auto OperRange = UsePhi->operands();
175 tryRemoveTrivialPhi(UsePhi, OperRange);
178 return Res;
181 // Eliminate trivial phis
182 // Phis are trivial if they are defined either by themselves, or all the same
183 // argument.
184 // IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
185 // We recursively try to remove them.
186 template <class RangeType>
187 MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
188 RangeType &Operands) {
189 // Bail out on non-opt Phis.
190 if (NonOptPhis.count(Phi))
191 return Phi;
193 // Detect equal or self arguments
194 MemoryAccess *Same = nullptr;
195 for (auto &Op : Operands) {
196 // If the same or self, good so far
197 if (Op == Phi || Op == Same)
198 continue;
199 // not the same, return the phi since it's not eliminatable by us
200 if (Same)
201 return Phi;
202 Same = cast<MemoryAccess>(&*Op);
204 // Never found a non-self reference, the phi is undef
205 if (Same == nullptr)
206 return MSSA->getLiveOnEntryDef();
207 if (Phi) {
208 Phi->replaceAllUsesWith(Same);
209 removeMemoryAccess(Phi);
212 // We should only end up recursing in case we replaced something, in which
213 // case, we may have made other Phis trivial.
214 return recursePhi(Same);
217 void MemorySSAUpdater::insertUse(MemoryUse *MU) {
218 InsertedPHIs.clear();
219 MU->setDefiningAccess(getPreviousDef(MU));
220 // Unlike for defs, there is no extra work to do. Because uses do not create
221 // new may-defs, there are only two cases:
223 // 1. There was a def already below us, and therefore, we should not have
224 // created a phi node because it was already needed for the def.
226 // 2. There is no def below us, and therefore, there is no extra renaming work
227 // to do.
230 // Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
231 static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
232 MemoryAccess *NewDef) {
233 // Replace any operand with us an incoming block with the new defining
234 // access.
235 int i = MP->getBasicBlockIndex(BB);
236 assert(i != -1 && "Should have found the basic block in the phi");
237 // We can't just compare i against getNumOperands since one is signed and the
238 // other not. So use it to index into the block iterator.
239 for (auto BBIter = MP->block_begin() + i; BBIter != MP->block_end();
240 ++BBIter) {
241 if (*BBIter != BB)
242 break;
243 MP->setIncomingValue(i, NewDef);
244 ++i;
248 // A brief description of the algorithm:
249 // First, we compute what should define the new def, using the SSA
250 // construction algorithm.
251 // Then, we update the defs below us (and any new phi nodes) in the graph to
252 // point to the correct new defs, to ensure we only have one variable, and no
253 // disconnected stores.
254 void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
255 InsertedPHIs.clear();
257 // See if we had a local def, and if not, go hunting.
258 MemoryAccess *DefBefore = getPreviousDef(MD);
259 bool DefBeforeSameBlock = DefBefore->getBlock() == MD->getBlock();
261 // There is a def before us, which means we can replace any store/phi uses
262 // of that thing with us, since we are in the way of whatever was there
263 // before.
264 // We now define that def's memorydefs and memoryphis
265 if (DefBeforeSameBlock) {
266 for (auto UI = DefBefore->use_begin(), UE = DefBefore->use_end();
267 UI != UE;) {
268 Use &U = *UI++;
269 // Leave the MemoryUses alone.
270 // Also make sure we skip ourselves to avoid self references.
271 if (isa<MemoryUse>(U.getUser()) || U.getUser() == MD)
272 continue;
273 U.set(MD);
277 // and that def is now our defining access.
278 MD->setDefiningAccess(DefBefore);
280 SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());
281 if (!DefBeforeSameBlock) {
282 // If there was a local def before us, we must have the same effect it
283 // did. Because every may-def is the same, any phis/etc we would create, it
284 // would also have created. If there was no local def before us, we
285 // performed a global update, and have to search all successors and make
286 // sure we update the first def in each of them (following all paths until
287 // we hit the first def along each path). This may also insert phi nodes.
288 // TODO: There are other cases we can skip this work, such as when we have a
289 // single successor, and only used a straight line of single pred blocks
290 // backwards to find the def. To make that work, we'd have to track whether
291 // getDefRecursive only ever used the single predecessor case. These types
292 // of paths also only exist in between CFG simplifications.
293 FixupList.push_back(MD);
296 while (!FixupList.empty()) {
297 unsigned StartingPHISize = InsertedPHIs.size();
298 fixupDefs(FixupList);
299 FixupList.clear();
300 // Put any new phis on the fixup list, and process them
301 FixupList.append(InsertedPHIs.begin() + StartingPHISize, InsertedPHIs.end());
303 // Now that all fixups are done, rename all uses if we are asked.
304 if (RenameUses) {
305 SmallPtrSet<BasicBlock *, 16> Visited;
306 BasicBlock *StartBlock = MD->getBlock();
307 // We are guaranteed there is a def in the block, because we just got it
308 // handed to us in this function.
309 MemoryAccess *FirstDef = &*MSSA->getWritableBlockDefs(StartBlock)->begin();
310 // Convert to incoming value if it's a memorydef. A phi *is* already an
311 // incoming value.
312 if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
313 FirstDef = MD->getDefiningAccess();
315 MSSA->renamePass(MD->getBlock(), FirstDef, Visited);
316 // We just inserted a phi into this block, so the incoming value will become
317 // the phi anyway, so it does not matter what we pass.
318 for (auto &MP : InsertedPHIs) {
319 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);
320 if (Phi)
321 MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
326 void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<WeakVH> &Vars) {
327 SmallPtrSet<const BasicBlock *, 8> Seen;
328 SmallVector<const BasicBlock *, 16> Worklist;
329 for (auto &Var : Vars) {
330 MemoryAccess *NewDef = dyn_cast_or_null<MemoryAccess>(Var);
331 if (!NewDef)
332 continue;
333 // First, see if there is a local def after the operand.
334 auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
335 auto DefIter = NewDef->getDefsIterator();
337 // The temporary Phi is being fixed, unmark it for not to optimize.
338 if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(NewDef))
339 NonOptPhis.erase(Phi);
341 // If there is a local def after us, we only have to rename that.
342 if (++DefIter != Defs->end()) {
343 cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);
344 continue;
347 // Otherwise, we need to search down through the CFG.
348 // For each of our successors, handle it directly if their is a phi, or
349 // place on the fixup worklist.
350 for (const auto *S : successors(NewDef->getBlock())) {
351 if (auto *MP = MSSA->getMemoryAccess(S))
352 setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef);
353 else
354 Worklist.push_back(S);
357 while (!Worklist.empty()) {
358 const BasicBlock *FixupBlock = Worklist.back();
359 Worklist.pop_back();
361 // Get the first def in the block that isn't a phi node.
362 if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) {
363 auto *FirstDef = &*Defs->begin();
364 // The loop above and below should have taken care of phi nodes
365 assert(!isa<MemoryPhi>(FirstDef) &&
366 "Should have already handled phi nodes!");
367 // We are now this def's defining access, make sure we actually dominate
368 // it
369 assert(MSSA->dominates(NewDef, FirstDef) &&
370 "Should have dominated the new access");
372 // This may insert new phi nodes, because we are not guaranteed the
373 // block we are processing has a single pred, and depending where the
374 // store was inserted, it may require phi nodes below it.
375 cast<MemoryDef>(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef));
376 return;
378 // We didn't find a def, so we must continue.
379 for (const auto *S : successors(FixupBlock)) {
380 // If there is a phi node, handle it.
381 // Otherwise, put the block on the worklist
382 if (auto *MP = MSSA->getMemoryAccess(S))
383 setMemoryPhiValueForBlock(MP, FixupBlock, NewDef);
384 else {
385 // If we cycle, we should have ended up at a phi node that we already
386 // processed. FIXME: Double check this
387 if (!Seen.insert(S).second)
388 continue;
389 Worklist.push_back(S);
396 void MemorySSAUpdater::removeEdge(BasicBlock *From, BasicBlock *To) {
397 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
398 MPhi->unorderedDeleteIncomingBlock(From);
399 if (MPhi->getNumIncomingValues() == 1)
400 removeMemoryAccess(MPhi);
404 void MemorySSAUpdater::removeDuplicatePhiEdgesBetween(BasicBlock *From,
405 BasicBlock *To) {
406 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
407 bool Found = false;
408 MPhi->unorderedDeleteIncomingIf([&](const MemoryAccess *, BasicBlock *B) {
409 if (From != B)
410 return false;
411 if (Found)
412 return true;
413 Found = true;
414 return false;
416 if (MPhi->getNumIncomingValues() == 1)
417 removeMemoryAccess(MPhi);
421 void MemorySSAUpdater::cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
422 const ValueToValueMapTy &VMap,
423 PhiToDefMap &MPhiMap) {
424 auto GetNewDefiningAccess = [&](MemoryAccess *MA) -> MemoryAccess * {
425 MemoryAccess *InsnDefining = MA;
426 if (MemoryUseOrDef *DefMUD = dyn_cast<MemoryUseOrDef>(InsnDefining)) {
427 if (!MSSA->isLiveOnEntryDef(DefMUD)) {
428 Instruction *DefMUDI = DefMUD->getMemoryInst();
429 assert(DefMUDI && "Found MemoryUseOrDef with no Instruction.");
430 if (Instruction *NewDefMUDI =
431 cast_or_null<Instruction>(VMap.lookup(DefMUDI)))
432 InsnDefining = MSSA->getMemoryAccess(NewDefMUDI);
434 } else {
435 MemoryPhi *DefPhi = cast<MemoryPhi>(InsnDefining);
436 if (MemoryAccess *NewDefPhi = MPhiMap.lookup(DefPhi))
437 InsnDefining = NewDefPhi;
439 assert(InsnDefining && "Defining instruction cannot be nullptr.");
440 return InsnDefining;
443 const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
444 if (!Acc)
445 return;
446 for (const MemoryAccess &MA : *Acc) {
447 if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&MA)) {
448 Instruction *Insn = MUD->getMemoryInst();
449 // Entry does not exist if the clone of the block did not clone all
450 // instructions. This occurs in LoopRotate when cloning instructions
451 // from the old header to the old preheader. The cloned instruction may
452 // also be a simplified Value, not an Instruction (see LoopRotate).
453 if (Instruction *NewInsn =
454 dyn_cast_or_null<Instruction>(VMap.lookup(Insn))) {
455 MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(
456 NewInsn, GetNewDefiningAccess(MUD->getDefiningAccess()), MUD);
457 MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
463 void MemorySSAUpdater::updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
464 ArrayRef<BasicBlock *> ExitBlocks,
465 const ValueToValueMapTy &VMap,
466 bool IgnoreIncomingWithNoClones) {
467 PhiToDefMap MPhiMap;
469 auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) {
470 assert(Phi && NewPhi && "Invalid Phi nodes.");
471 BasicBlock *NewPhiBB = NewPhi->getBlock();
472 SmallPtrSet<BasicBlock *, 4> NewPhiBBPreds(pred_begin(NewPhiBB),
473 pred_end(NewPhiBB));
474 for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; ++It) {
475 MemoryAccess *IncomingAccess = Phi->getIncomingValue(It);
476 BasicBlock *IncBB = Phi->getIncomingBlock(It);
478 if (BasicBlock *NewIncBB = cast_or_null<BasicBlock>(VMap.lookup(IncBB)))
479 IncBB = NewIncBB;
480 else if (IgnoreIncomingWithNoClones)
481 continue;
483 // Now we have IncBB, and will need to add incoming from it to NewPhi.
485 // If IncBB is not a predecessor of NewPhiBB, then do not add it.
486 // NewPhiBB was cloned without that edge.
487 if (!NewPhiBBPreds.count(IncBB))
488 continue;
490 // Determine incoming value and add it as incoming from IncBB.
491 if (MemoryUseOrDef *IncMUD = dyn_cast<MemoryUseOrDef>(IncomingAccess)) {
492 if (!MSSA->isLiveOnEntryDef(IncMUD)) {
493 Instruction *IncI = IncMUD->getMemoryInst();
494 assert(IncI && "Found MemoryUseOrDef with no Instruction.");
495 if (Instruction *NewIncI =
496 cast_or_null<Instruction>(VMap.lookup(IncI))) {
497 IncMUD = MSSA->getMemoryAccess(NewIncI);
498 assert(IncMUD &&
499 "MemoryUseOrDef cannot be null, all preds processed.");
502 NewPhi->addIncoming(IncMUD, IncBB);
503 } else {
504 MemoryPhi *IncPhi = cast<MemoryPhi>(IncomingAccess);
505 if (MemoryAccess *NewDefPhi = MPhiMap.lookup(IncPhi))
506 NewPhi->addIncoming(NewDefPhi, IncBB);
507 else
508 NewPhi->addIncoming(IncPhi, IncBB);
513 auto ProcessBlock = [&](BasicBlock *BB) {
514 BasicBlock *NewBlock = cast_or_null<BasicBlock>(VMap.lookup(BB));
515 if (!NewBlock)
516 return;
518 assert(!MSSA->getWritableBlockAccesses(NewBlock) &&
519 "Cloned block should have no accesses");
521 // Add MemoryPhi.
522 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) {
523 MemoryPhi *NewPhi = MSSA->createMemoryPhi(NewBlock);
524 MPhiMap[MPhi] = NewPhi;
526 // Update Uses and Defs.
527 cloneUsesAndDefs(BB, NewBlock, VMap, MPhiMap);
530 for (auto BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
531 ProcessBlock(BB);
533 for (auto BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
534 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
535 if (MemoryAccess *NewPhi = MPhiMap.lookup(MPhi))
536 FixPhiIncomingValues(MPhi, cast<MemoryPhi>(NewPhi));
539 void MemorySSAUpdater::updateForClonedBlockIntoPred(
540 BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM) {
541 // All defs/phis from outside BB that are used in BB, are valid uses in P1.
542 // Since those defs/phis must have dominated BB, and also dominate P1.
543 // Defs from BB being used in BB will be replaced with the cloned defs from
544 // VM. The uses of BB's Phi (if it exists) in BB will be replaced by the
545 // incoming def into the Phi from P1.
546 PhiToDefMap MPhiMap;
547 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
548 MPhiMap[MPhi] = MPhi->getIncomingValueForBlock(P1);
549 cloneUsesAndDefs(BB, P1, VM, MPhiMap);
552 template <typename Iter>
553 void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop(
554 ArrayRef<BasicBlock *> ExitBlocks, Iter ValuesBegin, Iter ValuesEnd,
555 DominatorTree &DT) {
556 SmallVector<CFGUpdate, 4> Updates;
557 // Update/insert phis in all successors of exit blocks.
558 for (auto *Exit : ExitBlocks)
559 for (const ValueToValueMapTy *VMap : make_range(ValuesBegin, ValuesEnd))
560 if (BasicBlock *NewExit = cast_or_null<BasicBlock>(VMap->lookup(Exit))) {
561 BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
562 Updates.push_back({DT.Insert, NewExit, ExitSucc});
564 applyInsertUpdates(Updates, DT);
567 void MemorySSAUpdater::updateExitBlocksForClonedLoop(
568 ArrayRef<BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap,
569 DominatorTree &DT) {
570 const ValueToValueMapTy *const Arr[] = {&VMap};
571 privateUpdateExitBlocksForClonedLoop(ExitBlocks, std::begin(Arr),
572 std::end(Arr), DT);
575 void MemorySSAUpdater::updateExitBlocksForClonedLoop(
576 ArrayRef<BasicBlock *> ExitBlocks,
577 ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT) {
578 auto GetPtr = [&](const std::unique_ptr<ValueToValueMapTy> &I) {
579 return I.get();
581 using MappedIteratorType =
582 mapped_iterator<const std::unique_ptr<ValueToValueMapTy> *,
583 decltype(GetPtr)>;
584 auto MapBegin = MappedIteratorType(VMaps.begin(), GetPtr);
585 auto MapEnd = MappedIteratorType(VMaps.end(), GetPtr);
586 privateUpdateExitBlocksForClonedLoop(ExitBlocks, MapBegin, MapEnd, DT);
589 void MemorySSAUpdater::applyUpdates(ArrayRef<CFGUpdate> Updates,
590 DominatorTree &DT) {
591 SmallVector<CFGUpdate, 4> RevDeleteUpdates;
592 SmallVector<CFGUpdate, 4> InsertUpdates;
593 for (auto &Update : Updates) {
594 if (Update.getKind() == DT.Insert)
595 InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
596 else
597 RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
600 if (!RevDeleteUpdates.empty()) {
601 // Update for inserted edges: use newDT and snapshot CFG as if deletes had
602 // not occured.
603 // FIXME: This creates a new DT, so it's more expensive to do mix
604 // delete/inserts vs just inserts. We can do an incremental update on the DT
605 // to revert deletes, than re-delete the edges. Teaching DT to do this, is
606 // part of a pending cleanup.
607 DominatorTree NewDT(DT, RevDeleteUpdates);
608 GraphDiff<BasicBlock *> GD(RevDeleteUpdates);
609 applyInsertUpdates(InsertUpdates, NewDT, &GD);
610 } else {
611 GraphDiff<BasicBlock *> GD;
612 applyInsertUpdates(InsertUpdates, DT, &GD);
615 // Update for deleted edges
616 for (auto &Update : RevDeleteUpdates)
617 removeEdge(Update.getFrom(), Update.getTo());
620 void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
621 DominatorTree &DT) {
622 GraphDiff<BasicBlock *> GD;
623 applyInsertUpdates(Updates, DT, &GD);
626 void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
627 DominatorTree &DT,
628 const GraphDiff<BasicBlock *> *GD) {
629 // Get recursive last Def, assuming well formed MSSA and updated DT.
630 auto GetLastDef = [&](BasicBlock *BB) -> MemoryAccess * {
631 while (true) {
632 MemorySSA::DefsList *Defs = MSSA->getWritableBlockDefs(BB);
633 // Return last Def or Phi in BB, if it exists.
634 if (Defs)
635 return &*(--Defs->end());
637 // Check number of predecessors, we only care if there's more than one.
638 unsigned Count = 0;
639 BasicBlock *Pred = nullptr;
640 for (auto &Pair : children<GraphDiffInvBBPair>({GD, BB})) {
641 Pred = Pair.second;
642 Count++;
643 if (Count == 2)
644 break;
647 // If BB has multiple predecessors, get last definition from IDom.
648 if (Count != 1) {
649 // [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its
650 // DT is invalidated. Return LoE as its last def. This will be added to
651 // MemoryPhi node, and later deleted when the block is deleted.
652 if (!DT.getNode(BB))
653 return MSSA->getLiveOnEntryDef();
654 if (auto *IDom = DT.getNode(BB)->getIDom())
655 if (IDom->getBlock() != BB) {
656 BB = IDom->getBlock();
657 continue;
659 return MSSA->getLiveOnEntryDef();
660 } else {
661 // Single predecessor, BB cannot be dead. GetLastDef of Pred.
662 assert(Count == 1 && Pred && "Single predecessor expected.");
663 BB = Pred;
666 llvm_unreachable("Unable to get last definition.");
669 // Get nearest IDom given a set of blocks.
670 // TODO: this can be optimized by starting the search at the node with the
671 // lowest level (highest in the tree).
672 auto FindNearestCommonDominator =
673 [&](const SmallSetVector<BasicBlock *, 2> &BBSet) -> BasicBlock * {
674 BasicBlock *PrevIDom = *BBSet.begin();
675 for (auto *BB : BBSet)
676 PrevIDom = DT.findNearestCommonDominator(PrevIDom, BB);
677 return PrevIDom;
680 // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not
681 // include CurrIDom.
682 auto GetNoLongerDomBlocks =
683 [&](BasicBlock *PrevIDom, BasicBlock *CurrIDom,
684 SmallVectorImpl<BasicBlock *> &BlocksPrevDom) {
685 if (PrevIDom == CurrIDom)
686 return;
687 BlocksPrevDom.push_back(PrevIDom);
688 BasicBlock *NextIDom = PrevIDom;
689 while (BasicBlock *UpIDom =
690 DT.getNode(NextIDom)->getIDom()->getBlock()) {
691 if (UpIDom == CurrIDom)
692 break;
693 BlocksPrevDom.push_back(UpIDom);
694 NextIDom = UpIDom;
698 // Map a BB to its predecessors: added + previously existing. To get a
699 // deterministic order, store predecessors as SetVectors. The order in each
700 // will be defined by teh order in Updates (fixed) and the order given by
701 // children<> (also fixed). Since we further iterate over these ordered sets,
702 // we lose the information of multiple edges possibly existing between two
703 // blocks, so we'll keep and EdgeCount map for that.
704 // An alternate implementation could keep unordered set for the predecessors,
705 // traverse either Updates or children<> each time to get the deterministic
706 // order, and drop the usage of EdgeCount. This alternate approach would still
707 // require querying the maps for each predecessor, and children<> call has
708 // additional computation inside for creating the snapshot-graph predecessors.
709 // As such, we favor using a little additional storage and less compute time.
710 // This decision can be revisited if we find the alternative more favorable.
712 struct PredInfo {
713 SmallSetVector<BasicBlock *, 2> Added;
714 SmallSetVector<BasicBlock *, 2> Prev;
716 SmallDenseMap<BasicBlock *, PredInfo> PredMap;
718 for (auto &Edge : Updates) {
719 BasicBlock *BB = Edge.getTo();
720 auto &AddedBlockSet = PredMap[BB].Added;
721 AddedBlockSet.insert(Edge.getFrom());
724 // Store all existing predecessor for each BB, at least one must exist.
725 SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>, int> EdgeCountMap;
726 SmallPtrSet<BasicBlock *, 2> NewBlocks;
727 for (auto &BBPredPair : PredMap) {
728 auto *BB = BBPredPair.first;
729 const auto &AddedBlockSet = BBPredPair.second.Added;
730 auto &PrevBlockSet = BBPredPair.second.Prev;
731 for (auto &Pair : children<GraphDiffInvBBPair>({GD, BB})) {
732 BasicBlock *Pi = Pair.second;
733 if (!AddedBlockSet.count(Pi))
734 PrevBlockSet.insert(Pi);
735 EdgeCountMap[{Pi, BB}]++;
738 if (PrevBlockSet.empty()) {
739 assert(pred_size(BB) == AddedBlockSet.size() && "Duplicate edges added.");
740 LLVM_DEBUG(
741 dbgs()
742 << "Adding a predecessor to a block with no predecessors. "
743 "This must be an edge added to a new, likely cloned, block. "
744 "Its memory accesses must be already correct, assuming completed "
745 "via the updateExitBlocksForClonedLoop API. "
746 "Assert a single such edge is added so no phi addition or "
747 "additional processing is required.\n");
748 assert(AddedBlockSet.size() == 1 &&
749 "Can only handle adding one predecessor to a new block.");
750 // Need to remove new blocks from PredMap. Remove below to not invalidate
751 // iterator here.
752 NewBlocks.insert(BB);
755 // Nothing to process for new/cloned blocks.
756 for (auto *BB : NewBlocks)
757 PredMap.erase(BB);
759 SmallVector<BasicBlock *, 8> BlocksToProcess;
760 SmallVector<BasicBlock *, 16> BlocksWithDefsToReplace;
762 // First create MemoryPhis in all blocks that don't have one. Create in the
763 // order found in Updates, not in PredMap, to get deterministic numbering.
764 for (auto &Edge : Updates) {
765 BasicBlock *BB = Edge.getTo();
766 if (PredMap.count(BB) && !MSSA->getMemoryAccess(BB))
767 MSSA->createMemoryPhi(BB);
770 // Now we'll fill in the MemoryPhis with the right incoming values.
771 for (auto &BBPredPair : PredMap) {
772 auto *BB = BBPredPair.first;
773 const auto &PrevBlockSet = BBPredPair.second.Prev;
774 const auto &AddedBlockSet = BBPredPair.second.Added;
775 assert(!PrevBlockSet.empty() &&
776 "At least one previous predecessor must exist.");
778 // TODO: if this becomes a bottleneck, we can save on GetLastDef calls by
779 // keeping this map before the loop. We can reuse already populated entries
780 // if an edge is added from the same predecessor to two different blocks,
781 // and this does happen in rotate. Note that the map needs to be updated
782 // when deleting non-necessary phis below, if the phi is in the map by
783 // replacing the value with DefP1.
784 SmallDenseMap<BasicBlock *, MemoryAccess *> LastDefAddedPred;
785 for (auto *AddedPred : AddedBlockSet) {
786 auto *DefPn = GetLastDef(AddedPred);
787 assert(DefPn != nullptr && "Unable to find last definition.");
788 LastDefAddedPred[AddedPred] = DefPn;
791 MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB);
792 // If Phi is not empty, add an incoming edge from each added pred. Must
793 // still compute blocks with defs to replace for this block below.
794 if (NewPhi->getNumOperands()) {
795 for (auto *Pred : AddedBlockSet) {
796 auto *LastDefForPred = LastDefAddedPred[Pred];
797 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
798 NewPhi->addIncoming(LastDefForPred, Pred);
800 } else {
801 // Pick any existing predecessor and get its definition. All other
802 // existing predecessors should have the same one, since no phi existed.
803 auto *P1 = *PrevBlockSet.begin();
804 MemoryAccess *DefP1 = GetLastDef(P1);
806 // Check DefP1 against all Defs in LastDefPredPair. If all the same,
807 // nothing to add.
808 bool InsertPhi = false;
809 for (auto LastDefPredPair : LastDefAddedPred)
810 if (DefP1 != LastDefPredPair.second) {
811 InsertPhi = true;
812 break;
814 if (!InsertPhi) {
815 // Since NewPhi may be used in other newly added Phis, replace all uses
816 // of NewPhi with the definition coming from all predecessors (DefP1),
817 // before deleting it.
818 NewPhi->replaceAllUsesWith(DefP1);
819 removeMemoryAccess(NewPhi);
820 continue;
823 // Update Phi with new values for new predecessors and old value for all
824 // other predecessors. Since AddedBlockSet and PrevBlockSet are ordered
825 // sets, the order of entries in NewPhi is deterministic.
826 for (auto *Pred : AddedBlockSet) {
827 auto *LastDefForPred = LastDefAddedPred[Pred];
828 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
829 NewPhi->addIncoming(LastDefForPred, Pred);
831 for (auto *Pred : PrevBlockSet)
832 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
833 NewPhi->addIncoming(DefP1, Pred);
835 // Insert BB in the set of blocks that now have definition. We'll use this
836 // to compute IDF and add Phis there next.
837 BlocksToProcess.push_back(BB);
840 // Get all blocks that used to dominate BB and no longer do after adding
841 // AddedBlockSet, where PrevBlockSet are the previously known predecessors.
842 assert(DT.getNode(BB)->getIDom() && "BB does not have valid idom");
843 BasicBlock *PrevIDom = FindNearestCommonDominator(PrevBlockSet);
844 assert(PrevIDom && "Previous IDom should exists");
845 BasicBlock *NewIDom = DT.getNode(BB)->getIDom()->getBlock();
846 assert(NewIDom && "BB should have a new valid idom");
847 assert(DT.dominates(NewIDom, PrevIDom) &&
848 "New idom should dominate old idom");
849 GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);
852 // Compute IDF and add Phis in all IDF blocks that do not have one.
853 SmallVector<BasicBlock *, 32> IDFBlocks;
854 if (!BlocksToProcess.empty()) {
855 ForwardIDFCalculator IDFs(DT);
856 SmallPtrSet<BasicBlock *, 16> DefiningBlocks(BlocksToProcess.begin(),
857 BlocksToProcess.end());
858 IDFs.setDefiningBlocks(DefiningBlocks);
859 IDFs.calculate(IDFBlocks);
860 for (auto *BBIDF : IDFBlocks) {
861 if (auto *IDFPhi = MSSA->getMemoryAccess(BBIDF)) {
862 // Update existing Phi.
863 // FIXME: some updates may be redundant, try to optimize and skip some.
864 for (unsigned I = 0, E = IDFPhi->getNumIncomingValues(); I < E; ++I)
865 IDFPhi->setIncomingValue(I, GetLastDef(IDFPhi->getIncomingBlock(I)));
866 } else {
867 IDFPhi = MSSA->createMemoryPhi(BBIDF);
868 for (auto &Pair : children<GraphDiffInvBBPair>({GD, BBIDF})) {
869 BasicBlock *Pi = Pair.second;
870 IDFPhi->addIncoming(GetLastDef(Pi), Pi);
876 // Now for all defs in BlocksWithDefsToReplace, if there are uses they no
877 // longer dominate, replace those with the closest dominating def.
878 // This will also update optimized accesses, as they're also uses.
879 for (auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) {
880 if (auto DefsList = MSSA->getWritableBlockDefs(BlockWithDefsToReplace)) {
881 for (auto &DefToReplaceUses : *DefsList) {
882 BasicBlock *DominatingBlock = DefToReplaceUses.getBlock();
883 Value::use_iterator UI = DefToReplaceUses.use_begin(),
884 E = DefToReplaceUses.use_end();
885 for (; UI != E;) {
886 Use &U = *UI;
887 ++UI;
888 MemoryAccess *Usr = dyn_cast<MemoryAccess>(U.getUser());
889 if (MemoryPhi *UsrPhi = dyn_cast<MemoryPhi>(Usr)) {
890 BasicBlock *DominatedBlock = UsrPhi->getIncomingBlock(U);
891 if (!DT.dominates(DominatingBlock, DominatedBlock))
892 U.set(GetLastDef(DominatedBlock));
893 } else {
894 BasicBlock *DominatedBlock = Usr->getBlock();
895 if (!DT.dominates(DominatingBlock, DominatedBlock)) {
896 if (auto *DomBlPhi = MSSA->getMemoryAccess(DominatedBlock))
897 U.set(DomBlPhi);
898 else {
899 auto *IDom = DT.getNode(DominatedBlock)->getIDom();
900 assert(IDom && "Block must have a valid IDom.");
901 U.set(GetLastDef(IDom->getBlock()));
903 cast<MemoryUseOrDef>(Usr)->resetOptimized();
912 // Move What before Where in the MemorySSA IR.
913 template <class WhereType>
914 void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
915 WhereType Where) {
916 // Mark MemoryPhi users of What not to be optimized.
917 for (auto *U : What->users())
918 if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))
919 NonOptPhis.insert(PhiUser);
921 // Replace all our users with our defining access.
922 What->replaceAllUsesWith(What->getDefiningAccess());
924 // Let MemorySSA take care of moving it around in the lists.
925 MSSA->moveTo(What, BB, Where);
927 // Now reinsert it into the IR and do whatever fixups needed.
928 if (auto *MD = dyn_cast<MemoryDef>(What))
929 insertDef(MD);
930 else
931 insertUse(cast<MemoryUse>(What));
933 // Clear dangling pointers. We added all MemoryPhi users, but not all
934 // of them are removed by fixupDefs().
935 NonOptPhis.clear();
938 // Move What before Where in the MemorySSA IR.
939 void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
940 moveTo(What, Where->getBlock(), Where->getIterator());
943 // Move What after Where in the MemorySSA IR.
944 void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
945 moveTo(What, Where->getBlock(), ++Where->getIterator());
948 void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
949 MemorySSA::InsertionPlace Where) {
950 return moveTo(What, BB, Where);
953 // All accesses in To used to be in From. Move to end and update access lists.
954 void MemorySSAUpdater::moveAllAccesses(BasicBlock *From, BasicBlock *To,
955 Instruction *Start) {
957 MemorySSA::AccessList *Accs = MSSA->getWritableBlockAccesses(From);
958 if (!Accs)
959 return;
961 MemoryAccess *FirstInNew = nullptr;
962 for (Instruction &I : make_range(Start->getIterator(), To->end()))
963 if ((FirstInNew = MSSA->getMemoryAccess(&I)))
964 break;
965 if (!FirstInNew)
966 return;
968 auto *MUD = cast<MemoryUseOrDef>(FirstInNew);
969 do {
970 auto NextIt = ++MUD->getIterator();
971 MemoryUseOrDef *NextMUD = (!Accs || NextIt == Accs->end())
972 ? nullptr
973 : cast<MemoryUseOrDef>(&*NextIt);
974 MSSA->moveTo(MUD, To, MemorySSA::End);
975 // Moving MUD from Accs in the moveTo above, may delete Accs, so we need to
976 // retrieve it again.
977 Accs = MSSA->getWritableBlockAccesses(From);
978 MUD = NextMUD;
979 } while (MUD);
982 void MemorySSAUpdater::moveAllAfterSpliceBlocks(BasicBlock *From,
983 BasicBlock *To,
984 Instruction *Start) {
985 assert(MSSA->getBlockAccesses(To) == nullptr &&
986 "To block is expected to be free of MemoryAccesses.");
987 moveAllAccesses(From, To, Start);
988 for (BasicBlock *Succ : successors(To))
989 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
990 MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
993 void MemorySSAUpdater::moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
994 Instruction *Start) {
995 assert(From->getSinglePredecessor() == To &&
996 "From block is expected to have a single predecessor (To).");
997 moveAllAccesses(From, To, Start);
998 for (BasicBlock *Succ : successors(From))
999 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
1000 MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
1003 /// If all arguments of a MemoryPHI are defined by the same incoming
1004 /// argument, return that argument.
1005 static MemoryAccess *onlySingleValue(MemoryPhi *MP) {
1006 MemoryAccess *MA = nullptr;
1008 for (auto &Arg : MP->operands()) {
1009 if (!MA)
1010 MA = cast<MemoryAccess>(Arg);
1011 else if (MA != Arg)
1012 return nullptr;
1014 return MA;
1017 void MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(
1018 BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
1019 bool IdenticalEdgesWereMerged) {
1020 assert(!MSSA->getWritableBlockAccesses(New) &&
1021 "Access list should be null for a new block.");
1022 MemoryPhi *Phi = MSSA->getMemoryAccess(Old);
1023 if (!Phi)
1024 return;
1025 if (Old->hasNPredecessors(1)) {
1026 assert(pred_size(New) == Preds.size() &&
1027 "Should have moved all predecessors.");
1028 MSSA->moveTo(Phi, New, MemorySSA::Beginning);
1029 } else {
1030 assert(!Preds.empty() && "Must be moving at least one predecessor to the "
1031 "new immediate predecessor.");
1032 MemoryPhi *NewPhi = MSSA->createMemoryPhi(New);
1033 SmallPtrSet<BasicBlock *, 16> PredsSet(Preds.begin(), Preds.end());
1034 // Currently only support the case of removing a single incoming edge when
1035 // identical edges were not merged.
1036 if (!IdenticalEdgesWereMerged)
1037 assert(PredsSet.size() == Preds.size() &&
1038 "If identical edges were not merged, we cannot have duplicate "
1039 "blocks in the predecessors");
1040 Phi->unorderedDeleteIncomingIf([&](MemoryAccess *MA, BasicBlock *B) {
1041 if (PredsSet.count(B)) {
1042 NewPhi->addIncoming(MA, B);
1043 if (!IdenticalEdgesWereMerged)
1044 PredsSet.erase(B);
1045 return true;
1047 return false;
1049 Phi->addIncoming(NewPhi, New);
1050 if (onlySingleValue(NewPhi))
1051 removeMemoryAccess(NewPhi);
1055 void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA) {
1056 assert(!MSSA->isLiveOnEntryDef(MA) &&
1057 "Trying to remove the live on entry def");
1058 // We can only delete phi nodes if they have no uses, or we can replace all
1059 // uses with a single definition.
1060 MemoryAccess *NewDefTarget = nullptr;
1061 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
1062 // Note that it is sufficient to know that all edges of the phi node have
1063 // the same argument. If they do, by the definition of dominance frontiers
1064 // (which we used to place this phi), that argument must dominate this phi,
1065 // and thus, must dominate the phi's uses, and so we will not hit the assert
1066 // below.
1067 NewDefTarget = onlySingleValue(MP);
1068 assert((NewDefTarget || MP->use_empty()) &&
1069 "We can't delete this memory phi");
1070 } else {
1071 NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
1074 // Re-point the uses at our defining access
1075 if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
1076 // Reset optimized on users of this store, and reset the uses.
1077 // A few notes:
1078 // 1. This is a slightly modified version of RAUW to avoid walking the
1079 // uses twice here.
1080 // 2. If we wanted to be complete, we would have to reset the optimized
1081 // flags on users of phi nodes if doing the below makes a phi node have all
1082 // the same arguments. Instead, we prefer users to removeMemoryAccess those
1083 // phi nodes, because doing it here would be N^3.
1084 if (MA->hasValueHandle())
1085 ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
1086 // Note: We assume MemorySSA is not used in metadata since it's not really
1087 // part of the IR.
1089 while (!MA->use_empty()) {
1090 Use &U = *MA->use_begin();
1091 if (auto *MUD = dyn_cast<MemoryUseOrDef>(U.getUser()))
1092 MUD->resetOptimized();
1093 U.set(NewDefTarget);
1097 // The call below to erase will destroy MA, so we can't change the order we
1098 // are doing things here
1099 MSSA->removeFromLookups(MA);
1100 MSSA->removeFromLists(MA);
1103 void MemorySSAUpdater::removeBlocks(
1104 const SmallPtrSetImpl<BasicBlock *> &DeadBlocks) {
1105 // First delete all uses of BB in MemoryPhis.
1106 for (BasicBlock *BB : DeadBlocks) {
1107 Instruction *TI = BB->getTerminator();
1108 assert(TI && "Basic block expected to have a terminator instruction");
1109 for (BasicBlock *Succ : successors(TI))
1110 if (!DeadBlocks.count(Succ))
1111 if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {
1112 MP->unorderedDeleteIncomingBlock(BB);
1113 if (MP->getNumIncomingValues() == 1)
1114 removeMemoryAccess(MP);
1116 // Drop all references of all accesses in BB
1117 if (MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB))
1118 for (MemoryAccess &MA : *Acc)
1119 MA.dropAllReferences();
1122 // Next, delete all memory accesses in each block
1123 for (BasicBlock *BB : DeadBlocks) {
1124 MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB);
1125 if (!Acc)
1126 continue;
1127 for (auto AB = Acc->begin(), AE = Acc->end(); AB != AE;) {
1128 MemoryAccess *MA = &*AB;
1129 ++AB;
1130 MSSA->removeFromLookups(MA);
1131 MSSA->removeFromLists(MA);
1136 MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
1137 Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
1138 MemorySSA::InsertionPlace Point) {
1139 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1140 MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
1141 return NewAccess;
1144 MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore(
1145 Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
1146 assert(I->getParent() == InsertPt->getBlock() &&
1147 "New and old access must be in the same block");
1148 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1149 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1150 InsertPt->getIterator());
1151 return NewAccess;
1154 MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(
1155 Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
1156 assert(I->getParent() == InsertPt->getBlock() &&
1157 "New and old access must be in the same block");
1158 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1159 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1160 ++InsertPt->getIterator());
1161 return NewAccess;