56#define DEBUG_TYPE "mem2reg"
58STATISTIC(NumLocalPromoted,
"Number of alloca's promoted within one block");
59STATISTIC(NumSingleStore,
"Number of alloca's promoted with a single store");
60STATISTIC(NumDeadAlloca,
"Number of dead alloca's removed");
61STATISTIC(NumPHIInsert,
"Number of PHI nodes inserted");
66 if (
const LoadInst *LI = dyn_cast<LoadInst>(U)) {
71 }
else if (
const StoreInst *
SI = dyn_cast<StoreInst>(U)) {
72 if (
SI->getValueOperand() == AI ||
79 }
else if (
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) {
80 if (!II->isLifetimeStartOrEnd() && !II->isDroppable())
82 }
else if (
const BitCastInst *BCI = dyn_cast<BitCastInst>(U)) {
86 if (!GEPI->hasAllZeroIndices())
104class AssignmentTrackingInfo {
124 if (DbgAssigns.
empty()) {
143 for (
auto *DAI : DbgAssigns) {
156 for (
auto *DAI : DbgAssigns)
160 void clear() { DbgAssigns.clear(); }
161 bool empty() {
return DbgAssigns.empty(); }
172 bool OnlyUsedInOneBlock;
177 AssignmentTrackingInfo AssignmentTracking;
180 DefiningBlocks.
clear();
184 OnlyUsedInOneBlock =
true;
186 AssignmentTracking.clear();
211 if (OnlyUsedInOneBlock) {
213 OnlyBlock =
User->getParent();
214 else if (OnlyBlock !=
User->getParent())
215 OnlyUsedInOneBlock =
false;
218 DbgUserVec AllDbgUsers;
220 std::copy_if(AllDbgUsers.begin(), AllDbgUsers.end(),
222 return !isa<DbgAssignIntrinsic>(DII);
224 AssignmentTracking.init(AI);
229struct RenamePassData {
230 using ValVector = std::vector<Value *>;
231 using LocationVector = std::vector<DebugLoc>;
247class LargeBlockInfo {
258 static bool isInterestingInstruction(
const Instruction *
I) {
259 return (isa<LoadInst>(
I) && isa<AllocaInst>(
I->getOperand(0))) ||
260 (isa<StoreInst>(
I) && isa<AllocaInst>(
I->getOperand(1)));
265 assert(isInterestingInstruction(
I) &&
266 "Not a load/store to/from an alloca?");
270 if (It != InstNumbers.
end())
279 if (isInterestingInstruction(&BBI))
280 InstNumbers[&BBI] = InstNo++;
281 It = InstNumbers.
find(
I);
283 assert(It != InstNumbers.
end() &&
"Didn't insert instruction?");
292struct PromoteMem2Reg {
294 std::vector<AllocaInst *> Allocas;
341 : Allocas(Allocas.
begin(), Allocas.
end()), DT(DT),
349 void RemoveFromAllocasList(
unsigned &AllocaIdx) {
350 Allocas[AllocaIdx] = Allocas.back();
356 unsigned &NP = BBNumPreds[BB];
366 RenamePassData::ValVector &IncVals,
367 RenamePassData::LocationVector &IncLocs,
368 std::vector<RenamePassData> &Worklist);
369 bool QueuePhiNode(
BasicBlock *BB,
unsigned AllocaIdx,
unsigned &Version);
393 if (AC && LI->
getMetadata(LLVMContext::MD_nonnull) &&
405 if (isa<LoadInst>(
I) || isa<StoreInst>(
I))
409 if (
I->isDroppable()) {
410 I->dropDroppableUse(U);
414 if (!
I->getType()->isVoidTy()) {
419 Instruction *Inst = cast<Instruction>(UU.getUser());
429 I->eraseFromParent();
445 bool StoringGlobalVal = !isa<Instruction>(OnlyStore->
getOperand(0));
450 Info.UsingBlocks.clear();
454 if (UserInst == OnlyStore)
456 LoadInst *LI = cast<LoadInst>(UserInst);
462 if (!StoringGlobalVal) {
467 if (StoreIndex == -1)
468 StoreIndex = LBI.getInstructionIndex(OnlyStore);
470 if (
unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) {
472 Info.UsingBlocks.push_back(StoreBB);
498 if (!
Info.UsingBlocks.empty())
503 Info.AssignmentTracking.updateForDeletedStore(
Info.OnlyStore, DIB);
520 Info.OnlyStore->eraseFromParent();
521 LBI.deleteValue(
Info.OnlyStore);
555 StoresByIndexTy StoresByIndex;
559 StoresByIndex.
push_back(std::make_pair(LBI.getInstructionIndex(
SI),
SI));
568 LoadInst *LI = dyn_cast<LoadInst>(U);
572 unsigned LoadIdx = LBI.getInstructionIndex(LI);
577 std::make_pair(LoadIdx,
static_cast<StoreInst *
>(
nullptr)),
580 if (
I == StoresByIndex.begin()) {
581 if (StoresByIndex.empty())
591 ReplVal = std::prev(
I)->second->getOperand(0);
611 Info.AssignmentTracking.updateForDeletedStore(
SI, DIB);
618 SI->eraseFromParent();
635void PromoteMem2Reg::run() {
638 AllocaDbgUsers.
resize(Allocas.size());
639 AllocaATInfo.
resize(Allocas.size());
645 for (
unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
650 "All allocas should be in the same function, which is same as DF!");
659 RemoveFromAllocasList(AllocaNum);
666 Info.AnalyzeAlloca(AI);
670 if (
Info.DefiningBlocks.size() == 1) {
673 RemoveFromAllocasList(AllocaNum);
681 if (
Info.OnlyUsedInOneBlock &&
684 RemoveFromAllocasList(AllocaNum);
690 if (BBNumbers.
empty()) {
693 BBNumbers[&BB] =
ID++;
697 if (!
Info.DbgUsers.empty())
698 AllocaDbgUsers[AllocaNum] =
Info.DbgUsers;
699 if (!
Info.AssignmentTracking.empty())
700 AllocaATInfo[AllocaNum] =
Info.AssignmentTracking;
703 AllocaLookup[Allocas[AllocaNum]] = AllocaNum;
707 Info.DefiningBlocks.end());
718 IDF.setLiveInBlocks(LiveInBlocks);
719 IDF.setDefiningBlocks(DefBlocks);
721 IDF.calculate(PHIBlocks);
723 return BBNumbers.
find(
A)->second < BBNumbers.
find(
B)->second;
728 QueuePhiNode(BB, AllocaNum, CurrentVersion);
739 RenamePassData::ValVector Values(Allocas.size());
740 for (
unsigned i = 0, e = Allocas.size(); i != e; ++i)
745 RenamePassData::LocationVector
Locations(Allocas.size());
749 std::vector<RenamePassData> RenamePassWorkList;
750 RenamePassWorkList.emplace_back(&
F.front(),
nullptr, std::move(Values),
751 std::move(Locations));
753 RenamePassData RPD = std::move(RenamePassWorkList.back());
754 RenamePassWorkList.pop_back();
756 RenamePass(RPD.BB, RPD.Pred, RPD.Values, RPD.Locations, RenamePassWorkList);
757 }
while (!RenamePassWorkList.empty());
771 A->eraseFromParent();
775 for (
auto &DbgUsers : AllocaDbgUsers) {
776 for (
auto *DII : DbgUsers)
777 if (DII->isAddressOfVariable() || DII->getExpression()->startsWithDeref())
778 DII->eraseFromParent();
785 bool EliminatedAPHI =
true;
786 while (EliminatedAPHI) {
787 EliminatedAPHI =
false;
795 E = NewPhiNodes.
end();
804 EliminatedAPHI =
true;
818 E = NewPhiNodes.
end();
824 if (&BB->
front() != SomePHI)
840 return BBNumbers.
find(
A)->second < BBNumbers.
find(
B)->second;
851 "PHI node has entry for a block which is not a predecessor!");
863 while ((SomePHI = dyn_cast<PHINode>(BBI++)) &&
879void PromoteMem2Reg::ComputeLiveInBlocks(
887 Info.UsingBlocks.end());
892 for (
unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) {
894 if (!DefBlocks.
count(BB))
901 if (
SI->getOperand(1) != AI)
906 LiveInBlockWorklist[i] = LiveInBlockWorklist.
back();
907 LiveInBlockWorklist.pop_back();
913 if (
LoadInst *LI = dyn_cast<LoadInst>(
I))
923 while (!LiveInBlockWorklist.empty()) {
924 BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
928 if (!LiveInBlocks.
insert(BB).second)
940 LiveInBlockWorklist.push_back(
P);
948bool PromoteMem2Reg::QueuePhiNode(
BasicBlock *BB,
unsigned AllocaNo,
951 PHINode *&PN = NewPhiNodes[std::make_pair(BBNumbers[BB], AllocaNo)];
959 PN =
PHINode::Create(Allocas[AllocaNo]->getAllocatedType(), getNumPreds(BB),
963 PhiToAllocaMap[PN] = AllocaNo;
970 bool ApplyMergedLoc) {
983 RenamePassData::ValVector &IncomingVals,
984 RenamePassData::LocationVector &IncomingLocs,
985 std::vector<RenamePassData> &Worklist) {
992 if (PhiToAllocaMap.
count(APN)) {
999 unsigned NewPHINumOperands = APN->getNumOperands();
1002 assert(NumEdges &&
"Must be at least one edge from Pred to BB!");
1007 unsigned AllocaNo = PhiToAllocaMap[APN];
1011 APN->getNumIncomingValues() > 0);
1014 for (
unsigned i = 0; i != NumEdges; ++i)
1015 APN->addIncoming(IncomingVals[AllocaNo], Pred);
1018 IncomingVals[AllocaNo] = APN;
1019 AllocaATInfo[AllocaNo].updateForNewPhi(APN, DIB);
1021 if (DII->isAddressOfVariable())
1026 APN = dyn_cast<PHINode>(PNI);
1032 }
while (APN->getNumOperands() == NewPHINumOperands);
1037 if (!Visited.
insert(BB).second)
1043 if (
LoadInst *LI = dyn_cast<LoadInst>(
I)) {
1049 if (AI == AllocaLookup.
end())
1052 Value *V = IncomingVals[AI->second];
1058 }
else if (
StoreInst *SI = dyn_cast<StoreInst>(
I)) {
1061 AllocaInst *Dest = dyn_cast<AllocaInst>(
SI->getPointerOperand());
1066 if (ai == AllocaLookup.
end())
1070 unsigned AllocaNo = ai->second;
1071 IncomingVals[AllocaNo] =
SI->getOperand(0);
1074 IncomingLocs[AllocaNo] =
SI->getDebugLoc();
1075 AllocaATInfo[AllocaNo].updateForDeletedStore(SI, DIB);
1077 if (DII->isAddressOfVariable())
1079 SI->eraseFromParent();
1098 if (VisitedSuccs.
insert(*I).second)
1099 Worklist.emplace_back(*
I, Pred, IncomingVals, IncomingLocs);
1107 if (Allocas.
empty())
1110 PromoteMem2Reg(Allocas, DT, AC).run();
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
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static void clear(coro::Shape &Shape)
This file defines the DenseMap class.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
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 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)
This class represents a conversion between pointers from one address space to another.
an instruction to allocate memory on the stack
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool empty() const
empty - Check if the array is empty.
A cache of @llvm.assume calls within a function.
void registerAssumption(CondGuardInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const Instruction & front() const
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
const Instruction & back() const
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="", Instruction *InsertBefore=nullptr)
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
bool startsWithDeref() const
Return whether the first element a DW_OP_deref.
A parsed version of the target data layout string in and methods for querying it.
This represents the llvm.dbg.assign instruction.
This is the common base class for debug info intrinsics for variables.
bool isAddressOfVariable() const
Does this describe the address of a local variable.
DIExpression * getExpression() const
Identifies a unique instance of a variable.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
This instruction compares its operands according to the predicate given to the constructor.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
const BasicBlock * getParent() const
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
void applyMergedLocation(const DILocation *LocA, const DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
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.
An instruction for reading from memory.
Value * getPointerOperand()
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="", Instruction *InsertBefore=nullptr)
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.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
bool contains(const T &V) const
Check if the SmallSet contains the given element.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
typename SuperClass::iterator iterator
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
bool isDroppable() const
A droppable user is a user for which uses can be dropped without affecting correctness and should be ...
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
static void dropDroppableUse(Use &U)
Remove the droppable use U.
iterator_range< use_iterator > uses()
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)
Return a range of dbg.assign intrinsics which use \ID as an operand.
void deleteAssignmentMarkers(const Instruction *Inst)
Delete the llvm.dbg.assign intrinsics linked to Inst.
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
Interval::succ_iterator succ_end(Interval *I)
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.
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...
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...
bool isAllocaPromotable(const AllocaInst *AI)
Return true if this alloca is legal for promotion.
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
void sort(IteratorTy Start, IteratorTy End)
void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, StoreInst *SI, DIBuilder &Builder)
===------------------------------------------------------------------—===// Dbg Intrinsic utilities
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...
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
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...
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
auto predecessors(const MachineBasicBlock *BB)
unsigned pred_size(const MachineBasicBlock *BB)
Function object to check whether the first component of a std::pair compares less than the first comp...