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");
385 struct BlockLifetimeInfo {
401 LivenessMap BlockLiveness;
435 unsigned NumIterations;
453 void dumpIntervals()
const;
455 void dumpBV(
const char *tag,
const BitVector &BV)
const;
459 bool removeAllMarkers();
464 unsigned collectMarkers(
unsigned NumSlot);
470 void calculateLocalLiveness();
474 bool applyFirstUse(
int Slot) {
477 if (ConservativeSlots.
test(Slot))
492 void calculateLiveIntervals(
unsigned NumSlots);
504 void removeInvalidSlotRanges();
513char StackColoring::ID = 0;
518 "Merge disjoint stack slots",
false,
false)
523void StackColoring::getAnalysisUsage(
AnalysisUsage &AU)
const {
528#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
531 dbgs() << tag <<
" : { ";
532 for (
unsigned I = 0,
E = BV.
size();
I !=
E; ++
I)
538 LivenessMap::const_iterator BI = BlockLiveness.find(
MBB);
539 assert(BI != BlockLiveness.end() &&
"Block not found");
540 const BlockLifetimeInfo &BlockInfo = BI->second;
542 dumpBV(
"BEGIN", BlockInfo.Begin);
543 dumpBV(
"END", BlockInfo.End);
544 dumpBV(
"LIVE_IN", BlockInfo.LiveIn);
545 dumpBV(
"LIVE_OUT", BlockInfo.LiveOut);
557 for (
unsigned I = 0,
E = Intervals.
size();
I !=
E; ++
I) {
558 dbgs() <<
"Interval[" <<
I <<
"]:\n";
559 Intervals[
I]->dump();
566 assert((
MI.getOpcode() == TargetOpcode::LIFETIME_START ||
567 MI.getOpcode() == TargetOpcode::LIFETIME_END) &&
568 "Expected LIFETIME_START or LIFETIME_END op");
583 if (
MI.getOpcode() == TargetOpcode::LIFETIME_START ||
584 MI.getOpcode() == TargetOpcode::LIFETIME_END) {
588 if (!InterestingSlots.
test(Slot))
590 slots.push_back(Slot);
591 if (
MI.getOpcode() == TargetOpcode::LIFETIME_END) {
595 if (!applyFirstUse(Slot)) {
600 if (!
MI.isDebugInstr()) {
605 int Slot = MO.getIndex();
608 if (InterestingSlots.
test(Slot) && applyFirstUse(Slot)) {
609 slots.push_back(Slot);
622unsigned StackColoring::collectMarkers(
unsigned NumSlot) {
623 unsigned MarkersFound = 0;
624 BlockBitVecMap SeenStartMap;
625 InterestingSlots.
clear();
626 InterestingSlots.
resize(NumSlot);
627 ConservativeSlots.
clear();
628 ConservativeSlots.
resize(NumSlot);
641 BetweenStartEnd.
resize(NumSlot);
643 BlockBitVecMap::const_iterator
I = SeenStartMap.find(Pred);
644 if (
I != SeenStartMap.end()) {
645 BetweenStartEnd |=
I->second;
651 if (
MI.isDebugInstr())
653 if (
MI.getOpcode() == TargetOpcode::LIFETIME_START ||
654 MI.getOpcode() == TargetOpcode::LIFETIME_END) {
658 InterestingSlots.
set(Slot);
659 if (
MI.getOpcode() == TargetOpcode::LIFETIME_START) {
660 BetweenStartEnd.
set(Slot);
661 NumStartLifetimes[
Slot] += 1;
663 BetweenStartEnd.
reset(Slot);
664 NumEndLifetimes[
Slot] += 1;
674 <<
" with allocation: " << Allocation->
getName() <<
"\n");
682 int Slot = MO.getIndex();
685 if (! BetweenStartEnd.
test(Slot)) {
686 ConservativeSlots.
set(Slot);
692 SeenStart |= BetweenStartEnd;
700 for (
unsigned slot = 0; slot < NumSlot; ++slot) {
701 if (NumStartLifetimes[slot] > 1 || NumEndLifetimes[slot] > 1)
702 ConservativeSlots.
set(slot);
712 if (
H.CatchObj.FrameIndex != std::numeric_limits<int>::max() &&
713 H.CatchObj.FrameIndex >= 0)
714 ConservativeSlots.
set(
H.CatchObj.FrameIndex);
716 LLVM_DEBUG(dumpBV(
"Conservative slots", ConservativeSlots));
724 BasicBlocks[
MBB] = BasicBlockNumbering.
size();
728 BlockLifetimeInfo &BlockInfo = BlockLiveness[
MBB];
730 BlockInfo.Begin.resize(NumSlot);
731 BlockInfo.End.resize(NumSlot);
735 bool isStart =
false;
737 if (isLifetimeStartOrEnd(
MI,
slots, isStart)) {
739 assert(
slots.size() == 1 &&
"unexpected: MI ends multiple slots");
741 if (BlockInfo.Begin.test(Slot)) {
742 BlockInfo.Begin.reset(Slot);
744 BlockInfo.End.set(Slot);
746 for (
auto Slot :
slots) {
754 <<
" with allocation: " << Allocation->
getName());
757 if (BlockInfo.End.test(Slot)) {
758 BlockInfo.End.reset(Slot);
760 BlockInfo.Begin.set(Slot);
768 NumMarkerSeen += MarkersFound;
772void StackColoring::calculateLocalLiveness() {
773 unsigned NumIters = 0;
781 LivenessMap::iterator BI = BlockLiveness.find(BB);
782 assert(BI != BlockLiveness.end() &&
"Block not found");
783 BlockLifetimeInfo &BlockInfo = BI->second;
788 LivenessMap::const_iterator
I = BlockLiveness.find(Pred);
792 if (
I != BlockLiveness.end())
793 LocalLiveIn |=
I->second.LiveOut;
804 LocalLiveOut.
reset(BlockInfo.End);
805 LocalLiveOut |= BlockInfo.Begin;
808 if (LocalLiveIn.
test(BlockInfo.LiveIn)) {
810 BlockInfo.LiveIn |= LocalLiveIn;
814 if (LocalLiveOut.
test(BlockInfo.LiveOut)) {
816 BlockInfo.LiveOut |= LocalLiveOut;
821 NumIterations = NumIters;
824void StackColoring::calculateLiveIntervals(
unsigned NumSlots) {
833 DefinitelyInUse.
clear();
834 DefinitelyInUse.
resize(NumSlots);
837 BlockLifetimeInfo &MBBLiveness = BlockLiveness[&
MBB];
838 for (
int pos = MBBLiveness.LiveIn.find_first(); pos != -1;
839 pos = MBBLiveness.LiveIn.find_next(pos)) {
846 bool IsStart =
false;
847 if (!isLifetimeStartOrEnd(
MI,
slots, IsStart))
850 for (
auto Slot :
slots) {
855 if (!DefinitelyInUse[Slot]) {
857 DefinitelyInUse[
Slot] =
true;
860 Starts[
Slot] = ThisIndex;
863 VNInfo *VNI = Intervals[
Slot]->getValNumInfo(0);
864 Intervals[
Slot]->addSegment(
867 DefinitelyInUse[
Slot] =
false;
874 for (
unsigned i = 0; i < NumSlots; ++i) {
879 VNInfo *VNI = Intervals[i]->getValNumInfo(0);
885bool StackColoring::removeAllMarkers() {
888 MI->eraseFromParent();
898 unsigned FixedInstr = 0;
899 unsigned FixedMemOp = 0;
900 unsigned FixedDbg = 0;
903 for (
auto &VI : MF->getVariableDbgInfo()) {
904 if (!
VI.Var || !
VI.inStackSlot())
906 int Slot =
VI.getStackSlot();
907 if (SlotRemap.
count(Slot)) {
909 << cast<DILocalVariable>(
VI.Var)->getName() <<
"].\n");
910 VI.updateStackSlot(SlotRemap[Slot]);
921 for (
const std::pair<int, int> &SI : SlotRemap) {
924 assert(To &&
From &&
"Invalid allocation object");
929 if (
From->comesBefore(To))
966 for (
auto &
Use : FromAI->
uses()) {
968 if (BCI->isUsedByMetadata())
979 std::vector<std::vector<MachineMemOperand *>> SSRefs(
984 if (
I.getOpcode() == TargetOpcode::LIFETIME_START ||
985 I.getOpcode() == TargetOpcode::LIFETIME_END)
992 const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(MMO->getValue());
996 if (!Allocas.
count(AI))
999 MMO->setValue(Allocas[AI]);
1007 int FromSlot = MO.getIndex();
1014 if (!SlotRemap.count(FromSlot))
1025 bool TouchesMemory =
I.mayLoadOrStore();
1032 "Found instruction usage outside of live range.");
1037 int ToSlot = SlotRemap[FromSlot];
1038 MO.setIndex(ToSlot);
1044 bool ReplaceMemOps =
false;
1048 if (
const auto *FSV = dyn_cast_or_null<FixedStackPseudoSourceValue>(
1049 MMO->getPseudoValue())) {
1050 int FI = FSV->getFrameIndex();
1051 auto To = SlotRemap.find(FI);
1052 if (To != SlotRemap.end())
1053 SSRefs[FI].push_back(MMO);
1058 bool MayHaveConflictingAAMD =
false;
1059 if (MMO->getAAInfo()) {
1060 if (
const Value *MMOV = MMO->getValue()) {
1065 MayHaveConflictingAAMD =
true;
1067 for (
Value *V : Objs) {
1071 const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(V);
1072 if (AI && MergedAllocas.
count(AI)) {
1073 MayHaveConflictingAAMD =
true;
1079 if (MayHaveConflictingAAMD) {
1081 ReplaceMemOps =
true;
1090 I.setMemRefs(*MF, NewMMOs);
1095 if (!
E.value().empty()) {
1097 MF->getPSVManager().getFixedStack(SlotRemap.find(
E.index())->second);
1099 Ref->setValue(NewSV);
1106 if (
H.CatchObj.FrameIndex != std::numeric_limits<int>::max() &&
1107 SlotRemap.count(
H.CatchObj.FrameIndex))
1108 H.CatchObj.FrameIndex = SlotRemap[
H.CatchObj.FrameIndex];
1110 LLVM_DEBUG(
dbgs() <<
"Fixed " << FixedMemOp <<
" machine memory operands.\n");
1111 LLVM_DEBUG(
dbgs() <<
"Fixed " << FixedDbg <<
" debug locations.\n");
1112 LLVM_DEBUG(
dbgs() <<
"Fixed " << FixedInstr <<
" machine instructions.\n");
1118void StackColoring::removeInvalidSlotRanges() {
1121 if (
I.getOpcode() == TargetOpcode::LIFETIME_START ||
1122 I.getOpcode() == TargetOpcode::LIFETIME_END ||
I.isDebugInstr())
1131 if (!
I.mayLoad() && !
I.mayStore())
1139 int Slot = MO.getIndex();
1144 if (Intervals[Slot]->empty())
1161 unsigned NumSlots) {
1163 for (
unsigned i=0; i < NumSlots; ++i) {
1165 if (SlotRemap.
count(i)) {
1166 int Target = SlotRemap[i];
1178 <<
"********** Function: " <<
Func.getName() <<
'\n');
1180 MFI = &MF->getFrameInfo();
1181 Indexes = &getAnalysis<SlotIndexes>();
1182 BlockLiveness.clear();
1183 BasicBlocks.
clear();
1184 BasicBlockNumbering.clear();
1188 VNInfoAllocator.
Reset();
1197 SortedSlots.
reserve(NumSlots);
1199 LiveStarts.
resize(NumSlots);
1201 unsigned NumMarkers = collectMarkers(NumSlots);
1203 unsigned TotalSize = 0;
1204 LLVM_DEBUG(
dbgs() <<
"Found " << NumMarkers <<
" markers and " << NumSlots
1214 LLVM_DEBUG(
dbgs() <<
"Total Stack size: " << TotalSize <<
" bytes\n\n");
1219 skipFunction(
Func.getFunction())) {
1221 return removeAllMarkers();
1224 for (
unsigned i=0; i < NumSlots; ++i) {
1225 std::unique_ptr<LiveInterval> LI(
new LiveInterval(i, 0));
1226 LI->getNextValue(Indexes->
getZeroIndex(), VNInfoAllocator);
1232 calculateLocalLiveness();
1233 LLVM_DEBUG(
dbgs() <<
"Dataflow iterations: " << NumIterations <<
"\n");
1237 calculateLiveIntervals(NumSlots);
1243 removeInvalidSlotRanges();
1247 unsigned RemovedSlots = 0;
1248 unsigned ReducedSize = 0;
1251 for (
unsigned I = 0;
I < NumSlots; ++
I) {
1252 if (Intervals[SortedSlots[
I]]->empty())
1253 SortedSlots[
I] = -1;
1274 for (
auto &s : LiveStarts)
1277 bool Changed =
true;
1280 for (
unsigned I = 0;
I < NumSlots; ++
I) {
1281 if (SortedSlots[
I] == -1)
1284 for (
unsigned J=
I+1; J < NumSlots; ++J) {
1285 if (SortedSlots[J] == -1)
1288 int FirstSlot = SortedSlots[
I];
1289 int SecondSlot = SortedSlots[J];
1297 auto &FirstS = LiveStarts[FirstSlot];
1298 auto &SecondS = LiveStarts[SecondSlot];
1303 if (!
First->isLiveAtIndexes(SecondS) &&
1306 First->MergeSegmentsInAsValue(*Second,
First->getValNumInfo(0));
1308 int OldSize = FirstS.size();
1309 FirstS.append(SecondS.begin(), SecondS.end());
1310 auto Mid = FirstS.begin() + OldSize;
1311 std::inplace_merge(FirstS.begin(), Mid, FirstS.end());
1313 SlotRemap[SecondSlot] = FirstSlot;
1314 SortedSlots[J] = -1;
1316 << SecondSlot <<
" together.\n");
1322 "Merging a small object into a larger one");
1334 StackSpaceSaved += ReducedSize;
1335 StackSlotMerged += RemovedSlots;
1336 LLVM_DEBUG(
dbgs() <<
"Merge " << RemovedSlots <<
" slots. Saved "
1337 << ReducedSize <<
" bytes\n");
1341 expungeSlotMap(SlotRemap, NumSlots);
1342 remapInstructions(SlotRemap);
1344 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
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)
NodeAddr< FuncNode * > Func
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.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
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