LLVM 19.0.0git
MemorySSAUpdater.cpp
Go to the documentation of this file.
1//===-- MemorySSAUpdater.cpp - Memory SSA Updater--------------------===//
2//
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
6//
7//===----------------------------------------------------------------===//
8//
9// This file implements the MemorySSAUpdater class.
10//
11//===----------------------------------------------------------------===//
13#include "llvm/ADT/STLExtras.h"
14#include "llvm/ADT/SetVector.h"
19#include "llvm/IR/BasicBlock.h"
20#include "llvm/IR/Dominators.h"
21#include "llvm/Support/Debug.h"
22#include <algorithm>
23
24#define DEBUG_TYPE "memoryssa"
25using namespace llvm;
26
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.
36MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(
37 BasicBlock *BB,
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;
44
45 // If this method is called from an unreachable block, return LoE.
46 if (!MSSA->DT->isReachableFromEntry(BB))
47 return MSSA->getLiveOnEntryDef();
48
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});
54 return Result;
55 }
56
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});
63 return Result;
64 }
65
66 if (VisitedBlocks.insert(BB).second) {
67 // Mark us visited so we can detect a cycle
69
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);
78 if (!SingleAccess)
79 SingleAccess = IncomingAccess;
80 else if (IncomingAccess != SingleAccess)
81 UniqueIncomingAccess = false;
82 PhiOps.push_back(IncomingAccess);
83 } else
84 PhiOps.push_back(MSSA->getLiveOnEntryDef());
85 }
86
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));
90
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.
96 if (Phi) {
97 assert(Phi->operands().empty() && "Expected empty Phi");
98 Phi->replaceAllUsesWith(SingleAccess);
100 }
101 Result = SingleAccess;
102 } else if (Result == Phi && !(UniqueIncomingAccess && SingleAccess)) {
103 if (!Phi)
104 Phi = MSSA->createMemoryPhi(BB);
105
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
108 // create a new one.
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());
115 }
116 } else {
117 unsigned i = 0;
118 for (auto *Pred : predecessors(BB))
119 Phi->addIncoming(&*PhiOps[i++], Pred);
120 InsertedPHIs.push_back(Phi);
121 }
122 Result = Phi;
123 }
124
125 // Set ourselves up for the next variable by resetting visited state.
126 VisitedBlocks.erase(BB);
127 CachedPreviousDef.insert({BB, Result});
128 return Result;
129 }
130 llvm_unreachable("Should have hit one of the three cases above");
131}
132
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
136// definition.
137MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {
138 if (auto *LocalResult = getPreviousDefInBlock(MA))
139 return LocalResult;
141 return getPreviousDefRecursive(MA->getBlock(), CachedPreviousDef);
142}
143
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.
147MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
148 auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());
149
150 // It's possible there are no defs, or we got handed the first def to start.
151 if (Defs) {
152 // If this is a def, we can just use the def iterators.
153 if (!isa<MemoryUse>(MA)) {
154 auto Iter = MA->getReverseDefsIterator();
155 ++Iter;
156 if (Iter != Defs->rend())
157 return &*Iter;
158 } else {
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.
165 return nullptr;
166 }
167 }
168 return nullptr;
169}
170
171// This starts at the end of block
172MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(
173 BasicBlock *BB,
174 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
175 auto *Defs = MSSA->getWritableBlockDefs(BB);
176
177 if (Defs) {
178 CachedPreviousDef.insert({BB, &*Defs->rbegin()});
179 return &*Defs->rbegin();
180 }
181
182 return getPreviousDefRecursive(BB, CachedPreviousDef);
183}
184// Recurse over a set of phi uses to eliminate the trivial ones
185MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {
186 if (!Phi)
187 return nullptr;
190 std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses));
191 for (auto &U : Uses)
192 if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U))
193 tryRemoveTrivialPhi(UsePhi);
194 return Res;
195}
196
197// Eliminate trivial phis
198// Phis are trivial if they are defined either by themselves, or all the same
199// argument.
200// IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
201// We recursively try to remove them.
202MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi) {
203 assert(Phi && "Can only remove concrete Phi.");
204 auto OperRange = Phi->operands();
205 return tryRemoveTrivialPhi(Phi, OperRange);
206}
207template <class RangeType>
208MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
209 RangeType &Operands) {
210 // Bail out on non-opt Phis.
211 if (NonOptPhis.count(Phi))
212 return Phi;
213
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)
219 continue;
220 // not the same, return the phi since it's not eliminatable by us
221 if (Same)
222 return Phi;
223 Same = cast<MemoryAccess>(&*Op);
224 }
225 // Never found a non-self reference, the phi is undef
226 if (Same == nullptr)
227 return MSSA->getLiveOnEntryDef();
228 if (Phi) {
229 Phi->replaceAllUsesWith(Same);
231 }
232
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);
236}
237
238void MemorySSAUpdater::insertUse(MemoryUse *MU, bool RenameUses) {
239 VisitedBlocks.clear();
240 InsertedPHIs.clear();
241 MU->setDefiningAccess(getPreviousDef(MU));
242
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.
247 //
248 // 2. There is no def below us, and therefore, there is no extra renaming work
249 // to do.
250
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.
255
256 if (!RenameUses && !InsertedPHIs.empty()) {
257 auto *Defs = MSSA->getBlockDefs(MU->getBlock());
258 (void)Defs;
259 assert((!Defs || (++Defs->begin() == Defs->end())) &&
260 "Block may have only a Phi or no defs");
261 }
262
263 if (RenameUses && InsertedPHIs.size()) {
265 BasicBlock *StartBlock = MU->getBlock();
266
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
270 // incoming value.
271 if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
272 FirstDef = MD->getDefiningAccess();
273
274 MSSA->renamePass(MU->getBlock(), FirstDef, Visited);
275 }
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);
281 }
282}
283
284// Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
286 MemoryAccess *NewDef) {
287 // Replace any operand with us an incoming block with the new defining
288 // access.
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)) {
294 if (BlockBB != BB)
295 break;
296 MP->setIncomingValue(i, NewDef);
297 ++i;
298 }
299}
300
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.
307void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
308 // Don't bother updating dead code.
309 if (!MSSA->DT->isReachableFromEntry(MD->getBlock())) {
311 return;
312 }
313
314 VisitedBlocks.clear();
315 InsertedPHIs.clear();
316
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;
324
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
327 // before.
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.
337 });
338 }
339
340 // and that def is now our defining access.
341 MD->setDefiningAccess(DefBefore);
342
343 SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());
344
345 SmallSet<WeakVH, 8> ExistingPhis;
346
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.
361
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;
365
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);
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);
381 if (!MPhi) {
382 MPhi = MSSA->createMemoryPhi(BBIDF);
383 NewInsertedPHIs.push_back(MPhi);
384 } else {
385 ExistingPhis.insert(MPhi);
386 }
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);
394 }
395 for (auto &MPhi : NewInsertedPHIs) {
396 auto *BBIDF = MPhi->getBlock();
397 for (auto *Pred : predecessors(BBIDF)) {
399 MPhi->addIncoming(getPreviousDefFromEnd(Pred, CachedPreviousDef), Pred);
400 }
401 }
402
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);
409 }
410
411 FixupList.push_back(MD);
412 }
413
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();
417
418 while (!FixupList.empty()) {
419 unsigned StartingPHISize = InsertedPHIs.size();
420 fixupDefs(FixupList);
421 FixupList.clear();
422 // Put any new phis on the fixup list, and process them
423 FixupList.append(InsertedPHIs.begin() + StartingPHISize, InsertedPHIs.end());
424 }
425
426 // Optimize potentially non-minimal phis added in this method.
427 unsigned NewPhiSize = NewPhiIndexEnd - NewPhiIndex;
428 if (NewPhiSize)
429 tryRemoveTrivialPhis(ArrayRef<WeakVH>(&InsertedPHIs[NewPhiIndex], NewPhiSize));
430
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();
434 if (RenameUses) {
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
440 // incoming value.
441 if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
442 FirstDef = MD->getDefiningAccess();
443
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);
449 if (Phi)
450 MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
451 }
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);
456 if (Phi)
457 MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
458 }
459 }
460}
461
462void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<WeakVH> &Vars) {
465 for (const auto &Var : Vars) {
466 MemoryAccess *NewDef = dyn_cast_or_null<MemoryAccess>(Var);
467 if (!NewDef)
468 continue;
469 // First, see if there is a local def after the operand.
470 auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
471 auto DefIter = NewDef->getDefsIterator();
472
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);
476
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);
480 continue;
481 }
482
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);
489 else
490 Worklist.push_back(S);
491 }
492
493 while (!Worklist.empty()) {
494 const BasicBlock *FixupBlock = Worklist.pop_back_val();
495
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
503 // it
504 assert(MSSA->dominates(NewDef, FirstDef) &&
505 "Should have dominated the new access");
506
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));
511 return;
512 }
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);
519 else {
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)
523 continue;
524 Worklist.push_back(S);
525 }
526 }
527 }
528 }
529}
530
532 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
533 MPhi->unorderedDeleteIncomingBlock(From);
534 tryRemoveTrivialPhi(MPhi);
535 }
536}
537
539 const BasicBlock *To) {
540 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
541 bool Found = false;
542 MPhi->unorderedDeleteIncomingIf([&](const MemoryAccess *, BasicBlock *B) {
543 if (From != B)
544 return false;
545 if (Found)
546 return true;
547 Found = true;
548 return false;
549 });
550 tryRemoveTrivialPhi(MPhi);
551 }
552}
553
554/// If all arguments of a MemoryPHI are defined by the same incoming
555/// argument, return that argument.
557 MemoryAccess *MA = nullptr;
558
559 for (auto &Arg : MP->operands()) {
560 if (!MA)
561 MA = cast<MemoryAccess>(Arg);
562 else if (MA != Arg)
563 return nullptr;
564 }
565 return MA;
566}
567
569 const ValueToValueMapTy &VMap,
570 PhiToDefMap &MPhiMap,
571 MemorySSA *MSSA) {
572 MemoryAccess *InsnDefining = MA;
573 if (MemoryDef *DefMUD = dyn_cast<MemoryDef>(InsnDefining)) {
574 if (!MSSA->isLiveOnEntryDef(DefMUD)) {
575 Instruction *DefMUDI = DefMUD->getMemoryInst();
576 assert(DefMUDI && "Found MemoryUseOrDef with no Instruction.");
577 if (Instruction *NewDefMUDI =
578 cast_or_null<Instruction>(VMap.lookup(DefMUDI))) {
579 InsnDefining = MSSA->getMemoryAccess(NewDefMUDI);
580 if (!InsnDefining || isa<MemoryUse>(InsnDefining)) {
581 // The clone was simplified, it's no longer a MemoryDef, look up.
582 InsnDefining = getNewDefiningAccessForClone(
583 DefMUD->getDefiningAccess(), VMap, MPhiMap, MSSA);
584 }
585 }
586 }
587 } else {
588 MemoryPhi *DefPhi = cast<MemoryPhi>(InsnDefining);
589 if (MemoryAccess *NewDefPhi = MPhiMap.lookup(DefPhi))
590 InsnDefining = NewDefPhi;
591 }
592 assert(InsnDefining && "Defining instruction cannot be nullptr.");
593 return InsnDefining;
594}
595
596void MemorySSAUpdater::cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
597 const ValueToValueMapTy &VMap,
598 PhiToDefMap &MPhiMap,
599 bool CloneWasSimplified) {
600 const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
601 if (!Acc)
602 return;
603 for (const MemoryAccess &MA : *Acc) {
604 if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&MA)) {
605 Instruction *Insn = MUD->getMemoryInst();
606 // Entry does not exist if the clone of the block did not clone all
607 // instructions. This occurs in LoopRotate when cloning instructions
608 // from the old header to the old preheader. The cloned instruction may
609 // also be a simplified Value, not an Instruction (see LoopRotate).
610 // Also in LoopRotate, even when it's an instruction, due to it being
611 // simplified, it may be a Use rather than a Def, so we cannot use MUD as
612 // template. Calls coming from updateForClonedBlockIntoPred, ensure this.
613 if (Instruction *NewInsn =
614 dyn_cast_or_null<Instruction>(VMap.lookup(Insn))) {
615 MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(
616 NewInsn,
617 getNewDefiningAccessForClone(MUD->getDefiningAccess(), VMap,
618 MPhiMap, MSSA),
619 /*Template=*/CloneWasSimplified ? nullptr : MUD,
620 /*CreationMustSucceed=*/false);
621 if (NewUseOrDef)
622 MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
623 }
624 }
625 }
626}
627
629 BasicBlock *Header, BasicBlock *Preheader, BasicBlock *BEBlock) {
630 auto *MPhi = MSSA->getMemoryAccess(Header);
631 if (!MPhi)
632 return;
633
634 // Create phi node in the backedge block and populate it with the same
635 // incoming values as MPhi. Skip incoming values coming from Preheader.
636 auto *NewMPhi = MSSA->createMemoryPhi(BEBlock);
637 bool HasUniqueIncomingValue = true;
638 MemoryAccess *UniqueValue = nullptr;
639 for (unsigned I = 0, E = MPhi->getNumIncomingValues(); I != E; ++I) {
640 BasicBlock *IBB = MPhi->getIncomingBlock(I);
641 MemoryAccess *IV = MPhi->getIncomingValue(I);
642 if (IBB != Preheader) {
643 NewMPhi->addIncoming(IV, IBB);
644 if (HasUniqueIncomingValue) {
645 if (!UniqueValue)
646 UniqueValue = IV;
647 else if (UniqueValue != IV)
648 HasUniqueIncomingValue = false;
649 }
650 }
651 }
652
653 // Update incoming edges into MPhi. Remove all but the incoming edge from
654 // Preheader. Add an edge from NewMPhi
655 auto *AccFromPreheader = MPhi->getIncomingValueForBlock(Preheader);
656 MPhi->setIncomingValue(0, AccFromPreheader);
657 MPhi->setIncomingBlock(0, Preheader);
658 for (unsigned I = MPhi->getNumIncomingValues() - 1; I >= 1; --I)
659 MPhi->unorderedDeleteIncoming(I);
660 MPhi->addIncoming(NewMPhi, BEBlock);
661
662 // If NewMPhi is a trivial phi, remove it. Its use in the header MPhi will be
663 // replaced with the unique value.
664 tryRemoveTrivialPhi(NewMPhi);
665}
666
668 ArrayRef<BasicBlock *> ExitBlocks,
669 const ValueToValueMapTy &VMap,
670 bool IgnoreIncomingWithNoClones) {
671 PhiToDefMap MPhiMap;
672
673 auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) {
674 assert(Phi && NewPhi && "Invalid Phi nodes.");
675 BasicBlock *NewPhiBB = NewPhi->getBlock();
676 SmallPtrSet<BasicBlock *, 4> NewPhiBBPreds(pred_begin(NewPhiBB),
677 pred_end(NewPhiBB));
678 for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; ++It) {
679 MemoryAccess *IncomingAccess = Phi->getIncomingValue(It);
680 BasicBlock *IncBB = Phi->getIncomingBlock(It);
681
682 if (BasicBlock *NewIncBB = cast_or_null<BasicBlock>(VMap.lookup(IncBB)))
683 IncBB = NewIncBB;
684 else if (IgnoreIncomingWithNoClones)
685 continue;
686
687 // Now we have IncBB, and will need to add incoming from it to NewPhi.
688
689 // If IncBB is not a predecessor of NewPhiBB, then do not add it.
690 // NewPhiBB was cloned without that edge.
691 if (!NewPhiBBPreds.count(IncBB))
692 continue;
693
694 // Determine incoming value and add it as incoming from IncBB.
695 NewPhi->addIncoming(
696 getNewDefiningAccessForClone(IncomingAccess, VMap, MPhiMap, MSSA),
697 IncBB);
698 }
699 if (auto *SingleAccess = onlySingleValue(NewPhi)) {
700 MPhiMap[Phi] = SingleAccess;
701 removeMemoryAccess(NewPhi);
702 }
703 };
704
705 auto ProcessBlock = [&](BasicBlock *BB) {
706 BasicBlock *NewBlock = cast_or_null<BasicBlock>(VMap.lookup(BB));
707 if (!NewBlock)
708 return;
709
710 assert(!MSSA->getWritableBlockAccesses(NewBlock) &&
711 "Cloned block should have no accesses");
712
713 // Add MemoryPhi.
714 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) {
715 MemoryPhi *NewPhi = MSSA->createMemoryPhi(NewBlock);
716 MPhiMap[MPhi] = NewPhi;
717 }
718 // Update Uses and Defs.
719 cloneUsesAndDefs(BB, NewBlock, VMap, MPhiMap);
720 };
721
722 for (auto *BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
723 ProcessBlock(BB);
724
725 for (auto *BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
726 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
727 if (MemoryAccess *NewPhi = MPhiMap.lookup(MPhi))
728 FixPhiIncomingValues(MPhi, cast<MemoryPhi>(NewPhi));
729}
730
732 BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM) {
733 // All defs/phis from outside BB that are used in BB, are valid uses in P1.
734 // Since those defs/phis must have dominated BB, and also dominate P1.
735 // Defs from BB being used in BB will be replaced with the cloned defs from
736 // VM. The uses of BB's Phi (if it exists) in BB will be replaced by the
737 // incoming def into the Phi from P1.
738 // Instructions cloned into the predecessor are in practice sometimes
739 // simplified, so disable the use of the template, and create an access from
740 // scratch.
741 PhiToDefMap MPhiMap;
742 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
743 MPhiMap[MPhi] = MPhi->getIncomingValueForBlock(P1);
744 cloneUsesAndDefs(BB, P1, VM, MPhiMap, /*CloneWasSimplified=*/true);
745}
746
747template <typename Iter>
748void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop(
749 ArrayRef<BasicBlock *> ExitBlocks, Iter ValuesBegin, Iter ValuesEnd,
750 DominatorTree &DT) {
752 // Update/insert phis in all successors of exit blocks.
753 for (auto *Exit : ExitBlocks)
754 for (const ValueToValueMapTy *VMap : make_range(ValuesBegin, ValuesEnd))
755 if (BasicBlock *NewExit = cast_or_null<BasicBlock>(VMap->lookup(Exit))) {
756 BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
757 Updates.push_back({DT.Insert, NewExit, ExitSucc});
758 }
759 applyInsertUpdates(Updates, DT);
760}
761
763 ArrayRef<BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap,
764 DominatorTree &DT) {
765 const ValueToValueMapTy *const Arr[] = {&VMap};
766 privateUpdateExitBlocksForClonedLoop(ExitBlocks, std::begin(Arr),
767 std::end(Arr), DT);
768}
769
771 ArrayRef<BasicBlock *> ExitBlocks,
772 ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT) {
773 auto GetPtr = [&](const std::unique_ptr<ValueToValueMapTy> &I) {
774 return I.get();
775 };
776 using MappedIteratorType =
778 decltype(GetPtr)>;
779 auto MapBegin = MappedIteratorType(VMaps.begin(), GetPtr);
780 auto MapEnd = MappedIteratorType(VMaps.end(), GetPtr);
781 privateUpdateExitBlocksForClonedLoop(ExitBlocks, MapBegin, MapEnd, DT);
782}
783
785 DominatorTree &DT, bool UpdateDT) {
786 SmallVector<CFGUpdate, 4> DeleteUpdates;
787 SmallVector<CFGUpdate, 4> RevDeleteUpdates;
788 SmallVector<CFGUpdate, 4> InsertUpdates;
789 for (const auto &Update : Updates) {
790 if (Update.getKind() == DT.Insert)
791 InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
792 else {
793 DeleteUpdates.push_back({DT.Delete, Update.getFrom(), Update.getTo()});
794 RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
795 }
796 }
797
798 if (!DeleteUpdates.empty()) {
799 if (!InsertUpdates.empty()) {
800 if (!UpdateDT) {
802 // Deletes are reversed applied, because this CFGView is pretending the
803 // deletes did not happen yet, hence the edges still exist.
804 DT.applyUpdates(Empty, RevDeleteUpdates);
805 } else {
806 // Apply all updates, with the RevDeleteUpdates as PostCFGView.
807 DT.applyUpdates(Updates, RevDeleteUpdates);
808 }
809
810 // Note: the MSSA update below doesn't distinguish between a GD with
811 // (RevDelete,false) and (Delete, true), but this matters for the DT
812 // updates above; for "children" purposes they are equivalent; but the
813 // updates themselves convey the desired update, used inside DT only.
814 GraphDiff<BasicBlock *> GD(RevDeleteUpdates);
815 applyInsertUpdates(InsertUpdates, DT, &GD);
816 // Update DT to redelete edges; this matches the real CFG so we can
817 // perform the standard update without a postview of the CFG.
818 DT.applyUpdates(DeleteUpdates);
819 } else {
820 if (UpdateDT)
821 DT.applyUpdates(DeleteUpdates);
822 }
823 } else {
824 if (UpdateDT)
825 DT.applyUpdates(Updates);
827 applyInsertUpdates(InsertUpdates, DT, &GD);
828 }
829
830 // Update for deleted edges
831 for (auto &Update : DeleteUpdates)
832 removeEdge(Update.getFrom(), Update.getTo());
833}
834
836 DominatorTree &DT) {
838 applyInsertUpdates(Updates, DT, &GD);
839}
840
842 DominatorTree &DT,
843 const GraphDiff<BasicBlock *> *GD) {
844 // Get recursive last Def, assuming well formed MSSA and updated DT.
845 auto GetLastDef = [&](BasicBlock *BB) -> MemoryAccess * {
846 while (true) {
848 // Return last Def or Phi in BB, if it exists.
849 if (Defs)
850 return &*(--Defs->end());
851
852 // Check number of predecessors, we only care if there's more than one.
853 unsigned Count = 0;
854 BasicBlock *Pred = nullptr;
855 for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BB)) {
856 Pred = Pi;
857 Count++;
858 if (Count == 2)
859 break;
860 }
861
862 // If BB has multiple predecessors, get last definition from IDom.
863 if (Count != 1) {
864 // [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its
865 // DT is invalidated. Return LoE as its last def. This will be added to
866 // MemoryPhi node, and later deleted when the block is deleted.
867 if (!DT.getNode(BB))
868 return MSSA->getLiveOnEntryDef();
869 if (auto *IDom = DT.getNode(BB)->getIDom())
870 if (IDom->getBlock() != BB) {
871 BB = IDom->getBlock();
872 continue;
873 }
874 return MSSA->getLiveOnEntryDef();
875 } else {
876 // Single predecessor, BB cannot be dead. GetLastDef of Pred.
877 assert(Count == 1 && Pred && "Single predecessor expected.");
878 // BB can be unreachable though, return LoE if that is the case.
879 if (!DT.getNode(BB))
880 return MSSA->getLiveOnEntryDef();
881 BB = Pred;
882 }
883 };
884 llvm_unreachable("Unable to get last definition.");
885 };
886
887 // Get nearest IDom given a set of blocks.
888 // TODO: this can be optimized by starting the search at the node with the
889 // lowest level (highest in the tree).
890 auto FindNearestCommonDominator =
891 [&](const SmallSetVector<BasicBlock *, 2> &BBSet) -> BasicBlock * {
892 BasicBlock *PrevIDom = *BBSet.begin();
893 for (auto *BB : BBSet)
894 PrevIDom = DT.findNearestCommonDominator(PrevIDom, BB);
895 return PrevIDom;
896 };
897
898 // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not
899 // include CurrIDom.
900 auto GetNoLongerDomBlocks =
901 [&](BasicBlock *PrevIDom, BasicBlock *CurrIDom,
902 SmallVectorImpl<BasicBlock *> &BlocksPrevDom) {
903 if (PrevIDom == CurrIDom)
904 return;
905 BlocksPrevDom.push_back(PrevIDom);
906 BasicBlock *NextIDom = PrevIDom;
907 while (BasicBlock *UpIDom =
908 DT.getNode(NextIDom)->getIDom()->getBlock()) {
909 if (UpIDom == CurrIDom)
910 break;
911 BlocksPrevDom.push_back(UpIDom);
912 NextIDom = UpIDom;
913 }
914 };
915
916 // Map a BB to its predecessors: added + previously existing. To get a
917 // deterministic order, store predecessors as SetVectors. The order in each
918 // will be defined by the order in Updates (fixed) and the order given by
919 // children<> (also fixed). Since we further iterate over these ordered sets,
920 // we lose the information of multiple edges possibly existing between two
921 // blocks, so we'll keep and EdgeCount map for that.
922 // An alternate implementation could keep unordered set for the predecessors,
923 // traverse either Updates or children<> each time to get the deterministic
924 // order, and drop the usage of EdgeCount. This alternate approach would still
925 // require querying the maps for each predecessor, and children<> call has
926 // additional computation inside for creating the snapshot-graph predecessors.
927 // As such, we favor using a little additional storage and less compute time.
928 // This decision can be revisited if we find the alternative more favorable.
929
930 struct PredInfo {
933 };
935
936 for (const auto &Edge : Updates) {
937 BasicBlock *BB = Edge.getTo();
938 auto &AddedBlockSet = PredMap[BB].Added;
939 AddedBlockSet.insert(Edge.getFrom());
940 }
941
942 // Store all existing predecessor for each BB, at least one must exist.
945 for (auto &BBPredPair : PredMap) {
946 auto *BB = BBPredPair.first;
947 const auto &AddedBlockSet = BBPredPair.second.Added;
948 auto &PrevBlockSet = BBPredPair.second.Prev;
949 for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BB)) {
950 if (!AddedBlockSet.count(Pi))
951 PrevBlockSet.insert(Pi);
952 EdgeCountMap[{Pi, BB}]++;
953 }
954
955 if (PrevBlockSet.empty()) {
956 assert(pred_size(BB) == AddedBlockSet.size() && "Duplicate edges added.");
958 dbgs()
959 << "Adding a predecessor to a block with no predecessors. "
960 "This must be an edge added to a new, likely cloned, block. "
961 "Its memory accesses must be already correct, assuming completed "
962 "via the updateExitBlocksForClonedLoop API. "
963 "Assert a single such edge is added so no phi addition or "
964 "additional processing is required.\n");
965 assert(AddedBlockSet.size() == 1 &&
966 "Can only handle adding one predecessor to a new block.");
967 // Need to remove new blocks from PredMap. Remove below to not invalidate
968 // iterator here.
969 NewBlocks.insert(BB);
970 }
971 }
972 // Nothing to process for new/cloned blocks.
973 for (auto *BB : NewBlocks)
974 PredMap.erase(BB);
975
976 SmallVector<BasicBlock *, 16> BlocksWithDefsToReplace;
977 SmallVector<WeakVH, 8> InsertedPhis;
978
979 // First create MemoryPhis in all blocks that don't have one. Create in the
980 // order found in Updates, not in PredMap, to get deterministic numbering.
981 for (const auto &Edge : Updates) {
982 BasicBlock *BB = Edge.getTo();
983 if (PredMap.count(BB) && !MSSA->getMemoryAccess(BB))
984 InsertedPhis.push_back(MSSA->createMemoryPhi(BB));
985 }
986
987 // Now we'll fill in the MemoryPhis with the right incoming values.
988 for (auto &BBPredPair : PredMap) {
989 auto *BB = BBPredPair.first;
990 const auto &PrevBlockSet = BBPredPair.second.Prev;
991 const auto &AddedBlockSet = BBPredPair.second.Added;
992 assert(!PrevBlockSet.empty() &&
993 "At least one previous predecessor must exist.");
994
995 // TODO: if this becomes a bottleneck, we can save on GetLastDef calls by
996 // keeping this map before the loop. We can reuse already populated entries
997 // if an edge is added from the same predecessor to two different blocks,
998 // and this does happen in rotate. Note that the map needs to be updated
999 // when deleting non-necessary phis below, if the phi is in the map by
1000 // replacing the value with DefP1.
1002 for (auto *AddedPred : AddedBlockSet) {
1003 auto *DefPn = GetLastDef(AddedPred);
1004 assert(DefPn != nullptr && "Unable to find last definition.");
1005 LastDefAddedPred[AddedPred] = DefPn;
1006 }
1007
1008 MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB);
1009 // If Phi is not empty, add an incoming edge from each added pred. Must
1010 // still compute blocks with defs to replace for this block below.
1011 if (NewPhi->getNumOperands()) {
1012 for (auto *Pred : AddedBlockSet) {
1013 auto *LastDefForPred = LastDefAddedPred[Pred];
1014 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
1015 NewPhi->addIncoming(LastDefForPred, Pred);
1016 }
1017 } else {
1018 // Pick any existing predecessor and get its definition. All other
1019 // existing predecessors should have the same one, since no phi existed.
1020 auto *P1 = *PrevBlockSet.begin();
1021 MemoryAccess *DefP1 = GetLastDef(P1);
1022
1023 // Check DefP1 against all Defs in LastDefPredPair. If all the same,
1024 // nothing to add.
1025 bool InsertPhi = false;
1026 for (auto LastDefPredPair : LastDefAddedPred)
1027 if (DefP1 != LastDefPredPair.second) {
1028 InsertPhi = true;
1029 break;
1030 }
1031 if (!InsertPhi) {
1032 // Since NewPhi may be used in other newly added Phis, replace all uses
1033 // of NewPhi with the definition coming from all predecessors (DefP1),
1034 // before deleting it.
1035 NewPhi->replaceAllUsesWith(DefP1);
1036 removeMemoryAccess(NewPhi);
1037 continue;
1038 }
1039
1040 // Update Phi with new values for new predecessors and old value for all
1041 // other predecessors. Since AddedBlockSet and PrevBlockSet are ordered
1042 // sets, the order of entries in NewPhi is deterministic.
1043 for (auto *Pred : AddedBlockSet) {
1044 auto *LastDefForPred = LastDefAddedPred[Pred];
1045 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
1046 NewPhi->addIncoming(LastDefForPred, Pred);
1047 }
1048 for (auto *Pred : PrevBlockSet)
1049 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
1050 NewPhi->addIncoming(DefP1, Pred);
1051 }
1052
1053 // Get all blocks that used to dominate BB and no longer do after adding
1054 // AddedBlockSet, where PrevBlockSet are the previously known predecessors.
1055 assert(DT.getNode(BB)->getIDom() && "BB does not have valid idom");
1056 BasicBlock *PrevIDom = FindNearestCommonDominator(PrevBlockSet);
1057 assert(PrevIDom && "Previous IDom should exists");
1058 BasicBlock *NewIDom = DT.getNode(BB)->getIDom()->getBlock();
1059 assert(NewIDom && "BB should have a new valid idom");
1060 assert(DT.dominates(NewIDom, PrevIDom) &&
1061 "New idom should dominate old idom");
1062 GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);
1063 }
1064
1065 tryRemoveTrivialPhis(InsertedPhis);
1066 // Create the set of blocks that now have a definition. We'll use this to
1067 // compute IDF and add Phis there next.
1068 SmallVector<BasicBlock *, 8> BlocksToProcess;
1069 for (auto &VH : InsertedPhis)
1070 if (auto *MPhi = cast_or_null<MemoryPhi>(VH))
1071 BlocksToProcess.push_back(MPhi->getBlock());
1072
1073 // Compute IDF and add Phis in all IDF blocks that do not have one.
1075 if (!BlocksToProcess.empty()) {
1076 ForwardIDFCalculator IDFs(DT, GD);
1077 SmallPtrSet<BasicBlock *, 16> DefiningBlocks(BlocksToProcess.begin(),
1078 BlocksToProcess.end());
1079 IDFs.setDefiningBlocks(DefiningBlocks);
1080 IDFs.calculate(IDFBlocks);
1081
1083 // First create all needed Phis.
1084 for (auto *BBIDF : IDFBlocks)
1085 if (!MSSA->getMemoryAccess(BBIDF)) {
1086 auto *IDFPhi = MSSA->createMemoryPhi(BBIDF);
1087 InsertedPhis.push_back(IDFPhi);
1088 PhisToFill.insert(IDFPhi);
1089 }
1090 // Then update or insert their correct incoming values.
1091 for (auto *BBIDF : IDFBlocks) {
1092 auto *IDFPhi = MSSA->getMemoryAccess(BBIDF);
1093 assert(IDFPhi && "Phi must exist");
1094 if (!PhisToFill.count(IDFPhi)) {
1095 // Update existing Phi.
1096 // FIXME: some updates may be redundant, try to optimize and skip some.
1097 for (unsigned I = 0, E = IDFPhi->getNumIncomingValues(); I < E; ++I)
1098 IDFPhi->setIncomingValue(I, GetLastDef(IDFPhi->getIncomingBlock(I)));
1099 } else {
1100 for (auto *Pi : GD->template getChildren</*InverseEdge=*/true>(BBIDF))
1101 IDFPhi->addIncoming(GetLastDef(Pi), Pi);
1102 }
1103 }
1104 }
1105
1106 // Now for all defs in BlocksWithDefsToReplace, if there are uses they no
1107 // longer dominate, replace those with the closest dominating def.
1108 // This will also update optimized accesses, as they're also uses.
1109 for (auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) {
1110 if (auto DefsList = MSSA->getWritableBlockDefs(BlockWithDefsToReplace)) {
1111 for (auto &DefToReplaceUses : *DefsList) {
1112 BasicBlock *DominatingBlock = DefToReplaceUses.getBlock();
1113 for (Use &U : llvm::make_early_inc_range(DefToReplaceUses.uses())) {
1114 MemoryAccess *Usr = cast<MemoryAccess>(U.getUser());
1115 if (MemoryPhi *UsrPhi = dyn_cast<MemoryPhi>(Usr)) {
1116 BasicBlock *DominatedBlock = UsrPhi->getIncomingBlock(U);
1117 if (!DT.dominates(DominatingBlock, DominatedBlock))
1118 U.set(GetLastDef(DominatedBlock));
1119 } else {
1120 BasicBlock *DominatedBlock = Usr->getBlock();
1121 if (!DT.dominates(DominatingBlock, DominatedBlock)) {
1122 if (auto *DomBlPhi = MSSA->getMemoryAccess(DominatedBlock))
1123 U.set(DomBlPhi);
1124 else {
1125 auto *IDom = DT.getNode(DominatedBlock)->getIDom();
1126 assert(IDom && "Block must have a valid IDom.");
1127 U.set(GetLastDef(IDom->getBlock()));
1128 }
1129 cast<MemoryUseOrDef>(Usr)->resetOptimized();
1130 }
1131 }
1132 }
1133 }
1134 }
1135 }
1136 tryRemoveTrivialPhis(InsertedPhis);
1137}
1138
1139// Move What before Where in the MemorySSA IR.
1140template <class WhereType>
1141void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
1142 WhereType Where) {
1143 // Mark MemoryPhi users of What not to be optimized.
1144 for (auto *U : What->users())
1145 if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))
1146 NonOptPhis.insert(PhiUser);
1147
1148 // Replace all our users with our defining access.
1150
1151 // Let MemorySSA take care of moving it around in the lists.
1152 MSSA->moveTo(What, BB, Where);
1153
1154 // Now reinsert it into the IR and do whatever fixups needed.
1155 if (auto *MD = dyn_cast<MemoryDef>(What))
1156 insertDef(MD, /*RenameUses=*/true);
1157 else
1158 insertUse(cast<MemoryUse>(What), /*RenameUses=*/true);
1159
1160 // Clear dangling pointers. We added all MemoryPhi users, but not all
1161 // of them are removed by fixupDefs().
1162 NonOptPhis.clear();
1163}
1164
1165// Move What before Where in the MemorySSA IR.
1167 moveTo(What, Where->getBlock(), Where->getIterator());
1168}
1169
1170// Move What after Where in the MemorySSA IR.
1172 moveTo(What, Where->getBlock(), ++Where->getIterator());
1173}
1174
1178 return moveTo(What, BB, Where);
1179
1180 if (auto *Where = MSSA->getMemoryAccess(BB->getTerminator()))
1181 return moveBefore(What, Where);
1182 else
1183 return moveTo(What, BB, MemorySSA::InsertionPlace::End);
1184}
1185
1186// All accesses in To used to be in From. Move to end and update access lists.
1187void MemorySSAUpdater::moveAllAccesses(BasicBlock *From, BasicBlock *To,
1188 Instruction *Start) {
1189
1191 if (!Accs)
1192 return;
1193
1194 assert(Start->getParent() == To && "Incorrect Start instruction");
1195 MemoryAccess *FirstInNew = nullptr;
1196 for (Instruction &I : make_range(Start->getIterator(), To->end()))
1197 if ((FirstInNew = MSSA->getMemoryAccess(&I)))
1198 break;
1199 if (FirstInNew) {
1200 auto *MUD = cast<MemoryUseOrDef>(FirstInNew);
1201 do {
1202 auto NextIt = ++MUD->getIterator();
1203 MemoryUseOrDef *NextMUD = (!Accs || NextIt == Accs->end())
1204 ? nullptr
1205 : cast<MemoryUseOrDef>(&*NextIt);
1206 MSSA->moveTo(MUD, To, MemorySSA::End);
1207 // Moving MUD from Accs in the moveTo above, may delete Accs, so we need
1208 // to retrieve it again.
1209 Accs = MSSA->getWritableBlockAccesses(From);
1210 MUD = NextMUD;
1211 } while (MUD);
1212 }
1213
1214 // If all accesses were moved and only a trivial Phi remains, we try to remove
1215 // that Phi. This is needed when From is going to be deleted.
1216 auto *Defs = MSSA->getWritableBlockDefs(From);
1217 if (Defs && !Defs->empty())
1218 if (auto *Phi = dyn_cast<MemoryPhi>(&*Defs->begin()))
1219 tryRemoveTrivialPhi(Phi);
1220}
1221
1223 BasicBlock *To,
1224 Instruction *Start) {
1225 assert(MSSA->getBlockAccesses(To) == nullptr &&
1226 "To block is expected to be free of MemoryAccesses.");
1227 moveAllAccesses(From, To, Start);
1228 for (BasicBlock *Succ : successors(To))
1229 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
1230 MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
1231}
1232
1234 Instruction *Start) {
1235 assert(From->getUniquePredecessor() == To &&
1236 "From block is expected to have a single predecessor (To).");
1237 moveAllAccesses(From, To, Start);
1238 for (BasicBlock *Succ : successors(From))
1239 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
1240 MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
1241}
1242
1245 bool IdenticalEdgesWereMerged) {
1246 assert(!MSSA->getWritableBlockAccesses(New) &&
1247 "Access list should be null for a new block.");
1248 MemoryPhi *Phi = MSSA->getMemoryAccess(Old);
1249 if (!Phi)
1250 return;
1251 if (Old->hasNPredecessors(1)) {
1252 assert(pred_size(New) == Preds.size() &&
1253 "Should have moved all predecessors.");
1254 MSSA->moveTo(Phi, New, MemorySSA::Beginning);
1255 } else {
1256 assert(!Preds.empty() && "Must be moving at least one predecessor to the "
1257 "new immediate predecessor.");
1258 MemoryPhi *NewPhi = MSSA->createMemoryPhi(New);
1259 SmallPtrSet<BasicBlock *, 16> PredsSet(Preds.begin(), Preds.end());
1260 // Currently only support the case of removing a single incoming edge when
1261 // identical edges were not merged.
1262 if (!IdenticalEdgesWereMerged)
1263 assert(PredsSet.size() == Preds.size() &&
1264 "If identical edges were not merged, we cannot have duplicate "
1265 "blocks in the predecessors");
1266 Phi->unorderedDeleteIncomingIf([&](MemoryAccess *MA, BasicBlock *B) {
1267 if (PredsSet.count(B)) {
1268 NewPhi->addIncoming(MA, B);
1269 if (!IdenticalEdgesWereMerged)
1270 PredsSet.erase(B);
1271 return true;
1272 }
1273 return false;
1274 });
1275 Phi->addIncoming(NewPhi, New);
1276 tryRemoveTrivialPhi(NewPhi);
1277 }
1278}
1279
1281 assert(!MSSA->isLiveOnEntryDef(MA) &&
1282 "Trying to remove the live on entry def");
1283 // We can only delete phi nodes if they have no uses, or we can replace all
1284 // uses with a single definition.
1285 MemoryAccess *NewDefTarget = nullptr;
1286 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
1287 // Note that it is sufficient to know that all edges of the phi node have
1288 // the same argument. If they do, by the definition of dominance frontiers
1289 // (which we used to place this phi), that argument must dominate this phi,
1290 // and thus, must dominate the phi's uses, and so we will not hit the assert
1291 // below.
1292 NewDefTarget = onlySingleValue(MP);
1293 assert((NewDefTarget || MP->use_empty()) &&
1294 "We can't delete this memory phi");
1295 } else {
1296 NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
1297 }
1298
1300
1301 // Re-point the uses at our defining access
1302 if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
1303 // Reset optimized on users of this store, and reset the uses.
1304 // A few notes:
1305 // 1. This is a slightly modified version of RAUW to avoid walking the
1306 // uses twice here.
1307 // 2. If we wanted to be complete, we would have to reset the optimized
1308 // flags on users of phi nodes if doing the below makes a phi node have all
1309 // the same arguments. Instead, we prefer users to removeMemoryAccess those
1310 // phi nodes, because doing it here would be N^3.
1311 if (MA->hasValueHandle())
1312 ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
1313 // Note: We assume MemorySSA is not used in metadata since it's not really
1314 // part of the IR.
1315
1316 assert(NewDefTarget != MA && "Going into an infinite loop");
1317 while (!MA->use_empty()) {
1318 Use &U = *MA->use_begin();
1319 if (auto *MUD = dyn_cast<MemoryUseOrDef>(U.getUser()))
1320 MUD->resetOptimized();
1321 if (OptimizePhis)
1322 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U.getUser()))
1323 PhisToCheck.insert(MP);
1324 U.set(NewDefTarget);
1325 }
1326 }
1327
1328 // The call below to erase will destroy MA, so we can't change the order we
1329 // are doing things here
1330 MSSA->removeFromLookups(MA);
1331 MSSA->removeFromLists(MA);
1332
1333 // Optionally optimize Phi uses. This will recursively remove trivial phis.
1334 if (!PhisToCheck.empty()) {
1335 SmallVector<WeakVH, 16> PhisToOptimize{PhisToCheck.begin(),
1336 PhisToCheck.end()};
1337 PhisToCheck.clear();
1338
1339 unsigned PhisSize = PhisToOptimize.size();
1340 while (PhisSize-- > 0)
1341 if (MemoryPhi *MP =
1342 cast_or_null<MemoryPhi>(PhisToOptimize.pop_back_val()))
1343 tryRemoveTrivialPhi(MP);
1344 }
1345}
1346
1348 const SmallSetVector<BasicBlock *, 8> &DeadBlocks) {
1349 // First delete all uses of BB in MemoryPhis.
1350 for (BasicBlock *BB : DeadBlocks) {
1351 Instruction *TI = BB->getTerminator();
1352 assert(TI && "Basic block expected to have a terminator instruction");
1353 for (BasicBlock *Succ : successors(TI))
1354 if (!DeadBlocks.count(Succ))
1355 if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {
1356 MP->unorderedDeleteIncomingBlock(BB);
1357 tryRemoveTrivialPhi(MP);
1358 }
1359 // Drop all references of all accesses in BB
1361 for (MemoryAccess &MA : *Acc)
1362 MA.dropAllReferences();
1363 }
1364
1365 // Next, delete all memory accesses in each block
1366 for (BasicBlock *BB : DeadBlocks) {
1368 if (!Acc)
1369 continue;
1370 for (MemoryAccess &MA : llvm::make_early_inc_range(*Acc)) {
1371 MSSA->removeFromLookups(&MA);
1372 MSSA->removeFromLists(&MA);
1373 }
1374 }
1375}
1376
1377void MemorySSAUpdater::tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs) {
1378 for (const auto &VH : UpdatedPHIs)
1379 if (auto *MPhi = cast_or_null<MemoryPhi>(VH))
1380 tryRemoveTrivialPhi(MPhi);
1381}
1382
1384 const BasicBlock *BB = I->getParent();
1385 // Remove memory accesses in BB for I and all following instructions.
1386 auto BBI = I->getIterator(), BBE = BB->end();
1387 // FIXME: If this becomes too expensive, iterate until the first instruction
1388 // with a memory access, then iterate over MemoryAccesses.
1389 while (BBI != BBE)
1390 removeMemoryAccess(&*(BBI++));
1391 // Update phis in BB's successors to remove BB.
1392 SmallVector<WeakVH, 16> UpdatedPHIs;
1393 for (const BasicBlock *Successor : successors(BB)) {
1395 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Successor)) {
1396 MPhi->unorderedDeleteIncomingBlock(BB);
1397 UpdatedPHIs.push_back(MPhi);
1398 }
1399 }
1400 // Optimize trivial phis.
1401 tryRemoveTrivialPhis(UpdatedPHIs);
1402}
1403
1405 Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
1407 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1408 MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
1409 return NewAccess;
1410}
1411
1413 Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
1414 assert(I->getParent() == InsertPt->getBlock() &&
1415 "New and old access must be in the same block");
1416 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1417 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1418 InsertPt->getIterator());
1419 return NewAccess;
1420}
1421
1423 Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
1424 assert(I->getParent() == InsertPt->getBlock() &&
1425 "New and old access must be in the same block");
1426 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1427 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1428 ++InsertPt->getIterator());
1429 return NewAccess;
1430}
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
bool End
Definition: ELF_riscv.cpp:480
Rewrite Partial Register Uses
#define I(x, y, z)
Definition: MD5.cpp:58
mir Rename Register Operands
static MemoryAccess * getNewDefiningAccessForClone(MemoryAccess *MA, const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap, MemorySSA *MSSA)
static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB, MemoryAccess *NewDef)
static MemoryAccess * onlySingleValue(MemoryPhi *MP)
If all arguments of a MemoryPHI are defined by the same incoming argument, return that argument.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file implements a set that has insertion order iteration characteristics.
static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI, AAResults &AA)
Definition: Sink.cpp:175
This file defines the SmallPtrSet class.
static const uint32_t IV[8]
Definition: blake3_impl.h:78
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
iterator end() const
Definition: ArrayRef.h:154
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
iterator begin() const
Definition: ArrayRef.h:153
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:160
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator end()
Definition: BasicBlock.h:451
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:438
reverse_iterator rbegin()
Definition: BasicBlock.h:454
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
Definition: BasicBlock.cpp:517
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:503
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:229
This class represents an Operation in the Expression.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:202
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
DomTreeNodeBase * getIDom() const
NodeT * getBlock() const
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const
Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...
Definition: Dominators.cpp:344
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
void calculate(SmallVectorImpl< NodeTy * > &IDFBlocks)
Calculate iterated dominance frontiers.
void setDefiningBlocks(const SmallPtrSetImpl< NodeTy * > &Blocks)
Give the IDF calculator the set of blocks in which the value is defined.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
AllAccessType::reverse_self_iterator getReverseIterator()
Definition: MemorySSA.h:189
DefsOnlyType::self_iterator getDefsIterator()
Definition: MemorySSA.h:195
DefsOnlyType::reverse_self_iterator getReverseDefsIterator()
Definition: MemorySSA.h:201
BasicBlock * getBlock() const
Definition: MemorySSA.h:164
AllAccessType::self_iterator getIterator()
Get the iterators for the all access list and the defs only list We default to the all access list.
Definition: MemorySSA.h:183
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Definition: MemorySSA.h:372
Represents phi nodes for memory accesses.
Definition: MemorySSA.h:479
void setIncomingValue(unsigned I, MemoryAccess *V)
Definition: MemorySSA.h:531
iterator_range< block_iterator > blocks()
Definition: MemorySSA.h:514
void addIncoming(MemoryAccess *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: MemorySSA.h:561
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Definition: MemorySSA.h:572
MemoryUseOrDef * createMemoryAccessBefore(Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt)
Create a MemoryAccess in MemorySSA before an existing MemoryAccess.
void insertDef(MemoryDef *Def, bool RenameUses=false)
Insert a definition into the MemorySSA IR.
void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where)
void removeEdge(BasicBlock *From, BasicBlock *To)
Update the MemoryPhi in To following an edge deletion between From and To.
void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks, ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VM, bool IgnoreIncomingWithNoClones=false)
Update MemorySSA after a loop was cloned, given the blocks in RPO order, the exit blocks and a 1:1 ma...
MemoryAccess * createMemoryAccessInBB(Instruction *I, MemoryAccess *Definition, const BasicBlock *BB, MemorySSA::InsertionPlace Point)
Create a MemoryAccess in MemorySSA at a specified point in a block.
void changeToUnreachable(const Instruction *I)
Instruction I will be changed to an unreachable.
void removeDuplicatePhiEdgesBetween(const BasicBlock *From, const BasicBlock *To)
Update the MemoryPhi in To to have a single incoming edge from From, following a CFG change that repl...
void updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock *LoopHeader, BasicBlock *LoopPreheader, BasicBlock *BackedgeBlock)
Update MemorySSA when inserting a unique backedge block for a loop.
void insertUse(MemoryUse *Use, bool RenameUses=false)
void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)
Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was spliced into From and To.
void removeMemoryAccess(MemoryAccess *, bool OptimizePhis=false)
Remove a MemoryAccess from MemorySSA, including updating all definitions and uses.
void applyInsertUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT)
Apply CFG insert updates, analogous with the DT edge updates.
MemoryUseOrDef * createMemoryAccessAfter(Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt)
Create a MemoryAccess in MemorySSA after an existing MemoryAccess.
void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM)
void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)
Apply CFG updates, analogous with the DT edge updates.
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To, Instruction *Start)
From block was merged into To.
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB, MemorySSA::InsertionPlace Where)
void wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New, ArrayRef< BasicBlock * > Preds, bool IdenticalEdgesWereMerged=true)
A new empty BasicBlock (New) now branches directly to Old.
void updateExitBlocksForClonedLoop(ArrayRef< BasicBlock * > ExitBlocks, const ValueToValueMapTy &VMap, DominatorTree &DT)
Update phi nodes in exit block successors following cloning.
void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where)
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:700
void moveTo(MemoryUseOrDef *What, BasicBlock *BB, AccessList::iterator Where)
Definition: MemorySSA.cpp:1651
const AccessList * getBlockAccesses(const BasicBlock *BB) const
Return the list of MemoryAccess's for a given basic block.
Definition: MemorySSA.h:757
void renamePass(BasicBlock *BB, MemoryAccess *IncomingVal, SmallPtrSetImpl< BasicBlock * > &Visited)
Definition: MemorySSA.h:828
bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
Definition: MemorySSA.cpp:2109
AccessList * getWritableBlockAccesses(const BasicBlock *BB) const
Definition: MemorySSA.h:809
void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *, InsertionPlace)
Definition: MemorySSA.cpp:1575
InsertionPlace
Used in various insertion functions to specify whether we are talking about the beginning or end of a...
Definition: MemorySSA.h:788
void insertIntoListsBefore(MemoryAccess *, const BasicBlock *, AccessList::iterator)
Definition: MemorySSA.cpp:1607
MemoryUseOrDef * createDefinedAccess(Instruction *, MemoryAccess *, const MemoryUseOrDef *Template=nullptr, bool CreationMustSucceed=true)
Definition: MemorySSA.cpp:1682
DefsList * getWritableBlockDefs(const BasicBlock *BB) const
Definition: MemorySSA.h:815
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
Definition: MemorySSA.h:717
MemoryAccess * getLiveOnEntryDef() const
Definition: MemorySSA.h:741
void removeFromLookups(MemoryAccess *)
Properly remove MA from all of MemorySSA's lookup tables.
Definition: MemorySSA.cpp:1794
const DefsList * getBlockDefs(const BasicBlock *BB) const
Return the list of MemoryDef's and MemoryPhi's for a given basic block.
Definition: MemorySSA.h:765
void removeFromLists(MemoryAccess *, bool ShouldDelete=true)
Properly remove MA from all of MemorySSA's lists.
Definition: MemorySSA.cpp:1821
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
Definition: MemorySSA.h:737
Class that has the common methods + fields of memory uses/defs.
Definition: MemorySSA.h:252
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Definition: MemorySSA.h:262
void setDefiningAccess(MemoryAccess *DMA, bool Optimized=false)
Definition: MemorySSA.h:295
Represents read-only accesses to memory.
Definition: MemorySSA.h:312
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:113
void clear()
Completely clear the SetVector.
Definition: SetVector.h:273
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:264
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:93
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:103
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
size_type size() const
Definition: SmallPtrSet.h:94
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:179
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:696
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Value handle that tracks a Value across RAUW.
Definition: ValueHandle.h:331
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_range operands()
Definition: User.h:242
void dropAllReferences()
Drop all references to operands.
Definition: User.h:299
unsigned getNumOperands() const
Definition: User.h:191
static void ValueIsRAUWd(Value *Old, Value *New)
Definition: Value.cpp:1254
ValueT lookup(const KeyT &Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: ValueMap.h:164
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:534
iterator_range< user_iterator > users()
Definition: Value.h:421
use_iterator use_begin()
Definition: Value.h:360
void replaceUsesWithIf(Value *New, llvm::function_ref< bool(Use &U)> ShouldReplace)
Go through the uses list for this definition and make each use point to "V" if the callback ShouldRep...
Definition: Value.cpp:542
bool use_empty() const
Definition: Value.h:344
bool hasValueHandle() const
Return true if there is a value handle associated with this value.
Definition: Value.h:554
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:328
A simple intrusive list implementation.
Definition: simple_ilist.h:81
iterator insert(iterator I, reference Node)
Insert a node by reference; never copies.
Definition: simple_ilist.h:165
bool empty() const
Check if the list is empty in constant time.
Definition: simple_ilist.h:139
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
NodeAddr< PhiNode * > Phi
Definition: RDFGraph.h:390
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:329
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:665
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1833
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1888
unsigned pred_size(const MachineBasicBlock *BB)