From 0a16da445740ca6fcd7a7ca571c1917e77315904 Mon Sep 17 00:00:00 2001 From: Nadav Rotem Date: Wed, 12 Sep 2012 04:57:37 +0000 Subject: Stack coloring: remove lifetime intervals which contain escaped allocas. The input program may contain intructions which are not inside lifetime markers. This can happen due to a bug in the compiler or due to a bug in user code (for example, returning a reference to a local variable). This commit adds checks that all of the instructions in the function and invalidates lifetime ranges which do not contain all of the instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163678 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/StackColoring.cpp | 47 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 47 insertions(+) (limited to 'lib/CodeGen/StackColoring.cpp') diff --git a/lib/CodeGen/StackColoring.cpp b/lib/CodeGen/StackColoring.cpp index 6df932c1ae..16b715a796 100644 --- a/lib/CodeGen/StackColoring.cpp +++ b/lib/CodeGen/StackColoring.cpp @@ -158,6 +158,14 @@ private: /// slots to use the joint slots. void remapInstructions(DenseMap &SlotRemap); + /// The input program may contain intructions which are not inside lifetime + /// markers. This can happen due to a bug in the compiler or due to a bug in + /// user code (for example, returning a reference to a local variable). + /// This procedure checks all of the instructions in the function and + /// invalidates lifetime ranges which do not contain all of the instructions + /// which access that frame slot. + void removeInvalidSlotRanges(); + /// Map entries which point to other entries to their destination. /// A->B->C becomes A->C. void expungeSlotMap(DenseMap &SlotRemap, unsigned NumSlots); @@ -543,6 +551,43 @@ void StackColoring::remapInstructions(DenseMap &SlotRemap) { DEBUG(dbgs()<<"Fixed "<begin(), BBE = MF->end(); BB != BBE; ++BB) + for (I = BB->begin(), IE = BB->end(); I != IE; ++I) { + + if (I->getOpcode() == TargetOpcode::LIFETIME_START || + I->getOpcode() == TargetOpcode::LIFETIME_END || I->isDebugValue()) + continue; + + // Check all of the machine operands. + for (unsigned i = 0 ; i < I->getNumOperands(); ++i) { + MachineOperand &MO = I->getOperand(i); + + if (!MO.isFI()) + continue; + + int Slot = MO.getIndex(); + + if (Slot<0) + continue; + + if (Intervals[Slot]->empty()) + continue; + + // Check that the used slot is inside the calculated lifetime range. + // If it is not, warn about it and invalidate the range. + LiveInterval *Interval = Intervals[Slot]; + SlotIndex Index = Indexes->getInstructionIndex(I); + if (Interval->find(Index) == Interval->end()) { + Intervals[Slot]->clear(); + DEBUG(dbgs()<<"Invalidating range #"< &SlotRemap, unsigned NumSlots) { // Expunge slot remap map. @@ -617,6 +662,8 @@ bool StackColoring::runOnMachineFunction(MachineFunction &Func) { // Propagate the liveness information. calculateLiveIntervals(NumSlots); + removeInvalidSlotRanges(); + // Maps old slots to new slots. DenseMap SlotRemap; unsigned RemovedSlots = 0; -- cgit v1.2.3-18-g5258 From dba5de5246f84fe50aef79e464e5aecdf5607ab4 Mon Sep 17 00:00:00 2001 From: Nadav Rotem Date: Wed, 12 Sep 2012 07:58:35 +0000 Subject: Enable stack-coloring, in hope that the recent fixes will enable correct dragonegg self-hosting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163687 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/StackColoring.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/CodeGen/StackColoring.cpp') diff --git a/lib/CodeGen/StackColoring.cpp b/lib/CodeGen/StackColoring.cpp index 16b715a796..0deb35ad7f 100644 --- a/lib/CodeGen/StackColoring.cpp +++ b/lib/CodeGen/StackColoring.cpp @@ -59,7 +59,7 @@ using namespace llvm; static cl::opt DisableColoring("no-stack-coloring", - cl::init(true), cl::Hidden, + cl::init(false), cl::Hidden, cl::desc("Suppress stack coloring")); STATISTIC(NumMarkerSeen, "Number of life markers found."); -- cgit v1.2.3-18-g5258 From d76f6eadc8c8511e1c5cd089a8a54e429c19aa60 Mon Sep 17 00:00:00 2001 From: Nadav Rotem Date: Wed, 12 Sep 2012 11:06:26 +0000 Subject: Add a flag to disable the code that looks for allocas which escaped the lifetime regions. This is useful for debugging. No testcase because without this check we fail on assertions when finding escaped allocas. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163702 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/StackColoring.cpp | 24 ++++++++++++++++++------ 1 file changed, 18 insertions(+), 6 deletions(-) (limited to 'lib/CodeGen/StackColoring.cpp') diff --git a/lib/CodeGen/StackColoring.cpp b/lib/CodeGen/StackColoring.cpp index 0deb35ad7f..a14d730025 100644 --- a/lib/CodeGen/StackColoring.cpp +++ b/lib/CodeGen/StackColoring.cpp @@ -59,12 +59,20 @@ using namespace llvm; static cl::opt DisableColoring("no-stack-coloring", - cl::init(false), cl::Hidden, - cl::desc("Suppress stack coloring")); + cl::init(false), cl::Hidden, + cl::desc("Disable stack coloring")); -STATISTIC(NumMarkerSeen, "Number of life markers found."); +static cl::opt +CheckEscapedAllocas("stack-coloring-check-escaped", + cl::init(true), cl::Hidden, + cl::desc("Look for allocas which escaped the lifetime region")); + +STATISTIC(NumMarkerSeen, "Number of lifetime markers found."); STATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots."); STATISTIC(StackSlotMerged, "Number of stack slot merged."); +STATISTIC(EscapedAllocas, + "Number of allocas that escaped the lifetime region"); + //===----------------------------------------------------------------------===// // StackColoring Pass @@ -104,7 +112,7 @@ class StackColoring : public MachineFunctionPass { /// VNInfo is used for the construction of LiveIntervals. VNInfo::Allocator VNInfoAllocator; /// SlotIndex analysis object. - SlotIndexes* Indexes; + SlotIndexes *Indexes; /// The list of lifetime markers found. These markers are to be removed /// once the coloring is done. @@ -533,7 +541,7 @@ void StackColoring::remapInstructions(DenseMap &SlotRemap) { #ifndef NDEBUG if (!I->isDebugValue()) { SlotIndex Index = Indexes->getInstructionIndex(I); - LiveInterval* Interval = Intervals[FromSlot]; + LiveInterval *Interval = Intervals[FromSlot]; assert(Interval->find(Index) != Interval->end() && "Found instruction usage outside of live range."); } @@ -583,6 +591,7 @@ void StackColoring::removeInvalidSlotRanges() { if (Interval->find(Index) == Interval->end()) { Intervals[Slot]->clear(); DEBUG(dbgs()<<"Invalidating range #"< SlotRemap; -- cgit v1.2.3-18-g5258 From 0cd19b93017fcaba737b15ea4da39c460feb5670 Mon Sep 17 00:00:00 2001 From: Nadav Rotem Date: Thu, 13 Sep 2012 12:38:37 +0000 Subject: Stack Coloring: We have code that checks that all of the uses of allocas are within the lifetime zone. Sometime legitimate usages of allocas are hoisted outside of the lifetime zone. For example, GEPS may calculate the address of a member of an allocated struct. This commit makes sure that we only check (abort regions or assert) for instructions that read and write memory using stack frames directly. Notice that by allowing legitimate usages outside the lifetime zone we also stop checking for instructions which use derivatives of allocas. We will catch less bugs in user code and in the compiler itself. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163791 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/StackColoring.cpp | 22 +++++++++++++++++----- 1 file changed, 17 insertions(+), 5 deletions(-) (limited to 'lib/CodeGen/StackColoring.cpp') diff --git a/lib/CodeGen/StackColoring.cpp b/lib/CodeGen/StackColoring.cpp index a14d730025..1a7801abd8 100644 --- a/lib/CodeGen/StackColoring.cpp +++ b/lib/CodeGen/StackColoring.cpp @@ -73,7 +73,6 @@ STATISTIC(StackSlotMerged, "Number of stack slot merged."); STATISTIC(EscapedAllocas, "Number of allocas that escaped the lifetime region"); - //===----------------------------------------------------------------------===// // StackColoring Pass //===----------------------------------------------------------------------===// @@ -259,8 +258,8 @@ unsigned StackColoring::collectMarkers(unsigned NumSlot) { const Value *Allocation = MFI->getObjectAllocation(Slot); if (Allocation) { - DEBUG(dbgs()<<"Found lifetime marker for allocation: "<< - Allocation->getName()<<"\n"); + DEBUG(dbgs()<<"Found a lifetime marker for slot #"<getName()<<"\n"); } if (IsStart) { @@ -538,8 +537,12 @@ void StackColoring::remapInstructions(DenseMap &SlotRemap) { // inside the expected live range. If the instruction is not inside // the calculated range then it means that the alloca usage moved // outside of the lifetime markers. + // NOTE: Alloca address calculations which happen outside the lifetime + // zone are are okay, despite the fact that we don't have a good way + // for validating all of the usages of the calculation. #ifndef NDEBUG - if (!I->isDebugValue()) { + bool TouchesMemory = I->mayLoad() || I->mayStore(); + if (!I->isDebugValue() && TouchesMemory) { SlotIndex Index = Indexes->getInstructionIndex(I); LiveInterval *Interval = Intervals[FromSlot]; assert(Interval->find(Index) != Interval->end() && @@ -569,6 +572,15 @@ void StackColoring::removeInvalidSlotRanges() { I->getOpcode() == TargetOpcode::LIFETIME_END || I->isDebugValue()) continue; + // Some intervals are suspicious! In some cases we find address + // calculations outside of the lifetime zone, but not actual memory + // read or write. Memory accesses outside of the lifetime zone are a clear + // violation, but address calculations are okay. This can happen when + // GEPs are hoisted outside of the lifetime zone. + // So, in here we only check instrucitons which can read or write memory. + if (!I->mayLoad() && !I->mayStore()) + continue; + // Check all of the machine operands. for (unsigned i = 0 ; i < I->getNumOperands(); ++i) { MachineOperand &MO = I->getOperand(i); @@ -652,7 +664,7 @@ bool StackColoring::runOnMachineFunction(MachineFunction &Func) { DEBUG(dbgs()<<"Total Stack size: "< Date: Thu, 13 Sep 2012 14:51:00 +0000 Subject: Fix a typo. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163801 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/StackColoring.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/CodeGen/StackColoring.cpp') diff --git a/lib/CodeGen/StackColoring.cpp b/lib/CodeGen/StackColoring.cpp index 1a7801abd8..832d4d1ca5 100644 --- a/lib/CodeGen/StackColoring.cpp +++ b/lib/CodeGen/StackColoring.cpp @@ -577,7 +577,7 @@ void StackColoring::removeInvalidSlotRanges() { // read or write. Memory accesses outside of the lifetime zone are a clear // violation, but address calculations are okay. This can happen when // GEPs are hoisted outside of the lifetime zone. - // So, in here we only check instrucitons which can read or write memory. + // So, in here we only check instructions which can read or write memory. if (!I->mayLoad() && !I->mayStore()) continue; -- cgit v1.2.3-18-g5258 From 18e2c290940b67c9dc1196e3c2234e7a20f60ae4 Mon Sep 17 00:00:00 2001 From: Nadav Rotem Date: Thu, 13 Sep 2012 15:46:30 +0000 Subject: Rename the flag which protects from escaped allocas, which may come from bugs in user code or in the compiler. Also, dont assert if the protection is not enabled. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@163807 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/StackColoring.cpp | 17 ++++++++++++----- 1 file changed, 12 insertions(+), 5 deletions(-) (limited to 'lib/CodeGen/StackColoring.cpp') diff --git a/lib/CodeGen/StackColoring.cpp b/lib/CodeGen/StackColoring.cpp index 832d4d1ca5..e9695b91e1 100644 --- a/lib/CodeGen/StackColoring.cpp +++ b/lib/CodeGen/StackColoring.cpp @@ -62,10 +62,15 @@ DisableColoring("no-stack-coloring", cl::init(false), cl::Hidden, cl::desc("Disable stack coloring")); + +/// The user may write code that uses allocas outside of the declared lifetime +/// zone. This can happen when the user returns a reference to a local +/// data-structure. We can detect these cases and decide not to optimize the +/// code. If this flag is enabled, we try to save the user. static cl::opt -CheckEscapedAllocas("stack-coloring-check-escaped", +ProtectFromEscapedAllocas("protect-from-escaped-allocas", cl::init(true), cl::Hidden, - cl::desc("Look for allocas which escaped the lifetime region")); + cl::desc("Do not optimize lifetime zones that are broken")); STATISTIC(NumMarkerSeen, "Number of lifetime markers found."); STATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots."); @@ -536,13 +541,15 @@ void StackColoring::remapInstructions(DenseMap &SlotRemap) { // In a debug build, check that the instruction that we are modifying is // inside the expected live range. If the instruction is not inside // the calculated range then it means that the alloca usage moved - // outside of the lifetime markers. + // outside of the lifetime markers, or that the user has a bug. // NOTE: Alloca address calculations which happen outside the lifetime // zone are are okay, despite the fact that we don't have a good way // for validating all of the usages of the calculation. #ifndef NDEBUG bool TouchesMemory = I->mayLoad() || I->mayStore(); - if (!I->isDebugValue() && TouchesMemory) { + // If we *don't* protect the user from escaped allocas, don't bother + // validating the instructions. + if (!I->isDebugValue() && TouchesMemory && ProtectFromEscapedAllocas) { SlotIndex Index = Indexes->getInstructionIndex(I); LiveInterval *Interval = Intervals[FromSlot]; assert(Interval->find(Index) != Interval->end() && @@ -685,7 +692,7 @@ bool StackColoring::runOnMachineFunction(MachineFunction &Func) { // Search for allocas which are used outside of the declared lifetime // markers. - if (CheckEscapedAllocas) + if (ProtectFromEscapedAllocas) removeInvalidSlotRanges(); // Maps old slots to new slots. -- cgit v1.2.3-18-g5258 From a26cadc58d32a739ccf99423922bfc542c1026b1 Mon Sep 17 00:00:00 2001 From: Nadav Rotem Date: Mon, 17 Sep 2012 10:21:55 +0000 Subject: Disable the protection from escaped allocas in an attempt to find violating passes. This may break the buildbots. I plan to revert it in a few hours. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@164024 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/StackColoring.cpp | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'lib/CodeGen/StackColoring.cpp') diff --git a/lib/CodeGen/StackColoring.cpp b/lib/CodeGen/StackColoring.cpp index e9695b91e1..54d8c8cde7 100644 --- a/lib/CodeGen/StackColoring.cpp +++ b/lib/CodeGen/StackColoring.cpp @@ -62,14 +62,13 @@ DisableColoring("no-stack-coloring", cl::init(false), cl::Hidden, cl::desc("Disable stack coloring")); - /// The user may write code that uses allocas outside of the declared lifetime /// zone. This can happen when the user returns a reference to a local /// data-structure. We can detect these cases and decide not to optimize the /// code. If this flag is enabled, we try to save the user. static cl::opt ProtectFromEscapedAllocas("protect-from-escaped-allocas", - cl::init(true), cl::Hidden, + cl::init(false), cl::Hidden, cl::desc("Do not optimize lifetime zones that are broken")); STATISTIC(NumMarkerSeen, "Number of lifetime markers found."); -- cgit v1.2.3-18-g5258