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 auto 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 // Determine the type used by loads/stores on this alloca. Per
527 // isAllocaPromotable, all loads/stores must use the same type, and GEP/
528 // bitcast/addrspacecast derived pointers cannot have load/store users, so
529 // loads/stores are always direct users of the alloca.
530 Type *PromotedType = nullptr;
531 for (User *U : AI->users()) {
532 if (auto *LI = dyn_cast<LoadInst>(Val: U)) {
533 PromotedType = LI->getType();
534 break;
535 }
536 if (auto *SI = dyn_cast<StoreInst>(Val: U)) {
537 PromotedType = SI->getValueOperand()->getType();
538 break;
539 }
540 }
541
542 for (Use &U : llvm::make_early_inc_range(Range: AI->uses())) {
543 Instruction *I = cast<Instruction>(Val: U.getUser());
544 if (isa<LoadInst>(Val: I) || isa<StoreInst>(Val: I))
545 continue;
546
547 // Drop the use of AI in droppable instructions.
548 if (I->isDroppable()) {
549 I->dropDroppableUse(U);
550 continue;
551 }
552
553 if (!I->getType()->isVoidTy()) {
554 // Follow the use/def chain to erase users of this instruction now
555 // instead of leaving it for dead code elimination later.
556 for (Use &UU : llvm::make_early_inc_range(Range: I->uses())) {
557 Instruction *Inst = cast<Instruction>(Val: UU.getUser());
558
559 // Drop the use of I in droppable instructions.
560 if (Inst->isDroppable()) {
561 Inst->dropDroppableUse(U&: UU);
562 continue;
563 }
564
565 Inst->eraseFromParent();
566 }
567 }
568
569 // Same as above for lifetime intrinsics directly on the alloca. If the
570 // alloca has no load/store users, PromotedType is null and the alloca will
571 // be deleted as dead, so no store is needed.
572 if (PromotedType)
573 if (auto *II = dyn_cast<IntrinsicInst>(Val: I))
574 if (II->isLifetimeStartOrEnd()) {
575 auto *Store = new StoreInst(UndefValue::get(T: PromotedType), AI,
576 /*isVolatile=*/false, AI->getAlign(),
577 I->getIterator());
578 Store->setDebugLoc(II->getDebugLoc());
579 }
580
581 I->eraseFromParent();
582 }
583}
584
585/// Rewrite as many loads as possible given a single store.
586///
587/// When there is only a single store, we can use the domtree to trivially
588/// replace all of the dominated loads with the stored value. Do so, and return
589/// true if this has successfully promoted the alloca entirely. If this returns
590/// false there were some loads which were not dominated by the single store
591/// and thus must be phi-ed with undef. We fall back to the standard alloca
592/// promotion algorithm in that case.
593static bool rewriteSingleStoreAlloca(
594 AllocaInst *AI, AllocaInfo &Info, LargeBlockInfo &LBI, const DataLayout &DL,
595 DominatorTree &DT, AssumptionCache *AC,
596 SmallPtrSet<DbgVariableRecord *, 8> *DVRAssignsToDelete) {
597 StoreInst *OnlyStore = Info.OnlyStore;
598 Value *ReplVal = OnlyStore->getOperand(i_nocapture: 0);
599 // Loads may either load the stored value or uninitialized memory (undef).
600 // If the stored value may be poison, then replacing an uninitialized memory
601 // load with it would be incorrect. If the store dominates the load, we know
602 // it is always initialized.
603 bool RequireDominatingStore =
604 isa<Instruction>(Val: ReplVal) || !isGuaranteedNotToBePoison(V: ReplVal);
605 BasicBlock *StoreBB = OnlyStore->getParent();
606 int StoreIndex = -1;
607
608 // Clear out UsingBlocks. We will reconstruct it here if needed.
609 Info.UsingBlocks.clear();
610
611 for (User *U : make_early_inc_range(Range: AI->users())) {
612 Instruction *UserInst = cast<Instruction>(Val: U);
613 if (UserInst == OnlyStore)
614 continue;
615 LoadInst *LI = cast<LoadInst>(Val: UserInst);
616
617 // Okay, if we have a load from the alloca, we want to replace it with the
618 // only value stored to the alloca. We can do this if the value is
619 // dominated by the store. If not, we use the rest of the mem2reg machinery
620 // to insert the phi nodes as needed.
621 if (RequireDominatingStore) {
622 if (LI->getParent() == StoreBB) {
623 // If we have a use that is in the same block as the store, compare the
624 // indices of the two instructions to see which one came first. If the
625 // load came before the store, we can't handle it.
626 if (StoreIndex == -1)
627 StoreIndex = LBI.getInstructionIndex(I: OnlyStore);
628
629 if (unsigned(StoreIndex) > LBI.getInstructionIndex(I: LI)) {
630 // Can't handle this load, bail out.
631 Info.UsingBlocks.push_back(Elt: StoreBB);
632 continue;
633 }
634 } else if (!DT.dominates(A: StoreBB, B: LI->getParent())) {
635 // If the load and store are in different blocks, use BB dominance to
636 // check their relationships. If the store doesn't dom the use, bail
637 // out.
638 Info.UsingBlocks.push_back(Elt: LI->getParent());
639 continue;
640 }
641 }
642
643 // Otherwise, we *can* safely rewrite this load.
644 // If the replacement value is the load, this must occur in unreachable
645 // code.
646 if (ReplVal == LI)
647 ReplVal = PoisonValue::get(T: LI->getType());
648
649 convertMetadataToAssumes(LI, Val: ReplVal, DL, AC, DT: &DT);
650 LI->replaceAllUsesWith(V: ReplVal);
651 LI->eraseFromParent();
652 LBI.deleteValue(I: LI);
653 }
654
655 // Finally, after the scan, check to see if the store is all that is left.
656 if (!Info.UsingBlocks.empty())
657 return false; // If not, we'll have to fall back for the remainder.
658
659 DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false);
660 // Update assignment tracking info for the store we're going to delete.
661 Info.AssignmentTracking.updateForDeletedStore(ToDelete: Info.OnlyStore, DIB,
662 DVRAssignsToDelete);
663
664 // Record debuginfo for the store and remove the declaration's
665 // debuginfo.
666 for (DbgVariableRecord *DbgItem : Info.DPUsers) {
667 if (DbgItem->isAddressOfVariable()) {
668 ConvertDebugDeclareToDebugValue(DVR: DbgItem, SI: Info.OnlyStore, Builder&: DIB);
669 DbgItem->eraseFromParent();
670 } else if (DbgItem->isValueOfVariable() &&
671 DbgItem->getExpression()->startsWithDeref()) {
672 InsertDebugValueAtStoreLoc(DVR: DbgItem, SI: Info.OnlyStore, Builder&: DIB);
673 DbgItem->eraseFromParent();
674 } else if (DbgItem->getExpression()->startsWithDeref()) {
675 DbgItem->eraseFromParent();
676 }
677 }
678
679 // Remove dbg.assigns linked to the alloca as these are now redundant.
680 at::deleteAssignmentMarkers(Inst: AI);
681
682 // Remove the (now dead) store and alloca.
683 Info.OnlyStore->eraseFromParent();
684 LBI.deleteValue(I: Info.OnlyStore);
685
686 AI->eraseFromParent();
687 return true;
688}
689
690/// Many allocas are only used within a single basic block. If this is the
691/// case, avoid traversing the CFG and inserting a lot of potentially useless
692/// PHI nodes by just performing a single linear pass over the basic block
693/// using the Alloca.
694///
695/// If we cannot promote this alloca (because it is read before it is written),
696/// return false. This is necessary in cases where, due to control flow, the
697/// alloca is undefined only on some control flow paths. e.g. code like
698/// this is correct in LLVM IR:
699/// // A is an alloca with no stores so far
700/// for (...) {
701/// int t = *A;
702/// if (!first_iteration)
703/// use(t);
704/// *A = 42;
705/// }
706static bool promoteSingleBlockAlloca(
707 AllocaInst *AI, const AllocaInfo &Info, LargeBlockInfo &LBI,
708 const DataLayout &DL, DominatorTree &DT, AssumptionCache *AC,
709 SmallPtrSet<DbgVariableRecord *, 8> *DVRAssignsToDelete) {
710 // The trickiest case to handle is when we have large blocks. Because of this,
711 // this code is optimized assuming that large blocks happen. This does not
712 // significantly pessimize the small block case. This uses LargeBlockInfo to
713 // make it efficient to get the index of various operations in the block.
714
715 // Walk the use-def list of the alloca, getting the locations of all stores.
716 using StoresByIndexTy = SmallVector<std::pair<unsigned, StoreInst *>, 64>;
717 StoresByIndexTy StoresByIndex;
718
719 for (User *U : AI->users())
720 if (StoreInst *SI = dyn_cast<StoreInst>(Val: U))
721 StoresByIndex.push_back(Elt: std::make_pair(x: LBI.getInstructionIndex(I: SI), y&: SI));
722
723 // Sort the stores by their index, making it efficient to do a lookup with a
724 // binary search.
725 llvm::sort(C&: StoresByIndex, Comp: less_first());
726
727 // Walk all of the loads from this alloca, replacing them with the nearest
728 // store above them, if any.
729 for (User *U : make_early_inc_range(Range: AI->users())) {
730 LoadInst *LI = dyn_cast<LoadInst>(Val: U);
731 if (!LI)
732 continue;
733
734 unsigned LoadIdx = LBI.getInstructionIndex(I: LI);
735
736 // Find the nearest store that has a lower index than this load.
737 StoresByIndexTy::iterator I = llvm::lower_bound(
738 Range&: StoresByIndex,
739 Value: std::make_pair(x&: LoadIdx, y: static_cast<StoreInst *>(nullptr)),
740 C: less_first());
741 Value *ReplVal;
742 if (I == StoresByIndex.begin()) {
743 if (StoresByIndex.empty())
744 // If there are no stores, the load takes the undef value.
745 ReplVal = UndefValue::get(T: LI->getType());
746 else
747 // There is no store before this load, bail out (load may be affected
748 // by the following stores - see main comment).
749 return false;
750 } else {
751 // Otherwise, there was a store before this load, the load takes its
752 // value.
753 ReplVal = std::prev(x: I)->second->getOperand(i_nocapture: 0);
754 }
755
756 convertMetadataToAssumes(LI, Val: ReplVal, DL, AC, DT: &DT);
757
758 // If the replacement value is the load, this must occur in unreachable
759 // code.
760 if (ReplVal == LI)
761 ReplVal = PoisonValue::get(T: LI->getType());
762
763 LI->replaceAllUsesWith(V: ReplVal);
764 LI->eraseFromParent();
765 LBI.deleteValue(I: LI);
766 }
767
768 // Remove the (now dead) stores and alloca.
769 DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false);
770 while (!AI->use_empty()) {
771 StoreInst *SI = cast<StoreInst>(Val: AI->user_back());
772 // Update assignment tracking info for the store we're going to delete.
773 Info.AssignmentTracking.updateForDeletedStore(ToDelete: SI, DIB, DVRAssignsToDelete);
774 // Record debuginfo for the store before removing it.
775 for (DbgVariableRecord *DbgItem : Info.DPUsers) {
776 if (DbgItem->isAddressOfVariable()) {
777 ConvertDebugDeclareToDebugValue(DVR: DbgItem, SI, Builder&: DIB);
778 }
779 }
780
781 SI->eraseFromParent();
782 LBI.deleteValue(I: SI);
783 }
784
785 // Remove dbg.assigns linked to the alloca as these are now redundant.
786 at::deleteAssignmentMarkers(Inst: AI);
787 AI->eraseFromParent();
788
789 // The alloca's debuginfo can be removed as well.
790 for (DbgVariableRecord *DbgItem : Info.DPUsers) {
791 if (DbgItem->isAddressOfVariable() ||
792 DbgItem->getExpression()->startsWithDeref())
793 DbgItem->eraseFromParent();
794 }
795
796 ++NumLocalPromoted;
797 return true;
798}
799
800void PromoteMem2Reg::run() {
801 Function &F = *DT.getRoot()->getParent();
802
803 AllocaATInfo.resize(N: Allocas.size());
804 AllocaDPUsers.resize(N: Allocas.size());
805 AllocaValueTypes.resize(N: Allocas.size());
806
807 AllocaInfo Info;
808 LargeBlockInfo LBI;
809 ForwardIDFCalculator IDF(DT);
810
811 NoSignedZeros = F.getFnAttribute(Kind: "no-signed-zeros-fp-math").getValueAsBool();
812
813 // removeIntrinsicUsers inserts StoreInst(undef). A cache miss on
814 // LBI.getInstructionIndex lookup causes a full O(|BB|) basic block rescan.
815 // Doing all inserts in advance lets us capture all the new instructions in
816 // just a single rescan.
817 for (AllocaInst *AI : Allocas) {
818 assert(isAllocaPromotable(AI) && "Cannot promote non-promotable alloca!");
819 assert(AI->getParent()->getParent() == &F &&
820 "All allocas should be in the same function, which is same as DF!");
821 removeIntrinsicUsers(AI);
822 }
823
824 for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
825 AllocaInst *AI = Allocas[AllocaNum];
826
827 if (AI->use_empty()) {
828 // If there are no uses of the alloca, just delete it now.
829 AI->eraseFromParent();
830
831 // Remove the alloca from the Allocas list, since it has been processed
832 RemoveFromAllocasList(AllocaIdx&: AllocaNum);
833 ++NumDeadAlloca;
834 continue;
835 }
836
837 // Calculate the set of read and write-locations for each alloca. This is
838 // analogous to finding the 'uses' and 'definitions' of each variable.
839 Info.AnalyzeAlloca(AI);
840
841 // If there is only a single store to this value, replace any loads of
842 // it that are directly dominated by the definition with the value stored.
843 if (Info.DefiningBlocks.size() == 1) {
844 if (rewriteSingleStoreAlloca(AI, Info, LBI, DL: SQ.DL, DT, AC,
845 DVRAssignsToDelete: &DVRAssignsToDelete)) {
846 // The alloca has been processed, move on.
847 RemoveFromAllocasList(AllocaIdx&: AllocaNum);
848 ++NumSingleStore;
849 continue;
850 }
851 }
852
853 // If the alloca is only read and written in one basic block, just perform a
854 // linear sweep over the block to eliminate it.
855 if (Info.OnlyUsedInOneBlock &&
856 promoteSingleBlockAlloca(AI, Info, LBI, DL: SQ.DL, DT, AC,
857 DVRAssignsToDelete: &DVRAssignsToDelete)) {
858 // The alloca has been processed, move on.
859 RemoveFromAllocasList(AllocaIdx&: AllocaNum);
860 continue;
861 }
862
863 // Initialize BBNumPreds lazily
864 if (BBNumPreds.empty())
865 BBNumPreds.resize(N: F.getMaxBlockNumber());
866
867 // Remember the dbg.declare record describing this alloca, if any.
868 if (!Info.AssignmentTracking.empty())
869 AllocaATInfo[AllocaNum] = Info.AssignmentTracking;
870 if (!Info.DPUsers.empty())
871 AllocaDPUsers[AllocaNum] = Info.DPUsers;
872 AllocaValueTypes[AllocaNum] = Info.ValueType;
873
874 // Keep the reverse mapping of the 'Allocas' array for the rename pass.
875 AllocaLookup[Allocas[AllocaNum]] = AllocaNum;
876
877 // Unique the set of defining blocks for efficient lookup.
878 SmallPtrSet<BasicBlock *, 32> DefBlocks(llvm::from_range,
879 Info.DefiningBlocks);
880
881 // Determine which blocks the value is live in. These are blocks which lead
882 // to uses.
883 SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
884 ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
885
886 // At this point, we're committed to promoting the alloca using IDF's, and
887 // the standard SSA construction algorithm. Determine which blocks need phi
888 // nodes and see if we can optimize out some work by avoiding insertion of
889 // dead phi nodes.
890 IDF.setLiveInBlocks(LiveInBlocks);
891 IDF.setDefiningBlocks(DefBlocks);
892 SmallVector<BasicBlock *, 32> PHIBlocks;
893 IDF.calculate(IDFBlocks&: PHIBlocks);
894 llvm::sort(C&: PHIBlocks, Comp: [](BasicBlock *A, BasicBlock *B) {
895 return A->getNumber() < B->getNumber();
896 });
897
898 unsigned CurrentVersion = 0;
899 for (BasicBlock *BB : PHIBlocks)
900 QueuePhiNode(BB, AllocaIdx: AllocaNum, Version&: CurrentVersion);
901 }
902
903 if (Allocas.empty()) {
904 cleanUpDbgAssigns();
905 return; // All of the allocas must have been trivial!
906 }
907 LBI.clear();
908
909 // Set the incoming values for the basic block to be null values for all of
910 // the alloca's. We do this in case there is a load of a value that has not
911 // been stored yet. In this case, it will get this null value.
912 IncomingVals.resize(Sz: Allocas.size());
913 for (unsigned i = 0, e = Allocas.size(); i != e; ++i)
914 IncomingVals.init(Idx: i, Val: UndefValue::get(T: AllocaValueTypes[i]));
915
916 // When handling debug info, treat all incoming values as if they have
917 // compiler-generated (empty) locations, representing the uninitialized
918 // alloca, until proven otherwise.
919 IncomingLocs.resize(Sz: Allocas.size());
920 for (unsigned i = 0, e = Allocas.size(); i != e; ++i)
921 IncomingLocs.init(Idx: i, Val: DebugLoc::getCompilerGenerated());
922
923 // The renamer uses the Visited set to avoid infinite loops.
924 Visited.resize(N: F.getMaxBlockNumber(), t: false);
925
926 // Add the entry block to the worklist, with a null predecessor.
927 pushToWorklist(BB: &F.front(), Pred: nullptr);
928
929 do {
930 RenamePassData RPD = popFromWorklist();
931 RenamePass(BB: RPD.BB, Pred: RPD.Pred);
932 } while (!Worklist.empty());
933
934 // Remove the allocas themselves from the function.
935 for (Instruction *A : Allocas) {
936 // Remove dbg.assigns linked to the alloca as these are now redundant.
937 at::deleteAssignmentMarkers(Inst: A);
938 // If there are any uses of the alloca instructions left, they must be in
939 // unreachable basic blocks that were not processed by walking the dominator
940 // tree. Just delete the users now.
941 if (!A->use_empty())
942 A->replaceAllUsesWith(V: PoisonValue::get(T: A->getType()));
943 A->eraseFromParent();
944 }
945
946 // Remove alloca's dbg.declare intrinsics from the function.
947 for (auto &DbgUsers : AllocaDPUsers) {
948 for (DbgVariableRecord *DbgItem : DbgUsers)
949 if (DbgItem->isAddressOfVariable() ||
950 DbgItem->getExpression()->startsWithDeref())
951 DbgItem->eraseFromParent();
952 }
953
954 // Loop over all of the PHI nodes and see if there are any that we can get
955 // rid of because they merge all of the same incoming values. This can
956 // happen due to undef values coming into the PHI nodes. This process is
957 // iterative, because eliminating one PHI node can cause others to be removed.
958 bool EliminatedAPHI = true;
959 while (EliminatedAPHI) {
960 EliminatedAPHI = false;
961
962 // Iterating over NewPhiNodes is deterministic, so it is safe to try to
963 // simplify and RAUW them as we go. If it was not, we could add uses to
964 // the values we replace with in a non-deterministic order, thus creating
965 // non-deterministic def->use chains.
966 EliminatedAPHI = NewPhiNodes.remove_if(Pred: [&](const auto &Entry) {
967 PHINode *PN = Entry.second;
968 // If this PHI node merges one value and/or undefs, get the value.
969 if (Value *V = simplifyInstruction(I: PN, Q: SQ)) {
970 PN->replaceAllUsesWith(V);
971 PN->eraseFromParent();
972 return true;
973 }
974 return false;
975 });
976 }
977
978 // At this point, the renamer has added entries to PHI nodes for all reachable
979 // code. Unfortunately, there may be unreachable blocks which the renamer
980 // hasn't traversed. If this is the case, the PHI nodes may not
981 // have incoming values for all predecessors. Loop over all PHI nodes we have
982 // created, inserting poison values if they are missing any incoming values.
983 for (const auto &PhiNode : NewPhiNodes) {
984 // We want to do this once per basic block. As such, only process a block
985 // when we find the PHI that is the first entry in the block.
986 PHINode *SomePHI = PhiNode.second;
987 BasicBlock *BB = SomePHI->getParent();
988 if (&BB->front() != SomePHI)
989 continue;
990
991 // Only do work here if there the PHI nodes are missing incoming values. We
992 // know that all PHI nodes that were inserted in a block will have the same
993 // number of incoming values, so we can just check any of them.
994 if (SomePHI->getNumIncomingValues() == getNumPreds(BB))
995 continue;
996
997 // Get the preds for BB.
998 SmallVector<BasicBlock *, 16> Preds(predecessors(BB));
999
1000 // Ok, now we know that all of the PHI nodes are missing entries for some
1001 // basic blocks. Start by sorting the incoming predecessors for efficient
1002 // access.
1003 auto CompareBBNumbers = [](BasicBlock *A, BasicBlock *B) {
1004 return A->getNumber() < B->getNumber();
1005 };
1006 llvm::sort(C&: Preds, Comp: CompareBBNumbers);
1007
1008 // Now we loop through all BB's which have entries in SomePHI and remove
1009 // them from the Preds list.
1010 for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) {
1011 // Do a log(n) search of the Preds list for the entry we want.
1012 SmallVectorImpl<BasicBlock *>::iterator EntIt = llvm::lower_bound(
1013 Range&: Preds, Value: SomePHI->getIncomingBlock(i), C: CompareBBNumbers);
1014 assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i) &&
1015 "PHI node has entry for a block which is not a predecessor!");
1016
1017 // Remove the entry
1018 Preds.erase(CI: EntIt);
1019 }
1020
1021 // At this point, the blocks left in the preds list must have dummy
1022 // entries inserted into every PHI nodes for the block. Update all the phi
1023 // nodes in this block that we are inserting (there could be phis before
1024 // mem2reg runs).
1025 unsigned NumBadPreds = SomePHI->getNumIncomingValues();
1026 BasicBlock::iterator BBI = BB->begin();
1027 while ((SomePHI = dyn_cast<PHINode>(Val: BBI++)) &&
1028 SomePHI->getNumIncomingValues() == NumBadPreds) {
1029 Value *PoisonVal = PoisonValue::get(T: SomePHI->getType());
1030 for (BasicBlock *Pred : Preds)
1031 SomePHI->addIncoming(V: PoisonVal, BB: Pred);
1032 }
1033 }
1034
1035 NewPhiNodes.clear();
1036 cleanUpDbgAssigns();
1037}
1038
1039/// Determine which blocks the value is live in.
1040///
1041/// These are blocks which lead to uses. Knowing this allows us to avoid
1042/// inserting PHI nodes into blocks which don't lead to uses (thus, the
1043/// inserted phi nodes would be dead).
1044void PromoteMem2Reg::ComputeLiveInBlocks(
1045 AllocaInst *AI, AllocaInfo &Info,
1046 const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
1047 SmallPtrSetImpl<BasicBlock *> &LiveInBlocks) {
1048 // To determine liveness, we must iterate through the predecessors of blocks
1049 // where the def is live. Blocks are added to the worklist if we need to
1050 // check their predecessors. Start with all the using blocks.
1051 SmallVector<BasicBlock *, 64> LiveInBlockWorklist(Info.UsingBlocks.begin(),
1052 Info.UsingBlocks.end());
1053
1054 // If any of the using blocks is also a definition block, check to see if the
1055 // definition occurs before or after the use. If it happens before the use,
1056 // the value isn't really live-in.
1057 for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) {
1058 BasicBlock *BB = LiveInBlockWorklist[i];
1059 if (!DefBlocks.count(Ptr: BB))
1060 continue;
1061
1062 // Okay, this is a block that both uses and defines the value. If the first
1063 // reference to the alloca is a def (store), then we know it isn't live-in.
1064 for (BasicBlock::iterator I = BB->begin();; ++I) {
1065 if (StoreInst *SI = dyn_cast<StoreInst>(Val&: I)) {
1066 if (SI->getOperand(i_nocapture: 1) != AI)
1067 continue;
1068
1069 // We found a store to the alloca before a load. The alloca is not
1070 // actually live-in here.
1071 LiveInBlockWorklist[i] = LiveInBlockWorklist.back();
1072 LiveInBlockWorklist.pop_back();
1073 --i;
1074 --e;
1075 break;
1076 }
1077
1078 if (LoadInst *LI = dyn_cast<LoadInst>(Val&: I))
1079 // Okay, we found a load before a store to the alloca. It is actually
1080 // live into this block.
1081 if (LI->getOperand(i_nocapture: 0) == AI)
1082 break;
1083 }
1084 }
1085
1086 // Now that we have a set of blocks where the phi is live-in, recursively add
1087 // their predecessors until we find the full region the value is live.
1088 while (!LiveInBlockWorklist.empty()) {
1089 BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
1090
1091 // The block really is live in here, insert it into the set. If already in
1092 // the set, then it has already been processed.
1093 if (!LiveInBlocks.insert(Ptr: BB).second)
1094 continue;
1095
1096 // Since the value is live into BB, it is either defined in a predecessor or
1097 // live into it to. Add the preds to the worklist unless they are a
1098 // defining block.
1099 for (BasicBlock *P : predecessors(BB)) {
1100 // The value is not live into a predecessor if it defines the value.
1101 if (DefBlocks.count(Ptr: P))
1102 continue;
1103
1104 // Otherwise it is, add to the worklist.
1105 LiveInBlockWorklist.push_back(Elt: P);
1106 }
1107 }
1108}
1109
1110/// Queue a phi-node to be added to a basic-block for a specific Alloca.
1111///
1112/// Returns true if there wasn't already a phi-node for that variable
1113bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo,
1114 unsigned &Version) {
1115 // Look up the basic-block in question.
1116 PHINode *&PN = NewPhiNodes[std::make_pair(x: BB->getNumber(), y&: AllocaNo)];
1117
1118 // If the BB already has a phi node added for the i'th alloca then we're done!
1119 if (PN)
1120 return false;
1121
1122 // Create a PhiNode using the type from loads/stores... and add the phi-node
1123 // to the BasicBlock.
1124 PN = PHINode::Create(Ty: AllocaValueTypes[AllocaNo], NumReservedValues: getNumPreds(BB),
1125 NameStr: Allocas[AllocaNo]->getName() + "." + Twine(Version++));
1126 PN->insertBefore(InsertPos: BB->begin());
1127 ++NumPHIInsert;
1128 PhiToAllocaMap[PN] = AllocaNo;
1129 return true;
1130}
1131
1132/// Update the debug location of a phi. \p ApplyMergedLoc indicates whether to
1133/// create a merged location incorporating \p DL, or to set \p DL directly.
1134static void updateForIncomingValueLocation(PHINode *PN, DebugLoc DL,
1135 bool ApplyMergedLoc) {
1136 if (ApplyMergedLoc)
1137 PN->applyMergedLocation(LocA: PN->getDebugLoc(), LocB: DL);
1138 else
1139 PN->setDebugLoc(DL);
1140}
1141
1142/// Recursively traverse the CFG of the function, renaming loads and
1143/// stores to the allocas which we are promoting.
1144///
1145/// IncomingVals indicates what value each Alloca contains on exit from the
1146/// predecessor block Pred.
1147void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred) {
1148 // If we are inserting any phi nodes into this BB, they will already be in the
1149 // block.
1150 if (PHINode *APN = dyn_cast<PHINode>(Val: BB->begin())) {
1151 // If we have PHI nodes to update, compute the number of edges from Pred to
1152 // BB.
1153 if (PhiToAllocaMap.count(Val: APN)) {
1154 // We want to be able to distinguish between PHI nodes being inserted by
1155 // this invocation of mem2reg from those phi nodes that already existed in
1156 // the IR before mem2reg was run. We determine that APN is being inserted
1157 // because it is missing incoming edges. All other PHI nodes being
1158 // inserted by this pass of mem2reg will have the same number of incoming
1159 // operands so far. Remember this count.
1160 unsigned NewPHINumOperands = APN->getNumOperands();
1161
1162 unsigned NumEdges = llvm::count(Range: successors(BB: Pred), Element: BB);
1163 assert(NumEdges && "Must be at least one edge from Pred to BB!");
1164
1165 // Add entries for all the phis.
1166 BasicBlock::iterator PNI = BB->begin();
1167 do {
1168 unsigned AllocaNo = PhiToAllocaMap[APN];
1169
1170 // Update the location of the phi node.
1171 updateForIncomingValueLocation(PN: APN, DL: IncomingLocs[AllocaNo],
1172 ApplyMergedLoc: APN->getNumIncomingValues() > 0);
1173
1174 // Add N incoming values to the PHI node.
1175 for (unsigned i = 0; i != NumEdges; ++i)
1176 APN->addIncoming(V: IncomingVals[AllocaNo], BB: Pred);
1177
1178 // For the sequence `return X > 0.0 ? X : -X`, it is expected that this
1179 // results in fabs intrinsic. However, without no-signed-zeros(nsz) flag
1180 // on the phi node generated at this stage, fabs folding does not
1181 // happen. So, we try to infer nsz flag from the function attributes to
1182 // enable this fabs folding.
1183 if (isa<FPMathOperator>(Val: APN) && NoSignedZeros)
1184 APN->setHasNoSignedZeros(true);
1185
1186 // The currently active variable for this block is now the PHI.
1187 IncomingVals.set(Idx: AllocaNo, Val: APN);
1188 AllocaATInfo[AllocaNo].updateForNewPhi(NewPhi: APN, DIB);
1189 for (DbgVariableRecord *DbgItem : AllocaDPUsers[AllocaNo])
1190 if (DbgItem->isAddressOfVariable())
1191 ConvertDebugDeclareToDebugValue(DVR: DbgItem, LI: APN, Builder&: DIB);
1192
1193 // Get the next phi node.
1194 ++PNI;
1195 APN = dyn_cast<PHINode>(Val&: PNI);
1196 if (!APN)
1197 break;
1198
1199 // Verify that it is missing entries. If not, it is not being inserted
1200 // by this mem2reg invocation so we want to ignore it.
1201 } while (APN->getNumOperands() == NewPHINumOperands);
1202 }
1203 }
1204
1205 // Don't revisit blocks.
1206 if (Visited.test(Idx: BB->getNumber()))
1207 return;
1208 Visited.set(BB->getNumber());
1209
1210 for (BasicBlock::iterator II = BB->begin(); !II->isTerminator();) {
1211 Instruction *I = &*II++; // get the instruction, increment iterator
1212
1213 if (LoadInst *LI = dyn_cast<LoadInst>(Val: I)) {
1214 AllocaInst *Src = dyn_cast<AllocaInst>(Val: LI->getPointerOperand());
1215 if (!Src)
1216 continue;
1217
1218 auto AI = AllocaLookup.find(Val: Src);
1219 if (AI == AllocaLookup.end())
1220 continue;
1221
1222 Value *V = IncomingVals[AI->second];
1223 convertMetadataToAssumes(LI, Val: V, DL: SQ.DL, AC, DT: &DT);
1224
1225 // Anything using the load now uses the current value.
1226 LI->replaceAllUsesWith(V);
1227 LI->eraseFromParent();
1228 } else if (StoreInst *SI = dyn_cast<StoreInst>(Val: I)) {
1229 // Delete this instruction and mark the name as the current holder of the
1230 // value
1231 AllocaInst *Dest = dyn_cast<AllocaInst>(Val: SI->getPointerOperand());
1232 if (!Dest)
1233 continue;
1234
1235 auto ai = AllocaLookup.find(Val: Dest);
1236 if (ai == AllocaLookup.end())
1237 continue;
1238
1239 // what value were we writing?
1240 unsigned AllocaNo = ai->second;
1241 IncomingVals.set(Idx: AllocaNo, Val: SI->getOperand(i_nocapture: 0));
1242
1243 // Record debuginfo for the store before removing it.
1244 IncomingLocs.set(Idx: AllocaNo, Val: SI->getDebugLoc());
1245 AllocaATInfo[AllocaNo].updateForDeletedStore(ToDelete: SI, DIB,
1246 DVRAssignsToDelete: &DVRAssignsToDelete);
1247 for (DbgVariableRecord *DbgItem : AllocaDPUsers[ai->second])
1248 if (DbgItem->isAddressOfVariable())
1249 ConvertDebugDeclareToDebugValue(DVR: DbgItem, SI, Builder&: DIB);
1250 SI->eraseFromParent();
1251 }
1252 }
1253
1254 // 'Recurse' to our successors.
1255
1256 // Keep track of the successors so we don't visit the same successor twice
1257 SmallPtrSet<BasicBlock *, 8> VisitedSuccs;
1258
1259 for (BasicBlock *S : reverse(C: successors(BB)))
1260 if (VisitedSuccs.insert(Ptr: S).second)
1261 pushToWorklist(BB: S, Pred: BB);
1262}
1263
1264void llvm::PromoteMemToReg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
1265 AssumptionCache *AC) {
1266 // If there is nothing to do, bail out...
1267 if (Allocas.empty())
1268 return;
1269
1270 PromoteMem2Reg(Allocas, DT, AC).run();
1271}
1272