1 //===-- MemorySSAUpdater.cpp - Memory SSA Updater--------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------===//
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"
30 #define DEBUG_TYPE "memoryssa"
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(
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
});
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
});
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
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
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());
101 for (auto *Pred
: predecessors(BB
))
102 Phi
->addIncoming(&*PhiOps
[i
++], Pred
);
103 InsertedPHIs
.push_back(Phi
);
108 // Set ourselves up for the next variable by resetting visited state.
109 VisitedBlocks
.erase(BB
);
110 CachedPreviousDef
.insert({BB
, 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
120 MemoryAccess
*MemorySSAUpdater::getPreviousDef(MemoryAccess
*MA
) {
121 if (auto *LocalResult
= getPreviousDefInBlock(MA
))
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.
135 // If this is a def, we can just use the def iterators.
136 if (!isa
<MemoryUse
>(MA
)) {
137 auto Iter
= MA
->getReverseDefsIterator();
139 if (Iter
!= Defs
->rend())
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.
154 // This starts at the end of block
155 MemoryAccess
*MemorySSAUpdater::getPreviousDefFromEnd(
157 DenseMap
<BasicBlock
*, TrackingVH
<MemoryAccess
>> &CachedPreviousDef
) {
158 auto *Defs
= MSSA
->getWritableBlockDefs(BB
);
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
) {
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
);
181 // Eliminate trivial phis
182 // Phis are trivial if they are defined either by themselves, or all the same
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
))
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
)
199 // not the same, return the phi since it's not eliminatable by us
202 Same
= cast
<MemoryAccess
>(&*Op
);
204 // Never found a non-self reference, the phi is undef
206 return MSSA
->getLiveOnEntryDef();
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
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
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();
243 MP
->setIncomingValue(i
, NewDef
);
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
264 // We now define that def's memorydefs and memoryphis
265 if (DefBeforeSameBlock
) {
266 for (auto UI
= DefBefore
->use_begin(), UE
= DefBefore
->use_end();
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
)
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
);
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.
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
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
);
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
);
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
);
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
);
354 Worklist
.push_back(S
);
357 while (!Worklist
.empty()) {
358 const BasicBlock
*FixupBlock
= Worklist
.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
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
));
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
);
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
)
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
,
406 if (MemoryPhi
*MPhi
= MSSA
->getMemoryAccess(To
)) {
408 MPhi
->unorderedDeleteIncomingIf([&](const MemoryAccess
*, BasicBlock
*B
) {
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
);
435 MemoryPhi
*DefPhi
= cast
<MemoryPhi
>(InsnDefining
);
436 if (MemoryAccess
*NewDefPhi
= MPhiMap
.lookup(DefPhi
))
437 InsnDefining
= NewDefPhi
;
439 assert(InsnDefining
&& "Defining instruction cannot be nullptr.");
443 const MemorySSA::AccessList
*Acc
= MSSA
->getBlockAccesses(BB
);
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
) {
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
),
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
)))
480 else if (IgnoreIncomingWithNoClones
)
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
))
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
);
499 "MemoryUseOrDef cannot be null, all preds processed.");
502 NewPhi
->addIncoming(IncMUD
, IncBB
);
504 MemoryPhi
*IncPhi
= cast
<MemoryPhi
>(IncomingAccess
);
505 if (MemoryAccess
*NewDefPhi
= MPhiMap
.lookup(IncPhi
))
506 NewPhi
->addIncoming(NewDefPhi
, IncBB
);
508 NewPhi
->addIncoming(IncPhi
, IncBB
);
513 auto ProcessBlock
= [&](BasicBlock
*BB
) {
514 BasicBlock
*NewBlock
= cast_or_null
<BasicBlock
>(VMap
.lookup(BB
));
518 assert(!MSSA
->getWritableBlockAccesses(NewBlock
) &&
519 "Cloned block should have no accesses");
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
))
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.
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
,
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
,
570 const ValueToValueMapTy
*const Arr
[] = {&VMap
};
571 privateUpdateExitBlocksForClonedLoop(ExitBlocks
, std::begin(Arr
),
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
) {
581 using MappedIteratorType
=
582 mapped_iterator
<const std::unique_ptr
<ValueToValueMapTy
> *,
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
,
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()});
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
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
);
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
,
622 GraphDiff
<BasicBlock
*> GD
;
623 applyInsertUpdates(Updates
, DT
, &GD
);
626 void MemorySSAUpdater::applyInsertUpdates(ArrayRef
<CFGUpdate
> Updates
,
628 const GraphDiff
<BasicBlock
*> *GD
) {
629 // Get recursive last Def, assuming well formed MSSA and updated DT.
630 auto GetLastDef
= [&](BasicBlock
*BB
) -> MemoryAccess
* {
632 MemorySSA::DefsList
*Defs
= MSSA
->getWritableBlockDefs(BB
);
633 // Return last Def or Phi in BB, if it exists.
635 return &*(--Defs
->end());
637 // Check number of predecessors, we only care if there's more than one.
639 BasicBlock
*Pred
= nullptr;
640 for (auto &Pair
: children
<GraphDiffInvBBPair
>({GD
, BB
})) {
647 // If BB has multiple predecessors, get last definition from IDom.
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.
653 return MSSA
->getLiveOnEntryDef();
654 if (auto *IDom
= DT
.getNode(BB
)->getIDom())
655 if (IDom
->getBlock() != BB
) {
656 BB
= IDom
->getBlock();
659 return MSSA
->getLiveOnEntryDef();
661 // Single predecessor, BB cannot be dead. GetLastDef of Pred.
662 assert(Count
== 1 && Pred
&& "Single predecessor expected.");
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
);
680 // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not
682 auto GetNoLongerDomBlocks
=
683 [&](BasicBlock
*PrevIDom
, BasicBlock
*CurrIDom
,
684 SmallVectorImpl
<BasicBlock
*> &BlocksPrevDom
) {
685 if (PrevIDom
== CurrIDom
)
687 BlocksPrevDom
.push_back(PrevIDom
);
688 BasicBlock
*NextIDom
= PrevIDom
;
689 while (BasicBlock
*UpIDom
=
690 DT
.getNode(NextIDom
)->getIDom()->getBlock()) {
691 if (UpIDom
== CurrIDom
)
693 BlocksPrevDom
.push_back(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.
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.");
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
752 NewBlocks
.insert(BB
);
755 // Nothing to process for new/cloned blocks.
756 for (auto *BB
: NewBlocks
)
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
);
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,
808 bool InsertPhi
= false;
809 for (auto LastDefPredPair
: LastDefAddedPred
)
810 if (DefP1
!= LastDefPredPair
.second
) {
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
);
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
)));
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();
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
));
894 BasicBlock
*DominatedBlock
= Usr
->getBlock();
895 if (!DT
.dominates(DominatingBlock
, DominatedBlock
)) {
896 if (auto *DomBlPhi
= MSSA
->getMemoryAccess(DominatedBlock
))
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
,
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
))
931 insertUse(cast
<MemoryUse
>(What
));
933 // Clear dangling pointers. We added all MemoryPhi users, but not all
934 // of them are removed by fixupDefs().
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
);
961 MemoryAccess
*FirstInNew
= nullptr;
962 for (Instruction
&I
: make_range(Start
->getIterator(), To
->end()))
963 if ((FirstInNew
= MSSA
->getMemoryAccess(&I
)))
968 auto *MUD
= cast
<MemoryUseOrDef
>(FirstInNew
);
970 auto NextIt
= ++MUD
->getIterator();
971 MemoryUseOrDef
*NextMUD
= (!Accs
|| NextIt
== Accs
->end())
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
);
982 void MemorySSAUpdater::moveAllAfterSpliceBlocks(BasicBlock
*From
,
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()) {
1010 MA
= cast
<MemoryAccess
>(Arg
);
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
);
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
);
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
)
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
1067 NewDefTarget
= onlySingleValue(MP
);
1068 assert((NewDefTarget
|| MP
->use_empty()) &&
1069 "We can't delete this memory phi");
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.
1078 // 1. This is a slightly modified version of RAUW to avoid walking the
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
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
);
1127 for (auto AB
= Acc
->begin(), AE
= Acc
->end(); AB
!= AE
;) {
1128 MemoryAccess
*MA
= &*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
);
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());
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());