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