X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FStackColoring.cpp;h=faaa6e73e4e704c7dbddcb2841775f3317dc3073;hb=71857ccdb83b6374f7a791c2dae45ce9934a85af;hp=de365cc1ff3ef1e3ca4a2bff756b1a3f7bcf11cd;hpb=d04a8d4b33ff316ca4cf961e06c9e312eff8e64f;p=oota-llvm.git diff --git a/lib/CodeGen/StackColoring.cpp b/lib/CodeGen/StackColoring.cpp index de365cc1ff3..faaa6e73e4e 100644 --- a/lib/CodeGen/StackColoring.cpp +++ b/lib/CodeGen/StackColoring.cpp @@ -23,7 +23,6 @@ #define DEBUG_TYPE "stackcoloring" #include "llvm/CodeGen/Passes.h" -#include "MachineTraceMetrics.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/PostOrderIterator.h" @@ -40,16 +39,16 @@ #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineLoopInfo.h" -#include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/CodeGen/MachineModuleInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/PseudoSourceValue.h" #include "llvm/CodeGen/SlotIndexes.h" #include "llvm/DebugInfo.h" -#include "llvm/Function.h" -#include "llvm/Instructions.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" #include "llvm/MC/MCInstrItineraries.h" -#include "llvm/Module.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -69,14 +68,14 @@ DisableColoring("no-stack-coloring", /// code. If this flag is enabled, we try to save the user. static cl::opt ProtectFromEscapedAllocas("protect-from-escaped-allocas", - cl::init(false), cl::Hidden, - cl::desc("Do not optimize lifetime zones that are broken")); + 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"); +STATISTIC(EscapedAllocas, "Number of allocas that escaped the lifetime region"); //===----------------------------------------------------------------------===// // StackColoring Pass @@ -104,12 +103,13 @@ class StackColoring : public MachineFunctionPass { }; /// Maps active slots (per bit) for each basic block. - DenseMap BlockLiveness; + typedef DenseMap LivenessMap; + LivenessMap BlockLiveness; /// Maps serial numbers to basic blocks. - DenseMap BasicBlocks; + DenseMap BasicBlocks; /// Maps basic blocks to a serial number. - SmallVector BasicBlockNumbering; + SmallVector BasicBlockNumbering; /// Maps liveness intervals for each slot. SmallVector Intervals; @@ -146,7 +146,7 @@ public: private: /// Debug. - void dump(); + void dump() const; /// Removes all of the lifetime marker instructions from the function. /// \returns true if any markers were removed. @@ -201,31 +201,35 @@ void StackColoring::getAnalysisUsage(AnalysisUsage &AU) const { MachineFunctionPass::getAnalysisUsage(AU); } -void StackColoring::dump() { +void StackColoring::dump() const { for (df_iterator FI = df_begin(MF), FE = df_end(MF); FI != FE; ++FI) { - unsigned Num = BasicBlocks[*FI]; - DEBUG(dbgs()<<"Inspecting block #"<getName()<<"]\n"); - Num = 0; + DEBUG(dbgs()<<"Inspecting block #"<getName()<<"]\n"); + + LivenessMap::const_iterator BI = BlockLiveness.find(*FI); + assert(BI != BlockLiveness.end() && "Block not found"); + const BlockLifetimeInfo &BlockInfo = BI->second; + DEBUG(dbgs()<<"BEGIN : {"); - for (unsigned i=0; i < BlockLiveness[*FI].Begin.size(); ++i) - DEBUG(dbgs()<begin(), BE = (*FI)->end(); BI != BE; ++BI) { @@ -256,7 +263,7 @@ unsigned StackColoring::collectMarkers(unsigned NumSlot) { Markers.push_back(BI); bool IsStart = BI->getOpcode() == TargetOpcode::LIFETIME_START; - MachineOperand &MI = BI->getOperand(0); + const MachineOperand &MI = BI->getOperand(0); unsigned Slot = MI.getIndex(); MarkersFound++; @@ -268,15 +275,15 @@ unsigned StackColoring::collectMarkers(unsigned NumSlot) { } if (IsStart) { - BlockLiveness[*FI].Begin.set(Slot); + BlockInfo.Begin.set(Slot); } else { - if (BlockLiveness[*FI].Begin.test(Slot)) { + if (BlockInfo.Begin.test(Slot)) { // Allocas that start and end within a single block are handled // specially when computing the LiveIntervals to avoid pessimizing // the liveness propagation. - BlockLiveness[*FI].Begin.reset(Slot); + BlockInfo.Begin.reset(Slot); } else { - BlockLiveness[*FI].End.set(Slot); + BlockInfo.End.set(Slot); } } } @@ -293,47 +300,58 @@ void StackColoring::calculateLocalLiveness() { // formulation, and END is equivalent to GEN. The result of this computation // is a map from blocks to bitvectors where the bitvectors represent which // allocas are live in/out of that block. - SmallPtrSet BBSet(BasicBlockNumbering.begin(), - BasicBlockNumbering.end()); + SmallPtrSet BBSet(BasicBlockNumbering.begin(), + BasicBlockNumbering.end()); unsigned NumSSMIters = 0; bool changed = true; while (changed) { changed = false; ++NumSSMIters; - SmallPtrSet NextBBSet; + SmallPtrSet NextBBSet; - for (SmallVector::iterator - PI = BasicBlockNumbering.begin(), PE = BasicBlockNumbering.end(); - PI != PE; ++PI) { + for (SmallVectorImpl::iterator + PI = BasicBlockNumbering.begin(), PE = BasicBlockNumbering.end(); + PI != PE; ++PI) { - MachineBasicBlock *BB = *PI; + const MachineBasicBlock *BB = *PI; if (!BBSet.count(BB)) continue; + // Use an iterator to avoid repeated lookups. + LivenessMap::iterator BI = BlockLiveness.find(BB); + assert(BI != BlockLiveness.end() && "Block not found"); + BlockLifetimeInfo &BlockInfo = BI->second; + BitVector LocalLiveIn; BitVector LocalLiveOut; // Forward propagation from begins to ends. - for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), - PE = BB->pred_end(); PI != PE; ++PI) - LocalLiveIn |= BlockLiveness[*PI].LiveOut; - LocalLiveIn |= BlockLiveness[BB].End; - LocalLiveIn.reset(BlockLiveness[BB].Begin); + for (MachineBasicBlock::const_pred_iterator PI = BB->pred_begin(), + PE = BB->pred_end(); PI != PE; ++PI) { + LivenessMap::const_iterator I = BlockLiveness.find(*PI); + assert(I != BlockLiveness.end() && "Predecessor not found"); + LocalLiveIn |= I->second.LiveOut; + } + LocalLiveIn |= BlockInfo.End; + LocalLiveIn.reset(BlockInfo.Begin); // Reverse propagation from ends to begins. - for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), - SE = BB->succ_end(); SI != SE; ++SI) - LocalLiveOut |= BlockLiveness[*SI].LiveIn; - LocalLiveOut |= BlockLiveness[BB].Begin; - LocalLiveOut.reset(BlockLiveness[BB].End); + for (MachineBasicBlock::const_succ_iterator SI = BB->succ_begin(), + SE = BB->succ_end(); SI != SE; ++SI) { + LivenessMap::const_iterator I = BlockLiveness.find(*SI); + assert(I != BlockLiveness.end() && "Successor not found"); + LocalLiveOut |= I->second.LiveIn; + } + LocalLiveOut |= BlockInfo.Begin; + LocalLiveOut.reset(BlockInfo.End); LocalLiveIn |= LocalLiveOut; LocalLiveOut |= LocalLiveIn; // After adopting the live bits, we need to turn-off the bits which // are de-activated in this block. - LocalLiveOut.reset(BlockLiveness[BB].End); - LocalLiveIn.reset(BlockLiveness[BB].Begin); + LocalLiveOut.reset(BlockInfo.End); + LocalLiveIn.reset(BlockInfo.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 @@ -342,25 +360,25 @@ void StackColoring::calculateLocalLiveness() { // 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; + BitVector LocalEndBegin = BlockInfo.End; + LocalEndBegin &= BlockInfo.Begin; LocalLiveIn |= LocalEndBegin; LocalLiveOut |= LocalEndBegin; - if (LocalLiveIn.test(BlockLiveness[BB].LiveIn)) { + if (LocalLiveIn.test(BlockInfo.LiveIn)) { changed = true; - BlockLiveness[BB].LiveIn |= LocalLiveIn; + BlockInfo.LiveIn |= LocalLiveIn; - for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), + for (MachineBasicBlock::const_pred_iterator PI = BB->pred_begin(), PE = BB->pred_end(); PI != PE; ++PI) NextBBSet.insert(*PI); } - if (LocalLiveOut.test(BlockLiveness[BB].LiveOut)) { + if (LocalLiveOut.test(BlockInfo.LiveOut)) { changed = true; - BlockLiveness[BB].LiveOut |= LocalLiveOut; + BlockInfo.LiveOut |= LocalLiveOut; - for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), + for (MachineBasicBlock::const_succ_iterator SI = BB->succ_begin(), SE = BB->succ_end(); SI != SE; ++SI) NextBBSet.insert(*SI); } @@ -384,9 +402,9 @@ void StackColoring::calculateLiveIntervals(unsigned NumSlots) { Finishes.resize(NumSlots); // Create the interval for the basic blocks with lifetime markers in them. - for (SmallVector::iterator it = Markers.begin(), + for (SmallVectorImpl::const_iterator it = Markers.begin(), e = Markers.end(); it != e; ++it) { - MachineInstr *MI = *it; + const MachineInstr *MI = *it; if (MI->getParent() != MBB) continue; @@ -395,7 +413,7 @@ void StackColoring::calculateLiveIntervals(unsigned NumSlots) { "Invalid Lifetime marker"); bool IsStart = MI->getOpcode() == TargetOpcode::LIFETIME_START; - MachineOperand &Mo = MI->getOperand(0); + const MachineOperand &Mo = MI->getOperand(0); int Slot = Mo.getIndex(); assert(Slot >= 0 && "Invalid slot"); @@ -411,17 +429,14 @@ void StackColoring::calculateLiveIntervals(unsigned NumSlots) { } // 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); - } + BlockLifetimeInfo &MBBLiveness = BlockLiveness[MBB]; + for (int pos = MBBLiveness.LiveIn.find_first(); pos != -1; + pos = MBBLiveness.LiveIn.find_next(pos)) { + Starts[pos] = Indexes->getMBBStartIdx(MBB); + } + for (int pos = MBBLiveness.LiveOut.find_first(); pos != -1; + pos = MBBLiveness.LiveOut.find_next(pos)) { + Finishes[pos] = Indexes->getMBBEndIdx(MBB); } for (unsigned i = 0; i < NumSlots; ++i) { @@ -482,7 +497,7 @@ void StackColoring::remapInstructions(DenseMap &SlotRemap) { // Keep a list of *allocas* which need to be remapped. DenseMap Allocas; - for (DenseMap::iterator it = SlotRemap.begin(), + for (DenseMap::const_iterator it = SlotRemap.begin(), e = SlotRemap.end(); it != e; ++it) { const AllocaInst *From = MFI->getObjectAllocation(it->first); const AllocaInst *To = MFI->getObjectAllocation(it->second); @@ -511,6 +526,10 @@ void StackColoring::remapInstructions(DenseMap &SlotRemap) { if (!V) continue; + const PseudoSourceValue *PSV = dyn_cast(V); + if (PSV && PSV->isConstant(MFI)) + continue; + // Climb up and find the original alloca. V = GetUnderlyingObject(V); // If we did not find one, or if the one that we found is not in our @@ -560,7 +579,7 @@ void StackColoring::remapInstructions(DenseMap &SlotRemap) { SlotIndex Index = Indexes->getInstructionIndex(I); LiveInterval *Interval = Intervals[FromSlot]; assert(Interval->find(Index) != Interval->end() && - "Found instruction usage outside of live range."); + "Found instruction usage outside of live range."); } #endif @@ -577,8 +596,8 @@ void StackColoring::remapInstructions(DenseMap &SlotRemap) { } void StackColoring::removeInvalidSlotRanges() { - MachineFunction::iterator BB, BBE; - MachineBasicBlock::iterator I, IE; + MachineFunction::const_iterator BB, BBE; + MachineBasicBlock::const_iterator I, IE; for (BB = MF->begin(), BBE = MF->end(); BB != BBE; ++BB) for (I = BB->begin(), IE = BB->end(); I != IE; ++I) { @@ -597,7 +616,7 @@ void StackColoring::removeInvalidSlotRanges() { // Check all of the machine operands. for (unsigned i = 0 ; i < I->getNumOperands(); ++i) { - MachineOperand &MO = I->getOperand(i); + const MachineOperand &MO = I->getOperand(i); if (!MO.isFI()) continue; @@ -724,9 +743,9 @@ bool StackColoring::runOnMachineFunction(MachineFunction &Func) { std::stable_sort(SortedSlots.begin(), SortedSlots.end(), SlotSizeSorter(MFI)); - bool Chanded = true; - while (Chanded) { - Chanded = false; + bool Changed = true; + while (Changed) { + Changed = false; for (unsigned I = 0; I < NumSlots; ++I) { if (SortedSlots[I] == -1) continue; @@ -743,7 +762,7 @@ bool StackColoring::runOnMachineFunction(MachineFunction &Func) { // Merge disjoint slots. if (!First->overlaps(*Second)) { - Chanded = true; + Changed = true; First->MergeRangesInAsValue(*Second, First->getValNumInfo(0)); SlotRemap[SecondSlot] = FirstSlot; SortedSlots[J] = -1;