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 {
121 void updateForDeletedStore(
126 if (DbgAssigns.
empty())
138 DbgAssignsToDelete->
insert(DAI);
139 DIB.insertDbgValueIntrinsic(DAI->getValue(), DAI->getVariable(),
140 DAI->getExpression(), DAI->getDebugLoc(),
152 for (
auto *DAI : DbgAssigns) {
165 for (
auto *DAI : DbgAssigns)
169 void clear() { DbgAssigns.clear(); }
170 bool empty() {
return DbgAssigns.empty(); }
181 bool OnlyUsedInOneBlock;
186 AssignmentTrackingInfo AssignmentTracking;
189 DefiningBlocks.
clear();
193 OnlyUsedInOneBlock =
true;
195 AssignmentTracking.clear();
220 if (OnlyUsedInOneBlock) {
222 OnlyBlock =
User->getParent();
223 else if (OnlyBlock !=
User->getParent())
224 OnlyUsedInOneBlock =
false;
227 DbgUserVec AllDbgUsers;
229 std::copy_if(AllDbgUsers.begin(), AllDbgUsers.end(),
231 return !isa<DbgAssignIntrinsic>(DII);
233 AssignmentTracking.init(AI);
238struct RenamePassData {
239 using ValVector = std::vector<Value *>;
240 using LocationVector = std::vector<DebugLoc>;
256class LargeBlockInfo {
267 static bool isInterestingInstruction(
const Instruction *
I) {
268 return (isa<LoadInst>(
I) && isa<AllocaInst>(
I->getOperand(0))) ||
269 (isa<StoreInst>(
I) && isa<AllocaInst>(
I->getOperand(1)));
274 assert(isInterestingInstruction(
I) &&
275 "Not a load/store to/from an alloca?");
279 if (It != InstNumbers.
end())
288 if (isInterestingInstruction(&BBI))
289 InstNumbers[&BBI] = InstNo++;
290 It = InstNumbers.
find(
I);
292 assert(It != InstNumbers.
end() &&
"Didn't insert instruction?");
301struct PromoteMem2Reg {
303 std::vector<AllocaInst *> Allocas;
353 : Allocas(Allocas.
begin(), Allocas.
end()), DT(DT),
361 void RemoveFromAllocasList(
unsigned &AllocaIdx) {
362 Allocas[AllocaIdx] = Allocas.back();
368 unsigned &NP = BBNumPreds[BB];
378 RenamePassData::ValVector &IncVals,
379 RenamePassData::LocationVector &IncLocs,
380 std::vector<RenamePassData> &Worklist);
381 bool QueuePhiNode(
BasicBlock *BB,
unsigned AllocaIdx,
unsigned &Version);
384 void cleanUpDbgAssigns() {
385 for (
auto *DAI : DbgAssignsToDelete)
386 DAI->eraseFromParent();
387 DbgAssignsToDelete.clear();
412 if (AC && LI->
getMetadata(LLVMContext::MD_nonnull) &&
424 if (isa<LoadInst>(
I) || isa<StoreInst>(
I))
428 if (
I->isDroppable()) {
429 I->dropDroppableUse(U);
433 if (!
I->getType()->isVoidTy()) {
438 Instruction *Inst = cast<Instruction>(UU.getUser());
448 I->eraseFromParent();
465 bool StoringGlobalVal = !isa<Instruction>(OnlyStore->
getOperand(0));
470 Info.UsingBlocks.clear();
474 if (UserInst == OnlyStore)
476 LoadInst *LI = cast<LoadInst>(UserInst);
482 if (!StoringGlobalVal) {
487 if (StoreIndex == -1)
488 StoreIndex = LBI.getInstructionIndex(OnlyStore);
490 if (
unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) {
492 Info.UsingBlocks.push_back(StoreBB);
518 if (!
Info.UsingBlocks.empty())
523 Info.AssignmentTracking.updateForDeletedStore(
Info.OnlyStore, DIB,
541 Info.OnlyStore->eraseFromParent();
542 LBI.deleteValue(
Info.OnlyStore);
565 AllocaInst *AI,
const AllocaInfo &Info, LargeBlockInfo &LBI,
575 StoresByIndexTy StoresByIndex;
578 if (
StoreInst *SI = dyn_cast<StoreInst>(U))
579 StoresByIndex.
push_back(std::make_pair(LBI.getInstructionIndex(SI), SI));
588 LoadInst *LI = dyn_cast<LoadInst>(U);
592 unsigned LoadIdx = LBI.getInstructionIndex(LI);
597 std::make_pair(LoadIdx,
static_cast<StoreInst *
>(
nullptr)),
600 if (
I == StoresByIndex.begin()) {
601 if (StoresByIndex.empty())
611 ReplVal = std::prev(
I)->second->getOperand(0);
631 Info.AssignmentTracking.updateForDeletedStore(SI, DIB, DbgAssignsToDelete);
638 SI->eraseFromParent();
655void PromoteMem2Reg::run() {
658 AllocaDbgUsers.
resize(Allocas.size());
659 AllocaATInfo.
resize(Allocas.size());
665 for (
unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
670 "All allocas should be in the same function, which is same as DF!");
679 RemoveFromAllocasList(AllocaNum);
686 Info.AnalyzeAlloca(AI);
690 if (
Info.DefiningBlocks.size() == 1) {
692 &DbgAssignsToDelete)) {
694 RemoveFromAllocasList(AllocaNum);
702 if (
Info.OnlyUsedInOneBlock &&
704 &DbgAssignsToDelete)) {
706 RemoveFromAllocasList(AllocaNum);
712 if (BBNumbers.
empty()) {
715 BBNumbers[&BB] =
ID++;
719 if (!
Info.DbgUsers.empty())
720 AllocaDbgUsers[AllocaNum] =
Info.DbgUsers;
721 if (!
Info.AssignmentTracking.empty())
722 AllocaATInfo[AllocaNum] =
Info.AssignmentTracking;
725 AllocaLookup[Allocas[AllocaNum]] = AllocaNum;
729 Info.DefiningBlocks.end());
740 IDF.setLiveInBlocks(LiveInBlocks);
741 IDF.setDefiningBlocks(DefBlocks);
743 IDF.calculate(PHIBlocks);
745 return BBNumbers.
find(
A)->second < BBNumbers.
find(
B)->second;
750 QueuePhiNode(BB, AllocaNum, CurrentVersion);
753 if (Allocas.empty()) {
762 RenamePassData::ValVector Values(Allocas.size());
763 for (
unsigned i = 0, e = Allocas.size(); i != e; ++i)
768 RenamePassData::LocationVector
Locations(Allocas.size());
772 std::vector<RenamePassData> RenamePassWorkList;
773 RenamePassWorkList.emplace_back(&
F.front(),
nullptr, std::move(Values),
774 std::move(Locations));
776 RenamePassData RPD = std::move(RenamePassWorkList.back());
777 RenamePassWorkList.pop_back();
779 RenamePass(RPD.BB, RPD.Pred, RPD.Values, RPD.Locations, RenamePassWorkList);
780 }
while (!RenamePassWorkList.empty());
794 A->eraseFromParent();
798 for (
auto &DbgUsers : AllocaDbgUsers) {
799 for (
auto *DII : DbgUsers)
800 if (DII->isAddressOfVariable() || DII->getExpression()->startsWithDeref())
801 DII->eraseFromParent();
808 bool EliminatedAPHI =
true;
809 while (EliminatedAPHI) {
810 EliminatedAPHI =
false;
818 E = NewPhiNodes.
end();
827 EliminatedAPHI =
true;
841 E = NewPhiNodes.
end();
847 if (&BB->
front() != SomePHI)
863 return BBNumbers.
find(
A)->second < BBNumbers.
find(
B)->second;
874 "PHI node has entry for a block which is not a predecessor!");
886 while ((SomePHI = dyn_cast<PHINode>(BBI++)) &&
903void PromoteMem2Reg::ComputeLiveInBlocks(
911 Info.UsingBlocks.end());
916 for (
unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) {
918 if (!DefBlocks.
count(BB))
925 if (
SI->getOperand(1) != AI)
930 LiveInBlockWorklist[i] = LiveInBlockWorklist.
back();
931 LiveInBlockWorklist.pop_back();
937 if (
LoadInst *LI = dyn_cast<LoadInst>(
I))
947 while (!LiveInBlockWorklist.empty()) {
948 BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
952 if (!LiveInBlocks.
insert(BB).second)
964 LiveInBlockWorklist.push_back(
P);
972bool PromoteMem2Reg::QueuePhiNode(
BasicBlock *BB,
unsigned AllocaNo,
975 PHINode *&PN = NewPhiNodes[std::make_pair(BBNumbers[BB], AllocaNo)];
983 PN =
PHINode::Create(Allocas[AllocaNo]->getAllocatedType(), getNumPreds(BB),
987 PhiToAllocaMap[PN] = AllocaNo;
994 bool ApplyMergedLoc) {
1007 RenamePassData::ValVector &IncomingVals,
1008 RenamePassData::LocationVector &IncomingLocs,
1009 std::vector<RenamePassData> &Worklist) {
1016 if (PhiToAllocaMap.
count(APN)) {
1023 unsigned NewPHINumOperands = APN->getNumOperands();
1026 assert(NumEdges &&
"Must be at least one edge from Pred to BB!");
1031 unsigned AllocaNo = PhiToAllocaMap[APN];
1035 APN->getNumIncomingValues() > 0);
1038 for (
unsigned i = 0; i != NumEdges; ++i)
1039 APN->addIncoming(IncomingVals[AllocaNo], Pred);
1042 IncomingVals[AllocaNo] = APN;
1043 AllocaATInfo[AllocaNo].updateForNewPhi(APN, DIB);
1045 if (DII->isAddressOfVariable())
1050 APN = dyn_cast<PHINode>(PNI);
1056 }
while (APN->getNumOperands() == NewPHINumOperands);
1061 if (!Visited.
insert(BB).second)
1067 if (
LoadInst *LI = dyn_cast<LoadInst>(
I)) {
1073 if (AI == AllocaLookup.
end())
1076 Value *
V = IncomingVals[AI->second];
1082 }
else if (
StoreInst *SI = dyn_cast<StoreInst>(
I)) {
1085 AllocaInst *Dest = dyn_cast<AllocaInst>(
SI->getPointerOperand());
1090 if (ai == AllocaLookup.
end())
1094 unsigned AllocaNo = ai->second;
1095 IncomingVals[AllocaNo] =
SI->getOperand(0);
1098 IncomingLocs[AllocaNo] =
SI->getDebugLoc();
1099 AllocaATInfo[AllocaNo].updateForDeletedStore(SI, DIB,
1100 &DbgAssignsToDelete);
1102 if (DII->isAddressOfVariable())
1104 SI->eraseFromParent();
1123 if (VisitedSuccs.
insert(*I).second)
1124 Worklist.emplace_back(*
I, Pred, IncomingVals, IncomingLocs);
1132 if (Allocas.
empty())
1135 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(AssumeInst *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 whole variable (discards/ignores fragment information).
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.
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.
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.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void applyMergedLocation(DILocation *LocA, DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
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.
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
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...
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)
Implement std::hash so that hash_code can be used in STL containers.
Function object to check whether the first component of a container supported by std::get (like std::...