Go to the documentation of this file.
57 #define DEBUG_TYPE "mem2reg"
59 STATISTIC(NumLocalPromoted,
"Number of alloca's promoted within one block");
60 STATISTIC(NumSingleStore,
"Number of alloca's promoted with a single store");
61 STATISTIC(NumDeadAlloca,
"Number of dead alloca's removed");
62 STATISTIC(NumPHIInsert,
"Number of PHI nodes inserted");
67 if (
const LoadInst *LI = dyn_cast<LoadInst>(U)) {
72 }
else if (
const StoreInst *
SI = dyn_cast<StoreInst>(U)) {
73 if (
SI->getOperand(0) == 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())
111 bool OnlyUsedInOneBlock;
116 DefiningBlocks.
clear();
120 OnlyUsedInOneBlock =
true;
137 DefiningBlocks.push_back(
SI->getParent());
146 if (OnlyUsedInOneBlock) {
148 OnlyBlock =
User->getParent();
149 else if (OnlyBlock !=
User->getParent())
150 OnlyUsedInOneBlock =
false;
159 struct RenamePassData {
160 using ValVector = std::vector<Value *>;
161 using LocationVector = std::vector<DebugLoc>;
169 LocationVector Locations;
177 class LargeBlockInfo {
188 static bool isInterestingInstruction(
const Instruction *
I) {
189 return (isa<LoadInst>(
I) && isa<AllocaInst>(
I->getOperand(0))) ||
190 (isa<StoreInst>(
I) && isa<AllocaInst>(
I->getOperand(1)));
195 assert(isInterestingInstruction(
I) &&
196 "Not a load/store to/from an alloca?");
200 if (It != InstNumbers.
end())
209 if (isInterestingInstruction(&BBI))
210 InstNumbers[&BBI] = InstNo++;
211 It = InstNumbers.
find(
I);
213 assert(It != InstNumbers.
end() &&
"Didn't insert instruction?");
222 struct PromoteMem2Reg {
224 std::vector<AllocaInst *> Allocas;
267 : Allocas(Allocas.
begin(), Allocas.
end()), DT(DT),
275 void RemoveFromAllocasList(
unsigned &AllocaIdx) {
276 Allocas[AllocaIdx] = Allocas.back();
282 unsigned &NP = BBNumPreds[
BB];
292 RenamePassData::ValVector &IncVals,
293 RenamePassData::LocationVector &IncLocs,
294 std::vector<RenamePassData> &Worklist);
318 if (isa<LoadInst>(
I) || isa<StoreInst>(
I))
322 if (
I->isDroppable()) {
323 I->dropDroppableUse(U);
327 if (!
I->getType()->isVoidTy()) {
332 Instruction *Inst = cast<Instruction>(UU.getUser());
342 I->eraseFromParent();
358 bool StoringGlobalVal = !isa<Instruction>(OnlyStore->
getOperand(0));
363 Info.UsingBlocks.clear();
367 if (UserInst == OnlyStore)
369 LoadInst *LI = cast<LoadInst>(UserInst);
375 if (!StoringGlobalVal) {
380 if (StoreIndex == -1)
381 StoreIndex = LBI.getInstructionIndex(OnlyStore);
383 if (
unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) {
385 Info.UsingBlocks.push_back(StoreBB);
407 if (AC && LI->
getMetadata(LLVMContext::MD_nonnull) &&
417 if (!
Info.UsingBlocks.empty())
432 Info.OnlyStore->eraseFromParent();
433 LBI.deleteValue(
Info.OnlyStore);
467 StoresByIndexTy StoresByIndex;
471 StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(
SI),
SI));
480 LoadInst *LI = dyn_cast<LoadInst>(U);
484 unsigned LoadIdx = LBI.getInstructionIndex(LI);
489 std::make_pair(LoadIdx,
static_cast<StoreInst *
>(
nullptr)),
491 if (
I == StoresByIndex.begin()) {
492 if (StoresByIndex.empty())
503 Value *ReplVal = std::prev(
I)->second->getOperand(0);
504 if (AC && LI->
getMetadata(LLVMContext::MD_nonnull) &&
530 SI->eraseFromParent();
545 void PromoteMem2Reg::run() {
548 AllocaDbgUsers.
resize(Allocas.size());
554 for (
unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
559 "All allocas should be in the same function, which is same as DF!");
568 RemoveFromAllocasList(AllocaNum);
575 Info.AnalyzeAlloca(AI);
579 if (
Info.DefiningBlocks.size() == 1) {
582 RemoveFromAllocasList(AllocaNum);
590 if (
Info.OnlyUsedInOneBlock &&
593 RemoveFromAllocasList(AllocaNum);
599 if (BBNumbers.
empty()) {
602 BBNumbers[&
BB] =
ID++;
606 if (!
Info.DbgUsers.empty())
607 AllocaDbgUsers[AllocaNum] =
Info.DbgUsers;
610 AllocaLookup[Allocas[AllocaNum]] = AllocaNum;
614 Info.DefiningBlocks.end());
625 IDF.setLiveInBlocks(LiveInBlocks);
626 IDF.setDefiningBlocks(DefBlocks);
628 IDF.calculate(PHIBlocks);
630 return BBNumbers.
find(A)->second < BBNumbers.
find(
B)->second;
646 RenamePassData::ValVector Values(Allocas.size());
647 for (
unsigned i = 0,
e = Allocas.size();
i !=
e; ++
i)
652 RenamePassData::LocationVector Locations(Allocas.size());
656 std::vector<RenamePassData> RenamePassWorkList;
657 RenamePassWorkList.emplace_back(&
F.front(),
nullptr,
std::move(Values),
660 RenamePassData RPD =
std::move(RenamePassWorkList.back());
661 RenamePassWorkList.pop_back();
663 RenamePass(RPD.BB, RPD.Pred, RPD.Values, RPD.Locations, RenamePassWorkList);
664 }
while (!RenamePassWorkList.empty());
676 A->eraseFromParent();
680 for (
auto &DbgUsers : AllocaDbgUsers) {
681 for (
auto *DII : DbgUsers)
682 if (DII->isAddressOfVariable() || DII->getExpression()->startsWithDeref())
683 DII->eraseFromParent();
690 bool EliminatedAPHI =
true;
691 while (EliminatedAPHI) {
692 EliminatedAPHI =
false;
700 E = NewPhiNodes.
end();
709 EliminatedAPHI =
true;
723 E = NewPhiNodes.
end();
729 if (&
BB->front() != SomePHI)
745 return BBNumbers.
find(A)->second < BBNumbers.
find(
B)->second;
756 "PHI node has entry for a block which is not a predecessor!");
768 while ((SomePHI = dyn_cast<PHINode>(BBI++)) &&
792 Info.UsingBlocks.end());
797 for (
unsigned i = 0,
e = LiveInBlockWorklist.size();
i !=
e; ++
i) {
806 if (
SI->getOperand(1) != AI)
811 LiveInBlockWorklist[
i] = LiveInBlockWorklist.back();
812 LiveInBlockWorklist.pop_back();
818 if (
LoadInst *LI = dyn_cast<LoadInst>(
I))
828 while (!LiveInBlockWorklist.empty()) {
833 if (!LiveInBlocks.
insert(
BB).second)
845 LiveInBlockWorklist.push_back(
P);
853 bool PromoteMem2Reg::QueuePhiNode(
BasicBlock *
BB,
unsigned AllocaNo,
856 PHINode *&PN = NewPhiNodes[std::make_pair(BBNumbers[
BB], AllocaNo)];
868 PhiToAllocaMap[PN] = AllocaNo;
875 bool ApplyMergedLoc) {
888 RenamePassData::ValVector &IncomingVals,
889 RenamePassData::LocationVector &IncomingLocs,
890 std::vector<RenamePassData> &Worklist) {
894 if (
PHINode *APN = dyn_cast<PHINode>(
BB->begin())) {
897 if (PhiToAllocaMap.
count(APN)) {
904 unsigned NewPHINumOperands = APN->getNumOperands();
907 assert(NumEdges &&
"Must be at least one edge from Pred to BB!");
912 unsigned AllocaNo = PhiToAllocaMap[APN];
916 APN->getNumIncomingValues() > 0);
919 for (
unsigned i = 0;
i != NumEdges; ++
i)
920 APN->addIncoming(IncomingVals[AllocaNo], Pred);
923 IncomingVals[AllocaNo] = APN;
925 if (DII->isAddressOfVariable())
930 APN = dyn_cast<PHINode>(PNI);
936 }
while (APN->getNumOperands() == NewPHINumOperands);
947 if (
LoadInst *LI = dyn_cast<LoadInst>(
I)) {
953 if (AI == AllocaLookup.
end())
956 Value *V = IncomingVals[AI->second];
961 if (AC && LI->
getMetadata(LLVMContext::MD_nonnull) &&
967 BB->getInstList().erase(LI);
971 AllocaInst *Dest = dyn_cast<AllocaInst>(
SI->getPointerOperand());
976 if (ai == AllocaLookup.
end())
980 unsigned AllocaNo = ai->second;
981 IncomingVals[AllocaNo] =
SI->getOperand(0);
984 IncomingLocs[AllocaNo] =
SI->getDebugLoc();
986 if (DII->isAddressOfVariable())
988 BB->getInstList().erase(
SI);
1007 if (VisitedSuccs.
insert(*I).second)
1008 Worklist.emplace_back(*
I, Pred, IncomingVals, IncomingLocs);
1016 if (Allocas.
empty())
1019 PromoteMem2Reg(Allocas, DT, AC).run();
DIExpression * getExpression() const
pred_range predecessors(BasicBlock *BB)
static StringRef getName(Value *V)
void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, StoreInst *SI, DIBuilder &Builder)
===------------------------------------------------------------------—===// Dbg Intrinsic utilities
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
static void dropDroppableUse(Use &U)
Remove the droppable use U.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
A parsed version of the target data layout string in and methods for querying it.
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
InstListType::iterator iterator
Instruction iterators...
const Function * getParent() const
Return the enclosing method, or null if none.
Interval::succ_iterator succ_end(Interval *I)
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
This class represents a no-op cast from one type to another.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool erase(const KeyT &Val)
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.
const_iterator end(StringRef path)
Get end iterator over path.
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
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...
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.
Value * getPointerOperand()
succ_range successors(Instruction *I)
bool empty() const
empty - Check if the array is empty.
LLVM Basic Block Representation.
static void clear(coro::Shape &Shape)
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
This class represents a conversion between pointers from one address space to another.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool isAddressOfVariable() const
Does this describe the address of a local variable.
Function object to check whether the first component of a std::pair compares less than the first comp...
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
void applyMergedLocation(const DILocation *LocA, const DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
iterator_range< use_iterator > uses()
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
STATISTIC(NumFunctions, "Total number of functions")
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Analysis containing CSE Info
unsigned getNumIncomingValues() const
Return the number of incoming edges.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
bool onlyUsedByLifetimeMarkersOrDroppableInsts(const Value *V)
Return true if the only users of this pointer are lifetime markers or droppable instructions.
This is the common base class for debug info intrinsics for variables.
An instruction for storing to memory.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
This instruction compares its operands according to the predicate given to the constructor.
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...
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
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...
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
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...
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
bool isDroppable() const
A droppable user is a user for which uses can be dropped without affecting correctness and should be ...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
A cache of @llvm.assume calls within a function.
Type * getType() const
All values are typed, get the type of this value.
unsigned pred_size(const BasicBlock *BB)
Get the number of predecessors of BB.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
static const Function * getParent(const Value *V)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
An instruction for reading from memory.
LLVM_NODISCARD bool empty() const
bool onlyUsedByLifetimeMarkers(const Value *V)
Return true if the only users of this pointer are lifetime markers.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
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...
void sort(IteratorTy Start, IteratorTy End)
A wrapper class for inspecting calls to intrinsic functions.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
bool startsWithDeref() const
Return whether the first element a DW_OP_deref.
const BasicBlock * getParent() const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
This class represents a function call, abstracting a target machine's calling convention.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
an instruction to allocate memory on the stack
Value * getOperand(unsigned i) const
LLVM Value Representation.
iterator_range< user_iterator > users()
bool isAllocaPromotable(const AllocaInst *AI)
Return true if this alloca is legal for promotion.
A Use represents the edge between a Value definition and its users.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.