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