1 //===-- MemorySSAUpdater.cpp - Memory SSA Updater--------------------===//
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-exception
7 //===----------------------------------------------------------------===//
9 // This file implements the MemorySSAUpdater class.
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"
24 #define DEBUG_TYPE "memoryssa"
27 // This is the marker algorithm from "Simple and Efficient Construction of
28 // Static Single Assignment Form"
29 // The simple, non-marker algorithm places phi nodes at any join
30 // 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 visit
32 // 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 control
35 // flow, where phi nodes may be in cycles with themselves, but unnecessary.
36 MemoryAccess
*MemorySSAUpdater::getPreviousDefRecursive(
38 DenseMap
<BasicBlock
*, TrackingVH
<MemoryAccess
>> &CachedPreviousDef
) {
39 // First, do a cache lookup. Without this cache, certain CFG structures
40 // (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
;
45 // If this method is called from an unreachable block, return LoE.
46 if (!MSSA
->DT
->isReachableFromEntry(BB
))
47 return MSSA
->getLiveOnEntryDef();
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
});
57 if (VisitedBlocks
.count(BB
)) {
58 // We hit our node again, meaning we had a cycle, we must insert a phi
59 // node to break it so we have an operand. The only case this will
60 // insert useless phis is if we have irreducible control flow.
61 MemoryAccess
*Result
= MSSA
->createMemoryPhi(BB
);
62 CachedPreviousDef
.insert({BB
, Result
});
66 if (VisitedBlocks
.insert(BB
).second
) {
67 // Mark us visited so we can detect a cycle
68 SmallVector
<TrackingVH
<MemoryAccess
>, 8> PhiOps
;
70 // Recurse to get the values in our predecessors for placement of a
71 // potential phi node. This will insert phi nodes if we cycle in order to
72 // 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
);
79 SingleAccess
= IncomingAccess
;
80 else if (IncomingAccess
!= SingleAccess
)
81 UniqueIncomingAccess
= false;
82 PhiOps
.push_back(IncomingAccess
);
84 PhiOps
.push_back(MSSA
->getLiveOnEntryDef());
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 okay
89 MemoryPhi
*Phi
= dyn_cast_or_null
<MemoryPhi
>(MSSA
->getMemoryAccess(BB
));
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 phi
94 if (Result
== Phi
&& UniqueIncomingAccess
&& SingleAccess
) {
95 // A concrete Phi only exists if we created an empty one to break a cycle.
97 assert(Phi
->operands().empty() && "Expected empty Phi");
98 Phi
->replaceAllUsesWith(SingleAccess
);
99 removeMemoryAccess(Phi
);
101 Result
= SingleAccess
;
102 } else if (Result
== Phi
&& !(UniqueIncomingAccess
&& SingleAccess
)) {
104 Phi
= MSSA
->createMemoryPhi(BB
);
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 just
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());
118 for (auto *Pred
: predecessors(BB
))
119 Phi
->addIncoming(&*PhiOps
[i
++], Pred
);
120 InsertedPHIs
.push_back(Phi
);
125 // Set ourselves up for the next variable by resetting visited state.
126 VisitedBlocks
.erase(BB
);
127 CachedPreviousDef
.insert({BB
, Result
});
130 llvm_unreachable("Should have hit one of the three cases above");
133 // This starts at the memory access, and goes backwards in the block to find the
134 // 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 single
137 MemoryAccess
*MemorySSAUpdater::getPreviousDef(MemoryAccess
*MA
) {
138 if (auto *LocalResult
= getPreviousDefInBlock(MA
))
140 DenseMap
<BasicBlock
*, TrackingVH
<MemoryAccess
>> CachedPreviousDef
;
141 return getPreviousDefRecursive(MA
->getBlock(), CachedPreviousDef
);
144 // This starts at the memory access, and goes backwards in the block to the find
145 // the previous definition. If the definition is not found in the block of the
146 // access, it returns nullptr.
147 MemoryAccess
*MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess
*MA
) {
148 auto *Defs
= MSSA
->getWritableBlockDefs(MA
->getBlock());
150 // It's possible there are no defs, or we got handed the first def to start.
152 // If this is a def, we can just use the def iterators.
153 if (!isa
<MemoryUse
>(MA
)) {
154 auto Iter
= MA
->getReverseDefsIterator();
156 if (Iter
!= Defs
->rend())
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.
171 // This starts at the end of block
172 MemoryAccess
*MemorySSAUpdater::getPreviousDefFromEnd(
174 DenseMap
<BasicBlock
*, TrackingVH
<MemoryAccess
>> &CachedPreviousDef
) {
175 auto *Defs
= MSSA
->getWritableBlockDefs(BB
);
178 CachedPreviousDef
.insert({BB
, &*Defs
->rbegin()});
179 return &*Defs
->rbegin();
182 return getPreviousDefRecursive(BB
, CachedPreviousDef
);
184 // Recurse over a set of phi uses to eliminate the trivial ones
185 MemoryAccess
*MemorySSAUpdater::recursePhi(MemoryAccess
*Phi
) {
188 TrackingVH
<MemoryAccess
> Res(Phi
);
189 SmallVector
<TrackingVH
<Value
>, 8> Uses
;
190 std::copy(Phi
->user_begin(), Phi
->user_end(), std::back_inserter(Uses
));
192 if (MemoryPhi
*UsePhi
= dyn_cast
<MemoryPhi
>(&*U
))
193 tryRemoveTrivialPhi(UsePhi
);
197 // Eliminate trivial phis
198 // Phis are trivial if they are defined either by themselves, or all the same
200 // IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
201 // We recursively try to remove them.
202 MemoryAccess
*MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi
*Phi
) {
203 assert(Phi
&& "Can only remove concrete Phi.");
204 auto OperRange
= Phi
->operands();
205 return tryRemoveTrivialPhi(Phi
, OperRange
);
207 template <class RangeType
>
208 MemoryAccess
*MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi
*Phi
,
209 RangeType
&Operands
) {
210 // Bail out on non-opt Phis.
211 if (NonOptPhis
.count(Phi
))
214 // Detect equal or self arguments
215 MemoryAccess
*Same
= nullptr;
216 for (auto &Op
: Operands
) {
217 // If the same or self, good so far
218 if (Op
== Phi
|| Op
== Same
)
220 // not the same, return the phi since it's not eliminatable by us
223 Same
= cast
<MemoryAccess
>(&*Op
);
225 // Never found a non-self reference, the phi is undef
227 return MSSA
->getLiveOnEntryDef();
229 Phi
->replaceAllUsesWith(Same
);
230 removeMemoryAccess(Phi
);
233 // We should only end up recursing in case we replaced something, in which
234 // case, we may have made other Phis trivial.
235 return recursePhi(Same
);
238 void MemorySSAUpdater::insertUse(MemoryUse
*MU
, bool RenameUses
) {
239 VisitedBlocks
.clear();
240 InsertedPHIs
.clear();
241 MU
->setDefiningAccess(getPreviousDef(MU
));
243 // In cases without unreachable blocks, because uses do not create new
244 // may-defs, there are only two cases:
245 // 1. There was a def already below us, and therefore, we should not have
246 // created a phi node because it was already needed for the def.
248 // 2. There is no def below us, and therefore, there is no extra renaming work
251 // In cases with unreachable blocks, where the unnecessary Phis were
252 // optimized out, adding the Use may re-insert those Phis. Hence, when
253 // inserting Uses outside of the MSSA creation process, and new Phis were
254 // added, rename all uses if we are asked.
256 if (!RenameUses
&& !InsertedPHIs
.empty()) {
257 auto *Defs
= MSSA
->getBlockDefs(MU
->getBlock());
259 assert((!Defs
|| (++Defs
->begin() == Defs
->end())) &&
260 "Block may have only a Phi or no defs");
263 if (RenameUses
&& InsertedPHIs
.size()) {
264 SmallPtrSet
<BasicBlock
*, 16> Visited
;
265 BasicBlock
*StartBlock
= MU
->getBlock();
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 an
271 if (auto *MD
= dyn_cast
<MemoryDef
>(FirstDef
))
272 FirstDef
= MD
->getDefiningAccess();
274 MSSA
->renamePass(MU
->getBlock(), FirstDef
, Visited
);
276 // We just inserted a phi into this block, so the incoming value will
277 // 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
);
284 // Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
285 static void setMemoryPhiValueForBlock(MemoryPhi
*MP
, const BasicBlock
*BB
,
286 MemoryAccess
*NewDef
) {
287 // Replace any operand with us an incoming block with the new defining
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 the
292 // other not. So use it to index into the block iterator.
293 for (const BasicBlock
*BlockBB
: llvm::drop_begin(MP
->blocks(), i
)) {
296 MP
->setIncomingValue(i
, NewDef
);
301 // A brief description of the algorithm:
302 // First, we compute what should define the new def, using the SSA
303 // construction algorithm.
304 // Then, we update the defs below us (and any new phi nodes) in the graph to
305 // point to the correct new defs, to ensure we only have one variable, and no
306 // disconnected stores.
307 void 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());
314 VisitedBlocks
.clear();
315 InsertedPHIs
.clear();
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;
325 // There is a def before us, which means we can replace any store/phi uses
326 // of that thing with us, since we are in the way of whatever was there
328 // We now define that def's memorydefs and memoryphis
329 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.
340 // and that def is now our defining access.
341 MD
->setDefiningAccess(DefBefore
);
343 SmallVector
<WeakVH
, 8> FixupList(InsertedPHIs
.begin(), InsertedPHIs
.end());
345 SmallSet
<WeakVH
, 8> ExistingPhis
;
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 it
351 // did. Because every may-def is the same, any phis/etc we would create, it
352 // would also have created. If there was no local def before us, we
353 // performed a global update, and have to search all successors and make
354 // sure we update the first def in each of them (following all paths until
355 // 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 a
357 // single successor, and only used a straight line of single pred blocks
358 // backwards to find the def. To make that work, we'd have to track whether
359 // getDefRecursive only ever used the single predecessor case. These types
360 // of paths also only exist in between CFG simplifications.
362 // If this is the first def in the block and this insert is in an arbitrary
363 // place, compute IDF and place phis.
364 SmallPtrSet
<BasicBlock
*, 2> DefiningBlocks
;
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 is
368 // not the last access, because it can introduce a new access past which a
369 // 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
);
382 MPhi
= MSSA
->createMemoryPhi(BBIDF
);
383 NewInsertedPHIs
.push_back(MPhi
);
385 ExistingPhis
.insert(MPhi
);
387 // Add the phis created into the IDF blocks to NonOptPhis, so they are not
388 // optimized out as trivial by the call to getPreviousDefFromEnd below.
389 // Once they are complete, all these Phis are added to the FixupList, and
390 // removed from NonOptPhis inside fixupDefs(). Existing Phis in IDF may
391 // need fixing as well, and potentially be trivial before this insertion,
392 // hence add all IDF Phis. See PR43044.
393 NonOptPhis
.insert(MPhi
);
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
);
403 // Re-take the index where we're adding the new phis, because the above call
404 // 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
);
411 FixupList
.push_back(MD
);
414 // Remember the index where we stopped inserting new phis above, since the
415 // fixupDefs call in the loop below may insert more, that are already minimal.
416 unsigned NewPhiIndexEnd
= InsertedPHIs
.size();
418 while (!FixupList
.empty()) {
419 unsigned StartingPHISize
= InsertedPHIs
.size();
420 fixupDefs(FixupList
);
422 // Put any new phis on the fixup list, and process them
423 FixupList
.append(InsertedPHIs
.begin() + StartingPHISize
, InsertedPHIs
.end());
426 // Optimize potentially non-minimal phis added in this method.
427 unsigned NewPhiSize
= NewPhiIndexEnd
- NewPhiIndex
;
429 tryRemoveTrivialPhis(ArrayRef
<WeakVH
>(&InsertedPHIs
[NewPhiIndex
], NewPhiSize
));
431 // Now that all fixups are done, rename all uses if we are asked. The defs are
432 // guaranteed to be in reachable code due to the check at the method entry.
433 BasicBlock
*StartBlock
= MD
->getBlock();
435 SmallPtrSet
<BasicBlock
*, 16> Visited
;
436 // We are guaranteed there is a def in the block, because we just got it
437 // handed to us in this function.
438 MemoryAccess
*FirstDef
= &*MSSA
->getWritableBlockDefs(StartBlock
)->begin();
439 // Convert to incoming value if it's a memorydef. A phi *is* already an
441 if (auto *MD
= dyn_cast
<MemoryDef
>(FirstDef
))
442 FirstDef
= MD
->getDefiningAccess();
444 MSSA
->renamePass(MD
->getBlock(), FirstDef
, Visited
);
445 // We just inserted a phi into this block, so the incoming value will become
446 // the phi anyway, so it does not matter what we pass.
447 for (auto &MP
: InsertedPHIs
) {
448 MemoryPhi
*Phi
= dyn_cast_or_null
<MemoryPhi
>(MP
);
450 MSSA
->renamePass(Phi
->getBlock(), nullptr, Visited
);
452 // Existing Phi blocks may need renaming too, if an access was previously
453 // optimized and the inserted Defs "covers" the Optimized value.
454 for (const auto &MP
: ExistingPhis
) {
455 MemoryPhi
*Phi
= dyn_cast_or_null
<MemoryPhi
>(MP
);
457 MSSA
->renamePass(Phi
->getBlock(), nullptr, Visited
);
462 void MemorySSAUpdater::fixupDefs(const SmallVectorImpl
<WeakVH
> &Vars
) {
463 SmallPtrSet
<const BasicBlock
*, 8> Seen
;
464 SmallVector
<const BasicBlock
*, 16> Worklist
;
465 for (const auto &Var
: Vars
) {
466 MemoryAccess
*NewDef
= dyn_cast_or_null
<MemoryAccess
>(Var
);
469 // First, see if there is a local def after the operand.
470 auto *Defs
= MSSA
->getWritableBlockDefs(NewDef
->getBlock());
471 auto DefIter
= NewDef
->getDefsIterator();
473 // The temporary Phi is being fixed, unmark it for not to optimize.
474 if (MemoryPhi
*Phi
= dyn_cast
<MemoryPhi
>(NewDef
))
475 NonOptPhis
.erase(Phi
);
477 // If there is a local def after us, we only have to rename that.
478 if (++DefIter
!= Defs
->end()) {
479 cast
<MemoryDef
>(DefIter
)->setDefiningAccess(NewDef
);
483 // Otherwise, we need to search down through the CFG.
484 // For each of our successors, handle it directly if their is a phi, or
485 // place on the fixup worklist.
486 for (const auto *S
: successors(NewDef
->getBlock())) {
487 if (auto *MP
= MSSA
->getMemoryAccess(S
))
488 setMemoryPhiValueForBlock(MP
, NewDef
->getBlock(), NewDef
);
490 Worklist
.push_back(S
);
493 while (!Worklist
.empty()) {
494 const BasicBlock
*FixupBlock
= Worklist
.pop_back_val();
496 // Get the first def in the block that isn't a phi node.
497 if (auto *Defs
= MSSA
->getWritableBlockDefs(FixupBlock
)) {
498 auto *FirstDef
= &*Defs
->begin();
499 // The loop above and below should have taken care of phi nodes
500 assert(!isa
<MemoryPhi
>(FirstDef
) &&
501 "Should have already handled phi nodes!");
502 // We are now this def's defining access, make sure we actually dominate
504 assert(MSSA
->dominates(NewDef
, FirstDef
) &&
505 "Should have dominated the new access");
507 // This may insert new phi nodes, because we are not guaranteed the
508 // block we are processing has a single pred, and depending where the
509 // store was inserted, it may require phi nodes below it.
510 cast
<MemoryDef
>(FirstDef
)->setDefiningAccess(getPreviousDef(FirstDef
));
513 // We didn't find a def, so we must continue.
514 for (const auto *S
: successors(FixupBlock
)) {
515 // If there is a phi node, handle it.
516 // Otherwise, put the block on the worklist
517 if (auto *MP
= MSSA
->getMemoryAccess(S
))
518 setMemoryPhiValueForBlock(MP
, FixupBlock
, NewDef
);
520 // If we cycle, we should have ended up at a phi node that we already
521 // processed. FIXME: Double check this
522 if (!Seen
.insert(S
).second
)
524 Worklist
.push_back(S
);
531 void MemorySSAUpdater::removeEdge(BasicBlock
*From
, BasicBlock
*To
) {
532 if (MemoryPhi
*MPhi
= MSSA
->getMemoryAccess(To
)) {
533 MPhi
->unorderedDeleteIncomingBlock(From
);
534 tryRemoveTrivialPhi(MPhi
);
538 void MemorySSAUpdater::removeDuplicatePhiEdgesBetween(const BasicBlock
*From
,
539 const BasicBlock
*To
) {
540 if (MemoryPhi
*MPhi
= MSSA
->getMemoryAccess(To
)) {
542 MPhi
->unorderedDeleteIncomingIf([&](const MemoryAccess
*, BasicBlock
*B
) {
550 tryRemoveTrivialPhi(MPhi
);
554 /// If all arguments of a MemoryPHI are defined by the same incoming
555 /// argument, return that argument.
556 static MemoryAccess
*onlySingleValue(MemoryPhi
*MP
) {
557 MemoryAccess
*MA
= nullptr;
559 for (auto &Arg
: MP
->operands()) {
561 MA
= cast
<MemoryAccess
>(Arg
);
568 static MemoryAccess
*getNewDefiningAccessForClone(
569 MemoryAccess
*MA
, const ValueToValueMapTy
&VMap
, PhiToDefMap
&MPhiMap
,
570 MemorySSA
*MSSA
, function_ref
<bool(BasicBlock
*BB
)> IsInClonedRegion
) {
571 MemoryAccess
*InsnDefining
= MA
;
572 if (MemoryDef
*DefMUD
= dyn_cast
<MemoryDef
>(InsnDefining
)) {
573 if (MSSA
->isLiveOnEntryDef(DefMUD
))
576 // If the MemoryDef is not part of the cloned region, leave it alone.
577 Instruction
*DefMUDI
= DefMUD
->getMemoryInst();
578 assert(DefMUDI
&& "Found MemoryUseOrDef with no Instruction.");
579 if (!IsInClonedRegion(DefMUDI
->getParent()))
582 auto *NewDefMUDI
= cast_or_null
<Instruction
>(VMap
.lookup(DefMUDI
));
583 InsnDefining
= NewDefMUDI
? MSSA
->getMemoryAccess(NewDefMUDI
) : nullptr;
584 if (!InsnDefining
|| isa
<MemoryUse
>(InsnDefining
)) {
585 // The clone was simplified, it's no longer a MemoryDef, look up.
586 InsnDefining
= getNewDefiningAccessForClone(
587 DefMUD
->getDefiningAccess(), VMap
, MPhiMap
, MSSA
, IsInClonedRegion
);
590 MemoryPhi
*DefPhi
= cast
<MemoryPhi
>(InsnDefining
);
591 if (MemoryAccess
*NewDefPhi
= MPhiMap
.lookup(DefPhi
))
592 InsnDefining
= NewDefPhi
;
594 assert(InsnDefining
&& "Defining instruction cannot be nullptr.");
598 void MemorySSAUpdater::cloneUsesAndDefs(
599 BasicBlock
*BB
, BasicBlock
*NewBB
, const ValueToValueMapTy
&VMap
,
600 PhiToDefMap
&MPhiMap
, function_ref
<bool(BasicBlock
*)> IsInClonedRegion
,
601 bool CloneWasSimplified
) {
602 const MemorySSA::AccessList
*Acc
= MSSA
->getBlockAccesses(BB
);
605 for (const MemoryAccess
&MA
: *Acc
) {
606 if (const MemoryUseOrDef
*MUD
= dyn_cast
<MemoryUseOrDef
>(&MA
)) {
607 Instruction
*Insn
= MUD
->getMemoryInst();
608 // Entry does not exist if the clone of the block did not clone all
609 // instructions. This occurs in LoopRotate when cloning instructions
610 // from the old header to the old preheader. The cloned instruction may
611 // also be a simplified Value, not an Instruction (see LoopRotate).
612 // Also in LoopRotate, even when it's an instruction, due to it being
613 // simplified, it may be a Use rather than a Def, so we cannot use MUD as
614 // template. Calls coming from updateForClonedBlockIntoPred, ensure this.
615 if (Instruction
*NewInsn
=
616 dyn_cast_or_null
<Instruction
>(VMap
.lookup(Insn
))) {
617 MemoryAccess
*NewUseOrDef
= MSSA
->createDefinedAccess(
619 getNewDefiningAccessForClone(MUD
->getDefiningAccess(), VMap
,
620 MPhiMap
, MSSA
, IsInClonedRegion
),
621 /*Template=*/CloneWasSimplified
? nullptr : MUD
,
622 /*CreationMustSucceed=*/false);
624 MSSA
->insertIntoListsForBlock(NewUseOrDef
, NewBB
, MemorySSA::End
);
630 void MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock(
631 BasicBlock
*Header
, BasicBlock
*Preheader
, BasicBlock
*BEBlock
) {
632 auto *MPhi
= MSSA
->getMemoryAccess(Header
);
636 // Create phi node in the backedge block and populate it with the same
637 // incoming values as MPhi. Skip incoming values coming from Preheader.
638 auto *NewMPhi
= MSSA
->createMemoryPhi(BEBlock
);
639 bool HasUniqueIncomingValue
= true;
640 MemoryAccess
*UniqueValue
= nullptr;
641 for (unsigned I
= 0, E
= MPhi
->getNumIncomingValues(); I
!= E
; ++I
) {
642 BasicBlock
*IBB
= MPhi
->getIncomingBlock(I
);
643 MemoryAccess
*IV
= MPhi
->getIncomingValue(I
);
644 if (IBB
!= Preheader
) {
645 NewMPhi
->addIncoming(IV
, IBB
);
646 if (HasUniqueIncomingValue
) {
649 else if (UniqueValue
!= IV
)
650 HasUniqueIncomingValue
= false;
655 // Update incoming edges into MPhi. Remove all but the incoming edge from
656 // Preheader. Add an edge from NewMPhi
657 auto *AccFromPreheader
= MPhi
->getIncomingValueForBlock(Preheader
);
658 MPhi
->setIncomingValue(0, AccFromPreheader
);
659 MPhi
->setIncomingBlock(0, Preheader
);
660 for (unsigned I
= MPhi
->getNumIncomingValues() - 1; I
>= 1; --I
)
661 MPhi
->unorderedDeleteIncoming(I
);
662 MPhi
->addIncoming(NewMPhi
, BEBlock
);
664 // If NewMPhi is a trivial phi, remove it. Its use in the header MPhi will be
665 // replaced with the unique value.
666 tryRemoveTrivialPhi(NewMPhi
);
669 void MemorySSAUpdater::updateForClonedLoop(const LoopBlocksRPO
&LoopBlocks
,
670 ArrayRef
<BasicBlock
*> ExitBlocks
,
671 const ValueToValueMapTy
&VMap
,
672 bool IgnoreIncomingWithNoClones
) {
673 SmallSetVector
<BasicBlock
*, 16> Blocks
;
674 for (BasicBlock
*BB
: concat
<BasicBlock
*const>(LoopBlocks
, ExitBlocks
))
677 auto IsInClonedRegion
= [&](BasicBlock
*BB
) { return Blocks
.contains(BB
); };
680 auto FixPhiIncomingValues
= [&](MemoryPhi
*Phi
, MemoryPhi
*NewPhi
) {
681 assert(Phi
&& NewPhi
&& "Invalid Phi nodes.");
682 BasicBlock
*NewPhiBB
= NewPhi
->getBlock();
683 SmallPtrSet
<BasicBlock
*, 4> NewPhiBBPreds(pred_begin(NewPhiBB
),
685 for (unsigned It
= 0, E
= Phi
->getNumIncomingValues(); It
< E
; ++It
) {
686 MemoryAccess
*IncomingAccess
= Phi
->getIncomingValue(It
);
687 BasicBlock
*IncBB
= Phi
->getIncomingBlock(It
);
689 if (BasicBlock
*NewIncBB
= cast_or_null
<BasicBlock
>(VMap
.lookup(IncBB
)))
691 else if (IgnoreIncomingWithNoClones
)
694 // Now we have IncBB, and will need to add incoming from it to NewPhi.
696 // If IncBB is not a predecessor of NewPhiBB, then do not add it.
697 // NewPhiBB was cloned without that edge.
698 if (!NewPhiBBPreds
.count(IncBB
))
701 // Determine incoming value and add it as incoming from IncBB.
702 NewPhi
->addIncoming(getNewDefiningAccessForClone(IncomingAccess
, VMap
,
707 if (auto *SingleAccess
= onlySingleValue(NewPhi
)) {
708 MPhiMap
[Phi
] = SingleAccess
;
709 removeMemoryAccess(NewPhi
);
713 auto ProcessBlock
= [&](BasicBlock
*BB
) {
714 BasicBlock
*NewBlock
= cast_or_null
<BasicBlock
>(VMap
.lookup(BB
));
718 assert(!MSSA
->getWritableBlockAccesses(NewBlock
) &&
719 "Cloned block should have no accesses");
722 if (MemoryPhi
*MPhi
= MSSA
->getMemoryAccess(BB
)) {
723 MemoryPhi
*NewPhi
= MSSA
->createMemoryPhi(NewBlock
);
724 MPhiMap
[MPhi
] = NewPhi
;
726 // Update Uses and Defs.
727 cloneUsesAndDefs(BB
, NewBlock
, VMap
, MPhiMap
, IsInClonedRegion
);
730 for (auto *BB
: Blocks
)
733 for (auto *BB
: Blocks
)
734 if (MemoryPhi
*MPhi
= MSSA
->getMemoryAccess(BB
))
735 if (MemoryAccess
*NewPhi
= MPhiMap
.lookup(MPhi
))
736 FixPhiIncomingValues(MPhi
, cast
<MemoryPhi
>(NewPhi
));
739 void MemorySSAUpdater::updateForClonedBlockIntoPred(
740 BasicBlock
*BB
, BasicBlock
*P1
, const ValueToValueMapTy
&VM
) {
741 // All defs/phis from outside BB that are used in BB, are valid uses in P1.
742 // Since those defs/phis must have dominated BB, and also dominate P1.
743 // Defs from BB being used in BB will be replaced with the cloned defs from
744 // VM. The uses of BB's Phi (if it exists) in BB will be replaced by the
745 // incoming def into the Phi from P1.
746 // Instructions cloned into the predecessor are in practice sometimes
747 // simplified, so disable the use of the template, and create an access from
750 if (MemoryPhi
*MPhi
= MSSA
->getMemoryAccess(BB
))
751 MPhiMap
[MPhi
] = MPhi
->getIncomingValueForBlock(P1
);
753 BB
, P1
, VM
, MPhiMap
, [&](BasicBlock
*CheckBB
) { return BB
== CheckBB
; },
754 /*CloneWasSimplified=*/true);
757 template <typename Iter
>
758 void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop(
759 ArrayRef
<BasicBlock
*> ExitBlocks
, Iter ValuesBegin
, Iter ValuesEnd
,
761 SmallVector
<CFGUpdate
, 4> Updates
;
762 // Update/insert phis in all successors of exit blocks.
763 for (auto *Exit
: ExitBlocks
)
764 for (const ValueToValueMapTy
*VMap
: make_range(ValuesBegin
, ValuesEnd
))
765 if (BasicBlock
*NewExit
= cast_or_null
<BasicBlock
>(VMap
->lookup(Exit
))) {
766 BasicBlock
*ExitSucc
= NewExit
->getTerminator()->getSuccessor(0);
767 Updates
.push_back({DT
.Insert
, NewExit
, ExitSucc
});
769 applyInsertUpdates(Updates
, DT
);
772 void MemorySSAUpdater::updateExitBlocksForClonedLoop(
773 ArrayRef
<BasicBlock
*> ExitBlocks
, const ValueToValueMapTy
&VMap
,
775 const ValueToValueMapTy
*const Arr
[] = {&VMap
};
776 privateUpdateExitBlocksForClonedLoop(ExitBlocks
, std::begin(Arr
),
780 void MemorySSAUpdater::updateExitBlocksForClonedLoop(
781 ArrayRef
<BasicBlock
*> ExitBlocks
,
782 ArrayRef
<std::unique_ptr
<ValueToValueMapTy
>> VMaps
, DominatorTree
&DT
) {
783 auto GetPtr
= [&](const std::unique_ptr
<ValueToValueMapTy
> &I
) {
786 using MappedIteratorType
=
787 mapped_iterator
<const std::unique_ptr
<ValueToValueMapTy
> *,
789 auto MapBegin
= MappedIteratorType(VMaps
.begin(), GetPtr
);
790 auto MapEnd
= MappedIteratorType(VMaps
.end(), GetPtr
);
791 privateUpdateExitBlocksForClonedLoop(ExitBlocks
, MapBegin
, MapEnd
, DT
);
794 void MemorySSAUpdater::applyUpdates(ArrayRef
<CFGUpdate
> Updates
,
795 DominatorTree
&DT
, bool UpdateDT
) {
796 SmallVector
<CFGUpdate
, 4> DeleteUpdates
;
797 SmallVector
<CFGUpdate
, 4> RevDeleteUpdates
;
798 SmallVector
<CFGUpdate
, 4> InsertUpdates
;
799 for (const auto &Update
: Updates
) {
800 if (Update
.getKind() == DT
.Insert
)
801 InsertUpdates
.push_back({DT
.Insert
, Update
.getFrom(), Update
.getTo()});
803 DeleteUpdates
.push_back({DT
.Delete
, Update
.getFrom(), Update
.getTo()});
804 RevDeleteUpdates
.push_back({DT
.Insert
, Update
.getFrom(), Update
.getTo()});
808 if (!DeleteUpdates
.empty()) {
809 if (!InsertUpdates
.empty()) {
811 SmallVector
<CFGUpdate
, 0> Empty
;
812 // Deletes are reversed applied, because this CFGView is pretending the
813 // deletes did not happen yet, hence the edges still exist.
814 DT
.applyUpdates(Empty
, RevDeleteUpdates
);
816 // Apply all updates, with the RevDeleteUpdates as PostCFGView.
817 DT
.applyUpdates(Updates
, RevDeleteUpdates
);
820 // Note: the MSSA update below doesn't distinguish between a GD with
821 // (RevDelete,false) and (Delete, true), but this matters for the DT
822 // updates above; for "children" purposes they are equivalent; but the
823 // updates themselves convey the desired update, used inside DT only.
824 GraphDiff
<BasicBlock
*> GD(RevDeleteUpdates
);
825 applyInsertUpdates(InsertUpdates
, DT
, &GD
);
826 // Update DT to redelete edges; this matches the real CFG so we can
827 // perform the standard update without a postview of the CFG.
828 DT
.applyUpdates(DeleteUpdates
);
831 DT
.applyUpdates(DeleteUpdates
);
835 DT
.applyUpdates(Updates
);
836 GraphDiff
<BasicBlock
*> GD
;
837 applyInsertUpdates(InsertUpdates
, DT
, &GD
);
840 // Update for deleted edges
841 for (auto &Update
: DeleteUpdates
)
842 removeEdge(Update
.getFrom(), Update
.getTo());
845 void MemorySSAUpdater::applyInsertUpdates(ArrayRef
<CFGUpdate
> Updates
,
847 GraphDiff
<BasicBlock
*> GD
;
848 applyInsertUpdates(Updates
, DT
, &GD
);
851 void MemorySSAUpdater::applyInsertUpdates(ArrayRef
<CFGUpdate
> Updates
,
853 const GraphDiff
<BasicBlock
*> *GD
) {
854 // Get recursive last Def, assuming well formed MSSA and updated DT.
855 auto GetLastDef
= [&](BasicBlock
*BB
) -> MemoryAccess
* {
857 MemorySSA::DefsList
*Defs
= MSSA
->getWritableBlockDefs(BB
);
858 // Return last Def or Phi in BB, if it exists.
860 return &*(--Defs
->end());
862 // Check number of predecessors, we only care if there's more than one.
864 BasicBlock
*Pred
= nullptr;
865 for (auto *Pi
: GD
->template getChildren
</*InverseEdge=*/true>(BB
)) {
872 // If BB has multiple predecessors, get last definition from IDom.
874 // [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its
875 // DT is invalidated. Return LoE as its last def. This will be added to
876 // MemoryPhi node, and later deleted when the block is deleted.
878 return MSSA
->getLiveOnEntryDef();
879 if (auto *IDom
= DT
.getNode(BB
)->getIDom())
880 if (IDom
->getBlock() != BB
) {
881 BB
= IDom
->getBlock();
884 return MSSA
->getLiveOnEntryDef();
886 // Single predecessor, BB cannot be dead. GetLastDef of Pred.
887 assert(Count
== 1 && Pred
&& "Single predecessor expected.");
888 // BB can be unreachable though, return LoE if that is the case.
890 return MSSA
->getLiveOnEntryDef();
894 llvm_unreachable("Unable to get last definition.");
897 // Get nearest IDom given a set of blocks.
898 // TODO: this can be optimized by starting the search at the node with the
899 // lowest level (highest in the tree).
900 auto FindNearestCommonDominator
=
901 [&](const SmallSetVector
<BasicBlock
*, 2> &BBSet
) -> BasicBlock
* {
902 BasicBlock
*PrevIDom
= *BBSet
.begin();
903 for (auto *BB
: BBSet
)
904 PrevIDom
= DT
.findNearestCommonDominator(PrevIDom
, BB
);
908 // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not
910 auto GetNoLongerDomBlocks
=
911 [&](BasicBlock
*PrevIDom
, BasicBlock
*CurrIDom
,
912 SmallVectorImpl
<BasicBlock
*> &BlocksPrevDom
) {
913 if (PrevIDom
== CurrIDom
)
915 BlocksPrevDom
.push_back(PrevIDom
);
916 BasicBlock
*NextIDom
= PrevIDom
;
917 while (BasicBlock
*UpIDom
=
918 DT
.getNode(NextIDom
)->getIDom()->getBlock()) {
919 if (UpIDom
== CurrIDom
)
921 BlocksPrevDom
.push_back(UpIDom
);
926 // Map a BB to its predecessors: added + previously existing. To get a
927 // deterministic order, store predecessors as SetVectors. The order in each
928 // will be defined by the order in Updates (fixed) and the order given by
929 // children<> (also fixed). Since we further iterate over these ordered sets,
930 // we lose the information of multiple edges possibly existing between two
931 // blocks, so we'll keep and EdgeCount map for that.
932 // An alternate implementation could keep unordered set for the predecessors,
933 // traverse either Updates or children<> each time to get the deterministic
934 // order, and drop the usage of EdgeCount. This alternate approach would still
935 // require querying the maps for each predecessor, and children<> call has
936 // additional computation inside for creating the snapshot-graph predecessors.
937 // As such, we favor using a little additional storage and less compute time.
938 // This decision can be revisited if we find the alternative more favorable.
941 SmallSetVector
<BasicBlock
*, 2> Added
;
942 SmallSetVector
<BasicBlock
*, 2> Prev
;
944 SmallDenseMap
<BasicBlock
*, PredInfo
> PredMap
;
946 for (const auto &Edge
: Updates
) {
947 BasicBlock
*BB
= Edge
.getTo();
948 auto &AddedBlockSet
= PredMap
[BB
].Added
;
949 AddedBlockSet
.insert(Edge
.getFrom());
952 // Store all existing predecessor for each BB, at least one must exist.
953 SmallDenseMap
<std::pair
<BasicBlock
*, BasicBlock
*>, int> EdgeCountMap
;
954 SmallPtrSet
<BasicBlock
*, 2> NewBlocks
;
955 for (auto &BBPredPair
: PredMap
) {
956 auto *BB
= BBPredPair
.first
;
957 const auto &AddedBlockSet
= BBPredPair
.second
.Added
;
958 auto &PrevBlockSet
= BBPredPair
.second
.Prev
;
959 for (auto *Pi
: GD
->template getChildren
</*InverseEdge=*/true>(BB
)) {
960 if (!AddedBlockSet
.count(Pi
))
961 PrevBlockSet
.insert(Pi
);
962 EdgeCountMap
[{Pi
, BB
}]++;
965 if (PrevBlockSet
.empty()) {
966 assert(pred_size(BB
) == AddedBlockSet
.size() && "Duplicate edges added.");
969 << "Adding a predecessor to a block with no predecessors. "
970 "This must be an edge added to a new, likely cloned, block. "
971 "Its memory accesses must be already correct, assuming completed "
972 "via the updateExitBlocksForClonedLoop API. "
973 "Assert a single such edge is added so no phi addition or "
974 "additional processing is required.\n");
975 assert(AddedBlockSet
.size() == 1 &&
976 "Can only handle adding one predecessor to a new block.");
977 // Need to remove new blocks from PredMap. Remove below to not invalidate
979 NewBlocks
.insert(BB
);
982 // Nothing to process for new/cloned blocks.
983 for (auto *BB
: NewBlocks
)
986 SmallVector
<BasicBlock
*, 16> BlocksWithDefsToReplace
;
987 SmallVector
<WeakVH
, 8> InsertedPhis
;
989 // First create MemoryPhis in all blocks that don't have one. Create in the
990 // order found in Updates, not in PredMap, to get deterministic numbering.
991 for (const auto &Edge
: Updates
) {
992 BasicBlock
*BB
= Edge
.getTo();
993 if (PredMap
.count(BB
) && !MSSA
->getMemoryAccess(BB
))
994 InsertedPhis
.push_back(MSSA
->createMemoryPhi(BB
));
997 // Now we'll fill in the MemoryPhis with the right incoming values.
998 for (auto &BBPredPair
: PredMap
) {
999 auto *BB
= BBPredPair
.first
;
1000 const auto &PrevBlockSet
= BBPredPair
.second
.Prev
;
1001 const auto &AddedBlockSet
= BBPredPair
.second
.Added
;
1002 assert(!PrevBlockSet
.empty() &&
1003 "At least one previous predecessor must exist.");
1005 // TODO: if this becomes a bottleneck, we can save on GetLastDef calls by
1006 // keeping this map before the loop. We can reuse already populated entries
1007 // if an edge is added from the same predecessor to two different blocks,
1008 // and this does happen in rotate. Note that the map needs to be updated
1009 // when deleting non-necessary phis below, if the phi is in the map by
1010 // replacing the value with DefP1.
1011 SmallDenseMap
<BasicBlock
*, MemoryAccess
*> LastDefAddedPred
;
1012 for (auto *AddedPred
: AddedBlockSet
) {
1013 auto *DefPn
= GetLastDef(AddedPred
);
1014 assert(DefPn
!= nullptr && "Unable to find last definition.");
1015 LastDefAddedPred
[AddedPred
] = DefPn
;
1018 MemoryPhi
*NewPhi
= MSSA
->getMemoryAccess(BB
);
1019 // If Phi is not empty, add an incoming edge from each added pred. Must
1020 // still compute blocks with defs to replace for this block below.
1021 if (NewPhi
->getNumOperands()) {
1022 for (auto *Pred
: AddedBlockSet
) {
1023 auto *LastDefForPred
= LastDefAddedPred
[Pred
];
1024 for (int I
= 0, E
= EdgeCountMap
[{Pred
, BB
}]; I
< E
; ++I
)
1025 NewPhi
->addIncoming(LastDefForPred
, Pred
);
1028 // Pick any existing predecessor and get its definition. All other
1029 // existing predecessors should have the same one, since no phi existed.
1030 auto *P1
= *PrevBlockSet
.begin();
1031 MemoryAccess
*DefP1
= GetLastDef(P1
);
1033 // Check DefP1 against all Defs in LastDefPredPair. If all the same,
1035 bool InsertPhi
= false;
1036 for (auto LastDefPredPair
: LastDefAddedPred
)
1037 if (DefP1
!= LastDefPredPair
.second
) {
1042 // Since NewPhi may be used in other newly added Phis, replace all uses
1043 // of NewPhi with the definition coming from all predecessors (DefP1),
1044 // before deleting it.
1045 NewPhi
->replaceAllUsesWith(DefP1
);
1046 removeMemoryAccess(NewPhi
);
1050 // Update Phi with new values for new predecessors and old value for all
1051 // other predecessors. Since AddedBlockSet and PrevBlockSet are ordered
1052 // sets, the order of entries in NewPhi is deterministic.
1053 for (auto *Pred
: AddedBlockSet
) {
1054 auto *LastDefForPred
= LastDefAddedPred
[Pred
];
1055 for (int I
= 0, E
= EdgeCountMap
[{Pred
, BB
}]; I
< E
; ++I
)
1056 NewPhi
->addIncoming(LastDefForPred
, Pred
);
1058 for (auto *Pred
: PrevBlockSet
)
1059 for (int I
= 0, E
= EdgeCountMap
[{Pred
, BB
}]; I
< E
; ++I
)
1060 NewPhi
->addIncoming(DefP1
, Pred
);
1063 // Get all blocks that used to dominate BB and no longer do after adding
1064 // AddedBlockSet, where PrevBlockSet are the previously known predecessors.
1065 assert(DT
.getNode(BB
)->getIDom() && "BB does not have valid idom");
1066 BasicBlock
*PrevIDom
= FindNearestCommonDominator(PrevBlockSet
);
1067 assert(PrevIDom
&& "Previous IDom should exists");
1068 BasicBlock
*NewIDom
= DT
.getNode(BB
)->getIDom()->getBlock();
1069 assert(NewIDom
&& "BB should have a new valid idom");
1070 assert(DT
.dominates(NewIDom
, PrevIDom
) &&
1071 "New idom should dominate old idom");
1072 GetNoLongerDomBlocks(PrevIDom
, NewIDom
, BlocksWithDefsToReplace
);
1075 tryRemoveTrivialPhis(InsertedPhis
);
1076 // Create the set of blocks that now have a definition. We'll use this to
1077 // compute IDF and add Phis there next.
1078 SmallVector
<BasicBlock
*, 8> BlocksToProcess
;
1079 for (auto &VH
: InsertedPhis
)
1080 if (auto *MPhi
= cast_or_null
<MemoryPhi
>(VH
))
1081 BlocksToProcess
.push_back(MPhi
->getBlock());
1083 // Compute IDF and add Phis in all IDF blocks that do not have one.
1084 SmallVector
<BasicBlock
*, 32> IDFBlocks
;
1085 if (!BlocksToProcess
.empty()) {
1086 ForwardIDFCalculator
IDFs(DT
, GD
);
1087 SmallPtrSet
<BasicBlock
*, 16> DefiningBlocks(BlocksToProcess
.begin(),
1088 BlocksToProcess
.end());
1089 IDFs
.setDefiningBlocks(DefiningBlocks
);
1090 IDFs
.calculate(IDFBlocks
);
1092 SmallSetVector
<MemoryPhi
*, 4> PhisToFill
;
1093 // First create all needed Phis.
1094 for (auto *BBIDF
: IDFBlocks
)
1095 if (!MSSA
->getMemoryAccess(BBIDF
)) {
1096 auto *IDFPhi
= MSSA
->createMemoryPhi(BBIDF
);
1097 InsertedPhis
.push_back(IDFPhi
);
1098 PhisToFill
.insert(IDFPhi
);
1100 // Then update or insert their correct incoming values.
1101 for (auto *BBIDF
: IDFBlocks
) {
1102 auto *IDFPhi
= MSSA
->getMemoryAccess(BBIDF
);
1103 assert(IDFPhi
&& "Phi must exist");
1104 if (!PhisToFill
.count(IDFPhi
)) {
1105 // Update existing Phi.
1106 // FIXME: some updates may be redundant, try to optimize and skip some.
1107 for (unsigned I
= 0, E
= IDFPhi
->getNumIncomingValues(); I
< E
; ++I
)
1108 IDFPhi
->setIncomingValue(I
, GetLastDef(IDFPhi
->getIncomingBlock(I
)));
1110 for (auto *Pi
: GD
->template getChildren
</*InverseEdge=*/true>(BBIDF
))
1111 IDFPhi
->addIncoming(GetLastDef(Pi
), Pi
);
1116 // Now for all defs in BlocksWithDefsToReplace, if there are uses they no
1117 // longer dominate, replace those with the closest dominating def.
1118 // This will also update optimized accesses, as they're also uses.
1119 for (auto *BlockWithDefsToReplace
: BlocksWithDefsToReplace
) {
1120 if (auto DefsList
= MSSA
->getWritableBlockDefs(BlockWithDefsToReplace
)) {
1121 for (auto &DefToReplaceUses
: *DefsList
) {
1122 BasicBlock
*DominatingBlock
= DefToReplaceUses
.getBlock();
1123 for (Use
&U
: llvm::make_early_inc_range(DefToReplaceUses
.uses())) {
1124 MemoryAccess
*Usr
= cast
<MemoryAccess
>(U
.getUser());
1125 if (MemoryPhi
*UsrPhi
= dyn_cast
<MemoryPhi
>(Usr
)) {
1126 BasicBlock
*DominatedBlock
= UsrPhi
->getIncomingBlock(U
);
1127 if (!DT
.dominates(DominatingBlock
, DominatedBlock
))
1128 U
.set(GetLastDef(DominatedBlock
));
1130 BasicBlock
*DominatedBlock
= Usr
->getBlock();
1131 if (!DT
.dominates(DominatingBlock
, DominatedBlock
)) {
1132 if (auto *DomBlPhi
= MSSA
->getMemoryAccess(DominatedBlock
))
1135 auto *IDom
= DT
.getNode(DominatedBlock
)->getIDom();
1136 assert(IDom
&& "Block must have a valid IDom.");
1137 U
.set(GetLastDef(IDom
->getBlock()));
1139 cast
<MemoryUseOrDef
>(Usr
)->resetOptimized();
1146 tryRemoveTrivialPhis(InsertedPhis
);
1149 // Move What before Where in the MemorySSA IR.
1150 template <class WhereType
>
1151 void MemorySSAUpdater::moveTo(MemoryUseOrDef
*What
, BasicBlock
*BB
,
1153 // Mark MemoryPhi users of What not to be optimized.
1154 for (auto *U
: What
->users())
1155 if (MemoryPhi
*PhiUser
= dyn_cast
<MemoryPhi
>(U
))
1156 NonOptPhis
.insert(PhiUser
);
1158 // Replace all our users with our defining access.
1159 What
->replaceAllUsesWith(What
->getDefiningAccess());
1161 // Let MemorySSA take care of moving it around in the lists.
1162 MSSA
->moveTo(What
, BB
, Where
);
1164 // Now reinsert it into the IR and do whatever fixups needed.
1165 if (auto *MD
= dyn_cast
<MemoryDef
>(What
))
1166 insertDef(MD
, /*RenameUses=*/true);
1168 insertUse(cast
<MemoryUse
>(What
), /*RenameUses=*/true);
1170 // Clear dangling pointers. We added all MemoryPhi users, but not all
1171 // of them are removed by fixupDefs().
1175 // Move What before Where in the MemorySSA IR.
1176 void MemorySSAUpdater::moveBefore(MemoryUseOrDef
*What
, MemoryUseOrDef
*Where
) {
1177 moveTo(What
, Where
->getBlock(), Where
->getIterator());
1180 // Move What after Where in the MemorySSA IR.
1181 void MemorySSAUpdater::moveAfter(MemoryUseOrDef
*What
, MemoryUseOrDef
*Where
) {
1182 moveTo(What
, Where
->getBlock(), ++Where
->getIterator());
1185 void MemorySSAUpdater::moveToPlace(MemoryUseOrDef
*What
, BasicBlock
*BB
,
1186 MemorySSA::InsertionPlace Where
) {
1187 if (Where
!= MemorySSA::InsertionPlace::BeforeTerminator
)
1188 return moveTo(What
, BB
, Where
);
1190 if (auto *Where
= MSSA
->getMemoryAccess(BB
->getTerminator()))
1191 return moveBefore(What
, Where
);
1193 return moveTo(What
, BB
, MemorySSA::InsertionPlace::End
);
1196 // All accesses in To used to be in From. Move to end and update access lists.
1197 void MemorySSAUpdater::moveAllAccesses(BasicBlock
*From
, BasicBlock
*To
,
1198 Instruction
*Start
) {
1200 MemorySSA::AccessList
*Accs
= MSSA
->getWritableBlockAccesses(From
);
1204 assert(Start
->getParent() == To
&& "Incorrect Start instruction");
1205 MemoryAccess
*FirstInNew
= nullptr;
1206 for (Instruction
&I
: make_range(Start
->getIterator(), To
->end()))
1207 if ((FirstInNew
= MSSA
->getMemoryAccess(&I
)))
1210 auto *MUD
= cast
<MemoryUseOrDef
>(FirstInNew
);
1212 auto NextIt
= ++MUD
->getIterator();
1213 MemoryUseOrDef
*NextMUD
= (!Accs
|| NextIt
== Accs
->end())
1215 : cast
<MemoryUseOrDef
>(&*NextIt
);
1216 MSSA
->moveTo(MUD
, To
, MemorySSA::End
);
1217 // Moving MUD from Accs in the moveTo above, may delete Accs, so we need
1218 // to retrieve it again.
1219 Accs
= MSSA
->getWritableBlockAccesses(From
);
1224 // If all accesses were moved and only a trivial Phi remains, we try to remove
1225 // that Phi. This is needed when From is going to be deleted.
1226 auto *Defs
= MSSA
->getWritableBlockDefs(From
);
1227 if (Defs
&& !Defs
->empty())
1228 if (auto *Phi
= dyn_cast
<MemoryPhi
>(&*Defs
->begin()))
1229 tryRemoveTrivialPhi(Phi
);
1232 void MemorySSAUpdater::moveAllAfterSpliceBlocks(BasicBlock
*From
,
1234 Instruction
*Start
) {
1235 assert(MSSA
->getBlockAccesses(To
) == nullptr &&
1236 "To block is expected to be free of MemoryAccesses.");
1237 moveAllAccesses(From
, To
, Start
);
1238 for (BasicBlock
*Succ
: successors(To
))
1239 if (MemoryPhi
*MPhi
= MSSA
->getMemoryAccess(Succ
))
1240 MPhi
->setIncomingBlock(MPhi
->getBasicBlockIndex(From
), To
);
1243 void MemorySSAUpdater::moveAllAfterMergeBlocks(BasicBlock
*From
, BasicBlock
*To
,
1244 Instruction
*Start
) {
1245 assert(From
->getUniquePredecessor() == To
&&
1246 "From block is expected to have a single predecessor (To).");
1247 moveAllAccesses(From
, To
, Start
);
1248 for (BasicBlock
*Succ
: successors(From
))
1249 if (MemoryPhi
*MPhi
= MSSA
->getMemoryAccess(Succ
))
1250 MPhi
->setIncomingBlock(MPhi
->getBasicBlockIndex(From
), To
);
1253 void MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(
1254 BasicBlock
*Old
, BasicBlock
*New
, ArrayRef
<BasicBlock
*> Preds
,
1255 bool IdenticalEdgesWereMerged
) {
1256 assert(!MSSA
->getWritableBlockAccesses(New
) &&
1257 "Access list should be null for a new block.");
1258 MemoryPhi
*Phi
= MSSA
->getMemoryAccess(Old
);
1261 if (Old
->hasNPredecessors(1)) {
1262 assert(pred_size(New
) == Preds
.size() &&
1263 "Should have moved all predecessors.");
1264 MSSA
->moveTo(Phi
, New
, MemorySSA::Beginning
);
1266 assert(!Preds
.empty() && "Must be moving at least one predecessor to the "
1267 "new immediate predecessor.");
1268 MemoryPhi
*NewPhi
= MSSA
->createMemoryPhi(New
);
1269 SmallPtrSet
<BasicBlock
*, 16> PredsSet(Preds
.begin(), Preds
.end());
1270 // Currently only support the case of removing a single incoming edge when
1271 // identical edges were not merged.
1272 if (!IdenticalEdgesWereMerged
)
1273 assert(PredsSet
.size() == Preds
.size() &&
1274 "If identical edges were not merged, we cannot have duplicate "
1275 "blocks in the predecessors");
1276 Phi
->unorderedDeleteIncomingIf([&](MemoryAccess
*MA
, BasicBlock
*B
) {
1277 if (PredsSet
.count(B
)) {
1278 NewPhi
->addIncoming(MA
, B
);
1279 if (!IdenticalEdgesWereMerged
)
1285 Phi
->addIncoming(NewPhi
, New
);
1286 tryRemoveTrivialPhi(NewPhi
);
1290 void MemorySSAUpdater::removeMemoryAccess(MemoryAccess
*MA
, bool OptimizePhis
) {
1291 assert(!MSSA
->isLiveOnEntryDef(MA
) &&
1292 "Trying to remove the live on entry def");
1293 // We can only delete phi nodes if they have no uses, or we can replace all
1294 // uses with a single definition.
1295 MemoryAccess
*NewDefTarget
= nullptr;
1296 if (MemoryPhi
*MP
= dyn_cast
<MemoryPhi
>(MA
)) {
1297 // Note that it is sufficient to know that all edges of the phi node have
1298 // the same argument. If they do, by the definition of dominance frontiers
1299 // (which we used to place this phi), that argument must dominate this phi,
1300 // and thus, must dominate the phi's uses, and so we will not hit the assert
1302 NewDefTarget
= onlySingleValue(MP
);
1303 assert((NewDefTarget
|| MP
->use_empty()) &&
1304 "We can't delete this memory phi");
1306 NewDefTarget
= cast
<MemoryUseOrDef
>(MA
)->getDefiningAccess();
1309 SmallSetVector
<MemoryPhi
*, 4> PhisToCheck
;
1311 // Re-point the uses at our defining access
1312 if (!isa
<MemoryUse
>(MA
) && !MA
->use_empty()) {
1313 // Reset optimized on users of this store, and reset the uses.
1315 // 1. This is a slightly modified version of RAUW to avoid walking the
1317 // 2. If we wanted to be complete, we would have to reset the optimized
1318 // flags on users of phi nodes if doing the below makes a phi node have all
1319 // the same arguments. Instead, we prefer users to removeMemoryAccess those
1320 // phi nodes, because doing it here would be N^3.
1321 if (MA
->hasValueHandle())
1322 ValueHandleBase::ValueIsRAUWd(MA
, NewDefTarget
);
1323 // Note: We assume MemorySSA is not used in metadata since it's not really
1326 assert(NewDefTarget
!= MA
&& "Going into an infinite loop");
1327 while (!MA
->use_empty()) {
1328 Use
&U
= *MA
->use_begin();
1329 if (auto *MUD
= dyn_cast
<MemoryUseOrDef
>(U
.getUser()))
1330 MUD
->resetOptimized();
1332 if (MemoryPhi
*MP
= dyn_cast
<MemoryPhi
>(U
.getUser()))
1333 PhisToCheck
.insert(MP
);
1334 U
.set(NewDefTarget
);
1338 // The call below to erase will destroy MA, so we can't change the order we
1339 // are doing things here
1340 MSSA
->removeFromLookups(MA
);
1341 MSSA
->removeFromLists(MA
);
1343 // Optionally optimize Phi uses. This will recursively remove trivial phis.
1344 if (!PhisToCheck
.empty()) {
1345 SmallVector
<WeakVH
, 16> PhisToOptimize
{PhisToCheck
.begin(),
1347 PhisToCheck
.clear();
1349 unsigned PhisSize
= PhisToOptimize
.size();
1350 while (PhisSize
-- > 0)
1352 cast_or_null
<MemoryPhi
>(PhisToOptimize
.pop_back_val()))
1353 tryRemoveTrivialPhi(MP
);
1357 void MemorySSAUpdater::removeBlocks(
1358 const SmallSetVector
<BasicBlock
*, 8> &DeadBlocks
) {
1359 // First delete all uses of BB in MemoryPhis.
1360 for (BasicBlock
*BB
: DeadBlocks
) {
1361 Instruction
*TI
= BB
->getTerminator();
1362 assert(TI
&& "Basic block expected to have a terminator instruction");
1363 for (BasicBlock
*Succ
: successors(TI
))
1364 if (!DeadBlocks
.count(Succ
))
1365 if (MemoryPhi
*MP
= MSSA
->getMemoryAccess(Succ
)) {
1366 MP
->unorderedDeleteIncomingBlock(BB
);
1367 tryRemoveTrivialPhi(MP
);
1369 // Drop all references of all accesses in BB
1370 if (MemorySSA::AccessList
*Acc
= MSSA
->getWritableBlockAccesses(BB
))
1371 for (MemoryAccess
&MA
: *Acc
)
1372 MA
.dropAllReferences();
1375 // Next, delete all memory accesses in each block
1376 for (BasicBlock
*BB
: DeadBlocks
) {
1377 MemorySSA::AccessList
*Acc
= MSSA
->getWritableBlockAccesses(BB
);
1380 for (MemoryAccess
&MA
: llvm::make_early_inc_range(*Acc
)) {
1381 MSSA
->removeFromLookups(&MA
);
1382 MSSA
->removeFromLists(&MA
);
1387 void MemorySSAUpdater::tryRemoveTrivialPhis(ArrayRef
<WeakVH
> UpdatedPHIs
) {
1388 for (const auto &VH
: UpdatedPHIs
)
1389 if (auto *MPhi
= cast_or_null
<MemoryPhi
>(VH
))
1390 tryRemoveTrivialPhi(MPhi
);
1393 void MemorySSAUpdater::changeToUnreachable(const Instruction
*I
) {
1394 const BasicBlock
*BB
= I
->getParent();
1395 // Remove memory accesses in BB for I and all following instructions.
1396 auto BBI
= I
->getIterator(), BBE
= BB
->end();
1397 // FIXME: If this becomes too expensive, iterate until the first instruction
1398 // with a memory access, then iterate over MemoryAccesses.
1400 removeMemoryAccess(&*(BBI
++));
1401 // Update phis in BB's successors to remove BB.
1402 SmallVector
<WeakVH
, 16> UpdatedPHIs
;
1403 for (const BasicBlock
*Successor
: successors(BB
)) {
1404 removeDuplicatePhiEdgesBetween(BB
, Successor
);
1405 if (MemoryPhi
*MPhi
= MSSA
->getMemoryAccess(Successor
)) {
1406 MPhi
->unorderedDeleteIncomingBlock(BB
);
1407 UpdatedPHIs
.push_back(MPhi
);
1410 // Optimize trivial phis.
1411 tryRemoveTrivialPhis(UpdatedPHIs
);
1414 MemoryAccess
*MemorySSAUpdater::createMemoryAccessInBB(
1415 Instruction
*I
, MemoryAccess
*Definition
, const BasicBlock
*BB
,
1416 MemorySSA::InsertionPlace Point
, bool CreationMustSucceed
) {
1417 MemoryUseOrDef
*NewAccess
= MSSA
->createDefinedAccess(
1418 I
, Definition
, /*Template=*/nullptr, CreationMustSucceed
);
1420 MSSA
->insertIntoListsForBlock(NewAccess
, BB
, Point
);
1424 MemoryUseOrDef
*MemorySSAUpdater::createMemoryAccessBefore(
1425 Instruction
*I
, MemoryAccess
*Definition
, MemoryUseOrDef
*InsertPt
) {
1426 assert(I
->getParent() == InsertPt
->getBlock() &&
1427 "New and old access must be in the same block");
1428 MemoryUseOrDef
*NewAccess
= MSSA
->createDefinedAccess(I
, Definition
);
1429 MSSA
->insertIntoListsBefore(NewAccess
, InsertPt
->getBlock(),
1430 InsertPt
->getIterator());
1434 MemoryUseOrDef
*MemorySSAUpdater::createMemoryAccessAfter(
1435 Instruction
*I
, MemoryAccess
*Definition
, MemoryAccess
*InsertPt
) {
1436 assert(I
->getParent() == InsertPt
->getBlock() &&
1437 "New and old access must be in the same block");
1438 MemoryUseOrDef
*NewAccess
= MSSA
->createDefinedAccess(I
, Definition
);
1439 MSSA
->insertIntoListsBefore(NewAccess
, InsertPt
->getBlock(),
1440 ++InsertPt
->getIterator());