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 //===----------------------------------------------------------------===//
12 #include "llvm/Analysis/MemorySSAUpdater.h"
13 #include "llvm/Analysis/LoopIterator.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/ADT/SetVector.h"
16 #include "llvm/ADT/SmallPtrSet.h"
17 #include "llvm/Analysis/IteratedDominanceFrontier.h"
18 #include "llvm/Analysis/MemorySSA.h"
19 #include "llvm/IR/BasicBlock.h"
20 #include "llvm/IR/DataLayout.h"
21 #include "llvm/IR/Dominators.h"
22 #include "llvm/IR/GlobalVariable.h"
23 #include "llvm/IR/IRBuilder.h"
24 #include "llvm/IR/LLVMContext.h"
25 #include "llvm/IR/Metadata.h"
26 #include "llvm/IR/Module.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Support/FormattedStream.h"
29 #include <algorithm>
30
31 #define DEBUG_TYPE "memoryssa"
32 using namespace llvm;
33
34 // This is the marker algorithm from "Simple and Efficient Construction of
35 // Static Single Assignment Form"
36 // The simple, non-marker algorithm places phi nodes at any join
37 // Here, we place markers, and only place phi nodes if they end up necessary.
38 // They are only necessary if they break a cycle (IE we recursively visit
39 // ourselves again), or we discover, while getting the value of the operands,
40 // that there are two or more definitions needing to be merged.
41 // This still will leave non-minimal form in the case of irreducible control
42 // flow, where phi nodes may be in cycles with themselves, but unnecessary.
getPreviousDefRecursive(BasicBlock * BB,DenseMap<BasicBlock *,TrackingVH<MemoryAccess>> & CachedPreviousDef)43 MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(
44 BasicBlock *BB,
45 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
46 // First, do a cache lookup. Without this cache, certain CFG structures
47 // (like a series of if statements) take exponential time to visit.
48 auto Cached = CachedPreviousDef.find(BB);
49 if (Cached != CachedPreviousDef.end())
50 return Cached->second;
51
52 // If this method is called from an unreachable block, return LoE.
53 if (!MSSA->DT->isReachableFromEntry(BB))
54 return MSSA->getLiveOnEntryDef();
55
56 if (BasicBlock *Pred = BB->getUniquePredecessor()) {
57 VisitedBlocks.insert(BB);
58 // Single predecessor case, just recurse, we can only have one definition.
59 MemoryAccess *Result = getPreviousDefFromEnd(Pred, CachedPreviousDef);
60 CachedPreviousDef.insert({BB, Result});
61 return Result;
62 }
63
64 if (VisitedBlocks.count(BB)) {
65 // We hit our node again, meaning we had a cycle, we must insert a phi
66 // node to break it so we have an operand. The only case this will
67 // insert useless phis is if we have irreducible control flow.
68 MemoryAccess *Result = MSSA->createMemoryPhi(BB);
69 CachedPreviousDef.insert({BB, Result});
70 return Result;
71 }
72
73 if (VisitedBlocks.insert(BB).second) {
74 // Mark us visited so we can detect a cycle
75 SmallVector<TrackingVH<MemoryAccess>, 8> PhiOps;
76
77 // Recurse to get the values in our predecessors for placement of a
78 // potential phi node. This will insert phi nodes if we cycle in order to
79 // break the cycle and have an operand.
80 bool UniqueIncomingAccess = true;
81 MemoryAccess *SingleAccess = nullptr;
82 for (auto *Pred : predecessors(BB)) {
83 if (MSSA->DT->isReachableFromEntry(Pred)) {
84 auto *IncomingAccess = getPreviousDefFromEnd(Pred, CachedPreviousDef);
85 if (!SingleAccess)
86 SingleAccess = IncomingAccess;
87 else if (IncomingAccess != SingleAccess)
88 UniqueIncomingAccess = false;
89 PhiOps.push_back(IncomingAccess);
90 } else
91 PhiOps.push_back(MSSA->getLiveOnEntryDef());
92 }
93
94 // Now try to simplify the ops to avoid placing a phi.
95 // This may return null if we never created a phi yet, that's okay
96 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));
97
98 // See if we can avoid the phi by simplifying it.
99 auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
100 // If we couldn't simplify, we may have to create a phi
101 if (Result == Phi && UniqueIncomingAccess && SingleAccess) {
102 // A concrete Phi only exists if we created an empty one to break a cycle.
103 if (Phi) {
104 assert(Phi->operands().empty() && "Expected empty Phi");
105 Phi->replaceAllUsesWith(SingleAccess);
106 removeMemoryAccess(Phi);
107 }
108 Result = SingleAccess;
109 } else if (Result == Phi && !(UniqueIncomingAccess && SingleAccess)) {
110 if (!Phi)
111 Phi = MSSA->createMemoryPhi(BB);
112
113 // See if the existing phi operands match what we need.
114 // Unlike normal SSA, we only allow one phi node per block, so we can't just
115 // create a new one.
116 if (Phi->getNumOperands() != 0) {
117 // FIXME: Figure out whether this is dead code and if so remove it.
118 if (!std::equal(Phi->op_begin(), Phi->op_end(), PhiOps.begin())) {
119 // These will have been filled in by the recursive read we did above.
120 llvm::copy(PhiOps, Phi->op_begin());
121 std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
122 }
123 } else {
124 unsigned i = 0;
125 for (auto *Pred : predecessors(BB))
126 Phi->addIncoming(&*PhiOps[i++], Pred);
127 InsertedPHIs.push_back(Phi);
128 }
129 Result = Phi;
130 }
131
132 // Set ourselves up for the next variable by resetting visited state.
133 VisitedBlocks.erase(BB);
134 CachedPreviousDef.insert({BB, Result});
135 return Result;
136 }
137 llvm_unreachable("Should have hit one of the three cases above");
138 }
139
140 // This starts at the memory access, and goes backwards in the block to find the
141 // previous definition. If a definition is not found the block of the access,
142 // it continues globally, creating phi nodes to ensure we have a single
143 // definition.
getPreviousDef(MemoryAccess * MA)144 MemoryAccess *MemorySSAUpdater::getPreviousDef(MemoryAccess *MA) {
145 if (auto *LocalResult = getPreviousDefInBlock(MA))
146 return LocalResult;
147 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
148 return getPreviousDefRecursive(MA->getBlock(), CachedPreviousDef);
149 }
150
151 // This starts at the memory access, and goes backwards in the block to the find
152 // the previous definition. If the definition is not found in the block of the
153 // access, it returns nullptr.
getPreviousDefInBlock(MemoryAccess * MA)154 MemoryAccess *MemorySSAUpdater::getPreviousDefInBlock(MemoryAccess *MA) {
155 auto *Defs = MSSA->getWritableBlockDefs(MA->getBlock());
156
157 // It's possible there are no defs, or we got handed the first def to start.
158 if (Defs) {
159 // If this is a def, we can just use the def iterators.
160 if (!isa<MemoryUse>(MA)) {
161 auto Iter = MA->getReverseDefsIterator();
162 ++Iter;
163 if (Iter != Defs->rend())
164 return &*Iter;
165 } else {
166 // Otherwise, have to walk the all access iterator.
167 auto End = MSSA->getWritableBlockAccesses(MA->getBlock())->rend();
168 for (auto &U : make_range(++MA->getReverseIterator(), End))
169 if (!isa<MemoryUse>(U))
170 return cast<MemoryAccess>(&U);
171 // Note that if MA comes before Defs->begin(), we won't hit a def.
172 return nullptr;
173 }
174 }
175 return nullptr;
176 }
177
178 // This starts at the end of block
getPreviousDefFromEnd(BasicBlock * BB,DenseMap<BasicBlock *,TrackingVH<MemoryAccess>> & CachedPreviousDef)179 MemoryAccess *MemorySSAUpdater::getPreviousDefFromEnd(
180 BasicBlock *BB,
181 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
182 auto *Defs = MSSA->getWritableBlockDefs(BB);
183
184 if (Defs) {
185 CachedPreviousDef.insert({BB, &*Defs->rbegin()});
186 return &*Defs->rbegin();
187 }
188
189 return getPreviousDefRecursive(BB, CachedPreviousDef);
190 }
191 // Recurse over a set of phi uses to eliminate the trivial ones
recursePhi(MemoryAccess * Phi)192 MemoryAccess *MemorySSAUpdater::recursePhi(MemoryAccess *Phi) {
193 if (!Phi)
194 return nullptr;
195 TrackingVH<MemoryAccess> Res(Phi);
196 SmallVector<TrackingVH<Value>, 8> Uses;
197 std::copy(Phi->user_begin(), Phi->user_end(), std::back_inserter(Uses));
198 for (auto &U : Uses)
199 if (MemoryPhi *UsePhi = dyn_cast<MemoryPhi>(&*U))
200 tryRemoveTrivialPhi(UsePhi);
201 return Res;
202 }
203
204 // Eliminate trivial phis
205 // Phis are trivial if they are defined either by themselves, or all the same
206 // argument.
207 // IE phi(a, a) or b = phi(a, b) or c = phi(a, a, c)
208 // We recursively try to remove them.
tryRemoveTrivialPhi(MemoryPhi * Phi)209 MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi) {
210 assert(Phi && "Can only remove concrete Phi.");
211 auto OperRange = Phi->operands();
212 return tryRemoveTrivialPhi(Phi, OperRange);
213 }
214 template <class RangeType>
tryRemoveTrivialPhi(MemoryPhi * Phi,RangeType & Operands)215 MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
216 RangeType &Operands) {
217 // Bail out on non-opt Phis.
218 if (NonOptPhis.count(Phi))
219 return Phi;
220
221 // Detect equal or self arguments
222 MemoryAccess *Same = nullptr;
223 for (auto &Op : Operands) {
224 // If the same or self, good so far
225 if (Op == Phi || Op == Same)
226 continue;
227 // not the same, return the phi since it's not eliminatable by us
228 if (Same)
229 return Phi;
230 Same = cast<MemoryAccess>(&*Op);
231 }
232 // Never found a non-self reference, the phi is undef
233 if (Same == nullptr)
234 return MSSA->getLiveOnEntryDef();
235 if (Phi) {
236 Phi->replaceAllUsesWith(Same);
237 removeMemoryAccess(Phi);
238 }
239
240 // We should only end up recursing in case we replaced something, in which
241 // case, we may have made other Phis trivial.
242 return recursePhi(Same);
243 }
244
insertUse(MemoryUse * MU,bool RenameUses)245 void MemorySSAUpdater::insertUse(MemoryUse *MU, bool RenameUses) {
246 InsertedPHIs.clear();
247 MU->setDefiningAccess(getPreviousDef(MU));
248
249 // In cases without unreachable blocks, because uses do not create new
250 // may-defs, there are only two cases:
251 // 1. There was a def already below us, and therefore, we should not have
252 // created a phi node because it was already needed for the def.
253 //
254 // 2. There is no def below us, and therefore, there is no extra renaming work
255 // to do.
256
257 // In cases with unreachable blocks, where the unnecessary Phis were
258 // optimized out, adding the Use may re-insert those Phis. Hence, when
259 // inserting Uses outside of the MSSA creation process, and new Phis were
260 // added, rename all uses if we are asked.
261
262 if (!RenameUses && !InsertedPHIs.empty()) {
263 auto *Defs = MSSA->getBlockDefs(MU->getBlock());
264 (void)Defs;
265 assert((!Defs || (++Defs->begin() == Defs->end())) &&
266 "Block may have only a Phi or no defs");
267 }
268
269 if (RenameUses && InsertedPHIs.size()) {
270 SmallPtrSet<BasicBlock *, 16> Visited;
271 BasicBlock *StartBlock = MU->getBlock();
272
273 if (auto *Defs = MSSA->getWritableBlockDefs(StartBlock)) {
274 MemoryAccess *FirstDef = &*Defs->begin();
275 // Convert to incoming value if it's a memorydef. A phi *is* already an
276 // incoming value.
277 if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
278 FirstDef = MD->getDefiningAccess();
279
280 MSSA->renamePass(MU->getBlock(), FirstDef, Visited);
281 }
282 // We just inserted a phi into this block, so the incoming value will
283 // become the phi anyway, so it does not matter what we pass.
284 for (auto &MP : InsertedPHIs)
285 if (MemoryPhi *Phi = cast_or_null<MemoryPhi>(MP))
286 MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
287 }
288 }
289
290 // Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
setMemoryPhiValueForBlock(MemoryPhi * MP,const BasicBlock * BB,MemoryAccess * NewDef)291 static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
292 MemoryAccess *NewDef) {
293 // Replace any operand with us an incoming block with the new defining
294 // access.
295 int i = MP->getBasicBlockIndex(BB);
296 assert(i != -1 && "Should have found the basic block in the phi");
297 // We can't just compare i against getNumOperands since one is signed and the
298 // other not. So use it to index into the block iterator.
299 for (auto BBIter = MP->block_begin() + i; BBIter != MP->block_end();
300 ++BBIter) {
301 if (*BBIter != BB)
302 break;
303 MP->setIncomingValue(i, NewDef);
304 ++i;
305 }
306 }
307
308 // A brief description of the algorithm:
309 // First, we compute what should define the new def, using the SSA
310 // construction algorithm.
311 // Then, we update the defs below us (and any new phi nodes) in the graph to
312 // point to the correct new defs, to ensure we only have one variable, and no
313 // disconnected stores.
insertDef(MemoryDef * MD,bool RenameUses)314 void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
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 std::find(InsertedPHIs.begin(), InsertedPHIs.end(), DefBefore) !=
323 InsertedPHIs.end()))
324 DefBeforeSameBlock = true;
325
326 // There is a def before us, which means we can replace any store/phi uses
327 // of that thing with us, since we are in the way of whatever was there
328 // before.
329 // We now define that def's memorydefs and memoryphis
330 if (DefBeforeSameBlock) {
331 DefBefore->replaceUsesWithIf(MD, [MD](Use &U) {
332 // Leave the MemoryUses alone.
333 // Also make sure we skip ourselves to avoid self references.
334 User *Usr = U.getUser();
335 return !isa<MemoryUse>(Usr) && Usr != MD;
336 // Defs are automatically unoptimized when the user is set to MD below,
337 // because the isOptimized() call will fail to find the same ID.
338 });
339 }
340
341 // and that def is now our defining access.
342 MD->setDefiningAccess(DefBefore);
343
344 SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());
345
346 // Remember the index where we may insert new phis.
347 unsigned NewPhiIndex = InsertedPHIs.size();
348 if (!DefBeforeSameBlock) {
349 // If there was a local def before us, we must have the same effect it
350 // did. Because every may-def is the same, any phis/etc we would create, it
351 // would also have created. If there was no local def before us, we
352 // performed a global update, and have to search all successors and make
353 // sure we update the first def in each of them (following all paths until
354 // we hit the first def along each path). This may also insert phi nodes.
355 // TODO: There are other cases we can skip this work, such as when we have a
356 // single successor, and only used a straight line of single pred blocks
357 // backwards to find the def. To make that work, we'd have to track whether
358 // getDefRecursive only ever used the single predecessor case. These types
359 // of paths also only exist in between CFG simplifications.
360
361 // If this is the first def in the block and this insert is in an arbitrary
362 // place, compute IDF and place phis.
363 SmallPtrSet<BasicBlock *, 2> DefiningBlocks;
364
365 // If this is the last Def in the block, also compute IDF based on MD, since
366 // this may a new Def added, and we may need additional Phis.
367 auto Iter = MD->getDefsIterator();
368 ++Iter;
369 auto IterEnd = MSSA->getBlockDefs(MD->getBlock())->end();
370 if (Iter == IterEnd)
371 DefiningBlocks.insert(MD->getBlock());
372
373 for (const auto &VH : InsertedPHIs)
374 if (const auto *RealPHI = cast_or_null<MemoryPhi>(VH))
375 DefiningBlocks.insert(RealPHI->getBlock());
376 ForwardIDFCalculator IDFs(*MSSA->DT);
377 SmallVector<BasicBlock *, 32> IDFBlocks;
378 IDFs.setDefiningBlocks(DefiningBlocks);
379 IDFs.calculate(IDFBlocks);
380 SmallVector<AssertingVH<MemoryPhi>, 4> NewInsertedPHIs;
381 for (auto *BBIDF : IDFBlocks) {
382 auto *MPhi = MSSA->getMemoryAccess(BBIDF);
383 if (!MPhi) {
384 MPhi = MSSA->createMemoryPhi(BBIDF);
385 NewInsertedPHIs.push_back(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)) {
398 DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
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.
432 if (RenameUses) {
433 SmallPtrSet<BasicBlock *, 16> Visited;
434 BasicBlock *StartBlock = MD->getBlock();
435 // We are guaranteed there is a def in the block, because we just got it
436 // handed to us in this function.
437 MemoryAccess *FirstDef = &*MSSA->getWritableBlockDefs(StartBlock)->begin();
438 // Convert to incoming value if it's a memorydef. A phi *is* already an
439 // incoming value.
440 if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
441 FirstDef = MD->getDefiningAccess();
442
443 MSSA->renamePass(MD->getBlock(), FirstDef, Visited);
444 // We just inserted a phi into this block, so the incoming value will become
445 // the phi anyway, so it does not matter what we pass.
446 for (auto &MP : InsertedPHIs) {
447 MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);
448 if (Phi)
449 MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
450 }
451 }
452 }
453
fixupDefs(const SmallVectorImpl<WeakVH> & Vars)454 void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<WeakVH> &Vars) {
455 SmallPtrSet<const BasicBlock *, 8> Seen;
456 SmallVector<const BasicBlock *, 16> Worklist;
457 for (auto &Var : Vars) {
458 MemoryAccess *NewDef = dyn_cast_or_null<MemoryAccess>(Var);
459 if (!NewDef)
460 continue;
461 // First, see if there is a local def after the operand.
462 auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
463 auto DefIter = NewDef->getDefsIterator();
464
465 // The temporary Phi is being fixed, unmark it for not to optimize.
466 if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(NewDef))
467 NonOptPhis.erase(Phi);
468
469 // If there is a local def after us, we only have to rename that.
470 if (++DefIter != Defs->end()) {
471 cast<MemoryDef>(DefIter)->setDefiningAccess(NewDef);
472 continue;
473 }
474
475 // Otherwise, we need to search down through the CFG.
476 // For each of our successors, handle it directly if their is a phi, or
477 // place on the fixup worklist.
478 for (const auto *S : successors(NewDef->getBlock())) {
479 if (auto *MP = MSSA->getMemoryAccess(S))
480 setMemoryPhiValueForBlock(MP, NewDef->getBlock(), NewDef);
481 else
482 Worklist.push_back(S);
483 }
484
485 while (!Worklist.empty()) {
486 const BasicBlock *FixupBlock = Worklist.back();
487 Worklist.pop_back();
488
489 // Get the first def in the block that isn't a phi node.
490 if (auto *Defs = MSSA->getWritableBlockDefs(FixupBlock)) {
491 auto *FirstDef = &*Defs->begin();
492 // The loop above and below should have taken care of phi nodes
493 assert(!isa<MemoryPhi>(FirstDef) &&
494 "Should have already handled phi nodes!");
495 // We are now this def's defining access, make sure we actually dominate
496 // it
497 assert(MSSA->dominates(NewDef, FirstDef) &&
498 "Should have dominated the new access");
499
500 // This may insert new phi nodes, because we are not guaranteed the
501 // block we are processing has a single pred, and depending where the
502 // store was inserted, it may require phi nodes below it.
503 cast<MemoryDef>(FirstDef)->setDefiningAccess(getPreviousDef(FirstDef));
504 return;
505 }
506 // We didn't find a def, so we must continue.
507 for (const auto *S : successors(FixupBlock)) {
508 // If there is a phi node, handle it.
509 // Otherwise, put the block on the worklist
510 if (auto *MP = MSSA->getMemoryAccess(S))
511 setMemoryPhiValueForBlock(MP, FixupBlock, NewDef);
512 else {
513 // If we cycle, we should have ended up at a phi node that we already
514 // processed. FIXME: Double check this
515 if (!Seen.insert(S).second)
516 continue;
517 Worklist.push_back(S);
518 }
519 }
520 }
521 }
522 }
523
removeEdge(BasicBlock * From,BasicBlock * To)524 void MemorySSAUpdater::removeEdge(BasicBlock *From, BasicBlock *To) {
525 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
526 MPhi->unorderedDeleteIncomingBlock(From);
527 tryRemoveTrivialPhi(MPhi);
528 }
529 }
530
removeDuplicatePhiEdgesBetween(const BasicBlock * From,const BasicBlock * To)531 void MemorySSAUpdater::removeDuplicatePhiEdgesBetween(const BasicBlock *From,
532 const BasicBlock *To) {
533 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
534 bool Found = false;
535 MPhi->unorderedDeleteIncomingIf([&](const MemoryAccess *, BasicBlock *B) {
536 if (From != B)
537 return false;
538 if (Found)
539 return true;
540 Found = true;
541 return false;
542 });
543 tryRemoveTrivialPhi(MPhi);
544 }
545 }
546
getNewDefiningAccessForClone(MemoryAccess * MA,const ValueToValueMapTy & VMap,PhiToDefMap & MPhiMap,bool CloneWasSimplified,MemorySSA * MSSA)547 static MemoryAccess *getNewDefiningAccessForClone(MemoryAccess *MA,
548 const ValueToValueMapTy &VMap,
549 PhiToDefMap &MPhiMap,
550 bool CloneWasSimplified,
551 MemorySSA *MSSA) {
552 MemoryAccess *InsnDefining = MA;
553 if (MemoryDef *DefMUD = dyn_cast<MemoryDef>(InsnDefining)) {
554 if (!MSSA->isLiveOnEntryDef(DefMUD)) {
555 Instruction *DefMUDI = DefMUD->getMemoryInst();
556 assert(DefMUDI && "Found MemoryUseOrDef with no Instruction.");
557 if (Instruction *NewDefMUDI =
558 cast_or_null<Instruction>(VMap.lookup(DefMUDI))) {
559 InsnDefining = MSSA->getMemoryAccess(NewDefMUDI);
560 if (!CloneWasSimplified)
561 assert(InsnDefining && "Defining instruction cannot be nullptr.");
562 else if (!InsnDefining || isa<MemoryUse>(InsnDefining)) {
563 // The clone was simplified, it's no longer a MemoryDef, look up.
564 auto DefIt = DefMUD->getDefsIterator();
565 // Since simplified clones only occur in single block cloning, a
566 // previous definition must exist, otherwise NewDefMUDI would not
567 // have been found in VMap.
568 assert(DefIt != MSSA->getBlockDefs(DefMUD->getBlock())->begin() &&
569 "Previous def must exist");
570 InsnDefining = getNewDefiningAccessForClone(
571 &*(--DefIt), VMap, MPhiMap, CloneWasSimplified, MSSA);
572 }
573 }
574 }
575 } else {
576 MemoryPhi *DefPhi = cast<MemoryPhi>(InsnDefining);
577 if (MemoryAccess *NewDefPhi = MPhiMap.lookup(DefPhi))
578 InsnDefining = NewDefPhi;
579 }
580 assert(InsnDefining && "Defining instruction cannot be nullptr.");
581 return InsnDefining;
582 }
583
cloneUsesAndDefs(BasicBlock * BB,BasicBlock * NewBB,const ValueToValueMapTy & VMap,PhiToDefMap & MPhiMap,bool CloneWasSimplified)584 void MemorySSAUpdater::cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
585 const ValueToValueMapTy &VMap,
586 PhiToDefMap &MPhiMap,
587 bool CloneWasSimplified) {
588 const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
589 if (!Acc)
590 return;
591 for (const MemoryAccess &MA : *Acc) {
592 if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&MA)) {
593 Instruction *Insn = MUD->getMemoryInst();
594 // Entry does not exist if the clone of the block did not clone all
595 // instructions. This occurs in LoopRotate when cloning instructions
596 // from the old header to the old preheader. The cloned instruction may
597 // also be a simplified Value, not an Instruction (see LoopRotate).
598 // Also in LoopRotate, even when it's an instruction, due to it being
599 // simplified, it may be a Use rather than a Def, so we cannot use MUD as
600 // template. Calls coming from updateForClonedBlockIntoPred, ensure this.
601 if (Instruction *NewInsn =
602 dyn_cast_or_null<Instruction>(VMap.lookup(Insn))) {
603 MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(
604 NewInsn,
605 getNewDefiningAccessForClone(MUD->getDefiningAccess(), VMap,
606 MPhiMap, CloneWasSimplified, MSSA),
607 /*Template=*/CloneWasSimplified ? nullptr : MUD,
608 /*CreationMustSucceed=*/CloneWasSimplified ? false : true);
609 if (NewUseOrDef)
610 MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
611 }
612 }
613 }
614 }
615
updatePhisWhenInsertingUniqueBackedgeBlock(BasicBlock * Header,BasicBlock * Preheader,BasicBlock * BEBlock)616 void MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock(
617 BasicBlock *Header, BasicBlock *Preheader, BasicBlock *BEBlock) {
618 auto *MPhi = MSSA->getMemoryAccess(Header);
619 if (!MPhi)
620 return;
621
622 // Create phi node in the backedge block and populate it with the same
623 // incoming values as MPhi. Skip incoming values coming from Preheader.
624 auto *NewMPhi = MSSA->createMemoryPhi(BEBlock);
625 bool HasUniqueIncomingValue = true;
626 MemoryAccess *UniqueValue = nullptr;
627 for (unsigned I = 0, E = MPhi->getNumIncomingValues(); I != E; ++I) {
628 BasicBlock *IBB = MPhi->getIncomingBlock(I);
629 MemoryAccess *IV = MPhi->getIncomingValue(I);
630 if (IBB != Preheader) {
631 NewMPhi->addIncoming(IV, IBB);
632 if (HasUniqueIncomingValue) {
633 if (!UniqueValue)
634 UniqueValue = IV;
635 else if (UniqueValue != IV)
636 HasUniqueIncomingValue = false;
637 }
638 }
639 }
640
641 // Update incoming edges into MPhi. Remove all but the incoming edge from
642 // Preheader. Add an edge from NewMPhi
643 auto *AccFromPreheader = MPhi->getIncomingValueForBlock(Preheader);
644 MPhi->setIncomingValue(0, AccFromPreheader);
645 MPhi->setIncomingBlock(0, Preheader);
646 for (unsigned I = MPhi->getNumIncomingValues() - 1; I >= 1; --I)
647 MPhi->unorderedDeleteIncoming(I);
648 MPhi->addIncoming(NewMPhi, BEBlock);
649
650 // If NewMPhi is a trivial phi, remove it. Its use in the header MPhi will be
651 // replaced with the unique value.
652 tryRemoveTrivialPhi(NewMPhi);
653 }
654
updateForClonedLoop(const LoopBlocksRPO & LoopBlocks,ArrayRef<BasicBlock * > ExitBlocks,const ValueToValueMapTy & VMap,bool IgnoreIncomingWithNoClones)655 void MemorySSAUpdater::updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
656 ArrayRef<BasicBlock *> ExitBlocks,
657 const ValueToValueMapTy &VMap,
658 bool IgnoreIncomingWithNoClones) {
659 PhiToDefMap MPhiMap;
660
661 auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) {
662 assert(Phi && NewPhi && "Invalid Phi nodes.");
663 BasicBlock *NewPhiBB = NewPhi->getBlock();
664 SmallPtrSet<BasicBlock *, 4> NewPhiBBPreds(pred_begin(NewPhiBB),
665 pred_end(NewPhiBB));
666 for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; ++It) {
667 MemoryAccess *IncomingAccess = Phi->getIncomingValue(It);
668 BasicBlock *IncBB = Phi->getIncomingBlock(It);
669
670 if (BasicBlock *NewIncBB = cast_or_null<BasicBlock>(VMap.lookup(IncBB)))
671 IncBB = NewIncBB;
672 else if (IgnoreIncomingWithNoClones)
673 continue;
674
675 // Now we have IncBB, and will need to add incoming from it to NewPhi.
676
677 // If IncBB is not a predecessor of NewPhiBB, then do not add it.
678 // NewPhiBB was cloned without that edge.
679 if (!NewPhiBBPreds.count(IncBB))
680 continue;
681
682 // Determine incoming value and add it as incoming from IncBB.
683 if (MemoryUseOrDef *IncMUD = dyn_cast<MemoryUseOrDef>(IncomingAccess)) {
684 if (!MSSA->isLiveOnEntryDef(IncMUD)) {
685 Instruction *IncI = IncMUD->getMemoryInst();
686 assert(IncI && "Found MemoryUseOrDef with no Instruction.");
687 if (Instruction *NewIncI =
688 cast_or_null<Instruction>(VMap.lookup(IncI))) {
689 IncMUD = MSSA->getMemoryAccess(NewIncI);
690 assert(IncMUD &&
691 "MemoryUseOrDef cannot be null, all preds processed.");
692 }
693 }
694 NewPhi->addIncoming(IncMUD, IncBB);
695 } else {
696 MemoryPhi *IncPhi = cast<MemoryPhi>(IncomingAccess);
697 if (MemoryAccess *NewDefPhi = MPhiMap.lookup(IncPhi))
698 NewPhi->addIncoming(NewDefPhi, IncBB);
699 else
700 NewPhi->addIncoming(IncPhi, IncBB);
701 }
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
updateForClonedBlockIntoPred(BasicBlock * BB,BasicBlock * P1,const ValueToValueMapTy & VM)731 void MemorySSAUpdater::updateForClonedBlockIntoPred(
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
747 template <typename Iter>
privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock * > ExitBlocks,Iter ValuesBegin,Iter ValuesEnd,DominatorTree & DT)748 void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop(
749 ArrayRef<BasicBlock *> ExitBlocks, Iter ValuesBegin, Iter ValuesEnd,
750 DominatorTree &DT) {
751 SmallVector<CFGUpdate, 4> Updates;
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
updateExitBlocksForClonedLoop(ArrayRef<BasicBlock * > ExitBlocks,const ValueToValueMapTy & VMap,DominatorTree & DT)762 void MemorySSAUpdater::updateExitBlocksForClonedLoop(
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
updateExitBlocksForClonedLoop(ArrayRef<BasicBlock * > ExitBlocks,ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps,DominatorTree & DT)770 void MemorySSAUpdater::updateExitBlocksForClonedLoop(
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 =
777 mapped_iterator<const std::unique_ptr<ValueToValueMapTy> *,
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
applyUpdates(ArrayRef<CFGUpdate> Updates,DominatorTree & DT)784 void MemorySSAUpdater::applyUpdates(ArrayRef<CFGUpdate> Updates,
785 DominatorTree &DT) {
786 SmallVector<CFGUpdate, 4> DeleteUpdates;
787 SmallVector<CFGUpdate, 4> InsertUpdates;
788 for (auto &Update : Updates) {
789 if (Update.getKind() == DT.Insert)
790 InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
791 else
792 DeleteUpdates.push_back({DT.Delete, Update.getFrom(), Update.getTo()});
793 }
794
795 if (!DeleteUpdates.empty()) {
796 // Update for inserted edges: use newDT and snapshot CFG as if deletes had
797 // not occurred.
798 // FIXME: This creates a new DT, so it's more expensive to do mix
799 // delete/inserts vs just inserts. We can do an incremental update on the DT
800 // to revert deletes, than re-delete the edges. Teaching DT to do this, is
801 // part of a pending cleanup.
802 DominatorTree NewDT(DT, DeleteUpdates);
803 GraphDiff<BasicBlock *> GD(DeleteUpdates, /*ReverseApplyUpdates=*/true);
804 applyInsertUpdates(InsertUpdates, NewDT, &GD);
805 } else {
806 GraphDiff<BasicBlock *> GD;
807 applyInsertUpdates(InsertUpdates, DT, &GD);
808 }
809
810 // Update for deleted edges
811 for (auto &Update : DeleteUpdates)
812 removeEdge(Update.getFrom(), Update.getTo());
813 }
814
applyInsertUpdates(ArrayRef<CFGUpdate> Updates,DominatorTree & DT)815 void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
816 DominatorTree &DT) {
817 GraphDiff<BasicBlock *> GD;
818 applyInsertUpdates(Updates, DT, &GD);
819 }
820
applyInsertUpdates(ArrayRef<CFGUpdate> Updates,DominatorTree & DT,const GraphDiff<BasicBlock * > * GD)821 void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
822 DominatorTree &DT,
823 const GraphDiff<BasicBlock *> *GD) {
824 // Get recursive last Def, assuming well formed MSSA and updated DT.
825 auto GetLastDef = [&](BasicBlock *BB) -> MemoryAccess * {
826 while (true) {
827 MemorySSA::DefsList *Defs = MSSA->getWritableBlockDefs(BB);
828 // Return last Def or Phi in BB, if it exists.
829 if (Defs)
830 return &*(--Defs->end());
831
832 // Check number of predecessors, we only care if there's more than one.
833 unsigned Count = 0;
834 BasicBlock *Pred = nullptr;
835 for (auto &Pair : children<GraphDiffInvBBPair>({GD, BB})) {
836 Pred = Pair.second;
837 Count++;
838 if (Count == 2)
839 break;
840 }
841
842 // If BB has multiple predecessors, get last definition from IDom.
843 if (Count != 1) {
844 // [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its
845 // DT is invalidated. Return LoE as its last def. This will be added to
846 // MemoryPhi node, and later deleted when the block is deleted.
847 if (!DT.getNode(BB))
848 return MSSA->getLiveOnEntryDef();
849 if (auto *IDom = DT.getNode(BB)->getIDom())
850 if (IDom->getBlock() != BB) {
851 BB = IDom->getBlock();
852 continue;
853 }
854 return MSSA->getLiveOnEntryDef();
855 } else {
856 // Single predecessor, BB cannot be dead. GetLastDef of Pred.
857 assert(Count == 1 && Pred && "Single predecessor expected.");
858 // BB can be unreachable though, return LoE if that is the case.
859 if (!DT.getNode(BB))
860 return MSSA->getLiveOnEntryDef();
861 BB = Pred;
862 }
863 };
864 llvm_unreachable("Unable to get last definition.");
865 };
866
867 // Get nearest IDom given a set of blocks.
868 // TODO: this can be optimized by starting the search at the node with the
869 // lowest level (highest in the tree).
870 auto FindNearestCommonDominator =
871 [&](const SmallSetVector<BasicBlock *, 2> &BBSet) -> BasicBlock * {
872 BasicBlock *PrevIDom = *BBSet.begin();
873 for (auto *BB : BBSet)
874 PrevIDom = DT.findNearestCommonDominator(PrevIDom, BB);
875 return PrevIDom;
876 };
877
878 // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not
879 // include CurrIDom.
880 auto GetNoLongerDomBlocks =
881 [&](BasicBlock *PrevIDom, BasicBlock *CurrIDom,
882 SmallVectorImpl<BasicBlock *> &BlocksPrevDom) {
883 if (PrevIDom == CurrIDom)
884 return;
885 BlocksPrevDom.push_back(PrevIDom);
886 BasicBlock *NextIDom = PrevIDom;
887 while (BasicBlock *UpIDom =
888 DT.getNode(NextIDom)->getIDom()->getBlock()) {
889 if (UpIDom == CurrIDom)
890 break;
891 BlocksPrevDom.push_back(UpIDom);
892 NextIDom = UpIDom;
893 }
894 };
895
896 // Map a BB to its predecessors: added + previously existing. To get a
897 // deterministic order, store predecessors as SetVectors. The order in each
898 // will be defined by the order in Updates (fixed) and the order given by
899 // children<> (also fixed). Since we further iterate over these ordered sets,
900 // we lose the information of multiple edges possibly existing between two
901 // blocks, so we'll keep and EdgeCount map for that.
902 // An alternate implementation could keep unordered set for the predecessors,
903 // traverse either Updates or children<> each time to get the deterministic
904 // order, and drop the usage of EdgeCount. This alternate approach would still
905 // require querying the maps for each predecessor, and children<> call has
906 // additional computation inside for creating the snapshot-graph predecessors.
907 // As such, we favor using a little additional storage and less compute time.
908 // This decision can be revisited if we find the alternative more favorable.
909
910 struct PredInfo {
911 SmallSetVector<BasicBlock *, 2> Added;
912 SmallSetVector<BasicBlock *, 2> Prev;
913 };
914 SmallDenseMap<BasicBlock *, PredInfo> PredMap;
915
916 for (auto &Edge : Updates) {
917 BasicBlock *BB = Edge.getTo();
918 auto &AddedBlockSet = PredMap[BB].Added;
919 AddedBlockSet.insert(Edge.getFrom());
920 }
921
922 // Store all existing predecessor for each BB, at least one must exist.
923 SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>, int> EdgeCountMap;
924 SmallPtrSet<BasicBlock *, 2> NewBlocks;
925 for (auto &BBPredPair : PredMap) {
926 auto *BB = BBPredPair.first;
927 const auto &AddedBlockSet = BBPredPair.second.Added;
928 auto &PrevBlockSet = BBPredPair.second.Prev;
929 for (auto &Pair : children<GraphDiffInvBBPair>({GD, BB})) {
930 BasicBlock *Pi = Pair.second;
931 if (!AddedBlockSet.count(Pi))
932 PrevBlockSet.insert(Pi);
933 EdgeCountMap[{Pi, BB}]++;
934 }
935
936 if (PrevBlockSet.empty()) {
937 assert(pred_size(BB) == AddedBlockSet.size() && "Duplicate edges added.");
938 LLVM_DEBUG(
939 dbgs()
940 << "Adding a predecessor to a block with no predecessors. "
941 "This must be an edge added to a new, likely cloned, block. "
942 "Its memory accesses must be already correct, assuming completed "
943 "via the updateExitBlocksForClonedLoop API. "
944 "Assert a single such edge is added so no phi addition or "
945 "additional processing is required.\n");
946 assert(AddedBlockSet.size() == 1 &&
947 "Can only handle adding one predecessor to a new block.");
948 // Need to remove new blocks from PredMap. Remove below to not invalidate
949 // iterator here.
950 NewBlocks.insert(BB);
951 }
952 }
953 // Nothing to process for new/cloned blocks.
954 for (auto *BB : NewBlocks)
955 PredMap.erase(BB);
956
957 SmallVector<BasicBlock *, 16> BlocksWithDefsToReplace;
958 SmallVector<WeakVH, 8> InsertedPhis;
959
960 // First create MemoryPhis in all blocks that don't have one. Create in the
961 // order found in Updates, not in PredMap, to get deterministic numbering.
962 for (auto &Edge : Updates) {
963 BasicBlock *BB = Edge.getTo();
964 if (PredMap.count(BB) && !MSSA->getMemoryAccess(BB))
965 InsertedPhis.push_back(MSSA->createMemoryPhi(BB));
966 }
967
968 // Now we'll fill in the MemoryPhis with the right incoming values.
969 for (auto &BBPredPair : PredMap) {
970 auto *BB = BBPredPair.first;
971 const auto &PrevBlockSet = BBPredPair.second.Prev;
972 const auto &AddedBlockSet = BBPredPair.second.Added;
973 assert(!PrevBlockSet.empty() &&
974 "At least one previous predecessor must exist.");
975
976 // TODO: if this becomes a bottleneck, we can save on GetLastDef calls by
977 // keeping this map before the loop. We can reuse already populated entries
978 // if an edge is added from the same predecessor to two different blocks,
979 // and this does happen in rotate. Note that the map needs to be updated
980 // when deleting non-necessary phis below, if the phi is in the map by
981 // replacing the value with DefP1.
982 SmallDenseMap<BasicBlock *, MemoryAccess *> LastDefAddedPred;
983 for (auto *AddedPred : AddedBlockSet) {
984 auto *DefPn = GetLastDef(AddedPred);
985 assert(DefPn != nullptr && "Unable to find last definition.");
986 LastDefAddedPred[AddedPred] = DefPn;
987 }
988
989 MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB);
990 // If Phi is not empty, add an incoming edge from each added pred. Must
991 // still compute blocks with defs to replace for this block below.
992 if (NewPhi->getNumOperands()) {
993 for (auto *Pred : AddedBlockSet) {
994 auto *LastDefForPred = LastDefAddedPred[Pred];
995 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
996 NewPhi->addIncoming(LastDefForPred, Pred);
997 }
998 } else {
999 // Pick any existing predecessor and get its definition. All other
1000 // existing predecessors should have the same one, since no phi existed.
1001 auto *P1 = *PrevBlockSet.begin();
1002 MemoryAccess *DefP1 = GetLastDef(P1);
1003
1004 // Check DefP1 against all Defs in LastDefPredPair. If all the same,
1005 // nothing to add.
1006 bool InsertPhi = false;
1007 for (auto LastDefPredPair : LastDefAddedPred)
1008 if (DefP1 != LastDefPredPair.second) {
1009 InsertPhi = true;
1010 break;
1011 }
1012 if (!InsertPhi) {
1013 // Since NewPhi may be used in other newly added Phis, replace all uses
1014 // of NewPhi with the definition coming from all predecessors (DefP1),
1015 // before deleting it.
1016 NewPhi->replaceAllUsesWith(DefP1);
1017 removeMemoryAccess(NewPhi);
1018 continue;
1019 }
1020
1021 // Update Phi with new values for new predecessors and old value for all
1022 // other predecessors. Since AddedBlockSet and PrevBlockSet are ordered
1023 // sets, the order of entries in NewPhi is deterministic.
1024 for (auto *Pred : AddedBlockSet) {
1025 auto *LastDefForPred = LastDefAddedPred[Pred];
1026 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
1027 NewPhi->addIncoming(LastDefForPred, Pred);
1028 }
1029 for (auto *Pred : PrevBlockSet)
1030 for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
1031 NewPhi->addIncoming(DefP1, Pred);
1032 }
1033
1034 // Get all blocks that used to dominate BB and no longer do after adding
1035 // AddedBlockSet, where PrevBlockSet are the previously known predecessors.
1036 assert(DT.getNode(BB)->getIDom() && "BB does not have valid idom");
1037 BasicBlock *PrevIDom = FindNearestCommonDominator(PrevBlockSet);
1038 assert(PrevIDom && "Previous IDom should exists");
1039 BasicBlock *NewIDom = DT.getNode(BB)->getIDom()->getBlock();
1040 assert(NewIDom && "BB should have a new valid idom");
1041 assert(DT.dominates(NewIDom, PrevIDom) &&
1042 "New idom should dominate old idom");
1043 GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);
1044 }
1045
1046 tryRemoveTrivialPhis(InsertedPhis);
1047 // Create the set of blocks that now have a definition. We'll use this to
1048 // compute IDF and add Phis there next.
1049 SmallVector<BasicBlock *, 8> BlocksToProcess;
1050 for (auto &VH : InsertedPhis)
1051 if (auto *MPhi = cast_or_null<MemoryPhi>(VH))
1052 BlocksToProcess.push_back(MPhi->getBlock());
1053
1054 // Compute IDF and add Phis in all IDF blocks that do not have one.
1055 SmallVector<BasicBlock *, 32> IDFBlocks;
1056 if (!BlocksToProcess.empty()) {
1057 ForwardIDFCalculator IDFs(DT, GD);
1058 SmallPtrSet<BasicBlock *, 16> DefiningBlocks(BlocksToProcess.begin(),
1059 BlocksToProcess.end());
1060 IDFs.setDefiningBlocks(DefiningBlocks);
1061 IDFs.calculate(IDFBlocks);
1062
1063 SmallSetVector<MemoryPhi *, 4> PhisToFill;
1064 // First create all needed Phis.
1065 for (auto *BBIDF : IDFBlocks)
1066 if (!MSSA->getMemoryAccess(BBIDF)) {
1067 auto *IDFPhi = MSSA->createMemoryPhi(BBIDF);
1068 InsertedPhis.push_back(IDFPhi);
1069 PhisToFill.insert(IDFPhi);
1070 }
1071 // Then update or insert their correct incoming values.
1072 for (auto *BBIDF : IDFBlocks) {
1073 auto *IDFPhi = MSSA->getMemoryAccess(BBIDF);
1074 assert(IDFPhi && "Phi must exist");
1075 if (!PhisToFill.count(IDFPhi)) {
1076 // Update existing Phi.
1077 // FIXME: some updates may be redundant, try to optimize and skip some.
1078 for (unsigned I = 0, E = IDFPhi->getNumIncomingValues(); I < E; ++I)
1079 IDFPhi->setIncomingValue(I, GetLastDef(IDFPhi->getIncomingBlock(I)));
1080 } else {
1081 for (auto &Pair : children<GraphDiffInvBBPair>({GD, BBIDF})) {
1082 BasicBlock *Pi = Pair.second;
1083 IDFPhi->addIncoming(GetLastDef(Pi), Pi);
1084 }
1085 }
1086 }
1087 }
1088
1089 // Now for all defs in BlocksWithDefsToReplace, if there are uses they no
1090 // longer dominate, replace those with the closest dominating def.
1091 // This will also update optimized accesses, as they're also uses.
1092 for (auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) {
1093 if (auto DefsList = MSSA->getWritableBlockDefs(BlockWithDefsToReplace)) {
1094 for (auto &DefToReplaceUses : *DefsList) {
1095 BasicBlock *DominatingBlock = DefToReplaceUses.getBlock();
1096 Value::use_iterator UI = DefToReplaceUses.use_begin(),
1097 E = DefToReplaceUses.use_end();
1098 for (; UI != E;) {
1099 Use &U = *UI;
1100 ++UI;
1101 MemoryAccess *Usr = cast<MemoryAccess>(U.getUser());
1102 if (MemoryPhi *UsrPhi = dyn_cast<MemoryPhi>(Usr)) {
1103 BasicBlock *DominatedBlock = UsrPhi->getIncomingBlock(U);
1104 if (!DT.dominates(DominatingBlock, DominatedBlock))
1105 U.set(GetLastDef(DominatedBlock));
1106 } else {
1107 BasicBlock *DominatedBlock = Usr->getBlock();
1108 if (!DT.dominates(DominatingBlock, DominatedBlock)) {
1109 if (auto *DomBlPhi = MSSA->getMemoryAccess(DominatedBlock))
1110 U.set(DomBlPhi);
1111 else {
1112 auto *IDom = DT.getNode(DominatedBlock)->getIDom();
1113 assert(IDom && "Block must have a valid IDom.");
1114 U.set(GetLastDef(IDom->getBlock()));
1115 }
1116 cast<MemoryUseOrDef>(Usr)->resetOptimized();
1117 }
1118 }
1119 }
1120 }
1121 }
1122 }
1123 tryRemoveTrivialPhis(InsertedPhis);
1124 }
1125
1126 // Move What before Where in the MemorySSA IR.
1127 template <class WhereType>
moveTo(MemoryUseOrDef * What,BasicBlock * BB,WhereType Where)1128 void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
1129 WhereType Where) {
1130 // Mark MemoryPhi users of What not to be optimized.
1131 for (auto *U : What->users())
1132 if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))
1133 NonOptPhis.insert(PhiUser);
1134
1135 // Replace all our users with our defining access.
1136 What->replaceAllUsesWith(What->getDefiningAccess());
1137
1138 // Let MemorySSA take care of moving it around in the lists.
1139 MSSA->moveTo(What, BB, Where);
1140
1141 // Now reinsert it into the IR and do whatever fixups needed.
1142 if (auto *MD = dyn_cast<MemoryDef>(What))
1143 insertDef(MD, /*RenameUses=*/true);
1144 else
1145 insertUse(cast<MemoryUse>(What), /*RenameUses=*/true);
1146
1147 // Clear dangling pointers. We added all MemoryPhi users, but not all
1148 // of them are removed by fixupDefs().
1149 NonOptPhis.clear();
1150 }
1151
1152 // Move What before Where in the MemorySSA IR.
moveBefore(MemoryUseOrDef * What,MemoryUseOrDef * Where)1153 void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
1154 moveTo(What, Where->getBlock(), Where->getIterator());
1155 }
1156
1157 // Move What after Where in the MemorySSA IR.
moveAfter(MemoryUseOrDef * What,MemoryUseOrDef * Where)1158 void MemorySSAUpdater::moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where) {
1159 moveTo(What, Where->getBlock(), ++Where->getIterator());
1160 }
1161
moveToPlace(MemoryUseOrDef * What,BasicBlock * BB,MemorySSA::InsertionPlace Where)1162 void MemorySSAUpdater::moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
1163 MemorySSA::InsertionPlace Where) {
1164 if (Where != MemorySSA::InsertionPlace::BeforeTerminator)
1165 return moveTo(What, BB, Where);
1166
1167 if (auto *Where = MSSA->getMemoryAccess(BB->getTerminator()))
1168 return moveBefore(What, Where);
1169 else
1170 return moveTo(What, BB, MemorySSA::InsertionPlace::End);
1171 }
1172
1173 // All accesses in To used to be in From. Move to end and update access lists.
moveAllAccesses(BasicBlock * From,BasicBlock * To,Instruction * Start)1174 void MemorySSAUpdater::moveAllAccesses(BasicBlock *From, BasicBlock *To,
1175 Instruction *Start) {
1176
1177 MemorySSA::AccessList *Accs = MSSA->getWritableBlockAccesses(From);
1178 if (!Accs)
1179 return;
1180
1181 assert(Start->getParent() == To && "Incorrect Start instruction");
1182 MemoryAccess *FirstInNew = nullptr;
1183 for (Instruction &I : make_range(Start->getIterator(), To->end()))
1184 if ((FirstInNew = MSSA->getMemoryAccess(&I)))
1185 break;
1186 if (FirstInNew) {
1187 auto *MUD = cast<MemoryUseOrDef>(FirstInNew);
1188 do {
1189 auto NextIt = ++MUD->getIterator();
1190 MemoryUseOrDef *NextMUD = (!Accs || NextIt == Accs->end())
1191 ? nullptr
1192 : cast<MemoryUseOrDef>(&*NextIt);
1193 MSSA->moveTo(MUD, To, MemorySSA::End);
1194 // Moving MUD from Accs in the moveTo above, may delete Accs, so we need
1195 // to retrieve it again.
1196 Accs = MSSA->getWritableBlockAccesses(From);
1197 MUD = NextMUD;
1198 } while (MUD);
1199 }
1200
1201 // If all accesses were moved and only a trivial Phi remains, we try to remove
1202 // that Phi. This is needed when From is going to be deleted.
1203 auto *Defs = MSSA->getWritableBlockDefs(From);
1204 if (Defs && !Defs->empty())
1205 if (auto *Phi = dyn_cast<MemoryPhi>(&*Defs->begin()))
1206 tryRemoveTrivialPhi(Phi);
1207 }
1208
moveAllAfterSpliceBlocks(BasicBlock * From,BasicBlock * To,Instruction * Start)1209 void MemorySSAUpdater::moveAllAfterSpliceBlocks(BasicBlock *From,
1210 BasicBlock *To,
1211 Instruction *Start) {
1212 assert(MSSA->getBlockAccesses(To) == nullptr &&
1213 "To block is expected to be free of MemoryAccesses.");
1214 moveAllAccesses(From, To, Start);
1215 for (BasicBlock *Succ : successors(To))
1216 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
1217 MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
1218 }
1219
moveAllAfterMergeBlocks(BasicBlock * From,BasicBlock * To,Instruction * Start)1220 void MemorySSAUpdater::moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
1221 Instruction *Start) {
1222 assert(From->getUniquePredecessor() == To &&
1223 "From block is expected to have a single predecessor (To).");
1224 moveAllAccesses(From, To, Start);
1225 for (BasicBlock *Succ : successors(From))
1226 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Succ))
1227 MPhi->setIncomingBlock(MPhi->getBasicBlockIndex(From), To);
1228 }
1229
1230 /// If all arguments of a MemoryPHI are defined by the same incoming
1231 /// argument, return that argument.
onlySingleValue(MemoryPhi * MP)1232 static MemoryAccess *onlySingleValue(MemoryPhi *MP) {
1233 MemoryAccess *MA = nullptr;
1234
1235 for (auto &Arg : MP->operands()) {
1236 if (!MA)
1237 MA = cast<MemoryAccess>(Arg);
1238 else if (MA != Arg)
1239 return nullptr;
1240 }
1241 return MA;
1242 }
1243
wireOldPredecessorsToNewImmediatePredecessor(BasicBlock * Old,BasicBlock * New,ArrayRef<BasicBlock * > Preds,bool IdenticalEdgesWereMerged)1244 void MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor(
1245 BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
1246 bool IdenticalEdgesWereMerged) {
1247 assert(!MSSA->getWritableBlockAccesses(New) &&
1248 "Access list should be null for a new block.");
1249 MemoryPhi *Phi = MSSA->getMemoryAccess(Old);
1250 if (!Phi)
1251 return;
1252 if (Old->hasNPredecessors(1)) {
1253 assert(pred_size(New) == Preds.size() &&
1254 "Should have moved all predecessors.");
1255 MSSA->moveTo(Phi, New, MemorySSA::Beginning);
1256 } else {
1257 assert(!Preds.empty() && "Must be moving at least one predecessor to the "
1258 "new immediate predecessor.");
1259 MemoryPhi *NewPhi = MSSA->createMemoryPhi(New);
1260 SmallPtrSet<BasicBlock *, 16> PredsSet(Preds.begin(), Preds.end());
1261 // Currently only support the case of removing a single incoming edge when
1262 // identical edges were not merged.
1263 if (!IdenticalEdgesWereMerged)
1264 assert(PredsSet.size() == Preds.size() &&
1265 "If identical edges were not merged, we cannot have duplicate "
1266 "blocks in the predecessors");
1267 Phi->unorderedDeleteIncomingIf([&](MemoryAccess *MA, BasicBlock *B) {
1268 if (PredsSet.count(B)) {
1269 NewPhi->addIncoming(MA, B);
1270 if (!IdenticalEdgesWereMerged)
1271 PredsSet.erase(B);
1272 return true;
1273 }
1274 return false;
1275 });
1276 Phi->addIncoming(NewPhi, New);
1277 tryRemoveTrivialPhi(NewPhi);
1278 }
1279 }
1280
removeMemoryAccess(MemoryAccess * MA,bool OptimizePhis)1281 void MemorySSAUpdater::removeMemoryAccess(MemoryAccess *MA, bool OptimizePhis) {
1282 assert(!MSSA->isLiveOnEntryDef(MA) &&
1283 "Trying to remove the live on entry def");
1284 // We can only delete phi nodes if they have no uses, or we can replace all
1285 // uses with a single definition.
1286 MemoryAccess *NewDefTarget = nullptr;
1287 if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
1288 // Note that it is sufficient to know that all edges of the phi node have
1289 // the same argument. If they do, by the definition of dominance frontiers
1290 // (which we used to place this phi), that argument must dominate this phi,
1291 // and thus, must dominate the phi's uses, and so we will not hit the assert
1292 // below.
1293 NewDefTarget = onlySingleValue(MP);
1294 assert((NewDefTarget || MP->use_empty()) &&
1295 "We can't delete this memory phi");
1296 } else {
1297 NewDefTarget = cast<MemoryUseOrDef>(MA)->getDefiningAccess();
1298 }
1299
1300 SmallSetVector<MemoryPhi *, 4> PhisToCheck;
1301
1302 // Re-point the uses at our defining access
1303 if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
1304 // Reset optimized on users of this store, and reset the uses.
1305 // A few notes:
1306 // 1. This is a slightly modified version of RAUW to avoid walking the
1307 // uses twice here.
1308 // 2. If we wanted to be complete, we would have to reset the optimized
1309 // flags on users of phi nodes if doing the below makes a phi node have all
1310 // the same arguments. Instead, we prefer users to removeMemoryAccess those
1311 // phi nodes, because doing it here would be N^3.
1312 if (MA->hasValueHandle())
1313 ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
1314 // Note: We assume MemorySSA is not used in metadata since it's not really
1315 // part of the IR.
1316
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
removeBlocks(const SmallSetVector<BasicBlock *,8> & DeadBlocks)1347 void MemorySSAUpdater::removeBlocks(
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
1360 if (MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(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) {
1367 MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB);
1368 if (!Acc)
1369 continue;
1370 for (auto AB = Acc->begin(), AE = Acc->end(); AB != AE;) {
1371 MemoryAccess *MA = &*AB;
1372 ++AB;
1373 MSSA->removeFromLookups(MA);
1374 MSSA->removeFromLists(MA);
1375 }
1376 }
1377 }
1378
tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs)1379 void MemorySSAUpdater::tryRemoveTrivialPhis(ArrayRef<WeakVH> UpdatedPHIs) {
1380 for (auto &VH : UpdatedPHIs)
1381 if (auto *MPhi = cast_or_null<MemoryPhi>(VH))
1382 tryRemoveTrivialPhi(MPhi);
1383 }
1384
changeToUnreachable(const Instruction * I)1385 void MemorySSAUpdater::changeToUnreachable(const Instruction *I) {
1386 const BasicBlock *BB = I->getParent();
1387 // Remove memory accesses in BB for I and all following instructions.
1388 auto BBI = I->getIterator(), BBE = BB->end();
1389 // FIXME: If this becomes too expensive, iterate until the first instruction
1390 // with a memory access, then iterate over MemoryAccesses.
1391 while (BBI != BBE)
1392 removeMemoryAccess(&*(BBI++));
1393 // Update phis in BB's successors to remove BB.
1394 SmallVector<WeakVH, 16> UpdatedPHIs;
1395 for (const BasicBlock *Successor : successors(BB)) {
1396 removeDuplicatePhiEdgesBetween(BB, Successor);
1397 if (MemoryPhi *MPhi = MSSA->getMemoryAccess(Successor)) {
1398 MPhi->unorderedDeleteIncomingBlock(BB);
1399 UpdatedPHIs.push_back(MPhi);
1400 }
1401 }
1402 // Optimize trivial phis.
1403 tryRemoveTrivialPhis(UpdatedPHIs);
1404 }
1405
changeCondBranchToUnconditionalTo(const BranchInst * BI,const BasicBlock * To)1406 void MemorySSAUpdater::changeCondBranchToUnconditionalTo(const BranchInst *BI,
1407 const BasicBlock *To) {
1408 const BasicBlock *BB = BI->getParent();
1409 SmallVector<WeakVH, 16> UpdatedPHIs;
1410 for (const BasicBlock *Succ : successors(BB)) {
1411 removeDuplicatePhiEdgesBetween(BB, Succ);
1412 if (Succ != To)
1413 if (auto *MPhi = MSSA->getMemoryAccess(Succ)) {
1414 MPhi->unorderedDeleteIncomingBlock(BB);
1415 UpdatedPHIs.push_back(MPhi);
1416 }
1417 }
1418 // Optimize trivial phis.
1419 tryRemoveTrivialPhis(UpdatedPHIs);
1420 }
1421
createMemoryAccessInBB(Instruction * I,MemoryAccess * Definition,const BasicBlock * BB,MemorySSA::InsertionPlace Point)1422 MemoryAccess *MemorySSAUpdater::createMemoryAccessInBB(
1423 Instruction *I, MemoryAccess *Definition, const BasicBlock *BB,
1424 MemorySSA::InsertionPlace Point) {
1425 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1426 MSSA->insertIntoListsForBlock(NewAccess, BB, Point);
1427 return NewAccess;
1428 }
1429
createMemoryAccessBefore(Instruction * I,MemoryAccess * Definition,MemoryUseOrDef * InsertPt)1430 MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessBefore(
1431 Instruction *I, MemoryAccess *Definition, MemoryUseOrDef *InsertPt) {
1432 assert(I->getParent() == InsertPt->getBlock() &&
1433 "New and old access must be in the same block");
1434 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1435 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1436 InsertPt->getIterator());
1437 return NewAccess;
1438 }
1439
createMemoryAccessAfter(Instruction * I,MemoryAccess * Definition,MemoryAccess * InsertPt)1440 MemoryUseOrDef *MemorySSAUpdater::createMemoryAccessAfter(
1441 Instruction *I, MemoryAccess *Definition, MemoryAccess *InsertPt) {
1442 assert(I->getParent() == InsertPt->getBlock() &&
1443 "New and old access must be in the same block");
1444 MemoryUseOrDef *NewAccess = MSSA->createDefinedAccess(I, Definition);
1445 MSSA->insertIntoListsBefore(NewAccess, InsertPt->getBlock(),
1446 ++InsertPt->getIterator());
1447 return NewAccess;
1448 }
1449