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/SmallPtrSet.h"
16 #include "llvm/ADT/SmallSet.h"
17 #include "llvm/Analysis/MemorySSA.h"
18 #include "llvm/IR/DataLayout.h"
19 #include "llvm/IR/Dominators.h"
20 #include "llvm/IR/GlobalVariable.h"
21 #include "llvm/IR/IRBuilder.h"
22 #include "llvm/IR/IntrinsicInst.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(BasicBlock *BB) {
43 // Single predecessor case, just recurse, we can only have one definition.
44 if (BasicBlock *Pred = BB->getSinglePredecessor()) {
45 return getPreviousDefFromEnd(Pred);
46 } else if (VisitedBlocks.count(BB)) {
47 // We hit our node again, meaning we had a cycle, we must insert a phi
48 // node to break it so we have an operand. The only case this will
49 // insert useless phis is if we have irreducible control flow.
50 return MSSA->createMemoryPhi(BB);
51 } else if (VisitedBlocks.insert(BB).second) {
52 // Mark us visited so we can detect a cycle
53 SmallVector<MemoryAccess *, 8> PhiOps;
55 // Recurse to get the values in our predecessors for placement of a
56 // potential phi node. This will insert phi nodes if we cycle in order to
57 // break the cycle and have an operand.
58 for (auto *Pred : predecessors(BB))
59 PhiOps.push_back(getPreviousDefFromEnd(Pred));
61 // Now try to simplify the ops to avoid placing a phi.
62 // This may return null if we never created a phi yet, that's okay
63 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));
64 bool PHIExistsButNeedsUpdate = false;
65 // See if the existing phi operands match what we need.
66 // Unlike normal SSA, we only allow one phi node per block, so we can't just
68 if (Phi && Phi->getNumOperands() != 0)
69 if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {
70 PHIExistsButNeedsUpdate = true;
73 // See if we can avoid the phi by simplifying it.
74 auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
75 // If we couldn't simplify, we may have to create a phi
78 Phi = MSSA->createMemoryPhi(BB);
80 // These will have been filled in by the recursive read we did above.
81 if (PHIExistsButNeedsUpdate) {
82 std::copy(PhiOps.begin(), PhiOps.end(), Phi->op_begin());
83 std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
86 for (auto *Pred : predecessors(BB))
87 Phi->addIncoming(PhiOps[i++], Pred);
92 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Result))
93 InsertedPHIs.push_back(MP);
94 // Set ourselves up for the next variable by resetting visited state.
95 VisitedBlocks.erase(BB);
98 llvm_unreachable("Should have hit one of the three cases above");
101 // This starts at the memory access, and goes backwards in the block to find the
102 // previous definition. If a definition is not found the block of the access,
103 // it continues globally, creating phi nodes to ensure we have a single
105 MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {
106 auto *LocalResult = getPreviousDefInBlock(MA);
108 return LocalResult ? LocalResult : getPreviousDefRecursive(MA->getBlock());
111 // This starts at the memory access, and goes backwards in the block to the find
112 // the previous definition. If the definition is not found in the block of the
113 // access, it returns nullptr.
114 MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
115 auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());
117 // It's possible there are no defs, or we got handed the first def to start.
119 // If this is a def, we can just use the def iterators.
120 if (!isa<MemoryUse>(MA)) {
121 auto Iter = MA->getReverseDefsIterator();
123 if (Iter != Defs->rend())
126 // Otherwise, have to walk the all access iterator.
127 auto End = MSSA->getWritableBlockAccesses(MA->getBlock())->rend();
128 for (auto &U : make_range(++MA->getReverseIterator(), End))
129 if (!isa<MemoryUse>(U))
130 return cast<MemoryAccess>(&U);
131 // Note that if MA comes before Defs->begin(), we won't hit a def.
138 // This starts at the end of block
139 MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(BasicBlock *BB) {
140 auto *Defs = MSSA->getWritableBlockDefs(BB);
143 return &*Defs->rbegin();
145 return getPreviousDefRecursive(BB);
147 // Recurse over a set of phi uses to eliminate the trivial ones
148 MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {
151 TrackingVH<MemoryAccess> Res(Phi);
152 SmallVector<TrackingVH<Value>, 8> Uses;
153 std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses));
154 for (auto &U : Uses) {
155 if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U)) {
156 auto OperRange = UsePhi->operands();
157 tryRemoveTrivialPhi(UsePhi, OperRange);
163 // Eliminate trivial phis
164 // Phis are trivial if they are defined either by themselves, or all the same
166 // IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
167 // We recursively try to remove them.
168 template <class RangeType>
169 MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
170 RangeType &Operands) {
171 // Detect equal or self arguments
172 MemoryAccess *Same = nullptr;
173 for (auto &Op : Operands) {
174 // If the same or self, good so far
175 if (Op == Phi || Op == Same)
177 // not the same, return the phi since it's not eliminatable by us
180 Same = cast<MemoryAccess>(Op);
182 // Never found a non-self reference, the phi is undef
184 return MSSA->getLiveOnEntryDef();
186 Phi->replaceAllUsesWith(Same);
187 removeMemoryAccess(Phi);
190 // We should only end up recursing in case we replaced something, in which
191 // case, we may have made other Phis trivial.
192 return recursePhi(Same);
195 void MemorySSAUpdater::insertUse(MemoryUse *MU) {
196 InsertedPHIs.clear();
197 MU->setDefiningAccess(getPreviousDef(MU));
198 // Unlike for defs, there is no extra work to do. Because uses do not create
199 // new may-defs, there are only two cases:
201 // 1. There was a def already below us, and therefore, we should not have
202 // created a phi node because it was already needed for the def.
204 // 2. There is no def below us, and therefore, there is no extra renaming work
208 // Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
209 static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
210 MemoryAccess *NewDef) {
211 // Replace any operand with us an incoming block with the new defining
213 int i = MP->getBasicBlockIndex(BB);
214 assert(i != -1 && "Should have found the basic block in the phi");
215 // We can't just compare i against getNumOperands since one is signed and the
216 // other not. So use it to index into the block iterator.
217 for (auto BBIter = MP->block_begin() + i; BBIter != MP->block_end();
221 MP->setIncomingValue(i, NewDef);
226 // A brief description of the algorithm:
227 // First, we compute what should define the new def, using the SSA
228 // construction algorithm.
229 // Then, we update the defs below us (and any new phi nodes) in the graph to
230 // point to the correct new defs, to ensure we only have one variable, and no
231 // disconnected stores.
232 void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
233 InsertedPHIs.clear();
235 // See if we had a local def, and if not, go hunting.
236 MemoryAccess *DefBefore = getPreviousDefInBlock(MD);
237 bool DefBeforeSameBlock = DefBefore != nullptr;
239 DefBefore = getPreviousDefRecursive(MD->getBlock());
241 // There is a def before us, which means we can replace any store/phi uses
242 // of that thing with us, since we are in the way of whatever was there
244 // We now define that def's memorydefs and memoryphis
245 if (DefBeforeSameBlock) {
246 for (auto UI = DefBefore->use_begin(), UE = DefBefore->use_end();
249 // Leave the uses alone
250 if (isa<MemoryUse>(U.getUser()))
256 // and that def is now our defining access.
257 // We change them in this order otherwise we will appear in the use list
258 // above and reset ourselves.
259 MD->setDefiningAccess(DefBefore);
261 SmallVector<MemoryAccess *, 8> FixupList(InsertedPHIs.begin(),
263 if (!DefBeforeSameBlock) {
264 // If there was a local def before us, we must have the same effect it
265 // did. Because every may-def is the same, any phis/etc we would create, it
266 // would also have created. If there was no local def before us, we
267 // performed a global update, and have to search all successors and make
268 // sure we update the first def in each of them (following all paths until
269 // we hit the first def along each path). This may also insert phi nodes.
270 // TODO: There are other cases we can skip this work, such as when we have a
271 // single successor, and only used a straight line of single pred blocks
272 // backwards to find the def. To make that work, we'd have to track whether
273 // getDefRecursive only ever used the single predecessor case. These types
274 // of paths also only exist in between CFG simplifications.
275 FixupList.push_back(MD);
278 while (!FixupList.empty()) {
279 unsigned StartingPHISize = InsertedPHIs.size();
280 fixupDefs(FixupList);
282 // Put any new phis on the fixup list, and process them
283 FixupList.append(InsertedPHIs.end() - StartingPHISize, InsertedPHIs.end());
285 // Now that all fixups are done, rename all uses if we are asked.
287 SmallPtrSet<BasicBlock *, 16> Visited;
288 BasicBlock *StartBlock = MD->getBlock();
289 // We are guaranteed there is a def in the block, because we just got it
290 // handed to us in this function.
291 MemoryAccess *FirstDef = &*MSSA->getWritableBlockDefs(StartBlock)->begin();
292 // Convert to incoming value if it's a memorydef. A phi *is* already an
294 if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
295 FirstDef = MD->getDefiningAccess();
297 MSSA->renamePass(MD->getBlock(), FirstDef, Visited);
298 // We just inserted a phi into this block, so the incoming value will become
299 // the phi anyway, so it does not matter what we pass.
300 for (auto *MP : InsertedPHIs)
301 MSSA->renamePass(MP->getBlock(), nullptr, Visited);
305 void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<MemoryAccess *> &Vars) {
306 SmallPtrSet<const BasicBlock *, 8> Seen;
307 SmallVector<const BasicBlock *, 16> Worklist;
308 for (auto *NewDef : Vars) {
309 // First, see if there is a local def after the operand.
310 auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
311 auto DefIter = NewDef->getDefsIterator();
313 // If there is a local def after us, we only have to rename that.
314 if (++DefIter != Defs->end()) {
315 cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);
319 // Otherwise, we need to search down through the CFG.
320 // For each of our successors, handle it directly if their is a phi, or
321 // place on the fixup worklist.
322 for (const auto *S : successors(NewDef->getBlock())) {
323 if (auto *MP = MSSA->getMemoryAccess(S))
324 setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef);
326 Worklist.push_back(S);
329 while (!Worklist.empty()) {
330 const BasicBlock *FixupBlock = Worklist.back();
333 // Get the first def in the block that isn't a phi node.
334 if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) {
335 auto *FirstDef = &*Defs->begin();
336 // The loop above and below should have taken care of phi nodes
337 assert(!isa<MemoryPhi>(FirstDef) &&
338 "Should have already handled phi nodes!");
339 // We are now this def's defining access, make sure we actually dominate
341 assert(MSSA->dominates(NewDef, FirstDef) &&
342 "Should have dominated the new access");
344 // This may insert new phi nodes, because we are not guaranteed the
345 // block we are processing has a single pred, and depending where the
346 // store was inserted, it may require phi nodes below it.
347 cast<MemoryDef>(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef));
350 // We didn't find a def, so we must continue.
351 for (const auto *S : successors(FixupBlock)) {
352 // If there is a phi node, handle it.
353 // Otherwise, put the block on the worklist
354 if (auto *MP = MSSA->getMemoryAccess(S))
355 setMemoryPhiValueForBlock(MP, FixupBlock, NewDef);
357 // If we cycle, we should have ended up at a phi node that we already
358 // processed. FIXME: Double check this
359 if (!Seen.insert(S).second)
361 Worklist.push_back(S);
368 // Move What before Where in the MemorySSA IR.
369 template <class WhereType>
370 void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
372 // Replace all our users with our defining access.
373 What->replaceAllUsesWith(What->getDefiningAccess());
375 // Let MemorySSA take care of moving it around in the lists.
376 MSSA->moveTo(What, BB, Where);
378 // Now reinsert it into the IR and do whatever fixups needed.
379 if (auto *MD = dyn_cast<MemoryDef>(What))
382 insertUse(cast<MemoryUse>(What));
385 // Move What before Where in the MemorySSA IR.
386 void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
387 moveTo(What, Where->getBlock(), Where->getIterator());
390 // Move What after Where in the MemorySSA IR.
391 void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
392 moveTo(What, Where->getBlock(), ++Where->getIterator());
395 void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
396 MemorySSA::InsertionPlace Where) {
397 return moveTo(What, BB, Where);
400 /// \brief If all arguments of a MemoryPHI are defined by the same incoming
401 /// argument, return that argument.
402 static MemoryAccess *onlySingleValue(MemoryPhi *MP) {
403 MemoryAccess *MA = nullptr;
405 for (auto &Arg : MP->operands()) {
407 MA = cast<MemoryAccess>(Arg);
414 void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA) {
415 assert(!MSSA->isLiveOnEntryDef(MA) &&
416 "Trying to remove the live on entry def");
417 // We can only delete phi nodes if they have no uses, or we can replace all
418 // uses with a single definition.
419 MemoryAccess *NewDefTarget = nullptr;
420 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
421 // Note that it is sufficient to know that all edges of the phi node have
422 // the same argument. If they do, by the definition of dominance frontiers
423 // (which we used to place this phi), that argument must dominate this phi,
424 // and thus, must dominate the phi's uses, and so we will not hit the assert
426 NewDefTarget = onlySingleValue(MP);
427 assert((NewDefTarget || MP->use_empty()) &&
428 "We can't delete this memory phi");
430 NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
433 // Re-point the uses at our defining access
434 if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
435 // Reset optimized on users of this store, and reset the uses.
437 // 1. This is a slightly modified version of RAUW to avoid walking the
439 // 2. If we wanted to be complete, we would have to reset the optimized
440 // flags on users of phi nodes if doing the below makes a phi node have all
441 // the same arguments. Instead, we prefer users to removeMemoryAccess those
442 // phi nodes, because doing it here would be N^3.
443 if (MA->hasValueHandle())
444 ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
445 // Note: We assume MemorySSA is not used in metadata since it's not really
448 while (!MA->use_empty()) {
449 Use &U = *MA->use_begin();
450 if (auto *MUD = dyn_cast<MemoryUseOrDef>(U.getUser()))
451 MUD->resetOptimized();
456 // The call below to erase will destroy MA, so we can't change the order we
457 // are doing things here
458 MSSA->removeFromLookups(MA);
459 MSSA->removeFromLists(MA);
462 MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
463 Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
464 MemorySSA::InsertionPlace Point) {
465 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
466 MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
470 MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore(
471 Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
472 assert(I->getParent() == InsertPt->getBlock() &&
473 "New and old access must be in the same block");
474 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
475 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
476 InsertPt->getIterator());
480 MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(
481 Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
482 assert(I->getParent() == InsertPt->getBlock() &&
483 "New and old access must be in the same block");
484 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
485 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
486 ++InsertPt->getIterator());