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/Analysis/MemorySSA.h"
17 #include "llvm/IR/DataLayout.h"
18 #include "llvm/IR/Dominators.h"
19 #include "llvm/IR/GlobalVariable.h"
20 #include "llvm/IR/IRBuilder.h"
21 #include "llvm/IR/LLVMContext.h"
22 #include "llvm/IR/Metadata.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/FormattedStream.h"
28 #define DEBUG_TYPE "memoryssa"
31 // This is the marker algorithm from "Simple and Efficient Construction of
32 // Static Single Assignment Form"
33 // The simple, non-marker algorithm places phi nodes at any join
34 // Here, we place markers, and only place phi nodes if they end up necessary.
35 // They are only necessary if they break a cycle (IE we recursively visit
36 // ourselves again), or we discover, while getting the value of the operands,
37 // that there are two or more definitions needing to be merged.
38 // This still will leave non-minimal form in the case of irreducible control
39 // flow, where phi nodes may be in cycles with themselves, but unnecessary.
40 MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(BasicBlock *BB) {
41 // Single predecessor case, just recurse, we can only have one definition.
42 if (BasicBlock *Pred = BB->getSinglePredecessor()) {
43 return getPreviousDefFromEnd(Pred);
44 } else if (VisitedBlocks.count(BB)) {
45 // We hit our node again, meaning we had a cycle, we must insert a phi
46 // node to break it so we have an operand. The only case this will
47 // insert useless phis is if we have irreducible control flow.
48 return MSSA->createMemoryPhi(BB);
49 } else if (VisitedBlocks.insert(BB).second) {
50 // Mark us visited so we can detect a cycle
51 SmallVector<MemoryAccess *, 8> PhiOps;
53 // Recurse to get the values in our predecessors for placement of a
54 // potential phi node. This will insert phi nodes if we cycle in order to
55 // break the cycle and have an operand.
56 for (auto *Pred : predecessors(BB))
57 PhiOps.push_back(getPreviousDefFromEnd(Pred));
59 // Now try to simplify the ops to avoid placing a phi.
60 // This may return null if we never created a phi yet, that's okay
61 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));
62 bool PHIExistsButNeedsUpdate = false;
63 // See if the existing phi operands match what we need.
64 // Unlike normal SSA, we only allow one phi node per block, so we can't just
66 if (Phi && Phi->getNumOperands() != 0)
67 if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {
68 PHIExistsButNeedsUpdate = true;
71 // See if we can avoid the phi by simplifying it.
72 auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
73 // If we couldn't simplify, we may have to create a phi
76 Phi = MSSA->createMemoryPhi(BB);
78 // These will have been filled in by the recursive read we did above.
79 if (PHIExistsButNeedsUpdate) {
80 std::copy(PhiOps.begin(), PhiOps.end(), Phi->op_begin());
81 std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
84 for (auto *Pred : predecessors(BB))
85 Phi->addIncoming(PhiOps[i++], Pred);
86 InsertedPHIs.push_back(Phi);
91 // Set ourselves up for the next variable by resetting visited state.
92 VisitedBlocks.erase(BB);
95 llvm_unreachable("Should have hit one of the three cases above");
98 // This starts at the memory access, and goes backwards in the block to find the
99 // previous definition. If a definition is not found the block of the access,
100 // it continues globally, creating phi nodes to ensure we have a single
102 MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {
103 auto *LocalResult = getPreviousDefInBlock(MA);
105 return LocalResult ? LocalResult : getPreviousDefRecursive(MA->getBlock());
108 // This starts at the memory access, and goes backwards in the block to the find
109 // the previous definition. If the definition is not found in the block of the
110 // access, it returns nullptr.
111 MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
112 auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());
114 // It's possible there are no defs, or we got handed the first def to start.
116 // If this is a def, we can just use the def iterators.
117 if (!isa<MemoryUse>(MA)) {
118 auto Iter = MA->getReverseDefsIterator();
120 if (Iter != Defs->rend())
123 // Otherwise, have to walk the all access iterator.
124 auto End = MSSA->getWritableBlockAccesses(MA->getBlock())->rend();
125 for (auto &U : make_range(++MA->getReverseIterator(), End))
126 if (!isa<MemoryUse>(U))
127 return cast<MemoryAccess>(&U);
128 // Note that if MA comes before Defs->begin(), we won't hit a def.
135 // This starts at the end of block
136 MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(BasicBlock *BB) {
137 auto *Defs = MSSA->getWritableBlockDefs(BB);
140 return &*Defs->rbegin();
142 return getPreviousDefRecursive(BB);
144 // Recurse over a set of phi uses to eliminate the trivial ones
145 MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {
148 TrackingVH<MemoryAccess> Res(Phi);
149 SmallVector<TrackingVH<Value>, 8> Uses;
150 std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses));
151 for (auto &U : Uses) {
152 if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U)) {
153 auto OperRange = UsePhi->operands();
154 tryRemoveTrivialPhi(UsePhi, OperRange);
160 // Eliminate trivial phis
161 // Phis are trivial if they are defined either by themselves, or all the same
163 // IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
164 // We recursively try to remove them.
165 template <class RangeType>
166 MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
167 RangeType &Operands) {
168 // Detect equal or self arguments
169 MemoryAccess *Same = nullptr;
170 for (auto &Op : Operands) {
171 // If the same or self, good so far
172 if (Op == Phi || Op == Same)
174 // not the same, return the phi since it's not eliminatable by us
177 Same = cast<MemoryAccess>(Op);
179 // Never found a non-self reference, the phi is undef
181 return MSSA->getLiveOnEntryDef();
183 Phi->replaceAllUsesWith(Same);
184 removeMemoryAccess(Phi);
187 // We should only end up recursing in case we replaced something, in which
188 // case, we may have made other Phis trivial.
189 return recursePhi(Same);
192 void MemorySSAUpdater::insertUse(MemoryUse *MU) {
193 InsertedPHIs.clear();
194 MU->setDefiningAccess(getPreviousDef(MU));
195 // Unlike for defs, there is no extra work to do. Because uses do not create
196 // new may-defs, there are only two cases:
198 // 1. There was a def already below us, and therefore, we should not have
199 // created a phi node because it was already needed for the def.
201 // 2. There is no def below us, and therefore, there is no extra renaming work
205 // Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
206 static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
207 MemoryAccess *NewDef) {
208 // Replace any operand with us an incoming block with the new defining
210 int i = MP->getBasicBlockIndex(BB);
211 assert(i != -1 && "Should have found the basic block in the phi");
212 // We can't just compare i against getNumOperands since one is signed and the
213 // other not. So use it to index into the block iterator.
214 for (auto BBIter = MP->block_begin() + i; BBIter != MP->block_end();
218 MP->setIncomingValue(i, NewDef);
223 // A brief description of the algorithm:
224 // First, we compute what should define the new def, using the SSA
225 // construction algorithm.
226 // Then, we update the defs below us (and any new phi nodes) in the graph to
227 // point to the correct new defs, to ensure we only have one variable, and no
228 // disconnected stores.
229 void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
230 InsertedPHIs.clear();
232 // See if we had a local def, and if not, go hunting.
233 MemoryAccess *DefBefore = getPreviousDefInBlock(MD);
234 bool DefBeforeSameBlock = DefBefore != nullptr;
236 DefBefore = getPreviousDefRecursive(MD->getBlock());
238 // There is a def before us, which means we can replace any store/phi uses
239 // of that thing with us, since we are in the way of whatever was there
241 // We now define that def's memorydefs and memoryphis
242 if (DefBeforeSameBlock) {
243 for (auto UI = DefBefore->use_begin(), UE = DefBefore->use_end();
246 // Leave the uses alone
247 if (isa<MemoryUse>(U.getUser()))
253 // and that def is now our defining access.
254 // We change them in this order otherwise we will appear in the use list
255 // above and reset ourselves.
256 MD->setDefiningAccess(DefBefore);
258 SmallVector<MemoryAccess *, 8> FixupList(InsertedPHIs.begin(),
260 if (!DefBeforeSameBlock) {
261 // If there was a local def before us, we must have the same effect it
262 // did. Because every may-def is the same, any phis/etc we would create, it
263 // would also have created. If there was no local def before us, we
264 // performed a global update, and have to search all successors and make
265 // sure we update the first def in each of them (following all paths until
266 // we hit the first def along each path). This may also insert phi nodes.
267 // TODO: There are other cases we can skip this work, such as when we have a
268 // single successor, and only used a straight line of single pred blocks
269 // backwards to find the def. To make that work, we'd have to track whether
270 // getDefRecursive only ever used the single predecessor case. These types
271 // of paths also only exist in between CFG simplifications.
272 FixupList.push_back(MD);
275 while (!FixupList.empty()) {
276 unsigned StartingPHISize = InsertedPHIs.size();
277 fixupDefs(FixupList);
279 // Put any new phis on the fixup list, and process them
280 FixupList.append(InsertedPHIs.end() - StartingPHISize, InsertedPHIs.end());
282 // Now that all fixups are done, rename all uses if we are asked.
284 SmallPtrSet<BasicBlock *, 16> Visited;
285 BasicBlock *StartBlock = MD->getBlock();
286 // We are guaranteed there is a def in the block, because we just got it
287 // handed to us in this function.
288 MemoryAccess *FirstDef = &*MSSA->getWritableBlockDefs(StartBlock)->begin();
289 // Convert to incoming value if it's a memorydef. A phi *is* already an
291 if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
292 FirstDef = MD->getDefiningAccess();
294 MSSA->renamePass(MD->getBlock(), FirstDef, Visited);
295 // We just inserted a phi into this block, so the incoming value will become
296 // the phi anyway, so it does not matter what we pass.
297 for (auto *MP : InsertedPHIs)
298 MSSA->renamePass(MP->getBlock(), nullptr, Visited);
302 void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<MemoryAccess *> &Vars) {
303 SmallPtrSet<const BasicBlock *, 8> Seen;
304 SmallVector<const BasicBlock *, 16> Worklist;
305 for (auto *NewDef : Vars) {
306 // First, see if there is a local def after the operand.
307 auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
308 auto DefIter = NewDef->getDefsIterator();
310 // If there is a local def after us, we only have to rename that.
311 if (++DefIter != Defs->end()) {
312 cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);
316 // Otherwise, we need to search down through the CFG.
317 // For each of our successors, handle it directly if their is a phi, or
318 // place on the fixup worklist.
319 for (const auto *S : successors(NewDef->getBlock())) {
320 if (auto *MP = MSSA->getMemoryAccess(S))
321 setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef);
323 Worklist.push_back(S);
326 while (!Worklist.empty()) {
327 const BasicBlock *FixupBlock = Worklist.back();
330 // Get the first def in the block that isn't a phi node.
331 if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) {
332 auto *FirstDef = &*Defs->begin();
333 // The loop above and below should have taken care of phi nodes
334 assert(!isa<MemoryPhi>(FirstDef) &&
335 "Should have already handled phi nodes!");
336 // We are now this def's defining access, make sure we actually dominate
338 assert(MSSA->dominates(NewDef, FirstDef) &&
339 "Should have dominated the new access");
341 // This may insert new phi nodes, because we are not guaranteed the
342 // block we are processing has a single pred, and depending where the
343 // store was inserted, it may require phi nodes below it.
344 cast<MemoryDef>(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef));
347 // We didn't find a def, so we must continue.
348 for (const auto *S : successors(FixupBlock)) {
349 // If there is a phi node, handle it.
350 // Otherwise, put the block on the worklist
351 if (auto *MP = MSSA->getMemoryAccess(S))
352 setMemoryPhiValueForBlock(MP, FixupBlock, NewDef);
354 // If we cycle, we should have ended up at a phi node that we already
355 // processed. FIXME: Double check this
356 if (!Seen.insert(S).second)
358 Worklist.push_back(S);
365 // Move What before Where in the MemorySSA IR.
366 template <class WhereType>
367 void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
369 // Replace all our users with our defining access.
370 What->replaceAllUsesWith(What->getDefiningAccess());
372 // Let MemorySSA take care of moving it around in the lists.
373 MSSA->moveTo(What, BB, Where);
375 // Now reinsert it into the IR and do whatever fixups needed.
376 if (auto *MD = dyn_cast<MemoryDef>(What))
379 insertUse(cast<MemoryUse>(What));
382 // Move What before Where in the MemorySSA IR.
383 void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
384 moveTo(What, Where->getBlock(), Where->getIterator());
387 // Move What after Where in the MemorySSA IR.
388 void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
389 moveTo(What, Where->getBlock(), ++Where->getIterator());
392 void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
393 MemorySSA::InsertionPlace Where) {
394 return moveTo(What, BB, Where);
397 /// \brief If all arguments of a MemoryPHI are defined by the same incoming
398 /// argument, return that argument.
399 static MemoryAccess *onlySingleValue(MemoryPhi *MP) {
400 MemoryAccess *MA = nullptr;
402 for (auto &Arg : MP->operands()) {
404 MA = cast<MemoryAccess>(Arg);
411 void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA) {
412 assert(!MSSA->isLiveOnEntryDef(MA) &&
413 "Trying to remove the live on entry def");
414 // We can only delete phi nodes if they have no uses, or we can replace all
415 // uses with a single definition.
416 MemoryAccess *NewDefTarget = nullptr;
417 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
418 // Note that it is sufficient to know that all edges of the phi node have
419 // the same argument. If they do, by the definition of dominance frontiers
420 // (which we used to place this phi), that argument must dominate this phi,
421 // and thus, must dominate the phi's uses, and so we will not hit the assert
423 NewDefTarget = onlySingleValue(MP);
424 assert((NewDefTarget || MP->use_empty()) &&
425 "We can't delete this memory phi");
427 NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
430 // Re-point the uses at our defining access
431 if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
432 // Reset optimized on users of this store, and reset the uses.
434 // 1. This is a slightly modified version of RAUW to avoid walking the
436 // 2. If we wanted to be complete, we would have to reset the optimized
437 // flags on users of phi nodes if doing the below makes a phi node have all
438 // the same arguments. Instead, we prefer users to removeMemoryAccess those
439 // phi nodes, because doing it here would be N^3.
440 if (MA->hasValueHandle())
441 ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
442 // Note: We assume MemorySSA is not used in metadata since it's not really
445 while (!MA->use_empty()) {
446 Use &U = *MA->use_begin();
447 if (auto *MUD = dyn_cast<MemoryUseOrDef>(U.getUser()))
448 MUD->resetOptimized();
453 // The call below to erase will destroy MA, so we can't change the order we
454 // are doing things here
455 MSSA->removeFromLookups(MA);
456 MSSA->removeFromLists(MA);
459 MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
460 Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
461 MemorySSA::InsertionPlace Point) {
462 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
463 MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
467 MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore(
468 Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
469 assert(I->getParent() == InsertPt->getBlock() &&
470 "New and old access must be in the same block");
471 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
472 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
473 InsertPt->getIterator());
477 MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(
478 Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
479 assert(I->getParent() == InsertPt->getBlock() &&
480 "New and old access must be in the same block");
481 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
482 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
483 ++InsertPt->getIterator());