//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "stackcoloring"
+#include "llvm/CodeGen/Passes.h"
#include "MachineTraceMetrics.h"
-#include "llvm/Function.h"
-#include "llvm/Module.h"
#include "llvm/ADT/BitVector.h"
-#include "llvm/Analysis/Dominators.h"
-#include "llvm/Analysis/ValueTracking.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SparseSet.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/LiveInterval.h"
-#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
-#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/MachineFrameInfo.h"
-#include "llvm/CodeGen/MachineMemOperand.h"
-#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/DebugInfo.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
#include "llvm/MC/MCInstrItineraries.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
using namespace llvm;
static cl::opt<bool>
DisableColoring("no-stack-coloring",
- cl::init(true), cl::Hidden,
- cl::desc("Suppress stack coloring"));
+ cl::init(false), cl::Hidden,
+ cl::desc("Disable stack coloring"));
-STATISTIC(NumMarkerSeen, "Number of life markers found.");
+/// 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<bool>
+ProtectFromEscapedAllocas("protect-from-escaped-allocas",
+ cl::init(false), cl::Hidden,
+ 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.");
STATISTIC(StackSlotMerged, "Number of stack slot merged.");
+STATISTIC(EscapedAllocas,
+ "Number of allocas that escaped the lifetime region");
//===----------------------------------------------------------------------===//
// StackColoring Pass
/// 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.
/// slots to use the joint slots.
void remapInstructions(DenseMap<int, int> &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<int, int> &SlotRemap, unsigned NumSlots);
FI != FE; ++FI) {
// Assign a serial number to this basic block.
- BasicBlocks[*FI] = BasicBlockNumbering.size();;
+ BasicBlocks[*FI] = BasicBlockNumbering.size();
BasicBlockNumbering.push_back(*FI);
BlockLiveness[*FI].Begin.resize(NumSlot);
MarkersFound++;
- const Value* Allocation = MFI->getObjectAllocation(Slot);
+ const AllocaInst *Allocation = MFI->getObjectAllocation(Slot);
if (Allocation) {
- DEBUG(dbgs()<<"Found lifetime marker for allocation: "<<
- Allocation->getName()<<"\n");
+ DEBUG(dbgs()<<"Found a lifetime marker for slot #"<<Slot<<
+ " with allocation: "<< Allocation->getName()<<"\n");
}
if (IsStart) {
LocalLiveOut.reset(BlockLiveness[BB].End);
LocalLiveIn.reset(BlockLiveness[BB].Begin);
+ // If we have both BEGIN and END markers in the same basic block then
+ // we know that the BEGIN marker comes after the END, because we already
+ // handle the case where the BEGIN comes before the END when collecting
+ // the markers (and building the BEGIN/END vectore).
+ // Want to enable the LIVE_IN and LIVE_OUT of slots that have both
+ // BEGIN and END because it means that the value lives before and after
+ // this basic block.
+ BitVector LocalEndBegin = BlockLiveness[BB].End;
+ LocalEndBegin &= BlockLiveness[BB].Begin;
+ LocalLiveIn |= LocalEndBegin;
+ LocalLiveOut |= LocalEndBegin;
+
if (LocalLiveIn.test(BlockLiveness[BB].LiveIn)) {
changed = true;
BlockLiveness[BB].LiveIn |= LocalLiveIn;
Finishes.clear();
Finishes.resize(NumSlots);
- BitVector Alive = BlockLiveness[MBB].LiveIn;
- Alive |= BlockLiveness[MBB].LiveOut;
-
- if (Alive.any()) {
- for (int pos = Alive.find_first(); pos != -1;
- pos = Alive.find_next(pos)) {
- Starts[pos] = Indexes->getMBBStartIdx(MBB);
- Finishes[pos] = Indexes->getMBBEndIdx(MBB);
- }
- }
-
+ // Create the interval for the basic blocks with lifetime markers in them.
for (SmallVector<MachineInstr*, 8>::iterator it = Markers.begin(),
e = Markers.end(); it != e; ++it) {
MachineInstr *MI = *it;
+ if (MI->getParent() != MBB)
+ continue;
+
assert((MI->getOpcode() == TargetOpcode::LIFETIME_START ||
MI->getOpcode() == TargetOpcode::LIFETIME_END) &&
"Invalid Lifetime marker");
- if (MI->getParent() == MBB) {
- bool IsStart = MI->getOpcode() == TargetOpcode::LIFETIME_START;
- MachineOperand &Mo = MI->getOperand(0);
- int Slot = Mo.getIndex();
- assert(Slot >= 0 && "Invalid slot");
- if (IsStart) {
- Starts[Slot] = Indexes->getInstructionIndex(MI);
- } else {
- Finishes[Slot] = Indexes->getInstructionIndex(MI);
- }
+ bool IsStart = MI->getOpcode() == TargetOpcode::LIFETIME_START;
+ MachineOperand &Mo = MI->getOperand(0);
+ int Slot = Mo.getIndex();
+ assert(Slot >= 0 && "Invalid slot");
+
+ SlotIndex ThisIndex = Indexes->getInstructionIndex(MI);
+
+ if (IsStart) {
+ if (!Starts[Slot].isValid() || Starts[Slot] > ThisIndex)
+ Starts[Slot] = ThisIndex;
+ } else {
+ if (!Finishes[Slot].isValid() || Finishes[Slot] < ThisIndex)
+ Finishes[Slot] = ThisIndex;
+ }
+ }
+
+ // Create the interval of the blocks that we previously found to be 'alive'.
+ BitVector Alive = BlockLiveness[MBB].LiveIn;
+ Alive |= BlockLiveness[MBB].LiveOut;
+
+ if (Alive.any()) {
+ for (int pos = Alive.find_first(); pos != -1;
+ pos = Alive.find_next(pos)) {
+ if (!Starts[pos].isValid())
+ Starts[pos] = Indexes->getMBBStartIdx(MBB);
+ if (!Finishes[pos].isValid())
+ Finishes[pos] = Indexes->getMBBEndIdx(MBB);
}
}
for (unsigned i = 0; i < NumSlots; ++i) {
- assert(!!Starts[i] == !!Finishes[i] && "Unmatched range");
- if (Starts[i] == Finishes[i])
+ assert(Starts[i].isValid() == Finishes[i].isValid() && "Unmatched range");
+ if (!Starts[i].isValid())
continue;
assert(Starts[i] && Finishes[i] && "Invalid interval");
}
// Keep a list of *allocas* which need to be remapped.
- DenseMap<const Value*, const Value*> Allocas;
+ DenseMap<const AllocaInst*, const AllocaInst*> Allocas;
for (DenseMap<int, int>::iterator it = SlotRemap.begin(),
e = SlotRemap.end(); it != e; ++it) {
- const Value* From = MFI->getObjectAllocation(it->first);
- const Value* To = MFI->getObjectAllocation(it->second);
+ const AllocaInst *From = MFI->getObjectAllocation(it->first);
+ const AllocaInst *To = MFI->getObjectAllocation(it->second);
assert(To && From && "Invalid allocation object");
Allocas[From] = To;
}
for (BB = MF->begin(), BBE = MF->end(); BB != BBE; ++BB)
for (I = BB->begin(), IE = BB->end(); I != IE; ++I) {
+ // Skip lifetime markers. We'll remove them soon.
+ if (I->getOpcode() == TargetOpcode::LIFETIME_START ||
+ I->getOpcode() == TargetOpcode::LIFETIME_END)
+ continue;
+
// Update the MachineMemOperand to use the new alloca.
for (MachineInstr::mmo_iterator MM = I->memoperands_begin(),
E = I->memoperands_end(); MM != E; ++MM) {
V = GetUnderlyingObject(V);
// If we did not find one, or if the one that we found is not in our
// map, then move on.
- if (!V || !Allocas.count(V))
+ if (!V || !isa<AllocaInst>(V)) {
+ // Clear mem operand since we don't know for sure that it doesn't
+ // alias a merged alloca.
+ MMO->setValue(0);
+ continue;
+ }
+ const AllocaInst *AI= cast<AllocaInst>(V);
+ if (!Allocas.count(AI))
continue;
- MMO->setValue(Allocas[V]);
+ MMO->setValue(Allocas[AI]);
FixedMemOp++;
}
if (!SlotRemap.count(FromSlot))
continue;
+ // 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, 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 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() &&
+ "Found instruction usage outside of live range.");
+ }
+#endif
+
// Fix the machine instructions.
int ToSlot = SlotRemap[FromSlot];
MO.setIndex(ToSlot);
DEBUG(dbgs()<<"Fixed "<<FixedInstr<<" machine instructions.\n");
}
+void StackColoring::removeInvalidSlotRanges() {
+ MachineFunction::iterator BB, BBE;
+ MachineBasicBlock::iterator I, IE;
+ for (BB = MF->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;
+
+ // 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 instructions 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);
+
+ 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 #"<<Slot<<"\n");
+ EscapedAllocas++;
+ }
+ }
+ }
+}
+
void StackColoring::expungeSlotMap(DenseMap<int, int> &SlotRemap,
unsigned NumSlots) {
// Expunge slot remap map.
bool StackColoring::runOnMachineFunction(MachineFunction &Func) {
DEBUG(dbgs() << "********** Stack Coloring **********\n"
<< "********** Function: "
- << ((Value*)Func.getFunction())->getName() << '\n');
+ << ((const Value*)Func.getFunction())->getName() << '\n');
MF = &Func;
MFI = MF->getFrameInfo();
Indexes = &getAnalysis<SlotIndexes>();
DEBUG(dbgs()<<"Total Stack size: "<<TotalSize<<" bytes\n\n");
// Don't continue because there are not enough lifetime markers, or the
- // stack or too small, or we are told not to optimize the slots.
+ // stack is too small, or we are told not to optimize the slots.
if (NumMarkers < 2 || TotalSize < 16 || DisableColoring) {
DEBUG(dbgs()<<"Will not try to merge slots.\n");
return removeAllMarkers();
// Propagate the liveness information.
calculateLiveIntervals(NumSlots);
+ // Search for allocas which are used outside of the declared lifetime
+ // markers.
+ if (ProtectFromEscapedAllocas)
+ removeInvalidSlotRanges();
+
// Maps old slots to new slots.
DenseMap<int, int> SlotRemap;
unsigned RemovedSlots = 0;
// and continue.
// Sort the slots according to their size. Place unused slots at the end.
- std::sort(SortedSlots.begin(), SortedSlots.end(), SlotSizeSorter(MFI));
+ // Use stable sort to guarantee deterministic code generation.
+ std::stable_sort(SortedSlots.begin(), SortedSlots.end(),
+ SlotSizeSorter(MFI));
bool Chanded = true;
while (Chanded) {
if (SortedSlots[I] == -1)
continue;
- for (unsigned J=0; J < NumSlots; ++J) {
+ for (unsigned J=I+1; J < NumSlots; ++J) {
if (SortedSlots[J] == -1)
continue;
First->MergeRangesInAsValue(*Second, First->getValNumInfo(0));
SlotRemap[SecondSlot] = FirstSlot;
SortedSlots[J] = -1;
- DEBUG(dbgs()<<"Merging #"<<I<<" and slots #"<<J<<" together.\n");
+ DEBUG(dbgs()<<"Merging #"<<FirstSlot<<" and slots #"<<
+ SecondSlot<<" together.\n");
unsigned MaxAlignment = std::max(MFI->getObjectAlignment(FirstSlot),
MFI->getObjectAlignment(SecondSlot));
projects / oota-llvm.git / blobdiff