1//===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===//
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 promotes memory references to be register references. It promotes
10// alloca instructions which only have loads and stores as uses. An alloca is
11// transformed by using iterated dominator frontiers to place PHI nodes, then
12// traversing the function in depth-first order to rewrite loads and stores as
13// appropriate.
14//
15//===----------------------------------------------------------------------===//
16
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SmallPtrSet.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/ADT/Twine.h"
24#include "llvm/Analysis/AssumptionCache.h"
25#include "llvm/Analysis/InstructionSimplify.h"
26#include "llvm/Analysis/IteratedDominanceFrontier.h"
27#include "llvm/Analysis/ValueTracking.h"
28#include "llvm/IR/BasicBlock.h"
29#include "llvm/IR/CFG.h"
30#include "llvm/IR/Constant.h"
31#include "llvm/IR/Constants.h"
32#include "llvm/IR/DIBuilder.h"
33#include "llvm/IR/DebugInfo.h"
34#include "llvm/IR/DebugProgramInstruction.h"
35#include "llvm/IR/Dominators.h"
36#include "llvm/IR/Function.h"
37#include "llvm/IR/InstrTypes.h"
38#include "llvm/IR/Instruction.h"
39#include "llvm/IR/Instructions.h"
40#include "llvm/IR/IntrinsicInst.h"
41#include "llvm/IR/Intrinsics.h"
42#include "llvm/IR/LLVMContext.h"
43#include "llvm/IR/Module.h"
44#include "llvm/IR/Type.h"
45#include "llvm/IR/User.h"
46#include "llvm/Support/Casting.h"
47#include "llvm/Transforms/Utils/Local.h"
48#include "llvm/Transforms/Utils/PromoteMemToReg.h"
49#include <algorithm>
50#include <cassert>
51#include <iterator>
52#include <utility>
53#include <vector>
54
55using namespace llvm;
56
57#define DEBUG_TYPE "mem2reg"
58
59STATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block");
60STATISTIC(NumSingleStore, "Number of alloca's promoted with a single store");
61STATISTIC(NumDeadAlloca, "Number of dead alloca's removed");
62STATISTIC(NumPHIInsert, "Number of PHI nodes inserted");
63
64bool llvm::isAllocaPromotable(const AllocaInst *AI) {
65 // Only allow direct and non-volatile loads and stores...
66 for (const User *U : AI->users()) {
67 if (const LoadInst *LI = dyn_cast<LoadInst>(Val: U)) {
68 // Note that atomic loads can be transformed; atomic semantics do
69 // not have any meaning for a local alloca.
70 if (LI->isVolatile() || LI->getType() != AI->getAllocatedType())
71 return false;
72 } else if (const StoreInst *SI = dyn_cast<StoreInst>(Val: U)) {
73 if (SI->getValueOperand() == AI ||
74 SI->getValueOperand()->getType() != AI->getAllocatedType())
75 return false; // Don't allow a store OF the AI, only INTO the AI.
76 // Note that atomic stores can be transformed; atomic semantics do
77 // not have any meaning for a local alloca.
78 if (SI->isVolatile())
79 return false;
80 } else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: U)) {
81 if (!II->isLifetimeStartOrEnd() && !II->isDroppable())
82 return false;
83 } else if (const BitCastInst *BCI = dyn_cast<BitCastInst>(Val: U)) {
84 if (!onlyUsedByLifetimeMarkersOrDroppableInsts(V: BCI))
85 return false;
86 } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Val: U)) {
87 if (!GEPI->hasAllZeroIndices())
88 return false;
89 if (!onlyUsedByLifetimeMarkersOrDroppableInsts(V: GEPI))
90 return false;
91 } else if (const AddrSpaceCastInst *ASCI = dyn_cast<AddrSpaceCastInst>(Val: U)) {
92 if (!onlyUsedByLifetimeMarkers(V: ASCI))
93 return false;
94 } else {
95 return false;
96 }
97 }
98
99 return true;
100}
101
102namespace {
103
104static void createDebugValue(DIBuilder &DIB, Value *NewValue,
105 DILocalVariable *Variable,
106 DIExpression *Expression, const DILocation *DI,
107 DbgVariableRecord *InsertBefore) {
108 // FIXME: Merge these two functions now that DIBuilder supports
109 // DbgVariableRecords. We neeed the API to accept DbgVariableRecords as an
110 // insert point for that to work.
111 (void)DIB;
112 DbgVariableRecord::createDbgVariableRecord(Location: NewValue, DV: Variable, Expr: Expression, DI,
113 InsertBefore&: *InsertBefore);
114}
115static void createDebugValue(DIBuilder &DIB, Value *NewValue,
116 DILocalVariable *Variable,
117 DIExpression *Expression, const DILocation *DI,
118 Instruction *InsertBefore) {
119 DIB.insertDbgValueIntrinsic(Val: NewValue, VarInfo: Variable, Expr: Expression, DL: DI, InsertBefore);
120}
121
122/// Helper for updating assignment tracking debug info when promoting allocas.
123class AssignmentTrackingInfo {
124 /// DbgAssignIntrinsics linked to the alloca with at most one per variable
125 /// fragment. (i.e. not be a comprehensive set if there are multiple
126 /// dbg.assigns for one variable fragment).
127 SmallVector<DbgVariableIntrinsic *> DbgAssigns;
128 SmallVector<DbgVariableRecord *> DVRAssigns;
129
130public:
131 void init(AllocaInst *AI) {
132 SmallSet<DebugVariable, 2> Vars;
133 for (DbgAssignIntrinsic *DAI : at::getAssignmentMarkers(Inst: AI)) {
134 if (Vars.insert(V: DebugVariable(DAI)).second)
135 DbgAssigns.push_back(Elt: DAI);
136 }
137 for (DbgVariableRecord *DVR : at::getDVRAssignmentMarkers(Inst: AI)) {
138 if (Vars.insert(V: DebugVariable(DVR)).second)
139 DVRAssigns.push_back(Elt: DVR);
140 }
141 }
142
143 /// Update assignment tracking debug info given for the to-be-deleted store
144 /// \p ToDelete that stores to this alloca.
145 void updateForDeletedStore(
146 StoreInst *ToDelete, DIBuilder &DIB,
147 SmallSet<DbgAssignIntrinsic *, 8> *DbgAssignsToDelete,
148 SmallSet<DbgVariableRecord *, 8> *DVRAssignsToDelete) const {
149 // There's nothing to do if the alloca doesn't have any variables using
150 // assignment tracking.
151 if (DbgAssigns.empty() && DVRAssigns.empty())
152 return;
153
154 // Insert a dbg.value where the linked dbg.assign is and remember to delete
155 // the dbg.assign later. Demoting to dbg.value isn't necessary for
156 // correctness but does reduce compile time and memory usage by reducing
157 // unnecessary function-local metadata. Remember that we've seen a
158 // dbg.assign for each variable fragment for the untracked store handling
159 // (after this loop).
160 SmallSet<DebugVariableAggregate, 2> VarHasDbgAssignForStore;
161 auto InsertValueForAssign = [&](auto *DbgAssign, auto *&AssignList) {
162 VarHasDbgAssignForStore.insert(V: DebugVariableAggregate(DbgAssign));
163 AssignList->insert(DbgAssign);
164 createDebugValue(DIB, DbgAssign->getValue(), DbgAssign->getVariable(),
165 DbgAssign->getExpression(), DbgAssign->getDebugLoc(),
166 DbgAssign);
167 };
168 for (auto *Assign : at::getAssignmentMarkers(Inst: ToDelete))
169 InsertValueForAssign(Assign, DbgAssignsToDelete);
170 for (auto *Assign : at::getDVRAssignmentMarkers(Inst: ToDelete))
171 InsertValueForAssign(Assign, DVRAssignsToDelete);
172
173 // It's possible for variables using assignment tracking to have no
174 // dbg.assign linked to this store. These are variables in DbgAssigns that
175 // are missing from VarHasDbgAssignForStore. Since there isn't a dbg.assign
176 // to mark the assignment - and the store is going to be deleted - insert a
177 // dbg.value to do that now. An untracked store may be either one that
178 // cannot be represented using assignment tracking (non-const offset or
179 // size) or one that is trackable but has had its DIAssignID attachment
180 // dropped accidentally.
181 auto ConvertUnlinkedAssignToValue = [&](auto *Assign) {
182 if (VarHasDbgAssignForStore.contains(V: DebugVariableAggregate(Assign)))
183 return;
184 ConvertDebugDeclareToDebugValue(Assign, ToDelete, DIB);
185 };
186 for_each(Range: DbgAssigns, F: ConvertUnlinkedAssignToValue);
187 for_each(Range: DVRAssigns, F: ConvertUnlinkedAssignToValue);
188 }
189
190 /// Update assignment tracking debug info given for the newly inserted PHI \p
191 /// NewPhi.
192 void updateForNewPhi(PHINode *NewPhi, DIBuilder &DIB) const {
193 // Regardless of the position of dbg.assigns relative to stores, the
194 // incoming values into a new PHI should be the same for the (imaginary)
195 // debug-phi.
196 for (auto *DAI : DbgAssigns)
197 ConvertDebugDeclareToDebugValue(DII: DAI, LI: NewPhi, Builder&: DIB);
198 for (auto *DVR : DVRAssigns)
199 ConvertDebugDeclareToDebugValue(DVR, LI: NewPhi, Builder&: DIB);
200 }
201
202 void clear() {
203 DbgAssigns.clear();
204 DVRAssigns.clear();
205 }
206 bool empty() { return DbgAssigns.empty() && DVRAssigns.empty(); }
207};
208
209struct AllocaInfo {
210 using DbgUserVec = SmallVector<DbgVariableIntrinsic *, 1>;
211 using DPUserVec = SmallVector<DbgVariableRecord *, 1>;
212
213 SmallVector<BasicBlock *, 32> DefiningBlocks;
214 SmallVector<BasicBlock *, 32> UsingBlocks;
215
216 StoreInst *OnlyStore;
217 BasicBlock *OnlyBlock;
218 bool OnlyUsedInOneBlock;
219
220 /// Debug users of the alloca - does not include dbg.assign intrinsics.
221 DbgUserVec DbgUsers;
222 DPUserVec DPUsers;
223 /// Helper to update assignment tracking debug info.
224 AssignmentTrackingInfo AssignmentTracking;
225
226 void clear() {
227 DefiningBlocks.clear();
228 UsingBlocks.clear();
229 OnlyStore = nullptr;
230 OnlyBlock = nullptr;
231 OnlyUsedInOneBlock = true;
232 DbgUsers.clear();
233 DPUsers.clear();
234 AssignmentTracking.clear();
235 }
236
237 /// Scan the uses of the specified alloca, filling in the AllocaInfo used
238 /// by the rest of the pass to reason about the uses of this alloca.
239 void AnalyzeAlloca(AllocaInst *AI) {
240 clear();
241
242 // As we scan the uses of the alloca instruction, keep track of stores,
243 // and decide whether all of the loads and stores to the alloca are within
244 // the same basic block.
245 for (User *U : AI->users()) {
246 Instruction *User = cast<Instruction>(Val: U);
247
248 if (StoreInst *SI = dyn_cast<StoreInst>(Val: User)) {
249 // Remember the basic blocks which define new values for the alloca
250 DefiningBlocks.push_back(Elt: SI->getParent());
251 OnlyStore = SI;
252 } else {
253 LoadInst *LI = cast<LoadInst>(Val: User);
254 // Otherwise it must be a load instruction, keep track of variable
255 // reads.
256 UsingBlocks.push_back(Elt: LI->getParent());
257 }
258
259 if (OnlyUsedInOneBlock) {
260 if (!OnlyBlock)
261 OnlyBlock = User->getParent();
262 else if (OnlyBlock != User->getParent())
263 OnlyUsedInOneBlock = false;
264 }
265 }
266 DbgUserVec AllDbgUsers;
267 SmallVector<DbgVariableRecord *> AllDPUsers;
268 findDbgUsers(DbgInsts&: AllDbgUsers, V: AI, DbgVariableRecords: &AllDPUsers);
269 std::copy_if(first: AllDbgUsers.begin(), last: AllDbgUsers.end(),
270 result: std::back_inserter(x&: DbgUsers), pred: [](DbgVariableIntrinsic *DII) {
271 return !isa<DbgAssignIntrinsic>(Val: DII);
272 });
273 std::copy_if(first: AllDPUsers.begin(), last: AllDPUsers.end(),
274 result: std::back_inserter(x&: DPUsers),
275 pred: [](DbgVariableRecord *DVR) { return !DVR->isDbgAssign(); });
276 AssignmentTracking.init(AI);
277 }
278};
279
280/// Data package used by RenamePass().
281struct RenamePassData {
282 using ValVector = std::vector<Value *>;
283 using LocationVector = std::vector<DebugLoc>;
284
285 RenamePassData(BasicBlock *B, BasicBlock *P, ValVector V, LocationVector L)
286 : BB(B), Pred(P), Values(std::move(V)), Locations(std::move(L)) {}
287
288 BasicBlock *BB;
289 BasicBlock *Pred;
290 ValVector Values;
291 LocationVector Locations;
292};
293
294/// This assigns and keeps a per-bb relative ordering of load/store
295/// instructions in the block that directly load or store an alloca.
296///
297/// This functionality is important because it avoids scanning large basic
298/// blocks multiple times when promoting many allocas in the same block.
299class LargeBlockInfo {
300 /// For each instruction that we track, keep the index of the
301 /// instruction.
302 ///
303 /// The index starts out as the number of the instruction from the start of
304 /// the block.
305 DenseMap<const Instruction *, unsigned> InstNumbers;
306
307public:
308
309 /// This code only looks at accesses to allocas.
310 static bool isInterestingInstruction(const Instruction *I) {
311 return (isa<LoadInst>(Val: I) && isa<AllocaInst>(Val: I->getOperand(i: 0))) ||
312 (isa<StoreInst>(Val: I) && isa<AllocaInst>(Val: I->getOperand(i: 1)));
313 }
314
315 /// Get or calculate the index of the specified instruction.
316 unsigned getInstructionIndex(const Instruction *I) {
317 assert(isInterestingInstruction(I) &&
318 "Not a load/store to/from an alloca?");
319
320 // If we already have this instruction number, return it.
321 DenseMap<const Instruction *, unsigned>::iterator It = InstNumbers.find(Val: I);
322 if (It != InstNumbers.end())
323 return It->second;
324
325 // Scan the whole block to get the instruction. This accumulates
326 // information for every interesting instruction in the block, in order to
327 // avoid gratuitus rescans.
328 const BasicBlock *BB = I->getParent();
329 unsigned InstNo = 0;
330 for (const Instruction &BBI : *BB)
331 if (isInterestingInstruction(I: &BBI))
332 InstNumbers[&BBI] = InstNo++;
333 It = InstNumbers.find(Val: I);
334
335 assert(It != InstNumbers.end() && "Didn't insert instruction?");
336 return It->second;
337 }
338
339 void deleteValue(const Instruction *I) { InstNumbers.erase(Val: I); }
340
341 void clear() { InstNumbers.clear(); }
342};
343
344struct PromoteMem2Reg {
345 /// The alloca instructions being promoted.
346 std::vector<AllocaInst *> Allocas;
347
348 DominatorTree &DT;
349 DIBuilder DIB;
350
351 /// A cache of @llvm.assume intrinsics used by SimplifyInstruction.
352 AssumptionCache *AC;
353
354 const SimplifyQuery SQ;
355
356 /// Reverse mapping of Allocas.
357 DenseMap<AllocaInst *, unsigned> AllocaLookup;
358
359 /// The PhiNodes we're adding.
360 ///
361 /// That map is used to simplify some Phi nodes as we iterate over it, so
362 /// it should have deterministic iterators. We could use a MapVector, but
363 /// since we already maintain a map from BasicBlock* to a stable numbering
364 /// (BBNumbers), the DenseMap is more efficient (also supports removal).
365 DenseMap<std::pair<unsigned, unsigned>, PHINode *> NewPhiNodes;
366
367 /// For each PHI node, keep track of which entry in Allocas it corresponds
368 /// to.
369 DenseMap<PHINode *, unsigned> PhiToAllocaMap;
370
371 /// For each alloca, we keep track of the dbg.declare intrinsic that
372 /// describes it, if any, so that we can convert it to a dbg.value
373 /// intrinsic if the alloca gets promoted.
374 SmallVector<AllocaInfo::DbgUserVec, 8> AllocaDbgUsers;
375 SmallVector<AllocaInfo::DPUserVec, 8> AllocaDPUsers;
376
377 /// For each alloca, keep an instance of a helper class that gives us an easy
378 /// way to update assignment tracking debug info if the alloca is promoted.
379 SmallVector<AssignmentTrackingInfo, 8> AllocaATInfo;
380 /// A set of dbg.assigns to delete because they've been demoted to
381 /// dbg.values. Call cleanUpDbgAssigns to delete them.
382 SmallSet<DbgAssignIntrinsic *, 8> DbgAssignsToDelete;
383 SmallSet<DbgVariableRecord *, 8> DVRAssignsToDelete;
384
385 /// The set of basic blocks the renamer has already visited.
386 SmallPtrSet<BasicBlock *, 16> Visited;
387
388 /// Contains a stable numbering of basic blocks to avoid non-determinstic
389 /// behavior.
390 DenseMap<BasicBlock *, unsigned> BBNumbers;
391
392 /// Lazily compute the number of predecessors a block has.
393 DenseMap<const BasicBlock *, unsigned> BBNumPreds;
394
395public:
396 PromoteMem2Reg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
397 AssumptionCache *AC)
398 : Allocas(Allocas.begin(), Allocas.end()), DT(DT),
399 DIB(*DT.getRoot()->getParent()->getParent(), /*AllowUnresolved*/ false),
400 AC(AC), SQ(DT.getRoot()->getParent()->getParent()->getDataLayout(),
401 nullptr, &DT, AC) {}
402
403 void run();
404
405private:
406 void RemoveFromAllocasList(unsigned &AllocaIdx) {
407 Allocas[AllocaIdx] = Allocas.back();
408 Allocas.pop_back();
409 --AllocaIdx;
410 }
411
412 unsigned getNumPreds(const BasicBlock *BB) {
413 unsigned &NP = BBNumPreds[BB];
414 if (NP == 0)
415 NP = pred_size(BB) + 1;
416 return NP - 1;
417 }
418
419 void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
420 const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
421 SmallPtrSetImpl<BasicBlock *> &LiveInBlocks);
422 void RenamePass(BasicBlock *BB, BasicBlock *Pred,
423 RenamePassData::ValVector &IncVals,
424 RenamePassData::LocationVector &IncLocs,
425 std::vector<RenamePassData> &Worklist);
426 bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version);
427
428 /// Delete dbg.assigns that have been demoted to dbg.values.
429 void cleanUpDbgAssigns() {
430 for (auto *DAI : DbgAssignsToDelete)
431 DAI->eraseFromParent();
432 DbgAssignsToDelete.clear();
433 for (auto *DVR : DVRAssignsToDelete)
434 DVR->eraseFromParent();
435 DVRAssignsToDelete.clear();
436 }
437};
438
439} // end anonymous namespace
440
441/// Given a LoadInst LI this adds assume(LI != null) after it.
442static void addAssumeNonNull(AssumptionCache *AC, LoadInst *LI) {
443 Function *AssumeIntrinsic =
444 Intrinsic::getDeclaration(M: LI->getModule(), Intrinsic::id: assume);
445 ICmpInst *LoadNotNull = new ICmpInst(ICmpInst::ICMP_NE, LI,
446 Constant::getNullValue(Ty: LI->getType()));
447 LoadNotNull->insertAfter(InsertPos: LI);
448 CallInst *CI = CallInst::Create(Func: AssumeIntrinsic, Args: {LoadNotNull});
449 CI->insertAfter(InsertPos: LoadNotNull);
450 AC->registerAssumption(CI: cast<AssumeInst>(Val: CI));
451}
452
453static void convertMetadataToAssumes(LoadInst *LI, Value *Val,
454 const DataLayout &DL, AssumptionCache *AC,
455 const DominatorTree *DT) {
456 // If the load was marked as nonnull we don't want to lose that information
457 // when we erase this Load. So we preserve it with an assume. As !nonnull
458 // returns poison while assume violations are immediate undefined behavior,
459 // we can only do this if the value is known non-poison.
460 if (AC && LI->getMetadata(KindID: LLVMContext::MD_nonnull) &&
461 LI->getMetadata(KindID: LLVMContext::MD_noundef) &&
462 !isKnownNonZero(V: Val, Q: SimplifyQuery(DL, DT, AC, LI)))
463 addAssumeNonNull(AC, LI);
464}
465
466static void removeIntrinsicUsers(AllocaInst *AI) {
467 // Knowing that this alloca is promotable, we know that it's safe to kill all
468 // instructions except for load and store.
469
470 for (Use &U : llvm::make_early_inc_range(Range: AI->uses())) {
471 Instruction *I = cast<Instruction>(Val: U.getUser());
472 if (isa<LoadInst>(Val: I) || isa<StoreInst>(Val: I))
473 continue;
474
475 // Drop the use of AI in droppable instructions.
476 if (I->isDroppable()) {
477 I->dropDroppableUse(U);
478 continue;
479 }
480
481 if (!I->getType()->isVoidTy()) {
482 // The only users of this bitcast/GEP instruction are lifetime intrinsics.
483 // Follow the use/def chain to erase them now instead of leaving it for
484 // dead code elimination later.
485 for (Use &UU : llvm::make_early_inc_range(Range: I->uses())) {
486 Instruction *Inst = cast<Instruction>(Val: UU.getUser());
487
488 // Drop the use of I in droppable instructions.
489 if (Inst->isDroppable()) {
490 Inst->dropDroppableUse(U&: UU);
491 continue;
492 }
493 Inst->eraseFromParent();
494 }
495 }
496 I->eraseFromParent();
497 }
498}
499
500/// Rewrite as many loads as possible given a single store.
501///
502/// When there is only a single store, we can use the domtree to trivially
503/// replace all of the dominated loads with the stored value. Do so, and return
504/// true if this has successfully promoted the alloca entirely. If this returns
505/// false there were some loads which were not dominated by the single store
506/// and thus must be phi-ed with undef. We fall back to the standard alloca
507/// promotion algorithm in that case.
508static bool
509rewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info, LargeBlockInfo &LBI,
510 const DataLayout &DL, DominatorTree &DT,
511 AssumptionCache *AC,
512 SmallSet<DbgAssignIntrinsic *, 8> *DbgAssignsToDelete,
513 SmallSet<DbgVariableRecord *, 8> *DVRAssignsToDelete) {
514 StoreInst *OnlyStore = Info.OnlyStore;
515 bool StoringGlobalVal = !isa<Instruction>(Val: OnlyStore->getOperand(i_nocapture: 0));
516 BasicBlock *StoreBB = OnlyStore->getParent();
517 int StoreIndex = -1;
518
519 // Clear out UsingBlocks. We will reconstruct it here if needed.
520 Info.UsingBlocks.clear();
521
522 for (User *U : make_early_inc_range(Range: AI->users())) {
523 Instruction *UserInst = cast<Instruction>(Val: U);
524 if (UserInst == OnlyStore)
525 continue;
526 LoadInst *LI = cast<LoadInst>(Val: UserInst);
527
528 // Okay, if we have a load from the alloca, we want to replace it with the
529 // only value stored to the alloca. We can do this if the value is
530 // dominated by the store. If not, we use the rest of the mem2reg machinery
531 // to insert the phi nodes as needed.
532 if (!StoringGlobalVal) { // Non-instructions are always dominated.
533 if (LI->getParent() == StoreBB) {
534 // If we have a use that is in the same block as the store, compare the
535 // indices of the two instructions to see which one came first. If the
536 // load came before the store, we can't handle it.
537 if (StoreIndex == -1)
538 StoreIndex = LBI.getInstructionIndex(I: OnlyStore);
539
540 if (unsigned(StoreIndex) > LBI.getInstructionIndex(I: LI)) {
541 // Can't handle this load, bail out.
542 Info.UsingBlocks.push_back(Elt: StoreBB);
543 continue;
544 }
545 } else if (!DT.dominates(A: StoreBB, B: LI->getParent())) {
546 // If the load and store are in different blocks, use BB dominance to
547 // check their relationships. If the store doesn't dom the use, bail
548 // out.
549 Info.UsingBlocks.push_back(Elt: LI->getParent());
550 continue;
551 }
552 }
553
554 // Otherwise, we *can* safely rewrite this load.
555 Value *ReplVal = OnlyStore->getOperand(i_nocapture: 0);
556 // If the replacement value is the load, this must occur in unreachable
557 // code.
558 if (ReplVal == LI)
559 ReplVal = PoisonValue::get(T: LI->getType());
560
561 convertMetadataToAssumes(LI, Val: ReplVal, DL, AC, DT: &DT);
562 LI->replaceAllUsesWith(V: ReplVal);
563 LI->eraseFromParent();
564 LBI.deleteValue(I: LI);
565 }
566
567 // Finally, after the scan, check to see if the store is all that is left.
568 if (!Info.UsingBlocks.empty())
569 return false; // If not, we'll have to fall back for the remainder.
570
571 DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false);
572 // Update assignment tracking info for the store we're going to delete.
573 Info.AssignmentTracking.updateForDeletedStore(
574 ToDelete: Info.OnlyStore, DIB, DbgAssignsToDelete, DVRAssignsToDelete);
575
576 // Record debuginfo for the store and remove the declaration's
577 // debuginfo.
578 auto ConvertDebugInfoForStore = [&](auto &Container) {
579 for (auto *DbgItem : Container) {
580 if (DbgItem->isAddressOfVariable()) {
581 ConvertDebugDeclareToDebugValue(DbgItem, Info.OnlyStore, DIB);
582 DbgItem->eraseFromParent();
583 } else if (DbgItem->getExpression()->startsWithDeref()) {
584 DbgItem->eraseFromParent();
585 }
586 }
587 };
588 ConvertDebugInfoForStore(Info.DbgUsers);
589 ConvertDebugInfoForStore(Info.DPUsers);
590
591 // Remove dbg.assigns linked to the alloca as these are now redundant.
592 at::deleteAssignmentMarkers(Inst: AI);
593
594 // Remove the (now dead) store and alloca.
595 Info.OnlyStore->eraseFromParent();
596 LBI.deleteValue(I: Info.OnlyStore);
597
598 AI->eraseFromParent();
599 return true;
600}
601
602/// Many allocas are only used within a single basic block. If this is the
603/// case, avoid traversing the CFG and inserting a lot of potentially useless
604/// PHI nodes by just performing a single linear pass over the basic block
605/// using the Alloca.
606///
607/// If we cannot promote this alloca (because it is read before it is written),
608/// return false. This is necessary in cases where, due to control flow, the
609/// alloca is undefined only on some control flow paths. e.g. code like
610/// this is correct in LLVM IR:
611/// // A is an alloca with no stores so far
612/// for (...) {
613/// int t = *A;
614/// if (!first_iteration)
615/// use(t);
616/// *A = 42;
617/// }
618static bool
619promoteSingleBlockAlloca(AllocaInst *AI, const AllocaInfo &Info,
620 LargeBlockInfo &LBI, const DataLayout &DL,
621 DominatorTree &DT, AssumptionCache *AC,
622 SmallSet<DbgAssignIntrinsic *, 8> *DbgAssignsToDelete,
623 SmallSet<DbgVariableRecord *, 8> *DVRAssignsToDelete) {
624 // The trickiest case to handle is when we have large blocks. Because of this,
625 // this code is optimized assuming that large blocks happen. This does not
626 // significantly pessimize the small block case. This uses LargeBlockInfo to
627 // make it efficient to get the index of various operations in the block.
628
629 // Walk the use-def list of the alloca, getting the locations of all stores.
630 using StoresByIndexTy = SmallVector<std::pair<unsigned, StoreInst *>, 64>;
631 StoresByIndexTy StoresByIndex;
632
633 for (User *U : AI->users())
634 if (StoreInst *SI = dyn_cast<StoreInst>(Val: U))
635 StoresByIndex.push_back(Elt: std::make_pair(x: LBI.getInstructionIndex(I: SI), y&: SI));
636
637 // Sort the stores by their index, making it efficient to do a lookup with a
638 // binary search.
639 llvm::sort(C&: StoresByIndex, Comp: less_first());
640
641 // Walk all of the loads from this alloca, replacing them with the nearest
642 // store above them, if any.
643 for (User *U : make_early_inc_range(Range: AI->users())) {
644 LoadInst *LI = dyn_cast<LoadInst>(Val: U);
645 if (!LI)
646 continue;
647
648 unsigned LoadIdx = LBI.getInstructionIndex(I: LI);
649
650 // Find the nearest store that has a lower index than this load.
651 StoresByIndexTy::iterator I = llvm::lower_bound(
652 Range&: StoresByIndex,
653 Value: std::make_pair(x&: LoadIdx, y: static_cast<StoreInst *>(nullptr)),
654 C: less_first());
655 Value *ReplVal;
656 if (I == StoresByIndex.begin()) {
657 if (StoresByIndex.empty())
658 // If there are no stores, the load takes the undef value.
659 ReplVal = UndefValue::get(T: LI->getType());
660 else
661 // There is no store before this load, bail out (load may be affected
662 // by the following stores - see main comment).
663 return false;
664 } else {
665 // Otherwise, there was a store before this load, the load takes its
666 // value.
667 ReplVal = std::prev(x: I)->second->getOperand(i_nocapture: 0);
668 }
669
670 convertMetadataToAssumes(LI, Val: ReplVal, DL, AC, DT: &DT);
671
672 // If the replacement value is the load, this must occur in unreachable
673 // code.
674 if (ReplVal == LI)
675 ReplVal = PoisonValue::get(T: LI->getType());
676
677 LI->replaceAllUsesWith(V: ReplVal);
678 LI->eraseFromParent();
679 LBI.deleteValue(I: LI);
680 }
681
682 // Remove the (now dead) stores and alloca.
683 DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false);
684 while (!AI->use_empty()) {
685 StoreInst *SI = cast<StoreInst>(Val: AI->user_back());
686 // Update assignment tracking info for the store we're going to delete.
687 Info.AssignmentTracking.updateForDeletedStore(ToDelete: SI, DIB, DbgAssignsToDelete,
688 DVRAssignsToDelete);
689 // Record debuginfo for the store before removing it.
690 auto DbgUpdateForStore = [&](auto &Container) {
691 for (auto *DbgItem : Container) {
692 if (DbgItem->isAddressOfVariable()) {
693 ConvertDebugDeclareToDebugValue(DbgItem, SI, DIB);
694 }
695 }
696 };
697 DbgUpdateForStore(Info.DbgUsers);
698 DbgUpdateForStore(Info.DPUsers);
699
700 SI->eraseFromParent();
701 LBI.deleteValue(I: SI);
702 }
703
704 // Remove dbg.assigns linked to the alloca as these are now redundant.
705 at::deleteAssignmentMarkers(Inst: AI);
706 AI->eraseFromParent();
707
708 // The alloca's debuginfo can be removed as well.
709 auto DbgUpdateForAlloca = [&](auto &Container) {
710 for (auto *DbgItem : Container)
711 if (DbgItem->isAddressOfVariable() ||
712 DbgItem->getExpression()->startsWithDeref())
713 DbgItem->eraseFromParent();
714 };
715 DbgUpdateForAlloca(Info.DbgUsers);
716 DbgUpdateForAlloca(Info.DPUsers);
717
718 ++NumLocalPromoted;
719 return true;
720}
721
722void PromoteMem2Reg::run() {
723 Function &F = *DT.getRoot()->getParent();
724
725 AllocaDbgUsers.resize(N: Allocas.size());
726 AllocaATInfo.resize(N: Allocas.size());
727 AllocaDPUsers.resize(N: Allocas.size());
728
729 AllocaInfo Info;
730 LargeBlockInfo LBI;
731 ForwardIDFCalculator IDF(DT);
732
733 for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
734 AllocaInst *AI = Allocas[AllocaNum];
735
736 assert(isAllocaPromotable(AI) && "Cannot promote non-promotable alloca!");
737 assert(AI->getParent()->getParent() == &F &&
738 "All allocas should be in the same function, which is same as DF!");
739
740 removeIntrinsicUsers(AI);
741
742 if (AI->use_empty()) {
743 // If there are no uses of the alloca, just delete it now.
744 AI->eraseFromParent();
745
746 // Remove the alloca from the Allocas list, since it has been processed
747 RemoveFromAllocasList(AllocaIdx&: AllocaNum);
748 ++NumDeadAlloca;
749 continue;
750 }
751
752 // Calculate the set of read and write-locations for each alloca. This is
753 // analogous to finding the 'uses' and 'definitions' of each variable.
754 Info.AnalyzeAlloca(AI);
755
756 // If there is only a single store to this value, replace any loads of
757 // it that are directly dominated by the definition with the value stored.
758 if (Info.DefiningBlocks.size() == 1) {
759 if (rewriteSingleStoreAlloca(AI, Info, LBI, DL: SQ.DL, DT, AC,
760 DbgAssignsToDelete: &DbgAssignsToDelete, DVRAssignsToDelete: &DVRAssignsToDelete)) {
761 // The alloca has been processed, move on.
762 RemoveFromAllocasList(AllocaIdx&: AllocaNum);
763 ++NumSingleStore;
764 continue;
765 }
766 }
767
768 // If the alloca is only read and written in one basic block, just perform a
769 // linear sweep over the block to eliminate it.
770 if (Info.OnlyUsedInOneBlock &&
771 promoteSingleBlockAlloca(AI, Info, LBI, DL: SQ.DL, DT, AC,
772 DbgAssignsToDelete: &DbgAssignsToDelete, DVRAssignsToDelete: &DVRAssignsToDelete)) {
773 // The alloca has been processed, move on.
774 RemoveFromAllocasList(AllocaIdx&: AllocaNum);
775 continue;
776 }
777
778 // If we haven't computed a numbering for the BB's in the function, do so
779 // now.
780 if (BBNumbers.empty()) {
781 unsigned ID = 0;
782 for (auto &BB : F)
783 BBNumbers[&BB] = ID++;
784 }
785
786 // Remember the dbg.declare intrinsic describing this alloca, if any.
787 if (!Info.DbgUsers.empty())
788 AllocaDbgUsers[AllocaNum] = Info.DbgUsers;
789 if (!Info.AssignmentTracking.empty())
790 AllocaATInfo[AllocaNum] = Info.AssignmentTracking;
791 if (!Info.DPUsers.empty())
792 AllocaDPUsers[AllocaNum] = Info.DPUsers;
793
794 // Keep the reverse mapping of the 'Allocas' array for the rename pass.
795 AllocaLookup[Allocas[AllocaNum]] = AllocaNum;
796
797 // Unique the set of defining blocks for efficient lookup.
798 SmallPtrSet<BasicBlock *, 32> DefBlocks(Info.DefiningBlocks.begin(),
799 Info.DefiningBlocks.end());
800
801 // Determine which blocks the value is live in. These are blocks which lead
802 // to uses.
803 SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
804 ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
805
806 // At this point, we're committed to promoting the alloca using IDF's, and
807 // the standard SSA construction algorithm. Determine which blocks need phi
808 // nodes and see if we can optimize out some work by avoiding insertion of
809 // dead phi nodes.
810 IDF.setLiveInBlocks(LiveInBlocks);
811 IDF.setDefiningBlocks(DefBlocks);
812 SmallVector<BasicBlock *, 32> PHIBlocks;
813 IDF.calculate(IDFBlocks&: PHIBlocks);
814 llvm::sort(C&: PHIBlocks, Comp: [this](BasicBlock *A, BasicBlock *B) {
815 return BBNumbers.find(Val: A)->second < BBNumbers.find(Val: B)->second;
816 });
817
818 unsigned CurrentVersion = 0;
819 for (BasicBlock *BB : PHIBlocks)
820 QueuePhiNode(BB, AllocaIdx: AllocaNum, Version&: CurrentVersion);
821 }
822
823 if (Allocas.empty()) {
824 cleanUpDbgAssigns();
825 return; // All of the allocas must have been trivial!
826 }
827 LBI.clear();
828
829 // Set the incoming values for the basic block to be null values for all of
830 // the alloca's. We do this in case there is a load of a value that has not
831 // been stored yet. In this case, it will get this null value.
832 RenamePassData::ValVector Values(Allocas.size());
833 for (unsigned i = 0, e = Allocas.size(); i != e; ++i)
834 Values[i] = UndefValue::get(T: Allocas[i]->getAllocatedType());
835
836 // When handling debug info, treat all incoming values as if they have unknown
837 // locations until proven otherwise.
838 RenamePassData::LocationVector Locations(Allocas.size());
839
840 // Walks all basic blocks in the function performing the SSA rename algorithm
841 // and inserting the phi nodes we marked as necessary
842 std::vector<RenamePassData> RenamePassWorkList;
843 RenamePassWorkList.emplace_back(args: &F.front(), args: nullptr, args: std::move(Values),
844 args: std::move(Locations));
845 do {
846 RenamePassData RPD = std::move(RenamePassWorkList.back());
847 RenamePassWorkList.pop_back();
848 // RenamePass may add new worklist entries.
849 RenamePass(BB: RPD.BB, Pred: RPD.Pred, IncVals&: RPD.Values, IncLocs&: RPD.Locations, Worklist&: RenamePassWorkList);
850 } while (!RenamePassWorkList.empty());
851
852 // The renamer uses the Visited set to avoid infinite loops. Clear it now.
853 Visited.clear();
854
855 // Remove the allocas themselves from the function.
856 for (Instruction *A : Allocas) {
857 // Remove dbg.assigns linked to the alloca as these are now redundant.
858 at::deleteAssignmentMarkers(Inst: A);
859 // If there are any uses of the alloca instructions left, they must be in
860 // unreachable basic blocks that were not processed by walking the dominator
861 // tree. Just delete the users now.
862 if (!A->use_empty())
863 A->replaceAllUsesWith(V: PoisonValue::get(T: A->getType()));
864 A->eraseFromParent();
865 }
866
867 // Remove alloca's dbg.declare intrinsics from the function.
868 auto RemoveDbgDeclares = [&](auto &Container) {
869 for (auto &DbgUsers : Container) {
870 for (auto *DbgItem : DbgUsers)
871 if (DbgItem->isAddressOfVariable() ||
872 DbgItem->getExpression()->startsWithDeref())
873 DbgItem->eraseFromParent();
874 }
875 };
876 RemoveDbgDeclares(AllocaDbgUsers);
877 RemoveDbgDeclares(AllocaDPUsers);
878
879 // Loop over all of the PHI nodes and see if there are any that we can get
880 // rid of because they merge all of the same incoming values. This can
881 // happen due to undef values coming into the PHI nodes. This process is
882 // iterative, because eliminating one PHI node can cause others to be removed.
883 bool EliminatedAPHI = true;
884 while (EliminatedAPHI) {
885 EliminatedAPHI = false;
886
887 // Iterating over NewPhiNodes is deterministic, so it is safe to try to
888 // simplify and RAUW them as we go. If it was not, we could add uses to
889 // the values we replace with in a non-deterministic order, thus creating
890 // non-deterministic def->use chains.
891 for (DenseMap<std::pair<unsigned, unsigned>, PHINode *>::iterator
892 I = NewPhiNodes.begin(),
893 E = NewPhiNodes.end();
894 I != E;) {
895 PHINode *PN = I->second;
896
897 // If this PHI node merges one value and/or undefs, get the value.
898 if (Value *V = simplifyInstruction(I: PN, Q: SQ)) {
899 PN->replaceAllUsesWith(V);
900 PN->eraseFromParent();
901 NewPhiNodes.erase(I: I++);
902 EliminatedAPHI = true;
903 continue;
904 }
905 ++I;
906 }
907 }
908
909 // At this point, the renamer has added entries to PHI nodes for all reachable
910 // code. Unfortunately, there may be unreachable blocks which the renamer
911 // hasn't traversed. If this is the case, the PHI nodes may not
912 // have incoming values for all predecessors. Loop over all PHI nodes we have
913 // created, inserting poison values if they are missing any incoming values.
914 for (DenseMap<std::pair<unsigned, unsigned>, PHINode *>::iterator
915 I = NewPhiNodes.begin(),
916 E = NewPhiNodes.end();
917 I != E; ++I) {
918 // We want to do this once per basic block. As such, only process a block
919 // when we find the PHI that is the first entry in the block.
920 PHINode *SomePHI = I->second;
921 BasicBlock *BB = SomePHI->getParent();
922 if (&BB->front() != SomePHI)
923 continue;
924
925 // Only do work here if there the PHI nodes are missing incoming values. We
926 // know that all PHI nodes that were inserted in a block will have the same
927 // number of incoming values, so we can just check any of them.
928 if (SomePHI->getNumIncomingValues() == getNumPreds(BB))
929 continue;
930
931 // Get the preds for BB.
932 SmallVector<BasicBlock *, 16> Preds(predecessors(BB));
933
934 // Ok, now we know that all of the PHI nodes are missing entries for some
935 // basic blocks. Start by sorting the incoming predecessors for efficient
936 // access.
937 auto CompareBBNumbers = [this](BasicBlock *A, BasicBlock *B) {
938 return BBNumbers.find(Val: A)->second < BBNumbers.find(Val: B)->second;
939 };
940 llvm::sort(C&: Preds, Comp: CompareBBNumbers);
941
942 // Now we loop through all BB's which have entries in SomePHI and remove
943 // them from the Preds list.
944 for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) {
945 // Do a log(n) search of the Preds list for the entry we want.
946 SmallVectorImpl<BasicBlock *>::iterator EntIt = llvm::lower_bound(
947 Range&: Preds, Value: SomePHI->getIncomingBlock(i), C: CompareBBNumbers);
948 assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i) &&
949 "PHI node has entry for a block which is not a predecessor!");
950
951 // Remove the entry
952 Preds.erase(CI: EntIt);
953 }
954
955 // At this point, the blocks left in the preds list must have dummy
956 // entries inserted into every PHI nodes for the block. Update all the phi
957 // nodes in this block that we are inserting (there could be phis before
958 // mem2reg runs).
959 unsigned NumBadPreds = SomePHI->getNumIncomingValues();
960 BasicBlock::iterator BBI = BB->begin();
961 while ((SomePHI = dyn_cast<PHINode>(Val: BBI++)) &&
962 SomePHI->getNumIncomingValues() == NumBadPreds) {
963 Value *PoisonVal = PoisonValue::get(T: SomePHI->getType());
964 for (BasicBlock *Pred : Preds)
965 SomePHI->addIncoming(V: PoisonVal, BB: Pred);
966 }
967 }
968
969 NewPhiNodes.clear();
970 cleanUpDbgAssigns();
971}
972
973/// Determine which blocks the value is live in.
974///
975/// These are blocks which lead to uses. Knowing this allows us to avoid
976/// inserting PHI nodes into blocks which don't lead to uses (thus, the
977/// inserted phi nodes would be dead).
978void PromoteMem2Reg::ComputeLiveInBlocks(
979 AllocaInst *AI, AllocaInfo &Info,
980 const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
981 SmallPtrSetImpl<BasicBlock *> &LiveInBlocks) {
982 // To determine liveness, we must iterate through the predecessors of blocks
983 // where the def is live. Blocks are added to the worklist if we need to
984 // check their predecessors. Start with all the using blocks.
985 SmallVector<BasicBlock *, 64> LiveInBlockWorklist(Info.UsingBlocks.begin(),
986 Info.UsingBlocks.end());
987
988 // If any of the using blocks is also a definition block, check to see if the
989 // definition occurs before or after the use. If it happens before the use,
990 // the value isn't really live-in.
991 for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) {
992 BasicBlock *BB = LiveInBlockWorklist[i];
993 if (!DefBlocks.count(Ptr: BB))
994 continue;
995
996 // Okay, this is a block that both uses and defines the value. If the first
997 // reference to the alloca is a def (store), then we know it isn't live-in.
998 for (BasicBlock::iterator I = BB->begin();; ++I) {
999 if (StoreInst *SI = dyn_cast<StoreInst>(Val&: I)) {
1000 if (SI->getOperand(i_nocapture: 1) != AI)
1001 continue;
1002
1003 // We found a store to the alloca before a load. The alloca is not
1004 // actually live-in here.
1005 LiveInBlockWorklist[i] = LiveInBlockWorklist.back();
1006 LiveInBlockWorklist.pop_back();
1007 --i;
1008 --e;
1009 break;
1010 }
1011
1012 if (LoadInst *LI = dyn_cast<LoadInst>(Val&: I))
1013 // Okay, we found a load before a store to the alloca. It is actually
1014 // live into this block.
1015 if (LI->getOperand(i_nocapture: 0) == AI)
1016 break;
1017 }
1018 }
1019
1020 // Now that we have a set of blocks where the phi is live-in, recursively add
1021 // their predecessors until we find the full region the value is live.
1022 while (!LiveInBlockWorklist.empty()) {
1023 BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
1024
1025 // The block really is live in here, insert it into the set. If already in
1026 // the set, then it has already been processed.
1027 if (!LiveInBlocks.insert(Ptr: BB).second)
1028 continue;
1029
1030 // Since the value is live into BB, it is either defined in a predecessor or
1031 // live into it to. Add the preds to the worklist unless they are a
1032 // defining block.
1033 for (BasicBlock *P : predecessors(BB)) {
1034 // The value is not live into a predecessor if it defines the value.
1035 if (DefBlocks.count(Ptr: P))
1036 continue;
1037
1038 // Otherwise it is, add to the worklist.
1039 LiveInBlockWorklist.push_back(Elt: P);
1040 }
1041 }
1042}
1043
1044/// Queue a phi-node to be added to a basic-block for a specific Alloca.
1045///
1046/// Returns true if there wasn't already a phi-node for that variable
1047bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo,
1048 unsigned &Version) {
1049 // Look up the basic-block in question.
1050 PHINode *&PN = NewPhiNodes[std::make_pair(x&: BBNumbers[BB], y&: AllocaNo)];
1051
1052 // If the BB already has a phi node added for the i'th alloca then we're done!
1053 if (PN)
1054 return false;
1055
1056 // Create a PhiNode using the dereferenced type... and add the phi-node to the
1057 // BasicBlock.
1058 PN = PHINode::Create(Ty: Allocas[AllocaNo]->getAllocatedType(), NumReservedValues: getNumPreds(BB),
1059 NameStr: Allocas[AllocaNo]->getName() + "." + Twine(Version++));
1060 PN->insertBefore(InsertPos: BB->begin());
1061 ++NumPHIInsert;
1062 PhiToAllocaMap[PN] = AllocaNo;
1063 return true;
1064}
1065
1066/// Update the debug location of a phi. \p ApplyMergedLoc indicates whether to
1067/// create a merged location incorporating \p DL, or to set \p DL directly.
1068static void updateForIncomingValueLocation(PHINode *PN, DebugLoc DL,
1069 bool ApplyMergedLoc) {
1070 if (ApplyMergedLoc)
1071 PN->applyMergedLocation(LocA: PN->getDebugLoc(), LocB: DL);
1072 else
1073 PN->setDebugLoc(DL);
1074}
1075
1076/// Recursively traverse the CFG of the function, renaming loads and
1077/// stores to the allocas which we are promoting.
1078///
1079/// IncomingVals indicates what value each Alloca contains on exit from the
1080/// predecessor block Pred.
1081void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred,
1082 RenamePassData::ValVector &IncomingVals,
1083 RenamePassData::LocationVector &IncomingLocs,
1084 std::vector<RenamePassData> &Worklist) {
1085NextIteration:
1086 // If we are inserting any phi nodes into this BB, they will already be in the
1087 // block.
1088 if (PHINode *APN = dyn_cast<PHINode>(Val: BB->begin())) {
1089 // If we have PHI nodes to update, compute the number of edges from Pred to
1090 // BB.
1091 if (PhiToAllocaMap.count(Val: APN)) {
1092 // We want to be able to distinguish between PHI nodes being inserted by
1093 // this invocation of mem2reg from those phi nodes that already existed in
1094 // the IR before mem2reg was run. We determine that APN is being inserted
1095 // because it is missing incoming edges. All other PHI nodes being
1096 // inserted by this pass of mem2reg will have the same number of incoming
1097 // operands so far. Remember this count.
1098 unsigned NewPHINumOperands = APN->getNumOperands();
1099
1100 unsigned NumEdges = llvm::count(Range: successors(BB: Pred), Element: BB);
1101 assert(NumEdges && "Must be at least one edge from Pred to BB!");
1102
1103 // Add entries for all the phis.
1104 BasicBlock::iterator PNI = BB->begin();
1105 do {
1106 unsigned AllocaNo = PhiToAllocaMap[APN];
1107
1108 // Update the location of the phi node.
1109 updateForIncomingValueLocation(PN: APN, DL: IncomingLocs[AllocaNo],
1110 ApplyMergedLoc: APN->getNumIncomingValues() > 0);
1111
1112 // Add N incoming values to the PHI node.
1113 for (unsigned i = 0; i != NumEdges; ++i)
1114 APN->addIncoming(V: IncomingVals[AllocaNo], BB: Pred);
1115
1116 // The currently active variable for this block is now the PHI.
1117 IncomingVals[AllocaNo] = APN;
1118 AllocaATInfo[AllocaNo].updateForNewPhi(NewPhi: APN, DIB);
1119 auto ConvertDbgDeclares = [&](auto &Container) {
1120 for (auto *DbgItem : Container)
1121 if (DbgItem->isAddressOfVariable())
1122 ConvertDebugDeclareToDebugValue(DbgItem, APN, DIB);
1123 };
1124 ConvertDbgDeclares(AllocaDbgUsers[AllocaNo]);
1125 ConvertDbgDeclares(AllocaDPUsers[AllocaNo]);
1126
1127 // Get the next phi node.
1128 ++PNI;
1129 APN = dyn_cast<PHINode>(Val&: PNI);
1130 if (!APN)
1131 break;
1132
1133 // Verify that it is missing entries. If not, it is not being inserted
1134 // by this mem2reg invocation so we want to ignore it.
1135 } while (APN->getNumOperands() == NewPHINumOperands);
1136 }
1137 }
1138
1139 // Don't revisit blocks.
1140 if (!Visited.insert(Ptr: BB).second)
1141 return;
1142
1143 for (BasicBlock::iterator II = BB->begin(); !II->isTerminator();) {
1144 Instruction *I = &*II++; // get the instruction, increment iterator
1145
1146 if (LoadInst *LI = dyn_cast<LoadInst>(Val: I)) {
1147 AllocaInst *Src = dyn_cast<AllocaInst>(Val: LI->getPointerOperand());
1148 if (!Src)
1149 continue;
1150
1151 DenseMap<AllocaInst *, unsigned>::iterator AI = AllocaLookup.find(Val: Src);
1152 if (AI == AllocaLookup.end())
1153 continue;
1154
1155 Value *V = IncomingVals[AI->second];
1156 convertMetadataToAssumes(LI, Val: V, DL: SQ.DL, AC, DT: &DT);
1157
1158 // Anything using the load now uses the current value.
1159 LI->replaceAllUsesWith(V);
1160 LI->eraseFromParent();
1161 } else if (StoreInst *SI = dyn_cast<StoreInst>(Val: I)) {
1162 // Delete this instruction and mark the name as the current holder of the
1163 // value
1164 AllocaInst *Dest = dyn_cast<AllocaInst>(Val: SI->getPointerOperand());
1165 if (!Dest)
1166 continue;
1167
1168 DenseMap<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Val: Dest);
1169 if (ai == AllocaLookup.end())
1170 continue;
1171
1172 // what value were we writing?
1173 unsigned AllocaNo = ai->second;
1174 IncomingVals[AllocaNo] = SI->getOperand(i_nocapture: 0);
1175
1176 // Record debuginfo for the store before removing it.
1177 IncomingLocs[AllocaNo] = SI->getDebugLoc();
1178 AllocaATInfo[AllocaNo].updateForDeletedStore(ToDelete: SI, DIB, DbgAssignsToDelete: &DbgAssignsToDelete,
1179 DVRAssignsToDelete: &DVRAssignsToDelete);
1180 auto ConvertDbgDeclares = [&](auto &Container) {
1181 for (auto *DbgItem : Container)
1182 if (DbgItem->isAddressOfVariable())
1183 ConvertDebugDeclareToDebugValue(DbgItem, SI, DIB);
1184 };
1185 ConvertDbgDeclares(AllocaDbgUsers[ai->second]);
1186 ConvertDbgDeclares(AllocaDPUsers[ai->second]);
1187 SI->eraseFromParent();
1188 }
1189 }
1190
1191 // 'Recurse' to our successors.
1192 succ_iterator I = succ_begin(BB), E = succ_end(BB);
1193 if (I == E)
1194 return;
1195
1196 // Keep track of the successors so we don't visit the same successor twice
1197 SmallPtrSet<BasicBlock *, 8> VisitedSuccs;
1198
1199 // Handle the first successor without using the worklist.
1200 VisitedSuccs.insert(Ptr: *I);
1201 Pred = BB;
1202 BB = *I;
1203 ++I;
1204
1205 for (; I != E; ++I)
1206 if (VisitedSuccs.insert(Ptr: *I).second)
1207 Worklist.emplace_back(args: *I, args&: Pred, args&: IncomingVals, args&: IncomingLocs);
1208
1209 goto NextIteration;
1210}
1211
1212void llvm::PromoteMemToReg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
1213 AssumptionCache *AC) {
1214 // If there is nothing to do, bail out...
1215 if (Allocas.empty())
1216 return;
1217
1218 PromoteMem2Reg(Allocas, DT, AC).run();
1219}
1220

source code of llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp