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 {
98 return false;
99 }
100 }
101
102 return true;
103}
104
105namespace {
106
107static void createDebugValue(DIBuilder &DIB, Value *NewValue,
108 DILocalVariable *Variable,
109 DIExpression *Expression, const DILocation *DI,
110 DbgVariableRecord *InsertBefore) {
111 // FIXME: Merge these two functions now that DIBuilder supports
112 // DbgVariableRecords. We neeed the API to accept DbgVariableRecords as an
113 // insert point for that to work.
114 (void)DIB;
115 DbgVariableRecord::createDbgVariableRecord(Location: NewValue, DV: Variable, Expr: Expression, DI,
116 InsertBefore&: *InsertBefore);
117}
118
119/// Helper for updating assignment tracking debug info when promoting allocas.
120class AssignmentTrackingInfo {
121 /// DbgAssignIntrinsics linked to the alloca with at most one per variable
122 /// fragment. (i.e. not be a comprehensive set if there are multiple
123 /// dbg.assigns for one variable fragment).
124 SmallVector<DbgVariableRecord *> DVRAssigns;
125
126public:
127 void init(AllocaInst *AI) {
128 SmallSet<DebugVariable, 2> Vars;
129 for (DbgVariableRecord *DVR : at::getDVRAssignmentMarkers(Inst: AI)) {
130 if (Vars.insert(V: DebugVariable(DVR)).second)
131 DVRAssigns.push_back(Elt: DVR);
132 }
133 }
134
135 /// Update assignment tracking debug info given for the to-be-deleted store
136 /// \p ToDelete that stores to this alloca.
137 void updateForDeletedStore(
138 StoreInst *ToDelete, DIBuilder &DIB,
139 SmallPtrSet<DbgVariableRecord *, 8> *DVRAssignsToDelete) const {
140 // There's nothing to do if the alloca doesn't have any variables using
141 // assignment tracking.
142 if (DVRAssigns.empty())
143 return;
144
145 // Insert a dbg.value where the linked dbg.assign is and remember to delete
146 // the dbg.assign later. Demoting to dbg.value isn't necessary for
147 // correctness but does reduce compile time and memory usage by reducing
148 // unnecessary function-local metadata. Remember that we've seen a
149 // dbg.assign for each variable fragment for the untracked store handling
150 // (after this loop).
151 SmallSet<DebugVariableAggregate, 2> VarHasDbgAssignForStore;
152 auto InsertValueForAssign = [&](auto *DbgAssign, auto *&AssignList) {
153 VarHasDbgAssignForStore.insert(V: DebugVariableAggregate(DbgAssign));
154 AssignList->insert(DbgAssign);
155 createDebugValue(DIB, DbgAssign->getValue(), DbgAssign->getVariable(),
156 DbgAssign->getExpression(), DbgAssign->getDebugLoc(),
157 DbgAssign);
158 };
159 for (auto *Assign : at::getDVRAssignmentMarkers(Inst: ToDelete))
160 InsertValueForAssign(Assign, DVRAssignsToDelete);
161
162 // It's possible for variables using assignment tracking to have no
163 // dbg.assign linked to this store. These are variables in DVRAssigns that
164 // are missing from VarHasDbgAssignForStore. Since there isn't a dbg.assign
165 // to mark the assignment - and the store is going to be deleted - insert a
166 // dbg.value to do that now. An untracked store may be either one that
167 // cannot be represented using assignment tracking (non-const offset or
168 // size) or one that is trackable but has had its DIAssignID attachment
169 // dropped accidentally.
170 auto ConvertUnlinkedAssignToValue = [&](DbgVariableRecord *Assign) {
171 if (VarHasDbgAssignForStore.contains(V: DebugVariableAggregate(Assign)))
172 return;
173 ConvertDebugDeclareToDebugValue(DVR: Assign, SI: ToDelete, Builder&: DIB);
174 };
175 for_each(Range: DVRAssigns, F: ConvertUnlinkedAssignToValue);
176 }
177
178 /// Update assignment tracking debug info given for the newly inserted PHI \p
179 /// NewPhi.
180 void updateForNewPhi(PHINode *NewPhi, DIBuilder &DIB) const {
181 // Regardless of the position of dbg.assigns relative to stores, the
182 // incoming values into a new PHI should be the same for the (imaginary)
183 // debug-phi.
184 for (auto *DVR : DVRAssigns)
185 ConvertDebugDeclareToDebugValue(DVR, LI: NewPhi, Builder&: DIB);
186 }
187
188 void clear() { DVRAssigns.clear(); }
189 bool empty() { return DVRAssigns.empty(); }
190};
191
192struct AllocaInfo {
193 using DPUserVec = SmallVector<DbgVariableRecord *, 1>;
194
195 SmallVector<BasicBlock *, 32> DefiningBlocks;
196 SmallVector<BasicBlock *, 32> UsingBlocks;
197
198 StoreInst *OnlyStore;
199 BasicBlock *OnlyBlock;
200 bool OnlyUsedInOneBlock;
201
202 /// The type used by all loads/stores of this alloca. This may differ from
203 /// the alloca's declared type if all accesses use a different type.
204 Type *ValueType;
205
206 /// Debug users of the alloca - does not include dbg.assign intrinsics.
207 DPUserVec DPUsers;
208 /// Helper to update assignment tracking debug info.
209 AssignmentTrackingInfo AssignmentTracking;
210
211 void clear() {
212 DefiningBlocks.clear();
213 UsingBlocks.clear();
214 OnlyStore = nullptr;
215 OnlyBlock = nullptr;
216 OnlyUsedInOneBlock = true;
217 ValueType = nullptr;
218 DPUsers.clear();
219 AssignmentTracking.clear();
220 }
221
222 /// Scan the uses of the specified alloca, filling in the AllocaInfo used
223 /// by the rest of the pass to reason about the uses of this alloca.
224 void AnalyzeAlloca(AllocaInst *AI) {
225 clear();
226
227 // As we scan the uses of the alloca instruction, keep track of stores,
228 // and decide whether all of the loads and stores to the alloca are within
229 // the same basic block.
230 for (User *U : AI->users()) {
231 Instruction *User = cast<Instruction>(Val: U);
232
233 if (StoreInst *SI = dyn_cast<StoreInst>(Val: User)) {
234 // Remember the basic blocks which define new values for the alloca
235 DefiningBlocks.push_back(Elt: SI->getParent());
236 OnlyStore = SI;
237 if (!ValueType)
238 ValueType = SI->getValueOperand()->getType();
239 else
240 assert(ValueType == SI->getValueOperand()->getType() &&
241 "All stores were checked to have used the same type");
242 } else {
243 LoadInst *LI = cast<LoadInst>(Val: User);
244 // Otherwise it must be a load instruction, keep track of variable
245 // reads.
246 UsingBlocks.push_back(Elt: LI->getParent());
247 if (!ValueType)
248 ValueType = LI->getType();
249 else
250 assert(ValueType == LI->getType() &&
251 "All loads where checked to have used the same type");
252 }
253
254 if (OnlyUsedInOneBlock) {
255 if (!OnlyBlock)
256 OnlyBlock = User->getParent();
257 else if (OnlyBlock != User->getParent())
258 OnlyUsedInOneBlock = false;
259 }
260 }
261 SmallVector<DbgVariableRecord *> AllDPUsers;
262 findDbgUsers(V: AI, DbgVariableRecords&: AllDPUsers);
263 std::copy_if(first: AllDPUsers.begin(), last: AllDPUsers.end(),
264 result: std::back_inserter(x&: DPUsers),
265 pred: [](DbgVariableRecord *DVR) { return !DVR->isDbgAssign(); });
266 AssignmentTracking.init(AI);
267 }
268};
269
270using DVRIndirectValuesAtStoreMap =
271 DenseMap<StoreInst *, SmallVector<DbgVariableRecord *, 1>>;
272using DVRIndirectValueLastStoreMap = DenseMap<DbgVariableRecord *, StoreInst *>;
273
274template <typename T> class VectorWithUndo {
275 SmallVector<T, 8> Vals;
276 SmallVector<std::pair<size_t, T>, 8> Undo;
277
278public:
279 void undo(size_t S) {
280 assert(S <= Undo.size());
281 while (S < Undo.size()) {
282 Vals[Undo.back().first] = Undo.back().second;
283 Undo.pop_back();
284 }
285 }
286
287 void resize(size_t Sz) { Vals.resize(Sz); }
288
289 size_t undoSize() const { return Undo.size(); }
290
291 const T &operator[](size_t Idx) const { return Vals[Idx]; }
292
293 void set(size_t Idx, const T &Val) {
294 if (Vals[Idx] == Val)
295 return;
296 Undo.emplace_back(Idx, Vals[Idx]);
297 Vals[Idx] = Val;
298 }
299
300 void init(size_t Idx, const T &Val) {
301 assert(Undo.empty());
302 Vals[Idx] = Val;
303 }
304};
305
306/// Data package used by RenamePass().
307struct RenamePassData {
308 RenamePassData(BasicBlock *B, BasicBlock *P, size_t V, size_t L)
309 : BB(B), Pred(P), UndoVals(V), UndoLocs(L) {}
310
311 BasicBlock *BB;
312 BasicBlock *Pred;
313
314 size_t UndoVals;
315 size_t UndoLocs;
316};
317
318/// This assigns and keeps a per-bb relative ordering of load/store
319/// instructions in the block that directly load or store an alloca.
320///
321/// This functionality is important because it avoids scanning large basic
322/// blocks multiple times when promoting many allocas in the same block.
323class LargeBlockInfo {
324 /// For each instruction that we track, keep the index of the
325 /// instruction.
326 ///
327 /// The index starts out as the number of the instruction from the start of
328 /// the block.
329 DenseMap<const Instruction *, unsigned> InstNumbers;
330
331public:
332
333 /// This code only looks at accesses to allocas.
334 static bool isInterestingInstruction(const Instruction *I) {
335 return (isa<LoadInst>(Val: I) && isa<AllocaInst>(Val: I->getOperand(i: 0))) ||
336 (isa<StoreInst>(Val: I) && isa<AllocaInst>(Val: I->getOperand(i: 1)));
337 }
338
339 /// Get or calculate the index of the specified instruction.
340 unsigned getInstructionIndex(const Instruction *I) {
341 assert(isInterestingInstruction(I) &&
342 "Not a load/store to/from an alloca?");
343
344 // If we already have this instruction number, return it.
345 auto It = InstNumbers.find(Val: I);
346 if (It != InstNumbers.end())
347 return It->second;
348
349 // Scan the whole block to get the instruction. This accumulates
350 // information for every interesting instruction in the block, in order to
351 // avoid gratuitus rescans.
352 const BasicBlock *BB = I->getParent();
353 unsigned InstNo = 0;
354 for (const Instruction &BBI : *BB)
355 if (isInterestingInstruction(I: &BBI))
356 InstNumbers[&BBI] = InstNo++;
357 It = InstNumbers.find(Val: I);
358
359 assert(It != InstNumbers.end() && "Didn't insert instruction?");
360 return It->second;
361 }
362
363 void deleteValue(const Instruction *I) { InstNumbers.erase(Val: I); }
364
365 void clear() { InstNumbers.clear(); }
366};
367
368struct PromoteMem2Reg {
369 /// The alloca instructions being promoted.
370 std::vector<AllocaInst *> Allocas;
371
372 DominatorTree &DT;
373 DIBuilder DIB;
374
375 /// A cache of @llvm.assume intrinsics used by SimplifyInstruction.
376 AssumptionCache *AC;
377
378 const SimplifyQuery SQ;
379
380 /// Reverse mapping of Allocas.
381 DenseMap<AllocaInst *, unsigned> AllocaLookup;
382
383 /// The PhiNodes we're adding.
384 ///
385 /// That map is used to simplify some Phi nodes as we iterate over it, so
386 /// it should have deterministic iterators. We could use a MapVector, but
387 /// since basic blocks have numbers, using these are more efficient.
388 DenseMap<std::pair<unsigned, unsigned>, PHINode *> NewPhiNodes;
389
390 /// For each PHI node, keep track of which entry in Allocas it corresponds
391 /// to.
392 DenseMap<PHINode *, unsigned> PhiToAllocaMap;
393
394 /// For each alloca, we keep track of the dbg.declare record that
395 /// describes it, if any, so that we can convert it to a dbg.value
396 /// record if the alloca gets promoted.
397 SmallVector<AllocaInfo::DPUserVec, 8> AllocaDPUsers;
398
399 /// For each alloca, keep an instance of a helper class that gives us an easy
400 /// way to update assignment tracking debug info if the alloca is promoted.
401 SmallVector<AssignmentTrackingInfo, 8> AllocaATInfo;
402 /// For each alloca, the type used by all loads/stores of this alloca.
403 SmallVector<Type *, 8> AllocaValueTypes;
404 /// A set of dbg.assigns to delete because they've been demoted to
405 /// dbg.values. Call cleanUpDbgAssigns to delete them.
406 SmallPtrSet<DbgVariableRecord *, 8> DVRAssignsToDelete;
407
408 /// For each store to an alloca, the #dbg_values with a deref alive there.
409 DVRIndirectValuesAtStoreMap DVRIndirectValuesAtStore;
410 /// For each #dbg_value with a deref, the last store to its alloca before it,
411 /// in its block.
412 DVRIndirectValueLastStoreMap DVRIndirectValueLastStore;
413
414 /// The set of basic blocks the renamer has already visited.
415 BitVector Visited;
416
417 /// Lazily compute the number of predecessors a block has, indexed by block
418 /// number.
419 SmallVector<unsigned> BBNumPreds;
420
421 /// The state of incoming values for the current DFS step.
422 VectorWithUndo<Value *> IncomingVals;
423
424 /// The state of incoming locations for the current DFS step.
425 VectorWithUndo<DebugLoc> IncomingLocs;
426
427 // DFS work stack.
428 SmallVector<RenamePassData, 8> Worklist;
429
430 /// Whether the function has the no-signed-zeros-fp-math attribute set.
431 bool NoSignedZeros = false;
432
433public:
434 PromoteMem2Reg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
435 AssumptionCache *AC)
436 : Allocas(Allocas.begin(), Allocas.end()), DT(DT),
437 DIB(*DT.getRoot()->getParent()->getParent(), /*AllowUnresolved*/ false),
438 AC(AC), SQ(DT.getRoot()->getDataLayout(),
439 nullptr, &DT, AC) {}
440
441 void run();
442
443private:
444 void RemoveFromAllocasList(unsigned &AllocaIdx) {
445 Allocas[AllocaIdx] = Allocas.back();
446 Allocas.pop_back();
447 --AllocaIdx;
448 }
449
450 unsigned getNumPreds(const BasicBlock *BB) {
451 // BBNumPreds is resized to getMaxBlockNumber() at the beginning.
452 unsigned &NP = BBNumPreds[BB->getNumber()];
453 if (NP == 0)
454 NP = pred_size(BB) + 1;
455 return NP - 1;
456 }
457
458 void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
459 const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
460 SmallPtrSetImpl<BasicBlock *> &LiveInBlocks);
461 void collectDVRIndirectValuesAtStores();
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 the alloca has no load/store users, PromotedType is null and the
554 // alloca will be deleted as dead, so no store is needed.
555 if (PromotedType)
556 if (auto *II = dyn_cast<IntrinsicInst>(Val: I))
557 if (II->isLifetimeStartOrEnd()) {
558 auto *Store = new StoreInst(UndefValue::get(T: PromotedType), AI,
559 /*isVolatile=*/false, AI->getAlign(),
560 I->getIterator());
561 Store->setDebugLoc(II->getDebugLoc());
562 }
563
564 I->eraseFromParent();
565 }
566}
567
568/// Rewrite as many loads as possible given a single store.
569///
570/// When there is only a single store, we can use the domtree to trivially
571/// replace all of the dominated loads with the stored value. Do so, and return
572/// true if this has successfully promoted the alloca entirely. If this returns
573/// false there were some loads which were not dominated by the single store
574/// and thus must be phi-ed with undef. We fall back to the standard alloca
575/// promotion algorithm in that case.
576static bool rewriteSingleStoreAlloca(
577 AllocaInst *AI, AllocaInfo &Info, LargeBlockInfo &LBI, const DataLayout &DL,
578 DominatorTree &DT, AssumptionCache *AC,
579 SmallPtrSet<DbgVariableRecord *, 8> *DVRAssignsToDelete) {
580 StoreInst *OnlyStore = Info.OnlyStore;
581 Value *ReplVal = OnlyStore->getOperand(i_nocapture: 0);
582 // Loads may either load the stored value or uninitialized memory (undef).
583 // If the stored value may be poison, then replacing an uninitialized memory
584 // load with it would be incorrect. If the store dominates the load, we know
585 // it is always initialized.
586 bool RequireDominatingStore =
587 isa<Instruction>(Val: ReplVal) || !isGuaranteedNotToBePoison(V: ReplVal);
588 BasicBlock *StoreBB = OnlyStore->getParent();
589 int StoreIndex = -1;
590
591 // Clear out UsingBlocks. We will reconstruct it here if needed.
592 Info.UsingBlocks.clear();
593
594 for (User *U : make_early_inc_range(Range: AI->users())) {
595 Instruction *UserInst = cast<Instruction>(Val: U);
596 if (UserInst == OnlyStore)
597 continue;
598 LoadInst *LI = cast<LoadInst>(Val: UserInst);
599
600 // Okay, if we have a load from the alloca, we want to replace it with the
601 // only value stored to the alloca. We can do this if the value is
602 // dominated by the store. If not, we use the rest of the mem2reg machinery
603 // to insert the phi nodes as needed.
604 if (RequireDominatingStore) {
605 if (LI->getParent() == StoreBB) {
606 // If we have a use that is in the same block as the store, compare the
607 // indices of the two instructions to see which one came first. If the
608 // load came before the store, we can't handle it.
609 if (StoreIndex == -1)
610 StoreIndex = LBI.getInstructionIndex(I: OnlyStore);
611
612 if (unsigned(StoreIndex) > LBI.getInstructionIndex(I: LI)) {
613 // Can't handle this load, bail out.
614 Info.UsingBlocks.push_back(Elt: StoreBB);
615 continue;
616 }
617 } else if (!DT.dominates(A: StoreBB, B: LI->getParent())) {
618 // If the load and store are in different blocks, use BB dominance to
619 // check their relationships. If the store doesn't dom the use, bail
620 // out.
621 Info.UsingBlocks.push_back(Elt: LI->getParent());
622 continue;
623 }
624 }
625
626 // Otherwise, we *can* safely rewrite this load.
627 // If the replacement value is the load, this must occur in unreachable
628 // code.
629 if (ReplVal == LI)
630 ReplVal = PoisonValue::get(T: LI->getType());
631
632 convertMetadataToAssumes(LI, Val: ReplVal, DL, AC, DT: &DT);
633 LI->replaceAllUsesWith(V: ReplVal);
634 LI->eraseFromParent();
635 LBI.deleteValue(I: LI);
636 }
637
638 // Finally, after the scan, check to see if the store is all that is left.
639 if (!Info.UsingBlocks.empty())
640 return false; // If not, we'll have to fall back for the remainder.
641
642 DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false);
643 // Update assignment tracking info for the store we're going to delete.
644 Info.AssignmentTracking.updateForDeletedStore(ToDelete: Info.OnlyStore, DIB,
645 DVRAssignsToDelete);
646
647 // Record debuginfo for the store and remove the declaration's
648 // debuginfo.
649 for (DbgVariableRecord *DbgItem : Info.DPUsers) {
650 if (DbgItem->isAddressOfVariable()) {
651 ConvertDebugDeclareToDebugValue(DVR: DbgItem, SI: Info.OnlyStore, Builder&: DIB);
652 DbgItem->eraseFromParent();
653 } else if (DbgItem->isValueOfVariable() &&
654 DbgItem->getExpression()->startsWithDeref()) {
655 InsertDebugValueAtStoreLoc(DVR: DbgItem, SI: Info.OnlyStore, Builder&: DIB);
656 DbgItem->eraseFromParent();
657 } else if (DbgItem->getExpression()->startsWithDeref()) {
658 DbgItem->eraseFromParent();
659 }
660 }
661
662 // Remove dbg.assigns linked to the alloca as these are now redundant.
663 at::deleteAssignmentMarkers(Inst: AI);
664
665 // Remove the (now dead) store and alloca.
666 Info.OnlyStore->eraseFromParent();
667 LBI.deleteValue(I: Info.OnlyStore);
668
669 AI->eraseFromParent();
670 return true;
671}
672
673/// Many allocas are only used within a single basic block. If this is the
674/// case, avoid traversing the CFG and inserting a lot of potentially useless
675/// PHI nodes by just performing a single linear pass over the basic block
676/// using the Alloca.
677///
678/// If we cannot promote this alloca (because it is read before it is written),
679/// return false. This is necessary in cases where, due to control flow, the
680/// alloca is undefined only on some control flow paths. e.g. code like
681/// this is correct in LLVM IR:
682/// // A is an alloca with no stores so far
683/// for (...) {
684/// int t = *A;
685/// if (!first_iteration)
686/// use(t);
687/// *A = 42;
688/// }
689static bool promoteSingleBlockAlloca(
690 AllocaInst *AI, const AllocaInfo &Info, LargeBlockInfo &LBI,
691 const DataLayout &DL, DominatorTree &DT, AssumptionCache *AC,
692 SmallPtrSet<DbgVariableRecord *, 8> *DVRAssignsToDelete,
693 const DVRIndirectValuesAtStoreMap &DVRIndirectValuesAtStore,
694 const DVRIndirectValueLastStoreMap &DVRIndirectValueLastStore) {
695 // The trickiest case to handle is when we have large blocks. Because of this,
696 // this code is optimized assuming that large blocks happen. This does not
697 // significantly pessimize the small block case. This uses LargeBlockInfo to
698 // make it efficient to get the index of various operations in the block.
699
700 // Walk the use-def list of the alloca, getting the locations of all stores.
701 using StoresByIndexTy = SmallVector<std::pair<unsigned, StoreInst *>, 64>;
702 StoresByIndexTy StoresByIndex;
703
704 for (User *U : AI->users())
705 if (StoreInst *SI = dyn_cast<StoreInst>(Val: U))
706 StoresByIndex.push_back(Elt: std::make_pair(x: LBI.getInstructionIndex(I: SI), y&: SI));
707
708 // Sort the stores by their index, making it efficient to do a lookup with a
709 // binary search.
710 llvm::sort(C&: StoresByIndex, Comp: less_first());
711
712 // Walk all of the loads from this alloca, replacing them with the nearest
713 // store above them, if any.
714 for (User *U : make_early_inc_range(Range: AI->users())) {
715 LoadInst *LI = dyn_cast<LoadInst>(Val: U);
716 if (!LI)
717 continue;
718
719 unsigned LoadIdx = LBI.getInstructionIndex(I: LI);
720
721 // Find the nearest store that has a lower index than this load.
722 StoresByIndexTy::iterator I = llvm::lower_bound(
723 Range&: StoresByIndex,
724 Value: std::make_pair(x&: LoadIdx, y: static_cast<StoreInst *>(nullptr)),
725 C: less_first());
726 Value *ReplVal;
727 if (I == StoresByIndex.begin()) {
728 if (StoresByIndex.empty())
729 // If there are no stores, the load takes the undef value.
730 ReplVal = UndefValue::get(T: LI->getType());
731 else
732 // There is no store before this load, bail out (load may be affected
733 // by the following stores - see main comment).
734 return false;
735 } else {
736 // Otherwise, there was a store before this load, the load takes its
737 // value.
738 ReplVal = std::prev(x: I)->second->getOperand(i_nocapture: 0);
739 }
740
741 convertMetadataToAssumes(LI, Val: ReplVal, DL, AC, DT: &DT);
742
743 // If the replacement value is the load, this must occur in unreachable
744 // code.
745 if (ReplVal == LI)
746 ReplVal = PoisonValue::get(T: LI->getType());
747
748 LI->replaceAllUsesWith(V: ReplVal);
749 LI->eraseFromParent();
750 LBI.deleteValue(I: LI);
751 }
752
753 // Each #dbg_value with a deref takes the value of the last store to the
754 // alloca, with its deref stripped.
755 SmallVector<std::pair<DbgVariableRecord *, Value *>, 1> DVRIndirectValues;
756 for (DbgVariableRecord *DbgItem : Info.DPUsers) {
757 if (!DbgItem->isDbgValue() || !DbgItem->getExpression()->startsWithDeref())
758 continue;
759
760 StoreInst *SI = DVRIndirectValueLastStore.lookup(Val: DbgItem);
761 // If there is no store to the alloca yet, or if the content is undef, the
762 // variable should keep its previous location.
763 Value *LastStoreValue = nullptr;
764 if (SI && (!isa<UndefValue>(Val: SI->getValueOperand()) ||
765 isa<PoisonValue>(Val: SI->getValueOperand()))) {
766 LastStoreValue = SI->getValueOperand();
767 }
768
769 // If the next instruction is a store, mark the record for removal to avoid
770 // a duplicate record, as the store will also create a record.
771 auto *Next = dyn_cast<StoreInst>(Val: DbgItem->getInstruction());
772 if (Next && Next->getPointerOperand() == AI) {
773 LastStoreValue = nullptr;
774 }
775 DVRIndirectValues.push_back(Elt: {DbgItem, LastStoreValue});
776 }
777
778 // Remove the (now dead) stores and alloca.
779 DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false);
780 while (!AI->use_empty()) {
781 StoreInst *SI = cast<StoreInst>(Val: AI->user_back());
782 // Update assignment tracking info for the store we're going to delete.
783 Info.AssignmentTracking.updateForDeletedStore(ToDelete: SI, DIB, DVRAssignsToDelete);
784 // Record debuginfo for the store before removing it.
785 for (DbgVariableRecord *DbgItem : Info.DPUsers) {
786 if (DbgItem->isAddressOfVariable()) {
787 ConvertDebugDeclareToDebugValue(DVR: DbgItem, SI, Builder&: DIB);
788 } else if (DbgItem->isDbgDeclareValue() &&
789 DbgItem->getExpression()->startsWithDeref()) {
790 // A #dbg_declare_value is converted to a #dbg_value at each store,
791 // with its deref stripped.
792 InsertDebugValueAtStoreLoc(DVR: DbgItem, SI, Builder&: DIB);
793 }
794 }
795 // Each live #dbg_value is cloned at each store with its deref stripped.
796 for (DbgVariableRecord *DbgItem : DVRIndirectValuesAtStore.lookup(Val: SI))
797 InsertDebugValueAtStoreLoc(DVR: DbgItem, SI, Builder&: DIB);
798
799 SI->eraseFromParent();
800 LBI.deleteValue(I: SI);
801 }
802
803 // Remove dbg.assigns linked to the alloca as these are now redundant.
804 at::deleteAssignmentMarkers(Inst: AI);
805 AI->eraseFromParent();
806
807 // The alloca's #dbg_declare records have been rewritten and can be deleted.
808 for (DbgVariableRecord *DbgItem : Info.DPUsers) {
809 if (DbgItem->isAddressOfVariable() ||
810 (DbgItem->isDbgDeclareValue() &&
811 DbgItem->getExpression()->startsWithDeref()))
812 DbgItem->eraseFromParent();
813 }
814 // Indirect #dbg_value records are rewritten to use the last store to the
815 // alloca, or removed if there is none.
816 for (auto [DbgItem, V] : DVRIndirectValues) {
817 if (!V) {
818 DbgItem->eraseFromParent();
819 continue;
820 }
821 DbgItem->setRawLocation(ValueAsMetadata::get(V));
822 DbgItem->setExpression(DIExpression::get(
823 Context&: V->getContext(), Elements: DbgItem->getExpression()
824 ->getSingleLocationExpressionElements()
825 ->drop_front()));
826 }
827
828 ++NumLocalPromoted;
829 return true;
830}
831
832/// Collect which records are valid at each store, and which store reaches each
833/// record, walking each block once for all allocas.
834void PromoteMem2Reg::collectDVRIndirectValuesAtStores() {
835 // A #dbg_value with a deref can be cloned and rewritten at each store.
836 // Any other kind is left to be poisoned.
837 SmallPtrSet<DbgVariableRecord *, 8> DVRIndirectValues;
838 SmallSetVector<BasicBlock *, 4> BlocksToProcess;
839 for (AllocaInst *AI : Allocas)
840 for (DbgVariableRecord *DVR : findDVRValues(V: AI))
841 if (DVR->isDbgValue() && DVR->getExpression()->startsWithDeref()) {
842 DVRIndirectValues.insert(Ptr: DVR);
843 BlocksToProcess.insert(X: DVR->getParent());
844 }
845
846 // Only promoteSingleBlockAlloca is supported, so each block is processed
847 // individually.
848 for (BasicBlock *BB : BlocksToProcess) {
849 // The records alive at this point, for each variable. There can be
850 // multiple if there are fragments.
851 SmallDenseMap<DebugVariableAggregate, SmallVector<DbgVariableRecord *, 1>>
852 LiveByVar;
853 // The records alive at this point, whose value use the alloca.
854 SmallDenseMap<Value *, SmallVector<DbgVariableRecord *, 1>> LiveByAlloca;
855 // The last store to each alloca before this point.
856 SmallDenseMap<Value *, StoreInst *> LastStore;
857 for (Instruction &I : *BB) {
858 for (DbgVariableRecord &DVR : filterDbgVars(R: I.getDbgRecordRange())) {
859 // Only #dbg_values have a meaningful location.
860 if (!DVR.isDbgValue())
861 continue;
862 // Any overlapping previous record is no longer live.
863 auto &Live = LiveByVar[DebugVariableAggregate(&DVR)];
864 erase_if(C&: Live, P: [&](DbgVariableRecord *L) {
865 if (!L->getExpression()->fragmentsOverlap(Other: DVR.getExpression()))
866 return false;
867 erase(C&: LiveByAlloca[L->getVariableLocationOp(OpIdx: 0)], V: L);
868 return true;
869 });
870 // If this is one of our indirect records, mark it live.
871 if (DVRIndirectValues.contains(Ptr: &DVR)) {
872 Live.push_back(Elt: &DVR);
873 Value *Ptr = DVR.getVariableLocationOp(OpIdx: 0);
874 LiveByAlloca[Ptr].push_back(Elt: &DVR);
875 if (StoreInst *SI = LastStore.lookup(Val: Ptr))
876 DVRIndirectValueLastStore[&DVR] = SI;
877 }
878 }
879 // Save the records alive at this point.
880 auto *SI = dyn_cast<StoreInst>(Val: &I);
881 if (!SI)
882 continue;
883 LastStore[SI->getPointerOperand()] = SI;
884 // Copy the list of live records into the map, if it was tracked.
885 auto Live = LiveByAlloca.lookup(Val: SI->getPointerOperand());
886 if (!Live.empty())
887 DVRIndirectValuesAtStore[SI] = std::move(Live);
888 }
889 }
890}
891
892void PromoteMem2Reg::run() {
893 Function &F = *DT.getRoot()->getParent();
894
895 AllocaATInfo.resize(N: Allocas.size());
896 AllocaDPUsers.resize(N: Allocas.size());
897 AllocaValueTypes.resize(N: Allocas.size());
898
899 AllocaInfo Info;
900 LargeBlockInfo LBI;
901 ForwardIDFCalculator IDF(DT);
902
903 NoSignedZeros = F.getFnAttribute(Kind: "no-signed-zeros-fp-math").getValueAsBool();
904
905 // removeIntrinsicUsers inserts StoreInst(undef). A cache miss on
906 // LBI.getInstructionIndex lookup causes a full O(|BB|) basic block rescan.
907 // Doing all inserts in advance lets us capture all the new instructions in
908 // just a single rescan.
909 for (AllocaInst *AI : Allocas) {
910 assert(isAllocaPromotable(AI) && "Cannot promote non-promotable alloca!");
911 assert(AI->getParent()->getParent() == &F &&
912 "All allocas should be in the same function, which is same as DF!");
913 removeIntrinsicUsers(AI);
914 }
915
916 collectDVRIndirectValuesAtStores();
917
918 for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
919 AllocaInst *AI = Allocas[AllocaNum];
920
921 if (AI->use_empty()) {
922 // If there are no uses of the alloca, just delete it now.
923 AI->eraseFromParent();
924
925 // Remove the alloca from the Allocas list, since it has been processed
926 RemoveFromAllocasList(AllocaIdx&: AllocaNum);
927 ++NumDeadAlloca;
928 continue;
929 }
930
931 // Calculate the set of read and write-locations for each alloca. This is
932 // analogous to finding the 'uses' and 'definitions' of each variable.
933 Info.AnalyzeAlloca(AI);
934
935 // If there is only a single store to this value, replace any loads of
936 // it that are directly dominated by the definition with the value stored.
937 if (Info.DefiningBlocks.size() == 1) {
938 if (rewriteSingleStoreAlloca(AI, Info, LBI, DL: SQ.DL, DT, AC,
939 DVRAssignsToDelete: &DVRAssignsToDelete)) {
940 // The alloca has been processed, move on.
941 RemoveFromAllocasList(AllocaIdx&: AllocaNum);
942 ++NumSingleStore;
943 continue;
944 }
945 }
946
947 // If the alloca is only read and written in one basic block, just perform a
948 // linear sweep over the block to eliminate it.
949 if (Info.OnlyUsedInOneBlock &&
950 promoteSingleBlockAlloca(AI, Info, LBI, DL: SQ.DL, DT, AC,
951 DVRAssignsToDelete: &DVRAssignsToDelete, DVRIndirectValuesAtStore,
952 DVRIndirectValueLastStore)) {
953 // The alloca has been processed, move on.
954 RemoveFromAllocasList(AllocaIdx&: AllocaNum);
955 continue;
956 }
957
958 // Initialize BBNumPreds lazily
959 if (BBNumPreds.empty())
960 BBNumPreds.resize(N: F.getMaxBlockNumber());
961
962 // Remember the dbg.declare record describing this alloca, if any.
963 if (!Info.AssignmentTracking.empty())
964 AllocaATInfo[AllocaNum] = Info.AssignmentTracking;
965 if (!Info.DPUsers.empty())
966 AllocaDPUsers[AllocaNum] = Info.DPUsers;
967 AllocaValueTypes[AllocaNum] = Info.ValueType;
968
969 // Keep the reverse mapping of the 'Allocas' array for the rename pass.
970 AllocaLookup[Allocas[AllocaNum]] = AllocaNum;
971
972 // Unique the set of defining blocks for efficient lookup.
973 SmallPtrSet<BasicBlock *, 32> DefBlocks(llvm::from_range,
974 Info.DefiningBlocks);
975
976 // Determine which blocks the value is live in. These are blocks which lead
977 // to uses.
978 SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
979 ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
980
981 // At this point, we're committed to promoting the alloca using IDF's, and
982 // the standard SSA construction algorithm. Determine which blocks need phi
983 // nodes and see if we can optimize out some work by avoiding insertion of
984 // dead phi nodes.
985 IDF.setLiveInBlocks(LiveInBlocks);
986 IDF.setDefiningBlocks(DefBlocks);
987 SmallVector<BasicBlock *, 32> PHIBlocks;
988 IDF.calculate(IDFBlocks&: PHIBlocks);
989 llvm::sort(C&: PHIBlocks, Comp: [](BasicBlock *A, BasicBlock *B) {
990 return A->getNumber() < B->getNumber();
991 });
992
993 unsigned CurrentVersion = 0;
994 for (BasicBlock *BB : PHIBlocks)
995 QueuePhiNode(BB, AllocaIdx: AllocaNum, Version&: CurrentVersion);
996 }
997
998 if (Allocas.empty()) {
999 cleanUpDbgAssigns();
1000 return; // All of the allocas must have been trivial!
1001 }
1002 LBI.clear();
1003
1004 // Set the incoming values for the basic block to be null values for all of
1005 // the alloca's. We do this in case there is a load of a value that has not
1006 // been stored yet. In this case, it will get this null value.
1007 IncomingVals.resize(Sz: Allocas.size());
1008 for (unsigned i = 0, e = Allocas.size(); i != e; ++i)
1009 IncomingVals.init(Idx: i, Val: UndefValue::get(T: AllocaValueTypes[i]));
1010
1011 // When handling debug info, treat all incoming values as if they have
1012 // compiler-generated (empty) locations, representing the uninitialized
1013 // alloca, until proven otherwise.
1014 IncomingLocs.resize(Sz: Allocas.size());
1015 for (unsigned i = 0, e = Allocas.size(); i != e; ++i)
1016 IncomingLocs.init(Idx: i, Val: DebugLoc::getCompilerGenerated());
1017
1018 // The renamer uses the Visited set to avoid infinite loops.
1019 Visited.resize(N: F.getMaxBlockNumber(), t: false);
1020
1021 // Add the entry block to the worklist, with a null predecessor.
1022 pushToWorklist(BB: &F.front(), Pred: nullptr);
1023
1024 do {
1025 RenamePassData RPD = popFromWorklist();
1026 RenamePass(BB: RPD.BB, Pred: RPD.Pred);
1027 } while (!Worklist.empty());
1028
1029 // Remove the allocas themselves from the function.
1030 for (Instruction *A : Allocas) {
1031 // Remove dbg.assigns linked to the alloca as these are now redundant.
1032 at::deleteAssignmentMarkers(Inst: A);
1033 // If there are any uses of the alloca instructions left, they must be in
1034 // unreachable basic blocks that were not processed by walking the dominator
1035 // tree. Just delete the users now.
1036 if (!A->use_empty())
1037 A->replaceAllUsesWith(V: PoisonValue::get(T: A->getType()));
1038 A->eraseFromParent();
1039 }
1040
1041 // Remove alloca's dbg.declare intrinsics from the function.
1042 for (auto &DbgUsers : AllocaDPUsers) {
1043 for (DbgVariableRecord *DbgItem : DbgUsers)
1044 if (DbgItem->isAddressOfVariable() ||
1045 DbgItem->getExpression()->startsWithDeref())
1046 DbgItem->eraseFromParent();
1047 }
1048
1049 // Loop over all of the PHI nodes and see if there are any that we can get
1050 // rid of because they merge all of the same incoming values. This can
1051 // happen due to undef values coming into the PHI nodes. This process is
1052 // iterative, because eliminating one PHI node can cause others to be removed.
1053 bool EliminatedAPHI = true;
1054 while (EliminatedAPHI) {
1055 EliminatedAPHI = false;
1056
1057 // Iterating over NewPhiNodes is deterministic, so it is safe to try to
1058 // simplify and RAUW them as we go. If it was not, we could add uses to
1059 // the values we replace with in a non-deterministic order, thus creating
1060 // non-deterministic def->use chains.
1061 EliminatedAPHI = NewPhiNodes.remove_if(Pred: [&](const auto &Entry) {
1062 PHINode *PN = Entry.second;
1063 // If this PHI node merges one value and/or undefs, get the value.
1064 if (Value *V = simplifyInstruction(I: PN, Q: SQ)) {
1065 PN->replaceAllUsesWith(V);
1066 PN->eraseFromParent();
1067 return true;
1068 }
1069 return false;
1070 });
1071 }
1072
1073 // At this point, the renamer has added entries to PHI nodes for all reachable
1074 // code. Unfortunately, there may be unreachable blocks which the renamer
1075 // hasn't traversed. If this is the case, the PHI nodes may not
1076 // have incoming values for all predecessors. Loop over all PHI nodes we have
1077 // created, inserting poison values if they are missing any incoming values.
1078 for (const auto &PhiNode : NewPhiNodes) {
1079 // We want to do this once per basic block. As such, only process a block
1080 // when we find the PHI that is the first entry in the block.
1081 PHINode *SomePHI = PhiNode.second;
1082 BasicBlock *BB = SomePHI->getParent();
1083 if (&BB->front() != SomePHI)
1084 continue;
1085
1086 // Only do work here if there the PHI nodes are missing incoming values. We
1087 // know that all PHI nodes that were inserted in a block will have the same
1088 // number of incoming values, so we can just check any of them.
1089 if (SomePHI->getNumIncomingValues() == getNumPreds(BB))
1090 continue;
1091
1092 // Get the preds for BB.
1093 SmallVector<BasicBlock *, 16> Preds(predecessors(BB));
1094
1095 // Ok, now we know that all of the PHI nodes are missing entries for some
1096 // basic blocks. Start by sorting the incoming predecessors for efficient
1097 // access.
1098 auto CompareBBNumbers = [](BasicBlock *A, BasicBlock *B) {
1099 return A->getNumber() < B->getNumber();
1100 };
1101 llvm::sort(C&: Preds, Comp: CompareBBNumbers);
1102
1103 // Now we loop through all BB's which have entries in SomePHI and remove
1104 // them from the Preds list.
1105 for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) {
1106 // Do a log(n) search of the Preds list for the entry we want.
1107 SmallVectorImpl<BasicBlock *>::iterator EntIt = llvm::lower_bound(
1108 Range&: Preds, Value: SomePHI->getIncomingBlock(i), C: CompareBBNumbers);
1109 assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i) &&
1110 "PHI node has entry for a block which is not a predecessor!");
1111
1112 // Remove the entry
1113 Preds.erase(CI: EntIt);
1114 }
1115
1116 // At this point, the blocks left in the preds list must have dummy
1117 // entries inserted into every PHI nodes for the block. Update all the phi
1118 // nodes in this block that we are inserting (there could be phis before
1119 // mem2reg runs).
1120 unsigned NumBadPreds = SomePHI->getNumIncomingValues();
1121 BasicBlock::iterator BBI = BB->begin();
1122 while ((SomePHI = dyn_cast<PHINode>(Val: BBI++)) &&
1123 SomePHI->getNumIncomingValues() == NumBadPreds) {
1124 Value *PoisonVal = PoisonValue::get(T: SomePHI->getType());
1125 for (BasicBlock *Pred : Preds)
1126 SomePHI->addIncoming(V: PoisonVal, BB: Pred);
1127 }
1128 }
1129
1130 NewPhiNodes.clear();
1131 cleanUpDbgAssigns();
1132}
1133
1134/// Determine which blocks the value is live in.
1135///
1136/// These are blocks which lead to uses. Knowing this allows us to avoid
1137/// inserting PHI nodes into blocks which don't lead to uses (thus, the
1138/// inserted phi nodes would be dead).
1139void PromoteMem2Reg::ComputeLiveInBlocks(
1140 AllocaInst *AI, AllocaInfo &Info,
1141 const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
1142 SmallPtrSetImpl<BasicBlock *> &LiveInBlocks) {
1143 // To determine liveness, we must iterate through the predecessors of blocks
1144 // where the def is live. Blocks are added to the worklist if we need to
1145 // check their predecessors. Start with all the using blocks.
1146 SmallVector<BasicBlock *, 64> LiveInBlockWorklist(Info.UsingBlocks.begin(),
1147 Info.UsingBlocks.end());
1148
1149 // If any of the using blocks is also a definition block, check to see if the
1150 // definition occurs before or after the use. If it happens before the use,
1151 // the value isn't really live-in.
1152 for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) {
1153 BasicBlock *BB = LiveInBlockWorklist[i];
1154 if (!DefBlocks.count(Ptr: BB))
1155 continue;
1156
1157 // Okay, this is a block that both uses and defines the value. If the first
1158 // reference to the alloca is a def (store), then we know it isn't live-in.
1159 for (BasicBlock::iterator I = BB->begin();; ++I) {
1160 if (StoreInst *SI = dyn_cast<StoreInst>(Val&: I)) {
1161 if (SI->getOperand(i_nocapture: 1) != AI)
1162 continue;
1163
1164 // We found a store to the alloca before a load. The alloca is not
1165 // actually live-in here.
1166 LiveInBlockWorklist[i] = LiveInBlockWorklist.back();
1167 LiveInBlockWorklist.pop_back();
1168 --i;
1169 --e;
1170 break;
1171 }
1172
1173 if (LoadInst *LI = dyn_cast<LoadInst>(Val&: I))
1174 // Okay, we found a load before a store to the alloca. It is actually
1175 // live into this block.
1176 if (LI->getOperand(i_nocapture: 0) == AI)
1177 break;
1178 }
1179 }
1180
1181 // Now that we have a set of blocks where the phi is live-in, recursively add
1182 // their predecessors until we find the full region the value is live.
1183 while (!LiveInBlockWorklist.empty()) {
1184 BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
1185
1186 // The block really is live in here, insert it into the set. If already in
1187 // the set, then it has already been processed.
1188 if (!LiveInBlocks.insert(Ptr: BB).second)
1189 continue;
1190
1191 // Since the value is live into BB, it is either defined in a predecessor or
1192 // live into it to. Add the preds to the worklist unless they are a
1193 // defining block.
1194 for (BasicBlock *P : predecessors(BB)) {
1195 // The value is not live into a predecessor if it defines the value.
1196 if (DefBlocks.count(Ptr: P))
1197 continue;
1198
1199 // Otherwise it is, add to the worklist.
1200 LiveInBlockWorklist.push_back(Elt: P);
1201 }
1202 }
1203}
1204
1205/// Queue a phi-node to be added to a basic-block for a specific Alloca.
1206///
1207/// Returns true if there wasn't already a phi-node for that variable
1208bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo,
1209 unsigned &Version) {
1210 // Look up the basic-block in question.
1211 PHINode *&PN = NewPhiNodes[std::make_pair(x: BB->getNumber(), y&: AllocaNo)];
1212
1213 // If the BB already has a phi node added for the i'th alloca then we're done!
1214 if (PN)
1215 return false;
1216
1217 // Create a PhiNode using the type from loads/stores... and add the phi-node
1218 // to the BasicBlock.
1219 PN = PHINode::Create(Ty: AllocaValueTypes[AllocaNo], NumReservedValues: getNumPreds(BB),
1220 NameStr: Allocas[AllocaNo]->getName() + "." + Twine(Version++));
1221 PN->insertBefore(InsertPos: BB->begin());
1222 ++NumPHIInsert;
1223 PhiToAllocaMap[PN] = AllocaNo;
1224 return true;
1225}
1226
1227/// Update the debug location of a phi. \p ApplyMergedLoc indicates whether to
1228/// create a merged location incorporating \p DL, or to set \p DL directly.
1229static void updateForIncomingValueLocation(PHINode *PN, DebugLoc DL,
1230 bool ApplyMergedLoc) {
1231 if (ApplyMergedLoc)
1232 PN->applyMergedLocation(LocA: PN->getDebugLoc(), LocB: DL);
1233 else
1234 PN->setDebugLoc(DL);
1235}
1236
1237/// Recursively traverse the CFG of the function, renaming loads and
1238/// stores to the allocas which we are promoting.
1239///
1240/// IncomingVals indicates what value each Alloca contains on exit from the
1241/// predecessor block Pred.
1242void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred) {
1243 // If we are inserting any phi nodes into this BB, they will already be in the
1244 // block.
1245 if (PHINode *APN = dyn_cast<PHINode>(Val: BB->begin())) {
1246 // If we have PHI nodes to update, compute the number of edges from Pred to
1247 // BB.
1248 if (PhiToAllocaMap.count(Val: APN)) {
1249 // We want to be able to distinguish between PHI nodes being inserted by
1250 // this invocation of mem2reg from those phi nodes that already existed in
1251 // the IR before mem2reg was run. We determine that APN is being inserted
1252 // because it is missing incoming edges. All other PHI nodes being
1253 // inserted by this pass of mem2reg will have the same number of incoming
1254 // operands so far. Remember this count.
1255 unsigned NewPHINumOperands = APN->getNumOperands();
1256
1257 unsigned NumEdges = llvm::count(Range: successors(BB: Pred), Element: BB);
1258 assert(NumEdges && "Must be at least one edge from Pred to BB!");
1259
1260 // Add entries for all the phis.
1261 BasicBlock::iterator PNI = BB->begin();
1262 do {
1263 unsigned AllocaNo = PhiToAllocaMap[APN];
1264
1265 // Update the location of the phi node.
1266 updateForIncomingValueLocation(PN: APN, DL: IncomingLocs[AllocaNo],
1267 ApplyMergedLoc: APN->getNumIncomingValues() > 0);
1268
1269 // Add N incoming values to the PHI node.
1270 for (unsigned i = 0; i != NumEdges; ++i)
1271 APN->addIncoming(V: IncomingVals[AllocaNo], BB: Pred);
1272
1273 // For the sequence `return X > 0.0 ? X : -X`, it is expected that this
1274 // results in fabs intrinsic. However, without no-signed-zeros(nsz) flag
1275 // on the phi node generated at this stage, fabs folding does not
1276 // happen. So, we try to infer nsz flag from the function attributes to
1277 // enable this fabs folding.
1278 if (isa<FPMathOperator>(Val: APN) && NoSignedZeros)
1279 APN->setHasNoSignedZeros(true);
1280
1281 // The currently active variable for this block is now the PHI.
1282 IncomingVals.set(Idx: AllocaNo, Val: APN);
1283 AllocaATInfo[AllocaNo].updateForNewPhi(NewPhi: APN, DIB);
1284 for (DbgVariableRecord *DbgItem : AllocaDPUsers[AllocaNo])
1285 if (DbgItem->isAddressOfVariable())
1286 ConvertDebugDeclareToDebugValue(DVR: DbgItem, LI: APN, Builder&: DIB);
1287
1288 // Get the next phi node.
1289 ++PNI;
1290 APN = dyn_cast<PHINode>(Val&: PNI);
1291 if (!APN)
1292 break;
1293
1294 // Verify that it is missing entries. If not, it is not being inserted
1295 // by this mem2reg invocation so we want to ignore it.
1296 } while (APN->getNumOperands() == NewPHINumOperands);
1297 }
1298 }
1299
1300 // Don't revisit blocks.
1301 if (Visited.test(Idx: BB->getNumber()))
1302 return;
1303 Visited.set(BB->getNumber());
1304
1305 for (BasicBlock::iterator II = BB->begin(); !II->isTerminator();) {
1306 Instruction *I = &*II++; // get the instruction, increment iterator
1307
1308 if (LoadInst *LI = dyn_cast<LoadInst>(Val: I)) {
1309 AllocaInst *Src = dyn_cast<AllocaInst>(Val: LI->getPointerOperand());
1310 if (!Src)
1311 continue;
1312
1313 auto AI = AllocaLookup.find(Val: Src);
1314 if (AI == AllocaLookup.end())
1315 continue;
1316
1317 Value *V = IncomingVals[AI->second];
1318 convertMetadataToAssumes(LI, Val: V, DL: SQ.DL, AC, DT: &DT);
1319
1320 // Anything using the load now uses the current value.
1321 LI->replaceAllUsesWith(V);
1322 LI->eraseFromParent();
1323 } else if (StoreInst *SI = dyn_cast<StoreInst>(Val: I)) {
1324 // Delete this instruction and mark the name as the current holder of the
1325 // value
1326 AllocaInst *Dest = dyn_cast<AllocaInst>(Val: SI->getPointerOperand());
1327 if (!Dest)
1328 continue;
1329
1330 auto ai = AllocaLookup.find(Val: Dest);
1331 if (ai == AllocaLookup.end())
1332 continue;
1333
1334 // what value were we writing?
1335 unsigned AllocaNo = ai->second;
1336 IncomingVals.set(Idx: AllocaNo, Val: SI->getOperand(i_nocapture: 0));
1337
1338 // Record debuginfo for the store before removing it.
1339 IncomingLocs.set(Idx: AllocaNo, Val: SI->getDebugLoc());
1340 AllocaATInfo[AllocaNo].updateForDeletedStore(ToDelete: SI, DIB,
1341 DVRAssignsToDelete: &DVRAssignsToDelete);
1342 for (DbgVariableRecord *DbgItem : AllocaDPUsers[ai->second])
1343 if (DbgItem->isAddressOfVariable())
1344 ConvertDebugDeclareToDebugValue(DVR: DbgItem, SI, Builder&: DIB);
1345 SI->eraseFromParent();
1346 }
1347 }
1348
1349 // 'Recurse' to our successors.
1350
1351 // Keep track of the successors so we don't visit the same successor twice
1352 SmallPtrSet<BasicBlock *, 8> VisitedSuccs;
1353
1354 for (BasicBlock *S : reverse(C: successors(BB)))
1355 if (VisitedSuccs.insert(Ptr: S).second)
1356 pushToWorklist(BB: S, Pred: BB);
1357}
1358
1359void llvm::PromoteMemToReg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
1360 AssumptionCache *AC) {
1361 // If there is nothing to do, bail out...
1362 if (Allocas.empty())
1363 return;
1364
1365 PromoteMem2Reg(Allocas, DT, AC).run();
1366}
1367