42#include "llvm/Config/llvm-config.h"
64#define DEBUG_TYPE "stack-coloring"
79 cl::desc(
"Do not optimize lifetime zones that "
89 cl::desc(
"Treat stack lifetimes as starting on first use, not on START marker."));
92STATISTIC(NumMarkerSeen,
"Number of lifetime markers found.");
93STATISTIC(StackSpaceSaved,
"Number of bytes saved due to merging slots.");
94STATISTIC(StackSlotMerged,
"Number of stack slot merged.");
95STATISTIC(EscapedAllocas,
"Number of allocas that escaped the lifetime region");
416 struct BlockLifetimeInfo {
432 LivenessMap BlockLiveness;
469 unsigned NumIterations;
487 void dumpIntervals()
const;
489 void dumpBV(
const char *tag,
const BitVector &BV)
const;
493 bool removeAllMarkers();
498 unsigned collectMarkers(
unsigned NumSlot);
504 void calculateLocalLiveness();
508 bool applyFirstUse(
int Slot) {
511 if (ConservativeSlots.
test(Slot))
526 void calculateLiveIntervals(
unsigned NumSlots);
538 void removeInvalidSlotRanges();
547char StackColoring::ID = 0;
552 "Merge disjoint stack slots",
false,
false)
557void StackColoring::getAnalysisUsage(
AnalysisUsage &AU)
const {
562#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
565 dbgs() << tag <<
" : { ";
566 for (
unsigned I = 0,
E = BV.
size();
I !=
E; ++
I)
572 LivenessMap::const_iterator BI = BlockLiveness.find(
MBB);
573 assert(BI != BlockLiveness.end() &&
"Block not found");
574 const BlockLifetimeInfo &BlockInfo = BI->second;
576 dumpBV(
"BEGIN", BlockInfo.Begin);
577 dumpBV(
"END", BlockInfo.End);
578 dumpBV(
"LIVE_IN", BlockInfo.LiveIn);
579 dumpBV(
"LIVE_OUT", BlockInfo.LiveOut);
591 for (
unsigned I = 0,
E = Intervals.
size();
I !=
E; ++
I) {
592 dbgs() <<
"Interval[" <<
I <<
"]:\n";
593 Intervals[
I]->dump();
600 assert((
MI.getOpcode() == TargetOpcode::LIFETIME_START ||
601 MI.getOpcode() == TargetOpcode::LIFETIME_END) &&
602 "Expected LIFETIME_START or LIFETIME_END op");
617 if (
MI.getOpcode() == TargetOpcode::LIFETIME_START ||
618 MI.getOpcode() == TargetOpcode::LIFETIME_END) {
622 if (!InterestingSlots.
test(Slot))
624 slots.push_back(Slot);
625 if (
MI.getOpcode() == TargetOpcode::LIFETIME_END) {
629 if (!applyFirstUse(Slot)) {
634 if (!
MI.isDebugInstr()) {
639 int Slot = MO.getIndex();
642 if (InterestingSlots.
test(Slot) && applyFirstUse(Slot)) {
643 slots.push_back(Slot);
656unsigned StackColoring::collectMarkers(
unsigned NumSlot) {
657 unsigned MarkersFound = 0;
658 BlockBitVecMap SeenStartMap;
659 InterestingSlots.
clear();
660 InterestingSlots.
resize(NumSlot);
661 ConservativeSlots.
clear();
662 ConservativeSlots.
resize(NumSlot);
664 StoreSlots.
resize(NumSlot);
678 BetweenStartEnd.
resize(NumSlot);
680 BlockBitVecMap::const_iterator
I = SeenStartMap.find(Pred);
681 if (
I != SeenStartMap.end()) {
682 BetweenStartEnd |=
I->second;
688 if (
MI.isDebugInstr())
690 if (
MI.getOpcode() == TargetOpcode::LIFETIME_START ||
691 MI.getOpcode() == TargetOpcode::LIFETIME_END) {
695 InterestingSlots.
set(Slot);
696 if (
MI.getOpcode() == TargetOpcode::LIFETIME_START) {
697 BetweenStartEnd.
set(Slot);
698 NumStartLifetimes[
Slot] += 1;
700 BetweenStartEnd.
reset(Slot);
701 NumEndLifetimes[
Slot] += 1;
711 <<
" with allocation: " << Allocation->
getName() <<
"\n");
719 int Slot = MO.getIndex();
722 if (! BetweenStartEnd.
test(Slot)) {
723 ConservativeSlots.
set(Slot);
729 StoreSlots.
set(Slot);
731 NumLoadInCatchPad[
Slot] += 1;
736 SeenStart |= BetweenStartEnd;
745 for (
unsigned slot = 0; slot < NumSlot; ++slot) {
746 if (NumStartLifetimes[slot] > 1 || NumEndLifetimes[slot] > 1 ||
747 (NumLoadInCatchPad[slot] > 1 && !StoreSlots.
test(slot)))
748 ConservativeSlots.
set(slot);
750 LLVM_DEBUG(dumpBV(
"Conservative slots", ConservativeSlots));
758 BasicBlocks[
MBB] = BasicBlockNumbering.
size();
762 BlockLifetimeInfo &BlockInfo = BlockLiveness[
MBB];
764 BlockInfo.Begin.resize(NumSlot);
765 BlockInfo.End.resize(NumSlot);
769 bool isStart =
false;
771 if (isLifetimeStartOrEnd(
MI,
slots, isStart)) {
773 assert(
slots.size() == 1 &&
"unexpected: MI ends multiple slots");
775 if (BlockInfo.Begin.test(Slot)) {
776 BlockInfo.Begin.reset(Slot);
778 BlockInfo.End.set(Slot);
780 for (
auto Slot :
slots) {
788 <<
" with allocation: " << Allocation->
getName());
791 if (BlockInfo.End.test(Slot)) {
792 BlockInfo.End.reset(Slot);
794 BlockInfo.Begin.set(Slot);
802 NumMarkerSeen += MarkersFound;
806void StackColoring::calculateLocalLiveness() {
807 unsigned NumIters = 0;
815 LivenessMap::iterator BI = BlockLiveness.find(BB);
816 assert(BI != BlockLiveness.end() &&
"Block not found");
817 BlockLifetimeInfo &BlockInfo = BI->second;
822 LivenessMap::const_iterator
I = BlockLiveness.find(Pred);
826 if (
I != BlockLiveness.end())
827 LocalLiveIn |=
I->second.LiveOut;
838 LocalLiveOut.
reset(BlockInfo.End);
839 LocalLiveOut |= BlockInfo.Begin;
842 if (LocalLiveIn.
test(BlockInfo.LiveIn)) {
844 BlockInfo.LiveIn |= LocalLiveIn;
848 if (LocalLiveOut.
test(BlockInfo.LiveOut)) {
850 BlockInfo.LiveOut |= LocalLiveOut;
855 NumIterations = NumIters;
858void StackColoring::calculateLiveIntervals(
unsigned NumSlots) {
867 DefinitelyInUse.
clear();
868 DefinitelyInUse.
resize(NumSlots);
871 BlockLifetimeInfo &MBBLiveness = BlockLiveness[&
MBB];
872 for (
int pos = MBBLiveness.LiveIn.find_first(); pos != -1;
873 pos = MBBLiveness.LiveIn.find_next(pos)) {
880 bool IsStart =
false;
881 if (!isLifetimeStartOrEnd(
MI,
slots, IsStart))
884 for (
auto Slot :
slots) {
889 if (!DefinitelyInUse[Slot]) {
891 DefinitelyInUse[
Slot] =
true;
894 Starts[
Slot] = ThisIndex;
897 VNInfo *VNI = Intervals[
Slot]->getValNumInfo(0);
898 Intervals[
Slot]->addSegment(
901 DefinitelyInUse[
Slot] =
false;
908 for (
unsigned i = 0; i < NumSlots; ++i) {
913 VNInfo *VNI = Intervals[i]->getValNumInfo(0);
919bool StackColoring::removeAllMarkers() {
922 MI->eraseFromParent();
932 unsigned FixedInstr = 0;
933 unsigned FixedMemOp = 0;
934 unsigned FixedDbg = 0;
937 for (
auto &VI : MF->getVariableDbgInfo()) {
940 if (SlotRemap.
count(
VI.Slot)) {
942 << cast<DILocalVariable>(
VI.Var)->getName() <<
"].\n");
943 VI.Slot = SlotRemap[
VI.Slot];
954 for (
const std::pair<int, int> &SI : SlotRemap) {
957 assert(To &&
From &&
"Invalid allocation object");
962 if (
From->comesBefore(To))
999 for (
auto &
Use : FromAI->
uses()) {
1001 if (BCI->isUsedByMetadata())
1012 std::vector<std::vector<MachineMemOperand *>> SSRefs(
1017 if (
I.getOpcode() == TargetOpcode::LIFETIME_START ||
1018 I.getOpcode() == TargetOpcode::LIFETIME_END)
1025 const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(MMO->getValue());
1029 if (!Allocas.
count(AI))
1032 MMO->setValue(Allocas[AI]);
1040 int FromSlot = MO.getIndex();
1047 if (!SlotRemap.count(FromSlot))
1058 bool TouchesMemory =
I.mayLoadOrStore();
1065 "Found instruction usage outside of live range.");
1070 int ToSlot = SlotRemap[FromSlot];
1071 MO.setIndex(ToSlot);
1077 bool ReplaceMemOps =
false;
1081 if (
const auto *FSV = dyn_cast_or_null<FixedStackPseudoSourceValue>(
1082 MMO->getPseudoValue())) {
1083 int FI = FSV->getFrameIndex();
1084 auto To = SlotRemap.find(FI);
1085 if (To != SlotRemap.end())
1086 SSRefs[FI].push_back(MMO);
1091 bool MayHaveConflictingAAMD =
false;
1092 if (MMO->getAAInfo()) {
1093 if (
const Value *MMOV = MMO->getValue()) {
1098 MayHaveConflictingAAMD =
true;
1100 for (
Value *V : Objs) {
1104 const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(V);
1105 if (AI && MergedAllocas.
count(AI)) {
1106 MayHaveConflictingAAMD =
true;
1112 if (MayHaveConflictingAAMD) {
1114 ReplaceMemOps =
true;
1123 I.setMemRefs(*MF, NewMMOs);
1128 if (!
E.value().empty()) {
1130 MF->getPSVManager().getFixedStack(SlotRemap.find(
E.index())->second);
1132 Ref->setValue(NewSV);
1139 if (
H.CatchObj.FrameIndex != std::numeric_limits<int>::max() &&
1140 SlotRemap.count(
H.CatchObj.FrameIndex))
1141 H.CatchObj.FrameIndex = SlotRemap[
H.CatchObj.FrameIndex];
1143 LLVM_DEBUG(
dbgs() <<
"Fixed " << FixedMemOp <<
" machine memory operands.\n");
1144 LLVM_DEBUG(
dbgs() <<
"Fixed " << FixedDbg <<
" debug locations.\n");
1145 LLVM_DEBUG(
dbgs() <<
"Fixed " << FixedInstr <<
" machine instructions.\n");
1151void StackColoring::removeInvalidSlotRanges() {
1154 if (
I.getOpcode() == TargetOpcode::LIFETIME_START ||
1155 I.getOpcode() == TargetOpcode::LIFETIME_END ||
I.isDebugInstr())
1164 if (!
I.mayLoad() && !
I.mayStore())
1172 int Slot = MO.getIndex();
1177 if (Intervals[Slot]->empty())
1194 unsigned NumSlots) {
1196 for (
unsigned i=0; i < NumSlots; ++i) {
1198 if (SlotRemap.
count(i)) {
1199 int Target = SlotRemap[i];
1211 <<
"********** Function: " <<
Func.getName() <<
'\n');
1213 MFI = &MF->getFrameInfo();
1214 Indexes = &getAnalysis<SlotIndexes>();
1215 BlockLiveness.clear();
1216 BasicBlocks.
clear();
1217 BasicBlockNumbering.clear();
1221 VNInfoAllocator.
Reset();
1230 SortedSlots.
reserve(NumSlots);
1232 LiveStarts.
resize(NumSlots);
1234 unsigned NumMarkers = collectMarkers(NumSlots);
1236 unsigned TotalSize = 0;
1237 LLVM_DEBUG(
dbgs() <<
"Found " << NumMarkers <<
" markers and " << NumSlots
1247 LLVM_DEBUG(
dbgs() <<
"Total Stack size: " << TotalSize <<
" bytes\n\n");
1252 skipFunction(
Func.getFunction())) {
1254 return removeAllMarkers();
1257 for (
unsigned i=0; i < NumSlots; ++i) {
1258 std::unique_ptr<LiveInterval> LI(
new LiveInterval(i, 0));
1259 LI->getNextValue(Indexes->
getZeroIndex(), VNInfoAllocator);
1265 calculateLocalLiveness();
1266 LLVM_DEBUG(
dbgs() <<
"Dataflow iterations: " << NumIterations <<
"\n");
1270 calculateLiveIntervals(NumSlots);
1276 removeInvalidSlotRanges();
1280 unsigned RemovedSlots = 0;
1281 unsigned ReducedSize = 0;
1284 for (
unsigned I = 0;
I < NumSlots; ++
I) {
1285 if (Intervals[SortedSlots[
I]]->empty())
1286 SortedSlots[
I] = -1;
1307 for (
auto &s : LiveStarts)
1310 bool Changed =
true;
1313 for (
unsigned I = 0;
I < NumSlots; ++
I) {
1314 if (SortedSlots[
I] == -1)
1317 for (
unsigned J=
I+1; J < NumSlots; ++J) {
1318 if (SortedSlots[J] == -1)
1321 int FirstSlot = SortedSlots[
I];
1322 int SecondSlot = SortedSlots[J];
1330 auto &FirstS = LiveStarts[FirstSlot];
1331 auto &SecondS = LiveStarts[SecondSlot];
1336 if (!
First->isLiveAtIndexes(SecondS) &&
1339 First->MergeSegmentsInAsValue(*Second,
First->getValNumInfo(0));
1341 int OldSize = FirstS.size();
1342 FirstS.append(SecondS.begin(), SecondS.end());
1343 auto Mid = FirstS.begin() + OldSize;
1344 std::inplace_merge(FirstS.begin(), Mid, FirstS.end());
1346 SlotRemap[SecondSlot] = FirstSlot;
1347 SortedSlots[J] = -1;
1349 << SecondSlot <<
" together.\n");
1355 "Merging a small object into a larger one");
1367 StackSpaceSaved += ReducedSize;
1368 StackSlotMerged += RemovedSlots;
1369 LLVM_DEBUG(
dbgs() <<
"Merge " << RemovedSlots <<
" slots. Saved "
1370 << ReducedSize <<
" bytes\n");
1374 expungeSlotMap(SlotRemap, NumSlots);
1375 remapInstructions(SlotRemap);
1377 return removeAllMarkers();
This file implements the BitVector class.
BlockVerifier::State From
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
static int getStartOrEndSlot(const MachineInstr &MI)
static cl::opt< bool > DisableColoring("no-stack-coloring", cl::init(false), cl::Hidden, cl::desc("Disable stack coloring"))
static cl::opt< bool > ProtectFromEscapedAllocas("protect-from-escaped-allocas", cl::init(false), cl::Hidden, cl::desc("Do not optimize lifetime zones that " "are broken"))
The user may write code that uses allocas outside of the declared lifetime zone.
static cl::opt< bool > LifetimeStartOnFirstUse("stackcoloring-lifetime-start-on-first-use", cl::init(true), cl::Hidden, cl::desc("Treat stack lifetimes as starting on first use, not on START marker."))
Enable enhanced dataflow scheme for lifetime analysis (treat first use of stack slot as start of slot...
Merge disjoint stack slots
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
This defines the Use class.
an instruction to allocate memory on the stack
PointerType * getType() const
Overload to return most specific pointer type.
Represent the analysis usage information of a pass.
This class represents a no-op cast from one type to another.
bool test(unsigned Idx) const
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
void clear()
clear - Removes all bits from the bitvector.
size_type size() const
size - Returns the number of bits in this bitvector.
Allocate memory in an ever growing pool, as if by bump-pointer.
void Reset()
Deallocate all but the current slab and reset the current pointer to the beginning of it,...
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
LiveInterval - This class represents the liveness of a register, or stack slot.
bool isLiveAtIndexes(ArrayRef< SlotIndex > Slots) const
bool isEHPad() const
Returns true if the block is a landing pad.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator_range< pred_iterator > predecessors()
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
SSPLayoutKind getObjectSSPLayout(int ObjectIdx) const
const AllocaInst * getObjectAllocation(int ObjectIdx) const
Return the underlying Alloca of the specified stack object if it exists.
SSPLayoutKind
Stack Smashing Protection (SSP) rules require that vulnerable stack allocations are located close the...
@ SSPLK_LargeArray
Array or nested array >= SSP-buffer-size.
@ SSPLK_AddrOf
The address of this allocation is exposed and triggered protection.
@ SSPLK_None
Did not trigger a stack protector.
void setObjectSSPLayout(int ObjectIdx, SSPLayoutKind Kind)
Align getObjectAlign(int ObjectIdx) const
Return the alignment of the specified stack object.
int64_t getObjectSize(int ObjectIdx) const
Return the size of the specified object.
void RemoveStackObject(int ObjectIdx)
Remove or mark dead a statically sized stack object.
int getObjectIndexEnd() const
Return one past the maximum frame object index.
uint8_t getStackID(int ObjectIdx) const
void setObjectAlignment(int ObjectIdx, Align Alignment)
setObjectAlignment - Change the alignment of the specified stack object.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const WinEHFuncInfo * getWinEHFuncInfo() const
getWinEHFuncInfo - Return information about how the current function uses Windows exception handling.
Representation of each machine instruction.
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Special value supplied for machine level alias analysis.
SlotIndex - An opaque wrapper around machine indexes.
void print(raw_ostream &os) const
Print this index to the given raw_ostream.
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
SlotIndex getZeroIndex()
Returns the zero index for this analysis.
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.
void reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Target - Wrapper for Target specific information.
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.
VNInfo - Value Number Information.
LLVM Value Representation.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
bool isUsedByMetadata() const
Return true if there is metadata referencing this value.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
void stable_sort(R &&Range)
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
void initializeStackColoringPass(PassRegistry &)
bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value * > &Objects)
This is a wrapper around getUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
char & StackColoringID
StackSlotColoring - This pass performs stack coloring and merging.
@ Ref
The access may reference the value stored in memory.
iterator_range< df_iterator< T > > depth_first(const T &G)
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
This struct is a compact representation of a valid (non-zero power of two) alignment.
This represents a simple continuous liveness interval for a value.
SmallVector< WinEHHandlerType, 1 > HandlerArray