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