43#include "llvm/Config/llvm-config.h"
65#define DEBUG_TYPE "stack-coloring"
80 cl::desc(
"Do not optimize lifetime zones that "
90 cl::desc(
"Treat stack lifetimes as starting on first use, not on START marker."));
93STATISTIC(NumMarkerSeen,
"Number of lifetime markers found.");
94STATISTIC(StackSpaceSaved,
"Number of bytes saved due to merging slots.");
95STATISTIC(StackSlotMerged,
"Number of stack slot merged.");
96STATISTIC(EscapedAllocas,
"Number of allocas that escaped the lifetime region");
386 struct BlockLifetimeInfo {
402 LivenessMap BlockLiveness;
436 unsigned NumIterations;
454 void dumpIntervals()
const;
456 void dumpBV(
const char *tag,
const BitVector &BV)
const;
460 bool removeAllMarkers();
465 unsigned collectMarkers(
unsigned NumSlot);
471 void calculateLocalLiveness();
475 bool applyFirstUse(
int Slot) {
478 if (ConservativeSlots.
test(Slot))
493 void calculateLiveIntervals(
unsigned NumSlots);
505 void removeInvalidSlotRanges();
514char StackColoring::ID = 0;
519 "Merge disjoint stack slots",
false,
false)
524void StackColoring::getAnalysisUsage(
AnalysisUsage &AU)
const {
529#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
532 dbgs() << tag <<
" : { ";
533 for (
unsigned I = 0, E = BV.
size();
I != E; ++
I)
539 LivenessMap::const_iterator BI = BlockLiveness.find(
MBB);
540 assert(BI != BlockLiveness.end() &&
"Block not found");
541 const BlockLifetimeInfo &BlockInfo = BI->second;
543 dumpBV(
"BEGIN", BlockInfo.Begin);
544 dumpBV(
"END", BlockInfo.End);
545 dumpBV(
"LIVE_IN", BlockInfo.LiveIn);
546 dumpBV(
"LIVE_OUT", BlockInfo.LiveOut);
558 for (
unsigned I = 0, E = Intervals.
size();
I != E; ++
I) {
559 dbgs() <<
"Interval[" <<
I <<
"]:\n";
560 Intervals[
I]->dump();
567 assert((
MI.getOpcode() == TargetOpcode::LIFETIME_START ||
568 MI.getOpcode() == TargetOpcode::LIFETIME_END) &&
569 "Expected LIFETIME_START or LIFETIME_END op");
584 if (
MI.getOpcode() == TargetOpcode::LIFETIME_START ||
585 MI.getOpcode() == TargetOpcode::LIFETIME_END) {
589 if (!InterestingSlots.
test(Slot))
591 slots.push_back(Slot);
592 if (
MI.getOpcode() == TargetOpcode::LIFETIME_END) {
596 if (!applyFirstUse(Slot)) {
601 if (!
MI.isDebugInstr()) {
606 int Slot = MO.getIndex();
609 if (InterestingSlots.
test(Slot) && applyFirstUse(Slot)) {
610 slots.push_back(Slot);
623unsigned StackColoring::collectMarkers(
unsigned NumSlot) {
624 unsigned MarkersFound = 0;
625 BlockBitVecMap SeenStartMap;
626 InterestingSlots.
clear();
627 InterestingSlots.
resize(NumSlot);
628 ConservativeSlots.
clear();
629 ConservativeSlots.
resize(NumSlot);
642 BetweenStartEnd.
resize(NumSlot);
644 BlockBitVecMap::const_iterator
I = SeenStartMap.find(Pred);
645 if (
I != SeenStartMap.end()) {
646 BetweenStartEnd |=
I->second;
652 if (
MI.isDebugInstr())
654 if (
MI.getOpcode() == TargetOpcode::LIFETIME_START ||
655 MI.getOpcode() == TargetOpcode::LIFETIME_END) {
659 InterestingSlots.
set(Slot);
660 if (
MI.getOpcode() == TargetOpcode::LIFETIME_START) {
661 BetweenStartEnd.
set(Slot);
662 NumStartLifetimes[
Slot] += 1;
664 BetweenStartEnd.
reset(Slot);
665 NumEndLifetimes[
Slot] += 1;
675 <<
" with allocation: " << Allocation->
getName() <<
"\n");
683 int Slot = MO.getIndex();
686 if (! BetweenStartEnd.
test(Slot)) {
687 ConservativeSlots.
set(Slot);
693 SeenStart |= BetweenStartEnd;
701 for (
unsigned slot = 0; slot < NumSlot; ++slot) {
702 if (NumStartLifetimes[slot] > 1 || NumEndLifetimes[slot] > 1)
703 ConservativeSlots.
set(slot);
713 if (
H.CatchObj.FrameIndex != std::numeric_limits<int>::max() &&
714 H.CatchObj.FrameIndex >= 0)
715 ConservativeSlots.
set(
H.CatchObj.FrameIndex);
717 LLVM_DEBUG(dumpBV(
"Conservative slots", ConservativeSlots));
725 BasicBlocks[
MBB] = BasicBlockNumbering.
size();
729 BlockLifetimeInfo &BlockInfo = BlockLiveness[
MBB];
731 BlockInfo.Begin.resize(NumSlot);
732 BlockInfo.End.resize(NumSlot);
736 bool isStart =
false;
738 if (isLifetimeStartOrEnd(
MI,
slots, isStart)) {
740 assert(
slots.size() == 1 &&
"unexpected: MI ends multiple slots");
742 if (BlockInfo.Begin.test(Slot)) {
743 BlockInfo.Begin.reset(Slot);
745 BlockInfo.End.set(Slot);
747 for (
auto Slot :
slots) {
755 <<
" with allocation: " << Allocation->
getName());
758 if (BlockInfo.End.test(Slot)) {
759 BlockInfo.End.reset(Slot);
761 BlockInfo.Begin.set(Slot);
769 NumMarkerSeen += MarkersFound;
773void StackColoring::calculateLocalLiveness() {
774 unsigned NumIters = 0;
782 LivenessMap::iterator BI = BlockLiveness.find(BB);
783 assert(BI != BlockLiveness.end() &&
"Block not found");
784 BlockLifetimeInfo &BlockInfo = BI->second;
789 LivenessMap::const_iterator
I = BlockLiveness.find(Pred);
793 if (
I != BlockLiveness.end())
794 LocalLiveIn |=
I->second.LiveOut;
805 LocalLiveOut.
reset(BlockInfo.End);
806 LocalLiveOut |= BlockInfo.Begin;
809 if (LocalLiveIn.
test(BlockInfo.LiveIn)) {
811 BlockInfo.LiveIn |= LocalLiveIn;
815 if (LocalLiveOut.
test(BlockInfo.LiveOut)) {
817 BlockInfo.LiveOut |= LocalLiveOut;
822 NumIterations = NumIters;
825void StackColoring::calculateLiveIntervals(
unsigned NumSlots) {
834 DefinitelyInUse.
clear();
835 DefinitelyInUse.
resize(NumSlots);
838 BlockLifetimeInfo &MBBLiveness = BlockLiveness[&
MBB];
839 for (
int pos = MBBLiveness.LiveIn.find_first(); pos != -1;
840 pos = MBBLiveness.LiveIn.find_next(pos)) {
847 bool IsStart =
false;
848 if (!isLifetimeStartOrEnd(
MI,
slots, IsStart))
851 for (
auto Slot :
slots) {
856 if (!DefinitelyInUse[Slot]) {
858 DefinitelyInUse[
Slot] =
true;
861 Starts[
Slot] = ThisIndex;
864 VNInfo *VNI = Intervals[
Slot]->getValNumInfo(0);
865 Intervals[
Slot]->addSegment(
868 DefinitelyInUse[
Slot] =
false;
875 for (
unsigned i = 0; i < NumSlots; ++i) {
880 VNInfo *VNI = Intervals[i]->getValNumInfo(0);
886bool StackColoring::removeAllMarkers() {
889 MI->eraseFromParent();
899 unsigned FixedInstr = 0;
900 unsigned FixedMemOp = 0;
901 unsigned FixedDbg = 0;
904 for (
auto &VI : MF->getVariableDbgInfo()) {
905 if (!
VI.Var || !
VI.inStackSlot())
907 int Slot =
VI.getStackSlot();
908 if (SlotRemap.
count(Slot)) {
910 << cast<DILocalVariable>(
VI.Var)->getName() <<
"].\n");
911 VI.updateStackSlot(SlotRemap[Slot]);
922 for (
const std::pair<int, int> &SI : SlotRemap) {
925 assert(To &&
From &&
"Invalid allocation object");
930 if (
From->comesBefore(To))
967 for (
auto &
Use : FromAI->
uses()) {
969 if (BCI->isUsedByMetadata())
980 std::vector<std::vector<MachineMemOperand *>> SSRefs(
985 if (
I.getOpcode() == TargetOpcode::LIFETIME_START ||
986 I.getOpcode() == TargetOpcode::LIFETIME_END)
993 const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(MMO->getValue());
997 if (!Allocas.
count(AI))
1000 MMO->setValue(Allocas[AI]);
1008 int FromSlot = MO.getIndex();
1015 if (!SlotRemap.count(FromSlot))
1026 bool TouchesMemory =
I.mayLoadOrStore();
1033 "Found instruction usage outside of live range.");
1038 int ToSlot = SlotRemap[FromSlot];
1039 MO.setIndex(ToSlot);
1045 bool ReplaceMemOps =
false;
1049 if (
const auto *FSV = dyn_cast_or_null<FixedStackPseudoSourceValue>(
1050 MMO->getPseudoValue())) {
1051 int FI = FSV->getFrameIndex();
1052 auto To = SlotRemap.find(FI);
1053 if (To != SlotRemap.end())
1054 SSRefs[FI].push_back(MMO);
1059 bool MayHaveConflictingAAMD =
false;
1060 if (MMO->getAAInfo()) {
1061 if (
const Value *MMOV = MMO->getValue()) {
1066 MayHaveConflictingAAMD =
true;
1068 for (
Value *V : Objs) {
1072 const AllocaInst *AI = dyn_cast_or_null<AllocaInst>(V);
1073 if (AI && MergedAllocas.
count(AI)) {
1074 MayHaveConflictingAAMD =
true;
1080 if (MayHaveConflictingAAMD) {
1082 ReplaceMemOps =
true;
1091 I.setMemRefs(*MF, NewMMOs);
1096 if (!E.value().empty()) {
1098 MF->getPSVManager().getFixedStack(SlotRemap.find(E.index())->second);
1100 Ref->setValue(NewSV);
1107 if (
H.CatchObj.FrameIndex != std::numeric_limits<int>::max() &&
1108 SlotRemap.count(
H.CatchObj.FrameIndex))
1109 H.CatchObj.FrameIndex = SlotRemap[
H.CatchObj.FrameIndex];
1111 LLVM_DEBUG(
dbgs() <<
"Fixed " << FixedMemOp <<
" machine memory operands.\n");
1112 LLVM_DEBUG(
dbgs() <<
"Fixed " << FixedDbg <<
" debug locations.\n");
1113 LLVM_DEBUG(
dbgs() <<
"Fixed " << FixedInstr <<
" machine instructions.\n");
1119void StackColoring::removeInvalidSlotRanges() {
1122 if (
I.getOpcode() == TargetOpcode::LIFETIME_START ||
1123 I.getOpcode() == TargetOpcode::LIFETIME_END ||
I.isDebugInstr())
1132 if (!
I.mayLoad() && !
I.mayStore())
1140 int Slot = MO.getIndex();
1145 if (Intervals[Slot]->empty())
1162 unsigned NumSlots) {
1164 for (
unsigned i=0; i < NumSlots; ++i) {
1166 if (SlotRemap.
count(i)) {
1167 int Target = SlotRemap[i];
1179 <<
"********** Function: " <<
Func.getName() <<
'\n');
1181 MFI = &MF->getFrameInfo();
1182 Indexes = &getAnalysis<SlotIndexes>();
1183 BlockLiveness.clear();
1184 BasicBlocks.
clear();
1185 BasicBlockNumbering.clear();
1189 VNInfoAllocator.
Reset();
1198 SortedSlots.
reserve(NumSlots);
1200 LiveStarts.
resize(NumSlots);
1202 unsigned NumMarkers = collectMarkers(NumSlots);
1204 unsigned TotalSize = 0;
1205 LLVM_DEBUG(
dbgs() <<
"Found " << NumMarkers <<
" markers and " << NumSlots
1215 LLVM_DEBUG(
dbgs() <<
"Total Stack size: " << TotalSize <<
" bytes\n\n");
1220 skipFunction(
Func.getFunction())) {
1222 return removeAllMarkers();
1225 for (
unsigned i=0; i < NumSlots; ++i) {
1226 std::unique_ptr<LiveInterval> LI(
new LiveInterval(i, 0));
1227 LI->getNextValue(Indexes->
getZeroIndex(), VNInfoAllocator);
1233 calculateLocalLiveness();
1234 LLVM_DEBUG(
dbgs() <<
"Dataflow iterations: " << NumIterations <<
"\n");
1238 calculateLiveIntervals(NumSlots);
1244 removeInvalidSlotRanges();
1248 unsigned RemovedSlots = 0;
1249 unsigned ReducedSize = 0;
1252 for (
unsigned I = 0;
I < NumSlots; ++
I) {
1253 if (Intervals[SortedSlots[
I]]->empty())
1254 SortedSlots[
I] = -1;
1275 for (
auto &s : LiveStarts)
1278 bool Changed =
true;
1281 for (
unsigned I = 0;
I < NumSlots; ++
I) {
1282 if (SortedSlots[
I] == -1)
1285 for (
unsigned J=
I+1; J < NumSlots; ++J) {
1286 if (SortedSlots[J] == -1)
1289 int FirstSlot = SortedSlots[
I];
1290 int SecondSlot = SortedSlots[J];
1298 auto &FirstS = LiveStarts[FirstSlot];
1299 auto &SecondS = LiveStarts[SecondSlot];
1304 if (!
First->isLiveAtIndexes(SecondS) &&
1307 First->MergeSegmentsInAsValue(*Second,
First->getValNumInfo(0));
1309 int OldSize = FirstS.size();
1310 FirstS.append(SecondS.begin(), SecondS.end());
1311 auto Mid = FirstS.begin() + OldSize;
1312 std::inplace_merge(FirstS.begin(), Mid, FirstS.end());
1314 SlotRemap[SecondSlot] = FirstSlot;
1315 SortedSlots[J] = -1;
1317 << SecondSlot <<
" together.\n");
1323 "Merging a small object into a larger one");
1335 StackSpaceSaved += ReducedSize;
1336 StackSlotMerged += RemovedSlots;
1337 LLVM_DEBUG(
dbgs() <<
"Merge " << RemovedSlots <<
" slots. Saved "
1338 << ReducedSize <<
" bytes\n");
1342 if (!SlotRemap.
empty()) {
1343 expungeSlotMap(SlotRemap, NumSlots);
1344 remapInstructions(SlotRemap);
1347 return removeAllMarkers();
This file implements the BitVector class.
BlockVerifier::State From
#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